Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient

Abstract

Convex composition optimization is an emerging topic that covers a wide range of applications arising from stochastic optimal control, reinforcement learning and multi-stage stochastic programming. Existing algorithms suffer from unsatisfactory sample complexity and practical issues since they ignore the convexity structure in the algorithmic design. In this paper, we develop a new stochastic compositional variance-reduced gradient algorithm with the sample complexity of $O((m+n)\log (1/\epsilon )+1/{\epsilon }^3)$ where $m+n$ is the total number of samples. Our algorithm is near-optimal as the dependence on $m+n$ is optimal up to a logarithmic factor. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of the new algorithm.

arXiv comment6 Pages. Accepted by ACC 2020

References in corpus (9)

• Variable selection in nonparametric additive models
• Stochastic Variance Reduction for Nonconvex Optimization
• Variance Reduction for Faster Non-Convex Optimization
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Tight Complexity Bounds for Optimizing Composite Objectives
• SDCA without Duality
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization
• Multi-Level Stochastic Gradient Methods for Nested Composition Optimization

Cited by in corpus (9)

• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Compositional ADAM: An Adaptive Compositional Solver
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization
• Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
• Compositional federated learning: Applications in distributionally robust averaging and meta learning
• Compositional Stochastic Average Gradient for Machine Learning and Related Applications