# Improving Computational Complexity in Statistical Models with Second-Order Information

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 9 Feb 2022.

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

- [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 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)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [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)

## Abstract (arXiv)

It is known that when the statistical models are singular, i.e., the Fisher information matrix at the true parameter is degenerate, the fixed step-size gradient descent algorithm takes polynomial number of steps in terms of the sample size n to converge to a final statistical radius around the true parameter, which can be unsatisfactory for the application. To further improve that computational complexity, we consider the utilization of the second-order information in the design of optimization algorithms. Specifically, we study the normalized gradient descent (NormGD) algorithm for solving parameter estimation in parametric statistical models, which is a variant of gradient descent algorithm whose step size is scaled by the maximum eigenvalue of the Hessian matrix of the empirical loss function of statistical models. When the population loss function, i.e., the limit of the empirical loss function when n goes to infinity, is homogeneous in all directions, we demonstrate that the NormGD iterates reach a final statistical radius around the true parameter after a logarithmic number of iterations in terms of n. Therefore, for fixed dimension d, the NormGD algorithm achieves the optimal overall computational complexity O(n) to reach the final statistical radius. This computational complexity is cheaper than that of the fixed step-size gradient descent algorithm, which is of the order O(nτ) for some τ > 1, to reach the same statistical radius. We illustrate our general theory under two statistical models: generalized linear models and mixture models, and experimental results support our prediction with general theory.