  In this paper we introduce Sampling with a Black Box, a generic technique for
the design of parameterized approximation algorithms for vertex deletion
problems (e.g., Vertex Cover, Feedback Vertex Set, etc.). The technique relies
on two components:
  $\bullet$ A Sampling Step. A polynomial time randomized algorithm which given
a graph $G$ returns a random vertex $v$ such that the optimum of $G\setminus
\{v\}$ is smaller by $1$ than the optimum of $G$ with some prescribed
probability $q$. We show such algorithms exists for multiple vertex deletion
problems.
  $\bullet$ A Black Box algorithm which is either an exact parameterized
algorithm or a polynomial time approximation algorithm.
  Our technique combines these two components together. The sampling step is
applied iteratively to remove vertices from the input graph, and then the
solution is extended using the black box algorithm. The process is repeated
sufficiently many times so that the target approximation ratio is attained with
a constant probability. The main novelty of our work lies in the analysis of
the framework and the optimization of the parameters it uses.
  We use the technique to derive parameterized approximation algorithm for
several vertex deletion problems, including Feedback Vertex Set, $d$-Hitting
Set and $\ell$-Path Vertex Cover. In particular, for every approximation ratio
$1<\beta<2$, we attain a parameterized $\beta$-approximation for Feedback
Vertex Set which is faster than the parameterized $\beta$-approximation of
[Jana, Lokshtanov, Mandal, Rai and Saurabh, MFCS 23']. Furthermore, our
algorithms are always faster than the algorithms attained using Fidelity
Preserving Transformations [Fellows, Kulik, Rosamond, and Shachnai, JCSS 18'].
