Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

Introduction

Stochastic gradient descent (SGD) is one of the simplest and most popular first-order methods to solve convex learning problems. Given a convex loss function and a training set of $T$ examples, SGD can be used to obtain a sequence of $T$ predictors, whose average has a generalization error which converges (with $T$) to the optimal one in the class of predictors we consider. The common framework to analyze such first-order algorithms is via stochastic optimization, where our goal is to optimize an unknown convex function $F$, given only unbiased estimates of $F$’s subgradients (see Sec. 2 for a more precise definition).

An important special case is when $F$ is strongly convex (intuitively, can be lower bounded by a quadratic function). Such functions arise, for instance, in Support Vector Machines and other regularized learning algorithms. For such problems, there is a well-known $\mathcal{O}(\log(T)/T)$ convergence guarantee for SGD with averaging. This rate is obtained using the analysis of the algorithm in the harder setting of online learning Hazan et al. 2007, combined with an online-to-batch conversion (see Hazan & Kale 2011 for more details).

Surprisingly, a recent paper by Hazan and Kale Hazan & Kale 2011 showed that in fact, an $\mathcal{O}(\log(T)/T)$ is not the best that one can achieve for strongly convex stochastic problems. In particular, an optimal $\mathcal{O}(1/T)$ rate can be obtained using a different algorithm, which is somewhat similar to SGD but is more complex (although with comparable computational complexity) Roughly speaking, the algorithm divides the $T$ iterations into exponentially increasing epochs, and runs stochastic gradient descent with averaging on each one. The resulting point of each epoch is used as the starting point of the next epoch. The algorithm returns the resulting point of the last epoch.. A very similar algorithm was also presented recently by Juditsky and Nesterov Juditsky & Nesterov 2010.

These results left an important gap: Namely, whether the true convergence rate of SGD, possibly with some sort of averaging, might also be $\mathcal{O}(1/T)$, and the known $\mathcal{O}(\log(T)/T)$ result is just an artifact of the analysis. Indeed, the whole motivation of Hazan & Kale 2011 was that the standard online analysis is too loose to analyze the stochastic setting properly. Perhaps a similar looseness applies to the analysis of SGD as well? This question has immediate practical relevance: if the new algorithms enjoy a better rate than SGD, it might indicate they will work better in practice, and that practitioners should abandon SGD in favor of them.

In this paper, we study the convergence rate of SGD for stochastic strongly convex problems, with the following contributions:

First, we extend known results to show that if $F$ is not only strongly convex, but also smooth (with respect to the optimum), then SGD with and without averaging achieves the optimal $\mathcal{O}(1/T)$ convergence rate.

We then show that for non-smooth $F$, there are cases where the convergence rate of SGD with averaging is $\Omega(\log(T)/T)$. In other words, the $\mathcal{O}(\log(T)/T)$ bound for general strongly convex problems is real, and not just an artifact of the currently-known analysis.

However, we show that one can recover the optimal $\mathcal{O}(1/T)$ convergence rate by a simple modification of the averaging step: Instead of averaging of $T$ points, we only average the last $\alpha T$ points, where $\alpha\in(0,1)$ is arbitrary. Thus, to obtain an optimal rate, one does not need to use an algorithm significantly different than SGD, such as those discussed earlier.

We perform an empirical study on both artificial and real-world data, which supports our findings.

Following the paradigm of Hazan & Kale 2011, we analyze the algorithm directly in the stochastic setting, and avoid an online analysis with an online-to-batch conversion. Our rate upper bounds are shown to hold in expectation, but we also sketch how we can obtain high-probability bounds (up to a $\log(\log(T))$ factor). While the focus here is on getting the optimal rate in terms of $T$, we note that our upper bounds are also optimal in terms of other standard problem parameters, such as the strong convexity parameter and the variance of the stochastic gradients.

In terms of related work, we note that the performance of SGD in a stochastic setting has been extensively researched in stochastic approximation theory (see for instance Kushner & Yin 2003). However, these results are usually obtained under smoothness assumptions, and are often asymptotic, so we do not get an explicit bound in terms of $T$ which applies to our setting. We also note that a finite-sample analysis of SGD in the stochastic setting was recently presented in Bach & Moulines 2011. However, the focus there was different than ours, and also obtained bounds which hold only in expectation rather than in high probability. More importantly, the analysis was carried out under stronger smoothness assumptions than our analysis, and to the best of our understanding, does not apply to general, possibly non-smooth, strongly convex stochastic optimization problems. For example, smoothness assumptions may not cover the application of SGD to support vector machines (as in Shalev-Shwartz et al. 2011), since it uses a non-smooth loss function, and thus the underlying function $F$ we are trying to stochastically optimize may not be smooth.

Preliminaries

We use bold-face letters to denote vectors. Given some vector $\mathbf{w}$, we use $w_{i}$ to denote its $i$-th coordinate. Similarly, given some indexed vector $\mathbf{w}_{t}$, we let $w_{t,i}$ denote its $i$-th coordinate. We let $\mathbf{1}_{A}$ denote the indicator function for some event $A$.

We will focus on an important special case of the problem, characterized by $F$ being a strongly convex function. Formally, we say that a function $F$ is $\lambda$-strongly convex, if for all $\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{W}$ and any subgradient $\mathbf{g}$ of $F$ at $\mathbf{w}$,

Another possible property of $F$ we will consider is smoothness, at least with respect to the optimum $\mathbf{w}^{*}$. Formally, a function $F$ is $\mu$-smooth with respect to $\mathbf{w}^{*}$ if for all $\mathbf{w}\in\mathcal{W}$,

Such functions arise, for instance, in logistic and least-squares regression, and in general for learning linear predictors where the loss function has a Lipschitz-continuous gradient.

The algorithm we focus on is stochastic gradient descent (SGD). The SGD algorithm is parameterized by step sizes $\eta_{1},\ldots,\eta_{T}$, and is defined as follows (below, we assume for simplicity that the algorithm is initialized at $\mathbf{0}\in\mathcal{W}$, following common practice).

Let $\mathbf{w}_{t+1}=\Pi_{\mathcal{W}}(\mathbf{w}_{t}-\eta_{t}\hat{\mathbf{g}}_{t})$, where $\Pi_{\mathcal{W}}$ is the projection operator on $\mathcal{W}$.

This algorithm returns a sequence of points $\mathbf{w}_{1},\ldots,\mathbf{w}_{T}$. To obtain a single point, one can use several strategies. Perhaps the simplest one is to return the last point, $\mathbf{w}_{T+1}$. Another procedure, for which the standard online analysis of SGD applies Hazan et al. 2007, is to return the average point

In terms of the step size, we note that the appropriate regime to consider is $\eta_{t}=\Theta(1/t)$ (see Appendix A for a fuller discussion of this). In particular, we will assume for the sake of our upper bounds that $\eta_{t}=1/\lambda t$. This assumption simplifies the analysis substantially, while not losing much in terms of generality. To see why, suppose the step sizes are actually $c/\lambda t$ for some If the step size is too small and $c$ is much smaller than $1$, the SGD analysis is known to fail (Nemirovski et al. 2009). $c\geq 1$, and let $\lambda^{\prime}=\lambda/c$. Then this step size is equivalent to $1/(\lambda^{\prime}t)$. Since any $\lambda$-strongly convex function is also $\lambda^{\prime}$-strongly convex (as $\lambda\geq\lambda^{\prime}$), then we can just analyze the algorithm’s behavior as if we run it on a $\lambda^{\prime}$-strongly convex function, using the default step size $1/\lambda^{\prime}t$. If so desired, one can then substitute $\lambda/c$ instead of $\lambda^{\prime}$ in the final bound, to see the upper bound in terms of $\lambda$ and $c$.

Full proofs of our results are provided in Appendix B.

Smooth Functions

We begin by considering the case where the expected function $F(\cdot)$ is both strongly convex and smooth with respect to $\mathbf{w}^{*}$. Our starting point is to show a $\mathcal{O}(1/T)$ for the last point obtained by SGD. This result is well known in the literature (see for instance Nemirovski et al. 2009) and we include a proof for completeness. Later on, we will show how to extend it to a high-probability bound.

The theorem is an immediate corollary of the following key lemma, and the definition of $\mu$-smoothness with respect to $\mathbf{w}^{*}$.

We now turn to discuss the behavior of the average point $\bar{\mathbf{w}}_{T}=(\mathbf{w}_{1}+\ldots+\mathbf{w}_{T})/T$, and show that for smooth $F$, it also enjoys an optimal $\mathcal{O}(1/T)$ convergence rate.

A rough proof intuition is the following: Lemma 1 implies that the Euclidean distance of $\mathbf{w}_{t}$ from $\mathbf{w}^{*}$ is on the order of $1/\sqrt{t}$, so the squared distance of $\bar{\mathbf{w}}_{T}$ from $\mathbf{w}^{*}$ is on the order of $((1/T)\sum_{t=1}^{T}1/\sqrt{t})^{2}\approx 1/T$, and the rest follows from smoothness.

Non-Smooth Functions

We now turn to the discuss the more general case where the function $F$ may not be smooth (i.e. there is no constant $\mu$ which satisfies Eq. (2) uniformly for all $\mathbf{w}\in\mathcal{W}$). In the context of learning, this may happen when we try to learn a predictor with respect to a non-smooth loss function, such as the hinge loss.

As discussed earlier, SGD with averaging is known to have a rate of at most $\mathcal{O}(\log(T)/T)$. In the previous section, we saw that for smooth $F$, the rate is actually $\mathcal{O}(1/T)$. Moreover, Hazan & Kale 2011 showed that for using a different algorithm than SGD, one can obtain a rate of $\mathcal{O}(1/T)$ even in the non-smooth case. This might lead us to believe that an $\mathcal{O}(1/T)$ rate for SGD is possible in the non-smooth case, and that the $\mathcal{O}(\log(T)/T)$ analysis is simply not tight.

However, this intuition turns out to be wrong. Below, we show that there are strongly convex stochastic optimization problems in Euclidean space, in which the convergence rate of SGD with averaging is lower bounded by $\Omega(\log(T)/T)$. Thus, the logarithm in the bound is not merely a shortcoming in the standard online analysis of SGD, but is really a property of the algorithm.

We begin with the following relatively simple example, which shows the essence of the idea. Let $F$ be the $1$-strongly convex function

The following theorem implies in this case, the convergence rate of SGD with averaging has a $\Omega(\log(T)/T)$ lower bound. The intuition for this is that the global optimum lies at a corner of $\mathcal{W}$, so SGD “approaches” it only from one direction. As a result, averaging the points returned by SGD actually hurts us.

Consider the strongly convex stochastic optimization problem presented above. If SGD is initialized at any point in $\mathcal{W}$, and ran with $\eta_{t}=c/t$, then for any $T\geq T_{0}+1$, where $T_{0}=\max\{2,c/2\}$, we have

When $c$ is considered a constant, this lower bound is $\Omega(\log(T)/T)$.

While the lower bound scales with $c$, we remind the reader that one must pick $\eta_{t}=c/t$ with constant $c$ for an optimal convergence rate in general (see discussion in Sec. 2).

This example is relatively straightforward but not fully satisfying, since it crucially relies on the fact that $\mathbf{w}^{*}$ is on the border of $\mathcal{W}$. In strongly convex problems, $\mathbf{w}^{*}$ usually lies in the interior of $\mathcal{W}$, so perhaps the $\Omega(\log(T)/T)$ lower bound does not hold in such cases. Our main result, presented below, shows that this is not the case, and that even if $\mathbf{w}^{*}$ is well inside the interior of $\mathcal{W}$, an $\Omega(\log(T)/T)$ rate for SGD with averaging can be unavoidable. The intuition is that we construct a non-smooth $F$, which forces $\mathbf{w}_{t}$ to approach the optimum from just one direction, creating the same effect as in the previous example.

In particular, let $F$ be the $1$-strongly convex function

over the domain $\mathcal{W}=^{d}$, which has a global minimum at $\mathbf{0}$. Suppose the stochastic gradient oracle, given a point $\mathbf{w}_{t}$, returns the gradient estimate

Consider the strongly convex stochastic optimization problem presented above. If SGD is initialized at any point $\mathbf{w}_{1}$ with $w_{1,1}\geq 0$, and ran with $\eta_{t}=c/t$, then for any $T\geq T_{0}+2$, where $T_{0}=\max\{2,6c+1\}$, we have

When $c$ is considered a constant, this lower bound is $\Omega(\log(T)/T)$.

We note that the requirement of $w_{1,1}\geq 0$ is just for convenience, and the analysis also carries through, with some second-order factors, if we let $w_{1,1}<0$.

Recovering an 𝒪⁡(1/T)\mathcal{O}(1/T) Rate for SGD with α\alpha-Suffix Averaging

In the previous section, we showed that SGD with averaging may have a rate of $\Omega(\log(T)/T)$ for non-smooth $F$. To get the optimal $\mathcal{O}(1/T)$ rate for any $F$, we might turn to the algorithms of Hazan & Kale 2011 and Juditsky & Nesterov 2010. However, these algorithms constitute a significant departure from standard SGD. In this section, we show that it is actually possible to get an $\mathcal{O}(1/T)$ rate using a much simpler modification of the algorithm: given the sequence of points $\mathbf{w}_{1},\ldots,\mathbf{w}_{T}$ provided by SGD, instead of returning the average $\bar{\mathbf{w}}_{T}=(\mathbf{w}_{1}+\ldots+\mathbf{w}_{T})/T$, we average and return just a suffix, namely

for some constant $\alpha\in(0,1)$ (assuming $\alpha T$ and $(1-\alpha)T$ are integers). We call this procedure $\alpha$-suffix averaging.

Note that for any constant $\alpha\in(0,1)$, the bound above is $\mathcal{O}(G^{2}/\lambda T)$. This matches the optimal guarantees in Hazan & Kale 2011 up to constant factors. However, this is shown for standard SGD, as opposed to the more specialized algorithm of Hazan & Kale 2011. Also, it is interesting to note that this bound is comparable to the bound of Thm. 1 for the last iterate, when $F$ is also smooth, as long as $\mu/\lambda=\mathcal{O}(1)$. However, Thm. 1 degrades as the function becomes less smooth. In contrast, Thm. 5 implies that with an averaging scheme, we get an optimal rate even if the function is not smooth. Finally, we note that it might be tempting to use Thm. 5 as a guide to choose the averaging window, by optimizing the bound for $\alpha$ (which turns out to be $\alpha\approx 0.65$). However, we note that the optimal value of $\alpha$ is dependent on the constants in the bound, which may not be the tightest or most “correct” ones.

The proof combines the analysis of online gradient descent Hazan et al. 2007 and Lemma 1. In particular, starting as in the proof of Lemma 1, and extracting the inner products, we get

One potential disadvantage of suffix averaging is that if we cannot store all the iterates $\mathbf{w}_{t}$ in memory, then we need to know from which iterate $\alpha T$ to start computing the suffix average (in contrast, standard averaging can be computed “on-the-fly” without knowing the stopping time $T$ in advance). However, even if $T$ is not known, this can be addressed in several ways. For example, since our results are robust to the value of $\alpha$, it is really enough to guess when we passed some “constant” portion of all iterates. Alternatively, one can divide the rounds into exponentially increasing epochs, and maintain the average just of the current epoch. Such an average would always correspond to a constant-portion suffix of all iterates.

High-Probability Bounds

Let $\delta\in(0,1/e)$ and assume $T\geq 4$. Suppose $F$ is $\lambda$-strongly convex over a convex set $\mathcal{W}$, and that $\|\hat{\mathbf{g}}_{t}\|^{2}\leq G^{2}$ with probability $1$. Then if we pick $\eta_{t}=1/\lambda t$, it holds with probability at least $1-\delta$ that for any $t\leq T$,

To obtain high probability versions of Thm. 1, Thm. 2, and Thm. 5, one needs to use this lemma in lieu of Lemma 1 in their proofs. This leads overall to rates of the form $\mathcal{O}(\log(\log(T)/\delta)/T)$ which hold with probability $1-\delta$.

Experiments

We now turn to empirically study how the algorithms behave, and compare it to our theoretical findings.

We studied the following four algorithms:

Sgd-A: Performing SGD and then returning the average point over all $T$ rounds.

Sgd-$\alpha$: Performing SGD with $\alpha$-suffix averaging. We chose $\alpha=1/2$ - namely, we return the average point over the last $T/2$ rounds.

Sgd-L: Performing SGD and returning the point obtained in the last round.

Epoch-Gd: The optimal algorithm of Hazan & Kale 2011 for strongly convex stochastic optimization.

First, as a simple sanity check, we measured the performance of these algorithms on a simple, strongly convex stochastic optimization problem, which is also smooth. We define $\mathcal{W}=^{5}$, and $F(\mathbf{w})=\|\mathbf{w}\|^{2}$. The stochastic gradient oracle, given a point $\mathbf{w}$, returns the stochastic gradient $\mathbf{w}+\mathbf{z}$ where $\mathbf{z}$ is uniformly distributed in $^{5}$. Clearly, this is an unbiased estimate of the gradient of $F$ at $\mathbf{w}$. The initial point $\mathbf{w}_{1}$ of all 4 algorithms was chosen uniformly at random from $\mathcal{W}$. The results are presented in Fig. 1, and it is clear that all 4 algorithms indeed achieve a $\Theta(1/T)$ rate, matching our theoretical analysis (Thm. 1, Thm. 2 and Thm. 5). The results also seem to indicate that Sgd-A has a somewhat worse performance in terms of leading constants.

Second, as another simple experiment, we measured the performance of the algorithms on the non-smooth, strongly convex problem described in the proof of Thm. 4. In particular, we simulated this problem with $d=5$, and picked $\mathbf{w}_{1}$ uniformly at random from $\mathcal{W}$. The results are presented in Fig. 2. As our theory indicates, Sgd-A seems to have an $\Theta(\log(T)/T)$ convergence rate, whereas the other 3 algorithms all seem to have the optimal $\Theta(1/T)$ convergence rate. Among these algorithms, the SGD variants Sgd-L and Sgd-$\alpha$ seem to perform somewhat better than Epoch-Gd. Also, while the average performance of Sgd-L and Sgd-$\alpha$ are similar, Sgd-$\alpha$ has less variance. This is reasonable, considering the fact that Sgd-$\alpha$ returns an average of many points, whereas Sgd-L return only the very last point.

Finally, we performed a set of experiments on real-world data. We used the same 3 binary classification datasets (ccat,cov1 and astro-ph) used by Shalev-Shwartz et al. 2011 and Joachims 2006, to test the performance of optimization algorithms for Support Vector Machines using linear kernels. Each of these datasets is composed of a training set and a test set. Given a training set of instance-label pairs, $\{\mathbf{x}_{i},y_{i}\}_{i=1}^{m}$, we defined $F$ to be the standard (non-smooth) objective function of Support Vector Machines, namely

Following Shalev-Shwartz et al. 2011 and Joachims 2006, we took $\lambda=10^{-4}$ for ccat, $\lambda=10^{-6}$ for cov1, and $\lambda=5\times 10^{-5}$ for astro-ph. The stochastic gradient given $\mathbf{w}_{t}$ was computed by taking a single randomly drawn training example $(\mathbf{x}_{i},y_{i})$, and computing the gradient with respect to that example, namely

The results of the experiments are presented in Fig. 3,Fig. 4 and Fig. 5. In all experiments, Sgd-A performed the worst. The other 3 algorithms performed rather similarly, with Sgd-$\alpha$ being slightly better on the Cov1 dataset, and Sgd-L being slightly better on the other 2 datasets.

In summary, our experiments indicate the following:

Sgd-A, which averages over all $T$ predictors, is worse than the other approaches. This accords with our theory, as well as the results reported in Shalev-Shwartz et al. 2011.

The Epoch-Gd algorithm does have better performance than Sgd-A, but a similar or better performance was obtained using the simpler approaches of $\alpha$-suffix averaging (Sgd-$\alpha$) or even just returning the last predictor (Sgd-L). The good performance of Sgd-$\alpha$ is supported by our theoretical results, and so does the performance of Sgd-L in the strongly convex and smooth case.

Sgd-L also performed rather well (with what seems like a $\Theta(1/T)$ rate) on the non-smooth problem reported in Fig. 2, although with a larger variance than Sgd-$\alpha$. Our current theory does not cover the convergence of the last predictor in non-smooth problems - see the discussion below.

Discussion

In this paper, we analyzed the behavior of SGD for strongly convex stochastic optimization problems. We demonstrated that this simple and well-known algorithm performs optimally whenever the underlying function is smooth, but the standard averaging step can make it suboptimal for non-smooth problems. However, a simple modification of the averaging step suffices to recover the optimal rate, and a more sophisticated algorithm is not necessary. Our experiments seem to support this conclusion.

There are several open issues remaining. In particular, the $\mathcal{O}(1/T)$ rate in the non-smooth case still requires some sort of averaging. However, in our experiments and other studies (e.g. Shalev-Shwartz et al. 2011), returning the last iterate $\mathbf{w}_{T}$ also seems to perform quite well. Our current theory does not cover this - at best, one can use Lemma 1 and Jensen’s inequality to argue that the last iterate has a $\mathcal{O}(1/\sqrt{T})$ rate, but the behavior in practice is clearly much better. Does SGD, without averaging, obtain an $\mathcal{O}(1/T)$ rate for general strongly convex problems? Also, a fuller empirical study is warranted of whether and which averaging scheme is best in practice.

Acknowledgements: We thank Elad Hazan and Satyen Kale for helpful comments, and to Simon Lacoste-Julien for pointing out a bug in Lemma 1 in a previous version of this paper.

References

Appendix A Justifying ηt=Θ⁡(1/t)\eta_{t}=\Theta(1/t) Step-Sizes

In this appendix, we justify our focus on the step-size regime $\eta_{t}=\Theta(1/t)$, by showing that for other step sizes, one cannot hope for an optimal convergence rate in general.

Let us begin by considering the scalar, strongly convex function $F(w)=\frac{1}{2}w^{2}$, in the deterministic case where $\hat{g}_{t}=g_{t}=\nabla F(w_{t})=w_{t}$ with probability $1$, and show that $\eta_{t}$ cannot be smaller than $\Omega(1/t)$. Intuitively, such small step sizes do not allow the iterates $w_{t}$ to move towards the optimum sufficiently fast. More formally, starting from (say) $w_{1}=1$ and using the recursive equality $w_{t+1}=w_{t}-\eta_{t}\hat{g}_{t}$, we immediately get $w_{T}=\prod_{t=1}^{T-1}(1-\eta_{t})$. Thus, if we want to obtain a $\mathcal{O}(1/T)$ convergence rate using the iterates returned by the algorithm, we must at least require that

For large enough $t$ and small enough $\eta_{t}$, $\log(1-\eta_{t})\approx-\eta_{t}$, and we get that $\sum_{t=1}^{T}\eta_{t}$ must scale at least logarithmically with $T$. This requires $\eta_{t}\geq\Omega(1/t)$.

Appendix B Proofs

In this subsection we collect some technical Results we will need for the other proofs.

Intuitively, the lemma holds because the strong convexity of $F$ implies that the expected value of $\|\hat{\mathbf{g}}_{1}\|^{2}$ must strictly increase as we get farther from $\mathbf{w}^{*}$. More precisely, strong convexity implies that for any $\mathbf{w}_{1}$,

Combining this and Eq. (5), we get that for all $t$,

The following version of Freedman’s inequality appears in De La Peña 1999 (Theorem 1.2A):

Let $d_{1},\dots,d_{T}$ be a martingale difference sequence with a uniform upper bound $b$ on the steps $d_{i}$. Let $V$ denote the sum of conditional variances,

The proof of the following lemma is taken almost verbatim from Bartlett et al. 2008, with the only modification being the use of Theorem 6 to avoid an unnecessary union bound.

Let $d_{1},\ldots,d_{T}$ be a martingale difference sequence with a uniform bound $|d_{i}|\leq b$ for all $i$. Let $V_{s}=\sum_{t=1}^{s}\text{Var}_{t-1}(d_{t})$ be the sum of conditional variances of $d_{t}$’s. Further, let $\sigma_{s}=\sqrt{V_{s}}$. Then we have, for any $\delta<1/e$ and $T\geq 4$,

Note that a crude upper bound on $\text{Var}_{t}d_{t}$ is $b^{2}$. Thus, $\sigma_{s}\leq b\sqrt{T}$. We choose a discretization $0=\alpha_{-1}<\alpha_{0}<\ldots<\alpha_{l}$ such that $\alpha_{i+1}=2\alpha_{i}$ for $i\geq 0$ and $\alpha_{l}\geq b\sqrt{T}$. We will specify the choice of $\alpha_{0}$ shortly. We then have,

where the last inequality follows from Theorem 6. If we now choose $\alpha_{0}=b\sqrt{\log(1/\delta)}$, then $\alpha_{j}\geq b\sqrt{\log(1/\delta)}$ for all $j$. Hence every term in the above summation is bounded by $\exp\left(\frac{-2\log(1/\delta)}{1+2/3}\right)<\delta$. Choosing $l=\log(\sqrt{T})$ ensures that $\alpha_{l}\geq b\sqrt{T}$. Thus we have

B.2 Proof of Lemma 1

By the strong convexity of $F$ and the fact that $\mathbf{w}^{*}$ minimizes $F$ in $\mathcal{W}$, we have

Also, by convexity of $\mathcal{W}$, for any point $\mathbf{v}$ and any $\mathbf{w}\in\mathcal{W}$ we have $\|\Pi_{\mathcal{W}}(\mathbf{v})-\mathbf{w}\|\leq\|\mathbf{v}-\mathbf{w}\|$. Using these inequalities, we have the following:

Plugging in $\eta_{t}=1/\lambda t$, we get

B.3 Proof of Thm. 2

For any $t$, define $\bar{\mathbf{w}}_{t}=(\mathbf{w}_{1}+\ldots+\mathbf{w}_{t})/t$. Then we have

By an induction argument (using Lemma 2 for the base case), it is easy to verify that

By the assumed smoothness of $F$ with respect to $\mathbf{w}^{*}$, we have $F(\bar{\mathbf{w}}_{T})-F(\mathbf{w}^{*})\leq\frac{\mu}{2}\|\bar{\mathbf{w}}_{T}-\mathbf{w}^{*}\|^{2}$. Combining it with the inequality above, the result follows.

B.4 Proof of Thm. 3

The SGD iterate can be written separately for the first coordinate as

Fix some $t\geq T_{0}$, and suppose first that $Z_{t}\leq-1/2$. Conditioned on this event, we have

since $t\geq T_{0}$ implies $\eta_{t}=c/t\leq 2$. On the other hand, if $Z_{t}>-1/2$, we are still guaranteed that $w_{t+1,1}\geq 0$ by the domain constraints. Using these results, we get

Substituting $\eta_{t}=c/t$ gives the required result.

B.5 Proof of Thm. 4

The SGD iterate for the first coordinate is

The intuition of the proof is that whenever $w_{t,1}$ becomes negative, then the large gradient of $F$ causes $w_{t+1,1}$ to always be significantly larger than $0$. This means that in some sense, $w_{t,1}$ is “constrained” to be larger than $0$, mimicking the actual constraint in the example of Thm. 3 and forcing the same kind of behavior, with a resulting $\Omega(\log(T)/T)$ rate.

To make this intuition rigorous, we begin with the following lemma, which shows that $w_{t,1}$ can never be significantly smaller than $0$, or “stay” below $0$ for more than one iteration.

For any $t\geq T_{0}=\max\{2,6c+1\}$, it holds that

Suppose first that $w_{t-1,1}\geq 0$. Then by Eq. (9) and the fact that $Z_{t}\geq-1$, we get $w_{t,1}\geq-c/(t-1)$. Moreover, in that case, if $w_{t,1}<0$, then by Eq. (9) and the previous observation,

Since $t\geq c$, we have $1-c/t\in(0,1)$, which implies that the above is lower bounded by

Moreover, since $t\geq 6c$, we have $-c/(t-1)+7c/t\in$, so the projection operator is unnecessary, and we get overall that

This result was shown to hold assuming that $w_{t-1,1}\geq 0$. If $w_{t-1,1}<0$, then repeating the argument above for $t-1$ instead of $t$, we must have $w_{t,1}\geq 5c/(t-1)\geq-c/(t-1)$, so the statement in the lemma holds also when $w_{t-1,1}<0$. ∎

We turn to the proof of Thm. 4 itself. By Lemma 4, if $t\geq T_{0}$, then $w_{t,1}<0$ implies $w_{t+1,1}\geq 0$, and moreover, $w_{t,1}+w_{t+1,1}\geq-c/(t-1)+5c/t\geq 3c/t$. Therefore, we have the following, where the sums below are only over $t$’s which are between $T_{0}$ and $T$:

Now, we claim that the probabilities above can be lower bounded by a constant. To see this, consider each such probability for $w_{t,1}$, conditioned on the event $w_{t-1,1}\geq 0$. Using the fact that $c/t<1$, we have

This probability is at most $1/4$, since it asks for $Z_{t}$ being constrained in an interval of size $1$, whereas $Z_{t}$ is uniformly distributed over $$, which is an interval of length$4$. As a result, we get

From this, we can lower bound Eq. (10) as follows:

Now, by Lemma 4, for any realization of $w_{T_{0},1},\ldots,w_{T,1}$, the indicators $\mathbf{1}_{w_{t,1}\geq 0}$ cannot equal $0$ consecutively. Therefore, $\mathbf{1}_{w_{t-1,1}\geq 0}+\mathbf{1}_{w_{t,1}\geq 0}$ must always be at least $1$. Plugging it in the equation above, we get the lower bound $(3c/16)\sum_{t=T_{0}+2}^{T}\frac{1}{t}$. Summing up, we have shown that

By the boundedness assumption on $\mathcal{W}$, we have To analyze the case where $\mathcal{W}$ is unbounded, one can replace this by a coarse bound on how much $w_{t,1}$ can change in the first $T_{0}$ iterations, since the step sizes are bounded and $T_{0}$ is essentially a constant anyway. $w_{t,1}\geq-1$, so

B.6 Proof of Thm. 5

Extracting the inner product and summing over $t=(1-\alpha)T+1,\ldots,T$, we get

In particular, since we take $\eta_{t}=1/\lambda t$, we get

It can be shown that $\sum_{t=(1-\alpha)T+1}^{T}\frac{1}{t}\leq\log(1/(1-\alpha))$. Plugging it in and slightly simplifying, we get the desired bound. ∎

B.7 Proof of Proposition 1

To prove this proposition, we will first prove the two auxiliary results, which rewrite $\|\mathbf{w}_{t+1}-\mathbf{w}^{*}\|^{2}$ in a more explicit form and provide a loose uniform upper bound. We will use the notation $\hat{\mathbf{z}}_{t}$ to denote $\mathbf{g}_{t}-\hat{\mathbf{g}}_{t}$.

For all $t$, it holds with probability $1$ that

The proof is analogous to that of Lemma 2, using the stronger condition that $\|\mathbf{g}_{t}\|\leq G$ (which follows from the assumption $\|\hat{\mathbf{g}}_{t}\|\leq G$ with probability $1$). Using strong convexity, we have

The lemma trivially holds for $\|\mathbf{w}_{t}-\mathbf{w}^{*}\|=0$. Otherwise, divide both sides by $\lambda\|\mathbf{w}_{t}-\mathbf{w}^{*}\|/2$, and the result follows. ∎

Under the conditions of Proposition 1, it holds for any $t\geq 2$ that

By the strong convexity of $F$ and the fact that $\mathbf{w}^{*}$ minimizes $F$ in $\mathcal{W}$, we have

Also, by convexity of $\mathcal{W}$, for any point $\mathbf{v}$ and any $\mathbf{w}\in\mathcal{W}$ we have $\|\Pi_{\mathcal{W}}(\mathbf{v})-\mathbf{w}\|\leq\|\mathbf{v}-\mathbf{w}\|$. Using these inequalities, we have the following:

Unwinding this recursive inequality till $t=2$, we get that for any $t\geq 2$,

Plugging this back, we get the desired bound. ∎

Considering the sum $\sum_{i=2}^{t}(i-1)Z_{i}$, we have that the sum of conditional variances satisfies

where the last upper bound is by Lemma 5.

We now apply Lemma 3 to the sum of martingale differences $\sum_{i=2}^{t}(i-1)Z_{i}$, and get that as long as $T\geq 4$ and $\delta\in(0,1/e)$, then with probability at least $1-\delta$, for all $t\leq T$,

Plugging this back into Eq. (12), we get that with probability at least $1-\delta$, for all $t\geq 2$,

What is left to do now is an induction argument, to show that $\|\mathbf{w}_{t}-\mathbf{w}^{*}\|^{2}\leq a/t$ for a suitably chosen value of $a$. By Lemma 5, this certainly holds for $t=1,2$ if $a\geq 8G^{2}/\lambda^{2}$. To show the induction step, let us rewrite the displayed inequality above as

where $b=16G\sqrt{\log(\log(T)/\delta)}/\lambda$ and $c=G^{2}(16\log(\log(T)/\delta)+1)/\lambda^{2}$. By the induction hypothesis, $\|\mathbf{w}_{i}-\mathbf{w}^{*}\|^{2}\leq a/i$ for all $i=2,\ldots,t$. Therefore, to show that $\|\mathbf{w}_{t+1}-\mathbf{w}^{*}\|^{2}\leq a/(t+1)$, it suffices to find a sufficiently large value of $a$ so that

Multiplying both sides by $t+1$, switching sides, and using the fact that $(t+1)/\sqrt{2(t-1)t}$ as well as $(t+1)/t$ is at most $3/2$ for any $t\geq 2$, it follows that $a$ should satisfy

Solving the quadratic inequality, we get that $a$ should satisfy

Taking the square of both sides and using the fact that $(x+y)^{2}\leq 2(x^{2}+y^{2})$, it is again sufficient that

Substituting in the values of $b,c$, we get

the induction hypothesis holds. Also, recall that for the base case to hold, we also need to assume $a\geq 8G^{2}/\lambda^{2}$, but this automatically holds for the value of $a$ above (since we assume $\delta<1/e$). This gives us the required result.