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

By Nikunj Saunshi, Yi Zhang, Mikhail Khodak, Sanjeev Arora. 2020

32 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent (2020, background): “…a statistical learning theory perspective, they define and provide regret bounds for lifelong learning (Alquier et al., 2017), or study the sample complexity and convergence of meta-learning algorithms (Denevi et al. 2018a, Du et al. 2020, Ji et al. 2020, Saunshi et al. 2020, Denevi et al. 2018b).”
When MAML Can Adapt Fast and How to Assist When It Cannot (2019, background): “Understanding how MAML and its alike work continues to draw research interests (Finn and Levine, 2018; Fallah et al., 2020; Raghu et al., 2020; Saunshi et al., 2020).”