  In the design and analysis of revenue-maximizing auctions, auction
performance is typically measured with respect to a prior distribution over
inputs. The most obvious source for such a distribution is past data. The goal
is to understand how much data is necessary and sufficient to guarantee
near-optimal expected revenue.
  Our basic model is a single-item auction in which bidders' valuations are
drawn independently from unknown and non-identical distributions. The seller is
given $m$ samples from each of these distributions "for free" and chooses an
auction to run on a fresh sample. How large does m need to be, as a function of
the number k of bidders and eps > 0, so that a (1 - eps)-approximation of the
optimal revenue is achievable?
  We prove that, under standard tail conditions on the underlying
distributions, m = poly(k, 1/eps) samples are necessary and sufficient. Our
lower bound stands in contrast to many recent results on simple and
prior-independent auctions and fundamentally involves the interplay between
bidder competition, non-identical distributions, and a very close (but still
constant) approximation of the optimal revenue. It effectively shows that the
only way to achieve a sufficiently good constant approximation of the optimal
revenue is through a detailed understanding of bidders' valuation
distributions. Our upper bound is constructive and applies in particular to a
variant of the empirical Myerson auction, the natural auction that runs the
revenue-maximizing auction with respect to the empirical distributions of the
samples.
  Our sample complexity lower bound depends on the set of allowable
distributions, and to capture this we introduce alpha-strongly regular
distributions, which interpolate between the well-studied classes of regular
(alpha = 0) and MHR (alpha = 1) distributions. We give evidence that this
definition is of independent interest.
