Optimal Minimization of the Sum of Three Convex Functions with a Linear Operator
[edit]
Proceedings of Machine Learning Research, PMLR 89:11851194, 2019.
Abstract
We propose a class of optimalrate primaldual algorithms for minimization of the sum of three convex functions with a linear operator. We first establish the optimal convergence rates for solving the saddlepoint reformulation of the problem only using firstorder information under deterministic and stochastic settings, respectively. We then proceed to show that the proposed algorithm class achieves these rates. The studied algorithm class does not require matrix inversion and is simple to implement. To our knowledge, this is the first work to establish and attain the optimal rates for this class of problems with minimal assumptions. Numerical experiments show that our method outperforms stateoftheart methods.
Related Material


