# Instability, Computational Efficiency and Statistical Accuracy

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2020.

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

- [Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Experts](https://mlsanity.com/paper/2309.13850/) (2023)
- [Counterfactual inference in sequential experiments](https://mlsanity.com/paper/2202.06891/) (2022)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [Generalization in Supervised Learning Through Riemannian Contraction](https://mlsanity.com/paper/2201.06656/) (2022)
- [Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent](https://mlsanity.com/paper/2110.07810/) (2021)
- [Network Gradient Descent Algorithm for Decentralized Federated Learning](https://mlsanity.com/paper/2205.08364/) (2022)
- [Dataset Distillation from First Principles: Integrating Core Information Extraction and Purposeful Learning](https://mlsanity.com/paper/2409.01410/) (2024)
- [Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures](https://mlsanity.com/paper/2205.11078/) (2022)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [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)
- [Generalization as a robust performance property of learning-enabled dynamical systems](https://mlsanity.com/paper/2608.30431/) (2026)

## Abstract (arXiv)

Many statistical estimators are defined as the fixed point of a data-dependent operator, with estimators based on minimizing a cost function being an important special case. The limiting performance of such estimators depends on the properties of the population-level operator in the idealized limit of infinitely many samples. We develop a general framework that yields bounds on statistical accuracy based on the interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (in)stability when applied to an empirical object based on n samples. Using this framework, we analyze both stable forms of gradient descent and some higher-order and unstable algorithms, including Newton's method and its cubic-regularized variant, as well as the EM algorithm. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models. We exhibit cases in which an unstable algorithm can achieve the same statistical accuracy as a stable algorithm in exponentially fewer steps -- namely, with the number of iterations being reduced from polynomial to logarithmic in sample size n.