Abstract
Stochastic Gradient Descent (SGD) is a popular tool in training large-scale machine learning models. Its performance, however, is highly variable, depending crucially on the choice of the step sizes. Accordingly, a variety of strategies for tuning the step sizes have been proposed, ranging from coordinate-wise approaches (a.k.a. "adaptive" step sizes) to sophisticated heuristics to change the step size in each iteration. In this paper, we study two step size schedules whose power has been repeatedly confirmed in practice: the exponential and the cosine step sizes. For the first time, we provide theoretical support for them proving convergence rates for smooth non-convex functions, with and without the Polyak-\L{}ojasiewicz (PL) condition. Moreover, we show the surprising property that these two strategies are adaptive to the noise level in the stochastic gradients of PL functions. That is, contrary to polynomial step sizes, they achieve almost optimal performance without needing to know the noise level nor tuning their hyperparameters based on it. Finally, we conduct a fair and comprehensive empirical evaluation of real-world datasets with deep learning architectures. Results show that, even if only requiring at most two hyperparameters to tune, these two strategies best or match the performance of various finely-tuned state-of-the-art strategies.
Introduction
Stochastic Gradient Descent (SGD) is the engine behind modern machine learning, but its success depends entirely on the learning rate (step size). Tuning this parameter is often considered a "black art." While theorists often recommend polynomial decay (like $1/\sqrt{t}$ or $1/t$), practitioners have long preferred heuristics like exponential decay or cosine annealing because they seem to work better in the real world.
However, until now, there was a significant gap: we lacked a solid theoretical explanation for why these specific schedules were so effective in non-convex landscapes, nor did we understand their "adaptivity"—their ability to perform well across different noise levels without re-tuning. This paper bridges that gap by providing the first theoretical convergence guarantees for these popular schedules.
Theoretical Framework and Adaptivity
The authors provide a rigorous mathematical analysis of two specific schedules:
- Exponential Step Size: $\eta_t = \eta_0 \cdot \alpha^t$
- Cosine Step Size: $\eta_t = \frac{\eta_0}{2} (1 + \cos(\frac{t\pi}{T}))$
These are analyzed under the Polyak-Łojasiewicz (PL) condition, a property weaker than convexity that often holds locally in deep learning landscapes. The analysis reveals that these schedules are "universal": in a noise-free environment, they achieve fast linear convergence, while in the presence of noise, they automatically transition to the optimal $O(1/T)$ rate without requiring hyperparameter adjustments based on the noise level.
Empirical Evaluation
The theory was validated using a mix of synthetic and real-world benchmarks, including FashionMNIST (CNN), CIFAR-10 (ResNet-20), CIFAR-100 (DenseNet-BC), and the Stanford Natural Language Inference (SNLI) dataset (Bi-LSTM).
As shown in Figure 1, the Exponential and Cosine schedules consistently match or outperform standard theoretical schedules ($O(1/\sqrt{t})$, $O(1/t)$) and the popular Adam optimizer across various vision tasks. While they look different, both schedules share a critical trait: they stay relatively large at the beginning to capture rapid progress and then decay sharply at the end to "squelch" the noise as the model nears an optimum.
Key Results
One of the most significant findings is the hyperparameter efficiency of these methods. Cosine decay requires only one hyperparameter ($\eta_0$), and exponential requires two ($\eta_0$ and $\alpha$). This is significantly simpler than "stagewise decay," which requires choosing multiple milestones and decay factors.
In head-to-head tests (Figure 2), Cosine and Exponential schedules consistently matched or outperformed ReduceLROnPlateau and Stagewise Decay. Notably, on CIFAR-100 with DenseNet, the Cosine schedule achieved the highest test accuracy (74.97%) and lowest training loss. Furthermore, on the SNLI task, these simple SGD schedules even outperformed Adam, which is typically the de-facto choice for natural language processing.
Conclusion
This work provides much-needed theoretical grounding for exponential and cosine step sizes, proving they are not just heuristics but mathematically sound, adaptive strategies. While future work could explore "horizon-free" versions of the cosine schedule or high-probability convergence bounds, these results suggest that simple, well-chosen schedules can often outperform more complex, finely-tuned state-of-the-art strategies.
Summary updated