Understanding Train-Validation Split in Meta-Learning with Neural Networks
Authors: Xinzhe Zuo
Zixiang Chen
Huaxiu Yao
Yuan Cao
Quanquan Gu
Venue: ICLR 2023 poster (2023)
Keywords: meta-learning
neural networks
deep learning
train-validation split
convolutional neural network

Abstract: The goal of meta-learning is to learn a good prior model from a collection of tasks such that the learned prior is able to adapt quickly to new tasks without accessing many data from the new tasks. A common practice in meta-learning is to perform a train-validation split on each task, where the training set is used for adapting the model parameter to that specific task and the validation set is used for learning a prior model that is shared across all tasks. Despite its success and popularity in multitask learning and few-shot learning, the understanding of the train-validation split is still limited, especially when the neural network models are used. In this paper, we study the benefit of train-validation split for classification problems with neural network models trained by gradient descent. We prove that the train-validation split is necessary to learn a good prior model when the noise in the training sample is large, while the train-train method fails. We validate our theory by conducting experiment on both synthetic and real datasets. To the best of our knowledge, this is the first work towards the theoretical understanding of train-validation split in meta-learning with neural networks.

Published as a conference paper at ICLR 2023
UNDERSTANDING TRAIN- VALIDAAAIIA SPLIT IN WITH NEURAL NETWORKS
Xinzhe Zuo', Zixiang Chen', Huaxiu Yao Yuan Cao", Quqnquan Gu f Department of Mathematics, University of California, Los Angles
xxz @matm.thh..mmmmmmmmm ucla.edu
Department of Computer Science, University of California, Los Angles cchenzx9,, Egu)ecs.o www..elleeeeoo
Department of Computer Science, Stanford University
huaxiu@cs. stanford. edu
Department of Statisties & Actuarial Science, University of Hong Kong yuancac@hku. hk
ABSTRACT
The goal of meta-learning is to learn a good prior model from a collection of tasks such that the learned prior able to adapt quickly to new tasks without accessing many data from the tasks. A common practice meta-learning is to perform a train-validation split on each task, where the training set is used for adapting the model parameter to that specific task and the validation set is used for learning prior model that is shared across all tasks. Despite its success and popularity multitask learning and few-shot learning, the understanding of the train-validation split is still limited, especially when the neural network models are used. In this paper, we study the benefit of train-validation split for classification problems with neural network models trained by gradient descent. For first-order -agest-ggostic meta-learning (FOMAML), we prove that the train-validation split is necessary learn good prior model when the noise in the training sample is large, while the train-train method fails. We validate our theory by conducting experiment both synthetic and real datasets. To the best of our knowledge, this is the first work towards the theoretical understanding train-validation split in meta- learning with neural networks.
INTRODUCTION
In recent years, meta-learning has gained increasing popularity and been successfully applied to wide range of problems including few-shot learning (Ren et al. 2018 Li et al. 2017 Rusu et al.) 2018 Snell et al. 2017). reinforcement learning (Gupta al. 2018b neural machine translation (Gu et al. 2018), and neural architecture search (NAS) (Lu et al, 2018 Real et al. 2019). A popular meta-learning idea is formulate it bi-level optimization problem, where the inner level computes the parameter adaptation to each task, while the outer level tries to minimize the meta-training loss. Such bi-level optimization formulation is empirically proved effective to learn new tasks quickly using only a few examples with the aid of past experience. Following this idea, meta-learning algorithms such as model agnostic meta-learning (MAML) (Finn et al., 2017) have achieved remarkable success in many applications.
Due to the nature bi-level optimization, meta-learning algorithms can often take advantage of train- rrin-validation split in the dataset, so that the inner and outer levels of the algorithm use different data points (Finn et al., 2017 Rajeswaran et al. 2019 Bai et al. 202T Fallah et al., 2020). It is believed that the formance. There has been several attempts to understand the importance of train-validation split in meta-learning for linear models (Wang et al.) 2021 Bai al. 2021 Saunshi et al. 2021). Specifi- cally, Wang et al. (2021) showed that when learning linear models, the train-train method performs much worse than the train-vall validation method if the sample size is small and the noise is large. They
split can help the meta-learning algorithm to achieve better per-
also show that the train train method is able to perform well on linear models when the sample
size is large enough. Bai et al. (202T) considered the linear centroid model introduced in Denevi

---

Published as a conference paper at ICLR 2023
et al. (2018b) and showed that the train-validation method outperforms the train-train method in an agnostic setting, while in the realizable noiseless setting, the train-train method can asymptotically than the rrai-validation method as the sample size and achieve strictly smaller mean square
dimension go to infinity at a fixed ratio. (Sansshi et al. (202T) considered a representation learning perspective, and demonstrated that train-validation split encourages the learned representation to be low-rank while the train-train method encourages high-rank representations. However, all these works focus on the linear regression setting, while the advantage of train-validation split remains elusive for meta-learning with neural networks.
Based on the above observation, we raise the following question:
How does Irain-validation split affect the meta learning with neural networks?
In this paper, answer the above question via case study of few-shot binary classification using a two-layer convolutional neural network. We consider a learning problem where the data model consists of large noises, and only limited number of data are available. Under this setting, we theoretically compare the performance of first-order MAML (FOMAML (Finn et al. (017)), which simplification of MAML that ignores the hessian terms, with train-validation split (the train- validation method) and without a train-validation split (the train-train method). We summarize our contributions as follows:
1. We show that under our setting, despite the complex bi-level structure of the FOMAMI loss and its non-convex landscape. is guaranteed that the rrain-valddttion method and the train- train method can both train a two-layer CNN to global minimum of the training loss with high probability.
2. We also demonstrate that there is a significant performance gap show that the neural network trained by the train-validation method can achieve test loss that decreases exponentially fast the number of training tasks increase. On the other hand, also show that the train-train method can at best achieve a constant level test loss.
test data. Specifically,
Our study demonstrates the importance of train- validatiin split in learning neural networks. To the best of our knowledge, this is the first theoretical work studying train-validation split of meta- learning with neural networks. Notably, the learning problem we consider is linearly realizable, for which Bai al.] (202T) showed that the train-train method asymptotically achieve better MSE than the train-validan validvaliootion method under a linear model. However, our results give the oppo- site conclusion for learning CNNs the train-validation method still outperforms the train-train method even for linearly realizable learning problems. Therefore, our results indicate that train- validation split may have a more significant advantage when learning complicated prediction models.
4. We perform experiments on both synthetic and real datasets with neural networks as backbone model to justify our theoretical results. In particular, even when the data and the neural network structure do not meet our theoretical assumptions, the experiment results still corroborate our theory certain extent. This demonstrates the practical value of our analysis.
k). Given two sequences {. and {yn} with Un 0, denote J. O(y,)) if [a... l yn is upper bounded by constant for all Similarly, we denote In = M(y,)) if / l/2 n is lower bounded by a positive constant. We denote x., = ((y)) if Fr, Olyn) and In (yy.). Finally, we use Ö(-), 5).), and Ô(-) to hide logarithmic factors.
Notation. For an integer k; we denote jk] =
2 ADDITIONAL RELATED WORK
Otimiization and generalization guarantees for meta-learning. number of recent works stud- ied the optimization guarantees for meta-learning algorithms. Finn & Levine (017)) proved the universality of gradient based meta-learning Wang et al. (2020) studied the global optimality con- ditions for MAML with nonconvex objective. Fallah et al. (2020) studied the convergence guar- antee for MAML with nonconvex loss function and proposed Hessian-Free MAML with the same theoretical guarantee of MAML without accessing second order information. Finn et al. (2019); Balcan et al. 2019); Khodak et al. (019)); Denevi et al. (2019 2018a) studied online meta- leetnng using online convex optimization. Another series of works have also studied the generalization error and sample complexities meta-learning methods. Specifically, Amit & Meir (2018) extended the PAC-Bayes argument the meta-learning setting and established generalization error bound for
2

---

Published as a conference paper at ICLR 2023
meta-learning. Saunshi et al. (2020) analyzed the sample complexity under the nonconvex setting using Reptile (Nichol et al. 2018). There has also been a stream of work studying generalization in meta-learning from the representation learning perspective (Du et al. 2020 Tripuraneni et al. 2020 Denevi et al. 2018ap. These works do not employ a train-validation split, instead they as- sume some underlying low-rank constraints the representation. Chen et al. (2022); [Huang et al.]
(2022); Wang et al. (2022) also studied generalization error bounds for meta-lcarning in the over- parametrized regime.
Feature learning in over parreaearaeeezeed neural networks. There is a series of recent work study- ing the feature learning dynamics of neural networks. For example, Allen-Zhuu & Li (2020a) studied a sparse coding model and showed that adversarial training can help CNN filters to learn "pure" dictionary bases. FAllen-Zhu & Li (2020b) studied the impact of ensemble and knowledge distilla- tion on the feature learning process. Zou ct al. (202I) demonstrated the generalization gap between Adam and stochastic gradient descent through the lens of feature learning. (Ca et al. (2022) studied feature learning and noise memorization in learning two-layer CNNs and showed phase transition between benign and harmful overfitting.
PROBLEM SETUP
In this section, we introduce our data model, neural network model, loss function, and the details about the FOMAML algorithm with train-train and validataiittion methods.
We first introduce our data model. In meta-learning, the goal is to train a model based on the data from K tasks, so that the trained model can learn new task efficiently. Theoretical analysis of meta-lcarning thus requires careful modeling of (i) the relation among different tasks, and (ii) the data distribution for each specific task. To achieve this, we suppose that the data distribution D3 for the k-th task is defined based on a vector Vk. i.e., Dj = D(v=), and that the vectors Vi..... VK are independently drawn from a distribution II. Following this framework, the data points of new task can be generated by first sampling vector E from II, then sampling data from the distribution D(D). In the following, we present the detailed definitions of II and (DD).
Definition 3.1 (Distribution of tasks). Let VI, ZM E Rd be fixed vectors, where Zi..... Za are orthogonal to v. A vector D is generated from II by (i) randomly pick vector z from (zi...., Zar J. and (ii) let D V +
Definition 3.1 based on a set of fixed vectors 1/ V.Zi..... ZM E Rd. Here w' captures the feature shared by all tasks. And ,I....,Zau ZuM give a dictionary of possible unique features of cach specific task. is important to note that we focus on the setting where the number of observed tasks K < M. Under our setting, with high probability, different tasks will use different unique features.
Definition 3.2 (Distribution of data). Given a vector i E Rdd each data point (x, y) with x =
(x(1), x(2 (T E Rdd and E { 1, 1} is generated from D(ū) as follows:
1. The label y is assigned as +1 -1 with equal probability.
2. A noise vector is generated from (0,, oद P)), where P Rdxd is the projection operator onto span((v, (1., Zi...., ZI....,Zar)) )).
One of (1), x22) randomly selected and assigned as y Pas the other is assigned as E.
For k E [K]. we denote by Sy {(X.. yk. J the set of independent samples from the k- th observed task. We consider a specific type of data input that consists of two patches, Xx.
(I) (2)TTT 1x 3,5 JT, to meet our study of convolutional neural networks. Note also that Definition 3.2 requires the noises in the data input to be sampled from the Gaussian distribution NO oz (I to ensure that the noise vector g orthogonal to the features v, v,Z1. 21.1..... ..M It is then easy to check that our data model is linearly realizable: the linear predictor 0- = ||>|| [v v " E 2d2d satisfy (0',x) = y for all (x, y) drawn from our data distribution. Our motivation to study this linearly realizable setting is that it has been proved in Bai et al. (2021) 1) that the train-train method is strictly better than the trainvaalddttonn method when learning linear models in the realizable setting. On the contrary, in this paper aim to show that for the linearly realizable data model defined in Definitions 3.1 and 3.2 the validation method can still outperform the train-trait train method for FOMAMI. in learning two-layer CNNs.
3

---

Published as a conference paper at ICLR 2023
We study two-layer CNN with hidden layer neurons whose second layer weights are frozen as =1's. We use the Huberized- R (Chatterji et al. 2021) activation function, which defined as
0 (2) = 2 /2hh,
< 0
2E h0
h/2, otherwise.
where set h 1/2 in analysis. Let W represent the collection of all weights of net- work. For data input [x(1) TT. consider the CNN f(W.x) (+1(W+1. F-I 11 x), where
F2(W,,X Σ 0 ((, jE
We use Wjr to denote the r-th convolution filter with second layer weight j. and use W, to denote the collection of Wa.l...., Wj.m- We consider cross-entropy loss. The loss of data point (x, y) is given by L C(W, x, 3) = fly f(W,x), x)], where {(z) = log(1 + exp(-z)). The loss of collection of data points S is defined by
C(W S) = S
Σ
C(W,x, x. y).
(X.))ES
Following the data model given in Definitions
3.1
and 3.2
define the test loss achieved by
CNN with weights W as Lrest ( (W) == (x.)) yy (W,x), We implement the FOMAMI.
algorithm (Finn al. 2017) to train the neural network. The train-train and train-validation methods are given as follows.
Train-train: for each task updates. Specifically, the meta objective is to minimize
all of the samples for adapting the parameter in the inner-loop
K
2 ( (S
E k=1
K
where W(W, Sx)) represents the weights of the network after gradient descent steps (w.rtt. loss C(, Sy)) starting from W with step size 7y The FOMAML algorithm updates the CNN weights using the following gradient update rule with step size ry:
w(++)) w(t) 7
1 K
(3.1)
Train-validation: for each task k we denote by Ih fl..... n1 the training data indices, and I (ni + .1) the validation data indices. We then use S {(x,, 3k.a) as the training data set, and St {(xx,5 (ess)) JEzz as the validation data set. The meta objective of the tran-validation method is to minimize
n
1 K K
Eu (W, {Sx)
Σ (W)
where W(W, (W) represents the weights of the network after J gradient descent steps (w.rtt loss C(. 8 starting from W with step size y. For the trainvalidattin method, the FOMAML algorithm implements the following outer-loop update rule to train the network:
K
w(++1) w(())
VwC(W,
) /w=
(3.2)
K
4 MAIN RESULTS
In this section, we present our theoretical results for the train- train and train- validation methods. We first introduce the following condition.
4

---

Published as a conference paper at ICLR 2023
Condition 4.1. There exists o, such that (1/2) a.vds |z.1l2 S (3/2) a.vd for [M], and (z; zy) - O(o3 (og(()) for all i j-
Condition 4.1 specifies the properties of the task task-specific features in Definition 3.1
Here require that the task-specific features to have weak correlations to each other, which is standard in dictionary learning. Moreover, it is easy to that such Z1...... ...,. ZM exist long M (poly(dd): with a simple Gaussian concentration argument, one can show that M independent zero-mean Gaussian random vectors with covariance matrix of vv / [|) are orthogonal and satisfy Condi- tion 4.1 with high probability.
With Condition and our data model in Definitions and it is necessary for neural network to learn the shared feature y to make accurate predictions on new task. On the other hand, if neural network only utilizes the task-specific features or the noises in the observed data fit the labels, then it can only achieve a good training loss, but will have a poor prediction accuracy on new tasks. Following this intuition, we aim construct concrete setting under which the train-train and rain-validation methods give different test losses while both achieving small training losses. The details of our constructed setting summarized in the following condition.
Condition 4.2. || = 1. 0g = d polylog(d), = d 1/2 //2//olylog(d)) n 0 K = polylog(d), polylog(d), ((d2/2) - M S d/2.
Condition 4.2 defines an over- parameterized setting where d >> Kn. Moreover, under Condi- tion 4.2 norms of the shared and task-specific features ||/|22 ||2||lz...... | llz are all (())
In comparison, with high probability, the norms of noise vectors in the data are ((polylog(d).. Therefore, Condition 4.2 defines a setting with relatively large noises.
The FOMAML algorithm involves inner and outer-loop training of the neural network. We specify our detailed hyper- prper-parameter configurations in the following condition.
Condition 4.3. In the FOMAML algorithm defined in Eq. (3.T) and Eq. (3.2). we initialize the CNN weights (0)) by Gaussian random initialization with standard deviation og = d-11/2 We set the inner-loop step size polylog(d), and the outer-loop step size n 1/polylog(d). We
run T = (oly(d) outer-loop iterations. Within each outer-loop iteration, we run gradient descent steps.
inner-loop
In Condition 4.3 we slightly larger step size for inner-loop compared to that for the outer-loop. This is to ensure that the inner-loop updates can make a difference, and it matches the meta-learning practice. Moreover, inner-loop iterations. The exact value of is not essential - we can easily apply our analysis to other values of J (1).
set J = 5 to demonstrate that analysis applies to the
with multiple
We are now in the position to state our main theoretical results. The theorem below gives the training and test loss guarantees for the train-traie method.
Theorem 4.4. Under Conditions 4.7 4.2 and 4.3 suppose that the train-train method to train the neural network. Then with probability at least 1 - (Kn)-10,
1. the training loss is small:
min (x-tt(((t)) (( s o (E[T]
poly(d)
2. the test loss is large:
min Crest (W(0) Q(1)) (E[2]
Theorem 4.4 demonstrates that FOMAML with train-train method can successfully train the CNN to minimize the training loss. However, it also shows that the train-train method fails on new tasks and can only achieve constant level test loss. In comparison, we have the following theorem for the vrain-valiatiinn method.
Theorem 4.5. Under Conditions 4.1 4.2 and suppose that one uses the train-validation method train the neural network. Then with probability least (Kn) -10
5

---

Published as a conference paper at ICLR 2023
1. the training loss is small:
min h val (W(()) (5t) & (polyca) (E
2. the test loss is also small: there exists constant 0 such that
Liett (W(T) = (x(xx((Xx)))
Although both methods can achieve a 1/poly(d) (d) training loss, the train-validation method is able to achieve test loss of O(exp) )) compared to constant test loss (2(1) by the train-train method. Thus, Theorems|4.4 (.. 4.3 show that for our data model, it is necessary to perform a train- vain-valiaation split to achieve good performance test data.
We also compare FOMAML with the vanilla supervised learning framework where one simply combines all data from the K tasks together and uses gradient descent to minimize the overall cross- entropy loss. In fact, the results of Theorem 4.4 still hold even for J = O, where algorithm Eq. (3.1) reduces gradient descent for vanilla supervised learning. Therefore, vanilla supervised learning can also only achieve (1) test loss. Clearly, our results imply that FOMAML with train-validation split can significantly outperform vanilla supervised learning when learning our data model.
Comparison with Bai et al. (021). Recently, Bai et al. (202T) studied the importance of the train- validation split in meta-learning under the linear centroid framework. Specifically, they considered linear ridge regression in the inner-loop and linear ridgeless regression in the outer-loop, and showed that the train-train method strictly outperforms the train-validation method in the realizable setting. As we have discussed in Section our data model is linearly realizable, and thus by Bai et al. (2021), the train-train method should outperform the validation method when learning our data model with linear ridge/ridgeless regression. On the contrary, Theorems 4.4 and 4.5 demonstrate that the wrin-validation method still significantly outperforms the train-train method for FOMAMI. in learning CNNs. We believe the key reason behind this difference is that the CNN model has much higher expressive power, and therefore can more casily overfit noises in the training data points when using FOMAML. The train-validation split thus greatly helps feature learning of the neural network by performing a sample splitting between the inner and outer-loops. Therefore, our results indicate that prediction models.
split may have more significant advantage when learning complicated
EXPERIMENT
5.1 EXPERIMENTAL SETUPS
Synthetic data. We generate synthetic data test our theory. For our data generation we choose: d = 1000, K = 343, n = 10, = 10.42, = 0.00066, ||/|| = 1. For our neural network we choose: m 18, du 0.032. And finally we choose the following parameters for inner and outer 0.001, J = 5, 17 0.0001.
level optimization:
Real-world Data. In our experiments, we further justify our theoretical findings in two real-world datasets: RainbowMNIST, minilmagenet, which are discussed as follows.
RainbowMNIST. Following (Yao al., 2021). RainbowMNIST is 10-way meta-learning dataset built upon original MNIST dataset, where each task is constructed by applying one com- bination of image transformations (c.g., coloring, rotation) on the original data. Here, 40 and 16 combinations are used for meta-training and meta-testing, respectively.
magele... Following the traditional meta-learning setting (Finn & Levine 2017 Snell et al.)
2017). minilmagenet dataset is split into meta- ttainiig, meta- veta-validation and meta-testing classes, where 64/16/20 classes are used for meta-trant wea-triiinn/valiatttiiii way, K-shot setting to split the training and validation set in our experiment, where N=5 and K=1 in this paper (i.e., 5-way, 1-shot learning).
We adopt the traditional N-
Backbones and Hyperparameters. For all real-world datasets, follow (Finn & Levine 2017 Snell et al.] 2017), we adopt the standard four-block convolutional layers the base learner, where Huberized-Rer ReLU is used as the activation function. The number inner-loop steps is set as 5. The lnner-loop and outer-loop learning rates are set 0.01 and 0.001 (minilmagenet), 0.1 and 0.01

---

Published as a conference paper at ICLR 2023
(Rainbow:MNIST), respectively. We report the average aceuracy with 95% confidence interval over all meta-testing tasks. For synthetic data, we follow our theoretical analysis and report the cross- entropy loss with 95% confidence interval over all meta-testing tasks. The inner-loop and out-loop learning rates are 0.01, 0.001, respectively.
5.2 RESULTS
Comparison between Different Activation Functions. We first conduct experiments to compare the performance between Huberized-ReLU activation function used in our theoretical analysis and the traditional ReLU function. The results are reported in Table [ indicating that Huberized-Reee ReLL performs similarly to ReLU, Thus it is reasonable replacement to simplify our analysis.
Table I: Performance comparison between different activation functions.
Synthetic
RaiSTowMNIST
minilmagenet
Setting
Activation
Loss
A
Ace t
ReLU
8.22 + 0.42
68.70 + 0.51%
27.19 + 1.23% 25.93 1 1.10%
Train- Train
Huberized-ReLL
8.50 1 0.43
65.32 1 0.54%
ReLU
4.62 + 0.24
87.68 + 0.21%
46.73 + 1.32%
Train-Validatee Validation
Huberized-Rel..
4.66 + 0.23
87.52 0.20%
46.15 + 1.36%
Performance w.r.f the Number of Inner-Loop Steps. We further compare the performance be- tween the train-train and rrainvaaiiattion methods for different inner-loop optimization steps. The results are reported in Table 2 According to the results, we observe that the train-validation split performs much better than the train-train method with more inner-loop steps. This is what ex- pected since less number of inner-loop steps corresponds to less overfitting to the training set during the inner-loop optimization. In the case of using less inner-loop steps, using the training set in the outer-loop optimization can still contribute to the optimization.
Table 2: Performance comparison of the number of optimization steps in the inner-loop.
Synthetic
RainbowMNIST
minilmagenet
Setting
# of Inner Steps
Loss 4
Acc 1
Acc
Train-Tras
7.22 + 0.37
79.76 + 0.41%
25.09 + 1.11% 25.17 + 1.04%
1 step
Train- Validation
4.81 0.24
85.83 0.25%
Train-Train Train
8.50 0.43
65.32 + 0.54%
25.93 + 1.10%
5 steps
Valii-Valiitioon
4.66 0.23
87.52 0.20%
46.15 + 1.36%
Performance w.r.t the Inner-Loop Learning Rate and the Outer-Loop Learning Rate. Finally, analyze the influence of inner-loop and outer-loop learning rates. The results in Tshle that train-validation split performs better when the inner-loop learning rate is smaller than the outer-loop learning rate, which corroborates our theoretical results. On synthetic data, the train-train method performs better when the outer-loop learning rate larger than the inner-loop learning rate. This is not surprising since smaller inner-loop learning rate corresponds less overfitting, similar to the phenomenon when using less inner-loop optimization steps (Table
Table 3: Performance w.r.t. the inner-loop learning rate and the outer-loop learning rate.
Synthetic
RNiSS
minilmagenet
Setting
Learning Rate
Loss 4
Acc t
Acc
Train-Trai
5.76 1 0.39
64.82 + 0.48%
20.00 0.00% 20.00 + 0.00%
outer-Ir > inner-Ir
Train- Validation
5.21 + 0.31
66.13 = 0.31 %
Train-Train
8.50 1 0.43
65.32 + 0.54%
20.00 0.10%
outer-Ir inner-Ir
Train- Validation
4.66 1 0.23
87.52 + 0.20%
46.15 1 1.36%
OVERVIEW OF PROOF TECHNIQUES
From here onward, will use upper script (t, r) wjrr denote the f-th outer-loop iteration and the 7-th inner-loop iteration. However, according to Eq. (3.I) and Eq. (3.2), the inner-loop updates
7

---

Published as a conference paper at ICLR 2023
for CNN filter Wjr is task-specific. Therefore we cannot rigorously use the notation (t.r) referring to specific task k. Luckily, all our analyses are based on the study of inner products of the form (Wj,r, xx,))
j.r without
j.r X E as the inner product after outer-loop updates followed by r inner-loop updates, where the inner-loop updates only use samples from task k. With these notations, we give the following two key lemmas that highlight the main differences between the train-train and train-validation methods.
can use the notation (w(f?))
(p),
Lemma 6.1. Suppose one the train-train method to train the neural network. Let T be the first iteration such that max,e[m) (w (w
(t.0) Ek,i) 2 ((1/polylog(d)) for k [K], [n], and j = yk,.. Then, under the same condition as in Theorem 4.4 for any T
for any k' E [K], r E [m]), and j' E (-1,1] we have
I' f' jrr ( .w)) & 10w uK 10()W'
(w
2. for arg max, (w (w (t.0)
J.r Ex,i),
(w j.r
(t,J) Ek,)) 2 (w (t.0)
Lemma 6.2. Suppose one uses the truin-validation method to train the neural network. Let TT2) be the first iteration such that max+e|m] j j(w (t.D)
//) 2 (((//ollyoog(d))oomm E {-1,1}. Then, under 3.r
the same condition as in Theorem 4.5 for any 1 S TT
for any E [K] and r = arg max, j(w
(t.0) (1.0) j,r v)
j j( (1,3) vx) = (11))(w (t.0)
jr uk O(1)""
2. for any E [m]. & E [K]. i E Iyall and j' E [1-1,1}
(t fr Ex.i) S o( max { { ( Ex.a), JŌ(a
The above two lemmas give some intuitions for the better generalization power of the vaaid-valiattion method. According to Lemma the J inner-loop gradient steps amplify the noise inner products more than the feature inner product for the train-train method. On the contrary, by Lemma 66.2 the J inner-loop gradient steps amplify the feature inner product and do not have big impact on the noise inner products for the raan-validation method.
In the rest of this section, we mainly sketch the proof of Theorem for Based on Lemma 6.2] we can see that the inner-loop updates in the train-validation method priori- tizes feature learning over noise memorization. Our further study of the outer-loop training proce- dure gives the following lemma.
for the vaiin-alidattinn method.
Lemma 6.3. Under the same condition as in Theorem 4.5 let T(2) = max, T/?, where r/ is
defined in Lemma 6.2 Then max,e[m) (w (T(3),0) .0) j E 1-1,1)
(k.x) = O(d 1/2) for any [K], E Ty and
We remind our readers that (2)) (defined in Lemma 6.2 represents the time taken for the feature inner product to grow to Q(1 (1//polloo(dd)) Therefore Lemma 6.3 is essentially still comparison between the growth rate feature and noise inner products: it shows that when the feature inner product grows to @(1), the noise inner products still remain at their initialization order which is (dd11/2) The next lemma provides key result for the convergence of the training loss.
Lemma 6.4. Let T = poly(d) be the total number of iterations. Under the same condition as in
Theorem 4.5 we have
((tt) k,
< δ
1 Tn
min
(K.
where (t,J) e' (yA, ' S(W(W(). S. (
8

---

Published as a conference paper at ICLR 2023
By definition, the feature inner product has grown to (11/polylog(d) time T(2), After T(2), implement a more careful study of the training process, as some data points may have been well- fitted (with small loss) and no longer significantly contribute to the training. Our next theorem shows that using the train-validation method, after T(2), the feature inner product will grow even larger and will at least (2(5) for some > 0 at the end the training.
Lemma 6.5. Under the same condition as in Theorem 4.5 suppose one runs the train-validation method for total of T poly(d) iterafions. Then max,e(m) (w {-1,1} and for some O.
(T,0) v) 2 9((K) for all j E
Lemma 6.5 shows that at the end of training, the neural network has sufficiently learned the shared feature v. When given fresh task, we should expect a small test loss because the shared feature will also be present in this newly sampled task.
We are now ready present the proof of Theorem 4.5
Proof of Theorem 4.3 By definition, 2i- Lir-val (St) ΣnE(K] Eiery (L.)) where
(l...) E(yk, S(W (w()) S(((W()) S xE,))) Then by Lemma 6.4 and the property of the cross-entropy
loss that (x) 2 exp( - x)/2 2 2 /2 for x > O, we have
min 2 - val (w((), (( < 8E(7]
-2 Σ Σ E ( -
- ---= δ
( k,
1 Tmi
δ (p)
min
(oly
AE[R] 1ETT
This proves the first part of Theorem
4.5 For the second part, consider a new data point (x, y). By Definition 3.1 and Definition 3.2 the data input consists of two patches, one of which is noise and vector & that is generated from N(O, o² - (I-))). Denote by E the event that (ER, E) S 1/4 and
(w (0.0) <) I d3/2 for all [K]. i [m]] [m] and (-1,1), where & is the noise vector from the new data Then using Gaussian concentration, we have P(E) 2 1 ((exp(-d(/1) We divide Crest ( into two parts:
Crest (W(D)- = ([(() x))] = B[((E)((uf( x))1 + E (1(())((()((" x))l
From this decomposition, it is clear that bounding I is more important, since P(E is exponentially small, which makes I2 small. Indeed, can bound I2 = (poly((d) exp(-0.5d' -0.5d// /+). Moreover,
(W(T), under the event E, holds that F F-,( my < log(2), and Fy (T) x) 2 af mmax,c[m]
(w..r (T.0) w)). Applying Lemma we have
(()(((()) x)) E
x) - (W xx),))) < ((K log(2)) < 2exp(-K')
where the last inequality is by the definition of É() and the inequality log(1+z) S x. Vx 2 0. There fore we have that /, < 2 (exp(-K)) Combining the bounds on /1 and 12 yields Lrest (W())) 2 expp(- - kc) + Oppoly exp( (00.//))////) = O( ((epp(-KK) which proves the theorem.
CONCLUSION AND FUTURE WORK
In this work, we study the FOMAML algorithm applied to a classification problem with two-layer CNN trained by gradient descent. We proved that although both train-train and train-validation methods can achieve a small training loss, to get good generalization results, it is necessary to perform a vein-validation split in the data when the noise large and the number of samples is limited. It is of interest to extend our result to more other types of data model (for example, natural language data), and deeper neural network structures. We would also like to extend our analysis to other popular meta-learning algorithms such MAML (with hessian term). iMAML (Rajeswaran (et al., 2019). Meta-Mere MiniBatchProx (Zhou et al. 2019), Reptile (Nichol et al. 2018 and closed-form solvers (Bertinetto et al. 2018).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We thank the anonymous reviewers and area chair for their helpful comments. 7C and QG are sup- ported in part by the National Science Foundation IIS-2008981 and the Sloan Research Fellowship.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005. 2020a.
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.098/6, 2020b.
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference Machine Learning, pp. 205-214. PMLR, 2018.
Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lee, Sham Kakade, Huan Wang, and Caiming Xiong. How important is the train- validaaaliotion split in meta-learning! In International Conference on Machine Learning, pp. 543-553. PMIR, 2021.
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning In International Conference on Machine Learning, pp. 424 433. PMLR, 2019.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differ- entiable closed-form solvers. arXiv preprint arXiv: 08,36, 2018.
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer con- volutional neural networks. arXiv preprint arXiv:2202.06526 2022.
Niladri S Chatterji, Philip M Long, and Peter L Bartlett. When does gradient descent with logistic loss find interpolating two-layer networks? J. Mach. Learn. Res., 22:159-1, 2021.
Lisha Chen, Songtao Lu, and Tianyi Chen. Understanding benign overfitting in nested meta learning. arXiv preprint arXiv:2206. /3482, 2022.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to- learn with statistical guarantees. arXiv preprint htth::880300000 2018 8a.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning learn around common mean. In ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 31 (NIPS 2018), volume 31. NIPS Proceedings, 2018b.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-learn stochastic gradient descent with biased regularization. In International Conference Machine Learning. pp. 1566-1575. PMLR, 2019.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09433 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In International Conference on Artificial Intelli- gence and Statistics, pp. 1082-1092. PMLR, 2020.
Chelsea Finn and Sergey Levine. Meta-learning and universality: Deep representations and gradient descent can approximate any learning algorithm. arXiv preprint 1rXiv:1710.11622,, 2017.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference Machine Learning, pp. 1126-1133 PMLR, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In International Conference Machine Learning, pp. 1920- 1930. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2023
Jiatao Gu, Yong Wang. Yun Chen, Kyunghyun Cho, and Victor OK Li. Meta-learning for low- resource neural machine translation. arXiv preprint arXiv: 084377888.887.... 2018.
Abhishek Gupta, Benjamin Eysenbach, Chelsea Finn, and Sergey Levine. Unsupervised meta- learning for reinforcement learning. arXiv preprint arXiv: arX.v:1806.04440, 2018a.
Abhishek Gupta, Russell Mendonea, YuXuan Liu, Picter Abbeel, and Sergey Levine. Meta- reinforcement learning of structured exploration strategies. Advances neural information pro- cessing systems, 31, 2018b.
Yu Huang, Yingbin Liang, and Longbo Huang. Provable generalization of overparameterizee meta- learning trained with sgd. arXiv preprint arXiv:2206.09155 2022.
Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient-based meta- learning methods. arXiv preprint arXiv:/906. 0271777 2019.
Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-sgd: Learning to learn quickly for few- shot learning. arXiv preprint arXiv:1007.0983. 2017.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055. 2018.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv:1803, 1r3.v91803.02999 2018.
Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. Advances in neural information processing systems, 32, 2019.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. Proceedings of the aaui conference on artificial intelligence, volume 33, pp. 4780-4789, 2019.
Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenenbaum, Hugo Larochelle, and Richard S Zemel. Meta-learning for semi-supervised few-shot classifica- 2018.
tion. arXiv preprint
Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osin- dero, and Raia Hadsell. Meta-learning with latent embedding optimization. arXiv preprint wrXiv:1807.05960. 2018.
Nikunj Saunshi, Yi Zhang, Mikhail Khodak, and Sanjeev Arora. A sample complexity separation between non-convex and convex meta-learning. In International Conference on Machine Learn- ing. pp. 8512-8521, PMLR, 2020.
Nikunj Saunshi, Arushi Gupta, and Wei Hu. A representation learning perspective on the importance of validavali splitting in meta-learning. In International Conference on Machine Learning, pp. 1333-93455 PMLR, 2021.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Ad- vances neural information processing systems, 30, 2017.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The impor- tance of task diversity. arXiv preprint arXiv:2006. 1650, 2020.
Haoxiang Wang, Yite Wang, Ruoyu Sun, and Bo Li. Global convergence of maml and theory- inspired neural architecture search for few-shot learning. In Proceedings of the IEEE/CVF Con- ference Computer Vision and Pattern Recognition, pp. 9797-9808, 2022.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. On the global optimality of model- agnostic meta-learning. In International Conference on Machine Learning, pp. 9837-9846. PMLR, 2020.
Xiang Wang, Shuai Yuan, Chenwei Wu, and Rong Ge. Guarantees for tuning the step size using dearning-to-lest approach. In International Conference on Machine Learning, pp. PMLR, 2021.
11

---

Published as a conference paper at ICLR 2023
Huaxiu Yao, Linjun Zhang, and Chelsea Finn. Meta-leamingg with fewer tasks through task interpo- lation. arXiv preprint arXiv:2106.26695, 2021.
Pan Zhou, Xiaotong Yuan, Huan Xu, Shuicheng Yan, and Jiashi Feng. Efficient meta learning via minibatch proximal update. Advances in Neural Information Processing Systems, 32, 2019.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of adam in
learning neural networks with proper regularization. arXiv preprint arXiv:2108. 2021.
12

---

Published as a conference paper at ICLR 2023
A COMPARISON WITH BAI ET AL. (2021)
In this section, we point out some differences between our experiment setup and that of Bai et al. (202T), which also studies the importance of a train-validation split in meta-learning. The main conclusion of [Bai et al. (202T) that the train-train method could outperform the train-validation method asymptotically under linear centroid model. They have also run experiments using CNN as backbone to support their theory (see Table of Bai et al. (202I)). This may seem to contradict experiments at first sight, since showed in Table that the train-validation method should outperform the train-traii method using CNN as backbone. We would like to point out that this is due to the different choice of loss function and optimization algorithms used by and Bai et al. 2021 as explained as follows.
A.1
REGULARIZER IN INNER-LOOP
Let us focus on the train-train method. Our loss function is given by
t (W, (S)))))))
Σ (WW(W, K
1
where W(W, Sx) represents the weights of the network after J gradient descent steps (w.r.t loss S(),S)) starting from W. While Bai al. (202I) has their loss function given by
2 t (W, (())
K Σ (wW,
(A.1)
where
W(W Sk) = arg mrg L(W", Sx) + W// W W
(A.2)
where À is a regularization parameter. This regularizer is popularized by Rajeswaran et al. (2019)
Zhou al. 2019). In practice, however, many meta-learning methods do use this regularizer in the inner-loop (add citations).
A.2 EXPERIMENT ALGORITHMS
To compare the performance of train-validation and train-train methods, Bai et al. (2021) used iMAMI. (Rajeswaran al., 2019) for the train-validation method and Meta- MintaMMMnBBathProxx (Zhou et al. 2019) for the train-train method. Both algorithms were developed to target the loss function given by Eq. (A.T). In particular, iMAML. used implicit function theorem calculate the gradient Vw Ww WwW. W&). and then uses this information to do gradient descent on W with respect to the loss function given by Eq. (A.I). iMAML is similar to MAML in the sense that both algorithms perform gradient descent on W with respect to their respective loss functions Ctr However, the structure of Meta-Mininn MittaMMinBatthPrron is different from that of iMAML and MAML. It is more closely related to Reptile (Nichol al., 2018), which is another first order meta-learning algorithm. Instead of per- forming gradient descent in the loter-loop, Reptile updates W at each step as a convex combination of W and W(W,S;) This gives
K
1 K
W W +
Σ
(WW, - W),
(A.3)
for some & E (0, 1). And Meta- MiniBBBhhrtttooox replaces W(W, Sx) with W(W, St) in the above. In our experiments, we used FOMAMI. for both train-validation and train-train. We believe that by using the same algorithm for vain-validation with train-train, the comparison fairer.
B ADDITIONAL. EXPERIMENTS
B. COMPARISON WITH REPTILE NNICHO ET AL. 2018
We compare FOMAML (using the train-validation method) with Reptile, which is another first- order algorithm used meta-learning. Different from FOMAML. Reptile does not require a train- validation split in the data set. In addition, the outer-loop of Reptile does not perform gradient
13

---

Published as a conference paper at ICLR 2023
descent, but convex combination between the unadapted weights and the task-adapted weights (see Eq. A.3) ). The results are summarized in Table 4 We see that on both RainbowMNIST and minilmagenet, FOMAML with train-validation outperiorms Reptile by small margin.
Table 4: Performance comparison between FOMAML and Reptile.
Algorithm Rainbow/NNIST
minilmagenet
FOMAMI.
87.52 + 0.20%
46.15 + 1.36%
Reptile
84.97 0.26%
45.19 + 1.31%
B.2
TIME EVOLUTION OF TEST LOSS OF FOMAML
We plot the time evolution of test loss using trained by FOMAML with train-validation and with train-train synthetic data set. The results are illustrated in Figure and train-validation and train-train, respectively.
7.5
7.0
8.4
Test Loss
6.5
8.3
8.2
6.0
8.1
5.5
8.0
5.0
7.9
200
400 600 Iteration
800
1000
200
600 800
1000
Iteration
(a) Train-Vast Validation
(b) Train-Train Train
Figure 1: Comparison of test loss over time of FOMAML trained with train- validatioo and with train-train. The test loss for the train-validation method decreases almost monotonically, whereas the test loss for the train-train method first decreases and then increases due to overfitting.
B.3 FOMAML WITH DIFFERENT NEURAL NETWORKS
In this section, we show that FOMAML with train-validaiton still outperforms FOMAML with tain-train on CNN with more layers and ResNet. The experiments are run on minilmagenet. The results are recorded in 3 We see that FOMAML with vrain-validation outperforms FOMAMI. with train-train by large margin under all 3 neural network structures.
Table 5: Performance w.r.t. different neural networks.
Setting
CNN layers normalization
CNN layers normalization
ResNet18
Train-tres train
25.93 + 1.10%
26.89 + 1.18%
35.63 + 1.26%
Train-validation
46. 15 +: 1.36%
50.89 +:: 1.39%
55.32 +: 1.43%
B.4 EFFECT OF THE NUMBER OF SAMPLES PER TASK
We then discuss the performance with respect to the number of examples. In Table 6 we report the performance minilmagenent when the number of examples per class is 1, 3, 5, which corresponds to 5-way I-shot, 5-way 3-shot and 5-way 5-shot settings. We observe that as the number of samples per class increases, both the train-train and train-validation methods receive performance increase.
C PRELIMINARY CALCULATIONS
In this section, present some calculations that useful for derivations later. Recall that {(2) = log(1 + exp( -2),, which gives (2(x) = - -(1 (1+ exp(2)) -1 Then, we can compute the partial derivative of the loss function using samples from task k as
à L(W,S,) = " Ow.r
à Owj,
E(yk. f(W, xx,))
14

---

Published as a conference paper at ICLR 2023
Table 6: Performance comparison w.r.t. the number of samples per class on minilmagenet.
Number of samples per class
3
5
Train-train
25.93 + 1.10%
36.23 0.82%
38.76
0.66%
Train-validation
46.15 + 1.36%
59.97
1.02%
63.18 0.90%
(yn, f(W, Xx.i))
F3 (W Xx,))
Ow Ow
j.r
(yv,) f(W, 3). >
p=1
Similarly, if we only evaluate the loss on the training set of Sg we have
0 C(W. Jw,,
1 T1 Σ Cvas f(W, xR,)))uk,
Σ
Let / 2 0 and T E [0, J] be the indices for the outer-loop and inner-loop respectively. We remind the readers our notation. Denote ((t,)) (y f(W((()) (8)), Xx,i)) when referring the train- train method and (t...) (yky, S(W(W(), S Xx.i)) when referring to the train-validation method.
k,
At outer step 1, using the samples from task ki we have the inner-loop updates as
i (tr++) ju .xk) = j(w (1.7) jir v)) 1
(ttrr ki
d(w vx)yk,) 1
(t.7,
(C.1)
For noise Éx,i, we have the inner-loop updates as (suppose we are using all the samples from task k for the inner-loop optimization)
(w (1) Ex.s) = (w (1,5) jr
jrr Ex,i)
Σ Ri
7
(E. Ex.a)
2 (t.rr) yu.ijo (aajjjo((ww)
((w (10) Exa)) 11
(C.2)
where the first sum goes from /' = 1 to 1' = omitting the term when i' = If we consider a noise Ek. from the validation of some task, i.e. [K] and i Ig and we only use the training set of task &o for inner-loop updates, then
(2,r) (t,+1) Ev.,) = (W br En,s) j.r
ni Ee
(er) Mel Vnr ((w)) (( (E,r)) Ev.a).
(tr))
(C.3)
we consider noise É from the training set of task, i.e. & E [K] and E Iy and we only use the training set of task k for inner-loop updates, then
(tr+1) (wir
En,))
(tar)
Ev,i)
7
(1)) R.
mn. (Ww (00) (Err)
mn
(1.5)) ki
uk ((wll.)
(1.r) Eves) ||
(C.4)
71
where the sum goes from i' to 1' = except when i' = i. Using only the training set of task k. the feature inner product update is
Bi
(17+1) vk) j(w (1,77 vk)
7
(tr) Ci
d(w
(t.7) jir pR)ye,)) 1
(C.5)
n
Next we look at the outer-loop updates. For the train-train method, the noise update is
(w 1,0) frr Ek.z) = =(w Ek..))
(t.0)
1
Σ
Ce wej ((w!( (t:J)
(E
Kn
15

---

Published as a conference paper at ICLR 2023
Kn ki "k,ao (awjod((w)) ((W)r" (k,a))) ||Ex,
7I (t..)
(C.6)
where the sum is over all K' [K] and i' [x] except when (K, (k, i). Hence, the number of terms in the sum is Kn 1. And
(t.5) (trr) En,e)) + o (( Dx) v2)sk.s)) (1)) = El (yrs yku Σ i Σ (
(C.7)
jm
The arguments in o'()) in Eq. (C.6) are given by Eq.
C.2
The outer-loop feature update is
j(w dr
v) = j (( (t.0) (++1.0)
jrr v) Kn
17
d'(( o 30 ve)yka)) 1
(t.))
(C.8)
where the arguments in (-) are given by Eq. (C.I) The arguments in a()) in Eq. CC.7 are given by Eq. (C.2) and Eq. (C.I). For the train-val caiinvvlidttion method, consider noise Ex, from the validation set of the k-th task, i.e. E Igal. We have
(++1.0) Ek,i) (r Ek.a)
(t.0)
E
1o ye jo (1.2) &E () Ex,))
Kng co (160)))
T_ ((. Kn2 k. y Jo. ((w))""
(t.2) (k,)) i
(C.9)
where the sum over all k/' [K] and 1' E I except when (k'; (') (k, i). The arguments in a'(-) are given by Eq. (.3). If we consider noise Eki from the training set, ie. &o [K] and i I then the outer-loop update is given by
(++1.0 Ev.s) (ww Ex.i) (w
7 Knz
Σ k
(it Wil yee jjo' (ww). Ex (x)) (k.))
(C.10)
where the sum is over all & E [K] and E Iyml. And the arguments in (-) are given by Eq. (C.4 The outer-loop update of the feature using the train-validation method similar using the train- train method:
i jw (++10)) jr D) = ji( (1.) v)
Σ kAS
((L..) kii
o' d((w jo vn)yee)) 1
(C.11)
Knz
where the arguments in o o'()) in Eq. C.II are given by Eq. C..)) Note that the E' term in Eq. (C.9)
Eq. 1C.10) and Eq. (C.11) are given by Eq. C.7 but the arguments in (-) in Eq. (C.7) are now given by Eq. (C.3) and Eq. (C.5)
D PRELIMINARY LEMMAS
We will work under the following parameters for the rest of the proof.
Condition D.1. ||~||| do Ja. 0s vit log(djo. 0g log(d) m log(d)).2 1) Ing(d) v. 7 log(d)o.4
1
Va n O()), K log(d)
5, 1. M d/2. We will also assume that our data split is symmetric: for each E [K]. and j E (-1,1}
Hi:iE Sk.i 11 0,
[(i:
yk. , =
Lemma D.2. Under Condition DnI Condition 4.1 the following estimates hold with probability at least (Kn) 10
1. 11 d) for any k E [K] and i E [n].
max {[(E,,;: Ex. k E [K] e [n), # (K, s
3. max (K(w))00) (0,0) w) : [m]} = O llwo for any j (-1,1}.
4. max
(0.0) Ek.i) : [m]] = Olooog V /ogg for any j {-1,1), E [K]
[n].
16

---

Published as a conference paper at ICLR 2023
(0.0) M(no) V maxxelmi j jW .2) < D(aoo/logmkki for any E {-1,1}.
MooooE I max)e(mm(W (0.0) Ex,i)) &
(w
for any j (-1,1), k
[K [r].
max (r (0,0) .zx)l :EE [m]] O(ooo, Vd/log((kn)))) for any j E 1-1,1,, [K].
M(nnasV) S max j( .xx) s Olana, </looo//( for any j E [-1,1},
[M].
Proof. By Lemma G.I we have with probability at least 1 - 5/3,
1
3
2 शoं = 15x.i11
2 oo
(En,is m S 20 v d log (12(Kn)2/8),
for all k; k' E [K] and i E [n] with (k # (K', f)) By Lemma G.2
we have with probability at
least 1 5/3.
(w00 m)) S 22log(24m/000n
(w jrr
(w.0), Sx.ii /
for r [m]. E (-1, k E [K] and E [n]]. Moreover.
< max j j(w jrr v) S /22og(24m/0000
(0,0)
2
rE[m]
T Vd
(0.0) Ek.,) S v 22log(24mkn/0joo0g/
max (w
rE(m) jir
for all j E (1,,11,44 h E [K] and i E [n]. Using similar ideas, we get that with probability at least 1 5/3.
3 2 V (0.0) for any k E [K]. [m], and E (-1,1). The second inequality is by Condition
(0.0) J.r
2x)1 = ((w
(0.0) (( fr
/ || 2x
S
x) S
3 v (0lgg(1mm////g /600 Vd,
2
4.1 The last
inequality is again by Lemma G.2 Moreover.
doo.Vd
j(w (0,0) rE[m] j.r
=4) S / 221lg((2m//800o
max
4
Combining the above results, we get that all of the above events hold simultancously with probability at least 1 - 5. Taking = (Kn) -10 gives the desired result.
Remark D.3. Since we will use the estimates in Lemma D.2 in the rest of our proofs repeatedly, we will not mention the high probability bound in our theorems. It should be understood that our theorems hold with the high probability bound given in Lemma D.2
Remark D.4. Recall that under Condition D.I the term Vlog(mKn) polyloglog(d). Its pres- ence/absence will not affect any of our prools.
Lemma D.5. Let { ys be two positive sequences updated as
F++1 2 x2(1 (1 + A), Ut+1 Σ y1(1 + B),
where To = o(1), yo = =(1), = o11) and B = o(1). For any D = 0(1), ler T be the first iteration that 2 D. We have that yr < (Gy)) if xn (
17

---

Published as a conference paper at ICLR 2023
Proof. Let consider the above two sequences 21 and ye with the inequalities replaced with equal- ity. Note that this will not affect our conclusion. Then we have
2t = zo + A)", y/ = 30 + B)
And for simplicity, let us also assume that 4T D. Then we have
(1 + A)", which entails
T log D) + log( 1) log(1 + A)
log( 1)
0
Zg
(D.1)
A
Let T be the first iteration such that yr 2 Gyo- Again, for simplicity, let suppose that yr Gyo- Using the same procedure, we obtain that
T' = -2 (log(G)
(D.2)
B
Applying our assumption that To 2 O $) to Eq.
D.1 and Eq. (.2). we conclude that T
T".
E TRAIN-TRAIN METHOD
E. PHASE
In this section, we will show that under Condition D.I our neural network will memorize the noise and will not learn the feature. Let k max (w...
(f)
(1.0) Ex,a) j == yk.,s r [m]]
and A = max { j( jor D) r e [mm]] Let T(1)) be the first iteration such that = R2 m
1/2 1112 (14 midd nn = (1)) and let T(1) = max ki and (k; = arg max (()) k2i So T(1)
the time for the slowest learned noise to have inner product of size @(1). And this is witnessed by the noise vector Eg.
Lemma E.1 (Restatement of Lemma 6.1 train-train method, then for any 1 T
Under Condition D.1 and Condition 4.1 if one uses the
1. For any k E [K], r E [m]) and j E 13 we have (t,) vn) I
j(w j.r
(100) j.r .x) (1))
For j Vg.s and arg max remm (w (1.0) Ei..).
(1.) Ex,)) 2 (w Ex,)) (1+ (1=20(00(02a)*
(1,0)
Proof.
The proof for both parts relies on the following hypothesis which we will verify inductively
later:
(a (t.0) ir
2x) o( (t) for all & e [K]. 1-1,
(E.1)
- ((,r)) ((1), for all 7 e [J].
(E.2)
k.a
j(w (1.7)
mk) o(1), for all E [J], k E [K], r E [m]. E 1-1,1).
(E.3)
(1.)) o' d((W jar (x,)) (w) Eg,)), for all T E [J] if j = Vi,s and (w (1,7) (E.)) 0.
(E.4)
Let us first suppose that the above hypothesis hold. By Eq. C.I we know j(w!(7) (1,7) (c,0)
Mx) is an in-
creasing sequence r. Without loss of generality, suppose that j( vu) > 0. Then Hypothesis
E.3 implies
d' d((( (1.7) J.r vx)i) (w.7) vk)-
18

---

Published as a conference paper at ICLR 2023
Then using the fact that - -(( $ 1, we can apply Eq. C.1 repeatedly to get
j(w (t..) .b) - j(w (2.0) vk) (1 + ,0(1))
(E.5)
where we have also used | 112 ||ا|| ||z1|1 = =1 + o(1). This proves part (1) of the lemma.
C.2 we have Let = Me, Define r(1) = arg maxx" (w Jir" Cg.e). By Eq.
(1 .ERA) 2 3.((t)= Sp,z) - 2 Σ O()) &
( o' ('w (6r)
n. (1 Jrlep (x,)))
Sk.8 |
|
iti
Eg. - -00)0 hal/dd/looggg (w
(1,7) + OL)O'' 5.(()) Ei ((())))
(E.6)
where the first inequality is because - (.) 1 1 and o'() S And we have used Lemma D.2 and Hypothesis E.2 to get the second inequality. Let us compare the size of the second and third term on the right hand side of Eq. (E.6). At (t, the third term is of size (( /n) (log(d)) ( /d), whereas the second term always has Hence the third term will dominate the second term at T) = 0), Note that the size of the second term does not change as and increase, meaning that if at time (t 2 0, T 2 0) we have
(0, 0), if we leave out in both terms and consider,
size ( / log (n)) = (log (D//aappppllllllooo
(t.T) Ar(1)) Ei.)) 211) (0)
then it always holds that the third term dominates the second term on the right hand side of Eq. (E.6). which implies
(r++1) Sr(t)
Si,a) 2 (w (weto
j.(()) Sa,s) + 2 (t.) (r(()) Sa (oo
(E.7)
Applying Eq.
E.7
J times at = 0 and using Hypothesis E.4 we obtain
(w!0..) (ir(0) Sa,e) 2 ( Ea,) (1 (00))((())
(E.8)
n
By Eq.
(.6). we have
(w (r((t) (.,,))
(++1.0)
(w.t..) (t.0)
jr(())= Ea,1)
1
Σ
Kn
(k.1))((
Kn ((1))((((()))) (()) jr(() Eg |E.1 l?
7 0(1))'
+
(w (t.0)
jr(()) Ex,) (0()) Vd (lo((K))
" ((1) ((w (,(() E 10,))
(E.9)
Kn
where we have used Hypothesis E.2 and the fact that --' < and d'(+ < 1 to get first inequality. Let us compare the second and third term on the right hand side of Eq. (E.9) At = 0, using Eq. EE.)) we have that
(O.)) d'((w (0r (a.)) 2 (
(w jr(t) Ei,)) (1 n
220))((aa))
(E.10)
If we drop 77 in both terms, under Condition D.I and Condition 4.1 one can calculate that the third term has size (log(d)* /Vd) whereas the second term has size (log(d)/ (polyyoooog)oo)())) Thus the third term dominates the second term Eq.
E.9 at O. And we get
(1,0) jr(1)) Eg,)
(w(2.0) (.r(0)) Eg,)
(0.0) (.r(0)) Eg,))
[1+ Kn
17
(1 - 2 (0())(((d) e((2d))
n y J
(.r()) E
1 2(1)
Kn
19

---

Published as a conference paper at ICLR 2023
where the first inequality in the first line is by definition of rtt). We note that the size of the second
term on the right hand side of Eq. E, does not change as and T increase. Thus, if (w (w!).))
(0.J) jir Eg,a) =
((1)= k.3 for some > 0, Eq.
E. 10p implies that a' ('(W)rrr fggz) = (2(1)o'((w)
((:)))) for E Then
have that the third term will dominate the second term the right hand side of Eq. (F.9)
t > 0, which yields (w (t++1.0) SE.a) > (w(r.0) 3r((t) Sk,z) since the third term on the right hand side of
jir(t)
Eq. E.9 is positive. We have shown that
(++10)
jr(t+ Sg.))
(w (1+1.0) jir(t) EE.e) > (W((.))
(ir(t) Eg.a)
Then using the same derivation of Eq.
E. we obtain
(t.J) (i((t) Sa.e) 2 (w) j.(()) Sa,)) (1 (0100((2))
n
for any 1 & T(). This proves the second part of the lemma.
We have the following theorem characterizing the size of A7
Theorem E.2. Under Condition D. and Condition 4.1 if onn uses the Irain-train method, then for any - T()
1. A 0(1)a = ((d-112), for E {-1,11}
2. For any k E [K]. i E [n]. j Wk,i and r E [mm]), we have
(w (1.0) Ek.I) (2)
Proof. Recall that the outer-loop for the feature is given by
(t+1.0) (W vx) jw vu)
(c.0)
Σ (t..) Kn W
7
(t,J) o' d'(w for uw Yo (vs, uw),
(E.11)
where the summation is over all k' [K] and [n]. Since (ux, vw) |lll22 + (Zz, Zxr) >
1 - (1) > 0, we get that j jww! (t.0)
j.r Uk) is an increasing sequence in t for any & E [K] and r E [m].
And Eq. CC8)) shows that j(w (t.0)
v) is an increasing sequence in t. We have
d'(wW (t.r) jo vR) s 2j 2j(w (t.)) vn) S (j(w(. jr Mx) (1 (1+10(1)) (0.0)
(LU)
= =0()) 3rr v) (1 (1+70(1))
where is first incquality is by Hypothesis E.3 and our assumption that j(w (1.0)
1/ 0. The second
inequality is by Lemma E.1 And the last equality is due to our Hypothesis generality, consider of the feature in the outer-loop by
E. Without loss of
1. Let r(() = arg max 1.r" p v). We can upper bound the growth
(t,0)
A (++1) (w (t+1.0)
(Wir((+4)) v) (w(f.0) (1.0)
(i.r(e- (1+ (1 (1+
(w (Wir(e=1) w) (1 (1)mm)))m))
(1,0)
(wirrt) v) (1+m())))))
A (1+0
(E.12)
where we have also used the fact that -l((-) < 1 by definition. Note that Eq. E..12 also holds for
j 11, i.e., A (t-1) < (4) (t) (1+ 0(1)m²)) using the same derivation. Next, we want to find a lower bound on the learning speed of the noise. After that, wish to show that the lower bound for the noise actually grows much faster than the upper bound of the memorization of the feature, which implies that noise will be learnt sufficiently well before our neural network can pick up any learning
20

---

Published as a conference paper at ICLR 2023
on the feature. Consider j
Mk.3"
Denote (1) arg maxye[m] (Wirr Sg.z) Plugging Lemmal E.1
(1:0)
and Hypothesis E.4 into Eq. [E.9
we have the following upper bound hold for all t S T())
goon ( ))
(++10) (i+()) SR
(++1.0) (.r(t)
(g,)) 2 (w
(r((t)) Sg, ((1)(1))
(t.0)
(E.13)
Kn n
where the first inequality is by definition of (1). Now we can compare the learning speed of the feature and noise:
A - A (6) (1 O(1)m))
(E.
(++1) 2,3
2 _ k. (1 2(11
17 K
(
541
(E.15)
We can apply Lemma D.5 once we check all of its conditions are satisfied. We have A ((d = o(1),
(0)
((2-1/2) = o(1). Let G = 2. A O(1)nr and B
2(1) d2d J+1 we have = (0) (/2 G-A 2 log(d) 5. Therefore, by Lemma
k
D.5 for any s T(),, we have A
- 2A, (0) This proves part (1) of our theorem.
We now prove part (2) of our theorem. Let k E [K], i E [m], r E [m]] and j = -yk,i- By Eq. C.6
(1+1.)) (w jr
Ek.i) S (w)) (1,0)
Σ
(l.) 28 tw ( ((w (t,J) Ewr Ex.i)
jrr
Kn (WF)((k)))
S (w/rr (x,a) + Kn (K.))
Σ
S (wirr)
(t.0) (x,a) + (O()) Va log(Kn)),
(E.16)
where the second inequality is because both --( and o' d-(-) are bounded by Using Eq. (E.1)) and the definition T(1), we can calculate that (1) = O(1) under Condition D.1 Therefore, for any S (1) 1 we have
max (w.(+ (1+1,0) rE (m
j.r Ek,i) V max (w Ex,) ( rE(m)
0 v (
where we have used Lemma D.2 to get the second inequality.
It remains to verify Hypothesis E.1 E.4
Let us suppose that Hypothesis E.I E.4 hold for all t < (t+1.0)
TT1), Then we have A (1+1)
2A and (w)rr Ex.e) s O(d-1/2) for any k [K], i [n])
r E [m] and - by Theorem E.2
Proof of Hypothesis E.1
For each task task-specific feature Zs. we have at ( 0 using Lemma D.2
M(roasVd) S max j(w
(w.00.0 Za) S Olapo (oooos/V)log((n)))..
(0.0)
j.r
max (0.0) mi O (looylog(mKn))
Since a. Vd o(1), we see that Hypothesis E. holds 0. We want prove that it holds 1+1. For any E [K], E [m]] we have
(1+1,0) j j(w jr
Za) = j(w (1.0)
ki ((,)) of ((w) (t.J) yu (7aes, Zs)
Zk)
Kn
(t.J)) o' d'(('''(())))))
(( j.r
(t.J)
2 M...) ||zz
Kn 1=1
21

---

Published as a conference paper at ICLR 2023
S jw (1.0)
((,))
d' ((wW)rr (1,3) (w) (og(d))
Kn
ki
1)
((. a' ((w))r)) v.) k2j
Kn
K
jw
(1.0) Zk)
(o.) o' ((w jo uu)ue,))00030 W
(E.17)
J.
Kn
k=1
where we used Condition 4.1
to get the first inequality. The last inequality is because log(d) < d. Suppose that at time t there exists some E [m]] and i [K] such that
j(w)
zz. 2 2 max jmaxj(w) (0.0) j.F
1.+1.0)
fr .z. 2 ((a,oovd).
Then, by Eq.
E. get
(t' ,) d' " ((0o..))( 2 2 max (w .zz) 5( (0,0) .z))
Kn
ki
0(a,ooVa))
(..)) (t,J)) d' ((W).) pa)uka) R,s
do θ
Kn
0, vd
log log(d)o. Vd
θ
Here the second inequality is by Lemma D.2 But then, Eq.
C.8
implies
j j(w
(++1,0) 3.7
1) j(w ((w v)
(0.0)
17
(1 k.s
o' ((w
jff v2)
(t.J)
Kn
k
log(d)o.2 0.2
(0,0) 2 min j(w (0.0)
v) + θ
rE[m] J.r
Vd
log(d)o.2
2 Polaoy/og(mMR + O
Vd
O(log(d))144 (0)
We used Lemma D.2 to get the third line and last line. This is a contradiction, since we should have
j(w 1,0) v² A (+11) < 22
Therefore for all k E [K] we conclude
max ma (++1.0) jrr
zx) < 2 max (w j.r
(0.0)
(0.0) zx) o(1) max j j(w jir
v) = o(1) max jww arr v) (0.0)
(m (++1.0)
This proves that Hypothesis E.1 holds at time + 1.
Proof of Hypothesis E.2 Without loss of generality, let us assume that Vi.; = 1. By our estimates
in Lemma D.2 Hypothesis E.2 clearly holds at initialization. Suppose it holds at time t. Recall
Eq. C.7 and that
Σ Σ
(ol(lw (1 (e,))
to(l (111.)) (z))
-=
(t+1,7) (w i,r
Ei.)) + a(wiit- .pz)),
(E.18)
22

---

Published as a conference paper at ICLR 2023
by the non-negativity of (+)). For any [m]] have
5 j( (1+1,0)
.gg = j j( (++1,0)
Zg) + j( (6+1,0) v
S arg max ((w
(++10)
zg) + arg max j(a (t+100) j,r v)
J.r
r'cmm]
r'E(m]
+ o(1) arg max j(w (1-100)
(w v)
r'Em]
= - ((1))A(t)))))))
(++1)
< 22
where we used Hypothesis E.1 to get the third line. Then, by Eq.
E.5 we have that for any [J]
(wi,r (()
mR) I (wi.r ((( (1+)
= =(IAA (+1) (1+70(1))
(E.19)
This implies
m
Σ aa(w] a((w((( (1+1,T) uz)) & 0(1)mA| = o(1)
We also have that
(++1.0) Σ a ((w1, Ek,,)) S (=((t)))))
o(1)
k,
where the inequality due to + 1 (1) which implies = (t+1) m 112 (1+ 207d
Hence,
k,
by Eq. E.18) we get that -1(6+1.00 (o() 2(1). Now, suppose that (((t1..)) 2(1)
k,a
k,
for some 0 S r < J - 1. We wish to show that - h.
p((+1.7+1) 2(1). By our previous argument, ((+1,r++)
suffices to show Em= a(ww (++ :Eg,)) = O()). Because that would imply - k, (0(()))) ((1. We have,
Σ
a((w ((wl 1.r
(+1,7++1 Eg,)) mo
(t+1)
[+
7 (o(1)(oaa)))
ki
n
m 1/2
1+ 2ood 2
(1 m 20())(0)))
S mo
$ O(1),
where the second inequality is because 7 + < J. This implies and done.
((+1,++11 ((((1) = 2(1) 2
Proof of Hypothesis E.3
By our estimates in Lemma D.2 Hypothesis E.3 clearly holds at initial-
ization. Suppose holds time Using Eq. (E. we immediately have that for any 7 [J],
E [m] and & [K].
i j( (++1,) pa) s 5(1)A =o1). dr
Proof of Hypothesis E.4 By estimates in Lemma ization. Suppose holds at time Suppose that (w (e+ EE.)) > for j Vi. and some r e [m].
D.2 Hypothesis E.4 clearly holds at initial-
j.r Recall that by the assumption of + 11 (1), we have
(/ (1+ rooa -s = =0())
(w
(++100) jr
-E.)) < - (t+1) k,j
< m 1/2
23

---

Published as a conference paper at ICLR 2023
Hence, by definition of d'(+) we have o' d'((W), (t+1.0) .(,,)) 2(w 2(w (e+1.0)
S. While
5.r
(wrr (o Eg,) o(1), we have d' ((w ((+1,)) (g,))) 2(w (1t,1)) EEE,). . By Eq. C.2 we have
(w3r jor
(1 EE,1) S (war Ek,)
((t1.)
2
(()) Sp,iil n - d' ((WW)r
SR. 1
n
if1
(w(t)
Sa, + (2
+ (1) (111,)) 3r sa,
n
(E, (1+ (110)((021) + 1/2
(1+1)))
Ek,)) [1 )1))
+ +o(d 1/2)T (1 (1+ o0())(G())
jor
(w(++1))) EE,3) (1+ n
)
+0(d-1/2)
(1+1) 833
(1 (1+ 201)0(00d) T+1 11(
(E.20)
"1
We used ()) < 1 and d'(+) S get the first line. We used Lemma D.2 for the second line. It is
straightforward to check recursively that (w (t-1,)) , S o(1) for r E [J 1] and hence Eq. (020
holds for T E [J - 1]. In the meantime, this also implies o'((w ((1 E [J - 1j. Then Eq. (F.20) implies
(E,))) 2(W j.r EE,)) for
(t+1,T)
(++1J)
Eg,) S =
kii ((+1) (1 2011)((7() + (12
jr
n 00(m 112) o(1).
Therefore, d' ((W (1+1,))
jr Ex,)) ((W -E,s)-
We note that by our definition, (1) is the time taken for the slowest-learnt noise to be memorized by our neural network. Other noises are learned faster. Our next theorem guarantees that other noises has almost the same inner product as the slowest-learnt noise at time T(1)
Theorem E.3. Under Condition D.I and Condition
4.1
suppose one uses the train-train method.
For any K E [K]. i [n] with (k, i) # (k, let precisely, it holds that
khi r(),, then we have =(t) (()) More
m 1/2 (1 1 + nooa
n
And
m 1/2 (1 roदd - -+0.55 S O
k,s
Proof. We first show that - l
(1( m 1/2 (1 ro?a -)) I(L). By definition of Ri 11/2
know that = (1)
112
1/2 (1+ pae when t k Suppose there exists E [T(]] T(] such
that it is the first iteration such
that
= (t)
< m 1/2 (1 yood
If such does not exist, then we
automatically have E(!) 2 m 1/2
7o?r
for all t [T(] TT). By definition of we have
(!-11) 2 m 1/2 (1 p
By Eq.
(E.9
we have the following lower bound on (t)
11-1)
01000(0 log(Kn)
R,
rof -J - ((d-1/2)
1/2 2 m 11/2 (1
=Ω(m m -1/3 -12 goor )-y
24

---

Published as a conference paper at ICLR 2023
where in the first inequality used -.) < 1 and o'(-) < and Lemma D.2 The second and the
third line are direct calculations under Condition D.I Using the same proot as Hypothesis/ E.2 we
have that p(0,7) 2(1 for any 7 E [J]. Using similar derivation of Eq. B. 13 we found that
no ()0(²) )
(++1
(0) (1 12(1 = ki
Kn
n
nood (ood d Kn
(t=l) O(d 1/2) (1 (21)
R
where the last inequality is because
((-1) k1
2 m 1/2 + - = Q(1) > Ö(d (/2) and
(1+ gold Kn
n (2))))) (ppolyoggd))
>>>>> (1). This shows that even if if (1)
R,1
=
((-1)
at some
1, we still have [ 7((m (0mm-112/00
1/2 (1+ 2020
)
(11) and (++1)) (1-1) Hence, = k2 2(1)
(1)
b,i
for all t E k. (T TWy Next, we need to show that k2 S O 112 + aa J+0.5
Let
L' ''=int (T kii T(): [ 2 m 1/2 + yood J40.5 vi E TT
where the inf of an empty set is defined as If t' oo then we are done, because that implies
= (TD)) m ( (1 +
gald -+0.5 Assume t' is finite. We first need to show that =/{
n
O (1+ + 2 -J.s.). By definition of f', we know (('-1) 2 < m 111 + 1o2d J4..5
By Eq. ( we have
S
((-1)
(1-1) k.j
+ O(d 1/2)
+
7 Olo2d)
Kn
+J00.5
nood
< m 1/2 1122
+ Odd 1/2)
+ O
n
Kn
< 115 - 1/2 (2((11
20
J40.5
n
where we used (() < 1, d'() S 1 and Lemma D.2 in the first inequality. The last inequality is because (dd-1/2) o Kn
3d o(1)m o11)m-1/2(1 ?odd -J40.5 by direct calculation. We now
show that -
-Mit. k,
((..)) = Olexp( - ) for all / E [t', TWJ Without loss of generality, assume
yk.t 1. Let r(t) = arg max+e|m] (w(,.)) Ev.s). Using similar proof of Hypothesis E.2 we have
(t,rr = (1) for T E [J - 1]. Since (t.0) (i.r(1)> Ex,a) 2 m- + "0?4 -J+0.5 we apply
that h2
E.7 J times to get (w (t.J)
(r)() Ex.i) 2 0m 1/2(1+ + v Then we have
Eq.
((..)) -E'
(ol(m (1))
. Ex,))) + o ((w (1:)) ,wl)))
j=tIr'l
5 l (((( Exii)) Σ
(1J)
(a((w(1))) (t,))
- Exii)) o0 "
(.)) mn))
< - l' (0(m 11/2 70.d
U.S
-
0 (xp (- O(1) log(d)).)))
(E.21)
The second line is because -f((.) is non-increasing. To justify the third line, first note that the second part of Theorem E.2 implies (w Ev,)) = ((2-1/2) for all r' E [m]]. And
(w (1,+1) -wp" Ex,) (w w En.i) Σ
((rr)
(()) KN k. ve (wwo(() -1.', Ex.) Eks))
25

---

Published as a conference paper at ICLR 2023
+ kkk
l ((rr)
d' o
d'
, 1|5
(10)
n
(w
1,r -1,rs
(1r))
Ck.i)
Σ (()))
$ ((r) -1,1 Eu,i) + O(d-1/3),
where we used -+(() < 1, o'(-) and Lemma D.2 This implies (t.J)
(w (W-1,'' Ek.a) v (w (w-1r's Ek.i)
(4.0)
=0d
since J = (1) and (w (1.0) 1,m' Cx,a) ) = ((d-113)) Hence.
(c,J) o (( -1,r' Ev,i)) & mõ(d-1/2) = =
By Eq.
C.1
and Eq. 11 we get that
(I.)) (w 1,r Vx) S (w -im, ux) S (w Ux) O(d
(c.0)
O 1/2 log(m)).
where the last equality is due to Lemma D.2 Thus,
m
Σ
Co((w ((w 1.. vx)) S māld Vlog(m)) o(1).
(t.J)
This justifies the third line of Eq. E.21 Using Eq. E.15 one can directly calculate that T(1) (polylog(d)). Then, using Eq. C.6
we have
(++1) b,
S < R3 + 0(d-113)
n p(t. P (o)2d)
Kn ki
s / + ((d-1/2) + Kn
0(o2d) exp (- log(d)0.)))
< (1) + (T() (0
" ((xp ( log(d)())))
Kn
< | + (0(0 ((o2d))((ex) exp log(d)
Kn
# + 1/3) ((1) (exp
exp ( (- log(d)).)))
(1) < 3 m 1/2 1 ao -40.55
< 2=
In the second last line, we can absorb (1) into (dd-1/2). And (()) n O(o = Ō(1) To get the last line, recall that = Z (m 1/2 202d - = ((1/polylog(d)) And 6(1) (exp log(d)).6))) o11 ld) This concludes our proof.
R
In short, we have shown that in Phase I, the feature has not been learnt well by any neurons, which is characterized by the inequality A (TO)) < (d-1/22 for j (-1,1}. And for each noise vector Ek.i
there exists weights w) (T(P)) (0) with j = yk. such that their inner product large: (w jrr ((1).
(T()),)
En,)) =
j.r
E.2 PIASE II
We have already proven that the end of Phase I, all of the noises memorized by the network with an inner product of size ((1) whereas the feature barely memorized, with an inner product of size ((d-1/2) After Phase I, there is no guarantee that -e((..)) = ?(1). For this reason, the learning of both the feature and noises will slow down. The difficulty in analysis at this stage is that
no longer have -(((.)) (1). The value of d((t.)) is getting smaller the inner products
k,
26

---

Published as a conference paper at ICLR 2023
for Ex.s) gets larger. Moreover, if examine Eq. (C.6). we observe that the second term on the right hand side could have a non-trivial effect on the growth of the noise inner product, if the third
( term the right hand side becomes exponentially smaller than the second term because of k, But the sign of each of the summand in the second term is undetermined, which makes the analysis even harder. We first make some claims that will help prove our theorems. And we will verify these claims at the end of this section. Let T poly(d) be the total run time. We have the following claims under Condition D.1 and Condition
4.1
Claim E.4. For any E [K], i E [m], r [m], and E [T()) 7], let j = -kk. then
(wrr (v.a) 013-113).
And
w Ex,i) O(d ((2)
Claim E.5. For any j [-,, and [T(1),
(1),,, I] we have
A ( - Oad
Claim E.6. For any j E (-1,1), k E [K], r E [m]] and t E (T(1) T) we have
max (w Jir
(1,0)
,zz) = o(1)AA)
Lemma E.7. Let 1 E (T)) [K], i E [n]] = yk and r = arg max
(w (w Jur Ex,r).
Suppose Claim E. E.6 hold at t. Then
112111((++ (w (t.0) Ev.i) 2 12 m 1/2 (1+ Jo -1
And
(w Ex,)) 2 2(m 112)-
Proof. The proof of the first inequality is very similar to the first part of the proof of Theorem E.3 Hence we will omit it and focus on proving the second inequality. We first recall from Eq. (C.2 that
(1,r+1) jr
Ev..)
(WT)))
(t,T)
EK.)) n
Σ
(1.)) R
jn. (W/l?) (x.) Ex,i)
(w
(((.))) o' d'( (1.r) Ex,,i) E
n ki
2 (t.)) En.i) - 1/2] - " p(t..) o'((w fo
(f.r) (x.,)) 112
(E.22)
for all J T [J - 1]. Here we have used- - (.) < 1, 0'() < and Lemma D.2 to get the inequality.
(w!! (1,0)
jr Ex,a) > m-11/ then we have
(w (1 Ek.i) 2 (t.0) Ev,s) - Jō = 1mm (1m2)
The last equality is because m 1/2 > 1/2). By the first part of this theorem, we have (w jrr Eu.a) 2 (m2 + 202d - Let us consider (1/2 + rold ((++1) s
(1.0)
(1.0) Ex,a) s (m 1/2 10m--122 g0 )) for some E [J 1]. Using similar proof as E.2 it can be shown that -((e.') = 2(11 for all I T
the proof of Hypothesis
(w) Eu,i) < 100mmm1//0
2a2d a ") Applying Eq. (B.22) +1 times, we get (w (tr++1) ERRA) 2 7 which implies (6,+1) Ex,r) 2 2(m 2(m-1/2) if (w/(r) En.i) 2
(1.0) Ex,))(((11 + 202d
2(m-1/ 1/2 1/2(11111 (1+ 2020 ((+1))). Lastly, Eq. (E.22 also implies
(w (t.J) En.i) 2 (w (tr+1) En,,) (J - (T + 112 = 2mm 11/2).
This proves the lemma.
27

---

Published as a conference paper at ICLR 2023
Lemma E.8. Suppose Claim E.4 E. E.6 hold at Let k E [K], i E [n]. If
= R,t = 0 0(mm (mmmm// 1/2 (1 yožal -J+1
=
(lit..) = O(d log(d)".))
then-
Proof.
Without loss of generality, assume yk = 1. Let r(() = arg max maxx -.,z). We
(2.0)
have
m
((.J) k,i
-8' Ei ((l :k.,)) o ((w ,.,)))))))))
i (o((w)))
Jit
j=Hlr=l
m Σ r=1
S l' a(((1 (( Ski)))
(o((w -Irtt ((r: + o (( -i. 1, m.
(t.))
Using similar proof as the proof of Hypothesis E.2 it can be shown that
((tTT)
12(1) for all
T E [J - 1] under Claim E. E.6 We then apply Eq. E.22 J 1 times to get
(.) Ek,a) Jō(d (1 O 7o2d
(w((.)) (1) En,a) 2
(ww1.00 (c.0)
20)) 20
(=() jō(d-117
(
n
% J
.(1)=(())
( n. (1 e11)
n
2(11m 1/2 Y d
The third line is because by assumption we have (t) kiz
= (m
+ 202d - -J+1 = =0(1) >
JO(d 1/2). On the other hand, Claim E.4 tells us that
(t.J) 1,r Ex.)) ((t-1/2),
for all r [m]. Henee,
Σ (ow (GJ) Ev.i)) (w.))) mm = o(1).
By Eq.
C.I and Eq. E. we get that
(w (t,J)
(t.0) (w (w,, Ux) S (w Ux) 1/2)
Ww.::: vk)
Thus,
Σ aa((w!!
(t.J) vzi) = mō(a 1/2) o(1).
We now have
(1
S -e" -e((((((
(o((w())) ((.( (t,))
(k.)) ((.)))
Σ
m
(1) Emri)) + o ((("" ux
k.
< - (2()) 1/2 RoRd
o(1) o(1))
n
= O(1) exp ( (- (21()) 1/2 70.d
= Odd 1o
This proves the lemma.
28

---

Published as a conference paper at ICLR 2023
Theorem E.9. If Claim E.4 E. E. hold for all T(1) <t T 1, then
<0(mm m 1/2 (1 1+ 2o? -J+1
)
n
for all k E [K], i E [n].
Proof. Set A(q) 1/2 (1+ rond -9
for g E [J]. We proved in Theorem E.3 that ((((J)) v
"
( - [A{[J - 0.5)) for all lt E [K], E [n]. Define
t(k, i) inf { < T - A(J 1), ++++)
where the infimum over an empty set is defined as co. In words, t(k:, i) is the last iteration with
k,j < A(J - 1). We have shown in the proof of Theorem E.3 that = (1) < 1.5A(J 1).
Similarly define
f(k: i) = inf t(k, sts :
5 > 4A(J - 1), 1), >t]
Again the inf over an empty set is defined as co. So ē(k, a) is the last iteration with = s 4A(J
1). Our goal is show that t(ke i)
for any &o [K] and [n]. We will prove this by contradiction. Let us suppose that ((k. i) < co. Then, for any t E [B(k, i) + 1, E(k: i)] we have that
(t. (d 1ng(4)).3) by Lemma E.8 Recall k
(++1)
= ki
+
Σ
(..J) (1.)
K2 d(w (e.w)))(o2Vaa/ie
Kn
(K,))(KK))
1 J) o' ((w)))
(.
((ood))
Kn k.
2 k ki
+ n
E
(.d
Vo Tog((K)))))) Voggooo) W3
Kn (WFF)
Kn k. d' jr _x.,))
1 ((,,)) d' 0.2)
(E.23)
where the second inequality is because o d'()) S 1. And similarly we have
(++1)
(t)
n
((.)) d ((w 2i (KFR)
Σ
(t,)) Exx (e
k
Kn
(e. o' d'
(1.)) ((oE))
Kn
0 0( ViVToo//
Kn RN
" ((t) o
(B.24)
Kn (K.3)
where we have again used o'()) S 1 to the second inequality. We have the following bound due to Lemma E.8
E(k..) Σ
i(k.i)
1 0() = Σ
M
" (( log(d)
Kn
Kn
+1
(=((,)))+1
n
TO(d 1og(d)00.3
Kn o(d
(E.25)
where the last equality is because T = Oppoly (d)). Let
i(k.i)
(K''') = arg max
Σ
(1,))
29

---

Published as a conference paper at ICLR 2023
Suppose it holds that
t(k.i)
< d//4
(E.26)
(=,())))-
Then using Eq. (E.24)
get
F(h.a)
(1).))+)
"
Σ
Kn (k, (k,
((k,))
7
Σ
((oRd)
Kn
+ n7 Va log +o
S 23 (1k+++1)
S 33AJ- - 1).
The second inequality is due to Eq. E.25 Eq. E.26 and the definition of (W' i'). The third inequality is because ()
vd Vd/lo Kn) 1/4 + o(d 1 = (d and k,
(*) 2 A(J
1) = 6(1). Thus Eq. (E.26) contradicts = k.
(((k)))-1) 2 4A(J 1) and we must have E(k: i) = co.
Next, we will show that if Eq. (.26) does not hold, then we also have i(k:, Do. Let us suppose
8(A.))
d//4
(b;
Since - -K > 0 for any t, we get that Ei=(H.))+ to < i( i) be the first iteration such that
(t:t)) is increasing in to. Let t(k: i) + 1 <
i(K.F)
(1,J) KK 2 1/8 1/8
Σ
((.)) Ki 2 111/441/4 = d//8
(1
Since each -((())) 1, we get that
to
(.,.)
(ood) K
K
(++
i(kii)
< + d 1/8
1/8
(bbi)))++1
((k.))
1d8
Σ
((,) Ri
(B.27)
(=t(k:s)+1
where the second and third line are by definition of ty- We can sum Eq.
E.23 over time to obtain
to
Σ
(++1)
7
Σ
Σ
Kn
(=1().))
[= (=())))-
i 3 +1 (1)
7
(1.J)
d' (w j.r
(1,3)
Ex (0
Kn
(=t(k;))+1
to
i(k.x)
7
Σ
(() 0 /d log(Kn) Kn)
+
Kn
(=t(k.)- -1
t= +k,,))+ (K25)
30

---

Published as a conference paper at ICLR 2023
to
(o
(( ((x
Kn
(=((),))+1
(k..s)
7
Σ
1 0 Vd
Kn
(=1(),)-
t= + (A R)
().)) d' d' 2
(1,3) jor Ew (oood))
Kn
(=
where the second inequality is because to < [(, i). We have used the definition of (k')") to get the last inequality. Then, subtracting Dte 2
from both sides yields
Vožvd
{(k,1)
1f)+ F
k 2 θ
(1(
v Mog((K)) Kn
Kn
+
0 notd
Knym
i(k.a)
i(k.s)
O(d 1/2)
((,))
((1)d-1/8
Σ
1=1(,,))+1
t=
1 1/8
().J)
(=((+)))+1
2 0(d2/8).
(E.28)
where we used Lemma E.7 to get the first inequality. The first equality is due to Eq. (B.27). The last
inequality is by our assumption ((k..)
(...)
2 2d/4 is then straightforward to check that W
(()(()))+1
5 2 ((d
for all 60 + 1155sin ((kk i).
To see this, let us sum Eq.
E.23
over time to obtain
Σ
(++1)
Σ
Σ
(i.)) ki
Wi
Kn
i=to+1
i=fo+1
t= (k)))
Σ
" ((t))
o' ((w ( fo ((oo))
Kn K3
i=to1
t-1
Σ
Σ
Nod Voo log(Kn)
Kn
1
i(k.d)
17
(L,)) 0 0 Vd /d/log(())))
Kn
kj
i=6+1
(=((k,)++
(k,))
i(k.))
Σ
17
Knell d log(Ko)))
Kn
1
{=(((t))+
no? dd (og(Kn)
E(k.i)
(1)
2 = (o+1)
+ θ
Kn
Kn
(==(kki)-1
i(k,i) Σ
E(k.
> 1(1))-1188
((.J)
k + 1/2-122
[k.0))
31

---

Published as a conference paper at ICLR 2023
((k.s)
((1)d-1/8 1/8
+1
2 (
where the second inequality is because we are removing a positive term from the sum. The third inequality is because t-1 f(k, i) and > t(k. 1). The fourth inequality is by definition of (k', f'). The second last inequality is by the second last line of Eq. (E.28). And our last inequality follows Eq.
E.28 Then, using similar proof of Lemma E.8 we have ((0.)) ((exp(-((d</e)) for
all l0 + 1 < L S i(k, i). This yields
8(M.8)
E(M..) Σ
Σ
aan W
( K
(=t():))+1
(R,,))
1=t++1
((K,a)
[(k,5)
S 2d 1/8
0(exp(-(d'181)
t=t(k,))+1
i(k,i)
S 2d/8//8 1/8
Σ
2 + +T (TT-pex(-O((d
((K.a)
S 2//8
1/8
Σ
((. W + 1(d
t=
i(k.i)
$ (2d-1/8 + )(
[t,
(E.29)
k','"
[=
where we used Eq. E..7 get the second line. And we used T (poly(d)) get the fourth line. To obtain the last inequality, we recall the assumption _
((k.i)
-,," > d//4, which
implies o(d-1) < o(d- ((k.d)
- -(ll.)) Eq. (E229) a contradiction in the form of x S Ar
[(k. for some x: 2 0 and A < 1. This implies that under the assumption _ W.
(t..) d/44
we should still have ī(k, i) = cc. Combining with our previous result which says [(k: = oo when ((k.d) (((k))
+1= - J) S d//4, we conclude that Elk: i) = oo and we are done.
Now that we know the noise inner products are upper bounded by 0m 1/2 yofd -J+1). ). we can provide a convergence guarantee based on this upper bound.
)
Theorem E.10 (Restatement of Theorem 4.4 (1)). Under Condition D.1 and Condition 4.1 let
T = (oly(d) be the total number of iterations. Then
min ( < -1 (E[T]
Proof. By Theorem E.9 we know that
70.d JJ+1 Ō(1)
O m 1/2 1/2(11
12
for all l E [K] and i E [n]. Denote E(t) = Σt, k.t- It then follows that = < Kno(1) = (1). Moreover, if we sum Eq.
E.24 over all k; i, we get
(++1) > E( + vn(Kn - 1) Σ
(()))) 0 V (ovlog(Kn)) 7
((1)))
Ω
O(oZd)
R4
Kn
ki
(k:4)
> = 211 Kn
Σ
(1,))
(
m
32

---

Published as a conference paper at ICLR 2023
where the Q2 1 ym
term is by Lemma E.7
We can then sum over to obtain
T-1
Σ ((+)))
00 Q1(1
"
Σ
((t 2 ((o)d),
Kn
hss
vm
(=7()
t=
(=
nooe Knym
(T()))
12
(t.)) Ri
(=) k,
T
K m oed
0
Õ(1) = =1))
(E.30)
k,j
t=
The last inequality is because (T) - ( < O().. And we can bound the minimum over t by
((. =ō (T (T-Tw)))) =6 TT
1
min LE
T-1
where the second equality is because T(1) = polylog(d) = o(T). Denote
((,,)
kid
k,,,( i.c. the argument of -((t.)) is J,k,), Then the loss is related to Ee (w Σ ((((t,
p(t).) by
Let 1' = arg min, ΣR,e (t, By definition of e()) and E(-) we can bound -f(xx 2 R3
exp(-x)/2 2 {xx) 2 for x > O. This can be used to bound our loss by
min T (witt) S Z (wilt)) rE[T]
Elaatt J,k())
S 2 Σ el (a(t.
< 5 Tn
This proves our theorem.
It remains to prove Claims E.4...E.6
Proof of Claim E.4 lowing upper bound
Without loss of generality, assume yk. 1. By Eq. (. we have the fol-
(1+1.0) (w -w- Ee,i) S (w -1 En.a)
(t.0)
Σ
(e. o' d' (ir) Ev () (ooggkkk)
Kn
(c.0)
-1,r Sn.i)
Σ
((,J) Wa
d' (..))
Kn
-I
(125")
(t.0) S (w -1, Ex.a)
" O 0 Tog Kn))
Kn
(k
where the second inequality is because we are adding a non-negative term to the sum. The last inequality is because o'()) < 1. Suppose all of our claims hold for t s T', where T" s ST-1. Using a similar derivation of Eq. (E.30) we have
T
KOLO a log(Kn))
Vl22V log( Kn))
Σ
Σ
(. E S
Kn
(o - 122
(=)
(K(,P")
33

---

Published as a conference paper at ICLR 2023
Then get
T
1T0- (w 1,
Ek.i) S (w (T20 Ek.i))
lolev Kn))
Σ Σ
Kn
W
1= T (16,))
K log(Kn)) (
S (W-1, Ek.)) +
S 0O O(d11/2)
(/2
where the third line due to part (2) of Theorem
E.2 This proves our claim.
Proof of Claim E.3 We will show that for any T I T O(poly(d)), we have that A (T)
O(d-1/4 for E [1,,1}. We have the following upper bound
A A (1)
"
Kn
A (0) 1 0(1)
11"
((t))
Kn
k,i
Suppose that there exists some T such that A
2 d-1/4 1/4 for the first time. Then
i-1
1/4 S A 10)
(2(0))
II (=
(1 11- 0(1)
my ((e,))
Kn
R.i
1/4 A (Tay)
(1- 0())
n7d Σ ((t.))
v II (=
Kn
k,
11-((1) 01) y
(ttnd) ki
2 (2((2/1))
Kn
(=T0)
log
1 O(1
my
(ttrd) kg
2 ((log(d)),
Kn
(1)
k
i-1
-0(1)
(t,J)
2 {(log(d))
Kn
7()
(og(d))Kn mydd
Σ
(tw)) kg
2 1
1=
K.
The third inequality is because by the first part of Theorem
E.2 we have A, (T
Odd-1/2). And
hence d 1/4 /AA (T()) (i(d//4) Note that in the proof of Theorem E.10 we have that
Σ
(t.J)
7. m(o of log(d) (Lg
K2
ki
(=PO)
k.
which creates contradiction. Hence, for all < T", we have A, S 1/4 This proves the claim.
Proof of Claim E.6 By our result in Phase I, we have that Claim E.6 holds at T(), The rest of the and we will omit it here.
proof is similar to the proof of Hypothesis and
34

---

Published as a conference paper at ICLR 2023
We have shown that for T = poly(d), the feature has not been learnt well if one uses the train-train method. Thus the testing loss will be large, which is characterized by the following theorem.
Theorem E.11 (Restatement of Theorem 4.4 (2)). Under Condition 4. and Condition D.1 the test
loss is large throughoul the whole training process
min Crest (W()) 9((). EE
Proof. Sample new example x from the distribution, since we use the convolutional structure,
we can assume that the first patch x(1) = y (v + z) and the second patch x(2) = g. Clearly
(Ex. E) follows the Gaussian distribution with mean zero and standard deviation og ||Ex,ill. By
Lemma D.2 we further know that [|Ex,ill2 - 20 vd. Therefore
P((EER, 2 2 d 1/4) S 2exp ( (-
80 (
S 2 2xe((_
(E.31)
Similarly we have that
(0.0) P (([( for .0)))))))) d3/2) s exxp
EE)
I =2exp(-d!(1)
(E.32)
80
Denote & to be the event that (Ex,i, E) < d-1/4 and ( jr E S d3/2 for all k E [K]. i E
[n]. r E [m]] and j E {-1,1}. Applying union bound, we have that the P(E) 2 1 - 2(n + m) mxpp(xpd 2 1/2. We can divide Lrest (W) into two parts:
Ciest (W)- = B[((uf(W,x))]
E[I(E)((Ff(W x)) ((II(E)(((((WX))
2 ([)(E)((I/((x)))
(E.33)
Let T' < And suppose that T' 2 T(), When event holds, for any j E (-1,1}, we have
T
(T" ())
jrr [) = -w .E)
(0.0)
7
Σ
Σ
d (12) (x.
Kn2
t=0
(K.))E
-1
I (w jor
(0.0)
.E)
"
Σ
(L.)) d' ((w (xx.i)d 1/4
Knz
1=0 (K
(0,0)
7
((t 1-14 R3
.E)
jar
Kno
t=0 (k.))e
-) ndd 1/4 T(2)
nd 1/4 T
(0,0)
(L.))
Σ
(L.J)
< jr
Knz
kj
K
(=0
(K.i)EV
1=
(k,i)e
1/d-1/1
jo .E) nd 1/17(22)
(0,0)
O(1)
Knz
< (0,0) .) 1/4) ((411/4)
jr
(d-11/4)
(E.34)
where the second line is by Eq. E.31 The third line is by 0 o < 1. The third last line is due (-() < 1. (2) polylog and Ei= Ei (t,J)
4, Ö(L) The second last line is by Eq. E. We note that Eq. (E.34) holds for all j E (-1,1), r E [m], and y (-1, 1}. Using ((w(T'')) (T',0) 2) s ((d-1/4) for all [m] and j E (-1,1).
the same procedure, one can show that j(w j.r Now without loss of generality assume y 1. We have
e(v( P. (WHT +1 x) - F-I (W(T) -1 xx)xx)) e [41 (W!)) .x) .x) F F-((W .x)
35

---

Published as a conference paper at ICLR 2023
F+1 F+1 (W (29)
.x)
a ((w (wr v x ((w (5))
Σ o + + (0(()11/4))
e (m0(d
2(1).
(E.35)
where second line is because 2(-) is nonincreasing and the fourth line is due to Claim E.5
Finally
plugging Eq. E.35 into Eq. [E.33) gives that
Lest (W) 2 ( (uf x)) B[I(E)0(L) ((F(E)) Q(1).
Since T' [T(, is arbitrary, we get that
min (E[TO),T]
Lrest Boen:(WW)) (W(0) = -((1--
However, the above proof would also work for T < (()) using our proofs from Phase Hence,
min Lusst (W()) 22(1)
EE(T)
which concludes our theorem.
F TRAIN- RALI--VAIIAAION METHOD
Contrary the train-train method, we will show in this section that under Condi- tion D.I the feature will be learned by our neural network. Abusing notations, let
max { (w(..) Ev.i) T [mi]. k = max { (ww (1.0)
W..r..r Ex.i) r [m]]. and A
(j(w()0) fr D) e [m]] for j E {-1,1}- Define = Joo / /lg (n), ki
max
max (C, (C, k.th and K. = max (()) [.). Let v = {(k, : [K] m1). V ((k,
13. So represents all of the samples from the validation set of all tasks. And V represents the samples from the validation set of all tasks with label j. We first present a series of useful lemmas that hold for all 2 0. Theses
[K] 71, yk. = 1), and V_ = [(k i) : l E [K] n1. yk.i = -1.
lemmas basically show that the learning speed of 75 very slow compared with the learning speed of the feature V.
Lemma F.1. Under Condition D. D.Iand Condition 4.1 for any 12 O, E [M]. j E (-1,1), one uses the main-validation method, then we have
(1,0) max j(w j. .z) o(1)A
Proof. Without loss of generality, let j = 1, E [M]. Denote r(1) = arg max (w(trr) 2x Define
(w( Ir(()) zx)
D(t)
A (1)
At t = 0, by Lemma D.2 we have
(( (0.0)
(.)())) 2
D(0)
<
O(o, Vo V(o.VV///og(mkm))) o(1).
A (0)
((op)
36

---

Published as a conference paper at ICLR 2023
Define Do ( v d log (kK))). We show that for any t' > O. we have D(t)= = 2Du o(1).
Observe that similar to Eq. (E.17). we have for any 2 0.
(1+1100) (w 1rr
-xx) = (w), 1rr
(1.0)
2k)
7
Σ
((
K
(M'
J.EW
S (w z
7
Σ
d' ((wl.r") pw (0(2d))
(F.1)
K
(Ae JJEV
where we used Condition 4.1 for the inequality, since (Z zx) S max(||z 1 | (ī]) (
Comparing Eq. (C.II) and Eq. (.II). we can roughly understand why this lemma is true: for any r E
[ml, the growth of (wirr) v) is at least factor of 1/(o]d) = (1) faster than that of (wl.r² 7z).
(t.0)
(t.0)
We can compute
(w (t.00 Ir(e)) 2 5
(ww()))) zx) - (1.0)
(m z+:)
(w.0.0) (0.0) Lr(eer z+>
(w irr('') [z3 (WIr(e) 2x) + (w (rr(e>> 2x:)
0(o2d) (w
(t+1.0)
v) (w (wIr(e)> 1i + |w (w..ree)= 7x))
(1.0)
1,r(()
Σ
((0,d) ((w) 1,((1() 2) - -(w -(w 1,((t)) w)) + ((w (0,0)
((m (1+11)
(1,0)
I.((e) Z
E
= (()3d) (w v) - (w (0,0)
I.((t)) v/) + (w (0.0)
Ir(ee) 2x))
< (A
min rE(m)
(wir v)) 1.r(0) 2x)
(0.0)
(0.0)
s ((odd) + O(oo v log(mKn)) DoA (0)
where the first and second lines by triangle inequality. The third line is by comparing Eq. (C.11)
and Eq. F. The fourth line is by the fact that (w((.0) ,2) is increasing in t for any r [m]. The
sixth line is by definition of A (t') and definition of r(0). The last line is by Lemma D.2 Then we have
(w zn)l
(A O / log(mKn)) + A (0)
1r(ee A (09)
< 0(0)d) Vlo(mmnn) + Do 2Do.
where we used A is increasing in get the second inequality. The third inequality is by direct calculation and comparison: Do O a. h/d//polylo((/ oo /.g(/oommmn = a. a. (oo//oomm/n/oooiioe (mm/lllloo//ll oo1) This proves the lemma.
o¹d (o.vd)²
L
Lemma F22 Under Condition D.1 and Condition 4.1 for any j E (-1,1), r E [m]. if at time we (1,0) have j ( in v) 2 1/3,,, then for any ks E [K]
j(w (1.0) jor zz) O(32d)i (1.0) w) = o oo)) (1.0) v)
Proof. Without loss of generality, assume j = 1. And suppose (f.0) v) 2 d 1/3 for some
r E [m]. By Eq. (C.II), we have
d 1/3 < (wl1.)) v) = =(w(0r)
(t.0)
(0.0) v) Kna
o ((-)) ,K))ue))) ||1112
ks
== (
37

---

Published as a conference paper at ICLR 2023
t-1
d-1/3 (wi,r) (0,0)
v) -
1
(e
d'
((
(W pe)yle.)) ||
Knz
jr
t==0 [k
t-1
d-1/3 - 00000000o(mmmmi 1
1)
Σ
Σ
o' ((W))
(C pe)y)..)) ||
Knz
jo
f==0 [k
1-1
2(d-1/3) $
Σ
)) of ((w (x)))e.)) 11
nnl
#==0 (k
Recall that from Condition D. and Condition 4.1
and
Kw 1. .1) S o(d-1/2) < 015 =
Σ Σ
((W vk)UEe)) , 11l11
ks
Knz n'=0 (R.i)EV
This implies
(0.0) (w 1, ,,,r,,)] = -0() "
Σ
(ie d' (k)UEN) 111112
Kn
ki
r'=0 (k.
Hence,
(1.0) (w Ir .)) (11)
7
Σ Σ
2i of (
(R) 1211
(R2)
Knz
y==0 (k.
On the other hand, from Eq.
F. and Lemma D.2 we have
(t.0)
2x) S (0.0) 2x) 1r
o' d(w
(E.)) 17
Kn2
==0 (k.))
s V0loso0vd/llo(mmlo
(e (( jor 1.0..
Knn
(K.))E
S -(1)
7
Mll k2
d' ((
(t v.)yn.)) ((ood))
K
1'=0 (K.))E
Σ
J) d'(( (6.)) vr)yee))
Knz ==0 (R.))EV
k,
(w (1.0) = =(1) (1.0)
v)
v)
1,
where the third line is direct comparison of the sizes of the first and second term of the second line. The second last equality is due to Eq.
Lemma F.3. Under Condition D.I and Condition 4.1 for any j (-1,1)) r [m]. if at time we (t.0) have (w (w jr v) < 1-3/ then for any l E [K]
j(w (t,0) zx) 1/3
Proof. Without loss of generality, consider 1. Let 1: E [K], [m]] and suppose (w((.0) v)
d-3/ 1/3 at time t. By Eq. C111)) we have
1/3 > (w 1,r v) = (w (0.0)
(t.0)
7
M o' ((w
(C.) (e)UUe.) 1
V)
Kno
kg
t==0 (k.))
38

---

Published as a conference paper at ICLR 2023
d-1/3 (0,0)) (0.0) v) >
"
(en :r) |11|
((w!) 30
Knz r'=0 @
[-1
1/3 min
r'Emm] 1,," v2 >
(w: (0.0)
"
((W))
Knz t'=0 (k
k,
1-1
d 1/3 +0d (12)) > Knz r'=0 (
"
Σ
(tt o' ((W)) vb)Dk..) 112112 k,d
1-1
1/3
r
(lt of ((WWf (.luk,)) 11122 k,
(F33
Knz
P==0 (k.
where the fourth line is by Lemma D.2 Meanwhile, using Eq.
F. and Lemma D.2 we obtain
(w) 1,r Zbb) I (wi.r
(1,0)
(0,0)
1,r Zx)
((. o' ((w 1r M )u)ue, W3
(GJ)
Knz ===0 (K'
S i,r 3xp + 2d (
(0.0)
< O (000, v d (lg(mKnn) + 2d 1/3
<d 1/3
where the second line is by Eq.
F. The last inequality is because the first term in the second last
line is (d-11/2 and (o)dd) (1).
This proves our lemma.
Lemma F.4. Under Condition D.1 at time t we have j (t.0)
and Condition 4.1 for any j j (-1,1), [m]] and ls E [K] if
io .zk) () .)), then
j( Air ,2x) = dl j0 v))
where w (t.3)) on both hand sides refer to the weights w (t.0) jrr samples from S
after steps inner-loop updates using
Proof.
Without loss of generality, let j 1. Using samples from S similar to Eq. C..5 we have
(1,7+1) (w (wl) , 1) = =(w(t)?) , 1)
(t,77
7
(1,7)
(1,t) o' d'(ww) v.)Un.) 1
(F.4)
kj
11 1=1
And
7 m
(t.+++) (w (ir =x3) (w(()7) 2/,
(1,7)
(+rr) ki
0' (177) (a) ( 1
111
i=1
This implies
J-1 1
(l..) (w 1,r vi = =(w((0)) ((.0)
v)
((,,))
(1.T) dW pe)yee)) 112112
ki
11
(1,0) (w(t."), .za) 1,r Za)
(1.T) of ((( mo)un.e) I| 12
n1
Recall ||0|| = and | = Olo2d) by Condition 4.1 O(odd) (f,0) (1rr
Since we are given (w((r) zz)
(w((o)) v), we conclude that
(t.)) Zu. = (w v). (w(tr²)
39

---

Published as a conference paper at ICLR 2023
The following corollary is immediate result of Lemma F2 and Lemma F.4
Corollary F3, Fix j E {-1,13. Then for any r E [m]] if at time we have I ( thenfor any [K]
(6,0)
v) d-1/3
jo
(/ (1,J) 2zkk - =x)
-(6 v) 0(/pollyoog(()
jo (.2) v),
where w 20 on both hand sides refer to the weights w (t-0) after steps inner-loop updates using samples from Sk-
(t.J)
Lemma F.6. Under Condition D.1 and Condition 4.1 for any (-1,11, [m], and k E [K],
if we are using the samples from Sy. then for any 2 we have
j(w (t.3) v) < 2 max {A)) .J7)
Proof. Without loss of generality, consider j = 1. Let E [m] and & E [K]. Using samples from ST by Eq. we have
(1.7+1) 1,r v) S (wi,r 1/ +
(1,7)
for any T E [J- - 1]. where we have used the fact that (-( S and d'()) S 1. Repeating times get
(w 1) S (wl. w) + Jr S (0) + Jy S max {A J7).
(t.0)
F.1 PHASE I
Let T7(2) be the first iteration such that A 2 m 11/2 (1 + +-)-²= =(1) and let 7 = .max, T Without loss of generality, let us assume that (2) < (2(2)
Recall that we assumed 7/2) T
Lemma F.7 (Restatement of Lemma 6. Under Condition D. and Condition 4.7
if one uses the
vrain-validation method, then for any S T(2),
1. For any k E [K] and r = arg max (w 1,r"
((t)))) Mx) = 2(1 (1.0) ()
For any r E [m], (ks i) E v, and j (-1,11}
(w))))) (...)) S <0( max (w Ex.)), c))
The proof of the first part relies on the following hypothesis which we will verify inductively later.
Proof.
k, = (1). for all r E [J]. & E [K], i E [n] such that Uk. = 1. (t.T)
(F.5)
o'(WW (t.r vx)) = (w (t.)) uk), for all E [J]. & E [K] if (w Wi .k) > 0.
(t.r)
(F.6)
C.5), we know (w (wl.? mn) is increasing in T for any E [m]] and E [K]. Moreover, we By Eq.
have
(witt (1+1.0) Ux) = (w iir vk)
(1.U)
7
Σ
(a.) K
o' ((w (t,)) pw) uw)
Kn (N.))
which shows that (t,0) 1rr
2k) is increasing in for all r E [m], k E [K], since (ux, Ux) = -|112 112 + 11 shows that (w v) is increasing in L for all [m]. Let r()
(Zs, Zee > 0. And Eq.
arg max)e[m] (w]))) v). Recall that under Lemma D.2 we have (w (w v) = P(To) > 0. Since
this is increasing in t, we have
(w.C (t.0) 1.r(e)* p) 2 1.r00 2) 2 (w (0.0)
1.r(o)= v) 0,
40

---

Published as a conference paper at ICLR 2023
where the first inequality is by definition of r(t). By Lemma F.1 we have for any & [K],
(w (1.0)
i.((t): mx) = (w).r()) v) + (Wir(()) zu) 2 (1 - ((1)) (1.0)
(2.0)
v) > 0.
And by monotonicity in J, we have (w (w)r()) Mx) 0 for all T E [.] From Eq. (.5 compute
(t,7)
we can
(w (17+1) 1r(()) vn) - ((()
(ll o ((w va)) |
(t.)
1r((t) p2) n1 imn.
= =w((r()) 1/2) + 71) (,r(s)) Ux)
= (w(lir)
I,(())) )x) + (11)).
where we have used Hypothesis F.5 F.6 and ||uxl12 (1) to get the second line. Applying this repeatedly to get
(w((.)) Lo(t)s vx) = (w (t,0)
(,((t)) uz) + ((1)) (1.0)
= 2(1 1.r()) (1 + +(1))',
(F.7
where we have used Lemma F. to get the second equality. This proves the first part of the lemma. Consider some (k E V. Without loss of generality we will prove the second part of the lemma for j = 1, since the proof for j = -1 is the same. By Eq. (C.3). for any r E [m]] we have
(wir
(1+++) Ek,)) S (w (w1.? (n.) + (0() (og(o)))
where we used -(() S 1, o.) < and Lemma D.2
This implies
(w.). -v.,) S (w Ex.i) + (100()00002
< 0 max (w/,, sx..). c))
(F.8)
The second inequality is by definition of C. This proves the second part of the lemma.
Remark F88. Eq. F.8 is not surprising result. Since Ex.i comes from the validation set and the inner-loop updates only uses samples from the training set, we expect that after J steps of inner-loop updates, the inner product should remain as the same order as before the J steps inner-loop updates.
Theorem F99 (Restatement of Lemma 6.3 T(2), (k. i) V. train-validation method, then for any
Under Condition D. and Condition 4.1 if one uses the
(0) R,
0(1 0 Ö(2-112). <
And
(0) R,
(0) k, Od2-1/2). < 0(1)
Proof. We will only prove our first statement that involves
k because the proof of the second
statement that involves (()) will be exactly the same.
Similar to the proof of Theorem E.2 we will give lower bound on the growth of A (t) and upper
bound on the growth of (*)
k.z" We can upper bound the growth of A
(t) using Lemma F.7 We first
note that since (w (t.J)
(wir(() vx) >
O. we have (wir((): uk) < 0. Thus, if (k. E T we have -(w(lr)
a' (((w((t.)) Trrg mx)UN,)) = O. Then by Eq. C.I1). we get
A (++1) (w (Wir(() 2) = Knz (K.
((+1.)
"
Σ
(i (t.))
k. ow vK)UEN)
(Wi(e)) v)
(t.0)
Kna (K.i)E__
"
Σ
ki
(0- ((1)(W
(W)) (IO))
41

---

Published as a conference paper at ICLR 2023
(t.0) (Wirt +)) +x Ir()) 4)
(1,0)
(w(..) 1,(0)) 2) +(()mm))
(1++2(()))7))
(F.9)
where we used o'(( (t,J)
((.))
1.r(t) 2x sk.s) = 0 if (k, i) E V_, and Hypothesis R.5 F.6 to get the second
equality. We used Lemma F.7 to get the third equality. Next, let (k, E V and [m]] We will
derive an upper bound on the growth of ( By Eq. (C.9 we have
1++1.00 (w)) Wir Ek.e)
(w(rr) (1,0)
EK,)
E
Knz (E
+ nd
Knz (dw((w,))) (t,)) {e.
(wirr Ekx) + ( Vd Voggo + " (w).""
Knz
S (w(r Ex,) + 1 Vo
7 ( max {(ml) Ex.)) c)).
(F.10)
Kna
where we used --(()) I and o'(+) I and Lemma D.2 in the first inequality.
We used
dxx)) < |/2|| for any x R get the second inequality. And used Lemma F.7 to get the last inequality. Abusing notation, let r(t) = arg max/e(m) (wi.
(1.0) Ex.u). By definition,
we have [0 (w iir(f) Es.i). Let us compare the size of the second and third term on the
(1.0)
right hand side of Eq. (F.00. The third term outweighs the second term at least by a factor of ((Jrood/(KKn)) = log(d)o. due to the presence of the constant C' in the third term. Therefore, k,
the second term dominated by the third term for all r E [m]] and for all 2 O. So Eq. (..0 becomes
(++1,0) Ek.e) S (w((,0) Ek.s) Knz (wi,r
7
((d2))o max { (Iw1.. (1.0) .E.)..))
(wi,r))
(1.0) EE.,), Cm.)).) Knz Knz
7 20 max (w (1,0)
, c})
I max
{=(0) k c) + " ((o max (=(..C)
< max
Knz
nopd
()) ki
(1 + (1)
Kn2
Since the above inequality holds for all r E [m] on the left hand side, it holds for r(t + 1) in particular. This gives
yood Kn
0 (1))
And it straightforward check by definition of k.s
(t) that
goad Kn
(1+1)
1 1 (1)
(F.11)
We are now ready to prove our theorem. Compare Eq. (T()))
F.9 and Eq.
F.1
we can use Lemma
D.5
to get an upper bound on k.
We take A = 221)mrm)))))) B = O(1)
G 2, D = m 1/22-
Kng
in Lemma D.5 We see that since A (dd11/2 A-A/B = 2 log(d)+. under Condition D.1
Lemma D.5 tells us that
(2) k,i < (
This proves our main theorem.
It remains to verify our previous hypothesis. Note that if we suppose all of our hypothesis hold at time < (22), then Theorem F99 implies that for all (k, v have @((+1) ((+1)
(() By
Lemma D.2 it is clear that Hypothesis E33 and hold initialization.
42

---

Published as a conference paper at ICLR 2023
Proof of Hypothesis F.5 The proof will be similar the proof of Hypothesis E.2 Let io E ? [n]] such that yk
[K]
and
Recall Eq. (C.7) and that
Σ F=
(o((m)r (t) Ek.1)) +o to (w1,),,7) vxl))
(o(iw( (1 (a,i)) + a( ((ww(etlr)
mx)))
(F.12)
r=1
Assume our Hypothesis hold at time t. We have
m
m Ek,)))
Σ
((w,,
(++1.)
σ (= ())
mo (O
= =(1)
(F.13)
where the first incquality is by definition (+++)) ki
and the second incquality is because ( <
kg
( The third equality is because m = polylog(d) and (O(( = O(d-1). For any
E [m]. we have
(1-1,0) 1,r
vn) = =(w].t (w((+1.0)
v) + (f+1.0) Za) 1rr
(
S A ((+1)
+ max
1ir'" rEmm
(c+1.0)
zkk
< (0(1)(((1)
$ 0(1A) (T
0(m 1/2(1 + +))
where the second line is by definition of A ((+1) The third line is by Lemma R1 The fourth line is because / ++1 < T(2) and A is increasing in l. The last line is by definition (2)) Thus
Σ
(t+l.) Co(ww
Fr vK) S m O(m 1/2 112 + - o(1)
(F.14)
Combining Eq.
C.7 Eq.
Eq. F.I3) and Eq. (F.14), we have
(101 (o((1) o(1) 2(1).
R2
Now, suppose that
R.s
((+,))
2(1) for some 0 < J-1 We wish to show that
k,
(041,7+1)
we know that for i > n1, we have 2(1). By Eq. (F.
(+11.+1)
En.i) S 0 max (wirr (ka).
(1+1.0)
(wirr
< 0
max
(=(11)
(1+1)
kii
cc)
(S(++)
k.j
where the second and third line are by definition of (++1)
and
ki respectively. This gives
k.
m
(++1,7+1)
Ex.e))
a (O k
))))
$ mo mo (
o(1),
(F.15)
43

---

Published as a conference paper at ICLR 2023
where the second inequality is because bound
k,
(t-1)
0( if [ni]. then by Eq. C.4 we can
(w 1,r
Ex,i) S (wir (1 (v,) + + + - o (111)) .k,)))
$ kwiz (1-1))) Ek.N)) (1+ + ( V dy log log(Kn)
I max (w ( c1.
where we used- -f()) < 1 and o') < 1 and Lemma D.2 in the first inequality. And we used a'xx) S 2 a| for any x E R to get the second inequality. This implies
max [[ E..)).C) I max
[wwft (++1,
[w
(1+1.0) Ex C (1 (1+c((d)))) T+1
< max
(1 (1+70
< o (0)
(1 + ((ofd(m)) 7+1
O(d 1/2),
where the third line is by definition of ((+1) The fourth line is because
(1+1) (()))) And
the last equality is by direct calculation. Thus
(++,++1) Ek,x) I max [[ (1+1,+1)
c..)l.c3 1/2 10(
This gives
(+11)+1) (xiil) S o (o(d-1/2)) = m
(0(d-1/2) (00)))))=m-(((())))) =0))
Using Eq.
C.5 have
(w (++1,++1)
vk) I (wi,r Ua) + 17 (1 (+1,7)
(++1,7)
mx
(wi,r Mk (1++0(1))
(1+1,7)
(wi, M1) (1+0(1))))
(1+1.0)
(w((+.00)
m1) (1++@()))
S O(m 1/2 (1++))))++++00)))))
O0 1/2),
(F.16)
where we used (')) 1, (x) < 2|xr| for any x E RR and | 1l (11) in the first inequality. The fifth inequality is by 1+1 111T7 (2) and the definition of (2), Then we have
Σ
a (+1,++1) mb) S m O(m-1)=-=))--- = 0(1.
(F.17)
1,
The inequality is because a (0(m -1/2)) = 0(m Combining Eq. and Eq. (.177) obtain
C.7
Eq.
(.12), Eq.
F.
((+1T++1 -0(()) oo1) 22())
This proves the hypothesis.
Proof of Hypothesis F.6
By Eq. F.16), we have that ((+1,T) vx) O(m-1/2). Thus if
((+1,r) Ux) 0, then
o ((w(tt2.)) vx)) 2 2(w(142.7) Un).
by definition of o((-)
44

---

Published as a conference paper at ICLR 2023
F.2 PHASE II
We have shown that when the feature inner product has grown to ( the noise inner products remain ((d-1/2), which exactly the opposite of Theorem E.2 Next we will show that this
difference is maintained at least when (1) has grown to Ollog( (f) For (k, i) E M, let
max max ((wle Wa.. Ek,e) 1/3 rE(m)
R =
And
R
max
max rE[m]
{
(w (( maiirr Sk..)).
Let 7,, (7 be the first iteration such that A
log(d)o.1 Let max {T_21 And recall
T = (oly(d) is the total number of iterations. We first present two claims under Condition D. and Condition 4.1
Claim F.10. For any t 2 T(2), any (k, i) E V, we have ((() - ((d-1/3).
Claim F.1. For any t $ T (k, i) E V we have (() k, - Od-1//4)
Remark F.12. Under Claim
F.10 it holds that [
(K, (1) S for all (k, i), (K' 17) E V.
Remark F.13. By Theorem holds for all $ T
E9 Claim F10 holds at time T Also by Theorem F9 Claim F.11
Note that from Eq. 1.111. the growth of j(w
(t,0) .2) depends on the size of j(w (t.J) m2)- We first
need a lemma that can gives lower bound on j(w (t.J) (or" .n) fort 2 T(2), The following lemma will be of a similar form to Lemma[E.
(1.0) v). Assume Claim F.11 Lemma F.14. For any T: 2 212 T(2), let r(1) = arg wiggmx, [[mm (w holds, then j (t.J) jr((y) px) 2 22m ) for any E [K].
Proof. For simplicity, take j = 1. We shall see that our proof does not depend on the choice of j and thus taking j = 1 is not loss of generality. By Eq. C.5 we know that (w
(w(trr) (t.r)
1r(()) ux) is an increasing
function of r. Thus if (w (.r(t)) px) = (0m=1/2), then we must have (w (,r()) vK) 2 22mm (mmm-112).
(t,0)
(t,J)
By Eq. C.11 and the definition of r()), we also have that (w(+.0) v) is increasing function in
t. By definition of T22), for any t 2 T(2), ,, holds that (w (1.0)
(Wirr(0) v) 2 m 1/2 (17111 +)) Then by
(t.0) Lemma R.2 we have (w (i)(())) mx) 2 ((1) (11))mmm12(1111 112 It suffices to prove that if
m
1/2 (1 + 7) v (w (1.0)
(i)((t)) vx) S m 1/2 (1))
(F.18)
for 7 [J], then (w((.)) (ir())) Mx) 2 Q(m 1 Let us suppose that F.18 true for some т. Under
(t.J)
our assumption that E(t) I (dd-1/4) we can apply the same proof as Hypothesis F.5 to get that
k.
-elt ((,7' 2(( for any T' E [r]. Then using the same derivation of Eq. F.7 we obtain
(t.)) 1ir0 px) ((1) 1.roo v) (1+0()))) 2
(1.0)
2(1)m 1/2
This concludes the lemma
The next lemma shows that as long as the noise vectors have not been learnt well by our network, the loss from different samples are essentially due to the feature and hence are of similar sizes.
Lemma F.15. Let {-1,1}. Under Condition D.I and Condition 4.1 while 5 < (dd11/4)
and ( < O(d (ddd-1/2)rr for all (ks i) E Vj, and mo m dA ( < O(1), we have ((..J) ((1) if k.s
(k1, i1), (k2, iz) E V
45

---

Published as a conference paper at ICLR 2023
Proof. Without loss of generality, assume yki.i of Hypothesis F.5 to get that
0k2.,5 =j 1.
We can essentially use the proof
Σ ((w
(t,)) 1,r (Stgttg)== - o(1) o(1);
(F.19a)
Σ ((w ((.)))
-1,03 (haree)) o(1)
(F.19b)
for q {1,2}. Moreover, since j(w (w v)) is increasing in t and for any E {-1,1),r (1.))
[m]. k [K]. get that (w -Irr 2x) S (w (0.0) mk) Odd-1/3). This implies
(t.)) - (,,)) (m))) o(1,,
for q E {1,2). By Eq. (C.7p it suffices to show that
(1.J) Σ a((wi, 1. (k,))) - o((w], 1r
(1,5) Mmal)) s O(1).
We divide the weights into two sets. Let G fr E [m]]
(w1) v) 2 d d and H = fr
[m] r & G}. Let us first consider r E g. By Corollary
F.5
we have that
(w) (w( Ze.) (
(t.J)
for q (1,2), which implies
(t.)) (Kxe) = (1+ 1rr
(1.)) v).
Moreover, by Lemma F.6 we get
(t..)) MKx) S (w(( : v) + d) max (A
(0) JJ7].
By a direct calculation, we have mo,dJy = d()) and by assumption mo (1) < (1). We can then calculate
Σo((m (kxk))
(t.J)
v
((w 1,r D)
(1
max (0) J7]) (A}))
reg
rEg
Σ a((w 1)) + Σ (11)0(o) max (A J7}
<
rEg
r
a((w
1.r v)) mO max {A J7]
(1.J)
rEg
Σ
a(( ((w 1,r 1)) + O())
(t,J)
(F.20)
rEg
where in the second line we used ol + E) I oxx) + O(1) for E 2 0. The third line is due to
| S m. Ifr E H. then by Lemma F33 we have (t.)) Zx.)) ) < 1/13
1/3, Then by Eq. (C.5) we have
(w (w((rrt)) (t.++)) pk s [(
(trr) vK, (1 0(1)))
for E [J- - 1]. Hence
(mr( vkxa) S (1.00 vk (1+
(1.0)
( 1/3).
(F.21)
Combining the above results, we finally have
m
Σ a(( (.r
(t.J) vx,))
Σ
Ca((w(()) (kk))) + Σ (a((w(y)) 1,r Mk,))
reg
reH
46

---

Published as a conference paper at ICLR 2023
Σ
a(w
(1.) 0(1) Σ (o(o(d-1/3) 1/3)
1r
rEB
(2)) 0()) + mo (O(d111)))
rEG
Σ Co((
1.7 0
(t.))
rEG
Σ a(w
1. /)) O (t.J)
(F:22)
rEg
where the second line is due to Eq. get
F:20
and Eq. F.21
Since the above holds for q E {1,2),
Σ ((w (t))
vk))) o((w),r) (1..)) vx.)))
s 0(1)) -
And using Eq.
C.7
we conclude that ky = =(1)
Lemma F.16.
Under Claim F.11 for any < TT we have - p((t,)) w for all (k, i) E V.
h
Proof. Without loss of generality, let consider 1. Let (k v... By Eq. C.7 Eq. F.19 and Eq. (.22 we have that
(t.J) k,
2 - Σ
ol(w (Aw)) 22) +
TEG
2 l' Σ
((w
( 1r
,)))
re(m]
where in the first line g = (r E [m]
(wirr))
(t.0)
.) 2 d--/d/1 1/3]. Then recall that s 7 implies
A log(d)o.1. Using Lemma F.6 we have that for all r E [m]
(wirr"
(t.J) i,r ./) < 2 max log(d))1 ,Jy} = 2Jy
Then by direct calculation using Condition D.I we get
((o,)) 2 -e' (mO(()))) 0(1))
= 1/66)
Remark F.17. The -1/8 factor on d can be replaced by any < 0. We choose - -1/8 for convenience in the later proof.
Proof of Claim E.I Consider (2) < t S T(3) Let 3 max ( (ks, V+}. By
Eq. F.8 and the definition of have that for any (k, v
((w (.)) (x,,)) < (1) < (1)
(F.23)
And if (k) E V_,,
= o' d'(ww (t.J) Ex.))) < -
(F.24)
where we note the second inequality Remark 1:12 It convenient to define
((,)))
Σ
(t.J)
/ /|v+l k.
(k.))E++
47

---

Published as a conference paper at ICLR 2023
because by Lemma F.15 ((.))
0())((00)) for all (k; E v4 Then by our assumption that F.16 we have that (tte.)) w(d By Eq. (C.9 we have that for any
t I T and Lemma
r E [m], and (k, E 4+
(w) 1rr
(++1))
Ev.a) I (w(r
(t.0) Ek.R)
Knz
7
E
1,,"
d' ( Ev (og(KK))
7
(11)
o' ((w Ex,)) (((
Knz
10 Vd
n0? d
500 θ
E (KGMEW
(t.)) Evr,)) ,,, 0
Knz
Kn²
10 Vd
5())
((.)) Wi o' ((wi.) (
Knz
(KAY)E
no Vdl Knz
Wiy of (1.)) (v(w)) , - -0( ( no0dd
e ((())))))))
Knz
(KI
no Vd
Σ
Knz
(KY))
!o vo
Σ
(1)
θ
g
J).
Kn2
Kn2
(KAP))
nooe
< < (ō(d- 1/2) +
((())) + old 1/2 )
Knz
3 (1 θ n
((()))) + old 1/2))
Knz
r el
(8) 1 A
elit..)).
Knz
where we used Eq. F.23 to get the second inequality. We used Eq. (F233 and Eq. (F24 to get
yooa ((t.J) = 0 (d 1/8) > o(d (dd-1/1
the fourth inequality. The last equality is because - Knz
And maximizing the left hand side over r E [m]] and (k) E + we get
n ((w)))
E((+))
E(0 (1) (1 θ
(F:25)
Knn
By Theorem F.9 we have that 6 (T d 1/3 Let T' be the first iteration such that
-(TT) 2 d 1/4
Then, using Eq. F.25
we get
nond
B(T) <E(T' (1
(T"
-1,11
Kin
n d
I <d'1/4 (1
E
((T)
Knz
nord
S 2/ + θ
Knn
1/4-1/4)
where the second inequality is by definition of T'. The third inequality is due to -f(-) < 1. We have
T' II
θ n0 Knz
1-1/1 d'1/1 E(T))
(1
e((t.)))
t= T(2)
48

---

Published as a conference paper at ICLR 2023
T-1
nood
d d-1/4/d-1/3 2
II
(1
θ
e(ec.))
Kin
T(2)
T
n
((log(d)) 5
log 1 θ
p((.)))
Knn
T(3)
T -0(1)
no
((().))
Kno
(=
2 log(d) Kn no
T
(F.26)
(=
where we get the third inequality by taking the logarithm of the second inequality. In the fourth
inequality, we used log(1 + x:) S ((1)x for x E [0, 1). By the second line of Eq. (F.9) we have
A (++1) 2 A
Σ
((t. M.
Kng
(K.))E
A
(( 1/2).
To get the second inequality, Summing over t, we obtain
Lemma F.15 and absorb all the constants into
T:
log(d) 2 (T,
(T(2)
nl
(=
T -2
log(d)o.1
Σ
n/1
(mmm 11/2)
(t,w))
(=
TT-1_2
0 log(d)011
Vm
(t,J)
7
(=
o log (d) / +
((,J))
(F.27)
"
(=7(2)
We used -.(--) S to get the last inequality. By a direct computation, we have
log(d)o.1 vm + log(d) + o(1) log(d)Kng
o(1) log(d)o.5
bood
"
F.27 we conclude that T(3) < T - and hence (k, E - J. If we redefine T" be the first iteration such that (T") d 1/4 then using the exactly same argument, we obtain T:(3) < T". This proves Claim.
Combining this fact with Eq. F.26
and Eq.
2:(3) T". Now let -00 max
Theorem E.18 (Restatement of Lemma 6.5). Under Claim F.10 we have ( < T.
Proof. We will only prove T (3 T, since the proof of ( < T will be the same. For the sake of
contradiction, let us assume that (3) 2 T. Then, for t < T. we have that A < log(d)).1. From
the proof of Lemma F616 we have
((t k.
2 - (m0(1n)++(())) 2 (x)))xxp(
for all (k, E V By the second line of Eq. F9
A (++1)
A Kna (K.0)E
E
{(1)0((mmm)))1
49

---

Published as a conference paper at ICLR 2023
A
(0) "
)
Knz
(k.1)EV+
1 + +0())rex((--(bo(()0)0))
This implies
T-1
A A
(T
+
Σ
0(1)gep) 1/2
t=
+ (u00===~~--)"""))pee-oooodd(//) 1/2
2 poly(d)s(11)exp(( exp( 100x0/9tt0)eoo000000000000001111
(dpoly(d))
where the second inequality is by definition of T(2)_ The third inequality is because = poly(d), ((2) = polylog(d), " = (polylog(d)) and m = polylog(d). And (ppoly(d)). But this is contradiction since assumed T < T which means A (7) I log(d)o.1 Thus, we must have > T And the proof of T T the same. This proves our theorem. This will be useful for convergence result later.
poly(d) exp())xp(p00)) (xg((O(log(d))m))
Theorem F.18 implies that before training ends, feature will be memorized by the neurons with an inner product of size at least log(d)0.1 As shall see later, this already guarantees small test loss. Our next theorem makes sure that the feature inner product will not grow too big by the end of the training.
Theorem F.19. Under Claim F.10 we have A,T) S 2 for j E (-1.1).
Proof. Without loss of generality, let j = 1. Let 1' be the first iteration such that A log(d)=1
Let r(f) = arg [[m] {(w(.r (1.0) .)). Using Eq.
CC.11 we have
(w (1+1,0)
(irr((+1): u) (w (t,0)
1
d'((w (t,J) ki (WIIr(+4) Uk) uk)yka.))
1,((++))
Knz
(K.))
< (w (t,0)
Σ
(L,J)
of d'((w
((Wr)()) vK)DEss
(t,J)
1.((t)
K
ki
(K.))
(w (t,0)
1r(t)) v)
Σ
(t..) of (t.J) kg
(Mir)) (1 vx))
Kin
(K.))EW)
$ (w.(0.))
(t.J)
K (K.))EW;
where the second line is by definition of rt)). We get the third line using the second line of Eq. F.9 We have used of o'(- < 1 to get the last line. By definition of r()), this means
(++1)
(t..)
Kno (K,))EW_
And by definition of i', we have
A 109 (t' 11-1)
7
Σ
(1.) kid
Knz
(
< log(d)": 1.1 +
< (1) ldg
where we have used -e((-) < to get the second inequality. Hence if T & t', then we are done.
So let suppose that T > 1'. Since Alt is increasing in f, we know that for all > 1. A >
50

---

Published as a conference paper at ICLR 2023
A 1 2 log(d)).1 By Corollary F.5 we have that (w (1.0)
( 2x)
(w) (..0) 1,((s)' v) for any &s E [K].
Moreover, for t 2
(w (wir(() pk) 2 (w Wir(( vx) ( (w (c.0)
(1,))
(t.0)
2) (1)AA e log(d))
By Eq. C.7 for (k: i) E + we have
((:,) b.
_ - (o((((( (1,3)
1.(()) Mx) Σ
(o((w (tJ)
-1,r Sk,i)) + a(w vx))))
S - l' (0(1) (o o(1)
= - (0((1 log(d"
s cxp ( O log(d)) (.) :
where the second inequality is due to Eq. (.19).
The last inequality is by property of the function
(.).. This implies
T
A Σ A 7
Σ
()
Kno := (
S ((1) log(d) + r1TO exp (1)
- (1) log(d)" 111 +0(1)
011 l
where the second last inequality is because nTT = (ppoly(d) p))/polllog(d)) = (ppoy((d) and
(pooy(dd) exp - (11 1og(d)=)))
- o(1). This proves our theorem.
Proof of Claim F.10 Suppose our claim holds for all E [T(2), T' - 1] where T I T. Then
by Theorem F.19 we have that A (T') S log(d) for j E {-1,1]. Let (k E V_.. Denote
r(t) = arg max, ma (w/,.") En,s). From Eq. (C.9), we get that
(wf, (.41.0) Ex,)) & (w,) (t.0) En.i) Knz (E.T)E
E
O00 log((n)
s (w1))) Ex.i) Knz (KPP)
Σ
dv log(Kn)
(w
(1.0) Ek.i) + (dd
Σ
(1.))
(F.28)
(WFY)V
where we also used Lemma D.2 in the first line. The third line is direct calculation using Condition D.I We have for f (2)
(++1) 2 A
n
Σ
(1))())(
1
Kn (K.))
R.1
A ē(1)
Σ
((.))
k.
(K.))E
where the first inequality is by definition of (2) and the monotonicity of A (0) And similarly
A (++1)
(9) Ō(1)
Σ
(t.J))
k,
(k.0)
Summing them up we obtain
A 1 +
[++1)
(++1)
2 A (t) + - 5(1) Σ
(.t) ki
(k.i)
51

---

Published as a conference paper at ICLR 2023
Summing over t we get
blog(d)123 2 ATT" + +A A (
(T')
A
( ((1)
Σ
t= T(2) (R.ieeV
T'
loggd)) -O(1)n
Σ
((,))
tT (k
T²
@(1) -1 Σ
((W)) ki
(F.29)
(= (k.))E
Plugging Eq. F.29
into Eq. F.28 we have
T
(T" 0) (wirr"
Ex.i) S (w 1,r Ex,) - 1/2-1/1)1
(T .0)
Σ
(W' (T .0) Ek,)) + O(d 1/2-1))))(1
(=
S (wi.r
O(d-1/2) 1/2) + 1/2
1(d-113),
where the third inequality is by Theorem F9
Since this relation holds for all [m]. we get that max (w(r" (T' .0) Ek,)) (dd-1/2). And hence (2") < (dd-1/2). This proves claim. n
Lemma F.20 (Restatement of Lemma 6.4
Let T poly(d) be the total number of iterations.
Under Condition D.I and Condition 4.1 we have
min
Σ (R.j)ED
O
EE(T(2) T
Tn
Proof. By Theorem F.19
we have A (T) < log(d)
1.2
for j E (-1,1). Using the same derivation of
Eq. F.29
have
Σ
nelle @())
(=T() (k.i)
And we can bound the minimum over by
min tE IT T
Σ
(t.
<
ki
(T - T())))))
TT
(K.))
where the second equality is because (2) polylog(d) o(1)T, and hence 7 ( ((1)..
Lastly, we have the following theorem for the convergence of training similar to Theorem E. Theorem F.21 (Restatement of Theorem (1)). Let poly(d) be the total number of iterations. Under Condition and Condition 4.1 we have
nvr (Wi))) < (1
min EE[T]
Proof. Denote (((,.)
(ll(all, J, i)). i.e. the argument of -
(t.J) ki
some function
al,, J, i). Then the training loss at time / is related to p(t,))) by
n--val (w())= Σ
(a(tt, J,k,
(k.))V
52

---

Published as a conference paper at ICLR 2023
Let L' arg min ?-1 1E (T3: Eiinev ((,)) By definition of (() and {(-) bound (x) 2
exp(-x)/2 2 f(x)/2 for x > O. This can be used to bound our loss by
min L (wit)) - Lavall (W)(t)) AE(T]
E ((a(t'
(K.))WW
< - E "(all'
(K.))
Tn
where the last inequality is by Lemma F.20 This proves our theorem.
Theorem F.22 (Restatement of Theorem 4.5 (2)). Let W W(T) be our trained weights using the
train-validation method. Then the test loss is small
Crest (W) o(1/polylog(d))
Proof. Sample new example from the distribution, since we use the convolutional structure, assume that the first patch x(!) y (v + z) and the second patch x(2) Clearly
(Ex,i,)) t) follows the Gaussian distribution with mean zero and standard deviation og ||Ex,i/12. By Lemma D.2 we further know that [|Ex,ill2 20 vd. Therefore
P(ICE,, 2) 2 d 1/4) 2exp (- 80//3/2
22exp(-d'/3
(F.30)
Similarly we have that
((((W (0.0) jor E)) 2222) S eex
< 2exp(_dd14)
(F.1))
80
Denote to be the event that (Ex, 4) S d and (ww for E)
(0.0)
S 3/2 for all [K], E [n],
[m] and j E [-1,1]. Applying union bound, we have that the P(E)= > 1 - 2(nn(n + m) exp(-d)14 We can divide Lrest (W) into two parts:
Lrest (W) = 1E (WVff x)) =
(F322)
In the following, we bound I and 1z respectively.
Bounding 1,: When event & holds, for any j E (-1,1), we have
T-1
(T.0) .
(w.
(0.0) J.r
(.s)) o ki
((w (.D)
(E.
Kn
t= (K.))
(0,0) (w
-E)
(t.J) o' ((wlii") ((.lli))). (dus))d-1/4
K t= (K.j)
(0,0)
(L,J) k,i
1 1/4
. Knz
Jr
= (K.))
Ijd nd--1/ 1/4 T(2)_
nd 1/4 T-1
(w jrr
(0.0)
(E)
(1.J)
Σ
Kn t=
kj
Knz
(RAjEV
(=
(R.))V
7d-
(w.00 (0.0)
-) + nd 1/47(2)
O(1)
Knz
53

---

Published as a conference paper at ICLR 2023
(w . + (1-21/4) +((-v)) Odd
10.0)
((d
(F.33)
where the second line by Eq. (.30). The third line is by (') S 1. The third last line is due to (-) I 1, ( = polylog( d) and -t=r(a) EjK.ee ((,J) (1) (recall Eq. (.29.). The
ki second last line is by Eq. (F.31). We note that Eq. (F.33 holds for all { (-1,1), E [m], and
y E (-1,1). Now without loss of generality we assume = 1. Then,
F-1(W-1,88
o
(2:00
1 + 2)) + aa (2.0)
(I.r E))
(2,0) o(w -1, v + z)) + mo (O 1/4))
m
Σ
allw -1, + z)) mo (od
(0,0)
m
ao((d11/1) + mo (o(d
1=1
< log 2,
where the second line is by Lemma Eq. (F.3)), the third line is by monotonicity of j (1.0) i j(w (t.0). (t.0) for .x) in t, the fourth line is by Lemma D.2
jr 2) and
Thus
(us(W, =
FW W (1,,,) -FF.x)))- (-I(W-1,x))
21
((w 1,r v + F-I
(T.D)
(T) F-1 (-1(W11)))
(A((T)))) -F-1(W
K log(d))u11 - log
< 2exp (- logg(d)).))
where the second and the third line are due to the fact that o(.) 2 O, the fourth line is by Theorem F.18 the fifth line is by definition of 7(3), the last line is by log(1 + x)) S x, Var 2 O. Therefore we have that
< exxp ( (- log(
(F.34)
Bounding Iz: Next we bound the second term Iz. When event E holds, for any j E (-1,1), have
T-1
(T.0) .E) = -(w
(0.0) (0.0)
J.r
.
Knz
(()))
R3 jo
(l (t.))
(E, En.s)
t=0 (k.))w
T-1
(w.0.0) (0.0)
. Knz 1=0 (k.))W
(lt,)) o' ((w (1.))
T-1
< (w j.
(0.0)
.E) Kna t=0 (k.))e
((, ((1(112)
54

---

Published as a conference paper at ICLR 2023
(w (0.0)
jr . Knz
(1((l))
--
Σ
(a.J)
Σ
T-1
Knz
(k.))EW
(= (k
(0.0) (w 3r .8) + =1(((((122)T + (1((1))
Kn2
(w3r . O(1Ell2) 0(11(112)
(0.0)
O(1E6l2)
(F.35)
where the second line by (c, Ex.a) 1 ||x.,||2|||||2 ((1
The third line is by o+) S
1. The third last line is due to - (-) - 1,7 = polylog(d) d) and Σi E(K.jew k,i
((t
O1)
(recall Eq. (F229). The second last line is by (( (0.0) E) I || j.r
(0.0) 1|2111122 (11 We note
that Eq. F.33) holds for all j {1,,1), E [m], and y {-1,1}. Now again without loss of generality we assume = and have that
F (W 1,1) =
(T.0) a -1, 1 v 2)) + <(w
(T.0) (2.0) -1,
(1..) E))
(T.0) -1, 1 2)) mo (((E(l
(0.0) o -1, + z)) + (0(1((())))
((1
where the second line is by Eq. F.35 (l (2,0) jor 2) in l. The fourth line is by Lemma D.2 Thus
The third line is by monotonicity of (( v) and
(yf(W.x)) x)) = 1 F+1 F+1 x1, F-1 F-1
< 1 - F-1(W-11x))
= loog(1 + exp(F (F (W-(
< 1 F-1 (W -1,x)
2 (1())),
(F.36)
where the second line is due to the fact that (-)) > 0, the fourth line is by by the property of cross-entropy loss, i.c., log(1 + exp(x)) & 1 + x for all x 2 O. Then we further have that
1 W v [[](ET)] VE [E(((s(W.x))'
S VP(E)) V (())
S v O(poly (d)) (x)) exp(-dt/4)
= Opoly (d)) exp( ( 0.5d
where the first inequality is by Cauchy-Schwarde inequality. The second inequality is by Eq. (F36).
The third inequality is by the fact that v O(1) < ((poly(d)). Plugging the bounds of I, Iz into Eq. (F.22 gives that
Crest () < 2 - 111 + O(poly(d))exp(-0.55'" = @(exp ( (o)())).1))
which completes the proof.
55

---

Published as a conference paper at ICLR 2023
G AUXILIARY LEMMA
Lemma G.1 (Restatement of Lemma B.2 from Cao et (2022)
Suppose that 0 and
2 log(4Kn/o)). Then with probability at least 1
2 0 S |5R.ill2 S 2 5
1
2d
(5 EM & 202 log (4(Kn)2/6).
for all k E [K] and i, E [n]] with (k. + (K,z'.
Lemma G.2 (Restatement of Lemma B.3 from Cao et al. 2022 Suppose that ò 0, d (log(mKk/00) and m = ((log(166)) Then with probability at least 1
(w/0 2)) S v /2lg(8mm6))og
(0.0) 1( jr Ek.il S
for all r E [m], E 1-,, h E [K] and i E [m]. Moreover,
2 < max j j(w j.r u) & /2log(8m/00oo.
(0,0)
2
rE|m]
Vd
< max (w (0.0)
rE[m] jr Ev.)) /21lo((mmkn/00)noggg
4
for all jE {-1,1), [K] and i in].
56


Reviews:
[{"review_id": "x6I2JLotoSU", "reviewer": "Reviewer_kJcp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes the train-validation split in meta-learning for classification problems with a two-layer CNN model. It proves that the train-validation split is necessary to learn a good prior model compared with a train-train model. Experiments justify the theoretical claims.", "summary_of_the_review": "Based on the novelty and strengths discussed above, I am close to an acceptation of the paper.", "strength_and_weaknesses": "Strength:\n- There is few research work studying train-validation split of meta-learning with neural networks, so it is great to have such work targeting on the theoretical foundations.\n- The theoretical analyses seem to be solid but I have not checked the proof details.\n\nWeakness:\n- What does it mean by \"FOMAML\" (first appears at Page 2)? It seems no where the term is introduced.\n- There is a little gap between the theories and the experiments, namely it would be great to have some synthetic data and experiments to meet the theoretical assumptions and to see how it matches to the theoretical claims. For example, we can generate synthetic data by Definition 3.2, then we can use a two-layer CNN described in the theoretical analysis as the backbones. To verify Thm 4.4 and 4.5, we can set different values of $d$ in synthetic data and to confirm the training loss is at the order of O(1/poly(d)) as claimed in the theorems. Similarly for the test loss, we want to see a figure plotting the test loss evolution, where train-train test loss converges to some constant while train-validation test loss continues to decrease. I think the theories and experiments can be more closely connected in this way.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h7dgnQPvKN", "reviewer": "Reviewer_SqBj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a theoretical results of FOMAML that shows train-train and train-validation methods can achieve a small training loss. It is necessary to perform a train-validation split in the task data to get good generalization results. Compared to previous work that only studies linear models . This paper advances the results to two-layer convolutional networks.\n", "summary_of_the_review": "This paper proposes a theoretical results of FOMAML that shows train-train and train-validation methods can achieve a small training loss. The results advance previous results and provide a deeper understanding of meta-learning. ", "strength_and_weaknesses": "**Strength**:\n\n* This paper presents theoretical results of FOMAML and advances previous results to convolutional neural networks. \n\n* The paper is well-written\n\n**Weakness**:\n\n* Does the theoretical results or analysis also applicable for second-order MAML, implicit MAML[1], closed-form solver[2], etc?\n\n\n* If the number of samples is large, how do the theoretical results change with different numbers of samples? In this case, does train-validation still better train-train meta learning?\n\n\n* How does the results compare to Reptile[3], which does not need a train-validation split.\n\nReferences;\n\n[1] Meta-Learning with Implicit Gradients. NeurIPS 2019\n\n[2] Meta-learning with differentiable closed-form solvers. ICLR 2019\n\n[3] On First-Order Meta-Learning Algorithms\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bn-OamvV7d", "reviewer": "Reviewer_7Hwe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, authors provide a theoretical analysis regarding the usage of training data only during episodic training in a meta-learning setup against train each episode using train and compute the loss on a validation split to propagate back through the network. The second strategy is commonly used by practitioners, however, some existing relevant work argue that it might not be required. In this work, authors show that using a train-val split strategy can achieve lower test loss in a meta-learning setup (when used with a two-layer convolutional network and first-order MAML as the meta-learning algorithm).", "summary_of_the_review": "The paper is well-written, analyzes an important implementation details from the meta-learning literature from a theoretical viewpoint and provides bounds which show that train-val is a better strategy for the model to generalize as opposed to train-train which is the common practice in the literature. However, the empirical and theoretical results are in conflict with the previous work from Bai et al. which casts doubts about the contributions of this paper.\n\nI'll be willing to modify my score if authors can clarify my confusion about the results from Bai et al.", "strength_and_weaknesses": "**Strengths**\n\n* The idea of training using a train split and back-propagating using the loss on the validation split has been a longstanding practice in the meta-learning literature - however, there has not been a lot of interest in analyzing that, either empirically of theoretically. Only existing work on this is from [Bai et al.](https://arxiv.org/pdf/2010.05843.pdf) which the authors discuss here. Theoretically analyzing whether train-val split is needed for meta-learning is an important topic.\n* Most of the assumptions made in terms of proving the bounds make sense to me. Authors use a Huberized-ReLU instead of a normal ReLU to simplify the proof and show that empirically it does not make much difference. I have not looked at the derivation in details provided in the appendix - the lemmas stated in the main manuscript makes sense to me at a high-level. \n* Authors perform experiments using synthetic datasets and also using a two-layer network on standard datasets like Mini-ImageNet which corroborates their theoretical findings.\n\n**Weakness**\n\nFor me, the biggest weakness or doubt about this paper that I have in mind is how well these results will extrapolate to other type of networks or networks with more layers. There is a discrepancy in terms of findings between this work and Bai et al. where Bai et al. claimed train-train split is enough with a linearized network and this work claims that their hypothesis is not valid when using a two-layer convolutional network. However, the empirical results of Bai et al. speaks a different story - if we see their Table 1 (page 11), they experiment with the same convolutional backbone as this paper on Mini-ImageNet and Tiered-ImageNet and show that train-train works equal or better compared to train-val, which contradicts the claims made in this paper. \n\nAlong the same line, my other question is - is there any guarantee that claims made in this paper will hold true for a different kind of architecture e.g. vision transformers or if we simply increase the number of layers in the convolutional network/add a normalization layer/add a residual connection? If these networks are too complicated to be analyzed theoretically, I think some empirical evaluation using train/train vs train/val strategy will help to justify the claims made in this paper. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "CqVnr7NDAz", "reviewer": "Reviewer_YDGh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors conduct an investigation into the importance of having train-validation sets for episodic few-shot learning, learned by meta-learning. They do as such by both theoretical proofs and empirical evaluation. \n\nWhile the intuitions behind having a train - validation set for meta-learning are quite clear and reasonable, this is a very good complementary study that showcases that the intuitions do in fact measure up to reality. ", "summary_of_the_review": "I recommended a weak reject due to the writing quality being problematic enough to cause precision and clarity issues in the work. If that is improved, I'd be happy to accept this paper.", "strength_and_weaknesses": "Strengths:\n\n- Clear empirical evaluation, with thorough experiments. \n- Inclusion of both theoretical justification and empirical results.\n\nWeaknesses:\n\n- Writing quality is clumsy, and at worst significantly affecting clarity and precision of what is being communicated. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster