Theory of Optimal Learning Rate Schedules and Scaling Laws for a Random Feature Model
Blake Bordelon, Francesco Mori
Abstract
Setting the learning rate for a deep learning model is a critical part of successful training, yet choosing this hyperparameter is often done empirically with trial and error. In this work, we explore a solvable model of optimal learning rate schedules for a powerlaw random feature model trained with stochastic gradient descent (SGD). We consider the optimal schedule η T ⋆ ( t ) \eta_{T}^{\star}(t) where t t is the current iterate and T T is the total training horizon. This schedule is computed both numerically and analytically (when possible) using optimal control methods. Our analysis reveals two regimes which we term the easy phase and hard phase. In the easy phase the optimal schedule is a polynomial decay η T ⋆ ( t ) ≃ T − ξ ( 1 − t / T ) δ \eta_{T}^{\star}(t)\simeq T^{-\xi}(1-t/T)^{\delta} where ξ \xi and δ \delta depend on the properties of the features and task. In the hard phase, the optimal schedule resembles warmup-stable-decay with constant (in T T ) initial learning rate and annealing performed over a vanishing (in T T ) fraction of training steps. We investigate joint optimization of learning rate and batch size, identifying a degenerate optimality condition. Our model also predicts the compute-optimal scaling laws (where model size and training steps are chosen optimally) in both easy and hard regimes. Going beyond SGD, we consider optimal schedules for the momentum β ( t ) \beta(t) , where speedups in the hard phase are possible. We compare our optimal schedule to various benchmarks in our task including (1) optimal constant learning rates η T ( t ) ∼ T − ξ \eta_{T}(t)\sim T^{-\xi} (2) optimal power laws η T ( t ) ∼ T − ξ t − χ \eta_{T}(t)\sim T^{-\xi}t^{-\chi} , finding that our schedule achieves better rates than either of these. Our theory suggests that learning rate transfer across training horizon depends on the structure of the model and task. We explore these ideas in simple experimental pretraining setups.
†
†
affiliationnotice:
Equal contribution
1
Introduction
Training deep learning models requires choosing many hyperparameters such as the learning rate, batch size, training horizon, total data, and architectural details, resulting in a complicated decision space. To make matters worse, it is challenging to characterize how these various hyperparameters jointly interact as one scales up the model size or training horizon. One strategy to reduce this complexity is to identify scaling protocols that allow for
transfer
of optimal hyperparameters, where small models can provide reliable proxies for tuning for large models. Such approximate hyperparameter transfer across model sizes can be achieved by principled parameterization and optimizer design
(
43
;
6
;
44
;
11
)
. However, these schemes do not automatically lead to transfer over training horizons
(
3
;
13
)
. In Figure
1
we illustrate the failure of transfer over training horizons
T
despite having successful transfer over model sizes (widths
N
). This failure motivates theory that can account for the behavior of optimal learning rates of SGD as the training horizon varies. Further, beyond optimal base learning rates themselves, one can also adopt a
learning rate schedule
. While many schedules such as linear decay, warmup-stable-decay, and cosine annealing are commonly used in practice, it is unclear under which conditions one should favor using a type of schedule over the other.
(a)
ResNet SGD Training on CIFAR-5M
(b)
Power Law Random Feature Model with SGD
Figure 1
:
SGD learning rates do not automatically transfer over training horizons
T
. This motivates theory that can identify not only how to scale
\eta
with
T
, but also how to set the entire learning rate schedule
\eta(t)
with
T
. (a) The loss of a deep ResNet trained on CIFAR-5M. (b) Test loss of a random feature model trained with SGD as a function of fixed learning rate
\eta
. The optimal learning rate shifts leftwards in this model, mimicking the behavior of the real network training
(
3
)
.
To address these questions in a theoretical framework, we make the following contributions:
•
We analyze SGD dynamics in a powerlaw random feature model
(
7
;
4
;
33
)
. We show that SGD fluctuations can lead to shifts in optimal learning rates across training horizons
T
that are
task and model dependent
.
•
We characterize both numerically and analytically the
optimal learning rate annealing schedule
for SGD in our model using optimal control, minimizing the final test loss at step
T
. This analysis reveals two phases of tasks, easy and hard. For easy tasks, our schedule takes the form
\eta(t)=T^{-\xi}f(t/T)
, while for hard tasks our schedule resembles warmup-stable-decay (WSD).
•
We compare our optimal schedules to various benchmarks including optimized constant learning rate and optimal powerlaw schedules, finding that our schedules can achieve better scaling exponents.
•
This analysis is generalized to optimal
batch size
schedules and optimal
momentum
schedules. Optimizing batch size and learning rate jointly enables a reduction in total wall-clock time, while optimizing the momentum parameter can provide an improvement in the scaling exponent for hard tasks beyond SGD.
1.1
Related Works
Based on the correspondence between neural networks in the lazy training regime
(
9
)
, many works have attempted to characterize neural scaling laws
(
22
;
18
)
by computing the generalization of random feature models with powerlaw features
(
39
;
7
;
2
;
4
;
33
;
26
;
14
)
. Several works have examined easy and hard phases of this model in the noise dominated regime
(
12
;
25
)
. Notably,
34
demonstrated that optimal rates for SGD can be achieved in the hard phase with data repetition and model averaging strategies.
28
recently analyzed this model to motivate invariances between learning rate and batch sizes when designing schedules.
(
35
)
identified a scaling collapse phenomenon where the compute optimal models exhibit universal loss dynamics across scales for a variety of learning rate schedules and developed a theoretical model of SGD that accounted for this supercollapse. Our work similarly utilizes this powerlaw random feature model, however we study the
optimal learning rate schedule
for SGD using optimal control theory.
Optimal control theory provides a principled framework for deriving hyperparameter schedules in reduced theoretical models. Pioneering work in the 1990s characterized optimal learning rate schedules for two-layer neural networks within the teacher-student formalism
(
37
;
36
)
. More recently, these techniques have been generalized to several hyperparameter protocols
(
30
;
29
)
. Analogous optimization procedures have also recently been studied in deep linear networks
(
8
)
and cognitive science
(
32
)
.
Most closely related to our work is
(
24
)
, which examined learning rate schedules within the context of power-law random feature models. However, their analysis was restricted to pre-defined, parametric schedules and did not address the theoretical derivation of the optimal control policy.
2
Setting
2.1
Power Law Linear Random Feature Model
We consider a random-feature model widely studied in the literature of scaling laws
(
7
;
4
;
26
;
33
)
.
Let the inputs
{\bm{x}}\in\mathbb{R}^{D}
be drawn from a probability distribution
p({\bm{x}})
. The associated labels are generated as
y({\bm{x}})={\bm{w}}^{*}\cdot{\bm{\psi}}({\bm{x}})+\sigma_{0}z\,,
(1)
where
\sigma_{0}>0
is the amplitude of the label noise and
z\sim\mathcal{N}(0,1)
. The vector
{\bm{\psi}}({\bm{x}})\in\mathbb{R}^{M}
(with
M
possibly infinite) is a feature map and
{\bm{w}}^{*}\in\mathbb{R}^{M}
a vector of parameters. We work in the feature eigenbasis, so that
\langle{\bm{\psi}}_{i}(\bm{x}){\bm{\psi}}_{j}(\bm{x})\rangle_{\bm{x}\sim p(\bm{x})}=\delta_{ij}\lambda_{i}\,.
(2)
We consider a linear student model
\hat{y}(\bm{x})={\bm{w}}\cdot\tilde{\bm{\psi}}(\bm{x})
, with parameters
{\bm{w}}\in\mathbb{R}^{N}
and projected features
\tilde{\bm{\psi}}(\bm{x})={\bm{G}}\bm{\psi}(\bm{x})
, where
{\bm{G}}\in\mathbb{R}^{N\times M}
is a projection matrix. To describe model-size effects, we assume
N\leq M
and that the top-
N
features are selected, i.e.,
{\bm{G}}=[{\bm{I}}_{N},{\bm{0}}_{N\times(M-N)}]
. We train via online stochastic gradient descent (SGD) on the square loss
{\bm{w}}_{t+1}={\bm{w}}_{t}-\frac{\eta_{t}}{m_{t}}\sum_{\mu=1}^{m_{t}}\tilde{\bm{\psi}}(\bm{x}_{\mu,t})({\bm{w}_{t}}\cdot\tilde{\bm{\psi}}(\bm{x}_{t,\mu})-y(\bm{x}_{t,\mu}))\,,
(3)
with learning rate
\eta_{t}
and minibatch size
m_{t}
. The samples
\bm{x}_{\mu,t}
and the label noise variables
z_{\mu,t}
are assumed to be independent. The parameters are initialized to zero.
2.2
Analytical Expression for Test Loss Dynamics
Following
(
7
)
, for
k=1\,\ldots N
, we define
c_{t,k}=\langle(w_{t,k}-w^{*}_{k})^{2}\rangle_{\mathcal{D}_{t-1}}
, where
\langle\cdot\rangle_{\mathcal{D}_{t-1}}
indicates the average over all noise sources up to time
t-1
. Assuming that the features
{\bm{\psi}}({\bm{x}})
are zero-mean Gaussian variables, one can show that the coefficients
c_{t,k}
satisfy the recursion relation
(
7
)
\displaystyle c_{t+1,k}
\displaystyle=\left(1-2\eta_{t}\lambda_{k}+\eta_{t}^{2}\frac{m_{t}+1}{m_{t}}\lambda_{k}^{2}\right)c_{t,k}
\displaystyle+\frac{\eta_{t}^{2}}{m_{t}}\lambda_{k}\sum_{\ell=1}^{N}\lambda_{\ell}c_{t,\ell}+\frac{\eta^{2}_{t}}{m_{t}}\sigma^{2}\lambda_{k}\,,
(4)
where we have defined the total irreducible noise as
\sigma^{2}=\sigma_{0}^{2}+\sum_{k=N+1}^{M}(w^{*}_{k})^{2}\lambda_{k}\,.
(5)
The test loss
L_{t}
at time
t
has the form
\displaystyle L_{t}
\displaystyle\equiv\langle\langle({\bm{w}}^{*}\cdot{\bm{\psi}}({\bm{x}})+\sigma_{0}z-{\bm{w}}\cdot\tilde{\bm{\psi}}(\bm{x}))^{2}\rangle_{\mathcal{D}_{t-1}}\rangle_{\bm{x},z}
\displaystyle=\sum_{k=1}^{N}c_{t,k}\lambda_{k}+\sigma^{2}\,.
(6)
It is therefore sufficient to track
c_{t,k}
in order to predict the test loss dynamics.
2.3
Power-law spectra
Motivated by empirical observations that natural data often exhibit power-law spectral decay
(
7
;
2
)
, we assume power-law scalings for the data covariance eigenvalues and the teacher weights:
\lambda_{k}\sim k^{-b}
and
(w^{*}_{k})^{2}\lambda_{k}\sim k^{-a}
, with exponents
a,b>1
. These parameters characterize the effective dimension and difficulty of the learning task.
Under these assumptions, for a constant learning rate
\eta
and batch size
m
, the excess loss scales as (see Appendix
C
):
L_{T}-\sigma^{2}\sim(\eta T)^{-\frac{a-1}{b}}+\frac{\sigma^{2}\eta}{m}\,,
(7)
where
\sim
denotes proportionality up to constant factors. Optimizing over a fixed learning rate yields the optimal constant strategy
\eta\sim T^{-(a-1)/(a+b-1)}
, which results in
L_{T}-\sigma^{2}\sim T^{-(a-1)/(a+b-1)}
. A fundamental question is whether this scaling exponent can be improved by modulating the learning rate over time, and if so, what is the optimal schedule
\eta_{T}^{*}(t)
.
(a)
Optimal Schedule (
b>a
)
(b)
Loss vs. Time (
b>a
)
(c)
Final Loss (
b>a
)
(d)
Optimal Schedule (
ba
) and easy (bottom row,
ba
)
Figure 3
:
Decomposition of the excess loss
L_{t}-\sigma^{2}
into bias and variance components.
(a)
In the easy phase (
b=2
,
a=3.5
), the optimal schedule minimizes bias and variance simultaneously throughout the training trajectory.
(b)
In the hard phase (
b=5
,
a=3.5
), the schedule minimizes the bias for the majority of the training time (
tt_{s}
) is responsible for suppressing the variance.
Parameters:
T=3162
,
N=1000
,
\sigma=0.5
,
m=5
.
3
Optimal LR schedules via optimal control
We formulate the selection of the learning rate schedule as an optimal control problem aimed at minimizing the terminal generalization error
L_{T}
for a fixed training budget
T
. Initially, we focus on optimizing the learning rate
\eta_{T}(t)
at a constant mini-batch size. Directly applying optimal control to the SGD dynamics in Eq. (
3
) is computationally intractable due to the high-dimensional and stochastic nature of the process. Instead, we optimize the control variable acting on the deterministic evolution of the variables
c_{t,k}
derived in Eq. (
4
). For this analysis, we fix the model size to a large value (
N=1000
unless stated otherwise). The joint optimization of model size and training time (compute-optimal scaling) is discussed in Section
3.5
.
3.1
Numerical optimal control
We first approach the problem numerically by optimizing the evolution equation (
4
) using a single-shooting method implemented in CasADi
(
1
)
, see Appendix
F
for details. This procedure allows us to identify the optimal learning rate schedules
\eta_{T}^{*}(t)
for various training horizons
T
, as illustrated in Figures
2
a and
2
d. Crucially, we observe that across different regimes of data structure (parameterized by
a
and
b
), the optimal schedules achieve a higher scaling exponent compared to the optimal constant-
\eta
baseline.
3.2
Analytical derivation of optimal schedules
To determine the analytical form of the optimal schedule, we consider the continuous-time limit for large
T
(when taking this limit, we will often use the notation
\eta(t)
). Assuming that the learning rate decays sufficiently fast as
t\to T
(see Appendix
C
), we can decompose the generalization error into bias and variance terms
L_{T}-\sigma^{2}\sim\operatorname{Bias}(T)+\operatorname{Var}(T)\,,
(8)
where
\operatorname{Bias}(T)=\left(\int_{0}^{T}dt~\eta(t)\right)^{-\frac{a-1}{b}}\,,
(9)
and
\displaystyle\operatorname{Var}(T)=\sigma^{2}\int_{0}^{T}dt~\frac{\eta^{2}(t)}{m(t)}\left(\int_{t}^{T}dt^{\prime}~\eta(t^{\prime})\right)^{-\frac{2b-1}{b}}\,,
(10)
where
m(t)
denotes the minibatch size at time
t
, that we take for now to be constant
m(t)=m
. To solve for the optimal schedule, we introduce the auxiliary state variable
\chi(t)=\int_{t}^{T}ds~\eta(s)
, such that
\eta(t)=-\dot{\chi}(t)
and
\chi(T)=0
. The optimization problem can then be recast as minimizing the following functional of
\chi(t)
\displaystyle L_{T}-\sigma^{2}=\chi(0)^{-\frac{a-1}{b}}+\frac{\sigma^{2}}{m}\int_{0}^{T}dt~\dot{\chi}^{2}(t)\chi(t)^{-\frac{2b-1}{b}}\,.
(11)
Since the Lagrangian density, i.e., the integrand in Eq. (
11
), explicitly depends on
\{\chi,\dot{\chi}\}
but not on
t
, we can apply Noether’s theorem
(
16
)
to identify a conserved quantity, which implies that the optimal trajectory satisfies the differential equation
\dot{\chi}(t)\propto\chi(t)^{(2b-1)/2b}
. The full analytical solution is detailed in Appendix
B
. To ensure the stability of the SGD dynamics, we additionally impose the hard constraint
\eta(t)\leq\eta_{\max}
. This constraint leads to two distinct scaling regimes depending on the parameters
a
and
b
. Following the terminology of
(
34
)
, we distinguish between an
easy phase
(
ba
), where it plays a critical role.
1
1
1
We note that this easy/hard distinction is focused on the behavior of label noise SGD and differs from other notions of easy and hard phases such as diverging RKHS norm
(
33
;
5
)
.
Easy phase.
In the regime where
ba
, the unconstrained optimum diverges, forcing the stability constraint
\eta(t)\leq\eta_{\max}
to become active. The optimal schedule is
\eta_{T}^{*}(t)=\begin{cases}\eta_{\max}&tt_{s}\,,\end{cases}
(14)
where the annealing phase duration scales as
1-t_{s}/T\sim T^{-\frac{b-a}{2b-1}}
, in agreement with the schedules derived numerically (see Fig.
7
). Interestingly, this protocol closely resembles a
warmup-stable-decay
(WSD) schedule
(
19
)
and yields a generalization error
L_{T}-\sigma^{2}\sim T^{-(a-1)/b}
, outperforming the optimal constant-
\eta
baseline.
Depending on the spectral properties of the data, the optimal learning rate schedule adopts either a polynomial decay or a WSD profile. To understand these distinct behaviors, it is instructive to analyze the bias-variance decomposition shown in Fig.
3
. The optimal schedule balances the reduction of bias, which benefits from larger learning rates (see Eq. (
9
)), against the variance, which requires annealing as
t\to T
(see Eq. (
10
)). This trade-off requires the late-stage annealing observed in both schedules.
In the hard phase (
b>a
), the slow decay of the bias implies that the unconstrained optimal learning rate would grow as
T^{b/a-1}
for large
T
. This divergence activates the stability constraint
\eta_{T}(t)\leq\eta_{\max}
, resulting in the WSD profile. While the easy phase schedule gradually decays to minimize both error components simultaneously, the hard phase strategy dedicates the majority of the training budget to maximizing bias suppression via a constant, maximal learning rate, compressing the variance-reducing annealing into a vanishing fraction of the total training time. In both regimes, a critical implication is that the optimal schedule relies on a fixed training horizon
T
. Anytime protocols, which are agnostic to the total budget, cannot effectively postpone variance minimization. The advantage of horizon-dependent schedules has been previously observed in convex optimization
(
20
;
10
)
.
Previous works have rationalized the effectiveness of the WSD schedule by conjecturing a “river valley” loss landscape
(
41
;
27
)
. Here, we demonstrate that WSD is the optimal strategy in the hard phase, providing an alternative explanation for its effectiveness based balancing demands of bias and variance reduction.
3.3
Comparison with benchmarks
Phase
Constant LR
Powerlaw
Optimal
Easy
(a>b)
\frac{a-1}{a-1+b}
\frac{a-1}{a-1+b}
\frac{a-1}{a}
Hard
(aa
(
15
)
.
34
show a combination of data repetition and model averaging can improve the rates in the hard phase to saturate the theoretically optimal rate.
Generalizing beyond the specific optimal schedule derived in Eq. (
12
), we investigate the sensitivity of the performance to the choice of the profile function within the general scaling
\eta_{T}(t)=T^{-\xi}g\left(t/T\right)
. In Appendix
C
, we show that the specific shape of
g(z)
does not change the scaling exponent, provided it decays faster than
(1-z)^{b-1}
as
z\to 1
. The prefactor exponent
\xi
must be chosen as
\xi=\max[0,1-b/a]
(using a different value would result in suboptimal scaling). Under these conditions, the generic schedule recovers the optimal scaling exponents in both the easy and hard regimes, differing from the optimal error only by a constant prefactor.
3.4
Joint optimization of learning rate and batch size
Our analysis extends naturally to the joint optimization of the learning rate
\eta(t)
and minibatch size
m(t)
under a fixed data budget
B_{\rm tot}=\int_{0}^{T}dt~m(t)
. In this setting, the wall-clock time
T
is treated as a free variable. As detailed in Appendix
D
, the optimization yields a degenerate family of solutions satisfying the relation
m(t)\propto\eta(t)\chi(t)^{-1+1/(2b)}
. This manifold of solutions includes the fixed-batch strategy derived previously. However, following
(
28
)
, we can break this degeneracy by selecting the specific schedule that minimizes the wall-clock time
T
required to achieve the optimal performance. This criterion implies fixing the learning rate at its maximum stable value,
\eta(t)=\eta_{\max}
, which dictates the following batch-size schedule:
m^{*}_{T}(t)=\frac{B_{\rm tot}}{2bT}\left(1-\frac{t}{T}\right)^{\frac{1}{2b}-1}\,,
(15)
corresponding to an increasing batch size during training. This type of procedure, known as a
batch ramp
, has been empirically proposed
(
38
)
but is derived here by a principled method.
The wall-clock time should be chosen to scale with the data budget as
T\sim B_{\rm tot}^{b/a}
for
ba
. Crucially, while the joint optimization reduces wall-clock time, it preserves the fundamental scaling of the generalization error with respect to the sample budget
B_{\rm tot}
. Specifically, we recover
L_{T}-\sigma^{2}\sim B_{\rm tot}^{-(a-1)/a}
in the easy phase (
ba
), matching the scaling laws obtained by optimizing
\eta
at fixed
m
. However, a significant distinction emerges when analyzing the scaling with respect to wall-clock time. In the hard phase, the error scaling with
T
remains unchanged relative to the fixed-batch optimal strategy (
L_{T}-\sigma^{2}\sim T^{-(a-1)/b}
). In contrast, in the easy phase, the joint optimization yields a strictly improved scaling of
L_{T}-\sigma^{2}\sim T^{-(a-1)/b}
(compared to
L_{T}-\sigma^{2}\sim T^{-(a-1)/a}
).
3.5
Compute-optimal scaling
(a)
Easy Phase (
ba
)
Figure 4
:
Compute optimal scaling.
Residual loss
L_{C}-\sigma_{0}^{2}
as a function of the compute
C=NT
for different values of the model size
N
. The dashed lines indicate the theoretical prediction.
Parameters:
\sigma=0.5
,
m=5
. In the easy phase
b=1.5
and
a=2
, in the hard phase
b=2
and
a=1.5
.
We next address the problem of jointly scaling the model size
N
and the data budget
B_{\rm tot}
to minimize the generalization error
L_{C}
under a fixed compute budget
C=B_{\rm tot}N
. Using Eq. (
5
), for
M\gg N\gg 1
, the effective noise variance scales as
\sigma^{2}\sim\sigma_{0}^{2}+N^{1-a}
. Consequently, in the easy phase, the excess loss scales as
L_{T}-\sigma_{0}^{2}\sim B_{\rm tot}^{-(a-1)/a}+N^{1-a}
. Balancing these terms yields the compute-optimal allocation
B_{\rm tot}\sim C^{a/(a+1)}
and
N\sim C^{1/(a+1)}
. This results in an optimal error scaling of
L_{C}-\sigma_{0}^{2}\sim C^{-(a-1)/(a+1)}
. Similarly, in the hard phase, the loss scales as
L_{T}-\sigma_{0}^{2}\sim B_{\rm tot}^{-(a-1)/b}+N^{1-a}
. Optimizing this tradeoff leads to
B_{\rm tot}\sim C^{b/(b+1)}
and
N\sim C^{1/(b+1)}
, yielding a final error scaling of
L_{C}-\sigma_{0}^{2}\sim C^{-(a-1)/(b+1)}
. These theoretical scaling laws are verified in Fig.
4
.
3.6
Optimal Momentum Schedules Compared to SGD
(a)
Easy Task Loss Dynamics
(b)
Easy Task Momentum
(c)
Easy Task Learning Rate
(d)
Hard Task
(e)
Hard Task
(f)
Hard Task
Figure 5
:
Optimal Schedule and loss dynamics for SGD + momentum. (a) For the easy task regime, the numerically optimized schedule achieves the same scaling law as SGD with optimal schedule
L_{T}-\sigma^{2}\sim T^{-1+1/a}
. (b) The optimal momentum dynamics vary significantly across
T
but only weakly vary with
t
. (c) The learning rate for optimal momentum schedules anneals similarly to SGD in the easy phase. (d) In the hard phase, the scaling law for the loss obtained by jointly optimizing momentum and learning rate is better than the SGD rate
T^{-(a-1)/b}
. (e)-(f) Near the end of training, the momentum variable increases and the learning rate rapidly decreases.
(a)
Annealing vs Fixed LR (blue)
(b)
Fixed Learning Rate Fails to Transfer
(c)
LR Transfer with Annealing
Figure 6
:
We plot width
N=32
depth
12
convolutional ResNets trained with SGD with batch size
m=32
. (a) Cross-entropy loss dynamics as a function of training time
t
for fixed learning rate (blue) and polynomial annealing schedule set to training horizon
T
. The final loss follows a better trend when using the annealing schedule. (b) Loss as a function of
(\eta,T)
and for fixed learning rate. The optimal learning rate decreases with
T
. (c) For polynomial annealing schedules, the optimal base learning rate is approximately constant across horizons
T
, consistent with our model in the hard phase. Further, the best performance achieved at
T
iterations is noticeably improved compared to constant learning rate.
We also study momentum with time varying learning rates
\eta_{t}
and momentum
\beta_{t}
which generate the update equations for parameters
\bm{w}_{t}
\displaystyle\bm{w}_{t+1}=\bm{w}_{t}+\eta_{t}\bm{v}_{t}
\displaystyle\bm{v}_{t}=(1-\beta_{t})\bm{v}_{t-1}+\beta_{t}\bm{g}_{t}
\displaystyle\bm{g}_{t}\equiv\frac{1}{m_{t}}\sum_{\mu=1}^{m_{t}}\tilde{\bm{\psi}}(\bm{x}_{t,\mu})\left(y(\bm{x}_{t,\mu})-\bm{w}_{t}\cdot\tilde{\bm{\psi}}(\bm{x}_{t,\mu})\right)
(16)
We optimize the loss at timestep
T
over the choices of
\{(\eta_{t},\beta_{t})\}_{t=1}^{T}
. Using similar methods to the analysis we used for SGD, we can compute the test loss by tracking three correlation variables
\{C_{k,t},R_{k,t},V_{k,t}\}
for each eigendirection
k
. These variables are defined as
\displaystyle C_{k,t}=\left<(w_{k,t}-w^{\star}_{k})^{2}\right>
\displaystyle R_{k,t}=\left
\displaystyle V_{k,t}=\left<(v_{k,t})^{2}\right>
(17)
which collectively evolve as a linear dynamical system that depends on
\lambda_{k},w^{\star}_{k},\eta_{t},\beta_{t}
and
m
. From this dynamical system, we can obtain the loss dynamics
L_{T}-\sigma^{2}=\sum_{k}\lambda_{k}C_{k,T}
, enabling use of optimal control. Recent work has demonstrated that allowing
\beta
to depend on time can improve scaling laws in this powerlaw random feature model
(
14
)
. Instead of a preset schedule for
\beta_{t}
, we investigate the
optimal control
policy for
\eta_{t}
and
\beta_{t}
. We plot the result for easy and hard tasks in Figure
5
, finding it differs from the anytime powerlaw schedule used by
(
14
)
. We find that the optimal control learning rate for easy tasks exhibits phenomenology remarkably similar to optimal SGD. However, for hard tasks, we find that optimizing the momentum schedule
\beta_{t}
in addition to the learning rate schedule
\eta_{t}
provides an improvement to the scaling law with
T
. The optimal momentum variables
\beta_{t}
in either case show an initial transient decrease before a final increase as
t/T\to 1
.
4
Experiments in Deep Networks
We study a simple setup of CIFAR-5M (an extended version of CIFAR-10 that allows one-pass training) image classification in a deep convolutional ResNet
(
31
)
. We train with SGD using either fixed learning rate or a polynomial decay schedule, consistent with our optimal schedule. In Figure
6
, we plot a comparison of the learning rate transfer for fixed learning rate schedules compared to polynomial decay. In Figure
6
(a) we show that the loss dynamics
L_{t}
for fixed learning rate (blue) can be outperformed at the same base learning rate by annealing with a schedule that decays to zero as
t/T\to 1
. In Figure
6
(b), we plot the optimal learning rate as a function of
T
for constant learning rate, which shifts left. Lastly, when using an annealing schedule we find that the optimal learning rate is approximately constant and the best performance at each value of
T
is improved compared to fixed learning rate. These observations are consistent with the behavior of our theoretical model in the hard phase since the optimal base learning rate is approximately constant. Based on the spectral analysis of the NTK for ResNets on CIFAR-5M from
(
4
)
, it is reasonable to expect this problem-architecture pair to fall in the hard phase. We note that our theory
does not generally predict transfer of base learning rates
, since in the easy phase, the optimal base learning rate will still scale as a powerlaw in
T
.
5
Conclusions
We theoretically analyzed the optimal learning rate schedule for a simple random feature model. Our results utilized optimal control methods, which enabled optimization over the full trajectory of the learning dynamics. This model recapitulated schedules often observed in practice including polynomial decay schedules and warmup-stable-decay. Further, we explored optimal batch size and optimal momentum schedules, finding possible improvements in wall-clock time or training horizon scaling laws respectively.
Limitations and Future Directions
While our analysis provided some insights into the behavior of SGD under different annealing schedules and different phases of task difficulty, there are several limitations to the present work. First, our current theory is focused on describing linear models trained with SGD. This can only capture optimization behaviors of neural networks operating in the lazy/kernel regime and also fails to capture the behavior of more sophisticated optimizers such as Adam or preconditioned optimizers like Muon, Shampoo, or SOAP
(
23
;
21
;
17
;
40
)
. Second, while our numerical solution to optimal momentum revealed an improvement in the scaling law exponent, we have not yet identified analytically what this improved exponent is for the hard phase. Lastly, we provided experiments of ResNets on CIFAR-5M that resemble our toy model in the hard phase. It would be interesting to identify naturalistic tasks (commonly studied architecture/optimizer/dataset pairs) that resemble the easy phase where both annealing and scaling the base learning rate are necessary to achieve optimal scaling laws.
Software and Data
We utilized the CasADi software package for numerical constrained optimal control problems
(
1
)
, for details see Appendix
F
. The implementation is available in the supplementary material. We used the CIFAR-5M dataset for our ResNet experiments
(
31
)
.
Code to reproduce the experiments can be found at
https://github.com/blakebordelon/opt-control-sgd-rf
.
Impact Statement
This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Appendix A
Long-time dynamics
We consider the evolution equation for
c_{t,k}
in Eq. (
4
). For small
\lambda_{k}
and recognizing that
\sum_{\ell=1}^{N}\lambda_{\ell}c_{t,\ell}=L_{t}-\sigma^{2}
, we get
\displaystyle c_{t+1,k}\approx\left(1-2\eta_{t}\lambda_{k}\right)c_{t,k}+\frac{\eta_{t}^{2}}{m_{t}}\lambda_{k}L_{t}\,.
(18)
This recursion admits the solution
(
7
)
c_{T,k}=c_{0,k}\prod_{i=0}^{T-1}\left(1-2\eta_{i}\lambda_{k}\right)+\lambda_{k}\sum_{n=0}^{T-1}\frac{\eta_{n}^{2}}{m_{n}}L_{n}\prod_{i=n+1}^{T-1}\left(1-2\eta_{i}\lambda_{k}\right)\,.
(19)
At late times
T
, and under the power-law assumptions
\lambda_{k}\sim k^{-b}
and
(w^{*}_{k})^{2}\lambda_{k}\sim k^{-a}
, we find the relation
L_{T}-\sigma^{2}=\sum_{k}\lambda_{k}c_{T,k}\approx f_{a}(2\chi_{0})+\int_{0}^{T}dt\ \frac{\eta(t)^{2}}{m(t)}L_{t}f_{2b}(2\chi(t))\,,
(20)
where
\chi(t)=\int_{t}^{T}\eta(t^{\prime})dt^{\prime}
,
\chi_{0}=\chi(0)
, and
f_{s}(\chi)\equiv\sum_{k=1}^{N}k^{-s}e^{-k^{-b}\chi}\,.
(21)
Note that
df_{s}(\chi)/d\chi=-f_{s+b}(\chi)
and that this function has asymptotic behaviors
f_{s}(\chi)\approx\zeta(s)=\sum_{k\geq 1}k^{-s}
for small
\chi
(and large
N
) and
f_{s}(\chi)\approx\Gamma((s-1)/b)\chi^{(1-s)/b}/b
for large
\chi
. Approximating
L_{t}\approx\sigma^{2}+f_{a}(2\chi_{0}-2\chi(t))
, we find
L_{T}-\sigma^{2}=\sum_{k}\lambda_{k}c_{T,k}\approx f_{a}(2\chi_{0})+\int_{0}^{T}dt\ \frac{\eta(t)^{2}}{m(t)}\left[\sigma^{2}+f_{a}(2\chi_{0}-2\chi(t))\right]f_{2b}(2\chi(t))\,.
(22)
Appendix B
Analytical derivation of optimal learning-rate schedules
B.1
Power-law spectra
Considering constant batch size
m(t)=m
, from Eq. (
22
) we get
L_{T}-\sigma^{2}\approx f_{a}(2\chi_{0})+\int_{0}^{T}dt\ \mathcal{L}(\dot{\chi}(t),\chi(t))\,,
(23)
where
\chi_{0}=\chi(0)
,
\ \mathcal{L}(\dot{\chi}(t),\chi(t))=\dot{\chi}(t)^{2}A(\chi,\chi_{0})\,,
(24)
and
A(\chi,\chi_{0})=\frac{1}{m}\left[\sigma^{2}+f_{a}(2\chi_{0}-2\chi)\right]f_{2b}(2\chi)\,.
(25)
Via Noether’s Theorem for time-translation
\frac{d}{dt}\left[\frac{\partial\mathcal{L}}{\partial\dot{\chi}}\dot{\chi}-\mathcal{L}\right]=0
, we can directly utilize this conservation law
\frac{d\mathcal{L}}{d\dot{\chi}}\dot{\chi}-\mathcal{L}=\mathcal{L}=c\,,
(26)
for some positive constant
c
, yielding
\dot{\chi}(t)=-\sqrt{\frac{c}{A(\chi(t),\chi_{0})}}\,,
(27)
where we choose the minus sign as
\chi(t)
is decreasing with
t
. By separating variables and imposing
\chi(T)=0
, we get
F(\chi,\chi_{0})\equiv\int_{0}^{\chi}d\chi^{\prime}~\sqrt{A(\chi^{\prime},\chi_{0})}=\sqrt{c}~(T-t)\,.
(28)
By setting
t=0
, we find
\sqrt{c}=\frac{F(\chi_{0},\chi_{0})}{T}\,,
(29)
yielding
\frac{F(\chi,\chi_{0})}{F(\chi_{0},\chi_{0})}=1-\frac{t}{T}\,.
(30)
For large
\chi_{0}
, we find
F(\chi_{0},\chi_{0})\approx\sqrt{\frac{b}{m}\Gamma\left(2-\frac{1}{b}\right)\sigma^{2}}~~(2\chi_{0})^{1/(2b)}\,,
(31)
and
A(\chi_{0},\chi_{0})\approx\frac{\sigma^{2}+\zeta(a)}{m}\frac{\Gamma((2b-1)/b)(2\chi_{0})^{(1-2b)/b}}{b}\,,
(32)
We now just need to determine
\chi_{0}
. We set to zero variations with respect to
\chi_{0}
in Eq. (
23
), yielding (note that
\mathcal{L}
is also a function of
\chi_{0}
)
-2f_{a+b}(2\chi_{0})-\frac{\partial\mathcal{L}}{\partial\dot{\chi}}(t=0)+\int_{0}^{T}dt~\frac{\partial\mathcal{L}}{\partial\chi_{0}}(t)=0\,.
(33)
We compute term by term. Using Eq. (
27
), we find
\frac{\partial\mathcal{L}}{\partial\dot{\chi}}(t=0)=2\dot{\chi}(0)A(\chi_{0},\chi_{0})=-2\sqrt{c~A(\chi_{0},\chi_{0})}\,.
(34)
Additionally,
\frac{\partial\mathcal{L}}{\partial\chi_{0}}=-2\frac{\dot{\chi}^{2}}{m}f_{a+b}(2\chi_{0}-2\chi)f_{2b}(2\chi)=2\frac{\dot{\chi}}{m}\frac{F(\chi_{0},\chi_{0})}{T}\frac{f_{a+b}(2\chi_{0}-2\chi)f_{2b}(2\chi)}{\sqrt{A(\chi,\chi_{0})}}\,.
(35)
Combining everything together, the condition for
\chi_{0}
reads
-\frac{\sqrt{m}T}{F(\chi_{0},\chi_{0})}f_{a+b}(2\chi_{0})+2\sqrt{f_{2b}(2\chi_{0})(\sigma^{2}+\zeta(a))}-2\int_{0}^{\chi_{0}}d\chi~\frac{\sqrt{f_{2b}(2\chi)}f_{a+b}(2\chi_{0}-2\chi)}{\sqrt{\sigma^{2}+f_{a}(2\chi_{0}-2\chi)}}=0\,.
(36)
We would like to analyze this equation in the large-
\chi_{0}
regime. The last term can be approximated as
\int_{0}^{\chi_{0}}d\chi~\frac{\sqrt{f_{2b}(2\chi)}f_{a+b}(2\chi_{0}-2\chi)}{\sqrt{\sigma^{2}+f_{a}(2\chi_{0}-2\chi)}}\approx\int_{0}^{\infty}dt~\frac{\sqrt{f_{2b}(2\chi_{0}-2t)}f_{a+b}(2t)}{\sqrt{\sigma^{2}+f_{a}(2t)}}\approx\sqrt{\frac{1}{b}\Gamma\left(2-\frac{1}{b}\right)}~C~(2\chi_{0})^{-1+1/(2b)}\,,
(37)
where
C=\int_{0}^{\infty}dt~\frac{f_{a+b}(2t)}{\sqrt{\sigma^{2}+f_{a}(2t)}}=\sqrt{\sigma^{2}+\zeta(a)}-\sigma\,.
(38)
Finally, the condition for
\chi_{0}
reads
-\Gamma((a+b-1)/b)(2\chi_{0})^{(1-a-b)/b}/b+\frac{F(\chi_{0},\chi_{0})}{T}\sqrt{\frac{\sigma^{2}}{m}\frac{\Gamma(2-1/b)(2\chi_{0})^{(1-2b)/b}}{b}}=0
(39)
leading to
\chi_{0}\approx\frac{1}{2}\left[\frac{m}{b\sigma^{2}}\frac{\Gamma\left(\frac{a+b-1}{b}\right)}{\Gamma\left(2-\frac{1}{b}\right)}\right]^{b/a}T^{b/a}\,.
(40)
Note that when
b>a
(hard phase),
\chi_{0}
grows superlinearly and hence
\eta(0)
diverges in
T
at early times. In this case, the additional constraint
\eta(t)<\eta_{\max}
must be imposed.
Eq. (
27
) can be solved explicitly in the scaling limit where
t
and
T
are large with
t/T
fixed. In this limit, both
\chi(t)
and
\chi_{0}-\chi(t)
are large and hence
A(\chi,\chi_{0})\approx\frac{\sigma^{2}}{m}\frac{\Gamma((2b-1)/b)\chi^{(1-2b)/b}}{b}
(41)
Therefore, Eq. (
27
) can be rewritten as
\dot{\chi}(t)\propto-\chi(t)^{1-1/(2b)}\,,
(42)
yielding
\int_{0}^{\chi(t)}d\chi^{\prime}~\chi^{\prime 1/(2b)-1}\propto-\int_{T}^{t}dt^{\prime}\,.
(43)
Finally we obtain
\chi(t)\approx\chi_{0}(1-t/T)^{2b}\,.
(44)
Finally, since
\eta(t)=-\dot{\chi}(t)
, we find
\eta(t)\approx\frac{2b\chi_{0}}{T}(1-t/T)^{2b-1}\,,
(45)
valid in the easy phase
bt_{s}\,,\end{cases}
(46)
where the switching time
0a
, the first term will dominate, implying
t_{s}\approx T
to leading order. If
ba
and compute the first-order corrections to
\tau_{s}\equiv t_{s}/T\approx 1
.
Using Eq. (
46
), we find
\displaystyle L_{T}-\sigma^{2}\sim T^{-(a-1)/b}f_{\rm Bias}(\tau_{s})+\frac{\sigma^{2}}{m}T^{-(b-1)/b}f_{\rm Var}(\tau_{s})\,,
(48)
where
f_{\rm Bias}(\tau_{s})=\left[\tau_{s}+\frac{1-\tau_{s}}{2b}\right]^{-(a-1)/b}\,,
(49)
and
f_{\rm Var}(\tau_{s})=\left[\frac{b}{b-1}\left(\left(\frac{1-\tau_{s}}{2b}\right)^{-(b-1)/b}-\left(\tau_{s}+\frac{1-\tau_{s}}{2b}\right)^{-(b-1)/b}\right)+(2b)^{(2b-1)/b}(1-\tau_{s})^{-(b-1)/b}\right]
(50)
Note that the variance second term is an increasing function of
\tau_{s}
, confirming that in the easy phase
ba
, we consider corrections
\tau_{s}\approx 1-\epsilon
and expand to leading order for small
\epsilon
, yielding (up to constants)
\displaystyle L_{T}-\sigma^{2}\sim T^{-(a-1)/b}+T^{-(a-1)/b}\epsilon+T^{-(b-1)/b}\epsilon^{-(b-1)/b}\,.
(51)
Minimizing this expression over
\epsilon
, we identify the scaling
\epsilon\sim T^{-(b-a)/(2b-1)}\,.
(52)
Overall, this argument predicts that
t_{s}\approx T(1-cT^{-(b-a)/(2b-1)})
(53)
for some constant
c
. Figure
7
shows that this prediction agrees with the result obtained by optimizing the full dynamics with CasADi (in that case, for a schedule
\eta(t)
we define
t_{s}
as the first time at which
\eta(t)=0.95)
. As a result, the loss scales as
\displaystyle L_{T}-\sigma^{2}\sim T^{-(a-1)/b}+\sigma^{2}T^{-(b-1)/b}\epsilon^{-(b-1)/b}\sim T^{-(a-1)/b}+\sigma^{2}T^{-(b-1)(a+b-1)/(b(2b-1))}\,.
(54)
Figure 7
:
Fraction
1-t_{s}/T
of the total training time spent in the annealing regime. The switching time
t_{s}
is defined here as the time at which the schedule
\eta^{*}(t)
crosses the level
0.95\eta_{\max}
for the first time. Same parameters as in Fig.
2
a.
Appendix C
Comparison with benchmarks
C.1
Constant learning rate
In the case of constant learning rate
\eta_{T}(t)=\eta_{T}
, the integral over
t
in Eq. (
22
) can be computed, leading to the simplified expression
L_{T}-\sigma^{2}\sim(\eta_{T}T)^{-\frac{a-1}{b}}+\frac{\sigma^{2}\eta_{T}}{m}\,.
(55)
Optimizing over
\eta_{T}
, we find
\eta_{T}\sim T^{-(a-1)/(a+b-1)}
and
L_{T}-\sigma^{2}\sim T^{-(a-1)/(a+b-1)}
.
C.2
Power-law schedules
In this section, we investigate the optimal power-law schedule
\eta(t)\sim t^{-\delta}
, with
0<\delta<1
. We start from the expression
L_{t}-\sigma^{2}\sim\left[\int_{0}^{T}ds\ \eta(s)\right]^{-\alpha}+\frac{\sigma^{2}}{m}\int_{0}^{T}dt\ \eta(t)^{2}f_{2b}(\chi(t))=\text{Bias}(t)+\text{Variance}(t)\,,
(56)
where
\alpha=(a-1)/b
and
\text{Bias}(t)=\left[\int_{0}^{T}ds\ \eta(s)\right]^{-(a-1)/b}\sim T^{-\alpha(1-\delta)}\,.
(57)
The variance integral can be decomposed in two contributions: one from the “bulk” of the integral and one from the region close to the upper limit
T
.
\text{Variance}(t)=\int_{0}^{T}dt\ \eta(t)^{2}f_{2b}(\chi(t))\approx\int_{0}^{T-\tau}dt\ \eta(t)^{2}f_{2b}(\chi(t))+\int_{T-\tau}^{T}dt\ \eta(t)^{2}f_{2b}(\chi(t))\,.
(58)
Where we choose
\tau
such that
\chi(T-\tau)\sim\mathcal{O}(1)
, leading
\chi(T-\tau)\equiv\int_{T-\tau}^{T}\eta(t^{\prime})dt^{\prime}\sim T^{1-\delta}-(T-\tau)^{1-\delta}\approx\tau T^{-\delta}\,,
(59)
so that
\tau\sim T^{\delta}
. As a consequence, for
tT-\tau
f_{2b}(\chi(t))\approx\text{constant}
. Therefore,
\text{Variance}(t)\sim T^{-\gamma(1-\delta)}\int_{0}^{T-\tau}dt\ t^{-2\delta}+\int_{T-\tau}^{T}dt\ T^{-2\delta}=T^{-\gamma(1-\delta)}\frac{T^{1-2\delta}-1}{1-2\delta}+T^{-\delta}\,.
(60)
Therefore,
\delta
must be chosen to minimize the combination of four terms
L_{t}-\sigma^{2}\sim T^{-\alpha(1-\delta)}+T^{-\gamma(1-\delta)}+T^{-\gamma(1-\delta)+1-2\delta}+T^{-\delta}\,,
(61)
where we recall that
\alpha=(a-1)/b>0
and
1<\gamma=2-1/b<2
. We find
\delta=\min\left[\frac{\alpha}{\alpha+1},\frac{\gamma}{\gamma+1}\right]
(62)
with a crossover between the two regimes at
a=2b
and
L_{T}-\sigma^{2}\sim T^{-\delta}\,.
(63)
Note that for the optimal schedule
L_{T}-\sigma^{2}\sim T^{-\min((a-1)/a,(a-1)/b)}
(64)
so that there is an exponent gap between the optimal and the optimal power law schedules for all
a,b>1
.
We next consider the scaling of power-law schedules with
T
-dependent prefactors of the form
\eta(t)\sim T^{-\nu}t^{-\delta}
. Following the same steps as before, we find
L_{T}-\sigma^{2}\sim T^{\alpha\nu-\alpha(1-\delta)}+T^{-2\nu-\gamma(1-\delta-\nu)}+T^{-2\nu-\gamma(1-\delta-\nu)+1-2\delta}+T^{-\delta-\nu}\,.
(65)
Denoting
x=\delta+\nu
, we can rewrite
\mathcal{L}(T)\sim T^{-\alpha(1-x)}+T^{-(\gamma+(2-\gamma)x-2\delta)}+T^{-\gamma+1-(2-\gamma)x}+T^{-x}\,.
(66)
Therefore, we can choose
\delta=0
, leading to a the same scaling behavior as the constant-in-
t
optimal-in-
T
schedule.
C.3
General scaling form
In this section, we investigate the performance of scaling form schedules
\eta(t)=T^{-\xi}g(t/T)\,,
(67)
for
\xi\geq 0
. Note that in the easy phase
b1
the bias increases with
T
), we get that
\tau^{*}
is determined by the asymptotic behavior of
g(\tau)
for
\tau\to 1
. Assuming
g(\tau)\sim(1-\tau)^{\delta}
with
\delta>0
, we get
(1-\tau^{*})\sim T^{-(1-\xi)/(1+\delta)}\,.
(73)
We can then split the variance term into a
“bulk” component for
\tau<\tau^{*}
and an “edge” component for
\tau>\tau^{*}
, leading to
\text{Variance}(T)\approx\text{Bulk Variance}(T)+\text{Edge Variance}(T)\,.
(74)
The bulk contribution reads
\text{Bulk Variance}(T)\sim T^{1-2\xi}\int_{0}^{\tau^{*}}d\tau~g^{2}(\tau)~\left(T^{1-\xi}\int_{\tau}^{1}d\tau^{\prime}~g(\tau^{\prime})\right)^{-\gamma}\,.
(75)
For
\delta>(\gamma-1)/(2-\gamma)=b-1
the integral over
\tau
converges as
\tau^{*}\to 1
and hence
\text{Bulk Variance}(T)\sim T^{1-2\xi-\gamma(1-\xi)}\,.
(76)
However, if
\deltab-1
, we get
L_{T}-\sigma^{2}\sim T^{-\alpha(1-\xi)}+T^{1-2\xi-\gamma(1-\xi)}+T^{-(\delta+\xi)/(\delta+1)}\,,
(80)
while for
\deltaa
(hard phase). The corresponding scaling laws are
L_{T}-\sigma^{2}\sim T^{-(a-1)/a}
for
ba
. The scalings match those of the optimal schedule.
C.3.1
The edge term is subleading for the optimal schedule
In the easy phase
ba
. Recall that in this phase the optimal learning rate schedule is (taking
\eta_{\max}=1
)
\eta(t)=\begin{cases}1\quad&\text{ for }tt_{s}\,,\end{cases}
(82)
with
\delta=2b-1
and
T-t_{s}\sim T^{1-(b-a)/(2b-1)}
. The edge boundary
t^{*}
is determined by the condition
\chi(t^{*})=1
, yielding
\chi(t^{*})=\int_{t^{*}}^{T}dt^{\prime}\eta(t^{\prime})=\int_{t^{*}}^{T}dt^{\prime}\left(\frac{1-t^{\prime}/T}{1-t_{s}/T}\right)^{\delta}=T\epsilon^{-\delta}(1-\tau^{*})^{\delta+1}=1\,,
(83)
where we have assumed
t_{s}1-\tau^{*}
, confirming that
t_{s}\ ,\ V_{k,t}=\left\ ,\ R_{k,t}=\left<\Delta_{k,t}v_{k,t}\right>
(93)
where the average is computed over the random samples from each minibatch. These three variables evolve according to the following linear dynamics
\displaystyle C_{k,t+1}=C_{k,t}-2\eta_{t}R_{k,t}+\eta_{t}^{2}V_{k,t}
\displaystyle V_{k,t+1}=(1-\beta_{t})^{2}V_{k,t}+2\beta_{t}(1-\beta_{t})\lambda_{k}(R_{k,t}-\eta V_{k,t})+\beta_{t}^{2}\left[\frac{m+1}{m}\lambda_{k}^{2}C_{k,t+1}+\frac{1}{m}\lambda_{k}\sum_{\ell}\lambda_{\ell}C_{\ell,t+1}+\frac{\sigma^{2}}{m}\lambda_{k}\right]
\displaystyle R_{k,t+1}=(1-\beta_{t})(R_{k,t}-\eta_{t}V_{k,t})+\beta_{t}\lambda_{k}C_{k,t+1}
(94)
We note that due to the time indexing that we adopted above, the right hand side for the equations defining the dynamics for
R_{k,t+1}
and
V_{k,t+1}
depend on
C_{k,t+1}
rather than
C_{k,t}
(though of course this can be substituted).
2
2
2
We find this convention yields better stability than defining the dynamics as
\bm{\Delta}_{t+1}=\bm{\Delta}_{t}-\eta_{t}\bm{v}_{t}
where
\bm{v}_{t}=(1-\beta_{t})\bm{v}_{t-1}+\beta_{t}\bm{g}_{t-1}
.
The loss function dynamics, as before, can be computed from
C_{k,t}
\displaystyle L_{t}-\sigma^{2}=\sum_{k}\lambda_{k}C_{k,t}.
(95)
We use the above dynamics for
\{C_{k,t},R_{k,t},V_{k,t}\}
.
Appendix F
Optimal Control Implementation
To determine the optimal learning rate schedules numerically, we formulate the problem as a discrete-time optimal control problem governed by the recursive evolution of
c_{t,k}
(Eq. (
4
)). We employ a direct single-shooting method to transcribe this control problem into a non-linear programming (NLP) problem. In this formulation, the control inputs (the learning rate
\eta_{t}
and optionally the batch size
m_{t}
) are treated as the primary decision variables. The state trajectory is not included in the set of decision variables. The objective function, defined as the terminal generalization error
L_{T}
, is thus expressed as a direct function of the initial conditions and the sequence of control inputs.
We implement this optimization framework using CasADi
(
1
)
, which performs automatic differentiation to efficiently compute the necessary gradients of the objective with respect to the control trajectory. The resulting NLP is solved using IPOPT (Interior Point OPTimizer), a primal-dual interior-point method. To ensure computational efficiency for large horizons, we configure the solver to use a limited-memory approximation of the Hessian and the MUMPS linear solver for the internal step computations. The implementation of our optimization framework is available in the supplementary material.