Adding some noise

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

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 ¹¹ 1 Variables $c$ and $r$ are typically denoted $x$ and $y$ in a ML courses, but we want to keep them free for the optimization variable. (couple of features and responses) $(c_i,r_i)\in C\times R$, for $i=1,\mathrm{\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 $\mathrm{\ell }:R\times R\to ℝ$.

• •

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

This minimization problem fits the framework of (1) with $x=(c,r)$, $F=\mathrm{\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

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

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

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:

• •

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

where $\xi \sim 𝒰(1,\mathrm{\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

<video autoplay muted src="adding-some-noise-anim_iterates.mp4" type="video/mp4" />

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

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

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).

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

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

The minibatch gradient is also bounded, indeed

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.