Convergence beyond the over-parameterized regime using Rayleigh quotients
Authors: David A. R. Robin
Kevin Scaman
Marc Lelarge
Venue: NeurIPS 2022 Accept (2022)

Abstract: In this paper, we present a new strategy to prove the convergence of Deep Learning architectures to a zero training (or even testing) loss by gradient flow. Our analysis is centered on the notion of Rayleigh quotients in order to prove Kurdyka-Lojasiewicz inequalities for a broader set of neural network architectures and loss functions. We show that Rayleigh quotients provide a unified view for several convergence analysis techniques in the literature. Our strategy produces a proof of convergence for various examples of parametric learning. In particular, our analysis does not require the number of parameters to tend to infinity, nor the number of samples to be finite, thus extending to test loss minimization and beyond the over-parameterized regime.

Convergence beyond the over-parameterized regime using Rayleigh quotients
David R. Robin INRIA École Normale Supérieure PSL Research University david a. a. robin@gmail.......o com
Kevin Scaman INRIA École Normale Supérieure PSL Research University kevin. scaman&inria.
Mare Lelarge INRIA
École Normale Supérieure PSL Research University marc. -elarge@enss...... fr
Abstract
In this paper, we present new strategy to prove the convergence deep learning ar- chitectures to zero training (or even testing) loss by gradient flow. Our analysis is centered on the notion of Rayleigh quotients in order to prove inequalities for broader set of neural network architectures and loss functions. We show that Rayleigh quotients provide unified view for several convergence anal- ysis techniques in the literature. Our strategy produces proof of convergence for various examples of parametric learning. In particular, our analysis does not require the number of parameters to tend to infinity, the number of samples to be finite, thus extending to test loss minimization and beyond the over peer-prraettrized regime.
1 Introduction
In order to understand the performance of vastly over-parameterrized networks, various works have investigated the properties of neural tangent kernels (NTK, see Jacot et al., 2018) and their eigenspaces. While the study of these spectra has led to proofs of convergence global minima despite the non- convexity of the problem, these analyses typically rely on an pweeeaaramttrizzaioon assumption, even infinite-width limits, casting shadow their applicability. NTK in particular, granted by the infinite width limit, does not hold with finite width and a growing number of samples, despite observed successes of neural networks in this regime. We provide a (toy) counter-example in dimension two to better outline this issue, and fix this flaw by re-centering the discussion on Rayleigh quotients, corresponding fixed directions, rather than positive definiteness, iee. uniformly bounding in all directions. We give several ideas to obtain bounds on Rayleigh quotients, and provide non-trivial examples for each of the presented ideas, including a recovery of known results, but also new convergence speed guarantee for the multi-class logistic regression.
of the
Overview. In typical supervised learning task, one is given training dataset of N la- beled samples D ((z,, yi) E Rd x RK and parametric model with m E N parameters, f: IR x RRd - R. The task is to find parameters fitting the training data, i.e. find 0* E R. such that Vi E [m). f00;; Rs y/- Aggregating these into single vector F 0 +ー fo (f .r (:)))s(())> this becomes satisfaction of system of equations F(0) y E. After choosing functional loss e: I - R,, one can learn the associated parameters by gradient flow 0,0 xm This corresponds exactly where the jacobian of the parameterization F is matrix DF E to the usual practice of defining a parametric function F. a functional loss E, and training by gradient flow on the parameters to minimize the parametric loss = éo F. The question is then when does this algorithm converge, and how fast ? Our focus is the regime of finitely many parameters (m E N) and large data (n >> +o.), where the over-parameterizatton arguments (m > n)) are insufficient.
D (()) vE(F(()).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Context. Early arguments for the proof of convergence of this system to loss of zero revolved around strong convexity hypotheses on the loss [see Boyd and Vandenberghe, 2004, Section 9.3.1]. However the parameterization F, typically as a neural network, leads to non-convex parametric losses & even when the functional loss & is convex, sometimes even parametric losses that are not locally quasi-convex [for details, see Liu et al., 2022]. Recently, a common solution has been the leverage of Lojassswjjiiiiic inequalities (0) 2 μu (0), which grant linear convergence by integrating with Grönwall's lemma since for gradient flows it holds -0, = V 2 (thus for E Ri+ -0) 2 μ [() + ((,,) S [(0) exp(-u()). For examples in continuous time, see Chizat [2020. Theorem 3.3 and 3.4]. Other results with discrete time include Arora et al. [2019, Theorem 4.1]. Oymak and Soltanolkotabi [2019, Theorem 2. Liu et al. [2020, Theorem 5.1] and Liu et al. [2022, Eq (3)] Generally speaking, discretized versions with sufficiently small learning rate have very similar dynamics, at the cost of some local smoothness assumption, and similarly, stochastic versions can leverage the same Eojasiewicz inequalities to prove convergence rates, so the continous-time dynamics proof can be viewed as a first step in the analysis of these more complex cases. These inequalities ensure that there are critical points that are not global minima, and can hold even for non-convex losses L, although they can be hard to prove.
The behavior of the dynamical system 0,0- -V) has been shown to be closely tied with the eigenspaces of the Neural Tangent Kernel (NTK) matrix ((0) = DF(0) DF(()) E R=*" introduced in Jacot et al. [2018, Section 4]. More precisely, the local decrease of the loss is -d,c(0) = Ve(.fo) (0)) fe). As an example, for the quadratic loss, the gradient satisfies [[VE(fa)] = (f)))) (0), such that positive definiteness condition (0) = l >> 0 guarantees the Dolyak-L.ojssewicc condition - (0) 2 4p (0), and thus by integration, convergence to zero with linear convergence speed. Several works, starting with Jacot et al. [2018, Proposition 2] but also Du et al. [2018], have shown that the smallest eigenvalue of this K(O) operator is indeed strictly positive if the network is sufficiently overparameterized (m >> n). Subsequent papers have also anayzed how overperameterized the network needs to be for this argument to hold, with interesting asymptotic bounds on the number of parameters required [Ji and Telgarsky, 2020, Chen et al., 2021].
Challenges. However, this argument for convergence is bound to fail when there are fewer parame- ters than datapoints (m <; n). In particular, for a fixed number of parameters m E N, it is impossible to have both n - +oo and Amiu ( (0)) > O, since ((0) E R=*x" has rank m < n by definition. As argued by Liu al. [2022, Proposition 3] for the quadratic loss (e: f + |f - ylا.. satisfying Ve(fo) 2(Fo y) E "R,",, this implies that for underparameterized systems. the Lojasiewicz con- dition cannot be satisfied for all y. since infugg= u² K (6))u//' u Amin (0)
O. Nonetheless, if some knowledge y; = fz;) for some f E Fo is available, then it is sufficient to show that inlney, wf (()u// /u" u > 0, where yn = (x=) - (a. S* E Fo} S R is only a subset of the responses Rn on which the smallest eigenvalue of the NTK might be positive. Bounding the eigenvalues of the NTK away from zero is sufficient, but not necessary, and for cases where the can bound the Rayleigh quotient of the gradient and enjoy similar
smallest eigenvalue is zero, guarantees despite the null cigenvaluc(s). Although stated differently in their respective context, previous uses of this restricted eigenvalue argument can be found for instance in Nitanda and Suzuki [2019, Assumption A4: response is -Tr-separablee, or Arora et al. [2019, Section 6, bounded inverseNNTK response]. We show how the argument used in these particular cases can be extended to a broader setting, and introduce tools to make calculations easier and obtain such guarantees.
Rayleigh quotient bounds enable convergence guarantees in the underparameterrized regime (m < n) and particular, for fixed number of parameters m, the guarantees hold even when the number of datapoints grows (n -> +0o) and the domain becomes continuous. Letting n - 4oo requires a slightly different formalism than the vectors and matrices used in this introduction, we will therefore use functional spaces in the following, and the usual notations of differential geometry, with parameters in indices for instance. Contrary to results such as Arora et al. [2019], Du et al. [2019], the formulation using functional spaces, from Jacot et al. [2018], extends to the case where datapoints are arbitrarily close and even identical, allowing guarantees on the expected loss with respect to a continuous distribution and not just the empirical loss measured on finitely many well-separated samples. In particular, these conditions need not rely on properties satisfied only with high- probability by random initialization when m > +oc, they can be proven even for fixed initialization and m E N.
Lastly, our analysis ties together in a more general framework the convergence arguments formulated in the functional space [Du et al., 2018, 2019] studying dynamics of the network response, and
2

---

similar arguments formulated in the parameter space [Li and Liang. 2018, Zou et al.. 2020], by centering the work on the singular values of the network differential (F E R=xm rather than the functional-space (F DF (0)) E TR or parameter-space DF(0)² (F) E Rm kernels.
Contributions. We provide definitions in Sec. 2, then present Kurdyka-t - Lojasiewizz inequalities, Rayleigh quotients, and their link in Sec. 3. We show in Sec. 4.1 that this recovers previously known linear bounds for the quadratic case. We illustrate a two-dimensional counterexample to the NTK positive-definitensss in Sec. 4.2, and how overcome it with Rayleigh quotients. In Sec. 4.3 prove a new bound on logistic regression obtained by the same technique. In Sec. 4.4 and Sec. 4.5, we outline arguments of convergence in more realistic settings and highlight future challenges.
2 Definitions for gradient flows and neural tangent kernels
Let X be set with no particular structure. We consider the problem of learning target function f : XX + IR, by having access only to samples (x, (x)) E X x R, where x ~ 'D are random samples from a probability distribution 'D on X. Let F = R be the vector space of functions from X to R. The setting presented in the introduction corresponds to X being finite containing the examples I; so that functions are represented as vectors f = (f(x)))<E(x)) and D is the empirical measure on X.
Definition 2.1. A network map is a function O + from θ a vector space of finite dimension equipped with an inner product ), 1o F equipped with the topology of pointwise convergence.
To avoid confusions as much as possible, we will reserve lowercase letters (f.g. h) for functions in F. and the uppercase F for network maps. We will usually put the parameters in index, and inputs between parenthesis, so that for 0 E O, the function fo X - R sends inputs x E X to outputs fo(x) E TR. Readers familiar with differential geometry will note that the assumption that t is vector space is simplification, and could be relaxed for instance to differentiable manifold. However, we are interested in easily readable results closest to applications, and this assumption will avoid cumbersome discussions on the parameter manifold's is tangent space, and keep results readable with only some background in linear algebra. In all the examples, is sufficient for our needs to set θ R" with canonical inner product and ll-lee 11-112. for some number of parameters m N.
Definition 2.2 (D- (D--semiorr).. Any probubility distribution 'D on X induces on F a bilinear symmetric positive semi-definite form (1s )D : F - TR, defined for (g, h)) E x F as
(g, h) = EX-D [g()))(x)]
The associated seminorm ||11p= : T + R4 is defined as ||91i = (g.9) = EEND [9(x)}].
This seminorm does not in general separate points, it is therefore not a norm on F. In particular, D does not have full support, then there are non-null functions g E I with null seminorm || = 0.
Definition 2.3 (Gradient flow). A gradient flow with respect to the differentiable loss L θ - R. an absolutely continuous curve 0 : R,, + O satisfying the differential equation 0,0 = - -VL(O)
Additionally, we say that a gradient flow is trivial if (00) = O, since it implies that for all t, 0. 00.
For U C O of R + θ is a gradient flow such that ( C U then we write just 0 : R4 + U.
A common choice for regression with target 1 E F is the quadratic loss L 0 - [I 8 1|3
If a network map F θ - F is differentiable for the pointwise convergence, we will write d.F. e + I for the differential of F at 0 E θ, with parameters in index for shortness. Evaluation at æ e X and derivation with respect to 0 e θ commute, casing computations (see Appendix A.2.2).
We write the corresponding gradient V X + O defined by (V.a(z) (dFo (x) for all x E X and v E O.
Definition 2.4 (Neural Tangent Kernel, NTK form). A differentiable network map F : O + F defines every point 0 E θ kernel function Ko X x X + IR as
Ko (0,z')= (V)) VFo(a'))
This function induces bilinear symmetric positive semi-definite form Kž : x F + R as
K h) = BEw (g( (')(a)))
3

---

In exponent notation, this bilinear form has signature K2 R x R + R. while the kernel Ko E _²*x; is an n X matrix when X is finite with E IN elements. Importantly, the (primal) kernel Kg is independent of the distribution D, while the (dual) kernel form Kü changes with 'D. Definition 2.5 (D-compatibility, functional gradient). A function& : F + R4 is said D-compatible ifV(J.9) E F x F, it holds that (ʃ g) D-almost everywhere implies {(f) = E(g).
Moreover, if is D D-compatible and differentiable, we say Ve: : + F is gradient of if satisfies v(f.)) E x (VLg,9)D = dlg(g)
This formalizes the idea that the loss depends only on the training samples, and the use of gradient simplifies the following statements. When it exists, the functional gradient is usually not unique, for it is defined only D-almost everywhere. See Appendix A.2.I for some examples of conditions under which it is well defined (for instance 'D has finite support, or & is the expectation of pointwise loss).
3 Rayleigh quotients to obtain Kurdyka-Lojasiett inequalities
3.1 Context: Kurdyka--.ojasiewiir inequalities for convergence
All convergence proof' presented in this paper rely on inequalities introduced by Kurdyka [1998] of the form of Proposition 3.1. These are used for instance to prove finite length of trajectories in dynamical systems (see e.g. Bolte et al. [2007, Corollary 4.1]), and sufficient to prove convergence to a loss of zero even for non-convex losses. We will therefore direct all later efforts to the construction of such inequalities. This was introduced as an extension to the linear convergence [see e.g. Nguyen, 2017, Section 1.3 for examples], to more general dynamics, and the proof of the following proposition is simple application of the chain rule to yp L (see A.2.3).
inequalities for
Proposition 3.1 (Convergence by Burdyka-LLoasiewiic. inequality). Let U C O. If & : U + R_ is such that there exists μs R2= and a strictly increasing difserentiable funtrnttiablefuuctioon yp I + R satisfying
v0 E U, (()) # > dep2(0) (VL(O), VL(0)) P
Then all non-trivial gradient flows 0 R - U of & satisfy Vt E R+, (0,)) S x (v((((0)) wu)
Moreover, if such a flow exists, then inf (()) = 0 and p(u) + oo if u + 0 (see Appendix A.2.4).
The central idea, similar to the one used in the following sections, is that desingularizing function & : E. + E transports the loss evolution [(0) + R; in dom((p) = Rt to the space Im( = R where the evolution is easy to understand, since (yp e (0) is bounded by an affine function of time. The desingularizing function provides a way to transfer the understanding of the convergence in the image of jo back to the domain of yp, where the loss evolution is little more complicated. The condition is also sometimes written V VL 2 (CC), where 3 R+ + R is (V(u)) = dip..
For the case of linear convergence speed guarantee, the Lojyak--ojasiwiizz condition from the introduction (i.e. (0) = (0)) 2 fu (0)) corresponds to the choice yp u + log(u). To accurately describe systems with more intricate dynamics, more complicated choices of y may be necessary, see the case of logistic regression in Sec. 4.3 for one such example.
3.2 Contribution: Hurdyka-LLojsieviie inequalities by composition
Definition 3.2 (Rayleigh quotients of bilinear maps). Ler (V, I1-Ilv) and (W, II-llw) ) be two vector spaces equipped with seminorms, and let A VxW - R be a bilinear map. Then for (z. y) E VxW such that (| E R2 (())), and (llvll E E4 \ {())), define the Rayleigh quotient
A(z, v)
R(A:
|<
With symmetric map A: V V V + R. the Rayleigh quotient R(A; x, is convex combination of the eigenvalues of A (which are real-valued), whose weighting depends on æ. Moreover, the minimal value is attained when is eigenvector corresponding to the minimal eigenvalue, and Amin(A) = inf (0) R(A;2,z). Lastly, when the map is an inner product, then the Rayleigh quotient
= (a, b)e/ ||a||e lblll is a form of cosine similarity. The most common usage is with x = y. but the asymmetric definition will be necessary later for the variational bound.

---

Proposition 3.3 (Kurdyka-Eojasiewiizz inequality by composition). Let F Q - I be a differen- tiable network map, and K₂ the associated neural tangent kernel (by Def 2.4). Let U _ be subset of parameters and Fu = F(U) C F its image by F. Let E: Fu + R2 be D-compatible differentiable loss with gradient : Fu -> whose seminorm is finite vf E Fu, [VVell < +00.
Assume that there exists strictly increasing differentiable 4p: IR. - IR satisfying
Vf E Fu, E(f) * 0 + dpe()) (V VegiD 21
If the Sgg-ayllighh quotient of the gradient of E is bounded below, i.e. if there exists μ E R,,, such that 40 E U. ((F())) # 0 = R (Kz; VlF(o). V(F(O) 2 P
Then, for C F)) u + R+, it holds
40 E u, (() + = dec(o) (VL(0), (((O)) 2
The proof of this statement is deferred to Appendix A.3.1, and similar to the usual NTK arguments. If K2 is j--unioorlly conditioned, then in particular K2 (Vé,; Vly) 2 v'Ve,, Vlf)D, which is exactly the Rayleigh quotient condition. The main difference is that it is not necessary to require uniform conditioning, it is sufficient for this property to hold on any subspace containing the gradient (and in particular the one-dimensional subspace defined by the gradient, i.e. the Rayleigh quotient).
Kurdyka-Lojar Lojasiewiz (KE) inequalities provide a reasonable path to convergence bounds, outside the usual convex framework. However, they can still be very difficult to obtain. This proposition splits the parametric-space KE inequality into a functional
KL inequality which is easier to obtain (trivial for quadratic losses, see Sec. 4. I; available for cross-entropy for instance, see Sec. 4.3) and a Rayleigh quotient bound, which is the focus of the following propositions. Similarly, we provide hereafter several variational forms that can help break the Rayleigh quotient bounding problem down into smaller blocks that can be easier to compute independently before reassembling.
Proposition 3.4 (Variational bound). Let F θ + I be differentiable network map, Ko the associated neural tangent kernel (by 2.4), and 0 E O. If E F satisfies [[ * 0, then it holds
R(K3: h, h) sup R R(dFo:v,h)
(E))(0)
Where dFţ is the bilinear form (v, h) + (dFg v. h) associated with the linear operator dFF.
This property is particularly useful to avoid dealing with the square of the differential, and instead obtain lower-bounds on the Rayleigh quotient by carefully selecting (suboptimal) inputs v E @ {0). Proposition 3.5 (Split cosine- singular value). Let F + + I' be differentiable network map, K the associated neural tangent kernel, 0 E O and h E I such that ||lll D # O. If there exists a subspace Oo C O and some μ E IR4 such that there exists E Oo satisfying R((:;)) ());;;;; d. v. v.h) 2 p., then for X= = inlvee,Ild /////////l E R_,. it holds R(K3; h, h) 2 1²² X.
This proposition is trivial consequence of the following one, but is easier to parse while still making apparent the distinction between a geometric quantity and the singular value X. See Sec. 4.2 for an example in dimension two, where μ is defined only by the angle between the gradient and the lemniscate's ' tangent, independently of the parameterization. Observe on the other hand that as X, the speed at which the lemniscate is traveled, changes, so does the gradient flow's convergence speed, Proposition 3.6. Let F : O + F be differemtiable network map, 0 E O, and h E F s.1. ||/ll + O. Let k E N Let (ai)ie (0) (0))* and (gt) E (I) (II-11)) If Span(g), then max R R(dF);u,h) Amin (R (1+, -Di d.o at (t))))).))) minve[s]l a.llD/ llaille rESpaula)(10
Vimax R ((5 ai, 9z),.) Amax (R (1))))))
where the smallest singular value of A E TRAk is Amin (A) min of Au/u uf (resp. max).
If the vectors (a. g) are taken orthogonal and such that dFg a, = d:g; for some d; E R, then the three matrices are the identity, and only the minimal Rayleigh quotient remains. If they are chosen only approximately orthogonal, then a corresponding multiplicative penalty is incurred.
The proofs of the preceding three propositions are deferred to Appendix A.3.2, A.3.3 and A.3.4 respectively.
5

---

4 Case studies
4.1 Linear models with quadratic loss, recovering known bounds
As sanity check and simple first contact with the variational bound, we consider model linear in its parameters, with quadratic loss, and recover the (known optimal) linear convergence rate. This proposition is the continuous time form of Karimi et al. (2016, Theorem 1].
Proposition 4.1 (Convergence of quadratic-loss linear models). Let X = θ = IR. and F O - F, be the linear network map F A -> fo defined by fa( (xr, 0). Let f X R be linear function. Let & : - + IR+ be the quadratic loss & : + [1((0) - f 1 where D distribution over X such that is well-defined and finite.
(A) If RR O gradient flow of L, then for all R.,, it holds ((.)) S ((0) E - (A)e, where A = EEWD [xxx"] Raxd is the (uncentered) covariance matrix of the samples, and X (A) its smallest non-null eigenvalue. Moreover, there exists D such that this bound is an equality.
The idea is apply Proposition 3.3. The functional Burdyka-Lojasiewee inequality is immediate, and we bound the Rayleigh quotient with Proposition 3.5 applied to the subspace θ, = Ker(A)
Proof. Let : RR_. - |l - 11, be the functional space quadratic loss, whose gradient Vl, -(--f) satisfies the Polyak-Lojasiewiez inequality || Z 4 Hence, let us show (0) + + R(K;: Vêr(o). Vlr(o)) 2 A Ain (A), which is sufficient by applying Proposition 3.3.
Let l" E θ be any parameter such that f = for where existence is guaranteed by lincarity of f*. Observe that the loss can be written (0) = (0 - )² A(0 0*). Let 0 E θ such that L()) & 0. In particular, 0 0" & (er(A). Then, let Os = Ker(A) (A) On one hand, it follows that
(dFe ((0) F(0))}
(u"A(0 )²))²
sup (E) | 1 ((() F(00) (w² Au) - 0-) A(D - 0*))
=1
with the maximum attained for Ker(A) \. ((0} the orthogonal projection
projjetooalpoojeetioon of (0 (0-0") 0r) to Ker(A)
satisfying A(O 8*) = Au and (0 0r, u) = 0, thus u" Au = A(0 A(0-0") = (0 (0-0-)" 8-) A0 - 8¹).
Then by definition inf (0) = /| inf (v" Av) = X (A). Conclude by Proposition 3.5, with and A (A). Equality recovered for A = la-
This is to be contrasted with a direct proof of the Kurdyka inequality, i.c. showing that
(O) (0 8-) 8*) (0)
(0 - 0-)² A(O 0*) 2 4
Although the proof seems a bit convoluted, the interesting part here is that the original bound can be split into two (hopefully simpler) subproblems, while still allowing the use of knowledge on (fe - f)), leveraged here by the assumption (0 10-0% 0*) (er(A)+ Note that knowledge of property such as (Ø 8*) E O C Rd for any subspace On could have been used to eliminate any eigenvalues of A on O including strictly positive eigenvalues, there is nothing specific to Ker(A) other than the existence of the prior knowledge (0 (f)) & Ker(A) (A) granted by (0) # 0.
4.2 Lemmiscate-constrainee optimization, singular values
We now present toy example simple enough to allow for explicit computations and constructed to illustrate the importance of parametrization. We consider linear functions in two dimensions where the function fia.b) IR2 + IR, f(a,b) (I, y) + oz + by is simply identified with (a, b) E IR.. We will still consider quadratic loss but we now assume that the target function f S(a .b)) is linear and with (a", b²) Fo = {a. b) E R2 (a² + b²)² a² b²). Although we are looking for a two dimensional linear functions f", knowing that f E Fg reduces the "degrees of freedom". In such scenario in machine learning, we typically incorporate this information in the parametrization. As result, we now have only one parameter to estimate, i.e. θ = R and our network maps F : R + R²
will satisfy Tm F) = Fo- Note that Bernoulli's lemniscate Fo (pictured in Fig 22a is neither a convex

---

set, nor manifold (due to the crossing at zero). There is no "natural" parametrization of Fo and as shown below, the chosen parametrization will matter. For more clarity on the consequences of this parameterization, we use two parameterizations of the lemniscate Fo:
cos(O) sfn cos(0) Fs 8 (1 (ins)(() sin( 1 sin(
20 02) 1+ 60 8o 1 + 602 + B4
1 1-
and, FL:00
The graph of these parameterizations {(0, F(O)) 0 RJ S R is depicted in Fig. 1. The first, Fs is differentiable 2m -eproodii and surjective, satisfying (s( 2T)) Fo. The second, FL is differentiable, but it is neither injective (since Fz(-1)= (0,0) FL(+1) nor surjective. It
punctured lemniscate Im(Fr) Fo (((-),(())))))) 0)}, it is only dense in the lemniscate Im(Frr) Fo-
-12
-12
+0.4
+0.4
..2
10.0
aiB)
+0.5
+1.
400)
.02
-0.5
40.0
a(8)
+0.5
+1.0
-0.4
-1.0
-0.4
(a) Periodic lemniscate (Fzt sphere lemniscate)
(b) Punctured lemniscate (Fz: line to lemniscate)
Figure 1: Graph of the two parameterizations presented (with 11 dots regularly spaced on [-1,+1])
Note that in both cases, the neural tangent kernel K₃ has rank (because there is only one parameter), thus Amin (Kz) = by rank deficiency but we can still prove convergence to zero loss.
To make things even more clear, we assume that all samples are lying on line: D is a distribution supported on the dimensnnnsooal subspace t with samples are of the form z(t, a" + b) E R x R for some E IR and any function f(a,8) with (a (a-a") (b ) 0 will achieve loss of zero. Indeed as shown in previous section, standard linear regression this case converges
(u, v) I {0). In words, all the labeled
loss of zero but the parameters inferred will not be on the lemniscate Tg. With the parametrization Fss or FL, we will find solution living on Fo. namely one of the two points in L (0) nT., as seen in Figure 2a.
+0.50
gereral optims
0o loce
10a
constreined ootime
+0.25
100
Loss
+0.00
10-1
Periodic parameterization Punctured parameterization
0.25
.0500
0
50
100
150
200
250
-1.0
-0.5
+0.0
+0.5
+1.0
Iteration count
(a) Beroulli's lemniscate Fu and level sets of
(b) Observed convergence speeds
Figure 2: Loss level sets with parameters (4, and f*) -3, corresponding to quadratic loss f: (a, b) (4a b 3)² and convergence speed with step size 10 and initial estimate 0(0) = 0. Both flows converge to the same functional minimum (Fs( = Fr, (0))), the one depicted the bottom in (a). Initializing
different point could have led to convergence the other minimum. Proposition 4.2 only shows that the loss converges to zero, leaving unaddressed the question of which minimum reached.
Proposition 4.2 (Lemniscate convergence with varying speed). Let (u, v) E RR2 such that u >> O and |e] < [u]. Let e E_ such that the equation (au be y) has exactly two solutions (a, b) Fo.

---

Let f:: R=² + E++ be the quadratic loss E(a,b) + (au - bu - -y) Let 0s R4 - R (resp.
0,.: : :R4 + +R) be a gradient flow with respect to the loss f F5 (resp. lo FI.) such that 8(0) Then there exists a constant PAo E _ such that it holds E ((Fs(()(t)) I {(0) exp( exp(-416\31) and where X33 and Xj. (V for 07, lim, Og (t).
((Fr(O((t))) S ((0) exp(-4p
The sketch of this proof is given in Appendix A.4.1. For the numerical values taken in Fig. 2a, we have \ं 4.05 x 10-3 showing that our bounds capture the speed of convergence. The idea is as previously, to use the quadratic loss convergence provided we can show R Ver V(F(O)) 2 M for all 0 E Os(R.) (resp. Xi for 0 0g (R+)), achieved by variational bound (Proposition 3.4) split according to Proposition 3.5.
property (I[V2) 2 4E) that will grant linear
4.3 Cross-entropy minimization with linear models
We now consider classification task with e 2 classes. Let A. = E (I,)) EvEjo) " = 13 be the set of distributions over those classes. The samples live in X Rd and the target function is f + A.. Let R + Ac, u + (cxp(u=)/ E, exp(u;)); be the softargmax map. Let O = Rexd be the parameter space, and X θ + (X + 12) be the operator mapping parameters to linear functions, such that X(0) : x + 0 x. We use the parameterization F + E0) where E is applied pointwise. For any fixed sample x E X, we define the loss for this sample as Hg : A. - RR, p + Eiele (x) log( The complete loss used to train this model is then the logistic regression L 0 + RRDD HH (=)) for which we give new convergence bound.
+ x (X (X-+R) R*) E (X (c)
H
(X OX-+R
BOND
R+
Definition 4.3 (Isolation). reul-valued random variable Y E L is k-isolated if P(Y 2 E(Y) k
All L variables are k-isolated for some A random variable Y with finite support, i.c. P(Y = = pt for some E IR" and A, is (minkg(a) pi)-isolaeed, regardless of the values y. This bounds the isolation of the maximal value in sense. Moreover, if d/ R - TR is increasing and Y is k-isolated, then it holds (E()(Y)) 2 (B(()) We use 1/n in our experiments (see A.5.6), where n E N is the number of training points.
but we will need notion of uniform isolation.
y4)
Definition 4.4 (Multi-class separating rays). We say that parameter E Rexd is e-separating ray for the distribution 'D if holds for DDaamost all x E X that
3i [c] Vj [c] \ {i), ()r, 2 (),,2) + 1|S122
where S. E Rd is the i-th row of S, i.e. (5 x) E R has a umique maximum (with a fixed margin).
This property is invariant by rescaling of and generalizes the notion of "separation margin" usual in two-class logistic regression. If ( is eseparatting for some ε >> O, then for D-almost all inputs x, the softargmax classifier f = F())= X + A. induces unique label E [c] as argmax, [x)
Proposition 4.5 (Convergence speed of logistic regression). Let D be distribution such that the point-loss random variable &g = (f where I ~ D, is k-isolated for all f F(().
Let C : 0 E θ + Ex-n [H (F (0) E R, be the multi-class cross-entropy loss. If there exists an E-separating ray Ç such that XER ((CC) O, then for all non non-trivial gradient flows R, + O
L(O.) & log (1+ Wo (exple2222 - CT)
where Wo R2 - R4 is the Lambert function, and C = log(e~(0o) - (c - 11-00)-111--- R.
The Lambert function Wo is defined by Wo(z)e deferred to Appendix A.5.3. The idea is to prove a functional leveraging the isolation property, then bound the Rayleigh quotient by leveraging the separation and inf & 0 hypotheses to obtain a parametric hurdyka-Lojasienn
see Corless al. [1996]. The proof is inequality by
inequality by Proposition 3.3.
Being a convex problem, the classical argument of Boyd and Vandenberghe [2004] gives bound ((.)) S Co/t as long as there a finite optimum 0" Ô. This bound becomes vacuous (Co - +00) in this setting with dirac labels, common in machine learning, because the infimum is located "at
8

---

infinity". This assumption has been previously lifted (under separability in Soudry et al. [2018], Nacson et al. [2019], without separability Ji and Telgarsky [2019]) recover the (11/t) asymptotic behavior, but without explicit bounds for finite times.
This result is consistent (see Appendix A.5.4) with the asymptotic ((1/t) bounds from Soudry et al. [2018, Theorem 5] with similar hypotheses, this proposition only makes quantitative the non- asymptotic behavior of this system, and the characteristic quantities driving the convergence speed. To do so, the separation assumption had to be made quantitative, hence the use of s-separating rays for fixed positive E, where previous work used only non non-quantified data separation (i.e. Be, Sş s.t. Ç is an E-separating ray for the data), see Appendix A.5.5 for more details. Similarly to the previous section, and contrary to the parameter-direction convergence theorems Soudry al. [2018, Theorem 5], Nacson et al. [2019, Theorem 3]. and Ji and Telgarsky [2019, Theorem 1.1], this proposition does not, on its own, yield any insights on implicit bias (which infimum reached) towards max- max-ma rays, additional arguments are required for this purpose. The focus here is on the precise quantification of convergence speed under separability assumptions, with continuous time.
4.4 Overparameterized two-layer networks with quadratic loss
Let X = Rd and IR + R be non-polynomial Lipschitz map. For E N \ {0} number of neurons. Let (m) I mx x R be parameter set and p(m). ((m) - I be the associated network map F(m) (w, a) + Σ ie(m] aww; - .r), i.e. a two-layer network' with non-linearity o.
Let C X be compact, and 2> distribution supported on K. Let f E IJ be a continuous function. Over ((m) = mxd x R,, let 3. be the (usual in practice) iid normal rescaled initialization with density p(w,a) a) IIlE[m] N(wa,; 0, 1) [Ike(m] N (ax: 0, 1/ 1//m). We write (z) max(0,
Proposition 4.6. Let = E R4, and 8 e)0, 1. There exists e E R1 such that, for all radii R E Ri, there exists a neuron count m such that with probability (1- 8) over initializations 0g ~ Ina the quadratic loss & 0 E ((m) + [[ I satisfies the inequality
40 B(Oo, R),
(I Boll2 + c)2 (C(0) -)
Therefore, for any desired precision Eo E Ri. there exists (m, x)) N Ri such that with probability at least (1 8) over initialization G, Ims gradient flow O Rt O of & with ((0) 0o satisfies Vt E R4, (0,,) S Eo + 1/ (Z0(0))33 3 +ll
Proof in Appendix A.7. The idea for the proof is to use universal approximation property on compacts [Cybenko, 1989, Barron, 1993, Leshno et al., 1993], to get [[ + dFF v 11, inequality from that with a variation of Proposition 3.5.
for some
v E O, then derive a Kurdyka-t.ojasewv// Knowledge of sarddkka-t.jjsiewwvvi inequality in a ball around initialization alone is not sufficient to show loss convergence to arbitrary precision in general, but the separable form of this inequality makes possible, following Scaman al. [2022, Proposition 4.6]. This proposition shows convergence outside the vastly overparameterized regime (m is finite even with infinite data), but still relies heavily on (very) large number of neurons. In the next section, we give a partial convergence argument using similar techniques in much more constrained regime.
4.5 Periodic signal recovery
Let X = IR. Among functions F = (R - RR), R we are interested continuous periodic antisymmetric functions, which we parameterize with θ = R. x Rm as F θ >> F, defined for (a, w) E O as F(a,w): + Exe(m) a, sin(w,z)), and ((a,w) the associated NTK at the point (a, w) E O.
The central property of this application, separating it from the most common machine learning applications, is the inability to obtain good samples. Let R E R2 be a finite window size, and define the training data distribution 2 U(-R. R. +R), the uniform distribution on the interval [-R, +R) Let Fo S JJ be the set of continuous periodic antisymmetric functions with period less than R. Crucially, we are interested not just learning the function on the interval, akin to just data retrieval,
'The bias term usually present in linear layers is omitted to lighten notations, without loss of generality since an additional dimension with non-null constant coordinate can be added to the input domain to compensate for it.

---

but rather in learning the function in (R - R) as whole. This problem is well defined, i.e. if f E To. then argminnges, llg f [f*). The periodicity assumptions makes the data sufficient to recover the target function among the hypotheses, however neither the assumption that the training and testing data distributions are identical, nor the assumption that the model has more parameters than there are data points are satisfied. There is infinite data, but there is bias in the sampling.
We will rely on two properties of frequency parameters to show bounds. First, we say that w E R is 5-separated if infiyj (i wil 2 å and inf; [wi]| 2 6. Then, we say that the pair (4, E R x 1 is E e-paired if sup)e[m) [W ww-ww] S E. Moreover, let zy E R,, be the first zero of sinc". (20 = 2.0815).
Proposition 4.7
region). Let (11, 11) E IRT x R2 such that vi S zo and 1] < zH
Let f E F be a target, and e: f E E+ 211f-f" 1' the quadratic loss, with gradiens Vł, = f f f Assume that there exists (a", ,w") ) 2 such that f F(a", , and w is R -separatee.
Then for all wa, E a such that ((F(a,w)) * (w,w") is n-paired, and Fo E [0,, Vk, az 2
1
(KD pp)²
R (KTasa (aw); VlF(aw)) V(F(aw) 2 (b1))
リ- n
Pb
where with & = - sinc', Φ = sine", and H = =Ensm 1 lm) E RR,, the constants are
Ko = ((1) P-1 ((0) kーク Moreover, oNf E R., Vu no: Bn > 0, s.t. Ko Po- (non degeneracy if enough periods observed)
4H 2M
Po Φ(n)
pー
Proof in Appendix A.6, leveraging Prop. 3.4 (variational bound) and Prop. 3.6. This shows that when each frequency present in the signal is correctly estimated, then a gradient flow is well-suited for fine-tuning both frequencies and amplitudes. There are sufficiently few interactions to allow each neuron (a,, wi) to descend towards its target (a; w If the modelling hypothesis is verified (the target is sum of sine waves), there is finite and small number of neurons giving sufficiently- parameterized system, and no need to go for vast overparanterization Letting the number of neurons tend to infinity is one way to ensure there is at least one neuron in each bassin, but not the only way.
5
Conclusion
We have shown that Hurdyka--.ojsiewiin inequalities can be leveraged to prove convergence of gradient flows to a loss of zero, even when the convergence speed is not linear. In contrast, Polyak- Lojasiewicz inequalities granted by positive-definiteness of the neural tangent kernel only covered least-squares losses enjoying linear convergence speed. Furthermore, we have shown that by focusing on lowering-bounding Rayleigh quotients rather than all eigenvalues at once, one can prove conver- gence even when the neural tangent kernel is not positive-definit the most striking example being the finite-width infinite-date data regime, where the neural tangent kernel must have null eigenvalues by rank deficiency. We have provided several simple examples of such convergence proofs outside the vastly werrpaarametrrized regime where there are more parameters than samples, along with tools and inequalities
preliminary results that lead us to believe that obtaining the crucial feasible more reasonable machine learning settings.
6 Acknowledgements
The authors would like to thank Thomas Le Corre, Lucas Weber, and Luca Ganassali for their help with various details of the proofs presented here, along with the anonymous reviewers, for their corrections and help in improving the readability of this work. The authors acknowledge support from the French government under the management of the Agence Nationale de la Recherche part of the "Investissements d' l'avenir" program, reference ANR-19-P3IA-000) (PRAIRIE 3IA Institute).
References
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and generalization neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 8580-8589, 2018
10

---

Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, March 2004. ISBN 0521833787.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- per-paaameteri non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
Lenaic Chizat. Sparse Optimization on Measures with Over-parameterried Gradient Descent. working paper or preprint, November 2020. URL https:: archivess-oueertes.. fr/ hal-02190822.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 322-332. PMLR, 09-15 Jun 2019. URL https: / /pppp/////occcoss....// mlr www.ppreessvveee //ro//rrra99a. html.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4951-4960. PMLR, 09-15 Jun 2019. URL https: h/tp::/:////coeednggss mlr. wwt..press/vee /v7/ htte//omakk9999 9a. html.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 33, 2020.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes pwerpparamterrize neural networks. In International Conference on Learning Representations, 2018.
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
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over prereerraettiizattoonn is sufficient learn deep re [lu} networks? In International Conference on Learning Representations, 2021. URL https: / opw.reveeeeeeeeeeeeeeeeeeeeeeeee thee/forrmmiieee id= wuZze
Atsushi Nitanda and Taiji Suzuki. Refined generalization analysis of gradient descent for overpa- rameterized two-layer neural networks with smooth activations on classification problems. arXiv preprint arXiv:1905.090 09870, 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterizeed neural networks via stochastic gradient descent on structured data. Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 1178-817, 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- peeepaaraeterizee deep relu networks. Machine Learning, 109(3):467 492, Mar 2020. ISSN 1573-0565. doi: 10.1007/110994-019-0533 $10994-019-05839-9
URL https://doi.orrs http://doooorr////////// ott.:o..rr/0......0.0..........0 1000/
Krzysztof Kurdyka. On gradients of functions definable in o-minimal structures. Annales de I' I'Institut Fourier, 48(3):769-783, 1998.
Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The łojasiewicz inequality for nonsmooth sub- analytic functions with applications to subgradient dynamical systems. SIAM Journal on Opti- mization, 17(5):1205-122: 2007. doi: 10. 10.1137/050644411 URL https://doii org/10. 1137/ 050644641.
Trong Phong Nguyen. Inégalités de Kundyka-Lojasievicz et convexité: algorithmes et applications. PhD thesis, Toulouse 1, 2017.

---

Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak -ojaseewwi condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-811. Springer, 2016.
Robert Corless, Gaston Gonnet, D. Hare, David Jeffrey, and D. Knuth. On the lambert w function. Advances in Computational Mathematics, 5:329-359, 01 1996. doi: 10.1007/BF02124750
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. Journal of Machine Learning Research, 19(70):1-57, 2018. URL http:// org. /ttp://aa....r///papp////////11/
html.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In Kamalika Chaud- huri and Masashi Sugiyama, editors, Proceedings of the Ewenty-Seconts International Conference on Artificial Intelligence and Statisties, volume 89 of Proceedings of Machine Learning Research, pages 1420-3428. PMLR, 16-18 18 nacson196 html.
Apr 2019, URL https: btttps://prott http///proeeeeeeee/eee//// wachnnss.ll mlr press/ /
Ziwei Ji and Matus Telgarsky. The implicit bias gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1772-1798. PMLR, 45-2810 Jun 2019, URL https::/procceeeeeeee
mlr ppwss/v99/ j11p/.ii.a.... 199...ml.. html.
George V. Cybenko. Approximation by superpositions of sigmoidal funetion. Mathematics of Control, Signals and Systems, 2:303-314, 1989.
Andrew Barron. Barron, a.c.: Universal approximation bounds for superpositions of a sigmoidal function. iece trans. on information theory 39, 930-945. Information Theory, IEEE Transactions on, 39:930 945, 06 1993. doi: 10.1 109/18.256500
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861-867, 1993. ISSN 0893-6080. doi: https///bbioggllllllulsss0000000 httpp://www, sciencedirect. wwt.eccoc/cccceeeeeeeee /ttp:///c///tttccce/////////////
URL
Kevin Scaman, Cedric Malherbe, and Ludovic Dos Santos. Convergence rates of non-convex stochastic gradient descent under generie lojasiewiez condition and local smoothness. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 19310-19321 PMLR, 17-23 Jul 2022. URL httpps//pproceeding: mlr. prw.s/ressseee v/ss/vv222. scaman22a, htmml....
A. Gut. Probability: A Graduate Course. Springer Texts in Statistics. Springer New York, 2013. ISBN 9781461447078. URL
woogolo fr ftt/bookssid-97ngggg2 -ggg..
Abdolhossein Hoorfar and Mehdi Hassani. Inequalities on the lambert w function and hyperpower function. J. Inequal. Pure and Appl. Math, 2008
S. Gerschgorin. Uber die abgrenzung der eigenwerte einer matrix. Izvestija Akademii Nauk SSSR, Serija Matematika, 7:749-754, 1931.
12


Reviews:
[{"review_id": "WJi4wM5oE32", "reviewer": "Reviewer_xNfg", "summary": "This work investigates the convergence of gradient flow to zero training (and test) loss. The main idea is to derive Kurdyka-Lojasiewicz inequality which is accomplished by lower bounding Rayleigh quotients, and several showcases of common learning problems have been analyzed by this technique. ", "questions": "Typo:\nline 319, \"be compact\". line 703, \"has a ...\". line 730, equation (1), it should be \"l.h.s $\\leq \\frac{\\eta}{2}$\". in equation just before line 737, it might be $\\frac{\\eta}{2} + \\frac{R}{\\sqrt{k}}$, which yields $\\sqrt{k}\\geq 2R/\\eta$. line 360, \"there there\". line 545, there might be an error in calculating first component of the gradient.\n\nQuestions and suggestions:\n\n1- Proof and statement of Prop 4.6 needs revision. First I can't find a proof that $\\theta(\\mathbb{R}_+)\\subseteq \\mathcal{B}(\\theta_0,R)$ if $\\theta$ is a gradient flow, and in fact you just assume this condition holds in line 745 without proving it and further in line 328 you defer its proof to future work. Please indicate what is the difficulty in proving it. Most importantly, in the beginning of page 27, the conclusion in the 3rd line $\\cdots \\geq \\frac{1}{\\lVert \\nu_0 \\rVert^2}(\\mathcal{L}(\\theta_0) +0 - \\epsilon)^2 $ does not seem correct because $a\\geq b $ does not imply $a \\geq b$. However it seems that there is a fix for that because you just need to consider $\\lVert \\nabla \\mathcal{L}(w,a) \\rVert_2 \\geq \\cdots \\geq \\frac{1}{\\lVert \\nu_0 \\rVert}(\\mathcal{L}-\\epsilon)$. Even with this change, the argument in line 751 needs explanation on how you use prop 3.1 to show $\\overset{\\sim}{\\mathcal{L}}(\\theta)$ converges to zero. One way I can think of is to use $\\phi(u)=-\\frac{1}{u}$ which is a strictly increasing differentiable function on positive real numbers and $\\phi'(u)=\\frac{1}{u^2}$ and it gives $\\lVert \\nabla \\tilde{\\mathcal{L}}(\\theta) \\rVert^2 \\geq \\mu \\tilde{\\mathcal{L}}(\\theta)^2$ which is true here as you assume $\\mathcal{L}(\\theta_t)\\geq \\epsilon$. Hence by showing that $\\mathcal{L}(\\theta_t)$ converges to $\\eta\\leq \\epsilon$, it follows that $\\mathcal{L}(\\theta_t) - \\epsilon$ is negative for large enough t, and hence $a \\geq b$ does not imply $a^2 \\geq b^2$ with $a=\\lVert \\nabla \\mathcal{L}(\\theta) \\rVert$ and $b=\\kappa (\\mathcal{L}(\\theta) - \\epsilon)$. Finally I would like to know about rate of convergence by using Prop 3.1. It seems to me Prop 3.1 can only be used to show contradiction, i.e. $\\eta\\leq\\epsilon$, and I'm wondering if $\\lVert \\nabla \\mathcal{L}(\\theta) \\rVert \\geq \\kappa (\\mathcal{L}(\\theta) - \\epsilon) $ can be used with prop 3.1 to give any rate of convergence.\n\n2- (when) is the $\\kappa$-isolated condition in line 307 satisfied? I couldn’t find how it is proved anywhere in the Proof section, and stating under which conditions it is satisfied seems crucial. Also please discuss how fast is the convergence rate of prop 4.5.\n\n3- It is true that existing a \"non-zero\" $\\epsilon$-separating ray leads to unique label in softmax classifier and also interesting that separating ray with zero loss implies dirac labels. Please cite any existing work that considers this separating ray assumption, assuming you are not the first one.\n\n4- in line 590, is the conclusion $\\nabla \\ell(u): x\\rightarrow \\nabla \\ell_x(u(x))$ a result of Lemma A.1?\n\n5- in line 583, please explain more thoroughly how \"convergence of positive r.v.s in expectation to zero leads to some subsequence converging a.e. to zero\".\n\n", "limitations": "The limitations concerning conditions under which prop 4.6 holds is discussed in lines 328-331. However I couldn't find how $\\kappa$-isolated in line 307 and $\\epsilon$-separating ray in line 309 are satisfied. It is strongly suggested to discuss these in the appendix.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall the paper is well-written and the main messages are easy to follow. However I had problems in understanding section 4.5 and its proofs, as well as prop 4.2, and couldn't check their correctness. Other results, except for prop 4.6 which might need slight modification discussed later, seem to be correct. The main weakness can be seen in discussing the conditions under which prop 4.6 and prop 4.5 hold, as addressed in below.\n\nI like the argument that Prop 3.1 makes the loss evolution more tractable using the function $\\phi$. Indeed in line 164 you provide $\\phi$ when PL condition is satisfied and further in section 4.3 provide example for multi-class logistic regression. In Prop 3.3 you argue that functional-space KL inequality is easier to obtain and together with Rayleigh quotient bound they imply parametric-space KL inequality, hence able to use the convergence result of Prop 3.1. The techniques employed throughout Prop 3.4-3.6 to split the Rayleigh quotient bound seems powerful and its first simple use is shown in linear models with quadratic loss in Prop 4.1.\n\nI would also like to know about any previous work that analyzes Cross-entropy minimization with linear models, assuming you are not the first paper to consider it. \n\nOverall the references include major important works in related areas, and some of them deal with Gradient Descent and overparameterized models. Please pinpoint the works that do not have overparametrized assumptions and if possible, compare your work to them. For example in line 150, you mention that \"this was introduced as an extension to PL inequality for linear convergence ...\". Please include as many references as possible that revolve around using inequalities in Kurdyka [1998]. One suggestion is to defer the proof of prop 4.1 to appendix so that you have more space.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "2pYUFS41w8i", "reviewer": "Reviewer_csDk", "summary": "This paper proposes a new insight in proving the convergence of the training of deep learning. Taking advantage of  the notion of Rayleigh quotients, the authors show that  KL inequalities for a broader set of neural network architectures and loss functions can be obtained. Moreover, several illustrative examples are provided to demonstrate their idea. In particular, their analysis does not require over-parameterization.", "questions": "Minor issues:\n\n1 A table of notations is preferred.\n\n2 What does the ``uniform conditioning\" (in Line 19) mean?", "limitations": "YES", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My detailed comments are given as below.\n\nStrengths:\n\n1 This is a theoretical article on the convergence of the GD for deep learning. This topic has been intensively studied recently. Most of previous works require the over-parameterization. But this work is different, and it presents a new strategy in proving the convergence based on the Rayleigh quotients and the KL inequalities. This innovative idea has intrigued me, and I feel that this article contributes significantly to  the understanding of training dynamics of NNs.\n\n2 One of main limitations of previous works is that their arguments require the positiveness of the NTK which further requires the over-parameterization. This paper points out that  one can bound the Rayleigh quotient of the gradient instead of lower bounding the eigenvalues of the NTK. Furthermore, the authors show the connection between the Rayleigh quotient and the KL inequalities which ensure the convergence.\n\n3 This paper is very well written and easy to read. Several case studies are presented in Sec 4.These cases are common and representative, and make their ideas very convincing. Moreover, the proof seems clean. Although I did not thoroughly examine the proof, it provided me with several fresh perspectives.\n\nWeaknesses:\n\nThis paper argues that the proposed new strategy can be used to prove the convergence of deep learning architectures to a zero training\".  However, only two-layer NNs are discussed in case studies. Can you provide some cases to support your argument on ``the deep architectures\"? ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2b4FxF5P-JY", "reviewer": "Reviewer_a4Qu", "summary": "This paper presents a strategy to prove the loss convergence of gradient flow for training loss of the form $\\ell(F(\\theta))$, where $F$ is the vector consisting of neural net outputs on each data point, and $\\ell$ maps the outputs to the final loss value (e.g., $\\ell$ can be the MSE to target values). Previously NTK-based analysis assumes that the smallest eigenvalue of the NTK matrix $K = DF \\cdot DF^\\top$ is bounded from below, then proves the loss convergence through establishing the PL condition under this assumption. In this paper, the authors avoid the assumption on the smallest eigenvalue and instead point out a proof strategy based on Rayleigh quotients of the NTK matrix and KL condition. This strategy is then applied to prove loss convergence bounds for linear regression, linear logistic regression, and some partial results are also given for two-layer net with squared loss.", "questions": "1. I wonder if the authors have some concrete examples showing that loss convergence bounds can indeed be deduced for nonlinear neural nets beyond the over-parameterized regime (without extra assumptions).\n2. How does the loss convergence bound in the linear logistic regression case compare with prior works? How much is known about the loss convergence rate of linear logistic regression in the literature?\n3. When does the isolation assumption hold in Proposition 4.5?", "limitations": "The major limitation has already been mentioned in Weakness 1. Besides that, this paper also has some limitations that are common in many optimization papers: (1) the dynamics of SGD and gradient flow can be very different; (2) the loss function can be non-smooth.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n1. The proposed proof strategy does not require the smallest eigenvalue of the NTK matrix to be lower bounded, allowing analysis when the number of data is more than the number of parameters.\n2. Applying the proposed proof strategy gives an alternative way to understand the loss convergence bound for linear regression.\n\n### Weaknesses:\n\n1. While it sounds more promising to establish loss convergence bounds beyond the over-parameterized regime, this paper does not prove any concrete theorem on nonlinear neural nets with fewer parameters than the number of data. In Sections 4.4 and 4.5, the authors give some partial results establishing loss convergence under the assumption that the gradient flow does not move far from the initial point. This assumption weakens the strength of the results because it seems to be a more interesting and important question that why gradient flow does not intend to move far away in search of a better solution. In other words, it is unclear how useful the proposed proof strategy is in terms of overcoming the various difficulties in analyzing loss convergence beyond over-parameterized regime.\n2. The results on linear logistic regression are not well contextualized relative to prior works. The authors claim that the loss convergence bound in this case is new (Line 97), but it is unclear how it compares with previous works such as the $O(1/t)$ bound in Theorem 5 of [1] for binary classification (see also Appendix E for the multi-class case). These two bounds should be the same when $t \\to \\infty$, so the authors should compare them carefully in the non-asymptotic case.\n3. The presentation of the current paper is not very understandable, since there are too many notations and the notations vary in different settings. I spent hours reading this paper to understand and memorize all these notations just to understand the basic idea. One main issue is that the definitions in Sections 2 and 3 include too many technical details that are unrelated to the idea of bounding Rayleigh quotients, e.g., the concept of D-seminorm is somewhat unnecessary because one can just replace the D-seminorm of $\\nabla \\ell_f$ with an expectation over the dataset, which is more accessible to the readers. To improve the presentation, I recommend the authors to either reduce the number of notations or add a warmup section that illustrates the proof strategy in a simple case (e.g., linear regression) before introducing the general setup.\n\n[1]. https://www.jmlr.org/papers/volume19/18-188/18-188.pdf", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept