  We study multi-item profit maximization when there is an underlying
distribution over buyers' values. In practice, a full description of the
distribution is typically unavailable, so we study the setting where the
mechanism designer only has samples from the distribution. If the designer uses
the samples to optimize over a complex mechanism class -- such as the set of
all multi-item, multi-buyer mechanisms -- a mechanism may have high average
profit over the samples but low expected profit. This raises the central
question of this paper: how many samples are sufficient to ensure that a
mechanism's average profit is close to its expected profit? To answer this
question, we uncover structure shared by many pricing, auction, and lottery
mechanisms: for any set of buyers' values, profit is piecewise linear in the
mechanism's parameters. Using this structure, we prove new bounds for mechanism
classes not yet studied in the sample-based mechanism design literature and
match or improve over the best-known guarantees for many classes.
