Nonlinear acceleration of momentum and primal-dual algorithms

Raghu Bollapragada, Damien Scieur, Alexandre d'AspremontMath. Program 2023 · OpenReview

Abstract

We describe convergence acceleration schemes for multistep optimization algorithms where the underlying fixed-point operator is not symmetric. In particular, our analysis handles algorithms with momentum terms such as Nesterov’s accelerated method or primal-dual methods. The acceleration technique combines previous iterates through a weighted sum, whose coefficients are computed via a simple linear system. We analyze performance in both online and offline modes, and we study in particular a variant of Nesterov’s method that uses nonlinear acceleration at each iteration. We use Crouzeix’s conjecture to show that acceleration performance is controlled by the solution of a Chebyshev problem on the numerical range of a non-symmetric operator modeling the behavior of iterates near the optimum. Numerical experiments are detailed on logistic regression problems.

Introduction

Most optimization algorithms are "forgetful," moving from one point to the next while discarding the information contained in the sequence of previous iterates. Extrapolation methods, such as Anderson Acceleration, attempt to rectify this by estimating the solution as a weighted average of the last few iterates.

However, existing theoretical guarantees for these methods have primarily applied to "single-step" algorithms where the underlying operator is symmetric, such as standard Gradient Descent. Modern high-performance algorithms, including Nesterov’s Accelerated Gradient Descent and Primal-Dual methods, are "multistep" and involve non-symmetric operators. This research fills the gap by providing the mathematical machinery to accelerate these more sophisticated, non-symmetric algorithms using Regularized Nonlinear Acceleration (RNA).

Theoretical Framework and Methods

The core of the proposed approach is Regularized Nonlinear Acceleration (RNA). Instead of simply selecting the final iterate $x_N$, RNA solves a small, inexpensive linear system to determine weights for a weighted average of the last $N$ iterates.

Non-Symmetric Analysis and Crouzeix’s Conjecture

To handle multistep methods, the authors model them as single-step iterations in a higher-dimensional space, resulting in a non-symmetric operator $G$. To bound the convergence rate of these systems, the authors leverage Crouzeix’s conjecture from matrix theory. They demonstrate that acceleration performance is governed by a Chebyshev problem defined over the numerical range—a specific set in the complex plane—of the operator.

Visualization of the Chebyshev problem over the numerical range of a non-symmetric operator, illustrating how convergence is controlled in the complex plane.

In symmetric methods, convergence is viewed as a line on the real axis. For multistep methods, it becomes a 2D shape in the complex plane. The "wider" this numerical range, the more challenging the acceleration. For Nesterov’s method, the numerical range is essentially a convex hull of ellipses; acceleration is most effective when the point $(1,0)$ in the complex plane lies outside this range.

Online RNA and Adaptive Guardrails

The authors introduce "Online RNA," which feeds accelerated points back into the optimization loop at every step rather than just post-processing a batch. To ensure stability, they propose an "Optimal Adaptive Algorithm" that checks if the accelerated step improves the objective function, ensuring performance never degrades below the original Nesterov method.

Empirical Results

The methods were evaluated on several benchmarks, including the Madelon-UCI dataset for $\ell_2$-regularized logistic regression and the Sonar dataset for visualizing Primal-Dual operators.

  • Performance vs. L-BFGS: In logistic regression experiments, Online RNA performed comparably to L-BFGS, the gold-standard quasi-Newton method.
  • Speed and Robustness: Online RNA was significantly faster than the classical Nesterov method. Crucially, it proved robust to miss-specified hyperparameters. While Nesterov’s method is highly sensitive to the strong convexity parameter $\mu$, RNA maintains performance even when $\mu$ is guessed incorrectly.
  • Efficiency: The computational overhead is minimal, as computing acceleration weights requires solving only a tiny linear system (e.g., $10 \times 10$).

Conclusion

This work extends nonlinear acceleration to a broader class of non-symmetric optimization algorithms. By mapping convergence to a geometric Chebyshev problem in the complex plane, the authors provide both theoretical bounds and a practical, robust acceleration scheme. Future work may focus on more rigorous treatments of stochastic iterations to handle the high variance inherent in Stochastic Gradient Descent (SGD) for multistep methods.

Summary updated

Abstract

We describe convergence acceleration schemes for multistep optimization algorithms where the underlying fixed-point operator is not symmetric. In particular, our analysis handles algorithms with momentum terms such as Nesterov’s accelerated method or primal-dual methods. The acceleration technique combines previous iterates through a weighted sum, whose coefficients are computed via a simple linear system. We analyze performance in both online and offline modes, and we study in particular a variant of Nesterov’s method that uses nonlinear acceleration at each iteration. We use Crouzeix’s conjecture to show that acceleration performance is controlled by the solution of a Chebyshev problem on the numerical range of a non-symmetric operator modeling the behavior of iterates near the optimum. Numerical experiments are detailed on logistic regression problems.
BibTeX
@inproceedings{bollapragada2023nonlinear,
  author = {Raghu Bollapragada and Damien Scieur and Alexandre d'Aspremont},
  title = {{Nonlinear acceleration of momentum and primal-dual algorithms}},
  booktitle = {Math. Program},
  year = {2023},
  url = {https://openreview.net/forum?id=WZNVN0ezXm},
}
Figure