One fundamental goal in any learning algorithm is to mitigate its risk for overfitting. Mathematically, this requires that the learning algorithm enjoys a small generalization risk, which is defined either in expectation or in probability. Both types of generalization are commonly used in the literature. For instance, generalization in expectation has been used to analyze algorithms, such as ridge regression and SGD, whereas generalization in probability is used in the VC theory, among others. Recently, a third notion of generalization has been studied, called uniform generalization, which requires that the generalization risk vanishes uniformly in expectation across all bounded parametric losses. It has been shown that uniform generalization is, in fact, equivalent to an information-theoretic stability constraint, and that it recovers classical results in learning theory. It is achievable under various settings, such as sample compression schemes, finite hypothesis spaces, finite domains, and differential privacy. However, the relationship between uniform generalization and concentration remained unknown. In this paper, we answer this question by proving that, while a generalization in expectation does not imply a generalization in probability, a uniform generalization in expectation does imply concentration. We establish a chain rule for the uniform generalization risk of the composition of hypotheses and use it to derive a large deviation bound. Finally, we prove that the bound is tight.
As a consequence of our main theorem, concentration bounds for a given learning algorithm can be immediately deduced once we recognize that the algorithm generalizes uniformly in expectation. Examples of when this holds include having (1) a finite average description length of the hypothesis, (2) a finite VC dimension of the , (3) differential privacy, (4) robust generalization, (5) typical generalization, (6) bounded mutual information, and (7) finite domains. We briefly describe these settings that have been previously studied in the literature and prove their connections to uniform generalization in Appendix . We also present connections between uniform generalization and learnability in Appendix . A second consequence of our work is establishing the equivalence between the notion of uniform generalization studied by @cite_2 and the notion of considered more recently by @cite_0 .
@cite_0 @cite_2
2279913547 2188409822
The traditional notion of generalization---i.e., learning a hypothesis whose empirical error is close to its true error---is surprisingly brittle. As has recently been noted in [DFH+15b], even if several algorithms have this guarantee in isolation, the guarantee need not hold if the algorithms are composed adaptively. In this paper, we study three notions of generalization---increasing in strength---that are robust to postprocessing and amenable to adaptive composition, and examine the relationships between them. We call the weakest such notion Robust Generalization. A second, intermediate, notion is the stability guarantee known as differential privacy. The strongest guarantee we consider we call Perfect Generalization. We prove that every hypothesis class that is PAC learnable is also PAC learnable in a robustly generalizing fashion, with almost the same sample complexity. It was previously known that differentially private algorithms satisfy robust generalization. In this paper, we show that robust generalization is a strictly weaker concept, and that there is a learning task that can be carried out subject to robust generalization guarantees, yet cannot be carried out subject to differential privacy. We also show that perfect generalization is a strictly stronger guarantee than differential privacy, but that, nevertheless, many learning tasks can be carried out subject to the guarantees of perfect generalization. 1.1. Introduction.- 1.2. Outer Integrals and Measurable Majorants.- 1.3. Weak Convergence.- 1.4. Product Spaces.- 1.5. Spaces of Bounded Functions.- 1.6. Spaces of Locally Bounded Functions.- 1.7. The Ball Sigma-Field and Measurability of Suprema.- 1.8. Hilbert Spaces.- 1.9. Convergence: Almost Surely and in Probability.- 1.10. Convergence: Weak, Almost Uniform, and in Probability.- 1.11. Refinements.- 1.12. Uniformity and Metrization.- 2.1. Introduction.- 2.2. Maximal Inequalities and Covering Numbers.- 2.3. Symmetrization and Measurability.- 2.4. Glivenko-Cantelli Theorems.- 2.5. Donsker Theorems.- 2.6. Uniform Entropy Numbers.- 2.7. Bracketing Numbers.- 2.8. Uniformity in the Underlying Distribution.- 2.9. Multiplier Central Limit Theorems.- 2.10. Permanence of the Donsker Property.- 2.11. The Central Limit Theorem for Processes.- 2.12. Partial-Sum Processes.- 2.13. Other Donsker Classes.- 2.14. Tail Bounds.- 3.1. Introduction.- 3.2. M-Estimators.- 3.3. Z-Estimators.- 3.4. Rates of Convergence.- 3.5. Random Sample Size, Poissonization and Kac Processes.- 3.6. The Bootstrap.- 3.7. The Two-Sample Problem.- 3.8. Independence Empirical Processes.- 3.9. The Delta-Method.- 3.10. Contiguity.- 3.11. Convolution and Minimax Theorems.- A. Appendix.- A.1. Inequalities.- A.2. Gaussian Processes.- A.2.1. Inequalities and Gaussian Comparison.- A.2.2. Exponential Bounds.- A.2.3. Majorizing Measures.- A.2.4. Further Results.- A.3. Rademacher Processes.- A.4. Isoperimetric Inequalities for Product Measures.- A.5. Some Limit Theorems.- A.6. More Inequalities.- A.6.1. Binomial Random Variables.- A.6.2. Multinomial Random Vectors.- A.6.3. Rademacher Sums.- Notes.- References.- Author Index.- List of Symbols. Suppose that G is a finite, connected graph and X is a lazy random walk on G . The lamplighter chain X ? associated with X is the random walk on the wreath product G ? =Z 2 ?G , the graph whose vertices consist of pairs (f - ,x) where f is a labeling of the vertices of G by elements of Z 2 = 0,1 and x is a vertex in G . There is an edge between (f - ,x) and (g - ,y) in G ? if and only if x is adjacent to y in G and f z =g z for all z?x,y . In each step, X ? moves from a configuration (f - ,x) by updating x to y using the transition rule of X and then sampling both f x and f y according to the uniform distribution on Z 2 ; f z for z?x,y remains unchanged. We give matching upper and lower bounds on the uniform mixing time of X ? provided G satisfies mild hypotheses. In particular, when G is the hypercube Z d 2 , we show that the uniform mixing time of X ? is T(d2 d ) . More generally, we show that when G is a torus Z d n for d=3 , the uniform mixing time of X ? is T(dn d ) uniformly in n and d . A critical ingredient for our proof is a concentration estimate for the local time of the random walk in a subset of vertices. I Functional on Stochastic Processes.- 1. Stochastic Processes as Random Functions.- Notes.- Problems.- II Uniform Convergence of Empirical Measures.- 1. Uniformity and Consistency.- 2. Direct Approximation.- 3. The Combinatorial Method.- 4. Classes of Sets with Polynomial Discrimination.- 5. Classes of Functions.- 6. Rates of Convergence.- Notes.- Problems.- III Convergence in Distribution in Euclidean Spaces.- 1. The Definition.- 2. The Continuous Mapping Theorem.- 3. Expectations of Smooth Functions.- 4. The Central Limit Theorem.- 5. Characteristic Functions.- 6. Quantile Transformations and Almost Sure Representations.- Notes.- Problems.- IV Convergence in Distribution in Metric Spaces.- 1. Measurability.- 2. The Continuous Mapping Theorem.- 3. Representation by Almost Surely Convergent Sequences.- 4. Coupling.- 5. Weakly Convergent Subsequences.- Notes.- Problems.- V The Uniform Metric on Spaces of Cadlag Functions.- 1. Approximation of Stochastic Processes.- 2. Empirical Processes.- 3. Existence of Brownian Bridge and Brownian Motion.- 4. Processes with Independent Increments.- 5. Infinite Time Scales.- 6. Functional of Brownian Motion and Brownian Bridge.- Notes.- Problems.- VI The Skorohod Metric on D(0, ?).- 1. Properties of the Metric.- 2. Convergence in Distribution.- Notes.- Problems.- VII Central Limit Theorems.- 1. Stochastic Equicontinuity.- 2. Chaining.- 3. Gaussian Processes.- 4. Random Covering Numbers.- 5. Empirical Central Limit Theorems.- 6. Restricted Chaining.- Notes.- Problems.- VIII Martingales.- 1. A Central Limit Theorem for Martingale-Difference Arrays.- 2. Continuous Time Martingales.- 3. Estimation from Censored Data.- Notes.- Problems.- Appendix A Stochastic-Order Symbols.- Appendix B Exponential Inequalities.- Notes.- Problems.- Appendix C Measurability.- Notes.- Problems.- References.- Author Index.