Year: 2021

Abstract:
We study non-convex subgradient flows for training two-layer ReLU neural networks from a convex geometry and duality perspective. We characterize the implicit bias of unregularized non-convex gradient flow as convex regularization of an equivalent convex model. We then show that the limit points of non-convex subgradient flows can be identified via primal-dual correspondence in this convex optimization problem. Moreover, we derive a sufficient condition on the dual variables which ensures that the stationary points of the non-convex objective are the KKT points of the convex objective, thus proving convergence of non-convex gradient flows to the global optimum. For a class of regular training data distributions such as orthogonal separable data, we show that this sufficient condition holds. Therefore, non-convex gradient flows in fact converge to optimal solutions of a convex optimization problem. We present numerical results verifying the predictions of our theory for non-convex subgradient descent.

heading: 1 INTRODUCTION
text: Neural networks (NNs) exhibit remarkable empirical performance in various machine learning tasks. However, a full characterization of the optimization and generalization properties of NNs is far from complete. Non-linear operations inherent to the structure of NNs, over-parameterization and the associated highly nonconvex training problem makes their theoretical analysis quite challenging.
In over-parameterized models such as NNs, one natural question arises: Which particular solution does gradient descent/gradient flow find in unregularized NN training problems? Suppose that X ∈ RN×d is the training data matrix and y ∈ {1,−1}N is the label vector. For linear classification problems such as logistic regression, it is known that gradient descent (GD) exhibits implicit regularization properties, see, e.g., (Soudry et al., 2018; Gunasekar et al., 2018). To be precise, under certain assumptions, GD converges to the following solution which maximizes the margin:
arg min w∈Rd
1 2 ‖w‖22, s.t. ynwTxn ≥ 1, n ∈ [N ]. (1)
Here we denote [N ] = {1, . . . , N}. Recently, there are several results on the implicit regularization of the (stochastic) gradient descent method for NNs. In (Lyu & Li, 2019), for the multi-layer homogeneous network with exponential or cross-entropy loss, with separable training data, it is shown that the gradient flow (GF) and GD finds a stationary point of the following non-convex max-margin problem:
arg min θ
1 2 ‖θ‖22, s.t. ynf(θ; xn) ≥ 1, n ∈ [N ], (2)
where f(θ; x) represents the output of the neural network with parameter θ given input x. In (Phuong & Lampert, 2021), by further assuming the orthogonal separability of the training data, it is shown that all neurons converge to one of the two max-margin classifiers. One corresponds to the data with positive labels, while the other corresponds to the data with negative labels.
However, as the max-margin problem of the neural network (2) is a non-convex optimization problem, the existing results only guarantee that it is a stationary point of (2), which can be a local minimizer or even a saddle point. In other words, the global optimality is not guaranteed.
In a different line of work (Pilanci & Ergen, 2020; Ergen & Pilanci, 2020b;a), exact convex optimization formulations of two and three-layer ReLU NNs are developed, which have global optimality guarantees in polynomial-time when the data has a polynomial number of hyperplane arrangements, e.g., in any fixed dimension or with convolutional networks of fixed filter size.
In this work, we first derive an equivalent convex program corresponding to the maximal margin problem (2). We then consider non-convex subgradient flow for unregularized logistic loss. We show that the limit points of non-convex subgradient flow can be identified via primal-dual correspondence in the convex optimization problem. We then present a sufficient condition on the dual variable to ensure that all stationary points of the non-convex max-margin problem are KKT points of the convex max-margin problem. For certain regular datasets including orthogonal separable data, we show that this sufficient condition on the dual variable holds, thus implies the convergence of gradient flow on the unregularized problem to the global optimum of the non-convex maximalo margin problem (2). Consequently, this enables us to fully characterize the implicit regularization of unregularized gradient flow or gradient descent as convex regularization applied to a convex model.

heading: 1.1 RELATED WORK
text: There are several works studying the property of two-layer ReLU networks trained by gradient descent/gradient flow dynamics. The following papers study the gradient descent like dynamics in training two-layer ReLU networks for regression problems. Ma et al. (2020) show that for two-layer ReLU networks, only a group of a few activated neurons dominate the dynamics of gradient descent. In (Mei et al., 2018), the limiting dynamics of stochastic gradient descent (SGD) is captured by the distributional dynamics from a mean-field perspective and they utlize this to prove a general convergence result for noisy SGD. Li et al. (2020) focus on the case where the weights of the second layer are non-negative and they show that the over-parameterized neural network can learn the ground-truth network in polynomial time with polynomial samples. In (Zhou et al., 2021), it is shown that mildly over-parameterized student network can learn the teacher network and all student neurons converge to one of the teacher neurons.
Beyond (Lyu & Li, 2019) and (Phuong & Lampert, 2021), the following papers study the classification problems. In (Chizat & Bach, 2018), under certain assumptions on the training problem, with overparameterized model, the gradient flow can converge to the global optimum of the training problem. For linear separable data, utilizing the hinge loss for classification, Wang et al. (2019) introduce a perturbed stochastic gradient method and show that it can attain the global optimum of the training problem. Similarly, for linear separable data, Yang et al. (2021) introduce a modified loss based on the hinge loss to enable (stochastic) gradient descent find the global minimum of the training problem, which is also globally optimal for the training problem with the hinge loss.

heading: 1.2 PROBLEM SETTING
text: We focus on two-layer neural networks with ReLU activation, i.e.,
f(θ,X) = (XW1)+w2, (3)
where W1 ∈ Rd×m, w2 ∈ Rm and θ = (W1,w2) represents the parameter. Due to the ReLU activation, this neural network is homogeneous, i.e., for any scalar c > 0, we have f(cθ; X) = c2f(θ; X). The training problem is given by
min θ N∑ n=1 `(ynf(θ; xn)), (4)
where `(q) : R → R+ is the loss function. We focus on the logistic, i.e, cross-entropy loss, i.e., `(q) = log(1 + exp(−q)). Then, we briefly review gradient descent and gradient flow. The gradient descent takes the update rule
θ(t+ 1) = θ(t)− η(t)g(t), where g(t) ∈ ∂◦L(θ(t)) and ∂◦ represents the Clarke’s subdifferential. The gradient flow can be viewed as the gradient descent with infinitesimal step size. The trajectory of the parameter θ during training is an arc θ : [0,+∞)→ Θ, where Θ = {θ = (W1,w2)|W1 ∈
Rd×m,W2 ∈ Rm}. More precisely, the gradient flow is given by the differential inclusion d
dt θ(t) ∈ −∂◦L(θ(t)),
for t ≥ 0, a.e..

heading: 2 MAIN RESULTS
text: In this section, we present our main results and defer the detailed analysis to the following sections. Consider the more general multi-class version of the problem withK classes. Suppose that ȳ ∈ [K]N is the label vector. Let Y = (yn,k)n∈[N ],k∈[K] ∈ RN×K be the encoded label matrix such that
yn,k = { 1, if ȳn = k, − 1, otherwise.
Similarly, we consider the following two-layer vector-output neural networks with ReLU activation:
F (Θ,X) =  f1(θ1,X)... fK(θK ,X)  =  (XW (1) 1 )+w (1) 2 ... (XW
(K) 1 )+w (K) 2  , where we write Θ = (θ1, . . . ,θK). For k = 1, . . . ,K, we have θk = (W (k) 1 ,w (k) 2 ) where W (k) 1 ∈ RN×m and w (k) 2 ∈ Rm. One can view each of the K outputs of F (Θ,X) as the output of a two-layer scalar-output neural network. Consider the following training problem:
min Θ K∑ k=1 N∑ n=1 `(yn,kfk(θk,xn)). (5)
According to (Lyu & Li, 2019), the gradient flow and the gradient descent finds a stationary point of the following non-convex max-margin problem:
arg min Θ K∑ k=1 1 2 ‖θk‖22, s.t. yn,kf(θk; xn) ≥ 1, n ∈ [N ], k ∈ [K]. (6)
Denote the set of all possible hyperplane arrangement as P = {diag(I(Xw ≥ 0))|w ∈ Rd}, (7)
and let p = |P|. We can also write P = {D1, . . . ,Dp}. From (Cover, 1965), we have an upper bound p ≤ 2r
( e(N−1)
r
)r where r = rank(X). We first reformulate (6) as convex optimization.
Proposition 1 The non-convex problem (6) is equivalent to the following convex program
min K∑ k=1 p∑ j=1 (‖uj,k‖2 + ‖u′j,k‖2),
s.t. diag(yk) p∑ j=1 DjX(uj,k − u′j,k) ≥ 1,
(2Dj − I)Xuj,k ≥ 0, (2Dj − I)Xu′j,k ≥ 0, j ∈ [p], k ∈ [K].
(8)
where yk is the k-th column of Y. The dual problem of (8) is given by max tr(ΛTY),
s.t. diag(yk)λk 0, max ‖w‖2≤1
|λTk (XTw)+| ≤ 1, k ∈ [K]. (9)
where λk is the k-th column of Λ.
We present the detailed derivation of the convex formulation (8) and its dual problem (9) in the appendix. Given u ∈ Rd, we define
D(u) = diag(I(Xu > 0)). (10)
For two vectors u,v ∈ Rd, we define the cosine angle between u and v by
cos∠(u,v) = uTv
‖u‖2‖v‖2 .

heading: 2.1 OUR CONTRIBUTIONS
text: The following theorem illustrate that for neurons satisfying sign(yTk (Xw (k) 1,i )+) = sign(w (k) 2,i ) at initialization, w(k)1,i align to the direction of ±XTD(w (k) 1,i )yk at a certain time T , depending on sign(w (k) 2,ik,+ ) at initialization. In Section 2.3, we show that these are dual extreme points of (8).
Theorem 1 Consider the K-class classification training problem (5) for any dataset. Suppose that the neural network is scaled at initialization such that ‖w(k)1,i ‖2 = |w (k) 2,i | for i ∈ [m] and k ∈ [K]. Assume that at initialization, for k ∈ [K], there exists neurons (w(k)1,ik ,w (k) 2,ik )such that
sign(yTk (Xw (k) 1,ik )+) = sign(w (k) 2,ik ) = s, (11)
where s ∈ {1,−1}. Consider the subgradient flow applied to the non-convex problem (5). Let δ ∈ (0, 1). Suppose that the initialization is sufficiently close to the origin. Then, for k ∈ [K], there exist T = T (δ, k) such that
cos∠ ( w
(k) 1,ik (T ), sXTD(w (k) 1,ik (T ))yk
) ≥ 1− δ.
Next, we impose conditions on the dataset to prove a stronger global convergence results on the flow. We say that the dataset (X, ȳ) is orthogonal separable among multiple classes if for all n, n′ ∈ [N ],
xTnxn′ > 0, if ȳn = ȳn′ , xTnxn′ ≤ 0, if ȳn 6= ȳn′ .
For orthogonal separable dataset among multiple classes, the subgradient flow for the non-convex problem (5) can find the global optimum of (6) up to a scaling constant.
Theorem 2 Suppose that (X, ȳ) ∈ RN×d × [K]N is orthogonal separable among multiple classes. Consider the non-convex subgradient flow applied to the non-convex problem (5). Suppose that the initialization is sufficiently close to the origin and scaled as in Theorem 1. Then, the non-convex subgradient flow converges to the global optimum of the convex program (8) and hence the non-convex objective (6) up to scaling.
Therefore, the above result characterizes the implicit regularization of unregularized gradient flow as convex regularization, i.e., group `1 norm, in the convex formulation (8). It is remarkable that group sparsity is enforced by small initialization magnitude with no explicit form of regularization.

heading: 2.2 CONVEX GEOMETRY OF NEURAL GRADIENT FLOW
text: Suppose that λ ∈ RN . Here we provide an interesting geometric interpretation behind the formula
cos∠(u,XTD(u)λ) > 1− δ.
which describes a dual extreme point to which hidden neurons approach to as predicted by Theorem 1. We now explain the geometric intuition behind this result. Consider an ellipsoid {Xu : ‖u‖2 ≤ 1}. A positive extreme point of this ellipsoid along the direction λ is defined by arg maxu : ‖u‖2≤1 λ TXu, which is given by the formula X Tλ
‖XTλ‖2 . Next, we consider the rectified ellipsoid setQ := {(Xu)+ : ‖u‖2 ≤ 1} introduced in (Ergen & Pilanci, 2021) and shown in Figure 1. The constraint maxu:‖u‖2≤1 |λ
T (Xu)+| ≤ 1 on λ is equivalent to λ ∈ Q∗. Here Q∗ is the absolute polar set of Q, which appears as a constraint in the convex program (9) and is defined as the following convex set
Q∗ = {λ : max z∈Q |λT z| ≤ 1}. (12)
An extreme point of this non-convex body along the direction λ is given by the solution of the problem
max u : ‖u‖2≤1 λT (Xu)+ = max Dj∈P max u : ‖u‖2≤1,(2Dj−I)Xu≥0 λTDjXu. (13)
Here, (λ,u) are primal-dual pairs as they appear in the convex dual program (9). First, note that a stationary point of gradient flow on the objective in (13) is given by the identity cu ∈ ∂◦uλ
T (Xu)+ where c is a constant. In particular, by picking the zero as the subgradient of (xTnu)+ when x T nu = 0,
u = XTD(u)λ
‖XTD(u)λ‖2 =
∑N n=1 λnxnI(uTxn > 0)
‖ ∑N n=1 λnxnI(uTxn > 0)‖2 . (14)
Note that the formula cos∠(u,XTD(u)λ) > 1− δ appearing in Theorem 1 shows that gradient flow reaches the extreme points of projected ellipsoids {DjXu : ‖u‖2 ≤ 1} in the direction of λ = yk, where Dj ∈ P corresponds to a valid hyperplane arrangement. This interesting phenomenon is depicted in Figures 3 and 4. The one-dimensional spikes in Figures 1 and 3 are projected ellipsoids. Detailed setup for Figure 1 to 4 and additional experiments can be found in Appendix F.
Figure 5: Two-layer ReLU network gradient descent dynamics on an orthogonal separable dataset. ŵ1,i = w1,i
‖w1,i‖2 is the normalized vector of the i-th hidden neuron in the first layer.

heading: 3 CONVEX MAX-MARGIN PROBLEM
text: In this section, we consider the equivalent convex model of the max-margin problem and its optimality conditions. We primarily focus on the binary classification problem for simplicity, which are later extended to the multi-class case. We can reformulate the nonconvex max-margin problem (2) as
min 1
2 (‖W1‖2F + ‖w2‖22), s.t. Y(XW1)+w2 ≥ 1, (15)
where Y = diag(y). This is a nonconvex optimization problem due to the ReLU activation and the two-layer structure of neural network. Analogous to the convex formulation introduced in (Pilanci & Ergen, 2020) for regularized training problem of neural network, we can provide a convex optimization formulation of (15) and derive the dual problem. Proposition 2 The problem (15) is equivalent to
P ∗cvx = min p∑ j=1 (‖uj‖2 + ‖u′j‖2),
s.t. Y p∑ j=1 DjX(u ′ j − uj) ≥ 1,
(2Dj − I)Xuj ≥ 0, (2Dj − I)Xu′j ≥ 0,∀j ∈ [p].
(16)
The dual problem of (16) is given by
D∗ = max λ yTλ s.t. Yλ 0, max u:‖u‖2≤1 |λT (XTu)+| ≤ 1. (17)
The following proposition gives a characterization of the KKT point of the non-convex max-margin problem (2). The definition of B-subdifferential can be found in Appendix A. Proposition 3 Let (W1,w2,λ) be a KKT point of the non-convex max-margin problem (2) (in terms of B-subdifferential). Suppose that w2,i 6= 0 for certain i ∈ [m]. Then, there exists a diagonal matrix D̂i ∈ RN×N satisfying
(D̂i)n = 1, for xTnw1,i > 0,
(D̂i)n ∈ {0, 1}, for xTnw1,i = 0, (D̂i)n = 0, for xTnw1,i < 0.
such that w1,i w2,i = XT D̂iλ, ‖XT D̂iλ‖2 = 1.
Based on the characterization of the KKT point of the non-convex max-margin problem (2), we provide an equivalent condition to ensure that it is also the KKT point of the convex max-margin problem (16). Theorem 3 The KKT point of the non-convex max-margin problem (15) (in terms of B-subdifferential) is the KKT point of the convex max-margin problem (16) if and only if λ is dual feasible, i.e.,
max u:‖u‖2≤1
|λT (Xu)+| ≤ 1. (18)
This condition is equivalent to for all Dj ∈ P , the dual variable λ satisfies that
max ‖u‖2≤1,(2Dj−I)Xu≥0
|λTDjXu| ≤ 1. (19)

heading: 3.1 DUAL FEASIBILITY OF THE DUAL VARIABLE
text: A natural question arises: is it possible to examine whether λ is feasible in the dual problem? We say the dataset (X,y) is orthogonal separable if for all n, n′ ∈ [N ],
xTnxn′ > 0, if yn = yn′ , xTnxn′ ≤ 0, if yn 6= yn′ .
For orthogonal separable data, as long as the induced diagonal matrices in Proposition 3 cover the positive part and the negative part of the labels, the KKT point of the non-convex max-margin problem (2) is the KKT point of the convex max-margin problem (16). Proposition 4 Suppose that (X,y) is orthogonal separable. Suppose that the KKT point of the nonconvex problem include two neurons (w1,i+ , w2,i+) and (w1,i− , w2,i−) such that the corresponding diagonal matrices D̂i+ and D̂i− defined in Proposition 3 satisfy that
D̂i+ ≥ diag(I(y = 1)), D̂i− ≥ diag(I(y = −1)). Then, the dual variable λ is dual feasible, i.e., satisfying (18).
The spike-free matrices discussed in (Ergen & Pilanci, 2021) also makes examining the dual feasibility of λ easier. The definition of spike-free matrices can be found in Appendix A Proposition 5 Suppose that X is spike-free. Suppose that the KKT point of the non-convex problem include two neurons (w1,i+ , w2,i+) and (w1,i− , w2,i−) such that the corresponding diagonal matrices D̂i+ and D̂i− defined in Proposition 3 satisfy that
D̂i+ ≥ diag(I(y = 1)), D̂i− ≥ diag(I(y = −1)). Then, the dual variable λ is dual feasible, i.e., satisfying (18).
Remark 1 For the spike-free data, the constraint on the dual problem is equivalent to
max Xu≥0,‖u‖2≤1
|λTXu| ≤ 1,
or equivalently max
Xu≥0,‖u‖2≤1 λTY+Xu ≤ 1, min Xu≥0 λTY−Xu ≥ −1.

heading: 4 SUB-GRADIENT FLOW DYNAMICS OF LOGISTIC LOSS
text: In this section, we consider the following sub-gradient flow of the logistic loss (4)
∂ ∂t w1,i(t) =w2,i(t)  ∑ n:(w1,i(t))T xn>0 λ̃n(t)xn(t)  , ∂ ∂t w2,i(t) = N∑ n=1 λ̃n(t)((w1,i(t)) Txn(t))+.
(20)
where the n-th entry of λ̃(t) ∈ RN is defined
λ̃n = −yn`′(qn), qn = yn(xTnW1)+w2. (21) For simplicity, we omit the term (t). For instance, we write w1,i = w1,i(t). To be specific, when wT1,ixn = 0, we select 0 as the subgradient of w2,i(w T 1,ixn)+ with respect to w1,i. Denote σi = sign(Xui). For σ ∈ {1,−1, 0}N , we define
g(σ, λ̃) = ∑
n:σn>0
λ̃nxn. (22)
For simplicity, we also write g(u, λ̃) := g(sign(Xu),λ) = ∑
n:wT1,ixn>0
λ̃nxn. (23)
Then, we can rewrite sub-gradient flow of the logistic loss (4) as follows:
∂ ∂t wi,1 = w2,ig(u, λ̃), ∂ ∂t wi,2 = w T i,1g(u, λ̃). (24)
Assume that the neural network is scaled at initialization, i.e., ‖w1,i(0)‖22 = w22,i(0) for i ∈ [m]. Then, the neural network is scaled for t ≥ 0.
Lemma 1 Suppose that ‖w1,i(0)‖2 = |w2,i(0)| > 0 for i ∈ [m]. Then, for any t > 0, we have ‖w1,i(t)‖2 = |w2,i(t)| > 0.
According to Lemma 1, for all t ≥ 0, sign(w2,i(t)) = sign(w2,i(0)). Therefore, we can simply write si = si(t) = sign(w2,i(t)). As the neural network is scaled for t ≥ 0, it is interesting to study the dynamics of w1,i in the polar coordinate. We write w1,i(t) = eri(t)ui(t), where ‖ui(t)‖2 = 1. The gradient flow in terms of polar coordinate writes
∂ ∂t ri = siu T i g(ui, λ̃), ∂ ∂t ui = si
( g(ui, λ̃)− ( uTi g(ui, λ̃) ) ui ) . (25)
Let xmax = maxi∈[n] ‖xi‖2. Define gmin to be gmin = min
σ∈Q ‖g(σ,y/4)‖2, s.t. g(σ,y/4) 6= 0, (26)
where we denote Q = {σ ∈ {1, 0,−1}N |σ = sign(Xw),w ∈ Rd}. (27)
As the set Q ⊆ {1,−1, 0}N is finite, we note that gmin > 0. We note that when maxn∈[N ] |qn| ≈ 0, we have λ̃ ≈ y4 . The following lemma shows that with initializations sufficiently close to 0, ‖g(u(t), λ̃(t))− g(u(t),y/4)‖2 and ∥∥∥ ddtg(u(t), λ̃(t))∥∥∥ 2 can be very small. Lemma 2 Suppose that T > 0 and δ > 0. Suppose that (u(t), r(t)) follows the gradient flow (25) with s = 1 and the initialization u(0) = u0 and r(0) = r0. Suppose that r0 is sufficiently small. Then, the following two statements hold.
• For all t ≤ T , we have
‖g(u(t), λ̃(t))− g(u(t),y/4)‖2 ≤ gminδ
8 .
• For t ≤ T such that sign(Xu(s)) is constant in a small neighbor of t, we have∥∥∥∥ ddtg(u(t), λ̃(t)) ∥∥∥∥ 2 ≤ g 2 minδ 16 .
Based on the above lemma on the property of g(u(t), λ̃(t)), we introduce the following lemma to upper-bound the time such that cos∠(u(t),g(u(t), λ̃(t))) approaches 1 − δ or sign(Xu(t)) changes.
Lemma 3 Let δ ∈ (0, 1).Suppose that u0 satisfies that ‖u0‖2 = 1 and λ̃(0)T (Xu0)+ > 0. Suppose that (u(t), r(t)) follows the gradient flow (25) with s = 1 and the initialization u(0) = u0 and r(0) = r0. Let v(t) = g(u(t),λ̃(t))
‖g(u(t),λ̃(t))‖2 . We write v0 = v(0), σ0 = σ(0) and g0 = ‖g(σ0,y/4)‖2.

heading: Denote
text: T ∗ = 1 2g0 √ 1− δ/8
( log √ 1− δ/8 + 1− δ√ 1− δ/8− 1 + δ − log √ 1− δ/8 + vT0 u0√ 1− δ/8− vT0 u0 ) . (28)
For c ∈ (0, 1− δ], define
T shift(c) = 1 2g0 √ 1− δ/8
( log √ 1− δ/8 + c√ 1− δ/8− c − log √ 1− δ/8 + vT0 u0√ 1− δ/8− vT0 u0 ) (29)
Suppose that r0 is sufficiently small such that the statements in Lemma 2 holds for T = T ∗. Then, at least one of the following event happens
• There exists a time T such that we have sign(Xu(t)) = sign(Xu0) for t ∈ [0, T ) and sign(Xu(t)) 6= sign(Xu0). Let u1 = u(T ) and v1 = limt→T−0 v(t). If uT1 v1 ≤ 1− δ, then the time T satisfies that
T ≤ T shift(vT1 u1). Otherwise, there exists a time T ′ satisfying T ′ ≤ T ∗, such that we have sign(Xu(t)) = sign(Xu0) for t ∈ [0, T ′] and u(T ′)Tv(T ′) ≥ 1− δ.
• There exists a time T ≤ T ∗,
such that we have sign(Xu(t)) = sign(Xu0) for t ∈ [0, T ] and u(T )Tv(T ) ≥ 1− δ. Corollary 1 Suppose that there exists a time T such that we have sign(Xu(t)) = sign(Xu0) for t ∈ [0, T ) and sign(Xu(t)) 6= sign(Xu0). If T > T shift(vT1 u1) =
1 g0 √ 1−δ/8
( log
√ 1−δ/8+vT1 u1√ 1−δ/8−vT1 u1 − log √ 1−δ/8+vT0 u0√ 1−δ/8−vT0 u0 ) , then, we have uT1 v1 > 1− δ.
Proposition 6 Consider the sub-gradient flow (25) with s = 1 and the initialization u(0) = u0 and r(0) = r0. Here at initilization the neuron u0 satisfies that ‖u0‖2 = 1 and yT (Xu0)+ > 0. Let v(t) = g(u(t),λ̃(t))
‖g(u(t),λ̃(t))‖2 . For any δ > 0, for sufficiently small r0, there exists a time T = O(log(δ−1))
such that u(T )Tv(T ) ≥ 1− δ and cos∠(u(T ),g(u(T ),y)) ≥ 1− δ. Remark 2 The statement of proposition is similar to Lemma 4 in (Maennel et al., 2018). However, their proof has a problem because they did not consider the change of sign(Xw) along the gradient flow. Our proof in Appendix D.4 corrects this error.

heading: 4.1 PROPERTY OF ORTHOGONAL SEPARABLE DATASETS
text: Denote B = {w ∈ Rd : ‖w‖2 ≤ 1}. The following lemma give a sufficient condition on w to satisfy the condition in Proposition 4. Lemma 4 Assume that (X,y) is orthogonal separable. Suppose that w ∈ B is a local maximizer of yT (Xw)+ in B and (Xw)+ 6= 0. Then, 〈w,xn〉 > 0 for n ∈ [N ] such that yn = 1. Suppose that w ∈ B is a local minimizer of yT (Xw)+ in B and (Xw)+ 6= 0. Then, 〈w,xn〉 > 0 for n ∈ [N ] such that yn = −1.
We show an equivalent condition of u ∈ B being the local maximizer/minimizer of yT (Xu)+ in B. Proposition 7 Assume that (X,y) is orthogonal separable. Then, u ∈ B is a local maximizer of yT (Xu)+ in B is equivalent to cos∠(u,g(u,y)) = 1. Similarly, u ∈ B is a local minimizer of yT (Xu)+ in B is equivalent to cos∠(u,g(u,y)) = −1.
Based on Proposition 4 and 7, we present the main theorem. Theorem 4 Suppose that the dataset is orthogonal separable and θ(t) follows the gradient flow. Suppose that the neural network is scaled at initialization, i.e., ‖w1,i(0)‖2 = |w2,i(0)| for all i ∈ [m]. For almost all initializations which are sufficiently close to zero, the limiting point of θ(t)‖θ(t)‖2 is θ∗
‖θ∗‖2 , where θ∗ is a global minimizer of the max-margin problem (2).
We present a sketch of the proof as follows. According to Proposition 6, for initialization sufficiently close to zero, there exist two neurons and time T+, T− > 0 such that cos∠(w1,i+(T+),g(w1,i+(T+),y)) ≥ 1− δ and cos∠(w1,i−(T−),g(w1,i−(T−),y)) ≤ −(1− δ). This implies that w1,i+(T+) and w1,i−(T+) are sufficiently close to certain stationary points of gradient flow maximizing/minimizing yT (Xu+) over B, i.e., {u ∈ B| cos(u,g(u,y)) = ±1}. As the dataset is orthogonal separable, from Proposition 7 and Lemma 4, the induced masking matrices D̂i+(T+) and D̂i−(T−) by w1,i+(T+)/w1,i−(T−) in Proposition 3 satisfy that D̂i+(T+) ≥ diag(I(y = 1)) and D̂i−(T−) ≥ diag(I(y = −1)). According to Lemma 3 in (Phuong & Lampert, 2021), for t ≥ max{T+, T−}, we also have D̂i+(t) ≥ diag(I(y = 1)) and D̂i−(t) ≥ diag(I(y = −1)). According to Theorem 3 and Proposition 4, the KKT point of the non-convex max-margin problem (2) that gradient flow converges to corresponds to the KKT point of the convex max-margin problem (16).

heading: 5 CONCLUSION
text: We provide a convex formulation of the non-convex max-margin problem for two-layer ReLU neural networks and uncover a primal-dual extreme point relation between non-convex subgradient flow. Under the assumptions on the training data, we show that flows converge to KKT points of the convex max-margin problem, hence a global optimum of the non-convex objective.

heading: 6 ACKNOWLEDGEMENTS
text: This work was partially supported by the National Science Foundation under grants ECCS-2037304, DMS-2134248, the Army Research Office.

heading: A DEFINITIONS AND NOTIONS
text: We introduce several useful definitions and notions which will be utilized in the proof.

heading: A.1 DEFINITIONS
text: Definition 1 Let O ⊂ Rn be an open set and let F : O → R be locally Lipschitz continuous at x ∈ O. Let DF be the differentiable points of F in O. The B-subdifferential of F at x is defined by
∂BF (x) := { lim k→∞ F ′(xk)|xk ∈ DF , xk → x } . (30)
The set ∂◦F (x) = co(∂BF (x)) is called Clarke’s subdifferential, where co denotes the convex hull.
Definition 2 A matrix A is spike-free if and only if the following conditions hold: for all ‖u‖2 ≤ 1, there exists ‖z‖2 ≤ 1 such that
(Au)+ = Az. (31)
This is equivalent to say that
max u:‖u‖2≤1,(I−XXT )(Xu)+=0
‖X†(Xu)+‖2 ≤ 1. (32)

heading: A.2 NOTIONS
text: We use the following letters for indexing.
• The index n is for the n-th data sample xn. • We use the index i to represent the i-th neuron-pair (w1,i, w2,i). • The index j is for the j-th masking matrix Di ∈ P .

heading: B PROOFS IN SECTION 3

heading: B.1 PROOF FOR PROPOSITION 2
text: Consider the following loss function l̃ : RN × RN → R ∪ {+∞}
˜̀(z,y) = { 0, ynzn ≥ 1,∀n ∈ [N ], +∞, otherwise. (33)
For a given y ∈ {1,−1}N , ˜̀(z,y) is a convex loss function of z. The non-convex max-margin is equivalent to
min l̃ ((XW1)+w2,y) + 1
2
( ‖W1‖2F + ‖w2‖22 ) . (34)
According to Appendix A.13 in (Pilanci & Ergen, 2020), the problem (34) is equivalent to
min l̃ ( p∑ i=1 DiX(u ′ i − ui),y ) + 1 2 ( ‖W1‖2F + ‖w2‖22 ) ,
s.t. (2Di − I)Xui ≥ 0, (2Di − I)Xu′i ≥ 0,∀i ∈ [p]. (35)
This is equivalent to (16). For fixed y ∈ {1,−1}N , the Fenchel conjugate function of ˜̀(z,y) with respect to z can be computed by
l∗(λ̂,y) = max z∈RN zTx− ˜̀(z,y)
= max z∈RN
zT λ̂, s.t. diag(y)z ≥ 1,
= { yT λ̂, diag(y)λ̂ ≤ 0 +∞, otherwise.
(36)
According to Theorem 6 in (Pilanci & Ergen, 2020), the dual problem of (16) writes
max−l̃∗(λ,y), s.t. max u:‖u‖2≤1 |λT (Xu)+| ≤ 1, (37)
which is equivalent to
max−yTλ, s.t. diag(y)λ ≤ 0, max u:‖u‖2≤1 |λT (Xu)+| ≤ 1. (38)
By taking λ = −λ̂, we derive (17). This completes the proof.

heading: B.2 PROOF FOR PROPOSITION 3
text: For the non-convex max-margin problem (15), consider the Lagrange function
L(W1,w2,λ) = 1
2 (‖W1‖2F + ‖w2‖22)− (Yλ)T (Y(XW1)+w2 − 1)
where Yλ 0. The KKT point of the non-convex max-margin problem (15) (in terms of Bsubdifferential) satisfies
0 ∈ ∂BW1L(W1,w2,λ), w2 − (XW1)T+λ = 0,
λn(yn(x T nW1)+w2 − 1) = 0.
(39)
The KKT condition on the i-th column of W1 is equivalent to
w1,i = N∑ n=1 w2,iλnxngn,i, (40)
where gn,i ∈ ∂B(z)+|z=xTnw1,i . In other words, we have
gn,i { = I(xTnw1,i ≥ 0), if xTnw1,i 6= 0, ∈ {0, 1}, if xTnw1,i = 0.
(41)
Let D̂i = diag([g1,i, . . . , gN,i]). Then, we can write that
w1,i = N∑ n=1 λngn,ixnw2,i
=w2,iX T D̂iλ.
(42)
From the definition of gn,i, we have
gn,ix T nw1,i = 0. (43)
Therefore, we can compute that
w2,i =(Xw1,i) T +λ
= N∑ n=1 I(xTnw1,i ≥ 0)xTnw1,iλn
= N∑ n=1 gn,ix T nw1,iλn
=wT1,iX T D̂iλ.
(44)
In summary, we have w1,i = w2,iX T D̂iλ, w2,i = w T 1,iX
T D̂iλ. (45) Suppose that w2,i 6= 0. This implies that
w1,i w2,i = XT D̂iλ, ‖XT D̂iλ‖2 = 1. (46)
This completes the proof.

heading: B.3 PROOF FOR THEOREM 3
text: PROOF We can write the Lagrange function for the convex max-margin problem (16) as L({uj}pj=1, {u ′ j} p j=1,λ, {zj} p j=1, {z ′ i} p j=1)
= p∑ j=1 (‖uj‖2 + ‖u′j‖2) + λ Tdiag(y) 1− diag(y) p∑ j=1 DjX(uj − u′j)  −
p∑ j=1 (zTj (2Dj − I)Xuj + (z′j)T (2Dj − I)Xu′j)
=λTy + p∑ j=1 (‖uj‖2 + ‖u′j‖2) + p∑ j=1 (u′j) T (XTDjλ−XT (2Dj − I)z′j)
+ p∑ j=1 (uj) T (−XTDjλ−XT (2Dj − I)zj).
(47)
where zj , z′j ∈ RN satisfies that zj ≥ 0, z′j ≥ 0 for j ∈ [p] and λ ∈ RN satisfies that diag(y)λ ≥ 0. The KKT point shall satisfy the following KKT conditions:
−XTDjλ + XT (2Dj − I)z′j ∈ ∂u′j‖u ′ j‖2,
XTDjλ + X T (2Dj − I)zj ∈ ∂uj‖uj‖2,
λn  p∑ j=1 (Dj)nx T n (uj − u′j)− yn  = 0, zj,n(2(Dj)n,n − 1)xTnuj = 0, z′j,n(2(Dj)n,n − 1)xTnu′j = 0.
(48)
Let (W1,w2,λ) be the KKT point of the non-convex problem (2) and λ satisfies (19). Let D̂i be the diagonal matrix defined in Proposition 3 with respect to w1,i and denote P̄ = {D̂i|i ∈ [m]}. Without the loss of generality, we may assume that {D̄i}mi=1 are different. (Otherwise, we can merge two neurons w1,i1 and w1,i2 with D̄i1 = D̄i2 together.)
Suppose that Dj ∈ P̂ , i.e., Dj = D̂i for certain i ∈ [m]. By letting u′j = w1,iw2,i, z′j = 0, uj = −w1,iw2,i and zj = 0, the following identities hold.
XTDjλ + X T (2Di − I)z′j = XT D̂iλ = w1,i w2,i = u′i ‖u′i‖ . (49)
−XTDjλ + XT (2Di − I)zj = −XT D̂iλ = w1,i w2,i = ui ‖ui‖ . (50)
Therefore, for index j satisfying Di ∈ P̂ , the first two KKT conditions in (48) hold.
For Dj /∈ P̂ , we can let uj = u′j = 0. As λ satisfies (19), we have max
‖u‖2≤1,(2Dj−I)Xu≥0 |λTDjXu| ≤ 1. (51)
According to Lemma 4 in (Pilanci & Ergen, 2020), this implies that there exist zj , z′j ≥ 0 such that ‖ −XTDjλ + ZT (2Dj − I)z′j‖ ≤ 1, ‖XTDjλ + ZT (2Dj − I)zj‖ ≤ 1. (52) Therefore, the first two KKT conditions in (48) hold.
From our choice of uj , zj ,u′j , zj , the last two KKT conditions in (48) hold. We also note that p∑ j=1 DjX(u ′ j − uj) = m∑ i=1 (Xw1,i)+w2,i. (53)
As (W1,w2,λ) is the KKT point of the non-convex problem, the third KKT condition in (48) holds. This completes the proof.

heading: C PROOFS IN SECTION 3.1
text: In this section, we present several proofs for propositions in Section 3.1.

heading: C.1 PROOF FOR PROPOSITION 4
text: We start with two lemmas. Lemma 5 Suppose that u0 = XT D̂0λ and ‖u0‖2 ≤ 1. For any masking matrix Dj ∈ P such that (Dj − D̂0)I(λ > 0) = 0, we have
max (2Dj−I)Xu≥0,‖u‖2≤1
λTDjXu ≤ 1. (54)
PROOF According to Lemma 4 in (Pilanci & Ergen, 2020), the constraint (54) is equivalent to that there exist zj ∈ RN such that zj ≥ 0 and ‖XTDjλ + XT (2Dj − I)zj‖ ≤ 1. (55) Consider the index n ∈ [N ] such that (Dj − D̂0)nn 6= 0. As (Dj − D̂0)I(λ > 0) = 0, we have λn ≤ 0. We let (zj)n = −λn. If (D̂0)nn = 0, then we have (Dj)nn = 1 and
(Dj − D̂0)nnλnxn = λnxn = −xTn (2(Dj)nn − 1)(zj)n. (56) If (D̂0)nn = 1, then we have (Dj)nn = 0 and
(Dj − D̂0)nnλnxn = −λnxn = −xTn (2(Dj)nn − 1)(zj)n. (57) For other index n ∈ [N ], we simply let (zj)n = 0. Then, we have
(Dj − D̂0)nnλnxn = 0 = −xTn (2(Dj)nn − 1)(zj)n. (58) Based on our choice of zj , we have zj ≥ 0 and for n ∈ [N ]
(Dj − D̂0)nnλnxn = −xTn (2(Dj)nn − 1)(zj)n. (59) This implies that XT (Dj − D̂0)λ = −XT (2Dj − I)zj . (60) Hence, we have
XTDjλ + X T (2Dj − I)zj = XT D̂0λ = u0. (61)
Therefore, ‖XTDjλ + XT (2Dj − I)zj‖2 ≤ 1. Lemma 6 Suppose that the data is orthogonal separable and Yλ ≥ 0. Suppose that u0 = XT D̂0λ and ‖u0‖2 ≤ 1. For any masking matrix Dj such that D̂0 − Dj ≥ 0, we have ‖XTDjλ‖2 ≤ ‖u0‖2 ≤ 1. Therefore, (54) holds. PROOF We note that u0 = XT (D̂0 − Dj)λ + XDjλ. Denote a = XT (D̂0 − Dj)λ and b = XTDjλ. We note that
aTb =  ∑ n:(D̂0)nn=1,(Dj)n,n=0 λnxn T  ∑ n′:(D̂0)n′n′=0,(Dj)n′n′=0 λn′xn′  . (62) As diag(y)λ ≥ 0, λn has the same signature with yn. Therefore, from the orthogonal separability of the data, we have
λnλn′x T nx T n′ ≥ 0. (63)
This immediately implies that aTb ≥ 0. Therefore, 1 ≥ ‖u0‖22 = ‖a + b‖22 = ‖a‖22 + ‖b‖22 + 2aTb ≥ ‖a‖2. (64) This completes the proof.
Based on Lemma 5 and Lemma 6, we present the proof for Proposition 3. Let u+ = w1,i+ w2,i+ . From the proof of Proposition 3, we note that ‖u+‖2 = 1. For any masking matrix Dj ∈ P , let D̃ = D̂i+Dj . As D̂i+ ≥ D̃, according to Lemma 6, we have ‖XT D̃λ‖2 ≤ ‖XT D̂i+λ‖2 = ‖u+‖2 ≤ 1. (65) As Yλ ≥ 0 and D̂i+ ≥ diag(I(y = 1)), we have (Dj−D̃)I(λ > 0) = Dj(I−D̂i+)I(λ > 0) = 0. From Lemma 5, we note that λ satisfies (54). Similarly, we can show that −λ also satisfies (54). This completes the proof.

heading: C.2 PROOF FOR PROPOSITION 5
text: PROOF Note that Yλ ≥ 0. Let Y+ = diag(I(y = 1)) and Y− = diag(I(y = −1)). We claim that
max ‖u‖≤1 λT (Xu)+ = max ‖u‖≤1 λTY+(Xu)+. (66)
Firstly, we note that
λT (Xu)+ = N∑ n=1 λn(x T nu)+ ≤ N∑ n=1 (λn)+(x T nu)+ = λ TY+(Xu)+. (67)
This implies that max‖u‖≤1 λ T (Xu)+ ≤ max‖u‖≤1 λTY+(Xu)+.
On the other hand, suppose that u ∈ arg max‖u‖≤1 λ TY+(Xu)+. As X is spike-free, there exists z such that ‖z‖2 ≤ 1 and Xz = (Xu)+. Therefore, we have
λTY+(Xu)+ = λ TY+Xz = λ TXz = λT (Xz)+. (68)
This implies that max‖u‖≤1 λ T (Xu)+ ≥ max‖u‖≤1 λTY+(Xu)+.
For any Dj ∈ P with Dj ≥ Y+. We note that
λT (Xu)+ ≤ λTDj(Xu)+ ≤ λTY+(Xu)+. (69)
Combining with (67), this implies that max‖u‖≤1 λ T (Xu)+ = max‖u‖≤1 λ TD(Xu)+.
Let us go back to the original problem. Let u+ = w1,i+ w2,i+ . We note that (Xw+) = D̂i+Xw+ = D̂i+XX T D̂i+λ. Therefore, we have
λT (Xw+) = λ T D̂i+XX T D̂i+λ = ‖XT D̂i+λ‖22 = ‖u+‖22 = 1. (70)
Thus, for any ‖u‖2 ≤ 1, suppose that (Xu)+ = Xz, where ‖z‖2 ≤ 1. Then, we have
λT D̂i+(Xu)+ = λ T D̂i+Xz ≤ ‖z‖2 ≤ 1. (71)
Therefore, max‖u‖≤1 λ T (Xu)+ = max‖u‖≤1 λ TD+(Xu)+ ≤ 1. Similarly, we have
min ‖u‖≤1 λT (Xu)+ = min ‖u‖≤1 λTD−(Xu)+ ≥ −1.
This completes the proof.

heading: D PROOFS IN SECTION 4

heading: D.1 PROOF FOR LEMMA 1
text: PROOF According to the sub-gradient flow (24), we can compute that
∂
∂t
( ‖w1,i‖22 − w22,i ) = 2wT1,i ( w2,ig(u, λ̃) ) − 2w2,iwT1,ig(u, λ̃) = 0. (72)
Let T0 = sup{T |‖w1,i(t)‖2 = |w2,i(t)| > 0,∀i ∈ [n], t ∈ [0, T )}. For t ∈ [0, T0), as the neural network is scaled, it is sufficient study the dynamics of w1,i in the polar coordinate. Let us write w1,i(t) = e
ri(t)ui(t), where ‖ui(t)‖2 = 1. Then, in terms of polar coordinate, the projected gradient flow follows
∂ ∂t ri =sign(w2,i)u T i g(ui, λ̃), ∂ ∂t ui =sign(w2,i) ( g(ui, λ̃)− ( uTi g(ui, λ̃) ) ui ) .
(73)
Without the loss of generality, we may assume that w2,i(0) 6= 0 for i ∈ [m]. Denote
xmax = max i∈[n] ‖xi‖2. (74)
From the definition of λ̃, we have ‖λ̃‖∞ ≤ 1/4. Therefore, we have∣∣∣∣ ∂∂tri ∣∣∣∣ ≤ ‖g(ui, λ̃)‖2 ≤ ∥∥∥∥∥∥ ∑
j:xTj u>0
λ̃jxj ∥∥∥∥∥∥ 2 ≤ nxmax 2 . (75)
Therefore, for finite t > 0, we have
ri(t) ≥ ri(0)− nxmaxt
4 , (76)
which implies that |w2,i(t)| > 0. This implies that T0 =∞.

heading: D.2 PROOF OF LEMMA 2
text: PROOF As we have ‖w1,i‖2 = |w2,i|, for n ∈ [N ], we can compute that
|qn| =|(xTnW1)+w2|
≤ m∑ i=1 |(xTnw1,i)+w2,i|
= m∑ i=1 ‖w1,i‖2|(xTnw1,i)+|
≤ m∑ i=1 ‖w1,i‖2|xTnw1,i|
≤‖xn‖2 m∑ i=1 ‖w1,i‖22.
(77)
Note that λ̃n = −yn`′(qn) and yn4 = −yn` ′(0). As `′ is 14 -Lipschitz continuous, we have∣∣∣λ̃n − yn/4∣∣∣ ≤ 1 4 |qn| ≤ ‖xn‖2 4 m∑ i=1 ‖w1,i‖22. (78)
For any σ̂ ∈ Q, as λ̃n ∈ [0, 1/4] for n ∈ [N ], we have
‖g(σ̂, λ̃)− g(σ̂,y/4)‖2
≤ ∥∥∥∥∥∥ ∑
n:(σ̂)n>0
(λ̃n − yn/4)xn ∥∥∥∥∥∥ 2
≤ ∑
k:(σ̂)k>0
|λk − λ̃k| ‖xk‖2
≤ n∑ k=1 ‖xk‖22 4 m∑ j=1 ‖w1,j‖22
=c1 m∑ i=1 ‖w1,i‖22,
(79)
where c1 = 14‖X‖ 2 F > 0 is a constant. Therefore, we can bound ‖g(σ̂, λ̃(t))‖ by
‖g(σ̂, λ̃(t))‖2 ≤ ‖g(σ̂,y/4)‖2 + c1 m∑ i=1 ‖w1,i(t)‖22 ≤ dmax + c1 m∑ i=1 e2ri(t), (80)
where we let gmax = max
σ∈Q ‖g(σ,y/4)‖2. (81)
Let r(t) = maxi∈[m] ri(t). We note that
∂ ∂t r(t) ≤ dmax + c1ne2r(t) ≤ c2(1 + e2r(t)), (82)
where c2 = max{nc1, dmax} > 0 is a constant. If we start with r(0) 0, then, r(t) cannot grow much faster than c2t. Let r̃(t) satisfy the following ODE:
∂ ∂t r̃(t) = c2(1 + e 2r̃(t)). (83)
The solution is given by
r̃a(t) = c2(t− a)− 1
2 log(1− e2c2(t−a)), (84)
where a > 0 is a parameter depending on the initialization. For any initial r(0), we have a unique a satisfying r̃a(0) = r(0). Therefore, we have r(t) ≤ r̃a(t) and
‖g(σ, λ̃(t))− g(σ,y/4)‖2 ≤ c1ne2r̃a(t). (85) According to the bound (85), by choosing a sufficiently small r0, (which leads to a sufficiently small a), such that
e2r̃a(T ) ≤ min { dminδ
16c1 , d2minδ 4n2x3max
} . (86)
Therefore, for t ≤ T , we have
‖g(σ̂, λ̃(t))− g(σ̂,y/4)‖2 ≤ c1ne2r̃a(t) ≤ c1ne2r̃a(T ) ≤ dminδ
8 . (87)
Hence, we have
‖g(σ(t), λ̃(t))− g(σ(t),y/4)‖2 ≤ c1ne2r̃a(t) ≤ c1ne2r̃a(T ) ≤ dminδ
8 . (88)
We can compute that d
dt λ̃i = −yil(2)(qi)
d dt qi. (89)
As l(2)(q) ∈ (0, 1/4], we can compute that∣∣∣∣ ddtqi ∣∣∣∣ ≤ m∑
j=1
|w2,j |‖xi‖2 ∥∥∥∥ ddtw1,j ∥∥∥∥ 2
+ m∑ j=1 ‖w1,j‖2‖xi‖2 ∣∣∣∣ ddtw2,j ∣∣∣∣ ≤n
4 m∑ j=1 ‖w1,j‖22x2max + n 4 m∑ j=1 w22,jx 2 max
≤nx 2 max
2 e2r(t).
(90)
Therefore, we have ∣∣∣∣ ddt λ̃i ∣∣∣∣ = |`′′(qi)| ∣∣∣∣ ddtqi ∣∣∣∣ ≤ 14 ∣∣∣∣ ddtqi ∣∣∣∣ ≤ nx2max8 e2r(t). (91) Suppose that sign(Xu(s)) = σ(t) holds for s in a small neighbor of t. Then, we have∥∥∥∥ ddtg(u(t), λ̃(t)) ∥∥∥∥ 2 = ∥∥∥∥ ddtg(σ(t), λ̃(t)) ∥∥∥∥ 2
≤ n∑ i=1 ‖xi‖2 ∣∣∣∣ ddt λ̃i ∣∣∣∣ ≤ n2x3max8 e2r(t) ≤n
2x3max 8 e2r̃a(T ) ≤ d 2 minδ 16 .
(92)
This completes the proof.

heading: D.3 PROOF OF LEMMA 3
text: PROOF Let T0 = sup{T |sign(Xu(t)) = sign(Xu0),∀t ∈ [0, T )}. We analyze the dynamics of u(t) in the interval [0,min{T0, T ∗}]. For t ≤ min{T0, T ∗}, as the statements in Lemma 2 hold, we can compute that
d dt v(t)Tu(t)
= d
dt
( g(σ0, λ̃(t))
‖g(σ0, λ̃(t))‖2
T
u(t)
)
=
( g(σ0, λ̃(t))
‖g(σ0, λ̃(t))‖2
)T d
dt u(t) + u(t)T
1 ‖g(σ0, λ̃(t))‖2 d dt g(σ0, λ̃(t))
− u(t)Tg(σ0, λ̃(t)) g(σ0, λ̃(t))
T d dtg(σ0, λ̃(t))
‖g(σ0, λ̃(t))‖32
≥g(σ0, λ̃(t))T d
dt ut −
2
gmin ∥∥∥∥ ddtg(σ0, λ̃(t)) ∥∥∥∥ 2
≥‖g(σ0, λ̃(t))‖2 ( 1− (v(t)Tu(t))2 ) − gminδ
8 ≥g0 (1− δ/8) ( 1− (v(t)Tu(t))2 ) − gminδ
8 ≥g0 ( 1− δ/4− (v(t)Tu(t))2 ) .
(93)
Here we utilize that g0 ≥ gmin, where gmin is defined in (26). Let z(t) satisfies the ODE dz(t)
dt = (1− δ/4− z(t)2)g0, (94)
with initialization z(0) = vT0 u0. Then, we note that
z(t) = √ 1− δ/8− 2 √
1− δ/8 1 + c3 exp(2g0t/( √ 1− δ/8)) , (95)
where c3 = (√
1−δ/8 vT0 u0
− 1 )−1 . We can compute that
z(T3) = 1− δ. (96) According to the comparison theorem, for t ≤ min{T0, T3}, we have
v(t)Tu(t) ≥ z(t). (97)
We first consider the case where T0 =∞. As T0 =∞, we have v(T ∗)Tu(T ∗) ≥ z(T ∗) = 1− δ. (98)
Therefore, the second event holds for T ≤ T ∗. Otherwise, we have T0 < ∞. Recall that u1 = u(T0) and v1 = limt↑T0 v(t). Let T1 = sup{T |v(t)Tu(t) < vT1 u1,∀t ∈ [0, T )} and T2 = sup{T |v(t)Tu(t) < 1 − δ, ∀t ∈ [0, T )}. If T2 ≤ T0, for t ∈ [0, T2], we have
d dt v(t)Tu(t) ≥
( 1− δ/4− (1− δ)2 ) g0 > 0. (99)
Therefore, v(t)Tu(t) monotonically increases in [0, T2]. As v(t)Tu(t) ≥ z(t) for t ∈ [0, T0], we have that z(T2) ≤ v(T2)Tu(T2) = 1− δ = z(T3). Hence, we have T2 ≤ T ∗. Therefore, the second condition of the first event holds at T = T2.
Then, we consider the case where T2 ≥ T0. For t ≤ T0, we have v(t)Tu(t) ≤ 1−δ. This implies that vT1 u1 ≤ 1− δ. Apparently, we have T1 ≤ T0. If T1 < T0, as T0 ≤ T2, for t ∈ [0, T0], the inequality
(99) holds. This implies that limt→T0−0 v(t) Tu(T0) > v(T1) Tu(T1) = limt→T0−0 v(t) Tu(T0), which leads to a contradiction. Therefore, we have T0 = T1. We note that
z(T shift(uT1 v1)) = u T 1 v1. (100)
As u(t)Tg(u(t), λ̃(t)) ≥ z(t) for t ∈ [0, T0], we have that z(T1) ≤ uT1 v1 ≤ z(T4). Hence, we have T0 = T1 ≤ T shift(uT1 v1). This completes the proof.

heading: D.4 PROOF OF PROPOSITION 6
text: We first introduce a lemma.
Lemma 7 Let a,b ∈ Rd and 0 < δ < c. Suppose that ‖a− b‖2 ≤ δ and ‖a‖2 ≥ c. Then, we have∥∥∥∥ a‖a‖2 − b‖b‖2 ∥∥∥∥ 2 ≤ 2δ c . (101)
PROOF As δ < c, we have ‖b‖2 > ‖a‖2 − ‖a− b‖2 ≥ c− δ > 0. We first note that∣∣‖a‖−12 − ‖b‖−12 ∣∣ = |‖a‖2 − ‖b‖2|‖a‖2‖b‖2 ≤ δc‖b‖2 . (102) Therefore, we can compute that∥∥∥∥ a‖a‖2 − b‖b‖2 ∥∥∥∥ 2
≤ ∥∥∥∥ a‖a‖2 − b‖a‖2 ∥∥∥∥ 2 + ∣∣∣∣ 1‖a‖2 − 1‖b‖2 ∣∣∣∣ ‖b‖2 ≤δ c + δ c = 2δ c .
(103)
This completes the proof.
Then we present the proof of Proposition 6.
PROOF As yT (Xu0)+ > 0, with sufficiently small initialization and sufficiently small δ > 0, we also have λ̃(0)T (Xu0)+ ≥ yT (Xu0)+/4− ‖X‖2‖λ̃(0)− y/4‖2 > 0. We prove that there exists a time T such that u(T )Tv(T ) ≥ 1− 34δ by contradiction. Denote v0 = v(0). For all possible values of ‖g(u,y/4)‖2, we can arrange them from the smallest to the largest by g(1) < g(2) < · · · < g(p).
Let Ti = 1 2 √
1−δ/8g(i)
( log
√ 1−δ/8+1−δ/2√ 1−δ/8−1+δ/2 − log √ 1−δ/8+g−1 (i) vT0 u0√ 1−δ/8−g−1
(i) vT0 u0
) and T = ∑p i=1 Ti. Suppose
that r0 is sufficiently small such that statements in Lemma 2 holds for T . According to Lemma 3, we can find 0 = t0 < t1 < . . . such that for i = 1, . . . , sign(Xu(t)) is constant on [ti−1, ti) and sign(Xu(ti−1)) 6= sign(Xu(ti)). We write ui = u(ti), gi = ‖g(u(ti),y/4)‖2,
g−i = lim t↑ti g(u(t), λ̃(t)), gi = g(u(ti), λ̃(t)), (104)
v−i = g−i ‖g−i ‖2 and vi = gi‖gi‖2 . We note that g − i = g + i−1. According to Lemma 3, we have
ti − ti−1 ≤ 1 2 √ 1− δ/8gi−1
( log √ 1− δ/8 + (v−i )Tui√ 1− δ/8− (v−i )Tui − log √ 1− δ/8 + vTi−1ui−1√ 1− δ/8− vTi−1ui−1 )
≤ 1 2 √ 1− δ/8gmin
( log √ 1− δ/8 + (v−i )Tui√ 1− δ/8− (v−i )Tui − log √ 1− δ/8 + vTi−1ui−1√ 1− δ/8− vTi−1ui−1 ) .
(105) Here we utilize that gi−1 ≥ gmin, where gmin is defined in (26). This implies that√
1− δ/8 + (v−i )Tui√ 1− δ/8− (v−i )Tui ≥ e2 √
1−δ/8gmin(ti−ti−1) √
1− δ/8 + vTi−1ui−1√ 1− δ/8− vTi−1ui−1 . (106)
We can show that for t satisfying t ≥ 1 2 √ 1−δ/8gmin
( log
√ 1−δ/8+1−δ/2√ 1−δ/8−1+δ/2 − log 1+g −1 minv T 0 u0 1−g−1minvT0 u0
) and
t ≤ T , we have ‖g(u(t),λ)‖2 > gmin. According to Lemma ??, as gi ≥ gmin, we have√ 1− δ/8 + g−1min(g − i )
Tui√ 1− δ/8− g−1min(g − i ) Tui ≥ e2 √
1−δ/8gmin(ti−ti−1) √
1− δ/8 + g−1mingTi−1ui−1√ 1− δ/8− g−1mingTi−1ui−1 . (107)
This implies that√ 1− δ/8 + g−1min(g − i )
Tui√ 1− δ/8− g−1min(g − i ) Tui ≥ e2 √ 1−δ/8gminti √ 1− δ/8 + g−1minvT0 u0√ 1− δ/8− g−1minvT0 u0 , (108)
or equivalently, for any t > 0, we have√ 1− δ/8 + g−1min(g(u(t)), λ̃(t))Tu(t)√ 1− δ/8− g−1ming(u(t), λ̃(t))Tu(t) ≥ e2 √ 1−δ/8gmint √ 1− δ/8 + g−1minvT0 u0√ 1− δ/8− g−1minvT0 u0 . (109)
Here we utilize that g(u(t),λ(t))Tu(t) is continuous w.r.t. t. Therefore, for t ≥ 1 2gmin ( log 2−δδ − log 1+g−1minv T 0 u0
1−g−1minvT0 u0
) , we have
1 + g−1min(g(u(t), λ̃(t))) Tu(t) 1− g−1ming(u(t), λ̃(t))Tu(t) ≥ √ 1− δ/8 + 1− δ/2√ 1− δ/8− 1 + δ/2 . (110)
This implies that g−1min(g(u(t), λ̃(t)))
Tu(t) ≥ 1− δ/2. (111) If ‖g(u(t),λ)‖2 = gmin, as the statements in Lemma 2 hold, we can compute that
‖g(u(t),λ)− g(u(t), λ̃(t))‖2 ≤ gminδ 4 = δ 4 ‖g(u(t),λ)‖2, (112)
which implies that ‖g(u(t), λ̃(t))‖2 ≤ (1 + δ/4)‖g(u(t),λ)‖2. (113)
Therefore, we have
v(t)Tu(t) = (g(u(t), λ̃(t)))Tu(t)
‖g(u(t), λ̃(t))‖2
≥ 1 1 + δ/4
(g(u(t), λ̃(t)))Tu(t)
gmin
≥1− δ/2 1 + δ/4 ≥ 1− 3 4 δ.
(114)
This leads to a contradiction. Analogously, we can show that for t ≥ ∑i j=1 Ti, we have ‖g(u(t),y/4)‖2 > g(i). Thus, by taking
t ≥ ∑p i=1 Ti, we have ‖g(u(t),y/4)‖2 > g(p) = gmax. However, from the definition of gmax, we have ‖g(u(t),y/4)‖2 ≤ gmax. This leads to a contradiction. Therefore, there exists a time T = ∑p i=1 Ti = O(log δ
−1) such that v(T )Tu(T ) ≥ 1− 34δ. We note that ‖g(u(T ),y/4)‖2 ≥ gmin. As the statements in Lemma (2) hold, we have
‖g(u(T ),y/4)− g(u(T ), λ̃(T ))‖2 ≤ δgmin
8 (115)
According to Lemma 7, we have∥∥∥∥∥ g(u(T ),y/4)‖g(u(T ),y/4)‖2 − g(u(T ), λ̃(T ))‖g(u(T ), λ̃(T ))‖2 ∥∥∥∥∥ 2 ≤ 2‖g(u(T ),y/4)− g(u(T ), λ̃(T ))‖2 gmin ≤ δ 4 .
(116)
This implies that
u(T )T g(u(T ),y/4)
‖g(u(T ),y/4)‖2
≥u(T )Tv(T )− ∥∥∥∥∥ g(u(T ),λ)‖g(u(T ),λ)‖2 − g(u(T ), λ̃(T ))‖g(u(T ), λ̃(T ))‖2 ∥∥∥∥∥ 2 ≥1− δ.
(117)
Hence, we have
cos∠(u(T ),g(u(T ),y)) = u(T )T g(u(T ),y)
‖g(u(T ),y)‖2 = u(T )T
g(u(T ),y/4)
‖g(u(T ),y/4)‖2 ≥ 1− δ.
This completes the proof.

heading: D.5 PROOF OF LEMMA 4
text: PROOF This is proved in Lemma 2 in (Phuong & Lampert, 2021). Here we provide an alternative proof. It is sufficient to prove for the case of local maximizer. Suppose that w is a local maximizer of yT (Xw)+ in B. We first consider the case where yT (Xw)+ > 0. If there exists n ∈ [N ] such that 〈w,xn〉 ≤ 0 and yn = 1. Consider v = xn/‖xn‖2 and let w =
w+ v ‖w+ v‖2 , where > 0. For index n ′ ∈ [N ] such that yn′ = 1, as the dataset is orthogonal separable, we have xTn′xn > 0 and
xTn′(w + v) = x T n′w + ‖xn‖2 xTn′xn > x T n′w. (118)
This implies that (xTn′w )+ ≥ (xTn′w)+. For yn′ = −1, as the data is orthogonal separable, we note that xTn′xn ≤ 0 and
xTn′(w + v) = x T n′w + ‖xn‖2 xTn′xn ≤ xTn′w. (119)
This implies that (xTj w )+ ≤ (xTj w)+. In summary, we have
yT (X(w + v))+ = N∑ n=1 yn(x T j (w + v))+ ≥ N∑ n=1 yn(x T j w)+ = y T (Xw)+ > 0 (120)
If 〈w,xn〉 < 0, then wTv < 0. This implies that with sufficiently small , we have ‖w + v‖2 < ‖w‖2 = 1. Therefore,
yT (Xw ))+ = 1
‖w + v‖2 yT (X(w + v))+ > y T (X(w + v))+ ≥ yT (Xw)+, (121)
which leads to a contradiction. If 〈w,xn〉 = 0, we note that (xTn (w + v))+ = > (x T nw)+. (122)
This implies that yT (X(w + v))+ ≥ yT (Xw)+ + . (123) We also note that ‖w + v‖2 = √ 1 + 2 = 1 +O( 2). Therefore, with sufficiently small , we have
yT (Xw )+ ≥ yT (Xw)+ + √
1 + 2 > yT (Xw)+. (124)
We then consider the case where yT (Xw)+ < 0. Apparently, we can make yT (Xw)+ larger by replacing w by (1− )w, where ∈ (0, 1), which leads to a contradiction. Finally, we consider the case where yT (Xw)+ = 0. This implies that∑
n:yn=1
(xTj w)+ = ∑
n:yn=−1 (xTj w)+. (125)
As (Xw)+ 6= 0, this implies that there exists at least for one index n ∈ [N ] such that yn = 1 and xTnw > 0. Let v = xn/‖xn‖2. We note that 1‖w+ v‖2 y
T (X(w + v))+ > 0 for > 0. This leads to a contradiction.

heading: D.6 PROOF OF PROPOSITION 7
text: It is sufficient to consider the case of the local maximizer. DenoteQ = {σ ∈ {−1, 0, 1}N |diag(σ) ∈ P}. For σ,σ′ ∈ Q, we say σ ⊆ σ′ if for all index n ∈ [N ] with σn 6= 0, σ′n = σn. We say σ ∈ Q is open if σn 6= 0 for n ∈ [N ]. Define
Sσ = {u|sign(Xu) = σ}. (126)
We start with the two lemmas.
Lemma 8 Let λ ∈ RN . Suppose that u0 satisfies that u0 = g(u0,λ)‖g(u0,λ)‖2 . Let σ = sign(u0). Then, v ∈ B2 is a local maximizer of λT (Xu)+ in B2 if for any open σ′ satisfying σ ⊆ σ′, we have ‖g(σ,y)‖2 = ‖g(σ′,y)‖2.
PROOF Suppose that σ is open. Then, Sσ is an open set. In a small neighbor around u0 = g(u0,λ) ‖g(u0,λ)‖2 = g(σ,λ) ‖g(σ,λ)‖2 , λ T (Xu)+ = u Tg(σ,λ) is a linear function of u. The Riemannian gradient of uTg(σ,λ) at v is zero. This implies that v locally maximizes λT (Xu)+.
Suppose that there exists at least one zero in σ. Consider any v ∈ B satisfying uT0 v = 0. Let > 0 be a small constant such that for any s ∈ (0, ], u0 + sv ∈ Sσ′ where σ ⊆ σ′. Let us = u+sv√1+s2 .
Suppose that ‖g(σ′′,λ)‖2 ≤ ‖g(σ,λ)‖2 for all open σ′′ satisfying σ ⊆ σ′′. For any σ′ with σ ⊆ σ′, we construct σ′′ by σ′′i = −1 for n ∈ [N ] such that σ′n = 0 and σ′′n = σ′n for n ∈ [N ] such that σ′n = 0. We note that ‖g(σ′′,λ)‖2 ≥ ‖g(σ′,λ)‖2. Thus, ‖g(σ′,λ)‖2 ≤ ‖g(σ′′,λ)‖2 ≤ ‖g(σ,λ)‖2. As |λT (Xus)+| = |g(σ′,λ)Tus| ≤ ‖g(σ′,λ)‖2, we have |λT (Xus)+| ≤ ‖g(σ′,λ)‖2 ≤ ‖g(σ,λ)‖2. Therefore, u is a local maximizer of λT (Xu)+.
Lemma 9 Suppose that the dataset is orthogonal separable. Let λ ∈ RN satisfy that diag(y)λ ≥ 0. Suppose that u0 satisfies that u0 =
g(u0,λ) ‖g(u0,λ)‖2 . Then, for any σ ′ satisfying σ ⊆ σ′, we have ‖g(σ′,λ)‖2 = ‖g(σ,λ)‖2.
PROOF If there exists n ∈ [N ] such that σn = 1 and yn = −1, as the data is orthogonal separable, we note that
xTng(σ,λ) = x T n  ∑ n′:σn′>0 λn′xn′  = yn(ynxn)T  ∑ n′:σn′>0 (λn′yn′)yn′xn′  ≤ 0, (127) which contradicts with sign(xTng(σ,λ)) = sign(x T nu0) = σn = 1.
Suppose that there exists n ∈ [N ] such that σn and yn = 1. Then, as the dataset is orthogonal separable, then, for index n1 ∈ [N ] such that σn1 = 0, we note that yn1 6= 1. Otherwise,
xTn1g(σ,λ) = x T n1  ∑ n2:σn2>0 λn2xn2  = xTn1  ∑ n2:σn2>0 (λn2yn2)yn2xn2  > 0, (128) which contradicts with sign(xTn1g(σ,λ)) = sign(x T n1u0) = σn1 = 0. This also implies that the index set {n ∈ [N ]|σn > 0} include all data with yn = 1. If there exists σ′ such that σ ⊆ σ′ and ‖g(σ′,λ)‖2 > ‖g(σ,λ)‖2. Then, there exists at least one index n ∈ [N ] such that σn ≤ 0 and σ′n = 1. However, from the previous derivation, we note that yn = −1 and
xTng(σ ′,λ) = xTn  ∑ j:σ′n1 >0 λn1xn1  = xTn  ∑ n1:σ′n1 >0 (λn1yn1)yn1xn1  < 0, (129) which contradicts with σ′n = 1.
By combining Lemma 8 and 9, we complete the proof.

heading: D.7 PROOF OF THEOREM 4
text: PROOF For almost all initialization, we can find two neurons such that sign(w2,i+) = sign(yT (Xw1,i+)+) = 1 and sign(w2,i−) = sign(y
T (Xw1,i−)+) = −1 at initialization. By choosing a sufficiently small δ > 0 in Proposition 6, there exist two neurons w1,i+ ,w1,i− and times T+, T− > 0 such that cos∠(w1,i+(T+),g(w1,i+(T+),y)) > 1 − δ and cos∠(w1,i+(T+),g(w1,i+(T+),y)) < −(1− δ). This implies that w1,i+(T+) and w1,i−(T+) are sufficiently close to certain stationary points of gradient flow maximizing/minimizing yT (Xu+) over B, i.e., {u ∈ B| cos(u,g(u,y)) = ±1}. As the dataset is orthogonal separable, according to Lemma 4 and Proposition 7, the corresponding diagonal matrices D̂i+(T+) and D̂i−(T−) satisfy that D̂i+(T+) ≥ diag(I(y = 1)) and D̂i−(T−) ≥ diag(I(y = −1)). According to Lemma 3 in (Phuong & Lampert, 2021), we have D̂i+(t) ≥ diag(I(y = 1)) and Di−(t) ≥ diag(I(y = −1)) hold for t ≥ max{T+, T−}. With t → ∞, according to Proposition 4, the dual variable λ in the KKT point of the non-convex max-margin problem (15) is dual feasible, i.e., λ satisfies (18). Suppose that θ∗ is a limiting point of {
θ(t) ‖θ(t)‖2 } t≥0 and λ∗ is the corresponding dual variable. From Theorem 1, we note that the pair
(θ∗,λ∗) corresponds to the KKT point of the convex max-margin problem (16).

heading: E PROOFS OF MAIN RESULTS ON MULTI-CLASS CLASSIFICATION

heading: E.1 PROOF OF PROPOSITION 1
text: The neural network training problem (5) can be separated into K subproblems. Each of these subproblems corresponds to the neural network training problem (4) for binary classification. For each subproblem, by applying Proposition 2, we complete the proof.

heading: E.2 PROOF OF THEOREM 1
text: We note that the neural network training problem (5) can be separated into K subproblems. Each of these subproblems corresponds to the neural network training problem (4) for binary classification. By applying Proposition 6 with to each subproblem with y = yk, we complete the proof.

heading: E.3 PROOF OF THEOREM 2
text: Similarly, the corresponding non-convex max-margin problem (6) and the convex max-margin problem (8) can be separated into K subproblems. Each of these subproblems corresponds to the nonconvex max-margin problem (2) and the convex max-margin problem (16) for binary classification. By applying Theorem 4 to each subproblem with y = yk, we complete the proof.

heading: F NUMERICAL EXPERIMENT

heading: F.1 DETAILS ON FIGURE 5
text: We provide the experiment setting in Figure 1 and 5 as follows. The dataset is given by X =[ 1.65 −0.47 −0.47 1.35 ] ∈ R2×2 and y = [ 1 −1 ] ∈ R2. Here we have N = 2 and d = 2. We note that this dataset is orthogonal separable but not spike-free. We plot the ellipsoid set and the rectified ellipsoid set in Figure 6.
We enumerate all possible hyperplane arrangements in the set P and solve the convex max-margin problem (16) via CVXPY to obtain the following non-zero neurons
u1,3 = [ 0.58 −0.16 ] , w′1,2 = [ −0.23 0.66 ] . (130)
We note that the dual problem (17) is equivalent to
max λTy,
s.t. ‖XTDjλ−XT (2Dj − I)zj,+‖2 ≤ 1,∀j ∈ [p], ‖ −XTDjλ−XT (2Dj − I)zj,−‖2 ≤ 1,∀j ∈ [p], zj,+ ≥ 0, zj,− ≥ 0,∀j ∈ [p],diag(y)λ ≥ 0.
(131)
The above problem is a second-order cone program (SOCP) and can be solved via standard convex optimization frameworks such as CVX and CVXPY. We solve (131) to obtain the optimal dual variable λ. For the geometry of the dual problem, as the dataset is orthogonal separable, the set {λ : max‖u‖2≤1 |λ T (Xu)+| ≤ 1} reduces to {λ : max‖u‖2≤1 |λ T (Xu∗1)+| ≤ 1,λ
T (Xu∗2)+| ≤ 1}, where u∗1,u∗2 correspond to two vectors at the spikes of the rectified ellipsoid set. We draw the sets {λ : max‖u‖2≤1 |λ
T (Xu)+| ≤ 1}, {λ :, the optimal dual variable λ and the direction of y in Figure 2.
For each Dj ∈ P , we solve for the vector uj which maximize/minimize λTDjXuj with the constraints ‖uj‖2 ≤ 1 and (2Dj − I)Xuj ≥ 0. We plot the rectified ellipsoid set {(Xu)+|‖u‖2 ≤ 1}, vectors uj , neurons in the optimal solution to (16) scaled to unit `2-norm and the direction of λ in Figure 1. We note that each neuron u∗j in the optimal solution from (16) (scaled to unit `2-norm) maximize/minimize the corresponding λTDjXuj given (2Dj − I)Xu∗j ≥ 0. Then, we consider a two-layer ReLU network with m = 10 neurons and apply the gradient descent method to train on the logistic loss (4). Let ŵ1,i =
w1,i ‖w1,i‖2 for i ∈ [m]. We plot ŵ1,i and (Xŵ1,i)+
at iteration {10l|l = 0, . . . , 4} along with neurons in the optimal solution to (16) scaled to unit `2-norm in Figure 5. Certain neurons do not move, while the activated neurons trained by gradient descent tend to converge to the direction of the neurons in the optimal solution to (16).
We repeat the training on the logistic loss (4) with the gradient descent method several times and we plot the trajectories in Figure 7.

heading: F.2 EXPERIMENT ON SPIKE-FREE DATASET
text: We repeat the previous numerical experiment on a non-spike-free dataset: X = [ 1.65 0.47 0.47 1.35 ] ∈
R2×2 and y = [ 1 1 ] ∈ R2. Similarly, we plot the ellipsoid set and the rectified set in Figure 8.
We enumerate all possible hyperplane arrangements in the set P and solve the convex max-margin problem (16) via CVXPY to obtain the following non-zero neuron
u1,4 = [ 0.43 0.59 ] (132)
We plot the rectified ellipsoid set {(Xu)+|‖u‖2 ≤ 1}, vectors uj , neurons in the optimal solution to (16) scaled to unit `2-norm and the direction of λ in Figure 9. We also plot ŵ1,i and (Xŵ1,i)+ at iteration {10l|l = 0, . . . , 4} along with neurons in the optimal solution to (16) scaled to unit `2-norm in Figure 10.

Review summaries:
The paper studies the subgradient flows when training a two-layer ReLU neural network. To this end, the non-convex max-margin problem is reformulated as a convex optimization problem. The authors then analyze the dual extreme points of the convex formulation and show the implicit regularization of unregularized gradient flow as convex regularization. Then, for the binary classification problem, it is proven that the KKT points of the non-convex max-margin problem correspond to the KKT points of the convex max-margin problem if the direction is dual feasible. The paper then demonstrates that this is the case under some conditions on spike-free matrices and orthogonal separable data. Finally it is shown that if the dataset is orthogonal separable and initialized sufficiently close to zero, the limiting point of the gradient flow is the global minimizer of the max-margin problem.