A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity

Peter D. Grünwald, Nishant A. Mehta

TL;DR

This paper introduces a novel, unified complexity measure that bridges PAC-Bayesian and Rademacher complexity, offering a more general framework for analyzing learning algorithms. This new measure allows for tighter excess risk bounds, recovering optimal rates for various classes of learning problems and unifying previously disparate theoretical results.

What Problem Does This Paper Address?

In statistical learning theory, understanding the generalization ability of algorithms (how well they perform on unseen data) is crucial. This is often achieved by bounding the "excess risk," which is the difference between an algorithm's performance and the best possible performance on the given data. Various complexity measures have been developed to provide these bounds, such as Rademacher complexity (for empirical risk minimization) and information complexity (for Bayesian methods). However, these measures often apply to specific types of algorithms or loss functions and don't easily unify. For instance, standard PAC-Bayesian bounds often don't achieve optimal rates for large classes, while Rademacher complexity analyses can be complex to extend to penalized estimators or generalized Bayesian approaches. This paper aims to bridge this gap by introducing a unified complexity notion that generalizes existing ones and allows for tighter, more broadly applicable excess risk bounds.

Methods

The core contribution is the introduction of a new complexity measure, COMP, which interpolates between data-dependent PAC-Bayesian complexity and data-independent Rademacher complexity. This is achieved by defining a "luckiness function" $w$ that can be adapted to the specific learning problem.

  • Unified Complexity Measure (COMP): This measure is built upon a generalized Shtarkov integral and can be seen as a data-dependent generalization of Rademacher and information complexity. The choice of the luckiness function $w$ allows for a spectrum of complexities, from data-independent (reducing to NML complexity for log-loss) to data-dependent (connecting to PAC-Bayesian information complexity).
  • Annealed Expectation and Exponential Stochastic Inequality (ESI): The paper uses these tools to establish the first main result: a bound on the annealed excess risk in terms of the new COMP. ESI provides a powerful way to relate high-probability and in-expectation bounds.
  • v-Central and Bernstein Conditions: To bridge the gap between annealed and actual excess risk, the authors leverage the v-central condition, which is shown to be equivalent to the Bernstein condition for bounded losses. This allows them to derive actual excess risk bounds.
  • H-local Complexity and Rademacher Complexity: The paper then connects the new COMP to H-local complexity and Rademacher complexity, providing explicit bounds for various classes of functions (VC-type, polynomial empirical entropy, polynomial entropy with bracketing). This allows for the recovery of optimal learning rates.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and bounds, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • A Unified Complexity Framework: The most significant insight is the creation of a single complexity measure that elegantly unifies and generalizes several existing notions (PAC-Bayesian, Rademacher, NML). This suggests a deeper underlying structure in learning theory.
  • The Role of the "Luckiness Function": The introduction of the luckiness function $w$ is a key innovation. It acts as a flexible parameter that allows the complexity measure to adapt to different learning scenarios, bridging the gap between data-dependent and data-independent approaches.
  • Separation of "Easiness" and Model Complexity: The new framework allows for a cleaner separation of the two key factors determining learning rates: the "easiness" of the problem (captured by Bernstein conditions) and the complexity of the model class. This simplifies the analysis.
  • Tight Bounds and Optimal Rates: The paper demonstrates that this unified approach leads to tight bounds and recovers known optimal learning rates for various function classes, including VC-type and polynomial entropy classes. This validates the power of the new complexity measure.
  • Connection to Data Compression: The interpretation of the complexity measure in terms of codelengths highlights a deep connection between learning theory and information theory/data compression.

Key Results

  • Theorem 4: Establishes a bound on the annealed excess risk in terms of the new unified complexity measure (COMPFULL). This generalizes existing PAC-Bayesian bounds.
  • Theorem 10: Provides bounds on the NML complexity (a data-independent version of COMP) in terms of H-local complexity and Rademacher complexity.
  • Theorems 15, 16, 17: Derive explicit bounds on COMP for VC-type classes, classes with polynomial empirical entropy, and classes with polynomial entropy with bracketing. These results are crucial for obtaining concrete learning rates.
  • Theorem 20: Recovers known optimal learning rates for ERM under Bernstein conditions for these classes, demonstrating the practical utility of the theoretical framework. For VC-type classes, it achieves rates of $O(n^{-1})$ (for $\beta=1$) and $O(n^{-1/2})$ (for $\beta=0$). For polynomial entropy classes, it achieves rates of $O(n^{-1/(2-\beta)})$.

Limitations and Future Work

  • Bounded Losses: The primary theoretical results are derived under the assumption of bounded losses. While some extensions to unbounded losses are mentioned, the core analysis relies on this assumption.
  • Distribution-Dependent Bounds: The derived bounds are often distribution-dependent (oracle inequalities), meaning they depend on the unknown true data-generating distribution $P$ (e.g., through the Bernstein condition). This makes them less directly applicable in practice without estimating these conditions.
  • Computational Issues: The paper notes that for practical application of some methods (like the two-part MDL estimator), determining the optimal parameters (like $\eta$) can be challenging as they depend on unknown properties of the data distribution.
  • Future Work: The authors suggest several avenues for future research, including extending the framework to handle unbounded losses more generally, developing data-dependent analogues of Rademacher complexities, and exploring the implications of the unified complexity for other learning settings and algorithms. They also highlight the potential for further connections to data compression and information theory.

Summary updated

Abstract

We present a novel notion of complexity that interpolates between and generalizes some classic existing complexity notions in learning theory: for estimators like empirical risk minimization (ERM) with arbitrary bounded losses, it is upper bounded in terms of data-independent Rademacher complexity; for generalized Bayesian estimators, it is upper bounded by the data-dependent information complexity (also known as stochastic or PAC-Bayesian, $\mathrm{KL}(\text{posterior} \operatorname{\|} \text{prior})$ complexity. For (penalized) ERM, the new complexity reduces to (generalized) normalized maximum likelihood (NML) complexity, i.e. a minimax log-loss individual-sequence regret. Our first main result bounds excess risk in terms of the new complexity. Our second main result links the new complexity via Rademacher complexity to $L_2(P)$ entropy, thereby generalizing earlier results of Opper, Haussler, Lugosi, and Cesa-Bianchi who did the log-loss case with $L_\infty$. Together, these results recover optimal bounds for VC- and large (polynomial entropy) classes, replacing localized Rademacher complexity by a simpler analysis which almost completely separates the two aspects that determine the achievable rates: 'easiness' (Bernstein) conditions and model complexity.
BibTeX
@inproceedings{grunwald2019tight,
  author = {Peter D. Grünwald and Nishant A. Mehta},
  title = {{A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity}},
  booktitle = {ALT},
  year = {2019},
  url = {https://openreview.net/forum?id=YA3E-hFBsQh},
}
Figure