Nonlinear Acceleration of Primal-Dual Algorithms

Raghu Bollapragada, Damien Scieur, Alexandre d’Aspremont
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:739-747, 2019.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-bollapragada19a, title = {Nonlinear Acceleration of Primal-Dual Algorithms}, author = {Bollapragada, Raghu and Scieur, Damien and d'Aspremont, Alexandre}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {739--747}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/bollapragada19a/bollapragada19a.pdf}, url = {https://proceedings.mlr.press/v89/bollapragada19a.html}, 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.} }
Endnote
%0 Conference Paper %T Nonlinear Acceleration of Primal-Dual Algorithms %A Raghu Bollapragada %A Damien Scieur %A Alexandre d’Aspremont %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-bollapragada19a %I PMLR %P 739--747 %U https://proceedings.mlr.press/v89/bollapragada19a.html %V 89 %X 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.
APA
Bollapragada, R., Scieur, D. & d’Aspremont, A.. (2019). Nonlinear Acceleration of Primal-Dual Algorithms. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:739-747 Available from https://proceedings.mlr.press/v89/bollapragada19a.html.

Related Material