⚡ electrical engineering

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

This paper presents a complete characterization of all linearly convergent algorithms for composite optimization problems by parametrizing them as baseline methods with trainable, exponentially-decaying modifications, thereby enabling the improvement of average-case performance while strictly preserving worst-case convergence and feasibility guarantees.

Original authors: Andrea Martin, Ian R. Manchester, Luca Furieri

Published 2026-06-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Andrea Martin, Ian R. Manchester, Luca Furieri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley. This is what computers do when they solve complex optimization problems: they try to find the "best" answer (the bottom of the valley) as quickly as possible.

For decades, mathematicians have designed "rules" (algorithms) to help computers do this. The most famous rules, like Gradient Descent or Nesterov's Accelerated Method, come with a safety guarantee: "No matter how tricky the valley is, we will definitely reach the bottom within a certain number of steps." This is the worst-case guarantee. It's like a hiker saying, "Even if I get lost in the worst possible storm, I will still find the exit by noon."

However, in the real world, most valleys aren't the worst-case scenario. They are usually easier. The problem is that the "safe" rules are often too cautious. They take a slow, steady path to ensure they never get lost, even though a faster, more direct path might exist for this specific valley.

The Big Idea: Learning to Run Faster Without Getting Lost

This paper asks a simple question: Can we teach a computer to take a shortcut for specific types of valleys, without losing the safety guarantee that it will eventually reach the bottom?

The authors say yes, and they provide a complete "recipe" for how to do it.

The Analogy: The Train and the Booster

Think of the standard, safe algorithm as a train moving on a track. It moves at a steady, predictable speed. It will always get to the destination, but it might be slow.

The authors propose adding a booster (a learnable component) to this train.

The Booster: This is a small, temporary push that helps the train speed up or change direction slightly to take a shortcut.
The Catch: If you push too hard or push for too long, the train might derail (diverge) or crash.
The Solution: The paper proves that if you make the booster fade away exponentially (like a rocket booster that burns out quickly), you can speed up the train significantly without ever risking a derailment.

The Two Main Discoveries

The paper makes two massive claims, which they call a "complete characterization":

The "How-To" Rule: They found a mathematical rule that tells you exactly how strong and how often you can apply these "boosters." As long as the booster gets weaker fast enough (exponentially decaying), the train is guaranteed to stay on track and reach the destination at the same speed as the original train, just with a slightly different path.
The "Everything" Rule: They proved that any algorithm that is guaranteed to reach the bottom quickly can be described as:
- The original safe train PLUS a fading booster.
- This means if you want to design a new, faster algorithm, you don't need to invent a new engine from scratch. You just need to learn the perfect "fading booster" to add to an existing safe engine.

What They Tested It On

The authors didn't just do math; they tested this on real-world problems to see if the "learned boosters" actually worked.

Solving Messy Equations: They tried to solve systems of linear equations (like balancing a complex budget) where the numbers are very sensitive (ill-conditioned).
- Result: Their "learned" algorithm started by moving in a direction that seemed counter-intuitive (increasing the error slightly) to build up momentum, then zoomed past the standard methods. It reached the answer much faster.
- Safety Check: When they tried to learn a booster without the "fading" rule, the algorithm went crazy and crashed. The safety guarantee was essential for the training to work.
Controlling a Robot (Model Predictive Control): They applied this to a system that controls a moving object (like a drone or car) in real-time. The computer has to solve an optimization problem every split-second to decide where to steer.
- Result: The learned algorithm found better control strategies much faster than the standard "safe" method. This meant the robot could react more smoothly and efficiently, even with limited computing time.

The Bottom Line

This paper provides a blueprint for "Learning to Optimize."

It tells us that we can use machine learning to teach algorithms to be faster and smarter for specific tasks, but we must do it in a very specific way: by adding temporary, fading corrections to a proven, safe algorithm.

Before: You had to choose between "Safe but Slow" or "Fast but Risky."
Now: You can have "Safe and Fast" by learning the perfect, fading booster to add to your safe engine.

The paper ensures that no matter how much you "teach" the algorithm to speed up, it will never lose its promise to eventually find the solution.

Technical Summary: Learning to Optimize with Guarantees

Problem Formulation
The paper addresses the challenge of improving the average-case performance of iterative optimization algorithms over a specific distribution of problem instances, while strictly preserving their worst-case linear convergence guarantees over the entire problem class. While "Learning to Optimize" (L2O) methods often employ neural networks to design update rules, they frequently lack theoretical convergence guarantees. Conversely, classical algorithms (e.g., Gradient Descent, Nesterov's Accelerated Gradient) offer rigorous worst-case bounds but may be suboptimal for specific application distributions (e.g., Model Predictive Control where problem structures are repetitive). The authors seek a theoretical framework to parameterize all linearly convergent algorithms such that they can be augmented by learnable components without sacrificing convergence rates or feasibility.

Methodology and Theoretical Framework
The core methodology involves a complete characterization of linearly convergent algorithms for composite optimization problems of the form $\min_x f(x) + g(x)$ . The authors propose that any linearly convergent algorithm can be decomposed into two components:

A baseline algorithm ( $\pi$ ) that is known to converge linearly to a set of fixed points ( $\text{Fix}_\pi$ ) at a rate $\gamma \in (0,1)$ .
An augmentation term ( $v_t$ ) that represents a learnable, exponentially decaying perturbation to the update rule.

The update rule is defined as:
$\xi_{t+1} = \pi(F, \xi_t) + v_t(F, \xi_{t:0})$
where $\xi_t$ is the state variable and $F$ represents the objective function.

The paper establishes two primary theoretical results:

Theorem 1 (Sufficiency): It proves that injecting an exponentially decaying signal $v_t$ into a linearly convergent baseline preserves linear convergence. Specifically, if the baseline converges with rate $\gamma$ and polynomial factor $p(t)$ , the augmented algorithm converges with a potentially degraded rate determined by the frequency of non-zero perturbations ( $N$ ) and the decay rate of $v_t$ . Crucially, if the baseline is monotonically linearly convergent, the asymptotic rate $\gamma$ remains unchanged even if perturbations are applied at every step, provided $v_t$ decays exponentially.
Theorem 2 (Completeness): The authors establish a completeness result for "regular" linearly convergent algorithms. An algorithm is defined as regular if its update sequence vanishes at the same exponential rate as the distance to the fixed points. The theorem states that any regular linearly convergent algorithm $\sigma$ can be represented as the sum of a Lipschitz continuous baseline $\pi$ and an exponentially decaying augmentation $v$ . This implies that the proposed parametrization is exhaustive for the class of regular linearly convergent algorithms.

Key Contributions

Complete Characterization: The paper provides a necessary and sufficient condition for linear convergence, showing that all regular linearly convergent algorithms can be parametrized as a baseline plus an exponentially decaying modification. This excludes only pathological non-convergent or non-regular cases.
Trade-off Quantification: The work quantifies the trade-off between the frequency of learned updates and the degradation of the worst-case convergence rate. It demonstrates that one can apply learned updates at every time step without altering the asymptotic convergence rate, provided the baseline is monotonically linearly convergent.
Applicability to Diverse Classes: The characterization is instantiated for three major classes of optimization problems:
- Nonconvex, gradient-dominated functions (satisfying Restricted Secant Inequality).
- Smooth, strongly convex functions (using Nesterov's Accelerated Gradient as the baseline).
- Optimization over polyhedral feasible sets (using Projected Gradient Descent).
Learning Framework: The authors propose a meta-optimization approach where the augmentation term $v_t$ is parameterized as a neural network (specifically an LSTM) multiplied by a trainable exponentially decaying scalar sequence. This ensures the structural constraint of exponential decay is met by design, allowing for the use of PAC-Bayes generalization bounds to quantify performance on unseen instances.

Results and Numerical Validation
The paper validates the framework through two numerical experiments:

Ill-Conditioned Linear Systems: In solving $Ax=b$ where $A$ is ill-conditioned, the learned augmentation (applied to Nesterov's Accelerated Gradient) significantly improved transient performance compared to standard GD and NAG. Notably, the learned optimizer initially increased the cost function to build momentum, a behavior not present in classical optimizers. Crucially, the authors demonstrate that without the exponential decay constraint, the learned optimizer diverged when unrolled beyond the training horizon, highlighting the necessity of the theoretical guarantees for stability.
Model Predictive Control (MPC): In a linear dynamical system control task with polyhedral constraints, the learned augmentation of Projected Gradient Descent reduced the closed-loop control cost. The learned optimizer effectively learned to saturate constraints more promptly than the baseline, improving performance within tight iteration budgets typical of real-time control.

Significance and Claims
The paper claims that its characterization bridges the gap between the expressivity of learning-based methods and the reliability of classical optimization. By proving that all regular linearly convergent algorithms admit this decomposition, the authors argue that one can safely "learn" the optimal deviations from a robust baseline without risking divergence. This allows for the design of solvers tailored to specific problem distributions (improving average-case performance) while retaining the rigorous worst-case guarantees required for safety-critical applications like MPC. The work positions the augmentation of convergent algorithms as analogous to the Youla parameterization in control theory, offering a systematic path to "learning to optimize" with provable guarantees.