Learning to Tune ADMM: Adaptive Relaxation with Convergence Guarantees

Paper: 2604.26932 Authors: Junan Lin, Paul J. Goulart, Luca Furieri Categories: math.OC, cs.LG

The Gap

ADMM is the workhorse for structured convex optimization, but its performance hinges on two knobs: penalty parameter ρ and relaxation parameter α. Practitioners know this. The problem: tuning ρ requires expensive matrix refactorizations in solvers like OSQP, while α is cheap to update but lacks principled tuning methods. Prior work focused on learning ρ schedules, accepting the computational cost. In settings like Model Predictive Control, where you solve thousands of similar problems in sequence, this cost compounds.

The gap: no one had shown how to learn α policies with convergence guarantees, nor demonstrated that learned α schedules could outperform fixed choices without sacrificing theoretical safety.

Problem: ADMM performance depends on (ρ, α) tuning
         |
         +---> Prior work: Learn ρ schedules
         |     Limitation: Expensive refactorizations
         |
         +---> This paper: Learn α schedules
               Assumption: Time-varying (ρ, α) can converge
               Method: Policy learning + theoretical analysis
               Evidence: Faster convergence on QP benchmarks
               Conclusion: α-tuning is computationally cheaper
                          and theoretically sound

The Increment

One sentence: Before this paper, ADMM parameter tuning meant choosing between expensive ρ updates or unprincipled α heuristics; after, you can learn α policies that provably converge and run faster.

Core Mechanism

The method has three components. First, a convergence analysis that extends classical ADMM theory to handle time-varying penalty and relaxation parameters under mild assumptions (bounded parameter sequences, sufficient penalty magnitude). This establishes the theoretical foundation.

Second, a policy learning framework that treats α selection as a sequential decision problem. At each iteration, a policy network observes problem state (primal/dual residuals, iterates) and outputs the next α value. The policy is trained offline on a distribution of related problems, then deployed online.

Third, an implementation strategy that exploits OSQP’s architecture. Since α updates don’t trigger matrix refactorizations (unlike ρ updates), the learned policy can adapt at every iteration with minimal overhead. The policy is trained via supervised learning on expert trajectories or reinforcement learning with convergence speed as reward.

Problem instance (QP parameters)
         |
         v
    [ADMM Solver]
         |
    +----+----+
    |         |
    v         v
Primal    Dual       <--- State observation
residual  residual        at iteration k
    |         |
    +----+----+
         |
         v
  [Policy Network]
         |
         v
    α(k+1)  <--- Relaxation parameter
         |
         v
  [ADMM Update] (no refactorization needed)
         |
         v
    x(k+1), z(k+1), y(k+1)

Think of ADMM as a car navigating to a destination (the optimal solution). The penalty parameter ρ is like the car’s suspension stiffness—changing it requires pulling over and swapping parts (matrix refactorization). The relaxation parameter α is like the steering wheel angle—you can adjust it continuously while driving. Classical ADMM uses cruise control with fixed steering. This paper learns a driving policy that adjusts the steering based on road conditions (residuals), getting you there faster without stopping to change parts. The convergence proof is the safety certification that this adaptive steering won’t cause crashes.

Key Concepts

• Over-relaxation in ADMM: Standard ADMM alternates between updating primal variable x, auxiliary variable z, and dual variable y. Over-relaxation means using a weighted combination of the new and old z values when updating y, controlled by parameter α. When α = 1, you get standard ADMM. When α > 1, you “overshoot” the update, which can accelerate convergence if chosen well but destabilize if chosen poorly. Imagine pushing a swing: α = 1 is pushing at the natural frequency, α > 1 is pushing harder to build amplitude faster, but push too hard (α too large) and you disrupt the rhythm. The trick is knowing when to push hard and when to ease off.

• Time-varying convergence analysis: Classical convergence proofs assume fixed parameters. Allowing parameters to change at every iteration breaks standard proof techniques because the contraction properties change over time. This paper shows convergence still holds if: (1) parameters stay within reasonable bounds, (2) the penalty stays large enough to maintain strong convexity, and (3) the relaxation doesn’t oscillate wildly. It’s like proving a car reaches its destination even if the driver adjusts steering continuously, by showing the adjustments are bounded and the car maintains forward progress.

• Policy learning for optimization: Instead of hand-tuning α or using fixed schedules, train a neural network to map problem state to α values. The policy sees residuals (how far from optimality) and iterates (current position), then outputs α. Training uses either imitation learning (copy expert trajectories from grid search) or reinforcement learning (reward faster convergence). The key insight: in MPC and similar settings, you solve many structurally similar problems, so a policy learned on past problems generalizes to future ones.

Framework Shift

Before (fixed parameters):           After (learned policy):

Problem --> [ADMM with              Problem --> [ADMM with
            fixed ρ, α]                         learned α(k)]
                |                                    |
                v                                    v
         Slow convergence                    Fast convergence
         or manual tuning                    + convergence proof
                                                     ^
                                                     |
                                            [Policy trained on
                                             problem family]

From static parameter selection to adaptive policies, the core shift is treating parameter tuning as a learning problem over problem distributions rather than a per-instance optimization.

Expert Assessment

Problem choice: Real gap. MPC practitioners solve thousands of QPs per second with the same structure. Shaving iterations matters. The focus on α over ρ is clever—it exploits a computational asymmetry in existing solvers that others overlooked.

Method maturity: The convergence analysis is solid but not groundbreaking—it extends known results to time-varying parameters under reasonable assumptions. The policy learning is straightforward supervised/RL. The real contribution is showing these pieces fit together: you can learn α policies that work in practice and still converge in theory. No major algorithmic innovation, but good engineering insight.

Experimental integrity: Baselines are fair (OSQP with default and tuned fixed parameters). The benchmarks are standard QP test problems. Numbers show consistent improvement in iteration count and wall-clock time. One concern: the policy is trained and tested on similar problem distributions. Generalization to out-of-distribution problems is not thoroughly explored. The paper is honest about this limitation.

Writing quality: The convergence proof section is dense and could use more intuition before diving into technical conditions. The experimental section is clear. The related work undersells how much prior work exists on adaptive ADMM parameters—it focuses narrowly on learning-based methods and misses classical adaptive schemes. Rewriting Section 2 to better motivate why time-varying parameters are hard to analyze would strengthen the paper.

Verdict: weak accept — Solid incremental contribution with practical value, but limited novelty in individual components. The combination is useful and the convergence guarantees are non-trivial, but this won’t change how people think about optimization.

Takeaways

If you’re building a solver for repeated structured problems (MPC, online learning, real-time control), consider learning parameter schedules for cheap-to-update knobs. The pattern generalizes: identify which parameters are expensive to change (trigger refactorizations, recompilations) and which are cheap, then focus learning on the cheap ones. The convergence analysis technique—showing time-varying parameters converge under boundedness and sufficient regularization—is a template for analyzing other adaptive algorithms. For practitioners: if your solver has a relaxation parameter, try learning a simple policy (even a lookup table based on residual ratios) before investing in more complex tuning.