# Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis

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

## Key facts

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

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

- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)
- [The Curse of Unrolling: Rate of Differentiating Through Optimization](https://mlsanity.com/paper/2209.13271/) (2022)
- [Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks](https://mlsanity.com/paper/2201.04753/) (2022)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization](https://mlsanity.com/paper/2403.07264/) (2024)
- [Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime](https://mlsanity.com/paper/2206.09901/) (2022)
- [High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance](https://mlsanity.com/paper/2304.00707/) (2023)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [Random Matrix Theory for Deep Learning: Beyond Eigenvalues of Linear Models](https://mlsanity.com/paper/2506.13139/) (2025)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [Random Function Descent](https://mlsanity.com/paper/2305.01377/) (2023)
- [Distribution-Aware Algorithm Design with LLM Agents](https://mlsanity.com/paper/2605.14141/) (2026)

## Abstract (arXiv)

Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model. However, we show that this is not the case for a class of large-scale problems trained with first-order methods including random least squares and one-hidden layer neural networks with random weights. In fact, the halting time exhibits a universality property: it is independent of the probability distribution. With this barrier for average-case analysis removed, we provide the first explicit average-case convergence rates showing a tighter complexity not captured by traditional worst-case analysis. Finally, numerical simulations suggest this universality property holds for a more general class of algorithms and problems.