A Unified Convergence Theorem for Stochastic Optimization Methods
Authors: Xiao Li
Andre Milzarek
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic optimization theory
almost sure convergence

Abstract: In this work, we provide a fundamental unified convergence theorem used for deriving expected and almost sure convergence results for a series of stochastic optimization methods. Our unified theorem only requires to verify several representative conditions and is not tailored to any specific algorithm. As a direct application, we recover expected and almost sure convergence results of the stochastic gradient method (SGD) and random reshuffling (RR) under more general settings. Moreover, we establish new expected and almost sure convergence results for the stochastic proximal gradient method (prox-SGD) and stochastic model-based methods for nonsmooth nonconvex optimization problems. These applications reveal that our unified theorem provides a plugin-type convergence analysis and strong convergence guarantees for a wide class of stochastic optimization methods. 

A Unified Convergence Theorem for Stochastic Optimization Methods
Xiao Li
School of Data Science (SDS)
Shenzhen Institute of Artificial Intelligence and Robotics for Society (AIRS)
The Chinese University of Hong Kong. Shenzhen Shenzhen, China
1 lixiao6cuhk, edu. on
Andre Milzarek
School of Data Science (SDS)
Shenzhen Research Institute of Big Data (SRIBD)
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
andremilzareeksechkk.ee edu.cc
Abstract
In this work, provide fundamental unified convergence theorem used for deriving expected and almost sure convergence results for a series stochastic optimization methods, Our unified theorem only requires to verify several repre- sentative conditions and not tailored to any specific algorithm. As a direct appli- cation, recover expected and almost sure convergence results of the stochastic gradient method (SGD) and random reshuffling (RR) under more general settings. Moreover, establish new expected and almost sure convergence results for the stochastic proximal gradient method (prox-SGD) and stochastic model-basee methods for nonsmooth nonconvex optimization problems. These applications reveal that our unified theorem provides a plugin-type convergence analysis and strong convergence guarantees for wide class of stochastic optimization methods.
Introduction
Stochastic optimization methods are widely used solve stochastic optimization problems and empirical risk minimization, serving as one of the foundations of machine learning. Among the many different stochastic methods, the most classic one is the stochastic gradient method (SGD), which dates back to Robbins and Monro [36]. If the problem at hand has a finite-sum structure, then another popular stochastic method is random reshuffling (RR) [20]. When the objective function has a composite form or is weakly convex (nonsmooth and nonconvex), then the stochastic proximal gradient method (prox-SGD) and stochastic model-based algorithms are the most typical approaches (18, 11]. Apart from the mentioned stochastic methods, there are many others like SGD with momentum, Adam, stochastic higher order methods, etc. In this work, our goal is establish and understand fundamental convergence properties of these stochastic optimization methods via a novel unified convergence framework.
Motivations. Suppose we apply SGD to minimize a smooth nonconvex function f. SGD generates a sequence of iterates {æ*) which is stochastic process due to the randomness of the algorithm and the utilized stochastic oracles. The most commonly seen 'convergence result' for SGD the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

expected iteration complexity, which typically takes the form [17]
min k=
E [1]
or E[IVS( SO
where T denotes the total number of iterations and k is an index sampled uniformly at random from {O..... T) Note that we ignored some higher-ordes convergence terms and constants to ease the presentation. Complexity results are integral to understand core properties and progress of the algorithm during the first T iterations, while the asymptotic convergence behavior plays an equally important role as it characterizes whether an algorithm can eventually approach an exact stationary point or not. We refer to Appendix H for additional motivational background for studying asymptotic convergence properties of stochastic optimization methods. Here, an expected convergence result, associated with the nonconvex minimization problem ming f()), has the form
lim E V f ((*"(ll = 0.
Intuitively, it should be possible to derive expected convergence from the expected iteration complexity (1) by letting T -> co. However, this is not the case as the 'min' operator and the sampled & are not well defined or become meaningless when T goes to co.
The above results are stated in expectation and describe the behavior of the algorithm by averaging infinitely many runs. Though this is an important convergence measure, in practical situations the algorithm is often only run once and the last iterate is returned as a solution. This observation moti- vates and necessitates almost sure convergence results, which establish convergence with probability 1 for a single run of the stochastic method:
lim [Vf(=")) = almost surely. 8-000
(3)
Backgrounds. Expected and almost sure convergence results have been extensively studied for convex optimization; see, e.g., [10, 34, 42, 46, 5, 41]. Almost sure convergence of SGD for minimizing smooth nonconvex function f was provided in the seminal work [3] using very standard assumptions, i.e., Lipschitz continuous V and bounded variance. Under the same conditions, the same almost sure convergence of SGD was established in [33] based on a much simpler argument than that of [3]. A weaker 'lim inf'-type almost sure convergence result for SGD with AdaGrad step sizes was shown in [26]. Recently, the work [28] derives almost sure convergence of SGD under the assumptions that and ff are Lipschitz continuous, f is coercive, is not asymptotically flat, and the v-th moment of the stochastic error is bounded with v 2 2. This result relies on stronger assumptions than the base results in [3]. Nonetheless, it allows more aggressive diminishing step sizes if >> 2. Apart from standard SGD, almost sure convergence of different respective variants for min-max problems was discussed in [22]. In terms of expected convergence, the work [6] showed lim [E[ V f(=*)]]] = 0 under the additional assumptions that o is twice continuously differentiable and the multiplication of the Hessian and gradient f²f(x)) V (xx is Lipschitz continuous.
Though the convergence of SGD is well-understood and a classical topic, asymptotic convergence results of the type (2) and (3) often require a careful and separate analysis for other stochastic optimization methods - especially when the objective function is simultaneously nonsmooth and nonconvex. In fact and as outlined, a direct transition from the more common complexity results (1) to the full convergence results (2) and (3) is often not possible without further investigation.
Main contributions. We provide a fundamental unified convergence theorem (see Theorem 2) for deriving both expected and almost sure convergence of stochastic optimization methods. Our theorem is not tailored to any specific algorithm, instead it incorporates several abstract conditions that suit vast and general class of problem structures and algorithms. The proof of this theorem is elementary.
We then apply our novel theoretical framework to several classical stochastic optimization methods to recover existing and to establish new convergence results. Specifically, we recover expected and almost sure convergence results for SGD and RR. Though these results are largely known in the literature, we derive unified and slightly stronger results under a general ABC condition [24, 23] rather than the standard bounded variance assumption. We also remove the stringent assumption used in [6] to show (2) for SGD. As core application of our framework, we derive expected and almost sure convergence results for prox-SGD in the nonconvex setting and under the more general ABC condition and for stochastic model-based methods under very standard assumptions. In particular, we show that the iterates {=*) Ja20 generated by Pro and other stochastic model-based methods

---

will approach the set of stationary points almost surely and in an expectation sense. These results are new our knowledge (see also Subsection 3.5 for further discussion).
The above applications illustrate the general plugin-type purpose of our unified convergence analysis framework. Based on the given recursion and certain properties of the algorithmic update, we can derive broad convergence results by utilizing our theorem, which can significantly simplify the convergence analysis of stochastic optimization methods; see Subsection 2.1 for a summary.
2 A unified convergence theorem
Throughout this work, let (22 [Fx P) be filtered probability space and let us assume that the sequence of iterates {a* 1x20 is adapted to the filtration (Fik [F200 i.e., each of the random vectors x² S2 + R" is Fk me-meauurablc.
In this section, present unified convergence theorem for the sequence {x h220 based an abstract convergence measure $. To make the abstract convergence theorem more accessible, the readers may momentarily regard + and (1u h=20 V and the sequence related the step sizes, respectively. We then present the main steps for showing the convergence of a stochastic optimization method by following step-by-step verification of the conditions in our unified convergence theorem.
Theorem 2.1. Let the mapping db R + R and the sequences {a" Ju20 S IR" and {ue Ju20 S R.4. be given. Consider the following conditions:
(P.1) The function 4b is Lg LapLipschitz continuous for some Lp > O, ie., we have [[(( D S
Le | yll for all x. y E R".
(P.2) There exists a constant a > 0 such that Ekzo ls E ((x*) co.
The following statements are valid:
(i Let the conditions (P.1) be satisfied and suppose further that
(P.3) There exist constants A, B, b 2 0 and P1 P2.9 9 >> 0 such that
Bll 11119] < Ape + B Blll (x
(P.4) The sequence {uR}K20 and the parameters a, b, g. PI. P2 satisfy
{pk3120 is bounded,
Σ p = 0o, and a,921, a a2b. P1.P2 2
Then, it holds that limg-100 TE + =
ii) Let the properties (P.1)-(P.)) hold and assume further that
(P.3') There exist constants A, 6 2 0, P2, > and random vectors Ag, Bg Ω E such that
x + p A + P PaB. B
and for all k Ag, By are FR+1 measuraaee and have E[A, Fx] 0 almost
surely, [[[[A&|1]] S A, and lim sup |B /11 [1 (x** (
(1))))))))
< oo almest surely.
(P.4') The sequence {ux Juzo and the parameters a, b, g, P1.P2 satisfy p4 - 0,
k=0 14 00,
Σ
2p Pk
< co,
and 2, qa 2 b P1 2'
1
P2 2 1.
R=0
Then, it holds that limg-roo [<())|] 0 almost surely.
The proof of Theorem 2.1 is elementary. We provide the core ideas here and defer its proof to Appendix A. Item (i) is proved by contradiction. An easy first result is lim inf Eill {>>*))((1))))>>))
0.
We proceed and assume that [ (xx*t) l]]k2o does not converge to zero. Then, for some å > 0,
we can construct two subsequences (Eere2 and {ur)2o such that l < Me and ((=+)( 2 25, []|[((2>) (x ]l"] < 8", and [|| {<<)(()))119 > 8 for all 4 < le < Based on this construction, the
conditions in theorem, and set of inequalities, we will eventually reach a contradiction. We
notice that the Lipschitz continuity of & plays a prominent role when establishing this contradiction. Our overall proof strategy inspired by the analysis of classical trust region-type methods, see, e.g.,
[9, Theorem 6.4.6]. Let also mention that different strategy for the fully deterministic setting and
3

---

scalar case + _R - R was provided in [8]. For item (ii), we first control the stochastic behavior of the error terms A₃ by martingale convergence theory. We can then conduct sample-based arguments to derive the final result, which is essentially deterministic and hence, follows similar arguments to that of item (i).
The major application areas of our unified convergence framework comprise stochastic optimization methods that have non-vanishing stochastic errors that utilize diminishing step sizes. In the next subsection, we state the main steps for showing convergence of stochastic optimization methods. This also clarifies the abstract conditions listed the theorem.
2.1 The steps for showing convergence of stochastic optimization methods
In order to apply the unified convergence theorem, we have to verify the conditions stated in the theorem, resulting in three main phases below.
Phase Verifying (P.1)-P.2). Conditions (P.1)-(P.2) are used for both the expected and the almost sure convergence results. Condition (P.1) is problem property and is very standard. We present the final convergence results in terms of the abstract measure Φ. This measure can be regarded as f f in convex optimization, V f in smooth nonconvex optimization, the gradient of the Moreau envelope in weakly convex optimization, etc. In all the situations, assuming Lipschitz continuity of the convergence measure 4 is standard and is arguably a minimal assumption in order to obtain iteration complexity and/or convergence results.
Condition (P.2) is typically result of the algorithmic property or complexity analysis. To verify this condition, one first establishes the recursion of the stochastic method, which almost always has the form
B Fil S (1 3,)y M (1
Sa-
Here, is a suitable Lyapunov function measuring the (approximate) descent property of the stochastic method, (a represents the error term satisfying Ex - Ca oc, 3y is often related the step sizes and satisfies Ee 3g (see Theorem B.1), we obtain Ek=o js [[]] (=**) < oo, i.e., condition (P.2).
Then, applying the supermartingale convergence theorem
Since condition (P.2) is typically a consequence of the underlying algorithmic recursion, one can also derive the standard finite-time complexity bound (1) in terms of the measure B[]] [[][((>>>)] (x*)) based on it. Hence, non-asymptotic complexity results are also included implicitly in our framework as a special case. To be more specific, (P.2) implies E 14g
[[]] + (x*) [|]]]] S M for some constant M > 0 and some total number of iterations T. This then yields minogAs7 [[[ [1=))|| M/ M/ Mk- Note that the sequence { J:20 is often related to the step sizes. Thus, choosing the step sizes properly results in the standard finite-time complexity result.
Phase I: Verifying (P.3)-(P.4) for showing expected convergence. Condition (P.3) requires an upper bound the step length of the update in terms of expectation, including upper bounds for the search direction and the stochastic error of the algorithm. It is often related to certain bounded variance-type assumptions for analyzing stochastic methods. For instance, (P.3) is satisfied under the standard bounded variance assumption for SGD, the more general ABC assumption for SGD, the bounded stochastic subgradients assumption, etc. Condition (P.4) is standard diminishing step sizes condition used in stochastic optimization.
Then, one can apply item (i) of Theorem 2.1 to obtain [[| 1 (a*)) 0.
Phase III Verifying (P.3') for showing almost sure convergence. Condition (P.3') is parallel to (P.3). It decomposes the update into a martingale term A₁ and a bounded error term Bg- We will see later that this condition holds true for many stochastic methods. Though this condition requires the update to have a certain decomposable form, it indeed can be verified by bounding the step length of the update in conditional expectation, which is similar to (P.3). Hence, (P.3') can be interpreted as a conditional version of (P.3). To see this, we can construct
x k+1
x
pkk
k++
x E[ x Fi.) +
pe L E[
x
Fil
(4)
DE
A By Jensen's 's inequality, we then have E[A, Fi] 0, E|||A [9] < 2 n E[|l=++1
Ba
=111 and |x 1 M PE]]| x111 Ful.

---

Thus, once it is possible to derive E|]|2 ++ x=11 Fil ( ) in an almost sure sense, condition (P.3') is verified with P1 P2 = Condition (P.4') is parallel to (P.4) and standard in stochastic optimization. Application of item (ii) of Theorem 2.1 then yields |x*))) - 0 almost surely.
In the next section, will illustrate how show convergence for set of classic stochastic methods by following the above three steps.
Applications to stochastic optimization methods
3.1 Convergence results SGD
We consider the standard SGD method for solving the smooth optimization problem mingeR" f(xx). where the iteration of SGD is given by
ag..
(5)
Here, 9 denotes stochastic approximation of the gradient V (xx*). We assume that each stochastic gradient g* is Fet:FF-+-aaassss -measurable and that the generated stochastic process {==) adapted the filtration [F2 We consider the following standard assumptions:
(A.1) The mapping V R IR. is Lipschitz continuous R. with modulus >>> 0. (A.2) The objective function f is bounded from below on R", i.e., there is such that f(x) 2 f for all R
(A.3) Each oracle 9d defines an unbiased estimator of V V i.e. it holds that Elg" | [r
V f(xx") almost surely, and there exist C, D 2 0 such that
Blllg* vf(>"))" )12 FRJ S C[f(x*) +]+D almost surely VKEN.
(A.4) The step sizes (ax*) } 120 satisfy Σ ag = oo and Ex= of <..
We now derive the convergence of SGD below by setting + = V and lıx = Or
Phase I: Verifying (P.1)-(P.2). (A.1) verifies condition (P.1) with Lę = L. We now check (P.2). Using (A.2), (A.3), and a standard analysis for SGD gives the following recursion (see Appendix C.1 for the full derivation):
(=)))**1))+) Fel S (1+ LCaf [f(=*) -1 (1-
Lax 2
LD 2
1+
[2
(6)
2
Taking total expectation, using (A.4), and applying the supermartingale convergence thcorem (Theo- rem B. gives Σ [x| fx**) to some finite value. This verifies (P.2) with a = 2.
[|a] 30. Furthermore, the sequence [e[f(=")]])a)) converges
Phase II: Verifying (P.3)-(P.4) for showing expected convergence. For (P.3), we have by (5) and (A.3) that
Elll=* x11 s 5 Ef ( Co
f + Do
< F for all k. Thus, condition (P.3) holds with q == 2, = CF + D, P1 = 2, = 1, P2 2, and b = 2. Condition (P.4) is verified by (A.4) and the previous parameters choices. Therefore, can apply Theorem 2.1 to
Due to the convergence of [x ) }>> there exists F such that B[f(**)
deduce [[]] fx II] +
Phase III: Verifying (P..') for showing almost sure convergence. For (P.3'), it follows from the update (5) that
a k+1 x (g v\(a²)) or (s("))
We have P1 11
g g fl F, and choosing any q b > 0 establishes (P.3'). As before, condition (P.4') follows from (A.4) and the previous parameters choices. Applying Theorem 2.1 yields [ + 0 almost surely.
vf(x*), P2 1, and B = (f(**) Using (A.2), (A.3), E[f(x*)
Finally, we summarize the above results in the following corollary.
Corollary 3.1. Let us consider SGD (5) for smooth noncovvex optimization problems under (A.1)
(A.4). Then, we have limp-+00 [|[| V f(x" (x) [] 0 and limg-+00 [[V((=>)] 0 almost surely.
5

---

3.2 Convergence results of random reshuffling
We now consider random reshufiling (RR) applied to problems with finite sum structure
min (xx ((a,)) #ER"
N
(ar,
where each component function i(; Rd + R is supposed to be smooth. At iteration k, RR first generates random permutation o+1 of the index set (I,...,NN J. It then updates æf to x*+1 through N consecutive gradient descent-type steps by accessing and using the component gradients
N).
{Vf(. of 1 ,....,, Vf(. NN k+1 }} sequentially. Specifically, one update-loop (epoch) of RR given
by
T = . =
- -g V
i= i..,,.., x g+1
After one such loop, the step size org and the permutation o k+1 is updated accordingly; cf. [20, 30, 32). We make the following standard assumptions:
(B.1) For all i E f1...., N). f(-: i) is bounded from below by some f and the gradient V f-,it) is Lipschitz continuous on 12" with modulus L 0.
(B.2) The step sizes {ax 1k20 satisfy Σk=o ag = oo and Σx= af cc.
A detailed derivation of the steps shown in Subsection 2.1 for RR is deferred to Appendix D.2. Based on the discussion Appendix D.2 and on Theorem 2.1, we obtain the following results for RR.
Corollary 3.2. We consider RR (7) for smooth nonconvex optimization problems under (B.1)-(B.2).
Then it holds that lim V fx*))]l = and limg [[x") = almost surely.
3.3 Convergence of the proximal stochastic gradient method
consider the composite-type optimization problem
min (xx) == f(z) + ((x)
(8)
where f:: IR + a continuously differentiable function and o R - (-o0, oo] is r-weakly convex (see Appendíx F. proper, and lower semicontinuous. In this section, want apply our unified framework to study the convergence behavior of the well-known proximal stochastic gradient method (prox-SGD):
k+1 a (x* -aggg),
where g x V (x**) is a stochastic approximation of V (**"), (au) S RR is suitable step size sequence, and pro R - R", prox arox (x) == argmingeR: (()) + 20 well-known proximity operator of
1 || y/1 is the
3.3.1 Assumptions and preparations
We first recall several useful concepts from nonsmooth and variational analysis. For a function h R (-o0, oo]. the Fréchet (or regular) subdifferential of h at the point is given by
@h(x)) (g IR" h(y) 2 h(x)) (g. y 2²) o(lly a=|) as y - a)),
see, e.g., [39, Chapter 8). If convex, then the Fréchet subdifferential coincides with the standard (convex) subdifferential. It is well-known that the associated first-order optimality condition for the composite problem (8) - Öx)(z) vf(x) + 0p(xx) can be represented as a nonsmooth equation, [39,2]] 21],
F (x)
prox
= - aVf(=)
where M denotes the so-called natural residual. The natural residual Fa a common stationarity measure for the nonsmooth problem (8) and widely used in the analysis of proximal methods.
We will make the following assumptions on f. s. and the stochastic oracles (g*) Jazo:
(C.1) The function f is bounded from below on R", i.e., there is f such that f(x) 2 for all x E R", and the gradient mapping V is Lipschitz continuous (on R") with modulus
(C.2) The function yp is r-weakly convex, proper, lower semicontinuous, and bounded from below dom sp, i.c., we have (p(x) 2 for all E dom sp.

---

(C.3) There exists L. > 0 such that p((x) - ((y) S Lø||æ yll for all 2, dom 4.
(C.4) Each 9e defines an unbiased estimator of V.(x=), i.e., we have Elgb Ful V.(xx*) almost surely, and there exist C, D 2 0 such that
Ellgg - Vf(x*)) I1 F& < C[((=') + D almost surely A
(C.5) The step sizes {av } 220 satisfy Ek ag = oo and Ex= x0.
Here, we again assume that the generated stochastic processes ( Jx20 is adapted to the filtration The assumptions (C.1), (C.2). (C.4), and (C.5) are fairly standard and broadly applicable. In particular, (C.1), (C.4), and (C.5) coincide with the conditions (A.1) used in the analysis of SGD. We continue with several remarks concerning condition (C.3).
Remark 3.3. Assumption (C.3) requires the mapping & be Lipschitz continuous on its effective domain dom yp This condition holds in many important applications, e.g., when op is chosen as a norm or indicator function. Nonconvex examples satisfying (C.2) and (C.3) include, e.g., the minimax concave penalty (MCP) function [45], the smoothly clipped absolute deviation (SCAD) [15], or the student-t loss function. We refer to [4] and Appendix E.2 for further discussion.
3.3.2 Convergence results of prox-SGD
We now analyze the convergence of the random process {x* ]k20 generated by the stochastic algorithmic scheme (9). As pioneered in [11], we will use the Moreau envelope envoe,
1 20
envey
IR" R, enva (x) milyER= (0)) +
æ y|1
(10)
as a smooth Lyapunov function to study the descent properties and convergence of prox-SGD.
We first note that the conditions (C.1) and (C.2) imply w-eaweak convexity of a for every 0 E (0, (L J. In this case, the Moreau envelope envey well-defined and continuously differentiable
function with gradient Venvoy (æ: (a: prox (æ:);; see, e.g., [38, Theorem 31.5).
As shown in [13, 11], the norm of the Moreau envelope - Venv (z)] defines an alternative stationarity measure for problem (8) that equivalent to the natural residual if is chosen sufficiently small. A more explicit derivation of this connection is provided in Lemma E.
Next, we establish convergence of prox-SGD by setting + = Venvag and 14 og- Our analysis is based on the following two estimates which are verified in Appendix E.4 and Appendix E.5.
Lemma 3.4. Let {x* Ja20 be generated by prox-SGD and let the assumptions (C.1) be satisfied. }, it holds that
Then, for E (0, [3L + 1)) and all l: with 0g S min +
Blenve (wx 3 Fxl I (1 4C# 4C4-1aa3 af))))) (envow [ L0ax| Venvey (a* ) + ( + D0-
(11)
almost surely, where 3 :0 f E.
Lemma 3.5. Let {a*} 1220 be generated by pro and suppose that the assumptions (C.1)-(C.4)
hold. Then, 0 E (0, [ + 7] 1) and all k with an I 27 we have almost surely
[[ xx FR) < 8(2L C)o -levvs (ar +5 +4(((2L+ + C)O L) D)a (12)
Phase I: Verifying (P.2) In [21, Corollary 3.4], it is shown that the gradient of the Moreau
envelope is Lipschitz continuous with modulus L. := max (0 (1 [L + + '[L I[++ + 7]} for all
0 E (0. [L + 1))) Thus, condition (P.1) is satisfied.
Furthermore, due to ag + O and choosing 0 E (0, [3L + -)-1), the estimate (11) in Lemma 3.4 holds for all A sufficiently large. Consequently, due to enver (x) 2 (proxop, 2 & and (C.5), Theorem B.I 1 is applicable and upon taking total expectation, {E(envoy (x*)]] converges some E IR. In addition, the sequence (env (x=) A220 converges almost surely some random variable e* and have Ex=p on Bl] Venvoy (a=)) cc. This verifies condition (P.2) with a
Phase HI: Verifying (P.4)-(P.4) for showing convergence in expectation. Assumptions (C.1) and Lemma 3.5 allow us to establish the required bound stated in (P.3). Specifically, taking total
7

---

expectation in (12), we have
B|[1 [+ x 11 S 8(2L + C)a Elenvo Φ) 4(((LL + C)O + 1) + D)a
for all sufficiently large. Due to Elenv ou (a*)) + there exists such that E[env ow (ax*) S
for all k. Hence, (P.3) holds with q- 2, A 8(2L + C)F + <( C) + 1) D). p1 2, and
B = 0. The property (P.4) easily follows from (C.5) and the parameter choices. Consequently, using Theorem 2.1, we can infer B[[ Venvop(a="]l
O.
Phase III: Verifying (P.3')
( for showing almost sure convergence. We follow the construction Og -1 (x x B|x x Fx]), B₁ ox "E[=**1 x Fel. and
in (4) and set A₂
P1.P2 = 1. Clearly, we have E[AA F = 0 and based on the previous results in Phase II, we can show E|]|=*+1 101 ((a which establishes boundedness of [E|] A AA.l)))) [x20- Similarly, for
Bg and by Lemma 3.5 and Jensen's 's inequality, we obtain
B&l12 S 0g B[|a 101 F& s 8(2L + C) (envoe (x*) +5) O(1)
Due to enve (a=) + almost surely, this shows lim = | 2 < oo almost surely. Hence, all requirements in (P.3') are satisfied with q = 2 and = O. Moreover, it is easy to see that property (P.4') also holds in this case. Overall, Theorem 2.1 implies Venvey (x (0 + 0 almost surely.
As mentioned, it is possible to express the obtained convergence results terms the natural residual Fott = -Flt nat see, e.g., Lemma 1. We summarize our observations in the following corollary.
Corollary 3.6. Let us consider prox-SGD (9) for the composite problem (8) under (C.5).(C.5) Then, we have lim Faa (x*) |[] = 0 and lim [F (x*) = almost surely.
Remark 3.7. As byproduct, Lemma 3.4 also leads to an expected iteration complexity result of prox-SGD by using the ABC condition (C.4) rather than the standard bounded variance assumption. This is a nontrivial extension of [11, Corollary 3.6]. We provide a full derivation in Appendix E.
3.4 Convergence of stochastic model-based methods
In this section, we consider the convergence of stochastic model-based methods for nonsmooth weakly convex optimization problems
min (xx)) =- (xx (xx) [e- <)] ((x),
(13)
where both f and (p are assumed be (nonsmooth) weakly convex functions and lower bounded, i.e., (ar) 2 yb for all æ E dom yp. Classical stochastic optimization methods - including proximal stochastic subgradient, stochastic proximal point, and stochastic prox-liness methods - for solving (13) are unified by the stochastic model-based methods (SMM) [14, 11]:
1 20
x k+1 argmin Sax (xx + soxx) +
| xx112
(14)
where fat (x, ) a stochastic approximation of f around x² using the sample eh: see Appendix F.1 for descriptions of three major types of SMM. Setting F& == o(E 5 5* it easy to that (ar*) Jx20 is adapted to J.20. We analyze convergence of SMM under the following assumptions.
(D.1) The stochastic approximation function fo satisties a one-sided accuracy property, i.e., we have [f (x, <)] f(#) for all æ E U and
Eg(fa( f(y) < " |
all YE,yEU
where U is an open convex set containing dom yp.
(D.2) The function y + fn E) + ply) is 1--weakly convex for all æ E U and almost every &.
(D.3) There exists L > such that the stochastic approximation function fa satisfies
(a. { (y. < L|æ vll V x. y U,
and almost every E.
(D.4) The function oo is -ipssiic continuous.
(D.5) The step sizes (ax) F:2 satisfy Σe= az do and Σx= oz < <0.
Assumptions (D.1), (D.2), (D.3) are standard for analyzing SMM and identical to that of [11]. (D.5) is convention for stochastic methods. Assumption (D.4) mimics (C.3); see Remark 3.3 for discussions.
8

---

We now derive the convergence of SMM below by setting + Venvey and M4 ag. Our derivation based on the following two estimates, in which the proof of Lemma 3.9 is given in Appendix F.2.
Lemma 3.8 (Theorem 4.3 of [11]). Let 0 E (0, (T + n) and or <0
0 be given. Then, we have
(1 - [T + 7)0)ax Venvow
2L
Elenvvo (x (x*+1) Fil] S env)
2(1 maa)
(1-1)aa 10a avs))
Lemma 3.9. For all k with ar 12n)), it holds that
B||| k+ - x² 12| Fu S (16(L + +
Phase I: Verifying (P.1)- As before, 121, Corollary 3.4] implies that the mapping Venvoy is Lipschitz continuous for all E (0, (T + -)) Hence, condition (P.1) is satisfied. Using ag - 0, we can apply Theorem B.1 to the recursion obtained in Lemma 3.8 for all l sufficiently large and it follows Ex= ag Venvow
< co. Thus, condition (P.2) holds with a = 2.
Phase II: Verifying (P..)-(P.4) for showing convergence in expectation. Taking total expectation in Lemma 3.9 verifies condition (P.3) with q = 2, (16(L + Lp)² + 8L2). pi = 2, B Moreover, condition (P.4) is true by assumption (D.5) and the previous parameters choices. Thus, applying
Theorem 2.1 gives [|] Venvey(2*" (x**)) 0
Phase III: Veritying (P.3') for showing almost sure convergence. As in (4), we can set A& = ag (w*+1~x'" - 101x-11--
1----120 x* F. B3
El++ x² Fil. Applying Lemma 3.9
0'
and utilizing Jensen's 's inequality, we have B[A F = El |+ A (4/a))B11l
x [l3] <
4(16(L- L2)² + 8L and | S 16(L+ Lb)
8L2. Thus, condition (P.3') is satisfied with
Pı = P2 = 1, 9 = 2. Assumption (D.5), together with the previous parameter choices verifies condition (P.4') and hence, applying Theorem 2.1 yields |/Venve (=))] + almost surely.
Summarizing this discussion, we obtain the following convergence results for SMM.
Corollary 3.10. We consider the family of stochastic model- basel methods (14) for the optimization problem (13) under assumptions (D.1)-DD.5). Let [="]220 be generated sequence. Then, we have lim Ven (x*) 0 and lim Venvooy (x*) = O almost surely.
Remark 3.11. The results presented in Corollary 3.10 also hold under certain extended settings. In fact, we can replace (D.3) by slightly more general Lipschitz continuity assumption on f. Moreover, is possible to establish convergence in the case where f is not Lipschitz continuous but has Lipschitz continuous gradient, which particularly useful when we apply stochastic proximal point method for smooth f. A more detailed derivation and discussion of such extensions is deferred to Appendix F.3.
3.5 Related work and discussion
SGD and RR. The literature for SGD is extremely rich and several connected and recent works have been discussed in Section Our result in Corollary 3.1 unifies many of the existing convergence analyses of SGD and is based on the general ABC condition (A.3) (see [23, 24, 19] for comparison) rather than on the standard bounded variance assumption. Our expected convergence result generalizes the one in [6] using much weaker assumptions. Our results for RR are in line with the recent theoretical observations in [30. 32, 25J. In particular, Corollary 3.2 recovers the almost sure convergence result shown in [25], while the expected convergence result appears to be new
Prox-SGD and SMM. The work [11] established one of the first complexity results for prox-SGD using the Moreau envelope. Under bounded variance assumption (C 0 in condition (C.4) and for general nonconvex and smooth f, the authors showed E[[| [[ll\ennvey (x=")
( + 1//2,, where & is sampled uniformly from the past T iterates x0 ...... TT. As mentioned, this result cannot be casily extended to the asymptotic convergence results discussed in this paper. Earlier studies of prox-SGD for nonconvex f and C 0 include [18] where convergence of prox-SGD is established if the variance parameter D = D -> O vanishes as k + oc. This can be achieved by progressively increasing the size of the selected mini-batches or via variance reduction techniques as in prox-SVRG and SAOX,SAGA, see [35]. The question whether prox-SGD can converge and whether the accumulation points of the iterates {xx* )=20 correspond to stationary points was only addressed recently in [27]. The authors use differential inclusion approach to study convergence of prox-SGD. However, additional compact constraints x E X' have to introduced the model (8) to guarantee sure boundedness of (x* 1220 and applicability of the differential inclusion techniques. Lipschitz

---

continuity of also appears an essential requirement in [27, Theorem 5.4]. The analyses in [14, 12] establish asymptotic convergence guarantees for SMM. However, both works require a priori (almost) sure boundedness of (æ* J220 and a density / Sarddtype condition in order to show convergence. We refer to [16] for an extension of the results [27, 12] to prox-SGD Hilbert spaces. By contrast, our convergence framework allows to complement these differential inclusion-based results and - for the first time - fully removes any stringent boundedness assumption on {a /220 Instead, our analysis relies on more transparent assumptions that are verifiable and common in stochastic optimization and machine learning. In summary, we are now able to claim: prox-SGD and SMM converge under standard stochastic conditions if is Lipschitz continuous. In the easier convex case, analogous results have been obtained, e.g., in [18, 1, 40].
We provide an overview of several related and representative results in Table in Appendix G.
4
Conclusion
In this work, we provided a novel convergence framework that allows to derive expected and almost sure convergence results for vast class of stochastic optimization methods under state-of-the-ar assumptions and in a unified way. We specified the steps on how to utilize our theorem in order to establish convergence results for given stochastic algorithm. As concrete examples, we applied our theorem to derive asymptotic convergence guarantees for SGD, RR. prox-SGD, and SMM. To our surprise, some of the obtained results appear be new and provide new insights into the convergence behavior of some well-known and standard stochastic methodologies. These applications revealed that our unified theorem can serve as a plugin-type tool with the potential facilitate the convergence analysis of a wide class of stochastic optimization methods.
Finally, it is important
investigate in which situations stationarity measure 4 can be strengthened - say to almost sure convergence guarantees for the iterates (ar } k20- We plan consider such a possible extension in future work.
convergence results in terms of the
Acknowledgments and Disclosure of Funding
The authors would like to thank the Area Chair and anonymous reviewers for their detailed and constructive comments, which have helped greatly to improve the quality and presentation of the manuscript. addition, we would like to thank Michael Ulbrich for valuable feedback and comments on an earlier version of this work.
X. Li was partially supported by the National Natural Science Foundation of China (NSFC) under Grant No. 12201534 534 and 72150002, by the Shenzhen Science and Technology Program under Grant No. RCBS202 1000910708011 and by the Shenzhen Institute of Artificial Intelligence and Robotics for Society (AIRS) under Grant No. AC01202101 108. A. Milzarek was partly supported by the National Natural Science Foundation of China (NSFC) Foreign Young Scholar Research Fund Project (RFIS) under Grant No. 121 10140400304 and by the Fundamental Research Fund - Shenzhen Research Institute of Big Data (SRIBD) Startup Fund [CYJ-AM20190611
References
[1] Yves F. Atchadé, Gersende Fort, and Eric Moulines, On perturbed proximal gradient algorithms.
J. Mach. Learn. Res., 18(10):1-33, 2017.
[2] Amir Beck. First-order methods in optimization. SIAM, Philadelphia, PA, 2017.
[3] Dimitri P. Bertsekas and John N. Tsitsiklis. Gradient convergence in gradient methods with errors. SIAM J. Optim., 10(3):627-644 642, 2000.
[4] Axel Böhm and Stephen J. Wright. Variable smoothing for weakly convex composite functions.
J. Optim. Theory Appl., 188(3):628-645) 2021.
[5] Léon Bottou. Stochastic learning. In Summer School on Machine Learning, pages 146-168. Springer, 2003.
[6] Léon Bottou, Frank F. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 322
10

---

[7] Leo Breiman. Probability, volume 7 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. Corrected reprint of the 1968 original.
[8] Guy Cohen and Daoli Zhu. Decomposition and coordination methods large scale optimization problems: The nondifferentiable case and the use of augmented lagrangians. Adv. in Large Scale Systems, 1:203-266, 1984.
[9] Andrew R. Conn, Nicholas M. Gould, and Philippe L. Toint. Trust-region methods. MPS/SIAM Series Optim. SIAM; MPS, Philadelphia, PA, 2000.
[10] J-C Culioli and Guy Cohen. Decompoxttion/coondaatto algorithms in stochastic optimization.
SIAM J. Control Optim., 28(6):1372-14033 1990.
[11] Damek Davis and Dmitriy Drusvyatskiy, Stochastic model-based minimization of weakly convex functions. SIAM J. Optim., 29(1):207-239, 2019..
[12] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D. Lee. Stochastic subgradient method converges on tame functions. Found. Comput. Math., (0(1):119-155) 2020.
[13] Dmitriy Drusvyatskiy and Adrian Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Math. Oper. Res., 43(3):9199944 19-9488 2018.
[14] John C. Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimiza- tion problems. SIAM J. Optim., 28(4):
2018. 2018.
[15] Jianqing Fan. Comments on "wavelets in statistics: A review" by A. Antoniadis. Journal of the Italian Statistical Society, 6(2):331, 1997.
[16] Caroline Geiersbach and Teresa Scarinci. Stochastic proximal gradient methods for nonconvex problems Hilbert spaces. Comput. Optim. Appl., 78(3):705-740, 2021.
[17] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Optim., 2344)2334--2368, 2013.
[18] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Math. Program., 155(1-2, Ser. A):267-305, 2016.
[19] Robert Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 1315-1323, PMLR, 13-15 Apr 2021.
[20] Mert Gürbüzbalaban, Asu Ozdaglar, and P. A. Parrilo. Why random reshufiling beats stochastic gradient descent. Math. Program., 186(1-2):49884, 2021.
[21] Tim Hoheisel, Maxime Laborde, and Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. J. Dyn. Games, 7(1):79-96, 2020.
[22] Ya-Ping Hsich, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-mo min-max optimiza- tion algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning, pages 4337-4348. PMLR, 2021.
[23] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint, arXiv:2002.03329, 2020.
[24] Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE Transactions on Neural Networks and Learning Systems, (1(0))43394 4400, 2019.
[25] Xiao Li, Andre Milzarek, and Junwen Qiu. Convergence of random reshuffling under the Hurdyka-Lojasievv inequality, arXiv preprint, 1r.0v:2110.04926, 2021.

---

[26] 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, pages 983-992. PMLR, 2019.
[27] Szymon Majewski, Blazej Miasojedow, and Eric Moulines. Analysis of nonsmooth stochastic approximation: the differential inclusion approach. arXiv preprint, arXiv: 2018.
[28] Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure convergence of stochastic gradient descent in non-convex problems. Advances in Neural Information Processing Systems, 33:1117-11228 2020.
[29] Andre Milzarek, Fabian Schaipp, and Michael Ulbrich. A semismooth Newton stochastic proximal point algorithm with variance reduction. arXiv preprint, AxXi:22204.00406611 2022.
[30] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffting: Sim- ple analysis with vast improvements. Advances in Neural Information Processing Systems, 2020.
[31] Yu. Nesterov. Gradient methods for minimizing composite functions. Math. Program., 140(1, Ser. 1):125-161, 2013.
[32] Lam M Nguyen, Quoe Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten van Dijk. A unified convergence analysis for shuffling-type gradient methods. J. Mach. Learn., 22(207):1-44 2021.
[33] Francesco Orabona.
Almost sure convergence of SGD on smooth non-convex functions. https: paramttterrree com/ 2020/ 10/ 05/ almost sure- www.ssssueeeeeeeeeeeeeeeeee convergence of- sgdd- on smos ton-tttt-oooo--eeeeeoeo
non- wow.er- 2020.
[34] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM J. Control Optim., 30(4):838-855, 1992.
[35] Sashank. J. Reddi, Suvrit Sra, Barnabas P6ezos, and Alexander J Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. In Advances in Neural Information Processing Systems 29, pages 1 1145-1155 1153, Curran Associates, Inc., 2016.
[36] Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
[37] Herbert Robbins and David Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Optimizing Methods in Statistics, pages 233-257. Elsevier, 1971.
[38] R. Tyrrell Rockafellar. Convex analysis. Princeton Landmarks Mathematics. Princeton University Press, Princeton, NJ, 1997. Reprint of the 1970 original, Princeton Paperbacks.
[39] R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational analysis, volume 317 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer- Verlag, Berlin, 1998.
[40] Lorenzo Rosasco, Silvia Villa, and B. Công Vü. Convergence of stochastic proximal gradient algorithm. Appl. Math. Optim., 82(3):891 997,, 2020.
[41] Othmane Sebbouh, Robert M Gower, and Aaron Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In Conference on Learning Theory, pages 3935-3971. PMLR, 2021.
[42] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning, pages 71-79. PMLR, 2013.
[43] Daniel W. Stroock, Probability theory. Cambridge University Press, Cambridge, second edition, 2011. An analytic view.
12

---

[44] Jean-Philippe Vial. Strong and weak convexity of sets and functions. Math. Oper. Res., 8(2):231-299, 1983.
[45] Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty, Ann. Statist., 38(2):894-942, 2010.
[46] Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the Twenty-Firs International Conference on Machine Learning, page 116, 2004.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations are written in equivalent forms as future works in the conclusion section; see Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We con- duct theoretical investigation about the fundamental stochastic optimization methods, which will not bring any negative socictal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We put them in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "mT4RMS7YFz_", "reviewer": "Reviewer_Nn1D", "summary": "This paper derives general convergence results for stochastic optimization methods. The results include the cases where the cost function is nonconvex and nonsmooth.", "questions": "I have the following questions about writing as well as the nature of the results:\n\n1) Please give an example, before providing your main theorem in Sec. 2, what an abstract convergence measure \\Phi could be.\n\n2) In convex and nonconvex optimization, asymptotic results are somewhat of secondary importance, as nonasymptotic bounds could provide reasonable heuristics to optimize the parameters of optimization methods. Why do the authors provide only asymptotic results in this paper? In other words, what was the difficulty in getting nonasymptotic results?\n\n3) Related to my second question, if authors manage to convert some of these results into nonasymptotic ones, is it clear that the rates of convergence would match standard rates? In other words, someone can derive a very slow convergence rate for these optimization methods (which would all converge in the same way asymptotically), but would not be very useful otherwise.\n\nI would be inclined to reconsider my rating if the authors provide a convincing discussion whether their technique can lead to nonasymptotic bounds.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The approach is general and can be applicable to several settings.\n\nWeakness: The results are only asymptotic and about the gradient norm (as such, not \"global\" optimization results).", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hf3ipPqRNSX", "reviewer": "Reviewer_T2QD", "summary": "The authors analyze the convergence of SGD-like methods such that the norm of the gradient in the last iterate convergence to zero in expectation and almost surely. They provide the general framework to analyze the convergence for SGD-like methods, including SGD, Random Reshuffling, Prox-SGD, and Model-Based methods. Using this framework, they show the convergence of these methods.", "questions": "Suggestion: In the proof of Theorem 2.1, I think that it is possible not to differentiate $q = 1$ and $q > 1$. Can we in (16) use the boundness of $\\beta_t$ and $\\mu_k,$ and then use the same arguments as for the case $q = 1$? This can simplify the proof.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "i) The authors prove the main Theorem 2.1, which generalizes results from, e.g. https://parameterfree.com/2020/10/05/almost-sure-convergence-of-sgd-on-smooth-non-convex-functions/\nor Gradient convergence in gradient methods with errors. Bertsekas et al. \n\nStrengths: The generalization can be useful and give insights into the community.\n\nWeaknesses: Yes, it can help to analyze a broad family of methods, but I think that the paper doesn't have enough examples to be sure that Theorem 2.1 is the \"Unified Convergence Theorem.\"\n\nii) As the authors noted, the last-iterate convergence of SGD and RR was analyzed before, so, qualitatively, the paper's contribution is the analysis of Prox-SGD and SMM.\n \nStrengths: Even the fact that it is possible to prove the convergence of Prox-SGD is interesting. \n\nWeaknesses: To prove the convergence, the authors use Assumption (C.3) that $\\varphi$ is $L$-Lipschitz. For instance, one of the most popular regularizers $\\varphi(x) = \\frac{1}{2} ||x||^2_2$ is not $L$-Lipschitz.\n\nI think the paper is good. It provides proof that Prox-SGD and SMM converge. At the same time, I'm not sure that Theorem 2.1 can be considered the \"Unified Convergence Theorem,\" but it can be helpful for the community.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DbqWoIvnsCx", "reviewer": "Reviewer_qySk", "summary": "This work provides a unified theorem for analyzing several stochastic optimization methods. Both expected and almost sure convergence are derived. For applications, the authors recover the convergence results for stochastic gradient descent (SGD) and random reshuffling (RR). In addition, this paper also obtains the convergence result for the stochastic proximal gradient method (prox-SGD) by using the proposed framework.", "questions": "Is there a typo in assumption (B.2)? Why do you require the sum of alpha^3 < infinity. The description for random reshuffling is rather rough, I would suggest the authors provide more details in the appendix for this method. \n\nSome minors: in line 54 the hessian and gradient, in line 350 analyses. \n\n\nEDIT: after the authors' response, I increased my score to 7.", "limitations": "Yes. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well written and easy to follow in general. The structure of the paper is good and provides some new insights into the convergence results for the stochastic optimization methods. The core theorem 2.1 is very important and its proof makes sense to me. Furthermore, the prox-SGD is analyzed via this framework to obtain some convergence results.\n\nThe main weakness is that the proposed method only provides an asymptotic convergence result, which is less informative compared to the finite-time type of bounds. In addition, the function value convergence might be also interested.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Bel-ZtSDYr", "reviewer": "Reviewer_1j9a", "summary": "This manuscript provides a unified asymptotic convergence analysis framework for several centralized stochastic optimization methods such as SGD, random reshuffling, proximal SGD and stochastic model-based methods. By introducing two sets of general conditions on the abstract convergence measure as well as the sequence generated by stochastic optimization algorithms, they derive both the expected and almost-sure convergence to the stationary points, respectively. The authors then apply this result to the abovementioned algorithms to obtain asymptotic convergence guarantees in the expected and almost-sure senses, which either recover existing convergence results (possibly under weaker assumptions) or generate new results.", "questions": "- On the generality of the proposed framework: To show the generality of the proposed unified theorem, the reviewer would like to see if it can be applied to other recently developed stochastic optimization algorithms that employs variance-reduction techniques and varying sizes of mini-batches.\n- On significance of contribution: It is not very clear how this proposed framework will improve the existing analysis. The reviewer would thus suggests adding a table to compare the convergence results of the existing stochastic algorithms and that obtained from the proposed framework with respect to different assumptions and problem settings to illustrate generality and reveal some insights if any.\n", "limitations": "The generality of the proposed framework is not very clear to the reviewer. The authors are thus suggested to make clear the scope of stochastic optimization algorithms that can be incorporated into this unified convergence analysis.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The main novelty of this paper relies on the generality of the proposed unified convergence analysis based on the abstract stationarity measure \\Phi, which seems new to the reviewer. The major comments are summarized as follows:\n\nStrengths:\n- By introducing general conditions on the abstract stationarity measure \\Phi, their theoretical analysis enjoys high flexibility to recover or complete the expected and  almost-sure asymptotic convergence results of existing stochastic optimization methods under several problem settings, thus is potential to simplify algorithm design and analysis.\n\n- This paper is well written and easy to follow. The convergence analysis for SGD, RR, prox-SGD and SMM methods is clear and reveals some insights among these methods.\n\nWeaknesses:\n- On technical novelty: Since the considered stochastic optimization methods in this work have been well studied, and the proof techniques used in this paper are standard, thus the technical contribution is limited to some extent.\n- On the obtained rate results: For non-convex problems, the convergence to a stationary point of the objective function is not very informative since the result cannot declare any optimality, from this understanding, the obtained asymptotic convergence results in this work are even weaker than the existing iteration complexity results which further shows the  non-asymptotic convergence rates under certain measures.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept