Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
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(\epsilon^{-3})$ in the expectation case, and $O(N+\sqrt{N}\epsilon^{-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.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationSimilar Papers 제목 키워드 기반
Optimal Algorithms for Convex Nested Stochastic Composite Optimization
Recently, convex nested stochastic composite optimization (NSCO) has received considerable attention for its applications in reinforcement learning and risk-averse optimization. The current NSCO algorithms have worse sto…
Stochastic OptimizationClosing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems
Stochastic nested optimization, including stochastic compositional, min-max, and bilevel optimization, is gaining popularity in many machine learning applications. While the three problems share a nested structure, exist…
Bilevel OptimizationConstructing unbiased gradient estimators with finite variance for conditional stochastic optimization
We study stochastic gradient descent for solving conditional stochastic optimization problems, in which an objective to be minimized is given by a parametric nested expectation with an outer expectation taken with respec…
Stochastic OptimizationTighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
Stochastic nested optimization, including stochastic compositional, min-max and bilevel optimization, is gaining popularity in many machine learning applications. While the three problems share the nested structure, exis…
Bilevel OptimizationRiemannian Stochastic Gradient Method for Nested Composition Optimization
This work considers optimization of composition of functions in a nested form over Riemannian manifolds where each function contains an expectation. This type of problems is gaining popularity in applications such as pol…
Meta-Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)