# On the stability of second order gradient descent for time varying convex
functions

Travis E. Gibson Massachusetts Institute of Technology  Brigham and Women’s
Hospital  Harvard Medical School  Broad Institute of MIT and Harvard  Sawal
Acharya Brigham and Women’s Hospital  Anjali Parashar Massachusetts Institute
of Technology  Joseph E. Gaudio Massachusetts Institute of Technology  Anurdha
M. Annaswamy Massachusetts Institute of Technology

###### 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 and Annaswamy 2022 for
second order gradient descent 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.

##  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 guarantees will assuredly be
related to cross-validation. There are also many scenarios where we envision
the optimization scheme itself would also need to have robustness guarantees.
Here, specifically, we are 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 a self-driving car that
catalogues new events and simultaneously labels and retrains the model (semi-
supervised) on the fly, or 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 needs to be assured that the model training process itself is
stable in real-time.111By stability here we are referring to the definitions
from dynamical systems and control theory [3], not the algorithmic stability
definition from Bousquet and Elisseeff [4]. Within control this field of study
falls under the moniker of Adaptive Control (AC).222Here we are referring to
AC that is simultaneously updating parameters while controlling, like Model
Reference Adaptive Control (MRAC) [5, 6], not the area of AC that has the
learning phase and the deployment phase separate, i.e. episodic learning [7,
8]. The closest area within ML where models are trained in real-time is fairly
nascent but aptly named Real-Time Machine Learning (RTML) [9,
10].333Continuous Learning (CL) and Lifelong Learning (LL) [11, 12] are
similar in name to RTML, but CL and LL are primarily concerned with concepts
like catastrophic forgetting [13] with an eye toward learning new things
without forgetting what you learned in the past. With these applications in
mind we are interested in analysing the stability of second order gradient
descent algorithms when applied to time varying cost functions.

GD and its variants have rightfully attracted significant attention given
their success as the workhorses for training deep neural networks [14]. The
accelerated gradient methods first introduced by Polyak [15] and Nesterov [16]
have had renewed interest [17, 18], as well as the expanded adoption and
innovation within stochastic gradient descent methods and online learning [19,
20, 21, 22]. The most popular optimization schemes for deep models combine
ideas from stochastic gradient descent, the classic accelerated methods with
momentum [23], and adaptive gradient methods [24], e.g. Adam [25]. Methods
like Adam are analyzed with Regret Analysis (RA) which frames the analysis in
terms of minimizing some accumulated cost over time as 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 [26], 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 a High-order Tuner (HT) going as far back as 1992 [27]. In the
original work by Morse [27] the HT was analyzed within the specific context of
model reference adaptive control. Gaudio et al. [1] and Moreu and Annaswamy
[2] recently showed that a HT could be parameterized to look like the popular
accelerated methods first introduced by Nesterov [16] and that in turn, one
could study their stability when applied to explicitly 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 [1] or for more
general functions but with hyper-parameters that were fixed in time and with
exceedingly strict constraints [2]. Specifically, our analysis demonstrates
that a simpler discrete time parameterization of the HT is possible
(coinciding with Nesterov form II as it is sometimes referred to [28]), a
different Lyapunov candidate can be used, and that together these allow for a
less conservative bound on the (now time-varying) hyper-parameters.

##  2 Problem Statement and Update Rule

We consider the following optimization problem,
$\min_{\bm{x}\in\mathbb{R}}f_{t}(\bm{x})$ where for every time $t$,
$f_{t}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$. The subscript $t$ denotes the
time variation in $f_{t}(\cdot)$ which could occur for a fixed cost function
but with streaming 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 a High-order Tuner (HT) which are second order
gradient algorithms similar in structure to the popular momentum methods, but
with explicitly time varying cost functions.

The HT studied here is parameterized as follows

$\displaystyle\bm{x}_{t}$
$\displaystyle=\beta_{t}{\bm{z}}_{t}+(1-\beta_{t}){\bm{y}}_{t}$ (1a)
$\displaystyle{\bm{y}}_{t+1}$ $\displaystyle=\bm{x}_{t}-\alpha_{t}\nabla
f_{t}(\bm{x}_{t})$ (1b) $\displaystyle{\bm{z}}_{t+1}$
$\displaystyle={\bm{z}}_{t}-\eta_{t}\nabla f_{t}(\bm{x}_{t})$ (1c)

where $\alpha_{t}$, $\beta_{t}$, and $\eta_{t}$ are all (potentially) time
varying hyper-parameters. This is almost identical to Nesterov [29] with the
significant difference being that the functions $f_{t}$ are explicitly time
varying.

For ease of discussion we will use the following definitions

$\displaystyle\alpha_{t}\mathrel{\mathop{\mathchar
58\relax}}=\frac{\mu_{t}}{N_{t}}\quad\quad\eta_{t}\mathrel{\mathop{\mathchar
58\relax}}=\frac{\gamma_{t}}{N_{t}}\quad\quad\bar{\beta}_{t}\mathrel{\mathop{\mathchar
58\relax}}=1-\beta_{t}\quad\quad\bar{\mu}_{t}\mathrel{\mathop{\mathchar
58\relax}}=1-\mu_{t}$ (2)

where $\gamma_{t}$, $\mu_{t}$, $\beta_{t}$, and $N_{t}$ are the free design
parameters. All norms, $\mathinner{\\!\left\lVert\cdot\right\rVert}$, are 2
norms. We will use the following definitions and assumptions throughout the
paper.

######  Definition 1 (convex).

A function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is convex if
$\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$ and $\lambda\in[0,1]$,

$f(\lambda\bm{x}+(1-\lambda){\bm{y}})\leq\lambda
f(\bm{x})+(1-\lambda)f({\bm{y}}).$

######  Definition 2 (smooth).

A continuously differentiable function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is L-smooth if there exists an
$L<\infty$ such that $\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$, then following
holds $\mathinner{\\!\left\lVert\nabla f(\bm{x})-\nabla
f({\bm{y}})\right\rVert}\leq
L\mathinner{\\!\left\lVert\bm{x}-{\bm{y}}\right\rVert}.$

######  Definition 3 (strong convexity).

A differentiable function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is $\sigma$-strongly convex if
$\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}\text{ and }\sigma\geq 0$, then
following holds $f({\bm{y}})\geq f(\bm{x})+\nabla
f(\bm{x})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{y}}-\bm{x})+\frac{\sigma}{2}\mathinner{\\!\left\lVert{\bm{y}}-\bm{x}\right\rVert}^{2}.$

######  Assumption 1.

For each $t$ the function $f_{t}$ is an $L_{t}$-smooth convex function and
furthermore the sequence $L_{t}$ is bounded, i.e. $L_{t}\in\ell_{\infty}$ (see
Definitions 1 and 2).

######  Assumption 2.

There exists an $\bm{x}_{*}$ such that $f_{t}(\bm{x}_{*})=\min f_{t}(\bm{x})$
for all $t$.

######  Assumption 3.

For each $t$ an upper bound on the smoothness of the function is obtained,
$N_{t}\geq L_{t}$, for explicit use in the HT, see Equation (2). If $L_{t}$ is
bounded then $N_{t}$ is bounded as well.

Assumptions 1 and 3 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 still be able to prove stability of our
algorithm but not its asymptotic convergence. For Assumption 2 note that
$\bm{x}_{*}$ need not be unique.

##  3 Stability for time varying functions

Our objective is to provide streamlined, 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 to follow,
and then proceeding onto the general result. In section §3.1 we present our
first result for smooth convex functions (Proposition 1), with the more
general results coming with Theorem 1 in §3.2 . We close with our analysis of
strongly convex functions in §3.3 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 1 in our presentation of Proposition 2. A completely general bound
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.

###  3.1 Warm-up direct proof for smooth convex

######  Proposition 1.

Let $f_{t}$ satisfy Assumptions 1-3. For the HT defined in Equation (1) with
arbitrary initial conditions $\\{\bm{x}_{0},{\bm{y}}_{0},{\bm{z}}_{0}\\}$,
$N_{t}\geq L_{t}$ ($f_{t}$ is $L_{t}$ smooth by assumption), and the following
three conditions satisfied

$\displaystyle\beta_{t}$ $\displaystyle\in[0,1]$ (3a) $\displaystyle\mu_{t}$
$\displaystyle\in[\epsilon,1],\quad\epsilon>0$ (3b) $\displaystyle\gamma_{t}$
$\displaystyle=\tfrac{1}{2}\mu_{t}.$ (3c)

then

$V_{t}=\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\mathinner{\\!\left\lVert{\bm{y}}_{t}-{\bm{z}}_{t}\right\rVert}^{2}$
(4)

is a Lyapunov candidate and it follows that $V_{t}\in\ell_{\infty}$.
Furthermore,
$\lim_{t\rightarrow\infty}\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}_{*})\right]=0$.

###### Proof.

To demonstrate that $V_{t}$ is bounded we will first show that $\Delta
V_{t+1}=V_{t+1}-V_{t}\leq 0$. The basic strategy is to obtain a bound for
$\Delta V_{t+1}$ in a quadratic form of the vectors $\nabla f_{t}(\bm{x}_{t})$
and $(\bm{x}_{t}-{\bm{z}}_{t})$, making as few intermediate bounds as possible
until the quadratic form is obtained, for which we then complete the square so
as to obtain constraints on the free design parameters. The final ingredient
is a simple argument regarding bounded monotonic sequences.

We begin by expanding the time step ahead Lyapunov candidate
$V_{t+1}=\mathinner{\\!\left\lVert{\bm{z}}_{t+1}-\bm{x}_{*}\right\rVert}^{2}+\mathinner{\\!\left\lVert{\bm{y}}_{t+1}-{\bm{z}}_{t+1}\right\rVert}$
from (4) by substituting the update for ${\bm{y}}_{t+1}$ from (1b) and
${\bm{z}}_{t+1}$ from (1c) and noting that
$\bm{x}_{t}-{\bm{z}}_{t}=\bar{\beta}_{t}({\bm{y}}_{t}-{\bm{z}}_{t})$ from (1a)
where $\bar{\beta}_{t}=1-\beta_{t}$, as defined in (2), we obtain

$V_{t+1}=\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+(\eta_{t}^{2}+(\eta_{t}-\alpha_{t})^{2})\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}-\bm{x}_{*})\\\
+\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+2(\eta_{t}-\alpha_{t})\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t}).$
(5)

Expanding $-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}-\bm{x}_{*})$
as $-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}+\bm{x}_{t}-\bm{x}_{t}-\bm{x}_{*})$
and noting that

$-\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-\bm{x}_{*})\leq
f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t})-\frac{1}{2L}\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2},$

from Corollary 9.1, it follows that

$-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}-\bm{x}_{*})\leq
2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t})+2\eta_{t}(f(\bm{x}_{*})-f(\bm{x}_{t}))-\frac{\eta_{t}}{L_{t}}\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}.$ (6)

Applying the bound in Equation (6) to Equation (5) we have

$\begin{split}V_{t+1}\leq&\
\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\left(\eta_{t}^{2}+(\eta_{t}-\alpha_{t})^{2}-\frac{\eta_{t}}{L_{t}}\right)\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}+2\eta_{t}(f(\bm{x}_{*})-f(\bm{x}_{t}))\\\
&+\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+2(2\eta_{t}-\alpha_{t})\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t}).\end{split}$
(7)

Now turning our attention to $V_{t}$ and rewriting the second component to be
in terms of $\bm{x}_{t}-{\bm{z}}_{t}$ we have

$V_{t}=\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\bar{\beta}_{t}^{-2}\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}$
(8)

where we have used the fact that
$\bm{x}_{t}-{\bm{z}}_{t}=(1-\beta_{t})({\bm{y}}_{t}-{\bm{z}}_{t})$ from
Equation (1a). Subtracting (8) from (7) it follows that

$\begin{split}\Delta
V_{t+1}\leq&\left(\eta_{t}^{2}+(\eta_{t}-\alpha_{t})^{2}-\frac{\eta_{t}}{L_{t}}\right)\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}+2\eta_{t}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))\\\
&+\left(1-\bar{\beta}_{t}^{-2}\right)\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+2(2\eta_{t}-\alpha_{t})\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t}).\end{split}$
(9)

We pause to define some variables

$\displaystyle{\bm{a}}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{N_{t}}\nabla f_{t}(\bm{x}_{t})$ $\displaystyle c_{1}$
$\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\gamma_{t}^{2}+(\gamma_{t}-\mu_{t})^{2}-\gamma_{t}$ $\displaystyle
c_{3}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=1-\bar{\beta}_{t}^{-2}$ $\displaystyle{\bm{b}}$
$\displaystyle\mathrel{\mathop{\mathchar 58\relax}}={\bm{x}_{t}-{\bm{z}}_{t}}$
$\displaystyle c_{2}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=2(2\gamma_{t}-\mu_{t})$ $\displaystyle c_{4}$
$\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=2\frac{\gamma_{t}}{N_{t}}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))$

Using the above definitions and the fact that $N_{t}\geq L_{t}$ (Assumption 3)
it follows that

$\Delta V_{t+1}\leq
c_{1}\mathinner{\\!\left\lVert{\bm{a}}\right\rVert}^{2}+c_{2}{\bm{a}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}{\bm{b}}+c_{3}\mathinner{\\!\left\lVert{\bm{b}}\right\rVert}^{2}+c_{4}.$

Completing the square we have

$\Delta V_{t+1}\leq
c_{1}\mathinner{\\!\left\lVert{\bm{a}}+\frac{c_{2}}{2c_{1}}{\bm{b}}\right\rVert}^{2}+\left(c_{3}-\frac{c_{2}^{2}}{4c_{1}}\right)\mathinner{\\!\left\lVert{\bm{b}}\right\rVert}^{2}+c_{4}.$
(10)

In order for $\Delta V_{t+1}\leq 0$ we need $c_{1},c_{4}$ and
$c_{2}^{2}-4c_{1}c_{3}$ to be less than or equal to zero (which in turn
implies that $c_{3}$ is less than zero as well). The coefficient $c_{4}$ is
always less than zero because of the optimally of $\bm{x}_{*}$. The
coefficients $c_{1},c_{3}$ as well as the expression $c_{2}^{2}-4c_{1}c_{3}$
are all less than zero given the conditions outlined in (3). It thus follows
that

$\Delta V_{t+1}\leq
2\frac{\gamma_{t}}{N_{t}}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))<0\
\forall\bm{x}_{t}\neq\bm{x}_{*}.$ (11)

It then follows that $({\bm{z}}_{t}-\bm{x}_{*})$ and
$({\bm{y}}_{t}-{\bm{z}}_{t})$ are bounded by the definition of $V_{t}$ in (4).
With $\bm{x}_{*}$ fixed and clearly bounded it then immediately follows that
${\bm{y}}_{t},{\bm{z}}_{t}\in\ell_{\infty}$. From (1a) and the boundedness of
$\beta_{t}$ (by construction) it then follows that
${\bm{y}}_{t}\in\ell_{\infty}$. From Definition 2 (smooth) and from
Assumptions 1-3 it then follows that the sequence
$\mathinner{\\!\left\lVert\nabla f_{t}(\bm{x}_{t})\right\rVert}$ is bounded as
well. Finally, given that smooth functions on compact sets are bounded we have
that $f_{t}(\bm{x}_{t})$ is bounded and therefore
$[f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t})]\in\ell_{\infty}$ as well. With that all
signals in the model are bounded
$\bm{x}_{t},{\bm{y}}_{t},{\bm{z}}_{t},f_{t}(\bm{x}_{t}),\nabla
f_{t}(\bm{x}_{t})\in\ell_{\infty}$.

Finally to prove convergence of the cost function to its minimum we will use
properties of monotonic sequences (i.e. partial sums of positive values). By
Assumption 1 $L_{t}$ is bounded and then by Assumption 3 we choose an $N_{t}$
that is bounded as well. Therefore, there exists a positive $\bar{N}$ such
that $\bar{N}\geq N_{t}$ for all $t$. Finally, recall from (3c) that
$\gamma_{t}\in[\epsilon/2,1/2]$. Using these bounds for $N_{t}$ and
$\gamma_{t}$, and Equation (11) it follows that

$\frac{\bar{N}}{\epsilon}\Delta V_{t+1}\leq
f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}).$ (12)

Summing both sides, multiplying by $-1$ and recalling that $V_{t}$ is a non-
increasing positive sequence, it follows that

$a_{\tau}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{t=0}^{\tau}[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}_{*})]\leq-\frac{\bar{N}}{\epsilon}\sum_{t=0}^{\tau}\Delta
V_{t+1}=\frac{\bar{N}}{\epsilon}[V_{0}-V_{\tau+1}]\leq\frac{\bar{N}}{\epsilon}V_{0}<\infty$
(13)

With $a_{\tau}$ a bounded monotonic sequence it follows that
$\lim_{\tau\to\infty}a_{\tau}$ exists [30, Theorem 3.14] and therefore
$\lim_{t\rightarrow\infty}\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}_{*})\right]=0$.
∎

######  Remark 1.

Note that we did not begin by providing successfully more refined bounds for
$f_{t}(\bm{x}_{t})-f_{t}(\bm{x}_{*})$. 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 the Lyapunov candidate we
achieve the desired result in (13). For the interested reader this approach
also extends to continuous time settings where the last step (under
appropriate conditions) invokes Barbălat’s Lemma [31].

###  3.2 A more general proof for smooth convex

######  Theorem 1.

Let $f_{t}$ satisfy Assumptions 1-3. For the HT defined in Equation (1) with
arbitrary initial conditions $\\{\bm{x}_{0},{\bm{y}}_{0},{\bm{z}}_{0}\\}$,
$N_{t}\geq L_{t}$ ($f_{t}$ is $L_{t}$ smooth by assumption) and with the
algorithm hyper-parameters $\\{\gamma_{t},\mu_{t},\beta_{t}\\}$ along with the
analysis parameters
$\lambda_{t}\in[0,1-\epsilon],\xi_{t}\in[\epsilon,\infty),\epsilon>0$ chosen
such that

$\displaystyle c_{5}<0,\quad\text{and}\quad c_{7}-\frac{c_{6}^{2}}{4c_{5}}<0$
(14)

where

$\displaystyle c_{5}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\gamma_{t}^{2}+\xi_{t+1}(\gamma_{t}-\mu_{t})^{2}-(1+\lambda_{t})\gamma_{t}$
$\displaystyle c_{6}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=2[\xi_{t+1}(\gamma_{t}-\mu_{t})+\gamma_{t}]$ (15a) $\displaystyle
c_{7}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\xi_{t+1}-\xi_{t}\bar{\beta}_{t}^{-2}$ (15b)

then

$W_{t}=\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\xi_{t}\mathinner{\\!\left\lVert{\bm{y}}_{t}-{\bm{z}}_{t}\right\rVert}^{2}$
(16)

is a Lyapunov candidate and it follows that $W_{t}\in\ell_{\infty}$.
Furthermore,
$\lim_{t\rightarrow\infty}\left[f_{t}(\bm{x}_{t+1})-f_{t}(\bm{x}_{*})\right]=0$.

###### Proof.

We begin by expanding the time step ahead Lyapunov candidate
$W_{t+1}=\mathinner{\\!\left\lVert{\bm{z}}_{t+1}-\bm{x}_{*}\right\rVert}^{2}+\xi_{t+1}\mathinner{\\!\left\lVert{\bm{y}}_{t+1}-{\bm{z}}_{t+1}\right\rVert}$
by substituting the update for ${\bm{y}}_{t+1}$ from (1b) and ${\bm{z}}_{t+1}$
from (1c) and noting that
$\bm{x}_{t}-{\bm{z}}_{t}=\bar{\beta}_{t}({\bm{y}}_{t}-{\bm{z}}_{t})$ from (1a)
where $\bar{\beta}_{t}=1-\beta_{t}$, as defined in (2), we get the following

$W_{t+1}=\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+(\eta_{t}^{2}+\xi_{t+1}(\eta_{t}-\alpha_{t})^{2})\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}-\bm{x}_{*})\\\
+\xi_{t+1}\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+\xi_{t+1}2(\eta_{t}-\alpha_{t})\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t}).$
(17)

Expanding $-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}-\bm{x}_{*})$
as $-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}+\bm{x}_{t}-\bm{x}_{t}-\bm{x}_{*})$
and noting that

$-\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-\bm{x}_{*})\leq(1-\lambda_{t})[f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t})]-\frac{1+\lambda_{t}}{2L}\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2},$

from Lemma 10, it follows that

$\begin{split}-2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}-\bm{x}_{*})\leq&\
2\eta_{t}\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t})+2(1-\lambda_{t})\eta_{t}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))\\\
&-\frac{(1+\lambda_{t})\eta_{t}}{L_{t}}\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}.\end{split}$ (18)

Substitution of Equation (18) into Equation (17)

$\begin{split}W_{t+1}\leq&\left(\eta_{t}^{2}+\xi_{t+1}(\eta_{t}-\alpha_{t})^{2}-\frac{(1+\lambda_{t})\eta_{t}}{L_{t}}\right)\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}+2(1-\lambda_{t})\eta_{t}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))\\\
&+\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\xi_{t+1}\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+[\xi_{t+1}2(\eta_{t}-\alpha_{t})+2\eta_{t}]\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t}).\end{split}$
(19)

Turning our attention to $W_{t}$ and rewriting the second component to be in
terms of $\bm{x}_{t}-{\bm{z}}_{t}$ we have

$W_{t}=\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\xi_{t}\bar{\beta}_{t}^{-2}\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}$
(20)

where we have used the fact that
$\bm{x}_{t}-{\bm{z}}_{t}=(1-\beta_{t})({\bm{y}}_{t}-{\bm{z}}_{t})$ from
Equation (1a). Substracting (20) from (19) with $\Delta W_{t+1}=W_{t+1}-W_{t}$
it follows that

$\begin{split}\Delta
W_{t+1}\leq&\left(\eta_{t}^{2}+\xi_{t+1}(\eta_{t}-\alpha_{t})^{2}-\frac{(1+\lambda_{t})\eta_{t}}{L_{t}}\right)\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}+2(1-\lambda_{t})\eta_{t}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))\\\
&+\left(\xi_{t+1}-\xi_{t}\bar{\beta}_{t}^{-2}\right)\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+[\xi_{t+1}2(\eta_{t}-\alpha_{t})+2\eta_{t}]\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{t}-{\bm{z}}_{t}).\end{split}$

Recall the definitions ${\bm{a}}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{N_{t}}\nabla f_{t}(\bm{x}_{t})$ and
${\bm{b}}\mathrel{\mathop{\mathchar 58\relax}}={\bm{x}_{t}-{\bm{z}}_{t}}$ with
$c_{5},c_{6},c_{7}$ defined in (15) along with

$c_{8}\mathrel{\mathop{\mathchar
58\relax}}=2\frac{(1-\lambda_{t})\gamma_{t}}{N_{t}}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))$

and the fact that $N_{t}\geq L_{t}$, then it follows that $\Delta W_{t+1}\leq
c_{5}\mathinner{\\!\left\lVert{\bm{a}}\right\rVert}^{2}+c_{6}{\bm{a}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}{\bm{b}}+c_{7}\mathinner{\\!\left\lVert{\bm{b}}\right\rVert}^{2}+c_{8}.$
Completing the square we have $\Delta W_{t+1}\leq
c_{5}\mathinner{\\!\left\lVert{\bm{a}}+\frac{c_{6}}{2c_{5}}{\bm{b}}\right\rVert}^{2}+\left(c_{7}-\frac{c_{6}^{2}}{4c_{5}}\right)\mathinner{\\!\left\lVert{\bm{b}}\right\rVert}^{2}+c_{8}.$
By the conditions in (14) it follows that

$\Delta W_{t+1}\leq
2\frac{(1-\lambda_{t})\gamma_{t}}{N_{t}}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))<0\quad\forall\bm{x}_{t}\neq\bm{x}_{*}.$

Following the same steps as outlined at the end of the proof of Proposition 1
it follows that $a_{\tau}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{t=0}^{\tau}[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}_{*})]$ is a
bounded monotonic sequence and therefore
$\lim_{t\rightarrow\infty}\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}_{*})\right]=0$.
∎

######  Corollary 1.1.

Let $f_{t}$ satisfy Assumptions 1-3. For the HT defined in Equation (1) with
arbitrary initial conditions $\\{\bm{x}_{0},{\bm{y}}_{0},{\bm{z}}_{0}\\}$,
$N_{t}\geq L_{t}$ ($f_{t}$ is $L_{t}$ smooth by assumption)

$\displaystyle\gamma_{t}$
$\displaystyle\in[\epsilon,2-\epsilon]\quad\epsilon\in(0,1)$ (21a)
$\displaystyle\mu_{t}$ $\displaystyle=\gamma_{t}$ (21b)
$\displaystyle\beta_{t}$ $\displaystyle\in[0,1-\epsilon]$ (21c)

and where the free design parameters (that only appear in the analysis) can be
chosen as

$\displaystyle\lambda_{t}=\frac{\gamma_{t}}{2}\quad\text{and}\quad\xi_{t}=\frac{1}{\frac{\epsilon}{2}\left((1-\epsilon)^{-2}-1\right)}\quad\text{(a
constant)}.$ (22)

Then all states and gradients are uniformly bounded and
$\lim_{t\rightarrow\infty}\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}_{*})\right]=0$.

######  Remark 2.

With a slightly modified Lyapunov candidate (compare (16) to (4)) we get the
most general bound we are aware of. Note however that the learning rate
parameter $\gamma_{t}$ must be less than 2 for stability to hold, see (14) and
(15a). We raise this point because when the function $f_{t}$ is fixed for all
time ($f_{t}=f$: a constant) Nesterov’s accelerated method requires
$\gamma_{t}$ to increase with time, $t$, in an unbounded fashion (i.e.
$\gamma_{t}\asymp 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.

###  3.3 The smooth and strongly convex setting

We close by showing exponential convergence for time varying strongly convex
functions.

######  Proposition 2.

Let $f_{t}$ satisfy Assumptions 1-3 as well as the additional assumption that
for each $t$, $f_{t}$ is $\sigma_{t}$–strongly convex. For the HT defined in
Equation (1) with arbitrary initial conditions
$\\{\bm{x}_{0},{\bm{y}}_{0},{\bm{z}}_{0}\\}$, $N_{t}\geq L_{t}$ ($f_{t}$ is
$L_{t}$ smooth by assumption), and the same three conditions from Equation (3)
in Proposition 1 satisfied
$\\{\beta_{t}\in[0,1],\mu_{t}\in[\epsilon,1],\epsilon>0,\gamma_{t}=\frac{\mu_{t}}{2}\\}$.
Then,
$V_{t}=\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\mathinner{\\!\left\lVert{\bm{y}}_{t}-{\bm{z}}_{t}\right\rVert}^{2}$
originally defined in (4) is a Lyapunov function which exponentially converges
to zero at rate

$V_{t+1}=\left(1-\omega_{t}\right)V_{t}$ (23)

where

$\displaystyle\omega_{t}\mathrel{\mathop{\mathchar 58\relax}}=$
$\displaystyle\
\min\left\\{\left[(1-\nu_{t})(1-\bar{\beta}_{t}^{2})\right],\left[\frac{\rho_{t}\nu_{t}(1-\bar{\beta}_{t}^{2})}{\rho_{t}\bar{\beta}_{t}^{2}+\nu_{t}(1-\bar{\beta}_{t}^{2})}\right]\right\\},$
(24a) $\displaystyle\rho_{t}\mathrel{\mathop{\mathchar 58\relax}}=$
$\displaystyle\
\frac{\mu_{t}}{2}\frac{\sigma_{t}}{N_{t}},\quad\text{and}\quad\nu_{t}\in[\epsilon,1-\epsilon].$
(24b)

###### Proof.

In order to demonstrate exponential convergence with the Lyapunov function it
suffices to show $V_{t+1}=g_{t}V_{t}$ for some
$g_{t}\in[-1+\epsilon,1-\epsilon]$. We will begin the proof by starting where
we left off with the bound (10) in Proposition 1, expanding the coefficients
and substituting $\gamma_{t}=\mu_{t}/2$ which results in

$\displaystyle\Delta V_{t+1}\leq$
$\displaystyle\frac{\mu_{t}}{N_{t}^{2}}(\mu_{t}-1)\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}+\left(1-\bar{\beta}_{t}^{-2}\right)\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+\frac{\mu_{t}}{N_{t}}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))$
(25a) $\displaystyle\leq$
$\displaystyle\left(1-\bar{\beta}_{t}^{-2}\right)\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+\frac{\mu_{t}}{N_{t}}(f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t}))$
(25b)

where we dropped the first term in (25a) for the second inequality in (25b)
because we typically want the learning rate $\mu_{t}\in[\epsilon,1]$ to be as
large as possible and the first expression in (25a) approaches 0 as $\mu_{t}$
tends to 1. Next we will use the strong convexity assumption along with the
distance to the minimizer bound provided in Lemma 8 for
$f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t})$ and we get

$\Delta
V_{t+1}\leq\left(1-\bar{\beta}_{t}^{-2}\right)\mathinner{\\!\left\lVert\bm{x}_{t}-{\bm{z}}_{t}\right\rVert}^{2}-\rho_{t}\mathinner{\\!\left\lVert\bm{x}_{t}-\bm{x}_{*}\right\rVert}^{2}$
(26)

where we recall the definition of $\rho_{t}$ from (24a). The next step is to
obtain bounds in terms
$\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}$ and
$\mathinner{\\!\left\lVert{\bm{y}}_{t}-{\bm{z}}_{t}\right\rVert}$ with the
hopes that the upper-bound can be expressed in terms $V_{t}$ thus allowing for
some kind of bound of the form $V_{t+1}=g_{t}V_{t}$ as we previously stated.
We accomplish this by adding and subtracting ${\bm{z}}_{t}$ within the norm
$\mathinner{\\!\left\lVert\bm{x}_{t}-\bm{x}_{*}\right\rVert}$ and then using
the fact that
$\bm{x}_{t}-{\bm{z}}_{t}=\bar{\beta}_{t}({\bm{y}}_{t}-{\bm{z}}_{t})$ from (1a)
we obtain

$\Delta
V_{t+1}\leq\bigl{(}\bar{\beta}_{t}^{2}-1\bigr{)}\mathinner{\\!\left\lVert{\bm{y}}_{t}-{\bm{z}}_{t}\right\rVert}^{2}-\rho_{t}\bigl{(}\bar{\beta}_{t}^{2}\mathinner{\\!\left\lVert{\bm{y}}_{t}-{\bm{z}}_{t}\right\rVert}^{2}+2\bar{\beta}_{t}({\bm{y}}_{t}-{\bm{z}}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{z}}_{t}-\bm{x}_{*})+\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}\bigr{)}.$
(27)

As in our prior analysis we define intermediate vectors and scalars to
simplify the expressions with

$\displaystyle{\bm{c}}\mathrel{\mathop{\mathchar
58\relax}}={\bm{y}}_{t}-{\bm{z}}_{t}\quad\quad\quad{\bm{d}}\mathrel{\mathop{\mathchar
58\relax}}={\bm{z}}_{t}-\bm{x}_{*}\quad\quad\quad\psi_{t}^{2}\mathrel{\mathop{\mathchar
58\relax}}=\bar{\beta}_{t}^{2}-1\quad\text{(note that $\psi_{t}\leq 0$) }$
(28)

and rewrite the inequality in (27) giving us the more compact inequality

$\Delta
V_{t+1}\leq\psi_{t}^{2}\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}^{2}-\rho_{t}\left(\bar{\beta}_{t}^{2}\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}^{2}+2\bar{\beta}_{t}{\bm{c}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}{\bm{d}}+\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}^{2}\right).$

We want to have an expression that is negative semidefinite in terms of
$\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}$ and
$\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}$ which we have for
$\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}$, but not yet for
$\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}$. To achieve this we borrow
${\nu_{t}\in[\epsilon,1-\epsilon]}$ from the expression
$\psi_{t}^{2}\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}$ and incorporate
it into the large expression in the parenthesis giving us

$\Delta
V_{t+1}\leq(1-\nu_{t})\psi_{t}^{2}\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}^{2}+\left[\left(-\rho_{t}\bar{\beta}_{t}^{2}+\nu_{t}\psi_{t}^{2}\right)\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}^{2}-2\rho_{t}\bar{\beta}_{t}{\bm{c}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}{\bm{d}}-\rho_{t}\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}^{2}\right].$
(29)

Completing the square for the component in the brackets we have

$\left(-\rho_{t}\bar{\beta}_{t}^{2}+\nu_{t}\psi_{t}^{2}\right)\mathinner{\\!\left\lVert{\bm{c}}+\frac{-2\rho_{t}\bar{\beta}_{t}}{2\left(-\rho_{t}\bar{\beta}_{t}^{2}+\nu_{t}\psi_{t}^{2}\right)}{\bm{d}}\right\rVert}^{2}+\left(-\rho_{t}-\frac{\rho_{t}^{2}\bar{\beta}_{t}^{2}}{\left(-\rho_{t}\bar{\beta}_{t}^{2}+\nu_{t}\psi_{t}^{2}\right)}\right)\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}^{2}.$
(30)

Taking the second component from (30) that is solely a function of
$\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}^{2}$ and using that to bound
the expression in the brackets of Equation (29) we obtain

$\Delta
V_{t+1}\leq-(1-\nu_{t})(1-\bar{\beta}_{t}^{2})\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}^{2}-\frac{\rho_{t}\nu_{t}(1-\bar{\beta}_{t}^{2})}{\rho_{t}\bar{\beta}_{t}^{2}+\nu_{t}(1-\bar{\beta}_{t}^{2})}\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}^{2}$
(31)

Finally, we recognize from the definition of ${\bm{c}}$ and ${\bm{d}}$ that
$V_{t}=\mathinner{\\!\left\lVert{\bm{c}}\right\rVert}^{2}+\mathinner{\\!\left\lVert{\bm{d}}\right\rVert}^{2}$,
and from Equation (31) with a few terms rearranged we arrive at the bound
provided in Equation (23). ∎

##  4 Connections to existing literature

###  4.1 High-order tuner

The HT in (1) was directly inspired by Gaudio et al. [1] which tried to
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. [1] was
$\ddot{\bm{x}}(t)+\beta\dot{\bm{x}}(t)=-\frac{\gamma\beta}{N_{t}}\nabla
f_{t}(\bm{x}(t))$ which the authors recognized could be reparameterized as

$\displaystyle\dot{\bm{z}}(t)$ $\displaystyle=-\frac{\gamma}{N_{t}}\nabla
f_{t}(\bm{x}(t))$ (32a) $\displaystyle\dot{\bm{x}}(t)$
$\displaystyle=-\beta(\bm{x}(t)-{\bm{z}}(t))$ (32b)

where $N_{t}$ varies over time and upper bounds the smoothness of $f_{t}$ at
each $t$. Reparameteriztion to the form in Equation (32) was essential for
discovery of the Lyapunov candidate

$V(t)=\frac{1}{\gamma}\left(\mathinner{\\!\left\lVert{\bm{z}}(t)-\bm{x}_{*}\right\rVert}^{2}+\mathinner{\\!\left\lVert{\bm{z}}(t)-\bm{x}(t)\right\rVert}^{2}\right).$
(33)

What was also shown in Gaudio et al. [1] was that the discretization of
Equation (32) to

$\displaystyle\bm{x}_{t}$
$\displaystyle=\beta{\bm{z}}_{t}+(1-\beta){\bm{y}}_{t}$ (34a)
$\displaystyle{\bm{y}}_{t+1}$
$\displaystyle=\bm{x}_{t}-\tfrac{\gamma\beta}{N_{t}}\nabla
f_{t+1}(\bm{x}_{t})$ (34b) $\displaystyle{\bm{z}}_{t+1}$
$\displaystyle={\bm{z}}_{t}-\tfrac{\gamma}{N_{t}}\nabla f_{t}(\bm{x}_{t})$
(34c)

was also stable and could use the same Lyapunov function (but in discrete time
$V_{t}=\frac{1}{\gamma}\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{*}\right\rVert}^{2}+\frac{1}{\gamma}\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{t}\right\rVert}^{2}$).
For quadratic costs and the HT in (34) they established stability with the
following constraints on their free design parameters from [1, Theorem 4]

$\beta\in(0,1)\quad\gamma\in\left(0,\tfrac{\beta(2-\beta)}{16+\beta^{2}}\right]$
(35)

and for quadratic costs that are $\sigma$-strongly convex a similar but even
more conservative bound was established [1, Theorem 5]. Moreu and Annaswamy
[2] used the same algorithm and analysis to provide similarly conservative
bounds for more general convex functions [2, Theorems 1,2].

There are several differences provided in this work compared to the prior art
[1, 2]. First we note that in our analysis, the free design parameters
$\gamma_{t}$ and $\beta_{t}$ (Equations (1) and (2)) are allowed to be time
varying in comparison to $\gamma,\beta$ in (34). We also added an extra degree
of freedom ($\alpha_{t},\mu_{t}$) in the gradient step size for the update
${\bm{y}}_{t+1}$ (compare (34b) 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 $\gamma_{t}$ and $\beta_{t}$ (compare Equations
(3), (14), (21) to (35)). We also used a different Lyapunov candidate
throughout, not scaling by $\gamma_{t}$ and instead of using
$\mathinner{\\!\left\lVert{\bm{z}}_{t}-\bm{x}_{t}\right\rVert}$ we used
$\mathinner{\\!\left\lVert{\bm{z}}_{t}-{\bm{y}}_{t}\right\rVert}$. In their
work both of these differences are moot because $\gamma_{t},\beta_{t}$ are in
fact treated as constants so we 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 $\bm{x}_{t}$ through
gradients for $f$ at two different time points ($\nabla f_{t+1}(\bm{x}_{t})$
and $\nabla f_{t}(\bm{x}_{t})$ in (34) as compared to just $\nabla
f_{t}(\bm{x}_{t})$ 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 [1, Theorem 5] and [2, Theorem 2]).

###  4.2 Accelerated second order 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 $t$ explicitly denoting their time variation, Assumption 1.
If we set $f_{t}\mathrel{\mathop{\mathchar 58\relax}}=f$ and set our hyper-
parameters as

$\displaystyle\mu_{t}=1\quad\quad\gamma_{t}=\frac{t}{2}\quad\quad\beta_{t}=\frac{2}{t+1}$
(36)

then we exactly recover Nesterov form II [28, 29]. the biggest difference
between these parameters and ours is that in order for us to establish
stability the hyper-parameter $\gamma_{t}$ can not grow unbounded and in our
case could reach a maximum of 2 (compare (21a) to (36)). For any stability
based approach with time varying $f_{t}$, it does not seem possible for a
component of the algorithm to have a learning rate that scales beyond
$\mathcal{O}(1/N_{t})$ as in the case for Nesterov. One of the issues is that
the state ${\bm{z}}_{t}$ 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 ${\bm{z}}_{t}$ that contributes to $\bm{x}_{t}$,
which from (1a) we see is $\beta_{t}{\bm{z}}_{t}$. To that end we tried to
analyze the equivalent dynamics with

$\displaystyle\bm{x}_{t}$
$\displaystyle=\tilde{\bm{z}}_{t}+(1-\beta_{t}){\bm{y}}_{t}$ (37a)
$\displaystyle{\bm{y}}_{t+1}$ $\displaystyle=\bm{x}_{t}-\alpha_{t}\nabla
f_{t}(\bm{x}_{t})$ (37b) $\displaystyle\tilde{\bm{z}}_{t+1}$
$\displaystyle=\frac{\beta_{t+1}}{\beta_{t}}\tilde{\bm{z}}_{t}-\beta_{t+1}\eta_{t}\nabla
f_{t}(\bm{x}_{t})$ (37c)

where $\tilde{\bm{z}}_{t}\mathrel{\mathop{\mathchar
58\relax}}=\beta_{t}{\bm{z}}_{t}$. So now the effective learning rate
associated with the state $\tilde{z}_{t}$ would be
${\beta_{t+1}\eta_{t}=\frac{t}{t+2}\frac{1}{N_{t}}}$ which is indeed
$\mathcal{O}(1/N_{t})$, but we were unsuccessful with this approach.

Others have pointed out stability issues with Nesterov’s method for smooth
convex functions, namely [32]. Much of the prior work has focused on different
definitions of stability and constructing careful examples for a 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 and Koren [32] can be used directly as a
counter example against stability for our algorithm with hyper-parameters as
they are defined in (37) when applied to time varying cost functions.
Furthermore, while Nesterov’s method does indeed have some stability
guarantees for fixed quadratic cost functions [33, 34], we conjecture that
those guarantees vanish when the quadratic cost functions vary over time.

###  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 a fixed cost function the data
arrives in a time varying fashion [20, 21]. We can make this explicit by
assuming we have a set of data $\mathcal{D}$ and at time $t$ we use a piece of
that data $D_{t}\in\mathcal{D}$ to define our time varying cost function
$f_{t}(\cdot)\mathrel{\mathop{\mathchar 58\relax}}=f(\cdot\ ,D_{t})$ from the
fixed but data dependent cost $f$.

When addressing these problems in the online learning setting Regret Analysis
(RA) is used and this requires the learning rates to asymptotically decrease
over time [20].444Adaptive regret analysis [35] looks to overcome some of the
drawbacks mentioned here but we are not aware of their use in the analysis of
second order gradient methods This is accomplished either through explicitly
reducing the learning rates over time or implicitly via scaling the learning
by the accumulated sub-gradients [24, 25]. 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 bounded555“Assume that the function $f_{t}$ has bounded
gradients, $\|\nabla f_{t}(\theta)\|_{2}\leq G$, $\|\nabla
f_{t}(\theta)\|_{\infty}\leq G_{\infty}$ for all $\theta\in R^{d}$ and
distance between any $\theta_{t}$ generated by Adam is bounded,
$\|\theta_{n}-\theta_{m}\|_{2}\leq D$, $\|\theta_{m}-\theta_{n}\|_{\infty}\leq
D_{\infty}$ for any $m,n\in\\{1,...,T\\}$)” – Kingma and Ba [25, page 4,
Theorem 4.1] with projection operators also extensively used in RA.

There are several recent attempts to address the stability of Stochastic
Gradient Descent with Momentum (SGDM) for general smooth convex functions [26,
36]. That work is more in 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) the quantity
$\mathinner{\\!\left\lVert f_{t}({\bm{z}}_{t})-f_{t}(\bm{x}_{*})\right\rVert}$
is directly bounded or included in the Lyapunov candidate, where in our work,
the function $f$ does not appear in the Lyapunov candidate (compare [26,
Equation (5)] or [28, Equation (2.3)] to (4)). 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. [26].

##  5 Discussion

The biggest limitation in our analysis comes via Assumption 2 where we assume
that there exists an optimal point (potentially non-unique) shared by all the
functions $f_{t}$. This is assumed so that there exists an $\bm{x}_{*}$ such
that $\nabla f_{t}(\bm{x}_{*})=0$. This is indeed a limiting assumption. We
note, however, that in the case of Stochastic Gradient Descent (SGD) there is
often the assumption of unbiased gradients. In the setting of SGD Assumption 2
coincides with the unbiased gradient assumption at $\bm{x}_{*}$.666If we
define $f(\cdot)=\frac{1}{T}\sum_{t=1}^{T}f_{t}(\cdot)$ then the unbiased
gradient assumption is simply that $\mathbb{E}[\nabla f_{t}(x)]=\nabla f(x)$.

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
extended to settings where there is feedback with a dynamical system [37]. We
recognise that no method or technique is a panacea. There are scenarios where
the optimality conferred by RA will be preferred, but we also think there are
going to be growing applications in real-time scenarios where stability will
be paramount. Ultimately, we simply hope that these methods might be useful in
providing further insight into second order gradient descent for time varying
functions as well as second order stochastic gradient descent. We are
particularly interested in trying to extend these results to the stochastic
setting.

## Acknowledgments and Disclosure of Funding

This work was supported by the Boeing Strategic University Initiative and NIH
R35GM143056.

## References

  * Gaudio et al. [2021] Joseph E. Gaudio, Anuradha M. Annaswamy, José M. Moreu, Michael A. Bolender, and Travis E. 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_ , pages 636–650. PMLR, 07 – 08 June 2021.  URL https://proceedings.mlr.press/v144/gaudio21a.html.
  * Moreu and Annaswamy [2022] José M. Moreu and Anuradha M. Annaswamy.  A stable high-order tuner for general convex functions.  _IEEE Control Systems Letters_ , 6:566–571, 2022.  doi: 10.1109/LCSYS.2021.3082875.  URL https://arxiv.org/abs/2011.09996.
  * Massera [1956] José L Massera.  Contributions to stability theory.  _Annals of Mathematics_ , 64(1):182–206, 1956\.
  * Bousquet and Elisseeff [2002] Olivier Bousquet and André Elisseeff.  Stability and generalization.  _The Journal of Machine Learning Research_ , 2:499–526, 2002.
  * Narendra and Annaswamy [2012] Kumpati S Narendra and Anuradha M Annaswamy.  _Stable adaptive systems_.  Courier Corporation, 2012.
  * Ioannou and Sun [2012] Petros A Ioannou and Jing Sun.  _Robust adaptive control_.  Courier Corporation, 2012.
  * Hazan and Singh [2022] Elad Hazan and Karan Singh.  Introduction to online nonstochastic control, 2022.  URL https://arxiv.org/abs/2211.09619.
  * Tsiamis et al. [2022] Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J. Pappas.  Statistical learning theory for control: A finite sample perspective, 2022\.  URL https://arxiv.org/abs/2209.05423.
  * dar [2019] Real time machine learning (rtml).  Technical Report HR001119S0037, Defense Advanced Research Projects Agency, March 2019.
  * [10] Real-time machine learning (rtml).  Technical Report NSF 19-566, National Science Foundation.  URL https://www.nsf.gov/pubs/2019/nsf19566/nsf19566.htm#toc.
  * Chen and Liu [2018] Zhiyuan Chen and Bing Liu.  Lifelong machine learning.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , 12(3):1–207, 2018.
  * Parisi et al. [2019] German I. Parisi, Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter.  Continual lifelong learning with neural networks: A review.  _Neural Networks_ , 113:54–71, 2019.  ISSN 0893-6080.  doi: https://doi.org/10.1016/j.neunet.2019.01.012.  URL https://www.sciencedirect.com/science/article/pii/S0893608019300231.
  * McCloskey and Cohen [1989] Michael McCloskey and Neal J Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  In _Psychology of learning and motivation_ , volume 24, pages 109–165. Elsevier, 1989.
  * Goodfellow et al. [2016] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio.  _Deep learning_ , volume 1.  MIT Press, 2016.
  * Polyak [1964] Boris T Polyak.  Some methods of speeding up the convergence of iteration methods.  _Ussr computational mathematics and mathematical physics_ , 4(5):1–17, 1964.
  * Nesterov [1983] Yurii Nesterov.  A method for solving a convex programming problem with convergence rate $o(1/k^{2})$.  _Dokl. Akad. Nauk SSSR_ , 269(3):543–547, 1983\.
  * Su et al. [2014] Weijie Su, Stephen Boyd, and Emmanuel Candes.  A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.
  * Wibisono et al. [2016] 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/pnas.1614734113.  URL https://www.pnas.org/content/113/47/E7351.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gabor Lugosi.  _Prediction, Learning, and Games_.  Cambridge University Press, 2006.  doi: 10.1017/CBO9780511546921.
  * Shalev-Shwartz [2012] Shai Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends® in Machine Learning_ , 4(2):107–194, 2012.  ISSN 1935-8237.  doi: 10.1561/2200000018.  URL http://dx.doi.org/10.1561/2200000018.
  * Hardt et al. [2016] Moritz Hardt, Ben Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In _International conference on machine learning_ , pages 1225–1234. PMLR, 2016.
  * Bottou et al. [2018] Léon Bottou, Frank E Curtis, and Jorge Nocedal.  Optimization methods for large-scale machine learning.  _SIAM review_ , 60(2):223–311, 2018.
  * Tieleman and Hinton [2012] Tijmen Tieleman and Geoffrey Hinton.  Lecture 6.5 rmsprop, coursera: Neural networks for machine learning.  _University of Toronto Technical Report_ , 2012.
  * Duchi et al. [2011] John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(Jul):2121–2159, 2011.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _Proceedings of the 3rd International Conference on Learning Representations (ICLR)_ , 2015.  URL https://openreview.net/forum?id=8gmWwjFyLj.
  * Liu et al. [2020] Yanli Liu, Yuan Gao, and Wotao Yin.  An improved analysis of stochastic gradient descent with momentum.  _Advances in Neural Information Processing Systems_ , 33:18261–18271, 2020.
  * Morse [1992] AS Morse.  High-order parameter tuners for the adaptive control of linear and nonlinear systems.  In _Systems, Models and Feedback: Theory and Applications:_ , 1992\.
  * Ahn and Sra [2022] Kwangjun Ahn and Suvrit Sra.  _Understanding Nesterov’s Acceleration via Proximal Point Method_ , pages 117–130.  2022\.  doi: 10.1137/1.9781611977066.9.  URL https://epubs.siam.org/doi/abs/10.1137/1.9781611977066.9.
  * Nesterov [2018] Yurii Nesterov.  _Lectures on convex optimization_.  Springer, 2018.
  * Rudin [1976] W. Rudin.  _Principles of Mathematical Analysis_.  International series in pure and applied mathematics. McGraw-Hill, 1976\.  ISBN 9780070856134.  URL https://books.google.com/books?id=kwqzPAAACAAJ.
  * Farkas and Wegner [2016] Bálint Farkas and Sven-Ake Wegner.  Variations on Barbălat’s lemma.  _The American Mathematical Monthly_ , 123(8):825–830, 2016.
  * Attia and Koren [2021] Amit Attia and Tomer Koren.  Algorithmic instabilities of accelerated gradient descent.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 1204–1214. Curran Associates, Inc., 2021.
  * Chen et al. [2018] Yuansi Chen, Chi Jin, and Bin Yu.  Stability and convergence trade-off of iterative optimization algorithms, 2018.  URL https://arxiv.org/abs/1804.01619.
  * Lessard et al. [2016] Laurent Lessard, Benjamin Recht, and Andrew Packard.  Analysis and design of optimization algorithms via integral quadratic constraints.  _SIAM Journal on Optimization_ , 26(1):57–95, 2016.
  * Hazan and Seshadhri [2009] Elad Hazan and Comandur Seshadhri.  Efficient learning algorithms for changing environments.  In _Proceedings of the 26th annual international conference on machine learning_ , pages 393–400, 2009.
  * Yan et al. [2018] Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang.  A unified analysis of stochastic momentum methods for deep learning.  _arXiv preprint arXiv:1808.10396_ , 2018.
  * Gaudio et al. [2019] Joseph E Gaudio, Travis E Gibson, Anuradha M Annaswamy, Michael A Bolender, and Eugene Lavretsky.  Connections between adaptive control and optimization in machine learning.  In _2019 IEEE 58th Conference on Decision and Control (CDC)_ , pages 4563–4568. IEEE, 2019.
  * Boyd and Vandenberghe [2004] Stephen Boyd and Lieven Vandenberghe.  _Convex Optimization_.  Cambridge University Press, 2004.  doi: 10.1017/CBO9780511804441.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.  ISSN 1935-8237.  doi: 10.1561/2200000050.  URL http://dx.doi.org/10.1561/2200000050.
  * Hazan [2022] Elad Hazan.  _Introduction to online convex optimization_.  2022\.

##  Appendix A Technical Lemmas and Corollaries

These technical lemmas can be found in most standard texts on convex
optimization [38, 39, 40]

######  Lemma 2 (First order condition of convexity [38, §3.1.3]).

Let $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a differentiable convex
function. Then $\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$,

$f({\bm{y}})\geq f(\bm{x})+\nabla
f(\bm{x})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{y}}-\bm{x})$

######  Lemma 3 (Basic property of smooth convex functions).

A continuously differentiable convex function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is L-smooth if and only if
$\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$,

$f({\bm{y}})\leq f(\bm{x})+\nabla
f(\bm{x})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}({\bm{y}}-\bm{x})+\frac{L}{2}\mathinner{\\!\left\lVert{\bm{y}}-\bm{x}\right\rVert}^{2}.$

######  Lemma 4 (Basic property of strongly convex functions).

If a continuously differentiable convex function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is $\sigma$-strongly convex ,
then $\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$

$(\nabla f(\bm{x})-\nabla
f({\bm{y}}))^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}-{\bm{y}})\geq\sigma\mathinner{\\!\left\lVert\bm{x}-{\bm{y}}\right\rVert}^{2}.$

######  Lemma 5 (co-coercivity of smooth convex functions).

If a continuously differentiable convex function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is L-smooth , then
$\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$

$(\nabla f(\bm{x})-\nabla
f({\bm{y}}))^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}-{\bm{y}})\geq\frac{1}{L}\mathinner{\\!\left\lVert\nabla
f(\bm{x})-\nabla f({\bm{y}})\right\rVert}^{2}.$

######  Lemma 6 (co-coercivity of smooth and strongly convex functions).

If a continuously differentiable convex function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is L-smooth and
$\sigma$-strongly convex , then $\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$

$(\nabla f(\bm{x})-\nabla
f({\bm{y}}))^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}-{\bm{y}})\geq\frac{\sigma
L}{\sigma+L}\mathinner{\\!\left\lVert\bm{x}-{\bm{y}}\right\rVert}^{2}+\frac{1}{\sigma+L}\mathinner{\\!\left\lVert\nabla
f(\bm{x})-\nabla f({\bm{y}})\right\rVert}^{2}.$

######  Lemma 7 (distance to minimizer for smooth convex functions).

If a continuously differentiable convex function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is L-smooth , then
$\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$

$\frac{1}{2L}\mathinner{\\!\left\lVert\nabla f(\bm{x})\right\rVert}^{2}\leq
f(\bm{x})-f(\bm{x}_{*})\leq\frac{L}{2}\mathinner{\\!\left\lVert\bm{x}-\bm{x}_{*}\right\rVert}^{2}.$

######  Lemma 8 (distance to minimizer for strongly convex functions).

If a continuously differentiable function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{N}\rightarrow\mathbb{R}$ is $\sigma$-strongly convex,
then $\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$

$\frac{1}{2\sigma}\mathinner{\\!\left\lVert\nabla
f(\bm{x})\right\rVert}^{2}\geq
f(\bm{x})-f(\bm{x}_{*})\geq\frac{\sigma}{2}\mathinner{\\!\left\lVert\bm{x}-\bm{x}_{*}\right\rVert}^{2}.$

######  Lemma 9 (Bubeck [39, Lemma 3.5]).

Let $f_{t}$ be a $L$-smooth convex function. Then
$\forall\bm{x},{\bm{y}}\in\mathbb{R}^{N}$,

$f(\bm{x})-f({\bm{y}})\leq\nabla
f_{t}(\bm{x})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}-{\bm{y}})-\frac{1}{2L}\mathinner{\\!\left\lVert\nabla
f(\bm{x})-\nabla f({\bm{y}})\right\rVert}^{2}.$

######  Corollary 9.1.

Under the setting in Lemma 9 with $\bm{x}=\bm{x}_{t}$, ${\bm{y}}=\bm{x}_{*}$,
and $\nabla f_{t}(\bm{x}_{*})=0$ the bound becomes

$\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{*}-\bm{x}_{t})\leq\left[f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t})\right]-\frac{1}{2L}\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}.$

######  Lemma 10.

Under the setting in Lemma 9 with $\bm{x}=\bm{x}_{t}$, ${\bm{y}}=\bm{x}_{*}$,
and $\nabla f_{t}(\bm{x}_{*})=0$ and for any $\lambda\in[0,1]$ the bound
becomes

$\nabla
f_{t}(\bm{x}_{t})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}(\bm{x}_{*}-\bm{x}_{t})\leq(1-\lambda)\left[f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t})\right]-\frac{1+\lambda}{2L}\mathinner{\\!\left\lVert\nabla
f_{t}(\bm{x}_{t})\right\rVert}^{2}.$

###### Proof.

Add and subtract $\lambda\left[f_{t}(\bm{x}_{*})-f_{t}(\bm{x}_{t})\right]$ and
apply Lemma 7. ∎