Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the kth moment of the valuations, for any (possibly fractional) k > 1. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.
This paper provides a generalization of the Glivenko-Cantelli theorem, a "submultiplicative" compromise between additive and multiplicative errors. The two main results go hand in hand, the first dealing with existence of a sufficient index which guarantees submultiplicativity and the second providing an upper bound on such an index in order to provide ease in applying the results. It is clear that only submultiplicative results are possible due to a simple counterexample given. The proofs of the main results are technical, but mathematically clear. 
Throughout the paper, the author(s) familiarity with previous work with generalizing the Glivenko-Cantelli theorem is verified, and the novelty of the work is demonstrated.
The author(s) apply these results to the problem of estimating revenue in an auction via empirical revenues. It is clear that understanding revenue estimation better will lend itself to revenue maximization. Moreover, investigating the connection between finite moments and uniform convergence in this example can offer a framework for exploring other estimators in a similar way.
While the paper is well-written, and I believe the results to be significant and even fundamental, I felt that the example given, while interesting, was quite specialized and detracted somewhat from generality of the paper. Even more detail in the discussion section on the potential impact to the learning theory community would be great.
Additional notes:
The definition of F_n(t) on lines 22 and 23 is hard to read. 
The phrasing on lines 66-68 is awkward. 
Between lines 104 and 105, why not continue with notation similar to that introduced in Theorem 1.3 for consistency?