Accelerating Stochastic Composition Optimization

2016/07/25 by Mengdi Wang, Ji Liu, Wang, Mengdi +3 · 2 citations
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Optimization and Search Problems #Reinforcement Learning in Robotics #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1607.07329

openalex publication_date 2016/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• Making Gradient Descent Optimal for Strongly Convex Stochastic\n Optimization
• Finite-Sample Analysis of Proximal Gradient TD Algorithms

Cited by

• Non-smooth stochastic gradient descent using smoothing functions
• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization
• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization

Related

• Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization
• Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• Stochastic Compositional Gradient Descent under Compositional Constraints
• Stochastic Recursive Momentum Method for Non-Convex Compositional Optimization