The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence
Authors: Daogao Liu
Zhou Lu
Venue: Submitted to ICLR 2023 (2023)

Abstract: Stochastic Gradient Descent (SGD) is among the simplest and most popular optimization and machine learning methods. Running SGD with a fixed step size and outputting the final iteration is an ideal strategy one can hope for, but it is still not well-understood even though SGD has been studied extensively for over 70 years. Given the $\Theta(\log T)$ gap between current upper and lower bounds for running SGD for $T$ steps, it was then asked by [Koren and Segal COLT 20'] how to characterize the final-iterate convergence of SGD with a fixed step size in the constant dimension setting, i.e., $d=O(1)$. 

In this paper, we consider the more general setting for any $d\leq T$, proving $\Omega(\log d/\sqrt{T})$ lower bounds for the sub-optimality of the final iterate of SGD in minimizing non-smooth Lipschitz convex functions with standard step sizes. Our results provide the first general dimension-dependent lower bound on the convergence of SGD's final iterate, partially resolving the COLT open question raised by [Koren and Segal COLT 20'].
Moreover, we present a new method in one dimension based on martingale and Freedman’s inequality, which gets the tight $O(1/\sqrt{T})$ upper bound with mild assumptions and recovers the same bounds $O(\log T/\sqrt{T})$ as previous best results under the standard assumptions.

Under review as a conference paper at ICLR 2023
THE CONVERGENCE RATE OF SGD's FINAL ITERATE: ANALYSIS ON DIMENSION DEPENDENCE
Anonymous authors Paper under double-bling review
ABSTRACT
Stochastic Gradient Descent (SGD) is among the simplest and most popular opti- mization and machine learning methods. Running SGD with fixed step size and outputting the final iteration is an ideal strategy one can hope for, but it is still not well-understood even though SGD has been studied extensively for over 70 years. Given the (log I') gap between current upper and lower bounds for running SGD for T steps, it was then asked by Koren & Segal (020) how to characterize the final-iterate convergence of SGD with a fixed step size in the constant dimension setting, i.c., = O(1). In this paper, we consider the more general setting for any d S T, proving (log d/ d/vT) lower bounds for the sub-optimality of the final iterate of SGD in minimizing non-smooth Lipschitz convex functions with standard step sizes. Our results provide the first general dimension-depenndnt lower bound the convergence of SGD's final iterate, partially resolving the COLT open question raised by Koren & Segal (2020). Moreover, we present a new method in one dimension based on martingale and Freedman's 's inequality, which gets the tight O(1/vT) upper bound with mild assumptions.
INTRODUCTION
Stochastic gradient descent (SGD) was first introduced by Robbins & Monro (195I). It soon became one of the most popular tools in applied machine learning, e.g., Johnson & Zhang 2013); |Schmidt et al. (2017) due to its simplicity and effectiveness. SGD works by iteratively taking small step the opposite direction of an unbiased estimate of sub-gradients and is widely used in minimizing convex function f over convex domain K., Formally speaking, given stochastic gradient oracle for an input x E X,, the oracle returns random vector 9 whose expectation is equal to one of the sub-gradients of f at z. Given an initial point x1, SGD generates sequence of points I1, "1,..., TT+1 according to the update rule
I++1 [gg[,; -n.it)
where IIx denotes projection onto 1C and (mer2: is a sequence of step sizes.
Theoretical analysis on SGD usually adopt running average step size, i.e., outputting + EE Ze in the end, to get optimal rates of convergence in the stochastic approximation setting. Optimal convergence rates have been achieved both convex and strongly convex settings when averaging of iterates is used Nemirovskij & Yudin (1983); Zinkevich (2003);Kaakdd Kakade & Tewari (2008): CCeaa Bianchi et al. (2044). Nonetheless, the final iterate of SGD, which is often preferred over the running average, as pointed out by
et al. (201)) has not been very well studied from the theoretical perspective, and convergence results for the final iterate are relatively scarce compared with the running average schedule.
Standard choices of step sizes for convex functions include = 1/V2 for unknown horizon T and 1/VT for known T, and 7/+ 1/t for strongly convex functions. In these cases, it is known that the finalitteatte convergence rate of SGD is optimal when is both smooth and strongly convex Nemirovski et al. (200))) However, in practice, the convex functions we want to minimize are often non-smooth. See Cohen et al. (2016); Lee et al. (2013) for more details. The convergence rate of SGD's final iterate with standard step sizes in the non-smooth setting is much less explored. Understanding this problem essential as the final iterate of SGD is popular and used often. If the last iterate of SGD performs well as the running average, yields very simple, implementable,

---

Under review as a conference paper at ICLR 2023
Work
Rate
Method
Convexity
Step size
Assumptions Smooth
Nemirovski al. 2009
O(1/T)
SGD
Strongly
1/t
Jain al. (2019)
O(I/VT)
SGD
Convex
standtadddr Non- son-standard
Jain et al. (2019)
O(1/T)
SGD
Strongly
Shamir & Zhang (2013)
Oloo T/vT)
SGD
Convex
1/vt
Shamir & Zhang
(2013)
(llg T/T)
SGD
Strongly
1/t
Harvey et al.
(2019a)
Milog T/VT)
GD
Convex
1/VE
d> T
Harvey et al. (2019a)
2(log I/T)
GD
Strongly
1/t
d2T T
Ours
Ailog d/v/)
GD
Convex
L/VT
d<T
Ours
A[llodd/\)
GD
Strongly
1/t
d
Table I: Convergence results for the expected sub-optimality of the final iterate of SGD for minimizing non-smooth convex functions various settings. GD denotes the sub-gradient descent method, and lower bounds of GD also hold for SGD, The lower bounds for Lipschitz convex functions in Shamir & Zhang (2013) 3) Harvey et al. (2019a) can also be extended to fixed step size 1/ I/VT, observed by Koren Segal (2020).
and interpretable form of SGD. If there is a lower bound saying the last iterate of SGD is worse than the running average, we may need to compare the last iterate and running average when implementing the algorithm.
line of works attempts to understand the convergence rate of the final iterate of SGD. A seminar work Shamir & Zhang 2013) first established a near-optimal O(log T/ convergence rate for the final iterate SGD with STANDARD step size schedule 7/ = 1/V2. Jain et al. (2019) proved an informatioon-hhooretiallll optimal D(I/T) upper bound using a rather NON-STANDARD step size schedule. Roughly speaking, the steps are divided into log T phases, and the step size decreases by half when entering the next phase. Many implementations take ever-shrinking step sizes. which is somewhat consistent with this theoretical result. Harvey et al. (2.1 (2019a) gave an Ql T/ T/VT) lower bound for the STANDARD 17 1/vÊ step size schedule, but their construction requires the dimension to be no less than T, which is restrictive. See Table [ more details. A natural question arises:
Question: What's 's the dependence on dimension of the convergence rate of SGD's 's final iterate with standard step sizes when d < T
In recent COLT open question raised by Koren & Segal (2020), the same problem was posed but mainly for the more restrictive constant dimension setting. Moreover, they conjectured that the right convergence rate of SGD with standard step size in the constant dimensional case is O /TT As preliminary support evidence for their conjecture, they analyzed a one-dimensional one-sided random walk special case. However, this result is limited in the one-dimension setting for the particular absolute-value function and thus can not be easily generalized. Analyzing the final-iterate convergence rate of SGD the general dimension for general convex functions is a more exciting and challenging question. In particular, in Koren & Segal 20200) they wrote:
For dimension d >> natural conjecture is that the right convergence rate is Olog d/VT), but have no indication to corroborate this.
Motivated by this, we mainly focus analyzing the final iterate of SGD with standard step size in general dimension d < T without smoothness assumptions in this paper.
1.1 OUR CONTRIBUTIONS
Our first main result an 2loog d/vT) lower bound for SGD minimizing Lipschitz convex functions with a fixed step size 7/: = 1/vT when dimension d < T, generalizing the result in Harvey et al. (2019a). Our main observation is that as long as 0 is one of the sub-gradient of f at T1. By modifying the original construction of Harvey ett al. (019a)),
let the initial point 2ı stay still for any number of steps
keep Di at 0 for T d steps and then 'kick' it to start taking similar route in Harvey et al. 2019a) in d-dimensional space, which incurs 2(log d/VT) sub-optimality.
2

---

Under review as a conference paper at ICLR 2023
This result is generalized to Lipschitz convex functions with 1/v decreasing step size schedule with the same sub-optimality, and an [log d/L)) lower bound to strongly convex functions with 1/t step size schedule is also constructed with the similar technique. Our lower bound results imply that the last iterate with fixed step size has sub-optimal convergence rate for SGD in general theoretically, which, unfortunately, is used lot in practice.
As for the upper bound, we present a new method based on martingale and Freedman's 's inequality analyze the one-dimensional case. Though seemingly straightforward, the convergence rate of fixed-step-size SGD for one-dimensional linear functions is still open and non-trivial, Koren & Segal (2020) considered minimizing linear function with restricted SGD oracle which only outputs =I. reducing this problem to a one-sided random walk. We relax the restriction on the SGD oracle and prove an D(1/VT) optimal rate for class of convex functions which we call nearly linear convex functions, with the help of martingale theory. The class of nearly linear functions captures many common functions, such as linear functions, |z], c², x² x sin(x) on [0, 1].
Our contributions are summarized follows:
We prove Slolg (T) lower bound for the sub-optimality of the final iterate of SGD minimizing non-smooth Lipschitz convex functions with тソt = 1/vT step size schedule. We also generalize this bound to the π/2 1/vl decreasing step size schedule, and also prove an (log d d/'T') lower bound for non-smooth strongly convex functions with 1 1/t. To the best of our knowledge, our results are the first that characterize the general dimension dependence in analyzing the final iterate convergence of SGD with standard step sizes.
We prove an optimal O(//VT) upper bound for the sub-optimality of the final iterate of SGD minimizing nearly linear Lipschitz convex functions with fixed ((1/VT) step sizes in one dimension, which captures a broad class of convex functions including linear functions.
PRELIMINARIES
Given bounded convex K. C Rd, and convex function f : K. R defined on K. our goal is to solve minlax: (xx) In the black-box optimization, there is no explicit representation of f. Instead, we can use stochastic oracle to query the sub- aob-rradients of form of a projection oracle. which outputs the closest point in K. to a given point x in the Euclidean norm, We introduce several standard definitions.
K. The set K is given in the
Definition (Sub-gradient). A sub-gradient g RRd of convex function K. - R al point x, is vector satisfying that for any E K.
f(x') - f(x) 2 (x' - z).
We use (f(x) to denote the set of all bradgeea of f at x. Definition (Strong Couvexity). A function f: K. - IR is said to be a-strongly convex, for any z,y K. and g E (x), the following holds:
f(y) f(x)
2 g (y x) + x11
(3)
Definition 3 (Lipschitz Function). A function f K. - IR is called G-Lipschitz (with respect to l norm), for any x, E K., we have that:
If(x) - f(y) S Gl|ar G||a-10 - vll2
Further, we assume I is convex, the above definition is equal to ||g]|2 for any sub- sub-gradient g-
Let IIx denote the projection operator on K., the (projected) stochastic gradient descent (SGD) is described Algorithm [] We make the following standard assumption on convex objective f and the SGD algorithm consider throughout this paper:
Assumption (Standard Assumption). We make the following assumptions for the objective f and running SGD:
The domain K. C R is convex and bounded with diameter D.
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Stochastic gradient descent with the final iterate output
1: Given K C IR_ initial point æ E K. step size schedule T);
2: for 1, ..... T: do
3: Query stochastic gradient oracle at 2, for de such that Elg 01 ..-..) 0f(m))
4: yt+1 = Ztt 7/-9t
5: 2t++1 (v++1)
6: end for
7:
return 2T+1
The objective f R convex and G-Lipschitz, and not necessarily differentiable.
The output stochastic gradients are bounded: llăella G. and we have Elge
I
|
91.... -6 0f())..
The first two items hold for both our lower bound and upper bound. Our results are in the strong versions regarding the third item. In particular, (GD). i... even if the gradient oracle always outputs 9. E 0f(z;) rather than in expectation, one still has the lower bound (log d/ /T). Our upper bound works for the SGD, where the oracle's outputs can be stochastic and one only assumes their expectations are sub-gradients.
lower bound even holds for Gradient Descent
LOWER BOUNDS
In this section prove our main result, that is the final iterate of SGD for (non-smooth) Lipschitz convex functions with fixed step sizes Ne = L/vT has sub-optimality 22 d/ d/vT), even with deterministic oracle. We build upon the construction in Harvey et al. (2019)), which is variant of classical lower bound constructions Nesterov (2003) and proves an ?2 T T/VT) lower bound for the digeesiimnii case d 2 T.
In a nutshell, we consider the setting d < T and construct function f along with special sub- gradient oracle such that the initial point stays still for the first T d steps, and then start moving in Algorithm in which the final iterate satisfies f2r++1) = M(log d/ d/vT). Then we extend the analysis to decreasing step sizes and strongly convex functions.
Let [3] be the set of positive integers no larger than j. For simplicity, we consider convex functions over the d-dimensional Fuclidean unit ball. Let O be the d-dimensional all-zero vector. We present our proof for general convex functions with fixed step sizes first. For decreasing step sizes and strongly convex functions, it is straightforward to scale our construction and get corresponding lower bounds, and we leave the proofs in the Appendix.
Theorem 4. For any positive integer T > O and 1 < T, there exists a I-Lipschitz convex function f K. + R. where K. C I2d is the Euclidean unit ball, and a non-stochastic sub-gne sub-gradient oracle satisfying Assumption such that when executing Algorithm on f with initial point 0 and step size schedule T/t 1/VT, I, the last iterate satisfies:
log d
f(xT+1) -min f(x) 2
(5)
zek
32vT
Proof. Let Ba be the Fuclidean unit ball and define f: BB. + for [d 1JU (0) to be:
f(x)
max H;(x) ogi
where H1(x) = hi x. and we define for i
aj (i
his = -b;
[ifi=js d
and = 8(d+1-)) bj b-= ( (frr j E [d]
(ifi
in which h:g is the j-th coordinate h2. Additionally, let hn and (x) = 0. It's straightforward to check that / is 1-Lipschitz on K, with minimum value of O. Furthermore, af()) is the convex
4

---

Under review as a conference paper at ICLR 2023
hull of (h, i E } where I(x) {i 0 H2(x) f())), which is standard fact in convex analysis Hiriart- Urruty & Lemaréchal (2013)
Setting I1 0. we observe that f(11) 0 which attains the global minimum, and by the characteri- zation of (x) from above, we know that bn = 0 is sub-gradient at æ1. This observation allows non-stochastic sub-gre sub-gradient oracle to output for the first T d steps and outputs hy where = min [xx) \ {0) for the last d steps. Define 21 -... = 2T- = 0, let T =: and we further define
TT 0j
b,
1- 1-i-T T
(ifl و <t-k())) T i (i
(
(for t > T +
We show inductively that these are precisely the first T itterates produced by algorithm I when using the sub- -ob-gradient oracle defined above. The following claim easy to verify from the definition.
Claim 5. We have the following claims:
zt non-negative. In particular, žo.j 2 - for j l T and zz.j = 0 for T 4VT
Zr. S 1 for all j. In particular, 2t E K.
2/T
Proof. It is evident that =t = 0 for j 2 1- T from the definition. As by 1 it suffices to
VT 2V7
prove that 0 < 0j 1-i-"" < T/T which is direct as 0 S - - T - 1 < d + d
We can now determine the value and sub grbddrrdient at 24. The case for the first T steps is trivial as the sub-gradient oracle always outputs O and æι never moves a bit. For the last d steps we have that z is supported on first T coordinates, and h,-T.2 Rt
1._r.2 2t for all i 13 T
For the other case T + S i < t,, one has that
T-
T---1
T (h+-T- - -:-TT-)
Σ
ztj (h+ T 14 h)) =
Σ
2t Stglh--T- - hi hi-T
=
1=1-T"
t-T-11
2t, (h: - h4s .) + 2ii- (he-T - hi -i-Tr.i-T-))
j=
1-7-1
Ztj + Zt,i (a:-T- + 1/2) >0
+1
which means 27 h--r- > 2, hi-r- for all T + +15i<t
The two results together guarantee that HІ-7 (2)) 2 H--T- (2)) for all T + +15 i and further f(xx) = H--T. (2t). Combining with the fact I(z.) = (t - T T",..., d + 1}, we conclude that the sub- sub-gradient oracle outputs h time t.
Lemma 6. For the function constructed in this section, the solution t- 2, for every T <t< T +
t-th step in algorithm 7 eequll
Proof. We prove this lemma by induction. For base case t = T" + 1, we know that 2 = 0 = xt
holds. Next, when 2, I, holds for some
1
U1+1, =2,
VT
b;
1-
for forl<p (trrs)j<tTT)) (for 2 2-77"
1 aj (ifijj<t-T)
/T
aj
VT
(ift-I"
VT (ift-T" <
T aj
bi t T
VT
for j <t T*)
b1
( for j = ---17 T*)
7T
2VT
for j > 1 T*)
5

---

Under review as a conference paper at ICLR 2023
So y1+1 2++1- Since 24-1 K, we have that T4+1 21+1-
From the above equivalence, we have that the vector Fa in algorithm which allows the determination of the value of the final iterate:
is equal to 2 for t [ 1],
1 1
log d
f(zr+1)= f(2r+1) Ha-1
24+1,2++15 8(d + j) 4vT
32vT
Remark 7. For the case d = we still have the Q11 (()/VT)) lower bound, by not using Σ 2i=1 in the last step.
log d
Remark 8. Notably, our lower bound is valid even for GD, where one can access noiseless lub-gradient oracle.
Theorem 4 improves the previously known lower bound by a factor of log d. implying an inevitable dependence on the dimension of the convergence of SGD's final iterate. Though our proof built upon Harvey et al. (2019a), their construction doesn't it apply directly. Other natural ways of adaption, for example, cyclic (gradient oracle repeatedly goes over each coordinate). repeated (gradient oracle stays at one coordinate for T/ steps then go to the next), do not work here.
Next, we extend this result to Lipschitz convex functions with step sizes T v and strongly convex functions with step sizes т) + both known to be the optimal choice of learning rate schedule. The proofs are mostly similar to that of Theorem 4 and we defer them to the Appendix.
Corollary 9. For any T and 1 < d < T, there exist a I- I-Lipschitz convex function f K. + R where K. C TR. is the Euclidean unit ball, and non-stochastic sub-gradien oracle satisfying Assumption such that when executing algorithm / on f with initial poins O and step size schedule f). = 1/vt, Lt, the last iterate satisfies:
logd
(XT+1) min f(x) 2 zEK
(6)
32vT
Corollary 10. For any T and 1 S d T, there exist a 3- 3-Lipschitz and -strrongly convex function f: - R where K c Bd is the Euclidean unit ball, and non-stochastic sub- aradggradiet oracle satisfying Assumption 4 such that when executing Algorithm [on with initial point O (the global minimum) and step size schedule T). 1/t, the final iterate satisfies:
log d
f(oT-1) min f(x) #EK
2 5T
UPPER BOUND IN ONE DIMENSION
With our lower bound, it is natural to conjecture that the optimal rate should be Ollog d/vT) when < T. In particular, it's believed that in the one-dimensional case, the optimal rate is ((1/VT).
As mentioned in the introduction, Koren & Segal 2020) considered random walk induced by linear function as evidence for this conjecture in one dimension, which somewhat restricted. In this section, we relax their assumptions by considering function class that call nearly linear functions, which capture broad class of functions, including linear functions, and prove an optimal rate O(//VT). For the general Lipschitz convex function class, our analysis also recovers the previously known best bound (
4.1 NEARLY LINEAR FUNCTIONS
Let f* = minzex (x) We need the following definition before defining nearly linear functions.
Definition 11. We say a point x is good if fxx - <
4GD
and define set of good points by S: VT
$ s= f(x)= - f < 4GD
VT

---

Under review as a conference paper at ICLR 2023
Now can define the convex function family. In nutshell, the class of nearly linear functions consider is the function such that at any not-good point, the absolute value of its sub gradient is not too small. Put it formally:
Definition 12 (Nearly Linear Function), We call corvex function I : K. - IR nearly linear if there exist a constant 0 < a S 1, such that for any xa & S which does not belong to the set of good points, we have El 91.-.. .9c-1] |cG,
We note that any general Lipschitz convex function is nearly linear with c = 1/VT, and our later analysis recovers the previously known best bound (log T/vT) under this interpretation. Therefore our method is a strict improvement over previous results.
The family of nearly linear f'unctions captures those functions whose sub-gradients do not change drastically outside the set of good points, for example, e= _² + x sin(x:). The linear functions considered in Koren & Segal (2200) lie in this family. The nice property of nearly linear functions allows a martingale- analysis which gives an improved ((1/VT) bound.
Our proof is based on the Martingale (difference) (See Appendix for a detailed definition), and we use Freedman's 's Inequality given below.
Theorem 13 (Freedman's Inequality, Theorem 1.6 in Freedman 1975)). Consider a real-valued martingale difference sequence {X+)t20 such that Xo O, and E[Xe+1 0 for all where (Frbe is the filtration defined by the sequence. Assume that the sequence is uniformly bounded, i... |x1 < M almost surely for all L. Now define the predictable quadratic variation process of the
martingale to be W. = =E F[x] for all 2 1. Then for all and o² > O and any
stopping time T, we have
12/2 02 + +M/33)
Pr
Σ X3 1=0
2EAW S for stopping time
r| s 2exp (-
Some previous works also martingale theory to analyze SGD. For example, Harvey et al. (20 201 generalizes Freedman's Inequality to demonstrate high probability (w.p. 1 - d') suboptimality bound O (log(1/8) log T/) for SGD with standard step sizes, which is improved to (log(1//)) by Harvey et al. (2019b).
4.2 ANALYSIS
We show how to improve the convergence of the last iterate of SGD with a fixed step size GVT in one dimension for nearly linear functions. The proof mainly consists of two parts. In the first part, we prove that for running SGD with fixed step sizes for any convex function satisfying Assumption I. with very high probability, the solution goes into the set of good points least once. In some sense, this is consistent with the known result that averaging scheme can achieve the optimal rate. straightforward get the following lemma by convexity.
4D
Lemma 14. For any E S, E 0f(x), one has
VT
Suppose we start from an arbitrary point xj E K. and the (random) sequence of the SGD algorithm with the fixed step size 17 is denoted by æ1, T2, ,T411, i.c. T++1 = IIx[ ; - -)))). The following lemma says that with very high probability, the solution enters S at least once.
Lemma 15. Given any In E K., and let n GVT For any nearly linear function f (under the Assumption 7 define == 00 SGD never goes back to S in the first steps, and T == mine(1 S i < x4 E S) otherwise. Ift T + and k > 10, we have that
4D
Pr[ra
x1] < 2exp(-(((T))
Lemma 15 shows that the probability that v, never entered S in the first T steps is negligible, whose proof can be found in the Appendix.
7

---

Under review as a conference paper at ICLR 2023
In the second part, bound the tail probability of the sub-optimality of the last iterate for nearly linear functions, from which we can bound the expectation of the sub-optimality. Roughly speaking, GDL and the last T + 1 - i steps all lie out the set of good points, and bound its probability by exp Oik + (T + 1 i))) And by Union Bound we know that the tail probability Pr]f(ET+1) optimal bound O ) VT
we consider the events that f(xT+1) f* N vT
GD vT - exp(- which is enough to get the
Theorem 16. Given positive integer T which is large enough, running SGD with a fixed step 4D on any nearly linear function f under Assumption I for T steps, one has
size 1j = GVT
GD VT
-
where f mingek f(x).
for any k 2 10. We define t = do if SGD never goes in the set S and let t == max; (1 sis x2 E S) otherwise.
Proof. We try to bound the tail probability, that is 12][(2++))
GDk -TT
One has
Pr]((FT+))- - f- GDk
VT
T+1 (
GDk
At 1] Pr(((rtt)))) - - GDk
At ===00 =0) o0]
TT
VT
T Pr(((ett)-11'
GDk Al= i]= Pr[[(TTTTT) - - GDk
A 1 = oo),
VT
where the second equality follows from the fact that Pr[f(eT+1)- - f the definition of S and & 2 10. By Lemma 15 we have
GDk vT
A t = T + 11
GDk xx= o0) S
Pr(S((T+1) - l
which is negligible when T is large enough.
At= i]. We use y = x, -;-1 to capture the movement of the solution. Let nı = inf and ng = supzes x, which exist because the domain bounded and the function is continuous. By Definition II there exists x² arg min f(x) such that either | - I01 2 4D/vT or [ng - x=1 2 4D/VT By our setting of step size 1), if æj > nR for some j. it is impossible that Ij+1 < nL,, and vice versa.
Now we begin to bound Pr[f(xT+1) - fr N CDk
VT
Consider the event = i and assume 1i+1 >> nR first. Hence 2j > nn for all <jST + 1. By the Assumption that f is nearly linear, we have [[[y]] [ G for some constant e E (0, (See Definition [1] Let Fi-1 be the filtration and 3/: = y/4 -By F.1l.. Obviously, we know
Ely;
Fi-1]= 0, löal < 2n/C' and {ū is martingale difference sequence. We know that
T+1 E[ 2 Fi-l S Eド= Eig Fi-1] S G² +1 i) as |ys| S n,.. Let W(,TT-1 := Ejzt1
by the assumption of being nearly t= Ef Ely, Fij1). It is evident that < GT +1 i)
linear and 1j nn-
Condition on f(øT+1) - -f" CDk At= i. It follows that T+1 Vi 2 D(k-1), More specifically, VT
vT
as E S and thus f(x;) 1 < 4GD we have that (1T+11 - f(x;) > CD(k-1) and further
VT
IT+1 -; T++1 Mj 2
D(k-4 Moreover, we know W(LT+1) S CT 1 i) and T+1
VT
5 GC which means Σ Σ== Uj = T+I U3 - Ej=+t Bly; Fy-1] 2 D(k-1)
VT
é = D(k-1) + 14/.
VI
As for the case when Fi+l < nr., conditioning on (((T+1)--*' - VT
GD: A i i <....
similar to get Ef Új < D(k-4)
/T 1e)
W(T+H] S G i) ^ -1
8

---

Under review as a conference paper at ICLR 2023
well. Hence we have
GD VT
T+1
D(k 4)
Pr]f(2++1) -
=t= i]
Pr[
Σ
-t=
VT
j=it1
T+1
D(k 4) VT
< Pr|
Σ y j=++1
+
(cT+)) S
Cn +
i)]
(8)
where the second inequality follows from the analysis above. Applying Freedman's Inequality (Theorem 13) over Equation ( one has
Pr(((rT+1) - 1 GDk
At=
VT
D(k-4) + +12132/2
max ([20)G(I+111)
2exp
GT + 1) + 21/ D(K-4)
/T
181)/3
VT
D(k-4) + +121/2
max
2exp
([2o)((++1-1)
De 2////3
3c
D(k
4)
<2exp
+ Cn/G(T + +1-
100G
VT
3c(k:
4)
3
=2exp(-
(T + +1-
40
10
Further, for k 2 10. we have
Pr[f(Er+1) - f GDk: VT
GDk
At +r([((TT1) - f²2 GDk
-
A 00
VT
VT
3c(k- 1
4)
3
2 expp(-
(T + 1-- +
40
10
i=1
20
3c(k
-
4)
exp(-
2exp(=(((V))))
36
40
where the last step follows from the fact that for any constant C > one has Σ
[--
exp(-Ci)di < 1/C. As a result, for 2 10GD/vT, we have that Pr[S(æt+1) f" M O(exp(-hA))
where A = O
I GD
Our conclusion follows from
hjdh 0(1/2) 0 Pr[f(1141) ff - Blf(er+1) --1=---- /==
GD
GD
(10)
VT
CONCLUSION
In this paper, we analyze the final iterate convergence rate of SGD with standard step size schedules, proving 2(log d/ /T) and (logg d/T') lower bounds for the sub-optimality SGD minimizing non- smooth general convex and strongly convex functions respectively. We also prove a tight O(1/vT) upper bound for one-dimensional nearly linear functions, more general setting than Koren & Segal (2020). This work is the first, to the best of our knowledge, that characterizes the dependence on dimension in the general T setting, and hope it advance our theoretical understanding of the final iterate convergence of SGD with standard step sizes, and guide the implementations in practice.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Nicolo Cesa- Desa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):0050-2577, 2004.
Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 9-21, 2016.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, 3(1):100-118, 1975.
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-probabillty bounds for strongly-convex stochastic gradient descent. arXiv preprint arXiv: 1909. 200900043, 2019b.
lean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals, volume 305. Springer science & business media, 2013.
Prateek Jain, Dheeraj Nagaraj. and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pp. 1752-1755. PMLR, 2019.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-323 2013.
Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. In NIPS, pp. 801-808, 2008.
Tomer Koren and Shahar Segal. Open problem: Tight convergence of sgd in constant dimension. In Conference on Learning Theory, pp. 3847-3851. PMLR, 2020.
Yin Tat Lee, Satish Rao, and Nikhil Srivastava. new approach to computing maximum flows using electrical flows. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 755-764, 2013.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal optimization, 19(4):1574- 1609, 2009.
Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):33-112, 2017.
Shai -Swwar,,, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal estimated sub-gradient solver for svm. Mathematical programming, 127(1); 2011.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pp. 71-79. PMLR, 2013.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936. 2003.
10

---

Under review as a conference paper at ICLR 2023
A MORE PRELIMINARIES
A.1 PRELIMINARIES ON MARTINGALE
We demonstrate some basic definitions with relationship to Martingale, which is used in the proof. Definition (Martingale). A sequence Y1, Y2, said to be a martingale with respect to another sequence X1, X2, ... for all nt
E[())) <0
EYx+1 x =Yn
Definition 18 (Martingale Difference). Consider an adapted sequence {i, on a probability
space. X is martingale difference sequence (MDS) if satisfies the following two conditions for all t:
E|Jx <000
[[[x, F a.s. a.s.
Definition 19 (Stopping Time). stopping time with respect a sequence of random variables X2, X3. is random variable T with the property that for each t, the occurrence or non- occurrence of the event T t depends only on the values of X2,X2, X3.' X
B OMITTED PROOFS FOR SECTION 3
B.1 PROOF OF COROLLARY 9
Proof. Define f K Ba + R and h2 E Rd for E [d + 1] U [0) by
[(x) max
H₂(x)
osisd+1
where H₂(x) h For i we define
0j bi
(f < < i)
VJ +j+T-6
h4.
(if -ifi=js d) and aj 8(d + 1 j)
bj
( (for j E [d]
2VT
0
(ificjsd
Additionally, let hg = 0 and Ho(x) = O. It's easy to check that f is 1-L.ipschitz with minimal value We have that 0f(x) is the convex hull of (h; i I(x) where Z(x) {i 2 H2(x) = f.)).
Our non-stochastic sub-gradient oracle outputs 0 for the first T - d steps and outputs hy where 2T-4+1 let T = d.
i' min I(x) {0} for the last d steps. Define 21
bi FJ+T aj E' VE
(i ( (ift T و s
21,
(fott T 1
We will show inductively that these precisely the first T iterates produced by algorithm ( using the sub-gradient oracle defined above. The following claim follows from definition.
Claim 20. We have the following claims:
zi non-negative. In particular, 21,, 2 for for
T and z1, = 0 for 2 1-
2t. I - ofr all j. In particular, 21 E K. 2/T
Proof. is obvious that 2t,j 0 for j 2 - T from the definition. As 1-1
b 1 it suffices
VIFI= 2/T
prove that 0 ag Lk=jtr vi 4/7
We have that
0
Σ VI j+TT- V
1 dr
2(1 2(-j-- -
2(1 G(-j--T (11)
Vt-I+ vJ
vt-1
k=
11

---

Under review as a conference paper at ICLR 2023
and further 1-j-"" T+1-j-1"
d+1-i /T
S 4vT by monotony. Thus 0 aj Lk=ftT Vk
1
V follows from the definition of az.
VT
We can now determine the value and sub-differential at 2t. The case for the first T steps is trivial as the sub- bob-gradient oracle always outputs 0 and 21 never moves bit. For the last d steps we have that 2 is supported on its first T coordinates and h h.-T.2 2t = h Ee for all > t T".
For T + +15 one has
t-T
T 2t (h4-T- hi-T-)=
Σ j=1-T-
2g(he-TT h)- 24 + 1)+ + Σ 2tz O.
which means 2 h2-T- >> 2, h--T- for all T +lsi<E t. The two results together guarantee that Hz-r- (2+) 2 H;-T. (zt) for all T + 1 S and further f(x)) Ht-T- (z+). Combining with the fact [(2)) (t (", 3.... d+ 1}, we conclude that the sub-gradient oracle outputs h
Lemma 21. For the function constructed in this section, the solution of t-th step in algorithm equals to 2 for every T < <t STS++1
Proof. We prove this lemma by induction. For base case t = T + 1, we know that 2t = 0 = holds. Next, when 2 F3 holds for some
11- -T .
Vt
by
aj Lk=j+T Vk
(for 1 ponljjst-nn TT) for j 2t-
1 0j (ifl)j<(-T)
bb
(ift- =jj=
V
0
(ift- <j
by
aj
Σl
Ek=str vi
(for j
T*)
b,
( for j = t T*)
VJ+T"
fro j 1 T*)
So Vr+1 2++1- Since ž K. have that Tr+1 21+1-
From the above claim we have that the vector x; in algorithm is equal to for / E [T + 1]. which allows determination of the value of the final iterate:
1 1
log d
f(#r+1) f(2T+1) = H
hat1
8(d + j) 4VT
32
B.2 PROOF OF COROLLARY
Proof. Define K Ba + R by H. E Rd for E [d + 1] (0} to be:
f(x)
max osi
Hx(x))
where H.(x)= 11 + / 1 and we define for i 2 1
hig = 0 (-
if lif
and aj = 2(d11-) (for j E [d]
0 (ifi
in which ha, is the j-th coordinate of h, Additionally, let ho = 0 and Hu(x) = || It's straightforward to check that f is 3-lipschitz and 1-strongly convex KC, with minimal value 0. Furthermore, (z)) is the convex hull of + E I(x)) where [(x) = (i 2 0 H₃(x) = fx)) Hiriart- standard fact in convex aniiysisHiiriart- Urrutyy & Lemaréchal 2013)
12

---

Under review as a conference paper at ICLR 2023
Setting 21 0, we observation that f(11) 0 which attains the global minimum, and by the characterization of (x) from above, we know that hg + I1 = 0 is a sub-gradient at 21- This observation allows our non-stochastic sub-gradient oracle to output O for the first T d steps and outputs hu + x where /' = min [(x) \.  {0) for the last d steps, since outputting 0 in the first
steps makes 21 ... DT -T+-++1 0 by the update rule of SGD. Define 21
2T-d+1 0,
let T = T - d and
1-(t- T----T----D0
(iflsj<t-T) SjST)
2t,j
(fort T ffrt>I*+I) +
We will show inductively that these are precisely the first T ittrates produced by algorithm I when using the sub sub-gradient oracle defined above. The following claim is easy to verify from definition.
Claim 22. We have the following claims:
žt is non-negative. In particular, 2z,j Z 20-13 for j < - T and a.j 0 2 1- T*,
= 0 1 E (T" + and = S -or 1 T +1. Thus E K. for all L.
Proof. The first claim simply follows from the fact that 1-T" d-j+1 from that (t (t- T -|-ي S -
S 1. The second claim follows
We can now determine the value and sub-differential at a, The case for the first 7 steps is trivial as the sub-gradient oracle always outputs and 11 never moves. For the value last steps we observe that supported on its first - T coordinates by definition,, and as a result h 21 h Zt for all > t> T
For the other case T + +15i < t, one have that
2 (h--T--h--T)) 14-T-))= Σ j=i
Whihhi-T - h4-T- 21,(a; + +1 +
Σ
2t, > 0.
-=
which means z 1T-T-- > z h for T +1 S Sisik L. The two results together guarantee that H,-T- (zx) 2 H; TT- (zt) for all T +1 < and thus f(zx) H,-r-(z)) Combining with the fact
I(a,) = {t- - T ..... d +}, we conclude that the sub-gradin gradiend oracle outputs h; +
Lemma 23. For the function f and its gradient oracle constructed in the proof, the output 2t of t-th step in Algorithm Sachhmm@qquee equuals to z for every T <IST+
Proof. We prove this lemma by induction. For base case = T + 1, we know by the definition of 2, that 2, = 0 = Iy holds. Next, when 2, x, for some f holds, we have that
Be+
=z.
(h+ ( + 20.5)
1 f 1-(1-T'---1))
( for 1 sijsstt-T> (for j2t22t-))
(ff
FF1-T==js1
0
0
(ift-T"<jsd
(t T j-
(for1 T*)
<
1 4
(ff1)j<t-T)
[fft-T=
[ -
1
(ift-T" <j d)
1-(1-7 T j)a
for j < <
for -
fro poj>t-Ty
So yet1 = 2t+-- Since 2 E KC, we have that de+1 = 2441
13

---

Under review as a conference paper at ICLR 2023
From the above equivalence have that the vector in algorithm is equal to for t [T 1}. which allows the determination of the value of the final iterate:
d
f(T++1) f(2++1) = -10741))=+++0000 (2+1(2T+1) 2
Σ
ha+1.
1
log
2 +1
27
57
C OMITTED PROOFS OF SECTION
4
C.I PROOF LEMMA 14
Proof. We prove this statement by contradiction. Suppose there exists æ E KC), 8 such that (+)) <
G By the convexity of f and the definition of sub-gradient and let..' K. be minimizer (arbitrarily .T.
the minimizers are not unique), one has
2 2(x)) Vf(oa
which implies that
f(x) ((*))((o - GD
VT
This means E S and thus is a contradiction.
C.2 PROOF OF LEMMA 1S
Proof. Let n2 = inf and ng = supres x, which exist because the domain is bounded. By our setting of parameters and definition, we know if zj > ng, then impossible that 2,+1 < nt, and xo, either 1 S sist. Without loss of generality, we consider first the case where z; > nn for all S < t. We define random variable y/-
vice versa. As we are considering
nn for all < i S f. or < for all
- to capture the movement of the solution for 1 S sist t.
Conditioning on T = oo, i.e. v; > nR for all S I, we have that [[ys] S -cnG = -4D/T for i 12 2 by Lemma 14] (the projection only makes the expectation smaller). By standard arguments, let F, be the filtration and T = yA Eigs F.-1]. ]. It easy to verify that {ūr} } is a martingale difference sequence:
F.
Ely F. - Ely
=
=.
(12)
E ||
< Gr < 0o.
(13)
Obviously, one has |0s| Gn VT
4D by the third line of Assumptions As result, Eb7
Fi-1] = Ely? Fi-1] (Ely, F(-1))2 < Ely? F < G22 Hence, we get the estimation
W. = Ei_ Fi-1l < (t - G2 Let & = Ei F(-1). We know that & =
Ei,EE Fi-1 -tp...
So far, we have shown that if x; > nı for all < sist t, then we must have 2 -tjjG, and at the same time D > Ei 9i 2 D which must happen. Similarly, x, < ny for all 1 < i < t, then we have & 2 tnjoG and - < El S D. If we can show the probability that | 2 trjoG and EL vel < D happen simultaneously is small, are done.
14

---

Under review as a conference paper at ICLR 2023
By the Freedman's 's Inequality, if = T 1, one has:
Pr[n, = oo | |n| < Pr(z; > nn. 1 S i S s
S2Pr
|e D 2 MyG
i=2
=2Pr[1
Σ i=2
D1
DAW, (t - G) AlA 2 t
(t-D)2
max 18/2T cnj
2exp
GTp + i6 (f- D)
<2exp(-0((T)).
We complete the proof.
15


Reviews:
[{"review_id": "rJQjSieyQO", "reviewer": "Reviewer_F4uV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper shows the lower bound for the final iterate of SGD and also upper bound for a class of nearly linear Lipschitz convex functions. The convergence result is dependent on the dimension $d$. ", "summary_of_the_review": "At the moment I do not support this paper because of the weaknesses noted above. ", "strength_and_weaknesses": "This paper provides the theoretical results on the upper bound and the lower bound for the final iterate of SGD. The authors consider dimension dependence on the convergence of SGD for non-smooth Lipschitz convex functions (upper bound) and nearly linear Lipschitz convex functions in one dimension (upper bound).\n \nThe first weakness is that the contribution of this paper is not really significant. There have been several lower bound results for SGD in the similar setting. The concept of nearly linear function is not motivated well enough. The contribution of the upper bound seems to be restrictive since it is dimension 1 and the results for SGD are not particularly interesting. In addition, the assumption that the domain is bounded is restrictive. \n\nThe second weakness is that some of the arguments are sloppy. For example:\n- Too much use of asymptotic notations (e.g. Theorem 15) make it really hard to verify the proof. It would be much better if the authors could clarify this.  \n- Theorem 15, without loss of generality: please clarify this.\n- Theorem 15, equation (10): how the conclusion changed into integration?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "da9WUaj1jEU", "reviewer": "Reviewer_6ixh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence of the final iterate of (projected) SGD for (strongly) convex Lipschitz problems defined on bounded domain with almost surely bounded noise in the stochastic subgradients. In this setup, the authors derive the lower bounds for the last iterate of the projected sub-gradient descent that are valid for $T \\geq d$, where $T$ is the number of iterations and $d$ is the dimensionality of the problem. The key idea behind proposed worst-case example is using the oracle that returns zero subgradient during the first $T-d$ iterations (the algorithm starts at the solution) and then the oracle returns \"bad\" subgradients that drift the method away from the solution. The derived lower bounds are valid for $1/\\sqrt{T}$ and $1/\\sqrt{t}$ stepsizes in the convex case and for $1/t$ stepsizes in the strongly convex case ($t$ is the iteration counter). Some upper bounds for SGD are obtained for $1$-dimensional problems that are \"nearly linear\".", "summary_of_the_review": "Overall, the paper addresses a very interesting problem and the derived lower bounds can be seen as a solid contribution to the literature on SGD. However, some proofs (especially for the results from Section 4) contain a lot of unexplained parts and require a lot of polishing. This is the only reason why I give such a low score: in the current shape the paper cannot be accepted. However, if the authors fix all the raised issues, I will be happy to increase my score.", "strength_and_weaknesses": "## Strengths\n\n1. **Lower bound for the final iterate and fixed dimension.** This result is new for the literature and highlights the differences between the last-iterate and averaged-iterate convergence guarantees. It does not directly follow from the existing approaches for constructing lower bounds.\n\n2. **Several classical stepsize schedules are considered.** The considered stepsize policies are among the most popular ones. This fact additionally justifies the importance of the derived results.\n\n\n## Weaknesses\n\n1. **Proofs contain a lot inaccuracies and missing parts.** I cannot verify the proof of Theorem 15, because it contains a number of inaccuracies and unexplained derivations. In the list of detailed comments, I provide all inaccuracies that I noticed. The authors should make the proofs much clearer according to my comments.\n\n2. **Bounded domain.** The bounded domain assumption is quite restrictive. I have not found the place in the proof of the lower bounds where the authors rely on this (except for the strongly case, since without this assumption the class of the considered functions is empty). So, at least for Theorem 4 and Corollary 8 the authors can remove this assumption, if I am not missing anything. However, in the proof of the upper bound the authors do rely on the boundedness of the domain. This is a significant limitation.\n\n3. **Bounded stochastic subgradients.** The third part of Assumption 1 is very restrictive, since it means that the noise is bounded. Is it possible to remove this assumption to get a similar upper bound?\n\n## Detailed questions and comments\n\n1. I think the paper will benefit from more in-depth comparison with the results from Jain et al. (2019). Although they have non-standard stepsizes, it will be good to provide them in this paper and discuss the differences with the standard ones.\n\n2. The construction used in the proof of the lower bound significantly relies on the fact that the oracle acts in an adversarial manner. This is possible because of the non-smoothness of the problem. However, in many real problems the set of points where the objective is non-smooth has zeroth Lebesgue measure and the methods rarely occur in these points (especially if we consider stochastic methods). Moreover, the choice of the subgradient can be non-adversarial (e.g., one can try to choose the subgradient somehow randomly to avoid bad behavior). That is, it would be interesting to derive some lower bounds in less adversarial setups than in the one considered in this paper.\n\n3. Page 5, the derivation after \"For the other case $T^\\ast + 1 \\leq i < t$\": I do not understand the second equality. Could the authors provided a detailed derivation? If I am not mistake, $h_{i - T^\\ast, j} = 0$ for all $j > i - T^\\ast$ and $h_{i - T^\\ast, i - T^\\ast} = - \\frac{1}{2}$. I do not see how it is reflected in the derivation.\n\n4. The discussion after Remark 7: one should emphasize that this lower bound is valid even for GD.\n\n5. Proof of Theorem 15, the derivation after \"One has\": the first equality is not correct since the events are not independent. One should replace \"$=$\" with \"$\\leq$\".\n\n6. Proof of Theorem 15, \"Without loss of generality\": why the generality is not lost? I think it is possible to have $x_j > n_R$ and $x_{j+1} < n_L$ (due to the stochasticity). How the proof will work in this case?\n\n7. Proof of Theorem 15, \"for some constant $c = \\Theta(1)$\": this should be specified formally in the theorem.\n\n8. Proof of Theorem 15, the upper bound for $W_{(i, T+1]}$: I do not understand how it is derived. Could the authors provided the detailed derivation? In particular, it is unclear why the absolute value is inside $|\\cdot|$.\n\n9. Proof of Theorem 15, the upper bound for $\\ell$: I do not see how this upper bound is obtained. The authors should provide a detailed derivation.\n\n10. The last step in formula (8) is unclear. The authors should provide a detailed derivation.\n\n11. Page 9, \"Applying Freedman's Inequality (Theorem 12)\": Theorem 12 does not provide such inequality. The authors should provide the details on how Theorem 12 is applied here. Because of these inaccuracies, I did not check the next part going after \"And further\". The authors should proofread it as well.\n\n12. Formula (10): why the integration is taken from $0$ to $GD$? Why this is $O(\\lambda)$? The authors should provide a detailed derivation.\n\n13. Appendix C.1: there is a mistake in the definition of sub-gradient.\n\n14. Proof of Lemma 14, \"Without loss of generality\": similar question to 6.\n\n15. Proof of Lemma 14, the derivation after \"As a result\": in then end one should have $\\mathbb{E}[|y_i| \\mid \\mathcal{F}_i]$.\n\n16. Proof of Lemma 14, lower bound for $\\ell$: how is it derived? The authors should provide a detailed derivation.\n\n17. Proof of Lemma 14, last formula, second inequality: why does it hold? The authors should provide a detailed derivation.\n\n18. Proof of Lemma 14, last formula, last inequality: it is not a direct application of Freedman's inequality. The authors should provide a detailed derivation.\n\n## Minor comments\n\n1. Paragraph after the proof of Claim 5: \"supported on its first $t - T^\\ast$\" --> \"supported on its first $t - T^\\ast - 1$\"\n\n2. Lemma 6: \"algorithm 1\" --> \"Algorithm 1\" (and everywhere else)\n\n3. The end of Page 5, the third row of the derivation for $y_{t+1,j}$, the first case: one should not have $-1$ in the numerator.\n\n4. Definition of $S$: I suggest to change the notation to $S_T$ since $S$ depends in $T$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RRlSaUC1_a", "reviewer": "Reviewer_axZ4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies loss of the last iterate of the gradient descent in stochastic non-smooth settings. For the case d < T, they show the lower bound  Ω(log d / sqrt{T}) on the final iteration loss with the learning rate 1/\\sqrt{T}, and show an upper bound O(1 / sqrt{T}) on the loss for certain class of functions.\n", "summary_of_the_review": "Incremental work which would benefit from better presentation.", "strength_and_weaknesses": "I have the following concerns about the paper:\n-- The main concern is that the result looks incremental. Basically, the idea is to freeze the iterate for the first T-d iterations, and then follow the proof which achieves Ω(log T / sqrt{T}) lower bound.\n-- Related to the previous point, the sqrt{T} factor in the bound looks a bit arbitrary. I understand that the learning rate 1 / sqrt{T} (and other learning rates considered in hte paper) is chosen since it’s a popular choice for the optimization. However, it could as well be almost any other learning rate, giving a different lower bound. To clarify my point: when I started reading the proof, I was wondering why the bound was not Ω(log d / sqrt{d}), given that we simply ignore all but last d iterations. And the only reason for that turned out to be the choice of learning rate.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "HNC99ysaqEb", "reviewer": "Reviewer_ao7o", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper derives upper and lower bounds on the excess risk of last iterate of SGD in small dimensions with \"standard\" step-size schedules. They provide two main results: a lower bound of $\\Omega\\left(\\frac{\\log{d}}{\\sqrt{T}}\\right)$ on excess risk\nfor convex Lipschitz functions (which is also extended to strongly convex functions). Secondly, they define a sub-class which they call nearly-linear functions, and show that SGD with a step-size of $\\frac{1}{\\sqrt{T}}$ achieves the optimal rate of $O\\left(\\frac{1}{\\sqrt{T}}\\right)$ on this sub-class in one dimension.", "summary_of_the_review": "I think the authors present important results on a fundamental problem. The only downside is that topic may be too specialized for ICLR.", "strength_and_weaknesses": "Strengths:\n\n\nThe authors make progress on a COLT 2020 published open problem, so the the question has certainly been deemed important by the community. In particular, even though SGD is a seemingly \"simple\" and widely-studied procedure, a tight characterization of the error of its final iterate is still not understood even in one dimension. Hence, the question is very natural. Both the results presented in the paper makes important contributions towards this problem. \n\nThe paper is well-written and presents the state of the problem well and give sufficient details of results and techniques of prior works. The proofs aren't long and complicated and it was nice that they could be presented in (almost) full details in the main text itself.\n\nWeaknesses:\n\nI think even though the results are important, in the bigger picture, the scope of the paper seems limited. \nFirstly, the existing gap is only a $\\log T$ factor.\nMore importantly, from an algorithm design perspective, we know (as discussed in the paper) that simple changes like returning the average iterate or last iterate but with a more complicated step-size suffices to get the optimal rate.\nTherefore, the results may be (very) interesting to a very specific sub-community and not to the general ICLR audience.\n\n\nI have some questions as well as minor corrections about the proof details:\n\n- In the lower bound construction in Theorem 4, it seems that the constructed sub-gradient oracle maintains state -- in particular, on the same input, it gives different outputs as sub-gradients based on the iteration counter. This is a more powerful oracle than used in typical lower bound constructions that I am familiar with. I know that it is within the purview of settings in which the upper bounds are typically stated. \nBut is this something which has been used in prior works? Also, do the authors think that it may be possible to get rid of this additional power?\n\n- Small missing argument before Lemma 6 -- for a complete argument, it seems that you should also argue that $H_i(z_t) < H_{t-T*}(z_t)$ for $i<t-T^*$ and then you have $I(x)\\subseteq \\\\{ t-T^*,..d+1 \\\\}$  (it says $=$ currently), right?\n\n- In the proof of Theorem 15, shouldn't it be $\\eta G(T+1-i)\\leq |l|\\leq c\\eta G(T+1-i)$ i.e. the lower bound does not have the factor $c$, since $\\mathbb{E}[y_i] \\in [-c\\eta G,-\\eta G]$? But it seems that this may affect the part of proof where you recover the $O(\\log{T}/\\sqrt{T})$ rate for general convex functions. What am I missing here?\n\n- Typo: In the proof of Lemma 6, right hand side of third equality should have $a_j \\frac{t-j-T^*}{\\sqrt{T}}$\n\n- Typo: In the proof of Theorem 15, shouldn't the definition of $W_{(i,T+1]}$ have $\\tilde y_j^2$ as the summand?\n\n- Typo: should be seminal instead of seminar in third line in page 2.\n\n- Typo? I don't understand the sentence \"Our results are in the strong versions regarding the third item\" just before start of Section 3.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject