Nonlinear Acceleration of Primal-Dual Algorithms

Raghu Bollapragada, Damien Scieur, Alexandre d'AspremontAISTATS 2019 · OpenReview

Abstract

We describe a convergence acceleration scheme for multi-step optimization algorithms. The extrapolated solution is written as a nonlinear average of the iterates produced by the original optimization algorithm. Our scheme does not need the underlying fixed-point operator to be symmetric, hence handles e.g. algorithms with momentum terms such as Nesterov’s accelerated method, or primal-dual methods such as Chambolle-Pock. The weights are computed via a simple linear system and we analyze performance in both online and offline modes. We use Crouzeix’s conjecture to show that acceleration is controlled by the solution of a Chebyshev problem on the numerical range of a nonsymmetric operator modelling the behavior of iterates near the optimum. Numerical experiments are detailed on image processing and logistic regression problems.

Introduction

In optimization, iterative algorithms generate a sequence $x_1, x_2, \dots$ intended to converge to a solution $x^*$. While many methods only utilize the final iterate, extrapolation techniques like Anderson acceleration—or its modern variant, Regularized Nonlinear Acceleration (RNA)—aim to improve convergence by taking a weighted average of the iterate history. Historically, these techniques were best understood for symmetric operators. This paper, presented at AISTATS 2019, extends the reach of RNA to non-symmetric operators, which are characteristic of multi-step methods like Nesterov’s momentum and Primal-Dual algorithms such as Chambolle-Pock.

Theoretical Framework: Crouzeix’s Conjecture

The performance of RNA is fundamentally linked to the geometry of the iteration operator in the complex plane. The authors utilize Crouzeix’s conjecture to bound the error of the accelerated sequence. They demonstrate that the speedup is determined by how effectively a polynomial can "squash" the values within the operator's numerical range while remaining normalized at 1. This reduces the acceleration problem to a complex-plane Chebyshev problem.

The Chebyshev polynomial "squashes" values within the numerical range to minimize the residual.

The Geometry of Convergence and Sampling

A critical insight is that the "fatness" of the numerical range relative to the point 1 dictates acceleration stability. For methods like Nesterov’s, the numerical range can be problematic. The authors propose applying RNA to powers of the operator (sampling every $k$ iterates). This sub-sampling effectively shrinks the numerical range and moves it away from 1, making the acceleration process both stable and effective.

Numerical range $W(O^k)$ for various powers $k$. As $k$ increases, the range shrinks away from the critical value 1, enabling effective acceleration.

Experimental Validation

The proposed acceleration scheme was evaluated across several domains:

  • Synthetic Quadratic Problems: Used to visualize the numerical range of operators and validate the theoretical bounds.
  • Image Processing: In Total Variation (TV) denoising tasks, the Offline RNA variant of the Primal-Dual Gradient Method (PDGM) consistently outperformed standard PDGM and its momentum-based variants.
  • Machine Learning Benchmarks: On $l_2$-regularized logistic regression and ridge regression tasks using UCI benchmarks and the NIPS 2003 Variable Selection Benchmark, RNA proved more robust than classical Anderson acceleration, particularly in high-accuracy regimes.

Conclusion

By bridging optimization theory with complex analysis and matrix theory, this work provides a robust framework for accelerating a wide class of non-symmetric optimization algorithms. RNA offers a "nonlinear" average that adapts to the local geometry of the optimization landscape. While highly effective for smooth operators, extending the rigorous theory to non-smooth mappings remains a key area for future research.

Summary updated

Abstract

We describe a convergence acceleration scheme for multi-step optimization algorithms. The extrapolated solution is written as a nonlinear average of the iterates produced by the original optimization algorithm. Our scheme does not need the underlying fixed-point operator to be symmetric, hence handles e.g. algorithms with momentum terms such as Nesterov’s accelerated method, or primal-dual methods such as Chambolle-Pock. The weights are computed via a simple linear system and we analyze performance in both online and offline modes. We use Crouzeix’s conjecture to show that acceleration is controlled by the solution of a Chebyshev problem on the numerical range of a nonsymmetric operator modelling the behavior of iterates near the optimum. Numerical experiments are detailed on image processing and logistic regression problems.
BibTeX
@inproceedings{bollapragada2019nonlinear,
  author = {Raghu Bollapragada and Damien Scieur and Alexandre d'Aspremont},
  title = {{Nonlinear Acceleration of Primal-Dual Algorithms}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=W8HqwkTVWU},
}
Figure