On Margin Maximization in Linear and ReLU Networks
Authors: Gal Vardi
Ohad Shamir
Nathan Srebro
Venue: ICLR 2022 Submitted (2022)
Keywords: Implicit bias
Homogeneous neural networks
Exponential loss
Logistic loss
Maximum margin
Linear networks
ReLU networks

Abstract: The implicit bias of neural networks has been extensively studied in recent years. Lyu and Li [2019] showed that in homogeneous networks trained with the exponential or the logistic loss, gradient flow converges to a KKT point of the max margin problem in the parameter space. However, that leaves open the question of whether this point will generally be an actual optimum of the max margin problem. In this paper, we study this question in detail, for several neural network architectures involving linear and ReLU activations. Perhaps surprisingly, we show that in many cases, the KKT point is not even a local optimum of the max margin problem. On the flip side, we identify multiple settings where a local or global optimum can be guaranteed. Finally, we answer a question posed in Lyu and Li [2019] by showing that for non-homogeneous networks, the normalized margin may strictly decrease over time.

Under review as a conference paper at ICLR 2022
ON MARGIN MAXIMIZATION IN LINEAR AND RELU NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The implicit bias of neural networks has been extensively studied in recent years. Lyu & Li (2019) showed that in homogeneous networks trained with the expo- nential or the logistic loss, gradient flow converges to a KKT point of the max margin problem the parameter space. However, that leaves open the question of whether this point will generally be an actual optimum of the max margin prob- lem. In this paper, we study this question chitectures involving linear and ReLU activations. Perhaps surprisingly, we show that in many cases, the KKT point is not even a local optimum the max margin problem. On the flip side, we identify multiple settings where a local global optimum can be guaranteed. Finally, we answer a question posed in Lyu Li (2019) by showing that for non-homogeneous networks, the normalized margin may strictly decrease over time.
detail, for several neural network ar-
INTRODUCTION
A central question in the theory of deep learning is how neural networks generalize even when trained without any explicit regularization, and when there are far more Iearnable parameters than training examples. In such optimization problems there many solutions that label the training data correctly, and gradient descent seems to prefer solutions that generalize well (Zhang et al. 2016). Hence, it is believed that gradient descent induces implicit bias (Neyshabur et al., 2014 2017
and characterizing this bias has been a subject of extensive research in recent years.
A main focus in the theoretical study of implicit bias is on homogeneous neural networks, These networks where scaling the parameters by any factor a > scales the predictions by a for some constant For example, fully-connected and convolutional ReLU networks without bias terms are homogencous. Lyu & Li (2019) proved that in linear and ReLU homogeneous networks trained with the exponential or the logistic loss, if gradient flow converges to zero loss then the direction to which the parameters of the network converge can be characterized point (KKT point) of the maximum margin problem in the parameter space. Namely, the problem of minimizing the l norm of the parameters under the constraints that each training example is classified correctly with margin at least 1. They also showed that this KKT point satisfies necessary conditions for optimality. However, the conditions are not known to be sufficient even for local optimality. It is analogous to showing that some unconstrained optimization problem converges to a point with gradient zero, without proving that it is either global or a local minimum.
first order stationary
In this work we consider several architectures of homogeneous neural networks with linear and ReLU activations, and study whether the aforementioned KKT point is guaranteed be global optimum of the maximum margin problem, a local optimum, or neither. Perhaps surprisingly, our results imply that in many cases, such depth-2 fully-connected ReLU networks and depth-2 di- agonal linear networks, the KKT point may not even be a local optimum of the maximum-manne problem. On the flip side, we identify multiple settings where a local or global optimum can be guaranteed.
We now describe our results in bit more detail. We denote by A the class of neural networks without bias terms, where the weights in each layer might have an arbitrary sparsity pattern, and
'They also assumed directional convergence, but Ji & Telgarsky 2020 later showed that this assumption not required.

---

Under review as a conference paper at ICLR 2022
Table 1: Results on depth-2 networks.
Table 2: Results on deep networks.
Linear
ReLU
Linear
ReLU
Global
Not local
Global
Not local
Fully-cone Fully-connected
Fully-connected
(Thm. 3.1
(Thm. 3.2
(Thm. 3.1
(Thm. 3.2
Not local
Not local
Nuo-sture assuming non-zero inputs to all neurons
Suu-hhree
Not local
Not local (Thm. 5.
(Thm.
(Thm. 3.2
(Thm. 5.1
Nun-sture assuming
Global
Not local
weights
N max margin for each layer sep- arately
(Thm.
(Thm
Global
Not local (Thm. 5.3
vectors
(Thm. 5.2
Nmn-taue assuming
Local,
Global (Thm.
non-zero inpuls to all neurons
Not global
N
margin for each layer sep- arately, assuming non-zero inputs to all neurons
(Thm. 4.3
Local, Not global (Thm. 5.4
Global (Thm.
N assuming non- zero inputs to all neurons
Not local (Thm
Not local (Thm 4.4
weights might be shared The class N contains, for example, convolutional networks. Morcover, denote by Noo-sbare the subclass of N that contains only networks without shared weights, such as fully-connected networks and diagonal networks (cf. Gunasekar et al. (2018b); Yun et al. )2200).
We describe our main results below, and also summarize them in Tables 1 and 2.
Fully-connected networks:
In linear fully- colleccon networks of any depth the KKT point is global optimum
In fully-connected depth-2 ReLU networks the KKT point may not even be a local optimum. Moreover, this negative result holds with constant probability over the initialization, i.e., there is training dataset such that gradient flow with random initialization converges with constant probability to the direction of a KKT point which is not local optimum.
Depth-2 networks in N:
The positive result on fulne-con linear networks does not extend to networks with sparse weights: In linear diagonal networks the KKT point may not be a local optimum.
In our proof for the above negative result, the KKT point contains a neuron whose weights vector is zero. However, in practice gradient descent often converges to networks that do not contain such zero neurons. We show that for linear networks in N the KKT point has only non-zero weights vectors, then it is global optimum. We also show that simple case of depth-2 diagonal linear networks, the optimality of the KKT points can be unex- pectedly subtle, in the context of margin maximization the predictor space (see Remark (4.1)
for the
For ReL.U networks in Wao in order to obtain positive result we need a stronger assump- tion. We show that the KKT point such that for every input the dataset the input to every hidden neuron in the network is non-zero, then it is guaranteed to be a local optimum (but not necessarily a global optimum).
For linear ReLU convolutional networks, even if the above assumptions hold, the KKT point may not be local optimum.
Deep networks in A':
We show that the positive results on depth-2 linear and ReLU networks in Amn-share (under the assumptions described above) do not apply to deeper networks.
We study a weaker notion of margin maximization: maximizing the margin for each layer separately. For linear networks of depth m 2 2 in A (including networks with shared weights), show that the KKT point is global optimum of the per-layer maximum margin problem. local optimum this problem, but under
For ReLU networks the KKT point may not even the assumption non-zero inputs to all neurons it is local optimum.
2See Section for the formal definition.
We note that margin maximization for such networks in the predictor space is already known Ji & Tel- garsky 2020). However, margin maximization in the predictor space does not necessarily imply margin maxi- mization the parameter space.
2

---

Under review as a conference paper at ICLR 2022
In the paper, focus is understanding what can be guaranteed for the KKT convergence points specified in Lyu & Li (011)). Accordingly, in most of our negative results, the construction as- sumes some specific initialization of gradient flow, and does not quantify how "likely" they to be reached under some random initialization. An exception is our negative result for depth-2 fully-connected ReLU networks (Thm. B.2)) which holds with constant probability under reason- able random initializations. Understanding whether this can be extended to the other settings we consider is an interesting problem for future research.
Finally, we consider non-homogeneous networks, for example, networks with skip connections or bias terms. Lyu & Li (2019) showed that a smoothed version of the normalized margin is mono- tonically increasing when training homogeneous networks. They observed empirically that the nor- malized margin is monotonically increasing also when training non-homogeneous networks, but did not provide a proof for this phenomenon and left it as an open problem. We give an example for simple non -omoogggees network where the normalized margin (as well as the smoothed margin) is strictly decreasing (see Thm. 6.1
The paper is structured as follows: In Section 2 we provide necessary notations and definitions, and discuss the most relevant prior results. Additional related works are discussed in Appendix A In Sections 3 and 5 we state our results on fully-connected networks, depth-2 networks in N and deep networks in N respectively, and provide some proof ideas. In Section non-homogeneous networks. All formal proofs are deferred to Appendix C
6 we state our result on
2 PRELIMINARIES
Notations. We use bold-faced letters to denote vectors, e.g., x = (Ii,..., za). For x E Rd we denote by ||x|| the Euclidean norm. We denote by 1.) the indicator function, for example 11 2 5) equals f 2 5 and 0 otherwise. For an integer 2 1 we denote [d] = {l....,d}
Neural networks. A cullyccomected neural network of depth m 2 2 is parameterized by a collection 0- [w(0]] of weight matrices, such that for every layer E [m]] we have W(0) Rdixdt-1, Thus, di denotes the number of neurons in the 1-th layer (i.e., the width of the layer). We assume that dm = 1 and denote by d == do the input dimension. The neurons in layers [m 1--1] are called hidden neurons. A fully-connected network computes a function ((::)) Rd + R defined recursively as follows. For an input x E R' we set h/ = x, and define for every j E [m - 1] the input to the j-th layer as h, = W h and the output of the j-th layer as h2 o (h,). where a: R + R is an activation function that acts coordinate-wist on vectors. Then, we define (0;:x) (1m) b'n Thus, there is no activation function in the output neuron. When considering depth-2 fully fully-connetted networks we often use a parameterization O [w....., Wk: v] where W....., W; are the weights vectors of the k hidden neurons (i.e., correspond to the rows of the first layer's weight matrix) and v are the weights of the second layer.
We also consider neural networks where some weights can be missing or shared. We define a class A of networks that may contain sparse and shared weights as follows. A network & in A is parameterized by [u Jmm
[ where is the depth of 4, and ! e R" are the parameters of the
1-th layer. We denote by W(O E dRde the weight matrix of the I-th layer. The matrix ((() is described by the vector u and a fuuction
[di] x [di-1] + [pd] U {0} as follows: w 0 if (i.j) = 0, and w = uy if gi(i.j) = k > O. Thus, the function 9i represents the sparsity and weight-sharing pattern of the 1-th layer, and the dimension pt of ( is the number of free parameters in the layer. We denote by d := dn the input dimension of the network and assume that the output dimension dm is 1. The function (0:-)) : Rdd + R computed by the neural network defined recursively by the weight matrices as in the case of fully-connected networks. For example, convolutional neural networks are in N. Note that the networks in ' do not have bias terms and do not allow weight sharing between different layers. Moreover, we define subclass A Ann--hare of N,, that contains networks without shared weights. Formally, a network is in Nuo-share if for every layer and every k [pi] there is at most one (i,j) E [d;] x [di-1] such that gr(i.)) k. Thus, networks in Nos Vno-shure shore might have sparse weights, but do not allow shared weights. For example, diagonal networks (defined below) and fully-connected networks are in N na share- shure-
3

---

Under review as a conference paper at ICLR 2022
A diagonal neural network is network in Nao-stare such that the weight matrix of each layer is diagonal, except for the last layer. Thus, the network is parameterized by 0 = [W1..... [Wml where W, E Rd for all E [m], and it computes function ( R - R defined recursively as follows. For input x Rd set ho x. For j E [m 11, the output of the j-th layer is hy = (diagg(w) wy)h,-,),,,,.. Then, we have $ x) = W hm
In all the above definitions the parameters @ of the neural networks are given by a collection of matrices or vectors. We often view 0 as the vector obtained by concatenating the matrices or vectors in the collection. Thus, ||O]] denotes the & norm of the vector 0.
The ReLU activation function is defined by (z) max (0, z), and the linear activation is (() In this work we focus on ReLU networks (i.e., networks where all neurons have the ReLU activation) and on linear networks (where all neurons have the linear activation). We say that a network & is homogeneous if there exists ((00; x) = a x)) Note that in our definition of the class N we do not allow bias terms, and hence all linear and ReLU networks in A are homogeneous. With the exception of Section 6 which studies non-homogeneous networks, all networks considered in this work are homogeneous.
0 such that for every
0 and 0, x we have
Optimization problem and gradient flow (GF). Let = [xx,, B.)) C CR²s x (-1, 1 be a bi- nary classification training dataset. Let T be neural network parameterized by O E R For a loss function & R + R the empirical loss of ((0:-) on the dataset is ( := Σi (( We focus the exponential loss {(q) - and the logistic loss E(g) = log + e 9), and consider gradient flow (GF) on the objective (()). This setting captures gradient descent with an infinitesi- mal step size. Let (t) be the trajectory of GF. Starting from an initial point @(0). the dynamics of
do(t) = (L(((t)). Note that the ReLU function is not differentiable at O. Practical implementations of gradient methods define the derivative a (0(0) to be some constant in [0, 1j. We note that the exact value of a' o0()) has no effect on our results.
(t) is given by the differential equation dt
Convergence to KKT point of the maximum-margin problem. We say that a trajectory ((t) In this work we rely on the following theorem:
converges in direction to 0 if lim
e(C)
[o]
Theorem 2.1 (Paraphrased from Lyu & Li 2019); & Telgarsky 2020 Let t be homogeneous linear or ReLU neural network. Consider minimizing either the exponential or the logistic loss over a binary classification dataset {(x,, 9:) using GF. Assume that there exists time to such that (to)) < 1, namely, & classifies every x; correctly. Then, GF converges in direction to first order stationary point (KKT point) of the following maximum margin problem in parameter space:
min 0
011
S.L.
Vi [n] 1,0(0xx,) 21.
(1)
2
Moreover, L(((t)) - 0 and [[0()]] + 00 as xc.
In the case of ReLU networks, Problem is non-smooth. Hence, the KKT conditions are defindd using Clarke's subdifferential, which generalization of the differential for non-differentiable functions. See Appendix [ for formal definition. We note that Lyu & Li (2019) proved the above theorem under the assumption that 0 converges in direction, and Ji & Telgarsky (2020) showed that such directional convergence occurs and hence this assumption is not required.
Lyu & Li (2019) also showed that the KKT conditions of Problem I are necessary for optimality. In convex optimization problems, necessary KKT conditions are also sufficient for global optimality. However, the constraints in Problem T are highly non-convex. Moreover, the standard method for proving that necessary KKT conditions are sufficient for local optimality, is by showing that the KKT point satisfies certain second order sufficient conditions (SOSC) (cf. [Ruszczynski (201T). However, even when & is a linear neural network it is not known when such conditions hold. Thus, the KKT conditions of Problem [ are not known to be sufficient even for local optimality.
A linear network with weight matrices W())..... (mm) computes a linear predictor x + (B, x) where & = W(m) the predictor space. Namely, characterizing the vector 33 from the aforementioned linear predictor. Gunasekar et al. (2018b) studied the implications of margin maximization in the parameter space on the implicit bias in the predictor space. They showed that minimizing |[0]] (under the constraints
(1), Some prior works studied the implicit bias of linear networks in
4

---

Under review as a conference paper at ICLR 2022
in Problem 1 implies: (1) Minimizing ||8||2 for fully-connected networks; (2) Minimizing || for depth-L diagonal networks; (3) Minimizing || 12/2 for depth-L convolutional networks with full-dimensional filters, where 3 are the Fourier coefficients of B. However, these implications may not hold if GF converges KKT point which is not global optimum of Problem
For some classes of linear networks. positive results were obtained directly in the predictor space, without assuming convergence to global optimum of Problem I in the parameter space. Most notably, for fully-connected linear networks (of any depth), Ji & Telgarsky (020)) showed that under the assumptions of Thm. 2. GF maximizes the l2 margin in the predictor space. Note that margin maximization in the predictor space does not necessarily imply margin maximization in the parameter space. Moreover, some results on the implicit bias in the predictor space of linear convolutional networks with full-dimensional convolutional filters are given in Gunasekar et al. (0188). However, the architecture and set of assumptions are different than what we focus on.
FULLY-CONNECTED NETWORKS
First, we show that fully-connected linear networks converge to global optimum of Problem
Theorem 3.1. Let m 2 2 and let be a depth-m fully-connected linear network parameterized by O. Consider minimizing either the exponential or the logistic loss over a dataset {(x,, B.)) using GF. Assume that there exists time to such that [(O(tu)) < 1. Then, GF converges in direction to a global optimum of Problem]
Proof idea (for the complete proof see Appendix C.2 Building on results from Ji & Telgarsky 2020) and Du et al. (2018), we show that GF converges in direction to KKT point O (W .r.,,,.., [mm) such that for every 1 E [m] we have W(() = C .vV where C > 0 and W C.
Vo.... Vm are unit vectors (with Vn. 1). Also, we have [[ min ||||| s.t. y,u x; 2 1 for all E [n]. Then, we show that every 0 that satisfies these proper- ties, and satisfies the constraints of Problem[[] is global optimum. Intuitively, the most "efficient" way (in terms of minimizing the parameters) to achieve margin with linear fully-connected net- work, is by using network such that the direction of its corresponding linear predictor maximizes the margin, the layers are balanced (i.e., have equal norms), and the weight matrices are aligned. Li
We now prove that the positive result in Thm. 3.1 does not apply to ReLU networks. We show that in d fully-connected ReLUU networks GF might converge in direction to KKT point of Problem [ which is not even a local optimum. Moreover, it occurs under conditions holding with constant probability over reasonable random initializations.
Theorem 3.2. Let & be 2eptth-2,flll--comee fully-connected ReLU network with input dimension 2 and two hidden neurons. Namely, for 0 = [W1, W2, v] and x E IR² we have 4(0; x) = =i= 1 via(w (w, x). Consider minimizing either the exponential or the logistic loss using GF. Consider the dataset ((11.1)): (x2, }2)} where X1 = (1,
= (-1, and = y22 = 1. Assume that the initialization (0) is such that for every E 21 we have (w (0), x.) > 0 and (02(0),x, x,) < O. Also, assume that 1i (0) > Then, GF converges to zero loss, and converges in direction to KKT
point of Problem] 7 which is not local optimum.
Proof idea (for the complete proof see Appendix on the given dataset, we show that it converges to zero loss, and converges in direction to KKT point 0 such
By
analyzing
the dynamics of GF
15
(1((2)
that W1 = (0,2) 2) 0 2, W = 0, and 02 = 0. Note that We and 622 0 since w wz2(t), (t) remain constant during the training and lim [t) = 0c.
1.
X2
0.
My(t,)
X1
This is illustrated in the figure on the right: For time \ we denote u, (L) = vi (t). We observe un (1), (2(
-1.
-0.5
0.5
1.
for times t t2. As - oo we have [[,,(t) + 00 and u converges in direction to (0, 1). The vector
005
Mz((t) = M2((2)
remains constant during the training. Hence
uz(() [
0.
5

---

Under review as a conference paper at ICLR 2022
Then, we show that for every 0 < < 1 there exists some O' such that ||0' - Ø11 S O' satisfies y: (0';)) 2 for every i E (1,2), and ||0'|| < ||@]|. Such O' is obtained from i by slightly changing W1, W2, and U2. Thus, by using the second hidden neuron, which is not active in 6, we can obtain a solution 0' with smaller norm.
We note that the assumption on the initialization in the above theorem holds with constant probability for standard initialization schemes (e.g., Xavier initialization).
Remark 3.1 (Unbounded sub-optimality). By choosing appropriate inputs X1,X5 in the setting of Thm. 3.2 it is not hard to show that the sub-optimality of the KKT point w.rt. the global optimum can be arbitrarily large. Namely, for every large M > 0 we can choose a dataset where the angle
| between X1 and X2 is sufficiently close to т, such that -0- 2 M, where @ is a KKT point to which GF converges, and 0* is a global optimum of Problem Indeed, as illustrated in the figure from the proof idea of Thm. 3.2 if one neuron active on both inputs and the other neuron not active on any input, then the active neuron needs to be very large in order to achieve margin 1, while if each neuron is active on single input then we can achieve margin 1 with much smaller parameters. We note that such unbounded sub-optimality can be obtained also in other negative results in this work (.4)
(in Thm. 4.1
Remark 3.2 (Robustness to small perturbations). Thm. 3.2 holds even if we slightly perturb the imputs X1, X2. Thus, it is not sensitive to small changes in the dataset. We note that such robustness
to small perturbations can be shown also for the negative results in Thm. 4.1 4.3 5.1 and
4 DEPTH-2 NETWORKS IN N
In this section we study depth-2 linear and ReLU networks in N. We first show that already for linear networks Nua-shore (more specifically, for diagonal networks) GF may not converge even to a local optimum.
Theorem 4.1. Let & be depth-2 linear or ReLU diagonal neural network parameterized by 0 [W1, W2). Consider minimizing either the exponential or the logistic loss using GF. There exists dataset ((x, IR2 x [1] of size and an initialization (()), such that GF converges to zero loss, and converges in direction to a KKT point @ of Problem [ which is not local optimum.
Proof idea (for the complete proof see Appendix C.4 Let x = (1 and y = 1. Let ( such that w (0) (2) (1, Recalling that the diagonal network computes the function x (W) o )2) T x (where o is the entry-wise product), we see that the second coordinate remains inactive during training. It is not hard to show that GF converges to the KKT point Ô with W1 W = (1, However, it is not local optimum, since for small c the parameters O' [w'), w/] with w| w/2 (vI (vI-vvi-,, (
satisfy the constraints of Problem and we have ||0'|| |0||
By Thm. 3.2 fully-connected ReLU networks may not converge to a local optimum, and by Thm. linear (and ReLU) networks with sparse weights may not converge to local optimum. In the proofs of both of these negative results, GF converges to a KKT point such that one of the weights vectors of the hidden neurons is zero. However, in practice gradient descent often converges to network that does not contain such disconnected neurons. Hence, natural question is whether the negative results hold also in networks that do not contain neurons whose weights vector is zero. In the following theorem we show that in linear networks such an assumption allows us to obtain a positive result. Namely, in depth-2 linear networks in Nno-starce if GF converges in direction to a KKT point of Problem I that satisfies this condition, then it is guaranteed to be a global optimum. However, we also show that in ReLU networks assuming that all neurons have non-zero weights not sufficient.
Theorem 4.2. We have:
1. Let 4 be depth-2 2 linear neural network in Nno-share parameterized by 0. Consider minimizing either the exponential or the logistic loss over a dataset ((x,, u:) using GF. Assume that there exists time to such that ((((tt)) < 1, and let ① be the KKT point of Problem 1 such that O(1 converges @ in direction (such ① exists by Thm. 2.1 Assume that in the network

---

Under review as a conference paper at ICLR 2022
parameterized by θ all hidden neurons have non-zero incoming weights vectors. Then, O is global optimum of Problem !
2. Let & be fullly-connetedd depth-2 ReLU network with input dimension 2 and 4 hidden neurons, parameterized by 0. Consider minimizing either the exponential or the logistic loss using GF. There exists a dataset and an initialization (()), such that GF converges to zero loss, and converges in direction a KKT point 0 of Problem ] which not a local optimum, and in the network parameterized by all hidden neurons have non-zero incoming weights.
We give here the proof idea for part (I). Let k be the width of the network. For every j E [k] we denote by w the incoming weights vector to the j-th hidden neuron, and by fy the outgoing weight. Let uj " w. We consider optimization problem over the variables u1,..., ur where the objective is to minimize Σje(a) ||u,|| and the
Proof idea (for the complete proof see Appendix C.5
constrains correspond to the constraints of Problem | Let 0 [W....., Wk. v] be the KKT point of Problem [ which GF converges in direction. For every j [K] we denote új = ëg w. We show that új,... Ug satisfy the KKT conditions of the aforementioned problem. Since the objective there is convex and the constrains affine, then it is global optimum. Finally, show that it implies global optimality of 0.
Remark 4.1 (Implications on margin maximization in the predictor space for diagonal linear net- works). Thm. annddd22 imply analogous results on diagonal linear networks also in the predictor space. As discussed in Section 2 Gunasekar et al. (2018b) showed that in depth-2 diagonal lin- ear networks, minimizing ||0|| under the constraints in Problem 7 implies minimizing 1|33]] where 3 is the corresponding linear predictor. Thm. 4.1 can be easily extended to the predictor space. namely, GF 2 linear diagonal networks might converge to a KKT point O of Problem 1 such that the corresponding linear predictor B3r is not a local optimum of the following problem:
arg min ||
s.t.
Vi E [m] 1.13. x.) 21.
3
Moreover, by combining part (1) of Thm_ 4.2 with the resuli from Gunasekar el al. (2018b), we de- duce that if GF on depth-2 diagonal linear network converges to a KKT point @ of Problem / with non-zero weights vectors, then the corresponding linear predictor is a global optimum of Problem
By part (2) of Thm. 4.2 assuming that GF converges to a network without zero neurons is not sufficient for obtaining a positive result in the case of ReLU networks. Hence, we now consider a stronger assumption, namely, that the KKT point 0 is such that for every x; in the dataset the inputs to all hidden neurons in the computation & 0 x:) are non-zero. In the following theorem we show that in depth-2 ReLU networks, if the KKT point satisfies this condition then it is guaranteed to be a local optimum of Problem [] However, even under this condition it is not necessarily global optimum. The proof is given in Appendix C.6 and uses ideas from the previous proofs, with some required modifications.
Theorem 4.3. Let & be 2epth-2 ReLU network in Nno-share parameterized by O. Consider mini- mizing either the exponential or the logistic loss over a dataset {(x,, u:) ) using GF. Assume that there exists time to such that L(O(t))) < 1, and let 0 be the KKT point of Problem I such that (
converges to Ô in direction (such ① exists by Thm. 2.1. Assume that for every i E [n]] the imputs to all hidden neurons in the computation कb (0;;;; xx) are non-zero. Then, i is a local optimum of Problem !
However; it may not be global optimum, even if the network &b is fully connected.
Note that in all the above theorems we do not allow shared weights. We now consider the case of 22pth-2 linear or ReLU networks in N, where the first layer is convolutional with disjoint patches (and hence has shared weights), and show that GF does not always converge in direction to local optimum, even when the inputs to all hidden neurons are non-zero (and hence there are no zero weights vectors).
Theorem 4.4. Let &e be a 2epth-2 linear or ReLU network in N. parameterized by 0 = [w, v. for W. E I2, such that for x E R2 we have 400xx) Σ ujo( T x(0) where (1) (æ1, (2) and (2) = (s). Thus, db is a convolutional network with two disjoint patches. Consider mini- mizing the exponential or the logistic loss using GF. Then, there exists dataset ((X, v)} of size 1,
7

---

Under review as a conference paper at ICLR 2022
and an initialization (0), such that GF converges to zero loss, and converges in direction to KKT
point f [ of which is not local optimum. Moreover, (wr, (w,x()) # ff j E {1,2).
Proof idea (for the complete proof see Appendix C.7 Let x = (4, /2: /2 and y = 1. Let
(0) such that w(0) = (0, and v(0) = /22 v2 Since x()) and x(2) are symmetric w.r.t
w (()), and v(0) does not break this symmetry, then w keeps its direction throughout the training. T
Thus, GF converges in direction to KKT point 0 where w = -0, 1)_ and V
+ It is not ( v2
a local optimum, since for every small > the parameters 0' = [w' v'I with w' (VC, T)T
and v = 1/22 2 12 Ve)
satisfy the constraints of Problem and ||0'|| < Ø||
DEEP NETWORKS IN A
In this section we study the more general case of depth-m neural networks in N,, where m 2 First, we show that for networks of depth at least 3 in N Noo-share. GF may not converge to a local optimum of Problem D for both linear and ReLU networks, and even where there are no zero weights vectors and the inputs to all hidden neurons are non-zero. We prove this claim for diagonal networks.
Theorem 5.1. Let m 2 3. Let & be a depth-m linear or ReLU diagonal neural network parame- terized by 0. Consider minimizing either the exponential or the logistic loss using GF. There exists a dataset {(x, f)} S R² x {-1.1} of size 1 and an initialization (()), such that GF converges to zero loss, and converges in direction to a KKT point 1 of Problem !
which is not a local optimum. Moreover, all imputs to neurons in the computation (00; x) are non-zero.
Proof idea (for the complete proof see Appendix C.8 Let x = (1, T) and y = 1. Consider the initialization (() where (0) (1,1) for every j E [m.) We show that GF converges in di-
rection to a KKT point Ô Wi..... Wml such that w (2 (2-1/m, 2 2-1/m) for all j [m]] Then, we consider the parameters 0' = [w',..., w'nl such that for every j E [m]] we have
w = ( 1/m (z
and show that e > is sufficiently small, then 0' satisfies the constraints in Problem 1 and we have ||0'|| |0||-
Note that in the case of linear networks, the above result is in contrast to networks with sparse weights of depth that converge to a global optimum by Thm. 4.2. and fully-connected networks of any depth that converge to a global optimum by Thm. 3.1 In the case of ReLU networks, the
above result in contrast to the case of depth-2 2 networks studied in Thm. 4.3 where it is guaranteed to converge to a local optimum.
In light of our negative results, we now consider a weaker notion of margin maximization, namely, maximizing the margin for each layer separately. Let & be network of depth m in parameterized
by 0 [m The maximum-margin problem for layer lo [m]] w.r.t. Og [ug I is:
(0)
min u
(fo)
Vi [n] s.t.
D, D00 x 21,
(3)
2
where 0' = [[ up
(1)
No
1) (o)) Up (lo+1) ,..., up (.)). For linear networks we have the following:
Theorem 5.2. Let > 2. Let & be any depth-m linear neural network in N. parameterized
by Jm Consider minimizing either the exponential or the logistic loss over a dataset
{(x,, y:) 1 using GF. Assume that there exists time to such that L(((to)) < 1. Then, GF converges in direction to KKT point θ [m0) of Problem T such that for every layer I E [m] the parameters vector (!) is a global optimum of Problem w.r.l. O.
The theorem follows by noticing that if o is a linear network, then the constraints in Problem 3 affine, and its KKT conditions are implied by the KKT conditions of Problem [[ See Appendix C.9 for the formal proof. By Thm. 4.1 and 5.1 linear networks in A might converge a KKT point
8

---

Under review as a conference paper at ICLR 2022
0 which is not local optimum of Problem However, by Thm. 5.2 each layer in @ is global optimum of Problem Thus, any improvement to 0 requires changing few layers simultancously.
While in linear networks GF maximize the margin for each layer separately, in the following theorem show that this claim does not hold for ReLU networks: Already for fully-connected networks of depth 2 GF may not converge to a local optimum of Problem 33 Appendix [C10ffor the proof). Theorem 5.3. Let & be fully-connected depth-2 ReLU network with input dimension 2 and 4 hidden neurons parameterized by Consider minimizing mininiing either the exponential or the logistic loss using GF. There exists dataset and an initialization (0) such that GF converges to zero loss, and converges in direction to KKT point @ of Problem 1 local optimum of Problem 3 w.r.t. O.
such that the weights of the first layer not
Finally, we show that in ReLUU networks in /N of any depth, if the KKT point to which GF converges in direction is such that the inputs to hidden neurons are non-zero, then it must be a local optimum of Problem 3 (but not necessarily a global optimum). The proof follows the ideas from the proof of
Thm. 5.2 with some required modifications, and is given in Appendix C.I1
Theorem 5.4. Let
2. Let & be any depth-m ReLU network in N parameterized by [u 10 Consider minimizing either the exponential or the logistic loss over a dataset (s), using GF, and assume that there exists time to such that [(A(tn)) < 1. Let = 0- [m be the KKT point of Problem I such that (t) converges to θ direction (such
exists by Thm. 2.7). Let I E [m]] and assume that for every E [n] the inputs to all neurons in layers
2 in the computation (00 xi) are non-zero. Then, the parameters vector ú!)) is a local optimum of Problem 3 w.r.. 0. However, may not be global optimum.
6 NON-HOMOGENNOOUS NETWORKS
be the normalized margin. If ② is homogeneous then maxi- mizing- (0) is equivalent to solving Problem [ i.e., minimizing ||0]] under the constraints (cf. Lyu
Let (0) := min 4 [|]]] :x)
Li 2019) In this section we study the normalized margin in non-homogeneous networks.
Lyu & Li 2019) showed under the assumptions from Thm. 2.1 that smoothed version of the normalized margin is monotonically increasing when training homogeneous networks. More pre-
cisely, there is function (0) which is an O ( -additive approximation of (()), such that
(0) is monotonically non-decreusing. This result does not apply to non non- non-hooggenouus networks, such as networks with skip connections or bias terms. Lyu & Li (2019) observed empirically that the normalized margin is monotonically increasing also when training non- non-homogeneous networks. However, they did not provide a proof for this phenomenon and left as an open problem. Their experiments are training convolutional neural networks (CNN) with bias MNIST. In the fol- lowing theorem we show an example for a simple non-homogeneous network where the normalized margin is monotonically decreasing during the training. This example implies that in order obtain such a result for non- non-homogee mon-hoogeenouss networks some additional assumptions must be made.
Theorem 6.1. Let & be depth-2 linear network with input dimension width 1 and skip connec- tion. Namely, is parameterized by f = [w, u. u] where w, v, u E RR and (0; x) = v w x +2+00 u xr. Consider the size-1 dataset {(1, 1)}, and assume that (0) = 2,, Then, GF w.r.t. either the ponential loss or the logistic loss converges to zero loss, converges in direction (i.e., lim;
0(t)
[
exists), and the normalized margin is monotonically decreasing during the training, i.e., dt
45(0(t)) 0
for all t 2 O. Moreover, we have (((()) > 0.9 and lim,- ((()))
We note that the proof readily extends in a few directions: It applies also for depth-2 network without a skip connection but with a bias term in the output neuron. In addition, it also holds for ReLU networks. Finally, the theorem applies also for the smoothed version of the normalized margin considered in Lyu & Li (2019). The proof of the theorem is given in Appendix [C.12 Intuitively.
| | vs then (0) 3. Also, since the partial derivative of the loss w.r.t. v, w depends on w, v (respectively) and on x, and the partial derivative w.r.t. u depends only on æ. then v, w grow faster than u during the training. Hence, t increases, Tell decreases and [0 ||]]
note that if [ |o
and |Ø I then (0) 1, and if T O and
increase.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pp. 7413-7424, 2019.
Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson. Blake Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. arXiv preprint arXiv:2102.09769 2021.
Mohamed Ali Belabbas. On implicit regularization: Morse functions and applications matrix factorization. arXiv preprini wrXiv:2001.04264, 2020.
Lenaic Chizat and Francis Bach. Implicit bias of geraddentdescenn for wide two-layer neural networks trained with the logistic loss. arXiv preprint (rXXi::0002.044886. 2020.
Francis H Clarke, Yuri Ledyaev, Ronald Stern, and Peter R Wolenski. Nonsmooth analysis and control theory, volume 178, Springer Science & Business Media, 2008
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In Advances in Neural Information Processing Sys- fems, pp. 384-395, 2018
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, 56(4): 1463-149,, 2013.
Armin Eftekhari and Konstantinos Zygalakis, Implicit regularization in matrix sensing; A geometric view leads stronger results. arXiv preprint arXiv:2008. 12091, 2020.
Gauthier Gidel, Francis Bach, and Simon Lacoste-Juliee Implicit regularization of discrete gradient dynamics in linear neural networks. In Advances in Neural Information Processing Systems, pp. 3202-3211, 2019.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprint /00.008802002466. 201 8a.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp- 9461-9471,2011 2018b.
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-10. IEEE, 2018c.
Meena Jagadeesan, Ilya Razenshteyn, and Suriya Gunasekar. Inductive bias of multi-channel linear convolutional networks with bounded weight norm. arXiv preprint 1rXiv:2102.122:: 2021.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv:1810.0000 02002, 2018a.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 10030:0000.07300, 2018b.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006. 266,020000.06677, 2020.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via a primal-dual analysis. In Algo- rithmic Learning Theory, pp. 772-804, PMLR, 2021.
Ziwei Ji, Miroslav Dudík, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pp. 2109-2136. PMLR, 2020.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over pee-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning The- ory, pp. 2-47. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2022
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint arXiv:2012.09839, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. 2019.
arXiv preprini 1rXiv:1906.000
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex sta- tistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 3345-3354, PMLR, 2018.
Edward Moroshko, Blake E Woodworth, Suriya Gunasckar, Jason Lee, Nati Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale training accuracy. Ad- vances Neural Information Processing Systems, 33, 2020.
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference Machine Learning, pp.
PMLR, 2019a.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasckar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. The 22nd International Conference Artificial Intelligence and Statistics, pp. 3420-3428, PMLR, 2019b.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1412.6664166. 2014.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization deep learning. In Advances Neural Information Processing Systems, pp. 5947-5956, 2017.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms, arXiv preprint arXiv:2005.065 06399, 2020.
Andrzej Ruszczynski. Nonlinear optimization. Princeton university press, 2011.
Ohad Shamir. Gradient methods never overfit on separable data, arXiv preprint arXiv:2007.00028
2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018.
Gal Vardi and Ohad Shamir. Implicit regularization in relu networks with the square loss. In Con- ference on Learning Theory, pp. 4224 4258. PMLR, 2021.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. arXiv preprint arXiv:2002.00927 2020.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. arXiv preprint arXiv:2010.02501, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: /6/ 1ot/11//1..00 1.05530, 2016.
A MORE RELATED WORK
Soudry et al. (0018) showed that gradient descent on linearly-separable binary classification prob- lems with exponentially-taile losses (e.g., the exponential loss and the logistic loss), converges to
the maximum l m-rmann direction. This analysis was extended to other loss functions, tighter con-
vergence rates, non-separable data, and variants of mudient-based optimization algorithms (Nacson
et al.] 20196; Ji & Telgarsky 2018b; Ji et al. 2020 Gunasekar et al.) 2018a Shamir 2020 & Telgarsky 2021).

---

Under review as a conference paper at ICLR 2022
As detailed in Section Lyu & Li (2019) and Ji & Telgarsky (2200) showed that GF homo- geneous neural networks with exponential-type losses converge in direction to a KKT point of the maximum margin problem in the parameter space. Similar results under stronger assumptions were previously obtained in Nacson et al. (2199)); Gunasekar et al. (2018b). The implications of margin maximization in the parameter space the implicit bias in the predictor space for linear neural networks were studied in Gunassekar et al. (2018b) (as detailed in Section 2 and also in Jagadeesan al. (2021). Margin maximization in the predictor space for fully-connected linear networks was shown by Ji & Telgarsky (2020) (as detailed in Section 2). and similar results under stronger assump- tions were previously established in Gunasekar et al. (2018b) and Ji & Telgarsky/ (2018a). The implicit bias in the predictor space of diagonal and convolutional linear networks was studied in Gu- nasekar et al. (201 8b); Moroshko et al. (2020): Yun et al. 2020). The implicit bias infinitelywwide
two-layer homogeneous neural networks was studied in Chizat & Bach (2020).
Finally, the implicit bias of neural networks in regression tasks w.r.t. the square loss was also ex- tensively studied in recent years (e.g.. G...asuua et al. (2018c); Razin & Cohen (2020); Arora et al.
(2019); [Belabbas| (2020); Efttkhari & Zygalakis (2020); Li et al. (2018); Ma et al. (2018) Wood-
worth et al. (2020); Gidel et al. (2019); Li et al. (2020); Yun et al. (2020); Vardi & Shamir (202))
Azulay et al. (2021)). This setting, however, is less relevant for our work.
B PRELIMINARIES ON THE KKT CONDITION
Below we review the definition of the KKT condition for non-smooth optimization problems (cf.
Lyu & Li (2019);] Dutta et al. (2013)).
Let f _R + R be locally Lipschitz function. The Clarke subdifferential Clarke et al. 2008
x E Rd is the convex set
8 f(x) = conv L
lim fx(x;) lim x, = x, f differentiable at x i-+00
If f is continuously differentiable at x then 0 fx(x) fxx()))
Consider the following optimization problem
min f(x S.t. Vn E [N] gn (x) S 0,
where S J. point of Problem if x satisfies gn (x) S 0 for all n E [N]. We say that a feasible point x is a KKT point if there exists .1,...,A4 AN 2 0 such that
In Rd R locally Lipschitz functions. We say that x Rd is feasible
1. 0 E 0 f(x) EmE[N An (x);
2. For all n [N] we have (x) O.
C PROOFS
C.I AUXILIARY LEMMAS
Throughout our proofs we use the following two lemmas from Du al. (0188:
Lemma C.1 (uu et al. (2018). ). Let m 2 2, and let &b be a depth-m m fully-connected linear or ReLU network parameterized by = [:,.... W.). Suppose that for every j E [m]] we have W; E &ddixd; 1. Consider minimizing any differentiable loss function (e.g. the exponential or the logistic loss) over a dataset using GF. Then, for every j E [m 1] at all time I we have
di (IW31²
d
I 11 0.
Moreover, for every j E [m 1] and i E [dy] we have
(1 :1I - I1 ai =0,
dt
where W, Wi. the i-th row of W2). and W Witale. column of W 1)
:] is the vector of incoming weights the i-th neuron in the j-th hidden layer (i.e.,
[: i] is the vector of outgoing weights from this neuron (i.e., the i-th
12

---

Under review as a conference paper at ICLR 2022
Lemma C.2 Du al. 2018 ) Let m 2, and let o be depth-m linear ReLU network in N, parameterized by = l
u u. Consider minimizing any differentiable loss function (e.g., the exponential the logistic loss) over dataset using GF. Then, for every [m - 1] at all time t we have
d dt -1
|uott|| -1o = 0.
Note that Lemma C.2 considers a larger family of neural networks since it allows sparse and shared weights, but Lemma C.I gives a stronger guarantee, since it implies balancedness between the in- coming and outgoing weights of each hidden neuron separately. In our proofs we will also need to use a balancedness property for each hidden neuron separately in depth-2 networks with sparse weights. Since this property is not implied by the above lemmas from Du et al. (2018), we now prove it.
Before stating the lemma, let introduce in Noe-sture We can always assume w.l.o.g. that the second layer is fully connected, namely, all hidden neurons
required notations. Let O be depth-2 network
connected the output neuron. Indeed, otherwise we can ignore the neurons that are not connected to the output neuron. For the network & we use the parameterization [W1.-..; Wa: vj. where is the number of hidden neurons. For every j E [k] the vector w, RR,, is the weights vector of the j-th hidden neuron, and we have 1 S S d where is the input dimention. For an input x E Rd we denote by x E IRPs a sub-vector of x, such that x' includes the coordinates of x that connected the j-th hidden neuron. Thus, given x, the input the j-th hidden neuron is xw). The vector E R is the weights vector of the second layer. Overall, we have & @ = ΣjE( (W, x)).
Lemma C.3. Let be a depth-2 linear or ReLU network in Nno-share parameterized by O [Wi...., Wk, vl. Consider minimizing any differentiable loss function (e.g. the exponential or the logistic loss) over a dataset using GF. Then, for every j E [k] at all time we have
d (1w,ll²- 03) =0. di
Proof. We have
((0) = Σ (g.0(0:x,))
= Σ &
y: Σ
(wo (x(x
:E(m]
xE [m]
[E[K]
Hence
dt (1wr,1²² = 2(W,, dwj
2((,, ww, (()))
dt
- Σ
yi Σ (w x()
[E(K]
= - Σ
uo x()
[.,jo(W]x()
1/4
[E(K]
Moreover,
d
dup
(03)
20g
20, C(0)
dt
dt
2ug Σ El
y4 Σ
mawwT x())
-uo((w] x!)
iE[n]
[E[K]
Hence the lemma follows.
Using the above lemma, show the following:
13

---

Under review as a conference paper at ICLR 2022
Lemma C.4. Let & be depth-2 linear ReLU network in Nno-share. parameterized by 0 (Wi...., Wk: vl. Consider minimizing any differentiable loss function (e.g. g., the exponential or the logistic loss) over dataset using GF starting from (().. Assume that lim [|0(t)]
and
that (t) converges in direction to 0 [W....., Wk. VI. i.e. 0 - =100|| lim [
O(t) Then, for
every 1 E [k] we have |wrll = 10,|-
Proof. For every 1 [k]. let A |w: (0) By Lemma C.3
have for every 1 [R]
and 2 0 that [t)l (t)) A. namely. the differences between the square norms of the incoming and outgoing weights of each hidden neuron remain constant during the training. Hence,
we have
[w)] A |((1))]
[x)(t)
|
|||| lim
||0|| lim
[O(II]
Thus, si [wr[t)] oc, then have jöy ||0| lim,
[witt)l [[({)]]
||wll
Assume now that [[w;()) A co. By the definition of i we have
[wll
||0|| lim
I [o(e)]
Since lim;-00
(O exists and lim [ = oc, then we have lim,
[w((
0. Hence,
[000
lim;
[xx(0]]
lim
(l) 0. Therefore ||wll ōt 0.
[0(1]
[8()
C.2 PROOF OF THM.
Suppose that the network is parameterized by 0 = [W(11, W(m) By Thm. 2.1 GF converges
in direction to a KKT point 0 [W W(m]] of Problem For every 1 E [m]] let A
| (0)] (I fe
By Lemma C.I
have for every l E [m]] and that
w (t)
w (+)
Σ W (()
- -1|m(000))
(0)+ (0) - (w)
=||
-1 =
=
Hence, we have
| ||0||
(1) + +
(r() F
||0||
lim
lim
|(({t)l
100
|1(tt]l
Since by Thm.
2.1 we have lim, ||0(t)]] = co, then lim
[[w() co, and we have
[W
|
||0|| lim
|| C
[0(())
Ji & Telgarsky (2000) (Proposition 4.4), when GF on a connecco linear network w.r.t. the exponential loss or the logistic loss converges zero loss, then have the following. There are unit vectors Vo...., Vm such that
W [
lim
v
for every E [m]. Moreover, we have Vn = 1, and Vo where
arg max min you x; ||a|=| *E(m]
the unique linear max margin predictor.
Note that we have
())
1/
||0|
((l(()) lim,
((
[[(e)]
lim
vivi11
C
w
||@||
lim
[(()))]] [[(e)]]
[
14

---

Lemma C.5. Let a,,...,0m am be real numbers such that [[5[mm] aj 2 c. for some C' 2 0. Then Ejelm) ag 2 C². Under review as a conference paper at ICLR 2022
Thus, W Cvivi-1 for every I E [m].
Let W/(m)........ ..... WW() = u. Since 0 a KKT point of Problem
we have for every E [m]]
(+ x;) OW()) .
V = Σ
Ayy
se|n
where X; 2 0 for every i, and X; = 0 yb x;) + 1. Since W7(1) are non-zero then there is E [n]]
such that y: (0; x,) = y;u x, = yn u X4. Likewise, since 0 satisfies the constraints of
Problem then for every i E [n] we have S ys (6: x;) y.C" u X;- Since, is a unit vector that maximized the margin, then we have
C min ||'|l s.t. you' x; for all E [n]
Assume toward contradiction that there is O' with ||''ll < ||0|| that satisfies the constraints in Prob- lem 1 Let u' W7(m) W By Eq. we have ||u'|| 2 ||شت| C Moreover, have
Iu'
[
W I [[e[m]] W ll due to the submultiplicatiiit of the Frobenius
norm. Hence [m]
|
2 C The following lemma implies that
10'1l = Σ
w 12 mmmmC C2 = Σ
2
2 0
[E(m]
[E|m]
in contradiction to our assumption, and thus completes the proof.
Proof. It suffices to prove the claim for the case where [[ = -O" Indeed, II aj > C then we can replace some 0, with an appropriate a' such that layI < layl and we only decrease Eje(m) az. Consider the following problem
min Σ JEIM]
s.t.
II jE[m]
0j
CT Cm
Using the Lagrange multipliers we obtain that there is some E such that for every 1 E [m] we have = A 11, aj- Thus, of = X [[)e(m) aj- It implies that aî a Since ] aj = T then layl C for every j E [m). Hence, Ejelm a² mC²
C.3 PROOF OF THM.
Consider an initialization ((0) is such that w (0) satisfies (w) x1) > and (w (0)(0), x2) > O, and (2) satisfies (W2(0), x1) < 0 and (w2(0), x2) < O. Moreover, assume that in (0) > 0.
Note that for every such that (W2, X1) < 0 and (W2, X2) < we have
V C(0)
E' (',y, Daw Σ
el (g144(():x)) 3i Vw [Mlo(W] x;) + (w)
2
Σ
(y, - y:220'wW] (w]x,)x; = =0
1=1
and
2 ((,:((0:x))) V., ((0xx;) = Σ
V by (())
((;))(())))) V.V. [olo(w]xx (e()))))))-) + (2o xx)
1=1
Σ (v: gid =0
15

---

Under review as a conference paper at ICLR 2022
Hence, W2 and 02 get stuck in their initial values. Moreover, we have
V., ((, - Σ l (v::((0:))) yi v., [uro(w]] x;) + 020 x:) Σ ( xw]]x SO.
Therefore, for every / we have 1i (1) 2 (0) 0.
We denote Wi = -wi] [1] wi [2]). Since (wi(0), xj) > 0 for j E [1,2) then wn [2] > 0. Assume
w.l.o.g. that wi (0) 0 (the case where wi (0) 0 is similar). For every Wi that satisfies
wi [2] 2 0 and 0 S wi [1] < wi[l](0) we have (WI.XI) > (W1,x2) > 0. Thus,
V w. w(,
Σ ((:1((0:)))) V (iio(w]x))) (20 x:)
i=1
Σ ((s((1o(((]x)) 0j) yiund'(w] x;)x;
Σ ((vww xx) 01x,
Since E' negative and monotonically increasing, and since U1 di x1 > W1
x2, then dwo I 0.
Also, dun > O. Moreover, if [1] 0 then vi w Ui w and thus dwi(l] O. Hence, for every we have wi [2](1)= 2 w1 (0)
di
and S w1 (1] S wi (1).
If ()) 21 1 then for some i E [1, 2} we have E(v, (O; x)) 2
and hence ((;x,)) S c for
some constant < Since we also have 11 2 (0) > 0, we have
dw [2] 2 c. U1 (0)
Therefore, if the initialization (()) is such that (()) 2 then w/ (2] increases at rate at least (-c)-e1(0) while wi [t](t) remains in [0, wi [O]( Note that for such w1 w1[1] and e1 2 (0) >> 0, if wil is sufficiently large then we have in (WI.x,) 2 for E {1,2]. Hence, there is some to such that L(O(to)) S 21(1) < 1 for both the exponential loss and the logistic loss.
Therefore, by Thm. 2.1 GF converges in direction to a KKT point of Problem I and we have lim (()()) 0 and lim [[@(t)] Co. It remains to show that it does not converge in direction to a local optimum of Problem
Let 0 = lim o(t)
/2 (2,0 1) 01 [[@()]] We denote 0 [w. W2, 01, Ø2). We show that W1 = 1.2 (0,
V2 W2 0 and 02 0. By Lemma C.1 we have for every t 2 O that (t)²
(1)l
2i (0)2 ||w, (0)]l² A. Since for every t we have W2(t) w2( and 02 (t) (0). and since
lim [0(1]] = x then we have lom [ [I]] = oo and lim (ni [t) = xc. Also, since
lim
[[]] do and w1 [1]((( [0, wa [1](]]] then lim, w1 (1) cc. Note that
[[0(t)] / [|)](())) + (1)2 + (0)] + (0) / w1 (f)) [|]] + (0)
Since wy [1][((t) E [0, wi [o) and [0())] - oc, we have
wi [1]
wi lim
[((t]] = 0.
Moreover,
Wi (t)
(w) [2 (t))²
1
W 12
lim
lim (+000
A + 2(w) [1][)]]]))))))))))) + 2(( (1)) + 2|
V2
and
W2(t)
(0 0.
W2 = lim
lim
0(11
[(()]
16

---

Under review as a conference paper at ICLR 2022
Finally, by Lemma C.4 and since i1 (t) O, have ||1ll
By Lemma C.4 also V2
have [62 = [22l || 0.
Next, we show that 0 does not point at the direction of a local optimum of Problem | Let = [W1, W2, 81, 02] be a KKT point of Problem that points at the direction of 0. Such 0 exists since (t) converges in direction to KKT point. Thus, we have Wa 0, d22 O, W1 a(0, 1)T and
d1 a for some a > O. Since satisfies the KKT conditions, we have
W Σ ==1
V.V w. (1:((0xxi) = E deys (010' x,)x.). 1=1
where X; 2 0 and X = 0 if y (0;x;; * Note that the KKT condition should be w.r.t. the Clarke subdifferential, but since W X, > 0 for E {1,2} then we use here the gradient. Hence, there is i {1, such that y, v x;) 1. Thus,
a +0= a² 4 4
1 = (0: x;) = ( x;) + i20 wx)x)) x;)
a.
Therefore, 2 and we have W1 (0,2) and ú1 2.
In order to show that @ is not local optimum, we show that for every 0 < e' < ttere exists some
O' such that
0' 0 e', O' satisfies (0'; x;) 2 for every E [1, 2}. and ||0'| < ||0||- Let
c= 9 < 1 Let 0' = [w1. w v1. usz] be such that w/ = 2- - w/ = (-v2c, T)_ of =
2.
and 2/2 = 2c. Note that
(00;;11) = 2.0
( (2:222)(11, 2))) + .2 (-VV2,,0111 )
E
26)
cc
+ = c
+ V2e . (-v20) =1,
= =2.0 a
2
2
2
and
2- (-) (1) V2 21
((0%:22) 2
2'
1 c
V2e (VZc) -1-2e+ 22
2
2
2
We also have
6' 81 = |w(
wzll 2
+ l| w + (v/ - 02) + (0/2 02))
2
-
+ 462
+ 2e + 2c < 90 =2
4
Finally, we have
22 |10112 = +4 4
176² < 8 4e+
17c
8c
+ 4e2 2 = 4et
< 8
0
4
Thus, ||0'l| < |10||-
C.4 PROOF OF THM.
Let (1 and y 1. Let (()) such that w1( w2 T. Note that C(e(0)
((1) < 1 for both linear and ReLUU networks with the exponential loss or the logistic loss, and therefore by Thm. 2.1 GF converges in direction to KKT point Ô of Problem [ and we have lim (()(t)) = 0 and lim
[[[(t]] = oc. We denote W1 = -ww][]] w1 ) and w2 = (wz[1), 2 T. Note that the initialization ((0) is such that the second hidden neuron has 0 in both its incoming and outgoing weights. Hence, the gradient w.r.t. | and wz [2[ is zero, and the second hidden neuron remains inactive during the training. Moreover, wi [1] and wa [1] strictly
17

---

Under review as a conference paper at ICLR 2022
increasing. Also, by Lemma C.3 we have for every t 2 0 that (r( w2 Overall, O such that W1 = W2 = (1.0)' Note that since the dataset is of size 1, then every KKT point of Problem must label the input with exactly 1.
It remains show that θ is not local optimum. Let 0 < 1, and let 0' = [w1, wil with w1 w/2 = (VII -, E, v 2 Note that O' satisfies the constraints of Problem | since y (0'; =
1 E + 2 5 1. Moreover, we have ||01|2 and ||0'112 2 (1 E + 5) e and therefore
|0') < ||0||-
C.5 PROOF OF THM.
C.5.1 PROOF PART
We assume w.l.o.g. that the second layer is fully-connected, namely, all hidden neurons are con- nected to the output neuron, since otherwise we can ignore disconnected neurons. For the network we use the parameterization 0 = [ Wk. v] introduced in Section C.I Thus, we have (00; x)
[e() t/w, x'.
By Thm. 2.1 GF converges in direction to = [WI...., Wk. v which satisfies the KKT conditions
of Problem Thus, there are A1..... An such that for every j E [k] we have
A V.W,, (v.((0:x.))
Σ Xyo0zx/
(6)
sc(m]
and we have X; 0 for all i, and X 0 if y; (0;x;)) = ys EiE // x + 1. By Thm. 2.1
also have lirm,-oo [[)]] oc. Hence, by Lemma C.4 we have [W = öoy for all j E [k].
Consider the following problem
min
Jull
S.L.
[
D6
u x 1.
[C(M]
[E(A)
For every E [k] we denote úN ūn WT. Since we assume that Wi o O for every 1 E [k]. and since will [ūy]. then ū, j 0 for all / E [k]. Note that since Wi...., Wky satisfy the constraints in Problem [ then uj..... üs satisfy the constraints in the above problem. In order to show that u...... üg satisfy the KKT condition of the problem, we need to prove that for every j E [k] we have
ú
XyEx!
(8)
|
for some X/ 2 0 such that X 0 if yo [EE(K]
|ög| for U, X # 1. From Eq. 6 and since ||
every 1 E [k). we have
ü₁ ūz w J Σ <E(m)
A = i3 Σ Xiyii = 1|
Amyxx |
Xxxee//
KEin)
EE|m]
(c(n)
Note that we have X; 2 0 for all i, and A₂ = 0 if EiERy 07 x - 1 EiER ūn x 1. Hence
Eq. 8 holds with N,..., Xr that satisfy the requirement. Since the objective in Problem is convex and the constraints are affine functions, then its KKT condition is sufficient for global optimality. Namely, u,,..., üg are global optimum for problem 7
We now deduce that Ô is global optimum for Problem Assume toward contradiction that there is solution 6' = [w',..., w/: v'] for the constraints in Problem such that ||01|2 < ||0]|2. Let
u/- = =//w/- Note that the vectors un satisfy the constraints in Problem 7
Moreover, we have
||u||| Σ
< Σ
(16112 + [lw]l))
1
1
0
[ + [!wil²))
2
2
AE[R]
rE[A]
[E[R]
LE A
Since || |,c|. the above equals
Σ
|w]l
1rl | =
Σ |
[E[K]
[E(
which contradicts the global optimality of ū
u..
18

---

Under review as a conference paper at ICLR 2022
C.5.2 PROOF OF PART
Let {(x;, (:) be a dataset such that yi 1 for all E [4] and we have x
(0,1)T,
X2 (1,0) X3
(0,-1) and x; (-1,0). Consider the initialization 8(0) (W), W2(0), Wa( wa(O), v(0) such that w.(0) = 2x; and 0;(0) = 2 for every i E [4].
Note that ())
4f(4) < for both the exponential loss and the logistic loss, and there-
fore by Thm. 2.1 GF converges in direction to a KKT point of Problem 1
and we have
lim;-ro (()(t)) 0 and lim,- ||@(t)] = co.
We now show that for all 2 0 we have wt( a(t)x; and (t( a(t) where a(t) 0 and lime a(t) cc. Indeed, for such ((), for every j E [4] we have
dwj
Dro xii) [w] xx)xx))
Vw, ((0)= Σ (vxx((0xx))) y Vw, x(0xx,,
e'
dt
1=1
= ([((2)) a d'(w] x,)x =a)2) (ax))
and
duj
v,, = Σ E' (v.0(0:x,)) V., = Σ F'
Σ 1=1 1=1
(wo x,)
.o(w]x xi)
dt
1=1
= E((a)
[oww]a x,) = (((a))
Moreover, since lim |0(|)]] = oc then lime-+00 a(t) = 0c. oc.
Hence, the KKT point θ is such that for every j E [4] the vector w points the direction xj. and we have 8y = ||y Also, the vectors W1, W2, W3, Wa have equal norms. That is, w, = ãx, and 0g for some > 0. Moreover, since it satisfies the KKT condition of Problem then we have
Auy Ww, (00:),,
W
where X; 2 and X; = y (0; xx) o 1. Hence, there is such that y, x0) 1.Therefore, ã² 1. Thus, we conclude that for all j E [4] we have w, X2 and ūj 1. Note that w 7 0 for all j E [4] as required.
Next, we show that 0 is not local optimum of Problem I We show that for every < < 1 there
exists some 0' such that (or ol S e, O' satisfies the constraints of Problem and ||0'|| < ||||
Let c' 2 Let 0' be such that v/ 8n for all j E [4], and we have w = (c', 1 <'T, w² = =(1 - d' -C) w/3 = (-r', 1 + e¹)T and w¹ (-1 + + It is easy to verify that 0' satisfies the constraints. Indeed, we have (0'; = ((1 (01-5))+e0 (1- = 1. Also, we have
0' 0 = v4. 2e = 2//e'' = e. Finally,
110113= (62 (1-
- (19) 44 Se' (c'- 1) 8 10112
C.6 PROOF OF THM.
We assume w.l.o.g. that the second layer is fully-connected, namely, all hidden neurons are con- nected to the output neuron, since otherwise we can ignore disconnected neurons. For the network t we use the parameterization O = [W1...., Wk, v) introduced in Section C.1 Thus, we have + (0 x) = ΣiE(M) via(w] x²).
We denote 0 [ [..., WR. v). Since ① is KKT point of Problem then there are Ai...., An such that for every j E [k] we have
w = Σ
Vww, (v.0(0:x)))
Σ
Avnuao (w) x/)x
EE m
sE|m]
19

---

Under review as a conference paper at ICLR 2022
and we have X 2 0 for all i, and X, if y (0:xx) yo EiEWy ( x() o 1. Note that the KKT condition should be w.r.t. the Clarke subdifferential, but since for all i, we have w J x + 0 by our assumption, then we can use here the gradient. By Thm. 2.1 we also have lime-so |0(()]] = co. Hence, by Lemma C.4 we have [/w || = أرت] for all j E [k]]
For i E [n]] and j E [k] let AGj = [(w] x 2 0). Consider the following problem
min
Σ
wull
s.t.
Vi E [n] VA
Σ [E(A]
Aau, x 21
(10)
[E
For every/ / E [k] let in = By Wi Since we assume that the inputs to all neurons in the computations ④(0; (0; x.) are non-zero, then we must have w, + 0 for every E [k]. Since we also have |w/l |,y]
then U, + 0 for all / E [k]. Note that since Wi..... Wk, V satisfy the constraints in Probelm then u1 U1..... Ug satisfy the constraints in the above problem. Indeed, for every E [n]] we have
Vi Σ LE|R
Aauj x = Yi Σ 1 (w,
x 2 0)
610 W x() 2 1. LETA
[E[R]
In order to show that ui..... Un satisfy the KKT condition of Probelm every j E [k]] we have
10
we need to prove that for
Σ AyyA KE(m)
(11)
for some Mi...., X₁ such that for all we have X 2 O, and X = yi Eie(H) Auū, x * 1. From
Eq. 9 and since |/ = |oy] for every E [k], we have
ú = 8g w, = i Σ A,yeū = 03 Σ
AmM = 110
Σ
A = =1ū5ا| Σ
<E(m)
iE(n)
rE(m)
iE(m)
Note that we have X; for all i, and X; if
yi Σ Aau x = Yi Σ 6y ( x 2 0) = y
Σ LETA
( (
x 1
[E|4
LE[K]
Hence Eq. 11 holds with .,,... X₂ that satisfy the requirement. Since the objective in Problem 10 is convex and the constraints are affine functions, then its KKT condition is sufficient for global optimality. Namely, ūj..... ūn are global optimum for Problem 10
We now deduce that θ is a local optimum for Problem 1 Since for every E [n] and / E [k] we have w x! # O, then there is
O, such that for every i, and every w/ with ||w| will x 0). Assume toward contradiction that there is solution 0' -"=1a [w',... ........ w v"] for the constraints in Problem such that ||0' θ < c and ||0'|| < |00
we have 1( 1( x! 2 0)
1 [w,
Note that we have ||w - -will < c for every E [k]. We denote u' = o/ w/wl The vectors u'. satisfy the constraints
Problem 10 since we have
36 Σ Aaul [E(k]
x y/ Σ
[w]
x
O)//w X
Σ SE|A]
1( x 2 O)
[E[K]
= y/ tE(A]
via
w/ x 2 1
where the last inequality is since 0' satisfies the constraints in Probelm 1
Moreover, we have
Σ ||&||| Σ bHHll <
(1e1 + [Iwill))
| 1
(1on + llwil?))
[E(
[c
EE(A]
[E
Since
||Wr|| | the above equals
Σ
||
|w/l = Σ
|
[E(M]
[E(K]
[E[M
which contradicts the global optimality of üi...., Úg.
remains to show that θ may not be a global optimum of Problem connected. The following lemma concludes the proof.
even if the network & is fully
20

---

Under review as a conference paper at ICLR 2022
Lemma C.6. Let & be 2epth-2 fully-connected ReLU network with input dimension 2 and two hidden neurons. Consider minimizing either the exponential or the logistic loss using GF. Then, there exists dataset {(x;, Bi)li=1 and an initialization ( such that GF converges to zero loss, converges in direction to a KKT point Ô = [ W2, v] of Problem such that (W,, xi) + for all j E 21 and E [n]. and 0 is not global optimum.
-0,-000111 Proof. Let X1 (1, X2 (-1,1)) X3 = (0,-1), 11 1/2 ys 1. Let
((I1,)), v1), (x2, 122, (X3, v3)) be dataset. Consider the initialization ( such that w (0) (0,3),
21 (0) = 3, (2) = 22) and (0) = 2. Note that ((0(0)) = 2 (2) + {44) < for both the exponential loss and the logistic loss, and therefore by Thm. 2.1 GF converges in direction to a KKT point 0 of Problem
Note that for 0 such that w a. (0, and W = (0,0-11) -1) for some B > 0, and 21 U2 > 0, we have
3
V Ww (()
Σ
((;)0(0:x))) yi ww ((0;x)) Σ &' (wla(w] + u20((, x:)) m1o'(wi (w/ x;)x;
t=1
2 (w1 (x)) 1x
2
=
Σ
= -/x, --x;=
u2
(11 a
Σ x,
4
i=1
and
3
V 01 [()) Σ ((,x0(0xx))) V. x00;x,) = Σ (v,00()))))) o(w]xx] x,)
1=1
i=1
Hence,
w [(0) points in the direction T) and -V,, [()) > 0. Moreover, we have -V
3
3
V Vw,f(0)
Σ (1:x0(0)))))
V,,,,((0 =
Σ ((uoo(W] x;) + u20 x:)) u22'(w) x.)x:
i=1
= (w2 xa)) 0283 12 (123))))
and
3
V(,((0)= = Σ (y. 31 v,,
Σ ((11o((1 + (20(wxx))) -ow]]x] x;)
= = x3 Jo (w x3) = l' (v23)
Therefore, -V C(O) points in the direction (0,-1)T and ((, > O. Hence for every t
have (t) a(t)- (0, 1) for some a(t) > 0 and vi (t) > 0. Also, we have w2(t)
3(t) . (0, - for some (t) > and o2(t) > 0. By Lemma C.1 we have for every 2 0 that
[t)l? - 0i (t)² = w1 (0)) 21 (0)2 = 0 and [[w)(t)]]² uy) [|)] 22) 0. Hence, we have 01 (t) att and o2(t) 8()). Therefore, we have w: ā (0. 1) and 01 à
for some 2 0. Likewise, we have W2 = (0, -1)T and 82 = for some 3 > Since satisfies
the constraints in Probelm [ then ā 2 and B 2 1. Note that (w, + 0 for all j E {1,2) and i (1,2,3)
We now show that there exists a solution O' to Problem global optimum. Let 0' = [w1, w'g, v'] such that w/ ||لा of = ā, w/ = (- - 1), and
I with a smaller norm, and hence θ is not xi
0/2 = B. It is easy to verify that 0' satisfies the constraints in Problem 1 and we have
1
25
1 + 3 < +1.2+1.3++
|101|2
+
+
+1
1
3 52 ā² + 3 = 0
ãz
32
16
21

---

Under review as a conference paper at ICLR 2022
C.7 PROOF OF THM. 4.4
Let x (4, '2' -4 +2
and y 1. Let ( (v)0).v()) where w(0) (0, 1) and
v(0) = v2' /2)
1 Note that x)) = 1 and hence (()()) < 1 for both the exponential
loss and the logistic loss. Therefore, by Thm. 2.1 GF converges in direction to KKT point O of Problem
[ and we have lim;-oc (()(t)) = 0 and lim;-+oc [ = oc.
The symmetry of the input x and the initialization ((0) implies that the direction of w does not change during the training, and that we have 1n (t) = u2(t) > 0 for all t 2 O. More formally, this claim follows from the following calculation. For j E {1,2) we have
v() (y: o(
x0:
E' (v)(((:)) o(w o(wTx())
Moreover,
Vw ((0))((((
(00 (v)(((:))) (110' xx U20 (w" (wTx(2) xx)))x(
Hence, if = > 0 and w points in the direction (0, 1) then it is easy to verify that V., (())
(()) < 0 and that V (()) points in the direction of -(x(") + x(2)) = -(0, v2) T Further-
more, by Lemma C.2 for every 2 0 we have [t]l [[v( [|)( [0]] = 0.
Therefore, the KKT point 0 [w, v is such that w points at the direction 10, 01 02 0,
and | = ||] Since 0 satisfies the KKT conditions of Problem then we have
w = V (142 (0:x))
where À 2 0 and À = 0f y き Hence, we must have x0) = 1. Letting & = 81 = 02 and using 2x2 = ||0] = |/| = w we have
= ( T x ())) + ( (2) zw (()) + zw x =zØ= (x()+x(2)) = =2.00 2. 22
V2 W2 2 = /
22
Therefore, w- (0, 1) T and (12 (2' +22 Note that we have (w, x1) * O and (w, x O.
It remains to show that 0 is not a local optimum of Problem I We show that for every < é
there exists some 0' = [w', v'] such that 0' é S é', 0' satisfies the constrains in Problem
and
|0'|| |l0]] Let
12 - (0,1/2) and let w' (ve, 1 - TT and v' = = (22
V
/e
2 v2
Note that
1
Ve
1
Ve)
|
||
2|2 + ||
=
c (1 ()-
+
=
2 2- 2e
1+
V/2
2
V2
2
= = - 2
c + <
é
é
=
2
||
+ 1|11 = |0|
2
2
Moreover,
0' 6| + 2 +
c
3
6
3e F2
6"
3
2
2
4
Finally, we show that 0' satisfies the constraints:
x0'::))= v/ x2)
150 WT x22))
1
ve
1
1
VE
1
+
4Ve
(1 (e)
(AVE
(1 -e)
V2
2
V2
V2
1
1
Ve
Ve)
1
Ve
1
Ve
(1 c)
+
+ 4Ve
V2
2
2
V2
22
2
2
2
=1-6
+ 4e
1 + 3e
1.
22

---

Under review as a conference paper at ICLR 2022
C.8 PROOF OF THM. 5.1
Let = (1, and - 1. Consider the initialization ( = [wi Wm (0)) where w,(0)
(1, for every j E [m=] Note that [()(0)) E(2) < for both linear and ReLUU networks with the exponential loss the logistic loss, and therefore by Thm. 2. and limz [()) oc. remains
[.T GF converges in direction
KKT point O of Problem and have lim (()(
to show that it does not converge in direction to a local optimum of Problem 1
From the symmetry of the network + and the initialization (()), it follows that for all /. the network & ((());;)) remains symmetric, namely, there are at(t) (t) such that w (, = (ay (t), (gy())) (t)). Moreover,
by Lemma C.2 for every 2 0 and j. E [m] we have ay({) = an == a(t). Thus, GF converges in direction to the KKT point I [Wi, ...... Wm] such that W (2-1/m, 2-1/m) for all j E [m]] Note that since the dataset is of size 1, then every KKT point of Problem must label the input x with exactly 1.
We now show that ① is local optimum of Problem The following arguments hold for both linear and ReL.U networks. Let <
< 1.2 Let 0'
[w] w'l such that for every j E [m]] we
have w/ = (( 1/m ( (22 m/m) T We have
40'0 ;x)
=
2
Hence, O' satisfies the constraints in Problem 1
We now show that for every sufficiently small 0
we have 10'1 |0| We need to show that
1
2/m
(1-E)
2/m
1 2/m
m
m
2m
2
2
Therefore, it suffices to show that
(1 e1+ 2/m + (1 t) 2/ <2
Let 9: R + R such that g(s) = (1 + 8) 2/m + (1 - 8) 2/m satisfy
We have g(0) = 2. The derivatives of
g((s)
(1 + 8)
2 -1
(1
m
m
and
g"())
2 2
(1 (1+8) 2-2
2
2 (1 2
m m
m
m
Since m 2 3 we have g'(0) = 0 and 50(0) < 0. Hence, 0 is a local maximum of Therefore for every sufficiently small 0 we have g(e) < 2 and thus ||0'1|2 < |0]|2
Finally, note that the inputs to all neurons in the computation ( x) are positive.
C.9 PROOF OF THM. 5.2
By Thm. 2.1 GF converge in direction to KKT point Ô = | of Problem We now show that for every layer / E [m]] the parameters vector ú(!) is global optimum of Problem w.r.t. O.
Since θ is KKT point of Problem then there are Ai...., An such that for every ( e [m] we have
(1)((0x)))
A
On(()
where A; > 0 for all i, and A
0 if (0,x), # 1. Letting ('(1())
(ū(1) ...., ü (1-1) u (1) ((+1) ü (m)], the above equation can be written as
2 (v: 2 (0'((( (1)))))
i Σ
x
On(
[e[n]
23

---

Under review as a conference paper at ICLR 2022
where A 0 for all and A, 0 if (,(((())))
y (0:x) * 1. Moreover, if the
constraints in Problem are satisfies in 0, then the constrains in Problem also satisfied for every E [m] in a()) w.r.t. 0. Hence, for every / E [mi] the KKT conditions of Problem 3 w.r.t. hold. Since the constraints in Problem are affine and the objective is convex, then this KKT point is a global optimum.
C.10 PROOF OF THM..
Let {xx, ()]; be a dataset such that y1 for all i E [4] and we have X1 (0, 1) X2 (1,0) X3 (0, -1) and X4 (-1, 0). In the proof of Thm. 4.2 (part 2) showed that for an appropriate initialization, for both the exponential loss and the logistic loss GF converges to zero loss, and converges in direction to a KKT point 0 of Problem Moreover, in the proof of Thm. 4.2
we showed that the KKT point 0 is such that for all j E [4] we have W, X, and ig 1.
We show that WI, W2, Wa. W4 is not a local optimum of Problem 3 w.r.t. O. It suffices to prove that
for every 0 < < 1 there exists some O' such that v/ ü, for all j [4). |00 0 S 0' satisfies
the constraints, and ||@']| < |@]|. The existence of such 0' is shown in the proof of Thm. 4.2 Hence, conclude the proof of the theorem.
C.11 PROOF OF THM. 5.4
By Thm. 2.1 GF converge in direction to a KKT point = i
of Problem Let E [m]]
1=1 and assume that for every E [n] the inputs all neurons in layers ., in the computation & ((0; x3) are non-zero. We now show that the parameters vector ū()) is local optimum of Problem w.r.t. 0.
For i E [n]] and & E [m - 1] we denote by x; E RR the output of the k-th layer in the computation (0; x;), and denote x; (0) = x, If [m - 1] then we define the following notations. We denote by Jt IRd: + IR the function computed by layers I + 1,..., m of ((0:)). Thus, we have (0; x,) = [((x!)) = fi o (wr()(-11 (-")). where WV(1) the weight matrix that corresponds to where W is the weights matrix that corresponds to ( Thus, (0;xx) = (.)).. If m then we denote by hi the function u (m) + W(m))x (m- thus we also have 4(0; x,) h, (ū (m)))
( For i [n]] we denote by h4 the function u + ((
Since i is KKT point of Problem then there are A An such that
y: (,)))())))
yi h(((
A
A
On())
Jull
where A; 2 0 for all i, and A = Of y hū())) # 1. Note that since the inputs to all neurons in layers l,..., 1 in the computation x0; are non-zero, then the function h; is differentiable at ( Therefore in the above KKT condition we use the derivative rather than the Clarke subdiffer- ential. Moreover, if the constraints in Problem are satisfies in 0 then the constrains in Problem are also satisfied in ( w.r.t. 0. Hence, the KKT condition of Problem w.r.t. O holds.
Also, note that since the inputs to all neurons layers 4,..., m - in the computation Φ x;) are non-zero, then the function h, is locally linear near ū()) We denote this linear function by h4- Therefore, (1) is a KKT point of the following problem
min n
S.t.
E
(n 2 1.
Since the constrains here are affine and the objective is convex, then (!) is global optimum of the above problem. Thus, there is small ball near ü where ū()) is the optimum of Problem w.r.t. 0. namely, it is local optimum.
24

---

Under review as a conference paper at ICLR 2022
Finally, note that in the proof of Lemma C.6 parameters vector 0' is obtained from @ by changing only the first layer. Hence, in ReLU networks GF might converge in direction to a KKT point of Problem which is not global optimum of Problem 3 even if all inputs neurons non-zero.
C.12 PROOF OF THM. 6.1
We have
du (l(y((0;a))
dl(vw + u)
Ou -f'(ww + u)
Iu
dw
)((F((0;))
dk(ow + u)
(ow + u) U. U.
dt
Sw
Ow
de
a(l0((0xx)) Ol(vw + u)
-l'(ww + u) w.
Ow
Ov
Since we also have v(0) = w0) then for every 2 0 we have vtt) = ne(t). Note that el (vw++) < 0 and hence all parameters u, w, v are strictly increasing. Since +() w(0) > then for every t 2
we have ut) = w(t) and hence du(r) dwo(t) du(() Therefore u(t) S utt) = w(t) for all t. dt dt
dt
We now calculate the derivative of V
W
2
vw
u
7())
0
01
22 + 2 + u²
22 + u²
We have
d vw
(u² + w² + 222 ((-e((zu) u/w² ('ow + u)u²) (v² + w² + w²)
dt
12 + 2 + u2
vw (2u(- -f (aw + u)w) + 2n0 - (vw + ujv) 2u( (vw - u)))
and by plugging w = v the above equals
(2n² + u2)2 (-22 (0² + u))²) (2u² + u²) 1² (v² u) (40² + 2u)]
28 u)r² (2v² + 12)2
[(20² + u²) (2x² + u]] 28 (v² u)v²ulu 1)
(2r² + u2)²
Next, we have
d
u
(-E'(ww + u)) V2² + w² + u
dt
1o + 2 2
22 + 2 + 2
Con(-e((nn) - + u)w) + 2wr - (aw + u)u) + 2u( e' (vw +
11
2v 02 2/
+ w + 2
2' (vw + u)
V22 + w² + u² u
20 + 2 + 22 (4ow 2w)
2 + 2 + u
and by plugging w = v the above equals
- ('022 + u)
22² + u²
(40² + +2m)
20 + u²
2 u²
(102 + uu
20 + 2 - u (20² w)
28 + 1 u)u ( 1)
20 u²
v 2202 + w²
2v u²
22 + n²
Overall, we have
(r)
(2² + u) u)u²u(uu 1)
20 + u) (u
1
dt
(2v² + u2)²
20 u2
2n2 + n
-2 (o² + u) u)u² (u
u
1
2v u2
2v + u²
V /2 + u
(0² + w))²((u 1)
W. 22 + uz
<0,
20 x2
2v + x2
25

---

Under review as a conference paper at ICLR 2022
where the inequality is since u > 1 and 0.
We now show that lim (t) = 0. Assume that |@]| A co. Let M > 0 be such that vw + u I M for all Then, -f' + + 2 C' for some constant for all t, which implies that + in contradiction to our assumption. Hence, we must have ||0|| + co. Since V = w 2 u 2 for all t, then we have u + oo and w + co. Therefore lim (() = lim f(ew + +u) = 0.
0. Thus, बे 2 C
is easy to verify that (()()) = 12 + -
viz > 0.9. In order to obtain 1o (((()) = 2/ we first 0. Let M > be some large constant. We show that there exists some t'
show that lime-+o
such that v(()) a(I] 2 .M for all 2 t', Since - oo, then there is some i such that v(t1) = 2M, and
A > O such that v(t2 A) 2M M Since u S v then u(t1) < 2M. For every 2 1 we have du(s)
du(t) = - ('( + u) 2 - l' (vw + u) 2M. Also, we have du(t) - ('(ww + u) z 2M dt di
dt
Hence, we have
/mm gi+ du(t)
+++A
du(l)
u(4 + + = u((1)+ +
J
di S 2M
di 2M (v(4 + A) - v(())
dt
2M dt
2M
1
1
M
2M +
(2M + M 2M) = 2M +
S M
2M
2
Thus,
vt1 + A)
2M + M
M
u(t1 + A)
M
Denote =1 + A. Note that for every 2 we have
u(t) = u(t)+ + [: du di = u(t')+ + [/¹ (-E((w + u)) = =(t) + S. (-e + u))
dt
2 v(() + [-(-e(vw- + 3)) = v(t') + M3 ':" fddu dt
di
2 M utt) + 3 (u(t) u(t)) 2 M - u((t) + M (u(t) - uu(')) = Mu(t).
We have
7(((1)) 2 + 2
wW
+
w
y2
u2
V22 + w² + u²
2n + u
V2 + u²
Since
1im u = 0 then lim, /20 4 = 0 and lim 20 = 1 2.
x²
Hence,
-om ((((t) = 1 2
as required. Finally, since lim y 0 and w(t) = v(t) > for all t,
then |θ converges to
12.0
0) Thus, O converges in direction.
26


Reviews:
[{"review_id": "yxKeY-t73At", "reviewer": "Reviewer_7GJf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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\n\n1. This paper presents lots of positive and negative results on the implicit bias of gradient flow, which certainly increases our knowledge of when gradient flow can or cannot converge to a local/global max-margin solution.\n2. Among the positive results, the most interesting one is the per-layer local optimality for deep ReLU nets. Given the negative results in this paper, the per-layer local optimality seems to be the last hope for providing theoretical guarantees for margin in deep learning. Also this per-layer local optimality could have potential consequences besides margin.\n3. The counterexamples for margin maximization are simple and intuitive.\n\n#### Weaknesses\n\n1. Although the authors made a lot of efforts analyzing the margin maximization across various different settings, this paper lacks a key result to highlight, and thus it may not be clear to readers what the main message is. Also this paper does not contain a conclusion section. The results for the linear nets reconstruct previous results with slight improvement, and the results for the ReLU nets are mostly negative. In my point of view, the result that interests me most is the per-layer local optimality for deep ReLU nets, and the main message could also be \"proving the global optimality of margin is hopeless\".\n2. Although I like the simplicity of the counterexamples, I could not get a high-level insight and do not understand when the counterexamples may conceptually hold. Most of the counterexamples look like corner cases that could be excluded easily:\n   * Theorem 3.2 considers a 2-neuron net. If the width is slightly wider, say 10, then we may get the max margin since there are more weight vectors with $\\langle w, x_i \\rangle > 0$.\n   * Theorem 4.1, 4.4, 5.1 use symmetry: some parameters are initially the same and there is no symmetry breaking during training. So random initialization may mitigate this issue.\n3. The relationship between this paper and Chizat & Bach (2020), Ji & Telgarsky (2020) needs more explanations. Specifically, these two previous works analyzed the neural net with infinite or exponential width. Ji & Telgarsky (2020) actually showed that the global optimality of margin can be attained if a covering condition holds: the directions of weight vectors in the first layer forms an $\\epsilon$-covers of the unit sphere. This means any counterexample should describe a training trajectory that violates the covering condition somehow. I would like to see if the authors can give high-level insights into why the covering conditions are violated.\n4. The counterexample on the non-homogeneous neural net does not seem to be very interesting. Note that the normalized margin itself is not well-defined for non-homogeneous neural nets, because dividing by norms does not make perfect sense anymore. Although Lyu & Li (2020) noticed that the monotonicity of normalized margin (defined by dividing the product of weight norms) for VGG with bias, to actually analyze this a better definition for the normalization margin is still needed. Thus it would be more interesting to have positive results with a well-defined normalized margin, or negative results against a broad class of normalized margin definitions.\n\n#### Minor Comments\n\n* The footnote 3 could be misleading. A possible misinterpretation could be: Ji & Telgarsky (2020) only proved margin maximization in the predictor space, but the current paper proves that in the parameter space with brand new techniques. This is not true because the proof by Ji & Telgarsky (2020) almost implies margin maximization in the parameter space, and this paper indeed used Proposition 4.4 from Ji & Telgarsky (2020).\n* Although the proofs for Theorem 5.2 and 5.4 are simple enough now, I am wondering whether it can be further simplified by applying Corollary 4.5 from Lyu & Li (2020). More specifically, for any homogeneous neural net, we can write $\\Phi(\\theta; x_i)$ as $\\langle \\theta, \\nabla \\Phi(\\theta; x_i) \\rangle$. Then we change the weight of the i-th layer (which corresponds to a part of $\\theta$) while fixing the others. For deep linear nets, we can see from the formula that $\\Phi(\\theta; x_i)$ is linear with the i-th layer weight; for deep ReLU nets, $\\Phi(\\theta; x_i)$ is locally linear with the layer weight. Lyu & Li (2020) showed the KKT convergence result for the original net. Fixing the weights of other layers implies the per-layer global optimality for linear nets. Since the KKT conditions are local conditions, the KKT conditions still hold if a ReLU net is linear everywhere wrt the i-th layer, which implies the per-layer global optimality for linear nets (as what this paper and Lyu & Li (2020) did). I believe this proof also shows how to generalize Theorem 5.2 and 5.4 to homogeneous nets besides ReLU and linear nets.\n* Section 2, Optimization problem and gradient flow (GF): it should be clarified that subgradient flow in the sense of Clarke is used for ReLU nets.", "summary_of_the_paper": "This paper studies the implicit bias of gradient flow in the lens of margin maximization. A previous work by Lyu & Li (2020) shows that gradient flow directionally converges to a KKT point of the margin maximization problem. The authors then focus on understanding what kind of local/global optimality of margin can be guaranteed by applying the KKT convergence result. The authors consider various settings on 2-layer/deep linear/ReLU neural nets, and for each setting they prove either local/global optimality of margin or an impossibility result.\n\nAs the positive results could be more preferable by the ML community, I summarize the positive results below:\n\n* Global optimality for (deep) fully-connected linear nets;\n* Global optimality for general two-layer linear nets with no weight sharing, assuming all the weights are non-zero;\n* Local optimality for general two-layer ReLU nets with no weight sharing, assuming all neurons have non-zero inputs;\n* Per-layer global optimality for general (deep) linear nets (i.e., every layer weights achieve the global max margin if all other layers are fixed.)\n* Per-layer local optimality for general (deep) ReLU nets (i.e., every layer weights achieve a local max margin if all other layers are fixed.), assuming all neurons have non-zero inputs.\n\nHere \"general\" nets can have arbitrary connections between neurons in adjacent layers.", "summary_of_the_review": "This paper studies an interesting topic and presents a lot of positive and negative results, which could be potentially used by other theoretical works later. But this paper lucks a key result to highlight. I appreciate the authors' efforts in analyzing the various settings in the paper, but I have to vote for weak rejection because of the lack of a key result and all the other weaknesses I mentioned above.\n\n-----------------\n\nI was mainly concerned that this paper lacks a key result to highlight, but after reading the rebuttal, I am now satisfied with the authors' response to this major concern. While my other concerns remain (and the authors did not respond to most of them), I am happy to increase my score to 6, assuming that the authors will add the short conclusion section as promised. I look forward to the next revision of the paper.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "duG_4kxyOqq", "reviewer": "Reviewer_frEy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 topic of this paper is interesting, I think that these margin maximization questions are very important. But it suffers from being a collection of a large amount of small results. The paper goes over a large quantity of different settings, and it can be a bit overwhelming and difficult to follow.\n\nNevertheless the paper is a good and quite thorough overview of what happens in all these settings (though I would have been interested to study what happens for multiple outputs as this could make things more interesting in the fully-connected case for example). The counterexample are well described and quite simple, giving an idea of what structure leads to KKT points begin non-optimal. The authors mention that some of their counter example are stable under perturbation while some aren't, but don't really go in the details. I think that this is an important question. To make an analogy, the loss surface of shallow linear network has multiple saddles but the probability to converge to them is 0 since they are all strict saddles. I think it is quite likely that a similar phenomenon could happen here where some of the counterexamples presented in this article only happen with probability zero or a very small probability.\n\nI found the non-homogeneous example interesting, though it is very simple.", "summary_of_the_paper": "This paper is inspired by recent results which have shown that homogeneous networks, when trained on losses with exponential decay converge in direction to KKT points, i.e. points which are first order stationary w.r.t. the opimization of the margin of classification. Since this margin maximization is non-convex, KKT points may not be global maximizers of the margin or not even local maximizers. The authors therefore study a wide range of architecture of linear and ReLU networks, some shallow, some deep, with or without sparse and shared weights, and study in which case all KKT points are global margin maximizers, local margin maximizers or neither (for negative results, counterexamples are given).\n\nFinally they study what happens for non-homogeneous networks, in particular in the presence of skip connection. While for homogeneous networks the margin increases during training, they give an example of a simple network with skip connection where the margin is strictly decreasing.", "summary_of_the_review": "The paper studies an important question and is quite thorough. However it suffers from being a collection of many rather small results.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "OVcyDBW5tf0", "reviewer": "Reviewer_AttS", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "There are some concerns about the technical contributions of the paper. First, the implications of the technical result are not clear, in particular for generalization ability. In other words, how the characterization affect the generalization performance of the network? \n\nThe second concern is that it is not clear how significant the generalization/improvement of the results is, compared to the result of Lyu & Li (2019) .  So far, it looks to me that the results are not as significant as the previous work. ", "summary_of_the_paper": "The paper investigates characterizations of solutions for the problem of training neural networks with exponential loss or logistic loss. The main contribution of the paper is to extend the previous work of  Lyu & Li (2019) for various types of networks. ", "summary_of_the_review": "The technical results seems non-trivial but the implications are not clear.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "HDWUYVlyhN", "reviewer": "Reviewer_sBmy", "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:\n- Findings are interesting and concern an important topic\n- Paper is generally well-written and rather easy to follow\n- main findings are conveniently summarized on a Table\n\nWeaknesses:\n- The paper is missing a sound conclusion/discussion on the implications of their findings.\n\nGiven the interesting negative findings of the paper, I feel it is missing a punchline: what is the implication of these findings about existing works on implicit bias? What is the step ahead from the authors' viewpoint? Suppose that global optimality was true more generally, what are the implications of this? How could this be useful for further theoretical analysis? And in cases where is not true, what does this imply about works investigating implicit bias?\n\nRelated to above: in view of your Thm. 5.2, do you believe that is possible more generally to characterize the converging point as global optimum of some other problem with KKT conditions a superset of the KKT conditions of the max margin Problem 1? \n\n- In the abstract it is stated that: \"On the flip side, we identify multiple setting where a local/global optimum can be guaranteed\". This reads very promising compared to the sole positive results of Thm 3.1 and Thm 5.2 (Thm 4.2a requires rather stringent non-zero weight conditions)\n\nQuestions to the authors:\n- The paper discusses binary classification. Have the authors considered what can be said about multiclass classification?\n- Is program (3) equivalent to min_\\theta \\max_\\ell ||u^{\\ell}||_2  s.t. y_i\\Phi(\\theta;x_i)\\geq 1 ? That is, does this imply that GF converges to the program that maximizes the worst margin among all layers?\n- In Remark 4.1: (2) is a convex program, so every local optimum is a global optimum. \"linear predictor \\tilde\\beta is not a local optimum of the following program\" might be confusing\n- Finally, can the authors comment explicitly on the role of bias?", "summary_of_the_paper": "The paper studies implicit bias of linear and Relu networks (fully connected, diagonal, convolutional etc). Specifically, it investigates deeper a result by Lyu & Li (2019) who showed that gradient flow of such homogeneous next converges to a KKT point of the max margin problem in the parameter space. Owing to its non-convex nature, KKT conditions of this max margin problem do not guarantee local/global optimality. The paper answers whether these KKT conditions are (or not) local/global optima for a variety of linear and homogeneous Relu networks. \n\nThe results are perhaps \"negative\" in the sense that Global optimality is found to be true only for Fully connected Linear (deep) nets, unless additional assumptions are made (Thm 3.1). An interesting positive result is that for linear deep nets not necessarily fully connected (e.g. diagonal/convolutional) the converging point of GF is a global optimum of a program that maximizes the margin of each layer independently. ", "summary_of_the_review": "The paper has interesting findings on implicit bias theory. While the findings themselves are presented in a rather clear manner, the paper is lacking a sound conclusion especially so since it is \"challenging\" existing beliefs. I would encourage the authors to attempt clarifying their view on how these results are expected to affect further research on implicit bias.", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies margin maximization in linear and ReLu networks. The reviewers appreciate the technical contributions of this paper, especially the simple counterexamples. However, reviewers also found the new results seem not to give enough conceptual insights or an important "main result". The meta reviewer agrees and thus decides to reject this paper.
Decision: Reject