Stochastic Frank-Wolfe for Composite Convex Minimization

A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily available. In this setting, generalized conditional gradient methods (aka Frank-Wolfe-type methods) provide scalable solutions by leveraging the so-called linear minimization oracle instead of the projection onto the semidefinite cone. Most problems in machine learning and modern engineering applications, however, contain some degree of stochasticity. In this work, we propose the first conditional-gradient-type method for solving stochastic optimization problems under affine constraints. Our method guarantees O(k(-1/3)) convergence rate in expectation on the objective residual and O(k (5/12)) on the feasibility gap.


Published in:
Advances In Neural Information Processing Systems 32 (Nips 2019)
Presented at:
NeurIPS 2019 : Thirty-third Conference on Neural Information Processing Systems, Vancouver, Canada, December 8-14, 2019
Year:
2019
Keywords:
Laboratories:


Note: The status of this file is: Anyone


 Record created 2019-09-17, last modified 2020-07-10

Final:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)