Towards Sample-efficient Overparameterized Meta-learning
Authors: Yue Sun
Adhyyan Narang
Halil Ibrahim Gulluk
Samet Oymak
Maryam Fazel
Venue: NeurIPS 2021 Poster (2021)
Keywords: Meta learning
Representation learning
Overparameterization

Abstract: An overarching goal in machine learning is to build a generalizable model with few samples. To this end, overparameterization has been the subject of immense interest to explain the generalization ability of deep nets even when the size of the dataset is smaller than that of the model. While the prior literature focuses on the classical supervised setting, this paper aims to demystify overparameterization for meta-learning. Here we have a sequence of linear-regression tasks and we ask: (1) Given earlier tasks, what is the optimal linear representation of features for a new downstream task? and (2) How many samples do we need to build this representation? This work shows that surprisingly, overparameterization arises as a natural answer to these fundamental meta-learning questions. Specifically, for (1), we first show that learning the optimal representation coincides with the problem of designing a task-aware regularization to promote inductive bias. We leverage this inductive bias to explain how the downstream task actually benefits from overparameterization, in contrast to prior works on few-shot learning. For (2), we develop a theory to explain how feature covariance can implicitly help reduce the sample complexity well below the degrees of freedom and lead to small estimation error. We then integrate these findings to obtain an overall performance guarantee for our meta-learning algorithm. Numerical experiments on real and synthetic data verify our insights on overparameterized meta-learning.

Towards Sample-effccient Overparameterized Meta-learning
Yue Sun University of Washington yuesunQuw.cd edu
Adhyyan Narang University of Washington adhyyanQuv.cm edu
Halil Ibrahim Gulluk
Bogazici University
com
Samet Oymak
Maryam Fazel
University of California, Riverside oymak ucr. edu
University of Washington mf mfazel@ur mazzeeuw.edee edu
Abstract
An overarching goal in machine learning is to build generalizable model with a small number samples. To this end, overparameterizztion has been the subject immense interest to explain the generalization ability of deep nets even when the size of the dataset is smaller than that of the model. While prior literature focuses on the classical supervised setting, this paper aims to demystiffy overparameterization for meta-learning. Here we have a sequence of linear-regression tasks and we ask: (1) Given earlier tasks, what is the optimal linear representation of features for a new downstream task? and (2) How many samples do we need to build this representation? This work shows that surprisingly, overparameterization arises a natural answer to these fundamental meta-learning questions. Specifically, for (1), we first show that learning the optimal representation coincides with the problem of designing task-aware regularization to promote inductive bias. This inductive bias explains how the downstream task actually benefits from overparameterization in contrast to prior works on few-shot learning. For (2), we develop theory to explain how feature covariance can implicitly help reduce the sample complexity well below the degrees of freedom and lead to small estimation error. We then integrate these findings obtaín an overall performance guarantee for our meta- learning algorithm. Numerical experiments on real and synthetic data verify our insights on overparameterized meta-learning.
Introduction
In multitude of machine learning (ML) tasks with limited data, it is crucial to build accurate models in sample-efficient way. Constructing simple yet informative representation of features is a critical component of learning model that generalizes well unseen test set. The field of meta-learning dates back to [8] 4 and addresses this challenge by transferring insights across distinct but related tasks. Usually, the meta-learner first (1) learns feature-representtaioon from previously seen tasks and then (2) uses this representation to succeed at an unseen task. The first phase is called representation learning and the second called few-shot learning. Such information transfer between tasks is the backbone of modern transfer and multitask learning and finds ubiquitous applications in image classification [4], machine translation 6 and reinforcement learning 17
Recent literature in ML theory has posited that overparameterivation can be beneficial to gener- alization in traditional single-task setups for both regression [28 38
3 32 29] and classification 31 30 problems. Empirical literature in deep learning suggests that overparameterization of interest for both phases of meta-learning as well. Deep networks stellar representation learners despite containing many more parameters than the sample size. Additionally, overparameterization
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is observed to be beneficial in the fhw-shot phase for learning in Figure A ResNet-50 network pretrained on Imagenet was utilized to obtain representation of R features for classifica- tion on CIFAR-10. 10. All layers except the final (softmax) layer are frozen and are treated as fixed meat We then train the final layer of the network for the downstream task which yields a linear classifier on pretrained features. The figure plots the effect of increasing R on the test error on CIFAR-10, for different choices of training size 72.. For each choice n2. increasing It beyond 12 is seen to reduce the test-error. These findings are corroborated by [17] (MAML) and [37], who successfully use a transfer learning method that adapts a pre-trained model, with 112980 parameters, to downstream tasks with only 1-5 new training samples.
2.00
trats
Few- Shot Test Error
0.6
Few shot train size 130
Few shot train size 590
Few Shot Test Error
1.75
0.5
1.25
1.00
0.4
0.75
0.50
ghting
0.25
shoordiial Enseretics
10
10
0.00
40
80
100
Representation Dimension
Representation Dimension
Figure 1: Illustration of the benefit of overparameterization in the few-shot phase. (a) Double- descent in transfer learning: dashed lines indicate the location where the number of features R exceed the number of training points; i.e., the transition from under to over aree-prramtterzaation The experimental details are contained in the supplement. (b) Illustration of the benefit of using Weighted Linl.--interpolation in Definition (blue). See Remark T for details and diseussion.
In Figure [b), we consider sequence of linear regression tasks and plot the few-shot error of our proposed projection and weighting based meta-learning algorithm for a fixed few-shot training size, but varying dimensionality of features. The resulting curve looks similar to Figure Ta) and suggests that the observations regarding overparameterriztton for meta-learning in neural networks can, to good extent, be captured by linear models, thus motivating their detailed study. This aligns with trends in recent literature: while deep nets nonlinear, recent advances show that linearized problems such as kernel regression (e.g., via neural tangent kernel (20] 16] 23 34 12) provide a
good proxy to understand some of the theoretical properties of practical overparameterized deep nets.
However, existing analysis of subspace- learning and few-shot phases of linear models have typically focused on the classical underparame- terized regime. These works (see Paragraphs 2-3 of Sec. 1.2) consider the case where representation learning involves projection onto a dimer--iimnsiooall subspace. On the other hand, recent works on double descent shows that an overparameterized interpolator beats PCA-based method. to build upon these results develop a theoretical understanding of overparameteriize meta-learning
meta-learning algorithms for both the representation
1.1 Our contributions
This paper studies meta-learning when each task is linear regression problem, similar in spirit to 36 [2]. In the representation learning phase, the learner is provided with training data from T distinct tasks, with nı training samples per task: using this data, it selects a matrix E Rdx with arbitrary R to obtain linear representation of features via the map - A In the few-shot learning phase, the learner faces a new task with n2 training samples and aims to use the representation A a to aid prediction performance.
We highlight that obtaining the representation consists of two steps: first the learner projects æ onto Rt basis directions, and then performs eigen-weighting of each of these directions, shown in Figure The overarching goal this paper is to propose a scheme to use the knowledge gained from earlier tasks to choose A that minimizes few-shot risk. This goal enables to engage with important questions regarding overparameterization.
'The code for this
is http:///iii////ttttoooooooo///// http:/twwww.....ooouuuouo/aaaaaa

---

Q1: What should the size R and the representation A be to minimize risk at the few-shot phase?
Q2: Can we learn the Rd dimensional representation A with N < Rd samples?
The answers to the questions above will shed light on whether overparamettrization is beneficial in few-shot learning and representation learning respectively. Towards this goal, we make several contributions to the sinite-sample understanding of linear meta-leamiigg under assumptions discussed in Section 2 Our results are obtained for a general data/task model with arbitrary task covariance Eg and feature covariance Ef which allows for rich set of observations.
Optimal representation for few-shot learning. As a stepping stone towards the goal of characteriz- ing few-shot risk for different A, in Section we first consider learning with known covariances Er and Σp respectively (Algorithm T. Compared to projection-onfe representations in previous works (see Paragraphs 2-3 of Sec. [.2). our scheme applies eigen-weighting matrix A to incentivize the optimizer to place higher weight on promising eigen-directions. This eigen- weightiegg procedure has been shown in the single-task case to be extremely crucial to avail the benefit of overparameterization [ [29 [2]: it captures an inductive bias that promotes certain features and demotes others. We show that the importance of eigen- weightingg extends to the multi-task case well.
Canonical task covariance. Our analysis in Section B also reveals that, the optimal subspace and rep- resentation matrix are closed-form functions of the canonical task covariance Σn Σ 12 Στ 2/ 1/2 which captures the feature saliency by summarizing the feature and task distributions.
Representation learning. In practice, task and fea- ture covariances (and hence the canonical covariance) are rarely known apriori. However, we can estimate the principal subspace of the canonical task covari- ance Er (which has degree of freedom (DoF) of Q ((Rd) from data. In Section 4 we first present em- pirical evidence that feature covariance Fr is "pos- itively correlated" with Σy. Then we propose an efficient algorithm based on setthodoffMMoeenne (MoM), and show that the sample complexity of rep- resentation learning is well below ((R)) due to the inductive bias. Our sample complexity bound de- pends on interpretable quantities such as effective
Σ F
Feature covariance
Dr
Task covariance
ΣT
Canonical task covariance
n1
Samples per each earlier task
T
Number of earlier tasks
N
Total sample size T x n1
112
Samples for new task
A
Begen-weiggting matrix
Table 1: Main notation
ranks FF, Er and improves over prior art (e.g., ized to low-rank Σn and identity EP (see Table
(22 36)), even though the prior works were special-
End to end meta-learning guarantee. In Section 5] we consider the generalization of Section 3 where we have only estimates of the covariances instead of perfect knowledge. This leads to an overall meta-learning guarantee in terms of A", NN and n2 and uncovers a bias-variance tradcoff: As N decreases, it becomes more preferable to use a smaller R (more bias, less variance) due to inaccurate estimate of the weak eigen-directions of Ex. In other words, we find that overparameterization is only beneficial for few-shot learning if the quality of representation learning is sufficiently good. This explains why, in practice, increasing the representation dimension may not help reduce few-shot risk beyond certain point (see Fig. 5)_
1.2 Related work
Overparameterized MIL and double-descent The phenomenon of double-descent was first dis- covered by [5]. This paper and subsequent works on this topic B (2.3BB]]
BT 29 [0] emphasize the importance of the right prior (sometimes referred to inductive bias or regularization) to avail the benefits of overparameterization. However, an important question that arises is: where does this prior come from? Our work shows that the prior can come from the insights learned from related previously-seen tasks. Section exxends the ideas in 33 38 to depict how the optimal representation described can be learned from imperfect covariance estimates as well.
Theory for representation learning Recent papers 22
21 36 [5]
propose the theoretical bounds
of representation learning when the tasks lie in an exactly dimensional subspace. 22 21
36
discuss method of moment estimators and [36] [5] discuss matrix factorized formulations. (36] shows
that the number of samples that enable meaningful representation learning is Odr²). 22 2 36)
3

---

Data
Tasks
X22
Rep learning
Feature
x
Feature distribution
X
Xp
B B-Dr
Projection Arbitrary dim
Prior work
Phose Bep learn obeains
XY.1
Yer x/
(x,
()) B.
Xgs
New Dota
Newe tank
B.
Few-shot learning
Eigen-weightiig
Our work
Estimate
Figure 2: (a) Steps of the meta-learning algorithm. (b) Our representation-leaniin algorithm has two steps: projection and eigen-weyd gggen-weighting.. We focus on the use of overparameterization weieraameerrittttn--eiiiiinggg weighting matrix (Def. 3 and compare this with overparameterization with simple projection (no eigen- weighting), and underparamettrrization (for which rigen-weighting has impact and is equivalent to projection). [36] [2 21 15 study underparameterized projections only. To distinguish from eigen-weighting, we will refer to simple projections as subspace-based representations.
assume the features follow standard normal distribution. We define a canonical covariance which handles arbitrary feature and task covariances. We also show that our estimator succeeds with Odd) samples when n4 ~ r, and extend the bound to general covariances with effective rank defined.
Subspace-based meta learning With tasks being low rank, [22 21 36 8 15] do few-shot learning low dimensional space. 39 40
study meta-learning for linear bandits. [26] gives information theoretic lower and upper bounds. 7 proposes subspace-bar based methods for nonlinear problems such as classification. We investigate representation with arbitrary dimension, specifically interested in overparameterized case and show it yields smaller eтror with general task/feature covariances. Related work [15] provides results on overparameterized representation learning, but [15] requires number of samples per pre-training task to obey nı Z d, whereas our results apply as soon as ž 1.
executed, similar to representation learning. The difference is that, the tasks are drawn from a finite set, and number of tasks can be larger than d and not necessarily low rank. [25 27 propose sample complexity bounds of representation learning for mixed linear regression. They can be combined with other structures such binary task vectors and sparse task vectors
Mixed Linear Regression (MLR) In MLR 41 24
multiple linear regression
2 Problem Setup
The problem consider consists of two phases:
Representation learning: Prior tasks are used learn suitable representation to process features.
Few-shot learning: new task learned with a few samples by using the suitable representation.
This section defines the key notations and describes the data generation procedure for the two phases. In summary, we study linear regression tasks, the features and tasks are generated randomly, i.i.d. from their associated distributions DT and Dr, and the two phases share the same feature and task distributions. The setup is summarized Figure a))
2.1 Data generation
Definition (Task and feature distributions) Throughout, DT and Dy denote the distributions of tasks 3r and features Dij respectively. These distributions are subGaussian, zero-mean with corresponding covariance matrices Σx and Σr.
Definition (Data distribution for a single task) Given a specific realization of task vector B ~ Dr. the corresponding label/input distribution (y. x) De is obtained via y where DF and is zero-mean subgaussian noise with variance a

---

Data for Representation Learning (Phase 1), We have T tasks, each with n2 training examples. The task vectors (B.))=1 Rd are drawn i.id. from the distribution Dr. The data for ith task is given by (Vig, Bij j=1 Ltd. Dz.- In total, there are N = T m examples.
Data for Few-Shot Learning (Phase 2). Sample task 3. Dr. Few-shot dataset has m2 examples (yi, 0, iid. D3..
We use representation learning data to learn representation of feature-task distribution, called eigen-weighting matrix A in Def. 3 helow.. The matrix A is passed to few-shot learning stage, helping learn 3, with few data.
2.2 Training in Phase
We will define weighted representation, called eigen- weighting matrix, and show how it is applied for few-shot learning. The matrix is learned during representation learning using the data from the T tasks. Denote X R whose 8th row is Di, and y [y,, -... We interested in studying the weighted 2-norm interpolator defined below for overparameterization regime 2 122.
Definition 3 (Figen-weighting matrix and Weighted norm interpolator) Lei the representa- tion dimension be R. where R is any integer between 1 and d. We define an eigen-weighting matrix A E RdxR and the associated weighted 22-norm interpolator
B^ arg min
||A B1[2
s.t. y = X3 and B E sange_spacelle
B
The solution is equivalent to defining â^ = A A and solving unweighted minimum 2-norm regression with features XA. This corresponds to our few-shot learning problem
arg aig |||||2 s.t. y XAo
from which we obtain BA = AÅs. When there is no confusion, we can replace 3^ with 3. One can easily see that 3 A (X AA) (Ty)ty. We note that Definition 3 is a special case of the weighted ridge regression discussed in [38]. as stated Observation [ An alternative equivalence between min-norm interpolation and ridge regression can be found in 32
Observation 1 Let X RRd and y RR"2, define
31 = lim argming | - yll + +BATAAT)) 3, B column space of A. t11
(2.1)
We have that G 3
3 Canonical Covariance and Optimal Representation
In this section, we ask the simpler question: if the covariances Ey and Ep are known, what is the best choice of A minimize the risk of the interpolator from Definition 3 In general, the covariances are not known; however, the insights from this section help us study the more general Define the risk as the expected error of inferring the label on the few-shot dataset,
case in Section 5
risk(A A, Er, ΣF) = (yy - x B²x Eg( 3) E - B) + o².
(3.1)
The natural choice of optimization for choosing would be choose the weighting that minimizes the eventual risk of the learned interpolator.
A arg min risk(A' ΣT, EF) A
(3.2)
1/2 x and associated task vector / = 1/2 3. This change of variables ensures x² = x²d 33; now, the task covariance in the transformed coordinates takes the form
Since the label y is bilinear in and 8, we introduce whitened features ã = EE
ΣS = Σ1= "
which we call the canonical task covariance; it captures the joint behavior of feature and task covariances Σ,, Er. Below, observe that the risk in Equation (3.I] is invariant to the change of co-ordinates that we have described above i.e does not change when Σ1/² "1/",,,,0 1/2 I,22 fixed and we vary EF and Σr.
5

---

Algorithm Constructing the optimal representation
Require: Projection dimension R, noise level 0, canonical covariance Σx, task covariance ΣF.
1: function COMPUTEOPTIMALREEN EF. Ex, 0, n22)
2: Dp. RR RR COMPUTEREDUCTIONAA Ep, ET,
3: Optimization: Get 0" from (PPTRRE))
4: Map to cigenvalues: Set diagonal A E RRXR with entries RRi (1/0; 1)
5: Lifting and feature whitening: A t U1(EP) 1/2AA return A
6:
7:
function COMPUTEREDUCTIONGC, EF.EF.FET OF)
8:
Get oesepseccooooiition Σn UEU
9:
Principal eigenspace U₁ E R = the first It columns of U.
10:
Top eigenvalues: Set Σ/ = U ΣTU, D UUT ΣpU Equivalent noise level: o + o² + tr(Er) tr(Ef).
11:
12:
return U1, Σp. Ef OR
Observation 2 (Equivalence problem with whitened features) Let data be generated as in Phase 1. Denote Σn > -/ Then Disk(F11> Er, ΣF) = risk((,,
This observation can be easily verified by substituting the change-of-coordinaaee into Equation and evaluating the risk.
3.1
The risk in (3.1) quantifies the quality representation A; however not a manageable function of A that can be straightforwardly optimized. In this subsection, show that it is asymptotically equivalent to a different optimization problem, which can be easily solved by analyzing KKT optimal- ity conditions. Theorem characterizes this equivalence; the COMPUTEREDUCTION subroutine of [ calculates key quantities that are used in specifying the reduction, and the COMPUTEOP- TIMALREP subroutine of Algorithm I Jses the solution of the simpler problem to obtain solution for the original.
Algorithm
Assumption (Bounded feature covariance) There exist positive constants Emins Emax such that Ep is lower/upper bounded as follows: 0 < Emin 3 Ep = Emax
Assumption (Joint diagonalizability) EF and Σx diagonal matrices
Assumption (Double asymptotic regime) We let the dimensions and the sample size grow as d, R. 122 at fixed ratios R = d/nz and = R/To..
Assumption 4 The joint empirical distribution of the eigenvalues of AR and ΣR is given by the average of Dirac 8's: El & converges to a fixed distribution d - sc.
With these assumptions, we can derive an analytical expression to quantify the risk representation A. We will then optimize this analytic expression obtain formula for the optimal representation.
Theorem (Asymptotic risk equivalence) Suppose Assumptions unique number obeying 112 E (EA?) Define O E R with entries O I+EA?
4 hold. Let & > 0 be the CA²
and calculate SR. an using the COMPUTEREDUCTIION procedure of Algorithmm analytic risk formula
Then, define the
1
FR f(0, 1
72 Σ
[1
2R 01013 1)0
(3.3)
n22
00
We have that
lim f(0, R n2) = lim risk ΣΙ 1/2 A, Er, EF)
(3.4)
n2-+00
The proof of Theorem T appllis the convex Gaussian Min-max Theorem (CGMT) in 35 and can be found in the Appendix B.2. We show that as dimension grows, the distribution of the estimator converges a Gaussian distribution and we can calculate the expectation of risk.
Thii equivalent to the more general scenario where Σr and Σr are jointly diagonalizable.

---

Theorem 1 provides us with a closed-form risk for any linear representation. Now, one can solve for the optimal representation by computing (EPTRRP) below. In order to do this, we propose an algorithm for the optimization problem in Appendix B.5 via study of the KKT conditions for the problem
R
= -arg min f(0, Σr, EF); s.t. 0 S 0 < 1,
0, = 712
(OPT-REP)
1=1
The optimal representation R = ((1/0: - 1)
The subroutine COMPUTEOPTIMALLN in Algorithm T summarizes this procedure.
2.00
1.50
ED corin WiriOO
Remark Thm. 1 states that risk E 1/,1,,,, Σr. Ex) can
Sho. Test
1.25
be arbitrarily bell-apprxximated by f EB. n2) if n2 is sufficiently large. In Fig. b)), we EF I 1000 Er
0.75
diag(Izv. 0. n2 = 40. The curves in Fig b) are the finite dimensional approximation of (LHS of (3.4); the dots are empirical approximations of the risk (RHS of (3.4). We tested two cases when A is the optimal or projection matrix with no weighting. Our theorem is corroborated by the observation that the dots and curves are visibly very close. The approximation is already accurate for the finite dimensional problem with just f22 40.
0.50
0.00
20
40 60
100
Representation Dimension
Figure 3: Theoretical risk of optimal representation. ΣF 1100. Σσ diag (oo) n22 = 40.
The benefit of overparameteriizatoo. Theorem I leads an optimal eigen-weighting strategy via asymptotic analysis.
In Figure we plot the effect the risk of increasing R for different shapes of task covariance; the parameter e controls how spiked Σy is, with smaller value for indicating increased spiked- ness. For the underparameterized problem, the weighting does not have any impact on the risk. In the overparameterized regime, the eigen- seighwee learner achieves lower few-shot error than its unweighted (A I) counterpart, showing that eigen-weighting becomes critical.
The eigen-wert weighting procedure can introduce inductive bias during few-shot learning, and helps explain how optimal representation minimizing the few-shot risk can be overparameterized with R > n2. We note that, an R dimensional representation can be recovered by a dimensional representation matrix of rank R. thus the underparameteriize case can never beat d dimensional case in theory. The error with optimal eigen-weighting in overparameterized regime is smaller than the respective underparameterizzed counterpart. The error is lower with smaller It implies that, while Σr gets closer low-rank, the excess error caused by choosing small dimension R (equal to the gap R o² in Algo I is not as significant.
Low dimensional representations zero out features and cause bias. By contrast, when Σn E Rdxd is not low rank, every feature contributes to learning with the importance of the features reflected by the weights. This viewpoint is in similar spirit to that of [19] where the authors devise a misspecified linear regression demonstrate the benefits of overparameterization. Our algorithm allows arbitrary representation dimension It and cigen-weighting.
4 Representation Learning
In this section, we will show how to estimate the useful distribution in representation learning phase that enables us to calculate higenweiighting matrix A". Note that A depends on the canonical covariance Σn 21/E", E/ Learning the R-dimensional principal subspace of En enables us to calculate A Denote this subspace by Sr.
'In Sec. the constraint is 0 < 0 < d-n2 & for robustness concerns.
'In the algorithm, E = 1 and AR. (1/07 -07-1 5 'We also need to estimate EF for whitening. Estimating Er is rather easy and incurs smaller emror compared Er. The analysis is provided in the first part of Appendix B.
1) 1)- because cA" for any constant gives the same A
7

---

Subspace estimation vs. inductive bias. The subspace based representation Sr has degrees of freedom= Rd. When Σr is exactly rank R and features are whitened. [36] provides a sample- complexity lower bound of Q Rd) examples and gives an algorithm achieving O (R samples. However, in practice, deep nets learn good representations despite overparameterizztion In this section, recalling our Q2, we argue that the inductive bias of the feature distribution can implicitly accelerate learning the canonical covariance. This differentiates our results from most prior works
such as [22 21 36]
two aspects:
1. Rather than focusing on low dimensional subspace and assuming N 2 Rd, we can estimate ΣT or ST in the overparameterized regime N Rd.
2. Rather than assuming whitened features E5 = I and achieving a sample complexity of R our learning guarantee holds for arbitrary covariance matrices Ep, Σr. The sample complexity depends on effective rank and can be arbitrarily smaller than DoF, We showcase our bounds via spiked covariance setting in Example bellow.
For learning Ey or its subspace Sr, we investigate the method-of-momest (MoM) estimator.
Definition 4 (MoM Estimator) For 1 I S T, define b,, 2n 2n
Σ}= Vij ,,
Ri j=m /241 Rij. Set
T
M =-= Σ (b;, 10 + b,,b
im1
The expectation of M is equal to M = EFFTTE.
Inductive bias in representation learning: Recall that canonical covariance En ///EE/1 the attribute of interest. However, feature covariance D/' term implicitly modulates the estimation procedure because the population MoM is not Σn but M = Ey E//² For instance, when estimating the principle canonical subspace Sr, the degree of alignment between Er and Ey can make or break the estimation procedure: If Fr and Σn have well-aligned principal subspaces, ST will be easier to estimate since Ep will amplify the Sr direction within M.
We verify the inductive bias practical image dataset, reported in Appendix A. We assessed correlation coefficient between covariances ΣT, Er via the aenonicall-feturee alignment score defined as the correlation coefficient
Ep. Er)
trace MM)
p P ΣT)
|E 1L 1E EE || Σril
Observe that, the MoM estimator M naturally shows up in the alignment definition because the inner product Σ,, E is equal to trace(M). This further supports our inductive bias intuition. As reference, we compared it to canonical-identity alignment defined trace(Err)
<dl Erlr (replacing EF with I). The canonical-featum alignment score is higher than the canonical-identity alignment score. This significant score difference exemplifies how Σp and Σn can synergistically align with each other (inductive bias). This alignment helps our MoM estimator defined below, illustrated by Example (spiked covariance).
In the following subsections, let N n refer to the total tasks in representation-leamiin phase. Let r tr(Ex), FT tr (rE)), and ir -tr(E)) Define the approximate low-rankness measure of feature covariance by
SF min s'p, s.t. S/p E (l,..,, d}, sr/d 2 dipt1
We have two results for this estimator.
1. Generally, we can estimate M with ((rrff) samples.
Let 72 2 8T, we can estimate M with O(sFrr) samples.
Paper [36] has sample complexity (dr²)) (r is exact rank). Our sample complexity is O(rer?).
TF, FT can be seen as effective ranks and our bounds are always smaller than (36]. We will discuss
later in Example]] | Our second result says when which is proven lower bound in [36].
sr, our sample complexity achieves the (dr)
'The (SF 1)-th eigenvalue is smaller than sF /dd Note the top eigenvalue L.

---

feature cov
Σ = I, Mi diag(Iur: .))
Er
ΣT diag I d-)
diag
Sp 6p d-sr
estimator
sample N
sample
error
sample N
sample
error
MoM
dsf
[ds. Frrj
MoM
der
ST
(8r/m)) )
rper
Pr
(rr/n1)
Table 2: Right side: Sample complexity and error of MoM estimators, SF (8y) is the dimension the principal eigenspace of the feature (task) covariance. FF 8 + (r(d sF), Pr 8T tr sr) are the effective ranks. Left side: This is the well-studied setting of identity feature covariance and low-rank task covariance. Our bound in the second row is the first result to achieve optimal sample complexity of ((dST) ) (cf. (36 (2)).
Theorem 2
Let data be generated in Phase 1. Assume Let n be a even number. Then with probability at least N ~100
[rll,
Er
for normalization
|M -MII S (fT +
TF
PT
T
2. Assume T 2 sp. If fr + a², then with probability at least CT
IM - MI S ((Tr - -0²)/n1) 1/2
Denote the top-R principal subspaces of M, M by Mapy Map and assume the eigen-gap condition (R ARt1 (M) M M|) Then a direct application of Davis-Kahan Theorem [3
bounds the subspace angle as follows
angle MMpp Mmp) S MM MII/(AR(M)) (R))
Estimating eigenspace of canonical covariance. Note that if EF and Σr are aligned, (e.g. Example below with 8F 8T = R), then Mop ST is exactly the principal subspace Σn. Theorem for the principal subspace Σr. Note that, such alignment is and more general requirement compared to related works which require whitened features [36] (22]
1.4
1.3
2 indeed gives estimation error
1.1
1.0
0.9
0.7
0.00
0.50
1.00
1.50
2.00
Example 1 (Spiked ΣT, Aligned principal subspaces)
Figure 4: Error of MoM estimator
Suppose the spectra of F and Σn are bimodal as follows Er diag( sgn Lp Id-sf), ΣT diag(Issy Lr s- Set statistical error Errr,N == Vrā.r/N /rr/T. When LF,FF 1, 8p 2 ST, the recovery
error of EEr and its principal subspace ST are bounded as
angle( (Mop: ST) S EErr,N + Eper and || - ΣT S Errt,N + LETT.
The estimation errors for ΣT, ST are controlled in terms of the effective ranks and the spectrum tails LF, IT. Typically 8F8T Z nh so Vržrr/N F/N term dominates the statistical error in practice. In Fig. 4 we plot the error of estimating M (whose principal subspace coincides with ΣT). ΣF diag Too, (70), En = diag(Ian O70). T = 100. We can see that the error increase with u.
Robustness of Optimal Representation and Overall Meta-Learning Bound
we described the algorithm for computing the optimal representation with known distributions of features and tasks. In Section we proposed the MoM estimator in representation learning phase to estimate the unknown covariance matrices. In this section, we study the algorithm's behaviors when calculate A using the estimated canonical covariance, rather than the full- information setting of Section
In Section 3
"This is simply equivalent scaling which does not affect the normalized error || - MM the appendix define S = max([] Er I Er |} and prove the theorem for general S.

---

Armed with the provably reliable estimators of Section 4 we can replace Σy and E5 in Algorithm | with our estimators. In this section, we inquire: how does the estimation error in covariance--ssimation in representation learning stage affect the downstream few-shot learning risk? That says, we are interested in (A, Σr; Er
risk A Σr; Σr).
Let us replace the constraint in (OPT-REP) by 2 1 This changes the "optimization" B2
step in Algorithm [ Theorem does not require explicit computation of the optimal representation by enforcing B. Instead, we use the robustness of such a representation (due to its well-conditioned nature) to deduce its stability. That said, for practical computation of optimal representation, simply use Algorithm| [
We can then evaluate @ after-the-fact as the minimum singular value of this representation to apply Theorem
3
without assuming an explicit
Let Aa (R) COMPUTEOPTIMALLRR R, Ep, M, n2)) denote the estimated optimal representa- tion and Ag( = COMPUTEOPTIMAL
E,, Σr, a. n2)) denote the true optimal representa- tion. which cannot be accessed in practice. Below we present the bound of the whole meta-learning algorithm. It shows that a bounded error in representation learning leads to bounded increase on the downstream few-shot learning risk, thus quantifying the robustness of few-shot learning to errors in covariance estimates.
Theorem 3 Let (e(R), (2) be defined above, and TF = tr(EF), ST tr(ET), tr tr(ET). The risk of meta-learning algorithm satisfies
risk( (R) Er. Er) - risk (R), Σr. Ep)
n2
(iT (iT +
TF 0²
+
IT
d(R )2 RB)
N
T
Notice that as the number of previous tasks T and total representation-leurinng samples N observed increases, the risk of the estimated Ag (t) approaches that of the optimal (R)
2.00
1.75-
(R) as we expect. The result only applies to the overpa- rameterized regime of interest R > ng. The expression of risk in the underparameterized case is different, and cov- ered by the second case of Equation(4.44 (4.4) in (38) We plot it in Fig (b) on the left side of the peak as a comparison.
1.50
1.25
1.00
57g- 0.75
Few 40
0.50
0.25
0.00
Risk with respect to PCA level R. In Fig. 5 we plot the сτrоr of the whole meta-learning algorithm. We simu- late representation learning and get M, use it to compute and plot the theoretical downstream risk (experiments match, see Fig. (b)). Mainly, we compare the behavior of Theorem 3 with different When grows, we search A in larger space. The optimal A in feasible subset is always no better than searching
50
60
70
80
90 100
Representation Dimension
Figure 5: End to end learning guarantees.
d 100, n2 40, 200. Er (Iz0. 0.05- Isu), Σ; F I100-
larger space, thus the risk decreases with R increasing. At the same time, representation learning error increases with R since need to fit a matrix in larger space. In essence, this result provides a theoretical justification on a sweet-spot for the optimal representation. d = R is optimal when N oc, i.e., representation learning error is 0. As N decreases, there is a tradeoff between learning error and truncating small eigenvalues. Thus choosing R adaptively with N can strike the right bias- variance tradeoff between the excess risk (variance) and the risk due to suboptimal representation.
6 Conclusion
In this paper, we study the sample efficiency of meta-learning with linear representations. We show that the optimal representation is typically overparameterized and outperforms subspace-based representations for general data distributions. We refine the sample complexity analysis for learning arbitrary distributions and show the importance of inductive bias of feature and task. Finally we provide an end-to-end bound for the meta-learning algorithm showing the tradeoff of choosing larger representation dimension v.s. robustness against representation learning error.
$ Note that 6 of RX gives the exact value of risk (A' Σr, ΣF) so we have an end to end error guarantec.
9The bracketed expression applies first conclusion of Theorem One can plug in the second as well.
10

---

Acknowledgements
This work supported in part by the TRIPODS II grant DMS 2023166, NSF TRIPODS CCF 1740551, NSF CCF-2046816, NSF CCF 2007036, Army Research Office grant W91 1911NF-21---0011, and the Moorthy Professorship at UW ECE.
References
[1] Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Convex multi-task feature learning. Machine learning, 73(3):243-235 272, 2008
[2] Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. Efficient representations for lifelong learning and autoencoding. In Conference on Learning Theory, pages 191-210 2015.
[3] Peter L Bartlett, Philip Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
[4] Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-198, 2000.
[5] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias variance of Sciences, (1(3)):15449-1855555 2019.
bias-variance trade-off. Proceedings of the National Academy
[6] Ondřej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Baint-Amand, et al. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the ninth workshop on statistical machine translation, pages 12-58, 2014.
[7] Quentin Bouniot, levgen Redko, Romaric Audigier, Angélique Loesch, Yevhenii Zotkin, and Amaury Habrard. Towards better understanding meta-learning methods through multi-task representation learning theory. arXiv preprint arXiv:2010.01992, 2020.
[8] Rich Caruana. Multitask learning, Machine learning, 28(1):41-75: 1997.
[9] Giovanni Cavallanti, Nicolo Cesa-Bianchi, and Claudio Gentile. Linear algorithms for online multitask classification. The Journal of Machine Learning Research, 11:2901-2934, 2010.
[10] Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overparameterization model compression: From double descent to pruning neural networks. arXiv preprint 20X.xx:002.087770 2020.
[11] Sitan Chen, Jerry Li, and Zhao Song. Learning mixtures of linear regressions in subexponential time via fourier moments. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 587-600, 2020.
[12] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. arXiv preprint /rXiv:/8/2.07000 2018.
[13] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[14] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li,, and Li Fei-Fei. Imagenet: A large- scale hierarchical image datahase. In 2009 IEEE conference computer vision and pattern recognition, pages 248-255. leee, 2009.
[15] Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002. 09434, 2020.
[16] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizee neural networks. In International Conference on Learning Representations, 2018.
11

---

[17] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostee meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1 1126-11 1135, 2017.
[18] Halil Ibrahim Gulluk, Yue Sun, Samet Oymak, and Maryam Fazel. Sample efficient subspace- based representations for nonlinear meta- leaanne...ing.. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2021.
IEEE,
[19] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint NXXiv:9903008660 2019.
[20] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[21] Weihao Kong, Raghav Somani, Sham Kakade, and Sewoong Oh. Robust meta-learning for mixed linear regression with small batches. arXiv preprint arXiv:2006. 09702, 2020.
[22] Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. arXiv preprint arXiv:2002.08930 2020.
[23] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32:8572-8583, 2019.
[24] Yuanzhi and Yingyu Liang. Learning mixtures of linear regressions with nearly optimal complexity. In Conference On Learning Theory, pages 1125-1144, 2018
[25] Karim Lounici, Massimiliano Pontil, Sara Van De Geer, Alexandre B Tsybakov, al. Oracle inequalities and optimal inference under group sparsity. The annals of statistics, 3944)21644 2204, 2011.
[26] James Lucas, Mengye Ren, Irene Kameni, Toniann Pitassi, and Richard Zemel. Theoretical bounds on estimation error for meta-learning. arXiv preprint 2rXiv:2010.07140, 2020.
[27] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. The Journal of Machine Learning Research, 17(1):2853-285) 2016.
[28] Song Mei and Andrea Montanari. The generalization error random features regression: Precise asymptotics and double descent curve. arXiv preprint 100.0:190. 2019.
[29] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint arXiv: 1911.11544, 2019.
[30] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: -igh--inensional asymptotics in the overparametrized regime, 2020.
[31] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification regression in overparameterized regimes: Does the loss function matter? arXiv preprint arXiv:2005.0805. 2020.
[32] Vidya Muthukumar, Kailas Vodrahalli, and Anant Sahai. Harmless interpolation of noisy data in regression. CORR, abs/1903.099 2019.
[33] Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint w:Xiv:2003.0189) 2020.
[34] Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. Generalization guaran- tees for neural networks via harnessing the low-rank structure of the jacobian. ICMI. Workshop on Understanding and Improving Generalization in Deep Learning, 2019.
12

---

[35] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Lasso with non-linear measurements equivalent to one with linear measurements. Advances in Neural Information Processing Systems, 28:3420-3428, 2015.
[36] Nilesh Tripuraneni, Chi Jin, and Michael I Jordan. Provable meta-learning of linear representa- tions. arXiv preprini arXiv:2002.1168% 2020.
[37] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, koray kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[38] Denny Wu and Ji Xu. On the optimal weighted Eg regularization in overparameterized linear regression, 2020.
[39] Jiaqi Yang, Wei Hu, Jason D Lee, and Simon S Du. Provable benefits of representation learning linear bandits. arXiv preprint arXiv:2010.0653) 2020.
[40] Jiaqi Yang, Wei Hu, Jason D Lee, and Simon S Du. Impact of representation learning in linear bandits. In International Conference on Learning Representations, 2021.
[41] Kai Zhong, Prateek Jain, and Inderjit S Dhillon. Mixed linear regression with multiple compo- nents. In Advances in neural information processing systems, pages 2190-2198, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In supplementary file
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect the random seed after running experi-
ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "mPponQObQAc", "reviewer": "Reviewer_gmou", "summary": "This paper studies the role of overparameterization in meta representation learning.\n\nMeta-learning studies how to learn from previous tasks to adapt quickly to new ones, while overparameterization studies the settings where the number of training points is smaller than the number of features. Recent works studied the generalization properties of meta-learning a linear representation but did not focus on the overparameterized setting, where the number of training samples per task is lower than the dimension of the meta-learned representation.\n\nThis work presents asymptotic results on the expected risk in the overparameterized regime. Furthermore they propose an algorithm to learn a linear representation together with sample complexity bounds. They also provide some empirical results validating their analysis.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I anticipate that I am not very familiar with theoretical results in meta representation learning and overparameterization. I apologize if I misunderstood crucial parts of the work and in that case I am willing to increase the score after the discussion.\n\n1. I found the paper hard to read. Some crucial symbols are introduced without definition or are inconsistent. Theorems and algorithms are poorly explained. Contributions and most of the experiments are also unclear. \n\n2. I do not think Theorem 1 (crucial part of the work) is meaningful. It is also not explained well. Usually an upper bound on the risk is provided and then limits are taken. Theorem 1 seems to skip the first part. Furthermore, with fixed $\\kappa = \\frac{R}{n_{2}}$ . if you take the limit for $n_2 \\to \\infty$ in 3.4  also $R \\to \\infty$  and the left hand side of (3.4) is 0 if the risk is bounded. Also it seems that the matrices will have infinite rows and columns in the limit.\n\n3. The authors do not mention [A, B] which also provide learning guarantees with meta-learning of a linear representation.\n\n#### **Final Score**\n4. I am giving this paper a 4. I think the problem that the authors are tackling is potentially interesting. Overparameterization probably plays a big role also in meta-learning. However I think the quality of the work is far from being sufficient for acceptance.\n\n#### **Additional comments**\n\n5. Close to line 37: how is training on cifar 10 in Figure 1(a) done? only the last layer is trained or all the weights are fine-tuned? I would write this here.\n\n6. line 62: I think saying that the linear representation mapping throws away features is wrong. It just weighs them.\n\n7. I found the contributions section quite heavy in terms of loosely defined notation and references to future sections.\n\n8. Line 244-247 are not clear\n\n9. Line 52: I think the term “underparametrized” is used in the wrong way here. The model the related work studies has input dimension higher than feature dimension $d < R$ while $R$ could still be (and often is) higher than the number of samples per task $n_2$, which would make it overparameterized in the sense meant by the authors.\n\n10. Observation 2 is not proved anywhere (not even in the supplementary).\n\n#### **Update**\nAfter the discussing with authors and reviewers I better understand the purpose of Theorem 1. However I am still unsure on the significance of the presented results and I still think the paper lacks clarity. I increased my score from 4 to 5.\n\n#### **References**\n\n[A] G. Denevi, C. Ciliberto, D. Stamos, and M. Pontil. Incremental learning-to-learn with statistical guarantees. In Proc. 34th Conference on Uncertainty in Artificial Intelligence (UAI), 2018.\n\n[B] G. Denevi, D. Stamos, C. Ciliberto, and M. Pontil. Online-within-online meta-learning. In Advances in Neural Information Processing Systems, pages 13089–13099, 2019.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss limitations in the conclusion section. I can not tell if the list is exaustive.\n\nThe work does not have potential negative societal impact since it is mostly theoretical.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "SFBuKvdqILo", "reviewer": "Reviewer_PuM5", "summary": "This paper studies overparametrized representation learning in meta-learning, i.e. representation dimensionality (R) is larger than number of samples ($n_2$) per task. It does so in the setting of linear representations, but goes beyond existing analyses that typically assume that the covariance of task regressors to be low rank and restrict representation dimensionality to be small. The paper characterizes the optimal representation for every dimensionality R (in an asymptotic regime), observes a double descent phenomenon w.r.t. R in the performance of the representation on test tasks, also concludes that the optimal dimensionality can be overparametrized in many cases. It then analyzes the sample complexity of learning such a representation with finite train tasks samples, and finds that choosing R adaptively with number of samples can strike a balance between bias and variance of the representation. An important phenomenon of alignment of feature covariance and task covariance is introduced and its effect on sample complexity and optimal dimensionality is studied. Experiments on simulated data verify some of findings and the presence of the alignment is observed on some real datasets (MNIST, CIFAR).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThis paper meaningfully extends the linear representation learning by studying the role and need for high dimensionality of representations when the features and tasks are not exactly low rank, unlike recent analyses that make such a low rank assumption. It makes good use of previously employed asymptotic analysis for regularized linear regression. I found the discussion and comparison to previous work adequate. A relevant work is [1] that also analyzes high dimensional representations for (overparametrized) meta-learning, but relies on gradient dynamics to automatically uncover the underlying subspace structure.\n\nQuality:\n\nThe results seem believable from a skim over the proofs. I didn't verify all the details, especially for the closed form expression in Theorem 1. Technical claims are supported by proofs in the appendix and with simulation experiments in some places.\n\nClarity:\n\nI found the paper mostly clearly written and easy to follow. I found the discussion before Theorem 2 a bit clunky (line 260-276), since $s_F$ and $s_T$ are only defined in Table 2. I would encourage the authors to rework this part a bit.\n\nSignificance:\n\nThe paper analyzes more general and realistic settings than those analyzed in previous work on meta-learning linear representations and explores the benefit of covariance alignment in sample complexity. The main contribution is theoretical and it does not necessarily provide any practical algorithmic suggestions. It needs to make simplifying assumptions in some cases, like asymptotic analysis, eigenspace alignment and linear representations, but these do not significantly dilute the conceptual contribution in my opinion.\n\n\nAdditional comments:\n\n- L84: Is DoF degree of freedom? not defined anywhere\n\n- L194: p=R?\n\n- L242,243: Something seems off in the alignment metrics. canonical-identity alignment is equal to 1/d in the way it is defined currently\n\n\n\n---------------------------------------------------------------------------------------------------------------------\n**Post rebuttal**: I thank the authors for their many responses to reviewer concerns. After reading everything and the reviewer discussions, I am inclined to retain my recommendation of accept (7). I think providing some more details and highlighting the conclusions from Fig 1(a) and 1(b) even later in the paper will help. One of the major concerns raised by other reviewers (which I agree with) is the clarity of the paper. More specifically, Theorem 1 can afford to be written much more clearly, especially the part about how the limit of $n\\_2\\rightarrow\\infty$ is taken. The author response provides a lot of clarification in this regard, but I think it can be improved even further, e.g. the statement \"the joint empirical distribution $\\frac{1}{R} \\sum_{i=1}^{R} \\delta_{\\Lambda_{R_i}, \\tilde{\\Sigma}^R_{T_i}}$ converges to a fixed distribution\" seems very important but is inadequately discussed. Many readers of this paper will not be familiar with the kind of asymptotic results and analyses presented in this paper, so it will help to clearly explain how the limits are taken, why an asymptotic analysis is needed, and what the results mean for the practical case of finite $d,n\\_2,R$. Also, some of the empirical verifications with CIFAR-10 and MNIST and a good suggestion made by another reviewer in the discussions was to extend this analysis to more few-shot learning based datasets. Personally I think that these changes are not too drastic to change my opinions about the paper.\n\n\n[1] N. Saunshi, Y. Zhang, M. Khodak, S. Arora. ICML 2020. A Sample Complexity Separation between Non-Convex and Convex\nMeta-Learning.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the work are discussed in Section 6.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "OLWlezaOyhK", "reviewer": "Reviewer_czkt", "summary": "This paper presents an analysis of the role of representation width when learning a shared feature extractor across multiple tasks. The authors argue that wider representations improve transfer, even when only a small number of labelled examples are accessible to fine-tune the last linear layer of a neural network. Their theoretical analysis focuses on linear regression with a linear feature extractor, with most experiments also on this setting.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe message of the paper is interesting and relevant to the few-shot learning community. In particular, a thorough study of width in meta-learning is novel and welcome. \n\nWeaknesses:\n\n- Simplified analytical setting: the authors only consider linear regression with a shared, linear feature extractor. Although linear regression has been used in prior work, some more recent theoretical works have shifted towards the more general convex (and sometimes non-convex) setting. See for example [1, 2]. Since linear regression induces a quadratic optimization problem, I am concerned that the proposed approach won't be easily extended to those settings.\n- Lack of real-world validation: On top of the simplified analytical setting, theoretical insights are never validated on real-world datasets. Hence, I wonder if those insights carry over to real-world applications. Taking classification tasks as an example, it is well-known that nearest-neighbor classifiers (like ProtoNet) tend to work better with lower-dimensional representations, while SVMs work best with larger representations.\n- As a minor remark, I think this paper would benefit from a reference to R2D2 [3] who obtain excellent classification results with a deep feature extractor and ridge regression classifier (but don't say anything about representation width). Their method could also be used to address the lack of real-world validation.\n\nReferences:\n\n[1] \"A Theoretical Analysis of the Number of Shots in Few-Shot Learning\", Cao et al., ICLR 2020.\n\n[2] \"On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms\", Fallah et al., AISTATS 2020.\n\n[3] \"Meta-learning with differentiable closed-form solvers\", Bertinetto et al., ICLR 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1 paragraph on limitations, none on societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "5elXOhbR8hi", "reviewer": "Reviewer_kYDu", "summary": "This paper considers the representation learning for multi-task linear regression problem in the setting with arbitrary feature covariance, arbitrary task covariance, and arbitrary representation dimension. In this setting, it aims to address two questions: (1) given a set of $T$ linear regression tasks with $N$ total samples, what is the optimal representation $\\Lambda \\in \\mathbb{R}^{d\\times R}$ for a downstream few-shot linear regression task? and (2) what is the sample complexity for finding this representation? To address these questions, the authors find a closed-form solution for the optimal representation when the fine-tuning phase involves an eigen-weighting procedure, which they argue introduces an inductive bias that enables few-shot success. They show that the key to estimating this optimal representation is estimating the \"canonical task covariance\", which they show necessitates a number of samples growing with the effective ranks (traces) of the task and feature covariances, rather than the ambient dimension $d$. The authors also provide an overall risk bound that shows it is preferable to have smaller $R$ for smaller $N$.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The introduction is mostly clear and does a great job of motivating the linear setting.\n\n2. To the best of my knowledge, arbitrary task covariance had not yet been considered for linear multi-task representation learning, so the dependence of the excess risk on the canonical task covariance is a new result.\n\n3. Showing that the sample complexity grows with the effective ranks of the covariance matrices rather than the ambient dimension is a nice result.\n\n4. The analysis is rigorous and certainly non-trivial. The proofs are correct as far as I could tell.\n\n5. Understanding over-parameterization in representation learning is a highly relevant problem.\n\nWeaknesses/Questions:\n\n1. After the introduction I found this paper very difficult to understand, which leaves me with numerous questions about its contributions (see below). The writing can be significantly improved, both in terms of fixing typos and more importantly, giving more simple and clear explanations of the results. I found the interpretations of Theorems 1 and 3 especially lacking, since they involve highly non-intuitive expressions yet very little explanation was given of them.\n\n2. Regarding Theorem 1 and eigen-weighting: what is the point of the eigen-weighting? How do the results compare to the case in which standard linear regression is executed in the few-shot phase instead? Do any insights from eigen-weighting generalize beyond linear models? I get that eigen-weighting is itself an inductive bias, but I am not sure how this inductive bias helps... right now it seems to only complicate the problem, making the optimal representation (in Theorem 1) non-intuitive and only computable in closed form under that restrictive assumptions that $n_2 \\rightarrow \\infty$ and the feature and task covariances are simultaneously diagonalizable.\n\n3. Regarding Theorem 2 and surrounding text: $s_F$ (and $s_T$) should be defined outside of the Theorem 2 so that it is clear what they are when you refer to them multiple times outside of the theorem. There should also be some accompanying intuition for this definition. It is also not clear why the relationships between $r_F$ and $s_F$, and $r_T$ and $s_T$ hold in Table 2.  Further, you have introduced $\\iota$ in Example 1, but it does not appear in the bound which does not make sense. \n\n4. Regarding Theorem 3: how does $\\theta_{-}$ scale, and how can $\\Lambda_{\\theta_{-}}(R)$ be computed (do you compute the representation using the constraint that its minimum singular value is lower bounded by $\\theta_{-}$, or is $\\theta_{-}$ evaluated after the fact)? It is not clear that \"representation learning error increases with $R$\" from the result. Also, the risk becomes negative when $R > n_2$, is there a missing assumption?\n\n5. I am doubtful of the novelty of many of the contributions of this paper compared to [1], which also provides bounds for the linear representation learning + few-shot learning problem in the over-parameterized setting with arbitrary feature covariance, and obtain a bound that depends on effective rank, not dimension (see Theorem 6). The authors do not mention this result in the current work.\n\n6. It is repeatedly stated that [2] gives a sample complexity of $dr^2$, but this is only true under the assumption that the minimum singular value of the task covariance matrix is $O(1/r)$. If it is $O(1)$, then [2] achieves $dr$. The authors need to mention this in the update and do a fair comparison with clear assumptions on the task covariance matrix.\n\nOverall: This paper is promising, but at this point I have too many questions and concerns to recommend acceptance.\n\n[1] Du et al. Few-Shot Learning via Learning the Representation, Provably. 2020.\n[2] Tripuraneni et al. Provable Meta-Learning of Linear Representations. 2020.\n\n----------------------\n\nPost-rebuttal: I thank the authors for their thorough response. They have helped me to better understand the results of the paper, and also resolved my concerns about comparisons with [1] and [2]. I believe this is an important result, but the clarity of the paper can be significantly improved in order for the result to be fully appreciated. I have raised my score to a 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies overparameterization for meta-learning in the setting of linear-regression tasks. It answers the questions about the optimal linear representation of features for a new downstream task and the number of samples needed to build this representation. The reviewers are quite diverse at the beginning and raised a number of questions, with one of the main criticisms being on the clarity of Theorem 1. The authors have done a good job at replying the reviews, and the reviewers also have done a good job at discussing the rebuttal. Finally, the originally negative reviewers are able to converge to the borderline and the positive reviewers maintained their scores. I propose acceptance of this paper due to the important contribution of demonstrating overparameterization to meta learning. However, I highly recommend the authors to take the comments from the reviewers and revise the paper carefully for its final version. It would make the paper even stronger if the revision can somehow address the following question raised in the discussion: it is expected the paper can provide either stronger empirical verifications (MNIST and CIFAR100 in the appendix are non-standard in FSL) or for theory beyond linear regression case.
Decision: Accept (Poster)