Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
This work addresses sample complexity issues in convex composition optimization for fields like reinforcement learning, offering a near-optimal algorithm that is incremental in improving upon existing methods.
The paper tackles the problem of convex composition optimization, which has applications in stochastic optimal control, reinforcement learning, and multi-stage stochastic programming, by developing a new stochastic compositional variance-reduced gradient algorithm that achieves a sample complexity of O((m+n)log(1/ε)+1/ε^3), with m+n being the total number of samples, and demonstrates its effectiveness on real-world datasets.
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/ε)+1/ε^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.