Abstract: We consider optimizing a function smooth convex function $f$ that is the average of a set of differentiable functions $f_i$, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient $f_i'$ is bounded by a linear function of the norm of the average gradient $f'$. We show that under these assumptions the basic stochastic gradient method with a sufficiently-small constant step-size has an $O(1/k)$ convergence rate, and has a linear convergence rate if $g$ is strongly-convex.
Introduction
In the landscape of numerical optimization for machine learning, practitioners often face a fundamental trade-off between Gradient Descent (GD) and Stochastic Gradient Descent (SGD). Deterministic GD utilizes the entire dataset to compute an accurate gradient, leading to fast convergence rates—specifically linear convergence for strongly convex functions. However, the per-iteration cost is prohibitive for large-scale datasets. Conversely, SGD uses a single random sample to estimate the gradient, making it computationally cheap per step but introducing significant variance. This "noise" typically necessitates a decaying step size, which slows the convergence rate to $O(1/\sqrt{k})$ for convex problems.
This paper, a theoretical note by Mark Schmidt and Nicolas Le Roux, explores a mathematical middle ground. The authors investigate specific conditions under which SGD can maintain its low per-iteration cost while achieving the superior convergence rates of deterministic GD.
The Strong Growth Condition (SGC)
The central pillar of this analysis is the Strong Growth Condition (SGC). This condition assumes that the norm of the gradient of any individual component function $f_i$ is bounded by a constant $B$ times the norm of the average gradient $f'$. Formally:
$$\max_i \{ \|f'_i(x)\| \} \leq B \|f'(x)\|$$
This assumption implies that if the average gradient vanishes (i.e., we have reached the optimum), then the gradients of all individual functions must also vanish. While this is a restrictive assumption in many classical settings, it perfectly describes "interpolation" problems. In these scenarios, such as over-parameterized neural networks or certain non-linear least squares problems, the model is expressive enough to fit every single data point perfectly, reaching a point where the loss and gradient for every sample are zero simultaneously.
Analysis and Methodology
The authors' proof strategy relies on re-evaluating the stochastic error in the gradient estimate. In standard SGD analysis, the variance of the gradient estimate is often assumed to be bounded by a constant. This persistent noise is what prevents SGD from converging with a constant step size, as the algorithm would eventually "chatter" around the optimum.
Under the SGC, however, the variance is not constant; it is proportional to the norm of the full gradient. As the algorithm approaches the optimum and the full gradient $f'(x)$ goes to zero, the stochastic error $e_k$ also shrinks to zero. This variance reduction allows for the use of a constant step size $\alpha$. Specifically, the authors show that if $\alpha < 2 / LB^2$ (where $L$ is the Lipschitz constant), the algorithm remains stable and converges directly to the solution without the need for a diminishing learning rate.
Theoretical Results
The paper establishes two primary convergence bounds for SGD under the SGC using a constant step size:
- Strongly Convex Functions: The algorithm achieves a linear convergence rate. The expected error decreases geometrically: $E[f(x_k) - f(x^*)] \leq \rho^k [f(x_0) - f(x^*)]$ for some $\rho < 1$. This matches the rate of deterministic GD and represents a significant acceleration over the standard $O(1/k)$ rate for stochastic methods in strongly convex settings.
- General Convex Functions: The algorithm achieves an $O(1/k)$ convergence rate. This is a notable improvement over the standard $O(1/\sqrt{k})$ rate associated with stochastic methods, again matching the performance of deterministic GD.
Discussion and Limitations
While the SGC provides a powerful bridge between stochastic and deterministic optimization, it is important to note its limitations. The condition is "strong" because it does not hold in settings with high label noise or heavy regularization where a perfect fit (zero gradient for all $f_i$) is impossible.
However, the theoretical insights are highly relevant to modern deep learning. Many contemporary models are trained in the "interpolation regime," where the number of parameters exceeds the number of data points. In these cases, the SGC may approximately hold, providing a theoretical justification for why practitioners can often use large, constant, or slowly decaying step sizes to achieve rapid training results. This work ultimately provides a unified view, showing that as the growth constant $B$ approaches 1, the behavior of SGD converges to that of deterministic GD.
Summary updated