Adding some noise

This content is available as a PDF here.

Contents

Stochastic gradient descent (SGD) is the workhorse of modern machine learning. Almost all recent achievements ($\ge$ 2010s) in computer vision, natural language processing are somehow connected to the use of SGD (or one of its multiple generalization). Despite this modern aspect, SGD takes its root in the seminal paper of (Robbins, Herbert and Monro, Sutton, 1951), more than 70 years ago. The key insight of Robbins and Monro is that first orders method are robust. What does it means? The gradient descent does not need an exact computation of the gradient, it only need that in average the computation is correct up to some “stochastic” errors. We will formalize this idea in this chapter. again inspired by the lecture notes of (Bach, Francis, 2021). A key insight from the seminal paper by (Bottou, Léon and Bousquet, Olivier, 2007) is that in machine learning, high precision is not required since it is meaningless to optimize below the statistical error. This paper considerably relaunched the interest towards SGD, especially for empirical risk minimization.

1 Stochastic approximation

Let $(\mathrm{\Omega },\mathcal{A},\mathbb{P})$ a probability space. We consider the following stochastic approximation problem

$$\begin{array}{}\text{(1)}& x^{\star }\in \arg \underset{x\in {\mathbb{R}}^d}{min}f(x):={\mathbb{E}}_{\xi \sim \mathbb{P}}[F(x;\xi )].\end{array}$$

Observe that (1) encompasses two important problem of supervised machine learning: expected risk minimization and empirical risk minimization. Let us recall basic fact on risk minimization. Our goal is given observations ¹ (couple of features and responses) $(c_i,r_i)\in C\times R$, for $i=1,\dots ,N$, the goal is to predict a new response $r\in R$ given a new feature $f\in C$. Consider now the test distribution $\mathbb{P}$ on $\mathrm{\Omega }=C\times R$ and a loss function $\ell :R\times R\to \mathbb{R}$.

• • Expected risk minimization. The expected risk (or simply risk) of a predictor $\varphi :C\to R$ is the quantity

$$\mathbb{R}(\varphi )={\mathbb{E}}_{(c,r)\sim \mathbb{P}}[\ell (r,\varphi (c))]={\int }_{C\times R}\ell (r,\varphi (c))d\mathbb{P}(c,r).$$

This minimization problem fits the framework of (1) with $x=(c,r)$, $F=\ell$ and $\mathbb{P}$ is the joint probability on $F\times R$.

• • Empirical risk minimization. The practical counterpart of the expected risk is the empirical risk defined as

$$\hat{\mathbb{R}}(\varphi )=\frac{1}{N}\sum _{i=1}^N\ell (r_i,f(c_i)).$$

Again, this minimization problem fits the framework of (1) with $x=(c,r)$, $F=\ell$, but now $\mathbb{P}$ is the empirical distribution based on the test data $(c_i,r_i)$.

2 Stochastic gradient descent

We suppose that we have access to stochastic estimation $g_{t+1}(x^t)$ of the gradient $\mathrm{\nabla }f(x^{(t)})$, i.e.,

$$\begin{array}{}\text{(2)}& x^{(t+1)}=x^{(t)}-{\eta }^{(t)}{g}^{(t+1)}(x^{(t)};{\xi }^{(t)}).\end{array}$$

The stochastic gradient algorithm is NOT a descent method in the sense of of the oracle $g^{(t+1)}(x^{(t)};{\xi }^{(t)})$ is not necessarly a descent direction as defined for instance in our lecture on the gradient descent.

Two situations:

• • Stochastic approximation. Here we have access to an additive noisy version of the “true” gradient:

$$g^{(t)}(x;\xi )=\mathrm{\nabla }f(x)+\xi .$$

• • Learning from samples. On the contrary, here we have for instance $\mathbb{P}$ that is a uniform choice between $i\in 1,\dots ,N$:

$$g^{(t)}(x;\xi )=\mathrm{\nabla }{f}_{\xi }(x),$$

where $\xi \sim \mathcal{U}(1,\dots ,N)$.

The standard assumption when dealing with SGD is the access to an unbiased estimator of the gradient.

Note that it is possible to deal with biased oracles, but this goes beyond the limit of this course.

We are going to study the convergence of SGD in expectation, that is the main way to analyze in the machine learning community the stochastic convergence. Nevertheless, the stochastic approximation literature, starting from (Robbins, H. and Siegmund, D., 1971), are often concerned with almost sure convergence based on martingale tools.

For convex function, we will assume that the noisy gradient $g^{(t)}$ are bounded almost-surely.

The simplest strategy to choose the step size, as for the batch gradient descent, is to fix some ${\eta }^{(t)}=\eta >0$. Unfortunately, this method does not converge towards a minimizers of (1)! It is nevertheless, the most frequent use of SGD in practice. Why? Because, despite the nonconvergence, it is possible to show that the iterations are “close enough” to the true minimizer in the following sense (even if $f$ is not convex).

A consequence is that when $T$ goes to $+\mathrm{\infty }$, the expected squared-norm of the gradient of a point uniformly chosen from the trajectory of SGD lies in a ball of radius $\frac{\eta L{B}^2}{2}\propto \eta$ centered in 0.

This is illustrated in the video below

The situation is radically different from the batch mode where the asymptotic regime produce a true solution.

3 Convergence rate in the convex setting

We now dive away from the constant stepsize framework, and will study what happens when ${\eta }^{(t)}$ varies accross iterations. The following theorem gives the $O(1/\sqrt{t})$ rate of SGD in the convex case.

Several remarks needs to be stated:

• • As claimed before, SGD is not a descent method. Moreover, we proved here the convergence in expectation of the value function of the averaged iterates $x^{(t)}$. Note that almost-sure convergence can be proved, but with more involved arguments, see for instance (Sebbouh, Othmane and Gower, Robert M. and Defazio, Aaron, 2021) and references therein.

• • It is possible to replace the noisy gradient step by a projected noisy gradient step, i.e., using the algorithm defined by

$$x^{(t+1)}={\mathrm{\Pi }}_{B(x^{(0)},D)}(x^{(t)}-{\eta }^{(t)}{g}^{(t+1)}(x^{(t)};{\xi }^{(t)})).$$

The obtained results are exactly the same.

• • It is also possible to remove the assumption that $x^{(0)}$ lives in a neighborhood of an optimal solution $x^{\star }$ and requires instead that $F$ is $B$-smooth. Note that in this case, we do not obtain better results (contrary to the nonstochastic setting).

• • The bound can be shown to optimal (Agarwal, Alekh and Bartlett, Peter L. and Ravikumar, Pradeep and Wainwright, Martin J., 2012, Theorem 1) (at least in the Lipschitz setting).

4 Minibatch Stochastic Gradient Descent

The minibatch idea is to make a tradeoff between the fast rate of the gradient descent but linear depency on $N$, and the slow rate of SGD but dimension-free dependency: we reduce the variance of the noise, but have a higher running time. Minibatching can also take advantage of parallel architectures such as GPU or SIMD instructions on CPU. A minibatch is built upon $B$ call to the stochastic oracle, and its SGD step associated is written as

$$x^{(t+1)}=x^{(t)}-\frac{{\eta }^{(t)}}{M}\sum _{m=1}^M{g}^{(t+1)}(x^{(t)};{\xi }_b^{(t)})\text{where}({\xi }_1^{(t)},\dots ,{\xi }_M^{(t)})\sim \mathcal{M}(M,N).$$

Observing that ${\tilde{g}}^{(t+1)}(x,\xi \xi )=\frac{1}{M}\sum _{m=1}^M{g}^{(t+1)}(x;{\xi }_m)$ is an unbiased estimator of the gradient of $f$, indeed

$$\begin{array}{rl}{\mathbb{E}}_{\xi \xi }[{\tilde{g}}^{(t+1)}(x^{(t)};\xi \xi )|x^{(t)}]& ={\mathbb{E}}_{\xi \xi }[\frac{1}{M}\sum _{m=1}^M{g}^{(t+1)}(x^{(t)};{\xi }_m)|x^{(t)}]\\ & =\frac{1}{M}\sum _{m=1}^M{\mathbb{E}}_{\xi \xi }[g^{(t+1)}(x^{(t)};{\xi }_m)|x^{(t)}]& \text{by linearity}\\ & =\frac{1}{M}\sum _{m=1}^M\mathrm{\nabla }f(x^{(t)})=\mathrm{\nabla }f(x^{(t)})& \text{unbiasedness.}\end{array}$$ The minibatch gradient is also bounded, indeed

$$\begin{array}{rl}\Vert {\tilde{g}}^{(t+1)}(x^{(t)};\xi \xi ){\Vert }_2^2& =\Vert \frac{1}{M}\sum _{m=1}^M{g}^{(t+1)}(x^{(t)};{\xi }_m){\Vert }_2^2\\ & \le \frac{1}{M^2}\sum _{m=1}^M\Vert g^{(t+1)}(x^{(t)};{\xi }_m){\Vert }_2^2\\ & \le \frac{B^2}{M}\mathbb{P}\text{-almost surely.}\end{array}$$ We can hence apply Theorem 2. A lot of effort has been done in the last year to determine what is the optimal minibatch size, see e.g., (Gower, Robert Mansel and Loizou, Nicolas and Qian, Xun and Sailanbayev, Alibek and Shulgin, Egor and Richtárik, Peter, 2019), or to derive schedule policy with increasing size of the minibatch.

Agarwal, Alekh and Bartlett, Peter L. and Ravikumar, Pradeep and Wainwright, Martin J. (2012). Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization.

Bach, Francis (2021). Learning Theory from First Principles.

Bottou, Léon and Bousquet, Olivier (2007). The Tradeoffs of Large Scale Learning, Curran Associates, Inc..

Gower, Robert Mansel and Loizou, Nicolas and Qian, Xun and Sailanbayev, Alibek and Shulgin, Egor and Richtárik, Peter (2019). SGD: General Analysis and Improved Rates, PMLR.

Robbins, H. and Siegmund, D. (1971). A CONVERGENCE THEOREM FOR NON NEGATIVE ALMOST SUPERMARTINGALES AND SOME APPLICATIONS**Research Supported by NIH Grant 5-R01-GM-16895-03 and ONR Grant N00014-67-A-0108-0018., Academic Press.

Robbins, Herbert and Monro, Sutton (1951). A Stochastic Approximation Method, Institute of Mathematical Statistics.

Sebbouh, Othmane and Gower, Robert M. and Defazio, Aaron (2021). Almost Sure Convergence Rates for Stochastic Gradient Descent and Stochastic Heavy Ball, PMLR.