\section{Introduction}

Stochastic gradient descent algorithms play an important role in convex and non-convex optimization. They are used in machine learning when the computation of the exact gradient of the objective function is computationally costly, but stochastic approximations can be evaluated fairly cheaply. The stochastic noise is furthermore believed to aid the algorithm in non-convex optimization by allowing it to escape `bad' local minima and saddle points.

 this work, we analyze toy models for stochastic gradient descent in machine learning applications. These differ from more classical perspectives principally in the fact that the intensity of noise in estimating $\nabla f(\theta)$ depends on the value $f(\theta)$ of the objective function. By comparison, more classical works on SGD assume uniform $L^p$-bounds for $p\in [2,\infty)$, independently of $\theta$. Our toy models are inspired by overparametrized supervised learning, i.e.\ minimization problems where the objective function vanishes on a high-dimensional set. In this setting, SGD with ML noise has the following novel properties:

\begin{enumerate}
\item The learning rate has to be small in terms of the smoothness of the objective function and the noise intensity, but can be uniformly positive for all time.
\item If the learning rate remains uniformly positive, we can prove almost sure convergence to a global minimizer, not just a critical point that is not a strict saddle.
\end{enumerate}

Let us make these claims more precise. The crucial property of ML noise is that its variance scales at most linearly with the objective function $f$. In particular, if $f$ is small, so is the noise. If $f$ satisfies a \L{}ojasiewicz inequality (e.g.\ if $f$ is strongly convex), the learning rate has to be small enough for the noise to not exceed a certain strength, and compared to the Lipschitz constant of $\nabla f$. It does not have to vanish asymptotically to guarantee convergence to the global minimum. In this sense, SGD with ML noise resembles deterministic GD more than it does SGD with classical noise. For details, see Theorem \ref{theorem linear convergence}. 

If the learning rate is strictly positive, at any time there are two options:
\begin{itemize}
\item $f(\theta_t)$ is small and so is the noise. If $f$ has good properties on the set $\{f<\varepsilon\}$ for some $\varepsilon>0$, then with large probability we stay inside the set once we enter for the first time. Conditioned on this event, we expect to converge to a minimizer linearly.
\item $f(\theta_t)$ is large and so is the noise. If $f$ has nice properties on the set $\{f>S\}$ for some $S>0$, we expect SGD with ML noise to not let us escape to infinity despite the growing noise intensity. If additionally the set $\{f\leq S+1\}$ is not too spread out away from the set of minimizers and the noise is `uniformly unbounded' (but with bounded variance), then from any point in $\{f\leq S+1\}$ there is a positive probability of jumping into the set $\{f<\varepsilon\}$ independently of the local gradient.
\end{itemize}

This intuition can be extended and made precise. In particular, under strong conditions on the target function and noise, we find that we converge linearly to a minimizer almost surely from any finite energy initialization. However, since the probability of jumping into the set $\{f<\varepsilon\}$ may be exceedingly small, we note that we do not expect to observe this linear convergence on realistic time scales in complicated real world applications for poor initialization. A precise statement of our main result can be found in Theorem \ref{theorem global convergence}.

Stochastic gradient descent can be studied as a general tool in convex and non-convex optimization or specifically in the context of deep learning applications. In this article, we take a balanced approach by incorporating key features of the energy landscape and stochastic noise in deep learning problems, but without specializing to a specific machine learning model. 

The article is structured as follows. In Section \ref{section review}, we review known results on stochastic gradient descent and objective functions in deep learning. We deduce some properties of the energy landscape and stochastic noise which a suitable toy model should satisfy. Discrete time SGD with ML noise is discussed in Section \ref{section discrete}. Numerical examples in Section \ref{section numerical} illustrate the difference of SGD with classical and ML noise in a toy problem. Some proofs are postponed to the appendices. Continuous time results on continuous time SGD with noise of ML type are presented in a companion article \cite{continuous_sgd}.

The different parts of the article -- analysis of energy landscape and noise, discrete time analysis -- can be read independently, and a reader only interested in one chapter can easily skip ahead.


\subsection{Context} 

Stochastic gradient descent algorithms have been an active field of research since their inception in the seminal paper \cite{robbins1951stochastic}. Stochastic gradient descent (SGD) and advanced gradient descent-based optimization schemes with stochastic gradient estimates have been the subject of increased attention recently due to their relevance in neural network-based machine learning, see e.g.\ \cite{dieuleveut2017bridging,needell2014stochastic,pmlr-v89-vaswani19a,ward2019adagrad,xie2020linear, defossez2020convergence,allen2017natasha,moulines2011non, rakhlin2011making,jentzen2021strong,ghadimi2016mini, ghadimi2013stochastic,fehrman2020convergence,bottou2018optimization,bernstein2018convergence,bach2013non} and many more. A good literature review can be found in \cite{fehrman2020convergence}.

Theoretic guarantees for the convergence of SGD can be split into two categories:

\begin{itemize}
\item For convex target functions, SGD converges to the global minimum. 
\item For smooth non-convex target functions, SGD converges to a critical point, which is not a strict saddle.
\end{itemize} 

Both types of guarantee can be obtained under different conditions and either in expectation or almost surely, and both can be complemented with sharp rates. We review results of both types in Section \ref{subsection brief review}. Results may hold for the final iteration $\theta_t$ of SGD, the best parameter $\tilde \theta_t$ along the SGD trajectory up to time $t$, or a weighted average $\bar \theta_t$ of previous positions of SGD. We focus on guarantees for the final position since a list of previous values, or even a non-trivially weighted average of previous positions, is expensive to maintain in deep learning, where a model may have millions of parameters.

Recently, it has been noted in the SGD literature \cite{karimi2016linear} that convexity can be replaced by the condition that the objective function satisfies a \L{}ojasiewicz-inequality, i.e.
\begin{equation}\label{eq lojasiewicz first}
\Lambda \,f(\theta)\leq |\nabla f|^2(\theta) \qquad\forall\ \theta.
\end{equation}
This advance is particularly crucial since objective functions in deep learning typically have complicated geometries where the set of global minimizers is a submanifold of high dimension and co-dimension. Such functions are not usually convex, even in a neighbourhood of a minimizer.

The inequality \eqref{eq lojasiewicz first} holds in particular for all strongly convex functions, but may not hold for smooth convex functions, e.g.\ $f(x) = \sqrt{x^2+1}$. Like for convex functions, the only critical points of a function satisfying a \L{}ojasiewicz inequality lie in the set of global minimizers. The assumption of a global \L{}ojasiewicz inequality thus remains restrictive, and other models, e.g.\ functions satisfying local \L{}ojasiewicz inequalities at the critical level sets have been considered \cite{dereich2021convergence}. 

Classically, the only assumption on SGD noise is a uniform second moment bound. In this work, we consider more realistic noise model inspired by deep learning applications. In this setting, we can prove convergence to the global minimum for a more general class of functions which are neither required to be convex, nor to satisfy a \L{}ojasiewicz inequality. In this sense, we prove a first type guarantee under weaker second type assumptions. 

While we obtain fast (linear) convergence to the global minimum 
\[
f(\theta_t) - \inf f \leq Z \,\rho^t\qquad\text{rather than the rate}\qquad f(\theta_t) - \inf f \leq \frac{C}t,
\]
which is typical in the stochastic setting, we note that the random variable $Z$ is typically too large to yield meaningful bounds in practice, unless the target function and noise have particularly convenient properties. Nevertheless, the fast convergence allows us to circumvent a common `staying local' assumption, which is automatic for exponentially decaying sequences.

The guarantees we obtain hold almost surely (i.e.\ with probability $1$) over the choice of initial condition and stochastic gradient optimization. The importance of almost sure statements in this context has for example been emphasized in \cite{patel2020stopping} in the context of deriving stopping criteria which are `triggered' with probability $1$.


\subsection{Notation and conventions}

All random variables are defined on a probability space $(\Omega,\mathcal A, \P)$ which remains abstract and is characterized mostly as expressive enough to support a random initial condition and countably many iid copies of a random variable to select a gradient estimator. The dyadic product of two vectors $a, b$ is denoted by
\[
a\otimes b = a\cdot b^T, \qquad\text{i.e.} (a\otimes b)_{ij} = a_i b_j.
\]


\section{Energy landscapes and stochastic noise in machine learning}\label{section review}

\subsection{A brief review of stochastic gradient descent}\label{subsection brief review}

Stochastic gradient descent algorithms are a class of popular algorithms in machine learning to find minimizers of an objective function $f$. Instead of taking a small step in the direction $-\nabla f$ in every iteration, we choose the update direction randomly according to a random variable $g$ with expectation $-\nabla f$ and suitable $L^p$-bounds for some $p\geq 2$. 

More formally, we consider the following model.

\begin{enumerate}
\item $f:\R^m\to [0,\infty)$ is a $C^1$-function 
\item $\nabla f$ satisfies the one-sided Lipschitz-condition
\[
\langle \nabla f(\theta_1) - \nabla f(\theta_2), \theta_1-\theta_2\rangle \leq C_L\,|\theta_1-\theta_2|^2
\]
\item $(\Omega,\mathcal A, \P)$ is a probability space and $g:\R^m\times\Omega\to\R^m$ is a family of functions such that
\begin{enumerate}
\item ${\mathbb E}_{\xi\sim\P} g(\theta,\xi) = \nabla f(\theta)$ for all $\theta\in \R^m$ and
\item ${\mathbb E}_{\xi\sim\P} \big[ |g(\theta,\xi)- \nabla f(\theta)|^2\big] < \infty$ for all $\theta \in \R^m$.
\end{enumerate}
\end{enumerate}

The SGD algorithm associated to the family $g$ of gradient estimators is given by the time-stepping scheme
\begin{equation}
\theta_{t+1} = \theta_t - \eta_t\,g(\theta_t, \xi_t)
\end{equation}
where 
\begin{enumerate}
\item the initial condition $\theta_0$ is a random variable in $\R^m$,
\item $\eta_t>0$ is the {\em learning rate} (or time step size) in the $t$-th time step, and
\item $\{\xi_t\}_{t\geq 0}$ is a family of random variables in $\Omega$ with law $\P$, which are iid and independent of $\theta_0$.
\end{enumerate}

In theoretical works, we typically consider decaying learning rates. This is rooted in results such as this, originating from \cite{robbins1951stochastic}.

\begin{theorem}\label{theorem sgd 1}
Assume that $\nabla f$ is Lipschitz-continuous with constant $C_L>0$ and that 
\begin{itemize}
\item $f$ is convex or
\item $f$ satisfies the {\em \L{}ojasiewicz inequality} $\Lambda (f-\inf f) \leq |\nabla f|^2$ for some $\Lambda>0$.
\end{itemize}
If
\begin{equation}\label{eq classical noise}
{\mathbb E}_\xi\big[|g(\theta,\xi)-\nabla f(\theta)|^2\big]\leq \sigma^2 \qquad\forall\ \theta\in \R^m
\end{equation}
and the learning rates $\eta_t$ satisfy the {\em Robbins-Monro} conditions
\[
\sum_{t=0}^\infty \eta_t = \infty, \qquad \sum_{n=0}^\infty \eta_t^2 <\infty,
\]
then $\lim_{t\to\infty}{\mathbb E}\big[f(\theta_t)\big] = \inf f$. If $f$ satisfies the {\em \L{}ojasiewicz inequality} and $\eta_t = \frac2{\Lambda(t+1)}$, then
\[
{\mathbb E}\big[f(\theta_t) - \inf f\big] \leq \frac{2C_L\sigma^2}{\Lambda^2}\,\frac{\log(t+1)}t\,{\mathbb E}\big[ f(\theta_0)- \inf f\big]
\]
\end{theorem}

A proof for the \L{}ojasiewicz case (which in particular contains the uniformly convex case) can be found in \cite[Theorem 4]{karimi2016linear}, albeit under the assumption that $|\nabla f|$ is uniformly bounded, which contradicts the assumption that $f$ satisfies a \L{}ojasiewicz inequality (unless $f$ is constant). This can be weakened to the assumption that the noise has bounded variance \cite{bottou2018optimization}

The first summation condition is equivalent to stating that we are solving a gradient-flow type equation on the entire real line. Violating it would introduce a finite time horizon, which would prevent convergence to the minimizer as $t\to \infty$ even in the non-stochastic setting and even for smooth and strongly convex objective functions. The second condition guarantees that the impact of gradient noise diminishes sufficiently as $t\to \infty$ such that the iterates $\{\theta_t\}_{t\geq 0}$ are not driven away from the global minimum in the long term by random oscillations. Unlike the first condition, it can be weakened \cite[Chapter 5]{kushner2003stochastic}. It has been suggested that the learning rate decay $\eta_ t= \bar \eta/t$ is optimal \cite[Section 4.1.2]{li2017stochastic}. 

If the objective function is non-convex and does not satisfy a \L{}ojasiewicz inequality, convergence to a critical point which is not a strict saddle can be guaranteed under suitable conditions on $f$ and $g$. We only give an imprecise statement.

\begin{theorem}\cite{mertikopoulos2020almost}\label{theorem sgd 2}
Under suitable conditions on the objective function $f$ and a condition of the type ${\mathbb E}\big[|g-\nabla f|^2\big] \leq \sigma^2$, the following holds: If $\eta_t = \frac{\eta_0}{(t+t_0)^p}$ for some $p\in (1/2,1]$, then
\begin{enumerate}
\item $f(\theta_t)$ converges to a random variable $Z$ almost surely and $Z$ lies in the set of critical values of $f$ almost surely.
\item $\sup_{t}|\theta_t|<\infty$ almost surely.
\item for every trajectory of SGD, there exists a connected component $\mathcal X$ of the set of critical points of $f$ such that $\lim_{t\to\infty} {\rm dist}(\theta_t, \mathcal X)=0$.
\item If $S$ is a connected component of the set of critical points of $f$ such that $D^2f(\theta)$ has a negative eigenvalue for all $\theta\in S$ (a ridge manifold), then $\P\big(\lim_{t\to\infty}{\rm dist}(\theta_t,S)=0\big) =1$. 
\end{enumerate}
\end{theorem}

In particular, an isolated strict saddle point is a zero-dimensional ridge manifold. Stronger statements, including a rate of convergence, are available at isolated local minima. The conditions on $f$ posed in \cite{mertikopoulos2020almost} are neither implied by our assumptions, nor are they more general. While sublevel sets of $f$ have to be compact in \cite{mertikopoulos2020almost} but not for us, we impose stronger conditions on the gradient away from the set of minimizers.


In practice, we typically choose learning rates according to a schedule of the form $\eta_t \equiv \eta^{(1)}$ for $0\leq t<T_1$, $\eta_t \equiv \eta^{(2)}$ for $T_1\leq t< T_2$, \dots with a discrete set of switching times $0< T_1<T_2 <\dots$ and learning rates $\eta^{(1)}> \eta^{(2)}>\dots$. Generally, the learning rates are chosen as large as possible without inducing numerical instability, and it is realistic to consider the setting where the learning rate is reduced only a finite number of times.

We consider the setting where even in the long term limit, the learning rate remains strictly positive. Under the conditions of Theorem \ref{theorem sgd 1}, we find that the energy quickly decays below a threshold depending on the learning rate.

\begin{theorem}\cite[Theorem 4]{karimi2016linear}\label{theorem sgd 3}
Assume that $f$ satisfies the {\em \L{}ojasiewicz inequality} $\Lambda (f-\inf f) \leq |\nabla f|^2$ and that $\nabla f$ is Lipschitz-continuous with Lipschitz-constant $C_L$. Assume further that the stochastic noise satisfies \eqref{eq classical noise}. If $\eta_t\equiv \eta < \frac{1}{C_L}$, then
\[
{\mathbb E}\big[f(\theta_t) - \inf f\big] \leq\left(1-\Lambda\eta\right)^t{\mathbb E}\big[f(\theta_0)-\inf f\big] + \frac{C_L\sigma^2}{2\Lambda}\,\eta\qquad\forall\ t\in\N.
\]
\end{theorem}

Theorems \ref{theorem sgd 1}, \ref{theorem sgd 2} and \ref{theorem sgd 3} made very weak assumptions on the nature of the stochastic noise in the estimators $g$.  Under different conditions, we can obtain better results. In particular, the type of noise encountered in the gradient estimators in machine learning is fairly special.


\subsection{On energy landscapes in machine learning}
Consider a parameterized function class
\[
h:\R^m \times \R^d \to \R^k
\]
where $\R^m$ is the space of parameters, $\R^d$ is the space in which the data is given, and $\R^k$ is a target space. In supervised learning problems, we seek to minimize functions of the form 
\[
L(\theta) = \frac1n \sum_{i=1}^n \ell\big( h(\theta,x_i), y_i\big)
\]
where
\begin{enumerate}
\item $\{(x_i,y_i)\}_{i=1}^n$ is our training set of data/output or data/label pairs in $\R^d\times \R^k$,
\item $\theta$ denotes the parameters of our function model, and
\item $\ell :\R^k\times \R^k\to [0,\infty)$ is a positive function.
\end{enumerate}
We use $\ell$ to establish a concept of similarity on $\R^k$ and optimize $\theta$ in order to make $h(\theta,x_i)$ ``similar'' to $y_i$ with respect to $\ell$, i.e.\ to make $\ell(h(\theta,x_i), y_i)$ small.

\begin{remark}
Depending on the context, both $L$ and $\ell$ are referred to as the loss function. At times, $L$ is referred to as `risk' and denoted by the symbol $\mathcal{R}$ instead.
\end{remark}

\begin{example}\label{example loss functions}
The prototypical example of a loss function in our context is MSE (mean squared error)/$\ell^2$-loss
\[\label{eq mse loss}
\ell(h,y) = \frac12\,\|h-y\|^2_{\R^k}.
\]
Another popular loss function in the setting of classification problems is softmax cross entropy loss
\[\showlabel\label{eq cross entropy}
\ell(h, y) = -\log\left(\frac{\exp(h\cdot y)}{\sum_{i=1}^k \exp(h\cdot e_i)}\right), \qquad y\in \{e_1,\dots, e_k\}.
\]
The energy landscapes in both types of learning problems are quite different since cross entropy loss is never zero (see \ref{example cross-entropy} for more details) and our results do not apply in the second setting.
\end{example}

In this article, we focus on $\ell^2$-type losses. Note that
\[
L(\theta) = 0 \qquad\LRa\qquad \frac1n\sum_{i=1}^n\big|h(\theta,x_i) - y_i\big|^2 = 0 \qquad\LRa \qquad h(\theta,x_i) = y_i \quad\forall\ 1\leq i\leq n.
\]
We give a modified version of a theorem of Cooper \cite[Theorem 2.1]{cooper2018loss}.

\begin{theorem}\cite{cooper2018loss}\label{theorem cooper}
Assume that 
\begin{enumerate}
\item the function model $h$ is overparametrized, i.e.\ $m>nk$,
\item the function model $h$ is so expressive that for any collection of outputs $y_1, \dots, y_n$ there exists $\theta\in \R^m$ such that 
\[
h(\theta, x_i) = y_i \qquad\forall\ 1\leq i \leq n,
\]
\item $h$ is $C^{m-nk+1}$-smooth in $\theta$.
\end{enumerate}
Then for Lebesgue-almost any choice of $(y_1,\dots, y_n)\in \R^{nk}$, the set
\[
N = \big\{\theta\in \R^m : L(\theta) = 0\big\}
\]
is a closed $m-nk$-dimensional $C^1$-submanifold of $\R^m$. If $h$ is Lipschitz-continuous in the first argument for every fixed $x$ and sufficiently overparameterized that it can fit arbitrary values at $n+1$ points, then $N$ is non-compact.
\end{theorem}

The conditions of this theorem are satisfied by certain overparametrized neural networks with smooth activation function \cite[Lemma 3.3]{cooper2018loss}, but also many other suitably expressive function classes. The condition $m\geq nk$ is implicit in the assumptions on expressivity and smoothness of $h$.

\begin{proof}
We can write $N = \Psi^{-1}(y)$ where
\[
\Psi:\R^m \to \R^{nk}, \qquad \Psi(\theta) = \begin{pmatrix} h(\theta, x_1)\\ \vdots\\ h(\theta,x_n)\end{pmatrix}, \qquad y = \begin{pmatrix} y_1\\ \vdots \\ y_n\end{pmatrix}.
\]
By assumption, $N$ is non-empty and if $y$ is a regular value of $\Psi$, then $N$ is a $C^1$-manifold of dimension $m-nk$. Since $\Psi$ is as smooth as $h$, we can conclude by Sard's theorem \cite{sard1942measure} that Lebesgue-almost every $y$ is a regular value of $\Psi$. As the pre-image of a single point under a continuous map, $N$ is closed.

If $h$ is sufficiently overparametrized that it can fit values not only at $n$ but at $n+1$ points, then for any $x_{n+1}\in\R^d$ and $y_{n+1}\in \R^k$ there exists $\theta\in \R^m$ such that $h(\theta, x_i) = y_{i}$ for $1\leq i\leq n+1$. In particular, for any choice $y_{n+1}\in\R^k$ we have $\theta \in N$. 

Let $y_{n+1}, y_{n+1}'\in\R^k$ and $\theta,\theta'$ associated indices in $N$. Since 
\[
\big|y_{n+1} - y_{n+1}'\big| = \big|h(\theta, x_{n+1}) - h(\theta', x_{n+1})\big| \leq C_h\,|\theta-\theta'|,
\]
we see $N$ cannot be compact since achieving very different outputs $y_{n+1}, y_{n+1}'$ requires very different parameters $\theta, \theta'$.
\end{proof}

We observe the following: If $L$ is convex, then the set of minimizers is convex. An $m-nk$-dimensional closed submanifold of $\R^m$ is a convex set if and only if it is an $m-nk$-dimensional affine subspace of $\R^m$. If the map $\theta\mapsto h(\theta,x)$ is generically non-linear, there is no reason to expect $N$ to be an affine space. Thus, we typically expect that $L$ is non-convex, even close to its set of minimizers. A rigorous statement on the non-convexity of objective functions in deep learning is given in Appendix \ref{appendix non-convexity}.

Thus, any toy model for the energy landscape $L:\R^m\to [0,\infty)$ of deep learning in overparametrized regression problems should have the following property: {\em There exists a non-compact closed $C^1$-manifold $N\subseteq \R^m$ such that $L(\theta)=0$ if and only if $\theta\in N$.} We can think of both the dimension and co-dimension of $N$ as being large.


\begin{remark}
While functions with these properties in general cannot be convex even in a neighbourhood of their set of minimizers, they may satisfy a \L{}ojasiewicz inequality of the form 
\[
\|\nabla f\|^2 \geq c\,f.
\]
One such function is $f(x,y) = \frac12\big(y-h(x)\big)^2$ for any $h\in C^1(\R)$ since
\[
\|\nabla f\|^2 \geq |\partial_yf|^2 = \big(y- h(x)\big)^2 = 2f.
\]
The assumption that a \L{}ojasiewicz inequality holds is standard in non-convex optimization, but may not be realistic in machine learning, where complex energy landscapes with many local minima, maxima, ridges and saddle points are observed. For a fascinating demonstration of how diverse these energy landscapes can be, see \cite{skorokhodov2019loss}. 
\end{remark}

However, we note that there are no critical points of high risk in square loss regression problems under very general conditions in the finite data or infinite data case.

\begin{lemma}\label{lemma no high energy critical points}
Let $\mu$ be a probability distribution on $\R^d\times \R^k$ with finite second moments (the data distribution). Assume that $h(\theta,\cdot)$ is a multi-layer perceptron with weights $\theta$ which maps $\R^d$ to $\R^k$. Define the risk functional
\[
\mathcal{R}(\theta) = \frac12 \int_{\R^d\times \R^k} \big|h(\theta,x)-y\big|^2\d\mu_{(x,y)}.
\]
Then there exists a constant $C>0$ such that
\[
|\theta|\cdot |\nabla \mathcal{R}(\theta)| \geq \mathcal{R}(\theta) - C.
\]
In particular, there exists $S>0$ such that 
\[
\mathcal{R}(\theta)>S \qquad \Ra\qquad \nabla \mathcal{R}(\theta)\neq 0.
\]
\end{lemma}

The function $\mathcal{R}$ is an empirical risk functional if $\mu$ is a finite sum of Dirac deltas and a population risk functional otherwise.

\begin{proof}
Let $h^*(x) = {\mathbb E}\big[y|x\big]$ and $\overline\mu$ the distribution of $x$ in $\R^d$ if $(x,y)$ is distributed according to $\mu$. Then
\begin{align*}
\mathcal{R}(\theta) &= \frac12 \int_{\R^d\times \R^k} \big|h(\theta,x)-h^*(x)\big|^2\d\mu_{(x,y)} + \frac12 \int_{\R^d\times \R^k} \big|h^*(x)-y\big|^2\d\mu_{(x,y)}\\
	&= \frac12 \int_{\R^d\times \R^k} \big|h(\theta,x)-h^*(x)\big|^2\d\overline\mu_{x} + C_\mu.
\end{align*}
For a neural network, we can decompose $\theta = (W, \hat \theta)$ and $h(\theta,x) = W\,\sigma\big(\hat h(\hat\theta,x)\big)$ where $\hat h:\R^d\to \R^l$ is a neural network with one layer less than $h$ and $W:\R^l\to \R^k$ is linear. If $\mathcal{R}(\theta)$ is larger than
\[
\int_{\R^d\times\R^k}|y|^2\,\d\mu_{(x,y)},
\]
then $h(\theta,x) \not\equiv 0$, so in particular $W\neq 0$. We can therefore compute
\begin{align*}
|\nabla_\theta \mathcal{R}| (\theta)&\geq \frac{|W\cdot \nabla_W \mathcal{R}|}{|W|}\\
	&= \frac1{|W|} \left|W\cdot\int_{\R^d} \big(h(\theta,x) - y\big)\cdot \nabla_Wh(\theta,x)\,\d\mu_{(x,y)}\right|^2\\
	&=\frac1{|W|} \left|\int_{\R^d} \big(h(\theta,x) - y\big)\left( W\nabla_Wh(\theta,x)\right)\,\d\mu_{(x,y)}\right|^2\\
	&= \frac1{|W|} \left|\int_{\R^d} \big(h(\theta,x) - h^*(x)\big) \cdot h(\theta,x)\,\d\overline\mu_{x}\right|
\end{align*}
since the representation of $h$ is linear in $W$, so $W\cdot \nabla_Wh(\theta,x) = h(\theta,x)$. Consequently
\begin{align*}
|W|\,|\nabla_\theta \mathcal{R}|(\theta)&\geq \int_{\R^d} \big|h(\theta,x) - h^*(x)\big|^2 - h^*(x)\cdot \big(h(\theta,x) - h^*(x)\big) \,\d\overline\mu_{x}\\
	&\geq \|h_\theta-h^*\|_{L^2(\P)}^2 - \|h_\theta-h^*\|_{L^2(\P)}\|h^*\|_{L^2(\mu)}\\
	&= 2\big(\mathcal{R}(\theta) - C_\mu\big) - \sqrt2\sqrt{\mathcal{R}(\theta) - C_\mu}\,\|h^*\|_{L^2(\mu)}.
\end{align*}
The claim follows since $2 \mathcal{R}(\theta) - \|h^*\|_{L^2(\mu)}\sqrt{2\,\mathcal{R}(\theta)} \geq \mathcal{R}(\theta) - \|h^*\|_{L^2(\mu)}^2$.
\end{proof}

\subsection{\L{}ojasiewicz landscapes}

We briefly discuss local \L{}ojasiewicz conditions in machine learning and beyond. For sufficiently `nice' objective functions, these can easily be seen to hold.

\begin{example}
Assume that $f:\R^m\to[0,\infty)$ is $C^2$-smooth and $N:= f^{-1}(0)$ is a $C^1$-manifold. Assume that
\begin{enumerate}
\item $D^2f$ is globally Lipschitz-continuous on the set $U = \{\theta : f(\theta) \leq 1\}$ and
\item there exists $0 < \lambda \leq \Lambda $ such that $\lambda |v|^2 \leq v^TD^2(\theta)v \leq \Lambda\,|v|^2$ for all $\theta \in N$ and $v\in (T_\theta N)^\bot$.
\end{enumerate}
Then there exists $\varepsilon>0$ such that $f$ satisfies a \L{}ojasiewicz inequality on the set $U_\varepsilon = \{\theta : f(\theta)<\varepsilon\}$ since 
\begin{align*}
f(\theta + tv) &= \frac{t^2}2\,v^T D^2f(\theta) v + O(t^3)\\
\nabla f(\theta+tv) &= t\,D^2f(\theta)\,v + O(t^2)
\end{align*}
so if $v\bot T_\theta N$ and $|\theta|=1$ we have
\begin{align*}
f(\theta+tv) &= \frac{t^2}2\,v^T D^2f(\theta) v + O(t^3)\\
	& \leq \frac{\Lambda}2\,t^2 + O(t^3)\\
	& \leq \frac\Lambda{2\lambda^2} \left(\lambda^2\,t^2 + O(t^3)\right)\\
	&\leq \frac\Lambda{2\lambda^2} \left(\left|D^2f(\theta)\,v\right|^2\,t^2 + O(t^3)\right)\\
	&= \frac\Lambda{2\lambda^2}|\nabla f(\theta)|^2 + O(t^3).
\end{align*}
Since $f(\theta + tv) \geq \frac{\lambda}2t^2$ and due to the uniform Lipschitz bound, the smallness of the correction term is uniform over the set $\{f<\varepsilon\}$.
\end{example}

\begin{example}[Quadratic regression]
For quadratic regression problems  
\[
L(\theta) = \frac1{2n}\sum_{i=1}^n \big(h(\theta,x_i)-y_i\big)^2
\]
we have
\begin{align*}
\nabla L(\theta) &= \frac1{n}\sum_{i=1}^n \big(h(\theta,x_i)-y_i\big)\,\nabla_\theta h(\theta,x_i)\\
D^2L(\theta) &= \frac1{n}\sum_{i=1}^n \nabla_\theta h(\theta,x_i) \otimes \nabla_\theta h(\theta,x_i) + \big(h(\theta,x_i)-y_i\big)\,D^2h(\theta,x_i).
\end{align*}
In particular if $L(\theta) =0$, the Hessian terms of $h$ drop out and
\[
D^2L(\theta) = \frac1{n}\sum_{i=1}^n \nabla_\theta h(\theta,x_i) \otimes \nabla_\theta h(\theta,x_i)
\]
The upper bound $\|D^2L\|\leq C$ is therefore satisfied on $N$ if the map $\theta\mapsto h(\theta,x_i)$ is Lipschitz-continuous. The lower bound corresponds to the assumption that the $n$ vectors $\nabla_\theta h(\theta,x_i)$ are bounded away from zero and bounded away from becoming linearly dependent. If this is the case, the lower bound
\[
\lambda|v|^2 \leq v^T D^2L(\theta)v
\]
holds since $v\in (T_\theta N)^\bot$ lies in the $n$-dimensional space spanned by $\{\nabla_\theta h(\theta,x_i) : 1\leq i\leq n\}$. These assumptions correspond to a function model in which we can always change the parameters by a small amount and change the model output by a positive amount, and in which the output at different data points $x_i, x_j$ is principally governed by different parameters. The Lipschitz-condition on $D^2L$ corresponds to the assumption that $h, \nabla_\theta h, D^2_\theta h$ are Lipschitz-continuous and bounded. 
\end{example}

\begin{example}[Cross-entropy classification]\label{example cross-entropy}
For classification problems, the cross-entropy loss function
\[
L(\theta) = -{\mathbb E}_{(x,i)\sim\mu} \left[ \log\left(\frac{\exp\big(h(x)\cdot e_i\big)}{\sum_{j=1}^k \exp\big(h(x)\cdot e_j\big)}\right)\right]
\]
never vanishes, so the energy landscape is fundamentally different from that of quadratic regression problems. We show that generally, a \L{}ojasiewicz condition of the type $\Lambda f \leq |\nabla f|^2$ cannot hold even for small values of the objective function.

The loss function
\[
\ell(h, i) = -\log\left(\frac{\exp (h\cdot e_i)}{\sum_{j=1}^k \exp(h\cdot e_j)}\right) = \log\left(\sum_{j=1}^k \exp(h\cdot e_j)\right) - h\cdot e_i
\]
satisfies
\begin{align*}
\nabla_h\ell(h,i) &= \sum_{l=1}^k \frac{\exp(h\cdot e_l)}{\sum_{j=1}^k\exp(h\cdot e_j)} \,e_l - e_i
\\
\big|\nabla_h\ell(h,i)\big|^2 &= \left|\frac{\exp(h\cdot e_i)}{\sum_{j=1}^k\exp(h\cdot e_j)}-1\right|^2 + \sum_{l\neq i} \left|\frac{\exp(h\cdot e_l)}{\sum_{j=1}^k\exp(h\cdot e_j)}\right|^2.
\end{align*}
With the counting density $p_l = \frac{\exp(h\cdot e_l)}{\sum_j\exp(h\cdot e_j)}$, we find that
\[
\ell = -\log(p_i) \geq 1-p_i, \qquad |\nabla \ell|^2 = (1-p_i)^2 + \sum_{l\neq i}p_l^2 \leq 2\,(1-p_i)^2,
\]
so 
\[
\frac12\big|\nabla_1\ell\big(h(\theta,x), i\big)\big|^2\leq (1-p_i)^2 \leq \min\big\{1,- \log(p_i)\big\}^2 \leq \min\big\{1,\ell\big(h(\theta,x), i\big)\big\}^2.
\]

Assume for the sake of contradiction that $\lambda\,L(\theta) \leq |\nabla L|^2(\theta)$ on the set $\{L<\varepsilon\}$. Then the solution $\theta$ of the gradient flow equation $\dot\theta = -\nabla L(\theta)$ satisfies
\[
\frac{d}{dt} L(\theta(t)) = - |\nabla L|^2(\theta(t)) \leq -\lambda\,L(\theta(t))\qquad \Ra \qquad L(\theta(t)) \leq e^{-\lambda t}\,L(\theta(0)).
\]
In particular 
\begin{align*}
\big|\theta(t)-\theta(0)\big| &\leq \int_0^t \big|\nabla L(\theta(s))\big|\,\,\mathrm{d}s
	\leq 2\,\int_0^t L(\theta(s))\,\,\mathrm{d}s
	\leq 2\,L(\theta(0))\int_0^t e^{-\lambda s}\,\,\mathrm{d}s \leq \frac{2\,L(\theta(0))}\lambda.
\end{align*}
if $L(\theta(0))<\varepsilon$. In particular, $\theta(t)$ is contained in a compact subset of $\R^m$ and $L(\theta(t))\not \to 0$ as $t\to\infty$, leading to a contradiction.
\end{example}



\subsection{Random selection SGD}

Consider a more general objective function $f:\R^m\to [0,\infty)$ of the form
\[
f(\theta) = {\mathbb E}_{\xi\sim\P} \phi(\theta,\xi)
\]
where $(\Omega,\mathcal A, \P)$ is a probability space and $\phi:\R^m\times \Omega\to [0,\infty)$ is a non-negative function such that
\begin{enumerate}[label=(G\arabic*), ref=(G\arabic*)]
\item for any fixed $\theta$, the function $\xi\mapsto \phi(\theta,\xi)$ is $\mathcal A$-measurable,
\item for any fixed $\xi$, the function $\theta\mapsto \phi(\theta,\xi)$ is continuously differentiable, and
\item for any compact set $K\subseteq\R^m$, there exists $\psi_K \in L^1(\P)$ such that 
\[
\phi(\theta,\xi) + \big|\nabla_\theta\phi(\theta,\xi)\big| \leq \psi_K(\xi)\qquad \forall\ \theta \in K
\]
$\P$-almost everywhere.
\end{enumerate}
The assumptions guarantee that expectation and parameter gradient commute \cite[Section 8.4]{konigsberger2013analysis}. A particular gradient estimator is
\[
g(\theta, \xi) = (\nabla_\theta\phi)(\theta,\xi)
\]
since
\[
{\mathbb E}_\xi g(\theta,\xi) = {\mathbb E}_\xi \big[ (\nabla_\theta\phi)(\theta,\xi)\big] = \nabla_\theta \big[{\mathbb E}_\xi \phi(\theta,\xi)\big] = \nabla f(\theta).
\]
Denote by $\Sigma$ the covariance matrix of the estimator $g$:
\[
\Sigma_{ij} (\theta) = {\mathbb E}_\xi \big[ \big(g_i(\theta,\xi) - \partial_i f(\theta)\big) \big(g_j(\theta,\xi)- \partial_jf(\theta)\big)\big],
\]
which we assume is well-defined:

\begin{enumerate}[label=(G\arabic*), ref=(G\arabic*)]\setcounter{enumi}{3}
\item for all $\theta\in \R^m$ we have $\nabla_\theta\phi(\theta,\cdot) \in L^2(\P)$.
\end{enumerate}

This model encompasses machine learning problems as discussed above with
\[
f(\theta) = \int_{\R^d\times \R^k} \ell\big(h(\theta,x),y\big)\,\d\mu_{(x,y)}, \qquad \xi = (x,y), \qquad g(\theta,\xi) = \partial_1\ell\big(h_\theta(x), y\big)\,\nabla_\theta h(\theta,x),
\]
if the loss function $\ell$ and the data distribution $\mu$ are compatible via growth conditions and moment bounds.



\subsection{SGD noise in machine learning}

We make an obvious observation.

\begin{lemma}\label{lemma no noise at minimum}
Assume there exists an $m-n$-dimensional manifold $N\subseteq \R^m$ such that $\phi(\theta,\xi) = 0$ for $\P$-almost all $\xi$. Then $\Sigma = 0$ everywhere on $N$ for the random selection gradient estimator.
\end{lemma}

\begin{proof}
Since $\phi(\theta,\xi) = 0$ an $\phi\geq 0$, we find that $\phi(\cdot,\xi)$ is minimal at $\theta$, so $\nabla_\theta\phi(\theta,\xi) =0$ for all $\xi$. Since there is no oscillation in the gradient estimator, the variance vanishes.
\end{proof}

\begin{remark}
A popular toy model for SGD is the family of gradient estimators
\[
g(x,\xi) = \nabla f(x) + \sigma \xi
\]
where $\sigma>0$ and $\xi$ is a standard Gaussian random variable. Unlike machine learning SGD, the estimators correspond to calculating exact gradients and deliberately perturbing them stochastically. Clearly, this toy model fails to capture key features of random selection SGD at the minimizing manifold.
\end{remark}

We prove a more quantitative version of Lemma \ref{lemma no noise at minimum}.

\begin{lemma}\label{lemma noise bounds}
Let $\mu$ be a data distribution and $h$ a parametrized function model such that $|\nabla_\theta h(\theta,x)| \leq C$ for $\mu$-almost every $x$. For a quadratic regression problem
\begin{align*}
L(\theta) &= \frac12 \int_{\R^d\times\R^k} \big|h(\theta,x) -y\big|^2\,\d\mu_{(x,y)} 
\end{align*}
the noise satisfies
\[
{\mathbb E}_{\xi\sim\P} \big[|g(\theta,\xi) - \nabla L(\theta)|^2\big] \leq {\mathbb E}_{\xi\sim\P} \big|g(\theta,\xi)\big|^2 \leq \|\nabla_\theta h \|_{L^\infty}^2\,L(\theta).
\]
For a cross-entropy classification problem
\begin{align*}
L(\theta) &= - \int_{\R^d\times\{1,\dots,k\}} \log\left(\frac{\exp\big(h(\theta,x)\cdot e_i\big)}{\sum_{j=1}^k \exp(h\big(\theta,x)\cdot e_j\big)}\right)\,\d\mu_{(x,i)}
\end{align*}
the noise satisfies
\[
{\mathbb E}_{\xi\sim\P} \big[|g(\theta,\xi) - \nabla L(\theta)|^2\big] \leq {\mathbb E}_{\xi\sim\P} \big|g(\theta,\xi)\big|^2 \leq 2\,\|\nabla_\theta h \|_{L^\infty}^2\,\min\big\{1,L(\theta)\big\}.
\]
\end{lemma}

\begin{proof}
{\bf Quadratic regression.}
\begin{align*}
\nabla L(\theta) &= \int_{\R^d\times\R^k} \big(h(\theta,x) - y\big)\cdot \nabla_\theta h(\theta,x)\,\d\mu_{(x,y)}\\
g(\theta,\xi) &= \big(h(\theta,x) - y\big)\cdot \nabla_\theta h(\theta,x)
\end{align*}
where $\xi = (x,y)$. Under the assumption that $\nabla_\theta h$ is uniformly bounded on $\R^m\times\R^d$, we observe that
\begin{align*}
{\mathbb E}_{\xi\sim\P} \big|g(\theta,\xi)\big|^2 &= \int_{\R^d\times\R^k}\mathrm{tr} \left\{(\nabla_\theta h)^T(\theta,x) \cdot \big(h(\theta,x)-y\big)^T \big(h(\theta,x) - y\big)\cdot \nabla_\theta h(\theta,x)\right\}\,\d\mu_{(x,y)}\\
	&= \int_{\R^d\times \R^k}\big|h(\theta,x)-y\big|^2 \,\mathrm{tr} \big\{(\nabla_\theta h)^T\nabla_\theta h\big\}(\theta,x)\,\d\mu_{(x,y)}\\
	&\leq \|\nabla_\theta h\|_{L^\infty}^2\int_{\R^d\times\R^k}\big|h(\theta,x)-y\big|^2\,\d\mu_{(x,y)}\\
	&= \|\nabla_\theta h \|_{L^\infty}^2\,L(\theta).
\end{align*}
As a Corollary, also 
\[
{\mathbb E}_{\xi\sim\mu} \big[|g(\theta,\xi) - \nabla L(\theta)|^2\big] \leq {\mathbb E}_{\xi\sim\mu} \big|g(\theta,\xi)\big|^2 \leq \|\nabla_\theta h \|_{L^\infty}^2\,L(\theta)
\]
since ${\mathbb E}_{\xi\sim\mu} g = \nabla L$.

{\bf Classification.} As in Example \ref{example cross-entropy}, we find that 
\[
\big|\nabla_1\ell\big(h(\theta,x), i\big)\big|^2 \leq 2\,\min\big\{1,\ell^2\big(h(\theta,x), i\big)\big\} 
\]
We set $\xi = (x,i)$ and estimate
\begin{align*}
g(\theta,\xi) &= (\nabla_1\ell)\big(h(\theta,x), y\big)\cdot \nabla_\theta h(\theta,x)
\end{align*}
by
\begin{align*}
{\mathbb E}_{\xi\sim\mu} \big[|g(\theta,x)|^2\big] &\leq \|\nabla_\theta h\|_{L^\infty}^2 {\mathbb E}_{\xi\sim\mu}\big[\big|\nabla_1 \ell\big(h(\theta,x), y\big)\big|^2\big]\\
	&\leq 2\, \|\nabla_\theta h\|_{L^\infty}^2 \,{\mathbb E}_{\xi\sim\mu}\big[\min\{1,\ell^2\big(h(\theta,x), y\big)\big\}\big]\\
	&\leq 2\, \|\nabla_\theta h\|_{L^\infty}^2 \,{\mathbb E}_{\xi\sim\mu}\big[\min\{1,\ell\big(h(\theta,x), y\big)\big\}\big]\\
	&\leq 2\, \|\nabla_\theta h\|_{L^\infty}^2 \,\min\{{\mathbb E}_{\xi\sim\mu}\big[\ell\big(h(\theta,x), y\big)\big], 1\big\}\\
	&= 2\, \|\nabla_\theta h\|_{L^\infty}^2 \,\min\{L(\theta), 1\}.
\end{align*}
\end{proof}

\begin{remark}\label{remark gradients linear}
Neural networks with $L$ layers can be decomposed as 
\[
h(\theta,x) = W\,\sigma\big(\hat h(\hat\theta,x)\big), \qquad \theta = (W, \hat \theta)
\]
where $\hat h(\hat \theta,\cdot) :\R^d\to \R^{M}$ is a neural network with $L-1$ layers and $\sigma$ is a nonlinear map between vector spaces. In particular
\[
\nabla_{\hat \theta} h(\theta,x) = W\,\sigma'\big(\hat h(\hat\theta,x)\big)\,\nabla_{\hat \theta}\hat h(\hat\theta,x),
\] 
i.e.\ also the gradient of $h$ with respect to deep layer weights is linear in the final linear weights. The derivative $\sigma'$ has to be interpreted as a diagonal matrix. By the chain rule, the linearity extends to the gradient of the loss function. The assumption that $|\nabla_\theta h| \leq C$ independently of $\theta$ and $x$ is therefore unrealistic in deep learning, but a weaker assumption like
\[
|\nabla_\theta h|(\theta,x) \leq C\sqrt{1+|\theta|^2}, \qquad {\mathbb E}\big[|g(\theta,\xi)|^2\big]\leq C\,f(\theta)\,(1+|\theta|^2)
\]
holds for two-layer neural networks with ReLU activation and deep networks (ResNets, multi-layer perceptra, ...) if the activation function $\sigma$ and its first derivative $\sigma'$ are bounded. 
\end{remark}

All statements above apply to both the overparametrized and underparametrized setting. A noise intensity which may scale with the objective function is a key feature of machine learning applications in general. The next result is specific to the overparametrized regime, where we show that the stochastic noise has low rank.

\begin{lemma}\label{lemma low rank}
Under the same conditions as Theorem \ref{theorem cooper}, we find that $\mathrm{rk}(\Sigma(\theta))\leq n$ for all $\theta\in\R^m$, independently of $k$.
\end{lemma}

\begin{proof}
If we set $L_i(\theta) = \big|h(\theta,x_i)-y_i\big|^2$, then 
\begin{align*}
\Sigma(\theta) &= \frac1n \sum_{i=1}^n \big(\nabla L_i - \nabla L\big) \otimes \big(\nabla L_i-\nabla L\big)(\theta)
\end{align*}
is a sum of $n$ rank $1$ matrices.
\end{proof}


\section{Stochastic gradient descent with ML noise in discrete time}\label{section discrete}

\subsection{Functions satisfying a \L{}ojasiewicz inequality}

It is easy to prove that if the noise in SGD is proportional to an objective function $f$ which satisfies a \L{}ojasiewicz condition, SGD reduces $f$ with small, but fixed positive step size $\eta>0$. The SGD scheme converges linearly, much like non-stochastic gradient descent. This is not a realistic model for machine learning, as \L{}ojasiewicz inequalities rule out the presence of all critical points which are not the global minimum, but the same tools can be used in more complex topics below.

\begin{theorem}\label{theorem linear convergence}\label{theorem lojasiewicz}
Assume the following.
\begin{enumerate}
\item $f:\R^m\to [0,\infty)$ satisfies the \L{}ojasiewicz inequality
\[
\Lambda\,f(\theta) \leq |\nabla f|^2(\theta),\qquad \Lambda>0.
\]
\item $f$ is $C^1$-smooth and $\nabla f$ satisfies the one-sided Lipschitz-condition
\[
\big(\nabla f(\theta) - \nabla f(\theta')\big) \cdot(\theta-\theta') \leq C_L\,|\theta-\theta'|^2 \qquad \forall\ \theta,\theta'\in \R^m.
\]
\item The family of gradient estimators $g:\R^m\times \Omega\to \R^m$ satisfies the following properties:
\begin{enumerate}
\item ${\mathbb E}_{\xi\sim\P} g(\theta,\xi) = \nabla f(\theta)$ for all $\theta\in \R^m$.
\item ${\mathbb E}_{\xi\sim\P}\big[|g(\theta,\xi) - \nabla f(\theta)|^2\big] \leq \sigma f(\theta)$.
\end{enumerate}
\item The initial condition $\theta_0$ is a random variable which satisfies the bound ${\mathbb E} \big[f(\theta_0)\big]<\infty$.
\item The random gradient selectors $\{\xi_t\}$ are iid with law $\P$ and independent of $\theta_0$.
\end{enumerate}
If $\theta_t$ is generated by the SGD iteration law $\theta_{t+1} = \theta_t - \eta\,g(\theta_t,\xi_t)$ and $0 < \eta < \frac{\Lambda}{\Lambda+\sigma}\,\frac2{C_L}$, then
\[
{\mathbb E}\big[f(\theta_t)\big] \leq \rho_\eta^t \,{\mathbb E}\big[f(\theta_0)\big], \qquad \text{where}\quad \rho_\eta = 1- \Lambda\,\eta + \eta^2 \,\frac{C_L(1+\sigma)}{2\Lambda} <1.
\]
Furthermore $\beta^tf(\theta_t)\to 0$ almost surely for every $\beta\in [1, \rho_\eta^{-1})$.
\end{theorem}

We note that similar results for SGD with non-standard noise bounds have been proved in the uniformly convex setting in \cite{stich2020error,stich2019unified}.

\begin{proof}
{\bf Expected objective value.}
Take $\theta_t, g_t$ to be fixed for now and $\theta_{t+1} = \theta_t - \eta \,g_t$. Then
\begin{align*}
f(\theta_{t+1}) - f(\theta_t) &= \int_0^1 \frac{d}{ds} f\big(\theta_t - \eta s\,g_t\big)\,\mathrm{d}s\\
	&= \int_0^1 \nabla f\big(\theta_t - s\,\eta g_t\big)\cdot \big(-\eta g_t\big) \,\mathrm{d}s\\
	&= \eta\int_0^1\frac{1}s \big[\nabla f\big(\theta_t - s\,\eta g_t\big) - \nabla f(\theta_t)\big] \cdot \big[\theta_t -s\eta\,g_t-\theta_t\big] - \nabla f(\theta_t) \cdot \eta\,g_t\,\,\mathrm{d}s\\
	&\leq \int_0^1 \frac1s\,C_L\big|\theta_t - s\eta\,g_t -\theta_t\big|^2 - \eta\, \nabla f(\theta_t)\cdot g_t \,\mathrm{d}s\\
	&= C_L\,\eta^2 |g_t|^2 \left( \int_0^1 s\,\mathrm{d}s\right) - \eta \,\nabla f(\theta_t)\cdot g_t.
\end{align*}
Now we consider $\theta_t, g_t= g(\theta_t,\xi_t)$ as the random variables they are in practice. We note that $\theta_{t}$ only depends on $\theta_0, \xi_0,\dots,\xi_{t-1}$ and is independent of $\xi_t$. Thus in expectation
\begin{align*}
{\mathbb E} \big[ \nabla f(\theta_t) \cdot g(\theta_t, \xi_t)\big] &= {\mathbb E}\big[ {\mathbb E}\big[\nabla f(\theta_t) \cdot g(\theta_t, \xi_t) \,\big|\,\theta_0,\xi_0,\dots\xi_{t-1}\big]\big]\\
	&= {\mathbb E}\big[ \nabla f(\theta_t)\cdot {\mathbb E}\big[g(\theta_t, \xi_t) \,\big|\,\theta_0,\xi_0,\dots\xi_{t-1}\big]\big]\\
	&= {\mathbb E}_{\theta_0,\xi_0,\dots,\xi_{t-1}} \big[|\nabla f|^2(\theta_t)\big]\\
{\mathbb E}\big[ |g_t|^2\big] &= {\mathbb E}\big[ |g_t - \nabla f(\theta_t)|^2 + 2 \,g_t\cdot \nabla f(\theta_t) - |\nabla f(\theta_t)|^2\big]\\
	&= {\mathbb E}\big[ |g_t - \nabla f(\theta_t)|^2\big] + {\mathbb E}\big[|\nabla f(\theta_t)|^2\big]
\end{align*}
by the tower identity for conditional expectations. Hence
\begin{align*}
{\mathbb E}\big[ f(\theta_{t+1}) - f(\theta_t)\big] &\leq \frac{C_L\,\eta^2}2\,{\mathbb E}\big[|g_t|^2\big] - \eta\,{\mathbb E}\big[ |\nabla f|^2(\theta_t)\big]\\
	&= \frac{C_L\,\eta^2}2 {\mathbb E}\big[|g_t-\nabla f(\theta_t)|^2\big] + \frac{C_L\,\eta^2}2 {\mathbb E}\big[ |\nabla f|^2(\theta_t)\big] -\eta\, {\mathbb E}\big[ |\nabla f|^2(\theta_t)\big]\\
	&\leq \frac{C_L\sigma\,\eta^2}2\,{\mathbb E}\big[f(\theta_t)\big] + \left( \frac{C_L\,\eta^2}2 - \eta\right)\,{\mathbb E}\big[ |\nabla f|^2(\theta_t)\big].
\end{align*}
If $\frac{C_L\,\eta^2}2 - \eta <0$, i.e.\ $0 < \eta < \frac{2}{C_L}$, we can estimate further that
\[
{\mathbb E}\big[ f(\theta_{t+1}) - f(\theta_t)\big] \leq \left(\frac{C_L\sigma\,\eta^2}2 + \Lambda\left(\frac{C_L\,\eta^2}2 - \eta\right)\right) \,{\mathbb E}\big[f(\theta_t)\big]
\]
or equivalently
\begin{align*}
{\mathbb E}\big[ f(\theta_{t+1})\big] &\leq \left(1 + C_L\frac{\sigma+\Lambda}2\,\eta^2 - \Lambda\eta\right) {\mathbb E}\big[f(\theta_t)\big].
\end{align*}
The prefactor $\rho_\eta:=1 + C_L\frac{\sigma+\Lambda}2\,\eta^2 - \Lambda\eta$ is smaller than $1$ if and only if 
\[
1 - \Lambda \eta + \eta^2 \,\frac{C_L(\Lambda+\sigma)}2 < 1 \qquad\LRa\qquad \eta \left(\frac{C_L(\Lambda+\sigma)}2\,\eta - \Lambda\right) <0 \qquad \LRa \qquad \eta \in \left(0, \frac{ 2\Lambda}{C_L\,(\Lambda+\sigma)}\right).
\]

{\bf Almost sure convergence.} The argument is standard for series with summable norms. Set 
\[
E_t(\varepsilon) = \{\sup_{s\geq t}\beta^sf(\theta_s) \geq \varepsilon\}.
\]
Then
\[
E_\infty(\varepsilon) := \bigcap_{t\geq 0} E_t(\varepsilon) = \big\{\limsup_{t\to\infty}\beta^tf(\theta_t) \geq \varepsilon\big\}
\]
satisfies
\begin{align*}
\P\big(E_\infty(\varepsilon)\big) &\leq \P\big( E_t(\varepsilon)\big)\\
	&\leq \sum_{s=t}^\infty \P\big(\{\beta^sf(\theta_s)\geq \varepsilon\}\big)\\
	&\leq \sum_{s=t}^\infty \frac{{\mathbb E}\big[\beta^s f(\theta_s)\big]}\varepsilon\\
	&\leq \frac{1} \varepsilon \sum_{s=t}^\infty \left(\beta\rho_\eta\right)^s\,{\mathbb E}\big[f(\theta_0)\big]\\
	&= \frac{(\beta\rho_\eta)^t}{1-\beta\rho_\eta}\,\frac{{\mathbb E}\big[f(\theta_0)\big]}\varepsilon.
\end{align*}
By taking $t\to\infty$, we observe that $\P\big(E_\infty(\varepsilon)\big) =0$, i.e.\ $\limsup_{t\to\infty}\beta^tf(\theta_t) <\varepsilon$ almost surely. As this holds for all $\varepsilon>0$, we find that $\beta^tf(\theta_t)\to 0$ almost surely.
\end{proof}

The optimal learning rate if the constants are known satisfies
\[
\frac{d}{d\eta} \left(1-\Lambda\eta + \frac{C_L(\Lambda+\sigma)}{2}\,\eta^2\right)=0 \qquad \Ra\qquad \eta = \frac{\Lambda}{C_L(\Lambda+\sigma)}, \quad \rho_\eta = 1-\frac{\Lambda^2}{2\,C_L(\Lambda+\sigma)}.
\]
In the noiseless case $\sigma =0$, this boils down to the well-known estimate for deterministic gradient descent. 



\begin{corollary}\label{corollary convergence to minimum lojasiewicz}
Assume that $f, \eta$ and $g$ are like in Theorem \ref{theorem linear convergence}. Then $\theta_t$ converges to a random variable $\theta_\infty$ in $L^2$ and almost surely. The rate of convergence is
\[
\|\theta_t - \theta_\infty\|_{L^2(\P)} \leq\rho_\eta^{t/2} \,\frac{\eta\sqrt{2C_L+\sigma}\,{\mathbb E}\big[f(\theta_0)\big]}{1- \rho_\eta^{1/2}}
\] $f(\theta_\infty) \equiv 0$ almost surely.
\end{corollary}

\begin{proof}
Note that 
\[
\theta_t = \theta_0 + \sum_{i=1}^t\big(\theta_i - \theta_{i-1}\big) 
\]
and that 
\begin{align*}
\sum_{i=1}^\infty\big\|\theta_i - \theta_{i-1}\big\|_{L^2} = \eta\sum_{i=1}^\infty\big\|g(\theta_i,\xi_i)\|_{L^2} 
	\leq \eta\sum_{i=1}^t\sqrt{{\mathbb E}\big[|\nabla f(\theta_i)|^2\big] + {\mathbb E}\big[|g(\theta_i,\xi_i) - \nabla f(\theta_i)|^2\big]}.
\end{align*}
Recall that 
\[
|\nabla f(\theta)|^2 \leq 2C_L\, f(\theta)\qquad\forall\ \theta \in \R^m
\]
for non-negative functions with Lipschitz-continuous gradient (see e.g.\ Lemma \ref{lemma bounded gradient} in Appendix \ref{appendix local convergence}) and that
\[
{\mathbb E}\big[ |g(\theta_i, \xi_i) - \nabla f(\theta_i)|^2\big] \leq \sigma\,{\mathbb E}\big[f(\theta_i)\big].
\]
as above. Thus
\begin{align*}
\sum_{i=1}^\infty\big\|\theta_i - \theta_{i-1}\big\|_{L^2} &\leq \eta \sum_{i=1}^\infty \left[ \sqrt{{\mathbb E}\big[2C_L\,f(\theta_i)\big]+ \sigma\,{\mathbb E}\big[f(\theta_i)\big]}\right]\\
	&\leq \eta \sqrt{2C_L+\sigma}\,\sqrt{{\mathbb E}\big[f(\theta_0)\big]} \sum_{i=1}^\infty \rho_\eta^{1/2}\\
	&<\infty,
\end{align*}
i.e.\ the limit
\[
\theta_\infty := \lim_{t\to\infty} \theta_t = \theta_0 + \sum_{i=1}^\infty (\theta_i - \theta_{i-1})
\]
exists in the $L^2$-sense and
\[
\|\theta_\infty-\theta_t\|_{L^2} \leq \sum_{i=t}^\infty \|\theta_{i+1} - \theta_i\|_{L^2} \leq \eta \sqrt{2CL+\sigma}\sqrt{{\mathbb E}\big[f(\theta_0)\big]} \sum_{i=t}^\infty \rho_\eta^{1/2} = \eta \sqrt{2CL+\sigma}\sqrt{{\mathbb E}\big[f(\theta_0)\big]} \frac{\rho_\eta^{t/2}}{1-\rho_\eta^{1/2}}.
\]
 Since the increments are summable, the convergence is pointwise almost everywhere by the same argument as in Theorem \ref{theorem linear convergence}.
\end{proof}

\subsection{Convergence close to the minimum}

Any function which has a critical point that is not the global minimum does not satisfy a \L{}ojasiewicz inequality. However, if such an inequality holds close to the minimum and the initial condition is very close to the global minimum, then with high probability we converge to the minimum exponentially fast.

\begin{theorem}\label{theorem local convergence}
Assume that there exists $\varepsilon>0$ such that the local \L{}ojasiewicz inequality
\[
\Lambda\,f(\theta)\leq |\nabla f(\theta)|^2
\]
holds on the set
\[
U(\varepsilon) = \{\theta : f(\theta)<\varepsilon\}
\] 
and that $\nabla f$ is $C_L$-Lipschitz continuous on $U(\varepsilon)$. Then for every $\delta>0$ there exists $\varepsilon'>0$ such that the following holds: If $\theta_0\in U(\varepsilon')$ almost surely, then with probability at least $1-\delta$ we have $\theta_t\in U(\varepsilon)$ for all $t\in \N$. 

Conditioned on the event that $\theta_t\in U(\varepsilon)$ for all $t$, the estimate 
\[\showlabel
\lim_{t\to\infty} \beta^t\,f(\theta_t) =0
\]
holds almost surely for every
\[\showlabel
\beta\ \in [1,\rho_\eta^{-1}) \qquad\text{where }\rho_\eta = 1 - \Lambda\eta + \eta^2 \frac{C_L(\Lambda+\sigma)}{2\Lambda}
\]
if the learning rate satisfies
\[
0 < \eta < \frac{2\Lambda}{C_L(1+\sigma)}.
\]
\end{theorem}

The proof idea is as follows: In any iteration, we expect the objective value to decrease. While it may increase at times, it can only increase by small amounts as long as the objective value is small, and it is unlikely for errors to accumulate sufficiently for $f(\theta_t)$ to exceed $\varepsilon$ if $f(\theta_0)\ll \varepsilon$ is small enough. In the event that $f(\theta_t)<\varepsilon$ for all $t\in\N$, we can follow along the lines of Theorem \ref{theorem linear convergence}. The rigorous proof is a variation of that of \cite[Theorem 4]{mertikopoulos2020almost} and given in Appendix \ref{appendix local convergence}. The main difference to the original is that the error is controlled by a decaying learning rate in \cite{mertikopoulos2020almost} and by the low noise intensity for low objective value in our context. If the set $U(\varepsilon)$ has multiple connected components, of course the \L{}ojasiewicz inequality and Lipschitz-condition are only required to hold locally as the result is local in nature.

\begin{remark}
A version of Corollary \ref{corollary convergence to minimum lojasiewicz} holds also in this case with virtually the same proof, conditioned on the event that $\theta_t\in U(\varepsilon)$ for all $t\in \N$.
\end{remark}

\subsection{On the global convergence of SGD with ML noise}

Whether SGD converges to a global minimum even with poor initialization if the target function does not satisfy a \L{}ojasiewicz inequality is quite delicate and requires strong assumptions. In general, this cannot be guaranteed.

\begin{example}
Consider the functions
\[
h_\alpha(x) = \frac{(x^2-1)^2}4 + \alpha x, \qquad f_\alpha(x) = h_\alpha(x) - \inf_{x'\in\R}h_\alpha(x').
\]
For $\alpha =0$, the function $f_\alpha$ has two minima of equal depth at $x=\pm 1$. If $\alpha$ is small but non-zero, the two local minima do not have equal depth. Assume that the gradient estimators are of the form
\[
g(x,\xi) = f_\alpha'(x) + \sqrt{\sigma \,f_\alpha(x)}\,\xi
\]
where $\xi$ is equal to $1$ or $-1$ with equal probability. If 
\[
\sqrt\sigma < \min_{1/4 < |x| < 1/2} \frac{|f_\alpha'(x)|}{\sqrt{f_\alpha(x)}}
\]
and $\eta$ is reasonably small, $x$ can never escape the potential well it started in.
\end{example}

The situation is different if the noise is unbounded and the objective function has particularly convenient properties not only at the set of global minimizers.

\begin{theorem}\label{theorem global convergence}
Let $f:\R^m\to [0,\infty)$ be a function such that
\begin{enumerate}
\item The set $N:= f^{-1}(0)$ is not empty.
\item $f$ is $C^1$-smooth and $\nabla f$ satisfies the one-sided Lipschitz condition
\[\showlabel\label{eq lipschitz global convergence}
\big(\nabla f(\theta) - \nabla f(\theta')\big) \cdot \big(\theta-\theta') \leq C_L |\theta-\theta'|^2.
\]
\item A \L{}ojasiewicz inequality holds on the set where $f$ is small, i.e.\ there exist $\varepsilon, \lambda >0$ such that
\[\showlabel \label{eq lojasiewicz small}
f(\theta) < \varepsilon \qquad\Ra\qquad \lambda\,f(\theta)\leq |\nabla f(\theta)|^2.
\]
\item A \L{}ojasiewicz inequality holds on the set where $f$ is large, i.e.\ there exist $S, \Lambda>0$ such that 
\[\showlabel \label{eq lojasiewicz large}
f(\theta) \geq S \qquad\Ra\qquad \Lambda\,f(\theta)\leq |\nabla f(\theta)|^2.
\]
\item $f$ grows uniformly away from its minimum, i.e.\ there exists $R>0$ such that 
\[\showlabel\label{eq low objective tight}
f(\theta)\leq  S \qquad\Ra\qquad \exists\ \theta' \text{ s.t. } f(\theta') = 0\text{ and } |\theta-\theta'|<R
\]
where $S$ is the same as in \eqref{eq lojasiewicz large}.
\end{enumerate}
Assume that the gradient noise satisfies the following:
\begin{enumerate}
\item The noise has ML type, i.e.\
\[
{\mathbb E}_\xi \big[ |g(\theta,\xi) - \nabla f(\theta)|^2\big] \leq \sigma\,f(\theta) \qquad\forall\ \theta.
\]
\item The noise is uniformly unbounded in the sense that
\[
g(\theta, \xi) = \nabla f(\theta) + \,\sqrt{\sigma\,f(\theta)}\,Y_{\theta,\xi}
\]
and there exists a continuous function $\psi:(0,\infty)^2\to(0,\infty)$ such that $Y$ satisfies
\begin{equation}\label{eq spread out noise}
{\mathbb E} Y_{\theta,\xi} =0, \qquad \P\big(Y_{\theta,\xi} \in B_r(\tilde\theta)\big) \geq \psi\big(|\tilde\theta |,r\big)>0 \qquad\forall\ \tilde\theta\in \R^m, r>0
\end{equation}
independently of $\theta$.
\end{enumerate}
Finally, assume that the learning rate satisfies 
\[
0<\eta< \min\left\{\frac{2\lambda}{C_L(\lambda +\sigma)}, \frac{2\Lambda}{C_L(\Lambda+\sigma)}\right\}.
\]
Assume that $\theta_0$ is an initial condition such that ${\mathbb E}\big[f(\theta_0)\big]<\infty$. Then the estimate
\[
\limsup_{t\to\infty} \frac{f(\theta_t)}{\rho^t} <\infty
\]
holds almost surely for every
\[\showlabel
\rho \in \left(\rho_\eta, 1\right), \qquad \rho_\eta:= 1 - \lambda\eta + \eta^2 \frac{C_L(\lambda+\sigma)}{2\lambda}.
\]
\end{theorem}


\begin{proof}[Proof sketch]
We use the \L{}ojasiewicz inequality on the set $\{f>S\}$ to show that SGD iterates visit the set $\{f\leq S\}$ infinitely often almost surely. For $\theta_t\in \{f\leq S\}$, there exists a uniformly positive probability that the $\theta_{t+1} \in \{f<\varepsilon'\}$ due to the condition on the noise to be sufficiently `spread out' and on the set $\{f\leq S\}$ to be sufficiently close to $\{f=0\}$. Thus for infinite time, we visit the set $\{f<\varepsilon'\}$ almost surely. 

Once we enter $\{f<\varepsilon'\}$, we remain trapped in the set $\{f<\varepsilon\}$ with high probability by Theorem \ref{theorem local convergence}, and in that case, we almost surely observe that $f\to 0$ at a linear rate. Even if we leave from $\{f<\varepsilon\}$, we almost surely visit again. The probability to escape infinitely often vanishes, so we expect that $f(\theta_t)\leq \rho_\eta^{t-T}\,f(\theta_T)$ for all $t\geq T$ for almost every realization of SGD for some random time $T$.  
\end{proof}

The full proof is given in Appendix \ref{appendix global convergence}. With a variation of the proof of Corollary \ref{corollary convergence to minimum lojasiewicz}, the following can be obtained. Note that the rate of convergence $\rho_\eta$ depends only on the \L{}ojasiewicz constant on the set where $f$ is small. 

\begin{corollary}\label{corollary global convergence argument}
Assume that $f, \eta$ and $g$ are like in Theorem \ref{theorem global convergence}. Then $\theta_t$ converges to a minimizer of $f$ almost surely.
\end{corollary}

\begin{remark}
Our results suggest that, in a fairly general class of functions, SGD with ML noise converges to a global minimizer exponentially fast (or at least that the objective function decays exponentially along SGD iterates). However, it may take a very long time to reach the set in which exponential convergence is achieved, especially if the dimension $m$ of the parameter space and the co-dimension $m-n$ of the minimizer manifold $N$ are both high. 
\end{remark}

We give a few simple examples of situations in which Theorem \ref{theorem global convergence} can in fact be applied. Despite its weaknesses, we believe this mechanism to be a major driving factor behind the success of SGD in the machine learning of overparametrized neural networks.

\begin{remark}
If the function $f$ satisfies the conditions of Theorem \ref{theorem global convergence}, noise of the form
\[
g(\theta,\xi) = \nabla f(\theta) + \sqrt{\sigma\,f(\theta)}\,Y_\xi
\]
is admissible, where where $Y\sim \mathcal N(0,I)$ is standard Gaussian noise.
\end{remark}

\begin{example}
The following functions satisfy the conditions of Theorem \ref{theorem global convergence}, but do not satisfy a global \L{}ojasiewicz inequality:
\begin{enumerate}
\item $f(x,y) = \sin(x) + \sin(y)+2$. The set of minimizers is a lattice, $f$ is bounded, and every minimizer is non-degenerate.
\item $f_\varepsilon(x) = x^2 + 2\varepsilon\,\sin^2(x/\varepsilon)$ for any fixed $\varepsilon>0$. The only minimizer is at $x=0$. Far away from the origin, the oscillatory perturbation becomes negligible in both $f_\varepsilon$ and $f_\varepsilon'$.
\end{enumerate}
More generally, if $f$ is a perturbation of a quadratic form in the following sense, then Theorem \ref{theorem global convergence} applies:
\begin{itemize}
	\item $f\geq 0$.
	\item The set $\{f=0\}$ is a finite union of disjoint compact $C^2$-manifolds $N_1, \dots, N_k$ (potentially of different dimensions). If $\theta\in N_k$, then $D^2f(\theta)$ has rank $m-\dim(N_k)$ at $x$ and the smallest non-zero singular value of $D^2f$ is bounded away from zero.
	\item The perturbation becomes negligible at infinity, i.e. there exists a positive definite symmetric matrix $A$ such that
	\[
	\lim_{|\theta|\to\infty}\frac{f(\theta)}{\frac12\,\theta^TA\theta} = 1, \qquad \lim_{|\theta|\to\infty}\frac{|\nabla f(\theta) - A\theta|}{|A\theta|} = 0.
	\]
\end{itemize}
Also the first example could be generalized to small perturbations of periodic functions with non-degenerate minimizers.
\end{example}

\begin{example}
The following functions {\em do not} satisfy the conditions of Theorem \ref{theorem global convergence} since there are low energy points arbitrarily far away from the set of global minimizers:
\[
f_1, f_2:\R\to\R, \qquad f_1(x) = 1+ \sin^2(x) - \frac1{x^2+1}, \qquad f_2(x) = 1+ x^2 \sin^2(x) - \frac1{x^2+1}.
\]
In this one-dimensional setting, that problem could presumably be solved by appealing to the recurrence of random walks, but the situation is hopeless in analogous constructions in dimension three or higher.
\end{example}

Let us consider the conditions placed in Theorem \ref{theorem global convergence} in the context of deep learning.

\begin{remark}
\begin{itemize}
\item As the parameter gradient of a deep neural network with respect to deep layer coefficients is linear in the final layer coefficients (see Remark \ref{remark gradients linear}), the Lipschitz-condition \eqref{eq lojasiewicz small} cannot hold globally. If the activation function is smooth, it holds locally.
\item Generically, the Hessian of $L$ has maximal rank on $N$ due to Theorem \ref{theorem cooper}, so the local \L{}ojasiewicz inequality \eqref{eq lojasiewicz small} should hold at least locally on $\R^m$. 
\item Due to Lemma \ref{lemma no high energy critical points}, the objective function has no critical points where it is large. While \eqref{eq lojasiewicz large} may not be satisfied as such, a condition of this type does not violate the spirit of the minimization problem under consideration.
\item It is currently unknown to us whether the condition \eqref{eq low objective tight} that the set of low objective values is within a bounded tube around $N$ is generically satisfied or not. We offer the following rationale: Let $\theta$ such that $L(\theta)\leq S$. Choose $n' = \frac{m-nk}k$ additional points $x_{n+1}, \dots, x_{n+n'}$ (assuming that $n'$ is an integer) and set $\hat y_i = h(\theta,x_i)$ for $1\leq i \leq n+n'$. If the map
\[
\widehat \Phi:\R^m\to \R^{nk+n'k} = \R^m, \qquad \widehat\Phi(\theta) = \big(h(\theta, x_1), \dots, h(\theta, x_n)\big)
\]
has a Lipschitz-continuous inverse, then there exists $\theta'$ such that 
\begin{enumerate}
\item $\Phi(\theta', x_i) = y_i$ for $1\leq i\leq n$ and $\Phi(\theta', x_i) = \hat y_i$ for $n+1\leq i \leq n+n'$.
\item $\theta$ and $\theta'$ are somewhat close as \begin{align*}
|\theta-\theta'| &\leq C\,|y-y'| 
	= C\sqrt{\sum_{i=1}^n |y_i-\hat y_i|^2}
	=C\sqrt{\sum_{i=1}^n |y_i-h(\theta,x_i)|^2}\\
	& = C\sqrt{n\,L(\theta)} \leq C\sqrt{nS}.
\end{align*}
\end{enumerate}
Thus a condition of the type \eqref{eq low objective tight} may hold for nicely parametrized models, but the constant is expected to be somewhat large if the data set is large.

\item The type of noise specified in \eqref{eq spread out noise} is unrealistic in overparametrized learning models as it is omni-directional, whereas realistic noise is necessarily low rank due to Lemma \ref{lemma low rank}. The fact that the noise is `spread out' is needed to guarantee that we may randomly `jump' into the set $\{f<\varepsilon\}$ from anywhere in the set $\{f\leq S\}$. Identifying more realistic geometric conditions with similar guarantees remains an open problem.
\end{itemize}
\end{remark}


\begin{remark}
Theorem \ref{theorem global convergence}, were it to apply, could be viewed as a negative result in the context of implicit regularization in machine learning. We can decompose the mean squared error population risk functional as
\begin{align*}
\mathcal{R}(h) &= \int_{\R^d} \big|h(x)-y\big|^2 \,\P(\d x\otimes \d y)\\
	&= \int_{\R^d} \big|h(x)-h^*(x)\big|^2 \,\P(\d x\otimes \d y) + \int_{\R^d} \big|h^*(x)-y\big|^2 \,\P(\d x\otimes \d y)\\
	&= \int_{\R^d} \big|h(x)-h^*(x)\big|^2 \,\P(\d x\otimes \d y) + C_0
\end{align*}
where $h^*(x) = {\mathbb E}[y|x]$ is the risk minimizer in the class of measurable functions and $C_0 = \mathcal{R}(h^*)$ is the minimum Bayes risk. If the distribution $\P$ admits any uncertainty in the output $y$ given observations $x$, then $C_0>0$. However, in overparametrized learning the empirical risk
\[
\widehat\mathcal{R}_n(h) = \frac1n\sum_{i=1}^n \big|h(x_i)-y_i\big|^2
\]
can be zero. Thus if $C_0$ is large and the parameters of a model are trained by SGD with small positive learning rate, then after a long time, we expect $\mathcal{R}$ and $\widehat\mathcal{R}_n$ to differ greatly at the parameters $\theta_t$. To avoid overfitting the training data, we therefore require an early stopping strategy. If the observations are virtually noiseless (which is the case for benchmark image classification problems), then this rationale may not apply, and SGD may perform well without early stopping.
\end{remark}



\section{A numerical illustration}\label{section numerical}

\begin{figure}
\includegraphics[width = 0.31\textwidth]{./Images/Uniform_SGD_300_constant.png}\hfill 
\includegraphics[width = 0.31\textwidth]{./Images/Uniform_SGD_300_fast_decaying.png}\hfill 
\includegraphics[width = 0.31\textwidth]{./Images/ML_SGD_300.png}

\vspace{4mm}
\includegraphics[width = 0.31\textwidth]{./Images/Uniform_SGD_1000_constant.png}\hfill 
\includegraphics[width = 0.31\textwidth]{./Images/Uniform_SGD_1000_fast_decaying.png}\hfill 
\includegraphics[width = 0.31\textwidth]{./Images/ML_SGD_1000.png}
\caption{SGD with homogeneous noise and constant learning rate (left) or decaying learning rate (middle) vs SGD with ML noise (right) after 300 iterations (top row) and after 1000 iterations (bottom row). For 1000 realizations of SGD, we mark the final position by a red dot in the energy landscape and plot a histogram density estimator of the $x$-coordinate below. 
\label{figure comparison}}
\end{figure}

We compare toy models for stochastic gradient descent
\begin{equation}\label{eq comparing sgds}
x_{n+1} = x_n - \eta \big(\nabla f(x_n) + \sigma Y_n\big), \qquad \tilde x_{n+1} = \tilde x_n - \eta \big(\nabla f(\tilde x_n) + \widetilde \sigma \sqrt{f(\tilde x_n)} \,Y_n\big)
\end{equation}
where $\eta$ is a learning rate, $\sigma, \widetilde \sigma>0$ control the noise level, and $Y_n$ is an is a standard Gaussian. For a fair comparison, $\sigma$ and $\widetilde\sigma$ have to be chosen such that the noise has the same magnitude at a certain point of interest.
Consider the function
\[
f:\R^2\to \R, \qquad f(x,y) = \frac{x^4}4 - x^2 +\alpha x + y^2 + c_\alpha
\]
where $\alpha \geq 0$ is a parameter and $c_\alpha$ is chosen such that $\inf_{(x,y)} f(x,y) = 0$. For any $\alpha\in(0,1]$, the function $f$ has two distinct local minima at $(x_-,0)$ and $(x_+,0)$ where $x_- < 0 < x_+$. Clearly, we have $f(x_-,0) < f(x_+,0)$. 

We considered 1000 realizations of SGD according to the schemes \eqref{eq comparing sgds} with $\alpha = 0.25$, learning rate $\eta = 0.05$ and noise $\widetilde\sigma = 4.0$. The parameter $\sigma$ was chosen such that the noise at the ridge between the minima of $f$ has the same intensity for both algorithms to give them equal opportunity to escape the local minimum. In all runs, the initial condition was $(x_0, y_0) = (3,0)$.

In Figure \ref{figure comparison}, we see that SGD with ML type noise and constant learning rate approaches the global minimum rapidly whereas SGD with homogeneous Gaussian noise and constant learning rate forms a cloud around the minima which has higher density at the global minimum. SGD with homogeneous noise and decaying learning rate forms more focussed clouds around the minima, but about 25\% of trajectories do not escape the local minimum. The decaying learning rate is chosen as 
\begin{equation}\label{eq learning rates}
\eta_t = t_0\,\frac{\eta}{t+t_1}, \qquad t_0 = 20, \quad t_1=5.
\end{equation}
We make similar observations if the learning rate decays of the same order but less rapidly with $t_0 =200$ and $t_1=50$, but with less focussed point clouds.

After 300 iterations, the point cloud of SGD with homogeneous noise and positive learning rate is comparable to that of SGD with ML noise at the local minimum. This seems to be due to the fact that both start closer to the local minimum and are equally likely to escape the local minimum due to our scaling of the noise.

Once a trajectory of SGD with ML noise enters the potential well of the global minimum, it is unlikely to escape, whereas SGD with homogeneous Gaussian noise exchanges particles back and forth between the two wells. Once within the potential well of the global minimum, a trajectory of SGD with ML noise converges to the global minimum rapidly. Therefore, after 1000 iterations, trajectories of SGD with ML noise are almost guaranteed to have found the global minimum, whereas trajectories of SGD with homogeneous noise are somewhat likely to be found in the potential well of the local minimum, independently of whether the learning rate is constant or decaying.


\section{Conclusion}

More realistic abstract models for the noise of stochastic gradient descent in machine learning may explain help explain some of the success that SGD has enjoyed in this specific non-convex optimization task. We believe our results are indicate why SGD often finds global minima/low loss local minima rather than positive loss local minima.

Our results give an indication that it may be admissible in these applications to leave the learning rate uniformly positive. This may be particularly relevant for online learning tasks, where new data is added to the model. Decaying learning rates significantly diminish the effect that new data can have in finite time.
The reason that the learning rate should be small in these optimization tasks is related both to the roughness of the loss landscape and the presence of stochastic noise. The estimates resemble non-stochastic gradient descent more closely than SGD with homogeneous noise estimates.

There are several pressing questions that were not explored in this work, both on the theoretical and practical side.

\begin{enumerate}
\item The biggest deficiency of our global convergence result is the reliance on omni-directional noise while realistic noise in machine learning SGD is low rank, at least for overparametrized models. Understanding the geometry of realistic noise and its impact on the convergence of SGD is an important open problem.

\item The objective functions we employ serve as toy models for the energy landscape of $L^2$-regression problems in deep learning. The energy landscape of classification problems and the associated gradient noise are quite different as noted in Example \ref{example loss functions} and Lemma \ref{lemma noise bounds}. Understanding the behavior of SGD in classification-like loss landscapes and noise models remains an open problem.

\item While our assumptions are fairly general in the context of optimization theory, they likely are too restrictive in the setting of deep learning. Understanding the geometry of deep learning problem, and whether they allow for similar results, is the next important step in this approach to the analysis of SGD. 

\item The Lipschitz-constant of the gradient of the objective function is not generally uniformly controlled over the parameter space. If a minimum is too steep, gradient descent may escape from it exponentially fast due to finite step size effects. This mechanism cannot be captured by continuum models and renders the positive step-size analysis invalid in the context of deep learning, unless we assume or enforce confinement to a bounded domain by other means.

\item In practice we do not use random selection SGD (choosing a batch of data samples randomly from the training set), but random pass SGD (passing through the entire training set batch by batch before repeating the same data point). The random directions in consecutive iterations are therefore not truly iid, and the noise may be less oscillatory in practice than random selection estimation would suggest. We believe the impact of this difference to be negligible for large data sets, but a rigorous connection has not been established to the best of our knowledge.

\item Typically, advanced optimizers like gradient descent with momentum, Nesterov's accelerated gradient descent or ADAM are used  in deep learning with stochastically estimated gradients. It remains to be seen whether noise of ML type allows for stronger estimates and global convergence guarantees also in that setting.

\item The main goal of this article was to understand SGD in toy models inspired by problems of deep learning. Another interesting direction is whether artificially perturbing (exact or estimated) gradients by omni-directional noise of ML type can improve the convergence of a gradient descent type optimization algorithm.
\end{enumerate}



\bibliographystyle{../../alphaabbr}
