On the convergence of SGD under the over-parameter setting
Authors: ruinan Jin
Yiwei Wang
Wei Liu
Baoxiang Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: SGD
over-parameter
almost surely convergence
global optimum convergence

Abstract: With the improvement of computing power, over-parameterized models get increasingly popular in machine learning. This type of model is usually with a complicated, non-smooth, and non-convex loss function landscape. However, when we train the model, simply using the first-order optimization algorithm like stochastic gradient descent (SGD) could acquire some good results, in both training and testing, albeit that SGD is known to not guarantee convergence for non-smooth and non-convex cases. Theoretically, it was previously proved that in training, SGD converges to the global optimum with probability $1 - \epsilon$, but only for certain models and $\epsilon$ depends on the model complexity. It was also observed that SGD tends to choose a flat minimum, which preserves its training performance in testing. In this paper, we first prove that SGD could iterate to the global optimum almost surely under arbitrary initial value and some mild assumptions on the loss function. Then, we prove that if the learning rate is larger than a value depending on the structure of a global minimum, the probability of converging to this global optimum is zero. Finally, we acquire the asymptotic convergence rate based on the local structure of the global optimum. 

Under review as a conference paper at ICLR 2023
ON THE CONVERGENCE OF SGD UNDER THE OVER- PARAMETER SETTING
Anonymous authors Paper under double-bling review
ABSTRACT
With the improvement of computing power, over- werrparameterized models get in- creasingly popular in machine learning. This type of model is usually with complicated, non-smooth, and non-convex loss function landscape. However, when we train the model, simply using the first-order optimization algorithm like stochastic gradient descent (SGD) could acquire some good results, in both train- ing and testing, albeit that SGD known not guarantee convergence for non- smooth and non-convex cases. Theoretically, it was previously proved that in training, SGD converges to the global optimum with probability for certain models and depends on the model complexity. It was also observed that SGD tends to choose flat minimum, which preserves its training perfor- mance in testing. In this paper, we first prove that SGD could iterate to the global optimum almost surely under arbitrary initial value and some mild assumptions the loss function. Then, prove that if the learning rate is larger than value depending on the structure this global optimum is zero. Finally, acquire the asymptotic convergence rate based on the local structure of the global optimum.
c. but only
global minimum, the probability of converging to
INTRODUCTION
With the improvement of the computing power of computer hardware, increasing number of wver-parameterized models are deployed in the domain of machine learning. One of the most repre- sentative and successful models is what we called deep neural network (LeCun et al. (201)): :): Amodei jet al. (2013): Graves et al. (213); ; He et al.] (2016) Silver et al. (2017). which has achieved great empirical success in various application
(Wu al. (2016); Krizhevsky al.) (2017); : Silver et al. (2017); Halla et al. (2022)). Meanwhile, deep neural networks are large in scale and have an optimization landscape that in general non-smooth and non-convex (Wu et al. 2019 Brutzkus & Globerson 2017). Training such a model should have been concerning. However, people could usually acquire very good results just through using first-order methods such as stochastic gradient descent (SGD). A large theoretical gap persists in understanding this process. Two main questions arise.
Due to the over-parametrization and the highly complex loss landscape of deep neural networks, optimizing the deep networks to the global optimum is likely NP-hard (Brutzkus & Globerson 2017 Blum & Rivest 1992). Nevertheless, in practice, simple first-order methods, which does not have convergence guarantee in the non-smooth and non-convex case (Liu et al.] 2022a b). are capable of
finding a global optimum. This happens even more often on the training data (Zhang et al.) 2021 Brutzkus & Globerson| 2017, Wu et al. 2019). It has been open problem (Goodfelllw et al. 2014) that, in this case, does SGD provably find the global optimum? Does the result generalize to more general model structures beyond neural networks?
2. In general, prremerraetriized models offer many global optimums. These global optimums have the same training loss of zero, and meanwhile drastically different test performance (Wu et al. 2018 Feng & Tu. 2021). Interestingly, studies find that SGD tends to converge to those generalizable ones (Zhang et al. 2021). In fact, it is observed empirically that SGD could usually find flat minima, which subsequently enjoys better generalization (Kramers) 1940; Dziugaite & Roy| 2017; Arpit eet al. 2017 Kleinberg et al. 2018 Hochreiter Schmidhuber 1997 1994). Why and how does SGD find flat global minimum? The empirical finding has yet to be theoretically validated.

---

Under review as a conference paper at ICLR 2023
Related Works For the first question, in recent years, there have been number of theoretical results that target to explain this phenomenon. Many of them focus on concrete neural network
models, like two-layer networks with linear active function (Bartlett et al. 2018 Hardt & Ma 2016).
Several works need the inputs to be random Gaussian variables (Gie et al. 2018 Tian, 2017 Du et al., 2017] Zhong al. 2017). Authors in Wu et al.] (2019); Allen-Zhu et al, (019)) consider the non-smooth case, but its techniques is depending on the structure of the network. They prove when the number of nodes is enough large, the objective is "almost convex" and "semi-smooth". The techniques unfortunately do not generalize to more general models. Another commonly used technique is to ignore the non-smoothness and apply the chain rule anyway on the smoth points (Bartlett et al. 2018). The derivation does provide some intuitions but they do not offer any rigorous guarantees, as the chain nule does not hold (Liu et al. 2202aa b). Even with these kinds of restrictions, existing works (Ge et al. 2018: Tian 2017: Du et al. |017 Bartlett et al. [2018) Vaswani ct al. 2019: Chizat & Bach 2018) only manage to find a high probability convergence result to the global optimum. The difference between this probability and I could depend on the structure of the model, like the number of nodes in the neural network, which raises further concerns on the tightness of the probability bound. It is currently lacking to analyze SGD for general models to obtain an almost surely convergence to the global optimum.
For the second question, most works investigate the flat minima in qualitative way. A recent work is by Xie et al. (2020), which views the SGD) process as a stochastic differential equation (SDE), and uses SDE to describe the process of the iteration escaping from the sharp minimum. Similar techniques are also used in the works by Wu et al. (2019) Feng & Tu (202I). Unfortunately, SGD can be viewed as an SDE only when the learning rate is suffeinntly small, and for normal learning rate trajectories formed by SGD and SDE could be arbitrarily different. Another technique used to / study this problem is to use the linear stability (Wu al. 2018 Feng & Tu 202T), which considers a linear system near global minimum. The behavior of SGD near some global minimum can then be characterized by the linear system of this global minimum. However, different from a deterministic system where the property near one point can be quantitative determine by the linearized system of this point, a stochastic system property near one point is determined by all points in Rd. Using this linearized function to fully represent SGD near some global minimum is thus not a rigorous argument.
Contributions
1. Under several mild assumptions about the non-smooth and non-convex loss function, we provide the first proof that from an arbitrary initialization SGD could make the iteration converge to the global optimum almost surely, i.e., P(e,, converges to global optimum) = 1.
2. Under the same set of assumptions and the same setting of SGD, we prove that if the learning rate is larger than a threshold, which depends on the sharpness of a global minimum, the probability which the iteration converges to this global optimum is strictly 0.
With similar assumptions and the same setting, we acquire the asymptotic convergence rate of the iteration converging to the global optimum. By this result, we know that SGD achieves an arbitrary accuracy in polynomial time.
Technical Insight The basic intuition is as follows. We first understand the SGD as a Markov chain with the continuous state space. Then we aim prove that the global optimum is the only absorbing state of this Markov chain. Concretely, due to the property of the sampling noise, this noise enjoys 0 variance when the optimization variable / reaches the global optimum (Claim 2.1), i.c., Eg. g (.. V 12 (notations are defined in the next section), which guarantees that once f, reaches the global optimum, it will not escape from the optimum. Meanwhile, in other local optimums, the positive variance makes 0, jump out to this local optimum. Otherwise, as this Markov chain is continuous state space Markov chain, an absorbing state with the measure 0 cannot become the real absorbing state (the probability of the 0,, reaching this absorbing state in every epoch is 0). Based on this, we need this absorbing state to have flat-enough neighborhood (Assumption 2.2 in the new version), which deduces that 6, that fall on this neighborhood tend to move closer to this absorbing state. Combining this absorbing state and this neighborhood statement, can prove the distribution of 6, will concentrate on the global optimum when as the iteration goes. Finally, this distribution will degenerate to the global optimum, that is, O₂ will converge the global optimum.
2

---

Under review as a conference paper at ICLR 2023
This neighborhood is the key insight of proving the convergence of SGD. The neighborhood cannot be very sharp (have at most quadratic growth), which is the reason we made Assumption 2.2, item 1. It is actually reflected in Equation (8). A flat enough neighborhood the third term (8) negative, which in turn makes the R(O,) (the Lyapunov function) to decrease with high probability (0,, close global optimum). Otherwise, if the neighborhood is sharp, this coefficient will become positive, which makes R(O,) increasing (0,, away from global optimum).
make the coefficient of
2 PROBLEM FORMULATION
We investigate SGD under the over parametrization setting, under few mild assumptions on the objective function. The setting and the assumptions, as well as some preliminaries that are relevant to the results, are provided in Section 2.1 We then present the sampling schemes in Section 2.2
2.1 OPTIMIZATION UNDER OVER- PAEERPRRAMETIIZATIONN
In this paper, given a dataset D = {( vill 24, E R we consider a model i f;), and the mean--quare error (MSE) loss, i.e.
N Σ ( = N
x;) = (f(0, - yy))²
(1)
The goal of an optimization method, like SGD, is to obtain an optimum E J', where J arg mineer (0).
In the over-paramen wer-parametrrizttonn setting, this optimum is zero. To handle the non-smoothness, we recall
the definition of Clarke subdifferential (Clarke 1990), which is important tool to design and operate SGD algorithms.
Definition (Clarke subdifferential (Clarke 1990 Let T E Ω be given. The Clarke subdifferential of f at & is defined by
(z)) =
lim Vf(x) is smooth x (5-5
where co represents the convex hull. If f is furthermore smooth, it holds that af(x) (V[(x)) use fz) to denote an arbitrary element in (f),, and for convenient, we call V as subgradient.
The Clarke subdifferential does not enjoy the chain rule and several techniques involved in regular gradient cannot be reused in our case. We provide counterexample to illustrate this in Claim A.
This property and a few assumptions to eliminate pathological cases are described in the below assumption.
Assumption 2.1. The loss function g(0) satisfies the following conditions:
1. g( is continuous and smooth almost everywhere;
2. The global optimum value of g(0) is O;
3. The set of global optimum points J is composed of countably connected components J. i.e., J = J, (Je [J
4. There is scalar 0, such that whenever g is smooth 01, 02 then for any data point (I,, yi),
([ Fg(02,2))]] < cmax(]l0 -211,,
This assumption describes the overall structure of the loss function g()). All 4 items in this As- sumption are quite mild and are commonly used in optimization and learning.
Items 1 and 2 are true under the MSE loss and the over- parametrization setting. Item 3 describes that the optimum is composed of countably many connected components and this item holds for almost all functions unless delicately constructs pathological counterexample Jin et al. (2022). In
3

---

Under review as a conference paper at ICLR 2023
this paper, to make the presentation clear, continue with the countably many points assumption J 1 } to avoid the tedious arguments on continuum of optimums. Item 4 can be seen as a non-smooth extension of the traditional L-smooth condition, i.e., [[Vg(z) Vg(y))l I L| yll-
It can be satisfied by many non-smooth functions, like ReLU and Jeaky-ReLUU,
Similar to the regular gradient, the subgradient is also zero at the optimum.
Claim 2.1. For the MSE loss function (7). if the global optimum is O, i.e., minøer g(0) 0. Then the subgradient at the optimum points J is
Proof. For any On {00 g is smooth 0). we can get that
1 N (f(0). ys) V.f(0., (1)
gg( Vi((bo)
Then for any H* E Jr, we have
lim
Vg(oo) = lim
(f(0). y1) y;) f(0o, x,)) 0,
00-8"
80- N
where g is smooth at 8g. Then,
0g(0") = co
lim Vg((o) : smooth at & = =c{0].
A0 -0-
This concludes that (g((t) O.
Notice that despite that is non-smooth in general, in our setting, it is smooth on the optimum as described in the above claim. This distinguishes setting from the line of literature non-smooth optimization.
To make a global convergence, we need at least one 0* J be very "sharp". That is, the 5g- neighborrg of 0* the loss function holds L-smooth condition with the coefficient Sg- and an assumption as follow:
Assumption 2.2. There exist 6" E JJ, rg- 2 1, 5 > 0, a neighboring area U( 56-) of such that for those 0 E U 58-) that Vg(0) holds
1. For any mini-batch Ct. gc, (8) holds the local one point L-smooth condition, i.e. [V)( < Bo- 110 0 (A 0 U(O (80-))-
2. The loss function holds (g) (0 0*) > ag- 110 10 (vo E U some constant ag- >
8g 1)), for
The first item of this assumption is very mild. Due to Claim 2.1 we know g(f) is smooth in 8*, that is, limg->0- gg( Vg(0*) = 0. Then item is just to bound the speed of subgradient tend to 0 is not slower than a linear function (not too sharp as O (0 or O(1 - 6* (I0.9)). The second item of this assumption is very close to the local Kurdyka-Loojssewiic condition, i.e. [[Vg(0)]| > g(0) g(0*) (r 2 1)(0 E L'0 (8-)) which local Dojaak-Eoasieewccz condition (item 2 and the local Kurdyka-Lojasiewicz condition are totally equivalent for an unary function). This assumption is milder than several assumptions used in the previous works. It can be seen as the loss function has an rg- 1-order Taylor expansion on 0". Compared with the one point strongly convexity used in Li Yuan (2017); Kleinberg et al. (2018). the positive Hessian matrix and local
typically mild condition used to substitute the
condition in global optimum used in Wu
et al. (2018); Jin al. 2022), our assumption is much milder.
2.2
TWO TYPES OF NOISE OF SGD
In the rest of this section we describe two types of SGD algorithms, by different sampling noise. The first type is with the traditional sampling noise while the second type is SGD with the sampling noise with global stable guarantee. They involve slightly different assumptions and the analysis of SGD also varies by the type of noise. Nevertheless, they conclude similar results as we will present in the next section.
4

---

Under review as a conference paper at ICLR 2023
2.2.1 REGULAR SAMPLING NOISE
We start with the iterations of an (regular) SGD algorithm, that
On 6n ((0n::n))))
Ont1 - On Un
where { represents the sampling noise. That is, we have the noised sampling
Vg(0,
Σ ((1(0, ( 8)²)
2, SEC;
where C₁ is a randomly selected mini-batch from the original data set. The next statement assumes that the subdgradient can be sampled without the sampling error being too large. is necessary for an algorithm to use the gradient:
Assumption 2.3. Let &n be the sampling noise involved in the n-th iteration of SGD and (g En) be the noised sampling of the subgradient. For any E IRd it holds
lim inf [| 0,
6-100
and
Eg,
(g)0 \
lim sup
< Mo.
where Mo 2 0 is constants decided by g. Meanwhile, we need liminfg [V > max max(AcvAM Mo. Ko).
First of this assumption milder than the widely used bounded variance assumption, i.e., Bg.. [0 5x) Vg(0)]| S a (Li Yuan 2017 Kleinberg et al. 2018 Second part is to
combine the } tend to co. For example, for very simple loss functions g (1l0 - 01 2| +
||0-0: 02 ||0 0zll²), It hold our Assumption 2.3 but not hold bounded variance assumption. Meanwhile, this sampling immediately implies the below bound.
Claim 2.2. For any bounded set Q that include J holds
Eg.. E.) Gqg(O) (VDE
where GQ a constant decided by Q.
Proof. For any smooth point in Q, the mini-bat mini-batch gradient norm satisfies
4
[[ (0)]
Σ
(f(). Vc) V.)
xx))
No
s EC:
(3)
N
4N ANEA ==1
V
mx:)
Σ
(5(0 Me) (11
=g)),
N
N3
Z.EC,
where No is the size of the mini-batch. Define
4N 4NEN N Ei=l (0
lcc, (0)
N3
Through Assumption 2.1 we know that h(0) is bounded on smooth points. Then we have
4NGo N3
V Vgc. (0.5.))
g(0)
(when g is smooth at 0).
(4)
Then,
N1 Es, (g((0.))
4NG N
N-1
Σ
Vic (0)1
N-1
g(0) GQg(O).
C.oo
N3C
all C.
5

---

Under review as a conference paper at ICLR 2023
For the non-smooth point 8, prove for any sequence 8, - 0 (g is smooth at 80), through
Equation (4), there
lim Vgc. (Oo, 5m))| (00. 60 +0
lim 06
Vgc, (Do. En sl
2
4NGQ No
lim g(0) 80
4NGQ g()).
No
Recall the following fact:
If |a
< 50,
||a2||
80. .... ||ax1? < so: the norm their any convex combination
| 2
Apai
1 80 80
Then we obtain
4NGQ |V gc. (0)]
No 9
This concludes that
EE (g)(1 S Gog(O).
We could observe that the noise variance Eg, (0,)( {0)0) = at the global optimum (Claim 2.1). Intuitively, the zero variance makes the An stable the global optimum, while for local minimum or a saddle point the variance is nonzero in general. This is intuitively how SGD escapes from local minimum and saddle points.
We have to notice that the global optimum is subset of the set where the noise variance equals 0. easy to prove that
J c EE, (((0E.)) ((0)]12 - -0 J
where J is equivalent to
J n A -1)) =0 C.
-
Our techniques will eventually prove that the SGD with regular sampling noise converges J This could be different than J in theory, but intuitively, for the aver-paramete model and a large amount of data the model f00,z) is complex enough to make sure that other stationary points are sensitive to the mini-batch batch selection. As such making a point, that is not the global optimum, stationary to all batches simultaneously is almost impossible, i.e., J / der to insure the rigor of the theory, we make an additional assumption only for the regular sampling noise. This assumption is lifted in the sampling noise with global stable guarantee.
0. Nevertheless, in or-
Additional assumption for regular sampling noise For the sampling noise {En}, points that are stationary all miti-hatches must be in J*, ie., J ======= J Meanwhile, for every mini-bater loss function 9C., the stationary point set of 9C, is countable.
If one slightly modifies SGD by adding an additional Gaussian noise, we will prove that such sam- pling noise will enjoy a global stable guarantee. With this variant of SGD, the above assumption could be lifted. We now present our proposed variant of SGD.
2.2.2 SAMPLING NOISE WITH GLOBAL STABLE GUARANTEE
The sampling noise we propose in this section is the regular noise in SGD plus an extra Gaussian noise, as
Un = 60 (Vg En) + (min(g(0,), KoTTnNN)
(5)
0.+1 = 8 Un
where { again represents the sampling noise, Ko is a constant to prevent the noise from approach-
ing infinity, } represents a mutually independent standard Gaussian noise, {T,, is mutually independent Bernoulli variable, i.e., P(T, 0) Pu. P(T, = 1) = 1- Pu. and {T, {e. (Nr) also mutually independent. The coefficient min(g((... Ku} is make sure the algorithm hold a positive noise variance Eg,.,.. ||2 duce the scale of the problem, making the scale of the noise equal the scale of the mini-batch
in non-optimal stationary points. We use [T,, to re-

---

Under review as a conference paper at ICLR 2023
gradient Vg((,, and as the original sampling noise. For example, if the batch size is 100 and the scale of the original data set is 10000, then we can set Po = - 0.01, which makes the average scale also 100. The tail term / ( KoTTaN, guarantees
of the noise min (O..), Ko that this algorithm has positive variance in /
3 MAIN RESULTS
Our first main result states that SGD must converge to global optimum with probability 1. This is large improvement from previous results with only 1 probability, where 5 depends the model. Our theorem answers the question raised in the introduction, affirmatively, that SGD could indeed obtain global optimum even in this non-smooth non-convex over-parameter setting. The next two theorems discuss the cases of rg- > 1 (higher than second-order local structure) and ro- = 1 (second-order local structure) respectively.
Theorem 3.1. Consider the SGD iteration in Equation 5), alternatively Equation (2) with J
J and the MSE loss function (7). If Assumptions 2.7 2.3 hold, and Assumption 2.2 holds with ræ- 1, then for any 0 < ED < min(L//2Mo. 1/4cK
po)}, }, and for any initialization 01 RRd
{0,} converges to the set J almost surely, i.e.
lim d(On, n-000
a.s.:
where d(x, J*) inf (11 yll. E J"} denotes the distance between point x and set J Mean- while the value of the loss function converges to 0 almost surely, i.e..
lim g(.)) =0 a.s..
For each main result, we provide a proof sketch to illustrate our idea in deriving the result. A rigorous argument is deferred to the appendix.
Proof sketch. Our proof mainly relies on two techniques. The first technique is the Lyapunov method. It transfers the convergence of high dimension vector 8, one dimensional Lya- punov function R(O,). The second technique is to use the idea of Markov process. We sketch these two steps and additional step follows.
Step 1: In this step, we aim to prove that there exists at least one bounded set So such that there is no limit point of (0,) } is in it almost surely. Through the Borel-Cantelli Lemma, it amounts proving
Σ P(e, So) t00.
In order to prove Equation 16 we use the Lyapunov method, constructing a Lyapunov function R(0) which holds unique zero R(00) = 0 and an open set So which include 0* (exact forms of R(0) and So are provided in the appendix). We assign I, as the characteristic function of the event
{0,, So). Then obtain the inequality
1+ R(O (1)) R(O..) < ( R (0..) + thy
(50)
where un defined in 12 with to0 E(u,)) < toc. Summing up Equation 6 yields
Σ (I R (Bw)) < E (I( (80) 2r (01) + E(un) < t00.
R
Subsequently could construct So So/U(0" 36). for some small enough &g make Σta E (1(50) [+ (0m)) Σta E (1) 7 (0.)) +o0. Then, whenever On S0/ %) we have R (0) E, we have
to0
400
Σ
P(0, E So) <
Σ
E (So)
2r R- (0m)) < t00.
n=l
7

---

Under review as a conference paper at ICLR 2023
As such we conclude Equation 6 and through the Gorel-Cantedn Lemma, we know that there is no limit point in Sn almost surely.
Step 2: In this step, we aim to prove that for any bounded set S that has intersection with J there is no limit point in it. The way we prove it is different for the two types of noise (2) and (5). Handling the sampling noise with global stable guarantee ( is relatively simple. The Gaussian noise of (5)
guarantees that it forms an irreducible Markov process. Then using the property of the irreducible
Markov process directly will prove the statement. For (2). the situation becomes complicated where an argument of the regular sampling noise does not deduce an irreducible Markov process. We prove using a delicate argument. We first prove that a max positive bounded invariant set D must hold its boundary set a DJ * 0, and every trajectory started from this set must almost surely converge to some global optimum. Here a set is max positive invariant if any trajectories started in So will not escape So and for any points 0" & JJ U is not positive invariant set. That means, for any point either almost every trajectory started with converges to J", or it holds a positive probability transfer to So. For the first situation, this statement is satisfied. For the second situation, we can make a small enough positive measure set, such that for any E S, there exists a &y and some large Then we can get desired
enough k, P(0n+* So
On = >
+00
400
[
400
[
P(O, ES)=
Σ
Pa- (do
Σ
P(On+* E S((ood))) 0n, =)= Pn-
m=k+1
n=k+1
4:00
Pa(d0) < +00.
n= Stoudd
Step 3: In the previous step we actually proved that almost surely either On + J or On - to0.
Through the Kolmogorov 0-1 law, we know (0, converges] a tail event. As such, P(nn - J*) E {0. 1). Meanwhile as P(O, oo) = 1 impossible, P(O, + J") could only take 1.
In step 3, we suspect that P(O, + 00) = is indeed impossible, even without the assumption lim info- [V)(()]] > max[4c/Mo. 4c/Ko). In fact, as long as 0n converges to J for any initialization 0, some neighboring domain of the optimum, it converges for all initialization. This is because for every initialization it either converges to the optimum or it has a positive probability to transfer to an arbitrary set with a positive measure. As the neighboring domain could be arbitrarily small, it is likely to exist.
5 or alternatively Equation (2) with J J and the MSE loss function (7). If Assumptions 2. 2.3 hold, and Assumption 2.2 holds with r-- 1, 1, then for any 0 < eo min(11/ccM) agg (2 po , 1//cK// - -Po)}, where normal sampling noise 2 can be seen as pa 0, and for any 01 E Rd. On converges to J almost surely, i.e.
Theorem 3.2. Consider the SGD iteration in Equation
lim J() n-000
a.s.,
where d(x, J²) = infy [lk= vll.y E J"} denotes the distance between point and set J Mean- while the value of the loss function converges to almost surely, iee.
lim n
g(0m)
a.s..
Proof sketch. This proof will be similar to the proof of Theorem 3.1 The difference is when ra- the convergence towards a global optimum with second-order local structure is conditional on the selection of the initial learning rate eo. The reason for this is the inequality
( n+1 R(0x+1) T(SO) R(Om) S - (a0- 60 2(2 po) T(S0)
( R(O.)) + un
(8)
holds only when the coefficient ag-E6 - 2(2 - po) 53 > O. By setting as the theorem the inequality and other arguments remain valid. This proof also agrees with our intuition that SGD converges to a sharper global optimum not easy as flat one (ra. 1).
Recall the second question raised in SGD was conjecturing if SGD tends to choose the flat minima (and to enjoy better generalization). In the end of the above proof we find that SGD converges
8

---

Under review as a conference paper at ICLR 2023
to sharper global optimum not easy flat one. This observation is through positive results only, though. We wonder if the converse is also true, that is, if global minimum is not flat, then SGD is unlikely to converge to that.
In the below theorem we answer the converse affirmatively. proved that if en is large enough, then the iteration will almost surely not converge this optimum.
Theorem 3.3. Consider the SGD iteration in Equation 5) alternatively Equation (2) with J
J and the MSE loss function (7). If Assumptions 2. 2.3 hold, and Assumption 2.2 holds with re- = then for any 01 Rd. if co > 90- /2-/2(2 Po Po where normal sampling noise 2 can be
seen as Po = 0, the probability that On converges to 0* is 0, i.e.
lim ||0, - 8' = 0) 0. 12-200
Proof sketch. The main idea is to prove that if the iteration always stays in neighboring domain of 0" then the probability that this iteration converges to 0" is zero. The Lyapunov method is helpful this case.
Step 1: In this step, we aim to acquire reverse inequality of 7 We first construct Lyapunov function R()) and domain S1 of f", and an event A., (0mg S1, no E [i, as well its characteristic function Lin Then we can acquire inequality
Ii,n (R(O R(O,)) 2 (2(2 - po) -0/30- J R(On) + Ji,nSa
where is defined by equation 33 Notice that if (2(2 -p)) -0 0, then this inequality will be a variant of diffusion process.
Step 2: In this step, aim to prove when approaches infinity, the iteration will transform fixed part of itself out of S1. Through (9), we get
E (R(0n+1)(L, (imtta))
E (Tint1 R(On+1)) 2
1 - 6o
TE (Ii, R(Om))
E (Li,R((B))
We know
E (R(On+ (1im l(,+1))
<
po,
E (Lim)((0w))
then E (1.n42R((n41)) will diverge to infinity, which is impossible to happen. As such, it must hold
E (R(On+ (J [sat1)) E (Ii,. R(0m))
2 Po.
Step 3: In this step, we will show that if E(4 # 0) > O, then 4t, R(0m) will not converge to almost surely. We prove it by contradiction and assume P( (lim, R(0,) = =0) = 1. That
means for any 6 > 0, P It R(0m)) > 6) + O. which concludes P (I R(0m) S <b - 1. Then
E (R(0n+1) (Lem L.m+1)) + K'G.
E ((,,)
This forms a contradiction.
Step 4: this final step, we will prove P( [11m On = -0²)= = 0. We inspect the event (0,- + 8r). If B(T * 0) > 0, then due to lim (On)(mm) -1 (1.) a.s., we could get P( (1ommn+400 10 R(0,)) = 0)
Then,
P((0.. - 8th n A P( lim I,tt0 0) 0.
4
Otherwise if E4 # 0) = 0, we have
P((0, 0²) n Ai,t & B(Ji,to # 0) 0.

---

Under review as a conference paper at ICLR 2023
Absolutely, we have
toc
U Ultton
{0, +07
Subsequently we have
+oc P(On. + 0*) = p (8n - +nnr
U Altto 1)=
(
((00 - - n Ai,to
p(
+00
m=1
i=1
+00
P (10 + +0 +00 A =0.
As we have shown the asymptotic convergence of SGD, the natural question is how fast it converges. To provide the convergence rate, we will need a slightly stronger version of Assumption 2.2 We need, instead of just one 0" all 0", to satisfy the order r + expansion. In this case, the supremum of the expansion order, among all optimum points, denoted as f maxg- EJ To-, where J {0r E J P(O, + 0*) > 0}.
Our next theorem provides the convergence rate of SGD.
Theorem 3A.. Consider the SGD iteration Equation 5 or alternatively Equation 2 with J J and the MSE loss function Q If Assumptions [2.1] 2.3 hold, and the variant of Assumption 2.2 described immediately preceding this statement holds with order 1, then for any 0₁ E RR On has an asymptotic convergence rate
(0())) on A) a.s.;
a.s.,
if f = 1, f > 1,
g(0,)=
where Po < 1 is constant decided by the learning rate co.
Proof sketch. The proof of this theorem based on the proof of Theorem 3.1 We asymptotically bound of martingale difference (Lemma AAII) and with the bound apply the martingale convergence theorem. The asymptotic convergence rate follows.
As immediate consequence of the convergence rate, the SGD algorithm could obtain an arbitrary accuracy in polynomial time. This validates the efficiency of SGD.
Corollary 3.1. Consider the same setting as Theorem 3.4 for g(O,)) reach an n accuracy is
For any 01 Rd, the computational time
(Nod log( (H) 0.8., if = 1, ONNd (a)dd(2) =) a.8., if > 1,
where No is the mini-batch size.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, 2019.
Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, al. Deep Speech 2: End- to-End speech recognition in English and Mandarin. In International Conference Machine Learning. 2015.
Devansh Arpit, Stanistaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International Conference Machine Learning, 2017.
10

---

Under review as a conference paper at ICLR 2023
Peter Bartlett, Dave Helmbold, and Philip Long. Gradient descent with identity initialization effi- ciently learns positive definite linear transformations by deep residual networks. In International Conference Machine Learning, 2018.
Avrim L Blum and Ronald L Rivest. Training a 3-node neural network NP-complete. Neural Networks, 5(1):117-127, 1992.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for ConvNet with Gaussian inputs. In International Conference on Machine Learning, 2017.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in neural information processing sys- tems, 31, 2018
Frank H Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990.
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer CNN: Don't be afraid of spurious local minima. In International Conference on Machine Learning. 2017.
Gintare Karolina Dziugaite and Daniel Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Uncertainty in Artificial Intelligence, 2017.
Yu Feng and Yuhai Tu. The inverse variance- vuriance-flatness relation in stochastic gradient descent is critical for finding flat minima. Proceedings of the National Academy of Sciences. (189)))0011617 188, 2021.
Rong Ge, Jason D Lee, and Tengyu Ma. Learning ame-hidden-laye layer neural networks with landscape design. In International Conference on Learning Representations, 2018.
Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. arXiv preprint arXiv: 1ete:41446664 2014.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. In International conference acoustics, speech and signal processing, 2013.
Ricardo Halla, Adeilson de Oliveira Souza, and Fábio José Pinheiro Sousa. Use of Artificial Neural Network for Analyzing the Contributions of Some Kinematic Parameters in the Polishing Process of Porcelain Tiles. Springer, 2022.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint arXiv:1611.04P7 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Conference on Computer Vision and Pattern Recognition, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Simplifying neural nets by discovering flat minima. Advances in Neural Information Processing Systems, 1994.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
Ruinan Jin, Yu Xing, and Xingkang He. On the convergence of mSGD and AdaGrad for stochastic optimization. In International Conference on Learning Representations, 2022.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does SGD escape local minima? In International Conference on Machine Learning, 2018.
Hendrik Anthony Kramers. Brownian motion in field of force and the diffusion model of chemical reactions. Physica, 7(4):284-304, 1940.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84-90 2017.
11

---

Under review as a conference paper at ICLR 2023
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
Guo Lei, Cheng Dai-Zhan, and Feng De-Xing. Introduction to Control Theory: From Basic Con- cepts Research Frontiers. Beijing: Science Press, 2005.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU activa- tion. In Advances in Neural Information Processing Systems, 2017.
Wei Liu, Xin Liu, and Xiaojun Chen. Linearly constrained nonsmooth optimization for training autoencoders. SIAM Journal on Optimization, 32(3):1931-1957) 2022a.
Wei Liu, Xin Liu, and Xiaojun Chen. An inexact augmented Lagrangian algorithm for training leaky ReLU neural network with group sparsity. Preprint wwXiv:2205.05428. 2022b.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 55007676):354-55, 2017.
Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis. In International Conference Machine Learning. 2017.
Sharan Vaswani, Francis R. Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and accelerated perceptron. International Conference on Artificial Intelligence and Statistics, 2019.
Zhong-zhi Wang, Yun Dong, and Fangqing Ding. On almost sure convergence for sums of stochastic sequence. Communications in Statistics- and Methods, 48(14):3609-3621 2019.
Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing Zhu. On the noisy gradient descent that generalizes SGD. In International Conference Machine Learning, 2019.
Lei Wu, Chao Ma, and E Weinan. How SGD selects the global minima in over weer-paameterizee learn- ing: A dynamical stability perspective. In Advances in Neural Information Processing Systems, 2018.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine trans- lation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144 2016.
Zeke Xie, Issei Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference on Learning Representations, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. Communications of the ACM, 6473)1007-115, 2021.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for me-hidden-llaer neural networks. In International Conference on Machine Learning, 2017.
12

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1
COUNTER-EXANEE
Claim A.1. The chain rule does not hold the Clarke subdifferentill.
Proof. For composite nonsmooth function, the chain rule may not hold at the nonsmooth point Liu ct al. (022b). We introduce an example as follows.
Consider
min w.. ER, fw1, W2, b1, b2)
(lwyo (wi + b1) b2) + 1)² + ((wzo (2w1 + b1) b2) - 1
(10)
Let w = 1, bj 0, w" = 0, biz 0, one can easily see that the SGD method will get stuck at
(wT, w2 67. b5), and
0f(ws. wz. bi bb) = {tt, 0,, 8,00 E -, E [--,,]]]
f(w] + c. 2 bj b2) = =5c²- - -c + < 2 = f(w], w bj b5) for some small positive number c.
Then, observe that (wi, wS, bj. b;) is neither a local minimizer of equation Morcover, one can that (1,2, 11, 11 is global minimizer of equation 10 which the function value is 0.
A.2 AUXILIARY LEMMAS
Lemma A.1. (Theorem 4.2.13, Lei et al. (2005)) Consider a Martingale difference column
(Xn,Fa) Fr) that satisfies sup, TE[[|X x (FFa) +00 almost surely. Then it holds that
MBAA - In +e) almost surely, Vn > 0,
where Sn = Ek-1
Lemma A.2. (Lemma in Jin et al. 2022 Suppose that {X,} E IR is non-negative sequence of random variables, then 0 X, < too holds almost surely if
< +oc.
Lemma A.3. (Wang al. 2019 Suppose that {X,} Rd is an L2 martingale difference sequence, and (Xn,Fy, Fa) is an adaptive process. Then it holds almost surely that Ek=D Xx < too if
00
00
Σ
113) < +00, or
Σ n=1
R.
11
< +00
happens almost surefy.
13

---

Under review as a conference paper at ICLR 2023
A.3 PROOF OF LEMMA A.4
Lemma A.4. Consider the SGD updates specified in equation 2 (or equation 2 with J JS*) and the MSE loss function equation [ If Assumptions 2.1 2.3 hold. then for any cD <
min(1/2cM4 1/4cM// po)}, where normal sampling noise 2 can be seen as Po = 0. Then
for any 01 Rd the probability of fn diverge the infinity is less than L, i.e., P(O, + 00)
Proof. We prove this Lemma by contradiction. We first assume P(d,, + oo) = 1, which means on + almost surely. By the Lagrange's mean value theorem, have
g(n++)) g(On)) = (o(0c.)" 0z),
where Sn is a point between 8, and 1 Sn is non-smooth point, then we can find at least one point in the set of V (.,,.... Therefore, we have
g(n+)1) g(O,,) (g((c,)) (f -n))
(g(,,) V En) (Vg(O,.) Vo(O,))) - 6n.)
I EO
(n) + (g(0..) (g(0,) - 0nl
S (0,) VV + 1 h//0://000000//a//o//o////////// + vol Vv, o (.))l + (0, 2
Through Assumption 2.3 we know that it hold B.g (0, 22 < Mo V (0())) 2 when On.
Do. Then we take an expectation over the sampling noise, we have
E (g(On+1) E (g(O.)) < ca E ( 2
cov Mo E (o.)))) + Mo . o g(
+ ccl - po) Kneō + cc - (10)
(co cM E (0,)l + COO Mo E (g().)) + c(1 po) Ko
+c Po Koco-
Since 1 cMors > 0, and (()g(.))) > max /o. 4e
po Ko) when 6,, - co, we can
get (( max 4c Ko) + 1. This implies
E Vg 2 (E ((
With this, we have
E (g(0n+1)) S E (g((1)
K/co Σ E (V -00 k=1
which is impossible. We thus conclude that {0,} can not tend to infinity almost surely, i.e., P(O, 00) < I.
A.4 PROOF OF THEOREM 3.1
Proof. For convenience, we abbreviate r'- == Then we let
lo = min {
30. +
r+1
m==min/
80- j
2r(r + () app c
(ro-)
and construct function
|10 0 1r
if 110 0*1| S max (1,50-)
R(0)
110 111,
if || 8* > Ko
R(110 0" ()),
max{1, < ||0 001l s Ko
14

---

Under review as a conference paper at ICLR 2023
where k[|l0 (1) is the smooth connection between || l*ll <1le 8*1l Ku) and ||0 8-| max(1,6p- 1).
(10 1-1
Then through choosing feasible k(0-0") and Ko, we can ensure that the Hessian matrix of R(0) bounded in Rd. Let the upper bound of the Hessian matrix be r(r + 1), i.e., x" Hagx S r(r + 1) || (vz R., 0 E I.
Next, we construct
(06) = 1000 < 00 0- 40
We also define event A = 10, E s(l)} and the characteristic function I Through the Lagrange's 's mean value theorem, we obtain
T( (R(On+1) R(O.)) 1( (". -O,),
where Cc., 10 0n). Note that
VR(OG.) = VR(O.) + VR(OG.) - VR(On),
and thus
( (R(0 R(O,)) - - VR(O, + - (V((,, VR(0,)]l10 0.ll- Hence, for any 0 E [0|110 0, s max 6g- }} we have
V R((0) = v(1 0- 1-1 (r + 1) 0- 0²)
Moreover, if ||0g. 0, < max m1. 66. }. we also have
RVOc.) ((.))) S r(r 1)]10n+1 0nll",
and if 110g. 0,1 2 max 1}. we have
[V,();,,)) VR(O,)) r(r + 1)116G. - 1,1
r(r +
S 10c, - 0n 0-|1r-11 100 0z
r(r + ||0x+1 - 0n1l".
With this, we have
VR(OG.) - V R(A,)) <r(r + 1)] | - 0,ll" = r(r 1)l"", (((b)) (R(0n+1) R((O))) (R((,)) "Tv,
Un ((00))(r 1)]l,.11**
1+1 R(0x+1) 11000 R(O,)) < -1 v R((,,) TT, 1 ((r))(rr)))))) + 1)][u,,11* 1+1
(16)
- ((((5)) (1))
n+1 R(0x+1)
(II)
Taking expectation of equation we have
(I(ho) (R(B)) vTu))
(80) (VR(O,)) Un (F))
(L0) co (((e,)))))))))))))))))(r)))))( (g((nn ((lo) ( (VR((,)) mmin
= eo E (1)) E (VR(O,) (
Define $ to be the set of 0', such that g(0") is not smooth. Then with Assumption 2.1 have
where h is an arbitrary measurable function. Hence, when 6n R. /S.
"
-(lo)(r + 1) - 8- 0011-~1 (0, 0))
7((o)) (r + 1)](a. -0-
-011"-1a0 a 1|0, 8º 1111"=1 I((00 ox- (r+ 1 (0.)
15

---

Under review as a conference paper at ICLR 2023
Therefore, we have
E
B 10 ((
VV((0)) (
= E / ( ( (Vg().))
2 E (b) ag- (r + (o,)).
and through Assumption 2.2 we get
E (T r(r + Uz 1t11)
= =r(r+ 1) + E 1 (10)
B (()1+((
+r(r + 1) E (1) E (Il min (f,) Ko KoTTnAN (F
+r(r+ + 1) 1)x0 E (()b) R (Vg(0 ) (n(n)) Ko) Ko]TTNN Nn Non
=r(r + 1)(²=1 E (10 E (1) g Onn, En (
+ r( 1)(²=1 E (( E (1l min (l..) Ko Nr (l
Sr(r+ + 1)(2 6 (Be. + 1) ( E (()b) R(O,)).
where G Gfrer) is defined in Claim 2.1 and results of equation can be seen the situation which Po 0. Then,
E (194) R(On+1)) - E (1%0) R(O,)) s - cg-eo E (I(6) R(0n)) -i1)
+ + + 1)(2 - (So. + 1)c5 1
afroo) E (1 R 3 (0m))
E ((1 1 (100 11(On+z)).
Due to On E ((b),, we know
Bp.
R(Ow)) <
2r(r+ + 11(2- Po)
)00) Eg
That means
agg- 10-0 ( 2x (0n)) > 2r(r + 1) - -o)aag r+ GG(or ((lb) H(O)),
Hence,
(T
n+1 ((0++1)) )) - F. (T R((O))
(1e)
C0 (1)))) R- (0,,)) - E ((T I(lo) r(())) R(On+1))
$
2
For the term E ((T(b) (1a) R(00++ (100))))). 1), we observe that
E ((I - (10) ((4)) = E ((1(/)) I((0) ((0) (1o)
(((0m+1)))))))) (1(()) - I(0o) ) R((a+1))) (12)
n+1
and
(100) (1o) (1o) )g( (0(0))))))00))0)1)))))))))))(( 2 (( (ll)) I (oo)
(7(b) ((()) ((10) )g( (1 < (TUlo) ((lb) [((n))-
Taking these into equation
12 we obtain
E ((T - -((00) R(Ox+1)) 2 E ((T!!1) I(Hba) (U0o No (T!l)) I(00) I
E (I((0) I 1(10)
(13)
Taking equation 13 into equation 12 we have
E (r ((0)) R(On+1)) E (I R(O,)) S ag. ED
E (loo) R2 (()()) - -10 F (T((1) -y(m))
(14)
16

---

Under review as a conference paper at ICLR 2023
Summing equation 14 over have
E (1 R((n+1)) (71 (1 ((O.)) S
Otg. CD
E (I!b) R (0,,) - 10 E (1 [14))
2
(15)
Rearranging the equation, we have
2(lo + g(f1))
Σ
E (
(1) R (0,))
< 400. agg Co
Next we construct a subset of 5(1o) as
5(60.lo)
{0|0 < 60 1 10 1 1o).
Define event
(bo.10)) = -0 E 5lóo
and the characteristic function be (60010) Obviously, we have
2(1o + g(f)))
E
(1 R R (0x)) <
(o)
(1
R
(16) R R (0w)) -
< t00.
ag.. 60
k=1
Let ro == infoestoio
Ri+i (0) > 0, we have
2r
E (1 (oool)))
2(10 + g(01))
ro
< 400,
c00-60
1=1
that is
+00
2(1a + g(0i))
P(0 E s(bodo)))
=
Σ (1(0olb)) <
< t00.
(16)
Cg-C
k=
Then we can obtain
4:00
P((nn} E 5(80.0)) i.o.) = ( unU
(Ox s(ooloo)
(17)
n=1 k=n
t00
(U E s((oooo))
lim +000
(18)
toc
lim
P(Oe E ((60.10)) =0.
(19)
n n
Note that equation 17 means the set S(om,do) has no limit point of {0x} almost surely. Then if we use the SGD update rule equation Since the noise Gaussian, any 0 Rd/J** and for any & > O, there is P(On+* E 5(ooda)) 00, = 0) = &. > O. we use SGD update rule equation 2 for any max positive invariant set D'J*, we know that there must exist boundary set OD. Moreover, VO' OD, if 6' E Rd/DD, then for any mini-batch C, we have Vgc. (#') = 0. Otherwise we can find a sequence {8" + 8', /'"/0" E D). making the trajectories started from 8" close to the trajectory started from 0'. It forms a contradiction. Then due to J = J*, we know That means 75 n J * 0. If 0' E D, we can conclude all trajectories started from O' are subset of OD. On the other hand, we can conclude àg is close set. Through Heine Borel theorem, exists a finite open cover U O, 5 @D, and every O, holding an arbitrary small diameter. We let 0' Oi. Then assign T, the lone time interval of one trajectory started from 0' and back to T,, If T, + +o0, that means this trajectory must stay infinity time in some Ok: that means exists global optimum Oz. Naturally, the trajectory will converge to this global optimum. If T₁ is bounded, that means the trajectory will enter into O infinite times. Due to mass of different
J
mini-batch and the enough small diameter and f(0) = P(O,+* Rd/D 0) = 8 > is continuous function, We get P(0n*k E ER//D(0, O₂) 8n > 0. it is contradiction about D is
17

---

Under review as a conference paper at ICLR 2023
positive invariant set. That means for any 0 E R/J", either trajectories started from it will converge to some global optimum, either it has positive probability to make sure it transfers to S( after k steps. Then for any bounded set So which has no intersection with J first get rid of those
points which will converge J We know that f(0) == P(0n+* E S 00,, 0) 60 0 is continuous function. Then we can get for any bounded closed set So which satisfied Su n J 0, there mss P(On+* E (66 00,- = 0) = 81 > O. Then we aim to prove there is no limit point in So almost surely by contradiction. We assume
+00
P(O, E So) = +00.
Then,
+00 Σ
+00
P(On ((6o.oo)
Σ
Pr((
k41
+oc
P(Onth E =0)
gad
n=
+00
P(On+* E 5(661o)) = -8)
So
x=
toc
81
P (n0) = 81
Σ n=1
P(On E So)
S0
n=
00.
Note that this in contradiction with equation
16 and thus +00 P(O,, E So) < +00. Then,
P((0n} E So, i...) = p
(nu
(
+oo
(Ox E So)
k=n
400
UU (0x {0)
lim
(20)
++0
k=n
+20 P(Ox E Sn) =0.
<
lim +00
that for any bounded set which does not include J = {0 g() = 0} has no limit point almost surely. This implies 0n + J or 0n - co. Since (fO.,) is convergence) is tail event. Then by the zero-one law, know P((0,) is convergence) 0 or 1. That means {0,) either converges to J" almost surely, or diverges to infinity almost surely. Through Lemma A.4 know P(O, - oc) < 1, thus {0,} can only converge J" almost surely.
Combining equation 20 with equation 16
A.5 PROOF OF THEOREM 3.2
Proof. We define R(0)= ||0 0" 112, and set
((la) { < ||0 00 : 6g-
We also define an event A!10) = {0,, E s(bo) and the characteristic function (,000) By Lagrange's mean value theorem, we have
(10) [R(0 - R(O.)) V " -O,),
where Cc., E E(0m+1, 0m).
Note that VR(Oc..) VR(0,) + VR(O.) V((Oa), we have
((o) (l)) (R(0.+1) P((O))) <
+ T(( (VR(O,))) (R(0.)]l100++1 0,1
18

---

Under review as a conference paper at ICLR 2023
Moreover, also have
(V.((0c.) - V R(O,,)) S 2 Ont1 0.l1 =,1
(400 (R(00++)) I((O)) I 1 R((On) '0u,, un + 1,140)21 2 12
(((O))
((1)) (R(0n+1) - I((On)) S - - I((n))* Un + 1 2|
p R(On+1) R(On)) S - - R(00)) (000m²n Un + T 1 n+1
(21)
(I 1 (1m) R((0++1)
(22)
Taking expectation of equation 21 we have
E (R(,))
(10) E ( (VR((On) Un (F,))
E
[ (1) co (VR((,,) 7 Fg((m:En) + I co (VR(0,) (minng(On)) Ko KoNTTNN) (
=oo (T (V (V
We define S (8' Vg(() is not continue 8¹). Then through Assumption 2.1 and note that Bo,.es(((On)) O, where h is an arbitrary measurable function, we have that the following when on E RŠ.
1 VR(O,) (g((.)) = 2I (-) 27 ag. 1| 10
2 (1) ax- 10- 0- = 21(() ar- R(00).
Therefore, we have
E
ERy/S
> E (1 ag- R(O,))
and through Assumption 2.2 we get
(10)
1,,,,111 ||2) = 26 E (1 E (1)
+ 2 ((1b) E (Ilv min (g(0n), Ko) Ko.Tn.Nl11
4 E (1) E (Vg(On, S² " Vminto(On), KooTT (F.))
20 E (T E (1 E., 12
2 E (14b) E (Ilv min (g(0n), (1.1
$ 2( Po) c (T R(0,)),
where the situation of equation 2 can be seen as Po = 0. Then we have
E (T n+1 R(Oa+1)) E (T. R(O.))
(o)
< co E (I(10) R(B,)) + 2(2 po) 20 E (I!1)) R(0.)) - E ((T!H)) -r(l0) ((0m))))1)))
and
E (1o) R(O - F (T (1)) R(Om))
< - (ag-co 2(2 Po) 26 E (I (lo) R(O,)) E ((I /(l)) R(Bn+1))
For the term E (11!1)) -100) RR(0) 1), we first observe that
E (11 - (10) (((1)))(0+)4)) = =E ((I ((5) 1 (10) R(0,, - (1(1)) (16) 1(0)) (((n)))(
(23)
19

---

Under review as a conference paper at ICLR 2023
and
(1 _ 1 (10) (441)((0++1)) 2 (0(4 [ 1 (10) )
(744) - ( ((( (g(0n+1) - lo( - I(lo] r((n)).
Taking these into equation
we have
E ((1) (11)) R(0m) 2 E ((1 7((0) (u4) u+1 Mo (144) (((6) 1(00) No)
(24)
= to E (I, [1o)
Substituting equation 24 into equation 23 we get
E (1lo) R((n+1) 1)) - (T R(O,))
(25)
< - (ag- 2(2 - po)e (100 R(O,)) - 10 (1 -101))
Summing equation 25 over n,, we have
(1 R(On+1)) E (I R(01))
(26)
< Ea - 2((2 P0)
Σ k=1
E (I (o) R(O,)) - 46 E -144
As 6n < Ogg. /2(2/222-22 - 3p-) we have
Σ 1=1
E (1 110 R(Ox)) <
to + g(1))
< 400.
2(2 po Bp
01-- 60
Next, we construct a subset of ((l)) as
S(Bo =0 8 1 8 1- < ko}
We also define (00.0) = f0n E ((fo.o)) and the characteristic function be (f6..)) Notice that, we
have
D 1=1
n
E (1 (60.0) R(Ox)) < (1) R(Ox)) v
0gg-E0 - 2(2 3 < +00
to + 9(01)
Denotero = inf inf f0
R(0)) > 0, then
(I (oodo))
lo g(0)
ro
agg. cu - 2(2 - poppppppp 33.
+00,
that is
P(Ox E s(holo))
= Σ
E (1(6)))))
tu + 9(1))
< +00.
(27)
00 2(2 Po 22
1=1
With this, we have
toc too
P((0n) 8(6010) i.o.) (
U (Ox E s(buttl)
Awn
lim 00
U(ex (0x e s(ho.ol))
(28)
k=n
lim
P(On E s(8o.o))
12 +000
k=n
0.
20

---

Under review as a conference paper at ICLR 2023
We remark thatequation 28 implies the set S(66,o)) has no limit point of {8,) almost surely. Then if we use the SGD update rule equation as the noise is Gaussian, for any / and any l >> O,
there is P(On+k E 5(60.t0) 00, = 0) = 60 > O.
If use SGD update rule equation 2] for any max positive invariant set D/J*, we know that there must exist boundary set 0D. Moreover, A9' E åD, if 6' E R /D, then for any mini-batch C₁ we have Vgc; (0') O. Otherwise we can find a sequence {Ø" + 0', /8" D), making the trajectories started from 8" close to the trajectory started from 0'_ It forms contradiction. Then due to J J we know 0' E J That means D J + 0. If 0' E D, we can conclude all trajectories started from 0' are a subset of ÒD. On the other hand, we can conclude Òg is a close set. Through Heine" Borel theorem, it exists a finite open cover U On 5 OD, and every On holding an arbitrary small diameter. We let O' E Og. Then we assign Tn as the lone time interval of one trajectory started from 0' and back to Tu. If Tú + to0, that means this trajectory must stay a infinity time some O₁, that means exists global optimum in Og. Naturally, the trajectory will converge to this global optimum. If T, is bounded, that means the trajectory will mass of different mini-batch and the enough small diameter and f(0) == P(0n+k E DIO,, = 0) = 8 > is a continuous function, We get P(0n+ e R2 /DIn, E 01) = 60 > O, it is contradiction about D is a positive invariant set. That means for any 0 E R/J", either trajectories started from it will converge some global optimum, either it has positive probability make sure it transfers to ((6udda) after l steps. Then for any bounded set S, which has no intersection with J we first get rid of those points which will converge to J We know that (0) == P(On+* E (( = 0) 8 > is a continuous function. Then we can get for any bounded closed set So which satisfied S, n J = 0, there minges, P(On+* E 5(60.00) (0,, = 0) 81 > Then we aim prove there no limit point in So almost surely by contradiction. We assume
enter into O1 infinite times. Due
+00 P(O, So) +oc.
Then we can get
Σ
P(O, s(oodo))
Σ
(d(
1
n=k+1
toc
P(Ontk E S(6oda))00, Pb)
gad
n=#
PiOnt 51ood0)10, = PO)
80
#=
+00
(do) = 81 t00
81
Σ
Σ n=1
P(On E S0)
n=
+ 00.
This is contradiction with equation 27 which implies
+:00
Σ
P(O, E S6) < t00.
n=1
21

---

Under review as a conference paper at ICLR 2023
Hence, can obtain
1:00
P([0n] So, i...) = P pNUUUU
(0s So)
n=1 k=n
lim
P
U@x (Ox So)
n +00
kmm
+000
lim
P(On So)
1- +00
(29)
Combining equation 29 with equation 27 for any bounded set which does not include J (0lg(0) 0},
say that it has limit point almost surely. That means 0n J or 6, almost surely. We know the event {0,, convergence) is a tail event. By zero-one law, we have P((0,) is convergence)
0 1. That means {g(O,) either converges J almost surely, or diverges to infinity almost surely. Through Lemma A.4 we know P(O, - oo) < That proves {0,} } can only converge to J" almost surely.
A.6 PROOF OF THEBREM
First we construct a function R(0)- = 110 012 We can get that
R(On+1) R((,)) = =10n+1 - 001 - |0,, 0²11 = (0n+1 - 0n)²² (0 - On - -20")
=2(0n 0-)²² (0n+1 0,) + 110 0n = -((,, 00'²²0, + ||
-((,, - 0²) (Eo (g(.n. + en min Ko.TTNNN
+ +1100 Vg 6.. cov min
(30)
For the term 2(0,, - 8-) (co (.. (.) formation:
we use the following trans-
2(0,, 0r) (0) /1
26o
= =2cu(A,. - -2
(g((.))
(31)
+ m20o Na.
For the term (an
1| we can obtain
co ((n, + + min Ko)
= =g() Sn 2 minl Ko) En) No + NN min(g((x), Ko}
= e E ( Em. Fr + E6P
Kol Vg(on.
- - (i En || |
N2 min Ko) - 2op min Ko}
S..
2 2 [g( 2
E ([ (
2e V min K (g T
(32)
Then construct set
stho 10110- 0- 10 0..1000 }/10").
We also define event A;,, (0.g ((6) no E [ n]] ; and its characteristic function as Ji. We substitute equation 32 and equation 31 into equation 30 and multiple Ji,s getting
Tr (R(0 - R(O.)) > (2(2 po) 60.3-) ) J,, R(On)) IgnSon
22

---

Under review as a conference paper at ICLR 2023
where
= ==0=2000n- -00) (Vg(0n ) Vo((n)) + 20) KoTTn (0, 0-)
+ cbll Vg 11 2| - THT ( C.) + G,,,, min(g(On), Ko}
(33)
e.po min (g(0n) Ko}
Martingale difference. Denote p == (R(0n+1) R(B,)) 2 (2(2 po)c -o ) we
have
R(0n) 2 R(0,, + Iin 1(0n-1)(4imm14 - -1,+1)).
Then,
E (4an41R(0nnz)) -E -B( 2 Po (1.,. - E (R((0n+2)(1in) - 1i,n-))),
which implies
E (R((O+1)((snn ((x+t)))
1 po- E (Iint1R(Ontz)) 2
E (I,, R(On))
E (Tim R((n))
Assuming
E (R(On+t)(Lin - (in+t))) < po E (1.n)((0n))
lim sup
+00
we have
E ( R(0n+1)) - 400.
Note that this contradicted the E (1 Mln41R(On4Ha R(On+1)) S lo. Hence,
E (R((n+1) I,,+1))
lim sup +00000
2 Po-
(34)
E R(O,))
Define an event 40 = 10n E (s(o),
2 i}, and its characteristic function as 4,+00 We next
prove P( (imm-++00 10,00 1(0m) 0) =0
We assume P limm-++oo R(O, = =0) 1, and we can get Pl [iim R(0n)) = =0)
1. That means for any e/ > 0, P Is,n R(0n) 6))
0. concluding P ([in) S 6)) - 1.
Then we get
E (R((0m+ ([in lintt))
E(R(On+1) > i0 = Pr. (d0)
lim sup +000000
lim sup +o
E ((,n)(())))
J R(0)P., (d0) [ R.,)P... (d0)
JRIOSS, E(R(0n++)) > lo = P.
limsup n+++
SR P..))....
P0
Note that this contradicted equation 34 which implies P R()
R(OO)) = =0) = 0.
Through inspecting the event (0,, + gr }, we can get
400
(0, + + c
U
Au,t0
i=1
23

---

Under review as a conference paper at ICLR 2023
That means
P(O,. - -0) P
(0n - i
Ü m=1
toc
Altta)
400
P
U (0,, +0* A
t00
lim R(O,) = =0]
P
+1++00
t00
lim R(0m)) =0)
n-+00
1=1
A.7 PROOF OF THEOREM 3.4
First order 3% (07). ). Then Assumption 2.2 implies that V 0* J' there is (V > 0 (g smooth at A and E (0",, 80- )/(0")) }). That means for any Of * 0f E J", there 10 0j z
infa,y9 pt9, ||0| 87] = 8 + and U(07, da; (0U(077503) = 0. Furthermore, it means that there are most infinite {0;} We assign this number m. Due lim on [ > bounded. Then we construct function R((0) as follow:
know {do; is
Ro: (0) = ||0 0,1
Then we try to prove that there exists a function R()) satisfies:
1. For any Rdd there exist Hae such that 0T Hoo(R) s (maxaςesz ( + 1)) 11112.
2. R(()) | 07 Tot -o
when 0 near the 07.
3. R(()) is bounded.
We define indicator functions
(())
1, if 00 0-1 S
0, 00
0-
where ri an undetermined coefficient. Clearly, function 1/." Ro; (0) can be seen as an unary
function Joz (x) = x= +1 (0 < x < r:) about the independent variable ||0 - 0, Then for any 5u > 0, we can always find
hez (x) = +1 + (roz + 1)?r;; 2r
2
to ensure there is a smooth connection (a parabola) between fe; (x) and he: (x). Denote this entirety after adding the smooth connection between Joz (x) and ha; (x) as jo (r), jo: (x) satis- fied j"(x) < and the connection point on lo; (x) is fi(rs) = r. + (ra; + 1)r, rez Then let
hep (x) be an arbitrary constant value M, for different rep, can always get inverse solution
6o; r, = hg. (M) Take Ko := ming; eJa, (Tgz" Rop (8), 1}, there must exists K, < Ku, such that sets (U (. (Ko))} do not intersect. Then
(Pa(M (Ko)))
R((0)
Em
ooz
jo: (1l@ (1), if U. U(0), (Ko))
(35)
Ko.
others
is what need. We next discuss this problem case by case according the value of
24

---

Under review as a conference paper at ICLR 2023
The first case is f = 1 (from here to equation 38), we define an event
A
{0, E U ho (Ko))
(16) Then we can get that
and the characteristic function be n.8,"
(1a)) (R(0n+1)- -((,))) s - in.17 RIco n
[(((0))
+ 2Mo E([|un]] (| Fn),
2
(36)
(1)) AoRico R(On) + (10 Sn.
S n,0
2
where { is a Martingale difference sequence defined
====o\lVA((e))1 - on + +MMollual1
(((0,))
p(ln) where ko, bn are two constants. We also define r/- 11-1 Fn.o=- and obtain
Ko (P(00(P((x+z))) -(((0)) S T ((1 Ko S 1( (o- R((O))
R(On,)
1" (roy 11 2000
(37)
< 1 (1) i((0m))))
< 31 (a) P((O.).
(fa)
Through calculating the sum of equation 36 equation 37
we obtain
f((O+1)) - P2(0n)) S kohieo R((0))) + +3 (((0)))))))))))))))())))))))(() + E'..
E (F((0++))(F)) 5 5(1 kahieo + 37 R((n))
((a) where S', = Em n. En. Denote K' == kokicu/2, we get
R((++1)
R((O.)
Fr
MT (1 k'eu
k'eu + 31
II==] (1 keEu + 31 (1((
Through the upper martingale convergence theorem, we get
n-1
II K'EO + +316-00)
R(0,)) -
almost surely. By Theorem 3.1 we also Σt ((-1)) < too almost surely, which means
R(0,) o 0(1 - k'())")
almost surely. Denote
= 1 - KK'c 11
we have
i((0.) = 0 almost surely.
(38)
The second case when f > 1. Let
Far +1
i,
min Isism, Pegso
min
30. +
70r
5oz hog (Ko);
JJ.
2r(r + 1)G ag. E/
Then we construct set
(1)) (0/0= < 10 - 8:1 < i0
25

---

Under review as a conference paper at ICLR 2023
We also define event A (10 n.0 = {0, E s(ho)) and let the characteristic function be 7 n,0,
Then we can
get that
((6)) noo (R(0n+1) R(O.)) - In,0; hico
[VR((,))1 &.
(39)
R Tl (6n) + r(lo) Su. S - ((a) kohic0
2
where { is a Martingale difference sequence defined
Ea == (((e,) en + 2.oolls. 1 2M E(I [
(fa) and ko, k are two constants. Define -ff 1- Ex L.:07 we get
10) R - -0- (R(0n+1) R(O,)) S 16- S --
(0.):
(40)
where dg is constant. Through calculating the sum of equation 39 and equation 40
we get
R(On+1) - R((O)) s KohiED R + (0.) + 1, 10) 0g
R + +
6'
2
where غ" = -m (l(o) Sn. We also have
R((0+11) S i((On) 1 - 1--KR (0n) + (--b)aott m=1 Ea
R((O))
This
1=
En R(On)
(0 R (0n,) 1-k' (0n) an (0n,
(0m)
Using the inequalities (1 + x) 2 1 + row; (ro < 0); we have
R 2' R² (0n) + W - 1) (1
(1 +)
do
2
2R ((m))
Summing this over n, we have
R (0n+1) 2 (+,())) + Wl
7
10)
(1 f)
2 n (1
P)
0g
+
2 P+1
(0x)
Note that Σk=l (-1)) < too almost surely, thus we have
n
&) 2R (0%)
R (0m41) 2 2(n)
almost surely.
Denote
(1 - r)
2R (0n)
Clearly,
(r 1)2
&
sup E (115).111FF)))
sup E
Fn
< +ocalmost surely.
4
R (0x)
By Lemma
we have
(1 P)Ck
0 10 surely.
2R (Ok)
Then,
2 (0w) 2 22 almost surely,
which implies
s(O.) ((((0.)) O(" - - almost surely.
26

---

Under review as a conference paper at ICLR 2023
A.8 PROOF OF COROLLARY 3.1
When the loss function g(...) attains the s' accuracy, according to Theorem 3.4 the overall number of SGD iteration is
0 logg( ) 71 0 (
almost surely, if 1 almost surely, if > 1.
Then consider the computational time of single step of SGD. Generally, the main time- consuming part of one step is computing the gradient of loss function on a batch of datasets, which can be decomposed into computing No times of numerical differentiation, where the No is the size of the dataset. We assume time consumed of computing a function value is O(1).
When specific numerical differentiation scheme is given, such 0f(o()..- ,0000000............ 9= R3
09.
_0 o0 +h,... (((00_) it's obviously the computation time of numerical gradient is (d).
h In summary, the whole computation time is
(Nod log( +)) o (+)²
almost surely, if =
almost surely,
if > 1,
which is bounded by polynomial time.
27


Reviews:
[{"review_id": "uJTxJ6dvzv2", "reviewer": "Reviewer_5yze", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides theoretical results for the asymptotic convergence of SGD algorithm under an over-parameterized setting. It shows a set of assumptions that can guarantee the global convergence of SGD almost surely in some non-convex setting. ", "summary_of_the_review": "Although this paper show interesting results, I am not fully convinced by the assumptions and the intuition/reasoning behind the proofs. ", "strength_and_weaknesses": "The strengths of this paper are the theoretical results for the global convergence of SGD almost surely. The authors consider the regular sampling scheme and propose a new scheme (sampling noise with global stable guarantee). They prove the asymptotic convergence for SGD under a set of assumptions. \n\nThe weaknesses of this paper are: \n- This paper did not explain the intuition why SGD converge globally very well. The assumptions are not clearly motivated. The authors should explain why they have two set of assumptions on the gradient/ sample gradient of g. One is Assumption 2.1 part 4, line 2 where there is a lower bound on the liminf of gradient, the other is Assumption 2.2 where we put an upper bound on the sample gradient. Please add a discussion why the theory needs these assumptions and make sure they do not contradict each other. In addition, Assumption 2.3 is not natural when it asks that the constants $c_\\theta, \\hat{c}_\\theta$ are bounded away from 0 and by a constant of $\\theta$. \n- The presentation of this paper is poor. There are many notations and variables that were mentioned before the authors define them in the draft. For example: $M_0$ and $a$ were referred in Assumption 2.1 but only defined until 2.2, $\\tilde{\\nabla} g$ has no definition, 'global stable guarantee' was referred before the explanation,... Most of the time, the sketch proofs are confusing and they did not help to understand the thought process to prove the theorems. \n\nQuestion: In Theorem 3.4, what is 'the variant of Assumption 2.3 described immediately preceding this statement'?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "r1jeWKI37b", "reviewer": "Reviewer_XXfc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence property of SGD under the over-parameter setting. Under some regular assumptions of the loss and subdifferential gradient noise, this paper gives some novel results: (1) SGD must converge to a global optimum with probability 1. (2) SGD converges to a sharper global optimum not as easy as a flat one. (3) SGD achieves an arbitrary accuracy in polynomial time.", "summary_of_the_review": "The paper provides some novel insights on SGD’s optimization landscape. For example, the authors show interesting and important findings that SGD could indeed obtain a global optimum even in the non-smooth non-convex over-parameter setting.\nI have some concerns.\n(1) This paper studies square loss. Can these results be generalized to general losses?\n(2) What’s the difference between $\\tilde{\\nabla}$ and $\\nabla$. subdifferential?\n(3) Can the authors provide some numerical experiments to support the theory in this paper?\n", "strength_and_weaknesses": "Strength:\nThe paper is technically sound. \nThe paper studies an interesting question related to the over-parameterized problem and provides more understanding of the optimization landscape.\nThe theoretical results are important to the machine learning community.\n\nWeakness；\nMore discussion should be added after each Theorem.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jAdtNWfhhS8", "reviewer": "Reviewer_fVFB", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper claims that SGD converges to global minimum almost surely, under some assumptions.", "summary_of_the_review": "Based on the mathematical issues I found, I doubt the correctness of this theoretical paper.", "strength_and_weaknesses": "I have a few technical concerns on different aspects of the theoretical results in this paper.\n\nProblematic assumptions:\n\nAssumption 1: $g(\\theta)$ is already non-negative by definition, and there is no need for repitition. The actual meaning of smoothness needs to be made clear here ($C^1$ or $C^{\\infty}$ ?)\n\nAssumption 3: the set of roots itself is already a closed set, as long as $g(\\theta)$ is continuous which is implicit: one only needs to prove any limit point $x$ of roots $\\{x_i\\}$ is still a root. Suppose for contradiction $g(x)>0$, then by its continuity there exists an open neighborhood $S$ containing $x$, such that for any $x'\\in S$ we have that $g(x')>g(x)/2>0$. However, some root $x_N$ will fall into $S$ which finishes the proof.\n\nAssumption 4: this is a rather strong assumption in my opinion. The simple example $f(\\theta,x)=(\\theta-x)^2$ fails to satisfy the assumption, let alone neural networks. Even if the domain is restricted to be a compact set of $\\mathbb{R}^d$, the constant $c$ is likely to be a large poly factor in the dimension $d$. \n\nAssumption 2.3: can you give any example included in the large family of functions as claimed? \n\n$\\tilde{\\nabla}g(\\theta)$ is not defined. Is it an unbiased estimator of $\\nabla g(\\theta)$ or what? The model of SGD isn't explained either.\n\nMain results:\n\nI will only take Theorem 3.1 as an example. The argument in step 3 is doubtful: $\\theta_n$ might not converge at all with positive probability. Suppose I am the adversary that generates the stochastic estimator $\\tilde{\\nabla}g(\\theta)$, then at any root I'm allowed to generate $\\pm a v$ by Assumption 2.2 where $v$ is randomly drawn from the unit sphere. Then such sequence of $\\{\\theta_n\\}$ doesn't converge, and one can only talk about limit points. Unfortunately, even a non-root point can be a limit point if $\\tilde{\\nabla}g(\\theta)$ is an unbiased estimator.\n\nI suspect that the proof goes through when $\\tilde{\\nabla}g(\\theta)$ is exact and the randomness of SGD decreases with function value, as in equation (5). However, this is a very strong and non-standard assumption and I feel it's not what the authors mean.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "F1TInnzHUR7", "reviewer": "Reviewer_zzGL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper utilizes a method based on Clarke subdifferential and Lyapunov stability to show that SGD for an over-parametrized model converges to the global optimum almost surely under arbitrary initial value and some mild assumptions on the loss function. In addition, it is also shown that if the learning rate is larger than a value depending on the structure of a global minimum, the probability of converging to this global optimum is zero.", "summary_of_the_review": "This paper considers a fundamental problem in the convergence guarantee of SGD in an over-parametrized model. However, the paper is not well-written in its current form, which makes the reviewer hard to verify its correctness.", "strength_and_weaknesses": "Strength:\nThis paper considers two fundamental problems in learning, i.e., does SGD provably find the global optimum with an over-parametrized model, and why SGD prefers a flat global minimum? If all the claims (Thm 3.1, 3.2, 3.3) in this paper are correct, it is indeed a breakthrough in this field.  \n\nWeaknesses:\nHowever, it is hard for me to judge the correctness of the draft due to the following writing issue. \n\n1. There are so many notations used without definition. For example, $\\tilde{\\nabla}$ in assumption 2.1 (it means subdifferential?), $N_0$ in the proof of Claim 2.2 (number of samples in a batch?), $K_0$ in equation (5) and $\\zeta_n$ in equation (9).\n\n2. I did not see the importance of Claims 2.1 and 2.2, but they took up much space in the paper. Moreover, the sketch of Thm 3.1 seems to be disconnected from the preliminaries in section 2. \n\nI would recommend the authors add more insights and intuitions of the proof instead of the proof details and provide some high-level comparisons on why the proposed techniques could show such strong results. This paper considers two fundamental problems in learning, i.e., does SGD provably find the global optimum with an over-parametrized model, and why SGD prefers a flat global minimum? If all the claims (Thm 3.1, 3.2, 3.3) in this paper are correct, it is a breakthrough in this field.  \n\nSome related references are missing. I would like the authors to address how their approach and results differ from these papers. \n\nVaswani, Sharan, Francis Bach, and Mark Schmidt. \"Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron.\" In The 22nd international conference on artificial intelligence and statistics, pp. 1195-1204. PMLR, 2019.\n\nChizat, Lenaic, and Francis Bach. \"On the global convergence of gradient descent for over-parameterized models using optimal transport.\" Advances in neural information processing systems 31 (2018).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject