Theoretical Characterization of the Generalization Performance of Overfitted Meta-Learning
Authors: Peizhong Ju
Yingbin Liang
Ness Shroff
Venue: ICLR 2023 poster (2023)

Abstract: Meta-learning has arisen as a successful method for improving training performance by training over many similar tasks, especially with deep neural networks (DNNs). However, the theoretical understanding of when and why overparameterized models such as DNNs can generalize well in meta-learning is still limited. As an initial step towards addressing this challenge, this paper studies the generalization performance of overfitted meta-learning under a linear regression model with Gaussian features. In contrast to a few recent studies along the same line, our framework allows the number of model parameters to be arbitrarily larger than the number of features in the ground truth signal, and hence naturally captures the overparameterized regime in practical deep meta-learning. We show that the overfitted min $\ell_2$-norm solution of model-agnostic meta-learning (MAML) can be beneficial, which is similar to the recent remarkable findings on "benign overfitting" and "double descent" phenomenon in the classical (single-task) linear regression. However, due to the uniqueness of meta-learning such as task-specific gradient descent inner training and the diversity/fluctuation of the ground-truth signals among training tasks, we find new and interesting properties that do not exist in single-task linear regression. We first provide a high-probability upper bound (under reasonable tightness) on the generalization error, where certain terms decrease when the number of features increases. Our analysis suggests that benign overfitting is more significant and easier to observe when the noise and the diversity/fluctuation of the ground truth of each training task are large. Under this circumstance, we show that the overfitted min $\ell_2$-norm solution can achieve an even lower generalization error than the underparameterized solution.

Published as a conference paper at ICLR 2023
THEORETICAL CHARACTERIZATION OF THE GENERALIZATION PERFORMANCE OF OVERFITTED META-LEARNING
Peizhong Ju
Yingbin Liang
Ness B. Shroff
Department of ECE The Ohio State University Columbus, OH 43210, USA ju ju.1710csu.ede
Department of ECE
Department of ECE & CSE
The Ohio State University Columbus, OH 43210, USA liang. 0890osu. edu
The Ohio State University Columbus, OH 43210, USA shroff. 11loff.11ee ceeeosu.ee. edu
ABSTRACT
Meta-learning has arisen as a successful method for improving training perfor- mance by training over many similar tasks, especially with deep neural networks (DNNs). However, the theoretical understanding of when and why overparame- terized models such DNNs can generalize well in meta-learning is still limited. As an initial step towards addressing this challenge, this paper studies the gener- alization performance of overfitted meta-learning under a linear regression model with Gaussian features. In contrast to few recent studies along the same line, our framework allows the number of model parameters than the number of features in the ground truth signal, and hence naturally cap- tures the overparameterized regime in practical deep meta-learning. We show that the overfitted min fg-norm solution of model-agnostic meta-learning (MAML) can be beneficial, which is similar to the recent remarkable findings on "benign overfitting" and "double descent" phenomenon in the classical (single-task) linear regression. However, due to the uniqueness of meta-learning such as task-specific gradient descent inner training and the diversity/ffuctuation of the ground-truth signals among training tasks, we find new and interesting properties that do not ex- ist in single-task linear regression. We first provide a high-probability upper bound (under reasonable tightness) on the generalization error, where certain terms de- crease when the number of features increases. Our analysis suggests that benign overfitting is more significant and casier to observe when the noise and the di- versity/fucttatiin of the ground truth of each training task are large. Under this circumstance, we show that the overfitted min fg-norm solution can achieve an even lower generalization error than the underparameterizeed solution.
be arbitrarily larger
INTRODUCTION
Meta-leamiig is designed to learn a task by utilizing the training samples of many similar tasks, i.e., learning to learn (Thrun Pratt, 1998). With deep neural networks (DNNs), the success of meta-Icarning has been shown by many works using experiments, e.g., (Antoniou et al., 2018; Finn al., 2017). However, theoretical results on why DNNs have a good generalization performance in meta-learning are still limited. Although DNNs have so many parameters that can completely fit all training samples from all tasks, is unclear why such an overfitted solution can still generalize well, which seems to defy the classical knowledge veaevvaaac---rreedo (Bishop, 2006; Hastie et al., 2009; Stein, 1956; James & Stein, 1992; LeCun et al., 1991; Tikhonov, 1943).
The recent studies on the "benign overfitting" and "double-descent" phenomena in classical (single- task) linear regression have brought new insights on the generalization performance of overfitted solutions. Specifically, "benign overfitting" and "double descent" describe the phenomenon that the test error descends again in the overparameterized regime in linear regression setup (Belkin et al., 2018; 2019; Bartlett et al., 2020; Hastie et al., 2019: Muthukumar et al., 2019; Ju et al., 2020; Mei & Montanari, 2019). Depending on different settings, the shape and the properties of the descent curve of the test error can differ dramatically. For example, Ju al. (2020) showed that the min E

---

Published as a conference paper at ICLR 2023
norm overfitted solution has very different descent curve compared with the min E norm overfitted solution. A more detailed review of this line of work can be found in Appendix A.
Compared to the classical (single-task) linear regression, model-agnostic meta-learning (MAML) (Finn et al., 2017; 7: Finn, 2018), which is a popular algorithm for meta-learning, differs in many aspects. First, the training process of MAML involves task-specific gradient descent inner training and outer training for all tasks. Second, there are some new parameters to consider in meta-training, such as the number of tasks and the diversity/lluttatton of the ground truth of each training task. These distinct parts imply that we cannot directly apply the existing analysis of "benign overfitting" and "double-descent" on single-task linear regression in meta-learning. Thus, it still unclear whether meta-leate weeannn also has similar "double-descent" phenomenon, and if yes, how the shape of the descent curve of overfitted meta-learning affected by system parameters.
A few recent works have studied the generalization performance of meta-learning. In Bernacchia (2021), the expected value of the test error for the overfitted min fn-norm solution of MAML is provided for the asymptotic regime where the number of features and the number of training samples go to infinity. In Chen et al. (2022), a high probability upper bound on the test error of a similar overfitted min fy-norm solution is given in the non-asymptotic regime. However, the eigenvalues of weight matrices that appeared in the bound of Chen et al. (2022) are coupled with the system parameters such the number of tasks, samples, and features, so that their bound is not fully expressed in terms of the scaling orders of those system parameters. This makes it hard to explicitly characterize the shape of the double-descent or analyze the tightness of the bound. In Huang et al. (2022), the authors focus on the generalization error during the SGD process when the training error not zero, which is different from our focus on the overfitted solutions that make the training error equal to zero (i.e., the interpolators). (A more comprehensive introduction on related works can be found in Appendix A.) All of these works let the number of model features in meta-learning equal to the number of true features, which cannot be used to analyze the shape of the couble-descent curve that requires the number of features used in the learning model to change freely without affecting the ground truth (just like the setup used in many works on single-task linear regression, e.g., Belkin et al. (2020); Ju et al. (2020)).
To fill the gap, we study the generalization performance of overfitted meta-learning, especially in quantifying how the test error changes with the number of features. As the initial step towards the DNNs' setup, we consider the overfitted min En-norm solution of MAML using linear model with Gaussian features. We first quantify the error caused by the one-step gradient adaption for the test task, with which we provide useful insights 1) practically choosing the step size of the test task and quantifying the gap with the optimal (but not practical) choice, and 2) how overparameterization can affect the noise error and task diversity error in the test task. We then provide explicit high- probability upper bound (under reasonable tightness) on the error caused by the meta-training for training tasks (we call this part "model error") in the non-asymptotic regime where all parameters are finite. With this upper bound and simulation results, we confirm the benign overfitting in meta- learning by comparing the model error of the overfitted solution with the underfitted solution. We further characterize some interesting properties of the descent curve. For example, we show that the descent is easier to observe when the noise and task diversity are large, and sometimes has a descent floor. Compared with the classical (single-task) linear regression where the double-descent phenomenon critically depends on non-zero noise, we show that meta-learning can still have the double-descent phenomenon even under zero noise long the task diversity is non-zero.
2 SYSTEM MODEL
In this section, we introduce the system model of meta-learning along with the related symbols. For the ease of reading, we also summarize our notations in Table 2 in Appendix B.
2.1 DATA GENERATION MODEL
We adopt a meta-learning setup with linear tasks first studied in Bernacchia (2021) as well as a few recent follow-up works Chen et al. (2022); Huang et al. (2022). However, in their formulation, the number of features and true model parameters are the same. Such a setup fails to capture the prominent effect of overparameterized models in practice where the number of model parameters
2

---

Published as a conference paper at ICLR 2023
is much larger than the number of actual feature parameters. Thus, in setup, introduce an additional parameter s to denote the number of true features and allow to be different and much smaller than the number of model parameters to capture the effect of overparameterization. In this way, we can fix and investigate how p affects the generalization performance. We believe this setup is closer to reality because determining the number of features learn is controllable, while the number of actual features of the ground truth is fixed and not controllable.
We consider mn training tasks. For the i-th training task (where i 1, m)) the ground truth is a linear model represented by y = / w + E, where s denotes the number of features, Vy E R is the underlying features, c IR denotes the noise, and y E R. denotes the output. When collect the features of data, since we do not know what are the true features, we usually choose more features than s, i.e., choose p features where p 2 8 to make sure that these p features include all true features. For analysis, without loss of generality, we let the first s features of all features be the true features. Therefore, although the ground truth model only has s features, we can alternatively expressed it with p features as y x= (()))
where the first 8 elements of x RR is at and 0 E IRP. The collected data are split into two parts with n, training data and
(n(() =
w(
validation data. With those notations, we write the data generation model into matrix equations as
x(() (0) E(())
y g((() xx(")"
(() + t
(1)
where each column of X (1) E R corresponds to the input of each training sample, each column of X (() E RRx=, corresponds to the input of each validation sample, gd(() R denotes the
output of all training samples, z(()) E R denotes the output of all validation samples, e((() E R
denotes the noise in training samples, and e0(i) denotes the noise invalidation samples.
Similarly to the training tasks, we denote the ground truth of the test task by w E RR, and thus x w.. Let w" [w E RR. Let n,, denote the number of training samples for the test task, and let each column of X" E RR denote the input of each training sample. Similar to Eq. (1), we then have
y¹ = (X") w + +e",
(2)
where c" E R"r denotes the noise and each element of y" E R"r corresponds to the output of each training sample.
In order to simplify the theoretical analysis, we adopt the following two assumptions. Assumption is commonly taken in the theoretical study of the generalization performance, e.g., Ju et al. (2020); Bernacchia (2021). Assumption is less restrictive (no requirement to be any specific distribution) and similar one also used in Bernacchia (2021).
Assumption 1 (Gaussian features and noise). We adopt i.i.d. Gaussian features (N, and assume iidd Gaussian noise. We use a and o, to denote the standard deviation of the noise for training tasks and the test task, respectively. In other words, e*6)) ~ NN InI,,). e(l) (0, o In.,.
m, ) for all i = 1,... ,,, and e" ~ ~N(0,o²
( Assumption (Diversityflucttaation of unbiased ground truth). The ground truth wt, and for all = 1,2, .m share the same mean w", i.e., E[w!"] w = E[w"]. For the i-th training task, elements of the true model parameter wo!) E RR are independent, i.e.
( -w!y w w!'] AA) = diag ((v(0,1) (2 .... (1)))))))
Let M() ()) v= V- /2//m, mm, vy = y ||ws" wollz and wo =
w
0 E RP.
2.2 MAML PROCESS
We consider the MAML algorithm (Finn et al., 2017: Finn, 2018), the objective of which is to train good initial model parameter among many tasks, which can adapt quickly to reach desirable model parameter for target task. MAML generally consists of inner-loop training for each individual task and outer-loop training across multiple tasks. To differentiate the ground truth parameters w(",, we use (+) (e.g., ()) to indicate that the parameter is the training result.
3

---

Published as a conference paper at ICLR 2023
In the inner-loop training, the model parameter for every individual task is updated from common meta parameter wn. Specifically, for the i-th training task (i 1,.... m), its model parameter ii(() is updated via a one-step gradient descent of the loss function based on its training data X
BC
inner == y x( w
(3)
where a₁ denotes the step size.
In the outer-loop training, the meta loss meta calculated based on the validation samples of all training tasks as follows:
Ceeta
E
outers
(t)
where Lotter
X w
(4)
The common (i.e., meta) parameter ti is then trained to minimize the meta loss L
At the test stage, we use the test loss Li y" via single gradient descent step to obtain desirable model parameter vi". i.e., vi" == r 0Cimz where 2 0 denotes the step size. The squared test error for any input æ is given by 8h0
w and adapt the meta parameter vò
(x, w"; ;0d) = x:- w x 1
(5)
2.3 SOLUTIONS OF MINIMIZING META LOSS
The meta loss in Eq. (4) depends the meta parameter ú via the inner-loop loss in Eq. (3). It can be shown (see the details Appendix C) that (mmti can be expressed as:
me
2mmr 11 fry-Büjje
(6)
where y E R (mm))xl and E (mmo) KP are respectively stacks of m vectors and matrices given by
y ()) x x g
x= T, - ((x(0))))
(²) x x0) (2))
x T, mo x111
(im) Peii
(m)) or x qe(mm)
T ((m) ((m)
X
By observing Eq. (6) and the structure of B, we know that ming Leeta has unique solution almost surely when the learning model is underparameterizze, i.c., p S mn,. However, in the real-world application of meta learning. an overparameterized model is of more interest due to the success of the DNNs. Therefore, in the rest of this paper, mainly focus the overparameterized situation, i.., when > mn, (so the meta training loss can decrease to zero). In this case, there exist (almost surely) numerous ió that make the meta loss become zero, i.e., interpolators of training samples.
Among all overfitted solutions, we are particularly interested in the min fo-n solution, since corresponds the solution of gradient descent that starts min fo-m overfitted solution Wi is defined as
linear model. Specially, the
W == arg min,, ||ام|| subject to Bi
(8)
In this paper, we focus quantifying the generalization performance of this min norm solution with the metric in Eq. (5).
3 MAIN RESULTS
To analyze the generalization performance, first decouple the overall test error into two parts: i) the error caused by the one-step gradient adaption for the test task, and ii) the error caused by the meta training for the training tasks. The following lemma quantifies such decomposition.
4

---

Published as a conference paper at ICLR 2023
Lemma 1. With Assumptions I and 2, for any learning result v (i.e., regardless how we train wi), the expected squared test error is
E ex"",e"
Lress ;00" = frest (110-wollk
where Jiest (S)
= (1-aa,)2 a,,) ((1== pt
ny at) (c+ vz) a.P oz nr
Notice that in the meta-learning phase, the ideal situation is that the learned meta parameter vù perfectly matches the mean Wo of true parameters. Thus, the term || woll2 characterizes how well the meta-training goes. The rest the terms in the Lemma then characterize the effect of the one-step training for the test task. The proof of Lemma 1 is in Appendix H. Note that the expression of fust (5) coincides with Eq. (65) of Bernacchia (2021). However, Bernacchia (2021) uses a different setup and does not analyze its implication as what we will do in the rest of this section.
3.1 UNDERSTANDING THE TEST ERROR
Proposition 1. We have
R-+p-1 (1)20= woll2 + v2) S mina, En,X", e aor (Lien w"; [00)]] S || - woll2 +
p+1
Further, by letting Or nrtp+1 (which is optimal when or 0), we have
Ex,X" ee, _w [Cres ;o"==""]] +,+
p+1
(1) wol 2 v2) +
P. o2
+p++
The derivation of Proposition is in Appendix H.1. Some insights from Proposition are as follows.
1) Optimal or does not help much when overparameterizee. For meta-learning, the number of training samples n, for the test task is usually small (otherwise there is need to do meta-learning). Therefore, in Proposition 1, when overparameterized (i.e., p is relatively large), the coefficient of (1|20 woll2 +v²) is close to 1. On the other hand, the upper bound | - wo +2, can be achieved by letting ar = 0, which implies that the effect of optimally choosing is limited un- der this circumstance. Further, calculating the optimal a,, requires the precise values of || wa v?, and of.. However, those values are usually impossible/hard to get beforehand. Hence, we next investigate how choose an easy-to-obtain Or-
p+1 n.tp+I
2) Choosing o, (n + p + 1) is practical and good enough when overparameterized. Choosing a, n,, .n/(nn, + p + 1) is practical since n, and p are known. By Proposition 1, the gap between choosing 0, nn/(n1, + 1) and choosing optimal is at most (n,+2+1y= ne of When p increases, this gap will decrease choosing a, = (n, + 1) is good enough.
0.2
In other words, when heavily overparameterizee,
reduce the noise error zero but cannot diminish the task diver- sity error to zero. In the expression of fiest (11e0 woll2) in Lemma 1, there are two parts related to the test task: the noise error (the term for a,) and the task diversity error (the term for v,). By Proposition 1, even if we choose the optimal ar,, the term of ve will not diminish to zero when mep 0² S Re of will
3) Overparameterization
increases. contrast, by letting a,, = n,, (n, + 1), the noise term diminish to zero when increases to infinity.
(n, (n--ptij00
3.2 CHARACTERIZATION OF MODEL ERROR
Since we already have Lemma 1, estimate the generalization error, it only remains estimate || [w0-wol? which we refer model error. The following Theorem 1 gives high probability upper bound on the model error.
Theorem 1. Under Assumptions and 2, when min(p, n+} 256, we must have
Prx Xullim) Ewwttmn ((10)) l | we 1l < bw 2 1
where bw = bw, + bideal and n min(p.n. J..4.
27m?n²
5

---

Published as a conference paper at ICLR 2023
The value of Bwo and bidcal completely determined by the finite (i.e., asymptotic region) system parameters p.s, m, nl, Bly || wolll v², o², and at- The precise expression will be given in Section 4, along with the proof sketch of Theorem 1. Notice that although b is only an upper bound, we will show in Section that each component of this upper bound relatively tight.
Theorem differs from the result in Bernacchia (2021) in two main aspects. First, Theorem I works in the con-asymptotic region where p and n, are both finite, whereas their result holds only in the asymptotic regime where p. ne + 0c. In general, an asymptotic result in order to understand and characterize how the generalization performance changes as the model becomes more overparameterized. Second, the nature of our bound is in high probability with respect to the training and validation data, which is much stronger than their result in expectation. Due to the above key differences, our derivation of the bound is very different and much harder.
-symptotiiic result is more powerful than
As we will show in Section 4, the detailed expressions of ww and bideal complicated. In order to derive some useful interpretations, we provide a simpler form by approximation for an overparam- eterized regime, where orp < 1 and min (p. n >> mike- In such a regime, we have
bw
mn. p
gideal
p- Camm.
where by mn Ci )o²
C2(1 C )u²). and C1 to C4 are some constants. It turns out that a number of interesting insights can be obtained from the simplified bounds above.
1) Heavier overparameteriration reduces the negative effects of noise and task diversity. From Eq. (9), we know that when p increases, bideal decreases to zero. Notice that bikkal is the only term that is related to o² and v², i.c., bāleau corresponds to the negative effect of noise and task diver- sity/fluctuation. Therefore,
conclude that using more features/parameters can reduce the negative effect of noise and task diversity/fluctutioon
Interestingly, bideal can be interpreted as the model error for the ideal interpolator Uasc defined
Wideal == arg min& || -wol2 subject to Bw 7
Differently from the min f--norm overfitted solution in Eq. (8) that minimizes the norm of ú. the ideal interpolator minimizes the distance between á and Wa, i.e., the model error (this is why we define as the ideal interpolator). The following proposition states that gideal corresponds to the model error of Wideal-
Proposition 2. When min(p, (p, n 2 256, we must have
{
26m2 nn min (p, n, 10.4
Pr (2(1mm) (o-(1m)_xx00 (((m) (L:m), (((mm)) (e00m))) |
wol 12 S
.bileal
2
2) Overfitting is beneficial to reduce model error for the ideal interpolator. Although calculating Wideaa not practical since it needs to know the value of wp. we can still use it as a benchmark that describes the best performance among all overfitted solutions. From the previous analysis, we have already shown that gādeal + when p + oo, i.e., the model error of the ideal interpolator decreases to 0 when the number of features grows. Thus, we can conclude that overfitting is beneficial to reduce the model error for the ideal interpolator. This can be viewed as evidence that overfitting itself should not always be viewed negatively, which is consistent with the success of DNNs in meta-learning.
3) The descent curve is easier to observe under large noise and task diversity, and the curve sometimes has a descent floor. In Eq. (9), when increases, bwn, increases but gidcal decreases. When a and becomes larger, bāleal becomes larger while bwn does not change, so that the descent of gideal contributes more to the trend of bw = bwt + (jikeal (i.c., the overall model error). By further calculating the derivative of by with respect to p (see details in Appendix D), we observe that, man wo 1 1, then by decreases
g > 1, then by always decreases for p Cammyy If g
'The approximation considers only the dominating terms and treats logarithm terms as constants (since they change slowly). Notice that our approximation here is different from an asymptotic result, since the precision of such approximation in the finite regime can he precisely quantified, whereas asymptotic result can only estimate the precision in the order of magnitude in the infinite regime as typically denoted by O(-) notations.

---

Published as a conference paper at ICLR 2023
(8)
(b)
109
p= 60, 0=0
model enrer
am
10a
0=03,
0=011=0011
100
null risk
102
102
30
38
Figure 1: The model error w.r.t. different values of and o, where m 10. n, 50, no 3, 8 5, | 2 100, and a 0.02 Subfigure (b) copy of subfigure (a) that zooms in the descent floor. Every point the average of 100 random simulations. The markers subfigure (b) indicate the descent floor for each curve.
Gemman ), and increases when Camnu when E (Camy
I-v9" Thus, the minimal value (i.e., the
floor value) of by is equal to ||wll (1 (1- C. "--""" which achieved at p Camn.
T-vØ" This implies that the descent curve of the model error has floor only when by is small, i.e., when the noise and
task diversity small. Notice that the threshold Camn. and the floor value ||
(1 (1-V))
1-v9
C4
increase as increases. Therefore, we anticipate that as v and a increase, the descent floor value and its location both increase.
In Fig. I, we draw the curve of the model error with respect to for the min 42-norm solution. In subfigure (a), the blue curve (with the marker "+") and the yellow curve (with the marker "x"") have relatively large and/or a. These two curves always decrease in the overparameterized region p > mn, and have no descent floor. In contrast, the rest three curves (purple, red, green) in subfigure (a) have descent floor since they have relatively small y and Subfigure (b) shows the location and the value of the descent floor. As we can see, when and a increase, the descent floor becomes higher and locates at larger p. These observations are consistent with our theoretical analysis.
In Appendix E.2, we provide a further experiment where we train two-layer fully connected neural network over the MNIST data set. We observe that a descent floor still occurs. Readers can find more details about the experiment in Appendix E.2.
4) Task diversity yields double descent under zero noise. For single-task classical linear regres- sion model y = x" wp + e. the authors of Belkin et al. (2020) study the overfitted min fo-n solutions singe learned by interpolating training samples with > n + i.i.d. Gaussian features. The result Belkin et al. (2020) shows that its expected model error is
E We single -woll
woll
p n p
woll
2
12 02.
p p-n-1
We find that both meta-learning and the single-task regression have similar bias terms p-mm || 1 and p- p ||wol|z. || respectivey When co, these bias terms increase to ||wollz which corresponds to the null risk (the error of a model that always predicts zero). For the single-task regression, the remaining term p-n-I o² Rv 2o² when > n, which contributes to the descent of generalization
eтror when increases. On the other hand, if there is no noise (a 0), then the benign overfit- ting/double descent will disappear for the single-task regression. In contrast, for meta-learning, the term that contributes to benign overfitting is gideal As we can see in the expression of iddea in Eq. (9), even if the noise is zero, as long as there exists task of the model error with respect to should still exist. This is also confirmed by Fig. ((a) with the descent blue curve (with marker "+") of
(i.e., >> 0), the descent
and a
5) Overfitted solution can generalize better than underfitted solution. Let wi (p=1) denote the solution when p 1. We have
(p=1)
2
w
02) 0
The derivation is in Appendix O. Notice that p s means that all features are true features, which is ideal for underparameterized solution. Compared the model error of overfitted solution, there

---

Published as a conference paper at ICLR 2023
no bias term of wo, but the terms of y² and o² are only discounted by and ny. In contrast, for the overfitted solution when p > mny, the terms of y² and o² are discounted by p. Since the value of m and the value of ny usually fixed or limited, while p can be chosen freely and made arbitrarily large, the overfitted solution can do much better to mitigate the negative effect caused new insight that when o,
by noise and task divergence. This provides is small, the overfitted f2-norm solution can have much better overall generalization performance than the underparameteriizd solution. This is further verified in Fig. ((a) by the descent blue curve (with marker "+"), where the first point of this curve with 5 (in the underparameterized regime) has a larger test error than its last point with p 1000 (in the overparameterized regime).
large and || ll
4 TIGHTNESS OF THE BOUND AND ITS PROOF SKETCH
We now present the main ideas of proving Theorem and theoretically explain why the bound in Theorem 1 is reasonably tight by showing each part of the bound is tight. (Numerical verification of the tightness is provided in Appendix E.I.) The expressions of bwg and bidcal (along with other related quantities) in Theorem will be defined progressively as we sketch our proof. Readers can also refer to the beginning of Appendix for a full list of the definitions of these quantities.
We first re-write|| ||w0 w 12 into terms related to B. When B is full row-rank (which holds almost surely when > mny), we have
16 = B3 (BBB" -1 7.
(10)
Define dry as
== 7
(11)
Doing some algebra transformations (details in Appendix F), we have
[wo - 1 (Ip B ) B) wo + B
("BBBT 1
(12)
Term
Term 2
To estimate the model error, we take siivide-and-oonqee strategy and provide set of propositions as follows estimate Term and Term 2 in Eq. (12). Proposition 3. Define
- mn)) + 2 (p- mm=) Inp + Inp
|woll2
p 22/ppn/n
bw (p- mnn) -2 mny) lnp
p + 2/p In 2mp
When mn, and p 2 16, We then have
Pr(Term I of Eq. (12) S bwml
2/p, Pr[Term I of Eq. (12) b 2 1 2/p,
E X((lm)) (((lmm)
[Temm I of Eq. (12)
mn
|woll2-
Proposition 3 gives three estimates on Term I of Eq. (12): the upper bound ban. lower bound T and the mean value. If we omit all logarithm terms, then these three estimates are the same, which implies that our estimation on Term 1 of Eq. (12) is fairly precise. (Proof of Proposition Appendix J.) It then remains to estimate Term 2 in Eq. (12). Indeed, this term is also the model error of the ideal interpolator. To see this, since Bi 7, we have B(ú Wp) = 7 Bwn = 87. Thus, to get min j woll2 as the ideal interpolator, we have Wideal we B (BB")-1a 8y. Therefore, we have
in
|
wi 12 (BB") (BB") 18
(13)
Now focus
| (BB") (BB(BB")
1 By Lemma 6 in Appendix G.2, we have
||5
(B""""")) -18713
|18y
(14)
Amaze (BB*)
Amii Amin (BB7))
We have the following results about the eigenvalues of BBT
8

---

Published as a conference paper at ICLR 2023
Proposition 4. Define of = ne
de (vp /uu + In vmi) and
meig.min p mmax (0, 1 2 1) nt ((n, + 1) max max 1 o/ + 66mn.) vFln p.
beig. p + (max (a/z, a1) 1) n + ((n maxfa', a1 2 =mmm)) vp
When p 2 n4 2 256, we must have
Pr { beig, S Amin Amin (Bin) Amax (Bxx S boig.max
23m 23mm?n? nn
Proposition 5. Define
Caig.min == max 1 -/,3p - 2mm max max - o/i3² V/2Vplpp Ceig,max = maxfa'; 1- - =1 (p (p+ (2mng + 11Vplup))
When ne 2 2 256, we have
Pr Pr( Ceig, I Amin (BB7)= < Amax (BB7) S Caig, 2 1 11mm1mmmmm m n
To see how the upper and lower bounds of the eigenvalues of BB" match, consider a&p < 1, which implies of < 1, and the fact that vp and Inp are lower order terms than then each of
min: meig, (aeg,maxxeeeiiiin Ceig.max be approximated by p + Emn, for some constant C. Further, when > miy, all beig, meig, Ceig.min, Ceig.max can be approximated by p. i.e., the upper and lower bounds of the eigenvalues of BBT match. Therefore, our estimation on Amax (BBT) and Amin ( in Proposition 4 and Proposition 5 are fairly tight. (Proposition is proved in Appendix L, and Proposition is proved in Appendix M.) From Eq. (14), it remains to estimate 1|ōv112.
Proposition Define
D = max {
| 1
nh + 2 n4 In(s)))) + 2 2l((s)))
The 22 n4 In(sni))
2 })
ax
n4
1 a, m,) mp + mn,u² In(sn:). (D+ a (p 1) 6. 25 (lm
by = mn.
The
Tte
When min ne 2 256, we must have
Prx(tmm) Xe(lim)
[eottoms (egillle))eeeien gellim) e (1:m3 1102112 S h13)
5mmn
2mm plo
We also have E [|871112 = mm (1+ aie + v²mmn (11-a))² a,) -2(p+1) where the expecta-
tion is on all random variables.
Proposition 6 provides upper bound by on [|őy|l2 and an explicit form for E [|0v1|2- By comparing by and I. || the differences are only some coefficients and logarithm terms. Thus, the estimation on ||6>/12 in Proposition 6 is fairly tight. Proposition 6 is proved in Appendix N.
Combining Eq. (13), Eq. (14), Proposition 4, Proposition 5, and Proposition 6, we can get the result by
of Proposition 2 by the union bound, where Nideal max beig min 1 (pp=,)) S Gox I (pSo,)) ). 0J- The detailed proof is in Appendix K. Then, by Eq. (13), Proposition 2, Proposition 3, and Eq. (12), we can get high probability upper bound on | w 12- i.e., Theorem 1. The detailed proof of Theorem 1 in Appendix I. Notice that we can easily plug our estimation of the model error (Proposition 2 and Theorem 1) into Lemma I to get an estimation of the overall test error defined in Eq. (5), which is omitted in this paper by the limit of space.
CONCLUSION
We study the generalization performance of overfitted meta-learning under linear model with Gaus- sian features. We characterize the descent curve of the model error for the overfitted min form solution and show the differences compared with the underfitted meta-learning and overfitted clas- sical ssingle-task) linear regression. Possible future directions include relaxing the assumptions and extending the result to other models related to DNNs (e.g., neural tangent kernel (NTK) models).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
The work of P. Ju and N. Shroff has been partly supported by the NSF grants NSF Al Institute (AI- EDGE) CNS-2112477 12471, CNS-2106933, 2007231, CNS-1955535, and CNS- and in part by Army Research Office under Grant 1911N1-21-1 The work of Y. Liang has been partly supported by the NSF grants NSF AI Institute (AI-EDGE) CNS-21 12471 and DMS-2134145.
REFERENCES
Antreas Antoniou, Harrison Edwards, and Amos Storkey. How train your maml. arXiv preprint arXiv:/810.09500 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-3322 2019.
Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lee, Sham Kakade, Huan Wang, and Caiming Xiong. How important is the arain-validatio split in meta-learning? In International Conference on Machine Learning, pp. 543-553. PMLR, 2021.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. understand deep learning we need to under- stand kernel learning. In International Conference on Machine Learning, pp. 541-549, 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv 2019.
preprint
Mikhail Belkin, Daniel Hsu, and Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-1180, 2020.
Alberto Bernacchia. Meta-leaming with negative learning rates. arXiv preprint arXiv:1102.00940, 2021.
Christopher M Bishop. Pattern recognition and machine learning. Springer, 2006.
Lisha Chen and Tianyi Chen. Is bayesian model model-agnostic meta learning better than model-agnostic meta learning, provably? In International Conference on Artificiaa Intelligence and Statistics, pp. 1733-1774. PMLR, 2022.
Lisha Chen, Songtao Lu, and Tianyi Chen. Understanding benign overfitting in nested meta learning. arXiv preprint arXiv:2206.1333 13482, 2022.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta- meta-learning for fast adaptation of deep networks. In International conference on machine learning, pp. 1126-11333 1135. PMLR, 2017.
Chelsea B Finn. Learning to Learn with Gradients. PhD thesis, University of California, Berkeley, 2018.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint 1xXiv:1903.08566 2019.
Yu Huang, Yingbin Liang, and Longbo Huang. Provable generalization overparameterized meta- learning trained with sgd. arXiv preprint wwXii:2206.091.36 2022.
William James and Charles Stein. Estimation with quadratic loss. In Breakthroughs in Statistics, pp. 443-460 Springer, 1992.
Peizhong Ju. Xiaojun Lin, and Jia Liu. Overfitting can be harmless for basis pursuit, but only to a degree, Advances in Neural Information Processing Systems, 33:7956-7967, 2020.
10

---

Published as a conference paper at ICLR 2023
Peizhong Ju, Xiaojun Lin, and Ness B Shroff. On the generalization power of overfitted two-layer neural tangent kernel models. arXiv preprint arXiv:2103.05243, 2021.
Peizhong Ju, Xiaojun Lin, and Ness B Shroff. On the generalization power of the overfitted three- layer neural tangent kernel model. arXiv preprint (..ivv220660204243 2022.
Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selec- tion. Annals of Statistics, pp. 1302-1338, 2000.
Yann LeCun, Ido Kanter, and Sara A Solla. Second order properties of enror surfaces: Learning time and generalization. Advances in Neural Information Processing Systems, pp. 918-924, 1991.
David Marquis, Hans De Moor, Kathryn Porter, and Michael Nathanson. Gershgorin's circle theo- rem for estimating the eigenvalues of a matrix with known error bounds, 2016.
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and double descent curve. arXiv preprint
2019.
JV Michalowiez, JM Nichols, F Bucholtz, and CC Olson. An isserlis' theorem for mixed gaussian variables: Application to the auto-bispectral density. Journal of Statistical Physics, 136(1):89- 102, 2009.
Partha Mitra. Understanding overfitting peaks in generalization error: Analytical risk curves for 12 and 4 penalized interpolation. arXiv preprint arXiv: 036603367, 2019.
Vidya Muthukumar, Kailas Vodrahalli, and Anant Sahai. Harmless interpolation of noisy data in regression. In 20/9 IEEE International Symposium on Information Theory (ISIT), pp. 2299-2303. IEEE, 2019.
Siddhartha Satpathi and R Srikant. The dynamics of gradient descent for overparametrized neural networks. In Learning for Dynamics and Control, pp. 373-384. PMLR, 2021.
Nikunj Saunshi, Arushi Gupta, and Wei Hu. A representation learning perspective on the importance of train-validation splitting in meta-learning. In International Conference Machine Learning. pp. 9333-9343. PMLR, 2021.
Charles Stein. Inadmissibility of the usual estimator for the mean of a multivariate normal distribu- tion. Technical report, Stanford University Stanford United States, 1956.
Yue Sun, Adhyyan Narang, Ibrahim Gulluk, Samet Oymak, and Maryam Fazel. Towards sample- efficient overparameterized meta-learning. Advances in Neural Information Processing Systems, 34:28156 1066-88660 28168, 2021.
Sebastian Thrun and Lorien Pratt. Learning to learn: Introduction and overview. In Learning to learn pp. 3-17. Springer, 1998.
Andrey Nikolayevich Tikhonov. On the stability of inverse problems. In Dold, Akad. Nauk SSSR, volume 39, pp. 195-198, 1943.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rXiv:1011.3027, 2010.
Yingtian Zou, Fusheng Liu, and Qianxiao Li. Unraveling model-agnostic meta-learning via the adaptation learning rate. In International Conference Learning Representations, 2021.

---

Published as a conference paper at ICLR 2023
A RELATED WORK
Our work is related to recent studies characterizing the double-descent phenomenon for overfitted solutions of single-task linear regression. Some works study the min f--norm solutions for linear regression with simple features such Gaussian Fourier features (Belkin et al., 2018; 2019; Bartlett et al., 2020; Hastie et al., 2019; Muthukumar et al., 2019), where they show the existence of the double-descent phenomenon. Some others (Mitra, 2019; Ju et al., 2020) study the min 4-- norm overfitted solution and show it also has the doublc-descent phenomenon, but with a descent curve whose shape is very different from that of the min fz-norm solution. Some recent works study the generalization performance when overparameterizztion in random feature (RF) models (Mei & Montanari, 2019), two-layer neural tangent kernel (NTK) models (Arora et al., 2019; Satpathi & Srikant, 2021: Ju et al., 2021), and three-layer NTK models (Ju et al., 2022). (RF and NTK models are linear approximations of shallow but wide neural networks.) These works show the benign overfitting for a certain set of learnalee ground truth functions that depends the network structure and which layer to train. However, all those works are on single-task learning, which cannot be directly used to characterize the generalization performance of meta-learning due to their differences in many aspects mentioned in the introduction.
Our work is related to few recent works on the generalization performance of meta-learning. In Bernacchia (2021), the expected value of the test error for the overfitted min fg-norm solution of MAML is provided. However, the result only works in the asymptotic regime where the number of features and the number of training samples go to infinity, which is different from ours where all quantities are finite. In Chen al. (2022), high probability upper bound on the test error of a similar overfitted min 22-norm solution is given in the non-asymptotic regime. A significant difference between ours and Chen et al. (2022) that our theoretical bound describes the shape of double descent in straightforward manner (i.e., our theoretical bound consists of decoupled system parameters). In contrast, the bound in Chen et al. (2022) contains coupled parts (e.g., eigenvalues of weight matrices are affected by the number of tasks, samples, and features), which may not be directly used to analyze the shape of double descent. Besides, we also explain and verify the tightness of the bound, while Chen et al. (2022) does not?. In Huang al. (2022), the authors focus on the generalization eтror during the SGD process when the training error is not zero, which is different from our focus the overfitted solutions that make the training error equal to zero (i.e., the interpolators). Our work also differs from Bernacchia (2021); Chen et al. (2022); Huang et al. (2022) in the data generation model for the purpose of quantifying how the number of features affects the test error, which has been explained in detail at the beginning of Section 2.1.
Type meta-lcaming Reps.
Overparameterizatioon Mcta
Method
Focus of analysis
Nested V
Per-task
Bai et al. (2021)
iMAML MAML, BMAML
Crain-validation split
Chen & Chen (2022)
Test risk
Saunshi ct al. (2021)
MAML
Optimal step size
Bernacehia (2021)
V
Train Train-validation split
Sun (2021)
V
Optimal representation
Zou et al. (2021)
MAML
Optimal step size
Chen et al. (2022)
/
HAML,iMAME
Benign overfitting
Ours
MAML
Descent curve shape'
Table 1: Positioning work in Table 1 of Chen et al. (2022) (which is shown here by the part
above the last row).
B NOTATION TABLE
We summarize the important notations in Table 2.
We use more specific setup (such as Gaussian features) than that in Chen et al. (2022), which allows us to provide more specific bound and verify its tightness.
FF.g, how the generalization performance of overfitted solutions changes with respect to the number of features.
12

---

Published as a conference paper at ICLR 2023
Symbol
Meaning
Type
sparsity (the number of non-zero parameters)
integer
the number of chosen parameters/features
integer
m
the number training tasks
integer
the (general) input vector
vector R
w())
the true parameters of the i-th task
vector R
the noise
scalar
the input vector corresponding to the true parameters
vector
(2)
the true parameters of the i-th task
vector R
w(())
the true parameters of the i-th task (padding with zeros)
vector R
the true parameters of the test task
vector R
the true parameters of the test task (padding with zeros)
vector R
w
mean value of w. (8)
vector R
mean value of ((
vector R
20
the (general) meta training result (before one-step gradient adaptation)
vector R
40'
the solution for the test task after one-step gradient adaptation on
vector R
the solution for the i-th task after one-step gradient adaptation on tü the overfitted min f--norm solution
vector R
vector R
Widcaal uiz"
the ideal overfitted solution
Vector R
the solution for the test task after one-step adaptation on
vector R
the number of the training samples for each training task
integer
the number of the validation samples for each training task
integer
fl
the number the training samples for the test task
integer
X
the matrix formed by n, training inputs of the i-th task
matrix RR
y y
the output vector corresponding to (()
vector RT
e"(o)
the noise in y ((t)
vector R
X
the matrix formed by n, validation inputs of the i-th task
matrix Rx
yrO)
the output vector corresponding to (x)
vector R
("(A)
the noise (())
vector R
the matrix of ny training samples for the test task
matrix RR
y"
the output corresponding to X"
vector R n
c"
the noise in y
vector R
standard deviation the noise
training samples
scalar
0r
standard deviation of the noise in the validation samples fluctuation of the ground truth for the training tasks
scalar
(.)(s)
scalar
Vr
fluctuation of the ground truth for the target task
scalar
C [(1)
the inner loss (on the training samples of the i-th training task)
loss function
(1)
the error for the validation samples after one-step gradient on the i-th task
loss function
outer
metta
the meta loss (average of C(i)
loss function
Liest
the squared test error for the test task
loss function
Qt.
step size of the one-step gradient on each training task
scalar
Ory
step size of the one-step gradient the target task
scalar
Table 2: Table of the notations.
13

---

Published as a conference paper at ICLR 2023
C
THE CALCULATION OF META LOss
By the definition of C
in Eq. (3), we have
(y)(0) X((1)² 2 0 y _x(()7 20
ac
a
inner
Iro
dro
θ (8 - -x(1)²² v
=-x(10)
y x(1)²
-11)x 2 X
Plugging it into Eq. (3), we thus have
( Ip
((0) x(1
+
01 x1()) ((0)
(15)
n2
Plugging Eq. (15) into Eq. (4), thus have
2 (0())
x²(o) 20(1
outer
2
2 y0(i) -x((i) ((1,-
ar "xx(( x(1
v + at x (1))
((1)
n
o(t)) at u())
x y( xx
Ip
at x
(())
2
By the definition of B in Eq. (7) and the definition of y Eq. (7), we thus have
L meta
lh Bubl
2mm
2mm
Eq. (6) thus follows.
D CALCULATION OF DESCENT FLOOR
Define h(p) = p-mnn.
/wol2 +
where p > Camne We have
Cama,
0h(p)
mik p²
|120112
bg
0p
(p )2
mn
||200
12
(11
Carmi
by
(p
Camnnn
2
p
mn,
||
mm | 12
Camma
(1- CamM
(1 11-
+ vo
vg
(p Camn,)'
bs
(recall that g ==
mn.
|/wlll
Notice that when Camm, and wo + 0. the first and the second factors are positive. Thus, we only need to consider the sign of A : Caran vo) Ifg 2 1, then A 0, which implies that hpp) is monotone decreasing. If g 1, then have
< when p (Cmmi
Camn.
> when p 1-v8
Camna
14

---

Published as a conference paper at ICLR 2023
(a) 60,
(b)
10
experiment
experiment theory
107
10c
theory null risk
model error
10a
null risk
10a
model
10a
10a
10a
10a
10a
10a
(c) v= 0.5, 0 0.5
(d) v 0.3, a= 0.3
10a
experiment theory null risk
experiment
10a
theory
10a
null risk
model
10
10a
10a
104
102
10a
102
10a
(e) U 0.1, = 0.1
10a
model
experiment
101
theory
risk
10a
10a
p
Figure 2: Comparison between the experimental values and the theoretical values of the model error.
which implies that h(p) is monotone decreasing when p E (Careryy Camna I-v9
and is monotone
Cymn. where this point increasing when p > Camn_ This suggests a descent floor at p 1-vg
h(p))
1|
Vg
gmAn
p=
C
1-V3
C4
Camn
I-v8
1
vg
||wool2
1
C₁
Ca
I-
/g)
=1/woll1
Ca
E ADDITIONAL EXPERIMENTS
E. SIMULATIONS TO VERIFY THE TIGHTNESS OF THEORY
In Fig. 2, we plot both the experimental values (denoted by separated markers) and the theoretical values (denoted by the continuous curve) of the model error. The simulation setup and (conse- quently) the experimental values are the same as those in Fig. 1 (note that we only show the points in the overparameterized region, i.e., p 2 mn,). The theoretical value is calculated by Theorem
15

---

Published as a conference paper at ICLR 2023
0.35
0.34
0.33
test error
0.32
0.31
0.30
0.29
40
100
500
network width (num of neurons)
Figure 3: The test emrо for two-layer fully connected neural network. The x-axis denotes the neural network width (i.e., the number of neurons the hidden layer).
and the approximation Eq. with constants' Ci = C3 0.001 and C2 C4 0.99995. As can see in Fig. 2, the experimental value points closely match the theoretical curves, which suggests that Theorem and Eq. (9) are fairly tight.
E.2 EXPERIMENTS OF META-LEARNING WITH NEURAL NETWORK ON REAL-WORLD DATA
In this section, we further verify our theoretical findings by an experiment over two-layer fully- connected neural network on the MNIST data set.
Neural network structure: The input dimension of the neural network is 49 (i.e., 7 x gray-scale image shrunk from the original layer weights and fully connected the hidden layer that consists of ReLUs (rectified linear units (0, }} with bias. The output of these ReLUs is then multiplied by the second layer weights and then goes to the output layer. The output layer is sigmoid activation function with bias.
28 gray-scale image). The input is multiplied by the first-
Experimental setup: There are training tasks and test task. The objective of each task is to identify whether the input image belongs
set of 5 different digits. Specifically, the for training tasks are {1, 2. 9), (0, 3, 9}, (0, 1, 4, 6, 8), {1, 2, 5, 7). respectively. The set for the task is 2, 6, 8). For each training task, there are 1000 training samples and 100 validation samples. All samples (except the ones to calculate the test error) are corrupted by i.i.d. Gaussian noise in each pixel with zero mean and standard deviation 0.3. The number samples for the one-step gradient is 1000 for these 4 training tasks and is 500 for the test task, i.c., 1000 and n, = 500. The number of validation samples n,, 100 for each of these training tasks. The initial weights are uniformly randomly chosen in the range [0. 1].
Training process: We use gradient descent to train the neural network. The step size in the outer- loop training is 0.3 and the step size of the one-step gradient adaptation is a, a, 0.05. After training 500 epochs, the meta-training error for each simulation lower than 0.025 (the range the meta-training emoor is [0, IJ), which means that the trained model almost completely fits all validation samples.
*These constants manually calibrated to fit the experimental values better.
16

---

Published as a conference paper at ICLR 2023
Simulation results and interpretation: We run the simulation 30 times with different random seeds. In Fig. 3, we draw a box plot showing the test error for the test task, where the blue curve denotes the average value of these 30 runs. We see that the overall trend of the test curve decreasing, which suggests that more parameters help to enhance the overfitted generalization performance. Another interesting phenomenon find from Fig. is that the curve is strictly monotonically decreasing and there exist some decent floors (c.g., when the network width is 80).
F
DETAILS OF DERIVING EQ. (12)
Notice that
(IT (BBBB))-BB wn, B" B²(BB")-1M (BB")"(BB") (Ip B" (BBB"") BB)
=(6))" ((BB") BBB))--BBBBBB -BBB)- wo
=0.
(16)
We thus have
wwww- w 11
B" BBBBB") (by Eq. (10))
= =II(T, (Tp B (BB") )BB) we B² 3"(BB") 1100)-18111 57112 (by Eq. (11))
LI, B" (BB") BB) woll + BB" (BB") T 5ا11 (by Eq. (16)).
Tem
Term
G SOME USEFUL LEMMAS
G.1 ESTIMATION ON LOGARITIIM
Lemma 2. For any x > O, we must have In 2 1.
Proof. This can derived by examining the monotonicity of In (1 22) The complete proof can be found, e.g., in Lemma 33 of Ju et al. (2020).
Lemma 3. When & 2 16, we must have 2
lnn / < 1.
Proof. We only need to prove that the function g(k) = 4lnk k S 0 when A: 2 16. To that end, when 1: 2 16, we have
0g(k)
4
0.
Ōk
Thus, g(k) is monotone decreasing when A 2 16. Also notice that g(16) = 4n 16 - 16 2 -4.91 < The result of this lemma thus follows.
G.2 ESTIMATION ON NORM AND EIGENVALUES
Let Amin()) (.) and Amin denote the minimum and maximum singular value of matrix.
Lemma 4. Consider orthonormal basis matrix U R and any vector E R Then
must have
Uallz = |all2-
Proof. We have
Ua Σ a,U,
(17)
1=1
17

---

Published as a conference paper at ICLR 2023
where U, is the i-th column of U and a, is the i-th element of Because U is orthonormal basis matrix, we know that U, are orthogonal to each other. other words.
10. j,
U - [1, i.
(18)
Thus, we have
1all22
T
Σ a.U
Σ a, (by Eq. (17))
Σ a (by Eq. (18))
||
The result of this lemma thus follows.
Lemma 5. Consider a diagonal matrix D diag(d), d2, de) R where min, d; 2 For any vector a, we must have
Da E min d, ||al| max d, ||a||2]
Proof. We have
h
h aj
[aals
Σ
daf E
min di
max de
Σ j=1
E
min di ||alla . max di ||a||
j=1
The result of this lemma thus follows.
Lemma 6. For any A Rack and a E 1x1 we must have
Aal E Amin (ATA)[al) Amax Amax(A (ATA) |al
Proof. Do singular value decomposition of A as A UDVT. Here D R is diagonal matrix that consists of all singular values, U E Rixa and V E Rixk (and their transpose) are orthonormal basis matrices. We have
|| Aa 1 = a Aa =a DVDDDVT. a
VDTDV'
E Amiul DD' V all Amax DD'D) VT a
27 (by Lemma 5)
Amin (A TATAN A) T all Amax (A A)
(by A = UDV?)
Amiu (ATA) || Amaa ATA)
(by Lemma 4).
The result of this lemma thus follows.
The following lemma is useful to estimate the eigenvalues of matrix whose off-diagonal elements are relatively small.
Lemma (Gershgorin's 's Circle Theorem (Marquis al., 2016).. I is an nxn matrix with complex entries 0i then (A( = Eifz lai,] is defined as the sum of the magnitudes of the non-diagonal entries of the i-th row. Then Gershgorin disc is the disc D(a r((A)) centered aas the complex plane with radius r((A). Theorem: Every eigenvalue of a matrix lies within at least one Gershgorin disc.
18

---

Published as a conference paper at ICLR 2023
G.3 ESTIMATION ON RANDOM VARIABLES OF CERTAIN DISTRIBUTIONS
Lemma 8 (Corollary 5.35 of Vershynin (2010)). Let A be an Ni x N2 matrix (N1 x N2) whose entries independent standard normal random variables. Then for every 2 with probability at least 2 exxp -t² /2) one has
Ni N2 LS Amin (A) S Amax (A) S VN V +1.
Lemma 9 (stated on pp. 1325 of Laurent Massart (2000)), Let U follow x² distribution with D degrees of freedom. For any positive x, we have
Pr - D D2 2V - 20 SET
Pr D U 2 Dr Se
Lemma 10 (Lemma 31 of Ju al. (2020)). Let u1, U2.-.. Uk and U1 "2.""" ug denote 2k ran- dom variables that follow i.i.d. standard normal distribution. For any 0, we must have
ka
(-2 1 at In
21 a )
Pr
S 2exp
2
where
t -1 -1+ +++v++
Lemma 11. For any k Z 16, let U1, u2.... wk and U1, ...... Ug denote 2k random variables that follows i..dd standard normal distribution. For any q S and e z O. we must have
2
Σ
u >c c. Vklung
S
ec.0.4 1lng
Further, by letting 1 and & k 2 16, we have
2
Pr
u
Vkink
5
k.0.4
By letting we have
k
2
Pr
Σ
ucty
>
cvk
<
c0..cc
Proof. Recall the definition of t in Lemma 10, we first want to prove at + In 24 that end, we have
2(v1+a²=1) To
2t
2(-1+
v1 22)
at
V 1 2² +l
(by the definition of t in Lemma 10)
a
a²
a²
2
(by Lemma 2)
2(-1 a²)
2
1 vi a²
+1
(since a² (-1+ v1+ v1 V1+dh +++)))
1+ 11+ a
(19)
2(v1 + a² 1)
Now we let 2c
Inq Thus, we have
ka
Vk kkng
(20)
2
19

---

Published as a conference paper at ICLR 2023
We have
Inq
=2 V k
Ink
2e
(since S k)
k
cc (by Lemma 3).
(21)
Because с 2 1, we have
1+ ++ 2 c V 0 c c + V2).
(22)
We thus have
21
a²
al + In
(by Eq. (19))
a
2(v1 + a² +1)
a²
2
(by Eq. (21))
2(1 + v e
a
(by Eq. (22))
2c(1 + v2)
4e lng
(since 2c V Ing
and v2 mz 1.414 3
2
(23)
5
k
Thus, have
k + In
))
21 20
2 2exp
2
a
k
4c lelng
2exp
(by Eq. (23))
2 k
=2 exp (-0.4clnq).
(24)
Plugging Eq. (20) and Eq. (24) into Lemma 10, the result of this lemma thus follows.
Lemma (Isserlis' theorem (Michalowicz et al., 2009)). If (x1, $2, ". Fa) is zero-mean mul- tivariate normal random vector, then
Ei ... r,, Σ II E[g,yyh
АCA3 (LJ)EA
where A denotes a partition of 1,2, ... into pairs, and A?, denotes all such partitions. For example,
E E2z1a13r B[arz2] E[1g21] + B[21as] E[12r1] + E[ R[æyas]
The following lemma is mentioned in Bernacchia (2021) without detailed proof. For the ease of readers, we provide a detailed proof of this lemma here. Lemma 13. Consider random matrix X E R whose each element follows i.i.d. standard Gaussian distribution (i.e., i..d. (o0, 1)). We mush have
[ X] pIn,
X nIp.
E XX n(n p 1)Ip.
Proof. Since each row of X are i..dd, we immediately have E|XX"] = nI, and E[X"x] pI,- remains to prove XXXX"xXX"] = n(n + + + 1)Ip- To that end, we have
[xx"] 1es X.XX"
Σ XanXj
(25)
20

---

Published as a conference paper at ICLR 2023
where X, denotes the i-th row of X, and Fly denotes the element in the i-th row, j-th column of the matrix. Thus, we have
XXxXx'
[xx]]
[XX]]
ii
{ EXnxXXas (by Eq. (25)).
Σ XixX
(26)
Now we examine the value of E XR. Xx. by Isserlis' theorem (Lemma 12).
E KK,
when * j:
0, when = j and k: + and | + l',
1, when = j and k: + and 1 (there are n(p - 1) such terms for each i),
1,
when j k and f l' (there are n(n 1) such terms for each i),
3. when = k and = 1' (there such terms for each i).
By Eq. (26), we thus have
E XXX xxx = (n(p 1) + m(n 1) + 3n) = n(n + p 1)Ip
The result of this lemma thus follows.
Lemma 14 (Lemma 24 of Ju et al. (2020)), Considering standard Gaussian distribution (O,0,), 1). when 2 we have
2/ 1212
22 -
S Pr
22 + V2 +4
t +
Notice that t + / e + 2 2 when t 2 0. We thus have
Pr (r 1 8/2
By the symmetry of the standard Gaussian distribution, we thus have
Pr 2 t) A1
H PROOF OF LEMMA
Proof. Similar to Eq. (15), we have
x "==11,-"xxxX
Or
+ ar x" X'y".
w"
i
(27)
n2
n,
By Eq. (27), we can express the learned result for the test task as
ar X
ar X"y"" ny
i0"
Ip
t
Trr
I,
Or
X
ar x" (XTFw² w + +E') (by Eq. (2)). nl,
(28)
Br
Considering a new input for the test task, the ground-truth is xx "" The distance between the ground-truth and the output of the learned model is
2 n" x 00 112-
21

---

Published as a conference paper at ICLR 2023
Taking the expectation on for the square of the distance, we have
E x "w""""-
x 200 1 - E x (w" - -w")
E(w" "0") xxx"" (w" -00)
m
(w" " Elxa" (trx"|(w" Iw" 20¹)
1w" w (since E. E[xx'' = Ip by Assumption 1).
Notice that
Or x X"X"
Cr X'Xx -1 20 + Or X'e" (by Eq. (28))
=
Ip
à +
nr
n2y
nt
ar
( w') - ar x"c"
Ip
n
ny
Then, taking the expectation on E", we have
E Xr.e"
1|w0"
- i
E
I " x'XxIT)
(w w²)
+
E
Qr x"e
Xr,e"
X
fr
(since e" is independent of other random variables)
w") (2b
E
Ip
x'xx") Or
T
Ip
ar x'XiX
(w0 (w-ww* ww)
X
n2
7r
a
TT
X T X"
?
E
6"
E
x
- 2a,
+
a
(nr + + +1)
1100
w w011
atP a² (by Lemma 13).
(29)
Notice that
E
100
w"11
w"
E || Wwo - (w" w
||0 woll2 + 12 (by Assumption 2, (w" wi) has zero mean).
(30)
The result of this proposition thus follows by plugging Eq. (30) into Eq. (29).
H.1 PROOF OF PROPOSITION 1
Proof.
For ease of notation, we let K = || wo 12 + vZ
From Lemma 1, we can see that
fiett (lrō- - woll)) is quadratic function of a.::
fiest (1:00 (onn-wool)) moll?)
((=t1
+1
K
po? 2Ka, + K.
a
nly
nt
Thus, minimize the test loss shown by Lemma can calculate the optimal choice of a, as
[arloppi
1
ptl nr
K
por nr
(Thus, we have [aylopii ht+
Pr when 0.)
Plugging (arlopui into fiest (1ee woll)) we thus have
Siest (116- woll2)
K
K²
K
p
(31)
l nr
K
pa? n
n,
+ p
+
1+
pd
K
22

---

Published as a conference paper at ICLR 2023
The right-hand side of Eq. (31) increases when of increases. or = oc, we can get the lower and upper bound of Eq. (31), i.c.
Therefore, by letting or 0 and
fress (1 (1ib-wolli)
K +
K
nr + +p+11
larkii
The result of this lemma thus follows.
I PROOF OF THEOREM ]
We summarize the definition of the quantities related to the definition of bw follows:
of
Ot (VP v n4
/ TT))²
Th
beig, p (max (0, o/.² 1) 1111) n4 ((n, + max 1 a!)² 6mmn) vplnp.
min = ma - a13² p 2mm, max a/}² Vplnp.
n + 2 n, In(sn,) + 2n(())))
nu 2 n4 In(s })
2
D = max
1-0
nh
a 22p(In n₂) 2
Imp'
(D+ ai (.15(())))))))
by = m0,0²
1
+ mm.uu 2l((m))).
n4e
mm)) + 2 (p mm Inp + 2np
bwo
|
p 2/plnp
by
iidell
max (eixxmei.,iin (p>mne) Ceig.min (pSm)) 0}*
bw bang + gidcal
(32)
Proof. Define the event in Proposition
A Aurget
E w(.mm) (((mmm)) (v(1m)))
Wideal wol1 1 I
gideaa w
Define the event Proposition 3 as
Aurgot, = Term I of Eq. (12) S bwoo }.
By the definition of be in Eq. (32) and the definition of Aurget,3 and Aurget, we have Ausget, Aurget = | - woll 1 < bw. Thus, we have
Pr [11Dee woll s bw } 2 Pr {Aarges, O Auargat
=1 Pr (Aurrpor, U Acarget)
> Pr Pr[ACinee (inge,,, Pr[AArgee (by the union bound)
26m
> p min min(n,, pn, (by Proposition 3 and Proposition 2)
27m² 2n?
21 min ( ne, 10.4
(33)
The last inequality is because thus follows.
p < since 0.6 > 2560.6 27.86 2 2. The result of this theorem
23

---

Published as a conference paper at ICLR 2023
J PROOF OF PROPOSITION 3
Define P = B (BB")-'B. In this section, we focus on estimating (T P) woll2- Since p2=P, P, we know P is indeed projection from R2² to the subspace spanned by the columns of B (i.e., the rows of B). The following Lemma shows that the subspace spanned by the columns of B" has rotational symmetry. Then, will use Lemma 16 to show how the rotational symmetry helps in estimating the expected value of the squared norm the projected vector. We then prove Proposition 3 by utilizing Lemma 15 and Lemma 16.
Lemma 15. The subspace spanned by the columns of B" has rotational symmetry (with respect to the randomness of (((1mm) and X((Im)). Specifically, for any rotation S E (O()) where S0(p) S Rexe denotes the of all rotations in p-dimensional space, the rotated random matrix SB shares
the same probability distribution with the original B
1,2, m. Proof. Notice that for any
Xv(i)
Ip
at
x())) g
n
=xv(1**
ST
at
"x"))== S- x()( ST
x
S-
= (SX
T
at
(sx-(i)
(SX (SX"I)) (since S = = because S is rotation)
n4
(sxx)) T
(xx()) ( ) at
=
1p
We thus have
X2(1) I, x(x)
ST
x
_ x x(22)
5
SBT
X Xu(m)² 2
Ip
a: x (m)) (m)))(((m) x((m)² 2 ST
(SX)())) T (SX
(I,
a (SX( (SX
me
T
I, (SX(2)) (SX
(34)
(Sx"(m)))
T' (I,- سي (Sx(m)) (Sx((m))))
Because of the rotational symmetry of Gaussian distribution, we know that the rotated random ma- trices (X)(() and SX4()) have the same probability distribution with the original random matrices x*(I) and X respectively. Therefore, by Eq. (34), we can conclude that SBT has the same probability distribution B². The result of this lemma thus follows.
The following lemma shows how to use rotational symmetry to calculate the expected value of the squared norm of the projected vector. Such result has also been used in literature (e.g.. (Belkin et al., 2020)).
Lemma 16. Considering any random projection Po E RRXP to a k-dim subspace where the sub- space has rotational symmetry, then for any given Rex1 must have
k 1
E Po
|P
Proof. Since the subspace has rotational symmetry, to calculate the expected value, we can fix subspace and integral over all rotations. Specifically, consider any fixed projection A that projects
24

---

Published as a conference paper at ICLR 2023
to k-dim subspace that is spanned by set of orthogonal vectors d1, ag..... ag R². Therefore, after projecting o with A, the squared norm of the projected vector is equal to
|
Σ aa, v)?.
Noticing that applying a rotation in the projected space of A is equivalent to applying the rotation a1, 02; ag, we then have
E
P
Po
Sa,, ds
so(p) iml
S Sa,, b)
so(p)
(since making a rotation S on both vectors does not change the inner product value)
aa, 1-)
so(p) 1=1
aj 2u)
s20(p)
|01|2
a; ú)²
Sp-1
St
i=1
|
2
k
(a;, d);
(35)
Sp-1 i=1 S--1
where SP-1 denotes the unit sphere in RR and Sp-1 denotes its area. Since A can be any fixed projection to k-dim subspace, without loss of generality, can simply let a be the i-th standard basis in R² (i.e., only the i-th element nonzero and is equal to 1). (Note that there are standard bases although A is spanned by only the first ie standard bases.) In this situation, we have
f (a;, (a,,)) 0)
(aj, 2) for i.j E (1.2.....)) .P}.
SP-1
and
Σ
(a 00
Σ
(ai 6)
||ا1|2 dō Sp-1
i=1 Sp-1
Sp
i=1
SP-1
Therefore, we have
f S (ai, 2) - Sp--1
p
By Eq. (35), we thus have
E. Po PPoul12 = |1 Po
The result of this lemma thus follows.
Now we are ready to prove Proposition 3.
Proof of Proposition 3. Define
arccos (wp, Pwa)
E [0, 7/2].
||ol 2
25

---

Published as a conference paper at ICLR 2023
Thus, have
III--) P) sin 0 1|wll12.
(36)
By Lemma 15, we know that the distribution of the hyper-plane spanned by the rows of B has rotational symmetry (which a -in-ddimensioaal space). Therefore, 0 follows the same distribution of the angle between uniformly distributed random vector a E IR and fixed man.ddimensional hyper-plane. To characterize such distribution of 0 (or equivalently, sin f), without loss of generality, we let a (0, Ip) and the hyper-plane be spanned by the first mny standard bases of IR.. Thus, we have
a [1mmn.)
a man 1:pp
cos2
sin?
(37)
||1|
||al 2
||2 and ||a| follow x² distribution with p mn, degrees and degrees of freedom, respectively. By Lemma 9 and letting x = In p in Lemma 9, we have
Notice that [mm.. + 1:pl
1
Pr aa 2 S p- 1--p--2plppg [/mnp]] - p
(38)
1
Pr |aa| 2 2/pl1/ + 222 p 1
(39)
Pr |mn,
4mm,++1pp + l:pl 1 (p mn.) + +2V(6 33-p-mm)))nm
mm.) Inp 21m S
1
(40)
p
Pr {1l amm. l:pl
2 - (m-mm.) + 22 (p -2m s
(41)
Because p 2 16, by Lemma 3, have
Inp
Vplnp
21 P
< <1 =
<1 - p 2/ppnpppppppp 0.
(42)
We define
A Aurget,3 (Term of Eq. (12) S bung )
A Auaget,33
Term of Eq. (12) tan
We thus have
Pr 3
sin? 02>0>>0 (0-m))) +2 mn.) Inp 2 In Pr
p p- 1-2vplnp
(by Eq. (36) and the definition of P)
||a (amm
(p mn,) 2 ( mn,) Inp + 2 2mpp) (by Eq. (37))
=Pr
|a12
- 2/plup
< Pr [Iaal2 S 2 p/pnpp
+ Pr { || 112 2 (p - mn,) + 2/ (p - mn,) (n lap + 21mp)
(by Eq. (42) and the union bound)
2 - (by Eq. (38) and Eq. (40)).
(43)
By Eq. (36) and Eq. (43), we thus have
Pr Pr[Aunge, 2
26

---

Published as a conference paper at ICLR 2023
Similarly, using Eq. (39) and Eq. (41) (also by the union bound), prove
Pr[Auarett.3]
By Lemma 16, we have EE| Pwol [
||20012- Thus, we have
Term 1 of Eq. (12) P mall
1wo
P
The result of this lemma thus follows.
K PROOF OF PROPOSITION 2
Proof. Define the event in Proposition
(iedeal woll2 S bjddaal
Aurget
E
(wimm) ((1mm) ((((m)
Define
Amax (BB*) beig, min L (p>n,) + Ceig, Ceig,min (psne)) Combining Proposition 4 and Proposition 5 with the union bound, we have
Anrgott1
23m2
Pr[Aaarger, 2 min ne J0.1
(44)
We adopt the event in Proposition
Aurget
E (w(1in (llmm) (((mm))
1187112 S b6
By Eq. (14), we have ni Aurget,
Ausget- Thus, we have
Pr[Anrged
2 Pr
Auarges,
2
=1 Pr
A A
x=1
> Σ Pri(Anunget, (by the union bound)
23m2 2n
5mn,
2mn
21 min (p, n4 nz
(by Eq. (44) and Proposition 6)
nt po.
26m2n1
21 min (p, n 10.4"
The last inequality is because 2 n4 2 and
n 2 256 - n 2 0.6 27.86 =
0.6 I 1.
The result of this proposition thus follows.
L PROOF OF PROPOSITION 4
We prove Proposition 4 by estimating every element of TBT, We split BBT into X blocks (each block is of size n, X n,,). Recalling the definition B in Eq. (7), we identify three types of elements in BB"
diagonal elements (type 1), off-diagonal elements of diagonal block (type 2), and other elements (type 3). Fig. illustrates these three types of elements when m = 2 and n, = 3. In the rest of this part, we will first define and estimate each type of elements separately in Appendices L.1, L.2, and L.3. Using these results, we will then estimate the eigenvalues of BB" and finish the proof of Proposition 4.
27

---

Published as a conference paper at ICLR 2023
type
type 2
type
type
type 3
type
type
type
type
type
type 3
type
type 2
type 2
type
type
type 3
type 3
type 3
type 3
type 3
type
type 2
type 2
type
type 3
type
type
type
type 2
type 3
type 3
type 3 type
type 2
type 1
Figure 4: Illustraiion of three types of the clements in BB" when = 2 and n, = 3. In this case BB is 6 x 6 matrix (i.e., IR ((mm).))(mmn)).. There are 4 (i.e., m²) blocks (divided by the dashed red line) and each block is of size x (i.e., no n,,)
TYPE 1: DIAGONAL ELEMENTS
Type elements are the diagonal elements of BB", which can be denoted
BBT 1(i-1)m +5. (4- (i-1)n+tj
an "x"0xx (xxxx T
=0X Ip
I,
or "xxxx())) 74
[X
(45)
ng
where E 21, m} corresponds to the i-th training task, j E {1, ... n.y corresponds to the input vector of the j-th validation sample (of the i-th training task). To estimate Eq. (45), have the following lemma.
Lemma 17, For any i 21,2,... ... , and any (,,2,... ... n.., when p 2 n4 2 256 we must have
5
Pr [BB")B-I)natt (6-1)antt (1-1)nuts 1b,, bıl} 2 1
VTi"
where
4 = max {0, a/3 (nz 2n, ln + nh 22pp - n2) In
b, = max(a', 1 of2 (ne + V2n, hn + Imm) + - n, + /2(p n4) Inng Inne-
Proof. See Appendix I.
28

---

Published as a conference paper at ICLR 2023
TYPE 2: OFF-DIAGONAL ELEMENTS OF DIAGONAL BLOCKS
Type 2 elements are the off-diagonal elements of diagonal blocks. Similar to Eq. (45), Type elements can be denoted by
[BB
(i-1)ou (i- 1)muttk
=1X I
Ot xxx)
T ( I
22
xxxx0" [x
(46)
n4
n
where j + k. We have the following lemma.
Lemma 18. For any i (1,2,--. ,. and any j.k E f1,2, .. nob that j & k, when 2 n4 2 256, we must have
5
Pr BB" (6- (i-1)m.+t, (1-1)m.thl S bb2
ni. n0.4
where
b2 = max Vn
Inn4 Vplnp.
Proof. See Appendix L.2.
TYPE 3: OTHER ELEMENTS (ELEMENTS OF OFF-DIAGONAL BLOCKS)
Type elements are other elements that are not Type Type 2. In other words, Type elements belong to off-diagonal blocks. Similar to Eq. (45) and Eq. (46), Type 3 elements can be denoted by
BB" 11-11) (I-1)m++k
x T
=(x"0003
I
at
xx00 x
Ip
at
x x())
[X
n
-(11p 1p 1 xx xxx00 [X Ip
at
(() x(1)?
[X
(47)
The
n
where i + 1. We have the following lemma.
Lemma 19. For any i, E (1,2,..,, ,m] and any j. 21,2, ... nnw that # when p 2 n 2 256, we must have
13
Pr
BB (t-1) 1). +s. (1- (1-1)m+th
s ba)
2
72 0.4
where
= 6Vpppp
Proof. See Appendix L.3.
Now are ready to prove Proposition 4.
Proof of Proposition 4. Define a few events as follows:
A := all type I elements of BBT are [b. b,]}
A₂ = all type 2 elements of BB" T are in [-b2. bel]
A all type 3 clements of BBd in [-bg. bal}
Notice that there mn, type elements, (n, 1) type 2 elements, and m(m 1)ng type elements. By the union bound, Lemmas 17, 18, and 19, we have
5
5
Pr[Af} <
m.n S mR
(48)
Vele
n
Pr([A] S
mmn (ng - 1),
(49)
0.4
13
Pr(Ag)
mmm 1)n?
(50)
n
29

---

Published as a conference paper at ICLR 2023
We first prove that Ni=1 A, A To that end, recall the definition of disc D (A)) and the radius of the disc (A) for matrix A in Lemma 7. We now apply Lemma 7 on BB". Because of Ag and Ag, for any (1,2,-... mn. we have
r.BB")== = Σ
[BB Jasl & (ny - 1)62 + (m 1)m,b3.
JE(12, mach ji
Because of N A, and Lemma have all eigenvalues of BB is in
bb, ((n. 1)62 + (m - 1s), b2 + ((n. 1)62 + (m 1)n,
Since p 2 2 256, we have
and v n4 Inne I Vplnp S vplup. 22 n4) In I 2plmp & 2pplnp,
(51)
Since n; 2 256, by Eq. (60) of Lemma 20, we have In S
45 n4. Thus, we have
1
In ny v II,, Inne
n4 In
(52)
45
Recalling the values of ,,, 5,, b2. and by in Lemmas 17, 18, and 19, we have b, - ((n - 1)b2 + (m 1)m,bs)
max (0, 1 - - ne - 22 In In n4 - n4 - /2( m)) Inne
(nv 1) (max(aa) ai} nr In + vplup)
(m 1)n 6/plnp
2p + (max{(,, 1-01--10 a²} 1- n4
- ((22+ + (ne - 1)) max(a', 1 - at32 + /2 + (n, - 1) + 6(m - 1)mo)) Vplup
(by Eq. (51) and max 1 - o13² S max - )))
2p + (max(0, 1 - a42² - 1) - ((nv + 1) maxfa/, - a,}² 2 6mm)) Vplup
beig.min,
and
bj + ((ng - 1)b2 + (m - 1)m,bb))
= =maxfa', 1 ai} (ne + 2m, Inn, - Imns) +p ns + /2(p - n)) Inn, + lane
+ (n, - maxffa/ 1- af Vv, In, + vplnp)
+ (m - 1)m, 1..ppppi
Sp + (maxfa - a,} - 1) ny
+ (V2++ (nw -1 1)) maxfa', of)² + 45 + V2+ + (n. - 1) + +66 1)mm) Volnp
(by Eq. (51) and max(0, (0, 1 - 2 < max ( - })
<p+ (maxfo%, - 1- - 1) n. + ((n. + 1) max((a,, 1 - of3² 2 + 6mn.) vplnp
-big. max.
Define
(p2n.) = beig < Amin (BB") < Amax (BB") < beig, max Irget,1
Therefore, have proven that no= A:
A (p2n)) targtt11
30

---

Published as a conference paper at ICLR 2023
remains estimate the probability of A
To that end, have
Pr
(p2m))
Pr
A
(since
0 A
A
Aargot,
target.
=1 Pr
A
i=1
3
21
Σ
Pr [A9) (by the union bound)
i=1
23m2 2
21
(by Eqs. (48)(4))(5)).
0.4
The result of this proposition thus follows.
L.1
PROOF LEMMA 17
Since all training inputs are independent with each other, without loss of generality, we let i = and replace 1x , by a random vector a ~ (N I,) E R which independent X In other words, estimating Eq. (45) is equivalent to estimate
|
az The x (1)
a
We further introduce some extra notations as follows. Since 2 n. we can define the singular values of ( E R2x as
0 S x
(()) < ((1) < ... Ane
((11)
(53)
Define
( = diag (x)(), Xx
x! E R
Do singular value decomposition of (1), we have
(1) ('OL
(54)
Notice that UT()) R is an orthogonal matrix, D is an orthogonal matrix. Using these notations, we thus have
(000) RPx", and V R R.x.
Ip
at x X1))* n4
-1*(1)
Ip
at "DD
D
TOIT
(by Eq. (54))
Th
-14
I
2
O
U(a)T (by the definition of D(()). (55)
Ip-n.
The following two lemmas will be useful in the proof of Lemma 17. Lemma 20. If x 2 16, then
3 x 2 In.r,
(56)
16
x + 2x In + Inx <
2x,
(57)
x 22 In 3
I
(58)
6
x Iax < V22.
(59)
Further, if 2 256, then
45 x 2 In r.
(60)
31

---

Published as a conference paper at ICLR 2023
Proof. We prove each equation sequentially follows. Proof of Eq. (56); When æ 2 16, we have
( 0
16 x
3
> 0.
d
16
Thus, 16 x In x monotone increasing when x 2 16. Thus, in order to prove 16 2 In for
all 2 16. we only need to prove 16 Eq. (56) holds.
3
16 2 In 16. Notice that In(16) = 2.7726 < 3. Therefore,
Proof of Eq. (57); Using Eq. (56), we have
3
2x ln + I
(
0.7999x S x.
16
Eq. (57) thus follows.
Proof of Eq. (58); Doing square root on both sides of
18 x 2 In we thus have
V3
I 2 In x
x 2
22x In
1
3
x
V 2x In
1-1
(since - V
2 0.3876 2 3
3
Eq. (58) thus follows.
Proof of Eq. (59); We have
3
+ I Sx
+
(by Eq. (56))
16
19
V2x
16
6
19
6 7)
2x (since
0.8397 <
16v2
Eq. (59) thus follows.
Proof of Eq. (60): When 2 256, we have
+ x i
In x)
1
0.
Fx
45
Thus, 45 x In æ monotone increasing when x 2 256. Thus, in order to prove 45 x In x for all
1
x > 256, we only need to prove 1 256 2 In 256. Notice that 256/45 Therefore, Eq. (60) holds.
256 0.1437 > 0.
Now we are ready to prove Lemma 17.
Proof of Lemma 17. Recalling (*(1) in Eq. (54), we define
a' = U a R
(61)
2
X =
a
xp
(62)
t=1
i=p-n
32

---

Published as a conference paper at ICLR 2023
We then have
|
I
n
TT
[In-
24 2(1)))
0
UnlL) a (by Eq. (55))
ne
I I.-n.
er )
mm
a' (by Eq. (61))
I p_
Ott
(1))
a
Σ
a
The
i=1
1=
P
min
1
((2)
Σ
d
22
jE(1,2,""..
n
1=n++1
2 n1
1
at (((1)
2
max
a
(E(,,,,",,m)
n
imzy+
max
0,
at
2(1))
n
Xne +
Xp-
2
max
{11
at (1)
Re
1 ai \
4(1)
})
Xn. + xpm
(by Eq. (62) and Eq. (53)).
(63)
Because of rotational symmetry of normal distribution of a, we know that Xaum and Xp-n: follows x² distribution of p and p ni degrees of freedom, respectively". We define several events as follows:
4
Xoy n4 + +2 In ym + 2 Vnt
2
A2
Xp-n: p n4 2 (p me) v + 2 vnte
2
A3
Xp-n; < n4 2 (p m)) In vne
2
A
X(I)
1(1) vp + vu: In The
AG
(101)
((1)
vp= vo: In vie
As
X
2
.4 2 n vTe
(x(()) and ( are independent, so a and (+(1) are also independent. The calculation x2, (or x²-n.) utilize the rotational symmetry of a (or a') is because x2, (or x²-n,) represents the squared norm of the result that projects a' into ni- (or (p ddim) subspace.
33

---

Published as a conference paper at ICLR 2023
We have
6
Pr X(
A =1
UUA X(()),a
Pr
Ai
21
Pr (A:)
Pr {A4 As) - Pr(AA) (by the union bound) X(())
i=1
4e
in in
2e (In v 12 (by Lemma and Lemma 8)
4
2
=1
TTt
exp ( In vTe In VTt)
2
21
(since In /ne 2 2 when n, 2 256)
v n
exp (In vmi)
=1
(64)
v n
Define the target event
(2)) (1)
Lb b1 m
A
Ip
x
14
It remains to prove that
A
A. To that end, when Ni= A&, we have
Ip
(1)
R4
2 max (0. -
Are
2
Xn. + Xp-n. (by Eq. (63))
ne v 2mz Inne)) + nu - 22( T4.) In max {0, 1 2
(by AB and Ag
=b,
and
1p
at
x
(
at
((11)
(1)) 2
})
18
max
74 1
Xmx + Xp-n, (by Eq. (63))
22
(VD + The + In v nuy) ;1}) 2
max
at
(Vp
Th - In slvvin vTo)²
1- at
T
Tht
(ne + V 2n, Inn, + Inn
+ - nu + 22(p - ne) Inn; + In ne
(by Af. Aś, Ai and Ag)
<max(o/, df2 (n v 2n, Inne + Inn)) +p nn + 22(p ne) n ne
=hn-
L.2 PROOF LEMMA 18
Since all samples are independent with each other, without loss of generality, we let i and re- place [x(()]; [x l by two i.i.d. random vector a. b ~ NN(0, Ip) RPx1 which are independent of X (() In other words, estimating Eq. (46) is equivalent to estimate
a "xxxx(0)) T n4
aT (I,
0t xx))) (()))))) b.
I
34

---

Published as a conference paper at ICLR 2023
Proof of Lemma 18. Recalling U*()) in Eq. (54), we define
a' = U'() a a Rex1, = = Una)"
E Rex1
(65)
T4
On, Σ
a pp-m
a/bL
(66)
1=p-R
We then have
a
1p
at x
(11) x((I)))
b
n4
24 A 2
(2(1)
Inn
0
U b
(by Eq. (55)
I I--n_
T
11
ny
0
b'
(by Eq. (65))
0
n,
((1)2) 2
at A
a/b² +
Σ
a&b'
i=
max
t(1) Qt
T2g 1
at
((1)²) 10nll + +1pp-al
}} ni
(by Eq. (65) and Eq. (53)).
(67)
Because of the rotational symmetry of normal distribution, we know that on, and pp-n. have the same probability distribution if a' and b' follow i..dd (N, I,) Define several events as follows:
A = |@ne1 > v nie lune
A flop-nel= > /plmp}.
A3
X(L)) vp+ /ni+ - In vTe
A4 = (() < vp vni - In VTt
We have
1
Pr
=1
Pr
A
X10),abb
X1O)
1==
21 Pr
{Ai}
Pr (A2) - Pr (As U.} (by the union bound)
a
a.b
X(()
1 2
2
2e (la /2 (by Lemma 11 and Lemma 8)
p
2 0.4
exp ( In vn: In nTx) (since 2 ny and n. 2 when n4 2 256)
n
21
(since In /na 2 2 when n, 2 256)
nt
0
exp (In vTe)
21
(68)
no.4
Define the target event
2 b S bz } at ( x(a)T) In
A aT
ni
"We can utilize the rotational symmetry because do, (or ),-n,) can be viewed as the result of the following steps: 1) project a' and b' into fixed subspace that is spanned by the first (or last 12c) standard basis vectors in R²: 2) calculate the inner product of these projected vectors.
35

---

Published as a conference paper at ICLR 2023
It remains to show that 0 11=1
A
A. To that end, when Ni= AG, we have
p
Ct
(11)
{1))
b
max
ar 11
2(1)
0g (11)
}
2
1mnal + +1pp-nl (by Eq. (67))
T4
nte
(VD + /na + In vnn) }})}]
max
04 (vD
/ni In vmn)
at
v Vn Inm
14
n
+ Ip (by Ai, Ag Ag. and AQ)
I max (a - a43² n4 In ne + vplng. p.
(69)
By Eq. (69) (which implies N A
A) and Eq. (68), the result of this lemma thus follows.
L.3 PROOF OF LEMMA 19
Because all inputs are i..dd Eq. (47) is the inner product of two independent vectors, where each vector follows the same distribution the vector
0t xx X a R².
1p
(70)
The
where (O, Ip) and is independent of x In other words, it is equivalent estimate of P2 where P1 and P2 follow the i..dd. shown in (70). If we can characterize the probability distribution of p. then
estimate Eq. (47). The following lemma shows the rotational symmetry of Eq. (70).
Lemma 21.
The probability distribution of p has rotational symmetry. In other words, for any rotation S E S0(p) where S0(p) S R2*P denotes the set of all rotations in p dimension, the rotated random vector Sp shares the same probability distribution with the original vector p.
Proof. By Eq. (70), we have
01 SX (X
Sp
Sa
T1t at SX (U)((( S
Sa
T1 0i (1) (1) S Sa
Sa
(because S = ST as a rotation is an orthogonal matrix)
-Sa (SX (1) (SX The
Notice that Sa and (I) the rotated vectors of and ( respectively. Since and (1) are independent Gaussian vector/matrix, by rotational symmetry, we know their distribution and independence do not affected by a common rotation S. Thus, Sa n, (SX (Sx(") (Sa) has the same probability distribution as p. The result of this lemma thus follows.
The following lemma characterize the distribution of the angle between two independent random vectors where both vectors have rotational symmetry.
Lemma 22. Consider two i.i.d. random vector C1, C2 TRP that have rotational symmetry. We then have
of
C2
Vplnp
2 2
Pr
>
<
+
|c21
2/ppmpp
p
p
36

---

Published as a conference paper at ICLR 2023
Proof. Notice that |e: |el denotes the angle between с₁ and C2. By rotational symmetry, it equivalent to prove that the angle between two independent random vectors that have rotational symmetry. To that end, consider two i..dd. random vectors #1, #2 ~ (0, Ip). The distribution of the angle between #1 and 22 should be the same as the angle hetween e₁ and c2- In other words, we have
c2
22
ce
(71)
11
|002112
||lll2
c22l2
By Lemma 11, we have
Pr
[ x2
2 Vpmpp po.4"
(72)
Noticing that | and ||02|12 follow chi-square distribution with p degrees of freedom, by Lemma 9, we have
Pr { | 112 p 2/plmp < < lup
(73)
p
Pr |ل2l| I p- 2/plmp] S lnp
(74)
By Eqs. (72)(73)(74) and the union bound, we thus have
x 22
2 vplng
Pr
5 + yo
[
[22122
p 20-2yphy Ipp
By Eq. (71), the result of this lemma thus follows.
Now we are ready to prove Lemma 19.
Proof of Lemma 19. Since p 2 ni 2 256, by Eq. (60) of Lemma 20, we have
1
2p
p - 2222plng 2 1 2
45
p 2
v5
45
p
=
3
(75)
We define some events as follows:
|| 2 2 T }
A1
A
||2212 2 b
T P2
Vplnp Inp
As
|| ||
- 2/p lmp
A {ppt P2
$ bz)
By Lemma 17, we have
5
Pr(AA} <
Pr(A2) <
(76)
Th
Ttt
By Lemma 22, we have
Pr(Ag) < +
(77)
p0.4
Since n. 256, by letting x n4 Eq. (57) of Lemma 20, we have
n4 2n In n4 + In n4 2n.-
(78)
37

---

Published as a conference paper at ICLR 2023
We also have
p n4
22 ne)
In + Inne
1
1
Sp nr +
12p
+
(by Eq. (60) in Lemma 20)
45
45
2
1
Sp n4 +
+
(since p 2 n1)
45
45
44
Rt.
(79)
45
45
Therefore, we have
2
44
b, S max 1 -0132 2n +
1 V 45
p
74
45
<max(ob 132 4p (since p 2 n2).
(80)
First, we want to show ni= A = A. To that end, when Ni AG, we have
| P2l
p
= =1|p1 12 ||22ll2
|| 12 llealla
vpImp (by
<b. p - 2/ppny y
A and Lemma 17)
vplnp
<4p
(by Eq. (75) and Eq. (80))
2p/3
=6 p In p.
Thus, we have proven that n n== A²
A, which implies that
3
Pr[A] Pr
A
=1 -1-Pr Pr
A,
i=1
21
Σ
Pr {A.} (by the union bound)
i=1
10
21
p (by Eq. (76) and Eq. (77))
13
21
0.6 (by
2 since p 2 n, 2 256).
nu
The result this lemma thus follows.
M PROOF OF PROPOSITION 5
Lemma 23. For any i (1,2.... ..., ..] and any f1,2, .. ,, when n4 2 p 2 256, we must
have
2
2
Pr BB" (i- 1)- (1-1)n+t5 [c,, a1} 2 1
p
T4
where
== max o1) (p 2/plnp).
T == maxfa', 1- o (p 2 / +2
38

---

Published as a conference paper at ICLR 2023
Proof. See Appendix M.1
Lemma 24. For any i (1,2. 2... m and any j.k E f1,2, .. noo that j # k, when ne 2 p 256 and at S 0.2, we must have
2
2
Pr [ (i- (i- (-1))=+ S [ 21
p0.4
n
where
22 = maxfa/, a.}² Vplup.
Proof. See Appendix M.2.
Lemma 25. For any i, E 21, m) that i I and for any j, k
21
.n when
n1 2 2 256 and 04 S 0.2, we must have
6
Pr BB") (t- +J. (11))muth] S Tz
2
p
/nz
po.4
where
C3 max o23 vplmp.
Proof. See Appendix M.3.
Now we are ready to prove Proposition
Proof of Proposition 5. Define few events as follows:
A = all type elements of BB" are in [.. a]},
A all type 2 elements of BB" are in [-ž ad]
A3 = all type 3 elements of BBT are in [-Ta, Td]
Because n, 2 pp 2 256, have
1 Vnc
2
(81)
vp
po.4
p
p0.4
Since p 2 256, by Eq. (60) in Lemma 20, we have
Inp = Vlnp Inp S
pnp.
(82)
45
Notice that there are mn, type 1 elements, (n, 1) type 2 elements, and mmm 1) type elements. By the union bound, Lemmas 17, 18, 19, and Eq. (81), we have
3mn, p0.
4mn, - 1) po.4 Pr[A5]
9m(m 1)m
Pr[4f]
Pr[AS]
(83)
1a.s
By N2= A, and Lemma 7, we have all eigenvalues of BB in
is ((n, 1)02 (m 1)n,cs) 00 ((n, 1)0z + (m 1)n,cz)]-
Recalling the values of [1, T2 and T3 in Lemmas 23, 24, 25, we have
Ci ((n, 1)2g + (m 1)m,73)
-ax(00, 2
(2max a3 + (n, - + + 2(m 1)m,) max.))maxx(.11111 of,? Vplnp 2 max(0,11 - 2 2mn, max(a a1)² plup
(noticing that max( (a,, at2² 2 max - d1)3)
Ceig.miin
39

---

Published as a conference paper at ICLR 2023
and
τ + ((n, 1) + (m - 13)
maxfa/,, - op (p+ + + In
+ (ng + + + 2(m 1)m,)) max (o o4) u/l2/plns plup
< max 1 - a1}² 2 p + (2mn, 1) 11)plupp) (by Eq. (82)
Ceig.maxx
Define the event
A (pSn.) Irget,1
= Coig,min S Amin (BB") S Amax (BB") S Coig,max
Therefore, we have proven Ni=n Ai
A ((SS)))
Thus, we have
3
Pr(A(nSni)
M
2 Pr
A
3
=1 - Pr
A
i=1
21
Pr[A:] (by th union bound)
16m2ng
21
(by Eq. (83)).
p0.4
The result of this proposition thus follows.
M.1 PROOF OF LEMMA 23
Proof. When p n,, we define the singular values of (1)) E RRxx"
0 X < X S ... 101).
((2)
Define
A11 = diag (11 ((1)
x E Rexp
We can still do the singular value decomposition Eq. (54), but here D [AtC) 0 R
since < nt. Using these notations, we thus have
at ( x000 =U(() I,
_ (
U
Ip
n4
nt
Similar to Eq. (63), we have
1,
0t x
x
E max 0, x((1)2
Xpr
7h
max
|
2(1)) a4
"
1
(c))
1))
2 Xp
(84)
n2
n
where X2 = !
|| = || 2 follows x² distribution with p degrees of freedom. We define
several events as follows:
A =
Xp
2 < p 2/ //ppppp
A2 =
X p + 2/plpp 21 p
2
Ag
x(1) Voe + -/- - In TTp
4
1(1 Vn- vĐ- In nm
40

---

Published as a conference paper at ICLR 2023
We have
Pr X a
A
=1 -
Pr
U
iiml
21 Σ
Pr[Ai]
Pr (As Aa} (by the union bound) X(())
1=1
21
2 exp
(- k /2) (by Lemma 9 and Lemma 8)
2
2
21
(since In yn+ 2 when n, 2 256).
VTu p
Define the target event
a 2 le, a
A
1p
0t x
(2)
(1)
n2
It remains to prove that
n
A8
A. To that end, when N A4, we have
Ip
at
x
x
n
2
max
0,1
)(11)
Xp
2
(by Eq. (84))
nt
0, at
(VTh + vp + In v 2 } (p- 11-2vllnp) (by As and Ag)
2 max
max (0,
a/)2 (p- 3/plmp)
When Ni=1 Af, we also have
at (()
x(())
Ip
at x ((1)2
at 111)
})
2
max
1
\1
X (by Eq. (84))
Tht
14
< mmax
1
O't
(Vi++ vF- - In vni)²
at
(Vr+ vD + In vnni
n4.
n4
(p 2/ 2/pnpp 2mp)) (by As. AB and Ai)
maxfal, 1 a33² (p (p+2/plng + 21mp)
M.2 PROOF OF LEMMA 24
Proof. Similar to Eq. (67), we have
2
a
I,
an x
x
b
ni
1 at x ((1)2
||
at ((1)
})
2
max
l0pl.
(85)
nt
n4
Define several events as follows:
A1
10pl > Vplnp
AQ
(g(1)) > Vne + vD - In T2
As
(1( Vn V/- - In Vni
41

---

Published as a conference paper at ICLR 2023
When Ni=1 Af, we have
T'
Ip
x (XXX)) b
x
Tte
<
max
Ott
(v vD- - In mt)
1
ar
(Vrz + vD + In vni) m
n
nu
Vplup (by Eq. (85), Ai, AG. and 15)
< <maxfa,, 1 - a²}3 Vplup.
Thus, we have
x 2
Pr
T
Ip
at
x
x
b s Volmp
n
2 Pr
A
=1 Pr
A
1-1
21 Pr[Ai]
Pr X
[Az Aa] (by the union bound)
a.b
2
21
exp
(-(In /T.)²/2) (by Lemma 11 and Lemma 8)
p0.4
2
2
21
(since In vn 2 2 when n4 2 256).
vml
M.3 PROOF OF LEMMA 25
Proof. Define several events as follows:
A
|l 12 2 c
A₂
|| 1/2 2 τ }
pf P2
Vplnp
Ag
| l12 |
2 Imp
A = Upp p2 I <33
By Lemma 23, have
2 + Pr[Au] Pr[Ai] <
2 2- p
2 Tu
S
+
(86)
p
Vmu
By Lemma 22, we have
2
2
Pr[As]]
< - +
(87)
p 2o.4
When p 2 256, by Eq. (60) of Lemma 20, have
1
1 V
Inp - 45 Vplnp S
45" P.
(88)
42

---

Published as a conference paper at ICLR 2023
First, we want to show Ni=1 A$
A. To that end, when Ni=1 Af, we have
p P2
1f p2) =11ill1
||22||2
|
|222l2
Vplup
3
I 1 a13 (p+2 p 2/plnp
(by
A
1
1+ /
45
+
2
45
Vplnp (by Eq. (88)
1 2/
1
45
1+ 2
m2 1- a1}² vp Inp (because
45
45
1.91 2).
1-2 2
45
Thus, we have proven Di=1 A
A. which implies that
Pr[A 2 Pr
A
=1 Pr
A
3
21
Σ
[r[AA]] (by the union bound)
1=1
6
21
po. (by Eq. (86) and Eq. (87)).
P
The result of this lemma thus follows.
N PROOF OF PROPOSITION 6
Plugging Eq. (1) into Eq. (7), we have
X²(I)T
I (1))
w(1) -xxx(112 (()) + (1)
m
X
I, as x222 x22)
w(2) e xx() ( (2)
==
X²(m)?
(I,
at (m)m)((mm)) (m)) es ( T (mm (m)) + (mm)
a
m,
By Eq. (11), we thus have
X T
P 24 xxxx))(())))
(w(1) w)) x1) x((1) (11)
x
I, 2 x22))))1(2)
(w wa) a4 x2)) (2) (2) (2)
d- =
Xu(m)²
(I,
ai (mm) x((m) X((m)x((m) 7) (w)(m) wi) ae
x (()) ((m) ((m)
((m)
ne
(89)
43

---

Published as a conference paper at ICLR 2023
In Eq. (89), since terms el(1om) and lmmmm) have and independent of each other, have
E elllm) pe
|
E e((kmm) eet (1om)
I1
at x
x (xx0)())) (20 wi)
me
(())))
X
(10) ((1))
+ (
xu(t)²
In ( ar xxxxxxx xxx) (m) -wo)
-m
+
1=1
2 at x x²(1) ((1)
+
E
(90)
e(())
n4
Notice that
x
x((0 ((1)
E
ef())
74
(x)))) x x(1)
(x"()* x())((1))
E
n ellt)
E Tr ( x (0) x²))² xx()]
(by trace trick Tr(W Z| Tr(ZW)
"f clls)
Tr
xv(i)"
x x x
(since
E (0 ((0" o2L,.).
(91)
n
ctcc)
Plugging Eq. (91) into Eq. (90), we thus have
||07112
gt(lmm) (m0(m
0m
+
X X²(1)²
Ip
at x 4(1) x(())
(w wo)
The
Term A
m
02 ni
Tr
x x
x
x (0) x1)
(by Eq. (91)).
(92)
Term
The following two lemmas estimate Term A and Term B. Lemma 26. When ne 2 16, we have
Pr X((lmm) (1mmm
E
Term A of Eq. (92)) < mn.y² 2I((s)))
w
(laa,,m,)) ap 1) 6 (125(l)))))
}
5mn,
21
n4
n2
and
Term of Eq. (92)] ymm,, (a-ar)) az)² ap + 1)
E Xl(lm)) X.Clmm) (lmm
Proof. See Appendix N.I.
44

---

Published as a conference paper at ICLR 2023
Lemma 27. We have
2mm
Pr Xv(loa), (o0ma))x((0n X((lo)
Term B in Eq. (92) <
Inp- (Iun))²
21
(93)
p0.4
ma n
E (Klii)))x00a
(Trm B in Eq. (92)
(94)
71
Proof. See Appendix N.2.
Now are ready to prove Proposition 6.
Proof of Proposition 6. By Eq. (92), Lemma 26, and Lemma 27, the result of Proposition 6 thus follows. Notice that the probability estimated by the union bound.
N.1
PROOF OF LEMMA 26
Proof. We have
X
I at x x(()
(2o wn)
E
T
E
X X
I
a2 x
(1)) x
(w wo)
x
(w wo)
= E
X X
I,
a2 x
(1) (0)
(w wo)
11e
(w -omm
1,
ai x
(()) x(())?)
x((()) (by the trace trick)
n
Tr (1))
I, at
x (
E. (w wo) woo7
a x x((xx(1)) 2)) X((i))
1,
n
Tr (1)
I,
at (0 ())
_A
A 0
I
at x
(0) x
x²
0
ne
(by Assumption 2).
(95)
Define
VA
0
a:
xxxx(0) x=(1) Rox..
A
0
I
Plugging A(g) into Eq. (95), we thus have
E 1013)
x T
1,
ar x t0 (()) 74
(w w))) Tr (A7)) A())
(96)
Here b:lia denotes the element at the j-th row, k-th column the matrix, [-]t. denotes the I-th row (vector) of the matrix, [:].& denotes the k-th column (vector) of the matrix. Notice that only the first s rows of A()) is non-zero. Define
Qui (1)) 3. (1 (1-
ae x 7h
12)
Σ
(() n
X(() (.).
1.
1=.12
45

---

Published as a conference paper at ICLR 2023
We thus have
mon ( or xxxx(())))
x
when j = 1," '1 8,
(A
j
0,
when j = 8 + 1, 1.. P.
when j 1, ,, ,
(0,
when j 8 + 1,... p.
Therefore, for any A (1,2,
no.. we have
[A ()) ( k.k (A)) (A)A
A A0Bi
Σ Uiu 2
(97)
By Eq. (96) and Eq. (97), we thus have
Term A in Eq. (92)
"() P
(98)
k=1j=1
Part I: calculate the expected value of Pf
By Assumption and Lemma 13, we have
3 1 2
n2, and E [ 31 ||
E
x
=
me(n 2).
(99)
We also have
(1) J:: 2,)) = =
(()
x(())
1. 4g
B
3.g x(1) (.)² 2 (by Assumption
x ( j.
1g
(100)
If fix ( and only consider the randomness in x since each element of X²(),, 1 are i.d.d. standard Gaussian random variables, then we have
Qijkk N(0,02....)
(1
2
2 where Qu.ak
x
(1) Joi
Σ
( (t) des x((i
(101)
n2
n2
(-,12
Thus, we have
E
Pij
xx))
R
E
Q
X
X
E (
2 Quik
(by Eq. (101))
=1 2 ar
E X(()
(()
a²
E
(()))
+
2
Σ
B(X (
Jos X100
14
m
x
I-
(1,2
a a, + 2)
ar(p (p
1)
=1 20 +
(by Eq. (99) and Eq. (100)
a (p
=(1 - -ax)² 2²)2
+
(102)
n4.
46

---

Published as a conference paper at ICLR 2023
By Eq. (102) and Eq. (97), thus have
A()) = n2 Σ mons? (u-
+ az (
Thus, we have
E Term A] vmm (L-- az) az +1
2m 1
Notice that we use the definition of v and (()) Assumption that v² Σj=1 " 2-
and (6) =
Part 2: derive high probability upper bound
By Assumption and Lemma (where e = 2.5 In(spre) and a = e). for any given j ,m),
(1,2, .m,j.
E (1,2,-.. .s), and l E {1,2, .P) {i}, must have
Pr (x*0) x (.) 2 2n5
2
(103)
spnt
A1,(1.)))
By Assumption and Lemma 9, for any given E (1,2, mm and j E (1,2, ,3. have
Pr
X (()
d:
$ no - 22 nu (nne), + 2 (ns,)) + 2l((sn)))
2
(104)
ST4,
A2,5.5)
By Eq. (101) and Lemma 14, for any (+),, we have
Qi.j. Quiik
2 (2ln(sns)
}
Pr
X=(i)
Thus, we have
Qiiik
Pr Xu(i) x
2 V2ln(smm)
5
(105)
aQrak
871
As.(...))
We define AL.i...), (2,)).)) and (s,(i.)k) as shown in Eq. (103), Eq. (104), and Eq. (105), respec-
tively. Then, detine the event
A - {
... A Ai.nnn A 2,00)) A (133)) hold for all i E (,, mm, j jE (1,2, IE (1,2, -- .pp \ (i). and & E {1, 2, ... n
... ,8], }.
Applying the union bound, we then have
2m
2m
5man
Pr[A]
2
T4
R4
71
14
When A happens, we have
2e.. (1-
at
x
(()) b:
2) 2
+
at (x(10)
J.s ) 2
(by Eq. (101))
nh
ne
I- (1,2, pd (G)
af(p -
<D(on, n4, 8) 8)
6. 6.25(In()pn.)) (by Ai, and As for all i,
(106)
47

---

Published as a conference paper at ICLR 2023
Thus, have
Term
Mis Ql (by Eq. (98))
m
3 200 Qiss" 2In(sm)) (by (5, for all i, k)
k=1j=l
(D(ar, n2, ai -1 1) 6.25 (In((1n))))) (Inpsp)))
Smnyv² lln(snn)
7t
(by Eq. (106) and the definition of v² in Assumption 2).
The result of this lemma thus follows by combining Part and Part 2.
N.2 PROOF OF LEMMA 27
Proof. In order show Eq. (93), it suffices show that
Tr ( T x(1) x x nome(lum)) 2
2mn
Pr max (1,2,, .m)
(107)
n2.
and in order to show Eq. (94), it suffices to show that for any i E f1,2, ... m
T x x (()) x = n.
(108)
We first prove Eq. (107). To that end, we notice that X ((1) is a nyy x ni matrix. For any 1,,, and j = 1,2, ... fyy, have
x T x x()) x())
x X
x
x()
k=1
= (xx(()
11.g. 1.
k=
2
Ne
Σ
(0)) le,5
[x
(109)
Thus, have
Tr X T
X ( x()) X
max
16(1,2,--, .m}
(1)) X xi) x((
max
1,(1,,." m
j=l
max
x 11.5 ](M
(by Eq. (109))
(1.22, m)
j=1k=1
1 1,x
Zn
max (1.22 m)
(110)
(1,,
Jc (1,2,.....
Notice that training input ( and validation input ((() independence with each other and each element follows i.i.d. standard Gaussian distribution. Therefore, by applying Lemma 11 (where c In n4. & p. and q p), for any given i, j. and k, we have
2 exp(In n4 0.4 n4 por
2
Pr
1r. [X ]0,
> Innee v plnpp
<
48

---

Published as a conference paper at ICLR 2023
The last inequality use the fact that In ny 0.4 In + 0,4 when min(n,,p p) 2 256. By the union bound, we thus have
P xx le
2mm
Pr
max ie(1,, mn
Inn Vel X
(111)
pa.
/ me) 1, )
By Eq. (110) and Eq. (111), we have proven Eq. (107). The result Eq. (93) of this lemma thus follows.
remains to prove Eq. (108). To that end, by Eq. (109), we have
2
nu
Tr x x
x
x
1e,
Thus, by Assumption 1, we have
Σ E 11,5 [X
115 [x
E
n
(xx
1x
B|
E|X 1
Rep
i.e, we have proven Eq. (108) (and therefore Eq. (94) holds). The result of this lemma thus follows.
O UNDERPARAMETERIZED SITUATION
In this case, we have p S mny. The solution that minimize the meta loss is
Wt arg min meta
When B full column-rank, have
1 BB"
Thus, we have
(wo- u 112 = Ww - B) 712
= (B" 85 2 (by Eq. (11)).
(112)
Define
(1
2
( 1) (a1, 02, 03, a1) = vas 1
0e a2
σ² as
Se (12
n,
+
ai 01 The
m
74
+
04
Notice that In 2 In 256 5.5 2 2 and 0.4 > 0n 256 x 0.4 x 5.5 2 2. Thus, we have
(In () Inp 1) 2 (2 1) which implies that Inn, 0.4 In p 2 In + 0.4Inp.
49

---

Published as a conference paper at ICLR 2023
Lemma 28. Consider the case p 1. there exist g.g. h E R such that
X
71
g for all i f1,2,... m.),
(113)
X
13 S h.
i1
- 2
(114)
74
then we musl have
(wo wecl12 2b (g.g.
wlmm)
climm) (()m)
Further, if
x 13 E [r. for all i E 21,2, ... .,),
(115)
then have
E wom) (1mm)) (n(tom)
(wo - 101212 S b(p=1) (g. (g.
(F/r) mr).
Proof. Since == 1, B becomes a vector and Bd B is scalar that equals
n.
B
Σ
x
2
13.
(116)
ne
1=1
By Eq. (112), we have
(BT57) 87)
Ww
(117)
(B' B)2
In this case, B Jry is also a scalar that equals to
2) 2 2
Bd B =
at
(10)
[xx0)]] (w(1) - wo)
ne
(
E.0 (x1())
ntt
1
Ot
xx 1x
n4
By the independence and zero mean of (i)
wo. (0), and e()), we have
( by)) 2
E fllmm)
w (im)
(1:m)
x
21)
(1))
11
n
1=1
0ee The
m
x x
2
1
Term
B
(118)
Term 3
50

---

Published as a conference paper at ICLR 2023
By Mouchy-Schwarz inequality, we have
7TR
2
(119)
==1
We then have
Term 1 of Eq. (118)
m
E
2² 1
C4 The
9
x
12
1
04 !
Σ
Σ
x
(013
i=1
j=1
(by Eq. (113) and Eq. (114))
2
27
m
n2
m
E
v2
at g
Σ
x
12
1
att
Σ
x
The
m
i=
j=
(by
Eq. (119))
2
m
m2
2
a2
y
Σ
x3
12
(1-
m²²
(by Eq. (115)),
n4g
m
and
Term 2 of Eq. (118)
2
27
(ai0 T4
2
Ct n4
2 m
Σ
Σ
nv
(1-
0+
m
>
XX
g
n2
n
j=1
(by Eq. (113) and Eq. (114))
E
oang
(1
a2
g
2 1
Σ
(x
[aag
(1
at
Σ
x
nt
n
n4
n
1=1
j=1
f=1
s=1
/=1
(by Eq. (119))
2
e
2
[
g
2 1
Σ
m n2
[
[o033
2
1
at
g
mF²
(by Eq. (115)).
nt
n2
m
,
The
n2t
i=1
j=1
Similarly, we have
2
BB²
m
at
x
113)
Σ Exx0003
(by Eq. (116)
n
2
27
E
1
Σ
m nhe
(1-
at nut
))
)
Σ
m ny
x
(by Eq. (113))
ntt
1=1
m The
E
I
g
(mr)²
(1-01
[
Σ> ΣΣ (03
(by Eq. (115)).
nt
The
Plugging the above equations into Eq. (117), the result of this lemma thus follows.
51

---

Published as a conference paper at ICLR 2023
Proposition 7. Define
Daingle 6(p=1)
(9.9, 1, h),
baingl = 1
b(p=1) (g. (f/r)². mr), (p.
g = n4e + 2v n log n + 2 2og n4:
g nt 2 n4 log n4,
2/n,
h = mn, + 2v mn, log(mn,))))))mommooo.mm + 2 llog(mn.).
no + 2 n. log n + 2 log Ry:
= 2/ noe lo. nv.
When = 5 = 1 and a2 relatively small such that 21 g 2 0. we must have
w (p=1)
2
2m
Pr X((Im)) X,,, Xu(lmm)
wi
baingle
(w(mm)) (lim) (ellon))
(1==)
2 < 'bsingee
2m
2m
Pr Xt(lim) (00im3,Xu(tnee Xu(tim))
E (m(mm)) (l (m(mm)
w0n
2
Proof. Notice that | follows x² distribution with ny degrees of freedom, and Σm
follows x² distribution with mn, degrees of freedom. Given any fixed i E 11,2, ... m.. by Lemma 9 (letting = log nz), we have
Pr
1())
2 g
<
x()
?
Pr
I
<
2
By Lemma (letting x = log(mn,))) )) we have
Pr
X
1 212210
h
5
1
mmm
By the union bound, we thus have
Pr x
? [g. gl. for all i E (1, .m]
2m
n
Similarly, have
Pr Pr 1 x //3 [r, F). for all i e (1,2, .....
2m
The result thus follows by Lemma 28.
We interpret the meaning of Proposition 7 as follows. We first approximate each part by the highest order term. Then we have y = gg
R n4, F R ny, and h z mn, &s mg. Thus, we have
b(p=1) g. g. 1, h) b(==1)(g. (g. (F/r)², mr).
Therefore, we can conclude that our estimation on the model error || wo 1 in this case is relatively tight. In other words, we know that (with high probability when and is relatively large, and a is relatively small)
2²
o²
(==1)
wi
+
2 m
m
(1 mm,
52


Reviews:
[{"review_id": "ni1xVRVGQNa", "reviewer": "Reviewer_LapN", "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 gives the test risk guarantee on the minimum $\\ell_2$ norm zero-loss solution (via combination of Lemma 1 and Theorem 1), which is where overparameterized model converges to via SGD. The bound, when simplified, leads to several interesting observations such as double descent via task diversity. Authors also provide results that support the relative tightness of the provided bound.", "summary_of_the_review": "The contribution of the paper is not very clear in comparison with the prior work; a head-to-head comparison is much needed.", "strength_and_weaknesses": "__Strength__\n- The technical quality of the result is clear, and the proof seems to be correct (but I could be wrong, as did not have enough time to go over the full derivation line-by-line, especially Appendix G).\n- The writing is clear overall, stating the assumptions and the setting in a rigorous manner.\n- The paper gives a very detailed discussion on the implication of the bound.\n\n__Weakness__\n- An explicit head-to-head comparison with the prior work is much needed. Although the paper already gives some discussions regarding the prior work in the introduction (and against Bernacchia (2021) in p6), it is still not super clear to me why Theorem 1 is an improvement over the previous results other than Bernacchia's. I am curious how the bound compares with Chen et al. (2022), especially because the criticism is that their bound is \"not in an explicit form (due to unknown quantities)\" and \"tightness of the bound is unclear.\" Regarding the former criticism, I think the same comment can be given to Theorem 1, as it contains the terms regarding the true model parameter $\\mathbf{w}_0$ and other constants from assumptions (which are usually not explicitly known but should be estimated). Perhaps including a big table for comparison, similar to that appearing in Chen et al., would be a good idea.\n\n- Related to the previous point, this paper considers a slightly different framework than previous works. Namely, the framework has a additional parameter $s$ to denote the true degree of freedom as opposed to the nominal dimensionality. I am curious how the provided result compares to the prior results when $s = p$ (please correct me if I missed something).\n\n- Tightness of the bound is part quite difficult to follow. Exactly how good is the approximation (e.g., the ratio between the upper and lower bound)? I recommend using cruder and simpler approximations to the weights regarding $p, m, n_v$ for the sake of clarity.\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "mifzX5O7hXv", "reviewer": "Reviewer_uCi7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes the sample complexity and error bound for MAML applied on linear meta-learning problem. While the features are iid and the tasks apply a subset of features, one can learn the useful features and apply them for downstream learning. The overfitting would not hurt generalization.", "summary_of_the_review": "I believe the paper is solid in theory and justifies an important problem. However I have a few confusions regarding the insight of the results, and whether they are too restrictive in the scenario that the RHS of the probability bound is larger than zero. I would like to see authors' comment and consider adding on the score.\n\n=============== Update ===============\n\nScore changed to 6 after first round response.", "strength_and_weaknesses": "Although the model is only linear case, I think the result is important for a first step of understanding the MAML. The proof is solid. Questions in detail:\n- In Theorem 1, if $n_t$ is small, $m$ or $n_v$ is large, then the RHS is smaller than zero. Does it mean, if $b_{w_0}$ and $b_w^{ideal}$ are both positive, then RHS of Thm. 1 is always positive? It is still a bit confusing. Intuitively, we need a few data for test phase, but typically as long as it’s larger than $s$ the number of features, the error should be small if you can identify the useful features in previous stages. But I did not see the explicit dependence on $s$. More importantly, why do more training tasks and validation samples hurt the probability, shouldn’t more data mean better learning performance?\n- I think the above issue also appears in Prop. 4-6.  \n- Eq(2), should it be $X^{r^T}$?\n- Eq(4) and the text below: $\\hat w$ was defined in Eq(3), is it switched to the parameter that minimizes validation error? If so, it would be better to use another notation. \n- Could you have a corollary for the case $w_s^0 = 0$ and a discussion? I'm interested in separating the role of mean and covariance in the bound.\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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "MymNwkTIR5D", "reviewer": "Reviewer_Akh7", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This work examines the generalization error and model error of single-step MAML in the mixed linear regression task. Unlike prior works, this work explicitly considers optimization in the over-parameterized regime, and derives model-error bounds in the non-asymptotic regime. Through theoretical derivations, the authors suggest that overparameterization tends to be beneficial, especially when task diversity and difficulty is high.", "summary_of_the_review": "While some additional experimental verifications (or rather illustrations) would improve the absorbability of this work, I believe that this work makes solid theoretical contributions to our understanding of meta-learning, and therefore I would recommend acceptance.", "strength_and_weaknesses": "\nOverall, the results proved in this paper are significant for demonstrating the benefits of overparameterized meta-learners, though the typical asterisks associated with the mixed-linear regression task and Gaussian features persist. The paper feels complete, but I find two factors that leave me wanting: \n\n1. Bernacchia(2021) leverages NTK theory to extend their analysis to non-gaussian and non-linear settings. Could similar techniques be used to extend your results to infinite-width settings? A road map highlighting results and propositions required to bridge this gap could contribute greatly to a discussion section.\n\n2. In showing the tightness of the bound in theorem 1, can you provide some numerical examples under some concrete sets of system parameters, and present it through visualizations? The tightness of the bounds in propositions 4 and 5 are quite difficult to contextualize as is. Space can certainly be found to present such figures, if not in at least in the appendix?\n\n3. In your setting, an assumption seems to be that the true features are a subset of the chosen features? Can you comment on what would happen if you incorporate a “misspecification” term into the analysis, i.e. where some true features are omitted?\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": "Not applicable"}, "extra_text": {}}, {"review_id": "H_SRhy0JkE", "reviewer": "Reviewer_3kzv", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 studied benign overfitting and double descent phenomenon in Meta-learning. Their analysis is based on linear regression with Gaussian features. In particular, they characterize the descent curve of the model error for the overfitted min l2-norm solution and show the phenomenon would be quite different compared to the single task (non-meta learning) setting. ", "summary_of_the_review": "This paper studied benign overfitting and double descent phenomenon in Meta-learning. I think this paper is well written, but currently, I can only give a weak acceptance because I have the following concerns, \n\nI am very interested in the messages delivered in section 3.2. I am convinced that such phenomena exist in the synthetic data distribution, but do they also exist for NNs in real applications?  Some experiments for real data or relevant literature may help a lot. \n\nOne of the most significant double descent phenomena for a single task is for epochs (iterations). What will happen for Meta-learning? The authors may want to add some comments.\n\nIn this paper, the authors studied the train-validation split method. What will happen for the train-train split method? Will the main results change, or remain the same?\n\n", "strength_and_weaknesses": "It is interesting to check whether benign overfitting and double descent phenomena exist in Meta-learning. The theoretical result is supported by comprehensive and technically strong proof. However, more evidence is needed to see whether such a finding also exists in a real application. ", "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": "4: The contributions are significant, and do not exist in prior works.", "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