# Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization

arXiv: https://arxiv.org/abs/1711.03937 · HTML: https://mlsanity.com/paper/1711.03937/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2017.

## Built on by (most cited first, 13 of 13)

- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Compositional federated learning: Applications in distributionally robust averaging and meta learning](https://mlsanity.com/paper/2106.11264/) (2021)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Learning Distributionally Robust Models at Scale via Composite Optimization](https://mlsanity.com/paper/2203.09607/) (2022)
- [Federated Conditional Stochastic Optimization](https://mlsanity.com/paper/2310.02524/) (2023)
- [Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows](https://mlsanity.com/paper/2112.01363/) (2021)
- [Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimization](https://mlsanity.com/paper/2211.01883/) (2022)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [Riemannian Stochastic Gradient Method for Nested Composition Optimization](https://mlsanity.com/paper/2207.09350/) (2022)

## Abstract (arXiv)

Stochastic composition optimization draws much attention recently and has been successful in many emerging applications of machine learning, statistical analysis, and reinforcement learning. In this paper, we focus on the composition problem with nonsmooth regularization penalty. Previous works either have slow convergence rate or do not provide complete convergence analysis for the general problem. In this paper, we tackle these two issues by proposing a new stochastic composition optimization method for composition problem with nonsmooth regularization penalty. In our method, we apply variance reduction technique to accelerate the speed of convergence. To the best of our knowledge, our method admits the fastest convergence rate for stochastic composition optimization: for strongly convex composition problem, our algorithm is proved to admit linear convergence; for general composition problem, our algorithm significantly improves the state-of-the-art convergence rate from O(T-1/2) to O((n1+n2)^2/3T-1). Finally, we apply our proposed algorithm to portfolio management and policy evaluation in reinforcement learning. Experimental results verify our theoretical analysis.