Guarantees for Tuning the Step Size using a Learning-to-Learn Approach
Authors: Xiang Wang
Shuai Yuan
Chenwei Wu
Rong Ge
Venue:  (2021)
Keywords: meta-learning
learning-to-learn
step size tuning
optimization
generalization

Abstract: Learning-to-learn---using optimization algorithms to learn a new optimizer---has successfully trained efficient optimizers in practice. This approach relies on meta-gradient descent on a meta-objective based on the trajectory that the optimizer generates. However, there were few theoretical guarantees on how to avoid meta-gradient explosion/vanishing problem, or how to train an optimizer with good generalization performance. In this paper, we study the learning-to-learn approach on a simple problem of tuning the step size for quadratic loss. Our results show that although there is a way to design the meta-objective so that the meta-gradient remains polynomially bounded, computing the meta-gradient directly using backpropagation leads to numerical issues that look similar to gradient explosion/vanishing problems. We also characterize when it is necessary to compute the meta-objective on a separate validation set instead of the original training set. Finally, we verify our results empirically and show that a similar phenomenon appears even for more complicated learned optimizers parametrized by neural networks.

Under review as a conference paper at ICLR 2021
GUARANTEES FOR TUNING THE STEP SIZE USING A TARRINGGTO-LEENEE APPROACH
Anonymous authors Paper under double-blind review
ABSTRACT
Learning-to-leant using optimization algorithms to learn optimizer- has successfully trained efficient optimizers in practice. This approach relies on meta- gradient descent meta-objective based on the trajectory that the optimizer generates. However, there were few theoretical guarantees on how to avoid meta- gradient explosion/vanishing problems, or how train optimizer with good generalization performance. In this paper we study the learning-to-lcary ap- proach on simple problem of tuning the step size for quadratic loss. Our results show that although there is a way to design the meta-objective so that the meta- gradient remain polynomially bounded, computing the meta- meta-gradient directly us- ing backpropagation leads to numerical issues that look similar to gradient explo- sion/vanishing problems. We also characterize when the meta-objective on separate validation set instead of the original training set. Finally, we verify our results empirically and show that a similar phenomenon ap- pears even for more complicated learned optimizers parametrized by neural net- works.
necessary to compute
INTRODUCTION
Choosing the right optimization algorithm and related hyper-parameters is important for training a deep neural network. Recently, series of works (e.g., Andrychowicz et al. (2016); Wichrowska et al. (2017)) proposed to use learning algorithms to find better optimizer. These papers use learning-to-lean approach: they design a class of possible optimizers (often parametrized by a neural network), and then optimize the parameters of the optimizer (later referred to as meta- parameters) to achieve better performance. We refer to the optimization of the optimizer as the meta optimization problem, and the application of the learned optimizer as the inner optimization problem. The learning-to-learn approach solves the meta optimization problem by defining meta- objective function based on the trajectory that the inner-optimize generates, and then using back- propagation to compute the meta-gradient (Franceschi et al., 2017).
Although the learning-to-leamn approach has shown empirical success, there are very few theoreti- cal guarantees for learned optimizers. In particular, since the optimization for meta-parameters is usually nonconvex problem, does it have bad local optimal solutions? Current ways of optimizing meta-pares peta-parameters rely on unrolling the trajectory of the inner-optimizer, which is very expensive and often lead to applodingvaanihing gradient problems. Is there way to alleviate these problems? Can we have provable way of designing meta-objective to make sure that the inner optimizers can achieve good generalization performance?
In this paper we answer some of these problems in a simple setting, where we use the learning- to-learn approach to tune the step size of the standard gradient descent/stochastic gradient descent algorithm. We will see that even in this simple setting, many of the challenges still remain and we get better learned optimizers by choosing the right meta-objective function. Though our results are proved only in the simple setting, we empirically verify the results using complicated learned optimizers with neural network parametrizations.

---

Under review as a conference paper at ICLR 2021
1.1 CHALLENGES OF LEARNING-TO-LEAN APPROACH AND OUR RESULTS
Metz et al. (2019) highlighted several challenges in the meta-optimization for learning-to-leam ap- proach. First, they observed that the optimal parameters for the learned optimizer (or even just the step size for gradient descent) can depend on the number of training steps t of the inner-optimization problem, which is also observed by Wu et al. (2018). Ge et al. (2019) theoretically proved this in least-squares setting. Because of this, one needs to ensure that the inner training has enough number of steps (similar to the number of steps that it would take when apply the learned optimizer). However, when the number of steps is large, the reta-gradient can often explode or vanish, which makes it difficult to solve the meta-optimization problem.
Our first result shows that this is still true in the case of tuning step size for gradient descent on a simple quadratic objective. In this setting, we show that there a unique local and global minimizer for the step size, and we also give a simple way to get rid of the gradient explosion/vanishie problem.
Theorem (Informal). For tuning the step size of gradient descent on quadratic objective, if the meta-objective is the loss of the last iteration, then the meta- peeta-gradient can explode/vanish. If the meta-objective is the log of the loss of the last iteration, then the meta- veetaggaddent is polynomially bounded. Further, doing meta-grades veeta-grddient descent with meta step size of 1/VK (where k is the number of meta- peati-gradiett steps) provably converges to the optimal step size for the inner optimiep
Surprisingly, even though taking the log of the objective solves the gradient explosion/vanishingg problem, one cannot simply implement such an algorithm using auto-differentiation tools such as those used in TensorFlow (Abadi al., 2016). The reason is that even though the meta-gradient is polynomially bounded, if we compute the meta-gradient using the standard back-propagation algo- rithm, the meta-gradient will be the ratio of two exponentially large/small numbers, which causes numerical issues. Detailed discussion for the first result appears in Section 3 (Theorem 3 and Theo- rem 4).
The generalization performance of the learned optimizer is another challenge. If one just tries to optimize the performance of the learned optimizer on the training set (we refer to this as the train- by-train approach), then the learned optimizer might overfit. Metz al. (2019) proposed to use train-by- rrin-by-validattin approach instead, where the meta-objective is defined to be the performance of the learned optimizer on separate validation set.
Our second result considers a simple least squares setting where y = (w" .x) + and É ~ (00 o²). We show that when the number of samples is small and the noise is large, it is important to use train-br hiin-by-validation while when the number of samples is much larger train- muin-by-train can also Iearn a good optimizer.
Theorem 2 (Informal). For a simple least squares problem in d dimensions, if the number of samples is a constant fraction of d (e.g.. d/2), and the samples have large noise, then the train-by-trant ap- proach performs much worse than train- seiin-b--vall validattion On the other hand, when number of samples n is large, train- train-by-train can get close to error do? /n, which is optimal.
We discuss the details in Section 4 (Theorem 5 and Theorem 6). In Section 5 we show that such observations also hold empirically for more complicated learned optimizers-an optimizer parametrized by neural network.
1.2
RELATED WORK
Learning-to-learn for supervised learning Hochreiter et al. (2001) introduced the application of gradient descent method to meta-learning. The idea of using a neural network to parametrize an optimizer started Andrychowicz et al. (2016), which used an LSTM to directly learn the update rule. Before that, the idea of using optimization to tune parameters for optimzers also appeared in Maclaurin et al. (2015). Later, Li & Malik (2016); Bello et al. (2017) applied techniques from reinforcement learning to learn an optimizer. Wichrowska al. (2017) used hierarchical RNN as the optimizer. Metz et al. (2019) adopted a small MLP as the optimizer and used dynamic weighting of two gradient estimators to stabilize and speedup the meta-training process.
2

---

Under review as a conference paper at ICLR 2021
Learning-to- in other settings Ravi & Larochelle (2016) used LSTM as a meta-learner to learn the update rule for training neural networks in the few-shot learning setting, Wang et al. (2016) learned RL algorithm by another meta-leariing RL algorithm, and Duan et al. (2016) learned general-purpose RNN that can adapt to different RL tasks.
Gradient-based meta-learning Finn et al. (2017) proposed Model-Agnostic Meta-Learning (MAMI.) where they parameterize the update rule for network parameters and learn a shared ini- tialization for the optimizer using the tasks sampled from some distribution. Subsequent works generalized or improved MAML, c.g., Rusu et al. (2018) Iearned a low-dimensional latent repre- sentation for gradient-based meta-learning, and Li et al. (2017) enabled the concurrent learning of learning rate and update direction. Chen et al. (2020) studied a model with an optimization solver stacked another neural component. They computed Rademacher complexity of the model, but didn't give any optimization guarantee or study train-by-train versus train-by-validation
Learning assisted algorithms design Similar ideas can also be extended to develop a meta- algorithm selecting an algorithm from a family parametrized algorithms. Gupta & Roughgarden (2017) first modeled the algorithm-selection process as statistical learning problem and bounded the number of tasks it takes to tune a step size for gradient descent. However, they didn't t consider the meta-optimization problem. Based on Gupta & Roughgarden (2017), people have developed and analyzed the meta-algorithms in many problems (Balcan et al., 2016; 201 8a;c;b; Denevi et al., 2018; Alabi et al., 2019; Denevi et al., 2019)
Tuning step size/step size schedule for SGD Shamir Zhang (2013) showed that SGD with polynomial step size scheduling can almost match the minimax rate in convex non-smooth settings, which was later tightened by Harvey et al. (2018) for standard step size scheduling. Assuming that the horizon T is known to the algorithm, the information-theoretii smooth setting was later achieved by Jain et al. (2019) which used another step size schedule, and Ge et al. (2019) showed that exponentially decaying step size scheduling achieve near optimal rate for least squares regression. There are also a line works that investigate methods which adapt vector of step sizes (Sutton, 1992; Schraudolph, 1999; Kearney al., 2018; Günther et al., 2019; Jacobsen et al., 2019).
optimal bound in convex non-
PRELIMINARIES
In this section, we first introduce some notations, then formulate the learning-to-lee le-r framework.
2.1 NOTATIONS
For any integer n, use [n]] to denote 21, m). We use |-||| denote the &g norm for vector and the spectral norm for a matrix. We use () to denote the inner product of two vectors. For symmetric matrix A E Raxd the d-dimensional identity matrix as la- We also denote the identity matrix simply as I when the dimension is clear from the context. We use 0(+), Q(-), hide constant factor dependencies. We use poly(-) to represent polynomial on the relevant parameters with constant degree. We say an event happens with high probability if it happens with probability for small constant c.
denote its eigenvalues
(A)
2 Aa(A). We denote
2.2 LEARNING-TO-LEAN FRAMEWORK
We consider the learning-to- learn approach applied to training a distribution of learning tasks. Each task specified by tuple (D, Stann Syana, E). Here D is distribution of samples in X Y. where X is the domain for the sample and Y is the domain for the label/value. The sets Smain and Syali are samples generated independently from D, which serve as the training and validation set (the validation set is optional). The learning task looks to find parameter w E W that minimizes the loss function f(w, œ, y) W X X X Y + R. which gives the loss of the parameter w for sample (r,y). y). The training loss for this task is f(w) = Sean
l(w, x, y), while the population E (8.
loss is fww B((.))-(((((e
3

---

Under review as a conference paper at ICLR 2021
The goal of inner-opiimization is to minimize the population loss f(w). For the learned op- timizer, we consider it as an update rule u(.) on weight w. The update rule is a parame- terized function that maps the weight at step and its history to the step + 1 W u(w,, Vf(w)), ff(w,-)).-- -..-- ;0). In most parts of this paper, we consider the update rule as gradient descent mapping with step size as the trainable parameter (here 0 = 7) which is the step size for gradient descent). That is, (n)ww = w f for gradient descent and W, (w)) = w - - VnV x; y) for stochastic gradient descent where (æ, v) is a sample randomly chosen from the training set Suain.
In the outer (meta) level, we consider a distribution T of tasks. For each task P~ T, we can define meta-loss function A P). The meta-loss function measures the performance of the optimizer on this learning task. The meta objective, for example, can be chosen the target training loss f at the last iteration (train-by-train) or the loss on the validation set (train-yy-validation).
The training loss for the meta-level is the average of the meta-loss across m different specific tasks mn Σx= A(0, Pt). The population loss for the meta-level is the
P2..., Pm. that is, (() 1 expectation over all the possible specific tasks F(0) = Er-T (0,, P)].
In order train an optimizer by gradient descent, we need compute the gradient of meta-objective F in terms of meta parameters 0. The meta parameter is updated once after applying the optimizer on the inner objective / times to generate the trajectory wo, Wi,.... Wir The meta-gradient is then computed by unrolling the optimization process and back- mack-propagating through the / applications of the optimizer. As we will see later, this unroll procedure is costly and can introduce meta-gradient explosion/vanishing problems.
3 ALLEVIATING GRADIENT EXPLOSION/VANISHIVG PROBLEMS
First we consider the meta- vetaa-gradeet explosion/vamishing problem. More precisely, we say the meta- gradient explodes/vanishes if it exponentially large/small with respect the number of steps of the inner-optimizer.
In this section, we consider very simple instance of the learning- to-leem approach, where the distribution T only contains single task P. and the task also just defines a single loss function f'. Therefore, in this section [()) F(n) An,, P). We will simplify notation and only use (1).
The inner task P is a simple quadratic problem, where the starting point fixed at wo, and the loss function is (w) _/o' Hw for some fixed positive definite matrix H. Without loss of general- ity, assume We has unit lg norm. Suppose the eigenvalue decomposition of is Σi= Apu,u, >a(H) are the largest and smallest eigen- values of H with T, > a. For each i E [d], let 6 be (wo, uz) and let Gain = min(lea), |, leal). We assume Cuin > 0 for simplicity. Note that if wo is uniformly sampled from the unit sphere, with high probability Cmin is least ((I/vd); if H is XXT with X E Rdx2dd as a random Gaussian matrix, with constant probability, both a and L - a are at least Md)).
Throughout this section we assume L = AH(H) and
Let } be the GD sequence running on (w) starting from wo with step size 1/. We consider several ways of defining meta-objective, including using the loss of the last point directly, or using the log of this value. We first show that although choosing (n) f does not have any bad local optimal solution, it has the gradient explosion/vanishing problem. We use F'(n) to denote the derivative of F in 1).
2 Theorem 3. Let the meta objective be f()) = f(w.,,) = L.,TT, H...H We know F(r) is a strictly
convex function in 17 with an unique minimizer. However, for any step size n < 2/L, | S
E = c?A 1 1,2112t11111 12 any step size > 2/ L, [f)(m) 2 2 22 - 1) L2t.
Note that in Theorem when 7) < 2/L, [f)( is exponentially small because |1 ./yya < 1 for all i E [d]: when 7) >>> 2/L. (')n)) is exponentially large because qyT. > 1. Intuitively, gradient
In the notation of Section 2, one can think that D contains single point (0, 0) and the loss function f(w) f(v, 0, 0).
4

---

Under review as a conference paper at ICLR 2021
explosion/vamishing happens because the meta-loss function becomes too small or too large. A natural idea to fix the problem is to take the log of the meta-loss function to reduce its range. We show that this indeed works. More precisely, if we choose F(n) = log (wet.) then we have
Theorem 4. Let the meta objective be ((n) = log (( We know F(n)) has a unique minimizer T and (1) = O a(L-a)) for all 2 O. Let {mk} be the GD sequence running on f with miin
1,3
meta step size PK =1/ Vk. Suppose the starting step size no S M. Given any 1/T. 0, there exists k' 2 poly Genin L, - such that for all k 2 k', Ims 171 S.
For convenience, in the above algorithmic result, we reset to zero once goes negative. Note that although we show the gradient is bounded and there is unique optimizer, the problem of optimizing is still not convex because the meta- eeta-gradient is not monotone. We use ideas from quasi-convex optimization to show that meta-gradient descent can find the unique optimal step size for this problem.
Surprisingly, even though we showed that the meta-gradient bounded, it cannot be effectively computed by doing propparoongttion due to numerical issues. More precisely:
Corollary 1. If we choose the mete-objective as F(n) = & log f(w,,)) when computing the meta- gradient using back- pock-propagation, there are intermediate results that exponentially large/small in number of inner-steps steps t.
Indeed, in Section 5 we empirically verify that standard auto-differentiation tools can still fail this setting. This suggests that one should be more careful about using standard back- propagation in the learning-to-lee to-larn approach. The proofs of the results in this section are deferred into Appendix A.
4 TRAIN-BY-TRAIN VS. TRAIN-BY --VLIIAATIO
Next we consider the generalization ability of simple optimizers. In this section consider a simple family of least squares problems. Let T be distribution of tasks where every task (D(w") Smann Svalid, E) determined by a parameter w" E Rd which is chosen uniformly at ran- dom on the unit sphere. For each individual task, (I,y) ~ D(w") ) is generated by first choosing (O, Ia) and then computing y/ (w", .x) + where & NV0. o²) with o 1. The loss function f(w, x, y) is just the squared loss f(w, 2, z) v) = 1/4 (v (w, x² That is, the tasks are just standard least-squares problems with ground-truth equal to w" and noise level 0².
For the meta-loss function, we consider two different settings. In the train-by-train setting, the training set Suain contains n independent samples, and the meta-loss function is chosen to be the training loss. That is, in each task P, we first choose w" uniformly at random, then generate (I1, 31 ...,,.., (In,yn) as the training set Sminn The meta-loss function ATVT()) (11, P) is defined be
2n Σ (M (We,, x.))²²
Here Wt,a is the result of running iterations of gradient descent starting from point 0 with step size 7). Note we truncate sequence and declare the meta loss is high once the weight norm exceeds certain threshold. We can safely do this because norm, so if the weight norm of our model is too high, it means the inner training has diverged and the step size is too large. Specifically, if at the 7-th step, ||W,,y|l || > 40o, we freeze the training this task and set Wy',, = 40 for all r < 7' S t. for some arbitrary vector u with unit norm. Setting the weight to large vector is just one way declare the loss is high; we choose this particular way for some proof convenience.
assume the ground truth weight w" has unit
As before, the empirical meta objective in train-by-train setting is the average of the meta-loss across m different specific tasks Pı, Pa.... Pm.. that is,
m ATSTGO (1. Px).
FToT(n)()) = m R
(1)
5

---

Under review as a conference paper at ICLR 2021
In the train- saiin-by--aldattion setting, the specific tasks generated by sampling nı training samples and ne validation samples for each task, and the meta-loss function is chosen to be the valida- tion loss. That is, in each specific task P. first choose w uniformly at random, then generate (I1, 31), v1),.., (Iny yn, ) as the training set Strain and (rf, yf), (F : as the validation set Svalid- The meta-loss function TTViin (mimm)))) m2) P) is defined to be
n2
(roV(n (1: P)
Σ (1l - -mmm,))))))
2n2
Here again W is the result of running iterations of the gradient descent on the training set starting from point O, and use the same truncation before. The empirical meta objective is defined
FraV (7)
(m1 Pk),
(2)
where each Ps is independently sampled according the described procedure.
We first show that when the number samples is small (in particular n < d) and the noise is large enough constant, train-by- -aii-by-train can be much worse than toin-by-valldatten (the total number of samples used in rrain-y--validatin is the same as -ain-by-trrai)
even when n1 +
Theorem 5. Let PrOT(N) (n) and FTo m2) m2) (1) be as defined in Equation (1) and Equation (2) respectively, Assume n. n1, n22 E [d/4, 3d/4]. Assume noise level a is large constant Ct. Assume unroll length 2 Cg number of training tasks 2 cy log(mtt and dimension d 2 e4 log(mt) for certain constants C2, Ca. C4. With high probability in the sampling of training tasks, we have
Mrain (1) and We.nim - w == = 12(1)02
for all Mrain E arg min F Froz(m)(()) (11):
Vialid = ((1/t) and IE al - w011== || 112 9(1)
for all Walii E arg min FrE (m) (T). In both equations the expectation is taken over new tasks.
Note that in this case, the number of samples is smaller than d, so the least square problem is under- determined and the optimal training loss would go to O (there is always a way to simultaneously satisfy all equations). This is exactly what train-by-train would do it will choose a large constant learning rate which guarantees the optimizer converges exponentially to the empirical risk minimizer (ERM). However, when the noise is large making the training loss go to O will overfit the noise and hurt the generalization performance. learning rate which allows it to leverage the information in the training samples without overfitting to noise. Theorem is proved in Appendix B. We also prove similar results for SGD in Appendix D
brain-by-validation on the other hand will choose smaller
We emphasize that neural networks often werrpparamtterized which corresponds to the case when d > n. Indeed Liu & Belkin (2018) showed that variants of stochastic gradient descent can converge the empirical risk minimizer with exponential rate in this case. Therefore in order to train neural networks, it is better to use vrii-by-validation. On the other hand, we show when the number of samples is large (n >> d), train-by-train can also perform well.
Theorem 6. Let Frer(w) (1)) be as defined in Equation 1. Assume noise level a constant et- Given unroll length t 2 02 log( (og())) number of training tasks m 2 San² log( (nm and dimension d 2 et for certain constants c, 022 C3 Cg. With
any 1 > 0, assume training set size n Z ad log( ed
pm
ed high probability in the sampling of training tasks, we have
2
E Bll =n < (1
n
for all Mirin arg migg20 Fror(H) (n), where the expectation is taken over new tasks.
Therefore if the cearning-to-lents approach is applied to traditional optimization problem that not over- wee--araaettriized, train-by-train can work well. In this case, the empirical risk minimizer (ERM) already has good generalization performance, and vain-by-train optimizes the convergence towards the ERM. We defer the proof of Theorem into Appendix C.

---

Under review as a conference paper at ICLR 2021
5 EXPERIMENTS
Optimizing step size for quadratic objective We first validate the results in Section 3. We fixed a 20-dimensional quadratic objective as the inner problem and vary the number of inner steps t and initial value 7)o- We compute the meta-gradient directly using a formula which we derive in Appendix A. In this way, we avoid the computation of exponentially small/large intermediate terms. We use the algorithm suggested in Theorem 4, except we choose the meta-step size to be 1/(100v the constants in the theorem were not optimized.
An example training curve of for t = 80 and тo 0.1 is shown in Figure 1, and we can see that ?) converges quickly within 300 steps. Similar convergence also holds for larger or much larger initial 77. In contrast, we also implemented the meta- traininiinggg with Tensorflow, where the code was adapted from the previous work of Wichrowska al. (2017). Experiments show that in many settings (especially with large & and large 1))) the implementation does not converge. In Figure 1, under the TensorFlow implementation, the step size is stuck at the initial value throughout the meta training because the meta gradient explodes and gives NaN value.
In Figure 2, we verify the observation from Metz al. (2019) that the optimal step size depends on inner training length.
0.031
Tensorflow
Optimal
0.03
G0
0.029
0
100
200
300
50
100
150
Meta steps
Inner training length t
Figure 1: Training 17 (f 80, 7o 0.1)
Figure 2: Optimal 17" for different t
Train-by-train train-by-validation, synthetic data Here validate theoretical results in Section 4 using the least-squares model defined there. We fix the input dimension to be 1000.
In the first experiment, fix the size of the data (n 500 for train-by-trainn 71 n2 250 for train-by-validationn.. Under different noise levels, we find the optimal 1y by a grid search on its meta-objective for train-by-train and train-by-validation settings respectively. We then the optimal vy found in each of these two settings to test on 10 new least-squares problem. The mean RMSE, well its range over the 10 test cases, are shown in Figure 3. We can see that for all of these cases, the crii-by-trring model overfits easily, while the train-by-validation model performs much better and does overfit. Also, when the noise becomes larger, the difference between these two settings becomes more significant.
6
TOT
T
TDT
RMSE (train)
ToV
RMSE (test)
TbV
4
2
0
0
2
3
3.
4
Figure 3: Training and testing RMSE for different o values (500 samples)
In the next experiment, fix 1 and change the sample size. For train- baain-by-validation we always split the samples evenly into training and validation set. From Figure 4, we can see that the gap between these two settings is decreasing
more data, as expected by Theorem 6.

---

Under review as a conference paper at ICLR 2021
2
TbT
ToT
RMSE (train)
1.5
Tbv
RMSE (test)
1.5
Tav
1
0.5
0.5
0
2500
5000
7500
10000
2500
5000
7500
10000
Sample size
Sample size
Figure 4: Training and testing RMSE for different samples sizes
1)
Train-by-train vs. train-by-validation, MLP optimizer on MNIST Finally we consider more complicated multi-layer perceptron (MLP) optimizer on MNIST data set. We use the same MLP optimizer as in Metz et al. (2019), details of this optimizer is discussed in Appendix F. As the inner problem, we use a two-layer fully-connected network of 100 and 20 hidden units with ReLU activations. The inner objective the classic 10-class cross entropy loss, and we use mini-batches of 32 samples at inner training. In all the following experiments, use SGD a baseline with step size tuned by grid search against validation loss.
To see whether the comparison between train-by-train and train-by-validation behave similarly to our theoretical results, we consider different number of samples and different levels label noise. For each optimizer, evaluation. The plots show the mean of the 5 tests. We didn't show the measure of the spread because the results of these 5 tests will not be readable in the plots.
independent tests and collect training accuracy and test accuracy for
close to each other, such that the range standard deviation marks
First, consider optimizing the MNIST dataset with small number of samples. In this case, the train- by-train setting uses 1,000 samples (denoted as "TbT "TbT1000"), and we use another 1 1,000 samples as the validation for the rean-by-vallddtion case (denoted "TbV 1000+1000" To be fair train- by-train we also consider TbT2000 where the train- train-by-train by-train algorithm has access to 2000 data points. Figure shows the results all the models have training accuracy close but both ТьT1000 and TbT2000 overfits the data significantly, whereas TbV1000++00 performs well.
Th:T1000
Accuraay (tran))
0.95
0.55
TEN10033-1000
TUT2000
Accuraay
SCD
0.85
1611000
0.55
TO72060
0
500
1006
1500
2000 Staps
2500
3000
3500
4000
500
10000
1500
2000
2500
3000
3500
4000
Steps
Figure 5: Training and testing accuracy for different models (1000 samples, no noise)
To show that when the noise is higher, the advantage of vaaiddao-vl increases, we keep the same sample size and consider "noisier" version MNIST, where we randomly change the label of sample with probability 0.2 (the new label is chosen uniformly at random, including the original label). The results are shown in Figure 6. We can see that both train-by-train models, as well as SGD, overfit casily with training accuracy close and their test performances are low. The train-by- validation model performs much better.
Finally we run experiments on the complete MNIST data set (without label noise). For the train-by- validation setting, we split the data set to 50,000 training samples and 10,000 validation samples. As shown in Figure 7. in this case train-by-train and -aalidattliiittion performs similarly (in fact both are slightly weaker than the tuned SGD baseline). This shows that when the sample size is sufficiently large, train-by-train can get comparable results as vaaa-by-aliidaiion
8

---

Under review as a conference paper at ICLR 2021
TST1000
Accurscy Itaie)
Acouracy (tea))
T1V1000+1000
T012300
0.7
0.7
8GD
TST1000
ToT0000
500
1000
1500
2030
2500
3000
3030
4003
0
500
1000
1930
2000
2500
3000
3500
4000
Figure 6: Training and testing accuracy for different models (1000 samples, 20% noise)
0.90
0.88
Acouracy (tain)
0.96
Acquray
0.90
1E:000200
TEV90200- 10000
TLV55000-1000 10000
0.5
1.5
2.5
3.5
0.5
1.5
2.5
35
Steuse
Steps
Figure 7: Training and testing accuracy for different models (all samples, noise)
CONCLUSION AND FUTURE WORKS
In this paper, we have proved optimization and generalization guarantees for tuning the step size quadratic loss. From optimization perspective, we considered simple task whose objective is quadratic function. We proved that the meta-gradient can explode/vanish if the meta-objective is simply the loss of the last iteration; we then showed that the log-transformed meta-objective has polynomially bounded meta-gradient and can be successfully optimized. To study the generalization issues, we considered the least squares problem. We showed that when the number samples is small and the noise is large, train-by-validation approach generalizes better than train-by-train while when the number of samples large, train-by-train can also work well. Although our theoretical results are proved for quadratic loss, this simple setting already yields interesting phenomenons and requires non non-trivial techniques to analyze. We have also verified our theoretical results on an optimizer parameterized by neural networks and MNIST dataset.
Since this is very first work studying the learning to learn approach, there are many potential future works. One immediate future work to extend the result for least squares log-transformed meta objective (as in Section 3). This is probably doable because compositing the log function with the current meta-objective should not change its minimizer. For the least squares problem, we only studied the generalization properties of the optimal step size under the meta-objective, it's unclear if meta-gradien gradiegt descent can converge to such an optimal step size. We believe our techniques for meta-optimization of the simple quadratic objective function (Section 3) can also be useful in this analysis. More broadly, we are also interested in analyzing more complicated optimizers on more complicated tasks.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, al. Tensorflow: system for large- scale machine learning. In /2th USENIX Symposium on Operating Systems Design and Imple- mentation (OSDI 16), pp. 265 283, 2016.
Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, and Ellen Vitercik. Learning to prune: Speeding up repeated computations. arXiv preprint arXiv:1904.11875. 2019.
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in neural information processing systems, pp. 3981-3989, 2016.
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. -choeic-tt thhooreti foundations of algorithm configuration for combinatorial partitioning problems. arXiv preprint 1o1 2016.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. arXiv preprint 1803 2018a.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 603-614. IEEE, 2018b.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complex- ity for multi-item profit maximization. Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 173-174, 2018c.
Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoe V Le. Neural optimizer search with reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 459 468. JMLR. org, 2017.
Xinshi Chen, Yufei Zhang, Christoph Reisinger, and Le Song. Understanding deep architectures with reasoning layer. arXiv preprint arXiv:2006. 134001,10,,4,,, 2020.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to- learn with statistical guarantees. arXiv preprint arXiv: /803.0808, 2018
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-lenn stochastic gradient descent with biased regularization. arXiv preprint arXiv:1903.10399 2019.
Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel. r12: Fast reinforcement learning via slow reinforcement learning. arXiv preprint
1.02799,, 2016.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1126-1135. JMLR. org, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. arXiv preprint / 2017.
Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. In Advances in Neural Information Processing Systems, pp. 14951-14962, 2019.
Johannes Günther, Alex Kearney, Nadia M Ady, Michael R Dawson, and Patrick M Pilarski. Meta- learning for predictive knowledge architectures: case study using tidbd on a sensor-rich robotic arm. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1967-1969, 2019.
Rishi Gupta and Tim Roughgarden. A pac approach to application-specife algorithm selection. SIAM Journal on Computing, 1613) 2017.
10

---

Under review as a conference paper at ICLR 2021
Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. arXiv preprint arXiv:1812.05217, 2018.
Sepp Hochreiter, A Steven Younger, and Peter Conwell. Learning learn using gradient descent. In International Conference on Artificial Neural Networks, pp. 87-94. Springer, 2001.
Andrew Jacobsen, Matthew Schlegel, Cameron Linke, Thomas Degris, Adam White, and Martha White. Meta-descent for online, continual prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3943-3950, 2019.
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. arXiv preprint arXiv: 12443, 2019.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, (6(189-206): 1984.
Alex Kearney, Vivek Veeriah, Jaden B Travnik, Richard S Sutton, and Patrick M Pilarski. Tidbd: Adapting lemporal-difference step-sizes through stochastic meta-descent. arXiv preprint arXiv:1804.03334 2018.
Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint wrXvvv1606.01885 2016.
Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-sgd: Learning to learn quickly for few- shot learning. arXiv preprint arXiv:1707.09833 2017.
Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for over-parameterized learn- ing. arXiv preprint arXiv:/810. 13395, 2018.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter optimiza- tion through reversible learning. In International Conference on Machine Learning, pp. 2113- 2122, 2015.
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training learned optimizers. In International Conference on Machine Learning. pp. 5556-4565, 2019.
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. 2016.
Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osin- dero, and Raia Hadsell. Meta-learning with latent embedding optimization. arXiv preprint arXiv:1807.05966. 2018.
Nicol Schraudolph. Local gain adaptation stochastic gradient descent. 1999.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In International conference on machine learning,
pp. 71-79, 2013.
Richard S Sutton. Adapting bias by gradient descent: An incremental version of delta-bar-delta, In AAAI, pp. 171-176. San Jose, CA, 1992.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. arXiv preprint arXiv: /6/ I.05633, 2016.
Olga Wichrowska, Niru Maheswaranathan. Matthew W Hoffman, Sergio Gomez Colmenarejo, Misha Denil, Nando de Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In Proceedings of the 34th International Conference on Machine Learning-Voie Volume 70, pp. 3751-3760. JMLR. org, 2017.
Yuhuai Wu. Mengye Ren, Renjie Liao, and Roger Grosse. Understanding short-horizon bias in stochastic meta-optimization. arXiv preprint arXiv:1803.000 2018.

---

Under review as a conference paper at ICLR 2021
In the appendix, first give the missing proofs for the theorems in the main paper. Later in Appendix F we give details for the experiments.
Notations: Besides the notations defined in Section we define more notations that will be used in the proofs.
For matrix E Raxd with S d, we denote its singular values as 01 2 on (X).
For positive semi-definite matrix E RRddd, we denote uTAu Au as ||u]] For matrix X E RRdx let Projx E Rdxd be the projection matrix onto the column span of X. That means, Projx = SST where the columns of S form orthonormal basis for the column span of X.
For any event ε, we use { to denote its indicator function: { equals 1 when & holds and equals 0 otherwise. We use & to denote the complementary event of E.
A PROOFS FOR SECTION 3 ALLEVIATING GRADIENT EXPLOSION/VANISHING PROBLEM FOR QUADRATIC OBJECTIVE
In this section, we prove the results in Section Recall the meta learning problem as follows:
The inner task is fixed quadratic problem, where the starting point is fixed at wo. and the loss function f(w) f Hw for some fixed positive definite matrix H Rdxd Suppose the eigenvalue decomposition of H is E A.u;u, In this section, we assume 1. = (H) and Aa( ()) are the largest and smallest eigenvalues of H with I, > a. We assume the starting point wo has unit & norm. For each i E [d], let c₁ be (wo, u.) and let Cmin min([c1], leal). We assume Cmin for simplicity, which satisfied if wo is chosen randomly from the unit sphere.
Let {Wr,)} } be the GD sequence running f(w) starting from wo with step size For the meta- objective, we consider using the loss of the last point directly, or using the log of this value. In Section A.1, we first show that although choosing F(n) = f(wa.,, does not have any bad local optimal solution, it has the gradient explosion/vanishiiiee problem (Theorem 3). Then, in Section A.2, log (w.,n) leads polynomially bounded meta-gradient and further show meta- -tttdierr descent converges to the optimal step size (Theorem 4). Although the meta- gradient is polynomially bounded, if we simply use pack-propogation compute the meta- gradieg,,,ent,, the intermediate results can still be exponentially large/small (Corollary 1). This is also proved in Section A.2.
show choosing (())=
A.1 META-GRADIENT VANISHING/EXPLOSION
In this section, we show although choosing F(1) = f(w.,,) does not have any bad local optimal solution, it has the meta-gradient explosion/vanishingg problem. Recall Theorem 3 as follows.
Theorem 3. Let the meta objective be (())) f(w..n) = -,T,,, We know F(n) is strictly convex function in with an unique minimizer. However, for any step size < 2/L, (n)) S E o 2 +
n/, 221-1 any step size 2/ T,, (F))) 2 1T 1) L.P.
Intuitively, if write Wt,r in the basis of the cigen-decomposition of H, then each coordinate evolve exponentially in t. The gradient of the standard objective is therefore also exponential in t.
Proof of Theorem 3. According to the gradient descent iterations, we have
Wt,g W1-1. 17 f = W1-1. 17 -1 = (--1H)en wH),,,1,1 (I nH) wa
Therefore, F(1) := f(w,n) fwo (I (H Hwo Taking the derivative of F(1).
d
F'(n) = -twp (I 7H) 21 H 2 = - Σ -
12

---

Under review as a conference paper at ICLR 2021
where C2 (Wo, uz) Taking the second derivative of F(1),
d
(n)) ((()))((2111))
- 1) (I 2
H = t(2t - 1)
Σ
m),,)
==1
Since L > a, have (T) > 0 for any 7). That means F(r) is strictly convex function in v with a unique minimizer.
For any fixed r/ E L) we know
1//:1l < 1 for all i [d] We have
d
('(n)
12
1 - . 2-1
1=1
For any fixed 17 E (2/L,, 20), we know nI. 1 > 1. We have
(n)
= =-1GLL2(1 17112-111
Σ
GXP(1 -
Σ
EAP(L - 1
150
(1))(110)))200
2
te
(nL 122t,
where the last inequality uses Σ 1 c3 1.
A.2 ALLEVIATING META-GRADIENT VANISHINC/EXPPLOSSOO
We prove when the the meta objective is chosen as 1 log f(wr,)), the meta- cetta-radient is polynomially bounded. Furthermore, we show meta-gradien descent can converge to the optimal step size within polynomial iterations. Recall Theorem 4 as follows.
Theorem 4. Let the meta objective be (n) log fwr.)) We know F(n) has unique minimizer c -(ma((Laa)) for all nj 0. Let {Tk} be the GD sequence running on F with
'f" and F'(n) =0
1.3
meta step size Pbk = 1/ L/. Suppose the starting step size Too S M. Given any 1/L > e > 0, there M
exists k' = 2 polyl c.... T., 2 such that for all k 2 K', |m 17' S..
When we take the log of the function value, the derivative of the function value with respect to becomes much more stable. We will first show some structural result F(n) it has unqiue minimizer and the gradient is polynomially bounded. Further the gradient is only close to when the point 17 is close to the unique minimizer. Then using such structural result prove that meta- gradient descent converges.
The proof consists of three claims. the first claim, we show that F has unique minimizer and the minus meta derivative always points to the minimizer. In the second claim, show that F has bounded derivative. In the last claim, we show that for any 7 that is outside the e-neighborhood of 11,,, [f)) is lower bounded. Finally, we combine these three claims to finish the proof.
Proof of Theorem
Claim 1. The meta objective F has only one stationary point that is also its unique minimizer 1f".. For any E (0.n*), F') < 0 and for any n E (o), f'(n) > 0. Furthermore, we know v7* E [1/L, 1/al.
We can compute the derivative of f in 17 as follows,
F'(n) -2w, (I H111 2111)22-1 H2 Dd G2 - 7
(3)
wil (1 (1 ) H4
Σd Gxr(1 12
It's not hard to verify that the denominator Ddd e - 11,,)22 always positive. Denote the
numerator -2 -i (1 m as g(n). Since g' g()1) > 0 for any 1j E (0), we know g(n)
13

---

Duuin (M) Under review as a conference paper at ICLR 2021
is strictly increasing in т). Combing with the fact that g(0) < 0 and g(00) > 0, we know there is
unique point (denoted as 17") where (n7") = 0 and g(7) < for all E (0)"")) and g(n) > 0 for all
E (71,.00 0o). Since the denominator in (n) is always positive and the numerator equals g(n), we know there is unique point 1)" where ('"n"") 0 and (n) < 0 for all E 10, and (1) > 0
for all 1y E (n"", oo). It's clear that 17" is the minimizer of F.
Also, it's not hard to verify that for any 7f E [0,1/L), F'(n) < and for any n (1/a, oo), ('(n)) > This implies that 1f" E [1/L, 1/a].
Claim 2. For any 1, E (0), we have
4T3
[F'(T) - C aLL - a)
Dmax.
For any 1) E [0, a+L we have A S - 1j for all i. Dividing the numerator and denominator
in ('(n) by (1 1702)21 we have
[((] = 2
E of 1-
I- mjar
21-1
2 2
2 C.A² GalL- 1 a))
4T.3 cjalL - a))
<
2g
?
)2 Ti
cja(l na)
1i=1
T- ga
where the second last inequality uses 1) S
2
a+L.
Similarly for any 17 E ( (aft oo), we have |1 - mdTa S nn - 1 for all i. Dividing the numerator and
denominator in (1) by (n - 1)2t, we have
ES 222 -- 2
TT([L- < 2(a + 1) 2) GX
4L3 L a)
((()) 22 G Σ & ( L-nd )2r
GL(L aa)
where the last inequality uses 1 2 atl.
2
Overall, we know for any 1) 2 0,
41,3
413
(n)) S L L max
S
2ya ZI
a(L - a))
min
Claim 3. Given M 2 2/a and
1/L> ( <> for any 1) E 10 - uu + c, M,,, we have
[F min 2ec
L2c
2 2cc min min a 1
L (M
L
M2
If n E [0,n' -c c and 17 S a. we have
F(()) = -2 1 2 X2 17):)) 2 Ex G2f(1 - 1//:)) 21 E._ - A
Ei_
ΣS E Ac(1 - 1/>;)221
Σd C7 A1(1 - n72 )2
where the second equality holds because Σtn G22 17" 2x) 0. For the numerator, we have
Σ c A27(1 1/..) - Σ EXT(1 1( 2 zG3a² 2 ((1 - (100))) - (1 -1)"=)) -1²²a)((-1))
a0² 2 naaaaaa (1 na- ca) )00)2111
for the denominator, we have
Σ -
Σ c7 (1 n2)22
14

---

Under review as a conference paper at ICLR 2021
where the second inequality holds because |1 ny1sl 1 - 1ja for all i. Overall, have when
2
7 E [0, - <| and S a+L
('))) 22 Gga2 ((1 - 1/xx) 1/xx)(111 - (1 - 1/0x - -00)) 20-1
Di=1 c22,) E/
(1 nn)))2r
200za0
2c0 3
i= (2); (1 - 17(x))
L
where the last inequality holds because (1 - noxx)= S and ΣS G2 S L.
Similarly, if 17 E [0, 17"' - c) and 11 2
2 a+t. we have
('(n) 22 eg2L ((1 nL) 21 (1 nL 2L))(-1)
Eiz o2, (1- -
=2 G7L2 ((nb + el 1)21-1 (11L 1)2(-1)
E =2,)
(n 11)2-
2eG
220G 1,2
2 (I. a1)2
ES x2)) (nI.. - 1)2
where the last inequality holds because 1) S 11" - S 1/0 and ΣS G/ S L.
If 1 E [n) + 0,0) and 1 S a+L' we have
F'(m) 22 ega²² ((1 1ja + 1a)))-1-(111000 -(1-)))-2)-
E c?>,) (1 -1-10
(1-1a)20 12)220
2ccga3
L
If E [nn + 000 and 1) 2 a+L we have
('(m) 22 L6L ((1 - 71 + + n))2 - (1 -11))(-11)
(1 (1-1)1.)22
2c0 L33
L
2 (M - 1))
>L Ri=1 Ged)
(11 - 112
where the last inequality uses the assumption that 17 S M.
With the above three claims, F')) < 0 for any E [0, 17n)) and F'(n) > 0 for any 1) E 20). So the opposite gradient descent always points to the minimizer.
ready to prove the optimization result. By Claim know
Since μ4 = 1/Vk, when A k1 = Liga
uu we know lok S Dmaax By Claim 2, we know }f((m)) S
Dmax for all 17 2 O, which implics f()) S e for all ls 2 k2. That means, meta gradient descent will never overshoot the minimizer by more than when & k1. In other words, after b meta iterations, once 7) enters the e-neighborhood of 77, it will never leave this neighborhood.
We also know that at meta iteration k2, we have The I max(1/a + Dmax: M) == M.. Here, 1/a + Dmax comes from the case that the starts from the left of 1)" and overshoot to the right of 'f" by Dmax- Since 17" E [1/L, 1/a], we have [7, - 17" S max(1 (1xx1//x, 1/a + Dmax - 1/L, M
1/L)= == R. By Claim 3, we know that [F'()) Z Duain (M) for any 1) E [0, nn - -uu in" + M.
Choosing some h satisfying Die,, 1/VK 2 D we know for any k > k2 Im 17" e.
15

---

Under review as a conference paper at ICLR 2021
Plugging in all the bounds for Dmin: D Dmax from Claim 3 and Claim 2, we know there exists A1 24 poly( 1 L, 2 a T. k2 z²
M
poly( ,,, T. satisfying these conditions.
Cmin
Cani
Next, we show although the meta- is polynomailly bounded, the intermediate results can still vanish or explode if we use back- mack-propogation to compute the meta-gradient.
Corollary 1. If we choose the meta-objectiiv as F(n) = _ log (w...) when computing the meta- gradient using back-pron propagattn,,, there are intermediate results that are exponentially large/small in number of inner-steps t.
Proof of Corollary This is done by direct calculation. If use back-propagation compute the derivative of log(f (we,,)) we need to first compute af(w..) (ww,.) that equals [f(()))))
8
Same as the analysis in Theorem 3, we can show [f(W..)) is exponentially large when 1) < 2/ I, and is exponentially small when 17 > L/L.
B PROOFS OF TRAIN-BY-TRAIN V.S. TRAIN-BY-VALIDATI (GD)
In this section, we show when the number of samples is small and when the noise level a large constant, train-by-train overfits to the noise in training tasks while train-by-validation generalizes well. We separately prove the results for train-by-train and train-by-validation in Theorem 7 and Theorem 8, respectively. Then, Theorem is simply a combination of Theorem and Theorem 8.
Recall that in the train-by-train setting, each task P contains a training set Stain with samples. The inner objective is defined as f(w)= = 2/2 (z2,)) (ww, z) y)² Let (wr.,) J be the GD sequence running on (w) from initialization O (with truncation). The meta-loss on task P is defined as the inner objective of the last point, (Trr(e)) P) f(we,)) 2n EE..) ((We,) x) -y)² The empirical meta objective (T (1) is the average of the meta-loss across m different tasks. We show that under (T (1)), the optimal step size is constant and the learned weight far from ground truth w" on new tasks. We prove Theorem 7 in Section B.2.
Theorem 7. Let the meta objective FTET(G)(T) be as defined in Equation I with [d/4, 3d/4]. Assume noise level a is a large constant G1. Assume unroll length t 2 c2 number of training tasks m C3 log(mt) and dimension d. 2 c4 log(m) for certain constants 02; C32 Ca. With probability at least 0.99 in the sampling of the training tasks, we have
Train = (1) and E.
| We - w =
for all Mirain E arg min F (1)) where the expectation is taken over new tasks.
In Theorem 7, ((11 is an absolute constant independent with a. Intuitively, the reason that train-by- train performs badly in this setting is because there is a way to set the step size constant such that gradient descent converges very quickly to the empirical risk minimizer, therefore making the br-innby-train objective very small. However, when the noise is large and the number of samples is smaller than the dimension, the empirical risk minimizer (ERM) overfits to the noise and is not the best solution.
In the vrvidato-validation setting, each task P contains a training set Suain with sam- ples and a validation set with ne samples. The inner objective is defined as f(w) 2es Ex.g)esmm (ww,x) y)²² Let {wrm} be the GD sequence running on f(w) from initial- ization 0 (with truncation). For each task P. the meta-loss ATo(n) (n, P) defined as the loss of the last point Wt, evaluated on the validation set Svand- That is, AroV (7, P)
2mg (E,g)sSun ((we., - y)²² The empirical meta objective (rov(m) is the average of the meta-loss across m different tasks P2....... .m....... We show that under Frev (m) the op- timal step size is (11/t) and the learned weight is better than initialization O by a constant on new tasks. Theorem 8 is proved in Section B.3.
Theorem 8. Let the meta objective (n (1) be as defined in Equation with ni, n2 (d/4,3d/4) 3d/4). Assume noise level is large constant Ct- Assume unroll length t 2 C2 number of
16

---

Under review as a conference paper at ICLR 2021
training tasks 2 Cs and dimension d 2 log(t) for certain constants c22 C3 Ca. With probability at least 0.99 in the sampling of training tasks, we have
Toalid ((1/t) and EE ||w. w0 -1|w"111 ||===11
92(1)
for all Millid arg min (ra (1), where the expectation is taken over new tasks.
Intuitively, train-by- be-i--b--vaiidttion is optimizing the right objective. As long as the meta-training prob- lem has good generalization performance (that is, good performance on a few tasks implies good should be able choose the op-
performance on the distribution of tasks), then train-by-validattee timal learning rate. The step size of (1/tt) here serves as regularization similar to early-stopping, which allows gradient descent algorithm achieve better error on test data.
We define more quantities that are useful in the analysis. In the train by train setting, given a task Pk (D(w)), S(it) E). The training set s(4) contains n samples {x, (k) (k) y; (k)
Notations
ya with
(wx (k) c/4)
Let train be an n x d matrix with its i-th row as (T. Let H == (x Iruin
train T x (A)
train be the covariance matrix of the inputs in s(K) Let elk) be an n-dimensional column vector with its i-th
entry equal to c!a))
Since S d, with probability 1, we know x(2) unin is full row rank. Therefore, (A) has pseudo- inverse (1 such that (()) (()) = Ln It's not hard to verify that there exists W Proj ( " + (x(() (t(()) such that y,
(wrinn _.!h) for every (ar (*)) E ((k)
Here, Proj Proj ( is the projection matrix onto the column span of (X(()) We also denote Proj (ro((((()) W as (w We use ((At) to denote (1 - me ).) Let whyh be the weight
obtained by running GD on s(k) with step size 17 (with truncation).
With the above notations, it's not hard verify that for task Pk. the inner objective f(w)
(k) The meta-loss on task Ps is just ATHT( (n. Pk) = 1 | - w
w
w train
In the train-by-validation setting, each task Pa. contains training set ((h) with ny sam- ples and a validation set s(k) valid with n2 samples. Similar as above, for the training set uainn (k),
((k)
we can define Smam x(k) (k) (k) (((e) Win' for the validation set valid we can define
Svalid ((k) (k)
valid: w. valid With these notations, the inner objective f(w) = 2 | w W HOM
and the meta-loss is (rn m2) Ph) Wen w (k)
wadld 1(6))
We also use these notations without index I to refer to the quantities defined on task P. In the proofs, we ignore the subsripts on n, 0,,1,ng m2 and simply write Arer(n, Pk), Aro (n,, Pk), Frot, Frev, Frur. Frov.
B.1 OVERALL PROOF STRATEGY
In this section (and the next), we follow similar proof strategies that consists of three steps.
First, we show for both train-by-train and train-by- vaalida-valiiation, there is good step size that achieves small empirical meta-objective (however the step sizes and the empirical meta-objective they achieve are different in the two settings). This does not necessarily mean that the actual optimal step size exactly the good step size that we propose, but it gives an upperbound on the empirical meta-objective for the optimal step size.
Step 1:
17

---

Under review as a conference paper at ICLR 2021
Second, define threshold step size such that for any step size larger than it, the empirical meta-objective must be higher than what was achieved at the good step size in Step 1. This immediately implies that the optimal step size cannot exceed this threshold step size.
Step 2:
Step 3: Third, we show the meta-learning problem has good generalization performance, that is, if a learning rate 7) performs well on the training tasks, it must also perform well on the task distribution, and vice versa. Thanks to Step and Step 2, know the optimal step size cannot exceed certain threshold and then only need to prove generalization result within this range. The generalization result is not surprising also emphasize that this is non-trivial as we will not restrict the step size 1) to be small enough that the algorithms do not diverge. Instead we use a truncation alleviate the diverging problem (this allows us to run the algorithm on distribution of data whose largest possible learning rate is unknown).
only have single trainable parameter 7, however
Combing Step 2, 3, know the population meta-objective has to be small the optimal step size. Finally, we show that as long as the population meta-objective is small, the performance of the algorithms satisfy what we stated in Theorem setting, because its meta-objective is exactly the correct measure that we are looking at; for the train- by-train setting we instead look at the property of empirical risk minimizer (ERM), and show that anything close to the ERM is going to behave similarly.
The last step is easier for the rrainbb--validdte
B.2 TRAIN-BY-TRAIN (GD)
Recall Theorem 7 as follows.
Theorem 7. Let the meta objective (reT(a)(T) be as defined in Equation with E [d/4, 3d/4]. Assume noise level a is a large constant Cj. Assume unroll length t 2 cz. number of training tasks m Cy log(mt) and dimension d. 2 c4 log(m) for certain constants c2 Ca, Ca. With probability at least 0.99 in the sampling of the training tasks, we have
Traai (1) and E || w =
for all Vrain E arg m Fro (1), where the expectation is taken over new tasks.
According to the data distribution, we know Xurain an n d random matrix with each entry i..d sampled from standard Gaussian distribution. In the following lemma, we show that the covariance matrix Harii is approximately isotropic when d/4 4/4+ S n S 3d/4. Specifically, we show Ld VL < (Xmin)) LLd and &. S (H(aai) S L for all to denote the upper bound of || H.mill to emphasize that this bounds the smoothness of the inner use letter L to denote constant 100. The proof of Lemma
[n]] with L 100. We use letter
objective. Throughout this section, follows from random matrix theory. We defer its proof into Section B.2.4.
Lemma Let X E Raxd be a random matrix with each entry i.idd. sampled from standard Gaussian distribution. Let H := 1/nX" X. Assume cd with [ $1. Then, with probability at least exp(-S(dd), there exists constans 100 such that
Vd S (xx VL
Ldd and 1 SA(HH) SL
for all i i [n].
In this section, we always assume the size of each training set is within [d/4, 3d/4] so Lemma holds. Since ||miill is upper bounded by L with high probability, we know the GD sequence converges Wirain for [0, 1/L]. In Lemma 2, we prove that the empirical meta objective Frur monotonically decreases as 1) increases until 1/L. Also, we show Frer exponentially small in at step size 1/L. This serves as step 1 in Section B.1. The proof is deferred into Section B.2.1.
Lemma 2. With probability least m [0, L/L] and
Prer(1) monotonically decreasing in
1
2T
13
18

---

Under review as a conference paper at ICLR 2021
When the step size is larger than L/L, the GD sequence diverge, which incurs high loss in meta objective. Later Definition 1, we define a step size î such that the GD sequence gets truncated with descent probability for any step size that is larger than rj. In Lemma 3, we show with high probability, the empirical meta objective is high for all > rj. This serves as step 2 in the proof strategy described in Section B.I. The proof is deferred into Section B.2.2.
Lemma 3.
With probability at least exp(-9(m)),
(Trr(1) 2 107.8
for all v) > 17.
By Lemma and Lemma 3, we know the optimal step size must lie in [1/L, We can also show 1/1. < fj < 3L, so Viain is constant. To relate the empirical loss at Virai to the population loss. We prove a generalization result for step sizes within [1/L, L/).. i7]. This serves as step Section B.I. The proof is deferred into Section B.2.3.
Lemma 4. Suppose a is large constant Assume 2 c2 d 2 c₁ for certain constants c22 With probability least 1 m (mex(=-((())) O m)
o²
(Frer(n) Frer(n)) S
for all 1) E [1)
Combining the above lemmas, know the population meta objective Frer is small at Thain which means We,nga is close to the ERM solution. Since the ERM solution overfits to the noise in training tasks, we know | w=| has to be large. We present the proof of Theorem 7 as follows.
Proof of Theorem We assume a is a large constant in this proof. According to Lemma 2, we know with probability at least m ex)(-S((d)) (1) is monotonically decreasing in [0. 1/L] and Frur (1/L) < 2 1/ This implies that the optimal step size Thrain 2 1/L L and By Lemma 3, we know with probability at least 1-exp( (exp(((((m)))
-
Frer (Trrsin) < <2L2o
c2 for certain constant C22 know T0L= > 21 1/L3) which then implies that the optimal step size Tinin lies in f. According to Lemma 6, we know ýj E (1/L, 3L). Therefore Virann is a constant.
Fror (n) 2 10Ls for all 17 > îj. where rj is defined in Definition As long
o²
o²
According to Lemma 4, know with probability at least 1 m))xp((((m))) [FreT(v) (T))(1)) S d² for all 1j [1/L, 77 As long as is larger than some constant, have FroT(Tuam)) S f.. Combing with the generalization result, have FTOT (Tiran) be large.
exp(-S((c))
O(t +
20² IT. Next, we show that under small population loss, IE || || -wIl has to
Let E, be the event that vd/vI S (Xtain) I LLd and 1/L & (H(aii) S for all e [n] and /da/44 / < [[Euaull S Vda. We have
E E| We.n
Whaiin ||
E
Wimnin
Wrriin _/2 1 {{1}
Husic
L
EE) / - - (Nueain) ) "Erain 1 {{11))²
L
(E [B| [[(uaan)) Grain|| 1 (E,} E We Wirain {Ei)))
I
Since Wr
Whaiin Musi
20 1,3
this then implics
40 2x 1,3
E (X ) Erain
(E E Wennin wrain (E)
T.
According to Lemma and Lemma 45, we know Pr(&]] > exp( ((d)). As long d is at least certain constant, have
Conditioning on ε,, we can lower bound |[(Xmam)) ) Grain|| by 4vT."
a
19

---

Under review as a conference paper at ICLR 2021
Pr[E]] 2 0.9. This then implies E (XXuain)) [train]
||
{&1} 2
90 40vl
Therefore, have
Wt - E
Wirain 1 {1 >
90
2a
9a
20
0
40vL
L
4L
L
4L'
where the first equality uses L = 100. Then, we have
o²
E Wi.nii w0
Wirain
1 118)) 2
E
Wi
Wirain
1{81)) 2 16
where the first inequality holds because for any Strain Wiiin is the projection of w" the subspace of Smain and Whtmiig is also in this subspace. Taking union bound for all the bad events, we know this result holds with probability at least 0.99 as long as large constant O₁ and 2 C2 m C3 log(mt) and d 2 c4 log(m) for certain constants c22 C3, C4.
B.2.1 BEIAAVIOR OF Frer FOR v E [0, 1/]
In this section, we prove the empirical meta objective Foor monotonically decreasing in [0, 1/ L). Furthermore, we show Frur(1 (1/L) is exponentially small in t.
Lemma 2. With probability least mmxxp(-S(()) Frer(1) is monotonically decreasing in [0, L/L] and
1 PrtT(1/L)22L' S2''0 (1 (1 T2 1
1
Proof Lemma For each & E [m]] & be the event that va/vI. S (x((unin)) S VLd and 1/L I (Huum) & for all i [n] and vda < |[ I do.. Here, L is constant 100 from Lemma 1. According Lemma and Lemma 45, know for each is [m]. &g happens with probability at least ex))- Taking union bound over all k E [m]], we know CkEmm] holds with probability at least - m exp(-S((d). From now on, we assume E holds.
Let's first consider each individual loss function ATOT (1, Pk). Let (wo()) be the GD sequence without truncation. We have
i (k) F.
(M) 20 train
②. -1,1 w train train (20 w train
(K)
TH (8))
= (1
1H train
(k))
(107-1.0 (10
(k)
w train
(1c)
= -(1 (I- 17.1 (k)
train
ywu (k) "train
For any 17 E [0, L/L,, we have (10
-
(k) train
=
(A)) )* + (x
triin
Strain
I 2v for any
(k) Therefore, w never exceeds the norm threshold and never gets truncated.
Noticing that ATOT (1,, Pt)
w
(K) TH(A)) (wo(k) w ( (ain)
) we have
(k) (H) (1 (1 "
ATOT (11, Pk) 2 (wiinn)
W mann
Taking the derivative of ATEr (1. Ps.) in 17, we have
( 2 (()) 0 A ( Pk) -t(([(h)) T ((H )2 - mn (ran) train
On
Conditioning on εx, know 1/T. < ((( (rain) T. for all i [n] and H is full rank in the
row span of (k) vain Therefore, we know &.
on Arrrr (n, Pk) < 0 for all E [0,1/L). Here, we assume
(k) train
0, which happens with probability 1.
Overall, know that conditioning on Ake(m] Ex, every Arbr(n, (n. Pk) is strictly decreasing for n [o, L). Since Frer(n) = + Em Arrr (1) Px), we know Frwr(1) is strictly decreasing when
" (0, 1/L]-
20

---

Under review as a conference paper at ICLR 2021
At step size 17 L,L, we have
ATer (11, Pk)
= (W
T "H (8) (T 17
17 22 W
train
1/2
1
>)llla | ||
22220 1 12
(1-12)²
S 2
L
1
L?
where we upper bound
w uain
by 4Lo² at the last step. Therefore, we have (1/L)
21--0 - )
B.2.2 LOWER BOUNDING FrST FOR E (7, 00)
In this section, we prove that the empirical meta objective lower bounded by Mo)² with high probability for E (7, oc). Step size ij is defined such that there is a descent probability of diverging for any step size larger than vj. Then, we show the contribution from these truncated sequence will be enough to provide an (o lower bound for Fror. The proof of Lemma 3 is given the end of this section.
Lemma 3. With probability at least - exp(-2((m),,
o²
Frer(n) 2 1008
for all 1) > i7.
We define îj as the smallest step size such that the contribution from the truncated sequence in the population meta objective exceeds certain threshold. The precise definition is as follows.
Definition 1. Given training task P, & be the event that vdlVI. S (x(X I VLd and 1/L S (Hmmm) S for all E [n] and vio /4 S [[ S Vda. Let Ez(1) be the event that the GD sequence is truncated with step size n,. Define n as follows.
7= inf n
0
B
Wiaii 1 H |wr.
2
T,6
In the next lemma, we prove that for any fixed training set, 1 1 n { (&(()) for any of 2 1). This immediately implies that Pr(& n Ex(1) and E || Wrrain 2 Ham 1 ( is non-decreasing in
Basically we need to show, conditioning on E,, if a GD sequence gets truncated at step size 1) it must be also truncated for larger step sizes. Let (w",,) be the GD sequence without truncation. We only need to show that for any T, if [w',,ll exceeds the norm threshold, ||="",, must also exceed the norm threshold for any r/' 2 n7 This is easy prove if is odd because in this case || |[w" is always non-decreasing in n. The case when 7 even is trickier because there indeed exists certain range of such that [ is decreasing in 7,. We manage to prove that this problematic case cannot happen when [w'sg]
is at least LvTo. The full proof of Lemma 5 is deferred into Section B.2.4.
Lemma 5. Fixing task P, let &n and Ez(1) be as defined in Definition 1. We have
(E, (&((1) 2 1 n {
for any 2 Tz.
In the next Lemma, prove that must lie within (1),,3L). We prove this by showing that the GD sequence never gets truncated for 7) E [0, 2/ L] and almost always gets truncated for E [2.54, oc). The proof is deferred into Section B.2.4.
Lemma 6.
Let r be as defined in Definition I. Suppose a is a large constant C1 Assume t 2 C22 d
C4 for some constants U2 C4. We have
1/L. < 3L.
21

---

Under review as a conference paper at ICLR 2021
Now, we ready give the proof of Lemma 3.
Proof of Lemma 3. Let & and (n) be as defined in Definition For the simplicity of the proof,
we assume E ||,r, Wrain Hmme & {&i n E2()) 2 Zz. We will discuss the proof for the other case at the end, which is very similar.
l
Conditioning on Eτ, we know |lwe, Whain 11 Ham S 181.o2. Therefore, we know Pr(E: n (n) 2 I
1873 For each task Px. define E(tt and ((R) (17) as the corresponding events on train- train By Hoeffding's incquality, we know with probability at least - exp(-S((m)),
ing set s(h)
1 ΣE
E n (m) 2 2018
By Lemma 5, we know 1 { E ne
E (m) 2 1 { {()) n th/ (i) for any n 2 17. Then, we can
lower bound Frer for any 7) > f as follows,
Fror(1)
1 m
w
(K)
train
(2)
m
(R)
w
irain
(b)
1 ( n nE ((4) ) (m)
2
(T)
m
k=1
20
1 (k)
n
{
5(k)
k=1
o²
200
1 el
n
g/ (1)
2
107.3
k=1
where the second inequality lower bounds the loss for one task by 2a² when the sequence gets truncated.
We have assumed E3 ||w,, - Wirain 1 Hime I ()) 2 Te in the proof. Now, we show the proof also works when E ||u,, - Werain 1|
Himi 1 E ( < fer with slight changes. Accord- > /7t for all n 1j. At each training set Swain; can define {E, n (77)) as lim,- 1 {&, n E We also have Pr[E, n (f)) 2 1873. The remaining proof is the same as before we substitute
ing to the definition and Lemma 5, we know 153 ||w,, - Wrain 2
Hmm 1 n
& by (
B.2.3 GENERALIZATION FOR 1) E [1/L,
In this section, show empirical meta objective Frer is point-wise close population meta objective FroT for all 77 E [1/
Lemma 4. Suppose is large constant C1- Assume c2, d 2 ca for certain constants C22 Ca- With probubility at least 1 - m www.meexpp--itt ((d)) O(1 m)exp(-(((m).
o²
(F)r(()) Pror(n)) S 13
for all n E [1/L, 7.
In this section, we first show Peιr concentrates on FTET for any fixed v and then construct e-net for Frot and Fror for 17 E [1/L, We give the proof of Lemma 4 at the end.
We first show that for fixed n, Frer(1) (1) is close to Frer(n) with high probability. We prove the meta-loss on each task ArTT (11, Pa) is sul=pouubxpponnttaal.. Then we apply Bernstein's 's inequality to get the result. The proof is deferred into Section B.2.4. We will assume a is large constant and I 2 C22 d 2 c for some constants C2 C4 so that Lemma holds and vj is constant.
Lemma 7. Suppose is constant. For any fixed n and any 1 1 - exp(- (f)((e
0, with probability at least
((eo(1) - (T) Se.
22

---

Under review as a conference paper at ICLR 2021
Next, we construct c-net for Frur. By the definition of i), we know for any S nj. the contribution from truncated sequences in Frur(1) (7) is small. We can show the contribution from the un- un-truncated sequences is O(t)-lipsc
Lemma 8. Suppose a is a large constant e1. Assume t 2 C22 d 2 for some constant 022 Ca. There exists an 11." L -nef N C [1/L, îi for FIET with |N] O()) That means, for any 1 [1/L, f]
11o 1
FFrr(n) - Frer(1))
for r/ = arg
Proof of Lemma 8. Let & and (7) be as defined in Definition For the simplicity of the proof, Zz. We will discuss the proof for the other
we assume E ||ur, Winin I| Honi 1 { n E2(r) s o²
case at the end, which is very similar.
We can divide E ||w.. Wasial
ll Huni as follows,
IE
Wt,n
Wtaain 12 Ham
=E
| Wuain
2 Ham
1 1 1E1 B | Wrsiill Mmm (
+
E ||w..
Whain 1 1 {EI}.
We will construct c-net for the first term and show the other two terms are small. Let's first con- sider the third term. Since ||we, Wisai ||
Huni subeepnttiaoaaa and Pr[E,] S exp(-S2dd))
have 1 ||w,, Wtrain 2
{ (() exp(-S(d)). Choosing d be least certain con-
Hmm
stant, we know || Wrain 11 He... { o² /L/
Then upper bound the second term. Since E ||w., Wrain 12 Hine
1 ( S L and
|| Warain P 2 2o when w diverges, we know Pr[E n En)r S 27 Then, we can upper bound the second term as follows,
1 E 2 |ww.
1
90²
Wuain 122 Huan { n & S 18
2T,6
T
Next, we show the first term 1/2 | Wieain 1| Hem. 1 {E, n &g (7)) has desirable Lipschitz condition.
According Lemma 5, know 1 {Ei n En)) 2 1 (&, n (2)) for any 17 S fj. Therefore, conditioning on E, n E2("), we know Wt.r never gets truncated for any S 17. This means Wt.g = m)lmmin))) We can compute the derivative of 1 ||we. Wirain Hem
Wanin with Bt. = as follows,
0 1
Wen - Wirain 112
Huuin (tHuain -17 H) "-1 Wirains Hurin (Wi. wuran)))
On 2 ||we,w|| we have [I(I HHHuii W'raill
4vLo and || I 2vLo, < 6vLo. We can bound | nH - with [[ -KL-nHurain r "uriinl + | || by bounding the expanding directions using [|(2 Hlraiin)) "Wrrin and bounding the shrinking directions using ||Wtrain|l Therefore, we can bound the derivative as follows,
Since
[I(T (I n HH W ||
θ 1
On | Wirain 112 11 SILX X 48L302t.
Suppose is constant, we know E. I|We, Wizsial 1/3
1 (8 n ( is Oit)-iipschizz. There- 1 1 with size O(t). That
Humi 2
fore, there exists E -nen N for E. ||u0s.n Werain Huis means, for any 77 E (.)
1 Huma 1 (E (&(()) < x²
2 | - Whain Hm 1 3 &
1 ||Wt. Werain
23

---

11o² Under review as a conference paper at ICLR 2021
for ry' arg ".,iin""",nn""iiii n)"). Note construct the c-net in particular way such that r/' is chosen as the largest step size in N that is at most
Combing with the upper bounds on the second term and the third term, we have for any 17 [1]
[Fur(n) Fror(1))1 $ L
for r/' = arg w
In the above analysis, we have assumed E ||we, Wrsin P 1 ( v a² The
Husis proof can be easily generalized to the other case. We can define [ n (7) -im 1{ (g))) Then the proof works long as we substitute 1 { 0 (
as
by
{ ( We will also add i into the e-net.
In order to prove Frur is close to FOwT point-wise in [1/4, we still need to construct an e-net for the empirical meta objective Frar-
Lemma 9. Suppose a is large constant C1. Assume 2 C2 d 2 c4 for certain constants c22 With probability at least 1 m exp( eexp(-S(dd)), there exists o² net N' [1/L, for Fror with |N| = Ot + m). That means, for any E [1/L,
o² 1
(1) Prer(1))
for n/ arg " n7").
Proof Lemma 9, For each [m]) & the event that vd/VT. S (X(())
mmi)) S VLd and
S Vila According to Lemma 1 and 1/L. S (x ) L. for all E [n] and vda /4 c(*)
Sirain
Lemma 45, know with probability at least m exp( ((d)),, & hold for all l: [m]. From now on, we assume all these events hold.
Recall that the empirical meta objective follows,
1 m Σ Aror (n, Pk).
Froz (n)
For any E [m]] let M7. be the smallest step size such that w(th) gets truncated. If ne.k > ft, by similar argument in Lemma 8, we know ArbT (1, Pk) is Ott)-Lipschitz in [1/L, f) as long as a is constant. If Ne.k I f). by Lemma 5 we know wi, gets truncated for any 2 Te This then implies that (To Ps.) is a constant function for E [T,ckk, f). We can also show that Aror (n, Pk) O(t)-Lipschitz [1/L, Tlc,k). There might be discontinuity in function value at Je,k. so we need to add 7c.k into the c-net.
O(t + m) for Frer. That means, for any Overall, we know there exists an 7 -net N with |N'| E [1/L,
Prer(n) Prer(n') s o² L
for r/ = arg EN" ).
Finally, we combine Lemma 7, Lemma 8 and Lemma 9 to prove that Fror is point-wise close to Frur for E [1/L, 7
Proof of Lemma 4. We assume constant in this proof. By Lemma 7, we know with probability at least exp( (e)mm) (rrr(())
Frer(1) (n) < for any fixed By Lemma 8, we know there exists an _و.² N for Fror with size (tt) By Lemma 9, we know with probability least m (xp(-pp()))) there exists -ee N' for Frer with size (l++m). According the proofs
24

---

Under review as a conference paper at ICLR 2021
of Lemma 8 and Lemma 9, it's not hard to verify that N is still an 11o" That means, for any E [1/L; fi,, we have
-ne- -net for Frer and Frer-
11
Frbr(1) Frur(t')). Frur Frer 5
1
for r/ = arg EN )- Taking union bound over N U N', we have with probability at least 1 - O(t + m) exp((((()
r²
Frur(n) - (r))(1) (n)
L
for all 17 N NU..
Overall, we know with probability at least 1 - m (mxp(-(((())) - Ott + m) exp(-S(m)), for all 7 E [1/
(F)r(()) Prur(1)) (n))
< (TT() Frer(r)) (F))(()) Frwr(1/) (Frrr(1)) - Frer(1) (1/)1
230²²
0²
L
L3
where r/' = arg MN n/). We use the fact that I, = 100 in the last inequality. 0
B.2.4 PROOFS OF TECHNICAL LEMMAS
Proof of Lemma Recall that Xusin is an n d matix with n = where c E [1/4,3/4] 3//oo///).ccoordin
to Lemma 48, with probability at least 2exp(-19 (12/2/2)), have
Vd Ved 1 S (Ximin)) S Vd Ved 4
for all i [n].
Since Huran 1/nxX main X irain we know \₁ H urain)
= (X Since c E [2 21, we have 1 + c', for some constant e'. Therefore,
100 da (VV Vcd)² < 100 e' and d (vd- 2
know with probability at least exp( ((d)),
1
- A; S 100,
100
for all i E [n]]
Similarly, since there exists constant c" such that Vd + Ved < (10 v' and vd - ved > (1/10+""))o we know with probability least 1 - exp(-=((())
Vd s (X 10vd,
10
for all E [n]. Choosing L = 100 finishes the proof.
Proof of Lemma We prove that for any training set Suain f n Eg(')) 2 f n (2((1)) for any v' 1). This is trivially true if is false on Smin- Therefore, focus the when &, holds for Suain Suppose Ne is the smallest step size such that the GD sequence gets truncated. Let (w be the GD sequence without truncation. There must exists
such that ||w' 2 4 Lo. We only need to prove that || 2 4vLo for any 1) 2 Ne- We prove this by showing the derivative of ||=""||l
1| in is non-negative assuming ||'"" 1| 2 4VLo.
(I 1)Hrriin Whaiin If 7 is an odd number, it's clear that by ||'2'||? is nen-negative at any 17 2 From now on, we assume is an even number. Actually in this case, Dyj || can be negative for some 1). However, we can prove the derivative must be non-negative assuming ||'"",nl > 4vT..
Recall the recursion of wh.n as w'.n Wirain
a
25

---

Under review as a conference paper at ICLR 2021
Suppose the eigenvalue decomposition of Humin is Σi= Nmnn with \1 2 ... An- Denote e₁ as (Wirain Uz) Let Ay be the smallest eigenvalue such that (1 - n)1) _ -1. This implies X S 2/1 for
any 2 j+ 1. We can write down | as follows
|/00 112
Σ i=1
(1 (1 (1-)1-
Σ - (1- 1=++1
Σ (1-(1-mA)))) (1-11111)) 2 + ||
Since El holds, we know || 2 < 4Lo². Combining with ||w/,|1 > 16Lo², we have
Σ (1 - (1 - )) o 2 12Lo². We can lower bound the derivative as follows,
|WTTMll 2 =
21 - (1 +
211,(1 - mn,) (1 (1- (1--1-11))) -
1=1
i=j+1
21
Xe(1 -
21 2
Σ
11 1=/+1
i=1
22t
Σ
M(1
())-)))) (1 (1 my a -2
21 x 8L02 nn-
Then, we only need show that Σ do(1 n/1 We have
(1 (1 n)x))) c is larger than 8Lo2 /n-
(1 - -1-
Σ (1)1-)))* (1 (1 (1- m)a)') 22 Σ
A 1 (1 - n/133² (1- (1-(1-11) (1=)11))))'² &f
(nd) - 1)(-1
(nA: - 1)2 - (1 - (1 - - o
d (nd) - -1)* 1771
(n); -1)²
1
(1- (1 - -m>,)))² of
(1 - --))))
& 12L00 / > 8LO²/1
Proof of Lemma 6. Similar as the analysis in Lemma 2, conditioning on ε₁, we know the GD sequence never exceeds the norm threshold for any 17 E [0, 2/). This then implies
E 2
[ Werain 1 1 f n { = 0,
Husi
for all 17 E L0.
Let (wh,n) be the GD sequence without truncation. For any step size 1) [2.5L, ool, conditioning on E,, we have
W 2 ((n/L- - - -1) Wrrain 2 (1.5' (1.5'-1)
a (1/7-11) 4VLo,
where the last inequality holds as long as o 2 5vI,t> 02 for some constant C2. Therefore, we
know when 17 E [2.5L, o0), 1 n = (& Then, we have for any 1) 2 2.5L,
1
2T (A/Lo -VLo-22 Pr[Ei] > 20 Pr[Ei] > x²
1
E 2
||
Wirai Hm... 1 (
2T.
T
26

---

Under review as a conference paper at ICLR 2021
where the last inequality uses Pr[Ei] 2 exp(-S((d) and assume d 2 c2 for some constant Ci- Overall, know E ||wa,n Wirain Huui n& equals for all r) E [0, and is at least f for all 1) E (2.5L,,00, By definition, we know (1/L,3L).
Proof of Lemma Recall that (T))(1) (ner(n, Pk) is subexpooono We can further write Arer Pk) follows,
m. J Ei= ArAT (1), Pt). We prove that each
=
ATT Ph)
2
1
W w
)
train)
tte(k)
Serain
(k)
1
w wh
(k)
|
(k) Stain
(K) win
wi|
(1/1
Stain 1)
(k)
X x 1)
2
2n
We can write Fr o maxx (o X
According Lemma 47, we know mmxx (R)
train
max (Xmmi)) is (())-ubgauusiin, which implies that mmax (/2 X (hin)) ma X train is
(8)
O(1/Vd) subgauussnnn Since Exmax(
constant, we know max v x uain
x tran)
O(1)
vn
subgaussian and Tiaax( (k)) train is -uuxxuubbioon Similarly, we know both 1
Saann 2
and
2n
x
Irain I)
(1/
(k) Strain
are O(1xxuubexponentia.
Suppose is constant, we know w wo is upper bounded by constant. Then, we
know (n Pk) 011)ssuhexponentia.. Therefore, Fre)(1) the average of m i.i.d. 0(1)- subexponential random variables. By standard concentration inequality, we know for any 1 > > 0, with probability at least exp(-S(e2m)),
Prer(1) (r) Sc.
B.3 BEAIN-BY-VALIDATUU (GD)
In this section, we show that the optimal step size under Frev O(1/t). Furthermore, we show un- der this optimal step size, GD sequence makes constant progress towards the ground truth. Precisely, we prove the following theorem.
Theorem 8. Let the meta objective (To((1))) be as defined in Equation 2 with T1, n2 E [d/4, 3d/4). Assume noise level a is a large constant er Assume unroll length I. 2 C2 number of training tasks m 2 0s and dimension d 2 Ci log(t) (t) for certain constants c22 C32 Cq. With probability at least 0.99 in the sampling of training tasks, we have
Myalid = (11(l) and TE [[wttnt -
2(1)
for all Walld arg min Frov((i.m)) (n)) where the expectation is taken over new tasks.
In this section, we still use L to denote constant 100. We start from analyzing the behavior of the population meta-objective Frav for step sizes within [0, 1/L]. We show the optimal step size within this range is (1//t) and GD sequence moves towards w" under the optimal step size. This serves as step in Section B.1 We defer the proof of Lemma 10 into Section B.3.1.
Lemma 10. Suppose noise level a large enough constant C1 Assume unroll length t 2 C2 and dimension d 2 C for some constants C22 C4. There exist m,, 72. = (11/t) with < 72 < ms such that
1 (11)) < 2
| C+ d²
2
a²
Frov(1) 2
||02
C+
An E [0.m]u
u Ins. 1/L.
10
2
where C. is a positive constant.
27

---

Under review as a conference paper at ICLR 2021
To relate the behavior of Frov the behavior of Frov, prove the following generalization result for step sizes in [0, 1/ This serves as step 3 in Section B.I. The proof is deferred into Section B.3.2.
Lemma 11. For any 1 > 0, assume d 2 ca log(1/e) for some constant c4. With probability at least 1 - ((1/e) exp((x((emm))
(Fov(n) (rov(n)) se
for all n E [0.1
In Lemma 12, we show the empirical meta objective Frov is high for all step size larger than 1/L, which then implies Walld E 1/L.. This serves as step 2 in Section B.1. We prove this lemma in Section B.3.3.
Lemma 12. Suppose is large constant. Assume 12 c2, e2, c4 log(t) for some constants C22 C4. With probubility at least 1 - -ep(
1
Frov(n) 20'0
2 2
for all n 2 1/L, where C' is positive constant independent with
Combining Lemma 10, Lemma and Lemma 12, we give the proof Theorem 8.
Proof of Theorem 8. According to Lemma 10, we know as long d and are larger than certain constants, there exists TJ, 1/2 Th (1/()) with y < 7/2 < f/3 such that
(12) S |w='|
C C²20222
10
(nw 2 ||=*||
6
C + 0² vn [0. (n3, 1/L],
6
10
for some positive constant C.
Choosing min(1, C/10) in Lemma 11, we know as long as d is larger than certain constant, with probability at least (xp(-N(mm),
Frw((n) Fro((1) C/10.
for all 17 E 1/L).
Therefore,
Frov S ||w0112
C + 02/2
10
Fro 2 ||1 ||00
C 0² 22 m0. |n 1/L).
10
By Lemma 12, we know as long as t 2 o2 d 2 log(t) for some constants C22 Ca, with probability least 1 - exp(ppppp exp(-S(mm))
(rw(() 2 C' + 2 700
for all 1) 2 1/L. As long as 1/VC", have Prov(n) 1 102 for all 17 2 1/L. Combining with Fryy (mz) < 1 ||w' 10 CC+0/22, we know Viatia E [0, 1/). Furthermore, since Frov(n) (n) 2
||00 ||=0=12 2 + 02 Vn m0 [1a, 1/L,, have 7)1 S Welldd 1/3.
Recall that 17, 1/3 = (11(),, we know Villi = @(1/t) At the optimal step size, we have
1 |l'1|
7 C' o
Frev (Nistaa S Frov ( (Mrrlia) + C/11 Frov (12) + C//10 < 2
10
Since Froy (Mand)) E We.nn. - w11 + 02/2. we have
E
Weennim w "1 < | 11 C.
Choosing m be least certain constant, this holds with probability at least 0.99.
28

---

Under review as a conference paper at ICLR 2021
B.3.1 BEHAVIOR OF FrEv FOR [0.1/L]
In this section, we study the behavior of Frov when 77 E [0, 1/L). We prove the following Lemma.
Lemma 10. Suppose noise level is a large enough constant e₁- Assume unroll length t 2 c2 and dimension Z ca for some constants c2 Ca. There exist n, T2, V (1/tt) with yn < 72 < m3 such that
1 2
9
o²
(12) -
|
1|
C
10
2
6
a²
(n) ||"11
C+
Vn E m0 Ins, 1/L]
2
where C' is a positive constant.
It's not hard to verify that Frav (n) = 2 |,r,, w" 1|2 -o /2. For convenience, denote Q(1)
1/2 ||wr,, w² In order prove Lemma 10, only need to show that EQ S 2 ||
for all 7 E [0, ml LJ [7s, 1/L.. In Lemma 13, we first show that this happens with high probability over the sampling of tasks.
9 C and (Q)) 2 3/ ||2 1|2 fo
TO
Lemma 13. Suppose noise level a is large enough constant 01. Assume unroll length t 2 C2 for certain constant cg. Then, with probability least 1- exp( exp(-I((d) over the sampling of tasks, there exists m, f22 113 (1/tt) with 722 < 1)3 such that
1
Q(1))= = 2 | -w" w=1 5
I
-C
2
1
C
Q = 2 |
w=1
w0
2
ww"
11
Vn E [0, U [ms. 1/4]
2
where C a positive constant.
Since are in the small step size regime, we know the GD sequence converges with high proba- bility and will not be truncated. For now, let's assume Wt,n = Br, Wrain + Be,, (Xuuin)) Etains where By 1 Mm We have
1 || Winn + BB,,((Xiaani '
Q(1
"iirain w0|
2
1
|Le w=' w=11 113 Be. (Xurin)* &
2
+ (Bi,, Winiin - w", Be,((Xuaai ) "araii)
1
||=l + BBrnnaann 112 + BB Errainl| of w²)
2
+ (Bi w", Be,n(Nurii)) ( "urin)
In Lemma 14. we show that with high probability the crossing term (Br, w², Be,y( (Xurin)) " (rrin) is negligible for all 7) E 1/,) By Hoeffding's in- equality, we know the crossing term is small for any fixed Constructing an e-net for the crossing term in 77, we can take union bound and show it's small for all 7 E jo, 1/L). We defer the proof of Lemma 14 to Section B.3.4.
Lemma 14. Assume a is a constant. For any > O, we know with probability at least
c
1 0(1/((1))) exp(-S((e2d)
K (raieerraie w., BL,n Br.,((Xonnn (Xomi)) { S
for all n E 10.)
Denote
G(n) := 2 | 112 + 2 W winnn +
Be, (X & Br,, w*).
Choosing C/4 in Lemma 14, we only need to show G(rz) I || 5C/4 and G(n) 2
|| C/4 for all n e [0, (ns, 1/L..
29

---

Under review as a conference paper at ICLR 2021
We first show that there exists 7)2 (1/t)) such that G(12) - 2 1=2 5C/4 for constant
C. It's not hard to show that 2 |B 12 + B ( "sraiall = O In Lemma 15, we show that the improvement (Br. W urain w²) = [2()() is linear in v). Therefore there exists 7/2 = (1/(t) such that G(m2) S / w/ 1| 5C/4 for some constant C. We defer the proof of Lemma 15 to Section B.3.4.
Lemma 15. For any fixed 1j E [0, L/tt) with probability at least - exp(-
1yt
(B wnine w
16L
To lower bound G(1) for small 17, we notice
G(n) 2 2 1|0011 - (Br,o) Wirain: w²)
We can show that 1 imin:: w*)
O(nl). Therefore, there exists m (B w²) - C/4 4 for all 77 E [0, m1l.
Wmii:
@1/()) such that
To lower bound ((n) for large 77, we lower bound G(n)) using the noise square term,
G(n) N Be,, (-Xaain) E
We show that with high probability [| (X Euail| 1|2 = 2(0²) for all n E [log(2)L/t,1// 1/L]. Therefore, as long as a is larger than some constant, there exists T/ = (1/t)) such that G( 2 ||=" 11 for all 1) E [1,, 1/L].
Combing Lemma 14 and Lemma 15, we give a complete proof for Lemma 13.
Proof of Lemma 13. Recall that
Q(n) |B Wrain w01l + BB., (Xmain) Etrai ||
1
2
(B,, w", Bt,, (Xrrin) * ((rrm))
-G(n) + (Br, W - w, Br,, (X Emmii)
We first show that with probability at least 1 exp(-S(d)), there exist vn, 1/2 1/3 O(1/l) with
m Mp < 7s such that G(1z) s 1/2 |011 5C/4 and G(r)) 2 1/2 //2||=111 C/4 for all
E (0. U [7s, 1/L].
According to Lemma 1, we know with probability at least 1 - (xxxeexx((()) vdlvT. 0, (Xusin) S
LLd and 1/L S (Hamm) L for all i [n] with L 100.
Upper bounding G(1z): We can expand G(r)) as follows:
G(n)
2 " 11 + 2 ( "urain ||
|| 11 + 1 || W 11 + 2 (P " (Be, Wrain w
1
Recall that Br. 1 - (I (mii)) ), for any vector in the span of Hirain;
B = (1 (1 m)Maan))))) w|l S Lift ||w||-
According to Lemma 45, we know with probability at least 1 - exp(-S(d)), [I5mill| S Vdo. Therefore, we have
1 B W Train 2 +
1 2
(X,uan)))))) Surain))) 2 12 13 2 2302
2
where the second inequality uses I. 2 1. According to Lemma 15, for any fixed E [0, L.41, with probability at least 1 - exp( (dd)). (Bt. Wiain w*) 2 nit 16r.
Therefore,
G(r) < |/01122 + 220000 nt
<
||w0|
7tC
16T.
2
32T.
30

---

Under review as a conference paper at ICLR 2021
where the second inequality holds long 17 321.4 Choosing 7/2 32 have
1 G(12)= - ||="
1
I 1|
5C
1024L
2
4
where C' = 81 Note C' is constant o, L are constants.
Lower bounding G(n) for n E [0, mil Now, we prove that there exists 7/1 = (11/t) with
m 112 such that for any vy [0, ml) G(n) 2 z 1|0" 112 G. Recall that
G(1)
1 2 ||l" 11a
BL, Winnin 11 + Be,, (Xirai))) ) (Br,, Wirain: w )
1|w0112
-Brr,n Wiraim w*)
Since (, w*}l S Litt, we know for any 1) E [0. m.,
G(m) 2 2
|| - Lmit.
Choosing 171 ALE
we have for any 1) [0,
C
G(n)
2 2
|| 10 x
4
Lower bounding G(n) for E [ns. 1/L]: Now, we prove that there exists f/3 (l/t)) with 77s > 1/2 such that for all 17 E [ns, 1/L].
G(n) 2 2 1100 1100122 2 C
4
Recall that
G(n) = 2 1 - w w²1 - 2
1
1
Br., (X ( ||
2 2
According Lemma 45, we know with probability at least exp(-I(d)), Therefore,
dd 2/2
s
||
Bt,, (Xinin) Strain 1|² 2 (1 e (1-e-1//)
2 a²
2
8L 32L
where the last inequality assumes 7) 2 l/t, As long as > log L2, we have log(2) s L/L. Choosing 7/- = L/t, we know for all 17 E [1s, 1/L],
σ²
G(n) 2 Br, (X x Srrin
64L
Note that 1 || 1/2. Therefore, as long as 2 SVL, we have
G(n) 2 ||=01
for all 17 E [na, 1/L].
Overall, we have shown that there exist 7/, 122, 77s (1/tt) with 7n < 1/2 < 7ss such that G(ra) <
1/2 |1 3C/4 and G(n) > 1/2 || - C/4 for all 17 E [0. ml U [ma. 1/L]. Recall that Q(n) = - + (Br,, "iain - "", Br,n( (Xmann (Xiunnn (miii) Choosing e = C/4 in Lemma 14, we know with probability at least exp( exp(-2(d))
BB,,, "i w², (X.min) (main)) ) < C/4 for all
7 [0, 1/L] Therefore, know ((12) _ 1/2 | C and Q(7) 2 1/2 || C/2 for all
E [0,m] U [ys, 1/L).
Next, we give the proof of Lemma 10.
31

---

Under review as a conference paper at ICLR 2021
Proof of Lemma 10. Recall that Frev (n) E1/2 |ew.. w01 + o² For convenience, denote
Q = 1/2 ||wt,, - w= 1| order to prove Lemma 10, we only need to show that EQ(1) -
||=="1" C C and EQ(1) 2 2 || 1o C. for all r E [0, ml U [77. 1/L]-
According to Lemma 13, as long as a is large enough constant 6₁ and least certain constant C2, with probability at least 1 - cxp(-52(d) over the sampling of Suain; there exists 7/1, 1)2 7/8
(1/() with M < 1/2 < 1/3 such that
((12) == 1/2 |/ - w=1
- 2
|| w00 1| C Iw=1
C 2
Q(n) == 1/2 |,0,, - w=
An E [0. [ns, 1/L]
where is positive constant. Call this event E. Suppose the probability that & happens is 1 - 6. We can write EQ( as follows.
EQ(n) = E(Q))
According the algorithm, we know ||w,, is always bounded by 4VLo. Therefore, Q(1) 1/2 ||we,, - == v 13Lo². When v) = 72, we have
- c) 01-
EQ(m2) <
1|0011
8
||=0|1 112
C (C )8
2
9C
1 |1²
10
where the last inequality assumes 8 x When y [0, U [ys, 1/4,, we have
C
100 130L
C
BQ(m) 2
1
11
(1 - 8) - 13L028
2
2
(1 6) C
||l0||
11
13Lo28
2
C
||
(1/2 + 13
2
1 ||00||2
6C
2
10"
where the last inequality holds as long as 5 - 5C+180Lo
According to Lemma 13, we know 8 < exp(- Therefore, the conditions for can be satisfied as long as d larger than certain constant.
B.3.2 GENERALIZATION FOR 77 E [0,1/L]
In this section, we show Prov is point-wise close to Frw for all E [0, 1/T.) Recall Lemma 11 as follows.
Lemma 11. For any 1 > > 0, assume d 2 log(1 /c) for some constant ca. With probability at least 1 - 1 exp(=(((eem))
Frov(1) Fro Sc.
for all n E 10,1/
In order to prove Lemma 11, let's first show that for fixed 77 with high probability Frev (n) is close to Frw (n). Similar as in Lemma 7, we show each ATOV (17. P&) is O(1))subeeponential We defer its proof to Section B.3.4.
32

---

Under review as a conference paper at ICLR 2021
Lemma 16. Suppose is constant. For any fixed nj [0, 1/]] and any >>> c 0, with probability at least eex((-((eem)
(Twv(1) - Prov(1) s..
Next, show that there exists an c-net for Frev with size (1//c). By c-net, a finite set Ne of step size such that [FTor(1) Prov(n)) I for any 1) E [0, 1/L] and r/' E arg min |n -y-n" n/'1. We defer the proof of Lemma 17 to Section B.3.4.
there exists
Lemma 17. Suppose a is constant. For any 1>> < <> O, assume d 2 ca log(1/c) for constant There exists an c-net Ne for Frw with [Nel = O(1/c). That means, for any 1l E [0, L]
|FTV (1) Frov (1)) S.e,
for o/ arg mingEN. In 1//--
Next, we show that with high probability, there also exists an c-net for Frev with size O(1/c). Lemma 18. Suppose a is constant. For any 1 > O, assume d 2 c4 (og(1/e) for constant ct- With probability at least 1 exp( exp(-9((22m), there exists c-net N, for FTOV with [Ne] O(1/c). That means, for any 1) E [0, 1/4,
Frwv (1) - (r) S,
for r/ arg aag minlgeN. |n 1//.
Combing Lemma 16, Lemma 17 and Lemma 18, now we give the proof of Lemma 11.
Proof of Lemma 11. The proof is very similar as in Lemma 4. By Lemma 16, we know with probability at least - exp(-(((2mm),, (n) - (n) - for any fixed By Lemma 17 and Lemma 18, we know as long as d = (llo)()/e)), with probability at least - exp(- exp(-S(e2m)) there exists e-net N, and Nº. for Frsv and Frev respectively. Here, both of N, and N have size O(1/c). According to the proofs of Lemma and Lemma 18, it's not hard to verify that N. N still an e-net for Frov and Frov. That means, for any E [0, 1/4, we have
Frov (n) - Frov (erv(y')l (n')), (lo)) - Frov Se, for v/ E arg minn In v/1-
Taking a union bound over N. U UN, we have with probability at least 1 0(1/e)ex((-(((mm))
Prov(n) Frov (n) Sc
for any 77 E N: U..
Overall, we know with probability at least -
for all 17 E 10,1/L]
Frov(n) (n) (rav(n)
Frww(n - (r)v(n') + (Frw - Frw (PPov(())))))))) (T'(
$3e,
where vf E arg min In - r/'1 Changing e to e/3 finishes the proof.
B.3.3 LOWER BOUNDING Frov FOR n [1/L., oc)
In this section, we prove Frov is large for any step size 2 1/L. Therefore, the optimal step size Tilldd must be smaller than Frwv-
Lemma 12. Suppose a is large constant. Assume 2 C2, d 2 ca log(t) for some constants C22 With probability least 1 exp((-((m))
1 _ Frw( 20'02
for all 1) 2 1/T,, where C' is a positive constant independent with
33

---

Under review as a conference paper at ICLR 2021
When the step size is very large (larger than 3L), we know the GD sequence gets truncated with high probability, which immediately implies the loss high. The proof of Lemma 19 deferred into Section B.3.4.
Lemma 19. Assume 1. 2 c2,d 2 ca for some constants C22 Ca. With probability at least ex))()))(m)),
Frov(n) 20²,
for all n E [3L, o0)
The case for step size within [1/ requires more efforts. We give the proof of Lemma 20 in this section later.
Lemma 20. Suppose a is large constant. Assume 2 c2, d 2 ea log(t),foo for some constants c22 C4. With probability at least 1 cxp((S(mm),,
(n) 2C40² + 1 =0"
for all 7 E [L],, where C4 is a positive constant independent with a.
With the above two lemmas, Lemma 12 is just a combination them.
Proof of Lemma 12. The result follows by taking union bound and choosing C' minn(C,, 1/2).
In the remaining of this section, we give the proof of Lemma 20. When the step size is between 1/L and 3L, the GD sequence has a reasonable probability of diverging, we can still show the loss is high similar before. If not, need to show the GD sequence overfits the noise in the training set, which incurs a high loss.
Recall that the noise term is roughly ||( (1- )) (X ( Emin When v E [1/L, 3L), eigenvalues of Ha Stain subspace can negative. If the non-zero n eigenvalues of Husio have the same value, there exists step size such that the eigenvalues of I - H in subspace Strann is 1. t is even, the eigenvalues of I - (I Huuaii ) in Strin subspace are zero, which means GD sequence does not catch any noise in S
Notice that the above problematic case cannot happen when the eigenvalues of Huain are spread out. Basically, when there two different eigenvalues, there won't ' exist any large 7 that can cancel both directions at the same time. In Lemma 21, we show with constant probability, the eigenvalues of Hmain are indeed spread out. The proof is deferred into Section B.3.4.
Lemma 21. Let the top eigenvalues of Haain be X1 2 ... 2 An- Assume dimension d ca for certain constant c4. There exist positive constants μ. pl, p. such that with probability at least μ.,
2...
Ap'n An-a'n+1 n²"
Next, we utilize this variance in eigenvalues to prove that the GD sequence has to learn a constant fraction of the noise in training set.
Lemma 22. Suppose noise level a large enough constant C1. Assume unroll length 2 C2 and dimension d 2 ca for some constants O2 C4. Then, with probability at least Ci
(B w| H 2 C20
for all n (1),, where C₁ C2 are positive constants.
Proof of Lemma 22. Let & be the event that vd/vIL S (x(uua))) S LLd and 1/L < Ax (Huain)) <
L for all i E [nx and Vdla /4 < [|5min|] S Vda. Let Eg be the event that vdl VT. < az (x(vaa)))) L for all
VLd and 1/L < >₂ (Haata) Lemma and Lemma 45, we know both E and Eg hold with probability at least - cxp( (dd))
in] and Vdo/4 /4 ||Evatal| I vdo. According to
Let the top cigenvalues of Husin be ê1 2 2 An- According to Lemma 21, assuming d is larger than certain constant, we know there exist positive constants μl (22 μg such that with probability at least (41, Apan An- 1 2 p3. Call this event &z
34

---

Under review as a conference paper at ICLR 2021
Let S1 and S2 be the span of the bottom and top jun eigenvectors of Huai respectively. Ac- cording to Lemma 45, we know ||Emii|| 2 I a with probability at least - exp( (xp(-(((d)).
Let P1 E R=x* be a rank-jugn projection matrix such that the column span of min P is S1. By
Lemma, know with probability at least proj Smmin 2 V/2 |Sraiill Taking a union bound, with probability at least - ((()),
exp(- ((d)),
Proi Strain 2 Lunda Similarly, we can define P2 for the S2 subspace and show with probability
8
least c (S)(d)), Proji,,Srain) 2 Virdor Call the intersection of both events & which happens with with probability at least exp( (dd)))
Taking a union bound, we know E1 n & n & holds with probability at least 21/2 as long as d larger than certain constant. Through the proof, we assume & n &2 n& Eg holds.
Let's first lower bound [ Wrain as follows,
|| Br Wraiinl || = Bun (Wirai + (Xurain) ( "Erain) - W Wirain| Be,y (Wirin + (X "
Recall that we define S1 and S2 as the span of the bottom and top uun eigenvectors Huain re- spectively. We rely on S₁ lower bound || w=ll when 17 is small and rely S2 when 1j is large.
Case 1: Let o miin (Br.)) be the smallest singular value of B within S subspace. QAn-wan+1 /z/(( (2L), we have
[B min (1-(1-17))
1 L
1
9 min
1 -
2L
2
where the second inequality assumes 2 max(L?? I22 22/22//// (2)) log 2. Then, we have
||Wa,
w01l 2 mi (Be,,) (|) PPojjs (X [mmal| - 1) - 1)
/1200
U2o
2
8
32VL'
where the second inequality uses
Proj p. Strain
Vuzdo 8
and the last inequality assumes o 48yL vuz
Case 2: If uunAl > 2 waa((L) we have nyynn 2 22+Ha/(2L) since Äugn An-ran+1 >
H43 and 17 2 1/T. Let o Sy (Be,)) be the smallest singular value of Ban within S2 subspace. We have
$1 (B.))) 2
-1)
2L
where the last inequality assumes 2 4L/H3- Then, similar as in Case 1, we can also prove /Pga [|Wa,, w 2 32VT.' Therefore, we have
2
Bt. Wirain
w. 20 Husi
Bt., Wirain
Winin 2
2 | B Wurain
Winn 1|
Fuuis
L
1024
for all 17 E [1/L, 3LJ. We denote C = 21/2 and C2
1021L
Before we present the proof of Lemma 20, we still need a technical lemma that shows the noise in Svalid concentrates at its mean. The proof of Lemma 23 is deferred into Section B.3.4.
Lemma 23. Suppose & is constant. For any 1 c > O, with probability least exp(-)(e))( An (Hwana) 2 1/L and
||we,n Woatid Mmns 2 ||
w 101 (1 c)0
for all 1) E [1/T.
35

---

Under review as a conference paper at ICLR 2021
Combing the above lemmas, we give the proof of Lemma 20.
Proof of Lemma 20. According Lemma 23, we know given 1 > 0, with probability least --O(L/e) exp(-I(eed)) A, 2 1/L and ||w,,, Wvlldd |1
mas 2 | w= I (1 c)o² for all ry E [1/L,3L] Call this event & Suppose Pr[E,] 2 - 6/2, where 5 will be specifies later. For each training set S ( we also define E(A) By concentration, we know with probability least 1 - exp( exp((S((6mm)) 1/m E
(M)) 21 6.
According to Lemma 22, we know there exist constants C1 C2 such that with probability at least C1
C2a² for all n [L]. Call this event & For each training set s(h) we also define ((k) By concentration, we know with probability at least 1 exp(-S((m)),
w0'l Humn
1/m E 1
(k) C2
C1/2.
For any step size E [T,,, we can lower bound FroV (1) as follows,
Frov (n)
1
1
(k)
(k) ||2 Wealid
2
k=1
m
(k)
(1)
1
(( {
2
Win
wellid
(((t)
m
(k)
I ((
{(())]
+ (el-ee) -)]-e)(1 - 8)0²
+ 1
2
Hous
IV
1
m
(1)
w/ Holh
1 ((0 negh) [() +
1 (1(1)) 6)0
As long ā S C//4, we know
m Σx=
{ (
n 2 C1/4. Let En) be the event that w
gets truncated with step size 17. We have
(R)
1 f n 2 Hunss
w
(R)
12
{((()) negh) n e(h) {
W7.7
wT
Huuss
k=1
m
(b)
2
1 {( g/ n neg E(K)
W
wx
m k=1
2
Hoali
If 1 m
(Et n
n Egg
E(k)
/ 2 C1/ we have
m
(k)
will
1 ( n nE (1))
1
(k)
-wx
will?
1 { / }
k= W
Hana
2
Huas
k=
C
9
9C10²
x
2
16
|| | wi| 2
Here, we lower bound
by 90² when the sequence gets truncated.
Huss
(2(x)) n nehh) n Egh) } < C1/8, we know 1 If 1 1 m
-E { n ((k) ne 2 C1/8.
m
Then, we have
wx 2
1 ne {()
1
in Warin - wi
(k)
1 (e n n c()) }
win
2
Hoais
2
k=1
C₁
C20²
C2C202
16
36

---

Under review as a conference paper at ICLR 2021
Letting C3 min( 901 CxC2) 2), then have
1 (1- (1-c)(11 -))o18)002 Cza² 1
Frov(n) (n) Czo² + 2
0²
2
2
where the last inequality chooses å C3/2. In order for Pr[Ei] 2 1 - 1 we only need
2 64 log(!) for some constant C4. Replacing C3/2 by C4 finishes the proof.
B.3.4 PROOFS OF TECHNICAL LEMMAS
Proof of Lemma 14. We first show that for fixed 7 E [0. 1/L,, the crossing term
{ (B,,," "rain w², Br. Xmmin) is small with high probability. We can write down the cross-
ing term as follows:
WBin w"
Erain) ((()) Br, (Ben, w=), Strain)
Noticing that Erain is independent with [(-Xrrin) Br, (Br, (Ba, w²) we will use Hoeffding's inequality bound (Br,, in W ==.,, Br, (X (train) (. According Lemma 1, we know with probability at least - exp( - ((d)), vd/v S o (Xuain) I ITd and 1/1. & (Haiia))) S L. for all i [r] with L 100. Since 17 1/L, we know [B we have
(1 myHumin) 1. Therefore,
2 vd
[[((main) Br,,,
for any 7 E 10, 1/L.. Then, for any e > 0, by Hoeffding's inequality, with probability at least 1 exp((I2(eed))
2 =" BL., (x.a((aann)) Emain) | | Se.
Next, construct an e-net on r and show the crossing term is small for all v E [0,1/L] Let
((r) = W =w, Br.n
We compute the derivative of s(r) as follows:
(n) = Huain 1) (r-Haaa Wirain Br,,((Nurainn (Erati)
+ (Br,, w", ....lrrii (I 11llerain) (Xmain)
(- (Eraiin)
By Lemma 45, know with probability least 1 exx((S((d)), || S Voo. Therefore,
lo' - 1.5 (1 (1-7) 2)= o 21 (1- 77 1-1
L) 2)-=1 o =3L 1.5g (1 3...
2)=² a.
We can control Ig' (n)) in different regimes:
For 1) E [0, 1 we have (g'(1)) s 3L 35 to.
Given any 5 i < log - 1, for any 17 E (,4h) ((11) we have lg'(r)) = 31
ot
For any
logt I/L.], we have Ig (n)1)) S 37.1%..
Fix any >> 0, we know there exists an e-net N. with size
IN.1
1
L
log
Σ
35.
+ (1 Logt
3I
E
t
ei
t-
3.0
+3VLO = o
< 8
t-1
such that for any 7 [0, 1/L,, there exists 1/' N. with 19(1) - g(n')) ) S e. Note that 100 and a is a constant. Taking a union bound over N. and all the other bad events, we have with probability least 1 ex)(- O(1/e) exp(-S(eed)) for all [0. 1/L],
(B Wiain w". Br,o Xmmin) (mmi)))
+ 2c.
37

---

Under review as a conference paper at ICLR 2021
As long as 1 >>>> é e by e//2 finishes the proof.
O, this happens with probability at least (x)())((e Replacing
Proof of Lemma 15. According to Lemma 1, we know with probability at least 1 - exp(-I(d)),
1/L I (H & L for all E [xx] with L 100. We can lower bound (Bi,, w*) as follows,
(Br,, Wiain: w²) = ((I (I - 1-77-Hoaa 1)Hura)))) winiin Wirnin?
Ain (I - --(1- - mHHain)))) | !l
exp (-T) nt
|
By Johnson-Lindenstrauss lemma (Lemma 49), we know with probability at least 1
2 2exp(-o<dd/4),
1
2 2
(1-
7 c)..
2
Then, know with probability at least 1-2exp( 1-2exp(-ce'd//
d/4) -ep((-
11t [[]
(Ben w²)
exe exp
| l?
rf
(1 c)²
exp
1 2c
1--xp
nyt
exep
exp
L
Since e" 51-x+ for any S 0, we know exp(-njt/1) I.) S - "//p///)((1///////((((/333 For any
7 S T./t. we have exp( L) & - -/tl/(2T)) Then with probability at least ex2exp(- (oxpp-ced/44) ex)(-S((d))
2e ntt
o irain w²) 2
4
2T.
9/6
2
16L'
where the second inequality holds by choosing = 1/4. Proof of Lemma 16. Recall that
Frov (n) = Aro Pk)
1=1
For each individual loss function ArbV (1, Pk), we have
ATO (7,, Pk)
(K)
w² - (Xx(1)
(N) 1
2
Wi.
valid Svalid
(T(2)
2
Wi,m
(k)
w
1122)
+
2n
(k) Svalid
+
(((()) w", ((x(1) T
whnn
valid)
Svatid
((R)
Lo
25
valid
+
Svalid
+ L5
(vr x I)
(vin
Svalia 1)
(A)
2n
We can write (+) as 2 Vn
(k)
) According to Lemma 47, we know mmx (x((A)
valid
Ex
(x)) (
-ubbauuubansnnnn, which implies that Tmax V (k) Ed vn
x (k))
validl is
subgaussinn. Since Eo
x-(1
valid) is constant, know a Ann
x-(1)
valid) is O(1)-
v
subgaussian and o vn ((iid)) is O(D)ssubexxonentiall Similarly, we know both
1 2n
Svalid
and
x
valia
1)
(+/ (vatid |))
are O(1))subexponentia.. This further implies that A (n. Pk) is
38

---

Under review as a conference paper at ICLR 2021
(1) subexponential. Therefore, Frov is the average of m i..d. =[)>subexponeetall random vari- ables. By standard concentration inequality, we know for any e > 0, with probability at least 1 - exp(=S((e²m))
(n) Frov(n) Sc.
Proof of Lemma 17. Recall that
Frev (n) -B Wt.n - -=11 + 02/12.
We only need construct c-net for } |t,, w0 1|? Let & be the event that va/vI. s of (Xuain) I Ld and 1/L & A (Huai))
- for all E [na] and ||Etrall| I doa We have
1 E 2
Win
w w²1 E | w0 w011 Pr[e] + E
| w" 10 Pr[E]
We first construct an 6-net for TE { Ilw.. w011 Pr[E]. Let Q(n) = Ie w0 Fix training set Swain under which event & holds. We show that ((1) has desirable lipschitz property. The derivative of (n) can be computed follows.
(n) = (t.uwain (I "nHurii)) " "train W1,1 w²)
Conditioning on E, we have
(Q'( = 0 - 7 10
Therefore, we have
2 Win - w 1 18 Pr[E] = 0(1)(( 7
Ön
Similar as in Lemma 14, for any > O, we know there exists e-net N. with size (11/c) such that for any r7 E [0, 1/L),
1
[ w0 12 Pr[E] E [
E
| w 11 Pr[E] se
for r// arg minjeN, |n) 1/'l-
Suppose the probability of E is 6. We have
25L0² Wt. - w1 Pr[
2 Se
where the last inequality assumes S 25 According to Lemma and Lemma 45, we know 5 : Pr[e] & exp( (d))). Therefore, given any > 0, there exists constant C4 such that I 2la as long as d 2 c4 log(1/c).
Overall, for any > 0, as long as d = ((log((/)))))))) there exists N with size O(1/c) such that for any 7) E [0, 1/L], [Fww (r)( 3e for E arg mingeN, N, In r/|) Changing e'/3 finishes the proof.
Proof of Lemma 18. For each [m], let & be the event that va/vI < or (x S LLd for s Vda. Then, write the empirical meta objective follows,
any E [nx] and
Smain
(k)
m Ara (n, 1.)
Frov(n) = m
Σ
Arer(y, Pt) + m
39

---

Under review as a conference paper at ICLR 2021
Similar Lemma 17, will show that the first term has desirable Lipschitz property and the second term is small. Now, let's focus on the first term 1 Ex== Arer(n, 1 Recall that
ATa (7, Px)
2 ui.. w
waald
(k)
1
B
(k)
(xx
(6) tc(l)) 1|2
Wirain
w
valid)
2
(1)))
Computing the derivative of ATOT (11, Pk.) in terms of 17, we have
ATEr (n, Pk) = (L (8) train (T 17 (k)
(k) w² (wi.
(xx()) if ((A)
validd Svalid) )
Om
train
w train
Conditioning on Ex, we can bound the derivative,
0 Arer(n, (1. Pt) = 0(1) (1 (1- ")
t-1
(1
(1
1
||
[x(())
)
(va (saatle)) 1))
On
+
vil
valid
Therefore, we have
m a On
(n, Ee) = -()) +
[ +
[(Ac) Svatia
1))
m
Similar in Lemma 16, know both ( and (1a X
(k)
1)
Ja
Svalid
((1) subxxpooooo........... Therefore, we know with probability at least 1 x (1e)
exp( (m)))
1 EE
(I) [ + ( val
(1)
1)
(A))
Svalid ))
= O(1. This further shows that with proba-
m
va
bility at least exp(- (m)))))))
1
Σ
(n, Px) = 0 (1-2)²
ATM
m
k=1
Similar as in Lemma 14, we can show that for any e >> 0, there exists an e-net with size 0(1/e) for m EE AT P
Next, we show that the second term m Ex= Aror (1, Px) is small with high probability. Ac-
cording to the proof in Lemma 16, we know
An, Pa) = 0(1) (1 (|
(R) Svatid
1|2
Xx 1)
(A)) Svatid 1))
+
+
Therefore, there exists constant C such that
Anur(1, S c Σ (1
H [aid
(k)
1|
(vaa
1
|xclaie ))
1
|/satdd 1)) e
+ d
Svalid
+
Va
Vd
It's not hard to verify that
(1 [|EESRad
(R)
+ 2
((k)
|
(+
[1)
(k)
1)
Svatid |)
(k)
Lg, is O(1)-
vil
valid
va
subexponential. Suppose the expectation of
|
+ 1
Sratha
(a)
+ (taa
|) (+a |
is 14, which is constant.
Suppose the probability of Ex be 5. We know the expectation of [
Lg, is μÓر due to independence. By standard concentration inequality, for any > > O, with probability at least exp exp(-S((2m))
(1 volid
+ 1
(ak)) Sealid
+
vatid I) (>a (saail ())
(7a
vatid 1)
(+a
( 1) 14 S Cuô+Ce < (C+1)e,
where the second inequality assumes 8 V c/(Cp). By Lemma I and Lemma 45, we know < exp(- Therefore, as long as d 2 ca log((1 (1c)) for some constant c4, we have 8 E c/(Cu).
40

---

Under review as a conference paper at ICLR 2021
Overall, we know that long as d ca log(1/e), with probability at least 1 - exp(-S((c"))) there exists N² with |N'| = ((1cc) such that for any E [0, 1/]:
(n) (7/) Frev)
Frsv
_ (2C + 3)e,
for o/ E arg men |n 1- 1//1- Changing e c//(2C + 3) finishes the proof.
Proof of Lemma 19. Let & be the event that vd/vI I (X S LLd and 1/L S Ae(Harin) S
for all i E [n]] and vdo/4 Σ ||Suail| I /do. Let &g be the event that vd/vL 1 (XVall)))) S LLd and 1/L < X; < L for all i E [r] and vdo/4 S |[Evaiil| x vdo. According to Lemma I and Lemma 45, know both & and & hold with probability least exp( (xp(-(((d)) Assuming d 2 for certain constant C₁, we know Pr[E, N& 2 2/3. Also define E and e// on each training set S(8) By concentration, we know with probability at least exp(-I(m)).
Σ m
1
m
(( n
It's easy to verify that conditioning on E the GD sequence always exceeds the norm threshold and gets truncated for 2 3L as long as is larger than certain constant. We can lower bound Frsv for any 1j 2 3L as follows,
(n)
m
(R)
w
(b)
1|
m
2
valid
H
178
(k)
(A)
1|
1 ((1 2 20 =²
w
valid
(1))
where the last inequality lower bounds
(b)
w
(k) vahi
by 20 when wit gets truncated. 1r(a)
Proof of Lemma 21. We first show that with constant probability in Xusin the variance of the eigenvalues of Hyain lower bounded by constant. Let À be 1/n Σ.= As. Specifically, we show 1/n X2 X2 is lower bounded by constant.
Let's first compute the variance of the eigenvalues in expectation. Let the i-th row of Xurai be nT! We have,
27
("r
urin Xtrain )
X
JE'
X
IE IE ||:;
||
|1
E
| 1|
11
n
ISiAišn
d²
2d
(nd(d + 2) + n(n - 1)d)
nd
n22
n
Similarly, we compute E [1/n] Em=
==
X3]
as follows.
n
E
x
(X Xtrain X X
71
713
1=1
|
E Exi,
n13
15i#jšn
d²
(nd(d + 2) + n(nn - 1)d)
+
3
n2
n
Therefore, have
12
d
d
4
E
X2
X2
+
2
2
71
n
3
n2
3
i=1
41

---

Under review as a conference paper at ICLR 2021
where the first inequality assumes 2 and the last inequality uses S 3d Since n 2 dd,
know n 2 2 as long as 2
Let be the event that vd/VD= S. of (Xmai) & LL and 1/L & Ac(Hrain) S L for i E [n] with
L = 100. According to Lemma 1, we know & happens with probability least 1 - cxp( ((d)).
Let 1 {&} be the indicator function for event E. Next we show that E[[// Em= (A, X) (EH is also lower bounded.
It's clear that E [ [E]] is upper bounded by E [X²] In order to lower bound , we first show that E E X [&
E
E
(E)
is small. We can decompose
E
X
{E}]
into two parts,
R Σ n
1 13 Σ
n
E
18
71 Σ
221 1E and A S =}
+ = n
The first term can be bounded by Pr(EE Since Pr[E] S exp(-S(dd), we know the first term at most 1/6 as long as d is larger than certain constant. The second term can be bounded by [AP {Ax > b}] According to Lemma 48, we know Pr(Ai 2 -L+ 4] S exp(-52(d()) Then, it's not hard to verify that E [A11 (A1 than certain constant. Overall, we know E 1 EL {E)
> L}} = O(1/d) that is bounded by 1/6 as long as d is larger
2 E [ E i= X - 1/3. Combing 1) [E) 2 1.
with the upper bounds E [X21 [E}], we have E I E
Since conditioning on E, X is bounded by L for all i E [n]. In order to make [ EA - x)21 {E}] lower bounded by one, there must exist positive constants (41, H22 such that with probability at least #1, & holds and Ei=(0 A)² 2 P2-
Since (A=(AA 2 #2 and X; S I for all i E [n]. we know there exists a subset of eigenvalues
S C (1:} with size pa such that |A: \ 2 μa for all X; S, where μa, n4 are both positive constants.
If at least half of eigenvalues in S are larger than Ā, we know at least Pa 2L number of eigenval-
ues smaller than X. Otherwise, the expectation of the eigenvalues will be larger than X, which contradicts the definition of Å. Similarly, if at least half eigenvalues in S are smaller than X, know least Marts number of eigenvalues are larger than X. Denote μ45 25 2L
pa#4 We know
Apan An- 144.
Proof of Lemma 23. Let & be the event that vd/vT. S (Xuuin)) S VLd and 1/1, S Ar (Huain)
L for all i [n] and Vdo /4 I [ I Vdo. Let Eg be the event that vd/vL I o, (Xvati) vLd and 1/L, S (HHrtal)) Lemma I and Lemma 45, we know both & and &g hold with probability at least 1 - e(p(- In this proof, we assume both properties hold and take a union bound the end.
T. for all i [n] and vda/
||Evatil| s Vdo. According to
We can lower bound [|We,n - Wvalidll 1 as follows.
[we, Wvatidll
1 Hruas = -|wwe. w² (Xvata) Evatial Huns
> | w0 10211 Il + ||Evatiall 2 2 w", Hvatial (aatia) Evatiaa
For the second term, by Lemma 45, we know for any 1 E O, with probability at least 1 exp(-12(e2d))
1 ||Evataall 1 2 (1 - e)0
n
We can write down the third term as <[(X vatia) (Ji Hvatia (We,n) w²) ) Evalia) Suppose ar is constant, we know [|(((xatia)t] T] Hymtia (We, w²|l = O(1/vd). Therefore, for a fixed r) E [1/L, 3L), we have with probability at least - exp( ((())))
(w w", Hvatia XX x Evatia) Se
42

---

la. Here, Proj E Baxx is Under review as a conference paper at ICLR 2021
To prove this crossing term is small for all 1y [1/L, need to construct e-net for the crossing term. Similar as in Lemma 9, we can show there exists an e-net for the crossing term with size (tt/e). Taking union bound over this e-net, are able to show with probability at least 1 - O(/cc) ((2)))
Kwr. - H (Xvaaia))\vaaaaa
Evalia) S E,
for all v E 3.]]. Overall, have with probability least 1 -
-S((cc
|102, - Wealdd ll Haas
2 21lut,r - w0 I1 + n
/vaiial / - 2 (wi. - _,,, H (Xaata) (Svata)
> =lwaenn w0'l12 + (1 --)= 22--22 -2e (1 -3e)o²
for all vj E [L], where the last inequality uses a 2 1. The proof finishes as we change 3e to é'
C PROOFS OF TRAIN-BY-TRAIN WITH LARGE NUMBER OF SAMPLES (GD)
In this section, we give the proof of Theorem 6. We show when the size of each training set n and the the number of training tasks are large enough, train-by-train also performs well. Recall Theorem as follows.
Theorem 6. Let (rer(a)(I) be defined in Equation 1. Assume noise level is a constant e1. Given any 1 <> 0, assume training set size n Z á log( nm ), unroll length 2 c2 (og(A)) number of training tasks can²
<4d2 log( from and dimension d 2 ca for certain constants c, C22 C3y Ca. With high probability in the sampling of training tasks, we have
do²
IE Wl " S (1
n
for all Maain arg min F where the expectation is taken over new tasks.
In the proof, we use the same notations defined in Section B. On each training task P, Lemma 24 we show the meta-loss can be decomposed into two terms:
ATAT (17, P) 2 ||we,7 Wisin Musi + 2n ||(T,. -roj Eirain
where Wirain = w² + (Xizan) ) Eirain- Recall that Xurain is a n x d matrix with its i-th row as x. The pseudo-inverse (Xurain) I has dimension d x satisfying X train X
a projection matrix onto the column span of Xurain
In Lemma 24, we show with a constant step size, the first term in ATor(1, P) is exponentially small. The second term basically the projection the noise on the orthogonal subspace of the data span. We show this term concentrates well on its mean. This lemma servers step in Section B.I. The proof of Lemma 24 deferred into Section C.I.
Lemma 24. Assume 2 40d. Given any 1 > 6 O, with probability at least 1 m mxxp(-((())) exp(-S((emdd/n))
(2/3 < 20(1
- 2r02
n n-d- 2n
d 2²
2do2
20m
In the next lemma, we show the empirical meta objective is large when 17 exceeds certain threshold. We define this threshold Ω such that for any step size larger than î the GD sequence has reasonable probability being truncated. In the proof, rely on the truncated sequences argue the meta- objective must be high. The precise definition of r is in Definition 2. This lemma serves as step 2 in Section B. We leave the proof of Lemma 25 into Section C.2.
Lemma 25. Let r be as defined in Definition with > E > 0. Assume n 2 ed, f 2 c2, d 2 C2 for some constants c, C2 C4. With probability least 1 exp(- - /n²)),
2do²
d 0² 2do2
Frer(n)
+
8n
2n 20m
for all 1) > 7
43

---

Under review as a conference paper at ICLR 2021
By Lemma 24 and Lemma 25, know when is reasonably large, Frez (17) is larger than Fror(2 (2/3) for all step sizes v/ n) This means the optimal step size ij must lie in [0, f). In Lemma 26, we show a generalization result for E f]. This serves as step 3 in Section B.1. We prove this lemma in Section C.3.
Lemma 26. Let be as defined in Definition with 1 > > O. Suppose is constant, Assume n 2 e log( 22 ed )d, t 2 02 d 2 for some constants c, C22 C4. With probability at least 1-m exp(-S((n))
O 2d + m) Sap(-S((me' dl /n²)).
1722
(Per(n) - (r)r(n)) S
for all 1) E [0,
Combining Lemma 24, Lemma 25 and Lemma 26, we present the proof of Theorem 6 as follows.
Proof of Theorem 6. According Lemma 24, assuming 40d, given any 1/2 > > 0, with probability at least m exp(-S(n)) exp(-S((e (xp(-S((emd//n)) Fra (2/3) 20(1 1))
n-d 0²
dd 20n
As long 2 log( ( for certain constant C have
(2/3) S n- d 0² + 100m
de2
2n
Let r as defined in Definition with the same c. According to Lemma 25, as long as n 2 cd, 022 d 2 C4 with probability at least - (22((-(('mma /n²)),
2d
+ n d r²
ed n
7.5
Fror(n)= 2 8n
0²
2n
20n
2n
100n
for all 17 > 9. We have Frer (n) > Fra (2/3) for all 2 f). This implies that Miain is within [0, and ( Frrr(2222) S n-d o²
do
2n
100a
By Lemma 26, assuming a is constant and assuming n 2 clog( ed ) for some constant e, we have in 0
with probability at least
(
2a + m.) (mme dd² /n²)),
[Fer(1)) (Ter(1)) < do
for all 17 E [0, n) This then implies
1722
d
24e do 0²
Frer S Fror (Frrin)
n
2n
n
By the analysis in Lemma 24, we have
FTU (Timin)
=E
Wr, Winin
Wirain
+ E 2n
11(1n
Proj Xiir Etrain
2
Humi
=R 2
|
Wirain
1
0²
Him
2n
Therefore, know B.J /
Whrain
2
24r n
Next, show this implies
Himi
E||1 [.. w0l small.
Let be the event that 1 - c (H s 11+c e for all E [d]. According to Lemma 27, we know Pr[g] 2 - exp(-2(e21) as long 10d/c². Then, decompose E Wt. w" as follows,
-w" E Wu - w01 Wt. w-1l 188 + We. - w -="1"118))
Let's first show the second term is small. Due to the truncation in our algorithm, we know [We.n w*ll? < 01202, which then implies E | -1 (E) < 41202 =1120eexp( exp(-S((en)) As long 2 S log( 3) for some constant c, we have E. We wx 1(8) edo?
44

---

Under review as a conference paper at ICLR 2021
We can upper bound the first term by Young's inequality,
E Wrrm
"n 1| 1 (8) - (1 + )1E We.
"urain || 1 1{8} + (1 + E) Whain - {E}.
Conditioning E, have | ninn
Whrain Mynis
(1 () ()-c)|luae.n..
Wirain
which implies
[rr.nmm Whain 12 1 (1 + 26) Wrrnii
Wirain Ham
as long as S 1/2. Similarly, we also have
||aaain w² w²11 I (1 + 2e) Warinn w" 11 11 Then, we have
w² ||² 1E8}
Wr.nins
<(1
2c)
Whaai
1 (8) + (1+ c)(1 26)IE || w='ll..... {E}
Honn
+ <(5
}E //we.... - Werain || Ham
+ (1 +1+ 5c
w" 1| Uraain
48
do²
do²
<(5
+(1 5c)
(1 + 293c)
Overall, we have TE || w 11 the conditions, we know this holds with probability at least 0.99 as long is constant Ci. 2 o log( rame ) 2 o2 log( n m 2 san"
+ 293e) der
edo + 294c da? Combining all
<*d log( fum ed ), C4 for some constants c, C22 C32 C1. We
finish the proof by choosing e//294.
C.1 UPPER BOUNDING (2/332/3)
In this section, we show there exists a step size that achieves small empirical meta objective. On each training task P, we show the meta-loss can be decomposed into two terms:
AT P)
Σ i=1
(wee.
Whrnin Iz) (5: It
X Sraiin Strain )
train
2n
=2
2 ||we. Wirain Mua
+ 2n
[ - Proj Xuai Etrain
where Whrain =² + (XXuan)) Etrain In Lemma 24, we show with constant step size, the first is exponentially small and the second term concentrates on its mean.
Lemma 24. Assume n 2 40d. Given any 1 > e > 0, with probability at least 1 1 m exp(- exp(-S(("md/n)),
PTTT(2/3) S 20(1
) 20
n d 0² +
èdo
3
2n
20n
Before we go to the proof of Lemma 24, let's first show the covariance matrix Humin is very close to identity when n is much larger than The proof follows from the concentration of singular values of random Gaussian matrix (Lemma 48). We leave the proof into Section C.4.
Lemma 27. Given 1 > > O, assume n 2 10d/e². With probability at least 1 - exp(-(((e=n))
(1 (1- vn n < az (X I (1 + c)/n and
and 1 - S (H(Hiiin) 1l+c
for all i E [d].
Now, we are ready to present the proof of Lemma 24.
Proof of Lemma 24. Let's first look at one training set Stain in which y: (ww,,/)) & for each sample. Recall the meta-loss
ATEa (1,, P) 2n
Σ
(WWe,, - (W",,,") 2
1=1
45

---

Under review as a conference paper at ICLR 2021
Recall that Xaain is an d matrix with its i-th row x; With probability 1, we know Xuain is full column rank. Denote the pseudo-inverse of X X and Xmin X Xrain.
train E Rd that satisfies X - La
Irain = Xmm. where Proj Xami E IR is projection matrix onto the column span of
Ximi
Let Whrain be w" X "rain Surin where Suain is n-dimensional vector with its i-th entry &.. We have,
(Tb P)
(won. Whrain Rz) - (5: 22 X Xtainn Stain 2n
1
2
i=1
||wt,
Wnain Hmm
-
(1 Proj Ximi Etrain
We.n
Wtainn 246r 2200
X
xx
2m
1=1
We first show the crossing term is actually zero. We have,
n
72
Win Wraain; JiLi - T2 Xt
Σ rriS
Σ
Iyth xt Xtain Strain
train Strin
Wt.n
Whain'
71
7i
1=1
1
W1,1
Whrains X train Traiinttain
X X-Tain- Xtrain X baain Strain
n
1
(Wen
Whmain X Strain
TrainStrain? = O,
where the second last equality holds because X X (k)
Proj Ximin"
train
We can define w wanin as wx + (x-(&) tt!k)) for every training set s((b) Then, we have
m
m
Fror(n)
m 2
(R)
W
tain
(R)
H
(R)
m
2n
(In
Proj (+) Inie
Strain
(k)
We first prove that the second term concentrates its mean. We concatenate m noise vectors (k) Strain into a single noise vector Sunin with dimension nm.. We can also construct a data matrix X E Ramxxmm that consists of x x(&) diagonal blocks. Then the second term be written
(nm
Projxm. Etrai
V num
According to Lemma 45, with probability least Sxp(-SP(e-ne /n)),
(1-60)
2d
1+ 2dd
Euain S
n
mm
n
By Johnson--Lndeestrruss Lemma (Lemma 49), know with probability at least exp(-S(("' (m))),
1 Vnm
2 (1 2) mnd Proj X mn
2d )a.
Stmin
Srain
2 - 22
(1
mn mm
n
n
Therefore, have
Vium Strain
3r2d )²2 and n
Vnm
Proj X Seraio
1 2 (1 26 26
Overall, know with probability least exp( ( mmd/n)))
1
Vnm (Jnm
Proj Erain
12
11 -
o² +
5e2do2
2
2n
2n
Now, we show the first term in meta objective is small when we choose a right step size. According to Lemma 27, know as long 2 40d, with probability least 1 exp(-S(n)), vn/2 <
46

---

Under review as a conference paper at ICLR 2021
and o. ( s 3//n22 and 1/2 < (H 3/22, for all i [d]. According Lemma 45, we know with probability at least exp(--(nn)) ( know all these events hold with probability at least 1 exp( exp(()((n))
2//oo Taking union bound tasks,
For each k E [m/] we have
Wimin
(K)
S 1+ 2 I 50. It's easy to verify that for any step size at
most 2/3, the GD sequence will not be truncated since we choose the threshold norm as 40g. Then, for any step size 17 - 2/3, we have
Σ
m
(k)
2
M
(I - 1/ I'u (K) 1
m 2
winn
w
tain
m11
train
km
3
17 2222502 S 220 -3 -2000
(1
where the last inequality chooses 1) as 2/3.
Overall, we know with probability at least 1 - m wwxppexpppppemmm -((n)) - exp( - (2(emmd/n))
(2/3) S 20(1 )20002 + n d 0²
5c
2n
2n
We finish the proof by changing
5=2 2 by (e')2/20.
C.2 LOWER BOUNDING POeT FOR 1 (ń, x))
In this section, we show the empirical meta objective is large when the step size exceeds certain threshold. Recall Lemma as follows.
Lemma 25. Let be defined in Definition with 1 > <> 0. Assume cd, t c2 2 c4 for some constants e, C4. With probubility at least 1 - exp( (0(e (mmmmmd? fndd/vi /n²)),
2d
+ n d 0² 20m
2d
FroT(1) 2
8n
2n
for all 1 > f.
Roughly speaking, we define á such that for any step size larger than ń the GD sequence has reasonable probability being truncated. The definition very similar as 7j in Definition 1. Definition 2. Given training task P, let & be the event that vn/2 S (N(uin))) S 3//n22 and 1/2 < (,(Hmmii)) < 3/2 for all i E [d] and /no/22 /2 < ||Emaiel| I| I 22/no. Let Eg(TT) be the event that the GD sequence is truncated with step size n, Given 1 e 0, define i as follows,
2do
= inf
17
0
E 2
Wt.n
Wraii 112 Hum 1 (()
Similar in Lemma 5, we show 1 { n & 2 1 ( for any n' 17. This means conditioning on ε a GD sequence gets truncated with step size 77, has to be truncated with any step size n 2 17. The proof is deferred into Section C.4.
Lemma 28. Fixing training set Spain let Er and (n) be as defined in Definition 2. We have
(( 2 ( (
for any n/ 2 17.
Next, we show ij does exist and is constant. Similar as in Lemma 6, we show that the GD sequence almost never diverges when is small and diverges with high probability when 1 is large. The proof is left in Section C.4.
Lemma 29. Let ń be as defined in Definition 2. Suppose a is a constant. Assume 2 cd, t 2
C2, Ca for some constants e, C22 C4. We have
4
< 1j < 6.
3
47

---

Under review as a conference paper at ICLR 2021
Next, show the empirical loss is large for any 7) larger than rj. The proof is very similar as the proof of Lemma
Proof of Lemma 25. By Lemma 29, we know n is constant as long as n 2 cd, 2 C22 d 2 Ca for some constants c, C22 C4. Let & and (n) be defined in Definition 2. For the simplicity of the proof, we assume E || - Wrainll Hmm 1 {Ei ( 2 using same techniques in Lemma 3
do The other case can be resolved
Conditioning on E₁, we know || Wrain Hmm I 455 Therefore, we know Pr[E1 n (f)) 2
3x452n For each task k, define El and (( (n) as the corresponding events on training set S ((k) By Hoeffding's inequality, we know with probability at least 1 - exp( (0((s2(2'mmm /n²)),
4e-d
edd
1 E n 2x 2 45
By Lemma 28, we know 1 ( n
t/4 (m)) 2 1 { { n E/ (i) for any 1j 2 î.
Recall that
FTO (11)
(K)
(8)
2
(Tr
Proj x Strain
2
train
2n
k=1
k=1
We can lower bound the first term for any 17 > 1j as follows,
m
Frer(n) = m A=1
(k)
(k)
(k)
(b)
1 { nEg
(
2
wi.g
Waain
2
Whn
w
rain
35"
m
(k))
n ne (m)
m
k=1
35
e²do²
(k)
m
8n
where the second inequality lower bounds the loss for one task by 35 o² when the sequence gets truncated.
For the second term, according to the analysis in Lemma 24, with probability at least exp(-S(( (mdnn))))
(In Proj (n) Strain
(k)
n2 - d 0²
ddoo
2n
20n
k=
Overall, with probability at least exp(-SS(( (s (cmmd/nn) /n²)).
Fror(n) 2 8n + n d 0²
2do²
2do
2n
20m
for all 17 > n.
C.3 GENERALIZATION FOR E [0,
Combing Lemma 24 and Lemma 25, it's not hard to see that the optimal step size Vian lies in [0. ii)- In this section, we show a generalization result for step sizes in [0, f). The proof of Lemma 26 is given the end of this section.
Lemma 26. Let be as defined in Definition with 1 > e > O. Suppose a is a constant, Assume n 2 e log( )d, t 2 02 d 2 ca some constants c, C22 Cq. With probability at least 1-m m exp(-S2(n)) O 2d + m) exp( exp(-Q((me) d² /n²)).
27e2
(Fwr(1) - (rer(n)) <
for all n E (),
48

---

Under review as a conference paper at ICLR 2021
In Lemma 30, show Frur concentrates Frer at any fixed step size. The proof is almost the same as Lemma 7. We omit its proof.
Lemma 30. Suppose a is a constant. For any fixed n and any 1 > e > 0, with probability at least 1 exp(=S(eemm),
(T) - (T) e.
Next, we construct an e-net for FTST in [0, n] The proof is very similar as in Lemma 8, We defer its proof into Section C.4.
Lemma 31. Let f be as defined in Definition 2 with 1> O. Assume the conditions in Lemmna 29 hold. Assume n 2 elog( ed )d for some constant c. There exists an dc" -net N C [0, f) for FTET with N = ( tn 2dd
That means, for any 1j E [0, ni},
FFer(n) - Frur(T)) 8c2
for r/' eN -7))
We also construct an e-net for the empirical meta objective. The proof is very similar as in Lemma 9. We leave its proof into Section C.4.
Lemma 32. Let i be as defined in Definition 2 with 1> 0. Assume the conditions in Lemma 29 hold. Assume n z 40d. With probability at least m (ep(--2(n)), there exists an d' -ner tn + m). That means, for any rj E [0, î), ad
N' с [0, for Fror with \N'
O
do
FFor (n) Fror(r')1
n
for r/ arg eN" 77")
Combing the above three lemmas, give the proof of Lemma 26.
Proof of Lemma 26. We assume a as a constant in this proof. By Lemma 30, we know with probability least expp(22(mme)))) (fn")) Frer(r) Frer(n) n
ddo for any fixed 17. By
Lemma 31, we know long 2 clog( f )d for some constant c, there exists scddo? net N ((()))
for Frur with size O in By Lemma 32, we know with probability at least
there exists an ?do? -net N' for Fruz with size O pm.m + m). It's not hard to verify that N U N' is still an doddo? net for Frov and Frov. That means, for any v E [0, fi,, we have
Prer(1')) 1 8e2do2
(FEr(1) FTor(n)), (Tro(())
for r/' arg " r²").
Taking a union bound over N U N we have with probability at least 1 - -0 + emp(-(((m /n²)))²),
Fror(n) - Frer(n) 2do
for all 17 N N.
Overall, we know with probability at least m exp(((((m)) -0 +m) (exxpp((mmmm) Qmm d2/n2)) for all E [.,
(F)r Fror(n))
< Frur(n) Frur(r')) ()er(() - Frur(1/)1 (rer(1)) - Frer(r)))
272
where 7/ = arg win 11").
49

---

Under review as a conference paper at ICLR 2021
C.4 PROOFS OF TECHNICAL LEMMAS
Proof of Lemma 27. According to Lemma 48, we know with probability at least 1 - exx((((3/2)
vn v az inain) S vn vdl +
for all i [d]. Since d -
En we have vni 1o
evā S oi (( S Vv=+
SVR v10
+ Choosing
v10
t { De we have with probability at least 1
(1 -1-5)v s o, (o S (1 5) VVn
Since (Huui)) = 1/no? (X (mann) we have 1 - S A Huain) 11
Proof of Lemma 28. The proof is almost the same in Lemma 5. We omit the details here. Basically, in Lemma 5, the only property we rely on is that the norm threshold larger than 2 ||Wamin conditioning on ε Conditioning on εi, know || 5a. Recall that the norm threshold is still set as 40o. So this property is preserved and the previous proof works.
Proof of Lemma 29. The proof is very similar in Lemma 6. Conditioning Ei, know Husin| || < 3/2 and ||Maaial| I 5a. So the GD sequence never exceeds the norm threshold 400 for any 17 S 4/3. That means,
E ||wa,n Wirain 1 H.n. ( =
for 1) S 4/3.
To lower bound the loss for large step size, we need to first lower bound || || Recall that Whaai === + (Ximin) "iirain Conditioning on ε1, we know | S 2//no and (a(Ximun)) vn/2, < 2/. By Johnson-Lindenstrauss Lemma (Lemma 49), have /d/n [|Erain|| |l with probability at least exp( Call this event Eg.
which implies ((
Proj Strain|| < 3
2
Conditioning on E n &g, we have
2 3 d V
(Xuain)
" Eurai s 2/noo
6 o
n
which is smaller than 1/2 as long as 2 122do², Note that we assume a is constant. This then implies |irrinll 2 1/2.
Let (w/,,) be the GD sequence without truncation. For any step size r) E [6, oo). conditioning on E O Eg, we have
| >
(6
1)- 1)r -1) [|riinn (2* -1 2 40o
where the last inequality holds as long as t 2 for some constant C2. Therefore, we know when n E [6, xo), I {Ei En() = 1 (E n &a). Assuming n 2 40d, we know E, holds with probability least 1 exp(pxS(p Then, we have for any 1) 6,
2do
E || - Wirain 2
2 (40o - 50) Pr(Ei nEg)
Husi
where the last inequality assumes n 2 d 2 for some constant c, C4.
Overall, we know E [|we. Whain 1| fm.. 1 (E n {n)) equals zero for all (0,4/3) and is at least eddo² for all [6, oo). By definition, we know क E (4/3,6).
Proof of Lemma 31. By Lemma 29, we know ń is a constant. The proof is very similar as in Lemma 8. Let E and En(n be as defined in Definition 2. For the simplicity of the proof, we assume E ||We, Wrain 1 (E, ( ddd The other case be resolved using techniques in the proof of Lemma 8.
50

---

dc2do² Under review as a conference paper at ICLR 2021
Recall the population meta objective
n d +
Frur (n) = E w/w,.
Wwain Husin
0².
2n
Therefore, we only need to construct an c-net for the first term.
We can divide F ||wa, Wirain Hum as follows,
W
Wirain Maii
2
| Whrain 2 Ham 1 1E E w| Wrain l 1 1
E |/w.. Whain 1 Huso 1 {E1}.
+
We will construct e-net for the first term and show the other two terms are small. Let's first consider the third term. Assuming 2 40d, we know Pr[E1] I exp(-I(n)).. Since ||,,,, - Warain Himi O(x-xulbexp,neniial, by Cauchy-Schward inequality, we have Whaii H { 0(1) exp( ((()) Choosing n 2 clog(n/(ed)) for some con-
E [|
stant e, we know Wre. Wirain
Hean { S ddo
Then we upper bound the second term. Since E ||we, Warii Musi
1 { & S do and
[|w,,,) Whrai M 2 4
35"d² when wr,6 diverges, we know Pr(E, n Ex(r) S 352m
4c"d
Then, we can
upper bound the second term as follows,
3 45
4e2d
6c2
E 2 |w
Wrain 2 1 & Hran
4
35
n
Next, similar as in Lemma 8, we can show the first term | Warai Huig
1 (()()) is
Ott)-lipsciizz. Therefore, there exists an e'do" -net N for E. || Warain ll Muai with size O in That means, for any 17 E [].
1 (E, (
< e
Win - Wirain Husi 1 ((
Wer Wirsin
Hus 1 1(
n
for r/ = arg ".. 7²))
Combing with the upper bounds the second term and the third term, have for any 17 [0. n)
Frer(n) Frer(11)1
n
for r/ arg "f r²").
Proof of Lemma 32. By Lemma 29, we know n is constant. For each A E [m]], let & be
the event that vn/2 S (x(())))
train I 3//o/2 and 1/2 < >,(H((h) train) I 3/2 for all i E [d] and < 2./no. Assuming 2 40d, by Lemma 27, we know with probability at least m expp exp(ex(((m)) (-)) & hold for all le E [m].
Vña/2 /2
(k))
Strain
Then, similar as in Lemma 9, there exists an -net N with |N' = 0 + m) for Frer. That means, for any 7) E [0, f).
2do²
Fruz (1) Fror x 2do²
for r/ arg o/s n").
51

---

Under review as a conference paper at ICLR 2021
D PROOFS OF TRAIN-BY-TRAIN V.S. TRAIN-BY-VALIDATION (SGD)
Previously, we have shown that train- train-by-validatioon generalizes better than train-by-train when the tasks are trained by GD and when the number of samples is small. In this section, we show a similar phenomenon also appears in the SGD setting.
In the train-by-traie setting, each task P contains training set Syain (())) The 2n Eiz,y) ((w, x) - y)² Let {wr,} be the SGD sequence running on f(w) from initialization (without truncation). That means, Wra 1,-1.n - 17 (V((w.-..) where (f(w,-1,)) = ((w (( Vi(r-1))
inner objective is defined as f(w) = 1
Ii(r-1). Here in- dex i(T - 1) is independently and uniformly sampled from [n]. We denote the SGD noise as 11-1,1 = (f(w--1.)) vf(w+-1,,). The meta-loss on task P is defined as follows,
ATOT(M) P) = f = ESOD
Σ
((we, x) - y)²
2n
where the expectation taken over the SGD noise. Note Wh,r depends on the SGD noise along the trajectory. Then, the empirical meta objective (1) is the average of the meta-loss across m different specific tasks
FFET(z) (1)
TTT(()) Ps).
(4)
In order control the SGD noise in expectation, we restrict the feasible set of step sizes into ((1/d)
We show within this range, the optimal step size under FreT(H) is (21/d) and the learned weight is far from ground truth w" on new tasks. We prove Theorem 9 in Section D.1.
Theorem 9. Let the meta objective FrOT(M)) be as defined in Equation 4 with n E 11/4,d/44 Suppose a is a constant. Assume unroll length 2 o2d and dimension d 2 C4 log(m) for certain constants 02 C4. Then, with probability at least 0.99 in the sampling of training tasks PI, Pm and test task P.
Mrain 22(1d) and ESOD / w =2(02))
for all Vraii E arg mino 27.3 (n))( where L = 100 and W.n is trained by running SGD on test task P.
In the -vviidii- setting, each task P contains a training Sman with ni sam- ples and a validation set with n2 samples. The inner objective is defined as f(w) = 2n, (z.g) ((w,z) 2)² Let {wr.}} be the SGD sequence running on f(w) from ini- tialization 0 (with the same truncation defined in Section 4). For each task P, the meta-loss AroV(m P) is defined
1
(no ESGD
Σ
(Wen, 2) y)²
2n2
(
The empirical meta objective Frov (21 (n)) is the average of the meta-loss across different tasks Pt, P2...., Pm.
(m) (m (T)
Frov
Arw(mn,ng) Pw).
(5)
In order to bound the SGD noise with high probability, restrict the feasible set of the step sizes into O( (ug= Within this range, prove the optimal step size under Frov(es,n2) is (1/(l) and the learned weight better than initialization 0 by a constant on new tasks. Theorem 10 proved in Section D.2.
Theorem 10. Let the meta objective Frov ms) be as defined in Equation 5 with n1, E Assume noise level is a large constant ey- Assume unroll length t 2 czd? log (d),
52

---

Under review as a conference paper at ICLR 2021
number of training tasks m 2 C3 and dimension d 2 Ca far certain constants c22 C3. C1. There exists constant C5 such that with probability at least 0.99 in the sampling of training tasks, we have
(1/Lt) and IE /. w=1l || -1-= -1===[(00--
Villid
Frov (m) (1), where the expectation is taken over the new for all Walld arg min osns ag (ox-
tasks and SGD noise.
Notations: In the following proofs, we use the same set of notations defined in Appendix B. We use EPsT to denote the expectation over the sampling of tasks and use ESGD to denote the expectation over the SGD noise. We use E' to denote Ep-yESSD. Same as in Appendix B, we use letter L to denote constant 100, which upper bounds || with high probability.
D.1 TRAIN-BY-TRAIN (SGD)
Recall Theorem 9 follows.
Theorem 9. Let the meta objective (r))(()) be defined in Equation 4 with E [d/4, 1d/4,3//4.
Suppose a is a constant. Assume unroll length t 2 c2d and dimension d 2 C1 log(m) (m) for certain constants 02 Ca. Then, with probability least 0.99 the sampling of training tasks PI, Pm and test task P.
Momin (2(1d)) and ESGD / w01 S2(02),
for all Mirain E arg min 27.4 Fror(.)) (n), where L 100 and Wenno is trained by running SGD on test task P.
In order to prove Theorem 9, we first show that Veain is (2(1d) in Lemma 33. The proof similar as in the GD setting. As long n O(1/d), the SGD noise is dominated by the full gradient. (()m)),, which implies that Virain ((1/d).
Then, we can show that Arur (17 P) is roughly We leave the proof of Lemma 33 into Section D.1.1.
Lemma 33. Assume 2 c2d with certain constant C2. With probability at least - mexpe-eppp-eee (2(()) in the sampling of m training tasks,
1
Tirain
6L7d
for all Wrain E arg ming 2Eda (r)
Let P (D(w*), Swain E) be an independently sampled test task with |Staia For any step size 1) E lo zZae.. let Wt.n be the weight obtained by running SGD on f(w) for steps. Next, show ESGD ||Wt. w=1l = A(o²) with high probability in the sampling of P. Lemma 34. Suppose is constant. Assume unroll length 2 c2d for some constant C2. With probability least cxx((-((()) the sampling of test task P.
3d/4].
ESGD [ew.. - w 112 2 128L
for all 7) E LoL-a: zb
where We, is obtained by running SGD on task P for iterations.
With Lemma Lemma 33 and Lemma 34, the proof of Theorem 9 is straightforward.
Proof of Theorem Combing Lemma 33 and Lemma 34, we know as long as o is a constant, t 2 c2d, d 2 c4 log(m), with probability at least 0.99, Viain = ((1dd) and ESGD | w ())²), for all Vini E arg minog 5253
Fror (n).
D. DETAILED PROOPS
Proof of Lemma 33. The proof is very similar to the proof of Lemma 2 except that need to bound the SGD noise term. For each k [m], let & be the event that VdlVT. (x(urinn)) S
53

---

Under review as a conference paper at ICLR 2021
VLd and 1/L (aiin))) < L for all E [n]] and vdo/4 /4 s |[ I Vdo. According to Lemma 1 and Lemma 45, we know for each & E [m], & happens with probability at least 1 exp( Taking union bound over all [ma], we know ARe(m]&R holds with probability at least 1 - exp(- From now on, we assume [ee[m] Eg holds.
For each k E [m]], we have
ATT (n, Pk) = ESGD
2
(w Wt.n
(R)
w
train
(K) ||
Since 1/L E (H(lk) train
S L and (win)
waiin
(k) is in the span of H (itk)
we have
ESGD
wiin
(k)
uaino || (n. Pt) - ア
(k)
L
EsGD
(k)
(k) train
2L
Recall the updates of stochastic gradient descent,
(1 - n7 w
(8) train
train ) (w 20 (8)
(Ks)
(R)
2,
1 1,10
Therefore,
ESCD
w
train
(k) 2
(k)
= ||(1 - me (hin)) (wi
(k)
(1)) ||
2
+1 2
|
|2
We know for any 5 1/L,
(1 - 2nL)
(k) |
w (A) train
(k) (1v - w (8) ||
S (1 - 2)
w 11-
(k) ||
w
The noise can be bounded as follows,
1/ ESGD
2 (k) !2 111
(b)
w 1
ESGD
1=(1-1) i(t- (w
(k)
(1()))
11 tain (wi-1.n)
(k)
- w (rain)
2
|w
(k)
1
<n² Esan
| 1 f(t 1) (
w (A)
mmin))
2
[w 111-1.1
(k)
Sn² max i(t-1)
(k) || || 1oo-1.m wrain
|
(7(
Since ||Xirain|| S VLvd, we immediately know max:(e-1) | S VLVd. Therefore, we can bound the noise as follows,
ESGD
|
(k)
1
w
(R)
Sn max i(t-1)
11
(R)
(A)) train (p))
<T.2
"raan
(k) 2
As long as 17 S d we have
(1 (1-77) (1-nL)
1,11,
(k)
(k)
< ESGD ||
[ waan
(k) (k)
2
1w,-1.1
$ (1
?
(k)
w (b)
wrain
2L
This further implies
(1 n-) Wnrinn 2| < ESGD
w - w
(k)
winin
(k)
- (1
17
)r
||Warin
2L
Let 172 : I
21 we have
L 2 (1
(7.
Pb) 5
| 11?
54

---

Under review as a conference paper at ICLR 2021
Let 7/1 61 for all 17 [n, we have
1
1
(1, Pa) 2
2T. (1
) || ||
6T.1
As long as t 2 a2d for certain constant c2, we know
2L (1
6I.d || 11 > -
1
L
1
)
|
2
4
As this holds for all & E [m]] and Frur = 1/m Em Aror(1) (1), Pt), we know the optimal step size Rriin is within lon 213al.
We rely the following technical lemma prove Lemma 34. Lemma 35. Suppose O(1/c) ((1/))xxp(-1 (((()))
a constant. Given any > 0. with probability at least
Wean w², BB.n((uunnn " Emain) Se,
for all n) E [0, zt-ll.
Proof of Lemma 35. By Lemma 1, with probability least - exp( exp(-S(d)), vd/VI S L for all fore (|((X"aai))" (een w*)l S 2/L/vd. Notice that Euain is independent with [(Ximin) ||] BB ( winn w*) By Hoeffding's inequality, with probability at least exp(=S((edd),
(Xiin)))) I VLd and 1/L S >;(
[n]. There-
Sc ([(( Be, Be, Eiraii)) {
Next, construct an e-net for 7) and show the crossing term is small for all r E [0, Z. For simplicity, denote ((1)) = W w², (Ximii)) Taking the derivative of g(n), have
(1( (Huiial Husia) )-1 1 Be, (xainn)))) (SErain) + W w", H n ) ("(maan
(Xirai)) (Srriin)
According Lemma 45, know with probability at least 1 exp(-S(d)) | Therefore, the derivative (n) can be bounded as follows,
Vda.
(n)) ((1)((1 2
Similar as Lemma 14, there exists an e-net N, with size O(1/e) such that for any 7 E [0, s there exists 7/ E N. with ((1n)-((r) I e. Taking union bound over Ne, we have with probability at least 1 - ((1ee) exp( Sapp--2tie (2((E d)), for every 17 E Ne,
| B Winin w", Be,n (e.n((aran))) (urai) S
which implies for every E [0, 3l.7l.
K BB w", (Nuraaa Eirain) S 2c.
Changing to é'/2 finishes the proof.
Proof Lemma 34. According to Lemma and Lemma 45, we know with probability at least 1- 1-exp(-S000 (x))) vd/vL S (:(mmnnn) < /Ld and 1/L < Ax(Hmain)) < for all [n]] and
Vdo /4 < |rainl S Vda. We assume these properties hold the proof and take union bound at the end.
Recall that ESGD | "0|l can be lower bounded as follows,
EsGD |/,,,,
11 ESCD (e,n( (Xizin ) Eirain) Σ (I H) nT.0 w²
Bt (wiain + (Xuain) (uain)
- w0
Bi, (Xxrain) Emain| + (Br, Winnnn w", (Nemnn)) Ecrain))
55

---

Under review as a conference paper at ICLR 2021
For any 17 loz 2tsal
can lower bound the first term follows,
(X,n( & ||
nt
2
x²
2
exp
16L
t
o²
1 exp
6l%d
16L
64L
where the last inequality holds as long as 2 c2d for certain constant Cg.
Choosing = o²
Lemma 35, we know with probability at least exp(-
2567.
o²
Wi w", BB,, (
256L
for all 1) [0, zt-al-
Overall, we have ESGD || 1²1 2 1282 Taking union bound over all the bad events, we know this happens with probability least exp(-
D.2 TRAIN-BY-VALIDATION (SGD)
Recall Theorem 10 as follows.
Theorem 10. Let the meta objective (rov())n)) be as defined in Equation 5 with n1. T22
[d/4, 3d/4). Assume noise level a is a large constant e₁ Assume unroll length t 2 o2d2 log (d), number of training tasks m c3 and dimension d Z C4 for certain constants c2 C3, C4. There exists constant such that with probability at least 0.99 in the sampling of training tasks, we have
Volld = ((1/L) and IE /w - -w²11² ||= 2(1)
(ToV()) (1), where the expectation is taken over the new for all Walld arg msnosns agd (a)
tasks and SGD noise.
To prove Theorem 10, we first study the behavior of the population meta objective Frby. That is,
2 || w² (XXaatu) Evatid 1| H
1
Fruv(n) (n) = Epwy Arv (n, P) =IE ESGD
1 =EP ESCD, ||we. w²1l + 0²
2
We show that the optimal step size for the population meta objective Frov is @(1/t) and EP-TEsCD || w1 | R(1) under the optimal step size.
Lemma 36. Suppose is large constant c1. Assume t 2 czdl (d), d Ca for some constants 22 C4 There exist m, 12, = (1/(l) with Th < < tJ and constant 0s such that
o²
Frev (12) - || 1
C+
10
2
a²
Frev (1) 2 || 1|2
C+
Vn E m0
u [ms: dz log (d)
10
2
where C is a positive constant.
In order to relate the behavior of Frev to Prov. we show a generalization result from Frev to Frev for 7) [0, ogd log (d/e))
Lemma 37. For any 1 > e >>> 0, assume is a constant and d 2 c4 log(1/e),oor some constant C4. There exists constant C2 such that with probability at least (11/e)exp(-01)) exp(-S((e=m))
(r)v()) Frwv (n)) S,
1 for all n E 10, oz log (d/e)
56

---

Under review as a conference paper at ICLR 2021
Combining Lemma 36 and Lemma 37, we give the proof of Theorem 10.
Proof of Theorem 10. The proof is almost the same as in the GD setting (Theorem 8). We omit the details here.
D.2.1 BEHAVIIR OF Frov FOR 7 [0, ng log
In this section, we give the proof of Lemma 36. Recall the lemma as follows,
Lemma 36. Suppose a is large constant et. Assume i o2d (d), 2 ca for some constants
22 C4. There exist nh 12, = (1/(l) with 1h < 1/2 < 1/a and constant C5 such that
9
x²
Frev (12) - 1|2
C+
10
2
a²
Fre (n) 2 ||=*11
C+
+
Vn E [0,
U [ma:
10
2
cnd log (d)
where C is a positive constant.
Recall that (T) Esan1/2 [|y,, - wI !|? Recall that we truncate the SGD sequence once the weight norm exceeds 4yTo. Due to the truncation, the expectation of 1 /2 ||,,, w²|l² over SGD noise is very tricky to analyze.
T ||w,, 11 + 02/2. Denote Q(7)
Instead, we define an auxiliary sequence (wor,,) that is obtained by running SGD on task P without truncation and we first study (') == 1/2 1/2EsGn I w w01 In Lemma 38, we show that with high probability in the sampling of task P, the minimizer of Q'()) is (1/(). The proof very similar the proof of Lemma 13 except that need to bound the SGD noise at step size 1/2- We defer the proof into Section D.2.3.
Lemma 38. Given a task P, let {wt.n) be the weight obtained by rumning SGD on task P without trancation. Choose With probability at least / Ld and 1/L < (H S for all [n] and /da/ /4/4444 ||Emailll S vda and there exists h, 12, T33 = ((1/t) with 1h < m22 < nss such that
large constant Cj- Assume unroll length t 2 czd for some constant co. exp(-I(d)) over the sampling of task P. vdlv < or (x(umn))) S
Q' Q1(12) = 1 sGD | - w 11
|| 1w0
- C
2
C
Q' (n) == 1/2EsGD ||w6.n - w²1
w 11
2 22
vn E [0, U [ns, 1/L]
where C is a positive constant.
To relate the behavior of Q'(r) defined on {wr,, to the behavior of Q(7) defined on (wr.))- We show when the step size small enough, the SGD sequence gets truncated with very small probability so that sequence {wr,p} almost always coincides with sequence (w',,) ). The proof of Lemma 39 is deferred into Section D.2.3.
Lemma 39. Given task P, assume Vd/VI. S miinma S LLd and 1/L S (4 L for all E [n) and Vda / & ||Erriell & Vil.. Given any 0, suppose ni ogd log" (d/e) for some constant Cs, we have
[Q(n) - Q'())) c.
Combining Lemma 38 and Lemma 39, we give the proof of lemma 36.
Proof of Lemma 36. Recall that we define Q(7) = 1/2EsGD [|u,, w and Q'(n) =
||vt,, 1/2
- w²1 Here, (wh_,) is SGD sequence running task P without truncation.
According to Lemma 38, with probability at least 1 - exp(-9(d)) over the sampling of task P. ValvT. & oi (Xuran) & VLd and 1/L. S A (Hrain) L for all i E [m] and Vila /4 [[ S
57

---

Under review as a conference paper at ICLR 2021
do and there exists 7/, 72. y7s (1/tt) with 7n1
72 nss such that
(1 - 2 ||001 11 C
C
Q'(1) 2 1|=
Vy [0, mi U [ma. 1/4]
where is positive constant. Call this event &. Suppose the probability that & happens is 1 6. We can write Ep-TQ(n) as follows,
Ep-TQ(1) = Ep-r(Q(m) + Bp-r(Q()))))rr)))
According the algorithm, know ||wz.ll is always bounded by 4vLo. Therefore, Q(1) 1/2 ||,t, - 1² < 13Lo². By Lemma 39, we know conditioning on E, 1Q(n) Q'(1)) S e for any S agd (d/e] As long as t 2 c2d log (d/e) for certain constant C2, we know 7/3 S
czd log' (d/c)'
When = 12, we have
E EptTQ(12) S (Q'(1) + +1 5) 13Lo
|| 1| - -C+e (1 (1-8) + 13Lo28
1
1
9C
$
1 11 - 13T 28 +
|w01 10=
2
10"
where the last inequality assumes 8 <
C and
C
200Lo
20
When 17 E [0, U [73,, egd lox (d/e) we have
BP-TQ(m)) 2 (Q) - <) (1 - 8) 13L028
C
2 |w"l 1
(1 -6) - -13Lo²8
-
2
IV
|
C
8
13L - c = ||
1
6C
2
2
10
where the last inequality holds as long as 8 I 2801.²2 and c 20
According to Lemma 38, we know < ((d)) Therefore, the conditions for can be satisfied as long d is larger than certain constant. The condition can be satisfied long as 17 <
ezd (aj for some constant C5.
D.2.2 GENERALIZATION FOR E [0, Tod"loga
In this section, we prove Lemma 37 by showing that Fro((n) (1) point-wise close Frev (n) for all
v E [0, ozd [oo"" (d/e). Recall Lemma 37 as follows.
Lemma 37. For any 1 > e > O, assume a is a constant and d 2 c4 (og((1)) some constant CA. There exists constant e, such that with probability at least 1 O(1/e) exp(-S((²m))
(F)ov()) Frov(n)) Sc
1 for all n E [0, es log (d/c))
In order to prove Lemma 37, we first show that for fixed v with high probability Prov(n) (1) is close to FTw((n). Similar as in Lemma 16, we can still show that each ArMV (7, P) is ([))sssbbexoonential The proof is deferred into Section D.2.3.
Lemma 40. Suppose a constant. Given any > O. for any fixed n with probability at least 1 - exp(p (
(To - (rov(n) se
58

---

Under review as a conference paper at ICLR 2021
Next, we show that there exists c-net for Frov with size O(1/e). By c-net, finite set Nº of step sizes such that |rav (n) - -rsv (n') I for any 1j and r/ E arg mingeN, 117 n/1. The proof is very similar in Lemma 17. We defer the proof of Lemma 41 into Section D.2.3. Lemma 41. Suppose
there exists
constant. For any > E > O, assume 2 сд log(1/e) for some C4- There exists constant Cs and an e-net Ne C [0, osd log (d/e) for Frov with |Nel O(1/c). That
means, for any 1l E [0, csd (oggte))))
1
(Frov(n) Fro( sc
ff arg mingeN |n |n-1/ 1/1-
Next, we show that with high probability, there also exists an e-net for Frav with size O(L/e). The proof is very similar the proof of Lemma 18. We defer the proof into Section D.2.3.
Lemma 42. Suppose a a constant, For any probability at least 1
> O, assume d 2 с4 log (1/e) )) for some Cạ. With there exists constant Cs and e-ner No C [0, osd (d/e)
for Frov with |Ne] O11/c). That means, for any 7) E [0, og log (a/e))
(Fov(n)) (r)v(n))) Sc
for n/ arg aigmin In 1//-
Combing Lemma 40, Lemma 41 and Lemma 42, now we give the proof of Lemma 37.
Proof of Lemma 37. The proof is almost the same as the proof of Lemma 11. We omit the details here.
D.2.3 PROOFS OF TECHNICAL LEMMAS
In Lemma 43, show when the step size is small, the expected SGD noise square is well bounded. The proof follows from the analysis Lemma 33.
Lemma 43. Let {wr be SGD sequence running task P without truncation. Let n'r,, be the SGD noise at wh.n- Assume vd/VI S (x(Xmmin) I VL T for all E [rx] and ||Smatell S /do. Suppose E [0, 21.3al: we have
ESGD ||"",p1' AIL302d
for all T St.
Proof of Lemma 43. Similar as the analysis in Lemma 33, for S 2L we have
ESGD
||m*t,,l'" 1| /w [ S LLd PPd|/w/-1, Wrain
and
ESGD ||w Wirin 2 (1 2T. Therefore, have
-- || 112
Wwrann + (X xt &Cminnl
4Lo².
ESGD ||r < 2 ddEGE |wh.ng - Whaii 1| 5 odd.
Proof Lemma 38. We can expand Q'(1)) as follows,
Q'(n) ESGD | w=ll
ESGD
Win + Be,y(XXrainl Exrai 17 Σ (I
n HHainn) )
1-1 n/ w²
T=0
Bi,,, Be Winin
w=11+ (Xerain) Sarain ||
2_
1/2
ESGD
Σ r=0
[-1
(I Husin)) 1-1 1-
) n
1-12-1
2
+ ( (Bi,, Wirain w², Be,n Surain)
59

---

Under review as a conference paper at ICLR 2021
Denote
B Wainn w= + -w1 Be, (Xrain) Strain|] 1 11²
G(n)
ESGD Σ (1
nyHurinn) )-1 7/ T.N
2
We first show that with probability at least exp(- there exist 7/, 72 133 (1/t)) with
122 < ns such that G(1z) $ 1/21|=0112 - 5C/4 and G(r) 2 1/2 I |011 - C/4 for all
Th
n E
[0.m] U [ms, 1/L].
According to Lemma 1, know with probability least exp(-9(d)), vd/vI S (X <
d and L/L L - A, (HHain) I L for all E [n]. According to Lemma 45, we know with probability least -
Vda S ||mmn s Vdo.
Upper bounding G(12): We can expand G(n) follows:
1 G(n) : 2
1
172
[ B W 11 + 2
BB.o (X Erain
+
ESGD
Σ (I
1j Humin) )-1
2
r=
||="|| + Be 112 + 1 (enann)n) Etain ||?
t-1
ESGD
Σ (1 11 )a
2
2
r=0
(Be,, Wrain w²)
Same as in Lemma 13, we know 2 || Be,, w
2 + 2 B mmain) Eminn || - 1,31,11222 For the
SGD noise, by Lemma 43 we know ESCD Therefore,
|
||
< 3.30 d for all t S t as long as 1 S 21
2
17
ESGD
Σ 1=0
(T n mainn)
n
7
EEDD
|n/,, 2 < 2T < 12
2
T=0
where the last inequality assumes 2 d. According to Lemma 15, for any fixed 1) E [0. L./1/ with probability least 1 exp(-S((d) over X Xrain
npl
B Wrain w²)
16L
Therefore, for any step size S 21
G(T)
2 1 11 + 3L
nt
1
||
nt
16L
2
32T
where the second inequality holds as long as 7 S 96 than 21 assuming 2 Then, we have
Choosing 1)2 9814 that is smaller
5C 4
G(mz) v 2
||
where constant C
30721.0a2
Lower bounding G(n) for n E [0, ml Now, we prove that there exists = O(1/t) with
T < 722 such that for any E [0, m.), G(r)) 2 1/f || 112 C. Recall that
1 |w=1|2
1 l| Wrai 2|2 + _ (,,,, EErnin 2 17²
G(n)
ESGD 2
Σ (I 11 Mriii)) n/ 7.97
(Br, WBr,n w²)
2, 100 12 (Bt, Wiiin w*)
Same as in Lemma 13, by choosing 7
abst we have for any n E [0.
C
C
G(n) 2
1100 0
2
4
60

---

Under review as a conference paper at ICLR 2021
Lower bounding G(n) for E [ns. 1/L]; Now, prove that there exists 77 (1/tt) with ?s > 1/2 such that for all 17 E 1/
C
G(n) 2 2
1100 11=01=-
4
Recall that
1
1
Ben (X ( 1|a + 172
G(T)) Br, W "² =11
ESGD
m ) n
22 (X.,((uruil Suain |l?
Same as in Lemma 13, by choosing = L/t(2) as long as 8vL, we have
G(n) 2 ||2
for all v E [1a, 1/L Note < 1/L as long as 2 log(2)
Overall, we have shown that there exist 7h 12, 73 (1/0) with vn < 1/2 < 73 such that G(1z) S 1/2 | 5C/4 and G(n) 2 1/2 [| 11 - C/4 for all 1 E [0. ml U [ms. 1/L]. Recall that ('(n) = G(7) + Wr w². Br., (Xirain) (iminn)) Choosing e = C/4 in Lemma 14, we know with probability at least exp(-22(d))
BBn. "inin w", Be, (2.,((aain) (mmin)) I C/4 for all n E 00, 1/T]- Therefore, know (1222 $ 1/2 w* C and Q'(1) 2 1/2 | C/2 for all E [0, U [73.1/L1 1/L].
O
In order prove Lemma 39, first construct a super-martingale show that as long as task P is well behaved, with high probability in SGD noise, the weight norm along the trajectory never
exceeds LoLo.
Lemma 44. Assume vd/v ox man) S LLd and 1/L S Ac(H S L all i E [n]] and vdo /4 S [[Emoial| S doa. Given any > > 0, suppose nj S ag log (d/6) for some constant cs. with probability at least 1 in the SGD noise,
|| < 4VLLo
for all 7 t.
Proof of Lemma 44. According to the proofs Lemma 43, as long as S 1 we have
ESCD [I - Wimai 1| [ $ (1
2L 11100-100 - Wirain
7)
Since log is a concave function, by Jenson's 's inequality, we know
ESGD
[lo
w Wirain| || [w//1.1
< log ESGD || Whaii
2 (w'_1.1 1.m I log [| - Wbrai|| 1| + log(1
"7 2L
Defining G. log w/ Wirain bound the martingale differences.
1 log(1
3) know Gr super-martingale. Next,
We can bound |G, LSSG (BsGD(G.lude (GG.G//--.... as follows,
[11 11 11 (w{ Wirain) 177711111 1,17 11
|G. - ESGD (Grl u w//1,p)1 S
max log m/-..n thii
[11 v/HHwiin) (w) Wirnin) 7m0 1.17
We can expand ||I H)Hrain) (w (wh_1, Wiraia) mmi2.. ??? as follows,
[[ ) (w/-1,, Wustn) 17111111111" 2
= (T THH ( Wirain) 2n (14- 1,00 (I
Wirai)) + +1² 11 -
61

---

Under review as a conference paper at ICLR 2021
We can bound the norm of the noise as follows,
| ||
Zi(t- 1) (u/-1. 1. Wrain) Huain (w/ Werain)
11(t-1)=111t () Wrmin) /|| + Hrain (w/-1,1 Frain
Whrain)
(Ld L) /1'-1.n Werain 2Ld |104_1.1 Werii ||
where the second inequality uses ||> v Ld. Therefore, we have
12m (n6- 1mm (1 - s)ddmmin)( (w/- Warain)) S 4Lnd || [ 1,1 Whaiin ||
x/² |n4-1.011 I rf |108-100 Wiaii
This further implies,
|G, BSsDDGr/kus (
|| - mn (wtrain)(///))
-u/-110 Umain]] + (4Lnd + 4L'r7dd))) 1|2 1.n Wrrain
< log
(T 11 H) ( (wik-1.0 Wirain) ||? -Tadd | Wraiin
8Lnd + 1/=
S
<log
1 (1 2L, - -La1dd
S 16Lnd + 8L?
where the second inequality
uses || (pM--
Wimin]]
2L)) ||u|- Wasin || The last inequality assumes S 12La and uses numerical inequal- ity log(1 + x) < Assuming y z 1/(L)), we further have [G, ESGG ( S Ldndd
By Azuma's inequality, we know with probability at least 1 8/t.
G. S Go + L2V 22nd (tg(
Plugging in G2 = log |w/.. - Wirain have
log(1 2 and GD = log ||wo Winain 112 = log || 1|
log ||'6.n
log |train 112 :log(11 1) I22 122 22nddogg
Warain
21
7 + L2V/2nnlogg(///
< log ||
Wmiin
2L
This implies,
2 W 1| 12e (- 12 (1)
wh.,, Wirain
|| 2 exp (O log (d)
Wirann
"exp (2/3),
where the second inequality assumes 17 S eg (dog for some constant Cr- Furthermore, since [|rranll |I s (1 +1++ VL)a, we have ||w/,,/| $ (1+ 1/3) || < 44Lo.
Overall, know long as 1) S (ddao with probability at least 5/t, /w/,,l ll S Av...
Since this analysis also applies to any T S t, we know for any т, with probability at least - 8/t, [
< 4vLo. Taking a union bound over 7 S t, we have with probability at least 8,
/w/ < 4. To for all <
Proof of Lemma 39. Let be the event that [ww < 4v for all 7 < t. We first show that
ESGD [|e,, - w² 2 is close to ESGD I|wi,, - w² '12 {E}. It's not hard to verify that
ESGD ||Wn,, w= w0 = ESGD ||wh. w 1| (E) I|u n= Pr(E).
62

---

Under review as a conference paper at ICLR 2021
where u is fixed vector with norm 4vLo. By Lemma 44, know Pr(E e/(25l0?) as long as 7 S ogd (d/e) for some constant c5. Therefore, we have
EsGD || - w011 ESOD | - 118 Se.
Next, we show that ESSD ||wl - w² 11 {8} is close to ESGD |w/,,, - w01 For any S T S t let E, be the event that || w Lv and || 4v Lo for all r' Basically &, means the weight norm exceeds the threshold at step r for the first time. It's easy to see that Uš E. Therefore, we have
ESGD [ w01 "I1 ESGD ( w=1l 188 + Σ ESGD | w =²1l21 1(8).
Conditioning on &,, we know 1. 4V..o. Since we assume
v S (X S V VT.
all i E [rx] and Strain < vda, we know ||Waain| 2 Lv, Therefore, we have ||u66-1.1 Wrrain S 6o.o. Recall the SGD updates,
whr,, Wtrain (1 11lleriin) (ur (2' - Whaii) 1
For the noise term, we have 7) | I 27 /1/Ww"-,,00 Whain that is most
|| ||0,- 1.0 Whain
assuming < FLd Therefore, we have /ww Wrain S 2 |w-- Waaii that event & is independent with the SGD noises after step т. Therefore, according the previous analysis, we know as long as 17 S 21.d.
< Lo. Note
ESGD
|
Wirnin 11 [918 S
[w' Wirnin 112 < 20"20
[|w6.. w | as follows,
Then, we can bound ESGD
ESGD
|| - w. 10'1218,
||w/k.n - Wasin + Warain w0 1=-12 |c,]
-ESGD
<BSGD
[|w//n Wirain | + 2FSCD [||w/.
Winai [& | w=1l +
+|| || w² 11
<2T,702 2La 3voo + 9Lo² S 3
Therefore, have
EsCD ||u6.,n - w² 1 = Σ
EsCD [|wek. - w=11( Pr[E.]
1=1
<31. 2 Pr(E,] = =3T?0² 3T.202P((E) & 3T.03e.
This then implies that ESGD |/w w0 w²
ESGD |w w² w=1l21 S3L
Finally, we have
ESGD [|W,. - w01 - ESGD
BkGD||w//, Il w w01
< ESCD [|We. - 112 EsGD Ilw,, w¹12 1 { + EsGD || - -w"l" w01 -Eso I| w 188
(3I20² +1)
as long 1 < og (d/e) Therefore, IQ(n) Q'(n)) s (3L30² e/2. Choosing e'
+31 finishes the proof.
2x
63

---

Under review as a conference paper at ICLR 2021
Proof of Lemma 40. Recall that
Frov (n)
Arw (1, P)
1
ESGD W/n
1
(K)
(k) 22
(1
m
k=1
Similar as in Lemma 11, we can show
(8)
(8) valid
2
is 011)-sshhexonnntiial which implies
sald
E 1
(R)
w valid m:
2 is s(xxxsbbexponential. Therefore, Frov (1) is the average of m ii.d
subeepoonntt random variables. By standard concentration inequality, we know for any <> O, with probability at least exp(- exp(=S((2m)),
(Tav(1)) - Frov(n) S
Proof of Lemma 41. Recall that
1 Frwv (1) P.p ESCD |w.. - -=112 0212
We only need to construct an e-net for pTT E ||wi,n - w² Let & be the event that
vd/ VL. S (Ximan)))) S VLd and 1/L S (HHrain) S L for all E [m] and vdaa ///4/4 [ S
do We have
EP-TEsCD |uct,1 w=1
1 =EP-T
ESGD
||
w" 11 E Pr[E] EPAT EsGD l|we. 111 & Pr(E]
2
According to Lemma 39, we know conditioning on E,
ESGD ||We.n - w=1 ESGD 1| - w w/1
as long as 7) S ogd (d/e) Note fuh,,)) is the SGD sequence without truncation. For the second term, we have
EPaT EscD Ww - - Pr[E] & 13Lo Pr(E] S c,
where the last inequality assumes Pr[E] S T3Laz. According to Lemma and Lemma 45, know Pr[E] < exp(-S(d)). Therefore, given any O, we have Pr[g] I 1si.= as long as 2 c4 log(1/c) (1/c) for some constant C4.
Then, we only need to construct an e-net for EP-T in Lemma 33, it's not hard to prove
FSGD |wC,, w=1 Pr(E]. By the analysis
i E P
EseD |[w wt 11 Pr[E7 0(1)t(1 7 y-1
On
2L
for all 17 E [0, esd log" (dfe)l- Similar as in Lemma 14, for any c > 0, we know there exists an c-net N. with size O(1/c) such that for any 1) E [0, ezd (d/e))
ESGD || - w² w01 11- Pr[E] - EP-T 2 EsGD || ||
1011 Pr[E] s
E EP&T
for v/ E arg mingeN. |n7 1/'-
Combing with the bounds on
ESGD w 11 {8} ESCD |umt,, - w/ {E} and
EP-T
ESGD |wr,, w0 g aod
Pr[E], we have for any E [0, agd 1op
Frov(n) FreV (v') < 4e
64

---

Under review as a conference paper at ICLR 2021
for r/ arg N. 1/1-- We finish the proof by replacing 4e by c'.
Proof of Lemma 42. The proof is very similar as the proof Lemma 18. The only difference is that need first relate the SGD sequence with truncation to the SGD sequence without truncation and then bound the Lipschitzness on the SGD sequence without truncation (as we did in Lemma 41). We omit the details here.
E TOOLS
E. NORM OF RANDOM VECTORS
We use the following lemma bound the noise in least squares model.
Lemma 45 (Theorem 3.1.1 in Vershynin (2018)). Let X (X1, X2, .,) E R² be random vector with each entry independently sampled from N ((0, 1). Then
Pr[[[|=|||
vn
2 0 < eexp (xxx(-1//(3)
where C' is an absolute constant.
E.2 SINGULAR VALUES GAUSSIAN MATRICES
Given random Gaussian matrix, in expectation its smallest and largest singular value can be bounded follows.
Lemma 46 (Theorem 5.32 in Vershynin (2010)). Let A be an N matrix whose entries are independent standard normal random variables. Then
VN /n Es (A) S Esmax (A) S VN Vn
Lemma 47 shows lipchitz function over i..dd Gaussian variables concentrate well on its mean.
We use this lemma to argue for any fixed step size, the empirical meta objective concentrates on the population meta objective.
Lemma 47 (Proposition 5.34 in Vershynin (2010)). Let f be a real valued Lipschitz function on R" with Lipschitz constant K. Let X be the standard normal random vector in IR". Then for every t one has
Pr(f(X) Ef(X) exp(
2K²
The following lemma shows tall random Gaussian matrix is well-conditioned with high probability. The proof follows from Lemma 46 and Lemma 47. We use Lemma 48 to show the covariance matrix well conditioned in the least squares model.
matrix whose entries are independent standard normal random variables. Then for every 2 0 with probability at least 1 2 exp(-t? one has
Lemma 48 (Corollary 5.35 in Vershynin (2010)). Let be an
VN- Vn - - 8min (A) < 8max (A) S VN vn+t
E.3 JOUNSON-LLNDENSTRAUN LEMMA
We also use Johnson-Lindenstine Lemma in some of the lemmas. Johnson-Linddenstauss Lemma tells us the projection of fixed vector on random subspace concentrates well as long as subspace is reasonably large.
Lemma 49 (Johnson & Lindenstrauss (1984)). Let P be a projection in Rd onto random dimensional subspace uniformly distributed Gd, Let z E Rd be a fixed point and e > then with probability at least
(
(1 11
"1=
||||| | + d ||||
65

---

Under review as a conference paper at ICLR 2021
F EXPERIMENT DETAILS
We describe the detailed settings of our experiments in Section F.1 and give more experimental results in Section F.2.
F.1 EXPERIMENT SETTINGS
Optimizing step size for quadratic objective In this experiment, meta-train a learning rate for gradient descent on a fixed quadratic objective. Our goal is to show that the autograd mod- ule in popular deep learning softwares, such Tensorflow, can have numerical issues when using the log-transformed meta objective. Therefore, we first implement the meta-training process with Tensorflow to see the results. We then re-implement the meta-training using the hand-derived meta- gradient (see Eqn 3) to compare the result.
A general setring for both implementations is follows. The inner problem is fixed as a 20- dimensional quadratic objective as described in Section 3, and we use the -og-transformed meta objective for training. The positive semi-definite matrix /1 is generated by first sampling 20 20 matrix X with all entries drawn from the standard normal distribution and then setting H = -x"x. The initial point We drawn from standard normal as well. Note that we use the same quadratic problem (i.e., the same H and wp) throughout the meta-training. We do 1000 meta-training iter- ations, and collect results for different settings of the initial learning rate voo and the unroll length 1.
We first implement the meta-training code with Tensorflow. Our code adapted from Wichrowska et al. (2017)* 2. We use their global learning rate optimizer and specify the problem set to have only one quadratic objective instance. We implemented the quadratic objective class ourselves (the "MyQuadratic" class). We also turned off multiple advanced features in the original code, such as attention and second derivatives, by assigning their flags as false. This ensures that the experiments have exactly the same settings as described. The meta-training learning rate is set to be 0.001, which is of similar scale as our next experiment. We also try RMSProp as the meta optimizer, which alleviates some of the numerical issues as renormalizes the gradient, but our experiments show that even RMSProp is still much worse than our implementation.
We then implement the meta-training by hand to show the accurate training results that avoid nu- merical issues, Specifically, we compute the meta-gradient using Eq (3), where we also scaled the numerator and denominator as described in Claim 2 avoid numerical issues. We use the algorithm suggested in Theorem 4, except we choose the meta-step size be 1/(100/k) as the constants in Theorem 4 were not optimized.
Train-by-train vs. train-by-validdtte synthetic data In this experiment, we find the optimal learning rate 17" for least-squares problems trained in train-by-train and train-by-validatioon settings and then see how the learning rate works on new tasks.
Specifically, we generate 300 different 1000-dimensional least-squares tasks with noise defined in Section 4 for inner-training and then use the meta-objectives defined in Eq (1) and (2) to find the optimal learning rate. The inner-training number of steps is set as 40. We try different sample sizes and different noise levels for comparison. Subsequently, in order to test how the two 17* (for train- by-train and rrin-by-validation respectively) work, we use them on 10 test tasks (the same setting as the inner-training problem) and compute training and testing root mean squared error (RMSE).
Note that since we only need the final optimal 17" found under the two meta-objective settings (re- gardless of how we find it), we do not need to actually do the meta-training. Instead, we do grid search on the interval 11-6,17 11. which is divided log-linearly 25 candidate points. For both the train-by-train and train-by- valldaa-a settings, we average the meta-objectives over the 300 inner problems and see which 7) minimizes this averaged meta-objective.
Train-by-train train-by-validatioon MLP optimizer on MNIST To observe the trade-off between train-by-train and train-by-validatee in a broader and more realistic case, we also do ex-
TTheir open source code is available at https: //gi www.w./.o//eeeoooll.ccoo ow/nodel aetooddellseeeeeeeeeeeeeeeee s/tree/ master/researce haahhh/eareeee Learned i miz
66

---

Under review as a conference paper at ICLR 2021
periments to meta-train MLP optimizer in Metz et al. (2019) to solve the MNIST classification problem. We use part of their code to integrate with our code in the first experiment, and we use exactly the same default setting as theirs, which is summarized below.
The MLP optimizer is a trainable optimizer that works on each parameter separately. When doing inner-training, for each parameter, we first compute some statistics of that parameter (explained be- low), which are combined into a feature vector, and then feed that feature vector to a Muti-Layer Perceptron (MLP) with ReLU activations, which outputs two scalars, the update direction and mag- nitude, The update is computed as the direction times the exponential of the magnitude. The feature vector is 31 dimeinesiinnal, which includes gradient, parameter value, first-order moving averages (5-dim), second-orde moving averages (5-dim), normalized gradient (5-dim), reciprocal of square root second-order moving averages (5-dim) and a step embedding (9-dim). All moving averages are computed using. 5 different decay rates (0.5, 0.9, 0.99, 0.999, 0.9999), and the step embedding tanh distortion of the current number of steps divided by different scales (3, 10, 30, 100, 300, 1000, 3000, 10000, 300000). After expanding the 31 31-dimensional feature vector for each parameter, we also normalize the set of vectors fimension-wise across all the parameters to have mean 0 and standard deviation (except for the step embedding part). More details can be found in their original paper and original implementation.
The inner-training problem is defined using two-layer fully connected network (i.e., another "MLP") with ReL.U activations to solve the classic MNIST 10-class classification problem. We use very small network for computational efficiency, and the two layers have 100 and 20 neurons. We fix the cross-entropy loss as the inner-objective and use mini-batches of 32 samples when inner- training.
When we meta-train the MLP optimizer, we use exactly the same process as fixed in experiments by Wichrowska et al. (2017). We use 100 different inner problems by shuffling the 10 classes and also sampling a new subset of data if we do not use the complete MNIST data set. We run each of the problems with three inner-training trajectories starting with different initialization. Each inner- training trajectory is divided into a certain number of unrolled segments, where we compute the meta-objective and update the meta-optimizer after each segment. The number of unrolled segments in each trajectory is sampled from 10 + Exp(30), and the length of each segment is sampled from 50 + Exp( (100), where Exp(-) denotes the exponential distribution. Note that the meta-objective computed after each segment is defined as the average of all the onner-objectives (evaluated on the train/validatio set for
within that segment for a better convergence. We also do not need to log- transfomm the inner-objective this time because the cross entropy loss has log operator itself. The meta-training, i.e. training the parameters of the MI.P in the MI.P optimzier, is completed using a classic RMSProp optimizer with meta learning rate 0.01.
toy-train/trrin-bae
For each settings of sample sizes and noise levels, we train two MLP optimizer: one for train-by- train, and one for rrain-by-validation When we test the learned MLP optimizer, we use similar settings as the inner-training problem, and we run the trajectories longer for full convergence (4000 steps for small data sets; 40000 steps for the complete data set). We run independent tests and collect training accuracy and test accuracy for evaluation. The plots show the mean of the 5 tests. We have also tuned a SGD optimizer (with the same mini-batch size) by doing a grid-search of the learning rate as baseline.
F.2 ADDITIONAL RESULTS
Optimizing step size for quadratic objective We try experiments for the same settings of the initial 7/o and inner training length / for all of three implementations (our hand-derived GD version, Tensorflow GD version and the Tensorflow RMSProp version). We do 1000 meta- meta-training steps for all the experiments.
For both Tensorflow versions, we always see infinite meta-objectives if 1oo is large or t is large, whose meta- veeaa-gradient is usually treated as zero, so the training get stuck and never converge. Even for the case that both and t is small, it still has very large meta-objectives (the scale of few hundreds), and that is why we also try RMSProp, which should be more robust against the gradient scales. Our
Their code is available at https: / / //gggttig wtw.tth..b...m..eeeeeee www.googlleoooooooooooooooooocoo wwwearchhegoooo reeeerreeecchhh cree/master/task fi lea_lea learned_cpt
67

---

Under review as a conference paper at ICLR 2021
Table 1:
Whether the implementation converges for different i (fixed noo 0.1)
10
20
40
80
Ours
Tensorflow GD
X
Tensorflow RMSProp
X
X
Table 2: Whether the implementation converges for different no (fixed 40)
1
0.001
0.01
0.1
Ours
Tensorflow GD
Tensorflow RMSProp
hand-derived version, however, does not have the numerical issues and can always converge to the optimal 17". The detailed convergence is summarized in Tab and Tab 2. Note that the optimal 17" is usually around 0.03 under our settings.
Train-by-train train-by-validattion MLP optimizer MNIST We also do additional ex- periments on training an MLP optimizer on the MNIST classification problem. We first try using all samples under the 20% noised setting. The results perform well if we have large data set, but since there is also noise in the data, the train-by-train model still overfits and is slightly worse than the train-by-vale -validdinaiioioo model.
shown in Fig 8. The train-by- setting
SGD
0.85
TbT60000
Accuracy (trin))
Accuracy (lest)
T6A5000+10000
0.8
0.8
0.75
0.75
SG0
0.85
ToT60000
0.85
TOV50000-10000
0.6
1.5
3.5
0.5
1.5
2 Staps
2.5
Staps
x10
x10
Figure 8: Training and testing accuracy for different models (all samples, 20% noise)
We then try an intermediate sample size 12000. The results are shown in Fig 9 (no noise) and Fig 10 (20% noise). We can see that the theory predicts, as the amount of data increases (from 1000 samples to 12000 samples and then to 60000 samples) the gap between train-by-train and train-by- validation decreases. Also, when we condition on the same number samples, having additional label noise always makes train-by-train model much worse compared to trainby--validttion.
68

---

Under review as a conference paper at ICLR 2021
SGD
Accuracy (train)
0.95
Accurscy (leas)
0.95
TDV80C0+4000
0.9
0.9
0.85
0.8
0.8
0.5
1.5
2 Steps
2.5
3.5
0.5
1.5
2
2.5
3.5
10
Steps
x10
Figure 9: Training and testing accuracy for different models (12000 samples, no noise)
SGD
TbT12000
0.9
0.9
TBM8802-4000
Accuracy (test)
0.7
0.7
830
TbT12000
TD48000+4000
0.5
0.5
0.5
1.5
2
2.5
3.5
0.5
1.5
2.5
3
3.5
Steps
x10
Steps
x10
Figure 10: Training and testing accuracy for different models (12000 samples, 20% noise)
69


Reviews:
[{"review_id": "nVEwoj7HeVx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents novel theoretical results on learning a step size for vanilla GD and SGD by unrolling the optimization steps and back-propagating, taking into account the simple problem minimizing quadratic functions and mean-square errors. The authors could demonstrate the occurrence of already-detected phenomena for learned optimizers, such as gradient explosion/vanishing and over-fitting, in the particular studied case. A few experiments illustrate what the developed theory predicts. \n\nTo the best of my knowledge, the literature lacks theoretical guarantees for learned optimizers and results as those within this manuscript can shed light on new ways to develop a solid learned optimizer theory. \n\nTheorems 1 and 2, seem central to motivate the work. Yet, they are very imprecise.\n\nIn Theorem 1:\n\n\"For tuning the step size of gradient descent on a quadratic objective, if the meta-objective is the\nloss of the last iteration, then the meta-gradient can explode/vanish.\"\n\nComment: Can is a loose expression — since it is a theorem, can it be shown that there are situations where they actually explode/ vanish? I believe this is discussed in Section 3, then why not state clearly that in the case of quadratics, the gradient vanishes?\n\nIn Theorem 2:\n\n\"For a simple least squares problem in d dimensions, if the number of samples n is a constant fraction of d (e.g., d/2), and the samples have large noise, then the train-by-train approach performs much worse than train-by-validation\"\n\nComment: what is much worse? How is this shown?\n\n\"On the other hand, when number of samples n is large, train-by-train can get close to error dσ2/\nn, which is optimal.\"\n\nComment: what is optimal?\"\n\n\nSection 3: After Equation (2), \"We first show that when the number of samples is small (in particular n < d) and the\nnoise is a large enough constant, train-by-train can be much worse than train-by-validation\"\n\nComment: Too many imprecise terms.\n\nUntil Section 3, the discussion emphasizes the use of logarithm for the meta-objective. But from section 4 onward, I see that the regular cost is used for the meta-objective. I am not sure if I am missing something here?\n\nFigure 2 is invoked to support ‘In Figure 2, we verify the observation from Metz et al. (2019) that the optimal step size depends on inner training length.’— While the trend shows difference with length, I was unsure if the difference is significant—a comparison of setting a constant step size would be more revealing.\n\nI also feel many of the proofs have not been properly explained in terms of the steps used in derivations, for example the various inequalities/upper bounds For Figures showing Training and Test RMSE, I would strongly recommend use of relative RMSE,\nthat is relative to the true value, expressed perhaps in dB plot. Currently it is very difficult to gauge the differences in terms of absolute RMSE.\n\nQuestion: What is the overall conclusion after the experiments?\n\nIs it that use of a logarithm helps remove vanishing gradient problem? From the experiments it seems the emphasis is that given data should be used with a separate validation data set.\n\nI do not think that the quadratic analysis necessarily makes it insignificant, since it does aid understanding. Nevertheless, I think its rather poorly written and structured and I was left trying to find out what is being emphasized. As a result, even this simple-case analysis seems unclear to me. The imprecise nature of the Theorems added more to the confusion.\n\n\nPros: \n- There are not many theoretical works on learned optimizers, thus this can be interesting to provide new insights.\n\n- The proofs seem to be correct and rely upon interesting mathematical properties, as far as I could follow.\n\nCons: \n\n- It seems to be hard to generalize the proposed analysis to more intricate (and practical) problems, such as training MLPs as optimizers. If this work intends to serve as a basis for further investigations, the authors should highlight which ideas could be still used in more general cases.\n\n- The results of Theorem 3 were partially discussed in Metz et al. (2019) (Sec. 2.3). The authors could acknowledge this fact in the text.\n\n- In Section 3, c_{min} is assumed to be positive, but what does it mean? Can w_0 be orthogonal to some eigenvector u_i of H?\n\n- There are many typos and colloquial statements are presented. Sentences as \"it is OK to use\", \"but didn’t give any\", should be avoided. Moreover there are 21 \"it's\" throughout the paper.\n\n- The statement \"Therefore in order to train neural networks, it is better to use train-by-validation.\" is too strong and was not proved.\n\n- Why is SGD noisier in Fig. 7 than the other methods? Are TbT and TbV calculating a full-batch gradient? This would not be a fair comparison if SGD had only access to an estimate of this gradient.\n\n\n\nMinor concerns:\n\n- What did the authors mean by \"constant fraction\" in Theorem 2? \n\n- I think the task definition should also depend on the initial condition w_0 as different initializations provide different trajectories.\n\n- The population losses were defined but not used in the text. Maybe it should be defined only in the appendix for clarity purposes.\n\n- What is the relevance of \"L > \\alpha\" to show that F(\\eta) is strictly convex in the proof of Theorem 3?\n\n- The constants in Theorem 5 and 6 are unused and could be omitted for the sake of concision. I recommend defining then in the proof only.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "cyIqI9IMTq", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Overview\n---\n\nMeta-gradient descent is an approach to step-size adaptation in which the step-size is adapted by considering how it influences the loss function over time. Intuitively, one can think of the trajectory of parameters $(w_s)_{s=1}^t$ as being a function of the step-size $\\eta$, and try to control the loss indirectly through the step-size's influence on the weight trajectory. This paper provides guarantees for this class of algorithms when applied to a quadradic loss function. It is shown that the meta-objective $\\ell_t(\\eta)=\\frac{1}{2}w_t(\\eta)^\\top H w_t(\\eta)$ contains no bad local solutions, but can suffer from vanishing/exploding gradients. It is then shown that this can be remedied simply considering the logarithm of this meta-objective, but that this too will have issues with numerical stability if approached with back-propagation. Finally, results related to the generalization ability of these methods are presented.\n\n**Overall, I recommend the paper for acceptance.** Despite focusing on a simple quadratic loss setting, the results are quite non-trivial and I believe will be of interest to many in the community. The writing was clear throughout, and I found the proofs that I worked through (Appendix A) to be instructive and of high-quality. The experiments leave a bit to be desired but I think are generally successful in demonstrating the results suggested by the theory.\n\nMy main reservation about this paper is the length of the Appendix. On one hand, I think it's absolutely unreasonable to expect reviewers to work through and verify **60** pages of proofs, for free, on their own time, given a two-week deadline, so I'm inclined to say that this work is better-suited for a journal where the results can be verified properly by reviewers. However, I did work through Appendix A, and the material was well-explained and generally quite excellent, so I'm willing to believe that the rest of the appendix follows suit. But because I don't have time to work through the remaining 50 pages, I can't be sure of the quality and this is reflected in my score, which might otherwise be higher.\n\n## Questions\n---\n- **Page 5**: *\"Note we truncate a sequence and declare the meta loss is high once the weight norm exceeds certain threshold. Specifically, if at the $\\tau^{\\text{th}}$ step, $\\|w_{\\tau,\\eta}\\|\\ge 40\\sigma$, we freeze the training on this task and set $w_{\\tau',\\eta}= 40\\sigma u$ for all $\\tau\\le \\tau'\\le t$, for some arbitrary vector $u$ with unit norm.\"* Why? Is there any specific justification for this, and how were these settings chosen?\n- **Page 6**: *\"Experiments show that in many settings (especially with large t and large $\\eta_0$) the implementation does not converge.\"* Where? Everything seems to be converging in the results shown in this section. Is this demonstrated elsewhere in the paper that I'm missing?\n- **Pages 7/8**: How many trials of these experiments were performed? Is there a reason why figures 5-7 don't include any measures of spread? Without some measure of spread it's hard to tell whether any of the differences are significant, which is problematic when these results are supposed to be verifying the theory presented.\n\n## Minor Comments (which did not affect my score)\n---\n- **Page 2**: *\"one needs to do the meta-training for an optimizer that runs for enough number of steps\"* this reads awkwardly.\n- **Page 2**: *\"Another challenge is about the generalization performance of the learned optimizer\"* This might read more clearly by rephrasing as \"The generalization performance of the learned optimizer is another challenge\"\n- **Page 13**: *\"where the second inequality holds\"* I think this is supposed to read equality rather than inequality.\n\n## Potentially Useful Citations\n---\nThe following citations investigate methods which adapt a *vector* of step-sizes, which might be of interest\n- **Incremental Delta-bar Delta (IDBD)**: Sutton, Richard S. \"Adapting bias by gradient descent: An incremental version of delta-bar-delta.\" AAAI. 1992.\n- **Stochastic Meta-descent (Generalization of IDBD)**: Schraudolph, Nicol N. \"Local gain adaptation in stochastic gradient descent.\" (1999): 569-574.\n- **TIDBD (IDBD for Reinforcement Learning algorithms)**:\n  Kearney, Alex, et al. \"Tidbd: Adapting temporal-difference step-sizes through stochastic meta-descent.\" arXiv preprint arXiv:1804.03334 (2018).\n  \n  Günther, Johannes, et al. \"Meta-learning for Predictive Knowledge Architectures: A Case Study Using TIDBD on a Sensor-rich Robotic Arm.\" Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. 2019.\n- **AdaGain (Meta-descent for learning stability)**: Jacobsen, Andrew, et al. \"Meta-descent for online, continual prediction.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YqUiMEr5eCI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors analyze two different approaches to \"learning to learn\" which correct various pathologies, however primarily restricted to the quadratic setting. The first is the use of the log objective rather than the raw objective for the inner-loop optimization step, and the second is the differences between train-by-train and train-by-validation. Overall, however, I feel that this work relies much too heavily on its supplemental material, as the proofs themselves are not well spelled out within the text itself, and at 68 pages total this is perhaps too extensive for this venue.\n\nThe authors give a reasonably good overview of recent approaches to to learning to learn, or meta-learning for optimizers. However, it is worth pointing out that they omit much of the early work in this area, particularly the work of Hochreiter et al., 2001 and the various citations therein, which give this area its name.\n\nNotationally, the work is also very dense. The authors might consider whether it is of value in introducing their approach whether to do away with the focus on supervised (e.g. input/output x/y data) models and instead focus on noisy gradients evaluated at each iteration. Otherwise it might be helpful to be more explicit about the indices x_i -> y_i when introducing these models, although this is perhaps a very nit-picky and aesthetic consideration.\n\nTheorem 3 is itself interesting, however it seems to follow quite directly from Section 2.3 of Metz et al. Although the authors do provide more detail, this is restricted to the quadratic inner-loop setting, whereas the description of Metz doesn't go so far due to the more general problem setting (and changing Hessians).\n\nTheorem 4, similarly is of interest. But it's not clear how much practical value it has. As far as I can tell the authors do not use this log objective when discussing the train-by-train/vs/train-by-validation setting. I may have misunderstood, but if this is not the case why not? Similarly, how does this compare empirically to the solution proposed by Metz et al? And lastly, the authors did not describe in detail how they dealt with the intermediate gradients which would have been most useful.\n\nFinally, the remaining theorems are interesting, but mostly seem to confirm the results of Metz at al, and are restricted to the quadratic setting. So more work might be needed to show why this is particularly of use.", "extra_scores": {}, "extra_text": {}}, {"review_id": "P93LCjaF30", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers algorithms that attempt to learn learning rates for gradient descent by gradient descent. Analysis is provided for a few specific quadratic losses showing that the gradient with respect to the learning rate may explode or vanish, and taking the logarithm is suggested to mitigate this. Further results suggest that implementing the gradient of the log comes with interesting numerical difficulties as *intermediate results* might explode or vanish even if the final answer does not.\n\nNext, linear regression problems are analyzed in both the over-determined and under-determined settings. It shown that in the under-determined setting the optimal learning rate when tuned on the training set is very far from the optimal learning rate when tuned on the validation set. \n\nExperiments are presented validating these theoretical findings, as well as comparisons to manual tuning on MNIST.\n\n\nI felt that the claims in the abstract were a bit overblown here. I would not say that there has been a characterization of when to use validation vs train set, or that the proposed logarithmic method necessarily avoids vanishing/exploding metagradients. Instead, these questions have been addressed in the very specific setting of linear regression.\n\nTheorems 5 and 6 appear to be making statements about the minimizers of the meta-objectives. Is there any guarantee that the meta-descent will efficiently approximate these minimizers so that the final algorithm actually comes with a guarantee?\n\nOverall, I was a bit underwhelmed by the linear regression setting. This setting seems a bit limited since it is almost possible to write in closed form what the sgd iterates will do. I am willing to concede that there is some significant difficulty here, or that this setting is somehow necessarily broadly relevant, but I don’t think it has been clearly discussed. As for the empirical comparison, MNIST is frankly also a kind of toy dataset at this point, and even in this setting it does not seem that any gain is to be had over simply tuning SGD via a logarithmic grid.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of learning the step size of gradient descent for quadratic loss. Interesting theoretical results are presented, which formally support the empirically observed problems of exploding/vanishing gradients, as well as another result showing that if meta-learning is done based on the validation performance, optimal performance can be achieved for a simple linear regression task.

On the negative side, there are several issues which preclude publication of the paper in its current stage:

1. The claims in the text seem to be much stronger than what is actually proved. 
2. The contributions are not properly connected to the literature (e.g., the relation to Metz et al. 2013 is not properly discussed).
3. Not mentioned in the reviews, but the paper does not explore the connection to similar results coming from online learning/sequential optimization. Recently there has been a surge of papers analyzing meta-learning from an online learning perspective; as an example,  Khodak et al. (2019) presents an adaptive step-size tuning with guarantees for a much more general problem setting. It could also be interesting to explore if the exploding gradient problem is also related to issues with mirror descent as described in Section 4.1 of Orabona and Pal (2018).
4. The presentation in the main text does not provide enough insight about the results, as too much material is relegated to the appendix.
5. The presentation is often imprecise; it is somewhat questionable (though it is a matter of taste) if the informal theorems are useful (why call them theorems?), but Corollary 1 is not indicated to be informal, yet it is hard to interpret formally. There are other issues such as the statements of Theorems 5 and 6 where conditional expectations are used without explicitly showing the conditions, high probability bounds are stated although the error probability never appears, etc.
6. It is not clear how meta-learning helps in Theorem 6 compared to methods adaptively tuning the step size (as a recent work, see, e.g., Joulani et al. 2020 and the references therein).



M. Khodak, M-F. Balcan, A. Talwalkar. Adaptive Gradient-Based Meta-Learning Methods. NeurIPS 2019.
F. Orabona, D. Pal. Scale-free online learning. Theoretical Computer Science 716, 50-69, 2018.
P. Joulani, A. Raj, A. Gyorgy, C. Szepesvari. A simpler approach to accelerated optimization: iterative averaging meets optimism. ICML 2020.


Decision: Reject