A Sample Complexity Measure with Applications to Learning Optimal Auctions
We introduce a new sample complexity measure, which we refer to as split-sample growth rate. For any hypothesis H and for any sample S of size m, the splitsample growth rateτ H (m) counts how many different hypotheses can empirical risk minimization output on any sub-sample of S of size m/2. We show that the expected generalization error is upper bounded by O log(τ H (2m)) m . Our result is enabled by a strengthening of the Rademacher complexity analysis of the expected generalization error. We show that this sample complexity measure, greatly simplifies the analysis of the sample complexity of optimal auction design, for many auction classes studied in the literature. Their sample complexity can be derived solely by noticing that in these auction classes, ERM on any sample or sub-sample will pick parameters that are equal to one of the points in the sample.
Summary:
Rademacher complexity is a powerful tool for producing generalization guarantees. The Rademacher complexity of a class H on a sample S is roughly the expected maximum gap between training and test performance if S were randomly partitioned into training and test sets, and we took the maximum over all h in H (eqn 11).  This paper makes the observation that the core steps in the standard generalization bound proof will still go through if instead of taking the max over all h in H, you only look at the h's that your procedure can possibly output when given half of a double sample (Lemma 1).  While unfortunately the usual final (or initial) high-probability step in this argument does not seem to go through directly, the paper shows (Theorem 2) that one can nonetheless get a useful generation bound from this using other means.  The paper then shows how this generalization bound yields good sample complexity guarantees for a number of natural auction classes.  In several cases, this improves over the best prior guarantees known, and also simplifies their analysis.
Evaluation:
While the core idea is to some extent an observation, I like the paper because it is a nice, cute idea that one could actually teach in a class.  And it allows for a simpler sample complexity analysis for auctions, which is great.  It may also have other uses too.  On the negative side, I wish the paper were able to answer whether the linear dependence on 1/delta is really necessary (see below).  That would make the paper feel more complete to me.  Still, I am overall positive.
Questions:
Do you know if the linear dependence on delta in Theorem 2 is required?  I see why you need it in your proof (due to using Markov) and you explain nicely why the usual use of McDiarmid to get an O(log(1/delta)) bound doesn't go through.  But this leaves open whether (a) there is a different way to get an O(log(1/delta)) bound, or on the other hand (b) there exist D,H for which you indeed have a more heavy-tailed chance of failure.   If this were resolved, the paper would feel more complete.
On a related note, do you know if you can get a bound along the lines of Theorem 2 in terms of the maximum # of hypotheses that can be produced from half of the *actual* sample S? (That is, replacing the sup over S of size m in the definition of \hat{\tau} with the actual training sample S?)
Suggestions: 
- If I am not mistaken, The proof of Lemma 1 basically goes through the textbook Rademacher bound proof, changing it where needed to replace H with \hat{H}_{S \union S'}.  That's fine, but you should explicitly tell the reader that that is what you are doing up front, so they know what's new vs what's old.  E.g., you have a nice discussion of this form for Theorem 2, where you talk about where it differs from the usual argument, that I think is quite useful.
- In Section 4 you examine several interesting scenarios (single bidder, multiple iid regular,...) , and for each one you say "In this case, the space of hypotheses H is ...".  I think what you mean to say is more that "In this case, it is known that an *optimal auction belongs to* the hypothesis class H of ...".  In other words, the generalization guarantees apply to any H you want, but now you are saying what the meaningful H is in each scenario, right?  I think this is worth saying explicitly, since otherwise the reader might get confused why H is changing each time.
Also I'll point out that the idea of counting the number of possible outputs of an auction mechanism in order to get a sample complexity bound has been used in the auction literature before. The first I know of is the FOCS 2005 paper "Mechanism design via machine learning" by Balcan, Blum, Hartline, and Mansour, though that paper operates in a transductive setting where an argument of this type is much easier to make.