Gradient Descent’s Last Iterate is Often (slightly) Suboptimal
arXiv:2604.13870v1 [math.OC] 15 Apr 2026
Guy Kornowski1 Ohad Shamir1,2 1 Weizmann Institute of Science 2 University of Toronto {guy.kornowski,ohad.shamir}@weizmann.ac.il April 16, 2026
Abstract We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. By now, it is √ known that standard stepsize choices lead to a last iterate convergence √ rate of log T / T after T steps. A breakthrough result of Jain et al. [2019] recovered the optimal 1/ T rate by constructing a non-standard stepsize sequence. However, this sequence requires choosing T in advance, as opposed to common stepsize schedules which apply for any time horizon. Moreover, Jain et al. conjectured that without prior knowledge of T , no stepsize sequence can ensure the optimal error for SGD’s last iterate, a claim which so far remained unproven. We prove this conjecture, and in fact show that even in the noiseless case of GD, it is impossible to avoid an excess poly-log factor in T when considering an anytime last iterate guarantee. Our proof further suggests that such (slightly) suboptimal stopping times are unavoidably common.
1
Introduction
Let f : X → R be a convex Lipschitz function over a convex domain X ⊂ Rd , and consider the stochastic gradient descent (SGD) algorithm1 starting from x0 ∈ X : xt+1 = ProjX (xt − ηt gt ) for all t ∈ N ,
(1)
where E[gt ] ∈ ∂f (xt ), and (η0 , η1 , . . . ) is the stepsize sequence (also referred to as learning rate). Although SGD has been studied extensively for decades [Robbins and Monro, 1951, Nemirovski and Yudin, 1983], and is commonly considered the main workhorse of machine learning [Zhang, 2004, Bottou, 2010, Goodfellow et al., 2016], there still remain some surprisingly fundamental √ gaps in its theoretical analysis. The textbook analysis of SGD implies that √ for stepsizes ηt = Θ(1/ t), the error of the average iterate P ( T1 Tt=1 xt after T steps) converges at a 1/ T rate (cf. Hazan, 2016, Theorem 3.4). This well-known result has the clear drawback that in practice, it is much more common to return the last iterate obtained, namely xT , rather than the average iterate. √ However, the last iterate of SGD with the aforementioned stepsizes only converges at a suboptimal log(T )/ T rate [Shamir and Zhang, 2013, Harvey et al., 2019], differing from the information-theoretically optimal rate by an excess log factor. This unsatisfying aspect led to substantial research efforts analyzing the last iterate convergence of SGD under various settings, as well as motivated 1
Strictly speaking, in this work we do not assume differentiability of f , and consider sub-gradient methods.
1
the design of modified output rules that recover the optimal rate. We further discuss prior works along these lines in Section 1.1. √ Ultimately, Jain et al. [2019] proved that the last iterate of SGD can indeed converge at an optimal 1/ T rate after T steps. At the heart of this remarkable result is the design of a non-trivial stepsize sequence −1 (ηt )Tt=0 , which unfortunately still suffers from a shortcoming: its values depend on T , and therefore the number of steps T must be chosen in advance. In other words, after completing a predetermined budget of T steps, if additional steps are required or desired, it is unclear how to continue minimizing the error at an optimal rate. In many applications however, it is desirable to have anytime algorithms with anytime guarantees, and the anytime nature of SGD is arguably one of its appeals in the first place. The described issue was raised already by Jain et al. [2019], where the authors conjectured that “in absence of a priori information about T , no step-size sequence can ensure the information theoretically optimal error rates for final iterate of SGD.” The conjecture has so far remained unproven, leaving a natural open problem in the theoretical analysis of SGD, as to whether the last iterate can achieve optimal convergence in an anytime fashion. In this work, we resolve this question and answer it negatively. In fact, we show that even in the noiseless case, the last iterate of gradient descent (GD, i.e. gt ∈ ∂f (xt ) deterministically) cannot possibly avoid an excess poly-log factor compared to the optimal rate, whenever the stopping time is not carefully chosen in advance. This stronger lower bound for anytime GD proves the conjecture of Jain et al. [2019] for SGD as a special case. The paper is structured as follows. After discussing related work, we present in Section 2 the formal setting that we consider. In Section 3 we state our main result, and discuss some notable consequences. In Section 3.1 we present the key proof ideas, with some formal proof details deferred to the appendix. We conclude in Section 4.
1.1
Related Work
Last iterate of SGD. As previously discussed, classical analyses of SGD typically deal with the convergence of the average iterate [Polyak and Juditsky, 1992, Nemirovski et al., 2009]. Zhang [2004] analyzed the convergence rate of the last iterate of SGD with constant stepsize for learning linear predictors. This was extended to general convex objectives and decaying stepsizes in Shamir and Zhang [2013]. Harvey et al. [2019] further established tight high probability bounds. Tight constants were derived for GD in the deterministic setting by Zamani and Glineur [2023]. The general smooth setting was studied by Moulines and Bach [2011], with results later improved by Taylor and Bach [2019], Liu and Zhou [2024b]. Several recent works studied last iterate convergence in the so called (near-)interpolation or low-noise regime, first for least-squares [Varre et al., 2021] and subsequently for general smooth losses [Attia et al., 2025, Garrigos et al., 2025]. Several works considered objectives with an empirical risk minimization structure, and established last iterate convergence for SGD with respect to different sampling schemes [Gower et al., 2019, Liu and Zhou, 2024a], which was further studied through connections to continual learning [Evron et al., 2025, Cai and Diakonikolas, 2025]. Optimal convergences rates. Several works considered modifications of SGD or of its output rule in order to remove excess log factors and recover optimal rates for strongly-convex objectives [Hazan and Kale, 2014, Rakhlin et al., 2012, Lacoste-Julien et al., 2012]. The question of whether some form of averaging is needed for SGD to recover optimal rates in this context was raised by Shamir [2012], and answered affirmatively
2
by Harvey et al. [2019] both for strongly-convex and convex √ objectives. However, their results applied only for the theoretically standard choice of step sizes (Θ(1/ t) in the convex case and Θ(1/t) in the stronglyconvex case). As previously discussed, Jain et al. [2019] then showed that it is possible to recover optimal rates with SGD’s last iterate by considering non-standard stepsizes that depend on the stopping time T . Anytime smooth GD. In the related setting of smooth convex deterministic optimization, recent works designed non-standard stepsizes for GD that accelerate the well-established convergence rates of constant stepsizes [Altschuler and Parrilo, 2024, Grimmer et al., 2025]. It was noted by Kornowski and Shamir [2024] that these results do not yield anytime improvements, and it was asked whether such improvements are possible, which was then answered positively by Zhang et al. [2025]. It is interesting to note that in the smooth deterministic setting, the best known anytime bounds differ from non-anytime bounds by polynomial factors, and it is an open problem as to whether this is necessary. In contrast, in this work we prove that poly-logarithmic gaps are necessary in the non-smooth setting.
2
Preliminaries
Notation. We denote N := {1, 2, . . . } and [n] := {1, . . . , n}. We use bold-faced font to denote vectors, e.g. x ∈ Rd , and denote by ∥ · ∥ the Euclidean norm. We denote dist(x, A) := inf a∈A ∥x − a∥ for A ⊂ Rd , x ∈ Rd , and by ProjA the projection operator onto A. ∂f (·) denotes the sub-gradient set of a convex function f . A function f : X → R is called G-Lipschitz if for any x, y ∈ X : |f (x) − f (y)| ≤ G ∥x − y∥. We use the standard big-O and little-o notation, with O(·), Ω(·) and Θ(·) hiding absolute constants that do not depend on problem parameters, and at = o(bt ) meaning limt→∞ at /bt = 0. Setting. Throughout the paper we impose the standard assumptions that f : X → R is convex and GLipschitz where X ⊂ Rd is a closed convex domain. Given an initial point x0 ∈ X , we consider the sub-gradient method (as in Eq. (1)) so that gt ∈ ∂f (xt ), with stepsize sequence η = (ηt )∞ t=0 . Given a stepsize sequence, we are interested in its worst-case anytime last iterate guarantee: G,D Definition 1. For stepsize sequence η = (ηt )∞ : N → R≥0 is an anytime convergence t=0 , we say that Eη rate guarantee for η, if for all G-Lipschitz and convex f over domain X with diameter at most D, and initialization x0 ∈ X , it holds that
f (xt ) − min f (x) ≤ EηG,D (t) for all t ∈ N . x∈X
For example, we recall the following known anytime last-iterate convergence guarantee: √ Example 2 ([Shamir and Zhang, 2013]). The stepsize sequence η = (D/G t + 1)∞ t=0 has the anytime DG(4+2 log t) G,D √ convergence guarantee Eη (t) = . t
3
Main Result
We are now ready to present our main result: Theorem 3. No stepsize sequence η has an anytime convergence guarantee satisfying ! 1/8 DG log (t) √ EηG,D (t) = o as t → ∞ . t 3
√ In particular, neither SGD nor GD’s last iterate can yield the optimal 1/ t rate in an anytime fashion. Remark 4 (absence of noise). As previously mentioned, Theorem 3 confirms the conjecture of Jain et al. [2019], and is in fact stronger as it applies even in the noiseless case of GD. It is interesting to note that an intuition conveyed by Jain et al. [2019] is that noise in the sub-gradients can lead SGD to be “bad in expectation” (precisely defined therein) even in one dimension. Our proof is based on a different perspective, where instead of noise, the key factors driving the lower bound constructions are high-dimensionality and not knowing when the algorithm should stop. We discuss this in more detail in Section 3.1. Remark 5 (suboptimal stopping times are common). Note that a stepsize sequence can have a guarantee √ G,D EηG,D with a sub-sequence (tk )∞ (tk ) = O(DG/ tk ). For example, applying k=0 ⊊ N satisfying Eη a “doubling trick” by concatenating optimal time-dependent stepsize sequences (e.g., as provided p by Jain G,D k k et al. 2019) √ for increasing powers of 2, yields an infinite sequence η so that Eη (2 ) = O(DG/ 2 /2) = O(DG/ 2k ). It is therefore interesting to ask how “dense” suboptimal stopping times are. Our proof actually shows that for any stepsize sequence, as T → ∞, a uniformly random stopping time t ∈ [T ] suffers from the aforementioned poly-log overhead. In other words, (slightly) suboptimal stopping times necessarily have so-called positive natural density [Niven, 1951], and therefore occur often, in a suitable sense.
3.1
Proof of Theorem 3
By a rescaling argument, it suffices to prove Theorem 3 for G = 1, D = 2, and we abbreviate notation accordingly by denoting Eη = Eη1,2 . Let η be some stepsize sequence, and suppose it has a corresponding anytime guarantee satisfying ϕ(t) Eη (t) ≤ √ (2) t for some non-decreasing function ϕ : N → [1, ∞) (e.g. ϕ(t) = c1 logc2 (t)+c3 for some constants c1 , c2 , c3 ). Our goal is to show that it cannot be that ϕ(t) = o(log1/8 (t)). To that end, √ we start by establishing two basic lower bounds on Eη (t), and therefore on ϕ(t) (which is at least Eη (t) t), in terms of (η0 , . . . , ηt−1 ). Lemma 6. For any stepsize sequence η and t ∈ N it holds that: 1. Eη (t) ≥ ηt−1 . P 1 1 2. If t−1 j=0 ηj ≥ 2 , then Eη (t) ≥ 4e2 Pt−1 η . j=0
j
Both of the bounds above holds already in one dimension. The first follows from considering a “vshaped” function with a minimum at 0, and noting that if xt−1 is very close to the minimum, then |xt | ≈ ηt−1 , which therefore serves a lower bound on the last-iterate error.2 Intuitively then, the lower bound on the last-iterate holds due to the algorithm not knowing when it should stop. The second bound follows from considering a quadratic, and it shows that the stepsize sum needs to grow at a rate of roughly Eη (t)−1 ≥ √ t/ϕ(t). The proof of Lemma 6 is deferred to the appendix. Next, we establish a third lower bound on Eη (t). 2
An easy, somewhat hacky way to prove this bound is simply by considering f (x) = |x| initiated at zero, so that all subgradients until time t are 0 ∈ ∂f (0), and then gt = 1 ∈ ∂f (0). The proof provided in the appendix however does not rely on an inconsistent sub-gradient choice.
4
Lemma 7. For any stepsize sequence η, any t ∈ N and ϕ as in Eq. (2), it holds that √ t−1 X min{1, ηj t + 1}2 1 √ Eη (t) ≥ . (t + 1 − j) 64ϕ(t + 1) t + 1 j=0
(3)
The proof of Lemma 7 is substantially more involved than the previously discussed bounds. It is highdimensional in nature, and is based on modifying a technique of Harvey et al. [2019] which builds on a lower bound for max-of-linear functions due to Nemirovski and Yudin [1983], as detailed in the appendix. √ √ We further note that min{1, ηj j + 1} ≥ ηj j + 1/ϕ(j + 1), since by Lemma 6.1 and Eq. (2) it holds √ that ϕ(j + 1) ≥ ηj j + 1 and ϕ(j + 1) ≥ 1. Hence, Eq. (3) implies that for any t ∈ N :
Eη (t) ≥
√ t−1 t−1 X X ηj2 (j + 1) (ηj j + 1/ϕ(j + 1))2 1 1 √ √ ≥ . (t + 1 − j) 64ϕ(t + 1) t + 1 j=0 64ϕ(t + 1)3 t + 1 j=0 (t + 1 − j)
ϕ(t+1) √ ≤ √ , we can rearrange and get Therefore, since Eη (t) ≤ ϕ(t) t t t−1 t−1 ηj2 j 1 X 1 X ηj2 (j + 1) ≥ . ϕ(t + 1) ≥ 128 (t + 1 − j) 128 (t + 1 − j) 4
j=0
(4)
j=0
With a lower bound on ϕ in hand, it remains to lower bound the sum above, which as discussed in Remark 5, we can obtain even for a constant fraction of t ∈ [T ] as T → ∞. To that end, as the bound above holds for all t, we let T ∈ N be some arbitrarily large time scale which we can average over, and get that 128ϕ(T + 1)4 ≥
T T t−1 jηj2 1X 1 XX 128ϕ(t + 1)4 ≥ T T (t + 1 − j) t=1
t=1 j=0
=
=
1 T
T −1 X
kηk2
T X t−1 X 1{j = k}
k=1
t=1 j=0
T −1
T
k=1 T −1 X
t=k
(t + 1 − j)
1 1 X 2X kηk T (t + 1 − k)
1 = T
" kηk2 HT +1−k
where Hn :=
n X 1 i=1
k=1
#
i
T /2
HT /2 X 2 ≥ kηk . T k=1
5
(5)
Moreover, for t1 < T soon to be chosen it holds that T /2 X
kηk2 ≥
k=1
T /2 X
kηk2 ≥ t1
T /2 X
ηk2
k=t1
k=t1
2 T /2 X t1 ≥ ηk T /2 − t1
(1)
k=t1
(2)
t1 ≥ T /2 − t1
!2 p √ T /2 + 1 , − 2ϕ(t1 ) t1 + 1 4e2 ϕ(T /2 + 1)
(6)
where (1) follows from a standard ℓ1 /ℓ2 inequality (for every vector x ∈ Rn : ∥x∥22 ≥ ∥x∥21 /n), and (2) is due to the fact that using Lemma 6, it holds that T /2 X k=t1
ηk =
T /2 X k=0
ηk −
tX 1 −1 k=0
p tX t1 1 −1 X T /2 + 1 1 1 √ ηk ≥ 2 − Eη (k + 1) ≥ 2 − ϕ(t1 ) 4e Eη (T /2 + 1) 4e ϕ(T /2 + 1) k k=0
k=1
p √ T /2 + 1 ≥ 2 − 2ϕ(t1 ) t1 + 1 . 4e ϕ(T /2 + 1) /2+1 By setting t1 := ⌊ 28 e4Tϕ(T ⌋ − 1, it holds that /2+1)2
p p √ T /2 + 1 T /2 + 1 − 2ϕ(t1 ) t1 + 1 ≥ 2 , 2 4e ϕ(T /2 + 1) 8e ϕ(T /2 + 1) which plugged back into Eq. (6) gives T /2 X
kηk2 ≥
k=1
≥
T 29 e4 ϕ(T /2+1)2 1 1 2 − 29 e4 ϕ(T /2+1)2
T 213 e8 ϕ(T + 1)4
· T
T /2 8e2 ϕ(T /2 + 1)2
.
Going back to Eq. (5), we see that 128ϕ(T + 1)4 ≥
HT /2 T · 13 8 . T 2 e ϕ(T + 1)4
By rearranging and recalling that the harmonic sum grows logarithmically, we overall get ϕ(T + 1) ≥
(HT /2 )1/8 25/2 e2
≥
which completes the proof.
6
1 25/2 e
· log1/8 (T /2) ,
4
Discussion
In this work, we proved that the last iterate of GD cannot converge at the information-theoretically optimal rate whenever the stopping time is not chosen in advance. As discussed, this proves a conjecture of Jain et al. [2019] regarding SGD. Our work leaves open several follow-up questions. In future work, we plan to extend our techniques to handle the strongly-convex case, where there exist similar gaps between the anytime log T /T last iterate rate [Shamir and Zhang, 2013] as opposed to 1/T when T is chosen in advance [Jain et al., 2019]. Another open direction is noting that while our result is qualitatively stronger than anticipated as it applies even to deterministic GD, it is quantitatively weaker √ than the known √ anytime upper bound (Example 2), 1/8 leaving open a fine-grained gap between log (T )/ T and log(T )/ T . Finally, following the discussion in Remark 5, we recall that the doubling trick is the only procedure we are aware of that constructs a subsequence of iterates converging at the optimal rate. It is interesting to note that this leads to exponentially increasing optimal stopping times, and therefore the set of optimal stopping times form a zero-density set.3 Hence, it is natural to ask whether this is inevitable: Is it true that for any stepsize sequence, any subsequence of stopping times which converge optimally necessarily has density zero? Notably, this corresponds to strengthening our result from suboptimal stopping times having positive density to always having density 1. Acknowledgments.
3
GK is supported by an Azrieli Foundation graduate fellowship.
A set T ⊂ N is called a zero-density set if limn→∞ |T ∩{1,...,n}| = 0. n
7
References Jason M Altschuler and Pablo A Parrilo. Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex optimization. Mathematical Programming, pages 1–14, 2024. Amit Attia, Matan Schliserman, Uri Sherman, and Tomer Koren. Fast last-iterate convergence of sgd in the smooth interpolation regime. arXiv preprint arXiv:2507.11274, 2025. Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT’2010: 19th International Conference on Computational Statistics, pages 177–186. Springer, 2010. Xufeng Cai and Jelena Diakonikolas. Last iterate convergence of incremental methods and applications in continual learning. In International Conference on Learning Representations, 2025. Itay Evron, Ran Levinstein, Matan Schliserman, Uri Sherman, Tomer Koren, Daniel Soudry, and Nathan Srebro. From continual learning to sgd and back: Better rates for continual linear models. In Fourth Conference on Lifelong Learning Agents-Workshop Track, 2025. Guillaume Garrigos, Daniel Cortild, Lucas Ketels, and Juan Peypouquet. Last-iterate complexity of sgd for convex and smooth stochastic problems. arXiv preprint arXiv:2507.14122, 2025. Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016. Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International conference on machine learning, pages 5200– 5209. PMLR, 2019. Benjamin Grimmer, Kevin Shu, and Alex L Wang. Accelerated objective gap and gradient norm convergence for gradient descent via long steps. INFORMS Journal on Optimization, 7(2):156–169, 2025. Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579–1613. PMLR, 2019. Elad Hazan. Introduction to online convex optimization. Foundations and Trends® in Optimization, 2(3-4): 157–325, 2016. 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 Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pages 1752–1755. PMLR, 2019. Guy Kornowski and Ohad Shamir. Open problem: Anytime convergence rate of gradient descent. In The Thirty Seventh Annual Conference on Learning Theory, pages 5335–5339. PMLR, 2024. Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv:1212.2002, 2012. Zijian Liu and Zhengyuan Zhou. On the last-iterate convergence of shuffling gradient methods. arXiv preprint arXiv:2403.07723, 2024a. 8
Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024b. Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011. Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009. Arkadi Semenovich Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983. Ivan Niven. The asymptotic density of sequences. Bulletin of the American Mathematical Society, 57(6): 420–434, 1951. Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838–855, 1992. Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Conference on Machine Learning, pages 1571–1578, 2012. Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400–407, 1951. Ohad Shamir. Open problem: Is averaging needed for strongly convex stochastic gradient descent? In Conference on Learning Theory, pages 47–1. JMLR Workshop and Conference Proceedings, 2012. Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pages 71–79. PMLR, 2013. Adrien Taylor and Francis Bach. Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions. In Conference on Learning Theory, pages 2934–2992. PMLR, 2019. 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. Moslem Zamani and François Glineur. Exact convergence rate of the last iterate in subgradient methods. arXiv preprint arXiv:2307.11134, 2023. Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the twenty-first international conference on Machine learning, page 116, 2004. Zihan Zhang, Jason Lee, Simon Du, and Yuxin Chen. Anytime acceleration of gradient descent. In Proceedings of Thirty Eighth Conference on Learning Theory, pages 5991–6013. PMLR, 2025.
9
A
Additional Proofs
A.1
Proof of Lemma 6
For the first item, given η and t, let ϵ > 0 be some arbitrarily small number so that ϵ < min{1, ηt−1 , ϵ and denote cϵ = Pt−2 . Consider the univariate function over [−1, 1] : η j=0
Pt−2
j=0 ηj },
j
if x < 0 −x, f (x) = cϵ x, if 0 ≤ x ≤ ϵ . x − ϵ + cϵ ϵ, if x > ϵ Note that f is 1-Lipschitz, convex since cϵ < 1, and minimized at f (0) = 0. Consider the iterates of GD initialized at x0P= ϵ. It is easy to see that for i < t − 1 it holds that xi+1 = xi − ηi cϵ , and therefore xt−1 = ϵ − cϵ t−2 j=0 ηj = 0. If at time t − 1 the subgradient is given by −1 ∈ ∂f (xt−1 ), this leads to xt = ηt−1 . Noting that ηt−1 > ϵ, we get that Eη (t) ≥ f (xt ) = ηt−1 − ϵ + cϵ ϵ. Since this inequality holds for arbitrarily small ϵ, it must hold that Eη (t) ≥ lim (ηt−1 − ϵ + cϵ ϵ) = ηt−1 . ϵ→0+
We now turn to prove the second claim, which is based on the proof of [Kornowski and Shamir, 2024, Theorem 1]. Given η and t, consider the convex quadratic f (x) =
4
x2 Pt−1
j=0 ηj
.
P 1 Note that f is 1-Lipschitz over [−1, 1] as long as t−1 j=0 ηj ≥ 2 , and is minimized at f (0) = 0. Examining Q ηj the iterates of GD initialized at x0 = 1, a simple induction reveals that xt = t−1 j=0 (1− 2 Pt−1 η ). Therefore j=0
j
!2 ηj · 1 − Pt−1 Eη (t) ≥ f (xt ) = Pt−1 4 j=0 ηj j=0 2 j=0 ηj ! t−1 X η 1 j = Pt−1 · exp 2 · log 1 − Pt−1 4 j=0 ηj 2 j=0 ηj j=0 t−1 X ηj 1 ≥ Pt−1 · exp −4 · Pt−1 4 j=0 ηj 2 j=0 ηj j=0 t−1 Y
1
=
A.2
4
e−2 Pt−1
j=0 ηj
.
Proof of Lemma 7
To prove Lemma 7, we start by proving the following auxiliary result. Lemma 8. Let T ∈ N, and suppose (aj )Tj=0 , (bj )Tj=0 ≥ 0 are non-negative sequences satisfying the following conditions: 10
(i)
PT
1 2 j=0 aj ≤ 2 .
(ii) For all j it holds that bj ≤ min{ 12 , 2η √1T +1 }. j
PT
(iii) For all j it holds that aj k=j+1 ηk ≤ 12 ηj bj . P −1 Then Eη (T ) ≥ 12 Tj=0 aj bj ηj . P Proof of Lemma 8. For i ∈ {0, . . . , T } we define the vectors vi := ij=1 aj−1 ej − bi ei+1 ∈ RT +1 , and let f : RT +1 → R P be the function f (x) := maxi {vi⊤ x}. Note that each component x 7→ vi⊤ x is 1-Lipschitz −1 2 since ∥vi ∥2 ≤ Tj=0 aj + maxj b2j ≤ 1, and therefore f is 1-Lipschitz as the maximum of 1-Lipschitz functions. We consider GD applied to f , initialized at the origin and projected onto the unit ball B ⊂ RT +1 , where the given subgradient at a point x ∈ RT +1 corresponds to vi for the minimal index i such that f (x) = vi⊤ x. We will first prove by induction over t that for all t ∈ [T ] : xt =
t X
bj−1 ηj−1 − aj−1
η k=j k ej .
Pt−1
(7)
j=1
For the base case t = 1, note that all the vi ’s are in the subgradient set of x0 = 0, so the subgradient choice of the minimal index leads to x1 = ProjB (0 − η0 v0 ) = ProjB (η0 b0 e1 )
(η0 b0 ≤ 2√T1 +1 <1)
=
η0 b0 e1 ,
and therefore (7) holds for t = 1. Now assume (7) holds at time t. To obtain the claim for t + 1, we start by showing that the returned subgradient at xt is vt . To see that, we see that for any i ∈ {0, . . . , T − 1} : ⊤ i t X X P bj−1 ηj−1 − aj−1 t−1 ηk ej vi⊤ xt = aj−1 ej − bi ei+1 k=j
j=1
j=1
min{i,t}
=
X j=1
P Pt−1 aj−1 bj−1 ηj−1 − aj−1 t−1 η − 1 · b b η − a η i i i i {i+1≤t} k=j k k=i+1 k , | | {z } {z } (⋆)
(⋆⋆)
and note that (⋆), (⋆⋆) > 0 by assumption (iii), and therefore the minimal index that maximizes the expression above is clearly i = t. Hence, the given subgradient at xt is vt as claimed, which gives that xt+1 = ProjB (xt − ηt vt ) t t−1 t X X X = ProjB bj−1 ηj−1 − aj−1 ηk ej − ηt aj−1 ej + ηt bt et+1 j=1
k=j
j=1
t+1 X Pt = ProjB bj−1 ηj−1 − aj−1 k=j ηk ej j=1
=
t+1 X
bj−1 ηj−1 − aj−1 {z j=1 | (⋄j )
Pt
k=j ηk
ej }
11
(8)
where the last equality follows from noting that for each j, by assumption (iii) it holds that P bj−1 ηj−1 ≥ (⋄j ) ≥ bj−1 ηj−1 − aj−1 Tk=j ηk ≥ 21 bj−1 ηj−1 ≥ 0 , P PT +1 PT +1 1 2 2 hence t+1 j=1 (⋄j ) ≤ j=1 (bj−1 ηj−1 ) ≤ j=1 4(T +1) < 1 using assumption (ii). We see that (8) completes the induction step, proving (7). To complete the proof, we note that minx∈B f (x) ≤ f (0) = 0, and recall we saw that f (xT ) = vT⊤ xT , therefore Eη (T ) ≥ f (xT ) − min f (x) ≥ f (xT ) = vT⊤ xT x∈B ⊤ T T X X P −1 = aj−1 ej − bT eT +1 bj−1 ηj−1 − aj−1 Tk=j ηk ej j=1
=
T X
j=1
P −1 ηk aj−1 bj−1 ηj−1 − aj−1 Tk=j
j=1 T
T −1
j=1
j=0
1X 1X ≥(iii) aj−1 bj−1 ηj−1 = aj bj ηj . 2 2
We will also need the following bound on step sums. Pt2 √ √ Lemma 9. For any t1 < t2 ∈ N : j=t1 ηj ≤ 2ϕ(t2 + 1)( t2 − t1 ) Proof of Lemma 9. By Lemma 6.1, for any t1 < t2 ∈ N : t2 X
t2 X
1
1
tX 2 +1
ϕ(j) √ ≤ ϕ(t2 + 1) ηj ≤ Eη (j + 1) ≤ j j=t j=t j=t +1 1
Z t2 t1
√ √ 1 √ dx = 2ϕ(t2 + 1)( t2 − t1 ) . x
We turn back prove Lemma 7. Given t ∈ N and any j < t, let √ min{1, ηj t + 1} 1 1 √ aj := , bj := min{ , }. 16ϕ(t + 1)(t + 1 − j) 2 2ηj t + 1 We note that the conditions in Lemma 8 hold: (i) It holds that t X j=0
a2j ≤
t
t
j=0
j=1
X X 1 1 1 1 1 π2 1 = < · < . 2 2 256ϕ(t + 1) (t + 1 − j) 256ϕ(t + 1) j 256 6 2
(ii) For all j : 1 1 √ bj ≤ min{ , }. 2 2ηj t + 1 12
(iii) For all j : aj
t X
ηk
k=j+1
√ p √ min{1, ηj t + 1} ≤ · 2ϕ(t + 1)( t − j + 1) 16ϕ(t + 1)(t + 1 − j) √ √ √ ηj 1 ( t − j + 1) t + 1 min{ √ , } = t+1−j 8 t+1 8 √ √ ηj t+1− j+1 t+1 1 ≤ · min{ √ , } t+1−j 8 t+1 8 | {z }
Lemma 9
≤1
ηj 1 1 , } < ηj bj . ≤ min{ √ 2 8 t+1 8 Therefore, since the conditions of Lemma 8 hold, we can apply and get that t−1
Eη (t) ≥
1X aj bj ηj 2 j=0
√ ηj min{1, ηj t + 1} 1 · min{ √ , } = 16ϕ(t + 1)(t + 1 − j) 4 t+1 4 j=0 √ t−1 X min{1, ηj t + 1}2 1 √ = . (t + 1 − j) 64ϕ(t + 1) t + 1 t−1 X
j=0
13