Sharper Generalization Bounds for Learning with Gradient-dominated Objective Functions

Yunwen Lei, Yiming YingICLR 2021 · OpenReview

Introduction

In classical learning theory, there is a perceived tension between optimization and generalization: training a model "too much" to minimize training error is often thought to cause overfitting and poor performance on new data. However, modern deep learning models frequently interpolate the training data—achieving zero training error—yet still generalize remarkably well.

Existing theoretical tools, such as algorithmic stability, have struggled to explain this phenomenon for non-convex problems. Previous bounds often required unrealistic assumptions, like "bounded gradients" (assuming the function never gets too steep) or "uniform Lipschitz constants," which do not hold for complex models like Deep Neural Networks (DNNs). Furthermore, many existing bounds suggested a "slow" generalization rate of $O(1/\sqrt{n})$, failing to capture the efficiency of modern algorithms.

This paper provides a new theoretical framework for understanding why these models generalize well. By focusing on "gradient-dominated" functions and leveraging a weaker form of algorithmic stability, the authors derive significantly tighter generalization bounds—$O(1/n)$ instead of the traditional $O(1/\sqrt{n})$—and prove that better optimization can actually lead to better generalization.

Theoretical Framework and Methods

The authors tackle the limitations of previous bounds by focusing on objective functions that satisfy the Polyak-Lojasiewicz (PL) condition (also known as gradient-dominance). In simple terms, a PL function ensures that the gradient grows as you move away from the global minimum, even if the function itself is not convex.

Key methodological shifts in this work include:

  • On-Average Stability: Instead of using "uniform stability," which looks at the worst-case change when swapping a single data point, the authors utilize "on-average stability." This is a more relaxed measure that is easier to satisfy in practice.
  • Exploiting Smoothness: Rather than assuming gradients are bounded by a constant, they use the smoothness (L-continuity of the gradient) of the loss function. This allows the gradient to grow naturally, making the theory applicable to a wider range of real-world models.
  • Implicit Regularization: The analysis shows that the PL condition itself acts as a form of implicit regularization, preventing the model from becoming "too unstable" even as the training error approaches zero.

Key Insights: Optimization, Interpolation, and Variance Reduction

A central takeaway from this research is that optimization is a friend to generalization. For gradient-dominated functions, the generalization error is bounded by $O(1/n\beta)$ plus the optimization error. This implies that as the optimization algorithm finds a better solution, the generalization bound inherently improves.

Furthermore, the authors prove the power of the interpolation setting. When a model can achieve zero training error, the generalization error can decay exponentially. This provides a strong theoretical justification for why highly expressive, over-parameterized models that fit data perfectly are often the best performers.

By removing the "bounded gradient" crutch, the theory becomes much more robust for practical applications, such as least squares regression in unbounded domains or deep networks where gradients can naturally become large.

Results & Algorithmic Comparisons

The paper achieves an excess generalization error bound of $O(1/n\beta)$, representing a "fast rate" compared to the $O(1/\sqrt{n})$ found in previous stability literature for non-convex settings. For Stochastic Gradient Descent (SGD) in the interpolation setting, they derived a linear convergence rate for the testing error, matching the known fast convergence of training error in those scenarios.

Additionally, the paper demonstrates that variance-reduction techniques (like SARAH or SpiderBoost), which are traditionally known to speed up training, also directly improve the generalization rate compared to standard SGD.

Iteration complexity of various algorithms to achieve specific generalization targets.

Empirical Validation

While the paper is primarily theoretical, it includes simulations to validate the findings. The authors used the IJCNN1 benchmark dataset for binary classification and synthetic Generalized Linear Models to verify the behavior of gradient-dominated functions. These tests confirmed the lack of overfitting during extended SGD training, aligning with their theoretical bounds.

Limitations and Future Work

Despite these advances, the framework has limitations. While many neural networks behave like PL functions in certain regions, not all non-convex problems satisfy this condition globally. Additionally, the main results are stated in terms of expected error. While extensions to high-probability bounds are possible, they typically reintroduce an additional $O(1/\sqrt{n})$ term.

Future work will likely focus on extending this stability-based analysis to even more general non-convex functions that may not satisfy the PL condition, potentially by examining local geometries or different types of "relaxed" convexity.

Summary updated

Abstract

Stochastic optimization has become the workhorse behind many successful machine learning applications, which motivates a lot of theoretical analysis to understand its empirical behavior. As a comparison, there is far less work to study the generalization behavior especially in a non-convex learning setting. In this paper, we study the generalization behavior of stochastic optimization by leveraging the algorithmic stability for learning with $\beta$-gradient-dominated objective functions. We develop generalization bounds of the order $O(1/(n\beta))$ plus the convergence rate of the optimization algorithm, where $n$ is the sample size. Our stability analysis significantly improves the existing non-convex analysis by removing the bounded gradient assumption and implying better generalization bounds. We achieve this improvement by exploiting the smoothness of loss functions instead of the Lipschitz condition in Charles & Papailiopoulos (2018). We apply our general results to various stochastic optimization algorithms, which show clearly how the variance-reduction techniques improve not only training but also generalization. Furthermore, our discussion explains how interpolation helps generalization for highly expressive models.
BibTeX
@inproceedings{lei2021sharper,
  author = {Yunwen Lei and Yiming Ying},
  title = {{Sharper Generalization Bounds for Learning with Gradient-dominated Objective Functions}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=r28GdiQF7vM},
}
Figure