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. |
Year | Venue | DocType |
---|---|---|
2022 | INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 151 | Conference |
Volume | ISSN | Citations |
151 | 2640-3498 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Adil Salim | 1 | 2 | 4.42 |
Laurent Condat | 2 | 65 | 6.92 |
Kovalev, Dmitry | 3 | 1 | 4.40 |
Peter Richtárik | 4 | 1314 | 84.53 |