An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints

Adil Salim · Laurent CONDAT · Dmitry Kovalev · Peter Richtarik

[ Abstract ]
Tue 29 Mar 1 a.m. PDT — 2:30 a.m. PDT


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.

Chat is not available.