Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization

Peiyuan Zhang, Jiaye Teng, Jingzhao ZhangarXiv 2023 · OpenReview

Introduction

In machine learning, a fundamental tension exists between optimization and generalization. While we aim to minimize training error, conventional wisdom warns that training for too long leads to "overfitting," where a model begins to memorize noise rather than learning underlying patterns. This phenomenon is often analyzed through the lens of algorithmic stability, particularly for gradient-based methods like Gradient Descent (GD) and Stochastic Gradient Descent (SGD).

A recent study by Peiyuan Zhang, Jiaye Teng, and Jingzhao Zhang, titled "Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization," provides a rigorous theoretical investigation into this trade-off. By establishing new lower bounds for the excess risk of GD and SGD, the authors clarify when overfitting is a physical reality and when it might be an artifact of pessimistic analysis.

The Training Horizon and Stability

The core of the investigation centers on the "training horizon"—the product of the step-size ($\eta$) and the number of iterations ($T$). In 2016, Hardt et al. demonstrated that the upper bound on generalization error for gradient methods grows with the training horizon, suggesting that longer training inherently increases the risk of overfitting. However, it remained unclear if these upper bounds were tight.

The authors set out to find the "floor"—the mathematical lower bounds—to determine if the best possible performance of these algorithms also degrades over time. If the lower bounds match the rising upper bounds, overfitting is inevitable; if they do not, the existing theories may be overly conservative.

Methodology: Constructing Hard Instances

The researchers employed a theoretical approach by constructing "hard instances"—specific mathematical loss functions and data distributions designed to challenge GD and SGD. They distinguished between two primary settings:

  1. Non-realizable SCO: Problems where inherent noise or conflict between data points exists, preventing any model from achieving zero error on all points simultaneously.
  2. Realizable SCO: Problems where an optimal solution exists that perfectly minimizes every data point (e.g., noise-free settings).

Using anti-concentration arguments and dimension-scaling techniques, they proved that in noisy settings, random fluctuations in gradients inevitably push the model away from the true optimum during extended training.

Key Results

The paper’s findings, summarized in the table below, provide a comprehensive map of generalization performance across different regimes.

Summary of upper and lower bounds for GD and SGD across different optimization settings.

1. Non-Realizable Settings

For non-realizable smooth stochastic convex optimization (SCO), the authors established a lower bound of $\Omega\left(\frac{1}{\eta T} + \frac{\eta T}{n}\right)$. This perfectly matches the existing upper bounds, confirming that in noisy environments, there is an optimal training duration. Beyond this point, the model provably overfits at a rate proportional to the training horizon divided by the sample size ($n$).

2. Realizable Settings

In the realizable case, the results are more nuanced:

  • Short Horizon ($\eta T = O(n)$): The lower bounds tightly match the upper bounds, certifying that current theories accurately describe early-stage training.
  • Long Horizon ($\eta T = \Omega(n)$): A significant gap emerges. While existing upper bounds suggest the error should eventually grow (indicating overfitting), the authors' lower bound is $\Omega\left(\frac{1}{\eta T} + \frac{1}{n}\right)$. Crucially, the $1/n$ term does not grow with $T$, suggesting that the "fast rate" of generalization might be maintained indefinitely.

The Overfitting Conjecture

Based on the gap observed in the realizable long-horizon case, the authors propose a bold conjecture: In smooth, realizable convex problems, GD and SGD do not overfit, regardless of training duration. They support this by proving the conjecture holds for one-dimensional problems and high-dimensional linear regression. This suggests that the perceived risk of overfitting in these settings may be a mathematical "ghost" rather than a reality.

Conclusion and Future Directions

This work provides the first tight lower bounds for generalization in smooth SCO, confirming that while overfitting is a fundamental reality in noisy settings, it may not be a universal law. The primary limitation remains the focus on convex problems; modern deep learning is non-convex, and extending these insights to such architectures is a critical next step. Future research will likely focus on developing more optimistic upper bound proofs that match these lower bounds, potentially vindicating long-term training in realizable scenarios.

Summary updated

Abstract

This work studies the generalization error of gradient methods. More specifically, we focus on how training steps $T$ and step-size $\eta$ might affect generalization in smooth stochastic convex optimization (SCO) problems. We first provide tight excess risk lower bounds for Gradient Descent (GD) and Stochastic Gradient Descent (SGD) under the general non-realizable smooth SCO setting, suggesting that existing stability analyses are tight in step-size and iteration dependence, and that overfitting provably happens. Next, we study the case when the loss is realizable, i.e. an optimal solution minimizes all the data points. Recent works show better rates can be attained but the improvement is reduced when training time is long. Our paper examines this observation by providing excess risk lower bounds for GD and SGD in two realizable settings: 1) $\eta T = \bigO{n}$, and (2) $\eta T = \bigOmega{n}$, where $n$ is the size of dataset. In the first case $\eta T = \bigOmega{n}$, our lower bounds tightly match and certify the respective upper bounds. However, for the case $\eta T = \bigOmega{n}$, our analysis indicates a gap between the lower and upper bounds. A conjecture is proposed that the gap can be closed by improving upper bounds, supported by analyses in two special scenarios.
BibTeX
@misc{zhang2023lower,
  author = {Peiyuan Zhang and Jiaye Teng and Jingzhao Zhang},
  title = {{Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization}},
  year = {2023},
  eprint = {2303.10758},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.10758},
}
Figure