Provable Meta-Learning of Linear Representations

By Nilesh Tripuraneni, Chi Jin, Michael I. Jordan. 2020

230 citations recorded by the source corpus.

Meta-learning, or learning-to-learn, seeks to design algorithms that can utilize previous experience to rapidly learn new skills or adapt to new environments. Representation learning---a key tool for performing meta-learning---learns a data representation that can transfer knowledge across multiple tasks, which is essential in regimes where data is scarce. Despite a recent surge of interest in the practice of meta-learning, the theoretical underpinnings of meta-learning algorithms are lacking, especially in the context of learning transferable representations. In this paper, we focus on the problem of multi-task linear regression---in which multiple linear regression models share a common, low-dimensional linear representation. Here, we provide provably fast, sample-efficient algorithms to address the dual challenges of (1) learning a common set of features from multiple, related tasks, and (2) transferring this knowledge to new, unseen tasks. Both are central to the general problem of meta-learning. Finally, we complement these results by providing information-theoretic lower bounds on the sample complexity of learning these linear features.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions (2022, background): “Some recent theoretical works [18, 19, 26, 36, 20, 35, 9] provide generalization and sample complexity guarantees for certain formalizations of multi-task learning based on the existence of a good representation.”
What Makes Multimodal Learning Better than Single (Provably) (2021, background): “Assumption 1 is a classical regularity condition for loss function in theoretical analysis [27, 41, 40].”
Provable and Efficient Continual Representation Learning (2022, background): “To the best of our knowledge, existing works on multitask learning do not achieve fast rates except for linear representations (Tripuraneni et al. (2020a); Sun et al. (2021)) which is a distinguishing feature of our bound.”
On the Theory of Transfer Learning: The Importance of Task Diversity (2020, background): “Despite the abstraction in this deﬁnition of task diversity, it exactly recovers the notion of task diversity in Tripuraneni et al. [2020] and Du et al. [2020], where it is restricted to the special case of linear functions and quadratic loss.”
Provable Lifelong Learning of Representations (2021, background): “We compare our results with recent work [Du et al., 2020, Tripuraneni et al., 2020, Balcan et al., 2015] in Table 1 for the linear case.”
Exploiting Shared Representations for Personalized Federated Learning (2021, methodology): “…of tasks is a classical approach in multi-task learning [Ando et al., 2005, Balcan et al., 2015, Baxter, 2000, Bengio et al., 2013, Bullins et al., 2019, Denevi et al., 2018, Kong et al., 2020, LeCun et al., 2015, Pontil and Maurer, 2013, Rish et al., 2008, Tripuraneni et al., 2020b].”
Meta-Adaptive Nonlinear Control: Theory and Algorithms (2021, background): “Therefore, the ACE upper bound of OMAC is better than the baseline adaptation if N > T , which is consistent with recent representation learning results [4, 5].”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, background): “This can be often achieved by learning a compact representation that is shared among multiple tasks (Tripuraneni et al., 2021; Du et al., 2021; Collins et al., 2022).”
Meta-Learning with Neural Tangent Kernels (2021, unknown): “…(MAML) (Finn et al., 2017) is perhaps one of the most popular and ﬂexible ones, with a number of follow-up works such as (Nichol et al., 2018; Finn et al., 2018; Yao et al., 2019; Khodak et al., 2019a;b; Denevi et al., 2019; Fallah et al., 2020; Lee et al., 2020; Tripuraneni et al., 2020).”