Exponential Generalization Bounds with Near-Optimal Rates for $L_q$-Stable Algorithms

Xiaotong Yuan, Ping LiICLR 2023 · OpenReview

Introduction: The Algorithmic Stability Bottleneck

A central question in statistical learning theory is understanding how well a model will perform on unseen data. To answer this, researchers frequently rely on the concept of "algorithmic stability"—a measure of how much a model's output changes if a single training example is swapped out.

Historically, stability analysis has been divided into two primary flavors:

  1. Uniform Stability: Considered the "gold standard," this strong, distribution-free notion leads to tight, near-optimal generalization bounds. However, it is often too restrictive for real-world scenarios, particularly those involving unbounded loss functions.
  2. $L_q$-Stability: A more relaxed, distribution-dependent alternative that is much easier to satisfy in practice. Unfortunately, the mathematical bounds derived from $L_q$-stability have traditionally been sub-optimal, burdened by a $\sqrt{N}$ overhead factor that renders them loose and less useful for large datasets.

This paper tackles a fundamental theoretical question: Is it possible to derive near-optimal exponential generalization bounds for $L_q$-stable algorithms that match the performance of their more restrictive uniform counterparts? By providing an affirmative answer, the authors bridge a significant gap in machine learning theory.

Methodological Innovations: The Logarithmic Leap

The authors achieve their breakthrough via a series of key theoretical innovations, most notably a novel concentration inequality. Their core contribution generalizes previous work on "uniform bounded differences" to the more flexible setting of "$L_q$-norm bounded differences" for sums of random functions.

Using this new inequality, the authors conduct a refined stability analysis that successfully reduces the stability overhead factor from $O(\sqrt{N})$ to $O(\log N)$. This "logarithmic leap" is a massive improvement in high-dimensional statistics, ensuring that generalization bounds remain tight and meaningful even as the sample size $N$ grows exceptionally large. Ultimately, the paper proves that $L_q$-stability is "strong enough" to provide near-optimal generalization without requiring the brute force of uniform stability.

Key Theoretical Results

The paper formalizes these insights through several major theorems (note that this is a purely theoretical work, so no empirical datasets were used):

  • Generalization Bounds (Theorem 2): The authors prove that for $L_q$-stable algorithms, the generalization gap scales with $q\gamma_q \log N + M_q \sqrt{q/N}$. This matches the near-optimal rates previously known only for uniformly stable algorithms.
  • Excess Risk (Theorem 3): The work establishes sharp excess risk bounds under standard assumptions, such as the Bernstein condition or quadratic growth.
  • Sparse Excess Risk (Theorem 4): The authors provide a new exponential risk bound specifically tailored for Iterative Hard Thresholding (IHT) style algorithms. For well-specified models, the bound scales roughly as $\frac{(k \log d + \log(1/\delta))^2 \log^2 N}{N}$, where $k$ is sparsity and $d$ is the dimension.

Application to Sparse Learning

To demonstrate the practical power of their improved theory, the authors apply it to Inexact $L_0$-ERM (Empirical Risk Minimization). They show that computationally tractable algorithms used for high-dimensional sparse recovery, such as Iterative Hard Thresholding (IHT), are $L_q$-stable under mild conditions.

Crucially, the authors demonstrate that sparse recovery algorithms are almost always stable over a fixed supporting set. This allows them to leverage their new $L_q$-stability theory to provide the first near-optimal exponential risk bounds for these estimators. Furthermore, these bounds naturally adapt to "well-specified" cases (where the true underlying model is actually sparse), achieving faster convergence rates of $1/N$ compared to the previously established "slow" rates of $1/\sqrt{N}$.

Limitations and Future Directions

While the paper makes significant strides, the authors note a slight deterioration in their $L_q$-stability tail bounds compared to uniform stability, specifically regarding poly-logarithmic terms. They attribute this to the inherent uncertainty of data distributions in the $L_q$ setting.

To remedy this, they suggest that future work could explore exponential versions of the Efron-Stein inequality, rather than the moment-based variants utilized in this study. Additionally, while the current work focuses heavily on IHT, the theoretical framework could be extended to other non-uniformly stable settings, such as unbounded ridge regression and $k$-fold cross-validation.

Summary updated

Abstract

The \emph{stability} of learning algorithms to changes in the training sample has been actively studied as a powerful proxy for reasoning about generalization. Recently, exponential generalization and excess risk bounds with near-optimal rates have been obtained under the stringent and distribution-free notion of uniform stability~\citep{bousquet2020sharper,klochkov2021stability}. In the meanwhile, under the notion of $L_q$-stability, which is weaker and distribution dependent, exponential generalization bounds are also available yet so far only with sub-optimal rates. Therefore, a fundamental question we would like to address in this paper is whether it is possible to derive near-optimal exponential generalization bounds for $L_q$-stable learning algorithms. As the core contribution of the present work, we give an affirmative answer to this question by developing strict analogues of the near-optimal generalization and risk bounds of uniformly stable algorithms for $L_q$-stable algorithms. Further, we demonstrate the power of our improved $L_q$-stability and generalization theory by applying it to derive strong sparse excess risk bounds, under mild conditions, for computationally tractable sparsity estimation algorithms such as Iterative Hard Thresholding (IHT).
BibTeX
@inproceedings{yuan2023exponential,
  author = {Xiaotong Yuan and Ping Li},
  title = {{Exponential Generalization Bounds with Near-Optimal Rates for $L\_q$-Stable Algorithms}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=1_jtWjhSSkr},
}
Figure