# Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 52 references that are in the map.
- First posted on arXiv 31 Dec 2025.

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

- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [A Continuous-Time View of Early Stopping for Least Squares](https://mlsanity.com/paper/1810.10082/) (2018)
- [The Implicit Regularization of Stochastic Gradient Flow for Least Squares](https://mlsanity.com/paper/2003.07802/) (2020)
- [Gradient descent follows the regularization path for general losses](https://mlsanity.com/paper/2006.11226/) (2020)
- [Margins, Shrinkage, and Boosting](https://mlsanity.com/paper/1303.4172/) (2013)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [Early stopping for kernel boosting algorithms: A general analysis with localized complexities](https://mlsanity.com/paper/1707.01543/) (2017)
- [A Unified Approach to Controlling Implicit Regularization via Mirror Descent](https://mlsanity.com/paper/2306.13853/) (2023)
- [On Regularization via Early Stopping for Least Squares Regression](https://mlsanity.com/paper/2406.04425/) (2024)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)

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

- [Separating Geometry from Probability in the Analysis of Generalization](https://mlsanity.com/paper/2604.19560/) (2026)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)

## Abstract (arXiv)

In this work, we introduce textitbasic inequalities for first-order iterative optimization algorithms, forming a simple yet versatile framework which connects implicit and explicit regularization. Building on related comparison inequalities for optimization iterates that already exist in the literature, we extend and unify these arguments to produce a general framework, which can be used as a tool for statistical analysis. In more detail, let f denote the objective function to be optimized. Given a first-order iterative algorithm initialized at θ0, with current iterate θT, the basic inequality upper bounds f(θT) - f(z) for any reference point z in terms of the accumulated step sizes, and the distances between θ0, θT, and z. These distances are measured in a geometry inherent to the optimization algorithm, which then translates into a notion of regularization being applied across the path of iterates. In addition to refining existing results on gradient descent, we provide new results for mirror descent and other first-order methods. We then show how to use these basic inequalities to derive elementary yet useful bounds on the prediction risk of early-stopped gradient descent and exponentiated gradient descent iterates in generalized linear models. We also supplement these findings with numerical experiments.