Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods
Authors: Zijian Liu
Zhengyuan Zhou
Venue: ICLR 2024 poster (2024)
Keywords: Convex Optimization
Stochastic Optimization
Last Iterate
Primary area: optimization

Abstract: In the past several years, the last-iterate convergence of the Stochastic Gradient Descent (SGD) algorithm has triggered people's interest due to its good performance in practice but lack of theoretical understanding. For Lipschitz convex functions, different works have established the optimal $O(\log(1/\delta)\log T/\sqrt{T})$ or $O(\sqrt{\log(1/\delta)/T})$ high-probability convergence rates for the final iterate, where $T$ is the time horizon and $\delta$ is the failure probability. However, to prove these bounds, all the existing works are either limited to compact domains or require almost surely bounded noises. It is natural to ask whether the last iterate of SGD can still guarantee the optimal convergence rate but without these two restrictive assumptions. Besides this important question, there are still lots of theoretical problems lacking an answer. For example, compared with the last-iterate convergence of SGD for non-smooth problems, only few results for smooth optimization have yet been developed. Additionally, the existing results are all limited to a non-composite objective and the standard Euclidean norm. It still remains unclear whether the last-iterate convergence can be provably extended to wider composite optimization and non-Euclidean norms. In this work, to address the issues mentioned above, we revisit the last-iterate convergence of stochastic gradient methods and provide the first unified way to prove the convergence rates both in expectation and in high probability to accommodate general domains, composite objectives, non-Euclidean norms, Lipschitz conditions, smoothness, and (strong) convexity simultaneously.

Published as a conference paper at ICLR 2024
REVISITING THE LAST-ITERATE CONVERGENCE OF STOCHASTIC GRADIENT METHODS*
Zijian Liu, Zhengyuan Zhou
Stern School of Business, New York University (z13067, zzhou) estern.nyu.edn
ABSTRACT
In the past several years, the last-iterate convergence of the Stochastic Gradient Descent (SGD) algorithm has triggered people's interest due to its good perfor- mance in practice but lack of theoretical understanding. For Lipschitz convex functions, different works have established the optimal ( log T/VT) or O(Vlog(1 (T) high-probabilltty convergence rates for the final iterate, where T the time horizon and 5 is the failure probability. However, bounds, all the existing works are either limited to compact domains or require almost surely bounded noises. It is natural to ask whether the last iterate of SGD can still guarantee the optimal convergence rate but without these two restrictive assumptions. Besides this important question, there are still lots of theoretical problems lacking an answer. For example, compared with the last-iterate conver- gence of SGD for non-smooth problems, only few results for smooth optimization have yet been developed. Additionally, the existing results are all limited to a non-composite objective and the standard Euclidean norm. It still remains unclear whether the last-iterate convergence can be provably extended to wider compos- itc optimization and oun-Euclidean norms. In this work, to address the issues mentioned above, revisit the last-iterate convergence of stochastic gradient methods and provide the first unified way to prove the convergence rates both expectation and in high probability accommodate general domains, composite objectives, non-Buclidean norms, Lipschitz conditions, smoothness, and (strong) convexity simultaneously.
prove these
INTRODUCTION
In this paper, we consider the constrained composite optimization problem minsex F(x) f(x)+ h(x) where both f(x) and h(x) are convex (but possibly satisfying additional conditions such as strong convexity, smoothness, etc.) and C Rd is a nonempty closed convex set. Since a true gradient is computationally prohibitive to obtain (e.g.. large-scale machine learning tasks) or infeasible to access (e.g., streaming data), the classic Stochastic Gradient Descent (SGD) (Robbins) Monro 1951) algorithm has emerged be the gold standard for light-weight yet effective computational procedure commonly adopted in production for the majority of machine learning tasks: SGD only requires a stochastic first-order oracle δf(z) satisfying [(āf(z) a]] E 0f(x) where O (z) denotes the set of subgradients at a and guarantees provable convergence under certain conditions (e.g.. Lipschitz condition for f(x) and finite variance the stochastic oracle).
particularly important problem in this area is to understand the last-iterate convergence of SGD, which has been motivated by experimental studies suggesting that returning the final iterate of SGD (or sometimes the average of the last few iterates) - rather than a running average often yields a so- lution that works well in practice (e.g., de.g.,/Shalev-ee -Shalev-Shwartz
al. (2007), )) As such, a fruitful line of liter- ature (Rakhlin et al. 2011 Shamir & Zhang 2013) Harvey et al. [019a]] Orabonal 2020 Jain et al.] 2021) developed extensive theoretical understanding of the non asymptotiicc last-iterate conver- gence rate. Loosely speaking, two optimal upper bounds, ((LVVT) for Lipschitz convex functions
AA extended version including more results is available at https://arxiv.or/abs//22 Corresponding author.

---

Published as a conference paper at ICLR 2024
and ((L/T) for Lipschitz strongly convex functions, have been established for both expected and convergence when h(x) = 0 (see Subsection 1.2 for a detailed discussion). How- ever, prove the high-probbiility rates, the existing works rely on restrictive assumptions: compact domains or almost surely bounded noises (or both), which can simplify the analysis but are unreal-
istic in lots of problems. Until today, whether these two assumptions can be relaxed simultaneously or not still remains unclear. Naturally, we want to ask the following question:
Q1: Is it possible to prove the high-probability last-iterate convergence of SGD for Lipschitz (strongly) convex functions without the compact domain assumption and beyond bounded noises?
Compared with the fast development of non-smooth problems, the understanding of the last-iterate convergence of SGD for smooth problems (i.e., the gradients of f (x:) are Lipschitz) is much slower. The best expected bound for smooth convex optimization under X = IR until now is still O VT) due to Moulines & Bach (2011), which is far from the optimal rate O(L/vT) of the averaging output (Theorem 4.2 in Lan (2020). However, temporarily suppose the domain is compact, one can immediately improve the rate from 0(1 /T) to ((1/T)) by noticing that we can reduce the smooth problem to the Lipschitz problem and use the known bounds from non-smooth convex optimization. Hence, one may expect the last-iterate convergence rate of SGD for smooth convex optimization should still be ((1/VT) for any kind of domain. If one further considers smooth and strongly convex problems, as far as we know, no formal result has been established for the final iterate of SGD in general domain except for the expected O1/TT) rate when X' = Rd under the PL-condition (which is known as a relaxation for strong convexity) (Gower et al. 2021: Khaled & Richtárik 2023). The above discussion thereby leads us to the second main question:
Q2: Does the last iterate SGD provably converge in the rate of 0 for smooth and convex functions and O(L/T) for smooth and strongly convex functions in a general domain?
Besides the two aforementioned questions, there are still several important missing parts. First, recalling that our original goal is to optimize the composite objective F(x) = f(x) + h(x), it is still unclear whether- and if so, how the last-iterate convergence of this harder problem can be proved. Moreover, the previous works are limited to the standard Euclidean norm. Whereas, in lots of specialized tasks, it may be beneficial to employ general norm instead of the lg norm to capture the non-Euclidean structure. However, whether this extension can be done remains open. Additionally, the proof techniques in the existing works vary in different settings, which builds barrier for researchers to better understand the convergence of the last iterate of SGD. Motivated by these challenges, we would like to ask the final question:
Q3: Is there unified way to analyze the last-iterate convergence of stochastic gradient methods both in expectation and in high probability to accommodate general domains, composite objectives, non-E Fuclidean norms, Lipschitz conditions, smoothness, and (strong) convexity at once?
1.1 OUR CONTRIBUTIONS
We provide affirmative answers to the above three questions and establish several new results by revisiting simple algorithm, Composite Stochastic Mirror Descent (CSMD) (Duchi et al. 2010). which is based on the famous Mirror Descent (MD) algorithm (Nemirovski & Yudin 1983| Beck & Teboulle 2003) and includes SGD as a special case. Specifically, our contributions are as follows.
We establish the first high-probabilityy convergence result for the last iterate of CSMD in general domains under sub-Gaussian noises answer Q1 affirmatively.
We prove the last iterate of CSMD can converge in the rate of Õ(1 for smooth convex optimization and (LLTT) for smooth strongly convex problems both in expectation and in high probability for any general domain X, hence resolving Q2.
We present a simple unified analysis that differs from the prior works and can be directly applicd to various scenarios simultancously, thus leading to a positive answer to Q3.
'To see why gradients are bounded in this case, we first fix point zo in the domain. Then by smoothness. there is [[x) V f(z))l22 O[I =a for any other point x, which immediately implies [>)]22
O[I - zo la [()o))) O(D + [[o((z))) where D is the domain diameter.
2

---

Published as a conference paper at ICLR 2024
1.2 RELATED WORK
We review the literature related to the last-iterate convergence of plain stochastic gradient meth- measured by the function value gap (see Subsection 2.1 for why we use this criterion) for both Lipschitz and smooth (strongly) convex optimization. We only focus momentum or averaging since it is already known that, without further special assumptions, both operations cannot help to improve the lower order term O(1/vT) for general convex functions and O(1/T) for strongly convex functions. For the last iterate of accelerated averaging based stochas- tic gradient methods, we refer the reader to Nesterov & Shikhman (2015) Lan (020): Orabona &
the algorithms without
Pãl (2021) for in-expectation rates and Davis & Drusvyatskiy (2020); Gorbunov et al. (2020); Liu
et al. (2023 Sadiev et al. 2023) for high-probabilityy bounds. As for the last iterate of stochastic gradient methods for structured problems (e.g., linear regression), the reader can refer Lo|Lei & Zhou
(2177) Ge et al. (2019): Varre et al. (2021); Pan et al. (2022) Wu et al. (2022) for recent progress.
Last iterate for Lipschitz (strongly) convex functions: Rakhlin et al. (2011) is the first to show an expected O(1/T)) convergence for strongly convex functions. But such bound is obtained under the additional assumption, smoothness with respect to optimung meaning their result does not hold in general. Later on, Shaamir& & Zhang (013)) proves the first expected last-iterate rates (log T/vT) and Ollog T for convex and strongly convex objectives, respectively. The high- probability bounds turn out to be much harder than the expected rates. After several years, Harvey et al. (2019a) is the first to establish a sigs-brbbbbility bound in the rate of ( log T/vT) and OTlog(I/a (8) log T/T) for convex and strongly convex problems where ó is the probability of failure. Afterward, Jain et al. (0021) improves the previous two rates O( O(VIoop /lo((1/))TT) and (l)g((/)))/T) but with a non-standard step size schedule. They also prove the expected rates O(I/VT) and (1) under the new step size.
However, a main drawback for the general convex case in all the above papers is requiring a compact domain. To our best knowledge, Orabona (2020) is the first and the only work showing how to shave off this restriction, and thereby obtains an expected O(log T/))) rate for general domains yet it is unclear whether his proof can be extended to the high-probability case or not. Until recently, [Zaaani recently,Zamani & Glineur (2023) exhibits new proof on how to obtain the convergence rate for the last iterate but only for the deterministic case. Lastly, we would like to mention that all of these prior results are built for non-composite objective fx) with the standard Euclidean norm.
Last iterate for smooth (strongly) convex functions: Compared with Lipschitz problems, much less work is done for smooth optimization. As far as know, the only result showing non- asymptotic rate for smooth convex functions dates back to Moulines & Bach (2IIT). in which the authors prove that the last iterate of SGD on TRd enjoys the expected rate 011 (T/ under addi- tional restrictive assumptions (e.g., mean squared smoothness). As for the strongly convex case, the expected rate O11/T)) under the PL-condition (which is known as a relaxation for strong convex- ity) has been established but only for non-composite optimization under the Euclidean norm on the domain X' = Rd (Gower et al. 2021 Khaled & Richtárik 2023).
Lower bounds for last iterate: Under the requirement d T where d is the dimension of the problem, Harvey et al. (2019a) is the first to provide lower bounds 2(lo T/VT) under the step size ((IvVl) for non-smooth convex functions and (2logT/T) under the step size O(1/l) when strong convexity is additionally assumed. Note that these two rates are both proved for deterministic optimization meaning that they can be also applied to the expected lower bounds. Subsequently, when < T holds, Liu Lu (2021) extends the above two lower bounds to 2(log d/VT) (this bound also true for the step size @(1 @(I/VT)) and 2(log d/T) under the same step size in Harvey ct al. (0019)). As a consequence, lower bounds
and (fLog(dAT)/vV have been established for both convex and strongly convex problems under the Lipschitz condition. For the high-probability bounds, Harvey et al. (2019a) shows their two deterministic bounds will incur an extra multiplicative factor (e(log(15)) namely, 2(log(1/5) log T/VT)) and 2(log(1 /5) log T/T). However, under more sophisticated designed step sizes, better upper bounds without the 22oog T) factor are possible, for example, see Jain et al. (2021) as mentioned above.
"To clarify, we mean the algorithm does not contain momentum or averaging operations. < 4 | x"1 Yr e X' where x" argmin
"This means 7L. > 0 such that f(x) f(x")
3

---

Published as a conference paper at ICLR 2024
Another highly related work is Liu et al. (2023). which presents generic approach to establish the high-pro proobbbbabylltty convergence of the average iterate under Sab-Gausiinn noises. We will show that their idea can be further used to prove the ceeb-bbbbbbiltty convergence for the last iterate.
2 PRELIMINARIES
Notations: N is the set of natural numbers (excluding 0). [d] == 21, ,d} for any d E N. a v.b and aAA are defined max {a, and min {a, b). respectively. (::-) is the standard Fuclidean inner product on R.. ||- represents a general norm on 1 and |||||+ + is its dual norm. Given set A C Rd, (A) stands for its interior points. For a function f. fz))) denotes the set of subgradients at æ.
We focus on the following optimization problem in this work min F(x) = f(x) + h(x), DEX
where f and h are both convex. X C int(dom(J)) Rd is closed convex set. The requirement
of X S int(dom(f)) is only to guarantee the existence of (f(z) for every point x in X' with no special reason. We emphasize that there is no compactness requirement on X. Additionally, given di being a differentiable and 1-strongly convex function with respect to || on X' (i.e., v(x) Z (1)) + (Va(yy) x y) + 2/1= y|l2.x,, Vz. y E A the Bregman divergence with respect to & is defined as (z, v) = (xx) vb()) - (Vv(z), x - y). Throughout this paper, we assume that argmingex + (g. x -))
v) + (o(a.)) can be solved efficiently for any g E Rd, E EX, 0.
Next, we list the assumptions used in our analysis:
1. Existence of a local minimizer: 3z* E arg minzex F(z) satisfying F(x") > -00.
(stroonly convex: For k f f and h. 3pu 2 such that (x. y) S k(z))
kwv) - (g,2 v), Va, y E X, E @k(y). Moreover, we assume at least one of (1' (h)) is zero
3. General (I, -smooth:: 3L 2 0, M 2 0 such that f(z) - f(v) (g. x v) S L || ull +
M| yll, Vz, y E X.g ge E 0f(v).
4. Unbiased gradient estimator: For a given x' E X in the 1-th iterate, we can access unbiased gradient estimator g", i.e., [g' [=1 E Of())) where F = o ( 8 E [t] is the o-algebra.
5A. Finite variance: 3o 2 such that |||s* 1
FT S o² where g = g" - -E-EEE -E F
5B. Sub-Gaussian noises: 3o 2 0 such that E [cxp(All<* | Fー s exp(>o²). AA E [0.0-3].
We briefly discuss the assumptions here. Assumptions 1, and 5A are standard in the stochastic optimization literature. Assumption is known as relative strong convexity appeared in previous works (Hazan & Kale, 2014: Lu al. 2018). We use it here since the last-iterate convergence rate will be derived for the CSMD algorithm, which employs Bregman divergence to exploit the non- Euclidean geometry. In particular, when || is the standard & norm, we can take (zx) 1 | to recover the common definition of strong convexity. Assumption 3 is borrowed from Section 4.2 in Lan (2020). Note that both L-smooth functions (by taking M = 0) and G-Lipschitz functions (by taking L = 0 and M = 2G) are subclasses of Assumption 3. Additionally, we remark that Assumption can be further relaxed to the following inequality
f(x) - f(y (g. - y) < (D v) + M M//2 (x, V). X, E (5(),
but without changing the convergence results proved in this paper (see ① and 55 in the proof of Lemma 4.I.. Lastly, Assumption 5B is used for the high-probability convergence bound.
Our proofs for the probabbibbbyl convergence rely the following simple fact for the centered Gabb-Gassiinn random vector. Similar results have been proved in prior works (Vershynin) 2018
et al. 2023). For completeness, we include the proof in Appendix
Lemma 2.1. Given a o-algebra F and a random vector Z E I2d that is F-measurable. if E Rd is random vector satisfying E [ Fl 0 and E (ex((\|)(112) [F] I exp()o²), VA [0, -=
then
E (exp ((E
F < exp (031)2
Rigoooussy speaking, y should he in in)(X)). But one can think X C (nt(oo)()))) avoid this issue
4

---

Published as a conference paper at ICLR 2024
2.1 CONVERGENCE CRITERION
We always measure the convergence via the function value gap, i.e. F(z) F(x*). There are several reasons to stick to this criterion. First, for the general convex case, the function value gap the standard metric. Next, for strongly convex functions, the function value gap is always stronger
(F measurement than the squared distance the optimal solution since || (FF==(((()FF(r")) F(x*))
holds by strong convexity. Even if F(x) is additionally assumed to be (I., 0)-smooth (e.g. f(x)
(I, Om-mmothh and h(x) 0), the bound on | x=1 cannot be converted the bound on
F(x) F(x") since F(z) F(x")= I (VF(2*),
x²) + 111x===11
(x
a || x² I12), which is probably worse than O( xx x²1 as x- only a local minimizer
meaning (=)x")) | possibly to be non-zero. Moreover, the function value gap is important in both
the theoretical and practical sides modern machine learning (c.g., the generalization error).
3 LAST-ITERATE CONVERGENCE OF STOCHASTIC GRADIENT METHODS
Algorithm Composite Stochastic Mirror Descent (CSMD)
Input: x² X, m 0, E [T]. for / = to T do
x [+1 = argmin xx + ( x²) + Dz(z,x))
Return T+
The algorithm, Composite Stochastic Mirror Descent, is presented Algorithm When h(z) = 0, Algorithm degenerates to the standard Stochastic Mirror Descent algorithm. If we further consider the case T- ==-1-|1a 1|- Algorithm| can recover the standard projected SGD by taking v)(x) = 1 || We assume T > throughout the following paper avoid some algebraic issues in the proof. The full version of every following theorem with its proof is deferred into the appendix.
3.1 GENERAL CONVEX FUNCTIONS
In this section, we focus on the last-iterate convergence of Algorithm Toor general convex functions (i.e., 2 = 14 0). First, the in-expectation convergence rates are shown Theorem 3.1 Theorem 3.1. Under Assumptions 1-4 and 5A with Jz
1h 0:
(V
T is unknown, by laking 2L A v
1L [T)
with 1j 0
Dola xx') M
there is
L.D (x (x*,
+ (M + o) Dul x log
E F so
T
VT
I is known, by taking 7)- 2T.
1
Vt [T]
with 17 0
Da(x
there is
/T
(M
(Dolo*,') T
(M (M + (M+o)y Dillt xr /
log T
E ((((TTt)--F(() 5o
VT
Before moving on the high high-probability bounds, we would like talk more about these expectation convergence results. First, the constant 17 here is optimized to obtain the best dependence on the parameters M, and (x ).)). Indeed, the last iterate provably converges for arbitrary n but with worse dependence on M, and (x (x" .²2). We refer the reader Theorem C.1 in the appendix for full version of Theorem 3.1 with any 17 > 0.
Next, by taking L = O, we immediately get the (nearly) optimal Õ(1VVT) convergence rate of the last iterate for non-smooth functions. Note that our bounds are better than [Shamir & Zhang (2013) since it only works for bounded domains and non-composite optimization. Besides, when considering smooth problems (taking M 0), best knowledge, our O(L/T++
+ t/VT) bound
5

---

Published as a conference paper at ICLR 2024
is the first improvement since the ( TT) rate by Moulines & Bach (2011). to Moulinees & Bach (201T), Theorem 3.1 nol on some restrictive assumptions like bounded stochastic gradients x= being global optimal point but is able to be used for the more general composite problems. Additionally, it is worth remarking that the OLL +o/v/T+ rate matches the optimal O rate for the averaged output æ Zang extra logarithmic factor. Notably, our bounds are also adaptive to the noise in this case. In other words, we can recover the well-known (L/TT) rate for the last iterate of the GD algorithm in the noiseless case. Last but most importantly, our proof is unified and thus can be applied to different settings (e.g., general domains, (L, MM -mmoothnnsss, non-Euclidean norms, etc.) simultaneously.
Moreover, compared
xT+1 = (Ei r')/T (Lan 2020 up to an
Remark 3.2. OOraoona (2020) exhibited a circuitous method based on comparing the last iterate with the averaged output show the expected last-iterate convergence for non-composite non-smooth convex optimization in general domains. However, it did not explicitly generalize to the broader problems considered in this paper. Moreover, our method is done in a direct manner (see Section 4
Theorem 3.3. Under Assumptions 1-4 and 5B with ja = pd and let E (0, 1):
T is unknown, by taking 7)t probability least 8, there is
N VI E V
[T) with "f
e (v
Dol x1)) M2+a2 )
then with
22
LD xt)
(M v log ) Do (x*, Ds( aa)llogg T
F(IT+1)- (0r7)-F((x7)) F(x))
T
VT
T is known, by taking Tt 2T,
1
vt E [T] with 17 = θ (V Pa xx
then with
VI
(M?+0²
log t) log
probability at least 8, there is
(M + a log 1) / Des (xt, xt) log LDu(x",z)) x²)) T
((I So
VT
In Theorem 3.3
we present the high-probability bounds for (L, -smoooh functions. Again, the constant y) is picked to get the best dependence on the parameters M. Dw (x, and log(1/0). The full version of Theorem 3.3 with arbitrary 1). Theorem C.2] deferred into the appendix. Com-
pared with Theorem 3.1 the high-probability rates only incur an extra O( log 1/0)) factor (or
(og(1/0))
(llo((1/8) for arbitrary y). which is known to be optimal for L = 0 (Harvey et al. 2019a)).
In contrast to the previous bounds (Harvey et al. 2019a Jain al. 2021) that only work for Lipschitz functions in compact domain, our results are the first to describe the high- bigh-probbbility behavior of Algorithm 1 for the wider (L, -smoothh function class in general domain even with sub-Gaussian noises, not to mention composite objectives and non- Non-Faclidean norms. Even in the special smooth case (setting M = 0), as far as we know, this is also the first last-iterate high-probability bound being adaptive to the noise a at the same time for plain stochastic gradient methods. Unlike the previous proofs employing some new probability tools (c.g., the generalized Freedman's 's inequality high- gigbprrobability argument is simple and only based on the basic
in Harvey et al. (2019a), property of sub-Gaussian random vectors (see Lemma 2.I). Therefore, we believe our work can bring some new insights researchers to gain better understanding of the convergence for the last iterate of stochastic gradient methods.
3.2 STRONGLY CONVEX FUNCTIONS
Now we turn our attention strongly convex functions. Due the space limitation, we only provide the results for the case of μ > 0 and = O. The other case, of = 0 and μ4n > 0, will be delivered in Appendix D.2
Theorem 3.4. Under Assumptions 1-4 and 5A with μy > and μn 0, let Ky =
L 2 Ps
T unknown, by taking either Tt MT(e42N9)' Vt E [T'] or ne 17(++144977
Vt E [1], there is
0 LDo(u" ,x') + (202 log
n) ()(t+2n)] Vt E [T] 2
E [(( - -F(x")
Ms((+N))
L(lter)Dole" ,ath) + (A52 +0 + log [(T+x()
") mou+i+iNg) 1A E [T)
My +T())

---

Published as a conference paper at ICLR 2024
t=1
2y(1+2e7)
If is known, by taking f
2 SEtST,VLe E [T] with := 1.5 and r = -
1y(9++2r))
2
12
myl1-T+2+axx)
there is
LD (x ,x'
(M² + 0²) log T
E ( 0o
+
T 34-dky
MT + +kz)
exp
The in-exeectation rates are stated in Theorem 3.4 where the constant 1) 1.5 is chosen without any special reason. Generally speaking, it can be any non-negative number satisfying 1) + KK > 1. The interested reader could refer Theorem D.I in the appendix for completed version of Theorem
3.4 We would like to remind that Ky 2 is not necessary as we are considering the general
(L, .M) - functions. Hence, it can be zero.
As before, we first take L = 0 to consider the special Lipschitz case. Due to Ky =0 now, all bounds will degenerate Olog T/T), which is known be optimal for the step size 1/uye (Harvey al., 2019a) and only incurs an extra (log T) factor compared with the best D(1/T) bound when is known (Jain al., 202T). We would also like to mention that Theorem 3.4 the first to give the in-expectation last-iterate bound for the step size (t+)) Interestingly, the extra O(log T') factor appears again compared the known (1/TT) bound on the function value gap for the non-uniform averaging strategy under this step size (Lacoste-Julien et al., 2012). Besides, [acoste--Jliie Jullin et al. 2012) also shows
|| - x [2]] = O(//T). Whereas, it is currently unknown whether our E [F((xT+1) - =((=)))))(())))) = Ollog T T/T) bound can be improved to match the O(1/T) rate or not.
For the general (L, M.)MMM)smooo case (even for (L, 0)- smoothness), our bounds are the first conver- gence results for the last iterate of stochastic gradient methods with respect to the function value gap"] Remarkably, all these rates do not require prior knowledge of M or a to set the step size. In particular, the bound for known T is adaptive to a when M 0, i... it can recover the well-known linear convergence rate O(exp(-T/e)
when a = 0.
Theorem 3.5. Under Assumptions 1-4 and 5B with μ 0 and pn O, let Ky E (0,
L. My
0 and
If T is unknown, by taking either πpe py(4+2R)) Vt [T] t py((ti+dxy) Vt [T] then with probability at least 5, there is
My (1(1=x)) (M² lox t)
T7c = #)lt+2ey) Vt E [T]
F(a"t1)-F(27) F(x))) <
My My (T++x()) (2 (a02+0* log log T My (T++x))
0
1) m/(1+++xx,)* Vt [T]
T(I+xj)
t= 2 t < ",,,tee [T] with ny 1.5 and T == [
(y(1+22a))
If'T is known, by taking nt
My 1y(n+2257
t2
1y((-T+2+-4mg) -
then with probability at least 1
8, there is
[1f(1 (1g) Kig) Dp("", xx))
(M2 + o² log log MT + kz)
F(x"-11) -F(=)))-((x>))) 5o 5O
+
T
exp
3+1kg
To finish this section, we provide the high-probability convergence results in Theorem 3.5 Again, the constant = 1.5 is set without any particular reason. The full statement with general 7/. Theorem D.2 can be found in the appendix. Besides, K2 is possible to be zero mentioned above. Compared with Theorem 3.4 only an additional O 1/8)) factor appears. Such extra loss is known to be inevitable for 0 due to Harvey et al. (2019a).
'Note that the rates under the PL-condition (e.g.. Gower et al. 2021 Khaled & Richtárik 2023 ) are incompatible with our settings since they can be only applied to non-constrained, non-composite and (7. 0)- smooth optimization problems with the Fuclidean norm.

---

Published as a conference paper at ICLR 2024
For the Lipschitz case (i.e.. L Kg. 0), by noticing (x OOM2 /n3 To all of these
bounds will degenerate (llog(1/o) log T/T) matching the best-known last-iterate hound proved by Harvey et al. (019a)) for the step size 1/1rt. For the step size 2/j, 1), |Havvey et ( 9h) has proved the high-probability bound ( (log(1/))) (T)) for the non-uniform averaging output instead of
(201
the last iterate. Hence, as far as we know, our high-probability rate for the step size (/+))++1) is new. However, we would like mention that our bound for known T is worse by logarithmic factor than Jain et al. (202I). though, which assumes bounded noises.
Finally, let us go back to the general (L, -smooth case. To our best knowledge, our results are first to prove the last iterate of plain stochastic gradient methods enjoying the provable high-probability convergence even for the smooth case (M~ O). Hence, we believe our work closes the gap between the lack of theoretical understanding and good performance of the last iterate of SGD for smooth and strongly convex functions. Lastly, the same as the in-expectation bound for known T in Theorem 3.4 our highh-robabiilty bound is also adaptive to when M- = 0.
4 UNIFIED THEORETICAL ANALYSIS
In this section, we introduce the ideas in our analysis and present three important lemmas, all the missing proofs of which are deferred into Appendix B
The key insight in our proofs is to utilize the convexity of F(x), which is highly inspired by the recent work (Zamani & Glineur 2023). To be more precise, using the classic convergence analysis for non-composite Lipschitz convex problems as an example, people always consider to upper bound the function value gap f(=²) f(x") (probably with some weight before it) then time to obtain the ergodic rate. Whereas, in such an argument, convexity is not necessary in fact (except if one wants to bound the average iterate in the last step). Hence, if the convexity of can be utilized somewhere, it is reasonable to expect last-iterate convergence guarantee. Actually, this thought is possible as shown by Zamani & Glineur (2023). in which the authors upper bound the quantity f(x²) f(=") where z' is a carefully chosen convex combination of other points and finally obtain the last-iterate rate by lower bounding - -==²) via convexity. More precisely, suppose 2x = =ff²* + Ee= a' where at 2 0, Vs E {0) U [t]. Vt E [T] satisfy Ex= of = 1, Vt E (T]. then there is - -f((²) 2 -aaJ(x") - ==1 (ar"()) by the convexity of f. By properly picking o', one can finally bound/ f(x)) f(xx) as proved by Zamani & Glineur (2023).
them over
Though Zamani Glineur (023) only shows how to prove the last-iterate convergence for deter- ministic non con-compo Lipschitz convex optimization under the Euclidean norm, we can catch the most important message conveyed by their paper and apply to our settings. Formally speaking, we will upper bound the term F(x F(=') for a well-designed z' rather than directly bound the function value gap F(x-11) - F(x*). ). This idea can finally help us construct a unified proof and obtain several novel results without prior restrictive assumptions. By careful caleulations, the new analysis leads us to the following most important and unified result, Lemma 4.1
Lemma 4.1. Under Assumptions
1-3, suppose V) S LLVIy, VI E (T] and let Yt =
Ne IT:=2 1+th% Vt [T]. if w, 2 0, [T] is non-increasing sequence and v 0 is T-ayn WT
defined as U = Σ. W.r."
Vt E [T] and un = Un then we have
WTTFe T1) F(x"))
Swn(1 ppm)en Ds (0",x'x) x²) + Σ 2w + +1551112)
T (et = 1-1 x²)+ + Σ
T
+
wy 2
(w: w w1-1)r(11 - 1 xxt),
1=2
where 5t = g E
Vt E [T] and 2
D.=1
ve- Vt (0) [T].
Let us discuss Lemma 4.1 more here. The requirement of the step size n7 having an upper bound 1/2IVR common in the optimization literature. It is used to ensure we can telescope sum some
TThis holds now due to "=|l== x 11 pt Dx xx) s M||a" x'1l-
8

---

Published as a conference paper at ICLR 2024
terms. For the special case μ M4 0, it degenerates to 7/.- 5 naturally shows up considering stochastic optimization. The most important sequences are we; Up and 2f. As mentioned above, the appearance of 2f is to make sure to get the last-iterate convergence. For how to find such a sequence, we refer the reader to our proofs in Appendix B for details.
We would like to say more about the sequence Wi before moving on. Suppose are in the de- terministic case temporarily, i.e., ç = 0, then a natural choice to set w; = 1, vt E [T] to this the correct choice even for the following
remove the last residual summation. It turns in-expectation bound in Lemma 4.2] So why do we still need this redundant wy? The reason is that setting W, to be one not enough for the bigh-probability bound. More precisely, we still choose we = 1, vt E [T], then there will be some extra positive terms after the concentration argument in the H.H.S. of the inequality in Lemma To deal with this issue, we borrow the idea recently developed by Liu et al. (2023). in which the authors employ an extra sequence wy to give clear proof for the high-probability bound for stochastic gradient methods. We refer the reader Liu et al. (2023) for detailed explanation of this technique.
I VE E [T]] and let Tt = Lemma 4.2. Under Assumptions 1-4 and 5A, suppose Ny S ILVAy
N: II 11 ,t E (T], then we have 1-
E [ - F(x*)]] (1- (Lmm))Do(o"aar x!) 2(M2 + +
Et. 72
2e=t Y
Suppose Lemma 4.1 holds, Lemma 4.2 is immediately obtained by setting wy 1t E [T] and using Assumptions 4 and 5A. This unified result for the expected last-iterate convergence can be applied many different settings like composite optimization and non-Euclidean norms without any restrictive assumptions.
Lemma 4.3. Under Assumptions 1-4 and 5B, suppose Tn I 21vay: Vt E
[T] and let " =
1 Vt E [T], then any ò E 1), with probability at least - 8, we have I1 1-pym
F(x - -a0-)-FF(+"""" F(x") <2
1
max 221ST 1 1197lt
D D+( + (M² (M²+0 -f2+02 (3(11 2og 2)
))
T
7e
Σ
Σ e=t Ys
To get Lemma 4.3
we need some extra effort to find the correct wy and invoke a simple property of uub--Gassiin random vectors (Lemma 2.I). The details can be found Appendix B Compared with prior works, this unified bigh-probbbility bound can be applied to various scenarios including general domains and sub-Gaussian noises.
Equipped with Lemma 4.2 and Lemma 4.3 we can prove all theorems provided in Section 3 by
plugging in different step sizes for different cases.
CONCLUSION
In this work, we present a unified analysis for the last-iterate convergence of stochastic gradient methods and obtain several new results. More specifically, establish the (nearly) optimal con- vergence of the last iterate of the CSMD algorithm both expectation and in high probability. Our proofs can not only handle different function classes simultaneously but also be applied to com- posite problems with non -uclldeld norms on general domains. We believe our work develops a deeper understanding of stochastic gradient methods. However, there still remain many directions worth exploring. For example, it could be interesting to see whether our proof can be extended to adaptive gradient methods like AdaGrad (McMahan & Streeter 2010 Duchi et al. 2011). We leave this important question as future work and expect it to be addressed.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work is generously supported by the National Science Foundation grant CCF-2106508. Zhengyuan Zhou would also like thank the 2024-2025 NYU Center for Global Economy and Business faculty grant and the NYU Research Catalyst Prize. We also thank the anonymous review- ers for their constructive comments and suggestions.
Ethics Statement: This is a theory work. Hence, there are no potential ethics concerns.
Reproducibility Statement: We include the full proofs of all theorems the appendix.
REFERENCES
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):677-75,, 2003.
Damek Davis and Dmitriy Drusvyatskiy. High probability guarantees for stochastic convex opti- mization. In Conference on Learning Theory, pp. 141 1411-1427. PMLR, 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
John Duchi, Shai Shalev-Shue Shwartz, Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In COLT, volume 10. pp. 14-26 Citeseer, 2010.
Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. Advances in neural information processing systems, 32, 2019.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Sys- tems, 33:15042-150533 2020.
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. International Conference on Artificial Inteli- gence and Statistics, pp. 1315-1323, PMLR, 2021.
Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non- smooth stochastic gradient descent. In Conference on Learning Theory, pp. 1579-1613. PMLR, 2019a.
Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent. arXiv preprint arXiv: / 111999990000 008400 2019b.
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.
Prateek Dheeraj M. Nagaraj, and Praneeth Netrapalli, Making the last iterate of sgd information theoretically optimal. SIAM Journal on Optimization, (1)) 108- 1130, 2021. doi: 10.1137/ 19M128908X. https: http:://doooooogg//// 11371/..1///1111111111111 000111311111190000
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
net./
forum? (rrrum??ddAAUAqHNN2E. Survey Certification.
Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method. arXiv preprint 122.2212 2012.
Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
10

---

Published as a conference paper at ICLR 2024
Yunwen Lei and Ding- Xuan Zhou. Analysis of online composite mirror descent algorithm. Neural computation, 29(3):825 0118255860,222 2017.
Daogao Liu and Zhou Lu. The convergence rate sgd's final iterate: Analysis on dimension dependence. arXiv preprint arxiv:2106. 2021.
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning, pp. 21884-21899 21914. PMLR, 2023.
Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first- order methods, and applications. SIAM Journal on Optimization, 28(1):333-333 2018.
H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In Conference Learning Theory (COLT), pp. 446..56. Omnipress, 2010.
Eric Moulines and Francis Bach. Non-asymplotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
Arkadi Nemirovski and David Yudin. Problem complexity and method efficiency in optimization. Wilee--ntersciencee, 1983.
Yu Nesterov and Vladimir Shikhman. Quasi-monotone subgradient methods for nonsmooth convex minimization. Journal of Optimization Theory and Applications, 165(3);917-940, 2015.
Francesco
Orabona.
Last
iterate
of sgd converges (even unbounded do-
mains). 2020.
URL
cest-iterate of sgd converges even in unbounded domaains//maaa///////
Francesco Orabona and Dávid Pál. Parameter-free stochastic optimization of variationally coherent functions. arXiv preprint arXhv:2102.00236 2021.
Rui Pan, Haishan Ye, and Tong Zhang. Eigencurve: Optimal learning rate schedule for SGD on quadratic objectives with skewed hessian spectrums. In International Conference on Learning Representations, 2022. htlphtts: httt:p:://ppenreiiee http:/iwwwww..eeeeeeeeeee net nett/Eorumml--rrAAlllle
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv: 100.5667 2011.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probabilityy bounds for stochas- tic optimization and variational inequalities: the case of unbounded variance. arXiv preprint arXiv:2302.00999, 2023.
Shai Shalev-Shwarzz Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub-gradient solver for svm. In Proceedings of the 24th international conference Machine learning, pp- 807-814, 2007.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In International conference machine learning, pp. 71-79. PMLR, 2013.
Aditya Vardhan Varre, Loucas Pillaud- Vivien, and Nicolas Flammarion. Last iterate convergence of sgd for least-squares in the interpolation regime. Advances in Neural Information Processing Systems, 34:21581-21591, 2021.
Roman Vershynin. digeensimmnio probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Jingfeng Wu. Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. In International Conference Machine Learning, pp. 24280-24314, PMLR, 2022.

---

Published as a conference paper at ICLR 2024
Moslem Zamani and François Glineur. Exact convergence rate of the last iterate in subgradient methods. arXiv preprint 2rx11:2300.11134, 2023.
12

---

Published as a conference paper at ICLR 2024
A PROOF OF LEMMA 2.1
Before giving the proof of Lemma 2.1 we need the following property of sub-Gaussian vectors.
This result is already known before (see Vershynin (2018)) We provide a proof here to make the paper self-consistent.
Lemma A.1. Given a o-algebra F, if E I' is a random vector satisfying E [exp(A|<<(33) F S
xx [0,0-7 then for any integer k 2 1 we have
E [[EE]
2k [F] S
((l:))22k
k 2 2
Proof. For the case ls 1, given any À E [0, o there is
exp (E [ F))
EE [exp (AI Fl S exp((o0)) + EE [[[|]] F S o².
For A: 2 2, we have
E
[||E|] 2* F E
2kt
1 |||El| 2 t dt F
/
2ht2
E [1 [|EE|| 2 f dt
0
Texp(o (||(11)
(a)
2k 1E
exp(o 2(2) F
dt
2ekt2h-1 11 expl-o -(2) dt
0
(M)
eko
2k k-1 exp(-s)ds = eko 28 T(b) = e(k!) 2N
where (a) is by TE [exp(o - 2||s!??) [F] S exppo-2200 = e and (b) is by the change of variable t t= =/s
Now are ready to prove Lemma 2.1
Proof of Lemma
2.1 Note that
E eepp ( (E, 2)) Fl
(15, 2)
|K M k!
E
(E, Z) +
|
TE [E, 2) F E
F
k!
2
(4) E
00
|I 2 ZZ|
||
|
F
(2k))
(2k + 1)!
(6)
|
22 (2k)
||<|12 |2] 2k + || 2 | 2 /4
S E
(2k + 1)!
2|
(2k + 131 ) 1
1
EE
|| 2k
|
4(2k- - 1}1 + (2k))
+
3
2=
2 1|
+ k/22 + 1/(2k + 1)
-E
+
|| 2k
12
|F
3
(2k)
k=
2
(c)
2
2k
|2| 2k
c(1 + k/2 + 1/(2k + 11)
S1+
3
h!
(2t)
k=2
(1)
2k
1
51+021
1
+
exp (0 (211211)
where (a) is by E (E. Z)
F [E
F1,2) = 0. (6) holds due to AM-GM inequality, (c) is by 2k
applying Lemma A.I to E
1 = || 2 [|K Fl and (d) is by 2/3 < 1 and
e(L 1:2 4/2 1/ + 1)) e(++++17 1/5)
max k22,
2k
< 1.
k
13

---

Published as a conference paper at ICLR 2024
B MISSING PROOFS IN SECTION
In this section, we provide the missing proofs of the most important three lemmas.
B.1 PROOF OF LEMMA
Proof of Lemma iary sequence
4.1 Inspired by Zamani & Glineur (023), we first introduce the following auxil-
se-1
x²
pe-1
E [T]
00
x Us
V--1
ve
+
vA
{0] [T)
1=0
V1
U2
where we recall that v
WT
0, VE [T] and uo U1 are non-decreasing. Note that z'
Die 7.7o
always falls in the domain X' because is convex combination of x², ,.,,... .,,,...aa xf that are in X.
Now, we start the proof from the (L,M) (L.M)-smotthhme
smmoothness of f.
1(att)) - 1(x²) S(g x. 1+ - x²) | - x. r²112 212 + M Ml x'll
= 1E', x² - -x²> + 15" x² - - x1t + (0', rttl - =z¹)
-
11
(g': -z) + L llalt1 1212 + M 1|
xy)
x² ||.
(1)
where g¹ = E | [t-1] E (z') and 5¹ g' g'. Next, we hound these four terms respectively.
For term I, by applying Cauchy-Sch Schwarz inequality, the I-strong convexity of 1b and AM- GM inequality, we can get the following upper bound
= S IIE' /2D (at ,xt) s 2m Do(att), ,x')
S
(2)
41/c
For term II, we recall that the update rule x²+1 argmin + (0'xx - x²) +
(=(a,=") Hence, by the optimality condition of x++1 there exists het1 E ah(x*+1) such that for any y X
(1 + Vib(x(t2) Vib(xt) r+1 -y) s 0,
which implies
(bb(2*)) Vib(z++1), x0 - 1) + +th (1h-111
0 ++1 8) 5
1 . - x²11)
11t
Du(y.x") D (y,, (1,, Dur(xt11 ,,xt)
+ h(y)) - M(x411)))))) - u4h Du:
n
where the last inequality holds due to (Vi(at)- - Veb(otl)), 2011 - y) = D (v, De (y, x++1)- Do Ds (xf+1, x²)) and (h++1, x(t1) < h(y) h(x++1((+))))))))))))))()))))h un (WH x
by the ps-strong convexity of h. We substitute y with 2² to obtain
+ M(xx) h(x++1)) un (2t , ol11). II Dels' ( (x (1x)
(3)
For term III, we simply use the ss-oong convexity of f to get
| ((=²) f(x²) 1y (s
14

---

Published as a conference paper at ICLR 2024
For term IV, we have
IV < LD (z'+) ,x¹) + M v (2 ,x1)
< LD ,x4) + M2 + Du (o(xttt 20t) x0))
(5)
where the first inequality holds by the 1-strong convexity of ab again and the second one is due to AM-GM inequality.
By plugging the bounds
(
into 3). and 5
we obtain
f(xtt1)- - f(x²)
5(5, 2¹ x²)) + 2nellls11 + Dalatt1 .xa)
4f/c
+ Delet x24) - (e(lt,x*+11 Do (2 ,0)) xt) + h((a)) -((e+t1) - pn Dola', attt)
"1
+ +f((2) f(x²) - HyDo(z', + (eett ,00) 21 D Dolatti, ,00)
41/c
Rearranging the terms to get
1 FF(x))
<(E, x² -x²) + -1y) xt) ) -(15 + pn) ('s
+ (( 211 Dolx''! ,x²) + 221 11(51112
1)
(a)
(5t 2² - x²) + (nT² - ( xx²) - (m5 1 + pn) x2 + 2n + 115"
(b) 1-1 (5', z² - x²) + (nt" De (2 x²) ( + Di) xl + 2712 + +11=1113
Ur
1-1 (g', 2-1 - x²) + (vt² us) 1t-1 - (2 xx²) - (mr + pn) (=) + 2m 2m + 1131
Ct
(6)
where (a) is by T/ S
1 < + Vt E
[T]
1
S 0, (b) holds due to the definition of
ZLVRY
2%p.
zt 1 1 x² +
111 implying 2t -²
2
(2211- (2* (c) is by noticing n) V
z²),
v2
vi
m
2LVHY < 1 Vt [T]
+ Th μ 2 and
My
Do(ef,xt)
(d)
(1-" _61
De
+ "o-1 1x ,0,) = Ut-1 Dos (2 (2
Vz
Ve
where (d) is by the convexity of the first argument in D (.)).
15

---

Published as a conference paper at ICLR 2024
Multiplying both sides of (6) by w (all of these three terms non-negative) and summing up from t 1 to T, we obtain
o (F(xtt))-114
ty 76 1 18 20 - x²) + 2wre + 115*)113
T
Σ
we're (1 / (=( ,0²) - wirl + pa)ee De (z=,, s(t1)
T
-wiman -
- (1T + mm)uTD xx x1 + Σ
2wr + +115%113
T
T w 1 1 18-t,2² 1-1 20 - x²))
(wrr(ne -11) 1--11-111 (1 + pn)) 1D-1 x0)
#1 (1 1o x²²) W pO)TT D , Σ 2w + (1E5
T
T
W 15 x-1 - xx²)+
Σ (w - 11-1) - p5) 1 (x+ ,x²);
where (e) holds due to 71 71 - 11)) = m (1/ - 14))
upl, 20 = x² and 7p (y) -1 - 11)) =
(o - #f) 1+p47--1
1-py90 = (n-1 + pM pn)Me II:-2
1
1-pp 7 + PA), Vt 2 2.
By the convexity of F and the definition of x' 12 + + x=1 "o- x² (which means x' is a con- vex combination of x², ,,,,,,,.. ,.,,... xx' by noticing that the weights summed up to 1 and nonnegative since 0t Vt E {0} U (7] is non-decreasing), we have
F(2*) S
UD F(**), 0/ U F(x*)
14
12
which implies
whae (F(xtt1-- - -F(3')
Wi7tiF F(x: (1) 1477 Σ Us ()-1) + n0 ((a)))))) ]
T Σ
wy (F(x+t1) F(x*))
Wiff Σ
- 20--) - F(x*))
mml
T
-TTTeT (F(x F(x*)) -
Σ
(21 vo) (F(xt) - F(x*))
1=/
Σ
Σ Ws7/s
(wr (w--00-)) (F(ot)-F(ss) F(x*))
10-176-196-1-
Now by the definition of 0 ET_ Wo7e
WTTT
Vl E [T] and no = vi, we observe that
T
Σ
Wo7t
(1) - up) = 0,
1=/l
16

---

Published as a conference paper at ICLR 2024
and for 2 2
T
Wt-
Σ WoYss
(oz
141
T
WaYs
V/-1
is
s=|-1
T
T
WT
Σ
woys
WT
Σ
Es=t-1
Wsys
E Wsys
T
s=
-0.
These two equations immediately imply
T
Σ
wer (F(x F(=1)) 2 wrYTOr (F(xT+1) - Fxx)))
(8)
Plugging
we finally get YTUT (+1 F(x*))
into
T
Swi (1 HommooD x²) WTTT(1T + pn)er x +
T+1)
2 +
(N +169111)
t=1
T
Σ 15 - -x')
(wr Wi -
t=2
<wi (1 wom)oo xxt)
2w (M² + +115(113)
+
w 211 x²) +
(w w w 1 22(t_11,x"
t=2
B.2
PROOF LEMMA
4
Proof of Lemma
4.2
We invoke Lemma 4.1
with 1, vt [T] to get
YrUT (F(xT+1)- F(z*))
T
<(1 - p (x( "a""",""" x²)) +
2 +11(11 + Σ
7t -11-11 (6', 20,21-1 19).
Taking expectations both sides to obtain
Fr [F(xT+1) F(x*)]
<(1 - Dy x²) +
2nono ( [15+111) + Σ
+E
m00-1B ((5))
2-1 x')]
<(1 - (11-umm)eoDpee x ) +
Σ (M2
1=1
E [E 1 | F[-1]] S o² (Assumption 5A) and x²) (2t-1 x² E Ft-1 and Assumption 4). Finally. we divide both sides by TrUr and plug in Σ w.
where the last line is due to E [| ---1 2²) E (E [ .2-1
, 20977
1)
7T VL E [7] and vo en to finish the proof.
Ey
17

---

Published as a conference paper at ICLR 2024
B.3
PROOF OF LEMMA 4.3
Proof of Lemma 4.3 We invoke Lemma 4.1 to get
WTYrer (F(x++1) - F(x"))
T
Sw - D ( ;0) +
Σ
2n o 115))12)
W 1-1 x²) +
[wn wi---ii- -uy)oz- ,x)).
(9)
1m2
Let we, VI E [T] be defined as follows (note that wn is also well-defined as w1 D. 27.
W4
4 E [7).
(10)
E
2r,0.0,0²
E._ 27.00 0
I 1-
where
1/
TT
1I E
[T]
and 01
C0.
(11)
s=
Note that w/ 2 0, E [7] is non-increasing, from the definition of 02 no = 01, there are always
Vt E [T] and
UT
T. Vt E [T] and 20 To.
(12)
ss WeYe
Es %
Now we consider the following non-negative sequence with Uo = and
o 2wneunenos E EF
U. exp
We claim U2 is a supermartingale by observing that
E U.
[T-1] = U, (exp (2wrtemerll 2wmmn)uoo | [[-
(a)
S - exp (2wrrenerro ) = U2-1,
where (a) holds due Assumption 5B by noticing
10
27
Ut 1
20.0 1-py
E. 27.
U2a2
G2
Hence, we know E
[UT
Uo 1. Thus, there is
2
(1) R [Un]
8 S
Pr Ur
2
2
2
8
+ Pr
2w
11
Σ
2 2wrenoo
+log
2
(13)
2'
where we use Markov's 's inequality in (b).
Next, we consider another non-negative sequence with Rg and
R₂ exp Σ
wor 2 x²) up
2 1
x0113
E EF
EF vs Ys e [T].
We prove that Rg also a supermartingale by
Re [--1] = R [exp
1-1 -
| Fe-1]
R exp (wf 2
w - -
1 R4-11
18

---

Published as a conference paper at ICLR 2024
where (c) is by applying Lemma 2.1 (note that 2'=1 - x' E e o [t 1])) Hence,
have E [r] $ Ro 1, which immediately implies
2
(
6
Pr
RT
E
[TT]
T
T
2
8
+ Pr
Wi 11 10100-1/0 165 20 1--1 - x²) 1
wi
22 2
1--10-1110 0//122 - 2²11 + log
2 1
8
2
[=1
T
2
+ Pr
2111 x²) 1 01 1 15", ,2
2w
7t
2.2
D + log
2
2'
(14)
t=1
where (d) is by Markov's inequality and the last line is due to || x0112 S the 1-strong convexity of tb.
2D 2D (2 ,,"=
from
Combining
13 and (4). with probability at least there is
WTYTUT (F(x F(x'))
2
T
(o-1--mm)ooll (x ,,,) 2og
w +
T
T
+
20 1/ (z 100()"11x'))+
+ Σ
[e - w1-1)re(me - 41) Do(o ,x')
1=1
T
[w] (1 - 1 + 2w/7i 0000 (= x² + 2log
Σ
2wm +
1=1
T
(w: w1-1)(nt /1)) + 2w D0 ,²²).
Observing that for 2 2
(w,, W/ w)-1)(m1" us) + 20/-000000
=2w? 102
(n - k1)
(-1 1 22.000002
+ -T 2
Ei=e
27. 1-1ps
+ 27002
1-177,
270000022
-2w -2w2 11 x
x (m - 15)
1- HSM
-2w,(weRi-1 w < 0,
where the last line holds due to w. S w and 1 S S ū. So we know
wryrer (
T
[wi - 11mm00 + 2wini13007 (0(x" )² + 2lo
+ Σ 2 +02)
8
2
w1 (1 -py + 2 vn (x" x + 2oo
+
w1
2 2 =03)
8
t=1
19

---

Published as a conference paper at ICLR 2024
where (c) is by wa w1, Vt [T]. Dividing both sides by Wr py,, get
F(x - F(x")
T
(1
1ff + 2wn )
vo
De(x"" ; x²1)
2
log
2
+ _
(M² + 02))
WT
Prut
W WIrre
PrU
t=1
S
+ max. 251ST
1- )
H 2x2)
+2 M2 +2= 0² (1
1 2log 2
))
r
7ell/
Et=1 7
2x 768
1
Das (a(" .at) +
2 M22 0² 122=0221100 (1
2)) 8)
Σ
T
7
<
max 2SAST 1 - pyme
Ei= 7t
I
t=l
ss
78
where (f) holds due to the following calculations
27.000002 + Ex ==1
2nan. 1-My7l
W1
1
max 31+
WT
Σ.=1 20.02
2S1ST
11
279u002
27/111102
2w1
of
uoo²
Σx=1 27
Σ
v0
60
UT
PreF
2t=1
T
2 T
2
log = 2 log
2
2
2 log
7t
WITrUT
8
1=1
Ur
8 1=1
s=t
Is
2 T
Vt (M² + 0²) < 2(M 0
2(M² + 0²)
7/t
TrTT
PT
1=1
28=t
Hence, the proof is completed.
C GENERAL CONVEX FUNCTIONS
In this section, we present the full version of theorems for general convex functions (i.e., Mz = Phh 0) with their proofs.
Theorem C.1. Under Assumptions 1-4 and 5A with ji = 1hh = 0:
IfT unknown, by laking ()t
" V
VL
E [T],
there is
2L
E [F - F(x*)] 0
LD x²)
Delx", x.)
nMM + +02) (08
VT
In parficular, by choosing 17 0
Do(z* at)) M=
there
x²)
(M (M+ (o+)
Dola" oxd) log T
E (F(TT+))-F(e")) 50
T
VT
T is known, by taking T). = I A J/ Vt [T],
there is
Dula", x²))
E [F(2Tt))- - =( 0
+ nA12 + +00)
T
In particular, by choosing = (V
x1))
(M12+04))ogg log
there is
(x' xx)
(M + o) (o))/Don Dola" x log
E
50
+
T
/T
20

---

Published as a conference paper at ICLR 2024
Proof. From Lemma 4.2 if ne S 21Vayy Vt [T], there is
(1- MyT D. xx)
E [F((T*+1) F(x*)]
+ +2(M++ + +
Σ
7t
(15)
E1= m
s Y
where 7/ = 1/ = 1 Vt E (T]. Note that js = pb = 0 now, so both 1/. = 1
Vt
1-
2L
Vi
[7' and 1/: - ZI
= A J VI E [7] satisfy ne S 2LVR ZL. VI [T]. Besides, "/t will degenerate to
")- Therefore, [15 can be simplified into
B [ - F(x*)] s Do(x", x0)) + 2(M + +a))
T
(16)
Ei=1Th
[m]
Esmt
7
Before proving convergence rates for these two different step sizes, we first recall some standard results.
Vt
VT
Σ t=1
Vt
t
VT;
(17)
Vi
vl
t=1
T
T+1
Σ
ds 2 V E [T]:
(18)
V8
V8
T
Σ
11+
$
-ll = + log T.
(19)
If n)
2E A 9 Vt E [T), we consider the following three cases:
1
Vi
1] < 21:
1. In this case, we have = 3, Vt E (T) and
+0²) B B[ - < De(x", + 2n 2
T
1
E 1/v2
Lest l/v8
t=l
De(x", xx))
1
+ +n((²² +02)
n''
1(VT+1-V)
(a) xo(x",x'))
4n(M22 +02) + log
I nVT
VT
1 Dx(x",=*)
+ 4n + -o)) +lg (g
(20)
17
where (a) is by
T
VT+ Vi
< 2/T+1
Σ
HVT++IVV)
t(T +1 1
t=l (T+1-1)
t=1
2
4 1
VT +
t
VT t=1
t
4(1 + log T)
VT
21

---

Published as a conference paper at ICLR 2024
T 1) 2 21
In this case, we have 1/1 = 2t VI [T] and
E [(( - [[[==)))=((+)]]]]
(0(x"xx))
M
1
T12L
L
T T++
t=1
M 0² T
Σ
1
L
1=1
19 2I (,=x,")')))))
(M² + o²) + log T) L 2m(M² + +2) + log T)
T
2LD 10
(2" x²))
(2))
T
VT
where (6) is by 1. S
2n VT
vT ): In this case, we define T [4n] where [.] is the floor function. Note
1/ E that
21
4n² L2 E (1, [ -1.
By observing
" 2 21. + T]. we can calculate
1
[F(x++1) F(x')] v Du xx1)
T
E
+ 2(M + 0z)
Σ 1/t
2ymt f7
(6) Dul=" x
1
+2(M/ +
m7
T
1h
Sest Ns
Da=
778
111
where (c) is by T <
(Ii= 1/1
(2i=1 me)
Now we bound terms I, II and III as follows
T
Vt
T Σ
Vi
VT+ S Vidt
I
2LV
2L +
22T +
1=1
1=1
VT + 3
(T)
57
2LT
< 2LT +
n
37
1/(4L2)
II
sam + Σ
28=741 M1
t=l
(T 1 + 1)/2L + Exer+1 7/ V3
2L
T
| 1 + 2/L/Vo
2L
T + 1 4n
11+
(d)
22 Σ
II (1 J tdt
1+lgg 7 2L
m1l+ 2')
<
1-
VT
(e)
Et=
"
21
1n AnL(vT+I-vin v++I STL
2VT+I-VT+1
II S 7/1 + log
2(VT+I- - VT+I)/
27/(1 + log T')
( 2n + log
V ++
11+
VT
22

---

Published as a conference paper at ICLR 2024
where (d) is due to S T and VT I 2nL, (e) holds by 7 S 2n2 and (f) is by, for
T E [T - 1 and T 2 2,
VF+ 2( T
VT
+
2 T
VT.
III 1
Σ
1
18
Σ
- 1/v8
21( V Vt)
1=T+1
+ + Vi
T
VT+1
1
I
21(T + t)
1(T +1 t)
1=
T
1 Σ
VT+1
7 (1+111
$ VT+I
211
7
1=
19
21y(1 + log T)
TT
Thus, we have
E [F(x
F(x*)]
D Du(x",x') xz)) T2
5
2n + logT)
2m(1 + log T)
2LT +
+ 2(M +02)
+
37
VT
VT
20.Doo x01)
5D (x*,,",
+ +87(M²+ +1 + log 27)
(22)
T
31)
Combining 20
21
and
we know
Das
E
F [(xI+t)-F(C
F
+ 4n + oz) log log
VT
1
22D (x ,x')
20 + tz)) + log
T
vT
2LD xx
5 5Dp("",," xx1
+ 80y(M2 o²) + +lg log ]
T
VT
37
2LD (x+ ,x1)
5D v0 (x" xx)
+ Sm( + +0²) + +log
T
VT
37
DDul ,x)))
D (a*, (x*
+ n(M² + NMM +07))1877)
(23)
By plugging in 17 0
(Vaate
Du we)) M=+o*
we get the desired bound.
If TJ VT
Vt E [T') we will obtain
E F ++1) - F(x')] < Dolx" xx1)
2LV
VT
+ 2
2L A
1
(M² +02)
T Σ
T
VT
T-t+1
1=1
D Do(x", x1
2LV VT
+ 2
1
A
(M² +0²)
Σ
T
1
T
"
2T
VT
7
t=1
D Delx"
VT
1
2L
2
A
(M² + +3)((1 + log 7)
T
2L
VT
2LD (2" x
1
+ 2 + +0²) + +lgg
T
VT
1)
=0
(D* x.
1
De (x*)x")))))))))))))")))
n2M² +00)1087 (24)
T
VT
"
23

---

Published as a conference paper at ICLR 2024
By plugging in = O (V
De( (MP402))oRR))
we get the desired bound.
Theorem C.2. Under Assumptions 1-4 and with jf - pi. = 0 and let å E (0, 1):
T unknown, by taking ?/
Vt [T], then with probability least 6, there
2T.
V
- F(x*) LDplo" xx*)
Do (a (a(" + (M++0 + log
1 () log T )
T
VT
In particular, by choosing 1) = (V Dy(a=
there is
M3++² log
( LD ,x!)
(M v log 2)v (st
(xt, ax)) log T
VT
If is known, by taking 1) = 1
21
A
/T
Vt [2], then with probability at least 1 - 8, there is
F(x)) LDw(x", x²)
(x" + (M + 0² log ) logT)
1
T
In particular, by choosing 77 = (v Do(o'
lox) there is
(M + a vovlog t) Des (at, at) log
F(x - F(x*) so LDu(er,zt) xt)
T
VT
Proof. From Lemma 4.3 if I 2Lvay
E [T]. with probability at least
there is
F(1 F(x*) <2
1 max 251TT 1 115711
D (z(x".a0 xx)
(A 102+02
1 2 log
2 Yell
(25)
E
s=t
where = 7/ II 2= I-ps
1- Vt E [T'. Note that juy = pbh = 0 now, so both 1)
1 A V
Vt
22
(T) and n/ = ar A 3. AI E [7] satisfy S 2LVRT
ZL VI E [T]. Besides, 7/t will degenerate to
Th Then we can simplify
(25 into
4D 42= x!)
(1+ + M M2 +02 (2 2 2) Σ
F(aT+)) F(x") s
(26)
-e=t
n
If T) = 2L A n 11 E [T], similar to (23) Vt
we will have
(DD ,² x²))
De x²)
M² + o² log 1 3 logT)
-( F(z))))(())) 0
02log
T
By plugging 1 =
Dole",'! .ot)
we get the desired bound.
M240" log
If = HL A Vt E [T], similar to
24
we will get
LDy(x"
(z x²)
+ 122 + o² log 1 o
LOST))
F(x)) 0
VT
By plugging in 1/ =
Dala' .
we get the desired bound.
(M4400 log 4) log
24

---

Published as a conference paper at ICLR 2024
D STRONGLY CONVEX FUNCTIONS
In this section, we present the full version of theorems for strongly convex functions with their proofs.
D.1 THE CASE OF ja > 0
Theorem D.I. Under Assumptions 1-4 and 5A with j >> 0 and pa = 0, let Kig = L Rg
2 0:
I is unknown, by laking either t/. p)((42x5)) 14 E (T) or ms(2+1+1ng)
11 E (T), there is
0
,a')) (A5240")
1A [T]
E F((T++1) - -F(=")))F((')1
S
(x((+ L(Lta))y(e' ,a'2 + (MF log (T
0
2 vA E (T)
T(T+*)))
9) Ry(4I+dyy
t=
p
T is known, by taking itt
2 S 1 S T Vt E [T] where v) 2 0 can be any
2
1
Py(t +4444)))))
mumber satisfying 7 + t.y > and = -[27, there is
LDn
(M2 + 02) log
E [F((T++1) - F(x*)] 5o
MT(T + 18))
exp
2rft-diy
Proof. When My > 0 and μr = 0, suppose the condition of m S 2LVHY
Vt E [T' in Lemma 4.2
holds, we have
(1- MyM1) Domii""(a"".... +2(M2 + 0²)
E -
(27)
Σ1=1 nh.
ssnt 7
Now observing that for any & E [T]
7t = 1h77-1
T.-T+11
t t
mll =
Mf
1
1fT)
711
t t=1
==2
2=2
where r, = I1 T-Mmh
11 E [T). Hence,
27 can be rewritten as
E F(xT+1) - F(x")]
p (x )x1) m + Pr-1
+ +2(M+++0
(Tr/TT1 - mmm)))
(28)
Pr-1
111
Now let us check the condition of n
1
Vt [T] for our three choices respectively:
21v1y
1
1
<
Vt E [T]:
(t + +2kg)
Mj 2L
2LV
(t + 1 4kl) H4 - 2L $
Vt E [T]
2L V mJ
1y(1+2xg] p3+21 S TLVEY
t=1
2 < My (2ky v(r+x;)) S 2LVHY 2 ps(t-7+2+4rr) #542L S 2LV
2515T.
12T+1
Therefore, 28 holds for all cases.
25

---

Published as a conference paper at ICLR 2024
First, consider 7) (y(H+2k)) V [T]. We can calculate 7/2
m,(1+2er) and
8 2kg
t 2ky
4A (T).
1 + 2kg
1 2x,
#=2
2=2
Hence, using 28 we have
E F[xxT++) - [xx")]
(1 1 (x",""xx'"
1426,
+ +2(M² + +02)
" (1+2a11
T
Mf 1 (1
Nr(1+2xy) + Ir-
Ir-I my(1+2er} 14
(Tr/Ti-1 1)(1 145 2y(422x))
15
t=2
2(M²+
+
(1+ 14+24 [I' 2
H1
(1 2x ( 2x (rr 2x²)
T
(Tr/Te-1 1)(t 1 + 21 + 2k5
2=
2LDo(1",x",
2(M +
Σ
1
T
(1 + 2ky) yT
(T- 1) 2xx
t=2
2T. xxt)
2(M 02)
T
14
(T t+ ++(((t + +2kr)
2LDx(x* ,
2(M + 02)
T
T
14
T + T+1+ 126 -
+ 2ng
2LDo(x" x!)
2(M + 02)
1 + log T + I+2Kg
log T+2k3 I+26,
2
T 1 + 2kg
2LD (1')
4(M² +
T
M$ (T + 2m5))
(DDulut,e") x² T
(M2 + 02) log T
=0
+
(29)
14 (T + k,))
Next, for the case of ")((+i+4ky)) Vt E [T], there are 7/ my(1+22,) and
S 1
4kz
(t + 4kg) + 4x,)
r
Vt E [T].
1f17s
4kg
(1 + 4x²) + 4xz))
4
2
26

---

Published as a conference paper at ICLR 2024
Thus, we have
E [11 - Fx))]
1t2k, (2)()"))))
11
T
Pf 1
+2(M² +00
15(14225) + -r-1
1y(1+22r]] + Dr-1
(Tr/Pr-1 1)(1 - 14 ky
115
t=2
2I,D +
2
+ +02)
(1+ (1+211 [ 2kg
H1
(1+ 2xy ( 2ky)rrr - 2x1g)
T
(TT/Ti-1 1011-1-1((111) 4wc 1
4(1 + 4.,
T(T + +1+ 8ky)
2(M + 0²)
2(1 + 4xz) (1 + 2k,, T( + + 8k1g)
4 + 4x²)
Σ
148
1 +1 + 8A/ (1 + + 4x5g)
2=2
4(1 + (x(")
22M² + +z)
T
4(t + 4kg)
Σ
T(T + +1+ +8Ky)
H1
(T (1+1-t))
10l1-t)1 t) + ++ 8tty) + 1 4k5y)
4(1 + 4k )
2(M + 0²))
T
4
1
2T + 1 + 8kg T+1-t + ++++
T(T + 1 +18g)) 8kg))
H4
[=1
4(1 + 4xy) ,x!)
2(M + +z2
4(1 + log T + log
2T+8K1)
T+8K,
T(T + 1 8ky)
H1
2T + 1 SKi
4(1 + ) (x*
8(M² + 0 o2) + log 21')
T(T + 1 + 8ky))
12T + 1 8kg)
+ +Kz Das (x",x²)) T(T + kg))
(M2 + 02) log (Ty + 16))
(30)
Finally, if T is known, recall that choose for any E [T]
t=1
1y(1+22y3
Th
my(n+2er)
2 2
2
+2
(y ++2+4kr)
Note that we have 771 my[1+2m7] and for any t [T]
2
1-1
Ts
T 1y
n+2k
y+26
(t-T ((t
12
g+2xx-1
(1-4k;) 1kc)[(2+4kc)
So we know
E [F(x)t1] - F(x*)]
(1 (1- (1-m
+ +2(M² +02)
m
2
mn + 1--1
IT-1
(Tr/TT- rr-/T-1-0 - 1)(1 - 14
13
Pf
2(M + +02)
+
-11 (1122k) [T' 2kg
Hj
(1 2k/ ((1 + 2x,)Irr 2n²)
+ +
m
m
TT/TT- 1)(1 - 11)
(Tr T 1) - 1151
(31)
27

---

Published as a conference paper at ICLR 2024
Note that we can bound
1
(1+ + 2xy ,T' 2kg
(T-++++14 1-- -2kg
0+2ky-I
2(14(19)
(4)
7+2K5
2
+ (+2xg)= 1 -2ks
2xg
1+2xg-1
2-2n
7-1
1
+
2
n
(6)
1
r (-1+
--1
1
1 -
S exp
cxxp
17 + 2kg
[) + 2ny
1 2xg
17 + 2xg
(c)
T
+1)
S exp
(32)
+ 2(11++2k5))
where (a) holds due to T - 7 2 0. (b) is by Ky 2 0 and
2 1, (c) is from r 2 T
7+2xy-1
2
7 + Ks > and Ky 2 0. We can also bound
(1 21+2)))((11 + In -2xg)
1
(1 + 2kbg)
ytany
+ (T -2k5 2(1+)rr)
(1 + +115))
- -2k5
2(1+4Ng)
2(1 + 4x,))
(1+2k (1+2%)) T + 1)(T - 2 + 881)
(
2(1 + +kr))
(1 + 2TT))(T - T-1 + 1)( T+1 + +2+ 8kg)
2
8(1 +1++6 4
(c) 8
S T+3+1664
(33)
(1 + 2k, (T + (T + 3 + 16x,)
where (d) by r < I+1 2
and (e) is by T 2 1. Besides, there is
1
12(n++ + " 2x²))n + 2n,g
n+2k, m+
T-1+1
(T (I-1+1+1N 1 (T-+))+
2
(1448 1) (2+4k))
5
1
1
1²(n + (9(n+2xg)nn + 2kg- - 1) n
9
( (144m)((+4mn)
1=2
(1+ (2 + 4ky)
(1+44)) + 4kg)
T-1 1
nn7(n + 2x,)2 )2 9 (1+ + 4n )(2 + 4niy)
-T] -T - + 8kg)
1²((1 + 21,
(T-7) - + + +3+ +
1=2
T-1 T-1-1 -1
2
2
(1 + )2
(T- 3
(T T+1 +3 8K1)
2
(1 + 4rs))(2 + 4kz)
2
(h)
32
S
(34)
1² + +2n))
T + 5 16kz
(T + + 16k,)'
28

---

Published as a conference paper at ICLR 2024
where bs) - 2 0 (w.lo.g., assume 2 otherwise, there is I= 0 I 2 and 7 -1 2 1, (g) is due to I - and (h) is by r + Ky 1. We also have
8
1
I1
(( ( -
4x₂)
1
(T (7-44148 (T-
(t ( (t+))++4n)))
(1+11g)) ((+1-1))))))
WE
1+ + 4xig
(x 4kg) - (t +xr ( 4m0y)
$
1 (t 4x₂)
E
1
(T-T+1 (T - T + + tt)
4
2T 2T + + SKy T- +
1
T T T T-++2+ Sti +
4(1 + log(T - T) + log T-7+248k3
2T-274248N
4(1 Aog+log'1 T")
(35)
12 1 27 + +33+8k 8ky)
(T +2+ 8Ny))
T+1 where we use 2/2 S
in the last inequality.
2
Plugging 32
(34) and 35 into 3 we have
F(x")]
T
2(M² +
8
S2LDx(1" exp exp
+1
+
2(1 + 2ny)
+ 16ks
32
4(1 + log T)
+ 22 + +02)
11 (T + +5+ 16m
13 + 8r())
LDu(
(M2 + +
(36)
T' exp 217444
(T +
Theorem D.2. Under Assumptions 1-4 and 5B with > 0 and μh = 0, let Ky = 8 E (0,
L
> and
If T is unknown, by laking either 1/t with probability at least 1 5, there is
p)(4+22g)> Vl E [T) or Th. = pf((+1+1ng)) (g(1=M;)D (ell-mi)Do(e'at
1I E [T]. then
to02+o log tox log
1): #)(1+2053 Vt E [T]
-(IT+1)FF F(x') S
My +xF))))))))))))))))))))
0
11 (D T(T+Ns)
+o" log {) log My(T+ing
T) MT(+1444g))
Vt [T]
t=1
py(1+2kg)
T is known, by laking t/
2 2 251ST, E [T] where vj 0 can be any
p
12++1
Py +1244k))
number satisfying n + Kz > and
T = ["7, then with probability at least 8, there is
F(2++))=F(z')50 50 (11 1 2 ))
(1 + x2,) Dey x() ,x=,, (M² + 0² log 2)) log T
Ms (T + +kg)
exp
Inttng
29

---

Published as a conference paper at ICLR 2024
Proof. When My 0 and juu 0, suppose the condition of m S 2LVUy" At [T] in Lemma 4.3
holds, we will have with probability at least 6
-
max pasTle
25:5T
x
Dolx" ,0
+ (PP +02 (1+2
2) 2))
Σ
T
7
(37)
Σi=1 7t
==
x 7s.
Now observing that for any t E [T]
7t = ph
Pr-Te-1
1 122
MhT
Pf
==2
2=2
1 1y
171
I t=
where r, = II I-Msn-
14 E [T]. Hence, 37
can be rewritten as
F(xT+1)- F(x*) 52 1
max 251ST 1 14STH
1,(x",,1)
(N1² (MP20²²
| 2 2og (22
Vell
x
(38)
1/1 + Pr-1
Pr
s=t
Now let us check the condition of n1 S
1
Vt E [T] for our three choices respectively:
21,11
1
1
1
T/e
S
[T];
1l + (255)
11
2T.
2L
21
2
<
V [T] 2L
(t 4xz)
1&g 2T.
Ms 1s(1)2k5) 2T S 2TN43
t=1
25t5T.
py(++207] Hy (2ky [(r++,]) 2LVR
#y(l-742+day) 71 S 2LVPy
t2
Therefore, 38 holds for all cases.
First, we consider Te= ()(+22))) Vt E [T]. We can find 1 maxggiTT T- (1+2g and
1+
S 3,
1-p192
P
II s=2
s 2kg
t 2ky
vt [T].
MT
1 2xg
1 2x,
2=2
Hence, using
338. we have
6
Du(o",
Pr-1
+
2) (1+21op 0o 22²
M2
8
Σ
m
x
Following similar steps in the proof of
29
we can get
[1 + Kig
Dol
D
(M2 + o² log log 7
F(TT+1) F(x")
F 5
(T + k5))
Next, for the case of Tt
Vt E [T]. there are 1 + max2cIST T-
1-
4, 7h
m)(1+2k)) and
s 1
4kg
(t+ 4ky) 1+ 4x2)
r.
At E [T].
1f7ss
4kg
2(1 + 4m, 2xT)
2
2
30

---

Published as a conference paper at ICLR 2024
Thus, have
Do(r", x4)
2) Pr-1 + 15+02 (1=210g 2 8
1
F(x*+1) - F(x²) 58
Σ
7elf
!
Σ
Ei=t
Hi
Following similar steps the proof of (30.. we can get
[1 + kz) x Do
(M² + 0² log (/) log T
F(xT+1) - F(x") S
T(T + Ky)
My(T + rig)
Finally, if T is known, we recall the current choice is for any t E (T]
t t=1
1y(1+2xg)
2 25
?/
127+1
ky(1-T+2+hmw))
where 7) > 1 and ==
[
Note that we have
1
1
1 max 25tST
=1+
=
1 1-p((12 mT+1)
nA 1.5 1.5+ +2n
1
= 2 +
11 2xgg -1
0.5 0.5 2
S 4
11 + 2xgg -
711 (1+2g))))) and for any t E [T]
1
1ST
r, 2=2
7+2k
11
n+2n/
12
0+2ky-1
12+
Thus, we have
((x
8 1 2xi
2
Dela" x1
2 2 M 022 (1+ 2l+2logg
Σ
Tol
+
Pr-1
Σ 78
Following similar steps in the proof of 36
we can get
F(IT+1)= - F(x")
<0
IV + 2xs
1
My + Kx,) (M2 + o² 2² log 2)) log
T
MT + ki))
exp
D.2 THE CASE OF μl >0
Theorem D.3. Under Assumptions 1-4 and 5A with p. 0 and ph > 0, let Kh.
2 0: 14
L
T unknown, by taking (M,(t4441.)) Vt E [T], there is
Pn + k2,)² 2 (x0 x0) T(T + KR)
(M² + 02) log un (T' + +kn)
E [((TT+ F(z') 0
1ST
T is known, by taking t/.
2M
11 [T] where vj 2 0 can be any number
12r+1
satisfying 17 + K4h > 0 and 5
[T]] there
[F(xT+1)-F(C so
14
(x x
+ 1V 7 2kh )
1
(M2 02) loglog T (T + KON)
exp
2(11+22A1
31

---

Published as a conference paper at ICLR 2024
Proof. When μ 0 and pl > 0, suppose the condition of mp S
1
Vt
[T] in Lemma
2LV,
21.
holds, we will have
E [F((xT+)) - F(x*)] S (1 - (1mm) -mm)) +2(MM²
+
El=1 76
e== 788
Dela" (0')
T
+ +2(M²++ +22)
(39)
Ei=17 7t.
Σx= 7
t=1
Observing that
7t = T) ph0 7/ II -
T T P--
Vt E [T],
14
2=2
where I'2 = II + mhTo)) Vt E {0) U [7]. So 39 can be rewritten
[F F(x)]] f pr , x²)
+ 24 (M + 0²²)
(40)
Tr-1 1
T T 1 -
We can check that
2
1
17 pn + 4mh)
Vt [T]
2k
2L
21 TSt
2RaHA
7/
12
2matt
2T
Therefore, 440) is true for all cases.
If mh
( 1L E [T], we have
2
2
(t (++1+ 4mh) +2+ +444m)
r
II + mmn)))
12 E (0) U..
(1 + 4mh + 4Kh)
Hence, by 40
E [ 11 [xx))]
U1 15("0 x1), x²)
8(M2 + 0²)
T
(+t4ka)) 1.
[T41+4mM))) 2T
(1+1+4 4 (k+ )1 (1+1+
14h
(2+
1=1
(1 + (2 + Des 2x
8(M2 + 02)
t + ++ 4Ah
1
T(T +37+3+7 8k5)
1/
1 4kh
1-+1-1((7 + +2 + 8hhh + t)
(1 + 4m,, (2 + 4kn) (xt, (,',
16(M + g2)
1
1
T+--1 + T + 2+ 8kB +
T(T + 1-3+8mm 8kK)
1hh
2T + + Ski
[=1
(1 + (R))(( + 4x,)), Do (xt xx
16(M² g2)
1 1 log T' + log 2T+2+8K1
T42+8KA
T(T + 3+ 8K6N)
14
2T 3 + 8k%
(1 + 4k²) + 4K4)))) Do (at,x*) x.
16(M² + (1
+ log 2T)
T(T + + 8K5))
(2T + + 8K%).
un (1 + D )
(M² + 0²) log T
(41)
T(T + km)
(T + kx)
TsT
If 1)
Ph ( 2
Vt E [T], we know for any t E {0) U [
82
(+T)))))))))
LST T
r (1 + Mml
7t2mA
(1- (tt
12++1
37+2mh
(1+ 1sa (2+1Ns)
32

---

Published as a conference paper at ICLR 2024
So obtain
E
M/ Dx x²))
+ (M P +
TT
T T 11
MnDa(
+ 2um(M + Σ
(T-T+144Al (TTT2
1-
+ 2
(144 (2+-AA))
Nh Do(x", x
T
+ 2um (M +2))
1/2
TT/ ST/Te-1
(8)
ph
Del (x" (x*)z)))
T
+ 2M1 + +
exp
2(1+1)20N)
T
-1
TT/ T T
14 Do (2'" 22
T
+ (MP +0²²
(42)
exp
2(1+
T
-1
where (a) by T 2 0 and r 2 2.2 (b)
is due to
1
T/2
T
1 2
))
T
1
exp
log
1
2ex
exp
17 2nh
2
17 + 2mth
2(1 17 + 2k²)
Now we bound
==
1 (1 + 2x
11 7+2kg
+1+ VT (T (1+4k (2+
17, -2xx) (1+ (1++)((+1)))) 2k
- 1T-
1
(1 + 4x%)) + 4k%))
p3, + 2xx 111++++10 2
TT T +8N, + 3)
(1+ + 4mhh (22 41%)
17 + 2m
+ 2k5))
(T-T)(T + 8KY 3)
( 2(1 + 4mm))
2(T + 1)
(1) + 2kA)
- - 1)(T + + 16K%)
2 2 + 7+2NM
12 2 + 2
6
(43)
T +5+ 16%A.
(T 5 16kh)
33

---

Published as a conference paper at ICLR 2024
where (c) is by - t and Next, there
44 1. We use 2 0, 2+1 in (d) and T 2 in (c).
T h
11
(t - T 4kn)2
((-r
P
(t 2xn)
(T-7+1+48) (T -11
(1+dra)(( 111 dr(.)
1 4kh
(1+ (T 4 T + 4kaA) - (1 + 4kH) + + 4k²))
+1 + 4444mk) (1 4k +1+ 4km)
1
-T 1)(T 2+ 8KH +1)
2T 2T + + 8Kg
T-T+1 +
T 2 + 8AH +
8
- 27 2 + 8K4 T - T + 2 8Kh
logT (T) log
(2T 2T + + 8KL)
8(1 log T)
(44)
1 (T + 2 8K6N)
where we use
2 < = T+1 in the last inequality.
Plugging
and into to get
E [xxx+11 F(*")]
12 2 (2
M4 DepDo (o (x',z') x()
2(M + +22)
942N,,
8(1 + log T)
+
+
exp
T 2(1++7+2ka)
14h
T + 16AA
T + + 8ki
14h De, 21)
T + (IV
(M² + +22) +0))log7
=0
(45)
1) 2kA
(T + knn)
exp
2(1+7)+2km)
Theorem D.4. Under Assumptions 1-4 and 5B with μy = 0 and > 0, let Kh =
L 14
0 and
8 E (0,
If unknown, by taking V) = (M((+44N))) Vt E [T], then with probability at least 1 5, there is
F(1TT)) - -(x") [1(1 + kT) (r))DD(l"" (x), T(T + kh)
(M² + 002 log 3) "llllo"" T PT + kh)
tST
IfT is known, by taking
Ph (11-2NN))
VL E (T) where vj 2 0 can be any number
2
t2++1
Pu(t 4ma)
satisfying + KA > 0 and +
[
then with probability at least 1 - ö, there is
Nh (x (x",,,""" ,x
- + (IV 2km pn + kN)
1
(M1 + o² log f) log
-(2)t))=((2) 50
exp
2(1+
34

---

Published as a conference paper at ICLR 2024
Proof. When μ 0 and Am O, suppose the condition of m S 2LVR,
21 Vt [T] in Lemma
holds, we will have with probability least 1
F(x + F(x")
22 1 + max
251ST 1- - 1-1sm)) -15mm))
Do(x"x))) + M2 +2² (1
log (
Σ
M
Ei=17 "t
Σ
1=1
s= 7s
4D (x" x²))
M2 [M2+0l +0² (1 11 (1+2l08 ,
2 2))
Σ
T
2el
(46)
1t=1
1=
s=t
Observing that
Tt = + phils-1
II (1 + phm = - 2=2
T, T--Pe1
Vt E [T],
18
14
2=2
where r2 = II (1 + umma), Vt E {0] U [T]. So (46 can be rewritten as
F((=")
4pm (x" +4pm (M² (1 [1+2log 2 2))
Σ
2
(47)
TT-1
We can check that
2 (n (t + 4m²)
1
Vt [T]
2km.44h
2L
2T. S
1
ma 2k
I
2ASHA
2L
Therefore, is true for all cases.
If 1 4m 1L E [T], following the similar steps in the proof of (41 we can finally get
[1 + Dx , x21) (M2 + o² log !) log 7
- F(x") 20
T(T + kK)
PM(T + kn)
1ST
If 1)t
palm 2
Vt E [T], following the similar steps in the proof of 45), we +
Mh(1 IN+
can finally get
Mh D Dx x²2) + (1V 1 1) (M² + 0² log 1 log
=(xx'=(0 F(x - -F(x") 00
T
2%
Pn(T (T + kK)
exp
2(1+7tt
35


Reviews:
[{"review_id": "3EtjuBDQg7", "reviewer": "Reviewer_V1N7", "summary": "The paper focuses on a fundamental problem on the convergence of SGD. Specifically, the main novelty is high probability, last iterate rates for SGD without bounded domain assumptions for solving convex problems. While doing so, the paper also presents unified results for composite problems / Bregman distances / convex or strongly convex problems / smooth or Lipschitz problems and expectation or high probability guarantees.", "questions": "+ Are the results of Zamani, Glineur 2023 and Liu et al., 2023 work well together to get the high probability rate on the last iterate without bounded domains, or do additional difficulties arise while combining these results? If so, what are these difficulties? To clarify, I think the paper is worthy of acceptance even if the combination of these tools do not create additional difficulties. Identifying 2 interesting techniques and deriving an interesting result (as stated before I think the result of the paper is interesting) is enough for acceptance in my opinion. But this should be clearly written.\n\n+ Before Sec. 4 the authors say \"to the best knowledge, our results are entirely new and the first to prove ....\", there is no need for such repetition or such exaggerated words as \"entirely new\", the sentence meaning is the same if you just say, \"to our knowledge our results are the first to prove ....\". Also the beginning of the sentence should be \"to our best knowledge\". Similarly, before Lemma 4.1 the authors use \"brand new analysis\" which is unnecessary and also unclear if it refers to the analysis of Zamani and Glineur, 2023 or this paper.\n\n+ In my understanding, the analysis of Zamani, Glineur 2023 seems like an alternative to Orabona, 2020 who built on Shamir, Zhang, 2013. Why is the analysis in Orabona, 2020 not sufficient to extend to high probability guarantees? Or do the authors think similar results can be shown with Orabona, 2020's analysis too? Explaining this will help the reader understand what is going on. Put another way, what is the reason that the paper builds on Zamani, Glineur 2023 instead of Orabona, 2020 for the last iterate of SGD - expectation guarantees without bounded domains?\n\n+ Throughout, the authors use notation such as (this one is for example from Lemma 4.1 but it is like this all around the paper and the proofs) $\\eta_{t\\in [T]} \\leq \\frac{1}{2L \\vee \\mu_f}$ which is convoluted, difficult to read and non-standard, whereas they can simply write in a standard way as $\\eta_t \\leq \\frac{1}{2L \\vee \\mu_f}$ for $t \\in [T]$. Things become much more cluttered when the authors start writing things like (again Lemma 4.1) $v_{t\\in \\{ 0 \\}\\cup [T]} > 0$, this is unnecessarily complicated and not very readable, please consider rewriting like $v_t > 0$ for $t \\in \\{ 0, 1, \\dots, T\\}$, which is much easier to read.\n\n+ In Lemma 4.1 and other places, author also use definitions such as $v_t = \\frac{w_T \\gamma_T}{\\sum_{s=1\\vee t}^T w_s\\gamma_s}$, why not just define $v_0$ separately and just write the sum starting from $s=t$ like normal? This is much more readable than seeing $t\\vee 1$ every time for such things.\n\n+ Please describe clearly in which ways Lemma 4.2 improves over the result of Orabona, 2020 since Bregman case or smooth case is just left to readers as exercises in Orabona, 2020.\n\n+ Many places, such as the footnote in page 6 says that \"Harvey et al. (2019a) claims their proof can extend do sub-Gaussian noises ....\" Or in the beginning of page 2: \"whether these two assumptions (referring to bounded noise) remains unclear\" This is rather strange as it gives the impression that the authors think the claim of Harvey et al. (2019a) is not correct. If so, please tell the readers why you believe their proof does not extend to sub-Gaussian noises. Also, it is so easy to write to the authors of Harvey et al. (2019a) an email to ask them the extension for sub-Gaussian case, if you are not convinced. It is not very nice to write it like this in a paper without checking with the authors of the existing paper to clarify their claims. Looking at Harvey et al. (2019a) I also think that their result is extendable to sub-Gaussian as they also described clearly what would change and how the changes would be handled. Again, the current submission does not need to focus on such minor issues, even if Harvey et al. (2019a)'s claim is true (which is in my opinion), the submission's contribution still stands since they get rid of the bounded domain assumption.\n\n+ What are the main technical novelties in addition to Liu et al., 2023? Please describe this in Sec. 1.2. The two works are quite related and this section does not clearly state this.\n\n+ Page 3 mentions \"smoothness with respect to optimum\", what do the authors refer to by this phrase?\n\n+ page 4, you can just use $\\mathcal{X}=\\mathbb{R}^d$ and define the domains of $f,g$ in standard ways to get rid of all the discussion about int(dom) etc. These are standard problem setups, it is better not to complicate things unnecessarily.\n\n+ page 4 and many places of the paper refer to the book Lan, 2020 for some results. Please clearly specify what you refer to in this book so that the readers know where to look at, we cannot expect readers to browse a whole book to understand what the authors are using from this book.\n\n+ Sec 2.1 is unnecessary and should be moved to the appendix. Moreover, the sentence starting with \"We also would like to emphasize that ....\" Reads strange, please consider rewriting. \n\n+ Theorem 3.1 has a step size choice depending on $x^*$, this is not good and should be avoided. The authors say after the statement that things work with any $\\eta$ independent of $x^*$, if so, write things that way in the main text. Of course, a result needing distance $x^*$ to set step size is definitely not desirable.\n\n+ The discussion after Theorem 3.1 says also that \"Orabona 2020 cannot be applied to composite optimization\", why? What breaks in their argument? It is not clear to me why Orabona, 2020 would not extend to composite setting in a straightforward way. If the authors make such claims such \"cannot be applied\" for previous results, they should explain why. Again, whether or not Orabona, 2020 can be extended to composite is not essential for this submission. The main contribution of the submission is independent of this. By putting phrases like this, the authors only confuse their reader. They do not have to claim novelty for every single result contained in the paper (in some cases they can just recover existing ones, this is okay), the authors should clarify their main contribution, which is high probability guarantees for last iterate of SGD for convex problems.\n\n+ Page 5 also claims that the results are the first improvement over Moulines, Bach 2011 for smooth problems, whereas Orabona, 2020 just left it as an exercise to extend their results for smooth problems. If the authors think that Orabona, 2020's analysis does not work with smoothness, they should write why they think so. Otherwise, this is misleading for a reader and only distracts from their main contribution of the submission.\n\n+ Before Theorem 3.2, the authors mention recovering $L/T$ rate in the noiseless case. It seems that this is not true with any $\\eta$ but only the $\\eta$ depending on $x^*$, can the authors clarify?\n\n+ The case of strongly convex is strange since in this case the bounded gradient assumption (that is, Lipschitzness of the convex function) and strongly convex assumption contradict each other. This is well-known, see for example Section 1 of \"SGD and Hogwild! Convergence Without the Bounded Gradients Assumption\" by Lam M. Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtarik, Katya Scheinberg, Martin Takac. In this case, what is the significance of the strongly convex and bounded gradient case? Of course, the unified result also contains cases where we do not have bounded gradient and strong convexity together, but this should be explained well and be separate from the main contribution of the paper.\n\n+ Paper uses the phrase at many places (including the title) \"last-iterative convergence\", this is not a correct terminology, also probably not a correct grammar, it should be \"last-iterate convergence\". It is used many times and disrupts the flow, please change it throughout.\n\n+ Please explain the 5th line in the chain of equations in the beginning of the proof of Lemma 2.1.\n\n+ Proof of Lemma 4.1. Explain the requirements of $v_k$ in the beginning of the proof. Add the reason why $z_t \\in \\mathcal{X}$, that is: because it is a convex combination of points $x^*, x^1, ..., x^t$ that are in $\\mathcal{X}$.\n\n+ beginning of page 15, fourth line is difficult to follow, please write clearly.\n\n+ After eq. (7), when authors use convexity of $F$ with $z^t$, $z^t$ is not written in a proper way for the reader to understand it is a convex combination of points. Please write the correct representation to improve readability. That is, you need to recall that $v_s$ is monotone and weights sum up to $1$. Zamani, Glineur, 2023 writes this clearly for example.\n\n+ Last inequality chain in page 15, please explain the last step.\n\n+ Page 17, the estimation of $2w_t\\gamma_t \\eta_t v_t$, please explain the first inequality. Also refer here to the definition of $\\bar v$ to improve readability.\n\n+ Beginning of page 18 while using Lemma 2.1, clarify what refers to $\\lambda$, $Z$ in the lemma and why the requirement in Lemma 2.1 on $\\lambda$ is satisfied here.\n\n+ Beginning of page 19: $w_1$ is undefined since $w_t$ contains a sum starting from $2$. Of course it is implicitly clear what it is, please define $w_1$ properly.\n\n+ Page 19, bound of $w_1/w_T$, please explain the inequality.\n\n+ After Lemma 4.2, the authors again say \"first unified inequality for the in-expectation\" and after Lemma 4.3, they say the same for high probability, I understand that the authors want to emphasize the novelties but after a point it gets tedious for the reader and gives the feeling of \"oversell\". Hence, please try to be more concise, state the novelty once or twice in the paper and then tell the readers main contributions clearly.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "As implicitly stated in my \"Summary\", I do think that the goal of the paper is interesting. A result involving high probability guarantees for the last iterate of SGD for convex problems is interesting in my opinion. The proofs are comprehensive and mostly carefully written (even though there are readability issues I will expand on in the later parts of my review). Having a unified result is also nice to cover different important settings.", "weaknesses": "Even though I think the main result of high probability rates for last iterate of SGD without bounded domains is interesting and worthy of acceptance (once the correctness is verified) there are many issues with the writing of the paper and proofs that should also be addressed which prevented me to be able to verify the correctness. Right now, the repeating theme in the paper is for the authors to spend way too much time and effort to show their improvements in marginal cases, which confuses reader to miss their main contribution (and also at times misleading comparisons with related works). In addition, the generality and unifications that the authors are trying to achieve (unification is a good thing as I said before but it should be presented in a correct way), makes the proofs unnecessarily complicated and difficult to check. I have suggestions to improve this. \n\nThe main reason for my rating is because I could not verify the proof for the main result of the paper in a reasonable time-span with many questions about technical aspects (given that as reviewers we need to review 4-6 papers in less than 20 days in addition to our regular work load). As a result, I cannot be convinced yet about the correctness. Hence, with my suggestions below, I am giving the authors the opportunity to clarify their main contribution, present their main contribution in a readable way, answer my questions about the proofs and help me verify the correctness which is required for acceptance. Once and if this is done, I will be willing to raise my score.\n\nIn particular, the issue is that the authors are trying too hard in the paper to \"sell the result\" which causes them to write the proofs in such a generality that it makes it hard to verify the result without investing days. The results of the paper should speak for themselves since high probability guarantees for last iterate without bounded domains for such an important algorithm SGD is important. I already invested days to clarify the exact contribution of the paper because the authors are trying to claim novelty in all the presented results, for this they just generalize things so much so that they can claim the novelty. But in some cases, some of these generalizations are straightforward and just degrade readability. Even though the paper definitely cites and states that they use the techniques from Zamani and Glineur, 2023 and Liu et al., 2023, they spent too much effort trying to justify their analysis is still novel. \n\nFor example, before Lemma 4.1, the authors give an effort to describe a high level message of Zamani and Glineur, 2023, but they say \"This brand new analysis is where we different from all the previous works\". It is unclear what are the \"previous work\" or what is \"brand new\". If there is a difference on this part of the analysis from Zamani and Glineur, 2023, please specify what it is, if not, this sentence should be clarified. It is okay to use a tool from another paper, Zamani and Glineur, 2023 in this case, but one should describe clearly what is used directly from that paper and what is modified and what the precise modification is.\n\nBecause of the unclarity in the writing of the paper, I had to spend a considerable amount of time checking the results of Zamani and Glineur, 2023, Liu et al., 2023, Orabona 2020 and Shamir, Zhang 2013 to identify precisely what the contribution is. At the end, writing of the paper felt like an oversell to me and misleading at times even though I still find the main contribution interesting (high probability, last iterate without bounded domains). \n\nAfter checking these 3 papers, I saw that we know (1) expectation rates for last iterate of SGD without bounded domains since Orabona, 2020, (2) we know high probability rates for average iterate of SGD without bounded domains since Liu et al., 2023. The contribution of the paper is to unify these two. However, the paper tries to also claim credit for doing (1) i.e., expectation guarantees for composite problems or Bregman distances or smooth problems: this is not good. \n\nBecause looking at the blog post Orabona, 2020, it is clearly written that Bregman extension and using smoothness instead of Lipschitzness are left as \"exercises\" to the reader. Also, looking at Orabona, 2020 analysis which builds on Shamir, Zhang, 2013, I agree with the blog post that these extensions (composite, Bregman, Lipschitz gradient) should be straightforward. If the authors disagree, they should clearly write why Orabona, 2020's approach does not generalize. Otherwise, the contribution of the paper is still enough without trying to justify every little thing. The authors can still add a remark saying that these were not explicit in Orabona, 2020 and they have these generalizations, but they should not emphasize this and focus on the main contribution of the paper: high probability guarantees for last iterate of SGD for convex problems without bounded domains.\n\n*** As such, what I recommend the authors to do is the following: as the main result of the paper, identify the simplest result that still captures the novelty by forgoing generality. In my view, the authors can just focus on a constrained problem with Euclidean distances, Lipschitz continuous (or smooth) convex function and provide a self-contained proof for high probability convergence of last iterate without bounded domains in this simplified setting. This way, both a reviewer such as myself and the readers of the paper can quickly verify the main result of the paper and appreciate the main contribution. The authors can then provide statements for the general cases with strong convexity/smoothness/composite cases/Bregman distances etc. and show the \"unification\" and provide their generalized proofs in the appendix (they can state the generalized result in the main text if they have the space). But what is needed is to distill the main contribution and give a digestible statement and proof for the reader so I can verify, right now there are many things I could not verify (written below). Right now, I have to go through so many generalized results to verify the correctness of the result which is tedious and time-consuming with the extensive review load.", "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": "", "extra_scores": {}}, {"review_id": "TJoeGjvHEu", "reviewer": "Reviewer_4SRm", "summary": "The work presents the last-iterative convergence of stochastic gradient methods  in expectation and in high probability on general domains not necessarly bounded.", "questions": "-It will be good to add discussion about your techniques to prove the last iterate SGD convergence for non convex objectives. \n-Bounded variance: This assumption contradicts strong convexity. I understand it is in several works in the literature. Take for instance F(x,y,z) = zx^2 + (1-z)y^2, z follows Bernoulli (1/2), then E_z(norm(\\nabla F(x,y,z) - \\nabla E_z(F(x,y,z)))^2) = (x-y)^2 and this is not bounded for all x and y in R.\n-You mentioned in your criticism to the SOTA in the abstract that \" the existing results are all limited to a single objective..\", as far as I can check you are also considering only a single objective, not multi objectives. Composite optimization problem still a single objective?\n-I did not check the proofs carefully.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The work presents high-probability and in expectation convergence result for the last iterate of SGD in general domains for convex or strongly convex objectives", "weaknesses": "-In find the work incremental compared to the litterature. In fact, the work generelises the convergence results of the last iterate SGD for convex or strongly convex objectives to the general domains not necessarly compact. I find the content of the paper more adapted to be publisehd in a math/optimisation journal than ICLR.", "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": "", "extra_scores": {}}, {"review_id": "O6tJoJhAIV", "reviewer": "Reviewer_yV1Y", "summary": "This work studies the last-iterate convergence of stochastic gradient methods for convex optimization. The considered algorithm is general enough to include common algorithms as special cases, and the considered setting is general enough to cover general domain/unbounded noise/high probability bound/wide range of losses. This work achieves near-optimal bounds under these general settings, by a simple yet powerful observation made in a previous work Zamani and Glineur 23. The key technique is to leverage the convexity of loss for proving the last-iterate convergence, by carefully designing a sequence $z_t$ to compare the loss values with $x_t$. As a result, the obtained technical lemma yields a unified analysis for the general settings.", "questions": "It looks to me the presentation of results currently takes up a lot of space. Is it possible to make it more compact and add more discussions on the main idea of using $z_t$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work makes a solid contribution to the understanding of the last-iterate convergence of stochastic gradient methods, which is an important problem is convex optimization and particularly gains interest from the ML community, since in practice the theoretically sub-optimal choice of the last iterate is cheaper and thus more popular.\n\nThe technical results are general and cover a wide range of settings, bypassing a few constraints of previous works including assumptions on compact domain and bounded noise.\n\nThe idea of constructing the sequence $z_t$ to make use of convexity is intuitive yet powerful.\n\nBesides recovering the near-optimal convergence results under a more general setting, for smooth functions, this work provides an $\\tilde{O}(1/\\sqrt{T})$ bound which improves upon the previously known best result $O(1/T^{1/3})$.", "weaknesses": "I do not find any substantial weakness. One constraint of this work is that it lacks a proof sketch or discussion on the main idea in the main-text. I believe the paper can benefit from adding a simplest example of $z_t$, explaining how it's used to utilize convexity. Doing so can improve the readability by giving the readers more intuitions on the design of $z_t$ and how it works.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)