Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning

Abstract

As a popular meta-learning approach, the model-agnostic meta-learning (MAML) algorithm has been widely used due to its simplicity and effectiveness. However, the convergence of the general multi-step MAML still remains unexplored. In this paper, we develop a new theoretical framework to provide such convergence guarantee for two types of objective functions that are of interest in practice: (a) resampling case (e.g., reinforcement learning), where loss functions take the form in expectation and new data are sampled as the algorithm runs; and (b) finite-sum case (e.g., supervised learning), where loss functions take the finite-sum form with given samples. For both cases, we characterize the convergence rate and the computational complexity to attain an $\epsilon$-accurate solution for multi-step MAML in the general nonconvex setting. In particular, our results suggest that an inner-stage stepsize needs to be chosen inversely proportional to the number $N$ of inner-stage steps in order for $N$-step MAML to have guaranteed convergence. From the technical perspective, we develop novel techniques to deal with the nested structure of the meta gradient for multi-step MAML, which can be of independent interest.

arXiv comment40 pages

References in corpus (21)

• Adam: A Method for Stochastic Optimization
• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Prototypical Networks for Few-shot Learning
• Trust Region Policy Optimization
• Theoretical Models of Learning to Learn
• Meta-SGD: Learning to Learn Quickly for Few-Shot Learning
• On First-Order Meta-Learning Algorithms
• Federated Meta-Learning with Fast Convergence and Efficient Communication
• One-Shot Visual Imitation Learning via Meta-Learning
• Fast Context Adaptation via Meta-Learning
• Few-Shot Learning via Learning the Representation, Provably
• Provable Meta-Learning of Linear Representations
• Learning-to-Learn Stochastic Gradient Descent with Biased Regularization
• On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
• Task-Robust Model-Agnostic Meta-Learning
• Incremental Learning-to-Learn with Statistical Guarantees
• Reconciling meta-learning and continual learning with online mixtures of tasks
• On the Global Optimality of Model-Agnostic Meta-Learning
• UFO-BLO: Unbiased First-Order Bilevel Optimization
• Multi-step Estimation for Gradient-based Meta-learning

Cited by in corpus (10)

• Dif-MAML: Decentralized Multi-Agent Meta-Learning
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization
• Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis
• UFO-BLO: Unbiased First-Order Bilevel Optimization
• The Advantage of Conditional Meta-Learning for Biased Regularization and Fine-Tuning
• How Does the Task Landscape Affect MAML Performance?
• Multi-step Estimation for Gradient-based Meta-learning
• Meta-Learning Strategies through Value Maximization in Neural Networks
• Compositional federated learning: Applications in distributionally robust averaging and meta learning