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

arXiv: https://arxiv.org/abs/2002.11172 · HTML: https://mlsanity.com/paper/2002.11172/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

## Built on by (most cited first, 17 of 17)

- [Bridging Multi-Task Learning and Meta-Learning: Towards Efficient Training and Effective Adaptation](https://mlsanity.com/paper/2106.09017/) (2021)
- [How Fine-Tuning Allows for Effective Meta-Learning](https://mlsanity.com/paper/2105.02221/) (2021)
- [Sample Efficient Linear Meta-Learning by Alternating Minimization](https://mlsanity.com/paper/2105.08306/) (2021)
- [Learning-to-learn non-convex piecewise-Lipschitz functions](https://mlsanity.com/paper/2108.08770/) (2021)
- [A Representation Learning Perspective on the Importance of Train-Validation Splitting in Meta-Learning](https://mlsanity.com/paper/2106.15615/) (2021)
- [Meta-learning with negative learning rates](https://mlsanity.com/paper/2102.00940/) (2021)
- [Metalearning with Very Few Samples Per Task](https://mlsanity.com/paper/2312.13978/) (2023)
- [Neural Operator: Is data all you need to model the world? An insight into the paradigm of data-driven scientific ML](https://mlsanity.com/paper/2301.13331/) (2023)
- [Meta-Learning Adversarial Bandit Algorithms](https://mlsanity.com/paper/2307.02295/) (2023)
- [Deep Transfer Learning: Model Framework and Error Analysis](https://mlsanity.com/paper/2410.09383/) (2024)
- [Provable Meta-Learning with Low-Rank Adaptations](https://mlsanity.com/paper/2410.22264/) (2024)
- [Learning Tensor Representations for Meta-Learning](https://mlsanity.com/paper/2201.07348/) (2022)
- [Where and How to Enhance: Discovering Bit-Width Contribution for Mixed Precision Quantization](https://mlsanity.com/paper/2508.03002/) (2025)
- [Transformers are almost optimal metalearners for linear classification](https://mlsanity.com/paper/2510.19797/) (2025)
- [First-order ANIL provably learns representations despite overparametrization](https://mlsanity.com/paper/2303.01335/) (2023)
- [Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances](https://mlsanity.com/paper/2310.02246/) (2023)
- [State-of-the-art in Robot Learning for Multi-Robot Collaboration: A Comprehensive Survey](https://mlsanity.com/paper/2408.11822/) (2024)

## Abstract (arXiv)

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 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.