Statistically and Computationally Efficient Linear Meta-representation Learning
Authors: Kiran Koshy Thekumparampil
Prateek Jain
Praneeth Netrapalli
Sewoong Oh
Venue: NeurIPS 2021 Poster (2021)
Keywords: meta-learning
alternating minimization
few-shot learning
representation learning
spectral methods
matrix factorization

Abstract: In typical few-shot learning, each task is not equipped with enough data to be learned in isolation. To cope with such data scarcity, meta-representation learning methods train across many related tasks to find a shared (lower-dimensional) representation of the data where all tasks can be solved accurately. It is hypothesized that any new arriving tasks can be rapidly trained on this low-dimensional representation using only a few samples. Despite the practical successes of this approach, its statistical and computational properties are less understood. Moreover, the prescribed algorithms in these studies have little resemblance to those used in practice or they are computationally intractable. To understand and explain the success of popular meta-representation learning approaches such as ANIL, MetaOptNet, R2D2, and OML, we study a alternating gradient-descent minimization (AltMinGD) method (and its variant alternating minimization (AltMin)) which underlies the aforementioned methods. For a simple but canonical setting of shared linear representations, we show that AltMinGD achieves nearly-optimal estimation error, requiring only $\Omega(\mathrm{polylog}\,d)$ samples per task. This agrees with the observed efficacy of this algorithm in the practical few-shot learning scenarios.

Common real world tasks follow a long tailed distribution where most of the tasks only have a small number of labeled examples [51) Collecting more clean labels is often costly (e.g., medical imaging). As each task does not have enough examples to be learned in isolation under this few-shot Iearning Statistically and Computationally Efficient Linear Meta-representation Learning
Kiran Koshy Thekumparampil, Prateek Jain', Praneeth Netrapalli", Sewoong Oh* University of Illinois at Jibana-Champaii Google Research India, Microsoft Research India, + UUniversity of Washington, Seattle
Abstract
In typical few-shot learning, each task is not equipped with enough data be learned in isolation. To cope with such data scarcity, meta-representattoo learn- ing methods train across many related tasks to find shared (lower-dimension) representation of the data where all tasks can be solved accurately. It is hypothe- sized that any arriving tasks can be rapidly trained this low-dimensional representation using only a few samples. Despite the practical successes of this approach, its statistical and computational properties are less understood. Recent theoretical studies either provide highly suboptimal statistical error, or require many samples for every task, which infeasible in the few-shot learning setting. Moreover, the prescribed algorithms in these studies have little resemblance to those used in practice or they are computationally intractable. To understand and explain the success of popular meta-representation learning approaches such as ANIL 43), MetaOptNet (36], R2D2 99, and OML [33], we study a alternating gradient-descent minimization (AltMinGD) method (and its variant alternating min- imization (AltMin) the Appendix) which underlies the aforementioned methods. For a simple but canonical setting of shared linear representations, we show that AltMinGD achieves nearly-optimal estimation error, requiring only 2(polylog d) samples task. This agrees with the observed efficacy of this algorithm in the practical few-shot learning scenarios.
Introduction
scenario, meta-learning attempts to jointly learn across large number of tasks to exploit some structural similarities among those tasks.
One popular approach is to learn a shared representation, where new arriving tasks can be solved accurately [5).. The premise is that (i) there shared low-dimensional representation fu (æ) R" represented by a task- indeeenddeeeentt meta- parameter U and (ii) simple linear model of (v: fu (z)) can make accurate prediction on the i-th task with a task-specific parameter v;. Once the representation Jo has been learnt, we can rapidly adapt to new arriving tasks as the representation dimension much smaller than the dimension d of the input data. This approach becoming increasingly
popular with a growing list of recent applications been empirically shown to achieve the state-of-the-art performances on benchmark few-shot learning
33 36 9
27 47 14
13
18] and has
datasets [47 14 43
(prajain@googlee. com, eenttrapalli@goggll...o (Part of the work was done while at Google Research India), and sewooon @ cs. washington.edu.
"tthhkump@@llinnn
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

These successes rely on a simple but effective training algorithm which alternately updates U and {1z} which we call AltMinGD (Alternating Minimization and Gradient Descent). Suppose we are given t tasks, and the i-th task is associated with dataset {(ar)) E R R,,,,) this paper, we closely follow the formulation of [47], which solves for a function fu : R + R (typically a deep neural network) and a task-specific linear model ey E IR" on a choice of a loss f(-,-):
(() )} of size m. In
min
Σ min Σ E((s f( "EER"
(1)
sEid
5E[m]
by alternately applying a (stochastic) gradient descent step of U in the outer loop (for given 2/ 's) and numerically finding the optimal solution v in the inner loop (for given U). Several closely related algorithms have been proposed, including separating training- set used for the inner loop and the
validation-set used for the outer-loop 43 36
g [5, early stopping the inner-loop [3]. applying to
datasets with imbalanced data sizes 42
14 and proposing new architectures and regularizers [27].
There is an increasing list [47 14
43 of numerical evidences showing that these meta representation
learning improves upon competing approaches including MAML (20] and its variants [23 32 39.
Further, 43 provides experimental evidences that shared representation is the dominant component in the efficacy of MAML 20). even though MAML does not explicitly seek a shared representation.
In this paper, analyze the computational and statistical properties of AltMinGD and its variant AltMin under the simple but canonical setting of learning a shared linear representation for linear regression tasks [48]. The fundamental question of interest is: as the number of tasks grow, does AltMinGD learn the underlying r-dimensional shared representation (subspace) more accurately, and consequently make more accurate predictions new tasks? This question is critical in explaining the empirical success in few-shot learning where the number of tasks in the training set is large while each of those tasks is data starved. Further, in settings like crowdsourcing or bioinformatics, collecting more data on new tasks is easier than collecting more data on existing tasks.
Contributions. We analyze the widely adopted AltMinGD and prove nearly optimal error rate. We show that AltMinGD requires only m = 22ogg + log log(1/=)) samples per task to achieve an error of in estimating the representation U when have large enough number t of tasks in the training data and assuming a constant dimensionality r = O1) of the representation. Under this condition, AltMinGD achieves an error decaying as Ō(a //lodd/mmtt d/mm).. which nearly matches the fundamental lower bound. Together, these analyses imply that AltMinGD is able to compensate for having only a few samples per task (small m) by having many few-shot tasks (large t), significantly improving the state-of- the--rt (see Table L. Note that the log lo/(1/)) dependence of m is hidden in the Ω notation and is not explicitly visible from our main theorems or the table. A fine grained analysis showing this dependence is provided in Theorem 9 in Appendix C
We follow the proof strategy of alternating minimization algorithms for matrix sensing [0 38 but there are important differences making the analysis challenging. First, the meta-learning dataset does not satisfy Restricted Isometry Property (RIP) central in the existing matrix sensing analysis, and hence none of the technical lemmas can be directly applied. We leverage on the task diversity property in Assumption to prove all necessary concentration bounds. Next, there is an inherent asymmetry in the problem; we require accurate estimation of U for generalization to new arriving tasks (which is the primary goal of meta-learning), but we do not necessarily require accurate estimation of u, ss. We exploit this to ensure accurate estimation of U with a small m.
Our analysis of AltMinGD leads to a fundamental theoretical question: is the condition m = 22 t) necessary? We introduce variation AltMinGD-S, S, which at each iteration selects a subset of tasks that are well-behaver (covering the r-dimensional subspace of current estimated U/ and uses (the empirical risk of) only those tasks in the update. While log / dependence is unavoidable if we require all i tasks to be well-bhhaved, ensuring a large fraction to be well-behaved requires smaller m. When the noise is sufficiently small with variance ((1 / log t), we show that AltMinGID-S requires only m = 22ooo log(1/ (1/=)) (with no dependence on t) to estimate the shared representation accurately.
Inspired by long line of successes in matrix completion and matrix sensing (30], we also analyze a variation of AltMinGD that alternately applies minimization for U and { updates, which we call AltMin, and prove slightly improved guarantees at an extra computational cost of a factor of dr?.
Notations: [n]
{1, 2.... n2). ||A|]| and [| denote the spectral and Frobenius norms of matrix A. (A, B) denotes the inner product. At is the Moore- Penoose pseudoinverse. No,0, Lxxa) means

---

that æ is d dimensional standard isotropic Gaussian random vector. Ö, Ωt and θ hide logarithmic terms in dimension d, rank r, tolerance and other problems parameters.
1.1 Related work
There is a large body of work in meta-learning since the seminal work in learning to learn 46
inductive bias learning 77), and multitask learning [12]. One popular approach starting from 28
is to learn a shared low-dimensional representation for set of related tasks. This is becoming increasingly popular with empirical successes in the few-shot learning scenarios
33 36
9
42
27 47 14.
Linear representation learning. In this paper, show that the popular AltMinGD algorithm for solving meta representation learning, achieves near-optimal error rate and sample complexity when applied to recovering linear representations, i.e. (z) U"x. This problem has been studied in
3
40 and Nuclear-norm minimization approaches are proposed in 4 24 2 41 but they do not
provide subxpace/generaalizatoi error guarantees and suffer from large training time. Closest to
work are [8 33 34 [9] which propose new algorithms with statistical guarantees. We also point a concurrent and independent work [16], which also analyzes AltMinGD but for special case of the noiseless setting. Authors empirically showed that AltMinGD performs better than other baseline federated learning algorithms for neural meta-representation learning on some datasets. We compare these results with our guarantees in Section 4.1
Competing against mett-reprreenttatinn learning approaches listed above are the bi-level optimization based methods. A pioneer in this direction is MAML [20], which is analyzed under linear regression tasks in [5 21 8 22 [1] and (21] identify that MAML outperforms simple Empirical Risk Minimization (ERM) when tasks are heterogeneous in their respective level of difficulty. [8] shows that, perhaps surprisingly, negative learning rate is optimal for MAML applied to linear regression tasks, where zero learning rate corresponds to the standard ERM.
Matrix sensing. Starting from matrix sensing and completion problems a low-rank matrix from linear measurements has been a popular topic of research. Linear meta- learning is special case of matrix sensing, but with non-standard sensing operator of the form A(UV²) = [A1 (UVT)..... Amx (UV*)) where (UVV)) = ( .VV }. This operator does not satisfy restricted isometry property in general, and existing matrix sensing results do not apply. Similar sensing operators have been studied in (29 [2] which gives m = M(d). We provide a significantly tightened analysis to require only 2loogt t + log log(1/e)).
30
recovering
2 Problem Formulation: Meta-learning of Shared Representation
We focus on the meta-learning problem with a shared linear representation for linear regression tasks. Let denote the number of tasks. The i-th task is associated with m samples {(x])) E Rd, 3y We assume there is common low-dimensional representation (U*)²*a of each data point x, parameterized by U E dx where r < d. The corresponding observation y is sampled by regressing over the low-dimensional representation (U+)² x. Now, in general, learning U is Na-hard 25.. Instead, similar to [48). we study the problem in the following tractable random design setting.
(i)
B)
Assumptions 1. Let U Rdxx be an orthonormal matrix. For task i E [4]. with task specific (1) ~ (O, its observation is: parameter vector x (6) E IR and j-th example x.
Vj = (0)) U u + +e
(2)
where ( ~ o2) is the measurement noise which is independent of x We denote by ( = (0) the model parameter vector for each regression task in d-dimensions. We denote the matrix of these parameters as: V = UV*V"" where (V*)T" = [1) ,..., (
The difficulty of estimating U* still depends on the diversity or incoherence of the tasks. Assumptions 2. Let Xi and X denote the largest and smallest eigenvalues of the task diversity matrix (r/ E Bexr respectively. Let k = >//. We say that V is pu-incoheret if
max |10 10) < i x :E(1]
(3)
3

---

To estimate the subspace U, we minimize the empirical risk of the t tasks in the training data, over the
parammereee U E Rdxr and the task-specific model parameters V = [e((1. e 200 E R
m
(3) - (Uv(1) I. ( 2
C(U.V)
(4)
The problem is non-convex due to the bi-linearity of Uand V. We are interested in the few-shot learning setting where the goal is to learn the representation accurately despite a small number of samples per task in the training data. Now, even if the representation U* is known a priori, we would require (r) samples per task to learn the parameter v. Furthermore, information theoretically the total number of samples
should scale at most linearly with the data dimension d.
3 Alternating minimization
We focus on AltMinGD from [47]. which learns shared parameterized representation f-) in (l]. Several variations of this algorithm are widely used, for example [43] 36,91. 91. However, we note that these previous works neither referred to this algorithm as AltMinGD, nor explicitly related it to the Alternating Minimization (AltMin) framework [3). To highlight this connection we follow the notations from the latter [30]. AltMinGD alternately updates the matrix of regression parameters V using exact minimization with fixed U, and updates the representation parameter U using the standard gradient descent step. Concretely,
v E arg min DERr
Σ jE[m]
Ell, ),, .iell 14.
U+U Σ iE|O JE(m]
As f(.,-) is typically a convex function, we estimate (1()) efficiently for fixed U. Note that many methods used in practice (ANIL [43 and MetaOptNet (36) back pack-propagate through their respective inner (potentially inexact) optimization step. However, since do exact inner minimization with respect to V. by generalization of the Danskin's 's theorem [0], hack-propagating through the inner minimization is equivalent computing the gradient Cu V') with respect to U and then setting V VVV*(U) VU) where (U) E arg miny L(U, V) is the minimizer for the current U. That is, Vu miny L(U, V) LU, V* (U)). For the linear representation learning problem specified in Section 2 the above updates reduce to the following:
( E arg aig min
Σ 1uu
,ou)) for all i E [t],
= U Un+ I (of0) Un 2 (6(0).
Given U, we can efficiently estimate each of the low r-dimensional regression parameters 600's separately and in parallel using standard least squares regression. Our analysis requires that when we update V for current U, U should be independent from the training points. Similarly, during the update for U, V should be independent of the data points. We ensure the independence using two strategies: (a) similar to standard online meta-learning settings (20). randomly select (previously unseen) tasks to update U and V. (b) within each task, we divide the datapoints into two sets to update V and U separately. But in our experiments, we re-used all the samples at each iteration. Algorithm|] presents a pseudo-code of AltMinGD applied to Problem 4 Note that in Algorithm|] T apply RRdecoooooiiio on U after every U update to ensure that magnitude of U and V does not stray far away from that of true U and V respectively. Otherwise, the sample complexity requirements of the algorithm increase in the condition number factors.
Kun-time and memory usage: Exact update for ()( has a time complexity of O(mr² + +r)), which can be brought down to 0mm- rr) by using gradient descent for solving the least squares. Our analysis shows that under the sample complexity assumptions of Theorem [ each of the least squares problem has a constant condition number. So, the total number of iterations for this update scale as log ! to achieve error. If we set 1/poly(t, r), then using standard error analysis, should be able to

---

Algorithm AltMinGD:
Meta-learning linear regression parameters via alternating minimization
gradient descent
Required: Data: {(x)) E IR", .u," E RR) for all 1 i S t, K: number of steps, stepsize.
Initialize U <- Uiit
2 Randomly shuffle the tasks (I.....t)
for 1 S k S K do
Tx [1 + 1(k-1)
K
for i To do
( f arg min
Σ (u, (U
DER
jelm/22
end
U U + Σ
Σ
( (Uv 22, )=,))) (v'0)
+=
U- QR(U)
end return U
Algorithm 2 AltMinGD-S Meta-Learning regression parameters via AltMinGD over task subsets
Required: Data: {(x,)) E Rdd y E IR) } for all < t, K: number of steps, fy: stepsize.
Use the same steps as AltMinGD (Algorithm D. but replace Line B with:
To {i E [1 + (k-1)) de
o max (UT s U) s 2; miin (U (WU) 2
K
where 5(i) 2
Ejelm/2 2 (3) )
obtain the optimal error rate in Theorem The gradient descent update for U requires O(mt dr) time assuming large enough mtt. Furthermore space complexity of AltMinGD is O(r + +
We provide an estimate of the statistical efficiency of the AltMinGD in Theorem provide an analysis of the traditional Alternating Minimization algorithm (AltMin) which uses exact minimization for updating U in the Appendix A We obtain a slightly improved statistical guarantee for AltMin terms of the condition number but its run-time is slower than that of AltMinGD.
We also
3.1 Subset Selection
Algorithm [operates over all the tasks in a batch, each of which are generated using a random process. Now, if the number of tasks t is large, then there a non-trivial probability that some of the tasks are outliers, i.c., they have large amount of error. This might lead an arbitrary poor solution due to the outlier tasks. This is reflected in our analysis of AltMinGD (see Theorem T.. where the number of samples per task grows logarithmically with which is non-intuitive as typically larger number of tasks should not hurt the sample complexity.
In more general representation learning problems, when the number of tasks t is large, there is more chance that some them are outlier tasks. Ideally we want to design an estimator for shared representation U that is robust to few outlier tasks. For the linear representation learning problem, we observe that to ensure small error for task, we require the Hessian to be well-conditioned. So, we compute the eigenvalues of the Hessian UT 5 for each task with the current U, and select only the tasks whose eigenvalues lie close to the expected repeated eigenvalue 1. Algorithm applies this criteria to select tasks in each iteration, and then use the standard AltMinGD updates on those selected tasks. This leads to improved dependence on as show in Theorem 3
Run-time: On top of the run-time complexity of AltMinGD, the subset selection scheme adds an additive (mt dr + 13) term. This arises due to O(r3) eigen-decompositionn of ÜT S Rrxr for each task.
5

---

4 Statistical guarantees for Alternating Minimization algorithms
We reiterate that O and Q hide logarithmic terms in d and r and other problem parameters. We analyze the AltMinGD and AltMinGD-S algorithms using the rescaled Frobenius norm error: II(I U (U*) ("U")" / E [0. 1] between the rank-r subspaces corresponding to the true U and the output of the algorithm U. We first provide our main results analyzing these algorithms, and present detailed comparisons to previous results in Section 4.1
AltMinGD: We first present our main result for the AllMinGD method (Algorithm I. applied to the linear representation learning problem described in Section 2
Theorem (Simplified version of Theorem 9 in Appendix
Let there be t linear regression tasks, Let K. \ >x, and let,
each with m samples satisfying Assumptions
m 2 0(r² + r rllott+ + R. (a/ /2) log & 12 2(K (alm.prr)) 12r3), and
mt 2 S(K udr² + +R.. .dr pddrr (o/vV:)))
Then AltMinGD (Algorithu 71. initialized Unit s.t.
I1(I - (P(UU))))mnil S [[[Tlog(mt//((: pdr (0/ (x,))) iterations with the r/t outputs U so that the following holds (w.p. 2 1 - K (ddr)22)) 2x
min(21/121, ((1/r)) and run for stepsize 17
I[II (U-UUUU"))UUL JillE S o 6O
pd mt
V
(5)
Vr
VAG
Remark (Initialization): Our result holds if the initial point Unii is reasonably accurate. One choice of initialization is to use the Bfethod-of-Momocee (MoM) [48]. Due to sub-optimality of MoM approach (148) Theorem 3], also provided in Theorem [2 in Appendix), we get an additional sample complexity requirement of ml 2 (rx"' (μK + r(a// /A;)"). Note that this does not degrade the asymptotic error rate, ((Vdr/ma) when Ö(v dr/tt) + O. In our experiments, we observed that random initialization works just as well. Such requirement of good initialization is common in theoretical analyses of alternating update methods 30 38] where it has been widely observed that random initialization works well in practice.
Remark 2 (Generalization in few-shot learning): Learning shared representation helps in gener- alizing to new arriving tasks in few-shot learning. Suppose we run Algorithm [ under the conditions of Theorem T to get an estimated subspace U. Let new task, whose task specific regression parame- ter x+ lie U* introduced with m samples. Now, we can apply the step Of Algorithm with U and the new samples, to meta-learn an estimate et of +*+ Then the mean-squared-enuo (MSE) of the estimated parameter is Ō((a/ / (x)) /md + r//m*)) Therefore, long as ml is large enough, only need m + = s(r) additional samples to get arbitrarily small MSE, opposed to m = (d)) of the trivial baseline of solving the new task by itself. We also improve upon other and f; see Section 4.1 and Table I more details.
baselines from [88 in terms of dependence
Remark 3 (Near-optimality of the error rate): We note that our error rate matches - up to poły(K, (4) factors - the information theoretic lower bound given in Corollary 2
Corollary 2. 48 Theorem 5] Let r < d/2 and mt 2 r(d (id--1 r). for all V w.p. 2 1/2
[(I (I- UU--(U D0 sl //dr) VA: mt)
dr
inf sup UEGE,
(6)
VT
where Gy is the Grassmannian manifold of r-dimensional subspaces in Rd. the infimum for i is taken over the set of all measurable functions that takes mt samples in total from the model in Section 2 satisfying Assumption 7 and
However, the sufficient conditions mt in Theorem above, which we discuss with a concrete example in the next remark.
I Thas factor gap from the necessary condition
Remark 4 (Gaussian example): Let us interpret our result using concrete example. Consider
independent Gaussian parameters y (+()) ~ A0 (I/r) such that the signal-to-noise ratio (i.e., I U u /0²) is independent of r. Then with high probability [|]+ @(1) and io X

---

(1). It follows that as per Assumption 2 the condition number k. = (1) and ē(). To estimate U up to error, AltMinGD needs total of mt = Ō + dr samples. The second term is dominant for small and is optimal, which follows from the near-optimality in Remark 2. However, it is open question if the first term is necessary, the best known lower bound in the noiseless case will require ml = Mddr). In this well-behaved Gaussian case, AltMinGD requires m 2 (2(2 + (1++2) )r log t) per task samples.
Remark (Dependence on the minimum eigenvalue): Notice that in the limit of - 0, V is rank deficient, thus making it impossible to recover the entire subspace of U* This is reflected in our Theorem 3 where the error-rate approaches the maximum possible value of one as X approaches zero (the LHS of Eq. (5) is at most one). However, for prediction error, smaller rank of V implies smaller dimensional representation to be learned, thus the prediction ervor bound should improve with lower X (and also smaller rank of V*). Proving tight guarantee in the prediction error is more challenging and most of the existing results in matrix sensing literature (29 only provide guarantees in parameter estimation error. On the contrary, the lower-bound in (6) becomes zero as X decreases, implying that the lower-bound is significantly weaker in A This is expected since the lower-bound is derived through a lower-bound for the corresponding subspace regression loss. Intuitively when X; = 0 the tasks become less diverse (more homogeneous), and therefore the regression becomes easier. Such condition number mismatch in upper and lower-bounds are common in low-rank literature (30]
Task subset selection (AltMinGD-S): One downside of Algorithm I is that m needs to increase with I (i.e., m = S2(log t)). We introduce AltMinGD-S Algorithm to study a fundamental question of whether this log dependence is necessary. We show that when the noise is sufficiently small, AltMinGD-SS achieves a per task sample complexity that does not increase with I.
Theorem 3 (Simplified version of Theorem in Appendix D). Consider the setting of Theorem !
Let K = A//A
2 2(7 + (a/ 2r logt), t2 0( 12r0), and
mt 2 50( pdr² + x² udr (a/ (x))))
+ initialized at Unit s.1. (U*) S min Then AltMinGD (Algorithm and run for K 22 [n log mt/ /it udr (a/ (x/)) iterations using the stepsize n U so that the following holds (w.p. 2 1 k))
r/t 2X²' outputs
II (U*) JlllE S 50 (V Vr
pdr r mt
(7)
Remark 7 (Bias of Subset Selection): One may observe that this scheme may introduce a bias in the training data at each iteration. However, we control this bias by adding a new requirement that the number of tasks should be at least t 2 2(( 222²)) (Theorem 6). This ensures that the only a small O(1/ur) fraction of the tasks are discarded at each step (Lemma D. in the Appendix D.I.. and this leads to a low bias. This requirement may be insignificant in our regime of interest where the number of tasks may be exponentially large, so that AltMinGD-S can provide gain over AltMinGD.
Remark 6 (When noise is small enough): Note that when the noise variance a is small enough or when there are large number of tasks, i.e. o² < O /log t), AltMinGD-S only needs m 2 2(r²) samples per task, assuming suitable initialization (see Remark 1). Furthermore, since AltMin-S selects a fraction of tasks to perform updates and the selection process requires only 00ml-dr+- the time-complexity of the method remains same as that of AltMinGD, up to constant factors. Next we see that AltMinGD-S removes the dependence of m on t completely, in the noiseless setting. Corollary 4. Let there be t linear regression tasks, each with m samples satisfying Assumptions 7
m 2 A((r²) 1 2 "))²,""), and ml 2 0(udr" K)-
Additionally assume that the observations are noiseless, iee a = 0. Then AltMinGD-S (AMMinGD-((llgrttmmm initialized at Unntt s.I. - -U* (unatll le & min(21/121) Õ(1 ({]/))) and run for K iterations
(Algorithm)
using the stepsize 1) 2x outputs U so that the following holds (w.p. 2 1 - K/(dr)00);
[I(I - (U)))
< (1
K (R)
(8)
Vr
6K
7

---

The above corollary shows that in the noiseless setting, the per-task sample complexity for AltMinGD. does not grow with t, and is nearly optimal. Also note that that even for noiseless setting, tech- niques like Method-of- ofo-ommnts (MoM) still incur error of /dr/mf. ignoring terms. contrast, AltMinGD-S when initialized using MoM method (see Remark 1)), incurs just ((exp(-t/<)) error. Proofs of Theorems
3 are in Appendix C.T & Appendix D.1
4.1 Sample complexity comparison
To the best of our knowledge, Theorems I and presents the first analysis of an efficient method for achieving optimal error rate in a, and r. 48 is most relevant that analyzes the landscape of the Empirical Risk Minimization (ERM) with Burer-Monteiro factorization. It shows that ERM can achieve a rescaled Frobenius norm eπror of & with tasks (assuming 2 d), when m Z log(t) + r² log(t)o"/s²)) We stress that this highly sub-optimal as for small estimation more tasks do not help improve the per-task sample complexity. This also does not reconcile with practice where more tasks tend to help accuracy and helps overcome small number of samples per-task. In contrast, AltMinGI) requires m 2 (1 + o²) log(t) + (r20² /e") /ea) (d/t)) where small emror can be achieved by collecting more tasks and increasing t. [19) studies the global minimizer of the non-convex ERM optimization Eq. without providing an efficient algorithm to solve it.
The authors show that non-convex ERM achieves a small generalization error if m {2(d), which is impractical in the few-shot learning setting.
Another approach is Method-offMooment (MoM), which estimates U by finding the principal directions of particular 4th moment of the data 48
35 MoM can indeed trade-off smaller error
e by increasing the number of tasks f. But the algorithm is inexact, i.c., even for = O, we need This is in a stark contrast with AltMinGD exactly, as long as m Orr log / + r²) and (dr); ; see Figure la for an illustration. We consolidate these comparisons in Table
m + oo achieve exact recovery of U*: see Appendix G
and A AltMinnGDSS where for noiseless case, we can find e
Finally, a concurrent and independent work by [16] also analyzes AltMinGD but only for the special case when there is noise, i.c., 0. We show tighter results that more generally applicable: (i) our analysis applies to general noise a that is not necessarily zero, (ii) even in the noiseless case, analysis of AltMinGD is tighter and shows smaller sample complexity, and (iii) we present novel AltMinGD-S that further improves the sample complexity. Precisely, in the noiseless case,
[16 proves that m [xx² 3 log t) is sufficient for finding U* with a large enough t. Our tighter analysis shows that m Q( log t + r²) (Theorem 1 is sufficient with no dependence in Note that the condition number x > 1 and can be arbitrarily large depending on the problem instance. Further, we present novel algorithm, AltMinGD-S, that only requires m 2 {i(r²) (Corollary 4
Table 1: Comparison of per-task sample complexity results m(t,s) to reach error when solving linear meta-representation learning with tasks, d dimensions, subspace rank r O(1) and noise variance o² (Sections 4 2 let t >> d. We also report if the prescribed algorithm is computationally tractable and extendable to practical neural-net setting. AltMinGD-S relies on the eigen values the data when projected onto U and cannot be directly applied to neural networks.
Analysis
Per-task sample complexity m(t,e)
Tractable?
Practical?
Non-convex ERM 19
②id + (tg(() +
Burer-Monteiro ERM
((log(t) + =
Yes
Yes
Method-of-Moments
21 + 22 + cdd
Yes
No
AltMinGD (Theorem
π((1 + 0²) logt + odd
Yes
Yes
AltMinGD-S (Theorem
2(1 + + log(t) ol'gtt) + 12
Yes
No
Lower-bound 48
22( 12
d'd
5 Experimental results
In this section we empirically compare the performance of AltMinGD (Algorithm T and its exact minimization variant AltMin (Algorithm 3 in Appendix), two different versions of Method-of-
8

---

Bron I: (7 Willl
Erooc (o 30
Eroon I (M(O)) "Wll
magaitude
samples per (xrs)
(a)
(b)
(c)
Figure 1: (a): AltMin and AltMinGD achieves vanishing error as noise a decreases, whereas the error of the two -foiodd-o--Moeetss (MoM, MoM2) stay bounded away from zero. BM-GD, which seems unstable and hard tune, achieves an intermediate level of error. (b), (c): AltMin, AltMinGD and BM-GD incurs significantly smaller error in estimation of true subspace U than MoM and MoM2, both for growing number of tasks (f) and for growing number of samples per task (m).
Enor [(X (0 1
Noise (a) AltMin
magninude (d)) (b) AltMinGD
Eroo: (() -rtto" yT1l
Enve: [[ U0100""T000
Erver Ia unterr M01
Noise magniude
Noise magnizade (()
Noise magninul
(c) MoM
(d) MoM2
(e) BM-GD
Figure 2: Compared others, BM-GD is unstable and challenging to tune in the low-noise regime.
MoM2 (35)) and simultaneous gradient descent (U, V) using the Burer- Monteiro factorized loss 4 (BM-GD [48).. We omit AltMinGD-S here because the logarithmic gain (1/ (t) of AltMinGD-S will only be observed when have exponentially large number of tasks (I). This is challenging to simulate using our modest computing hardware. However, for big-data scenarios similar subset select schemes may be useful. In all the figures, the magenta dashed line with square marker represents AltMinGD, the blue straight line with circular marker denotes the AltMin. the red dotted line with downwards pointing triangular marker denotes the MoM, the yellow dotted line with upwards pointing triangular marker represents the MoM2, and the green dashed and dotted line with diamond marker represents the BM-GD. In all the figures we plot the subspace estimation error of the output U of the algorithms. The error calculated using the rescaled Frobenius norm [I(I (U* "T)T)) |l/ /r. which takes value in the interval [0, 1). All results are averaged over multiple runs, and more experiments details and plots are provided in Appendix H
Moments (MoM 48
Figure La plots subspace distance against the standard deviation of the regression noise, e) (0, ) see (2). Clearly, as predicted by Theorems [ and 5 (in Appendix), the methods Consider-AltMinn
and AltMin - -achieve smaller error than MoM methods for small noise regime. Here the error of AltMinGD and AltMin are linearly proportional to However as predicted the error of MoM and MoM constant multiple of /dra/ mt /r for all values of a, and does not improve when decreases (see Table 1). While BM-GD does not have any known algorithmic guarantees, it still performs better than MoM methods. However, BM-GM becomes unstable and challenging to tune at low noise regime, even at lower comparable step-size than AltMinGD, To highlight this, the individual trials for each algorithm this plot are plotted in Figure 2 Figure Tb plots the subspace error against the number of tasks t. In Figure Ic plot the the error against

---

High task diversity
Moderate tosk diveriity
Low task diversity
Broon la (7(0)) Twwll
Erron Ii (M(()))))) "Wll
p.o. S S.9.
Erroe: 1 (EFP)))
Number of iterations
Number iterations
Numbhr iterations
(a)
(b)
(C)
Figure 3: AltMin converges using fewer iterations than AltMinGD and BM-GD, but AltMinGD can be faster in practice due to its computationally cheaper iteration. While the performance of all the
methods degrade as task diversity decreases, AltMin appears to be most robust to changes in diversity.
the number samples per tasks m. In both of these figures, we observe that, AltMinGD, AltMin and BM-GD achieve much smaller subspace error than the MoM and MoM2. Furthermore, as predicted, the squared error of all these methods decrease linearly in m and L. We again note that BM-GD unstable and hard to tune, especially for large L. The individual trials for each algorithm on these two plots are plotted in the Appendix [H] ERM-based BM-GD performs poorer than Alternate Minimization based AltMin and AltMinGD. This might be due to the presence of many bad local minima in the optimization landscape of the ERM problem jointly over (U, V) [48] Theorem 2].
In Figure we plot the subspace estimation error against the number of iterations of AltMinGD, Alt- Min, and BM-GD for varying levels of task diversity μ (Assumption 2). We observe that AltMin takes significantly fewer iterations to converge than AltMinGD and BM-GD. and AltMinGD converges earlier than BM-GD. However, each iteration of AltMin is very slow as it needs O(d²) operations, where as AltMinGD and BM-GD need only (d) operations per iteration. Therefore, AltMinGD could be the fastest in practical nigh-dimensional setting. BM-GD seems to be slower than AltMinGI because BM-GD seems to need a smaller stepsize than AltMinGD to stabilize its convergence. While that AltMin is more robust than others. This may be attributable to AltMin's 's tighter dependence on the condition number k (Theorem 5 in Appendix) when compared to AltMinGD (Theorem
all the methods perform worse when the task diversity decreases ((a) - (b) + (c)),
Conclusion
When learning shared representation for multiple tasks, common approach is to alternate between finding the best linear model for each task on the current representation, and taking one gradient descent step update the shared representation. This algorithm, AltMinGD, has been widely used in meta-representaation learning with little theoretical understanding. We provide insights into the empirical success of AltMinGD by studying it in the canonical problem of linear meta-learning. We showed that, AltMinGD provides a nearly optimal error rate, along with nearly optimal per-task and overall sample complexities in their dependence in the dimensionality of the data. To the best of our knowledge, this is the first such optimal error rate that scales appropriately with the noise in observations, while still ensuring per-task sample complexity to be nearly independent of the dimensionality d. Latter is key requirement in meta- peeta-learning as individual tasks are data-starved. The limitations of our results are: (i) the analysis does not extend to non-linear representations, (ii) the dependence on the rank r of the shared subspace, the incoherence μu, and the condition number may not be tight; and (iii) our analysis "local" and requires a good initialization. We also proposed and analyzed a task subset selection- based method (A (AIMMinGD-S) that further improves the per-task sample complexity and ensures that is independent of the number of tasks in small noise or large number of tasks regime. However, the subset selection scheme heavily relies on the linearity of the shared representation. Therefore, this scheme cannot be directly applied to more practical neural network training. It also remains open question if it is possible to achieve a per-task sample complexity that does not depend on the number of tasks f, even in the large noise setting.
Our work leads to several interesting future directions and questions. For the non- non-linear version of the problem, ensuring optimal error rate with optimal per-task sample complexity is an interesting open question. Finally, analyzing alternating minimization methods with stochastic gradients and streaming tasks is another promising direction. Our proof techniques could be combined with that of recent results in efficient one-pass SGD (31 to design nearly optimal stochastic algorithm.
10

---

Acknowledgements
Oh acknowledges funding from Google faculty research award, NSF grants I1S-1929955, CCF- 1705007, CNS-2002664, CCF 2019844 as part of Institute for Foundation of Machine Learning, and CNS-2112471 part of Institute for Future Edge Networks and Distributed Intelligence. We also thank anonymous reviewers for their reviews and suggestions for improving our manuscript.
References
[1] Ali Amir-Moéz et al. Extreme properties of eigenvalues of hermitian transformation and singular values of the sum and product of linear transformations. Duke Mathematical Journal, 23(3):46-477, 1956.
[2] Yonatan Amit, Michael Fink, Nathan Srebro, and Shimon Ullman. Uncovering shared structures in multiclass classification. In Proceedings of the 24th international conference Machine learning, pages 17-24, 2007.
[3] Rie Kubota Ando and Tong Zhang. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research, 6(Nov):1817-1853 2005.
[4] Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Convex multi-task feature learning. Machine learning, 73(3):243-277 2008
[5] Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lee, Sham Kakade, Huan Wang, and Caiming Xiong. How important the train-validation split in meta-learning? In International Conference Machine Learning, pages 543-553, PMLR, 2021.
[6] Jonathan Baxter. Learning internal representations. In Proceedings of the eighth annual conference on Computational learning theory, pages 311-320, 1995.
[7] Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-198, 2000.
[8] Alberto Bernacchia. Meta-learning with negative learning rates. In International Conference on Learning Representations, 2020.
[9] Luca Bertinetto, Joao F Henriques, Philip Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations, 2018.
[10] Dimitri Bertsekas. Convex optimization theory. Athena Scientific, 2009.
[11] Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematies, 76777717 2009.
[12] Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
[13] Wei- Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. A closer look at few-shot classification. International Conference on Learning Representations, 2018.
[14] Yinbo Chen, Xiaolong Wang, Zhuang Liu, Huijuan Xu, and Trevor Darrell. new meta-baseline for few-shot learning. arXiv preprint arXiv:2003.04390 2020.
[15] Liam Collins, Aryan Mokhtari, and Sanjay Shakkottai. Why does maml outperform erm? an optimization perspective. arXiv preprint arXiv:2010.14672, 2020.
[16] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. arXiv preprint arXiv:2102.07078. 2021.
[17] I. Csiszár and G. Tusnady. Information geometry and alternating minimization procedure. Statistics and Decision, 1984.
[18] Guneet Singh Dhillon, Pratik Chaudhari, Avinash Ravichandran, and Stefano Soatto. A baseline for few-shot image classification. In International Conference on Learning Representations, 2019.

---

[19] Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint S2ti:2200.0094344 2020.
[20] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. arXiv preprint arXiv: Set::/703.30000 2017.
[21] Katelyn Gao and Ozan Sener. Modeling and optimization trade-off in meta-learning, Advances Neural Information Processing Systems, 33, 2020.
[22] Micah Goldblum, Steven Reich, Liam Fowl, Renkun Ni. Valeriia Cherepanova, and Tom Goldstein. Unraveling meta-learning Understanding feature representations for few-shot tasks. In International Conference on Machine Learning, pages 3607-3616. PMLR, 2020.
[23] Fusheng Hao, Fengxiang He, Jun Cheng. Lei Wang. Jianzhong Cao, and Dacheng Tao. Collect and select: Semantic alignment metric learning for few-shot learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8460-8469, 2019.
[24] Zaid Harchaoui, Matthijs Douze, Mattis Paulin, Miroslav Dudik, and Jérôme Malick. Large- scale image classification with trace-norm regularization. In 2012 IEEE Conference on Com- puter Vision and Pattenn Recognition, pages 3386-3393, IEEE, 2012.
[25] Moritz Hardt, Raghu Meka, Prasad Raghavendra, and Benjamin Weitz. Computational limits for matrix completion. In Conference on Learning Theory, pages 703-725. PMLR, 2014.
[26] Harold V Henderson and Shayle R Searle. On deriving the inverse of a sum of matrices. Siam Review, 23(1):53-60, 1981.
[27] Shaoli Huang and Dacheng Tao. All you need is a good representation: A multi-level and classifier-centir representation for few-shot learning. arXiv preprint 19X1::191../2476, 2019.
[28] Nathan Intrator and Shimon Edelman. Making a low-dimensional representation suitable for diverse tasks. In Learning to learn, pages 135-157. Springer, 1996.
[29] Prateek Jain and Inderjit S Dhillon. Provable inductive matrix completion. arXiv preprint arXiv: 0626, 2013.
[30] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665-674, 2013.
[31] Prateek Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Paral- lelizing stochastic gradient descent for least squares regression: hini-batching, averaging, and model misspecification. Journal of Machine Learning Research, 18, 2018.
[32] Muhammad Abdullah Jamal and Guo-Jun Qi. Task agnostic meta-learning for few-shot learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 17719-11727. 2019.
[33] Khurram Javed and Martha White. Meta-learning representations for continual learning. In Advances in Neural Information Processing Systems, volume 32, 2019.
[34] Weihao Kong. Raghav Somani, Sham Kakade, and Sewoong Oh. Robust meta-learning for mixed linear regression with small batches. Advances in Neural Information Processing Systems,
33, 2020.
[35] Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In International Conference on Machine Learning, pages 5394-5404. PMLR, 2020.
[36] Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In 2019 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10649-10657. IEEE Computer Society, 2019.
[37] Raghu Meka, Prateek Jain, and Inderjit Dhillon. Guaranteed rank minimization via singular value projection. arXiv preprint arxiv:0909.5457, 2009,
12

---

[38] Praneeth Netrapalli, Prateck Jain, and Sujay Sanghavi. Phase retrieval using alternating mini- mization. IEEE Transactions on Signal Processing, 63(18))4814-422 2015.
[39] Boris Oreshkin, Pau Rodriguez, and Alexandre Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning. arXiv preprint 1rXx::/805..0123, 2018
[40] Alon Orlitsky. Supervised dimensionality reduction using mixture models. In Proceedings of the 22nd international conference on Machine learning, pages 768-775, 2005.
[41]
Massimiliano Pontil and Andreas Maurer. Excess risk bounds for multitask learning with trace norm regularization. In Conference on Learning Theory, pages 55-76, 2013.
[42] Siyuan Qiao, Chenxi Liu, Wei Shen, and Alan L. Yuille. Few-shot image recognition by predicting parameters from activations. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), June 2018.
[43] Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of MAML. arXiv preprint arXiv:1909.0911 2019.
[44] Irina Rish, Genady Grabarnik, Guillermo Cecchi, Francisco Pereira, and Geoffrey Gordon. Closed-form supervised dimensionality reduction with generalized linear models. In Proceed- ings of the 25th international conference on Machine learning, pages 832-839, 2008
[45] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data deep learning era. In Proceedings of the IEEE international conference on computer vision, pages 843 022,-552222 2017.
[46] Sebastian Thrun and Lorien Pratt. Learning to learn: Introduction and overview. In Learning to learn, pages 3-17. Springer, 1998.
[47] Yonglong Tian, Yue Wang, Dilip Krishnan, Joshua B Tenenbaum, and Phillip Isola. Re- thinking few-shot image classification: good embedding is all you need? arXiv preprint arXiv:2003. / 1539, 2020.
[48] Nilesh Tripuraneni, Chi Jin, and Michael I Jordan. Provable meta-learning of linear representa- tions, arXiv preprint arXiv:2002. 1684, 2020.
[49] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint
2010.
[50] Roman Vershynin. High-dimensional probability An introduction with applications in data science, volume 47, Cambridge university press, 2018
[51] Yu-Xiong Wang. Deva Ramanan, and Martial Hebert. Learning to model the tail. In Advances in Neural Information Processing Systems, pages 7029-7033 2017.
[52] Kai Zhong, Prateek Jain, and Inderjit S Dhillon. Efficient matrix sensing using rank-1 gaussian measurements. In International conference on algorithmic learning theory, pages 3-18. Springer, 2015.
13

---

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] see Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We conduct a purely theoretical study analyzing existing techniques.
(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] see Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or 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 (e.g., with respect to the random seed after running experi- ments multiple times)? [No] Instead error bars we provide separate plots for each of the random runs for all the algorithms (some in Appendix H
(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)? [No] The amount of compute required to simulations is trivial
4. If you using existing assets (e.g., code, data, models) or curating/releasing 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 assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're '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 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 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 on participant compensation? [N/A]
14


Reviews:
[{"review_id": "rEIJ43nNoXf", "reviewer": "Reviewer_HZi9", "summary": "This paper provides sample complexity and error bounds for “alternating gradient descent minimization” (AltMinGD), an algorithm used for meta-learning. It shows that AltMinGD applied to linear regression is superior to competitors such as Empirical Risk Minimization (ERM) and Method of Moments (MoM). Furthermore, they show that the bounds are tight and basically cannot be improved upon.\n", "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": "Even if results apply to linear representations only, I find this work very compelling and useful.\nIn the last couple of years, increasing evidence shows that linear meta-representation learning is a very useful and tractable framework to understand meta-learning, and to gain some intuition about the phenomena observed in more complicated (non-linear) contexts.  \nThe paper is well written and I think it can be published in its current form.\n\nI only have a couple of clarification questions:\n1) By assumption the matrix U is orthogonal. My understanding is that AltMinGD enforces orthogonality of U by a QR decomposition at the end of training. This step is not even mentioned in the text and it seems very brute force. How important is the assumption of orthogonal U? Why doesn’t the QR last step ruin the representation obtained during training?\n2) What is the intuition behind the superior performance of AltMinGD with respect to ERM and MoM?\n\nOther comments:\n\n- A number of papers about meta-learning and linear regression have been published recently that the authors have not considered: https://arxiv.org/abs/2102.00940, https://arxiv.org/abs/2010.05843, https://arxiv.org/abs/2010.12916, https://arxiv.org/abs/2010.14672\n- In line 124 (Assumption 2), the condition number k is introduced but not used.\n- Line 171. How is the number 4 selected as maximum condition number for the Hessian?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "mfeikus14vq", "reviewer": "Reviewer_j2Hi", "summary": "The paper analyses linear meta-representation learning, deriving formally statistical guarantees for widely adopted and empirically successful alternating minimisation algorithms (AltMinGD). With the gained insight, the authors propose a new variant of AltMinGD, named AltMinGD-S, which introduces a task selection mechanism at each alternating iteration to improve efficiency with respect to number of samples per task in high number of tasks scenarios.", "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": "The paper provides valuable theoretical insights and statistical bounds on representation meta-learning. The analysis is thorough and well explained, reaching simple and insightful conclusions. The new proposed method of AltMinGD-S is maybe of incremental novelty, but it is well motivated and rooted in the new insights, although I have some doubts on its practical efficacy (see comments). The experiments are not very comprehensive and not very well explained.\n\nSpecific comments:\n\n1) It is unclear from the text in several locations whether AltMinGD is an existing algorithm that is analysed to get statistical bounds, or is a new algorithm proposed in this paper. I think it is the former. If so, some sentences and labels might need to be rephrased to avoid saying \"our method\" or similar when referring to it, e.g. line 285.\n\n2) The organisation of the paper could be improved to make the above distinction clearer and improve the clarity of the paper in general. As far as I understand, sections 2 and 3 are essentially background, with the exception of subsection 3.1, which introduces the idea of  AltMinGD-S. I think a more organic structure should follow how the contributions are presented in the introduction: i) background on AltMinGD and similar, ii) statistical analysis of AltMinGD (firt half of section 4) and then iii) introduce idea of AltMinGD-S based on these insights (subsection 3.1 + second half of section 4). In the current form, I struggled to understand what is statistical guarantees on existing methods and what is novel method.\n\n3) is the new variant AltMinGD-S named AltMin in the abstract and experiments? I am finding it very confusing to track the experimental proofs of the claims in the experiments.\n\n4)  If I understood well the high level idea of AltMinGD-S, it only selects the tasks that it finds having low error at a particular iteration, leaving out the high error tasks which risk to \"throw it off\". In this way, is not a bias introduced  in the learning? The model is encouraged to learn some tasks very well and just ignore those that it can not do so well. Maybe the experiments disprove this, but I could not find much evidence in them (as pointed out in point 3).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No unstated limitation or societal impact concern.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "NZFmZ_3Vgqz", "reviewer": "Reviewer_v2WH", "summary": "The paper analyses the problem of **linear** meta-representation learning, and more particularly the *alternating minimization and gradient descent* algorithm (AltMinGD) that has become empirically popular for meta-learning methods. The authors prove statistical guarantees for this algorithm.   \nThey also propose an alternate version, AltMinGD-S, which achieves better per-task sample complexity, but is less tractable in practice because it is based on a task subset selection which relies on the linearity of the representations.\nThen, they show with experiments than the AltMin algorithms achieve smaller errors than the Method of Moments and similar error than the Burer-Monteiro ERM, while being easier to tune. They also study the number of iterations required, and show that the AltMin algorithms (AltMin, AltMinGD, AltMin-S) are the fastest ones.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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:**__  This paper presents a novel and broad statistical analysis in terms of error and sample complexity of AltMin algorithms. [12] also analyzed the statistical guarantees of AltMinGD in the linear case, but only in the noiseless setting and in the view of federated learning. The authors clearly clarify the differences with [12].\n\n__**Quality:**__  The work presented here is considerable, there is a lot of additional results in the appendix, particularly for the AltMin algorithm. The authors state in the paper that the BM-GD algorithm is hard to tune, but the plots provided in the paper do not help in supporting this. The plots in appendix G are important to see the variability of the results of the BM-GD algorithm. The authors discussed the limitations of their work and compared the different bounds on the sample complexity for the algorithms considered.\n\n__**Clarity:**__  I found the paper dense to read, the writing could improve in clarity.  \nI think there is an error when referring to related work, the notations and the definition of the AltMin algorithm is associated to [41], but this paper does not use the same notations, and it never refers to AltMin. I assume the authors wanted to refer to [24]. \nThe numbering and the formulation of the theorems is not the same between the main paper and the appendix. I think the theorem 1 in the paper corresponds to theorem 9 in the appendix and same for the proof, but it is hard to confirm because the formulations and the quantities involved in the two theorems are different. It seems like the theorem are repeated multiple times (with different formulations), which messes up the numbering and makes it difficult to find for the proof corresponding to each theorem.\n\n__**Significance:**__ I found the paper interesting as it provides a strong analysis of the AltMin algorithms, though it is restricted to the linear case. These algorithms are widely used in practice for meta-learning methods. Researchers could leverage this work for a non-linear analysis of AltMin or put into practice the insights from these results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work presented here is very theoretical. To study the possible negative impacts of this kind of work is to study the negative impacts of the whole field. ", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I spent between 6 to 7 hours to review this paper."}, "extra_text": {}}, {"review_id": "0bEsnHUNue4", "reviewer": "Reviewer_GdPm", "summary": "**Summary**: \nThis paper analyses the statistical and computational properties of one particular type of meta-representation learning approaches, which alternatively optimises a shared feature extractor that produces linear representations, and solves inner task-specific linear models taking in the shared linear representations. Under the canonical settings when the feature extractor is linear, they show that the meta-representation learning algorithm can achieve near optimal error rate.\n\n**Contributions**:\n- This paper analyses one family of widely adopted meta-representation learning algorithms they call AltMinGD, and prove a near optimal error rate, following the proof strategy for matrix sensing (which is still significantly different from the linear meta-representation learning problem).\n- This paper introduces a new variation of AltMinGD-S, motivated by their analysis. The new algorithm selects a subset of well-behaved tasks at each iteration, and requires a much smaller number of samples per task to estimate representation.\n- This paper also analyses a variation called AltMin (in appendix) where the outer loop feature extractor is optimised exactly, and proves slightly improved guarantees.\n\n", "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**: \nAlthough there are previous theoretical studies trying to analyse the statistical and computational properties of meta-representation learning algorithms, they often focus on algorithms that have little resemblance to those used in practice, or provide a highly suboptimal error rate. This paper focuses on one particular type of algorithm called AltMinGD, which is successful and popular among previous work. They show that in the canonical setting when the learned shared representation is linear, their analysis of this algorithm would give a near-optimal error rate.\n\nEven though the proving strategy is inspired by those from matrix sensing. The two problems are significantly different, and this paper proves all necessary concentration bounds.\n\nThey also introduce a new variation called AltMinGD-S that would require much fewer samples per task and analyse this new algorithm.\n\n**Quality**:\nThis work has clear motivation and I think they are tackling an important problem with practical implications. However, I am not familiar with related work and the theoretical work on meta-representation learning, I am afraid I cannot comment more on the quality of their analysis. \n\nI would like to only highlight one of my concerns below. I would appreciate it if the authors could give an explanation: If I understand correctly, many previous work on meta-representation learning such as MetaOptNet, ANIL, etc, actually backpropagate through the inner loop minimisation when updating their feature extractors. However, in this paper, (if I am not mistaken), the algorithms *alternatively* optimise the feature extractor and solve the inner loop optimisation for each task. When computing the gradient w.r.t the feature extractor parameters $U$, do you consider the fact that the optimal inner parameter $V^{\\ast}$ is actually dependent on $U$ , and compute gradients accordingly? If yes, I have no further concerns. If not, could the authors discuss whether this difference might lead to different conclusions in their analysis?\n\n**Clarity**:\nThe motivation and assumption of this work are clear and well presented. The theoretical analysis part is intense if the reader did not read background references, but I think the authors have already put effort into making it clear.\n\n**Significance**:\nI believe this paper is tackling an important problem of meta-representation learning that is of practical relevance. The conclusions and proof strategy presented in this work can also be useful for future work.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "**Limitations**:\nThis paper is under a simplified setting where the shared representation is linear, and all tasks are considered when updating the feature extractor (non-stochastic optimisation). But I think the conclusions are still useful, and these are sensible simplifications as a first work to analyse this algorithm.\n\n**Societal Impact**:\nThis is a theoretical work and I have no concerns over its negative societal impact.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns over this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this is a solid contribution to NeurIPS: it tackles a relevant problem in the context of meta-learning and does so by proposing a novel and interesting strategy inspired by the matrix sensing literature. The authors provide a thorough theoretical investigation of the setting considered, which yields insights also on previous work on the topic of linear meta-representation learning. There are a few issues with clarity that authors have addressed during the discussion period and that will need to be taken care of in the final version of the paper. In particular, including material from the Appendix (e.g. plots concerning the behavior of Burer-Monteiro gradient descent) and adding further insight regarding the distinction between AltMin and AltMinGD-S (also explaining why this was not tested in the experiments). 
Decision: Accept (Poster)