  Traditionally, the Bayesian optimal auction design problem has been
considered either when the bidder values are i.i.d., or when each bidder is
individually identifiable via her value distribution. The latter is a
reasonable approach when the bidders can be classified into a few categories,
but there are many instances where the classification of bidders is a
continuum. For example, the classification of the bidders may be based on their
annual income, their propensity to buy an item based on past behavior, or in
the case of ad auctions, the click through rate of their ads. We introduce an
alternate model that captures this aspect, where bidders are \emph{a priori}
identical, but can be distinguished based (only) on some side information the
auctioneer obtains at the time of the auction.
  We extend the sample complexity approach of Dhangwatnotai, Roughgarden, and
Yan (2014) and Cole and Roughgarden (2014) to this model and obtain almost
matching upper and lower bounds. As an aside, we obtain a revenue monotonicity
lemma which may be of independent interest. We also show how to use Empirical
Risk Minimization techniques to improve the sample complexity bound of Cole and
Roughgarden (2014) for the non-identical but independent value distribution
case.
