An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints

Adil Salim; Laurent Pierre Condat; Dmitry Kovalev; Peter Richtarik

An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints

Adil Salim, Laurent Pierre Condat, Dmitry Kovalev, Peter Richtarik

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	The 25th International Conference on Artificial Intelligence and Statistics
Publisher	arXiv
State	Published - 2022

Bibliographical note

KAUST Repository Item: Exported on 2022-09-14
Acknowledgements: AS was supported by KAUST and by a Simons-Berkeley Research Fellowship.

Access to Document

https://repository.kaust.edu.sa/bitstream/10754/667732/5/2102.11079.pdf

Cite this

@inproceedings{aff9ab2b1a004205bdb3731be6b31751,

title = "An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints",

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.",

author = "Adil Salim and Condat, {Laurent Pierre} and Dmitry Kovalev and Peter Richtarik",

note = "KAUST Repository Item: Exported on 2022-09-14 Acknowledgements: AS was supported by KAUST and by a Simons-Berkeley Research Fellowship.",

year = "2022",

language = "English (US)",

booktitle = "The 25th International Conference on Artificial Intelligence and Statistics",

publisher = "arXiv",

}

TY - GEN

T1 - An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints

AU - Salim, Adil

AU - Condat, Laurent Pierre

AU - Kovalev, Dmitry

AU - Richtarik, Peter

N1 - KAUST Repository Item: Exported on 2022-09-14 Acknowledgements: AS was supported by KAUST and by a Simons-Berkeley Research Fellowship.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/667732

UR - https://proceedings.mlr.press/v151/salim22a.html

M3 - Conference contribution

BT - The 25th International Conference on Artificial Intelligence and Statistics

PB - arXiv

ER -

An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this