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

Abstract:In this work, we introduce $\textit{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 $\theta_0$, with current iterate $\theta_T$, the basic inequality upper bounds $f(\theta_T) - f(z)$ for any reference point $z$ in terms of the accumulated step sizes, and the distances between $\theta_0$, $\theta_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.

Statistics Theory (math.ST); Machine Learning (cs.LG); Numerical Analysis (math.NA); Optimization and Control (math.OC); Machine Learning (stat.ML)

arXiv:2512.24999 [math.ST]

(or arXiv:2512.24999v2 [math.ST] for this version)

https://doi.org/10.48550/arXiv.2512.24999 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.