# Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 40 references that are in the map.
- First posted on arXiv 15 Oct 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression](https://mlsanity.com/paper/2006.02601/) (2020)
- [Sharp Analysis of Expectation-Maximization for Weakly Identifiable Models](https://mlsanity.com/paper/1902.00194/) (2019)
- [Regularized EM Algorithms: A Unified Framework and Statistical Guarantees](https://mlsanity.com/paper/1511.08551/) (2015)
- [Instability, Computational Efficiency and Statistical Accuracy](https://mlsanity.com/paper/2005.11411/) (2020)
- [Statistical and Computational Guarantees for the Baum-Welch Algorithm](https://mlsanity.com/paper/1512.08269/) (2015)

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

- [Network Gradient Descent Algorithm for Decentralized Federated Learning](https://mlsanity.com/paper/2205.08364/) (2022)
- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)
- [An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models](https://mlsanity.com/paper/2205.07999/) (2022)
- [Improving Computational Complexity in Statistical Models with Second-Order Information](https://mlsanity.com/paper/2202.04219/) (2022)
- [Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation](https://mlsanity.com/paper/2511.18167/) (2025)

## Abstract (arXiv)

We study the statistical and computational complexities of the Polyak step size gradient descent algorithm under generalized smoothness and Lojasiewicz conditions of the population loss function, namely, the limit of the empirical loss function when the sample size goes to infinity, and the stability between the gradients of the empirical and population loss functions, namely, the polynomial growth on the concentration bound between the gradients of sample and population loss functions. We demonstrate that the Polyak step size gradient descent iterates reach a final statistical radius of convergence around the true parameter after logarithmic number of iterations in terms of the sample size. It is computationally cheaper than the polynomial number of iterations on the sample size of the fixed-step size gradient descent algorithm to reach the same final statistical radius when the population loss function is not locally strongly convex. Finally, we illustrate our general theory under three statistical examples: generalized linear model, mixture model, and mixed linear regression model.