Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Stochastic Optimization

October 21, 2021


We consider the problem of minimizing composite functions of the form f(g(x)) + h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector map- ping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochas- tic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an ε-stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When g is a finite average of N components, we ob- tain sample complexity O(N + N^{4/5} ε^{−1}) for both mapping and Jacobian evaluations. When g is a general expectation, we obtain sample complexities of O(ε^{−5/2}) and O(ε^{−3/2}) for component mappings and their Jacobians respectively. If in addition f is smooth, then improved sample complexities of O(N + N^{1/2} ε^{−1}) and O(ε^{−3/2}) are derived for g being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.

Download the Paper


Written by

Lin Xiao

Junyu Zhang


Mathematical Programming

Research Topics


Core Machine Learning

Help Us Pioneer The Future of AI

We share our open source frameworks, tools, libraries, and models for everything from research exploration to large-scale production deployment.