Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms
Not on the map. Why?
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.
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
22 of 34 references.
References · 22
- 2014Adam: A Method for Stochastic Optimizationcited by 37,240
- 2016Learning to learn by gradient descent by gradient descentcited by 620
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
- 2023Resurrecting Recurrent Neural Networks for Long Sequencescited by 408
- 2021User-friendly introduction to PAC-Bayes boundscited by 239
- 2016Learning to Optimizecited by 195
- 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 163
- 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
- 2014Global convergence of the Heavy-ball method for convex optimizationcited by 61
- 2023Learning to Warm-Start Fixed-Point Optimization Algorithmscited by 32
- 2021Accelerating Quadratic Optimization with Reinforcement Learningcited by 30
- 2020Safeguarded Learned Convex Optimizationcited by 24
10 more
- 2013Gradient methods for convex minimization: better rates under weaker conditionscited by 23
- 2021Accelerated Forward-Backward Optimization using Deep Learningcited by 11
- 2023Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methodscited by 7
- 2024Learning to optimize with convergence guarantees using nonlinear system theorycited by 7
- 2019Robustness of accelerated first-order algorithms for strongly convex optimization problemscited by 6
- 2024Data-Driven Performance Guarantees for Classical and Learned Optimizerscited by 5
- 2021Convex Synthesis of Accelerated Gradient Algorithmscited by 4
- 2024Parametrizations of All Stable Closed-loop Responses: From Theory to Neural Network Control Designcited by 3
- 2025Perturbed Gradient Descent Algorithms are Small-Disturbance Input-to-State Stablecited by 3
- 2025The Fastest Known First-Order Method for Minimizing Twice Continuously Differentiable Smooth Strongly Convex Functionscited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 2.
3 papers.