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

DOI10.1007/S10107-021-01709-ZMaRDI QIDQ6338400arXivFDO

Authors Junyu Zhang, Lin Xiao

Publication date 9 April 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/S10107-021-01709-Z

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Nonconvex programming, global optimization (90C26)

arXiv classification

math.OC

Abstract: We consider minimization of 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 mapping. 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 stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an $epsilon$-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 obtain sample complexity $mathcalO(N+N^{4/5}epsilo{n}^{-1})$ for both mapping and Jacobian evaluations. When $g$ is a general expectation, we obtain sample complexities of $mathcalO(epsilo{n}^{-5/2})$ and $mathcalO(epsilo{n}^{-3/2})$ for component mappings and their Jacobians respectively. If in addition $f$ is smooth, then improved sample complexities of $mathcalO(N+N^{1/2}epsilo{n}^{-1})$ and $mathcalO(epsilo{n}^{-3/2})$ are derived for $g$ being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.

This page was built for publication: Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338400)