Convergence of stochastic gradient descent under a local Lojasiewicz
  condition for deep neural networks
We study the convergence of stochastic gradient descent (SGD) for non-convex
objective functions. We establish the local convergence with positive
probability under the local \L{}ojasiewicz condition introduced by Chatterjee
in \cite{chatterjee2022convergence} and an additional local structural
assumption of the loss function landscape. A key component of our proof is to
ensure that the whole trajectories of SGD stay inside the local region with a
positive probability. We also provide examples of neural networks with finite
widths such that our assumptions hold.
Jing An, Jianfeng Lu
Convergence of stochastic gradient descent under a local Lajasiewicz condition for deep neural networks

###### Abstract

We extend the global convergence result of Chatterjee [7] by considering the stochastic gradient descent (SGD) for non-convex objective functions. With minimal additional assumptions that can be realized by finitely wide neural networks, we prove that if we initialize inside a local region where the Lajasiewicz condition holds, with a positive probability, the stochastic gradient iterates converge to a global minimum inside this region. A key component of our proof is to ensure that the whole trajectories of SGD stay inside the local region with a positive probability. For that, we assume the SGD noise scales with the objective function, which is called machine learning noise and achievable in many real examples. Furthermore, we provide a negative argument to show why using the boundedness of noise with Robbins-Monro type step sizes is not enough to keep the key component valid.

## 1 Introduction

The stochastic gradient descent (SGD) and its variants are widely applied in machine learning problems due to its computational efficiency and generalization performance. A typical empirical loss function for the training writes as

\[F(\theta)=\mathbb{E}_{\xi\sim\mathcal{D}}[f(\theta,\xi)], \tag{1.1}\]

where \(\xi\) denotes the random sampling from the training data set following the distribution \(\mathcal{D}\). A standard SGD iteration to train weight variables \(\theta\in\mathbb{R}^{n}\) is of the form

\[\theta_{k+1}=\theta_{k}-\eta_{k}\nabla f(\theta_{k},\xi_{k}). \tag{1.2}\]

Here, the step size \(\eta_{k}\) can be either a fixed constant or iteration-adapted, and \(\nabla f(\theta_{k},\xi_{k})\) is a unbiased stochastic estimate of the gradient \(\nabla F(\theta_{k})\), induced by the sampling of the gradient.

The convergence of SGD for convex objective functions has been well established, and we give an incomplete list of works [6, 26, 5, 25, 21, 16] here for reference. However, in practice, it is more realistic to study the SGD for non-convex optimization problems, because training tasks are usually combined with complex neural networks and the stochastic gradient algorithms perform particularly well in non-convex optimization [10, 17, 28]. Compared with convex optimization, the behavior of stochastic gradient algorithms over the non-convex landscape is unfortunately much less understood. Due to the noise, the trajectory of stochastic iterates is more difficult to track. Thus, it is natural to investigate whether stochastic gradient algorithms converge through the training, and what minimum they converge to in the non-convex problem. However, these questions are noticeably challenging in both qualitative and quantitative senses. Most available results are limited. For example, works
such as [1, 2, 14, 34] provide convergence guarantees to a local minimum in terms of quantifying the vanishing of \(\nabla F\), but little information is given on what critical points that SGD converges to. Many convergence results are based on global assumptions on the objective function, including the global Poylak Lajasiewicz condition [22, 23], the global quasar-convexity [15], or assumptions of weak convexity and global boundedness of iterates [12, 33]. Those global assumptions are often not realistic, at least they cannot cover general multi-modal landscapes.

Connected with deep neural network structures, most convergence results are built in the over-parametrized regime, which means that the number of neurons grow at least polynomially with respect to the sample size. For example, works including [8, 18, 32, 36] consider wide neural networks, which essentially linearize the problem by extremely large widths. Particularly in such settings, Poylak-Lajasiewicz type conditions are shown to be satisfied, and they thus prove convergence with linear rates [3, 23]. However, convergence results are very limited for neural networks with finite widths and depths, and we refer to [7, 19] for recent progresses in terms of the convergence of gradient descents in such scenario.

In particular, [7] constructs feedforward neural networks with smooth and strictly increasing activation functions, with the input dimension being greater than or equal to the number of data points. Such neural networks satisfy a local version of the Lajasiewicz inequality, and the convergence of gradient descent to a global minimum given appropriate initialization are fully analyzed. In this work, our goal is to extend the global convergence result in [7] to a stochastic version, with minimal additional assumptions added to the loss function \(F(\theta)\).

#### Notation

Throughout the note, \(|\cdot|\) denotes the Euclidean norm, \(B(\theta,r)\) denotes an Euclidean ball with radius \(r\) centered at \(\theta\). Unless otherwise specified, the expectation \(\mathbb{E}=\mathbb{E}_{\xi\sim\mathcal{D}}\), and the gradients \(\nabla=\nabla_{\theta}\).

## 2 Preliminaries

We name the major assumption used in [7] as the local Lajasiewicz condition. Let us first recall the definition as in [7]: Given the dimension \(d\), let \(F:\mathbb{R}^{d}\to[0,\infty)\) be a non-negative loss function. For any \(\theta_{0}\in\mathbb{R}^{d}\) and \(r>0\), we define

\[\alpha(\theta_{0},r):=\inf_{B(\theta_{0},r),F(\theta)\neq 0}\frac{|\nabla F( \theta)|^{2}}{F(\theta)}. \tag{2.1}\]

If \(F(\theta)=0\) for all \(\theta\in B(\theta_{0},r)\), then we set \(\alpha(\theta_{0},r)=\infty\). With that, the main assumption is

**Assumption 1** (local Lajasiewicz condition).: _We assume that for some \(r>0\),_

\[4F(\theta_{0})<r^{2}\alpha(\theta_{0},r). \tag{2.2}\]

**Assumption 2** (\(C_{l}\)-smoothness).: _Furthermore, we assume that for a compact set \(\mathcal{K}\), there exist a constant \(C_{L}>0\) such that_

\[|\nabla F(\theta_{1})-\nabla F(\theta_{2})|\leq C_{L}|\theta_{1}-\theta_{2}| \tag{2.3}\]

_for any \(\theta_{1},\theta_{2}\in\mathcal{K}\)._

Based on that, we can obtain a local growth control of \(|\nabla F|\). The following result is a local version of [35, Lemma B.1]. The proof is the same and omitted, because the only modification needed for the localization is by assuming the local boundedness of \(|\nabla F|\).
**Lemma 2.1**.: _Suppose that \(F:\mathbb{R}^{d}\to\mathbb{R}\) is a non-negative function. Assume \(\nabla F\) is Lipschitz continuous in a compact set \(\mathcal{K}\) with the constant \(C_{L}\), and there exists \(\bar{C}>0\) such that \(\max_{\theta\in\mathcal{K}}|\nabla F(\theta)|=\bar{C}\). Then there exists a compact set \(\tilde{\mathcal{K}}\subset\mathcal{K}\), where \(\text{dist}(\partial\mathcal{K},\partial\tilde{\mathcal{K}})\) depends on \(C_{L}\) and \(\bar{C}\), such that for any \(\theta\in\tilde{\mathcal{K}}\),_

\[|\nabla F(\theta)|^{2}\leq 2C_{L}F(\theta). \tag{2.4}\]

Throughout the note, we assume that \(B(\theta_{0},r)\subset\tilde{\mathcal{K}}\) for a given radius \(r>0\).

### Additional assumptions

Besides the local Lajasiewicz condition, we need an additional structural assumption on \(F\). Given a large radius \(R\) such that (2.2) is satisfied for all \(r\leq R\), it is natural to assume that the \(F(\theta)\) is bounded away from zero near the domain boundary.

**Assumption 3**.: _For some constant \(M_{0}>0\),_

\[F(\theta)\geq M_{0},\quad\text{for all }\theta\in B(\theta_{0},R)\setminus B( \theta_{0},R-1). \tag{2.5}\]

Here we set the annulus radius to be \(1\) for simplicity. The assumptions (2.5) can include more general \(F\) by applying geometric transformations to \(F\), or linear transformations to the dataset to change the annulus radius.

The assumption (2.5) is in order to ensure that the support of the global minimum \(F(\theta^{*})=0\) is away from the boundary \(\partial B(\theta_{0},R)\). In [7, Theorem 2.1], Chatterjee constructed a feedforward neural network with finite width and depth that satisfies the local Lajasiewicz condition (2.2). We will verify in the Appendix that such a neural network satisfies (2.5) as well.

### Stochastic gradients

To analyze the convergence of stochastic gradient algorithms, it is unavoidable to assume some structure of the gradient noise. We may write the stochastic gradient in the decomposition form

\[\nabla f(\theta,\xi)=\nabla F(\theta)+Z(\theta,\xi), \tag{2.6}\]

where the noise term \(Z(\theta,\xi)\) is unbiased

\[\mathbb{E}[Z(\theta,\xi)]=0. \tag{2.7}\]

In most papers, usually two kinds of structural assumptions are imposed on the noise. We take a brief review.

* If one plans to analyze SGD with adaptive step sizes \(\eta_{k}\), i.e., in the Robbins-Monro flavor [31] \[\sum_{k=1}^{\infty}\eta_{k}=\infty,\quad\sum_{k=1}^{\infty}\eta_{k}^{1+m/2}< \infty,\text{ with }m\geq 2,\] (2.8) then it is typical to assume the bounded moments of stochastic gradients, that is, for some constant \(c>0\) and \(m\geq 2\), \[\mathbb{E}[|Z(\theta,\xi)|^{m}]\leq c^{m}<\infty.\] (2.9) The bounded variance (\(m=2\)) assumption is standard in stochastic optimization, and we refer to classical books, lecture notes and papers [4, 27, 29, 20] on this setup. The noise boundedness and adaptive step sizes have been a popular combination to establish convergence, for example,
[24] provides a SGD convergence based on the local convexity assumption, [13] gives the convergence of SGD to the local manifold of minima by estimating \(\mathbb{P}(F(\theta_{k})-\inf_{\theta\in\mathbb{R}^{d}}F(\theta)\geq\epsilon)\). We also mention works such as [30] that introduces the stochastic variance reduction method, which is motivated by improving the convergence rate for \(\min_{0\leq k\leq N-1}\mathbb{E}[|\nabla F(\theta_{k})|^{2}]\).
* On the other hand, if one just wants to establish global convergence for a fixed step size \(\eta\), additional assumptions on how the stochastic gradient being related to the loss function can help. One option, according to [35], is that **Assumption 4**.: _For some constant \(\sigma>0\),_ \[\nabla f(\theta,\xi)=\nabla F(\theta)+\sqrt{\sigma F(\theta_{k})}Z_{\theta,\xi},\] (2.10) _with_ \[\mathbb{E}[Z_{\theta,\xi}]=0,\quad\mathbb{E}[|Z_{\theta,\xi}|^{2}]\leq 1.\] (2.11) Here \(\sqrt{\sigma F(\theta_{k})}Z_{\theta,\xi}\) is named as the machine learning noise, which scales with the function value. We refer to [35, Section 2.5] for many types of machine learning problems satisfying the assumption (2.10)-(2.11). A more relaxed and general version, considered in [11], is that there exists a monotonically increasing function \(\varrho:\mathbb{R}_{+}\to\mathbb{R}_{+}\) so that \[\mathbb{P}\big{(}|\nabla f(\theta,\xi)-\nabla F(\theta)|^{2}\geq t\varrho(F( \theta))\big{)}\leq e^{-t}.\] (2.12)

In this note, we will present the global convergence of SGD under the second type assumption (2.10)-(2.11). Moreover, we will discuss why convergence under assumptions (2.8)-(2.9) can fail for the local Lajasiewicz condition.

### Comparison to previous convergence results

Our motivation is in the same vein as [7]: we assume the local Lajasiewicz condition for the initialization so that the convergence result may apply to feedforward neural networks of bounded width and depth.

Several convergence results for SGD in non-convex optimization have been developed in recent years, and we list a few here and highlight their differences:

* [24]: Convergence to a local minima \(\theta^{*}\) that are Hurwicz regular, i.e., \(\nabla^{2}F(\theta^{*})\succ 0\). The key difference is that they assume that there exists \(a>0\) such that \(\langle\nabla F(\theta),\theta-\theta^{*}\rangle\geq a|\theta-\theta^{*}|^{2}\) for all \(\theta\) in a convex compact neighborhood of \(\theta^{*}\).
* [35]: It assumes that the Lajasiewicz condition holds in an \(\epsilon\)-sublevel set of \(F\). As a consequence, a convergence rate for \(F(\theta)\to 0\) is obtained, but the proof cannot track where the global minimizer \(x^{*}\) locates.

Similar to the result in [7] for gradient descents, we will show that under our assumptions (1-4) as in the setup, with some computable probability, stochastic iterates will convergence to the global minimum almost surely. We need to choose the initialization in a ball where (2.2) holds, and as a consequence, the global miminizer also lies in the same ball without assuming its existence a priori, similar to [7]. Compared to [35], our results is Euclidean as we can track the stochastic trajectories in the training.
Main result

Given the assumptions we describe in the previous section, we present the global convergence of SGD with a quantitative rate and a step-size bound. We point out that (2.10)-(2.11) assuming noise in SGD being proportional to the objective function play an important role here.

**Theorem 3.1**.: _We choose an initialization \(\theta_{0}\) with a radius \(R>1\) such that (2.2) holds. Let \(F\) be a loss function such that its gradient is Lipschitz continuous (2.3), and (2.5) holds for \(B(\theta_{0},R)\), Then for every \(\delta>0\), there exists \(\varepsilon>0\) such that if \(F(\theta_{0})\leq\varepsilon\), with probability at least \(1-\delta\), we have \(\theta_{k}\in B(\theta_{0},R-1)\) for all \(k\in\mathbb{N}\)._

_Conditioned on the event that \(\theta_{k}\in B(\theta_{0},R-1)\) for all \(k\in\mathbb{N}\), we have_

\[\lim_{k\to\infty}\beta^{k}F(\theta_{k})=0 \tag{3.1}\]

_almost surely for every \(\beta\in[1,\rho^{-1})\), where_

\[\rho=1-\eta\alpha+\frac{\eta^{2}}{2}C_{L}(2C_{L}+\sigma)\in(0,1), \tag{3.2}\]

_if the step size \(\eta\) satisfies \(0<\eta\leq\min\{\frac{1}{\alpha},\frac{\alpha}{4C_{L}(2C_{L}+\sigma)}\}\). Moreover, conditioned on the same event, \(\theta_{k}\) converges almost surely to a point \(\theta_{*}\) where \(F(\theta_{*})=0\)._

Proof.: We define the event where all the iterates up to \(k\)-th step stay in a ball \(B(\theta_{0},r)\):

\[E_{k}(r):=\bigcap_{j=0}^{k}\{|\theta_{j}-\theta_{0}|\leq r\}, \tag{3.3}\]

for some \(r\in(0,R]\) to be determined later. We denote \(\mathcal{F}_{k}\) as the filtration generated by \(\xi_{1},\cdots,\xi_{k-1}\). Take the interpolation \(\theta_{k+s}=\theta_{k}-s\eta\nabla f(\theta_{k},\xi_{k})\) for \(s\in[0,1]\), we have that

\[\begin{split} F(\theta_{k+1})&-F(\theta_{k})=\int_ {0}^{1}\frac{d}{ds}F\big{(}\theta_{k}-s\eta\nabla f(\theta_{k},\xi_{k})\big{)} ds\\ &=-\eta\int_{0}^{1}\nabla F(\theta_{k+s})\cdot\nabla f(\theta_{k},\xi_{k})ds\\ &=-\eta\int_{0}^{1}\nabla F(\theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})ds-\eta\int_{0}^{1}(\nabla F(\theta_{k+s})-\nabla F(\theta_{k})) \cdot\nabla f(\theta_{k},\xi_{k})ds\\ &\leq-\eta\nabla F(\theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})+ \eta C_{L}\int_{0}^{1}|\theta_{k+s}-\theta_{k}||\nabla f(\theta_{k},\xi_{k})| ds\\ &=-\eta\nabla F(\theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})+ \eta^{2}C_{L}\int_{0}^{1}s|\nabla f(\theta_{k},\xi_{k})|^{2}ds\\ &=-\eta\nabla F(\theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})+ \frac{\eta^{2}}{2}C_{L}|\nabla f(\theta_{k},\xi_{k})|^{2},\end{split} \tag{3.4}\]

and we apply the smoothness assumption (2.3) in the middle inequality. Rearrange terms and multiply with the indicate function on both sides, we have

\[F(\theta_{k+1})\mathbb{1}_{E_{k+1}(r)}\leq\Big{(}F(\theta_{k})-\eta\nabla F( \theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})+\frac{\eta^{2}}{2}C_{L}|\nabla f (\theta_{k},\xi_{k})|^{2}\Big{)}\mathbb{1}_{E_{k+1}(r)}. \tag{3.5}\]
Now we want to replace \(\mathbbm{1}_{E_{k+1}(r)}\) by \(\mathbbm{1}_{E_{k}(r)}\) on the right side. Note that \(\mathbbm{1}_{E_{k}(r)}\geq\mathbbm{1}_{E_{k+1}(r)}\), and moreover,

\[F(\theta_{k})-\eta\nabla F(\theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})+\frac{ \eta^{2}}{2}C_{L}|\nabla f(\theta_{k},\xi_{k})|^{2}\geq 0, \tag{3.6}\]

since the discriminant of this quadratic equation is \(|\nabla F(\theta_{k})|^{2}-2C_{L}F(\theta_{k})\leq 0\) by (2.4). We thus get

\[F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(r)}\leq\Big{(}F(\theta_{k})-\eta\nabla F( \theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})+\frac{\eta^{2}}{2}C_{L}|\nabla f( \theta_{k},\xi_{k})|^{2}\Big{)}\mathbbm{1}_{E_{k}(r)}. \tag{3.7}\]

We replace \(\nabla f\) above by the decomposition (2.10), that is \(\nabla f(\theta_{k},\xi_{k})=\nabla F(\theta_{k})+\sqrt{\sigma F(\theta_{k})} Z_{\theta,\xi}\), and use the bound (2.4) as well as the local Lajasiewicz condition (2.2). By taking the expectation we have that

\[\mathbb{E}[F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(r)}|\mathcal{F}_{k}]\leq\big{(} 1-\eta\alpha+\frac{\eta^{2}}{2}C_{L}(2C_{L}+\sigma)\big{)}F(\theta_{k}) \mathbbm{1}_{E_{k}(r)}. \tag{3.8}\]

We may choose a small step-size \(0<\eta^{*}\leq\min\{\frac{1}{\alpha},\frac{\alpha}{4C_{L}(2C_{L}+\sigma)}\}\), so that

\[\rho=1-\eta^{*}\alpha+\frac{\eta^{*2}}{2}C_{L}(2C_{L}+\sigma)\leq 1-\frac{ \alpha\eta^{*}}{2}\in(0,1).\]

With this, we obtain a contraction

\[\mathbb{E}[F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(r)}|\theta_{0}]\leq\rho\mathbb{ E}[F(\theta_{k})\mathbbm{1}_{E_{k}(r)}|\theta_{0}]\leq\rho^{k+1}F(\theta_{0}). \tag{3.9}\]

Based on the contraction of \(F\), we can nicely control the Euclidean distance between \(\theta_{k}\) and \(\theta_{0}\). Note that

\[\mathbb{E}[|(\theta_{k+1}-\theta_{k})\mathbbm{1}_{E_{k}(r)}|] =\eta^{*}\mathbb{E}[|\nabla f(\theta_{k},\xi_{k})\mathbbm{1}_{E_{ k}(r)}|]=\eta^{*}\mathbb{E}[|(\nabla F(\theta_{k})+\sqrt{\sigma F(\theta_{k})} Z_{\theta_{k},\xi_{k}})\mathbbm{1}_{E_{k}(r)}|]\] \[\leq\eta^{*}\sqrt{2C_{L}}\sqrt{\mathbb{E}[F(\theta_{k})\mathbbm{ 1}_{E_{k}(r)}]}+\eta^{*}\sqrt{\mathbb{E}[\sigma F(\theta_{k})\mathbbm{1}_{E_{ k}(r)}]}\sqrt{\mathbb{E}[|Z_{\theta_{k},\xi_{k}})|^{2}]} \tag{3.10}\] \[=(\sqrt{2C_{L}}+\sqrt{\sigma})\eta^{*}\rho^{k/2}F(\theta_{0}),\]

where we apply the Cauchy-Schwarz inequality, the growth bound (2.4), and (2.10-2.11). The total distance is thus finite

\[\mathbb{E}\Big{[}\sum_{k=0}^{\infty}|(\theta_{k+1}-\theta_{k})\mathbbm{1}_{E_ {k}(r)}|\Big{]}\leq\frac{(\sqrt{2C_{L}}+\sqrt{\sigma})\eta^{*}}{1-\sqrt{\rho}} F(\theta_{0})<\infty. \tag{3.11}\]

By the Markov's inequality, for any \(\tilde{\delta}\in(0,1)\), we have the length of trajectory bounded by

\[\sum_{k=0}^{\infty}|(\theta_{k+1}-\theta_{k})\mathbbm{1}_{E_{k}(r)}|\leq\frac {(\sqrt{2C_{L}}+\sqrt{\sigma})\eta^{*}}{(1-\sqrt{\rho})\tilde{\delta}}F( \theta_{0}), \tag{3.12}\]

with probability at least \(1-\tilde{\delta}\). This means that as long as the local Lajasiewicz condition holds, the stochastic iterates will converge to a point with high probability. What remains to show that there exists a positive probability for

\[E_{\infty}(r):=\bigcap_{j=0}^{\infty}\{|\theta_{j}-\theta_{0}|\leq r\} \tag{3.13}\]

to occur. In fact, we can set \(r=R-1\) and argue that there exists a positive probability that all stochastic iterates are trapped in the ball \(B(\theta_{0},R-1)\). Let us consider the following two cases:
* Utilizing (3.10), the chance for the next iterate to escape the ball \(B(\theta_{0},R)\) is \[\begin{split}\mathbb{P}\big{(}E_{k}(R-1)&\text{ occurs but }\theta_{k+1}\in B^{c}(\theta_{0},R)\big{)}\leq\mathbb{P}(|\theta_{k+1}-\theta_{k}| \mathbbm{1}_{E_{k}(R-1)}\geq 1)\\ &\leq\mathbb{E}[|\theta_{k+1}-\theta_{k}|\mathbbm{1}_{E_{k}(R-1)} ]\leq(\sqrt{2C_{L}}+\sqrt{\sigma})\eta^{*}\rho^{k/2}F(\theta_{0}).\end{split}\] (3.14)
* Utilizing (2.5), the chance for the next iterate to enter the annulus \(B(\theta_{0},R)\setminus B(\theta_{0},R-1)\) is \[\begin{split}\mathbb{P}\big{(}E_{k}(R-1)&\text{ occurs but }\theta_{k+1}\in B(\theta_{0},R)\setminus B(\theta_{0},R-1)\big{)}\\ &\leq\mathbb{P}(F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(R)}\geq M_{0 })\leq\frac{\mathbb{E}[F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(R)}]}{M_{0}}\leq \frac{\rho^{k+1}F(\theta_{0})}{M_{0}}.\end{split}\] (3.15)

We are ready to conclude, note that the event defined in (3.3) over radius \(r=R-1\) is monotonically decreasing,

\[E_{k+1}(R-1)\subseteq E_{k}(R-1). \tag{3.16}\]

Let us define

\[\tilde{E}_{k+1}(R-1):=E_{k}(R-1)\setminus E_{k+1}(R-1), \tag{3.17}\]

whose probability is indeed the summation of (3.14) and (3.15)

\[\mathbb{P}(\tilde{E}_{k+1}(R-1))\leq F(\theta_{0})\Big{(}(\sqrt{2C_{L}}+\sqrt {\sigma})\eta^{*}\rho^{k/2}+\frac{\rho^{k+1}}{M_{0}}\Big{)}. \tag{3.18}\]

The probability of the complementary event can be bounded,

\[\mathbb{P}(E_{k}^{c}(R-1))=\sum_{i=1}^{k}\mathbb{P}(\tilde{E}_{i}(R-1))<F( \theta_{0})\Big{(}(\sqrt{2C_{L}}+\sqrt{\sigma})\frac{\eta^{*}\sqrt{\rho}}{1- \sqrt{\rho}}+\frac{\rho^{2}}{M_{0}(1-\rho)}\Big{)} \tag{3.19}\]

for any \(k\in\mathbb{N}\). Thus for every \(0<\delta<1\), there exists \(\varepsilon>0\) depending on \(C_{L},\sigma,\eta^{*},\rho\) and \(M_{0}\), such that if \(F(\theta_{0})\leq\varepsilon\), then

\[\mathbb{P}(E_{k}(R-1))\geq 1-\delta \tag{3.20}\]

for all \(k\in\mathbb{N}\). Taking \(k\to\infty\), we then have \(\mathbb{P}(E_{\infty}(R-1))\geq 1-\delta\).

Conditioned on the event \(E_{\infty}(R-1)\), we can conclude from (3.9) that for every \(\beta\in[1,\rho^{-1})\),

\[\lim_{k\to\infty}\beta^{k}F(\theta_{k})=0 \tag{3.21}\]

almost surely. Moreover, for all \(1\leq j<k\), by (3.10),

\[\begin{split}\mathbb{E}[|\theta_{k}-\theta_{j}|\mathbbm{1}_{E_{ \infty}(R-1)}]&\leq\sum_{i=j}^{k-1}\mathbb{E}[|\theta_{i+1}- \theta_{i}|\mathbbm{1}_{E_{\infty}(R-1)}]\leq\sum_{i=j}^{k-1}\mathbb{E}[| \theta_{i+1}-\theta_{i}|\mathbbm{1}_{E_{i}(R-1)}]\\ &\leq\sum_{i=j}^{k-1}(\sqrt{2C_{L}}+\sqrt{\sigma})\eta^{*}\rho^{ i/2}F(\theta_{0})<(\sqrt{2C_{L}}+\sqrt{\sigma})\eta^{*}F(\theta_{0})\frac{\rho^{j/2}}{1- \sqrt{\rho}}.\end{split} \tag{3.22}\]

As \(j\to\infty\), this bound goes to zero. Thus \(\{\theta_{k}\}_{k\geq 0}\) from a Cauchy sequence conditioned on \(E_{\infty}(R-1)\), and

\[\theta_{k}\to\theta_{*}\in B(\theta_{0},R-1),\quad\text{as }k\to\infty.\]

By (3.9), we see that \(F(\theta_{*})=0\) conditioned on \(E_{\infty}(R-1)\). We also know that with probability at least \(1-\delta\), \(\theta_{k}\in B(\theta_{0},R-1)\) for all \(k\in\mathbb{N}\). Therefore, we can conclude that with probability at least \(1-\delta\), \(\theta_{k}\) converges to a global minimizer \(\theta_{*}\in B(\theta_{0},R-1)\)
Non-convergence with bounded noises

One may wonder if the machine learning noise is relaxed by only assuming the boundedness (2.9), whether it can be shown that SGD iterates still converge inside \(B(\theta_{0},r)\) for some radius \(r>0\). As a companion of bounded noises, we should consider to take a Robbins-Monro type adaptive step sizes

\[\eta_{k}=\frac{\gamma}{(k+n_{0})^{q}},\ \ \ \ q\in(1/2,1] \tag{4.1}\]

for SGD (1.2), with constants \(\gamma,n_{0}>0\) to be chosen.

If all the stochastic iterates \(\theta_{k}\) stay inside the ball where the local Lajasiewicz condition (2.2) holds, then we show in Lemma 4.2 that the convergence happens with an algebraic rate. Lemma 4.2 relies on classical results in numerical sequences, which can be traced back to [9].

**Lemma 4.1** ([9], Lemma 1 and Lemma 4).: _Let \(\{b_{k}\}_{k\geq 1}\) be a non-negative sequence such that_

\[b_{k+1}\leq\Big{(}1-\frac{C_{1}}{(k+n_{0})^{q}}\Big{)}b_{k}+\frac{C_{2}}{(k+n_{ 0})^{q+p}}, \tag{4.2}\]

_where \(q\in(0,1]\), \(p>0\) and \(C_{1},C_{2}>0\), then_

1. _if_ \(q=1\) _and_ \(C_{1}>p\)_, we have_ \[b_{k}\leq\frac{C_{2}}{C_{1}-p}\frac{1}{k}+o\Big{(}\frac{1}{k}\Big{)};\] (4.3)
2. _if_ \(q<1\)_, we have_ \[b_{k}\leq\frac{C_{2}}{C_{1}}\frac{1}{k^{p}}+o\Big{(}\frac{1}{k^{p}}\Big{)}.\] (4.4)

In the proof of Lemma 4.2, an iteration inequality of the form (4.2) will show up after we apply the local Lajasiewicz condition (2.2), set up suitable \(n_{0}\), and use the boundedness of the noise (2.9). The power \(q\) comes from (4.1), and the extra power \(p\) comes from \(\eta_{k}^{2}\).

**Lemma 4.2**.: _Given a radius \(r>0\) where (2.2) holds. Assume that the noise term in (2.6) satisfies (2.9), and the SGD iterates are updated with adaptive step sizes \(\eta_{k}=\frac{\gamma}{(k+n_{0})^{q}},1/2<q\leq 1\)._

_Conditioned on the event that \(\theta_{k}\in B(\theta_{0},r)\) for all \(k\in\mathbb{N}\), then for \(n_{0}\geq\Big{(}\frac{2C_{L}^{2}\gamma}{\alpha}\Big{)}^{1/q}\), we have the convergence_

\[\mathbb{E}[F(\theta_{k})]\leq\begin{cases}\frac{\gamma^{2}c^{2}C_{L}}{\alpha \gamma-2}\frac{1}{k}+o\Big{(}\frac{1}{k}\Big{)},&\text{ if }q=1\text{ and }\gamma>2/\alpha\\ \frac{\gamma^{2}c^{2}C_{L}}{\alpha\gamma}\frac{1}{k^{q}}+o\Big{(}\frac{1}{k^ {q}}\Big{)},&\text{ if }1/2<q<1.\end{cases} \tag{4.5}\]

Proof.: We consider the same event as before

\[E_{k}(r):=\bigcap_{j=0}^{k}\{|\theta_{j}-\theta_{0}|\leq r\}, \tag{4.6}\]

for some \(0<r\leq R\). Taking similar beginning steps as in Theorem 3.1, we arrive to the same inequality as (3.7).

\[F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(r)}\leq\Big{(}F(\theta_{k})-\eta_{k} \nabla F(\theta_{k})\cdot\nabla f(\theta_{k},\xi_{k})+\frac{\eta_{k}^{2}}{2} C_{L}|\nabla f(\theta_{k},\xi_{k})|^{2}\Big{)}\mathbbm{1}_{E_{k}(r)}. \tag{4.7}\]
By inserting \(\nabla f(\theta,\xi)=\nabla F(\theta)+Z(\theta,\xi)\), we expand the right side to be

\[F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(r)}\] \[\leq\Big{(}F(\theta_{k})-\eta_{k}|\nabla F(\theta_{k})|^{2}+(\eta_ {k}^{2}C_{L}-\eta_{k})\nabla F(\theta_{k})\cdot Z(\theta_{k},\xi_{k})+\frac{ \eta_{k}^{2}}{2}C_{L}(|\nabla F(\theta_{k},\xi_{k})|^{2}+|Z(\theta_{k},\xi_{ k})|^{2})\Big{)}\mathbbm{1}_{E_{k}(r)} \tag{4.8}\]

Because \(Z(\theta_{k},\xi_{k})\) has zero mean and its second moment is bounded by \(c^{2}\) (2.9), in addition with (2.4), by taking the expectation we have that

\[\mathbb{E}[F(\theta_{k+1})\mathbbm{1}_{E_{k+1}(r)}|\theta_{0}]\leq\Big{(}1- \alpha\eta_{k}+\eta_{k}^{2}C_{L}^{2}\Big{)}\mathbb{E}[F(\theta_{k})\mathbbm{1 }_{E_{k}(r)}|\theta_{0}]+\frac{\eta_{k}^{2}c^{2}C_{L}}{2}. \tag{4.9}\]

We may view \(\mathbb{E}[F(\theta_{k})\mathbbm{1}_{E_{k}(r)}|\theta_{0}]\) as \(b_{k}\) in (4.2). We may set \(n_{0}\) to satisfy

\[n_{0}\geq\Big{(}\frac{2C_{L}^{2}\gamma}{\alpha}\Big{)}^{1/q}, \tag{4.10}\]

so that

\[1-\alpha\eta_{k}+\eta_{k}^{2}C_{L}^{2}\leq 1-\frac{\alpha\eta_{k}}{2}=1-\frac{ \alpha\gamma}{2(k+n_{0})^{q}}. \tag{4.11}\]

Note that the higher order term in (4.9 has the expression

\[\frac{\eta_{k}^{2}c^{2}C_{L}}{2}=\frac{\gamma^{2}c^{2}C_{L}}{2(k+n_{0})^{2q}}. \tag{4.12}\]

Thus, we apply Lemma 4.1 and obtain the convergence

1. if \(q=1\), we set \(\gamma>\frac{2}{\alpha}\) so that \[\mathbb{E}[F(\theta_{k})\mathbbm{1}_{E_{k}(r)}|\theta_{0}]\leq\frac{\gamma^{2 }c^{2}C_{L}}{\alpha\gamma-2}\frac{1}{k}+o\Big{(}\frac{1}{k}\Big{)};\] (4.13)
2. if \(1/2<q<1\), we have \[\mathbb{E}[F(\theta_{k})\mathbbm{1}_{E_{k}(r)}|\theta_{0}]\leq\frac{\gamma^{2 }c^{2}C_{L}}{\alpha\gamma}\frac{1}{k^{q}}+o\Big{(}\frac{1}{k^{q}}\Big{)}.\] (4.14)

**Remark 4.3**.: _Compared with the proof of Theorem 3.1, the decay rate (4.5) of \(F(\theta_{k})\) is not enough to ensure that \(E_{\infty}(r)\) happens with a positive probability. In fact, we need both probabilities in (3.14) and (3.15) to be summable._

_In [24], the authors assume a local convexity in a convex neighborhood \(\mathcal{K}\) of a local minimizer \(x^{*}\), so that there exists \(0<\alpha<\beta<\infty\) and_

\[\alpha|x-x^{*}|^{2}\leq\nabla F(x)^{\top}(x-x^{*})\leq\beta|x-x^{*}|^{2},\quad \text{for all }x\in\mathcal{K}.\]

_This ensures a strong contraction of \(|x_{k}-x^{*}|^{2}\) through iterations. Just with bounded noises, they can show \(\{x_{k}\}\) stays inside the neighborhood \(\mathcal{K}\) with a positive probability under Ronbin-Monro step sizes. Unfortunately, the local Lajasiewicz condition (2.2) we assume here is not sufficient to guarantee such a contraction._
In fact, we can show that the boundedness of noises is not enough to guarantee that iterates stay inside a ball all the time under the local Lajasiewicz condition (2.2). Let us present a negative result in the following. By constructing identically independent random variables \(Z(\theta_{k},\xi)\equiv Z_{k}\) such that \(\mathbb{E}[Z_{k}]=0\) and \(\mathbb{E}[|Z_{k}|]=\bar{m}>0\) for \(k\in\mathbb{N}\), it turns out that under adaptive step sizes (4.1), iterates will escape the ball \(B(\theta_{0},r)\) almost surely.

**Lemma 4.4**.: _Consider the following stochastic gradient iteration_

\[\theta_{k+1}=\theta_{k}-\eta_{k}(\nabla F(\theta_{k})+Z_{k}), \tag{4.15}\]

_where \(\eta_{k}=\frac{\gamma}{(k+n_{0})^{q}},1/2<q\leq 1\), \(n_{0}\geq\left(\frac{2C_{L}^{2}\gamma}{\alpha}\right)^{1/q}\) and \(\gamma>2/\alpha\) as in Lemma 4.2. We assume that \(Z_{k}\) are i.i.d. with \(\mathbb{E}[Z_{k}]=0,\mathbb{E}[|Z_{k}|]=\bar{m}\) for some \(\bar{m}>0\), and \(\mathbb{E}[|Z_{k}|^{2}]\leq c^{2}\) for some \(c>0\). Then, given a radius \(r>0\) such that (2.2) holds, \(\{\theta_{k}\}_{k\geq 0}\) will exit the ball \(B(\theta_{0},r)\) almost surely._

Proof.: We argue by contradiction. Suppose all iterates from (4.15) stay inside the ball \(B(x_{0},r)\), we aim to prove that \(\lim_{n\to\infty}\sum_{k=0}^{n}|\theta_{k+1}-\theta_{k}|=\infty\) almost surely. For any \(n\geq 1\), we have

\[\begin{split}\sum_{k=0}^{n}|\theta_{k+1}-\theta_{k}|& =\sum_{k=0}^{n}\eta_{k}|\nabla F(\theta_{k})+Z_{k}|\geq\sum_{k=0} ^{n}\frac{\gamma}{k+n_{0}}|\nabla F(\theta_{k})+Z_{k}|\\ &\geq\tilde{c}\sum_{k=1}^{n}\frac{1}{k}|\nabla F(\theta_{k})+Z_{ k}|\geq\tilde{c}\Big{(}\sum_{k=1}^{n}\frac{1}{k}|Z_{k}|-\sum_{k=1}^{n}\frac{1}{k}| \nabla F(\theta_{k})|\Big{)},\end{split} \tag{4.16}\]

where the second inequality can be satisfied if we choose \(\tilde{c}\in(0,\frac{\gamma}{n_{0}+1})\). We claim that

\[\sum_{k=1}^{n}\frac{1}{k}|Z_{k}|\to\infty,\quad\text{as $n\to\infty$ \ almost surely}. \tag{4.17}\]

If not, say there exists a finite number \(\mu>0\) such that \(\lim_{n\to\infty}\sum_{k=1}^{n}\frac{1}{k}|Z_{k}|=\mu\), the Cesaro mean theorem implies that the Cesaro average also converges to the same limit,

\[\frac{1}{n}\sum_{j=1}^{n}\Big{(}\sum_{k=1}^{j}\frac{1}{k}|Z_{k}|\Big{)}\to\mu,\quad\text{as $n\to\infty$ \ almost surely}. \tag{4.18}\]

On the other hand,

\[\begin{split}\frac{1}{n}\sum_{j=1}^{n}\Big{(}\sum_{k=1}^{j}\frac {1}{k}|Z_{k}|\Big{)}&=\frac{1}{n}\sum_{k=1}^{n}\Big{(}\sum_{j=k} ^{n}\frac{1}{k}|Z_{k}|\Big{)}=\frac{1}{n}\sum_{k=1}^{n}\frac{n+1-k}{k}|Z_{k}| \\ &=\sum_{k=1}^{n}\frac{1}{k}|Z_{k}|+\frac{1}{n}\sum_{k=1}^{n}\frac {1}{k}|Z_{k}|-\frac{1}{n}\sum_{k=1}^{n}|Z_{k}|,\end{split} \tag{4.19}\]

which implies that as \(n\to\infty\), \(\frac{1}{n}\sum_{k=1}^{n}|Z_{k}|\to 0\) almost surely. But by the law of large number and the construction of \(Z_{k}\), \(\frac{1}{n}\sum_{k=1}^{n}|Z_{k}|\to\bar{m}\neq 0\), we get the contradiction. Thus (4.17) is proved.

Due to (4.5) in Lemma 4.2, we have that \(\lim_{n\to\infty}\sum_{k=1}^{n}\frac{1}{k}|\nabla F(\theta_{k})|\leq\lim_{n \to\infty}\sum_{k=1}^{n}\frac{\sqrt{2C_{L}}}{k}\sqrt{F(\theta_{k})}<\infty\) almost surely. With (4.17), we deduce from (4.16) that \(\lim_{n\to\infty}\sum_{k=0}^{n}|\theta_{k+1}-\theta_{k}|=\infty\) almost surely.

However, this statement cannot happen if all iterates stay inside the ball, because by Lemma 4.2, \(F(\theta_{k})\) converges. By a stopping criterion, it implies that \(\sum_{k=0}^{n}|\theta_{k+1}-\theta_{k}|<\infty\). The infinite sum tells that the SGD iterates will exit the ball almost surely.
### Acknowledgement

The work of JL is supported in part by National Science Foundation via grant DMS-2012286.

## Appendix A Appendix

In [7], Chatterjee provides a feedforward neural network that satisfies the local Lajasiewicz condition (2.2). The purpose of this appendix is to show that this feedforward neural network construction satisfies Assumption 3 (2.5) as well.

The object function that [7] considers is the squared error loss. For the dateset \(\{(x_{i},y_{i})\}_{i=1}^{n}\), we consider

\[F(\theta):=\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\varphi(x_{i},\theta))^{2}.\] (A.1)

Here, \(\varphi(x,\theta)\) is the neural network writes as

\[\varphi(x,\theta):=\tilde{\sigma}_{L}(W_{L}\tilde{\sigma}_{L-1}(\cdots(W_{2} \tilde{\sigma}_{1}(W_{1}x+b_{1})+b_{2})\cdots)+b_{L}),\] (A.2)

with \(\tilde{\sigma}_{1}\cdots,\tilde{\sigma}_{L}\) being activation functions acting componentwisely, and \(W_{l}\in\mathbb{R}^{d_{l}\times d_{l-1}},d_{0}=d,d_{L}=1,b_{l}\in\mathbb{R}^{l}\) for \(1\leq l\leq L\). The parameter to be trained is

\[\theta=(W_{1},b_{1},W_{2},b_{2},\cdots W_{L},b_{L}),\] (A.3)

and it can be viewed as a vector \(\mathbb{R}^{p}\) with \(p=\sum_{l=1}^{L}d_{l}(d_{l-1}+1)\).

Let us follow the setups in Theorem 2.1 in [7] and state our result.

**Theorem A.1**.: _We consider the squared error loss (A.1) with a feedforward neural network (A.2), with depth \(L\geq 2\), \(d_{L}=1\) and \(\tilde{\sigma}_{L}=\) identity. Suppose for \(0\leq l\leq L-1\), the activation functions \(\tilde{\sigma}_{l}\in C^{2},\tilde{\sigma}_{l}(0)=0\), and \(c_{l}:=\min_{x}\tilde{\sigma}_{l}^{\prime}(x)>0\). Suppose the input data \(x_{1},\cdots,x_{n}\in\mathbb{R}^{d}\) are linearly independent, and let \(\lambda_{0}\) be the minimum eigenvalue of \(\frac{1}{n}X^{\top}X\), with the matrix \(X=(x_{1},\cdots x_{n})\in\mathbb{R}^{d\times n}\) formed by column vectors \(x_{i}\)'s. We can initialize \(\theta_{0}=(W_{1},b_{1},W_{2},b_{2},\cdots W_{L},b_{L})\) such that \(b_{l}=0\) for all \(1\leq l\leq L\), \(W_{1}=0\), and the entries of \(W_{2},\cdots,W_{L}\) are all strictly positive. In addition, let \(R>0\) be the minimum value of the entries of \(W_{2},\cdots,W_{L-1}\), and \(A>R>0\) be the minimum value of the entries of \(W_{L}\), we have the following lower bound:_

\[F(\theta)\geq\frac{\lambda_{0}}{2n}(A-R)^{2}R^{2L-4}(d_{L-1}d_{L-2}\cdots d_{ 2}c_{L-1}c_{L-2}\cdots c_{1})^{2}d_{1}|\theta-\theta_{0}|^{2}-\frac{1}{n}\sum _{i=1}^{n}y_{i}^{2}.\] (A.4)

Proof.: Let us define

\[\varphi_{1}(x,\theta)=\tilde{\sigma}_{1}(W_{1}x+b_{1})\] (A.5)

and for \(2\leq l\leq L\),

\[\varphi_{l}(x,\theta)=\tilde{\sigma}_{l}(W_{l}\tilde{\sigma}_{L-1}(\cdots(W_{ 2}\tilde{\sigma}_{1}(W_{1}x+b_{1})+b_{2})\cdots)+b_{l}).\] (A.6)

Following the computations in [7], we have that, the partial derivative of \(\varphi_{l}\) with respect to \((i,j)\) entry of \(W_{1}\) is

\[\partial_{ij}\varphi_{l}(x,\theta)=x_{j}q_{i}(x,\theta):=x_{j}W_{L}D_{L-1}(x, \theta)W_{L-1}\cdots W_{2}D_{1}(x,\theta)e_{i},\] (A.7)

where \(D_{l}(x,\theta)\in\mathbb{R}^{d_{l}\times d_{l}}\) is a diagonal matrix with diagonal entries filled by \(\tilde{\sigma}_{l}^{\prime}(W_{l}\varphi_{l-1}(x,\theta)+b_{l})\), and \(e_{i}\in\mathbb{R}^{d_{1}}\) is the \(i\)-th unit vector.
Let \(\theta_{0}\) be the starting vector where the entries of \(W_{2},\cdots W_{L-1}\) are all strictly positive, and \(b_{1},\cdots,b_{L}\) and \(W_{1}\) be zero, then one can find \(\varphi(x,\theta_{0})=0\) for each \(x\). Thus \(F(\theta_{0})=\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}\). Using the Young's inequality and the Cauchy-Schwarz inequality, the loss function can be rewritten as

\[\begin{split} F(\theta)&\geq\frac{1}{n}\sum_{i=1}^ {n}\left(y_{i}^{2}+\varphi(x_{i},\theta)^{2}-2|\varphi(x_{i},\theta)||y_{i}| \right)\\ &\geq\frac{1}{2n}\sum_{i=1}^{n}\varphi(x_{i},\theta)^{2}-\frac{1 }{n}\sum_{i=1}^{n}y_{i}^{2}\geq\frac{1}{2n^{2}}\Big{(}\sum_{i=1}^{n}\varphi(x_ {i},\theta)\Big{)}^{2}-\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}.\end{split}\] (A.8)

Moreover, by mean value theorem, we can find some \(\tilde{\theta}=(\tilde{W}_{1},\tilde{b}_{1},\tilde{W}_{2},\tilde{b}_{2}, \cdots\tilde{W}_{L},\tilde{b}_{L})\) between \(\theta\) and \(\theta_{0}\) such that

\[\Big{(}\sum_{i=1}^{n}\varphi(x_{i},\theta)\Big{)}^{2}=\Big{(}\sum_{i=1}^{n} \partial_{\theta}\varphi(x_{i},\tilde{\theta})^{\top}(\theta-\theta_{0})\Big{)} ^{2}=\sum_{i,j=1}^{n}(\theta-\theta_{0})^{\top}H_{ij}(\tilde{\theta})(\theta- \theta_{0}),\] (A.9)

where \(H_{ij}(\tilde{\theta})=\partial_{\theta}\varphi(x_{i},\tilde{\theta})\cdot \partial_{\theta}\varphi(x_{j},\tilde{\theta})\). We can bound \(\sum_{i,j=1}^{n}H_{ij}(\tilde{\theta})\) from below by the minimum eigenvalue \(\lambda(\tilde{\theta})\). Note that \(\lambda_{0}\) is the minimum eigenvalue of \(\frac{1}{n}X^{\top}X\). As \(A>R\) is a lower bound on the entries of \(W_{L}\), We have that the entries of \(\tilde{W}_{L}\) are bounded below by \(A-R\), with \(c_{l}:=\min_{u}\tilde{\sigma}_{l}^{\prime}(u)>0\), we deduce that

\[\lambda(\tilde{\theta})\geq n\lambda_{0}(A-R)^{2}R^{2L-4}(d_{L-1}d_{L-2}\cdots d _{2}c_{L-1}c_{L-2}\cdots c_{1})^{2}d_{1}.\] (A.10)

Therefore, we bound \(F(\theta)\) by

\[F(\theta)\geq\frac{\lambda_{0}}{2n}(A-R)^{2}R^{2L-4}(d_{L-1}d_{L-2}\cdots d_{2 }c_{L-1}c_{L-2}\cdots c_{1})^{2}d_{1}|\theta-\theta_{0}|^{2}-\frac{1}{n}\sum_{ i=1}^{n}y_{i}^{2}.\] (A.11)

From the lower bound estimate above, if \(R\) is large enough compared with \(\sum_{i=1}^{n}y_{i}^{2}\), we can find \(M_{0}>0\) such that \(F(\theta)\geq M_{0}\) for \(R-1\leq|\theta-\theta_{0}|\leq R\).
