# Sample Efficient Linear Meta-Learning by Alternating Minimization

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 18 May 2021.

## Builds on (most cited first, 14 of 14)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [Exploiting Shared Representations for Personalized Federated Learning](https://mlsanity.com/paper/2102.07078/) (2021)
- [Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML](https://mlsanity.com/paper/1909.09157/) (2019)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms](https://mlsanity.com/paper/1908.10400/) (2019)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Learning Internal Representations (COLT 1995)](https://mlsanity.com/paper/1911.05781/) (2019)
- [A Sample Complexity Separation between Non-Convex and Convex Meta-Learning](https://mlsanity.com/paper/2002.11172/) (2020)
- [Computational Limits for Matrix Completion](https://mlsanity.com/paper/1402.2331/) (2014)

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

- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [Robust Federated Finetuning of LLMs via Alternating Optimization of LoRA](https://mlsanity.com/paper/2502.01755/) (2025)
- [Nearly Minimax Algorithms for Linear Bandits with Shared Representation](https://mlsanity.com/paper/2203.15664/) (2022)
- [Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/2307.06887/) (2023)
- [Active Multi-Task Representation Learning](https://mlsanity.com/paper/2202.00911/) (2022)
- [Subspace Recovery from Heterogeneous Data with Non-isotropic Noise](https://mlsanity.com/paper/2210.13497/) (2022)
- [Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data](https://mlsanity.com/paper/2308.04428/) (2023)
- [Metalearning with Very Few Samples Per Task](https://mlsanity.com/paper/2312.13978/) (2023)
- [Trace norm regularization for multi-task learning with scarce data](https://mlsanity.com/paper/2202.06742/) (2022)
- [Linear Speedup in Personalized Collaborative Learning](https://mlsanity.com/paper/2111.05968/) (2021)
- [Improved Active Multi-Task Representation Learning via Lasso](https://mlsanity.com/paper/2306.02556/) (2023)
- [FloE: On-the-Fly MoE Inference on Memory-constrained GPU](https://mlsanity.com/paper/2505.05950/) (2025)
- [Federated Representation Learning in the Under-Parameterized Regime](https://mlsanity.com/paper/2406.04596/) (2024)
- [Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits](https://mlsanity.com/paper/2410.02068/) (2024)
- [Multitask Learning via Shared Features: Algorithms and Hardness](https://mlsanity.com/paper/2209.03112/) (2022)
- [PromptRefine: Enhancing Few-Shot Performance on Low-Resource Indic Languages with Example Selection from Related Example Banks](https://mlsanity.com/paper/2412.05710/) (2024)
- [Blessing of Class Diversity in Pre-training](https://mlsanity.com/paper/2209.03447/) (2022)
- [Regret Analysis of Multi-task Representation Learning for Linear-Quadratic Adaptive Control](https://mlsanity.com/paper/2407.05781/) (2024)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [Active Representation Learning for General Task Space with Applications in Robotics](https://mlsanity.com/paper/2306.08942/) (2023)
- [Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples](https://mlsanity.com/paper/2410.11227/) (2024)
- [Effects of Structural Allocation of Geometric Task Diversity in Linear Meta-Learning Models](https://mlsanity.com/paper/2509.18349/) (2025)
- [Collaborative and Efficient Fine-tuning: Leveraging Task Similarity](https://mlsanity.com/paper/2602.07218/) (2026)
- [RepUCB: Representation Learning-Based UCB for Heterogeneous Multi-Task Linear Bandits](https://mlsanity.com/paper/2604.00531/) (2026)
- [Multi-Task Representation Learning for Conservative Linear Bandits](https://mlsanity.com/paper/2605.12176/) (2026)

## Abstract (arXiv)

Meta-learning synthesizes and leverages the knowledge from a given set of tasks to rapidly learn new tasks using very little data. Meta-learning of linear regression tasks, where the regressors lie in a low-dimensional subspace, is an extensively-studied fundamental problem in this domain. However, existing results either guarantee highly suboptimal estimation errors, or require Omega(d) samples per task (where d is the data dimensionality) thus providing little gain over separately learning each task. In this work, we study a simple alternating minimization method (MLLAM), which alternately learns the low-dimensional subspace and the regressors. We show that, for a constant subspace dimension MLLAM obtains nearly-optimal estimation error, despite requiring only Omega(log d) samples per task. However, the number of samples required per task grows logarithmically with the number of tasks. To remedy this in the low-noise regime, we propose a novel task subset selection scheme that ensures the same strong statistical guarantee as MLLAM, even with bounded number of samples per task for arbitrarily large number of tasks.