How Important is the Train-Validation Split in Meta-Learning?
Authors: Yu Bai
Minshuo Chen
Pan Zhou
Tuo Zhao
Jason D. Lee
Sham M. Kakade
Huan Wang
Caiming Xiong
Venue:  (2021)
Keywords: Learning theory
meta-learning

Abstract: Meta-learning aims to perform fast adaptation on a new task through learning a "prior" from multiple existing tasks. A common practice in meta-learning is to perform a train-validation split where the prior adapts to the task on one split of the data, and the resulting predictor is evaluated on another split. Despite its prevalence, the importance of the train-validation split is not well understood either in theory or in practice, particularly in comparison to the more direct non-splitting method, which uses all the per-task data for both training and evaluation.
We provide a detailed theoretical study on the whether and when the train-validation split is helpful on the linear centroid meta-learning problem, in the asymptotic setting where the number of tasks goes to infinity. We show that the splitting method converges to the optimal prior as expected, whereas the non-splitting method does not in general without structural assumptions on the data. In contrast, if the data are generated from linear models (the realizable regime), we show that both the splitting and non-splitting methods converge to the optimal prior. Further, perhaps surprisingly, our main result shows that the non-splitting method achieves a strictly better asymptotic excess risk under this data distribution, even when the regularization parameter and split ratio are optimally tuned for both methods. Our results highlight that data splitting may not always be preferable, especially when the data is realizable by the model. We validate our theories by experimentally showing that the non-splitting method can indeed outperform the splitting method, on both simulations and real meta-learning tasks.

Under review as a conference paper at ICLR 2021
How IMPORTANT IS THE TRAIN- VALIDATION SPLIT IN META-LEARNING?
Anonymous authors Paper under double-blind review
ABSTRACT
Meta-learning aims to perform fast adaptation on a new task through learning a "prior" from multiple existing tasks. A common practice in meta-learning is perform a Iruin- validation splil where the prior adapts to the task on one split of the data, and the resulting predictor evaluated on another split. Despite preva- Ience, the importance of the train-validation split is not well understood either in theory or in practice, particularly in comparison to the more direct non-splitting method, which uses all the per-task data for both training and evaluation.
We provide detailed theoretical study on whether and when the train- validation split is helpful on the linear centroid meta-learning problem, in the asymptotic set- ting where the number of tasks goes infinity. We show that the splitting method converges to the optimal prior as expected, whereas the non-splitting method does not in general without structural assumptions on the data. In contrast, if the data are generated from linear models (the realizable regime), we show that both the splitting and non-splitting methods converge to the optimal prior. Further, per- haps surprisingly, our main result shows that the non-splitting method achieves a strictly better asymptotic excess risk under this data distribution, even when the regularization parameter and split ratio are optimally tuned for both methods. Our results highlight that data splitting may not always be preferable, especially when the data is realizable by the model. We validate our theories by experimen- tally showing that the non-splitting method can indeed outperform the splitting method, on both simulations and real meta-learning tasks.
INTRODUCTION
Meta-learning, also known as "learning to learn", has recently emerged as a powerful paradigm for learning to adapt to unseen tasks (Schmidhuber, 1987). The high-level methodology in meta- learning is akin to how human beings learn new skills, which is typically done by relating to certain prior experience that makes the learning process easier. More concretely, meta-learning does not train one model for each individual task, but rather learns a "prior" model from multiple existing tasks that it is able quickly adapt unseen tasks. Meta-learning has been successfully applied to many real problems, including few-shot image classification (Finn et al., 2017: Snell et al., 2017), ceperrparramter optimization (Franceschi et al., 2018). low-resource machine translation (Gu et al., 2018) and short event sequence modeling (Xie et al., 2019).
A common practice in meta-learning algorithms is perform sample splitting, where the data within each task is divided into a training split which the prior uses to adapt to task-specific predictor, and a validation split on which we evaluate the performance of the task-specific pre- dictor (Nichol et al., 2018; Rajeswaran et al., 2019; Fallah et al., 2020; Wang et al., 2020a). For example, in a 5-way k-shot image classification task, standard meta-learning algorithms such as MAML (Finn et al., 2017) use 5k examples within each task training data, and use additional examples (c.g. & images, one for each class) as validation data. This sample splitting is believed to be crucial it matches the evaluation criterion at meta-test time, where we perform adaptation training data from a new task but evaluate its performance on unseen data from the same task.
Despite the aformentioned importance, performing the train-validaie from the data efficiency perspective - Because of the split, neither the training nor the evaluation stage is able to use all the available per-task data. In the few-shot image classification example,
split has a potential drawback

---

Under review as a conference paper at ICLR 2021
each task has total of 6k examples available, but the train- vaindvalidationn split forces to use these data separately in the two stages. Meanwhile, performing the only option in practice: there exist algorithms such as Reptile (Nichol & Schulman, 2018) and Meta-MinihatchProx (Zhou et al., 2019) that can instead use all the per-task data for training the task-specific predictor and also perform well empirically on benchmark tasks. These algorithms modify the loss function in the outer loop so that the training loss no longer matches the meta-test loss, but may have the advantage in terms of data efficiency for the overall problem of learning the best prior. So far it is theoretically unclear how these two approaches (with/without train- vaiinvalidation split) compare with each other, which motivates us to ask the following
split is also not the
Question: Is the train-validation split necessary and optimal in meta- meta-learning?
In this paper, we perform detailed theoretical study on the importance of the train-validation split. We consider the linear centroid meta-learning problem (Denevi et al., 2018b), where for each task we learn linear predictor that is close to a common centroid in the inner loop, and find the best centroid in the outer loop (see Section 2 for the detailed problem setup). This problem captures the essence of meta-learning with non-linear models (such as neural networks) in practice, yet is sufficiently simple that allows precise theoretical characterization. We use a biased ridge solver as the inner loop with a (tunable) regularization parameter, and compare two outer-loop algorithms of either performing the train- validation split (the train-val method) or using all the per-task data for both training and evaluation (the train-train method). Specifically, we compare the two methods when the number of tasks T is large, and examine if and how fast they converge to the (properly defined) best centroid at meta-test time. We summarize our contributions as follows:
On the linear centroid meta-learning problem, show that the train- validation split is necessary in the general agnostic setting: As T + oc, the train-val method converges to the optimal centroid for test-time adaptation, whereas the train-train method does not without further assumptions on the tasks (Section 3). The convergence of the train-val method is expected since its (population) training loss is equivalent to the meta-test time loss, whereas the non-convergence of the train-train method is because these two losses are not equivalent in general.
Our main theoretical contribution is to show that the train-validation split is not necessary and even non-optimal, in the perhaps more interesting regime when there structural assumptions on the tasks: When the data are generated from noiseless linear models, both the train-val and train- train methods converge to the common best centroid, and the train-train method achieves a strictly better (asymptotic) estimation error and test loss than the train-val method (Section 4). This is in stark contrast with the agnostic case, and suggests that data efficiency may indeed be more important when the tasks have a nice structure. Our results build on tools from random matrix theory in the proportional regime, which may be of broader technical interest.
We perform meta-learning experiments fication tasks, showing that the train-train method consistently outperforms the train-val method (Section 5 & Appendix D). This validates our theories and presents empirical evidence that sample- splitting may not be crucial; methods that utilize the per-task data more efficiently may be preferred.
simulations and benchmark few-shot image classi-
1.1 RELATED WORK
Meta-learning and representation learning theory Baxter (2000) provided the first theoretical analysis of meta-learning via covering numbers, and Maurer et al. (2016) improved the analysis via Gaussian complexity techniques. Another recent line of theoretical work analyzed gradient-based meta-learning methods (Denevi et al., 201 8a; Finn et al., 2019; Khodak et al., 2019; Ji et al., 2020) and showed guarantees for convex losses by using tools from online convex optimization. Saunshi et al. (2020) proved the success of Reptile in one-dimensional subspace setting. Wang et al. (2020b) compared the performance of train-train and vaan-vaa methods for learning the learning rate. Denevi et al. (2018b) proposed the linear centroid model studied in this paper, and provided generalization error bounds for train-val method; the bounds proved also hold for train-train method, so are not sharp enough to compare the two algorithms. Wang et al. (2020a) studied the convergence of gradient- praddeent-baeed meta-learning by relating to the kernelized approximation. On the representation learning end, Du et al. (2020): Tripuraneni et al. (2020a;b) showed that ERM can successfully pool data across tasks to learn the representation. Yet the focus is on the accurate estimation of the common representation, not on the fast adaptation of the learned prior. Lastly, we remark that there
2

---

Under review as a conference paper at ICLR 2021
analyses for other representation learning schemes (McNamara & Balcan, 2017; Galanti et al., 2016; Alquier et al., 2016).
Empirical understandings of meta-learning Raghu al. (2020) investigated the representation learning perspective of meta-learning and showed that MAML with a full finetuning inner loop mostly learns the top-layer linear classifier and does not change the representation layers much. This result partly justifies the validity our linear centroid meta-learning problem in which the fea- tures (representations) are fixed and only a linear classifier is learned. Goldblum et al. (2020) investi- gated the difference of the neural representations learned by classical training (supervised learning) and meta-learning, and showed that the meta-learned representation is both better for downstream adaptation and makes classes more separated than the classically trained one. Although the classical training method in (Goldblum et al., 2020) does not perform train- validatinn split, is not exactly the same the train-train method considered in this work it effectively performs supervised learning on all tasks combined and does not do a per-task adaptation.
Multi-task learning Multi-task learning also exploits structures and similarities across multiple tasks. The carliest idea dates back to Caruana (1997); Thrun & Pratt (1998); Baxter (2000), initially in connections to neural network models. They further motivated other approaches using kernel methods (Evgeniou et al., 2005; Argyriou et al., 2007) and multivariate linear regression models with structured sparsity (Liu al., 2009; 2015). More recent advances on deep multi-task learning focus on learning shared intermediate representations across tasks Ruder (2017). These multi-task learning approaches usually minimize the joint empirical risk over all tasks, and the models for different tasks are enforced to share large amount of parameters. In contrast, meta-learinn only requires the models to share the same "prior", which is more flexible than multi-task learning.
2 PRELIMINARIES
In this paper, we consider the standard meta-learning setting, in which we observe data from T 2 supervised learning tasks, and the goal is to find prior (or "initialization") using the combined data, such that the (T + 1) new task may be solved sample-efficienly using the prior.
Linear centroid meta-learning We instantiate our study the linear centroid meta-learning problem (also known as learning to learn around a common mean, Denevi et al. (201 2018))), where we wish learn a task-specific linear predictor w. _d in the inner loop for each task t, and learn "centroid" Wo in the outer loop that enables fast adaptation to w, within each task:
Find the best centroid wo E Rd for adapting to a linear predictor w, on each task t.
Formally, we assume that we observe training data from T > tasks, where for each task index t we sample a task pt (a distribution over Rd R) from some distribution of tasks I1, and observe examples (x) E Raxd x Rn" that are drawn i.i.d. from pt:
Pt II, (x) = ((x,,, " where (x+,) Br,)) iid ~ Pt-
We do not make further assumptions (n, d): in particular, allow the underdetermined setting n & d, in which there exists (one or many) interpolators w, that perfectly fit the data: X,W, = Yr-
Inner loop: Ridge solver with biased regularization towards the centroid Our goal in the inner loop is to find a linear predictor w, that fits the data in task while being close to the given "centroid" Wo d We instantiate this through ridge regression (i.e. linear regression with L, regularization) where the regularization biases w, towards the centroid. Formally, for any Wo E Rd and any dataset (X, y), we consider the algorithm
Ax(wo; x) := arg min - Xw yl1 + \|w woll" wo + (X X +nLa) - ' X
w
where À is the regularization strength (typically a tunable by ||w - l this inner solver encourages the solution to be close to wp, as we desire. Such regularizer is widely used in practical meta-leamiig algorithms such as MetaOptNet (Lee al.,
As we regularize
3

---

Under review as a conference paper at ICLR 2021
2019) and Minbbbbitttttcrrxx (Zhou et al., 2019). In addition, À - O, this solver recovers gradient descent fine-tuning: we have
Ao(wo: x,y) == lim Ax y) x-0
X (y Xwo) = arg min Xw=y ||w woll
(where X E R denotes the pseudo-inverse of X). This is the minimum -isttaaced interpolator of (X, y) and also the solution found by gradient descent on Xw yl| initialized at wo. Therefore our ridge solver with À > 0 can be seen generalized version of the gradient descent solver used in MAML (Finn et al., 2017).
Finding the best centroid In the outer loop, our goal find the best centroid wo- The standard approach in meta-learning is to perform a train-validation split, that is, (1) execute the inner solver on first split of the task-specific data, and (2) evaluate the loss on second split, yielding function of Wo that we can optimize. This two-stage procedure can be written as
Outer loop:
Compute we(wo) = Awoo Xtrinn yy and evaluate ||y:a
X w. (wo)]l
where (Xtrain, .ytrain) {(x,, ye,)) v(,))) and (Xy²), yyal) {(xi,i, vt,;) (.mm)+)mn++)) two disjoint splits of the per-task data (x) of size (n1, n2), with n1 + r2 Written concisely, this is to consider the "split loss"
1 | X (wo: X.rain .y y|r
ee (w))
2n1
In this paper, we will also consider an alternative version, where we do not perform the train- validation split, but instead all the per-lask data for both training and evaluation. Mathemati- cally, this is to look at the "non-split loss""
(wo) 1 ly: (wo: yt)
(3)
2n
Our overall algorithm is solve the empirical risk minimization (ERM) problem on the T' observed tasks, using either one of the two losses above:
tr- (wo) = T
etr (wo) and (wo) = T
1
ge (wo),
1=1
(4)
W 0,T
(troval.tr-tr) = arg min trr- (wo).
L
Wo
Let L (tttvvll (wo)) : (x.,.I((X..)) (eftr-waltt-tt)) (wo) be the population risks.
(Meta-YTest time The meta-test time performance of any meta-learning algorithm is a joint func- tion of the (learned) centroid wo and the inner algorithm Alg. Upon receiving new task pr+1 II and training data XXT+1yT-il E Rn x R", we run the inner loop Alg with prior wo on the training data, and evaluate it on an (unseen) test example (x', y') pr+1:
(x' Alg(wo: X7 - vr
test (Wo: Alg) EE (X (XW.)) (
Additionally, for both train-val and train-train methods, we need ensure that the inner loop used for meta-test is exactly the same as that used in meta-training. Therefore, the meta-test performance for the train-val and train-train methods above should be evaluated as
X, (
L test W,T AA.mi), L (w).7) b
L test (Wo.T Ax.a),
where Axm denotes the ridge solver with regularization strength A > 0 on m I n data points. Finally, we let
Wo.- (A; arg min (wo)
(5)
denote the best centroid if the inner loop uses As,a. The performance of the train-val algorithm w should be compared against (X, whereas the train-train algorithm W should be compared against Wo, (X,
with small step-size, gradient flow.
4

---

Under review as a conference paper at ICLR 2021
2.1
SETTING THROUGH ASYMPTOTIC ANALYSIS
In this paper we are interested in the lask-abundant setting where we fix some finite (d, n) and let T be very large. We analyze such a task-abundant setting through the asymptotic analysis framework, that is, examine the limiting properties of the estimator (e.g. W 0,r
(trtta))tttt)))) as + cc. Here we set up the basic notation of asymptotic analysis required in this paper. We emphasize that our large T setting captures practical meta-learning scenarios; for example, 5-way image classification minilmageNet (Ravi& & Larochelle, 2017) contains ((5)) diverse tasks (at train time).
Asymptotic rate of estimation excess risk Let L be any population risk with minimizer Wo,+ (which we assume is unique), LT be the empirical risk on the observed data from T tasks, and Wa,r be the minimizer of LT (i.e. the ERM). We say that Wo,r is consistent if Wo,7 + Wo,, in probability as T + oo. For consistent ERMs, we define asymptotic parameter estimation error (in MSE loss) and asymptotic excess risk as follows?:
AsymMSE(Wo.r) == lim T E W 11] 7-500
AsymExccesRRssk == lim T' B.L((W,))) L(wo..)] T-x
We emphasize that asymptotic statements are more refined than non-asymptotic O()) style upper bounds in the T + oo limit: they already imply the (MSE, excess risk} has order (1//T) and specifies the leading constant.
THE IMPORTANCE OF SAMPLE SPLITTING
(tr-val,tre-rr) defined in (4) converge to the best test-time centroid (A; or Wo,, (A; n)) (defined (5)) respectively T in the general situation where we do not make structural assumptions on the data distribution Pt-
We begin by analyzing whether the algorithms Wor
Proposition (Consistency and asymptotics of train-val method). Suppose Ex-p, [xx]] > 0,
Expep [||||"]] сo and (x, []] [|yl]] oo for almost surely all pt II. Then for any A > and any (M1, T22) such that nı + n22 = n, the train-val method Wh, converges to the best test-time
tat--al + +oo (A, n21) almost surely as T + oc. Further, we have centroid: 0,T
AsymMSE ( tattwal tr tr test (Wo. (X, m1) Cov Cov(Vettial (Wo, (A, V 2 test (Wo, (2, n)))),
AsymExccssRisk/.a W
tr-rvaa tr (V- L (A, Cov (Vet (w,, 0,T
Proposition 2 (Inconsistency of train-train method). There exists a distribution of tasks II on d= satisfying the conditions in Proposition I which the train-train method does not converge the best test-time centroid: for any n. 2 and any X >> O, the estimation error | Wo, n)ll and the excess risk X,m. 0,7 - L (Wo, (X, n)) are both bounded away from 0 almost surely as xc.
Propositions and 2 justify the importance of sample splitting: the train-val method converges to the best test-time centroid, whereas the train-train method does not converge to the best centroid in general. The reason behind Proposition is simple: the population loss tr-val for the train- val method is indeed equal to the test-time loss test making the train-val method proper ERM for the meta-test time we care about, and thus the consistency and asymptotic normality follow from classical results for the ERM (e.g. (Van der Vaart, 2000; Liang, 2016)).
In contrast, for the train-train method, expected loss tr is general not equivalent to Lestt tr- measures the in-sample prediction error of the per-task predictor, whereas test measures the out-of-sample prediction error. Consequently, the population minimizers of Liest and L are not equal in general, which leads to Wo, converging to the minimizer of tr not of A The proof of Proposition 2 constructs a simple counter-example in d = 1, but we expect such a mismatch to generally hold in any dimension. Appendix A gives the proofs of Proposition and 2.
These definitions assume that the expectation exists for finite T: the more general definition can be found Appendix A.I.
5

---

Under review as a conference paper at ICLR 2021
4 IS SAMPLE SPLITTING ALWAYS OPTIMAL?
Proposition 2 states a negative result for the train-train method, showing that it does not converge to the best test-time centroid without further assumptions on the data distribution. However, such a negative result is inherently worst-case, and does not preclude the possibility that there exists a data distribution on which the train-train method can also work well. In this section, we construct a simple data distribution in which we can analyze the performance of both the train-val and the train-train methods more explicitly, showing that sample splitting is indeed not optimal, and the train-train method can work better.
Realizable linear model We consider the following instantiation of the (generic) data distribution assumption in (1): We assume that each task pt specified by a W, E Rd sampled from some distribution II (overloading notation), and the observed data follows the noiseless linear model with ground truth parameter Wy:
yt - - W
where the inputs Xt,5 jid N(O, Ia) and are independent of w,, We assume that has finite second moment (i.e. Ew.~n IIl we 11 < co). Note that when n 2 d, we are able to perfectly recover w, for all t (by solving linear equations), therefore the problem in the inner loop is in a sense "easy"; when < d, we cannot hope for such perfect recoveries. Our goal in the outer loop is to find the best wo. measured by the test loss Xx, for the train-train method and Lxn for the train-val method.
4.1 COMPARISON OF TRAIN-TRAIN AND TRAIN-VAL ON THE REALIZABLE MODEL
We begin by showing that on this task and data distribution, the population best centroids wo,, n1) arg min Lx (wo) is the same for any (A, n), and both the train-val and train- train methods are asymptotically consistent and converge to same best centroid.
Theorem 3 (Consistency of both train- val and train-train methods). On the realizable linear model (6), the test-time meta loss for all X > 0 and all n is minimized at the same point, that is, the mean of the ground truth parameters:
Wo, (A, n) = arg min 3 (wo) = Wo., == Eww-nlwel, for all X >> 0, n.
wo
Further, both the train-val method and the train-train method are asymptotically consistent: for any X > 0, n, and (n1, n2). we have
w (n1, n2; X) - Wo.+ and W A) Wo, almost surely as - co.
See its proof in Appendix B.I. Theorem 3 shows that both train-val and train-train methods are consistent, and they converge to the same optimal parameter Wo,, which the mean of w,- This is a consequence of the good structure in our realizable linear model (6): at high level, Wo,, is indeed the best centroid since it has (on average) the closest distance to a randomly sampled w.-
Theoerem 3 suggests that now able compare performance of the two methods based their asymptotic parameter estimation error (for estimating Wo,-). Throughout the rest of this section, let
R² := TE. ||: wo.-
denote the variance of w., We are now ready to state our main result.
Theorem 4 (Comparison of asymptotic MSE of the train-val and train-train methods). In the dinensiinnsi limiting regime d, n - oc, d/n + y E co), the optimal rate of the train- train method obtained by tuning the regularization
(0, 00) satisfies
5
5
inf lim d////////////// Ast.:./dd//yyyyyMMMas.s X
AsymMSE (warttr (n; 2)) inf PM, R2 ASO
1+
+r R².
+
27
27
+ 1 (A
where Ph, = = 1)3
47)2 /////((2)))))) + + 1)2 47)
3/2 47/3//2
and the inequality becomes equality at 7 = In contrast, the optimal rate of the train-val method by tuning the regularization X E (0, xo) and split ratio E (0, is
infx>0.sE(0.1 lim -oe, AsymMSE outr-val (ns n(1 - s); = (1 R As max(1 + 5-/27, 27 + + < 1 (ty > 0), the train-tratt method achieves a strictly better asymptotic rate than the train-val method when X and are optimally tuned in both methods.

---

Under review as a conference paper at ICLR 2021
Implications Comparison between the analytical upper bound max + 52 5/27 + for train-train (1+ for train-val in Theorem 4 shows that the train-train method achieves a strictly better asymptotic MSE than the train-val method, for any Y > 0². (See Figure ((a) for visualization of the exact optimal rates and the upper bound (+).) Perhaps surprisingly. this suggests that the train- train method is not only "correct" (converging the best centroid), but can be even better than the train-val method, when the data is structured. While the "correctness" of the train-train method is a consequence of the realizable linear model, we believe its superior asymptotic MSE due the fact that the train- taiintrrin method is able to use the data more efficiently than the train-val method.
Also, while we reached such a conclusion on this particular problem of linear centroid meta-learning, we suspect that this phenomenon to be not restricted to this problem, and may hold in more general- ity when data structured or when the signal-to-noise ratio high. As we are going to see, our real data experiments in Section 5.2 indeed suggests that the superiority of the train-train method may also hold on real meta-learning tasks with neural networks.
4.2 PROOF IIGILIGITTS OF THEOREM 4
Here we sketch the technical highlights in proving Theorem We defer the full proof to Ap- pendix B.5.
Exact asymptotic MSE for both methods The proof begins by calculating the exact asymptotic MSE for both methods, which we provide in the following theorem.
Lemma 5 (Exact asymptotic rates of the train-val and train-train methods). Suppose that Per-tr
R +x)+ and Per-val
E (I ((o//))) +x)²)
+(n++1) Ef_ +
(B(ELL) of /(oo")+/0)
Ei ( +xp])*
where for any n. of (n) 2... (n) denotes the eigenvalues of the matrix X X E Raxd, where we recall Xt E Raxd is a random matrix with i.idd. standard Gaussian entries. For any (n, d), we have on the realizable linear model (6) that
d.R. Pervval
cetr-tr AsymMSE(w (Wo, A)) ddR² Per-trs
tetrval AsymMSE WoT (11, A))
712
See its proof in Appendix B.2. Lemma 5 follows straightforwardly from the classical asymptotic result for empirical risk minimization (Van der Vaart, 2000) and simplifications of certain matrix traces in terms of the spectrum of the empirical covariance matrix n Σn X,X!
Simplifying and optimizing the asymptotic MSEs The asymptotic MSEs of the train- train and train-val method in Lemma 5 are not yet directly comparable, the quantities Ptr-tr and Ptr-val depend on the spectrum of the empirical covariance matrix as well as additional tunable parameters such X and (M1, n2) (for the train-val method). Towards proving Theorem 4, further simplify the rates and analyze the optimal tunable parameters, using separate strategies for the two methods:
For the train-val method, we show that the optimal tunable parameters for any (n, d) is taken at special case À = oo and n2) = (0, n). at which the rates only depends on 1 Xttrinn xtrain through its rank (and thus has a simple closed-form). We state this result in Corollary 8. The proof builds on algebraic manipulations of the quantity Ptr-val and can be found in Appendix B.3.
my
For the train-train method, we apply random matrix theory to simplify the spectrum of _ x, in the proportional limit where d, + oo and d/n stays a constant (Bai & Silverstein, 2010; Anderson et al.. 2010), and obtain a closed-form expression of the asymptotic MSE for any À > O, which we can analytically optimize over X. We state this result in Theorem 9. The proof builds on the Steiltjes transform and its "derivative trick" (Dobriban et al., 2018), and is deferred to Appendix B.4.
The same conclusion also holds for the asymptotic excess risk, as the Hessian of the excess risk is rescaled identity, Appendix B.2.
7

---

Under review as a conference paper at ICLR 2021
5 EXPERIMENTS
5.1 SIMULATIONS
We experiment on the realizable linear model studied Section 4. Recall that the observed data of the 1-th task are generated as
nd NO, Ia). Yr = X,W,, with X1,5
We independently generate W, lid ,(Wo,,, Ia/Vd), where Wu,+ is the linear centroid and the cor- responding n2 = 1 here. The goal is to learn the linear centroid Wo.- using the train-train method and train-val method, i.e., minimizing E and Éx respectively. Note that both Ltetr and L are quadratic in Wo. therefore, we can find the close-form solutions t 0,7 (ttr-tt.tr-vvl) We measure the
performance of train-train and train-val methods using the fg-error ||
(tr-tr.tr-aal) 0,T
1|2.
We present the comparison among train-train and train-val methods in Figure 1 with scatter plots representing the simulation outputs under different settings. Across all the simulations, we well-tune the regularization coefficient Ả in the train-train method, and use a sufficiently large À = 10000 in the train-val method according to Corollary The simulated results concentrate around the reference curves corresponding to our theoretical findings. This corroborates our analyses and demonstrates the better performance of train-train method on the realizable linear model.
We additionally investigate the effect of averaging the loss over multiple splits in the train- val method (a "cross-validation" type loss) rather than the vanilla single split. We show that such cross- coossvvaliatiinn can indeed improve over the vanilla single-split train-val method. We also experi- ment with the stronger "leave-one-out style cross cross-validatee validation and show that it achieves better MSEs than the constant-fold cross cooss-valdaation (Appendix E).
traall
Deval, nil-1
0.
Trival, m1 optimal
10"
tn-val, ref. curve 6/I
ref. curve 1 4d/Sp
Mixe RL1
Tp-tr,
le-tr, optimul
4/T
rcc.
to-kr.
PCE curve
teerr.
10"
d/ Euilo
Number of tukka
d/n ratio with Bood towel) 60
Optinml seymptotic MSE WoY
(teer, (rom))
(4)
Figure Panel (a) presents the optimal (wy: (blue) in Theorem via grid search, and the optimal AsymMSE(WH)) (wtrr))) in Corollary with n. 0 (orange) and nu = 5 (green), as well as the upper bound of (W8F) (magenta) Corollary 4. The optimal ( O.T reference curves in plots (b) and (c). Panel (b) plots the fz-error of W
are used as [tr-tr,t-val) as the total number of tasks
increases from 20 1000 with increment of 20. We fix data dimension d 60 and per-task sample size n 20. the train-val method, we experiment on Ti and n Panel (c) shows the scaled (by T) fz-error of w vral the ratio d/n varies from 0 (n 20 and T 1000 are fixed).
0.T
5.2 FEW-SHOT IMAGE CLASSIFICATION
We further investigate the comparison between the train-train and train-val type methods in few- shot image classification on minilmageNet (Ravi & Larochelle, 2017) and ticredImageNet (Ren et al., 2018).
Methods We instantiate the train-train and ral method in the centroid meta-leaming setting with a ridge solver. The methods are almost exactly the same as in our theoretical setting in (2) and (3), with the only differences being that the parameters w, (and hence wo) parametrize deep
8

---

Under review as a conference paper at ICLR 2021
neural network instead of a linear classifier, and the loss function is the cross- eross-entropy instead of squared loss. Mathematically, we minimize the following two loss functions:
1
Lx, LX (wo)
4 ger-val (wo)
arg min ((w,; Xtrain yf ) + X A//w, woll? xxxx y%a
T
T
T
1
(wo) = T
pt-er (wo) = T 8
arg min (ww; Xe. + A liwe - wo woll :e,,
W1
where Yz) is the data for task t of size n, and (x!rinn b y!rai) and yyal) is a split of the data of size (21) We note that both loss functions above have been considered in prior work (I in iMAML (Rajeswaran et al., 2019), and L in Meta- Betaa-MinbatccProx (Zhou et al., 2019)), though we use slightly different implementation details from these prior work to make sure that the two methods here are exactly the same except for whether the split is used. Additional details about the implementation can be found in Appendix D.
Experimental settings We adopt the episodic training procedure (Finn et al., 2017: Zhou et al., 2019; Rajeswaran al., 2019). In meta-test, we sample a set of N-way (K + 1))-hot test tasks. The first K instances are for training and the remaining one is for testing. In meta-training, "higher way" training strategy. We set the default choice of the train-validation split ratio to be an even split n2 n2 = n/2 following Zhou et al. (2019); Rajeswaran
use the
al. (2019). For example, for a 5-way 5-shot classification setting, each task contains 5 x (5 + 1) = 30 total images, and we set n, R2 = 15. (We additionally investigate the optimality of this split ratio in Appendix D.1.) We evaluate both methods under the transduction setting where the information is shared between the test data via batch normalization. We report the average accuracy over 2, 0.0 random test episodes with 95% confidence interval.
Results Table presents the percent classification accuracy on minilmagenet and tieredImageNet. We find that the train-train method consistently outperforms the train-val method. Specifically, on minilmageNNt, train-train method outperforms train-val by 2.01% and 3.87% on the 1-shot 5-way and 5-shot 5-way tasks respectively; On taared train-train on average improves by about 6.40% on the four testing cases. These results show the advantages of train-train method over train- val and support our theoretical findings in Theorem 4.
Table 1: Few-shot classification accuracy (%) the minilmageNet and tieredImageNet datasets.
minilmage
method
1-shot 5-way
5-shot 5-way
1-shot 20-way
5-shot 20-way
train-val
48.76 + 0.87
63.56 + 0.95
17.52 0.49
21.32 + 0.54
train-train
50.77 1 0.90
67.43 + 0.89
21.17 1: 0.38
34.30 1: 0.41
meredImaaee
method
1-shot 5-way
5-shot 5-way
1-shot 10-way
5-shot 10-way
train-val
50.61 + 1.12
67.30 = 0.98
29.18 + 0.57
43.15 + 0.72
train-train
54.37 0.93
71.45 0.94
35.56 0.60
54.50 + 0.71
CONCLUSION
We study the importance of train-validation split on the linear-centroid meta-learning problem, and show that the necessity and optimality of aain-validation split depends greatly on whether the tasks structured: the sample splitting is necessary in general situations, and not necessary and non- optimal when the tasks are nicely structured. It would be of interest to study whether a similar conclusion holds other meta-learning problems such as learning a representation, or whether our insights can be used towards designing meta-learning algorithms with better empirical performance.
REFERENCES
Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret bounds for lifelong learning. arXiv preprint 16Xiv:16/0.0800 2016.

---

Under review as a conference paper at ICLR 2021
Greg W Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction random matrices, volume 118. Cambridge university press, 2010.
Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Multi-task feature learning. In Advances in neural information processing systems, pp. 41-48, 2007.
Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
Jonathan Baxter. A model of inductive bias learning. J. Artif. Int. Res., 2000.
Rich Caruana. Multitask learning. Machine Learning, 28))) 1997. ISSN 1573-0565, doi: 10. 10.1023/A11003379667774 URL
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to- learn with statistical guarantees. arXiv preprint http://p.....c......0.1011111111
2018a.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around a common mean. In Advances in Neural Information Processing Systems, pp. 10169-10179, 2018b.
Edgar Dobriban, Stefan Wager, et al. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
Simon $ Du, Wei Hu, Sham M Kakade, Jason Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09434 2020.
Theodoros Evgeniou. Charles A Micchelli. and Massimiliano Pontil. Learning multiple tasks with kereel methods. Journal of machine learning research, 6(Apr):615-637, 2005.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-lcarning algorithms. In International Conference on Artificial Intelli- gence and Statistics, pp. 1082-1092, 2020.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1126-1135, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine Online meta-learning. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimilano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. arXiv preprint 1rXiv:1806.04911 04910, 2018.
Tomer Galanti, Lior Wolf, and Tamir Hazan. theoretical framework for deep transfer learning. Information and Inference: Journal of the IMA, 5(2):159-209) 2016.
Micah Goldblum, Steven Reich, Liam Fowl, Renkun Ni, Valeriia Cherepanova, and Tom Gold- stein. Unraveling meta-leaming: Understanding feature representations for few-shot tasks. arXiv preprint arXiv:2002.06753 2020.
Jiatao Gu, Yong Wang, Yun Chen, Kyunghyun Cho, and Victor OK Li. Meta-learning for low- resource neural machine translation. arXiv preprint arXiv: 100..8888.0333 2018.
Kaiyi Ji, Jason D Lee, Yingbin Liang, and Н Vincent Poor. Convergence of meta-learning with
task-specific adaptation over partial parameters. arXiv preprint arXiv:2006.09486 2020.
Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient-based meta-
learning methods. arXiv preprint (tt:::990002711 2019.
A. Krizhevsky, Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. pp. 1097-1105, 2012.
10

---

Under review as a conference paper at ICLR 2021
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 10657-10665, 2019.
Perey Liang. Cs229t/sta231: Statistical learning theory (winter 2016), 2016.
Han Liu, Mark Palatucci, and Jian Zhang. Blockwise coordinate descent procedures for the multi- task lasso, with applications to neural semantic basis discovery. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 656, 2009.
Han Liu, Lie Wang, and Tuo Zhao. Calibrated multivariate regression with application to neural semantic basis discovery. Journal of machine learning research: JMLR, 16:1579, 2015.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. The Journal of Machine Learning Research, ((1):2853-2884) 2016.
Daniel McNamara and Maria-Florina Balcan. Risk bounds for transferring representations with and without fine-tuning In Proceedings the 34th International Conference on Machine Learning- Volume 70, pp. 2373-2381. JMLR. JMLRR org, 2017.
A. Nichol and J. Schulman. 180.:00939,99 2, 2018.
Reptile: a scalable metalearning algorithm.
arXiv preprint
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv: (rXi::/803.02999, 2018.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning feature reuse? towards understanding the effectiveness of maml, In International Conference on Learning Rep- resentations, 2020. URL https: http:ps:///ppeeeeeeee http:///ppeeeieeeeeeeeeeeeeeeeet net wwt.:neeeeeetieeeeeeeeeeeeeeeeee
IKg.KCEEPP..
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. In Advances in Neural Information Processing Systems, pp. 113-124, 2019.
S. Ravi and H. Larochelle. Optimization as a model for few-shot learning. 2017.
M. Ren, F. Triantafillou, S. Ravi, J. Snell, K. Swersky, J. Tenenbaum, H. Larochelle, and R. Zemel. Meta-leaming for semi-supervised few-shot classification. arXiv preprint arXiv:1803.0m 00676, 2018.
Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint 17060000060 2017.
O. Russakovsky, Deng, H. Su, Krause, S. Satheesh, S. Ma, Huang, A. Karpathy, A. Khosla, and M. Bernstein. Imagenet large scale visual recognition challenge. 1152))211-222,2000 2015.
Nikunj Saunshi, Yi Zhang, Mikhail Khodak, and Sanjeev Arora. A sample complexity separation between non-convex and convex meta-learning arXiv preprint arXiv:2002. 1177, 2020.
Jürgen Schmidhuber. Evolutionary principles in self-referential learning, or on learning how to learn: the meta-meta.... hook. PhD thesis, Technische Universität München, 1987.
J. Snell, K. Swersky, and R. Zemel. Prototypical networks for few-shot learning. pp. 4077-4087, 2017.
Sebastian Thrun and Lorien Pratt. Learning to Learn: Introduction and Overview, pp. 3-17. Springer US Boston, MA, 1998. ISBN 17-117-5-----55522222 doi: 10.1007/978-11461155 1-6615-5529-9 URL hwtph:ttt///cc.ccm / /oo. org / 10. 1
1-4615 51155555529211111
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. arXiv preprint arXiv:2002.1 1684, 2020a.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The impor- tance of task diversity. arXiv preprint arXiv:200../1650, 2020b.
Aad W Van der Vaart. Asymptotic statisties, volume Cambridge university press, 2000.

---

Under review as a conference paper at ICLR 2021
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Haoxiang Wang, Ruoyu Sun, and Bo Li. Global convergence and induced kernels of gradient-based meta-learning with neural nets. arXiv preprini urXiv:2006. /4606, 2020a.
Xiang Wang, Shuai Yuan, Chenwei Wu, and Rong Ge. Guarantees for tuning the step size using learning-to-learn approach. arXiv preprint arXiv:2006. 10::: 2020b.
Yujia Xie, Haoming Jiang, Feng Liu, Tuo Zhao, and Hongyuan Zha. Meta learning with relational information for short sequences. In Advances in Neural Information Processing Systems, pp- 2019.
Pan Zhou, Xiaotong Yuan, Huan Xu, Shuicheng Yan, and Jiashi Feng. Efficient meta learning via minibatch proximal update. Advances in Neural Information Processing Systems, pp. 1534-
2019.
A PROOFS FOR SECTION 3
A.1 DETAILED INTRODUCTION ON ASYMPTOTIC ANALYSIS
Here we provide more details on the asymptotic analysis framework sketched in Section 2.1.
In typical scenarios, for consistent ERMs, the limiting distribution of Wo,r r is asymptotically normal with known covariance matrix, as is characterized in the following classical result (see, c.g. Van der Vaart (2000, Theorem 5.21) and also Liang (2016)).
Proposition 6 (Asymptotic normality and excess risk of ERMs). Assume the population minimizer Wo, unique and the ERM Wo,T is consistent (i.e. converges to Wo., in probability as T + oc). Further assume the following regularity conditions:
(a) There exists some random variable A, = A(r,, Xt) such that E[A}]] < oc and
[[ee(w1) ( & A, l|w] - w2ll
for all W1, W2 E Rd.
(b) E < oo;
(c) tiice-differentiable with V V2L(wo,)) >
then the ERM Wo,r is asymptoticallly normally distributed, with
VT (Wo.T - Wo,-) 4 N(D, (TZN
Pws
T (L(Wo.T) - L(wo..)) & A AT A where Pw-
where 4 denotes convergence in distribution and & RRd R is the loss function single task.
When this happens, we define the asymptotic rate of estimation (in MSE loss) and asymptotic excess risk Wo,7 as those of its limiting distribution:
AsymMSE w == EA~Pa
AsymExcessRisk Wo.r) = EA~Pa AV*L tr >
A.2 PROOF OF PROPOSITION 1
Equivalence of test-time risk and training loss for train-val method We first show that
tr-vval (Wo) = E.(trrvallwwa A (Wo)
12

---

Under review as a conference paper at ICLR 2021
for all Wo, is, the population meta-test loss is exactly the same the population risk of the train- val method. This is straightforward: as the tasks are i.i.d. and Ax(wo; Xtraan yt is independent of the test points (Xya), yral), have for any Wo that
1
Big Bletoval (wo)] - (X,.),
Ni
X Aa(wo X
ttainn
2n12
val Ut,1
valT 1,1
As Xtrain y. ))aan))) 2
(3/ - X" AAni (wo: Xr+1. 2)
= E
Pry1~11, WI (1))) w/)
2
test X,11 (Wo).
Therefore the train-val method is acutally a valid ERM for the test loss L and it remains to show that the train-val method is (itself) consistent.
Consistency
We expand the empirical risk of the train-val method as
T
T.q.val (Wo)= = T
yt val
Xyal Ax Xtrain "r y |
2n2
1=1
y
+ (xtran Xtrain + ALa) Xtrain (yrtain X; wo)]]l (wo X
T
2112
||yall
X (X; X xtrain + n1Alaa) xtrain paiin train
x. A(Xtrain
n xtrain ni Ala) -woll
T
2112
wo My - w.J by + const,
2
where
T
XyalT Xyal
Mr
2 2xttrain Xtrain /nn + AL2)
(X xtrain /m) + Ala) -1
122
T
by = T
Σ
A( A(xtrain train
Xtrain/ /ni + AIa)
xval (y
x (xtrain T xtrain + n2 ALa)
ttrain y train)
Noticing that (Xtrain Xtrain /nn
and by the assumption that (x,)) [xx (xxx)) [xy] < cc, we have |||[M]]| || oo and [|[|by II] < co. Since the task Pi 's are i.i.d.
by the law of large numbers, we have with probability one that
Mr B[
XvalT X
2 (Xtrain Xtrain /ni ALa)
(Xtrain Xtrain /nn +Ia)
-1
(8)
n2
-E,.. Xx(ttrain
X.rrain /nn ALa) Ala) -1E, [xtrain] xtrain /nj + Ald) (1))-1]+ 0,
(where E, Eexpp (xx T] 0) and
bt + E(bT]
X(X x(Xtrain xtrain /ni + XIa) 1 Xxal (yxal - (xtraini xtrain + ALa) Xtrrin ytrain)
(X..
n2
< 00
(9)
as 7 - xc. Therefore, by Slutsky's Theorem, we have
Wo.7 = M. by + E - = arg min trrv (wob) = arg min L (Wo) = (o,-(A,
wo
wo
T xc. This proves the consistency of the train-val method.
13

---

Under review as a conference paper at ICLR 2021
Asymptotic normality
Similar above, write the per-task loss as
4 ((w)) = 2 | - call?
where
À
A
Xya
(xi
x /n + AId) -1
T
1 val
(xa X /n1 + AIa)
-xtrain y
C/
In order show the desired asymptotic normality result, it suffices check the conditions in Propo- sition First, we have
V4 = A, (A,wo - c.).
This is Lipschitz in wo with Lipschitz constant
A Aolop S I < n22
| lF
As Ex [||x|[[] < oo, the above quantity clearly square integrable, therefore verifying (a). As use similar arguments as above to show (b) holds. Finally, have already seen L is wiice-differenttable (since is quadratic in wo) and L²Woww,+)) > 0, which verifies (c). Therefore the conditions of Proposition hold, which yields the desired asymptotic normality result.
Wo, Wo,, (1) is finite,
A.3 PROOF OF PROPOSITION 2
High-level idea a high level, this proof proceeds by showing that the train-train method is also consistent to the (population) minimizer of I and constructing a simple counter-example on which the minimizers of L tr-tr is not equal to that of L test
Population minimizers of trr-tr and L Irr-val We begin by simplifying the non-splitting risk. We have
(t.t((wo) 2n yy: X,AA X:)1
2n 1yye X, [wo + ( X, + nAIa) -x, (y. X.wo)]|
1
2 | c2112
where
1 -== X.(X, nALa) y Vn
A XX, X, + -ALa) and -- V
Using similar arguments as in the proof of Proposition (Appendix A.2), we see that the train- train method wHt converges with probability one to the minimizer of the pouplation risk tr which is
tr-tt wirt 0.*
= arg min I tr-tr (wo) = (B[A, A EEA, c.)
We
X2 12X XxxxxX/n+AII X X,
E
XXX X, ALa) (I, - X,(X, X, + nnla)) -1x, ():
X
X. X,
E XXXX X2/n /n
(aT 2 Yt
=
n
n
(10)
14

---

Under review as a conference paper at ICLR 2021
On the other hand, recall from Proposition ((8) and (9)) that the population minimizer of L
(A, n)) arg min L L (wo)
(X, X,/n n AI.) AL. 1X, X./n n AIa) A {
[E X./n n Ala) -
(x D (xy]
xE (aa) x n AId) Xaa)-11 X
n
(11)
Construction of the counter-example We now construct a distribution for which (10) is not equal to (11). Let d = 1 and let all pt be the following distribution:
Pr (1 Bt.1) = (1,3) with probability 1/2:
(3, -1) with probability 1/2.
Clearly, we have E, 5, St = X X / / [1. and By [2'v// = O. Therefore we have
wit = =B[(st + 2) 81 E
(s+ + A) 2)- StaV
and
(A. = -E + E
5A(s; + A)-
yr.
n
-E[[(se + 2) - (st -)=
2r,
n
We now show that wh K (o, n)) by showing that
E
(st + 2) 2) Ft, Ft,i
E
31,1
# 0
(st + A)2
for any À O. Indeed, conditioning (2t,1, Vt.1) (1, know that the sum-of-square in st has one term that equals 1, and all others i.i.d. being or 9 with probability one half. On the other hand, if we condition on (æx, 1, 1t, (3, - -1), then know the in s, has one term that equals 9 and all others i.i.d.. This means that the negative contribution in the expectation is smaller than the positive contribution, in other words
E
F4,1
3E
(st X)2 (I1,1, = (1,3)
1
(st + X)2
-E
(Z),1, (3. (1) > 0.
2
(s,
X)2
This shows w * Wo, (A, n) and consequently the wHi does not converge to Wu,- n) and the difference is bounded away from zero as + Dc.
Finally, for this distribution, the risk Listt (Wo) is strongly convex (since has positive second derivative), this further implies that Lisst (wir:)) Lest (wo, (A, n)) is bounded away from zero almost surely as T Dc.
B PROOFS FOR SECTION
B. PROOF OF THEOREM 3
We first show that Wo,+ Ew,-n/ww [w]] is global optimizer for tr--tr and ttr-val with any regulariza- tion coefficient >> 0, any n, and any split n2), ). To do this, it suffices to check that the gradient Wo,+ is zero and the Hessian is positive definite (PD).
15

---

Under review as a conference paper at ICLR 2021
Optimality of wo,+ in both - and Ltr-vll We first look at L for any Wo R we have
= (wo)
E (wo)]
1
XeW; X, [x] + ndIs) " x7 (X,we X,wo) + wo ]1"
E
2n
1
LE
X
[a [Lo- (X) + +ndL)) (
xf x,xi) (we -woil
(12)
2n
Similarly, Ltr-val can be written
trr-val (wo)
(13)
=B(ct-val (wo)]
Xxyl w. Xyyal ((xtrain) T xtrain + n1 ATa) (xtrain) (xtrain we xo) + ww
|
E
2nz
Xxaal (Ia ((xtrann) T Xttain + +ndlaa -1 (Xtrain) T X(trin) (wr wo) woil
E
(14)
2nz
We denote
M Xt (I (x, + nALa) X. X, and
(15)
M = X.all [Id - ((xtrain) Xtraiin + n ALa)
(Xtrai) T Xtrain
(16)
simplify the notations in (12) and (14). We take gradient of L L and Lrrval with respect to Woi
V Vw I tr-tr 1 (Wo)
E
(M
M (w, woll
(17)
1
1
V wo L (wev)((w))
- -E [MM "M - wo)]
(18)
722
Substituting Wo,, into (17) and taking expectation, deduce
- (M M "w, (wr- wo,-)] =0 n
V tr-tr (Wo,.)
(19)
To see this, observe that by definition E E'w, Wo,el = 0. Combining with being generated independently of X,, we have the first term RHS of (19) vanish. In addition, z, independent white noise, therefore, the second term in RHS of (19) also vanishes. Following the same argument, we can show
V Wi L tr-vvll wo. 0,
since X is also independent of w., The above reasonings indicates that Wo,+ is stationary point of both trrtr and Irr-vll The remaining step is to check L. and Ltt.al are PD. From (17) and (18), derive respectively the hessian of tr-tr and tr-vvl
V tr-t (Wo..) _ [ (anf:ttrTTMM-" M and
V We
tr-val (Wo.))= = -- ((M T MMr-aal.
122
Let E Idd be any nonzero vector, check v TV2 L (wo.())) 0. A key obser- vation is that [Ia (x. mAIa) X. positive definite for any A 0. To see this, let T1 2 ... 2 oa be eigenvalues of X X,, some algebra yields the eigenvalues of A_ LL Xx +ndLa) -1 x, X, are Ato. > 0 for À o 0 and i =l.i==,,..,, I,...,, d. Hence, we deduce
V wo t (wo,.)) 1 Bly X xx,
x, x x.v) 0, (20)
since X, is isotropic (an explicit computation of the hessian matrix can found in Appendix B.2). As consequence, we have shown that Wo,, is a global optimum of trr-tr The same argument applies I,tr-val, and the proof is complete.
16

---

Under review as a conference paper at ICLR 2021
(tr-tr,tr-val) Consistency of W N.T
To check the consistency, need verify the conditions (a) (c) in
Proposition 6.
For condition (a), we derive from (17) and (18) that
Ve [e( (w1) (e (w2)
[M
[M
tr
M T trrr
[w] w2ll:
72
where n should be replaced by n2 for the split method (we slightly abuse the notation for simplicity). It suffices to show E
(M, (tr-trttwal)) ) ) MM, " (tr-tr,tr-val)
< which follows from the same argu- op
ment in the proof of Proposition 1. In particular, we know 0 I L (x X + nAIs) - x X, = La and x X llppl
< 0o since X, is Gaussian. As consequence, for the no-split method,
we have E (| M op
< co. For the split method, we also have 0 = L
((x)rain) Xtrain + ndla) -1 (Xtrain) Xtrain 3 La and (Xyaa) xx= < oc, which implies
(M T Mi op oc.
For condition (b), using a similar argument in condition (a) and combining with H² Bo, w.ll we have E[| ( (wo,+) [33] < cc.
For condition (c), using (20), we directly verify that [trttrtteal is twice-differentiable and 7 (trvtr,t--vll
0.
B.2 PROOF OF LEMMA 5
Proof. In this section we prove Lemma 5. Using the the asymptotic normality in Proposition 6, the asymptotic covariance is V --2 (trttr ( following, only need to find i and Cov (oo
Cov[Ve yy 2 (tr.trttvl Therefore, in the
Asymptotic variance of u.7" We begin with the computation of the expected Hessian [EMM""" MM
E( "
La X X, + nAIa) -1 x, xx,x))
x, X,X, X, (I, (X,X,, mAI,) -
x, xxXx)
=E
D.. T D. D. (Ia - (D. D. + adIa) -d Dj) V
V. (Ia E
(21)
where the equality (i) is obtained by plugging in the SVD of X, U,D.V. with U, F e D, E m and V, E Baxdd_ A key observation is that U, and V, are independent, since X, is isotropic, i.e., homogeneous in each orthogonal direction. To see this, for any orthogonal matrices Q pnxn and P dddd we know X, and QX,PT share the same distribution. Moreover, we have QX, = D. independent and both uniformly distributed on all the orthogonal matrices of the corresponding dimensions "R xn and R dxd respectively).
as the SVD. This shows that the left and right singular matrices
Recall that we denote o 2 of as the eigenvalues of _X. X,. Thus, we have D.D. = (n)
Diag(no ..... no0 (n)), ). We can further simplify (21) as
E
V. [Ia D.D.D nALa) -D, D. D.D.D. D, (Ia-DD. D. + nALa) - D.) V/
n1=a(") (m)
nd=o (n) (o - A)2
V.Diag
VT
(a(") + +}2²
d mx²a(")) Vi.Vi.
(22)
(n) + 2)2
17

---

Under review as a conference paper at ICLR 2021
We will utilize the isotropicity of X find (22). Recall that have shown that V, is uniform on all the orthogonal matrices. Let P E Rdxd be any permutation matrix, then V,P has the same distribution V,. For this permuted data matrix V,P, (22) becomes
nxPo!"") (")
(a: (m) + x)2
(o, (7,
with rp()) denotes the permutation of the i-th element in P.
Summing over all the permutations P (and there are totally d! instances), we deduce
(M
M
a (1)
Σ
E
V
( (t)
(o (m)
+ 1)2
all permutation
Tp
d
d
a (n)
= (d - 1)
Vi.Vis
(n) + 1)2
(o;
(n((n))
d
220 (n)
= (d - 1)
V.Diag
V
(A+ oi (1))2"
(A + 0x
(10)
A20(1))
(d 1)!E
VilaV
(23)
+ 1n)p2
Dividing (d-1) 1)! both sides of (23) yields
d
220,00 (n)
t T M
"
d
Ia.
(24)
() + of mm)y3
Next, we find the expected covariance matrix + (e (wo.)))
E (wo,
(Vo (w
B(M M.-"(Wo.--
(Wo.- -w). w.) -W:)
(M.--r) T M
n(Po(")) (n)
nd2o(1)) (N)
E V ViDigg
V. -w.) w.)
(of") (n) + A)2
(0 + x)2
n)Pa(m)) (n)
n (n)
V,Diag
VT
(25)
(a(") (1) + X)2
(o + x)²
Here step (i) uses the SVD of X, and the computation in (22), Combining (24) and (25), we derive the asymptotic covariance matrix of using trr-ir as
AsymCov wi:1 V cr-tr (Wo,)) 2
V
gr
Cov
d
d
-2
E
n
() + ai m2
n)2a(")) (n)
nd20(1) (n)
E
V,Diag
v (Wo.+ - w.)(wo. - w.)
(a(") + +1)²
(o (n) + AA²²
n12o(1)) (n)
n²2a(")) (n)
V,Diag
V
(26)
(a 2)2
(n) x)2
Taking trace in (26), we deduce
AsymMSF(W!rth
18

---

Under review as a conference paper at ICLR 2021
tr(AsymCor(WW.77
df
A2og (n)
E
n²
+ Ti 12
n² (o)
(2 (2)
V (wo.- -w) - -wo)
tr
E
ViDiag
(o +
(of +
d²
X (n)
E
n²
(A (2))))
n
Xa 12
ViloV, (Wo. - wi)(wo.- -w.)(wo---.)] -w))
(A + o. 11)
(a; (m) / + (
2 tr (Bl(wo,+ we)(wo.- - we) [)
E
E XPo: (m) /1 +
EV d (1) / + of 0.!))
E
dR²
(27)
Ei= of (n) /A (m) }²) 2'
E
where step (i)
utilizes the independence between w, and X, and applies the permutation trick in "
(o (or +x)*
(23) to find E V,Diag (o1 +X)*
v
Asymptotic variance of w Similar to the no-split case, we compute the Hessian
0,
E
ptrtrval
[(( Mirvvl) n2
first.
72
(M M
Xtrain =n1 -1 (xtrain) Xxtrann) T (X:al) T Xxal
12
[I ((xtrain)
Laa (xx X Xtrain + +niAla) (Xtrain) T X(trin)
[ (Xxtran)) T Tx train + Ald) ((xtrain) Xtrain) T
n2E E
La ((xtrain)) I Xtrain + AnnALa) (xtrain) T train
x
Tog train (La ((D)tai)) train
+ +n
(raiin)) T "Draiin (Virain) T].
(28)
n2I, and the independence be- tween Xtrain and Xyyl, and (ti) follows from the SVD of Xtrain = Utrain Drrain (Vtrain)
where (i) uses the data generating assumption [X(aal)) T X
Here we denote o1 (m1)
2 d (n1) the eigenvalues of L (Xtrain) Xtrain Thus, have ni
(Darain) T Darain Diag(n10)) (m1) ..... noo (mn)). We can now further simplify (28)
22
train (La ((Dtrann) Darain ni AIa) - (Dtrain) Ditrain) (Vtrain)
X²
X2
B
Diag
(Vtrain) T
(a (mi)
A)2
+ x)2 (a
(m1)
(i 12g
x
La.
(29)
(A (
Step (i) follows from the same computation in (22), and step (ii) uses the permutation trick in (23).
19

---

Under review as a conference paper at ICLR 2021
Next, we find the expected covariance matrix 2 BVV (wo,,) (wo,,)) Ver (wo,+)) J.
ni
E VIVe (wo,,)((
")
(Wo., - - we) (M!-'r) T "M
Diag E
(Virain) T (Iei)) T
(mi) +
(m1)
ad
>
X yrrann Diag
(Virain) T (wo.- w.)(Wo,+ - -.))
01
(mi)
+X
od
(11) +
A
Dirain
(Virain)
( (
(1n)
(m1)
+ +
xrali DDag
A
A
(Virain) T
(30)
(m1) +
(n1)
+
Combining (29) and (30), we derive the asymptotic covariance matrix of using I.tr-val as
AsymCov
0.f
= E[V
2 gtr-val
Cov
V pravaal
2gtr-val [Eo,.)]B[V
d²
d
X2
-2
E
2
()+ a mmaypa
A
E
Viran
(Virain) T ((x:a)) T
(mi) +
(m1)
+
d
A
x Diag
(Virain) T (woo- -w:) - -w.)
o (iu) +
of
(1u) +
A
virain Diag
(Virain) T (Xxaa))
(mn)
(mn) +
+
ytaain Diag
A
(Virain) T
(31)
(m))
+
0d
(mi)
+ A
Taking trace in (31), we deduce
A tndtr
tr-trr = (ov)Amyyoo 0,7
E
n
(A +
(2n)
ir
E
Diag
A
(Virrin)T T(x::o)) T
0
[mi]
+
(ms)
+
Staiin
(Virain) T(wo,+ - w.). -w:)
(m1)
x
(m1)
+
A
Diag
(Virrin) T (X(xO))
((m)) +
σ d
(m1)
+
(V
xval ytrain Diag
(m1) + X
d
[ni)
+
20

---

Under review as a conference paper at ICLR 2021
d²
x
E
n2
(A
{2
tr
E
Virain
Diag
(Virain) T (Xx:a)) T
0
(mn)
+ x
+ X (ni)
X²
Xial
(Virain) T )
(0 ((1)) A)2
(of + 2)2
vtal Diag
(Virain) (Wo,+ we) w.)(wo.t-w))
(n1)
A
dd
(nn)
+
(32)
where (i) follows from the cyclic property of the matrix trace operation. Due to the isotropicity of x Xtrain and Xyal, we claim that
A
A
E
Diag
(Virain) T (X:aI)
(m))
(m1)
X2
X2
X ytrain
(Virain) T (xxaa))
(oint))
A)2
(a
+ A)2 (m1)
Dian
(m1) (Vtrain) T
X
(33)
(mL)
0
diagonal matrix cla with all the diagonal elements identical. We can show the claim bying taking expectation with respect to Xyal first. Since Virain is an orthogonal matrix, Xya Virain has the same distribution as x.al and independent of X,. We verify that any off-diagonal element of the matrix expectation
X² (o(m1) + A)2
X + X)2
A = Exp" (virain) (Xxxa) Etraiiiaaing Diag
(n1) (o
(Virain) (Xxal) T(X:al) vtrain
zero. We denote Xyal = [xi...., xn] E Rraxd with x; üdd N(O, Ia)- For h: + e, the (k, ()-th entry Ag,e of A is
X²
Σ sanieess )
(( Z3AEE
Ag.
Σ
(o (m1) + X)2
X²
Σ mmmn
E
an j. (a (ni) + A)2
0.
where Vi,j denotes the j-th element of x,. Equality (i) holds, since either Uh,m or We, only appears once each summand. Therefore, we can write Diag (A1,1,.... Aa,a) with Ag, being
X²
A = E
Σ m.n
(m))
+ X)2
Σ
E
Ih k T. T
(a
(ns)
+ 2)2
21

---

Under review as a conference paper at ICLR 2021
(m1)
Observe that Ak, only depends on ok
Plugging back into (33), have
A
E
Vtrain
Diag
(Vi T (xia))
(m1)
+t
d
(11)
+ 2
X2
A2
Virain
(V T (xxaa)
(oi
(o X)2
(a
(nn) + ))2
A
(Vtrain)
(ns) Y
(m1)
0
+
A
E Vian
Diag( 11,1 Ad,a)
(1n)
+
Od
(mi)
Diag
A
A
(Virain) T
((m)) +
d
(m1)
+
A
A2
E Prain
(Viraing T
(a("1)
+
(o
(m))
X)2
cld,
where equality (i) utilizes the permutation trick in (24). To this end, it sufficient find
tr
Vtrain Diag
A
A
(Vtrain) T ((x:a))
(m1)
+ X
(11)
+
X2
x
Etraint Diag
(Virain) T (X.al)
(o
(11) (o(m))
+
X)2
(o(mi)
+12
A
A
(Virain]]) -
vtrain Diag
(nn)
+ X
d
(a1)
+
X²
22
tr E x v Diag
(Virain) T ((xxal)
(a
(ni)
+ X)2
(o
(ms)
X)2
d
X²
X
(Vtraing (Vtrain)((xxa)) (xx=a))
(34)
(o) (ns) +
+
(m1) (o
x)2
Observe again that Xyal
Raaxd is Gaussian random matrix. We rewrite (34) as
27
2²
2
d
E
Σ V. Diag
(a("1) + X)2
(o(m))
2)2
V
(35)
where V N(O, Ia) i.i.d. Gaussian random vectors for b.... 12. To compute (35), we need the following result.
Claim 7. Given any symmetric matrix A E Raxd and i.i.d. standard Gaussian random vectors iid
V, N(O, La), we have
E [(v A Av) = 2|| + (A) and (v Au) = ||
(36)
(37)
Proof of Claim We show (36) first. We denote Ai,; as the (1, ()th element and v; as the i-th element of v. Expanding the quadratic form, we have
E [v Av) =E
Au Aki
22

---

Under review as a conference paper at ICLR 2021
E
0 A
+ E
Σ
U + AncAss + Ass
isd
A2, +
(AP
A + A,5
isd
(A)
+
Σ A +
Σ(A + A,,))
bFj
tA) + 2||A|| Pr.
Next, we show (37) by the cyclic property of race.
E [[v A ir (E In Ave A)) ir(A?) -|AI|
We back to the computation of (35) using Claim
27
X²
X
E
v, T Diag
Vj
(of (m))
+ AA22
(o d
(m)
+ 1)2
==
27
112
X²
X²
d
R
vi Diag
(oi (m)) + +1)2"
(o (m1) + x)2
Vi
27
X2
X2
+ d
E
Σ itj
v. Diag
(m(1)) + +1)2
(a
(mn) + X)2
V
112
1,2
Diag
X
X²
(0) (m1)
+ x)2
(a + X)2
(ni)
n2 2
|
12
X²
E d
(of (mi) + x)2
(o
(n)) + +\)2
Fr.
(2 -
1)BB E
X²
X
Diag
d
(0) (mi) + 2)2"
(a + A)²
n22
E
X²
+ (m2 + 1)E
X
(38)
d
(o
(m1) +
A)2
(m1) + A)4
Combining (38) and (33), by the independence between w, and Xtrrin, Xval, we compute (32) as AsymMSE(w11fF)
-2
d²
X
E
n
+ o
m2
2
171)) 1)
X2
A
12
+ (n2 + 1)E
Σ
d
(a (n1) + +)]2
(n1) + 21
(0
E
[(wo,+
wi) - w
d
E
Σi x² >²/(a/ + 2)2
+ (nz + 1)E
E X0/(o (m))))) + 2)
E
Ed X2/(2 + 0:00))0]1
2
The proof is complete.
23

---

Under review as a conference paper at ICLR 2021
B.3 OPTIMAL RATE OF THE TRAIN-VAL VAL METHOD AT FINITE (n, d)
Corollary 8 (Optimal rate of the train-val method at finite (n, d)). For any (n, d) and any split ratio (21) (n1, n-n1), the optimal rate (by taning the regularization X > 0) of train-val method is achieved at
trrvval W (2; A)) = lim AsymMSE( Wo.r (ni, 122 A]) (d + 122 1)R²²
inf AsymMSE A=O
Wo.
X-200
112
Further optimizing the rate over n2, the best rate taken (n1, n2) (0, n), in which the rate is
infxso, m2tin) AsymMSE Worr (m1, n2; A)) (d n R)
Discussion: Using all data as validation Corollary 8 suggests that the optimal asymptotic rate of the train-val method is obtained at X = oo and (n1, m2)) = (0, n). In other words, the optimal choice for the train-val method is to use all the data as validation. In this case, since there is training data, the inner solver reduces to the identity map: A Wo: X,) = Wo. and the outer loop reduces to learning single linear model Wo on all the tasks combined. We remark that while the optimality of such a split ratio is likely an artifact of the data distribution we assumed (noiseless realizable linear model) and may not generalize other meta-learning problems, we do find experimentally that using more data as validation (than training) can also improve the performance on real meta- learning tasks (see Table 2).
Proof of Corollary 8
Fix nı E [mx] and n2 = n - 111. Recall from Lemma that
E
(Σ X2/(o, (m)) + )))²)
+ (n2 + +1) (0 +21²
dR2
tr-val AsymMSE W (n1, n2; n2; (n1,
722
E2
ΣV X2 (o (m)) ) + +1)2))
Clearly, as -> 00, we have
dR²
d² + (mz + 1)d
(d + n2 + 1)R²
lim AsymMSE Netrova (wi,r m21 A)) X
712
d²
112
It remains to show that the above quantity is a lower bound for Asym Whrr (h for
any À > 0, which is equivalent to
E
Σ
X²/(o,mm) (mx) + x))) + (122 + 1) X²/(0, + +AJ2
d + n2 +1
for all X 0.
E (m)) + 1)²1)²
d
(39)
We now prove (39). For E [mi]. define random variables
x
X; = (o (m)) + x)2
E [0, 1] and y; = 1 - x, E [0.
Then the left-hand side of (39) can be rewritten as
E (d no + En x,)² + (ne + () + Σm x?)
(Eid nu X,])
2i Y))² + (n2 + 1) - 2 2 Em Y?) E (d Σm
(Lid Σ Y:l)²
d² + (nq + +1)d - 2(d n12 + 1) > Yi] E [ Y.)
(n2 +
d² 2dE Y. + EE) Y!1)
24

---

Under review as a conference paper at ICLR 2021
By algebraic manipulation, inequality (39) is equivalent to showing that 1 + (m2 + 1)
Σ V
d + n22 +
(40)
E Σ Y.])
Clearly, IB
[ x By Cauchy-Schwarz we also have
[
x
1 B
z
11
Therefore we have
C 2 + (n2 + 1) Σ Y??
122 +1
122 +1
d
+ n2 +1
2
1+
1+
(E|
T1
d
d
where we have used that n1 S n S d. This shows (40) and consequently (39).
B.4 RATE OF THE TRAIN-TRAIN METHOD IN THE PROPORTIONAL LIMIT
Theorem (Exact rates of the train-train method in the proportional limit). In the digensiinlii limiting regime d, - oc, d/n + where y E (0, oo) is a fixed shape parameter, for any X > 0
i/nd Asym. ( (n; A)) = P2,
tr-tr
(++++++++++)0 -47) 47)
where PA, = PA,
Proof of Theorem 9 Let Σx == x denote the sample covariance matrix of the inputs in
single task (t). By Lemma 5, we have
1 Σ oi
A)1
(s R².
(1 Ed oi (En) (o: (o: + +))2
(41)
= n² 1 ALa ALa) 1
( ( + Ala) Aaa) -
In.d
1l.,d
We now evaluate quantities I and In, in the high-dimensional limit of d, - 00, d/n + 7
(0, oc). Consider the (slightly generalized) Stieltjes transform of Σ,, defined for all A1 A2 > 0:
d,n=to0, d/n-ry 2x( ur (A + se
8(A1, A2)= = lim
As the entries of X, are i.i.d N(O, 1), the above limiting Stieltjes transform is the Stieltjes form of the Marchenko-PP -Pattu law, which has a closed form (see, e.g. (Dobriban et al., 2018, Equation (7)))
1 7- \ + (Ai/22 + 7)2 47
s(1 22) =>,² s(21/>2, 1)
A
24d1/A2
(42)
2 - 1 + (A1/A2 + +1+ 24
27d1
Now observe that differentiating s sA11, A2) yields quantity (known as the derivative trick of Stielt- jes transforms). Indeed, we have
d sAi,, A2)
d lim
1 |r (Aila + A2
d)e
00, d/n
E d
(ArIa+ )² -1)
lim
tr
(43)
d,n-+0,, +/
dxz
lim
E. ir (d + -
d,n-to,, d/n-ty
25

---

Under review as a conference paper at ICLR 2021
(Above, the exchange of differentiation and limit is due to the uniform convergence of the deriva- tives, which holds at any λ1, A2 > O. See Appendix B.4.1 for a detailed justification.) Taking
X = X and A2 = 1, we get
lim F (AIa + En)- = di2 lim 1nnd d,n-to,, d/u-ty d d/n-ty
s(A1, d2)l =
Similarly we have
+ = - 6 σλ di3
_d d de
lim
Ind
lim d/n--oo,d/n-n
(Al 22)1
d, d/n->7
Evaluating the right-hand sides from differentiating the closed-form expression (42), we get
1
X+1+7
1
lim d 000, d/n-ty
In
27
V(A (++) -
27'
(7 1)2 + 1)>
lim d d/n-ry
(A++++1) 4 6/22
Substituting back to (41) yields that
lim d,n- d/n-py
AsymMSE(
tr-tr 0.7 (
(n; X)) =
lim
R² -n,a/ a
d,n, d/n-t7
4 + (7 1)A]
R².
V(A+1+9)2-0r -1) 2
-1)
(A+1+ -4475//22
A+I+y
472 472
1)2 (7+ 1)A]
R²
47) 2'
((A +
v
This proves the desired result.
B.4.1 INTERCHANGING DERIVATIVE AND EXPECTATION / LIMIT
Here we rigorously establish the interchange of the derivative and the expectation / limit used in (43). For convenience of notation let Σ Σ. X / denote the empirical covariance matrix of X.. We wish to show that
d
lim dAg d/
BB(t(((ALLa + [)]
lim d.n-+so.d/n-7
E
tr tr((
di²
This involves the interchange of derivative and limit, and then the interchange of derivative and expectation.
Interchange of derivative and expectation
First, we show that for any fixed (d, n),
E (t
+x
= E dDz
tr((A11a+ (
dAz
By definition of the derivative, have
d
tr (r + X3 +
+Σ) -1) tr (( + 2) -1
E[tr((AnTa + X2 12
lim E t0
dAz
t
For any A > O, the function ++ tr((A+t() -1) ) is continuously differentiable at f = with deriva- tive -ir-tr(AA2PB and thus locally Lipschitz around t = 0 with Lipschitz constant |tr( A -BB] + 1. Applying this in the above expectation with A = A + A Z A and B = Σ, we get that for sufficiently small it|, the fraction inside the expectation is upper bounded by |rr(> Σ + 1 < oo uniformly over t. Thus by the Dominated Convergence Theorem, the limit can be passed into the expectation, which yields the expectation of the derivative.
26

---

Under review as a conference paper at ICLR 2021
Interchange of derivative and limit to show that
Define fn,a(2)) + +22))=)) It suffices
d lim
fna()2)
lim d.n-+oo,d/n ())))2)
dd2 d,n to-toodd/n>y
where
(22) E d 1 dD d + -
by the result the preceding part.
As (A,) s(1, X2) pointwise over A2 by properties of the Wishart matrix (Bai & Silverstein, 2010) and each individual Jn, is differentiable, suffices to show that the derivatives d (22) converges uniformly for X2 neighborhood of Xg. Observe that can rewrite f as
(h2) = -Ea,,, Ex-pand Oxx [1]]]
where Fndd is the empirical distribution of the eigenvalues of Σ, and
A
9xp (A) (A1 (22))
for all A A20 0.
A1
Therefore, as Fn.d converges weakly to the Marchenko-Pasiie distribution with probability one and 9x, is uniformly bounded for X2 in a small neighborhood of X we get that (x, does converge uniformly to the expectation of 9x, (A) under the Marchenko-Pasiie distribution. This shows the desired interchange of derivative and limit.
B.5 PROOF OF THEOREM 4
Throughout this proof we assume that R² 1 without loss of generality (as all the rates are constant multiples of R²)).
Part I: Optimal rate for trr-t
By Theorem 9, we have
lim A=0 d.n do.d//
inf
AsymMSF Whil (m: A))
4.2 ( 1)2 ( 1)A] (A+1+y- / + 1)2 1)2 -4)
inf
A
(A++++1) 4/)
:=1(A,))
In order to bound infx=o f fA,, 7), picking any À = X(n) gives f(A(7), 7) as a valid upper bound, and our goal is choose that yields a bound tight as possible. Here we consider the choice
À = X(7) = max {1 - 7/2,7 - 1/2] (1 7/2)1 (r I 1 + (7 1/2)1 fy > 1}
which we now show yields the claimed upper bound.
Case 1: < Substituting À = 1-17//2 into f(), and simplifying, we get
f(1 f(1-r/2,7) 2(>2 - 37 4)
(2 7/23 =: 91(7).
Clearly, g1 (0) and 91 (1) = 32/27. Further differentiating twice gives
77 > 0 for all y [0, 1]. (2 7/235
((())
Thus 91 convex on [0, 1). from which we conclude that
5
g1 (7) & (1 - 7) (0 + 91
27
27

---

Under review as a conference paper at ICLR 2021
Case 2: 1
Substituting À = 7 1/2 into f(A,1) and simplifying, get
1 1/2,7) (47 37 + 1) 92())
(2 1/2)3
We have 92(1) (1) 32/27. Further differentiating 92 gives
6
s2(7)= = (47 1)2
(4y - 1)$ +1<1 <<
for all 7 > 1.
(4y - 1)3
Therefore we have for all 7 > that
92(r) 92((1) ',' (2(1)dt s0())===1+)+==-======)))))))- 5
27
Combining Case and 2, we get
inf f(A, 7) $ (1 AS0
[1
5 27 1 s 1)
(5
+
< 1 (y S 1) g2 ty 13 S
27
5
-maxx
1+
1 27
27
This is the desired upper bound for L
Equality at 7 =1 At 1, we have
We finally show that the above upper bound becomes an equality when = 1.
8A
8A-4
((A (A+2 V 4x)
21+ / 4/
Make the change of variable expression is equivalent to minimizing
/ 1 4/> so that X-1 (t2 1)/4, minimizing the above
(12 - 1)1/32
11+
(t2 2 - t 1/2)
8t3
over > It is straightforward to check (by computing the first and second derivatives) that the above quantity is minimized at = 3 with value 32/27. In other words, we have shown
32
{1
5
5
inf f(,, 1) Aso
27 7, 27
27
7=1
that is, the equality holds at y = 1.
Part II: Optimal rate for L trrvvll We now prove the result trr-val, that is,
inf X (00,) d.n
lim
AsymMSE wiryyal (ns, n(1 s);
lim don-too 220m AsymMSE (WA (
inf
(ni, 122; 2)) (6)) 1+7.
First, equality (ii) follows from Corollary 8 and the fact that (d + n + 1)/n + 1 + y. Second, the "2" direction of equality (i) is trivial (since always have "inf lim > lim inf"). Therefore get the "2" direction of the overall equality, and remains to prove the "<" direction.
For the "<" direction, we fix any À O. and bound FAMMMSFFWWtry0 (n1, (2; (and conse-
quently its limit as d, n co.) We have from Lemma that
AsymMSF( (trvvll (m n2; X))
28

---

Under review as a conference paper at ICLR 2021
Din X²/(o, + +2)²)
+ (m2 + 1) >²((o, +1)a
712
E
E \2/(oi (m)) + =2pp]
d
d² + (ng + 1)d
112
E EE
ii=1 X2 2/, (m1) ))
d + 12 +
1
112
Σラ= (0 (mi) + =xj2])
Observe that
2
22
E
E
1=1
(0,
(m1)
+ x)2
d
i== oi
(m1)
/d x
(18)
(ii1)
X²
E
(mL) /d + +2)
(1 + 2)2
where (i) follows from the convexity of + 22/(t + 2)2 on
0: (ii) follows from the
Ei (ni) E tr( x,J x.)
same convexity and Jensen's inequality, and (iii) since E
| /mi d. Applying this in the preceeding bound yields
n2; A)) v + n2 +
(1+
(1 + A)2
A troyal (2i
X
Further plugging in ns and = n(1 - 8) for any E (0. 1) yields
lim d. A (ns, - A)) < +
2)+
X
Finally, the right-hand side is minimized - 00 and 0, from which we conclude that
inf lim (0,1) don d/u-ty AsymMSE((Wttr n2; A)) S ++%,
which is the desired "<" direction.
C CONNECTIONS TO BAYESIAN ESTIMATOR
Here discuss the relationship between our train-trail meta-learining estimator using ridge regres- sion solvers and a Bayesian estimator under a somewhat natural hierarchical generative model for the realizable setting in Section We show that these estimators equal in general, albeit they have some similarities in their expressions.
We consider the following hierarchical probabilitistic model:
02 _ Wa|Wo, Wo. N(O N(..00
(
Hid
R² Wo.:: d _Taa Y: - oze where Z₁
idd
N(O, I.).
This model is similar to our realizable linear model (6), except that wo has a prior and that there is observation noise in the data (such that data likelihoods and posteriors well-defined). We also note that the R²/ / variance for w, guarantees that B|llw; Wo || = R², consistent with our definition (7).
29

---

Under review as a conference paper at ICLR 2021
Bayesian estimator We now derive the Bayesian posterior mean estimator of Wo,., which requires us to compute the posterior distribution of Wo., given the data (x) 3e))
We begin by computing the likelihood of one task by marginalizing over w,;
/ p(We/Woot)) p(y:|Xt, we)dw,
p(X,, x
/ exp
|w wo
lyve
XeW,ll
11
exp
dw:
2R2/d
20²
|
1 +
Wu,+
y 0²
T
X
Ia
Wo.+
X
exp
2R2/d /d
2
R2/d
R2
22
Re/d
R2fd
+
o²
-.W.. 2 wo.
(x|xx
do²
X
do²
X Ye R2/d
o exp
Wo, + Wo,
X X,
+
Ia
R
R2/d
R
where (i) is obtained by integrating a multivariate Gaussian density over W,, and "xx" drops all the terms that do not depend Wo,.- Therefore, by the Bayes rule, the overall posterior distribution of Wo, is given by
T
Wo, ((,,,
& x(Wo,)) II (( [=1
||wo. 11
x exp
20 /d
T
(-2 2 Wo..
1
(xxxxx+
do Ia R²
X X, R2
Wo. + Wo, (x,X, +
2 I
x yt R2 /2/d
exp
R²
This means that the posterior distribution Wo,+ Gaussian, with mean i.e. the Bayesian estima- tor, equal to
0,T
Bayes
: E Wo,*
((Xe.))))7
(A,
(A
Bayes
-1 Bayes
CT
where
d Ia +
do R22
X X,
AT
Bayes
X X,
Ia
02
R2/d
t=1
T
d
X yt R2/dd
TT
Bayes
X
X
+
R
Ld
We note that W WoT"" Indeed, recall the closed form of our train-train estimator is (cf. (10))
Bayes has similar form as our train-train estimator, but is not exactly the same.
(A -A
where
T
A
tr-tr
X X, + ndIa) -2 -x,xXx X,,
t=1
T
tr-tr CT
Σ
[X] X + +
XTy=. yv.
Bayes As Wo.r uses the inverse and W uses the squared inverse, these two sets of estimators are not the same in general, no matter how we tune the À in the train-train estimator. This is true even if we set or oo so that the prior of Wa,+ becomes degenerate (and the Bayesian estimator reduces to the MLE).
Hereafter we treat X, as fixed, as the density of X, won't affect Bayesian calculation.
Any density p(w) o exp(-w' Aw/2 w c) specifies Gaussian distreibution N(J, E), where A and Σ pt, that μ A -
Σ
30

---

Under review as a conference paper at ICLR 2021
D DETAILS ON THE FEW-SHOT IMAGE CLASSIFICATION EXPERIMENT
Here we provide additional details of the few-shot image classification experiment Section 5.2.
a few gradient steps the inner argmin problem to obtain (an approximation of) Wt. and plug w. into the Vwa e, (( (Wo) (which involves W, through implicit function differentiation) for optimizing wo in the outer loop.
Optimization and architecture For both methods,
For both train-train and train-val methods, we use the standard 4-layer convolutional network in (Finn et al., 2017; Zhou et al., 2019) the backbone (i.e. the architecture for wz). We further such as the regularization constant X, the learning rate (initial learning
tune their rate and its decay strategy), and the gradient clipping threshold.
Datasets We experiment minilmageNet (Ravi & Larochelle, 2017) and tieredImageNet (Ren al., 2018). MinilmageNet consists of 100 classes of images from ImageNet (Krizhevsky et al., 2012) and each class has 600 images of resolution 84 x 84 x 3. We use 64 classes for training, 16 classes for validation, and the remaining 20 classes for testing (Ravi Larochelle, 2017). Tiered- ImageNet consists of 608 classes from the ILSVRC-12 data set (Russakovsky et al., 2015) and each image also resolution 84 x 84 x 3. magreeI groups classes into broader hierarchy categories corresponding to higher-level nodes in the ImageNet. Specifically, its top hierarchy has 20 training categories (351 classes), 6 validation categories (97 classes) and 8 test categories (160 classes). This structure ensures that all training classes are distinct from the testing classes, provid- ing a more realistic fhw-shot learning scenario.
D.1 EFFECT OF THE SPLIT RATIO FOR THE TRAIN- VAL METHOD
We further tune the split (M1, n2) in the train-val method and report the results in Table 2. As can be seen, as the number of test samples 122 increases, the percent classification accuracy on both the minilmageNet and maeredI datasets becomes higher. This testifies our theoretical affirmation in Corollary However, note that even if we take the best split (71, T22) = (5, 25) (and compare again with Table 1), the train-val method still performs worse than the train-train method.
We remark that our theoretical results on train-traie performing better than train-val (in Section 4) rely on the assumptions that the data can be exactly realized by the representation and contains label noise. Our experimental results here may suggest that the minilmageNet and mageed few-shot tasks may have a similar structure (there exists NN representation that almost perfectly realizes the label with no noise) that allows the train-train method to perform better than the train- val method.
Table 2: Investigation of the effects of training/validation splitting ratio in the train-val method (iMAML) to the few-shot classification accuracy (%) on minilmageNet and ticredImageNeet.
datasets N1 25, 122
B1 15, 12
ni 5, /2 25
minilmageNNt
62.09 + 0.97
63.56 = 0.95
63.92 + 1.04
tieredImageNet
66.45 1 1.05
67.30 = 0.98
67.50 0.94
E COMPARISON WITH CROSS- VALIDATION ON SYNTHETIC DATA
We test the effect of using cross-validation for the train-val method on the same synthetic data (realizable linear centroid meta-learning) as in Section 5.1.
Method We fix the number of per-task data n = 20, and use 4-fold cross validation in the fol- lowing two settings: (R1, R22) (5, 15), and (71, n2) (15, 5). In both cases, partition the data into 4 parts each with 5 data points, and we roulette over 4 possible partitions of which one as train and which as validation. The estimated optimal wgr is obtained by minimize the averaged
31

---

Under review as a conference paper at ICLR 2021
train-val loss over the 4 partitions:
(
valu
Xval
Ax(wo: xtraind yy. yrainad) 3|
val
W
= arg min Wa
(wo);
t=1
where superseript denotes the index of the cross- cross- validation. The performance is depicted in Figure
2.
15
(tr-tr tr-val, ov) Wo.7
tr-val, ml 15,
10
ref. curve I-F 4d/n
tr-val + cross-validation,
n1=15
tr-val, ml
5
ref. curve 1 1d/3n
W0.*
Lo-val + cross-validation,
tr-tr, ref.
n1=5
0.5
1
1.5
2
2.5
3
f error of a (tr-tr, tr-val, ov) v.s. d/n ratio
Wor
Figure 2: The scaled (by T) ey-error of (trrltr the ratio d/n varies from 0 to 3 (n 20 and T 1000 are fixed). For the vols-vaaiiattinn method, the regularization coefficient À = 0.5 is tuned.
WoT
Result As showin in Figure 2, for both (M1, cross-validation consistently beats the performance of the train-val method. This demonstrates the variance-reductionn effect of cross-validation. Note that the best performance (among the cross- validation methods) is still achieved at nı = 5, similar as for the vanilla train-val method. However, numerically, the best cross-validation performance still not as good as the train-train method.
(15,5) 5) and n2), (5, 15), using
Leave-one-out cross-validation Figure 3 left further tests with an increased number of per-task samples n = 40, and incorporates the train-val method with the leave-one-out cross-vasd cross-validation. i.c., (11,722) (39, 1) and (RI, (1, 39). We repeat the experiment 10 times for plotting the error bar (shaded area). We see that the train-train method still outperforms the train-val method with leave-one-out validation.
We further increase the per-task sample size n to 200, and test the leave-one-out method with a sample split of (2,) (1, 199). We adopt matrix inverse trick mitigate the computational overhead of finding Ax Xtrain.j yt y train.j). To ease the computation, we also vary d from 0 to 400 on a coarse grid (with an increment of 80). From Figure 3 right, we see that the leave-one-out method can slightly beat the train-train method for some d/n values. Compared to n = 20 and = 40 experiments, this is the first time of seeing leave-one-out method outperforms the train- train method. We suspect that the per-task sample size n plays a vital role in the power of the leave-one-out method: a large tends to have strong variance reduction effect in the leave-one-out method, so that the performance can be improved. Yet using the leave-one-our method with large invokes high computational burden.
32

---

Under review as a conference paper at ICLR 2021
3
2.3
leave-ote-oor
W0.7
Jeave-oue
2
validatioo,, 188
Wg.
1.5
leive-one-out
validation, al
textr, ref.
tr-fr, ref, curve
f error Wa
ftstte v.s. d/n ratio
82 error W v.s. d/n ratio
Figure 3: The scaled (by T) f2-error of (tr-tr,ev as the ratio d/n varies from 0 to 3 (n E (40, 0,7 and T = 1000 are fixed). For the cross-validation method, the regularization coefficient À = 0.5.
Left: n 40. Leave-out-out CV performs worse than the train- train method. Right: 200.
Leave one-out CV appears better than the train-train method for d/n E (1.2,166).
F NONASYMPTOTIC ANALYSIS UNDER GENERAL SCALINGS OF d, n, T
We sketch nonasymptotic analysis of the train-train method in the realizable linear model in ädd Section 4. We assume in addition that w. N(Wo,,: 12 I2).
We begin by recalling from Appendix and B.2 that the train-train and train-val estimators have closed-form expressions
W
Σ
A
Σ
A
(44)
tr-vvl W
B
Σ
B
(45)
where
X X
X X,
A X
+ Ald
n
n -1 Xval Xyal
B, = 2 Xtrain
Xtrain
(Xtrain
Xtrain
Ald
Ald
71
n12
Nonasymptotic result for w For simplicity, we restrict attention on the analysis of the train- train estimator wirtr, whose closed form expression is given in (44). Analysis of the train-val esti- mator can be done in a similar fashion.
We sketch a proof for the following
Result: Let T (dd and (d, n) is such that
E Do (o(")))/((0) (n) + =)
(d,
O(1)
(1L Ei of (n) ((0 + x)²1)
TTiis Gaussian assumption is mainly for technical convenience, and can he relaxed to that we, Wo,+,; are i.i.d. with variance R² /d and uu-GGusssian with parameter D(R /d) without changing the proof.
33

---

Under review as a conference paper at ICLR 2021
(which for example holds if (d, n) are in the proportional limit), then with high probability have
R2 ++ va)) 7
d (drraar(d 1) n) + (dv T
log (ō)
AISE(WO.)) = d
d1
R² 2 T (t. = AsymMSE
T
that is, the MSE for the train-train method concentrates around the asymptotic MSE. Proof Sketch
We first define the matrix
Ex= =
Σ
A
-2
Σ
=
T
A
-t=
A,
1= A?
T
T
which will be key to analysis. Observe that conditioned on A, (and only looking at the random- ness of wt), we have
A.(w: Wo,+) ~ ~ N Σx
R2
tr-tr 0,T
Wo.-
Σ
A₁
Σ
d
1=1
Therefore, applying the Hanson- Wright inequality (Vershynin, 2018, Theorem 6.2.1) yields that
Hanson-Wright
R
MSE (177)
| tr-tr wo,-|l 1|
tr tr(Er) + max | llz V log 8z Ex lop log
with probability at least 8. In the following, we argue that tr(Er) is the dominating term in the above bound and concentrates around the asymptotic MSE in Lemma 5, whereas the error terms within the max are lower order errors compared with tr (E))
Concentration of tr(EEr)
Recall that A, are i.i.d. PSD matrices in Rdxd We have
2t
TT' Ar
T
A?
(r(ET)
-
7 3,AA
+
Σ Ar
B[A B[A
Li=
Ar
-2
5T
-1=1
A?
E[A
T
T
T
III
We argue that I the main term that depends on (d, n) and independent of T. Further, Aq has eigenvalues X²a;/(A= + )²)² where {a:] are the eigenvalues of X Xi/n, and A has uniformly distributed eigenvectors. Following the same analysis of Lemma
XxX,//ia see that
E
1 nd
Zi=1
(a. (m) ((0 +)4
I= d Per-tr = d.
Di=1 (m) ((a 2)2 +X)a])
E
This is exactly the same quantity that appeared in the asymptotic MSE for the train-traie method in Theorem 4. the following we assume that d, n is such that furrr (d, n) = O(1)
We further argue that terms II and III are low-order terms compared with term I. Indeed, term I Odd). Applying matrix concentrations (e.g. the matrix Bernstein inequality). we can get that terms and III are of order max / (Toog(T/8)/T, (og(T/0))T)) with probability at least 1 - 6. Combining the terms yields that
log(T (T/5)
tr(Er)
d furt + =dy T
T
with high probability.
34

---

Under review as a conference paper at ICLR 2021
Controlling the error in the MSE wish to show that
We now control
|EllA Flr and (consequently)
EErlop-- We
EE S O
tr tr(ET)
with high probability. This can be seen from the combination of two results: (1) ((d/T) by the preceding part, and (2)
ET S T Amin (E A
Σ A So(Va/T).
The above requires (1) ||Aull (vd),, which is true since we have 0 5 A S AIa and thus
A I Vd, and (2) Amin (EisT A+/T) (1(1) with high probability, which true whenever (
T Q(d) because of matrix concentration and the fact that Amin (B[Ai]) = 2(1).
Putting together
We have with high probability that
R² d
(110 (t))) 7 (d. () 1 dy
log (
MSE W
T
as long as T = 2(dd and d, n is such that firtt(d, (etr(,,)) n) = @(1).
F.1 SYNTHETIC EXPERIMENT
We verify our theoretical findings under general scalings of d, T. We adopt the data generating model in Section 5.1 again. To compare the performance of the train-train and train-val methods, choose the number of tasks T 300 and per-task sample size = 100. We vary d from 0 to 300. Note that now comparable to n and d and much smaller than T 1000 used in previous experiments. Figure 4 shows the close fit of reference curves to the simulated &g errors.
Wo,* (tr-tr, tr-val)
fr-val, ml = 0, ref. curve 14d//n
tr-val, nl 20,
0.?7
3
ref. curve I- 5d/4n
trstr, ref. curve
0.5
1
1.5
2
2.5
3
lg error of w (tr-tr, tr-val) 0,T
v.S. d/n ratio
Figure 4: The scaled (by 7' & of [t as the ratio d/n varies from 0 to 3 in the general scaling setting (n 100 and T 300 are fixed). The regularization coefficient À is fine tuned for the method and = 2000 for the train-val method.
W
35


Reviews:
[{"review_id": "_AMKAu33Lb", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the theoretical properties of meta-learning. In particular, the train-validation split to tackle the linear centroid meta-learning problem is investigated using statistical asymptotic theory. First, the authors proved that the train-validation method has statistical consistency, while the train-train method has a statistical bias to the centroid. Under the noise-free setting, however, both methods have statistical consistency. Furthermore, the train-train method is superior to the train-validation method in the sense of the asymptotic MSE. Based on the asymptotic analysis the optimal ratio of the data splitting for the train-validation method was also derived. The theoretical findings are confirmed by some numerical experiments. \n\nIn this paper, the meta-learning is formulated as a multiple ridge regression problem and the standard statistical asymptotic theory is used to derive some theoretical results. The impact of the results will be rather limited. \n\nIn the paper, the difference between the train-val method and the train-train method was investigated. The theoretical properties are well-known in the standard context of statistics and machine learning. That is, the overfitting to the training data yields a serious bias to the generalization error. Information criteria such as AIC, BIC, etc provide the bias correction to fill the gap. I guess that the authors are aware of the close relationship between the present formulation of the meta-learning and the classical statistical theory. The authors could mention its relationship and could go to further intriguing problems such as the analysis of meta-learning using lasso-type regularization. \n\nIn my option, the theoretical contribution of this paper is quite limited. \n\nSome more comments below:\n- In each task, the same number of data is assumed to be observed. Was that just for the sake of simplicity? How is the theoretical results modified when the sample size varies from task to task?\n- In Proposition 1, the meaning of the Cov(\\nabla\\ell_t) is not very understandable.\n- The authors analyzed the statistical properties of the meta-learning using realizable linear models, or in other words, the noise-free models. The noise-free model is extremal situation, and a more general situation could be studied.\n- In Corollary 6, can the author provide an intuitive reason why splitting with zero training and all validation is optimal.\n- In section 4.2, the proportional limit was studied. Is it possible to derive a theoretical bound in the case that T, n, and d take comparable numbers?\n- The authors did not provide any interpretation of the conclusion of Corollary 8. Showing a persuasive reason is of great help to the readers. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "UjMmPu-_crG", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In meta-learning, a common practice is to do a train/validation split of the data within each that, so that optimization of meta-parameters is performed on validation, not training, losses. In this paper, the author argue that this split is important for correcting model misspecification, but if the model is correctly specified, not doing a split might actually lead to better learning rates. They provide theoretical justification under a simple linear model, and some experiments on synthetic and real data.\n\nDisclaimer: I have good expertise in random matrix theory but I am not as knowledgeable about the meta-learning literature. Thus, my review will mostly focus on the results themselves, with the hope that other reviewers can better evaluate how this work compares to other work in the area.\n\nGlobally, I think the results of this paper are interesting. The proof of Theorem 7 (the trickiest result) is clever. I think the high-level structure of the paper could be improved and results better presented, but the \"core\" of the paper holds its ground. Per the disclaimer I cannot judge the novelty of the work. Overall I would lean towards acceptance.\n\n[pros]\n1. The central result of the paper is, in my mind, Corollary 8. Its precursor, Theorem 7, has a clever proof that was different from what I expected. Namely, I thought it would be based on linear spectral statistics results as found in Bai and Silverstein (2004), but instead they noticed their statistic of interest can be computed from the nice trick of directly differentiating (a generalization of) the Stieltjes transform. It's very elegant.\n\n2. I think Propositions 2-3 are the other interesting results, namely by showing that consistency of the methods are intimately linked to model specification.\n\n3. To obtain a workable theoretical analysis, the authors analyzed a simple linear model, (6). However, this model also leads to counterintuitive results, such as Corollary 6. What happens when the model is very flexible, like a neural net? Issues of model misspecification become less relevant, so one might think we are more in the setting of Section 4. However, it's possible that the gap in learning rates between train-val and train-train is an artifact of how simple the linear model is. I think the \"real data\" experiments in Section 5 are interesting in that respect and suggest that it remains true with deep models, so this is an important contribution as well.\n\n[cons]\n1. I think the structure of the paper could be much improved. Since Corollary 8 is the most important result, it should be given the status of a Theorem. Theorem 4, 5, and 7 should disappear. I think Corollary 6 and its ensuing discussion should disappear as well. Theorem 4 is ok, but maybe should be given a lesser status. I think if Proposition 2-3 could be merged into a single Theorem it would be nice too. I would try to eliminate or shorten as much as possible Section 2.1, I found this a bit distracting. The rest of Section 2 is fine for me. Otherwise, I would really emphasize the two scenarios: under model misspecification (Section 3) and under correct model specification with a working example, the linear model (Section 4), perhaps by changing the titles of the current sections. Finally, as discussed in my \"pro\" point 3, the \"real data\" experiments in Section 5 are really important, and it's a pity a lot of details are relegated to the appendix. Since I suggest cutting a lot of theoretical results, I would maybe bring back a lot of details currently dumped in Section A.2, since I think this deep, real data example is really crucial for making the case that the paper is relevant to normal practice.\n\n2. I would like to see more details as to why interchange of the derivative and both the limit and the integral is justified in the proof of Theorem 7 (uniform convergence).\n\nOther comments:\n- Calling \\hat{w}_{0, T}^{tr-val} in Proposition 2 an \"algorithm\" doesn't make much sense, I think \"estimator\" is more accurate.\n- There seems to be a major typo in the statement of Theorem 7: you talk of the train-val method but the math has tr-tr written.\n\nReferences\n\n[1] Bai, Z. D., and Jack W. Silverstein. \"CLT for Linear Spectral Statistics of Large-Dimensional Sample Covariance Matrices.\" Annals of Probability (2004): 553-605.", "extra_scores": {}, "extra_text": {}}, {"review_id": "HkTwvaNaisi", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors verify the importance of train-validation split in meta-learning theoretically, which is commonly used in the meta-learning paradigms. By analyzing the linear centroid meta-learning problem, the authors show that the splitting method converges to the optimal prior as expected, whereas the non-splitting method does not in general, without structural assumptions on the data. The authors validate the theories empirically through both simulations and real meta-learning tasks.\n\nThe paper provides new insights on the usage of the train-validation splits in meta-learning theoretically. Some popular methods such as iMAML are also used as comparisons in the experiments. \n\nHere are some suggestions:\n1. Will the batch-size, the meta-training way influence the results in Table 1. More ablations like Table 2 should be investigated.\n\n2. The authors could discuss whether the theory can be applied to other kinds of meta-learning methods and how the theoretical results can guide the design of new meta-learning methods.", "extra_scores": {}, "extra_text": {}}, {"review_id": "E36PVO9lzvj", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper compares two approaches of data splitting in meta-learning: train-validation split and train-train split. This paper shows that the best of the two approaches depends on the specific problem.\n\nStrength: It is easy to follow the paper and it is very convincing why the train-train approach could be better than the train-validation approach.\n\nWeakness: I am not an expert in meta-learning and I could be wrong with my comments. But my concerns are:\n\n1) Both inner loop and outer loop are solving the linear regression problems. In fact, because the estimate of the inner loop $\\mathcal{A}(w_0; X, y)$ is linear in $w_0$, we can combine the inner loop and outer loop together, and our estimate for $w_0$ is a linear regression estimate where the new features are constructed by the original features and response, and the loss is not only averaged by the sample size $n$ of each task but also the number of tasks $T$. It is unclear to me how ''this problem captures\nthe essence of meta-learning with non-linear models (such as neural networks) in practice'' as claimed on page 2. Furthermore, as $T$ goes to infinity, it becomes the classic linear regression regime where dimension fixed and sample size goes to infinity. Because of this, it is intuitive and looks straightforward to check that the train-validation split gives a consistent estimate and the train-train split gives a consistent estimate in the realizable setting but not in general. I would say to improve the significance of the paper, the authors could like at the regime where d, n, T both grows to infinity at certain rates e.g. $d=\\Theta(Tn)$.   \n\n2) One major reason that the train-validation split is inferior to the train-train split is that a significant amount of data is missed in the training. My question is why we do not apply K-fold cross-validation instead of a simple train-validation split. In the case of ridge regression, it is possible to do a leave-one-out cross-validation efficiently, i.e., we can obtain the leave-one-out prediction risk without fitting the regression $n$ times but using the estimate trained by the entire data. For general meta-learning, K-fold cross-validation should be a better approach than a train-validation split. In the linear regression setting, leave-one-out cross-validation should be a more proper approach. Then it will be kind of fair to compare K-fold cross-validation with the train-train split and it will be interesting to see train-train split can be still better.\n\n3) Because of the linear regression settings with $T\\rightarrow \\infty$, I think it is closely related to a Bayesian hierarchical model with the Gaussian prior on the coefficients (due to the ridge penalty in the inner loop). Is the Bayesian estimator be consistent as well when $T\\rightarrow infty$? Some discussion about this connection would be good.\n\nBecause of these concerns, I currently recommend a reject. But it is possible that I will change my mind if the authors can address my concerns well.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors investigate theoretical properties of meta-learning. In particular, the train-validation split to tackle the linear centroid meta-learning problem is investigated in asymptotically regimes (a non-asymptotic analysis of the train-train estimator has been added later on). It is shown that the train-validation method has statistical consistency, while the train-train method has a statistical bias to the centroid. Yet, in the noise-free setting both methods have statistical consistency. Furthermore, the train-train method is superior to the train-validation method in the sense of the asymptotic MSE. Based on the asymptotic analysis the optimal ratio of the data splitting for the train-validation method is derived. The theoretical findings are corroborated by some numerical experiments.
The main theoretical result suggests that the train-train method + optimally tuned regularization is a strong alternative to the train-validation split, hence the authors' recommendation that for meta-learning train-train method should be preferred.

The reviewers and the area chair appreciated the theoretical findings and the subsequent effort to improve the paper the authors put in place during the discussion period. Unfortunately, the tight competition among papers in this year's edition of the conference makes this specific submission not compelling enough for publication. 
I would like to encourage the authors to sumbit to another ML venue in the near future, while considering improvements in their experimental validation (as also suggested by some reviewers).

Decision: Reject