  This paper introduces the targeted sampling model in optimal auction design.
In this model, the seller may specify a quantile interval and sample from a
buyer's prior restricted to the interval. This can be interpreted as allowing
the seller to, for example, examine the top $40$ percents bids from previous
buyers with the same characteristics. The targeting power is quantified with a
parameter $\Delta \in [0, 1]$ which lower bounds how small the quantile
intervals could be. When $\Delta = 1$, it degenerates to Cole and Roughgarden's
model of i.i.d. samples; when it is the idealized case of $\Delta = 0$, it
degenerates to the model studied by Chen et al. (2018). For instance, for $n$
buyers with bounded values in $[0, 1]$, $\tilde{O}(\epsilon^{-1})$ targeted
samples suffice while it is known that at least $\tilde{\Omega}(n
\epsilon^{-2})$ i.i.d. samples are needed. In other words, targeted sampling
with sufficient targeting power allows us to remove the linear dependence in
$n$, and to improve the quadratic dependence in $\epsilon^{-1}$ to linear. In
this work, we introduce new technical ingredients and show that the number of
targeted samples sufficient for learning an $\epsilon$-optimal auction is
substantially smaller than the sample complexity of i.i.d. samples for the full
spectrum of $\Delta \in [0, 1)$. Even with only mild targeting power, i.e.,
whenever $\Delta = o(1)$, our targeted sample complexity upper bounds are
strictly smaller than the optimal sample complexity of i.i.d. samples.
