Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis
math.ST, cs.LG, cs.NA, math.NA, math.OC, stat.ML, stat.TH
Submitted: 2025-12-31
Updated: 2026-09-14
Comments: 37 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this work, we introduce basic inequalities for first-order iterative optimization algorithms, forming a simple yet versatile framework which connects implicit and explicit regularization.
Terminology
Abstract
In this work, we introduce basic 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.
Sources
- Transformers Learn Shortcuts to Automata
- In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
- On the Convergence of Adam and Beyond
- On Reverse Pinsker Inequalities
- Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression
Related papers
- Conformal Prediction for Dyadic Regression Under Complex Missingness
- Bentkus-type asymptotic e-values
- High-Dimensional Asymptotics of Differentially Private PCA
- KL Convergence Guarantees for Score diffusion models under minimal data assumptions
- Geometric bias in eigenspace perturbation under random heterogeneous noise
- On the Asymptotic Inadmissibility of Double Machine Learning Estimators Under Structure-Agnostic Models