Stochastic Methods for Composite Optimization Problems

We consider minimization of stochastic functionals that are compositions of a (potentially) non-smooth convex function $h$ and smooth function $c$ and, more generally, stochastic weakly-convex functionals. We develop a family of stochastic methods---including a stochastic prox-linear algorithm and a stochastic (generalized) sub-gradient procedure---and prove that, under mild technical conditions, each converges to first-order stationary points of the stochastic objective. We provide experiments further investigating our methods on non-smooth phase retrieval problems; the experiments indicate the practical effectiveness of the procedures.