On the stability of gradient descent with second order dynamics for time-varying cost functions
Authors: Travis E Gibson
Sawal Acharya
Anjali Parashar
Joseph Emilio Gaudio
Anuradha Annaswamy
Venue: Accepted by TMLR ()

Abstract: Gradient based optimization algorithms deployed in Machine Learning (ML) applications are often analyzed and compared by their convergence rates or regret bounds. While these rates and bounds convey valuable information they don’t always directly translate to stability guarantees. Stability and similar concepts, like robustness, will become ever more important as we move towards deploying models in real-time and safety critical systems. In this work we build upon the results in Gaudio et al. 2021 and Moreu & Annaswamy 2022 for gradient descent with second order dynamics when applied to explicitly time varying cost functions and provide more general stability guarantees. These more general results can aid in the design and certification of these optimization schemes so as to help ensure safe and reliable deployment for real-time learning applications. We also hope that the techniques provided here will stimulate and cross-fertilize the analysis that occurs on the same algorithms from the online learning and stochastic optimization communities.

Published in Transactions on Machine Learning Research (02/2025)
On the stability of gradient descent with second order dy- namics for time-varying cost functions
Travis E. Gibson1.2344 1.3.,4,, Sawal Acharya20, Anjali Parashar', Joseph E. Gaudio', and Anuradha M. Annaswamy*
Massachusetts Institute of Technology Brigham and Women's Hospital
Harvard Medical School
BBoadd Institute MIT and Harvard SStanford University
* "Correpsondence:
Reviewed on OpenReview:
Abstract
Gradient based optimization algorithms deployed Machine Learning (ML) applications are often analyzed and compared by their convergence rates regret bounds. While these rates and bounds convey valuable information they don't always directly translate to stability guarantees. Stability and similar concepts, like robustness, will become ever more important as we move towards deploying models in real-time and safety critical systems. In this work we build upon the results in Gandio et al. 2021 and Moreu & Annaswamy 2022 for gradient descent with second order dynamics when applied explicitly time varying cost functions and provide more general stability guarantees. These more general results can aid in the design and certification of these optimization schemne as to help ensure safe and reliable deployment for real-time learning applications. We also hope that the techniques provided here will stimulate and cross-fertilize the analysis that occurs on the same algorithms from the online learning and stochastic optimization communities.
1 Introduction
For data-driven technologies to be reliably deployed in the real world they will inevitably need robustness guarantees. Those guarantees, while practical, will also aid in the formal certification of these methods. Robustness guarantees will be even more important for Safety Critical and Real-Time Systems (SCS RTS). Part of these robustness guarantecs will assuredly be related to cross-validation. There are also many scenarios where we envision the optimization scheme itself would also need have robustness guarantees. Here, specifically,
interested in the robustness guarantees of Gradient Descent (GD) based optimization schemes. Consider for instance systems that learn in real-time while they are deployed, like self-driving car that catalogues new events and simultancously labels and retrains the model (semisuupervised) on the fly, an aircraft control algorithm that updates the feedback control gains in flight. In both these instances one does not have the luxury of tuning learning rates offline or performing episodic learning and control, but nceds be assured that the model training process itself stable real-time. By stability here we are referring to the definitions from dynamical systems and control theory (Massera, 1956), not the algorithmic stability definition from Bousquet & Flisseeff (2002).

---

Published in Transactions on Machine Learning Research (02/2025)
Within control this field of study falls under the moniker of Adaptive Control (AC).' The closest area within ML. where models are trained in real-time is fairly nascent but aptly named Real-Time Machine Learning (RTML) (DARPA; NSF).² 2 With these applications in mind we are interested in analyzing the stability of gradient descent algorithms with second order dynamics when applied to time varying cost functions. To simplify nolation we will refer to GD with second order dynamics as simply second order GD (nol to be confused with the order of the gradients that are taken).
GD and its variants have rightfully attracted significant attention given their success the workhorses for training deep neural networks (Goodfellow et al., 2016). The accelerated gradient methods first introduced by Polyak (1964) and Nesterov (1983) have had renewed interest (Su et al., 2014; Wibisono et al., 2016), as well as the expanded adoption and innovation within stochastic gradient descent methods and online learning (Cesa-Bianchi Bianchi & Lugosi, 2006; Shalev-Shwarzz, 2012; Hardt et al., 2016; Bottou et al., 2018). The most popular optimization schemes for deep models combine ideas from stochastic gradient descent, the classic accelerated methods with momentum (Tieleman & Hinton, 2012), and adaptive gradient mothods (Duchi et al., 2011), e.g. Adam (Kingma & Ba, 2015). Methods like Adam are analyzed with Regret Analysis (RA) which frames the analysis in terms of minimizing some accumulated cost over time apposed to the direct analysis of something like a Lyapunov function. We note that there are other examples where Stochastic GD with Momentum (SGDM) are analyzed with Lyapunov functions (Liu et al., 2020), bringing those works more in line with the style of analysis presented in this work. See $4 for a detailed discussion about RA and SGDM.
Orthogonal work to the above, that also investigated higher order gradient descent techniques, occurred within the control theory community under the name of High-order Tuner (HT) (Morse, 1992). Prior to the introduction of the HT by Morse, parameter updates used in model reference adaptive control were typically defined using only first order derivatives (i.e. if the adaptive parameter is f(t) then the update would be d0/ = ..... Morse showed how to construct update laws for adaptive control parameters where the time derivative could be any arbitrary order n, (i.c. d'0/de ft" = ..... Note that the update law is what one uses to "tune" the adaplive control parameters, hence the name "high-order Luner".
Gaudio et al. (2021) and Moreu & Annaswamy (2022) recently showed that a HT could be parameterized to look like the popular accelerated methods first introduced by Nesterov (1983) and that in turn, one could study their stability when applied to explicilly time varying functions. Our work picks up from here. The contributions of this work include streamlined stability proofs for time varying smooth convex functions where prior art's proofs were for linear regression models only (Gaudio et al., 2021) or for more general functions but with hyper-pane hyper-parameters that were fixed in time and with exceedingly strict constraints (Moreu & Annaswamy, 2022). Specifically, our analysis demonstrates that a simpler discrete time parameterization of the HT is possible (coinciding with Nesterov form 11 as it is sometimes referred to (Ahn & Sra, 2022)), a different Lyapunov candidate can be used, and that together these allow for a less conservative bound on the (now vareing paper-parametess..
This paper is organized as follows. In Scction 2 we formally state our problem along with the major assumptions stated explicitly. In Section 3 we present our main theoretical results. Section 4 provides a detailed discussion around the literature. This is followed by Section where we provide additional simulations. In Scction we discuss acceleaatinn within the context of time varying objective functions. We close with our conclusions in Section 7.
2 Problem Statement and Update Rule
We consider the following optimization problem, min f(()) where for every time i, fe RN + R. The subscript t denotes the time variation in f((-) which could occur for fixed cost function but with streaming
Here we are referring to AC that is simultaneously updating parameters while controlling, like Model Reference Adaptive Control (MRAC) (Narendra & Annaswamy, 2012; Toannou & Sun, 2012), not the area of AC that has the learning phase and the deployment phase separate, i.c cpisodic learning (Hazan & Singh, 2022; Tsiamis et al., 2022).
2Contimous Learning (CL) and Lifelong Learning (LL) (Chen & Liu, 2018; Parisi et al,, 2019) are similar in name to RTML, but CL and I.I. are primarily concerned with concepts like catastrophic forgetting (MeCloskey Cohen, 1989) with an eye toward learning new things without forgetting what you learned in the past.
2

---

Published in Transactions on Machine Learning Research (02/2025)
data or in scenarios where the objective function itself changes over time. The algorithm we study in this report falls under the umbrella of what we are calling High-order Tuner (HT) which are gradient descent. algorithms with second order dynamics similar in structure to the popular momentum methods, but with explicithy time varying cost functions.
The HT studied here parameterized as follows
3; = B. + (1 - -B)y
(Ia)
3/++ It a ((,))
(1b)
-++1 2: 1/ (2x))
(1c)
where at, Bt, and T/ are all (potentially) time varying hyper-parametert This is almost identical to Nesterov (2018) with the significant difference being that the functions ft are explicitly time varying.
For ease of discussion we will use the following definitions
M1
Th :=
Vt N
3. 1 3t
Pr := pr
(2)
where Th, Me, Be, and N₂ are the free design parameters. We will refer to N, as the normalization parameter. All norms, |1-II, are 2 norms. We will use the following definitions and assumptions throughout the paper. Definition 1 (convex). A function f TRNN IR is convex if Va, RR and A E [0.
f(xx + (1 A)y) S (z) + (1 ())())
Definition 2 (smooth). A continuously differentiable function f : R + IR is L-smooth if there exists an L < 30 such that Vz, y E RVV, then following holds [[( - ff())) - L|| -yll-
Definition 3 (strong convexity). A differentiable function / RV + R is a-strongly convex if Va, E N and 2 0, then following holds f(y) 2 f()) Vf(=) m) + -=|l²-
Assumption 1. For each the function ft is an L--mmooth convex function and furthermore the sequence L is bounded, i.e. Lt E loo (see Definitions and 2).
Assumption 2. There exists an x" such that fa(x*) = min f((z) for all t. Assumption 3. For each an upper bound on the smoothness of the function is obtained, N₂ 2 Lt; for explicit use in the HT, see Equation (2). If L, is bounded then N, is bounded as well.
Remark 1. Assumptions and allow for arbitrary variation in the smoothness of the time varying function, but the smoothness, and therefore the bound on the smoothness, can not grow arbitrarily large. If we did allow arbitrarily large smoothness bounds then we will stilll be able to prove stability of our algorithm but not its asymptotic convergence. In order for Assumption 3 to be satisfied one will need practical means of estimating the smoothness, Lt, of the function. For twice differentiable functions the trace of the Hessian is elficiently computable and can be used as a bound for the smoothness." Finally, we note that in order to obtain asymptotic convergence guarantees we need the optimal point x" to be fixed, but given that our results are grounded in a stability analysis framework (all signals remain bounded with arbitrary initial conditions), the optimal point can actually change over time and stability is maintained (see $3.4).
3 Stability for time varying functions
Our objective to provide steamlided,, tractable, and complete proofs that fit. within the main text. We will not begin with the most general results first, instead starting with a less general result that is easier follow, and then proceeding onto the general result. In section $3.1 present our first result for smooth
Forr twice differentiable functions and by the intermediate value theorem have that Vf(x) - vf(y) fz)() v) for some [x, v). The hessian 2 of a convex function is a positive semi-definite (symmetric) matrix, and for a the induced 2-norm [=) = Amax A (=)) where Amax denotes the largest eigenvalue. Computing the eigenvalues of a matrix requires full knowledge of the matrix, but if we simply want to bound the eigenvalues we recall that the trace of square matrix is equal the sum of its eigenvalues. This taken together results in the hound |\( < S supec(zeo trace( 2 f(e)) Jar vll
3

---

Published in Transactions on Machine Learning Research (02/2025)
convex functions (Proposition 1), with the more general results coming with Theorem 1 in $3.2 Then in $3.3 we present our analysis for strongly convex lunctions with Proposition 2. For the strongly convex setting obtaining the exponential convergence rate in a simple form necessitates some degree of simplification so we use the simplified setting of Proposition for the strongly convex setting is straightforward but challenging to present in a compact form without the introduction of a significant number of intermediate variables. We close with discussion on time varying optimal points.
our presentation of Proposition 2. A completely general bound
3.1 Warm-up direct proof for smooth convex
Proposition 1. Let fo satisfy Assumptions 1-3. For the HT defined in Equation (1) with arbitrary initial conditions (æo: yo. 20), N, 2 Lt (fe is L, smooth by assumption), and the following three conditions satisfied
3: E [0.1]
(3a)
Pe E [c,1], E>0
(3b)
7t = 2/4.
(3c)
then
V - - x +1131 2el?
(4)
is Lyapunov candidate and it follows that V₁ loo. Furthermore, lime-+00 [fc(x)) f((x")] 0.
Proof. To demonstrate that V, bounded we will first show that AV = V141 V2 S 0. The basic strategy is to obtain bound for AV+1 a quadratic form of the vectors Vfe()r)) and (æ,, - 2t), making as few intermediate bounds as possible until the quadratic form is obtained, for which we then complete the square as to obtain constraints the free design paramcters. The final ingredicnt is simple argument regarding bounded monotonic sequences.
We begin by expanding the time step ahead Lyapunov candidate V/+1 = =||=+11 x²11 + +118:+111111 Z1+1 from (4) by substituting the update for yst1 from (1b) and z4+1 from (1c) and noting that xt 2$ = Be 2z from (1a) where Bg 3,, as defined (2), we obtain
V41 = =1|z| =111 + (n²² + (n [ 2m ([xx) -x*)
+ +||æ: 2.112 2(1 az)) Vi))) 2z). (5)
Expanding -2n, (z) - xx)) as 21 (T( xc 3zz - x²) and noting that
( - x²) S f((x=)= - f(((x))
2T. [[
from Corollary A.8.1, it follows that
-2n, (((x)) -x")== s 2T (i(x)) (xx 21) --_((((('--))))) Th [[[(()))
(6)
Applying the bound Equation (6) to Equation (5) we have
V41 < 1| =x112= + T/ + (n -0)² 1)
L, [[ 2n((fx)) f(xx))
(7)
+ +|[x, zel 2(27) az) fx(x)) 21).
Now turning our attention to V₁ and rewriting the sccond component to be in terms of x; 2t we have
V =11
2=11 1+.322 ==11=++,,+
2
(8)
4

---

Published in Transactions on Machine Learning Research (02/2025)
where we have used the fact that 2e- 21 (1 -B)((v 2,) from Equation (1a). Subtracting (8) from (7) it follows that
11 + +n) -a,)²- -7: [(x,)) ( fe(
AV 1
[,
(9)
+ B-²) ||02 z111² + 2(21; - Vi. z.).
We pause to define some variables
a, = (((())))
c1 == : + (7t - (Mx) -77
6g = 3,2
No
1t (f((x²) f((w))
b. Dt 2t
C2 = 2(2%/ - pt)
C4 N
Using the above definitions and the fact that N; 2 L (Assumption 3) it follows that
AV+1 S sallasl? + c2a + cs [blbal +c.-
Completing the square we have
c 4e1
AVe sala
C2 bi +
+
Cs
|bbl|
+ co.
(10)
201
In order for AV S O we need C C4 and Gj 4e ca to be less than or equal zero (which in turn implies that C3 is less than zero as well). The coefficient ca is always less than zero because of the optimally of x*. The coefficients c3 as well as the expression cž 4cic3 are all less than zero given the conditions outlined in (3). It thus follows that
N₂ AV & 2 2 (fi(x') - f((x:)) < Va, + x".
(11)
It then follows that -x==x") and (3/ z4) z4) are bounded by the definition of V2 in (4). With x' fixed and clearly bounded it then immediately follows that yr, 2 E Ex. From (1a) and the boundedness of Br (by construction) it then follows that y: E lxo. From Definition 2 (smooth) and from Assumptions 1-3 then follows that the sequence [[(x)))] is bounded as well. Finally, given that smooth functions on compact sets are bounded we have that f(x)) is boundod and therefore [f( fe()))] E lo as well. With that all signals in the model are bounded Fe, Vt. Ze: (x;), V Va(e)) E fee.
Finally to prove convergence of the cost function to its minimum (i.c. partial sums of positive values). By Assumption 1 L, is bounded and then by Assumption 3 we choose an N₂ that is bounded as well. Therefore, there exists a positive N such that N 2 N, for all t. Finally, recall from (3c) that 7 E 1/2), Using these bounds for N₂ and nt and Equation (11) it follows that
will use properties of monotonic sequences
N AV S f((x)) ((()))
(12)
Summing both sides, multiplying by -1 and recalling that V2 is a non-increasing positive sequence, follows that
a - f((x') 1=0
N
N Vo 0o N [1o Vi+1l S -
Σ AV
(13)
t=
With a, a bounded monotonic sequence it follows that lim Or exists (Rudin, 1976, Theorem 3.14) and therefore lim; [f((x.) - f(x=)][== 0.
Remark 2. Note that we did not begin by providing successfully more refined bounds for f((w,) - f((")) )
Instead we began with a Lyapunov candidate that explicitly bounds the states of the optimizer (4), and then by summing the bound on the time difference of the Lyapunov candidate we achieve the desired result in (13). For the interested reader this approach also extends to innuus time settings where the last step
5

---

Published in Transactions on Machine Learning Research (02/2025)
(under appropriate conditions) invokes Barbälat's Lemma (Farkas & Wegner, 2016). When fi = is not time-varying it is commonly incorporated into the Lyapunov candidate directly (Liu et al., 2020, Equation(5)); (Ahn & Sra, 2022, Equation (2.3)). When ft is allowed to be time varying, however, it may not satisfy all the conditions to be a Lyapunov function. Namely, a Lyapunov function has to be lowerbounded by a time-invariant non-decrescent function of the parameter you want to show is bounded. For instance if you have time varying Lyapunov candidate Vi())) you will need to show that there exists a non-decrescent function where a(0) 0 and a([=]]) s (x) for all æ 0 (Kalman & Bertram, 1960, Theorem 1). With the cost function fo now explicitly varying over time the above condition can easily be violated.
3.2 A more general proof for smooth convex
Theorem 1. Let Jt satisfy Assumplions 1-3. For the HT defined Equation (1) with arbilrary initial conditions (æo, yo: 20}. N₂ 2 Le (ft Lt smooth by assumption) and with the algorithm Saper-parumeters {nh Me, Be) along with the analysis porameters de [0. - c1,5 E (0) 0 chosen such that
c
C5 0, and C7 4os
0
(14)
where
Cs = ft + E441 -me² - (1+ d0
C6 2 - 14) + +
(15a)
C7 = E1-1 Er
(15b)
then
W. =1, - x x²11² + Eelly. - -112
(16)
is a Lyapunov candidate and follows that We E loc. Purthermore, lim [f((2)+1) - fe(x*)] = =0.
Proof. We begin by expanding the time step ahead Lyapunov candidate W441 = | - x01 11? +
S4+1 yt++ z+lll by substituting the update for yot1 from (Ib) and 2141 from (1c) and noting that
Φr 2t = Bels 21) from (la) where 3r = Br, defined in (2), we get the following
W4+1 = =1|2 =x1 (nz + E a.) 3)) 2n, (.. xx)
+ E141 [141||22- - 11 + E141((m - as V (2))
22). (17)
Expanding -2m fx(( (zt - xx")====- as V
fx(, T (z) + 2, xx, - x²) and noting that
V((()) (x: - xx) s (1 >e)(f((=") - [((xx)) 1 + d [
2L
from Lemma A.9, it follows that
2np (a(x)) - x²) 2m, fe ( 2.) + xe)((f(((*)) - -f((z))
(1 + Ar) [
(18)
L
Substitution of Equation (18) into Equation (17)
W41 S (1i + Ent1(1 - aa)² (1 + de)mi [xx))]] + + - Ax)m((f((x)) - f((x)))
Lr
(19)
+1|a, x w011 + S.+1|/0, - =1ll2 + 1 ar) 2n fxx))) T (x: z1).
Turning our attention to We and rewriting the second component to be in terms of we have
W. =||z xx
(20)

---

Published in Transactions on Machine Learning Research (02/2025)
where we have used the fact that xt- -1- (1) 21) from Equation (la). Substracting (20) from (19)
with AW W4+1 - Wt it follows that
(1+ de)mI [|>Se(a)))] + 2(1 - Ax)ma - - Je(()))
AW+1 < nh + Ee+1(1) - (++))==
Lt
+ (Se.1 - (6..11)6,1.))) 1:00= - -z1l1 [E141 2111 - ove) + 2mp V))x)) (a; -z).
Recall the definitions a= 1 (att and b =-== zt with cs, Co, C7 defined in (15) along with No
Os := (1 de (((x")){(xx)))
No
and the fact that N, 2 Le, then it follows that AW S co collaill + coa b. + c7 c7|lbell + cs. Completing the
square we have AW S os
+ ca by
+
c7
ف lbbll cs. By the conditions in (14) it follows that
AW+1 $ (1 - deMr (fi(x*) fr(x))) < Vx, + x".
N₂
Following the same steps as outlined at the end of the proof of Proposition it follows that at == Σx Ei=olf(are) f((x")] is a bounded monotonic sequence and therefore lim, [xt()) - fa(x*)] =0
With slightly modified Lyapunov candidate (compare (16) to (4)) we get the most general bound are aware of. Note however that the learning rate parameter 7t must be less than 2 for stability to hold, see (14) and (15a). We raise this point because when the function is fixed for all time (fa =f f: constant) Nesterov's accelerated method requires "/ to increase with time, 4, in unbounded fashion (i.e. Nt x t). We discuss this further in $4.2 - it is likely impossible to have a stable accelerated method like Nesterov for arbitrary time varying functions. We follow up the main theorem with a corollary that has much simpler conditions with some accompanying simulations to demonstrate the non-vacuous nature of our bounds.
Remark 3.
a
Corollary 1.1. Let fo satisfy Assumptions 1-3. For the HT defined in Equation (1) with arbitrary initial conditions (Io, yo: zub. N₂ 2 Le (fe is La smooth by assumption)
E [1, 1.5)
(21a)
Pt = 1
(21b)
Ae = 1/7
(21c)
and where the free design parameters (that only appear in the analysis) are chosen as A 1 and & 1, then all states and gradients are uniformly bounded. If we replace the above bounds with the slightly more stringent cases where the free design parameter X < 1 which in turn will require "it < 1.5 then also have lime-sxo [fr( - f((x') = O. A visualization of the slabilily conditions in (14) for the parumelers in (21) are shown in Figure 1.
We have an entire section dedicated to simulations but we didn't want to wait until the very end to demonstrate the non- vacuous nature of our results. The simulation in Figure 1(B) demonstrate that with % = 1 the HT coincides with vanilla GD. As " increases beyond 1 (with B, 1/7,, be 1) the HT (empirically) demonstratos acceleration (monochrome black/white solid lines) with the purple dashed line coinciding with > = 1.5 matching our stability analysis in Corollary 1.1. In the simulation we also changed the optimal point halfway through so as to have another window of transients where the algorithms have to converge to the new optimal value. As was previously stated in Remark 1 our stability results (bounded trajectorics for arbitrary initial conditions) hold even for optimal set points that vary over time. We will have more say about the long term behavior of the HT in Section 5.

---

Published in Transactions on Machine Learning Research (02/2025)
A
B
10t
1.0
HT (v: color bar)
0.9
10a
40
NAGD
HT (y: 1.5)
10
0.8
100
30
0.7
102
20
0.6
1001
109
0.5
1.0
1.1
1.2
1.3
1.4 1.5
20 40
60
80
100
Yt
Figure 1: The stability conditions outlined in Corollary 1.1 are nonvacuous. (A) Visualization of the sufficient conditions outlined in Equation (14) under the parameter sellingg in Equation (21). There is an asymptote at " 1.5 for the value of 4cyc7 og (green line) (B) Algorithms are optimizing the function f(( = log(a; exp(-b. 1 -)) + exp(br(x= (x)) where a₂ = 1 and b, = 7. For t < 50 = 0 and for t > 50 G = 5. This results in an optimization problem where the optimal solution x* changes from 0 to 5 at L = 50. Vanilla GD shown the dashed blue line with Nesterov Accelerated Gradient Descent (NAGD) in dashed red. For the HT with it varied from to 10 see the solid monochrome (shades of grey) lines. With ?t the optimizer coincides with GD and as Y is increased the HT begins to exhibit acceleration more closely resembling NAGD (light grey to black solid line). HT with a 1.5 shown in dashed purple. Full details provided in Appendix B.
3.3 The smooth and strongly convex setting
We close by showing exponential convergence for time varying strongly convex functions.
Proposition 2. Let fe satisfy Assumptions 1-3 as well as the additional assumption that for each t, ft is
o, strongly conver. For the HT defined in Equation (1) with arbitrary initial conditions {æo, Yo. yo. 20}, N₂ 2 L (fe is L, smooth by assumption), and the same three conditions from Equation (3) in Proposition 1 satisfied
{Be E 10, He E le, 1], > 0, = ) Then, V = I| x x=1 + +|lyt zell originally defined in (4) is
Lyapunou function which exponentially converges to zero at rate
V4+1 (1 - wr) V4
(22)
where
Povi (1
we == min (11-))(1-))) -83)
(23a)
Prst + v1 B7)
de Pt = 2 N,
and E [e,
(23b)
Proof. In order demonstrate exponential convergence with the Lyapunov function it suffices show Ve+ V. for some g. [1-1+e, e]. We will begin the proof by starting where we left off with the bound (10) in Proposition expanding the coefficients and substituting "/ ue/2 which results in
AV+1 V4+
H4 N2
(1:: f/ + 21 P4 N
||,0, =211 Me N,
(fel==) f((x)))
(24a)
< <1-
(Ji(z=)) fz(wx))
(24b)
where we dropped the first term in (24a) for the second inequality in (24b) because we typically want the learning rate ja E [e, 1] to be as large as possible and the first expression in (24a) approaches 0 as μt tends to 1. Next we will use the strong convexity assumption along with the distance to the minimizer bound provided
in Lemma A.7 for fe(x*) - fe( and we get
AV41 S (1 (1- -,-2) - 2=11 - Pe Pellac. x²1
(25)
8

---

Published in Transactions on Machine Learning Research (02/2025)
where we recall the definition of Pt from (23). The next step is to obtain bounds in terms || x'1l and ly:- - zz|l with the hopes that the upper-bound can be expressed in terms V thus allowing for some kind of bound of the form V4+1 9r V as we previously stated. We accomplish this by adding and subtracting within the norm || x - x=|| and then using the fact that It 2t Be(3/ - 21) from (la) we obtain
AV4 S (0) 1)lly - 2111 pa (B 211 23. 2))(zz - x²) + +1| x²11²).
(26)
As in our prior analysis we define intermediale vectors and scalars to simplify the expressions with
y Zt
d, = xx
v =
(note that the S 0)
(27)
and rewrite the inequality in (26) giving us the more compact inequality
AV++ S v Pi (B.llell + 23,c, +ldd)1))
We want to have an expression that negative semidefinite in terms of |ele and |[d]], which we have for ||e||.. but not yet for ||]]]. To achieve this we borrow vs E [e, c| from the expression &/ and incorporate it into the large expression in the parenthesis giving
AV++ (1 mebilll + (
2pc -
(28)
Completing the square for the component in the brackets have
(-pu8f + m
Ca +
-pp de
+ -Pt {
||d 1|d.
(29)
(-por m1/33)
(-pr3t vmf3)
Taking the second component from (29) that is solely a function of |dol? and using that to bound the expression in the brackets of Equation (28) we obtain
Prus (3) (32)
AV41 -
p..3 + 11(1 - B?) ||d:|"
(30)
Finally, we recognize from the definition of ct and de that V2 Vlcll +|ldell and from Equation (30) with a lew terms rearranged we arrive at the bound provided Equation (22).
3.4 Time varying optimal points
In Remark we eluded to the fact that while we assume fixed optimal point x", for the purposes of proving asymptotic convergence results, can actually allow for time varying æ; and still remain bounded. Specifically, for our setting one can prove that for any piecewise constant 2f with only a finite number of changes the HT remains bounded with fe(x;) converging to each new optimal point after it is changed. This holds because in our proof setting we make no assumptions about the initial conditions of the parameters or any other a priori assumptions about their boundedness. We can make this little more conerete with the following thought experiment.
Consider our problem setting with arbitrary initial conditions To, yo. 2y and an optimal æ11 to begin with. Our proofs say that we are stable and f(())) will asymptotically converge to f(()))) Now some time T we get a new optimal zं (with the subscript [2]). Importantly we do nothing to the algorithm and it just continues to run as originally defined. For analysis we now say ær; øT are our new initial conditions. Recall that our proof explicitly states that we are stable for arbitrary initial conditions and so we will still be bounded for all time with the new z and (zz) will now asymptotically converge to the new fo f((z))) as well. Using this line of reasoning the following meta-theorem holds.

---

Published in Transactions on Machine Learning Research (02/2025)
Theorem 2. Let fo satisfy Assumptions 1 and 9 where there erists a piecewise constont iं that changes in value only finite number of limes. For the HT defined in Equation (1) with arbilrary imilial condilions {æo, yo, 20}, N, 2 Lt (ft is L, smooth by assumption), and the conditions on the fepper-poremeters and further assumptions as outlined in either Propositions and 2 or Theorem 1, the parameters of the HT remain bounded for all lime. Furthermore after each successive change in the optimal poinl, Je(az)) will begin to asymptotically converge (or ae will begin to exponentially converge in the case of strongly conver) each new optimal function value (to each new optimal point).
One can go further and analyze continuously varying æ;, for instance if æt "slowly varying" (the quantity #i+1 zx is uniformly bounded) and the style of analysis presented here can be adapted to this setting well. However, some kind of robustness modification will be needed (e.g. the use of the projection operator or Icaky integration, which is called the "sigma" modification in the adaptive control literature Tsakalis & Ioannou (1987)). One can no longer prove convergence to the optimal functions or optimal point themselves, but instcad, compact regions around them (Narendra & Annaswamy, 2012, $8.6). We note that these notions of stability never enters one's mind when studying gradient algorithms with tools like regret analysis because you priori assume all the parameters and gradients are uniformly bounded before you even start the analysis, see $4.3.
4 Connections to existing literature
4.1 High-order tuner
The HT in (I) was directly inspired by Gaudio et al. (2021) which tried connect stability proof techniques for second order gradient flow methods (continuous time) to second order gradient descent methods (discrete time). The second order gradient flow algorithm under study in Gaudio et al. (2021) was i(t)+ + -ar which the authors recognized could be reparameterized as
x0 v far(())
--N, N.
(t) = Y V((((tt))
(31a)
N +(t) ((x(() (t))
(31b)
where N₁ varies over time and upper bounds the smoothness fe at cach Reparameteriztion the form in Equation (31) was essential for discovery of the Lyapunov candidate
v(I) - x11 +|| -1|=(()==(()))) (())))
(32)
What was also shown in Gaudio et al. (2021) was that the discretization of Equation (31) to
2t = 32z + (1 - f)
(33a)
Vi+1 28 N. (z.)
(33b)
#++ = 21 No Vf((x))
(33c)
was also stable and could use the same Lyapunov function (but in discrete time Vn2 = +| x. )²)) For quadratic costs and the HT in (33) they established stability with the following constraints on their free design parameters from (Gaudio et al., 2021, Theorem 4)
11
x +
8 e (0,1) 7 (0, 6(2-9) 16+
(34)
and for quadratic costs that are o-strongly convex a similar but even more conservative bound was established (Gaudio et al., 2021, Theorem 5). Moreu & Annaswamy (2022) used the same algorithm and analysis provide similarly conservative bounds for more general convex functions (Moreu & Annaswamy, 2022, Theorems 1.2). These overly conservative constraints do not allow % to exceed (or even approach 1) which is necessary to achieve performance improvement over vanilla. GD (Corollary and Figure 1).
10

---

Published in Transactions on Machine Learning Research (02/2025)
There are several differences provided in this work compared to the prior art (Gaudio et al., 2021; Moreu & Annaswamy, 2022). First we note that in our analysis, the free design parameters n and 3e (Equations (1) and (2)) are allowed to be time varying in comparison to Y, 3 in (33). We also added an extra degree of freedom (at: Hc) in the gradient step size for the update yt+1 (compare (33b) to (1b) and (2)). Our analysis (even for the simplified constraints in Proposition 1 and Corollary 1.1) allow more flexibility in the choice of " and 3e (compare Equations (3), (14), (21) to (34)). We also used a different Lyapunov candidate throughout, not scaling by "r and instead of using || - æel we used || y/ ll In their work both of these differences are moot because nt St are in fact treated as constants so can easily map between the Lypaunov functions. In our work they are not constants and these subtle changes to the Lyapunov candidate have non-trivial impacts on the analysis. We also simplified the discrete HT, not requiring one to pass the state 2t through gradients for f at two different time points (V/++1 (1x)) and V=((2)) in (33) as compared to just (a(e)))) in (1)). Finally, for the strongly convex setting we establish exponential convergence of the Lyapunov function to zero, where as prior art established exponential convergence to a compact set (compare Proposition 2 to (Gaudio et al., 2021, Theorem 5) and (Moreu & Annaswamy, 2022, Theorem 2)).
4.2 Accelerated methods (classical)
While the structure of our second order method is nearly identical to the setting one has when studying accelerated methods, there are some distinct differences. The first and foremost is that in our setting, we are assuming that the objective function is changing over time, our cost functions are subscripted with explicitly denoting their time varialion, Assumption 1. If we set St == f and set our hyper-parameetrs as
t 7 2
2
Me
Be 1+1
(35)
then we exactly recover Nesterov form 11 (Ahn & Sra, 2022; Nesterov, 2018). The biggest difference between these parameters and ours is that in order for us to establish stability the cyper-parameter Ye can not grow unbounded and in our case could reach a maximum of 2 (compare (21a) to (35)). For any stability based approach with time varying ft, it does not seem possible for a component of the algorithm to have a learning rate that scales beyond (1/NN) as in the case for Nesterov. One of the issues is that the state 2, does indeed grow unbounded in Nesterov. This however is not an issue when implementing Nesterov as the parameter one cares about is actually the component of z, that contributes to Tt, which from (1a) we see is Biz,. To that end we tried to analyze the equivalent dynamics with
e. = 2 + (1 - B,)
(36a)
Ut+1 = x. - a, V.((t)
(36b)
Bi+1 2, B1t1 ((.)
(36c)
Be
where :=:= Biz, and the other variables are unchanged but just redefined as Z, = Dz and ÿt = y:- So now f I. which is indeed proportional the effective learning rate associated with the state ā, would be Be41%/ = 122 N. to 1/N,, but we were unsuccessful with this approach.
Others have pointed out stability issues with Nesterov's method for smooth convex functions, namely Attia & Koren (2021). Much of the prior work has focused on different definitions of stability and constructing careful examples for single function f with desired properties. In our fully time varying setting however no such careful construction is necessary and the building blocks of the 'gadget" function in Attia & Koren (2021) can be used directly as a counter example against stability for our algorithm with they are defined in (36) when applied to time varying cost. functions. Furthermore, while Nesterov's method does indeed have some stability guarantees for fixed quadratic cost functions (Chen et al., 2018; Lessard et al., 2016), we conjecture that those guarantees vanish when the quadratic cost. functions vary over time.
as
4.3 Online learning and stochastic gradient descent
Our general setting of a cost function changing at each iteration also naturally arises in the setting of online learning and various flavors of stochastic (or sub-gradient) descent, where for fixed cost function the data
11

---

Published in Transactions on Machine Learning Research (02/2025)
arrives in a time varying fashion "Shalv-Shwarter 2012; Hardt et al., 2016). We can make this explicit by assuming we have a set of data DD and at time we use piece of that data D, E 'D to define our time varying from the fixed but data dependent cost f.
cost function ft(-)= ==
When addressing these problems in the online learning setting Regret Analysis (R.A) is used and this requires the learning rates to asymptotically decrease over time (Shalev-Shwartz, 2012). This accomplished either through explicitly reducing the learning rates over time or implicitly via scaling the learning by the accumulated iubggradients (e.g. Adagrad (Duchi et al., 2011) and Adam (Kingma & Ba, 2015)). Another major difference is in the initial problem setup and what assumptions are made. In the analysis of Adam for instance most signals and gradients in the algorithm are a priori assumed to be bounded with projection operators also extensively used in R.A
There are several recent attempts to address the stability of Stochastic Gradient Descent with Momentum (SGDM) for general smooth convex functions (Liu et al., 2020; Yan et al., 2018). That work is more line with the analysis presented here. One key difference, however, is in the choice of Lyapunov candidate. In SGDM (and in the analysis of Nesterov's accelerated method) quantity like (ve)) fa(x*)] is directly bounded included in the Lyapunov candidate, where in work, the function f does not appear in the Lyapunov candidate (compare (Liu et al., 2020, Equation (5)), (Ahn & Sra, 2022, Equation (4.10)), (Wilson et al., 2021, Equation ion (10)), or (Bansal & Gupta, 2019, Equation (5.5) to Equation (4) in this work) for the reasons we previously discussed in Remark 2. It instead falls out in the difference of the Lyapunov candidate, see Equation (11). This subtle difference likely has non-trivial implications. One exciting direction forward would be to possibly combine the Lyapunov candidate in this work with the stochastic analysis by Liu et al. (2020).
5 Simulation experiments
With these simulations we have two goals. The first is to demonstrate what can happen to traditional vanilla GD and NAGD when they are applied to time varying cost functions. The second is to demonstrate the long term behavior of HT in comparison to methods like Adam and Adagrad, which were designed via regret analysis. For all of our experiments, including the ones we alrcady discussod, the following function is being optimized
(x) = log exp(- - ct)) + a exp((x(r- -4))
(37)
Throughout the experiments we are comparing the HT with hyper-parameters " = 1.5, Mt = 1, and 3, = 1/1.5 (Corollary 1.1) to three different groups of methods, GD and NAGD, Time-varying Normalized (TN)-GD and TN-NAGD, and Adagrad and Adam. For completeness we list their details as well as hyper-parameter scttings below. For complete details on these experiments see Section B
GD and NAGD (Figures 1 and 2A)
GD: Ø4+1 zt 1/2 (xx)), (normalization parameter N is constant).
- -NAGD: Dynamics in (1) with parameters chosen as in (35) with be = 1, 70- = 1/2 3r = _2 (normalization parameter N₂ N constant).
i+1
TN-GD and TN-NAGD (Figure 2B)
-TN-GD 2++1 x, N. (xx)), (normalization parameter N₂ changes over time).
TN-NAGD: Dynamics in (1) with parameters chosen as in (35) with fr 1, 7 1/2 B, 8+1 (normalization parameter N, can now vary over time).
Adagrad and Adam (Figure 3)
Adagrad: I++1 Fz - a V (o, a is a constant
Vi(le)
"Adaptive regret analysis (Hazan & Seshadhri, 2009) looks overcome some of the drawbacks mentioned here but we are not aware of their use in the analysis of gradient methods with second order dynamies. Se Assume that the function ft has bounded gradients, [[ G. [[))l( I Go for all 0 C Rd and distance between any 0, generated by Adam is bounded, ||0.. 8m ll D, ||0m An S Dos for any m, E (l...., T})" Kingmaa & Ba (2015, page 4, Theorem 4.1)
12

---

Published in Transactions on Machine Learning Research (02/2025)
A
B
50
HT
50
HT
GD
TN GD
40
40
NAGD
TN IN-D
f(bo))
30
file)
30
20
20
10
10
0
0
40 60
80
100
20 40
60
80
100
t
Figure 2: An abrupt change in the smoothness of the objective function can cause instability. At t 50 the parameter b, in (37) is changed from 7 to 14. (A) The normalizer for the learning rate, N, is designed for 6, 7 and when b, 14 the normalizer is too small and GD and NAGD become unstabe. The HT is provably stable with time varying N₂ and this paramcter is adjusted to accommodate for the change in the smoothness of the objective function. (B) When the classic algorithms are given a time-varying normalizer they do not demonstrate the same poor performance. TN-GD is provably stable, but there not such theory for TN-NAGD. HT is the same in both (A) and (B).
Adam: I++1 = 0t
My Vocte"
a v2
In Figure 2A we are simply showing what happens with vanilla GD and NAGD when unanticipated change occurs in the smoothness of the function that is being optimized. If the smoothness of the function becomes large relative to the normalization constant in GD and NAGD then instability can occur. There is a trivial and obvious fix to this problem. One can simply replace the fixed value of N in the denominator of the learning rates of GD and NAGD with a time varying parameter N, resulting in TN-GD and TN-NAGD. see Figure 2B. This is an obvious thing one can do and for TN-GD can actually be shown that this is still stable algorithm. It is not at all obvious however that one can simply adjust papee-parrmesers on the fly for NAGD or any second order gradient descent algorithm for that matter. This was one of the main motivations for this work. With the HT we can adjust N, on the fly and we are provably stable
The HT is designed to run continuously. As previously discussed in the introduction, while the name 'online learning' might suggest lcarning continuously, it does not in fact mean this. We compared the HT to two prominent mothods Adam and Adagrad that were designed via regret analysis. In Figure 3 the HT, Adam, and Adagrad are compared where three different times throughout the experiment the optimal point in the objective function is changed (this is performed by changing c in (37)). In this experiment the learning rate for Adam and Adagrad was manually tuned for the best performance over the first 50 time steps of the experiment. One can see that indeed the yellow and green lines converge much faster to the minimum over the first 50 time steps. However, with each successive change in the optimal point of the objective function the performance of Adam and Adagrad degrades. This kind of behavior is expected from any algorithm designed via regret analysis as the learning rates have to asymptotically decay.
We have not yet explicitly defined regret, so lets do that here.
T Regret(T))= = Σ f((x)) - Σ f((er) where ST = arg min Σ f())).
T
T
(38)
With regret the accumulated cost up to time T is always compared to the accumulated cost with the best fixed cost in hindsight कy. In Figure 3(B) you can compare the pointwise in time optimal solution (æī grcy-dashed line) to the regret optimal solution (ør, pink). The regret optimal solution spend much of its time near 0 because it is trying to figure out the best. fixed optimal value up until that time. Inspecting Figure 3(C) we see that all the methods have average costs that lower than the average cost with the regret optimal solution. In Figure 3(D) we plotted the methods average regret over time (the values from panel (C) subtracted from the pink line) as well as the lower bound where regret is calculated for the pointwise in time optimal solution.
13

---

Published in Transactions on Machine Learning Research (02/2025)
A
B
60
6 (Adagrad)
6 [Adam)
4
X; (Adam)
(Adagrad)
(HT)
(HT)
6(4) (pointwise optimal)
XT (regret optimal)
(pointwise optimal)
40
0
-2
100
200
300
400
t
t, T
C
Adam Adagrad
HT
Adam
regret optimal
Adagrad
20
bound
Regret(()
10
-20
100 200
200
300
400
T
time. The paramcter that controls the optimal solution с₁ in (37) is initially at 0, is changed to 5 at t 50, is changed to -4 at = 150, and then is returned to ( at = 300. (A) The objective function fe over time. One can see that the performance of Adam and Adagrad degrades over time. (B) The estimates from the optimizers along with the regret optimal and pointwise optimal solutions. (C) Average cost over time. (D) Average regret over time.
Figure 3: Methods designed via regret analysis have degraded performance
6 What does acceleration look like with time varying cost functions?
We haven't discussed acceleration with any meaningful depth yet. We will cut to the chase barring extra assumptions there really is no such thing as acceleration when one allows for time vorying cost functions. You can have time-varying cost function with time-invariant optimal solution (Assumption 2) for which all gradient based optimization technique will have arbitrarily poor performance. By arbitrary performance here we mcan that the convergence time can be extended arbitrarily far into the future while still satisfying Assumption 2. We now discuss one such example.
Example 1. Consider the following 2-dimensional streaming regression problem
f((x,) = (1- D.
(39)
where D. E R is the time varying data vector that only takes values (depending the time t)
[1 OJT for <<T [0 IJT, otherwise.
D.
(40)
The only fixed value that is optimal for all time in Example 1 is x= = [1 1]T. Any algorithm (even an oracle with access to D,) that proposes updates at time t given information at - 1 will have instantaneously poor performance at time r. Even though a fixed optimal solution exists, no algorithm can see this change coming. We can make this little more tangible within the context of gradients by explicitly writing them down
14

---

Published in Transactions on Machine Learning Research (02/2025)
2(1 x1,1)
for t < T
0
(x+()))= =
(41)
otherwise
2(1 (2,1)
where we have used the following subscript notation
at [x1, x2,1
Using the gradients in Equation (41) to update æ, means that before only the first entry in æ, will be updated and the second entry in Dt will simply remain at its initial condition. Then at time = when we calculate the cost fi there will be an instantancous change that will no longer take into account all the learning that has occurred through the successive updates in F1, as the new cost. function from that point forward will only be function of z2,r- So if want to arbitrarily increase the time to convergence in this setting one simply nceds increase т. This example rather silly but demonstrates why convergence rates in the setting of time varying (convex) cost functions isn't really a thing that studied without extra constraints (beyond convexity) being imposed on fc-
7 Conclusions
The advantage of our approach is a natural setting for situations where learning is performed in real-time for arbitrary amounts of time. In our setting the learning rates do not need to asymptotically decrease over time. In fact for stability to hold the learning rates necessarily have to be bounded away from 0, see Equations (3b) and (3c). In addition, the structure of our Lyapunov candidates mirror those used in control, and could likely be exlended to settings where there is feedback with a dynamical system (Gaudio et al., 2019). We recognize that no method or technique a panacea. There are scenarios where the optimality conferred by Regret Analysis will be preferred, but we also think there are going to be growing applications in rcal-time scenarios where stability will be paramount. Ultimately, we simply hope that these methods might be useful in providing further insight into gradient descent with second order dynamics for time varying objective functions well as stochastic gradient descent with second order dynamics well. We are particularly interested in trying to extend these results to the stochastic setting and the accompanying relaxation of Assumption 2.
15

---

Published in Transactions on Machine Learning Research (02/2025)
Code Availability
Code to reproduce the figures is available at httpper//ggttib.cooo///ooob////s
Author Contributions
Following the CRediT taxonomy standard https://credit..iss org
TEG:
Conceptualization, Formal analysis, Funding acquisition, Investigation, Methodology, Project ad- ministration, Resources, Software, Supervision, Validation, Visualization, Writing original draft, Writing review & editing
SA:
Formal analysis, Investigation, Mothodology, Software, Validation, Visualization, Writing review & editing
AP: Validation, Writing review & editing
JEG: Concoptualization, Validation, Writing - review & editing
AMA:
Conceptualization, Funding acquisition, Supervision, Writing review & editing
Acknowledgments
This work was supported by the Boeing Strategic University Initiative (Annaswamy) and NIH R35GM143056 (Gibson)
16

---

Published in Transactions on Machine Learning Research (02/2025)
References
Kwangjun Ahn and Suvrit Sra. Understanding Nesterov's Acceleration via Prosimal Point Method, pp. 117 130. 2022. doi: 10.133/1.979161197766.61 URL https://epubs.siie siam org/doi//at abto///b///// abt/aa..a/////a 1137/1. 9781611977066.
Amit Attia and Tomer Koren. Algorithmic instabilities of accelcrated gradient descent. In M. Ranzato, A. Beygelzimer Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1204-120 1214. Curran Associates, Inc., 2021. URL https: http:://proceeding.. .df..
Nikhil Bansal and Anupam Gupta. Potential-function proofs for gradient methods. Theory of Computing, 15(4):1 32, 2019. doi: v015a004.
URL http:://ttherryofcopppiiii org/ aatgcesttcees////
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for largo-scale machine learning. SIAM review, 60(2):223-35) 11111,1 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Mochine Learning Research, 2:499-520 2002.
Stephen Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2004. doi: 10.1017/CB09780051 1804441..
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-355 357, 2015. ISSN 1935-8237. doi: 1561/2200000050.
URL http://xxxddo..org////
Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
doi: 10.10T/CC0095505154400
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms, 2018. URL https://arxiv. org/abs/ http//b///88...1..1111 01619.
Zhiyuan Chen and Bing Liu. Lifelong machine learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 12(3):1 207, 2018.
DARPA. Real time machine learning (rtml). Technical Report HR00011990003, Defense Advanced Research
http://awaggppgppppp//////p/pppa wearrtttiiiiieeeseeeteeee ties/resources/ Projects Agency, March 2019. URL attpss//sani /ttp////ttt/////aa//////////////
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):2111-2155) 2011.
Bálint Farkas and Sven-Ake Wegner. Variations on Barbälat's lemma. The American Mathematical Monthly, 123(8):825 830, 2016.
Joseph E Gaudio, Travis E Gibson, Anuradha M Annaswamy, Michael Bolender, and Eugene Lavretsky. Connections between adaptive control and optimization in machine learning. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 3563-4568. IEEE, 2019.
Joseph F. Gaudio, Anuradha M. Annaswamy, José M. Moreu, Michael A. Bolender, and Travis F. Gibson. Accelerated learning with robustness to adversarial regressors. In Proceedings of the 3rd Conference on Learning for Dynamics and Control, volume 144 of Proceedings of Machine Learning Research, pp. 636-650. PMLR, 07 08 June 2021. URL httpps:/prooceedngss mlr paress/v144/gat gaadioaaa html.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234 PMLR, 2016.
17

---

Published in Transactions on Machine Learning Research (02/2025)
Elad Hazan. Introduction to online conver optimization. 2022.
Elad Hazan and Comandur Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th anaual international conference on machine learning, pp- 393-40444 400, 2009.
Flad Hazan and Karan Singh. Introduction to online nonstochastic control, 2022. URL https://arxiv..rrr abs/2211.0900 09619.
Petros A Ioannou and Jing Sun. Robust adaptive control. Courier Corporation, 2012.
Rudolf E Kalman and John E Bertram. Control system analysis and design via the "sccond method" of 1yapunov: I continuous-time systems. 1960.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR), 2015. URL attps://openreviev.. net// forum?id-8gm//:jJyyL
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. STAM Journal on Oplämization, 26(1):57 95, 2016.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Newral Information Processing Systems, 33:18261 182711 2020.
José L Masscra. Contributions stability thcory. Annals of Mathematics, 64(1):182-200 1956.
Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and molivation, volume 24, pp. 109 165. Elsevier, 1989.
José M. Moreu and Amuradha M. Annaswamy. A stable high-order tuner for general convex functions. IEEE URL https://arxiv..rr
Control Systems Letters, 6:566-571 2022. doi: N0.1000/LCSSSS22221.33883 abs/2011. 09996.
AS Morse. High-order parameter tuners for the adaptive control of linear and nonlinear systems. In Systems, Models and Feedback: Theory and Applications:, 1992.
Kumpati S Narendra and Anuradha M Annaswamy. Stable adaplive systems. Courier Corporation, 2012.
Yurii Nesterov. A method for solving a convex programming problem with convergence rate o(1/k²). Dokl. Akad. Nauk SSSR, 23):333 547, 1983.
Yurii Nesterov. Lectures on conver optimization. Springer, 2018.
NSF. Real-time machine learning (rtml). Technical Report NSF 19-566, National Science Foundation. URL https:// hstf:://wwww/.../////./mmm http:/pps///11/sff1111eammmm 19566 htm#toc..
German I. Parisi, Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: review. Neural Networks, 113:54-71, 2019. ISSN 0893-6080. URL
doi: ar:icleepp//0088680119903.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
W. Rudin. Principles of Mathematical Analysis. International series in pure and applied mathematies. McGraw-Hill, 1976. ISBN 9780070856134. URL https://books. http://oooo..ooggleeoe/oooooooee
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends0 in Machine Learning, 4(2):107-194, 2012. ISSN 1935-8237. doi: 10.1561 /220000018. URL http://dx..oi.orrg/ 1561/2200000088.
18

---

Published in Transactions on Machine Learning Research (02/2025)
Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. In 7. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, vol- ume 27. Curran Associates, Inc., 2014. URL https: https://proceeddngs www..ns........... 00G66000000//////0/4466666662222 Pap.eoe................. pdf.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5 rissprop, coursera: Neural networks for machine learning. University of Toronto Technical Report, 2012.
Kostas Tsakalis and Petros Toannou. Adaptive control of linear time-varying plants. Aulomalica, 23(4): 459-468, 1987.
Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J. Pappas. Statistical learning theory for control: A finite sample perspective, 2022. URL http:://aaxxi..og/abbbeeeeee htggg//bb/220 05423.
Andre Wibisono, Ashia C. Wilson, and Michael I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113(47):E7351 E7358, 2016. ISSN 0027-8424. doi: 10.1073/ 21/8//mas.1000 1614734113. URL https://ww, pnas. wwt.paaa..oooteeeeeeeeeepppeeeee /rt//////oottt//133//////555555
Ashia C. Wilson, Ben Recht, and Michael I. Jordan. A Yyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-34 34, 2021. URL http://jmlr org/ org/papers/
v22/20-195. htm.
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic momentum methods for deep learning, Xiviv preprint Xrxiv: 10396, 2018.
19

---

Published in Transactions on Machine Learning Research (02/2025)
A Technical Lemmas and Corollaries
These technical lemmas can be found in most standard texts convex optimization (Boyd & Vandenberghe, 2004; Bubeck, 2015; Hazan, 2022)
Lemma A.1 (First order condition of convexity (Boyd & Vandenberghe, 2004, $3.1.3)). Let f:R R + R be a differentiable convez function. Then Va, y E R
f(y) 2 f(z) (y
Lemma A.2 (Basic property of smooth convex functions). A continuously differentiable conver function f f: +R R is L-smooth if and only if Vx, y E IRN,
L, f(y) S f()) Vf(x) x)) + 2 x=12
Lemma A.3 (Basic property of strongly convex functions). If continuously differentiable conver function f R: + R is a-strongly conver, then Va, E EN
(Vf(z) vf(y)) - y) 2 ol|= yyl?
Lemma A.4 (co-coercivity of smooth convex functions). f f:RN + R is L-smooth, then Vx, y
continuously differentiable conver function
R
(Vf(x) V/(y)) - [ -v(())
Lemma A.5 (co-coercivity of smooth and strongly convex functions). If continuously differentiable conver. function f: RRN + R is L-smooth and osstrongly conver, then Vz, IRN
(v(()) vf(w)) -) aT.
y1l [f(x) ff())
Lemma A.6 (distance to minimizer for smooth convex functions). If continuously differentiable conver function f :RN R is L-smooth. then Vx,
N
[f(=))| < f(x) f(x')= S x= 2L
Lemma A.7 (distance to minimizer for strongly convex functions). If continuously differentiable function f f: R: + R is a-strongly conver, then Va, y E V
[[]f(()]| 2 f(x) - f(xx))x) > x-=x"11 x²12
20
Lemma A.8 ((Bubeck, 2015, Lemma 3.5)). Let Js be L-smooth conver function. Then Va, y R...
1
((x) f(y) < (((()) y)
V V
2T.
Corollary A.8.1. Under the setting in Lemmna A.8 with wt, y x", and V(((x)) 0 the bound becomes
fi(()) xx) [f((x") fi (ax)] 2L. [f
Lemma A.9. Under the setting in Lemma A.8 with xz, y xx, and fi(x)) and for any X [0.1] the bound becomes
((( xi) 5 (1 x) [f((a*) - f((x))] 1 vf((=)))1
2L
Proof. Add and subtract X [[((x*) Se(are)] and apply Lemma A.6.
20

---

Published in Transactions on Machine Learning Research (02/2025)
B
Experimental Details
For the optimization function fe in (37) it is useful to note that the second derivative of
0² dr f((z) by sech (be( sech?(b: + x)) b
and thus Jt. an L--smooth function where L, bj. all simulations the HT parameters are chosen as T 1.5, He 1, 1/1.5 coinciding with Corollary 1.1.
B.1 Details for Figure
The algorithms are optimizing Equation (37) with
d;
b; = 7
Gr 0 for 50 and then C2 5 for 2 50
For GD, NAGD, and HT the learning rate normalizer is N₂ = N = =49. All methods are initialized with
V0 50 5
B.2 Details for Figure! 2
The algorithms optimizing Equation (37) with
5
7 for < 50 and then b, 21 for 50
= 0
For GD, NAGD, the learning rate normalizer is N = 49 throughout. For TN-GD, TN-SAGD and HT N₂ = 49 for < 50 and then N₂ = 441 for 2 50. All methods are initialized with xp = Vo 2g
B.3 Details for Figure 3
The algorithms are optimizing Equation (37) with
b; =7 a:
G: 0 for < 50, a 5 for < / 150, a -4 for 150 S < 300, and then & for 2 300 For HT the learning rate normalizer is N, 49. For Adam and Adagrad the learning rate manually tuned to have the best possible performance and was set to = 1.
21


Reviews:
[{"review_id": "6RNbnHPNho", "reviewer": "Reviewer_Wios", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- (Strength) The paper is written clearly, the analysis is more general than prior work (at least when confined to the setting of time-varying objectives).\n- (Strength) The paper provides interesting connections between optimization and control theory proofs.\n- (Weakness) Several technical issues in the proofs need to be addressed:\n1. The paper states that \"for ∆Vt+1 ≤ 0 we need c1, c4 and $c_2^2 - 4c_1c_3$ to be less than or equal to zero\", but this is incorrect - the condition should be $4c_1c_3 - c_2^2 \\leq 0$. While this doesn't seem to affect the final result since the proof sets this quantity to exactly 0, the statement should be fixed.\n2. The claim that \"the optimal point can actually change over time and stability is maintained\" appears too strong. The paper assumes $x^*$ is fixed for proving asymptotic convergence but claims stability holds even with time-varying $x_t^*$. I don't see how the proof can be modified to handle this, it relies crucially on $f_t (x_t) - f(x^*) \\leq 0$ for all $t$.\n3. The claim that \"In the stochastic setting Assumption 2 is equivalent to the unbiased sub-gradient assumption\"-- I honestly can't see why this is the case. Could you clarify?\n- (Weakness) The paper essentially assumes overparameterization ($x^*$ minimizes all the $f_t$) but doesn't exploit this to potentially get better rates. Specifically, the paper claims it's impossible to have learning rates scaling beyond $\\mathcal{O}(1/N_t)$ for time-varying objectives, but under overparameterization this limitation may not hold. At least the authors should provide a lower bound showing this. Limiting learning rates to be this small is why the analysis here can't recover Nesterov's method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes gradient descent methods with second-order dynamics for time-varying objective functions through the lens of stability analysis. The paper considers a Lyapunov/potential function framework that shows stability (in the sense of a bounded trajectory) with time-varying objectives for an algorithm that resembles Nesterov acceleration (though the analysis technically does not recover Nesterov's accelerated gradient method). The authors provide analysis in both the smooth and strongly convex settings with relaxed hyperparameter constraints compared to prior work. Finally, the paper provides some experimental verification for the stability of the iterates under time-varying objectives.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please address my points in the strengths and weaknesses sections.\n- Generally: what is particularly difficult about the time-varying objective when you assume overparameterization? The analysis looks somewhat standard and similar to existing Lyapunov analysis (or \"potential function\" in general) of optimizationa algorithms (e.g. [1, 2]). Can you elaborate on this here?\n\n[1] Bansal, Nikhil, and Anupam Gupta. \"Potential-function proofs for gradient methods.\" Theory of Computing 15.1 (2019): 1-32.\n[2] Wilson, Ashia C., Ben Recht, and Michael I. Jordan. \"A Lyapunov analysis of accelerated methods in optimization.\" Journal of Machine Learning Research 22.113 (2021): 1-34.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8YvSOJiT7V", "reviewer": "Reviewer_1pi2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Compared with existing works, this paper allows a more flexible choice of hyperparameters in the gradient descent step, especially the learning rate. And they also use a different Lyapunov candidate.\n2. For the strongly convex setting, they build the convergence of the Lyapunov function to zero instead of a compact set in other works.\n3. Corollary 1.1 provides a practical choice of those hyper-parameters, which is useful in real applications.\n\nWeaknesses:\n1. After reading the paper, it is still a little unclear to me about the advantages of using $\\\\|\\mathbf{z}_t-\\mathbf{y}_t\\\\|$ instead of $\\\\|\\mathbf{z}_t-\\mathbf{x}_t\\\\|$, could the authors explain more about the benefits of using this different Lyapunov candidate?\n2. As the authors stated, the HT methods cannot perform as well as the Regret Analysis in some scenarios. Considering the conditions under which the HT methods can perform better would be interesting.\n3. Assumption 2 may not always hold for real applications. In other words, it would be more appropriate to consider time-varying optimal $x$ in the setting of time-varying cost functions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops a more general stability guarantee for gradient descent with second order dynamics when applied to time-varying cost functions. Specifically, they use better-designed hyper-parameters and a different Lyapunov candidate to build a less conservative bound on the hyperparameters, which do not require asymptotically decreasing learning rates over time.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As mentioned above, the authors can add more explanations about the advantages of using $\\\\|\\mathbf{z}_t-\\mathbf{y}_t\\\\|$ instead of $\\\\|\\mathbf{z}_t-\\mathbf{x}_t\\\\|$.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vrVSfV6pLa", "reviewer": "Reviewer_ezmR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This submission is organized with clear structure. The authors provided the detailed mathematical proof for all the theoretical analysis of the convergence results of the high-order tuner algorithms applied to the explicitly time varying cost functions. They also conduct numerical experiments and these empirical results validate the theoretical results. However, this submission has the following weaknesses:\n\n1. The authors should present more background introduction for the high-order tuner methods that are the gradient descent methods with second order dynamics in section 2. This high-order tuner method is totally different from the standard gradient descent. Hence, it is reasonable for the authors to better introduce the previous related works and the illustrate more ideas behind this high-order tuner method. \n\n2. This high-order tuner method has one issue that the parameter $\\alpha_t$ depends on the parameter $N_t$, while $N_t$ must satisfies the condition that $N_t \\geq L_t$ as specified in different theorems. However, $L_t$ is the smoothness parameter of the objective function. Hence, to achieve the different convergence results, we need to know these smoothness parameter $L_t$ of the objective function when we implement the high-order tuner method. This may cause some issues because in practice, we may not know or it is difficult to estimate the values of these $L_t$.\n\n3. Proposition 1 and the warm up of Theorem 1. Hence, proposition 1 is a bit redundant in this submission. Maybe it can be moved to appendix. Also proposition 2 should be Theorem 2.\n\n4. The most significant weakness of this submission is that the authors only prove asymptotic convergence results in Proposition 1 and Theorem 1 for the general convex case. While for the strongly convex case, the authors proved a non-asymptotic linear convergence rate as specified in proposition 2. For the vanilla GD, it can reach a linear convergence rate for strongly convex case while it can also reach a sub-linear convergence rate for the general convex case. Therefore, the authors need to investigate and prove a non-asymptotic explicit sub-linear convergence rate for the general convex condition. The current result of $\\lim_{t \\to \\infty}f(x_t) = f(x_*)$ is not impressive enough.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work the authors analyzed gradient descent with second order dynamics when applied to explicitly time varying cost functions and provide more general stability guarantees. These results aid in the design and certification of optimization schemes to ensure safe and reliable deployment for real-time learning applications. The authors consider the general convex setting and strongly convex setting and proved the convergence results in these two different conditions. They also provide the empirical results from numerical experiments that are consistent with the theoretical analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors must made changes or justify their work for all the four weaknesses mentioned in the Strengths And Weaknesses section.\n\nThe most important requested change is the weakness 4 about the proof of the non-asymptotic sublinear convergence rate of the high-order tuner methods for the general convex case. If the authors could prove the explicit convergence rate under the general convex case, I suggest that this submission should be accepted by TMLR. Otherwise, this submission does not deserve a publishment.", "broader_impact_concerns": "There are no concerns on the ethical implications of the work that would require adding a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper substantially generalizes the existing stability analysis of gradient methods by allowing a more flexible choice of hyperparameters in the gradient descent step and time-varying functions. The analysis shows an interesting connection between optimization and control theory proofs. All the reviewers acknowledge the interests of the results and the strength of the theoretical analysis. The discussions and revision address the issues well.
Decision: Accept (poster)