Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning

Abstract

Conditional stochastic optimization covers a variety of applications ranging from invariant learning and causal inference to meta-learning. However, constructing unbiased gradient estimators for such problems is challenging due to the composition structure. As an alternative, we propose a biased stochastic gradient descent (BSGD) algorithm and study the bias-variance tradeoff under different structural assumptions. We establish the sample complexities of BSGD for strongly convex, convex, and weakly convex objectives under smooth and non-smooth conditions. Our lower bound analysis shows that the sample complexities of BSGD cannot be improved for general convex objectives and nonconvex objectives except for smooth nonconvex objectives with Lipschitz continuous gradient estimator. For this special setting, we propose an accelerated algorithm called biased SpiderBoost (BSpiderBoost) that matches the lower bound complexity. We further conduct numerical experiments on invariant logistic regression and model-agnostic meta-learning to illustrate the performance of BSGD and BSpiderBoost.

The updated version is the camera-ready version in NeurIPS 2020

References in corpus (17)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Theoretical Models of Learning to Learn
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Deep Generalized Method of Moments for Instrumental Variable Analysis
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• The proximal point method revisited
• Reinforcement Learning via Fenchel-Rockafellar Duality
• Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Adversarial Generalized Method of Moments
• Dual Instrumental Variable Regression
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• Learning with Group Invariant Features: A Kernel Perspective
• A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization

Cited by in corpus (6)

• Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers
• On the Convergence of SGD with Biased Gradients
• Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks
• Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets
• Learning Deep Neural Networks under Agnostic Corrupted Supervision
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction