Few-Shot Learning via Learning the Representation, Provably

By Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, Qi Lei. 2020

298 citations recorded by the source corpus.

This paper studies few-shot learning via representation learning, where one uses $T$ source tasks with $n_1$ data per task to learn a representation in order to reduce the sample complexity of a target task for which there is only $n_2 (\ll n_1)$ data. Specifically, we focus on the setting where there exists a good \emph{common representation} between source and target, and our goal is to understand how much of a sample size reduction is possible. First, we study the setting where this common representation is low-dimensional and provide a fast rate of $O\left(\frac{\mathcal{C}\left(\Phi\right)}{n_1T} + \frac{k}{n_2}\right)$; here, $\Phi$ is the representation function class, $\mathcal{C}\left(\Phi\right)$ is its complexity measure, and $k$ is the dimension of the representation. When specialized to linear representation functions, this rate becomes $O\left(\frac{dk}{n_1T} + \frac{k}{n_2}\right)$ where $d (\gg k)$ is the ambient input dimension, which is a substantial improvement over the rate without using representation learning, i.e. over the rate of $O\left(\frac{d}{n_2}\right)$. Second, we consider the setting where the common representation may be high-dimensional but is capacity-constrained (say in norm); here, we again demonstrate the advantage of representation learning in both high-dimensional linear regression and neural network learning. Our results demonstrate representation learning can fully utilize all $n_1T$ samples from source tasks.

Subfields: Artificial Intelligence, Computational Mechanics, Representation & Self-Supervised Learning

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 Computational Mechanics

In Representation & Self-Supervised Learning

Citations in the corpus

Rethinking Few-Shot Image Classification: a Good Embedding Is All You Need? (2020, background): “ meta-testing set. On the other hand, we also ﬁnd that self-supervised embedding, which does not explicitly require this NKcompositionality, achieves a similar level of performance. A concurrent work [10] studies the representations for few-shot learning from the theoretical point of view. 3. Does y”
The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “Yet another task relationship is that every objective Lt is the composition of two functions ft ◦ g, where the function g : Rn → Rs is referred to as the shared representation; see, e.g., Maurer et al. (2016); Balcan et al. (2015); Tripuraneni et al. (2021); Du et al. (2021).”
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.”
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).”
Continual Learning with Filter Atom Swapping (2022, methodology): “By convert input feature x to the lifted feature vector φ ( x ) , according to (Du et al., 2020), Equation.”
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.”
A No-Free-Lunch Theorem for MultiTask Learning (2020, methodology): “…latent substructures, both as applied to classiﬁcation (Muandet, Balduzzi and Schölkopf, 2013; McNamara and Balcan, 2017; Arora et al., 2019), or to regression settings (Jalali et al., 2010; Lounici et al., 2011; Negahban and Wainwright, 2011; Du et al., 2020; Tripuraneni, Jordan and Jin, 2020).”
Provable Meta-Learning of Linear Representations (2020, result): “In concurrent work, Du et al. (2020) obtain results similar to ours for multi-task linear regression and provide comparable guarantees for a two-layer ReLU network using a notion of training task diversity akin to ours.”
Meta-Adaptive Nonlinear Control: Theory and Algorithms (2021, background): “On the theoretic side, [4, 5, 33] have shown representation learning reduces sample complexity on new tasks, and “task diversity” is critical.”
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).”
A Scaling Law for Syn2real Transfer: How Much Is Your Pre-training Effective? (2021, result): “Among others, some recent studies [16, 42, 62] derived an error bound of a ﬁne-tuning task in the multi-task scenario based on complexity analysis; the bound takes an additive form O ( An − 1 / 2 + Bs − 1 / 2 ) , where n and s are the data size of pre-training and ﬁne-tuning, respectively, with…”
Exploiting Shared Representations for Personalized Federated Learning (2021, background): “[2016], Du et al. [2020] and Tripuraneni et al. [2020a], learning an accurate k-dimensional representation during training (or meta-training) reduces the sample complexity of solving a new task from Θ(d) to Θ(k) in the linear case, enabling strong few-shot performance if k is small.”
Provable and Efficient Continual Representation Learning (2022, methodology): “Our analysis is related to the literature on representation learning theory [55, 39, 85, 18, 26, 76, 3].”
On the Theory of Transfer Learning: The Importance of Task Diversity (2020, background): “[2020] and Du et al. [2020], where it is restricted to the special case of linear functions and quadratic loss.”
In-N-Out: Pre-Training and Self-Training using Auxiliary Information for Out-of-Distribution Robustness (2020, methodology): “Our setup extends a linear regression setting commonly used for analyzing multi-task problems [13, 46].”
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution (2022, unknown): “Prior works on transfer learning mainly analyze linear probing (Wu et al., 2020; Tripuraneni et al., 2020; Du et al., 2020).”
What Makes Multimodal Learning Better than Single (Provably) (2021, background): “[40, 7, 32, 10] have provided the sample complexity bounds in the special case of the linear feature and linear task mapping.”