# SGEM: STOCHASTIC GRADIENT WITH ENERGY AND
## MOMENTUM

**Anonymous authors**
Paper under double-blind review

ABSTRACT

In this paper, we propose SGEM, Stochastic Gradient with Energy and Momentum to solve a large class of general non-convex stochastic optimization problems,
based on the AEGD method that originated in the work [AEGD: Adaptive Gradient Descent with Energy. arXiv: 2010.05109]. SGEM incorporates both energy
and momentum at the same time so as to inherit their dual advantages. We show
that SGEM features an unconditional energy stability property, and derive energydependent convergence rates in the general nonconvex stochastic setting, as well
as a regret bound in the online convex setting. A lower threshold for the energy
variable is also provided. Our experimental results show that SGEM converges
faster than AEGD and generalizes better or at least as well as SGDM in training
some deep neural networks.

1 INTRODUCTION

In this paper, we propose SGEM: Stochastic Gradient with Energy and Momentum to solve the
following general non-convex stochastic optimization problem

min (1)
_θ_ R[d][ f] [(][θ][) :=][ E][ξ][[][f] [(][θ][;][ ξ][)]][,]
_∈_

differentiable and bounded from below, i.e.,where Eξ[·] denotes the expectation with respect to the random variable f _[∗]_ = inf _θ∈Rd f_ (θ) > −c for some ξ. We assume that c > 0. _f is_

Problem (1) arises in many statistical learning and deep learning models (LeCun et al., 2015; Goodfellow et al., 2016; Bottou et al., 2018). For such large scale problems, it would be too expensive to
compute the full gradient ∇f (θ). One approach to handle this difficulty is to use an unbiased estimator of _f_ (θ). Denote the stochastic gradient at the t-th iteration as gt, the iteration of Stochastic
_∇_
Gradient Descent (SGD) (Robbins & Monro, 1951) can be described as:

_θt+1 = θt −_ _ηtgt,_

where ηt is called the learning rate. Its convergence is known to be ensured if ηt meets the sufficient
condition:


_ηt[2]_ _[<][ ∞][.]_ (2)
_t=1_

X


_ηt = ∞,_
_t=1_

X


However, vanilla SGD suffers from slow convergence due to the variance of the stochastic gradient,
which is one of the major bottlenecks for practical use of SGD (Bottou, 2012; Shapiro & Wardi,
1996). Its performance is also sensitive to the learning rate, which is tricky to tune via (2). Different techniques have been introduced to improve the convergence and robustness of SGD, such
as variance reduction (Defazio et al., 2014; Lei et al., 2017; Johnson & Zhang, 2013; Osher et al.,
2019), momentum acceleration (Allen-Zhu, 2018; Sutskever et al., 2013), and adaptive learning rate
(Duchi et al., 2011; Tieleman & Hinton, 2012; Kingma & Ba, 2017). Among these, momentum and
adaptive learning rate techniques are most economic since they require slightly more computation
in each iteration. However, training with adaptive algorithms such as Adam or its variants typically
generalizes worse than SGD with momentum (SGDM), even when the training performance is better
Wilson et al. (2018).

The most popular momentum technique, Heavy Ball (HB) (Polyak, 1964) has been extensively
studied for stochastic optimization problems (Liu et al., 2020b; Jin et al., 2018; Qian, 1999). SGDM,


-----

also called SHB, as a combination of SGD and momentum takes the following form

_mt = µmt_ 1 + gt, θt+1 = θt _ηtmt,_
_−_ _−_

where m0 = 0 and µ ∈ (0, 1) is the momentum factor. This helps to reduce the variance in stochastic
gradients thus speeds up the convergence, and has been found to be successful in practice (Sutskever
et al., 2013).

AEGD originated in the work Liu & Tian (2020) is a gradient-based optimization algorithm that
adjusts the learning rate by a transformed gradient v and an energy variable r. The method includes
two ingredients: the base update rule:

_rt_
_θt+1 = θt + 2ηrt+1vt,_ _rt+1 =_ _,_ (3)

1 + 2ηvt[2]

and the stochastic evaluation of the transformed gradient vt as

_gt_
_vt =_ _._ (4)

2 _f_ (θt; ξt) + c

AEGD is unconditionally energy stable with guaranteed convergence in energy regardless of the sizep
of the base learning rate η > 0 and how vt is evaluated. This explains why the method can have a
rapid initial training process as well as good generalization performance (Liu & Tian, 2020).

In this paper, we attempt to incorporate both energy and momentum at the same time so as to inherit
their dual advantages. We do so by keeping the base AEGD update rule (3), but taking

_mt_
_vt =_ _,_ _mt = βmt_ 1 + (1 _β)gt,_ _β_ (0, 1). (5)

2(1 _β[t])_ _f_ (θt; ξt) + c _−_ _−_ _∈_
_−_

We call this novel method SGEM. An immediate advantage is that with suchp _vt one can significantly_
reduce the oscillations observed in the AEGD in stochastic cases. Regarding the theoretical results,
in this work we develop a convergence theory for SGEM, in both stochastic nonconvex setting and
online convex setting. While in Liu & Tian (2020), convergence analysis is provided mainly in
deterministic setting, and the result in the stochastic setting is only an upper bound on the norm of
the stochastic transformed gradient v rather than on ∇f (θ).

We highlight the main contributions of our work as follows:

-  We propose a novel and simple gradient-based method SGEM which integrates both energy
and momentum. The only hyperparameter requires tuning is the base learning rate.

-  We show the unconditional energy stability of SGEM, and provide energy-dependent convergence rates in the general stochastic nonconvex setting, and a regret bound for the online
convex framework. We also obtain a lower threshold for the energy variable. Our assumptions are natural and mild.

-  We empirically validate the good performance of SGEM on several deep learning benchmarks. Our results show that

**– The base learning rate requires little tuning on complex deep learning tasks.**
**– Overall, SGEM is able to achieve both fast convergence and good generalization per-**
formance. Specifically, SGEM converges faster than AEGD and generalizes better or
at least as well as SGDM.

**Related works. The essential idea behind AEGD is the so called Invariant Energy Quadratiza-**
ton (IEQ) strategy, originally introduced for developing linear and unconditionally energy stable
schemes for gradient flows in the form of partial differential equations (Yang, 2016; Zhao et al.,
2017). As for gradient-based methods, there has appeared numerous works on the analysis of convergence rates. In online convex setting, a regret bound for SGD is derived in Zinkevich (2003); the
classical convergence results of SGD in stochastic nonconvex setting can be found in Bottou et al.
(2018); For SGDM, we refer the readers to Yu et al. (2019); Yan et al. (2018); Liu et al. (2020b)
for convergence rates on smooth nonconvex objectives. For adaptive gradient methods, most convergence analysis are restricted to online convex setting (Duchi et al., 2011; Reddi et al., 2018; Luo
et al., 2019), while recent attempts, such as Chen et al. (2019); Zou et al. (2019), have been made to
analyze the convergence in stochastic nonconvex setting.


-----

This paper is organized as follows. We first review AEGD in Section 2, then introduce the proposed
algorithm in Section 3. Theoretical analysis including unconditional energy stability, convergence
rates in both stochastic nonconvex setting and online convex setting are presented in Section 4. In
Section 5, we report some experimental results on deep learning tasks.

**Notation For a vector θ ∈** R[n], we denote θt,i as the i-th element of θ at the t-th iteration. For vector
norm, we use to denote l2 norm and use to denote l norm. We also use [m] to represent
_∥· ∥_ _∥· ∥∞_ _∞_
the list {1, ..., m} for any positive integer m.

2 REVIEW OF AEGD

Recall that for the objective function f, we assume that f is differentiable and bounded from below,
i.e., f (θ) > −c for some c > 0. The key idea of AEGD introduced in Liu & Tian (2020) is the use
of an auxiliary energy variable r such that

_∇f_ (θ) = 2rv, _v := ∇_ _f_ (θ) + c, (6)

where r, taking as _f_ (θ) + c initially, will be updated together withp _θ, and v is dubbed as the_

transformed gradient. The gradient flow _θ[˙] =_ _f_ (θ) is then replaced by

p _−∇_

_θ˙ = −2rv,_ _r˙ = v ·_ _θ.[˙]_

A simple implicit-explicit discretization gives the following AEGD update rule:

_f_ (θt)
_vt =_ _∇_ _._ (7a)

2 _f_ (θt) + c
p


_θt+1 = θt −_ 2ηrt+1vt, (7b)
_rt+1 −_ _rt = vt · (θt+1 −_ _θt)._ (7c)

This yields a decoupled update for r as rt+1 = rt/(1 + 2η|vt|[2]), which serves to adapt the learning rate. For large-scale problems, stochastic sampling approach is preferred. Let f (θt; ξt) be a
stochastic estimator of the function value f (θt) at the t-th iteration, gt be a stochastic estimator of
the gradient ∇f (θt), then the stochastic version of AEGD is still (7) but with vt replaced by

_gt_
_vt =_ _._

2 _f_ (θt; ξt) + c

Usually, gt should be required to satisfy E[gtp] = ∇f (θt) and E[∥gt∥[2]] bounded. Correspondingly,
an element-wise version of AEGD for stochastic training reads as

_gt,i_
_vt,i =_ 2 _f_ (θt; ξt) + c _,_ _i ∈_ [n], (8a)

p


_rt,i_
_rt+1,i =_ _,_ _r1,i =_

1 + 2ηvt,i[2]


_f_ (θ1; ξ1) + c, (8b)


_θt+1,i = θt,i −_ 2ηrt+1,ivt,i. (8c)

The element-wise AEGD allows for different effective learning rates for different coordinates, which
has been empirically verified to be more effective than the global AEGD (7). For further details, we
refer to Liu & Tian (2020). We will focus only on the element-wise version of SGEM in what
follows.

3 THE PROPOSED ALGORITHM

In this section, we present a novel algorithm to improve AEGD with added momentum in the following manner:


_mt = βmt_ 1 + (1 _β)gt,_ _m0 = 0,_ (9a)
_−_ _−_

_mt_
_vt =_ _,_ (9b)

2(1 _β[t])_ _f_ (θt; ξt) + c
_−_
p


-----

where β ∈ (0, 1) controls the weight for gradient at each step. With vt so defined, the update
rule for r and θ are kept the same as given in (8b, c). The relation between the energy and the
momentum in the algorithm is realized through relating(as an approximation of _F =_ _∇f_ _mt ( as an approximation to ∇f_ ) to vt

learning tasks, f as a loss function is often in the form of ∇ 2[√]f +c [), where][ v][t][ is used to update the energy] f (θ) = _m[1]_ _mi=1_ _[l][i][(][θ][)][, where][ r][t][+1][ l][. In machine][i][, measuring]_

the distance between the model output and target label at the i-th data point, is typically bounded
from below, that is, li(θ) > _c,_ _i_ [m], for some c > 0. HenceP c in (9b) can be easily chosen
_−_ _∀_ _∈_
in advance so that f (θt; ξt) as a random sample from {li(θt)}i[m]=1 [is bounded below by][ −][c][ for all]
_t ∈_ [T ]. We summarize this in Algorithm 1 (called SGEM, for short).

A key feature of SGEM is that it incorporates momentum into AEGD without changing the overall
structure of the AEGD algorithm (the update of r and θ remain the same) so that it is shown (in
Section 4) to still enjoy the unconditional energy stability property as AEGD does. In addition, by
using mt instead of gt, the variance can be largely reduced. In fact, as proved in Liu et al. (2020b),
combination of the gradients at all previous steps,under the assumption Eξt [∥gt −∇f (θt)∥[2]] = σg[2] _[<][ ∞][,][ m][t][, which can be expressed as a linear]_


_β[t][−][j]gj,_ (10)
_j=1_

X


_mt = (1 −_ _β)_

enjoys a reduced “variance” in the sense that


2[#]


Eξt


_β[t][−][j]_ _f_ (θj)
_∇_
_j=1_

X


_≤_ (1 − _β)σg[2][.]_



[#]

Eξt _β[t][−][j]∇f_ (θj) _≤_ (1 − _β)σg[2][.]_

" _j=1_

X

_[m][t][ −]_ [(1][ −] _[β][)]_

**Algorithm 1 SGEM. Good default setting for parameters are η = 0.2, β = 0.9**


**Require: the base learning rate η; a constant c such that f** (θt; ξt) + c > 0 for all t ∈ [T ]; a
momentum factor β ∈ (0, 1).

**Require: Initialization: θ1; m0 = 0; r1 =** _f_ (θ1; ξ1) + c 1

1: for t = 1 to T − 1 do p
2: Compute gradient: gt = ∇f (θt; ξt)

3: _mt = βmt_ 1 + (1 _β)gt (momentum update)_
_−_ _−_

4: _vt = mt/(2(1 −_ _β[t])_ _f_ (θt; ξt) + c) (transformed momentum)

5: _rt+1 = rt/(1 + 2ηvt_ _vt) (energy update)_

7:6: end forθt+1 = θt − 2ηrt+1 ⊙p ⊙vt (state update)
8: return θT

**Remark 3.1. (i) In Algorithm 1, we use x ⊙** _y to denote element-wise product, x/y to denote_
_element-wise division of two vectors x, y ∈_ R[n].
_(ii) It is clear that mt defined in (10) is not a convex combination of gj, this is why there is a factor_
1 − _β[t]_ _in (9b); such treatment is dubbed as bias correction in Kingma & Ba (2017) for Adam._
_(iii) In most machine learning problems, we have f_ (θ) ≥ 0, for which a good default value for c in
_Algorithm 1 is 1._

4 THEORETICAL RESULTS

In this section, we present our theoretical results, including the unconditional energy stability of
SGEM, the convergence of SGEM for the general stochastic nonconvex optimization, a lower bound
for energy rT, and a regret bound in the online convex setting.

4.1 UNCONDITIONAL ENERGY STABILITY

**Theorem 4.1. (Unconditional energy stability) SGEM in Algorithm 1 is unconditionally energy**
_stable in the sense that for any step size η > 0,_

E[rt[2]+1,i[] =][ E][[][r]t,i[2] []][ −] [E][[(][r][t][+1][,i] _i_ [n], (11)

_[−]_ _[r][t,i][)][2][]][ −]_ _[η][−][1][E][[(][θ][t][+1][,i]_ _[−]_ _[θ][t,i][)][2][]][,]_ _∈_


-----

_that is E[rt,i] is strictly decreasing and convergent with E[rt,i] →_ E[ri[∗][]][ as][ t][ →∞][, and also]


lim
_t→∞_ [E][[(][θ][t][+1][,i][ −] _[θ][t,i][)][2][] = 0][,]_


_t=1_ E[(θt+1,i − _θt,i)[2]] ≤_ _η(f_ (θ1) + c), _∀i ∈_ [n]. (12)

X


**Remark 4.1. (i) The unconditional energy stability only depends on (8b, c), irrespective of the**
_choice for vt. This property essentially means that the energy variable rt, which serves to approxi-_
_mate(ii) (12) indicates that the sequencef_ (θt) + c, is strictly decreasing for anyθt+1 _θt_ _η >converges to zero at a rate of at least 0._ 1/√t. We note

_that this does not guarantee the convergence ofp_ _∥_ _−_ _∥_ _θt_ _unless additional information on the geometry_
_{_ _}_
_of f is available._

_Proof. From (8b, c) we have_


(θt+1,i _θt,i)[2]_ = 4η[2]rt[2]+1,i[v]t,i[2] (By 8c)
_−_

= (2ηrt+1,i)(rt,i _rt+1,i)_ (By 8b)
_−_

= η((rt,i[2] _t+1,i[)][ −]_ [(][r][t,i]

_[−]_ _[r][2]_ _[−]_ _[r][t][+1][,i][)][2][)][.]_

This upon taking expectation ensures the asserted properties. Such proof with no use of the special
form of vt, is the same as that for AEGD (see Liu & Tian (2020)).

4.2 CONVERGENCE ANALYSIS


Below, we state the necessary assumptions that are commonly used for analyzing the convergence
of a stochastic algorithm for nonconvex problems, and notations that will be used in our analysis.
**Assumption 4.1. 1. (Smoothness) The objective function in (1) is L-smooth: for any x, y ∈** R[n],

_f_ (y) _f_ (x) + _f_ (x)[⊤](y _x) +_ _[L]_
_≤_ _∇_ _−_ 2 _[∥][y][ −]_ _[x][∥][2][.]_

_2. (Independent samples) The random samples {ξt}t[∞]=1_ _[are independent.]_

_3. (Unbiasedness) The estimator of the gradient and function value are unbiased:_

Eξt [gt] = ∇f (θt), Eξt [f (θt; ξt)] = f (θt).

Denoting the variance of the stochastic gradient and function value by σg and σf, respectively:


Eξt [∥gt −∇f (θt)∥[2]] = σg[2][,] Eξt [|f (θt; ξt) − _f_ (θt)|[2]] = σf[2][.]

We have the following results.

**Theorem 4.2. Let {θt} be the solution sequence generated by Algorithm 1 with a fixed η > 0.**
_Under Assumption 4.1 and assume that the stochastic gradient and function value are bounded such_
_that ∥gt∥∞_ _≤_ _G∞_ _and 0 < a ≤_ _f_ (θt; ξt) + c ≤ _B, then σg ≤_ _G∞_ _and for all T ≥_ 1,


_≤_ _[C][1][ +][ C][2][n][ +]ηT[ C][3][σ][g]_


_nT_


1

_T_ [E]


_f_ (θt)
_∥∇_ _∥[2]_
_t=1_

X


min _rT,i_


_where C1, C2, C3 are constants depending on β, η, L, G_ _, a, B, n and f_ (θ1) + c.
_∞_

**Remark 4.2. (i) Numerically we observe that for reasonable choice of η, rt,i decays much slower**
_than 1/√t (See Figures 1), thus the convergence result in Theorem 4.2 is meaningful. The question_

_of how rT depends on T is theoretically interesting but subtle to characterize. Nevertheless, in The-_
_orem 4.3 below, we identify a sufficient condition for ensuring a lower threshold for E[rT,i], from_
_which we see that in the absence of noise, i.e σg = 0, mini ri[∗]_ _[>][ 0][ can be ensured, then the rate of]_
_O(1/T_ ) is recovered in Theorem 4.2.
_(ii) The assumption that the magnitude of the stochastic gradient is bounded is standard in non-_
_convex stochastic analysis (Bottou et al., 2018). As for the upper bound on the stochastic func-_
_tion value, we recall the new introduced update rule in SGEM (9a,b): to bound vt, we don’t_
_need an upper bound on f_ _; while such upper bound is technically needed to bound mt since_
_mt = 2(1 −_ _β[t])[√]f + cvt._


-----

Figure 1: mini rt,i of SGEM with default base learning rate 0.2 in training DL tasks.

We only present a sketch of proofs for Theorem 4.2 and 4.3 here, using notation _F[˜]t_ =

_f_ (θt; ξt) + c, ηt = η/F[˜]t and viewing rt+1 as a n × n diagonal matrix that is made up of

[rt+1,1, ..., rt+1,i, ..., rt+1,n]. Detailed proofs, including two crucial lemmas and the full proof for

p

Theorem 4.4, are deferred to the appendix.

_Proof. Using the L-smoothness of f_, we have

_f_ (θt+1) _f_ (θt) _f_ (θt)[⊤](θt+1 _θt) +_ _[L]_ (13)
_−_ _≤∇_ _−_ 2 _[∥][θ][t][+1][ −]_ _[θ][t][∥][2][.]_

The first term on the RHS is carefully regrouped as


_−_ 1[1][ −]β[β][t][ ∇][f] [(][θ][t][)][⊤][η][t][−][1][r][t][g][t][ + 1]1 _[ −]β[β][t][ ∇][f]_ [(][θ][t][)][⊤][(][η][t][−][1][r][t][ −] _[η][t][r][t][+1][)][g][t][ −]_

_−_ _−_

Taking a conditional expectation on the first term gives


_β_

1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][r][t][+1][m][t][−][1][.]
_−_


1 _β_
_−_ min _rt,i_ _f_ (θt) _._

1 − _β[t][ η][t][−][1][∇][f]_ [(][θ][t][)][T][ r][t][∇][f] [(][θ][t][)][ ≥] [(1][ −] _[β][)][ η]√B_ _i_ _∥∇_ _∥[2]_

We manage to bound the other two terms in terms of _ni=1_ _Tt=1_ _[r][t][+1][,i][g]t,i[2]_ and
_n_ _T_
_i=1_ _t=1_ _[r][t][+1][,i][m]t,i[2]_ [. Their bounds are presented in Lemma A.2. The asserted bound then fol-]P P
lows by further summation in t with telescope cancellation for f (θt+1) _f_ (θt) and bounding the
P P _−_
last term in (13) using (12).


4.3 LOWER BOUND FOR THE ENERGY

First note that the L-smoothness of f (θ) implies the LF -smoothness of F (θ) =


_f_ (θ) + c with

(14)


_G[2]_
_L +_ _∞_

2F [2](θ[∗])


_LF =_


2F (θ[∗])


This will be used in the following result and its proof.
**Theorem 4.3 (Lower bound of rT ). Under the same assumptions as in Theorem 4.2, we have**

min E[rT,i] max _F_ (θ[∗]) _ηD1_ _βD2_ _σD3, 0_ _,_ (15)
_i_ _≥_ _{_ _−_ _−_ _−_ _}_

_where σ = max_ _σf_ _, σg_ max _G_ _, B_ _with LF given in (14) and_
_{_ _}≤_ _{_ _∞_ _}_

_√BnF_ (θ1)

_D1 =_ _[L][F][ nF][ 2][(][θ][1][)]_ _,_ _D2 =_

2 (1 _β)[√]a [,]_

_−_

1 _G[2]_
_D3 =_ _ηnT_ _∞_

2[√]a [+][ F] [(][θ][1][)] 4a[3][ + 1]a _[.]_

r

p

_Moreover, in the absence of noise, we have_

min _rT,i > min_ _ri[∗]_ _[>][ 0]_ _if_ _ηD1 + µD2 < F_ (θ[∗]). (16)


-----

**Remark 4.3. (i) (16) is only a sufficient condition, not used as a guide for choosing η. We observe**
_from our experimental results that the upper bound for η to guarantee the positiveness of ri[∗]_ _[can be]_
_much larger (See Figure 1)._
_(ii) In Theorem 4.3, we measure how far r[∗]_ _can deviate from F_ (θ[∗]) in the worst situation. Under
_the stochastic nonconvex setting, ηD1 is the error brought by the step size η, βD2 is due to the use_
_of momentum, and σD3 is responsible for the existence of noise._
_(iii) In the case of no momentum and no noise, we have_

min _rT,i > min_ _ri[∗]_ _[>][ 0]_ _if_ _η < [F]_ [(][θ][∗][)] _._
_i_ _i_ _D1_

_This captures the result for the deterministic AEGD obtained in Liu & Tian (2020)._

_Proof. Using the LF -smoothness of F_ (θ), we have


_F_ (θt+1) _F_ (θt) _F_ (θt)[⊤](θt+1 _θt) +_ _[L][F]_ (17)
_−_ _≤∇_ _−_ 2 _[∥][θ][t][+1][ −]_ _[θ][t][∥][2][,]_

in which the key term _F_ (θt)[⊤](θt+1 _θt) can be decomposed into three terms:_
_∇_ _−_

_vt_ _vt_

( _F_ (θt) )[⊤](θt+1 _θt),_ ( _[g][t]_ (
_∇_ _−_ 2 [g]F[˜][t]t _−_ 2 F[˜]t _−_ 1 _β_ [)][⊤][(][θ][t][+1][ −] _[θ][t][)][,]_ 1 _β_ [)][⊤][(][θ][t][+1][ −] _[θ][t][)][,]_

_−_ _−_

The first two terms are bounded by using the bounded variance assumption and (12), respectively.
We convert the last term, using (recall 7c)

_rt+1,i −_ _rt,i = vt,i(θt+1,i −_ _θt,i),_

into expressions in terms of rt+1,i _rt,i, which upon summation is bounded by rT,i. The last term_
in (17) is bounded again by using (12). −

4.4 REGRET BOUND FOR ONLINE CONVEX OPTIMIZATION

Our algorithm is also applicable to the online optimization that deals with the optimization problems
having no or incomplete knowledge of the future (online). In the framework proposed in Zinkevich
and evaluate it on a previously unknown loss function(2003), at each step t, the goal is to predict the parameter ft. The nature of the sequence is unknown θt ∈F, where F ⊂ R[n] is a feasible set,
in advance, the SGEM algorithm needs to be modified. This can be done by replacing f (θt, ξt) by
_ft(θt) and taking gt = ∇ft(θt) in vt defined in (9), i.e.,_

_mt = βmt_ 1 + (1 _β)_ _ft(θt),_ (18a)
_−_ _−_ _∇_

_mt_
_vt =_ _._ (18b)

2(1 _β[t])_ _ft(θt) + c_
_−_

This algorithm is also unconditional energy stable as pointed out in Remark 4.1. For convergence,p
we evaluate our algorithm using the regret, that is the sum of all the previous difference between the
online prediction ft(θt) and the best fixed point parameter ft(θ[∗]) from a feasible set :
_F_



[ft(θt) _ft(θ[∗])],_
_−_
_t=1_

X


_R(T_ ) =


where θ[∗] = argminθ _Tt=1_ _[f][t][(][θ][)][. For convex objectives we have the following regret bound.]_
_∈F_

**Theorem 4.4. Let** _θt_ _be the solution sequence generated by SGEM with a fixed η > 0. Assume_
_{_ _}_ P
_Fthat and ∥x f −t are convex, SGEM achieves the following bound on the regret, for ally∥∞_ _≤_ _D∞_ _for all x, y ∈F, 0 < a ≤_ _ft(θt) + c ≤_ _B, and θt ∈F for all T ≥_ _t1, ∈_ [T ]. When

_n_ 1/2

1

_R(T_ ) _C_ _nT/η_ _,_ (19)
_≤_ _i=1_ _rT,i_ !
p X

_where C is a constant depending on β, B, D∞_ _and f1(θ1) + c._


-----

**Remark 4.4. (i) If rT,i > ri[∗]** _[>][ 0][, then][ R][(][T]_ [)][ is of order][ O][(]√T ), which is known the best possible

_bound for online convex optimization (Hazan, 2019, Section 3.2). Our experimental results show_
_that for η in a reasonable range, rT,i decays much slower than 1/√T (See Figure 1), for which the_

_convergence holds true in the sense that_

_R(T_ )
lim = 0.
_T →∞_ _T_

_(ii) The bound on θt is typically enforced by projection onto F (Zinkevich, 2003), with which the_
_regret bound (19) can still be proven since projection is a contraction operator (Hazan, 2019, Chap-_
_ter 3). As for the upper bound on the function value, just like we remarked for Theorem 4.2, it is_
_technically needed to bound mt._

5 NUMERICAL EXPERIMENTS

In this section, we compare the performance of the proposed method with several other methods, including AEGD, SGDM, AdaBelief (Zhuang et al., 2020), AdaBound (Luo et al., 2019), RAdam (Liu
et al., 2020a), Yogi (Zaheer et al., 2018), and Adam (Kingma & Ba, 2017), when applied to training deep neural networks. [1] We consider three convolutional neural network (CNN) architectures:
VGG-16 (Simonyan & Zisserman, 2015), ResNet-34 (He et al., 2016), DenseNet-121 (Huang et al.,
2017) on the CIFAR-10 and CIFAR-100 datasets (Krizhevsky & Hinton, 2009); we also conduct
experiments on the ImageNet dataset (Russakovsky et al., 2015) with the ResNet-18 architecture
(He et al., 2016).

For experiments on CIFAR-10 and CIFAR-100, we employ the fixed budget of 200 epochs and
reduce the learning rates by 10 after 150 epochs. The weight decay and minibatch size are set as
5 × 10[−][4] and 128 respectively. For the ImageNet tasks, we run 90 epochs and use similar learning
rate decaying strategy at the 30th and 60th epoch. The weight decay and minibatch size are set as
1 × 10[−][4] and 256 respectively.

In each task, we only tune the base learning rate and report the one that achieves the best final
generalization performance for each method:

-  SGEM: For CIFAR10 & 100 tasks, we use the default parameter η = 0.2; for the ImageNet
task, the learning rate is set as η = 0.3.

-  SGDM, AEGD: We search learning rate among {0.05, 0.1, 0.2}.

-  AdaBelief, AdaBound, Yogi, RAdam, Adam: We search learning rate among
0.0005, 0.001, 0.01, other hyperparameters such as β1, β2, ϵ are set as the default val_{_ _}_
ues in their literature.

From the experimental results of CIFAR10 & 100, we see that in all tasks, SGEM and AEGD
achieve higher test accuracy than the other methods while the oscillation of AEGD in test accuracy
is significantly reduced by SGEM as expected. We also observe that the differences between these
methods are more obvious in experiments on CIFAR-100.

For the ImageNet task, since all previous experiments show that SGDM gives the highest test accuracy, we focus on the comparison between SGDM and SGEM, and only run Adam as a representative of other adaptive methods. The results are presented in Figure 3. It can be seen that SGEM
still shows fast convergence and is able to achieve comparable test accuracy as SGDM in the end
of training. Here the highest test accuracy achieved by SGDM and SGEM are 69.89 and 69.92,
respectively.

6 CONCLUSION

In this paper, we propose SGEM, which integrates AEGD with momentum. We show that SGEM
still enjoys the unconditional energy stability property as AEGD, while the use of momentum helps
to reduce the variance of the stochastic gradient significantly, as verified in our experiments. We

[1Code is available at https://anonymous.4open.science/r/SGDEM-0042.](https://anonymous.4open.science/r/SGDEM-0042)


-----

(a) VGG-16 on CIFAR-10 (b) ResNet-34 on CIFAR-10 (c) DenseNet-121 on CIFAR-10

(d) VGG-16 on CIFAR-100 (e) ResNet-34 on CIFAR-100 (f) DenseNet-121 on CIFAR-100

Figure 2: Test accuracy for VGG-16, ResNet-34 and DenseNet-121 on CIFAR-10/100

Figure 3: Training loss and test accuracy for ResNet-18 on ImageNet

also provide convergence analysis in both online convex setting and the general stochastic nonconvex setting. Since our convergence results depend on the energy variable, a lower bound on the
energy is also presented. Finally, we empirically show that SGEM converges faster than AEGD and
generalizes better or at least as well as SGDM on several deep learning benchmarks.

Based on our observations in this paper, we list some problems for future work. First, we believe
there is a threshold for η[∗], such that rT either tends to a positive number or decays slower than
1/√T if η < η[∗]. A further theoretical investigation on this issue is desirable. Second, since rt is

strictly decreasing, there is a room to limit rt for controlling its decay whenever necessary. A proper
energy limiter should be obtained.

REFERENCES

Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal
_[of Machine Learning Research, 18(221):1–51, 2018. URL http://jmlr.org/papers/](http://jmlr.org/papers/v18/16-410.html)_
[v18/16-410.html.](http://jmlr.org/papers/v18/16-410.html)

Leon Bottou. _Stochastic Gradient Descent Tricks, volume 7700 of Lecture Notes in Com-_
_puter Science (LNCS)._ Springer, neural networks, tricks of the trade, reloaded edition, Jan

-----

[uary 2012. URL https://www.microsoft.com/en-us/research/publication/](https://www.microsoft.com/en-us/research/publication/stochastic-gradient-tricks/)
[stochastic-gradient-tricks/.](https://www.microsoft.com/en-us/research/publication/stochastic-gradient-tricks/)

L´eon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine
learning. SIAM Rev., 60(2):223–311, 2018.

Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of Adam-type
algorithms for non-convex optimization. In International Conference on Learning Representa_tions, 2019._

Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient
method with support for non-strongly convex composite objectives. In Advances in Neural In_[formation Processing Systems, volume 27, 2014. URL https://proceedings.neurips.](https://proceedings.neurips.cc/paper/2014/file/ede7e2b6d13a41ddf9f4bdef84fdc737-Paper.pdf)_
[cc/paper/2014/file/ede7e2b6d13a41ddf9f4bdef84fdc737-Paper.pdf.](https://proceedings.neurips.cc/paper/2014/file/ede7e2b6d13a41ddf9f4bdef84fdc737-Paper.pdf)

John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and
stochastic optimization. Journal of Machine Learning Research, 12:2121–2159, 2011.

[Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:](http://www.deeplearningbook.org)
[//www.deeplearningbook.org.](http://www.deeplearningbook.org)

Elad Hazan. Introduction to online convex optimization. arXiv, abs/1909.05207, 2019.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp.
770–778, 2016. doi: 10.1109/CVPR.2016.90.

Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q. Weinberger. Densely connected
convolutional networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition
_(CVPR), pp. 2261–2269, 2017. doi: 10.1109/CVPR.2017.243._

Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle
points faster than gradient descent. In Proceedings of the 31st Conference On Learning Theory,
volume 75, pp. 1042–1085, 2018.

Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, 2013. [URL https://proceedings.neurips.cc/paper/2013/file/](https://proceedings.neurips.cc/paper/2013/file/ac1dd209cbcc5e5d1c6e28598e8cbbe8-Paper.pdf)
[ac1dd209cbcc5e5d1c6e28598e8cbbe8-Paper.pdf.](https://proceedings.neurips.cc/paper/2013/file/ac1dd209cbcc5e5d1c6e28598e8cbbe8-Paper.pdf)

Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. _arXiv,_
abs/1412.6980, 2017.

Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Uni_versity of Toronto, 2009._

Yann LeCun, Y. Bengio, and Geoffrey Hinton. Deep learning. Nature, 521:436–44, 05 2015. doi:
10.1038/nature14539.

Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex finite-sum optimization via SCSG methods. In Advances in Neural Information Processing Systems, volume 30, 2017. [URL https://proceedings.neurips.cc/paper/2017/file/](https://proceedings.neurips.cc/paper/2017/file/81ca0262c82e712e50c580c032d99b60-Paper.pdf)
[81ca0262c82e712e50c580c032d99b60-Paper.pdf.](https://proceedings.neurips.cc/paper/2017/file/81ca0262c82e712e50c580c032d99b60-Paper.pdf)

Hailiang Liu and Xuping Tian. AEGD: Adaptive gradient decent with energy. _arXiv,_
abs/2010.05109, 2020.

Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Confer_[ence on Learning Representations, 2020a. URL https://openreview.net/forum?id=](https://openreview.net/forum?id=rkgz2aEKDr)_
[rkgz2aEKDr.](https://openreview.net/forum?id=rkgz2aEKDr)

Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with
momentum. In NeurIPS, 2020b.


-----

Liangchen Luo, Yuanhao Xiong, and Yan Liu. Adaptive gradient methods with dynamic bound of
learning rate. In International Conference on Learning Representations, 2019.

Stanley Osher, Bao Wang, Penghang Yin, Xiyang Luo, Farzin Barekat, Minh Pham, and Alex Lin.
Laplacian smoothing gradient descent. arXiv, abs/1806.06317, 2019.

B. T. Polyak. Some methods of speeding up the convergence of iterative methods. _Z. Vyˇ[ˇ]_ _cisl. Mat i_
_Mat. Fiz., 4:791–803, 1964. ISSN 0044-4669._

Ning Qian. On the momentum term in gradient descent learning algorithms. _Neural Net-_
_works, 12(1):145–151, 1999. ISSN 0893-6080. doi: https://doi.org/10.1016/S0893-6080(98)_
00116-6. URL [https://www.sciencedirect.com/science/article/pii/](https://www.sciencedirect.com/science/article/pii/S0893608098001166)
[S0893608098001166.](https://www.sciencedirect.com/science/article/pii/S0893608098001166)

Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In
_International Conference on Learning Representations, 2018._

Herbert Robbins and Sutton Monro. A stochastic approximation method. Ann. Math. Statistics,
[22:400–407, 1951. ISSN 0003-4851. doi: 10.1214/aoms/1177729586. URL https://doi.](https://doi.org/10.1214/aoms/1177729586)
[org/10.1214/aoms/1177729586.](https://doi.org/10.1214/aoms/1177729586)

Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng
Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.
ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision
_(IJCV), 115(3):211–252, 2015. doi: 10.1007/s11263-015-0816-y._

A. Shapiro and Y. Wardi. Convergence analysis of gradient descent stochastic algorithms. J. Optim.
_[Theory Appl., 91(2):439–454, 1996. ISSN 0022-3239. doi: 10.1007/BF02190104. URL https:](https://doi.org/10.1007/BF02190104)_
[//doi.org/10.1007/BF02190104.](https://doi.org/10.1007/BF02190104)

K. Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv, abs/1409.1556, 2015.

Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on
_Machine Learning, volume 28, pp. 1139–1147, 2013._

Tijmen Tieleman and Geoffrey Hinton. RMSprop: Divide the gradient by a running average of its
recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26–31, 2012.

Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The
marginal value of adaptive gradient methods in machine learning. arXiv, abs/1705.08292, 2018.

Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic momentum methods for deep learning. In Proceedings of the 27th International Joint Conference on
_Artificial Intelligence, pp. 2955–2961, 2018._

Xiaofeng Yang. Linear, first and second-order, unconditionally energy stable numerical schemes for
the phase field model of homopolymer blends. Journal of Computational Physics, 327:294–316,
2016.

Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In ICML, 2019.

Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive
methods for nonconvex optimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman,
N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems,
[volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/](https://proceedings.neurips.cc/paper/2018/file/90365351ccc7437a1309dc64e4db32a3-Paper.pdf)
[paper/2018/file/90365351ccc7437a1309dc64e4db32a3-Paper.pdf.](https://proceedings.neurips.cc/paper/2018/file/90365351ccc7437a1309dc64e4db32a3-Paper.pdf)

Jia Zhao, Qi Wang, and Xiaofeng Yang. Numerical approximations for a phase field dendritic crystal
growth model based on the invariant energy quadratization approach. International Journal for
_Numerical Methods in Engineering, 110:279–300, 2017._


-----

Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon
Papademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief
in observed gradients. In Advances in Neural Information Processing Systems, volume 33,
pp. 18795–18806, 2020. [URL https://proceedings.neurips.cc/paper/2020/](https://proceedings.neurips.cc/paper/2020/file/d9d4f495e875a2e075a1a4a6e1b9770f-Paper.pdf)
[file/d9d4f495e875a2e075a1a4a6e1b9770f-Paper.pdf.](https://proceedings.neurips.cc/paper/2020/file/d9d4f495e875a2e075a1a4a6e1b9770f-Paper.pdf)

Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In
_Proceedings of the Twentieth International Conference on International Conference on Machine_
_Learning, ICML, pp. 928–935, 2003._

Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of adam and rmsprop. 2019 IEEE/CVF Conference on Computer Vision and Pattern
_Recognition (CVPR), pp. 11119–11127, 2019._


-----

A APPENDIX

A.1 PROOF OF THEOREM 4.2

For the proofs of Theorem 4.2 and Theorem 4.3, we introduce notation


_f_ (θt; ξt) + c. (20)


_F˜t :=_


The initial data for ri is taken as r1,i = F[˜]1. We also denote the update rule presented in Algorithm
1 as
_θt+1 = θt −_ 2ηrt+1vt, (21)
where rt+1 is viewed as a n × n diagonal matrix that is made up of [rt+1,1, ..., rt+1,i, ..., rt+1,n].
**Lemma A.1. Under the assumptions in Theorem 4.2, we have for all t ∈** [T ],

_(i) ∥∇f_ (θt)∥∞ _≤_ _G∞._

_(ii) E[( F[˜]t)[2]] = F_ [2](θt) = f (θt) + c.

_(iii) E[ F[˜]t] ≤_ _F_ (θt). In particular, E[r1,i] = E[ F[˜]1] ≤ _F_ (θ1) for all i ∈ [n].

_(iv) σg[2]_ [=][ E][[][∥][g][t] _f_ [=][ E][[][|][f] [(][θ][t][;][ ξ][t][)][ −] _[f]_ [(][θ][t][)][|][2][]][ ≤] _[B][2][.]_

_[−∇][f]_ [(][θ][t][)][∥][2][]][ ≤] _[G]∞[2]_ _[and][ σ][2]_


_(v) E[|F_ (θt) − _F[˜]t|] ≤_


1

2[√]a _[σ][f]_ _[.]_


_(vi) E[∥∇F_ (θt) − 2 gF[˜]tt _[∥][2][]][ ≤]_ _[G]8a∞[2][3][ σ]f[2]_ [+][ 1]2a _[σ]g[2][.]_


_Proof. (i) By assumption ∥gt∥∞_ _≤_ _G∞, we have_

_f_ (θt) = E[gt] E[ _gt_ ] _G_ _._
_∥∇_ _∥∞_ _∥_ _∥∞_ _≤_ _∥_ _∥∞_ _≤_ _∞_

(ii) This follows from the unbiased sampling of

_f_ (θt) = Eξt [f (θt; ξt)].


(iii) By Jensen’s inequality, we have

E[ F[˜]t] ≤ E[ F[˜]t[2][] =] _F_ (θt)[2] = F (θt).
q

(iv) By assumptions ∥gt∥∞ _≤_ _G∞_ and f (θt; ξt) +p c < B, we have

_σg[2]_ [=][ E][[][∥][g][t] _[−∇][f]_ [(][θ][t][)][∥][2][] =][ E][[][∥][g][t][∥][2][]][ −∥∇][f] [(][θ][t][)][∥][2][ ≤] _[G]∞[2]_ _[,]_

_σf[2]_ [=][ E][[][∥][f] [(][θ][t][;][ ξ][t][)][ −] _[f]_ [(][θ][t][)][∥][2][] =][ E][[][∥][f] [(][θ][t][;][ ξ][t][)][∥][2][]][ −∥][f] [(][θ][t][)][∥][2][ ≤] _[B][2][.]_

(v) By the assumption 0 < a ≤ _f_ (θt; ξt) + c = F[˜]t[2][, we have]


_f_ (θt) _f_ (θt; ξt)
_−_

_F_ (θt) + F[˜]t


E[|F (θt) − _F[˜]t|] ≤_ E


1

2[√]a [E][[][|][f] [(][θ][t][)][ −] _[f]_ [(][θ][t][;][ ξ][t][)][|][]][ ≤]


2[√]a _[σ][f]_ _[.]_


(vi) By the definition of F (θ), we have

2

_f_ (θt)

_F_ (θt) = _∇_
_∥∇_ _−_ 2 [g]F[˜][t]t _∥[2]_ 2F (θt) 2 F[˜]t

_[−]_ _[g][t]_

2

_f_ (θt)( F[˜]t _F_ (θt))

= [1] _∇_ _−_ +

4 _F_ (θt) F[˜]t _[∇][f]_ [(][θ]F˜[t][)]t[ −] _[g][t]_

2

_f_ (θt)( F[˜]t _F_ (θt)) _f_ (θt) _gt_
_∇_ _−_ + [1] _∇_ _−_

_≤_ 2[1] _F_ (θt) F[˜]t 2 _F˜t_


_∞_ _Ft_ _F_ (θt) + [1]
_≤_ _[G]2a[2][2][ |][ ˜]_ _−_ _|[2]_ 2a _[∥∇][f]_ [(][θ][t][)][ −] _[g][t][∥][2][,]_


-----

where both the gradient bound and the assumption that 0 < a ≤ _f_ (θt; ξt) + c = F[˜]t[2] [are essentially]
used. Take an expectation to get

E[ _F_ (θt) ] _∞_ _Ft_ _F_ (θt) ] + [1]
_∥∇_ _−_ 2 [g]F[˜][t]t _∥[2]_ _≤_ _[G]2a[2][2][ E][[][|][ ˜]_ _−_ _|[2]_ 2a [E][[][∥∇][f] [(][θ][t][)][ −] _[g][t][∥][2][]][.]_


Similar to the proof for (iv), we have

E[ _F[˜]t_ _F_ (θt) ] _f_ _[.]_
_|_ _−_ _|[2]_ _≤_ 4[1]a _[σ][2]_

This together with the variance assumption for gt gives


E[ _F_ (θt) ] _∞_ _f_ [+ 1] _g[.]_
_∥∇_ _−_ 2 [g]F[˜][t]t _∥[2]_ _≤_ _[G]8a[2][3][ σ][2]_ 2a _[σ][2]_

**Lemma A.2. For any T ≥** 1, we have

_(i) E_ _Tt=1_ _[v]t[⊤][r][t][+1][v][t]_ _≤_ _[nF]2[ (]η[θ][1][)]_ _._

_(ii) Eh PTt=1_ _[m]t[⊤]_ 1[r][t][+1]i[m][t][−][1] E _Tt=1_ _[m]t[⊤][r][t][+1][m][t]_ _η_
_−_ _≤_ _≤_ [2][BnF][ (][θ][1][)]

_(iii) Eh PTt=1_ i _η_ h P. i

_(iv) Eh PTt=1_ _[∥][g]t[r][⊤][t][r][+1][t][+1][m][g][t][t][∥][2][i]≤≤[8](1[BnF][2]−[BnF]β[ (])[2][θ][ 2]η[1][(][)][θ][.][1][)]_

_(v) Eh Ph PTt=1_ _[∥][r][t][+1][g][t][∥][2]i[i]_ _≤_ [8][BnF](1−β[ 2])[(][2][θ]η[1][)] _[.]_

_Proof. From Algorithm 1 line 5, we have_
_rt,i −_ _rt+1,i = 2ηrt+1,ivt,i[2]_ _[.]_
Taking summation over t from 1 to T gives


_T_

_t=1_ _rt+1,ivt,i[2]_ _[≤]_ _[r]2[1]η [,i]_ _[.]_

X


_rt+1,ivt,i[2]_
_t=1_

X


_r1,i −_ _rT +1,i = 2η_

From which we get


_T_ _n_ _T_

_F1_

_vt[⊤][r][t][+1][v][t]_ [=] _rt+1,ivt,i[2]_
_t=1_ _i=1_ _t=1_ _[≤]_ _[n]2[ ˜]η [.]_

X X X

Taking expectation and using (iii) in Lemma A.1 gives (i).


Recall that mt = 2(1 − _β[t]) F[˜]tvt and_ _F[˜]t ≤_


_B, we further get_


_T_

_F1_
_vt[⊤][r][t][+1][v][t]_ [= 2][Bn][ ˜]

_η_

_t=1_

X


_m[⊤]t_ _[r][t][+1][m][t]_
_t=1_ _[≤]_ [4][B]

X

Using rt+1,i ≤ _rt,i and m0,i = 0, we also have_


_T −1_

_rt+1,im[2]t,i_
_t=1_ _[≤]_

X


_t=1_ _rt+1,im[2]t−1,i_ _[≤]_

X


_rt,im[2]t_ 1,i [=]
_−_
_t=1_

X


_rt+1,im[2]t,i[.]_ (22)
_t=1_

X


_i=1_


_i=1_


_i=1_


_i=1_


Connecting the above two inequalities and taking expectation gives (ii).

Using rt+1,i _r1,i, the above inequality further implies_
_≤_


_rt+1mt_ =
_∥_ _∥[2]_
_t=1_

X


_rt[2]+1,i[m][2]t,i_
_t=1_ _[≤]_

X


_r1,irt+1,im[2]t,i_

_i=1_ _t=1_

X X


_i=1_


_rt,im[2]t,i_
_t=1_

X


_F˜1 ≤_ 2BnF[˜]1[2][/η.]


_i=1_


-----

Taking expectation and using (ii) in Lemma A.1 gives (iii).

By mt = βmt 1 + (1 _β)gt, we have_
_−_ _−_


2

_β_

1 _β [m][t][−][1][,i]_
_−_ 


_gt[⊤][r][t][+1][g][t]_ [=]
_t=1_

X


_rt+1,igt,i[2]_ [=]
_t=1_

X


1 _β [m][t,i][ −]_
_−_


_rt+1,i_
_t=1_

X


_i=1_


_i=1_


_T_

2β[2]
_rt+1,im[2]t,i_ [+]

(1 _β)[2]_

_t=1_

_−_

X


_rt+1,im[2]t−1,i_
_t=1_

X


(1 − _β)[2]_


_i=1_


_i=1_


_T_

8BnF[˜]1
_m[⊤]t_ _[r][t][+1][m][t]_
_t=1_ _[≤]_ (1 _β)[2]η [.]_

_−_

X


_≤_ [2(1 +](1 _β[ β])[2][2][)]_

_−_


Here the third inequality is by (a + b)[2] _≤_ 2a[2] + 2b[2]; (22) and 0 < β < 1 are used in the fourth
inequality. Taking expectation and using (iii) in Lemma A.1 gives (iv).

Similar as the derivation for (ii), we have


_F˜1_ 8BnF[˜]1[2]
_≤_ (1 _β)[2]η [.]_

_−_


_rt+1gt_
_∥_ _∥[2]_ _≤_
_t=1_

X


_rt,igt,i[2]_
_t=1_

X


_i=1_


Taking expectation and using (ii) in Lemma A.1 gives (v).

We are now ready to prove Theorem 4.2. The upper bound on σg is given by (iv) in Lemma A.1.
Since f is L-smooth, we have

_f_ (θt+1) _f_ (θt) + _f_ (θt)[⊤](θt+1 _θt) +_ _[L]_ (23)
_≤_ _∇_ _−_ 2 _[∥][θ][t][+1][ −]_ _[θ][t][∥][2][.]_

Denoting ηt = η/F[˜]t, the second term in the RHS of (23) can be expressed as

_f_ (θt)[⊤](θt+1 _θt)_
_∇_ _−_

= _f_ (θt)[⊤]( 2ηrt+1vt)
_∇_ _−_


1
= (since mt = 2(1 _β[t]) F[˜]tvt)_
_−_ 1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][r][t][+1][m][t] _−_

_−_

1
= (24)
_−_ 1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][r][t][+1][(][βm][t][−][1][ + (1][ −] _[β][)][g][t][)]_

_−_

_β_

=
_−_ 1[1][ −]β[β][t][ ∇][f] [(][θ][t][)][⊤][η][t][r][t][+1][g][t][ −] 1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][r][t][+1][m][t][−][1]

_−_ _−_

=
_−_ 1[1][ −]β[β][t][ ∇][f] [(][θ][t][)][⊤][η][t][−][1][r][t][g][t][ + 1]1 _[ −]β[β][t][ ∇][f]_ [(][θ][t][)][⊤][(][η][t][−][1][r][t][ −] _[η][t][r][t][+1][)][g][t]_

_−_ _−_

_β_
_−_ 1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][r][t][+1][m][t][−][1][.]

_−_

We further bound the second term and third term in the RHS of (24), respectively. For the second
term, we note that | 1[1]−[−]β[β][t][ | ≤] [1][ and]

_|∇f_ (θt)[⊤](ηt−1rt − _ηtrt+1)gt|_

= _f_ (θt)[⊤]ηt 1(rt _rt+1)gt +_ _f_ (θt)[⊤](ηt 1 _ηt)rt+1gt_
_|∇_ _−_ _−_ _∇_ _−_ _−_ _|_

= |∇f (θt)[⊤]ηt−1(rt − _rt+1)gt + (ηt−1 −_ _ηt)gt[⊤][r][t][+1][g][t]_
+ (ηt−1 − _ηt)(∇f_ (θt) − _gt)[⊤]rt+1gt|_

_≤∥∇f_ (θt)∥∞|ηt−1|∥rt − _rt+1∥1,1∥gt∥∞_ + |ηt−1 − _ηt|gt[⊤][r][t][+1][g][t]_
+ |ηt−1 − _ηt||(∇f_ (θt) − _gt)[⊤]rt+1gt|_

_≤_ (ηG[2]∞[/][√][a][)(][∥][r][t][∥][1][,][1] _[−∥][r][t][+1][∥][1][,][1][) + (2][η/][√][a][)][g]t[⊤][r][t][+1][g][t]_
+ (2η/[√]a) ( _f_ (θt) _gt)[⊤]rt+1gt_ _._ (25)
_|_ _∇_ _−_ _|_


-----

The third inequality holds because for a positive diagonal matrix A, x[⊤]Ay ≤∥x∥∞∥A∥1,1∥y∥∞,
where ∥A∥1,1 = _i_ _[a][ii][. The last inequality follows from the result][ r][t][+1][,i][ ≤]_ _[r][t,i][ for][ i][ ∈]_ [[][n][]][, the]

assumption ∥gt∥∞ _≤_ _G∞,_ _F[˜]t ≥_ _[√]a, and (i) in Lemma (A.1)._

[P]

For the third term in the RHS of (24), we note that


_β_ _βη_

1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][r][t][+1][m][t][−][1][ ≤] (1 _β)[√]a_ _[|∇][f]_ [(][θ][t][)][⊤][η][t][r][t][+1][m][t][−][1][|][,]
_−_ _−_


in which


_|∇f_ (θt)[⊤]rt+1mt−1|

= _gt[⊤][r][t][+1][m][t][−][1]_ [+ (][∇][f] [(][θ][t][)][ −] _[g][t][)][⊤][r][t][+1][m][t][−][1][|]_
_|_

_≤_ 2[1] _[g]t[⊤][r][t][+1][g][t]_ [+ 1]2 _[m]t[⊤]−1[r][t][+1][m][t][−][1]_ [+][ |][(][∇][f] [(][θ][t][)][ −] _[g][t][)][⊤][r][t][+1][m][t][−][1][|][,]_ (26)

where the last inequality is because for a positive diagonal matrix A, x[⊤]Ay ≤ 2[1] _[x][⊤][Ax][ +][ 1]2_ _[y][⊤][Ay][.]_

Substituting (25) and (26) into (24), we get


_f_ (θt)[⊤](θt+1 _θt)_ _∞_ _rt_ 1,1 _rt+1_ 1,1)
_∇_ _−_ _≤−_ 1[1][ −]β[β][t][ ∇][f] [(][θ][t][)][⊤][η][t][−][1][r][t][g][t][ +][ ηG]√a[2] (∥ _∥_ _−∥_ _∥_

_−_

2η _βη_ _βη_
+ _√a +_ 2(1 _β)[√]a_ _gt[⊤][r][t][+1][g][t]_ [+] 2(1 _β)[√]a_ _[m]t[⊤]−1[r][t][+1][m][t][−][1]_
 _−_  _−_

+ [2][η] ( _f_ (θt) _gt)[⊤]rt+1gt_ + _βη_
_√a_ _|_ _∇_ _−_ _|_ (1 _β)[√]a_ _[|][(][∇][f]_ [(][θ][t][)][ −] _[g][t][)][⊤][r][t][+1][m][t][−][1][|][.]_

_−_

With (27), we take an conditional expectation on (23) with respect to (θ) and rearrange to get

1 − _β_ 1 − _β_

1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][−][1][r][t][∇][f] [(][θ][t][) =][ E][ξ][t] 1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][−][1][r][t][g][t]
_−_  _−_ 

_≤_ Eξt "f (θt) − _f_ (θt+1) + _[ηG]√a∞[2] (∥rt∥1,1 −∥rt+1∥1,1)_

2η _βη_ _βη_
+ _√a +_ 2(1 _β)[√]a_ _gt[⊤][r][t][+1][g][t]_ [+] 2(1 _β)[√]a_ _[m]t[⊤]−1[r][t][+1][m][t][−][1]_
 _−_  _−_

+ [2][η] ( _f_ (θt) _gt)[⊤]rt+1gt_
_√a_ _|_ _∇_ _−_ _|_


(27)

(28)


_βη_
+ _,_

(1 _β)[√]a_ _[|][(][∇][f]_ [(][θ][t][)][ −] _[g][t][)][⊤][r][t][+1][m][t][−][1][|][ +][ L]2_

#

_−_ _[∥][θ][t][+1][ −]_ _[θ][t][∥][2]_

where the assumption Eξt [gt] = ∇f (θt) is used in the first equality. Since ξ1, ..., ξt are independent
random variables, we set E = Eξ1 Eξ2 _...EξT and take a summation on (28) over t from 1 to T to get_


_T_

E 1 − _β_

1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][−][1][r][t][∇][f] [(][θ][t][)]

" _t=1_ #

_−_

X

_≤_ E _f_ (θ1) − _f_ (θT +1) + _[ηG]√a∞[2] E_ _∥r1∥1,1 −∥rT +1∥1,1_
h i _T_ h i

2η _βη_ _βη_
+ E _gt[⊤][r][t][+1][g][t]_ +
_√a +_ 2(1 _β)[√]a_ 2(1 _β)[√]a_ [E]
 _−_  " _t=1_ # _−_

X


_m[⊤]t−1[r][t][m][t][−][1]_
_t=1_

X


(29)


+ √[2][η]a E


( _f_ (θt) _gt)[⊤]rt+1gt_
_|_ _∇_ _−_ _|_
_t=1_

X


_βη_

(1 _β)[√]a_ [E]
_−_


+ _[L]_

2 [E]


_|(∇f_ (θt) − _gt)[⊤]rt+1mt−1|_
_t=1_

X


_θt+1_ _θt_
_t=1_ _∥_ _−_ _∥[2]_

X


-----

Below we bound each term in (29) separately. By the Cauchy-Schwarz inequality, we get

_T_

E ( _f_ (θt) _gt)[⊤]rt+1mt_ 1

" _t=1_ _|_ _∇_ _−_ _−_ _|#_
X

_T_

E _f_ (θt) _gt_ _rt+1mt_ 1
_≤_ " _t=1_ _∥∇_ _−_ _∥∥_ _−_ _∥#_

X

_T_ 1/2 _T_ 1/2[#]

E _f_ (θt) _gt_ _rt+1mt_ 1
_≤_ _∥∇_ _−_ _∥[2]_ _∥_ _−_ _∥[2]_

" _t=1_   _t=1_ 
X X

_T_ 1/2 _T_ 1/2

E _f_ (θt) _gt_ E _rt+1mt_ 1

_≤_ " _t=1_ _∥∇_ _−_ _∥[2]#!_ " _t=1_ _∥_ _−_ _∥[2]#!_

X X


2BnT/ηF (θ1)σg, (30)

_≤_
p

where Lemma A.1 (ii) and the bounded variance assumption were used. We replace mt 1 in (30)
_−_
by gt and use Lemma A.1 (v) to get


( _f_ (θt) _gt)[⊤]rt+1gt_
_t=1_ _|_ _∇_ _−_ _|#_

X

_T_ 1/2

E" _t=1_ _∥∇f_ (θt) − _gt∥[2]#!_

X


_T_ 1/2

_rt+1gt_
_t=1_ _∥_ _∥[2]#!_

X


_≤_ [2]


2BnT/ηF (θ1)σg

_._ (31)
1 − _β_


By (12), the last term in (29) is bounded above by


_∞_

_θt+1_ _θt_

"t=0 _∥_ _−_ _∥[2]_
X


(32)

_≤_ _[Lηn]2_ _[F][ 2][(][θ][1][)][.]_


_L_

2 [E]


Substituting Lemma A.1 (i) (iii), (32), (31), (30) into (29) to get


1 _β_
_−_ (f (θ1) _f_ ) + _[ηG]∞[2]_ (θ1)

1 _β[t][ ∇][f]_ [(][θ][t][)][⊤][η][t][−][1][r][t][∇][f] [(][θ][t][)]# _≤_ _−_ _[∗]_ _√a nF_
_−_

2 _β_ 8BnF (θ1)
+ + _[βBnF]_ [(][θ][1][)]
_√a +_ 2(1 _β)[√]a_ (1 _β)[2]_ (1 _β)[√]a_
 _−_  _−_ _−_

+ [(4 +][ β][)][√][2][Bη] _√nTσg +_ _[Lηn]_

(1 _β)[√]a [F]_ [(][θ][1][)] 2 _[F][ 2][(][θ][1][)][.]_
_−_


_t=1_


(33)


Note that the left hand side is bounded from below by


(1 _β)_ _[η]_
_−_ _√_


min _rT,i_ _f_ (θt)
_i_ _∥∇_ _∥[2]_

_t=1_

X


where we used | 1[1]−[−]β[β][t][ | ≥] [1][ −] _[β][ and][ η][t][ ≥]_ _[η/]_


_B. Thus we have_


_≤_ _[C][1][ +][ C][2][n][ +]η[ C][3][σ][g]_


_nT_


_f_ (θt)
_∥∇_ _∥[2]_
_t=1_

X


min _rT,i_


-----

where


_√B_
_C1 = [(][f]_ [(][θ][1][)][ −] _[f][ ∗][)]_ _,_

1 − _β_

_√BηG[2]_ 2 _β_

_C2 =_ (1 _∞β)[F][√][(]a[θ][1][)]_ + _√a +_ 2(1 _β)[√]a_

_−_  _−_

_√BLη_

+ _[βB][3][/][2][F]_ [(][θ][1][)]

(1 _β)[2][√]a_ [+] 2(1 _β)[2][ F][ 2][(][θ][1][)][,]_
_−_ _−_

_C3 = [(4 +][ β][)][B][√][2][η]_

(1 _β)[√]a [F]_ [(][θ][1][)][.]
_−_

A.2 PROOF OF THEOREM 4.3


8B3/2F (θ1)

(1 _β)[3]_

 _−_


First note that by (iv) in Lemma A.1, max{σg, σf _} ≤_ max{G∞, B}.
Recall that F (θ) = _f_ (θ) + c, then for any x, y ∈{θt}t[T]=0 [we have]
p

_f_ (x)
_F_ (x) _F_ (y) = _∇_
_∥∇_ _−∇_ _∥_ 2F (x) 2F (y)

_[−∇][f]_ [(][y][)]

= [1] _∇f_ (x)(F (y) − _F_ (x)) +

2 _F_ (x)F (y) _[∇][f]_ [(][x]F[)][ −∇](y) _[f]_ [(][y][)]


_G_
_∞_

2(F (θ[∗]))[2][ |][F] [(][y][)][ −] _[F]_ [(][x][)][|][ +]


2F (θ[∗]) _[∥∇][f]_ [(][x][)][ −∇][f] [(][y][)][∥][.]


One may check that


_G_
_F_ (y) _F_ (x) _∞_
_|_ _−_ _| ≤_ 2F (θ[∗]) _[∥][x][ −]_ _[y][∥][.]_

These together with the L-smoothness of f lead to

_F_ (x) _F_ (y) _LF_ _x_ _y_ _,_
_∥∇_ _−∇_ _∥≤_ _∥_ _−_ _∥_

where


_G[2]_
_L +_ _∞_

2(f (θ[∗]) + c)


_LF =_


_f_ (θ[∗]) + c


This confirms the LF -smoothness of F, which yields

_F_ (θt+1) _F_ (θt) _F_ (θt)[⊤](θt+1 _θt) +_ _[L][F]_
_−_ _≤∇_ _−_ 2 _[∥][θ][t][+1][ −]_ _[θ][t][∥][2]_

= ( _F_ (θt) )[⊤](θt+1 _θt) + (_ _[g][t]_
_∇_ _−_ 2 [g]F[˜][t]t _−_ 2 F[˜]t _−_ [1]1[ −] _[β]β [t]_ _[v][t][)][⊤][(][θ][t][+1][ −]_ _[θ][t][)]_

_−_

+ ( [1][ −] _[β][t]_

1 − _β [v][t][)][⊤][(][θ][t][+1][ −]_ _[θ][t][) +][ L]2[F]_ _[∥][θ][t][+1][ −]_ _[θ][t][∥][2][.]_


Summation of the above over t from 1 to T and taken with the expectation gives


E[F (θT +1) − _F_ (θ1)] ≤


_Si,_ (34)
_i=1_

X


-----

where


_T_

1 − _β[t]_ _t_ [(][θ][t][+1]

_t=1_ 1 _β [v][⊤]_ _[−]_ _[θ][t][)]_

_−_

X


_S1 = E_

_S2 = E_

_S3 = E_

_S4 = E_


_T_

( _[g][t]_
_t=1_ 2 F[˜]t _−_ [1]1[ −] _[β]β [t]_ _[v][t][)][⊤][(][θ][t][+1][ −]_ _[θ][t][)]_

_−_

X

_T_

( _F_ (θt) )[⊤](θt+1 _θt)_
_t=1_ _∇_ _−_ 2 [g]F[˜][t]t _−_ #

X


_T_

_LF_

2

_t=1_

_[∥][θ][t][+1][ −]_ _[θ][t][∥][2]_

X


Below we bound S1, S2, S3, S4 separately. To bound S1, we first note that

_rt+1,i_ _rt,i =_ 2ηrt+1,ivt,i[2] [=][ v][t,i][(][−][2][ηr][t][+1][,i][v][t,i][) =][ v][t,i][(][θ][t][+1][,i]
_−_ _−_ _[−]_ _[θ][i][)]_

from which we get


1 − _β[t]_ _t_ [(][θ][t][+1]

1 _β [v][⊤]_ _[−]_ _[θ][t][)]_
_−_


_S1 = E_

= E

_≤_ E


_t=1_

_n_

_i=1_

X

_n_

_i=1_

X


1 − _β[t]_

1 _β_ [(][r][t][+1][,i][ −] _[r][t,i][)]_
_−_


_t=1_


(Since rt+1,i _rt,i)_
_≤_


_rt+1,i_ _rt,i_
_t=1_ _−_

X


= E[rT +1,i] − _nE[ F[˜]1]._

_i=1_

X

_T_

( _[g][t]_
_t=1_ 2 F[˜]t _−_ [1]1[ −] _[β]β [t]_ _[v][t][)][⊤][(][θ][t][+1][ −]_ _[θ][t][)]_

_−_

X


For S2, we have

_S2 = E_

= E


_T_

_t=1(−_ 2 [1]F[˜]t

X


_β_

E (

" _i=1_ _t=1_ _−_ 2 [1]F[˜]t 1 − _β [m][t][−][1][,i][)][⊤][(2][ηr][t][+1][,i][v][t,i][)]_
X X

_n_ _T_

_βη_

(1 _β)[√]a_ [E] _rt+1,imt−1,ivt,i_
_−_ " _i=1_ _t=1_ #

X X

_n_ _T_ 1/2 _n_

_βη_

(1 _β)[√]a_ [E] _rt+1,im[2]t−1,i_
_−_ " _i=1_ _t=1_   _i=1_

X X X


_T_ 1/2[#]

_rt+1,ivt,i[2]_
_t=1_ 

X


_√BnF_ (θ1)
_≤_ _[β](1_ _β)[√]a [,]_

_−_

where the fourth inequality is by the Cauchy-Schwarz inequality, the last inequality is by Lemma
A.1 (i) (ii).


-----

For S3, by the Cauchy-Schwarz inequality, we have


_T_

_S3 = E"_ _t=1(∇F_ (θt) − 2 [g]F[˜][t]t )[⊤](θt+1 − _θt)#_

X

_T_

_≤_ E" _t=1_ _∥∇F_ (θt) − 2 [g]F[˜][t]t )∥∥θt+1 − _θt)∥#_

X

_T_ 1/2 _T_ 1/2[#]

_≤_ E" _t=1_ _∥∇F_ (θt) − 2 [g]F[˜][t]t )∥[2]  _t=1_ _∥θt+1 −_ _θt∥[2]_

X X

_T_ 1/2 _T_ 1/2

_≤_ E" _t=1_ _∥∇F_ (θt) − 2 [g]F[˜][t]t )∥[2]#! E" _t=1_ _∥θt+1 −_ _θt∥[2]#!_

X X


_G[2]_
_∞_ _f_ [+ 1] _g[,]_

8a[3][ σ][2] 2a _[σ][2]_


_F_ (θ1)
_≤_


_ηnT_


where the last inequality is by (vi) in Lemma A.1 and (12) in Theorem 4.1.

For S4, also by (12) in Theorem 4.1, we have


_≤_ _[L][F][ ηnF]2_ [ 2][(][θ][1][)]


_S4 =_ _[L][F]_

2 [E]


_θt+1_ _θt_
_t=1_ _∥_ _−_ _∥[2]_

X


With the above bounds on S1, S2, S3, S4, (34) can be rearranged as


_G[2]_
_∞_ _f_ [+ 1] _g_

4a[3][ σ][2] _a_ _[σ][2]_ _[−]_ _[L][F][ ηnF]2_ [ 2][(][θ][1][)]


_√BnF_ (θ1)
_F_ (θ[∗])
_−_ _[β](1_ _β)[√]a_

_n_ _−_ _[−]_ _[F]_ [(][θ][1][)]


_ηnT_


_≤_ E[rT +1,i] − _nE[ F[˜]1] + F_ (θ1)

_i=1_

X

min E[rT +1,i] + (n 1)E[ F[˜]1] (n 1)E[ F[˜]1] + _F_ (θ1) E[ F[˜]1]
_≤_ _i_ _−_ _−_ _−_ _−_
  

min E[rT +1,i] + E[ _F_ (θ1) _F1_ ]
_≤_ _i_ _|_ _−_ [˜] _|_


min E[rT +1,i] +
_≤_ _i_


2[√]a _[σ][f]_ _[,]_


where (iii) in Lemma A.1 was used. Hence,

min E[rT,i] max _F_ (θ[∗]) _ηD1_ _βD2_ _σD3, 0_ _,_
_i_ _≥_ _{_ _−_ _−_ _−_ _}_

where σ = max _σf_ _, σg_ and
_{_ _}_


_D1 =_ _[L][F][ nF][ 2][(][θ][1][)]_


_√BnF_ (θ1)

(1 _β)[√]a [,]_
_−_

_G[2]_
_∞_

4a[3][ + 1]a _[.]_


_D2 =_

_ηnT_


2[√]a [+][ F] [(][θ][1][)]


_D3 =_

A.3 PROOF OF THEOREM 4.4


Using the same argument as for (iv) in Lemma A.2, we have


_T_

_f1(θ1) + c_

_t=1_ _rt+1,igt,i[2]_ _[≤]_ [8][Bn](1p − _β)[2]η_

X


_i=1_


-----

With this estimate and the convexity of ft, the regret can be bounded by


_ft(θt)_ _ft(θ[∗])_
_−_ _≤_
_t=1_

X


_gt[⊤][(][θ][t]_
_t=1_ _[−]_ _[θ][∗][)]_

X


_R(T_ ) =


_n_ _T_

_gt,i_ _rt+1,i_ _|θt,i −_ _θi[∗][|]_

_i=1_ _t=1_ _|_ _|[√]_ _√rt+1,i_

X X

1/2

_n_ _T_ _n_ _T_

_rt+1,igt,i[2]_

_i=1_ _t=1_ ! _i=1_ _t=1_

X X X X


1/2

_θi[∗]_

_[|][2]_

_,i_ !

1/2

1

_rT +1,i_ !


_θt,i_ _θi[∗]_
_|_ _−_ _[|][2]_

_rt+1,i_


_n_ 1/2

_√2B_ 1

(f1(θ1) + c)[1][/][4][p]nT/η _,_

_≤_ [2][D]1[∞] − _β_ _i=1_ _rT +1,i_ !

X

where the fourth inequality is by the Cauchy-Schwarz inequality, and the assumption _x_ _y_
_∥_ _−_ _∥∞_ _≤_
_D_ for all x, y is used in the last inequality.
_∞_ _∈F_


-----

