Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization

Abstract

Stochastic compositional optimization generalizes classic (non-compositional) stochastic optimization to the minimization of compositions of functions. Each composition may introduce an additional expectation. The series of expectations may be nested. Stochastic compositional optimization is gaining popularity in applications such as reinforcement learning and meta learning. This paper presents a new Stochastically Corrected Stochastic Compositional gradient method (SCSC). SCSC runs in a single-time scale with a single loop, uses a fixed batch size, and guarantees to converge at the same rate as the stochastic gradient descent (SGD) method for non-compositional stochastic optimization. This is achieved by making a careful improvement to a popular stochastic compositional gradient method. It is easy to apply SGD-improvement techniques to accelerate SCSC. This helps SCSC achieve state-of-the-art performance for stochastic compositional optimization. In particular, we apply Adam to SCSC, and the exhibited rate of convergence matches that of the original Adam on non-compositional stochastic optimization. We test SCSC using the portfolio management and model-agnostic meta-learning tasks.

Accepted in IEEE Transactions on Signal Processing. The short version of this paper has been awarded the IEEE ICASSP Best Student Paper Award

References in corpus (8)

• On the Convergence of Adam and Beyond
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Online Meta-Learning
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Provable Guarantees for Gradient-Based Meta-Learning
• Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization
• Unbiased Simulation for Optimizing Stochastic Function Compositions
• A Stochastic Composite Gradient Method with Incremental Variance Reduction

Cited by in corpus (12)

• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Learning to Continuously Optimize Wireless Resource in a Dynamic Environment: A Bilevel Optimization Perspective
• Training Robust Deep Models for Time-Series Domain: Novel Algorithms and Theoretical Analysis
• Projection-Free Algorithm for Stochastic Bi-level Optimization
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning
• Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks
• Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization
• Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks
• Optimal Algorithms for Convex Nested Stochastic Composite Optimization
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• Compositional federated learning: Applications in distributionally robust averaging and meta learning