Abstract:

We consider minimization of stochastic functionals that are compositions of a (potentially) non-smooth convex function h and smooth function c. We develop two stochastic methods--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. Additionally, we analyze this problem class in the context of phase retrieval and other nonlinear modeling problems, showing that we can solve these problems (even with faulty measurements) with extremely high probability under appropriate random measurement models. We provide substantial experiments investigating our methods, indicating the practical effectiveness of the procedures.