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
$\mathcal{O}(k^{-1/3})$ convergence rate in expectation on the objective
residual and $\mathcal{O}(k^{-5/12})$ on the feasibility gap.
