Multi-Level Composite Stochastic Optimization via Nested Variance Reduction

DOI10.1137/19M1285457MaRDI QIDQ6324404arXivFDO

Authors Junyu Zhang, Lin Xiao

Publication date 29 August 2019

Published in arXiv

Full work available at URL https://doi.org/10.1137/19M1285457

Mathematics Subject Classification ID

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

arXiv classification

math.OCstat.ML

Abstract: We consider multi-level composite optimization problems where each mapping in the composition is the expectation over a family of random smooth mappings or the sum of some finite number of smooth mappings. We present a normalized proximal approximate gradient (NPAG) method where the approximate gradients are obtained via nested stochastic variance reduction. In order to find an approximate stationary point where the expected norm of its gradient mapping is less than $epsilon$, the total sample complexity of our method is $O(epsilo{n}^{-3})$ in the expectation case, and $O(N+sqrtNepsilo{n}^{-2})$ in the finite-sum case where $N$ is the total number of functions across all composition levels. In addition, the dependence of our total sample complexity on the number of composition levels is polynomial, rather than exponential as in previous work.

This page was built for publication: Multi-Level Composite Stochastic Optimization via Nested Variance Reduction

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