Skip to main content

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

Author(s): Saunshi, Nikunj; Zhang, Yi; Khodak, Mikhail; Arora, Sanjeev

To refer to this page use:
Abstract: One popular trend in meta-learning is to learn from many training tasks a common initialization that a gradient-based method can use 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 \emph{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 \emph{initialization-based meta-learning} algorithm is Ω(𝑑), where 𝑑 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 𝑂(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.
Publication Date: 2020
Citation: Saunshi, Nikunj, Yi Zhang, Mikhail Khodak, and Sanjeev Arora. "A Sample Complexity Separation between Non-Convex and Convex Meta-Learning." In Proceedings of the 37th International Conference on Machine Learning (2020): pp. 8512-8521.
ISSN: 2640-3498
Pages: 8512 - 8521
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the 37th International Conference on Machine Learning
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.