# A Study of Condition Numbers for First-Order Optimization

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

## Key facts

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

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

- [Activated Gradients for Deep Neural Networks](https://mlsanity.com/paper/2107.04228/) (2021)
- [An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games](https://mlsanity.com/paper/2211.01280/) (2022)
- [On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Acceleration](https://mlsanity.com/paper/2209.14827/) (2022)
- [Understanding Adam Requires Better Rotation Dependent Assumptions](https://mlsanity.com/paper/2410.19964/) (2024)
- [Model Immunization from a Condition Number Perspective](https://mlsanity.com/paper/2505.23760/) (2025)
- [No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths](https://mlsanity.com/paper/2306.11922/) (2023)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Solving Hidden Monotone Variational Inequalities with Surrogate Losses](https://mlsanity.com/paper/2411.05228/) (2024)
- [Convergence Properties of Natural Gradient Descent for Minimizing KL Divergence](https://mlsanity.com/paper/2504.19259/) (2025)

## Abstract (arXiv)

The study of first-order optimization algorithms (FOA) typically starts with assumptions on the objective functions, most commonly smoothness and strong convexity. These metrics are used to tune the hyperparameters of FOA. We introduce a class of perturbations quantified via a new norm, called *-norm. We show that adding a small perturbation to the objective function has an equivalently small impact on the behavior of any FOA, which suggests that it should have a minor impact on the tuning of the algorithm. However, we show that smoothness and strong convexity can be heavily impacted by arbitrarily small perturbations, leading to excessively conservative tunings and convergence issues. In view of these observations, we propose a notion of continuity of the metrics, which is essential for a robust tuning strategy. Since smoothness and strong convexity are not continuous, we propose a comprehensive study of existing alternative metrics which we prove to be continuous. We describe their mutual relations and provide their guaranteed convergence rates for the Gradient Descent algorithm accordingly tuned. Finally we discuss how our work impacts the theoretical understanding of FOA and their performances.