Unified Optimal Analysis of the (Stochastic) Gradient Method

Introduction

We consider the unconstrained optimization problem

where here $\nabla f(\mathbf{x}_{t})$ denotes the gradient of $f$ at $\mathbf{x}_{t}$.

There exists two constants $L,\sigma^{2}\geq 0$, s.t.

Let $\{\mathbf{x}_{t}\}_{t\geq 0}$ denote the iterates of (1). We show that for appropriate stepsizes $\gamma_{t}$ and an appropriately defined average iterate after $T$ iterations, $\bar{\mathbf{x}}_{T}:=\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}\mathbf{x}_{t}$ for weights $w_{t}\geq 0$ and $W_{T}:=\sum_{t=0}^{T}w_{t}$, it holds for $R=\left\lVert\mathbf{x}_{0}-\mathbf{x}^{\star}\right\rVert$:

and that only relies on constant stepsizes in (1).

This analysis unifies the analyses of gradient descent and SGD for smooth functions. In the deterministic case and in the iterpolation setting (where $\sigma^{2}=0$), we recover the exponential convergence rates of these algorithms (up to a factor 4 in the exponent) when $\mu>0$. Furthermore, the result for convergence in function values is tight up to absolute (non-problem specific) constants Nesterov (2004). Similarly, in the stochastic setting we recover the best known rates not only for the function values but also for the squared distance of the last iterate to the optimum Nemirovski et al. (2009); Shamir and Zhang (2013).

2 Related Work

Whilst the first analyses of stochastic gradient descent (SGD) Robbins and Monro (1951) focused on asymptotic results Chung (1954), the focus shifted to non-asymptotic results in recent years.

The $(L,\sigma^{2})$-smoothness assumption appeared in this form recently in e.g. Grimmer (2019), though very similar conditions have been studied in the literature Bertsekas and Tsitsiklis (1996); Schmidt and Roux (2013); Needell et al. (2016); Bottou et al. (2018); Gower et al. (2019). We will discuss a few of these in Section 2 below. In contrast to the bounded gradient assumption, these assumption allow to chose $\sigma^{2}=0$ in non-trivial situations and thus allow to recover faster rates in general. However, adapting the proof technique from Lacoste-Julien et al. (2012) to the relaxed assumptions considered here (cf. Lemma 7 below, or Stich et al. (2018); Grimmer (2019)) gives f(\bar{\mathbf{x}}_{T})-f^{\star}=\mathcal{O}\bigl{(}\frac{L^{2}R^{2}}{\mu T^{2}}+\frac{\sigma^{2}}{\mu T}\bigr{)}, where the dependence on the initial distance $R$ is not optimal, i.e. not exponentially decreasing as in Bach and Moulines (2011). Gower et al. (2019) generalize the results of Needell et al. (2016) for the convergence of the distance $\left\lVert\mathbf{x}_{T}-\mathbf{x}^{\star}\right\rVert^{2}$ to the setting considered here and obtain the same rate as stated earlier in this subsection.

To keep our focus, we do not discuss obvious generalizations of our bounds to other settings here. For instance convergence under average smoothness or importance sampling Bach and Moulines (2011); Needell et al. (2016) or expected smoothness conditions Gower et al. (2018).

Motivating Examples

In this section we give a few examples that motivate Assumption 2.

In the non-stochastic setting, we have $\mathbf{g}_{t}=\nabla f(\mathbf{x}_{t})$, $\forall t\geq 0$. If $f$ is $L$-smooth, then $f$ is also $(L,0)$-smooth, as seen by the choice $\mathbf{y}=\mathbf{x}^{\star}$ in the following inequality that holds for convex $L$-smooth functions (Nesterov, 2004, Theorem 2.1.5):

Example 2 (Stochastic Gradient Descent).

Hence, we recover the \mathcal{O}\bigl{(}\frac{\sigma^{2}}{\mu T}\bigr{)} convergence rate of SGD for the function values and the \mathcal{O}\bigl{(}\frac{\sigma^{2}}{\mu^{2}T}\bigr{)} rate for the last iterate—which are the best known rates Rakhlin et al. (2012); Shamir and Zhang (2013). We like to point out that we here do not need to rely on the frequently used bounded-gradient assumption, as e.g. in Lacoste-Julien et al. (2012); Rakhlin et al. (2012); Shamir and Zhang (2013).

Example 3 (Empirical Risk Minimization).

When the loss at the optimum vanishes, i.e. $\nabla f_{i}(\mathbf{x}^{\star})=0$, $\forall i\in[m]$—the so called interpolation setting—we have $\sigma^{2}=0$ and we recover linear convergence of SGD, as e.g. in Schmidt and Roux (2013); Needell et al. (2016); Ma et al. (2018).

The above observation also holds in more general settings, such as e.g. under expected smoothness or weak growth conditions (cf. Gower et al. (2018, 2019)).

Convergence Analysis Part I—Deriving a Recursion

Following standard techniques, we prove the following lemma:

where we also used $\mu$-convexity in the last inequality. By re-arranging and taking expectation on both sides, we get:

and the claim follows by observing $(1-L\gamma_{t})\geq\frac{1}{2}$ for $\gamma_{t}\leq\frac{1}{2L}$. ∎

This intermediate results shows that SGD with constant stepsizes reduces the initial error term $\left\lVert\mathbf{x}_{0}-\mathbf{x}^{\star}\right\rVert^{2}$ linearly, but only converges towards a $\frac{\gamma\sigma^{2}}{\mu}$-neighborhood of $\mathbf{x}^{\star}$ (cf. discussions in e.g. Bach and Moulines (2011); Bottou et al. (2018)). To obtain a convergence guarantee that holds for arbitrary accuracy, we need to choose the stepsize $\gamma$ carefully:

If $\frac{1}{2L}\geq\frac{\ln(\max\{2,\mu^{2}\left\lVert\mathbf{x}_{0}-\mathbf{x}^{\star}\right\rVert^{2}T/\sigma^{2}\})}{\mu T}$ then we choose $\gamma=\frac{\ln(\max\{2,\mu^{2}\left\lVert\mathbf{x}_{0}-\mathbf{x}^{\star}\right\rVert^{2}T/\sigma^{2}\})}{\mu T}$.

If otherwise $\frac{1}{2L}<\frac{\ln(\max\{2,\mu^{2}\left\lVert\mathbf{x}_{0}-\mathbf{x}^{\star}\right\rVert^{2}T/\sigma^{2}\})}{\mu T}$ then we pick $\gamma=\frac{1}{2L}$.

With these choices of $\gamma$, we can showWe refer the readers to the proof of Lemma 2 below for detailed computations in a very similar setting.

Convergence Analysis Part II—Solving the Recursion

In this section, we consider two non-negative sequences $\{r_{t}\}_{t\geq 0}$, $\{s_{t}\}_{t\geq 0}$, that satisfy the relation

for all $t\geq 0$ and for parameters $b>0$, $a,c\geq 0$ and non-negative stepsizes $\{\gamma_{t}\}_{t\geq 0}$ with $\gamma_{t}\leq\frac{1}{d}$, $\forall t\geq 0$, for a parameter $d\geq a$, $d>0$.

First, we derive a suboptimal (up to polylogarithmic factors) solution of (8).

Let $\{r_{t}\}_{t\geq 0}$, $\{s_{t}\}_{t\geq 0}$ as in (8) and $a>0$. Then there exists a constant stepsize $\gamma_{t}\equiv\gamma\leq\frac{1}{d}$ such that for weights $w_{t}:=(1-a\gamma)^{-(t+1)}$ and $W_{T}:=\sum_{t=0}^{T}w_{t}$ it holds:

Decreasing Stepsizes (Avoiding Log Terms).

In Lemma 2 above we collected suboptimal logarithmic terms. The averaging scheme with exponentially decreasing weights has a too short effective window to reduce the variance at the optimal \mathcal{O}\bigl{(}\frac{1}{T}\bigr{)} rate. In contrast, averaging schemes with polynomial weights can in general achieve the optimal \mathcal{O}\bigl{(}\frac{1}{T}\bigr{)} decrease of the statistical term, but do not decrease the optimization term exponentially fast (see e.g. Lacoste-Julien et al. (2012),Shamir and Zhang (2013)). This suggests that a combination of these averaging strategies might yield the best results. We analyze a simple two-phase scheme, that first performs $\frac{T}{2}$ iterations without averaging and then switches to suffix averaging scheme for the remaining iterations (this analysis could be generalized to $\alpha$-suffix averaging as in Rakhlin et al. (2012)).

Let $\{r_{t}\}_{t\geq 0}$, $\{s_{t}\}_{t\geq 0}$ as in (8), $a>0$. Then there exists stepsizes $\gamma_{t}\leq\frac{1}{d}$ and weighs $w_{t}\geq 0$, $W_{T}:=\sum_{t=0}^{T}w_{t}$, such that:

Sublinear Rate (a=0𝑎0a=0).

The previous lemma allows to derive the main result presented in this note. For completeness, we also recite a lemma that solves the recursion in the special case $a=0$.

Let $\{r_{t}\}_{t\geq 0}$, $\{s_{t}\}_{t\geq 0}$ as in (8) for $a\geq 0$. Then there exists a constant stepsize $\gamma_{t}\equiv\gamma\leq\frac{1}{d}$ such that

SGD convergence rates.

To conclude this section, we now briefly summarize our main result that follows by replacing the variables in Lemmas 2–4 by the values stated at the beginning of this section, and observing $f(\bar{\mathbf{x}}_{T})\leq\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}f(\mathbf{x}_{t})$ for convex $f$.

where here $R:=\left\lVert\mathbf{x}_{0}-\mathbf{x}^{\star}\right\rVert$, and again $W_{T}:=\sum_{t=0}^{T}w_{t}$ and $\bar{\mathbf{x}}_{T}:=\sum_{t=0}^{T}w_{t}\mathbf{x}_{t}$.

The theorem follows from the decrease Lemma 6 and Lemmas 3 and 4 with $a=\mu$, $b=1$, $c=\sigma^{2}$ and $d=2L$. For this we observe that all stepsizes $\gamma_{t}\leq\frac{1}{d}\equiv\frac{1}{2L}$, $\forall t\geq 0$. ∎

We here did not explicitly state the (suboptimal) convergence result for tuned constant stepsizes that follows directly from Lemma 2.

Discussion

We study the iteration complexity of the (stochastic) gradient descent method and recover—simultaneously—the best known rates for the function value suboptmality for an average iterate of SGD and the distance to the optimal solution of the last iterate of SGD. Our analysis focuses on the general stochastic setting, but—as a special case—we also recover the exponential convergence rates in the deterministic setting. This unified analysis address several shortcomings of previous works.

Whilst we only consider (strongly) convex functions here, further extension of the framework to larger function classes would obviously be an interesting future direction. We would like to remark that Assumption 2 potentially also covers a much larger class of functions than the few examples discussed in Section 2. For instance, the approximate gradient oracles introduced in Devolder et al. (2014) satisfy this assumption as well (cf. (Devolder et al., 2014, Theorem 1)) and, interestingly, Hölder continuous functions (which are in general not continuously differentiable) still admit approximate gradient oracles. However, as these oracles are not unbiased in general, Assumption 1 prevents the immediate application our framework in this extended setting (though, extension of our results under mild relaxations of the unbiasedness Assumption 1, similar as e.g. in Bottou et al. (2018), are immediately possible).

A small drawback our results is that one needs knowledge of $T$ and the problem parameters $\mu,L,\sigma$ to implement the schemes presented here (to decide on the stepsize, and for switching to the suffix averaging). In practice, some of these limitations can be remedied by the doubling trick. Further, just knowing $T$ up to some constant factor approximation is sufficient to recover the optimal rate up to constant factors.

Acknowledgments

We would like to thank Martin Jaggi for his support and his helpful comments and Praneeth Karimireddy for his suggestions to improve the first version of this manuscript.

References

Appendix A Technical Lemmas

We start by re-arranging (8) and multiplying both sides with $w_{t}$:

By summing from $t=0$ to $t=T$, we obtain a telescoping sum:

$W_{T}=(1-a\gamma)^{-(T+1)}\sum_{t=0}^{T}(1-a\gamma)^{t}\leq\frac{w_{T}}{a\gamma}$ (here we leverage $a\gamma\leq\frac{a}{d}\leq 1$),

and $W_{T}\geq w_{T}=(1-a\gamma)^{-(T+1)}$,

we can further simplify the left and right hand sides:

Now the lemma follows by carefully tuning $\gamma$. Consider the two cases:

If $\frac{1}{d}\geq\frac{\ln(\max\{2,a^{2}r_{0}T^{2}/c\})}{aT}$ then we choose $\gamma=\frac{\ln(\max\{2,a^{2}r_{0}T^{2}/c\})}{aT}$ and get that Equation (9) is

as in case $2\geq a^{2}r_{0}T^{2}/c$ it holds $ar_{0}T\leq\frac{2c}{aT}$.

If otherwise $\frac{1}{d}<\frac{\ln(\max\{2,a^{2}r_{0}T^{2}/c\})}{aT}$ then we pick $\gamma=\frac{1}{d}$ and get that Equation (9) is

Collecting these two cases concludes the proof. ∎

A.2 Decreasing Stepsizes (Avoiding Log Terms)

For the proof of Lemma 3 we need auxiliary results, for both of which we do not claim much novelty here.

Let $\{r_{t}\}_{t\geq 0}$, $\{s_{t}\}_{t\geq 0}$ be as in (8) for $a>0$ and for constant stepsizes $\gamma_{t}\equiv\gamma:=\frac{1}{d}$, $\forall t\geq 0$. Then it holds for all $T\geq 0$:

This follows by relaxing (8), and unrolling:

The next lemma is similar to the result derived in (Lacoste-Julien et al., 2012, Sec. 3.2), except that we cannot chose the stepsizes $\gamma_{t}$ arbitrarily large and hence need to take care of the initial conditions. Similar results were presented e.g. in Stich et al. (2018); Grimmer (2019).

Let $\{r_{t}\}_{t\geq 0}$, $\{s_{t}\}_{t\geq 0}$ as in (8) for $a>0$ and for decreasing stepsizes $\gamma_{t}:=\frac{2}{a(\kappa+t)}$, $\forall t\geq 0$, with parameter $\kappa:=\frac{2d}{a}$, and weights $w_{t}:=(\kappa+t)$. Then

where here again $W_{T}:=\sum_{t=0}^{T}w_{t}$.

where the equality follows from the definition of $\gamma_{t}$ and $w_{t}$ and the inequality from $(\kappa+t)(\kappa+t-2)=(\kappa+t-1)^{2}-1\leq(\kappa+t-1)^{2}$. Again we have a telescoping sum:

$W_{T}=\sum_{t=0}^{T}w_{t}=\sum_{t=0}^{T}(\kappa+t)=\frac{(2\kappa+T)(T+1)}{2}\geq\frac{T(T+1)}{2}\geq\frac{T^{2}}{2}$,

and $W_{T}=\frac{(2\kappa+T)(T+1)}{2}\leq\frac{2(\kappa+T)(1+T)}{2}\leq(\kappa+T)^{2}$ for $\kappa=\frac{2d}{a}\geq 1$.

By applying these two estimates we conclude the proof. ∎

We can now combine the findings of these two lemmas.

For integer $T\geq 0$, we choose stepsizes and weights as follows:

for $\kappa=\frac{2d}{a}$ and t_{0}=\bigl{\lceil}\frac{T}{2}\bigr{\rceil}. We will now show that these choices imply the claimed result.

We start with the case $T\leq\frac{d}{a}$. This case is similar to the proof of Lemma 2 and it suffices to consider Equation 9 for the choice $\gamma=\frac{1}{d}$. We observe that Equation 9 simplifies to

If $T>\frac{d}{a}$, then we obtain from Lemma 6 that

From Lemma 7 we have for the second half of the iterates:

Now we observe that the restart condition $r_{t_{0}}$ satisfies:

because $T\geq\frac{d}{a}$. These inequalities show the claim. ∎

A.3 Sub-linear Convergence rate

We start by re-arranging (8) and summing from $t=0$ to $t=T$:

If $\frac{1}{d^{2}}\leq\frac{r_{0}}{c(T+1)}$, then we pick $\gamma=\frac{1}{d}$ with $\gamma\leq\frac{\sqrt{r_{0}}}{\sqrt{c(T+1)}}$ and verify

If otherwise $\frac{1}{d^{2}}>\frac{r_{0}}{c(T+1)}$ then we pick $\gamma=\frac{\sqrt{r_{0}}}{\sqrt{c(T+1)}}$ to obtain