A Sample Complexity Separation between Non-Convex and Convex Meta-Learning

Abstract

One popular trend in meta-learning is to learn from many training tasks a common initialization for a gradient-based method that can be used to solve a new task with few samples. The theory of meta-learning is still in its early stages, with several recent learning-theoretic analyses of methods such as Reptile [Nichol et al., 2018] being for convex models. This work shows that convex-case analysis might be insufficient to understand the success of meta-learning, and that even for non-convex models it is important to look inside the optimization black-box, specifically at properties of the optimization trajectory. We construct a simple meta-learning instance that captures the problem of one-dimensional subspace learning. For the convex formulation of linear regression on this instance, we show that the new task sample complexity of any initialization-based meta-learning algorithm is $\Omega (d)$, where $d$ is the input dimension. In contrast, for the non-convex formulation of a two layer linear network on the same instance, we show that both Reptile and multi-task representation learning can have new task sample complexity of $\mathcal{O}(1)$, demonstrating a separation from convex meta-learning. Crucially, analyses of the training dynamics of these methods reveal that they can meta-learn the correct subspace onto which the data should be projected.

34 pages

References in corpus (10)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Theoretical Models of Learning to Learn
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• A mathematical theory of semantic development in deep neural networks
• Meta-Learning with Implicit Gradients
• The Benefit of Multitask Representation Learning
• Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML
• An analytic theory of generalization dynamics and transfer learning in deep linear networks
• Learning-to-Learn Stochastic Gradient Descent with Biased Regularization

Cited by in corpus (5)

• When MAML Can Adapt Fast and How to Assist When It Cannot
• How Important is the Train-Validation Split in Meta-Learning?
• Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent
• Meta-learning with negative learning rates
• Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets