# A Generalized Version of Chung's Lemma and its Applications

arXiv: https://arxiv.org/abs/2406.05637 · HTML: https://mlsanity.com/paper/2406.05637/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 48 references that are in the map.
- First posted on arXiv 9 Jun 2024.

## Builds on (most cited first, 28 of 28)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance](https://mlsanity.com/paper/2002.05273/) (2020)
- [SMG: A Shuffling Gradient-Based Method with Momentum](https://mlsanity.com/paper/2011.11884/) (2020)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2210.01748/) (2022)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)
- [How Free is Parameter-Free Stochastic Optimization?](https://mlsanity.com/paper/2402.03126/) (2024)
- [Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods](https://mlsanity.com/paper/1311.2115/) (2013)

## Built on by (most cited first, 1 of 1)

- [Convergence Rates for Distribution Matching with Sliced Optimal Transport](https://mlsanity.com/paper/2602.10691/) (2026)

## Abstract (arXiv)

Chung's Lemma is a classical tool for establishing asymptotic convergence rates of (stochastic) optimization methods under strong convexity-type assumptions and appropriate polynomial diminishing step sizes. In this work, we develop a generalized version of Chung's Lemma, which provides a simple non-asymptotic convergence framework for a more general family of step size rules. We demonstrate broad applicability of the proposed generalized lemma by deriving tight non-asymptotic convergence rates for a large variety of stochastic methods. In particular, we obtain partially new non-asymptotic complexity results for stochastic optimization methods, such as Stochastic Gradient Descent (SGD) and Random Reshuffling (RR), under a general (θ,μ)-Polyak-Lojasiewicz (PL) condition and for various step sizes strategies, including polynomial, constant, exponential, and cosine step sizes rules. Notably, as a by-product of our analysis, we observe that exponential step sizes exhibit superior adaptivity to both landscape geometry and gradient noise; specifically, they achieve optimal convergence rates without requiring exact knowledge of the underlying landscape or separate parameter selection strategies for noisy and noise-free regimes. Our results demonstrate that the developed variant of Chung's Lemma offers a versatile, systematic, and streamlined approach to establish non-asymptotic convergence rates under general step size rules.