Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networks
Authors: Akshay Kumar
Jarvis Haupt
Venue: Accepted by TMLR ()

Abstract: This paper examines gradient flow dynamics of two-homogeneous neural networks for small initializations, where all weights are initialized near the origin. For both square and logistic losses, it is shown that for sufficiently small initializations, the gradient flow dynamics spend sufficient time in the neighborhood of the origin to allow the weights of the neural network to approximately converge in direction to the Karush-Kuhn-Tucker (KKT) points of a neural correlation function that quantifies the correlation between the output of the neural network
and corresponding labels in the training data set. For square loss, it has been observed that neural networks undergo saddle-to-saddle dynamics when initialized close to the origin. Motivated by this, this paper also shows a similar directional convergence among weights of
small magnitude in the neighborhood of certain saddle points.

Published in Transactions on Machine Learning Research (06/2024)
Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networks
Akshay Kumar
lumar51 @umn. edu
Department of Electrical and Computer Engineering University of Minnesola, Minneapolis, MN
Jarvis Haupt
jdhauptshummn edu
Department of Electrical and Computer Engineering University of Minnesota, Minneopolis, MN
Reviewed on OpenReview: https: openreviee. net/ pert/formm?ee hd=1
Abstract
This paper examines gradient flow dynamics of two-homogeneens neural nebworks for small initializations, where all weights are initialized near the origin. For both square and logistic losses, it is shown that for sulficiently small initializations, the gradient flow dynamics spend sufficient time in the neighborhood of the origin to allow the weights of the neural network to approximately converge in direction the Karush-Kuhn Kanns-KKunTTuckk (KKT) points of a neural correlation function that quantifies the correlation between the output of the neural network and corresponding labels in the training data set. For square loss, it has been observed that neural networks undergo saddle-to-saddu dynamics when initialized close to the origin. Motivated by this, this paper also shows similar directional convergence among weights of small magnitude in the neighborhood of certain saddle points.
1 Introduction
Massively overparamettrizzd deep neural networks trained with (stochastic) gradient descent widely known to be imunensely successful archilectures for inference. Recent works have attributed this success to the implicit regularization of gradient descent the mysterious ability of gradient descent to find a solution that generalizes well despite the non-convexity the loss landscape, the presence of spurious optima, and no explicit regularization (Neyshabur et al. 2015 Soudry el al. 2018
To resolve this mystery, several works have studied the dynamics of gradient descent during training of neural networks (Jacot et al.) 2018 Chizat et al.] 2019 Mci et al.) 2019 Chizat & Bach 2018). An important observation emerging from these studies has been the effect of initialization
the trajectory of gradient descent. For large initialization, the gradient descent dynamics are approximately linear and can be described by the so-called Neural Tangent Kernel (NTK) (Jacot et al. 2018 Arora et al. (011b)). This regime is also referred to as lazy training (Chizat et al.) 2019). since the weights of the neural networks do not change much and remain near their initializations throughout training, preventing the neural net from learning the underlying fcatures from the data.
In contrast, for small initializations, gradient descent dynamics is highly non-linear and exhibits feature learn- ing (Geiger et al. 2020 Yang & Hu 2021 Mei et al. 2019). Additionally, the benefit of small initializations over large in terms of gencralization performance has also been observed under various settings (Geiger et al. 2020). For example, Chizat et al.
(0019) train deep convolutional neural networks with varying scales of initialization while keeping other aspects the neural network fixed, and a significant drop in performance is observed upon incrcasing the scale of initialization. In other recent works such as Jacot al.) (2022);
Boursier et al. (2022); Pesme & Flammarion (2023), a phenomenon termed saddle-to soffeett-saddlle dynamics has been observed during training. These works reveal that the trajectory of gradient descent passes through

---

Published in Transactions on Machine Learning Research (06/2024)
sequence of saddle points during training, in stark contrast to the linear dynamics observed in the NTK regime.
The investigation into the gradient descent dynamics of neural networks with small initializations has spurred numerous inquiries, yet a comprehensive theoretical framework remains clusive. The study of linear neural networks has led to valuable insights into the sparsity-inducing tendencies of gradient descent (Woodworth itt al. 2020 Arora et al. 2019a). These tendencies also appear be present in non-linear neural networks (Chizat et al. 2019 Chizat & Bach 2018), however, rigorous results are limited to two-layer Rectified Linear
Unit (ReLU)
and Leaky-Rac ReLU networks under various simple data-specific assumptions such orthogonal
inputs
[Boursier ct al.
2022), lincarly separable data (Min et al., 2024 Wang & Ma 2022 Lyu et al.
2021
Wang & Ma, 2023). the XOR mapping (Brutzkus & Globerson 2019) or univariate data (Williams
et al.
2019 Safran et al. 2022). Another important line of work has uncovered an intriguing phenomenon
of directional convergence among neural network weights during the initial training stages (Maennel et al.
2018
Luo et al. 2021 Brutzkus & Globcrson 2019 Atannaov al. 2022 Chen et al. 2023). In Maennel et al. (2018), it is shown that. the weights of two-layer ReLU neural networks, trained using gradient. flow with small initialization, converge in direction early in the training process while maintaining small norm. Although this result primarily describes dynamics near initialization, it constitutes crucial step towards a comprehensive understanding of neural network training dynamics and has contributed significantly towards
understanding the training dynamics in some of the aforementioned works (Boursier et al. 2022 Min et al.
2024 Wang & Ma 2023 Lyu et al.) 2021). However, the work of Maennel et al. (2018) is limited to two-layer ReLU networks and raises the question of whether this phenomenon holds for other neural networks.
2 Our Contributions
This work establishes the phenomenon of directional convergence in a more general setting. Specifically, we study the gradient flow dynamics resulting from training of two- wooogengesssuus neural networks near small initializations and also at certain saddle points.
A neural network H. where H(x; w) is the real-valued output the neural network, x is the input, and w is a vector containing all the weights, defined here to be (posiivvi)) homogeneous if
H(x; ew) = H((x;; w), for all 2 0.
While this class does not encompass deep neural networks, it is broad enough to include several interesting types of neural networks. Let (ar) denote the ReLU (or Leaky-ReL.U) function, then, some examples of two- two-homogeneous neural networks include
Two-layer ReLU networks: H(x: (ux, un) Et Ux up).
(x)))
Single-layer squared ReLU networks: H(x; { Et Pxo(x uu),, where Ps E (-1, 1}.
Deep ReLU networks with only two trainable layers, for example H(x: W,. W2) v ((W2a(Wi3) where is a fixed vector. We emphasize that this class includes any L-layer deep ReLU network with exactly two trainable layers (not necessarily two consccutive layers).
We consider supervised learning setup for training and assune that {xi, (1 is the training dataset, X = [XI....,x,] E idxn,, = [yt...., ..] RR, and H(X; w) = [H(x;; w)...., H(x w)] R is the vector containing the output of neural worw for all inputs, where w E R We do not make any structural assumptions on the training dataset.
In describing results, vital role is played by quantity we refer to as the neural correlation function (NCF), which for a fixed vector z E R² and neural network H as above is defined as
(z)((w)= = z T H(X:
The NCF is measure of the correlation between the vector and the output of the neural network. For given NCF, we refer to the following constrained optimization problem as constrained NCF;
max (2.x(w)..
||w|3=1
2

---

Published in Transactions on Machine Learning Research (06/2024)
Loss
Rachene
Norm weights
20000
30000
40000
50000
No. iecrations
No. of Herations
(a)
(b)
Figure 1: A two-dimensional scenario where single-layer squared ReLU neural network with 20 hid- den neurons trained by gradient descent. The network architecture defined as H(r1, (2))))) E max(0, u1 + ug,22)², where u, represents the weights for the ith neuron. For training, we use 50 unit norm inputs and corresponding labels are generated using the function (z1, = 5 max max(0, + max -2102 We use square loss and optimize using gradient descent for 50000 iterations with step-size 5 1005 At initialization, the weights of each hidden neuron are drawn from Gaussian distribution with standard deviation 10-5, Panel (a): the evolution of training loss and the 4--norm of all the weights with iterations. Panel (b): the evolution of arctan (t) (the angle ut(t) makes with the positive x-axis) for all hidden neurons. We see that the norm of the weights remain small and loss barely changes, though the weight vectors converge in direction to their final location (denoted with red dots).
Our first main result Theorem 5.1 shows that, for square and logistic loss ! if the initialization is sufficiently small, then, the gradient dynamics spends sufficient time near the origin such that the weights are either approximately O, or approximately converge in direction to non non-negative Karush- Kuhn--uuunaaaa Tucker (KKT) points of the constrained NCF
max (w)
Our next main result (Thorrem 5.5) shows a similar directional convergence near certain saddle points for square loss. Specifically, show that if initialized in sufficiently small neighborhood of that saddle point, then the gradient dynamics spends sufficient time near the saddle point such that the weights with small magnitude either approximately converge in direction to non-negative KKT points of the constrained NCF defined with respect to the residual error at that saddle point, or are approximately 0.
For illustration, we provide a brief "toy" example showing the phenomenon of directional convergence near small initialization. We train a single-layer squared ReLU neural network using gradient descent and small initialization, and provide in Figure visual depiction of (a) the overall loss and the lg norm of the network weights, and (b) the angle the weight vectors make with the positive horizontal axis, all as function of the number of training iterations. (See the figure caption for more specific experimental details.) It is evident that the training loss barely changes, and the norm of all the weights remains small, indicating that gradient dynamics is still near the origin. This is not surprising since the origin is a saddle point. However, the direc- tions of the individual weight vectors for the neurons undergo significant changes. This experiment suggests that while the gradient dynamics may not significantly change the weight vector magnitudes, it does change their directions. Further, and perhaps more interestingly, these directions not only change but also appear converge. The objective of this paper to explain how such a phenomenon could occur by just minimizing the loss using gradient descent, and also characterize the directions along which the weights converge.
Probably the most related existing work to our effort here is Maennel et al. 2018), which exclusively focuses on two-layer ReLU neural networks. Compared to that work, ours establishes directional convergence near small initializations for two-homogeneous noural networks, a much wider class of neural networks, highlighting
The results in Theorem 5.1 apply, fact, more general class of loss functions.
3

---

Published in Transactions on Machine Learning Research (06/2024)
the inherent importance of homogeneity for these types of phenomena. As alluded above, this class also includes deep ReLU networks with only two trainable layers (not necessarily two consecutive layers), for which the results of Maennel et al. (2018) are inapplicable. Further, while Maennel et al. (2018) only focuses on initialization, we also establish dircctional convergence near certain saddle points. This extension is particularly pertinent because has been observed in previous works that neural networks exhibit saddle- to-saddle dynamics under small initialization. Consequently, our result describing dynamics near small initialization and saddle points could be important for better understanding of the training dynamics in the future.
Finally, while the result of Maennel et al. 2018) has certainly advanced our understanding, their analysis near small initializations relies on heuristic arguments and are not completely rigorous; see Min et al. 20024 Section 2.2) for specific details. Our proof technique is rigorous and fundamentally different from Maennel ct al. 2018) handle a wider class of neural networks.
3 Preliminaries
In this section, we briefly describe some preliminary concepts that will be useful in rigorously describing the problem.
Throughout the paper, ||1 denotes the l2 norm for vector and the spectral norm for matrix. For any N E N, we let [N] 21.2..... ,N denote the set of positive integers less than or equal to N. We denote derivatives by =(t) dz(t) de and for the sake of brevity we may remove the independent variable t if is clear from the context. For a vector x, I; denotes its i-th entry. The k-dimensional sphere is denoted by 8k-1, A KKT point of an optimization problem is defined to be non-negative KKT point if the objective value that KKT point is non-negative.
A function f X + R is called locally Lipschitz continuous if for every x E X there exists a neighborhood U of x such that f restricted to U is Lipschitz continuous. A locally Lipschitz continuous function is differentiable almost everywhere (Borwein & Lewis 2000 Theorem 9.1.2).
For any locally Lipschitz continuous function, f X + R. its Clarke subdifferential at point X is the set
0f(x) = conv lim vf(x)) lim x, = xx,x E x 1-000
where Q2 is any full- mellure subset of X such that f is differentiable for all x E Q. The set 0f(x) is nonempty, convex, and compact for all x E X, and the mapping x + 0f(x) is hpper-semicontinouu (Clarke et al. 1998 Proposition 1.5). We denote by (x) the unique minimum norm subgradient.
Since the neural networks considered in this paper may be non-smooth (as function of w), rigorously define the gradient flow for such functions we use the notion of o-minimal structures (Coste) 2000). In particular, consider neural networks that are definable under some o-minimal structure, mild technical assumption that is satisfied by almost all modern neural networks (Ji & Telgarsky. 2020). including the
examples presented in Section 2 Formally, an o-minimal structure is a collection S [S where each Sn is a set of subsets of R. containing all algebraic subsets of R and is closed under finite union and intersection, complement, projection, and Cartesian product. The elements of S are the finite unions of points and intervals. For a given o-minimal structure S, a set A R" is definable if A E Sn. A function I D Rm with D RR is definable if the graph of is in Sn+m- Since a set remains definable under projection, the domain D is also definable; see Coste 2000 for detailed introduction of o-minimal structures.
Using the notion of definability under o-minimal structures, we define gradient flow for non-smooth functions following Davis et al. (2018); Ji & Telgarsky| (2020): : Lyu & Li (2020). A function z I - Rdd on the interval is an are is absolutely continuous for any compact sub-interval of I. An are is differentiable almost everywhere, and the composition of an are with a locally Lipschitz function also an are. For any locally Lipschitz and definable function f(x), x(t) evolves under gradient flow of fxx if it is arc, and
x(t) (x)((())), for a.e. t2 0.
(1)
4

---

Published in Transactions on Machine Learning Research (06/2024)
If xt) evolves under positive gradient flow of fxx), i.e., x(t) (x(()))), for a.c. t 2 O, we still call x(t) gradient flow of [xx). In what follows, it will be clear from the context whether it is positive or negative gradient flow.
4 Problem Setup
Within the framework introduced above, we consider the minimization of
L (ww) = Σ e (H((x;:))
(2)
where E(). y) is a loss function; this work, we assume the loss function is definable and have locally Lipschitz gradient.
Assumption 1. The loss function E(G.y) y) is definable under some o-minimal structure that includes poly- nomials and exponentials, and Vgl(f. 3) locally Lipschitz in ğ.
The above assumption is satisfied by commonly used loss functions such square loss and logistic loss. Next, as alluded above, also assume that the neural networks under consideration are tuo-homogeneoos, property we formalize via the following assumption.
Assumption 2. For any fiaed x, H(x; w) is locally Lipschitz and definable under some o-minimal structure that includes polymomials and exponentials, and for all c 2 0, H(x;cw) = c²H(x;))
In Wilkie (1996), it was shown that there exists an o-minimal structure in which polynomials and exponential functions are definable. Also, the definability of a function is stable under algebraic operations, composition, inverse, maximum, and minimum. Since ReLU ReT.U/Leaky /Leaky-ee..U neural networks involving ReLU activation function are definable (Ji & Telgarsky 2020). Also, under the above assumptions, L (w) is definable. Finally, we also require H to be two-homogeneous for our results to hold, which rules out deep neural networks such as deep ReLU networks with more than 2 trainable layers.
a maximum of two polynomials, typical
Next, since L (w) is definable, the gradient flow w(t) is an are that satisfies for a.c. t t 0
((1) E (W (t), w(0) = Swo:
where Wo vector and 8 is a positive scalar that controls the scale of initialization.
For differential inclusions, it is possible to have multiple solutions for the same initialization. This leads to technical difficulties in proving our results. We will address this difficulty by making use of the following definition which is inspired by Lyu et al. (2021) and will be discussed in more detail in the later sections.
Definition 4.1. Suppose g(w): R + IR is locally Lipschitz and definable under some o- o-minimal structure, and consider the following differential inclusion with initialization w
dw dt 0g(w), w(0) w, for a.e. t t2 0.
We say w is a non-branching initialization the differential inclusion has a unique solution for all 2 0.
Before proceeding to the main results, we briefly state additional definitions which are used in the paper. Let
B where X and y denote the training examples and labels. For z E R", we define ll2z, y) W1)..,, Vol(En,V.)) Volle,., [|z||2 < 8, then
w) Sk-1),
R². Now, since Vgl(ū.u) is locally Lipschitz in f. we define & such that if
(1( - (2. 3/1222
(4)
and 3=00 -33 (0,
5

---

Published in Transactions on Machine Learning Research (06/2024)
5 Main Results
5.1
Directional Convergence Near Initialization
We are now in position to state our first main result establishing approximate directional convergence of the weights near small initialization.
Theorem 5.1. Let Wu be unit norm vector and a non-branching initialization of the differential inclusion
ú E ON ON- u(0) = Wo-
(5)
For any E (0. m), where 1j positive constan there exist > and ō such that the following holds: for any 8 (0.3) and solution w(t) of eq.
(3 with initialization w(0) ówo, we have
[lw())2 S VCO, for all l E 0. T
where T In(C) Further, either 435
w T
[ 2 on, and
2 1
1 +
| (T(
2n
where â is non-negalive KKT point of
N- -((0,)))H((
max ||]|
or
[w I 25c.
Here, e represents the level of directional convergence of the weight, and C' represents how long gradient flow needs to stay near the origin lo ensure the desired level of directional convergence.
In words, the first part the result establishes that for a given choice of e > O, we can choose d sufficiently small such that the norm of the weights remains small for all t [o, T), indicating that gradient flow remains near the origin. The second part quantifies what happens the time T: there are two possible outcomes. In scenario, the weights approximately converge in direction towards a non-negative KKT point of the constrained NCF defined with respect to yO, and neural network H (additionally, |[w(T) 2 δn, where 17 is a constant that does not depend on 5.) In contrast, in the second scenario ||w(T))l2 S 20c, where we can choose e and both to be arbitrarily small. Thus, compared to the first scenario, in the second scenario, the weights get much closer to the origin. In fact, as it will become more clear from the proof skeich later, this happens because the gradient dynamics of the NCF can converge to
It easy verify that for square loss, ((j,y) -0 - y)²² and (0, = y. Similarly, for logistic loss, ((0.v) In(1+e 5v) and (0, y/2. Hence, for both of these loss functions, the weights approximately converge in direction towards a non-negative KKT point of
max (u) y uX: u13=11
Now, for general training data, it may not be possible to get a closed form expression for the KKT points of the NCF. In Appendix G we provide some simple examples where closed form expressions can be computed, which may be helpful the readers.
Finally, note that we require Wo to be non- non-branching initialization of eq. 5 The necessity for such requirement essentially arises because there could exist multiple solutions for differential inclusions. We discuss it in more detail after providing the proof sketch of the above theorem. However, we note that if the neural network H(x; w) has locally Lipschitz gradients then this requirement is always satisfied, since in that case eq. 5 always has a unique solution. This would include, for example, the squared ReLU neural network.
Here, y) depends on the solution eq. 5.. which solely relies X,y, H. wo, and independent of 8. See Lemma and the proof for more details.

---

Published in Transactions on Machine Learning Research (06/2024)
5.1.1 Proof Sketch of Theorem 5.1
We provide a brief proof sketch for Theorem 5.1 here; the complete proof can be found in Appendix Q The proof ultimately relies upon two lemmnas. The first one describes the approximate dynamics of w(1) in the initial stages of training for small initialization.
Lemma 5.2. Let > be an arbitrardy large constant and w(f) be any solution of eq. 13 with initialization
w(0) = Swo, where S V and l|woll2 = Then, for all t 0, In(C)
435
|I(())l2 S VCS.
VC6.
(6)
Further, for the differential inclusion
ú E ON (NN u(0) = wo.
(7)
and any e there crisls small enough δ such that for any E (0,
w(t)
0, In(C)
u(t) Se, for all i
(8)
8
433
where u(t) is a cerlain solution of eq.
The first part of the lemma shows that for sufficiently small 5 the gradient dynamics can spend an arbitrarily large time near the origin. To understand the implications of the second part, let us first focus on the differential inclusion in eq. (7, which is the positive gradient flow of the NCF defined with respect to (0, y) and neural network H. From eq. (8), we observe that for small initialization, in the initial stages of the dynamics, w(t)/5 is approximately equal to u(4). To get an intuitive idea about the proof of the above lemma, consider the evolution of w(t) near small initializations, which approximately can be expressod as
n W Vg((H(x;:)) W))H((X
Vge(O, y))OH(x;w)
Since H(x; w) is two-homogencous, we have that 0H(x; w) is one-homogeneous. Hence, dividing the above equation by we get
w/0
70, ()) =
v
ON -/N
Since w(0)/5 Wo, from the above equation observe that the evolution of w(t//ō is approximately governed by the differential inclusion in eq. (7). Thus, one expects w(1//ō to be close to certain solution of eq. provided [|w(t)]l2 remains small.
Now, since 5 is a positive scalar, dividing w(t) by does not change the direction of w(t). Further, note that the dynamics of u(t) do not depend on and the approximation in eq. ( can be made to hold for an arbitrarily long time by choosing sufficiently small 8. Thus, if we choose C large enough such that the approximation in eq. (8) is valid for a sufficiently long time in which u(t) approximately converges in direction, then by virtue of eq. (8) w(t) would also approximately converge in direction.
Thus, our aim is to establish approximate directional convergence of u(t) within some finite time. For this, we turn towards analyzing the gradient flow dynamics of the NCF. Recall that, for a given vector z, the NCF is defined as
N2 = =z]H(X;u)
(9)
and gradient flow will satisfy for a.c. t
du
di E (N,.((u), (0) = Uo
(10)

---

Published in Transactions on Machine Learning Research (06/2024)
0.5
-0.5
2
81
Figure 2: The gradient field of f(u1, u2) = u1 u1/u2//
where Un is the initialization.
Since the function value increases along the gradient flow trajectory and (2) may not be bounded from above, the gradient flow trajectory can potentially diverge to infinity and take (y) to infinity along with it. However, in the following lemma we show that the gradient flow will always converge in direction, and also characterize those directions.
Lemma 5.3. For any solution u(t) of 10 either lim N2, (u(()) oc or lime
= 0. u(t) erists then its value, say u², must Also, either lim;++c [Ju(t)]la exists or lim u(t) O. If lim, [n())l2
u(t)
a non-negnnnnnee non-negative KKT point of the optimization problem
max (N, = z ((:uu.
(11)
The above lemma states that any solution of eq. 10 will either converge to 0 converge in direction to KKT point of the constrained NCF. To establish directional convergence in the above lemma,, we follow a similar technique as in Ji & Telgarsky 20200 Theorem 3.1).
To prove Theorem 5.1 from here, we combine Lomma. 5.2 and Lemma 5.3 From a given initialization Swo.
we get Wo. Then, the solution u(l) of the differential inclusion eq. using Lemuna 5.3 we choose T large enough such that u(T) either approximately converges in direction the KKT point of the NCF or gets close 0. Then, based on that T, using Lemma 5.2 we choose ö sufficiently small such that w(t//6 is close to u(t), for all E [0, T). The result follows.
There is, however, one issue with the above argument. The differential inclusions could have multiple solutions, and in eq. (,, the approximation holds for some solution of eq. 7 it is not known beforehand which solution would be. Therefore, we would need to choose T large enough such that all solutions of eq. 7 have approximately converged in direction. However, this may not be possible for all initializations We. To illustrate this we consider a simple example.
Consider the function f(u,, U2) U1 U22 that satisfies Assumption 2 and is differentiable everywhere except along the line U2 0. In Figure 2 we plot its gradient field. Note that û [], is critical point for (w1, U2), i.c., 0 E (ū). Thus, if initialized at ú, one possible gradient flow solution is to stay at û for all 12 0. However, (ū contains other vectors which could lead to gradient flow escaping from û. Moreover, one could construct gradient flow solution that can spend arbitrary amount time at before escaping it. Specifically, for any finite T,
: for all Ee [0, 7) coos (E T") sinh (t - T)
ur(t)
for all t 2 T,
is a possible gradient flow solution. We note that lim up (t) uy (t)llz 11/22,1/V2] however, clearly for any finite time T we choose T large such that ur / [1 (T) [|2 stays away from [1/V2, 1/v2

---

Published in Transactions on Machine Learning Research (06/2024)
Thus, we not establish finite time approximate directional convergence for all possible gradient flow solutions. Complete details for this example can be found in Appendix
To address this issue, we only consider initialization which leads to unique solution. In particular, we assume Wo to be a non-branching initialization of eq. (5). As noted earlier, if the neural network has locally Lipschitz gradients, then this requirement is always satisfied. However, for more general networks such as two-layer ReLU neural networks the above assumption may appear somewhat restrictive. That said, is worth noting that similar assumption of two-layer Leaky-ReLU neural networks were investigated in simple setting involving linearly separable data. Furthermore, Maennel et al. (2018) addresses this challenge of non-uniqueness by asserting that the differential inclusion resulting from the gradient flow of the loss function will have unique solution in "almost all" cases, but do not provide a formal proof. We leave it as an important future research direction handle more general initializations.
also made in Lyu et al. (2021) where the full training dynamics
Another potential research direction is to characterize the set of non-branching initializations. For example, in the function depicted in Figure it can be shown that except for the set {u2 0, u1 > 0}, all the other points non-branching, which implies that almost all points are non-branching: for details see Lemma E.2 Whether a similar behavior happen for broader class of datasets and neural networks is an interesting future direction, and a positive answer would justify the non-branching assumption in those cases. However, establishing such a result, even for a two-layer (Leaky) ReLU neural networks, seems to be difficult. In the following lemma, we show that for two-layer Leaky-ReLU neural networks there exists sets, near certain KKT points, within which all points are non con-bancching We hope can help futurr works in better characterization of the set of non-branching initializations.
Lemma 5.4. Let H(x;0, v, u) (x u), where (x) max(x, az), for some E R. Suppose {u., u. is KKT point of
max NN u) = uz (X
where v,2" oX u.) > 0 and min;e[m] the set = {u. u sign(v.)o > || 2 inclusion
x u.l > 0. Then there erists a y > O such that every element of
u u. 12 S 7} a non-branching instialization of the differential
N,,N u) ú Nz,
The proof can be found Appendix Note that in the above lemma minggn]] |x] u,| >> 0 implies that the hyperplane defined by u, does not pass through any vector in the training set. Also, although we have only considered single neuron, the above lemma can be extended multi-neuron setting by ensuring that the initialization of each neuron is in set similar to S.
5.1.2 A Corollary for Separable Neural Networks
We next consider the case when H(x; w) is separable and can be divided into smaller neural networks. In the following lemma, describe the directional convergence for such neural networks near small initialization.
Corollary 5.4.1. Suppose Consider the same setting as in Theorem 5. then, for any c E 1), where n) is positive constant, there cxist C >>> 1 and 8 >0 0 such that for any 8 (0,3), and for all E [H], either
write Ww...., wH] such that H(x; w) = Hx(x; wi), for all x.
VC 2 |w, (T) 2 8n, and (T ú [w)(
(1 (1
e,
2n
where ú, is non-negalive KKT point of N N_ -0( (X:
(12)
or
[w; S 28c, where -= In(C)
43/
9

---

Published in Transactions on Machine Learning Research (06/2024)
25
1000
00040
2000
(1020
[in meliona)
Figure 3: The lower part shows the content of Figure Lb with the horizontal and vertical axes interchanged. The top plot shows the constrained NCF Ny, (0) Eim1 U: max(0, Corollary 5.4.1 the neuron weights converge in direction to the KKT points of the NCF.
xx)) As predicted by
The above result establishes that for separable neural networks, the weights of smaller neural nelworks ap- proximately converge in direction to the KKT points of the optimization problem in eq. 12 the constrained NCF defined with respect to the output of smaller neural networks.
Indeed, this is precisely what we observed for the "toy" experiments depicted in Figure Recall, in that case, the neural network In the bottom of Figure 3 we again plot the evolution of the direction of the weights for each hidden neuron. On the top, we plot the constrained NCF with respect to the output of each neuron, which will be identical for each neuron. We clearly observe that the weights of each neuron converge in direction towards KKT points of the constrained NCF.
the sum of squared ReLU functions and hence satisfies the setting of Corollary 5.4.1
Finally, we would like to emphasize that while in Theorem 5.1 the directional convergence is established for all the weights, Corollary 5..41 further establishes directional convergence for weights of smaller neural networks as well. In fact, the results in previous works 2-layer ReLU neural network (Maennel et al, 2018), which is separable, are along the lines of Corollary 5.4.1 and it is possible to gel. those results using Corollary 5.4.1 We provide these details in Appendix
5.2 Directional Convergence Near Saddle Points
Several theoretical and empirical works have observed a saddle-to-saddlee dynamics during training of neural networks with small initialization and square loss (Jacot al.) 2022 Pesme & Flammarion, 2023 Boursier et al. 2022 Jin et al.] 2023). The evolution of loss alternates between being stagnant and decreasing sharply, almost like a piecewise constant function. This indicates that weights move from one saddle of the loss function to another during training. Some theoretical works further show that at each saddle point only certain number of weights are non-zero. For example, Pesme & Flammarion (2023) proves saddle-to-saddlee dynamics two-homogeneons diagonal linear networks, where at each saddle points only few weights are non-zero. The authors of [Boursier et al. (2022) study two-layer ReLU network with orthogonal inputs, and show that gradient flow enters neighborhood of saddle point where one set of neurons have high norm while others have zero norm.
In this section, we show that the directional convergence near initialization described in the previous section also occurs near certain saddle points for square loss. However, there could be different kinds of saddle points throughout the loss landscape. The choice of saddle points considered here is motivated by the above observations, such as only a certain number of weights being non-zero at the saddle points.
We assume that the weights of neural network w can be divided into two sets, w [W,, w. such that H(x; w) H., (x; w.) + H. (x; w.), where H., (x; w.) and Hz(x; wz) each satisfy Assumption 2 For square
10

---

where à is non-negative KKT point of Published in Transactions on Machine Learning Research (06/2024)
loss, minimize
1 n L (ww: W:) = Σ
1 2 (X; w.,) +xx(X: - yyl? (13)
(x; wn.) Hx( w.) -vill -
The saddle point of eq. Assumption We assume (Wn, W saddle point of eq. 13 such that
13 that we consider here satisfies the following.
Wall2 E [m, M), and
= 0,
(14)
where m, M are positive constants. Further, (x; w.)) does not have a locally Lipschitz gradient, then we assume that there crists 7,K >> 0 such that for all Wn satisfying l|w,, wnll2 S y it holds that
Wn, s)
Wn - where -dw, LWwn, 0).
(15)
In the above assumption, Wn is the set of weights with high norm while w, contains sets of weights with zero norm. Due to homogeneity, (x; W.) = O, and thus Hn (x; is effectively the output of the neural network at (W,, W
When Hn wn) does not have locally Lipschitz gradient, we require eq. 15 to ensure that if w, initialized near Way then stays near it for sulficiently long time. We discuss the motivation for this inequality after discussing our main theorem of this section, stated below.
Theorem 5.5. Let (w,, W2) satisfy Assumption and define y= y (X; Wa). Suppose Ca is wnit norm vector and non-branching initialization of the differential inclusion
ú E ONy. (u), u(), Cz.
(16)
and such that the following holds: for any 8 (0,8) and gradient flow solution {w (t), wt(() of eq. (13) that satisfies for a.e. 2 0
For any E (0, n), where 1j posilive constan 3 there exist
W
Tw.. L (W,, Wx)
W (0)
+ 8Gn
(17)
w
Ow: L (Wn, w=)
(0)
w + 8G=
where Sn is unit norm vector, we have
[[w,(t) wnll2 (t) W C8,, for all t [0,T]
(18)
where T 1 In (C), and M2 is constar Further, either M2
I| (T) 8n and (T) ú
3 2n
21 - 1+
E,
(W)(T))la
NG.H (u) (X:
max ||
Iw, (T)(T $ 28c.
In the above theorem, the initialization is near a saddle point which satisfies Assumption 3 and å controls how far the initialization is from the saddle point. The vector y represents the residual error at the saddle point and plays the same role y0) did in Theorem 5.1 Provided (. is non-branching initialization
Here, ry depends the solution of eq. 16 which solcly relies X. Ha. and is independent of 6. See the proof for more dctails.
4 M2 depends 9, ||y]] and various parameters associated with Ms and Hn near (W., wa} such their Lipschitz constant, maximum value etc. Importantly, it does not depend and
11

---

Published in Transactions on Machine Learning Research (06/2024)
of eq. [6),, we show that for sufficiently small ö, the gradient flow spends enough time near the saddle point such that weights of small magnitude either approximately converge in direction to the KKT point of the NCF defined with respect to y and Hz, or gets close to O. The above theorem, similar to Theorem 5.1 shows directional convergence among weights of small magnitude. The proof tochnique is similar to the proof of Theorem 5.1 for details see Appendix DJ We also demonstrate the phenomenon of directional convergence near saddle points using a numerical experiment in Appendix D
We next explain the motivation for eq. 115 in Assumption 2 when (x; wx) does not have locally Lipschitz gradients. Our proof of the above theorem crucially relies showing that wn((t remains close to w,, and (=(t) remains small for a sufficiently long time; i.c., eq. (18) holds. Suppose w=(t) remains small, then the evolution of w,(() (4) is approximately governed by the gradient flow of L (w., 0). To understand the gradient flow dynamics of L (Wn, 0) near Wa, we use the following lemma.
Lemma 5.6. Suppose (wn, W is soddle point of eq. 13 such that W E [m, M,, and W = 0. Then,
O E 3w. L (Wn,0)
If Hn, (.) has locally Lipschitz gradients, then Vw. L (w., 0) would be small and vary smoothly in the neighborhood of w.. This suffices to ensure that if w,, (0) is close to Wn, then wn.(!) remains close to W, for a sufficiently long time.
However, if Hn wn) does not have locally Lipschitz gradients, then 0 E aw. L (w,,. 0) but dw., L (w,. . 0) may be large near Wn. This prevents us from ensuring (t) remains near Wn For example consider g(u) (u, |u2 1)2 and let ú [1, Then, 0 E dg(ū). Let u [1 + 5, 6|" Then, for any E (0, 0.1) and s E 00(() ||s||2 2 1, and no matter how close u is to u, if initialized at u², the gradient flow will quickly get away from ú (see the Appendix for details).
Hence, we require eq. 15 which implics that 6w. L(Wn, 0) varies smoothly along w,, - W,.- This sufficient for us to ensure w.. (4) remains near Wn- In fact, if Hr (x; w.) have locally Lipschitz gradient, then eq. 15 is automatically satisfied, since
(w,, W.. s) 2 - -|,,, - Wa V/ll2/12 Vw, L (w 0) 1|2
= = -W,,,, - w.ll21 V L (w,,, 0) - V w., L ( 0) l1 -x|[w, w., -w,
where the equality holds since w... and the loss function have locally Lipschitz gradient. We also note that if the gradient of H. w.) is not locally Lipschitz globally, but is locally Lipschitz in the neighborhood of wn, then eq. (15) is also satisfied. For example again consider g(u) = (ny |42| - 1)² and let ú = []. Then, is easy to show that 0 E (g)ū and g(u) has locally Tipschitz gradient around ú.
L (w,,
0 from Lemma 5.6 The last inequality follows since Hn
5.3 Higher Orders of Homogeneity
Given the results of Theorem 5.1 and Theorem 5.5| it is natural to ask whether neural networks with higher orders of homogeneity also exhibit similar behavior. Presently, we are unsure if such a behavior is possible. The main difficulty due to the relative scaling between the weights and the gradient at small initialization. From our discussion in Soction 5.1.1 we know that near small initialization, the evolution of w(t) can approximately be expressed as
W R
V VeE yi (xH()(
Now, from Lemma B.1 we know that if H(x; w) is I-homogeneous, then 0H(x; w) is (L (6-1)-im 1)-homogeneous. Thus, if [[w( scales as 8, then |[H((x w(0) is expected to scale as 81.11 For L = 2, (0)l0 and |XH((x; (0))ll2 both scale as 8. Hence, for small 8, in the initial stages of training, the gradient flow will not change the norm of the weights significantly, but can have significant impact on its direction. However, for L > 2 and small 8, the gradient is smaller than the weights, where the relative scaling between the two
12

---

Published in Transactions on Machine Learning Research (06/2024)
further worsens upon increasing L. Thus, it seems that, in the initials stages of training, the gradient will not have much impact on the direction and magnitude of the weights. Nonetheless, it is possible that in the slightly later stages of training the gradient can be large enough to change the direction of weights. However, it is unclear to us how to rigorously analyze such scenarios and is therefore a subject of future research.
6 Conclusions and Future Directions
In this work, we studied the gradient flow dynamics of two-homogeneous neural networks near small ini- tializations and saddle points, and showed the approximate directional convergence of their weights in the initial stages of training.
An important future direction is, of course, to study the entire gradient flow dynamics of neural networks, and our work could be an important step towards a comprehensive undorstanding of training dynamics of neural networks. Particularly, for successful training under small initialization, the gradient dynamics will have to eventually escape the origin. The escape direction may be determined by the directions to which the weights converge while the dynamiis is near the origin. This also holds true while escaping other saddle points encountered by gradient dynamics during the training process, which notably is known to undergo saddle-to-saddle dynamics.
Another possible future direction is to investigate similar directional convergence in deeper neural networks. For non-smooth neural works,, we required an additional assumption on the initialization to ensure unique- ness. would be interesting to analyze scenarios when such assumptions do not hold. We defer that to a future investigation.
Acknowledgments
The authors graciously acknowledge gift funding from InterDigital, which partially supported this work.
References
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Newral Information Processing Systems, 2019b.
Alexander Atanasov, Blake Bordelon, and Cengiz Pehlevan. Neural networks as kernel learners: The silent alignment effect. In International Conference on Learning Representations, 2022.
J. M. Borwein and A. S. Lewis. Conves Analysis and Nonlinear Oplimization. Springer Verlag, Berlin, Heidelberg, New York, 2000.
Etienne Boursier, Loucas Piliend-Vivien, and Nicolas Flammarion. Gradient flow dynamics of shallow reLU networks for square loss and orthogonal inputs. In Advances in Neural Information Processing Systems, 2022.
Alon Brutzkus and Amir Globerson. Why do larger models generalize better? A theoretical perspective via the XOR problem. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Zhengan Chen, Yuqing Li, Tao Luo, Zhangehen Zhou, and Zhi-Qin John Xu. Phase diagram of initial condensation for two-layer neural networks, 2023.
Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for ovar-parameterized models using optimal transport. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Lénaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Aduances in Newral Information Processing Systems, 2019.
F. H. Clarke, Yu. S. Ledyaev, R. J. Stern, and R. Wolenski. Nonsmooth Analysis and Control Theory. Springer-Vertee Berlin, Heidelberg, 1998. ISBN 0387983368.
F.H. Clarke. Optimization and Nonsmooth Analysis. Wiley New York, 1983.
M. Coste, An Introduction to O-minimal Geometry. Dottorato di ricerca in matematica / Università di Pisa, Dipartimento di Matematica. Istituti editoriali poligrafici internazionali, 2000. ISBN 9788881472260.
Damek Davis, Dmitriy Drusvyatskiy, Sham M. Kakade, and J. Lee. Stochastic subgradient method converges on tame functions. Foundations of Compulational Mathemalics, 20:119- 2018.
Aleksej F. Filippov. Differential equations with discontinuous righthand sides. In Mathematics and Tts Applications, 1988.
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020(11):113011, nov 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, 2018.
Arthur Jacot, François Ged, Berfin Şimgek, Clément Hongler, and Franck Gabriel. Saddle-to-saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity, 2022.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In Advonces in Neurul Information Processing Systems, volume 33, 2020.
Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Shaolei Du, and Jason D. Lee. Understanding incremental learning of gradient descent: A fine-grained analysis of matrix sensing. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Tao Luo, Zhi-Qin John Xu, Zheng Ma, and Yaoyu Zhang. Phase diagram for two-layer relu neural networks infinite-wice limit. Journal of Machine Learning Research, 22(71):1-47, 2021.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. In Advances in Neural Information Processing Systems, volume 34, 2021.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient descent quantizes relu network features, 2018.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mcan-ficld theory of two-layers neural networks: dimension-free bounds and kernel limit. In Proceedings of the Thirty-Second Conference on Learning Theory, pp. 2388 2464, 2019.
Hancheng Min, Enrique Mallada, and Rene Vidal. Early neuron alignment in two-layer reLU networks with small initialization. In The Twelfth International Conference Learning Representations, 2024.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role implicit regularization in deep learning. In ICLR (Workshop), 2015.
Scott Pesme and Nicolas Flammarion. Saddlo-to-saddle dynamics diagonal linear networks. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Itay Safran, Gal Vardi, and Jason D. Lee. On the effective number of linear regions in shallow univariate reLU networks: Convergence guarantees and implicit bias. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. J. Mach. Learn. Res., 19(1):2822-288) Jamuary 2018.
Mingze Wang and Chao Ma. Early stage convergence and global convergence of training mildly paramcterized neural networks. In Advonces in Newral Information Processing Systems, volume 35, pp. 743 756, 2022.
Mingze Wang and Chao Ma. Understanding multi-phase optimization dynamics and rich nonlinear behaviors of reLU networks. In Shirty-seventh Conference on Neural Information Processing Systems, 2023.
A. Wilkie. Model completeness results for expansions of the ordered field of real numbers by restricted plasfian functions and the exponential function. Journal of the Americon Mathematioal Sociely, 9(4): 1051 1094, 1996. ISSN 08940347, 10886834. URL http::///tttt http://ww....trrooo/ooo.oo jator org/sttable/2122111
Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. Advonces in Neural Information Processing Systems, volume 32, 2019.
Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Proceedings of Thirty Third Conference on Learning Theory, pp. 3635-3673, 2020.
Greg Yang and Edward J. Hu. Tensor programs iv: Feature learning in infinite-width neural networks. In Proceedings of the 38th International Conference on Machine Learning, pp. 11727 11737, 2021.
Appendices
A Key Properties of o-minimal Structures and Clarke Subdifferentials
In this section we give a brief overview of o-minimal structures, and the relevant properties of Clarke subdifferentials that are used in the proofs our results. We borrow much of the discussion below from & Telgarsky (2020): Davis et al. (2018)
An o-minimal structure is a collection S 1 where each Sn is set of subsets of R", that satisfies following axioms:
The elements of S are finite unions of points and intervals.
All algebraic subsets of T are in S.,
For all n, Sn a Boolean subalgebra of the power set of I
If A E Sn, B E Sm, then A x B Sntm
If 1 R" the projection on first coordinates and A Sn+1, then P(A) Sn.
For a given o-minimal structure S, a set A C R" is definable if A E S,, A function f D - RT with D c RD is definable the graph of f is in Satm- Since a set remains definable under projection, the domain D is also definable.
In Wilkie (1996). it was shown that there exists an o-minimal structure in which polynomials and exponential functions definable. Also, the definabiliyy of a function is stable under algebraic operations, composition,
15

---

Published in Transactions on Machine Learning Research (06/2024)
inverse, maximum, and minimum. Since ReLU and Leaky-ReLU can each be expressed as maximums of two polynomials, it can be shown that the functions we will consider in this paper are definable.
It is also true that deep neural networks with ReLU or Leaky-ReLU activation, and different kinds of layers, are definable. For completeness, we state that result here as a lemma.
Lemma A.1. [ji & Telgarsky 2020, Lemma B.2) Suppose there exist k. do. di,..., dp > 0 and L definable functions (f1,...,9) 9L) where Jj R x x Rdj-1 x R - IRdd, Let h1 (x, w) = (x, w), and for 2 i L,
hy(x, = (x 11 (x, w),.., - (x, w), w)
then all bij are definable. (II suffices if each oulpul coordinate of 94 is the minimum or marimum over some finite set of polynomials, which allows for linear, convolutional, ReLU, mar-pooling layers and skip connections.)
We also note that, since definability is stable under composition, the objective functions arising for definable losses are also definable.
A.1 Chain Rules for Non-differentiable Functions
Recall that for any locally Lipschitz continuous function f X + R. its Clarke subdifferential at point x E X is the set
0s(x) = conv lim vx(x)) lim x; = x 1-500
where Q is any full-measure subset X such that f differentiable at each of its points, and 0f(x) denotes the unique minimum norm subgradient.
The functions considered in this paper be compositions of non-differentiable functions. We Clarke's chain rule of differentiation, described in the following lemma, compute the Clarke subdiffcrentials in such cases.
Theorem 2.3.9 ) Let hi,...,,,, An TRd R and g TR R be locally Lipschilz functions, and f(x) ((h1(x),...... ..... hn (x)), then,
Lemma A.2. CClare 1983
0f(x) S conv Σ asS Si E ah,(x), e 0g(h1 (x)x)))))....,((()))
The chain rule for gradient flow described in the next lemma, which is crucial for our analysis, essentially implics that for differential inclusions fx(x) plays the same role as Vf(x) does for differential equations. Lemma A.3. (Davis et al., 2018, Lemma (. & Telgarsky, 2020, Lemma B.9) Given locally Lipschilz defimable function f D with an open domain D, for any interval I and any are T + D, il holds for a.e. t 1 that
d(f(x(()) (x" x()), for all x²) E Of(((()).
di
Further, x 1 D salisfies
x E 0f(x), for a.e. t2
then, il holds for a.e. 12 0 that
x(t) Ff(x(t)), and d(s(((()) (1f{(((t))
dt
and therefore,
f(x(t) f(x(0)) / [0f(x(s))3dss,4 vi
16

---

Published in Transactions on Machine Learning Research (06/2024)
A.2 The Kurdyka-Lojasiewica Inequality
For gradient flow trajectories that are bounded, the Lojjsku-Lojossiwwiiz Inequalily is useful for showing convergence, essentially by establishing the existence of a desingularizing function, which is formally defined as follows.
Definition A.1. A function v : 10, + R is called a desingularizing function when V is contintous on v0, with v(() = 0, and it is continuously differentiable on (0, with W/
The following lemmaa, which can be seen as an unbounded version of the plays an important role in establishing the directional convergence of gradient flow trajectorics of the ncural correlation function where the trajectories can be unbounded.
Inequality,
Lemma A.4. (Ji Telgarsky, 2020, Lemma 3.6) Given a locally Lipschitz definable function f with an open domain D C. {x 1), for any c, > O, there exists > and definable desingularizing function V on [0, such that
((((x)))xxla|||[( 2 1, of fxx) E v0 and (0)](() 2 clxx1310,
where 0,f(x) = (0f(x): | | and f1f(x)= = 0f(x) - 0x,(x).
B Additional Notation and Some Preliminary Lemmata
For notational convenience when dealing with Clarke subdifferentiall, introduce the following notation for sets containing vectors.
YA, C Rd. A = (xty:X
BB C Rd and E IR, cB = y
YB C Rd. and p e Rd (p. == (p"y y CR
For any norm || on Rd B = y
The following lemma states two important properties of homogeneous functions.
Lemma B.1. ( Lyyu & La 2020, Theorem B.2), {Ji & Telgarsky, 2020, Lemma C.1)) Let F FRR R be locally Lipschitz and L positively homogencous for some L >> 0, then:
For any w E 12 and c 2 0,
0F(cw) ch -F(w)
For any w E R
w LF(w), for all E OF(w).
This result gives rise to the following corollary, which we use frequently in our analysis. Corollary B.1.1. For any E R and 2 0,
w s 2HH(x; w), for all E OH((x w),
and
0H(x; = c0H(x;w).
C
Proofs Omitted from Section 5.1
In this section we first prove Lemma 5.2 and Lemma 5.3 and then them to ultimately prove Theorem 5.1
17

---

Published in Transactions on Machine Learning Research (06/2024)
C.1 Proof of Lemma 5.2
To prove Lemma 5.2 make use of the following lemma. It shows that if two differential inclusions are initialized at the same point, and the difference between them is small in a bounded interval, then the difference between their solutions is also small. This is well-known stability result (Filippov 1988 1, Section 8); we provide a proof in Appendix J for completeness.
Theorem
Lemma C.1. Consider the following differential inclusions for L [];
dů OH(( ú), ū(0) = uo.
E
(19)
dt
and
du
E Σ (z: + ((0))0H(x;3)) u(() = 11;
(20)
dt
all i [n]] and [0. Then, for any 6 0 there erists a 6 > such that for each solution u(t) of eq. (0) there erists solution ü(t) of eq. [9 satisfying
where T is finite, and (t)(2 S 8 for
max eE(0,T]
[lu(() m()]22 S.
(21)
Proof of Lemma 5.2 Using the chain rule from Lemma A.2 the gradient flow dynamics are
w E
V (H(xx: v.) OH((;; w), w w(0) = dwo-
(22)
Now, we define z(t) = [/w( and note that =(0) = 82 < 1/C'< <. Since w(t) continuous function, so is 2tt). Hence, there exists some y > O, such that for all E (0,7), z(t) 1. We define T to be the smallest > O such that =(7)- 1. It follows that for all / E [0, T, =(1 11.
Now, if =(t) < and since 3 [| H(X: w)ll2 E S*-1), then || (()) - (ll( < 8, for all
E [0, fj. From the definition of 3 in eq- we get.
(H w < H w())la (1 < 10 =3.
From the above equation and using Corollary B.1.1 we have
: = 2w w Vgll (H(x;; w), w: H(x;; w) - -4H(X; ((H( s <33|w 4,32, (23)
and so =(1) ResBör which implies
f In
4
82
Further, since 8 <
1 vo. we have that
In (C) < T implies
483
In (C)
x(1) < C82 vt E
0,
(24)
433
Now, consider é E 0,
In(C) 4/3
Note that
H(X;; w())]l2 & Bl( < 3C8.
(25)
18

---

Published in Transactions on Machine Learning Research (06/2024)
Define E(t) w(t)) - y0, then,
||(())22 = - (0,,))) s (II w(1)l2 s B3Co2.
Next, the dynamics of w(t) can be written as
W E Σ (H((; w), 16) (H)()) = (.0)))))))
(26)
==1
Dividing eq. 26 by 6, from 1-homogeneity of 07((x; w) (corollary
B.1.1 we have
Σ
ge (0, 91) (/11))
(27)
Now, consider the differential inclusion
dw dt
Vyl (0())))();; w) w(0) Wo-
(28)
Using the fact that for all t E
[0, In(C)
|lE(t)l2 s 83, and using Lemma C.1 have that there exists
433
small enough 8 such that for all 5 < 6,
w(t) ((()
S
2
where w(() solution of eq. (88).
C.2 Proof of Lemma 5.3
Recall that (u) = TT (X: u). Throughout this section, for the sake of brevily, we will use N(u) instead of (u). The gradient flow ut)) satisfies, for a.c. 2 O,
du di
E (NN(u)
Σ u)) = Un-
(29)
We will first prove some auxiliary lemmata. The first follows simply from two-homogeneity of Nu) and Lemma B.
Lemma C.2. For any (N) S u 2V) For any 2 0, (N((c) caN(u)
The next lemma states that if the initialization is non-zero, then gradient flow stays away from the origin for all finite time.
Lemma C.3. Suppose u(t) is a solution of eq. 29 where u is a non-zero vector. Then, for all finite 1>0 0, [|u(t)]22 > 0.
Proof. Since |lu(0) > 0, from continuity of u(t), there exists some y > such that [|((t]]22 > 0, for all E 7). For the sake of contradiction, suppose there exists some finite T > 0 such that [|u(T) l = 0 for the first time. Then, for all 1 [o, T), [[n(1]]2 > 0. Since for a.e. i. E (0,
dlog([|u(33 dt
1 d d|
4z H(X: u) 2 4,1122|22
| dt
it follows that for all e (0,7),
| 12 N un 12 1111
Taking L. - T, we have [|u(T)]
> ||00/30-000 -1
0 which leads contradiction.
7
19

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma C.4. If (u((t)) 0, for any to 0, then, NN(((t) 2 0 and ||u(t)]l2 |u((t)]l2, for all t 2 to.
Proof. Since, using Lemma A.3
N(u(()) - (V(((o)) / [|ú(s)]Bds
we have that for 2 to, (u((()) 2 (u(((o)) 2 0. The second claim is true since for a.e. t 2 0, implies
dilull 4N(u)
dt
[u(1]1 |lu(6))122 4 of." N(u(s))ds O.
The following lemma states the conditions for first-order KKT point of the constrained NCF.
Lemma C.5. If a veclor u² E Rx11 is a first-order KKT point of
max N(u) H((x;
(30)
then
2, (H((x; = X'u", ||u = 1,
(31)
where X" E IR the Lagrange mulltpphier. X #20 O.
Also, 2V(u") X and hence, for a non-negalive KKT point
Proof.
The Lagrangian is equal to
L(u, A) = Nuu) + X([|u] -))
If u" is first-order KKT point then it must satisfy the constraint set and, for some X,
0 @ +
implying
0 E 2, OH((x; + 2'u".
1=1
Choosing X" = -2 we get eq. 31
By Lemma C.2
x = X I 2 = u aN(ut) = 2N""")
In the following lemma we define Mu),, which is central to our proof, and its minimum norm Clarke subdifferential.
Lemma C.6. For any nonzero R define N(u) Nuu)/ I| then,
aÑ(u)= = { s
||ul | SE aN(w)) - (((( =
2N(u)ul
uu
s ||u||
)N(m))
s
and
TN(u))
uu
@N(u)
|u|]
20

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. First, note that (u) is differentiable if and only if (u) is differentiable. Therefore, for any non-zero u such that (u) is differentiable,
VV(()) VW(u)
2u)
|
The first claim follows from the definition of Clarke subdifferential and Lemma C.2 note that
For the second claim,
uu = |s|2
4N(
4N(u)²
S
+
|u|
|
where s (u),,, for all @V(u). Hence, for the minimum norm subdifferential of N(u), we must choose the minimum norm subdifferential of (u)).
We now proceed to proving Lemma 5.3 We begin by showing that either u(t) converges to lim u(t)/|lu(()l2 exists. We consider two cases.
Case 1: (o)) > 0.
In this case, we show that limy-soo u(t)/ ([)(( exists using a similar technique as in Ji & Telgarsky (020 Specifically, we show that the length of the curve swept. by u(t)/|]u((()B which defined as
de,
|u|| 2
has finite length, and thus lim u(t)/|u((() exists.
We assume (Nu(()) y O, and thus [u(0]]2 0. From Lemma C.4 for all 2 0,
N(((()) 2 (N(((0)) 7
implying
d u 2 Tu 2N(u(()) 2 2y, for a.e. 2 0,
di
which in turn implies
[ > |m(0))113 + 4yt, for all t 2 0.
(32)
Recall that (u)) (u)/llll Since ||u()]]22 0, (u(()) is defined for all 2 0. Also, by Lemina A.3 for a.e. 2 0,
dV(u))
| and ń = (u)...
dt
Therefore, using the chain rule from Lemma A.3 for a.e. 2 0 we have
dN(u) T (I unT |
@N(u)
@N (I un?
TN(u) 2 0,
(33)
dt
|u| 2
where in the second equality we used that ú = (N),,, for a.e. 12 0. Hence, for all /2 2 41 2 0,
(1- uu" T N(((())) - ((u(()) 1" TN(u)
AN(u)dt 20
|
Therefore, (u(())) is increasing function, and hence, for any t 2 0, that M(((t) 2 ((u(O)) implies N(((()) ((((()))()(())13
21

---

Published in Transactions on Machine Learning Research (06/2024)
From the above inequality and eq. 32 we have lom M(((()) oc.
Now, since (u) < |x|a||H(X;))) u)حز < / / we have that N(u) is bounded. Hence, by monotone
convergence theorem, lim N (u(t)) exists; here, we suppose it equal to f.
Note that, by the chain rule, for a.c. 0,
u
I
uu
uu T
aN(u) |
dt
|ul2
|
2
|uul2
u
implies
d
|TT uu
aN(u)
(34)
dt
|u|
|
Suppose (u(t)) converges to f in finite time, i.., (u((T) f for some finite T. Then, for a.c. 2 T. aN(u) 0 implies dt
[ u(t)(())
aN(u(())
=
Therefore, from eq. 34 we have
d = 0, for a.e. t T,
dt
||u||2
and hence, lim
u(t) ne(llla exists and is equal to [
UTT
Thus, we may assume - (Nu(t)) > 0, for all finite t. Define g(u) = (u)). Then, since
(0)N(1))22 =0
we have that
g 2 ||u||||@,ggu\)|l
Hence, from Theorem A.4. there exists v > 0 and a desingularizing function V((-) defined on [0, v) such that if [|lll2 and g(u) < v, then
1 s v [(g(()))lllll@d w'(f V
(35)
Since lim N (u(t)) J, and eq. 32 holds, may choose T large enough such that ||u(t)]22 1, and g(n(()) < v, for all 1 2 T. Hence, for a.e. 12 T.
(u aN(u) dt
I uu T
uu
dN(u))
(u)
(N(()
| 2
|
[
| l
uu
(N(u))
d
11
Ju 2
|u]
dt
[
2
||ula |aN (w)l
u
dtt
d
w' - Nu)))
dt
|||||2
implying
d
dV - N()))
dt
[ 2
dt
22

---

Published in Transactions on Machine Learning Research (06/2024)
In the chain of equalities and inequalities above, used Lemma C.6 for the fourth equality, and for the first inequality we used eq. 35 Now; integrating both sides of the above from T to any 4 2 T, we have
11
dt I VT
v( & ( ((((T)) < 00,
dt
|
which implies
u
d
u
d
u
di
dl
db
|
12
dt
1
dt
||u||2
d
11
dt (T - ((((T))) <0,
dt
u
completing the proof.
Case 2: ((u(0)) 2 O. In this case, we may further assume that NN((t)) S O, for all 2 0, since if for some finite MV(((t) > 0, we can use the proof for Case 1 by choosing 7 as the starting time to prove the claim. Thus, we assume ((u(t)) O, for all t t20 0. Now, since
dd d
2 dt = - ú =='u=22(u((t) S O, for a.c. t 0,
it follows that []u(t)]l2 decreases with time. Hence, lim; [[u())lla exists. Tf lim [|u(()]l2 = 0, then lim u(t) = 0 and lim ((u(t)) = 0 and we are done.
Otherwise, assume that lim [|(([]]2 7 0. In this case, since []u(()]22 is a decreasing function, [|u(t]]l2 2 77, for all 2 0. Since by Lemma A.3 for a.e. 2 0,
dV(u)) = 1
dt
we have that ((((t) increases with time. But, we also assume M(u(()) & 0, and so by the monotone convergence theorem, (u((()) converges. We further claim that lim NV((t)) = 0. Suppose for the sake of contradiction limy N(((t)) = -y < O. Since N(u(t) increases with time, we have ((u(t)) S --, for all 1 0. Hence,
1 d u 2
n T 2N(u(t)) S -2,, for a.c. 12 0.
2 dt
The above equation implies that [|u(t)l22 will become less than n within finite time, which leads to a contradiction, and therefore, lim,- (N(())) O.
We next show that lim u(t)/[[u(()] exists. We can do this in same way in the proof of Case 1. Define û(t) 2u(t)/m, /n, and note that if û(t) converges in direction, then u(t) also converges in direction. We make this transformation because to Lemma A.4 require [|u(t]]22 1 after some time T. While u(t) may never exceed 1, we do have []((()]2 2 1, for all 12 0.
Next, (u((t) is defined for all t 2 0, since ||u(t)]l2 > 0 for all t 1 0. Also, since (u(()) converges to 0, (u((t) also converges to O. Also, ((((t) = (ūtt), thus (ū((t)) converges to 0 as well. From here to prove directional convergence of úit) we can use the the same approach as in Case 1, specifically from eq. 34 onward.
We next turn lowards showing that if lime-soa T[[ exists, then the limit must be a non-negative KKT point of the constrained NCF. Suppose u² is the limit. We have already shown that N(u*) = Mu') 2 0. Thus, we only need to prove that u² KKT point, i.e., from eq. (1). must satisfy
u(e)
2N(u")u" e @N(("))
(36)
23

---

Published in Transactions on Machine Learning Research (06/2024)
Assume for the sake of contradiction that there exists some y such that for all @N(u"), we have
||s 20-2NNu">> J 12 2
(37)
Define {u | uIll S <... Given 7, by upper semi-continuity of the Clarke subdifferential, we may choose c E (0, sufficiently small such that for all E ue, we have
(u(u)= E {p: q+r,q (N(""), ||ll2 S 7/4).
(38)
u(t) Since |
converges to u', and (u) is continuous, we can choose T large enough such that for all t 2 T
u(l) u² S and 2u(l) N |u(t]l22
u(t) [Tu(t)l2) - 2u 2n' 57/4.
(39)
[|(()]l2
Suppose 8 E (u")), then, for all E R
{0) we have
uu
(u)
(N(u)
2uV(u)
|ul|
|
u
2
2u
aN
N
l
|ul|2
|
||2
2u
$
.V
aN
|ul|a
u
|
2
2u N ||u||
||s 2n M (u")
)ll
ØN
2u N (u")
||u|||
|
where in the sccond equality used 1- h-mooggnnyyty of @V(u) and 2 homogeneity of M(u), and the inequalities follow from triangle inequality of norms.. Hence, for a.e. 2 T, using eq. eq. (39) we have
37 eq. (38 and
(T-
T())(())) [N(u(t)) 27 2-4-7/4-/44 7/2, [|u(t)] [|a(t)]la 1
implying
d. (N di (N (T((O))))
(11
u(tu(T)
ON (u((t))
2 2//4
[n(0) [u(t)]la
2
which contradicts the fact that limp .
m(t) [
converges, thus proving our claim.
Now, before we lurn to prove Theorem 5.1
we state another useful lemma.
Lemma C.7. lime u(l) * 0, then there erists > and T 2 0 such that [[u(()]la 2 n, for all / 2 T.
Proof. The proof is built using the argument already presented in the proof of Lemma 5.3 and we consider two cases.
Case 1: (u())) > 0. We assume (()))) 7 0, and therefore, ||u(0)]12 0. From Lemma C.4 for all t 0, we have
((u(t)) (u((0)) 7, which implies
d u dl
Tu -2N(u(t)) 2 2y, for a.e. t2 0,
(40)
which in turn implies
[u(t]]22 2 ||u(O)ll2 for all t 2 0.
(41)
24

---

Published in Transactions on Machine Learning Research (06/2024)
Thus, can choose ||u(0)]2,, and T O.
Case 2: (u)))) - 0.
For this case we may further assume that (u)()) x 0, for all 2 0, since if for some 6, (u((t) > 0, then using Lemma C.4 we have [|u(t)]22 2 [[u(f)]l2, for all t 2 f. Then, since M(u(f) > implies ||u(t)]l2 2 > 0, we may choose ||(()]22 and = L.
So, let assume that (u(())) 0, for all 22 0. Then,
d u 2
u 2V(((t)) s 0, for a.e. t 2 0.
2 dt
Therefore, ||(()]l2 decreases with time, and hence, lim ||(())122 exists and ||u(()]l2 lime-soo [|(()] for all 1 2 0. Since have assumed lim,-xo u(() * 0, we have lime-se |u(()]22 0. Thus, we may choose = limy-+00 [|u(t]]l, and T = 0.
C.3 Proof of Theorem 5.1
Consider the differential inclusion
ú E ON ON-
g0 y ()) u(0) Wo.
(42)
and let u(t) be its unique solution. By Lemma 5.3 either lim, u(t) = 0 or lim, Tu(
n(t)
exists.
We first consider the case when lim u(t) 0. Here, we define 17 1 and fix an n). Then, we choose T large enough such that
Iu(0]22 S for all 1 T.
(43)
Next, if lim, (() * 0, then from Lemma
C.7 there exists > 0 and T 2 such that []x((]]22 2 27, for
all t T. Also, from Lemma 5.3
lim u(t)/||u(t|llz ú, t+0
where û is non-negative KKT point of
max N |
Nu = - (O -( u(:uu.
(44)
For fixed (0, we choose T T such that
u(t)
|utt]ll 2 e, for all t T.
(45)
Having chosen T for fixed E (0, 1)) in both cases, we next choose C' such that In(C) 433
= T. From Lemma 5.2
there exists 8 such that for any d < 8
In(C)
[w(t)l22 < VC8, for all t E
433
and
w (
u(T)
S.
(46)
5
2
Thus, we may write w
u(T) + S, where ||Sl|2 < e. If lim u(t) = 0, then, using
43
|w([]]|2 5 28c.
25

---

Published in Transactions on Machine Learning Research (06/2024)
Else, since (0, and [|u(T)ll2 2 2n, we have ||u(T) + Cll 2 n. Hence,
w(T) u(T) +
(w(T)
[T( Cl2
which implies
( u(T) {T
[ ú |l(
||u(T)ll2
w (1)l2 ||u(T) +112
|l
S12
| Cll
Now, since
|l(
1
1
[T) + Clle
| + |cl2
14
21
|
27
and
5
-c
2
||([T) C1|2
77
we have
w(T) Tá
(1- 6
2 (1 - t)
- 2 1 -
1
[T(2
2n/
21/
C.4 Proof of Corollary 5.4.1
Consider the differential inclusion
ú E ON (N) S
u), u(0) Wo-
(47)
and let u(t) be its unique solution. From separability, can write u(t) [t). (t) such that for all j E [H] we have
új E ON e1
V OHH (0) Wojs
(48)
where Wo = [Wol..... Wohl cxists.
By Lemma 5.3 for all j E [H]] either lim; uy (t) = 0 or lim [[0;(0]]
n,(t)
Let Z be the collection of all indices such that lim, uy(t) (t) = 0, for all j E Z, and 2 be the complement
of 2 [M]. For all j E 2o, from Lemma C.7 there exists f) > and T₃ 2 0 such that [|u;()]l22 2 2nj, for
all t Tj. Define 77 = min(1, minjez 14)) and T' maxjez= Tj, and fix an E (0, m).
From Lemma 5.3 for all j e 2 have
lim (4)lluu, = ūg t00
where ú, is a non-negative KKT point of
max N (u) (0, (H,())) | -1
(49)
Then, for a given e, we choose T, > such that
u (t) új e, for all t > Tı, and all z
(50)
u, (0)l2
For all j 2, we choose T2 large enough such that
[1)l2] S e; for all 1 > T2 and all j 2.
51
26

---

Published in Transactions on Machine Learning Research (06/2024)
Define T 1.. T2) and choose C' such that In(C) any 8 I 8
T. From Lemma 5.2
there exists ō such that for
433
[w(1)2 vCS, for all t 0.. In(C)]
433
and
w(T) T Sc
(52)
By separability, we may write w,(7) (T) - Sj, where 1sil12 S e. If j E 2 then, using eq. 51 we have
Iw 12 2dc.
Else, since E (0, 17), and ||u, (T) 2 2n, we have ||u (T) +ille 2 n, Hence, using similar reasoning as in the later part of the proof of Theorem 5.1 we get for all j E 2",
3 2T
e.
w (T)l
D Proofs Omitted from Section 5.2
We first prove Lemma 5.6
D.1 Proof Lemma 5.6
We note that since Wn,, W.) is a saddle point of
L (Wn, = 2
11 (X; w..
- 2
(53)
and W. 0, we have
0 1w., L Wn, 0) iw (W,, 0)
E
(54)
0
which establishes 0 E Ow,, (Wn, 0).
To prove Theorem 5.5 we first describe the approximate dynamics of (t), wt) near the saddle point in the following lemma.
Lemma D.1. Let (Wn,w.) satisfy Assumption and define y y Ho (X: wa). Let C 1 be arbitrarily large constant and (wn(t), w=({)} satisfy for 2 0
wn]] w
1ww,, L (Wn, W:) Ow: L (Wns wz)
[w.(0) (0)
Wn + + w. + 8C2
< -
=
(55)
where 82 S min((2)) te )) and 1|Gal12 = ||S=|12 Then
(w. - w.ll2 + [/w w=ll3 < 208 for all E
0. 1
1
(c)
(56)
M2
where M2 is a positive constan
Further, for the differential inclusion ú E ON H. (u), u(0) Sz:
(57)
5 My here same
Theorem 5.5 See statement. of Theorem and the the proof of Lemma D.1 more details.
27

---

Published in Transactions on Machine Learning Research (06/2024)
and for any e 0 there erists small enough 3 > 0 such that for any d < 8,
(t) u(()
0, In(C)
s; for all 1
(58)
M2
where u(t) is a certoin solution of eq. 57
Proof. We note that since (w,, 3 is a saddle point of
L (wns w.) - 2 (X; w.)) + (X; y112,
(59)
have
010
0
E
Σ F
Σ == B, (x;; w
=
D. (x); w.)
(60)
We now define
An Hn (X; Ha,X; w.); Ax(1) = (X: w=()), and Z(t) [[w,(() w (1)
Since (t,, w. (1)) is continuous curve, ((t) is also contimuous curve. Note that Z(0) = 28 S
min(1/C,, 222)) < m²). Therefore, there exists some > 0, such that Z(t) S min(1, R²), for all E 0. Let T be the smallest t > 0 such that Z(T*) = min(1, Hence, for all E [0,T"]
(() & min 7)) Our next goal to find a lower bound for T We operate T*).
Recall that
(X: S 3
(61)
Moreover, by the locally Lipschitz property of H, (X: w..,, there exists μr > 0 such that
[Ax(t))l S 11l w,. wn ll,, for all [0, T*). Define e(t) (X: w. (f)) + H. X w. (t)) y, then, using Z(t) < 1,we have
(62)
||e()]l2 |H,, X: w. (1)) + H. (X; (() - y112
$ | + | (t) + (X: (X: w. (t)) I | + #1 + 3 == M1,
where in the last inequality we used eq.
62 and cq.
Using Corollary B.1.1 we have
d w. (t)llz
27, X w.) e S 28M (t)l
(63)
dt
We first consider the case when H. (x; wx) has a locally Lipschitz gradient. Let
J(w,) =: [VH, (X,; VH,,
wn)l E Rdxn.
From eq.
600 we have
0 U. VH VHn W.) J(w.yy
(64)
By the locally Lipschitz property of VH (x; wn), we may assume that there exists μ2l > 0 such that
[J (t)) - J ( S (t)l wn
(65)
Further, since w.(t) (t) bounded for all t [0, Th,, we may assume there exists μa such that
(t))l - μ3.
(66)
28

---

Published in Transactions on Machine Learning Research (06/2024)
Thus,
d Wn w
(Wn Wn, WnnJ(wnn)e)
dt
(Wn Wn. (w,)(w,.)) (H w,, H, yy)
(Wn Ww,J(w,,)) (A. + (1) y))
(Wn, Wn, ((,)) (Wn W,, J(. J(w,) (An (1) A.))
(W,, Wn. J(n)) J(w,)y) - (w, W.. ((w)) (A, + A.))))
$ P2 Wn wn112 |,,, Wn Walle//J((w
A.. (t) + (t)l2)
$ P2 Wn - wn.12 + /1 Wn wn 11 + Busl|w, W., Wn wx11a w
& (e2 + M1 Wn wx + 8p3 |
The third equality follows from definition of (t) and (t). In last equality, we use eq. 64 incquality follows from Cauchy-Schwartz and eq.
The first
665 We get second incquality from eq. 660.cq. .g.
62 and
eq. 61]. In the final inequality, we use [!w W 2 S 1, for all [0,
Combining the above inequality with eq. 63 we obtain
1 dZ)(t) I (N2 p1 w.. (t)
w. 1 B + p3) w. w/ (t)l M₂Z(t),
2 dt
where M2 = max( 11M3, 3(M + pa)). Therefore, for all E [0, T" Z(I) S Z(0)e 4Ma implies
1
1
T 2
In
M₂
Z(0)
M2
25
Since we assume 25 < 0, we have that T 2
1 In (C). Thus, for all t E [0,
1 In (c)) Mr
M;
z(t) - CZ S 2C52
proving eq. 56
We next consider the case when Hy (X; w.) does not have a locally Lipschitz gradient. Recall that if l|w, - w,ll2 S 7, then
(wn W,, =s|ww, w. wa where s E -0w, I(Wn, 0).
(67)
Further, we may assume that there exists a constant μs > such that if [|w,, W.ll2 S y, then
max vE(n
| I Ps, where p. E OH((;;
(68)
Using the chain rule, we also have
Ow, I(Wn, wz) S Sw., (I(wn,, w:) T.(w,, 0)) + Ow. I(W,n, 0).
(69)
Note that Ow. (I(wn, w.) - I(wn: 0)) S 2 Hz(x;; wz) (x;; wa). Therefore, if [|,, -w,l22 S 7, then, using eq. 668 for any Wa: and p Ow., (L(Wn, Wx) - L(w., 0)), we have
||l|a <
H wxw.X./w))l wz)lla S HoVTBB|l.11
(70)
Next, using eq.
69 we have
1 //| w,,
wn 2
(wn Wn, W.) E -(W, Wn, Ow. L(wn, wz))
2
dt
E - (wn W.. Dw. (L(wn) We) L(Wn, 0)) Ow, L(wn, 0))
29

---

Published in Transactions on Machine Learning Research (06/2024)
Since (t) Wa I for all E [0, using eq. 67 and eq.
70 we have
1 d w w uss/nfll,, W. l K|| w. wn ll S As w k//w, wn
dt
where in the last inequality we use [[w(()) w S 1, for all 1 E [0, 7 Combining above inequality with eq. 63 we have
1 dz((t) 2 8(2 + pav (1)l2 + k||w, w..li < M2Z(1),
2 dt
where M2 == 3(2M,, + p3v n.). Therefore, for all t [0, we have that Z(t) S Z(0)e implies
1 T
In
In
M2
Z(0)
M2
28
Since we assume 28 < C we have that T
> M;
In (C). Thus, for all t E 00, Mz
In (c)]
(t) - CZ < 2C62
proving eq. (66.
We now move towards proving the sccond part. We use similar technique as in the proof of Lemma 5.2 We define E(t) = e(() y. Then,
(lE())l2 = ||5 + (X; wt + (X) - yyl2
1|H,, (X: w., (f)) H., w.) + He (X:
S M1 Wn - wx + B w (t)
S M1 5
Thus, the dynamics of (t) can be written as
W₂ E
(xH = Σ (T. Ex)
(71)
Dividing eq. 71 by and using J-homogeneity of 0H((x; w) (Corollary B.1.1 we have
n
n
0
(x;
Σ TT (x)))H, w0/
(72)
Now, consider the differential inclusion
dw
J. W.), (0) Ce. Σ
(73)
dl
Since for all (0, M, such that for all 5 < 6,
In (C)) IK(())22 & mIV08 308², using Lemma C.1 there exists small enough 0
(t) wz(1) <c,
where w(f) solution of eq.
30

---

Published in Transactions on Machine Learning Research (06/2024)
D.2 Proof of Theorem 5.5
Consider the differential inclusion
ú E Σ
D,OH, u), u(0) = S2:
(74)
and let u(t) be unique solution. By Lemma 5.3 either lim u(t) or lim [u( exists.
u(f)
We first consider the case when lim u(t) = O. Here, we define 1 and fix an E (0, m)) Then, we
choose T large enough such that
||u())l2 S e, V.
(75)
We next consider the case when limy- (t) * 0. Then, from Lemma C.7 there exists 1 > and T 2 0 such that [|u(t)]l2 2 2n,, for all t 2 T. Also, from Lemma 5.3
lim (()/llu((lll = ú, 10000
where ú is non-negative KKT point of
max H. u)) y, such that ||ul|
(76)
For fixed (0, choose T> T such that
u(t) T
2 e, for all 2 T.
(77)
[ut)]l2
Having chosen T for fixed E (0, 1) in both cases, next choose C such that In(C) M2
T. From Lemma D.1
there exists 3 such that for any <<>
0, In(C)
w.((t) Wn 12 ([W w. 12 s 2C82, for all
M2
and
w (T)
u(T)
c.
(78)
5
2
Thus, we may write (.(T) uTT) + S, where ||<||2 S If lim u(t) = 0, then, using eq.
75
|T) 28c.
Else, since e E (0,7), and ||u 2 2n, we have |lu(T) + <l|2 2 m. Hence,
w u +
| (T)
||u(T) Cll2
which implics
W ( Tú
u(T) C
[u
C
+
(T) [Tu(T) Cl|2
[[]
[T((T) + C1|2
|u(T) + C||2
Since
[ll
|
1
e
>
1
[u(T) + <|12
||u[T)
15
21
(T)a
27
and
T à
[ + Sll2
77
have that
w= (T) Tú
2 (1 - <) (1 11-
e
(1+
2
1
6.
w. (2)
2n
2n
31

---

Published in Transactions on Machine Learning Research (06/2024)
3.0
2.5
2,0
Lows
1.5
Distance of weights from subdle polat:
2000
1.0
1200
0.5
3300
3.0
10000
20000
40000
30000
No. iterations
Rin Aineanion)
(a)
(b)
Figure 4: Panel (a): the evolution of training loss and the fz-distance of the weights from the saddle point with iterations. Panel (b): The lower part shows the evolution of (t) for the last 10 hidden neurons. The top plot shows the constrained NCF (0) Ei= max(0, [cos(O), sin)()))))(()) sin (x)) where y is the residual error at the saddle point. We see that the weights remain near the saddle point and loss barely changes, though the weights of the last 10 neurons converge in direction to the KKT points of the constrained NCF.
D.3 Numerical Experiments
We experimentally show the phenomenon of directional convergence among the weights small magnitude near saddle points. For this, we again consider the example depicted in Figure [ Recall, the network
architecture is defined as 22 )_ Σ max(0, U, + u2 and there are 50 unit norm inputs with corresponding labels generated using the function H (21, x2) 5 max(0, 21) + mmax(0,-2))
We consider the following saddle point (ū,,... ú20), where u, [V1/2, 0). if S 10, and u; = [0. Oj. if
> 10. Now, {u..-.. ] is a saddle point since if æ1 2 0, then H(z1, 02; {ū. 1 = m0x(0, x1)) H" (21, 22), and œ1 < O, then Vu, H(x1, x2: (u, 122)) = 0, for all < 10. Moreover, Vu, H(x1, F2j {u, 1,10) = 0, for all i 10.
We initialize the weights by adding an i.id. Gaussian vector of standard deviation 10-5 to { { úg0 We use square loss and optimize using gradient descent for 50000 iterations with step-size 5 10 We plot the evolution of the overall loss and the l distance of the network weights from the saddle point with iterations in Figure 4a and Figure 4b contains the evolution of the angle the weight vectors of the last 10 hidden neurons (they have small magnitude at initialization) make with the positive horizontal axis with iterations and the constrained NCF defined with respect to the residual error at the saddle point. It is evident that the training loss barely changes, and the weights remains close the saddle point. Morcover, the individual weight vectors for the neurons with small magnitude converge to the the KKT point of the constrained NCF. We note that. the constrained NCF seems to have set of flat KKT points, and therefore, if the weights are initialized in that set, then they remain there seen in Figure 4b
E Gradient Flow Dynamics of f(u1, u2) = un /u2
In the following lemma, we describe the gradient flow solutions of f(11, = un |uz] when initialized at [1,0].
Lemma E.1. For any T > 0, consider the following time-varying function
0 for all E [0,
(t) u2r (t)
ur(
(79)
coos (t T) sinh (t T)
for all t T,
32

---

Published in Transactions on Machine Learning Research (06/2024)
then, for a.e. t 220 0, (t)(t) satisfies
ui
Bu, (11, u2) Sug (u1, u2)
[22
Iu [0)
1 0
i/2
E
u1 U2
u2
=
(80)
where
[- 1, [], if u2 = 0
0 u2l E
1, u2 > 0,
1, if 122
Proof. For & E (O, (t) is constant, hence,
0
0
Since uIT(() = 1 and u2r(() = O, for all / E [0, T), we have
(ugr (t) uir (1)0 = [-1,
3
0
For T, (tr(t) and (t) are continuous and differentiable functions, thus,
ùrr
sinh(t T) cosh(t T)
ü27
Since Ugr > 0, hence, for all t > T, we have
Juer (t) UIT (t)0)
sinh it T) cosh(t - T)
completing the proof.
The above lemma shows that for any T > ur (4) defined in eq- 79 is gradient flow solution of [w,, u2) when initialized [1,0]T, For any finite T', it is easy to see that lim (r(t)/|lur(t)ll 11/V2,1/V2] Hence, for a fixed T and any e > 0, we can choose such that
(T(T)
[1/22 1/V2
2
|
In the next lemma, we show that except for the set {uz = 0, u1 > 0}, all points are non-branching for gradient flow dynamics of (u,, U2) = un [ull
Lemma E.2. Let [2] E IR2 (u2 = 0, un > 0}, then the differential inclusion
i1 #2
1u, S(1, uz)
|uz|
[u [0)] (2( 22
21
E
(81)
Bug [u1, U2)
und
has unique solution, where
[- 1, 1], if u2 = 0
2 uzl E
1, of U2 > 0,
1, if U2
Proof. We first note that
ربfj = u22
which implies
d (uf(t) - (t) =
dt
33

---

Published in Transactions on Machine Learning Research (06/2024)
Hence,
n²(1)= (1))) = 2/.
(82)
Now, we prove the lemma by considering different cases.
Case 1: |22| |=i]. From eq. (82) we have vi( x²()) - - z5. Thus, rτ(() (1) x.. Now, since
|22| > |21,, we get that uz(t) 0, Vt O. Since uz stays away from the set {uz = 0}, o., (ui((t)))))))) u2()))
and 0uz (t), (t)) are always unique and hence, (w1 (t), u2() is unique.
Case 2: |z2l < | 22 + 0, > 0. In this case, since 222 > 0, we have 21 = | > 0. Now, since
((, ut)) = [22(t) 2 and 21 > 0, therefore, u1(t) 2 21 > 0, Vt 2 0. Now,
(w²) 2uzú2 2/ug uu
Since (t) > Vt 2 O, we get ut(()= 2 22(0) 23 > 0, V O. Hence, uy(t) stays away from the set fuz = 0}, which implies 0u, (uz(() u2(()) and 0ng (wn (z)) are always unique and thus,[u (4), u2()) is unique.
Before proceeding to the next cases, we first show that the set S = {u2 0, u1 S 50} is stable critical point, that is, if [u1 (f), u2())} E S, for some time 2 0, then, [n1 (f), uz(t)] = [2) u2(()) Vt 2
Proving [0.0] is a stable critical point is trivial since 0x, f(0,0) 0) = 0= = On, fu1,
Now, suppose (i), u2)) = [ār, dz], where ân < and û2 0. Then, f(1,, ú2) = 0, and since gradient flow can not decrease the objective value, we have f(u (t), uz())) 2 0, for all t 2 f. Also, since for any ūn 0 and ū2 # 0, we have f(1,, ū2) < O, therefore, gradient flow can only move along the u2 0 axis, i.e., only (I) can change. However, since on, [(11, 0g) 0gg 0, u1(() can not change for L 2 [. Hence, [ui (t), un (t)] = (Q),), u2))), for all 1 12T. F.
82). we have (t) u²(() = =f - Thus, uf(() = v3(t) + o 22. Now, since |21| > |22], we get that (t(t) > 0, 2 0. Now, since u1(0) = 21 < 0, therefore, 21 < O, VI 2 Hence, (2) is O for the first time at some i 2 O, then from the stability of the set S, we have < t I, since u2(t) + 0, fu, u2(()) and Inz (t), u2))
Case 3: |22| < |2r|.21 21 < 0. From eq.
(ui (t), (t)] = (f), (t), Vt 2 E. For 0
are always unique and hence, [u (t), uz(()] is unique.
Case 3: |22| = =121, S.O. O. From eq. 82 we have [ur = |m2(t)]- Now, since un (0) = S 0, therefore, if (F) is 0 for the first time at some t 2 O, then u2( is also 0 for the first time at E. Then, from the stability of [0, 0), we have [un (4), u2)) = [0, oj. AL 2 L. For 0 S < I, since uz(() # O, On, [mm (1)((), u2()) and
(un (t)) are always unique and hence, [u1 (t), u2 (f) is unique.
F Proof of Lemma 5.4
Since {u., } is KKT point of
N Nan(u, u) = uz 7x u).
max m
therefore, for some À E IR, we have
0 Nw ZT (X Ju),
(83)
0 Au, + U. Σ o' [xc u. 1 1=1
(84)
where d'() is the subdifferential of a-)). Also, since x,_ u. * 0, a'xx u.) is unique for all i E [m]]
Now, we may further assume that mingeta) |x] u, 1/ and max ||x;|12 = 72, for some 71, 1/2 > 0. Choose
7 = / (2m)): and recall S = (u, u: sign(v.)u > ||u]|2| ||u -u--u u,llz 5.). Note that since u.2" T o u.) > 0, therefore, |u-| + 0 and (1.) E [1,,1). Also, multiplying eq. 183 by us and using u. o [X u.) > 0, we get that X < 0.
34

---

Published in Transactions on Machine Learning Research (06/2024)
Now, the gradient flow equation is
2 oxX u
[v(0]]
p 9
i
E
11
o'(x 1 2,2x
[0(0]
where {p, q} E S. We first note that
dt (v²
1P211uu133 200 -2m Ju 0,
which implies
(t) |lu(0)1 p² 119112.
(85)
Since sign(u.)p ||q||, we get sign(p) sign u.) and thus [p] ||q/22 Therefore, from the above equation, we get (1) ||u(()] > 0, which implies v² > 0. Since (1) is continuous and never becomes 0, we have sign(v(t)) = sign(v(0)) = sign(p) = sign(v.).
To prove uniqueness, we will show that x u(t) * O, for all E [n] and 2 Note that, since ||u, - 9ll2 S Y we may assume q = u, eb, where [lbll2 = and |e| S 7. Thus,
x (() |x] q
|x] TxTTn u.l
||| bJ 2 m 72 /2.
which implics x. (0) * 0, for all i E [n]. For the sake of contradiction, suppose there exists some f >
such that x ((]) = O, for some E [n]], for the first time. Then, for all i E [0, we have x u(l) A 0, for all E [n]- Furthermore, due to continuity of u(t), we have, for all i e [n],
sign(x, u()) sign(x} u(0)), Vt E (0,
Now, note that
x u. ((0)) x, u. u. + Ex. u b
2 xx] u. [c]]x]]]llll b)
= xx] u. [(| u.l- bl) 2 12/2.
Thus, for all i E [m],
sign(x; u(t)) = (x] u(O)) = sign u.), E (0,0),
which implies
u(t) (() + I v(t) Σ
o' (x, T ((()))xxx,dt
i=1
= =u(0) + (L/ u(t)dt
(x: u, )2xx
u(0) + (% u(t)/endt
(fo u(t)/undt u.
= uu()) -> Σ o' (x: u. )
where in the last equality we used eq. Thus, we can write
84 Now, recall that À < O and sign(v(1)) sign(vs), for all t 62 0.
u(f) = u(0) - au.,
for some ā > O. This implies that, for all i [n]],
xx_ u.x, u(() xT_,xx, u.,] u(() a u.12 2 12/2+ 15++a) an 0,
which contradicts xT (Tu( 0, for some i [n].
35

---

Published in Transactions on Machine Learning Research (06/2024)
G KKT Points of NCF: Some Examples
In this section provide some examples where KKT points of the NCF can be computed analytically.
G.1 Symmetric Data and Squared ReLU
Let be even, and suppose the training set is the union of {x,, M and {-x,, - such that n/2 x ll * 0. Let the neural network H(x; u) = o(x T u), where o(x) = max(æ, max(x,az)} for some a R. Then, for square or logistic loss, the constrained NCF
max Σ Yi (o(x) u) o( o(-x; u))
Now, since (ax) -o(=)) = (1+ )²) the constrained NCF can be writlen as
n/2
(1 + u
Σ
MEXiX]
max u
It is well known that KKT points of the above problem will be the eigenvectors of the matrix Ene yxx,x.
G.2 Symmetric Data and 2-layer ReLU
This example is inspired from Lyu et al. {x,, 81 n2/2 and { {-x,, M //? such that Σ where (x)) = max(æ, ox), for some R
2021
Let n be even, and suppose the training set is the union of y,x, lla * O. Let the neural network H(x; u) vo u), Then, for square or logistic loss, the constrained NCF is
n/2
uye (o(x) u) a o(-x]u)).
max
Now, since (xx -o(x)) (1 + aa)ar, the constrained NCF can be written
n/2
max 1
(1 + a)v
Σ
y:x;
u.
Let q Em/? yix; Now, (v,, u.} KKT point of the above problem if there exists such that
Xo + q u. = 0,
(86)
u, + -.q O, of + | = 1.
(87)
(88)
Now, if we choose A, 0, then and ú satisfies the KKT equation, where ú is any vector such
that á q 0 and | 1.
Next, if we choose A, + 0, then v, + 0. Because, if v. 0, then, from eq. 187 we get ||u 1|2 = 0, which
leads to violation of eq. 88 Since v. * O, we have u. -v../2.q Putting this in eq. 166) we get X2 |/q/2. From eq. we gave
1 1= 2f + |u. = v² + 2
which implies v2 1/v2. Hence, (+1/V2, / (V2(g(122) is another set of KKT points.
36

---

Published in Transactions on Machine Learning Research (06/2024)
H Directional Convergence for 2-layer (Leaky) ReLU Neural Network
Suppose (α)) max ax) is the Leaky ReLU activation for some R and H(x; {ux, ux)
Ex=1 (x up) the 2-layer Leaky ReLU neural network with hidden neurons. Now, since H is separable, from Corollary 5.4.1 for all E [H], in the initial stages of training {uk, ug} will cither be
approximately 0 converge in direction a non-negative KKT point of
max uy ox("))
(89)
+++||||
where for the sake simplicity we have assumed the loss function to be either square or logistic. The following lemma shods more light into the KKT points of the above optimization problem.
o(Xu..) u.) # 0. Then Lemma H.1. Suppose (v., J is a non-zero KKT point of eq. 89 that is, v.y o(X Jull = ||uulll = 1/v2, and /2u, a KKT point of
max y JT (XX u). | =1
(90)
Using the above lemma get that if {uk, u converges in direction to non-zero KKT point of eq. 189 then uy will have converged in direction to a KKT point of eq. (90). This is precisely the result stated in Maennel et al. (2018). We also note that the result. in Maennel et al. (2018) were derived under the balanced initialization assumption, where ||u = |ow holds at initialization and remains such throughout training. However, our results hold for more general initializations as well.
H.1 Proof of Lemma H.1
Proof. Since {u,, 3 is KKT point of eq.
89 we have
0 = λa + o u.) (X
0 Au, u. Xdiag(o' (X u.))y,
(91)
where d'(+) is the subdifferential of a-)) and is applied elementwise. Also, for a vector z, diag(z) denotes a diagonal matrix constructed using entries from z. Upon multiplying the lop and bottom equation by v. and u respectively we get
0 2aal/2 + +uay' oXX u.)
A||u. u. Xdiag(o' (X u.))y = Al/ua v.y o( uu).
where we used o' d'(x)= (x)) Now, since v.y (X u.) # 0, by adding the two equations and using
|v.12 + ||u.ll = 1, we get 0. Since X + 0, from the above equation also get |u.12 = ||u.l3 Combining
this with the fact that 10.12 2 ||u, 1, have |u, = | 22 1/v2.
Furthermore, since A + 0, from
91 we get
u. (ds/A)Xdiag(od (X_))))))))))
which implies V2u" is a KKT point of eq. 190h_
Gradient Flow Dynamics of g(u) = (uy /22 - 1)2
We first describe the gradient field of g(u) = (uy Nuz 1)2 near [1, 0)T
Lemma I.1. Let = [1,0]", then, e @u) Further, for any 8 e (0, 0.1,, let ud [1+ 8, Then, for any -ōg(n²), ||s||a 2 1.
37

---

Published in Transactions on Machine Learning Research (06/2024)
Proof. Since
Ou, Gungiu u2)) Ougg(ur u2) =
2 21z 1)
221 2 u2 (ur/21) - 1)]
it is easy to show 0 E Ög(ū). Next,
Oun Oun)(u²) gung(u))
- 26(1 - 6(1 - -2 - +(1+))))
=
and so for any s E -0g(u") we have that
||||| 2 2(1 + 5)(1 - =))01(((++ 2 2 2 1.1) 2 1.
The lemma above establishes that there exist points in any arbitrarily small neighborhood of the saddle point i where the gradient of g(u) has large norm.
In the next lemma we describe the gradient flow dynamics of g(u) (wa u2l 1)2 near [1, 0]", and show that gradient flow will escape from any arbitrarily small neighborhood of the saddle point in constant. time. Lemma I.2. Let ú = [1,0]², and (t) be a solution of the differential inclusion
ù1
E - [u. u2)
[0]
= 1+0
(92)
W2 Ou.g(u1, u2) u2(
Then, for any E (0, 0.1, Ius (0.1) u|12 2 0.09.
We show that no matter how close the initialization is to the saddle point ü, the gradient flow will escape from it within constant time. Here, []))(0) x|ا2 I v2š where ó can be arbitrarily small and positive. However, (0.1) u|l2 2 0.09, thus, us(() escapes from the neighborhood of û within constant time for any arbitrarily small 6.
Proof. Choose 8 E (0.0.1) and let =
= {(u1, (2) 01 E [0.8, v2 E (6/2,0.35]]. Note that for any u E S
we have
6/2 < 6(1 - 1.201-112-000000 0.35) < 2 21 U2l - 1) < 2 0.35 (1 -1- 0.8 - and
(93)
0.9 2 2 0.8(1 1.2--.30 S 2u (ny U22 - 1) s 1.2 (1 0.8 - 2.4.
(94)
Let (t) be solution of eq. (92). For the sake of brevity, we use u(t) instead of uz).). Note that u(0) e S. Let T' be the smallest t 2 such that u(T') S. For all t [0, TT, uz(() O, thus, u(t) satisfies
[ -22 (u u22 1)] 22 (u) /ua| - 1)
for all t [0,T].
(95)
From eq.
93 and eq. 94h. for any i E [0, T), we have
ú1 E [8/2, 1]. and d E 2.49.
(96)
Using these bounds, we next show that T > 0.1. Assume for the sake of contradiction, T S 0.1. Then, from eq. (66). for any t e [], we have
0.8 < an (0) S un (0) + 61/2 < (1()) < un (0) < 1.2, and 8/2 < (0) < (0) 0.94 5 (1) < u2 2.4 5 + < 0.34
From the above equation, we observe that u(T) E S, which leads to a contradiction. Thus, T > 0.1. Hence, using the lower bound on ti in eq. 966, we have
u0.1 2 u2 (0) 0.9 0.1 > 0.09.
Thus,
[u(0.1) a/I2 > l2 (0.1) > 0.09.
38

---

Published in Transactions on Machine Learning Research (06/2024)
J Proof of Lemma C
We prove Lemma C.1 in similar way as in Filippov 1988), though that proof considers more general case. For our problem, the proof can be slightly shortened.
To prove Lemma we make use the following lemma
Lemma J.1. Filippor 1988, Lemma 13, Section 5) Let for all E [a, b] the vector-valued function X (t)
absolutely continuous, (t) + x(t) as k + oo, and for each k 1,2.... the functions Sx(t) E M
(a.b) with M being bounded closed set. Then the vector-valued function x(t) is absolutely continuous and x()) cono(() almost everyohere t (a,
almost everywhere
Proof of Lemma C.7. For the sake of contradiction, assume that the statement in Lemma C.1 is not true. Thus, for some there exists a sequence of solutions ut(t) of
du dt
E
Σ (=c + ((0))H((xx))) u(0) = up, = 1,2,...,
(97)
where (f(( S 8,. for all i [n] and j 2 and d3 0, such that for any solution û(t) of
dü
E
2 0H((x ū), ū(0) = uo.
(98)
dt
we have
max [1,(1) (n(()))(())l22> E 0,
(99)
We also assume that oj S B/V for some positive constant B and for all j 2 1. We first show that {u)(t)} has convergent subsequence. Note that for any e [0, T), (t) is bounded since
1 2 dt
(a. + (()))((x;))) s 43 1 12 + B),
which implies
[1,,(0)) < |
< | | = B².
(13
We next define
: = supfl w)ll2: w E Sk-1].
We note that {t)) is equicontinoous, since for any to [0, and j 2 1,
[lu{(4) - u,,()))l
Es + (x))))
<
1( + (+)) 12ds
i=1
< 12 t BI + B).
Therefore, using the Arzelà-Asee Theorem, there exists subsequence (u,, (1) that converges uniformly. We denote the limiting function by â(t). We complete proof by showing û(t) is solution of eq. 988 since that will lead to contradiction.
For any vector u, we define F(u) = Ei= =0H(xx;u). For any y > 0, the y neighborhood of F(u), denoted by (u), is defined as
M (u) {v : v h q, h F(u), || 5
It is easy to show that for any finite 7, Fx (u) nonempty, convex, and compact set. Also, we define
= {u: u x|از m) = (t f s
39

---

Published in Transactions on Machine Learning Research (06/2024)
Choose any f [0, T) Since, F(u) is upper semicontinuous, for any Y O, there exist small enough r 0 such that for all E (!))), F(u) _ (F)()()). Further, since it()) is continuous, there exists small enough a such that, for all E 8 â(t) E (t).. Hence, for any > 0, there exist a small enough a > 0, such that for all t E 8", F(ū(t)) _ ()()()).
Next, since (1) converges uniformly to û(t), we can choose k large enough such that | (1) ú(t)ll2 S g. for all L and & 8a, Since û(t) continuous, there exist 0, such that (a(t)-ú(f)) S 2 for all t E 88. Thus, for all E 8 ng and h k1,
| (1) - a(0) l2 S (1) - 0(1)l2 + (Iū(() - a())l2 S n
Henco, Fl (t)) C (ú(f)), for all E la 8 and kj-
Also, since 6ju- + O, we can choose l/2 large enough, such that on S nBix for all k > k2. Thus, EE= (t)0H(( un (t))ll2 S nBixOj S 7, for all & l2. Therefore, for all z max [2) and E 1" ni.
(1) E + (10H((x),(0)))) (1) E (a)()())),
for a.e. LE i n
From Lemma. J.1 ú(t) is absolutely continuous in 8a n 1 and
a(t)= E 222 (ū((), for a.e. t n8.
We can cover the interval [0, by varying Therefore, û(t) is absolutely continuous in the interval [o, T] and û(t) exist almost everywhere. Also, if for any & E [0, T), û(t) exists then û(() E (f)(())), where y can made arbitrarily small. Hence,
a(t) E F(ū(t)), for a.c. E [O.T].
40


Reviews:
[{"review_id": "XOJdIAwWN0", "reviewer": "Reviewer_GZga", "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": "Strengths\n* The problem formalizes and proves the observations of Maennel et al 2018. \n* The analysis seems clean and without issues (though I did not check the details carefully). \n* Local analysis of gradient flow is relevant as describing the full gradient flow trajectory is very difficult (if not impossible) for generic data even for the simple case of a shallow network with ReLU activation. \n\nWeaknesses\n* Writing feels technical but it is clear \n* Experiments showing escape behavior near the saddles would be valuable", "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 the directional convergence of two homogenous networks initialized with small weights. In particular, the authors prove that the weight vectors move towards maximizing directions of the neural correlation function defined on the sphere while their norm remains small. The time to exit this small norm phase is also given. A similar analysis is done to study escape behavior near other saddles far from the origin.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Question: Can the authors comment on why it is not possible to show the saddle escape behavior for logistic loss although this was possible for the saddle point at the origin?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UG2ke1OPjH", "reviewer": "Reviewer_ziAa", "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": "- Strength. The initial directional convergence phenomenon has been widely observed. However, most previous theoretical works are limited to specific dataset. In this paper, the authors establish a clean theorem to characterize this phenomenon  for general dataset. They prove that the net converges to the KKT directions of some constrained optimization problem.\n\n\n - Weaknesses. Please refer to Requested Changes.", "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 studied the directional convergence of gradient flow near small initialization.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The result in the main theorem does not seem intuitive. Previous works can ``calculate'' the convergent directions for some specific dataset, such as $\\frac{1}{n}\\sum_{i=1}^n y_i x_i$. Could the authors provide some specific examples and calculate the specific expression of the KKT directions of $\\max_{||w||\\_2=1} z^\\top H(X; w)$ in the main theorem? I think it can great help the readers understand this theorem.\n\n2. The KKT directions may be not unique. Is it hopeful to provide a fine-grained characterization about the uniqueness of the convergent direction (under some stricter conditions)?\n\n3. Some other related works. [1] about theoretical analysis of initial condensation; [2][3] about the entire training dynamics.\n\n[1] Chen et al. Phase diagram of initial condensation for two-layer neural networks. (CSIAM Transactions on Applied Mathematics )\n\n[2] Wang and Ma. Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networks. (NeurIPS 2022)\n\n[3] Safran et al. On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias. (NeurIPS 2022)", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jvb8hvrbFL", "reviewer": "Reviewer_wmhE", "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": "Strengths:\n- Understanding the training dynamics of neural networks is an important task. Our current understanding is still far from complete even for the simpler cases of two-layered networks. The paper furthers our understanding of these networks and I feel like it can be a valuable addition to the literature.\n\n- While I did not check all mathematical derivations carefully, the presented outline makes sense and the analysis seems to be non-trivial. The idea that the training dynamics can be coupled with the gradient flow of the correlation function is particularly nice.\n\nWeakness:\n- The paper makes some non-trivial assumptions both concerning the network and the dynamics. I feel like those assumptions can severely limit the applicability of the results. I expand on this point below.", "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 explores the training dynamics of shallow neural networks with homogeneous activations.\nThe main result shows that when the networks' weights are initialized with a sufficiently small norm, the weights stay small for some predetermined time and their direction converges. Moreover, the possible directional limits are also characterized in terms of the KKT points of maximizing the networks' output with the sample's labels.\nThe authors also establish a similar result when the weights are initialized at a certain type of saddle-points, rather than close to the origin.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As I noted above my biggest concern is about the assumptions the authors impose in the paper. I feel like an in-depth discussion about the interplay of the different assumptions, and the main limitations could greatly help evaluate the contribution. I list below several specific questions:\n\n- Requiring that the network is 2-homogeneous is a very restrictive assumption. Unless I'm missing a specific example, realistically, it only captures 2-layered ReLU networks (the other examples in the paper are a bit artificial). Since 2-layered ReLU networks already form an important class of examples, I do not hold this restriction against the paper too much, but I do feel like something should be discussed in the paper. Why is this assumption important for the analysis? What happens if the degree of homogeneity is changed (for example 1- or 3-homogeneous)? Do you expect a similar result to hold without this assumption?\n\n- The second assumption I find troubling is that of having non-branching solutions. I completely understand why this assumption is necessary for the analysis and I can also see why it is automatically satisfied in some cases. However, I don't see a reason why it will be satisfied in general. In particular, given the limitation imposed by having a 2-homogeneous network, is there any reason to expect non-branching for ReLU networks? The authors honestly raise this limitation in the main body of the text, but I would be happy to hear/read more details. Essentially, at the moment I am not sure whether the result holds for ReLU networks or not. \n\n- I would also be happy to hear the authors' opinion concerning Assumption 2 in the same context as my previous question.\n\n\nMinor comments:\n- In the Single-layer squared ReLU networks example, the authors could also allow for arbitrary signs for each neuron, making this example slightly more general and relevant.\n\n- Page 4, Line -12: \"... Each S_n is *a* set...\"", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cxW8T9uw0Y", "reviewer": "Reviewer_zNgm", "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": "Strength:\n1. This paper is mostly well-written. The theoretical results are clear and sound (proofs are checked, albeit not very carefully, and they make sense). \n2. The analyses are rigorous. A critical assumption \"initialization is non-branching\" (the resulting solution to the differential inclusion is unique) is carefully explained, and the authors provide a great example to justify this assumption.\n3. The provided results are general. Prior analyses on directional convergence with small initialization mostly studied two-layer ReLU networks and this work studies almost any 2-homogeneous neural networks. \n\nWeakness:\n1. Some definitions are not properly defined in the main paper, for example, \"non-negative KKT points\". \n2. The directional convergence discussed here is not exactly the one shown in other works (Maennel et al., 2018; Boursier et al., 2022;  Wang & Ma, 2023; Min et al., 2024;). This paper studies the directional convergence of all parameters, while the others study, for two-layer ReLU nets, the directional convergence of first-layer weights (via balancedness assumption). Such difference needs to be pointed out and the authors are recommended to draw connections between these two types of directional convergence.", "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 a directional convergence in training 2-homogeneous neural networks with small initialization. It is shown that weight parameters, when initialized sufficiently close to the origin, converge in direction to a KKT point of some neural correlation function. Then the analyses are extended to certain cases where the network weights are initialized around some saddle points.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical changes: Please see \"Weakness\"\n\nThe authors are also recommended to implement the following change:\n1. The neural correlation function can be easily motivated by taking the 1-st order Taylor expansion of the loss function around \\hat{y}\\_i=0 (this is shown in the proof), which leads to a first-order term $\\sum_{i=1}^n \\nabla_1\\ell(0,y_i) \\mathcal{H}_i$, exactly the neural correlation function by noticing that  $\\nabla_1\\ell(0,y_i)=-y_i$. Such simple derivations in the main paper would help with understanding the NC function. Moreover, based on this derivation, I think the $\\ell$ can potentially be any loss function with Lipschtz gradient w.r.t. first term around zero, besides the $l_2$ and logistic loss discussed in the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the directional convergence in training 2-homogeneous neural networks with small initialization. It demonstrates that when weight parameters are initialized sufficiently close to the origin, they converge directionally to a KKT point of a specific neural correlation function. The analysis is further extended to scenarios where the network weights are initialized near certain saddle points.

This is a very solid theoretical work. While the analysis of directional convergence with small initialization is not new, this work extends previous analysis from 2-layer ReLU networks to almost any 2-homogeneous neural network. All the reviewers acknowledge the paper's contribution and believe the findings will interest the deep learning theory community. I agree with the reviewers and recommend acceptance.
Decision: Accept (poster)