On the Convergence of SGD with Biased Gradients

Sometimes we will assume the Polyak- Łojasiewicz (PL) condition (which is implied by standard $\mu$-strong convexity, but is much weaker in general):

Finally, whilst the above assumptions are standard, we now introduce biased gradient oracles.

We assume that the noise and bias terms are bounded:

Our assumption on the noise is similar as in (Bottou, 2010; Stich, 2019) and generalizes the standard bounded noise assumption (for which only $M=0$ is admitted). By allowing the noise to grow with the gradient norm and bias, an admissible $\sigma^{2}$ parameter can often be chosen to be much smaller than under the constraint $M=0$.

Our assumption on the bias is similar as in (Bertsekas, 2002). For the special case when $\zeta^{2}=0$ one might expect (and we prove later) that gradient methods can still converge for any bias strength $0\leq m<1$, as in expectation the corrupted gradients are still aligned with the true gradient, $\operatorname{{\mathbb{E}}}_{\xi}\left\langle\nabla f(\mathbf{x}_{t}),\mathbf{g}(\mathbf{x},\xi)\right\rangle>0$ (see e.g. Bertsekas, 2002). In the case $\zeta^{2}>0$, gradient based methods can only converge to a region where $\left\lVert\nabla f(\mathbf{x})\right\rVert^{2}=\mathcal{O}(\zeta^{2})$. We make these claims precise in Section 4 below.

A slightly different condition than Assumption 4 was considered in (Hu et al., 2020a), but they measure the relative error with respect to the stochastic gradient $\nabla f(\mathbf{x})+\mathbf{n}(\mathbf{x},\xi)$, and not with respect to $\nabla f(\mathbf{x})$ as we consider here. Whilst we show that biased gradient methods converge for any $m<1$, for instance Hu et al. (2020a) required a stronger condition $m\leq\frac{\mu}{L}$ on $\mu$-strongly convex functions (see also Remark 7 below).

A key step in our proof is to derive a modified version of the descent lemma for smooth functions (cf. Nesterov, 2004). We give all missing proofs in the appendix.

When $M=m=\zeta^{2}=0$ we recover (even with the same constants) the standard descent lemma.

We first show that Lemma 2 allows to derive convergence on all smooth (including non-convex) functions, but only with respect to gradient norm, as mentioned in Section 3.2 above. By rearranging (5) and the notation $F_{t}:=\operatorname{{\mathbb{E}}}{f(\mathbf{x}_{t})-f^{\star}}$, $F=F_{0}$ we obtain

and by summing and averaging over $t$,

where $\Psi_{T}:=\frac{1}{T}\sum_{t=0}^{T-1}\operatorname{{\mathbb{E}}}\left\lVert\nabla f(\mathbf{x}_{t})\right\rVert^{2}$. We summarize this observation in the next lemma:

The quantity on the left hand side is equal to the expected gradient norm of a uniformly at random selected iterate, $\Psi_{T}=\operatorname{{\mathbb{E}}}\left\lVert\nabla f(\mathbf{x}_{\rm out})\right\rVert^{2}$ for $\mathbf{x}_{\rm out}\in_{\rm u.a.r.}\{\mathbf{x}_{0},\dots,\mathbf{x}_{T-1}\}$ and a standard convergence measure. Alternatively one could consider $\min_{t\in[T]}\operatorname{{\mathbb{E}}}\left\lVert\nabla f(\mathbf{x}_{t})\right\rVert^{2}\leq\Psi_{T}$.

If there is no additive bias, $\zeta^{2}=0$, then Lemma 3 can be used to show convergence of SGD by carefully choosing the stepsize to minimize the term in the round bracket. However, with a bias $\zeta^{2}>0$ SGD can only converge to a $\mathcal{O}(\zeta^{2})$ neighborhood of the solution.

If there is no bias, $\zeta^{2}=m=0$, then this result recovers the standard convergence rate of gradient descent (when also $\sigma^{2}=M=0$) or stochastic gradient descent, in general. When the biased gradients are correlated with the gradient (i.e. $\zeta^{2}=0$, $m>0$), then the exact solution can still be found, though the number of iterations increases by a factor of $(1-m)$ in the deterministic case, or by $(1-m)^{2}$ if the noise term is dominating the rate. When there is an uncorrelated bias, $\zeta^{2}>0$, then SGD can only converge to a neighborhood of a stationary point and a finite number of iterations suffice to converge. This result is tight in general, as we show in Remark 5 below.

To show convergence under the PL condition, we observe that (5) and (4) imply

By now unrolling this recursion we obtain the next theorem.

This result shows, that SGD with constant stepsize converges up to the error floor $\mathcal{O}(\zeta^{2}+\gamma L\sigma^{2})$, given in (7). The second term in this bound can be decreased by choosing the stepsize $\gamma$ small, however, the first term remains constant, regardless of the choice of the stepsize. We will investigate this error floor later in the experiments.

Without bias terms, we recover the best known rates under the PL condition (Karimi et al., 2016). Compared to the SGD convergence rate for $\mu$-strongly convex function our bound is worse by a factor of $\kappa$ compared to (Stich, 2019), but we consider convergence of the function value of the last iterate $F_{T}$ here.

Albeit Theorem 4 shows convergence of the gradient norms, this convergence does not imply convergence in function value in general (unless the gradient norm is related to the function values, as for instance guaranteed by (4)). We now give an example of a weakly-convex (non-strongly convex) smooth function, where Algorithm 1 can diverge.

This result shows that in general it is not possible to converge when $\zeta^{2}\neq 0$, and that the approximate solutions found by SGD with unbiased gradients (in Example 8 converging to 0) and by SGD with biased gradients can be arbitrarily far away. It is an interesting open question, whether SGD can be made robust to biased updates, i.e. preventing this diverging behaviour through modified updates (or stronger assumptions on the bias). We leave this for future work.

The well-known top-$k$ spasification operator (Dryden et al., 2016; Alistarh et al., 2018) that selects the $k$ largest coordinates of the gradient vector $\nabla f(\mathbf{x})$ is a biased gradient oracle with $m\leq\frac{d-k}{d}$ and $\zeta^{2}=0$. This means, that GD with top-$k$ compression converges to a stationary point on smooth functions and under the PL condition the convergence rate is $\mathcal{O}\bigl{(}\frac{d}{k}\kappa\log\frac{1}{\epsilon}\bigr{)}$ when there is no additional noise. This recovers the rate of greedy coordinate descent when analyzed in the Euclidean norm (Nutini et al., 2015).

The biased random-$k$ sparsification operator randomly selects $k$ out of the $d$ coordinates of the stochastic gradient, and sets the other entries to zero. As $m=1-\frac{k}{d}$, this implies a $\frac{d}{k}$ slowdown over the corresponding rates of GD (recovering the rate of random coordinate descent (Nesterov and Spokoiny, 2017; Richtárik and Takác, 2016)) and SGD, with asymptotic dominant term $\mathcal{O}\bigl{(}\frac{d\sigma^{2}}{k}\bigr{)}$ that is expected (cf. Chaturapruek et al., 2015). In the appendix we further discuss differences to unbiased random-$k$ sparsification.¹¹1By rescaling the obtained sparse vector by the factor $\frac{d}{k}$ one obtains a unbiased estimator (with higher variance). With these sparsification operators the dominant term in the rate remains $\mathcal{O}\bigl{(}\frac{d\sigma^{2}}{k}\bigr{)}$, but the optimization terms can be improved as a benefit of choosing larger stepsizes. However, this observation does not show a limitation of the biased rand-$k$ oracle, but is merely a consequence of applying our general result to this special case. Both algorithms are equivalent when properly tuning the stepsize.

Next, we discuss the zeroth-order gradient oracle obtained by Gaussian smoothing (cf. Nesterov and Spokoiny, 2017). This oracle is defined as (Polyak, 1987):

where $\tau>0$ is a smoothing parameter and $\mathbf{u}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$ a random Gaussian vector. Nesterov and Spokoiny (2017, Lemma 3 & Theorem 4) provide estimates for the bias:

and the second moment:

We conclude that Assumptions 3, and 4 hold with:

Nesterov and Spokoiny (2017) show that on smooth functions gradient-free oracles in general slow-down the rates by a factor of $\mathcal{O}(d)$, similar as we observe here with $M=\mathcal{O}(d)$. However, their oracle is stronger, for instance they can show convergence (up to $\mathcal{O}(\zeta^{2})$) on weakly-convex functions, which is not possible with our more general oracle (see Example 8).

Devolder et al. (2014) introduced the notion of inexact gradient oracles. A $(\delta,L)$-gradient oracle for $\mathbf{y}\in\mathbb{R}^{d}$ is a pair $(\tilde{f}(\mathbf{y}),\tilde{\mathbf{g}}(\mathbf{y}))$ that satisfies $\forall\mathbf{x}\in\mathbb{R}^{d}$:

We have by (Devolder et al., 2014):

hence we can conclude: $\zeta^{2}=2\delta L$ and $m=0$.

It is important to observe that the notion of a $(\delta,L)$ oracle is stronger than what we consider in Assumption 4. For this, consider again the Huber-loss from Example 8 and a $(\delta,L)$ gradient estimator $\tilde{\mathbf{g}}(x)$. For $x\to\infty$, we observe that it must hold $\left\lVert\tilde{\mathbf{g}}(x)-\nabla h(x)\right\rVert\to 0$, otherwise the condition of the $(\delta,L)$ oracle is violated. In contrast, the bias term in Assumption 4 can be constant, regardless of $x$. Devolder (2011, preprint) generalized the notion of $(\delta,L)$ oracles to the stochastic case, which we discuss in the appendix.

The notion of top-$k$ compressors has been generalized to arbitrary $\delta$-compressors, defined as

This notion has for instance been used in (Beznosikov et al., 2020; Stich et al., 2018). For this class of operator it holds

In the noiseless case, our results show convergence for arbitrary small $\delta>0$ ($m<1)$ and we recover the rates given in (Beznosikov et al., 2020, Theorem 1).

Another example of updates that can be viewed as biased gradients, are delayed gradients, for instance arising in asynchronous implementations of SGD (Niu et al., 2011). For instance Li et al. (2014, Proof of Theorem 2) provide a bound on the bias. See also (Stich and Karimireddy, 2019) for a more refined analysis in the stochastic case. However, these bounds are not of the form as in Assumption 4, as they depend on past gradients, and not only the current gradient at $\mathbf{x}_{t}$. We leave generalizations of Assumption 4 for future work (moreover, delayed gradient methods have been analyzed tightly with other tools already).

In our first setup (Figure 1), we consider a synthetic case in which we add a constant value $\zeta\in\{0,0.1,0.001\}$ to the gradient to control the bias, and vary the noise $\sigma^{2}\in\{0,1\}$. This corresponds to the setting where we have $m=0,\zeta^{2}>0$, $M=0$, $\sigma^{2}\geq 0$.

Discussion of Results. Figure 1 highlights the effect of the parameters $\sigma^{2}$ and $\zeta^{2}$ on the rate of the convergence and the neighbourhood of the convergence. Notice that a small bias value can only affect the convergence neighborhood when there is no stochastic noise. In fact this matches the error floor we derived in (7). When $\zeta^{2}$ is small compared to $\sigma^{2}$, i.e, the bias is insignificant compared to the noise, the second term in (7) determines the neighborhood of the optimal solution to which SGD with constant stepsize converges. In contrast, when $\zeta$ is large the first term in (7) dominates the second term and determines the neighborhood of the convergence. As mentioned earlier in Section 4.3, the second term in (7) also depends on the stepsize, meaning that by increasing (decreasing) the stepsize the effect of $\sigma^{2}$ in determining the convergence neighborhood can be increased (decreased).

In contrast to the previous section, we leave the completely synthetic setup, and consider structured bias that arises from compressing the gradients by using either the random-$k$ or top-$k$ method (Alistarh et al., 2018), displayed in Figures 2, 3. We use the same objective function $f$ as introduced earlier. In each iteration we compress the stochastic gradient, $\sigma^{2}\in\{0,1,100\}$, by the top-$k$ or random-$k$ method, i.e.,

where $\mathcal{C}$ is either $\operatorname*{{top-k}}$ or $\operatorname{{rand-k}}$ operator, for $\frac{k}{d}\in\{0.1,1\}$. As we showed in Section 5, this corresponds to the setting $\zeta^{2}=0$ for rand-$k$, and $\zeta^{2}>0$ for top-$k$, with $m=1-\frac{k}{d}$.

Error floor. Figure 2, 3 show the effect of the parameters $\sigma^{2}$ and $k$ (that determine the level of noise and bias respectively) on the rate of convergence as well as the error floor, when using random-$k$ and top-$k$ compressors and a constant stepsize $\gamma$.

Convergence rate. In Figure 5 we show the convergence for different noise levels $\sigma^{2}$ and compression parameters $k$. For each configuration and algorithm, we tuned the stepsize $\gamma$ to reach the target accuracy (set by $\epsilon$) in the fewest number of iterations as possible.

We optimize the function $f$ using the zeroth-order gradient oracle defined in Section 5.2. The smoothing parameter $\tau$ affects both the values of $\sigma^{2}$ and $\zeta^{2}$ and hence the error floor.

Discussion of Results. Figure 4 shows the error floor for the zeroth-order gradient method with different values of $\tau$. We can observe that the difference between the error floors matches what we saw in theory, i.e, $\sigma^{2}+\zeta^{2}\sim\mathcal{O}(\tau^{2})$.

We use the PyTorch framework (Paszke et al., 2019) to empirically compare top-$k$ and random-$k$ with SGD without compression for training Resnet+BN+Dropout (Resnet18) (He et al., 2016) on the CIFAR-10 dataset (Krizhevsky, 2012). Following the standard practice in compression schemes (Lin et al., 2018; Wang et al., 2018), we apply the compression layer-wise. We use SGD with momentum and we tune the momentum parameter $\beta$ and the learning rate separately for each setting (see Appendix C). Although SGD with momentum is not covered by our analysis, we use this method since it is the state-of-the-art training scheme in deep learning and required to reach a good accuracy. In each setting we trained the neural network for 180 epochs and report the cross entropy error for the training data.

Discussion of results. Figure 6 shows the convergence. We can observe that similar to Figures 2 and 3, top-$k$ can still converge to the same error floor as SGD but with a slower rate. Rand-$k$ is more severely impacted by the $\mathcal{O}(\frac{d}{k})$ slowdown predicted by theory and would require more iterations to converge to higher accuracy.