# Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 34 references that are in the map.
- First posted on arXiv 1 Aug 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [Accelerating Quadratic Optimization with Reinforcement Learning](https://mlsanity.com/paper/2107.10847/) (2021)
- [Safeguarded Learned Convex Optimization](https://mlsanity.com/paper/2003.01880/) (2020)
- [Gradient methods for convex minimization: better rates under weaker conditions](https://mlsanity.com/paper/1303.4645/) (2013)
- [Accelerated Forward-Backward Optimization using Deep Learning](https://mlsanity.com/paper/2105.05210/) (2021)
- [Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods](https://mlsanity.com/paper/2312.16775/) (2023)
- [Learning to optimize with convergence guarantees using nonlinear system theory](https://mlsanity.com/paper/2403.09389/) (2024)
- [Robustness of accelerated first-order algorithms for strongly convex optimization problems](https://mlsanity.com/paper/1905.11011/) (2019)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [Convex Synthesis of Accelerated Gradient Algorithms](https://mlsanity.com/paper/2102.06520/) (2021)
- [Parametrizations of All Stable Closed-loop Responses: From Theory to Neural Network Control Design](https://mlsanity.com/paper/2412.19280/) (2024)
- [Perturbed Gradient Descent Algorithms are Small-Disturbance Input-to-State Stable](https://mlsanity.com/paper/2507.02131/) (2025)
- [The Fastest Known First-Order Method for Minimizing Twice Continuously Differentiable Smooth Strongly Convex Functions](https://mlsanity.com/paper/2506.01168/) (2025)

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

- [Deep FlexQP: Accelerated Nonlinear Programming via Deep Unfolding](https://mlsanity.com/paper/2512.01565/) (2025)
- [Learning to accelerate Krasnosel'skii-Mann fixed-point iterations with guarantees](https://mlsanity.com/paper/2601.07665/) (2026)
- [Learning Over-Relaxation Policies for ADMM with Convergence Guarantees](https://mlsanity.com/paper/2604.26932/) (2026)

## Abstract (arXiv)

The design of many classical optimization algorithms is driven by the certification of linear convergence rates over classes of optimization problems. In this paper, we consider the problem of improving the average-case performance of an algorithm over a specific distribution of problem instances. While this task can be tackled by embedding trainable components into the algorithm updates, a key challenge is to preserve worst-case guarantees across the entire problem class. For classes of composite optimization problems, we show that all linearly convergent algorithms can be parametrized in terms of a baseline linearly convergent algorithm, and a set of trainable, exponentially-decaying modifications to its update rule; crucially, this parametrization excludes all-and only-the algorithms that do not converge linearly. Our results apply to improving the average-case performance of classical algorithms such as gradient descent for nonconvex, gradient-dominated functions; Nesterov's accelerated method for smooth, strongly convex functions; and projected gradient methods for optimization over polyhedral feasible sets. We illustrate how our characterization can be used for learning to optimize with linear convergence and feasibility guarantees. Numerical results showcase benefits over classical optimizers when solving ill-conditioned systems of linear equations and running a model predictive control scheme on a linear dynamical system.