The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program
Authors: Yifei Wang
Mert Pilanci
Venue: ICLR 2022 Poster (2022)
Keywords: Two-layer ReLU networks
convex optimization
convex duality
gradient flow

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.

Published as a conference paper at ICLR 2022
THE CONVEX GEOMETRY OF BACKPROPAGATION: NEURAL NETWORK GRADIENT FLOWS CONVERGE TO EXTREME POINTS OF THE DUAL CONVEX PROGRAM
Yifei Wang
Mert Pilanci
Department of Electrical Engineering Stanford University Stanford, CA 94305, USA wangy f1 @ew.ff8@etaaffd..oommo
Department of Electrical Engineering
Stanford University Stanford, CA 94305, USA
#llanci@stanfoon
ABSTRACT
We study non-convex subgradient flows for training two-layer ReLU neural net- works from convex geometry and duality perspective. We characterize the implicit bias of unregularized non-convex gradient flow as convex regularization of an equiv- alent convex model. We then show that the limit points of non-convex subgradient flows can be identified via primal-dual correspondence this convex optimization problem. Moreover, we derive sufficient condition 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, show that this sufficient condition holds. Therefore, non-convex gradient flows converge to optimal solutions of convex optimization problem. We present numerical results verifying the predictions of our theory for non-convex subgradient descent.
INTRODUCTION
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, veee-parameterization and the associated highly nonconvex training problem makes their theoretical analysis quite challenging.
In weeepparameterized models such as NNs, natural question arises: Which particular solution does gradient descent/gradient flow find in unregularized NN training problems? Suppose that X E Nd the training data matrix and y {1, 11] is the label vector. For linear classification problems such as logistic regression, is known that gradient descent (GD) exhibits implicit regularization properties, see, e.g., (Soudry al. 2018: Gunasekar al., 2018). To be precise, under certain assumptions, GD converges to the following solution which maximizes the margin:
arg min w WERd
/// s.t. yn ynw' x, 2 1, E [N].
(I)
Here denote [N] (1,..,, NJ. Recently, there are several results the implicit regularization of the (stochastic) gradient descent method for NNs. In (Lyu & Lij 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 1001: s.t. (0; 2 1, E [N],
where f(0: x) represents the output of the neural network with parameter @ given input x. In (Phuong & Lampert 20221. }. by further assuming the orthogonal separability of the training data, it is shown that 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.

---

Published as a conference paper at ICLR 2022
However, the max- mar-ma problem of the neural network 2 is 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 saddle point. In other words, the global optimality is not guaranteed.
In a different line of work (Pilanci & Ergen 2020 Ergen & Pilanci, 2020; 202Ib), exact convex optimization formulations of two and three-layer ReLU NNs developed, which have global optimality guarantees in polynomial-ting arrangements, e.g., in any fixed dimension or with convolutional networks of fixed filter size. The convex optimization framework was extended to vector output networks (Sahiner et al. (021b). quantized networks (Bartan & Pilanci (021b), autoencoders (Sahiner et al. [021c] Gupta al.) 202T), networks with polynomial activation functions (Bartan & Pilanci| (021a). networks with batch normalization (Frgen et al. 202T), univariate deep ReL.U networks, deep linear networks (Ergen & Pilanci 2021c) and Generative Adversarial Networks (Sahiner et al. (221aa)
when the data has a polynomial number of hyperplane
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 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 mar-margin problem. For certain regular datasets including orthogonal separable data, 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.
1.1 RELATED WORK
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 dynamies in training two-layer ReLU networks for regression problems. Ma et al.] (2020) show that for two-layer ReLU networks, only group of 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. [i et al. (2020) focus 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 al. (021), it is shown that mildly over- over-parann parameterized student network can learn the teacher network and all student neurons converge to one of the teacher neurons.
Beyond (yu & Li 2019) and (Phuong & Lampert (021). the following papers study the classification problems. In (Chizat& Bach, 2018), under certain assumptions on the training problem, with over- parameterized 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. (202T) 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.
1.2 PROBLEM SETTING
We focus on two-layer neural networks with ReLU activation, i.e., f(0,x) = (XW 1)4 w2, where Wi E Rdxmm W2 E IRm and 0 = (W1, W2) represents the parameter. Due to the ReLU activation, this neural network is homogeneous, i.e., for any scalar >> O, we have f(c0; X) c² (0: The training problem is given by
N
min
(0::
(3)
where E(g): IR + R, is the loss function. We focus on the logistic, i.c, cross-entropy loss, i.c. ((g)) = log(1 + +eep(=9))
2

---

Published as a conference paper at ICLR 2022
Then, we briefly review gradient descent and gradient flow. The gradient descent takes the update rule 0 + 1) 0(() - (())((),
where g(t) 8 ((((t)) and 0 represents the Clarke's s subdifferential.
The gradient flow can be viewed as the gradient descent with infinitesimal step size. The trajectory of the parameter 0 during training is an are 0 [0, +-0) + O, where Q {0 = (W1, w2)[W1 R W2 E IR." More precisely, the gradient flow is given by the differential inclusion
dt - for 0, almost everywhere.
2
MAIN RESULTS
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 with K classes. Suppose that y [K] the label vector. Let (yn,k)ne(N))kel E R. Nx be the encoded label matrix such that
1,
if Jn = k, otherwise.
Vn,
1,
Similarly, we consider the following two-layer vector-output neural networks with ReLU activation:
x1(01.
(XW(I))
F(O,X)
[k(0k, X)
(XW(K)) w22 (K)
where we write θ (.),..., 0k). For h: I..... K. we have 02 (w(
2 where
w(1)) E Nxm and wa (k) E _ One can view each of the K outputs of F(O, X) as the output of two-layer scalar-output neural network. Consider the following training problem:
K
mii
Eyyn,k (Ox, x.)).
(4)
A m
According to (Lyu & Li 2019), the gradient flow and the gradient descent finds stationary point of the following non-convex max margin problem:
K
arg min
Σ
10x 12,
s.t.
1, [M] E [K].
(5)
l=
Denote the set of all possible hyperplane arrangement as
p = (diag([(XV 2 0))/w E ER).
and let [P]. We can also write p = .D, Dp). From (Cover 1965 we have an upper
bound p < 2r c((N1))) where r = (an) We first reformulate 5 convex optimization.
Proposition 1
The non-convex problem 5 equivalent to the following conver program
K
ΣΣ (1lu,ull2 + ||4/,0l22)
min
k=1
s.t. diag(y:)
Σ D,X(UjA u', 2
(2D, 1 I)Xu,, 2 2, I)Xu', 2 0, [p), [K].
where Yk the k-th column of Y. The dual problem of given by max tr(ATy)
(8)
diag (y
max
A X w 1,k (K).
||w willa1
where De is the kith column of A.
3

---

Published as a conference paper at ICLR 2022
We present the detailed derivation of the convex formulation 7 and its dual problem 8 in the appendix. Given E R", we define (uu) = diag > +)). For two vectors u, V E R we define the cosine angle between and by cos L(u, v) ||u u"v
2.1 OUR CONTRIBUTIONS
The following theorem illustrate that for neurons satisfying sign(y (Xw ((1)))) = sign (12,) at initialization, w align to the direction of D(W (k) y at a certain time T, depending on sign( W2 2 at initialization. In Section 2.3, we show that these are dual extreme points of 7
(k)
Theorem Consider the K K-class classification training problem 4 for any dataset. Suppose that
the neural network is scaled at initialization such that [wi, ll (h) I E [mi] and E [K].
Assume that at initialization, for E [K], there exists neurons (w 1.14 2,4x such that
(k)
sign(yk (Xw (Xw1.)) =ignn)
(k)
where: 8 E (1,- Consider the subgradient flow applied to the non-convex problem (4) Let
5 E (0, 1). Suppose that the initialization is sufficiently close the origin. Then, for k [K]. there exist T = T(ô, k) such that
(k) cos L (w (T), sX sX" D(w i (T))&a) -.
Next, we impose conditions the dataset to prove a stronger global convergence results the flow. We say that the dataset (X, y) is orthogonal separable among multiple classes for all n, n' E [N],
x Xn. 0, if Un Dn'
X S O, if Fn * Dn.
For orthogonal separable dataset among multiple classes, the subgradient flow for the non-convex problem 4 can find the global optimum of (5) up to scaling constant.
Theorem Suppose that (X. E Nxd x [K] is orthogonal separable among multiple classes. Consider the non-convex subgradient flow applied the non-convex problem (4). Suppose that the
initialization is sufficiently close to the origin and scaled as in Theorem 7 Then, the non-convex subgradient flow converges the global optimum of the convex program and hence the non-convex objective (5) up to scaling.
Therefore, the above result characterizes the implicit regularization of unregularized gradient flow convex regularization, i.e., group & norm, in the convex formulation ( is remarkable that group sparsity is enforced by small initialization magnitude with explicit form of regularization.
2.2 CONVEX GEOMETRY OF NEURAL GRADIENT FLOW
Suppose that À e N. Here we provide an interesting geometric interpretation behind the formula
cos (1, X D()AA > -
which deseribes a dual extreme point to which hidden neurons approach to as predicted by Theorem D We now explain the geometric intuition behind this result. Consider ellipsoid (Xu : | S 1}. A positive extreme point of this ellipsoid along the direction is defined by
Next, we consider the rectified ellipsoid set Q = ((Xu)+ ||u||2 & 1} introduced in (Ergen & Pilanci 2021a) and shown in Figure The constraint max iaax://uul.s1 (Xu))))+ < 1 on À is equivalent to À E Q*. Here Q is the absolute polar of Q, which appears as a constraint in the convex program and is defined as the following convex set
arg max || XXu, which is given by the formula
x X
Q ( max A Z < 1}. ZEQ
(10)
4

---

Published as a conference paper at ICLR 2022
An extreme point of this non-convex body along the direction X is given by the solution of the problem
max X = max DjEP u: | -1)
max
A Xu Xu.
(11)
Here, (A, u) are primal-dual pairs as they appear in the convex dual program 8 First, note that
stationary point of gradient flow on the objective in (1I) is given by the identity cu E (X))
where is constant. particular, by picking the zero the subgradient of (x", u)+ when X
DX'D(uAA22 = Em X (u' x, 0)
X'D(u)A
u
(12)
I1 1 X, (u'x, 0)1
Note that the formula cos L(u, X'D())A) > 1- appearing in Theorem shows that gradient flow reaches the extreme points of projected ellipsoids (D,Xu ||u||2 I 1] in the direction of X yk. where Dj E P corresponds to a valid hyperplane arrangement. This interesting phenomenon is projected ellipsoids.
depicted in Figures and The one-dimensional spikes in Figures[]
Detailed setup for Figure to and additional experiments can be found in Appendix F
2.0
optimal
y'u
max DAT I
1.5
maximal
minimal
1.5
optimal
daptyM
(Kw)))-
1.0
1.0
0.5
-0.5
0.0
-1.0
-0.5
-1.5
-1.0
-0.5
0.0
0.5
1.5
2.0
-20
-1.5
-1.0
-0.5
0.0
0.5
1.0
2.5
2.0
Figure 1: Rectified Ellipsoid Q := {(Xu)+
Figure 2: Convex absolute polar set Q" of the Rectified Ellipsoid (purple) and other dual constraints (grey).
Ju/l2 < }} and its extreme points (spikes).
2.00
optimal A
1.
ylu-0
trained (XmL)).
(Xw,).1
1.50
cone boundary
nouron
2.25
3-th neturon
néuurnn
neturn
0.0
6-th neuron
0.75
neuron
9-th neuron
0.50
optimal neuron
0.00
-1.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
-1.0
-0.5
0.0
0.5
1.0
Figure 3: Trajectories of (Xw1,s) along the training dynamics of gradient descent.
Figure Trajectories of W1,i [w]. along the training dynamics of gradient de- scent.
Figure 5: Two-layer ReLU network gradient descent dynamics on an orthogonal separable dataset. is the normalized vector of the i-th hidden neuron in the first layer.
W1,1 |w
5

---

Published as a conference paper at ICLR 2022
3 CONVEX MAX-MARGIN PROBLEM
In this section, we consider the equivalent convex model of the max-margin problem and its optimality conditions. We primarily focus 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 11? + ([w2))), S.I. ((W W2 21,
(13)
where Y = dy. 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 neural network, we can provide a convex optimization formulation of (3) and derive the dual problem.
Proposition 2 The problem
(33 is equivalent to
Pd cvx min
(||u 112 + 112)
P
(14)
s.t. Y Σ D, ( uuj) 2 1,
j=1
(2D - Xu 2 (2D, - 1)Xu 2 0j e lp.
The dual problem of (14) is given by
D max y S.S. S. YAZ 0,
A
u u)+1 S 1.
(15)
u: ullas
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
Proposition 3 Let (W1, W2, X) be a KKT point of the non-convex max-margin problem 2 (in terms of B-subdifferential) Suppose that W2,i for certain i [m.) Then, there exists diagonal matrix D. NN satisfying
(D.), = 1, for x, W1 > 0,
(D:), E (0. 1}, for xx, W1,1 0,
(D:), 0, for x W1,1 O.
such that
W1,1 = D' X 1.
W2.1
Based on the characterization of the KKT point of the non-convex max-mas max-margin problem 2 we provide an equivalent condition to ensure that also the KKT point of the convex max-margin problem (14).
Theorem
terms of B-subdifferential) The KKT point of the non-convex max max-maarin problem 13
corresponds KKT point of the convex max-margin problem 14
X is dual feasible, i.e.,
max
(
(16)
wl|lu||a11
This condition is equivalent to for all D, E the dual variable À satisfies that
max (2D, (2D,, 1jx20
AT $1
(17)
3.1 DUAL FEASIBILITY OF THE DUAL VARIABLE
A natural question arises: is it possible examine whether À is feasible in the dual problem? We say the dataset (X,y) is orthogonal separable if for all n' E [N].
x Xm. > 0, if yn = yn'
X X < 0, if yn # yn'

---

Published as a conference paper at ICLR 2022
For orthogonal separable data, long the induced diagonal matrices in Proposition cover the positive part and the negative part of the labels, the KKT point of the non-convex max- maxx-nargin problem (2) is the KKT point of the convex max margin problem (14).
Proposition 4 Suppose that yX is orthogonal separable. Suppose that the KKT point of the non- convex problem include two neurons (W1.i-: W2,6.) and (W1.t_ (2,1 such that the corresponding diagonal matrices Di, and D:_ defined in Proposition satisfy that
D. diag(T(y = 1)), D diag(T(y -1))
Then, the dual variable X is dual feasible, i.e., satisfying (16).
The spike-free matrices discussed (Ergen & Pilanci 202 also makes examining dual feasibility of X easier. The definition of spike-free matrices be found in Appendix
Proposition 5 Suppose that X is spike-free. Suppose that the KKT point of the non-convex problem include two neurons (Wi,s)> W2,i ) and (Wi,i W2,, such that the corresponding diagonal matrices Di, and D._ defined in Proposition satisfy that
D. diag(I(y 1)), diag(1y -1)).
Then, the dual variable À is dual feasible, i.e., satisfying (16).
Remark For the spike-free data, the constraint on the dual problem is equivalent to
max Xuzo.|uul251
A2Xul S 1,
equivalently
max Xu20,Ijulas
XYY Xu <1,
min Xuzi
A Xu 2 -1
4 SUB-GRADIENT FLOW DYNAMICS OF LOGISTIC LOSS
In this section, we consider the following sub uub-gradient flow of the logistic loss
(1, (t)
Σ
)m(()x((1)
01
(()) x..0
(18)
0
N (1) = Σ (0))((
W2,
Øt
where the n-th entry of x()) R.N is defined
Ån =
yn (gn), 4n = Un W1)+ w)++2. W2-
(19)
For simplicity, we omit the term (t). For instance, we write W1,i = w1,(t). To be specific, when w Xn, = O, we select 0 as the subgradient of w2, (wT,(T with respect to W1,t Denote a: = sign Xu,). For a N we define
g(o X)
Σ Annn.
(20)
For simplicity, also write
g(u, X) == gssign(Xu):
Σ Anxn.
(21)
new, >0
Then, can rewrite sub-gradie gradient flow of the logistic loss 3 as follows:
i W.1 = (2 X).
at W = - X)
(22)
ät
Assume that the neural network scaled at initialization, i.e., (w) = =w3,(0) for E [m]] Then, the neural network is scaled for f.

---

Published as a conference paper at ICLR 2022
Lemma Suppose that |w1,,(0)|lz |w2,(0) for i E [m]. Then, for any 0. we have [t1,:(t)l22 = [t), > 0.
According to Lemma for all 2 0, sign sign(u2,((t)) = sign(wp, 2, (0)). Therefore, we can simply
write 8; (t) = sign W2,2 (f)) As the neural network is scaled for 2 0, it is interesting study
the dynamics of w in the polar coordinate. We write W1,a(t) e (t), where ||u:())l2 1. The gradient flow in terms of polar coordinate writes
a 0t ri
i ōt u, st (g(u, u g(u, X)) u.)
u g(u, X)
(23)
Let Tmax
max
|x: 1|2 Define gmin to be
Imin
min 0c
|g(o. 2/4)l2,, s.t. g(o.y/4) #0, where we denote
(24)
fo (1.0. (1.0.-13% =
(25)
As the set Q
S (1, 1,, is finite, we note that Imin >> O. We note that when max |ral < 0, we have Ā xs Y The following lemma shows that with initializations sufficiently close to 0, (lg(u()), (()) g(u((), y /4)ll2 and 4 g(u((), X(OO|/ ((())())())) can be very small.
4.
follows Lemma 2 Suppose that T O and 5 > 0. Suppose that (u(I), ((()) follows the gradient flow (23
with 8 = 1 and the initialization u0) = un and r(0) = vo. Suppose that vo is sufficiently small.
Then, the following two statements hold.
For all S T, we have (lg((((), ((1) g(u((), S Qmind
For S such that sign(Xu(s) is constant in a small neighbor of 1, we have L
d {g(((((,X(1))
Based on the above lemma on the property of g(((),, A(t)), we introduce the following lemma to upper-bound the time such that cos g(u()),(((t), A(t))) approaches - or sign(Xu(t)) changes.
Lemma Let 5 E (0, Suppose that un satisfies that || 12 = 1 and ( (Xu))+ > 0. Suppose that (u(t),r(t)) follows the gradient flow (23) with 1 and the initialization u(0) uo and ((())
r(0) To- Les v(t) ((0(i())
We write vo v(0), au (0)) and go lg y/4)
Denote
VI 5/8 + 8
v - 5/8 + vo up
T
log
log
(26)
2go / I 6/8
VI 8/8 - 1 V1 6/8 - vă un
For c E (0, - 5). define
1
VI 6/8 +
/ 0/8 v uo
Tehift (c)
log
v1 5/8 llog
(27)
2go / 8/8
V1 5/8 v/ uo
Suppose that ro 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 time T such that we have sign(Xu(t)) sign (un)) for E (0.T) and sign(Xu(()) * sign(X (ugn( Let u, = u(T) and = lim v(l). If uf < 8, then the time T satisfies that < Trehiit (vf un). Otherwise, there exists a time T satisfying T < T,,, such that have sign(Xu(t)) u(I')Tv(T))
sign(Xuo) for t E [0,T"] and
There exists a time < T such that we have and u(T)) v(T) 8.
= sign(Xu,) for [0,
8

---

Published as a conference paper at ICLR 2022
Corollary
Suppose that there exists a time sign(Xuo) for E ()) and sign(Xu((t)
T such that have sign (u(t)) * sign(Xuo). If T >
Tshitt (vl u1) =
log V V1-5/8tv5u log v VI-A/8+v] un
then, we have uf Un >
g0 go 1-88
V1-
VI- vo ue
Proposition 6 Consider the sub- bub-gradient flow (3 with & s= and the initialization u(0) = un and r(0) ro- Here initilization the neuron Ug satisfies that ||uoll2 1 and y" (Xug)+ > Let For any ô for sufficiently small ro, there exists time T (1ogg(011)
v() (ls(((t) X(1) l
g(m()).X())
such that (T)) vT) 2 5 and cos L(u(T), g(u(T),))) 1
Remark The statement of proposition is similar to Lemma in (Maennel al. 2018). However, their proof contains 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.
We next study the properties of orthogonal separable datasets. Denote B (w E Rd The following lemma give a sufficient condition
|wl]2 S 1}.
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 y" (Xw)+ +. in B and + + O. Then, (w, xa) > 0 for n E [N] such that yn 1. Suppose that E B is local minimizer of yd (Xw)= in B and (Xw)+ o 0. Then, (w, Xn) > 0 [N]
such that Yn -1
We show an equivalent condition of u E B being the local maximizer/minimizzee of y (Xu)+ in B. Proposition 7 Assume that (X, y) is orthogonal separable. Then, u E B is a local maximizer of y (Xu)+ + in B is equivalent to cos / Luu, g(u, y)) 1. Similarly, E B is local minimizer of (Xu)) in B is equivalent cos / (u, g(u. = 11
Based on Proposition and we present the main theorem.
Theorem Suppose that the dataset orthogonal separable and 0(t) follows the gradient flow.
Suppose that the neural network is scaled at initialization, i.e., ||w1,: = (0) all i [m]]
For almost all initializations which are sufficiently close to zero, the limiting point of [0(O]la To lla where 0* is a global minimizer of the max-margin problem
0(t) is gr
We present sketch of the proof. According to Proposition 6 for initialization sufficiently close to zero. there exist two neurons and time T4, T_ such that cos Z(W1.i, (T+), ((W1,._ (T+ ). y))
and cos <(W1,;_ (T-). (F-).g(w)) ((W1,i. (T-), < -(1 - 5). This implies that W1,1, (T+) and W1,i (T+) are sufficiently close to certain stationary points of gradient flow maximizing/miniman
(Xu,)
over B, i.e., {u E B| cos( (u, g(u, y)) = =1}. As the dataset is orthogonal separable, from Proposition and Lemma the induced masking matrices D),, (T+) and D=(TT) by W1,1, (/t,),1,. (T-) in Proposition 3 satisfy that D (T,)) 2 diag([(x>
1)) and D,_ (T-) diag(I(y -1))
According to Lemma 3 in (Phuong & Lampert 2021). ) for t 2 Mnx{T_,T_L [T]..w we also have D., (t) 2
diag(I(y 1)) and D (t) 2 diag -1). According Theorem 3 and Proposition 4 the KKT point of the non-convex problem (2) that gradient flow converges to corresponds to the KKT point of the convex problem (14).
CONCLUSION
We provide 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 the training data, show that flows converge to KKT points of the convex max-margin problem, hence a global optimum of the non-convex objective.
6 ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under grants ECCS-203732 DMS-2134248, and US Army Research Office.

---

Published as a conference paper at ICLR 2022
REFERENCES
Burak Bartan and Mert Pilanci. Neural spectrahedra and semidefinite lifts: Global convex op- timization of polynomial activation neural networks in fully polynomial-time arXiv preprint arXiv:2101.02429, 2021a.
Burak Bartan and Mert Pilanci. Training quantized neural networks to global optimality via semidefi- nite programming. International Conference on Machine Learning (ICML), 2021, 2021b.
Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in Neural Information Processing Systems, 31:3036- 3046, 2018.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions electronic computers, (3:326-3334 1965.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of enn architectures: Convex optimization of two-and three-layer networks in polynomial time. International Conference Learning Representations (ICLR), 2020.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterrized neural networks. Journal of Machine Learning Research, 22(212): 2021a.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks convex programs. International Conference on Machine Learning, pp. 2993-3003. PMLR, 2021b.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference Machine Learning, pp. 3004-3014. PMLR, 2021c
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Demys- tifying batch normalization in relu networks: Equivalent convex optimization models and implicit regularization. arXiv preprint 2 2021.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832-1841. PMLR, 2018
Vikul Gupta, Burak Bartan, Tolga Ergen, and Mert Pilanci. Exact and relaxed convex formulations for shallow neural autoregressive models. In International Conference on Acoustics, Speech, and Signal Processing, 2021.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on Learning Theorr, pp. 2613-2683 PMLR, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogencous neural networks. arXiv preprint arXiv: 1906v:1906.05886 058900 2019.
Chao Ma, Lei Wu, and Weinan F. The saannchinn--ciiaationn behavior of the gradient descent dynamics for two-layer neural network models. arXiv preprint arXiv:2006.14450. 2020.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient descent quantizes relu network features. arXiv preprint arXiv: 083667 2018.
Song Mei, Andrea Montanari, and Phan- Phan-Minh Nguyen. mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences. (16555).7666--7777,, 2018.
Mary Phuong and Christoph H Lampert. The inductive bias of relu networks on orthogonally separable data. 2021.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial time convex optimization formulations for two-layer networks. pp. 7695-7705, 2020.
10

---

Published as a conference paper at ICLR 2022
Arda Sahiner, Tolga Ergen, Batu Ozturkler, Burak Bartan, John Pauly, Morteza Mardani, and Mert Pilanci. Hidden convexity wasserstein gans: Interpretable generative models with closed-form solutions. arXiv preprint arXtv:2107.05680. 2021a.
Arda Sahiner, Tolga Ergen, John Pauly, and Mert Pilanci. Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-tine algorithms. International Conference on Learning Representations (ICLR), 2021b.
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John Pauly. Convex regularization behind neural reconstruction. International Conference Learning Representations (ICLR), 2021c.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Gang Wang, Georgios B Giannakis, and Jie Chen. Learning relu networks on linearly separable data: Algorithm, optimality, and generalization. IEEE Transactions on Signal Processing, 67(9):
2357-23707 2019.
Qiuling Yang, Alireza Sadeghi, Gang Wang, and Jian Sun. Learning two-layer relu networks is nearly as easy as learning linear classifiers on separable data. IEEE Transactions on Signal Processing, 69:4416-4427, 2021.
Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over-paramettrized two-layer neural network. arXiv preprint arXiv:2102.02410 02410, 2021.

---

Published as a conference paper at ICLR 2022
A
DEFINITIONS AND NOTIONS
We introduce several useful definitions and notions which will be utilized in the proof.
A.1 DEFINITIONS
Definition Let In be an open set and let F O + R be locally Lipschitz continuous at O. Let Dr be the differentiable points of F in O. The B-subdifferential of F at is defined by
FBF())
lim F'(x")/x* e Dr, 2k - 3 K-
(28)
The set 8 F(x) (()) is called Clarke's subdifferential, where denotes the convex hull.
Definition A matrix is spike-free if and only if the following conditions hold: for all | S 1,
there exists | S such that
(Au)+ Az.
(29)
This is equivalent to say that
max
X (Xu)+Il2 I 1.
(30)
w: U (Xu)_=0
A.2 NOTIONS
We use the following letters for indexing.
The index n for the n-th data sample X,-
We use the index to represent the i-th neuron-pair (W1,1, W2,1).
The index is for the j-th masking matrix D2 E
B PROOFS IN SECTION
B.1 PROOF FOR PROPOSITION
Consider the following loss function 7: R. x R + RRU
[0,
Un 2 vn E [N], otherwise.
E(z,y)
(31)
+ 00,
For given y {1, (1,-1) yl, is convex loss function of z. The non-convex max-margin is equivalent to
1 ([W) |1 + l|2
min T(XW))) W2, y)
(32)
2
According to Appendix A.13 in PPilanci & Ergen 2020), the problem 32) is equivalent
min Σ
D,X( u.).y
(I|W |[wa11))
(33)
s.t. (2D; I)uu; (2D: I)Xu, 0, Vi [p].
This is equivalent to 14 For fixed E N the Fenchel conjugate function of ε(z,y) with respect can be computed by
1" ((, = max z" x ((zzy)
zERN
max 2 TT X, s.t. diag(y) jz 2 1, ZERA
(34)
Ty
diagly) < 0 + oc, otherwise.
12

---

Published as a conference paper at ICLR 2022
According to Theorem 6 in PPilanci & Ergen 2020), the dual problem of (4) writes
max /- (X.y), s.t.
max 1
|X (X²) 1
(35)
which is equivalent to
max y" X, s.t. diag(y)A A S 0, max
|X (Xu)++ 1
(36)
wlllu|las1
By taking X = X, we derive
15 This completes the proof.
B.2 PROOF FOR PROPOSITION
For the non-convex max-margin problem
13
consider the Lagrange function
L(W1, W2, A) [ + ||wl)))))))))) (YA)) 1)
where YA
The KKT point of the non-convex max-margin problem (3) (in terms of B- subdifferential) satisfies
0 E ow L(W I. W2. A), (XW) ) X = 0,
(37)
(x,
T W1 Wi)+ 1) 0.
The KKT condition on the i-th column of W1 is equivalent to
N
W1.5
W2 Wn In
(38)
1=1
where In.s E (2)++)x==x w In other words, we have
= I(x wxx.1. 0),
x W1,1 + 0, if W1.: = 0.
In.i
(39)
E 10,
Let D, = (diag((9.......... IN,I)). Then, we can write that
WI,F
x
(40)
U22 x2' X D.A.
From the definition gn,ts we have Therefore, compute that
T In.iXy W1,3 0.
(41)
W2,1
(Xw1,
T(x T W1,i 2 0)x2 W1,iAn
n=1
(42)
N
In, W
n=1
D.A.A
In summary, we have
W1,1 = x
W2,1 W2, = wf.
(43)
Suppose that w2,1 * O. This implies that
W X
X'DAA|= 11
(44)
W2,4
This completes the proof.
13

---

Published as a conference paper at ICLR 2022
B.3 PROOF FOR THEOREM 3
PROOF We can write the Lagrange function for the convex max-margin problem 14 as
T( )== [u X, (2)) 1== (2)))=1)
P
(||uس|2 + ||ا/اl2) + A diag(y) 1 11 (1-diag(y) diag(y)
DD,X(u; u/)
xz (2D) - X) + (2))²(2D)
(2D) 1)Xu,)
(45)
p
Uy
|u/
j=1
5=1
(-X - (2D 1)zz).
1=1
where 2,, 2 E R. satisfies that z, 2 0. ž 2 0 for j E [p] and X E R satisfies that diag(y) 2 0.
The KKT point shall satisfy the following KKT conditions:
-X'DAA X" (2D) T)z's E 0uz (ul11ll122
X'D x (2D) -I)z; E Gu, 111ي
Am
D Dj)ax (uy -uj) - = 0,
(46)
(2,m(2(D))n, - 1)x, uj 0, 2/ (2(D)) 1)x 0.
Let (W1, W2, A) be the KKT point of the non-convex problem (2) and À satisfies (17.. Let D, be
the diagonal matrix defined in Proposition 3 with respect to W1,4 and denote P = [D.li [m]].
Without the loss of generality, we may assume that [D,) are different. (Otherwise, we can merge two neurons W1.i and W1.2 with D;, = Di; together.)
Suppose that Dj P. ie., Dj D; for certain E [m]. By letting u' = W2, z) Uj W2, and = O, the following identities hold.
X"D x (2D:
X
D'A D''
WI4
u
(47)
W2,5
||n|||
X'D (2D; -
Wi,i u:
(48)
W2
|
Therefore, for index j satisfying D; P., the first two KKT conditions in (46) hold.
For Dj & P,, can let u, u': = 0. As À satisfies 17 we have
max
| ATD, S.
(49)
1. (2D, 1
According to Lemma 4 in PPilanci & Ergen 2020 this implies that there exist 2,, 21 such that
|| ||-X" I z (2D, - f)z, 1, x D,A+ (2D, I)z, |l 1.
(50)
Therefore, the first two KKT conditions in (46) hold.
From our choice of uj, Zj. u'y Zj, the last two KKT conditions in (46) hold. We also note that
DD, - uz) = Σ (Xwss) W2,5-
(51)
1=1
As (W1, W2. A) is the KKT point of the non-convex problem, the third KKT condition in (46) holds. This completes the proof.
14

---

Published as a conference paper at ICLR 2022
C PROOFS IN SECTION 3.1
In this section, we present several proofs for propositions in Section 3.1
C.I PROOF FOR PROPOSITION
We start with two lemmas.
Lemma 5 Suppose that Ug Dz and |olll S 1. For any masking matrix Dj P such that
(D, DD) 0) 0. we have
max
X D 1
(52)
(2D; r) Xu20, 211
PROOF According to Lemma 4 in (Pilanci & Ergen 2020), the constraint 52 is equivalent to that there exist zj R. such that 2 and
|x'DAA+XX x (2D) M2,íl S 1.
(53)
Consider the index n E [N] such that (Dj Dolnn # 0. As (D, - Do)I(A > 0) = 0, we have
An S O. We let (zz)n -An. If (Dp)an O, then we have (D) )nn and
(Dj Do) Xn -x 2 (2 )mn nn 1)((z)nn
(54)
If (Do).n nn L, then have (Dj) and
(D, Do)
Xn -x )m 1)(2))
(55)
For other index n E [N]. we simply let (z,)n 0. Then, have
(D; Do)an
0- -x (2DD))n, 1)(
(56)
Based on our choice of z,j we have 23 2 0 and for [N]
(D, Do) An = x (2( )mn 1)(2))n
(57)
This implies that
XT - Do)A = -x (2) - -1)2..
(58)
Hence, we have
X T
Tyz, = X U1-
(59)
Therefore, | XT - 122 1.
Lemma 6 Suppose that the data is orthogonal separable and Y 2 0. Suppose that ug = DD
and ||u S 1. For any masking matrix Dj such that D3 - Dj 2 0, we have || S
||uu||2 I 1. Therefore, (52) holds.
PROOF We note that ug XT Dj)A + XD,A. Denote X'D,A. We note that
x (D, - -D,) and b
T
aTb
Σ
Xa
Σ
Xn Xn'
(60)
(D.
As diag(y) ) > 0, Ao has the same signature with yn. Therefore, from the orthogonal separability of the data, we have
An An x 0.
(61)
This immediately implies that a 2 0. Therefore,
2 | 122 = |a + bl2 = |a | + [bbl2 + 2a 2 ||al|2
(62)
This completes the proof.
Based on Lemma 5 and Lemma 6 we present the proof for Proposition 3. Let u4
W1.14
From the
proof of Proposition we note that |u |l| =
For any masking matrix Dj E PP let D D. D
As D., 2 D, according to Lemma we have
D < I D: A1I2 11
(63)
As YA > 0 and D. diag(I(g (I(y = 1)), have (D, - DD)I(A > 0)
I[(A 0) 0.
From Lemma 5 we note that À satisfies (52). Similarly, we can show that also satisfies (2) This completes the proof.
15

---

Published as a conference paper at ICLR 2022
C.2 PROOF FOR PROPOSITION 5
PROOF Note that YA 2 O. Let Y (liag(I(() =1) and Y- - -diag(lly = --1), We claim
that
max 31
(Xu)+ max A (Xu)+
(64)
Firstly, we note that
N Σ
N
X
X
An (x u)
2( (An)+ (x,, (x] u)+ (Xu)+
(65)
This implies that ul (Xu)+ v maxl Y (Xu)+.
On the other hand, suppose that arg max| X Y (Xu)+. As X is spike-free, there exists such that |zl||2 and Xz (Xu)+ Therefore, have
Y (Xu)+ + X X A (Xz)+. This implies that u A (Xu)+ Z maxi|ul|s Y For any Dj E P with Dj 2 Y We note that
(66)
X (Xu)+ S XXu)+ S Y
(67)
Combining with (65). this implies that max ulll1 X (Xu)+ max =l| A'D(Xu)+
Let us go back to the original problem. Let u = w2
W1.1,
We note that (Xw+) = D,, Xw+ =
D., XX A. Therefore, we have
x"(x++) = D. XX'D, I 2l = u 1 =1
(68)
Thus, for any ||u|2 suppose that (Xu) Xz, where |z||2 1. Then, we have
X D (Xu)+ ADD,, Xz - |z|| 1.
(69)
Therefore, maxiju jul A (Xu) = max |1| A D (u) + < 1. Similarly, we have
min =||
X (Xu)+ min A D (Xu) 2 -1
||
This completes the proof.
D PROOFS IN SECTION
D. PROOF FOR LEMMA 1
PROOF According to the sub aub-gradient flow 22 we can compute that
0
(Il [/ w².) 2w w2, Xi) 2w2, 2w,, w X) = 0.
(70)
Let Tú sup (1.((t)ll2 (t) 0, Vi [n].t E (0, Fort [0, To). as the neural network is scaled, it is sufficient study the dynamics of W1, in the polar coordinate. Let us write (t.:(t) (t)). where [t)l()) = 1. Then, in terms of polar coordinate, the projected gradient
flow follows
a
01 ri sign( uf g(u,, 2),
(71)
0
sign (w.s) (g, X) (uf g(, Xi) u:
at
Without the loss of generality, we may assume that (0) * for [m]. Denote
Fmax max || 12-
(72)
16

---

Published as a conference paper at ICLR 2022
From the definition of X, we have || I 1/4. Therefore, we have
i Ot ri
- uu, 1)1 -
Σ
RT
(73)
f*xFUO0 uso
Therefore, for finite & > 0, we have
ri(t) 2 (0) I.Tma
(74)
which implies that [t) > 0. This implies that To oc.
D.2 PROOF OF LEMMA 2
PROOF As have |w,,l|2 |w2,a/. for n E [M]. can compute that
1mal [I(x W 1) w2l
m
[x] W1, w. #22
W1. 12 (x w1.))-1
(75)
|| la x w1.l
1=1
S ||x 1|2
Note that dn yn (gn) and 4 - 2- (0). As L-Liscchitz continuous, we have
1 - /n/4/ s
1 7laal S
| 2 4
m
wialls
(76)
For any â Q, as An 10,1/4] for [N], we have
(g(ō, X) g(ō, g/4)l/4)|l2
(ān yn/ /4) x
n=
Σ
DA - Aml ||xx
k= >0
(77)
Xx
k=1
m
where e₁ = || is constant. Therefore, we can bound (ōg X(t)) by
m
lg((, X(0))222 < (lgg(..//))) + 9
ww,,( < dmax c1
2n(
(78)
i=1
where we let
Jmax max (onxll/aa.y/411) oe
(79)
17

---

Published as a conference paper at ICLR 2022
(m) Let r(t) jm) rz(t). We note that
0 r(t)
S dmax + cine2 c2 + 22r(1),
(80)
Ōt
where max(nci, dmax} > 0 is a constant. If we start with r(0) < 0, then, r(t) cannot grow much faster than 62t. Let F()) satisfy the following ODE:
a 0t
((t) c2(1 + 22)())
(81)
The solution is given by
1
(t( = c2(1 a) log(1 220x(1-a)).
(82)
where a >> 0 is a parameter depending on the initialization. For any initial r(0), we have unique satisfying (0) = r(0). Therefore, we have r(t) S (t) and
lg:(,, (()) g(a, y/4)ll2 S cine?fa(t),
(83)
According to the bound (33 by choosing sufficiently small ro, (which leads to sufficiently small a), such that
(P) I min { d
(84)
16cz
2x3 max
Therefore, for t S T. we have
dmind
lg(o, X(1)) - g(o,, sineefult) S (F(() S
(85)
8
Hence, we have
d
(tg( A(t) ((o S (a S (F
S
(86)
8
We can compute that
d A, = (2 (g:)
dl J. 4i-
(87)
di
As ((2) (0, 1/4), we compute that
d
d |2 x|:2|||
Wi.j
dt
dt
1
m
d W2,5
Ww Wirsllallxe |x111
dt
(88)
71 m
m
[wi 2 max
12 4
Σ
W
2.
max
max
j=1
j=1
n.r 2 max 2r((1)
Therefore, we have
d
d
1 d
n maxaax 2r(1).
(g))
4i
S
96
(89)
dt
dt
4
8
Suppose that sign( Xu(s)) = (() holds for s a small neighbor of L. Then, we have
d ((u(t), X(o)
d dt
g( (t),
A(t))
dt
|x|lla
<
72
2
max (t(
(90)
dt
8
1=1
3
d2
71 max
2P))T))
<
miin
8
16
This completes the proof.
18

---

Published as a conference paper at ICLR 2022
D.3 PROOF OF LEMMA 3
PROOF Let To = sup Siign(Xu(() = sign(Xuo)) vi E [0, T)}. We analyze the dynamics of
u(l) in the interval [0, min J. For i s min[To; T*). as the statements in Lemma hold, can compute that
d v(t)u((t) u(t)
dt
g(oo, (()) T
||8 (2 u(t)
dt ( g(oo: X(t))
d
u(t) + u(t)
llo X(t))ll2 dt g(00. X(t))
1
d
|g(o, X(t))ll2)
dt
g(oo. ((t)) d @g(0o, X(t))
-u(t) A(t)
(91)
28(00. A(t)) d lg( A(t))ll d
Bl0 X(t) dt
dt
Imin
218(00, ((1))l2a (1 (v(())" u(())) (v(()"(u()))))
Imin
8
290 (1 - 6/8) (1 - (v(t)" Imin
8
290 (1 6/4 - (v()) n(t))))
Here we utilize that go 2 Imin. where gmin is defined in (24 Let z(t) satisfies the ODE
dz(t) (1 8/4 x(t))) )go.
(92)
with initialization z(0) = vo up. Then, we note that
2 8/8
(t) = V 1 6/8
(93)
1 cs exp /g/l/ ///l//l(11) 1V1- 8/8))
VL-8/8 v.
-11 1)
where 0g =
We can compute that
<(T3) 1-
(94)
According to the comparison theorem, for l S min(To, Ta). we have
u(t) 2 =(t).
(95)
We first consider the case where To = 00. As To = co, we have
v(T') u(T*) 2 (T') 1-8.
(96)
Therefore, the second event holds for T < T
Otherwise, we have To
Recall that un u(To) and lim v(t.. Let Ti
(up
vT ug Vt E (0,T)} and Tr (tp(Tiv(t)T 1 5, vt
[0. T)).
Tf < To, for t E [o, T2]. we have
d di v(t) u(t) 2 (1- 8/4- (1 (1- -6)) g0 > 0.
(77)
Therefore, v(t) u(t) monotonically increases in T2]. As u(t) > 2(t) for t E Tol have that 2T2)) < ((T.)" uT(2) condition of the first event holds at T Tg.
8= =Ty) Hence, we have T2 S T Therefore, the second
Then, we consider the case where T2 2 To. Fort t < To. we have v(t) (t)) < 1-8. This implies that vf in S 1 5. Apparently, have Ti < To If Ti < To. as To $ T2. for & [0, To). the inequality
19

---

Published as a conference paper at ICLR 2022
(7) holds. This implies that lime-To- v(t) u(To) v(Ti) u(T)
(((T)) = lim v(t) u(To). v(t))u(TT).
which leads to contradiction. Therefore, we have To = TT. We note that
=(1 (u vi) = u V1.
(98)
As (ut))t(((t)... x(t)= 2 =t) for t [0, To). we have that = =(T)) ufvi v1 S (Ts)) Hence, we have g(u(t),
To = Ti S T shift (uf v1). This completes the proof.
D.4 PROOF OF PROPOSITION 6
We first introduce a lemma.
Lemma Let a, b E R and 0 < 6 < c. Suppose that ||a
-bll I and ||al| 2 c. Then, we have
28
(99)
||l|
|bl2
12
c
PROOF As d we have |16||2 > ||al2
||a
bll2
8
0. We first note that
||||||
- ||b||||
5
|all2"
|bll''|
(100)
|||2||b|12
c| bbl2
Therefore, we can compute that
b
|a|
[b]
2
b
||bll
(101)
|a
2
|a
2|
|aI|
|
8
8
25
This completes the proof.
Then we present the proof of Proposition 6
PROOF As y (Xuo)+ >> with sufficiently small initialization and sufficiently small å >> also have ((0)"(Xu))+: 2 y" (Xun)+/4- | ((()) - y > 0. We prove that there exists a time T such that u(T) v(T) v(T))v(T) 2 1 3 5 by contradiction. Denote vo = v(0). For all possible values of (g, y/4)l22. we can arrange them from the smallest to the largest by 9(1) < 9(2) < ... < 9(p)
log y 1-8/8+11-77
/1-6/8+9,, vo un
Let T; 2
61-6/8-1-6/2 log V1-6/8-
and T = Σ T. Suppose
9,0 v8
that ro is sufficiently small such that statements in Lemma 2 holds for T. According to Lemma 3
we can find 0 to < 41 <... such that for i = 1,..., sign sign(Xu(()) is constant on [4:-1, 4i) and
sign( (u((,-1)) o sign (u(())). We write u, u(4). 0: = (g(u(44,y/4))
g:
lim g( (((()) (()), g: = (((u(4),5(0)) 176.
(102)
g,
and V;
g: 1glla
We note that g = g According to Lemma
3 we have
lg 1l2
1 - 5/8 + (v. Tu;
0/8 v
i- Ui
t, t--1 1 I
log
log
2/ 8/8gi-1
VI - 6/8 - (v. Y'u
0/8 vT Wi-1
1
log /I 11--81 8/8 + (v. 'Tu
5/8
+ v. 4i-1
log
2- 6/8gmin
5/8 - (v, Tuu
V1 5/8 vT_ u1-1
(103)
Here utilize that 9i-1 Imins where Jmin is defined in
24 This implies that
VI 6/8 + (v. yru, u;
V1 5/8 + vTT u
> 2
(104)
6/8 (v; Tu,
V1 8/8 v u
20

---

Published as a conference paper at ICLR 2022
log /1 11- 11-8/8+1-66
+ mmin vo
We can show that for satistying 2/1-6/8gmin
v1 11-6/8-145/ log
and
1-9min Vo Up
t I T, we have [lg(((t), A)lla Imin. According to Lemma
as 94 2 Iwin we have
v1 6/8 9min (g: u,
8/8 + Imin Minini-11 11
T
e2 L-V1-//8
(105)
V1 6/8 Imin (g, Tu;
v 6/8 Imin 111-1
-1 T
This implies that
/1 5/8 + 9mn 8g ) u;
2 2 1-/88gmm 4, / 5/8 + 9min Vo up
2
(106)
VI 5/8 Imin gi )d u;
VI 6/8 Imin vi ug
or equivalently, for any > O, we have
V1 11-6/6 8/8 9 min (g()()).)(())))
17/8mmm V 5/8 + Imin vō Uo
(107)
V1 8/8 I (((())()(())))))))) (()) A(t))
V1 8/8 -miin Vo Uo
Here we utilize that g(u((), A(1)² u(()) is continuous w.r.t.
4. Therefore, for I 2
(log 2-8 5
log +. vo u1
we have
2gmii
mii v8 up
1 Mmmi ((((())))))))))))()))) ((O))=
v1 -188/8 8/8 +
5/2
(108)
1 Mmin g (()),
V1 - 1-88/8-111 - 1 8/2
This implies that
Funn (g( (()))
(1) 8/2.
(109)
[[g(u(t), A)ll2 = Jmin. as the statements Lemma 2 hold, we can compute that
(g(u((), g(u((),(())I < Imind ô 4 (lg(u()),)) A))22,
(110)
which implies that Therefore, we have
[lg(u(t), (1 8/4))lg(u((), 2)122
(111)
v(t) u(t) (g(u((), ((()))((()
(lg(u((), A(O))
(g(u(1), u()))
(112)
+ 6/4
Jmin
- 6/2
3 8.
+ 6/4
This leads a contradiction.
Analogously, we can show that for 2 Ej=1 Ti, we have (lg(u((), 9()) Thus, by taking t > Ei= Tr, we have [g((((),y/4) //))l/2 >> 9(p) Jmax. However, from the definition of gmaxs have (u(() y 44 Imax- This leads to contradiction. Therefore, there exists time T=
Dn T, (log 8 such that v(T) (TT) 2 88.
We note that [lg(u(T) /4) 2 Imiu- As the statements in Lemma 2 hold, we have
8gmin
(g(()()))//4) g(u(T),
(113)
According to Lemma
we have g(u(T),X(T))
g(u(T).y/4)
(llg(u(T). g(u(T),
<
y/(44)) X(T))l
4
Imin
(114)
21

---

Published as a conference paper at ICLR 2022
This implies that
u(T)² g(u(T), (g(u(T), y///4//2
g(u(T),
((())))((T)
(115)
2u(T)"v(T)
(ls(u(T). A)ll [Iı(u(T), X(T))la 1
21 - 8.
Hence, we have
u(T) g(u(T),))
u(T) g(u(T).y/4) y)) [lg(u(T).//4)l 21
cos
This completes the proof.
D.5 PROOF OF LEMMA 4
PRooF This is proved in Lemma 2 in (Phuong & Lampert 2021). Here we provide an alternative proof. is sufficient prove for the case of local maximizer. Suppose that a local maximizer of y" (Xw)+ in B. We first consider the case where y" (Xw) > 0.
If there exists n [N] such that (w, Xa) 0 and yn 1. Consider v x,, / /,/ ||| and let
w-ev W. w where >> 0. For index n' [N] such that yn = 1, as the dataset is orthogonal
separable, we have x Xn > 0 and
x (ww + +vv = x w + X ||2
Xn
x W.
(116)
This implies that (x we)+ 2 (x w)+. For ynr 1, as the data is orthogonal separable, we note that xfx,, < 0 and
x (ww + +vv = X w
Xn S x W.
(117)
X ll
This implies that (x² wel+ S (x] w)+ In summary, have
- +cv)+ Σ Un (w + ev))
wxx (Xw)+ > =x"x))
(118)
(w, xn) < O, then wTv < This implies that with sufficiently small e, we have ||w + evll2 < [w| = 1. Therefore,
y"( + ("(X(w + [v))+ (X(W 2
2 ( (XW)+
(119)
which leads to contradiction. If (w, = 00 we note that
(x,, -e> (x77 w)+. =
(120)
This implies that
y" (' +ev))+ ( + We also note that ||w + +evl22 = VI+ 1+0( Therefore, with sufficiently small e, we have
(121)
((W)) (T[Xw)+++ (
(Xw)..
(122)
V
We then consider the case where yT ((ww)+ < Apparently, replacing w by (1 11-c8 c)w, where e E (0, 1), which leads to a contradiction.
make y (Xw)+ larger by
Finally, consider the case where y (Xw)+ 0. This implies that
Σ (x] w) nyy==1
Σ w)
(123)
As (Xw) * 0, this implies that there exists at least for one index n E [N] such that yo = 1 and x w > 0. Let = xn/lxx, We note that [ (X(w Ev))+ > 0 for > 0. This leads contradiction.
22

---

Published as a conference paper at ICLR 2022
D.6 PROOF OF PROPOSITION
is sufficient to consider the case of the local maximizer. Denote Q = (o E 1, d)
P). For o, o' E Q, we say o S o' for all index n E [N] with on * 0, o = on. open if n # 0 for [N]. Define
We say a E Q
S. = (ulsign(Xu) = o...
(124)
We start with the two lemmas.
Lemma 8 Let À RN. Suppose that ug satisfies that ug A( Let sign(uo). Then, (u
B2 is local maximizer of X" (Xu)+ in B2 for any open of satisfying S a', have (g(Ory))l = ||g(o', 12)
PROOF Suppose that a open. Then, S. an open set. In small neighbor around up g(Ho.A)
g(a.A) B X (Xu)+ u g(o, A) is a linear function of u. The Riemannian gradient of u g(o, A) at v zero. This implies that v locally maximizes X (Xuu++
Aill
Suppose that there exists at least one zero in Consider any v E B satisfying u v 0. Let 0 be a small constant such that for any s (0, c). un + sv E So where C Let Ug = utav
VI+
Suppose that llg(o" A) < (e(o,))li for all open o" satisfying S a". For any o' with S r', we construct a" by of -1 for n E [N] such that a 0 and o" d' for E [N] such that of = 0. We note that llg(o" A)ll2 2 llg(o', A)ll2. Thus, (l((o,))) s lgg A)l22 As (X"(Xu;)+] = lg(o', Ai) ug I Ig(o', X) have
lgg(o" A)l A (Xu,)+1 lg(a', A)lle |g(a, 2)1l2. Therefore, u is local maximizer of X (Xu)+.
Lemma 9 Suppose that the dataset is orthogonal separable. Let X E RN satisfy that diagly) 2 0. o', have
Suppose that Ug satisfies that ug
g()).)) A Then, for any a' satisfying
llg(o', A) = llg A))l2
PROOF If there exists n [AV such that on 1 and yn -1, the data is orthogonal separable, we note that
go A) = =x
An n1:0,,30
Σ
= -yn(UnXn)) yr
Σ
Yoe Wr Xxp'
S00, (125)
which contradicts with sign(x", g(o A)) sign un) = Jn
Suppose that there exists E [N] such that on and yn 1. Then, the dataset is orthogonal separable, then, for index n2 E [N] such that on, = 0, we note that you, * 1. Otherwise,
g,, A) XT
Σ
Xnz Xnz
Xx1
Σ
Xnn 0,
(126)
12107gg 30
#2:0mg30
which contradicts with sign g(a, A)) sign un) On O. This also implies that the index set (n E [N] > 0} include all data with yn
If there exists o' such that o' and lg(a', A)]l2 lgg(o, A)1 Then, there exists at least one index E [N] such that on S 0 and of However, from the previous derivation, we note that
Yn - and
_ 2) = x
=x
Σ fior 0o
Any Xny
= x
Σ Ri:00
(on Mey Di Xny
< <0,
(127)
>0
which contradicts with 0'
By combining Lemma and complete the proof.
23

---

Published as a conference paper at ICLR 2022
D.7 PROOF OF THEOREM 4
find two neurons such that sign(w2,;)) and sign(u22 ) sign(y" (Xw1. )-) -1 initializa- tion. By choosing a sufficiently small > in Proposition 6 there exist two neurons W1.4.; Wi.1_ and times T-
PROOF For almost all initialization,
sign(y" (Xw1,i,)+)
such that cos Z(WI,1_ (T+), g(Wi, (T+).)) y)) 1 6 and < -(1 6). This implies that W1,44 (T+) and W1,1 (T+) are
cos 2(11,, (T+) g(1,,
sufficiently close to certain stationary points of gradient flow maximizing/minimizz
(Xu,) over B, i.e., (u B] cos cu.s(u,gee (u, = 113. As the dataset is orthogonal separable, according to Lemma and Proposition
7 the corresponding diagonal matrices Di, (T+) and (T-) satisfy that D (T+) d 1)) and D (T-) 2 diag(I(y =-1). According to Lemma 3 in PPhuogg Lampert 2021). we have D;, (1) 2 diag([I(y = 1)) and D, (1) 2 diag(I(y = -1)
hold tort max[T+. T_).
With + c0, according to Proposition 4 the dual variable À the KKT point of the non-convex margnn problem (3) is dual feasible, i.c., À satisfies (T Suppose that 0" is limiting point
(( and X is the corresponding dual variable. From Theorem I, we note that the pair of { [ 120
(0* )) corresponds the KKT point the convex max-margin problem
E
PROOFS OF MAIN RESULTS ON MULTI-CLASS CLASSIFICATION
E.1 PROOF OF PROPOSITION
The neural network training problem can be separated into K subproblems. Each of these subproblems corresponds to the neural network training problem (3) for binary classification. For each subproblem, by applying Proposition 2 we complete the proof.
E.2 PROOF OF THEOREM
We note that the neural network training problem 4 can separated into K subproblems. Each of these subproblems corresponds to the neural network training problem (3) for binary classification. By applying Proposition 66 with to each subproblem with y = Ys. we complete the proof.
E.3 PROOF THEOREM 2
Similarly, the corresponding non-convex max-margin problem and the convex max-margin problem 7 can be separated into K subproblems. Each of these subproblems corresponds to the non- convex max-margin problem (2) and the convex max-margin problem (14) for binary classification. By applying Theorem too each subproblem with Yk, we complete the proof.
F NUMERICAL EXPERIMENT
F.1 DETAILS ON FIGURE
We provide the experiment setting in Figure T and 5 as follows. The dataset given by X
R.? 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 6
1.65
-0.47
R22 2x2 and y |
-0.47
1.35
24

---

Published as a conference paper at ICLR 2022
Figure 6: The ellipsoid set and the rectified ellipsoid set. Orthogonal separable dataset.
We enumerate all possible hyperplane arrangements in the set P and solve the convex max-margin problem (4) via CVXPY to obtain the following non-zero neurons
0.58 -0.66
-0.23
U1,3 =
w1,2 = 0.66
(128)
We note that the dual problem
15 is equivalent to
max A y,
s.t.
- - 1)2,,+ 1, E [p],
(129)
- x x D (2D, - 1)z,,-11 < 1, vj E [p].
2j 2 0, 2 0, [p]. dyag(y)) 2 0.
The above problem is a second-order cone program (SOCP) and can be solved via standard convex optimization frameworks such CVX and CVXPY. We solve ([29) to obtain the optimal dual variable X. For the geometry of the dual problem, as the dataset is orthogonal separable, the set {A max ul|2S1 a ( | I 1} reduces to {X max|jullas] | ("(X)))+ I 1, (Xu))++ s 1}. where ui, uz correspond to two vectors at the spikes of the rectified ellipsoid set. We draw the sets {İ max]julls! |A (Xu)+I < 1}. (A the optimal dual variable À and the direction of y in Figure
For each D, P. solve for the vector u, which maximize/minimizz A ADD, Xu, with the constraints ||ll & 1 and (2D, Xu, 2 0. We plot the rectified ellipsoid set (Xu)+ ||llll S 1}. vectors Uj neurons in the optimal solution (14) scaled to unit f--norm and the direction of X in Figure [
We note that each neuron u in the optimal solution from (14) (scaled to unit (n-nor)
maximize/minimize the corresponding X Du, given (2D, - X) 0.
Then, we consider two-layer ReLU network with m = 10 neurons and apply the gradient descent method to train on the logistic loss 3.. Let W1, T for i [m]] We plot W1,i and (Xw (,,++
at iteration [10' O...., 4} along with neurons in the optimal solution (14) scaled to unit fg-norm in Figure [] Certain neurons do not move, while the activated neurons trained by gradient
descent tend converge to the direction of the neurons in the optimal solution
(14).
We repeat the training on the logistic loss with the gradient descent method several times and we
plot the trajectories in Figure
25

---

Published as a conference paper at ICLR 2022
2,00
opemall
1.75
yluw
optimal (se) )+
Boundary
th neuron
1:25
4-th neuron
54hh Deurer
1.00
0.75
th nouron
94h neuron
10-th neuron
optimal
0.25
-1.0
0.00
-0.5
1.95
1.75
trained pow,.
(ite)).
cone bouneary
1.50
0.5
1-th neuton
th nouron
1.25
54th neurer
0.0
64h neuron
74t neczun
0.75
-0.5
10 th nouron
0.50
optimal neuron
0.25
-1.0-
-1.0
-0.5
0.0
0.5
1.0
0.00
0.25
0.50
0.75
1.00
1.25
155
1.75
2.00
2.00
1.0
optimal
1.75
y'o=0
optimal (3N) J.
2-th neviror
1.25
34h necrrnn
to nouron
1.00
neurcn
84th neuron
th nouron
0.25
-1.0
0.00
0.25
1.00
1.75
ylu-u trained 10w,
(30)
.... cone boundary
1.50
0.5
tn nouron
neurce
0.0
5-th neurer
Ch nouron
1.00
0.75
-0.5
th nouron
0.50
optimal nouron
-1.0
0.00
-1.0
-0.5
0.0
0.5
1.0
0.00
0.25
0.50
0.75
1.00
1.25
1.35
2.00
Figure 7: Multiple independent random initializations of gradient descent trajectories on the same orthogonal separable dataset.
26

---

Published as a conference paper at ICLR 2022
F.2 EXPERIMENT ON SPIKE-FREE DATASET
1.65
0.47
We repeat the previous numerical experiment on non-spike-free dataset: X
0.47
1.35
2 and y 1 e RR2. Similarly, we plot the ellipsoid set and the rectified set Figure
Figure The ellipsoid and the rectified ellipsoid set for a non-spike-free dataset.
We enumerate all possible hyperplane arrangements in the set P and solve the convex max-margin problem [44 via CVXPY to obtain the following non-zen neuron
T0.43 [0.59
11,4
(130)
We plot the rectified ellipsoid ((uu)+ |1/2 < 1). vectors 1y, neurons in the optimal solution
(14) scaled to unit f2-norm and the direction of À in Figure 9 We also plot W1,1 and (Xw1,)+ at iteration /10' = .,...,4 4} along with neurons in the optimal solution to (I4) scaled to unit f--norm
Figure 10
2.0
0.5
0.0
optimal
you
maximal
minimal
optim (Xw,)))
1.0
-0.5
0.0
0.5
1.0
15
2.0
Figure 9: Recitified Ellipsoidal set and correspond- ing extreme points for non-spike-free dataset.
27

---

Published as a conference paper at ICLR 2022
2.00
optiml 2
1.75
y'um
optimal [Xw]..
Boundary
th nouron
1:25
4thh neuron
Schipeuree
1.00
0.75
th nouron
94h netron
10-th neuron
optimal
0.25
-1.0
0.00
1.75
trained (om,ls
y
cone boundary
1.50
0.5
Lith neuron
th nouron
1.25
neuror
0.0
64h metron
74th meuron
0.75
-0.5
10 nouron
0.50
optimal neuron
0.25
-1.0
-1.0
-0.5
0.5
0.5
1.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.00
1.0
optimal 2
1.75
y'u=
optinaal Lim).
24th neurer
1.25
34h neuroe
to nouron Settineuror
1.00
neurc
84th neuron
th nouron
0.25
-10
0.00
1.00
Figure 10: Multiple independent random initializations of gradient descent trajectories on the same non-spike-frec dataset. Note that the optimal extreme point (star), which the uniquely optimal single neuron is on the boundary of the main two-dimensional ellipsoid and not on the one-dimensional spikes (projected ellipsoids). Also note that some neurons are stuck at spurious stationary points.
28


Reviews:
[{"review_id": "zkLmFj5GUw", "reviewer": "Reviewer_uQbv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is to prove that the non-convex gradient flows for the max-margin problem converges to the KKT points of the convex max-margin problem. This is a significant result which may be of interest to parts of the community.\n\nOn the other hand, the structure of the paper can be improved. For instance, Section 2.2. is labelled \"Outline of our contributions\" but this section already contains some preliminary results, e.g. the characterization of the dual extreme points as well as the discussion of the implicit regularization of unregularized gradient flow, while the main contributions are not discussed here. \n\nMoreover, I found Section 5 a bit hard to follow since the purpose of the individual Lemmas is not made clear directly in the section. The flow of the section could be improved by providing additional information about which role they play in the overall proofs.\n\nFinally, the abstract says that the paper presents numerical results verifying the predictions of their theory. However, those experiments are only contained in the Appendix.\n\nOverall, while the paper contains some interesting results, overall the presentation and flow can be improved. Therefore I am leaning towards rejection of the paper.\n\n\n\n--- \nAfter rebuttal: The authors made several improvements to the flow and structure of the paper, as suggested in my review. Therefore I have increased my score.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper contains some interesting results which may be of interest to the community, but the presentation and flow of the paper can be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "aByoprKyOOf", "reviewer": "Reviewer_pBSm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. Clear presentation and strong logicality;\n2. The corresponding non-convex max-margin problem with the following dual reformulation is clear (maybe mathematically correct);\n3. The geometry discussion of the neural gradient flow is clear, especially based on Figures 1-4.\n", "summary_of_the_paper": "This paper discussed the convergence of the gradient flows of two-layer neural networks, while they claim the convergence of non-convex gradient flows to global optimum which is different from existing works. The theoretical analysis framework seems to be novel and some sufficient condition is proposed to support the strong theoretical results.", "summary_of_the_review": "Although I am not an expert on this topic, the paper is well-written and the novelty of the idea seems to be clear after careful reading and thinking.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SgpEwwk8wK3", "reviewer": "Reviewer_8kmN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I feel that the technique and the result are novel and of interest to the community. While other approaches, such as NTK or mean-field, have established global convergence guarantees, those results are asymptotic in the size of the neural network and do not provide the interpretation of the max-margin classifier. I feel that these results make the line of work on the convex formulation more complete, and will serve to further encourage the line of work analyzing neural networks based on some hidden form of convexity.\n\nAs an aside, it would be great if the authors can comment on the extendability of this approach to the setup of three-layer ReLU, as studied in Ergen and Pilanci 2021. ", "summary_of_the_paper": "This work analyzes the training dynamics of two-layer ReLU networks applied to separable problem data, based on the equivalent convex formulation by Pilanci, Ergen 2020. The main result states that the gradient-flow training dynamics provably converges to a \"maximum-margin classifier\". ", "summary_of_the_review": "Establishing training guarantees of two-layer ReLU networks based on convex formulation of Pilanci, Ergen 2020 is sufficiently novel and interesting.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The papers makes progress on the important question of implicit bias in gradient based neural learning. Remarkably they derive reasonable conditions for global optimality.
Decision: Accept (Poster)