Learning Rate Annealing Can Provably Help Generalization,
Even for Convex Problems

Preetum Nakkiran
Harvard University¹¹1Part of this work completed while the author was interning at OpenAI.

Abstract

Learning rate schedule can significantly affect generalization performance in modern neural networks, but the reasons for this are not yet understood. Li et al., (2019) recently proved this behavior can exist in a simplified non-convex neural-network setting. In this note, we show that this phenomenon can exist even for convex learning problems – in particular, linear regression in 2 dimensions.

We give a toy convex problem where learning rate annealing (large initial learning rate, followed by small learning rate) can lead gradient descent to minima with provably better generalization than using a small learning rate throughout. In our case, this occurs due to a combination of the mismatch between the test and train loss landscapes, and early-stopping.

1 Introduction

The learning rate schedule of stochastic gradient descent is known to strongly affect the generalization of modern neural networks, in ways not explained by optimization considerations alone. In particular, training with a large initial learning-rate followed by a smaller annealed learning rate can vastly outperform training with the smaller learning rate throughout – even when allowing both to reach the same train loss. The recent work of Li et al., (2019) sheds some light on this, by showing a simplified neural-network setting in which this behavior provably occurs.

Refer to caption — (a) Small learning rate.

It may be conjectured that non-convexity is crucial for learning-rate schedule to affect generalization (for example, because strongly-convex objectives have unique global minima). However, we show this behavior can appear even in strongly-convex learning problems. The key insight is that although strongly-convex problems have a unique minima, early-stopping breaks this uniqueness: there is a set of minima with the same train loss $\varepsilon$ . And these minima can have different generalization properties when the train loss surface does not closely approximate the test loss surface. In our setting, a large learning-rate prevents gradient descent from optimizing along high-curvature directions, and thus effectively regularizes against directions that are high-curvature in the train set, but low-curvature on the true distribution (see Figure 1).

Technically, we model a small learning rate by considering gradient flow. Then we compare the following optimizers:

(A)

Gradient descent with an infinitesimally small step size (i.e. gradient flow).
(B)

Gradient descent with a large step size, followed by gradient flow.

We show that for a particular linear regression problem, if we run both (A) and (B) until reaching the same $\varepsilon>0$ train loss, then with probability $3/4$ over the train samples, the test loss of (A) is twice that of (B). That is, starting with a large learning rate and then annealing to an infinitesimally small one helps generalization significantly.

Our Contribution. We show that non-convexity is not required to reproduce an effect of learning rate on generalization that is observed in deep learning models. We give a simple model where the mechanisms behind this can be theoretically understood, which shares some features with deep learning models in practice. We hope such simple examples can yield insight and intuition that may eventually lead to a better understanding of the effect of learning rate in deep learning.

Organization. In Section 2 we describe the example. In Section 3 we discuss features of the example, and its potential implications (and non-implications) in deep learning. In Appendix A, we include formal proofs and provide a mild generalization of the example in Section 2.

1.1 Related Work

This work was inspired by Li et al., (2019), which gives a certain simplified neural-network setting in which learning-rate schedule provably affects generalization, despite performing identically with respect to optimization. The mechanisms and intuitions in Li et al., (2019) depend crucially on non-convexity of the objective. In contrast, in this work we provide complementary results, by showing that this behavior can occur even in convex models due to the interaction between early-stopping and estimation error. Our work is not incompatible with Li et al., (2019); indeed, the true mechanisms behind generalization in real neural networks may involve both of these factors (among others).

There are many empirical and theoretical works attempting to understand the effect of learning-rate in deep learning, which we briefly describe here. Several recent works study the effect of learning rate by considering properties (e.g. curvature) of the loss landscape, finding that different learning rate schedules can lead SGD to regions in parameter space with different local geometry Jastrzebski et al., (2020); Lewkowycz et al., (2020). This fits more broadly into a study of the implicit bias of SGD. For example, there is debate on whether generalization is connected to “sharpness” of the minima (e.g. Hochreiter and Schmidhuber, (1997); Keskar et al., (2016); Dinh et al., (2017)). The effect of learning-rate is also often also studied alongside the effect of batch-size, since the optimal choice of these two parameters is coupled in practice Krizhevsky, (2014); Goyal et al., (2017); Smith et al., (2017). Several works suggest that the stochasticity of SGD is crucial to the effect of learning-rate, in that different learning rates lead to different stochastic dynamics, with different generalization behavior Smith and Le, (2017); Mandt et al., (2017); Hoffer et al., (2017); McCandlish et al., (2018); Welling and Teh, (2011); Li et al., (2019). In particular, it may be the case that the stochasticity in the gradient estimates of SGD acts as an effective “regularizer” at high learning rates. This aspect is not explicitly present in our work, and is an interesting area for future theoretical and empirical study.

2 Convex Example

The main idea is illustrated in the following linear regression problem, as visualized in Figure 1. Consider the data distribution $\mathcal{D}$ over $(x,y)\in\mathbb{R}^{2}\times\mathbb{R}$ defined as:

x\in\{\vec{e_{1}},\vec{e_{2}}\}\text{ uniformly at random };\quad y=\langle\beta^{*},x\rangle

for some ground-truth $\beta^{*}\in\mathbb{R}^{2}$ . We want to learn a linear model $\hat{y}(x):=\langle\beta,x\rangle$ with small mean-squared-error on the population distribution. Specifically, for model parameters $\beta=(\beta_{1},\beta_{2})\in\mathbb{R}^{2}$ , the population loss is

L_{\mathcal{D}}(\beta):=\mathop{\mathbb{E}}_{x,y\sim D}[(\langle\beta,x\rangle-y)^{2}]

We want to approximate $\beta^{*}=\operatorname*{argmin}_{\beta}L_{\mathcal{D}}(\beta)$ . Suppose we try to find this minima by drawing $n$ samples $\{x_{i},y_{i}\}$ from $\mathcal{D}$ , and performing gradient descent on the empirical loss:

\hat{L}_{n}(\beta):=\frac{1}{n}\sum_{i\in[n]}(\langle\beta,x_{i}\rangle-y_{i})^{2}

starting at $\beta=0$ , and stopping when $\hat{L}_{n}\leq\varepsilon$ for some small $\varepsilon$ .

Now for simplicity let $n=3$ , and let the ground-truth model be $\beta^{*}=(\beta^{*}_{1},\beta^{*}_{2})\in\mathbb{R}^{2}$ . With probability $3/4$ , two of the samples will have the same value of $x$ – say this value is $x=\vec{e_{1}}$ , so the samples $(x_{i},y_{i})$ are $\{(e_{1},\beta^{*}_{1}),(e_{1},\beta^{*}_{1}),(e_{2},\beta^{*}_{2})\}$ . In this case the empirical loss is

\hat{L}_{n}(\beta)=\underbrace{\frac{2}{3}(\beta_{1}-\beta^{*}_{1})^{2}}_{\textrm{(A)}}+\underbrace{\frac{1}{3}(\beta_{2}-\beta^{*}_{2})^{2}}_{\textrm{(B)}}

(1)

which is distorted compared to the population loss, since we have few samples relative to the dimension. The population loss is:

L_{\mathcal{D}}(\beta)=\frac{1}{2}(\beta_{1}-\beta^{*}_{1})^{2}+\frac{1}{2}(\beta_{2}-\beta^{*}_{2})^{2}

(2)

The key point is that although the global minima of $L_{\mathcal{D}}$ and $\hat{L}_{n}$ are identical, their level sets are not: not all points of small train loss $\hat{L}_{n}(\beta)$ have identical test loss $L_{\mathcal{D}}(\beta)$ . To see this, refer to Equation 1, and consider two different ways that train loss $\hat{L}_{n}=\varepsilon$ could be achieved. In the “good” situation, term (A) in Equation 1 is $\varepsilon$ , and term (B) is $0$ . In the “bad” situation, term (A) is $0$ and term (B) is $\varepsilon$ . These two cases have test losses which differ by a factor of two, since terms are re-weighted differently in the test loss (Equation 2). This is summarized in the below table.

	Residual $(\beta-\beta^{*})$	Train Loss $\hat{L}_{n}(\beta)$	Test Loss $L_{\mathcal{D}}(\beta)$
Good:	$[\sqrt{\frac{3\varepsilon}{2}},0]$	$\varepsilon$	$0.75\varepsilon$
Bad:	$[0,\sqrt{3\varepsilon}]$	$\varepsilon$	$1.5\varepsilon$

Now, if our optimizer stops at train loss $\varepsilon$ , it will pick one of the points in $\{\beta:\hat{L}_{n}(\beta)=\varepsilon\}$ . We see from the above that some of these points are twice as bad as others.

Notice that gradient flow on $\hat{L}_{n}$ (Equation 1) will optimize twice as fast along the $\beta_{1}$ coordinate compared to $\beta_{2}$ . The gradient flow dynamics of the residual $(\beta-\beta^{*})$ are:

\frac{d\beta}{dt}=-\nabla_{\beta}\hat{L}_{n}\implies\begin{cases}\frac{d}{dt}(\beta_{1}-\beta_{1}^{*})=-\frac{4}{3}(\beta_{1}-\beta_{1}^{*})\\ \frac{d}{dt}(\beta_{2}-\beta_{2}^{*})=-\frac{2}{3}(\beta_{2}-\beta_{2}^{*})\end{cases}

This will tend to find solutions closer to the “Bad” solution from the above table, where $(\beta_{1}-\beta_{1}^{*})^{2}\approx 0$ and $(\beta_{2}-\beta_{2}^{*})^{2}\gg 0$ .

However, gradient descent with a large step size can oscillate on the $\beta_{1}$ coordinate, and achieve low train loss by optimizing $\beta_{2}$ instead. Then in the second stage, once the learning-rate is annealed, gradient descent will optimize on $\beta_{1}$ while keeping the $\beta_{2}$ coordinate small. This will lead to a minima closer to the “Good” solution, where $(\beta_{2}-\beta_{2}^{*})\approx 0$ . These dynamics are visualized in Figure 1.

This example is formalized in the following claim. The proof is straightforward, and included in Appendix A.

Claim 1.

For all $0<\alpha<1$ , there exists a distribution $\mathcal{D}$ over $(x,y)\in\mathbb{R}^{2}\times\mathbb{R}$ and a learning-rate $\eta>0$ (the “large” learning-rate) such that for all $0<\varepsilon<1$ , the following holds. With probability $3/4$ over $n=3$ samples:

1.

Gradient flow from $0$ -initialization, early-stopped at train loss $\varepsilon$ , achieves population loss

$L_{\mathcal{D}}(\beta_{\emph{bad}})\geq\frac{3}{2}\varepsilon(1-\alpha)$
2.

Annealed gradient descent from $0$ -initialization (i.e. gradient descent with stepsize $\eta$ for $K$ steps, followed by gradient flow) stopped at train loss $\varepsilon$ , achieves population loss

$L_{\mathcal{D}}(\beta_{\emph{good}})\leq\frac{3}{4}\varepsilon+\exp(-\Omega(K))$

In particular, since $\alpha$ can be taken arbitrarily small, and $K$ taken arbitrarily large, this implies that gradient flow achieves a population loss twice as high as gradient descent with a careful step size, followed by gradient flow.

Moreover, with the remaining $1/4$ probability, the samples will be such that gradient flow and annealed gradient descent behave identically:

\beta_{\emph{good}}=\beta_{\emph{bad}}

3 Discussion

Similarities. This example, though stylized, shares several features with deep neural networks in practice.

•

Neural nets trained with cross-entropy loss cannot be trained to global emperical risk minimas, and are instead early-stopped at some small value of train loss.
•

There is a mismatch between train and test loss landscapes (in deep learning, this is due to overparameterization/undersampling).
•

Learning rate annealing typically generalizes better than using a small constant learning rate Goodfellow et al., (2016).
•

The “large” learning rates used in practice are far larger than what optimization theory would prescribe. In particular, consecutive iterates of SGD are often negatively-correlated with each other in the later stage of training Xing et al., (2018), suggesting that the iterates are oscillating around a sharp valley. Jastrzebski et al., (2018) also finds that the typical SGD step is too large to optimize along the steepest directions of the loss.

Limitations. Our example is nevertheless a toy example, and does not exhibit some features of real networks. For example, our setting has only one basin of attraction. But real networks have many basins of attraction, and there is evidence that a high initial learning rate influences the choice of basin (e.g. Li et al., (2019); Jastrzebski et al., (2020)). It remains an important open question to understand the effect of learning rate in deep learning.

Acknowledgements

We thank John Schulman for a discussion around learning rates that led to wondering if this can occur in convex problems. We thank Aditya Ramesh, Ilya Sutskever, and Gal Kaplun for helpful comments on presentation, and Jacob Steinhardt for technical discussions refining these results.

Work supported in part by the Simons Investigator Awards of Boaz Barak and Madhu Sudan, and NSF Awards under grants CCF 1565264, CCF 1715187, and CNS 1618026.

References

Dinh et al., (2017) Dinh, L., Pascanu, R., Bengio, S., and Bengio, Y. (2017). Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 1019–1028. JMLR. org.
Goodfellow et al., (2016) Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep learning. MIT press.
Goyal et al., (2017) Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K. (2017). Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv:1706.02677.
Hochreiter and Schmidhuber, (1997) Hochreiter, S. and Schmidhuber, J. (1997). Long short-term memory. Neural computation, 9(8):1735–1780.
Hoffer et al., (2017) Hoffer, E., Hubara, I., and Soudry, D. (2017). Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In Advances in Neural Information Processing Systems, pages 1731–1741.
Jastrzebski et al., (2018) Jastrzebski, S., Kenton, Z., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. (2018). On the relation between the sharpest directions of dnn loss and the sgd step length. arXiv preprint arXiv:1807.05031.
Jastrzebski et al., (2020) Jastrzebski, S., Szymczak, M., Fort, S., Arpit, D., Tabor, J., Cho, K., and Geras, K. (2020). The break-even point on optimization trajectories of deep neural networks. arXiv preprint arXiv:2002.09572.
Keskar et al., (2016) Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. T. P. (2016). On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04836.
Krizhevsky, (2014) Krizhevsky, A. (2014). One weird trick for parallelizing convolutional neural networks. arXiv preprint arXiv:1404.5997.
Lewkowycz et al., (2020) Lewkowycz, A., Bahri, Y., Dyer, E., Sohl-Dickstein, J., and Gur-Ari, G. (2020). The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02218.
Li et al., (2019) Li, Y., Wei, C., and Ma, T. (2019). Towards explaining the regularization effect of initial large learning rate in training neural networks.
Mandt et al., (2017) Mandt, S., Hoffman, M. D., and Blei, D. M. (2017). Stochastic gradient descent as approximate bayesian inference. The Journal of Machine Learning Research, 18(1):4873–4907.
McCandlish et al., (2018) McCandlish, S., Kaplan, J., Amodei, D., and Team, O. D. (2018). An empirical model of large-batch training. arXiv preprint arXiv:1812.06162.
Smith et al., (2017) Smith, S. L., Kindermans, P.-J., Ying, C., and Le, Q. V. (2017). Don’t decay the learning rate, increase the batch size. arXiv preprint arXiv:1711.00489.
Smith and Le, (2017) Smith, S. L. and Le, Q. V. (2017). A bayesian perspective on generalization and stochastic gradient descent. arXiv preprint arXiv:1710.06451.
Welling and Teh, (2011) Welling, M. and Teh, Y. W. (2011). Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681–688.
Xing et al., (2018) Xing, C., Arpit, D., Tsirigotis, C., and Bengio, Y. (2018). A walk with sgd. arXiv preprint arXiv:1802.08770.

Appendix A Formal Statements

In this section, we state and prove Claim 1, along with a mild generalization of the setting via Lemma 1.

A.1 Notation and Preliminaries

For a distribution $\mathcal{D}$ over $(x,y)\in\mathbb{R}^{d}\times\mathbb{R}$ , let $L_{\mathcal{D}}(\beta):=\mathop{\mathbb{E}}_{x,y\sim D}[(\langle x,\beta\rangle-y)^{2}]$ be the population loss for parameters $\beta$ . Let $\hat{L}_{n}(\vec{\beta})=\frac{1}{n}\sum_{i}(\langle x_{i},\beta\rangle-y_{i})^{2}$ be the train loss for $n$ samples $\{(x_{i},y_{i})\}$ .

Let $GF_{\beta_{0}}(L,\varepsilon)$ be the function which optimizes train loss $L$ from initial point $\beta_{0}$ , until the train loss reaches early-stopping threshold $\varepsilon$ , and then outputs the resulting parameters.

Let $GD_{\beta_{0}}(L,K,\tau,\varepsilon)$ be the function which first optimizes train loss $L$ with gradient-descent starting at initial point $\beta_{0}$ , with step-size $\eta$ , for $K$ steps, and an early-stopping threshold $\varepsilon$ , and then continues with gradient flow with early-stopping threshold $\varepsilon$ .

For $n$ samples, let $X\in\mathbb{R}^{n\times d}$ be the design matrix of samples. Let $\Sigma_{X}=\mathop{\mathbb{E}}_{x,y\sim\mathcal{D}}[xx^{T}]$ be the population covariance and let $\hat{\Sigma}_{X}=\frac{1}{n}X^{T}X$ be the emperical covariance.

We assume throughout that $\Sigma_{X}$ and $\hat{\Sigma}_{X}$ are simultaneously diagonalizable:

\Sigma_{X}=U\Lambda U^{T}\quad;\quad\hat{\Sigma}_{X}=U\Gamma U^{T}

for diagonal $\Lambda=\textrm{diag}(\lambda_{i}),S=\textrm{diag}(\gamma_{i})$ and orthonormal $U$ . Further, assume without loss of generality that $\hat{\Sigma}_{X}\succ 0$ (if $\hat{\Sigma}_{X}$ is not full rank, we can restrict attention to its image).

We consider optimizing the the train loss:

\hat{L}(\beta)=\frac{1}{n}||X(\beta-\beta^{*})||_{2}^{2}=||\beta-\beta^{*}||^{2}_{\hat{\Sigma}_{X}}

Observe that the optimal population loss for a point with $\varepsilon$ train loss is:

\displaystyle\min_{\begin{subarray}{c}\text{s.t. }L_{\hat{\Sigma}}(\beta)=\varepsilon\end{subarray}}L_{\Sigma}(\beta)=\varepsilon\min_{i}(\{\frac{\lambda_{i}}{\gamma_{i}}\})

(3)

Similarly, the worst population loss for a point with $\varepsilon$ train loss is:

\displaystyle\max_{\begin{subarray}{c}\text{s.t. }L_{\hat{\Sigma}}(\beta)=\varepsilon\end{subarray}}L_{\Sigma}(\beta)=\varepsilon\max_{i}(\{\frac{\lambda_{i}}{\gamma_{i}}\})

(4)

Now, the gradient flow dynamics on the train loss is:

\displaystyle\frac{d\beta}{dt}=-\nabla_{\beta}\hat{L}(\beta)=-\frac{2}{n}X^{T}X(\beta-\beta^{*})

Switching to coordinates $\delta:=U^{T}(\beta-\beta^{*})$ , these dynamics are equivalent to:

\displaystyle\frac{d\delta}{dt}=-2\Gamma\delta

The empirical and population losses in these coordinates can be written as:

\displaystyle L_{\mathcal{D}}(\delta)=\sum_{i}\lambda_{i}\delta_{i}^{2}\quad;\quad\hat{L}(\delta)=\sum_{i}\gamma_{i}\delta_{i}^{2}

And the trajectory of gradient flow, from initialization $\delta(0)\in\mathbb{R}^{d}$ , is

\displaystyle~{}\forall i\in[d]:~{}~{}\delta_{i}(t)=\delta_{i}(0)e^{-2\gamma_{i}t}

With this setup, we now state and prove the following main lemma, characterizing the behavior of gradient flow and gradient descent for a given sample covariance.

A.2 Main Lemma

Lemma 1.

Let $\Sigma,\hat{\Sigma}\in\mathbb{R}^{d\times d}$ be as above. Let eigenvalues be ordered according to $\hat{\Sigma}$ : $\gamma_{1}\geq\gamma_{2}\geq\dots\geq\gamma_{d}$ .

Let $S=\{k,k+1,\dots,d\}$ for some $k$ . That is, let $S$ index a block of “small” eigenvalues. Let $\overline{S}=[n]\setminus S$ . Assume there is an eigenvalue gap between the “large” and “small” eigenvalues, where for some $p>0$

~{}\forall i\in\overline{S}:\gamma_{i}/\gamma_{k}\geq 1+p.

For all $0<\alpha<1$ , if the initialization $\delta(0)=U^{T}(\beta_{0}-\beta^{*})\in\mathbb{R}^{d}$ satisfies

1.

At initialization, the contribution of the largest eigenspace to the train loss is at least $\varepsilon$ :

$\gamma_{1}\delta_{1}(0)^{2}>\varepsilon$

The eigenvalue gap is large enough to ensure that eventually only the “small” eigenspace is significant, specifically:

\varepsilon^{p}\sum_{i\in\overline{S}}\frac{\gamma_{i}\delta_{i}(0)^{2}}{(|S|\gamma_{j^{*}}\delta_{j^{*}}(0)^{2})^{1+p}}\leq\alpha\quad\text{where }j^{*}:=\operatorname*{argmin}_{j\in S}\gamma_{j}\delta_{j}(0)^{2}

Then there exists a learning-rate $\eta:=1/\gamma_{1}$ (the “large” learning-rate) such that

1.

Gradient flow $\beta_{slow}\leftarrow GF_{\vec{\beta}_{0}}(\hat{L},\varepsilon)$ achieves population loss

$L_{\mathcal{D}}(\beta_{slow})\geq\varepsilon(1-\alpha)\min_{j\in S}\frac{\lambda_{j}}{\gamma_{j}}$

Annealed gradient descent run for $K$ steps $\beta_{fast}\leftarrow GD(\hat{L},K,\eta,\varepsilon)$ has loss

L_{\mathcal{D}}(\beta_{fast})\leq\varepsilon\max_{j:\gamma_{j}=\gamma_{1}}(\frac{\lambda_{j}}{\gamma_{j}})+\exp(-\Omega(K))

In particular, if the top eigenvalue of $\Gamma$ is unique, then

L_{\mathcal{D}}(\beta_{fast})\leq\varepsilon\frac{\lambda_{1}}{\gamma_{1}}+\exp(-\Omega(K))

The constant $\Omega(K)$ depends on the spectrum, and taking $\Omega(K)=-K\log(\max_{j:\gamma_{j}\neq\gamma_{1}}|1-2\gamma_{j}/\gamma_{1}|)$ suffices.

Proof.

Gradient Flow.

The proof idea is to show that gradient flow must run for some time $T$ in order to reach $\varepsilon$ train loss – and since higher-eigenvalues optimize faster, most of the train loss will be due to contributions from the “small” coordinates $S$ .

Let $T$ be the stopping-time of gradient flow, such that $\hat{L}(\delta(T))=\varepsilon$ . We can lower-bound the time $T$ required to reach $\varepsilon$ train loss as:

	$\displaystyle\|S\|\gamma_{j^{}}\delta_{j^{}}(0)^{2}e^{-4\gamma_{k}T}$	$\displaystyle\leq\sum_{j\in S}\gamma_{j}\delta_{j}(0)^{2}e^{-4\gamma_{j}T}\leq\sum_{j\in[n]}\gamma_{j}\delta_{j}(0)^{2}e^{-4\gamma_{j}T}=\hat{L}(\delta(T))=\varepsilon$		(5)
	$\displaystyle\implies T$	$\displaystyle\geq\frac{1}{4\gamma_{k}}\log(\frac{\|S\|\gamma_{j^{}}\delta_{j^{}}(0)^{2}}{\varepsilon})$		(6)

Decompose the train loss as:

\hat{L}(\delta)=\hat{L}_{\overline{S}}(\delta)+\hat{L}_{S}(\delta)

Where $\hat{L}_{S}(\delta):=\sum_{i\in S}\gamma_{i}\delta_{i}^{2}$ and $\hat{L}_{\overline{S}}(\delta):=\sum_{i\in\overline{S}}\gamma_{i}\delta_{i}^{2}$ . Now, we can bound $\hat{L}_{\overline{S}}(\delta(T))$ as:

$\displaystyle\hat{L}_{\overline{S}}(\delta(T))=\sum_{i\in\overline{S}}\gamma_{i}\delta_{i}(T)^{2}$	$\displaystyle=\sum_{i\in\overline{S}}\gamma_{i}\delta_{i}(0)^{2}e^{-4\gamma_{i}T}$
	$\displaystyle\leq\sum_{i\in\overline{S}}\gamma_{i}\delta_{i}(0)^{2}(\frac{\varepsilon}{\|S\|\gamma_{j^{}}\delta_{j^{}}(0)^{2}})^{\gamma_{i}/\gamma_{k}}$	(by Equation 6)
	$\displaystyle\leq\sum_{i\in\overline{S}}\gamma_{i}\delta_{i}(0)^{2}(\frac{\varepsilon}{\|S\|\gamma_{j^{}}\delta_{j^{}}(0)^{2}})^{1+p}$
	$\displaystyle\leq\alpha\varepsilon$

Where the last inequality is due to Condition 2 of the Lemma. Now, since $\hat{L}(\delta)=\hat{L}_{\overline{S}}(\delta)+\hat{L}_{S}(\delta)$ , and $\hat{L}(\delta(T))=\varepsilon$ , and $\hat{L}_{\overline{S}}(\delta(T))\leq\alpha\varepsilon$ , we must have

\hat{L}_{S}(\delta(T))\geq(1-\alpha)\varepsilon

This lower-bounds the population loss as desired.

\displaystyle L_{\mathcal{D}}(\delta(T))

\displaystyle\geq\sum_{i\in S}\lambda_{i}\delta_{i}(T)^{2}\geq\min_{j\in S}(\frac{\lambda_{j}}{\gamma_{j}})\sum_{i\in S}\gamma_{i}\delta_{i}(T)^{2}=\min_{j\in S}(\frac{\lambda_{j}}{\gamma_{j}})\hat{L}_{S}(\delta(T))\geq\min_{j\in S}(\frac{\lambda_{j}}{\gamma_{j}})(1-\alpha)\varepsilon

Annealed Gradient Descent.

For annealed gradient descent, the proof idea is: set the learning-rate such that in the gradient descent stage, the optimizer oscillates on the first (highest-curvature) coordinate $\delta_{1}$ , and optimizes until the remaining coordinates are $\approx 0$ . Then, in the gradient flow stage, it optimizes on the first coordinate until hitting the target train loss of $\varepsilon$ . Thus, at completion most of the train loss will be due to contributions from the “large” first coordinate.

Specifically, the gradient descent dynamics with stepsize $\eta$ is:

\delta_{i}(t+1)=(1-2\eta\gamma_{i})\delta_{i}(t)

for discrete $t\in\mathbb{N}$ . We set $\eta:=1/\gamma_{1}$ , so the first coordinate simply oscillates: $\delta_{1}(t+1)=-\delta_{1}(t)$ . This is the case for the top eigenspace, i.e. all coordinates $i$ where $\gamma_{i}=\gamma_{1}$ . The remaining coordinates decay exponentially. That is, let $Q:=\{i:\gamma_{i}\neq\gamma_{1}\}$ be the remaining coordinates (corresponding to smaller eigenspaces). Then we have:

~{}\forall i\in Q:~{}\delta_{i}(t)^{2}\leq c^{-t}\delta_{i}(0)^{2}

(7)

for constant $c=\max_{j:\gamma_{j}\neq\gamma_{1}}|1-2\eta\gamma_{j}|^{2}<1$ .

Recall, the population and empirical losses are:

\displaystyle L_{\mathcal{D}}(\delta)=\sum_{i}\lambda_{i}\delta_{i}^{2}\quad;\quad\hat{L}(\delta)=\sum_{i}\gamma_{i}\delta_{i}^{2}

By Equation 7, after $K$ steps of gradient descent, the contribution to the population loss from the coordinates $i\in Q$ is small:

\sum_{i\in Q}\lambda_{i}\delta_{i}(K)^{2}\leq\exp(-\Omega_{c}(K))

By Condition 1 of the Lemma, the train loss is still not below $\varepsilon$ after the gradient descent stage, since the first coordinate did not optimize: $\delta_{1}(0)=\pm\delta_{1}(0)$ . We now run gradient flow, stopping at time $T\in\mathbb{R}$ when the train loss is $\varepsilon$ . At this point, we have

\hat{L}(\delta(T))\leq\varepsilon\implies\sum_{i\not\in Q}\gamma_{i}\delta_{i}(T)^{2}\leq\varepsilon

And thus,

	$\displaystyle L_{\mathcal{D}}(\delta(T))$	$\displaystyle=\sum_{i\not\in Q}\lambda_{i}\delta_{i}(T)^{2}+\sum_{i\in Q}\lambda_{i}\delta_{i}(T)^{2}$
		$\displaystyle\leq(\max_{k\not\in Q}\frac{\lambda_{k}}{\gamma_{k}})\sum_{i\not\in Q}\gamma_{i}\delta_{i}(T)^{2}+\exp(-\Omega(K))$
		$\displaystyle\leq(\max_{k\not\in Q}\frac{\lambda_{k}}{\gamma_{k}})\varepsilon+\exp(-\Omega(K))$

as desired. ∎

As a corollary of Lemma 1, we recover the 2-dimensional of Claim 1.

A.3 Proof of Claim 1

Proof sketch of Claim 1.

Consider the distribution $\mathcal{D}$ defined as: Sample $x\in\{\vec{e_{1}},\vec{e_{2}}\}$ uniformly at random, and let $y=\langle\beta^{*},x\rangle$ for ground-truth $\beta^{*}=(100\alpha^{-1/2},100\alpha^{-1/2})$ . The population covariance is simply

\Sigma_{X}=\begin{bmatrix}1/2&0\\ 0&1/2\end{bmatrix}

With probability $3/4$ , two of the three samples will have the same value of $x$ . In this case, the sample covariance will be equal (up to reordering of coordinates) to

\hat{\Sigma}_{X}=\begin{bmatrix}2/3&0\\ 0&1/3\end{bmatrix}

This satisfies the conditions of Lemma 1, taking the “small” set of eigenvalue indices to be $S=\{2\}$ . Thus, the conclusion follows by Lemma 1.

With probability $1/4$ , all the samples will all be identical, and in particular share the same value of $x$ . Here, the optimization trajectory will be 1-dimensional, and it is easy to see that gradient flow and annealed gradient descent will reach identical minima. ∎

Learning Rate Annealing Can Provably Help Generalization, Even for Convex Problems