Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Randhawa, Sikander
Master of Science - MSc
University of British Columbia
Consider the problem of minimizing functions that are Lipschitz and strongly convex, but not necessarily differentiable. We prove that after T steps of stochastic gradient descent (SGD), the error of the final iterate is O(log⁡T⁄T) with high probability. We also construct a function from this class for which the error of the final iterate of deterministic gradient descent is Ω(log⁡T⁄T). This shows that the upper bound is tight and that, in this setting, the last iterate of stochastic gradient descent has the same general error rate (with high probability) as deterministic gradient descent. This resolves both open questions posed by Shamir (2012). We prove analogous results for functions which are Lipschitz and convex, but not necessarily strongly convex or differentiable. After T steps of stochastic gradient descent, the error of the final iterate is O(log⁡T⁄√T) with high probability, and there exists a function for which the error of the final iterate of deterministic gradient descent is Ω(log⁡T⁄√T). In the strongly-convex setting, several forms of SGD, including suffix averaging, are known to achieve the optimal O(1⁄T) convergence rate in expectation. An intermediate step of our high probability analysis for the error of the final iterate proves that the suffix averaging method achieves error O(1⁄T) with high probability, which is optimal (for any first-order optimization method). This improves results of Rakhlin et al. (2012) and Hazan and Kale (2014), both of which achieved error O(1⁄T), but only in expectation, and achieved a high probability error bound of O(log⁡log⁡T ⁄T), which is suboptimal. This is the first known high-probability result which attains the optimal O(1⁄T) rate. We also consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. (2012) and prove that it too achieves the optimal O(1⁄T) convergence rate with high probability. This provides a second algorithm which achieves the optimal O(1⁄T) convergence rate with high-probability. Our high-probability results are proven using a generalization of Freedman's Inequality which we develop.
Understanding the role of averaging in non-smooth stochastic gradient descentbySikander RandhawaB. Sc, University of British Columbia, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)August 2020c© Sikander Randhawa, 2020The following individuals certify that they have read, and recommend to the Faculty of Graduate and Postdoc-toral Studies for acceptance, the thesis entitled:Understanding the role of averaging in non-smooth stochastic gradient descentsubmitted by Sikander Randhawa in partial fulfillment of the requirements for the degree of Master of Sciencein Computer Science.Examining Committee:Nicholas J. A. Harvey, Computer ScienceSupervisorBruce Shepherd, Computer ScienceSupervisory Committee MemberiiAbstractConsider the problem of minimizing functions that are Lipschitz and strongly convex, but not necessarily dif-ferentiable. We prove that after T steps of stochastic gradient descent (SGD), the error of the final iterate isO(log(T )/T ) with high probability. We also construct a function from this class for which the error of the finaliterate of deterministic gradient descent is Ω(log(T )/T ). This shows that the upper bound is tight and that, inthis setting, the last iterate of stochastic gradient descent has the same general error rate (with high probability)as deterministic gradient descent. This resolves both open questions posed by Shamir [42].We prove analogous results for functions which are Lipschitz and convex, but not necessarily strongly con-vex or differentiable. After T steps of stochastic gradient descent, the error of the final iterate is O(log(T )/√T )with high probability, and there exists a function for which the error of the final iterate of deterministic gradientdescent is Ω(log(T )/√T ).In the strongly-convex setting, several forms of SGD, including suffix averaging, are known to achieve theoptimal O(1/T ) convergence rate in expectation. An intermediate step of our high probability analysis for theerror of the final iterate proves that the suffix averaging method achieves error O(1/T ) with high probability,which is optimal (for any first-order optimization method). This improves results of Rakhlin et al. [36] andHazan and Kale [17], both of which achieved error O(1/T ), but only in expectation, and achieved a highprobability error bound of O(log log(T )/T ), which is suboptimal. This is the first known high-probability resultwhich attains the optimal O(1/T ) rate.We also consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. [26] and prove that it tooachieves the optimal O(1/T ) convergence rate with high probability. This provides a second algorithm whichachieves the optimal O(1/T ) convergence rate with high-probability. Our high-probability results are provenusing a generalization of Freedman’s Inequality which we develop.iiiLay SummaryMany machine learning tasks are represented as optimization problems where the objective is to produce aminimizer of some function. Often, what makes this task difficult is that it is very slow to compute the functionvalue at any point. Nonetheless, there are simple procedures which provide non-trivial theoretical guarantees onfinding an approximate minimizer. One such algorithm is gradient descent, which makes incremental progresstowards a minimizer by taking small steps in the “steepest downhill direction.” If the shape of the function doesnot change rapidly, gradient descent guarantees progress at every step. Otherwise, some steps can increase thefunction value; this is the setting we consider. We study the function value of different combinations of thepoints visited by gradient descent and compare them to the value of the minimizer. Understanding this is ofpractical significance because gradient descent is a fundamental algorithm for many machine learning tasks.ivPrefaceThe main body of work presented in this thesis was largely conducted in collaboration with Nicholas Harvey,Christopher Liaw, and Yaniv Plan and was accepted for publication [15] at the Conference of Learning Theory2019 [Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, Sikander Randhawa. Tight analyses of non-smoothstochastic gradient descent. In Conference on Learning Theory, 2019.]. The majority of the results and proofsfound in Chapter 2, Chapter 3, Chapter 4, Section 5.2 can be found in [15]. The proofs of these results weredeveloped as a result of collaborative effort and the writing was shared equally amongst authors. Some excep-tions include the proofs in Section 3.4 and Section 3.5 which are currently unpublished and were developed andwritten by me. The statements of results from Chapter 5 and Chapter 6 can be found in [15] without proof. Weprovide full proofs in this thesis. I wrote Section 5.1 in Chapter 5, derived and wrote the results in Section 6.3,and wrote Section 6.2. The writing responsibilities in other sections of these chapters were shared amongstcollaborators.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.1 Preliminaries on martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.1 High probability upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.2 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.3 High probability upper bound for suffix averaging . . . . . . . . . . . . . . . . . . . . . 81.4 Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Finite Dimensional Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.1 Lower bound on error of final iterate, strongly convex case . . . . . . . . . . . . . . . . . . . . 112.2 Lower bound on error of final iterate, Lipschitz case . . . . . . . . . . . . . . . . . . . . . . . . 132.3 Omitted proofs for the lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.1 Strongly convex case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.2 Lipschitz case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.3 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 High Probability Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1 Upper bound on error of final iterate, strongly convex case . . . . . . . . . . . . . . . . . . . . 203.1.1 Bounding the noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.1.2 High probability bounds on squared distances to x∗ . . . . . . . . . . . . . . . . . . . . 23vi3.1.3 Upper bound on error of suffix averaging . . . . . . . . . . . . . . . . . . . . . . . . . 243.2 Upper bound on error of final iterate, Lipschitz case: proof sketch . . . . . . . . . . . . . . . . 243.2.1 Bounding the noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.3 Omitted proofs from Section 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.3.1 Standard analysis of SGD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.3.2 Proof of Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.3.3 Proof of Lemma 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3.4 Proof of Lemma 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.3.5 Proof of Claim 3.18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.3.6 Proof of Claim 3.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.4 Alternative proof of Theorem 1.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4.1 Proof of Lemma 3.22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.4.2 Proof of Lemma 3.23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.5 High probability bound on a non-uniform averaging scheme . . . . . . . . . . . . . . . . . . . 373.5.1 Main idea of proof of Theorem 3.25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.5.2 High probability upper bound analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.5.3 Proof of Claim 3.26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.5.4 Bounding ZT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.5.5 Missing proofs from Subsection 3.5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 Probabilistic Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.1 Proof of Theorem 1.11 and corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.1.1 Corollaries of Theorem 1.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.2 Proof of Theorem 1.19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 Infinite Dimensional and Probabilistic Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . 515.1 Functions attaining large error infinitely often . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.1.1 Proof of Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.1.2 Proof of Lemma 5.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.1.3 Proof of Claim 5.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.2 Necessity of log(1/δ ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626 Extensions and Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.1 Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.1.1 Scaling assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.1.2 Subgaussian noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676.2 Subgaussian and subexponential random variables . . . . . . . . . . . . . . . . . . . . . . . . . 676.2.1 Subgaussian random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676.2.2 Subexponential random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696.2.3 Relationship between subgaussian and subexponential random variables . . . . . . . . . 706.3 Upper bound on error of final iterate: subgaussian noise . . . . . . . . . . . . . . . . . . . . . . 71vii6.3.1 Upper bound on error of final iterate, strongly convex case with subgaussian noise . . . 716.3.2 High probability bounds on squared distances to x∗ . . . . . . . . . . . . . . . . . . . . 756.3.3 Suffix averaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766.3.4 Proof of Theorem 6.35 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776.3.5 Using Theorem 1.11 with conditionally subgaussian increments . . . . . . . . . . . . . 797 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 817.1 Open questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82A Standard Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85A.1 Useful scalar inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86viiiAcknowledgmentsFirst and foremost I would like to express a deep sense of gratitude to my supervisor, Nick Harvey. I amextremely grateful and consider myself lucky to have been able to learn from him. I would not be in the positionI am in now without the patience, guidance, and optimism of Nick. I would also like to thank Hu Fu and BruceShepherd for being wonderful mentors to me.To my Mom, Dad, Brother, Grandmother and my Uncle Sam: without your consistent love, support, sacrificeand encouragement there is not much that I would be able to accomplish. Thank you for raising me and givingme everything when you had nothing. To my closest friends, Angad Kalra and Harish Anand, thank you foralways inspiring me to grow as a human and for the countless laughs and good times which we have shared.ixDedicationThis thesis is dedicated to my Mom, Dad, and Brother.xChapter 1Introduction1.1 IntroductionStochastic gradient descent (SGD) is one of the oldest randomized algorithms, dating back to 1951 [37]. It isa very simple and widely used iterative method for minimizing a function. In a nutshell, the method works byquerying an oracle for a noisy estimate of a subgradient, then taking a small step in the opposite direction. Thesimplicity and effectiveness of this algorithm has established it both as an essential tool for applied machinelearning [21, 40], and as a versatile framework for theoretical algorithm design.In theoretical algorithms, SGD often appears in the guise of coordinate descent, an important special casein which each gradient estimate has a single non-zero coordinate. Some of the fast algorithms for Laplacianlinear systems [23, 28] are based on coordinate descent (and the related Kaczmarz method [44]). Multi-armedBandits were discovered years ago to be a perfect setting for coordinate descent [2]: the famous Exp3 algorithmcombines coordinate descent and the multiplicative weight method. Recent work on the geometric medianproblem [9] gave a sublinear time algorithm based on SGD, and very recently a new privacy amplificationtechnique [12] has been developed that injects noise to the subgradients while executing SGD. Surveys andmonographs discussing gradient descent and aimed at a theoretical CS audience include Bansal and Gupta [4],Bubeck [7], Hazan [16], and Vishnoi [46].The efficiency of SGD is usually measured by the rate of decrease of the error — the difference in value be-tween the algorithm’s output and the true minimum. The optimal error rate is known under various assumptionson f , the function to be minimized. In addition to convexity, common assumptions are that f is smooth (gradientis Lipschitz) or strongly convex (locally lower-bounded by a quadratic). Strongly convex functions often arisedue to regularization, whereas smooth functions can sometimes be obtained by smoothening approximations(e.g., convolution). Existing analyses [32] show that, after T steps of SGD, the expected error of the final it-erate is O(1/√T ) for smooth functions, and O(1/T ) for functions that are both smooth and strongly convex;furthermore, both of these error rates are optimal without further assumptions.The non-smooth setting is the focus of this thesis. In theoretical algorithms and discrete optimization, theconvex functions that arise are often non-smooth. For example, the objective for the geometric median problemis a (sum of) 2-norms [9], so Lipschitz but not smooth. Similarly, formulating the minimum s-t cut problemas convex minimization [29], the objective is a 1-norm, so Lipschitz but not smooth. In machine learning, the1objective for regularized support vector machines [41] is strongly convex but not smooth.A trouble with the non-smooth setting is that the error of (even deterministic) gradient descent need notdecrease monotonically with T , so it is not obvious how to analyze the error of the final iterate. A workaround,known as early as [33], is to output the average of the iterates. Existing analyses of SGD show that the expectederror of the average is Θ(1/√T ) for Lipschitz functions [33], which is optimal, whereas for functions that arealso strongly convex [18, 36] the average has error Θ(log(T )/T ) with high probability, which is not the optimalrate. An alternative algorithm, more complicated than SGD, was discovered by Hazan and Kale [17]; it achievesthe optimal expected error rate of O(1/T ). Suffix averaging, a simpler approach in which the last half of theSGD iterates are averaged, was also shown to achieve expected error O(1/T ) [36], although implementationscan be tricky or memory intensive if the number of iterations T is unknown a priori. Non-uniform averagingschemes with optimal expected error rate and simple implementations are also known [27, 43], although thesolutions may be less interpretable.Shamir [42] asked the very natural question of whether the final iterate of SGD achieves the optimal rate inthe non-smooth scenario, as it does in the smooth scenario. If true, this would yield a very simple, implementableand interpretable form of SGD. Substantial progress on this question was made by Shamir and Zhang [43], whoshowed that the final iterate has expected error O(log(T )/√T ) for Lipschitz f , and O(log(T )/T ) for stronglyconvex f . Both of these bounds are a log(T ) factor worse than the optimal rate, so Shamir and Zhang [43] writeAn important open question is whether the O(log(T )/T ) [expected] rate we obtained on [the lastiterate], for strongly-convex problems, is tight. This question is important, because running SGDfor T iterations, and returning the last iterate, is a very common heuristic. In fact, even for thesimpler case of (non-stochastic) gradient descent, we do not know whether the behavior of the lastiterate... is tight.Our work shows that the log(T ) factor is necessary, both for Lipschitz functions and for strongly convex func-tions, even for non-stochastic gradient descent. So both of the expected upper bounds due to Shamir and Zhangare actually tight. This resolves the first question of Shamir [42]. In fact, we show a much stronger statement:any convex combination of the last k iterates must incur a log(T/k) factor. Thus, suffix averaging must averagea constant fraction of the iterates to achieve the optimal rate.Recently, Jain et al. [20] consider the setting where the time horizon, T , is fixed ahead of time. They showthat in both the strongly-convex case and the Lipschitz case, a suitable choice of step size gives the final iteratethe optimal convergence rates of O(1/T ) and O(1/√T ), respectively in expectation and with high probability.On the other hand, for the strongly-convex and stochastic case, when T is unknown, they show that no choiceof step size gives the individual iterates of SGD the O(1/T ) rate for every T .High probability bounds on SGD are somewhat scarce; most of the literature proves bounds in expectation,which is of course easier. A common misconception is that picking the best of several independent trials ofSGD would yield high-probability bounds, but this approach is not as efficient as it might seem1. So it is bothinteresting and useful that high-probability bounds hold for a single execution of SGD. Some known high-probability bounds for the strongly convex setting include [22], for uniform averaging, and [17, 36], which give1 It is usually the case that selecting the best of many independent trials is very inefficient. Such a scenario, which is very common inuses of SGD, arises if f is defined as ∑mi=1 fi or Eω [ fω ]. In such scenarios, evaluating f exactly could be inefficient, and even estimatingit to within error 1/T requires Θ(T 2) samples via a Hoeffding bound, whereas SGD uses only O(T ) samples.2a suboptimal bound of O(log log(T )/T ) for suffix averaging (and a variant thereof). In this work, we give twohigh probability bounds on the error of SGD for strongly convex functions: O(1/T ) for suffix averaging andO(log(T )/T ) for the final iterate. Both of these are tight. (Interestingly, the former is used as an ingredient forthe latter.) The former answers a question of Rakhlin et al. [36, §6], and the latter resolves the second questionof Shamir [42]. For Lipschitz functions, we prove a high probability bound of O(log(T )/√T ) for the finaliterate, which is also tight.Our work can also be seen as extending a line of work on understanding the difference between an averageof the iterates or the last iterate of an iterative process. For instance, an important result in game theory is that themultiplicative weights update algorithm converges to an equilibrium [14], i.e. the set of players are required toplay some sort of “coordinated average” of their past strategies. Recently, [3] studied the convergence behaviourof players’ individual strategies and found that the strategies diverge and hence, coordination (i.e. averaging) isneeded to obtain an equilibrium. In a similar spirit, our work shows that the iterates of gradient descent havea sub-optimal convergence rate, at least for non-smooth convex functions, and thus, some form of averagingis needed to achieve the optimal rate. It is an interesting direction to see whether or not this is necessary inother iterative methods as well. For instance, the multiplicative weights update algorithm can be used to give aniterative algorithm for maximum flow [8], or linear programming in general [1, 34], but also requires some formof averaging. We hope that this thesis contributes to a better understanding on when averaging is necessary initerative processes.1.2 PreliminariesLetX be a closed, convex subset of Rn, f : X →R be a convex function, and ∂ f (x) the subdifferential of f atx. Our goal is to solve the convex program minx∈X f (x). (Our later assumptions will imply that minx∈X f (x) isrealized by some point x∗). We assume that f is not explicitly represented. Instead, the algorithm is allowed toquery f via a stochastic gradient oracle, i.e., if the oracle is queried at x then it returns gˆ= g− zˆ where g∈ ∂ f (x)and E [ zˆ ] = 0 conditioned on all past calls to the oracle. The setX is represented by a projection oracle, whichreturns the point inX closest in Euclidean norm to a given point x. We say that f is α-strongly convex iff (y) ≥ f (x)+ 〈g, y− x 〉+ α2‖y− x‖2 ∀y,x ∈X ,g ∈ ∂ f (x). (1.1)Throughout this thesis, ‖·‖ denotes the Euclidean norm in Rn and [T ] denotes the set {1, . . . ,T}.We say that f is L-Lipschitz if ‖g‖ ≤ L for all x ∈X and g ∈ ∂ f (x). For the remainder of this thesis, unlessotherwise stated, we make the assumption that α = 1 and L = 1; this is only a normalization assumption and iswithout loss of generality (see Section 6.1). For the sake of simplicity, we also assume that ‖zˆ‖ ≤ 1 a.s. althoughour arguments generalize to the setting when zˆ are subgaussian (see Section 6.1).Let ΠX denote the projection operator on X , which is defined by ΠX (y) = argminx∈X ‖x− y‖. The(projected) stochastic gradient algorithm is given in Algorithm 1. Notice that the algorithm maintains a sequenceof points and there are several strategies to output a single point. The simplest strategy is to simply output xT+1.However, one can also consider averaging all the iterates [35, 39] or averaging only a fraction of the final iterates[36]. Notice that the algorithm also requires the user to specify a sequence of step sizes. The optimal choice ofstep size is known to be ηt = Θ(1/t) for strongly convex functions [32, 36], and ηt = Θ(1/√t) for Lipschitz3functions. For our analyses, we will use a step size of ηt = 1/t for strongly convex functions and ηt = 1/√t forLipschitz functions.Algorithm 1 Projected stochastic gradient descent for minimizing a non-smooth, convex function.1: procedure STOCHASTICGRADIENTDESCENT(X ⊆ Rn, x1 ∈X , step sizes η1,η2, . . .)2: for t← 1, . . . ,T do3: Query stochastic gradient oracle at xt for gˆt such that E [ gˆt | gˆ1, . . . , gˆt−1 ] ∈ ∂ f (xt)4: yt+1← xt −ηt gˆt (take a step in the opposite direction of the subgradient)5: xt+1←ΠX (yt+1) (project yt+1 onto the setX )6: return eitherxT+1 (final iterate)1T+1 ∑T+1t=1 xt (uniform averaging)1T/2+1 ∑T+1t=T/2+1 xt (suffix averaging)1.2.1 Preliminaries on martingalesLet {di,Fi}ni=1 be such that di areFi measurable random variables where {Fi}ni=1 forms a filtration of a sigmafield F , E [ |di| ] < ∞ and E [di | Fi ] = 0. We call {di,Fi}ni=1 a martingale difference sequence. The partialsums of a martingale difference sequence form a martingale.In order to control the tail distribution of a martingale, one needs to make some assumptions on the behaviorof the increments, di. A common assumption which is used in the classical Hoeffding’s inequality is that |di| ≤ cialmost surely where ci ∈ R. Then, Hoeffding’s inequality yieldsPr[n∑i=1di ≥ x]≤ exp(− x22∑ni=1 c2i), ∀x> 0.Therefore, Hoeffding’s inequality is useful if one can derive an almost sure bound on the sum of squaredmagnitudes by a scalar, ∑ni=1 c2i . A weaker assumption which allows Hoeffding’s inequality to be applicablefor a much broader class of martingales is that the increments are conditionally subgaussian2. In this setting,one can use Hoeffding’s inequality when the sum of squared subgaussian norms is almost surely bounded by ascalar.The classical Freedman’s inequality is a martingale concentration inequality which has the advantage thatone need not require an almost sure bound on the sum of squared magnitudes. Freedman’s inequality canroughly be stated as follows:Pr[n∑i=1di ≥ x and Bn ≤ y]≤ exp(− Cx2x+ y)∀x,β > 0,where Bt is some process derived from ∑ti=1 di. Notice that a high probability bound of y on Bn yields a highprobability bound of√y on ∑ni=1 di, whereas Hoeffdings inequality requires an almost sure bound of ∑ni=1 c2i onthe sum of squared magnitudes in order to achieve a high probability bound of√∑ni=1 c2i on ∑ni=1 di. Bt can bedefined in many ways and there are various forms of Freedman’s inequality which use different selections of Bt .2A random variable is subgaussian if its tail distribution resembles the gaussian tail distribution. For a more detailed description seeSection 6.2.4Some of these processes, together with an accompanying version of Freedman’s inequality using that processfollow below:Definition 1.1. Let {di,Fi}ni=1 be a martingale difference sequence. Let vari−1 = E[d2i | Fi−1]. Let Vart =∑ti=1 vari−1. The predictable process (Vart)nt=1 is called the sum of conditional variances (SCV).Theorem 1.2 ([13, Theorem 1.6]). Let {di,Fi}ni=1 be a martingale difference sequence. Assume that |di| ≤ cfor every i almost surely. Then, for every x,y> 0Pr[n⋃i=1{t∑i=1di ≥ x and Vart ≤ y}]≤ exp(− c2x22(cx+ y)).Remark 1.3. de la Peña [10] later proved a similar result which relaxes the almost sure bound on the incrementsand instead assumes a Bernstein style conditional bound on the moments of di. Theorem 1.2 yields a highprobability bound of√y on ∑ni=1 di if one can prove a high probability bound of y on the SCV process.Definition 1.4. Let {di,Fi}ni=1 be a martingale difference sequence. Let vi−1 beFi−1 measureable and minimalsuch that for all λ > 0 we have E [exp(λdi) | Fi−1 ] ≤ exp(λ 22 vi−1). Let Vt = ∑ti=1 vi−1. The predictableprocess (Vt)nt=1 is called the sum of squared conditional subgaussian norms (SSCSN).Theorem 1.5 ([11, Theorem 2.6]). Let {di,Fi}ni=1 be a martingale difference sequence. Assume, for 1≤ i≤ n,there exist Fi−1 measureable random variables vi−1 such that for all λ > 0 we have E [exp(λdi) | Fi−1 ] ≤exp(λ 22 vi−1). Then, for every x,y> 0Pr[n⋃i=1{t∑i=1di ≥ x and Vt ≤ y}]≤ exp(− x22y).Remark 1.6. Notice that Theorem 1.5 does not require an almost sure bound on the increments di. Instead, itassumes subgaussian increments. Theorem 1.5 yields a high probability bound of√y if one can prove a highprobability bound of y on the SSCSN process.It may be challenging to obtain an a high probability bound on the SCV or SSCSN processes. Instead, itis sometimes useful to consider the following process. Indeed, by Lemma 1.8 the sum of squared magnitudes(SSCM) process bounds both the SCV process and the SSCSN process. For a statement of a concentrationinequality similar to Freedman’s inequality which uses a process similar to the SSCM process, see [31, Theo-rem 3.14].Definition 1.7. Let {di,Fi}ni=1 be a martingale difference sequence. Suppose that |di| ≤ mi−1 where mi−1 isFi−1 measureable. Let Mt = ∑ti=1 m2i−1. The predictable process (Mt)nt=1 is called the sum of squared condi-tional magntitudes (SSCM).Lemma 1.8. Suppose |di| ≤ mi−1 where mi−1 is Fi−1 measurable. Then, vari−1 ≤ mi−1 and vi−1 ≤ m2i−1.Consequently, Vart ≤Mt and Vt ≤Mt for all t ∈ [n].Proof (of Lemma 1.8). The first part of the claim follows because E [vari−1 | Fi−1 ] = E[d2i | Fi−1]≤ m2i−1,since |di| ≤mi−1 which isFi−1 measurable. The second part of the claim follows because E [exp(λdi) | Fi−1 ]≤exp(λ 22 m2i−1)by Hoeffding’s Lemma (Lemma A.5). 5In this thesis we derive a generalization of Freedman’s inequality (as formulated in Theorem 1.5). WhileTheorem 1.5 is useful in the setting where one can obtain a high probability bound on the SSCSN processby a scalar, our Theorem 1.11 can be used with a high probability upper bound on the SSCSN by a randomquantity with a particular structure. This random quantity contains a scaled and translated version of the originalmartingale – and we will refer to this entanglement between the SSCSN process and the original martingale asthe chicken and egg phenomenon. Theorem 1.11 is used to derive a high probability bound on the error of thefinal iterate of Algorithm 1. While Theorem 1.11 requires one to control the SSCSN process, our application ofTheorem 1.11 begins by bounding the SSCM process. Lemma 1.8 implies that this is sufficient.1.3 Our contributionsOur main results are bounds on the error of the final iterate of stochastic gradient descent for non-smooth,convex functions.Strongly convex and Lipschitz functions. We prove anΩ(log(T )/T ) lower bound, even in the non-stochasticcase, and an O(log(T ) log(1/δ )/T ) upper bound with probability 1−δ .Lipschitz functions. We prove an Ω(log(T )/√T ) lower bound, even in the non-stochastic case, and anO(log(T ) log(1/δ )/√T ) upper bound with probability 1−δ .1.3.1 High probability upper boundsTheorem 1.9. Suppose f is 1-strongly convex and 1-Lipschitz. Suppose that zˆt (i.e., E [ gˆt ]− gˆt , the noise of thestochastic gradient oracle) has norm at most 1 almost surely. Consider running Algorithm 1 for T iterationswith step size ηt = 1/t. Let x∗ = argminx∈X f (x) and δ ∈ (0,1) be arbitrary. Then, with probability at least1−δ ,f (xT+1)− f (x∗) ≤ O(log(T ) log(1/δ )T).Theorem 1.10. Suppose f is 1-Lipschitz and X has diameter 1. Suppose that zˆt (i.e., E [ gˆt ]− gˆt , the noise ofthe stochastic gradient oracle) has norm at most 1 almost surely. Consider running Algorithm 1 for T iterationswith step size ηt = 1/√t. Let x∗ = argminx∈X f (x) and δ ∈ (0,1) be arbitrary. Then, with probability at least1−δ ,f (xT+1)− f (x∗) ≤ O(log(T ) log(1/δ )√T).The assumptions on the strong convexity parameter, Lipschitz parameter, and diameter are without loss ofgenerality; see Section 6.1. The bounded noise assumption for the stochastic gradient oracle is made only forsimplicity; our analysis can be made to go through if one relaxes the a.s. bounded condition to a subgaussiancondition; see Section 6.3. We also remark that a linear dependence on log(1/δ ) is necessary for stronglyconvex functions; see Section 5.2.Our main probabilistic tool to prove Theorem 1.9 and Theorem 1.10 is a new extension of the classicFreedman inequality [13] to a setting in which the martingale exhibits a curious phenomenon. Ordinarily amartingale is roughly bounded by the square root of the sum of squared magnitudes (SSCM) (this is the contentof Freedman’s inequality). We consider a setting in which the SSCM is itself bounded by (a linear transformationof) the martingale. We refer to this as a “chicken and egg” phenomenon.6Theorem 1.11 (Generalized Freedman). Let {di,Fi}ni=1 be a martingale difference sequence. Suppose vi−1, fori ∈ [n], are positive andFi−1-measurable random variables such that E [exp(λdi) | Fi−1 ]≤ exp(λ 22 vi−1)forall i ∈ [n], λ > 0. Let St = ∑ti=1 di and Vt = ∑ti=1 vi−1. Let αi ≥ 0 and set α = maxi∈[n]αi. ThenPr n⋃t=1St ≥ x and Vt ≤ t∑i=1αidi +β ≤ exp(− x4α +8β/x)∀x,β > 0.The proof of Theorem 1.11 appears in Section 4.1. Freedman’s Inequality [13] (as formulated in The-orem 1.5, up to constants) simply omits the terms highlighted in yellow, i.e., it sets α = 0. Observe thatTheorem 1.11 assumes subgaussian increments as in [11] (as opposed to [10, 13] which assumes bounded in-crements).1.3.2 Lower boundsTheorem 1.12. For any T and any constant c > 0, there exists a convex function fT : X → R, where Xis the unit Euclidean ball in RT , such that fT is (3/c)-Lipschitz and (1/c)-strongly convex, and satisfies thefollowing. Suppose that Algorithm 1 is executed from the initial point x1 = 0 with step sizes ηt = c/t. Letx∗ = argminx∈X fT (x). ThenfT (xT )− fT (x∗) ≥ logT4c ·T (1.2)More generally, any weighted average x¯ of the last k iterates hasfT (x¯)− fT (x∗) ≥ ln(T )− ln(k)4c ·T . (1.3)Thus, suffix averaging must average a constant fraction of iterates to achieve the optimal O(1/T ) error.Remark 1.13. Let L= (3/c) and α = (1/c). Then, the lower bound from Eq. (1.2) can be re-written as L236αlogTT .This is within a constant factor of the guaranteed upper bound of 17L2α1+logTT by Shamir and Zhang [43].Theorem 1.14. For any T and any constant c> 0, there exists a convex function fT :X → R, whereX is theunit Euclidean ball in RT , such that fT is (1/c)-Lipschitz, and satisfies the following. Suppose that Algorithm 1is executed from the initial point x1 = 0 with step sizes ηt = c/√t with c> 0. Let x∗ = argminx∈X fT (x). ThenfT (xT )− fT (x∗) ≥ logT32c√T. (1.4)More generally, any weighted average x¯ of the last k iterates hasfT (x¯)− fT (x∗) ≥ ln(T )− ln(k)32c√T. (1.5)Furthermore, the value of f strictly monotonically increases for the first T iterations:f (xi+1) ≥ f (xi)+ 164c√T (T − i+1) ∀i ∈ [T ]. (1.6)Remark 1.15. Let L = (1/c) and R = 1. Then, the lower bound from Eq. (1.4) can be written as (R/c+7cL2) logT64√T. This is within a constant factor of the guaranteed upper bound of (R/c+ cL2)2+logT√Tby Shamir andZhang [43].Remark 1.16. In order to incur a logT factor in the error of the T iterate, Theorem 1.12 and Theorem 1.14constructs a function fT parameterized by T . It is also possible to create a single function f , independentof T , which incurs an additional factor very slightly below logT for infinitely many T . This is described inTheorem 5.1 and Theorem 5.2.1.3.3 High probability upper bound for suffix averagingInterestingly, our proof of Theorem 1.9 requires understanding the suffix average. (In fact this connection isimplicit in [43]). Hence, en route, we prove the following high probability bound on the error of the average ofthe last half of the iterates of SGD.Theorem 1.17. Suppose f is 1-strongly convex and 1-Lipschitz. Consider running Algorithm 1 for T iterationswith step size ηt = 1/t and assume T is even. Let x∗ = argminx∈X f (x) and δ ∈ (0,1) be arbitrary. Then, withprobability at least 1−δ ,f(1T/2+1T∑t=T/2xt)− f (x∗) ≤ O(log(1/δ )T).Remark 1.18. This upper bound is optimal. Indeed, Section 5.2 shows that the error is Ω(log(1/δ )/T ) evenfor the one-dimensional function f (x) = x2/2.Theorem 1.17 is an improvement over the O(log(log(T )/δ )/T)bounds independently proven by Rakhlinet al. [36] (for suffix averaging) and Hazan and Kale [17] (for EpochGD). Once again, we defer the statementof the theorem for general strongly-convex and Lipschitz parameters to Section 6.1.1.4 TechniquesFinal iterate. When analyzing gradient descent, it simplifies matters greatly to consider the expected error.This is because the effect of a gradient step is usually bounded by the subgradient inequality; so by linearity ofexpectation, one can plug in the expected subgradient, thus eliminating the noise [7, §6.1].High probability bounds are more difficult. (Indeed, it is not a priori obvious that the error of the final iterateis tightly concentrated.) A high probability analysis must somehow control the total noise that accumulates fromeach noisy subgradient step. Fortunately, the accumulated noise forms a zero-mean martingale but unfortunately,the martingale depends on previous iterates in a highly nontrivial manner. Indeed, suppose (Xt) is the martingaleof the accumulated noise and let vart−1 = E[(Xt −Xt−1)2 | X1, . . . ,Xt−1]be the conditional variance at time tand let Vart =∑ti=1 vari−1 be the sum of conditional variances (SCV). Freedman’s inequality roughly states thatXT .√VarT . A significant technical step of our analysis (Lemma 3.4) shows that the sum of squared conditionalmagnitudes (SSCM), (Mt)t≤T of the accumulated noise exhibits the “chicken and egg” phenomenon alluded toin the discussion of Theorem 1.11. Roughly speaking, we have MT ≤ αXT−1+β (where α,β > 0 are scalars),which implies a bound on VarT since Lemma 1.8 states that VarT ≤ MT . Therefore, an inductive argumentusing Freedman’s inequality shows that XT .√αXT−1+β .√α√αXT−2+β +β . · · · . This naive analysisinvokes Freedman’s inequality T times, so a union bound incurs an extra factor logT in the bound on XT . This8can be improved via a trick [6]: by upper-bounding the SSCM by a power-of-two (and by T ), it suffices toinvoke Freedman’s inequality logT times, which only incurs an extra factor log logT in the bound on XT .Notice that this analysis actually shows that Xt .√Mt for all t ≤ T , whereas the original goal was onlyto control XT . Any analysis that simultaneously controls all Xt , t ≤ T , must necessarily incur an extra factorlog logT . This is a consequence of the Law of the Iterated Logarithm3. Previous work employs exactly such ananalysis [17, 22, 36] and incurs the loglogT factor. Rakhlin et al. [36] explicitly raise the question of whetherthis log logT factor is necessary.Our work circumvents this issue by developing a generalization of Freedman’s Inequality (Theorem 1.11)to handle martingales of the above form, which ultimately yields optimal high-probability bounds. We are nolonger hindered by the Law of the Iterated Logarithm because our variant of Freedman’s Inequality does notrequire us to have fine grained control over the martingale over all times.Another important tool that we employ is a new bound on the Euclidean distance between the iteratescomputed by SGD (Lemma 3.3). This is useful because, by the subgradient inequality, the change in the errorat different iterations can be bounded using the distance between iterates. Various naive approaches yield abound of the form ‖xa− xb‖2 ≤ (b−a)2min{a2,b2} (in the strongly convex case). We derive a much stronger bound,comparable to ‖xa− xb‖2 ≤ |b−a|min{a2,b2} . Naturally, in the stochastic case, there are additional noise terms thatcontribute to the technical challenge of our analysis. Nevertheless, this new distance bound could be useful infurther understanding non-smooth gradient descent (even in the non-stochastic setting).As in previous work on the strongly convex case [43], the error of the suffix average plays a critical role inbounding the error of the final iterate. Therefore, we also need a tight high probability bound on the error of thesuffix average.Suffix averaging. To complete the optimal high probability analysis on the final iterate, we need a high proba-bility bound on the suffix average that avoids the loglogT factor. As in the final iterate setting, the accumulatednoise for the suffix average forms a zero-mean martingale, (Xt)TT/2, but now the squared conditional magnitudeat step t satisfies mt ≤ αtmt−1 +βtwˆt√mt−1 + γt , where wˆt is a conditionally mean-zero random variable andαt ,βt and γt are constants. In [36], using Freedman’s Inequality combined with the trick from [6], they obtain abound on a similar martingale but do so over all time steps and incur a loglogT factor. However, our goal is onlyto bound XT and according to Freedman’s Inequality XT .√MT , where MT is the sum of squared conditionalmagnitudes at time T . So, our goal becomes to bound MT . To do so, we develop a probabilistic tool to boundthe t iterate of a stochastic process that satisfies a recursive dependence on the (t−1) iterate similar to the oneexhibited by Mt .Theorem 1.19. Let (Xt)Tt=1 be a stochastic process and let (Ft)Tt=1 be a filtration such that Xt isFt measurableand Xt is non-negative almost surely. Let αt ∈ [0,1) and βt ,γt ≥ 0 for every t. Assume that E [exp(λX1) ] ≤exp(λK) for λ ∈ (0,1/K] where K = max1≤t≤T(2γt1−αt ,2β 2t1−αt). Let wˆt be a mean-zero random variable condi-tioned onFt such that |wˆt | ≤ 1 almost surely for every t. Suppose that Xt+1 ≤ αtXt +βtwˆt√Xt + γt for every t.Then, the following hold.• For every t, Pr [Xt ≥ K log(1/δ ) ]≤ eδ .3Let Xt ∈ {−1,+1} be uniform and i.i.d. and ST = ∑Tt=1 Xt . The Law of the Iterated Logarithm states that limsupT ST√2T log logT = 1a.s.9• More generally, if σ1, . . . ,σT ≥ 0, then Pr[∑Tt=1σtXt ≥ K log(1/δ )∑Tt=1σt]≤ eδ .The recursion Xt+1 ≤ αt +βtwˆt√Xt +γt presents two challenges that make it difficult to analyze. Firstly, thefact that it is a non-linear recurrence makes it unclear how one should unwind Xt+1. Furthermore, unravelingthe recurrence introduces many wˆt terms in a non-trivial way. Interestingly, if we instead consider the momentgenerating function (MGF) of Xt+1, then we can derive an analogous recursive MGF relationship which re-moves this non-linear dependence and removes the wˆt term. This greatly simplifies the recursion and leads to asurprisingly clean analysis. The proof of Theorem 1.19 can be found in Section 4.2. (The recursive MGF boundwhich removes the non-linear dependence is by Claim 4.6.)Deterministic lower bound. As mentioned above, a challenge with non-smooth gradient is that the error ofthe T iterate may not monotonically decrease with T , even in the deterministic setting. The full extent of thisnon-decreasing behavior seems not to have been previously understood. We develop a technique that forces theerror to be monotonically increasing for Ω(T ) consecutive iterations. The idea is as follows. If GD takes a stepin a certain direction, a non-differentiable point can allow the function to suddenly increase in that direction. Ifthe function were one-dimensional, the next iteration of GD would then be guaranteed to step in the oppositedirection, thereby decreasing the function. However, in higher dimensions, the second gradient step could benearly orthogonal to the first step, and the function could have yet another non-differentiable point in this seconddirection. In sufficiently high dimensions, this behavior can be repeated for many iterations. The tricky aspectis designing the function to have this behavior while also being convex. We show that this is possible, leadingto the unexpectedly large error in the T iteration. We believe that this example illuminates some non-obviousbehavior of gradient descent.10Chapter 2Finite Dimensional Lower Bounds2.1 Lower bound on error of final iterate, strongly convex caseIn this section we prove that the final iterate of SGD for strongly convex functions has error that is suboptimal bya factor Ω(logT ), even in the non-stochastic case. We give the proof of Theorem 1.12 in the case where c = 1.Theorem 1.12 can be obtained in full generality from the analysis in this section by applying the followingreduction, which is easily verifiable via induction.Lemma 2.1. Suppose that executing Algorithm 1 over the feasible region X ⊂ Rn, on the convex functionf : Rn 7→ R, using initial point x1, step-sizes ηt , and map σ such that σ(x) ∈ ∂ f (x) as a subgradient oracle,yields the iterates x1,x2, . . .. Then, executing Algorithm 1 over X on the function (1/c) · f , using initial pointx1, step-sizes c ·ηt , and subgradient oracle (1/c)σ also yields the iterates x1,x2, . . . .When c = 1, we define a function f = fT , depending on T , for which the final iterate produced by Algo-rithm 1 has f (xT ) = Ω(log(T )/T ) and minx∈X f (x) ≤ 0, thereby proving (1.2). Let X be the Euclidean unitball in RT . Define f :X → R and hi ∈ RT for i ∈ [T +1] byf (x) = maxi∈[T+1]Hi(x) where Hi(x) = hTi x+12‖x‖2hi, j =a j (if 1≤ j < i)−1 (if i = j ≤ T )0 (if i< j ≤ T )and a j =12(T +1− j) (for j ∈ [T ]).It is easy to see that f is 1-strongly convex due to the 12 ‖x‖2 term. Furthermore f is 3-Lipschitz over Xbecause ‖∇Hi(x)‖ ≤ ‖hi‖+ 1 and ‖hi‖2 ≤ 1+ 14 ∑Tj=1 1(T+1− j)2 < 1+ 12 . Finally, the minimum value of f overX is non-positive because f (0) = 0.Subgradient oracle. In order to execute Algorithm 1 on f we must specify a subgradient oracle. First, werequire the following claim, which follows from standard facts in convex analysis [19, Theorem 4.4.2].Claim 2.2. ∂ f (x) is the convex hull of { hi+ x : i ∈I (x) }, where I (x) = { i : Hi(x) = f (x) }.Our subgradient oracle is non-stochastic: given x, it simply returns hi′+ x where i′ = minI (x).11Explicit description of iterates. Next we will explicitly describe the iterates produced by executing Algo-rithm 1 on f . Define the points zt ∈ RT for t ∈ [T +1] by z1 = 0 andzt, j =1− (t− j−1)a jt−1 (if 1≤ j < t)0 (if t ≤ j ≤ T ).(for t > 1).We will show inductively that these are precisely the first T iterates produced by Algorithm 1 when using thesubgradient oracle defined above. The following claim is easy to verify from the definition of zt .Claim 2.3.• For t ∈ [T +1], zt is non-negative. In particular, zt, j ≥ 12(t−1) for j < t and zt, j = 0 for j ≥ t.• ‖z1‖= 0 and ‖zt‖2 ≤ 1t−1 for t > 1. Thus zt ∈X for all t ∈ [T +1].The “triangular shape” of the hi vectors allows us to determine the value and subdifferential at zt .Claim 2.4. f (zt) = Ht(zt) for all t ∈ [T +1]. The subgradient oracle for f at zt returns the vector ht + zt .Proof. We claim that hTt zt = hTi zt for all i > t. By definition, zt is supported on its first t − 1 coordinates.However, ht and hi agree on the first t−1 coordinates (for i> t). This proves the subclaim.Next we claim that zTt ht > zTt hi for all 1≤ i< t. This also follows from the definition of zt and hi:zTt (ht −hi) =t−1∑j=1zt, j(ht, j−hi, j) =t−1∑j=izt, j(ht, j−hi, j) = zt,i(ai+1)+t−1∑j=i+1zt, ja j > 0.These two claims imply that Ht(zt) ≥ Hi(zt) for all i ∈ [T + 1], and therefore f (zt) = Ht(zt). MoreoverI (zt) = { i : Hi(zt) = f (zt) }= {t, . . . ,T +1}. Thus, when evaluating the subgradient oracle at the vector zt , itreturns the vector ht + zt . Since the subgradient returned at zt is determined by Claim 2.4, and the next iterate of SGD arises from astep in the opposite direction, a straightforward induction proof allows us to show the following lemma. Recallthat ηt = 1/t since we assume c = 1.Lemma 2.5. For the function f constructed in this section, the vector xt in Algorithm 1 equals zt , for everyt ∈ [T +1].Proof. By definition, z1 = x1 = 0. By Claim 2.4, the subgradient returned at x1 is h1+ x1 = h1, so Algorithm 1sets y2 = x1−η1h1 = e1, the first standard basis vector. Then Algorithm 1 projects onto the feasible region,obtaining x2 =ΠX (y2), which equals e1 since y2 ∈X . Since z2 also equals e1, the base case is proven.So assume zt = xt for 2 ≤ t < T ; we will prove that zt+1 = xt+1. By Claim 2.4, the subgradient returned at12xt is gˆt = ht + zt . Then Algorithm 1 sets yt+1 = xt −ηt gˆt . Since xt = zt and ηt = 1/t, we obtainyt+1, j = zt, j− 1t (ht, j + zt, j)=t−1tzt, j− 1t ht, j=t−1t{1−(t− j−1)a jt−1 (for j < t)0 (for j ≥ t)}− 1ta j (for j < t)−1 (for j = t)0 (for j > t)=1t{1− (t− j−1)a j (for j < t)0 (for j ≥ t)}− 1ta j (for j < t)−1 (for j = t)0 (for j > t)=1t1− (t− j)a j (for j < t)1 (for j = t)0 (for j ≥ t+1)So yt+1 = zt+1. Since xt+1 =ΠX (yt+1) is defined to be the projection ontoX , and yt+1 ∈X by Claim 2.3, wehave xt+1 = yt+1 = zt+1. The value of the final iterate is easy to determine from Lemma 2.5 and Claim 2.4:f (xT+1) = f (zT+1) = HT+1(zT+1) ≥T∑j=1hT+1, j · zT+1, j ≥T∑j=112(T +1− j) ·12T>logT4T.(Here the second inequality uses Claim 2.3.) This proves (1.2). A small modification of the last calcula-tion proves (1.3); details may be found in Claim 2.11 in the case where c = 1 (the general case follows fromLemma 2.1). This completes the proof of Theorem 1.12.2.2 Lower bound on error of final iterate, Lipschitz caseIn this section we prove a lower bound result for Lipschitz functions analogous to those in Section 2.1. Through-out this section we will assume that ηt = c√t where c = 1. Specifically, we define a function f = fT , dependingon T , for which the final iterate produced by Algorithm 1 has f (xT ) = Ω(log(T )/√T ), thereby proving (1.4)when c = 1. Then, Eq. (1.4) for arbitrary c> 0 is a corollary of the result with c = 1 and Lemma 2.1.The function f is defined as follows. As before,X denotes the Euclidean unit ball in RT . For i∈ [T ], definethe positive scalar parametersai =18(T − i+1) bi =√i2√T.13Define f :X → R and hi ∈ RT for i ∈ [T +1] byf (x) = maxi∈[T+1]hTi x where hi, j =a j (if 1≤ j < i)−bi (if i = j ≤ T )0 (if i< j ≤ T ).Note that f is 1-Lipschitz overX because‖hi‖2 ≤T∑j=1a2j +b2T =164T∑j=11j2+14<12.Also, the minimum value of f overX is non-positive because f (0) = 0.Subgradient oracle. In order to execute Algorithm 1 on f we must specify a subgradient oracle. Similar toClaim 2.2, [19, Theorem 4.4.2] impliesClaim 2.6. ∂ f (x) is the convex hull of { hi : i ∈I (x) }, where I (x) ={i : hTi x = f (x)}.Our subgradient oracle is as follows: given x, it simply returns hi′+ x where i′ = minI (x).Explicit description of iterates. Next we will explicitly describe the iterates produced by executing Algo-rithm 1 on f . Define the points zt ∈ RT for t ∈ [T +1] by z1 = 0 andzt, j =(b j√j− a jt−1∑k= j+11√k)(if 1≤ j < t)0 (if t ≤ j ≤ T ).(for t > 1).We will show inductively that these are precisely the first T iterates produced by Algorithm 1 when using thesubgradient oracle defined above.Claim 2.7. For t ∈ [T +1], zt is non-negative. In particular, zt, j ≥ 14√T for j < t and zt, j = 0 for j ≥ t.Proof. By definition, zt, j = 0 for all j ≥ t. For j < t,zt, j =(b j√j−a jt−1∑k= j+11√k)=(12√T− 18(T − j+1)t−1∑k= j+11√k)(by definition of a j and b j)≥ 12√T− 14(T − j+1)t−1− j√t−1 (by Claim A.10)≥ 12√T− 14√T(by Claim A.11), replacing t with t+1=14√T.14Claim 2.8. zt, j ≤ 1/√T for all j. In particular, zt ∈X (the unit ball in RT ).Proof. We have zt, j = 0 for all j ≥ t, and for j < t, we havezt, j =(b j√j−a jt∑k= j+11√k)≤ b j√j=12√T.Since Claim 2.7 shows that zt ≥ 0, we have ‖zt‖ ≤ 1, and therefore zt ∈X . The “triangular shape” of the hi vectors allows us to determine the value and subdifferential at zt .Claim 2.9. f (zt) = hTt zt for all t ∈ [T +1]. The subgradient oracle for f at zt returns the vector ht .Proof. We claim that hTt zt = hTi zt for all i > t. By definition, zt is supported on its first t − 1 coordinates.However, ht and hi agree on the first t−1 coordinates (for i> t). This proves the subclaim.Next we claim that zTt ht > zTt hi for all 1≤ i< t. This also follows from the definition of zt and hi:zTt (ht −hi) =t−1∑j=1zt, j(ht, j−hi, j) (zt is supported on first t−1 coordinates)=t−1∑j=izt, j(ht, j−hi, j) (hi and ht agree on first i−1 coordinates)= zt,i(ai+bi)+t−1∑j=i+1zt, ja j> 0.These two claims imply that hTt zt ≥ hTi zt for all i ∈ [T + 1], and therefore f (zt) = hTt zt . Moreover I (zt) ={i : hTi zt = f (zt)}= {t, . . . ,T +1}. Thus, when evaluating the subgradient oracle at the vector zt , it returns thevector ht . Since the subgradient returned at zt is determined by Claim 2.9, and the next iterate of SGD arises from astep in the opposite direction, a straightforward induction proof allows us to show the following lemma.Lemma 2.10. For the function f constructed in this section, the vector xt in Algorithm 1 equals zt , for everyt ∈ [T +1].Proof. The proof is by induction. By definition x1 = 0 and z1 = 0, establishing the base case.So assume zt = xt for t ≤ T ; we will prove that zt+1 = xt+1. Recall that Algorithm 1 sets yt+1 = xt −ηtgt ,and that ηt = 1√t . By the inductive hypothesis, xt = zt . By Claim 2.9, the algorithm uses the subgradient gt = ht .15Thus,yt+1, j = zt, j− 1√t ht, j={ b j√j −a j∑t−1k= j+1 1√k (for 1≤ j < t)0 (for j ≥ t)}− 1√ta j (for 1≤ j < t)−bt (for j = t)0 (for j > t)=b j√j −a j∑tk= j+1 1√k (for j < t)bt√t (for j = t)0 (for j > t)So yt+1 = zt+1. Since xt+1 = ΠBT (yt+1) by definition, and yt+1 ∈X by Claim 2.8, we have xt+1 = yt+1 =zt+1. The value of the final iterate is easy to determine from Lemma 2.5 and Claim 2.4:f (xT+1) = f (zT+1) = hTT+1zT+1 =T∑j=1hT+1, j · zT+1, j ≥T∑j=118(T +1− j) ·14√T>logT32√T.(Here the second inequality uses Claim 2.7.) This proves (1.4). A small modification of the last calculationproves (1.5) in the case where c = 1 (the general case follows from Lemma 2.1); details may be found inClaim 2.12. The proof of (1.6) may be found in Subsection 2.3.3. This completes the proof of Theorem 1.14.2.3 Omitted proofs for the lower bounds2.3.1 Strongly convex caseThe following claim proves Eq. (1.3) when c = 1. The result in full generality follows then as a corollary of thecase when c = 1 and Lemma 2.1.Claim 2.11. For any k ∈ [T ], let x¯ = ∑T+1t=T−k+2λtxt be any convex combination of the last k iterates. Thenf (x¯) ≥ ln(T )− ln(k)4T.Proof. By Lemma 2.5, xt = zt ∀t ∈ [T +1]. By Claim 2.3, every zt ≥ 0 so x¯≥ 0. Moreover, zt, j ≥ 1/2T for all16T − k+2≤ t ≤ T +1 and 1≤ j ≤ T − k+1. Consequently, x¯ j ≥ 1/2T for all 1≤ j ≤ T − k+1. Thus,f (x¯) ≥ hTT+1x¯ (by definition of f )=T−k+1∑j=1hT+1, j x¯ j︸︷︷︸≥1/2T+T∑j=T−k+2hT+1, j x¯ j︸ ︷︷ ︸≥0≥T−k+1∑j=1a j · 12T=12TT−k+1∑j=112(T +1− j)≥ 14TT−k+1∑j=11T +1− j≥ 14T∫ T−k+111T +1− x dx=log(T )− log(k)4T2.3.2 Lipschitz caseThe following claim proves Eq. (1.5) in the case when c = 1. The result in full generality follows from the casec = 1 and Lemma 2.1.Claim 2.12. For any k ∈ [T ], let x¯ = ∑T+1t=T−k+2λtxt be any convex combination of the last k iterates. Thenf (x¯) ≥ ln(T )− ln(k+1)32√T.Proof. By Lemma 2.10, xt = zt for all t. By Claim 2.7, every zt ≥ 0 so x¯ ≥ 0. Moreover, zt, j ≥ 1/4√T for allT − k+2≤ t ≤ T +1 and 1≤ j ≤ T − k+1, and zt,T ≥ 0 for all t ≤ T +1. Consequently, x¯ j ≥ 1/4√T for all171≤ j ≤ T − k+1 and x¯T ≥ 0. Thus,f (x¯) ≥ hTT+1x¯ (by definition of f )=T−k+1∑j=1hT+1, jx¯ j +T∑j=T−k+2hT+1, jx¯ j︸ ︷︷ ︸≥0≥T−k+1∑j=1a j14√T=14√TT−k+1∑j=118(T − j+1)≥ 132√T∫ T−k+111T − x+1 dx=log(T )− log(k)32√T2.3.3 MonotonicityThe following claim completes the proof of Eq. (1.6) when c = 1. The general result follows as a consequenceof the case when c = 1 and Lemma 2.1.Claim 2.13. For any i≤ T , we have f (xi+1)≥ f (xi)+1/32√T (T − i+1).Proof.f (xi+1)− f (xi) = hTi+1zi+1−hTi zi (by Claim 2.9)=i∑j=1(hi+1, jzi+1, j−hi, jzi, j)=i−1∑j=1(hi+1, jzi+1, j−hi, jzi, j)+(hi+1,izi+1,i−hi,i zi,i︸︷︷︸=0)=i−1∑j=1a j(zi+1, j− zi, j)+aizi+1,i=i−1∑j=1a j ·(−a j√i)+18(T − i+1)zi+1,i≥ − 164√ii−1∑j=1( 1T − j+1)2+132√T (T − i+1) (by Claim 2.7)≥ 164√T (T − i+1) (by Claim 2.14)18Claim 2.14. For any i≤ T1√ii−1∑j=1( 1T − j+1)2≤ 1√T· 1T − i+1 .Proof. Applying Claim A.12 shows thati−1∑j=1( 1T − j+1)2=T∑`=T−i+21`2≤ 1T − i+1 −1T=i−1T (T − i+1) ≤ =iT (T − i+1) .So it suffices to prove that √iT (T − i+1) ≤1√T· 1T − i+1 .This obviously holds as i≤ T . 19Chapter 3High Probability Bounds3.1 Upper bound on error of final iterate, strongly convex caseWe now turn to the proof of the upper bound on the error of the final iterate of SGD, in the case where fis 1-strongly convex and 1-Lipschitz (Theorem 1.9). Recall that the step size used by Algorithm 1 in thiscase is ηt = 1/t. We will write gˆt = gt − zˆt , where gˆt is the vector returned by the oracle at the point xt ,gt ∈ ∂ f (xt), and zˆt is the noise. Let Ft = σ(zˆ1, . . . , zˆt) be the σ -algebra generated by the first t steps of SGD.Finally, recall that ‖zˆt‖ ≤ 1 and E [ zˆt | Ft−1 ] = 0. Without loss of generality, we may assume that T ≥ 4 sincef (xT )− f (x∗) ≤ O(1) for T < 4. Moreover, we may assume without loss of generality that T is even becausef (xT )− f (xT−1)≤ O(1/T ).We begin with the following lemma which can be inferred from the proof of Theorem 1 in Shamir andZhang [43]. For completeness, we provide a proof in Section 3.3.Lemma 3.1. Let f be 1-strongly convex and 1-Lipschitz. Suppose that we run SGD (Algorithm 1) with stepsizes ηt = 1/t. Assume that T is even. Thenf (xT ) ≤ 1T/2+1T∑t=T/2f (xt)︸ ︷︷ ︸suffix average+T/2∑k=11k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉︸ ︷︷ ︸ZT , the noise term+ O(logTT).Lemma 3.1 asserts that the error of the last iterate is upper bounded by the sum of the error of the suffixaverage and some noise terms (up to the additive O(log(T )/T ) term). Thus, it remains to show that the errordue to the suffix average is small with high probability (Theorem 1.17) and the noise terms, which we denote byZT , are small. We defer the proof of Theorem 1.17 to Subsection 3.1.3. By changing the order of summation,we can writeZT =T∑t=T/2〈 zˆt , wt 〉 (3.1)where wt =t∑j=T/2α j(xt − x j) and α j = 1(T − j)(T − j+1) for j ∈ [T −1],20and set αT = 0 to ensure a summand of 0 when j= t = T. The main technical difficulty is to show that ZT is smallwith high probability. Formally, we prove the following lemma, whose proof is outlined in Subsection 3.1.1.Lemma 3.2. ZT ≤ O(log(T ) log(1/δ )T)with probability at least 1−δ .Given Theorem 1.17 and Lemma 3.2, the proof of Theorem 1.9 is immediate when T is even. In the case whereT is odd, we may apply the argument for T − 1 and then use the fact that f (xT ) ≤ f (xT−1)+O(1/T ) sinceηt = 1/T and ‖gˆt‖= O(1).3.1.1 Bounding the noiseThe main technical difficulty in the proof is to understand the noise term, which we have denoted by ZT . Noticethat (Zt)T/2≤t≤T is a martingale with respect to (Ft)T/2≤t≤T since E [ zˆt | Ft−1 ] = 0, wt is Ft−1 measurableand E [ |〈 zˆt , wt 〉| ]< ∞. The last property holds because we may use the fact that∥∥xt − x j∥∥= O(1). The naturalstarting point is to better understand the sum of squared magnitudes (SSCM) of ZT . Notice that |〈 zˆt , wt 〉| ≤ ‖wt‖and wt is Ft−1 measurable. Therefore, we use ∑Tt=T/2 ‖wt‖2 as the SSCM process of ZT . We we will seethat ∑Tt=T/2 ‖wt‖2 is bounded by a linear transformation of ZT . This “chicken and egg” relationship inspiresus to derive a new probabilistic tool (generalizing Freedman’s Inequality) to disentangle the SSCM from themartingale.The main challenge in analyzing ‖wt‖ is to precisely analyze the distance∥∥xt − x j∥∥ between SGD iterates.A loose bound of∥∥xt − x j∥∥2 . (t− j)∑t−1i= j ‖gˆi‖2i2 follows easily from Jensen’s Inequality. We prove the followingtighter bound, which may be of independent interest. The proof is in Section 3.3.Lemma 3.3. Suppose f is 1-Lipschitz and 1-strongly convex. Suppose we run Algorithm 1 for T iterations withstep sizes ηt = 1/t. Let a< b. Then,‖xa− xb‖2 ≤b−1∑i=a‖gˆi‖2i2+2b−1∑i=a(f (xa)− f (xi))i+2b−1∑i=a〈 zˆi, xi− xa 〉i.Using Lemma 3.3 and some delicate calculations we obtain the following upper bound on ∑Tt=T/2 ‖wt‖2, re-vealing the surprisingly intricate relationship between ZT (the martingale) and∑Tt=T/2 ‖wt‖2 (its SSCM process).This is the main technical step that inspired our probabilistic tool (the generalized Freedman’s Inequality).Lemma 3.4 (Main Technical Lemma). There exists positive values R1 = O(log2 TT 2), R2 = O(logTT), Ct =Θ(log(T − t)), R3 = O(logTT 2)such thatT∑t=T/2‖wt‖2 ≤ R1+R2∥∥xT/2− x∗∥∥2+ T−1∑t=T/2Ctt〈 zˆt , wt 〉︸ ︷︷ ︸≈O(log(T )/T )ZT+R3T−1∑t=T/2〈 zˆt , xt − x∗ 〉. (3.2)This bound is mysterious in that the left-hand side is an upper bound on the sum of squared magnitudes ofZT , whereas the third term on the right-hand side is essentially a scaled version of ZT itself. This is the “chickenand egg phenomenon” alluded to in Section 1.4, and it poses another one of the main challenges of boundingZT . This bound inspires our main probabilistic tool, which we restate for convenience here.21Theorem 1.11 (Generalized Freedman). Let {di,Fi}ni=1 be a martingale difference sequence. Suppose vi−1,for i ∈ [n], are positive and Fi−1-measurable random variables such that E [exp(λdi) | Fi−1 ] ≤ exp(λ 22 vi−1)for all i ∈ [n], λ > 0. Let St = ∑ti=1 di and Vt = ∑ti=1 vi−1. Let αi ≥ 0 and set α = maxi∈[n]αi. ThenPr[n⋃t=1{St ≥ x and Vt ≤t∑i=1αidi+β} ]≤ exp(− x4α+8β/x)∀x,β > 0.In order to apply Theorem 1.11, we need to refine Lemma 3.4 to replace the terms∥∥xT/2− x∗∥∥2 andR3∑T−1t=T/2〈 zˆt , (xt−x∗)〉with sufficient high probability upper bounds. Rakhlin et al. [36] showed that ‖xt − x∗‖2≤O(log log(T )/T ) for all T2 ≤ t ≤ T simultaneously, with high probability, which does not suffice for our pur-poses. In contrast, our analysis only needs a high probability bound on∥∥xT/2− x∗∥∥2 and R3∑Tt=T/2 ‖xt − x∗‖2;this allows us to avoid a log logT factor here by foregoing a simultaneous analysis on all of the ‖xt − x∗‖2 terms.Indeed, we haveTheorem 3.5. Both of the following hold:• For all t ≥ 2, ‖xt − x∗‖2 ≤ O(log(1/δ )/t) with probability 1−δ , and• Let σt ≥ 0 for t = 2, . . . ,T . Then, ∑Tt=2σt ‖xt − x∗‖2 = O(∑Tt=2σtt log(1/δ ))w.p. 1−δ .The proof of Theorem 3.5, in Subsection 3.1.2, uses our tool for bounding recursive stochastic processes(Theorem 1.19). Therefore, we need to expose a recursive relationship between ‖xt+1− x∗‖2 and ‖xt − x∗‖2 thatsatisfies the conditions of Theorem 1.19. Interestingly, Theorem 3.5 is also the main ingredient in the analysisof the error of the suffix average (see Subsection 3.1.3). We now have enough to give our refined version ofLemma 3.4, which is now in a format usable by Freedman’s Inequality.Lemma 3.6. For every δ > 0 there exists positive values R = O(log2 T log(1/δ )T 2), Ct = Θ(log(T − t)) such that∑Tt=T/2 ‖wt‖2 ≤ R+∑T−1t=T/2 Ctt 〈 zˆt , wt 〉, with probability at least 1−δ .Proof. The lemma essentially follows from combining our bounds in Theorem 3.5 with an easy corollaryof Freedman’s Inequality (Corollary 4.4) which states that a high probability bound of M on the SSCM of amartingale implies a high probability bound of√M on the martingale.Let R1, R2,R3 and Ct be as in Lemma 3.4. Consider the resulting upper bound on ∑Tt=T/2 ‖wt‖2. We al-ready have a bound on the first term in Eq. (3.2), namely R1 = O(log2(T )/T 2). We know proceed to givea high probability bound on the second term, and the fourth term. The first claim in Theorem 3.5 givesR2∥∥xT/2− x∗∥∥2 = O( logT log(1/δ )T 2 ) with probability at least 1−δ because R2 = O(log(T )/T ).By the second claim in Theorem 3.5, we have R23∑T−1t=T/2 ‖xt − x∗‖2 = O(log2 TT 4 log(1/δ ))with probabilityat least 1− δ because R3 = O(logTT 2). Hence, we have derived a high probability bound on the SSCM ofR3∑Tt=T/2〈 zˆt , xt−x∗ 〉. Therefore, we turn this into a high probability bound on the martingale itself by applyingCorollary 4.4 and obtain R3∑T−1t=T/2〈 zˆt , xt − x∗ 〉= O(logT log(1/δ )T 2)with probability at least 1−δ . Now that we have derived an upper bound on the sum of squared conditional magnitudes of ZT in the formrequired by our Generalized Freedman Inequality (Theorem 1.11), we are finally ready to prove Lemma 3.2 (ourhigh probability upper bound on the noise, ZT ).22Proof (of Lemma 3.2). We have demonstrated that ZT satisfies the “Chicken and Egg” phenomenon with highprobability. Translating this into a high probability upper bound on the martingale ZT itself is a corollary ofTheorem 1.11. Indeed, if (Mt)T/2≤t≤T is a martingale with increments di and if its SSCM process at time stepT is bounded by R log(1/δ )+∑Tt=T/2αtdt with maxt αt = O(√R). Then Corollary 4.5 bounds the martingale attime step T by√R log(1/δ ) with high probability.Recall that our martingale at time T is ZT = ∑Tt=T/2〈 zˆt , wt 〉. Let at = zˆt , bt = wt , and dt = 〈 at , bt 〉 fort = T/2, . . . ,T and at = bt = dt = 0 for t < T/2. Then, ZT =∑Tt=T/2 dt as in the conclusion of Corollary 4.5. Tosatisfy the hypothesis of Corollary 4.5, we will use Lemma 3.6 which showsT∑t=1‖bt‖2 =T∑t=T/2‖wt‖2 ≤ R log(1/δ )+T∑t=T/2Ctt︸︷︷︸:=αt〈 zˆt , wt 〉︸ ︷︷ ︸=dt,where R = O(log(T )2/T 2). Notice that maxt αt = maxt Ctt = O(log(T )/T ) = O(√R). Hence, applying Corol-lary 4.5 proves that ZT =O(√R log(1/δ )) =O((logT log(1/δ ))/T ) with probability at least 1−δ , as required.3.1.2 High probability bounds on squared distances to x∗In this section, we prove Theorem 3.5. We begin with the following claim which can be extracted from [36,Equation (11)] by taking G = 4 (since ‖gˆt‖2 ≤ (‖zˆt‖+‖gt‖)2 ≤ (1+1)2 = 4), λ = 1, and ηt = 1/t.Claim 3.7 ([36, Proof of Lemma 6]). Suppose f is 1-strongly-convex and 1-Lipschitz. Define Yt = t ‖xt+1− x∗‖2and Ut = 〈 zˆt+1, xt+1− x∗ 〉/‖xt+1− x∗‖2. ThenYt+1 ≤(t−1t)Yt +2 ·Ut√Ytt+4t+1.This claim exposes a recursive relationship between ‖xt+1− x∗‖2 and ‖xt − x∗‖2 and inspires our probabilis-tic tool for recursive stochastic processes (Theorem 1.19). We prove Theorem 3.5 using this tool:Proof (of Theorem 3.5). Consider the stochastic process (Yt)T−1t=1 where Yt is as defined by Claim 3.7. Notethat Yt satisfies the conditions of Theorem 1.19 with Xt = Yt , wˆt = Ut , αt = t−1t = 1− 1/t, βt = 2/√t, andγt = 4/(t +1). Observe that Ut is a Ft+1 measurable random variable which is mean zero conditioned on Ft .Furthermore, note that |Ut | ≤ 1 with probability 1 because ‖zˆt+1‖ ≤ 1 with probability 1. Furthermore, it is easyto check that max1≤t≤T(2γt1−αt ,2β 21−αt)= 8 with the above setup. Lastly, we observe that ‖x2− x∗‖2 ≤ 4 withprobability 1. Indeed by 1-strong-convexity and 1-Lipschitzness of f ,‖xt − x∗‖ ≥ 〈gt , xt − x∗ 〉 ≥ 12 ‖xt − x∗‖2 .Thus, taking K = 8, it follows that E [exp(λX1) ]≤ exp(λK), as required by Theorem 1.19. So, we may applyTheorem 1.19 to obtain:• For every t = 1, . . .T −1, Pr [Yt ≥ 8log(1/δ ) ]≤ eδ .• Let σ ′t ≥ 0 for t = 1, . . . ,T −1. Then, Pr[∑T−1t=1 σ′t Yt ≥ 8log(1/δ )∑T−1t=1 σ ′t]≤ eδ .23Recalling that Yt = t ‖xt+1− x∗‖2 and setting σ ′t = σt/t and adjusting δ as required proves Theorem 3.5. 3.1.3 Upper bound on error of suffix averagingTo complete the proof of the final iterate upper bound (Theorem 1.9), it still remains to prove the suffix averagingupper bound (Theorem 1.17). In this section, we prove this result as a corollary of the high probability bounds on‖xt − x∗‖2 that we obtained in the previous subsection. See Section 3.4 for an alternative proof of Theorem 1.17which does not involve the high probability bounds on ‖xt − x∗‖2.The following proof of Theorem 1.17 is quite short and involves several ingredients. Some of the ingredientsare fairly standard: Lemma 3.14 is a standard analysis of Algorithm 1 and Corollary 4.4 is an easy corollary ofFreedman’s inequality which takes a high probability bound on the sum of squared magnitudes (SSCM) processof a martingale and converts it into a high probability bound on the martingale itself. The main novel ingredientis Theorem 3.5 which allows one to bound ∑Tt=T/2 ‖xt − x∗‖2 by O(log(1/δ )) with probability at least 1− δ .This summation is the SSCM process of a martingale which arises from an application of Lemma 3.14. Then,Corollary 4.4 converts this high probability bound on the SSCM to a high probability bound on the martingale.Proof (of Theorem 1.17). By Lemma 3.14 with w = x∗ we haveT∑t=T/2[ f (xt)− f (x∗)] ≤ 12T∑t=T/2ηt ‖gˆt‖2︸ ︷︷ ︸(a)+12ηT/2∥∥xT/2− x∗∥∥2︸ ︷︷ ︸(b)+T∑t=T/2〈 zˆt , xt − x∗ 〉︸ ︷︷ ︸(c). (3.3)It suffices to bound the right hand side of (3.3) by O(log(1/δ )) with probability at least 1−δ . Indeed, bounding‖gˆt‖2 by 4, (a) in (3.3) is bounded by O(1). Term (b) is bounded by O(log(1/δ )) by Theorem 3.5.It remains to bound (c). Theorem 3.5 implies ∑Tt=T/2 ‖xt − x∗‖2 = O(log(1/δ )) with probability at least1−δ . Therefore, Corollary 4.4 shows that (c) is at most O(log(1/δ )) with probability at least 1−δ . 3.2 Upper bound on error of final iterate, Lipschitz case: proof sketchIn this section we provide a proof sketch of the upper bound of the final iterate of SGD, in the case where f is 1-Lipschitz but not necessarily strongly-convex (Theorem 1.10). The proof of Theorem 1.10 closely resembles theproof of Theorem 1.9 and we will highlight the main important differences. Perhaps the most notable differenceis that the analysis in the Lipschitz case does not require a high probability bound on ‖xt − x∗‖2.Recall that the step size used by Algorithm 1 in this case is ηt = 1/√t. We will write gˆt = gt − zˆt , where gˆtis the vector returned by the oracle at the point xt , gt ∈ ∂ f (xt), and zˆt is the noise. LetFt = σ(zˆ1, . . . , zˆt) be theσ -algebra generated by the first t steps of SGD. Finally, recall that ‖zˆt‖ ≤ 1 and E [ zˆt | Ft−1 ] = 0.As before, we begin with a lemma which can be obtained by modifying the proof of Lemma 3.1 to replaceapplications of strong convexity with the subgradient inequality.Lemma 3.8. Let f be 1-Lipschitz. Suppose that we run SGD (Algorithm 1) with step sizes ηt = 1√t . Then,f (xT ) ≤ 1T/2+1T∑t=T/2f (xt)︸ ︷︷ ︸suffix average+T/2∑k=11k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉︸ ︷︷ ︸ZT , the noise term+ O(log(T )√T).24Lemma 3.8 asserts that the error of the last iterate is bounded by the sum of the error of the average of theiterates and some noise terms (up to the additive O(logT/√T ) term). A standard analysis (similar to the proofof Lemma 3.14) reveals ∑Tt=T/2 [ f (xt)− f (x∗)] ≤ O(√T )+∑Tt=T/2〈 zˆt , xt − x∗ 〉. Applying Azuma’s inequalityon the summation (using the diameter bound to obtain 〈 zˆt , xt − x∗ 〉2 ≤ 1) showsLemma 3.9. For every δ ∈ (0,1),1T/2+1[T∑t=T/2f (xt)− f (x∗)]= O(√log(1/δ )/T),with probability at least 1−δ .As a consequence of Lemma 3.9, it is enough to prove that the error due to the noise terms are small in orderto complete the proof of Theorem 1.10. By changing the order of summation, we can write ZT =∑Tt=T/2〈 zˆt , wt 〉wherewt =t−1∑j=1α j(xt − x j) and α j = 1(T − j)(T − j+1) .Just as in Section 3.1, the main technical difficulty is to show that ZT is small with high probability. Formally,we prove the following lemma, whose proof is outlined in Subsection 3.2.1.Lemma 3.10. For every δ ∈ (0,1), ZT ≤ O(log(T ) log(1/δ )/√T)with probability at least 1−δ .Given Lemma 3.9 and Lemma 3.10, the proof of Theorem 1.10 is straightforward. The next sub-section providesa proof sketch of Lemma 3.10.3.2.1 Bounding the noiseThe goal of this section is to prove Lemma 3.10. Just as in Section 3.1, the main technical difficulty is tounderstand the noise term, denoted ZT . Observe that (Zt)T/2≤t≤T a martingale, and ∑Tt=T/2 ‖wt‖2 is the SSCMof ZT . The SSCM of ZT will be shown to exhibit the “chicken and egg” relationship which we have alreadyseen explicitly exhibited by the SSCM of the noise terms in the strongly convex case. That is, we will see thatthe ∑Tt=T/2 ‖wt‖2 is bounded by a linear transformation of ZT . We will again use our Generalized Freedman todisentangle the sum of squared magnitudes from the martingale.The distance∥∥xt − x j∥∥ between SGD iterates is again a crucial quantity to understand in order to bound∑Tt=T/2 ‖wt‖2 (see Subsection 3.1.1 to see why). Therefore, we develop a distance estimate analogous toLemma 3.3Lemma 3.11. Suppose f is 1-Lipschitz. Suppose we run Algorithm 1 for T iterations with step sizes ηt = 1/√t.Let a< b. Then,‖xa− xb‖2 ≤b−1∑i=a‖gˆi‖2i+2b−1∑i=a(f (xa)− f (xi))√i+2b−1∑i=a〈 zˆi, xi− xa 〉√i.We then use Lemma 3.11 to prove Lemma 3.12, our main upper bound on ∑Tt=T/2 ‖wt‖2. This follows fromsome delicate calculations similar to those in Subsection 3.3.4, replacing the strongly-convex distance estimate(Lemma 3.3) with the Lipschitz distance estimate (Lemma 3.11), along with some other minor modifications.25This upper bound reveals the surprisingly intricate relationship between ZT (the martingale) and ∑Tt=T/2 ‖wt‖2(its SSCM).Lemma 3.12 (Main Technical Lemma (Lipschitz Case)). There exists positive values R1 = O(log2 TT), R2 =O(logTT 1.5), and Ct = O(logT ), such thatT∑t=T/2‖wt‖2 ≤ R1+R2T∑t=T/2〈 zˆt , xt − x∗ 〉+T∑t=T/2〈 zˆt , Ct√t wt 〉︸ ︷︷ ︸≈O(logT/√T )ZT.Just as in Lemma 3.4, the left-hand side is an upper bound on the sum of squared magnitudes of ZT , whereasthe right-hand side essentially contains a scaled version of ZT itself. This is another instance of the “chickenand egg phenomenon” alluded to in Section 1.4, and it is the main challenge of bounding ZT . For convenience,we restate our main probabilistic tool which allows us to deal with the chicken and egg phenomenon.Theorem 1.11 (Generalized Freedman). Let {di,Fi}ni=1 be a martingale difference sequence. Suppose vi−1,for i ∈ [n], are positive and Fi−1-measurable random variables such that E [exp(λdi) | Fi−1 ] ≤ exp(λ 22 vi−1)for all i ∈ [n], λ > 0. Let St = ∑ti=1 di and Vt = ∑ti=1 vi−1. Let αi ≥ 0 and set α = maxi∈[n]αi. ThenPr[n⋃t=1{St ≥ x and Vt ≤t∑i=1αidi+β} ]≤ exp(− x4α+8β/x)∀x,β > 0.In order to apply Theorem 1.11, we need to refine Lemma 3.12 to replace R2∑Tt=T/2〈 zˆt , xt−x∗ 〉 with a suffi-cient high probability upper bound. This is similar to the refinement of Lemma 3.4 from Subsection 3.1.1. How-ever, unlike the refinement in Subsection 3.1.1 (which required a high probability bound on ∑Tt=T/2 At ‖xt − x∗‖2without any diameter bound), the refinement here is quite easy. Using the diameter bound, the almost surebound of ‖zˆt‖ ≤ 1, and Azuma’s inequality, we can bound ∑Tt=T/2〈 zˆt , xt−x∗ 〉 by√T log(1/δ ) with probabilityat least 1−δ . This yields the following lemma.Lemma 3.13. For every δ ∈ (0,1), there exists positive values R = O(log2 T√log(1/δ )T), Ct = O(logT ), suchthat ∑Tt=T/2 ‖wt‖2 ≤ R+∑T−1t=T/2〈 zˆt , Ct√t wt 〉, with probability at least 1−δ .Now that we have derived an upper bound on the sum of squared magnitutdes of ZT in the form requiredby Generalized Freedman Inequality (Theorem 1.11), we are now finally ready to prove Lemma 3.10 (the highprobability upper bound on the noise, ZT ).Proof (of Lemma 3.10). We have demonstrated that ZT satisfies the “Chicken and Egg” phenomenon with highprobability. Translating this into a high probability upper bound on the martingale ZT itself is a corollary ofTheorem 1.11.Indeed, consider a filtration {Ft}Tt=T/2. Let dt = 〈 at , bt 〉 define a martingale difference sequence where‖at‖ ≤ 1 and E [at | Ft−1 ] = 0. Suppose there are positive values, R, αt , such that maxTt=T/2{αt} = O(√R)and ∑Tt=T/2 ‖bt‖2 ≤ ∑Tt=T/2αtdt +R√log(1/δ ) with probability at least 1−δ . Then, Corollary 4.5 bounds themartingale at time step T by√R log(1/δ ) with high probability.26Observe that Lemma 3.13 allows us to apply Corollary 4.5 with at = zˆt , bt = wt , αt = (Ct/√t) for t =T/2, . . . ,T −1, αT = 0, maxTt=T/2{αt}= O(logT/√T), and R = O(log2 T/T)to prove Lemma 3.10.3.3 Omitted proofs from Section 3.13.3.1 Standard analysis of SGDThe following lemma is standard.Lemma 3.14. Let f be an 1-strongly convex and 1-Lipschitz function. Consider running Algorithm 1 for Titerations. Then, for every w ∈X and every k ∈ [T ],T∑t=k[f (xt)− f (w)]≤ 12T∑t=kηt‖gˆt‖2+ 12ηk ‖xk−w‖2+T∑t=k〈 zˆt , xt −w 〉.Proof.f (xt)− f (w) ≤ 〈gt , xt −w 〉− 12 ‖xt −w‖2 (by strong-convexity)= 〈 gˆt , xt −w 〉− 12 ‖xt −w‖2+ 〈 zˆt , xt −w 〉 (gˆt = gt − zˆt)=1ηt〈 xt − yt+1, xt −w 〉− 12 ‖xt −w‖2+ 〈 zˆt , xt −w 〉 (yt+1 = xt −ηt gˆt)=12ηt(‖xt − yt+1‖2+‖xt −w‖2−‖yt+1−w‖2)− 12‖xt −w‖2+ 〈 zˆt , xt −w 〉≤ 12ηt(‖ηt gˆt‖2+‖xt −w‖2−‖xt+1−w‖2)− 12‖xt −w‖2+ 〈 zˆt , xt −w 〉 (by Claim A.8).Now, summing t from k to T ,T∑t=k[f (xt)− f (w)]≤ 12T∑t=kηt ‖gˆt‖2+ 12T∑t=k+1(1ηt− 1ηt−1−1)︸ ︷︷ ︸=0‖xt −w‖2+(12ηk− 12)‖xk−w‖2+T∑t=k〈 zˆt , xt −w 〉≤ 12T∑t=kηt ‖gˆt‖2+ 12ηk ‖xk−w‖2+T∑t=k〈 zˆt , xt −w 〉 (ηt = 1/t),as desired. 273.3.2 Proof of Lemma 3.1Lemma 3.1. Let f be 1-strongly convex and 1-Lipschitz. Suppose that we run SGD (Algorithm 1) with stepsizes ηt = 1/t. Assume that T is even. Thenf (xT ) ≤ 1T/2+1T∑t=T/2f (xt)︸ ︷︷ ︸suffix average+T/2∑k=11k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉︸ ︷︷ ︸ZT , the noise term+ O(logTT).Proof (of Lemma 3.1). Let k ∈ [T −1]. Apply Lemma 3.14, replacing k with T − k and w = xT−k to obtain:T∑t=T−k[f (xt)− f (xT−k)]≤ 12T∑t=T−kηt ‖gˆt‖2+T∑t=T−k〈 zˆt , xt − xT−k 〉.Now, divide this by k+1 and define Sk = 1k+1 ∑Tt=T−k f (xt) to obtainSk− f (xT−k) ≤ 12(k+1)T∑t=T−kηt ‖gˆt‖2+ 1k+1T∑t=T−k〈 zˆt , xt − xT−k 〉Observe that kSk−1 = (k+1)Sk− f (xT−k). Combining this with the previous inequality yieldskSk−1 = kSk +(Sk− f (xT−k)) ≤ kSk + 12(k+1) T∑t=T−kηt ‖gˆt‖2+ 1k+1T∑t=T−k〈 zˆt , xt − xT−k 〉.Dividing by k, we obtain:Sk−1 ≤ Sk + 12k(k+1)T∑t=T−kηt ‖gˆt‖2+ 1k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉.Thus, by induction:f (xT ) = S0≤ ST/2+T/2∑k=112k(k+1)T∑t=T−kηt ‖gˆt‖2+T/2∑k=11k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉 (3.4)=1T/2+1T∑t=T/2f (xt)+T/2∑k=112k(k+1)T∑t=T−kηt ‖gˆt‖2+T/2∑k=11k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉.Since we assume that f is 1 Lipschitz, we have ‖gt‖ ≤ 1. Recall that we assume that the noise is bounded,28i.e. ‖zˆt‖ ≤ 1. Thus ‖gˆt‖2 ≤ 4. Recall that ηt = 1/t. So we can bound the middle term asT/2∑k=112k(k+1)T∑t=T−kηt ‖gˆt‖2 ≤ 2T/2∑k=11k(k+1)T∑t=T−k1t≤ 2T/2∑k=11k(k+1)· k+1T − k= 2T/2∑k=11k(T − k)≤ 4TT/2∑k=11k= O(logTT).This completes the proof. 3.3.3 Proof of Lemma 3.3Lemma 3.3. Suppose f is 1-Lipschitz and 1-strongly convex. Suppose we run Algorithm 1 for T iterationswith step sizes ηt = 1/t. Let a< b. Then,‖xa− xb‖2 ≤b−1∑i=a‖gˆi‖2i2+2b−1∑i=a(f (xa)− f (xi))i+2b−1∑i=a〈 zˆi, xi− xa 〉i.Proof (of Lemma 3.3).‖xa− xb‖2 = ‖xa−ΠX (yb)‖22≤ ‖xa− yb‖22 (Claim A.8)= ‖xa− xb−1+ xb−1− yb‖22= ‖xa− xb−1‖22+‖xb−1− yb‖22+2〈ηb−1gˆb−1, xa− xb−1 〉= ‖xa− xb−1‖22+η2b−1 ‖gˆb−1‖22+2〈ηb−1gˆb−1, xa− xb−1 〉= ‖xa− xb−1‖22+η2b−1 ‖gˆb−1‖22+2〈ηb−1gb−1, xa− xb−1 〉+2〈ηb−1zˆb−1, xb−1− xa 〉Repeating this argument iteratively on ‖xa− xb−1‖, ‖xa− xb−2‖, . . . , ‖xa− xa+1‖, we obtain:‖xa− xb‖2 ≤b−1∑i=a‖gˆi‖22i2+2b−1∑i=a〈gi, xa− xi 〉i+2b−1∑i=a〈 zˆi, xi− xa 〉i.Applying the subgradient inequality 〈 gi, xa− xi 〉 ≤ f (xa)− f (xi) to each term of the second summation givesthe desired result. 293.3.4 Proof of Lemma 3.4Proof (of Lemma 3.4). Recall from Eq. (3.1) that wt = ∑t−1j=T/2α j(xt − x j).Definition 3.15. Define BT := ∑Tt=T/21T−t+1 ∑t−1j=T/2α j∥∥xt − x j∥∥2.Claim 3.16. ∑Tt=T/2 ‖wt‖2 ≤ BT .Proof. Let At = ∑t−1j=T/2α j. Then‖wt‖2 = A2t∥∥∥∥∥ T−1∑j=T/2 α jAt (xt − x j)∥∥∥∥∥2≤ A2tT−1∑j=T/2α jAt∥∥xt − x j∥∥2≤ 1T − t+1t−1∑j=T/2α j∥∥xt − x j∥∥2 ,where the first inequality is due to the convexity of ‖·‖2 and the second inequality is Claim A.13. Using the definition of BT and Lemma 3.3, let us write BT ≤ Λ1+Λ2+Λ3 whereΛ1 := 4T∑t=T/21T − t+1t−1∑j=T/2α jt−1∑i= j1i2(since ‖gˆt‖2 ≤ 4 for all t),Λ2 := 2T∑t=T/21T − t+1t−1∑j=T/2α jt−1∑i= j(Fj−Fi)i(where Fa := f (xa)− f (x∗) ),Λ3 := 2T∑t=T/21T − t+1t−1∑j=T/2α jt−1∑i= j〈 zˆi, xi− x j 〉i.Let us bound each of the terms separately. Recall from Eq. (3.1) that α j = 1(T− j)(T− j+1) for j ∈ [T −1].Claim 3.17. Λ1 ≤ O(log2(T )T 2).Proof. This follows from some straightforward calculations. Indeed,Λ1 = 4T∑t=T/21T − t+1t−1∑j=T/2α jt−1∑i= j1i2≤ 4T∑t=T/21T − t+1t−1∑j=T/21(T − j)(T − j+1)(T − j)(T/2)2≤ 4(T/2)2T∑t=T/21T − t+1t−1∑j=T/21T − j+1≤ O(log2(T )T 2).30Claim 3.18.Λ2 ≤ O(log(T )T 2)+O(log(T )T)∥∥xT/2− x∗∥∥22+O( log(T )T 2) T−1∑t=T/2〈 zˆt , xt − x∗ 〉.We will prove Claim 3.18 in the next section.Claim 3.19.Λ3 =T−1∑i=T/2〈zˆi,Ciiwi〉,where Ci := ∑T`=i+12T−`+1 =Θ(log(T − i)).Proof. Rearranging the order of summation in Λ3 we get:Λ3 =T∑t=T/22T − t+1t−1∑j=T/2α jt−1∑i= j〈 zˆi, xi− x j 〉i=T∑t=T/22T − t+1t−1∑i=T/2〈 zˆi, ∑i−1j=T/2α j(xi− x j) 〉i=T∑t=T/22T − t+1t−1∑i=T/2〈 zˆi, wi 〉i=T−1∑i=T/2〈zˆi,∑Tt=i+1 2T−t+1iwi〉=T−1∑i=T/2〈zˆi,Ciiwi〉,as desired. The previous three claims and the fact that BT is an upper bound on ∑Tt=T/2 ‖wt‖2 (Claim 3.16) complete theproof of Lemma 3.4. 3.3.5 Proof of Claim 3.18Let us rewriteΛ2 =T−1∑a=T/2γaFaand determine the coefficients γa.Claim 3.20. For each a ∈ {T/2, . . . ,T −1}, γa = O(log(T )T 2).Proof. In the definition of Λ2, the indices providing a positive coefficient for Fa must satisfy j = a, a ≤ i, and31a≤ t−1. Recall that we assume T ≥ 4, so a≥ 2. Hence, the positive contribution to γa is:T∑t=1+a2T − t+1αat−1∑i=a1i≤T∑t=1+a(2T − t+1αa)(log(T/(a−1))) (by Claim A.15)≤T∑t=1+a(2T − t+1αa)(T −a+1a−1)(by Claim A.14)=T∑t=1+a(2T − t+1)(1(T −a)(T −a+1))(T −a+1a−1)=1T −aT∑t=1+a2(T − t+1)(a−1) .The terms contributing to the negative portion of γa satisfy, i= a, j≤ a, and a≤ t−1. The negative contributioncan be written as−T∑t=1+a2T − t+1a∑j=T/2α j · 1a= −T∑t=1+a(2T − t+1)(1a)(1T −a −1T/2+1)(by Claim A.13)= −T∑t=1+a(2T − t+1)(1a)(2a−T +22(T/2+1)(T −a))= − 1(T/2+1)(T −a)T∑t=1+a(2T − t+1)(2a−T +22a)= − 2(T +2)(T −a)T∑t=1+a(2T − t+1)(1− T −22a).32Now, combining the positive and negative contribution we see:γa ≤ 1T −aT∑t=1+a2T − t+1(1a−1 −2T +2(1− T −22a))=1T −aT∑t=1+a2T − t+1(T +2−2(a−1)(1− T−22a )(a−1)(T +2))=1T −aT∑t=1+a2T − t+1(T +2−2(a−1)+ 2(T−2)(a−1)2a(a−1)(T +2))≤ 1T −aT∑t=1+a2T − t+1(2(T −a)+2(T +2)(a−1))≤ 1T −aT∑t=1+a2T − t+1(2(T −a)+2(T −a)(T +2)(a−1))(a≤ T −1)=1(T +2)(a−1)T∑t=1+a8T − t+1≤ 1(T +2)(T/2−1)T∑t=1+a8T − t+1 (a≥ T/2)= O(log(T )T 2),as desired. Proof (of Claim 3.18).Λ2 =T−1∑a=T/2γaFa≤ O(log(T )T 2) T−1∑a=T/2(f (xa)− f (x∗))(by Claim 3.20 and the definition of Fa)Then by Lemma 3.14 with k = T/2 and w = x∗,≤ O(log(T )T 2)(12T−1∑t=T/2ηt ‖gˆt‖2+ 12ηT/2∥∥xT/2− x∗∥∥2+ T−1∑t=T/2〈 zˆt , xt − x∗ 〉)(3.5)≤ O(log(T )T 2) T−1∑t=T/21t+O(log(T )T)∥∥xT/2− x∗∥∥2+O( log(T )T 2) T−1∑t=T/2〈 zˆt , xt − x∗ 〉 (‖gˆt‖ ≤ 2)≤ O(log(T )T 2)+O(log(T )T)∥∥xT/2− x∗∥∥2+O( log(T )T 2) T−1∑t=T/2〈 zˆt , xt − x∗ 〉,as desired. 3.3.6 Proof of Claim 3.7Proof (of Claim 3.7). We begin by stating two consequences of strong convexity:331. 〈gt ,xt − x∗〉 ≥ f (xt)− f (x∗)+ 12 ‖xt − x∗‖2,2. f (xt)− f (x∗)≥ 12 ‖xt − x∗‖2 (since 0 ∈ ∂ f (x∗)).The analysis proceeds as follows:‖xt+1− x∗‖2 = ‖ΠX (xt −ηt gˆt)− x∗‖2≤ ‖xt −ηt gˆt − x∗‖2 (Claim A.8)= ‖xt − x∗‖2−2ηt〈gˆt ,xt − x∗〉+η2t ‖gˆt‖2= ‖xt − x∗‖2−2ηt〈gt ,xt − x∗〉+2ηt〈zˆt ,xt − x∗〉+η2t ‖gˆt‖2≤ ‖xt − x∗‖2−2ηt(f (xt)− f (x∗))− 1t‖xt − x∗‖2+2ηt〈zˆt ,xt − x∗〉+η2t ‖gˆt‖2≤(1− 2t)‖xt − x∗‖2+2ηt〈zˆt ,xt − x∗〉+η2t ‖gˆt‖2=(t−2t)Yt−1t−1 +2tUt−1√Yt−1t−1 +‖gˆt‖2t2.Recall that ‖gˆt‖2 ≤ 4 because zˆt ≤ 1 and f is 1-Lipschitz. Multiplying through by t and bounding ‖gˆt‖2 by 4yields the desired result. 3.4 Alternative proof of Theorem 1.17In this section we demonstrate how to prove Theorem 1.17 using the Generalized Freedman inequality. Inparticular, we will not use Theorem 3.5 (the high probability bound on ‖xt − x∗‖2), which was the main tool usedto bound the error of suffix-averaging in Subsection 3.1.3. Here, we state a specialized form of the GeneralizedFreedman’s Inequality which is a direct corollary from Lemma 4.3. Notice that Theorem 3.21 does not includeVT in the event which it bounds whereas Theorem 1.11 includes VT . This is because Theorem 3.21 assumesthat VT satisfies the “chicken and egg” phenomenon almost surely whereas Theorem 1.11 does not make thisassumption.Theorem 3.21. Let {dt ,Ft}Tt=1 be a martingale difference sequence. Suppose that, for t ∈ [T ], vt−1 are non-negativeFt−1-measurable random variables satisfying E [exp(λdt) | Ft−1 ]≤ exp(λ 22 vt−1)for all λ > 0. LetST = ∑Tt=1 dt and VT = ∑Tt=1 vt−1. Suppose there exists α1, . . . ,αT ,β ∈ R≥0 such that VT ≤ ∑Tt=1αtdt +β . Letα ≥maxt∈[T ]αt . ThenPr [ST ≥ x ] ≤ exp(− x24α · x+8β).The main idea of this proof is to upper bound the error of the suffix average by a martingale whose sumof squared conditional magnitudes (SSCM) is bounded above by a linear combination of its own increments,where the coefficients in the linear combination are all O(1). Informally, we will showT∑t=T/2[ f (xt)− f (x∗)] ≤T∑t=1dt +O(1) andT∑t=1d2t ≤T∑t=1O(1)dt +O(1).34Then, an application of Theorem 3.21 using α = O(1), β = O(1) and x = O(log(1/δ )) proves Theorem 1.17.More formally, we prove the following lemmata.Lemma 3.22. Let f be a 1 strongly-convex and 1-Lipschitz function over X . Consider running SGD (Algo-rithm 1) until time T with step size ηt = 1/t. Let x∗ = argminx∈X f (x). Then,T∑t=T/2( f (xt)− f (x∗)) ≤ ζ +T/2−1∑t=2ξt〈 zˆt , xt − x∗ 〉+T∑t=T/2〈 zˆt , xt − x∗ 〉, (3.6)where ζ = O(1) and ξt =Θ( tT).Lemma 3.23. Let ξt be as in Lemma 3.22. Then,T/2−1∑t=2ξ 2t ‖xt − x∗‖2+T∑t=T/2‖xt − x∗‖2 ≤ σ +T/2−1∑t=2σtξt〈 zˆt , xt − x∗ 〉+T∑t=T/2σt〈 zˆt , xt − x∗ 〉, (3.7)where σ and σt are O(1) for all t.Lemma 3.22 and Lemma 3.23 suffice for us to prove Theorem 1.17 by applying Theorem 3.21.Proof (of Theorem 1.17). It suffices to bound ∑Tt=T/2 ( f (xt)− f (x∗)) by O(log(1/δ )) with probability at least1−δ . Let dt = ξt〈 zˆt , xt−x∗ 〉 for t = 2, . . . ,T/2−1, dt = 〈 zˆt , xt−x∗ 〉 for t = T/2, . . . ,T, and d1 = 0. ApplyingLemma 3.22, it suffices to bound∑Tt=1 dt by O(log(1/δ ))with probability at least 1−δ .We check the conditionsneeded to apply Theorem 3.21.Let vt−1 = 0 for t = 1, vt−1 = ξ 2t ‖xt − x∗‖2 for t = 2, . . . ,T/2−1 and vt−1 = ‖xt − x∗‖2 for t = T/2, . . . ,T.Using Cauchy-Schwarz and the almost sure bound on ‖zˆt‖, we see |〈 zˆt , xt − x∗ 〉| ≤ ‖xt − x∗‖ . Because ‖xt − x∗‖is Ft−1-measurable, this implies (via Hoeffdings Lemma – Lemma A.5) that for every t and λ > 0 we haveE [exp(λdt) | Ft−1 ]≤ exp(λ 22 vt−1).Next, applying Lemma 3.23, we have ∑t=1 vt−1 ≤ σ +∑Tt=1σtdt with σt ,σ = O(1). Setting β = σ andαt = σt , we have α = maxt∈[T ]αt = O(1), we may now apply Theorem 3.21 using β = O(1), α = O(1),x = O(log(1/δ )) to obtain the desired result.A tool which we will use repeatedly to prove the two lemmata above is the following result from [36].Lemma 3.24 ([36, Lemma 6]). Let f be λ strongly-convex. Consider running SGD (Algorithm 1) until timestep T with step size ηt = 1/(λ t). Then, for all t ≥ 3‖xt − x∗‖2 ≤ 2λ (t−2)(t−1)t−1∑i=2(i−1)〈 zˆi, xi− x∗ 〉+ ‖gˆt−1‖2λ 2(t−1) .353.4.1 Proof of Lemma 3.22Proof (of Lemma 3.22). By Lemma 3.14 with w = x∗ we haveT∑t=T/2( f (xt)− f (x∗)) ≤ 12T∑t=T/2ηt ‖gˆt‖2︸ ︷︷ ︸(a)+12ηT/2∥∥xT/2− x∗∥∥2︸ ︷︷ ︸(b)+T∑t=T/2〈 zˆt , xt − x∗ 〉.Observe that (a) is bounded by O(1) by bounding ‖gˆt‖2 by 4 using 1-Lipschitzness, that ‖zˆt‖ ≤ 1 almost surely,and that ηt = 1/t.Now, we bound (b). Applying Lemma 3.24 and recalling ηT/2 = T/2, we obtain∥∥xT/2− x∗∥∥2 ≤ T(T/2−2)(T/2−1) T/2−1∑t=2 (t−1)〈 zˆt , xt − x∗ 〉+∥∥gˆT/2−1∥∥2T/2−1 .Now, setting ζ = (a)+ ‖gˆt−1‖2(T/2−1) and ξt =T (t−1)(T/2−2)(T/2−1) completes the proof of Lemma 3.22. 3.4.2 Proof of Lemma 3.23Proof (of Lemma 3.23). Applying Lemma 3.24 and rearranging the sum on the first line, we haveT/2−1∑t=2ξ 2t ‖xt − x∗‖2 ≤ ξ 22 ‖x2− x∗‖2+T/2−1∑t=3ξ 2t(2(t−2)(t−1)t−1∑i=2(i−1)〈 zˆi, xi− x∗ 〉+ ‖gˆt−1‖2t−1)= ξ 22 ‖x2− x∗‖2+T/2−1∑t=3ξ 2t ‖gˆt−1‖2(t−1)︸ ︷︷ ︸:=s1+T/2−2∑i=2(i−1)(T/2−1∑t=i+1ξ 2t(t−2)(t−1))· 〈 zˆi, xi− x∗ 〉One may use 1-Lipschitz and 1 strong convexity to bound ‖x2− x∗‖2 by O(1). Using Lipschitzness and theassumption that ‖zˆt‖ ≤ 1 almost surely, and recalling that ξt =Θ(t/T ), we can bound s1 by O(1).Next, applying Lemma 3.24 and rearranging and splitting the sum on the first line below we have again wehaveT∑t=T/2‖xt − x∗‖2 ≤T∑t=T/22(t−2)(t−1)t−1∑i=2(i−1)〈 zˆi, xi− x∗ 〉+T∑t=T/2‖gˆt−1‖2t−1=T∑t=T/2‖gˆt−1‖2t−1︸ ︷︷ ︸:=s2+T/2−1∑i=2(i−1)(T∑t=T/22(t−2)(t−1))· 〈 zˆi, xi− x∗ 〉+T∑t=T/2(i−1)(T∑t=i+12(t−1)(t−2))· 〈 zˆi, xi− x∗ 〉.36Notice that s2 = O(1) by bounding ‖gˆt−1‖2 using Lipschitzness of f and the assumption that ‖zˆt‖ ≤ 1 almostsurely. Therefore we have,T/2−1∑t=2ξ 2t ‖xt − x∗‖2+T∑t=t/2‖xt − x∗‖2≤ s1+ s2+T/2−2∑i=2(i−1)(T/2−1∑t=i+1ξ 2t(t−2)(t−1))· 〈 zˆi, xi− x∗ 〉+T/2−1∑i=2(i−1)(T∑t=T/22(t−2)(t−1))· 〈 zˆi, xi− x∗ 〉+T∑t=T/2(i−1)(T∑t=i+12(t−1)(t−2))· 〈 zˆi, xi− x∗ 〉.We rewrite the right hand side of the above inequality asσ +T/2−1∑i=2σ˜i〈 zˆi, xi− x∗ 〉+T∑i=T/2σi〈 zˆi, xi− x∗ 〉where σ = s1+ s2, σi = (i−1)(∑Tt=i+1 2(t−1)(t−2))for i = T/2, . . . ,T andσ˜i :=(i−1)(∑T/2−1t=i+1ξ 2t(t−2)(t−1) +∑Tt=T/22(t−2)(t−1))for i = 2, . . . ,T/2−2,(i−1)(∑Tt=T/22(t−2)(t−1))for i = T/2−1.Note that σi = O(1) for all i = T/2, . . . ,T and σ = O(1) as well (recalling that s1 and s2 are O(1)). Next,using ξi = Θ(i/T ) one can verify that σ˜i = O(i/T ). Again, because ξi = Θ(i/T ), this means that we can writeσ˜i = σiξi for some σi = O(1), completing the proof of Lemma 3.23.3.5 High probability bound on a non-uniform averaging schemeIn this section, we prove that a non-uniform averaging scheme attains the optimal O(1/T ) rate with high proba-bility. Recall that we have already seen that the suffix average attains the optimal O(1/T ) with high probabilityin Section 3.4. The averaging scheme was first proposed and analyzed in expectation by Lacoste-Julien et al.[26]. The analysis of the final iterate, suffix-average, and this non-uniform averaging scheme can all be seen asapplications of the Generalized Freedman inequality, Theorem 1.11.Theorem 3.25. Let X ⊆ Rn be a convex set. Suppose that f :X → R is µ-strongly convex (with respect to‖·‖2) and L-Lipschitz. Assume that:(a) gt ∈ ∂ f (xt) for all t (with probability 1).(b) ‖zˆt‖ ≤ L (with probability 1).37Set ηt = 2µ(t+1) and γt =tT (T+1)/2 . Then, for any δ ∈ (0,1), with probability at least 1−δ ,f(T∑t=1γtxt)− f (x∗) ≤ O(L2 · log(1/δ )µ· 1T).3.5.1 Main idea of proof of Theorem 3.25The main idea of the proof is to follow the in-expectation analysis by Lacoste-Julien et al. [26], but keeptrack of the mean zero “noise” terms which appear due to the stochastic nature of the subgradient oracle. Inparticular, Lacoste-Julien et al. [26] repeatedly use the subgradient inequality for µ-strongly-convex functions(see Eq. (1.1)):f (xt)− f (x∗) ≤ 〈gt , xt − x∗ 〉− µ2 ‖xt − x∗‖22 ,where xt is the current iterate, x∗ is the minimizer, and gt ∈ ∂ f (xt). The subgradient oracle used by SGD pro-duces gˆt which is not necessarily a member of ∂ f (xt), and therefore the above inequality is not valid. However,since E [ gˆt ] ∈ ∂ f (xt), we may write gˆt = gt − zˆt , where E [ zˆt | Ft−1 ] = 0. Therefore, we obtain a “noisy”subgradient inequality:f (xt)− f (x∗)≤ 〈gt , xt − x∗ 〉− µ2 ‖xt − x∗‖22+ 〈 zˆt , xt − x∗ 〉. (3.8)Now, applying the analysis of Lacoste-Julien et al. [26] and replacing applications of the subgradient inequalitywith Eq. (3.8) we obtain the following inequality.Claim 3.26. Let ZT = ∑Tt=1 t〈 zˆt , xt − x∗ 〉 . Then,f(T∑t=1γtxt)− f (x∗) ≤ O(L2µT)+O(1T 2)ZT .Therefore, the main challenge lies in bounding ZT by O(T ) with high probability. Notice that ZT isthe sum of conditionally mean-zero increments, making it the value of a martingale at time T . The stan-dard Azuma inequality would require an almost sure bound of O(1/T ) on its total variance, denoted VT =O(∑Tt=1 t2 ‖xt − x∗‖22), in order to obtain the desired bound on ZT .On the other hand, the classic Freedman inequality would require a high probability bound of O(1/T ) on VT .The most obvious way to do this is come up with tail bounds on ‖xt − x∗‖2 directly and this is the approach takenby Rakhlin et al. [36], which led to the suboptimal O(log(log(T ))/T ) convergence rate for the suffix-averagingstrategy.Instead, we turn to the Generalized Freedman Inequality by Harvey et al. [15], which can help us derive thedesired high-probability bound if we are able to prove that VT satisfies some specific recursive structure with ZT– that is, VT ≤ O(T )ZT +O(T 2). The advantage of this approach is that, unlike the approach of applying theclassic Freedman inequality, we no longer require a tail bound on ‖xt − x∗‖2. Instead, we can achieve our goalby using elementary analysis. This results in an elegant proof of our main result using a technique which we38believe can be broadly applicable to other first order stochastic optimization procedures.3.5.2 High probability upper bound analysisAssuming Claim 3.26 holds, it remains to bound the quantity ZT = ∑Tt=1 t〈 zˆt , xt − x∗ 〉 with high probability.The strategy here will be to show that VT := L2∑Tt=1 t2 ‖xt − x∗‖2 (an upper bound on the sum of the squaredincrements of ZT ), satisfies a recursive property involving ZT again. In particular, we will show that VT isbounded by a linear transformation of ZT with probability one. Then, applying Theorem 3.21 givesLemma 3.27. Let ZT =∑Tt=1 t · 〈 zˆt , xt−x∗ 〉. Then for any δ ∈ (0,1), ZT ≤O(L2µ ·T log(1/δ )), with probabilityat least 1−δ .Lemma 3.27 and Claim 3.26 together prove Theorem 3.25. The proof of Claim 3.26 can be found inSubsection 3.5.3 and the proof of Lemma 3.27 can be found in Subsection 3.5.4.3.5.3 Proof of Claim 3.26The proof follows carefully the analysis of Lacoste-Julien et al. [26], but we must be careful with the noise termsas our goal is obtain a high probability bound.Proof (of Claim 3.26). We write zˆt = gt − gˆt . Since f is µ-strongly convex, we havef (xt)− f (x∗) ≤ 〈gt , xt − x∗ 〉− µ2 ‖xt − x∗‖22= 〈 gˆt , xt − x∗ 〉− µ2 ‖xt − x∗‖22+ 〈 zˆt , xt − x∗ 〉.The first two terms can be bounded as follows.〈 gˆt , xt − x∗ 〉− µ2 ‖xt − x∗‖22=1ηt〈 xt − yt+1, xt − x∗ 〉− µ2 ‖xt − x∗‖22=12ηt(‖xt − yt+1‖22+‖xt − x∗‖22−‖yt+1− x∗‖22)− µ2‖xt − x∗‖22≤ 12ηt(‖xt − yt+1‖22+‖xt − x∗‖22−‖xt+1− x∗‖22)− µ2‖xt − x∗‖22 .The first line uses the definition of Algorithm 1 and the last line uses a property of Euclidean projections: sincext+1 is the projected point ΠX (yt+1) and x∗ ∈X , we have ‖xt+1− x∗‖22 ≤ ‖yt+1− x∗‖22.It is convenient to scale by t in order to later obtain a telescoping sum. Using the definition of the gradient39step, i.e. xt − yt+1 = ηt gˆt , we havet ·(f (xt)− f (x∗)−〈 zˆt , xt − x∗ 〉)≤ t ‖ηt gˆt‖222ηt+ t( 12ηt− µ2)‖xt − x∗‖22−t2ηt‖xt+1− x∗‖22=t ‖gˆt‖22µ(t+1)+(µt(t+1)4− 2µt4)‖xt − x∗‖22−t(t+1)µ4‖xt+1− x∗‖22≤ (2L)2µ+µ4·(t(t−1)‖xt − x∗‖22− t(t+1)‖xt+1− x∗‖22).Now, summing over t, the right-hand side telescopes and we obtain ∑Tt=1 t · ( f (xt)− f (x∗)) is bounded above byT∑t=1t · 〈 zˆt , xt − x∗ 〉+ 4L2 ·Tµ.Dividing by T (T +1)/2 and applying Jensen’s inequality, we obtain thatf( T∑t=1γtxt)− f (x∗)≤T∑t=1γt ·(f (xt)− f (x∗))≤ 2T (T +1)T∑t=1t · 〈 zˆt , xt − x∗ 〉︸ ︷︷ ︸=ZT+8L2µ(T +1).3.5.4 Bounding ZTObserve that ZT is a sum of a martingale difference sequence. Define dt = t · 〈 zˆt , xt − x∗ 〉, vt−1 := t2 ‖xt − x∗‖,and VT = L2∑Tt=1 vt−1. Note that vt−1 is Ft−1-measurable. The next claim shows that vt−1 and dt satisfy theassumptions of Generalized Freedman’s inequality (Theorem 3.21).Claim 3.28. For all t and λ > 0, we have E [exp(λdt) | Ft−1 ]≤ exp(λ 22 L2 · vt−1).Proof. First, we can apply Cauchy-Schwarz to get that |t〈 zˆt , xt − x∗ 〉| ≤ t · ‖zˆt‖ · ‖xt − x∗‖ ≤ t ·L · ‖xt − x∗‖ be-cause ‖zˆt‖≤L a.s. Next, applying Hoeffding’s Lemma ( [30] - Lemma 2.6), we have E [exp(λ t〈 zˆt , xt − x∗ 〉) | Ft−1 ]≤exp(λ 22 L2 · t2 ‖xt − x∗‖2). To bound ZT , we will show that we can bound its sum of squared magnitudes (SSCM) by a linear combina-tion of the increments. This will allow us to use the Generalized Freedman Inequality (Theorem 3.21).Lemma 3.29. There exists non-negative constants α1, . . . ,αT such that maxi∈[T ] {αi} = O(L2µ ·T)and β =O(L4µ2 ·T 2)such that VT ≤ ∑Tt=1αtdt +β .Proof (of Lemma 3.27). By Claim 3.28, we have E [exp(λdt) | Ft−1 ] ≤ exp(λ 22 L2 · vt−1)for all λ > 0 andVT =∑Tt=1 L2 ·vt−1. By Lemma 3.29, we have VT ≤∑Tt=1 ·αtdt + ·β . Plugging α =O(L2µ ·T), β =O(L4µ2 ·T 2),and x = O(L2µ ·T log(1/δ ))into Theorem 3.21 proves the lemma. 40It remains to prove Lemma 3.29. To do so, we will need the following two lemmata, which are adapted from[36] to use the step sizes ηt = 2µ(t+1) . For completeness, we provide a proof in the supplementary material.Lemma 3.30 ([36] - Lemma 5). With probability 1, and for all t, ‖xt − x∗‖ ≤ 2Lµ .Lemma 3.31 ([36] - Lemma 6). For all t ≥ 3, there exists non-negative numbers a1(t), . . . ,at(t) with ai(t) =Θ(i3/t4) and b1(t), . . . ,bt(t) with bi(t) = Θ(i2/t4), such that with probability 1 ‖xt+1− x∗‖2 is bounded aboveby4µt∑i=3ai(t)〈 zˆi, xi− x∗ 〉+ 4µ2t∑i=3bi(t)‖gˆt‖2 .Remark 3.32. Lemma 3.30 and Lemma 3.31 are true regardless of the assumption we place on zˆt .Proof (of Lemma 3.29). Recall ‖gˆi‖≤ 2L because f is L-Lipschitz and ‖zˆi‖≤ L almost surely. By Lemma 3.30and Lemma 3.31, we bound ∑Tt=1 vt−1 and then multiply through by L2 to obtain a bound on VT :T∑t=1vt−1 =T∑t=1t2 · ‖xt − x∗‖2≤ 56L2µ2+T∑t=4t2(4µt−1∑i=3ai(t−1)〈 zˆi, xi− x∗ 〉)+4µ2T∑t=4(t−1∑i=3bi(t−1)‖gˆi‖2)≤ 56L2µ2+T∑t=4t2(4µt−1∑i=3ai(t−1)〈 zˆi, xi− x∗ 〉)+4(2L)2µ2T∑t=4(t−1∑i=3bi(t−1))=4µT∑t=4t2(t−1∑i=3ai(t−1)〈 zˆi, xi− x∗ 〉)+16 ·L+2µ2T∑t=4t2(t−1∑i=3bi(t−1))+56L2µ2=T−1∑i=34µ(T∑t=i+1t2 · ai(t−1)i)︸ ︷︷ ︸:=αi·i〈 zˆi, xi− x∗ 〉+ 16 ·L2µ2T∑t=4t2(t−1∑i=3bi(t−1))+56L2µ2︸ ︷︷ ︸:=βDefine α1,α2,αT = 0. We have VT ≤ ∑Ti=1αi · i · 〈 zˆi, xi− x∗ 〉+β . It remains to show max{αi} = O(Tµ)andβ = O(L2µ2 T2)(multiplying through by L2 yields the bound on VT ). To bound max{αi}, observe that fori ∈ {3, . . . ,T −1} ,T∑t=i+1t2 · ai(t−1)i=T∑t=i+1t2O(i2t4)=T∑t=i+1t2O(1t2)= O(T − i) .41To bound β , observeT∑t=4t2(t−1∑i=3bi(t−1))=T∑t=4t2t−1∑i=3O(i2t4)=T∑t=4t2t−1∑i=3O(1t2)=T∑t=4O(t) = O(T 2).3.5.5 Missing proofs from Subsection 3.5.4Both of the proofs in this section are slight modifications of the proofs found by Rakhlin et al. [36].Proof (of Lemma 3.30). Due to strong convexity and the fact that f (xt)− f (x∗)≥ 0, we haveL‖xt − x∗‖ ≥ ‖gt‖‖xt − x∗‖≥ 〈gt , xt − x∗ 〉≥ µ2‖xt − x∗‖2 ,where we used L-Lipschitzness of f to bound ‖gt‖ by L. Proof (of Lemma 3.31). The definition of strong convexity yields〈gt , xt − x∗ 〉 ≥ f (xt)− f (x∗)+ µ2 ‖xt − x∗‖2 .Strong convexity and the fact that 0 ∈ ∂ f (x∗) impliesf (xt)− f (x∗)≥ µ2 ‖xt − x∗‖2 .Next, recall that for any x∈X , and for any z, we have ‖ΠX (z)− x‖≤ ‖z− x‖ . Lastly, recall ηt = 2µ(t+1) .Usingthese, we have‖xt+1− x∗‖2= ‖ΠX (xt −ηt gˆt)− x∗‖2 ≤ ‖xt −ηt gˆt − x∗‖2= ‖xt − x∗‖2−2ηt〈 gˆt , xt − x∗ 〉+η2t ‖gˆt‖2= ‖xt − x∗‖2−2ηt〈gt , xt − x∗ 〉+2ηt〈 zˆt , xt − x∗ 〉+η2t ‖gˆt‖2≤ ‖xt − x∗‖2−2ηt ( f (xt)− f (x∗))−ηtµ ‖xt − x∗‖2+2ηt〈 zˆt , xt − x∗ 〉+η2t ‖gˆt‖2≤ (1−2ηtµ)‖xt − x∗‖2+2ηt〈 zˆt , xt − x∗ 〉+η2t ‖gˆt‖2=(1− 4t+1)‖xt − x∗‖2+ 4µ(t+1)〈 zˆt , xt − x∗ 〉+ 4µ2(t+1)2‖gˆt‖2 . (3.9)42Repeatedly applying Eq. (3.9) until t = 4, yields the following upper bound on ‖xt+1− x∗‖24µt∑i=4[1i+1t∏j=i+1(1− 4j+1)]· 〈 zˆi, xi− x∗ 〉+ 4µ2t∑i=4[1(i+1)2t∏j=i+1(1− 4j+1)]· ‖gˆt‖ .Observing thatt∏j=i+1(1− 4j+1)=t∏j=i+1j−3j+1=(i−2) · (i−1) · i · (i+1)(t−2) · (t−1) · t · (t+1) ,proves the lemma by taking ai(t) = 1i+1 · (i−2)·(i−1)·i·(i+1)(t−2)·(t−1)·t·(t+1) and bi(t) = 1(i+1)2 ·(i−2)·(i−1)·i·(i+1)(t−2)·(t−1)·t·(t+1) 43Chapter 4Probabilistic Tools4.1 Proof of Theorem 1.11 and corollariesIn this section we prove Theorem 1.11 and derive some corollaries. We restate Theorem 1.11 here for conve-nience.Theorem 1.11. Let {di,Fi}ni=1 be a martingale difference sequence. Suppose vi−1, for i ∈ [n], are positiveandFi−1-measurable random variables such that E [exp(λdi) | Fi−1 ]≤ exp(λ 22 vi−1)for all i ∈ [n], λ > 0. LetSt = ∑ti=1 di and Vt = ∑ti=1 vi−1. Let αi ≥ 0 and set α = maxi∈[n]αi. ThenPr[n⋃t=1{St ≥ x and Vt ≤t∑i=1αidi+β} ]≤ exp(− x4α+8β/x)∀x,β > 0.The proof of Theorem 1.11 is inspired by a standard proof of Freedman’s inequality. The standard proofbegins with the observation that Mt(λ ) := exp(λSt − λ 22 Vt)defines a supermartingale for any λ > 0 (recallthat St is the martingale at time t and Vt is the sum of squared conditional subgaussian norms (SSCSN) attime n). Then, noting that {Sn ≥ x and Vn ≤ y} ⊂{λSn− λ 22 Vn ≥ λx− λ22 y}for any λ > 0 allows one toapply the exponentiated Markov inequality (Lemma A.1) to the larger event to obtain Pr [Sn ≥ x,Vn ≤ y ] ≤exp(−λx+ λ 22 y)E [Mn ] . Since (Mt)t∈N is a supermartingale with M0 = 1, minimizing over λ yields a sim-plified version of Freedman’s inequality. To obtain Freedman’s inequality in full generality, one may apply amodification of the above argument involving the stopping time τ = min{ t : St ≥ x,Vt ≤ y } .In our setting, we also aim to design a supermartingale whose role is similar to the supermartingale Mt(λ )plays in the proof above. However, due to the entanglement between our martingale and its SSCSN processin the event whose probability we aim to bound (i.e. the chicken and egg phenomenon), some special care isrequired in order to derive such a supermartingale. Indeed, as we will see in the following proof, we will needto carefully balance the parameters c and λ˜ .Proof (of Theorem 1.11). Suppose 0 ≤ λ < 1/(2α); the actually choice of λ will be optimized later. Define44c = c(λ ,α) as in Claim 4.2. Let λ˜ = λ + cλ 2α . Define U0 := 1 and for t ∈ [n], defineUt(λ ) := exp(t∑i=1(λ + cλ 2αi)di−t∑i=1λ˜ 22vi−1).Claim 4.1. Ut(λ ) is a supermartingale w.r.t.Ft .Explanation of the role of Ut(λ ) and why it differs from Mt(λ ). Notice that the supermartingale Ut(λ )differs from Mt(λ ). The scaling on the increments di in the definition ofUt(λ ) are specifically designed with thegoal of applying the exponentiated Markov inequality (Lemma A.1) to expose the expectation of a nonnegativesupermartingale with bounded initial value. This was a key step in the proof of Freedman’s inequality describedabove. In our setting, recalling that St = ∑ti=1 di, we have{n∑i=1(λ + cλ 2αi)di− cλ 2Vt ≥ λx− cλ 2β}︸ ︷︷ ︸:=E⊃{St ≥ x,Vt ≤n∑i=1αidi+β}︸ ︷︷ ︸:=G,where the scaling on the increments di in the event E matches the scaling in Ut(λ ) and the event G is essen-tially the event we would like to analyze. Notice that E is an event which we may apply the exponentiatedMarkov inequality to. Ideally, an application of Lemma A.1 on the event E would yield an upper bound ofexp(−λx+cλ 2β ) times the expectation of a nonnegative supermartingale with bounded initial value as was thecase in the standard proof outlined above. Instead, Lemma A.1 yields the expectation of the following processexp(An− cλ 2Vn), where An = ∑ni=1(λ + cλ 2αi)di, and it is unclear whether this is a supermartingale. Now,according to Claim 4.1 exp(An− λ˜ 22 Vn)is a supermartingale. In order to enforce that Lemma A.1 yields anupper bound on the probability of E involving the expectation of a supermartingale, we will enforce cλ 2 = λ˜22so that the expectation of the random process which results from applying Lemma A.1 on the event E is equalto E [Un(λ ) ] . Formally,Pr [G ] ≤ Pr [E ] ≤ exp(−λx− cλ 2β)E[exp(An− cλ 2Vn)] (by Lemma A.1)= exp(−λx− cλ 2β)E [Un(λ ) ] (by choice of c)≤ exp(−λx− cλ 2β) (Ut(λ ) is a supermartingale).Proof (of Claim 4.1). For all t ∈ [n]:E [Ut(λ ) | Ft−1 ] =Ut−1(λ )exp(− λ˜22vt−1)E[exp((λ + cλ 2αt)dt) | Ft−1 ]≤Ut−1(λ )exp(− λ˜22vt−1)exp((λ + cλ 2αt)22vt−1)≤Ut−1(λ )exp(− λ˜22vt−1)exp(λ˜ 22vt−1)=Ut−1(λ ),45where the second line follows from the assumption that E [exp(λdt) | Ft−1 ]≤ exp(λ 22 vt−1)for all λ > 0 andthe third line is because λ + cλ 2αt ≤ λ˜ (since c≥ 0 and αt ≤ α). We conclude that Ut(λ ) is a supermartingalew.r.t.Ft . Define the stopping time T = min{ t : St ≥ x and Vt ≤ ∑ti=1αidi+β } with the convention that min /0 = ∞.Since Ut is a supermartingale w.r.t.Ft , then UT∧t is a supermartingale w.r.t.Ft ([25, Theorem 10.15]). Recallthat ST∧n = ∑T∧ni=1 di.Pr[n⋃t=1{St ≥ x and Vt ≤t∑i=1αidi+β}]= Pr[ST∧n ≥ x and VT∧n ≤T∧n∑i=1αidi+β]= PrλST∧n ≥ λx and cλ 2VT∧n ≤ cλ 2 T∧n∑i=1 αidi+ cλ 2β︸ ︷︷ ︸:=A(subtracting inequalities from A ) ≤ Pr[T∧n∑i=1(λ + cλ 2αi)di− cλ 2VT∧n ≥ λx− cλ 2β](by Lemma A.1) ≤ E[exp(T∧n∑i=1(λ + cλ 2αi)di− cλ 2VT∧n)]· exp(−λx+ cλ 2β ).Recall that c was chosen (via Claim 4.2) so that cλ 2 = (λ + cλ 2α)2/2 = λ˜ 2/2. This selection of c is crucial toconnect the result of the application of Lemma A.1 above to the supermartingale Ut(λ ). Hence,E[exp(T∧n∑i=1(λ + cλ 2αi)di− cλ 2VT∧n)]= E[exp(T∧n∑i=1(λ + cλ 2αi)di− λ˜22VT∧n)]= E [UT∧n(λ ) ] ≤ 1,where the inequality is by the optional stopping theorem for bounded stopping times ([25, Theorem 10.11]).Since λ < 1/(2α) was arbitrary, we conclude thatPr[n⋃t=1{St ≥ x and Vt ≤t∑i=1αidi+β}]≤ exp(−λx+ cλ 2β )≤ exp(−λx+2λ 2β ),46where the inequality is because c≤ 2. Now, we can pick λ = 12α+4β/x < 12α to conclude thatPr[n⋃t=1{St ≥ x and Vt ≤t∑i=1αidi+β}]≤ exp(−λ (x−2λβ ))≤ exp(−λ(x− 2β2α+4β/x))≤ exp(−λ(x− 2β4β/x))= exp(−λx2)= exp(− x4α+8β/x).Claim 4.2. Let α ≥ 0 and λ ∈ [0,1/2α). Then there exists c = c(λ ,α) ∈ [0,2] such that 2cλ 2 = (λ + cλ 2α)2.Proof. If λ = 0 or α = 0 then the claim is trivial (just take c = 1/2). So assume α,λ > 0.The equality 2cλ 2 = (λ + cλ 2α)2 holds if and only if p(c) := α2λ 2c2+(2λα−2)c+1 = 0. The discrim-inant of p is (2λα − 2)2− 4α2λ 2 = 4− 8λα . Since λα ≤ 1/2, the discriminant of p is non-negative so theroots of p are real. One root of p is located atc =2−2αλ −√(2αλ −2)2−4λ 2α22λ 2α2=1−αλ −√1−2αλα2λ 2.Set γ = αλ , and observe that 2γ ∈ [0,1]. Using the numeric inequality √1− x ≥ 1− x/2− x2/2 valid for allx≤ 1, we havec =1− γ−√1−2γγ2≤ 1− γ− (1− γ−2γ2)γ2= 2.On the other hand, using the numeric inequality√1− x≤ 1− x/2− x2/8 valid for all x ∈ [0,1], we havec =1− γ−√1−2γγ2≥ 1− γ− (1− γ− γ2/2)γ2=12≥ 0.4.1.1 Corollaries of Theorem 1.11In this thesis, we often deal with martingales, Mn, where the sum of squared conditional magnitudes (SSCM) ofthe martingale is bounded by a linear transformation of the martingale, with high probability (which is what weoften refer to as the “chicken and egg” phenomenon — the bound on the SSCM of Mn involves Mn itself). Trans-forming these entangled high probability bounds on the SSCM into high probability bounds on the martingaleitself are easy consequences of our Generalized Freedman inequality (Theorem 1.11).Lemma 4.3. Let {di,Fi}ni=1 be a martingale difference sequence. Let vi−1 be a Fi−1 measurable randomvariable such that E [exp(λdi) | Fi−1 ] ≤ exp(λ 22 vi−1)for all λ > 0 and for all i ∈ [n]. Define Sn = ∑ni=1 di47and define Vn = ∑ni=1 vi−1. Suppose that there exists α1, . . . ,αn ≥ 0 and R(δ ) > 0 (for δ ∈ (0,1)) such thatPr [Vn ≤ ∑ni=1αidi+R(δ ) ]≥ 1−δ . Let α = maxi∈[n]αi. Then,Pr [Sn ≥ x ]≤ δ + exp(− x24αx+8R(δ ))∀x> 0.Proof. Fix δ ∈ (0,1). Define the events E (x) = {Sn ≥ x} and G = {Vn ≤ ∑ni=1αidi+R(δ )}. ThenPr [Sn ≥ x ] = Pr [E (x)∧G ] + Pr [E (x)∧G c ]≤ Pr [E (x)∧G ]+Pr [G c ]︸ ︷︷ ︸≤δ≤ exp(− x24αx+8R(δ ))+δ ,where the final inequality is due to applying Theorem 1.11 to Pr [E (x)∧G ]. In this thesis, we use Lemma 4.3 via the following two corollaries. The first Corollary can be proven by usingthe original Freedman’s inequality.Corollary 4.4. Let {Ft}Tt=1 be a filtration and suppose that at are Ft-measurable random vectors and bt areFt−1-measurable random vectors. Further, suppose that1. ‖at‖ ≤ 1 almost surely and E [at | Ft−1 ] = 0; and2. ∑Tt=1 ‖bt‖2 ≤ R log(1/δ ) with probability at least 1−O(δ ).Define dt = 〈at , bt 〉. Then ∑Tt=1 dt ≤ O(√R log(1/δ ))with probability at least 1−O(δ ).Proof. Since ‖at‖ ≤ 1, by Cauchy-Schwarz we have that |dt | ≤ ‖bt‖. Therefore, E[exp(λdt) | Ft−1 ] ≤exp(λ 22 ‖bt‖2)for all λ by Lemma A.5. Next, applying Lemma 4.3 with dt = 〈at , bt 〉 and vt−1 = ‖bt‖2, αi = 0for all i, and R(δ ) = R log(1/δ ) yieldsPr[T∑t=1dt ≥ x]≤ δ + exp(− x28R log(1/δ )).The last term is at most δ by taking x =√8R log(1/δ ). Corollary 4.5. Let {Ft}Tt=1 be a filtration and suppose that at are Ft-measurable random vectors and bt areFt−1-measurable random vectors. Define dt = 〈at , bt 〉. Assume that ‖at‖≤ 1 almost surely and E [at | Ft−1 ] =0. Furthermore, suppose that there exists R> 0 and non-negative values {αt}T−1t=1 where max{αt}T−1t=1 =O(√R),such that for every δ sufficiently small, with probability at least 1−O(δ ), we have ∑Tt=1 ‖bt‖2 ≤ ∑T−1t=1 αtdt +R log(1/δ ). Then ∑Tt=1 dt ≤ O(√R log(1/δ ))with probability at least 1−δ .Proof. We prove only the first case, the second case can be proved by bounding√log(1/δ ) by log(1/δ ) andusing the proof of the first case.Since ‖at‖≤ 1, by Cauchy-Schwarz we have that |dt | ≤ ‖bt‖. Therefore, E[exp(λdt) | Ft−1 ]≤ exp(λ 22 ‖bt‖2 )for all λ by Lemma A.5. Next, applying Lemma 4.3 with dt = 〈 at , bt 〉 and vt−1 = ‖bt‖2, with αT = 0, and48R(δ ) = R log(1/δ ) yieldsPr[T∑t=1dt ≥ x]≤ δ + exp(− x24(maxT−1t=1 {αt})x+8R log(1/δ )). (4.1)Recall that maxT−1t=1 {αt} = O(√R). Thus, for some x = Θ(√R log(1/δ )), the last term in (4.1) is at most δ .Replacing δ with δ/2 completes the proof. 4.2 Proof of Theorem 1.19Theorem 1.19. Let (Xt)Tt=1 be a stochastic process and let (Ft)Tt=1 be a filtration such that Xt isFt measurableand Xt is non-negative almost surely. Let αt ∈ [0,1) and βt ,γt ≥ 0 for every t. Assume that E [exp(λX1) ] ≤exp(λK) for λ ∈ (0,1/K] where K = max1≤t≤T(2γt1−αt ,2β 2t1−αt). Let wˆt be a mean-zero random variable condi-tioned onFt such that |wˆt | ≤ 1 almost surely for every t. Suppose that Xt+1 ≤ αtXt +βtwˆt√Xt + γt for every t.Then, the following hold.• For every t, Pr [Xt ≥ K log(1/δ ) ]≤ eδ .• More generally, if σ1, . . . ,σT ≥ 0, then Pr[∑Tt=1σtXt ≥ K log(1/δ )∑Tt=1σt]≤ eδ .Proof (of Theorem 1.19).We begin by deriving a recursive MGF bound on Xt .Claim 4.6. Suppose 0≤ λ ≤min1≤t≤T(1−αt2β 2t). Then for every t,E [exp(λXt+1) ] ≤ exp(λγt)E[exp(λXt(1+αt2))].Proof. Since Xt is non-negative almost surely, we may define the random variable X = βtwˆt√Xt . Since |wˆt | ≤ 1almost surely and Xt is Ft-measurable, E[exp(λ 2X2) | Ft ] ≤ exp(λ 2β 2t Xt) for all λ . Since E [ wˆt | Ft ] = 0we may apply Claim A.6 with c2 = β 2t Xt to obtainE[exp(λβtwˆt√Xt) | Ft]= E [exp(λX) | Ft ] ≤ exp(λ 2β 2t Xt). (4.2)Hence,E [exp(λXt+1) ] ≤ E[exp(λαtXt +λβtwˆt√Xt +λγt)](by assumption)= E[exp(λαtXt +λγt)E[exp(λβtwˆt√Xt) | Ft ]]≤ E[exp(λαtXt +λ 2β 2t Xt +λγt)] (by Eq. (4.2))= E[exp(λXt(αt +λβ 2t)+λγt)]≤ E[exp(λγt +λXt(1+αt2))] (because λ ≤ 1−αt2β 2t).Next, we prove an MGF bound on Xt .49Claim 4.7. For every t and for all 0≤ λ ≤ 1/K, E [exp(λXt) ]≤ exp(λK).Proof. Let λ ≤ 1/K. We proceed by induction over t. The base case holds by assumption. Assume thatE [exp(λXt) ]≤ exp(λK). Now, consider the MGF of Xt+1:E [exp(λXt+1) ] ≤ E[exp(λγt +λXt(1+αt2))](by Claim 4.6)≤ exp(λγt +λK(1+αt2)),where the first inequality is valid because λ ≤ 1/K ≤ min1≤t≤T(1−αt2β 2t)and the second inequality follows be-cause (1+αt)/2 < 1 and so we can use the induction hypothesis since λ (1+αt)/2 < λ ≤ 1/K. Furthermore,the definition of K ensuresK ≥ 2γt1−αt =γt1− (1+αt2 ) ,which shows that γt +K(1+αt2)≤ K. Hence,E [exp(λXt+1) ] ≤ exp(λK) ,as desired. Now we are ready to complete the proof of both claims in Theorem 1.19. The first claim in Theorem 1.19follows by observing our MGF bound on Xt and then applying the transition from MGF bounds to tail boundsgiven by Claim A.7 (with c = 1 and C = K).Next, we prove the second claim in Theorem 1.19. Claim 4.7 gives that for every t and for all λ ≤ 1/(σtK),we have E [exp(λσtXt) ]≤ exp(λσtK). Hence, we can combine these MGF bounds using Lemma A.4 to obtainE[exp(λ ∑Tt=1σtXt)] ≤ exp(λK∑Tt=1σt) for all λ ≤ (K∑Tt=1σt)−1. With this MGF bound in hand, we mayapply the transition from MGF bounds to tail bounds given by Claim A.7 to complete the proof of the secondclaim in Theorem 1.19. 50Chapter 5Infinite Dimensional and Probabilistic LowerBounds5.1 Functions attaining large error infinitely oftenIn order to achieve large error for the T iterate, Theorem 1.12 constructs a strongly convex function parameter-ized by T . (Similarly, Theorem 1.14 constructs a Lipschitz function parameterized by T .) It is not possible fora single function to achieve error ω(1/T ) for every T ≥ 1 in the strongly-convex case (or ω(1/√T ) for everyT ≥ 1 in the Lipschitz case). The reason is that this would contradict the fact that suffix averaging achieveserror O(1/T ) in the strongly-convex case (and that the average over all iterates achieves error O(1/√T ) in theLipschitz case). Nevertheless, for every function g(T ) = o(log(T )/T ) it possible to construct a strongly convexfunction which achieves error C ·g(T ), for every C> 0 for infinitely many T . (A similar statement is true for theLipschitz case.) In the remainder of this section, we use `2 to denote the space of square-summable sequencesin RN.Theorem 5.1. For every non-negative g(T ) = o(log(T )/T ), and for any c > 0, there exists a convex functionf : X → R where X ⊂ `2, such that f is (3/c)-Lipschitz and (1/c)-strongly convex, infx∈X f (x) = 0 andsatisfies the following. Suppose that Algorithm 1 is executed from the initial point x1 = 0 with step sizes ηt = c/t.Then,limsupT→∞f (xT )g(T )= +∞.Theorem 5.2. For every non-negative g(T ) = o(log(T )/√T)and for every c> 0, there exists a convex functionf :X →R whereX ⊂ `2, such that f is (1/c)-Lipschitz, infx∈X f (x) = 0 and satisfies the following. Supposethat Algorithm 1 is executed from the initial point x1 = 0 with step sizes ηt = c/√t. Then,limsupT→∞f (xT )g(T )= +∞.Remark 5.3. We provide the proof of Theorem 5.1 in Sub-subsection 5.1.1. The proof of Theorem 5.2 is omitteddue to its similarity with the proof of Theorem 5.1. We prove Theorem 5.1 in the setting where c = 1. The resultfollows in full generality as a corollary of the c = 1 case and an analogous statement to Lemma 2.1 for Hilbert51spaces.Since we are now working with infinite dimensional functions, rigour requires us to state the definition ofthe subdifferential of a convex function applicable to functions defined on a Hilbert space E.Definition 5.4 ([5, Definition 2.30]). Let E be a Hilbert space and let f be a proper convex function defined onE. Then, g∈ E∗ (the dual Hilbert space of E) is a subgradient of f at x if, for all y∈ E, f (y)≥ f (x)+〈y−x, g〉.The subdifferential of f at x, denoted ∂ f (x), is the collection of subgradients of f at x.The main tool we use to prove Theorem 5.1 and Theorem 5.2 is the following natural result. In a nutshell,Lemma 5.5 states that running Algorithm 1 on an infinite sum of convex functions is equivalent to running aninstance of Algorithm 1 for each summand in parallel. While the statement of the following result is fairlyintuitive, the proof of Lemma 5.5 is rather technical. Therefore, we defer its proof to Subsection 5.1.2 and focuson using Lemma 5.5 to prove Theorem 5.1 and Theorem 5.2.Lemma 5.5. Consider a family of non-negative, convex functions, { fi}∞i=1, where fi : RTi → R. Let Xi ⊆ RTibe a closed and convex set such that Xi ⊆BTi(0,R), where BTi(0,R) is the Euclidean ball of radius R in RTi .Assume that fi is bounded by M and L Lipschitz onXi for every i. Define f :∏∞i=1RTi → R andX asf(x(1),x(2), . . .)=∞∑i=11C2ifi(Cix(i))and X =∞∏i=1XiCi, (5.1)where x(i) ∈ RTi and ∑∞i=1 1Ci ≤ 1, with Ci ∈ [1,∞). Then, the following hold:1. f (x) is well-defined for every x ∈X (i.e. limn→∞∑ni=1 1C2i fi(Cix(i)) exists for all x ∈X ).2. f is convex.3. If fi is α strongly convex onXi for every i, then f is α strongly convex onX .4. If fi is subdifferentiable onXi (∂ fi(x) 6= /0 for every x ∈Xi), then f is subdifferentiable onX . Therefore,if one could execute Algorithm 1 individually for each fi, then one can execute Algorithm 1 on the functionf .5. f is L-Lipschitz onX . That is, for every x ∈X and g ∈ ∂ f (x), ‖g‖ ≤ L.6. Let σi be a map such that for every x∈Xi, σi(x)∈ ∂ fi(x). Let x(i)t denote the t-th iterate of Algorithm 1 onthe function fi using the feasible regionXi, step sizes ηt , initial point x(i)1 and the subgradient oracle σi.Then, there is a map σ such that for every x ∈X , σ(x) ∈ ∂ f (x) and the t-th iterate of gradient descenton the function f using the feasible region X , step sizes ηt , initial point x1 = (x(1)1 /C1,x(2)1 /C2, . . .) andthe subgradient oracle σ is given byxt =(x(1)tC1,x(2)tC2, . . .).How Lemma 5.5 will be used. Lemma 5.5 allows one to carefully design a single infinite dimensional func-tion from many finite dimensional functions (see Eq. (5.1)) while maintaining crucial properties such as con-vexity, Lipschitzness, and boundedness. Importantly, running Algorithm 1 on this infinite dimensional functionis “equivalent” to running an instance of Algorithm 1 for each finite dimensional function in parallel: The valueof the t-th iterate of the infinite dimensional instance can be obtained by a weighted sum of the values of t-th52iterates of each of the finite dimensional instances. Therefore, if we use fi = fTi where fTi are the Ti-dimensionalfunctions from Section 2.1 which exhibit Ω(log(Ti)/Ti) error after Ti iterations of Algorithm 1, then we couldenforce error Ω(log(Ti)/Ti) at iteration Ti as long as each fi were non-negative. Letting limi→∞Ti = ∞ and ig-noring the scaling factors 1/Ci, we have that limsupT→∞f (xT )log(T )/T = Ω(1). The presence of the scaling factors1/Ci, which are necessary for maintaining Lipschitz-ness, weaken the result to limsupT→∞f (xT )g(T ) =+∞ for anyg(T ) = o(log(T )/T ).5.1.1 Proof of Theorem 5.1We will prove Lemma 5.6, which is quite similar to Theorem 5.1, except that it appears to have a strongerhypothesis. However, Lemma 5.7 implies that the hypothesis is actually not stronger: For each g= o(log(T )/T )we also have g = o(log(T )/(T ·h(T ))) for some function h such that limT→∞ h(T ) = +∞. Thus Theorem 5.1follows from Lemma 5.6.Lemma 5.6. For every non-negative g(T ) = o(log(T )/(T ·h(T ))) where limT→∞ h(T ) = +∞, there exists aconvex function f :X → R where X ⊂ `2 is convex and f is 3-Lipschitz, 1-strongly convex, infx∈X f (x) = 0and satisfies the following. Suppose that Algorithm 1 is executed from the initial point x1 = 0 with step sizesηt = 1/t. Then,limsupT→∞f (xT )g(T )= +∞.Lemma 5.7. Suppose g(T ) is a non-negative function such that g(T ) = o(log(T )/T ). Then we may writeg(T ) = o(log(T )/(T ·h(T ))) for some h(T ) satisfying limT→∞ h(T ) = +∞.Proof. Let h(T ) =√log(T )/Tg(T ) . Then, limT→∞ h(T ) = +∞ because g = o(log(T )/T ) . We havelimT→∞[g(T )log(T )/(T ·h(T ))]= limT→∞[√g(T )log(T )/T]= 0,because g(T ) = o(log(T )/T ) . Proof (of Lemma 5.6).Showing that limsupT→∞f (xT )g(T ) =+∞ is equivalent to showing the following:∀M > 0, ∀N ∈ N, ∃T ≥ N s.t. f (xT )>Mg(T ). (5.2)We would like to apply Lemma 5.5, and so we must define functions fi which satisfy the required properties.Let Ci = 2i. Let Ti ≥ i be such that∀t ≥ Ti ≥ i : g(t)≤ 14C2i(log tt ·h(t)), (5.3)which is possible because g(T )= o(log(t)/(t ·h(t))). Our functions fi are defined mainly using the Ti-dimensionalversion of the function defined in Section 2.1, which we will denote by fTi and provides the Ω(log(T )/T ) lowerbound on the error of Algorithm 1. Recall some important properties of the function fTi which were derived inSection 2.1. LetBT (0,R) be the Euclidean ball of radius R in RT .53• fTi is 3-Lipschitz and 1-strongly convex overBTi(0,1),• There exists a subgradient oracle such that running Algorithm 1 on fTi using this oracle, feasible regionBTi(0,1), and step sizes ηt = 1/t satisfies fTi(xTi+1)≥ logTi4Ti (this is the content of Theorem 1.12).Defining the functions fi. Using fTi as the definition of fi in an application of Lemma 5.5 is problematicbecause fTi is not guaranteed to be non-negative. As a consequence, we will not be able to assert that the valueof the Ti-th iterate of Algorithm 1 on f is Ω(log(Ti)C2i Ti), even though the proof1 Theorem 1.12 shows that thistrue for the Ti-th iterate of Algorithm 1 on fTi and Lemma 5.5 guarantees that the value of the t-h iterate forf is a scaled sum of the values of the t-th iterates of the fTi’s. Instead, we augment the definition of fTi sothat the function remains Lipschitz, strongly convex, attains the lower bound from Theorem 1.12, and is alsonon-negative. Note that simply taking the max of 0 and fTi is not a feasible approach since the resulting functionis not strongly convex.Let fi :BTi(0,1)→ R be defined as fi(x) = max{ fTi(x), 12 ‖x‖2}. It is straightforward to check that fi is 3-Lipschitz, bounded by 3 onBTi(0,1) and also 1-strongly convex (these properties follow easily from the fact thatfTi is 3-Lipschitz and 1 strongly convex onBTi(0,1)). Also, because fTi(0) = 0, we see that infx∈BTi (0,1) fi(x) =0. Finally, fi is subdifferentiable on Xi, and there is a subgradient oracle for which fi can be made to achievethe same lower bound as fTi achieves in Theorem 1.12. This is formalized in the following claim, whose proofwe defer to Subsection 5.1.2.Claim 5.8. There exists a subgradient oracle for the function fi such that if x(i)1 ,x(i)2 , . . . are the iterates producedby running Algorithm 1 with the function fi, the feasible region BTi(0,1), the step sizes ηt = 1/t, and initialpoint x(i)1 = 0 then,fi(x(i)Ti+1) ≥logTi4Ti. (5.4)Defining the function f . Recall that Ci = 2i. We define f : ∏∞i=1BTi(0,1)/Ci → R as follows. Let x =(x(1),x(2), . . .) be such that x(i) ∈BTi(0,1)/Ci. Then, definef(x(1),x(2), . . .):=∞∑i=11C2ifi(Cix(i)).Note that f is non-negative and f (0) = 0. Therefore, infx∈X f (x) = 0. Let σi be the subgradient oracle for fiwhose existence is guaranteed by Claim 5.8 and let x(i)t denote the t-th iterate of Algorithm 1 on fi using thesubgradient oracle σi, initial point x(i)1 = 0, and step size ηt = 1/t. Then, using Lemma 5.5, we get the following:• f is well defined and subdifferentiable overX ,• f is 3-Lipschitz overX ,• f is 1-strongly convex overX ,1The statement of Theorem 1.12 states that fTi(xTi+1)− infx∈X fTi(x) = Ω(logTiTi), however the proof argues that fTi(xTi+1) =Ω(logTiTi)and shows that infxX fTi(x)≤ 054• There exists a subgradient oracle, σ , for f overX such that the t-th iterate, xt , of Algorithm 1 on f usingthe subgradient oracle σ , initial point x1 = 0, and step size ηt = 1/t satisfies,xt =(x(1)tC1,x(2)tC2, . . .). (5.5)Showing Eq. (5.2) holds. Let M > 0 and let N ∈ N. The following is true because limT→∞ h(T ) = ∞.∃n s.t., ∀T ≥ n, h(T )>M. (5.6)Consider N′ = max{n,N}. Then, we have the following:f(xTN′+1)=∞∑i=11C2ifi(x(i)TN′+1)(by definition of f and Eq. (5.5))≥ 1C2N′fN′(x(N′)TN′+1)(each fi is non-negative)≥ 14C2N′logTN′TN′(by Eq. (5.4))≥ g(TN′)h(TN′) (by Eq. (5.3))> M ·g(TN′) (because TN′ ≥ N′ ≥ n and using Eq. (5.6)).Hence, we’ve shown for every M > 0 and for every N ∈ N, there exists t ≥ N (namely, TN′ ≥ N′ ≥ N) such thatf (xt)>M ·g(t). This demonstrates that Eq. (5.2) holds and therefore the proof is complete. 5.1.2 Proof of Lemma 5.5Throughout this subsection, we work under the assumptions of Lemma 5.5. That is, we assume we have afamily of non-negative convex functions { fi}∞i=1 such that fi : RTi → R and closed convex sets Xi ⊂ RTi suchXi is contained in some Euclidean ball of radius R, denotedBTi(0,R). We setX =∏∞i=1XiCiwhere ∑∞i=1 1Ci ≤ 1and Ci ∈ [1,∞) and define f :∏∞i=1RTi →R as f (x(1),x(2), . . .) = ∑∞i=1 1C2i fi(Cix(i)). We will prove Lemma 5.5 inpieces. Combining Claim 5.9, Claim 5.11, Claim 5.13, Claim 5.14, and Claim 5.15 proves Lemma 5.5.First, let us check that f is well defined.Claim 5.9. For every x ∈X , limn→∞∑ni=1 1C2i fi(Cix(i)) exists and is finite.Indeed, this follows as a corollary of the following claim since a series with non-negative summands con-verges if and only if it is bounded. Recall that fi are non-negative functions.Claim 5.10. f is bounded by onX .Proof. Let x = (x(1)/C1,x(2)/C2, . . .) ∈X .f (x) =∞∑i=11C2ifi(x(i)) ≤ M∞∑i=11C2i≤ M,because fi is bounded by M onXi. 55Next, we prove the implications involving convexity and strong convexity.Claim 5.11. f is a convex function. If fi is α-strongly convex for every i, then f is α-strongly convex.Proof. Convexity follows easily by considering λx+(1− λ )y where x,y ∈ ∏∞i=1RTi and λ ∈ (0,1). Indeed,since each fi is convex we have f (λx+(1−λ )y)≤ λ f (x)+(1−λ ) f (y), as desired.To check strong convexity, it suffices to prove that the function g(x) := f (x)− α2 ‖x‖2 is convex. Let x =(x(1),x(2), . . .) where x(i) ∈ RTi . Then,g(x) =∞∑i=1[1C2ifi(Cix(i))− α2∥∥∥x(i)∥∥∥2] = ∞∑i=1[1C2i(fi(Cix(i))− α2∥∥∥Cix(i)∥∥∥2)] ,which is convex because fi− α2 ‖·‖2 is a convex function since fi is α-strongly convex. To prove the implications involving the subdifferentiability and Lipschitz-ness of f on X , we will requirea characterization of the subdifferential of f (Claim 5.17) which will also be useful in proving that runningAlgorithm 1 on f is equivalent to running an instance of Algorithm 1 for each fi in parallel.Claim 5.12. Let x = (x(1)/C1,x(2)/C2, . . .) ∈X (that is x(i) ∈Xi). Then, ∂ f (x) =∏∞i=1 1Ci ∂ fi(x(i))Claim 5.12 immediately proves the following claim regarding the subdifferentiability of f onX and Lips-chitzness is an easy consquence of Claim 5.12 and our assumptions.Claim 5.13. Suppose for every i, for every x ∈Xi that ∂ fi(x) 6= /0. Then, ∂ f (x) 6= /0 for every x ∈X .Claim 5.14. f is L-Lipschitz onX .Proof. Let x = (x(1)/C1,x(2)/C2, . . .) ∈X . By Claim 5.12, we may write any g ∈ ∂ f (x) asg =(g(1)/C1,g(2)/C2, . . .),where g(i) ∈ ∂ fi(x(i)). Hence,‖g‖2 =∞∑i=1∥∥g(i)∥∥2C2i≤ L2∞∑i=11C2i≤ L2.Next, we will use Claim 5.12 to prove that that running Algorithm 1 on f is equivalent to running an instanceof Algorithm 1 for each fi in parallel.Claim 5.15. Let σi be a map such that for every x ∈ Xi, σi(x) ∈ ∂ fi(x). Let x(i)t denote the t-th iterate ofAlgorithm 1 on the function fi, using the feasible regionXi, step sizes ηt , initial point x(i)1 and the subgradientoracle σi. Then, there is a map σ such that for every x ∈X , σ(x) ∈ ∂ f (x) and the t-th iterate of gradientdescent on the function f using the feasible regionX , step sizes ηt , initial point x1 = (x(1)1 /C1,x(2)1 /C2, . . .) andthe subgradient oracle σ is given byxt =(x(1)tC1,x(2)tC2, . . .).56Proof. We begin by specifying σ . By Claim 5.12, the following definition of σ is valid:σ(x(1)C1,x(2)C2, . . .)=(1C1σ1(x(1)),1C2σ2(x(2)), . . .).We proceed by induction, using the subgradient oracle σ . The base case is true by assumption, that is weassumed x1 =(x(1)1C1,x(2)1C2, . . .). Now, suppose xt =(x(1)tC1, x(2)tC2, . . .). Then,yt+1 = xt −ηtσ(xt)=(x(1)tC1,x(2)tC2, . . .)−ηtσ(x(1)tC1,x(2)tC2, . . .)(by induction hypothesis)=(x(1)tC1,x(2)tC2)−ηt(1C1σ1(x(1)t ),1C2σ2(x(2)t ), . . .)(by definition of σ )=(1C1(x(1)t −ηtσ1(x(1)t )),1C2(x(2)t −ηtσ2(x(2)t )), . . .)=(1C1y(1)t+1,1C2y(2)t+1, . . .).Then, xt+1 = ΠX (yt+1). Now, we will apply Claim 5.16. To do so, we must check yt+1 ∈ `2. Indeed, thefollowing shows that this is true.‖yt+1‖2 =∞∑i=11C2i∥∥∥x(i)t −ηtσi(x(i))t ∥∥∥2≤∞∑i=11C2i(∥∥∥x(i)t ∥∥∥2+∥∥∥σi(x(i)t )∥∥∥2+2∥∥∥x(i)t ∥∥∥∥∥∥σi(x(i)t )∥∥∥) (by Cauchy-Schwarz)=∞∑i=11C2i∥∥∥x(i)t ∥∥∥2+ ∞∑i=12C2i∥∥∥x(i)t ∥∥∥∥∥∥σi(x(i)t )∥∥∥+ ∞∑i=11C2i∥∥∥σi(x(i)t )∥∥∥2 (each series converges absolutely)≤ R2∞∑i=11C2i+RL∞∑i=12C2i+L2∞∑i=11C2i(sinceXi ⊂BTi(0,R) and fi is L Lipschitz)< ∞ (because∞∑i=11C2i≤ 1)Therefore, by Claim 5.16, because each Xi is closed and convex we may compute this by computing theprojection of 1Ci y(i)t+1 ontoXi/Ci and then concatenating the results. Recall that ΠXi(y(i)t+1) = x(i)t+1, by definition57of Algorithm 1. Hence, we haveΠXi/Ci(1Ciy(i)t+1)= argminz∈Xi/Ci∥∥∥∥z− 1Ci y(i)t+1∥∥∥∥=1Ciargminz∈Xi∥∥∥z− y(i)t+1∥∥∥=1CiΠXi(y(i)t+1)=1Cix(i)t+1.Hence, we havext+1 = ΠX (yt+1) =(ΠX1/C1(1C1y(1)t+1),ΠX2/C2(1C2y(2)t+1), . . .)=(x(1)t+1C1,x(2)t+1C2, . . .),as desired. Claim 5.16. Let Y = ∏∞i=1Yi where each Yi ⊆ RTi is a closed convex set. Let z =(z(1),z(2), . . .) ∈ `2 wherez(i) ∈ RTi . Then, ΠY (z) =(ΠY1(z(1)),ΠY2(z(2)), . . .).Proof. Since ∏∞i=1Yi is closed and convex, then by [38, Theorem 4.10] we have that ΠY (z) is achievedby a unique element for z ∈ `2. Let ΠY (z) = (y(1),y(2), . . .) =: y where y(i) ∈ Yi. Suppose that for some i,y(i) 6= ΠYi(z(i)). Then, by the uniqueness of the projection onto a convex set, we have that∥∥y(i)− z(i)∥∥2 >∥∥ΠYi(z(i))− z(i)∥∥2. Consider the point y′ := (y(1), . . .y(i−1),ΠYi(z(i)),y(i+1), . . .) ∈ Y . We have‖y− z‖2 =∞∑j=1∥∥∥y( j)− z( j)∥∥∥2 > ∑j 6=i∥∥∥y( j)− z( j)∥∥∥2+∥∥∥ΠYi(z(i))− z(i)∥∥∥2 = ∥∥y′− z∥∥2 ,which contradicts the assumption that y =ΠY (z).Next, we must check Claim 5.12.Proof of Claim 5.12The proof of Claim 5.12 depends on the following lemma.Claim 5.17. Suppose h : `2 → R is such that h(y(1),y(2), . . .) = ∑∞n=1 hn(y(n)) where each hn : RTn → R is aconvex function. Assume h converges on some set Y ⊆ `2. Suppose that for every y = (y(1),y(2), . . .) ∈ Y withy(n) ∈ RTn , we have that ∑∞n=1∥∥g(n)∥∥<+∞ for every g(n) ∈ ∂hn(y(n)). Then, for all y ∈X∂h(y(1),y(2), . . .) = ∂h1(y(1))×∂h2(y(2))× . . . .See Sub-subsection 5.1.2 for a proof. To prove Claim 5.12 we will apply Claim 5.17, which requires us tocheckX ⊂ `2.Claim 5.18. X ⊂ `2.58Proof. Let x = (x(1)/C1,x(2)/C2, . . .) ∈X .‖x‖2 =∞∑i=1∥∥x(i)∥∥2C2i≤ R2∞∑i=11C2i≤ R2becauseXi ⊆BTi(0,R). Proof (of Claim 5.12). We will apply Claim 5.17 with hn = 1C2n fn ◦CnIn where In is the n× n identity matrix,Y =X =∏∞n=1 1CnXn, and h = f = ∑∞n=1 fn. To do so, we must check• Each fn is convex (which implies hn is convex),• X = 1Ci ∏∞i=1Xi ⊂ `2,• f is bounded everywhere onX (since f (x) is a sum of non-negative numbers, it converges if and only ifit is bounded),• For every x(i) ∈Xi, g(i) ∈ ∂(1C2ifi ◦CiITi)(x(i)/Ci), ∑∞i=1∥∥g(i)∥∥ < +∞, where ITi is the identity matrix inTi dimensions.The first three points are handled by assumption, Claim 5.18 and Claim 5.10. It remains to check the fourthpoint. By Claim A.9, ∂(1C2ifi ◦CiITi)(x(i)/Ci) = 1Ci ∂ fi(x(i)). Furthermore, because fi is L-Lipschitz, then everysubgradient of fi on Xi has norm at most L. Hence, for every g ∈ 1Ci ∂ fi(x(i)), ‖g‖2 ≤ (L/Ci)2. We have∑∞i=1 LCi ≤ L, and therefore the fourth point holds.Hence, applying Claim 5.17, we have for every x =(x(1)/C1,x(2)/C2, . . .) ∈X , we have∂ f (x(1)/C1,x(2)/C2, . . .) =∞∏i=1∂(1C2ifi ◦CiITi)(x(i)Ci)=∞∏i=11Ci∂ fi(x(i)),which completes the proof of the claim.Proof of Claim 5.17Claim 5.17. Suppose h : `2 → R is such that h(y(1),y(2), . . .) = ∑∞n=1 hn(y(n)) where each hn : RTn → R is aconvex function. Assume h converges on some set Y ⊆ `2. Suppose that for every y = (y(1),y(2), . . .) ∈ Y withy(n) ∈ RTn , we have that ∑∞n=1∥∥g(n)∥∥<+∞ for every g(n) ∈ ∂hn(y(n)). Then, for all y ∈X∂h(y(1),y(2), . . .) = ∂h1(y(1))×∂h2(y(2))× . . . .Proof. Let y ∈Y . We write y as ⊕∞n=1y(n) where y(n) ∈RTn denote the components of y. We have ∑∞n=1 hn(y(n))converges by assumption.First we show that ∂h1(y(1))× ∂h2(y(2))× . . . ⊆ ∂h(y(1),y(2), . . .). Let z = ⊕∞n=1z(n) ∈ `2 be arbitrary. Foreach n, suppose g(n) ∈ ∂hn(y(n)). Hence, for all z(n) ∈ RTnhn(z(n))≥ hn(y(n))+(z(n)− y(n))Ty(n).59Therefore, summing this inequality over n, we have:h(z) =∞∑n=1hn(z(n))≥∞∑n=1[hn(y(n))+(z(n)− y(n))Tg(n)]We may write ∑∞n=1[hn(y(n))+ (z(n)− y(n))Tg(n)]= ∑∞n=1 hn(y(n))+∑∞n=1(z(n)− y(n))Tg(n) if both series onthe right hand side converge. Observe that ∑∞n=1 hn(y(n)) converges by assumption. We now show ∑∞n=1(z(n)−y(n))Tg(n) converges absolutely. Indeed,∞∑n=1|(z(n)− y(n))Tg(n)| ≤∞∑n=1∥∥∥z(n)− y(n)∥∥∥∥∥∥g(n)∥∥∥ (by Cauchy-Schwarz)≤∞∑n=1‖z− y‖∥∥∥g(n)∥∥∥= ‖z− y‖∞∑n=1∥∥∥g(n)∥∥∥ (since x and y are in `2)< +∞ (∑∞n=1‖g(n)‖<+∞ by assumption) ,as desired. Therefore,h(z) ≥ h(y)+ 〈 z− y, g 〉,where z = ⊕∞n=1z(n), y = ⊕∞n=1y(n), g = ⊕∞n=1g(n). This demonstrates that ⊕∞n=1g(n) ∈ ∂h(y(1),y(2), . . .), sinceZ ∈ `2 was arbitrary.Now, we prove ∂h(y(1),y(2), . . .)⊆ ∂h1(y(1))×∂h2(y(2))× . . .. Suppose g =⊕∞n=1g(n) is a subgradient of hat y ∈ Y . Since `2 is self-dual, then by Definition 5.4 the subgradients of h live in `2 and so g ∈ `2. We verifythat for every n, g(n) ∈ ∂hn(y(n)). Let z∈RTn be arbitrary and let y˜= (y(1),y(2), . . . ,y(n−1),z,y(n+1), . . .). Observethat y˜ ∈ `2 because y ∈ `2 and moreover notice that h(y˜) converges since h(y˜) differs from h(y) in only a singlesummand and h(y) converges. Since g is a subgradient of h at y, we haveh(y˜)−h(y) ≥ (y˜− y)Tg⇔∞∑j=1h j(y˜( j))−∞∑j=1h j(y( j)) ≥∞∑j=1(y˜( j)− y( j))Tg( j)⇔∞∑j=1[h j(y˜( j))−h j(y( j))]≥∞∑j=1(y˜( j)− y( j))Tg( j) (h(y) and h(y˜) converge).By definition of y we havey˜( j) =y( j) if j 6= n,z otherwise.60Therefore, h(y˜)−h(y)≥ (y˜− y)Tg is equivalent tohn(z)−hn(y(n))≥ (z− y(n))Tg(n),which is equivalent to saying that g(n) is a subgradient of hn at y(n) as desired. 5.1.3 Proof of Claim 5.8Recall the definition of the augmented version of fTi , fi = max{fTi(x),12 ‖x‖2}.The main idea of showing thatfi provides the same lower bound on the performance of Algorithm 1 as fTi itself is to show that under theappropriate choice of subgradient oracle, running Algorithm 1 using fi is equivalent to running Algorithm 1using fTi (at least for the first Ti+1 iterations) in the sense that both executions produce the same iterates.Proof (of Claim 5.8). We begin by recalling the definition of the function fTi and its subgradient oracle:LetBTi(0,1) be the Euclidean unit ball in RTi . Define f :BTi(0,1)→ R and h` ∈ RTi for ` ∈ [T +1] byfTi(x) = max`∈[T+1]H`(x) where H`(x) = hT` x+12‖x‖2h`, j =a j (if 1≤ j < `)−1 (if `= j ≤ T )0 (if ` < j ≤ T )and a j =12(T +1− j) (for j ∈ [T ]).Recall the definition of the subgradient oracle for fTi from Section 2.1: Given a point x ∈BTi(0,1), defineσ ′i (x) = h`′+ x where `′ = minI (x) and I (x) = { ` : H`(x) = fTi(x) }. Defineσi(x) =σ ′i (x) if ∂ fi(x)⊆ ∂ fTi(x),arbitrary x ∈ ∂ fi(x) otherwise.Recall that by Lemma 2.5 the t-th (for t = 1, . . . ,Ti+1) iterate produced by Algorithm 1 on fTi when usingstep size ηt = 1/t and feasible region BTi(0,1) is given by the vector zt ∈ RTi which is strictly positive onthe first t− 1 coordinates and is zero on the remaining coordinates (by Claim 2.3). Therefore, the subgradientoracles σi and σ ′i agree on the vectors z1, . . .zTi+1 because fi(zt) = max{fTi(zt),12 ‖zt‖2}= fTi(zt) >12 ‖zt‖2(which implies ∂ fi(zt) = ∂ fTi(x)).Since the instance of Algorithm 1 on fTi and the instance of Algorithm 1 on fi begin at the same starting pointand because the subgradient oracles for both algorithms agree on z1, . . . ,zTi+1 (which are the iterates producedby the instance running on fTi), we have that the t-th iterate produced by Algorithm 1 when executed on fi is zt .That is, x(i)t = zt for t ∈ [Ti+1]. Observe thatfi(x(i)Ti+1) = fi(zTi+1) = fTi(zTi+1) ≥logTi4Ti,where the final inequality is because fTi is the function which realizes the lower bound in Theorem 1.12. 615.2 Necessity of log(1/δ )In this section, we show that the error of the last iterate and suffix average of SGD in the strongly-convex settingis Ω(log(1/δ )/T ) with probability at least δ .Lemma 5.19 ([24, Lemma 4]). Let X1, . . . ,XT be independent random variables taking value {−1,+1} uni-formly at random and X = 1T ∑Tt=1 Xi. Then for any√6≤ c< 2√T ,Pr[X ≥ c√T]≥ exp(−9c2/2).Consider the single-variable function f (x) = 12 x2 and suppose that the domain is X = [−1,1]. Then f is1-strongly convex and 1-Lipschitz on X . Moreover, suppose that the subgradient oracle returns x− zˆ where zˆis −1 or +1 with probability 1/2 (independently from all previous calls to the oracle). Finally, suppose we runAlgorithm 1 with step sizes ηt = 1/t with an initial point x1 = 0.Claim 5.20. Let√6≤√29 log(1/δ )≤ 2√T . Then f (xT+1)≥ 19 log(1/δ )T with probability at least δ .Proof. We claim that xt+1 = 1t ∑ti=1 zˆi for all t ∈ [T ] where zˆi is the random sign returned by the subgradientoracle at iteration i. Indeed, for t = 1, we have y2 = x1− η1(x1− zˆ1) = zˆ1 since η1 = 1. Moreover, x2 =ΠX (y2) = y2 since |y2| ≤ 1. Now, suppose that xt = 1t−1 ∑t−1i=1 zˆi. Then yt+1 = xt −ηt(xt − zˆt) = 1t ∑ti=1 zˆi. Since|yt+1| ≤ 1, we have xt+1 = yt+1.Hence, by Lemma 5.19 with c =√29 log(1/δ ), we have xT+1 ≥√29 log(1/δ )/√T with probability at leastδ (provided T ≥ 118 log(1/δ )). We conclude that f (xT+1)≥ log(1/δ )9T with probability at least Ω(δ ). We can also show that Theorem 1.17 is tight. To make the calculations simpler, first assume T is a multipleof 4. We further assume that the noise introduced by the stochastic subgradient oracle is generated as follows.For 1≤ t < T/2 and t > 3T/4, zˆt = 0. For T/2≤ t ≤ 3T/4, first define At = ∑Ti=t 1i . Then we set zˆt to be ± 14Atwith probability 1/2. Note that At ≥ 1/4 for T/2≤ t ≤ 3T/4 so we still have |zˆt | ≤ 1 for all t.Claim 5.21. Let√6 ≥√29 log(1/δ ) ≤ 2√T . Then f(1T/2+1 ∑T+1t=T/2+1 xt)≥ Ω(log(1/δ )T)with probability atleast δ .Proof. Proceeding as in the above claim, we have xt+1 = 1t ∑ti=1 zˆi. We claim that1T/2+1T+1∑t=T/2+1xt =1T/2+13T/4∑t=T/2At zˆt . (5.7)To see this, we have1T/2+1T∑t=T/2xt+1 =1T/2+1T∑t=T/21tt∑i=1zˆi=1T/2+1T∑i=1zˆiT∑t=max{i,T/2}1t=1T/2+13T/4∑t=T/2At zˆt ,62where the last equality uses the assumption that zˆt 6= 0 only if T/2 ≤ t ≤ 3T/4 and changes the name of theindex. Notice that At zˆt is ±14 with probability 1/2 so we can write Eq. (5.7) as14(T/2+1)T/4+1∑t=1Xtwhere Xt are random signs. Applying Lemma 5.19 with c =√log(1/δ ), we conclude that Eq. (5.7) is at leastΩ(√log(1/δ )/√T ) with probability at least δ . So we conclude that f(1T/2+1 ∑T+1t=T/2+1 xt)≥Ω(log(1/δ )T)withprobability at least δ . 63Chapter 6Extensions and Generalizations6.1 GeneralizationsIn this section, we discuss generalizations of our results. In Subsection 6.1.1, we explain that the scaling of thefunction (e.g., Lipschitzness) can be normalized without loss of generality. In Subsection 6.1.2, we state someresults which demonstrate that the assumption of almost surely bounded noise can be relaxed to subgaussiannoise in our upper bounds (Theorems 1.9, 1.10 and 1.17). The proofs of these results can be found in Section 6.3.6.1.1 Scaling assumptionsFor most of this thesis we consider only convex functions that have been appropriately normalized, due to thefollowing facts.• Strongly convex case. The case of an α-strongly convex and L-Lipschitz function can be reduced to thecase of a 1-strongly convex and 1-Lipschitz function.• Lipschitz case. The case of an L-Lipschitz function on a domain of diameter R can be reduced to the caseof a 1-Lipschitz function on a domain of diameter 1.We will discuss only the first of these in detail. The second is proven with similar ideas and so we only sketchthe proof.Strongly convex settingTheorem 6.1. Suppose f is α-strongly convex and L-Lipschitz, and that zˆt has norm at most L almost surely.Consider running Algorithm 1 for T iterations with step size ηt = 1αt . Let x∗ = argminx∈X f (x). Then, withprobability at least 1−δ ,f (xT+1)− f (x∗) ≤ O(L2αlog(T ) log(1/δ )T).Theorem 6.2. Suppose f is α-strongly convex and L-Lipschitz, and that zˆt has norm at most L almost surely.Consider running Algorithm 1 for T iterations with step size ηt = 1αt . Let x∗ = argminx∈X f (x). Then, with64probability at least 1−δ ,f(1T/2+1T∑t=T/2xt)− f (x∗) ≤ O(L2αlog(1/δ )T).We prove these theorems by reduction to Theorem 1.9 and Theorem 1.17, respectively. That is, suppose thatf is a function that has strong convexity parameter α and Lipschitz parameter L. We construct a function h thatis 1-Lipschitz and 1-strongly convex (using Claim 6.3) and a subgradient oracle such that running SGD on hwith this subgradient oracle is equivalent to running SGD on f . Formally, we prove the following two claims:Claim 6.3. Let f be an α-strongly convex and L-Lipschitz function. Then, h(x) := αL2 f (Lα x) is 1-Lipschitz and1-strongly convex.Claim 6.4. Suppose f is α-strongly convex and L-Lipschitz on a domainX ⊂Rn. Let the initial point x1 ∈Xbe given. Let h be as defined in Claim 6.3. Then, there is a coupling between the following two processes:• the execution of Algorithm 1 on input f with initial point x1, step size ηt = 1/(αt) and feasible regionX• the execution of Algorithm 1 on input h with initial point x˜1 := (α/L)x1, step size η˜t = 1/t and feasibleregion (α/L)Xsuch that the iterates of the second process correspond to the iterates of the first process scaled by α/L. That is,if we denote by x˜t the iterates of the execution of SGD using h and xt for the execution on f , then x˜t = (α/L)xt .Theorem 6.1 and Theorem 6.2 follow easily now. We prove Theorem 6.1 by reducing to Theorem 1.9. Theproof of Theorem 6.2 can be obtained by reducing similarly to Theorem 1.17.Proof (of Theorem 6.1). Suppose f is α strongly-convex and L-Lipschitz and letX be the feasible region. Leth(x)= αL2 f( Lα x). By Claim 6.3, h is a 1 strongly-convex and 1-Lipschitz function. Note that minx∈(α/L)X h(x)=αL2 minx∈X f (x). Using the coupling provided in Claim 6.4, let xt be the iterates of produced by running SGDwhen using f over the regionX and x˜t be the iterates of SGD when using h over the region (α/L)X . Claim 6.4shows that x˜t = (α/L)xt . Therefore, we haveh(x˜T+1)− minx∈(α/L)Xh(x) =αL2(f (xT+1)−minx∈Xf (x)).Hence, applying Theorem 1.9, we have our desired result by noting thath(x˜T+1)− minx∈(α/L)Xh(x) = O(log(T ) log(1/δ )T)with probability 1−δ .Now it remains to prove Claim 6.4 and Claim 6.3Proof (of Claim 6.4). The coupling is given by constraining the algorithms to run in parallel and enforcing theexecution of SGD on h to use a scaled version of the outputs of the subgradient oracle used by the executionof SGD on f . That is, at step t, if gˆt is the output of the subgradient oracle of the execution of SGD on f(i.e. E [ gˆt ] ∈ ∂ f (xt)), then we set the output of the subgradient oracle of the execution of SGD on h at step t tobe 1L gˆt .65The subgradient oracle for h is valid if x˜t = (α/L)xt . Indeed, ∂h(x) = 1L f( Lα x)by Claim A.9. Therefore,∂h((α/L)xt) = 1L∂ f (xt). Since E [ gˆt ] ∈ ∂ f (xt) then E [ (1/L)gˆt ] ∈ ∂h((α/L)xt). Next, we prove via inductionthat x˜t = (α/L)xt .By definition, x˜1 = (α/L)x1, which handles the base case. Now, assume x˜t = (α/L)xt . Let gˆt be theoutput of the subgradient oracle for SGD running on f . The subdifferential for h at x˜t is 1L∂ f (xt). Therefore,the subgradient oracle for h is valid at this step. Now, yt+1 = xt − 1αt gˆt . Meanwhile, y˜t+1 = x˜t − 1t 1L gˆt =αL (xt − 1αt g˜t) = αL yt+1. Therefore,x˜t+1 =Π(α/L)X (y˜t+1) =Π(α/L)X (yt+1(α/L)) = (α/L)ΠX (yt+1) = (α/L)xt+1as desired. Proof (of Claim 6.3). First we show that h is 1-Lipschitz:|h(x)−h(y)| = αL2∣∣∣∣ f( Lα x)− f(Lαy)∣∣∣∣ ≤ αL2 L∥∥∥∥ Lα (x− y)∥∥∥∥ = ‖x− y‖ .The inequality holds since f is L-Lipschitz.Now we show that h is 1-strongly convex. A function g is α strongly convex, if and only if the functionx 7→ g(x)− α2 ‖x‖2 is convex. Indeed, for h:h(x)− 12‖x‖2 = αL2f(Lαx)− 12‖x‖2 = αL2(f(Lαx)− L22α‖x‖2)=αL2(f(Lαx)− α2∥∥∥∥ Lα x∥∥∥∥2).The function on the right is convex because f is α-strongly convex. This implies that x 7→ h(x)− 12 ‖x‖2 isconvex, meaning that h is 1-strongly convex. Lipschitz settingTheorem 6.5. Suppose f is an L-Lipschitz function onX and that zˆt has norm at most L almost surely. Considerrunning Algorithm 1 for T iterations with step size ηt = RL√t . Let f∗ =minX f (x).Then, with probability at least1−δ ,f (xT+1)− f ∗ = O(RL · log(T ) log(1/δ )√T).Theorem 6.5 can be proved by a reduction to Theorem 1.10, similarl to the strongly-convex setting. We donot provide proofs, as the ideas are similar to the strongly-convex setting and can be easily adapted to prove theresults in this setting. The main claims are as follows.Claim 6.6. Let f be an L-Lipschitz function on X . Then, h(x) := 1RL f (Rx) is 1-Lipschitz on (1/R)X andminx∈(1/R)X h(x) = 1RL minx∈X f (x). Note that diam(X )≤ 1.Claim 6.7. Suppose f is L-Lipschitz on a domain X ⊂ Rn. Let the initial point x1 ∈X be given. Let h be asdefined in Claim 6.6. Then, there is a coupling between the following two processes:• the execution of Algorithm 1 on input h with initial point x˜1 := (1/R)x1, step size η˜t and feasible region(1/R)X , and66• the execution of Algorithm 1 on input f with initial point x1, step size ηt = RL η˜t and feasible regionXsuch that the iterates of the first process correspond to the iterates of the second process scaled by 1R . That is, ifwe denote by x˜t the iterates of the execution of SGD using h and xt for the execution on f , then x˜t = (1/R)xt .6.1.2 Subgaussian noiseTheorems 1.9 and 1.10 assume that the stochastic gradient oracle produces noise at each step that almost surelyhas Euclidean norm at most 1. It is possible to relax this assumption to include stochastic gradient oracleswhich allow unbounded noise as long as the norm of the noise is sufficiently “concentrated” around someconstant. The notion of concentration which we use is subgaussian-ness. For example, normally distributedrandom variables are subgaussian. See Section 6.2 for a formal introduction to subgaussian random variables.Below we informally state our high probability upper bounds generalized to handle subgaussian noise. We willprove a formal version of Theorem 6.8 in Section 6.3. A formal version of Theorem 6.9 can be obtained byapplying similar modifications to the proof of Theorem 6.9 as was done to the proof of Theorem 1.9 to obtainTheorem 6.8.Theorem 6.8 (Informal subgaussian extension, strongly convex case). Suppose f is 1-strongly convex and 1-Lipschitz. Assume ‖zˆt‖ is a subgaussian random variable conditioned onFt−1. Consider running Algorithm 1for T iterations with step size ηt = 1/t. Let x∗ = argminx∈X f (x). Then, with probability at least 1−δ ,f (xT+1)− f (x∗) ≤ O(log(T ) log(1/δ )T).Theorem 6.9 (Informal subgaussian extension, Lipschitz case). Suppose f is 1-Lipschitz and diam(X ) ≤ 1.Assume ‖zˆt‖ is a subgaussian random variable conditioned on Ft−1. Consider running Algorithm 1 for Titerations with step size ηt = 1/√t. Let f ∗ = minx∈X f (x). Then, with probability at least 1−δ ,f (xT+1)− f (x∗) ≤ O(log(T ) log(1/δ )√T).Remark 6.10. Theorem 6.8 and Theorem 6.9 can be extended to handle functions with arbitrary Lipschitz andstrong convexity constants using the reductions from Subsection 6.1.1.6.2 Subgaussian and subexponential random variablesIn this section, we go over some basic preliminaries on subgaussian and subexponential random variables; thereader is referred to the book by Vershynin [45, Chapter 2] for further background. The results stated herewill be useful in Section 6.3 where we extend our high probability convergence by relaxing the bounded noiseassumption.6.2.1 Subgaussian random variablesDefinition 6.11 (Subgaussian random variable).67• For a random variable X, define‖X‖ψ2 = inf{t > 0 : E[exp(X2/t2)]≤ 2 } .We call X subgaussian if ‖X‖ψ2 is finite.• For a random variable X and a sigma-algebraF , define‖X |F‖ψ2 = inf{t > 0 : E[exp(X2/t2) | F ]≤ 2 } .We call X subgaussian conditioned onF if ‖X |F‖ψ2 is finite.Fact 6.12. ‖·‖ψ2 is a norm. It is refered to as the ψ2-norm.Claim 6.13. Let X be a subgaussian random variable. Then E[exp(X2/‖X‖2ψ2)]≤ 2.Proof. Let S ={t > 0 : E[exp(X2/t2)]≤ 2 }. For every ε > 0, we have that ‖X‖ψ2 + ε > t for some t ∈ S.Hence,E[exp(X2/(‖X‖ψ2 + ε)2)]< E[exp(X2/t2)]≤ 2.Therefore, for every ε > 0 we have E[exp(X2/(‖X‖ψ2 + ε)2)]< 2. Taking ε→ 0 and applying the monotoneconvergence theorem completes the proof. Claim 6.14. Let X be a subgaussian random variable. Then E[exp(λ 2X2)] ≤ exp(λ 2 ‖X‖2ψ2) for all |λ | ≤1/‖X‖ψ2 .Proof. Suppose |λ | ≤ 1‖X‖ψ2 , which implies that the function x 7→ xλ 2‖X‖2ψ2 is concave. Hence,E[exp(λ 2X2)]= E[exp(λ 2 ‖X‖2ψ2 X2/‖X‖2ψ2)]≤ E[exp(X2/‖X‖2ψ2)]λ 2‖X‖2ψ2 (by Jensen’s inequality)≤ 2λ 2‖X‖2ψ2 (by Claim 6.13)≤ exp(λ 2 ‖X‖2ψ2).Claim 6.15. Suppose that E[exp(λ 2X2)]≤ exp(λ 2κ2) for all |λ | ≤ 1/κ . Then ‖X‖ψ2 ≤ κ/√ln2.Proof. Let λ˜ =√ln2/κ ≤ 1/κ . By Claim 6.14,E[exp((ln2)X2/κ2)]= E[exp(λ˜ 2X2)]≤ exp(λ˜ 2κ2)= 2.Hence, by Definition 6.11, we have ‖X‖ψ2 ≤ κ/√ln2. The combination of Claim 6.15 and Claim 6.14 establishes that the two properties E[exp(X2/t)]≤ 2 andE[exp(λ 2X2)] ≤ exp(λ 2t2) for all |λ | ≤ 1/t are “equivalent”. That is, if a random variable satisfies one of68the properties with value t, then it satisfies the other property with value t ′ which differs from t only by someconstant factor independent of the random variable X .Claim 6.16 (‖·‖ψ2 bound to tail bound). Suppose ‖X‖ψ2 ≤ κ . Then,Pr[X ≤ κ√log(e/δ )]≥ 1−δ ∀δ ∈ (0,1].Proof. By the exponentiated Markov inequalityPr [X ≥ t ] ≤ exp(−λ 2t2)E[exp(λ 2X2)] ≤ exp(−λ 2t2+λ 2κ2) (for all |λ | ≤ 1/κ),where the second inequality uses Claim 6.14. Setting λ = 1/κ and t = κ√log(e/δ ) completes the proof. The following Claim is an extension of the well known Hoeffding’s Lemma (Lemma A.5) from boundedrandom variables to subgaussian random variables.Claim 6.17. Suppose X is mean-zero such that ‖X‖ψ2 ≤ κ . Then E [exp(λX) ]≤ exp(λ 2κ2)for all λ ∈ R.Proof. Claim 6.14 implies that E[exp(λ 2X2)] ≤ exp(λ 2κ2) for all |λ | ≤ 1κ . Hence, the result follows fromClaim A.6. 6.2.2 Subexponential random variablesDefinition 6.18 (Subexponential random variable).• For a random variable X, define‖X‖ψ1 = inf{ t > 0 : E [exp(|X |/t) ]≤ 2 } .We call X subexponential if ‖X‖ψ1 is finite.• For a random variable X and a sigma-algebraF , define‖X |F‖ψ1 = inf{ t > 0 : E [exp(|X |/t) | F ]≤ 2 } .We call X subexponential conditioned onF if ‖X |F‖ψ1 is finite.Fact 6.19. ‖·‖ψ1 is a norm. It is referred to as the ψ1-norm.Claim 6.20. Let X be a subexponential random variable. Then E[exp(X/‖X‖ψ1)]≤ 2.Proof. Let S = { t > 0 : E [exp(|X |/t) ]≤ 2 }. For every ε > 0, we have that ‖X‖ψ1 + ε > t for some t ∈ S.Hence,E[exp(|X |/(‖X‖ψ1 + ε))]< E [exp(|X |/t) ]≤ 2.Therefore, for every ε > 0 we have E[exp(|X |/(‖X‖ψ1 + ε))]< 2. Taking ε→ 0 and applying the monotoneconvergence theorem completes the proof. 69Claim 6.21. Let X be a subexponential random variable. Then E [exp(λ |X |) ] ≤ exp(λ ‖X‖ψ1)for all λ ∈[0,1/‖X‖ψ1 ].Proof. Suppose λ ∈ [0,1/‖X‖ψ1 ], which implies that the function x 7→ xλ‖X‖ψ1 is concave. Hence,E [exp(λ |X |) ] = E[exp(λ ‖X‖ψ1 |X |/‖X‖ψ1)]≤ E[exp(|X |/‖X‖ψ1)]λ‖X‖ψ1 (by Jensen’s inequality)≤ 2λ‖X‖ψ1 (by Claim 6.20)≤ exp(λ ‖X‖ψ1).Claim 6.22. Suppose that E [exp(λ |X |) ]≤ exp(λκ) for all λ ∈ [0,1/κ]. Then ‖X‖ψ1 ≤ κ/(ln2).Proof. Let λ˜ = (ln2)/κ, so clearly λ˜ ∈ [0,1/κ]. By Claim 6.21,E [exp(ln2 |X |/κ) ] = E[exp(λ˜ |X |)]≤ exp(λ˜κ)= 2.Hence, by Definition 6.18, we have ‖X‖ψ1 ≤ κ/(ln2). The combination of Claim 6.22 and Claim 6.21 establishes that the two properties E [exp(|X |/t) ] ≤ 2 andE [exp(λ |X |) ] ≤ exp(λ t) for all |λ | ≤ 1/t are “equivalent”. That is, if a random variable satisfies one of theproperties with value t, then it satisfies the other property with value t ′ which differs from t only by someconstant factor independent of the random variable X .Claim 6.23 (‖·‖ψ1 bound to tail bound). Suppose ‖X‖ψ1 ≤ κ . Then, for every δ ∈ (0,1), X ≤ κ log(e/δ ) withprobability at least 1−δ .Proof. By the exponentiated Markov inequality,Pr [X ≥ t ] ≤ exp(−λ t)E [exp(λX) ] ≤ exp(−λ t+λκ) (for all λ ∈ (0,1/κ]),where the second inequality follows from Claim 6.21. Setting λ = 1/κ and t = κ log(e/δ ) completes theproof. 6.2.3 Relationship between subgaussian and subexponential random variablesSubgaussian and subexponential random variables share a simple connection, as hilighted by the result below.Claim 6.24. Suppose X is a subgaussian random variable. Then, X2 is subexponential with∥∥X2∥∥ψ1 = ‖X‖2ψ2Proof. This is easy to see by comparing the definition of each norm:∥∥X2∥∥ψ1 = inf{ t > 0 : E[exp(X2/t)]≤ 2 }︸ ︷︷ ︸:=A,70‖X‖ψ2 = inf{t > 0 : E[exp(X2/t2)]≤ 2 }︸ ︷︷ ︸:=B.Clearly,{b2 : b ∈ B }= A. Hence,∥∥X2∥∥ψ1 = infA = (infB)2 = ‖X‖2ψ2 ,as desired. 6.3 Upper bound on error of final iterate: subgaussian noiseTheorems 1.9 and 1.10 assume that the stochastic gradient oracle produces noise at each step that almost surelyhas Euclidean norm at most 1. In this section, we work with the weaker assumption that the noise at each stepis conditionally subgaussian. (A formal definition of this term appears in Section 6.2.)As before, we will write gˆt = gt− zˆt , where gˆt is the vector returned by the oracle at the point xt , gt ∈ ∂ f (xt),and zˆt is the noise. LetFt = σ(zˆ1, . . . , zˆt) be the σ -algebra generated by the first t steps of SGD. Finally, recallthat E [ zˆt | Ft−1 ] = 0. Instead of assuming that ‖zˆt‖≤ 1 almost surely, we will assume that ‖zˆt‖ is a subgaussianrandom variable conditioned onFt−1.We will prove an extension of Theorem 1.9 in the following subsection (see Theorem 6.25). A similarextension for Theorem 1.10 can also be obtained, however its proof is omitted since it relies mainly on the ideasintroduced in the next section.6.3.1 Upper bound on error of final iterate, strongly convex case with subgaussian noiseThe goal of this subsection is to prove Theorem 6.25. The analysis will reuse many claims from the analysis ofTheorem 1.9 and follow the general approach taken there as well.Assumptions. The main difference between Theorem 6.25 and Theorem 1.9 is the assumption on the noiseproduced by the stochastic gradient oracle. In this subsection, we assume ‖‖zˆt‖2 |Ft−1‖ψ2 ≤ κ for every t.Theorem 6.25. Suppose f is 1-strongly convex and 1-Lipschitz. Suppose that ‖‖zˆt‖ |Ft−1‖ψ2 ≤ κ for all t.Consider running Algorithm 1 for T iterations with step size ηt = 1/t. Let x∗ = argminx∈X f (x). Then, withprobability at least 1−δ ,f (xT+1)− f (x∗) ≤ O((κ+1)2log(T ) log(1/δ )T).One important result that we need is a bound on∥∥∥‖gˆt‖2∥∥∥ψ1. In Section 3.1, this was not necessary, since‖gˆt‖2 was almost-surely bounded by 4. This made for a clean analysis. Here, ‖gˆt‖2 can potentially be un-bounded, and therefore we need to provide control on it’s tail distribution. Indeed, this is accomplished by thefollowing claim.Claim 6.26. For every t, ‖‖gˆt‖ |Ft−1‖ψ2 = O(κ+1). Therefore,∥∥∥‖gˆt‖2 |Ft−1∥∥∥ψ1= O((κ+1)2). Thisimplies∥∥∥‖gˆt‖2∥∥∥ψ1= O((κ+1)2).71Proof. Recall, gˆt = gt− zˆt where gt ∈ ∂ f (xt) and zˆt is mean-zero conditioned onFt−1 such that ‖‖zˆt‖ |Ft−1‖ψ2 ≤κ. Now, because ‖·‖ψ1 is a norm, we have‖‖gˆt‖ |Ft−1‖ψ2 ≤ ‖‖gt‖+‖zˆt‖ |Ft−1‖ψ2 ≤ ‖‖gt‖ |Ft−1‖ψ2 +‖‖zˆt‖ |Ft−1‖ψ2 ≤ κ+1/√ln2.We have used that ‖‖gt‖ |Ft−1‖ψ2 ≤‖1 |Ft−1‖ψ2 by 1-Lipschitzness of f . By definition, we have ‖1 |Ft−1‖ψ2 ≤1/√ln2. Lastly, we have used the assumption that ‖‖zˆt‖ |Ft−1‖ψ2 ≤ κ. Lemma 6.27. Let f be 1-strongly convex and 1-Lipschitz. Suppose that we run SGD (Algorithm 1) with stepsizes ηt = 1/t and that ‖zˆt |Ft−1‖ψ2 ≤ κ. Thenf (xt) ≤ 1T/2+1T∑t=T/2f (xt)︸ ︷︷ ︸suffix average+T/2∑k=11k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉︸ ︷︷ ︸ZT , the noise term+X ,where X is a random variable such that ‖X‖ψ1 = O((κ+1)2 logTT 2).Proof. We may proceed just as in the proof of Lemma 3.1. Applying Eq. (3.4), we obtainf (xT ) ≤ ST/2+T/2∑k=112k(k+1)T∑t=T−kηt ‖gˆt‖2+T/2∑k=11k(k+1)T∑t=T−k〈 zˆt , xt − xT−k 〉,where ST/2 = 1T/2+1 ∑Tt=T/2 f (xt). From this point, the only difference is analyzing the following sum:T/2∑k=112k(k+1)T∑t=T−kηt ‖gˆt‖2 ,because we cannot bound ‖gˆt‖2 as was done in the proof of Lemma 3.1. Instead, we may bound it’s ψ1-normusing the fact that∥∥∥‖gˆt‖2∥∥∥ψ1= O((κ+1)2)(Claim 6.26) and the triangle inequality for ‖·‖ψ1 . This yields:∥∥∥∥∥T/2∑k=1 12k(k+1)T∑t=T−kηt ‖gˆt‖2∥∥∥∥∥ψ1≤ O((κ+1)2logTT),as desired. Since ‖X‖ψ1 ≤O((κ+1)2 logTT), we have that by Claim 6.23, X ≤O((κ+1)2 logTT log(1/δ )), with prob-ability at least 1− δ . The suffix average is bounded by O((κ+1)2 log(1/δ )T)by Theorem 6.37 (we defer theproof to Subsection 6.3.3). Therefore, it remains to analyze ZT . By changing the order of summation, we canwrite ZT = ∑Tt=T/2〈 zˆt , wt 〉 wherewt =t∑j=T/2α j(xt − x j) and α j = 1(T − j)(T − j+1) .We will prove the following lemma, whose proof is outlined in Sub-subsection 6.3.1.72Lemma 6.28. ZT = O(κ (κ+1) logT log(1/δ )T)with probability at least 1−δ .Theorem 6.25 follows from Theorem 6.37, Lemma 6.28 and Lemma 6.27.Bounding the noiseThe main idea is to follow the steps in Subsection 3.1.1. However, certain steps will require a slightly differentanalysis due to the absence of a bound on ‖gˆt‖2. Lemma 3.3 still holds in the subgaussian noise case. We restateit here:Lemma 3.3. Suppose f is 1-Lipschitz and 1-strongly convex. Suppose we run Algorithm 1 for T iterationswith step sizes ηt = 1/t. Let a< b. Then,‖xa− xb‖2 ≤b−1∑i=a‖gˆi‖2i2+2b−1∑i=a(f (xa)− f (xi))i+2b−1∑i=a〈 zˆi, xi− xa 〉i.However, we prove a slight variant of Lemma 3.4.Lemma 6.29. There exists positive values R = O(logTT), Ct = Θ(log(T − t)) , At = O(logTT 2)and a non-negative random variable X with ‖X‖ψ1 = O((κ+1)2 log2(T )T 2)such thatT∑t=T/2‖wt‖2 ≤ X +R∥∥xT/2− x∗∥∥2+ T−1∑t=T/2〈 zˆt , Ctt wt 〉+T−1∑t=T/2〈 zˆt , At(xt − x∗) 〉.Proof. We may follow the proof of Lemma 3.4 from Subsection 3.3.4, with some minor differences. Here wewill only provide a brief outline of the differences.We redefine Λ1 as follows, while keeping the definition of Λ2 and Λ3 as in the proof of Lemma 3.4.Λ1 :=T∑t=T/21T − t+1t−1∑j=T/2α jj−1∑i= j‖gˆi‖2i2.Recall, ∑Tt=T/2 ‖wt‖2 ≤ Λ1+Λ2+Λ3, just as in Subsection 3.3.4.Using the triangle inequality and the ψ1 norm bound on ‖gˆi‖2 from Claim 6.26, we may replace Claim 3.17withClaim 6.30. ‖Λ1‖ψ1 = O((κ+1)2 log2(T )T 2).We may keep Claim 3.19 as our bound on Λ3:Claim 3.19.Λ3 =T−1∑i=T/2〈 zˆi, Cii wi 〉,where Ci := ∑T`=i+12T−i+1 = O(log(T )).It remains to bound Λ2. We provide a slight variant of Claim 3.18:73Claim 6.31. There exists positive values R1, R2 such that R1 =O(logTT)and R2 =O(logTT 2)and a non-negativerandom variable, X, such that ‖X‖ψ1 = O((κ+1)2 log(T )T 2), whereΛ2 ≤ X +R1∥∥xT/2− x∗∥∥2+R2 T−1∑t=T/2〈 zˆt , xt − x∗ 〉.Proof. We may follow the proof of Claim 3.18 (found in Subsection 3.3.5) up to Eq. (3.5). At this stage, wemay continue the proof without bounding ‖gˆt‖2 , and instead collect these terms to obtain:Λ2 ≤ O(logTT 2) T−1∑t=T/21t‖gˆt‖2+O(logTT)∥∥xT/2− x∗∥∥2+O( logTT 2) T−1∑t=T/2〈 zˆt , xt − x∗ 〉.At this step, we can take X = O(logTT 2)∑T−1t=T/21t ‖gˆt‖2. It’s ψ1-norm is bounded as desired by using Claim 6.26and the triangle inequality for the ψ1-norm. Lemma 6.29 follows from Claim 6.30, Claim 6.31, and Claim 3.19. Just as in Section 3.1, we will use Theorem 1.11. A snag is that our Lemma 6.29 does not quite bound theSSCM of ZT by a linear transformation of ZT . However, Lemma 6.33 refines Lemma 6.29 so that we may useTheorem 1.11 (similar to how Lemma 3.6 refines Lemma 3.4) . The proof of Lemma 6.33 uses the followinganalog of Theorem 3.5 (see Subsection 6.3.2 for a proof).Theorem 6.32. Both of the following hold:• For all t ≥ 2, ‖xt − x∗‖2 = O((κ+1)2 log(1/δ )/t)with probability 1−δ , and• Let σt ≥ 0 for t = 2, . . . ,T . Then,∑Tt=1σt ‖xt − x∗‖2 = O((κ+1)2 log(1/δ )∑Tt=2σtt)with probability1−δ .Lemma 6.33. For every δ ∈ (0,1), there exists positive values R=((κ+1)2 log2(T ) log(1/δ )T 2), and Ct =O(logT )such that ∑Tt=T/2 ‖wt‖2 ≤ R+∑T−1t=T/2 Ctt 〈 zˆt , wt 〉 with probability at least 1−δ .Proof.From Lemma 6.29, we haveT∑t=T/2‖wt‖2 ≤ X +R′∥∥xT/2− x∗∥∥2+ T−1∑t=T/2〈 zˆt , Ctt wt 〉+T−1∑t=T/2〈 zˆt , At (xt − x∗) 〉,where X ,R′,At ,Ct are as promised by Lemma 6.29. Because ‖X‖ψ1 = O((κ+1)2 logTT 2), then by Claim 6.23, wehave X = O((κ+1)2 logT log(1/δ )T 2), with probability at least 1−δ .Furthermore, Theorem 6.32 states that∥∥xT/2− x∗∥∥2 = O( (κ+1)2 log(1/δ )T ) with probability at least 1− δ .Hence, R′∥∥xT/2− x∗∥∥2 = O((κ+1)2 log(1/δ ) log(T )T 2 ) with probability at least 1−δ .Lastly, it remains to deal with ∑T−1t=T/2〈 zˆt , At(xt − x∗) 〉. Observe that this is a sum of a martingale differencesequence with SSCM bounded by ∑T−1t=T/2 A2t ‖xt − x∗‖2. Using Theorem 6.32 (the upper bound on squareddistances of the iterates xt to x∗), this is bounded above by O((κ+1)2 log(1/δ ) log2(T )T 4). Now, we can translate74our SSCM bound to a high probability bound on the martingale itself by applying Corollary 6.40 (which isan application of Theorem 1.11 for bounding a martingale with subgaussian increments when it’s SSCM isbounded) to obtain ∑T−1t=T/2〈 zˆt , At(xt − x∗) 〉= O(κ (κ+1) log(1/δ ) log(T )T 2)with probability at least 1−δ .Now, we are ready to complete the proof of Lemma 6.28.Proof (of Lemma 6.28). Let R, Ct , X be as promised from Lemma 6.33. These values provide a high probabilityupper bound of R′ log(1/δ )+∑T−1t=T/2Ctt 〈 zˆt , wt 〉 on the SSCM of ZT , where R′ log(1/δ ) = R. Corollary 6.41(an application of Theorem 1.11 for martingales with subgaussian increments) allows us to then bound ZT byκ√R′ log(1/δ ) with probability at least 1− δ . Indeed, recalling that R′ = O((κ+1)2 log2(T )T 2)yields our desiredresult. 6.3.2 High probability bounds on squared distances to x∗The main goal of this subsection is to prove Theorem 6.32.Claim 6.34. Suppose f is 1-strongly-convex and 1-Lipschitz. Define Yt = t ‖xt+1− x∗‖2 and Ut = 〈 zˆt+1, xt+1−x∗ 〉/‖xt+1− x∗‖ . Then,Yt+1 ≤(t−1t)Yt +2 ·Ut√Ytt+‖gˆt+1‖2t+1.The proof of Claim 6.34 is identical to the proof of Claim 3.7, except that we cannot bound ‖gˆt‖2 by 4 dueto the fact that the noise, zˆt , is not bounded as was assumed in Claim 3.7.The main tool to prove this theorem is the following analog to Theorem 1.19. See Subsection 6.3.4 for aproof.Theorem 6.35. Let (Xt)Tt=1 be a stochastic process and let (Ft)Tt=1 be a filtration such that Xt isFt-measurableand Xt is non-negative almost surely. Let αt ∈ [0,1) and βt ,γt ≥ 0 for every t. Let wˆt beFt+1-measurable suchthat ‖wˆt |Ft‖ψ2 ≤ τ for every t and E [ wˆt | Ft ] = 0. Let yˆt be Ft+1-measurable such that ‖yˆt |Ft‖ψ1 ≤ ρfor every t. Suppose Xt+1 ≤ αtXt + βtwˆt√Xt + γt yˆt , for every t. Assume that E [exp(λX1) ] ≤ exp(λK), forλ ∈ (0,1/K]. Then,• For every t, Pr [Xt ≥ K log(1/δ ) ]≤ eδ ,• If σ1, . . . ,σT ≥ 0, then Pr[∑Tt=1σtXt ≥ K log(1/δ )∑Tt=1σt]≤ eδ ,where K = maxTt=1(2γtρ1−αt ,4β 2t τ21−αt).Proof (of Theorem 6.32). Consider the stochastic process (Yt)Tt=1 where Yt is as defined by Claim 6.34. Notethat Yt satisfied the conditions of Theorem 6.35 with Xt = Yt , wˆt =Ut , αt = t−1t , βt =2√t , γt =1t+1 , yˆt = ‖gˆt‖2,τ = κ , ρ = (κ + 1)2. Indeed, Yt is Ft-measurable and non-negative almost surely. Ut is Ft+1-measurablewhich is mean zero conditioned on Ft . Furthermore, ‖Ut |Ft‖ψ2 ≤ κ because ‖‖zˆt‖ |Ft‖ψ2 ≤ κ . Further-more, ‖gˆt‖2 is also Ft+1-measurable and∥∥∥‖gˆt‖2 |Ft∥∥∥ ≤ (κ + 1)2 by Claim 6.26. It’s easy to check thatmax1≤t≤T(2γtρ1−αt ,4β 2t τ21−αt)= O((κ+1)2). We must check the following claim:Claim 6.36. For all λ ∈ (0, 1Θ((κ+1)2)], E[exp(λ ‖x2− x∗‖2)]≤ exp(λΘ((κ+1)2)).75Proof.E[exp(λ ‖x2− x∗‖2)]= E[exp(λ(‖ΠX (x1− gˆ1)− x∗‖2))]≤ E[exp(λ(‖x1− x∗− gˆ1‖2))]= E[exp(λ(‖x1− x∗‖2+‖gˆ1‖2−2〈 x1− x∗, gˆ1 〉))].By 1-strong-convexity and 1-Lipschitzness of f ,‖xt − x∗‖ ≥ 〈gt , xt − x∗ 〉 ≥ 12 ‖xt − x∗‖2 ,for every t. Hence,E[exp(λ ‖x2− x∗‖2)]≤ E[exp(λ(4+‖gˆ1‖2+4‖gˆ1‖))]= exp(4λ )E[exp(λ ‖gˆ1‖2)exp(4λ ‖gˆ1‖)]≤ exp(4λ )(E[exp(2λ ‖gˆ1‖2)])1/2(E [exp(8λ ‖gˆ1‖) ])1/2 (by Theorem A.2).Recall that ‖‖gˆ1‖‖ψ2 = O(κ + 1) and∥∥∥‖gˆ1‖2∥∥∥ψ1= O(κ + 1)2 (by Claim 6.26). Therefore, we may bound theMGF’s of ‖gˆ1‖ and ‖gˆ1‖2 using Claim 6.14 for the former and Claim 6.21 for the latter. That is we may write:E[exp(2λ ‖gˆ1‖2)]≤ exp(2λ (κ+1)2) for all λ ∈ [0, 12(κ+1)2],andE [exp(8λ ‖gˆ1‖) ]≤ exp(8λ (κ+1)2)for all λ ∈ [0, 18(κ+1)2].Hence, we may plug in these MGF bounds to obtainE[exp(λ ‖x2− x∗‖2)]≤ exp(4λ )exp(λ (κ+1)2)exp(4λ (κ+1)2),for all λ ∈ (0, 18(κ+1)2 ]. Hence,E[exp(λ ‖x2− x∗‖2)]≤ exp(4λ +5λ (κ+1)2)≤ exp(9λ (κ+1)2) ,for all λ ∈ (0, 18(κ+1)2 ]. 6.3.3 Suffix averagingThe following is an extension of Theorem 1.17 to the case of subgaussian noise.Theorem 6.37. Suppose f is 1-strongly convex and 1-Lipschitz. Consider running Algorithm 1 for T iterationswith step size ηt = 1/t. Let x∗ = argminx∈X f (x). Suppose that there exist κ > 0, such that ‖zˆt |Ft−1‖ψ2 ≤ κ76for every t. Then, with probability at least 1−δ ,f(1T/2+1T∑t=T/2xt)− f (x∗) ≤ O((κ+1)2log(1/δ )T).Proof. By Lemma 3.14 with w = x∗ we haveT∑t=T/2[ f (xt)− f (x∗)] ≤ 12T∑t=T/2ηt ‖gˆt‖2︸ ︷︷ ︸(a)+12ηT/2∥∥xT/2− x∗∥∥2︸ ︷︷ ︸(b)+T∑t=T/2〈 zˆt , xt − x∗ 〉︸ ︷︷ ︸(c). (6.1)It suffices to bound each term of the right hand side of (6.1) by O(κ2 log(1/δ )) with probability at least 1−δ .(a). By Claim 6.26, we have∥∥∥∥∥ T∑t=T/2ηt ‖gˆt‖2∥∥∥∥∥ψ1≤T∑t=T/2ηt∥∥∥‖gˆt‖2∥∥∥ψ1≤ O((κ+1)2).Hence, we apply Claim 6.23 to bound (a) by O((κ+1)2 log(1/δ ))with probability at least 1−δ .(b). We have already bounded (b) by O((κ+1)2 log(1/δ ))in Theorem 6.32.(c). To bound (c), we will come up with a high probability bound on the sum of squared conditional magni-tudes of (c) (observe that (c) is a martingale with conditionally subgaussian increments) and then applyour transition from high probability bounds on the SSCM to high probability bounds on martingales(Corollary 6.40). The SSCM of (c) is given by ∑Tt=T/2 ‖xt − x∗‖2. Indeed, by Theorem 6.32, this isbounded by O((κ+1)2 log(1/δ ))with probability at least 1−δ . This translates into a high probabilitybound on (c) using Corollary 6.40. Indeed, take at = zˆt , bt = xt − x∗, and R = κ2. This yields a bound ofO(κ (κ+1) log(1/δ )) with probability 1−δ on (c) as desired.6.3.4 Proof of Theorem 6.35Theorem 6.35. Let (Xt)Tt=1 be a stochastic process and let (Ft)Tt=1 be a filtration such that Xt isFt-measurableand Xt is non-negative almost surely. Let αt ∈ [0,1) and βt ,γt ≥ 0 for every t. Let wˆt beFt+1-measurable suchthat ‖wˆt |Ft‖ψ2 ≤ τ for every t and E [ wˆt | Ft ] = 0. Let yˆt be Ft+1-measurable such that ‖yˆt |Ft‖ψ1 ≤ ρfor every t. Suppose Xt+1 ≤ αtXt + βtwˆt√Xt + γt yˆt , for every t. Assume that E [exp(λX1) ] ≤ exp(λK), forλ ∈ (0,1/K]. Then,• For every t, Pr [Xt ≥ K log(1/δ ) ]≤ eδ ,• If σ1, . . . ,σT ≥ 0, then Pr[∑Tt=1σtXt ≥ K log(1/δ )∑Tt=1σt]≤ eδ ,77where K = maxTt=1(2γtρ1−αt ,4β 2t τ21−αt).Proof (of Theorem 6.35). We begin by deriving a recursive MGF bound on Xt . The proof of this recursiveMGF bound differs from the proof of Claim 4.6 because in Claim 4.6 after conditioning onFt , we were left tobound the MGF of a subgaussian random variable. In this case however, due to the presence of yˆt , we will beleft to bound the MGF of the sum of a subgaussian and subexponential random variable. For this reason, theMGF bound we obtain is valid in a smaller region than the MGF bound from Claim 4.6.Claim 6.38. Suppose λ ∈ (0,minTt=1(12γtρ ,1−αt4β 2t τ2)]. Then, for every tE [exp(λXt+1) ] ≤ exp(λγtρ)E[λXt(1+αt2)].Proof (of Claim 6.38). Because ‖yˆt |Ft‖ψ1 ≤ ρ , we have, by Claim 6.21:E [exp(2λγt yˆt) | Ft ] ≤ exp(2λγtρ) for all λ ∈ (0, 12γtρ ]. (6.2)Furthermore, because ‖wˆt |Ft‖ψ2 ≤ τ , E [ wˆt | Ft ] = 0 and√Xt isFt-measurable, we have by Claim 6.17:E[exp(2λβtwˆt√Xt) | Ft ] ≤ exp(4λ 2β 2t τ2Xt) for all λ ∈ R. (6.3)Now, we put these MGF bounds together (assuming λ ∈ (0,minTt=1 12γtρ ]:E [exp(λXt+1) ] ≤ E[exp(λαtXt)E[exp(λβtwˆt√Xt)exp(λγt yˆt) | Ft]]≤ E[exp(λαtXt)E[exp(2λβtwˆt√Xt) | Ft ]1/2 E [exp(2λγt yˆt) | Ft ]1/2 ]≤ E[exp(λαtXt)exp(2λ 2β 2t τ2Xt)exp(λγtρ)] (by Eq. (6.2) and Eq. (6.3))= exp(λγtρ)E[exp(λXt(αt +2λβ 2t τ2))] .If we assume that λ ∈ (0,minTt=1 1−αt4β 2t τ2 ], then we haveE [exp(λXt+1) ] ≤ exp(λγtρ)E[exp(λXt(1+αt2))],as desired. Next, we prove an MGF bound on Xt .Claim 6.39. For every t, and for every λ ∈ (0,1/K], we have E [exp(λXt) ] ≤ exp(λK) . That is, ‖Xt‖ψ1 ≤K/ ln2.Proof. Let λ ∈ (0,1/K]. We proceed by induction over t. The base case holds by assumption. Assume that78E [exp(λXt) ]≤ exp(λK). Observe that λ satisfies the condition in Claim 6.38. Then,E [exp(λXt+1) ] ≤ exp(λγtρ)E[exp(λXt(1+αt2))](by Claim 6.38)≤ exp(λγtρ)exp(λK(1+αt2))(by induction hypothesis)= exp(λ(γtρ+K(1+αt2))).Hence, we need K ≥ K (1+αt2 )+ γtρ. Indeed, by definition of K,K ≥ 2γtρ1−αt =γtρ1− (1+αt2 ) ,which yields the desired inequality. Now, we can use Claim 6.39 to prove Theorem 6.35. The first claim in Theorem 6.35 follows from usingClaim 6.39 and the MGF bound to tail bound transition given by Claim A.7.Next, we prove the second claim from Theorem 6.35. Claim 6.39 gives that for every t and for all λ ∈(0,1/(σtK)], we have E [exp(λσtXt) ]≤ exp(λσtK). Hence, we can combine these MGF bounds using Lemma A.4to obtain E[exp(λ ∑Tt=1σtXt)] ≤ exp(λK∑Tt=1σt) for all λ ∈ (0,(K∑Tt=1σt)−1]. With this MGF bound inhand, we may apply the transition from MGF bounds to tail bounds given by Claim A.7 to complete the proofof the second claim from Theorem 6.35. 6.3.5 Using Theorem 1.11 with conditionally subgaussian incrementsCorollary 6.40. Let {Ft}Tt=1 be a filtration and suppose that at are Ft-measurable random variables and btareFt−1 measurable random variables. Further, suppose that1. There exists κ > 0 such that ‖at |Ft−1‖ψ2 ≤ κ for every t,2. E [at | Ft−1 ] = 0 for every t,3. ∑Tt=1 ‖bt‖2 ≤ R log(1/δ ) with probability at least 1−O(δ ).Define dt = 〈at , bt 〉. Then, ∑Tt=1 dt = O(κ√R log(1/δ ))with probability at least 1−O(δ ).Proof. The assumption that E [at | Ft−1 ] = 0 and ‖at |Ft−1‖ψ2 ≤ κ implyE [exp(λdt) | Ft−1 ] ≤ exp(λ 2κ2 ‖bt‖2),by Claim 6.17 because ‖dt |Ft−1‖ψ2 ≤ κ ‖bt‖.We may apply Lemma 4.3 with dt = 〈at , bt 〉, vt−1 = 2κ2 ‖bt‖2, αt = 0 for every i, and R(δ )= 2κ2R log(1/δ )to obtainPr[T∑t=1dt ≥ x]≤ δ + exp(− x216κ2R log(1/δ ).)The final term above is at most δ if x = 4κ√R log(1/δ ). Corollary 6.41. Let {Ft}Tt=1 be a filtration and suppose that at areFt-measurable random variables and bt areFt−1-measurable random variables. Define dt = 〈at , bt 〉. Assume there exists κ > 0 such that ‖at |Ft−1‖ψ2 ≤ κ79and E [at | Ft−1 ] = 0. Suppose that there exists R> 0 and non-negative values {αt}T−1t=1 where κ2 max{αt}T−1t=1 =O(κ√R), such that exactly one of the following holds for every δ ∈ (0,1) :1. ∑Tt=1 ‖bt‖2 ≤ ∑T−1t=1 αtdt +R log(1/δ ) with probability at least 1−O(δ ),2. ∑Tt=1 ‖bt‖2 ≤ ∑T−1t=1 αtdt +R√log(1/δ ) with probability at least 1−O(δ ).Then, ∑Tt=1 dt ≤ O(κ√R log(1/δ ))with probability at least 1−O(δ ).Proof. We prove only the first case, the second case can be proved by bounding√log(1/δ ) by log(1/δ ) andusing the proof of the first case.Proceeding as in the proof of Corollary 6.40, we haveE [exp(λdt) | Ft−1 ] ≤ exp(λ 2κ2 ‖bt‖2).We may now apply Lemma 4.3 with dt = 〈at , bt 〉 and vt−1 = 2κ2 ‖bt‖2, with αT = 0 and R(δ ) = R log(1/δ )to obtain:Pr[T∑t=1dt ≥ x]≤ δ + exp(− x2(8κ2 maxT−1t=1 (αt) · x+16κ2R)).Recalling that κ2 max{αt}T−1t=1 = O(κ√R), we may set x =Θ(κ√R log(1/δ ))to bound the final term by δ .80Chapter 7Conclusions and Future WorkIn this thesis we identified some gaps in the theoretical understanding of the role that the averaging of iteratesproduced by SGD plays in the non-smooth setting. We fully characterized the performance of the final iterate inboth the strongly-convex and non strongly-convex setting. That is, we have provided deterministic lower boundsmatching the expected upper bounds of Shamir and Zhang [43], answering a COLT 2012 open question [42].Moreover, we have extended the known expected convergence rates to hold with arbitrarily high probability.Next, we identified a shortage of high-probability upper bounds in the strongly-convex setting of non-smooth SGD. The work in this thesis establishes two optimal and tight (even including log(1/δ ) factors) high-probability upper bounds, using suffix-averaging from [36] and non-uniform averaging from [26].Along the way, we developed a new concentration inequality which extends the classical Freedman’s in-equality. This concentration inequality was a key probabilistic tool used on multiple occasions throughout thisthesis, perhaps highlighting it’s practical significance. The Generalized Freedman Inequality was used cruciallyto break the barrier of sub-optimal high probability results in the strongly-convex setting.7.1 Open questionsThere remain some interesting open questions. The first is whether or not there exists a sequence of step sizesfor which the individual iterates obtain, for all t, error o(log(t)/t) in the strongly-convex cases and o(log(t)/√t)in the Lipschitz case. Note that in the strongly convex case, Jain et al. [20] showed that for a fixed T , one canobtain a rate of O(1/T ) for the last iterate and that in the stochastic setting, no choice of step sizes yieldsexpected error O(1/t) for all t > 0.Another question is to determine the exact dependence on δ of our high probability upper bound on theerror of the final iterate. In the strongly-convex case, our best lower bound has an additive log(1/δ ) term,whereas our upper bound has a multiplicative factor of log(1/δ ). In contrast, for the final iterate in the Lipschitzcase, we do not know a log(1/δ ) lower bound on the error; conceivably the upper bound could be improved toO((log(T )+√log(1/δ ))/√T).81Bibliography[1] S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: A meta algorithm and itsapplications. Theory of Computing, 8(6):121–164, 2012. → page 3[2] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarialmulti-arm bandit problem. In Proceedings of FOCS, pages 322–331, 1995. → page 1[3] J. P. Bailey and G. Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the2018 ACM Conference on Economics and Computation, pages 321–338. ACM, 2018. → page 3[4] N. Bansal and A. Gupta. Potential-function proofs for first-order methods. arXiv:1712.04581, 2017. →page 1[5] V. Barbu and T. Precupanu. Convexity and optimization in Banach spaces. Springer Science & BusinessMedia, 2012. → page 52[6] P. L. Bartlett, V. Dani, T. Hayes, S. Kakade, A. Rakhlin, and A. Tewari. High-probability regret boundsfor bandit online linear optimization. In 21th Annual Conference on Learning Theory (COLT 2008), July2008. → page 9[7] S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in MachineLearning, 8(3–4), 2015. → pages 1, 8[8] P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S.-H. Teng. Electrical flows, laplaciansystems, and faster approximation of maximum flow in undirected graphs. In Proceedings of STOC,pages 273–282. ACM, 2011. → page 3[9] M. B. Cohen, Y. T. Lee, G. Miller, J. Pachocki, and A. Sidford. Geometric median in nearly linear time.In Proceedings of STOC, pages 9–21, 2016. → page 1[10] V. de la Peña. A general class of exponential inequalities for martingales and ratios. The Annals ofProbability, 27(1):537–564, 1999. → pages 5, 7[11] X. Fan, I. Grama, and Q. Liu. Exponential inequalities for martingales with applications. ElectronicJournal of Probability, 20, 2015. → pages 5, 7[12] V. Feldman, I. Mironov, K. Talwar, and A. Thakurta. Privacy amplification by iteration. In Proceedings ofFOCS, 2018. → page 1[13] D. A. Freedman. On tail probabilities for martingales. Annals of Probability, 3(1):100–118, 1975. →pages 5, 6, 7[14] Y. Freund, R. E. Schapire, et al. Adaptive game playing using multiplicative weights. Games andEconomic Behavior, 29(1-2):79–103, 1999. → page 382[15] N. J. Harvey, C. Liaw, Y. Plan, and S. Randhawa. Tight analyses for non-smooth stochastic gradientdescent. In Conference on Learning Theory, pages 1579–1613, 2019. → pages v, 38[16] E. Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3–4),2015. → page 1[17] E. Hazan and S. Kale. Beyond the regret minimization barrier: optimal algorithms for stochasticstrongly-convex optimization. The Journal of Machine Learning Research, 15(1):2489–2512, 2014. →pages iii, 2, 8, 9[18] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization.Machine Learning, 69(2-3):169–192, 2007. → page 2[19] J.-B. Hiriart-Urruty and C. Lemaréchal. Convex Analysis and Minimization Algorithms I.Springer-Verlag, 1996. → pages 11, 14, 86[20] P. Jain, D. Nagaraj, and P. Netrapalli. Making the last iterate of sgd information theoretically optimal. InConference on Learning Theory, pages 1752–1755, 2019. → pages 2, 81[21] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. InAdvances in neural information processing systems, pages 315–323, 2013. → page 1[22] S. M. Kakade and A. Tewari. On the generalization ability of online strongly convex programmingalgorithms. In NIPS, pages 801–808, 2008. → pages 2, 9[23] J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu. A simple, combinatorial algorithm for solving SDDsystems in nearly-linear time. In Proceedings of STOC, 2013. → page 1[24] P. Klein and N. E. Young. On the number of iterations for Dantzig–Wolfe optimization andpacking-covering approximation algorithms. SIAM Journal on Computing, 44(4):1154–1172, 2015. →page 62[25] A. Klenke. Probability theory: a comprehensive course. Springer Science & Business Media, 2013. →page 46[26] S. Lacoste-Julien, M. Schmidt, and F. Bach. A simpler approach to obtaining an o (1/t) convergence ratefor the projected stochastic subgradient method. arXiv preprint arXiv:1212.2002, 2012. → pagesiii, 37, 38, 39, 81[27] S. Lacoste-Julien, M. W. Schmidt, and F. R. Bach. A simpler approach to obtaining an O(1/t)convergence rate for the projected stochastic subgradient method, Dec. 2012. arXiv:1212.2002. → page 2[28] Y. T. Lee and A. Sidford. Efficient accelerated coordinate descent methods and faster algorithms forsolving linear systems. In Proceedings of FOCS, 2013. → page 1[29] Y. T. Lee, S. Rao, and N. Srivastava. A new approach to computing maximum flows using electricalflows. In Proceedings of STOC, pages 755–764, 2013. → page 1[30] P. Massart. Concentration inequalities and model selection. Springer, 2007. → page 40[31] C. McDiarmid. Concentration. In Probabilistic methods for algorithmic discrete mathematics, pages195–248. Springer, 1998. → page 5[32] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach tostochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009. → pages 1, 383[33] A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley,1983. → page 2[34] S. A. Plotkin, D. B. Shmoys, and É. Tardos. Fast approximation algorithms for fractional packing andcovering problems. Mathematics of Operations Research, 20(2):257–301, 1995. → page 3[35] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journalon Control and Optimization, 30(4):838–855, 1992. → page 3[36] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochasticoptimization. In Proceedings of ICML, 2012. → pages iii, 2, 3, 8, 9, 22, 23, 35, 38, 41, 42, 81[37] H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22(3):400–407, Sept. 1951. → page 1[38] W. Rudin. Real and Complex Analysis. McGraw-Hill, 1987. → page 58[39] D. Ruppert. Efficient estimations from a slowly convergent Robbins-Monro process. Technical report,Cornell University Operations Research and Industrial Engineering, 1988. → page 3[40] M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient.Mathematical Programming, 162(1-2):83–112, 2017. → page 1[41] S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter. Pegasos: primal estimated sub-gradient solver forSVM. Mathematical Programming, 127(1):3–30, 2011. → page 2[42] O. Shamir. Open problem: Is averaging needed for strongly convex stochastic gradient descent?Proceedings of the 25th Annual Conference on Learning Theory, PMLR, 23:47.1–47.3, 2012. → pagesiii, 2, 3, 81[43] O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence resultsand optimal averaging schemes. Proceedings of the 30th International Conference on Machine Learning,PMLR, 28(1):71–79, 2013. → pages 2, 7, 8, 9, 20, 81[44] T. Strohmer and R. Vershynin. A randomized solver for linear systems with exponential convergence. InProceedings of APPROX/RANDOM, 2006. → page 1[45] R. Vershynin. High-dimensional probability: An introduction with applications in data science.Cambridge University Press, 2018. → pages 67, 85[46] N. Vishnoi. Algorithms for convex optimization, 2018.https://nisheethvishnoi.wordpress.com/convex-optimization/. → page 184Appendix AStandard ResultsLemma A.1 (Exponentiated Markov). Let X be a random variable and λ > 0. Then Pr [X > t ]≤ exp(−λ t)E [exp(λX) ].Theorem A.2 (Cauchy-Schwarz). Let X and Y be random variables. Then |E [XY ]|2 ≤ E[X2 ]E[Y 2 ].Theorem A.3 (Generalized Hölder’s Inequality). Let X1, . . . ,Xn be random variables and p1, . . . , pn ≥ 1 be suchthat ∑i 1/pi = 1. Then E [∏ni=1|Xi| ]≤∏ni=1 (E [ |Xi|pi ])1/piProof. Follows by induction using Hölder’s inequality. Lemma A.4. Let X1, . . . ,Xn be random variables and K1, . . . ,Kn > 0 be such that E [exp(λXi) ]≤ exp(λKi) forall 0< λ ≤ 1/Ki. Then E [exp(λ ∑ni=1 Xi) ]≤ exp(λ ∑ni=1 Ki) for all 0< λ ≤ 1/∑ni=1 Ki.Proof. Let pi =∑nj=1 K j/Ki and observe that piKi =∑nj=1 K j. By assumption, if λ pi≤ 1/Ki (i.e. λ ≤ 1/∑nj=1 K j)then E [exp(λ piXi) ]≤ exp(λ piKi). Applying Theorem A.3, we conclude thatE[exp(λn∑i=1Xi)]≤n∏i=1E [exp(λ piXi) ]1/pi ≤n∏i=1exp(λ piKi)1/pi = exp(λn∑i=1Ki).Lemma A.5 (Hoeffding’s Lemma). Let X be any real valued random variable with expected value E [X ] = 0and such that a≤ X ≤ b almost surely. Then, for all λ ∈ R, E [exp(λX) ]≤ exp(λ 2(b−a)2/8).Claim A.6 ([45, Proposition 2.5.2]). Suppose there is c > 0 such that for all 0 < λ ≤ 1c , E[exp(λ 2X2)] ≤exp(λ 2c2). Then, if X is mean zero it holds thatE[exp(λX)]≤ exp(λ 2c2),for all λ ∈ R.Proof. Without loss of generality, assume c = 1; otherwise replace X with X/c. Using the numeric inequalityex ≤ x+ex2 which is valid for all x ∈R, if |λ | ≤ 1 then E [exp(λX) ]≤ E [λX ]+E[exp(λ 2X2)]≤ exp(λ 2). Onthe other hand, if |λ | ≥ 1, we may use the numeric inequality1 ab≤ a2/2+b2/2, valid for all a,b ∈R, to obtainE [exp(λX) ]≤ E[exp(λ 2/2+X2/2)]≤ exp(λ 2/2)exp(λ 2/2) = exp(λ 2).1Young’s Inequality85Claim A.7. Suppose X is a random variable such that there exists constants c and C such that E [exp(λX) ]≤cexp(λC) for all 0< λ ≤ 1/C. Then, Pr [X ≥C log(1/δ ) ]≤ ceδ .Proof. Apply Lemma A.1 to Pr [X ≥ t ] to get Pr [X ≥ t ]≤ cexp(−λ t+λC). Set λ = 1/C and t =C log(1/δ )to complete the proof. Claim A.8 ([19, Eq. (3.1.6)]). Let X be a convex set and x ∈X ⊆ Rn. Then ‖ΠX (y)− x‖ ≤ ‖y− x‖ for ally ∈ Rn.Claim A.9 ([19, 4.2.1]). Let A : Rn→ Rm be a linear map and let g be a finite convex function on Rm. Then∂ (g◦A)(x) = AT∂g(Ax) for all x ∈ Rm.A.1 Useful scalar inequalitiesClaim A.10. For 1≤ a≤ b, ∑bk=a 1√k ≤ 2b−a+1√b.Proof.b∑k=a1√k≤∫ ba−11√xdx = 2(√b−√a−1) = 2 b−a+1√b+√a−1 .Claim A.11. For any 1≤ j ≤ t ≤ T , we have t− j(T− j+1)√t ≤ 1√T .Proof. The function g(x) = x− j√x has derivativeg′(x) =1√x(1− x− j2x)=1√x(12+j2x).This is positive for all x> 0 and j ≥ 0, and sot− j√t≤ T − j√T,for all 0< t ≤ T . This implies the claim. Claim A.12. Assume 0≤ k and k+1≤ m.m∑`=k+11`2≤ 1k− 1m.Proof. The sum may be upper-bounded by an integral as follows:m∑`=k+11`2≤∫ mk1x2dx =1k− 1m.86Claim A.13. Let α j = 1(T− j)(T− j+1) . Let a,b be such that a≤ b< T . Then,b∑j=aα j =1T −b −1T −a+1 ≤1T −b .Proof.b∑j=aα j =b∑j=a1(T − j)(T − j+1) =b∑j=a(1T − j −1T − ( j−1)),which is a telescoping sum. Claim A.14. Suppose a< b. Then, log(b/a)≤ (b−a)/a.Claim A.15. Let b≥ a> 1. Then, ∑bi=a 1i ≤ log(b/(a−1)).87
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Understanding the role of averaging in non-smooth stochastic gradient descent
Text