Improved Overparametrization Bounds for Global Convergence of SGD for Shallow Neural Networks
Authors: Bartłomiej Polaczyk
Jacek Cyranka
Venue: Accepted by TMLR ()

Abstract: We study the overparametrization bounds required for the global convergence of stochastic gradient descent algorithm for a class of one hidden layer feed-forward neural networks equipped with ReLU activation function. We improve the existing state-of-the-art results in terms of the required hidden layer width. We introduce a new proof technique combining nonlinear analysis with properties of random initializations of the network.

Published in Transactions on Machine Learning Research (03/2023)
Improved Overparametrization Bounds for Global Conver- gence of SGD for Shallow Neural Networks
Barttomiej Polaczyk
b. ppllecaakk@mmimuu..cuu
Institute of Informatics, University of Warsow
Jacek Cyranka
cyranka
Institute of Informatics, University of Warsaw
Reviewed on OpenReview: htips: // openreview. met/foruse id- Ry2g6w6FoE
Abstract
We study the overparametrriztion bounds required for the global convergence of stochastic gradient descent algorithm for class of one hidden layer feed-forward neural networks equipped with ReLU activation function. We improve the existing state-of-the-art results in terms of the required hidden layer width. We introduce a new proof technique combining nonlinear analysis with properties of random initializations of the network.
1 Introduction
The study of convergence propertics of mini-batch stochastic gradient descent (SGD) iterations applied to leed-forward neural nets (NN) is at the core of modern machine learning research. SGD with its variants like ADAM is the most common optimization scheme applied for supervised training of NN. principle however, the loss landscape encountered when training NN is highly nonconvex, especially for deep nonlinear NN as revealed, e.g., by visualizations performed by Li al. (0088) and construction proofs of spurious local minima by Auer et al. (1996ap; Brutzkus al. (2018). The nonconvexity may have severe consequences for practical NN training routincs, SGD may potentially get stuck at spurious local minimum saddle point and cease to converge further down the loss valley. Yet, practice suggests that with enough overparametrization, SGD iterations achieve global minima (i.e., perfect fitting of the training data) most of the times. This phenomenon is not fully understood yet and is the main theme of this paper.
Contemporary research on NN convergence theory was initiated with the study of linear networks. The loss landscape in this setting was fully characterized by Kawaguchi (2016), solving the problem stated by Choromanska et al. (2015) The rescarch revealed the feasibility of global SGD convergence for deep NN despite the loss landscape nonconvexity.
Even though it seems difficult to fully characterize the loss landscape in the nonlinear setting, proving the global SGD convergence is still feasible. Recent research suggests that SGD converges globally with high probability for random initialization of weights, under the assumption of sufficiently large overparametriza- tion expressed terms of NN layers' widths. The first result of this kind required an unrealistic level of overparametrization of polynomial order in the number of samples, cf. Allen-Zhu al. (2019). The following series of related results (see Table !| further reduced the required level of overparametrization using various techniques and assumptions training data. Especially in the case of Deep NN equipped with analytic acti- vation functions, an overparametrization of the lincar order with respect to the number of training examples is sufficient. However, such light overparamelrization results do not apply in the case of a non-differentiable ReLU activation function (see Table D Existing theoretical bounds still require a significantly larger number of parameters than used in practice. The question about an exact boundary marking the minimal number of parameters required for the global convergence still open even for shallow (one hidden layer) ReLU NN, see, e.g., Oymak & Soltanolkotabi
2020

---

Published in Transactions on Machine Learning Research (03/2023)
1.1 Main Contribution.
We establish new theoretical order of overparamelrization required for SGD convergence towards global minimizer for one hidden layer NN with ReLU activations, improving known state-of-the-art bounds. We introduce a new proof technique based on nonlinear analysis. First, we show the global convergence of continuous solutions the MSE loss. Second, using the existing nonsmooth analysis results, we establish closeness of continuous trajectories to SGD sequences sequences until convergence for a sufficiently small learning rate.
the differential inclusion (DI) being a nonsmooth analog of the gradient flow for
The concept of studying the dynamics of continnous solutions pursued in this work already appeared earlier (Arora et al. 2019a Du et al.) 2019b). However, the authors treated the convergence of SGD sequences independently from the analysis of contimuous solutions, which served motivational purposc only. We develop a rigorous method for establishing the convergence of SGD sequences via the convergence of continuous solutions, which works for general nonsmooth approximators including deep NN and general loss functions.
1.2 Informal statements.
We derive our global convergence results under the following assumptions and notation (made precise later on). We consider a shallow (one hidden layer) NN equipped with ReLU activation in the hidden layer and linear activation in the output layer. Let N be the sample size and denote do, d1, d2 the dimensions of the input, hidden layer, and output, respectively. The input data comes from the i.id. nab-Gaussian distribution on the sphere in R where du E [N N] for some du E (0, 1). The initial weight vector 6g (being vector obtained by flattening the weights of all NN layers) is oblained via. the LeCun scheme (variance scales with width). (()) is the MSE loss for some label matrix and weight vector 0. The subdifferential in the sense of Clarke is denoted by Ô and f is the Ω notation hiding the logarithmic terms. All presented results hold with high probability (WHP), meaning that the probability of the event converges to one as the number of samples N diverges to infinity, a convention widely adopted in the literature.
Our first main result provides a condition for the global convergence of the continuous solutions of the nonsmooth analog of gradient flow for L.
Theorem 1.1 (Informal Corollary 4.4).. Let the width of the shallow NN satisfy di = (251125)) Then, any solution 0: R4 - TK to the DT Cauchy problem ((0) = do, 0(t) E -aL(0(t)) satisfies ((((t)) s C(0(0)) exp(-ctd,) for all t 2 and some constant
WHP.
The second main result establishes the global convergence for the mini-batch SGD iterates WHP.
Theorem 1.2 (Informal Theorem 5.1 Let the width of the shallow NN satisfy di = ((N1.22). Then, for any error e > 0 and any mini-batch size, the mini-boteh SGD sequences with step size small enough achieve the loss value below E a lineor convergence rate WHP.
We obtain Theorem 1.2 via the following result. It is stated for general approximators (inchuding deep ReLU NN) and general losses (including hinge loss, cross-entropy etc.). We believe is of independent interest. We drop the assumption on the MSE loss and particular NN, and use the notion of an arbitrary loss L.
Theorem 1.3. (Informal Theorem 5.6) Let the loss function È be arbilrary salisfying some meld technical conditions. Additionally, assume there erists nonempty compact set Q, s.t. any solution 0 the DI 0(t) e -OC(O(t)) initialized in Q, remains in some compact set G and converges to zero as L(((t)) < ((0(0))e- Then, for any > 0, the SGD sequences initialized in Q and with step size small enough achieve the loss value below al a linear converyence rale WHP.
Let us comment briefly some key aspects of our results.
Overparametrization Bound Improvement.
Theorem 1.2 improves statc-of-tho-art overparamctrization bounds for global SGD convergence for shallow
ReLU NN
Table we compare to the selected works that we find most related. For instance,
Nguyen 2021 require dj S(N2). Similarly, Oymak & Soltanolkotabi 2020h require d, 2(N1/d8)
2

---

Published in Transactions on Machine Learning Research (03/2023)
(which is better for du larger than N2/3), where they train the first weight matrix only and the second weights matrix remains fixed, ef. Remarks 5.3 and 5.4 for a detailed discussion and Section C for numerical experiments comparing both setups. We also note that we have more general data assumptions than Oymak
& Soltanolkotabi (2020).
On the other hand, results from Kawaguchi & Huang (2019) and Liu et al. 2022 require only linear
overparametrization and work for more general data. However, they do not apply ReLU as they rely heavily on the smoothness of the activation function. In particular, analysis of non-smooth activation functions seems to be much more challenging task, see e.g., result showing the existence of spurious local minima in the ReLU setting Safran & Shamir 2018
Discrete vs Continuous Convergence.
The idea of establishing a link between contimuous solutions to the gradient flow and their discrete GD analogs for deep linear networks was introduced recently by Elkabetz & Cohen 2021). Their method require the Hessian to exist and to be bounded along the continuous trajectories. Such approach does not work when a nonsmooth activation function, e.g. ReLU, employed we provide additional evidence supporting this claim in Section g
Our approach of passing from continuous solutions to SGD sequences more general because it works in the differential inclusions setting, which treats nondifferentiable objectives (in contrast to Elkabetz & Cohen 2021
SGD step size.
One should keep in mind that Theorem 1.2 is qualitative it does not provide a constructive condition for the step size to guarantee convergence. However, existing quantitative results for ReLU NNs provide global convergence of the SGD scheme under the condition that the learning rale is of order O11/N²,, which is still far from the learning rates used in ML practice. Cf., e.g., Arora et al. (2019b]; Oymak Soltanolkotabl (2020 Nguyen 2021
Table 1: A Perspective related work. Reported resulta using notation O hides logarithmie terma, N is the number train samples, do is the imput dimension, L is the number of layers of deep NN
Work
Algorithm
ReLU
Deep
Data
Scaling
Initialization
2019
GD
yes
non degenerate
normalized
(12
LeCun
(1)N (shallow) fi(N + do do1.)) (deep)
Kawagnchi & Huang
2019
GD
n0
yes
normalized
LeCun
Daniely
2020b
GD
n0
no
gauasian
((N/da)
LeCun
Liu
SGD
yes
non degenerate
normalized
O(N)
LeCun
Allen-Zhi et al.
2019
SGD
separable unif. on sphere
LeCun
Arora et a)
20106
GD
yes
yes
f((N7)
LeCun
Zou & Gu
2019
SGD
yes
yes
separable
LeCun
Danicly
SGD
yes
unif. sphere
(u(N/da)
non-standard
Oymak & Soltanolkotbii
2020
(on layer 1)
SGD
unif. on sphere
fx(N1/4])
LeCun
((N?) (shallow) 0( (deep)
Nguyen
2021
GD
yes
yes
subgaussian
LeCun
Ours
SGD
subgaussian
0(x1
LeCun
1.3 Other Related Work.
We summarize the current literature concerning the question of SGD global convergence for NN equipped with the MSE loss in Table D We split the results into two groups, first the ones working for smooth acti-
Half of the weights of the first layer is initialized standard Caussians and the second half is copy of the first half. Half of the weights of the second layer equals some big enough fixed real number, while the other half equals to the negative of that number.
3

---

Published in Transactions on Machine Learning Research (03/2023)
vations and second, the results for ReLU activation function, also considered in this work. Similar and, in some cases, tighter overparametrivatinn
results have been established for training deep NN equipped with cross-entropy loss Li & Liang (018]; Ji & Telgarsky (2020 Chen et al. (2021). All existing results ex- cept Daniely (2020b) and Daniely (2020a) from Table ! are derived under the assumption that there is a significant. overpararmetrization of the NN under study (at least, one wide hidden layer). [Daniely] (2020a) provides an optimal bound but requires weights initialization that is far from standard, making the opti- mization process equivalent NTK optimization. Daniely (2020b) provides near-optimal bound (with an extra logarithmic factor), which however does not work for ReLU. Earlier work focused on the non-existence of spurious local minima without consideration of SGD dynamics Xie et al. (211)). The extreme case of
overparametrization. i.e., infinite layer width, has also been analyzed in Chizat & Bach 20188 Jacot et al. 2018 Mei et al. 2018).
One can also find negative results the literature, demonstrating, e.g., the existence of spurious local min- ima in underparameterized regimes, Auer et al. (1996b), or convergence towards spurious local minima, as in Brutzkus al. (0188) As for other fundamental properties, nonlinear NN universal approxima- tors Cybenko (189:; Shaham et al. (2018). NN memorization property has also been extensively studied in the case of shallow NN, known overaaamettriation bounds for perfect memorization of the data are
optimal Zhang et al. (2017): Hardt & Ma 2017); Nguyen & Hein 2018); Baldi & Vershynin
2019
Yun et al. 2019 ; Bubeck et al. (2220)
1.4 Organization of this paper
In Section 2 we introduce the notation and recall some facts regarding differential inclusions. In Section we study the properties of the DI solutions for MSE loss. In Section ! we prove the global convergence result for DI solutions under random initialization. In Section we extend the result of Section A SGD itcrates. In Section we present some numerical experiments related to our results. We summarize our findings in
Section i
2 Preliminaries
Let X Nxdo be matrix of the training inputs (arranged rowwise) and Y Nxda be matrix of training labels, where N E N4 = 1,2... is the sample size and do, d2 E N4 are the dimensions of the input and output respectively. Consider the following one hidden-layer feed-forward NN
Y dal (XW)V,
where for some d1 N+, W Roxd, and V Rdixd2 are the weight matrices and 6: R - R is the ReLU activation function applied element-wise. We often assume that X, Y are fixed and known from context, whence they are not explicitly mentioned as parameters, e.g., in the loss function formula. We denote the hidden layer by H, i..., H del @(XW) E RNd, We write D dodj + d,dg and denote parameter vector by e RP, i.c., f is obtained by stacking vectorized matrices W, V. We identify matrices with their vectorized forms and write simply 0 (W, V).
The standard dot product and Euclidean distance on Rd for d E N4, are denoted by (5-) and ||- For Rd and r > O, Blx,r) def { Ry: lyy æ|1 I r is the closed ball with radius centered at For matrix A E Rn. Ag. denotes the i-th row vector of A for E [nr]. and A₂ denotes the i-th column vector of A for E [mo], where [k]] = {l....,k) k} for & E N.. Finally, we denote the minimal eigen- and singular values of A by Amin (A) and omin (A), i.e., Tmin (A) = V Amiin (AT A), while the operator and Frobenius norms of A are denoted by ||Allop and |
Our aim is to optimize the MSE loss function L: D + R4, defined via 2()) 1 J - &1 The widely applied ReLU activation function non din-dfferentiable at x = 0 but the generalized derivative the sense of Clarke, cf. Clarke (1983), exists and is equal to the interval [o, 1]. More preciscly, let E N, and f: Rd R be a locally Lipschitz function. By Rademacher's theorem, the set D, of points where f is differentiable is of full Lebesgue measure. For Dj, denote the gradient of f(x) by Vf(x). Then, the Clarke
4

---

Published in Transactions on Machine Learning Research (03/2023)
subdifferential of at any point Rd is defined via
@f(x) "nt conv {y RR: y lim Vf(zn) for some Dj 32 2n "3 x
where conv is the convex hull operator. The Clarke subdifferential satisfies 0f(x) (V)(z)) for any I E Dj. We refer the reader to Rockafellar & Wets 2009h for detailed treatment of generalized gradients.
Recall that curve r: R+ + R is absolutely continuous if there exists map R4+ - that is integrable compact intervals and s.t. x(t) x00)= So u(s) ds for all t 2 0. To lighten the notation sometimes write =1(()= = a()) and call any absolutely continuous curve an arc. For a given xp E IR and f: R + I we are interested in finding ares x that are solutions to the following differential inclusion Cauchy problem
x (0) = zo. =(1) E -00(z((()) for a.c. 120
(1)
The following property plays a crucial role in analyzing such problems we say that satisfies the chain rule for any are x: R+ + Rd.
d { (0, =(t): ee 0f(z(t)))
d (f (t) for a.e. t 2 0.
(2)
dt
Consider the dynamics given by the following DI obtained from equation by taking ʃ f= L.,
0(0) = to. d(t) E -OC()()) for a.e. t O,
(3)
where On E R.P is some initial value. Note that a-priori it is unknown if there exists solution to equation defined the whole interval [0, x). Recall the notation H = @XXW). The following standard result is due to the fact that L satisfies the chain rule equation 2 cf. Davis et al. (022)), combined with usual arguments regarding DIs, subdifferential of L and Grönwall's s lemma. Since we were unable to find such statement that rigorously treats its existential component connected to the theory of DIs, we provide its detailed proof in Appendix
Proposition 2.1. For any initial Gg E IR,, there exists > and a solution 6: (O.T)) RD to the DI equation 3. Moreover, for any bounded domain G Gog each solution A to equation can be extended to infinity or up until it hits the boundary of G. Finally, for any such 0, denoting co(s) one gels
mat T (H*
((((t)) < ((((0)) exp ( (-2 f as) for every t E (0,7).
3 Dynamics of the Differential Inclusion
In this section, we show that the integral of the loss (square root) along the parameter trajectories de- termined by the DI equation 3 satisfies a simple one-dimensional differential inequality. From that we infer boundedness properties of the loss along trajectories. The constants appearing in the differential inequality depend on the initialization propertics only which allows us to provide WHP estimates in Section 4
Recall the notation H =<(XW) and (s(s)) = Jmin (HT (0(s))) By Weyl's inequality, ef., e.g., Theorem 4), and Lemma H.I
Dax
2013
(tu(t)= (0) < ((t) H s
& 11 ( W(
(4)
Therefore, to use Proposition 2.1 in lemuna below we bound the quantity || its proof, which is based on a careful application of Grönwall's lemma, to Appendix B
(((
W(0)] We defer
Lemma 3.1. Any solution 0: [0, T) - RR, 0 = (W, V), to the DT equation salisfies
10(()) e(0) < 1l (IIW (0)]l= |00))++ (I) exp (V2)
(5)
We the same symbols denate points and curves.
5

---

Published in Transactions on Machine Learning Research (03/2023)
for every t e (O,T), where C(t) So v [(((s) ds. Moreover
| ( - 1/2 (c + (2(t)))) (2)
exp (c(((t))))
(6)
for every 1 E (), where
X
X ((00)l, VO
2 (O)]e
||
(7)
Using Lemma and Proposition 2.1 we infer in the proposition below that loss trajectories along solutions to the DI equation 3 obey some specific differential inequality. This observation is crucial for obtaining the main results this paper, i.., Corollary 1.4 and Theorem 5.1
Proposition 3.2. Let C,C1,02 02 be as in Lemma 1
equation Set
((((O)))
def
Jmin (a (H(((()))))
(8)
If for some T 0, 0: (0,T) + RDD solves the DI equation y: (0, + R to the problem
then E(l) def So /c((s)) ds is solution
0 = 0: 5'(t) < a cxxp (at(civ(t) + c2n (2)
- a²t) for all t E (0,
(9)
Proof. Using Proposition
2.1 the incquality (u- - 8)² 2 u² -2lul for a 2 0, v E R, and the estimate
from equation we get for all E [O,
VC(e(t)) & VC((())) exp - (-1/ (s) ds)
S / [(O(O)) exp (a) + (0) / loo(s) - ao())) (co()))o0)))
ds)
$ (C(((0)) exp (- taa(0) + 2000 (0) /. |x HolloplW(s) W()) ds).
Using the bound from equation 6 due to Lemma 3.1 and noting that C'(t) = ((B(t)) we arrive at
[1()) S a exp
(- tta + 2x L. |x (()) ds
(- la" +a / + (c(()))(2((())))) exp (c(((s)))) ds)
Sa exp
and the conclusion follows by estimating C(s) s C(t) for all [0,t].
Perhaps surprisingly, due the double exponential dependence on y (t), a simple condition involving a, c, C1, C2 a determines that solutions to equation remain bounded by 2a/a² for all times, as demon-
strated in Lemma 3.3 below. This property is illustrated in Figure]
Lemma 3.3. Let a, C, be some arbitrory porameters of equation If a >> 0 and
acc (ot
d²o2 a
exp (4ca² /a 8'
1
(10)
then for any T 0, any solution y: [0, + I. to the problem from equation bounded from above by 2a/a² and its derivative at any time t E [0, T) is bounded by ae a21//2
Proof. Let y: T) + be any solution to equation g Sct
to inf {1 [0, T): (cIv(() eay (1)) = =a/2).

---

Published in Transactions on Machine Learning Research (03/2023)
By assumption y(0) 0 and > whence by contimuity of y, to > 0. Morcover, for a.c. t to:
(() - aexp (at(civ(())) + (t)(())
a²t) s ceexp--att/2)
whence y(1) S 2a/a² (1 - 11-2-))0/2) < 2a/a² for all 1 < to. If to < T, then by continuily of y [0, T),
y(to)= I 2a/a² as well, in which case
+ + (eal()))) 1
1
0C1 a
a² 02
exp (4ca² /a²)
8 4a
a
but this yields a contradiction with equation
Therefore to T desired.
Using Proposition 3.2 in conjunction with Lemma 3.3
we obtain in the theorem below the announced global
convergence guarantee for continuous parameter trajectories.
0.08
0.35
0.58
8 0.45
1174
0.48
174
1746
12.5
17.5
Figure I: Numerical illustration of the solutions equation for fixed c1, 02, and
[2.042, The color scale encodes It. is visible that the solution y(t) either
the values of 4(acs/o /a" + 2a 2a"e2/o" "x"")xx(eeo" /a*), ) the quantity determining equation
10
remains bounded or explodes rapidly depending on the condition involving the constants.
Theorem 3.4. Let a, a,a, be as in Proposition
3.
Assume that and that at initialization
GC1
c2
4ca 2
1
(10(0),,YY)
exp
(11)
8
Then, any solution 0: [0, T) RRD to the DI equation be extended to a solution on R4 and any such eatension satisfies for all 2
L(((t)) (()(()) exp(
(12)
and for u 4/X0)oo//((010)0000000
[0(t) (()) < =l|0(0)]le"
(13)
Remark 3.5. Theorem 3.4 provides a technical condition (equation 11 under which the global convergence of continuous solutions the DT is guaranteed, ef. equation 12 and that the solutions stay in the proximity of initialization, cf. equation 3 It is the foundation of all our subsequent results.
Proof of Theorem 3.4 If C(((0)) 0, then the result holds. L(((0)) 0, then set U(s) def 22a X olo (IIW (0) + [IV(0)] e x Xllap= and let G B(O(0), 20 (2a/a") 2a)aa)). By Proposition 2. there
exists T > O and a solution 0: [o, T) + R to the DI equation which can be extended up until hits the boundary of G. Assume that 0 is already such an extension. By Proposition 3.2 [(t) = f v ((((s)) ds
solves equation whence Lemma 3.3 asserts that if a > 0 and equation 11 satisfied, then L(t) is bounded from above by 2a/a² and ('(()= = C(O(t)) is bounded from above by ae ta2 for all E [0,
By Lemma 3.1 [|@(t) [()]] < U(C(t) < U(2//a²) for all t [O, so never reaches the boundary of G, whence T and equation 12 follows. Estimating [[W()]]] [[V(0]]| s /2]10(0)] gives equation 13 7

---

Published in Transactions on Machine Learning Research (03/2023)
4 Convergence of the Differential Inclusion Trajectories
To verify that equation holds WHP at initialization, we need impose some additional assumptions on the data matrices X, Y, and on the initialization scheme of 8o. In this section, all the complexity notations O, Q2 θ etc., are understood in terms of N approaching infinity, e-g., for any space. X and a function f:Ax + R, we say that f(z, N) = O(N) if [f(z,,) S CN for some constant C' > 0 and all x E.
Recall that a random variable 2 E I sub-Gaussiag 0: Exxp(=2 2/2) I 2} finite.
its Orlicz norm defined as | inf >
random vector Z E R" said to be sub-Gaussian 1 def
SuPtER" ||4]==1 (2, t) ya is finite. For more refined treatment of the Orlicz norms and mub-Gaussian random variables, we refer the reader to Vershynin 20180
In the sequel, we impose the following assumption.
Assumption 4.1.
1. Xg's are random i.i.d sub-Gaussian vectors s.I. ||xal22 via and |X O(1) for i E (N].
2. (Wo)ss ~ -N(0, ( for (i,5) E [do] [di] and some 3w >
3. (Vo)ay ~ (0, (?) for (i,j) E [41] x [dz] and some 3. > 0.
4. Wo and Vo are independent random matrices.
5. BwBe ((1).
6. = O(VT2) for i E [N].
The result below provides a lower bound on (o()). The proof is a slight modification of the argument from (Nguyen al., 2021 Theorem 5.1). Since we believe that there is a minor mistake in the proof therein (namely, in the integral estimates in Appendix E.1), we present our proof in Appendix C for completeness. We stress however that the main idea and authorship of the result is due to Nguyen et al. 22021
Thcorem 4.2. Under Assumption 4.1 let do E [No, , N for some 8g E (0, 1). Let V: V: [1,1,0 be s.t. d max (N, C(5u)d ( (NN) log"")])) (N)) for some C(ōu) > depending on 8u only. Then, there exists universal constant c(δo) depending on dg only, s.t. (0) 2 /c(ōo)dodi Bw holds with probability at least
- cxp((x - O(23) exp( (xN(-1(()))))).
The following lemma follows from standard concentration inequalities we provide the proof for completeness in Appendix D
Lemma 4.3. If Assumption is satisfied, then
Wolll ((Vvddd and ||Vol e @(Vd)3)3.)
with probability 1 2 2exp( ((dod)))) - 2 2xxp(=(((ddd)),
| = O O(/max(mmmmd doo)
with probability 1 1- exp((S0(max(a)) do))), and
((0,)= = O[| 1 log(N))
with probability. - exp(( (N))
Combining results from Sections and f we obtain the following result demonstrating the global convergence
of solutions to DI equation g towards zero loss under initialization satisfying Assumption 4.1 The full proof
is provided in Appendix P
8

---

Published in Transactions on Machine Learning Research (03/2023)
Corollary 4.4. Under Assumption 4.1 let 3. =d Let morcover c(5o) and C(ôn) be as in Theorem and
d for some p 2 0 and do (N ,N for some dg E (0,
d2 1/(1+p) log2(N))
d1 2 max ((òo)
dope
Then, any solution 0: [), + IR to the DI equation S can be extended to solution on R+ and any such extension satisfies
C(O(I)) S L(O(0)) exp ( L c(66)ded1) 1
for all t 2 0 with probability at least 1 - exp ( - N exp(-S(d2 (oold2logN)) log.)).
dg
d2N2. do
1/(ot)) -x(N))xxp((Q(NNN
Proof sketch. By Theorem 3.4 and Theorem 4.2 it suffices to verify that F(O(0), X, o(1). The last
condition is verified WHP by mcans of Theorem and Lemma
is technical tool we use in subsequent sections to obtain the SGD convergence guarantees. Yet, it is still of interest, as it allows us to deduce that under the standard LeCun initialization (st = 1/da, 1), the overparamctrization bound of the order (2(N1.255 is sufficient for the global conver- gence of the continuous trajectories. We comment more on comparison with other results in Remarks 5.3
Remark 4.5. Corollary
and !
5 Convergence of the Stochastic Gradient Descent Iterations
Let us consider a discrete version of the dynamics given by the DI Cauchy problem equation stochastic gradient descent. We start with introducing some additional notation.
g i.e., the
Let (E,F, be a probability space and consider function f:: RP x E - R, s.t. S(,s) is locally Lipschitz for all E E. Let 0o E IR' be random variable with absolutely continuous distribution function. For a fixed stepsize 17 > O, we say that a sequence of D --valued random variables (8%) is an f-SGD sequence if
6f = 0o: 0+ E 0% - (5(%) Ek+1) for l N,
(14)
where @f(0, s) is the Clarke subdifferential at point applied to the function + f(0 s) and (Ex) is a sequence of i.i.d. E-valued random variables distributed according to μ4, which are independent of Og-
For E [N], let [N](() denote the family of subsets of [N] containing exactly b elements and As ~ Unif( be random variable selecting each item from [N]() with the same probability. We define the loss function
Ch: RD (N] + IR+ for batch sample of size b E [N] via the formula (' A) 2 EieA llY 1.1. Therefore, an CDDSGD sequence any random sequence (0%) satisfying equation 14 with [N] and i.i.d. sequence & (n)(( for N4. We stress that this construction corresponds to the usual mini-batch SGD.
Corollary 4.4 states that, assuming enough overparametrization, the continoous trajectories given by the dynamics of the DI problem equation 3 converge to the global minima of the loss L if the initial value 0g is chosen properly, which happens WHP. In the theorem below we deduce an analogous convergence result for the SDD itcrates defined above.
Thcorem 5.1. Under Assumption
4.1 let B3 d," for some p and do, d1, d2, 8u, c(6o), C(ōu) be in 0, batch size b = b(N) [N] and any family ((0)) n > 0} of -GDDD
Corollary 4.4 Choose any error
sequences equation 1A
Then, there erists a step size no E (0,1) s.t. for a.c. E qu), C(0..) ) < E for some
N nb
max (0, log doogNN))dd,33 /2 c(6n)dod,
k*
1
(15)
where C >>0 O is some absolute constant. The result. holds with probability at least 1 1- eexp (- do 2 O(N2) exp() (XN622(()))/)) -ex((- log N)).
2/(0+))--
Ld
9

---

Published in Transactions on Machine Learning Research (03/2023)
Remark 5.2. Note that k* in Theorem 5.1 depends via log(1/E), ie., SGD converges to the global minima at a linear rate.
Remark 5.3. In order to compare the bounds obtained by Theorem 5.1 with other works, one has to take into consideration not only parameters B, but also scaling of the data matrices X and Y. E.g., Oymak & Soltanolkotabi (2020) works under the assumptions that ||X = 1 for i E [N] and Bw = which by the properties of Gaussian distribution corresponds exactly to our case X || = dd and Bw 1/vdo-
Remark 5.4. Corollary 5.1 under the LeCun initialization, 8 = 1 1/do: 18 = 1/d,. yields exponential loss
convergence WHP for d1 = (2(11.25). improving on d1 ((N2) due to Nguyen (2021). Similarly, under different but equivalent scaling, (0ymak & Soltanolkotabi 2020 Corollary 2.4) shows that overparametriza-
tion of the form dj [2(N4/dj is sufficient for exponential loss convergence, when only the first layer is trained for do E [VN,N], .N, whereas the second layer is fixed. Neglecting the logarithmic factor, one can see that our bound d1 = ((N1225 improves upon d1 = 32(N2/d) for 80 S 2.75/3 z .9,, including practical datasets dimensions. Moreover, our bound works also for óg E (0,0.5) and for any d2 (while they assume d2 = 1). Finally, a simple adaptation of our technique combined with some observations from Oymak & Soltanolkotabi 2020 allows to obtain the bound d1 12(N2//// in training one layer setup, cf. Appendix G
The main tool used to obtain Theorem 5.1 is the following abstract result, which claims that under some technical conditions on f and initialization scheme, the solutions to the DI involving f are WHP close in the supremum norm to the trajectories of the corresponding piecewise interpolated processes.
Theorem 5.5 (Banchhi et al. (2022)). For any probability space (E,F, let f: R x E R be s.t. for some function k: R + R,, the following conditions are satisfied:
V x E RD, Is 0, V 2,y E B(x,s), V&E,, (1 8) - f(z, 0)ll S n(x,, 8)lly - =||;
2. VEERR R, 3 K > 0, Be) e) S K(1 + |=]]);;
3. V KCR a.t.
suPEek (e= < x0;
K is compect
4. for a.e. X ERR,, I is C² in some neighborhood of x. Then, for any time horizon T > O, the following DI problem is well-defined
ō(l) E (0(0.) for a.e. L LE (0,7).
(16)
Moreover, if (00))Ke, > }} is a family of f-SGD sequences equation 14 initialized at random contin- uously distributed Oo, then there exists a set N C (0, oo) s.t. No is of zero Lebesgue measure and s.t. for every compact set K RD, time horizon T 0, and error 0,
lim P(30: [0,7] + RR" solving equation 16 ((0) E K, sup 00() - (*)) < | Go K) 1, tE|oTT]
70
where 8r is the corresponding random (measurable w.r.f. (EN) piecewise interpolated process defined, i.e., ('((t) def 0% (t/n () -0")
(17)
for all E [kn, (k + 1)m), EN
The following theorem built upon Bianchi et al. (202)) can be seen as a general tool allowing to pass (when deducing global convergence) from the solutions to the DI equation g to the SGD sequences given by equation 14 We state it for general approximators (including, e.g., deep ReLU NN) and general loss functions as we believe it is of independent interest. In particular, we drop the assumption on the MSE loss and the NN denoted by Y.
Theorem 5.6. Let L. IR + R for i E [N] be arbitrary locally Lipschitz functions satisfying the chain rule equation and being C² in some neighhorhood of a.e. point of R.D Set L EiejN Ex- Assume there episls nonemply compact sets Q CGC CRD s.l. any solution 0: [0, oc) RDD to the DI
0(L) E -ZC(0()) 0,
(18)
10

---

Published in Transactions on Machine Learning Research (03/2023)
if initialized in Q, remains in G and satisfies [(f(t)) v ((((0))e yt for all t 2 0 and some q 0. Choose
confidence threshold ō > 0, ervor e > 0, batch size b E [N], and family {(0%) k " 0} of LDD
sequences given by equation 14 where = = [N]e, P Unif([M]]) and L: RD x [N]] + R+ is given by
- -iEA (0). Assume that 8n is continuously distributed.
=
Then, there erists a step size yo E (0, s.t. for a.c. 1 E (0, P(Z(0))) < el0o E EQ) 2 1 - 5 for N k* S $11 vp max(0, log(E=-)
((0)))]-
Proof sketch of Theorem 5.6 Let def suPpeQ (0) and T enf (t 2 0: le
7t 1 E/2) = max (0, 1og(23/e)
so that all solutions to the DI equation 18 initialized in the set Q fall to E ([0, before time T (and
clearly never escape it). Set L. del
=sup ||l|| v E aL(0), 0 E G).
If we could apply Theorem 5.5 with the family [(0))e)) v > 0}, = min(e/2L, 1) and T 1 T it would yield that for any e 1), there exists no E (0, 1) s.t. for a.e. 17 = (0,
P(3 A solving d(t) E -EEL Ab) s.t. 8(0) E Q and sup |0(t) - (t) < É 8o E EQ) 21-6 - 5. LE[O,T]
Recall that As ~ Uni'([ and note that E, Ab) N/2 (-),, whence if (() solves O(1) E -OEI (0(t), Ab): then ((tN/b) solves equation 18 In particular [(((t)) S E/2 for any t 2 N T Therefore, as for E (0, 17)
it holds that T S nk < T. then for a.e. E (0,
[(0--) = =(0)))=((0'06 )) S ((((n))) + S
with probability at least 1- 8 conditioned on 0g E Q
However, in general C does not satisfy the assumptions of Theorem 5.5 In order to overcome this, we need to consider the set G and modify L outside of some neighborhood containing G, so that it becomes 1g initialized in Q remain in G, then it turns out that such modification does not conflict with the argument above, as is discussed in detail in Appendix
globally Lipschitz. As all solutions to cquation
We are ready to prove the main result of this section.
Proof of Theorem 5. For 0 (W,V) TR. and X E Vxdo, let ao(8 det m (onn(( and C(X, 0) ser
-||Y- - V(XWVVI F. Define
Q(x) (BERP:
aol xo(x, 0) 2 V((
((8,0) S Cdgd, B log(N), |10|| s C( + +V /ddd230).
where c(ōo) is the same constant as in Theorem 4.2 F is defined as in Theorem 3.4 equation II and C' >>> 0 is some big enough absolute constant such that
22.5 1/(+1)
do N
P(Oo E Q(X)) 2 1 exp (
) ((N3))(((( (xV(6(((/6)))) exp(-O0(a log N)),
d
which is possible in virtue of Theorem 4.2 and Lemma 4.3 cf. Proof of Corollary
4.4 For each X, let
loop }, that any solution to the DI 0 E -OC( if initialized in Q()), remains in the set G(Ò) B(Q()),U in virtue of Lemma 3.1 (cf., Proof of Theorem 3.4 Moreover, U(X) < oo by compactness of Q(X), whence G(X) is compact.
der uxXx 0) 2V /)/a/((Xx 0) and U del
SuPeEQ(X) { 2 x
For each X, apply Theorem 5.6 with Z(-) - -(X,), Q(x), 7 inf ag 0), 8 P(O, & Q()))
and G = G(X), to get that for some no E 10) and a.c. 17 E (0, no), P(C(X, 0
< <e E Q(x)) > P(Og e
Q(X)), where k* is as in Theorem 5.6 and whence bounded as in equation 15 Note that 1/0 depends on X only.
by the definition of Q(X).
Using the incquality P(A < (B)) multiplying both sides by 8, integrating w.r.t. the distribution
of X and estimating (1-8)² 2 1-26, we get that P(B E (0, 1) s.t. for a.c. 17 E (0, ((0).) < E) is at least 1 - 2P. & Q(X)), as desired.
11

---

Published in Transactions on Machine Learning Research (03/2023)
9.8
50-
40
40
40
40
30
0.6
8
8 30
8 30-
-04
20
20-
10
10
10
10
(a) Probability of convergence, (W, V) (b) Avg. number of num. zeros in final
(c) Avg. number of num. zeros in final preactivation, W only
training
preactivation, (W, V) training
Figure 2: Numerical results for both training sctups after 50k SGD Hterates.
6 Numerical Experiments
We present some numerical results illustrating two training setups when both layers (W, V) are trained and when W is trained only. As shown in (Oymak & Soltanolkotabi 2020, Section 4), it is expected that overparametrization of the order (d) is sufficient for global convergence of SGD iterations in case when only the hidden layer is trained. We complement their findings by analyzing the two layer training regime, observing that a similar phenomenon occurs empirically, thus showing that some further investigation of the optimization of shallow neural networks (beyond our Theorem 5.1 is still required. We also compare with a recent work Elkabetz Cohen 20011, , where the authors took approach similar to ours, i.e., they start with analysis of continuous solutions and pass from there to SGD iterates. We show that, in contrast to ours, in case of ReLU networks their approach based Hessian analysis along the trajectories cannot be applied, as these cross the boundaries of differentiability regions. Some additional findings are also reported.
6.1 Setup
Data is generated per single experimental run as follows: N 200, rows of X are i.i.d. from the unit sphere, d2 = 1 and labels Y are randomly chosen s.t. half are set to and the other half to -1. In the first training setup W has i.i.d. (00, 1) entries and V has i.i.d. (o, 1/d,) entries. In the second training setup W is as before and V is fixed - half of the entries are 1/vd, and half are -1/vdz as in Oymak & Soltanolkotabi (2020)- In all of the experiments we vary do, d1. The NNs are implemented within the Pytorch framework. We used the standard SGD optimizer (in fact, GD as the batch size is set to 200) with momentum (0.9). The learning rate differs on the training sctup and set to 0.15 (W only training), or 0.002 ((W, V) training).
6.2 Results
Figure
2n illustrates the probability of convergence towards a global minimum depending on the network configuration. The probability is approximated based on 10 independent runs and dg.d, grid spaced, the convergence criterion is ||g /ll/lyll 2.5 10-3 as in Oymak & Soltanolkotabl (2020). Compared with Oymak & Soltanolkotabi 2020 there seems to be no difference between training sctups in terms of convergence probability and it is supposed that the overparametrization O(N/do) is sufficient for the global we present the average number of numerical zeros (absolute values below 10-8) in the preactivation layer at convergence. Our investigation reveals an SGD optimization bias in both setups toward global minima with positive number of zero preactivation neurons (i.e., ReLU non differentiability points). In fact, these seem to be points of intersection of several ReLU activation pattern regions, as there are many zeros found. Note the different scales of the two plots the W only training setup results in order of magnitude more numerical zeros than in the case of (W,V) training. This in particular suggests that the training trajectories might cross many different ReLU regions and thus they would be far from the linear regime described in Elkabetz & Cohen 2021 Below, we investigate further this phenomenon.
SGD convergence. In Figures 2b
2c
We now turn to Figures g in which we analyze the training trajectories for both setups. is seen that despite being close to global minima (loss is already close to as seen on Figures 3a the number of numerical zeros in the preactivation pattern stays positive and is confined small range of values depending on the studied overparametrization level as presented on Figures 3b
3g
This confirms the observation above that
12

---

Published in Transactions on Machine Learning Research (03/2023)
the GD scheme prefers minima located close to the boundaries between several ReLU activation patterns. In fact, these seem to be corner points connecting several regions. We are not aware of any explanation of such a phenomenon in the literature. Moreover, despite being close to global minima, the activation patterns keep changing while performing the consecutive GD iterates before eventually stabilizing in some rogion. At which iteration that happens, depends on the overparametrivatioo level as presented on Figures 3c 3h This, particular, demonstrates that most of the shallow ReLU networks training scheme happens in the nonlincar regime, L.e, is not confined to single ReLU activation region until the very end stage of training. The activation regions keep changing in nonlinear fashion. Hence, the problem of studying the convergence of ReLU nets cannot be simplified to study within a linear regime as suggested by Elkabetz & Cohen (202
20=20,61-200..
20-20,d17752.d21
d0-20,d1-2028..0
(a) Loss values
(b) Number of numerical zeros (threshold 10-*) in the preactivation
(c) Hamming distance between ReLU indicators
(d) AC
(e) AY
of consecutive iterates
d==0,,1=2000
(0=10,d1=752dd22
d1-22228,222
(f) Loss values
(8) Number of numerical zeros
(h) Hamming distance between ReLU indicators
(i) AC
( AY
of GD Berates
Figure 3: Top row: training the hidden layer of the shallow NN only. Bottom row: training both layers of the shallow NN. The mumber of the hidden neurons is varied (the NN ronfiguration
provided in the legend) and the total number opnchs the evolution equal to 25k. The solid curve presents the mean from five independent runs, and the shaded region presents the standard devlation, plotted every 100th epoch. In Figures 3b Bg by the aumber of numerical zeros we mean the count of absolute values smaller than the given threshold in the hidden layer preactivation matrix (before applying ReLU).
Finally, on Figures 3d
3i
3e
3j
we investigated the relative loss change AC [C(0))- and the relative L(th, 1)
differential change measured in the operator norm AD- IDD where DÝ, is the differential of Ý [DDY--1lopp
(NN output) with respect to 0x (NN weights vector). is visible that the relative differential change is by order of magnitude larger than the relative loss change, suggesting that the training for moderate and larger overparametrization levels is far from the lazy training regime studied in Chizat et al. (2019). Where the
general criterion for the lazy training regime is given by AL >>>>> AD, cf. Chizat et al. 2019 Section 1.2).
7 Conclusions and Future Work
We have demonstrated an improved trainability overparametrization bound of order ((N11.25) on the hidden layer of shallow NN equipped with ReLU activation functions. We have obtained Theorem 5.6 an result allowing to pass from continuous solutions of the DI to the dynamics of SGD. We believe that contri- bution deepens the understanding of the optimization theory of NN. There are several natural directions of further rescarch and we list some of them below. First direction is towards the theory of deep networks, where one could try lo combine Theorem 5.6 with an analysis of DI dynamics in order to obtain improved overparametrization guarantees. Secondly, Theorem 5.6 might serve as a tool to obtain overparametrization bounds which are suggested by numerical experiments Soction D Finally, all known bounds for ReLU NNs are valid under strong, probabilistic data assumptions and it would be of interest to pursue directions of research that would allow for more general data such in the case of smooth activations, ef. Table 1
13

---

Published in Transactions on Machine Learning Research (03/2023)
8
Acknowledgements
BP and JC were partially supported by NAWA Polish Returns grant PPN/PPO/201//1/0000
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Procesdings of Muchine Learning Research, pp. PMLR, 09-15 Jun 2019. URL https://procceeddng/
htt.rpprees/v99/alleele zhullinn html
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Regresenlalions, 2019a. URL
https::/openreevie httpppppwwweeeeeeeeeeeeerrrrrnnc
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 09-15 Jun 2019b. URL https://
proceedings. mlr. wwt.pprrees///aaeee /ww.///rrraa9....m html
J-P Aubin and Arrigo Cellina. Differential inclusions: set-valued maps and viability theory, volume 264. Springer Science & Business Media, 2012.
Peter Auer, Mark Herbster, and Manfred K Warmuth. Exponentially many local minima for single neurons. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo (eds.), Advances in Neural Infor- mation Processing Systems 8, pp. 316-322. MIT Press, 1996a. URL http::/paperss wwtpsiccppppp.p.p..eeeepepppp cc/paper/ 102e wwweeniimmn---ssssi---eeeerooo .p
Peter Auer, Mark Herbster, and Manfred K. К Warmuth. Exponentially many local minima for single neurons. In D. Touretzky, M. C. Mozer, and M. Hasselmo (eds.), Advances in Newral Information Process- ing Systems, volume 8. MIT Press, 1996b. URL
http://pooceddnngg..errrr......p pdf..
Pierre Baldi and Roman Vershynin. The capacity of feedforward neural networks. Neural Networks, 116: 288 311, 2019. ISSN 0893-6080. doi:
0.00 URL https://www.
Pascal Bianchi, Walid Hachem, and Sholom Schochtman. Convergence of constant step stochastic gradient descent for non-smooth non-convex functions. Set- Valued and Variational Analysis, pp. 1 1-31, 2022.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over-parameterized networks that provably generalize on linearly separable data. International Conference on Learning Representations, 2018. URL httts:://pperrevieee wttp://wwwweeeoooorrdddddaaraaae
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. In Hugo Larochelle, Marc' Aurelio Ran- zato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL httppa://proceedings.t www.r/oceddingg.nuiis......////e wwtp:/iue...pppppr//////s/s hash/ 226990009a0/aaeee11550000111/111 www.rractt-stttttt..o html
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-parameterizaton is sufficient learn deep reflu} networks? In International Conference on Learning Representations, 2021. URL
http://wwwww.eeeeeooorrrrrddadde uZa6
14

---

Published in Transactions on Machine Learning Research (03/2023)
Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over over- parameteriieeee models using optimal transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Desa-Bianchi, and R. Garnett (eds.), Advances in Newral Information Processing Systems, vol-
ume 31. Curran Associates, Inc., 2018. URL https://proceeddins neurips. wttp:/cccaappe////e/eep/
(latc55Gas5/0067799430666/// Paperrr pdf
Lénaïe Chizat, Edouard Oyallon, and Francis Bach. pp. 2933 2943, 2019.
lazy training in differen- URL http:://paperr..ns..ccc.co
On
tiable programming.
8559-021 1er19-on-layy-- waw--aa-taaaaiinngggeeeea-a
Anna Choromanska, MIkael HenalT, Michael Mathieu, Gerard Ben Arous, and Yann LeCun. The Loss Surfaces of Multilayer Networks. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Bighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pp. 204, San Diego, California, USA, 09-12 May 2015. PMLR. URL https://proceeeding. mlr, pressvre vv8/ choromanska15. / html
F.H. Clarke. Optimization and Nonsmooth Analysis. Wiley New York, 1983.
G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303 314, Dec 1989. ISSN 1435-568X. doi: 10.1007/BB02255224.. URL https://doi.oon org/ 10. 00.100//FF22552744
Amit Daniely. Neural networks learning and memorization with (almost) no parametttttii....onnn... In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Pro- cessing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020a. URL https::/prooceddnggs.
Amit Danicly. Memorizing gaussians with no over-paramcterizzion via gradient decent on neural networks.
arXiv preprinl ar Xiv:2000 1 12895, 2020b.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 2253 2261, 2016. URL httpss:/prroceednngs.. wwtpp:ttpppppppppppppeeeeeepeeee haass// Autuu--bbbrrtt..... html
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D. Lee. Stochastic subgradient method converges on tame functions. Found. Comput. Math., 20(1):119-154, 2020. ISSN 1615-3375. doi: 10.1007/ s10208-018-09409-3 URL https://doi org/10. 10771110000--00880004999
Achiya Dax. From eigenvalues to singular values: a review. Advances in Pure Mathematics, 2013, 2013.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep noural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (ods.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, PMLR, 09-15 Jun 2019a. URL httpps://proceedingss mlr. www.ppressvvviee http://sg...ll..pees/////////// biteess/v9/ddllc..tt
pp.
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. Open Review.net, 2019b. URL httpppss//pperrreiii..eeee/////
id-S1ek3109YQ
Omer Elkabetz and Nadav Cohen. Continuous vs. discrete optimization of deep neural networks. In Thirty- Fifth Conference on Neural Information Processing Systems, 2021. URL https://oppnrrvier..o
15

---

Published in Transactions on Machine Learning Research (03/2023)
A. F. Filippov. Differential equations with discontinuous righthand sides, volume 18 of Mathematics and its Applications (Sowiet Series). Kluwer Academic Publishers Group, Dordrecht, 1988. ISBN 90-277-2699- Translated
X. doi: 070007997-94--5-7799-- URL http::///oo....o//00000000//0000 from the Russian.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL hattps://operreeee
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biancht and R. Garnett (eds.), Advances in Newral Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018. URL https://proceedings www.oeiiinnnnn.iis...... nwwripe..rcccceeooooo coor:ipp.ccpppppr/00////111 .dd.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. In International Conference on Learning Representations, 2020. URL https://openreviien wwtp://ee//ooomiiii/ie/ea Hygegyyro
Kenji Kawaguchi. Deep learning without poor local minima. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnelt (eds.), Advances in Neural Information Processing Systems, vol- ume 29. Curran Associates, Inc., 2016. URL http:://ppoooccaagg..ooooooocopp
21C99966711229905111111333330 Paper .dff
Kenji Kawaguchi and Jiaoyang Huang. Gradient descent finds global minima for gencralizable deep neu- ral networks of practical sizes. In 57th Annual Allerton Conference on Communication Control, and Computing, Alleroon 2019, Monticello, IL, USA, September 24-27, 2019, pp. 92 99. IEEE, 2019. doi: 10.110//ALERTTNN 20..EERROO..011.80 8019.8919696. URL. https::/ddt/ org/10. 1109 ALLERTON 2019 8919696
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neu- ral nets. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett (eds.), Ad-
vances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: //proceedings.
itwpeeeddinnnnnnnuniieeeeee neur httpa///cee/a/e////eeeaaaa00066e
.p pddf
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Biandn and Roman Garnett (ods.), Advances in Neural Information Processing Systems 31: An- rual Conference Newral Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8168-8177, 2018. URL. https://prroceddnn wwwpeeddinnnnnuuiis..... www.neeeuu.eeeeeeeeeeee pttprp//scccppppp/////aaaaalll 3fte776aa176c11eee445557922222 htt.:/6sa--btttttt..hca. html
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applicd and Computational Harmonic Analysis, 2022. ISSN 1063-5203. doi: https://dbi..org/10000/////
ccienee/arracee/l1///s5500000000 wttp:///...aa.......2.... URL htttp:://ww..ciiencediie com/
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, E16333).77665-77777 2018. ISSN 0027-8424. doi: 10.1073/ 21133/pmas.168 pon.ss1006579115 URL https://www http:///www.naa..ooom ppaas.org/coontee//15//////////
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with lincar widths. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8056-8062. PML.R 18 24 Jul 2021. URL htttps://proceeddngg: mlr pwtps//vw3//guueerrrrrer
html
Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep cnns. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Slockholm, Sweden, July 10-1 10-15, 2018, volume 80 of Proceedings of Machine
16

---

Published in Transactions on Machine Learning Research (03/2023)
Learning Rescarch, pp. 3727-3736. PMLR, 2018. URL http:://poooeedunn.....rpp//////
html
Quynh Nguyen, Marco Mondelli, and Guido F. Montúfar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event,
volume 139 of Proceedings of Machine Learning Research, pp. 8119 8129. PMLR, 2021. URL http: V/proceedings. mlr. wttppp//v1///////eo//2e22. html
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterriattoo:: Global convergence guarantees for training shallow neural networks. JEEE J. Sel. Areas Inf. Theory, 1(1):84-105, 2020. doi: 1111009/jaat.2220.299909
URL https://doi.orgg 1109/jsait 2020. 2991332.
R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
1. Safran and O. Shamir. Spurious Local Minima are Common in Two-Layer ReLU Neural Networks. ICML 2018, 2018
Cri Shaham, Alexander Cloninger, and Ronald R. Coifman. Provable approximation properties for deep neu- ral networks. Applied and Computational Harmonic Analysis, 44(3):537-555 557, 2018. ISSN 1063-5203. doi:
URL http:///www.cceeneedrret.....m http://reee..eoo/cccce////araaaa
p11/S1063550316300033
Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math., 12(4): 2012. ISSN 1615-3375. doi: 1010007/110088001--0099. URL https://doi.org:: 1007/
81 610208-011-9099-
Roman Vershynin. Higl-dimensional probability, volume 47 of Cambridge Series in Statistical and Prob- abilistic Mathematics. Cambridge University Press, Cambridge, 2018. ISBN 978-1-108-4159944, doi: 10.1017/978110929 108231596. URL https://doi. /tt////i.og/////////// 1017/9781108231556 An introduction with appli- cations in data science, With a foreword by Sara van de Geer.
Bo Xie, Yingyu Liang, and Le Song. Diverse Neural Network Learns True Target Functions. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1216-1224, Fort Lauderdale, FL, mlr.
USA, 20-22 Apr 2017. PMLR. URL http::/pproceedingn
html
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Achéé- Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancowver, BC, Canada, pp. 15532 15543, 2019. URL http:::://ppoocedngg.... neuriss..ri...... wttppp..ccppppppe cc/paper//119/ hat1://be40002227777711117777777
Abstractt...tt.......m...m...... html
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.ne,, 2017. URL https: : /ttp::///peeeieeeeee
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterrzeed deep neural net- works. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Newral Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancou- ver, BC, Canada, pp. 2053 2062, 2019. URL http:::// https://proceednngs.et http::gg...rerreec..ppp/p/////// 2a6.ad222002a166555500222222//12 www.rraaa-aatttt..tt.m.m html
17


Reviews:
[{"review_id": "KOQJxhZ0HQ", "reviewer": "Reviewer_Uxfn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The analysis in this paper is exceedingly clear. Many of the results follow from straightforward arguments presented in the appendix and some are short enough to prove in the text. Given the strength of the results, I think this is a real accomplishment. One thing I believe could be improved (though, in part, this is due to my own deficiency) is the discussion of the implications of using a differential inclusion as opposed to an ODE for the parameters or a gradient flow (as in the case of the infinite width limit). \n\nThe biggest weakness from my perspective is the numerical experiments. In fact, I would be satisfied with this paper if the numerics were not present at all. The authors check that the convergence occurs with high probability when the hidden layer is sufficiently large---indeed, this is consistent with global convergence but I don't see how it probes anything directly related to the analysis. There is a lot of focus on the number of zeros in the trained preactivation (or inactive units). I do not immediately see how this is connected to the convergence results. I understand that the authors want to provide some contrast with Elkabetz and Cohen, but I am not sure that these experiments are really necessary for that. There is a large literature explaining the difference between the linear regime and nonlinear regime, including the papers already mentioned in the manuscript by Chizat. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper improves existing asymptotic bounds on the extent of overparameterization required to ensure global convergence for single hidden layer relu networks trained with SGD. In the continuous time case, the authors formulate the training process as a differential inclusion with the time derivative of the parameters as the sub-gradient of the population loss function. In this case, a convergence rate that improves with width is also provided. The authors obtain these bounds by first analyzing the dynamics of the differential inclusion and then extending their results to the discrete time case by proving a theorem (5.5) that allows to the authors to bound the sup norm between the continuous time trajectory and the discrete time trajectory. Ultimately, the authors obtain a scaling that the width of the hidden layer should be $d_1 =  \\tilde{\\Omega}(N^{1.25})$ which is an improvement over more general bounds and even other bounds that focus on single hidden layer relu. There are a number of numerical results presented: I was not entirely clear on the intent or meaning of these, as discussed below.  ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think in order for this paper to be presented clearly to a broad audience, slightly more background on differential inclusions could be added. At least some statements of what a \"solution\" to a DI problem means would be helpful to many readers, I believe. I am not suggesting that the authors write a separate primer on DIs.\n\nI am not sure why there's not an attempt to study the scaling results numerically. The current set of experiments is not clearly presented, so if these are really informed directly by the analysis, then it would be nice to have a much more transparent assessment of their utility. \n\n Minor, but the notation $2.5e - 03$ should really be $2.5\\times 10^{-3}$ for clarity. ", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lmtC8JJkk2", "reviewer": "Reviewer_fTpx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The math in the paper seems correct, and the problem studied is of interest to the community. \nHowever, I have three main concerns:\n\n1. The literature review misses some relevant work by Daniely on \"memorization with (almost) no overhead\", see https://arxiv.org/pdf/1911.09873.pdf and https://arxiv.org/pdf/2003.12895.pdf . In the first of these two papers, the data points x are assumed to be drawn from a Gaussian distribution, and memorization of SGD-trained networks is proved with d_1 = O(N / d_0), which is a better rate than the one in this paper. Since the assumptions are similar in this paper (the main difference being Gaussian x vs. sub-Gaussian x), the authors should discuss the differences between their result and proof ideas and those in Daniely.\n\n2. I am having difficulty understanding what are the new elements in this analysis. The main elements of this analysis are in Section 3, 4, 5. But it seems like the arguments in Sections 4 & 5 may already be known. The authors should be more explicit about what has been done before vs. what is new.\n\na. It seems that Section 4 follows from a known lower bound on the minimum eigenvalue of the NTK at initialization via general lemmas shown in Nguyen et al. 2021.\n\nThese lemmas are in the appendix as Lemma C.1 and Lemma C.3 and are re-proved, although it not clear why since they already appear in Nguyen et al. 2021. In the main text it is also stated that the proof is a slight modification of the argument of Nguyen et al. 2021. Could the authors please be more explicit in explaining the differences with that work? \n\nFinally, the last ingredient of Appendix C is Lemma C.2, which lower-bounds the magnitudes of the Hermite coefficients of the ReLU activation function. This lemma follows from the explicit formula for the Hermite coefficients of the ReLU. See Appendix A.2 of https://arxiv.org/pdf/1910.04970.pdf, or Lemma 11 and page 18 of of https://arxiv.org/pdf/1602.05897.pdf .\n\nb. It seems that Section 5 is also a direct application of a result of Bianchi et al. 2022.\n\n3. The presentation of the result has many technical details in the main text. It would help the reader for them to be put in the appendix, so that in the main text the authors could focus on the key elements of the proof.\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies what width is required for an SGD-trained neural network with 1 hidden layer and ReLU activations to fit the training data. The assumption on the data is that it is drawn from a subgaussian distribution. The result is that a width of d_1 = O(N^{1.25}) on the hidden layer is sufficient to memorize the labels for N training examples.\n\nThe proof proceeds by: (1) in sections 3 and 4, studying the gradient flow solutions and proving that they have to be bounded in a compact set. (2) using the analysis of gradient flow solutions to compare to SGD using a theorem of Bianchi et al. 2022 for comparing gradient flow solutions to SGD sequences.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "\n\n* In this sentence: “Yet, practice suggests that with enough overparametrization, SGD iterations achieve global minima most of the times”. By global minima do you mean just that the training data is fit?\n\n* In this phrase: “which is better for d_0 in a small neighborhood of N\", do you mean, \"which is better for d_0\" larger than N^{2/3}?\"\n\n* Please streamline this sentence, since it is confusing: \"However, existing quantitative results for ReLU NNs give to the best of our knowledge no better bound than O(1/N^2), which is still far from the learning rates used in ML practice\". \n\n* Appendix B, equation (23), last line should be an inequality\n\n* Between equations (8) and (9), missing a parenthesis in \\sqrt{\\cL(\\theta(s)}. Parenthesis also missing in first line of proof of Proposition 3.2.\n\n*  In Figure 1, please add comparison to the theoretical bound, since the caption mentions it but it can't be seen in the figure. Or at least justify \"Observe that empirically the upper bound is smaller than the derived theoretical bound.\" without having the reader do the calculation.\n\n* The argument in Lemma 3.3 is hard to read. Please simplify it, especially considering it is in the main text. It took a minute for me to parse why the last line is a contradiction, because the exponent of alpha in the denominator at the end is different from the one in (10), which threw me off. Also, in equation (11) in the statement of Theorem 3.4, the same expression as (10) appears, but with different constant factors. These small changes are distracting and it would be better if, e.g., you just stated (10) as you state (11) and just called on (10) in the statement of Theorem 3.4.\n\n* In Assumption 4.1, \"W0 and V0 are independent random vectors.\", these are matrices, right?\n\n* In Assumption 4.1, please instead make \\|Y_{i:}\\|_2 be O(\\sqrt{d_2}) at initialization, so that this holds without assuming Le Cun initialization. You can immediately switch to LeCun initialization if you'd like and in the proof you can use that \\|Y_{i:}\\|_2 = O(\\beta_w \\beta_v \\sqrt{d_0d_1d_2}), but this looks very strange as an assumption.\n\n* Theorem 4.3 typo, \"for some and C(\\delta_0)\".  Appendix C typo, \"We not turn to the\", \"for for\". Appendix E typo, \"tha fact\" \n\n* Equation (14) should be \\theta_{k+1}^{\\eta} \\in \\theta_k^{\\eta} - \\eta \\cdot \\partial f(\\theta_k^{\\eta}, \\xi_{k+1}) ?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2UECbnT5Ov", "reviewer": "Reviewer_7vWr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts: improved over-parameterization requirements by leveraging a continuous-time analysis\n\nWeaknesses:\nOne missing aspect is a characterization of the step-size needed for SGD to succeed. Currently Theorem 5.6 is of the flavor \"there exists a step-size $\\eta_0$, due to the asymptotic nature of Theorem 5.5, so it is unclear how small $\\eta_0$ needs to be for optimization to succeed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies sufficient bounds on over-parameterization for achieving vanishing training loss for two-layer ReLU networks trained via (stochastic) gradient descent on arbitrary data satisfying certain regularity conditions.\nThe obtained bounds improve on previous works which considered the ReLU, in particular Nguyen (2021) and Oymak & Soltanolkotabi (2020). Importantly, the result relies on a continuous-time, non-smooth analysis of the differential inclusion analogous to the gradient flow, which avoids discrete time analyses which seemed to incur additional need for over-parameterization in previous works.\nThe continuous-time results are extended to discrete-time through appropriate mini-batch SGD discretization, adapting results from Bianchi et al. (2022), and experiments are provided to illustrate the findings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* it would be helpful to provide more insight on what the step-size needs to be in order for the SGD results to apply, if that's available, or at least comment on this issue\n* Theorem 1.1/1.2 are a bit hard to parse without reading what follows, could you define the setting and architecture used more clearly before stating them?\n* some comments would be welcome after Corollary 4.5, since that's the first place where the over-parameterization bounds appear. In particular, perhaps some of the comments in Remark 5.2/3 could be moved there? Similarly, a brief discussion after Theorem 3.4 would be a helpful addition.\n* legends are difficult to read in Figure 3, please increase the font or make the plots bigger.\n* could you define more clearly what you mean by \"number of zeros in final preactivations\"? are these the number of $(i,j)$ such that $w_j^\\top x_i \\approx 0$?\n* what is $D Y$ in the definition of $\\Delta D$? Could you explain further why the proposed characterization of lazy vs active training ($\\Delta L \\gg \\Delta D$) is valid, or where it comes from?", "broader_impact_concerns": "no", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agreed that this is a technically interesting work, which contributes to existing literature by providing an important improvement that further closes the gap between upper and lower bound on this basic problem. While some parts of the proof technique appeared in earlier works (e.g. Nguyen et al, Bianchi et al), the authors appropriately acknowledge the existing literature. It is therefore recommended for acceptance at TMLR. 

Decision: Accept (poster)