Tight Analyses for Non-Smooth Stochastic Gradient Descent

Introduction

Stochastic gradient descent (SGD) is one of the oldest randomized algorithms, dating back to 1951 . It is a very simple and widely used iterative method for minimizing a function. In a nutshell, the method works by querying an oracle for a noisy estimate of a subgradient, then taking a small step in the opposite direction. The simplicity and effectiveness of this algorithm has established it both as an essential tool for applied machine learning , and as a versatile framework for theoretical algorithm design.

In theoretical algorithms, SGD often appears in the guise of coordinate descent, an important special case in which each gradient estimate has a single non-zero coordinate. Some of the fast algorithms for Laplacian linear systems are based on coordinate descent (and the related Kaczmarz method ). Multi-armed Bandits were discovered years ago to be a perfect setting for coordinate descent : the famous Exp3 algorithm combines coordinate descent and the multiplicative weight method. Recent work on the geometric median problem gave a sublinear time algorithm based on SGD, and very recently a new privacy amplification technique has been developed that injects noise to the subgradients while executing SGD. Surveys and monographs discussing gradient descent and aimed at a theoretical CS audience include Bansal and Gupta , Bubeck , Hazan , and Vishnoi .

The efficiency of SGD is usually measured by the rate of decrease of the error — the difference in value between the algorithm’s output and the true minimum. The optimal error rate is known under various assumptions on $f$, the function to be minimized. In addition to convexity, common assumptions are that $f$ is smooth (gradient is Lipschitz) or strongly convex (locally lower-bounded by a quadratic). Strongly convex functions often arise due to regularization, whereas smooth functions can sometimes be obtained by smoothening approximations (e.g., convolution). Existing analyses show that, after $T$ steps of SGD, the expected error of the final iterate is $O(1/\sqrt{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 paper. In theoretical algorithms and discrete optimization, the convex functions that arise are often non-smooth. For example, the objective for the geometric median problem is a (sum of) 2-norms , so Lipschitz but not smooth. Similarly, formulating the minimum $s$-$t$ cut problem as convex minimization , the objective is a 1-norm, so Lipschitz but not smooth. In machine learning, the objective for regularized support vector machines is strongly convex but not smooth.

A trouble with the non-smooth setting is that the error of (even deterministic) gradient descent need not decrease monotonically with $T$, so it is not obvious how to analyze the error of the final iterate. A workaround, known as early as , is to output the average of the iterates. Existing analyses of SGD show that the expected error of the average is $\Theta(1/\sqrt{T})$ for Lipschitz functions , which is optimal, whereas for functions that are also strongly convex the average has error $\Theta(\log(T)/T)$ with high probability, which is not the optimal rate. An alternative algorithm, more complicated than SGD, was discovered by Hazan and Kale ; it achieves the optimal expected error rate of $O(1/T)$. Suffix averaging, a simpler approach in which the last half of the SGD iterates are averaged, was also shown to achieve expected error $O(1/T)$ , although implementations can be tricky or memory intensive if the number of iterations $T$ is unknown a priori. Non-uniform averaging schemes with optimal expected error rate and simple implementations are also known , although the solutions may be less interpretable.

Shamir asked the very natural question of whether the final iterate of SGD achieves the optimal rate in the non-smooth scenario, as it does in the smooth scenario. If true, this would yield a very simple, implementable and interpretable form of SGD. Substantial progress on this question was made by Shamir and Zhang , who showed that the final iterate has expected error $O(\log(T)/\sqrt{T})$ for Lipschitz $f$, and $O(\log(T)/T)$ for strongly convex $f$. Both of these bounds are a $\log(T)$ factor worse than the optimal rate, so Shamir and Zhang write

An important open question is whether the $O(\log(T)/T)$ [expected] rate we obtained on [the last iterate], for strongly-convex problems, is tight. This question is important, because running SGD for $T$ iterations, and returning the last iterate, is a very common heuristic. In fact, even for the simpler case of (non-stochastic) gradient descent, we do not know whether the behavior of the last iterate… is tight.

Our work shows that the $\log(T)$ factor is necessary, both for Lipschitz functions and for strongly convex functions, even for non-stochastic gradient descent. So both of the expected upper bounds due to Shamir and Zhang are actually tight. This resolves the first question of Shamir . 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 average a constant fraction of the iterates to achieve the optimal rate.

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 of SGD would yield high-probability bounds, but this approach is not as efficient as it might seem It is usually the case that selecting the best of many independent trials is very inefficient. Such a scenario, which is very common in uses of SGD, arises if $f$ is defined as $\sum_{i=1}^{m}f_{i}$ or $\operatorname{E}_{\omega}\left[\,f_{\omega}\,\right]$. In such scenarios, evaluating $f$ exactly could be inefficient, and even estimating it to within error $1/T$ requires $\Theta(T^{2})$ samples via a Hoeffding bound, whereas SGD uses only $O(T)$ samples. . So it is both interesting and useful that high-probability bounds hold for a single execution of SGD. Some known high-probability bounds for the strongly convex setting include , for uniform averaging, and , which give a suboptimal bound of $O(\log\log(T)/T)$ for suffix averaging (and a variant thereof). In this work, we give two high probability bounds on the error of SGD for strongly convex functions: $O(1/T)$ for suffix averaging and $O(\log(T)/T)$ for the final iterate. Both of these are tight. (Interestingly, the former is used as an ingredient for the latter.) The former answers a question of Rakhlin et al. [28, §6], and the latter resolves the second question of Shamir . For Lipschitz functions, we prove a high probability bound of $O(\log(T)/\sqrt{T})$ for the final iterate, which is also tight.

Our work can also be seen as extending a line of work on understanding the difference between an average of the iterates or the last iterate of an iterative process. For instance, one of the most important results in game theory is that the multiplicative weights update algorithm converges to an equilibrium , i.e. the set of players are required to play some sort of “coordinated average” of their past strategies. Recently, studied the convergence behaviour of players’ individual strategies and found that the strategies diverge and hence, coordination (i.e. averaging) is needed to obtain an equilibrium. In a similar spirit, our work shows that the iterates of gradient descent have a sub-optimal convergence rate, at least for non-smooth convex functions, and thus, some form of averaging is needed to achieve the optimal rate. It is an interesting direction to see whether or not this is necessary in other iterative methods as well. For instance, the multiplicative weights update algorithm can be used to give an iterative algorithm for maximum flow , or linear programming in general , but also requires some form of averaging. We hope that this paper contributes to a better understanding on when averaging is necessary in iterative processes.

Preliminaries

We say that $f$ is $L$-Lipschitz if $\left\lVert g\right\rVert\leq L$ for all $x\in\mathcal{X}$ and $g\in\partial f(x)$. For the remainder of this paper, unless otherwise stated, we make the assumption that $\alpha=1$ and $L=1$; this is only a normalization assumption and is without loss of generality (see Appendix F). For the sake of simplicity, we also assume that $\left\lVert\hat{z}\right\rVert\leq 1$ a.s. although our arguments generalize to the setting when $\hat{z}$ are sub-Gaussian (see Appendix F).

Let $\Pi_{\mathcal{X}}$ denote the projection operator on $\mathcal{X}$. The (projected) stochastic gradient algorithm is given in Algorithm 1. Notice that there the algorithm maintains a sequence of points and there are several strategies to output a single point. The simplest strategy is to simply output $x_{T+1}$. However, one can also consider averaging all the iterates or averaging only a fraction of the final iterates . Notice that the algorithm also requires the user to specify a sequence of step sizes. The optimal choice of step size is known to be $\eta_{t}=\Theta(1/t)$ for strongly convex functions , and $\eta_{t}=\Theta(1/\sqrt{t})$ for Lipschitz functions. For our analyses, we will use a step size of $\eta_{t}=1/t$ for strongly convex functions and $\eta_{t}=1/\sqrt{t}$ for Lipschitz functions.

Our Contributions

Our main results are bounds on the error of the final iterate of stochastic gradient descent for non-smooth, convex functions.

We prove an $\Omega(\log(T)/T)$ lower bound, even in the non-stochastic case, and an $O(\log(T)\log(1/\delta)/T)$ upper bound with probability $1-\delta$.

Lipschitz functions.

We prove an $\Omega(\log(T)/\sqrt{T})$ lower bound, even in the non-stochastic case, and an $O(\log(T)\log(1/\delta)/\sqrt{T})$ upper bound with probability $1-\delta$.

1 High probability upper bounds

Suppose $f$ is $1$-strongly convex and $1$-Lipschitz. Suppose that $\hat{z}_{t}$ (i.e., $\operatorname{E}\left[\,\hat{g_{t}}\,\right]-\hat{g_{t}}$, the noise of the stochastic gradient oracle) has norm at most $1$ almost surely. Consider running Algorithm 1 for $T$ iterations with step size $\eta_{t}=1/t$. Let $x^{*}=\operatornamewithlimits{argmin}_{x\in\mathcal{X}}f(x)$. Then, with probability at least $1-\delta$,

Suppose $f$ is and $1$-Lipschitz and $\mathcal{X}$ has diameter $1$. Suppose that $\hat{z}_{t}$ (i.e., $\operatorname{E}\left[\,\hat{g_{t}}\,\right]-\hat{g_{t}}$, the noise of the stochastic gradient oracle) has norm at most $1$ almost surely. Consider running Algorithm 1 for $T$ iterations with step size $\eta_{t}=1/\sqrt{t}$. Let $x^{*}=\operatornamewithlimits{argmin}_{x\in\mathcal{X}}f(x)$. Then, with probability at least $1-\delta$,

The assumptions on the strong convexity parameter, Lipschitz parameter, and diameter are without loss of generality; see Appendix F. The bounded noise assumption for the stochastic gradient oracle is made only for simplicity; our analysis can be made to go through if one relaxes the a.s. bounded condition to a sub-Gaussian condition. We also remark that a linear dependence on $\log(1/\delta)$ is necessary for strongly convex functions; see Appendix G.

Our main probabilistic tool to prove Theorem 3.1 and Theorem 3.2 is a new extension of the classic Freedman inequality to a setting in which the martingale exhibits a curious phenomenon. Ordinarily a martingale is roughly bounded by the square root of its total conditional variance (this is the content of Freedman’s inequality). We consider a setting in which the total conditional variance As stated, Theorem 3.3 assumes a conditional sub-Gaussian bound on the martingale difference sequence, whereas Freedman assumes both a conditional variance bound and an almost-sure bound. These assumptions are easily interchangeable in both our proof and Freedman’s proof. For example, Freedman’s inequality with the sub-Gaussian assumption appears in [9, Theorem 2.6]. is itself bounded by (a linear transformation of) the martingale. We refer to this as a “chicken and egg” phenomenon.

Let $\{d_{i},\mathcal{F}_{i}\}_{i=1}^{n}$ be a martingale difference sequence. Suppose $v_{i-1}$, $i\in[n]$ are positive and $\mathcal{F}_{i-1}$-measurable random variables such that $\operatorname{E}\left[\,\exp(\lambda d_{i})\,\mid\,\mathcal{F}_{i-1}\,\right]\leq\exp\left(\frac{\lambda^{2}}{2}v_{i-1}\right)$ for all $i\in[n],\,\lambda>0$. Let $S_{t}=\sum_{i=1}^{t}d_{i}$ and $V_{t}=\sum_{i=1}^{t}v_{i-1}$. Let $\alpha_{i}\geq 0$ and set $\alpha=\max_{i\in[n]}\alpha_{i}$. Then

The proof of Theorem 3.3 appears in Appendix C. Freedman’s Inequality (as formulated in [9, Theorem 2.6], up to constants) simply omits the terms highlighted in yellow, i.e., it sets $\alpha=0$.

2 Lower bounds

More generally, any weighted average $\bar{x}$ of the last $k$ iterates has

Thus, suffix averaging must average a constant fraction of iterates to achieve the optimal $O(1/T)$ error.

More generally, any weighted average $\bar{x}$ of the last $k$ iterates has

Furthermore, the value of $f$ strictly monotonically increases for the first $T$ iterations:

In order to incur a $\log T$ factor in the error of the $T{{}^{\textrm{th}}}$ iterate, Theorem 3.4 and Theorem 3.5 constructs a function $f_{T}$ parameterized by $T$. It is also possible to create a single function $f$, independent of $T$, which incurs the $\log T$ factor for infinitely many $T$. This is described in Remark B.5.

3 High probability upper bound for suffix averaging

Interestingly, our proof of Theorem 3.1 requires understanding the suffix average. (In fact this connection is implicit in ). Hence, en route, we prove the following high probability bound on the error of the average of the last half of the iterates of SGD.

Suppose $f$ is $1$-strongly convex and $1$-Lipschitz. Consider running Algorithm 1 for $T$ iterations with step size $\eta_{t}=1/t$. Let $x^{*}=\operatornamewithlimits{argmin}_{x\in\mathcal{X}}f(x)$. Then, with probability at least $1-\delta$,

This upper bound is optimal. Indeed, Appendix G shows that the error is $\Omega(\log(1/\delta)/T)$ even for the one-dimensional function $f(x)=x^{2}/2$.

Theorem 3.7 is an improvement over the O\big{(}\log(\log(T)/\delta)/T\big{)} bounds independently proven by Rakhlin et al. (for suffix averaging) and Hazan and Kale (for EpochGD). Once again, we defer the statement of the theorem for general strongly-convex and Lipschitz parameters to Appendix F.

Techniques

Final 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 of expectation, one can plug in the expected subgradient, thus eliminating the noise [6, §6.1].

High probability bounds are more difficult. (Indeed, it is not a priori obvious that the error of the final iterate is tightly concentrated.) A high probability analysis must somehow control the total noise that accumulates from each 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 $(X_{t})$ is the martingale of the accumulated noise and let $V_{t-1}=\operatorname{E}\left[\,(X_{t}-X_{t-1})^{2}\,\mid\,X_{1},...,X_{t-1}\,\right]$ be the conditional variance at time $t$. A significant technical step of our analysis (Lemma 7.4) shows that the total conditional variance (TCV) of the accumulated noise exhibits the “chicken and egg” phenomenon alluded to in the discussion of Theorem 3.3. Roughly speaking, we have $\sum_{t=1}^{T}V_{t-1}\leq\alpha X_{T-1}+\beta$ where $\alpha,\beta>0$ are scalars. Since Freedman’s inequality shows that $X_{T}\lesssim\sqrt{\sum_{t=1}^{T}V_{T}}$, an inductive argument gives that $X_{T}\lesssim\sqrt{\alpha X_{T-1}+\beta}\lesssim\sqrt{\alpha\sqrt{\alpha X_{T-2}+\beta}+\beta}\lesssim\cdot\cdot\cdot$. This naive analysis involves invoking Freedman’s inequality $T$ times, so a union bound incurs an extra factor $\log T$ in the bound on $X_{T}$. This can be improved via a trick : by upper-bounding the TCV by a power-of-two (and by $T$), it suffices to invoke Freedman’s inequality $\log T$ times, which only incurs an extra factor $\log\log T$ in the bound on $X_{T}$.

Notice that this analysis actually shows that $X_{t}\lesssim\sqrt{\sum_{i=1}^{t}V_{i}}$ for all $t\leq T$, whereas the original goal was only to control $X_{T}$. Any analysis that simultaneously controls all $X_{t}$, $t\leq T$, must necessarily incur an extra factor $\log\log T$. This is a consequence of the Law of the Iterated LogarithmLet $X_{t}\in\{-1,+1\}$ be uniform and i.i.d. and $S_{T}=\sum_{t=1}^{T}X_{t}$. The Law of the Iterated Logarithm states that $\limsup_{T}\frac{S_{T}}{\sqrt{2T\log\log T}}=1$ a.s.. Previous work employs exactly such an analysis and incurs the $\log\log T$ factor. Rakhlin et al. explicitly raise the question of whether this $\log\log T$ factor is necessary.

Our work circumvents this issue by developing a generalization of Freedman’s Inequality (Theorem 3.3) to handle martingales of the above form, which ultimately yields optimal high-probability bounds. We are no longer hindered by the Law of the Iterated Logarithm because our variant of Freedman’s Inequality does not require 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 iterates computed by SGD (Lemma 7.3). This is useful because, by the subgradient inequality, the change in the error at different iterations can be bounded using the distance between iterates. Various naive approaches yield a bound of the form $\left\lVert x_{a}-x_{b}\right\rVert^{2}\leq\frac{(b-a)^{2}}{\min\left\{a^{2},b^{2}\right\}}$ $\left\lVert x_{a}-x_{b}\right\rVert^{2}\leq\frac{(b-a)^{2}}{\min\left\{a^{2},b^{2}\right\}}$ (in the strongly convex case). We derive a much stronger bound, comparable to $\left\lVert x_{a}-x_{b}\right\rVert^{2}\leq\frac{\lvert b-a\rvert}{\min\left\{a^{2},b^{2}\right\}}$. Naturally, in the stochastic case, there are additional noise terms that contribute to the technical challenge of our analysis. Nevertheless, this new distance bound could be useful in further understanding non-smooth gradient descent (even in the non-stochastic setting).

As in previous work on the strongly convex case , the error of the suffix average plays a critical role in bounding the error of the final iterate. Therefore, we also need a tight high probability bound on the error of the suffix average.

To complete the optimal high probability analysis on the final iterate, we need a high probability bound on the suffix average that avoids the $\log\log T$ factor. As in the final iterate setting, the accumulated noise for the suffix average forms a zero-mean martingale, $(X_{t})_{T/2}^{T}$, but now the conditional variance at step $t$ satisfies $V_{t}\leq\alpha_{t}V_{t-1}+\beta_{t}\hat{w}_{t}\sqrt{V_{t-1}}+\gamma_{t}$, where $\hat{w}_{t}$ is a mean-zero random variable and $\alpha_{t},\beta_{t}$ and $\gamma_{t}$ are constants. In , using Freedman’s Inequality combined with the trick from , they obtain a bound on a similar martingale but do so over all time steps and incur a $\log\log T$ factor. However, our goal is only to bound $X_{T}$ and according to Freedman’s Inequality $X_{T}\lesssim\sqrt{\sum_{t=T/2}^{T}V_{t}}$. So, our goal becomes to bound $\sum_{t=T/2}^{T}V_{t}$. To do so, we develop a probabilistic tool to bound the $t{{}^{\textrm{th}}}$ iterate of a stochastic process that satisfies a recursive dependence on the $(t-1){{}^{\textrm{th}}}$ iterate similar to the one exhibited by $V_{t}$.

Let $(X_{t})_{t=1}^{T}$ be a stochastic process and let $(\mathcal{F}_{t})_{t=1}^{T}$ be a filtration such that $X_{t}$ is $\mathcal{F}_{t}$ measurable and $X_{t}$ is non-negative almost surely. Let $\alpha_{t}\in[0,1)$ and $\beta_{t},\gamma_{t}\geq 0$ for every $t$. Let $\hat{w}_{t}$ be a mean-zero random variable conditioned on $\mathcal{F}_{t}$ such that $\left\lvert\hat{w}_{t}\right\rvert\leq 1$ almost surely for every $t$. Suppose that $X_{t+1}\leq\alpha_{t}X_{t}+\beta_{t}\hat{w}_{t}\sqrt{X_{t}}+\gamma_{t}$ for every $t$. Then, the following hold.

where $K=\max_{1\leq t\leq T}\left(\frac{2\gamma_{t}}{1-\alpha_{t}},\frac{2\beta_{t}^{2}}{1-\alpha_{t}}\right)$.

The recursion $X_{t+1}\leq\alpha_{t}+\beta_{t}\hat{w}_{t}\sqrt{X_{t}}+\gamma_{t}$ presents two challenges that make it difficult to analyze. Firstly, the fact that it is a non-linear recurrence makes it unclear how one should unwind $X_{t+1}$. Furthermore, unraveling the recurrence introduces many $\hat{w}_{t}$ terms in a non-trivial way. Interestingly, if we instead consider the moment generating function (MGF) of $X_{t+1}$, then we can derive an analogous recursive MGF relationship which removes this non-linear dependence and removes the $\hat{w}_{t}$ term. This greatly simplifies the recursion and leads to a surprisingly clean analysis. The proof of Theorem 4.1 can be found in Appendix D. (The recursive MGF bound which removes the non-linear dependence is by Claim D.1.)

Deterministic lower bound.

As mentioned above, a challenge with non-smooth gradient is that the error of the $T{{}^{\textrm{th}}}$ iterate may not monotonically decrease with $T$, even in the deterministic setting. The full extent of this non-decreasing behavior seems not to have been previously understood. We develop a technique that forces the error to be monotonically increasing for $\Omega(T)$ consecutive iterations. The idea is as follows. If GD takes a step in a certain direction, a non-differentiable point can allow the function to suddenly increase in that direction. If the function were one-dimensional, the next iteration of GD would then be guaranteed to step in the opposite direction, thereby decreasing the function. However, in higher dimensions, the second gradient step could be nearly orthogonal to the first step, and the function could have yet another non-differentiable point in this second direction. In sufficiently high dimensions, this behavior can be repeated for many iterations. The tricky aspect is designing the function to have this behavior while also being convex. We show that this is possible, leading to the unexpectedly large error in the $T{{}^{\textrm{th}}}$ iteration. We believe that this example illuminates some non-obvious behavior of gradient descent.

Lower bound on error of final iterate, strongly convex case

It is easy to see that $f$ is $1$-strongly convex due to the $\frac{1}{2}\left\lVert x\right\rVert^{2}$ term. Furthermore $f$ is $3$-Lipschitz over $\mathcal{X}$ because $\left\lVert\nabla H_{i}(x)\right\rVert\leq\left\lVert h_{i}\right\rVert+1$ and $\left\lVert h_{i}\right\rVert^{2}\leq 1+\frac{1}{4}\sum_{j=1}^{T}\frac{1}{(T-j)^{2}}<1+\frac{1}{2}$. Finally, the minimum value of $f$ over $\mathcal{X}$ is non-positive because $f(0)=0$.

In order to execute Algorithm 1 on $f$ we must specify a subgradient oracle. First, we require the following claim, which follows from standard facts in convex analysis [16, Theorem 4.4.2].

$\partial f(x)$ is the convex hull of $\left\{\;h_{i}+x\,:\,i\in\mathcal{I}(x)\;\right\}$, where $\mathcal{I}(x)=\left\{\;i\,:\,H_{i}(x)=f(x)\;\right\}$.

Our subgradient oracle is non-stochastic: given $x$, it simply returns $h_{i^{\prime}}+x$ where $i^{\prime}=\min\mathcal{I}(x)$.

Explicit description of iterates.

We will show inductively that these are precisely the first $T$ iterates produced by Algorithm 1 when using the subgradient oracle defined above. The following claim is easy to verify from the definition of $z_{t}$.

For $t\in[T+1]$, $z_{t}$ is non-negative. In particular, $z_{t,j}\geq\frac{1}{2(t-1)}$ for $j<t$ and $z_{t,j}=0$ for $j\geq t$.

$\left\lVert z_{1}\right\rVert=0$ and $\left\lVert z_{t}\right\rVert^{2}\leq\frac{1}{t-1}$ for $t>1$. Thus $z_{t}\in\mathcal{X}$ for all $t\in[T+1]$.

The “triangular shape” of the $h_{i}$ vectors allows us to determine the value and subdifferential at $z_{t}$.

$f(z_{t})=H_{t}(z_{t})$ for all $t\in[T+1]$. The subgradient oracle for $f$ at $z_{t}$ returns the vector $h_{t}+z_{t}$.

We claim that $h_{t}^{\textsf{T}}z_{t}=h_{i}^{\textsf{T}}z_{t}$ for all $i>t$. By definition, $z_{t}$ is supported on its first $t-1$ coordinates. However, $h_{t}$ and $h_{i}$ agree on the first $t-1$ coordinates (for $i>t$). This proves the first part of the claim.

Next we claim that $z_{t}^{\textsf{T}}h_{t}>z_{t}^{\textsf{T}}h_{i}$ for all $1\leq i<t$. This also follows from the definition of $z_{t}$ and $h_{i}$:

These two claims imply that $H_{t}(z_{t})\geq H_{i}(z_{t})$ for all $i\in[T+1]$, and therefore $f(z_{t})=H_{t}(z_{t})$. Moreover $\mathcal{I}(z_{t})=\left\{\;i\,:\,H_{i}(z_{t})=f(z_{t})\;\right\}=\left\{t,...,T+1\right\}$. Thus, when evaluating the subgradient oracle at the vector $z_{t}$, it returns the vector $h_{t}+z_{t}$. ∎

Since the subgradient returned at $z_{t}$ is determined by Claim 5.3, and the next iterate of SGD arises from a step in the opposite direction, a straightforward induction proof allows us to show the following lemma. A detailed proof is in Appendix B.1.

For the function $f$ constructed in this section, the vector $x_{t}$ in Algorithm 1 equals $z_{t}$, for every $t\in[T+1]$.

The value of the final iterate is easy to determine from Lemma 5.4 and Claim 5.3:

(Here the second inequality uses Claim 5.2.) This proves (3.1). A small modification of the last calculation proves (3.2); details may be found in Claim B.1. This completes the proof of Theorem 3.4.

Lower bound on error of final iterate, Lipschitz case

In this section we prove a lower bound result for Lipschitz functions analogous to those in Section 5. Specifically, we define a function $f=f_{T}$, depending on $T$, for which the final iterate produced by Algorithm 1 has $f(x_{T})=\Omega(\log(T)/\sqrt{T})$, thereby proving (3.3). Throughout this section we will assume that $\eta_{t}=\frac{c}{\sqrt{t}}$ for $c\geq 1$.

Note that $f$ is $1$-Lipschitz over $\mathcal{X}$ because

Also, the minimum value of $f$ over $\mathcal{X}$ is non-positive because $f(0)=0$.

In order to execute Algorithm 1 on $f$ we must specify a subgradient oracle. Similar to Claim 6.1, [16, Theorem 4.4.2] implies

$\partial f(x)$ is the convex hull of $\left\{\;h_{i}\,:\,i\in\mathcal{I}(x)\;\right\}$, where $\mathcal{I}(x)=\left\{\;i\,:\,h_{i}^{\textsf{T}}x=f(x)\;\right\}$.

Our subgradient oracle is as follows: given $x$, it simply returns $h_{i^{\prime}}+x$ where $i^{\prime}=\min\mathcal{I}(x)$.

Explicit description of iterates.

We will show inductively that these are precisely the first $T$ iterates produced by Algorithm 1 when using the subgradient oracle defined above.

For $t\in[T+1]$, $z_{t}$ is non-negative. In particular, $z_{t,j}\geq\frac{1}{4\sqrt{T}}$ for $j<t$ and $z_{t,j}=0$ for $j\geq t$.

By definition, $z_{t,j}=0$ for all $j\geq t$. For $j<t$,

We have $z_{t,j}=0$ for all $j\geq t$, and for $j<t$, we have

Since Claim 6.2 shows that $z_{t}\geq 0$, we have $\left\lVert z_{t}\right\rVert\leq 1$, and therefore $z_{t}\in\mathcal{X}$. ∎

The “triangular shape” of the $h_{i}$ vectors allows us to determine the value and subdifferential at $z_{t}$.

$f(z_{t})=h_{t}^{\textsf{T}}z_{t}$ for all $t\in[T+1]$. The subgradient oracle for $f$ at $z_{t}$ returns the vector $h_{t}$.

We claim that $h_{t}^{\textsf{T}}z_{t}=h_{i}^{\textsf{T}}z_{t}$ for all $i>t$. By definition, $z_{t}$ is supported on its first $t-1$ coordinates. However, $h_{t}$ and $h_{i}$ agree on the first $t-1$ coordinates (for $i>t$). This proves the first part of the claim.

Next we claim that $z_{t}^{\textsf{T}}h_{t}>z_{t}^{\textsf{T}}h_{i}$ for all $1\leq i<t$. This also follows from the definition of $z_{t}$ and $h_{i}$:

These two claims imply that $h_{t}^{\textsf{T}}z_{t}\geq h_{i}^{\textsf{T}}z_{t}$ for all $i\in[T+1]$, and therefore $f(z_{t})=h_{t}^{\textsf{T}}z_{t}$. Moreover $\mathcal{I}(z_{t})=\left\{\;i\,:\,h_{i}^{\textsf{T}}z_{t}=f(z_{t})\;\right\}=\left\{t,...,T+1\right\}$. Thus, when evaluating the subgradient oracle at the vector $z_{t}$, it returns the vector $h_{t}$. ∎

Since the subgradient returned at $z_{t}$ is determined by Claim 6.4, and the next iterate of SGD arises from a step in the opposite direction, a straightforward induction proof allows us to show the following lemma.

For the function $f$ constructed in this section, the vector $x_{t}$ in Algorithm 1 equals $z_{t}$, for every $t\in[T+1]$.

The proof is by induction. By definition $x_{1}=0$ and $z_{1}=0$, establishing the base case.

So assume $z_{t}=x_{t}$ for $t\leq T$; we will prove that $z_{t+1}=x_{t+1}$. Recall that Algorithm 1 sets $y_{t+1}=x_{t}-\eta_{t}g_{t}$, and that $\eta_{t}=\frac{c}{\sqrt{t}}$. By the inductive hypothesis, $x_{t}=z_{t}$. By Claim 6.4, the algorithm uses the subgradient $g_{t}=h_{t}$. Thus,

So $y_{t+1}=z_{t+1}$. Since $x_{t+1}=\Pi_{\mathcal{B}_{T}}(y_{t+1})$ by definition, and $y_{t+1}\in\mathcal{X}$ by Claim 6.3, we have $x_{t+1}=y_{t+1}=z_{t+1}$. ∎

The value of the final iterate is easy to determine from Lemma 5.4 and Claim 5.3:

(Here the second inequality uses Claim 6.2.) This proves (3.3). A small modification of the last calculation proves (3.4); details may be found in Claim B.2. The proof of (3.5) may be found in Subsection B.3. This completes the proof of Theorem 3.5.

Upper bound on error of final iterate, strongly convex case

We now turn to the proof of the upper bound on the error of the final iterate of SGD, in the case where $f$ is 1-strongly convex and 1-Lipschitz (Theorem 3.1). Recall that the step size used by Algorithm 1 in this case is $\eta_{t}=1/t$. We will write $\hat{g}_{t}=g_{t}-\hat{z}_{t}$, where $\hat{g}_{t}$ is the vector returned by the oracle at the point $x_{t}$, $g_{t}\in\partial f(x_{t})$, and $\hat{z}_{t}$ is the noise. Let $\mathcal{F}_{t}=\sigma(\hat{z}_{1},...,\hat{z}_{t})$ be the $\sigma$-algebra generated by the first $t$ steps of SGD. Finally, recall that $\left\lVert\hat{z}_{t}\right\rVert\leq 1$ and $\operatorname{E}\left[\,\hat{z}_{t}\,\mid\,\mathcal{F}_{t-1}\,\right]=0$.

We begin with the following lemma which can be inferred from the proof of Theorem 1 in Shamir and Zhang . For completeness, we provide a proof in Appendix E.

Let $f$ be 1-strongly convex and 1-Lipschitz. Suppose that we run SGD (Algorithm 1) with step sizes $\eta_{t}=1/t$. Then

Lemma 7.1 asserts that the error of the last iterate is upper bounded by the sum of the error of the suffix average and some noise terms (up to the additive $O(\log T/T)$ term). Thus, it remains to show that the error due to the suffix average is small with high probability (Theorem 3.7) and the noise terms are small. We defer the proof of Theorem 3.7 to Subsection 7.3. By changing the order of summation, we can write $Z_{T}=\sum_{t=T/2}^{T}\langle\>\hat{z}_{t},\,w_{t}\>\rangle$ where

The main technical difficulty is to show that $Z_{T}$ is small with high probability. Formally, we prove the following lemma, whose proof is outlined in Subsection 7.1.

$Z_{T}\leq O\left(\frac{\log(T)\log(1/\delta)}{T}\right)$ with probability at least $1-\delta$.

Given Theorem 3.7 and Lemma 7.2, the proof of Theorem 3.1 is immediate.

The main technical difficulty in the proof is to understand the noise term, which we have denoted by $Z_{T}$. Notice that $Z_{T}$ is a sum of a martingale difference sequence. The natural starting point is to better understand the TCV of $Z_{T}$ (i.e. $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$). We we will see that $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$ is bounded by a linear transformation of $Z_{T}$. This “chicken and egg” relationship inspires us to derive a new probabilistic tool (generalizing Freedman’s Inequality) to disentangle the total conditional variance from the martingale.

The main challenge in analyzing $\left\lVert w_{t}\right\rVert$ is precisely analyzing the distance $\left\lVert x_{t}-x_{j}\right\rVert$ between SGD iterates. A loose bound of $\left\lVert x_{t}-x_{j}\right\rVert^{2}\lesssim(t-j)\sum_{i=j}^{t}\frac{\left\lVert\hat{g}_{i}\right\rVert^{2}}{i^{2}}$ follows easily from Jensen’s Inequality. We prove the following tighter bound, which may be of independent interest. The proof is in Appendix E.

Suppose $f$ is 1-Lipschitz and 1-strongly convex. Suppose we run Algorithm 1 for $T$ iterations with step sizes $\eta_{t}=1/t$. Let $a<b$. Then,

Using Lemma 7.3 and some delicate calculations we obtain the following upper bound on $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$, revealing the surprisingly intricate relationship between $Z_{T}$ (the martingale) and $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$ (its TCV). This is the main technical step that inspired our probabilistic tool (the generalized Freedman’s Inequality).

There exists positive values $R_{1}=O\left(\frac{\log^{2}T}{T^{2}}\right)$, $R_{2}=O\left(\frac{\log T}{T}\right)$, $C_{t}=O(\log T)$, $A_{t}=O\left(\frac{\log T}{T^{2}}\right)$ such that

This bound is mysterious in that the left-hand side is an upper bound on the total conditional variance of $Z_{T}$, whereas the right-hand side essentially contains a scaled version of $Z_{T}$ itself. This is the “chicken and egg phenomenon” alluded to in Section 4, and it poses another one of the main challenges of bounding $Z_{T}$. This bound inspires our main probabilistic tool, which we restate for convenience here.

Theorem 3.3 (Generalized Freedman). Let $\{d_{i},\mathcal{F}_{i}\}_{i=1}^{n}$ be a martingale difference sequence. Suppose $v_{i-1}$, $i\in[n]$ are positive and $\mathcal{F}_{i-1}$-measurable random variables such that $\operatorname{E}\left[\,\exp(\lambda d_{i})\,\mid\,\mathcal{F}_{i-1}\,\right]\leq\exp\left(\frac{\lambda^{2}}{2}v_{i-1}\right)$ for all $i\in[n],\,\lambda>0$. Let $S_{t}=\sum_{i=1}^{t}d_{i}$ and $V_{t}=\sum_{i=1}^{t}v_{i-1}$. Let $\alpha_{i}\geq 0$ and set $\alpha=\max_{i\in[n]}\alpha_{i}$. Then

In order to apply Theorem 3.3, we need to refine Lemma 7.4 to replace the terms $\left\lVert x_{T/2}-x^{*}\right\rVert^{2}$ and $\sum_{t=T/2}^{T-1}\langle\>\hat{z}_{t},\,A_{t}(x_{t}-x^{*})\>\rangle$ with sufficient high probability upper bounds. In , they showed that $\left\lVert x_{t}-x^{*}\right\rVert^{2}\leq O(\log\log(T)/T)$ for all $\frac{T}{2}\leq t\leq T$ simultaneously, with high probability, so using that would give a slightly suboptimal result. In contrast, our analysis only needs a high probability bound on $\left\lVert x_{T/2}-x^{*}\right\rVert^{2}$ and $\sum_{t=T/2}^{T}A_{t}\left\lVert x_{t}-x^{*}\right\rVert^{2}$; this allows us to avoid a $\log\log T$ factor here. Indeed, we have

For all $t\geq 2$, $\left\lVert x_{t}-x^{*}\right\rVert^{2}\leq O\left(\log(1/\delta)/t\right)$ with probability $1-\delta$, and

Let $\sigma_{t}\geq 0$ for $t=2,...,T$. Then, $\sum_{t=2}^{T}\sigma_{t}\left\lVert x_{t}-x^{*}\right\rVert=O\left(\sum_{t=2}^{T}\frac{\sigma_{t}}{t}\log(1/\delta)\right)$ w.p. $1-\delta$.

The proof of Theorem 7.5, in Subsection 7.2, uses our tool for bounding recursive stochastic processes (Theorem 4.1). Therefore, we need to expose a recursive relationship between $\left\lVert x_{t+1}-x^{*}\right\rVert^{2}$ and $\left\lVert x_{t}-x^{*}\right\rVert^{2}$ that satisfies the conditions of Theorem 4.1. Interestingly, Theorem 7.5 is also the main ingredient in the analysis of the error of the suffix average (see Subsection 7.3). We now have enough to give our refined version of Lemma 7.4, which is now in a format usable by Freedman’s Inequality.

For every $\delta>0$ there exists positive values $R=O\left(\frac{\log^{2}T\log(1/\delta)}{T^{2}}\right)$, $C_{t}=O\left(\log T\right)$ such that $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}\leq R+\sum_{t=T/2}^{T-1}\frac{C_{t}}{t}\langle\>\hat{z}_{t},\,w_{t}\>\rangle,$ with probability at least $1-\delta$.

The lemma essentially follows from combining our bounds in Theorem 7.5 with an easy corollary of Freedman’s Inequality (Corollary C.4) which states that a high probability bound of $M$ on the TCV of a martingale implies a high probability bound of $\sqrt{M}$ on the martingale.

Let $R_{1}$, $R_{2}$, $C_{t}$, and $A_{t}$ be as in Lemma 7.4, and consider the resulting upper bound on $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$. The first claim in Theorem 7.5 gives $R_{2}\left\lVert x_{T/2}-x^{*}\right\rVert^{2}=O\left(\frac{\log^{2}T\log(1/\delta)}{T^{2}}\right)$ because $R_{2}=O\left(\log T/T\right)$.

By the second claim in Theorem 7.5, we have $\sum_{t=T/2}^{T-1}A_{t}^{2}\left\lVert x_{t}-x^{*}\right\rVert^{2}=O\left(\frac{\log^{2}T}{T^{4}}\log(1/\delta)\right)$ with probability at least $1-\delta$ because each $A_{t}=O\left(\frac{\log T}{T^{2}}\right)$. Hence, we have derived a high probability bound on the total conditional variance of $\sum_{t=T/2}^{T}\langle\>\hat{z}_{t},\,A_{t}(x_{t}-x^{*})\>\rangle$. Therefore, we turn this into a high probability bound on the martingale itself by applying Corollary C.4 and obtain $\sum_{t=T/2}^{T-1}\langle\>\hat{z}_{t},\,A_{t}(x_{t}-x^{*})\>\rangle=O\left(\frac{\log^{2}T\log(1/\delta)}{T^{2}}\right)$ with probability at least $1-\delta$. ∎

Now that we have derived an upper bound on the total conditional variance of $Z_{T}$ in the form required by our Generalized Freedman Inequality (Theorem 3.3), we are finally ready to prove Lemma 7.2 (our high probability upper bound on the noise, $Z_{T}$).

We have demonstrated that $Z_{T}$ satisfies the “Chicken and Egg” phenomenon with high probability. Translating this into a high probability upper bound on the martingale $Z_{T}$ itself is a corollary of Theorem 3.3.

Indeed, consider a filtration $\{\mathcal{F}_{t}\}_{t=T/2}^{T}$. Let $d_{t}=\langle\>a_{t},\,b_{t}\>\rangle$ define a martingale difference sequence where $\left\lVert a_{t}\right\rVert\leq 1$ and $\operatorname{E}\left[\,a_{t}\,\mid\,\mathcal{F}_{t-1}\,\right]=0$. Suppose there are positive values, $R$, $\alpha_{t}$, such that $\max_{t=T/2}^{T}\{\alpha_{t}\}=O\left(\sqrt{R}\right)$ and $\sum_{t=T/2}^{T}\left\lVert b_{t}\right\rVert^{2}\leq\sum_{t=T/2}^{T}\alpha_{t}d_{t}+R\log(1/\delta)$ with probability at least $1-\delta$. Then, Corollary C.5 bounds the martingale at time step $T$ by $\sqrt{R}\log(1/\delta)$ with high probability.

Observe that Lemma 7.6 allows us to apply Corollary C.5 with $a_{t}=\hat{z}_{t}$, $b_{t}=w_{t}$, $\alpha_{t}=(C_{t}/t)$ for $t=T/2,...,T-1$, $\alpha_{T}=0$, $\max_{t=T/2}^{T}\{\alpha_{t}\}=O\left(\log T/T\right)$, and $R=O\left(\log^{2}T/T^{2}\right)$ to prove Lemma 7.2. ∎

In this section, we prove Theorem 7.5. We begin with the following claim which can be extracted from .

Suppose $f$ is $1$-strongly-convex and $1$-Lipschitz. Define $Y_{t}=t\left\lVert x_{t+1}-x^{*}\right\rVert^{2}$ and $U_{t}=\langle\>\hat{z}_{t+1},\,x_{t+1}-x^{*}\>\rangle/\left\lVert x_{t+1}-x^{*}\right\rVert_{2}$. Then

This claim exposes a recursive relationship between $\left\lVert x_{t+1}-x^{*}\right\rVert^{2}$ and $\left\lVert x_{t}-x^{*}\right\rVert^{2}$ and inspires our probabilistic tool for recursive stochastic processes (Theorem 4.1). We prove Theorem 7.5 using this tool:

Consider the stochastic process $(Y_{t})_{t=1}^{T-1}$ where $Y_{t}$ is as defined by Claim 7.7. Note that $Y_{t}$ satisfies the conditions of Theorem 4.1 with $X_{t}=Y_{t}$, $\hat{w}_{t}=U_{t}$, $\alpha_{t}=\frac{t-2}{t-1}=1-1/(t-1)$, $\beta_{t}=2/\sqrt{t-1}$, and $\gamma_{t}=4/t$. Observe that $U_{t}$ is a $\mathcal{F}_{t+1}$ measurable random variable which is mean zero conditioned on $\mathcal{F}_{t}$ Furthermore, note that $\left\lvert U_{t}\right\rvert\leq 1$ with probability 1 because $\left\lVert\hat{z}_{t+1}\right\rVert\leq 1$ with probability 1. Furthermore, it is easy to check that $\max_{1\leq t\leq T}\left(\frac{2\gamma_{t}}{1-\alpha_{t}},\frac{2\beta^{2}}{1-\alpha_{t}}\right)=8$ with the above setup. So, we may apply Theorem 4.1 to obtain:

Recalling that $Y_{t}=t\left\lVert x_{t+1}-x^{*}\right\rVert^{2}$ and setting $\sigma_{t}^{\prime}=\sigma_{t}/t$ proves Theorem 7.5. ∎

3 Upper Bound on Error of Suffix Averaging

To complete the proof of the final iterate upper bound (Theorem 3.1), it still remains to prove the suffix averaging upper bound (Theorem 3.7). In this section, we prove this result as a corollary of the high probability bounds on $\left\lVert x_{t}-x^{*}\right\rVert^{2}$ that we obtained in the previous subsection.

It suffices to bound the right hand side of (7.2) by $O(\log(1/\delta))$ with probability at least $1-\delta$. Indeed, bounding $\left\lVert\hat{g}_{t}\right\rVert^{2}$ by 4, (a) in (7.2) is bounded by $O(1)$. Term (b) is bounded by $O(\log(1/\delta))$ by Theorem 7.5.

It remains to bound (c). Theorem 7.5 implies $\sum_{t=T/2}^{T}\left\lVert x_{t}-x^{*}\right\rVert^{2}=O(\log(1/\delta))$ with probability at least $1-\delta$. Therefore, Corollary C.4 shows that (c) is at most $O(\log(1/\delta))$ with probability at least $1-\delta$. ∎

Upper bound on error of final iterate, Lipschitz case: Proof Sketch

In 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 3.2). The proof of Theorem 3.2 closely resembles the proof of Theorem 3.1 and we will highlight the main important differences. Perhaps the most notable difference is that the analysis in the Lipschitz case does not require a high probability bound on $\left\lVert x_{t}-x^{*}\right\rVert^{2}$.

Recall that the step size used by Algorithm 1 in this case is $\eta_{t}=1/\sqrt{t}$. We will write $\hat{g}_{t}=g_{t}-\hat{z}_{t}$, where $\hat{g}_{t}$ is the vector returned by the oracle at the point $x_{t}$, $g_{t}\in\partial f(x_{t})$, and $\hat{z}_{t}$ is the noise. Let $\mathcal{F}_{t}=\sigma(\hat{z}_{1},...,\hat{z}_{t})$ be the $\sigma$-algebra generated by the first $t$ steps of SGD. Finally, recall that $\left\lVert\hat{z}_{t}\right\rVert\leq 1$ and $\operatorname{E}\left[\,\hat{z}_{t}\,\mid\,\mathcal{F}_{t-1}\,\right]=0$.

As before, we begin with a lemma which can be obtained by modifying the proof of Lemma 7.1 to replace applications of strong convexity with the subgradient inequality.

Let $f$ be 1-Lipschitz. Suppose that we run SGD (Algorithm 1) with step sizes $\eta_{t}=\frac{1}{\sqrt{t}}$. Then,

Lemma 8.1 asserts that the error of the last iterate is bounded by the sum of the error of the average of the iterates and some noise terms (up to the additive $O(\log T/\sqrt{T})$ term). A standard analysis (similar to the proof of Lemma E.1) reveals $\sum_{t=T/2}^{T}\left[f(x_{t})-f(x^{*})\right]\leq O({\sqrt{T}})+\sum_{t=T/2}^{T}\langle\>\hat{z}_{t},\,x_{t}-x^{*}\>\rangle$. Applying Azuma’s inequality on the summation (using the diameter bound to obtain $\langle\>\hat{z}_{t},\,x_{t}-x^{*}\>\rangle^{2}\leq 1$) shows

As a consequence of Lemma 8.2, it is enough to prove that the error due to the noise terms are small in order to complete the proof of Theorem 3.2. By changing the order of summation, we can write $Z_{T}=\sum_{t=T/2}^{T}\langle\>\hat{z}_{t},\,w_{t}\>\rangle$ where

Just as in Section 7, the main technical difficulty is to show that $Z_{T}$ is small with high probability. Formally, we prove the following lemma, whose proof is outlined in Subsection 8.1.

For every $\delta\in(0,1)$, $Z_{T}\leq O\left({\log(T)\log(1/\delta)}/{\sqrt{T}}\right)$ with probability at least $1-\delta$.

Given Lemma 8.2 and Lemma 8.3, the proof of Theorem 3.2 is straightforward. The next sub-section provides a proof sketch of Lemma 8.3.

The goal of this section is to prove Lemma 8.3. Just as in Section 7, the main technical difficulty is to understand the noise term, denoted $Z_{T}$. Observe that $Z_{T}$ is a sum of a martingale difference sequence, and $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$ is the TCV of $Z_{T}$. The TCV of $Z_{T}$ will be shown to exhibit the “chicken and egg” relationship which we have already seen explicitly exhibited by the TCV of the noise terms in the strongly convex case. That is, we will see that the $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$ is bounded by a linear transformation of $Z_{T}$. We will again use our Generalized Freedman to disentangle the total conditional variance from the martingale.

The distance $\left\lVert x_{t}-x_{j}\right\rVert$ between SGD iterates is again a crucial quantity to understand in order to bound $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$ (see Subsection 7.1 to see why). Therefore, we develop a distance estimate analogous to Lemma 7.3

Suppose $f$ is 1-Lipschitz. Suppose we run Algorithm 1 for $T$ iterations with step sizes $\eta_{t}=1/\sqrt{t}$. Let $a<b$. Then,

We then use Lemma 8.4 to prove Lemma 8.5, our main upper bound on $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$. This follows from some delicate calculations similar to those in Appendix E.1, replacing the strongly-convex distance estimate (Lemma 7.3) with the Lipschitz distance estimate (Lemma 8.4), along with some other minor modifications. This upper bound reveals the surprisingly intricate relationship between $Z_{T}$ (the martingale) and $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}$ (its TCV).

There exists positive values $R_{1}=O\left(\frac{\log^{2}T}{T}\right)$, $R_{2}=O\left(\frac{\log T}{T^{1.5}}\right)$, and $C_{t}=O\left(\log T\right)$, such that

Just as in Lemma 7.4, the left-hand side is an upper bound on the total conditional variance of $Z_{T}$, whereas the right-hand side essentially contains a scaled version of $Z_{T}$ itself. This is another instance of the “chicken and egg phenomenon” alluded to in Section 4, and it is the main challenge of bounding $Z_{T}$. For convenience, we restate our main probabilistic tool which allows us to deal with the chicken and egg phenomenon.

Theorem 3.3 (Generalized Freedman). Let $\{d_{i},\mathcal{F}_{i}\}_{i=1}^{n}$ be a martingale difference sequence. Suppose $v_{i-1}$, $i\in[n]$ are positive and $\mathcal{F}_{i-1}$-measurable random variables such that $\operatorname{E}\left[\,\exp(\lambda d_{i})\,\mid\,\mathcal{F}_{i-1}\,\right]\leq\exp\left(\frac{\lambda^{2}}{2}v_{i-1}\right)$ for all $i\in[n],\,\lambda>0$. Let $S_{t}=\sum_{i=1}^{t}d_{i}$ and $V_{t}=\sum_{i=1}^{t}v_{i-1}$. Let $\alpha_{i}\geq 0$ and set $\alpha=\max_{i\in[n]}\alpha_{i}$. Then

In order to apply Theorem 3.3, we need to refine Lemma 8.5 to replace $R_{2}\sum_{t=T/2}^{T}\langle\>\hat{z}_{t},\,x_{t}-x^{*}\>\rangle$ with a sufficient high probability upper bound. This is similar to the refinement of Lemma 7.4 from Subsection 7.1. However, unlike the refinement in Subsection 7.1 (which required a high probability bound on $\sum_{t=T/2}^{T}A_{t}\left\lVert x_{t}-x^{*}\right\rVert^{2}$ without any diameter bound), the refinement here is quite easy. Using the diameter bound, the almost sure bound of $\left\lVert\hat{z}_{t}\right\rVert\leq 1$, and Azuma’s inequality, we can bound $\sum_{t=T/2}^{T}\langle\>\hat{z}_{t},\,x_{t}-x^{*}\>\rangle$ by $\sqrt{T\log(1/\delta)}$ with probability at least $1-\delta$. This yields the following lemma.

For every $\delta\in(0,1)$, there exists positive values $R=O\left(\frac{\log^{2}T\sqrt{\log(1/\delta)}}{T}\right)$, $C_{t}=O\left(\log T\right)$, such that $\sum_{t=T/2}^{T}\left\lVert w_{t}\right\rVert^{2}\leq R+\sum_{t=T/2}^{T-1}\langle\>\hat{z}_{t},\,\frac{C_{t}}{\sqrt{t}}w_{t}\>\rangle,$ with probability at least $1-\delta$.