summaries: 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.

summaries: 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.

summaries: 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.

abstractText: 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 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.

authors:
Pierre Alquier
The Tien Mai
Massimiliano Pontil

title: Regret bounds for lifelong learning

venue: arXiv preprint arXiv:1610.08628,

authors:
Greg W Anderson
Alice Guionnet
Ofer Zeitouni

title: An introduction to random matrices, volume 118

venue: Cambridge university press,

authors:
Andreas Argyriou
Theodoros Evgeniou
Massimiliano Pontil

title: Multi-task feature learning

venue: In Advances in neural information processing systems,

authors:
Zhidong Bai
Jack W Silverstein

title: Spectral analysis of large dimensional random matrices, volume 20

title: A model of inductive bias learning

venue: J. Artif. Int. Res.,

title: Multitask learning

venue: Machine Learning,

authors:
Giulia Denevi
Carlo Ciliberto
Dimitris Stamos
Massimiliano Pontil

title: Incremental learning-tolearn with statistical guarantees

venue: arXiv preprint arXiv:1803.08089,

title: Learning to learn around a common mean

venue: In Advances in Neural Information Processing Systems,

authors:
Edgar Dobriban
Stefan Wager

title: High-dimensional asymptotics of prediction: Ridge regression and classification

venue: The Annals of Statistics,

authors:
Simon S Du
Wei Hu
Sham M Kakade
Jason D Lee
Qi Lei

title: Few-shot learning via learning the representation, provably

venue: arXiv preprint arXiv:2002.09434,

authors:
Theodoros Evgeniou
Charles A Micchelli
Massimiliano Pontil

title: Learning multiple tasks with kernel methods

venue: Journal of machine learning research,

authors:
Alireza Fallah
Aryan Mokhtari
Asuman Ozdaglar

title: On the convergence theory of gradientbased model-agnostic meta-learning algorithms

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In Proceedings of the 34th International Conference on Machine LearningVolume

authors:
Chelsea Finn
Aravind Rajeswaran
Sham Kakade
Sergey Levine

title: Online meta-learning

venue: In Proceedings of the 36th International Conference on Machine Learning,

authors:
Luca Franceschi
Paolo Frasconi
Saverio Salzo
Riccardo Grazzi
Massimilano Pontil

title: Bilevel programming for hyperparameter optimization and meta-learning

venue: arXiv preprint arXiv:1806.04910,

authors:
Tomer Galanti
Lior Wolf
Tamir Hazan

title: A theoretical framework for deep transfer learning

venue: Information and Inference: A Journal of the IMA,

authors:
Micah Goldblum
Steven Reich
Liam Fowl
Renkun Ni
Valeriia Cherepanova
Tom Goldstein

title: Unraveling meta-learning: Understanding feature representations for few-shot tasks

venue: arXiv preprint arXiv:2002.06753,

authors:
Jiatao Gu
Yong Wang
Yun Chen
Kyunghyun Cho
Victor OK Li

title: Meta-learning for lowresource neural machine translation

venue: arXiv preprint arXiv:1808.08437,

authors:
Kaiyi Ji
Jason D Lee
Yingbin Liang
H Vincent Poor

title: Convergence of meta-learning with task-specific adaptation over partial parameters

venue: arXiv preprint arXiv:2006.09486,

authors:
Mikhail Khodak
Maria-Florina Balcan
Ameet Talwalkar

title: Adaptive gradient-based metalearning methods

venue: arXiv preprint arXiv:1906.02717,

authors:
A. Krizhevsky
I. Sutskever
G. Hinton

title: Imagenet classification with deep convolutional neural networks

authors:
Kwonjoon Lee
Subhransu Maji
Avinash Ravichandran
Stefano Soatto

title: Meta-learning with differentiable convex optimization

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

title: Cs229t/stat231: Statistical learning theory (winter

authors:
Han Liu
Mark Palatucci
Jian Zhang

title: Blockwise coordinate descent procedures for the multitask lasso, with applications to neural semantic basis discovery

venue: In Proceedings of the 26th Annual International Conference on Machine Learning,

authors:
Han Liu
Lie Wang
Tuo Zhao

title: Calibrated multivariate regression with application to neural semantic basis discovery

venue: Journal of machine learning research: JMLR,

authors:
Andreas Maurer
Massimiliano Pontil
Bernardino Romera-Paredes

title: The benefit of multitask representation learning

venue: The Journal of Machine Learning Research,

authors:
Daniel McNamara
Maria-Florina Balcan

title: Risk bounds for transferring representations with and without fine-tuning

authors:
A. Nichol
J. Schulman

title: Reptile: a scalable metalearning algorithm

venue: arXiv preprint arXiv:1803.02999,

authors:
Alex Nichol
Joshua Achiam
John Schulman

title: On first-order meta-learning algorithms

authors:
Aniruddh Raghu
Maithra Raghu
Samy Bengio
Oriol Vinyals

title: Rapid learning or feature reuse? towards understanding the effectiveness of maml

venue: In International Conference on Learning Representations,

authors:
Aravind Rajeswaran
Chelsea Finn
Sham M Kakade
Sergey Levine

title: Meta-learning with implicit gradients

authors:
S. Ravi
H. Larochelle

title: Optimization as a model for few-shot learning

authors:
M. Ren
E. Triantafillou
S. Ravi
J. Snell
K. Swersky
J. Tenenbaum
H. Larochelle
R. Zemel

title: Meta-learning for semi-supervised few-shot classification

venue: arXiv preprint arXiv:1803.00676,

title: An overview of multi-task learning in deep neural networks

venue: arXiv preprint arXiv:1706.05098,

authors:
O. Russakovsky
J. Deng
H. Su
J. Krause
S. Satheesh
S. Ma
Z. Huang
A. Karpathy
A. Khosla
M. Bernstein

title: Imagenet large scale visual recognition challenge

authors:
Nikunj Saunshi
Yi Zhang
Mikhail Khodak
Sanjeev Arora

title: A sample complexity separation between non-convex and convex meta-learning

venue: arXiv preprint arXiv:2002.11172,

title: Evolutionary principles in self-referential learning, or on learning how to learn: the meta-meta-.

venue: hook. PhD thesis, Technische Universität München,

authors:
J. Snell
K. Swersky
R. Zemel

title: Prototypical networks for few-shot learning

authors:
Sebastian Thrun
Lorien Pratt

title: Learning to Learn: Introduction and Overview, pp. 3–17

authors:
Nilesh Tripuraneni
Chi Jin
Michael I Jordan

title: Provable meta-learning of linear representations

venue: arXiv preprint arXiv:2002.11684,

authors:
Nilesh Tripuraneni
Michael I Jordan
Chi Jin

title: On the theory of transfer learning: The importance of task diversity

venue: arXiv preprint arXiv:2006.11650,

title: Asymptotic statistics, volume 3

title: High-dimensional probability: An introduction with applications in data science, volume 47

authors:
Haoxiang Wang
Ruoyu Sun
Bo Li

title: Global convergence and induced kernels of gradient-based meta-learning with neural nets

venue: arXiv preprint arXiv:2006.14606,

authors:
Xiang Wang
Shuai Yuan
Chenwei Wu
Rong Ge

title: Guarantees for tuning the step size using a learning-to-learn approach

venue: arXiv preprint arXiv:2006.16495,

authors:
Yujia Xie
Haoming Jiang
Feng Liu
Tuo Zhao
Hongyuan Zha

title: Meta learning with relational information for short sequences

authors:
Pan Zhou
Xiaotong Yuan
Huan Xu
Shuicheng Yan
Jiashi Feng

title: Efficient meta learning via minibatch proximal update

heading: 1 INTRODUCTION

text:
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 metalearning 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 so that it is able to quickly adapt to unseen new tasks. Meta-learning has been successfully applied to many real problems, including few-shot image classification (Finn et al., 2017; Snell et al., 2017), hyper-parameter 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 to perform a sample splitting, where the data within each task is divided into a training split which the prior uses to adapt to a task-specific predictor, and a validation split on which we evaluate the performance of the task-specific predictor (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 as training data, and use additional examples (e.g. k images, one for each class) as validation data. This sample splitting is believed to be crucial as it matches the evaluation criterion at meta-test time, where we perform adaptation on training data from a new task but evaluate its performance on unseen data from the same task.
Despite the aformentioned importance, performing the train-validation split has a potential drawback 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,
each task has a total of 6k examples available, but the train-validation split forces us to use these data separately in the two stages. Meanwhile, performing the train-validation split is also not the only option in practice: there exist algorithms such as Reptile (Nichol & Schulman, 2018) and Meta-MinibatchProx (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-validation split) compare with each other, which motivates us to ask the following
Question: Is the train-validation split necessary and optimal in meta-learning?
In this paper, we perform a 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 a 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 a 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, we show that the train-validation split is necessary in the general agnostic setting: As T → ∞, 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 are structural assumptions on the tasks: When the data are generated from noiseless linear models, both the train-val and traintrain 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 on simulations and benchmark few-shot image classification 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 samplesplitting may not be crucial; methods that utilize the per-task data more efficiently may be preferred.

heading: 1.1 RELATED WORK

text:
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., 2018a; 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 a one-dimensional subspace setting. Wang et al. (2020b) compared the performance of train-train and train-val 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-based 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
are analyses for other representation learning schemes (McNamara & Balcan, 2017; Galanti et al., 2016; Alquier et al., 2016).
Empirical understandings of meta-learning Raghu et 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 features (representations) are fixed and only a linear classifier is learned. Goldblum et al. (2020) investigated 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 a train-validation split, it is not exactly the same as the train-train method considered in this work as it effectively performs a 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 earliest 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 et 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 a large amount of parameters. In contrast, meta-learning only requires the models to share the same “prior”, which is more flexible than multi-task learning.

heading: 2 PRELIMINARIES

text:
In this paper, we consider the standard meta-learning setting, in which we observe data from T ≥ 1 supervised learning tasks, and the goal is to find a prior (or “initialization”) using the combined data, such that the (T + 1)-th new task may be solved sample-efficiently using the prior.
Linear centroid meta-learning We instantiate our study on the linear centroid meta-learning problem (also known as learning to learn around a common mean, Denevi et al. (2018b)), where we wish to learn a task-specific linear predictor wt ∈ Rd in the inner loop for each task t, and learn a “centroid” w0 in the outer loop that enables fast adaptation to wt within each task:
Find the best centroid w0 ∈ Rd for adapting to a linear predictor wt on each task t.
Formally, we assume that we observe training data from T ≥ 1 tasks, where for each task index t we sample a task pt (a distribution over Rd × R) from some distribution of tasks Π, and observe n examples (Xt,yt) ∈ Rn×d × Rn that are drawn i.i.d. from pt:
pt ∼ Π, (Xt,yt) = {(xt,i, yt,i)}ni=1 where (xt,i, yt,i) iid∼ pt. (1)
We do not make further assumptions on (n, d); in particular, we allow the underdetermined setting n ≤ d, in which there exists (one or many) interpolators w̃t that perfectly fit the data: Xtw̃t = yt.
Inner loop: Ridge solver with biased regularization towards the centroid Our goal in the inner loop is to find a linear predictor wt that fits the data in task twhile being close to the given “centroid” w0 ∈ Rd. We instantiate this through ridge regression (i.e. linear regression with L2 regularization) where the regularization biases wt towards the centroid. Formally, for any w0 ∈ Rd and any dataset (X,y), we consider the algorithm
Aλ(w0; X,y) := arg min w
1 n ‖Xw − y‖2 + λ ‖w −w0‖2 = w0 +
( X>X + nλId )−1 X>(y −Xw0),
where λ > 0 is the regularization strength (typically a tunable hyper-parameter). As we regularize by ‖w −w0‖2, this inner solver encourages the solution to be close to w0, as we desire. Such a regularizer is widely used in practical meta-learning algorithms such as MetaOptNet (Lee et al.,
2019) and Meta-MinibatchProx (Zhou et al., 2019). In addition, as λ → 0, this solver recovers gradient descent fine-tuning: we have
A0(w0; X,y) := lim λ→0 Aλ(w0; X,y) = w0 + X†(y −Xw0) = arg minXw=y ‖w −w0‖2
(where X† ∈ Rd×n denotes the pseudo-inverse of X). This is the minimum-distance interpolator of (X,y) and also the solution found by gradient descent 1 on ‖Xw − y‖2 initialized at w0. Therefore our ridge solver with λ > 0 can be seen as a generalized version of the gradient descent solver used in MAML (Finn et al., 2017).
Outer loop: Finding the best centroid In the outer loop, our goal is to find the best centroid w0. The standard approach in meta-learning is to perform a train-validation split, that is, (1) execute the inner solver on a first split of the task-specific data, and (2) evaluate the loss on a second split, yielding a function of w0 that we can optimize. This two-stage procedure can be written as
Compute wt(w0) = Aλ(w0; Xtraint ,ytraint ), and evaluate ∥∥yvalt −Xvalt wt(w0) ∥∥2 . where (Xtraint ,y train t ) = {(xt,i, yt,i)}n1i=1 and (Xvalt ,yvalt ) = {(xt,i, yt,i)} n i=n1+1
are two disjoint splits of the per-task data (Xt,yt) of size (n1, n2), with n1 + n2 = n. Written concisely, this is to consider the “split loss”
`tr-valt (w0) := 1
2n2
∥∥yvalt −Xvalt Aλ(w0; Xtraint ,ytraint ) ∥∥2 . (2)
In this paper, we will also consider an alternative version, where we do not perform the trainvalidation split, but instead use all the per-task data for both training and evaluation. Mathematically, this is to look at the “non-split loss”
`tr-trt (w0) := 1
2n ‖yt −XtAλ(w0; Xt,yt)‖2 . (3)
Our overall algorithm is to solve the empirical risk minimization (ERM) problem on the T observed tasks, using either one of the two losses above:
L̂tr-valT (w0) := 1
T
T∑
t=1
`tr-valt (w0) and L̂ tr-tr T (w0) :=
1
T
T∑
t=1
`tr-trt (w0),
ŵ {tr-val,tr-tr} 0,T := arg min
w0
L̂ {tr-val,tr-tr} T (w0).
(4)
Let L{tr-val,tr-tr}(w0) := Ept∼Π,(Xt,yt)∼pt [ ` {tr-val,tr-tr} t (w0) ] be the population risks.
(Meta-)Test time The meta-test time performance of any meta-learning algorithm is a joint function of the (learned) centroid w0 and the inner algorithm Alg. Upon receiving a new task pT+1 ∼ Π and training data (XT+1,yT+1) ∈ Rn×d × Rn, we run the inner loop Alg with prior w0 on the training data, and evaluate it on an (unseen) test example (x′, y′) ∼ pT+1:
Ltest(w0;Alg) := EpT+1∼ΠE(XT+1,yT+1),(x′,y′)iid∼pT+1
[ 1
2
( x′>Alg(w0; XT+1,yT+1)− y′ )2] .
Additionally, for both train-val and train-train methods, we need to 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
Ltestλ,n1(ŵ tr-val 0,T ) := L test(ŵtr-val0,T ;Aλ,n1), Ltestλ,n(ŵtr-tr0,T ) := Ltest(ŵtr-tr0,T ;Aλ,n), where Aλ,m denotes the ridge solver with regularization strength λ > 0 on m ≤ n data points. Finally, we let
w0,?(λ;n) = arg min w0
Ltestλ,n(w0) (5)
denote the best centroid if the inner loop uses Aλ,n. The performance of the train-val algorithm ŵtr-val0,T should be compared against w0,?(λ, n1), whereas the train-train algorithm ŵ tr-tr 0,T should be compared against w0,?(λ, n). 1with a small step-size, or gradient flow.

heading: 2.1 TASK-ABUNDANT SETTING THROUGH ASYMPTOTIC ANALYSIS

text:
In this paper we are interested in the task-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̂{tr-val,tr-tr}0,T ) as T → ∞. 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 on miniImageNet (Ravi & Larochelle, 2017) contains ( 64 5 ) diverse tasks (at train time).
Asymptotic rate of estimation & excess risk Let L be any population risk with minimizer w0,? (which we assume is unique), L̂T be the empirical risk on the observed data from T tasks, and ŵ0,T be the minimizer of L̂T (i.e. the ERM). We say that ŵ0,T is consistent if ŵ0,T → w0,? in probability as T → ∞. For consistent ERMs, we define its asymptotic parameter estimation error (in MSE loss) and asymptotic excess risk as follows2:
AsymMSE(ŵ0,T ) := lim T→∞
T · E [ ‖ŵ0,T −w0,?‖2 ]
AsymExcessRisk(ŵ0,T ) := lim T→∞
T · E[L(ŵ0,T )− L(w0,?)].
We emphasize that asymptotic statements are more refined than non-asymptotic O(·) style upper bounds in the T → ∞ limit: they already imply the {MSE, excess risk} has order O(1/T ) and specifies the leading constant.

heading: 3 THE IMPORTANCE OF SAMPLE SPLITTING

text:
We begin by analyzing whether the algorithms ŵ{tr-val,tr-tr}0,T defined in (4) converge to the best test-time centroid w0,?(λ;n1) or w0,?(λ;n) (defined (5)) respectively as T → ∞, in the general situation where we do not make structural assumptions on the data distribution pt. Proposition 1 (Consistency and asymptotics of train-val method). Suppose Ex∼pt [xx>] 0, Ex∼pt [‖x‖4] < ∞ and E(x,y)∼pt [‖xy‖] < ∞ for almost surely all pt ∼ Π. Then for any λ > 0 and any (n1, n2) such that n1 + n2 = n, the train-val method ŵtr-val0,T converges to the best test-time centroid: ŵtr-val0,T → w0,?(λ, n1) almost surely as T →∞. Further, we have AsymMSE(ŵtr-val0,T ) = tr ( ∇−2Ltestλ,n1(w0,?(λ, n1)) · Cov ( ∇`tr-valt (w0,?(λ, n1)) ) · ∇−2Ltestλ,n1(w0,?(λ, n1)) ) ,
AsymExcessRiskLtestλ,n1 (ŵtr-val0,T ) = tr
( ∇−2Ltestλ,n1(w0,?(λ, n1)) · Cov ( ∇`tr-valt (w0,?(λ, n1)) )) .
Proposition 2 (Inconsistency of train-train method). There exists a distribution of tasks Π on d = 1 satisfying the conditions in Proposition 1 on which the train-train method does not converge to the best test-time centroid: for any n ≥ 1 and any λ > 0, the estimation error ‖ŵtr-tr0,T − w0,?(λ, n)‖ and the excess risk Ltestλ,n(ŵ tr-tr 0,T )−Ltestλ,n(w0,?(λ, n)) are both bounded away from 0 almost surely as T →∞.
Propositions 1 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 1 is simple: the population loss Ltr-val for the trainval method is indeed equal to the test-time loss Ltestλ,n1 , making the train-val method a 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, its expected loss Ltr-tr is in general not equivalent to Ltestλ,n: Ltr-tr measures the in-sample prediction error of the per-task predictor, whereas Ltestλ,n measures the out-of-sample prediction error. Consequently, the population minimizers of Ltestλ,n and L
tr-tr are not equal in general, which leads to ŵ0,? converging to the minimizer of Ltr-tr, not of Ltestλ,n. 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 1 and 2.
2These definitions assume that the expectation exists for finite T ; the more general definition can be found in Appendix A.1.

heading: 4 IS SAMPLE SPLITTING ALWAYS OPTIMAL?

text:
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 is specified by a wt ∈ Rd sampled from some distribution Π (overloading notation), and the observed data follows the noiseless linear model with ground truth parameter wt:
yt = Xtwt, (6)
where the inputs xt,i iid∼ N(0, Id) and are independent of wt. We assume that Π has a finite second moment (i.e. Ewt∼Π[‖wt‖2] <∞). Note that when n ≥ d, we are able to perfectly recover wt for all t (by solving linear equations), therefore the problem in the inner loop is in a sense “easy”; when n < d, we cannot hope for such perfect recoveries. Our goal in the outer loop is to find the best w0, measured by the test loss Ltestλ,n for the train-train method and L test λ,n1 for the train-val method.

heading: 4.1 COMPARISON OF TRAIN-TRAIN AND TRAIN-VAL ON THE REALIZABLE MODEL

text:
We begin by showing that on this task and data distribution, the population best centroids w0,?(λ, n) = arg minw0 L test λ,n(w0) is the same for any (λ, n), and both the train-val and traintrain 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 λ > 0 and all n is minimized at the same point, that is, the mean of the ground truth parameters:
w0,?(λ, n) = arg min w0
Ltestλ,n(w0) = w0,? := Ewt∼Π[wt], for all λ > 0, n.
Further, both the train-val method and the train-train method are asymptotically consistent: for any λ > 0, n, and (n1, n2), we have
ŵtr-val0,T (n1, n2;λ)→ w0,? and ŵtr-tr0,T (n;λ)→ w0,? almost surely as T →∞.
See its proof in Appendix B.1. Theorem 3 shows that both train-val and train-train methods are consistent, and they converge to the same optimal parameter w0,? which is the mean of wt. This is a consequence of the good structure in our realizable linear model (6): at a high level, w0,? is indeed the best centroid since it has (on average) the closest distance to a randomly sampled wt.
Theoerem 3 suggests that we are now able to compare performance of the two methods based on their asymptotic parameter estimation error (for estimating w0,?). Throughout the rest of this section, let
R2 := E [ ‖wt −w0,?‖2 ] (7)
denote the variance of wt. 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 high-dimensional limiting regime d, n → ∞, d/n → γ ∈ (0,∞), the optimal rate of the traintrain method obtained by tuning the regularization λ ∈ (0,∞) satisfies
inf λ>0
limd,n→∞,d/n=γ AsymMSE ( ŵtr-tr0,T (n;λ) ) = inf λ>0 ρλ,γR 2 (?)
≤ max { 1 + 5
27 γ,
5
27 + γ
} ·R2,
where ρλ,γ =4γ2 [ (γ − 1)2+(γ + 1)λ ] /(λ+γ+1− √ (λ+ γ + 1)2 − 4γ)2/ ( (λ+ γ + 1)2 − 4γ )3/2 , and the inequality becomes equality at γ = 1. In contrast, the optimal rate of the train-val method by tuning the regularization λ ∈ (0,∞) and split ratio s ∈ (0, 1) is
infλ>0,s∈(0,1) limd,n→∞,d/n=γ AsymMSE ( ŵtr-val0,T (ns, n(1− s);λ) ) = (1 + γ)R2.
As max{1 + 5γ/27, 5/27 + γ}< 1+γ (∀γ > 0), the train-train method achieves a strictly better asymptotic rate than the train-val method when λ and s are optimally tuned in both methods.
Implications Comparison between the analytical upper bound max{1 + 5γ/27, 5/27 + γ}R2 for train-train (1 + γ)R2 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 γ > 03. (See Figure 1(a) for a visualization of the exact optimal rates and the upper bound (?).) Perhaps surprisingly, this suggests that the traintrain method is not only “correct” (converging to 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 is due to the fact that the train-train 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 generality when data is structured or when the signal-to-noise ratio is 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.

heading: 4.2 PROOF HIGHLIGHTS OF THEOREM 4

text:
Here we sketch the technical highlights in proving Theorem 4. We defer the full proof to Appendix 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 ρtr-tr = E [∑d
i=1(σ (n) i ) 2/(σ (n) i +λ)
4 ]
( E [∑d
i=1 σ (n) i /(σ (n) i +λ)
2 ])2 and ρtr-val = E
[(∑d i=1 λ 2/(σ (n1) i +λ) 2 )2 +(n2+1) ∑d i=1 λ 4/(σ (n1) i +λ) 4 ] ( E [∑d
i=1 λ 2/(σ (n1) i +λ)
2 ])2 ,
where for any n, σ(n)1 ≥ · · · ≥ σ (n) d denotes the eigenvalues of the matrix 1 nX > t Xt ∈ Rd×d, where we recall Xt ∈ Rn×d is a random matrix with i.i.d. standard Gaussian entries. For any (n, d), we have on the realizable linear model (6) that
AsymMSE ( ŵtr-tr0,T (n;λ) ) = dR2ρtr-tr, AsymMSE ( ŵtr-val0,T (n1, n2;λ) ) = dR2ρtr-val
n2 .
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 1n ∑n t=1 XtX > t .
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, as the quantities ρtr-tr and ρtr-val depend on the spectrum of the empirical covariance matrix as well as additional tunable parameters such as λ and (n1, n2) (for the train-val method). Towards proving Theorem 4, we 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 a special case λ = ∞ and (n1, n2) = (0, n), at which the rates only depends on 1n1 X train> t X train t
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 ρtr-val, and can be found in Appendix B.3.
• For the train-train method, we apply random matrix theory to simplify the spectrum of 1nX>t Xt in the proportional limit where d, n → ∞ 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 λ > 0, which we can analytically optimize over λ. 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.
3The same conclusion also holds for the asymptotic excess risk, as the Hessian of the excess risk is a rescaled identity, see Appendix B.2.

heading: 5 EXPERIMENTS

heading: 5.1 SIMULATIONS

text:
We experiment on the realizable linear model studied in Section 4. Recall that the observed data of the t-th task are generated as
yt = Xtwt, with xt,i iid∼ N(0, Id).
We independently generate wt iid∼ N(w0,?, Id/ √ d), where w0,? is the linear centroid and the corresponding R2 = 1 here. The goal is to learn the linear centroid w0,? using the train-train method and train-val method, i.e., minimizing L̂tr-trT and L̂ tr-val T , respectively. Note that both L̂ tr-tr T and L̂ tr-val T are quadratic in w0, therefore, we can find the close-form solutions ŵ {tr-tr,tr-val} 0,T . We measure the performance of train-train and train-val methods using the `2-error ‖w0,? − ŵ{tr-tr,tr-val}0,T ‖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 8. 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 trainval method (a “cross-validation” type loss) rather than the vanilla single split. We show that such cross-validation can indeed improve over the vanilla single-split train-val method. We also experiment with the stronger “leave-one-out” style cross-validation and show that it achieves better MSEs than the constant-fold cross-validation (Appendix E).
0,T ) are used as
reference curves in plots (b) and (c). Panel (b) plots the `2-error of ŵ {tr-tr,tr-val} 0,T as the total number of tasks increases from 20 to 1000 with an increment of 20. We fix data dimension d = 60 and per-task sample size n = 20. For the train-val method, we experiment on n1 = 0 and n1 = 5. Panel (c) shows the scaled (by T ) `2-error of ŵ {tr-tr,tr-val} 0,T as the ratio d/n varies from 0 to 3 (n = 20 and T = 1000 are fixed).

heading: 5.2 FEW-SHOT IMAGE CLASSIFICATION

text:
We further investigate the comparison between the train-train and train-val type methods in fewshot image classification on miniImageNet (Ravi & Larochelle, 2017) and tieredImageNet (Ren et al., 2018).
Methods We instantiate the train-train and train-val method in the centroid meta-learning 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 wt (and hence w0) parametrize a deep
neural network instead of a linear classifier, and the loss function is the cross-entropy instead of squared loss. Mathematically, we minimize the following two loss functions:
Ltr-valλ,n1 (w0) := 1
T
∑
t=1
`tr-valt (w0) = 1
T
T∑
t=1
` ( arg min
wt
`(wt; X train t ,y train t ) + λ ‖wt −w0‖2 ; Xvalt ,yvalt
) ,
Ltr-trλ (w0) := 1
T
T∑
t=1
`tr-trt (w0) = 1
T
T∑
t=1
` ( arg min
wt
`(wt; Xt,yt) + λ ‖wt −w0‖2 ; Xt,yt ) ,
where (Xt,yt) is the data for task t of size n, and (Xtraint ,y train t ) and (X val t ,y val t ) is a split of the data of size (n1, n2). We note that both loss functions above have been considered in prior work (Ltr-val in iMAML (Rajeswaran et al., 2019), and Ltr-tr in Meta-MinibatchProx (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 et al., 2019). In meta-test, we sample a set of N -way (K+ 1)-shot test tasks. The first K instances are for training and the remaining one is for testing. In meta-training, we use the “higher way” training strategy. We set the default choice of the train-validation split ratio to be an even split n1 = n2 = n/2 following Zhou et al. (2019); Rajeswaran et al. (2019). For example, for a 5-way 5-shot classification setting, each task contains 5 × (5 + 1) = 30 total images, and we set n1 = n2 = 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, 000 random test episodes with 95% confidence interval.
Results Table 1 presents the percent classification accuracy on miniImagenet and tieredImageNet. We find that the train-train method consistently outperforms the train-val method. Specifically, on miniImageNet, 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 tieredImageNet, train-train on average improves by about 6.40% on the four testing cases. These results show the advantages of train-train method over trainval and support our theoretical findings in Theorem 4.

heading: 6 CONCLUSION

text: We study the importance of train-validation split on the linear-centroid meta-learning problem, and show that the necessity and optimality of train-validation split depends greatly on whether the tasks are structured: the sample splitting is necessary in general situations, and not necessary and nonoptimal when the tasks are nicely structured. It would be of interest to study whether a similar conclusion holds on 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.

heading: A PROOFS FOR SECTION 3

heading: A.1 DETAILED INTRODUCTION ON ASYMPTOTIC ANALYSIS

text:
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 ŵ0,T is asymptotically normal with a known covariance matrix, as is characterized in the following classical result (see, e.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 w0,? is unique and the ERM ŵ0,T is consistent (i.e. it converges to w0,? in probability as T →∞). Further assume the following regularity conditions:
(a) There exists some random variable At = A(pt,Xt,yt) such that E[A2t ] <∞ and ‖∇`t(w1)−∇`t(w2)‖ ≤ At ‖w1 −w2‖
for all w1,w2 ∈ Rd;
(b) E[‖∇`t(w0,?)‖2] <∞;
(c) L is twice-differentiable with∇2L(w0,?) 0,
then the ERM ŵ0,T is asymptotically normally distributed, with √ T · (ŵ0,T −w0,?) d→ N ( 0,∇2L(w0,?)−1Cov(∇`t(w0,?))∇2L(w0,?)−1 ) =: Pw,
T · (L(ŵ0,T )− L(w0,?)) d→∆>∇2L(w0,?)∆ where ∆ ∼ Pw.
where d→ denotes convergence in distribution and `t : Rd → R is the loss function on a single task.
When this happens, we define the asymptotic rate of estimation (in MSE loss) and asymptotic excess risk ŵ0,T as those of its limiting distribution:
AsymMSE(ŵ0,T ) := E∆∼Pw [ ‖∆‖2 ] = tr ( ∇2L(w0,?)−1Cov(∇`t(w0,?))∇2L(w0,?)−1 ) AsymExcessRisk(ŵ0,T ) := E∆∼Pw [ ∆>∇2L(w0,?)∆ ] = tr ( ∇2L(w0,?)−1Cov(∇`t(w0,?)) ) .

heading: A.2 PROOF OF PROPOSITION 1

text:
Equivalence of test-time risk and training loss for train-val method We first show that
Ltr-val(w0) = E[`tr-valt (w0)] = Ltestλ,n1(w0)
for all w0, that is, the population meta-test loss is exactly the same as the population risk of the trainval method. This is straightforward: as the tasks are i.i.d. and Aλ(w0; Xtraint ,ytraint ) is independent of the test points (Xvalt ,y val t ), we have for any w0 that
E[`tr-valt (w0)] = Ept∼Π,(Xt,yt)∼pt
[ 1
2n2
∥∥yvalt −Xvalt Aλ(w0; Xtraint ,ytraint ) ∥∥2 ]
= Ept∼Π,(Xt,yt)∼pt
[ 1
2
( yvalt,1 − xval>t,1 Aλ(w0; Xtraint ,ytraint )
)2]
= E pT+1∼Π,(XT+1,yT+1),(x′,y′)iid∼pt
[ 1
2
( y′ − x′>Aλ,n1(w0; XT+1,yT+1)
)2]
= Ltestλ,n1(w0).
Therefore the train-val method is acutally a valid ERM for the test loss Ltestλ,n1 , 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
L̂tr-valT (w0) = 1
T
T∑
t=1
1
2n2
∥∥yvalt −Xvalt Aλ(w0; Xtraint ,ytraint ) ∥∥2
= 1
T
T∑
t=1
1
2n2
∥∥yvalt −Xvalt [ w0 + (X train> t X train t + n1λId) −1Xtrain>t (y train t −Xtraint w0) ]∥∥2
= 1
T
T∑
t=1
1
2n2
∥∥yvalt −Xvalt (Xtrain>t Xtraint + n1λId)−1Xtrain>t ytraint −Xvalt n1λ(Xtrain>t Xtraint + n1λId)−1w0 ∥∥2
= 1 2 w>0 MTw0 −w>0 bT + const,
where
MT := 1
T
T∑
t=1
λ2(Xtrain>t X train t /n1 + λId)
−1 X val> t X val t
n2 (Xtrain>t X train t /n1 + λId) −1,
bT := 1
T
T∑
t=1
λ(Xtrain>t X train t /n1 + λId) −1 · 1 n2
Xval>t ( yvalt −Xvalt (Xtrain>t Xtraint + n1λId)−1Xtrain>t ytraint ) .
Noticing that (Xtrain >
t X train t /n1 + λId) −1 λ−1Id and by the assumption that E(x,y)∼pt [xx>] ≺ ∞, E(x,y)∼pt [xy] < ∞, we have E[‖MT ‖] < ∞ and E[‖bT ‖] < ∞. Since the task pt’s are i.i.d., by the law of large numbers, we have with probability one that
MT → E[MT ]
= Ept,(Xt,yt) [ λ2(Xtrain>t X train t /n1 + λId) −1 X val> t X val t
n2 (Xtrain>t X train t /n1 + λId)
−1 ]
= Ept,(Xt,yt) [ λ2(Xtrain>t X train t /n1 + λId) −1Σt(X train> t X train t /n1 + λId) −1] 0,
(8)
(where Σt = Ex∼pt [xx>] 0) and bT → E[bT ]
= Ept,(Xt,yt) [ λ(Xtrain>t X train t /n1 + λId)
−1 · 1 n2
Xval>t ( yvalt −Xvalt (Xtrain>t Xtraint + n1λId)−1Xtrain>t ytraint
)]
<∞ (9)
as T →∞. Therefore, by Slutsky’s Theorem, we have ŵ0,T = M −1 T bT → E[MT ]−1E[bT ] = arg min
w0 Ltr-val(w0) = arg min w0 Ltestλ,n1(w0) = w0,?(λ, n1)
as T →∞. This proves the consistency of the train-val method.
Asymptotic normality Similar as above, we can write the per-task loss as
`t(w0) = 1
2 ‖Atw0 − ct‖2 ,
where
At = λ√ n2 Xvalt (X train> t X train t /n1 + λId) −1,
ct = 1√ n2
( yvalt −Xvalt (Xtrain>t Xtraint /n1 + λId)−1 1
n1 Xtrain>t y train t
) .
In order to show the desired asymptotic normality result, it suffices to check the conditions in Proposition 6. First, we have
∇`t(w0) = A>t (Atw0 − ct). This is Lipschitz in w0 with Lipschitz constant
∥∥A>t At ∥∥ op ≤ ‖At‖2Fr < 1
n2
∥∥Xvalt ∥∥2 Fr .
As Ex∼pt [‖x‖4] < ∞, the above quantity is clearly square integrable, therefore verifying (a). As w0,? = w0,?(λ, n1) is finite, we can use similar arguments as above to show (b) holds. Finally, we have already seen L is twice-differentiable (since it is quadratic in w0) and ∇2L(w0,?) 0, which verifies (c). Therefore the conditions of Proposition 6 hold, which yields the desired asymptotic normality result.

heading: A.3 PROOF OF PROPOSITION 2

text:
High-level idea At a high level, this proof proceeds by showing that the train-train method is also consistent to the (population) minimizer of Ltr-tr, and constructing a simple counter-example on which the minimizers of Ltr-tr is not equal to that of Ltestλ,n.
Population minimizers of Ltr-tr and Ltr-val We begin by simplifying the non-splitting risk. We have
`tr-trt (w0) = 1
2n ‖yt −XtAλ(w0; Xt,yt)‖2
= 1
2n
∥∥yt −Xt [ w0 + (X > t Xt + nλId) −1X>t (yt −Xtw0) ]∥∥2
= 1
2 ‖Atw0 − ct‖2 ,
where
At = 1√ n nλXt(X > t Xt + nλId) −1 and ct = 1√ n
( In −Xt(X>t Xt + nλId)−1X>t ) yt.
Using similar arguments as in the proof of Proposition 1 (Appendix A.2), we see that the traintrain method ŵtr-tr0,T converges with probability one to the minimizer of the pouplation risk L
tr-tr, which is
wtr-tr0,? = arg min w0
Ltr-tr(w0) = ( E[A>t At] )−1E[A>t ct]
= E [ λ2(X>t Xt/n+ λId) −2 X > t Xt n ]−1 · E [ 1 n λ(X>t Xt/n+ λId) −1X>t (In −Xt(X>t Xt + nλId)−1X>t )yt ] = E [ λ2(X>t Xt/n+ λId) −2 X > t Xt n ]−1 · E [ λ2(X>t Xt/n+ λId) −2 1 n X>t yt ] .
(10)
On the other hand, recall from Proposition 1 ((8) and (9)) that the population minimizer of Ltestλ,n is
w0,?(λ, n) = arg min w0
Ltestλ,n(w0)
= E [ λ2(X>t Xt/n+ λId) −1Σt(X > t Xt/n+ λId) −1]−1 · { λE [ (X>t Xt/n+ λId) −1]Ept,(x′,y′)∼pt [x′y′]
− λE [ (X>t Xt/n+ λId) −1Σt(X > t Xt/n+ λId)
−1 1 n X>t yt
]} .
(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:
pt : (xt,i, yt,i) = { (1, 3) with probability 1/2; (3,−1) with probability 1/2.
Clearly, we have Σt = 5, st := X>t Xt/n ∈ [1, 9], and Ex′,y′∼pt [x′y′] = 0. Therefore we have
wtr-tr0,? = E [ (st + λ) −2st ]−1 · E [ (st + λ)
−2 1 n
n∑
i=1
xt,iyt,i
] ,
and
w0,?(λ, n) = −E [ 5λ2(st + λ) −2]−1 · E [
5λ(st + λ) −2 1 n
n∑
i=1
xt,iyt,i
]
= −E [ λ(st + λ) −2]−1 · E [
(st + λ) −2 1 n
n∑
i=1
xt,iyt,i
] .
We now show that wtr-tr0,? 6= w0,?(λ, n) by showing that
E [ (st + λ)
−2 1 n
n∑
i=1
xt,iyt,i
] = E [ xt,1yt,1
(st + λ)2
] 6= 0
for any λ > 0. Indeed, conditioning on (xt,1, yt,1) = (1, 3), we know that the sum-of-squares in st has one term that equals 1, and all others i.i.d. being 1 or 9 with probability one half. On the other hand, if we condition on (xt,1, yt,1) = (3,−1), then we know the sum in st 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 [ xt,1yt,1
(st + λ)2
] = 1
2 · 3E
[ 1
(st + λ)2
∣∣∣∣(xt,1, yt,1) = (1, 3) ]
+ 1
2 · −3E
[ 1
(st + λ)2
∣∣∣∣(xt,1, yt,1) = (3,−1) ] > 0.
This shows wtr-tr0,? 6= w0,?(λ, n) and consequently the ŵtr-tr0,T does not converge to w0,?(λ, n) and the difference is bounded away from zero as T →∞. Finally, for this distribution, the risk Ltestλ,n(w0) is strongly convex (since it has a positive second derivative), this further implies that Ltestλ,n(ŵ tr-tr 0,T ) − Ltestλ,n(w0,?(λ, n)) is bounded away from zero almost surely as T →∞.

heading: B PROOFS FOR SECTION 4

heading: B.1 PROOF OF THEOREM 3

text:
We first show that w0,? = Ewt∼Π[wt] is a global optimizer for Ltr-tr and Ltr-val with any regularization coefficient λ > 0, any n, and any split (n1, n2). To do this, it suffices to check that the gradient at w0,? is zero and the Hessian is positive definite (PD).
Optimality of w0,? in both Ltr-tr and Ltr-val. We first look at Ltr-tr: for any w0 ∈ Rd we have Ltr-tr(w0) = E[`tr-trt (w0)]
= 1 2n E [∥∥∥Xtwt −Xt [( X>t Xt + nλId )−1 X>t (Xtwt −Xtw0) + w0 ]∥∥∥ 2 ]
= 1 2n E [∥∥∥Xt ( Id − ( X>t Xt + nλId )−1 X>t Xt ) (wt −w0) ∥∥∥ 2] . (12)
Similarly, Ltr-val can be written as
Ltr-val(w0) (13)
= E[`tr-valt (w0)]
= 1 2n2 E [∥∥∥Xvalt wt −Xvalt [( (Xtraint ) >Xtraint + n1λId )−1 (Xtraint ) > (Xtraint wt −Xtraint w0 ) + w0 ]∥∥∥ 2 ]
= 1 2n2 E [∥∥∥Xvalt ( Id − ( (Xtraint ) >Xtraint + n1λId )−1 (Xtraint ) >Xtraint ) (wt −w0) ∥∥∥ 2] . (14)
We denote
Mtr-trt = Xt ( Id − ( X>t Xt + nλId )−1 X>t Xt ) and (15)
Mtr-valt = X val t ( Id − ( (Xtraint ) >Xtraint + n1λId )−1 (Xtraint ) >Xtraint ) (16)
to simplify the notations in (12) and (14). We take gradient of Ltr-tr and Ltr-val with respect to w0:
∇w0Ltr-tr(w0) = − 1 n E [ (Mtr-trt ) >Mtr-trt (wt −w0) ] , (17) ∇w0Ltr-val(w0) = − 1
n2 E [ (Mtr-valt ) >Mtr-valt (wt −w0) ] . (18)
Substituting w0,? into (17) and taking expectation, we deduce
∇w0Ltr-tr(w0,?) = − 1 n E [ (Mtr-trt ) >Mtr-trt (wt −w0,?) ] = 0. (19)
To see this, observe that by definition E[wt − w0,?] = 0. Combining with wt being generated independently of Xt, we have the first term in RHS of (19) vanish. In addition, zt is independent white noise, therefore, the second term in RHS of (19) also vanishes. Following the same argument, we can show
∇w0Ltr-val(w0,?) = 0, since X′t is also independent of wt. The above reasonings indicates that w0,? is a stationary point of both Ltr-tr and Ltr-val. The remaining step is to check ∇w0Ltr-tr(w0,?) and ∇w0Ltr-val(w0,?) are PD. From (17) and (18), we derive respectively the hessian of Ltr-tr and Ltr-val as
∇2w0Ltr-tr(w0,?) = 1 n E[(Mtr-trt )>Mtr-trt ] and
∇2w0Ltr-val(w0,?) = 1 n2 E[(Mtr-valt )>Mtr-valt ].
Let v ∈ Rd be any nonzero vector, we check v>∇2w0Ltr-tr(w0,?)v > 0. A key observation is that ( Id − ( X>t Xt + nλId )−1 X>t Xt ) is positive definite for any λ 6= 0. To see this, let σ1 ≥ · · · ≥ σd be eigenvalues of 1nX>t Xt, some algebra yields the eigenvalues of( Id − ( X>t Xt + nλId )−1 X>t Xt ) are λλ+σi > 0 for λ 6= 0 and i = 1, . . . , d. Hence, we deduce
v>∇2w0Ltr-tr(w0,?)v = 1 n E[v>X>t
( Id − ( X>t Xt + nλId )−1 X>t Xt )2 Xtv] > 0, (20)
since Xt is isotropic (an explicit computation of the hessian matrix can be found in Appendix B.2). As a consequence, we have shown that w0,? is a global optimum of Ltr-tr. The same argument applies to Ltr-val, and the proof is complete.
Consistency of ŵ{tr-tr,tr-val}0,T . To check the consistency, we need to verify the conditions (a) – (c) in Proposition 6.
For condition (a), we derive from (17) and (18) that ∥∥∥∇`{tr-tr,tr-val}t (w1)−∇`{tr-tr,tr-val}t (w2) ∥∥∥ ≤ 1 n ∥∥∥(M{tr-tr,tr-val}t )>M{tr-tr,tr-val}t ∥∥∥ op ‖w1 −w2‖,
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-tr,tr-val}t )>M{tr-tr,tr-val}t ∥∥∥ op ] <∞, which follows from the same argument in the proof of Proposition 1. In particular, we know 0 Id− ( X>t Xt + nλId )−1 X>t Xt Id
and E[ ∥∥X>t Xt ∥∥ op
] < ∞ since Xt is Gaussian. As a consequence, for the no-split method, we have E [∥∥(Mtr-trt )>Mtr-trt ∥∥2
op
] < ∞. For the split method, we also have 0 Id −
( (Xtraint ) >Xtraint + nλId )−1 (Xtraint ) >Xtraint Id and E[ ∥∥(Xvalt )>Xvalt ∥∥ op ] < ∞, which implies
E [∥∥(Mtr-valt )>Mtr-valt ∥∥2 op ] <∞.
For condition (b), using a similar argument in condition (a) and combining with R2 = E[‖w0,? − wt‖2], we have E[‖∇`{tr-tr,tr-val}t (w0,?)‖2] <∞. For condition (c), using (20), we directly verify that L{tr-tr,tr-val} is twice-differentiable and ∇2L{tr-tr,tr-val} 0.

heading: B.2 PROOF OF LEMMA 5

text:
Proof. In this section we prove Lemma 5. Using the the asymptotic normality in Proposition 6, the asymptotic covariance is∇−2L{tr-tr,tr-val}Cov[∇`{tr-tr,tr-val}t ]∇−2L{tr-tr,tr-val}. Therefore, in the following, we only need to find ∇−2L{tr-tr,tr-val} and Cov[∇`{tr-tr,tr-val}t ]. • Asymptotic variance of ŵtr-tr0,T . We begin with the computation of the expected Hessian 1 nE[(M tr-tr t ) >Mtr-trt ].
E[(Mtr-trt )>Mtr-trt ]
= E [( Id − ( X>t Xt + nλId )−1 X>t Xt )> X>t Xt ( Id − ( X>t Xt + nλId )−1 X>t Xt )]
(i) = E [ Vt ( Id − (D>t Dt + nλId)−1D>t Dt )> D>t Dt ( Id − (D>t Dt + nλId)−1D>t Dt ) V>t ] ,
(21)
where the equality (i) is obtained by plugging in the SVD of Xt = UtDtV>t with Ut ∈ Rn×n, Dt ∈ Rn×d, and Vt ∈ Rd×d. A key observation is that Ut and Vt are independent, since Xt is isotropic, i.e., homogeneous in each orthogonal direction. To see this, for any orthogonal matrices Q ∈ Rn×n and P ∈ Rd×d, we know Xt and QXtP> share the same distribution. Moreover, we have QXtP> = (QUt)Dt(PVt)> as the SVD. This shows that the left and right singular matrices are independent and both uniformly distributed on all the orthogonal matrices of the corresponding dimensions (Rn×n and Rd×d, respectively).
Recall that we denote σ(n)1 ≥ · · · ≥ σ (n) d as the eigenvalues of 1 nX > t Xt. Thus, we have D > t Dt = Diag(nσ (n) 1 , . . . , nσ (n) d ). We can further simplify (21) as
E [ Vt ( Id − (D>t Dt + nλId)−1D>t Dt )> D>t Dt ( Id − (D>t Dt + nλId)−1D>t Dt ) V>t ]
= E [ VtDiag ( nλ2σ (n) 1
(σ (n) 1 + λ)
2 , . . . ,
nλ2σ (n) d
(σ (n) d + λ) 2
) V>t ]
= E
[ d∑
i=1
nλ2σ (n) i
(σ (n) i + λ)
2 vt,iv
> t,i
] . (22)
We will utilize the isotropicity of Xt to find (22). Recall that we have shown that Vt is uniform on all the orthogonal matrices. Let P ∈ Rd×d be any permutation matrix, then VtP has the same distribution as Vt. For this permuted data matrix VtP, (22) becomes
E
[ d∑
i=1
nλ2σ (n) i
(σ (n) i + λ)
2 vt,τp(i)v
> t,τp(i) ] with τp(i) denotes the permutation of the i-th element in P.
Summing over all the permutations P (and there are totally d! instances), we deduce
d!E[(Mtr-trt )>Mtr-trt ]
= ∑
all permutation τp
E
[ d∑
i=1
nλ2σ (n) i
(σ (n) i + λ)
2 vt,τp(i)v
> t,τp(i)
]
= (d− 1)!E
  d∑
j=1
[ d∑
i=1
nλ2σ (n) i
(σ (n) i + λ) 2
] vt,jv > t,j
= (d− 1)!E [ VtDiag ( d∑
i=1
λ2σ (n) i
(λ+ σ (n) i )
2 , . . . ,
d∑
i=1
λ2σ (n) i
(λ+ σ (n) i ) 2
) V>t ]
= (d− 1)!E [ d∑
i=1
λ2σ (n) i
(λ+ σ (n) i )
2 VtIdV
> t
] (23)
Dividing (d− 1)! on both sides of (23) yields
E[(Mtr-trt )>Mtr-trt ] = n
d E
[ d∑
i=1
λ2σ (n) i
(λ+ σ (n) i ) 2
] Id. (24)
Next, we find the expected covariance matrix 1n2E[∇`tr-trt (w0,?)(∇`tr-trt (w0,?))>].
E[∇`tr-trt (w0,?)(∇`tr-trt (w0,?))>] = E[(Mtr-trt )>Mtr-trt (w0,? −wt)(w0,? −wt)>(Mtr-trt )>Mtr-trt ] (i) = E [ VtDiag ( nλ2σ (n) 1
(σ (n) 1 + λ)
2 , . . . ,
nλ2σ (n) d
(σ (n) d + λ) 2
) V>t (w0,? −wt)(w0,? −wt)>
·VtDiag ( nλ2σ (n) 1
(σ (n) 1 + λ)
2 , . . . ,
nλ2σ (n) d
(σ (n) d + λ) 2
) V>t ] . (25)
Here step (i) uses the SVD of Xt and the computation in (22). Combining (24) and (25), we derive the asymptotic covariance matrix of using Ltr-tr as
AsymCov(ŵtr-tr0,T )
= E[∇−2`tr-trt ]Cov[∇`tr-trt (w0,?)]E[∇−2`tr-trt ]
= d2
n2
( E [ d∑
i=1
λ2σ (n) i
(λ+ σ (n) i ) 2
])−2
· E [ VtDiag ( nλ2σ (n) 1
(σ (n) 1 + λ)
2 , . . . ,
nλ2σ (n) d
(σ (n) d + λ) 2
) V>t (w0,? −wt)(w0,? −wt)>
·VtDiag ( nλ2σ (n) 1
(σ (n) 1 + λ)
2 , . . . ,
nλ2σ (n) d
(σ (n) d + λ) 2
) V>t ] . (26)
Taking trace in (26), we deduce
AsymMSE(ŵtr-tr0,T )
= tr(AsymCov(ŵtr-tr0,T ))
= d2
n2
( E [ d∑
i=1
λ2σ (n) i
(λ+ σ (n) i ) 2
])−2
· tr ( E [ VtDiag ( n2λ4(σ (n) 1 ) 2
(σ (n) 1 + λ)
4 , . . . ,
n2λ4(σ (n) d ) 2 (σ (n) d + λ) 4
) V>t (w0,? −wt)(w0,? −wt)> ])
(i) = d2
n2
( E [ d∑
i=1
λ2σ (n) i
(λ+ σ (n) i ) 2
])−2
· n 2
d tr
( E [ d∑
i=1
λ4(σ (n) i ) 2 (λ+ σ (n) i ) 4 VtIdV > t (w0,? −wt)(w0,? −wt)>
])
= d E [∑d i=1 λ 4(σ (n) i ) 2/(λ+ σ (n) i ) 4 ]
( E [∑d
i=1 λ 2σ (n) i /(λ+ σ (n) i )
2 ])2 · tr
( E[(w0,? −wt)(w0,? −wt)>] )
= dR2 E [∑d i=1(σ (n) i ) 2/(λ+ σ (n) i ) 4 ]
( E [∑d
i=1 σ (n) i /(λ+ σ (n) i )
2 ])2 , (27)
where step (i) utilizes the independence between wt and Xt and applies the permutation trick in
(23) to find E [ VtDiag ( n2λ4(σ (n) 1 ) 2
(σ (n) 1 +λ)
4 , . . . ,
n2λ4(σ (n) d ) 2
(σ (n) d +λ) 4
) V>t ] .
• Asymptotic variance of ŵtr-val0,T . Similar to the no-split case, we compute the Hessian 1 n2 E[∇2`tr-valt ] = 1n2E[(M tr-val t ) >Mtr-valt ] first.
E[(Mtr-valt )>Mtr-valt ]
= E [( Id − ( (Xtraint ) >Xtraint + n1λId )−1 (Xtraint ) >Xtraint )> (Xvalt ) >Xvalt
· ( Id − ( (Xtrain)>t X train t + n1λId )−1 (Xtraint ) >Xtraint )]
(i) = n2E [( Id − ( (Xtraint ) >Xtraint + n1λId )−1 ((Xtraint ) >Xtraint )>
· ( Id − ( (Xtrain)>t X train t + n1λId )−1 (Xtraint ) >Xtraint )]
(ii) = n2E [ Vtraint ( Id − ((Dtraint )>Dtraint + n1λId)−1(Dtraint )>Dtraint )2 (Vtraint ) > ] , (28)
where (i) uses the data generating assumption E[(Xvalt )>Xvalt ] = n2Id and the independence between Xtraint and X val t , and (ii) follows from the SVD of X train t = U train t D train t (V train t ) >.
Here we denote σ(n1)1 ≥ · · · ≥ σ (n1) d as the eigenvalues of 1 n1 (Xtraint ) >Xtraint . Thus, we have (Dtraint ) >Dtraint = Diag(n1σ (n1) 1 , . . . , n1σ (n1) d ). We can now further simplify (28) as
n2E [ Vtraint ( Id − ((Dtraint )>Dtraint + n1λId)−1(Dtraint )>Dtraint )2 (Vtraint ) > ]
(i) = n2E [ Vtraint Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) (Vtraint ) > ]
(ii) = n2 d E
[ d∑
i=1
λ2
(λ+ σ (n1) i ) 2
] Id. (29)
Step (i) follows from the same computation in (22), and step (ii) uses the permutation trick in (23).
Next, we find the expected covariance matrix 1 n22 E[∇`tr-trt (w0,?)(∇`tr-trt (w0,?))>].
E[∇`tr-trt (w0,?)(∇`tr-trt (w0,?))>] = E[(Mtr-trt )>Mtr-trt (w0,? −wt)(w0,? −wt)>(Mtr-trt )>Mtr-trt ] = E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(w0,? −wt)(w0,? −wt)>
·Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) > ] . (30)
Combining (29) and (30), we derive the asymptotic covariance matrix of using Ltr-val as
AsymCov(ŵtr-val0,T )
= E[∇−2`tr-valt ]Cov[∇`tr-valt (w0,?)]E[∇−2`tr-valt ]
= d2
n22
( E [ d∑
i=1
λ2
(λ+ σ (n1) i ) 2
])−2
· E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(w0,? −wt)(w0,? −wt)>
·Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) > ] . (31)
Taking trace in (31), we deduce
AsymMSE(ŵtr-tr0,T )
= tr(AsymCov(ŵtr-tr0,T ))
= d2
n22
( E [ d∑
i=1
λ2
(λ+ σ (n1) i ) 2
])−2
· tr ( E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(w0,? −wt)(w0,? −wt)>
·Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) > ])
(i) = d2
n22
( E [ d∑
i=1
λ2
(λ+ σ (n) i ) 2
])−2
· tr ( E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(w0,? −wt)(w0,? −wt)> ]) ,
(32)
where (i) follows from the cyclic property of the matrix trace operation. Due to the isotropicity of Xtraint and X val t , we claim that
E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) > ]
(33)
is a diagonal matrix cId with all the diagonal elements identical. We can show the claim bying taking expectation with respect to Xvalt first. Since V train t is an orthogonal matrix, X val t V train t has the same distribution as Xvalt and independent of Xt. We verify that any off-diagonal element of the matrix expectation
A := EXvalt [ (Vtraint ) >(Xvalt ) >Xvalt V train t Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
)
· (Vtraint )>(Xvalt )>Xvalt Vtraint ]
is zero. We denote Xvalt V train t = [x1, . . . ,xn] > ∈ Rn2×d with xi iid∼ N(0, Id). For k 6= `, the (k, `)-th entry Ak,` of A is
Ak,` = E
 ∑
j
( λ2
(σ (n1) j + λ) 2
(∑
i
xk,ixj,i
)(∑
i
xj,ix`,i
))
= E
 ∑
j
λ2
(σ (n1) j + λ) 2
(∑
m,n
xk,mxj,mxj,nx`,n
)
(i) = 0,
where xi,j denotes the j-th element of xi. Equality (i) holds, since either xk,m or x`,n only appears once in each summand. Therefore, we can write A = Diag (A1,1, . . . , Ad,d) with Ak,k being
Ak,k = E
 ∑
j
λ2
(σ (n1) j + λ) 2
(∑
m,n
xk,mxj,mxj,nx`,n
)
= E
[ λ2
(σ (n1) k + λ) 2
(∑
m,n
xk,mxk,mxk,nxk,n
)] .
Observe that Ak,k only depends on σ (n1) k . Plugging back into (33), we have
E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) > ]
= E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) Diag(A1,1, . . . , Ad,d)
·Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) > ]
= E [ Vtraint Diag ( λ2A1,1
(σ (n1) 1 + λ)
2 , . . . ,
λ2Ad,d
(σ (n1) d + λ) 2
) (Vtraint ) > ]
(i) = cId,
where equality (i) utilizes the permutation trick in (24). To this end, it is sufficient to find c as
c = 1
d tr
( E [ Vtraint Diag ( λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ
σ (n1) 1 + λ
, . . . , λ
σ (n1) d + λ
) (Vtraint ) > ])
= 1
d tr
( E [ Xvalt V train t Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) (Vtraint ) >(Xvalt ) >
·Xvalt Vtraint Diag (
λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) (Vtraint ) >(Xvalt ) > ]) . (34)
Observe again that Xvalt V train t ∈ Rn2×d is a Gaussian random matrix. We rewrite (34) as
c = 1
d E
    n2∑
i,j=1
v>i Diag
( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) vj   2   , (35)
where vi iid∼ N(0, Id) is i.i.d. Gaussian random vectors for i = 1, . . . , n2. To compute (35), we need the following result.
Claim 7. Given any symmetric matrix A ∈ Rd×d and i.i.d. standard Gaussian random vectors v,u
iid∼ N(0, Id), we have E [ (v>Av)2 ] = 2‖A‖2Fr + tr2(A) and (36)
E [ (v>Au)2 ] = ‖A‖2Fr. (37)
Proof of Claim 7. We show (36) first. We denote Ai,j as the (i, j)-th element of A and vi as the i-th element of v. Expanding the quadratic form, we have
E [ (v>Av)2 ] = E   ∑
i,j,k,`≤d vivjvkv`Ai,jAk,`

= E
 ∑
i≤d v4iA 2 i,i
 + E  ∑
i 6=j v2i v 2 j (A 2 i,j +Ai,iAj,j +Ai,jAj,i)

= 3 ∑
i≤d A2i,i +
∑ i 6=j (A2i,j +Ai,iAj,j +Ai,jAj,i)
= tr2(A) + 2 ∑
i≤d A2i,i +
∑ i 6=j (A2i,j +Ai,jAj,i)
= tr2(A) + 2‖A‖2Fr. Next, we show (37) by the cyclic property of race.
E [ (v>Au)2 ] = tr ( E [ uu>Avv>A ]) = tr(A2) = ‖A‖2Fr.
We back to the computation of (35) using Claim 7.
c = 1
d E
  n2∑
i,j=1
( v>i Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) vj )2
= 1
d E
  n2∑
i=1
( v>i Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) vi )2
+ 1
d E
 ∑
i 6=j
( v>i Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
) vj )2
= n2 d E
[ tr2 ( Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
))]
+ 2 n2 d E   ∥∥∥∥∥Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
)∥∥∥∥∥ 2
Fr

+ n2(n2 − 1)
d E   ∥∥∥∥∥Diag ( λ2
(σ (n1) 1 + λ)
2 , . . . ,
λ2
(σ (n1) d + λ) 2
)∥∥∥∥∥ 2
Fr

= n2 d
 E [ d∑
i=1
λ2
(σ (n1) i + λ) 2
]2 + (n2 + 1)E [ d∑
i=1
λ4
(σ (n1) i + λ) 4
]  . (38)
Combining (38) and (33), by the independence between wt and Xtraint ,X val t , we compute (32) as
AsymMSE(ŵtr-tr0,T )
= d2
n22
( E [ d∑
i=1
λ2
(λ+ σ (n1) i ) 2
])−2
· n2 d
 E [ d∑
i=1
λ2
(σ (n1) i + λ) 2
]2 + (n2 + 1)E [ d∑
i=1
λ4
(σ (n1) i + λ) 4
]
· E [ (w0,? −wt)(w0,? −wt)> ]
= dR2
n2
E [∑d
i=1 λ 2/(σ (n1) i + λ)
2 ]2 + (n2 + 1)E [∑d i=1 λ 4/(σ (n1) i + λ) 4 ]
( E [∑d
i=1 λ 2/(λ+ σ (n1) i )
2 ])2 .
The proof is complete.
B.3 OPTIMAL RATE OF THE TRAIN-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 (n1, n2) = (n1, n−n1), the optimal rate (by tuning the regularization λ > 0) of the train-val method is achieved at
inf λ>0
AsymMSE ( ŵtr-val0,T (n1, n2;λ) ) = lim λ→∞ AsymMSE ( ŵtr-val0,T (n1, n2;λ) ) = (d+ n2 + 1)R 2 n2 .
Further optimizing the rate over n2, the best rate is taken at (n1, n2) = (0, n), in which the rate is
infλ>0, n2∈[n] AsymMSE ( ŵtr-val0,T (n1, n2;λ) ) = (d+ n+ 1)R2
n .
Discussion: Using all data as validation Corollary 8 suggests that the optimal asymptotic rate of the train-val method is obtained at λ =∞ and (n1, n2) = (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 no training data, the inner solver reduces to the identity map: A∞,0(w0; Xt,yt) = w0, and the outer loop reduces to learning a single linear model w0 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 to other meta-learning problems, we do find experimentally that using more data as validation (than training) can also improve the performance on real metalearning tasks (see Table 2).
Proof of Corollary 8 Fix n1 ∈ [n] and n2 = n− n1. Recall from Lemma 5 that
AsymMSE ( ŵtr-val0,T (n1, n2;λ) ) = dR2 n2 · E [(∑d i=1 λ 2/(σ (n1) i + λ) 2 )2 + (n2 + 1) ∑d i=1 λ 4/(σ (n1) i + λ) 4 ]
( E [∑d
i=1 λ 2/(σ (n1) i + λ)
2 ])2 .
Clearly, as λ→∞, we have
lim λ→∞
AsymMSE ( ŵtr-val0,T (n1, n2;λ) ) = dR2
n2 · d
2 + (n2 + 1)d
d2 =
(d+ n2 + 1)R 2
n2 .
It remains to show that the above quantity is a lower bound for AsymMSE ( ŵtr-val0,T (n1, n2;λ) ) for any λ > 0, which is equivalent to E [(∑d
i=1 λ 2/(σ (n1) i + λ)
2 )2
+ (n2 + 1) ∑d i=1 λ 4/(σ (n1) i + λ) 4
]
( E [∑d
i=1 λ 2/(σ (n1) i + λ)
2 ])2 ≥
d+ n2 + 1
d , for all λ > 0.
(39)
We now prove (39). For i ∈ [n1], define random variables
Xi := λ2
(σ (n1) i + λ)
2 ∈ [0, 1] and Yi := 1−Xi ∈ [0, 1].
Then the left-hand side of (39) can be rewritten as
E [ (d− n1 + ∑n1 i=1Xi) 2 + (n2 + 1) ( d− n1 + ∑n1 i=1X 2 i )]
(E[d− n1 + ∑n i=1Xi]) 2
= E [ (d−∑n1i=1 Yi) 2 + (n2 + 1) ( d− 2∑n1i=1 Yi + ∑n1 i=1 Y 2 i )]
(E[d−∑n1i=1 Yi]) 2
= d2 + (n2 + 1)d− 2(d+ n2 + 1)E[
∑ Yi] + E [ ( ∑ Yi) 2 ] + (n2 + 1)E [∑ Y 2i ]
d2 − 2dE[∑Yi] + (E[ ∑ Yi]) 2
By algebraic manipulation, inequality (39) is equivalent to showing that
E [ ( ∑ Yi) 2 ] + (n2 + 1)E [∑ Y 2i ]
(E[ ∑ Yi])
2 ≥ d+ n2 + 1
d . (40)
Clearly, E[( ∑ Yi) 2] ≥ (E[∑Yi])2. By Cauchy-Schwarz we also have
E [∑
Y 2i ] ≥ 1 n1 E [(∑ Yi )2] ≥ 1 n1 ( E [∑ Yi ])2 .
Therefore we have E [ ( ∑ Yi) 2 ] + (n2 + 1)E [∑ Y 2i ]
(E[ ∑ Yi])
2 ≥ 1 + n2 + 1 n1 ≥ 1 + n2 + 1 d = d+ n2 + 1 d ,
where we have used that n1 ≤ n ≤ d. This shows (40) and consequently (39).

heading: B.4 RATE OF THE TRAIN-TRAIN METHOD IN THE PROPORTIONAL LIMIT

text:
Theorem 9 (Exact rates of the train-train method in the proportional limit). In the high-dimensional limiting regime d, n→∞, d/n→ γ where γ ∈ (0,∞) is a fixed shape parameter, for any λ > 0
limd,n→∞,d/n=γ AsymMSE ( ŵtr-tr0,T (n;λ) ) = ρλ,γR 2.
where ρλ,γ =4γ2 [ (γ − 1)2+(γ + 1)λ ] /(λ+1+γ− √ (λ+ γ + 1)2 − 4γ)2/ ( (λ+ γ + 1)2 − 4γ )3/2 .
Proof of Theorem 9 Let Σ̂n := 1nXtX > t denote the sample covariance matrix of the inputs in a single task (t). By Lemma 5, we have
AsymMSE(ŵtr-tr0,T (n;λ)) = R 2 ·
1 dE [∑d i=1 σi(Σ̂n) 2/(σi(Σ̂n) + λ) 4 ]
( 1 dE [∑d i=1 σi(Σ̂n)/(σi(Σ̂n) + λ) 2 ])2
= R2 · 1 d E [ tr ( (Σ̂n + λId) −4Σ̂2n )]
︸ ︷︷ ︸ In,d
/{ 1 d E [ tr ( (Σ̂n + λId) −2Σ̂n )]
︸ ︷︷ ︸ IIn,d
}2 .
(41)
We now evaluate quantities In,d and IIn,d in the high-dimensional limit of d, n → ∞, d/n → γ ∈ (0,∞). Consider the (slightly generalized) Stieltjes transform of Σ̂n defined for all λ1, λ2 > 0:
s(λ1, λ2) := lim d,n→∞, d/n→γ
1 d E [ tr ( (λ1Id + λ2Σ̂n) −1 )] .
As the entries of Xt are i.i.d. N(0, 1), the above limiting Stieltjes transform is the Stieltjes form of the Marchenko-Pastur law, which has a closed form (see, e.g. (Dobriban et al., 2018, Equation (7)))
s(λ1, λ2) = λ −1 2 s(λ1/λ2, 1) =
1 λ2 · γ − 1− λ1/λ2 +
√ (λ1/λ2 + 1 + γ)2 − 4γ
2γλ1/λ2
= γ − 1− λ1/λ2 +
√ (λ1/λ2 + 1 + γ)2 − 4γ
2γλ1 .
(42)
Now observe that differentiating s(λ1, λ2) yields quantity II (known as the derivative trick of Stieltjes transforms). Indeed, we have
− d dλ2 s(λ1, λ2) = − d dλ2 lim d,n→∞, d/n→γ 1 d E [ tr ( (λ1Id + λ2Σ̂n) −1 )]
= lim d,n→∞, d/n→γ
1 d E [ − d dλ2 tr ( (λ1Id + λ2Σ̂n) −1 )]
= lim d,n→∞, d/n→γ
1 d E [ tr ( (λ1Id + λ2Σ̂n) −2Σ̂n )] .
(43)
(Above, the exchange of differentiation and limit is due to the uniform convergence of the derivatives, which holds at any λ1, λ2 > 0. See Appendix B.4.1 for a detailed justification.) Taking λ1 = λ and λ2 = 1, we get
lim d,n→∞, d/n→γ IIn,d = lim d,n→∞, d/n→γ
1 d E [ tr ( (λId + Σ̂n) −2Σ̂n )] = − d dλ2 s(λ1, λ2)|λ1=λ,λ2=1.
Similarly we have
lim d,n→∞, d/n→γ In,d = lim d,n→∞,d/n→γ
1 d E [ tr ( (λId + Σ̂n) −4Σ̂2n )] = −1 6 d
dλ1
d2
dλ22 s(λ1, λ2)|λ1=λ,λ2=1.
Evaluating the right-hand sides from differentiating the closed-form expression (42), we get
lim d,n→∞, d/n→γ
In,d = 1 2γ · λ+ 1 + γ√ (λ+ 1 + γ)2 − 4γ − 1 2γ ,
lim d,n→∞, d/n→γ
IIn,d = (γ − 1)2 + (γ + 1)λ
((λ+ 1 + γ)2 − 4γ)5/2 .
Substituting back to (41) yields that
lim d,n→∞, d/n→γ AsymMSE(ŵtr-tr0,T (n;λ)) = lim d,n→∞, d/n→γ R2 · In,d/II2n,d
= R2 · 4γ 2 [ (γ − 1)2 + (γ + 1)λ ]
((λ+ 1 + γ)2 − 4γ)5/2 · (
λ+1+γ√ (λ+1+γ)2−4γ
− 1 )2
= R2 · 4γ 2 [ (γ − 1)2 + (γ + 1)λ ]
((λ+ 1 + γ)2 − 4γ)3/2 · ( λ+ 1 + γ − √ (λ+ 1 + γ)2 − 4γ )2 .
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 Σ = Σ̂n = X>t Xt/n denote the empirical covariance matrix of Xt. We wish to show that d
dλ2 lim d,n→∞,d/n→γ 1 d E [ tr ( (λ1Id + λ2Σ) −1)] = lim d,n→∞,d/n→γ 1 d E [ d dλ2 tr ( (λ1Id + λ2Σ) −1) ] .
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),
d dλ2 E [ tr ( (λ1Id + λ2Σ)
−1)] = E [ d
dλ2 tr ( (λ1Id + λ2Σ)
−1) ] .
By definition of the derivative, we have
d dλ2 E [ tr ( (λ1Id + λ2Σ) −1)] = lim t→0 E
[ tr ( (λ1Id + λ2Σ + tΣ) −1)− tr ( (λ1Id + λ2Σ) −1)
t
] .
For any A 0, the function t 7→ tr((A+tB)−1) is continuously differentiable at t = 0 with derivative −tr(A−2B), and thus locally Lipschitz around t = 0 with Lipschitz constant |tr(A−2B)|+ 1. Applying this in the above expectation with A = λ1Id + λ2Σ λ1Id and B = Σ, we get that for sufficiently small |t|, the fraction inside the expectation is upper bounded by |tr(λ−21 Σ)| + 1 < ∞ uniformly over t. Thus by the Dominated Convergence Theorem, the limit can be passed into the expectation, which yields the expectation of the derivative.
Interchange of derivative and limit Define fn,d(λ2) := 1dE [ tr ( (λ1Id + λ2Σ) −1)]. It suffices to show that
d
dλ2 lim d,n→∞,d/n→γ fn,d(λ2) = lim d,n→∞,d/n→γ f ′n,d(λ2),
where
f ′n,d(λ2) = E [ d
dλ2
1 d tr ( (λ1Id + λ2Σ)
−1) ]
= −1 d E [ tr ( (λ1Id + λ2Σ) −2Σ )]
by the result of the preceding part.
As fn,d(λ2)→ s(λ1, λ2) pointwise over λ2 by properties of the Wishart matrix (Bai & Silverstein, 2010) and each individual fn,d is differentiable, it suffices to show that the derivatives f ′n,d(λ̃2) converges uniformly for λ̃2 in a neighborhood of λ2. Observe that can rewrite f ′n,d as
f ′n,d(λ̃2) = −Eµ̂n,d [ Eλ∼µ̂n,d [ gλ̃2(λ) ]] ,
where µ̂n,d is the empirical distribution of the eigenvalues of Σ, and
gλ̃2(λ) := λ (λ1 + λ̃2λ)2 ≤ 1 λ1λ̃2 for all λ ≥ 0.
Therefore, as µ̂n,d converges weakly to the Marchenko-Pastur distribution with probability one and gλ̃2 is uniformly bounded for λ̃2 in a small neighborhood of λ2, we get that f ′ n,d(λ̃2) does converge uniformly to the expectation of gλ̃2(λ) under the Marchenko-Pastur distribution. This shows the desired interchange of derivative and limit.

heading: B.5 PROOF OF THEOREM 4

text:
Throughout this proof we assume thatR2 = 1 without loss of generality (as all the rates are constant multiples of R2).
Part I: Optimal rate for Ltr-tr By Theorem 9, we have
inf λ>0 lim d,n→∞,d/n=γ
AsymMSE ( ŵtr-tr0,T (n;λ) )
= inf λ>0
4γ2 [ (γ − 1)2 + (γ + 1)λ ]
(λ+ 1 + γ − √
(λ+ γ + 1)2 − 4γ)2 · ((λ+ γ + 1)2 − 4γ)3/2︸ ︷︷ ︸ :=f(λ,γ)
.
In order to bound infλ>0 f(λ, γ), picking any λ = λ(γ) gives f(λ(γ), γ) as a valid upper bound, and our goal is to choose λ that yields a bound as tight as possible. Here we consider the choice
λ = λ(γ) = max {1− γ/2, γ − 1/2} = (1− γ/2)1 {γ ≤ 1}+ (γ − 1/2)1 {γ > 1} which we now show yields the claimed upper bound.
Case 1: γ ≤ 1 Substituting λ = 1− γ/2 into f(λ, γ) and simplifying, we get
f(1− γ/2, γ) = 2(γ 2 − 3γ + 4)
(2− γ/2)3 =: g1(γ).
Clearly, g1(0) = 1 and g1(1) = 32/27. Further differentiating g1 twice gives
g′′1 (γ) = γ2 + 7γ + 4
(2− γ/2)5 > 0 for all γ ∈ [0, 1].
Thus g1 is convex on [0, 1], from which we conclude that
g1(γ) ≤ (1− γ) · g1(0) + γ · g1(1) = 1 + 5
27 γ.
Case 2: γ > 1 Substituting λ = γ − 1/2 into f(λ, γ) and simplifying, we get
f(γ − 1/2, γ) = 2γ 2(4γ2 − 3γ + 1) (2γ − 1/2)3 =: g2(γ).
We have g2(1) = g1(1) = 32/27. Further differentiating g2 gives
g′2(γ) = − 1 (4γ − 1)2 − 6 (4γ − 1)3 − 6 (4γ − 1)4 + 1 < 1 for all γ > 1.
Therefore we have for all γ > 1 that
g2(γ) = g2(1) +
∫ γ
1
g′2(t)dt ≤ g2(1) + γ − 1 = γ + 5
27 .
Combining Case 1 and 2, we get
inf λ>0
f(λ, γ) ≤ g1(γ)
≤ 1 {γ ≤ 1}+ g2(γ)1 {γ > 1} ≤ ( 1 + 5
27 γ
) 1 {γ ≤ 1}+ ( 5
27 + γ
) 1 {γ > 1}
= max { 1 + 5
27 γ,
5
27 + γ
} .
This is the desired upper bound for Ltr-tr.
Equality at γ = 1 We finally show that the above upper bound becomes an equality when γ = 1. At γ = 1, we have
f(λ, 1) = 8λ
(λ+ 2− √ λ2 + 4λ)2(λ2 + 4λ)3/2
= 8λ−4
(1 + 2/λ− √ 1 + 4/λ)2(1 + 4/λ)3/2 .
Make the change of variable t = √
1 + 4/λ so that λ−1 = (t2 − 1)/4, minimizing the above expression is equivalent to minimizing
(t2 − 1)4/32 (t2/2− t+ 1/2)2t3 = (t+ 1)4 8t3
over t > 1. It is straightforward to check (by computing the first and second derivatives) that the above quantity is minimized at t = 3 with value 32/27. In other words, we have shown
inf λ>0
f(λ, 1) = 32
27 = max
{ 1 + 5
27 γ,
5
27 + γ }∣∣∣∣ γ=1 ,
that is, the equality holds at γ = 1.
Part II: Optimal rate for Ltr-val We now prove the result on Ltr-val, that is,
inf λ>0,s∈(0,1) lim d,n→∞,d/n=γ
AsymMSE ( ŵtr-val0,T (ns, n(1− s);λ) )
(i) = lim
d,n→∞,d/n=γ inf λ>0,n1+n2=n AsymMSE
( ŵtr-val0,T (n1, n2;λ) )
︸ ︷︷ ︸ d+n+1 n
(ii) = 1 + γ.
First, equality (ii) follows from Corollary 8 and the fact that (d + n + 1)/n → 1 + γ. Second, the “≥” direction of equality (i) is trivial (since we always have “inf lim ≥ lim inf”). Therefore we get the “≥” direction of the overall equality, and it remains to prove the “≤” direction. For the “≤” direction, we fix any λ > 0, and bound AsymMSE(ŵtr-val0,T (n1, n2;λ)) (and consequently its limit as d, n→∞.) We have from Lemma 5 that
AsymMSE(ŵtr-val0,T (n1, n2;λ))
= d n2 · E [(∑d i=1 λ 2/(σ (n1) i + λ) 2 )2 + (n2 + 1) ∑d i=1 λ 4/(σ (n1) i + λ) 4 ]
( E [∑d
i=1 λ 2/(σ (n1) i + λ)
2 ])2
≤ d n2 · d 2 + (n2 + 1)d( E [∑d
i=1 λ 2/(σ (n1) i + λ)
2 ])2
= d+ n2 + 1 n2 · 1(
E [
1 d ∑d i=1 λ 2/(σ (n1) i + λ)
2 ])2
Observe that
E
[ 1
d
d∑
i=1
λ2
(σ (n1) i + λ) 2
] (i)
≥ E   λ 2
(∑d i=1 σ (n1) i /d+ λ )2

(ii) ≥ λ 2
( E [∑d
i=1 σ (n1) i /d
] + λ )2
(iii) =
λ2
(1 + λ)2 ,
where (i) follows from the convexity of t 7→ λ2/(t + λ)2 on t ≥ 0; (ii) follows from the same convexity and Jensen’s inequality, and (iii) is since E [∑d i=1 σ (n1) i ] = E [ tr( 1n1 X > t Xt) ] =
E [ ‖Xt‖2Fr /n1 ] = d. Applying this in the preceeding bound yields
AsymMSE(ŵtr-val0,T (n1, n2;λ)) ≤ d+ n2 + 1 n2 · (1 + λ)
2
λ2 .
Further plugging in n1 = ns and n2 = n(1− s) for any s ∈ (0, 1) yields
lim d,n→∞,d/n→γ
AsymMSE(ŵtr-val0,T (ns, n(1− s);λ)) ≤ γ + 1− s 1− s · (1 + λ)2 λ2 .
Finally, the right-hand side is minimized at λ→∞ and s = 0, from which we conclude that
inf λ>0,s∈(0,1) lim d,n→∞, d/n→γ
AsymMSE(ŵtr-val0,T (n1, n2;λ)) ≤ 1 + γ,
which is the desired “≤” direction.

heading: C CONNECTIONS TO BAYESIAN ESTIMATOR

text:
Here we discuss the relationship between our train-train meta-learining estimator using ridge regression solvers and a Bayesian estimator under a somewhat natural hierarchical generative model for the realizable setting in Section 4. We show that these two estimators are not equal in general, albeit they have some similarities in their expressions.
We consider the following hierarchical probabilitistic model: w0,? ∼ N (
0, σ2w d Id
) , wt|w0,? iid∼ N ( w0,?, R2
d Id
) , yt = Xtwt + σzt where zt iid∼ N(0, In).
This model is similar to our realizable linear model (6), except that w0 has a prior and that there is observation noise in the data (such that data likelihoods and posteriors are well-defined). We also note that the R2/d variance for wt guarantees that E[‖wt − w0,?‖2] = R2, consistent with our definition (7).
Bayesian estimator We now derive the Bayesian posterior mean estimator of w0,?, which requires us to compute the posterior distribution of w0,? given the data {(Xt,yt)}Tt=14. We begin by computing the likelihood of one task by marginalizing over wt:
p(Xt,yt|w0,?) ∝ ∫ p(wt|w0,?) · p(yt|Xt,wt)dwt
∝ ∫ exp ( −‖wt −w0,?‖ 2
2R2/d
) · exp ( −‖yt −Xtwt‖ 2
2σ2
) dwt
(i)∝ exp ( −‖w0,?‖ 2
2R2/d +
1
2 ( w0,? R2/d + X>t yt σ2 )>( X>t Xt σ2 + Id R2/d )−1( w0,? R2/d + X>t yt σ2
))
∝ exp ( −1
2 w>0,?
(( X>t Xt + dσ2
R2 Id )−1 X>t Xt R2/d ) w0,? + w > 0,? ( X>t Xt + dσ2 R2 Id )−1 X>t yt R2/d ) ,
where (i) is obtained by integrating a multivariate Gaussian density over wt, and “∝” drops all the terms that do not depend on w0,?. Therefore, by the Bayes rule, the overall posterior distribution of w0,? is given by
p ( w0,?|{(Xt,yt)}Tt=1 ) ∝ p(w0,?) · T∏
t=1
p(Xt,yt|w0,?)
∝ exp ( −‖w0,?‖ 2
2σ2w/d
) ·
T∏
t=1
exp ( −1
2 w>0,?
(( X>t Xt + dσ2
R2 Id )−1 X>t Xt R2/d ) w0,? + w > 0,? ( X>t Xt + dσ2 R2 Id )−1 X>t yt R2/d ) .
This means that the posterior distribution of w0,? is Gaussian, with mean , i.e. the Bayesian estimator, equal to5
ŵBayes0,T := E [ w0,? | {(Xt,yt)}Tt=1 ] = (ABayesT ) −1cBayesT ,
where
ABayesT := d
σ2w Id +
T∑
t=1
( X>t Xt + dσ2
R2 Id )−1 X>t Xt R2/d ,
cBayesT :=
T∑
t=1
( X>t Xt + dσ2
R2 Id )−1 X>t yt R2/d .
We note that ŵBayes0,T has a similar form as our train-train estimator, but is not exactly the same. Indeed, recall the closed form of our train-train estimator is (cf. (10))
ŵtr-tr0,T = (A tr-tr T ) −1ctr-trT ,
where
Atr-trT =
T∑
t=1
( X>t Xt + nλId )−2 X>t Xt,
ctr-trT =
T∑
t=1
( X>t Xt + nλId )−2 X>t yt.
As ŵBayes0,T uses the inverse and ŵ tr-tr 0,T 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 σw = ∞ so that the prior of w0,? becomes degenerate (and the Bayesian estimator reduces to the MLE).
4Hereafter we treat Xt as fixed, as the density of Xt won’t affect the Bayesian calculation. 5Any density p(w) ∝ exp(−w>Aw/2 + w>c) specifies a Gaussian distreibution N(µ,Σ), where A =
Σ−1 and c = Σ−1µ, so that µ = A−1c.

heading: D DETAILS ON THE FEW-SHOT IMAGE CLASSIFICATION EXPERIMENT

text:
Here we provide additional details of the few-shot image classification experiment in Section 5.2.
Optimization and architecture For both methods, we run a few gradient steps on the inner argmin problem to obtain (an approximation of) wt, and plug wt into the ∇w0`{tr-val,tr-tr}t (w0) (which involves wt through implicit function differentiation) for optimizing w0 in the outer loop.
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) as the backbone (i.e. the architecture for wt). We further tune their hyper-parameters, such as the regularization constant λ, the learning rate (initial learning rate and its decay strategy), and the gradient clipping threshold.
Datasets We experiment on miniImageNet (Ravi & Larochelle, 2017) and tieredImageNet (Ren et al., 2018). MiniImageNet consists of 100 classes of images from ImageNet (Krizhevsky et al., 2012) and each class has 600 images of resolution 84 × 84 × 3. We use 64 classes for training, 16 classes for validation, and the remaining 20 classes for testing (Ravi & Larochelle, 2017). TieredImageNet consists of 608 classes from the ILSVRC-12 data set (Russakovsky et al., 2015) and each image is also of resolution 84 × 84 × 3. TieredImageNet 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, providing a more realistic few-shot learning scenario.

heading: D.1 EFFECT OF THE SPLIT RATIO FOR THE TRAIN-VAL METHOD

text:
We further tune the split (n1, n2) in the train-val method and report the results in Table 2. As can be seen, as the number of test samples n2 increases, the percent classification accuracy on both the miniImageNet and tieredImageNet datasets becomes higher. This testifies our theoretical affirmation in Corollary 8. However, note that even if we take the best split (n1, n2) = (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-train performing better than train-val (in Section 4) rely on the assumptions that the data can be exactly realized by the representation and contains no label noise. Our experimental results here may suggest that the miniImageNet and tieredImageNet few-shot tasks may have a similar structure (there exists a NN representation that almost perfectly realizes the label with no noise) that allows the train-train method to perform better than the trainval method.

heading: E COMPARISON WITH CROSS-VALIDATION ON SYNTHETIC DATA

text:
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 following two settings: (n1, n2) = (5, 15), and (n1, n2) = (15, 5). In both cases, we 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 one as validation. The estimated optimal ŵcv0 is obtained by minimize the averaged
train-val loss over the 4 partitions:
`cvt (w0) := 1
4
4∑
j=1
1
2nval
∥∥∥yval,jt −Xval,jt Aλ(w0; Xtrain,jt ,ytrain,jt ) ∥∥∥ 2 ,
ŵcv0 = arg min w0
1
T
T∑
t=1
`cvt (w0),
where superscript j denotes the index of the cross-validation. The performance is depicted in Figure 2.
Result As showin in Figure 2, for both (n1, n2) = (15, 5) and (n1, n2) = (5, 15), using cross-validation consistently beats the performance of the train-val method. This demonstrates the variance-reduction effect of cross-validation. Note that the best performance (among the crossvalidation methods) is still achieved at n1 = 5, similar as for the vanilla train-val method. However, numerically, the best cross-validation performance is still not as good as the train-train method.
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-validation, i.e., (n1, n2) = (39, 1) and (n1, n2) = (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 (n1, n2) = (1, 199). We adopt a matrix inverse trick to mitigate the computational overhead of finding Aλ(w0; Xtrain,jt ,ytrain,jt ). 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 n = 40 experiments, this is the first time of seeing leave-one-out method outperforms the traintrain 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 n tends to have a strong variance reduction effect in the leave-one-out method, so that the performance can be improved. Yet using the leave-one-out method with a large n invokes a high computational burden.
F NONASYMPTOTIC ANALYSIS UNDER GENERAL SCALINGS OF d, n, T
We sketch an nonasymptotic analysis of the train-train method in the realizable linear model in Section 4. We assume in addition that wt iid∼ N(w0,?, R 2 d Id) 6.
We begin by recalling from Appendix B.1 and B.2 that the train-train and train-val estimators have closed-form expressions
ŵtr-tr0,T =
( T∑
t=1
At
)−1 T∑
t=1
Atwt, (44)
ŵtr-val0,T =
( T∑
t=1
Bt
)−1 T∑
t=1
Btwt, (45)
where
At := λ 2 ( X>t Xt n + λId )−2 X>t Xt n ,
Bt := λ 2
( Xtrain>t X train t
n1 + λId
)−1 Xval>t X val t
n2
( Xtrain>t X train t
n1 + λId
)−1 .
Nonasymptotic result for ŵtr-tr0,T For simplicity, we restrict attention on the analysis of the traintrain estimator ŵtr-tr0,T , whose closed form expression is given in (44). Analysis of the train-val estimator can be done in a similar fashion.
We sketch a proof for the following
Result: Let T = Ω(d) and (d, n) is such that
ftr-tr(d, n) = E [ 1 d ∑d i=1(σ (n) i ) 2/(σ (n) i + λ) 4 ]
( 1 dE [∑d i=1 σ (n) i /(σ (n) i + λ) 2 ])2 = Θ(1)
6This Gaussian assumption on wt is mainly for technical convenience, and can be relaxed to that wt,i − w0,?,i are i.i.d. with variance R2/d and sub-Gaussian with parameter O(R2/d) without changing the proof.
(which for example holds if (d, n) are in the proportional limit), then with high probability we have
MSE(ŵtr-tr0,T ) = R2
d
( 1±O ( 1√ d )) · [ 1 T · ( d · ftr-tr(d, n)±O ( d √ log(T/δ) T ))]
≈ R 2
T · ftr-tr(d, n) =
1 T AsymMSE(ŵtr-tr0,T ),
that is, the MSE for the train-train method concentrates around the asymptotic MSE.
Proof Sketch We first define the matrix
ΣT :=
( T∑
t=1
At
)−2 T∑
t=1
A2t = 1 T · (∑T t=1 At T )−2∑T t=1 A 2 t T ,
which will be key to our analysis. Observe that conditioned on At (and only looking at the randomness of wt), we have
ŵtr-tr0,T −w0,? = ( T∑
t=1
At
)−1 T∑
t=1
At(wt −w0,?) ∼ N ( 0, R2
d ΣT
) .
Therefore, applying the Hanson-Wright inequality (Vershynin, 2018, Theorem 6.2.1) yields that
MSE(ŵtr-tr0,T ) = ∥∥wtr-tr0,T −w0,? ∥∥2 ∈ R 2
d
( tr(ΣT )±max { ‖ΣT ‖Fr √ log 1
δ , ‖ΣT ‖op log
1
δ
})
with probability at least 1 − δ. In the following, we argue that tr(ΣT ) 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(ΣT ).
Concentration of tr(ΣT ) Recall that At are i.i.d. PSD matrices in Rd×d. We have
tr(ΣT ) = 1
T 〈(∑T t=1 At T )−2 , ∑T t=1 A 2 t T 〉
= 1
T
{ 〈 E[A1]−2,E[A21]
〉 ︸ ︷︷ ︸
I
+ 〈(∑T t=1 At T )−2 − E[A1]−2,E[A21] 〉
︸ ︷︷ ︸ II
+ 〈(∑T t=1 At T )−2 , ∑T t=1 A 2 t T − E[A21] 〉
︸ ︷︷ ︸ III
} .
We argue that I is the main term that depends on (d, n) and is independent of T . Further, A1 has eigenvalues λ2σi/(λ+ σi)2 where {σi}di=1 are the eigenvalues of X>1 X1/n, and A1 has uniformly distributed eigenvectors. Following the same analysis of Lemma 5, we see that
I = d2 · ρtr-tr = d · E [ 1 d ∑d i=1(σ (n) i ) 2/(σ (n) i + λ) 4 ]
( 1 dE [∑d i=1 σ (n) i /(σ (n) i + λ) 2 ])2 ︸ ︷︷ ︸ :=ftr-tr(d,n) .
This is exactly the same quantity that appeared in the asymptotic MSE for the train-train method in Theorem 4. In the following we assume that d, n is such that ftr-tr(d, n) = Θ(1).
We further argue that terms II and III are low-order terms compared with term I. Indeed, term I is O(d). Applying matrix concentrations (e.g. the matrix Bernstein inequality), we can get that terms II and III are of order max{ √ d log(T/δ)/T , d log(T/δ)/T} with probability at least 1 − δ. Combining the terms yields that
tr(ΣT ) ∈ 1
T
{ d · ftr-tr(d, n)± d √ log(T/δ)
T
}
with high probability.
Controlling the error in the MSE We now control ‖ΣT ‖Fr and (consequently) ‖ΣT ‖op. We wish to show that
‖ΣT ‖Fr ≤ O (
1√ d
) · tr(ΣT )
with high probability. This can be seen from the combination of two results: (1) tr(ΣT ) = Ω(d/T ) by the preceding part, and (2)
‖ΣT ‖Fr ≤ 1 T · 1 λmin( ∑ t≤T At) 2 ∥∥∥∥∥ T∑
t=1
A2t/T ∥∥∥∥∥ Fr ≤ O( √ d/T ).
The above requires (1) ‖At‖Fr ≤ O( √ d), which is true since we have 0 . At . λId and thus∥∥A2t ∥∥ Fr ≤ λ2 √ d, and (2) λmin( ∑ t≤T At/T ) = Ω(1) with high probability, which is true whenever T = Ω(d) because of matrix concentration and the fact that λmin(E[A1]) = Ω(1).
Putting together We have with high probability that
MSE(ŵtr-tr0,T ) = R2
d
( 1±O ( 1√ d )) · [ 1 T · ( d · ftr-tr(d, n)±O ( d √ log(T/δ) T ))] .
as long as T = Ω(d) and d, n is such that ftr-tr(d, n) = Θ(1).

heading: F.1 SYNTHETIC EXPERIMENT

text: We verify our theoretical findings under general scalings of d, n, T . We adopt the data generating model in Section 5.1 again. To compare the performance of the train-train and train-val methods, we choose the number of tasks T = 300 and per-task sample size n = 100. We vary d from 0 to 300. Note that now T is 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 `2 errors.