Few-Shot Learning via Learning the Representation, Provably

Simon S. Du; Wei Hu; Sham M. Kakade; Jason D. Lee; Qi Lei

Source-linked AI summary

Few-Shot Learning via Learning the Representation, Provably

Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, Qi Lei

arXiv:2002.09434v2Feb 21, 2020cs.LGmath.OCstat.ML

TL;DR

The paper studies how shared representations learned from source tasks can reduce target-task sample requirements in few-shot learning. It develops analyses for low-dimensional and capacity-constrained representations, finding that representation learning can fully exploit all n1T source samples across linear and neural-network settings.

Problem
Few-shot learning needs to reduce target-task sample complexity when only n2 data are available, but prior bounds require many tasks and do not benefit from increasing n1.
Method
The paper learns a common representation with task-specific linear predictors and analyzes structural conditions under which source tasks cover the target task.
Results
Representation learning can fully exploit all n1T source samples in low-dimensional, high-dimensional, nonlinear, and overparametrized neural-network settings.
Takeaways & Limitations
Capacity control for representation learning need not come from explicit low dimensionality; norm-based high-dimensional representations can also provide the advantage of representation learning.
Takeaways & Limitations
The results replace the i.i.d. task assumption with structural conditions describing the target task as covered by source tasks.

Abstract

from arXiv · show

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(Φ\right)}{n_1T} + \frac{k}{n_2}\right)$; here, $Φ$ is the representation function class, $\mathcal{C}\left(Φ\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)$. This result bypasses the $Ω(\frac{1}{T})$ barrier under the i.i.d. task assumption, and can capture the desired property that all $n_1T$ samples from source tasks can be \emph{pooled} together for representation learning. Next, 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.

1 Introduction

The paper asks when representation learning can use all source-task data to improve few-shot target learning, addressing limitations of prior bounds under i.i.d. task assumptions. It analyzes low-dimensional and capacity-constrained representations, including linear and neural-network settings.

Motivation: Representation learning uses related source tasks to learn a shared feature extractor, followed by a simple predictor for the target task.The intended benefit is that a sufficiently good shared representation can make few target samples sufficient.
Problem: Prior bounds require many source tasks and do not improve as the number of samples per source task increases.This conflicts with the expectation that additional source-task data should help representation learning.
Problem: The paper asks which task connections enable representation learning to utilize all source data rather than being limited by an i.i.d. task barrier.The proposed structural conditions describe the target task as being covered by source tasks.
Contributions: The results claim that all n1T source samples can be fully exploited for representation learning under structural task conditions.The paper further argues that capacity control need not rely on explicit low dimensionality.
Scope: The analysis covers low-dimensional linear representations, low-dimensional nonlinear classes, high-dimensional linear representations, and overparametrized neural networks.The paper also treats neural networks among the nonlinear and overparametrized settings.

2 Related Work

Theoretical work on representation learning spans early covering-number analyses, i.i.d.-task sample-complexity bounds, and gradient-based meta-learning guarantees. Concurrent work studies related low-dimensional linear settings, while this paper extends coverage to broader representations and network classes.

Early theory analyzed multitask representation learning using covering numbers.
i.i.d.-task analyses established target-task sample-complexity benefits but exhibit a 1/T concentration rate.
Tripuraneni et al. (2020a) obtained a similar low-dimensional linear result under isotropic inputs, a special case of this paper’s setting.
This paper additionally treats high-dimensional linear representations, general nonlinear representations, and overparametrized neural networks.
Other theoretical lines analyze gradient-based meta-learning for convex losses using online convex optimization, alongside several alternative representation-learning schemes.

3 Notation and Setup

The setup uses multiple source tasks to learn a shared representation and then fits a linear predictor for a data-scarce target task. It formalizes task data, representations, target excess risk, and common-representation assumptions.

T source tasks each provide n1 i.i.d. samples from distributions over X×Y, with X ⊆ R^d and Y ⊆ R.
A representation φ: X → Z maps inputs into Z ⊆ R^k, with separate linear predictors trained on top of the common representation.
The target procedure retains the learned representation and trains a linear predictor using n2 i.i.d. target samples.
The target objective is small population loss, equivalently controlling how much the learned model exceeds the optimal target model in excess risk.
The few-shot regime has n2 much smaller than the sample count required to learn the target task from scratch.
A ground-truth representation φ* and task-specific specializations w*_t are assumed to jointly specify the conditional mean for every task.

4 Low-Dimensional Linear Representations

The low-dimensional linear analysis learns a shared map from source-task data under input-coverage and task-diversity conditions, then applies it to the target task. The resulting guarantees use pooled source data and reduce target sample requirements.

The linear representation class consists of maps x ↦ B^⊤x from R^d to R^k, where k ≪ d.
The source inputs are represented as a linear operator acting jointly on task-specific parameter matrices.
The learned source representation is retained while a linear function is fitted on top for the target task.
The model assumes a shared ground-truth matrix representation, task-specific coefficients, and independent Gaussian noise in the linear regression model.
Covariance dominance requires source covariances to cover the target covariance; the result remains valid when this holds for a constant fraction of source tasks.
Theorem 4.1 shows target learning with O(k) samples versus the O(d) baseline for linear regression, while pooling all n1T source samples bypasses the Ω(1/T) barrier.
The framework also extends to multi-class problems, with a result independent of the number of classes.

5 General Low-Dimensional Representations

The general-representation analysis keeps a low-dimensional feature space but replaces linear maps with a function class whose complexity is measured through data-dependent Gaussian width. Concentration assumptions support a target excess-risk theorem similar to the linear case.

The section assumes a common low-dimensional representation function class Φ while allowing general, potentially nonlinear representations.
The input distribution is shared across source and target tasks, while each task retains its own specialization function.
Gaussian width is used to measure representation-class complexity through a set that depends on the training inputs X.
The framework defines covariance and symmetric covariance between representation functions and establishes that the symmetric covariance is positive semidefinite.
Point-wise and uniform covariance-concentration assumptions control empirical covariances relative to their population counterparts.
Theorem 5.1 gives an expected target excess-risk bound whose representation complexity is captured by the Gaussian width of the data-dependent set.
Removing the probabilistic assumption on the target specialization incurs an additional factor of k in the bound.

6 High-Dimensional Linear Representations

The paper studies capacity-constrained high-dimensional linear representations without an explicit dimensionality limit, using norm constraints to exploit intrinsic low-dimensional structure. Under shared input covariance and coherence between source and target tasks, the resulting target-task bound can use all n1T source samples.

Setup: High-dimensional representations are controlled by norms rather than explicit dimensionality, allowing the analysis to exploit intrinsic representation dimension.The representation class uses maps x → B^⊤x, with norm constraints added to the source and target optimization problems.
Assumptions: The analysis assumes all tasks share the same input covariance, while each task retains its own specialization function.The paper gives image classification across classes as one example of this setting.
Guarantee: Theorem 6.1 provides a high-probability expected-excess-risk guarantee for a target predictor learned from the estimated representation under coherent source and target models.The theorem assumes n1 ≥ n2 and uses nuclear-norm control over the source task model.
Advantage: In the nearly low-dimensional regime, the theorem indicates that all n1T source samples can be exploited for representation learning.The paper treats T as generally O(1) for a well-behaved, nearly low-dimensional source model.
Advantage: When the source predictors are intrinsically low-dimensional, representation learning can improve over learning the target task directly.The paper identifies the intrinsic rank through the source model and compares the resulting bound with a ridge-regression baseline.
Interpretation: The learned representation reweights feature combinations according to source-task importance, while target-task data learn the corresponding coefficients.The paper illustrates this mechanism through a feature-selection analogy and a reweighted ℓ2 constraint.

7 Neural Networks

The paper extends its representation-learning analysis to two-layer ReLU networks, learning a shared hidden representation from source tasks and retraining the output layer for the target task. Under shared task distributions and teacher-network assumptions, the neural-network guarantee improves over direct target-task training and uses all n1T source data.

Model: The neural-network setting uses a two-layer ReLU model whose hidden-layer map serves as the representation and whose output weights specialize to each task.The representation is Φ = {x → (B^⊤x)+}, with square loss and weight decay on source tasks.
Model: Target-task learning fixes the hidden-layer weights and retrains only the output layer.This separates representation learning on source tasks from prediction fitting on the target task.
Assumptions: The theorem assumes a common input distribution, source teacher-network generation, and coherence between the target and source task models.The induced ReLU feature covariance is treated as a kernel over normalized hidden-layer directions.
Guarantee: Theorem 7.1 gives a high-probability expected-excess-risk bound for the target predictor under these neural-network assumptions.The bound includes ζn1,n2 as a lower-order term arising from randomness in the input data.
Comparison: The representation-learning bound is smaller than the direct target-task neural-network baseline because n1T ≥ n2.The comparison is stated for fixed-design error, with the baseline trained using weight decay directly on target data.

8 Conclusion

The paper presents statistical analyses showing that representation learning can use all source-task data for few-shot target learning across both low- and high-dimensional representation classes. It also identifies open questions about how broadly these findings extend and how to optimize representations.

Contributions: The paper reports the first statistical analysis showing that representation learning can fully exploit all source-task data for few-shot target learning.This result is presented for both low-dimensional and high-dimensional representation function classes.
Implications: The results indicate that explicit low dimensionality is not necessary because norm-based capacity control can force classifiers to learn good representations.The conclusion frames this as a supported finding of Sections 6 and 7.
Open questions: Open questions include whether the phenomenon holds across deep-learning models, which other capacity controls apply, and how to optimize for good representations.These questions define the paper’s stated future directions.

A Proof of Theorem 4.1

The proof of Theorem 4.1 combines concentration guarantees for source and target covariances with bounds on the learned predictor’s source and target errors. It uses net arguments and union bounds to obtain high-probability control.

Source-task concentration: Claim A.1 establishes covariance concentration across the source tasks under a sample-size condition involving n1, d, T, and δ.The claim requires n1 ≫ ρ^4(d + log(T/δ)).
Target-task concentration: The proof represents the target design through normalized subgaussian features and applies a covariance-concentration lemma in the reduced 2k-dimensional space.The transformed target rows have zero mean, identity covariance, and ρ^2-subgaussian tails.
Error guarantees: Claims A.3 and A.4 provide high-probability guarantees for source and target training data, respectively, which are combined in the theorem proof.The theorem proof invokes Claims A.1–A.4 and obtains success probability at least 1 − 4δ.
Uniform control: An ε-net over orthonormal matrices controls the random subspaces needed for uniform source-task bounds.The argument combines the net cardinality with union bounds over candidate subspaces.
Theorem conclusion: The final target-risk argument analyzes the excess risk of the learned linear predictor x 7→(B̂ŵT+1)^⊤x.The target predictor is formed by fitting the target-task output weights on top of the learned representation.

B Proof of Theorem 5.1

The proof introduces representation divergence and establishes its positive-semidefinite and covariance-monotonic properties, then uses high-probability concentration and optimality arguments to bound Theorem 5.1’s excess risk.

Representation divergence: The representation divergence D_q(φ, φ′) is defined through covariance and a pseudoinverse Schur-complement expression.It is positive semidefinite and vanishes when the two representations coincide.
Representation divergence: If Λ_q(φ, φ′) ⪰ αΛ_q′(φ, φ′), then D_q(φ, φ′) ⪰ αD_q′(φ, φ′).The proof minimizes a convex quadratic function over an auxiliary vector and transfers the covariance-order relation to divergence.
High-probability control: With probability at least 1 −δ, empirical distributions and concentration conditions from the theorem’s assumptions hold simultaneously.The proof combines several high-probability events using a union bound and does not track constant factors multiplying δ.
High-probability control: The learned representation and task predictors satisfy an optimality-based inequality after substituting the common representation and decomposing the noise contribution.The argument uses independence from target-task samples and notes that the cross term is zero.
Excess-risk bound: The resulting excess-risk bound completes the proof of Theorem 5.1 after taking expectation over the target task’s predictor.The final steps invoke the divergence relation and the preceding concentration bounds.

C.1 Proof Sketch of Theorem 6.1

The proof sketch derives Theorem 6.1 by controlling source and target estimation errors, intrinsic-dimension concentration, and noise terms under nuclear-norm constraints.

Estimator and constraints: The estimator is constrained by a nuclear-norm radius R, with factorized parameters chosen so the constraint remains expressive for admissible predictors.At a global minimum, the factor norms are controlled while representing any predictor with nuclear norm at most R.
Error decomposition: The analysis introduces intrinsic-concentration and estimation-error quantities for source and target tasks.The terms ε_ic,i control intrinsic-dimension concentration, while ε_ee,i control fixed-design estimation error from noisy labels.
Final guarantee: Combining the basic inequality, source and target concentration, and a union bound yields the high-probability guarantee of Theorem 6.1.A term proportional to ∥Σ∥/n_1 is absorbed by ∥Σ∥/n_2 under the assumption n_1 ≥ n_2.
Concentration bounds: The proof bounds the noise term through matrix concentration, with variance controlled by T∥Σ∥ and Tr(Σ) and intrinsic dimension at most T + n.Hanson–Wright and intrinsic matrix Bernstein inequalities provide the stated controls.
Concentration bounds: Intrinsic-dimension concentration applies to projected representations and preserves the whitening distribution’s sub-gaussian norm.The argument uses a matrix deviation inequality and applies it to the representation-transformed design.

D Proof of Theorem 7.1

The proof of Theorem 7.1 transfers the high-dimensional representation-learning guarantee to infinite-dimensional neural-network features by lifting networks to linear regression and matching regularizers.

Infinite-dimensional lifting: Neural networks are lifted to infinite-dimensional linear regression using features φ(x)_b = (b⊤x)+ indexed by directions b on the unit sphere.Network outputs become inner products between signed measures and the infinite feature vector.
Regularizer correspondence: The lifted regularizer is a group ℓ1 regularizer on the vector measure α.Its value is expressed as an integral of the squared norm of α over the unit sphere.
Regularizer correspondence: The finite-neuron and infinite-width formulations have matching regularizer values at corresponding constructions.The proof verifies equality using the factorization and the optimality relation β_j = ∥We_j∥_2.
Applying Theorem 6.1: A finite network need not attain the global minimum of the infinite-width objective because the teacher network’s regularized loss is attainable with finitely many neurons.This suffices for applying Theorem 6.1 to the learner network.
Applying Theorem 6.1: Theorem 6.1 has no dependence on input dimension, including logarithmic terms, so it applies to the infinite-dimensional feature vector.For the ∥·∥_2,1 regularizer, the needed dual operator-norm bound follows from ∥A∥_2,∞ ≤ ∥A∥_2.