# Corridor Geometry in Gradient-Based Optimization

Benoit Dherin∗
Google
<EMAIL_ADDRESS>Mihaela Rosca∗
Google DeepMind, London
<EMAIL_ADDRESS>
###### Abstract

We characterize regions of a loss surface as corridors when the continuous
curves of steepest descent—the solutions of the gradient flow—become straight
lines. We show that corridors provide insights into gradient-based
optimization, since corridors are exactly the regions where gradient descent
and the gradient flow follow the same trajectory,  while the loss decreases
linearly. As a result, inside corridors there are no implicit regularization
effects or training instabilities that have been shown to occur due to the
drift between gradient descent and the gradient flow.  Using the loss linear
decrease on corridors, we devise a learning rate adaptation scheme for
gradient descent; we call this scheme Corridor Learning Rate (CLR). The CLR
formulation coincides with a special case of Polyak step-size, discovered in
the context of convex optimization. The Polyak step-size has been shown
recently to have also good convergence properties for neural networks; we
further confirm this here with results on CIFAR-10 and ImageNet.

**footnotetext: Equal contribution

##  1 Introduction

In recent years, a fruitful approach to understanding optimization in deep
learning has come from studying the discrepancy between gradient descent
(GD)—at the basis for most modern deep learning optimizers—and its continuous-
time counterpart, the gradient flow (GF). On one hand, the discrepancy between
GD and the GF has been used to find sources of implicit regularization and
training instabilities [11, 33, 2, 32, 10, 20, 24, 28, 29, 30] and with it
novel insights into the effect of learning rates, batch sizes, and neural
landscapes. On the other hand, it has been empirically observed that there are
regions in neural network training where GD closely follows the GF [6, 30, 9],
with a theoretical bound between the trajectory of GD and the GF constructed
by Elkabetz and Cohen [9]. Taken together, these results showcase the
importance of understanding the conditions of the loss landscape under which
GD and the GF follow the same trajectory, which can unlock when implicit
regularization and training instabilities are expected to occur. To this end,
Rosca et al. [30] find a sufficient condition based on the loss gradient and
Hessian for when GD follows the GF exactly.

Our main contribution is to add to this body of work, by characterizing the
local geometry of regions where the trajectories of GD coincide with those of
the GF for general loss surfaces. Geometrically, we find that these regions
exactly coincide with regions where the solutions of the GF become straight
lines, regions we call corridors. We show that a necessary and sufficient
condition for a region to be a corridor is that the image $Hg$ of loss
gradient $g$ by the loss Hessian $H$ vanishes. Although exact corridors (i.e.
where $Hg$ is exactly zero) may not exist on neural loss landscapes, we
believe that understanding corridors can provide an insight into optimization
and implicit regularization in deep learning, especially in regions where $Hg$
is small (as opposed to zero). Based on the assumption that the loss landscape
is a corridor, we devise a learning rate adaptation scheme for GD, which we
call the Corridor Learning Rate (CLR); inside corridors, the CLR converges to
the optimum in one step. Outside exact corridors, we find empirically that CLR
converges on multiple datasets (CIFAR-10 [19] and Imagenet [8]) and multiple
neural network architectures.  Perhaps surprisingly, the CLR coincides with a
special case of Polyak step-size for GD, introduced by Polyak [27] as optimal
in the non-smooth convex case. The Polyak step-size has been shown to also be
optimal in other convex settings (e.g. smooth and strongly convex) by Hazan
and Kakade [13]. Recently, a stochastic variant of the Polyak step-size has
been used in the context of neural optimization where, under mild assumptions,
theoretical convergence guaranties have been obtained by Loizou et al. [21];
the authors observe fast convergence on MNIST [1], CIFAR-10 [19], CIFAR-100
[19], for the ResNet [14] and DenseNet [16] architectures as well as for
matrix factorization. Our experiments support their evidence on efficiency of
this learning rate formulation in neural network training. We note that the
CLR is not the focus of this work, nor do we aim to make it competitive with
existing approaches as in Orvieto et al. [25]: our aim is to explore the
notion of corridor and demonstrate its usefulness in the context of deep
learning.

##  2 Corridors

In this section, we define the geometrical notion of corridor, provide an
equivalent analytic criterion for corridors, and show that corridors coincide
with regions where GD and the GF follow the same trajectory. Our results are
valid for twice differentiable loss functions
$E:\mathbb{R}^{n}\rightarrow\mathbb{R}$. We denote by $g(\theta)=\nabla
E(\theta)$ the loss gradient and its Hessian by $H(\theta)=\nabla\nabla
E(\theta)$. In deep learning $\theta$ denotes the parameter of a neural
network, and $E(\theta)$ denotes a measure of discrepancy between neural
network predictions and the ground truth averaged over all the examples in the
training set. With our notation, the GF differential equation becomes
$\dot{\theta}=-g(\theta).$ Its solutions $\theta(t)$ are given by the unique
curves of continuous steepest descent.

######  Definition 2.1.

We define a corridor as a domain $U\subset\mathbb{R}^{n}$ of a loss surface
with loss $E:\mathbb{R}^{n}\rightarrow\mathbb{R}$ iff the solutions of the GF
(i.e., the curves $\theta(t)$ satisfying $\dot{\theta}(t)=-g(\theta(t))$ are
straight lines  traveled at constant speed on $U$, (i.e.,
$\theta(t)=\theta(0)+tv$ for a velocity vector $v$). Inside corridors, we thus
refer to the GF solutions as the lines of steepest descent.

The main theorem in this section states that a subset $U$ is a corridors if
and only if ${H(\theta)g(\theta)=0,\forall\theta\in U}$ (Theorem 2.11). We
first start with a few corridor examples, to provide an intuition about what
they are and we motivate our main theorem by observing that $Hg=0$ for all
these examples.

###  2.1 Examples of corridors

######  Example 2.2.

(Linear pieces.) In dimension one, only linear pieces are corridors. To see
why, consider the loss $E:\mathbb{R}\rightarrow\mathbb{R}$, and $\theta(t)$
the solution of the GF i.e., $\dot{\theta}=-\nabla E(\theta)$. Consider the
time interval $[0,T]$ under which $E$ is a corridor; we show that $\nabla
E(\theta)$ is constant in that interval. By the corridor assumption, we have
that $\theta(t)=\theta(0)+tv,$ satisfies the GF equation for a certain $v$,
which implies that $\nabla E(\theta(t))$ is constant (equals to $v$) for all
$t\in[0,T]$, and thus $E$ is linear in $[\theta(0),\theta(T)]$. Since for a
linear function, its Hessian vanishes, we have that $Hg=0$ on the corridor.

######  Example 2.3.

(Convex n-dimensional cones.) The loss
$E:\mathbb{R}^{d}\rightarrow\mathbb{R}$, $E(\theta)=\alpha\|\theta\|$ (where
$\|\cdot\|$ is the $l_{2}$ norm) has no linear piece, but it is a corridor.
This corridor can be described as the collection of half-lines passing through
a point in the circle
${C=\\{(\theta,1):\>\|\theta\|^{2}=1/\alpha^{2}\\}\subset\mathbb{R}_{\theta}\times\mathbb{R}}$
and stopping at the origin $(0,0)$. The projection of these lines on the
parameter plane $\mathbb{R}_{\theta}$ are the lines of steepest descent and
the solutions of the GF. The $n$-dimensional cone is a convex surface with a
single global minima. Note that the gradient of $E(\theta)=\alpha\|\theta\|$
is $g=\alpha\frac{\theta}{\|\theta\|}$, and its Hessian is
$H=\alpha(\frac{1}{\|\theta\|}-\frac{\theta\theta^{T}}{\|\theta\|^{3}})$ and
thus $Hg=0$, except at the origin.

######  Example 2.4.

(Concave n-dimensional Cones.) Turning the previous example on its head, we
obtain the concave n-dimensional cone with loss function
$E(\theta)=\beta-\alpha\|\theta\|_{2}$. A similar computation shows that
$Hg=0$, except at the origin.

######  Example 2.5.

(Ruled-surfaces.) Both the 2-dimensional convex and concave cones are examples
of _ruled-surfaces_ [34], which are surfaces defined by the property that
there is always a line lying on the surface through each of its points as in
Figure 1a. As Proposition 2.10 below shows, in $\mathbb{R}^{2}$, if a region
is a corridor then it is ruled-surface (the converse being not necessarily
true) allowing for much more complicated shapes than just linear pieces.

######  Example 2.6.

(Multiple corridors). The previous examples were examples of loss surfaces
entirely formed by a single corridor. We can glue corridors together to obtain
fairly complicated loss surfaces with a hierarchical structure. Figure 1b
displays such an example, where wavy convex and concave cones are glued to
pieces of ruled-surfaces and linear pieces. Note that $Hg=0$ holds almost
everywhere except on a set measure null, corresponding to the gluing lines,
where the loss is possibly not differentiable. This example is non-convex (and
non-smooth at the gluing lines).

######  Example 2.7.

(Quadratic Counter-example.) Quadratic losses do not possess corridors. For
instance, the solutions of the GF for the loss $E(\theta)=\theta^{2}/2$ are
lines toward the origin $\theta(t)=\theta e^{-t}$, but are travelled at non-
constant speed $\dot{\theta}(t)=\theta e^{-t}$. Note that $Hg=\theta$ does not
vanish, except a $0$. See Appendix C for a proof that quadratic functions in
higher dimensions do not possess corridors.

(a) Individual corridors.

(b) Loss surface formed from multiple corridors.

Figure 1:  Visualizing corridors. LABEL:sub@fig:individual_corridors: Ruled
surfaces forming a corridor, with example lines of steepest descent.
LABEL:sub@fig:multiple_corridors: A line of steepest descent (shown in red)
formed on a loss surface constructed from multiple corridors.

###  2.2 Characterizing corridors: a necessary and sufficient condition

Theorem 2.11 below gives an analytical characterization of corridors in terms
of the Hessian. Before stating it, let us start with two lemmas:

######  Lemma 2.8.

Suppose that $\theta(t)$ is a solution of $\dot{\theta}=-g(\theta)$. Then
$-Hg$ measures the rate of change of the loss gradient under the GF:

$\frac{d}{dt}g(\theta(t))=-H(\theta(t))g(\theta(t)).$ (1)

The proof follows immediately from the chain rule

$\frac{d}{dt}g(\theta(t))=\nabla_{\theta}g(\theta(t))\dot{\theta}(t)=-H(\theta(t))g(\theta(t)).$

######  Lemma 2.9.

Inside corridors, GF solutions are of the form $\theta(t)=\theta-tg(\theta)$
and the loss gradient is constant on this line: $g(\theta-
tg(\theta))=g(\theta)$ for all $t$ as long as the line remains a solution.

###### Proof.

By Def. 2.1, solutions to the GF inside a corridor are of the form
$\theta(t)=a+tb$. Setting $t=0$ implies that $a=\theta(0)$. We also have that
inside a corridor $\dot{\theta}(t)=b$, and thus
$b=-g(\theta(t))=-g(\theta(0)+tb)$. So $g$ is constant on $\theta(t)$ and we
obtain that $b=-g(\theta(0))$ by setting $t=0$. ∎

The next proposition shows that the loss decreases linearly on a line of
steepest descent within a corridor; moreover, the trajectories followed on the
loss surface when the parameter follows a line of steepest descent is itself a
line:

######  Proposition 2.10.

On a corridor $U\subset\mathbb{R}^{n}$ the loss decreases linearly under the
GF. More precisely, on the line of steepest descent through $\theta$, i.e.,
$\theta(t)=\theta-tg(\theta)$, we have that
${E(\theta(t))=E(\theta)-t\|g(\theta)\|^{2}}$. Moreover, the line of steepest
descent lifts to a line through $\theta$ on the loss surface:
${t\mapsto\left(\theta-g(\theta)t,\,E(\theta)-t\|g(\theta)\|^{2}\right)}$.

###### Proof.

By the chain rule we have that the loss under the GF satisfies the following
differential equation
$\frac{d}{dt}E(\theta(t))=\nabla_{\theta}E(\theta)\dot{\theta}(t)=-\|g(\theta(t))\|^{2}$.
Since inside a corridor the gradient is constant along the solution of the GF
and equal to $g(\theta)$, we can thus solve this equation and we obtain that
$E(\theta(t))=E(\theta)-t\|g(\theta)\|^{2}$. The last part of the proposition
then follows by the definition of the loss surface as the set of points
$\\{(\theta,\,E(\theta)):\>\theta\in\mathbb{R}^{n}\\}$. ∎

We now give an analytical characterisation of corridors in terms of the
Hessian.

######  Theorem 2.11.

Let $E:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a twice differentiable loss
function and $U\subset\mathbb{R}^{n}$ be a domain of the parameter space. Then
$U$ is a corridor if and only if $H(\theta)g(\theta)=0$ for all $\theta\in U$.

###### Proof.

In a corridor $U$, $g$ is constant on the lines $\theta(t)$ of steepest
descent by Lemma 2.9, and thus
$\frac{d}{dt}g(\theta(t))=-H(\theta(t))g(\theta(t))=0$ by Lemma 2.8. Since
this holds for all $\theta(0)\in U$, this implies $H(\theta)g(\theta)=0$ on
$U$. Conversely, if $H(\theta)g(\theta)=0,\forall\theta\in U$, we have that

$\frac{d}{dt}g(\theta(t))=-H(\theta(t))g(\theta(t))=0,$

which implies that $g(\theta(t))=g(\theta(0))$ and the GF ODE on corridors
becomes $\dot{\theta}=-g(\theta(0))$. This last equation is easy to solve:

$\theta(t)=\theta(0)+\int_{0}^{t}-g(\theta(t^{\prime}))dt^{\prime}=\theta(0)-tg(\theta_{0}),$

entailing that the GF solution is a straight line and we are thus in a
corridor. ∎

##  3 Corridors are important for optimization

We now show that corridors are the only regions where GD steps on the GF. In
Appendix A, we show that inside corridors Runge-Kutta4 [12] and momentum [26]
also follow the GF trajectory.

######  Theorem 3.1.

Let $E:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a twice differentiable loss
function and $U\subset\mathbb{R}^{n}$ be a domain of the parameter space. Then
$U$ is a corridor if and only if the GD iterates $\theta_{n}$ step on the
solution $\theta(t)$ of the GF: $\theta(nh)=\theta_{n}$.

###### Proof.

In a corridor, we prove by induction that $\theta_{n}=\theta(nh)$, where
$\theta(t)=\theta_{0}-tg(\theta_{0})$ is the line of steepest descent through
$\theta_{0}$ from Lemma 2.9. We obtain the base case by definition of GD:
$\theta_{1}=\theta_{0}-hg(\theta_{0})=\theta(h)$. Now suppose by induction
that we have $\theta_{n}=\theta(nh)$. This implies that
$\theta_{n+1}=\theta(nh)-hg(\theta(nh))=\theta_{0}-nhg(\theta_{0})-hg(\theta_{0})=\theta((n+1)h)$,
where we used that $g(\theta_{0}-nhg(\theta_{0}))=g(\theta_{0})$ according to
Lemma 2.9.

Conversely, we assume that $\theta_{n}=\theta(nh)$ for all initial conditions
$\theta\in U$ and all learning rates $h$ as long as we remain on $U$. By
setting $n=1$, we obtain that the solution of the GF through $\theta$ becomes
$\theta(h)=\theta_{1}=\theta-hg(\theta)$. The Taylor expansion of the GF
solution with initial condition $\theta$ is

$\theta(h)=\theta-h\theta^{\prime}+\frac{h^{2}}{2}\theta^{\prime\prime}+\mathcal{O}(h^{3})=\theta-
hg(\theta)-\frac{h^{2}}{2}\frac{d}{dt}g(\theta)+\mathcal{O}(h^{3})=\theta-
hg(\theta)+\frac{h^{2}}{2}H(\theta)g(\theta)+\mathcal{O}(h^{3}),$

where the first equality comes from the definition of the GF, and the second
one from Lemma 2.8. From here, we have that $H(\theta)g(\theta)=0$, and thus
we are inside a corridor by Theorem 2.11. ∎

Theorem 3.1 shows that GD and the GF follow the same trajectory if and only if
the landscape is a corridor. This entails that as long as a corridor is not
exited, GD exactly minimizes the loss function $E$,  which decreases linearly
(Proposition 2.10), and implicit regularization effects found due to the
discrepancy between GD and the GF such as Implicit Gradient Regularization [2]
have no effect.

While inside corridors GD follows the GF exactly, this is not the case for
Stochastic Gradient Descent (SGD), where a different data batch $B$ is used at
each iteration. The batch gradient $g_{B}$ can be rewritten as
$g_{B}=g+\epsilon_{B}$ where $g$ denotes the full batch gradient, and the
residual $\epsilon_{B}$ is due to the noise induced by the sampling of batch
$B$. Despite being inside a corridor, SGD will not follow the GD trajectory
exactly, since $\theta(h)=\theta-hg(\theta)\neq\theta-hg_{B}(\theta)=\theta-
hg(\theta)-h\epsilon_{B}$. Thus, as the batch size decreases and the learning
rate increases, implicit regularization will occur for SGD inside corridors.
In Appendix A.3, we quantify this further based on results on implicit
regularization for SGD from Smith et al. [32]: we show that while the gradient
norm implicit regularizer vanishes inside corridors, the per batch consistency
implicit regularizer remains.

We show that Runge-Kutta4 as well as GD with momentum also slide on the lines
of steepest descent (i.e. the solutions of the GF) in a corridor in the
Appendix. For Runge-Kutta4, the discrete steps exactly follow GF solutions
inside a corridor (Appendix A.2). For momentum, we show in Appendix A.1 that
if the momentum iterates enter a corridor with velocity zero or one aligned
with the initial corridor gradient, momentum will follow the lines of steepest
descent, but at a different speed than the GF. For momentum with zero initial
velocity, we recover the ODE describing momentum found by Ghosh et al. [10]
and Cattaneo et al. [4], but the implicit regularization term vanishes, like
for GD. Outside of these conditions, however, momentum may drift from the GF,
creating theoretical conditions for implicit regularization. These results
suggests the importance of understanding corridors for optimization; we turn
our attention to this in the next section.

##  4 Corridor learning rate adaptation

We devise a simple learning rate adaptation for GD based on the idea of
corridors.  We assume that a point $\theta$ is in a corridor of the loss
surface; as shown in Theorem 3.1, the gradient iterates starting at $\theta$
coincide with the line of steepest descent $\theta(h)=\theta-hg(\theta)$ on
the corridor. Moreover, by Proposition 2.10, the loss on this steepest descent
line decreases linearly as $E(\theta(h))=E(\theta)-h\|g(\theta)\|^{2}$.
Assuming the minimal value of the loss function is $E(\theta^{*})$ is 0, which
holds for common losses used in deep learning with models with sufficient
capacity,  and solving for $h$ in order to obtain the step size that allows us
to reach that optimal value in one step whilst in a corridor, we obtain:

$\displaystyle E(\theta)-h\|g(\theta)\|^{2}=0,$ (2)

which if solved for $h$ gives the Corridor Learning Rate (CLR) and
corresponding gradient update:

$h(\theta)=\frac{E(\theta)}{\|g(\theta)\|^{2}},\quad\quad\theta^{\prime}=\theta-\frac{E(\theta)}{\|g(\theta)\|^{2}}g(\theta),$
(3)

###  4.1 Connection to Polyak step size

The CLR is connected to the Polyak step size [27] for GD, where the learning
rate is set to $h=\frac{E(\theta)-E(\theta^{\textbf{}}*)}{\|g(\theta)\|^{2}}$
and $E(\theta^{*})$ is the loss function at the optimum. Thus, if
$E(\theta^{*})=0$ (as is the case for over-parameterized neural networks), the
CLR recovers the Polyak step size. Polyak [27] argues that this step size is
optimal when $E$ is non-smooth and convex. This optimality result has been
extended to various additional convex settings by Hazan and Kakade [13] in
particular to $\beta$-smooth and strongly convex functions. They further
provide an algorithm which does not require knowledge of $E(\theta^{*})$, but
only a lower bound on $E(\theta^{*})$; assuming the lower bound is $0$, the
learning rate used is $h=\frac{E(\theta)}{2\|g(\theta)\|^{2}}$, differing from
the CLT by a multiplier of $1/2$.

Beyond the convex case, Loizou et al. [21] adapted the Polyak step-size to the
stochastic setting and analysed convergence properties in a number of smooth
cases, and in particular: 1) The Polyak-Lojasiewicz (PL) condition, which in
the over parameterized regime assumes that the adaptive step-size
$E(\theta)/\|\nabla E(\theta)\|^{2}$ is bounded, and 2) a condition on the
gradient $\mathbb{E}(\|\nabla E_{B}(\theta)\|^{2})\leq\rho\|\nabla
E(\theta)\|^{2}+\delta$ for some $\rho,\delta\geq 0$ and where $E_{B}$ is the
batch loss; the latter condition has been previously studied by Bottou et al.
[3]. Loizou et al. [21] find theoretical convergence guarantees in both cases:
namely to an exact minimizer in case 1) and to a neighborhood of the global
minima in case 2), provided some modifications such as clipping the step-size
for too large values and multiplying it by a constant factor as an additional
hyper-parameter. Orvieto et al. [25] considered further variations guarantying
convergence to an exact minimizer in the same setting.

The CLT and Polyak assumptions: The CLT is derived by assuming the loss
landscape is a corridor, and then solving the learning rate that reaches the
optimum loss value of $0$ in one step. In contrast, the initial formulation of
the Polyak learning rate is derived assuming a convex loss function. We note
that the set of convex functions and corridors have non null differences;
Example 2.7 has shown that quadratic functions do not allow corridors, while
Example 2.4 has shown a concave function that is a corridor. The more recent
use of the Polyak learning rate, such as that of Loizou et al. [21] in the
non-convex case, employs other assumptions, such as the PL condition. The PL
condition is a broad condition, which holds for large parts of neural network
landscapes; this can be further observed by the fact that the PL condition is
equivalent to assuming that the Polyak step-size is finite, and the Polyak
step-size has been used successfully to train neural networks. While corridors
are not likely to cover entire neural network landscapes due edge of stability
results [6, 23], it has been observed that GF follows GD early in neural
network training [6, 30]. Furthermore, the understanding of corridors in
neural networks is relevant from an implicit regularisation point of view, as
implicit regularisation derived from the discretization error of gradient
descent will not be present in corridors.

###  4.2 Empirical evidence from deep learning

While the landscape of neural networks is not formed by corridors only (since
then phenomena such as the edge of stability [6] would not occur), there has
been empirical evidence that regions where GD coincides with the GF occur in
network training [6, 29].  Namely, for convergent learning rates, one observes
that GF follows GD before the edge of stability phenomenon happens [6, 30],
making corridors a possibly useful notion to understand the geometry of these
regions (see Theorem 3.1). As discussed in the previous section, the CLR
coincides the Polyak step-size, which has already been shown to be a fast and
effective scheme in deep learning. In particular, Loizou et al. [21] observe
fast convergence for deep matrix factorization, multiple datasets from Chang
and Lin [5], as well as for MNIST [1], CIFAR-10 [19], CIFAR-100 [19]. Their
results use the ResNet-34 [14] and DenseNet-121 [16] architectures. We add to
this body of evidence by testing the CLR for the ResNet-18 [14] and VGG [31]
architectures on CIFAR-10, and a ResNet-50 architecture on ImageNet [8]. In
all cases we tried, we observed that the CLR provides stable training and
quick convergence. Figure 2 shows that the CLR reaches 0 training loss quicker
than SGD over a learning rate sweep on CIFAR-10, but that a larger learning
rate reaches a better test set accuracy. Figure 3 shows ImageNet results
across a series of batch sizes. Figure 4 shows the value of the CLR in
training for both datasets. We note that with CLR we observe an (automated)
initial learning rate warm-up followed by a decay, coinciding with the common
practice of learning rate manually devised schedules [22, 15]. We present
additional experimental results in the Appendix B.

Figure 2: The adaptive CLR converges for a ResNet-18 trained on CIFAR-10, and
it does so quicker than SGD with a fixed learning rate obtained from a sweep.
Batch size 4096. Results across a wide range of batch sizes can be found in
Figure 9. Results obtained using 3 seeds.

Figure 3: The CLR converges for a ResNet-50 trained on Imagenet across batch
sizes. We compare with vanilla SGD in Figure 8: the CLR converges quicker than
the fixed learning rates. Results obtained using 3 seeds.

Figure 4: CLR values adapt to training. Note: for ImageNet we cap the maximum
value of the learning rate to 10. Results obtained using 3 seeds.

##  5 Conclusion

We defined the notion of corridors in loss landscapes as regions of the loss
surface where the solutions of the GF become lines travelled at constant
speed. We then found useful properties of corridors, by showing that inside
corridors GD follows the GF exactly, that $H(\theta)g(\theta)$ vanishes, and
that corridors are the only regions where this can happen.  We also showed
that inside corridors the loss decreases linearly, allowing us to construct an
adaptive learning rate for GD, the corridor learning rate (CLT). We found that
the CLT coincides with the Polyak step-size [27]; the Polyak step size had
been observed to converge in the context of deep learning in prior work, and
here we contributed to these results using additional architectures and
datasets.  The focus of this work is to advertise the notion of corridors, and
foster new research along these geometric lines (pun intended!). Our focus
here is not to devise an adaptation learning scheme competitive with
algorithms such as Adam [18], or other adaptive learning rates for SGD [30,
17, 7] but instead to showcase the usefulness of studying corridors. In
particular, we hope that future work will hone into the theoretical and
empirical study of when corridors occur in neural network training. Since
inside corridors implicit regularization effects induced by the discretization
error of GD do not occur, finding the scope of corridors in neural landscapes
can further unlock the understanding of optimization induced implicit
regularization in deep learning.

## Acknowledgements

We would like to thank David Barrett, Shakir Mohamed, and Michael Munn for
helpful discussion and feedback as well as Patrick Cole for their support.

## References

  * lec [1989] Backpropagation applied to handwritten zip code recognition.  _Neural computation_ , 1(4):541–551, 1989.
  * Barrett and Dherin [2021] David G.T. Barrett and Benoit Dherin.  Implicit gradient regularization.  In _ICLR_ , 2021.
  * Bottou et al. [2018] Leon Bottou, Frank E. Curtis, and Jorge Nocedal.  Optimization methods for large-scale machine learning.  _SIAM Review_ , 60(2), 2018.
  * Cattaneo et al. [2023] Matias D Cattaneo, Jason M Klusowski, and Boris Shigida.  On the implicit bias of adam.  _arXiv:2309.00079_ , 2023.
  * Chang and Lin [2011] Chih-Chung Chang and Chih-Jen Lin.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2, 2011\.  Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  * Cohen et al. [2021] Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar.  Gradient descent on neural networks typically occurs at the edge of stability.  In _ICLR_ , 2021.
  * Cutkosky et al. [2023] Ashok Cutkosky, Aaron Defazio, and Harsh Mehta.  Mechanic: A learning rate tuner.  _arXiv:2306.00144_ , 2023.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _CVPR_ , 2009.
  * Elkabetz and Cohen [2021] Omer Elkabetz and Nadav Cohen.  Continuous vs. discrete optimization of deep neural networks.  In _NeurIPS_ , 2021.
  * Ghosh et al. [2023] Avrajit Ghosh, He Lyu, Xitong Zhang, and Rongrong Wang.  Implicit regularization in heavy-ball momentum accelerated stochastic gradient descent.  _ICLR_ , 2023.
  * Gunasekar et al. [2017] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro.  Implicit regularization in matrix factorization.  _NeurIPS_ , 2017.
  * Hairer et al. [2006] Ernst Hairer, Marlis Hochbruck, Arieh Iserles, and Christian Lubich.  Geometric numerical integration.  _Oberwolfach Reports_ , 3(1):805–882, 2006.
  * Hazan and Kakade [2019] Elad Hazan and Sham Kakade.  Revisiting the polyak step size.  _arXiv:1905.00313_ , 2019.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , 2016.
  * He et al. [2019] Tong He, Zhi Zhang, Hang Zhang, Zhongyue Zhang, Junyuan Xie, and Mu Li.  Bag of tricks for image classification with convolutional neural networks.  In _CVPR_ , 2019.
  * Huang et al. [2017] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger.  Densely connected convolutional networks.  In _CVPR_ , 2017.
  * Ivgi et al. [2023] Maor Ivgi, Oliver Hinder, and Yair Carmon.  Dog is sgd’s best friend: A parameter-free dynamic step size schedule.  _arXiv:2302.12022_ , 2023.
  * Kingma and Ba [2015] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _ICLR_ , 2015.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  _https://www.cs.toronto.edu/ kriz/learning-features-2009-TR.pdf_ , 2009.
  * Kunin et al. [2021] Daniel Kunin, Javier Sagastuy-Brena, and Hidenori Tanaka Ganguli, Surya Daniel L.K. Yamins.  Symmetry, conservation laws, and learning dynamics in neural networks.  In _ICLR_ , 2021.
  * Loizou et al. [2021] Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien.  Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence.  In _AISTATS_ , 2021.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Sgdr: Stochastic gradient descent with warm restarts.  In _ICLR_ , 2017.
  * Ma et al. [2022] Chao Ma, Daniel Kunin, Lei Wu, and Lexing Ying.  Beyond the quadratic approximation: the multiscale structure of neural network loss landscapes, 2022.
  * Miyagawa [2022] Taiki Miyagawa.  Toward equation of motion for deep neural networks: Continuous-time gradient descent and discretization error analysis.  In _NeurIPS_ , 2022.
  * Orvieto et al. [2022] Antonia Orvieto, Simon Lacoste-Julien, and Nicolas Loizou.  Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution.  In _NeurIPS_ , 2022.
  * Polyak [1964] Boris T Polyak.  Some methods of speeding up the convergence of iteration methods.  _Ussr computational mathematics and mathematical physics_ , 4(5):1–17, 1964.
  * Polyak [1987] Boris T Polyak.  Introduction to optimization. optimization software.  _Inc., Publications Division, New York_ , 1:32, 1987.
  * Rosca and Deisenroth [2023] Mihaela Rosca and Marc Peter Deisenroth.  Implicit regularisation in stochastic gradient descent: from single-objective to two-player games.  _arXiv:2307.05789_ , 2023.
  * Rosca et al. [2021] Mihaela Rosca, Yan Wu, Benoit Dherin, and David G.T. Barrett.  Discretization drift in two-player games.  In _ICML_ , 2021.
  * Rosca et al. [2023] Mihaela Rosca, Yan Wu, Chongli Qin, and Benoit Dherin.  On a continuous time model of gradient descent dynamics and instability in deep learning.  In _TMLR_ , 2023.
  * Simonyan and Zisserman [2015] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In _ICLR_ , 2015.
  * Smith et al. [2021] Samuel L Smith, Benoit Dherin, David G.T. Barrett, and Soham De.  On the origin of implicit regularization in stochastic gradient descent.  In _ICLR_ , 2021.
  * Soudry et al. [2018] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  _JMLR_ , 2018.
  * Stolfi et al. [2004] Jorge Stolfi, David Eppstein, Charles Matthews, Paul Gond, Luca Innocenti, Sam Nead, and Anonymous Collaborators.  Ruled surface.  _Wikipedia_ , 2004.  URL https://en.wikipedia.org/wiki/Ruled_surface.

##  Appendix A Beyond gradient descent

###  A.1 Momentum follows a sped up GF in corridors

In this section, we investigate the behaviour of momentum inside corridors. As
in the main text, we will use that inside a corridor, we have $g(\theta-
tg(\theta))=g(\theta),\forall t\geq 0$ (Lemma 2.9).

We now use this property to investigate momentum updates in corridors.
Momentum updates with decay rates $\beta$ and learning rate $h$ are defined as

$\displaystyle v_{0}$ $\displaystyle=0$ (4) $\displaystyle v_{t}$
$\displaystyle=\beta v_{t-1}-hg(\theta_{t-1})$ (5) $\displaystyle\theta_{t}$
$\displaystyle=\theta_{t-1}+v_{t}$ (6)

######  Lemma A.1.

Momentum updates in a corridor (the model is initialised in a corridor and
remains in a corridor as updates occur) can be written as

$\displaystyle v_{t}$
$\displaystyle=-h\frac{(1-\beta^{t})}{1-\beta}g(\theta_{0})$ (7)
$\displaystyle\theta_{t}$
$\displaystyle=\theta_{0}-\frac{h}{1-\beta}\sum_{i=1}^{t}(1-\beta^{i})g(\theta_{0})$
(8)

###### Proof.

The proof is by induction. Base case:

$\displaystyle v_{1}$ $\displaystyle=\beta
v_{0}-hg(\theta_{0})=-hg(\theta_{0})$ (9) $\displaystyle\theta_{1}$
$\displaystyle=\theta_{0}-hg(\theta_{0})$ (10)

Induction step:

$\displaystyle v_{t}$ $\displaystyle=$ $\displaystyle\beta
v_{t-1}-hg(\theta_{t-1})$ $\displaystyle=$
$\displaystyle\beta\left(-h\frac{(1-\beta^{t-1})}{1-\beta}g(\theta_{0})\right)-hg(\theta_{t-1})$
$\displaystyle=$
$\displaystyle\beta\left(-h\frac{(1-\beta^{t-1})}{1-\beta}g(\theta_{0})\right)-hg(\theta_{0})\quad\textrm{(Induct.
Hypo. \&}\,\textrm{ Lemma~{}\ref{lemma:cost_grad})}$ $\displaystyle=$
$\displaystyle-h\frac{1}{1-\beta}\left(\beta(1-\beta^{t-1})+1-\beta\right)g(\theta_{0})$
$\displaystyle=$ $\displaystyle-h\frac{(1-\beta^{t})}{1-\beta}g(\theta_{0})$

From here:

$\displaystyle\theta_{t}$
$\displaystyle=\theta_{t-1}+\sum_{i=1}^{t}v_{i}=\theta_{0}-\frac{h}{1-\beta}\sum_{i=1}^{t}(1-\beta^{i})g(\theta_{0})$
(11)

finishing the proof. ∎

######  Remark A.2.

The above results show that if momentum enters a corridor with a zero velocity
vector, it follows the lines of the GF, but at a different speed given by the
coefficient $\beta$. Note that the assumption that momentum enters the
corridor with zero velocity (i.e, $v_{0}=0$) is key to the proof. A similar
proof can be repeated by assuming the initial velocity to be aligned to the
initial gradient corridor (i.e., $v_{0}=\lambda g(\theta_{0})$) allowing us to
use Lemma 2.9. However, outside of these conditions, momentum may no longer
stay on the lines of steepest descent and may start drifting away from the GF.
This gives an edge to momentum compared to GD since implicit regularization
[2, 30] can occur.

######  Remark A.3.

Inside corridors momentum with initial zero velocity follows the ODE exactly:

$\displaystyle\dot{\theta}=-\frac{1-\beta^{n}}{1-\beta}g(\theta(t)),\hskip
20.00003ptt\in[hn,h(n+1)]$ (12)

###### Proof.

Since this ODE is of the form $\dot{\theta}=-c_{n}g(\theta(t)),\hskip
20.00003ptt\in[hn,h(n+1)]$, we have that just like under the GF, under this
ODE $\dot{g(\theta)}=-c_{n}H(\theta(t))g(\theta)=0$, and thus as long as a
corridor is not exited, under the trajectory of this ODE the gradient is
constant in time. We then have:

$\displaystyle\theta(nh)=\theta((n-1)h)-h\frac{1-\beta^{n}}{1-\beta}g(\theta(t))=\theta((n-1)h)-h\frac{1-\beta^{n}}{1-\beta}g(\theta(0))$
(13)

which when expanded in $n$ leads to the momentum equation in corridors in Eq
8. This results shows that the implicit regularization terms found for
momentum by Ghosh et al. [10] vanish, just like for GD, and that momentum
follows the same trajectory as GD, but at a higher speed (given by the
coefficient $\beta$). ∎

###  A.2 RK4 follows the GF in corridors

In this section, we investigate the behaviour of RK4 inside corridors.

We have that the RK4 update is

$\displaystyle k_{1}$ $\displaystyle=-g(\theta_{t-1})$ (14) $\displaystyle
k_{2}$ $\displaystyle=-g(\theta_{t-1}+\frac{h}{2}k_{1})$ (15) $\displaystyle
k_{3}$ $\displaystyle=-g(\theta_{t-1}+\frac{h}{2}k_{2})$ (16) $\displaystyle
k_{4}$ $\displaystyle=-g(\theta_{t-1}+hk_{3})$ (17) $\displaystyle\theta_{t}$
$\displaystyle=\theta_{t-1}+\frac{1}{6}(k_{1}+2k_{2}+2k_{3}+k_{4})$ (18)

Since we have that inside a corridor $g(\theta-tg(\theta))=g(\theta),\forall
t\geq 0$, it follows that $k_{1}=k_{2}=k_{3}=k_{4}=-g(\theta_{t-1})$, and thus
$\theta_{t}=\theta_{t-1}-g(\theta_{t-1})$, which is exactly the GF trajectory
inside a corridor. As with GD, we find that Rk4 follows the GF exactly inside
corridors.

###  A.3 Stochastic Gradient Descent

We now study the implicit regularization effect of SGD inside corridors. Smith
et al. [32] show that after one epoch SGD iterates, in expectation over all
possible batch shufflings $\sigma$, follow a modified flow with an error
$\mathcal{O}(m^{3}h^{3})$:

$\displaystyle E_{\sigma}\left[\theta_{m}\right]$
$\displaystyle=\theta(mh)+\mathcal{O}(m^{3}h^{3}),\hskip
30.00005pt\text{with}$ (19) $\displaystyle\dot{\theta}$
$\displaystyle=-g(\theta)-\frac{h}{4}\nabla_{\theta}\|g(\theta)\|^{2}-\frac{h}{4m}\sum_{i=1}^{m}\nabla_{\theta}\|g(\theta)-g_{i}(\theta)\|^{2}$
(20)

where $m$ is the number of updates in an epoch and $g_{i}$ is the gradient
corresponding to batch $i$.

Since $\frac{1}{2}\nabla_{\theta}\|g(\theta)\|^{2}=H(\theta)g(\theta)$, and
$H(\theta)g(\theta)=0$ inside a corridor (Theorem 2.11), this entails that the
only regularization pressure of order $\mathcal{O}(h^{2})$ left from SGD is
the minimisation of $\nabla_{\theta}\|g(\theta)-g_{i}(\theta)\|^{2}$.

##  Appendix B Additional experimental results

Figure 5: The corridor learning rate converges for a ResNet-50 trained on
CIFAR-10.

Figure 6: The CLR converges for a VGG trained on CIFAR-10. Results obtained
using 3 seeds.

Figure 7: Loss and $H(\theta)g(\theta)$ across a trajectory obtained with the
learning rate adaptation scheme for a ResNet-18 trained on CIFAR-10. Results
obtained using 3 seeds.

Figure 8: The CLR converges for a ResNet-50 trained on Imagenet, and it does
so quicker that vanilla SGD (curves with fixed learning rates). We show that
the same setting the CLR converges across a wide range of batch sizes in
Figure 9. Results obtained using 3 seeds.

Figure 9: The CLR converges for a ResNet-18 trained on CIFAR10.

##  Appendix C Quadratic functions do not have corridors

In this section, we show that quadratic functions which display corridors are
linear.

Assume $E(\theta)=\frac{1}{2}\theta^{T}A\theta+b\theta+c$. We then have
$\nabla_{\theta}E=A\theta+b$ and $\nabla^{2}_{\theta}E=A$. For $U$ to be a
corridor, we need that
$\nabla^{2}_{\theta}E\nabla_{\theta}E=A(A\theta+b)=0,\forall\theta\in U$.
Consider $\lambda_{i},u_{i}$ be the $i$’th largest eigenvalue and eigenvector
of $A$.

We have that

$\displaystyle
A(A\theta+b)=\sum_{i}\left(\lambda_{i}^{2}{u_{i}}^{T}\theta+\lambda_{i}u_{i}^{T}b\right)u_{i}=0,\forall\theta\in
U$ (21)

We then have that $\forall i$ either

  * •

$\lambda_{i}=0$

  * •

$\lambda_{i}{u_{i}}^{T}\theta+u_{i}^{T}b=0$

if $\lambda_{i}=0\forall i$, we have that $A=0$ and $E$ is a linear function.
If $A\neq 0$, we have that

$\displaystyle\nabla_{\theta}E=A\theta+b=\sum_{i}(\lambda_{i}\theta^{T}u_{i}+b^{t}u_{i})u_{i}=\sum_{i,\lambda_{i}=0}b^{t}u_{i}u_{i}$
(22)

which is a constant, and again we have that $E$ is linear in $\theta$ in $U$.