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

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 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.

On Margin Maximization in Linear and ReLU Networks
Gal Vardi
Ohad Shamir
TTI-Chicago and Hebrew University" galvardi@ttic.ed
Weizmann Institute of Science ohad. shamir@we zmann, ac i1
Nathan Srebro
TTI-Chicago nati@ttic.edi
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 exponen- tial or the logistic loss, gradient flow converges to a KKT point of the max margin problem in 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.
Introduction
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 learnable parameters than training examples. In such optimization problems there are many solutions that label the training data correctly, and gradient descent seems to prefer solutions that generalize well [Zhang et al. 2016) Hence, is believed that gradient descent induces an implicit bias [Neyshabur and characterizing this bias has been a subject of extensive research in recent years.
2014 2017
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 L. For example, fully-connected and convolutional ReLU networks without bias terms homogeneous. Lyu and Li (2099) proved that linear and ReLU homogeneous networks trained with the exponential the logistic loss, if gradient flow (GF) converges then the direction to which the parameters of the network converge can be characterized as first order stationary point (KKT point) of the maximum margin problem in parameter space. Namely, the problem of minimizing the & 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 showing that some unconstrained optimization problem converges to point with gradient zero, without proving that it is either global or a local minimum. Thus, the
sufficiently small loss
"Wrk done while the author was at the Weizmann Institute of Science
They also assumed directional convergence, but [j and Telgarsky 2020 later showed that this assumption is not required.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table Results on depth-2 networks
Linear
ReLU
Global
Not local
Fully-connected
(Thm. 3.1
(Thm. 3.2
Not local
Not local
(Thm. 4.1
(Thm. 3.2
Nno-share assuming non- weights vectors
Global
Not local
(Thm. 4.2
(Thm. 4.2
Local,
no-uuuree assuming non- 7ero inputs to all neurons
Global
Not global
(Thm. 4.2
(Thm. 4.3
N assuming non-zero in- puts to all neurons
Not local
Not loca
(Thm. 4.4
(Thm.
question of when GF maximizes the margin remains open. Understanding margin maximization may be crucial for explaining generalization in deep learning, and might allow us to utilize margin-based generalization bounds for neural networks.
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 to 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 diagonal linear networks, the KKT point may not even be a local optimum of the maximum margin problem. On the flip side, we identify multiple settings where local or global optimum can be guaranteed.
We now describe our results in bit more detail. We denote by N the class of neural networks without bias terms, where the weights in each layer might have an arbitrary sparsity pattern, and weights might be s The class '' contains, for example, convolutional networks. Moreover, we denote by Noo-share the subclass of N that contains only networks without shared weights, such as jully-connected networks and diagonal networks (cf. Gunasekar et al. [2088b] Yun et (2020). We describe our main results below, and also summarize them in Tables
and
Fully-connected networks:
In linear connecco networks of any depth the KKT point a global optimun")
In fully-connected depth-2 ReLU networks the KKT point may not even be local optimum. Moreover, this negative result holds with constant probability over the initialization, i.e., there training dataset such that GF with random initialization converges with positive probability to the direction of a KKT point which is not a local optimum.
Depth-2 networks in N:
In linear networks with sparse weights, and specifically in diagonal networks, show that the KKT point may not be a local optimum.
In proof of the above negative result, the KKT point contains neuron whose weights vector is zero. However, in practice gradient descent often converges to networks that do not contain such neurons. We show that for linear networks in Nno-stare- if the KKT point has only non-zero weights vectors, then it is a global optimum. Thus, despite the above negative result, a reasonable assumption on the KKT point allows to obtain a strong positive result. We also show some implications of our results on margin maximization in predictor space for depth-2 diagonal linear networks (see Remark 4.1
For ReLU networks in Naw-share in order to obtain a positive result we need stronger assumption. We show that the KKT point such that for every input in the dataset the input to every hidden
See Section 2 for the formal definition.
"We note that margin maximization for such networks in predictor space is already known [ji and Telgarsky 2020]. However, margin maximization in predictor space does not necessarily imply margin maximization in parameter space.

---

Table 2: Results on deep networks
Linear
ReLU
Global
Not local
Fully-connected
(Thm. 3.
(Thm. 3.2
Nu nnosha share assuming non-zero in-
Not local
Not local
puts to all neurons
(Thm. 5.1
(Thm. 5.1
N max margin for each layer
Global
Not local
separately
(Thm. 5.2
(Thm. 5.3
N max margin for each layer
Local.
Global
separately, assuming non-Zero
Not global
(Thm. 5.2
inputs to all neurons
(Thm. (..4
neuron the network is non-zero, then it guaranteed to be local optimum (but not necessarily global optimum).
We prove that assuming the network does not have shared weights is indeed required in the above positive results, since for networks with shared weights (such as convolutional networks) they no longer hold.
Deep networks in A::
We discuss the difficulty in extending our positive results to deeper networks. Then, we study a weaker notion of margin maximization: maximizing the margin for each layer separately. For linear networks of depth m 2 2 in NV (including networks with shared weights), we show that the KKT point a global optimum of the per-layer maximum margin problem. For ReLU networks the KKT point may not even be local optimum of this problem, but under the assumption on non-zero inputs to all neurons it is local optimum.
As detailed above, we consider several different settings, and the results vary dramatically between the settings. Thus, results draw somewhat complicated picture. Overall, our negative results show that even in very simple settings GF does not maximize the margin even locally, and we believe that these results should be used starting point for studying which assumptions for proving margin maximization. Our positive results indeed show that under certain reasonable assumptions GF maximizes the margin (either locally or globally). Also, the notion of per-layer margin maximization which we consider suggests another path for obtaining positive results on the implicit bias.
required
In the paper, our focus is on understanding what can be guaranteed for the KKT convergence points specified in Lyu and Li (201)). Accordingly, in most of our negative results, the construction assumes some specific initialization of GF, and does not quantify how "likely" they are to be reached under some random initialization. An exception is negative result for depth-2 fully-connected ReLU networks (Theorem 3.2). which holds with constant probability under reasonable random initializations. Understanding whether this can be extended the other settings consider is interesting problem for future research.
In Section 2 we provide necessary notations and definitions, and discuss relevant prior results. Additional related works are discussed Appendix In Sections and 5 we state results on fully-connede networks, depth-2 networks in A and deep networks N respectively, and provide some proof ideas. All formal proofs are deferred to Appendix
Our paper is structured as follows:
2 Preliminaries
Notations. We use bold-faced letters to denote vectors, e.g., x = (#I,.... Ta). For x E Rd we denote by ||x|| the Euclidean norm. We denote by 1(.) the indicator function, for example 1( 2 5) equals if 2 5 and 0 otherwise. For an integer 2 1 we denote [d] {1, [1....,d}.
Neural networks. A fully-connected neural network & of depth collection 0- = [w] of weight matrices, such that for every layer / [m]] we have Will e x Thus, d, denotes the number of neurons in the I-th layer (i.c., the width of the layer). We
2 is parameterized by
3

---

assume that dm = 1 and denote by d: do the imput dimension. The neurons in layers [m - 1] are called hidden neurons. A fully-connected network computes a function :(0; Rd - IR defined
recursively as follows. For an input x E R we set hg = x, and define for every j E [m - 1] the input to the j-th layer as h, = h''''' and the output of the j-th layer as h = o oh,)) where Ø: E + R is an activation function that acts coordinate- waide on vectors. Then, 2 x) = hy Thus, there is no activation function in the output neuron. When considering 2 fully-connected networks
define
often use a parameterization 0 [Wi....; Wk, v] where wi...., Wi are the weights vectors of the k hidden neurons (i.e., correspond to the rows of the first layer's weight matrix) and are the weights of the second layer.
We also consider neural networks where some weights can be missing or shared. We define a class N of networks that may contain sparse and shared weights as follows. A network & in 'N' is parameterized by 0 = [u(]mm
.l=1 where m is the depth of i and u()) E R are the parameters of the (-th layer. We denote by W [dxxdd-1 the weight matrix of the (-th layer. The matrix w is described by the vector u and function gi [di] x [d:-]] + [pi] U {0} as follows: sg ur if gi(i. j) > 0. Thus, the function gi represents the sparsity and weight-sharing pattern of the (-th layer, and the dimension Pt of u is the number of free parameters the layer We denote by d dg the input dimension of the network and assume that the output dimension dm, is 1. The function Φ(0: -)= Rd -> IR 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 .V. Note that the networks in N do not have bias terms and do not allow weight sharing between different layers. Moreover, we define a subclass Non-share of N,, that contains networks without shared weights. Formally, a network & is in N if for every layer I and every k E [pr] there is at most one (i.j) E [dr] x [d:1]] such that gi (i. = k. Thus, networks in Nno-share might have sparse weights, but do not allow shared weights. For example, diagonal networks (defined below) and fully-connected networks are in Nnn-sbare-
w!"" if (i.j) 0, and w
A diagonal neural network is network in sha such that the weight matrix of each layer is diagonal, except for the last layer. Thus, the network is parameterized by [Wi,..., wm] where Wj E Rdd for all j [m], and it computes function (0:-)) Rdd - E defined recursively as follows. For input x E IRd set he x. For j [m 1), the output of the j-th layer is hy (diag(w,))
Then, we have ((;xx) W hm
In all the above definitions the parameters f of the neural networks are given by a collection of matrices or vectors. We often view O as the vector obtained by concatenating the matrices or vectors in the collection. Thus, ||O]] denotes the f2 norm of the vector 0.
The ReLU activation function is defined by (=))
ma,x(0,=) =). and the linear activation is (z) = z. In this work 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 & homogeneous if there exists L 0 such that for every a > 0 and 0, x we have (aa0; x) a 44 0 x). Note that in our definition of the class / we do not allow bias terms, and hence all linear and ReLU networks in A are homogeneous, where L is the depth of the network. All networks considered in this work are homogeneous.
C Rd x (-1.1} be a binary classification training dataset. Let & be a neural network parameterized by 0 E R=. For loss function É: IR- + R the empirical loss of 4 ((: .) on the dataset S is
Optimization problem and gradient flow (GF). Let S =
((0) Σ (1.x((:x)))
We focus on the exponential loss E(g) = - and the logistic loss {(g) = log(1 + +
We consider GF on the objective given in Eq. This setting captures gradient descent with an infinitesimally small step size. Let (t) be the trajectory of GF. Starting from an initial point (0)). - (()())). Note that the ReLU
the dynamics of O(L) is given by the differential equation di function is not differentiable at O. Practical implementations of gradient methods define the derivative o' (0) to be some constant in [0, 1]. We note that the exact value of a' o'(0) has effect our results.
d0(t)

---

Convergence to KKT point of the maximum-mane problem. We say that a trajectory (t)) In this work we rely on the following theorem:
converges in direction to 0 lim
0(r)
[((()]]
||ā||
Theorem 2.1 (Paraphrased from Lyu and Li 2019 Ji and Telgarsky (020)) Let O be a homoge- neous linear or ReLU neural network. Consider minimizing either the exponential or the logistic loss over a binary classification dataset (:)4 using GF. Assume that there exists time to such that ((O( < 1, namely, & classifies every x; correctly. Then, GF converges in direction to a first order stationary point (KKT point) of the following maximum margin problem in parameter space:
min [101 0
S.T. Vi [
y. (=0(0xx,)
(2)
2
Moreover, (()())) + 0 and [I0(1) 0G as co.
In the case of ReLU networks, Problem 2 is non-smooth. Hence, the KKT conditions are defined
using the Clarke subdifferential, which is generalization of the derivative for -inddefferett functions. See Appendix [ for a formal definition. We note that Lyu and Li] [2019] proved the above theorem under the assumption that A converges in direction, and and Telgarsky [2020] showed that such a directional convergence occurs and hence this assumption is not required.
Lyu and Li [2019] also showed that the KKT conditions of Problem are necessary for optimality, In convex optimization problems, necessary KKT conditions are also sufficient for global optimality. However, the constraints in Problem X 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 (201 ID. 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(L))... ..... ((m) computes a linear predictor where B = W(m) ..... W()), Some prior works studied the implicit bias of linear networks in predictor space. Namely, characterizing the vector 3 from the aforementioned linear predictor. Gunasekar al. [2018b] studied the implications of margin maximization in parameter space on the implicit bias in predictor space. They showed that minimizing |||| (under the constraints in Problem implies: (1) Minimizing || for fully-connected networks; (2) Minimizing ||
(B,x)
for depth-L diagonal networks; (3) Minimizing || for depth-L convolutional networks with full-dimensional filters, where 3 are the Fourier coefficients of (. However, these implications may not hold if GF converges to KKT point which is not global optimum of Problem
For some classes of linear networks, positive results were obtained directly in predictor space, without assuming convergence to global optimum of Problem in parameter space. Most notably, for fully- connected linear networks (of any depth), Ji and Telgarsky (2020) showed that under the assumptions of Theorem 1 GF maximizes the &2 margin in predictor space. Note that margin maximization in predictor space does not necessarily imply margin maximization in parameter space. Moreover, some results on the implicit bias in predictor space of linear convolutional networks with full-dimensional convolutional filters are given in Gunasekar et al. (2018b). However, the architecture and set of assumptions are different than what we focus See Appendix A for discussion additional related work.
3 Fully-connected networks
First, we show that fully-connected linear networks converge to a global optimum of Problem 2
Theorem 3.1. Let m 2 2 and let & be a depth-m fully-comnected linear network parameterized by 0. Consider minimizing either the exponential or the logistic loss over a dataset {xx, v:)) using GF. Assume that there exists time to such that L(0(ta)) < 1. Then, GF converges in direction to global optimum of Problem 2
Proof idea (for the complete proof see Appendix C.2
Building results from Ji and Telgarsky
2020 and Du et al. [2018), we show that GF converges in direction to KKT point 0
W W[m) such that for every 1 [m]] we have ((() C. - where C > 0 and
5

---

15
(1(())
Figure 1: For time we denote
10-
(t (t). Above we illus-
trate (1) uz(l) for times ( < l2. As I + 0o we have [|]] + 00 and
X2
[M1(6)
X1
u converges in direction to (0, 1). The vector U2 remains constant during the training. Hence (a(() + 0. [[([
-0.5
0.5
Uy(6))= =x())==[(t))
Voy..., Vm are unit vectors (with Vm 1). Also, have |[ Way C
min ||u|| s.t. you x; 1 for all i E [n]. Then, show that every 0 that satisfies these prop- erties, and satisfies the constraints of Problem 2 is a global optimum. Intuitively, the most "efficient" way (in terms of minimizing the parameters) to achieve margin 1 with linear fully-connected network, 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 of the layers aligned.
We now prove that the positive result in Theorem 3.1 does not apply to ReLU networks. We show that in depth-2 fully-comnected ReLU networks GF might converge in direction to a KKT point of Problem 2 which is not even local optimum. Moreover, occurs under conditions holding with constant probability over reasonable random initializations.
Theorem 3.2. Let & be a 2upph--2fully--onneee
ReLU network with input dimension 2 and two hidden neurons. Namely, for = [w1, W2, v) and x I2Z we have (00 x) = - vro (w, x). Consider minimizing either the exponential
the logistic loss using GF. Consider the dataset
X2 = ()1, and y1 = y/2 1. Assume that the initialization (() is such that for every E [1.2] we have (W1(0), xx) > and (wz(0), xx))
{x11. ( (x2, } where X1 = (1,
Also, assume that U1 (0) > O. Then, GF converges to zero loss, and converges in direction to KKT
point of Problem 2 which is not local optimum.
Proof idea (for the complete proof see Appendix C.3 given dataset, we show that it converges to zero loss, and converges in direction to a KKT point such that W1 = (0, 2) `1 2, W2 0, and i2 = O. Note that W2 = 0 and 02 wa((), v2() remain constant during the training and lim [|@(t)] = oc. See Figure for an illustration. Then, we show that for every 0 < < there exists some 0' such that ||0' θ |S c, O' satisfies y: (0'; x;) for every slightly changing W1. W2. and Ø2. Thus, by using the second hidden neuron, which is not active in we can obtain a solution 0' with smaller norm.
By analyzing the dynamics of GF on the
since
2). and ||0'l| < ||0||. Such O' is obtained from 0 by
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, X2 in the setting of Theorem 3.2 it is not hard to show that the sub-optimality of the KKT point w.r.t. the global optimum can be arbitrarily large. Namely, for every large M > we can choose a dataset where the angle between Xı and Xa is sufficiently close n, such that |||| 2 M, where Ô is KKT point which GF converges, and 0" is a global optimum of Problem
T0"
2 Indeed, as illustrated in Figure | if one neuron is 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 a single imput then we can achieve margin with much smaller parameters. We note that such unbounded sub- aub-optimality can be obtained also in other negative results in this work (in Theorems 4.1 and 5.4).
Remark 3.2 (Robustness to small perturbations). Theorem 3.2 holds even if we slightly perturb the inputs 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 Theorems 4.1 4.3 5.7 and 5.4

---

4 Depth-2 networks in N
In this section we study depth-2 linear and ReLU networks N. We first show that already for linear networks in Nuosshrre (more specifically, for diagonal networks) GF may not converge even to local optimum.
Theorem 4.1. Let & be a depth-2 linear or ReLU diagonal neural network parameterized by
i = -W1, Wa]. Consider minimizing either the exponential or the logistic loss using GF. There exists a dataset {(x, y)} - R ] of size and an initialization (0), such that GF converges to zero loss, and converges in direction to a KKT point O of Problem 2 which is not a local optimum.
Let = (1, and y 1. Let ((0) such that W1 (0) W2(0) = (1, Recalling that the diagonal network computes the function x r (W1 w2) x (where o is the entry-wise product), we see that the second coordinate remains inactive
Proof idea (for the complete proof see Appendix C.4
during training. It not hard show that GF converges the KKT point O with W1 W (1, 11,0"
However, it is not a local optimum, since for small 6 >> 0 the parameters O' = [w]. wgl with
w/- 3 = (v1
W/2
satisfy the constraints of Problem 2 and we have ||@'|l ||]|.
By Theorem 3.2 fully-connected ReLU networks may not converge local optimum, and by Theorem 4.1 linear (and ReLU) networks with sparse weights may not converge to a local optimum. In the proofs of both of these negative results, GF converges 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, a 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 N if GF converges to a KKT point of Problem 2 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 is not sufficient.
KKT point such that one of the
Theorem 4.2. We have:
1. Let tb be depth-2 linear neural network in Nno- parameterized by 0. Consider minimizing either the exponential or the logistic loss over a dataset {(x, Vi=1 using GF. Assume that there exists time to such that L(O(to)) < 1, and let O be the KKT point of Problem such that ((t) converges to θ in direction (such O exists by Theorem 2. Assume that in the network parameterized by @ all hidden neurons have non-zero incoming weights vectors. Then, θ is global optimum of Problem
2. Let 4 be a fully-co depth-2 ReLU network with input dimension 2 and 4 hidden neurons parameterized by O. Consider minimizing either the exponential or the logistic loss using GF There exists a dataset and an initialization ((0), such that GF converges to zero loss, and converges in direction to a KKT point 0 of Problem 2 which is not a local optimum, and in the network parameterized by 0 all hidden neurons have non-zero incoming weights.
Proof idea (for the complete proof see Appendix C.5 We give here the proof idea for part (1). Let k be the width of the network. For every j E [k] we denote by w, the incoming weights vector the j-th hidden neuron, and by 2j the outgoing weight. Let u, j. We consider an optimization problem over the variables uI,.... UN where the objective is to minimize ΣjE( ||u,|| and the
constrains correspond to the constraints of Problem Let θ I....., Wx, v) be the KKT point of Problem 2 to which GF converges in direction. For every j E [k] we denote ú, ū, w. We show that û₁ üg satisfy the KKT conditions of the aforementioned problem. Since the objective there is convex and the constrains are affine, then it is a global optimum. Finally, we show that it implies global optimality of Ô.
Remark 4.1 (Implications on margin maximization in predictor space for diagonal linear networks). Theorems 4. andd 4.2 imply analogous results on diagonal linear networks also in predictor space. As we discussed in Section 2 Gunusekar et al. (208b) showed that in depth-2 diagonal linear networks, minimizing |00, under the constraints in Problem 2 Pimplies minimizing [|3]|, where (3 is the corresponding linear predictor. Theorem 4.1 can be easily extended to predictor space, namely,
7

---

GF on depth-2 linear diagonal networks might converge to a KKT point θ of Problem 2 such that the corresponding linear predictor B is not an optimum of the following problem:
argmin 1|31| s.1. E [m]] 3/ (3, x,) 21.
(3)
B
Moreover, by combining part (1) of Theorem 4.2 with the result from Gunasekar al. | (2018b), we
deduce that if GF on a depth-2 diagonal linear network converges to a KKT point O of Problem with non-zero weights vectors, then the corresponding linear predictor is a global optimum of Problem 3
We argue that since in practice gradient descent often converges to networks without werghteight neurons, then part (1) of Theorem 4.2 gives a useful positive result for depth-2 linear networks. However, by part (2) of Theorem 4.2 this assumption is not sufficient for obtaining a positive result in the case of ReLU networks. Hence, we now consider 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 2 However, even under this condition it is not necessarily global optimum. The proof is given in Appendix and and uses ideas from the previous proofs, with some required modifications.
Theorem 4.3. Let be a depth-2 ReLU network in nhr-sh parameterized by 0. Consider min- imizing either the exponential the logistic loss over dataset {(xi, Ue H== using GF. Assume that there exists time to such that ((O(to)) < L, and let O be the KKT point of Problem such that (() converges to O in direction (such O exists by Theorem 2. Assume that for every E [m] the inputs to all hidden neurons in the computation (00; xx) are non-zero. Then, 0 a local optinum of Problem 2 However, it may not be global optimum, even if the network & is fully connected.
Note that in all the above theorems we do not allow shared weights. We now consider the case of depth-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 no zero weights vectors).
Theorem 4.4. Let & be a 2epth-2 linear or ReLU network in N, parameterized by = [w, for w, E R.2, such that for x E RA. we have $ x) = Σ}=1 E (yo x where x (1) = (I1, and (2)) (1)) Thus, & is a convolational network with two disjoint patches. Consider minimizing either the exponential or the logistic loss using GF. Then, there exists a dataset (xx,y) } of size 1, and an initialization (0), such that GF converges to zero loss, and converges in direction to KKT point
[w, V of Problem 2 which is not a local optimum. Moreover, (W,
x x()) + f j E [1,2].
Proof idea (for the complete proof see Appendix C.7 Let x = 4, 1 V2' -4, and y = Let
Since (1) and (2) are symmetric w.r.t. (0)), and v0) does not break this symmetry, then w keeps its direction throughout the training. Thus, we show that GF converges in direction to a KKT point 0 where w (0, 1)T and V
(0) such that (() = (0, 1)T and v(0) = V2 v2)
V2
Then, we show that it is not local optimum, since for every small >> 0 the parameters 0' [w'
with w' = (VE, T and v' = 1z
+
V 2
satisfy the constraints of Problem and xt 2
v2
we have ||0'|| < ||0).
5 Deep networks in N
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 Non-shure GF may not converge to a local optimum of Problem 2 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. More precisely, we prove this claim for diagonal networks.
8

---

Theorem 5.1. Let m 2 3. Let d be 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, v)} S R2 x 1 of size 1 and an initialization O)), such that GF converges to zero loss, and converges in direction to KKT point O of Problem 2 which is not local optimum. Moreover, all inputs to neurons in the computation ((0; x) are non-zero.
Proof idea (for the complete proof see Appendix C. Let x =1,x=),,) (1,1)T and y Consider the initialization (()) where w,(0) (1,1) for every j [mm] We show that GF converges in direction to KKT point 0 [W1..... Wml such that w (2-1/m
1/m 2 2-1/m) T for all j E [m]]
Then, we consider the parameters 0' = [wi..... winl such that for every [m]] we have w/-
and show that e > 0 is sufficiently small, then e' satisfies the constraints in Problem 2 and we have ||0'|| < ||0||
( (( (7
Note that in the case of linear networks, the above result is in contrast to networks with sparse weights of depth that converge to global optimum by Theorem 4.2 and to fully-connected networks of any depth that converge to global optimum by Theorem 3.1 In the case of ReLU networks, the above result is in contrast to the case of 2epth-2 networks studied in Theorem 4.3 where is guaranteed to converge to a local optimum.
In light of our negative results, we consider weaker notion of margin maximization, namely, maximizing the margin for each layer separately. Let t be a neural network of depth m in N. parameterized by 0 [u The maximum margin problem for a layer to E [m]] w.r.t. Oo- =
[u) 10 1 is the following:
| s.t. E [n] y (0'; x;) 21,
min G
(4)
where 0' = (ub
u0 1) (1)) up f1++1) ( For linear networks we have the following:
Theorem 5.2. Let m 2 2. Let & be any depth-m linear neural network in N. parameterized by 0- = 1m I=I- Consider minimizing either the exponential or the logistic loss over a dataset
((x;, (.) Fi using GF. Assume that there exists time in such that L(O(lo)) < 1. Then, GF converges in direction to KKT point O = =1000 of Problem 2 such that for every layer 1 E [m] the parameters vector ú!) is global optimum of Problem w.r.t. O.
The theorem follows by noticing that if & is a linear network, then the constraints in Problem 4 are affine, and its KKT conditions are implied by the KKT conditions of Problem 2 See Appendix C.9 for the formal proof. Note that by Theorems 4.1 4.4 [5. linear networks in N might converge in direction to KKT point O which is not a local optimum of Problem 2 However, Theorem 5.2
implies that each layer in θ is global optimum of Problem Hence, any improvement 0 requires changing at least two layers simultaneously.
While in linear networks GF maximize the margin for each layer separately, in the following theorem (which we prove in Appendix CC10) we show that this claim does not hold for ReLU networks: Already for fully-connected networks of 2epth-2 GF may not converge in direction to a local optimum of Problem
Theorem 5.3. Let de be a fully-connected depth-2 ReLU network with input dimension and hidden neurons parameterized by O. Consider minimizing either the exponential or the logistic loss using GF. There exists a dataset and an initialization (0) such that GF converges to zero loss, and converges in direction to a KKT point i of Problem such that the weights of the first layer are not a local optimum of Problem w.r.t. O.
Finally, we show that ReLU networks in A 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 4 (but not necessarily a global optimum). The proof follows the ideas from the proof of Theorem 5.2 with some required modifications, and is given in Appendix C.Il
9

---

Theorem 5.4. Let m 2 2. Let & be any depth-m ReLU network in N parameterized by 0 = [u 11 Consider minimizing either the exponential or the logistic loss over a dataset {(x,, Vs) V using GF. and assume that there exists time to such that (()()))) < Let = ju | be the KKT point of Problem such that O(t) converges to in direction (such 0 exists by Theorem 2.79. Let I E [m]] and assume that for every E In] the inputs to all neurons in layers 2 I in the computation ((0;x,) are non-zero. Then, the parameters vector ú is local optimum of Problem w.r.. 9. However, may not be a global optimum.
1-1-
Acknowledgments and Disclosure of o Funding
This research supported in part by European Research Council (ERC) grant 754705.
References
S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pages 7413-7424, 2019.
S. Azulay, E. Moroshko, M. S. Nacson, B. Woodworth, N. Srebro, A. Globerson, and D. Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. arXiv preprint arXiv:2102.09769 2021.
M. A. Belabbas. On implicit regularization: Morse functions and applications to matrix factorization. arXiv preprint urXiv:2001.04266 2020.
L. Chizat and F. Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint 2242::2000.044886 2020.
F. H. Clarke, Y. S. Ledyaev, R. J. Stern, and P. R. Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science Business Media, 2008
S. S. Du, W. Hu, and J. D. Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems, pages 384-395 2018.
Dutta, K. Deb, R. Tulshyan, and R. Arora. Approximate kkt points and a proximity measure for termination. Journal of Global Optimization, 56(4):1463-1149, 2013.
A. Eftekhari and K. Zygalakis. Implicit regularization in matrix sensing: A geometric view leads to stronger results. arXiv preprint arXiv:2008. 12091, 2020.
T. Ergen and M. Pilanci. Convex geometry and duality of over-parameterizee neural networks. Journal of machine learning research, 2021a.
T. Ergen and M. Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference on Machine Learning, pages 3004-3014, PMLR, 2021b.
G. Gidel, F. Bach, and S. Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. In Advances in Neural Information Processing Systems, pages 3202-3211, 1, 2019.
Gunasckar, Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprint arXiv:1802.0022 2018a.
Gunasekar, J. D. Lee, D. Soudry, and Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pages 9461-9471, 2018b.
S. Gunasekar, B. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regularization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018c.
10

---

N. Haim, G. Vardi, G. Ychudai, O. Shamir, and M. Irani. Reconstructing training data from trained neural networks. arXiv preprint arXiv:2206.074 077558. 2022.
M. Jagadeesan, I. Razenshteyn, and S. Gunasekar. Inductive bias of multi-channel linear convolutional networks with bounded weight norm. arXiv preprint arXiv:2102.122 2021.
Z. Ji and M. Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint 1rXiv:1110002033 2018a.
Z. Ji and M. Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 1803.00700 2018b.
Z. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006.06637, 2020.
7. Ji and M. Telgarsky. Characterizing the implicit bias via a primal-dual analysis. In Algorithmic Learning Theory, pages 772-804. PMLR, 2021.
Z. Ji, M. Dudík, E. Schapire, and M. Telgarsky. Gradient descent follows the regularization path for general losses. In Conference Learning Theory, pages 2109-2136. PMLR, 2020.
Y. Li. T. Ma, and H. Zhang. Algorithmic regularization in werr-paaamterrzedd matrix sensing and neural networks with quadratic activations. In Conference Learning Theory, pages 2-47. PMLR, 2018.
Z. Li, Y. Luo, and K. Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint arXiv:2012.09839, 2020.
K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 1Xii:1906.05580 2019.
K. Lyu, Z. Li, R. Wang, and S. Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34, 2021.
Ma, K. Wang, Y. Chi, and Y. Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference Machine Learning, pages 3345-3354 PMLR, 2018.
E. Moroshko, B. E. Woodworth, S. Gunasekar, J. D. Lee, N. Srebro, and D. Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. Advances in Neural Information Processing Systems, 33, 2020.
M. S. Nacson, J. Lee, S. Gunasekar, P. H. P. Savarese, N. Srebro, and D. Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-3428. PMLR, 2019.
B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv: 1412.6614, 2014.
B. Neyshabur, Bhojanapalli, D. McAllester, and N. Srebro. Exploring generalization in deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956 2017.
M. Phuong and C. H. Lampert. The inductive bias of relu networks on orthogonally separable data. In International Conference on Learning Representations, 2020.
N. Razin and N. Cohen. Implicit regularization in deep learning may not be explainable by norms. arXiv preprint arXiv:2005.0633 06398, 2020.
A. Ruszezynski. Nonlinear optimization. Princeton university press, 2011.
I. Safran, G. Vardi, and D. Lee. On the effective number linear regions in shallow univariate relu networks: Convergence guarantees and implicit bias. arXiv preprint (xXix:2205.00077 2022.
R. Sarussi, A. Brutzkus, and A. Globerson. Towards understanding learning in neural networks with linear teachers. In International Conference on Machine Learning, pages 9313-9322, PMLR, 2021.
11

---

O. Shamir. Gradient methods never overfit on separable data. arXiv preprint arXiv: TrXi::007.00022 2020.
D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1):2222-28) 2018.
N. Timor, G. Vardi, and O. Shamir. Implicit regularization towards rank minimization in relu networks. arXiv preprint 1.Xiv:2201.1270000 2022.
G. Vardi. On the implicit bias in deep-learning algorithms. arXiv preprint arXiv:2208.1259/ 2022.
G. Vardi and O. Shamir. Implicit regularization in relu networks with the square loss. In Conference on Learning Theory, pages 4224-4258. PMIR, 2021.
G. Vardi, G. Yehudai, and O. Shamir. Gradient methods provably converge non-robust networks arXiv preprint urXiv:2202.04344 2022.
B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, Golan, D. Soudry, and N. Srebro. Kernel and rich regimes in overparametrized models. arXiv preprint arXiv:2002. 09277, 2020.
C. Yun, S. Krishnan, and Mobahi. A unifying view on implicit bias in training linear neural networks. arXiv preprint arXiv:20/0.02501, 2020.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03533 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The paper
is purely theoretical in nature, and we do not see any potential negative societal impacts
that should be discussed.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "F3rR-DghYGc", "reviewer": "Reviewer_pTzM", "summary": "The implicit bias of gradient descent/flow for homogeneous models using losses with an exponential tail has been previously characterized the first-order critical point of a $\\ell_2$-max margin problem in parameter space. The purpose of this paper is to investigate whether this critical point can be guaranteed to have stronger properties, such as local or global optimality in the max-margin problem. The authors study a variety of situations including linear or Relu neural networks, of depth 2 or more, with or without weight sharing. In all these situations, they prove whether there is a positive local/global optimality result and if not, they give counter-examples. \n", "questions": "- Thm.3.2. would benefit from a discussion with two related works: [1] and [2]. [1] gives another context where the final margin is suboptimal while [2], on the positive side, shows that there is global margin maximization for infinite-width networks under assumptions (the difference between the two being, it seems, that the limit small initialization/large width are interverted).\n\n[1] Gradient descent on two-layer nets: Margin maximization and simplicity bias, Lyu,  Li,  Wang,  Arora, 2021.\n\n[2] Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss, Chizat, Bach, 2020.", "limitations": "N/A.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe paper is well written, clear and well organized. It consists in a collection of theoretical results, each comes with a proof strategy in the main text. The various insights are summarized in Table 1 and 2 which, at a glance, give an interesting general picture of the problem. I was quite impressed by the profusion of results and settings considered, and overall I think that the paper will surely be useful for the community of researchers working on the theory of implicit bias of gradient descent.\n\nI don't have particular concerns about the paper (ie \"weaknesses\") besides the fact that it deals with a rather specific theoretical question which might be only of interest to a restricted number of specialists. But I think that as a community we need this kind of papers that investigate in depth certain theoretical points, so I don't think that this is much of a weakness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "E0lTxENKWxT", "reviewer": "Reviewer_fRNg", "summary": "This paper studies the implicit bias of gradient descent through the lens of margin maximization, and the main focus is to understand what can be guaranteed by the KKT convergence result by Lyu & Li (2019). It then presents a series of positive and negative results on the local and global optimality of KKT points across different settings, depending on whether the neural net is linear/nonlinear, whether it is fully-connected/diagonal, and whether it has shared weights or not. This paper also proposes the notion of per-layer margin maximization to be another path to obtain positive results on the implicit bias, and establishes a local optimality result assuming non-zero inputs to all neurons.", "questions": "1. Chizat and Bach(2020); Ji & Telgarsky (2020) prove the global optimality of margin for wide two-layer nets under the assumption that the directions of weight vectors in the first layer approximately cover the unit sphere.  Phuong and Lampert (2020) prove the global optimality of margin on orthogonally separable data. Lyu et al. (2021) prove the global optimality of margin on symmetric and linearly separable data. It would be nice if the authors can reconcile their negative results with these positive results from previous works. For example, how are the assumptions violated in the counter-examples?\n2. I'm wondering if the per-layer optimality results (Theorem 5.2 and 5.4) have a close relationship with Corollary 4.5 in Lyu & Li (2019). For linear nets,\n\\begin{align*}\n\\left< u^{(l_0)}, \\frac{\\partial \\Phi(\\theta'; x_i)}{\\partial u^{(l_0)}} \\right> = \\Phi(\\theta'; x_i).\n\\end{align*}\nSo Eq. (4) becomes\n\\begin{align*}\n\\min_{u^{(l_0)}}  \\frac{1}{2} \\\\|u^{(l_0)}\\\\|^2 \\quad s.t. \\quad \\forall i \\in [n], y_i \\left< u^{(l_0)}, \\frac{\\partial \\Phi(\\theta'; x_i)}{\\partial u^{(l_0)}} \\right> \\ge 1.\n\\end{align*}\nNote that $(\\partial \\Phi(\\theta'; x_i))/ (\\partial u^{(l_0)})$ does not change with $u^{(l_0)}$. So Corollary 4.5 in Lyu & Li (2019) should have implied Theorem 5.2. The ReLU case is similar as $\\Phi$ is locally linear.", "limitations": "The authors have discussed the limitations of their counter-examples in Lines 83 - 89.\nIt would be nice if the authors can mention the following limitations which are shared in common with many implicit bias works:\n1. The difference between GF and SGD may not be negligible;\n2. Reaching a KKT point can take exponential time even for linear logistic regression (Soudry et al., 2018).", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### Strengths:\n1. This paper is well-written and presents a nice exhibition of the meaning of Lyu & Li's KKT convergence across different settings.\n2. Theorem 3.1 shows that GF on deep linear fully-connected nets converges to the max-margin solution in the parameter space, which complements the previous margin maximization result in the predictor space (Ji & Telgarsky, 2020).\n3. The per-layer local optimality result gives a new characterization of the convergence point.\n\n#### Weaknesses:\n1. I like the simple counter-examples shown in this paper for margin maximization, but an obvious weakness is that all these examples are for small datasets and small neural nets. It is nice that the authors include discussions like Remarks 3.1 and 3.2 on the generality of the counter-examples, but perhaps the authors could discuss more on large datasets and wide neural nets.\n2. It is unclear how the per-layer local optimality result can be connected to generalization or other learning metrics.\n3. The negative results are not well contextualized relative to prior works that attempt to prove the global optimality of margin (see Questions below).\n\n#### Minor comments:\n* It is not a good idea to put so many important related works in Appendix A. Perhaps the authors could consider to move this section to the main paper.\n* It would be nice if the authors can include a section to conclude the paper at the end.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Dw1J5x0ky5-", "reviewer": "Reviewer_Uo2f", "summary": "This paper analyzes margin maximization properties of gradient flow (GF) on linear and ReLU neural networks. It was shown by previous work that GF converges to a KKT point of a margin maximization problem when trained on linear or ReLU networks. This paper first considers fully-connected networks, and shows that for linear networks, GF converges to a global optimum of the margin maximization problem, while for ReLU networks, the GF solution may not even be locally optimal. Next, if the network may contain sparse connections (e.g., diagonal networks), it is shown that the GF solution may not be locally optimal even for depth-2 linear networks. If we further require all neurons have nonzero incoming weight vectors in the KKT solution, then it will be globally optimal for depth-2 linear networks, but this condition is still not enough to guarantee local optimality for depth-2 ReLU networks or deep linear networks with depth larger than 2. For depth-2 ReLU networks with sparse connections, if it is further required that the inputs to all hidden neurons are nonzero, then it is shown that GF converges to a local optimum, but it might not be globally optimal. ", "questions": "N/A", "limitations": "As mentioned above, it will he helpful to have a discussion section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper gives a detailed analysis of margin maximization for GF. It is shown that a KKT point may not be globally or even locally optimal in many different settings. On the other hand, with some additional regularity conditions (e.g., no zero input weight vectors), local or global optimality can be guaranteed. I think these results are useful to the community. \n\nOn the other hand, it seems many of the negative examples can be handled by having a randomly-initialized network with a reasonable width, which is more relevant to practice. It would be very interesting if there exists a setting that can also fail a wide randomly-initialized network. Additionally, the proof idea of Theorem 3.1 is similar to that of [Ji and Telgarsky 2018, Gradient descent aligns the layers of deep linear networks]; the difference should be discussed.\n\nFinally, the presentation is a little intense, especially at the end of the paper. It will also be helpful to have a section discussing limitations, open problems, etc.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CHT5vRspGOV", "reviewer": "Reviewer_rHbR", "summary": "The paper studies margin maximization for linear and ReLU networks with exponential and logistic loss. Under this setting, several prior works could show that gradient flow converges to a KKT point of the max margin problem, but these works did not discuss when the KKT point is a local/global optimum of the max margin problem. The current paper studies this question. For the various settings of the network (linear/ReLU, fully connected/convolutional/weight sharing) and the training data, they show that the KKT solutions are *not* even local optimum of the max margin problem. However, in some special cases such as deep linear nets with fully connected architecture, they can show the global optimality.\nThe main results of the paper can be summarized as follows.\n\n- Global optimality for deep linear nets with dense connections: every KKT point is a global optimum of the max margin problem. This result also holds when the network has sparse connections under an additional assumption that the KKT point has non-zero incoming weights.\n\n- For 2-layer ReLU nets: KKT points with non-zero inputs to hidden neurons are local optimum, but they are not necessarily global. The non-zero input assumption appears to be important as they show there exists a dataset where the same network with 2 inputs and 2 hidden neurons does not have this property.\n\n- For deep ReLU nets: KKT points with non-zero inputs to all neurons satisfy a per-layer local optimality. As before, the non-zero input assumptions seems to be necessary as they show there exists a dataset where a 2-layer ReLU net with 2 inputs and 4 hidden neurons may not have this property. However, for deep linear nets, per-layer global optimality always holds.", "questions": "See Weakness.", "limitations": "It would be nice to improve the generality of the counterexamples in the paper, e.g. by replacing a toy example with more general conditions on the training data and network widths.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper studies an important question resulting from previous works: when the KKT points are local/global optimum of the max margin problem. I am not aware of any previous work which studies this in detail, so in that sense the contribution of the paper seems to be novel. \n2. The provided examples on local optimality of KKT points appear to be simple, and can serve as a good starting point for studying sufficient conditions on the network, the data, and the initialization for proving global max margin in deep learning.\n3. The results are clearly presented in the main paper.\n\nWeakness:\n1. The negative results are mostly stated for a specific choice of the data points and a toy network (with a few inputs and neurons). This makes me wonder how much of the conclusions in these counterexamples carry over to the more general settings where the data could be drawn from some continuous distribution and the network widths are more general.\n2. The paper studies gradient flow as given by an ODE. In several places in the proofs (also in Theorem 2.1), one needs to take time t to infinity. However, it is not very clear why such a solution even exists because an ODE in general can have a finite-time blow up, i.e. the solution has the form [0,t0) where t0 is finite but ||\\theta(t)|| may still diverge.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept