# Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 15 references that are in the map.
- First posted on arXiv 20 Jun 2022.

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

- [Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning](https://mlsanity.com/paper/1810.01075/) (2018)
- [Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis](https://mlsanity.com/paper/2006.04299/) (2020)
- [Universal Average-Case Optimality of Polyak Momentum](https://mlsanity.com/paper/2002.04664/) (2020)

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

- [The Curse of Unrolling: Rate of Differentiating Through Optimization](https://mlsanity.com/paper/2209.13271/) (2022)
- [FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity](https://mlsanity.com/paper/2404.09816/) (2024)
- [Insights on Muon from Simple Quadratics](https://mlsanity.com/paper/2602.11948/) (2026)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Polynomial Preconditioning for Gradient Methods](https://mlsanity.com/paper/2301.13194/) (2023)
- [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)

The recently developed average-case analysis of optimization methods allows a more fine-grained and representative convergence analysis than usual worst-case results. In exchange, this analysis requires a more precise hypothesis over the data generating process, namely assuming knowledge of the expected spectral distribution (ESD) of the random matrix associated with the problem. This work shows that the concentration of eigenvalues near the edges of the ESD determines a problem's asymptotic average complexity. This a priori information on this concentration is a more grounded assumption than complete knowledge of the ESD. This approximate concentration is effectively a middle ground between the coarseness of the worst-case scenario convergence and the restrictive previous average-case analysis. We also introduce the Generalized Chebyshev method, asymptotically optimal under a hypothesis on this concentration and globally optimal when the ESD follows a Beta distribution. We compare its performance to classical optimization algorithms, such as gradient descent or Nesterov's scheme, and we show that, in the average-case context, Nesterov's method is universally nearly optimal asymptotically.