Year: 2020

Abstract:
Learning-to-learn—using optimization algorithms to learn a new optimizer—has successfully trained efficient optimizers in practice. This approach relies on metagradient descent on a meta-objective based on the trajectory that the optimizer generates. However, there were few theoretical guarantees on how to avoid metagradient explosion/vanishing problems, 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 metagradient remain 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.

text: Learning-to-learn—using optimization algorithms to learn a new optimizer—has successfully trained efficient optimizers in practice. This approach relies on metagradient descent on a meta-objective based on the trajectory that the optimizer generates. However, there were few theoretical guarantees on how to avoid metagradient explosion/vanishing problems, 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 metagradient remain 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.

heading: 1 INTRODUCTION
text: Choosing the right optimization algorithm and related hyper-parameters is important for training a deep neural network. Recently, a series of works (e.g., Andrychowicz et al. (2016); Wichrowska et al. (2017)) proposed to use learning algorithms to find a better optimizer. These papers use a learning-to-learn 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 metaparameters) 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 a metaobjective function based on the trajectory that the inner-optimizer generates, and then using backpropagation to compute the meta-gradient (Franceschi et al., 2017).
Although the learning-to-learn approach has shown empirical success, there are very few theoretical guarantees for learned optimizers. In particular, since the optimization for meta-parameters is usually a nonconvex problem, does it have bad local optimal solutions? Current ways of optimizing meta-parameters rely on unrolling the trajectory of the inner-optimizer, which is very expensive and often lead to exploding/vanishing gradient problems. Is there a way to alleviate these problems? Can we have a 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 learningto-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 can 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.

heading: 1.1 CHALLENGES OF LEARNING-TO-LEARN APPROACH AND OUR RESULTS
text: Metz et al. (2019) highlighted several challenges in the meta-optimization for learning-to-learn approach. 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 a 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 we apply the learned optimizer). However, when the number of steps is large, the meta-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 is a unique local and global minimizer for the step size, and we also give a simple way to get rid of the gradient explosion/vanishing problem.
Theorem 1 (Informal). For tuning the step size of gradient descent on a quadratic objective, if the meta-objective is the loss of the last iteration, then the meta-gradient can explode/vanish. If the meta-objective is the log of the loss of the last iteration, then the meta-gradient is polynomially bounded. Further, doing meta-gradient descent with a meta step size of 1/ √ k (where k is the number of meta-gradient steps) provably converges to the optimal step size for the inner-optimizer.
Surprisingly, even though taking the log of the objective solves the gradient explosion/vanishing problem, one cannot simply implement such an algorithm using auto-differentiation tools such as those used in TensorFlow (Abadi et 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 algorithm, 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 Theorem 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 trainby-train approach), then the learned optimizer might overfit. Metz et al. (2019) proposed to use a train-by-validation approach instead, where the meta-objective is defined to be the performance of the learned optimizer on a separate validation set.
Our second result considers a simple least squares setting where y = 〈w∗, x〉+ ξ and ξ ∼ N (0, σ2). We show that when the number of samples is small and the noise is large, it is important to use train-by-validation; while when the number of samples is much larger train-by-train can also learn a good optimizer.
Theorem 2 (Informal). 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. On the other hand, when number of samples n is large, train-by-train can get close to error dσ2/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.

heading: 1.2 RELATED WORK
text: 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 in 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 et al. (2017) used a 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.
Learning-to-learn 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 an RL algorithm by another meta-learning RL algorithm, and Duan et al. (2016) learned a general-purpose RNN that can adapt to different RL tasks.
Gradient-based meta-learning Finn et al. (2017) proposed Model-Agnostic Meta-Learning (MAML) where they parameterize the update rule for network parameters and learn a shared initialization for the optimizer using the tasks sampled from some distribution. Subsequent works generalized or improved MAML, e.g., Rusu et al. (2018) learned a low-dimensional latent representation 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 on 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 metaalgorithm selecting an algorithm from a family of parametrized algorithms. Gupta & Roughgarden (2017) first modeled the algorithm-selection process as a statistical learning problem and bounded the number of tasks it takes to tune a step size for gradient descent. However, they didn’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; 2018a;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-theoretically optimal bound in convex nonsmooth 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 can achieve near optimal rate for least squares regression. There are also a line of works that investigate methods which adapt a vector of step sizes (Sutton, 1992; Schraudolph, 1999; Kearney et al., 2018; Günther et al., 2019; Jacobsen et al., 2019).

heading: 2 PRELIMINARIES
text: In this section, we first introduce some notations, then formulate the learning-to-learn framework.

heading: 2.1 NOTATIONS
text: For any integer n, we use [n] to denote {1, 2, · · · , n}. We use ‖·‖ to denote the `2 norm for a vector and the spectral norm for a matrix. We use 〈·, ·〉 to denote the inner product of two vectors. For a symmetric matrix A ∈ Rd×d, we denote its eigenvalues as λ1(A) ≥ · · · ≥ λd(A). We denote the d-dimensional identity matrix as Id. We also denote the identity matrix simply as I when the dimension is clear from the context. We use O(·),Ω(·),Θ(·) to hide constant factor dependencies. We use poly(·) to represent a polynomial on the relevant parameters with constant degree. We say an event happens with high probability if it happens with probability 1− c for small constant c.

heading: 2.2 LEARNING-TO-LEARN FRAMEWORK
text: We consider the learning-to-learn approach applied to training a distribution of learning tasks. Each task is specified by a tuple (D, Strain, Svalid, `). Here D is a 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 Strain and Svalid 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 a parameter w ∈ W that minimizes the loss function `(w, x, y) : W × X × Y → R, which gives the loss of the parameter w for sample (x, y). The training loss for this task is f̂(w) := 1|Strain| ∑ (x,y)∈Strain `(w, x, y), while the population loss is f(w) := E(x,y)∼D[`(w, x, y)].
The goal of inner-optimization is to minimize the population loss f(w). For the learned optimizer, we consider it as an update rule u(·) on weight w. The update rule is a parameterized function that maps the weight at step τ and its history to the step τ + 1 : wτ+1 = u(wτ ,∇f̂(wτ ),∇f̂(wτ−1), · · · ; θ). In most parts of this paper, we consider the update rule u as gradient descent mapping with step size as the trainable parameter (here θ = η which is the step size for gradient descent). That is, uη(w) = w − η∇f̂(w) for gradient descent and uη(w) = w − η∇w`(w, x, y) for stochastic gradient descent where (x, y) is a sample randomly chosen from the training set Strain.
In the outer (meta) level, we consider a distribution T of tasks. For each task P ∼ T , we can define a meta-loss function ∆(θ, P ). The meta-loss function measures the performance of the optimizer on this learning task. The meta objective, for example, can be chosen as the target training loss f̂ at the last iteration (train-by-train), or the loss on the validation set (train-by-validation).
The training loss for the meta-level is the average of the meta-loss across m different specific tasks P1, P2, ..., Pm, that is, F̂ (θ) = 1m ∑m i=1 ∆(θ, Pk). The population loss for the meta-level is the expectation over all the possible specific tasks F (θ) = EP∼T [∆(θ, P )].
In order to train an optimizer by gradient descent, we need to compute the gradient of meta-objective F̂ in terms of meta parameters θ. The meta parameter is updated once after applying the optimizer on the inner objective t times to generate the trajectory w0, w1, ..., wt. The meta-gradient is then computed by unrolling the optimization process and back-propagating through the t applications of the optimizer. As we will see later, this unroll procedure is costly and can introduce meta-gradient explosion/vanishing problems.

heading: 3 ALLEVIATING GRADIENT EXPLOSION/VANISHING PROBLEMS
text: First we consider the meta-gradient explosion/vanishing problem. More precisely, we say the metagradient explodes/vanishes if it is exponentially large/small with respect to the number of steps t of the inner-optimizer.
In this section, we consider a very simple instance of the learning-to-learn approach, where the distribution T only contains a single task P , and the task also just defines a single loss function f 1. Therefore, in this section F̂ (η) = F (η) = ∆(η, P ). We will simplify notation and only use F̂ (η).
The inner task P is a simple quadratic problem, where the starting point is fixed at w0, and the loss function is f(w) = 12w
>Hw for some fixed positive definite matrix H . Without loss of generality, assume w0 has unit `2 norm. Suppose the eigenvalue decomposition of H is ∑d i=1 λiuiu > i . Throughout this section we assume L = λ1(H) and α = λd(H) are the largest and smallest eigenvalues of H with L > α. For each i ∈ [d], let ci be 〈w0, ui〉 and let cmin = min(|c1|, |cd|). We assume cmin > 0 for simplicity. Note that if w0 is uniformly sampled from the unit sphere, with high probability cmin is at least Ω(1/ √ d); if H is XX> with X ∈ Rd×2d as a random Gaussian matrix, with constant probability, both α and L− α are at least Ω(d). Let {wτ,η} be the GD sequence running on f(w) starting from w0 with step size η. 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 F̂ (η) = f(wt,η) does not have any bad local optimal solution, it has the gradient explosion/vanishing problem. We use F̂ ′(η) to denote the derivative of F̂ in η.
Theorem 3. Let the meta objective be F̂ (η) = f(wt,η) = 12w > t,ηHwt,η. We know F̂ (η) is a strictly convex function in η with an unique minimizer. However, for any step size η < 2/L, |F̂ ′(η)| ≤ t ∑d i=1 c 2 iλ 2 i |1− ηλi|2t−1; for any step size η > 2/L, |F̂ ′(η)| ≥ c21L2t(ηL− 1)2t−1 − L2t.
Note that in Theorem 3, when η < 2/L, |F̂ ′(η)| is exponentially small because |1 − ηλi| < 1 for all i ∈ [d]; when η > 2/L, |F̂ ′(η)| is exponentially large because ηL− 1 > 1. Intuitively, gradient
1In the notation of Section 2, one can think that D contains a single point (0, 0) and the loss function f(w) = `(w, 0, 0).
explosion/vanishing 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̂ (η) = 1t log f(wt,η), then we have
Theorem 4. Let the meta objective be F̂ (η) = 1t log f(wt,η). We know F̂ (η) has a unique minimizer η∗ and F̂ ′(η) = O ( L3
c2minα(L−α)
) for all η ≥ 0. Let {ηk} be the GD sequence running on F̂ with
meta step size µk = 1/ √ k. Suppose the starting step size η0 ≤ M. Given any 1/L > > 0, there exists k′ = M 6 2 poly( 1
cmin , L, 1α , 1 L−α ) such that for all k ≥ k ′, |ηk − η∗| ≤ .
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 a unique optimizer, the problem of optimizing η is still not convex because the meta-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 is bounded, it cannot be effectively computed by doing back-propagation due to numerical issues. More precisely:
Corollary 1. If we choose the meta-objective as F̂ (η) = 1t log f(wt,η), when computing the metagradient using back-propagation, there are intermediate results that are exponentially large/small in number of inner-steps t.
Indeed, in Section 5 we empirically verify that standard auto-differentiation tools can still fail in this setting. This suggests that one should be more careful about using standard back-propagation in the learning-to-learn approach. The proofs of the results in this section are deferred into Appendix A.

heading: 4 TRAIN-BY-TRAIN VS. TRAIN-BY-VALIDATION
text: Next we consider the generalization ability of simple optimizers. In this section we consider a simple family of least squares problems. Let T be a distribution of tasks where every task (D(w∗), Strain, Svalid, `) is determined by a parameter w∗ ∈ Rd which is chosen uniformly at random on the unit sphere. For each individual task, (x, y) ∼ D(w∗) is generated by first choosing x ∼ N (0, Id) and then computing y = 〈w∗, x〉 + ξ where ξ ∼ N (0, σ2) with σ ≥ 1. The loss function `(w, x, y) is just the squared loss `(w, x, y) = 12 (y − 〈w, x〉)
2. That is, the tasks are just standard least-squares problems with ground-truth equal to w∗ and noise level σ2.
For the meta-loss function, we consider two different settings. In the train-by-train setting, the training set Strain 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 (x1, y1), ..., (xn, yn) as the training set Strain. The meta-loss function ∆TbT (n)(η, P ) is defined to be
∆TbT (n)(η, P ) = 1
2n n∑ i=1 (yi − 〈wt,η, xi〉)2.
Here wt,η is the result of running t iterations of gradient descent starting from point 0 with step size η. Note we truncate a sequence and declare the meta loss is high once the weight norm exceeds certain threshold. We can safely do this because we assume the ground truth weight w∗ has unit 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 τ -th step, ‖wτ,η‖ ≥ 40σ,we freeze the training on this task and set wτ ′,η = 40σu for all τ ≤ τ ′ ≤ t, for some arbitrary vector u with unit norm. Setting the weight to a large vector is just one way to declare the loss is high; we choose this particular way for some proof convenience.
As before, the empirical meta objective in train-by-train setting is the average of the meta-loss across m different specific tasks P1, P2, ..., Pm, that is,
F̂TbT (n)(η) = 1
m m∑ k=1 ∆TbT (n)(η, Pk). (1)
In the train-by-validation setting, the specific tasks are generated by sampling n1 training samples and n2 validation samples for each task, and the meta-loss function is chosen to be the validation loss. That is, in each specific task P , we first choose w∗ uniformly at random, then generate (x1, y1), ..., (xn1 , yn1) as the training set Strain and (x ′ 1, y ′ 1), ..., (x ′ n2 , y ′ n2) as the validation set Svalid. The meta-loss function ∆TbV (n1,n2)(η, P ) is defined to be
∆TbV (n1,n2)(η, P ) = 1
2n2 n2∑ i=1 (y′i − 〈wt,η, x′i〉)2.
Here again wt,η is the result of running t iterations of the gradient descent on the training set starting from point 0, and we use the same truncation as before. The empirical meta objective is defined as
F̂TbV (n1,n2)(η) = 1
m m∑ k=1 ∆TbV (n1,n2)(η, Pk), (2)
where each Pk is independently sampled according to the described procedure.
We first show that when the number of samples is small (in particular n < d) and the noise is a large enough constant, train-by-train can be much worse than train-by-validation, even when n1 +n2 = n (the total number of samples used in train-by-validation is the same as train-by-train)
Theorem 5. Let F̂TbT (n)(η) and F̂TbV (n1,n2)(η) be as defined in Equation (1) and Equation (2) respectively. Assume n, n1, n2 ∈ [d/4, 3d/4]. Assume noise level σ is a large constant c1. Assume unroll length t ≥ c2, number of training tasks m ≥ c3 log(mt) and dimension d ≥ c4 log(mt) for certain constants c2, c3, c4. With high probability in the sampling of training tasks, we have
η∗train = Θ(1) and E ∥∥wt,η∗train − w∗∥∥2 = Ω(1)σ2,
for all η∗train ∈ arg minη≥0 F̂TbT (n)(η); η∗valid = Θ(1/t) and E ∥∥wt,η∗valid − w∗∥∥2 = ‖w∗‖2 − Ω(1)
for all η∗valid ∈ arg minη≥0 F̂TbV (n1,n2)(η). In both equations the expectation is taken over new tasks.
Note that in this case, the number of samples n is smaller than d, so the least square problem is underdetermined and the optimal training loss would go to 0 (there is always a way to simultaneously satisfy all n 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 0 will overfit to the noise and hurt the generalization performance. Train-by-validation on the other hand will choose a smaller learning rate which allows it to leverage the information in the training samples without overfitting to noise. Theorem 5 is proved in Appendix B. We also prove similar results for SGD in Appendix D
We emphasize that neural networks are often over-parameterized, which corresponds to the case when d > n. Indeed Liu & Belkin (2018) showed that variants of stochastic gradient descent can converge to the empirical risk minimizer with exponential rate in this case. Therefore in order to train neural networks, it is better to use train-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 F̂TbT (n)(η) be as defined in Equation 1. Assume noise level is a constant c1. Given any 1 > > 0, assume training set size n ≥ cd 2 log( nm d ), unroll length t ≥ c2 log( n d ), number of training tasks m ≥ c3n 2
4d2 log( tnm d ) and dimension d ≥ c4 for certain constants c, c2, c3, c4. With
high probability in the sampling of training tasks, we have
E ∥∥wt,η∗train − w∗∥∥2 ≤ (1 + )dσ2n ,
for all η∗train ∈ arg minη≥0 F̂TbT (n)(η), where the expectation is taken over new tasks.
Therefore if the learning-to-learn approach is applied to a traditional optimization problem that is not over-parameterized, train-by-train can work well. In this case, the empirical risk minimizer (ERM) already has good generalization performance, and train-by-train optimizes the convergence towards the ERM. We defer the proof of Theorem 6 into Appendix C.

heading: 5 EXPERIMENTS
text: 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 η0. 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/(100 √ k) as the constants in the theorem were not optimized.
An example training curve of η for t = 80 and η0 = 0.1 is shown in Figure 1, and we can see that η converges quickly within 300 steps. Similar convergence also holds for larger t or much larger initial η0. In contrast, we also implemented the meta-training with Tensorflow, where the code was adapted from the previous work of Wichrowska et al. (2017). Experiments show that in many settings (especially with large t and large η0) 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 et al. (2019) that the optimal step size depends on inner training length.
0 100 200 300
Meta steps
0
0.2
0.4
Ours Tensorflow
Figure 1: Training η (t = 80, η0 = 0.1) 0 50 100 150 200 Inner training length t
0.029
0.03
0.031
O p ti m
a l
*
Figure 2: Optimal η∗ for different t
Train-by-train vs. train-by-validation, synthetic data Here we validate our theoretical results in Section 4 using the least-squares model defined there. We fix the input dimension d to be 1000.
In the first experiment, we fix the size of the data (n = 500 for train-by-train, n1 = n2 = 250 for train-by-validation). Under different noise levels, we find the optimal η∗ by a grid search on its meta-objective for train-by-train and train-by-validation settings respectively. We then use the optimal η∗ found in each of these two settings to test on 10 new least-squares problem. The mean RMSE, as well as its range over the 10 test cases, are shown in Figure 3. We can see that for all of these cases, the train-by-train model overfits easily, while the train-by-validation model performs much better and does not overfit. Also, when the noise becomes larger, the difference between these two settings becomes more significant.
In the next experiment, we fix σ = 1 and change the sample size. For train-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 as we use more data, as expected by Theorem 6.
Train-by-train vs. train-by-validation, MLP optimizer on MNIST Finally we consider a 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 is the classic 10-class cross entropy loss, and we use mini-batches of 32 samples at inner training. In all the following experiments, we use SGD as 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 of label noise. For each optimizer, we run 5 independent tests and collect training accuracy and test accuracy for 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 are so close to each other, such that the range or standard deviation marks will not be readable in the plots.
First, consider optimizing the MNIST dataset with small number of samples. In this case, the trainby-train setting uses 1,000 samples (denoted as “TbT1000”), and we use another 1,000 samples as the validation set for the train-by-validation case (denoted as “TbV1000+1000”). To be fair to trainby-train we also consider TbT2000 where the train-by-train algorithm has access to 2000 data points. Figure 5 shows the results—all the models have training accuracy close to 1, but both TbT1000 and TbT2000 overfits the data significantly, whereas TbV1000+1000 performs well.
To show that when the noise is higher, the advantage of train-by-validation increases, we keep the same sample size and consider a “noisier” version of MNIST, where we randomly change the label of a 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 easily with training accuracy close to 1 and their test performances are low. The train-byvalidation model performs much better.
Finally we run experiments on the complete MNIST data set (without label noise). For the train-byvalidation 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 train-by-validation 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 train-by-validation.

heading: 6 CONCLUSION AND FUTURE WORKS
text: In this paper, we have proved optimization and generalization guarantees for tuning the step size for quadratic loss. From the optimization perspective, we considered a simple task whose objective is a 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 of samples is small and the noise is large, train-by-validation approach generalizes better than train-by-train; while when the number of samples is 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-trivial techniques to analyze. We have also verified our theoretical results on an optimizer parameterized by neural networks and MNIST dataset.
Since this is a very first work studying the learning to learn approach, there are many potential future works. One immediate future work is to extend the result for least squares to 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-gradient descent can converge to such an optimal step size. We believe our techniques for the 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.

heading: A PROOFS FOR SECTION 3 – ALLEVIATING GRADIENT EXPLOSION/VANISHING PROBLEM FOR QUADRATIC OBJECTIVE
text: In this section, we prove the results in Section 3. Recall the meta learning problem as follows:
The inner task is a fixed quadratic problem, where the starting point is fixed at w0, and the loss function is f(w) = 12w
>Hw for some fixed positive definite matrix H ∈ Rd×d. Suppose the eigenvalue decomposition of H is ∑d i=1 λiuiu > i . In this section, we assume L = λ1(H) and α = λd(H) are the largest and smallest eigenvalues of H with L > α. We assume the starting point w0 has unit `2 norm. For each i ∈ [d], let ci be 〈w0, ui〉 and let cmin = min(|c1|, |cd|). We assume cmin > 0 for simplicity, which is satisfied if w0 is chosen randomly from the unit sphere.
Let {wτ,η} be the GD sequence running on f(w) starting from w0 with step size η. For the metaobjective, 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̂ (η) = f(wt,η) does not have any bad local optimal solution, it has the gradient explosion/vanishing problem (Theorem 3). Then, in Section A.2, we show choosing F̂ (η) = 1t log f(wt,η) leads to polynomially bounded meta-gradient and further show meta-gradient descent converges to the optimal step size (Theorem 4). Although the metagradient is polynomially bounded, if we simply use back-propogation to compute the meta-gradient, the intermediate results can still be exponentially large/small (Corollary 1). This is also proved in Section A.2.

heading: A.1 META-GRADIENT VANISHING/EXPLOSION
text: In this section, we show although choosing F̂ (η) = f(wt,η) does not have any bad local optimal solution, it has the meta-gradient explosion/vanishing problem. Recall Theorem 3 as follows.
Theorem 3. Let the meta objective be F̂ (η) = f(wt,η) = 12w > t,ηHwt,η. We know F̂ (η) is a strictly convex function in η with an unique minimizer. However, for any step size η < 2/L, |F̂ ′(η)| ≤ t ∑d i=1 c 2 iλ 2 i |1− ηλi|2t−1; for any step size η > 2/L, |F̂ ′(η)| ≥ c21L2t(ηL− 1)2t−1 − L2t.
Intuitively, if we write wt,η in the basis of the eigen-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,η = wt−1,η − η∇f(wt−1,η) = wt−1,η − ηHwt−1,η = (I − ηH)wt−1,η = (I − ηH)tw0.
Therefore, F̂ (η) := f(wt,η) = 12w > 0 (I − ηH)2tHw0. Taking the derivative of F̂ (η),
F̂ ′(η) = −tw>0 (I − ηH)2t−1H2w0 = −t d∑ i=1 c2iλ 2 i (1− ηλi)2t−1,
where ci = 〈w0, ui〉 . Taking the second derivative of F (η),
F ′′(η) =t(2t− 1)w>0 (I − ηH)2t−2H3w0 = t(2t− 1) d∑ i=1 c2iλ 3 i (1− ηλi)2t−2.
Since L > α, we have F̂ ′′(η) > 0 for any η. That means F̂ (η) is a strictly convex function in η with a unique minimizer.
For any fixed η ∈ (0, 2/L) we know |1− ηλi| < 1 for all i ∈ [d]. We have∣∣∣F̂ ′(η)∣∣∣ ≤ t d∑ i=1 c2iλ 2 i |1− ηλi|2t−1.
For any fixed η ∈ (2/L,∞), we know ηL− 1 > 1. We have
F̂ ′(η) =− tc21L2(1− ηL)2t−1 − t ∑
i 6=1:(1−ηλi)≤0
c2iλ 2 i (1− ηλi)2t−1 − t ∑ i 6=1:(1−ηλi)>0 c2iλ 2 i (1− ηλi)2t−1
≥tc21L2(ηL− 1)2t−1 − t d∑ i=1 c2iλ 2 i ≥ tc21L2(ηL− 1)2t−1 − L2t,
where the last inequality uses ∑d i=1 c 2 i = 1.

heading: A.2 ALLEVIATING META-GRADIENT VANISHING/EXPLOSION
text: We prove when the the meta objective is chosen as 1t log f(wt,η), the meta-gradient is polynomially bounded. Furthermore, we show meta-gradient descent can converge to the optimal step size within polynomial iterations. Recall Theorem 4 as follows.
Theorem 4. Let the meta objective be F̂ (η) = 1t log f(wt,η). We know F̂ (η) has a unique minimizer η∗ and F̂ ′(η) = O ( L3
c2minα(L−α)
) for all η ≥ 0. Let {ηk} be the GD sequence running on F̂ with
meta step size µk = 1/ √ k. Suppose the starting step size η0 ≤ M. Given any 1/L > > 0, there exists k′ = M 6 2 poly( 1
cmin , L, 1α , 1 L−α ) such that for all k ≥ k ′, |ηk − η∗| ≤ .
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 on F̂ (η) – it has a unqiue minimizer and the gradient is polynomially bounded. Further the gradient is only close to 0 when the point η is close to the unique minimizer. Then using such structural result we prove that metagradient descent converges.
Proof of Theorem 4. The proof consists of three claims. In the first claim, we show that F̂ has a unique minimizer and the minus meta derivative always points to the minimizer. In the second claim, we show that F̂ has bounded derivative. In the last claim, we show that for any η that is outside the -neighborhood of η∗, |F̂ ′(η)| is lower bounded. Finally, we combine these three claims to finish the proof.
Claim 1. The meta objective F̂ has only one stationary point that is also its unique minimizer η∗. For any η ∈ [0, η∗), F̂ ′(η) < 0 and for any η ∈ (η∗,∞), F̂ ′(η) > 0. Furthermore, we know η∗ ∈ [1/L, 1/α].
We can compute the derivative of F̂ in η as follows,
F̂ ′(η) = −2w>0 (I − ηH)2t−1H2w0 w>0 (I − ηH)2tHw0 = −2 ∑d i=1 c 2 iλ 2 i (1− ηλi)2t−1∑d i=1 c 2 iλi(1− ηλi)2t . (3)
It’s not hard to verify that the denominator ∑d i=1 c 2 iλi(1 − ηλi)2t is always positive. Denote the
numerator −2 ∑d i=1 c 2 iλ 2 i (1− ηλi)2t−1 as g(η). Since g′(η) > 0 for any η ∈ [0,∞), we know g(η)
is strictly increasing in η. Combing with the fact that g(0) < 0 and g(∞) > 0, we know there is a unique point (denoted as η∗) where g(η∗) = 0 and g(η) < 0 for all η ∈ [0, η∗) and g(η) > 0 for all η ∈ (η∗,∞). Since the denominator in F̂ ′(η) is always positive and the numerator equals g(η), we know there is a unique point η∗ where F̂ ′(η∗) = 0 and F̂ ′(η) < 0 for all η ∈ [0, η∗) and F̂ ′(η) > 0 for all η ∈ (η∗,∞). It’s clear that η∗ is the minimizer of F̂ .
Also, it’s not hard to verify that for any η ∈ [0, 1/L), F̂ ′(η) < 0 and for any η ∈ (1/α,∞), F̂ ′(η) > 0. This implies that η∗ ∈ [1/L, 1/α]. Claim 2. For any η ∈ [0,∞), we have
|F̂ ′(η)| ≤ 4L 3
c2minα(L− α) := Dmax.
For any η ∈ [0, 2α+L ], we have |1−ηλi| ≤ 1−ηα for all i. Dividing the numerator and denominator in F̂ ′(η) by (1− ηα)2t, we have
∣∣∣F̂ ′(η)∣∣∣ = 2 ∣∣∣∑di=1 c2iλ2i1−ηα ( 1−ηλi1−ηα )2t−1∣∣∣ c2dα+ ∑d−1 i=1 c 2 iλi( 1−ηλi 1−ηα ) 2t ≤ 2 ∑d i=1 c 2 iλ 2 i c2dα(1− ηα) ≤ 2(α+ L) ∑d i=1 c 2 iλ 2 i c2dα(L− α) ≤ 4L 3 c2dα(L− α) ,
where the second last inequality uses η ≤ 2α+L .
Similarly for any η ∈ ( 2α+L ,∞), we have |1− ηλi| ≤ ηL− 1 for all i. Dividing the numerator and denominator in F̂ ′(η) by (ηL− 1)2t, we have
F̂ ′(η) = 2 ∣∣∣∑di=1 c2iλ2iηL−1 ( 1−ηλiηL−1 )2t−1∣∣∣ c21L+ ∑d i=2 c 2 iλi( 1−ηλi ηL−1 ) 2t ≤ 2 ∑d i=1 c 2 iλ 2 i c21L(ηL− 1) ≤ 2(α+ L) ∑d i=1 c 2 iλ 2 i c21L(L− α) ≤ 4L 3 c21L(L− α)
where the last inequality uses η ≥ 2α+L .
Overall, we know for any η ≥ 0,
|F̂ ′(η)| ≤ 4L 3
L− α max
( 1
c2dα ,
1
c21L
) ≤ 4L 3
c2minα(L− α) .
Claim 3. Given M̂ ≥ 2/α and 1/L > > 0, for any η ∈ [0, η∗ − ] ∪ [η∗ + , M̂ ], we have
|F ′(η)| ≥ min
( 2 c2dα 3
L ,
2 c21L 2
(M̂L− 1)2
) ≥ 2 c2min min ( α3
L ,
1
M̂2
) := Dmin(M̂).
If η ∈ [0, η∗ − ] and η ≤ 2α+L , we have
F̂ ′(η) = −2 ∑d i=1 c 2 iλ 2 i (1− ηλi)2t−1∑d
i=1 c 2 iλi(1− ηλi)2t
= −2 ∑d i=1 c 2 iλ 2 i (1− ηλi)2t−1 − ∑d i=1 c 2 iλ 2 i (1− η∗λi)2t−1∑d
i=1 c 2 iλi(1− ηλi)2t
,
where the second equality holds because ∑d i=1 c 2 iλ 2 i (1 − η∗λi)2t−1 = 0. For the numerator, we have d∑ i=1 c2iλ 2 i (1− ηλi)2t−1 − d∑ i=1 c2iλ 2 i (1− η∗λi)2t−1 ≥c2dα2 ( (1− ηα)2t−1 − (1− η∗α)2t−1
) ≥c2dα2 ( (1− ηα)2t−1 − (1− ηα− α)2t−1 ) ;
for the denominator, we have
d∑ i=1 c2iλi(1− ηλi)2t ≤ ( d∑ i=1 c2iλi ) (1− ηα)2t,
where the second inequality holds because |1 − ηλi| ≤ 1 − ηα for all i. Overall, we have when η ∈ [0, η∗ − ] and η ≤ 2α+L ,∣∣∣F̂ ′(η)∣∣∣ ≥2c2dα2 ((1− ηα)2t−1 − (1− ηα− α)2t−1)(∑d
i=1 c 2 iλi
) (1− ηα)2t
≥ 2 c 2 dα 3(∑d i=1 c 2 iλi ) (1− ηα) ≥ 2 c 2 dα 3 L ,
where the last inequality holds because (1− ηα) ≤ 1 and ∑d i c 2 iλi ≤ L.
Similarly, if η ∈ [0, η∗ − ] and η ≥ 2α+L , we have∣∣∣F̂ ′(η)∣∣∣ ≥2c21L2 ((1− ηL)2t−1 − (1− ηL− L)2t−1)(∑d i=1 c 2 iλi ) (1− ηL)2t
=2 c21L
2 ( (ηL+ L− 1)2t−1 − (ηL− 1)2t−1 )(∑d i=1 c 2 iλi ) (ηL− 1)2t
≥ 2 c 2 1L 3(∑d i=1 c 2 iλi ) (ηL− 1)2 ≥ 2 c 2 1α 2L2 (L− α)2 ,
where the last inequality holds because η ≤ η∗ − ≤ 1/α and ∑d i c 2 iλi ≤ L.
If η ∈ [η∗ + ,∞) and η ≤ 2α+L , we have∣∣∣F̂ ′(η)∣∣∣ ≥2c2dα2 ((1− ηα+ α)2t−1 − (1− ηα)2t−1)(∑d i=1 c 2 iλi ) (1− ηα)2t
≥2 c 2 dα 3
L ,
If η ∈ [η∗ + ,∞) and η ≥ 2α+L , we have∣∣∣F̂ ′(η)∣∣∣ ≥2c21L2 ((1− ηL+ η )2t−1 − (1− ηL)2t−1)(∑d i=1 c 2 iλi ) (1− ηL)2t
≥ 2 c 2 1L 3(∑d i=1 c 2 iλi ) (ηL− 1)2 ≥ 2 c 2 1L 2 (M̂L− 1)2 ,
where the last inequality uses the assumption that η ≤ M̂. With the above three claims, we are ready to prove the optimization result. By Claim 1, we know F ′(η) < 0 for any η ∈ [0, η∗) and F ′(η) > 0 for any η ∈ (η∗,∞). So the opposite gradient descent always points to the minimizer. Since µk = 1/ √ k, when k ≥ k1 := D 2 max 2 we know µk ≤
Dmax . By Claim 2, we know |F̂ ′(η)| ≤
Dmax for all η ≥ 0, which implies |µkF̂ ′(η)| ≤ for all k ≥ k1. That means, meta gradient descent will never overshoot the minimizer by more than when k ≥ k1. In other words, after k1 meta iterations, once η enters the -neighborhood of η∗, it will never leave this neighborhood.
We also know that at meta iteration k1, we have ηk1 ≤ max(1/α + Dmax,M) := M̂. Here, 1/α+Dmax comes from the case that the eta starts from the left of η∗ and overshoot to the right of η∗ by Dmax. Since η∗ ∈ [1/L, 1/α], we have |ηk1 − η∗| ≤ max(1/α, 1/α + Dmax − 1/L,M − 1/L) := R. By Claim 3, we know that |F̂ ′(η)| ≥ Dmin(M̂) for any η ∈ [0, η∗ − ] ∪ [η∗ + , M̂ ]. Choosing some k2 satisfying ∑k2 k=k1 1/ √ k ≥ RDmin , we know for any k ≥ k2, |ηk − η ∗| ≤ .
Plugging in all the bounds for Dmin, Dmax from Claim 3 and Claim 2, we know there exists k1 = 1 2 poly(
1 cmin , L, 1α , 1 L−α ), k2 = M6 2 poly( 1 cmin , L, 1α , 1 L−α ) satisfying these conditions.
Next, we show although the meta-gradient is polynomailly bounded, the intermediate results can still vanish or explode if we use back-propogation to compute the meta-gradient.
Corollary 1. If we choose the meta-objective as F̂ (η) = 1t log f(wt,η), when computing the metagradient using back-propagation, there are intermediate results that are exponentially large/small in number of inner-steps t.
Proof of Corollary 1. This is done by direct calculation. If we use back-propagation to compute the derivative of 1t log(f(wt,η)), we need to first compute ∂f(wt,η) ∂ 1 t log(f(wt,η)) that equals 1 tf(wt,η)
. Same as the analysis in Theorem 3, we can show 1tf(wt,η) is exponentially large when η < 2/L and is exponentially small when η > 2/L.

heading: B PROOFS OF TRAIN-BY-TRAIN V.S. TRAIN-BY-VALIDATION (GD)
text: In this section, we show when the number of samples is small and when the noise level is 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 5 is simply a combination of Theorem 7 and Theorem 8.
Recall that in the train-by-train setting, each task P contains a training set Strain with n samples. The inner objective is defined as f̂(w) = 12n ∑ (x,y)∈Strain (〈w, x〉 − y) 2 . Let {wτ,η} be the GD sequence running on f̂(w) from initialization 0 (with truncation). The meta-loss on task P is defined as the inner objective of the last point, ∆TbT (n)(η, P ) = f̂(wt,η) = 12n ∑ (x,y)∈Strain (〈wt,η, x〉 − y) 2 . The empirical meta objective F̂TbT (n)(η) is the average of the meta-loss across m different tasks. We show that under F̂TbT (n)(η), the optimal step size is a constant and the learned weight is far from ground truth w∗ on new tasks. We prove Theorem 7 in Section B.2.
Theorem 7. Let the meta objective F̂TbT (n)(η) be as defined in Equation 1 with n ∈ [d/4, 3d/4]. Assume noise level σ is a large constant c1. Assume unroll length t ≥ c2, number of training tasks m ≥ c3 log(mt) and dimension d ≥ c4 log(m) for certain constants c2, c3, c4. With probability at least 0.99 in the sampling of the training tasks, we have
η∗train = Θ(1) and E ∥∥wt,η∗train − w∗∥∥2 = Ω(1)σ2,
for all η∗train ∈ arg minη≥0 F̂TbT (n)(η), where the expectation is taken over new tasks.
In Theorem 7, Ω(1) is an absolute constant independent with σ. Intuitively, the reason that train-bytrain performs badly in this setting is because there is a way to set the step size to a constant such that gradient descent converges very quickly to the empirical risk minimizer, therefore making the train-by-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 train-by-validation setting, each task P contains a training set Strain with n1 samples and a validation set with n2 samples. The inner objective is defined as f̂(w) =
1 2n1 ∑ (x,y)∈Strain (〈w, x〉 − y) 2 . Let {wτ,η} be the GD sequence running on f̂(w) from initialization 0 (with truncation). For each task P , the meta-loss ∆TbV (n1,n2)(η, P ) is defined as the loss of the last point wt,η evaluated on the validation set Svalid. That is, ∆TbV (n1,n2)(η, P ) =
1 2n2 ∑ (x,y)∈Svalid (〈wt,η, x〉 − y) 2 . The empirical meta objective F̂TbV (n1,n2)(η) is the average of the meta-loss across m different tasks P1, P2, ..., Pm. We show that under F̂TbV (n1,n2)(η), the optimal step size is Θ(1/t) and the learned weight is better than initialization 0 by a constant on new tasks. Theorem 8 is proved in Section B.3.
Theorem 8. Let the meta objective F̂TbV (n1,n2)(η) be as defined in Equation 2 with n1, n2 ∈ [d/4, 3d/4]. Assume noise level σ is a large constant c1. Assume unroll length t ≥ c2, number of
training tasks m ≥ c3 and dimension d ≥ c4 log(t) for certain constants c2, c3, c4. With probability at least 0.99 in the sampling of training tasks, we have
η∗valid = Θ(1/t) and E ∥∥wt,η∗valid − w∗∥∥2 = ‖w∗‖2 − Ω(1)
for all η∗valid ∈ arg minη≥0 F̂TbV (n1,n2)(η), where the expectation is taken over new tasks.
Intuitively, train-by-validation is optimizing the right objective. As long as the meta-training problem has good generalization performance (that is, good performance on a few tasks implies good performance on the distribution of tasks), then train-by-validation should be able to choose the optimal learning rate. The step size of Θ(1/t) here serves as regularization similar to early-stopping, which allows gradient descent algorithm to achieve better error on test data.
Notations We define more quantities that are useful in the analysis. In the train by train setting, given a task Pk := (D(w∗k), S (k) train, `). The training set S (k) train contains n samples {x (k) i , y (k) i }ni=1 with y (k) i = 〈 w∗k, x (k) i 〉 + ξ (k) i .
Let X(k)train be an n × d matrix with its i-th row as (x (k) i ) >. Let H(k)train := 1 n (X (k) train) >X (k) train be the covariance matrix of the inputs in S(k)train. Let ξ (k) train be an n-dimensional column vector with its i-th entry equal to ξ(k)i .
Since n ≤ d, with probability 1, we know X(k)train is full row rank. Therefore, X (k) train has pseudoinverse (X(k)train) † such that X(k)train(X (k) train) † = In. It’s not hard to verify that there exists w (k) train =
Proj (X (k) train ) >w ∗ k + (X (k) train) †ξ (k) train such that y (k) i =
〈 w
(k) train, x (k) i 〉 for every (x(k)i , y (k) i ) ∈ S (k) train.
Here, Proj (X (k) train ) > is the projection matrix onto the column span of (X
(k) train) >. We also denote
Proj (X (k) train ) >w ∗ k as (w (k) train) ∗. We use B(k)t,η to denote (I − (I − ηH (k) train) t). Let w(k)t,η be the weight obtained by running GD on S(k)train with step size η (with truncation).
With the above notations, it’s not hard to verify that for task Pk, the inner objective f̂(w) = 1 2 ∥∥∥w − w(k)train∥∥∥2 H
(k) train
. The meta-loss on task Pk is just ∆TbT (n)(η, Pk) = 12 ∥∥∥wt,η − w(k)train∥∥∥2
H (k) train
.
In the train-by-validation setting, each task Pk contains a training set S (k) train with n1 samples and a validation set S(k)valid with n2 samples. Similar as above, for the training set S (k) train, we can define ξ(k)train, X (k) train, H (k) train, w (k) train, B (k) t,η , w (k) t,η ; for the validation set S (k) valid, we can define
ξ (k) valid, X (k) valid, H (k) valid, w (k) valid. With these notations, the inner objective is f̂(w) = 1 2 ∥∥∥w − w(k)train∥∥∥2 H
(k) train
and the meta-loss is ∆TbV (n1,n2)(η, Pk) = 1 2 ∥∥∥wt,η − w(k)valid∥∥∥2 H
(k) valid
.
We also use these notations without index k to refer to the quantities defined on task P. In the proofs, we ignore the subsripts on n, n1, n2 and simply write ∆TbT (η, Pk),∆TbV (η, Pk), F̂TbT , F̂TbV , FTbT , FTbV .

heading: B.1 OVERALL PROOF STRATEGY
text: In this section (and the next), we follow similar proof strategies that consists of three steps.
Step 1: First, we show for both train-by-train and train-by-validation, there is a 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 is exactly the good step size that we propose, but it gives an upperbound on the empirical meta-objective for the optimal step size.
Step 2: Second, we define a 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 3: Third, we show the meta-learning problem has good generalization performance, that is, if a learning rate η performs well on the training tasks, it must also perform well on the task distribution, and vice versa. Thanks to Step 1 and Step 2, we 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 as we only have a single trainable parameter η, however we also emphasize that this is non-trivial as we will not restrict the step size η to be small enough that the algorithms do not diverge. Instead we use a truncation to alleviate the diverging problem (this allows us to run the algorithm on distribution of data whose largest possible learning rate is unknown).
Combing Step 1, 2, 3, we know the population meta-objective has to be small at 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 5. The last step is easier for the train-by-validation setting, because its meta-objective is exactly the correct measure that we are looking at; for the trainby-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.

heading: B.2 TRAIN-BY-TRAIN (GD)
text: Recall Theorem 7 as follows.
Theorem 7. Let the meta objective F̂TbT (n)(η) be as defined in Equation 1 with n ∈ [d/4, 3d/4]. Assume noise level σ is a large constant c1. Assume unroll length t ≥ c2, number of training tasks m ≥ c3 log(mt) and dimension d ≥ c4 log(m) for certain constants c2, c3, c4. With probability at least 0.99 in the sampling of the training tasks, we have
η∗train = Θ(1) and E ∥∥wt,η∗train − w∗∥∥2 = Ω(1)σ2,
for all η∗train ∈ arg minη≥0 F̂TbT (n)(η), where the expectation is taken over new tasks.
According to the data distribution, we know Xtrain is an n × d random matrix with each entry i.i.d. sampled from standard Gaussian distribution. In the following lemma, we show that the covariance matrix Htrain is approximately isotropic when d/4 ≤ n ≤ 3d/4. Specifically, we show√ d√ L ≤ σi(Xtrain) ≤ √ Ld and 1L ≤ λi(Htrain) ≤ L for all i ∈ [n] with L = 100. We use letter L to denote the upper bound of ‖Htrain‖ to emphasize that this bounds the smoothness of the inner objective. Throughout this section, we use letter L to denote constant 100. The proof of Lemma 1 follows from random matrix theory. We defer its proof into Section B.2.4.
Lemma 1. Let X ∈ Rn×d be a random matrix with each entry i.i.d. sampled from standard Gaussian distribution. Let H := 1/nX>X. Assume n = cd with c ∈ [ 14 , 3 4 ]. Then, with probability at least 1− exp(−Ω(d)), there exists constant L = 100 such that √ d√ L ≤ σi(X) ≤ √ Ld and 1 L ≤ λi(H) ≤ L,
for all i ∈ [n].
In this section, we always assume the size of each training set is within [d/4, 3d/4] so Lemma 1 holds. Since ‖Htrain‖ is upper bounded by L with high probability, we know the GD sequence converges to wtrain for η ∈ [0, 1/L]. In Lemma 2, we prove that the empirical meta objective F̂TbT monotonically decreases as η increases until 1/L. Also, we show F̂TbT is exponentially small in t 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 at least 1 −m exp(−Ω(d)), F̂TbT (η) is monotonically decreasing in [0, 1/L] and
F̂TbT (1/L) ≤ 2L2σ2 (
1− 1 L2
)t .
When the step size is larger than 1/L, the GD sequence can diverge, which incurs a high loss in meta objective. Later in 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 η̃. In Lemma 3, we show with high probability, the empirical meta objective is high for all η > η̃. This serves as step 2 in the proof strategy described in Section B.1. The proof is deferred into Section B.2.2. Lemma 3. With probability at least 1− exp(−Ω(m)),
F̂TbT (η) ≥ σ2
10L8 ,
for all η > η̃.
By Lemma 2 and Lemma 3, we know the optimal step size must lie in [1/L, η̃]. We can also show 1/L < η̃ < 3L, so η∗train is a constant. To relate the empirical loss at η ∗ train to the population loss. We prove a generalization result for step sizes within [1/L, η̃]. This serves as step 3 in Section B.1. The proof is deferred into Section B.2.3. Lemma 4. Suppose σ is a large constant c1. Assume t ≥ c2, d ≥ c4 for certain constants c2, c4. With probability at least 1−m exp(−Ω(d))−O(t+m) exp(−Ω(m)),
|FTbT (η)− F̂TbT (η)| ≤ σ2
L3 ,
for all η ∈ [1/L, η̃],
Combining the above lemmas, we know the population meta objective FTbT is small at η∗train, which means wt,η∗train is close to the ERM solution. Since the ERM solution overfits to the noise in training tasks, we know ∥∥wt,η∗train − w∗∥∥ has to be large. We present the proof of Theorem 7 as follows. Proof of Theorem 7. We assume σ is a large constant in this proof. According to Lemma 2, we know with probability at least 1−m exp(−Ω(d)), F̂TbT (η) is monotonically decreasing in [0, 1/L] and F̂TbT (1/L) ≤ 2L2σ2(1 − 1/L2)t. This implies that the optimal step size η∗train ≥ 1/L and F̂TbT (η ∗ train) ≤ 2L2σ2(1−1/L2)t.By Lemma 3, we know with probability at least 1−exp(−Ω(m)), F̂TbT (η) ≥ σ 2
10L8 for all η > η̃, where η̃ is defined in Definition 1. As long as t ≥ c2 for certain constant c2, we know σ 2 10L8 > 2L 2σ2(1−1/L2)t, which then implies that the optimal step size η∗train lies in [1/L, η̃]. According to Lemma 6, we know η̃ ∈ (1/L, 3L). Therefore η∗train is a constant. According to Lemma 4, we know with probability at least 1 − m exp(−Ω(d)) − O(t + m) exp(−Ω(m)), |FTbT (η) − F̂TbT (η)| ≤ σ 2
L3 , for all η ∈ [1/L, η̃]. As long as t is larger than some constant, we have F̂TbT (η∗train) ≤ σ 2
L3 . Combing with the generalization result, we have FTbT (η ∗ train) ≤ 2σ 2 L3 . Next, we show that under a small population loss, E ∥∥wt,η∗train − w∗∥∥2 has to be large. Let E1 be the event that √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and√
dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. We have
E ∥∥wt,η∗train − wtrain∥∥2Htrain ≥ 1LE∥∥wt,η∗train − wtrain∥∥2 1 {E1}
≥ 1 L ( E ∥∥wt,η∗train − w∗train − (Xtrain)†ξtrain∥∥1 {E1})2 ≥ 1 L ( E ∥∥(Xtrain)†ξtrain∥∥1 {E1} − E ∥∥wt,η∗train − w∗train∥∥1 {E1})2 .
Since E ∥∥wt,η∗train − wtrain∥∥2Htrain ≤ 4σ2L3 , this then implies
E ∥∥(Xtrain)†ξtrain∥∥1 {E1} − E∥∥wt,η∗train − w∗train∥∥1 {E1} ≤ √ L 4σ2
L3 =
2σ
L . Conditioning on E1, we can lower bound ∥∥(Xtrain)†ξtrain∥∥ by σ4√L . According to Lemma 1 and Lemma 45, we know Pr[E1] ≥ 1 − exp(−Ω(d)). As long as d is at least certain constant, we have
Pr[E1] ≥ 0.9. This then implies E ∥∥(Xtrain)†ξtrain∥∥1 {E1} ≥ 9σ40√L . Therefore, we have
E ∥∥wt,η∗train − w∗train∥∥1 {E1} ≥ 9σ40√L − 2σL = 9σ4L − 2σL = σ4L,
where the first equality uses L = 100. Then, we have
E ∥∥wt,η∗train − w∗∥∥2 ≥ E∥∥wt,η∗train − w∗train∥∥2 1 {E1} ≥ (E ∥∥wt,η∗train − w∗train∥∥1 {E1})2 ≥ σ216L2 ,
where the first inequality holds because for any Strain, w∗train is the projection of w ∗ on the subspace of Strain and wt,η∗train is also in this subspace. Taking a union bound for all the bad events, we know this result holds with probability at least 0.99 as long as σ is a large constant c1 and t ≥ c2,m ≥ c3 log(mt) and d ≥ c4 log(m) for certain constants c2, c3, c4.
B.2.1 BEHAVIOR OF F̂TbT FOR η ∈ [0, 1/L]
In this section, we prove the empirical meta objective F̂TbT is monotonically decreasing in [0, 1/L]. Furthermore, we show F̂TbT (1/L) is exponentially small in t.
Lemma 2. With probability at least 1 −m exp(−Ω(d)), F̂TbT (η) is monotonically decreasing in [0, 1/L] and
F̂TbT (1/L) ≤ 2L2σ2 (
1− 1 L2
)t .
Proof of Lemma 2. For each k ∈ [m], let Ek be the event that √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and
1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. Here, L is constant 100 from Lemma 1. According to Lemma 1 and Lemma 45, we know for each k ∈ [m], Ek happens with probability at least 1 − exp(−Ω(d)). Taking a union bound over all k ∈ [m], we know ∩k∈[m]Ek holds with probability at least 1−m exp(−Ω(d)). From now on, we assume ∩k∈[m]Ek holds.
Let’s first consider each individual loss function ∆TbT (η, Pk). Let {ŵ(k)τ,η} be the GD sequence without truncation. We have
ŵ(k)τ,η − w (k) train =ŵ (k) τ−1,η − w (k) train − ηH (k) train(ŵ (k) τ−1,η − w (k) train)
=(I − ηH(k)train)(ŵ (k) τ−1,η − w (k) train) = −(I − ηH (k) train) tw (k) train.
For any η ∈ [0, 1/L], we have ∥∥∥ŵ(k)τ,η∥∥∥ ≤ ∥∥∥w(k)train∥∥∥ = ∥∥∥(w(k)train)∗ + (X(k)train)†ξ(k)train∥∥∥ ≤ 2√Lσ for any
τ. Therefore, ∥∥∥w(k)t,η ∥∥∥ never exceeds the norm threshold and never gets truncated.
Noticing that ∆TbT (η, Pk) = 12 (w (k) t,η − w (k) train) >H (k) train(w (k) t,η − w (k) train), we have
∆TbT (η, Pk) = 1
2 (w
(k) train) >H (k) train(I − ηH (k) train) 2tw (k) train.
Taking the derivative of ∆TbT (η, Pk) in η, we have
∂
∂η ∆TbT (η, Pk) = −t(w(k)train) >(H (k) train) 2(I − ηH(k)train) 2t−1w (k) train.
Conditioning on Ek, we know 1/L ≤ λi(H(k)train) ≤ L for all i ∈ [n] and H (k) train is full rank in the row span of X(k)train. Therefore, we know ∂ ∂η∆TbT (η, Pk) < 0 for all η ∈ [0, 1/L). Here, we assume∥∥∥w(k)train∥∥∥ > 0, which happens with probability 1.
Overall, we know that conditioning on ∩k∈[m]Ek, every ∆TbT (η, Pk) is strictly decreasing for η ∈ [0, 1/L]. Since F̂TbT (η) := 1m ∑m k=1 ∆TbT (η, Pk), we know F̂TbT (η) is strictly decreasing when η ∈ [0, 1/L].
At step size η = 1/L, we have
∆TbT (η, Pk) = 1
2 (w
(k) train) >H (k) train(I − ηH (k) train) 2tw (k) train
≤1 2 L
( 1− 1
L2 )t ∥∥∥w(k)train∥∥∥2 ≤ 2L2σ2(1− 1L2 )t ,
where we upper bound ∥∥∥w(k)train∥∥∥2 by 4Lσ2 at the last step. Therefore, we have F̂TbT (1/L) ≤
2L2σ2(1− 1L2 ) t.
B.2.2 LOWER BOUNDING F̂TbT FOR η ∈ (η̃,∞)
In this section, we prove that the empirical meta objective is lower bounded by Ω(σ2) with high probability for η ∈ (η̃,∞). Step size η̃ is defined such that there is a descent probability of diverging for any step size larger than η̃. Then, we show the contribution from these truncated sequence will be enough to provide an Ω(σ2) lower bound for F̂TbT . The proof of Lemma 3 is given at the end of this section. Lemma 3. With probability at least 1− exp(−Ω(m)),
F̂TbT (η) ≥ σ2
10L8 ,
for all η > η̃.
We define η̃ 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 a training task P, let E1 be the event that √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and
1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. Let Ē2(η) be the event that the GD sequence is truncated with step size η. Define η̃ as follows,
η̃ = inf { η ≥ 0 ∣∣∣∣E12 ‖wt,η − wtrain‖2Htrain 1{E1 ∩ Ē2(η)} ≥ σ2L6 } .
In the next lemma, we prove that for any fixed training set, 1 { E1 ∩ Ē2(η′) } ≥
1 { E1 ∩ Ē2(η) } for any η′ ≥ η. This immediately implies that Pr[E1 ∩ Ē2(η)] and E 12 ‖wt,η − wtrain‖ 2 Htrain 1 { E1 ∩ Ē2(η) } is non-decreasing in η.
Basically we need to show, conditioning on E1, if a GD sequence gets truncated at step size η, 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 τ, if ∥∥w′τ,η∥∥ exceeds the norm threshold, ∥∥w′τ,η′∥∥ must also exceed the norm threshold for any η′ ≥ η. This is easy to prove if τ is odd because in this case
∥∥w′τ,η∥∥ is always non-decreasing in η. The case when τ is even is trickier because there indeed exists certain range of η such that
∥∥w′τ,η∥∥ is decreasing in η.We manage to prove that this problematic case cannot happen when
∥∥w′τ,η∥∥ is at least 4√Lσ. The full proof of Lemma 5 is deferred into Section B.2.4. Lemma 5. Fixing a task P, let E1 and Ē2(η) be as defined in Definition 1. We have
1 { E1 ∩ Ē2(η′) } ≥ 1 { E1 ∩ Ē2(η) } ,
for any η′ ≥ η.
In the next Lemma, we prove that η̃ must lie within (1/L, 3L).We prove this by showing that the GD sequence never gets truncated for η ∈ [0, 2/L] and almost always gets truncated for η ∈ [2.5L,∞). The proof is deferred into Section B.2.4. Lemma 6. Let η̃ be as defined in Definition 1. Suppose σ is a large constant c1. Assume t ≥ c2, d ≥ c4 for some constants c2, c4. We have
1/L < η̃ < 3L.
Now, we are ready to give the proof of Lemma 3.
Proof of Lemma 3. Let E1 and Ē2(η) be as defined in Definition 1. For the simplicity of the proof, we assume E 12 ‖wt,η̃ − wtrain‖ 2 Htrain 1 { E1 ∩ Ē2(η̃) } ≥ σ 2
L6 . We will discuss the proof for the other case at the end, which is very similar.
Conditioning on E1, we know 12 ‖wt,η̃ − wtrain‖ 2 Htrain ≤ 18L2σ2. Therefore, we know Pr[E1 ∩ Ē2(η̃)] ≥ 118L8 . For each task Pk, define E (k) 1 and Ē (k) 2 (η) as the corresponding events on training set S(k)train. By Hoeffding’s inequality, we know with probability at least 1− exp(−Ω(m)),
1
m m∑ k=1 1 { E(k)1 ∩ Ē (k) 2 (η̃) } ≥ 1 20L8 .
By Lemma 5, we know 1 { E(k)1 ∩ Ē (k) 2 (η) } ≥ 1 { E(k)1 ∩ Ē (k) 2 (η̃) } for any η ≥ η̃. Then, we can
lower bound F̂TbT for any η > η̃ as follows,
F̂TbT (η) = 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)train∥∥∥2 H (k) train ≥ 1 m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)train∥∥∥2 H (k) train 1 { E(k)1 ∩ Ē (k) 2 (η) } ≥2σ2 1
m m∑ k=1 1 { E(k)1 ∩ Ē (k) 2 (η) } ≥2σ2 1
m m∑ k=1 1 { E(k)1 ∩ Ē (k) 2 (η̃) } ≥ σ 2 10L8 ,
where the second inequality lower bounds the loss for one task by 2σ2 when the sequence gets truncated.
We have assumed E 12 ‖wt,η̃ − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η̃) } ≥ σ 2
L6 in the proof. Now, we show the
proof also works when E 12 ‖wt,η̃ − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η̃) } < σ 2
L6 with slight changes. Accord-
ing to the definition and Lemma 5, we know E 12 ‖wt,η̃ − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η) } > σ 2
L6 for all η > η̃. At each training set Strain, we can define 1 { E1 ∩ Ē2(η̃′) } as limη→η̃+ 1 { E1 ∩ Ē2(η) } . We also have Pr[E1 ∩ Ē2(η̃′)] ≥ 118L8 . The remaining proof is the same as before as we substitute 1 { E1 ∩ Ē2(η̃) } by 1 { E1 ∩ Ē2(η̃′) } .
B.2.3 GENERALIZATION FOR η ∈ [1/L, η̃]
In this section, we show empirical meta objective F̂TbT is point-wise close to population meta objective FTbT for all η ∈ [1/L, η̃]. Lemma 4. Suppose σ is a large constant c1. Assume t ≥ c2, d ≥ c4 for certain constants c2, c4. With probability at least 1−m exp(−Ω(d))−O(t+m) exp(−Ω(m)),
|FTbT (η)− F̂TbT (η)| ≤ σ2
L3 ,
for all η ∈ [1/L, η̃],
In this section, we first show F̂TbT concentrates on FTbT for any fixed η and then construct -net for F̂TbT and FTbT for η ∈ [1/L, η̃]. We give the proof of Lemma 4 at the end.
We first show that for a fixed η, F̂TbT (η) is close to FTbT (η) with high probability. We prove the meta-loss on each task ∆TbT (η, Pk) is O(1)-subexponential. Then we apply Bernstein’s inequality to get the result. The proof is deferred into Section B.2.4. We will assume σ is a large constant and t ≥ c2, d ≥ c4 for some constants c2, c4 so that Lemma 6 holds and η̃ is a constant. Lemma 7. Suppose σ is a constant. For any fixed η and any 1 > > 0, with probability at least 1− exp(−Ω( 2m)), ∣∣∣F̂TbT (η)− FTbT (η)∣∣∣ ≤ .
Next, we construct an -net for FTbT .By the definition of η̃,we know for any η ≤ η̃, the contribution from truncated sequences in FTbT (η) is small. We can show the contribution from the un-truncated sequences is O(t)-lipschitz. Lemma 8. Suppose σ is a large constant c1. Assume t ≥ c2, d ≥ c4 for some constant c2, c4. There exists an 11σ 2
L4 -net N ⊂ [1/L, η̃] for FTbT with |N | = O(t). That means, for any η ∈ [1/L, η̃],
|FTbT (η)− FTbT (η′)| ≤ 11σ2
L4 ,
for η′ = arg minη′′∈N,η′′≤η(η − η′′).
Proof of Lemma 8. Let E1 and Ē2(η) be as defined in Definition 1. For the simplicity of the proof, we assume E 12 ‖wt,η̃ − wtrain‖ 2 Htrain 1 { E1 ∩ Ē2(η̃) } ≤ σ 2
L6 . We will discuss the proof for the other case at the end, which is very similar.
We can divide E 12 ‖wt,η − wtrain‖ 2 Htrain as follows,
E 1
2 ‖wt,η − wtrain‖2Htrain
=E 1
2 ‖wt,η − wtrain‖2Htrain 1 {E1 ∩ E2(η̃)}+ E
1 2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η̃) } + E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ Ē1 } .
We will construct an -net for the first term and show the other two terms are small. Let’s first consider the third term. Since 12 ‖wt,η − wtrain‖ 2 Htrain
isO(1)-subexponential and Pr[Ē1] ≤ exp(−Ω(d)), we have E 12 ‖wt,η − wtrain‖ 2 Htrain 1 { Ē1 }
= O(1) exp(−Ω(d)). Choosing d to be at least certain constant, we know 12 ‖wt,η − wtrain‖ 2 Htrain 1 { Ē1 } ≤ σ2/L4.
Then we upper bound the second term. Since E 12 ‖wt,η̃ − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η̃) } ≤ σ 2
L6 and 1 2 ‖wt,η̃ − wtrain‖ 2 Htrain
≥ 2σ2 when wt,η̃ diverges, we know Pr[E1 ∩ Ē2(η̃)] ≤ 12L6 . Then, we can upper bound the second term as follows,
E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η̃) } ≤ 18L2σ2 1
2L6 =
9σ2
L4
Next, we show the first term 12 ‖wt,η − wtrain‖ 2 Htrain 1 {E1 ∩ E2(η̃)} has desirable Lipschitz condition. According to Lemma 5, we know 1 {E1 ∩ E2(η)} ≥ 1 {E1 ∩ E2(η̃)} for any η ≤ η̃. Therefore, conditioning on E1 ∩ E2(η̃), we know wt,η never gets truncated for any η ≤ η̃. This means wt,η = Bt,ηwtrain with Bt,η = (I − (I − ηHtrain)t). We can compute the derivative of 12 ‖wt,η − wtrain‖ 2 Htrain as follows, ∂
∂η
1 2 ‖wt,η − wtrain‖2Htrain =
〈 tHtrain(I − ηHtrain)t−1wtrain, Htrain(wt,η − wtrain) 〉 .
Since ‖wt,η‖ = ‖(I − (I − ηHtrain)t)wtrain‖ ≤ 4 √ Lσ and ‖wtrain‖ ≤ 2 √ Lσ, we have ‖(I − ηHtrain)twtrain‖ ≤ 6 √ Lσ. We can bound ∥∥(I − ηHtrain)t−1wtrain∥∥ with ‖(I − ηHtrain)twtrain‖ + ‖wtrain‖ by bounding the expanding directions using ‖(I − ηHtrain)twtrain‖ and bounding the shrinking directions using ‖wtrain‖ . Therefore, we can bound the derivative as follows, ∣∣∣∣ ∂∂η 12 ‖wt,η − wtrain‖2Htrain
∣∣∣∣ ≤ tL× 8√Lσ × 6L√Lσ = 48L3σ2t. Suppose σ is a constant, we know E 12 ‖wt,η − wtrain‖ 2 Htrain
1 {E1 ∩ E2(η̃)} is O(t)-lipschitz. Therefore, there exists an σ 2
L4 -net N for E 1 2 ‖wt,η − wtrain‖ 2 Htrain 1 {E1 ∩ E2(η̃)} with size O(t). That means, for any η ∈ [1/L, η̃],∣∣∣∣E12 ‖wt,η − wtrain‖2Htrain 1 {E1 ∩ E2(η̃)} − E12 ‖wt,η′ − wtrain‖2Htrain 1 {E1 ∩ E2(η̃)} ∣∣∣∣ ≤ σ2L4
for η′ = arg minη′′∈N,η′′≤η(η − η′′). Note we construct the -net in a particular way such that η′ 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 η ∈ [1/L, η̃],
|FTbT (η)− FTbT (η′)| ≤ 11σ2
L4
for η′ = arg minη′′∈N,η′′≤η(η − η′′).
In the above analysis, we have assumed E 12 ‖wt,η̃ − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η̃) } ≤ σ 2
L6 . The proof can be easily generalized to the other case. We can define 1 { E1 ∩ Ē2(η̃′) } as
limη→η̃− 1 { E1 ∩ Ē2(η) } . Then the proof works as long as we substitute 1 { E1 ∩ Ē2(η̃) } by
1 { E1 ∩ Ē2(η̃′) } . We will also add η̃ into the -net.
In order to prove FTbT is close to F̂TbT point-wise in [1/L, η̃], we still need to construct an -net for the empirical meta objective F̂TbT .
Lemma 9. Suppose σ is a large constant c1. Assume t ≥ c2, d ≥ c4 for certain constants c2, c4. With probability at least 1 −m exp(−Ω(d)), there exists an σ 2
L4 -net N ′ ⊂ [1/L, η̃] for F̂TbT with
|N | = O(t+m). That means, for any η ∈ [1/L, η̃],
|F̂TbT (η)− F̂TbT (η′)| ≤ σ2
L4 ,
for η′ = arg minη′′∈N ′,η′′≤η(η − η′′).
Proof of Lemma 9. For each k ∈ [m], let E1,k be the event that √ d/ √ L ≤ σi(X(k)train) ≤ √ Ld and 1/L ≤ λi(H(k)train) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ∥∥∥ξ(k)train∥∥∥ ≤ √dσ. According to Lemma 1 and Lemma 45, we know with probability at least 1−m exp(−Ω(d)), E1,k’s hold for all k ∈ [m]. From now on, we assume all these events hold.
Recall that the empirical meta objective as follows,
F̂TbT (η) := 1
m m∑ k=1 ∆TbT (η, Pk).
For any k ∈ [m], let ηc,k be the smallest step size such that w(k)t,η gets truncated. If ηc,k > η̂, by similar argument as in Lemma 8, we know ∆TbT (η, Pk) is O(t)-Lipschitz in [1/L, η̂] as long as σ is a constant. If ηc,k ≤ η̂, by Lemma 5 we know w(k)t,η gets truncated for any η ≥ ηc,k. This then implies that ∆TbT (η, Pk) is a constant function for η ∈ [ηc,k, η̂].We can also show that ∆TbT (η, Pk) is O(t)-Lipschitz in [1/L, ηc,k). There might be a discontinuity in function value at ηc,k, so we need to add ηc,k into the -net.
Overall, we know there exists an σ 2 L4 -net N ′ with |N ′| = O(t + m) for F̂TbT . That means, for any η ∈ [1/L, η̃], ∣∣∣F̂TbT (η)− F̂TbT (η′)∣∣∣ ≤ σ2 L4 for η′ = arg minη′′∈N ′,η′′≤η(η − η′′).
Finally, we combine Lemma 7, Lemma 8 and Lemma 9 to prove that F̂TbT is point-wise close to FTbT for η ∈ [1/L, η̃].
Proof of Lemma 4. We assume σ as a constant in this proof. By Lemma 7, we know with probability at least 1 − exp(−Ω( 2m)), ∣∣∣F̂TbT (η)− FTbT (η)∣∣∣ ≤ for any fixed η. By Lemma 8, we know there exists an 11σ 2
L4 -net N for FTbT with size O(t). By Lemma 9, we know with probability at least 1−m exp(−Ω(d)), there exists an σ 2
L4 -netN ′ for F̂TbT with sizeO(t+m). According to the proofs
of Lemma 8 and Lemma 9, it’s not hard to verify thatN ∪N ′ is still an 11σ 2
L4 -net for F̂TbT and FTbT . That means, for any η ∈ [1/L, η̃], we have
|FTbT (η)− FTbT (η′)|, |F̂TbT (η)− F̂TbT (η′)| ≤ 11σ2
L4 ,
for η′ = arg minη′′∈N∪N ′,η′′≤η(η − η′′). Taking a union bound over N ∪N ′, we have with probability at least 1−O(t+m) exp(−Ω(m)),∣∣∣F̂TbT (η)− FTbT (η)∣∣∣ ≤ σ2
L4
for all η ∈ N ∪N ′. Overall, we know with probability at least 1 − m exp(−Ω(d)) − O(t + m) exp(−Ω(m)), for all η ∈ [1/L, η̃],
|FTbT (η)− F̂TbT (η)| ≤|FTbT (η)− FTbT (η′)|+ |F̂TbT (η)− F̂TbT (η′)|+ |F̂TbT (η′)− FTbT (η′)|
≤23σ 2 L4 ≤ σ 2 L3 ,
where η′ = arg minη′′∈N∪N ′,η′′≤η(η − η′′). We use the fact that L = 100 in the last inequality.

heading: B.2.4 PROOFS OF TECHNICAL LEMMAS
text: Proof of Lemma 1. Recall thatXtrain is an n×dmatix with n = cdwhere c ∈ [1/4, 3/4].According to Lemma 48, with probability at least 1− 2 exp(−t2/2), we have
√ d− √ cd− t ≤ σi(Xtrain) ≤ √ d+ √ cd+ t,
for all i ∈ [n]. Since Htrain = 1/nX>trainXtrain, we know λi(Htrain) = 1/nσ 2 i (Xtrain). Since c ∈ [ 14 , 3 4 ], we have
1 cd ( √ d + √ cd)2 ≤ 100 − c′ and 1cd ( √ d − √ cd)2 ≥ 1100 + c
′, for some constant c′. Therefore, we know with probability at least 1− exp(−Ω(d)),
1
100 ≤ λi(Htrain) ≤ 100,
for all i ∈ [n]. Similarly, since there exists constant c′′ such that √ d + √ cd ≤ (10 − c′′) √ d and √ d − √ cd ≥ (1/10 + c′′) √ d, we know with probability at least 1− exp(−Ω(d)),
1
10
√ d ≤ σi(Xtrain) ≤ 10 √ d,
for all i ∈ [n]. Choosing L = 100 finishes the proof. Proof of Lemma 5. We prove that for any training set Strain, 1 { E1 ∩ Ē2(η′) } ≥ 1 { E1 ∩ Ē2(η′) } for any η′ > η. This is trivially true if E1 is false on Strain. Therefore, we focus on the case when E1 holds for Strain. Suppose ηc is the smallest step size such that the GD sequence gets truncated. Let {w′τ,ηc} be the GD sequence without truncation. There must exists τ ≤ t such that
∥∥w′τ,ηc∥∥ ≥ 4√Lσ. We only need to prove that
∥∥w′τ,η∥∥ ≥ 4√Lσ for any η ≥ ηc. We prove this by showing the derivative of ∥∥w′τ,η∥∥2 in η is non-negative assuming ∥∥w′τ,η∥∥2 ≥ 4√Lσ.
Recall the recursion of w′τ,η as w ′ τ,η = wtrain − (I − ηHtrain)τwtrain. If τ is an odd number, it’s clear that ∂∂η ∥∥w′τ,η∥∥2 is non-negative at any η ≥ 0. From now on, we assume τ is an even number.
Actually in this case, ∂∂η ∥∥w′τ,η∥∥2 can be negative for some η. However, we can prove the derivative
must be non-negative assuming ∥∥w′τ,η∥∥2 ≥ 4√Lσ.
Suppose the eigenvalue decomposition of Htrain is ∑n i=1 λiuiu > i with λ1 ≥ · · ·λn. Denote ci as 〈wtrain, ui〉 . Let λj be the smallest eigenvalue such that (1− ηλj) ≤ −1. This implies λi ≤ 2/η for any i ≥ j + 1. We can write down
∥∥w′τ,η∥∥2 as follows ∥∥w′τ,η∥∥2 = j∑
i=1
( 1− (1− ηλi)t )2 c2i + n∑ i=j+1 ( 1− (1− ηλi)t )2 c2i
≤ j∑ i=1 ( 1− (1− ηλi)t )2 c2i + ‖wtrain‖ 2 .
Since E1 holds, we know ‖wtrain‖2 ≤ 4Lσ2. Combining with ∥∥w′τ,η∥∥2 ≥ 16Lσ2, we have∑j
i=1 (1− (1− ηλi)t) 2 c2i ≥ 12Lσ2. We can lower bound the derivative as follows,
∂
∂η ‖wτ,η‖2 = j∑ i=1 2tλi(1− ηλi)t−1 ( 1− (1− ηλi)t ) c2i + n∑ i=j+1 2tλi(1− ηλi)t−1 ( 1− (1− ηλi)t ) c2i
≥2t j∑ i=1 λi(1− ηλi)t−1 ( 1− (1− ηλi)t ) c2i − 2t 2 η n∑ i=j+1 c2i ≥2t j∑ i=1 λi(1− ηλi)t−1 ( 1− (1− ηλi)t ) c2i − 2t× 8Lσ2/η.
Then, we only need to show that ∑j i=1 λi(1 − ηλi)t−1 (1− (1− ηλi)t) c2i is larger than 8Lσ2/η. We have j∑ i=1 λi(1− ηλi)t−1 ( 1− (1− ηλi)t ) c2i = j∑ i=1 λi (1− ηλi)t−1 1− (1− ηλi)t ( 1− (1− ηλi)t )2 c2i
= j∑ i=1 λi (ηλi − 1)t−1 (ηλi − 1)t − 1 ( 1− (1− ηλi)t )2 c2i
= j∑ i=1 λi (ηλi − 1)t (ηλi − 1)t − 1 1 ηλi − 1 ( 1− (1− ηλi)t )2 c2i
≥ j∑ i=1 1 η ( 1− (1− ηλi)t )2 c2i ≥ 12Lσ2/η > 8Lσ2/η.
Proof of Lemma 6. Similar as the analysis in Lemma 2, conditioning on E1, we know the GD sequence never exceeds the norm threshold for any η ∈ [0, 2/L]. This then implies
E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η) } = 0,
for all η ∈ [0, 2/L]. Let {w′τ,η} be the GD sequence without truncation. For any step size η ∈ [2.5L,∞], conditioning on E1, we have∥∥w′t,η∥∥ ≥ ((η/L− 1)t − 1) ‖wtrain‖ ≥ (1.5t − 1)( σ 4 √ L − 1 ) ≥ 4 √ Lσ, where the last inequality holds as long as σ ≥ 5 √ L, t ≥ c2 for some constant c2. Therefore, we
know when η ∈ [2.5L,∞), 1 { E1 ∩ Ē2(η) } = 1 {E1}. Then, we have for any η ≥ 2.5L,
E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η) } ≥ 1
2L
( 4 √ Lσ − 2 √ Lσ )2 Pr[E1] ≥ 2σ2 Pr[E1] ≥ σ2
L3 ,
where the last inequality uses Pr[E1] ≥ 1− exp(−Ω(d)) and assume d ≥ c4 for some constant c4.
Overall, we know E 12 ‖wt,η − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η) } equals zero for all η ∈ [0, 2/L] and is at
least σ 2
L3 for all η ∈ [2.5L,∞). By definition, we know η̃ ∈ (1/L, 3L).
Proof of Lemma 7. Recall that F̂TbT (η) := 1m ∑m k=1 ∆TbT (η, Pk). We prove that each ∆TbT (η, Pk) is O(1)-subexponential. We can further write ∆TbT (η, Pk) as follows,
∆TbT (η, Pk) = 1
2 ∥∥∥w(k)t,η − w∗k − (X(k)train)†ξ(k)train∥∥∥2 H
(k) train
≤1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 ∥∥∥H(k)train∥∥∥+ 12n ∥∥∥ξ(k)train∥∥∥2 + ∥∥∥w(k)t,η − w∗k∥∥∥ ( 1√ n ∥∥∥ξ(k)train∥∥∥)( 1√n ∥∥∥X(k)train∥∥∥ ) .
We can write ∥∥∥H(k)train∥∥∥ as σ2max( 1√nX(k)train). According to Lemma 47, we know σmax(X(k)train) − Eσmax(X(k)train) is O(1)-subgaussian, which implies that σmax( 1√ n X (k) train) − Eσmax( 1√ n X (k) train) is O(1/ √ d)-subgaussian. Since Eσmax( 1√nX (k) train) is a constant, we know σmax( 1√ n X (k) train) is O(1)-
subgaussian and σ2max( 1√ n X (k) train) is O(1)-subexponential. Similarly, we know both 1 2n ∥∥∥ξ(k)train∥∥∥2 and( 1√ n
∥∥∥X(k)train∥∥∥)( 1√n ∥∥∥ξ(k)train∥∥∥) are O(1)-subexponential. Suppose σ is a constant, we know
∥∥∥w(k)t,η − w∗k∥∥∥ is upper bounded by a constant. Then, we know ∆TbT (η, Pk) is O(1)-subexponential. Therefore, F̂TbT (η) is the average of m i.i.d. O(1)subexponential random variables. By standard concentration inequality, we know for any 1 > > 0, with probability at least 1− exp(−Ω( 2m)),∣∣∣F̂TbT (η)− FTbT (η)∣∣∣ ≤ .

heading: B.3 TRAIN-BY-VALIDATION (GD)
text: In this section, we show that the optimal step size under F̂TbV is Θ(1/t). Furthermore, we show under 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 F̂TbV (n1,n2)(η) be as defined in Equation 2 with n1, n2 ∈ [d/4, 3d/4]. Assume noise level σ is a large constant c1. Assume unroll length t ≥ c2, number of training tasks m ≥ c3 and dimension d ≥ c4 log(t) for certain constants c2, c3, c4. With probability at least 0.99 in the sampling of training tasks, we have
η∗valid = Θ(1/t) and E ∥∥wt,η∗valid − w∗∥∥2 = ‖w∗‖2 − Ω(1)
for all η∗valid ∈ arg minη≥0 F̂TbV (n1,n2)(η), 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 FTbV 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 1 in Section B.1 We defer the proof of Lemma 10 into Section B.3.1. Lemma 10. Suppose noise level σ is a large enough constant c1. Assume unroll length t ≥ c2 and dimension d ≥ c4 for some constants c2, c4. There exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that
FTbV (η2) ≤ 1 2 ‖w∗‖2 − 9 10 C +
σ2
2
FTbV (η) ≥ 1 2 ‖w∗‖2 − 6 10 C +
σ2
2 ,∀η ∈ [0, η1] ∪ [η3, 1/L]
where C is a positive constant.
To relate the behavior of FTbV to the behavior of F̂TbV , we prove the following generalization result for step sizes in [0, 1/L]. This serves as step 3 in Section B.1. The proof is deferred into Section B.3.2. Lemma 11. For any 1 > > 0, assume d ≥ c4 log(1/ ) for some constant c4. With probability at least 1−O(1/ ) exp(−Ω( 2m)),
|F̂TbV (η)− FTbV (η)| ≤ , for all η ∈ [0, 1/L].
In Lemma 12, we show the empirical meta objective F̂TbV is high for all step size larger than 1/L, which then implies η∗valid ∈ [0, 1/L]. This serves as step 2 in Section B.1. We prove this lemma in Section B.3.3. Lemma 12. Suppose σ is a large constant. Assume t ≥ c2, d ≥ c4 log(t) for some constants c2, c4. With probability at least 1− exp(−Ω(m)),
F̂TbV (η) ≥C ′σ2 + 1
2 σ2,
for all η ≥ 1/L, where C ′ is a positive constant independent with σ.
Combining Lemma 10, Lemma 11 and Lemma 12, we give the proof of Theorem 8.
Proof of Theorem 8. According to Lemma 10, we know as long as d and t are larger than certain constants, there exists η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that
FTbV (η2) ≤ 1 2 ‖w∗‖2 − 9 10 C + σ2/2
FTbV (η) ≥ 1 2 ‖w∗‖2 − 6 10 C + σ2/2,∀η ∈ [0, η1] ∪ [η3, 1/L],
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 1− exp(−Ω(m)),
|F̂TbV (η)− FTbV (η)| ≤ C/10, for all η ∈ [0, 1/L]. Therefore,
F̂TbV (η2) ≤ 1 2 ‖w∗‖2 − 8 10 C + σ2/2
F̂TbV (η) ≥ 1 2 ‖w∗‖2 − 7 10 C + σ2/2,∀η ∈ [0, η1] ∪ [η3, 1/L].
By Lemma 12, we know as long as t ≥ c2, d ≥ c4 log(t) for some constants c2, c4, with probability at least 1− exp(−Ω(m)),
F̂TbV (η) ≥ C ′σ2 + 1
2 σ2,
for all η ≥ 1/L. As long as σ ≥ 1/ √ C ′, we have F̂TbV (η) ≥ 1 + 12σ
2 for all η ≥ 1/L. Combining with F̂TbV (η2) ≤ 12 ‖w ∗‖2− 810C+σ 2/2, we know η∗valid ∈ [0, 1/L]. Furthermore, since F̂TbV (η) ≥ 1 2 ‖w ∗‖2 − 710C + σ 2/2,∀η ∈ [0, η1] ∪ [η3, 1/L], we have η1 ≤ η∗valid ≤ η3. Recall that η1, η3 = Θ(1/t), we know η∗valid = Θ(1/t). At the optimal step size, we have
FTbV (η ∗ valid) ≤ F̂TbV (η∗valid) + C/10 ≤ F̂TbV (η2) + C/10 ≤
1 2 ‖w∗‖2 − 7 10 C + σ2/2.
Since FTbV (η∗valid) = E 12 ∥∥wt,η∗valid − w∗∥∥2 + σ2/2, we have
E ∥∥wt,η∗valid − w∗∥∥2 ≤ ‖w∗‖2 − 75C.
Choosing m to be at least certain constant, this holds with probability at least 0.99.
B.3.1 BEHAVIOR OF FTbV FOR η ∈ [0, 1/L]
In this section, we study the behavior of FTbV when η ∈ [0, 1/L]. We prove the following Lemma. Lemma 10. Suppose noise level σ is a large enough constant c1. Assume unroll length t ≥ c2 and dimension d ≥ c4 for some constants c2, c4. There exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that
FTbV (η2) ≤ 1 2 ‖w∗‖2 − 9 10 C +
σ2
2
FTbV (η) ≥ 1 2 ‖w∗‖2 − 6 10 C +
σ2
2 ,∀η ∈ [0, η1] ∪ [η3, 1/L]
where C is a positive constant.
It’s not hard to verify that FTbV (η) = E1/2 ‖wt,η − w∗‖2+σ2/2. For convenience, denoteQ(η) := 1/2 ‖wt,η − w∗‖2 . In order to prove Lemma 10, we only need to show that EQ(η2) ≤ 12 ‖w
∗‖2 − 9 10C and EQ(η) ≥ 1 2 ‖w
∗‖2 − 610C for all η ∈ [0, η1] ∪ [η3, 1/L]. In Lemma 13, we first show that this happens with high probability over the sampling of tasks. Lemma 13. Suppose noise level σ is a large enough constant c1. Assume unroll length t ≥ c2 for certain constant c2. Then, with probability at least 1−exp(−Ω(d)) over the sampling of tasks, there exists η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that
Q(η2) := 1
2 ‖wt,η2 − w∗‖ 2 ≤ 1 2 ‖w∗‖2 − C
Q(η) := 1
2 ‖wt,η − w∗‖2 ≥
1 2 ‖w∗‖2 − C 2 ,∀η ∈ [0, η1] ∪ [η3, 1/L]
where C is a positive constant.
Since we are in the small step size regime, we know the GD sequence converges with high probability and will not be truncated. For now, let’s assume wt,η = Bt,ηw∗train +Bt,η(Xtrain)
†ξtrain, where Bt,η = I − (I − ηHtrain)t. We have
Q(η) = 1
2 ∥∥Bt,ηw∗train +Bt,η(Xtrain)†ξtrain − w∗∥∥2 = 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain
〉 = 1
2 ‖w∗‖2 + 1 2 ‖Bt,ηw∗train‖ 2 + 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 − 〈Bt,ηw∗train, w∗〉 + 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉 .
In Lemma 14, we show that with high probability the crossing term〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉 is negligible for all η ∈ [0, 1/L]. By Hoeffding’s inequality, we know the crossing term is small for any fixed η. Constructing an -net for the crossing term in η, we can take a union bound and show it’s small for all η ∈ [0, 1/L]. We defer the proof of Lemma 14 to Section B.3.4. Lemma 14. Assume σ is a constant. For any 1 > > 0, we know with probability at least 1−O(1/ ) exp(−Ω( 2d)),∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ , for all η ∈ [0, 1/L].
Denote
G(η) := 1 2 ‖w∗‖2 + 1 2 ‖Bt,ηw∗train‖ 2 + 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 − 〈Bt,ηw∗train, w∗〉 . Choosing = C/4 in Lemma 14, we only need to show G(η2) ≤ ‖w∗‖2 − 5C/4 and G(η) ≥ ‖w∗‖2 − C/4 for all η ∈ [0, η1] ∪ [η3, 1/L].
We first show that there exists η2 = Θ(1/t) such that G(η2) ≤ 12 ‖w ∗‖2 − 5C/4 for some constant C. It’s not hard to show that 12 ‖Bt,ηw ∗ train‖ 2 + 12 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 = O(η2t2σ2). In Lemma 15, we show that the improvement 〈Bt,ηw∗train, w∗〉 = Ω(ηt) is linear in η. Therefore there exists η2 = Θ(1/t) such that G(η2) ≤ 12 ‖w
∗‖2 − 5C/4 for some constant C. We defer the proof of Lemma 15 to Section B.3.4. Lemma 15. For any fixed η ∈ [0, L/t] with probability at least 1− exp(−Ω(d)),
〈Bt,ηw∗train, w∗〉 ≥ ηt
16L .
To lower bound G(η) for small η, we notice
G(η) ≥ 1 2 ‖w∗‖2 − 〈Bt,ηw∗train, w∗〉 .
We can show that 〈Bt,ηw∗train, w∗〉 = O(ηt). Therefore, there exists η1 = Θ(1/t) such that 〈Bt,ηw∗train, w∗〉 ≤ C/4 for all η ∈ [0, η1]. To lower bound G(η) for large η, we lower bound G(η) using the noise square term,
G(η) ≥ 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 . We show that with high probability
∥∥Bt,η(Xtrain)†ξtrain∥∥2 = Ω(σ2) for all η ∈ [log(2)L/t, 1/L]. Therefore, as long as σ is larger than some constant, there exists η3 = Θ(1/t) such that G(η) ≥ 1 2 ‖w
∗‖2 for all η ∈ [η3, 1/L]. Combing Lemma 14 and Lemma 15, we give a complete proof for Lemma 13.
Proof of Lemma 13. Recall that
Q(η) = 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain
〉 =G(η) + 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain
〉 We first show that with probability at least 1 − exp(−Ω(d)), there exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that G(η2) ≤ 1/2 ‖w∗‖2 − 5C/4 and G(η) ≥ 1/2 ‖w∗‖2 − C/4 for all η ∈ [0, η1] ∪ [η3, 1/L]. According to Lemma 1, we know with probability at least 1−exp(−Ω(d)), √ d/ √ L ≤ σi(Xtrain) ≤√
Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] with L = 100.
Upper bounding G(η2): We can expand G(η) as follows:
G(η) := 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 = 1
2 ‖w∗‖2 + 1 2 ‖Bt,ηw∗train‖ 2 + 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 − 〈Bt,ηw∗train, w∗〉 . Recall that Bt,η = I − (I − ηHtrain)t, for any vector w in the span of Htrain,
‖Bt,ηw‖ = ∥∥(I − (I − ηHtrain)t)w∥∥ ≤ Lηt ‖w‖ .
According to Lemma 45, we know with probability at least 1 − exp(−Ω(d)), ‖ξtrain‖ ≤ √ dσ. Therefore, we have 1
2 ‖Bt,ηw∗train‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 ≤ L2η2t2/2 + L3η2t2σ2/2 ≤ L3η2t2σ2, where the second inequality uses σ, L ≥ 1. According to Lemma 15, for any fixed η ∈ [0, L/t], with probability at least 1− exp(−Ω(d)), 〈Bt,ηw∗train, w∗〉 ≥ ηt 16L . Therefore,
G(η) ≤ 1 2 ‖w∗‖2 + L3η2t2σ2 − ηt 16L ≤ 1 2 ‖w∗‖2 − ηt 32L ,
where the second inequality holds as long as η ≤ 132L4σ2t . Choosing η2 := 1 32L4σ2t , we have
G(η2) ≤ 1 2 ‖w∗‖2 − 1 1024L5σ2 = 1 2 ‖w∗‖2 − 5C 4 ,
where C = 1819.2L5σ2 . Note C is a constant as σ, L are constants.
Lower bounding G(η) for η ∈ [0, η1] : Now, we prove that there exists η1 = Θ(1/t) with η1 < η2 such that for any η ∈ [0, η1], G(η) ≥ 12 ‖w ∗‖2 − C4 . Recall that
G(η) = 1 2 ‖w∗‖2 + 1 2 ‖Bt,ηw∗train‖ 2 + 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 − 〈Bt,ηw∗train, w∗〉 . ≥1
2 ‖w∗‖2 − 〈Bt,ηw∗train, w∗〉 .
Since |〈Bt,ηw∗train, w∗〉| ≤ Lηt, we know for any η ∈ [0, η1],
G(η) ≥ 1 2 ‖w∗‖2 − Lη1t.
Choosing η1 = C4Lt , we have for any η ∈ [0, η1],
G(η) ≥ 1 2 ‖w∗‖2 − C 4 .
Lower bounding G(η) for η ∈ [η3, 1/L]: Now, we prove that there exists η3 = Θ(1/t) with η3 > η2 such that for all η ∈ [η3, 1/L],
G(η) ≥ 1 2 ‖w∗‖2 − C 4 .
Recall that
G(η) = 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 ≥ 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 . According to Lemma 45, we know with probability at least 1 − exp(−Ω(d)), √ dσ
2 √ 2 ≤ ‖ξtrain‖ .
Therefore, ∥∥Bt,η(Xtrain)†ξtrain∥∥2 ≥ (1− e−ηt/L)2 σ2 8L ≥ σ 2 32L ,
where the last inequality assumes η ≥ log(2)L/t. As long as t ≥ log(2)L2, we have log(2)L/t ≤ 1/L. Choosing η3 = log(2)L/t, we know for all η ∈ [η3, 1/L],
G(η) ≥ 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 ≥ σ2 64L .
Note that 12 ‖w ∗‖2 = 1/2. Therefore, as long as σ ≥ 8
√ L, we have
G(η) ≥ 1 2 ‖w∗‖2
for all η ∈ [η3, 1/L]. Overall, we have shown that there exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that G(η2) ≤ 1/2 ‖w∗‖2 − 5C/4 and G(η) ≥ 1/2 ‖w∗‖2 − C/4 for all η ∈ [0, η1] ∪ [η3, 1/L]. Recall that Q(η) = G(η) + 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉 . Choosing = C/4 in Lemma 14, we know
with probability at least 1 − exp(−Ω(d)), ∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ C/4 for all η ∈ [0, 1/L]. Therefore, we know Q(η2) ≤ 1/2 ‖w∗‖2 − C and Q(η) ≥ 1/2 ‖w∗‖2 − C/2 for all η ∈ [0, η1] ∪ [η3, 1/L]. Next, we give the proof of Lemma 10.
Proof of Lemma 10. Recall that FTbV (η) = E1/2 ‖wt,η − w∗‖2 + σ 2
2 . For convenience, denote Q(η) := 1/2 ‖wt,η − w∗‖2 . In order to prove Lemma 10, we only need to show that EQ(η2) ≤ 1 2 ‖w ∗‖2 − 910C and EQ(η) ≥ 1 2 ‖w
∗‖2 − 610C for all η ∈ [0, η1] ∪ [η3, 1/L]. According to Lemma 13, as long as σ is a large enough constant c1 and t is at least certain constant c2, with probability at least 1 − exp(−Ω(d)) over the sampling of Strain, there exists η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that
Q(η2) := 1/2 ‖wt,η2 − w∗‖ 2 ≤ 1
2 ‖w∗‖2 − C
Q(η) := 1/2 ‖wt,η − w∗‖2 ≥ 1 2 ‖w∗‖2 − C 2 ,∀η ∈ [0, η1] ∪ [η3, 1/L]
where C is a positive constant. Call this event E . Suppose the probability that E happens is 1 − δ. We can write EQ(η) as follows,
EQ(η) = E[Q(η)|E ] Pr[E ] + E[Q(η)|Ē ] Pr[Ē ].
According to the algorithm, we know ‖wt,η‖ is always bounded by 4 √ Lσ. Therefore, Q(η) := 1/2 ‖wt,η − w∗‖2 ≤ 13Lσ2. When η = η2, we have
EQ(η2) ≤ ( 1
2 ‖w∗‖2 − C
) (1− δ) + 13Lσ2δ
= 1 2 ‖w∗‖2 − δ 2 − C + (C + 13Lσ2)δ
≤1 2 ‖w∗‖2 − 9C 10 ,
where the last inequality assumes δ ≤ C10C+130Lσ2 .
When η ∈ [0, η1] ∪ [η3, 1/L], we have EQ(η2) ≥ ( 1
2 ‖w∗‖2 − C 2
) (1− δ)− 13Lσ2δ
= 1 2 ‖w∗‖2 − δ 2 − (1− δ)C 2 − 13Lσ2δ
≥1 2 ‖w∗‖2 − C 2 − (1/2 + 13Lσ2)δ
≥1 2 ‖w∗‖2 − 6C 10 ,
where the last inequality holds as long as δ ≤ C5C+130Lσ2 .
According to Lemma 13, we know δ ≤ exp(−Ω(d)). Therefore, the conditions for δ can be satisfied as long as d is larger than certain constant.
B.3.2 GENERALIZATION FOR η ∈ [0, 1/L]
In this section, we show F̂TbV is point-wise close to FTbV for all η ∈ [0, 1/L]. Recall Lemma 11 as follows. Lemma 11. For any 1 > > 0, assume d ≥ c4 log(1/ ) for some constant c4. With probability at least 1−O(1/ ) exp(−Ω( 2m)),
|F̂TbV (η)− FTbV (η)| ≤ ,
for all η ∈ [0, 1/L].
In order to prove Lemma 11, let’s first show that for a fixed η with high probability F̂TbV (η) is close to FTbV (η). Similar as in Lemma 7, we show each ∆TbV (η, Pk) is O(1)-subexponential. We defer its proof to Section B.3.4.
Lemma 16. Suppose σ is a constant. For any fixed η ∈ [0, 1/L] and any 1 > > 0, with probability at least 1− exp(−Ω( 2m)), ∣∣∣F̂TbV (η)− FTbV (η)∣∣∣ ≤ . Next, we show that there exists an -net for FTbV with size O(1/ ). By -net, we mean there exists a finite set N of step size such that |FTbV (η) − FTbV (η′)| ≤ for any η ∈ [0, 1/L] and η′ ∈ arg minη∈N |η − η′|. We defer the proof of Lemma 17 to Section B.3.4. Lemma 17. Suppose σ is a constant. For any 1 > > 0, assume d ≥ c4 log(1/ ) for constant c4. There exists an -net N for FTbV with |N | = O(1/ ). That means, for any η ∈ [0, 1/L],
|FTbV (η)− FTbV (η′)| ≤ , for η′ ∈ arg minη∈N |η − η′|.
Next, we show that with high probability, there also exists an -net for F̂TbV with size O(1/ ). Lemma 18. Suppose σ is a constant. For any 1 > > 0, assume d ≥ c4 log(1/ ) for constant c4. With probability at least 1−exp(−Ω( 2m)), there exists an -netN ′ for F̂TbV with |N | = O(1/ ). That means, for any η ∈ [0, 1/L],
|F̂TbV (η)− F̂TbV (η′)| ≤ , for η′ ∈ arg minη∈N |η − η′|.
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 1 − exp(−Ω( 2m)), ∣∣∣F̂TbV (η)− FTbV (η)∣∣∣ ≤ for any fixed η. By Lemma 17 and Lemma 18, we know as long as d = Ω(log(1/ )), with probability at least 1− exp(−Ω( 2m)), there exists -net N and N ′ for FTbV and F̂TbV respectively. Here, both of N and N ′ have size O(1/ ). According to the proofs of Lemma 17 and Lemma 18, it’s not hard to verify that N ∪N ′ is still an -net for F̂TbV and FTbV . That means, for any η ∈ [0, 1/L], we have
|FTbV (η)− FTbV (η′)|, |F̂TbV (η)− F̂TbV (η′)| ≤ , for η′ ∈ arg minη∈N ∪N ′ |η − η ′|.
Taking a union bound over N ∪N ′ , we have with probability at least 1−O(1/ ) exp(−Ω( 2m)),∣∣∣F̂TbV (η)− FTbV (η)∣∣∣ ≤ for any η ∈ N ∪N ′ . Overall, we know with probability at least 1−O(1/ ) exp(−Ω( 2m)), for all η ∈ [0, 1/L],
|FTbV (η)− F̂TbV (η)| ≤|FTbV (η)− FTbV (η′)|+ |F̂TbV (η)− F̂TbV (η′)|+ |F̂TbV (η′)− FTbV (η′)| ≤3 ,
where η′ ∈ arg minη∈N ∪N ′ |η − η ′|. Changing to ′/3 finishes the proof.
B.3.3 LOWER BOUNDING F̂TbV FOR η ∈ [1/L,∞)
In this section, we prove F̂TbV is large for any step size η ≥ 1/L. Therefore, the optimal step size η∗valid must be smaller than F̂TbV . Lemma 12. Suppose σ is a large constant. Assume t ≥ c2, d ≥ c4 log(t) for some constants c2, c4. With probability at least 1− exp(−Ω(m)),
F̂TbV (η) ≥C ′σ2 + 1
2 σ2,
for all η ≥ 1/L, where C ′ is a positive constant independent with σ.
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 is high. The proof of Lemma 19 is deferred into Section B.3.4. Lemma 19. Assume t ≥ c2, d ≥ c4 for some constants c2, c4. With probability at least 1− exp(−Ω(m)), F̂TbV (η) ≥ σ2, for all η ∈ [3L,∞)
The case for step size within [1/L, 3L] requires more efforts. We give the proof of Lemma 20 in this section later. Lemma 20. Suppose σ is a large constant. Assume t ≥ c2, d ≥ c4 log(t) for some constants c2, c4. With probability at least 1− exp(−Ω(m)),
F̂TbV (η) ≥C4σ2 + 1
2 σ2,
for all η ∈ [1/L, 3L], where C4 is a positive constant independent with σ.
With the above two lemmas, Lemma 12 is just a combination of them.
Proof of Lemma 12. The result follows by taking a union bound and choosing C ′ = min(C4, 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, if the GD sequence has a reasonable probability of diverging, we can still show the loss is high similar as before. If not, we 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 12 ∥∥(I − (I − ηHtrain)t)(Xtrain)†ξtrain∥∥2. When η ∈ [1/L, 3L], the eigenvalues of I − ηHtrain in Strain subspace can be negative. If all the non-zero n eigenvalues of Htrain have the same value, there exists a step size such that the eigenvalues of I − ηHtrain in subspace Strain is −1. If t is even, the eigenvalues of I − (I − ηHtrain)t in Strain subspace are zero, which means GD sequence does not catch any noise in Strain.
Notice that the above problematic case cannot happen when the eigenvalues of Htrain are spread out. Basically, when there are two different eigenvalues, there won’t exist any large η that can cancel both directions at the same time. In Lemma 21, we show with constant probability, the eigenvalues of Htrain are indeed spread out. The proof is deferred into Section B.3.4. Lemma 21. Let the top n eigenvalues of Htrain be λ1 ≥ · · · ≥ λn. Assume dimension d ≥ c4 for certain constant c4. There exist positive constants µ, µ′, µ′′ such that with probability at least µ,
λµ′n − λn−µ′n+1 ≥ µ′′.
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 σ is a large enough constant c1. Assume unroll length t ≥ c2 and dimension d ≥ c4 for some constants c2, c4. Then, with probability at least C1
‖Bt,ηwtrain − w∗‖2Htrain ≥ C2σ 2,
for all η ∈ [1/L, 3L], where C1, C2 are positive constants.
Proof of Lemma 22. Let E1 be the event that √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤
L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. Let E3 be the event that √ d/ √ L ≤ σi(Xvalid) ≤√
Ld and 1/L ≤ λi(Hvalid) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξvalid‖ ≤ √ dσ. According to Lemma 1 and Lemma 45, we know both E1 and E3 hold with probability at least 1− exp(−Ω(d)). Let the top n eigenvalues of Htrain be λ1 ≥ · · · ≥ λn. According to Lemma 21, assuming d is larger than certain constant, we know there exist positive constants µ1, µ2, µ3 such that with probability at least µ1, λµ2n − λn−µ2n+1 ≥ µ3. Call this event E2.
Let S1 and S2 be the span of the bottom and top µ2n eigenvectors of Htrain respectively. According to Lemma 45, we know ‖ξtrain‖ ≥ √ d
4 σ with probability at least 1 − exp(−Ω(d)). Let P1 ∈ Rn×n be a rank-µ2n projection matrix such that the column span of (Xtrain)†P1 is S1. By Johnson-Lindenstrauss Lemma, we know with probability at least 1 − exp(−Ω(d)),∥∥ProjP1ξtrain∥∥ ≥ √µ22 ‖ξtrain‖ . Taking a union bound, with probability at least 1 − exp(−Ω(d)),∥∥ProjP1ξtrain∥∥ ≥ √µ2dσ8 . Similarly, we can define P2 for the S2 subspace and show with probability at least 1− exp(−Ω(d)),
∥∥ProjP2ξtrain∥∥ ≥ √µ2dσ8 . Call the intersection of both events as E4, which happens with with probability at least 1− exp(−Ω(d)). Taking a union bound, we know E1 ∩ E2 ∩ E3 ∩ E4 holds with probability at least µ1/2 as long as d is larger than certain constant. Through the proof, we assume E1 ∩ E2 ∩ E3 ∩ E4 holds. Let’s first lower bound ‖Bt,ηwtrain − w∗train‖ as follows,
‖Bt,ηwtrain − w∗train‖ = ∥∥Bt,η (w∗train + (Xtrain)†ξtrain)− w∗train∥∥ ≥ (∥∥Bt,η (w∗train + (Xtrain)†ξtrain)∥∥− 1)
Recall that we define S1 and S2 as the span of the bottom and top µ2n eigenvectors of Htrain respectively. We rely on S1 to lower bound ‖wt,η − w∗‖ when η is small and rely on S2 when η is large.
Case 1: Let σS1min(Bt,η) be the smallest singular value of Bt,η within S1 subspace. If ηλn−µ2n+1 ≤ 2− µ3/(2L), we have
σS1min(Bt,η) ≥ min
( 1− ( 1− 1
L2
)t , 1− ( 1− µ3
2L
)t) ≥ 1
2 ,
where the second inequality assumes t ≥ max(L2, 2L/µ3) log 2. Then, we have ‖wt,η − w∗‖ ≥ ( σS1min(Bt,η) (∥∥ProjS1(Xtrain)†ξtrain∥∥− 1)− 1) ≥ ( 1
2
(√ µ2σ 8 √ L − 1 ) − 1 ) ≥ √ µ2σ 32 √ L ,
where the second inequality uses ∥∥ProjP1ξtrain∥∥ ≥ √µ2dσ8 and the last inequality assumes σ ≥ 48√L√µ2 .
Case 2: If ηλn−µ2n+1 > 2−µ3/(2L), we have ηλµ2n ≥ 2 +µ3/(2L) since λµ2n−λn−µ2n+1 ≥ µ3 and η ≥ 1/L. Let σS2min(Bt,η) be the smallest singular value of Bt,η within S2 subspace. We have
σS2min(Bt,η) ≥ ((
1 + µ3 2L
)t − 1 ) ≥ 1
2 ,
where the last inequality assumes t ≥ 4L/µ3. Then, similar as in Case 1, we can also prove ‖wt,η − w∗‖ ≥ √ µ2σ
32 √ L .
Therefore, we have
‖Bt,ηwtrain − w∗‖2Htrain = ‖Bt,ηwtrain − w ∗ train‖ 2 Htrain ≥ 1 L ‖Bt,ηwtrain − w∗train‖ 2 ≥ µ2σ 2 1024L2 ,
for all η ∈ [1/L, 3L]. We denote C1 := µ1/2 and C2 = µ21024L2 . 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 > > 0, with probability at least 1 − O(t/ ) exp(−Ω( 2d)), λn(Hvalid) ≥ 1/L and
‖wt,η − wvalid‖2Hvalid ≥ ‖wt,η − w ∗‖2Hvalid + (1− )σ 2,
for all η ∈ [1/L, 3L].
Combing the above lemmas, we give the proof of Lemma 20.
Proof of Lemma 20. According to Lemma 23, we know given 1 > > 0, with probability at least 1 − O(t/ ) exp(−Ω( 2d)), λn(Hvalid) ≥ 1/L and ‖wt,η − wvalid‖2Hvalid ≥ ‖wt,η − w
∗‖2Hvalid + (1 − )σ2 for all η ∈ [1/L, 3L]. Call this event E1. Suppose Pr[E1] ≥ 1− δ/2, where δ will be specifies later. For each training set S(k)train, we also define E (k) 1 . By concentration, we know with probability
at least 1− exp(−Ω(δ2m)), 1/m ∑m k=1 1 { E(k)1 } ≥ 1− δ.
According to Lemma 22, we know there exist constants C1, C2 such that with probability at least C1, ‖Bt,ηwtrain − w∗‖2Htrain ≥ C2σ
2 for all η ∈ [1/L, 3L]. Call this event E2. For each training set S
(k) train, we also define E (k) 2 . By concentration, we know with probability at least 1 − exp(−Ω(m)), 1/m ∑m k=1 1 { E(k)2 } ≥ C1/2.
For any step size η ∈ [1/L, 3L], we can lower bound F̂TbV (η) as follows,
F̂TbV (η) = 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)valid∥∥∥2 H (k) valid
≥ 1 m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)valid∥∥∥2 H (k) valid 1 { E(k)1 } ≥ 1 m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 } + 1 2 (1− )(1− δ)σ2
≥ 1 m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 } + 1 2 (1− )(1− δ)σ2.
As long as δ ≤ C1/4, we know 1m ∑m k=1 1 { E(k)1 ∩ E (k) 2 } ≥ C1/4. Let Ē3(η) be the event that w(k)t,η gets truncated with step size η. We have
1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 } = 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 ∩ E (k) 3 } + 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 ∩ Ē (k) 3 } .
If 1m ∑m k=1 1 { E(k)1 ∩ E (k) 2 ∩ Ē (k) 3 } ≥ C1/8, we have
1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 } ≥ 1 m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 ∩ Ē (k) 3 } ≥C1
8 × 9σ
2
2 =
9C1σ 2
16 . Here, we lower bound ∥∥∥w(k)t,η − w∗k∥∥∥2
Hvalid by 9σ2 when the sequence gets truncated.
If 1m ∑m k=1 1 { E(k)1 ∩ E (k) 2 ∩ Ē (k) 3 } < C1/8, we know 1m ∑m k=1 1 { E(k)1 ∩ E (k) 2 ∩ E (k) 3 } ≥ C1/8. Then, we have 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 } ≥ 1 m m∑ k=1 1 2 ∥∥∥B(k)t,η wtrain − w∗k∥∥∥2 Hvalid 1 { E(k)1 ∩ E (k) 2 ∩ E (k) 3 } ≥C1
8 × C2σ
2
2 = C1C2σ
2
16
Letting C3 = min( 9C116 , C1C2 16 ), we then have
F̂TbV (η) ≥ C3σ2 + 1 2 (1− )(1− δ)σ2 ≥ C3σ
2
2 +
1 2 σ2,
where the last inequality chooses δ = = C3/2. In order for Pr[E1] ≥ 1 − δ/2, we only need d ≥ c4 log(t) for some constant c4. Replacing C3/2 by C4 finishes the proof.

heading: B.3.4 PROOFS OF TECHNICAL LEMMAS
text: Proof of Lemma 14. We first show that for a fixed η ∈ [0, 1/L], the crossing term∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ is small with high probability. We can write down the crossing term as follows:〈
Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉 = 〈 [(Xtrain) †]>Bt,η(Bt,ηw ∗ train − w∗), ξtrain 〉 .
Noticing that ξtrain is independent with [(Xtrain)†]>Bt,η(Bt,ηw∗train − w∗), we will use Hoeffding’s inequality to bound ∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣. According to Lemma 1, we know with probability at least 1 − exp(−Ω(d)), √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] with L = 100. Since η ≤ 1/L, we know ‖Bt,η‖ = ‖I − (I − ηHtrain)t‖ ≤ 1. Therefore, we have ∥∥[(Xtrain)†]>Bt,η(Bt,ηw∗train − w∗)∥∥ ≤ 2√L√
d ,
for any η ∈ [0, 1/L]. Then, for any > 0, by Hoeffding’s inequality, with probability at least 1− exp(−Ω( 2d)), ∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ . Next, we construct an -net on η and show the crossing term is small for all η ∈ [0, 1/L]. Let
g(η) := 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉 .
We compute the derivative of g(η) as follows: g′(η) = 〈 tHtrain(I − ηHtrain)t−1w∗train, Bt,η(Xtrain)†ξtrain 〉 + 〈 Bt,ηw ∗ train − w∗, tHtrain(I − ηHtrain)t−1(Xtrain)†ξtrain
〉 By Lemma 45, we know with probability at least 1− exp(−Ω(d)), ‖ξtrain‖ ≤ √ dσ. Therefore,
|g′(η)| ≤ L1.5t (
1− η L
)t−1 σ + 2L1.5t ( 1− η
L
)t−1 σ = 3L1.5t ( 1− η
L
)t−1 σ.
We can control |g′(η)| in different regimes:
• For η ∈ [0, Lt−1 ], we have |g ′(η)| ≤ 3L1.5tσ.
• Given any 1 ≤ i ≤ log t− 1, for any η ∈ ( iLt−1 , (i+1)L t−1 ], we have |g ′(η)| ≤ 3L 1.5tσ ei .
• For any η ∈ (L log tt−1 , 1/L], we have |g ′(η)| ≤ 3L1.5σ.
Fix any > 0, we know there exists an -net N with size
|N | = 1
( L
t− 1 log t−1∑ i=0 3L1.5tσ ei + ( 1 L − L log t t− 1 ) 3L1.5σ )
≤1
( 3eL2.5tσ
t− 1 + 3 √ Lσ
) = O( 1 )
such that for any η ∈ [0, 1/L], there exists η′ ∈ N with |g(η)− g(η′)| ≤ . Note that L = 100 and σ is a constant. Taking a union bound over N and all the other bad events, we have with probability at least 1− exp(−Ω(d))−O(1/ ) exp(−Ω( 2d)), for all η ∈ [0, 1/L],∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ + = 2 .
As long as 1 > > 0, this happens with probability at least 1 − O(1/ ) exp(−Ω( 2d)). Replacing by ′/2 finishes the proof.
Proof of Lemma 15. According to Lemma 1, we know with probability at least 1 − exp(−Ω(d)), 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] with L = 100.We can lower bound 〈Bt,ηw∗train, w∗〉 as follows,
〈Bt,ηw∗train, w∗〉 = 〈( I − (I − ηHtrain)t ) w∗train, w ∗ train 〉 ≥λmin ( I − (I − ηHtrain)t ) ‖w∗train‖ 2
≥ ( 1− exp ( −ηt L )) ‖w∗train‖ 2 .
By Johnson-Lindenstrauss lemma (Lemma 49), we know with probability at least 1 − 2 exp(−c 2d/4),
‖w∗train‖ ≥ 1 2 (1− ) ‖w∗‖ = 1 2 (1− ).
Then, we know with probability at least 1− 2 exp(−c 2d/4)− exp(−Ω(d)), 〈Bt,ηw∗train, w∗〉 ≥ ( 1− exp ( −ηt L )) ‖w∗train‖ 2
≥ ( 1− exp ( −ηt L )) 1 4 (1− )2
≥1− 2 4
( 1− exp ( −ηt L )) Since ex ≤ 1− x+ x2/2 for any x ≤ 0, we know exp(−ηt/L) ≤ 1− ηt/L+ η2t2/(2L2). For any η ≤ L/t,we have exp(−ηt/L) ≤ 1−ηt/(2L). Then with probability at least 1−2 exp(−c 2d/4)− exp(−Ω(d)),
〈Bt,ηw∗train, w∗〉 ≥ 1− 2
4
ηt
2L
≥ ηt 16L ,
where the second inequality holds by choosing = 1/4.
Proof of Lemma 16. Recall that
F̂TbV (η) := 1
m m∑ k=1 ∆TbV (η, Pk)
For each individual loss function ∆TbV (η, Pk), we have
∆TbV (η, Pk) = 1
2 ∥∥∥w(k)t,η − w∗ − (X(k)valid)†ξ(k)valid∥∥∥2 H
(k) valid
= 1
2 ∥∥∥w(k)t,η − w∗∥∥∥2 H
(k) valid
+ 1
2n ∥∥∥ξ(k)valid∥∥∥2 +〈w(k)t,η − w∗, 1n (X(k)valid)>ξ(k)valid 〉
≤25Lσ 2
2 ∥∥∥H(k)valid∥∥∥+ 12n ∥∥∥ξ(k)valid∥∥∥2 + 5√Lσ ( 1√ n ∥∥∥X(k)valid∥∥∥)( 1√n ∥∥∥ξ(k)valid∥∥∥ )
We can write ∥∥∥H(k)valid∥∥∥ as σ2max( 1√nX(k)valid). According to Lemma 47, we know σmax(X(k)valid) − Eσmax(X(k)valid) is O(1)-subgaussian, which implies that σmax( 1√ n X (k) valid) − Eσmax( 1√ n X (k) valid) is O(1/ √ d)-subgaussian. Since Eσmax( 1√nX (k) valid) is a constant, we know σmax( 1√ n X (k) valid) is O(1)-
subgaussian and σ2max( 1√ n X (k) valid) is O(1)-subexponential. Similarly, we know both 1 2n ∥∥∥ξ(k)valid∥∥∥2 and( 1√ n ∥∥∥X(k)valid∥∥∥)( 1√n ∥∥∥ξ(k)valid∥∥∥) are O(1)-subexponential. This further implies that ∆TbV (η, Pk) is
O(1)-subexponential. Therefore, F̂TbV is the average of m i.i.d. O(1)-subexponential random variables. By standard concentration inequality, we know for any 1 > > 0, with probability at least 1− exp(−Ω( 2m)), ∣∣∣F̂TbV (η)− FTbV (η)∣∣∣ ≤ .
Proof of Lemma 17. Recall that
FTbV (η) =E 1
2 ‖wt,η − w∗‖2 + σ2/2.
We only need to construct an -net for E 12 ‖wt,η − w ∗‖2. Let E be the event that
√ d/ √ L ≤
σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and ‖ξtrain‖ ≤ √ dσ. We have
E 1
2 ‖wt,η − w∗‖2 = E
[ 1
2 ‖wt,η − w∗‖2 |E
] Pr[E ] + E [ 1
2 ‖wt,η − w∗‖2 |Ē
] Pr[Ē ]
We first construct an -net for E [
1 2 ‖wt,η − w
∗‖2 |E ]
Pr[E ]. Let Q(η) := 12 ‖wt,η − w ∗‖2 . Fix a
training set Strain under which event E holds. We show that Q(η) has desirable lipschitz property. The derivative of Q(η) can be computed as follows,
Q′(η) = 〈 tHtrain(I − ηHtrain)t−1wtrain, wt,η − w∗ 〉 .
Conditioning on E , we have |Q′(η)| = O(1)t(1− η
L )t−1.
Therefore, we have ∣∣∣∣ ∂∂ηE [ 1 2 ‖wt,η − w∗‖2 |E ] Pr[E ] ∣∣∣∣ = O(1)t(1− ηL )t−1. Similar as in Lemma 14, for any > 0, we know there exists an -net N with size O(1/ ) such that for any η ∈ [0, 1/L],∣∣∣∣E [12 ‖wt,η − w∗‖2 |E ] Pr[E ]− E [ 1 2 ‖wt,η′ − w∗‖2 |E ] Pr[E ]
∣∣∣∣ ≤ for η′ ∈ arg minη∈N |η − η′|.
Suppose the probability of Ē is δ. We have E [ 1
2 ‖wt,η − w∗‖2 |Ē
] Pr[Ē ] ≤ 25Lσ 2
2 δ ≤ ,
where the last inequality assumes δ ≤ 2 25Lσ2 . According to Lemma 1 and Lemma 45, we know δ := Pr[Ē ] ≤ exp(−Ω(d)). Therefore, given any > 0, there exists constant c4 such that δ ≤ 2 25Lσ2 as long as d ≥ c4 log(1/ ). Overall, for any > 0, as long as d = Ω(log(1/ )), there exists N with size O(1/ ) such that for any η ∈ [0, 1/L], |FTbV (η) − FTbV (η′)| ≤ 3 for η′ ∈ arg minη∈N |η − η′|. Changing to ′/3 finishes the proof.
Proof of Lemma 18. For each k ∈ [m], let Ek be the event that √ d/ √ L ≤ σi(X(k)train) ≤ √ Ld for any i ∈ [n] and ∥∥∥ξ(k)train∥∥∥ ≤ √dσ. Then, we can write the empirical meta objective as follows, F̂TbV (η) := 1
m m∑ k=1 ∆TbT (η, Pk)1Ek + 1 m m∑ k=1 ∆TbT (η, Pk)1Ēk .
Similar as Lemma 17, we will show that the first term has desirable Lipschitz property and the second term is small. Now, let’s focus on the first term 1m ∑m k=1 ∆TbT (η, Pk)1Ek . Recall that
∆TbT (η, Pk) = 1
2 ∥∥∥w(k)t,η − w(k)valid∥∥∥2 H
(k) valid
= 1
2 ∥∥∥B(k)t,η w(k)train − w∗ − (X(k)valid)†ξ(k)valid∥∥∥2 H
(k) valid
.
Computing the derivative of ∆TbT (η, Pk) in terms of η, we have
∂
∂η ∆TbT (η, Pk) =
〈 tH
(k) train(I − ηH (k) train) t−1w (k) train, H (k) valid
( w
(k) t,η − w∗ − (X (k) valid) †ξ (k) valid )〉 Conditioning on Ek, we can bound the derivative,∣∣∣∣ ∂∂η∆TbT (η, Pk) ∣∣∣∣ = O(1)t(1− ηL)t−1 (∥∥∥H(k)valid∥∥∥+ ( 1√
d ∥∥∥X(k)valid∥∥∥)( 1√ d ∥∥∥ξ(k)valid∥∥∥)) . Therefore, we have∣∣∣∣∣ 1m m∑ k=1 ∂ ∂η ∆TbT (η, Pk)1Ek ∣∣∣∣∣ = O(1)t(1− ηL)t−1 1m m∑ k=1 (∥∥∥H(k)valid∥∥∥+ ( 1√ d ∥∥∥X(k)valid∥∥∥)( 1√ d
∥∥∥ξ(k)valid∥∥∥)) . Similar as in Lemma 16, we know both
∥∥∥H(k)valid∥∥∥ and ( 1√d ∥∥∥X(k)valid∥∥∥)( 1√d ∥∥∥ξ(k)valid∥∥∥) are O(1)-subexponential. Therefore, we know with probability at least 1 − exp(−Ω(m)), 1 m ∑m k=1
(∥∥∥H(k)valid∥∥∥+ ( 1√d ∥∥∥X(k)valid∥∥∥)( 1√d ∥∥∥ξ(k)valid∥∥∥)) = O(1). This further shows that with probability at least 1− exp(−Ω(m)),∣∣∣∣∣ 1m m∑ k=1 ∂ ∂η ∆TbT (η, Pk)1Ek
∣∣∣∣∣ = O(1)t(1− ηL)t−1 . Similar as in Lemma 14, we can show that for any > 0, there exists an -net with size O(1/ ) for 1 m ∑m k=1 ∆TbT (η, Pk)1Ek .
Next, we show that the second term 1m ∑m k=1 ∆TbT (η, Pk)1Ēk is small with high probability. According to the proof in Lemma 16, we know
∆TbT (η, Pk) = O(1) (∥∥∥H(k)valid∥∥∥+ 1d ∥∥∥ξ(k)valid∥∥∥2 + ( 1√ d ∥∥∥X(k)valid∥∥∥)( 1√ d ∥∥∥ξ(k)valid∥∥∥)) Therefore, there exists constant C such that
1
m m∑ k=1 ∆TbT (η, Pk)1Ēk ≤ C 1 m m∑ k=1 (∥∥∥H(k)valid∥∥∥+ 1d ∥∥∥ξ(k)valid∥∥∥2 + ( 1√ d ∥∥∥X(k)valid∥∥∥)( 1√ d ∥∥∥ξ(k)valid∥∥∥))1Ēk . It’s not hard to verify that (∥∥∥H(k)valid∥∥∥+ 1d ∥∥∥ξ(k)valid∥∥∥2 + ( 1√d ∥∥∥X(k)valid∥∥∥)( 1√d ∥∥∥ξ(k)valid∥∥∥) ) 1Ēk is O(1)-
subexponential. Suppose the expectation of (∥∥∥H(k)valid∥∥∥+ 1d ∥∥∥ξ(k)valid∥∥∥2 + ( 1√d ∥∥∥X(k)valid∥∥∥)( 1√d ∥∥∥ξ(k)valid∥∥∥) ) is µ, which is a constant. Suppose the probability of Ēk be δ. We know the expectation of(∥∥∥H(k)valid∥∥∥+ 1d ∥∥∥ξ(k)valid∥∥∥2 + ( 1√d ∥∥∥X(k)valid∥∥∥)( 1√d ∥∥∥ξ(k)valid∥∥∥) ) 1Ēk is µδ due to independence. By
standard concentration inequality, for any 1 > > 0, with probability at least 1− exp(−Ω( 2m)),
C 1
m m∑ k=1 (∥∥∥H(k)valid∥∥∥+ 1d ∥∥∥ξ(k)valid∥∥∥2 + ( 1√ d ∥∥∥X(k)valid∥∥∥)( 1√ d ∥∥∥ξ(k)valid∥∥∥))1Ēk ≤ Cµδ+C ≤ (C+1) , where the second inequality assumes δ ≤ /(Cµ). By Lemma 1 and Lemma 45, we know δ ≤ exp(−Ω(d)). Therefore, as long as d ≥ c4 log(1/ ) for some constant c4, we have δ ≤ /(Cµ).
Overall, we know that as long as d ≥ c4 log(1/ ), with probability at least 1 − exp(−Ω( 2m)), there exists N ′ with |N ′ | = O(1/ ) such that for any η ∈ [0, 1/L],
|F̂TbV (η)− F̂TbV (η′)| ≤ (2C + 3) , for η′ ∈ arg minη∈N |η − η′|. Changing to ′/(2C + 3) finishes the proof. Proof of Lemma 19. Let E1 be the event that √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤
L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. Let E2 be the event that √ d/ √ L ≤ σi(Xvalid) ≤√
Ld and 1/L ≤ λi(Hvalid) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξvalid‖ ≤ √ dσ. According to Lemma 1 and Lemma 45, we know both E1 and E2 hold with probability at least 1 − exp(−Ω(d)). Assuming d ≥ c4 for certain constant c4, we know Pr[E1 ∩E2] ≥ 2/3. Also define E(k)1 and E (k) 2 on each training set S(k)train. By concentration, we know with probability at least 1− exp(−Ω(m)),
1
m m∑ k=1 1 { E(k)1 ∩ E (k) 2 } ≥ 1 2 .
It’s easy to verify that conditioning on E1, the GD sequence always exceeds the norm threshold and gets truncated for η ≥ 3L as long as t is larger than certain constant. We can lower bound F̂TbV for any η ≥ 3L as follows,
F̂TbV (η) = 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)valid∥∥∥2 H (k) valid
≥ 1 m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)valid∥∥∥2 H (k) valid 1 {E1 ∩ E2} ≥ 2σ2 1 2 = σ2,
where the last inequality lower bounds ∥∥∥w(k)t,η − w(k)valid∥∥∥2
H (k) valid
by 2σ2 when w(k)t,η gets truncated.
Proof of Lemma 21. We first show that with constant probability in Xtrain, the variance of the eigenvalues of Htrain is lower bounded by a constant. Let λ̄ be 1/n ∑n i=1 λi. Specifically, we show
1/n ∑n i=1 λ 2 i − λ̄2 is lower bounded by a constant.
Let’s first compute the variance of the eigenvalues in expectation. Let the i-th row of Xtrain be x>i . We have,
E [ λ̄2 ] = 1
n2 E
[( tr ( 1
n X>trainXtrain
))2] = 1
n4 E ( n∑ i=1 ‖xi‖2 )2
= 1
n4 n∑ i=1 E ‖xi‖4 + 1 n4 ∑ 1≤i 6=j≤n E ‖xi‖2 ‖xj‖2
= 1 n4 ( nd(d+ 2) + n(n− 1)d2 ) = d2 n2 + 2d n3 .
Similarly, we compute E [ 1/n ∑n i=1 λ 2 i ] as follows,
E
[ 1
n n∑ i=1 λ2i
] = 1
n3 E [ tr ( X>trainXtrainX > trainXtrain )] = 1
n3 n∑ i=1 E ‖xi‖4 + 1 n3 ∑ 1≤i 6=j≤n E 〈xi, xj〉2
= 1 n3 (nd(d+ 2) + n(n− 1)d) = d
2
n2 + d n + d n2
Therefore, we have
E
[ 1
n n∑ i=1 λ2i − λ̄2 ] = d n + d n2 − 2d n3 ≥ d n ≥ 4 3 ,
where the first inequality assumes n ≥ 2 and the last inequality uses n ≤ 3d4 . Since n ≥ 1 4d, we know n ≥ 2 as long as d ≥ 8. Let E be the event that √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for i ∈ [n] with L = 100. According to Lemma 1, we know E happens with probability at least 1 − exp(−Ω(d)). Let 1 {E} be the indicator function for event E . Next we show that E[1/n ∑n i=1(λi − λ̄)21 {E}] is also lower bounded.
It’s clear that E [ λ̄21 {E} ] is upper bounded by E [ λ̄2 ] . In order to lower bound
E [
1 n ∑n i=1 λ 2 i1 {E} ] , we first show that E [ 1 n ∑n i=1 λ 2 i1 { Ē }]
is small. We can decompose E [
1 n ∑n i=1 λ 2 i1 { Ē }] into two parts,
E
[ 1
n n∑ i=1 λ2i1 { Ē }] =E [ 1 n n∑ i=1 λ2i1 { Ē and λ1 ≤ L }] + E [ 1 n n∑ i=1 λ2i1 {λ1 > L} ] .
The first term can be bounded by L2 Pr[Ē ]. Since Pr[Ē ] ≤ exp(−Ω(d)), we know the first term is at most 1/6 as long as d is larger than certain constant. The second term can be bounded by E [ λ211 {λ1 > L} ] . According to Lemma 48, we know Pr[λ1 ≥ L+ t] ≤ exp(−Ω(dt)). Then, it’s
not hard to verify that E [ λ211 {λ1 > L} ] = O(1/d) that is bounded by 1/6 as long as d is larger
than certain constant. Overall, we know E [
1 n ∑n i=1 λ 2 i1 {E} ] ≥ E [ 1 n ∑n i=1 λ 2 i ] − 1/3. Combing
with the upper bounds on E [ λ̄21 {E} ] , we have E [ 1 n ∑n i=1(λi − λ̄)21 {E} ] ≥ 1. Since conditioning on E , λi is bounded by L for all i ∈ [n]. In order to make E [
1 n ∑n i=1(λi − λ̄)21 {E} ] lower bounded by one, there must exist positive constants µ1, µ2 such
that with probability at least µ1, E holds and 1n ∑n i=1(λi − λ̄)2 ≥ µ2.
Since 1n ∑n i=1(λi−λ̄)2 ≥ µ2 and λi ≤ L for all i ∈ [n],we know there exists a subset of eigenvalues S ⊂ {λi}n1 with size µ3n such that |λi − λ̄| ≥ µ4 for all λi ∈ S, where µ3, µ4 are both positive constants.
If at least half of eigenvalues in S are larger than λ̄, we know at least µ3µ4n2L number of eigenvalues are smaller than λ̄. Otherwise, the expectation of the eigenvalues will be larger than λ̄, which contradicts the definition of λ̄. Similarly, if at least half of eigenvalues in S are smaller than λ̄, we know at least µ3µ4n2L number of eigenvalues are larger than λ̄. Denote µ5 := µ3µ4 2L . We know λµ5n − λn−µ5n+1 ≥ µ4. Proof of Lemma 23. Let E1 be the event that √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤
L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. Let E3 be the event that √ d/ √ L ≤ σi(Xvalid) ≤√
Ld and 1/L ≤ λi(Hvalid) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξvalid‖ ≤ √ dσ. According to Lemma 1 and Lemma 45, we know both E1 and E3 hold with probability at least 1 − exp(−Ω(d)). In this proof, we assume both properties hold and take a union bound at the end.
We can lower bound ‖wt,η − wvalid‖2Hvalid as follows,
‖wt,η − wvalid‖2Hvalid = ∥∥wt,η − w∗ − (Xvalid)†ξvalid∥∥2Hvalid ≥‖wt,η − w∗‖2Hvalid + 1 n ‖ξvalid‖2 − 2
∣∣〈wt,η − w∗, Hvalid(Xvalid)†ξvalid〉∣∣ . For the second term, by Lemma 45, we know for any 1 > > 0, with probability at least 1 − exp(−Ω( 2d)),
1 n ‖ξvalid‖2 ≥ (1− )σ2.
We can write down the third term as 〈 [(Xvalid) †]>Hvalid(wt,η − w∗), ξvalid 〉 . Suppose σ is a constant,
we know ∥∥[(Xvalid)†]>Hvalid(wt,η − w∗)∥∥ = O(1/√d). Therefore, for a fixed η ∈ [1/L, 3L], we have with probability at least 1− exp(−Ω( 2d)),∣∣〈wt,η − w∗, Hvalid(Xvalid)†ξvalid〉∣∣ ≤ .
To prove this crossing term is small for all η ∈ [1/L, 3L], we need to construct an -net for the crossing term. Similar as in Lemma 9, we can show there exists an -net for the crossing term with size O(t/ ). Taking a union bound over this -net, we are able to show with probability at least 1−O(t/ ) exp(−Ω( 2d)), ∣∣〈wt,η − w∗, Hvalid(Xvalid)†ξvalid〉∣∣ ≤ , for all η ∈ [1/L, 3L]. Overall, we have with probability at least 1−O(t/ ) exp(−Ω( 2d)),
‖wt,η − wvalid‖2Hvalid ≥‖wt,η − w ∗‖2Hvalid +
1 n ‖ξvalid‖2 − 2 ∣∣〈wt,η − w∗, Hvalid(Xvalid)†ξvalid〉∣∣ ≥‖wt,η − w∗‖2Hvalid + (1− )σ
2 − 2 ≥ (1− 3 )σ2, for all η ∈ [1/L, 3L], where the last inequality uses σ ≥ 1. The proof finishes as we change 3 to ′.

heading: C PROOFS OF TRAIN-BY-TRAIN WITH LARGE NUMBER OF SAMPLES (GD)
text: 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 m are large enough, train-by-train also performs well. Recall Theorem 6 as follows. Theorem 6. Let F̂TbT (n)(η) be as defined in Equation 1. Assume noise level is a constant c1. Given any 1 > > 0, assume training set size n ≥ cd 2 log( nm d ), unroll length t ≥ c2 log( n d ), number of training tasks m ≥ c3n 2
4d2 log( tnm d ) and dimension d ≥ c4 for certain constants c, c2, c3, c4. With
high probability in the sampling of training tasks, we have E ∥∥wt,η∗train − w∗∥∥2 ≤ (1 + )dσ2n , for all η∗train ∈ arg minη≥0 F̂TbT (n)(η), 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 , in Lemma 24 we show the meta-loss can be decomposed into two terms:
∆TbT (η, P ) = 1
2 ‖wt,η − wtrain‖2Htrain +
1
2n ∥∥(In − ProjXtrain)ξtrain∥∥2 , where wtrain = w∗ + (Xtrain)†ξtrain. Recall that Xtrain is a n × d matrix with its i-th row as x>i . The pseudo-inverse (Xtrain)† has dimension d×n satisfying X†trainXtrain = Id. Here, ProjXtrain ∈ R
n×n is a projection matrix onto the column span of Xtrain.
In Lemma 24, we show with a constant step size, the first term in ∆TbT (η, P ) is exponentially small. The second term is basically the projection of the noise on the orthogonal subspace of the data span. We show this term concentrates well on its mean. This lemma servers as step 1 in Section B.1. The proof of Lemma 24 is deferred into Section C.1. Lemma 24. Assume n ≥ 40d. Given any 1 > > 0, with probability at least 1−m exp(−Ω(n))− exp(−Ω( 4md/n)),
F̂TbT (2/3) ≤ 20(1− 1
3 )2tσ2 + n− d 2n σ2 + 2dσ2 20n .
In the next lemma, we show the empirical meta objective is large when η 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, we rely on the truncated sequences to argue the metaobjective must be high. The precise definition of η̂ is in Definition 2. This lemma serves as step 2 in Section B.1. We leave the proof of Lemma 25 into Section C.2. Lemma 25. Let η̂ be as defined in Definition 2 with 1 > > 0. Assume n ≥ cd, t ≥ c2, d ≥ c4 for some constants c, c2, c4. With probability at least 1− exp(−Ω( 4md2/n2)),
F̂TbT (η) ≥ 2dσ2 8n + n− d 2n σ2 − 2dσ2 20n ,
for all η > η̂.
By Lemma 24 and Lemma 25, we know when t is reasonably large, F̂TbT (η) is larger than F̂TbT (2/3) for all step sizes η > η̂. This means the optimal step size η̂ must lie in [0, η̂]. In Lemma 26, we show a generalization result for η ∈ [0, η̂]. 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 2 with 1 > > 0. Suppose σ is a constant. Assume n ≥ c log( n d )d, t ≥ c2, d ≥ c4 for some constants c, c2, c4.With probability at least 1−m exp(−Ω(n))− O( tn 2d +m) exp(−Ω(m 4d2/n2)),
|FTbT (η)− F̂TbT (η)| ≤ 17 2dσ2
n ,
for all η ∈ [0, η̂],
Combining Lemma 24, Lemma 25 and Lemma 26, we present the proof of Theorem 6 as follows.
Proof of Theorem 6. According to Lemma 24, assuming n ≥ 40d, given any 1/2 > > 0, with probability at least 1−m exp(−Ω(n))− exp(−Ω( 4md/n)), F̂TbT (2/3) ≤ 20(1− 13 )
2tσ2 + n−d 2n σ 2 + 2dσ2 20n . As long as t ≥ c2 log( n d ) for certain constant c2, we have
F̂TbT (2/3) ≤ n− d
2n σ2 +
7 2dσ2
100n .
Let η̂ be as defined in Definition 2 with the same . According to Lemma 25, as long as n ≥ cd, t ≥ c2, d ≥ c4 with probability at least 1− exp(−Ω( 4md2/n2)),
F̂TbT (η) ≥ 2dσ2 8n + n− d 2n σ2 − 2dσ2 20n = n− d 2n σ2 + 7.5 2dσ2 100n
for all η > η̂. We have F̂TbT (η) > F̂TbT (2/3) for all η ≥ η̂. This implies that η∗train is within [0, η̂] and F̂TbT (η∗train) ≤ F̂TbT (2/3) ≤ n−d2n σ 2 + 7 2dσ2 100n .
By Lemma 26, assuming σ is a constant and assuming n ≥ c log( n d )d for some constant c, we have with probability at least 1−m exp(−Ω(n))−O( tn 2d +m) exp(−Ω(m 4d2/n2)),
|FTbT (η)− F̂TbT (η)| ≤ 17 2dσ2
n ,
for all η ∈ [0, η̂]. This then implies
FTbT (η ∗ train) ≤ F̂TbT (η∗train) +
17 2dσ2 n ≤ n− d 2n σ2 + 24 2dσ2 n .
By the analysis in Lemma 24, we have
FTbT (η ∗ train) =E
1
2 ∥∥wt,η∗train − wtrain∥∥2Htrain + E 12n ∥∥(In − ProjXtrain)ξtrain∥∥2 =E 1
2 ∥∥wt,η∗train − wtrain∥∥2Htrain + n− d2n σ2. Therefore, we know E 12
∥∥wt,η∗train − wtrain∥∥2Htrain ≤ 24 2dσ2n . Next, we show this implies E ∥∥wt,η∗train − w∗∥∥2 is small.
Let E be the event that 1− ≤ λi(Htrain) ≤ 1 + for all i ∈ [d]. According to Lemma 27, we know Pr[E ] ≥ 1 − exp(−Ω( 2n)) as long as n ≥ 10d/ 2. Then, we can decompose E ∥∥wt,η∗train − w∗∥∥2 as follows,
E ∥∥wt,η∗train − w∗∥∥2 = E ∥∥wt,η∗train − w∗∥∥2 1 {E}+ E∥∥wt,η∗train − w∗∥∥2 1{Ē} .
Let’s first show the second term is small. Due to the truncation in our algorithm, we know∥∥wt,η∗train − w∗∥∥2 ≤ 412σ2, which then implies E∥∥wt,η∗train − w∗∥∥2 1{Ē} ≤ 412σ2 exp(−Ω( 2n)). As long as n ≥ c 2 log( n d ) for some constant c, we have E ∥∥wt,η∗train − w∗∥∥2 1{Ē} ≤ dσ2n .
We can upper bound the first term by Young’s inequality, E ∥∥wt,η∗train − w∗∥∥2 1 {E} ≤ (1 + 1 )E∥∥wt,η∗train − wtrain∥∥2 1 {E}+ (1 + )E ‖wtrain − w∗‖2 1 {E} .
Conditioning on E , we have ∥∥wt,η∗train − wtrain∥∥2Htrain ≥ (1 − )∥∥wt,η∗train − wtrain∥∥2 which implies∥∥wt,η∗train − wtrain∥∥2 ≤ (1 + 2 )∥∥wt,η∗train − wtrain∥∥2Htrain as long as ≤ 1/2. Similarly, we also have ‖wtrain − w∗‖2 ≤ (1 + 2 ) ‖wtrain − w∗‖2Htrain . Then, we have
E ∥∥wt,η∗train − w∗∥∥2 1 {E}
≤(1 + 1 )(1 + 2 )E ∥∥wt,η∗train − wtrain∥∥2Htrain 1 {E}+ (1 + )(1 + 2 )E ‖wtrain − w∗‖2Htrain 1 {E}
≤(5 + 1 )E ∥∥wt,η∗train − wtrain∥∥2Htrain + (1 + 5 )E ‖wtrain − w∗‖2Htrain
≤(5 + 1 ) 48 2dσ2
n + (1 + 5 )
dσ2
n ≤ (1 + 293 )dσ
2
n .
Overall, we have E ∥∥wt,η∗train − w∗∥∥2 ≤ (1 + 293 )dσ2n + dσ2n = (1 + 294 )dσ2n . Combining all the conditions, we know this holds with probability at least 0.99 as long as σ is a constant c1, n ≥ cd 2 log( nm d ), t ≥ c2 log( n d ),m ≥ c3n 2 4d2 log( tnm d ), d ≥ c4 for some constants c, c2, c3, c4. We finish the proof by choosing = ′/294.
C.1 UPPER BOUNDING F̂TbT (2/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:
∆TbT (η, P ) = 1
2n n∑ i=1 ( 〈wt,η − wtrain, xi〉 − ( ξi − x>i X † trainξtrain ))2 = 1
2 ‖wt,η − wtrain‖2Htrain +
1
2n ∥∥(In − ProjXtrain)ξtrain∥∥2 , where wtrain = w∗+ (Xtrain)†ξtrain. In Lemma 24, we show with a constant step size, the first term is exponentially small and the second term concentrates on its mean.
Lemma 24. Assume n ≥ 40d. Given any 1 > > 0, with probability at least 1−m exp(−Ω(n))− exp(−Ω( 4md/n)),
F̂TbT (2/3) ≤ 20(1− 1
3 )2tσ2 + n− d 2n σ2 + 2dσ2 20n .
Before we go to the proof of Lemma 24, let’s first show the covariance matrix Htrain is very close to identity when n is much larger than d. 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 > > 0, assume n ≥ 10d/ 2. With probability at least 1− exp(−Ω( 2n)),
(1− ) √ n ≤ σi(Xtrain) ≤ (1 + ) √ n and 1− ≤ λi(Htrain) ≤ 1 + ,
for all i ∈ [d].
Now, we are ready to present the proof of Lemma 24.
Proof of Lemma 24. Let’s first look at one training set Strain, in which yi = 〈w∗, xi〉+ ξi for each sample. Recall the meta-loss as
∆TbT (η, P ) = 1
2n n∑ i=1 (〈wt,η, xi〉 − 〈w∗, xi〉 − ξi)2 .
Recall thatXtrain is an n×dmatrix with its i-th row as x>i .With probability 1, we knowXtrain is full column rank. Denote the pseudo-inverse of Xtrain as X † train ∈ Rd×n that satisfies X † trainXtrain = Id and XtrainX † train = ProjXtrain , where ProjXtrain ∈ R
n×n is a projection matrix onto the column span of Xtrain.
Let wtrain be w∗ + X † trainξtrain, where ξtrain is an n-dimensional vector with its i-th entry as ξi. We have,
∆TbT (η, P )
= 1
2n n∑ i=1 ( 〈wt,η − wtrain, xi〉 − ( ξi − x>i X † trainξtrain ))2 = 1
2 ‖wt,η − wtrain‖2Htrain +
1
2n ∥∥(In − ProjXtrain)ξtrain∥∥2 − 1n n∑ i=1 〈 wt,η − wtrain, xiξi − xix>i X † trainξtrain 〉 .
We first show the crossing term is actually zero. We have,
1
n n∑ i=1 〈 wt,η − wtrain, xiξi − xix>i X † trainξtrain 〉 = 1 n 〈 wt,η − wtrain, n∑ i=1 xiξi − n∑ i=1 xix > i X † trainξtrain 〉
= 1
n
〈 wt,η − wtrain, X>trainξtrain −X>trainXtrainX † trainξtrain 〉 = 1
n
〈 wt,η − wtrain, X>trainξtrain −X>trainξtrain 〉 = 0,
where the second last equality holds because XtrainX † train = ProjXtrain .
We can define w(k)train as w ∗ k + (X (k) train) †ξ (k) train for every training set S (k) train. Then, we have
F̂TbT (η) = 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)train∥∥∥2 H (k) train + 1 m m∑ k=1 1 2n ∥∥∥(In − ProjX(k)train )ξ(k)train∥∥∥2 We first prove that the second term concentrates on its mean. We can concatenate m noise vectors ξ
(k) train into a single noise vector ξ̄train with dimension nm.We can also construct a data matrix X̄train ∈ Rnm×dm that consists of X(k)train as diagonal blocks. Then the second term can be written as
1
2 ∥∥∥∥ 1√nm (Inm − ProjX̄train)ξ̄train ∥∥∥∥2 .
According to Lemma 45, with probability at least 1− exp(−Ω( 4md2/n)),( 1− 2d
n
) σ ≤ 1√
nm ∥∥ξ̄train∥∥ ≤ (1 + 2d n ) σ.
By Johnson-Lindenstrauss Lemma (Lemma 49), we know with probability at least 1 − exp(−Ω( 4md)),
1√ nm ∥∥ProjX̄train ξ̄train∥∥ ≥ (1− 2) √ md√ mn 1√ nm ∥∥ξ̄train∥∥ ≥ (1− 2)√ d n (1− 2d n )σ.
Therefore, we have ∥∥∥ 1√nm ξ̄train∥∥∥2 ≤ (1 + 3 2dn )σ2 and ∥∥∥ 1√nmProjX̄train ξ̄train∥∥∥2 ≥ (1 − 2 2) dnσ2. Overall, we know with probability at least 1− exp(−Ω( 4md/n)),
1
2 ∥∥∥∥ 1√nm (Inm − ProjX̄train)ξ̄train ∥∥∥∥2 ≤ n− d2n σ2 + 5 2dσ22n .
Now, we show the first term in meta objective is small when we choose a right step size. According to Lemma 27, we know as long as n ≥ 40d, with probability at least 1 − exp(−Ω(n)), √ n/2 ≤
σi(X (k) train) ≤ 3 √ n/2 and 1/2 ≤ λi(H(k)train) ≤ 3/2, for all i ∈ [d]. According to Lemma 45, we know with probability at least 1− exp(−Ω(n)), ∥∥∥ξ(k)train∥∥∥ ≤ 2√nσ. Taking a union bound on m tasks, we know all these events hold with probability at least 1−m exp(−Ω(n)).
For each k ∈ [m], we have ∥∥∥w(k)train∥∥∥ ≤ 1+ 2√n2√nσ ≤ 5σ. 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 40σ. Then, for any step size η ≤ 2/3, we have
1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)train∥∥∥2 H (k) train = 1 m m∑ k=1 1 2 ∥∥∥(I − ηH(k)train)tw(k)train∥∥∥2 H (k) train
≤3 4 (1− η 2 )2t25σ2 ≤ 20(1− 1 3 )2tσ2,
where the last inequality chooses η as 2/3.
Overall, we know with probability at least 1−m exp(−Ω(n))− exp(−Ω( 4md/n)),
F̂TbT (2/3) ≤ 20(1− 1
3 )2tσ2 + n− d 2n σ2 + 5 2dσ2 2n .
We finish the proof by changing 5 2 2 by ( ′)2/20.
C.2 LOWER BOUNDING F̂TbT FOR η ∈ (η̂,∞)
In this section, we show the empirical meta objective is large when the step size exceeds certain threshold. Recall Lemma 25 as follows. Lemma 25. Let η̂ be as defined in Definition 2 with 1 > > 0. Assume n ≥ cd, t ≥ c2, d ≥ c4 for some constants c, c2, c4. With probability at least 1− exp(−Ω( 4md2/n2)),
F̂TbT (η) ≥ 2dσ2 8n + n− d 2n σ2 − 2dσ2 20n ,
for all η > η̂.
Roughly speaking, we define η̂ such that for any step size larger than η̂ the GD sequence has a reasonable probability being truncated. The definition is very similar as η̃ in Definition 1. Definition 2. Given a training task P, let E1 be the event that √ n/2 ≤ σi(Xtrain) ≤ 3 √ n/2 and
1/2 ≤ λi(Htrain) ≤ 3/2 for all i ∈ [d] and √ nσ/2 ≤ ‖ξtrain‖ ≤ 2 √ nσ. Let Ē2(η) be the event that the GD sequence is truncated with step size η. Given 1 > > 0, define η̂ as follows,
η̂ = inf { η ≥ 0 ∣∣∣∣E12 ‖wt,η − wtrain‖2Htrain 1{E1 ∩ Ē2(η)} ≥ 2dσ2n } .
Similar as in Lemma 5, we show 1 { E1 ∩ Ē2(η′) } ≥ 1 { E1 ∩ Ē2(η) } for any η′ ≥ η. This means conditioning on E1, if a GD sequence gets truncated with step size η, it has to be truncated with any step size η′ ≥ η. The proof is deferred into Section C.4. Lemma 28. Fixing a training set Strain, let E1 and Ē2(η) be as defined in Definition 2. We have
1 { E1 ∩ Ē2(η′) } ≥ 1 { E1 ∩ Ē2(η) } ,
for any η′ ≥ η.
Next, we show η̂ does exist and is a constant. Similar as in Lemma 6, we show that the GD sequence almost never diverges when η is small and diverges with high probability when η is large. The proof is left in Section C.4. Lemma 29. Let η̂ be as defined in Definition 2. Suppose σ is a constant. Assume n ≥ cd, t ≥ c2, d ≥ c4 for some constants c, c2, c4. We have
4 3 < η̃ < 6.
Next, we show the empirical loss is large for any η larger than η̃. The proof is very similar as the proof of Lemma 3.
Proof of Lemma 25. By Lemma 29, we know η̂ is a constant as long as n ≥ cd, t ≥ c2, d ≥ c4 for some constants c, c2, c4. Let E1 and Ē2(η) be as defined in Definition 2. For the simplicity of the proof, we assume E 12 ‖wt,η̂ − wtrain‖ 2 Htrain 1 { E1 ∩ Ē2(η̂) } ≥ 2dσ2
n . The other case can be resolved using same techniques in Lemma 3
Conditioning on E1, we know 12 ‖wt,η̂ − wtrain‖ 2 Htrain ≤ 3445 2σ2. Therefore, we know Pr[E1 ∩ Ē2(η̂)] ≥ 4 2d 3×452n . For each task k, define E (k) 1 and Ē (k) 2 (η) as the corresponding events on training set S(k)train. By Hoeffding’s inequality, we know with probability at least 1− exp(−Ω( 4md2/n2)),
1
m m∑ k=1 1 { E(k)1 ∩ Ē (k) 2 (η̂) } ≥ 2d 452n .
By Lemma 28, we know 1 { E(k)1 ∩ Ē (k) 2 (η) } ≥ 1 { E(k)1 ∩ Ē (k) 2 (η̂) } for any η ≥ η̂.
Recall that
F̂TbT (η) = 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)train∥∥∥2 H (k) train + 1 m m∑ k=1 1 2n ∥∥∥(In − ProjX(k)train )ξ(k)train∥∥∥2 . We can lower bound the first term for any η > η̂ as follows,
F̂TbT (η) = 1
m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)train∥∥∥2 H (k) train ≥ 1 m m∑ k=1 1 2 ∥∥∥w(k)t,η − w(k)train∥∥∥2 H (k) train 1 { E(k)1 ∩ Ē (k) 2 (η) } ≥35 2σ2
4
1
m m∑ k=1 1 { E(k)1 ∩ Ē (k) 2 (η) } ≥35 2σ2
4
1
m m∑ k=1 1 { E(k)1 ∩ Ē (k) 2 (η̂) } ≥ 2dσ2 8n ,
where the second inequality lower bounds the loss for one task by 352σ2 when the sequence gets truncated.
For the second term, according to the analysis in Lemma 24, with probability at least 1 − exp(−Ω( 4md/n)),
1
m m∑ k=1 1 2n ∥∥∥(In − ProjX(k)train )ξ(k)train∥∥∥2 ≥ n− d2n σ2 − 2dσ220n . Overall, with probability at least 1− exp(−Ω( 4md2/n2)),
F̂TbT (η) ≥ 2dσ2 8n + n− d 2n σ2 − 2dσ2 20n ,
for all η > η̂.
C.3 GENERALIZATION FOR η ∈ [0, η̂]
Combing Lemma 24 and Lemma 25, it’s not hard to see that the optimal step size η∗train lies in [0, η̂]. In this section, we show a generalization result for step sizes in [0, η̂]. The proof of Lemma 26 is given at the end of this section. Lemma 26. Let η̂ be as defined in Definition 2 with 1 > > 0. Suppose σ is a constant. Assume n ≥ c log( n d )d, t ≥ c2, d ≥ c4 for some constants c, c2, c4.With probability at least 1−m exp(−Ω(n))− O( tn 2d +m) exp(−Ω(m 4d2/n2)),
|FTbT (η)− F̂TbT (η)| ≤ 17 2dσ2
n ,
for all η ∈ [0, η̂],
In Lemma 30, we show F̂TbT concentrates on FTbT at any fixed step size. The proof is almost the same as Lemma 7. We omit its proof. Lemma 30. Suppose σ is a constant. For any fixed η and any 1 > > 0, with probability at least 1− exp(−Ω( 2m)), ∣∣∣F̂TbT (η)− FTbT (η)∣∣∣ ≤ . Next, we construct an -net for FTbT in [0, η̂]. The proof is very similar as in Lemma 8. We defer its proof into Section C.4. Lemma 31. Let η̂ be as defined in Definition 2 with 1 > > 0. Assume the conditions in Lemma 29 hold. Assume n ≥ c log( n d )d for some constant c. There exists an 8 2dσ2
n -net N ⊂ [0, η̂] for FTbT with |N | = O( tn 2d ). That means, for any η ∈ [0, η̂],
|FTbT (η)− FTbT (η′)| ≤ 8 2dσ2
n ,
for η′ = arg minη′′∈N,η′′≤η(η − η′′).
We also construct an -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 η̂ be as defined in Definition 2 with 1 > > 0. Assume the conditions in Lemma 29 hold. Assume n ≥ 40d. With probability at least 1 − m exp(−Ω(n)), there exists an 2dσ2
n -net N ′ ⊂ [0, η̂] for F̂TbT with |N ′| = O( tn 2d +m). That means, for any η ∈ [0, η̂],
|F̂TbT (η)− F̂TbT (η′)| ≤ 2dσ2
n ,
for η′ = arg minη′′∈N ′,η′′≤η(η − η′′).
Combing the above three lemmas, we give the proof of Lemma 26.
Proof of Lemma 26. We assume σ as a constant in this proof. By Lemma 30, we know with probability at least 1 − exp(−Ω(m 4d2/n2)), ∣∣∣F̂TbT (η)− FTbT (η)∣∣∣ ≤ 2dσ2n for any fixed η. By Lemma 31, we know as long as n ≥ c log( n d )d for some constant c, there exists an 8 2dσ2
n -net N for FTbT with size O( tn 2d ). By Lemma 32, we know with probability at least 1 −m exp(−Ω(n)), there exists an 2dσ2
n -net N ′ for F̂TbT with size O( tn 2d + m). It’s not hard to verify that N ∪N ′ is still an 8 2dσ2
n -net for F̂TbV and FTbV . That means, for any η ∈ [0, η̂], we have
|FTbT (η)− FTbT (η′)|, |F̂TbT (η)− F̂TbT (η′)| ≤ 8 2dσ2
n ,
for η′ = arg minη′′∈N∪N ′,η′′≤η(η − η′′).
Taking a union bound over N ∪ N ′, we have with probability at least 1 − O( tn 2d + m) exp(−Ω(m 4d2/n2)), ∣∣∣F̂TbT (η)− FTbT (η)∣∣∣ ≤ 2dσ2 n for all η ∈ N ∪N ′. Overall, we know with probability at least 1−m exp(−Ω(n))−O( tn 2d +m) exp(−Ω(m
4d2/n2)), for all η ∈ [0, η̂],
|FTbT (η)− F̂TbT (η)| ≤|FTbT (η)− FTbT (η′)|+ |F̂TbT (η)− F̂TbT (η′)|+ |F̂TbT (η′)− FTbT (η′)|
≤17 2dσ2
n ,
where η′ = arg minη′′∈N∪N ′,η′′≤η(η − η′′).

heading: C.4 PROOFS OF TECHNICAL LEMMAS
text: Proof of Lemma 27. According to Lemma 48, we know with probability at least 1−2 exp(−t2/2), √ n− √ d− t ≤ σi(Xtrain) ≤ √ n+ √ d+ t
for all i ∈ [d]. Since d ≤ 2n 10 , we have
√ n − √ n√
10 − t ≤ σi(Xtrain) ≤
√ n + √ n√
10 + t. Choosing
t = ( 13 − 1√ 10
) √ n, we have with probability at least 1− exp(−Ω( 2n)),
(1− 3
) √ n ≤ σi(Xtrain) ≤ (1 + 3 ) √ n.
Since λi(Htrain) = 1/nσ2i (Xtrain), we have 1− ≤ λi(Htrain) ≤ 1 + .
Proof of Lemma 28. The proof is almost the same as in Lemma 5. We omit the details here. Basically, in Lemma 5, the only property we rely on is that the norm threshold is larger than 2 ‖wtrain‖ conditioning on E1. Conditioning on E1, we know ‖wtrain‖ ≤ 5σ. Recall that the norm threshold is still set as 40σ. So this property is preserved and the previous proof works.
Proof of Lemma 29. The proof is very similar as in Lemma 6. Conditioning on E1, we know ‖Htrain‖ ≤ 3/2 and ‖wtrain‖ ≤ 5σ. So the GD sequence never exceeds the norm threshold 40σ for any η ≤ 4/3. That means,
E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η) } = 0
for all η ≤ 4/3. To lower bound the loss for large step size, we need to first lower bound ‖wtrain‖ . Recall that wtrain = w ∗+(Xtrain) †ξtrain. Conditioning on E1, we know ‖ξtrain‖ ≤ 2 √ nσ and σd(Xtrain) ≥ √ n/2,
which implies ∥∥(Xtrain)†∥∥ ≤ 2/√n. By Johnson-Lindenstrauss Lemma (Lemma 49), we have∥∥ProjXtrainξtrain∥∥ ≤ 32√d/n ‖ξtrain‖ with probability at least 1 − exp(−Ω(d)). Call this event E3. Conditioning on E1 ∩ E3, we have∥∥(Xtrain)†ξtrain∥∥ ≤ 2√nσ 2√ n 3 2 √ d n ≤ 6 √ d n σ,
which is smaller than 1/2 as long as n ≥ 122dσ2. Note that we assume σ is a constant. This then implies ‖wtrain‖ ≥ 1/2. Let {w′τ,η} be the GD sequence without truncation. For any step size η ∈ [6,∞], conditioning on E1 ∩ E3, we have ∥∥w′t,η∥∥ ≥ ((6× 12 − 1)t − 1 ) ‖wtrain‖ ≥ ( 2t − 1 ) 1 2 ≥ 40σ,
where the last inequality holds as long as t ≥ c2 for some constant c2. Therefore, we know when η ∈ [6,∞), 1 { E1 ∩ Ē2(η) } = 1 {E1 ∩ E3}. Assuming n ≥ 40d,we know E1 holds with probability at least 1− exp(−Ω(n)). Then, we have for any η ≥ 6,
E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η) } ≥1
4 (40σ − 5σ)2 Pr[E1 ∩ E3] ≥
2dσ2
n ,
where the last inequality assumes n ≥ c, d ≥ c4 for some constant c, c4.
Overall, we know E 12 ‖wt,η − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η) } equals zero for all η ∈ [0, 4/3] and is at
least 2dσ2
n for all η ∈ [6,∞). By definition, we know η̂ ∈ (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 E1 and Ē2(η) be as defined in Definition 2. For the simplicity of the proof, we assume E 12 ‖wt,η̂ − wtrain‖ 2 Htrain 1 { E1 ∩ Ē2(η̂) } ≤ 2dσ2
n . The other case can be resolved using techniques in the proof of Lemma 8.
Recall the population meta objective
FTbT (η) = E 1
2 ‖wt,η − wtrain‖2Htrain + n− d 2n σ2.
Therefore, we only need to construct an -net for the first term.
We can divide E 12 ‖wt,η − wtrain‖ 2 Htrain as follows,
E 1
2 ‖wt,η − wtrain‖2Htrain
=E 1
2 ‖wt,η − wtrain‖2Htrain 1 {E1 ∩ E2(η̂)}+ E
1 2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η̂) } + E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ Ē1 } .
We will construct an -net for the first term and show the other two terms are small. Let’s first consider the third term. Assuming n ≥ 40d, we know Pr[E1] ≤ exp(−Ω(n)). Since 12 ‖wt,η − wtrain‖ 2 Htrain
is O(1)-subexponential, by Cauchy-Schwarz inequality, we have E 12 ‖wt,η − wtrain‖ 2 Htrain 1 { Ē1 }
= O(1) exp(−Ω(n)). Choosing n ≥ c log(n/( d)) for some constant c, we know 12 ‖wt,η̂ − wtrain‖ 2 Htrain 1 { Ē1 } ≤ 2dσ2 n .
Then we upper bound the second term. Since E 12 ‖wt,η̂ − wtrain‖ 2 Htrain
1 { E1 ∩ Ē2(η̂) } ≤ 2dσ2
n and 1 2 ‖wt,η̂ − wtrain‖ 2 Htrain ≥ 35 2σ2 4 when wt,η̂ diverges, we know Pr[E1 ∩ Ē2(η̂)] ≤ 4 2d 352n . Then, we can upper bound the second term as follows,
E 1
2 ‖wt,η − wtrain‖2Htrain 1
{ E1 ∩ Ē2(η̂) } ≤ 3× 45 2σ2
4
4 2d
352n ≤ 6
2dσ2
n
Next, similar as in Lemma 8, we can show the first term 12 ‖wt,η − wtrain‖ 2 Htrain 1 {E1 ∩ E2(η̂)} is O(t)-lipschitz. Therefore, there exists an 2dσ2
n -net N for E 1 2 ‖wt,η − wtrain‖ 2 Htrain 1 {E1 ∩ E2(η̂)} with size O( tn 2d ). That means, for any η ∈ [0, η̂],∣∣∣∣E12 ‖wt,η − wtrain‖2Htrain 1 {E1 ∩ E2(η̂)} − E12 ‖wt,η′ − wtrain‖2Htrain 1 {E1 ∩ E2(η̂)}
∣∣∣∣ ≤ 2dσ2n for η′ = arg minη′′∈N,η′′≤η(η − η′′). Combing with the upper bounds on the second term and the third term, we have for any η ∈ [0, η̂],
|FTbT (η)− FTbT (η′)| ≤ 8 2dσ2
n
for η′ = arg minη′′∈N,η′′≤η(η − η′′).
Proof of Lemma 32. By Lemma 29, we know η̂ is a constant. For each k ∈ [m], let E1,k be the event that √ n/2 ≤ σi(X(k)train) ≤ 3
√ n/2 and 1/2 ≤ λi(H(k)train) ≤ 3/2 for all i ∈ [d] and√ nσ/2 ≤ ∥∥∥ξ(k)train∥∥∥ ≤ 2√nσ. Assuming n ≥ 40d, by Lemma 27, we know with probability at least 1−m exp(−Ω(n)), E1,k’s hold for all k ∈ [m].
Then, similar as in Lemma 9, there exists an 2dσ2 n -net N ′ with |N ′| = O( nt 2d +m) for F̂TbT . That means, for any η ∈ [0, η̂], ∣∣∣F̂TbT (η)− F̂TbT (η′)∣∣∣ ≤ 2dσ2 n
for η′ = arg minη′′∈N ′,η′′≤η(η − η′′).

heading: D PROOFS OF TRAIN-BY-TRAIN V.S. TRAIN-BY-VALIDATION (SGD)
text: Previously, we have shown that train-by-validation 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-train setting, each task P contains a training set Strain = {(xi, yi)}ni=1. The inner objective is defined as f̂(w) = 12n ∑ (x,y)∈Strain (〈w, x〉 − y) 2 . Let {wτ,η} be the SGD sequence running on f̂(w) from initialization 0 (without truncation). That means, wτ,η = wτ−1,η − η∇̂f̂(wτ−1,η), where ∇̂f̂(wτ−1,η) = (〈 wτ−1,η, xi(τ−1) 〉 − yi(τ−1) ) xi(τ−1). Here index i(τ − 1) is independently and uniformly sampled from [n]. We denote the SGD noise as nτ−1,η := ∇̂f̂(wτ−1,η)−∇f̂(wτ−1,η). The meta-loss on task P is defined as follows,
∆TbT (n)(η, P ) = ESGDf̂(wt,η) = ESGD 1
2n ∑ (x,y)∈Strain (〈wt,η, x〉 − y)2 ,
where the expectation is taken over the SGD noise. Note wt,η depends on the SGD noise along the trajectory. Then, the empirical meta objective F̂TbT (n)(η) is the average of the meta-loss across m different specific tasks
F̂TbT (n)(η) = 1
m m∑ k=1 ∆TbT (n)(η, Pk). (4)
In order to control the SGD noise in expectation, we restrict the feasible set of step sizes intoO(1/d). We show within this range, the optimal step size under F̂TbT (n) is Ω(1/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 F̂TbT (n) be as defined in Equation 4 with n ∈ [d/4, 3d/4]. Suppose σ is a constant. Assume unroll length t ≥ c2d and dimension d ≥ c4 log(m) for certain constants c2, c4. Then, with probability at least 0.99 in the sampling of training tasks P1, · · · , Pm and test task P ,
η∗train = Ω(1/d) and ESGD ∥∥wt,η∗train − w∗∥∥2 = Ω(σ2),
for all η∗train ∈ arg min0≤η≤ 1 2L3d F̂TbT (n)(η), where L = 100 and wt,η∗train is trained by running SGD on test task P.
In the train-by-validation setting, each task P contains a training set Strain with n1 samples and a validation set with n2 samples. The inner objective is defined as f̂(w) =
1 2n1 ∑ (x,y)∈Strain (〈w, x〉 − y) 2 . Let {wτ,η} be the SGD sequence running on f̂(w) from initialization 0 (with the same truncation defined in Section 4). For each task P , the meta-loss ∆TbV (n1,n2)(η, P ) is defined as
∆TbV (n1,n2)(η, P ) = ESGD 1
2n2 ∑ (x,y)∈Svalid (〈wt,η, x〉 − y)2 .
The empirical meta objective F̂TbV (n1,n2)(η) is the average of the meta-loss acrossm different tasks P1, P2, ..., Pm,
F̂TbV (n1,n2)(η) = 1
m m∑ k=1 ∆TbV (n1,n2)(η, Pk). (5)
In order to bound the SGD noise with high probability, we restrict the feasible set of the step sizes into O( 1
d2 log2 d ). Within this range, we prove the optimal step size under F̂TbV (n1,n2) is Θ(1/t) and
the learned weight is better than initialization 0 by a constant on new tasks. Theorem 10 is proved in Section D.2.
Theorem 10. Let the meta objective F̂TbV (n1,n2) be as defined in Equation 5 with n1, n2 ∈ [d/4, 3d/4]. Assume noise level σ is a large constant c1. Assume unroll length t ≥ c2d2 log2(d),
number of training tasks m ≥ c3 and dimension d ≥ c4 for certain constants c2, c3, c4. There exists constant c5 such that with probability at least 0.99 in the sampling of training tasks, we have
η∗valid = Θ(1/t) and E ∥∥wt,η∗valid − w∗∥∥2 = ‖w∗‖2 − Ω(1)
for all η∗valid ∈ arg min0≤η≤ 1 c5d 2 log2(d) F̂TbV (n1,n2)(η), where the expectation is taken over the new tasks and SGD noise.
Notations: In the following proofs, we use the same set of notations defined in Appendix B. We use EP∼T 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∼T ESGD. Same as in Appendix B, we use letter L to denote constant 100, which upper bounds ‖Htrain‖ with high probability.

heading: D.1 TRAIN-BY-TRAIN (SGD)
text: Recall Theorem 9 as follows. Theorem 9. Let the meta objective F̂TbT (n) be as defined in Equation 4 with n ∈ [d/4, 3d/4]. Suppose σ is a constant. Assume unroll length t ≥ c2d and dimension d ≥ c4 log(m) for certain constants c2, c4. Then, with probability at least 0.99 in the sampling of training tasks P1, · · · , Pm and test task P ,
η∗train = Ω(1/d) and ESGD ∥∥wt,η∗train − w∗∥∥2 = Ω(σ2),
for all η∗train ∈ arg min0≤η≤ 1 2L3d F̂TbT (n)(η), where L = 100 and wt,η∗train is trained by running SGD on test task P.
In order to prove Theorem 9, we first show that η∗train is Ω(1/d) in Lemma 33. The proof is similar as in the GD setting. As long as η = O(1/d), the SGD noise is dominated by the full gradient. Then, we can show that ∆TbT (η, P ) is roughly (1 − Θ(1)η)t, which implies that η∗train = Ω(1/d). We leave the proof of Lemma 33 into Section D.1.1. Lemma 33. Assume t ≥ c2d with certain constant c2. With probability at least 1−m exp(−Ω(d)) in the sampling of m training tasks,
η∗train ≥ 1
6L5d ,
for all η∗train ∈ arg min0≤η≤ 1 2L3d F̂TbT (η).
Let P = (D(w∗), Strain, `) be an independently sampled test task with |Strain| = n ∈ [d/4, 3d/4]. For any step size η ∈ [ 16L5d , 1 2L3d ], let wt,η be the weight obtained by running SGD on f̂(w) for t steps. Next, we show ESGD ‖wt,η − w∗‖2 = Ω(σ2) with high probability in the sampling of P. Lemma 34. Suppose σ is a constant. Assume unroll length t ≥ c2d for some constant c2. With probability at least 1− exp(−Ω(d)) in the sampling of test task P ,
ESGD ‖wt,η − w∗‖2 ≥ σ2
128L ,
for all η ∈ [ 16L5d , 1 2L3d ], where wt,η is obtained by running SGD on task P for t iterations.
With Lemma Lemma 33 and Lemma 34, the proof of Theorem 9 is straightforward.
Proof of Theorem 9. Combing Lemma 33 and Lemma 34, we know as long as σ is a constant, t ≥ c2d, d ≥ c4 log(m),with probability at least 0.99, η∗train = Ω(1/d) and ESGD ∥∥wt,η∗train − w∗∥∥2 = Ω(σ2), for all η∗train ∈ arg min0≤η≤ 1
2L3d F̂TbT (η).

heading: D.1.1 DETAILED PROOFS
text: Proof of Lemma 33. The proof is very similar to the proof of Lemma 2 except that we need to bound the SGD noise term. For each k ∈ [m], let Ek be the event that √ d/ √ L ≤ σi(Xtrain) ≤
√ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. According to Lemma 1 and Lemma 45, we know for each k ∈ [m], Ek happens with probability at least 1− exp(−Ω(d)). Taking a union bound over all k ∈ [m], we know ∩k∈[m]Ek holds with probability at least 1−m exp(−Ω(d)). From now on, we assume ∩k∈[m]Ek holds.
For each k ∈ [m], we have
∆TbT (η, Pk) := 1
2 ESGD ∥∥∥w(k)t,η − w(k)train∥∥∥2 H
(k) train
.
Since 1/L ≤ λi(H(k)train) ≤ L and (w (k) t,η − w (k) train) is in the span of H (k) train, we have
1
2L ESGD ∥∥∥w(k)t,η − w(k)train∥∥∥2 ≤ ∆TbT (η, Pk) ≤ L2 ESGD ∥∥∥w(k)t,η − w(k)train∥∥∥2 . Recall the updates of stochastic gradient descent,
w (k) t,η − w (k) train = (I − ηH (k) train)(w (k) t−1,η − w (k) train)− ηn (k) t−1,η.
Therefore, ESGD [∥∥∥w(k)t,η − w(k)train∥∥∥2 |w(k)t−1,η] = ∥∥∥(I − ηH(k)train)(w(k)t−1,η − w(k)train)∥∥∥2+η2ESGD [∥∥∥n(k)t−1,η∥∥∥2 |w(k)t−1,η] .
We know for any η ≤ 1/L, (1− 2ηL) ∥∥∥w(k)t−1,η − w(k)train∥∥∥2 ≤ ∥∥∥(I − ηH(k)train)(w(k)t−1,η − w(k)train)∥∥∥2 ≤ (1− ηL )∥∥∥w(k)t−1,η − w(k)train∥∥∥2 .
The noise can be bounded as follows, η2ESGD [∥∥∥n(k)t−1,η∥∥∥2 |w(k)t−1,η]
=η2ESGD [∥∥∥xi(t−1)x>i(t−1)(w(k)t−1,η − w(k)train)−H(k)train(w(k)t−1,η − w(k)train)∥∥∥2 |w(k)t−1,η]
≤η2ESGD [∥∥∥xi(t−1)x>i(t−1)(w(k)t−1,η − w(k)train)∥∥∥2 |w(k)t−1,η]
≤η2 max i(t−1) ∥∥xi(t−1)∥∥2 ∥∥∥w(k)t−1,η − w(k)train∥∥∥2 H
(k) train
.
Since ‖Xtrain‖ ≤ √ L √ d, we immediately know maxi(t−1) ∥∥xi(t−1)∥∥ ≤ √L√d. Therefore, we can bound the noise as follows,
η2ESGD [∥∥∥n(k)t−1,η∥∥∥2 |w(k)t−1,η] ≤η2 max
i(t−1) ∥∥xi(t−1)∥∥2 ∥∥∥w(k)t−1,η − w(k)train∥∥∥2 H
(k) train ≤L2η2d ∥∥∥w(k)t−1,η − w(k)train∥∥∥2 .
As long as η ≤ 12L3d , we have (1− ηL) ∥∥∥w(k)t−1,η − w(k)train∥∥∥2 ≤ ESGD [∥∥∥w(k)t,η − w(k)train∥∥∥2 |w(k)t−1,η] ≤ (1− η2L )∥∥∥w(k)t−1,η − w(k)train∥∥∥2 .
This further implies (1− ηL)t ‖wtrain‖2 ≤ ESGD ∥∥∥w(k)t,η − w(k)train∥∥∥2 ≤ (1− η2L )t ‖wtrain‖2 .
Let η2 := 12L3d , we have
∆TbT (η, Pk) ≤ L 2 (1− 1 4L4d )t ‖wtrain‖2
Let η1 := 16L5d , for all η ∈ [0, η1] we have
∆TbT (η, Pk) ≥ 1 2L (1− 1 6L4d )t ‖wtrain‖2 .
As long as t ≥ c2d for certain constant c2, we know 1
2L (1− 1 6L4d )t ‖wtrain‖2 > L 2 (1− 1 4L4d )t ‖wtrain‖2 .
As this holds for all k ∈ [m] and F̂TbT = 1/m ∑m i=1 ∆TbT (η, Pk), we know the optimal step size η∗train is within [ 1 6L5d , 1 2L3d ].
We rely the following technical lemma to prove Lemma 34. Lemma 35. Suppose σ is a constant. Given any > 0, with probability at least 1 − O(1/ ) exp(−Ω( 2d)), ∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ , for all η ∈ [0, 12L3d ].
Proof of Lemma 35. By Lemma 1, with probability at least 1 − exp(−Ω(d)), √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n]. There-
fore ∥∥[(Xtrain)†]>Bt,η(Bt,ηw∗train − w∗)∥∥ ≤ 2√L/√d. Notice that ξtrain is independent with [(Xtrain) †]>Bt,η(Bt,ηw ∗ train − w∗). By Hoeffding’s inequality, with probability at least 1 −
exp(−Ω( 2d)), ∣∣〈[(Xtrain)†]>Bt,η(Bt,ηw∗train − w∗), ξtrain〉∣∣ ≤ . Next, we construct an -net for η and show the crossing term is small for all η ∈ [0, 12L3d ]. For simplicity, denote g(η) := 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉 . Taking the derivative of g(η), we have g′(η) =t 〈 Htrain(I − ηHtrain)t−1w∗train, Bt,η(Xtrain)†ξtrain
〉 + t 〈 Bt,ηw ∗ train − w∗, Htrain(I − ηHtrain)t−1(Xtrain)†ξtrain
〉 According to Lemma 45, we know with probability at least 1 − exp(−Ω(d)), ‖ξtrain‖ ≤ √ dσ. Therefore, the derivative g′(η) can be bounded as follows,
|g′(η)| = O(1)t(1− η L )t−1
Similar as in Lemma 14, there exists an -net N with size O(1/ ) such that for any η ∈ [0, 13L3d ], there exists η′ ∈ N with |g(η)−g(η′)| ≤ . Taking a union bound overN ,we have with probability at least 1−O(1/ ) exp(−Ω( 2d)), for every η ∈ N ,∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ . which implies for every η ∈ [0, 13L3d ].∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ 2 . Changing to ′/2 finishes the proof.
Proof of Lemma 34. According to Lemma 1 and Lemma 45, we know with probability at least 1 − exp(−Ω(d)), √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and√
dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. We assume these properties hold in the proof and take a union bound at
the end.
Recall that ESGD ‖wt,η − w∗‖2 can be lower bounded as follows,
ESGD ‖wt,η − w∗‖2 =ESGD ∥∥∥∥∥Bt,η(w∗train + (Xtrain)†ξtrain)− η t−1∑ τ=0 (I − ηHtrain)t−1−τnτ,η − w∗ ∥∥∥∥∥ 2
≥ ∥∥Bt,η(w∗train + (Xtrain)†ξtrain)− w∗∥∥2 ≥ ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + 2 〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉
For any η ∈ [ 16L5d , 1 2L3d ], we can lower bound the first term as follows,∥∥Bt,η(Xtrain)†ξtrain∥∥2 ≥(1− exp(−ηt L ))2 σ2 16L
≥ ( 1− exp ( − t
6L6d
))2 σ2
16L
≥ σ 2
64L ,
where the last inequality holds as long as t ≥ c2d for certain constant c2.
Choosing = σ 2
256L in Lemma 35, we know with probability at least 1− exp(−Ω(d)),∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ σ2256L, for all η ∈ [0, 12L3d ].
Overall, we have ESGD ‖wt,η − w∗‖2 ≥ σ 2
128L . Taking a union bound over all the bad events, we know this happens with probability at least 1− exp(−Ω(d)).

heading: D.2 TRAIN-BY-VALIDATION (SGD)
text: Recall Theorem 10 as follows. Theorem 10. Let the meta objective F̂TbV (n1,n2) be as defined in Equation 5 with n1, n2 ∈ [d/4, 3d/4]. Assume noise level σ is a large constant c1. Assume unroll length t ≥ c2d2 log2(d), number of training tasks m ≥ c3 and dimension d ≥ c4 for certain constants c2, c3, c4. There exists constant c5 such that with probability at least 0.99 in the sampling of training tasks, we have
η∗valid = Θ(1/t) and E ∥∥wt,η∗valid − w∗∥∥2 = ‖w∗‖2 − Ω(1)
for all η∗valid ∈ arg min0≤η≤ 1 c5d 2 log2(d) F̂TbV (n1,n2)(η), where the expectation is taken over the new tasks and SGD noise.
To prove Theorem 10, we first study the behavior of the population meta objective FTbV . That is,
FTbV (η) := EP∼T∆TbV (η, P ) =EP∼T ESGD 1
2 ∥∥wt,η − w∗ − (Xvalid)†ξvalid∥∥2Hvalid =EP∼T ESGD 1
2 ‖wt,η − w∗‖2 +
σ2
2 .
We show that the optimal step size for the population meta objective FTbV is Θ(1/t) and EP∼T ESGD ‖wt,η − w∗‖2 = ‖w∗‖2 − Ω(1) under the optimal step size. Lemma 36. Suppose σ is a large constant c1. Assume t ≥ c2d2 log2(d), d ≥ c4 for some constants c2, c4. There exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 and constant c5 such that
FTbV (η2) ≤ 1 2 ‖w∗‖2 − 9 10 C +
σ2
2
FTbV (η) ≥ 1 2 ‖w∗‖2 − 6 10 C +
σ2
2 ,∀η ∈ [0, η1] ∪ [η3,
1
c5d2 log 2(d)
]
where C is a positive constant.
In order to relate the behavior of FTbV to F̂TbV ,we show a generalization result from F̂TbV to FTbV for η ∈ [0, 1
c5d2 log2(d/ ) ].
Lemma 37. For any 1 > > 0, assume σ is a constant and d ≥ c4 log(1/ ) for some constant c4. There exists constant c5 such that with probability at least 1−O(1/ ) exp(−Ω( 2m)),
|F̂TbV (η)− FTbV (η)| ≤ , for all η ∈ [0, 1
c5d2 log2(d/ ) ].
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 BEHAVIOR OF FTbV FOR η ∈ [0, 1c5d2 log2 d ]
In this section, we give the proof of Lemma 36. Recall the lemma as follows,
Lemma 36. Suppose σ is a large constant c1. Assume t ≥ c2d2 log2(d), d ≥ c4 for some constants c2, c4. There exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 and constant c5 such that
FTbV (η2) ≤ 1 2 ‖w∗‖2 − 9 10 C +
σ2
2
FTbV (η) ≥ 1 2 ‖w∗‖2 − 6 10 C +
σ2
2 ,∀η ∈ [0, η1] ∪ [η3,
1
c5d2 log 2(d)
]
where C is a positive constant.
Recall that FTbV (η) = EP∼T ESGD1/2 ‖wt,η − w∗‖2 + σ2/2. Denote Q(η) := ESGD1/2 ‖wt,η − w∗‖2. Recall that we truncate the SGD sequence once the weight norm exceeds 4 √ Lσ. Due to the truncation, the expectation of 1/2 ‖wt,η − w∗‖2 over SGD noise is very tricky to analyze.
Instead, we define an auxiliary sequence {w′τ,η} that is obtained by running SGD on task P without truncation and we first study Q′(η) := 1/2ESGD ∥∥w′t,η − w∗∥∥2 . In Lemma 38, we show that with high probability in the sampling of task P , the minimizer of Q′(η) is Θ(1/t). The proof is very similar as the proof of Lemma 13 except that we need to bound the SGD noise at step size η2. We defer the proof into Section D.2.3.
Lemma 38. Given a task P , let {w′τ,η} be the weight obtained by running SGD on task P without truncation. Choose σ as a large constant c1. Assume unroll length t ≥ c2d for some constant c2. With probability at least 1 − exp(−Ω(d)) over the sampling of task P,
√ d/ √ L ≤ σi(Xtrain) ≤√
Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ and there exists
η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that
Q′(η2) := 1/2ESGD ∥∥w′t,η2 − w∗∥∥2 ≤ 12 ‖w∗‖2 − C
Q′(η) := 1/2ESGD ∥∥w′t,η − w∗∥∥2 ≥ 12 ‖w∗‖2 − C2 ,∀η ∈ [0, η1] ∪ [η3, 1/L]
where C is a positive constant.
To relate the behavior of Q′(η) defined on {w′τ,η} to the behavior of Q(η) defined on {wτ,η}. We show when the step size is small enough, the SGD sequence gets truncated with very small probability so that sequence {wτ,η} almost always coincides with sequence {w′τ,η}. The proof of Lemma 39 is deferred into Section D.2.3. Lemma 39. Given a task P , assume √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for
all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. Given any > 0, suppose η ≤ 1
c5d2 log2(d/ ) for some
constant c5, we have |Q(η)−Q′(η)| ≤ .
Combining Lemma 38 and Lemma 39, we give the proof of lemma 36.
Proof of Lemma 36. Recall that we define Q(η) := 1/2ESGD ‖wt,η − w∗‖2 and Q′(η) = 1/2ESGD ∥∥w′t,η − w∗∥∥2 . Here, {w′τ,η} is a SGD sequence running on task P without truncation. According to Lemma 38, with probability at least 1 − exp(−Ω(d)) over the sampling of task P,√ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤
√ dσ and there exists η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that
Q′(η2) ≤ 1
2 ‖w∗‖2 − C
Q′(η) ≥ 1 2 ‖w∗‖2 − C 2 ,∀η ∈ [0, η1] ∪ [η3, 1/L]
where C is a positive constant. Call this event E . Suppose the probability that E happens is 1 − δ. We can write EP∼TQ(η) as follows,
EP∼TQ(η) = EP∼T [Q(η)|E ] Pr[E ] + EP∼T [Q(η)|Ē ] Pr[Ē ].
According to the algorithm, we know ‖wt,η‖ is always bounded by 4 √ Lσ. Therefore, Q(η) := 1/2 ‖wt,η − w∗‖2 ≤ 13Lσ2. By Lemma 39, we know conditioning on E , |Q(η) − Q′(η)| ≤ for any η ≤ 1
c5d2 log2(d/ ) . As long as t ≥ c2d2 log2(d/ ) for certain constant c2, we know η3 ≤
1 c5d2 log2(d/ ) .
When η = η2, we have
EP∼TQ(η2) ≤ (Q′(η2) + ) (1− δ) + 13Lσ2δ ≤ ( 1
2 ‖w∗‖2 − C +
) (1− δ) + 13Lσ2δ
≤1 2 ‖w∗‖2 − C + 13Lσ2δ + ≤ 1 2 ‖w∗‖2 − 9C 10 ,
where the last inequality assumes δ ≤ C260Lσ2 and ≤ C 20 .
When η ∈ [0, η1] ∪ [η3, 1c5d2 log2(d/ ) ], we have
EP∼TQ(η2) ≥ (Q′(η)− ) (1− δ)− 13Lσ2δ ≥ ( 1
2 ‖w∗‖2 − C 2 − ) (1− δ)− 13Lσ2δ
≥1 2 ‖w∗‖2 − C 2 − δ 2 − 13Lσ2δ − ≥ 1 2 ‖w∗‖2 − 6C 10 ,
where the last inequality holds as long as δ ≤ C280Lσ2 and ≤ C 20 .
According to Lemma 38, we know δ ≤ exp(−Ω(d)). Therefore, the conditions for δ can be satisfied as long as d is larger than certain constant. The condition on can be satisfied as long as η ≤
1 c5d2 log2(d) for some constant c5.
D.2.2 GENERALIZATION FOR η ∈ [0, 1 c5d2 log2 d ]
In this section, we prove Lemma 37 by showing that F̂TbV (η) is point-wise close to FTbV (η) for all η ∈ [0, 1
c5d2 log2(d/ ) ]. Recall Lemma 37 as follows.
Lemma 37. For any 1 > > 0, assume σ is a constant and d ≥ c4 log(1/ ) for some constant c4. There exists constant c5 such that with probability at least 1−O(1/ ) exp(−Ω( 2m)),
|F̂TbV (η)− FTbV (η)| ≤ ,
for all η ∈ [0, 1 c5d2 log2(d/ ) ].
In order to prove Lemma 37, we first show that for a fixed η with high probability F̂TbV (η) is close to FTbV (η). Similar as in Lemma 16, we can still show that each ∆TbV (η, P ) isO(1)-subexponential. The proof is deferred into Section D.2.3. Lemma 40. Suppose σ is a constant. Given any 1 > > 0, for any fixed η with probability at least 1− exp(−Ω( 2m)), ∣∣∣F̂TbV (η)− FTbV (η)∣∣∣ ≤ .
Next, we show that there exists an -net for FTbV with sizeO(1/ ). By -net, we mean there exists a finite set N of step sizes such that |FTbV (η)−FTbV (η′)| ≤ for any η and η′ ∈ arg minη∈N |η− η′|. The proof is very similar as in Lemma 17. We defer the proof of Lemma 41 into Section D.2.3. Lemma 41. Suppose σ is a constant. For any 1 > > 0, assume d ≥ c4 log(1/ ) for some c4. There exists constant c5 and an -net N ⊂ [0, 1c5d2 log2(d/ ) ] for FTbV with |N | = O(1/ ). That means, for any η ∈ [0, 1
c5d2 log2(d/ ) ],
|FTbV (η)− FTbV (η′)| ≤ , for η′ ∈ arg minη∈N |η − η′|.
Next, we show that with high probability, there also exists an -net for F̂TbV with size O(1/ ). The proof is very similar as the proof of Lemma 18. We defer the proof into Section D.2.3. Lemma 42. Suppose σ is a constant. For any 1 > > 0, assume d ≥ c4 log(1/ ) for some c4. With probability at least 1−exp(−Ω( 2m)), there exists constant c5 and an -netN ′ ⊂ [0, 1c5d2 log2(d/ ) ] for F̂TbV with |N | = O(1/ ). That means, for any η ∈ [0, 1c5d2 log2(d/ ) ],
|F̂TbV (η)− F̂TbV (η′)| ≤ , for η′ ∈ arg minη∈N |η − η′|.
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.

heading: D.2.3 PROOFS OF TECHNICAL LEMMAS
text: In Lemma 43, we show when the step size is small, the expected SGD noise square is well bounded. The proof follows from the analysis in Lemma 33. Lemma 43. Let {w′τ,η} be an SGD sequence running on task P without truncation. Let n′τ,η be the SGD noise at w′τ,η . Assume √ d/ √ L ≤ σi(Xtrain) ≤ √ L √ σ for all i ∈ [n] and ‖ξtrain‖ ≤ √ dσ. Suppose η ∈ [0, 12L3d ], we have ESGD
∥∥n′τ,η∥∥2 ≤ 4L3σ2d for all τ ≤ t.
Proof of Lemma 43. Similar as the analysis in Lemma 33, for η ≤ 12L3d , we have ESGD [∥∥n′τ,η∥∥2 |w′τ−1,η] ≤ L2d∥∥w′τ−1,η − wtrain∥∥2 .
and ESGD ∥∥w′τ−1,η − wtrain∥∥2 ≤ (1− η2L )τ−1 ‖wtrain‖2 ≤ ∥∥w∗train + (Xtrain)†ξtrain∥∥2 ≤ 4Lσ2.
Therefore, we have ESGD ∥∥n′τ,η∥∥2 ≤ L2dESGD ∥∥w′τ,η − wtrain∥∥2 ≤ 4L3σ2d.
Proof of Lemma 38. We can expand Q′(η) as follows,
Q′(η) := 1
2 ESGD ∥∥w′t,η − w∗∥∥2 = 1
2 ESGD ∥∥∥∥∥Bt,ηw∗train +Bt,η(Xtrain)†ξtrain − η t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η − w∗ ∥∥∥∥∥ 2
= 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + η2 2 ESGD ∥∥∥∥∥ t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η ∥∥∥∥∥ 2
+ 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉
Denote
G(η) := 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2+ η2 2 ESGD ∥∥∥∥∥ t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η ∥∥∥∥∥ 2 .
We first show that with probability at least 1 − exp(−Ω(d)), there exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that G(η2) ≤ 1/2 ‖w∗‖2 − 5C/4 and G(η) ≥ 1/2 ‖w∗‖2 − C/4 for all η ∈ [0, η1] ∪ [η3, 1/L]. According to Lemma 1, we know with probability at least 1−exp(−Ω(d)), √ d/ √ L ≤ σi(Xtrain) ≤√
L √ d and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n].According to Lemma 45, we know with probability
at least 1− exp(−Ω(d)), √ dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ.
Upper bounding G(η2): We can expand G(η) as follows:
G(η) := 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + η2 2 ESGD ∥∥∥∥∥ t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η ∥∥∥∥∥ 2
= 1 2 ‖w∗‖2 + 1 2 ‖Bt,ηw∗train‖ 2 + 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + η2 2 ESGD ∥∥∥∥∥ t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η ∥∥∥∥∥ 2
− 〈Bt,ηw∗train, w∗〉 .
Same as in Lemma 13, we know 12 ‖Bt,ηw ∗ train‖ 2 + 12 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 ≤ L3η2t2σ2. For the SGD noise, by Lemma 43 we know ESGD
∥∥n′τ,η∥∥2 ≤ 4L3σ2d for all τ ≤ t as long as η ≤ 12L3d . Therefore,
η2
2 ESGD ∥∥∥∥∥ t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η ∥∥∥∥∥ 2 ≤ η 2 2 t−1∑ τ=0 ESGD ∥∥n′τ,η∥∥2 ≤ 2L3η2σ2dt ≤ 2L3η2σ2t2,
where the last inequality assumes t ≥ d. According to Lemma 15, for any fixed η ∈ [0, L/t], with probability at least 1− exp(−Ω(d)) over Xtrain,
〈Bt,ηw∗train, w∗〉 ≥ ηt
16L .
Therefore, for any step size η ≤ 12L3d ,
G(η) ≤ 1 2 ‖w∗‖2 + 3L3η2σ2t2 − ηt 16L ≤ 1 2 ‖w∗‖2 − ηt 32L ,
where the second inequality holds as long as η ≤ 196L4σ2t . Choosing η2 := 1 96L4σ2t that is smaller than 12L3d assuming t ≥ d. Then, we have
G(η2) ≤ 1 2 ‖w∗‖2 − 5C 4 ,
where constant C = 13072L5σ2 .
Lower bounding G(η) for η ∈ [0, η1] : Now, we prove that there exists η1 = Θ(1/t) with η1 < η2 such that for any η ∈ [0, η1], G(η) ≥ 12 ‖w ∗‖2 − C4 . Recall that
G(η) = 1 2 ‖w∗‖2 + 1 2 ‖Bt,ηw∗train‖ 2 + 1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + η2 2 ESGD ∥∥∥∥∥ t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η ∥∥∥∥∥ 2
− 〈Bt,ηw∗train, w∗〉 .
≥1 2 ‖w∗‖2 − 〈Bt,ηw∗train, w∗〉 .
Same as in Lemma 13, by choosing η1 = C4Lt , we have for any η ∈ [0, η1],
G(η) ≥ 1 2 ‖w∗‖2 − C 4 .
Lower bounding G(η) for η ∈ [η3, 1/L]: Now, we prove that there exists η3 = Θ(1/t) with η3 > η2 such that for all η ∈ [η3, 1/L],
G(η) ≥ 1 2 ‖w∗‖2 − C 4 .
Recall that
G(η) = 1
2 ‖Bt,ηw∗train − w∗‖ 2 +
1
2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 + η2 2 ESGD ∥∥∥∥∥ t−1∑ τ=0 (I − ηHtrain)t−1−τn′τ,η ∥∥∥∥∥ 2
≥1 2 ∥∥Bt,η(Xtrain)†ξtrain∥∥2 . Same as in Lemma 13, by choosing η3 = log(2)L/t, as long as σ ≥ 8 √ L, we have
G(η) ≥ 1 2 ‖w∗‖2
for all η ∈ [η3, 1/L]. Note η3 ≤ 1/L as long as t ≥ log(2)L2. Overall, we have shown that there exist η1, η2, η3 = Θ(1/t) with η1 < η2 < η3 such that G(η2) ≤ 1/2 ‖w∗‖2 − 5C/4 and G(η) ≥ 1/2 ‖w∗‖2 − C/4 for all η ∈ [0, η1] ∪ [η3, 1/L]. Recall that Q′(η) = G(η) + 〈 Bt,ηw ∗ train − w∗, Bt,η(Xtrain)†ξtrain 〉 . Choosing = C/4 in Lemma 14, we know
with probability at least 1 − exp(−Ω(d)), ∣∣〈Bt,ηw∗train − w∗, Bt,η(Xtrain)†ξtrain〉∣∣ ≤ C/4 for all η ∈ [0, 1/L]. Therefore, we know Q′(η2) ≤ 1/2 ‖w∗‖2 −C and Q′(η) ≥ 1/2 ‖w∗‖2 −C/2 for all η ∈ [0, η1] ∪ [η3, 1/L]. In order to prove Lemma 39, we first construct a super-martingale to show that as long as task P is well behaved, with high probability in SGD noise, the weight norm along the trajectory never exceeds 4 √ Lσ. Lemma 44. Assume √ d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and√
dσ/4 ≤ ‖ξtrain‖ ≤ √ dσ. Given any 1 > δ > 0, suppose η ≤ 1
c5d2 log2(d/δ) for some constant c5,
with probability at least 1− δ in the SGD noise,∥∥w′τ,η∥∥ < 4√Lσ for all τ ≤ t.
Proof of Lemma 44. According to the proofs of Lemma 43, as long as η ≤ 12L3d , we have ESGD [∥∥w′t,η − wtrain∥∥2 |w′t−1,η] ≤ (1− η2L )∥∥w′t−1,η − wtrain∥∥2 .
Since log is a concave function, by Jenson’s inequality, we know ESGD [ log ∥∥w′t,η − wtrain∥∥2 |w′t−1,η]
≤ logESGD [∥∥w′t,η − wtrain∥∥2 |w′t−1,η] ≤ log ∥∥w′t−1,η − wtrain∥∥2 + log(1− η2L ).
Defining Gt = log ∥∥w′t,η − wtrain∥∥2 − t log(1 − η2L ), we know Gt is a super-martingale. Next, we bound the martingale differences.
We can bound |Gt − ESGD[Gt|w′t−1,η]| as follows,
|Gt − ESGD[Gt|w′t−1,η]| ≤ max n′t−1,η,n ′′ t−1,η log (∥∥(I − ηHtrain)(w′t−1,η − wtrain)− ηn′t−1,η∥∥2∥∥(I − ηHtrain)(w′t−1,η − wtrain)− ηn′′t−1,η∥∥2 )
We can expand ∥∥(I − ηHtrain)(w′t−1,η − wtrain)− ηn′t−1,η∥∥2 as follows,∥∥(I − ηHtrain)(w′t−1,η − wtrain)− ηn′t−1,η∥∥2
= ∥∥(I − ηHtrain)(w′t−1,η − wtrain)∥∥2 − 2η 〈n′t−1,η, (I − ηHtrain)(w′t−1,η − wtrain)〉+ η2 ∥∥n′t−1,η∥∥2
We can bound the norm of the noise as follows,∥∥n′t−1,η∥∥ = ∥∥∥xi(t−1)x>i(t−1)(w′t−1,η − wtrain)−Htrain(w′t−1,η − wtrain)∥∥∥ ≤ ∥∥∥xi(t−1)x>i(t−1)(w′t−1,η − wtrain)∥∥∥+ ∥∥Htrain(w′t−1,η − wtrain)∥∥ ≤ (Ld+ L)
∥∥w′t−1,η − wtrain∥∥ ≤ 2Ld∥∥w′t−1,η − wtrain∥∥ , where the second inequality uses
∥∥xi(t−1)∥∥ ≤ √Ld. Therefore, we have∣∣2η 〈n′t−1,η, (I − ηHtrain)(w′t−1,η − wtrain)〉∣∣ ≤ 4Lηd∥∥w′t−1,η − wtrain∥∥2 , η2 ∥∥n′t−1,η∥∥2 ≤ 4L2η2d2 ∥∥w′t−1,η − wtrain∥∥2 .
This further implies,
|Gt − ESGD[Gt|w′t−1,η]|
≤ log (∥∥(I − ηHtrain)(w′t−1,η − wtrain)∥∥2 + (4Lηd+ 4L2η2d2) ∥∥w′t−1,η − wtrain∥∥2∥∥(I − ηHtrain)(w′t−1,η − wtrain)∥∥2 − 4Lηd∥∥w′t−1,η − wtrain∥∥2 )
≤ log ( 1 + 8Lηd+ 4L2η2d2
(1− 2Lη − 4Lηd)
) ≤ 16Lηd+ 8L2η2d2,
where the second inequality uses ∥∥(I − ηHtrain)(w′t−1,η − wtrain)∥∥2 ≥ (1 −
2Lη) ∥∥w′t−1,η − wtrain∥∥2 . The last inequality assumes η ≤ 112Ld and uses numerical inequality log(1 + x) ≤ x. Assuming η ≤ 1/(Ld), we further have |Gt − ESGD[Gt|w′t−1,η]| ≤ L2ηd.
By Azuma’s inequality, we know with probability at least 1− δ/t,
Gt ≤ G0 + L2 √ 2tηd log(t/δ).
Plugging inGt = log ∥∥w′t,η − wtrain∥∥2−t log(1− η2L ) andG0 = log ‖w0 − wtrain‖2 = log ‖wtrain‖2 , we have
log ∥∥w′t,η − wtrain∥∥2 ≤ log ‖wtrain‖2 + t log(1− η2L ) + L2√2tηd log(t/δ)
≤ log ‖wtrain‖2 − η
2L t+ L2
√ 2tηd log(t/δ).
This implies, ∥∥w′t,η − wtrain∥∥2 ≤‖wtrain‖2 exp(η(− 12Lt+ L2√2 log(t/δ)d√t ))
= ‖wtrain‖2 exp ( O(d2 log2(d/δ))η ) ≤‖wtrain‖2 exp (2/3) ,
where the second inequality assumes η ≤ 1c5d2log2(d/δ) for some constant c5. Furthermore, since ‖wtrain‖ ≤ (1 + √ L)σ, we have ∥∥w′t,η∥∥ ≤ (1 + e1/3) ‖wtrain‖ < 4√Lσ. Overall, we know as long as η ≤ 1c5d2log2(d/δ) , with probability at least 1 − δ/t,
∥∥w′t,η∥∥ ≤ 4√Lσ. Since this analysis also applies to any τ ≤ t, we know for any τ, with probability at least 1 − δ/t,∥∥w′τ,η∥∥ < 4√Lσ. Taking a union bound over τ ≤ t, we have with probability at least 1 − δ,∥∥w′τ,η∥∥ < 4√Lσ for all τ ≤ t. Proof of Lemma 39. Let E be the event that
∥∥w′τ,η∥∥ < 4√Lσ for all τ ≤ t. We first show that ESGD ‖wt,η − w∗‖2 is close to ESGD
∥∥w′t,η − w∗∥∥2 1 {E}. It’s not hard to verify that ESGD ‖wt,η − w∗‖2 = ESGD ∥∥w′t,η − w∗∥∥2 1 {E}+ ‖u− w∗‖2 Pr[Ē ],
where u is a fixed vector with norm 4 √ Lσ. By Lemma 44, we know Pr[Ē ] ≤ /(25Lσ2) as long as η ≤ 1 c5d2 log2(d/ )
for some constant c5. Therefore, we have∣∣∣ESGD ‖wt,η − w∗‖2 − ESGD ∥∥w′t,η − w∗∥∥2 1 {E}∣∣∣ ≤ . Next, we show that ESGD
∥∥w′t,η − w∗∥∥2 1 {E} is close to ESGD ∥∥w′t,η − w∗∥∥2. For any 1 ≤ τ ≤ t, let Eτ be the event that
∥∥w′τ,η∥∥ ≥ 4√Lσ and ∥∥w′τ ′,η∥∥ < 4√Lσ for all τ ′ < τ. Basically Eτ means the weight norm exceeds the threshold at step τ for the first time. It’s easy to see that ∪tτ=1Eτ = Ē . Therefore, we have
ESGD ∥∥w′t,η − w∗∥∥2 = ESGD ∥∥w′t,η − w∗∥∥2 1 {E}+ t∑
τ=1
ESGD ∥∥w′t,η − w∗∥∥2 1 {Eτ} .
Conditioning on Eτ , we know ∥∥w′τ−1,η∥∥ < 4√Lσ. Since we assume √d√L ≤ σi(Xtrain) ≤ √L√d for
all i ∈ [n] and ξtrain ≤ √ dσ, we know ‖wtrain‖ ≤ 2 √ Lσ. Therefore, we have ∥∥w′τ−1,η − wtrain∥∥ ≤ 6 √ Lσ. Recall the SGD updates,
w′τ,η − wtrain = (I − ηHtrain)(w′τ−1,η − wtrain)− ηn′τ−1,η. For the noise term, we have η ∥∥n′τ−1,η∥∥ ≤ 2ηLd∥∥w′τ−1,η − wtrain∥∥ that is at most ∥∥w′τ−1,η − wtrain∥∥
assuming η ≤ 12Ld . Therefore, we have ∥∥w′τ,η − wtrain∥∥ ≤ 2 ∥∥w′τ−1,η − wtrain∥∥ ≤ 12√Lσ. Note that event Eτ is independent with the SGD noises after step τ . Therefore, according to the previous analysis, we know as long as η ≤ 12L3d ,
ESGD [∥∥w′t,η − wtrain∥∥2 |Eτ] ≤ ∥∥w′τ,η − wtrain∥∥2 ≤ 2L2σ2.
Then, we can bound ESGD [∥∥w′t,η − w∗∥∥2 |Eτ] as follows,
ESGD [∥∥w′t,η − w∗∥∥2 |Eτ]
=ESGD [∥∥w′t,η − wtrain + wtrain − w∗∥∥2 |Eτ]
≤ESGD [∥∥w′t,η − wtrain∥∥2 |Eτ]+ 2ESGD [∥∥w′t,η − wtrain∥∥ |Eτ ] ‖wtrain − w∗‖+ ‖wtrain − w∗‖2 ≤2L2σ2 + 2 · 2Lσ · 3 √ Lσ + 9Lσ2 ≤ 3L2σ2.
Therefore, we have t∑
τ=1
ESGD ∥∥w′t,η − w∗∥∥2 1 {Eτ} = t∑
τ=1
ESGD [∥∥w′t,η − w∗∥∥2 |Eτ]Pr[Eτ ]
≤3L2σ2 t∑
τ=1
Pr[Eτ ] = 3L2σ2 Pr[Ē ] ≤ 3L2σ2 .
This then implies that ∣∣∣ESGD ∥∥w′t,η − w∗∥∥2 − ESGD ∥∥w′t,η − w∗∥∥2 1 {E}∣∣∣ ≤ 3L2σ2 .
Finally, we have∣∣∣ESGD ‖wt,η − w∗‖2 − ESGD ∥∥w′t,η − w∗∥∥2∣∣∣ ≤ ∣∣∣ESGD ‖wt,η − w∗‖2 − ESGD ∥∥w′t,η − w∗∥∥2 1 {E}∣∣∣+ ∣∣∣ESGD ∥∥w′t,η − w∗∥∥2 − ESGD ∥∥w′t,η − w∗∥∥2 1 {E}∣∣∣ ≤ ( 3L2σ2 + 1 )
as long as η ≤ 1 c5d2 log2(d/ )
. Therefore, |Q(η)−Q′(η)| ≤ ( 3L2σ2 + 1 ) /2. Choosing ′ =
2 (3L2σ2+1) finishes the proof.
Proof of Lemma 40. Recall that
F̂TbV (η) := 1
m m∑ k=1 ∆TbV (η, P ) = 1 m m∑ k=1 ESGD 1 2 ∥∥∥w(k)t,η − w(k)valid∥∥∥2 H (k) valid .
Similar as in Lemma 11, we can show 12 ∥∥∥w(k)t,η − w(k)valid∥∥∥2
H (k) valid
isO(1)-subexponential, which implies ESGD 12 ∥∥∥w(k)t,η − w(k)valid∥∥∥2
H (k) valid
is O(1)-subexponential. Therefore, F̂TbV (η) is the average of m i.i.d.
O(1)-subexponential random variables. By standard concentration inequality, we know for any 1 > > 0, with probability at least 1− exp(−Ω( 2m)),∣∣∣F̂TbV (η)− FTbV (η)∣∣∣ ≤ .
Proof of Lemma 41. Recall that
FTbV (η) =EP∼T ESGD 1
2 ‖wt,η − w∗‖2 + σ2/2
We only need to construct an -net for EP∼T ESGD 12 ‖wt,η − w ∗‖2. Let E be the event that√
d/ √ L ≤ σi(Xtrain) ≤ √ Ld and 1/L ≤ λi(Htrain) ≤ L for all i ∈ [n] and √ dσ/4 ≤ ‖ξtrain‖ ≤√
dσ We have
EP∼T ESGD 1
2 ‖wt,η − w∗‖2 =EP∼T [ 1
2 ESGD ‖wt,η − w∗‖2 |E
] Pr[E ] + EP∼T [ 1
2 ESGD ‖wt,η − w∗‖2 |Ē
] Pr[Ē ]
According to Lemma 39, we know conditioning on E ,∣∣∣∣12ESGD ‖wt,η − w∗‖2 − 12ESGD ∥∥w′t,η − w∗∥∥2 ∣∣∣∣ ≤ ,
as long as η ≤ 1 c5d2 log2(d/ ) . Note {w′τ,η} is the SGD sequence without truncation.
For the second term, we have EP∼T [ 1
2 ESGD ‖wt,η − w∗‖2 |Ē
] Pr[Ē ] ≤ 13Lσ2 Pr[Ē ] ≤ ,
where the last inequality assumes Pr[Ē ] ≤ 13Lσ2 . According to Lemma 1 and Lemma 45, we know Pr[Ē ] ≤ exp(−Ω(d)). Therefore, given any > 0, we have Pr[Ē ] ≤ 13Lσ2 as long as d ≥ c4 log(1/ ) for some constant c4.
Then, we only need to construct an -net for EP∼T [ 1 2ESGD ∥∥w′t,η − w∗∥∥2 |E]Pr[E ].By the analysis in Lemma 33, it’s not hard to prove∣∣∣∣ ∂∂ηEP∼T [ 1 2 ESGD
∥∥w′t,η − w∗∥∥2 |E]Pr[E ]∣∣∣∣ = O(1)t(1− η2L )t−1, for all η ∈ [0, 1
c5d2 log2(d/ ) ]. Similar as in Lemma 14, for any > 0, we know there exists an -net
N with size O(1/ ) such that for any η ∈ [0, 1c5d2 log2(d/ ) ],∣∣∣∣EP∼T [12ESGD ∥∥w′t,η − w∗∥∥2 |E ] Pr[E ]− EP∼T [ 1 2 ESGD ∥∥w′t,η′ − w∗∥∥2 |E]Pr[E ]∣∣∣∣ ≤ for η′ ∈ arg minη∈N |η − η′|.
Combing with the bounds on ∣∣∣ 12ESGD ‖wt,η − w∗‖2 1 {E} − 12ESGD ∥∥w′t,η − w∗∥∥2 1 {E}∣∣∣ and
EP∼T [ 1 2ESGD ‖wt,η − w ∗‖2 |Ē ] Pr[Ē ], we have for any η ∈ [0, 1 c5d2 log2(d/ ) ],
FTbV (η)− FTbV (η′) ≤ 4
for η′ ∈ arg minη∈N |η − η′|. We finish the proof by replacing 4 by ′.
Proof of Lemma 42. The proof is very similar as the proof of Lemma 18. The only difference is that we need to 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.

heading: E TOOLS

heading: E.1 NORM OF RANDOM VECTORS
text: We use the following lemma to bound the noise in least squares model.
Lemma 45 (Theorem 3.1.1 in Vershynin (2018)). Let X = (X1, X2, · · · , Xn) ∈ Rn be a random vector with each entry independently sampled from N (0, 1). Then
Pr[ ∣∣‖x‖ − √n∣∣ ≥ t] ≤ 2 exp(−t2/C2),
where C is an absolute constant.

heading: E.2 SINGULAR VALUES OF GAUSSIAN MATRICES
text: Given a random Gaussian matrix, in expectation its smallest and largest singular value can be bounded as follows.
Lemma 46 (Theorem 5.32 in Vershynin (2010)). Let A be an N × n matrix whose entries are independent standard normal random variables. Then
√ N − √ n ≤ Esmin(A) ≤ Esmax(A) ≤ √ N + √ n
Lemma 47 shows a lipchitz function over i.i.d. 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 Rn with Lipschitz constant K. Let X be the standard normal random vector in Rn. Then for every t ≥ 0 one has
Pr[f(X)− Ef(X) ≥ t] ≤ exp(− t 2
2K2 ).
The following lemma shows a 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 is well conditioned in the least squares model.
Lemma 48 (Corollary 5.35 in Vershynin (2010)). Let A be an N × n matrix whose entries are independent standard normal random variables. Then for every t ≥ 0 with probability at least 1− 2 exp(−t2/2) one has
√ N − √ n− t ≤ smin(A) ≤ smax(A) ≤ √ N + √ n+ t

heading: E.3 JOHNSON-LINDENSTRAUSS LEMMA
text: We also use Johnson-Lindenstrauss Lemma in some of the lemmas. Johnson-Lindenstrauss Lemma tells us the projection of a fixed vector on a random subspace concentrates well as long as the subspace is reasonably large.
Lemma 49 (Johnson & Lindenstrauss (1984)). Let P be a projection in Rd onto a random ndimensional subspace uniformly distributed in Gd,n. Let z ∈ Rd be a fixed point and > 0, then with probability at least 1− 2 exp(−c 2n),
(1− ) √ n
d ‖z‖ ≤ ‖Pz‖ ≤ (1 + )
√ n
d ‖z‖ .

heading: F EXPERIMENT DETAILS
text: We describe the detailed settings of our experiments in Section F.1 and give more experimental results in Section F.2.

heading: F.1 EXPERIMENT SETTINGS
text: Optimizing step size for quadratic objective In this experiment, we meta-train a learning rate for gradient descent on a fixed quadratic objective. Our goal is to show that the autograd module in popular deep learning softwares, such as 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 metagradient (see Eqn 3) to compare the result.
A general setting for both implementations is as follows. The inner problem is fixed as a 20- dimensional quadratic objective as described in Section 3, and we use the log-transformed meta objective for training. The positive semi-definite matrix H is generated by first sampling a 20× 20 matrix X with all entries drawn from the standard normal distribution and then setting H = XTX . The initial point w0 is drawn from standard normal as well. Note that we use the same quadratic problem (i.e., the same H and w0) throughout the meta-training. We do 1000 meta-training iterations, and collect results for different settings of the initial learning rate η0 and the unroll length t.
We first implement the meta-training code with Tensorflow. Our code is 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 we 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 it 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 numerical issues. Specifically, we compute the meta-gradient using Eq (3), where we also scaled the numerator and denominator as described in Claim 2 to avoid numerical issues. We use the algorithm suggested in Theorem 4, except we choose the meta-step size to be 1/(100 √ k) as the constants in Theorem 4 were not optimized.
Train-by-train vs. train-by-validation, synthetic data In this experiment, we find the optimal learning rate η∗ for least-squares problems trained in train-by-train and train-by-validation settings and then see how the learning rate works on new tasks.
Specifically, we generate 300 different 1000-dimensional least-squares tasks with noise as 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 t is set as 40. We try different sample sizes and different noise levels for comparison. Subsequently, in order to test how the two η∗ (for trainby-train and train-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 η∗ found under the two meta-objective settings (regardless of how we find it), we do not need to actually do the meta-training. Instead, we do a grid search on the interval [10−6, 1], which is divided log-linearly to 25 candidate points. For both the train-by-train and train-by-validation settings, we average the meta-objectives over the 300 inner problems and see which η minimizes this averaged meta-objective.
Train-by-train vs. train-by-validation, MLP optimizer on MNIST To observe the trade-off between train-by-train and train-by-validation in a broader and more realistic case, we also do ex-
2Their open source code is available at https://github.com/tensorflow/models/tree/ master/research/learned_optimizer
periments to meta-train an MLP optimizer as in Metz et al. (2019) to solve the MNIST classification problem. We use part of their code 3 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 below), 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 magnitude. The update is computed as the direction times the exponential of the magnitude. The feature vector is 31-dimensional, which includes gradient, parameter value, first-order moving averages (5-dim), second-order 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 is tanh distortion of the current number of steps divided by 9 different scales (3, 10, 30, 100, 300, 1000, 3000, 10000, 300000). After expanding the 31-dimensional feature vector for each parameter, we also normalize the set of vectors dimension-wise across all the parameters to have mean 0 and standard deviation 1 (except for the step embedding part). More details can be found in their original paper and original implementation.
The inner-training problem is defined as using a two-layer fully connected network (i.e., another “MLP”) with ReLU activations to solve the classic MNIST 10-class classification problem. We use a 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 innertraining.
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 innertraining 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 inner-objectives (evaluated on the train/validation set for train-by-train/train-by-val) within that segment for a better convergence. We also do not need to log-transform the inner-objective this time because the cross entropy loss has a log operator itself. The meta-training, i.e. training the parameters of the MLP in the MLP optimzier, is completed using a classic RMSProp optimizer with meta learning rate 0.01.
For each settings of sample sizes and noise levels, we train two MLP optimizer: one for train-bytrain, and one for train-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 5 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.

heading: F.2 ADDITIONAL RESULTS
text: Optimizing step size for quadratic objective We try experiments for the same settings of the initial η0 and inner training length t for all of three implementations (our hand-derived GD version, Tensorflow GD version and the Tensorflow RMSProp version). We do 1000 meta-training steps for all the experiments.
For both Tensorflow versions, we always see infinite meta-objectives if η0 is large or t is large, whose meta-gradient is usually treated as zero, so the training get stuck and never converge. Even for the case that both η0 and t is small, it still has very large meta-objectives (the scale of a few hundreds), and that is why we also try RMSProp, which should be more robust against the gradient scales. Our
3Their code is available at https://github.com/google-research/google-research/ tree/master/task_specific_learned_opt
hand-derived version, however, does not have the numerical issues and can always converge to the optimal η∗. The detailed convergence is summarized in Tab 1 and Tab 2. Note that the optimal η∗ is usually around 0.03 under our settings.
Train-by-train vs. train-by-validation, MLP optimizer on MNIST We also do additional experiments on training an MLP optimizer on the MNIST classification problem. We first try using all samples under the 20% noised setting. The results are shown in Fig 8. The train-by-train setting can perform well if we have a 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-validation model.
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 as 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-byvalidation decreases. Also, when we condition on the same number of samples, having additional label noise always makes train-by-train model much worse compared to train-by-validation.

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

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.

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.