# An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 16 May 2022.

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

- [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)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [An Exponential Learning Rate Schedule for Deep Learning](https://mlsanity.com/paper/1910.07454/) (2019)
- [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)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [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)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [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)
- [Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent](https://mlsanity.com/paper/2110.07810/) (2021)

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

- [Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures](https://mlsanity.com/paper/2205.11078/) (2022)

## Abstract (arXiv)

Using gradient descent (GD) with fixed or decaying step-size is a standard practice in unconstrained optimization problems. However, when the loss function is only locally convex, such a step-size schedule artificially slows GD down as it cannot explore the flat curvature of the loss function. To overcome that issue, we propose to exponentially increase the step-size of the GD algorithm. Under homogeneous assumptions on the loss function, we demonstrate that the iterates of the proposed exponential step size gradient descent (EGD) algorithm converge linearly to the optimal solution. Leveraging that optimization insight, we then consider using the EGD algorithm for solving parameter estimation under both regular and non-regular statistical models whose loss function becomes locally convex when the sample size goes to infinity. We demonstrate that the EGD iterates reach the final statistical radius within the true parameter after a logarithmic number of iterations, which is in stark contrast to a polynomial number of iterations of the GD algorithm in non-regular statistical models. Therefore, the total computational complexity of the EGD algorithm is optimal and exponentially cheaper than that of the GD for solving parameter estimation in non-regular statistical models while being comparable to that of the GD in regular statistical settings. To the best of our knowledge, it resolves a long-standing gap between statistical and algorithmic computational complexities of parameter estimation in non-regular statistical models. Finally, we provide targeted applications of the general theory to several classes of statistical models, including generalized linear models with polynomial link functions and location Gaussian mixture models.