An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints

Adil Salim, Laurent Condat, Dmitry Kovalev, Peter Richtarik
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:4482-4498, 2022.

Abstract

Optimization problems under affine constraints appear in various areas of machine learning. We consider the task of minimizing a smooth strongly convex function F(x) under the affine constraint Kx = b, with an oracle providing evaluations of the gradient of F and multiplications by K and its transpose. We provide lower bounds on the number of gradient computations and matrix multiplications to achieve a given accuracy. Then we propose an accelerated primal-dual algorithm achieving these lower bounds. Our algorithm is the first optimal algorithm for this class of problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-salim22a, title = { An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints }, author = {Salim, Adil and Condat, Laurent and Kovalev, Dmitry and Richtarik, Peter}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {4482--4498}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/salim22a/salim22a.pdf}, url = {https://proceedings.mlr.press/v151/salim22a.html}, abstract = { Optimization problems under affine constraints appear in various areas of machine learning. We consider the task of minimizing a smooth strongly convex function F(x) under the affine constraint Kx = b, with an oracle providing evaluations of the gradient of F and multiplications by K and its transpose. We provide lower bounds on the number of gradient computations and matrix multiplications to achieve a given accuracy. Then we propose an accelerated primal-dual algorithm achieving these lower bounds. Our algorithm is the first optimal algorithm for this class of problems. } }
Endnote
%0 Conference Paper %T An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints %A Adil Salim %A Laurent Condat %A Dmitry Kovalev %A Peter Richtarik %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-salim22a %I PMLR %P 4482--4498 %U https://proceedings.mlr.press/v151/salim22a.html %V 151 %X Optimization problems under affine constraints appear in various areas of machine learning. We consider the task of minimizing a smooth strongly convex function F(x) under the affine constraint Kx = b, with an oracle providing evaluations of the gradient of F and multiplications by K and its transpose. We provide lower bounds on the number of gradient computations and matrix multiplications to achieve a given accuracy. Then we propose an accelerated primal-dual algorithm achieving these lower bounds. Our algorithm is the first optimal algorithm for this class of problems.
APA
Salim, A., Condat, L., Kovalev, D. & Richtarik, P.. (2022). An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:4482-4498 Available from https://proceedings.mlr.press/v151/salim22a.html.

Related Material