Accelerating Stochastic Composition Optimization

Abstract

Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic first-order method, namely the accelerated stochastic compositional proximal gradient (ASC-PG) method, which updates based on queries to the sampling oracle using two different timescales. The ASC-PG is the first proximal gradient method for the stochastic composition problem that can deal with nonsmooth regularization penalty. We show that the ASC-PG exhibits faster convergence than the best known algorithms, and that it achieves the optimal sample-error complexity in several important special cases. We further demonstrate the application of ASC-PG to reinforcement learning and conduct numerical experiments.

References in corpus (4)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Investigating practical linear temporal difference learning

Cited by in corpus (9)

• Variance Reduced methods for Non-convex Composition Optimization
• Compositional ADAM: An Adaptive Compositional Solver
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization
• Borrowing From the Future: Addressing Double Sampling in Model-free Control
• Stochastic Proximal AUC Maximization
• Fast Stochastic Variance Reduced ADMM for Stochastic Composition Optimization
• Borrowing From the Future: An Attempt to Address Double Sampling
• PASTO: Strategic Parameter Optimization in Recommendation Systems -- Probabilistic is Better than Deterministic