The convergence of the Stochastic Gradient Descent (SGD) : a self-contained proof
We give here a proof of the convergence of the Stochastic Gradient Descent (SGD) in a self-contained manner.
\section{Introduction}
 The Stochastic Gradient Descent (SGD) or other algorithms derived from it are used extensively in Deep Learning, a branch of Machine Learning; but the proof of convergence is not always easy to find. The goal of this paper is to adapt various proofs from the literature in a simple format.  
 In particular no claim of originality is made (see \cite{turinici2020convergence,ayadi2020stochastic,turinici2020xray,Turinici_2019
} for some of my recent research papers in this area); on the contrary please cite this work if you find it useful (arxiv or DOI: \text{10.5281/zenodo.4638695}).
 
 This proof can be used in any domain where a self-contained presentation is needed.
 
 \section{Recall of the general framework}
 
 Suppose $(\Omega,F,\mathbb{P})$ is a probability space,  
 $L:\Omega \times \mathbb{R}^N \to \mathbb{R}$ a function depending on a random argument $\omega$ and a parameter $X$ (second argument) to be optimized. Denote 
 \begin{equation}
     \mathcal{L}(X) = \mathbb{E}_\omega [ L(\omega,X)].
 \end{equation}
 The goal of the SGD is to find a minimum of $\mathcal{L}$. It operates iteratively by taking at iteration $n$:
\begin{itemize}
\item  a (deterministic) "learning rate" $\rho_n$ (schedule fixed {\it a priori} 
\item a random $\omega_n \in \Omega$ independent of any other previous random variables is drawn (following the law $\mathbb{P}$)
\item and updating by the formula
\begin{equation}
X_{n+1} = X_n - \rho_n \nabla_x L(\omega_n,X_n).
\end{equation}
\end{itemize}

 
 
 \section{Hypothesis on $L$ and $\mathcal{L}$}
 
 In order to prove the convergence we need some hypothesis that are detailed below
 
\begin{enumerate}
\item 
    The gradient of $L$ is bounded:
 \begin{equation}
     \exists B > 0 : \ 
     \sup_\omega 
     \| \nabla_X L(\omega,X) \|^2 \le B, \ \forall X \in \mathbb{R}^N.
 \label{eq:hypgradbounded}
 \end{equation}
\item $\mathcal{L}$ is strongly convex:
\begin{equation}
\exists \mu > 0 : \     \mathcal{L}(Y) \ge \mathcal{L}(X) + \langle \nabla \mathcal{L}(X), Y-X \rangle + \frac{\mu}{2} \|X-Y\|^2, \ \forall X,Y \in \mathbb{R}^N.
\label{eq:hypstrongconvex}
 \end{equation}
Note that for $\mu=0$ this is just the usual convexity, i.e. the function is above its tangent. 
For general $\mu$ this tells that the function is even above a parabola centered in any $X$. For regular functions this means that the Hessian
$D^2 \mathcal{L}$ of $\mathcal{L}$ satisfies $D^2 \mathcal{L} \ge \mu \cdot I_N$\footnote{Here $I_N$ is the $N\times N$ identity matrix.}. 
\end{enumerate}


\section{A convergence result and its proof}

We fill prove the following

\begin{theorem}
Suppose that each $L(\omega,\cdot)$ is differentiable (a.e. $\omega \in \Omega$)\footnote{This requirement can be largely weakened. For instance in the case of ReLU activation, which corresponds to the positive part $x\mapsto x_+$,  one can employ any suitable sub-gradient of the $x_+$ function and in particular take at the non-regular point $x=0$ any value between $0$ and $1$.} and that 
$\mathcal{L}$ satisfies the hypothesis 
\eqref{eq:hypgradbounded} and \eqref{eq:hypstrongconvex}. 
 Then 
 \begin{enumerate}
\item the function $\mathcal{L}$ has an unique minimum $X_*$;
\label{item:uniqueness}
     \item \label{item:inequalitydn}
For any $n \ge 0$ denote
 \begin{equation}
     d_n =  \mathbb{E} \left[ \|X_{n}-X_*\|^2 \right].
 \end{equation}
 Then
 \begin{equation}
     d_{n+1} \le      (1-\rho_n \mu) d_n + \rho_n^2 B.
\label{eq:dnplusone} \end{equation}
\item \label{item:constant}
For any $\epsilon > 0$ there exists a $\rho > 0$ such that if $\rho_n = \rho$ then 
\begin{equation}
    \limsup_{n\to \infty}  \mathbb{E} \left[ \|X_{n+1}-X_*\|^2 \right] \le \epsilon.
\label{eq:estimationvoisinage}
\end{equation}
\item \label{item:convergence}
Take $\rho_n$ a sequence such that:
\begin{equation}
\rho_n \to 0 \text{ and } \sum_{n\ge 1} \rho_n = \infty.
\label{eq:hyprhon}
\end{equation}
 Then $d_n \to 0$, that is 
 $\lim_{n \to \infty }X_n = X_*$, where the convergence is the $L^2$ convergence of random variables.
\end{enumerate}
 \begin{proof}
{\bf Item \ref{item:uniqueness}}:
The existence and uniqueness of the optimum is guaranteed by the assumptions of strong convexity and smoothness of $\mathcal{L}$.

\noindent {\bf Item \ref{item:inequalitydn}}:
We have
\begin{align}
&    \mathbb{E} \left[ \|X_{n+1}-X_*\|^2 \right]  = 
    \mathbb{E} \left[ \|X_{n}-X_* - \rho_n \nabla_x L(\omega_n,X_n)\|^2 \right]  
\nonumber    \\&= 
    \mathbb{E} \left[ \|X_{n}-X_*\|^2 \right]  +
\rho_n^2    \mathbb{E} \left[ \|\nabla_x L(\omega_n,X_n)\|^2 \right]  
- 2 \rho_n 
    \mathbb{E} \left[ \langle X_{n}-X_*, \nabla_x L(\omega_n,X_n)\rangle \right].
\end{align}
First we remark that\footnote{The formal justification is as follows: 
denote  by $\mathcal{F}_n$ the sigma algebra generated by $X_1$, ..., $X_n$, $\omega_1$, ..., $\omega_{n-1}$. In particular $\omega_n$ is independent of
$\mathcal{F}_n$. Recall now that for any random variables $U$ measurable with respect to $\mathcal{F}_n$ and $V$ independent of $\mathcal{F}_n$:
$ \mathbb{E}[ g(U,V) | \mathcal{F}_n] = \int g(v,U) P_V(dv) $ and in particular
$\mathbb{E}[ g(U,V)]= \mathbb{E}[\mathbb{E}[ g(U,V) | \mathcal{F}_n]]= 
\mathbb{E}[ \int g(v,U) P_V(dv)]$.
}
$$   \mathbb{E} \left[ \langle X_{n}-X_*, \nabla_x L(\omega_n,X_n)\rangle \right]
 = \mathbb{E} \left[ \langle X_{n}-X_*, \nabla \mathcal{L}(X_n)\rangle \right].
$$
But at its turn
\begin{align}
    &
\mathbb{E} \left[ \langle X_{n}-X_*, \nabla \mathcal{L}(X_n)\rangle \right] \ge 
\mathbb{E} \left[ \mathcal{L}(X_n) - \mathcal{L}(X_*) + \frac{\mu}{2}  \|X_{n}-X_*\|^2 \right] 
\nonumber\\& 
\ge \frac{\mu}{2}  \mathbb{E}  [\|X_{n}-X_*\|^2],
\end{align}
the last inequality being guaranteed by the fact that $X_*$ is the minimum.
Putting together all relations proved so far one obtains the relation
\eqref{eq:dnplusone}.

\noindent {\bf Item \ref{item:constant}}:
When $\rho_n$ is constant equal to $\rho$ inequality \eqref{eq:dnplusone} is equivalent to 
$$d_{n+1} - \rho \frac{B}{\mu} \le (1-\rho \mu) (d_n - \rho \frac{B}{\mu}).$$
Since the function $x \mapsto x_+$ (the positive part) is increasing we obtain for $\rho < 1/\mu$:
$$\left(d_{n+1} - \rho \frac{B}{\mu} \right)_+
\le (1-\rho \mu) \left(d_n - \rho \frac{B}{\mu}\right)_+,$$
and by iteration, for any $k\ge 1$:
$$\left(d_{n+k} - \rho \frac{B}{\mu} \right)_+
\le (1-\rho \mu)^k \left(d_n - \rho \frac{B}{\mu}\right)_+.$$
Taking $k\to \infty$ we obtain 
$\limsup_k \left(d_{k} - \rho \frac{B}{\mu} \right)_+=0$ hence the conclusion \eqref{eq:estimationvoisinage} for $\rho$ smaller then $1/\mu$
 and $\epsilon \mu / B$.

\noindent {\bf Item \ref{item:convergence}}:
For non-constant $\rho_n$ and arbitrary fixed $\epsilon$
we obtain from \eqref{eq:dnplusone}
$$d_{n+1} - \epsilon \le (1-\rho_n \mu) (d_n - \epsilon) + \rho_n (\rho_n B - \mu \epsilon).$$ 
When $n$ is large enough $\rho_n (\rho_n B - \mu \epsilon)\le 0$ and 
thus 
$$d_{n+1} - \epsilon \le (1-\rho_n \mu) (d_n - \epsilon),$$ 
therefore 
$$\left(d_{n+k} - \epsilon\right)_+
\le (1-\rho_n \mu) \left(d_n - \epsilon\right)_+.$$
Iterating such inequalities we obtain
$$\left(d_{n+k} - \epsilon \right)_+
\le \prod_{\ell=n}^{n+k-1} (1-\rho_\ell \mu) \left(d_n - \epsilon \right)_+.$$
From the Lemma \ref{lemma:product} we obtain
$\lim_{k \to \infty} \left(d_{k} - \epsilon \right)_+=0$ and since this is true for any $\epsilon$ the conclusion follows.
\end{proof}


\end{theorem}
\begin{lemma}
Let $\mu >0$ and $\rho_n$ a sequence of positive real numbers such that $\rho_n \to 0$ and $\sum_{n\ge 1} \rho_n = \infty$. Then for any $n \ge 0$:
\begin{equation}
\lim_{k\to \infty}    \prod_{\ell= n}^{n+k} (1-\rho_\ell \mu) = 0.
\end{equation}
\label{lemma:product}
\end{lemma}
\begin{proof}
Recall that for any $x \in ]0,1[$ we have $\log(1-x) \le -x$; 
then:
\begin{equation}
0 \le   \prod_{\ell= n}^{n+k} (1-\rho_\ell \mu) = e^{ \sum_{\ell= n}^{n+k} \log(1-\rho_\ell \mu)} \le e^{ \sum_{\ell= n}^{n+k} (-\rho_\ell \mu)} \overset{k\to \infty}{\longrightarrow} e^{- \infty} =0,
\end{equation}
which concludes the proof.
\end{proof}

\section{Concluding remarks}
We make here some remarks concerning the hypothesis and the use in Neural Networks.

First, consider the hypothesis $\sum_n \rho_n= \infty$; at first it may seem strange but this is not really so. Note that in particular it is true when $\rho_n$ is a constant. But in general, if we forget the stochastic part\footnote{This can be made precise when the stochastic part is added, see \cite{ayadi2020stochastic}.}, one can interpret the SGD as following some continuous time dynamics  of the type $X'(t) = - \nabla \mathcal{L}(X)$; for the simple quadratic function $\mathcal{L}(X)=  \alpha \|X\|^2 / 2$ the dynamics is 
$X'(t)  = -\alpha X(t)$ with solution $X(t) = e^{-\alpha t}X(0)$ needs an infinite 'time' $t$ to converge to the minimum $X_*=0_N$. Or here $\sum_n \rho_n$ is the discrete version of the time and thus it is not a surprise to need infinite time to obtain $X_*$ with infinite precision. On the other hand if a finite precision is needed one can just take a constant time step as indicated in the theorem\footnote{but in this case one may spend a too long time to wait for the convergence to this small neighborhood to arrive see \cite{ayadi2020stochastic} for some ways to accelerate the convergence.}.


On the other hand, an important example that satisfies 
\eqref{eq:hyprhon} is $\rho_n = \frac{c_1}{c_2 + n}$, with $c_1, c_2 > 0$. In general giving a functional form for $\rho_n$ is termed 'choosing a decay rate', but it may not be clear what the best decay rate is in general.  


2021-03-29T02:15:47.000
2103
2103.14350
en
https://arxiv.org/abs/2103.14350
We give here a proof of the convergence of the Stochastic Gradient Descent (SGD) in a self-contained manner.
Machine Learning (stat.ML); Machine Learning (cs.LG); Probability (math.PR)
The convergence of the Stochastic Gradient Descent (SGD) : a self-contained proof
Qwen/Qwen-72B
1. YES
2. YES