A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance

Xiaoyu Li, Zhenxun Zhuang, Francesco OrabonaICML 2021 · OpenReview

TL;DR

While deep learning practitioners have long favored exponential and cosine learning rate schedules for their empirical success, theoretical justification has been surprisingly thin. This paper provides the first convergence proofs for these schedules in non-convex settings and reveals a "hidden superpower": they automatically adapt to gradient noise, matching or beating complex, finely-tuned schedules with significantly less manual effort.

What Problem Does This Paper Address?

In the world of Stochastic Gradient Descent (SGD), the "step size" (or learning rate) is everything. If it's too large, the model overshoots; if it's too small, training takes forever. Most theoretical "adaptive" methods (like Adam or AdaGrad) focus on adapting to the geometry of the loss landscape. However, there is another critical factor: noise.

Standard theory suggests that if you have a "noise-free" environment, you should use a constant step size to converge quickly. If you have "noise" (common in mini-batch training), you need a decaying step size to settle into a minimum. Usually, a researcher has to know the noise level beforehand to choose the right polynomial decay. The authors tackle a major gap: proving that the popular Exponential and Cosine schedules are "noise-blind"—they work optimally in both noisy and noise-free scenarios without needing to tune hyperparameters based on the noise level.

Methods

The authors provide a rigorous mathematical analysis of two specific schedules:

  1. Exponential Step Size: $\eta_t = \eta_0 \cdot \alpha^t$
  2. Cosine Step Size: $\eta_t = \frac{\eta_0}{2} (1 + \cos(\frac{t\pi}{T}))$

They analyze these under the Polyak-Łojasiewicz (PL) condition, a mathematical property that is weaker than convexity but often holds locally in deep neural networks. They also provide "worst-case" analyses for general smooth non-convex functions where the PL condition might not hold.

The novelty lies in the proof technique, which demonstrates that these schedules behave like a constant step size early in training (making rapid progress) and then decay rapidly enough at the end to "quench" the noise, effectively mimicking the best of both worlds.

Datasets

The authors validated their theory using standard deep learning benchmarks to ensure the math translates to reality:

  • FashionMNIST: Using a standard Convolutional Neural Network (CNN).
  • CIFAR-10: Using a 20-layer Residual Network (ResNet-20).
  • CIFAR-100: Using a 100-layer DenseNet-BC.
  • NLP Task: The appendix includes experiments on Natural Language Processing tasks where these schedules were compared against Adam.

Key Insights and Ideas

  • The "Universal" Property: The most striking finding is that these schedules are "adaptive to noise." In the past, you might have needed one strategy for a large-batch (low noise) setup and another for a small-batch (high noise) setup. Exponential and Cosine schedules handle both automatically.
  • Mathematical Convergence: This is the first time these specific, widely-used schedules have been proven to converge for smooth non-convex functions.
  • Hidden Similarities: Despite looking very different on a graph, the proofs reveal that both schedules share a similar underlying "decay profile" that is key to their success.
  • Hyperparameter Efficiency: The authors argue that "simplicity is a feature." While "stagewise decay" (dropping the learning rate at specific milestones) is popular, it requires tuning when to drop and how much to drop. Cosine requires only one hyperparameter ($\eta_0$), and Exponential requires two ($\eta_0$ and $\alpha$).
Comparison with Stagewise Decay and Plateau

Key Results

  • Theoretical Rates: Under the PL condition, the exponential schedule recovers an almost optimal $O(1/T)$ convergence rate in noisy settings, while maintaining a linear (fast) rate in noise-free settings.
  • Empirical Dominance: In head-to-head tests, Cosine and Exponential schedules consistently matched or outperformed more complex methods like Adam, SGD with Armijo line search, and ReduceLROnPlateau.
  • Robustness: The experiments showed that even with minimal tuning, these two simple schedules could match the performance of "finely-tuned" state-of-the-art strategies that require significantly more human time to optimize.
Comparison with Adam and Armijo

Limitations and Future Work

  • PL Condition Dependency: Much of the "magic" of the noise adaptivity is proven under the PL condition. While the authors cite evidence that this holds locally in neural networks, it isn't a universal property of all non-convex functions.
  • High Probability Bounds: The current proofs focus on "expected" convergence (the average behavior). The authors suggest that future work should look into "high probability" bounds to guarantee performance in every single run.
  • Optimal Rates: While the rates are "almost optimal," there is still a small poly-logarithmic gap between these results and the theoretical lower bounds for non-convex optimization that could be tightened.

Summary updated

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 size...
BibTeX
@inproceedings{li2021second,
  author = {Xiaoyu Li and Zhenxun Zhuang and Francesco Orabona},
  title = {{A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=NqcZCKESPGe},
}
Figure