Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization - Zhang, Junyu; Xiao, Lin (Microsoft, 2020)
We consider minimization of composite functions of the form , where and are convex functions (which can be nonsmooth) and is a smooth vector mapping. In addition, we assume that is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic 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 is a finite average of components, we obtain sample complexity for both mapping and Jacobian evaluations. When is a general expectation, we obtain sample complexities of and for component mappings and their Jacobians respectively. If in addition is smooth, then improved sample complexities of and are derived for being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.