On the Convergence of mSGD and AdaGrad for Stochastic Optimization
Authors: ruinan Jin
Yu Xing
Xingkang He
Venue: ICLR 2022 Poster (2022)
Keywords: stochastic gradient descent
adaptive gradient algorithm
asymptotic convergence

Abstract: As one of the most fundamental stochastic optimization algorithms, stochastic gradient descent (SGD) has been intensively developed and extensively applied in machine learning in the past decade. There have been some modified SGD-type algorithms, which outperform the SGD in many competitions and applications in terms of convergence rate and accuracy, such as momentum-based SGD (mSGD) and adaptive gradient algorithm (AdaGrad). Despite these empirical successes, the theoretical properties of these algorithms have not been well established due to technical difficulties. With this motivation, we focus on convergence analysis of mSGD and AdaGrad for any smooth (possibly non-convex) loss functions in stochastic optimization. First, we prove that the iterates of mSGD are asymptotically convergent to a connected set of stationary points with probability one, which is more general than existing works on subsequence convergence or convergence of time averages. Moreover, we prove that the loss function of mSGD decays at a certain rate faster than that of SGD. In addition, we prove the iterates of AdaGrad are asymptotically convergent to a connected set of stationary points with probability one. Also, this result extends the results from the literature on subsequence convergence and the convergence of time averages. Despite the generality of the above convergence results, we have relaxed some assumptions of gradient noises, convexity of loss functions, as well as boundedness of iterates.

Published as a conference paper at ICLR 2022
ON THE CONVERGENCE OF MSGD AND ADAGRAD FOR STOCHASTIC OPTIMIZATION
Ruinan Jin
LSC, NCMIS, Academy of Mathematics and Systems Science Chinese Academy of Sciences, Beijing 100190, China
School Mathematical Sciences University of Chinese Academy of Sciences, Beijing 100049, China
Yu Xing
Division of Decision and Control Systems KTH Royal Institute of Technology SE-100 44 Stockholm, Sweden
Xingkang He
Department of Electrical Engineering University of Notre Dame, IN, USA
ABSTRACT
As one of the most fundamental stochastic optimization algorithms, stochastic gradient descent (SGD) has been intensively developed and extensively applied in machine learning in the past decade. There have been some modified SGD-type algorithms,, which outperform the SGD in many competitions and applications in terms convergence rate and accuracy, such as momentum-bart and adaptive gradient algorithm (AdaGrad). Despite these empirical successes, the theoretical properties of these algorithms have not been well established due technical difficulties. With this motivation, focus on convergence analysis of mSGD and AdaGrad for any smooth (possibly non-convex) loss functions in stochastic optimization. First, we prove that the iterates of mSGD are asymp- totically convergent to a connected set of stationary points with probability one, which is more general than existing works on subsequence convergence or con- vergence of time averages. Moreover, we prove that the loss function of mSGD decays at certain rate faster than that of SGD. addition, we prove the iterates of AdaGrad are asymptotically convergent to connected set of stationary points with probability one. Also, this result extends the results from the literature on subsequence convergence and the convergence of time averages. Despite the gen- erality of the above convergence results, we have relaxed some assumptions gradient noises, convexity of loss functions, well boundedness of iterates.
SGD (mSGD)
INTRODUCTION
In recent years, the rapid development of machine learning has stimulated lot of applications of op- timization algorithms to employing tremendous data in practical scenarios. Many optimization algo- rithms of machine learning are based on gradient descent (GD). A typical GD algorithm, minimizing a loss function s(0) IR via seeking an N-dimensional real-valued parameter 6" arg min g(0), B
writes follows
0 0, E, Ve,g(
where 0, the estimate of 0* at step n, En positive step size (learning rate) be designed, and V Va,g (0,) stands for the gradient of g( (2)) at step n. When certain conditions are satisfied, 6, in
*Corresponding author: xhe9 @nd.edu

---

Published as a conference paper at ICLR 2022
equation wwill converge to the optimal solution. However, since the computation of (g,)(,,) relies on all data at each step, is inefficient to apply GD-based algorithms (c.g., equation I when the data amount is very large. Therefore, more and more attention has been given how accelerate the GD-bbsed algorithms. One of the attempts is stochastic gradient descent (SGD) which originated from Robbins & Monro (1951). Instead of calculating Ve,g (p)) over all data, SGD algorithms use a relatively small proportion of data to estimate the gradient, i.e., Ve,g G, 5n) where 5n is a random vector introduced to choose a subset of data for each update. Then the SGD modified from GD equation D is as follows
0,+1 02 E, V V ( Sn.
(2)
Besides reducing gradient computation, g (e. 5m) can be used as an estimate of the gradient for the scenarios where the accurate gradient is unavailable due to external noises.
In recent years, SGD has shown its prominent advantages in dealing with high dimensional optimiza- tion problems such as regularized empirical risk minimization and training deep neural networks (see, c.g. Graves et al. (2013); ; Nguyen et al. (2018); Hinton & &alakhutdinov (2006); Krizhevsky (ct al. (2012) and references therein). In Nguyen et al. (2018): Bottou (2012), the convergence and the convergence rate of SGD have been analyzed.
Despite outstanding successes of SGD, it usually has a relatively slow convergence rate induced by random gradients and it provides fluctuating iterates in the learning process. In order to improve the theoretical and empirical performance of SGD, there have been a number of investigations, in- cluding three typical algorithms for accelerating the convergence rate: (1) The momentum-based stochastic gradient descend (mSGD), which reduces the update variance by averaging the past gra- dients (Polyak) 1964): (2) The adaptive gradient algorithm (AdaGrad), which replaces the step size of SGD with adaptive step size (Duchi et al. 201T); (3) Adaptive momentum gradient algorithm (Adam), which integrates mSGD and AdaGrad (Kingma& Ba 2013). However, the convergence results of these algorithms have not been well established, especially for non-convex loss functions. In this paper, we focus on the investigation of mSGD and AdaGrad, We believe that the convergence analysis results in this paper are helpful for the future research on the convergence or generalization of Adam and other stochastic optimization algorithms.
The technique of mSGD is originally developed by Polyak (Polyak 1964) for the acceleration of convergence rate of gradient-baact based methods. A typical expression of mSGD is as follows (Zarebal
ct al. 2015 Sutskever et al. 2013)
Vn 0V + En V e (0,, 5.).
0,+1 0, Vn-
where & E [0, and e, > 0 are relatively momentum coefficient and step size (leamnng rate), respec- tively. Another type of mSGD with the name of stochastic heavy ball (SHB) has also been studied Gitman et al. 2019 Gupal & Bazhenov 1972),
Vn Ba + (1 e, 0,+1 0, Va
where B, E (0. 1) and Y, are relatively momentum coefficient and step size (learning rate). In recent years, mSGD has been widely employed in the applications of deep learning such image classifi- cation (Krizhevsky et al.) (012), fault diagnosis (Tang et al., 2018). statistical image reconstruction (Kim al. 2014), etc. Moreover, a number of variants on momentum are emerging, see, e.g.. synthesized Nesterov variants (SNV) (Williams & Lovett 2016), robust momentum (Cyrus et al.) 2018). and PID-control based methods (An et al.] (2018). The importance of momentum in deep learning has been illustrated in [Sutskever et al. (2013) through experiments. However, the theoreti- cal analysis for convergence and convergence rate of mSGD needs further investigation, especially for non-convex loss functions which are common in deep learning. Most existing results are estab- lished with guaranteed subsequence convergence or convergence of time averages (see Yang et al. 2016);; Gitman et al. (2019); Polyak (1977); Kaniovskii (1983), Li & Orabona (2020) and refer- ences therein). Nevertheless, there is a still distance to asymptotic convergence, which is usually more general and useful in practical applications requiring stable iterates for each realization. Seb- bouh et al.] (2020) studied the asymptotic convergence of mSGD with time-varying parameter On, which however is less common than the static in practical applications.
Convergence analysis for SGD unveils that the convergence rate heavily depends on the choice of step size e, (Robbins& & Monro 1951 Nguyen al. 2018), which may consume huge amount
1 The convergence definitions are given in Section 3.
2

---

Published as a conference paper at ICLR 2022
of efforts fine tune. In order to deal with this problem. the algorithm AdaGrad with adaptive step size is proposed in Duchi et al. (2010) and McMahan Streeter (2010) concurrently. In the literature, there are two main forms of AdaGrad. One is based on the norm of gradients follows (Stretter & Mcmahan 2010)
Sn S + V (G, (n.nl)) 0,+1 0,
do
Ve,8 On $n);
(5)
VSn
where Ogy is constant. The other form is based on the coordinate-win gradients (Duchi al. 2020)
2010 Li & Orabona 2019
Qn 2n-1 V 0, (0,, 5n) Ve,
Ve, e, Oz. Sn), 0.+1 0, Ve, 0, On, 5n):
where Ug is constant. In our paper we focus on the norm form (equation 5). In recent years, AdaGrad has shown its effectiveness in the field of sparse optimization (Duchi et al. 2013). tensor factorization (Lacroix et al. 20188) and deep learning (Heaton & Jeff 2018). Some algorithm vari- ants like RMSProp (Tieleman & Hinton 2012) and SAdaGrad (Chen et al., 2018 are also studied. However, there few results on the convergence of AdaGrad. Most of these results only prove subsequence convergence or convergence
time averages (see, c.g. Zou et al. (2019); Chen et al. (219); Défossez et al. (2020); Ward et al. (2019)) Although [i & Orabonal (2019) and Gadat & Gavra 2020) studied the asymptotic convergence of a modified AdaGrad algorithm, the result not applicable to AdaGrad in equation 5 Thus, the asymptotic convergence of AdaGrad in equation 5
is still open.
In this theoretical paper, aim establish the convergence of mSGD and AdaGrad under mild conditions. The main contributions of this paper are three-fold:
We prove that the iterates of mSGD are asymptotically convergent to a connected set of stationary points for possibly non-convex loss function almost surely (i.c., with probability one), which is more general than existing works on subsequence convergence.
We quantify the convergence rate of mSGD for the loss functions. Through this conver- gence rate we can get theoretical explanation of why mSGD can be seen as an acceleration SGD. Moreover, we provide the convergence rate of mean-square gradients and connect it to the convergence of time averages.
We prove the iterates of AdaGrad are asymptotically convergent to connected set of sta- tionary points almost surely for possible con-conex loss functions. The convergence result for the AdaGrad extends the subsequence convergence in the literature.
The remainder of the paper is organized as follows. In Section 2, we introduce the related work considering the convergence of mSGI) and AdaGrad. The main results of the paper are given in Section 3, where we study the convergence and convergence rate of mSGD as well as the conver- gence of AdaGrad. Section 4 concludes the whole paper. Sections and 6 are Code of Ethics and Reproducibility, respectively. The proofs are given in Appendix.
2 RELATED WORK
Convergence of mSGD: For the normalized mSGD (SHB). Polyak (Polyak 1977
1964) and Kan-
iovski (Kaniovskil 1983) studied its convergence (subsequence convergence and convergence of time averages) properties for convex loss functions. Igor Gitman (Gitman et al. 2019) provided some convergence results of mSGD (SHB) for non-convex loss functions, but there is considerable distance to the asymptotic convergence. Moreover, there is a requirement for uniform boundedness of a noise term in Gitman et (2019), i.e., [E[[ e, O,,, 5x) Va.g( (0,l])) S 8, which confines the application scope of mSGD (SHB). In addition, the designs of momentum coefficients in Polyak [1977 1964); Kaniovskii 1983); Gitman et al. (2019) are not consistent with some practical appli- cations (Smith et al. 2018 Sutskever et al. 2013). Therefore, the asymptotic convergence of mSGD for convex and non-convex loss functions needs further investigation.
Convergence rate of mSGD: Despite outstanding empirical successes of mSGD, there few sults on convergence rate of mSGD. In these results, Mai & Johansson (020)) studied class of convex loss functions, and obtained convergence rate of time averages without reflecting the role
3

---

Published as a conference paper at ICLR 2022
of momentum parameter. Gitman et al. (2199) and Nicolas Loizou & Richtárik (2020) respectively investigated the asymptotic convergence rate of mSGD (SHB) by restricting to quadratic loss func- tions. [Lu et al. (020)) studied the properties of SHB, where the relation between the loss function of SHB and the step size in every step was studied under the setting that a, and Ba are constants. The convergence rate of time averages
also studied. However, since the momentum parameters not consistent with some applications (Smith et al., 2018 (Sutskever et al. 2013) and the standard mSGD equation B not covered, further studies are needed.
In the original work for AdaGrad (Duchi et al., 2011), it was proved that AdaGrad can converge faster in the time averages sense if gradients are sparse and the loss function is convex. Similar results were established by [Chen et al. (2019). and Ward et al. (2019). Zou et al. 2019) and Défossez al. (2200) established convergence results the subsequence sense. Asymptotic convergence was obtained in Li & Orabonal (2019) for non-convex functions, but the form of the algorithm no longer standard, as discussed in Duchi et al. (2011). Although such a change alleviates the difficulty in the proof of asymptotic convergence, it cannot be applied to the study the AdaGrad in equation Moreover, they required that a noise term of point-wise boundedness (i.e., |]V,, (0,: 5,) Ve.g(e.)) I 8, where 8 is positive constant), which however relatively restrictive.
Convergence of AdaGrad:
MAIN RESULTS
In this section, we provide the main results of this paper, including the analysis of convergence and convergence rate of mSGD in equation 2 and the analysis of convergence of AdaGrad in equation In the following, JRN denotes the N-dimensional Euclidean space and ||-Il stands for the 2-norm, i.e., the Euclidean norm. To proceed, we need some definitions, consisting of asymptotic convergence, subsequence convergence, square convergence, and convergence of time averages.
Definition (Asymptotic convergence) A sequence {xn} is asymptoticallly convergent set IK, if
- (infze |xx==xxl) =0
Definition 2 (Subsequence convergence) sequence {xa} converges in subsequence to a set K, if
there exists at least one subsequence {xt,) of {xy] such that lim [infaex |xL. - -xll)
Definition 3 (Mean-square convergence) A stochastic sequence {xn} converges in mean square to fixed vector 1/1mm -[|))==
Definition 4 (Convergence of time averages) stochastic sequence {xa} converges in time aver- ages to a fixed vector if limy I E[[|x, - xl|2) =.
is obvious that asymptotic convergence implies subsequence convergence, and that mean-square convergence ensures convergence of time averages, but vice versa.
3.1 CONVERGENCE OF MSGD
In this subsection, with the help of some stochastic approximation techniques (Chen) 2006), we aim to prove that O,, in equation 3 is asymptotically convergent to connected component J of the set / := eel] [)] = 0} almost surely (a.s.) under proper conditions. When this connected component degenerates to stationary point 0*, it holds that 6, 0", a.s..
In contrast to the existing works of subsequence convergence (cf. Zou et al. (2019): Chen et al. 2019); Défossez al. (2020); Ward et al.) (2019), we aim prove that 6, of mSGD in equation is able to achieve asymptotic convergence. Since mSGD in equation Blss stochastic algorithm, we aim to establish its a.s. asymptotic convergence. To proceed, we need some reasonable assumptions with respect to noise sequence ( and loss function g(0).
Assumption Noise sequence {5.} are mutually independent and independent of 0 and Vo, such that s(x) = Egg (g(x,E,) for any x TRN.
4

---

Published as a conference paper at ICLR 2022
Assumption 2 (Loss function assumption) Loss function g(0) satisfies the following conditions:
1) g(0) is non-negative and continuously differentiable function.
2) The set of stationary points of [[Veg(0)) is not an empty set, that [ 0) = 00 + 0.
3) V@g satisfies the Lipschitz condition, i.e., there is a scalar > O, such that for any x,y IR.
Vag(x) vyg(>)] S c||x [[[xx->ii yll-
4) There is scalar M > O such that for any 0 E RN and positive integer
Eg. ([V =0)) = M =M(1+
(6)
Assumption M and conditions 1)-3) of Assumption 2 are common in the literature (Gitman et al,
2019). Assumption 2 does pose any requirement on the convexity of g(0). In other words, we allow any convex or non-convex loss functions g(0) as long as they satisfy this assumption.
Condition 4) corresponds to the condition in Shalev-Shwartz et al. (201 1): Nemirovski el. (2009);
Hazan & Kale (2014); Gitman et al.] (2019): Yang et al. (2016); Polyak (1977): Kaniovskii (1983)
where the following inequality is assumed to hold for any I and positive integer n,
Eg, Voo Vog(O, 51) 50,
- K, VO E ERR
where a positive scalar. Note that equation 6 reduces equation if g () is uniformly upper bounded over the space RN. Since equation 6 does not need this uniform boundedness, it substan- tially extends equation 7 such that mSGD also applicable to the scenarios with unbounded loss functions.
Different from deterministic GD-type algorithms with a constant step size, in order ensure the convergence of mSGD, we need decreasing step size for counteracting the randomness induced by noise } (Gitman et al. 2019; Robbins & Monro, 1951]. Specifically, we make the following assumption step size &, together with a fixed momentum coefficient az
Assumption Momentum coefficient a E [0, 1) and the sequence of step size En is positive, mono- tonically decreasing to zero, such that 5+00 e = 4:00 and E Eq +00.
The setting of en in Assumption is consistent with stochastic approximation for root seeking of functions (Chen) 2006) as well as some stochastic optimization algorithms (Gupal & Bazhenov 1972 Polyak| 1977 Kaniovskil 1983 Gitman al. 2019). An explicit example of step size e, satisfying Assumption 3 is E 1/n. Although SHB in equation shares a similar expression as mSGD, the provided conditions of step sizes in Gupal & Bazhenov (1972); Polyak (1977); Kan-
iovskii (1983); Gitman et al. (2019) are not applicable to the general cases of mSGD with static a (Smith et al. 2018 Sutskever al. 2013).
In fact, SHB in equation has a similar expression as mSGD in equation 3 Multiplying Y on both sides of the first equation of equation 4 yields
Vn Y/
Bo 1n 70(1 B.) Ve,g((0. (O,, 5.)
-
o.+1 O, - Vv-n-
We treat Y as one term, as the role of v. in equation 3
By comparing coefficients of equation
and equation we get (²1)) = 1%/%% 1) and & = % B,). In the literature (Gupal & Bazhenov
1972 Polyak 1977 Kaniovskii 1983 Gitman et al. 2019 the parameter setting of SHB in equa- tion has the rollowing requirements
4.00
Σ 7/ 400,
Σ vh <00,
B. 1,
lim B.
1=1
or
4:00
+000
4:00
y2
Σ R
7/1 000,
Σ (1 - 22) t00,
Σ
< t00,
lim B, 1.
Bn
n
n=1
5

---

Published as a conference paper at ICLR 2022
According to the above requirements Bn and ye the requirements E, and a!())
E
E
100,
Σ
E
t00
lim 0+0
(d)
=0.
mm
or
1:00 Σ
1:00 Σ
En
1% #=1
Bn)
Bn
to0,
simsupare a-++
B,
We can see that the static momentum parameter a, which is widely used in practical applications, does not satisfy these conditions. In |Sebbouh al. (2020), the authors studied an algorithm (SHB- IMA) that has a similar form to mSGD given in equation but their conditions for parameters cannot cover the case with a static a.
Before providing the main theorem for convergence, we need useful lemma In the analysis of asymptotic convergence of mSGD, the following lemma plays an important role.
Lemma 1 Consider the mSGD in equation If Assumptions 1-3 hold, then for V0 e RN and VO E TR", there is a scalar T (0,, vo), such that R. (g(0,)) < (' vo) any n 2 1.
Lemma D
actually guarantees stability of mSGD. Let F 00,, vo. (5:)__)) be the minimal a- algebra generated by 01, vo. (5)) As a result, O, is adapted Fn Then for any N4, holds that
E (1 Vo. (.Ve.g(o.) -ea,) (O. =E E E ((e))(e)) -V...) (o. $.)11(((--)))
=E Bgg (IVo, (O,)
Ve,g 5n) S SM SM (1
(0)1))
S MM(
(9)
where the second equality follows from the independence between E. and { vo. (-)))) As- sumption [ and the last two inequalities hold due to 4) in Assumption Lemma respectively. Intuitively, the result in equation means that the fluctuation induced by random noise (5) |
well restrained. Note that the derived result in equation 9 is totally different from equation required in the literature Shalev-Shwarte et al. 2211] Nemirovski et al.) 2009 Hazan & Kale
2014 Gitman et al.] 2019; Yang et al.) 2016 Polyak 1977; Kaniovskii 1983). since equation needs uniformly upper bound K over the whole space (i.e., 0 E IR*) which is difficult to satisty
when loss function g()) is quadratic or cubic with respect to 0 over unbounded parameter space.
In contrast, regardless of the order of g(0) with respect 0, equation ensures boundedness of
E (lVa, 0,) V Ve.g 0.,, =1>)1?)) for learning any fixed true parameter 0-. This reflects favorable learning process against random noise 5. for dealing with general loss functions g(0). This result paves the way to the following theorem on asymptotic convergence of mSGD.
Theorem Consider the mSGD in equation 3 Assumptions 1-3 hold, then for v0, N and Vvn E R.N, there exists connected set J C such that the iterate O, is convergent to the set J almost surely, i.e.
lim d d(),,)")=0,
a.s.
n1-000
where d(x,J') inff(llx-ylllae E'} denotes the distance between point and set J
In Theorem 1, we prove that the iterates of mSGD asymptotically converge to a connected set of stationary points almost surely. When this connected set degenerates a stationary point 0* it holds that 6% + 0", a.s.. The result enables engineers for the design of proper momentum coefficients and step sizes (like a = 0.9, &n = 0.1/n) in the related applications mSGD with mathematic guarantee.
3.2 CONVERGENCE RATE OF MSGD
In this subsection, analyze the convergence rate of mSGD. Before that, given positive real quences {a,} and {b,). we let a, = O(b)) if there is a constant c > O, such that a, b, < for any 2 1. For quantitative analysis, need some extra assumptions.

---

Published as a conference paper at ICLR 2022
Assumption 4 (Loss function assumption) Loss function g(0) satisfies the following conditions:
1) (()) is non-negative and continuously differentiable function. The set of its stationary points [e]][[e(())) 0} bounded set which has only finite connected components J.....nn. In addition, there is E' > 0, such that for any E (1,2.....n1) and O < d(0,Ji) < <'', it holds that (g(0) 8i| + 00 where gi = {g(0)l0 E Jij is constant.
2) For any i E f1.2..... n).
it holds that
[oog d(O.))+0 8(0) gi
liminf
2 2>>0. 0.
many problems of machine learning, especially deep learning, because of strong non-linearity mapping from input data to output data and the structure complexity of employed models, loss functions could be non-convex and may have multiple local critical points. Assumption 4 does not require convexity of the loss function, but guarantees the properties of the loss function around critical points. Assumption 4 2) can be treated as a local version of condition.
In
(P-L)
Theorem Consider the mSGD in equation with the noise following a uniform sampling distri- bution. If Assumptions 4 hold, for vvvo E R. and v0, E ERN, it holds that
E (())))) = =0(e -
(10)
where p = exp EE=1 Ma and M is defined in condition 4) of Assumption
In Theorem 2
let a = O, then we can obtain the convergence rate of SGD,,
E (1Ve, = =((= E 0ee #+)
According to the obtained bounds, the convergence rate of mSGD with a E (0, 1) is larger than that of SGD, which is the case with a = O. Moreover, Theorem 2 provides a stronger characterization of convergence rate than some existing works considering the convergence rate of time averages E E(I V (0.)(0.))'' [0.) O(T') (1 = 1 in Liu et al. (2020) and = -1 11/2 in Mai & Johansson )020 In the following. we will elaborate on this point. From equation 10 there exists a scalar 0 such that Vn
E (1) 1 (0,))
exp
Σ p(1-a"
implying
Ex- (1|
V V. 0m)) 12)
10.
1 Σx
exp
Σn
r(l p(1-a}=
se:
So it holds that
( = (
Σ
Σ
T
T
Let E, 1. then we know that Σ E, = O(IT). Hence,
T
sin(n)
T
p(lap = 0
Σ
= 0
T Σ n pl-aj
T
T
If
pl-aa a)² < 1, IJ
p!l-a," 0 p(loojt!! so have
1 o
((nnooatt = =0(T (rou-op))
n=1
7

---

Published as a conference paper at ICLR 2022
If p(1-a)² = 1, it holds that M
a(l-a)²
O and hence
1
1 0(InT) 0 ln7
(
M(-aj
T
If p(-a)) > 1, then Σ
xl-ay2
CT( + Ca as T too, where Ca is a positive constant, so
E
pllay Ca(T) o
Ca T
n=1
Note that the coefficient Ca depends on s. p. and a. where s is the constant given in Assumption only depending g(0). and is given in Theorem 2 and relies M in 4) of Assumption 2 and step size &,- The above observation indicates that setting a close to one makes mSGD) achieve con- vergence rate of time averages of order O1//T). As remarked previously, larger implies smaller coefficient Ca and thus quicker convergence rate. Interestingly, since Ca(T) is monotonically in- creasing, the convergence rate has a relatively small coefficient when small. This could illustrate why mSGD can achieve better performance in the early phase of iteration.
3.3 CONVERGENCE OF ADAGRAD
In this subsection, we aim to establish the convergence of AdaGrad. Compared to the study of mSGD, the design of adaptive step size increases the technical difficulties. To proceed, the required conditions on loss function g() are summarized follows.
Assumption 5 Loss function g in equation 5 satisfies the following conditions:
!) g(0) is non-negative and continuously differentiable function. The its stationary points J = (0 [[]]\e))))))))) 0} is bounded set which has only finite connected components JI...., In addition, there El >> O, such that for any and 0 < d( < E,, it holds that (g(0) gil / where = {g( [)] E J is constant.
2) The gradient Veg( () satisfies the Lipschitz condition, Le. any x,y E RVV.
V/s((x) - Vy8(>)| S ce|x yll-
3) There are two constants M' > 0 and O such that for any R. and E N+.
Eg. V (0 E.)11)) (os(0,55))1)
M Ves(())] +a.
(11)
Condition 2) is the same in 2) of Assumption Condition 1) is relatively weak, because it does not require any convexity of the loss function or global conditions as P-L condition. There are many
functions satisfying Assumption 1) but not convex, such as y sin? (x), y = (x- 1)(x (x ()) and y cos² (x). Similar to condition 4) of Assumption 2, condition 3) condition to restrain the noise influence. Equation [1 is milder than (Vog(0,E.) 5.) Vog(0)]l S S a.s. (Li
Orabonal 2019 Défossez et al. 2020), which is relatively restrictive in dealing with unbounded
noises, e.g., Vog 0. 5m) = V Vog(O 0 + 5m. where 5, is independent identically distributed and Gaus- sian.
Compared to SGD and mSGD, there are more challenges in analyzing the convergence of Ada- Grad. The challenges mainly come from two aspects: (1) since AdaGrad does not have a decreas- ing step size, the noise influence AdaGrad cannot be restrained mSGD which is with the help decreasing step size satisfying Assumption B (2) adaptive step size of AdaGrad in equa-
tion (i.e., 0o/ E Vo,g( 0, [2) is a random variable conditionally dependent of š, given a 01, 51.... 5n-1 Then when deal with terms in the proof like
dg V (V Vo,g(G, En) or S,
a Vo, 5.,)
(12)
we cannot make the conditional expectation to transform equation 12
do V (o),((B))l'"
of S
Eg. (IVe.. (x)1
or
8

---

Published as a conference paper at ICLR 2022
In the literature, Li & Orabona (2019) changed the step size 0g
( $1112
and Gadat & Gavra 2020) changed the step size to Y // O₂ + where
0₂ = 01 + Ya (pxl & 0, 5.) gr 0,-);
and Pn.nn: On are tuned parameters, in order to make it conditionally independent of En given 0 51 5e-1). which however is no longer the standard AdaGrad as in equation Streeter & Mcmahan 2010 Chen et al. 2019).
Before we provide the main theorem of this subsection, useful lemma is worth discussing.
Lemma Let {a)), (Bx) being non-negative random variable sequences, such that the following conditions hold almost surely
Cge 00;
I OxBx +00;
Then there exists subsequence {Bm, } of [Ba), such that Pn. x 0 almost surely.
Proof We aim prove liminfx 400 Br 0 by contradiction. Suppose liminfz-4od then 3ko such that vk > ko, Bx > u/2. It follows that
0,
a& k=
Σ
Σ
Cs < to0.
(13)
k=
Obviously, there is a contradiction between equation 13 and the condition Σt=1 Oh = 400 Thus,
liminfa- - Bx O. So get that there exists subsequence {pm,} of {B&} holds Bm. surely.
k 0 almost
This lemma, inspired by Proposition in Ya. I. Alber (Alber al., 1998, is quite useful in the convergence analysis of AdaGrad. Then we are ready to provide the convergence result of AdaGrad the following theorem.
Theorem Consider the AdaGrad equation Assumptions and hold, then for '0, R and Sn = O, there exists connected component of the set J CJ, such that the estimate 0, is convergent the set J' almost surely, i.e.,
lim d d(O,,, )) =
a.s.
B1-00
In Theorem prove the standard AdaGrad is convergent almost surely, in contrast the vergence time averages in Chen et al.] (2019); |ard et al. (2019) which focus on the metric E B[| Va, (0,)))), or the subsequence convergence in Zou et (2019; Défossez 2020 focusing min E() V Ve,g ((,)))).
4 CONCLUSION AND FUTURE WORK
In this paper, we studied the convergence of two algorithms extensively used in machine learn- ing applications, namely, momentum-based stochastic gradient descent (mSGD) and adaptive step stochastic gradient descent (AdaGrad).. By considering general loss functions (either convex non- convex), we first establish the almost sure asymptotic convergence of mSGD. Moreover, we find the convergence rate of the mSGD and reveal that the mSGD indeed has faster convergence rate than the SGD. Furthermore, we prove AdaGrad is convergent almost surely under mild conditions. Subsequence convergence and convergence of time averages in the literature substantially tended in this work to asymptotic convergence. To better understand the AdaGrad, we will study its convergence rate in the future.

---

Published as a conference paper at ICLR 2022
5 CODE OF ETHICS
This is theoretical paper focusing on the investigation for the convergence of mSGD and AdaGrad optimization algorithms. The results in this paper do have issues fairness, inappropriate potential applications and impact, privacy and security issues, legal compliance, research Integrity Issues, or responsible research practice (e.g.. IRB, documentation, research ethics). This paper does no involve human subjects, practices to data set releases, potentially harmful insights, methodologies and applications, or pontential conflicts of interest and sponsorship.
REPRODUCIBILITY
This is theoretical paper focusing on the investigation for the convergence mSGD and AdaGrad optimization algorithms. The developed results are provided in the main paper. i.e., Theorems 1-3. In Appendix, the proofs of these theorems are provided together with some useful lemmas well as their proof'. An outline of these proof's is given in Section A in Appendix.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Ya I. Alber, Alfredo N. Iusem, and Mikhail V. Solodov. On the projected subgradient method for nonsmooth convex optimization in a Hilbert space. Mathematical Programming, 81(1):23-35, 1998.
Wangpeng An, Haoqian Wang, Qingyun Sun, Jun Xu, Qionghai Dai, and Lei Zhang. A PID con- troller approach for stochastic optimization of deep networks. In Proceedings of the IEEE Con- ference Computer Vision and Pattern Recognition, pp. 8522-888 8531, 2018.
Léon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade, pp- 421-436. Springer, 2012.
Han-Fu Chen. Stochastic Approximation and Its Applications. Springer Science & Business Media, 2006.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of Adam-typ algorithms for non-convex optimization. International Conference on Learning Representa- lions, 2019. URL
Zaiyi Chen, Yi Xu, Enhong Chen, and Tianbao Yang. SADAGRAD: Strongly adaptive stochastic gradient methods. In International Conference on Machine Learning, pp. 913-921, 2018.
Saman Cyrus, Bin Hu, Bryan Van Scoy, and Laurent Lessard. A robust accelerated optimization algorithm for strongly convex functions. In American Control Conference, pp. 1376-1381, 2018.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of Adam and Adagrad. arXiv preprint arXiv:2003.02395 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In 23rd Conference on Learning Theory, COLT 2010, pp. 257-269, 2010.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2111-2159, 2011. URL
http:// wwt.ooog//ppp..... v12 www.h/uhhhiaaa..m.m.
John Duchi, Michael Jordan, and Brendan McMahan. Estimation, optimization, and parallelism when data is sparse. Advances in Neural Information Processing Systems, 26:2832-2840, 2013.
S. Gadat and I. Gavra. Asymptotic study of stochastic adaptive algorithm in non-convex landscape. 2020.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. Advances in Neural Information Processing Systems, 32, 2019.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey E. Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp.
2013.
A. M. Gupal and L. G. Bazhenov. Stochastic analog of the sonjjngate-raddien method. Cybernetics, 8(1):138-144 140, 1972.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1): 2489-2512, 2014.
Heaton and Jeff. lan Goodfellow, Yoshua Bengio, and Aaron Courville: Deep learning. Genetic Programming and Evolvable Machines, pp. 305-307, 2018.
Geoffrey E. Hinton and Ruslan R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 31365786):504-500 2006.
Yu M. Kaniovskii. Behaviour in the limit of iterations of the stochastic two-step method. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fizáki, 23(1):13-20 1983.
11

---

Published as a conference paper at ICLR 2022
Donghwan Kim, Sathish Ramani, and Jeffrey A Fessler. Combining ordered subsets and momentum for accelerated X-ray CT image reconstruction. IEEE Transactions on Medical Imaging. 34(1): 167-178, 2014.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference for Learning Representations, 2015.
Alex Krizhevsky, llya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep con- volutional neural networks. Advances in Neural Information Processing Systems, 25:1097-1105, 2012.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pp. 2863-2872, 2018.
X. Li and F. Orabona. A high probability amalysis of adaptive sgd with momentum. 2020.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 983- 992, 2019.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. arXiv preprint arXiv:2007.0798) 2020.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradi- ent, Newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3)653--70, 2020.
Vien Mai and Mikael Johansson. Convergence of a stochastic gradient method with momentum for nonsmooth nonconvex optimization. In International Conference on Machine Learning, pp- 6630-6639, 2020.
Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. 2010.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574 1574- 1609, 2009.
Y. Nesterov. Introductory Lectures on Convex Optimization: Basic Course. Introductory Lectures on Convex Optimization: A Basic Course, 2004.
Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. SGD and Hogwild! convergence without the bounded gradients assumption. Interna- tional Conference on Machine Learning, pp. 3750-3758, 2018.
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Com-
putational Mathematics Mathematical Physics, 4(5):1-17, 1964.
Boris T. Polyak. Comparison of convergence rate of one-step and multistep optimization algorithms in the presence of noise. Izv. Akad. Nauk SSSR, Tekh. Kibern., 1:9-12, 1977.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 2203)4400-477 1951.
O. Sebbouh, R. M. Gower, and A. Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. 2020.
Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal estimated sub-gradient solver for SVM. Mathematical programming, 127(1):3-30, 2011.
Samuel L Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc Le. Don't decay the learning rate, increase the batch size. 2018.
M. Streeter and H. B. Memahan. Less regret via online conditioning. Computer Science, 2010.
12

---

Published as a conference paper at ICLR 2022
Iya Sutskever, James Martens, George Dahl, and Geoffrey E. Hinton. On the importance of initial- ization and momentum in deep learning. In International Conference on Machine Learning, pp- 1139-1147, 2013.
Shenghao Tang, Changging Shen, Dong Wang, Shuang Li, Weiguo Huang, and Zhongkui Zhu. Adaptive deep feature learning network with Nesterov momentum and its application to rotating machinery fault diagnosis. Neurocomputing, 305:1-14, 2018.
Tijmen Tieleman and Geoffrey E. Hinton. Lecture 6.5-RMSProp. COURSERA: Neural networks for machine learning. University of Toronto, Technical Report, 2012.
Zhong-zhi Wang. Yun Dong, and Fangqing Ding. On almost convergence for sums of stochastic sequence. Communications in Statistics- Theory and Methods, 48 (1811)6609-3000 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence over noncon- vex landscapes, from any initialization. In International Conference on Machine Learning, pp- 6677-6686, 2019.
Matthew O. Williams and Teems E. Lovett. Numerical diagnostics for systems of differential alge- braic equations. arXiv preprint arXiv: 1602.07550, 2016.
Tianbao Yang. Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint 1rXtv:1604.03257. 2016.
Szymon Zareba, Adam Gonczarek, Jakub M. Tomezak, and Jerzy Swiatek. Accelerated learning for restricted Boltzmann machine with momentum term. In Progress in Systems Engineering, pp. 187-192. 2015.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. sufficient condition for conver- gences of Adam and RMSProp. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 11127-11135, 2019.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX OUTLINE
Section B aims to verify the convergence results of mSGD, Several auxiliary lemmas are first pro- vided, followed by a proof outline for the main results of mSGD. Then the proofs of these lemmas given. Theorems I are proved in Sections [.9 and [. respectively.
Soction[Caimn to verify the convergence results of AdaGrad. Some auxilarr lemmas are given at the beginning. followed by proof outline of the main results for AdaGrad in Section
C.1
Then we provide the proofs of
the lemmas. Theorem 3 proved in Section C.8
B CONVERGENCE AND CONVERGENCE RATE OF MSGD
The following lemmas are used for the proofs of Theorems 2 Hereafter, N4, denotes the set of all positive integers.
A function f is in a (differentiabilitt) class C+ its /th derivatives exist and are continuous, where I I k.
Lemma (Lemma 1.2.3 in Nesterov 2004)) Suppose f(x) ECI (x with gradient satisfying the following Lipschitz condition
[Vf(x) vf6ii] Sc|l>>>l
then for any x. RN, it holds that
f6)) + V))+ (x- 111 - (V) (x-))+ +yll- -11.
Lemma Suppose f(x) EC (N) with gradient satisfying the following Lipschitz condition
[[ (((x)>-((()) v - c||x-yll,
and the set S (x)V = ) bounded and only has finite connected components S2,... Sm.. Furthermore, assume there exists E > 0, such that for any i = 1,2....,m and x E {x|0 < Six < E) it holds that [x(x fil + O, where fi = fxx for x E S,. Then for any i = 1,2, 1,,....,m m, if there is
6o > 0 satisfying S;) < E it follows that
|f(x sc,((xx) -il-
Lemma WWan al. 2019 Suppose that {X,} TRN is Lr martingale difference sequence, and Fn) Fn) is an adaptive process. Then it holds that L Xx < too a.s., if
[([|x,11>) < to0, or Σ E 2
< t00, a.s.
Lemma 6 Suppose that {Xx} E R is non-negative sequence of random variables, then it holds that En Xn < 400 a.s. if E o (X,) < 400.
Lemma Suppose (v,) is sequence generated by mSGD in equation Under Assumptions it holds that Ento E (11)m112) < c(vo, 0:), and E [vrll < 4oo a.s., where c(vo, 01) is constant only related to Vo and 0
Lemma 8 Suppose {0,} is sequence generated by mSGD in equation 3 Under Assumptions holds that: for n 2 I,
73
Σ
E& < B(vo. 01) < t00,
Σ E Vag(())1 t00.
where B(vo, 01) O is constant only related vo and Oi.
14

---

Published as a conference paper at ICLR 2022
Lemma Suppose {0,} is sequence generated by mSGD in equation such that {g(O.)) verges a.s. If Assumptions 3 hold, and
g(0n+1) S Sn - b L e e [g({))] a.s.,
(14)
where So is random variable such that lim Su 5 a.s., and b is a positive constant, then there exists a connected component J" of
0 = 0}, such that
d d(),,."") -mك 0.
B.I PROOF OUTLINE OF THEOREMS 1 AND 2
The proof is in light of the Lyapunov method. We aim to prove that g( (0,) is convergent a.s., and then to prove Va,g(( 0,) + 0 a.s. With these two results, we are able to get 6 + /" a.s. In the following, we provide the proof outline to show how to obtain the provided results of mSGD,
Step 1:
We prove mSGD is stable algorithm, i.e., (())).) <K < t00, V n, in Lemma to prove that a weighted sum of the loss function value, i.e.,
The idea
(1/22-))*
is bounded through a recursion formula (a rough form)
Un - 5 AAd B Σ
( (. (A, B are two constants).
Then we apply Assumption
to and then obtain
- Un-U S Aad B n-1
Σ (1/(2-
af (A, B are two constants).
R
Combining Un-1 and R leads to
Fn - F--1 SAx"
(A, B' are two constants),
2 2-
where
n-1
F Σ 1=1
Z(i + 1(1+1)EE
G (1+(((((0)) (1+g(0++1))
(i)
2 2-
and
z(1) M = (1 + +Mee²
π 1=
(1 Moez) (1+ Moe +1).
Thus, we are able obtain E(g (.)) < F A - af +B (1/(2 a))² to0
Step 2: From Lemma and the condition Σ e² +00, we are able to prove that Σ"= ||ve|| and
Σ& [ (o,
(e))( || are convergent a.s. respectively, as stated in Lemma and Lemma
Step 3: We divide g(0,) into three terms
g(0, (O.)) Σ A Σ B&e Ve. + Σ C (V (On. Vo,s(0,)).
able to prove that Σ" [l)) convergent a.s.. From the convergence theorem for certinnnll-difffeeeee sum (Lemma 5), we prove Then prove g(0,) convergent Step 4: By Lemma 9 and the convergence g( ((,) in Step 3, we get 6, + J" a.s.
From Lemma 7 and Lemma
B V g 0 I| is
that Σn C7 (Ve, g 0., 5.,) V ((0))) is convergent
Step 5: After the proof of the convergence of mSGD, analyze the iterates of F,. Then under new assumption iim - (og(0))))/(((() g:) 2 s O, we are able to obtain the convergent rate of mSGD.
15

---

Published as a conference paper at ICLR 2022
B.2 PROOF OF LEMMA 4
First we construct a closed and bounded set S which satisfies S 3 U S. Since / E S) is continuous function on a closed set, [V]())] Ex S) is uniformly continuous function. Then 3 E > 0, v S, if S() < Eg. there is [V[(x) < <<///4 We assign 6o = m
Let S = Sx) < e/}, S = {x]d(x, Si) < e) Since Si) a continuous function, Vxo E S we can always find straight line lo paralle to (x(ox) and passing through Xo, defined as
Vf(xx)
4: x xo
[
From S S, we know Xo S. Since S. is open set, there exists do < 0 < Bo. such that xo + (VVflx)/\Vf((o))) E S ab < < Bo), and
V
do
sup 1<0
XO +
V.((x))
inf Bo
xo +
S
120
[V](x))]
Define function
Vf(xx) [Vf((x]]] - fi (t E (ao:Bi)):
8(1) = f No +
Since x + E S (an <1 Bo), it holds that
xn+ [V[(xo)]| 1) - Si +
f)((x))
So g(1) ECI ( (co, Then for Vd, 1" (ao. from Newton-Leibniz formula, it follows that
8(()- ( (( (600)
(6(())))8(()))) &. (()ddx.
(15)
Next we will prove gx(x) satisfies the Lipschitz condition. According to the definition of S,, fxo + VV /V/(x//\VVV(x)) keeps the same sign over 1 E Bo). Thus, V Ti, E (Co, it holds that
)((())))))))))))))))))))))))))
V/(10)
v((x)) [V)())]]
Vf(xo)
-(()))8(())
[
vf 1o
- vv xO - [VV[(x)]]
(x((x))
vf(xo)
7. 77(100 x0+ + D2 V
vf(xo)
v xo + ύ
[x(o)
vx(x))
v)((x))
v An +
vs x D2 [
[V
From the Lipschitz condition of V.,. we have that
< vf xo + [V
Vf(xo)
) vf
-vf
xo 42
Vx(x)) [V
)
scln -aa|
vf(xo)
[V
= =c/o]- -2/-
From the above analsis, we obtain the Lipschitz condition of g' (x), that is, V f1 12, there is lg'(T)
22) S c| :2/. By using the absolute value inequality, we get that -c|ti 12 S ((((T)
g' 2 I c - T.. Then it follows from equation| 15 that
g(t') - g((")) [[" (g' - 10--g/0 g'(r') dx J(" 8(())xx f.= -cp-- -c--x-11lde -(xxx f. 8(())xx
=- --
(1' (2) +8 (()((( -1"),
+
16

---

Published as a conference paper at ICLR 2022
Let r' = =0r="" --g()// So = 0 (o). Next, we will prove r" (co. Bo). We separate
into two cases. First, we assume that g' g0(0) > 0. In this case, because
1 S
sup i<0
An +
we just need to prove
f(x0) [V
E,S V10 E 82(0),0) .0.
N0 + 10
(16)
Note that
(xx)
((x0)
+
.S S (:), +
S E +
[xo]
From E Sy, we get [xoo)l < CE// /4 and d(xo. S:) < E/. Then we have
( xo + to [ ss
f(m)
v E + nol I E + (0()) E +
[[
+ El Ej
I E
<Ej-
4 2
Thus, equation 16 holds, meaning when g((0) > 1" (do.Bo).
Secondly, when g' (0) < O, we can also prover" (co. Bo). It follows that
8(0) = 8(()) 2 g((') e((") (1' -1) g (t) 1") 2c
(g' (0)) 1
(8'(0))²
2c (8))))
1
20
1 2c
V
vf(xo)
1
[V
2c
That is
1 [((())))
2c
Because of the arbitrariness of xo, we concludes that 3e' min( VS, (i= 1,2,....m. if S() < E there is
[]
B.3 PROOF OF LEMMA 6
For vθ have
+oo +he
X 8)
Σ
100 Σ 1=
U EE
lim 10200000
lim P +0+000
x, 2
S
lim
E
1=
m m
1=
where the last inequality is due Markov inequality. Since
E
(X)
oo, follows that
+ +o0
nun X 1=
lim
E
Σ X
(17)
n
m+++o
F
By Cauchy's convergence test, we have Σ < 00, a.s.
B.4 PROOF OF LEMMA I
Recall the mSGD algorithm in equation 3
Vn 0V + Enp ((,,
(18)
0, 9 Vn
(19)
Equation equation 18 is equivalent to
Fn 0V + e, Ve, g 0g) + ex VV,g 5x) - Vo,g(0.))
17

---

Published as a conference paper at ICLR 2022
Under Assumption 2), it follows from Lemma that
-Vgg(0)) - C 1v.111 -g(0+))-((0)) -vag(()))) + 11,11
(20)
In this subsection, we just use the right side of equation subsection. Consider Vag((,)Tu in the following
20
The left side will be used in the next
Ve.s(0,) = (aa
<V v( ",gp::/h"___a00000000000000000a" Vog(0
Recursively applying the above equation yields
Vag((0) -
a' - vo, Σ a
4-1
(21)
a' V (.
By substituting the above equation into equation 20 and noting -(Veg(()) ve_ v VV,,(())-Vo, Ve_ 0 (0)0))_lllllllll < c||,,-11?, we obtain
8(0 g(0.)
$ - a' (oo,((1)) Σ - V. Vo. Vos())) 1lr/
1=2
(22)
Σ a (Va8(()) - Vo 8(0,(())1))
- a V ((0
Σ V + Σ (1vil
Denote Z()): 1 (1 Moez), where
cM
Mo a
where 8 >>0 0 is a constant and M is introduced in Assumption 2 4). Here we define Mo. Z(r) and 8 to facilitate the proof equation 33
From Assumption
holds that Σ e? < 4o0, Thus,
Σ 1:00 Moe? < -o0 From a general inequality In(1 +x) < x for 1, we get
Z(r)=
II + MoE = exp Σ In(1 1 + Moe?)
+.20
< exp
Σ Moe?
< t0o,
which means that Z(r) is uniformly upper bounded. Then multiplying Z(r + 1) on both sides of equation 22 and taking the mathematical expectation yield
Z(r + -((()))(())))((())) < Z(r 1
-
(Vo,8(0)) + Σ a a''iz(ii+ 1)E ((vv)))))))
-Z(1+1) Σ
α
e: E
Veg(e)
< C- (V, + Σ a''iz(ii+)) 1) (1IvllP).
(23)
where the first and second inequalities are respectively due to Z(i + 1) < Z(i) and Z(1 +
1) a
18

---

Published as a conference paper at ICLR 2022
Next, we aim to analyze -/==1 at "Z(+ 1)E 1) ((vvvl)))) in equation 23 is proved in Appendix B.5 that
i
Z(i+ 1)
Σ
(11-331--1 8311 1) 2 + I) (1 - Va
x1
kml
2
a
1++
8)(1
Z(k +1)
E ((Es((Oe+1)) - (B())))))))(((88888(8((( (EEE-18((02)
(24)
Taking a weighted sum of equation 24 yields
a 'Z 1)E[
a (1+51
(11vo12)
Σ a-'
a (1+31(1-) 1) + (()) 02, &0)))
a a1-8
Σ d'
Σ
(1+8)( 1) Z(k 1) B -
-E (2)111(08)() A
al-6
(25)
We derive that
) d' ((vo))) '
A Σ a
1 σ ((1 E (I]vol1),
(26)
i
B
Σ Σ
a k+
() ( (..(0(,55)1)))
al 1-
=
Σ
a
(et* + B 51)(
(27)
α a1-5(1
(1
aτ)
k=1
2 1
C=-
Σ
Σ
α
1- 8(f z(k 1) B(Exx((+H))) -E (E (8)-18(00))
11-
k=
2
a +z(k 1) B ((egg((++))) (E
(28)
Substituting equation
26
equation
28
into equation 23 yields
Z(1 + I)E
(8(0++1)-g(e))
- 8(0.))
-''10000 5
<-Z(1 + 11)0
E (V (Vo,)(0))T
(1)oo1)))
1 σ
(29)
+ αl 11-5(1- -²)
Σ
a i 1)e² ( Vo..
E=1
α Σ
2c
Σ ok
( (((()))(E(((())))BBB(CeCC
a
Construct sequence (Vx) as follows
1 n-1
V, Σ
Z(z + I)E (((0++1)8((8)))
(30)
2 α
1=]
19

---

Published as a conference paper at ICLR 2022
By substituting equation 29 into equation followwinn the way of equation 26
equation 28
we have
V S a2 - α3)
ca c2 a)
1 1 Z(1) E
(Vol) (V),(((1)' mn)
a)(1 (1 (1-a)(1 (1--x)) Z(1) E (||vol?3
n-j
Z(++ 1) (( Vax(O, 5)11
α al-6(1 61 x1 a)²
2 0
2c
a [(-
Z(++1) 1) (
α1
61 x1-8(1
2-
where f(n-1) is defined as follows
n- f(n ()- = E (a(2-a))* - a n_!
Σ (2-
(2
Move the last term to the left-hand side of the above inequality, then we have
Σ
1
Z(t 1)B
(0) -e) (n-1) -(()))
2 2-
0 (2 - a.
E (V) + ca a)
((1)
Z(1) (llvol²)
(31)
1-a a
a)(1 σ.)
Σ
Z(t - 1) e),² V Vag(O, Va)(0,,))13)
α 6 a (1 - x)
2 - a
1=1
where
[m)
= (1+ 20e f(n -1) 221-8(1 og))
9+1
(32)
Because of 1, it holds that f(n 1) > 0 and (n) G It follows from Assumption
3 that
Σ
Z(1 + 1) (( 74.(0,,5)11))
a 8 σ (1 a)²
2 a
(33)
Z(1 + 1)MoE?e (n-1) (1 ((g(e)))
where
cM
Mp = al- a1- a²) x)2
Calculate f(n-1) 1), then obtain
f(1-1) n-1 (a(2 103-001 a))² - α
n-!
Σ
a 1+8 (2 -a))))= 00
20

---

Published as a conference paper at ICLR 2022
It holds that
Σ
1
Z(r + 1]B
(n) - x()))
2 - 0
A(1 + 11 (1+T(((0))
2 - 0
R
Σ
Z +1+1) 1) (441 + +g(0
2 2- 0
Z(t + () + +Moe,) E
4
(1+ (1+8((1)
(34)
2
R
1 n-t
Σ f(n 1)
(e--
a-
n-1
(1)) (1+((1+
Z(t + 1)
2
1=1
n-1
Z(1 + 1) + Moe,) E
e (n "1+
1=1
Substituting equation
33
and equation 34 into equation 31 yields
R-11
Σ
Z(1 + 1)E
C/+1 (1+ (1+
(n)
2
n--
Σ
+ Z(1 + () M (1+
(35)
2 a
1-1
(2 ())
E (VV + ca" (2 a)
(1)
Z(1) E (11vol3).
1 x
2(1 a1 ox))
According to the definition of 2(1), we have
4:00
Z(t) [I Moe?) (1 + Moe?)
II (1 Moe?) (1+ (1+ I(t++) 1). km1+1
K-
Let
n-
Z(1 + ((++))EB (1+(0(())))))
α
and it follows from equation 35| that
E E(g(e))) + a² a2 2(1) -11 E (V
a))
Fn - ko SZ(1)
2 α
1-
(36)
ca.' a (2 ax)
2(1 a1 aτ) T(I)TE EE (11x011))
Denote p p=exp/ ( E M
By taking the summation of equation 36 we obtain
Fn ((())) (1+ ((1)))
Σ
1-1
p(2 a))
(Vo,8(0))
Σ a'
2
α
a
ca (2 a)
+ - (1 0:))
Z(1) E (1lvol 122)
Σ a¹
1=1
p(2 a)
1-a E E(el (1 (1+g()))) pax x))
E (Vo,g((1))
(1-x) x22
ca 188 1+8 (2 - o.)
2(1- - 2(1-a)2(1 ατ) 1(1) E (1)
21

---

Published as a conference paper at ICLR 2022
Define
((0 1 p(2 0.)
E (el (1+((+)()1))
pa(2 a)
12 [(Vo,g(0))
1-0 a
(1 a)²
ca c 0.)
+ 2(1 a))(2 στ) 7(1) E (1)=o113)-
It follows from the relationship between g( ((++1) and Fn that
R-n
E (1 + g(0+++))
<
Z(n E) (n)) (1 ((0+++)))
2 a- 1
Σ
1)E+1)E(e (1 (1+
2 - a
pfn 1 - vo))
which leads to E (g(0.))
T(00, vo).
B.5 PROOF EQUATION 24
We consider
Eg(0++1) ())
= 8(0)) + + -()-)))))(0)
{e((((++1) 8(0))
<=eVaag())) 11; =illvil
(37)
(~&,V e, (1, (e V 5 + fellvvl1
-av/v-1- |||1 &: Ve,g 0,) Vog(0,,5 |
-(E,0011 v (.)) (V)g(()) vag
( E.)) - {
where the first inequality is due S E in Assumption 3 and the last equality is from equa- tion 19 Since and 0 are independent, taking the mathematical expectation of equation 37 and noting that
E ( (VV -e. ve.((. = =0,
(V),((0))
yield
E (Eig(0:+1)) - (Ei-18(0:)
(38)
Sal(v] v- - E (11vil13) + E ( voxx0)))) = (1lv)l1).
Moreover, holds that
E (1[V Vo,g(0, (V)
E (l) E.. (
E (lvv av 112) - (())
(39)
E?
(Ilaal)) + a E (1|v=~111 2a E(v E(vTvv-1) - EE ((Vo))(8)))
Combining equation
38 and equation 39 we
E (E:g( 1)) E ((G-ig(()))
8²
s E (llv)l12) a² 1 (1v-
E ([Vv - - (11v)13)
(40)
+ 22
E (((Vogg()) - Ve,((e, vo.((..))13)
2
22

---

Published as a conference paper at ICLR 2022
Since - 0, given any ò > O, there is an integer to such that for i 2 1- CE; > a 66 0). Since io is finite, without loss of generality, we assume io = 0 for convenience, iee, 1 C7 >
11-6 (8 > (i 2 1). Thus, we have
E Egg (c+1)) - E (E)-1g((0))
a'16
2 E (B(111))) a [B(1vl))-aato (11=-111) + & E ((V (e8(00
(41)
Multiplying both sides of equation 41 by A(i 1), and noticing that Z(i) Z(i+ 1), have
Z(i+ ((i+1)(([v11l) - zz)) (()))))) ((v)-111))
2
E?
- al 1i+ ((eg((( - (()) + xx 1 (,,
Then equation 24 is obtained by recursively applying the above inequality.
B.6 PROOF OF LEMMA
From equation 40 we have
E (Eng((nt))) 0n+1)) - E (eog(01))
a Σ
2 E (IVV
E (11vx113) +
E E[1
Σ
- Σ E (11v:11)
2 1=1
2
(42)
" Σ
2 ((V))(()))) - Va,g( {)11).
follows from Assumption 5) and Lemma that
E [ ( Ve, (,8(0,5)11 5) < M(1 + 7(0), < too.
Because of Σー_ & < too, there scalar M > such that for Vn
Σ
va,((,,))))) < M t00.
2
Then it follows from equation 42 that
n
Σ [1 a² - cE)
2
+ a² 2
M + Eog(0)) (0)
En 1E (g(0
E (11vo11- -1lvall))
Σ c- E (+
2
1=1
M + Eog 0 o² (1)221))/2<
where K is positive scalar. Since e, + when is large enough, it holds that {((1 a²) < <1-02-
сE Without loss of generality, assume (1 d²) <1 d - CE for 2 0, so E" ((Iv)(1)
10K +00 By Lemma 6 obtain E 11:11 < to0.
I-a2
B.7 PROOF OF LEMMA g
Through Taylor expansion, we derive that
g(0.+1) g(0,)
(43)
-Vo,8(03)) ((++0 0,) -Vax(0,)) v -vax())) (0 -0+1,-0),
23

---

Published as a conference paper at ICLR 2022
where gr means point between 8 and 0,+1- Substituting equation 21 into equation 43 yields
g(0+1)) g(0) aa'''' E o (Veg(()) Vo_ (((0-1)) v-1
Σ d VVgg(()))))) Ves((,)) (Vog (Vo_8(()))Vev(())) (0++1- -.))
It follows that 8(0++1) -g(0))+ Σ 18(0++1)-8(0)))
α" Vo,8(0)) J v1+
1 a²
=g(0))
1-a El [1
1 a
a"-1+1
VVag(0)Vox((,55 Σ (00))(02) (Vesee))) (0.+1 0.)
Σ a+11+1
a (V,.(()))
V1-1-
(44)
Take the mathematical expectation of equation 44 and notice Assumption 3), then have
a T-a Volg(01)
1
EE (g(( (g((0++)) 1 (g(01)
El ([V))((())))
T-a
Σ & E ((
Σ E (1va)1))
2c
Σ a rm]
E (11x11P).
From Lemma 7 it follows that for some positive constant Q,
2c
"
E (11v. + 1- Σ
E (11v)))) <e
Hence,
a E (g((0+1)) <Q+ (g((())))) a-a Va
1
a-a ((
& E 0.))1)
As result,
Σ <(((Va)()))
Ves(00)TT
el [(V
1-a EE((( 11))
1-a
00
From Lemma we have E" Σ" V < too a.s..
B.8 PROOF OF LEMMA
We divide the proof into three steps.
The first step is to prove
iim (.e,(((,))) 0 a.s..
Suppose the above conclusion does not hold, i.e.,
lim Ve.g((,)) > 22 a.s.,
24

---

Published as a conference paper at ICLR 2022
where is random variable depending sample paths. Then it holds that
+ +oo
[| 8(m)) 1/²
P
UUn ==Im=R
From equation
14 and lim Su 5 a.s., if Vo, (.)) 1 it holds that
g(0++1) S.. -
i=
It follows that
+00 P( lim 8(0++1) -00 2 P n-7
(wW)))(0))) =
U [==1
As result, lim ++ g(0 g(O)) meaning contradiction. Hence,
liminf Vo,g(0,)) a.s.
(45)
7
Step 2 is to prove that the set {0,} has accumulation point contained in with probability one. From equation 45, we have Ve >
e [(m))( > E e) 0.
P UN
m=n
Since [V)(()]1 is continuous, vg > 0, it holds that
+00 +:00 inf 6EJ
00n 011 8)
In addition, under the given conditions, J is a closed set. It holds that
P
UU
min O. 011 > 6) 0.
1==mm
For convenience, let 0: == arg minge/ 0 0112, then
400
(11e 0% s v8 5))
P
(46)
m
follows that
n {m.)) i=l
U
0m, 0 S v8 1,
(47)
where SN is the set of all infinite subsequences of N. Since (0 CJ (0 is bounded. From the accumulative point principle, the event
UU
1 0m, S 515),
a deterministic event, i.c., being true for every sample path. Thus
|| ||0m.
Bm,, || S v8)
(m, (my))
1/21
a deterministic event as well, where Fell N the arbitrariness of {m,). we get that
the set of all infinite subsequences of (m:). Due to
(110m) - 0me, S v8
U
n
(48)
Am (mg i221
25

---

Published as a conference paper at ICLR 2022
is a deterministic event. Therefore,
[10m ( (m
U
n
Smj < v88 2 mm - 0mill < v8) n n(1een 0nn11 < v8) vτ)
(49)
|1emn 0m,, < v8 (( (mm, Omng < v8
U
(milEahy (mi JE 1eff isz1
n 0mey 0mng 11
< v8)
>P
U
n (1em
Omn, 11
v8 n nn
100
fnlmmm 1m. - 0 < v8)
te 1221
nIl
Om:
omi| < kv8)n
(10m - -Oin, 11 < vτ))
Em:
1/11
(my lf i.22 1.21
U (m
Om - 0mill < vō)
n (110
O < V8 ))
(mr te (mi,) leggeegff Jeggi 1321
U
n
(10:i:
Oino, 11 =
(mmtech (mm,)e
1.21
))
n Om 0%
<< v8
Combine 47 and
48
then get that
(10ing (
P
uun
U
n
- Oinzy | V8) (vv5)) )
JEsA shi (mr) 1
1521
n(
(n 10 0ūnl < v8) )) = 1.
U
)e.Re
1m1
So
[oll<vo V8 ( (1emm 0% < v8)
P
n |00m -e,,1I<<
11 0m, - -0% < <5²) vo))
=1
26

---

Published as a conference paper at ICLR 2022
Thus it holds that
nu (10:-00]1 vo U 0n 0/1l s s38)) (3v8)
1=11,22
nu (100- -;,1| = v8) U (l0) 1;'l = v8) n (10) (555
P
n (100 om v88) U (10m 0 < vō)
n 0m, 0mg <v8)
v8)
This means we can find two "same" convergent subsequences (0.,) and { with probability one. Because a closed set and {0 C J, we know that there exists 0" J such that
lim Og = +00aa a.s.
(50)
This indicates that we can find an accumlative point {0,} in J with probability one. Denote the connected component containing 0" by J"
Step 3 is to prove that there is connected component J' of J such that 0, 1" a.s. From equa- tion 50 we have
+os +
0 001 - =1.
Since g(0) is continuous, we have
400
nun (c(0m)-g(00))) 55) n=
P
Since {g(0,)) converges a.s., let M be the limit, i.e., lim ((0,) = M a.s. Hence g(e") M, and g(0) for all J Define (0lg(0) M). From g(0.) - M a.s. and the continuity of g()). it holds that O, - A a.s. Obviously, J' C A. J" A, then the conclusion follows. Now assume J" Ç A. From the definition J", follows that there are two disjoint open sets V and H such that A C HUV, J' CV, A/J" C H, H nv' = (H1' and v' are closures of // and V). So we just need to prove that 6, + V a.s. A contradiction argument is be used. Suppose that (0,) has accumulation points in V and И simultaneously with a probability larger than zero. That is,
P (NU #=1 D
+00
( E EH)
+o0 + (NU ( (n(e)))))) 0. ==
+30
(Un (
(51)
Expanding equation 51 we get
too U ((EE))(())E)) = (
P
> 00.
r=1
12m.f2
Note that the event
(()E))
n
U
(ma))eNx NxN izm.zzn
can be written as
((ea (Ba vV) E (H) EH)
U
n
27

---

Published as a conference paper at ICLR 2022
where { n (Bi) = 0. The event
((OEEN())EE)) U
) ( EHU))
(52)
(
means Vr 2 O must belong to one of H and V. So U(B) must include the set fr, 1, }. Denote { and {Bi} as {a." and ( }. and then equation 52 can be written as
U
n ( (
1 E EH)
(a Je JEss
So we get
n (( (V) EH)) 0.
(53)
r=1 taf )ipk
follows from v' n' 0 that
inf @
|0(0) 0(2) 0,
(54)
where is constant. By Lemma
it holds that Vs 0
nuIn #=
On 0mtil 11 25 =0.
(55)
Now we consider {a=" + 1]. In fact, {at") + 13 and { have finite number of identical elements with probability one. If not, then
400 4.00
in Em))
UUE
(0 (0 EV) a
n= mmn
By equation 54 follows that
p0 0m+1l 2s
R= mnn
+00 4.00
>
1 (c)
25
Om
+1
== m=n
>P
4:00
0 Cm
EV)
EV)
E {11) 0. a
R=
Immn
which however contradicts with equation
55
Hence {ap" + 1} and {B.") have a finite number of
identical elements with probability one. From { {a. FU(B S 1,r++ 2,.., we know that
+o0 +.00
UN #=lm=n
(P) +1) E (a =1.
(56)
Hence { is finite sequence with probability one, otherwise it contradicts with equation 53 Thus, the assumption does not hold, and 6, - V a.s. Furthermore, 6, J". Therefore, there 18 connected component J' of J such that
lim d(O,,, O. n=400
28

---

Published as a conference paper at ICLR 2022
B.9 PROOF OF THEOREM 1
First of all we aim to prove that g( (0++) is convergent almost surely. parts follows.
Divide equation
into four
a" Vo,8(01) v + 1 1-a
α²
g g(0+t)) = =((())
Ei (IV
1 - a
(A)
a= r+1
& (as(e))Vas()),.))
Σ
(0,,)(0)) vas(O)) (0-11-0 -0)
(57)
(C)
1+1
(Veg(()) Ve v-11
α
Due to a < 1, a is tending to zero, which ensures the convergence of part (A). For (C), we consider the absolute value of Dm It follows from Assumption 3) that
Σ
V og 8(0g) vas(()) (0.1 0,)
V og ((0g)) Vas(O))) (0.+1 - 0.)
m
Σ eg 8(0g) vas(O,) || _
Σ
2
Through Lemma 7 we get Dm 11 a.s., leading
Σ
V o. 8(0g))))))))))0
vos(O))) (0.-1 - 0.) a.s.
Through Cauchy's y test for convergence, we know that (C) is convergent almost surely. By using the same function, it holds that (D) is convergent almost surely. For (B), we have
α
1+1 & Ves((()) (V.
(B)
1=1
(58)
a" n-1+1
"-1+1 VVag(())) (Vag(0. ( -Vas(e))
Σ
Σ
From Lemma
it follows that (C) is convergent almost surely. For (B), it holds that
-+1
(B)
& V.g((e))
T Vo. 5
/=1 a
(59)
--++1
--a-++1
Σ
V
(
Σ
VVg(())((vux(e..) -Vag(())))
By Lemma
we know
1+11 1+1
Σ
& Vog((())) too a.s..
a
From Lemmas 5 and & it follows that
a=
Σ
a B++ VV Veg(())
is convergent a.s. Thus (B) is convergent a.s., and g( ((+1) is convergent a.s. Substituting equa-
tion 59 into equation (7 leads
e(0,+1) < 5- Σ vag(e))
29

---

Published as a conference paper at ICLR 2022
where { is defined follows
a
--
Si =0())
Ve, (())(())))) ) v1
1-a (0
1
Σ
α n-1+
& (e)s(()) (Vas(0,,5) (Ves(0 -vas(0)) + Σ (o.,((=)-Vas(()) vas(o)) (0++1 - 0,)
a
a [-] a (V v
we know (5n) is convergent a.s. It follows from Lemma 9 that there exists a connected component Jd of J such that lim d( (n,
B.10 PROOF OF THEORRM
First of all get that
[-1 = -- -o,8--vo, Σ a (Veg(())- (101))-Vo,,8(0 ((0
(60)
vas(()) T (0,+1 -,))
+ Σ a V ( (o +
From Theorem I it follows that g(O,) is convergent a.s., and orbitally convergent to gi (i = 1,2.....NN a.s.. Then it holds that
lim g( (p)) Σ 1g: a.s., n-2
where
lim g(0)) = gg
lim g(,) * gi
For convenient, we let g" = -i 188
Then we make some transformation on equation 60
(g(0++)) -8") (8(0,) - 8*) = -aaat
Vo,8(0)) -a-
+ Σ av
a & V, Vo.(( + (Ve, -ve (0,11 -
vas(e))) -
(61)
Then we make some transformations, take absolute values, take the mathematical expectation, and use same techniques in Theorem Since the sampling noise follows a uniform distribution, there is
E(I[V 0,8 02, 32) < M M v (),))... So it follows that F F/ S Pa-1 2 where Pa Pa-1- Qn-1. and F² are defined as follows
1
n-1
1
n-1
P 1 (2 - x)
E E (( + +Z(1L
IE (g(O1)
(1 ay
α
2 α
I(n + I) (v, + ca a)
- 2(1-a)(1 - σ 2(1) (11,ol?3,
1 1-a
(62)
F Σ
1
R-f
Z(1 1)B (g)))((0++))) =8)):
2
1=1
1
m-
Q
Σ
& E ([
(1 0)
2
1=1
where g" = >inf g(0). Then have
Qn-1 n-1
F"
<
|
F + P
(63)
30

---

Published as a conference paper at ICLR 2022
Derive Qn/Ent1 as follows
Qn
E )
-+
Ex+1 E (1 8 (3)
E Fy
(1
a)²
Σ "Z(++
E
(!"] [ 0.+ - 8*1) "E (1V B 88 ((++1))12)
1
2-a
E B V
[ (1))
(1-0)²
E 2-a
1)2 1)
((((+++))) (r+1) (c
(n)
88)
It follows that
liminf Qr
n n- Ext1 Fr
E [i 8 8( )1))) -- I-
E (1IV 8 (0++))ll))
in (1 a)2 n00
E
Z((t + 1) e (((++))))))))) - 8*)
(64)
2-
4E=1
E 0 ((
liminf
2-a
(1 022
"2(1 + 1)
- g( (1+1) -1-+))---))
2-
From equation 32 we have
(n)
1+ 208 fn -1)
9+1
a al-ò(1 a²)
2ce,
Σ (a(2 a))* a nn
Σ (2 =)))*
(65)
= =1 al 8 x8))
$ + Ca
where Ca
2 [1 a (22-a))
Substituting equation 65 into equation 64 yields
lim Qa F
1E (VVVV ((++1))12))
(66)
2-
2 (1 a)-
liminf
E
Z(1 + 1) E c+1 g((++))) -8'))
2-
Then proceed
with the proof
under
different
cases,
namely,
EL (+L E (II V g( (0+1))12)) too and Σ
(x-a) -
(I ((+++))ll)) t00.
First, if ". 1 ( ( " E (IIV g (1)) oo (the proof for this condition is up equation 76 It follows from Assumption 2) and the uniform convergence and O' stolz theorem that
lim Qn
B-000000
Ent1 FM
E
E 8, 8(0++1)112)
liminf
1-a
(1 ax2
E 2-
"Z(1 + 1) T) (1 + Cati) (8( (((++))) 8*1) -8
(67)
E 8 (0p 1)12
liminf
a)²
0-2+00
Z(n 1)
(1+ Ca&) |g( 2((/+1)= -8
liminf
(1 a2 0
Z(n 1) + Caen)
p(1 aa2²
31

---

Published as a conference paper at ICLR 2022
{
where p= -
exp exp
-x= M
By using O'stolz theorem on Qn/ follows that
2x
1
Σ
+ IE (IIV 8 ((++1)]
lim
lim
2-
n 4-++
(1 0:)
110000
21=1
"A(1 + E
6 ( (++1) 8'))
2-
1
E I=-a
e++ E. (1 8 e 8( (1=-)
$ (1-x)2 #-00000
lim
E 2-a
111 + 1) E (((+)) s"
1 lim
E,, LE (IIV 0,8 (,))1²))
(1 - x)2 n n
Z(n + 1) 18 g 0p+ g*
1
re, E2 (g( Oz++) 8")
$ (1 - a) n . Z(n + 1) EE gg( (0+1) - 8"1
lim
0.
So we conclude that 3oo E N4, such that Vn 2 n1..
Qn
3 0
(68)
F
222 d)
From equation 63 it follows that
Qi
F
F
Σ
1
P-
(69)
F
im
1=1
Using the inequality In(1 I +x) S and equation
67
we get
Qi F?
exp
Σ
In
1
exp
Σ
ke
p(l-a)
F
F
i=
(70)
=0
2i-1 p()
ay
where & is a constant. It follows that
(1
2:
P--1
-=
p
P-
(71)
Q: py
F(
[1
0 p
no
11
From equation 62 we have
1-1
1
1-1
P7 (1 x)² 2-a
E ([ +Z(1)
E Eg((1))
2-
(72)
cα a (2 x)
1-1
+ 2(1 a1 σ²)
Z(I)E (1v0113) 0 122-2200 0
+ gax"
where p= = [1- [ & E (())(())))))) + Z(ILLE (g))) and q =
2(1- ) Z(1) EE (11oo11)) Sub-
ca (2-a)
stituting equation
72 into equation 71 and noting equation 68 yield
E--1
0 F
Ph-1
11
0 p?
FF
1-1
P.-1
qot"
Σ
Q
0
(1
Q F
1=
F
1=
(73)
P( 1
1-1
qo--1
2-
3-
1-m0
3-a 1-mm
f= 11
2(2-a)
2(2-a)
3 0
np-1
2 1-1
2(2 22(2-))
a))
(x+
Σ
< CO
3 - a
R=
+1
32

---

Published as a conference paper at ICLR 2022
where co is positive constant. It follows that
E
I
2 co 1-
P.
n-1
N
1
2
F
I Fi
1
Q F
Fi
o(e
Σ
p(
spp
(74)
Combine equation 69
equation
and equation
74 then get
Q Fl
n=1
n-1
Qi F/
P- = -
Σ
12
1
1
p(t p(--aj²
(75)
1= +1
In addition, we have
E (g(0+=1) -8') g")
Fr 0(e
Li a-t
(76)
If Σ" (2aa)
E (1IV a 8( 8(0++))113) too, holds that
1
lim
E (1IV G 8 (0++ (0++1)12
2
that is
E ( ([lIVe,,) 8 ((0x+)))))++))) =0
2 (=(())))))))()222
Under 4))umption we have
E (g(0r+1)= 8*)
Vo 1 1 ((B+1)
1 E
(1)
In+ 1a+1) 0.
limsup 110000000
limsup n-++
1=-a)"
5 s(2-a)
2-a
follows that
E (( -8" --01=
2-x)
E
Now compare
22-a with
x0-077
It holds that
(z-a)" exp (- Σ 36
"
exp exp(-n0 (opnn2n oz)
exp Σ
SE;
nnnn -a) a1)
exp Σ
S6
p(1 a)2
p(1-a)²
1-1
It follows from Assumption that En + O. indicating Σ sufficiently large. Thus, we have
S6 p(1
nln(2 a.) < 0 when is
(z-a)" no+ exp( Σ" p(1-a}
limsup
limsupexp
Σ
SE;
nlnn22 (ln(2-c)) 01) <1.
+
p(1 0.2
Then it holds that
0g())))) - 8" = 8=1=0
= (
p(l-a²²
52
(77)
Combining equation 77 and equation 76 leads to
(l((0.+)) - 8"1 = 0 Σ" p(l
R
E 9. 8 1(
+00. The above bound holds trivially
2-a
E
(++1)) too, It follows from Lemma that
=(
Σ pll
E
33

---

Published as a conference paper at ICLR 2022
C CONVERGENCE OF ADAGRAD
The following lemmas are used for the proof of Theorem
Lemma 10 Suppose f(x) E C²
(x E IR") with f(x) and its gradient satisfying the following
Lipschitz condition
[V vs(i|| 1 <c||x->|]]
then V xg E IR", there is
| s (x( -f)
where f inffe R fxx)
Lemma 11 Suppose {0r} is sequence generated by AdaGrad in equation 5 and Assumptions
and hold. If V > a where a given in Assumption 3), then for any n E N4. 0 R
and & 20, it holds that
8(0++1)
g(Om)
V e
8
((p=1))1
V Ve,)(0n)) 1
(M
11)
S
5i+2
S -
do
Ve.g(0n)
0g
V e
8( 11-1)
Vo,s(0,))1
20
S te
20
+e 2
$ +
V
(00-1, 1)
cOp
Vo, (0,, 5u) 11
+ 4M ag 2
+ +x((1
+ +r
S
4-1
where
(())
0g
Va,g (0,) (V Ve, 5n)
2
S
+e
n-1
E Vo. On (n, (m))
(e)
1
V ve 5,)
M +1
st -
M+1
s te
Lemma Suppose {0,) sequence generated by AdaGrad in equation and Assumptions
and S hold. If V
a, s0,((0 {()) < where a is given in Assumption
3). then for any E N,. 0 R.N,
and E E 4), it holds that
8(0,-1)
g(0,)
Va, 0 ((,)
2f +
Vo._, 8( Q(0,-1,,5 5m-1)
11+1
S
20S +R
2
(M + 1)
V Ve, 10,00000,5--00 50 50-1))1++
Uo
[ 88 (g (0n-1)11
Vo..s( Om)) 2
25-+ +e
20
52 tc n-2
s +e
n-1
Olo (M 1)
V 0 18 (0,-)))))))))))) 1)|1
V Ve.g(O.)
Onaa M + 1)
$2
S +e
2
$2 カ-1
S
4-1
cog
Vo.g( On En)11
+A
B!
2
s1+e
where
(e)
|| - - Vo. Em)
Og
A
2
+e
n-
dol
V 11,
| -E (10a[_(((eeee)]]((]_).]))
Bi
2a(M + 1)52 +8 n-1
34

---

Published as a conference paper at ICLR 2022
Lemma 13 Suppose {0,} is sequence generated by AdaGrad in equation 5 and Assumptions and 5 hold. Then Vn N,, 4Oi RNN Ve (0, 2). holds that
(o)((1))
< +o0 a.s..
Lemma Suppose }0,} is sequence generated by AdaGrad in equation and Assumptions and hold. Then Vn N4 V0, E ER" E (0, 3 +00, it holds that
g( p g"
5 4.00 a.s.,
S
which g" = =inf BERN (0).
Lemma Suppose { sequence generated by AdaGrad equation subject to Sn
Ei=1 [V Vo,g(e, 5x]1 too a.s. Under Assumptions and Vn N A0, R
VEo E (0, g).
holds that
0 a.s.
50
Lemma 16 Suppose that {Xn} RN is vector sequence and f(x) E C¹ monotonically non- increasing non-negative function with fT= f(x)dx < sa (Va 0). Then VN E N4,, holds that
1X
X 1
Σ |X
f(x)dx <
Σ
X 1 Σ [xx|1p)
C.I PROOF OUTLINE OF THEOREM
Like the proof of mSGD, the proof for AdaGrad is also in light the Lyapumov method. We aim to prove Vg(O,)) -> 0 a.s., and then get J' The key step prove convergence of AdaGrad to show
Oi V Vo,g(On On 5.) T V ((0 5m)
Fn
VSn
but the learning rate of AdaGrad is random variable and it is not conditionally independent of V Vo,g(0, 5,), meaning that
ao Vo O,,, & V
(0,
5x)
Fr
#
d
Vo, 0. Sn
V
Vnn
In the following, we provide the proof outline Theorem 3. Step 1: This step is to ensure
C4
Va On 5.,)
Vo, (0, 5m)
Fn 50.
VSn
We are able to obtain the following equation
Va,g( On "V (o,)((n))
Ve,g 0 5x)
VM 8, (0,)
VSn
2n5
VM
(K)
M ++1 1
Ve, Ve.)((e))1
Va,s 0r Ex
2(M + 1) SS
(L)
35

---

Published as a conference paper at ICLR 2022
For (K), due to Sn-1 Sn, it follows that
(K) =
(n, 5x) - -V e (On)
2n5,n
M +1
a On 5m) - v M IV n On))
2
M +1
(0, 5n), thus holds that Note that Sn-1 is conditional independent on Ve,
E
& On 5m) A Fn
V
M +
2 VS M+1 (I (.) + (M 1M-11 1) Vo,
Next we prove (K) can be controlled by (L) according to Lemmas 11 deal with the cases of [Va,((,))
and 12 These two lemmas
and [|Va, a, ((,,)] a, respectively. In these two lemmas,
introduce a constant e for the reason as stated in Step in the following.
Step 2: Through Lemmas
11 and 12 obtain that
Σ [V(s(0)))// < < Σ (V
13 stating that Σx V 0g 12)1 +2e < 4o0, Note that if 42e will become I (2. we do not introduce E, the term س (Lg(OL, 5)11//// S,,,,, and this term may not be bounded.
From Lemma 16 we obtain Lemma
Step 3: Lemma 13 ensures that Ve,z(O,) 0m) has subsequence satisfying Ve,, Ve,,g(00 ((0,) a.s. By using the recursion formula g( g(0x+1) - g(0,) S 1/SS, + Pu. where E Pr < too a.s., and Lemma 4 we obtain V 7a,8(0) (,)) + 0 a.s. Consequently, 6 J"
C.2 PROOF OF LEMMA 10
For vx E RRW, we define function
-
8(t) = x+1 ||x' - xx|
where x' is a constant point such that - is parallel to fx(x). By taking the derivative, we obtain
x
g'(r) d'z xx+r x'-x x'-x | -x1'
(78)
x+
Through the Lipschitz condition of fx(x), we get Vt,, 12
x )
x-x ))
x-x
(1) - -800-8(1)) 81((2)
d-z f x+1
-- v
f
xx+2 T|xt - x1|
x+1
[x
|/ - x||
x+2 ||:
|x-
x
-
x-x
<
x
1
x+1
x
1xx
x
|x--x||
S c/ls - 12/.
So g' (1) satisfies the Lipschitz condition, and we have i(f) 2 inf f(x) > -c, Let g"
infx (xg(x), then it holds that for V to E IR,
8(0) -g' 2 -(0))
(79)
By using the Newton-Leibniz's 's formula, we get that
8(0))g(to) = [- g((a)da= = 1 (g((a) (c(a)-8((0)) 8((0)) ff ('(d)da.
to
36

---

Published as a conference paper at ICLR 2022
Through the Lipschitz condition of g', get that
g(0) -0(0)) z -cla 0lda+ S." g' g((O)da (g' (g))
2c
Then we take a special value of t0. Let In -g g (0)/c, then we get
8(0) g(to) 2 1 2c (8'(0))
( caadda+
g(0)dr - (0- (00))
(80)
(x')))
1
(8))
2c
Substituting equation
80 into equation
79
we get
g(0) g (g (0))
2c
Due to 2f and (g'(0)) [[V it follows that
| (c(
C.3 PROOF OF LEMMA
First of all, it follows from Lemma that
ca. V
Ve,8( On, 5m)
8(0++1)-g(0)) - g((), S (0,t1 0,)
2
Sn
(81)
a Vo, 0n)) Ve,,)(V,,n (n, 5x)
cap
Ve,g( 0, (e, 5.)11
+
SSn
2
Sn
where
S, Σ
V e (0, 5
Note that
V (0,8(0n.5)) 5n) W &()))
M
(82)
M Vo,g( 0z, =0) +
(M 1> o. -V,, Vo,g((,, 5n),
where M M 2 and M' is defined in Assumption 3). Substitute equation 82 into equation 81 then we get that
8( 0 8(0))
Vo, 0,, E.)11
V V(,)(0m))) 2 SSn
0g
(M 11+1)
2
M
VS,
(83)
0g 1 +
/M 1V 0 (0,,) || [0.)|/+
caf
Ve, [n)
Ve, 5m)
2 VS, VM+1
2
Sn
Due to S, 2 S, 1, it follows that
0k
V (0, 5n) VM 1V 8 (0.)
2 v S
(84)
< 0g
1
Va,s(O,. En) M - 1V
2
37

---

Published as a conference paper at ICLR 2022
Substitute equation 84
into equation 83
then we have
g( ((++)) g(0,)
Ve,. ( Ony 5.)11
V Ve,g( On)
S dg
+ (M+ 1)
M +1
Sn
SSn
(85)
Va,8 On 5n) - V a. (h)) 1||
cap
V o (0, 51
+
VSn=i
VM
Sp
Notice that
dg
0 (0. 5n) V + IV 0. (B.)
2
S
VM
0p
Vo,g( On 51 (M ((. -20 2Vag((On: Vo Ve.8((n))
2
v
S
+
(86)
do
1
Ve,g(O, 5. (M + V) - -2
2
VS
M+1
06
Va,g( ((,) 0,))
(Ve,g(O,)
Ve,g (0, 5.)
Substitute equation 86
into equation 85 and divide both sides of the inequality by S (E < 4), then
we get
8( (0+1))
8(0m)
S
St
C6
1
V On |
(0,))
+ (M
2
1
S +
S
06)
1
Vo. V 0n))1
Vo,8(On On
a,
2
M
1-1
+
cap
V s, (0,
On. {
d6
Vo,s(0,)) (Ve.s(()) Va. 5n
2
S
+
$7-1
Notice that 8(0,1)
x(0,11) S
then obtain
3
8( ((0m
8(0,)
55
1
S
0g
1
Vo,g( O, |
+ (M + (Vo,((.)))
2
M 1
S +e
S +e
(87)
0
Vo,g On, En)]1² + (MM Vo.g (0 (0,)]] -
+
2
M +
1-1
+
cop
V g 0,, 5.
ao
V
Ve,
2
5
38

---

Published as a conference paper at ICLR 2022
Rearrange the above inequality, then it holds that
8(0++))
g( (0,)
S
V (0,)1
do
(M + 1)
2
S +e
00
V Ve,g( On I1
(M 1) (o,)((0n)1
cap
V Ve,g( Op 5n)1 x/
2
M ++1
S +E
$ +e
2
Sg
n-1
(88)
|| fn (g ((0 ST
(V
do 2
(M +1)
S +e
Ve.g( On. | ++
(M 1) V 0.g e.)
(M + 1)
e 8 On-1)]l
+
2
M
+c
+
n-
s
n-1
o On: 5in) 1
caj.
x(())
2
[e) is defined as follow
do
X
Va, Verg(On)) (Ve, V Ve,g(Gn 5n)
Due to || ([e))((,))12> we have
Ve,,((Gn Gr, Sn s.))1p((m.1))))
[ +a
(89)
< (M (M Ve.g ((,,) (2)
Moreover, using the Taylor formula, obtain
Vo. |I] =
V 8( 1
1) + (V,, Vo, 1))
Va, ((0 . |) +V
02 ( (V,,8(0,) 18.,1((mm1)
V 0,)) V e, 8( Gg ||||
V 1 8( ( 1)12
(0,0 - V 8.8 0m)
+ +
V e 8 1 - -
Under Assumption 5 we get that
|V (m))
Ve,
+2 V 0 8 G ||1| (0,((,)) - Ve,- "e,,,8((,,-))) 8(0.-1) Vo. 11 -ve.
V 8 .0- 11= 200ic
(90)
VSn-1
+ Ve,,,
(((0 1g 1. 5
Sn-1
From inequality 2a < 2 |||a||2 111b112
(2 > 0), it follows that
(M (M--1) (M-1) Ve,g( ( km) |2 Ve,g(0,))
< (M (M Ve,,
8 0
M
V V (0,)ll + 4N22a3c2
V Ven_1 (0.
(91)
4M
Sn-1
By substituting equation
89 into equation
91 we have
(M (M-1) Ve.
E 0, ((, 5.) F-.1)
M +
(92)
// 10
< (M + Vo, 8(0,,)
M 1
Vo,g(
4M2 o222 0.)11 Vo,)(()))l'"
4M -
Sn-1
39

---

Published as a conference paper at ICLR 2022
+e
Divide both sides of equation 92 by Sn-1
and notice -
from M > 2, then it holds that
V On 5m)
V (A,8(O))l' +
M
$ n-
-- 1)
V Voa-18 g( O
V V (a)))))]l= +4M22
1 10p-11:5
(93)
(M + 1)
Sp-1
5 11
2
+
Co
where
E (
e, On (n,,
V 0 (0: )
(e))
0g
2
M +1
5
M +
+e
Making some simple transformations on equation 93
leads to
+e 51]1 (e,
(M 1) V o, (0,)l
(M 1)/l Vo, 9,11 Og 1|
do
2
M
+
S +e
s +
1-1
(94)
ag
V o Ol
4M aj.
Vo, 8 0 1,
1)1
10
$2 + 1-1
5 te
R-1
Substitute equation 94 into equation 88 then we get
g( ((+1))
8(0,)
5E
$
1+1
Ve, v g Gg 1]
V (0,)
0g 2
<
M + 1)
S2ze te n-1
S +E
(95)
dg
Vo,8(00 ((,))l
+ 4M asic
V B
8( G 1, 5mm 111
caß
||
V aa On, En) 2
+
10
$2 +e
5 +8
2
S!+E
--1
x
+ (e)
follows that
Ve, (e.)(0.))12
V Ve,g(0.))
V e 0w)l
Oli
10
S
20
SI+C +
St
20
S te
| 0, 1,)1
V 90,,118 g (0, (0,11)12
|| N 0 0.)1
0i
do
20
$ +E n-1
20
S +e
+
R-2
(96)
V e
8( 1n11
0g
20
5 R-2
06
| 0 0l)
do
V
19,118(
(2-1))1
Vo,g( 0.)1
<
+
20
S n-1
20
+t
s2 +e
R-
#-1
40

---

Published as a conference paper at ICLR 2022
Substituting equation 96 into equation 95 yields
g( 2(0++1)
g(0))
a+1
S
Vo, 10--188 8(0 11-1))
Ve, (m)) (n)
(M 1)
S
S +e
04
Vong (n)) [m))
Cg
Vg V 88 10 1)
((,))(0,)1
(97)
20
S the
20
$
+
$ +e
2
V Vo
1:-1:56 1: 1-1)) ||
cap
V Vo,g ( On 11
+ 4M2 agj
+ x
+ v
2
S +
C.4 PROOF OF LEMMA 12
First of all, dividing both sides of equation 81 by S yields
8( 8(Om-1) g(0,)
04 V V (0, (,)) VV, V
(0,.((n..)) On: 50)
caß || Ve, (m))))))))
+
(98)
S
S
S
Due to Su+1 2 S.. it holds that
g( 0
g(O,)
C6 (,,)(())))) V On (nn
caf V a On, 5x)
<
+
(99)
SE 1+
S
S +e
2
Then we make some transformations to obtain that
Vo, (..((O))vv. V On, 5m)
S +
46
DeV,(((,)) 0
V On. 5n)
( 5m)
S
stite
S +e
n-1
dg V 0 0, ) V 0 Gn 5m)
(M+ 1)a
1
V (o..( E,))
<
+00
2
2 + l)a
$
S
4g)
Va,g( 1l.
(M 1)asa
2
5
SĀ
+
06
| (v.g(()))
((V En)1 (11((_mm1)) (1
+A
(e)
+ +B
2a + 1)
5²
(100)
where
(e)
dg ( (aa.:ealllVve.e...ovvv....
Vo,
(101)
((e) un Ve, e, g0,))
1 +e (1Vo,8((.. (10))=((((a((0.66))()0))1) 2a(M + 1)52
Due to | VV,)((0)))
< a, weget
E V...g(Oe (0, [m)1 (
s SM (a. (M+1)c
(102)
41

---

Published as a conference paper at ICLR 2022
Substitute it into equation 100
then get
s(O,+1)
g(Om)
04)
Vo,8( Ow)
Chea +1)
ST
S
$ +e
2
S te
S
V 1m)
cap
V Ve,g( (e, On 10)1
+A,
Bi
25 n-1
2
Sh c1+e
(103)
Va, 1m 04
Cha(M +1)
25 +2
2
S2 +e
Sh +
+ cap || Ve.g On, 11
(e)
Bn
S
0o Vo,,(0.))
We make some transformations on
to obtain that
25
Vo,
- 0o VolVoon
e (e))((n))1
V
25
1 te n-1
205 +
205
n-
(104)
V (0,)((0))
[1
0g
V e 8 0 1111)
d
| (00_-1(00n1))) (1
Vo,8 Ve,,((.)))
20S x-1
20
S n-2
20
5 n2-2
5
Then we use inequality 2 < 2/|a||2 + 1b1l2 (A > 0) on equation 90 to get
Vo._ 8 1)l?
Ve, 8(0
10(M +1)
(105)
10apc((++))
afe² S
V e
8( Oz
1m-
S
105 by S +
Divide both sides of equation
5-1 and notice Sp-2 S S S Sn, then we have
Ve,g(0.)1
V 9, g Pg I?
Ve, 2 1)l?
S +
+
M +
105 +E R-2
n-1
(106)
100fe 2 (M +
V e
8( 10
1)]
V Vo,_ 8.0011.1111111
sI+E
52
Then we calculate 4
da (M + Jequation
106
equation 104
a
(a,8((,)))
c6(M+1
(V,g( (w)) 1
e, 8( 0m- 1)12
2
2
52 +e
< dg Ve,g((n)) 0b)
V e
8( @0
1,55 5m--1/ 1]
+5 C +1+1)2
1)2
205 +e
51+e
n-1
(M + 1)
Ve, 10,_18( ( 1)
V a (g,) (l)
Ve V
do
252+ +t
20
S $2 +
52 +8
4-1
42

---

Published as a conference paper at ICLR 2022
||
| 18(0,-1) |||
(g(M+1) 2
Move
the right-hand side of the above inequality, then
have
06
V 0.)
00 coll o. (
V
10-18 (0-18 511
+ +5
2 te
205 +e 1-1
sl+e
n-1
(M + 1)
V (1) do
|
18 10000 10
Ve,8 0.))
(107)
2 +
20
S +e
S +
Cl aM 11)
(2(00-1)
Ve,g 0n)l12)
2
$
S
-
Substitute equation 107
into equation 103
then we have
g (0++))
g(On)
ST.
S
$ dol Va,8(0n)) (B))l
180-188(0-11)) 1: (. 111
+ 2 1)2
51+8 4-1
205 カ-1
(M (M+ + 1)
0o
Vo 8(0 8(02-1)11
Vo,8(0,)) 1
Ve, (.
(108)
25 +e
n-1
20
S
$
a6 (M +
Ve, ((0
Ve. 2
(ga(M 1
te
S
S
S
caf
| Vo,g( On, 5m)) 1|
A +B
S)+t
C.5 PROOF OF LEMMA 13
First of all, holds that
(0+1)
g(O,)
5
S
#+1
= =I(( sa)
g((,+1)
3(On)
+
+1 +1
>a) .)(
( (8((++1)
g(0,)
Se
ST
R++
S5
(1Vo,8(0.))) sa) E &. the indicator function such that
{
V Vo,g((n))l <a
(11Va. sa) =
0
|[,,s(0,)) >a
For convenient, we abbreviate I( ([oo as _ and (n following.
(0,)) > a) as I.a in the
43

---

Published as a conference paper at ICLR 2022
Through Lemma
12 get that
0(0+1))
g(On)
Sp+1
S
$ - 0o|
V e, [e,)]
V 1 00-00-1150 (0-0-115-111) 1))1
+ 5
205 c カ-1
51+8
(M + 1)
V 0 8( On 000m1))1
Vo,5((0))
+ 1/
[Ve,-18(0pp))) 01-15100-
1
25 +e
20
5
a-1
aM(M + 1)
Ve 0 8 (0p (0n-1)11
Ve. (o,) (x)
Cha(M + 1)
n-1
+ (E)
S
2
S
1
co 1
V V (
On 5m)
12
B
+1,
S
(109)
Through Lemma
we get 8(On) 5e
8800 ((00+))
S V Vor8( 0,, V0,)(0,))'' ||
S 12a Uo 20
Co 1,20
V Von-11((0n11
Ve,g( Ox)) (b)
$2
1+8
S +
| 4--
+ dg
(110)
20
$2 +e
V e 8( 0 1), 1.5-1111 112
cop p2a
Va.g O,, 5.) 1|
V
4M2 a2 2pp
$ +E
R-1
-
Calculate equation ion T09
+ equation
TTO
then holds that
8(0m+1)
8(On)
[(0++))
8(Ow) Ow)
Sa n
+ 1,20
S
SE
S
| 70p-188
((O--))l'
V Ve, Om)) 12 s
(4
(1 + 1,00
20
5 +
V 1e,,118
8( 2(Op 1011
Ve,g (,)) 2
do (M + 1) + +1200
+ 2
$ te
1 +
S
0o
(155 + +1200)
Ve, (en))(
+ 4M² az 2
e, & Og 1), 5.
2
20
5 +e
(111)
1-1
#-1
co2 12a
V V 0n, 51
V o, 8 0 1. 5 1)1
+
2
1
2
S1+t
sI+e
(M + 1)
+
15
V Ve, Or 1,
S
25
4-1
Cia Coa(M M +
1
cap
(e, 1,) s!+e
+
p
2
1 +e
L+t
2
5
S
nー
+ 1 All
+ +
(e)
12 Xn
(E)
+ 12
44

---

Published as a conference paper at ICLR 2022
Notice 1 S then get
dga M 1)
dga(M +1)
1
(112)
8 g2
Sñ
2
S te
S
+
Substitute equation
II2
into equation
then we get
g( ((0+1)
g(O,)
S 1++1
S
dg
Ve 0 8( e
||
V v ((,)(0n)|1 (1
20
S 11-
S $11
Oo 2
Ve, 1
V 0.) 8 p 1|
(M +
5i+e R-1
S
do [o,8(0n) 12
V 00-11 g 0
1). 1):5)) 51-1 1|
cog p2a
V Vo,3(0. On |
4M agj 2
20
+2
+2
S s1+e
nー
| 0n-1, 8000-1
(M 1)gee²
2
1)2
+ +1 -
V 1e. (0
25
n-1
Aha M +1)
+ coL
S
V 0 On 5n)
S5a All) + -1
+ 1,2 x1xxx (0)
2
S +
+E
S
4-1
+ +12
(113)
We make a summation of equation 113 to get
& ((0x.))
g( (x)
S
S+1
Yo 8 0g 11
00
20
3m3
$
++
521 +
40
n + 1)
Vo 8 0g 1)12
|/
1Vog(( 0+)
+
(M
Σ
2
$2 te
S
vo18(00)1
Vo
0
1) E1
+ 4M afi Σ
12
20
+
k-1
(114)
cO
Vag(O, E211
1
p.
2 1)2
2
k=3
(M + 1)az
Σ
1
| 0
1 +e
3
25
Chal (ha(M= (M + 1)
1
cof
V 0 (0, [
+
2
$111
+
S
+8
k=
s +
Σ
" + +
+ 1, x
(e)
+ 1 (aa((())
3
follows from Lemma 16 that
Vo 0g E2)1
dx
(115)
s
x1+e
ESE
45

---

Published as a conference paper at ICLR 2022
and
Vo 0.
t
dx
(116)
1
S2
x1+e
ES
and
V 8 8 Ok
1.
Se 1)ll
+00
2
dx
(117)
S +e
-11
82
(1+2E)S²
Due to 1.d < 1 and 1aa0 S 1,
we get that
n
Vo f:
11
cob a
Vel8(1x: 5x)1
4M² ag
0
+
$7 +t
2
1-1
k=
Vo 8 (1-
+ +5ahe² 2 + 1)²
sl+c k-1
(118)
(M + 1) 1)
co
V 8 (0--0 5(-1)) 1)|
50
25 tt
2
$
k-1
8M & of
copy
sahe² (M + 1)2
og (M +1)
cop
K.
(1 + 25
+8
2c5
E
(1 (1+28) 2
2E5
Substituting equation
118
into equation 114 leads
g(0,+1)
8(s))
S411
%
Vooa{(>))1
Vo..(0.))1
Co + 2
Voig(0>)
Ve. o,))
(M +1)
20
s SE
$2
$2
S +e
(V0,(00 12)
Cna(M 11)
1
1
+ K
20
$211
2
S
Sh
+e
+1x
Faa Bk
+12
+
x(e)
+ y(ay(
It is obvious that
V 8 0b)1
Vo.,(0.))1
(oog(02))
Ve,g 0m)
Co (M (M+1)
+
20
S S7+C
2
S t
S +e
Vo.g( 02)) ||
V Vo.g 02) 12
dga(M 1)
1
co
C6o (M(M+1)
+
K
<
2
82 +E
S +
20
$ +
S
apaa (M 11)
+ K := I.
25 +
follows that
g( (
8(O))
SE
S
06
(ag(()))
+L+ Σ (A
"1
(e) + = +12"x + (1)
(119)
20
Note that (1.2AA2 Ag). (1 Bx). (12"X4 and (1 are all martingale difference sequences, thus
(x + 1 B3 + 12 + 2oy)) = 0. Then we calculate mathematical
follows that EL=1
46

---

Published as a conference paper at ICLR 2022
expectation equation
119
[o,g(00) 12
8(0,+1)
g(Os)
do
E
E
+L
S
5
20
$2-1
That is
Va Va.((0 \a
20
& ((O)))
+ L
< to0.
(120)
+ St-1
S
From Lemma 6 it holds that
Vo ((x)l
< +o0 a.s..
(121)
S +e
C.6
PROOF OF LEMMA 14
follows from equation
119 that
8(
((0+1))
g(0: s(0s)
+L+
Σ
1 + B1
(e)
+ + +1 (1))
(122)
Sc
S
From equation [01 we obtain
af
Σ
E
1 1 113)
- Σ
1.2
( (b,)) - Ve.g((,) (V. On 5n)
Ve,g
$l+2e
With inequality (a + b)2 2( + b²), 2a b < d² bb² (a, b> > 0) and equation 120 get
E
k
Sa
df
[[ Ve,s(0n)) e, (nn
S
11+2
0
Ve, 8(n)l
(
(==1\ +2
4 Sa Ve..e E.)) (1)
$ 2E
$1+2e
s1+26
af Vo.g(e,))''
22( + 2
afal
V 0 1l te
22M (2(++2)00 22
s $
(())) St
<0 + 2) aga
L
(123)
follows from Lemma 5 that Ei S ( is convergent a.s. Similarly, Σx 1 EaBle)
x(
and Σ 2 are both convergent a.s. It follows that
4
(e)
+1.
Ble
12 x
(e)
+ < to0 a.s.
s( 0m+1)
8(0s)
L 400 a.s.
5
For convenience, let 5 x(0,) 34
+ L 5.. Thus, holds that
g( (00+.)
5 to0 a.s.
(124)
S
47

---

Published as a conference paper at ICLR 2022
C.7 PROOF OF LEMMA 15
First of all, 0A < Eo 8 there is 0 < 30 <
From Lemma 13
it follows that
Va, g B 0n-1))1
<
to0 a.s..
(125)
300
n
It follows from equation that
(o,,(00) Ve ((00
Chic
Ve.., 8(0,,,,
VS
(126)
ofc²
S 80011
Divide both sides of equation 126 by s and notice that S, > Sn-1 > Sn-2, then we get
V Vo,)(0,)| V 8
age V V 8( 1)
Chcl V
18(0 2002-11- 5n [)]
S
n-1
$ -
$ +
(127)
af
8 00 1, 5-- 1)
+
S 188
n-
Note that 0 << e0
2. then it follows from Lemma 10 and Lemma 14 that
| 0 8 ((0-1))11
2c(8(0,-1) -x-1)) g")
<205 < +00.
5 30 n-
5300
It follows that
Vo, Vo,s(0,) 0.))
Vo,_18(0 ((0=))
Chet ageMr
2
Cdyca
+
1-1
$2 t
n-2
s
$2+300
S
S
af
Ob0
1( 5m Fn -1| - 14..18(0m111 5x-
Vo
$2 +
Sp-2 +00
Vo..1 1n
n-2
Thus, we have
V (o.)(
Vo,,, (0(0)))))
Kn
(128)
560
where
5 Chect (M +1 abcca+
agi +1)++1)
K
Chc
[F.
(IVV,,
5 t+a
$12
[E
- -1| (n
1.
R-2
It follows that
Ve, ( 5m-1 (0 1) 2_ M 8,- 1 1)-1)
> E
+
52 t00
1-2
48

---

Published as a conference paper at ICLR 2022
By Lemma 16
have that
000
Von-18
x
Oz-11
1|
E
a
S n-
Sp-1
6
1 10)
lim
E2
dx
lim
E
S
S2
n-34000
x22
n-+
2 --0 a
Due to Sn-1 - too a.s., it follows that
88 11 1
1)1l
E
to0.
(129)
S +
teo
n
From Lemma 13 we get
V e
8( Op- 00-1))11
E
+00.
(130)
m=
a
S t00
Combine equation 129
and equation 130 then
00
1:00
1(0n
1111
Σ E n=4
E
5 400
S n
R=4
n-2
(131)
M
V 0,
(
Gr 1)
4000
a
S
divergent a.s. From Lemma 13 we get that Σ 111))-113) < too and K,-1 is a martingale
difference sequence. Thus, Σx Kn-1 is convergent a.s.. Combine equation Lemma 2 then have
128 equation 13] and
Ve.g 0.))
+ 0 a.s.
(132)
c0
C.8 THE PROOF OF THEOREM 3
We consider the proof under two conditions, namely, Sn too a.s. S₁ too First, if Sr < +oo a.s., from Lemma 13 we get that We E (0, 1), it holds that
V Vo.g(0.)) 0x)11
too a.s.
$211
Thus, conclude that
V 0 (0,)
a.s..
52 +
Due to Sn-1 < 400 a.s., get
[V,,((n)]l a.s.,
(133)
49

---

Published as a conference paper at ICLR 2022
Second, S, too a.s., let -+ 0 equation 113 then it holds that
8 2(0m-1) g(0n)
V 1V 18 (00 1/-1
0g
20
VSn-2
VSn-1
V AV (0n-11800-111)
| ( 0,,) 11
do
+ 2
(M +1)
VS
VRn
aa [e,
Vo /o 8( Og 1), 5--1
[Veg(Onn 5m
4M agic
+ ccop
(134)
20
VS
Sn
dg (M + 1)2
Vo, 1
1. 5n-1111
(M
1)
+
V 1 ((
2
Sp-1
25 n-1
Ona Cha(M
+ (M+
1
+ +1 An + 11a Bn + 1 n
+ 1--0
2
S
SSn
where
1 An
11aBB Bn +1 +1200nn + +12ar,
lim
(= + +150B(1) + +12 x + 1 1(ar(
e-0
a
VSa-1 0 (0,)² (ie[(VV., (Va,8(0,) Ve.g(nn: En)
V
0n
Vo,g( Om)) 1,
2a(M + 1)
do
12a0
(e 5n 5.) Fn-1)
{1 -1 V $1))1(
2(M + 1) VSn-1
122a
Ve,g((n)) On)
(Vo,g(O,) (Ve,g((()(V(()
Va,g (0, 5m))
VSn-1
Make some transformations on
to obtain that
Sn
Ve,g(0r. O.. E.)1
Vo, Eu]1
Sn
S
(I S. 5o |2| Fn-1)
(1 [/.))(0....))1 (( ( [[]I)s
+ S
S
M Vo, 8 1l S
a
(/Ve,((On, 51) -E (l) 5m 10 (())))
+
S
Sn
where the last inequality is from Assumption
5). Ler 0 < <
<
It follows from Lemma 15 that
v( (%))
t00. Then we have
M
M|[Va,,(0..)
M8
(E) 1/2 - E' e'e (0. and
1
Sx-1
s2 +t)
V o On, Em)
M8 +a
(
((-()nn))))
Sn
+ei
S
S
(135)
1
+ (M8 + +a)
57
+&
R-1
50

---

Published as a conference paper at ICLR 2022
Similarly, we have
18 (0
Md +a
+ (M8 +a)
Sn-1
S tei
5
Sh
t0)
x-2
(136)
-B 1
(1(((-22))
S
Substitute equation 135 and equation 136 into equation 134
then we get
g(0++)) -((0,) $ ccas+ + c (M8 + a)
+ Pa + Qa.
(137)
2
S
+0
where
cap
Cx ( (0, 5..
(VV 5ull (m.))
Sa-1
of o (M 1)2
Ve, (0001 Sa- 1)1 11)
25n-2
+ A, + 1e Br + 1220 X
+ a2
0g
Vo Vo,-)((0 (0 (()2
V[,,((,)))
0g (M + 1)
Vo, (..))
Pa 20
+ 2
VSn-2
VSn-1
VSn-1
VSn
V
V8,-i8( 8(0, 10 1). 5n-1
(M (M+ 1)
+ 4-2 aqje"
V n V 0. 1,
5
25 n-1
#-1
+ Cha(M +11
a 2 (M + 1)2 +a)
1
VS
VSn
2
$2 +8
S 11
Ø-1
+ +co (MS +a)
tt
S +&1
4-2
51

---

Published as a conference paper at ICLR 2022
It follows from Sn - to0 a.s. that
4:00
1:00
Ve. ----1
8( (0p 1
Ve.g( (m)) 1
Σ 3
PR
20
V
VSa1
n=3
0l (M +1
Σ
V (l00((0 Og
1)|1
(o. 2
VSn-1
vSn
#=3
V 00-188 8 Og 1), 1m5511 11?
(M + 1)
+ 4M² dnj
V
R=3
5
25 n-1
n-1
Chal Csa(M M +1)
2 (M + 1M +a)
1
Σ
2
S/
VSn
n=
2
S
+
st +
1
1
capy (M8 +a)
s
3
S
V Vo,g(02))
Ve.g( 0n)
0g
lim a+++
20
VSi
VSo-i
00
|vo,8(0,)
vo,,(0,)1
(ha(M +1)
+
(M 1)
lim 4-++000
lim
2
v/2
VS,
2
VS2
n +
Sn
Ve 1 g (g
1),5 5m-1
(M + 1) 2
400
+ 4M agee
Σ
Σ
V
B 18.18(00.) 1,000-1,55111 10-)11
S n=1
25
Cha(M
+
1
M8 +a
a + PMM8+
2
V22
S
-1
25 +
From Lemma
15
we get that
Vo,g( 0w))
V (m)
lim
lim
0,
VSn1
and
Vo.8(0.)11
(e,g((.)
lim
lim
lim
R #+0000
SSn
n +00
VSn-1
n
It follows that
do
n (11))1
do
V (6))(1
Coa(M 11)
Σ
Pa
+
(M 1M+1 1)
20
VSo
2
VSi
2
VSi
3=3
+00 || 0 8( 0 1), 5m111
(M + 1) +20
2M aiic²
Σ
|| 1Ve.-18(0m-11.65
(138)
2=2
25
m=2
aga(M M + 1)
M8 +
a + 1 +a)
2
VS2
$2 14
25 19)
By Lemma we have
8
1), Sa-1
2
(M + 1)2622
4M a3
Σ
((em to0 (139)
2 1-1
1-1
52

---

Published as a conference paper at ICLR 2022
Thus, Σ Pr is convergent. In addition, it holds that
E [1 Anl
E (1/4nll
Σ E
100
(1
( (...(())]l V (mn
Ve,s(0n))
(Ve.s.)))
Vo 5n)) (n.1))
VS
1:00 a 2
Vo.
+ 4000
a v(
Σ
E
S
S
3
It follows from Lemma
15 that =0 < 8 < :
such that
(Va,((0)) a.s.,
lim 4-
meaning that there is an almost surely bounded random variable â such that
Ve.g( (e,))
80 a.s.
It follows that
V (0,)1 6
a.s.,
Sn-1
52 +11 Ep)
Then we derive that
100
Σ
E
Sa Anll
12
V 0 (0.))l
af
Σ
+ Σ
Ve..(0.))
(l Ew)1 Fa.1
S
S
3=3
3=3
V
Ve.8(0
af
< 2 Σ
+ Σ
ve, 0m)
Ve.
(140)
Sp-1
Sp-1
of
V e (n))
of V Vo,8(0,))
2(M +1)
Σ
+2
Σ
Sn-1
Sp-1
3=
#=3
4.00
Ve,)((,))
< <2( 1)8 1) +a)
Σ
U.s..
t0)
From Lemma E Ar is convergent almost surely. Similarly, we can prove other parts of
Σt Qn are also convergent almost surely. Thus, E Qu is convergent almost surely. By summary, we get
Σ PPn Qn) is convergent almost surely.
(141)
It is easy to find that J; is a bounded closed set. So AA > O we can construct an open cover H (U) (0 E Ji) of J, Through the HeineBorel theorem, we can get finite open subcover EU( (k (k=00 0, I.....)) from H."". Then assign U U
We can get (i is open
set. Under Assumption 5 = vog()) has only finite connected components J1 J2. So d( m (J,,J Let o dij,)) It follows from Lemma 4 that Fe > 0,
when d(6 d(O,J,) < Eg, there
(es( < 2c (c) -il,
(142)
where gi denotes g(0) (0 E Ji). Let c c= min Eo. 8// and construct U:(", ..... U.!)) It is obvious that V U Ui (i i), d(u
2.2 and [[Vg(()) & 2c 2c)g()) sil (0 "
53

---

Published as a conference paper at ICLR 2022
Since J is bounded set, EN >> O, such that J K (K is the closure of U(O,N)). Then we construct Since U.!) is a open set and K is a closed set, we conclude M is closed set. Since |Vog O) || is a continuous function, 30,+ E M. [V [b)] mingeM [Vog(O)]] Let
a set M = S U.D).
r= (Ve > O.
Then we prove that Vu > 0.0 E K, 38 0, if (
0) || 8, makes d(0,J) < We prove it by contradiction. Assume Buo > 0, vgi > O, 0s, holds || l/ g ((0%,)) < 81 and d(o.J) 2 uo- We make 61 1, and we form sequence (0) is obvious that [| 1 (n)
OIl Since {0 is bounded, through the Accumulation point theorem, there exists a convergent subsequence (0 C [0 We defined ((0) -- 01,,,, Through the continuity of d (0,J) and || [ we get d 2 40 and I g 0 (0) =0. It is contradiction by the definition of J. So Vu > furthermore, due to the continuity of g(0), we can get VEi > 0, 3 8' > 0, if ddO,,d < 8', there is
0,0 K, 38 0, [Vex ( ö, makes d d(O))) u (3,, makes d(O,J) < u). And
- Ei. So combine these two consequences. We can prove Ve 3b > 0, if 0 U
and Vog 0) < b, there is gg()) gi| < E1
Through equation 121 and Lemma 6 we get there is subsequence {l g ((O)))) of [[[Ve.((0,)]13) which satisfies that
lim n
VoL, (0,, 1|1 = a.s..
(143)
Next we aim to prove lim, (V,,((0))122 no positive accumulation points, that is to say, Vep > O, there are only finite values of [Ve,g(()]] larger than co- And obviously, we just need to prove AO < ép < r, there are only finite values of V()l( larger than We prove this by contradiction. We suppose 30 < e < a, making the set S ( (0,)) 0,) be infinite set. Then we assign E =e/8c and define o min(b, e44]. Due equation 143] we get there exists a subsequence {0p, J of [0.) which satisfies |Ve,,, g( (pp)) < We rank S as a subsequence fll (m,,)) ) of Vig (,)) 12)) Then there is infinite subsequence {l] g( (m,, )l}}} of ( Om.. )l²}} such that vn E N+. 3I, np. (m+)) ). For convenient, abbreviate {m;,) } as {in And we construct another infinite sequence }qr} as follows
O. It is equivalent to prove that vl ((,,)((,)))'" (2) has
q1 max n : P1 n < min faainfm;pppp (m >p: 7. / Ve. (e.) sof.
42 min [n: 41 V 0m)] > e):
92x-1 max {n: min (m, mi -20-3) } < min(m: my >> min(m; : mi 920-3).
V Ve.g(( Oz)) [}}
42. = min (n : q2--1, Vo,g(0,)) > e].
Now we prove that 3No when Q2a > No. it has < V 8(0 )1 <r. The left side is obvious (the definition of q2n). And for the right side, we know Ve 8( (0) S e. follows from equation 5 that
Vo, df S,
10 - 0,11= | (0 E.)
Sn (g, 51)1
E FOA--E((Ve/) Vo.. (()
of
(M Ve.g(( [ +a).
Sp
Through previous consequences we can easily find that
ag
ab Veng(On)) (b,) ||
Σ
8( On 5, (I
E EE Ve.
e, On, 5.) {3)))
S
S
2=2
+00 a.s..
Note that a + 0, a.s.. We conclude
0 0,1l + a.s..
(144)
54

---

Published as a conference paper at ICLR 2022
Through Assumption
5 2) get
| e (n+1)1l - |V (x,)) v V eu+1 8 (x+1)]
& On 1) V (o.z(0n)l'' (o)) I clI0xt1 Oul + 0 a.s., So INo. when > No. get that when 92n No 1, there I [V 1/ 8 p2. 1lll + ||| 8a 020 Il VV (00018 S e r e r. That means that O120 E U (0) so we can prove Bio. such that Oyz. E (i) And due to (Vag((0)) 0n) Se<r (n E (2n)) we get vk E (42n-1, q20), lis, such that Og E u!A Due (V j E (92n=1,92x)). For convenient, sign i 1---11 102n And then we can conclude that
VV,g 0,) I || e
there is |1 B 8( (x+1)]1
V 0m)
e. Then
to 10++1 0.1 - Oa.s., we know
Vee (b,)ll I 2clg(0,) 8iyzal (n E 1920-1.9221
Due to locally sign-present peteerrreeeeggeeeeeeenne property, we get
V Vos 0,) 2c(g(0,) 0,) ginza (g(0,) 2 8ipza or
V e,) f 22((g( (b,) Blazn (g(0,) S 8lyg.) (n E [q2- 1290).
Ways dispose these two cases is same, just show how to prove the first case, We get
s( Opp. ||1
| Pozm- 8( 0 0p20 11 < 2c(8(0gz.)) 8igza
V Voza-- 8 Ozza 1)12
e- 0 <
2c
g( 12 1441) 8 (02m-111) + 20 +20(8(022-1) 8lize)
| -ezz-11 8( 8(002m-1) 1220-11)1
1=0
From equation
137
we obtain
g( 0 2 1+++1) -8())-8(0p) (pp0-1te)
cap cf 1)
(MÒ + +a)
Pazm-1+i + 292n-1t1-
2
$ 82
42n-1t
So there is
42n
L
02--1 Σ
e <<
(P Qu2o-141)
$ +.8
1=0
920-1
(145)
2c 8 (000)
8ize-1
08zn
8( O
2(00za-1)l 1)1
which
ca,(
L 2c caf
(M8 +a).
Due to V 8(0
2 < < b, so through equation
141 we get that e(0 Bizn- < <e/Sc.
Substitute it into equation
146
We get
4z
42n 4b
Σ
(Pez- Qaz..
(146)
St+0 tc1 92c-1+7
2L
Through equation 141 we know E (Pn + Qn) is convergence almost surely. So we get that
2/=0
Pize iti + 1ti
- a.s. by the Cauchy's test for convergence. Combining
1/52+8,
- 0 a.s., we get
5
1
9ia-tti
(147)
42o 22--92n-1 ---11
e
Σ
P Puze- Qoa ) e
a.s., 21.
21
+C]
S42e
55

---

Published as a conference paper at ICLR 2022
so there is
+-00
92n
-2n-1
too a.s..
(148)
+0
92a-1 1ti
But on the other hand, we know we get
| 8:za-1+t 1 (
> 0 (i> 0). Together with equation 121
1:00
92c
42n
1:00
42
920-1
V 00 1188 O O2ea (0-a-11-))
Σ
Σ
Σ
S +EI
5 tei
920-141
92-1ti
(149)
x(,))
t000 a.s..
contradicts with equation 148 so we get that [Va,g(0,)] + a.s., Combining equation 133 we get ||V (Ve.((0,)) + 0 no matter S,, < +00 a.s. Sn toc, Under Assumption 5 1), it is safe to conclude that there exists a connected component JL of J such that lim d (+, = 0.
56


Reviews:
[{"review_id": "jXZ92LoIFaG", "reviewer": "Reviewer_ecdk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "PAPER SUMMARY: This paper presents new proofs to the convergence of momentum-SGD and AdaGrad. The new theoretical results show they both converge (in the sense of the estimate sequence). Also, the momentum-SGD converges at a faster rate than SGD (with additional assumption on the properties of the loss function used).\n\nNOVELTY & SIGNIFICANCE: momentum-SGD and AdaGrad are extensively used algorithms in practice. Providing further understanding of their properties is always a good direction to go. This paper proves that under some mild assumptions, momentum-SGD can converges faster than SGD (with additional assumption on the properties of the loss function used). This seems to be a new result for nonconvex objectives (for convex/strongly convex ones we already have similar results). For AdaGrad, the paper proves that the estimate sequence itself is convergent, but not convergence rate is provided. Such result for AdaGrad seems a bit weak. In the theoretical aspect, this paper paves new ways to prove the convergence for such algorithms.\n\nTECHNICAL SOUNDNESS: The theoretical results and assumptions seem legitimate and reasonable. But I have not checked the proof details.\n", "summary_of_the_paper": "New convergence results for momentum-SGD and AdaGrad", "summary_of_the_review": "The paper provies new convergence results for momentum-SGD and AdaGrad, showing that momentum-SGD converges faster than SGD and AdaGrad's estimate sequence converges. The momentum-SGD proof is beneficial for understanding why momentum works in nonconvex objectives, which is still a not well understood topic.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "S7FouqCyh_S", "reviewer": "Reviewer_MDU9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I read some parts of the proof carefully, and it seems that there are some mistakes that should be resolved. I also have several suggestions for the presentation of the paper.\n\nRegarding the presentation: (* are the major concerns)\n\n1. In the optimization literature, the term \"estimate sequence\" refers to a sequence of auxiliary functions, which were first used in the analysis of Nesterov's accelerated gradient descent. See Definition 2.2.2 of the following textbook.\n\nNesterov, Yurii. Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science & Business Media, 2003.\n\nPlease consider just using \"iterates\" to refer to the \\theta_n in the paper.\n\n2*. The updating rules of mSGD and SHB in equations 3 and 4 are actually equivalent. This should be mentioned in the paper, and it is inappropriate to say that \"the results in Liu et al (2020) do not apply to mSGD.\" \n\nFor example, to get equ 4 from 3, we have\n\n$v_n = \\alpha v_{n-1} + \\varepsilon \\nabla_n,  \\theta_{n+1} = \\theta_n - v_n$\n\n$\\frac{1}{\\alpha + \\varepsilon} v_n = \\frac{\\alpha}{\\alpha + \\varepsilon} v_{n-1} + \\frac{\\varepsilon}{\\alpha + \\varepsilon} \\nabla_n, \\theta_{n+1} = \\theta_n - (\\alpha+ \\varepsilon) * \\frac{1}{\\alpha + \\varepsilon} v_n$ \n\nTo get equ 4, we just need to set $\\frac{1}{\\alpha + \\varepsilon} v_n$ as $v_n$ and $\\beta$ as $\\frac{\\alpha}{\\alpha + \\varepsilon}$. All the parameters can also depend on $n$. \n\n3*. It would be much better if simple proof sketches of theorems 1, 2, and 3 can be added. For example, how is the milder assumption in Assumption 2 4) handled in the analysis? How is the difficulty mentioned in equ (11) handled? Otherwise, readers have to dive into the details of proof to figure them out.\n\n4. In Assumption 4 1), $\\varepsilon_1$ has already been used as stepsizes. \n\n5. Assumption 4 2) is very similar to the Polyak-Lojasiewicz condition, this should be mentioned.\n\n6*. It is inappropriate to say that \"We can observe that the convergence rate of mSGD is quicker than that of SGD in this sense.\" In equation (78), It is unclear why the bound $O((\\frac{1}{2-\\alpha})^n)$ is relaxed to the bound presented in Theorem 1. Looking at $O((\\frac{1}{2-\\alpha})^n)$, a larger momentum $\\alpha \\rightarrow 1^-$ actually gives a worse bound.\n\n7. Under Assumption 5, why is \"condition 1)\" is relatively weak?\n\nRegarding the proof:\n\nI haven't checked all the proof in detail, here are some problems that need to be clarified:\n\n1. Lemma 3 is a standard result, see Lemma 1.2.3 of the textbook mentioned above.\n\n2. In Lemma 4, it seems that the S_i needs to be bounded, as used in the proof.\n\n3. In Lemma 4, $\\varepsilon_0$ is actually defined in the proof, this should be clarified.\n\n4. In the second last equation on page 14, the last term should be integrated to t', not x.\n\n5* The last equation on page 14 is incorrect, how is x_2 canceled? It seems that t'' > 0 is needed, why is this true?\n\n6* In equ 17, why is $|g'(t')| = ||\\nabla f(x_0)||$? Specifically, we have $g'(t') = \\frac{x_0 - x_2}{\\|x_0 - x_2\\|}\\cdot \\nabla f(x_0)$. Therefore, $|g'(t')| = ||\\nabla f(x_0)||$ if and only if $x_0- x_2$ is parallel to $\\nabla f(x_0)$, why is this the case?\n\n7* In the second last equality of the proof of lemma 4, how is the term $g'(t'')$ handled? The equality holds if and only if $g'(t'') = g'(t')$, why is this true?\n", "summary_of_the_paper": "This paper focuses on developing asymptotic convergence of mSGD and Adagrad, which is stronger than the existing results on subsequence convergence and iterate average convergence. The assumptions are similar or weaker than previous works. ", "summary_of_the_review": "In summary, the issues mentioned above must be resolved. In my opinion, there are obvious mistakes in the proof. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "CU3ifJUpEp", "reviewer": "Reviewer_qmsj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper appears to use a different template other than ICLR's. I encourage the authors to double check this. The current template makes the paper harder to read at least for me.\n\nStrengths:\n- Theorem 1 presents asymptotic convergence which complements existing results in the literature. Convergence in theorem 2 is for metric depending on last iterate which is stronger compared to time-averaged metric.\n- The convergence on expectation of squared norm gradient on last iterate shows that mSGD is better than SGD.\n\nWeaknesses:\n- The clarity of the paper is not good, the proofs in the appendix are highly technical and hard to follow. I would recommend to have an outline to better understand how each lemma play a role in the main convergence analysis. I have gone through the proofs and find no problem but there is a chance I miss something.\n\nComments:\n- What is the motivation of using assumption 4 or 5 rather than assuming convexity. As these assumptions are not standard, it is better to include examples of classes of function that satisfy these assumptions.", "summary_of_the_paper": "The paper analyzes the convergence of momentum-based SGD (mSGD) and AdaGrad in the sense of asymptotic convergence rather than time average or subsequence convergence in existing results. The analysis shows that mSGD is better than SGD in terms of expectation of squared gradient norms on last iterate.", "summary_of_the_review": "The paper contains solid contribution in terms of theoretical analysis, especially for mSGD. The convergence results are on last iterate different from existing results. However, given the currents state of the submission, the clarity of the paper needs to be significantly improved. Adding proof outline and providing more explanations for key steps definitely helps to improve the quality of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an asymptotic analysis of the convergence of the last iterate of mSGD and Adagrad. This result extends previous work providing stronger results under weaker assumptions. Even if these topics received less attention from the community, they are key problems in stochastic optimization.

The reviewers and I had several doubts about the proofs and relation with previous work. However, the rebuttal phase essential acted as a minor revision process. In fact, the authors fixed all the issues, convincing the reviewers (and me) that the results are novel, correct, and interesting.

For the above reasons, I recommend the acceptance of this paper.
Decision: Accept (Poster)