Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient

2018-06-01 · Tianyi Lin, Chenyou Fan, Mengdi Wang, Michael. I. Jordan

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.

📄 PDF Abstract BibTeX arXiv:1806.00458

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization

2022-07-18 · Wei Jiang, Gang Li, Yibo Wang, Lijun Zhang 외

Variance reduction techniques such as SPIDER/SARAH/STORM have been extensively studied to improve the convergence rates of stochastic non-convex optimization, which usually maintain and update a sequence of estimators fo…

Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization

2018-02-07 · Tianyi Lin, Chenyou Fan, Mengdi Wang

We consider the nonsmooth convex composition optimization problem where the objective is a composition of two finite-sum functions and analyze stochastic compositional variance reduced gradient (SCVRG) methods for them. …

Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization

2023-08-18 · Jin Liu, Xiaokang Pan, Junwen Duan, Hongdong Li 외

This paper delves into the realm of stochastic optimization for compositional minimax optimization - a pivotal challenge across various machine learning domains, including deep AUC and reinforcement learning policy evalu…

Stochastic Optimization

Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization

2019-12-31 · Huizhuo Yuan, Xiangru Lian, Ji Liu

Stochastic compositional optimization arises in many important machine learning tasks such as value function evaluation in reinforcement learning and portfolio management. The objective function is the composition of two…

Management Reinforcement Learning Stochastic Optimization

Optimal Algorithms for Stochastic Multi-Level Compositional Optimization

2022-02-15 · Wei Jiang, Bokun Wang, Yibo Wang, Lijun Zhang 외

In this paper, we investigate the problem of stochastic multi-level compositional optimization, where the objective function is a composition of multiple smooth but possibly non-convex functions. Existing methods for sol…