Year: 2021

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 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 & Li (2019) by showing that for non-homogeneous networks, the normalized margin may strictly decrease over time.

heading: 1 INTRODUCTION
text: 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 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, it is believed that gradient descent induces an 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 are networks where scaling the parameters by any factor α > 0 scales the predictions by αL for some constant L. For example, fully-connected and convolutional ReLU networks without bias terms are homogeneous. 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 loss1, then the direction to which the parameters of the network converge can be characterized as a first order stationary point (KKT point) of the maximum margin problem in the parameter space. Namely, the problem of minimizing the `2 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 a global or a local minimum.
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 a global optimum of the maximum margin problem, a local optimum, or neither. Perhaps surprisingly, our results imply that in many cases, such as 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 a local or global optimum can be guaranteed.
We now describe our results in a 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
1They also assumed directional convergence, but (Ji & Telgarsky, 2020) later showed that this assumption is not required.
Table 1: Results on depth-2 networks.
Linear ReLU
Fully-connected Global(Thm. 3.1) Not local (Thm. 3.2) Nno-share Not local(Thm. 4.1) Not local (Thm. 3.2) Nno-share assuming non-zero weights vectors Global (Thm. 4.2) Not local (Thm. 4.2) Nno-share assuming non-zero inputs to all neurons Global (Thm. 4.2) Local, Not global (Thm. 4.3) N assuming nonzero inputs to all neurons Not local (Thm. 4.4) Not local (Thm. 4.4)
Table 2: Results on deep networks.
Linear ReLU
Fully-connected Global(Thm. 3.1) Not local (Thm. 3.2) Nno-share assuming non-zero inputs to all neurons Not local (Thm. 5.1) Not local (Thm. 5.1) N - max margin for each layer separately Global (Thm. 5.2) Not local (Thm. 5.3) N - max margin for each layer separately, assuming non-zero inputs to all neurons Global (Thm. 5.2) Local, Not global (Thm. 5.4)
weights might be shared2. The class N contains, for example, convolutional networks. Moreover, we denote by Nno-share 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. (2020)). We describe our main results below, and also summarize them in Tables 1 and 2.

heading: Fully-connected networks:
text: • In linear fully-connected networks of any depth the KKT point is a global optimum3. • 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 a training dataset such that gradient flow with random initialization converges with constant probability to the direction of a KKT point which is not a local optimum.
Depth-2 networks in N : • The positive result on fully-connected 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 Nno-share, if the KKT point has only non-zero weights vectors, then it is a global optimum. We also show that even for the simple case of depth-2 diagonal linear networks, the optimality of the KKT points can be unexpectedly subtle, in the context of margin maximization in the predictor space (see Remark 4.1).
• For ReLU networks in Nno-share, in order to obtain a positive result we need a stronger assumption. We show that if the KKT point is such that for every input in 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 or ReLU convolutional networks, even if the above assumptions hold, the KKT point may not be a local optimum.

heading: Deep networks in N :
text: • We show that the positive results on depth-2 linear and ReLU networks in Nno-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 depthm ≥ 2 inN (including networks with shared weights), we show that the KKT point is a global optimum of the per-layer maximum margin problem. For ReLU networks the KKT point may not even be a local optimum of this problem, but under the assumption on non-zero inputs to all neurons it is a local optimum.
2See Section 2 for the formal definition. 3We note that margin maximization for such networks in the predictor space is already known (Ji & Telgarsky, 2020). However, margin maximization in the predictor space does not necessarily imply margin maximization in the parameter space.
In the paper, our focus is on understanding what can be guaranteed for the KKT convergence points specified in Lyu & Li (2019). Accordingly, in most of our negative results, the construction assumes some specific initialization of gradient flow, and does not quantify how “likely” they are to be reached under some random initialization. An exception is our negative result for depth-2 fully-connected ReLU networks (Thm. 3.2), which holds with constant probability under reasonable 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 monotonically increasing when training homogeneous networks. They observed empirically that the normalized 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 a simple non-homogeneous 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, 4 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 6 we state our result on non-homogeneous networks. All formal proofs are deferred to Appendix C.

heading: 2 PRELIMINARIES
text: Notations. We use bold-faced letters to denote vectors, e.g., x = (x1, . . . , xd). For x ∈ Rd we denote by ‖x‖ the Euclidean norm. We denote by 1(·) the indicator function, for example 1(t ≥ 5) equals 1 if t ≥ 5 and 0 otherwise. For an integer d ≥ 1 we denote [d] = {1, . . . , d}.
Neural networks. A fully-connected neural network Φ of depth m ≥ 2 is parameterized by a collection θ = [W (l)]ml=1 of weight matrices, such that for every layer l ∈ [m] we have W (l) ∈ Rdl×dl−1 . Thus, dl denotes the number of neurons in the l-th layer (i.e., the width of the layer). We assume that dm = 1 and denote by d := d0 the input dimension. The neurons in layers [m− 1] are called hidden neurons. A fully-connected network computes a function Φ(θ; ·) : Rd → R defined recursively as follows. For an input x ∈ Rd we set h′0 = x, and define for every j ∈ [m − 1] the input to the j-th layer as hj = W (j)h′j−1, and the output of the j-th layer as h ′ j = σ(hj), where σ : R→ R is an activation function that acts coordinate-wise on vectors. Then, we define Φ(θ;x) = W (m)h′m−1. Thus, there is no activation function in the output neuron. When considering depth-2 fully-connected networks we often use a parameterization θ = [w1, . . . ,wk,v] where w1, . . . ,wk 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 N of networks that may contain sparse and shared weights as follows. A network Φ in N is parameterized by θ = [u(l)]ml=1 where m is the depth of Φ, and u
(l) ∈ Rpl are the parameters of the l-th layer. We denote by W (l) ∈ Rdl×dl−1 the weight matrix of the l-th layer. The matrix W (l) is described by the vector u(l), and a function gl : [dl] × [dl−1] → [pl] ∪ {0} as follows: W (l)ij = 0 if gl(i, j) = 0, and W (l) ij = uk if gl(i, j) = k > 0. Thus, the function gl represents the sparsity and weight-sharing pattern of the l-th layer, and the dimension pl of u(l) is the number of free parameters in the layer. We denote by d := d0 the input dimension of the network and assume that the output dimension dm is 1. The function Φ(θ; ·) : Rd → R computed by the neural network is 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 N do not have bias terms and do not allow weight sharing between different layers. Moreover, we define a subclass Nno-share of N , that contains networks without shared weights. Formally, a network Φ is in Nno-share if for every layer l and every k ∈ [pl] there is at most one (i, j) ∈ [dl] × [dl−1] such that gl(i, j) = 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 Nno-share.
A diagonal neural network is a network in Nno-share such that the weight matrix of each layer is diagonal, except for the last layer. Thus, the network is parameterized by θ = [w1, . . . ,wm] where wj ∈ Rd for all j ∈ [m], and it computes a function Φ(θ; ·) : Rd → R defined recursively as follows. For an input x ∈ Rd set h0 = x. For j ∈ [m − 1], the output of the j-th layer is hj = σ(diag(wj)hj−1). Then, we have Φ(θ;x) = w>mhm−1.
In all the above definitions the parameters θ of the neural networks are given by a collection of matrices or vectors. We often view θ as the vector obtained by concatenating the matrices or vectors in the collection. Thus, ‖θ‖ denotes the `2 norm of the vector θ. The ReLU activation function is defined by σ(z) = max{0, z}, and the linear activation is σ(z) = z. 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 L > 0 such that for every α > 0 and θ,x we have Φ(αθ;x) = αLΦ(θ;x). Note that in our definition of the class N we do not allow bias terms, and hence all linear and ReLU networks inN are homogeneous. With the exception of Section 6 which studies non-homogeneous networks, all networks considered in this work are homogeneous.
Optimization problem and gradient flow (GF). Let S = {(xi, yi)}ni=1 ⊆ Rd×{−1, 1} be a binary classification training dataset. Let Φ be a neural network parameterized by θ ∈ Rm. For a loss function ` : R → R the empirical loss of Φ(θ; ·) on the dataset S is L(θ) := ∑n i=1 `(yiΦ(θ;xi)). We focus on the exponential loss `(q) = e−q and the logistic loss `(q) = log(1+e−q), and consider gradient flow (GF) on the objective L(θ). This setting captures gradient descent with an infinitesimal step size. Let θ(t) be the trajectory of GF. Starting from an initial point θ(0), the dynamics of θ(t) is given by the differential equation dθ(t)dt = −∇L(θ(t)). Note that the ReLU function is not differentiable at 0. Practical implementations of gradient methods define the derivative σ′(0) to be some constant in [0, 1]. We note that the exact value of σ′(0) has no effect on our results.
Convergence to a KKT point of the maximum-margin problem. We say that a trajectory θ(t) converges in direction to θ̃ if limt→∞ θ(t) ‖θ(t)‖ = θ̃ ‖θ̃‖ . In this work we rely on the following theorem:
Theorem 2.1 (Paraphrased from Lyu & Li (2019); Ji & Telgarsky (2020)). Let Φ be a homogeneous linear or ReLU neural network. Consider minimizing either the exponential or the logistic loss over a binary classification dataset {(xi, yi)}ni=1 using GF. Assume that there exists time t0 such that L(θ(t0)) < 1, namely, Φ classifies every xi correctly. Then, GF converges in direction to a first order stationary point (KKT point) of the following maximum margin problem in parameter space:
min θ
1 2 ‖θ‖2 s.t. ∀i ∈ [n] yiΦ(θ;xi) ≥ 1 . (1)
Moreover, L(θ(t))→ 0 and ‖θ(t)‖ → ∞ as t→∞.
In the case of ReLU networks, Problem 1 is non-smooth. Hence, the KKT conditions are defined using Clarke’s subdifferential, which is a generalization of the differential for non-differentiable functions. See Appendix B for a formal definition. We note that Lyu & Li (2019) proved the above theorem under the assumption that θ converges in direction, and Ji & Telgarsky (2020) showed that such a directional convergence occurs and hence this assumption is not required.
Lyu & Li (2019) also showed that the KKT conditions of Problem 1 are necessary for optimality. In convex optimization problems, necessary KKT conditions are also sufficient for global optimality. However, the constraints in Problem 1 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 (2011)). However, even when Φ is a linear neural network it is not known when such conditions hold. Thus, the KKT conditions of Problem 1 are not known to be sufficient even for local optimality.
A linear network with weight matrices W (1), . . . ,W (m) computes a linear predictor x 7→ 〈β,x〉 where β = W (m) · . . . ·W (1). Some prior works studied the implicit bias of linear networks in the predictor space. Namely, characterizing the vector β 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 ‖θ‖ (under the constraints
in Problem 1) implies: (1) Minimizing ‖β‖2 for fully-connected networks; (2) Minimizing ‖β‖2/L for depth-L diagonal networks; (3) Minimizing ‖β̂‖2/L for depth-L convolutional networks with full-dimensional filters, where β̂ are the Fourier coefficients of β. However, these implications may not hold if GF converges to a KKT point which is not a global optimum of Problem 1.
For some classes of linear networks, positive results were obtained directly in the predictor space, without assuming convergence to a global optimum of Problem 1 in the parameter space. Most notably, for fully-connected linear networks (of any depth), Ji & Telgarsky (2020) showed that under the assumptions of Thm. 2.1, GF maximizes the `2 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. (2018b). However, the architecture and set of assumptions are different than what we focus on.

heading: 3 FULLY-CONNECTED NETWORKS
text: First, we show that fully-connected linear networks converge to a global optimum of Problem 1. Theorem 3.1. Let m ≥ 2 and let Φ be a depth-m fully-connected linear network parameterized by θ. Consider minimizing either the exponential or the logistic loss over a dataset {(xi, yi)}ni=1 using GF. Assume that there exists time t0 such that L(θ(t0)) < 1. Then, GF converges in direction to a global optimum of Problem 1.
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 a KKT point θ̃ = [W̃ (1), . . . , W̃ (m)] such that for every l ∈ [m] we have W̃ (l) = C · vlv>l−1, where C > 0 and v0, . . . ,vm are unit vectors (with vm = 1). Also, we have ‖W̃ (m) · . . . · W̃ (1)‖ = Cm = min ‖u‖ s.t. yiu>xi ≥ 1 for all i ∈ [n]. Then, we show that every θ that satisfies these properties, and satisfies the constraints of Problem 1, is a global optimum. Intuitively, the most “efficient” way (in terms of minimizing the parameters) to achieve margin 1 with a linear fully-connected network, is by using a 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.
We now prove that the positive result in Thm. 3.1 does not apply to ReLU networks. We show that in depth-2 fully-connected ReLU networks GF might converge in direction to a KKT point of Problem 1 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 a depth-2 fully-connected ReLU network with input dimension 2 and two hidden neurons. Namely, for θ = [w1,w2,v] and x ∈ R2 we have Φ(θ;x) = ∑2 l=1 vlσ(w > l x). Consider minimizing either the exponential or the logistic loss using GF. Consider the dataset {(x1, y1), (x2, y2)} where x1 = ( 1, 14 )> , x2 = ( −1, 14 )> , and y1 = y2 = 1. Assume that the initialization θ(0) is such that for every i ∈ {1, 2} we have 〈w1(0),xi〉 > 0 and 〈w2(0),xi〉 < 0. Also, assume that v1(0) > 0. Then, GF converges to zero loss, and converges in direction to a KKT point of Problem 1 which is not a local optimum.
Proof idea (for the complete proof see Appendix C.3). By analyzing the dynamics of GF on the given dataset, we show that it converges to zero loss, and converges in direction to a KKT point θ̃ such that w̃1 = (0, 2)>, ṽ1 = 2, w̃2 = 0, and ṽ2 = 0. Note that w̃2 = 0 and ṽ2 = 0 since w2(t), v2(t) remain constant during the training and limt→∞ ‖θ(t)‖ = ∞. This is illustrated in the figure on the right: For time t we denote ui(t) = vi(t)wi(t). We observe u1(t),u2(t) for times t1 < t2. As t → ∞ we have ‖u1(t)‖ → ∞ and u1 converges in direction to (0, 1). The vector u2 remains constant during the training. Hence u2(t)‖θ(t)‖ → 0. −1.0 −0.5 0.5 1.0 −1.0 −0.5 0.5 1.0 1.5
Then, we show that for every 0 < < 1 there exists some θ′ such that ‖θ′ − θ̃‖ ≤ , θ′ satisfies yiΦ(θ
′;xi) ≥ 1 for every i ∈ {1, 2}, and ‖θ′‖ < ‖θ̃‖. Such θ′ is obtained from θ̃ by slightly changing w̃1, w̃2, and ṽ2. Thus, by using the second hidden neuron, which is not active in θ̃, we can obtain a solution θ′ 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,x2 in the setting of Thm. 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 > 0 we can choose a dataset where the angle between x1 and x2 is sufficiently close to π, such that ‖θ̃‖ ‖θ∗‖ ≥ M , where θ̃ is a KKT point to which GF converges, and θ∗ is a global optimum of Problem 1. Indeed, as illustrated in the figure from the proof idea of Thm. 3.2, if one neuron is active on both inputs and the other neuron is 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 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 (in Thm. 4.1, 4.3, 4.4 and 5.4).
Remark 3.2 (Robustness to small perturbations). Thm. 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 Thm. 4.1, 4.3, 5.1 and 5.4.
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 in Nno-share (more specifically, for diagonal networks) GF may not converge even to a local optimum.
Theorem 4.1. Let Φ be a depth-2 linear or ReLU diagonal neural network parameterized by θ = [w1,w2]. Consider minimizing either the exponential or the logistic loss using GF. There exists a dataset {(x, y)} ⊆ R2×{−1, 1} of size 1 and an initialization θ(0), such that GF converges to zero loss, and converges in direction to a KKT point θ̃ of Problem 1 which is not a local optimum.
Proof idea (for the complete proof see Appendix C.4). Let x = (1, 2)> and y = 1. Let θ(0) such that w1(0) = w2(0) = (1, 0)>. Recalling that the diagonal network computes the function x 7→ (w1◦w2)>x (where ◦ 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 w̃1 = w̃2 = (1, 0)>. However, it is not a local optimum, since for small > 0 the parameters θ′ = [w′1,w ′ 2] with w′1 = w ′ 2 = (√ 1− , √ 2 )> satisfy the constraints of Problem 1, and we have ‖θ′‖ < ‖θ̃‖.
By Thm. 3.2 fully-connected ReLU networks may not converge to a local optimum, and by Thm. 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 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 a 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 Nno-share, if GF converges in direction to a KKT point of Problem 1 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.
Theorem 4.2. We have:
1. Let Φ be a depth-2 linear neural network inNno-share, parameterized by θ. Consider minimizing either the exponential or the logistic loss over a dataset {(xi, yi)}ni=1 using GF. Assume that there exists time t0 such that L(θ(t0)) < 1, and let θ̃ be the KKT point of Problem 1 such that θ(t) converges to θ̃ in direction (such θ̃ exists by Thm. 2.1). Assume that in the network
parameterized by θ̃ all hidden neurons have non-zero incoming weights vectors. Then, θ̃ is a global optimum of Problem 1.
2. Let Φ be a fully-connected depth-2 ReLU network with input dimension 2 and 4 hidden neurons, parameterized by θ. 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 θ̃ of Problem 1, which is not a local optimum, and in the network parameterized by θ̃ 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 ∈ [k] we denote by wj the incoming weights vector to the j-th hidden neuron, and by vj the outgoing weight. Let uj = vjwj . We consider an optimization problem over the variables u1, . . . ,uk where the objective is to minimize ∑ j∈[k] ‖uj‖ and the
constrains correspond to the constraints of Problem 1. Let θ̃ = [w̃1, . . . , w̃k, ṽ] be the KKT point of Problem 1 to which GF converges in direction. For every j ∈ [k] we denote ũj = ṽjw̃j . We show that ũ1, . . . , ũk 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 the predictor space for diagonal linear networks). Thm. 4.1 and 4.2 imply analogous results on diagonal linear networks also in the predictor space. As we discussed in Section 2, Gunasekar et al. (2018b) showed that in depth-2 diagonal linear networks, minimizing ‖θ‖2 under the constraints in Problem 1 implies minimizing ‖β‖1, where β is the corresponding linear predictor. Thm. 4.1 can be easily extended to the predictor space, namely, GF on depth-2 linear diagonal networks might converge to a KKT point θ̃ of Problem 1, such that the corresponding linear predictor β̃ is not a local optimum of the following problem:
arg min β ‖β‖1 s.t. ∀i ∈ [n] yi〈β,xi〉 ≥ 1 . (2)
Moreover, by combining part (1) of Thm. 4.2 with the result from Gunasekar et al. (2018b), we deduce that if GF on a depth-2 diagonal linear network converges to a KKT point θ̃ of Problem 1 with non-zero weights vectors, then the corresponding linear predictor is a global optimum of Problem 2.
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 θ̃ is such that for every xi in the dataset the inputs to all hidden neurons in the computation Φ(θ̃;xi) 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 1. However, even under this condition it is not necessarily a 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 a depth-2 ReLU network in Nno-share parameterized by θ. Consider minimizing either the exponential or the logistic loss over a dataset {(xi, yi)}ni=1 using GF. Assume that there exists time t0 such that L(θ(t0)) < 1, and let θ̃ be the KKT point of Problem 1 such that θ(t) converges to θ̃ in direction (such θ̃ exists by Thm. 2.1). Assume that for every i ∈ [n] the inputs to all hidden neurons in the computation Φ(θ̃;xi) are non-zero. Then, θ̃ is a local optimum of Problem 1. However, it may not be a 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 a 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 Φ be a depth-2 linear or ReLU network in N , parameterized by θ = [w,v] for w,v ∈ R2, such that for x ∈ R4 we have Φ(θ;x) = ∑2 j=1 vjσ(w
>x(j)) where x(1) = (x1, x2) and x(2) = (x3, x4). Thus, Φ is a convolutional network with two disjoint patches. Consider minimizing the exponential or the logistic loss using GF. Then, there exists a dataset {(x, y)} of size 1,
and an initialization θ(0), such that GF converges to zero loss, and converges in direction to a KKT point θ̃ = [w̃, ṽ] of Problem 1 which is not a local optimum. Moreover, 〈w̃,x(j)〉 6= 0 for j ∈ {1, 2}. Proof idea (for the complete proof see Appendix C.7). Let x = (
4, 1√ 2 ,−4, 1√ 2
)> and y = 1. Let
θ(0) such that w(0) = (0, 1)> and v(0) = (
1√ 2 , 1√ 2
)> . Since x(1) and x(2) are symmetric w.r.t.
w(0), and v(0) does not break this symmetry, then w keeps its direction throughout the training. Thus, GF converges in direction to a KKT point θ̃ where w̃ = (0, 1)> and ṽ = (
1√ 2 , 1√ 2
)> . It is not
a local optimum, since for every small > 0 the parameters θ′ = [w′,v′] with w′ = ( √ , 1− )> and v′ = (
1√ 2
+ √ 2 , 1√ 2 − √ 2
)> satisfy the constraints of Problem 1, and ‖θ′‖ < ‖θ̃‖.

heading: 5 DEEP NETWORKS IN N
text: In this section we study the more general case of depth-m neural networks inN , wherem ≥ 2. First, we show that for networks of depth at least 3 in Nno-share, GF may not converge to a local optimum of Problem 1, 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 ≥ 3. Let Φ be a depth-m linear or ReLU diagonal neural network parameterized by θ. Consider minimizing either the exponential or the logistic loss using GF. There exists a dataset {(x, y)} ⊆ R2 × {−1, 1} of size 1 and an initialization θ(0), such that GF converges to zero loss, and converges in direction to a KKT point θ̃ of Problem 1 which is not a local optimum. Moreover, all inputs to neurons in the computation Φ(θ̃;x) are non-zero.
Proof idea (for the complete proof see Appendix C.8). Let x = (1, 1)> and y = 1. Consider the initialization θ(0) where wj(0) = (1, 1)> for every j ∈ [m]. We show that GF converges in direction to a KKT point θ̃ = [w̃1, . . . , w̃m] such that w̃j = ( 2−1/m, 2−1/m )> for all j ∈ [m]. Then, we consider the parameters θ′ = [w′1, . . . ,w ′ m] such that for every j ∈ [m] we have
w′j = (( 1+ 2 )1/m , ( 1− 2 )1/m)> , and show that if > 0 is sufficiently small, then θ′ satisfies the constraints in Problem 1 and we have ‖θ′‖ < ‖θ̃‖.
Note that in the case of linear networks, the above result is in contrast to networks with sparse weights of depth 2 that converge to a global optimum by Thm. 4.2, and to 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 is in contrast to the case of depth-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 a network of depthm inN , parameterized by θ = [u(l)]ml=1. The maximum-margin problem for a layer l0 ∈ [m] w.r.t. θ0 = [u (l) 0 ] m l=1 is:
min u(l0)
1
2 ∥∥∥u(l0)∥∥∥2 s.t. ∀i ∈ [n] yiΦ(θ′;xi) ≥ 1 , (3) where θ′ = [u(1)0 , . . . ,u (l0−1) 0 ,u (l0),u (l0+1) 0 , . . . ,u (m) 0 ]. For linear networks we have the following: Theorem 5.2. Let m ≥ 2. Let Φ be any depth-m linear neural network in N , parameterized by θ = [u(l)]ml=1. Consider minimizing either the exponential or the logistic loss over a dataset {(xi, yi)}ni=1 using GF. Assume that there exists time t0 such thatL(θ(t0)) < 1. Then, GF converges in direction to a KKT point θ̃ = [ũ(l)]ml=1 of Problem 1, such that for every layer l ∈ [m] the parameters vector ũ(l) is a global optimum of Problem 3 w.r.t. θ̃.
The theorem follows by noticing that if Φ is a linear network, then the constraints in Problem 3 are affine, and its KKT conditions are implied by the KKT conditions of Problem 1. See Appendix C.9 for the formal proof. By Thm. 4.1, 4.4 and 5.1, linear networks inN might converge to a KKT point
θ̃ which is not a local optimum of Problem 1. However, by Thm. 5.2 each layer in θ̃ is a global optimum of Problem 3. Thus, any improvement to θ̃ requires changing a few layers simultaneously.
While in linear networks GF maximize the margin for each layer separately, in the following theorem we 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 3 (see Appendix C.10 for the proof). Theorem 5.3. Let Φ be a fully-connected depth-2 ReLU network with input dimension 2 and 4 hidden neurons parameterized by θ. 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 θ̃ of Problem 1, such that the weights of the first layer are not a local optimum of Problem 3 w.r.t. θ̃.
Finally, we show that in ReLU networks inN 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.11. Theorem 5.4. Let m ≥ 2. Let Φ be any depth-m ReLU network in N parameterized by θ = [u(l)]ml=1. Consider minimizing either the exponential or the logistic loss over a dataset {(xi, yi)}ni=1 using GF, and assume that there exists time t0 such that L(θ(t0)) < 1. Let θ̃ = [ũ(l)]ml=1 be the KKT point of Problem 1 such that θ(t) converges to θ̃ in direction (such θ̃ exists by Thm. 2.1). Let l ∈ [m] and assume that for every i ∈ [n] the inputs to all neurons in layers ≥ l in the computation Φ(θ̃;xi) are non-zero. Then, the parameters vector ũ(l) is a local optimum of Problem 3 w.r.t. θ̃. However, it may not be a global optimum.

heading: 6 NON-HOMOGENEOUS NETWORKS
text: Let γ̄(θ) := mini∈[n] yiΦ ( θ ‖θ‖ ;xi ) be the normalized margin. If Φ is homogeneous then maximizing γ̄(θ) is equivalent to solving Problem 1, i.e., minimizing ‖θ‖ under the constraints (cf. Lyu & 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 a smoothed version of the normalized margin is monotonically increasing when training homogeneous networks. More precisely, there is a function γ̃(θ) which is an O ( ‖θ‖−L ) -additive approximation of γ̄(θ), such that
γ̃(θ) is monotonically non-decreasing. This result does not apply to non-homogeneous 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-homogeneous networks. However, they did not provide a proof for this phenomenon and left it as an open problem. Their experiments are on training convolutional neural networks (CNN) with bias on MNIST. In the following 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 to obtain such a result for non-homogeneous networks some additional assumptions must be made. Theorem 6.1. Let Φ be a depth-2 linear network with input dimension 1, width 1 and a skip connection. Namely, Φ is parameterized by θ = [w, v, u] where w, v, u ∈ R, and Φ(θ;x) = v ·w ·x+u ·x. Consider the size-1 dataset {(1, 1)}, and assume that θ(0) = [2, 2, 2]. Then, GF w.r.t. either the exponential loss or the logistic loss converges to zero loss, converges in direction (i.e., limt→∞ θ(t) ‖θ(t)‖ exists), and the normalized margin is monotonically decreasing during the training, i.e., dγ̄(θ(t))dt < 0 for all t ≥ 0. Moreover, we have γ̄(θ(0)) > 0.9 and limt→∞ γ̄(θ(t)) = 12 .
We note that the proof readily extends in a few directions: It applies also for a 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, note that if v‖θ‖ , w ‖θ‖ = 0 and u ‖θ‖ = 1 then γ̄(θ) = 1, and if u ‖θ‖ = 0 and v ‖θ‖ = w ‖θ‖ = 1√ 2
then γ̄(θ) = 12 . 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 x, then v, w grow faster than u during the training. Hence, as t increases, u‖θ‖ decreases and v ‖θ‖ , w ‖θ‖ increase.

heading: A MORE RELATED WORK
text: Soudry et al. (2018) showed that gradient descent on linearly-separable binary classification problems with exponentially-tailed losses (e.g., the exponential loss and the logistic loss), converges to the maximum `2-margin direction. This analysis was extended to other loss functions, tighter convergence rates, non-separable data, and variants of gradient-based optimization algorithms (Nacson et al., 2019b; Ji & Telgarsky, 2018b; Ji et al., 2020; Gunasekar et al., 2018a; Shamir, 2020; Ji & Telgarsky, 2021).
As detailed in Section 2, Lyu & Li (2019) and Ji & Telgarsky (2020) showed that GF on homogeneous 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. (2019a); Gunasekar et al. (2018b). The implications of margin maximization in the parameter space on the implicit bias in the predictor space for linear neural networks were studied in Gunasekar et al. (2018b) (as detailed in Section 2) and also in Jagadeesan et 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 assumptions were previously established in Gunasekar et al. (2018b) and in Ji & Telgarsky (2018a). The implicit bias in the predictor space of diagonal and convolutional linear networks was studied in Gunasekar et al. (2018b); Moroshko et al. (2020); Yun et al. (2020). The implicit bias in infinitely-wide 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 extensively studied in recent years (e.g., Gunasekar et al. (2018c); Razin & Cohen (2020); Arora et al. (2019); Belabbas (2020); Eftekhari & Zygalakis (2020); Li et al. (2018); Ma et al. (2018); Woodworth et al. (2020); Gidel et al. (2019); Li et al. (2020); Yun et al. (2020); Vardi & Shamir (2021); Azulay et al. (2021)). This setting, however, is less relevant for our work.

heading: B PRELIMINARIES ON THE KKT CONDITION
text: Below we review the definition of the KKT condition for non-smooth optimization problems (cf. Lyu & Li (2019); Dutta et al. (2013)).
Let f : Rd → R be a locally Lipschitz function. The Clarke subdifferential (Clarke et al., 2008) at x ∈ Rd is the convex set
∂◦f(x) := conv {
lim i→∞ ∇f(xi) ∣∣∣ lim i→∞ xi = x, f is differentiable at xi } .
If f is continuously differentiable at x then ∂◦f(x) = {∇f(x)}. Consider the following optimization problem
min f(x) s.t. ∀n ∈ [N ] gn(x) ≤ 0 , (4) where f, g1, . . . , gn : Rd → R are locally Lipschitz functions. We say that x ∈ Rd is a feasible point of Problem 4 if x satisfies gn(x) ≤ 0 for all n ∈ [N ]. We say that a feasible point x is a KKT point if there exists λ1, . . . , λN ≥ 0 such that
1. 0 ∈ ∂◦f(x) + ∑ n∈[N ] λn∂ ◦gn(x);
2. For all n ∈ [N ] we have λngn(x) = 0.

heading: C PROOFS

heading: C.1 AUXILIARY LEMMAS
text: Throughout our proofs we use the following two lemmas from Du et al. (2018): Lemma C.1 (Du et al. (2018)). Let m ≥ 2, and let Φ be a depth-m fully-connected linear or ReLU network parameterized by θ = [W1, . . . ,Wm]. Suppose that for every j ∈ [m] we have Wj ∈ Rdj×dj−1 . Consider minimizing any differentiable loss function (e.g., the exponential or the logistic loss) over a dataset using GF. Then, for every j ∈ [m− 1] at all time t we have
d
dt
( ‖Wj‖2F − ‖Wj+1‖ 2 F ) = 0 .
Moreover, for every j ∈ [m− 1] and i ∈ [dj ] we have d
dt
( ‖Wj [i, :]‖2 − ‖Wj+1[:, i]‖2 ) = 0 ,
where Wj [i, :] is the vector of incoming weights to the i-th neuron in the j-th hidden layer (i.e., the i-th row of Wj), and Wj+1[:, i] is the vector of outgoing weights from this neuron (i.e., the i-th column of Wj+1).
Lemma C.2 (Du et al. (2018)). Let m ≥ 2, and let Φ be a depth-m linear or ReLU network in N , parameterized by θ = [u(1), . . . ,u(m)]. Consider minimizing any differentiable loss function (e.g., the exponential or the logistic loss) over a dataset using GF. Then, for every j ∈ [m− 1] at all time t we have
d
dt (∥∥∥u(j)∥∥∥2 − ∥∥∥u(j+1)∥∥∥2) = 0 . Note that Lemma C.2 considers a larger family of neural networks since it allows sparse and shared weights, but Lemma C.1 gives a stronger guarantee, since it implies balancedness between the incoming 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 us introduce some required notations. Let Φ be a depth-2 network in Nno-share. We can always assume w.l.o.g. that the second layer is fully connected, namely, all hidden neurons are connected to 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, . . . ,wk,v], where k is the number of hidden neurons. For every j ∈ [k] the vector wj ∈ Rpj is the weights vector of the j-th hidden neuron, and we have 1 ≤ pj ≤ d where d is the input dimention. For an input x ∈ Rd we denote by xj ∈ Rpj a sub-vector of x, such that xj includes the coordinates of x that are connected to the j-th hidden neuron. Thus, given x, the input to the j-th hidden neuron is 〈wj ,xj〉. The vector v ∈ Rk is the weights vector of the second layer. Overall, we have Φ(θ;x) = ∑ j∈[k] vjσ(w > j x j).
Lemma C.3. Let Φ be a depth-2 linear or ReLU network in Nno-share, parameterized by θ = [w1, . . . ,wk,v]. Consider minimizing any differentiable loss function (e.g., the exponential or the logistic loss) over a dataset using GF. Then, for every j ∈ [k] at all time t we have
d
dt
( ‖wj‖2 − v2j ) = 0 .
Proof. We have
L(θ) = ∑ i∈[n] ` (yiΦ(θ;xi)) = ∑ i∈[n] ` yi ∑ l∈[k] vlσ(w > l x j i )  . Hence
d
dt
( ‖wj‖2 ) = 2〈wj ,
dwj dt 〉 = −2〈wj ,∇wjL(θ)〉
= −2 ∑ i∈[n] `′ yi ∑ l∈[k] vlσ(w > l x l i)  · yivjσ′(w>j xji )w>j xji = −2
∑ i∈[n] `′ yi ∑ l∈[k] vlσ(w > l x l i)  · yivjσ(w>j xji ) . Moreover,
d
dt
( v2j )
= 2vj dvj dt = −2vj∇vjL(θ) = −2vj ∑ i∈[n] `′ yi ∑ l∈[k] vlσ(w > l x l i)  · yiσ(w>j xji ) . Hence the lemma follows.
Using the above lemma, we show the following:
Lemma C.4. Let Φ be a depth-2 linear or ReLU network in Nno-share, parameterized by θ = [w1, . . . ,wk,v]. Consider minimizing any differentiable loss function (e.g., the exponential or the logistic loss) over a dataset using GF starting from θ(0). Assume that limt→∞ ‖θ(t)‖ = ∞ and that θ(t) converges in direction to θ̃ = [w̃1, . . . , w̃k, ṽ], i.e., θ̃ = ‖θ̃‖ · limt→∞ θ(t)‖θ(t)‖ . Then, for every l ∈ [k] we have ‖w̃l‖ = |ṽl|.
Proof. For every l ∈ [k], let ∆l = ‖wl(0)‖2 − vl(0)2. By Lemma C.3, we have for every l ∈ [k] and t ≥ 0 that ‖wl(t)‖2 − vl(t)2 = ∆l, 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
|ṽl| = ‖θ̃‖ · lim t→∞ |vl(t)| ‖θ(t)‖ = ‖θ̃‖ · lim t→∞ √ ‖wl(t)‖2 −∆l ‖θ(t)‖ .
Thus, if limt→∞ ‖wl(t)‖ =∞, then we have |ṽl| = ‖θ̃‖ · limt→∞ ‖wl(t)‖‖θ(t)‖ = ‖w̃l‖.
Assume now that ‖wl(t)‖ 6→ ∞. By the definition of θ̃ we have ‖w̃l‖ = ‖θ̃‖ · limt→∞ ‖wl(t)‖‖θ(t)‖ . Since limt→∞ ‖wl(t)‖ ‖θ(t)‖ exists and limt→∞ ‖θ(t)‖ =∞, then we have limt→∞ ‖wl(t)‖ ‖θ(t)‖ = 0. Hence,
limt→∞ |vl(t)| ‖θ(t)‖ = limt→∞ √ ‖wl(t)‖2−∆l ‖θ(t)‖ = 0. Therefore ‖w̃l‖ = ṽl = 0.

heading: C.2 PROOF OF THM. 3.1
text: Suppose that the network Φ is parameterized by θ = [W (1), . . . ,W (m)]. By Thm. 2.1, GF converges in direction to a KKT point θ̃ = [W̃ (1), . . . , W̃ (m)] of Problem 1. For every l ∈ [m] let ∆l =∥∥W (l)(0)∥∥2 F − ∥∥W (1)(0)∥∥2
F . By Lemma C.1, we have for every l ∈ [m] and t ≥ 0 that∥∥∥W (l)(t)∥∥∥2 F − ∥∥∥W (1)(t)∥∥∥2 F = l−1∑ j=1 ∥∥∥W (j+1)(t)∥∥∥2 F − ∥∥∥W (j)(t)∥∥∥2 F = l−1∑ j=1 ∥∥∥W (j+1)(0)∥∥∥2 F − ∥∥∥W (j)(0)∥∥∥2 F
= ∥∥∥W (l)(0)∥∥∥2 F − ∥∥∥W (1)(0)∥∥∥2 F = ∆l .
Hence, we have∥∥∥W̃ (l)∥∥∥ F = ‖θ̃‖ · lim t→∞ ∥∥W (l)(t)∥∥ F ‖θ(t)‖ = ‖θ̃‖ · lim t→∞ √∥∥W (1)(t)∥∥2 F + ∆l ‖θ(t)‖ .
Since by Thm. 2.1 we have limt→∞ ‖θ(t)‖ =∞, then limt→∞ ∥∥W (1)(t)∥∥
F =∞, and we have∥∥∥W̃ (l)∥∥∥
F = ‖θ̃‖ · lim t→∞
∥∥W (1)(t)∥∥ F ‖θ(t)‖ = ∥∥∥W̃ (1)∥∥∥ F := C .
By Ji & Telgarsky (2020) (Proposition 4.4), when GF on a fully-connected linear network w.r.t. the exponential loss or the logistic loss converges to zero loss, then we have the following. There are unit vectors v0, . . . ,vm such that
lim t→∞ W (l)(t)∥∥W (l)(t)∥∥ F = vlv > l−1
for every l ∈ [m]. Moreover, we have vm = 1, and v0 = u where u := arg max
‖u‖=1 min i∈[n]
yiu >xi
is the unique linear max margin predictor.
Note that we have
W̃ (l)
C = W̃ (l)∥∥∥W̃ (l)∥∥∥ F = ‖θ̃‖ · limt→∞ W (l)(t) ‖θ(t)‖ ‖θ̃‖ · limt→∞ ‖W (l)(t)‖ F ‖θ(t)‖ = lim t→∞ W (l)(t)∥∥W (l)(t)∥∥ F = vlv > l−1 .
Thus, W̃ (l) = Cvlv>l−1 for every l ∈ [m].
Let ũ = W̃ (m) · . . . ·W̃ (1) = Cmu. Since θ̃ is a KKT point of Problem 1, we have for every l ∈ [m]
W̃ (l) = ∑ i∈[n] λiyi ∂Φ(θ̃;xi) ∂W (l) ,
where λi ≥ 0 for every i, and λi = 0 if yiΦ(θ̃;xi) 6= 1. Since W̃ (l) are non-zero then there is i ∈ [n] such that 1 = yiΦ(θ̃;xi) = yiũ>xi = yiCmu>xi. Likewise, since θ̃ satisfies the constraints of Problem 1, then for every i ∈ [n] we have 1 ≤ yiΦ(θ̃;xi) = yiCmu>xi. Since, u is a unit vector that maximized the margin, then we have
‖ũ‖ = Cm = min ‖u′‖ s.t. yiu′>xi ≥ 1 for all i ∈ [n] . (5)
Assume toward contradiction that there is θ′ with ‖θ′‖ < ‖θ̃‖ that satisfies the constraints in Problem 1. Let u′ = W ′(m) · . . . ·W ′(1). By Eq. 5 we have ‖u′‖ ≥ ‖ũ‖ = Cm. Moreover, we have ‖u′‖ = ∥∥W ′(m) · . . . ·W ′(1)∥∥ ≤ ∏l∈[m] ∥∥W ′(l)∥∥F due to the submultiplicativity of the Frobenius norm. Hence ∏ l∈[m] ∥∥W ′(l)∥∥ F ≥ Cm. The following lemma implies that
‖θ′‖2 = ∑ l∈[m] ∥∥∥W ′(l)∥∥∥2 F ≥ m · C2 = ∑ l∈[m] ∥∥∥W̃ (l)∥∥∥2 F = ∥∥∥θ̃∥∥∥2
in contradiction to our assumption, and thus completes the proof. Lemma C.5. Let a1, . . . , am be real numbers such that ∏ j∈[m] aj ≥ Cm for some C ≥ 0. Then∑
j∈[m] a 2 j ≥ m · C2.
Proof. It suffices to prove the claim for the case where ∏ j∈[m] aj = C m. Indeed, if ∏ j∈[m] aj > Cm then we can replace some aj with an appropriate a′j such that |a′j | < |aj | and we only decrease∑ j∈[m] a 2 j . Consider the following problem
min 1
2 ∑ j∈[m] a2j s.t. ∏ j∈[m] aj = C m .
Using the Lagrange multipliers we obtain that there is some λ ∈ R such that for every l ∈ [m] we have al = λ · ∏ j 6=l aj . Thus, a 2 l = λ · ∏ j∈[m] aj . It implies that a 2 1 = . . . = a 2 m. Since∏
j∈[m] aj = C m then |aj | = C for every j ∈ [m]. Hence, ∑ j∈[m] a 2 j = mC 2.

heading: C.3 PROOF OF THM. 3.2
text: Consider an initialization θ(0) is such that w1(0) satisfies 〈w1(0),x1〉 > 0 and 〈w1(0),x2〉 > 0, and w2(0) satisfies 〈w2(0),x1〉 < 0 and 〈w2(0),x2〉 < 0. Moreover, assume that v1(0) > 0. Note that for every θ such that 〈w2,x1〉 < 0 and 〈w2,x2〉 < 0 we have ∇w2L(θ) = 2∑ i=1 `′(yiΦ(θ;xi)) · yi∇w2Φ(θ;xi) = 2∑ i=1 `′(yiΦ(θ;xi)) · yi∇w2 [ v1σ(w > 1 xi) + v2σ(w > 2 xi)
] =
2∑ i=1 `′(yiΦ(θ;xi)) · yiv2σ′(w>2 xi)xi = 0 .
and ∇v2L(θ) = 2∑ i=1 `′(yiΦ(θ;xi)) · yi∇v2Φ(θ;xi) = 2∑ i=1 `′(yiΦ(θ;xi)) · yi∇v2 [ v1σ(w > 1 xi) + v2σ(w > 2 xi) ] =
2∑ i=1 `′(yiΦ(θ;xi)) · yiσ(w>2 xi) = 0 .
Hence, w2 and v2 get stuck in their initial values. Moreover, we have ∇v1L(θ) = 2∑ i=1 `′(yiΦ(θ;xi)) · yi∇v1 [ v1σ(w > 1 xi) + v2σ(w > 2 xi) ] = 2∑ i=1 `′(yiΦ(θ;xi)) · σ(w>1 xi) ≤ 0 .
Therefore, for every t ≥ 0 we have v1(t) ≥ v1(0) > 0. We denote w1 = (w1[1], w1[2]). Since 〈w1(0),xj〉 > 0 for j ∈ {1, 2} then w1[2](0) > 0. Assume w.l.o.g. that w1[1](0) ≥ 0 (the case where w1[1](0) ≤ 0 is similar). For every w1 that satisfies w1[2] ≥ 0 and 0 ≤ w1[1] ≤ w1[1](0) we have 〈w1,x1〉 > 〈w1,x2〉 > 0. Thus,
∇w1L(θ) = 2∑ i=1 `′(yiΦ(θ;xi)) · yi∇w1 [ v1σ(w > 1 xi) + v2σ(w > 2 xi) ] =
2∑ i=1 `′(yi(v1σ(w > 1 xi) + 0)) · yiv1σ′(w>1 xi)xi
= 2∑ i=1 `′(v1w > 1 xi) · v1xi .
Since `′ is negative and monotonically increasing, and since v1w>1 x1 > v1w > 1 x2, then dw1[1] dt ≤ 0. Also, dw1[2]dt > 0. Moreover, if w1[1] = 0 then v1w > 1 x1 = v1w > 1 x2 and thus dw1[1] dt = 0. Hence, for every t we have w1[2](t) ≥ w1[2](0) > 0 and 0 ≤ w1[1](t) ≤ w1[1](0). If L(θ) ≥ 1 then for some i ∈ {1, 2} we have `(yiΦ(θ;xi)) ≥ 12 and hence `
′(yiΦ(θ;xi)) ≤ c for some constant c < 0. Since we also have v1 ≥ v1(0) > 0, we have
dw1[2]
dt ≥ −c · v1(0) ·
1 4 .
Therefore, if the initialization θ(0) is such that L(θ) ≥ 1 then w1[2](t) increases at rate at least (−c)·v1(0)
4 while w1[1](t) remains in [0, w1[1](0)]. Note that for such w1[1] and v1 ≥ v1(0) > 0, if w1[2] is sufficiently large then we have v1〈w1,xi〉 ≥ 1 for i ∈ {1, 2}. Hence, there is some t0 such that L(θ(t0)) ≤ 2`(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 1, and we have limt→∞ L(θ(t)) = 0 and limt→∞ ‖θ(t)‖ = ∞. It remains to show that it does not converge in direction to a local optimum of Problem 1.
Let θ̄ = limt→∞ θ(t) ‖θ(t)‖ . We denote θ̄ = [w̄1, w̄2, v̄1, v̄2]. We show that w̄1 = 1√ 2 (0, 1)>, v̄1 = 1√ 2
, w̄2 = 0 and v̄2 = 0. By Lemma C.1, we have for every t ≥ 0 that v1(t)2 − ‖w1(t)‖2 = v1(0)
2 − ‖w1(0)‖2 := ∆. Since for every t we have w2(t) = w2(0) and v2(t) = v2(0), and since limt→∞ ‖θ(t)‖ = ∞ then we have limt→∞ ‖w1(t)‖ = ∞ and limt→∞ |v1(t)| = ∞. Also, since limt→∞ ‖w1(t)‖ =∞ and w1[1](t) ∈ [0, w1[1](0)] then limt→∞ w1[2](t) =∞. Note that
‖θ(t)‖ = √ ‖w1(t)‖2 + v1(t)2 + ‖w2(0)‖2 + v2(0)2 = √ ∆ + 2 ‖w1(t)‖2 + ‖w2(0)‖2 + v2(0)2 .
Since w1[1](t) ∈ [0, w1[1](0)] and ‖θ(t)‖ → ∞, we have
w̄1[1] = lim t→∞
w1[1](t)
‖θ(t)‖ = 0 .
Moreover,
w̄1[2] = lim t→∞
w1[2](t)
‖θ(t)‖ = lim t→∞
√ (w1[2](t))2
∆ + 2(w1[1](t))2 + 2(w1[2](t))2 + ‖w2(0)‖2 + v2(0)2 = 1√ 2 ,
and
w̄2 = lim t→∞
w2(t) ‖θ(t)‖ = lim t→∞ w2(0) ‖θ(t)‖ = 0 .
Finally, by Lemma C.4 and since v1(t) > 0, we have v̄1 = ‖w̄1‖ = 1√2 . By Lemma C.4 we also have |v̄2| = ‖w̄2‖ = 0.
Next, we show that θ̄ does not point at the direction of a local optimum of Problem 1. Let θ̃ = [w̃1, w̃2, ṽ1, ṽ2] be a KKT point of Problem 1 that points at the direction of θ̄. Such θ̃ exists since θ(t) converges in direction to a KKT point. Thus, we have w̃2 = 0, ṽ2 = 0, w̃1 = α(0, 1)> and ṽ1 = α for some α > 0. Since θ̃ satisfies the KKT conditions, we have
w̃1 = 2∑ i=1 λi∇w1 ( yiΦ(θ̃;xi) ) = 2∑ i=1 λiyi ( ṽ1σ ′(w̃>1 xi)xi ) ,
where λi ≥ 0 and λi = 0 if yiΦ(θ̃;xi) 6= 1. Note that the KKT condition should be w.r.t. the Clarke subdifferential, but since w̃>1 xi > 0 for i ∈ {1, 2} then we use here the gradient. Hence, there is i ∈ {1, 2} such that yiΦ(θ̃;xi) = 1. Thus,
1 = yiΦ(θ̃;xi) = ṽ1σ(w̃ > 1 xi) + ṽ2σ(w̃ > 2 xi) = α ·
α 4 + 0 =
α2
4 .
Therefore, α = 2 and we have w̃1 = (0, 2)> and ṽ1 = 2.
In order to show that θ̃ is not a local optimum, we show that for every 0 < ′ < 1 there exists some θ′ such that ∥∥∥θ′ − θ̃∥∥∥ ≤ ′, θ′ satisfies Φ(θ′;xi) ≥ 1 for every i ∈ {1, 2}, and ‖θ′‖ < ‖θ̃‖. Let = ′2
9 < 1 2 . Let θ ′ = [w′1,w ′ 2, v ′ 1, v ′ 2] be such that w ′ 1 = ( 2 , 2− 2 ) >, w′2 = (− √
2 , 0)>, v′1 = 2 and v′2 = √ 2 . Note that
Φ(θ′;x1) = 2 · σ ( (
2 , 2− 2 )(1, 1 4 )> ) + √ 2 · σ ( (− √ 2 , 0)(1, 1 4 )> )
= 2 · σ (
2 +
1 2 − 2
) + √ 2 · σ ( − √ 2 ) = 1 ,
and
Φ(θ′;x2) = 2 · σ ( (
2 , 2− 2 )(−1, 1 4 )> ) + √ 2 · σ ( (− √ 2 , 0)(−1, 1 4 )> )
= 2 · σ ( −
2 +
1 2 − 2
) + √ 2 · σ (√ 2 ) = 1− 2 + 2 = 1 .
We also have ∥∥∥θ′ − θ̃∥∥∥2 = ‖w′1 − w̃1‖2 + ‖w′2 − w̃2‖2 + (v′1 − ṽ1)2 + (v′2 − ṽ2)2 = ( 2
4 + 4 2
) + 2 + 0 + 2 < 9 = ′2 .
Finally, we have
‖θ′‖2 = 2 4 + 4− 8 + 4 2 + 2 + 4 + 2 = 8− 4 + 17 2 4 < 8− 4 + 17 8 < 8 = ∥∥∥θ̃∥∥∥2 . Thus, ‖θ′‖ < ‖θ̃‖.

heading: C.4 PROOF OF THM. 4.1
text: Let x = (1, 2)> and y = 1. Let θ(0) such that w1(0) = w2(0) = (1, 0)>. Note that L(θ(0)) = `(1) < 1 for both linear and ReLU networks with the exponential loss or the logistic loss, and therefore by Thm. 2.1 GF converges in direction to a KKT point θ̃ of Problem 1, and we have limt→∞ L(θ(t)) = 0 and limt→∞ ‖θ(t)‖ = ∞. We denote w1 = (w1[1],w1[2])> and w2 = (w2[1],w2[2])
>. 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. w1[2] and w2[2] is zero, and the second hidden neuron remains inactive during the training. Moreover, w1[1] and w2[1] are strictly
increasing. Also, by Lemma C.3 we have for every t ≥ 0 that w1[1](t)2 = w2[1](t)2. Overall, θ̃ is such that w̃1 = w̃2 = (1, 0)>. Note that since the dataset is of size 1, then every KKT point of Problem 1 must label the input x with exactly 1.
It remains to show that θ̃ is not local optimum. Let 0 < < 1, and let θ′ = [w′1,w ′ 2] with w′1 = w ′ 2 = (√ 1− , √ 2 )> . Note that θ′ satisfies the constraints of Problem 1, since y·Φ(θ′;x) = 1− + 2 · 2 = 1. Moreover, we have ‖θ̃‖ 2 = 2 and ‖θ′‖2 = 2 ( 1− + 2 ) = 2− and therefore ‖θ′‖ < ‖θ̃‖.

heading: C.5 PROOF OF THM. 4.2

heading: C.5.1 PROOF OF PART 1
text: We assume w.l.o.g. that the second layer is fully-connected, namely, all hidden neurons are connected to the output neuron, since otherwise we can ignore disconnected neurons. For the network Φ we use the parameterization θ = [w1, . . . ,wk,v] introduced in Section C.1. Thus, we have Φ(θ;x) = ∑ l∈[k] vlw > l x l.
By Thm. 2.1, GF converges in direction to θ̃ = [w̃1, . . . , w̃k, ṽ] which satisfies the KKT conditions of Problem 1. Thus, there are λ1, . . . , λn such that for every j ∈ [k] we have
w̃j = ∑ i∈[n] λi∇wj ( yiΦ(θ̃;xi) ) = ∑ i∈[n] λiyiṽjx j i , (6)
and we have λi ≥ 0 for all i, and λi = 0 if yiΦ(θ̃;xi) = yi ∑ l∈[k] ṽlw̃ > l x l i 6= 1. By Thm. 2.1, we also have limt→∞ ‖θ(t)‖ =∞. Hence, by Lemma C.4 we have ‖w̃j‖ = |ṽj | for all j ∈ [k]. Consider the following problem
min ∑ l∈[k] ‖ul‖ s.t. ∀i ∈ [n] yi ∑ l∈[k] u>l x l i ≥ 1 . (7)
For every l ∈ [k] we denote ũl = ṽl · w̃l. Since we assume that w̃l 6= 0 for every l ∈ [k], and since ‖w̃l‖ = |ṽl|, then ũl 6= 0 for all l ∈ [k]. Note that since w̃1, . . . , w̃k, ṽ satisfy the constraints in Problem 1, then ũ1, . . . , ũk satisfy the constraints in the above problem. In order to show that ũ1, . . . , ũk satisfy the KKT condition of the problem, we need to prove that for every j ∈ [k] we have
ũj ‖ũj‖ = ∑ i∈[n] λ′iyix j i (8)
for some λ′i ≥ 0 such that λ′i = 0 if yi ∑ l∈[k] ũ > l x l i 6= 1. From Eq. 6 and since ‖w̃l‖ = |ṽl| for every l ∈ [k], we have ũj = ṽj · w̃j = ṽj
∑ i∈[n] λiyiṽjx j i = ṽ 2 j ∑ i∈[n] λiyix j i = ‖ṽjw̃j‖ ∑ i∈[n] λiyix j i = ‖ũj‖ ∑ i∈[n] λiyix j i .
Note that we have λi ≥ 0 for all i, and λi = 0 if yi ∑ l∈[k] ũ > l x l i = yi ∑ l∈[k] ṽlw̃ > l x l i 6= 1. Hence Eq. 8 holds with λ′1, . . . , λ ′ n that satisfy the requirement. Since the objective in Problem 7 is convex and the constraints are affine functions, then its KKT condition is sufficient for global optimality. Namely, ũ1, . . . , ũk are a global optimum for problem 7.
We now deduce that θ̃ is a global optimum for Problem 1. Assume toward contradiction that there is a solution θ′ = [w′1, . . . ,w ′ k,v ′] for the constraints in Problem 1 such that ‖θ′‖2 < ‖θ̃‖2. Let u′l = v ′ lw ′ l. Note that the vectors u
′ l satisfy the constraints in Problem 7. Moreover, we have∑
l∈[k] ‖u′l‖ = ∑ l∈[k] |v′l|·‖w′l‖ ≤ ∑ l∈[k] 1 2 ( |v′l|2 + ‖w′l‖ 2 ) = 1 2 ‖θ′‖2 < 1 2 ∥∥∥θ̃∥∥∥2 = ∑ l∈[k] 1 2 ( |ṽl|2 + ‖w̃l‖2 ) . Since ‖w̃l‖ = |ṽl|, the above equals∑ l∈[k] ‖w̃l‖2 = ∑ l∈[k] |ṽl| · ‖w̃l‖ = ∑ l∈[k] ‖ũl‖ ,
which contradicts the global optimality of ũ1, . . . , ũk.

heading: C.5.2 PROOF OF PART 2
text: Let {(xi, yi)}4i=1 be a dataset such that yi = 1 for all i ∈ [4] and we have x1 = (0, 1)>, x2 = (1, 0)
>, x3 = (0,−1) and x4 = (−1, 0). Consider the initialization θ(0) = [w1(0),w2(0),w3(0),w4(0),v(0)] such that wi(0) = 2xi and vi(0) = 2 for every i ∈ [4]. Note that L(θ(0)) = 4`(4) < 1 for both the exponential loss and the logistic loss, and therefore by Thm. 2.1 GF converges in direction to a KKT point θ̃ of Problem 1, and we have limt→∞ L(θ(t)) = 0 and limt→∞ ‖θ(t)‖ =∞. We now show that for all t ≥ 0 we have wi(t) = α(t)xi and vi(t) = α(t) where α(t) > 0 and limt→∞ α(t) =∞. Indeed, for such θ(t), for every j ∈ [4] we have
−dwj dt = ∇wjL(θ) = 4∑ i=1 `′(yiΦ(θ;xi)) · yi∇wjΦ(θ;xi) = 4∑ i=1 `′ ( 4∑ l=1 vlσ(w > l xi) ) · ( vjσ ′(w>j xi)xi ) = `′(α2) · α ·
4∑ i=1 σ′(w>j xi)xi = ` ′(α2) · αxj ,
and
−dvj dt = ∇vjL(θ) = 4∑ i=1 `′(yiΦ(θ;xi)) · yi∇vjΦ(θ;xi) = 4∑ i=1 `′ ( 4∑ l=1 vlσ(w > l xi) ) · σ(w>j xi)
= `′(α2) · 4∑ i=1 σ(w>j xi) = ` ′(α2) · α .

heading: Moreover, since limt→∞ ‖θ(t)‖ =∞ then limt→∞ α(t) =∞.
text: Hence, the KKT point θ̃ is such that for every j ∈ [4] the vector w̃j points at the direction xj , and we have ṽj = ‖w̃j‖. Also, the vectors w̃1, w̃2, w̃3, w̃4 have equal norms. That is, w̃j = α̃xj and ṽj = α̃ for some α̃ > 0. Moreover, since it satisfies the KKT condition of Problem 1, then we have
w̃j = 4∑ i=1 λiyi∇wjΦ(θ̃;xi) ,
where λi ≥ 0 and λi = 0 if yiΦ(θ̃;xi) 6= 1. Hence, there is i such that yiΦ(θ̃;xi) = 1.Therefore, α̃2 = 1. Thus, we conclude that for all j ∈ [4] we have w̃j = xj and ṽj = 1. Note that w̃j 6= 0 for all j ∈ [4] as required.
Next, we show that θ̃ is not a local optimum of Problem 1. We show that for every 0 < < 1 there exists some θ′ such that ∥∥∥θ′ − θ̃∥∥∥ ≤ , θ′ satisfies the constraints of Problem 1, and ‖θ′‖ < ‖θ̃‖. Let ′ =
2 √ 2 . Let θ′ be such that v′j = ṽj = 1 for all j ∈ [4], and we have w′1 = ( ′, 1 − ′)>,
w′2 = (1 − ′,− ′)>, w′3 = (− ′,−1 + ′)> and w′4 = (−1 + ′, ′)>. It is easy to verify that θ′ satisfies the constraints. Indeed, we have Φ(θ′;xi) = ((1− ′) + ′ + 0 + 0) = 1. Also, we have∥∥∥θ′ − θ̃∥∥∥ = √4 · 2 ′2 = 2√2 ′ = . Finally,
‖θ′‖2 = 4 · ( ′2 + (1− ′)2 ) + 4 = 8 + 8 ′ ( ′ − 1) < 8 = ‖θ̃‖2 .

heading: C.6 PROOF OF THM. 4.3
text: We assume w.l.o.g. that the second layer is fully-connected, namely, all hidden neurons are connected to the output neuron, since otherwise we can ignore disconnected neurons. For the network Φ we use the parameterization θ = [w1, . . . ,wk,v] introduced in Section C.1. Thus, we have Φ(θ;x) = ∑ l∈[k] vlσ(w > l x l).
We denote θ̃ = [w̃1, . . . , w̃k, ṽ]. Since θ̃ is a KKT point of Problem 1, then there are λ1, . . . , λn such that for every j ∈ [k] we have
w̃j = ∑ i∈[n] λi∇wj ( yiΦ(θ̃;xi) ) = ∑ i∈[n] λiyiṽjσ ′(w̃>j x j i )x j i , (9)
and we have λi ≥ 0 for all i, and λi = 0 if yiΦ(θ̃;xi) = yi ∑ l∈[k] ṽlσ(w̃ > l x l i) 6= 1. Note that the KKT condition should be w.r.t. the Clarke subdifferential, but since for all i, j we have w̃>j x j i 6= 0 by our assumption, then we can use here the gradient. By Thm. 2.1, we also have limt→∞ ‖θ(t)‖ =∞. Hence, by Lemma C.4 we have ‖w̃j‖ = |ṽj | for all j ∈ [k].
For i ∈ [n] and j ∈ [k] let Aij = 1(w̃>j x j i ≥ 0). Consider the following problem min ∑ l∈[k] ‖ul‖ s.t. ∀i ∈ [n] yi ∑ l∈[k] Ailu > l x l i ≥ 1 . (10)
For every l ∈ [k] let ũl = ṽl · w̃l. Since we assume that the inputs to all neurons in the computations Φ(θ̃;xi) are non-zero, then we must have w̃l 6= 0 for every l ∈ [k]. Since we also have ‖w̃l‖ = |ṽl|, then ũl 6= 0 for all l ∈ [k]. Note that since w̃1, . . . , w̃k, ṽ satisfy the constraints in Probelm 1, then ũ1, . . . , ũk satisfy the constraints in the above problem. Indeed, for every i ∈ [n] we have
yi ∑ l∈[k] Ailũ > l x l i = yi ∑ l∈[k] 1(w̃>l x l i ≥ 0)ṽlw̃>l xli = yi ∑ l∈[k] ṽlσ(w̃ > l x l i) ≥ 1 .
In order to show that ũ1, . . . , ũk satisfy the KKT condition of Probelm 10, we need to prove that for every j ∈ [k] we have
ũj ‖ũj‖ = ∑ i∈[n] λ′iyiAijx j i (11)
for some λ′1, . . . , λ ′ n such that for all i we have λ ′ i ≥ 0, and λ′i = 0 if yi ∑ l∈[k]Ailũ > l x l i 6= 1. From Eq. 9 and since ‖w̃l‖ = |ṽl| for every l ∈ [k], we have
ũj = ṽj ·w̃j = ṽj ∑ i∈[n] λiyiṽjAijx j i = ṽ 2 j ∑ i∈[n] λiyiAijx j i = ‖ṽjw̃j‖ ∑ i∈[n] λiyiAijx j i = ‖ũj‖ ∑ i∈[n] λiyiAijx j i . Note that we have λi ≥ 0 for all i, and λi = 0 if yi ∑ l∈[k] Ailũ > l x l i = yi ∑ l∈[k] ṽl1(w̃ > l x l i ≥ 0)w̃>l xli = yi ∑ l∈[k] ṽlσ(w̃ > l x l i) 6= 1 .
Hence Eq. 11 holds with λ′1, . . . , λ ′ n 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, ũ1, . . . , ũk are a global optimum for Problem 10.
We now deduce that θ̃ is a local optimum for Problem 1. Since for every i ∈ [n] and l ∈ [k] we have w̃>l x l i 6= 0, then there is > 0, such that for every i, l and every w′l with ‖w′l − w̃l‖ ≤ we have 1(w̃>l x l i ≥ 0) = 1(w′>l xli ≥ 0). Assume toward contradiction that there is a solution θ′ = [w′1, . . . ,w ′ k,v ′] for the constraints in Problem 1 such that ‖θ′ − θ̃‖ ≤ and ‖θ′‖2 < ‖θ̃‖2. Note that we have ‖w′l − w̃l‖ ≤ for every l ∈ [k]. We denote u′l = v′lw′l. The vectors u′1, . . . ,u′k satisfy the constraints in Problem 10, since we have
yi ∑ l∈[k] Ailu ′> l x l i = yi ∑ l∈[k] 1(w̃>l x l i ≥ 0)v′lw′>l xli = yi ∑ l∈[k] 1(w′>l x l i ≥ 0)v′lw′>l xli
= yi ∑ l∈[k] v′lσ(w ′> l x l i) ≥ 1 ,
where the last inequality is since θ′ satisfies the constraints in Probelm 1. Moreover, we have∑ l∈[k] ‖u′l‖ = ∑ l∈[k] |v′l|·‖w′l‖ ≤ ∑ l∈[k] 1 2 ( |v′l|2 + ‖w′l‖ 2 ) = 1 2 ‖θ′‖2 < 1 2 ∥∥∥θ̃∥∥∥2 = ∑ l∈[k] 1 2 ( |ṽl|2 + ‖w̃l‖2 ) . Since ‖w̃l‖ = |ṽl|, the above equals∑ l∈[k] ‖w̃l‖2 = ∑ l∈[k] |ṽl| · ‖w̃l‖ = ∑ l∈[k] ‖ũl‖ ,
which contradicts the global optimality of ũ1, . . . , ũk.
It remains to show that θ̃ may not be a global optimum of Problem 1, even if the network Φ is fully connected. The following lemma concludes the proof.
Lemma C.6. Let Φ be a depth-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 a dataset {(xi, yi)}ni=1 and an initialization θ(0), such that GF converges to zero loss, converges in direction to a KKT point θ̃ = [w̃1, w̃2, ṽ] of Problem 1 such that 〈w̃j ,xi〉 6= 0 for all j ∈ {1, 2} and i ∈ [n], and θ̃ is not a global optimum.
Proof. Let x1 = ( 1, 14 )> , x2 = ( −1, 14 )> , x3 = (0,−1), y1 = y2 = y3 = 1. Let {(x1, y1), (x2, y2), (x3, y3)} be a dataset. Consider the initialization θ(0) such that w1(0) = (0, 3), v1(0) = 3, w2(0) = (0,−2) and v2(0) = 2. Note that L(θ(0)) = 2` ( 9 4 ) + `(4) < 1 for both the exponential loss and the logistic loss, and therefore by Thm. 2.1 GF converges in direction to a KKT point θ̃ of Problem 1.
Note that for θ such that w1 = α ·(0, 1)> and w2 = β ·(0,−1)> for some α, β > 0, and v1, v2 > 0, we have ∇w1L(θ) = 3∑ i=1 `′(yiΦ(θ;xi)) · yi∇w1Φ(θ;xi) = 3∑ i=1 `′ ( v1σ(w > 1 xi) + v2σ(w > 2 xi) ) · v1σ′(w>1 xi)xi
= 2∑ i=1 `′(v1σ(w > 1 xi)) · v1xi = v1`′ ( v1 α 4 ) 2∑ i=1 xi ,
and
∇v1L(θ) = 3∑ i=1 `′(yiΦ(θ;xi)) · yi∇v1Φ(θ;xi) = 3∑ i=1 `′(yiΦ(θ;xi)) · σ(w>1 xi) .
Hence, −∇w1L(θ) points in the direction (0, 1)> and −∇v1L(θ) > 0. Moreover, we have ∇w2L(θ) = 3∑ i=1 `′(yiΦ(θ;xi)) · yi∇w2Φ(θ;xi) = 3∑ i=1 `′(v1σ(w > 1 xi) + v2σ(w > 2 xi)) · v2σ′(w>2 xi)xi
= `′(v2σ(w > 2 x3)) · v2x3 = v2`′(v2β)x3 ,
and
∇v2L(θ) = 3∑ i=1 `′(yiΦ(θ;xi)) · yi∇v2Φ(θ;xi) = 3∑ i=1 `′(v1σ(w > 1 xi) + v2σ(w > 2 xi)) · σ(w>2 xi)
= `′(v2σ(w > 2 x3))σ(w > 2 x3) = ` ′(v2β) · β .
Therefore, −∇w2L(θ) points in the direction (0,−1)> and −∇v2L(θ) > 0. Hence for every t we have w1(t) = α(t) · (0, 1)> for some α(t) > 0 and v1(t) > 0. Also, we have w2(t) = β(t) · (0,−1)> for some β(t) > 0 and v2(t) > 0. By Lemma C.1, we have for every t ≥ 0 that ‖w1(t)‖2 − v1(t)2 = ‖w1(0)‖2 − v1(0)2 = 0 and ‖w2(t)‖2 − v2(t)2 = ‖w2(0)‖2 − v2(0)2 = 0. Hence, we have v1(t) = α(t) and v2(t) = β(t). Therefore, we have w̃1 = α̃ · (0, 1)> and ṽ1 = α̃ for some α̃ ≥ 0. Likewise, we have w̃2 = β̃ ·(0,−1)> and ṽ2 = β̃ for some β̃ ≥ 0. Since θ̃ satisfies the constraints in Probelm 1, then α̃ ≥ 2 and β̃ ≥ 1. Note that 〈w̃j ,xi〉 6= 0 for all j ∈ {1, 2} and i ∈ {1, 2, 3}.
We now show that there exists a solution θ′ to Problem 1 with a smaller norm, and hence θ̃ is not a global optimum. Let θ′ = [w′1,w ′ 2,v ′] such that w′1 = x1 α̃‖x1‖ , v ′ 1 = α̃, w ′ 2 = 1 β̃ · ( − 54 ,−1 ) , and v′2 = β̃. It is easy to verify that θ ′ satisfies the constraints in Problem 1, and we have
‖θ′‖2 = 1 α̃2 + α̃2 + 1
β̃2
( 25
16 + 1
) + β̃2 < 1
4 + α̃2 + 1 · 3 + β̃2 < β̃2 + α̃2 + α̃2 + β̃2 = ‖θ̃‖2 .

heading: C.7 PROOF OF THM. 4.4
text: Let x = (
4, 1√ 2 ,−4, 1√ 2
)> and y = 1. Let θ(0) = [w(0),v(0)] where w(0) = (0, 1)> and
v(0) = (
1√ 2 , 1√ 2
)> . Note that Ψ(θ(0);x) = 1 and hence L(θ(0)) < 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 1, and we have limt→∞ L(θ(t)) = 0 and limt→∞ ‖θ(t)‖ =∞. 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 v1(t) = v2(t) > 0 for all t ≥ 0. More formally, this claim follows from the following calculation. For j ∈ {1, 2} we have
∇vjL(θ) = `′(yΦ(θ;x)) · y∇vjΦ(θ;x) = `′(yΦ(θ;x)) · σ(w>x(j)) . Moreover,
∇wL(θ) = `′(yΦ(θ;x))·y∇wΦ(θ;x) = `′(yΦ(θ;x))· ( v1σ ′(w>x(1))x(1) + v2σ ′(w>x(2))x(2) ) .
Hence, if v1 = v2 > 0 and w points in the direction (0, 1)>, then it is easy to verify that∇v1L(θ) = ∇v1L(θ) < 0 and that ∇wL(θ) points in the direction of −(x(1) + x(2)) = −(0, √ 2)>. Furthermore, by Lemma C.2, for every t ≥ 0 we have ‖w(t)‖2 − ‖v(t)‖2 = ‖w(0)‖2 − ‖v(0)‖2 = 0.
Therefore, the KKT point θ̃ = [w̃, ṽ] is such that w̃ points at the direction (0, 1)>, ṽ1 = ṽ2 > 0, and ‖w̃‖ = ‖ṽ‖. Since θ̃ satisfies the KKT conditions of Problem 1, then we have
w̃ = λ∇w ( yΦ(θ̃;x) ) ,
where λ ≥ 0 and λ = 0 if yΦ(θ̃;x) 6= 1. Hence, we must have yΦ(θ̃;x) = 1. Letting z := ṽ1 = ṽ2 and using 2z2 = ‖ṽ‖2 = ‖w̃‖2 = w̃22 , we have
1 = ṽ1σ(w̃ >x(1)) + ṽ2σ(w̃ >x(2)) = zw̃>x(1) + zw̃>x(2) = zw̃> ( x(1) + x(2) ) = z · w̃2 √ 2
= w̃2√ 2 · w̃2 √ 2 = w̃22 .
Therefore, w̃ = (0, 1)> and ṽ = (
1√ 2 , 1√ 2
) . Note that we have 〈w̃,x(1)〉 6= 0 and 〈w̃,x(2)〉 6= 0.
It remains to show that θ̃ is not a local optimum of Problem 1. We show that for every 0 < ′ < 1 there exists some θ′ = [w′,v′] such that ∥∥∥θ′ − θ̃∥∥∥ ≤ ′, θ′ satisfies the constrains in Problem 1, and ‖θ′‖ < ‖θ̃‖. Let = ′2
2 ∈ (0, 1/2), and let w ′ = (
√ , 1− )> and v′ = ( 1√ 2 + √ 2 , 1√ 2 − √ 2 )> .
Note that ‖θ′‖2 = ‖w′‖2 + ‖v′‖2 = + (1− )2 + (
1√ 2 +
√
2
)2 + ( 1√ 2 − √ 2 )2 = + 1 + 2 − 2 + 1 + 2
= 2− 2 + 2 < 2− 2 + 2 = 2 = ‖w̃‖2 + ‖ṽ‖2 = ∥∥∥θ̃∥∥∥2 . Moreover, ∥∥∥θ′ − θ̃∥∥∥2 = + 2 +
4 + 4 = 2 +
3 2 = ′4 4 + 3 ′2 4 < ′2 4 + 3 ′2 4 = ′2 .
Finally, we show that θ′ satisfies the constraints:
Φ(θ′;x) = v′1σ(w ′>x(1)) + v′2σ(w ′>x(2))
= ( 1√ 2 + √ 2 )( 4 √ + 1√ 2 · (1− ) ) + ( 1√ 2 − √ 2 )( −4 √ + 1√ 2 · (1− ) ) =
1√ 2 · (1− ) ( 1√ 2 + √ 2 + 1√ 2 − √ 2 ) + 4 √ ( 1√ 2 + √ 2 − 1√ 2 + √ 2 ) = 1− + 4 = 1 + 3 ≥ 1 .

heading: C.8 PROOF OF THM. 5.1
text: Let x = (1, 1)> and y = 1. Consider the initialization θ(0) = [w1(0), . . . ,wm(0)], where wj(0) = (1, 1)> for every j ∈ [m]. Note that L(θ(0)) = `(2) < 1 for both linear and ReLU networks with the exponential loss or the logistic loss, and therefore by Thm. 2.1 GF converges in direction to a KKT point θ̃ of Problem 1, and we have limt→∞ L(θ(t)) = 0 and limt→∞ ‖θ(t)‖ =∞. It remains 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 θ(0), it follows that for all t the network Φ(θ(t); ·) remains symmetric, namely, there are αj(t) such that wj(t) = (αj(t), αj(t)). Moreover, by Lemma C.2, for every t ≥ 0 and j, l ∈ [m] we have αj(t) = αl(t) := α(t). Thus, GF converges in direction to the KKT point θ̃ = [w̃1, . . . , w̃m] such that w̃j = ( 2−1/m, 2−1/m )> for all j ∈ [m]. Note that since the dataset is of size 1, then every KKT point of Problem 1 must label the input x with exactly 1.
We now show that θ̃ is not a local optimum of Problem 1. The following arguments hold for both linear and ReLU networks. Let 0 < < 12 . Let θ ′ = [w′1, . . . ,w ′ m] such that for every j ∈ [m] we
have w′j = (( 1+ 2 )1/m , ( 1− 2 )1/m)> . We have
y · Φ(θ′;x) = ( 1 +
2
) + ( 1−
2
) = 1 .
Hence, θ′ satisfies the constraints in Problem 1. We now show that for every sufficiently small > 0 we have ‖θ′‖2 < ‖θ̃‖2. We need to show that
m
( 1 +
2
)2/m +m ( 1−
2
)2/m < 2m ( 1
2
)2/m .
Therefore, it suffices to show that
(1 + ) 2/m + (1− )2/m < 2 .
Let g : R→ R such that g(s) = (1 + s)2/m + (1− s)2/m. We have g(0) = 2. The derivatives of g satisfy
g′(s) = 2
m (1 + s)
2 m−1 − 2
m (1− s)
2 m−1 ,
and
g′′(s) = 2
m
( 2 m − 1 ) (1 + s) 2 m−2 + 2 m ( 2 m − 1 ) (1− s) 2 m−2 .
Since m ≥ 3 we have g′(0) = 0 and g′′(0) < 0. Hence, 0 is a local maximum of g. Therefore for every sufficiently small > 0 we have g( ) < 2 and thus ‖θ′‖2 < ‖θ̃‖2.
Finally, note that the inputs to all neurons in the computation Φ(θ̃;x) are positive.

heading: C.9 PROOF OF THM. 5.2
text: By Thm. 2.1 GF converge in direction to a KKT point θ̃ = [ũ(l)]ml=1 of Problem 1. We now show that for every layer l ∈ [m] the parameters vector ũ(l) is a global optimum of Problem 3 w.r.t. θ̃.
Since θ̃ is a KKT point of Problem 1, then there are λ1, . . . , λn such that for every l ∈ [m] we have
ũ(l) = ∑ i∈[n]
λi ∂ ( yiΦ(θ̃;xi) ) ∂u(l) ,
where λi ≥ 0 for all i, and λi = 0 if yiΦ(θ̃;xi) 6= 1. Letting θ′(u(l)) = [ũ(1), . . . , ũ(l−1),u(l), ũ(l+1), . . . , ũ(m)], the above equation can be written as
ũ(l) = ∑ i∈[n] λi ∂ ( yiΦ(θ ′(ũ(l));xi) ) ∂u(l) ,
where λi ≥ 0 for all i, and λi = 0 if yiΦ(θ′(ũ(l));xi) = yiΦ(θ̃;xi) 6= 1. Moreover, if the constraints in Problem 1 are satisfies in θ̃, then the constrains in Problem 3 are also satisfied for every l ∈ [m] in ũ(l) w.r.t. θ̃. Hence, for every l ∈ [m] the KKT conditions of Problem 3 w.r.t. θ̃ hold. Since the constraints in Problem 3 are affine and the objective is convex, then this KKT point is a global optimum.

heading: C.10 PROOF OF THM. 5.3
text: Let {(xi, yi)}4i=1 be a dataset such that yi = 1 for all i ∈ [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) we 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 θ̃ of Problem 1. Moreover, in the proof of Thm. 4.2 we showed that the KKT point θ̃ is such that for all j ∈ [4] we have w̃j = xj and ṽj = 1.
We show that w̃1, w̃2, w̃3, w̃4 is not a local optimum of Problem 3 w.r.t. θ̃. It suffices to prove that for every 0 < < 1 there exists some θ′ such that v′j = ṽj for all j ∈ [4], ‖θ′ − θ̃‖ ≤ , θ′ satisfies the constraints, and ‖θ′‖ < ‖θ̃‖. The existence of such θ′ is shown in the proof of Thm. 4.2. Hence, we conclude the proof of the theorem.

heading: C.11 PROOF OF THM. 5.4
text: By Thm. 2.1 GF converge in direction to a KKT point θ̃ = [ũ(l)]ml=1 of Problem 1. Let l ∈ [m] and assume that for every i ∈ [n] the inputs to all neurons in layers l, . . . ,m− 1 in the computation Φ(θ̃;xi) are non-zero. We now show that the parameters vector ũ(l) is a local optimum of Problem 3 w.r.t. θ̃.
For i ∈ [n] and k ∈ [m−1] we denote by x(k)i ∈ Rdk the output of the k-th layer in the computation Φ(θ̃;xi), and denote x (0) i = xi. If l ∈ [m − 1] then we define the following notations. We denote by fl : Rdl → R the function computed by layers l + 1, . . . ,m of Φ(θ̃; ·). Thus, we have Φ(θ̃;xi) = fl(x (l) i ) = fl ◦ σ ( W̃ (l)x (l−1) i ) , where W̃ (l) is the weight matrix that corresponds to ũ(l). For i ∈ [n] we denote by hi the function u(l) 7→ fl ◦σ(W (l)x(l−1)i ) where W (l) is the weights matrix that corresponds to u(l). Thus, Φ(θ̃;xi) = hi(ũ(l)). If l = m then we denote by hi the function u(m) 7→W (m)x(m−1)i , thus we also have Φ(θ̃;xi) = hi(ũ(m)).
Since θ̃ is a KKT point of Problem 1, then there are λ1, . . . , λn such that
ũ(l) = ∑ i∈[n]
λi ∂ ( yiΦ(θ̃;xi) ) ∂u(l) = ∑ i∈[n] λi ∂ ∂u(l) [ yi · hi(ũ(l)) ] ,
where λi ≥ 0 for all i, and λi = 0 if yi · hi(ũ(l)) 6= 1. Note that since the inputs to all neurons in layers l, . . . ,m − 1 in the computation Φ(θ̃;xi) are non-zero, then the function hi is differentiable at ũ(l). Therefore in the above KKT condition we use the derivative rather than the Clarke subdifferential. Moreover, if the constraints in Problem 1 are satisfies in θ̃, then the constrains in Problem 3 are also satisfied in ũ(l) w.r.t. θ̃. Hence, the KKT condition of Problem 3 w.r.t. θ̃ holds.
Also, note that since the inputs to all neurons in layers l, . . . ,m − 1 in the computation Φ(θ̃;xi) are non-zero, then the function hi is locally linear near ũ(l). We denote this linear function by h̃i. Therefore, ũ(l) is a KKT point of the following problem
min u(l)
1
2 ∥∥∥u(l)∥∥∥2 s.t. ∀i ∈ [n] yih̃i(u(l)) ≥ 1 . Since the constrains here are affine and the objective is convex, then ũ(l) is a global optimum of the above problem. Thus, there is a small ball near ũ(l) where ũ(l) is the optimum of Problem 3 w.r.t. θ̃, namely, it is a local optimum.
Finally, note that in the proof of Lemma C.6 the parameters vector θ′ is obtained from θ̃ by changing only the first layer. Hence, in ReLU networks GF might converge in direction to a KKT point of Problem 1 which is not a global optimum of Problem 3, even if all inputs to neurons are non-zero.

heading: C.12 PROOF OF THM. 6.1
text: We have du
dt = −∂`(yΦ(θ;x)) ∂u = −∂`(vw + u) ∂u = −`′(vw + u) .
dw dt = −∂`(yΦ(θ;x)) ∂w = −∂`(vw + u) ∂w = −`′(vw + u) · v .
dv dt = −∂`(yΦ(θ;x)) ∂w = −∂`(vw + u) ∂v = −`′(vw + u) · w .
Since we also have v(0) = w(0) then for every t ≥ 0 we have v(t) = w(t). Note that `′(vw+u) < 0 and hence all parameters u,w, v are strictly increasing. Since v(0) = w(0) > 1 then for every t ≥ 0 we have v(t) = w(t) > 1 and hence du(t)dt < dw(t) dt = dv(t) dt . Therefore u(t) ≤ v(t) = w(t) for all t.
We now calculate the derivative of
γ̄(t) = v ‖θ‖ · w ‖θ‖ + u ‖θ‖ =
vw
v2 + w2 + u2 + u√ v2 + w2 + u2 .
We have d
dt
[ vw
v2 + w2 + u2
] =
1 (v2 + w2 + u2)2 [( −`′(vw + u)w2 − `′(vw + u)v2 ) (v2 + w2 + u2)
−vw (2v(−`′(vw + u)w) + 2w(−`′(vw + u)v) + 2u(−`′(vw + u)))] , and by plugging in w = v the above equals
1 (2v2 + u2)2 [( −2`′(v2 + u)v2 ) (2v2 + u2) + v2`′(v2 + u) ( 4v2 + 2u )] = −2`′(v2 + u)v2
(2v2 + u2)2 [ (2v2 + u2)− ( 2v2 + u )] = −2`′(v2 + u)v2u(u− 1) (2v2 + u2)2 .
Next, we have d
dt
[ u√
v2 + w2 + u2
] =
1
v2 + w2 + u2
[ (−`′(vw + u)) √ v2 + w2 + u2
−u 1 2 √ v2 + w2 + u2
(2v(−`′(vw + u)w) + 2w(−`′(vw + u)v) + 2u(−`′(vw + u))) ]
= −`′(vw + u) v2 + w2 + u2
[√ v2 + w2 + u2 − u 1
2 √ v2 + w2 + u2 (4vw + 2u)
] ,
and by plugging in w = v the above equals
−`′(v2 + u) 2v2 + u2
[√ 2v2 + u2 − u 1
2 √ 2v2 + u2
( 4v2 + 2u )] = −`′(v2 + u)
2v2 + u2
[ 2v2 + u2 − u ( 2v2 + u ) √
2v2 + u2
] =
2`′(v2 + u)v2(u− 1) 2v2 + u2 · 1√ 2v2 + u2 .
Overall, we have
dγ̄(θ) dt = −2`′(v2 + u)v2u(u− 1) (2v2 + u2)2 + 2`′(v2 + u)v2(u− 1) 2v2 + u2 · 1√ 2v2 + u2
= −2`′(v2 + u)v2(u− 1)
2v2 + u2
[ u
2v2 + u2 − 1√ 2v2 + u2 ] = −2`′(v2 + u)v2(u− 1)
2v2 + u2
[ u− √ 2v2 + u2
2v2 + u2
] < 0 ,
where the inequality is since u > 1 and v > 0.
We now show that limt→∞ L(θ(t)) = 0. Assume that ‖θ‖ 6→ ∞. Let M > 0 be such that vw + u ≤ M for all t. Then, −`′(vw + u) ≥ C for some constant C > 0. Thus, dudt ≥ C for all t, which implies that u → ∞ in contradiction to our assumption. Hence, we must have ‖θ‖ → ∞. Since v = w ≥ u ≥ 1 for all t, then we have v → ∞ and w → ∞. Therefore limt→∞ L(θ(t)) = limt→∞ `(vw + u) = 0. It is easy to verify that γ̄(θ(0)) = 412 + 2√ 12 > 0.9. In order to obtain limt→∞ γ̄(θ(t)) = 12 we first show that limt→∞ uv = 0. Let M > 4 be some large constant. We show that there exists some t ′ such that v(t)u(t) ≥ M for all t ≥ t ′. Since v → ∞, then there is some t1 such that v(t1) = 2M , and ∆ > 0 such that v(t1 + ∆) = 2M +M3. Since u ≤ v then u(t1) ≤ 2M . For every t ≥ t1 we have dv(t) dt = −` ′(vw + u) · v ≥ −`′(vw + u) · 2M . Also, we have du(t)dt = −` ′(vw + u) ≤ 12M · dv(t) dt . Hence, we have
u(t1 + ∆) = u(t1) + ∫ t1+∆ t1 du(t) dt dt ≤ 2M + ∫ t1+∆ t1 1 2M dv(t) dt dt = 2M + 1 2M (v(t1 + ∆)− v(t1))
= 2M + 1
2M
( 2M +M3 − 2M ) = 2M + M2
2 ≤M2 .
Thus, v(t1 + ∆)
u(t1 + ∆) ≥ 2M +M
3
M2 ≥M .
Denote t′ = t1 + ∆. Note that for every t ≥ t′ we have
v(t) = v(t′) + ∫ t t′ dv dt dt = v(t′) + ∫ t t′ (−`′(vw + u))wdt = v(t′) + ∫ t t′ (−`′(vw + u))vdt
≥ v(t′) + ∫ t t′ (−`′(vw + u))M3dt = v(t′) +M3 ∫ t t′ du dt dt ≥M · u(t′) +M3 (u(t)− u(t′)) ≥M · u(t′) +M (u(t)− u(t′)) = Mu(t) .
We have
γ̄(θ(t)) = vw
v2 + w2 + u2 + u√ v2 + w2 + u2 = v2 2v2 + u2 + u√ 2v2 + u2 .
Since limt→∞ uv = 0 then limt→∞ u√ 2v2+u2 = 0 and limt→∞ v
2
2v2+u2 = 1 2 . Hence,
limt→∞ γ̄(θ(t)) = 1 2 as required. Finally, since limt→∞ u v = 0 and w(t) = v(t) > 0 for all t, then θ‖θ‖ converges to [ 1√ 2 , 1√ 2 , 0 ] . Thus, θ converges in direction.

Review summaries:
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.  As the positive results could be more preferable by the ML community, I summarize the positive results below:  * Global optimality for (deep) fully-connected linear nets; * Global optimality for general two-layer linear nets with no weight sharing, assuming all the weights are non-zero; * Local optimality for general two-layer ReLU nets with no weight sharing, assuming all neurons have non-zero inputs; * 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.) * 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.  Here "general" nets can have arbitrary connections between neurons in adjacent layers.

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

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