Year: 2021

Abstract:
We prove that finding all globally optimal two-layer ReLU neural networks can be performed by solving a convex optimization program with cone constraints. Our analysis is novel, characterizes all optimal solutions, and does not leverage duality-based analysis which was recently used to lift neural network training into convex spaces. Given the set of solutions of our convex optimization program, we show how to construct exactly the entire set of optimal neural networks. We provide a detailed characterization of this optimal set and its invariant transformations. As additional consequences of our convex perspective, (i) we establish that Clarke stationary points found by stochastic gradient descent correspond to the global optimum of a subsampled convex problem (ii) we provide a polynomial-time algorithm for checking if a neural network is a global minimum of the training loss (iii) we provide an explicit construction of a continuous path between any neural network and the global minimum of its sublevel set and (iv) characterize the minimal size of the hidden layer so that the neural network optimization landscape has no spurious valleys. Overall, we provide a rich framework for studying the landscape of neural network training loss through convexity.

heading: 1 INTRODUCTION
text: Let X ∈ Rn×d and y ∈ Rn be the data matrix and the label vector. Given a number of neurons m > 1 and a regularization parameter β > 0, we consider the regularized optimization problem
P∗m = min θ∈Θm
{ Lβ(θ) : = ` ( m∑ i=1 σ(Xui)αi ) + β 2 m∑ i=1 ( ‖ui‖22 + α2i )} . (1)
where Θm = Rd×m × Rm, θ = (U,α), ui is the i-th column of U ∈ Rd×m and αi is the i-th coefficient of α ∈ Rm. Here we focus on the ReLU activation, i.e., σ(z) = max{z, 0} and absorb the label y ∈ Rn in the loss function ` : Rn → R, which is assumed to be convex (e.g., logistic, hinge, squared loss). The model ∑m i=1 σ(Xui)αi in (1) can be easily extended to the one with bias term by adding a column of 1’s into the data X . We refer to an element θ ∈ Θm as a neural network and to each pair (ui, αi) as a neuron. We denote the set of optimal neural network as
Θ∗m = {θ ∈ Θm | Lβ(θ) = P∗m}. (2)
We denote the best training loss achievable by a neural as P∗ = infm>1 P∗m. The ReLU activation induces a natural partition of the parameter space. We denote D1, . . . , Dp as all possible values of diag(1(Xu > 0)). We introduce the corresponding convex cones Ci = {u ∈ Rd|(2Di − I)Xu > 0} for i ∈ [p] where we denote [p] = {1, . . . , p}. From this partition we have the local linearization
σ(Xu) = DiXu , for u ∈ Ci . (3)
We let Di+p = −Di for i ∈ [p] and Ci+p = Ci for i ∈ [p]. Such a partition of the parameter space has regained attention in the recent literature. In fact, Pilanci & Ergen (2020) recently showed that an optimal neural network θ∗ ∈ Θm for any m > 2p can be
constructed based on a solution of the convex optimization problem
P∗c : = min W∈W
{ Lcβ(W ) : = ` ( 2p∑ i=1 DiXwi ) + β · 2p∑ i=1 ‖wi‖2 } , (4)
where we introduced the convex feasible setW : = {W = (w1, . . . , w2p) | wi ∈ Ci}. In a nutshell, this equivalence can be intuitively explained as follows. From the constraint wi ∈ Ci, we obtain the local linearization σ(Xwi) = DiXwi for i ∈ [p] and σ(Xwi) = −DiXwi for i ∈ [p+ 1, 2p]. By choosing neurons (ui, αi) such that wi = |αi|ui, αi > 0 for i ∈ [p] and αi 6 0 for i > p + 1, we further obtain by positive homogeneity of the ReLU that
2p∑ i=1 DiXwi = 2p∑ i=1 σ(Xui)αi . (5)
From the fact that the cones C1, . . . , Cp cover the entire space, Pilanci & Ergen (2020) establish the equality P∗c = P∗, and show that an optimal neural network can be constructed from an optimal solution w∗1 , . . . , w ∗ p.
In this work, we explore in more depth the mapping from the optimal set of solutionsW∗ of the convex program (4) to the set of optimal neural networks Θ∗m. In fact, our main contribution is to show how to construct the set Θ∗m givenW∗ through simple mappings and transformations. Throughout our analysis, we unveil some novel necessary conditions for a neural network to be optimal and we illustrate the relevance of these conditions by relating them to usual necessary conditions for optimality (e.g., Clarke stationarity).

heading: 1.1 PRIOR AND RELATED WORK
text: Literature on the theory of deep learning is now extremely vast, and we mention here only a few classical results and recent works which focus on the properties of the neural network training loss, from an optimization perspective (e.g., the convergence of first-order methods, absence of spurious minima in the loss landscape, and, convex re-formulations of neural network training), and in the case of single-layer with ReLU-type activations.
Several recent works considered over-parameterized neural networks in the infinite-width limit. In particular, it is known that in this regime, gradient descent converges to an optimal solution, see (Jacot et al., 2018; Du et al., 2018; Allen-Zhu et al., 2018; Nguyen, 2021). Further analysis in (Chizat & Bach, 2018) showed that almost no hidden neurons move from their initial values to actively learn useful features, so that this regime resembles that of kernel training and the infinite-width limit infuses convexity. Wang & Lin (2021) showed that with an explicit regularizer based on the scaled variation norm, overparametrization is generally harmless to two-layer ReLU networks. However, experiments in (Arora et al., 2016) suggest that this kernel approximation is unable to fully explain the success of non-convex neural network models.
Convexity arguments in neural networks were proposed in the recent literature (Bengio et al., 2006; Bach, 2017). However, existing works, except (Pilanci & Ergen, 2020), are restricted to infinitely wide networks. In turn, Bengio et al. (2006) and Bach (2017) consider greedy neuron-wise optimization strategies for the infinite-dimensional optimization problem, which requires solving non-convex problems at every step to train a shallow neural network. In contrast, in our work, we reveal the hidden convex optimization landscape for any finite number of hidden neurons.
Besides the convexity properties of infinitely wide networks, many works derived lower bounds on the hidden layer size to guarantee the absence of spurious minima. Venturi et al. (2019) showed that the un-regularized (i.e. β = 0) objective Lβ has no spurious local minima provided that the number of neurons satisfies m > n, and a similar result was shown in (Livni et al., 2014). Similar results were derived for deep networks. For instance, Soudry & Carmon (2016) showed that under a dropout-like noise assumption, there exist no differentiable spurious minima if the product of the dimensions of the layer weights exceeds n and this result matches the classical lower bound (Baum, 1988) on the minimal width of a neural network to implement any dichotomy for inputs in general position. In a similar vein, Nguyen & Hein (2017) showed that no spurious minima occur provided that one of the layer’s inner width exceeds n and under additional non-degeneracy conditions. For activations other than the ReLU (e.g., linear, quadratic, polynomial), similar lower bounds were derived in (Venturi
et al., 2019; Du & Lee, 2018; Soltanolkotabi et al., 2018). These analyses are typically based on the idea that when m & n then it is very likely that the features σ(Xu1), . . . , σ(Xum) form a basis of Rn so that the training problem reduces to finding a linear model with weights α1, . . . , αm which perfectly fits the labels. For the hinge loss and linear separable data, (Wang et al., 2019) show that the modified stochastic gradient descent method can achieve global optimality despite the presence of spurious local minima and saddle points.
The training landscape of neural networks is of great interest for theoretical analysis in the optimization of neural networks. An important perspective is to analyze the landscape via paths through the parameter space, see (Vidal et al., 2017). Indeed, in (Haeffele & Vidal, 2015; 2017; Sharifnassab et al., 2019), it is shown that there exists a non-increasing path in objective value from every point to the global minimum with mild assumption on the layer width. The existence of such paths also indicates that the level sets of the training loss are connected (Freeman & Bruna, 2016; Venturi et al., 2019; Nguyen, 2019; Nguyen et al., 2021) and there is no bad local valley (Nguyen & Hein, 2017).
However, with regularization, the training problem is more challenging. Intuitively, it reduces the set of optimal solutions to those with small norms. Without regularization (i.e., β = 0), it should be noted that the set of optimal solutions always contains infinitely many points. For instance, with ReLU activations, it holds that if θ∗ = {(u∗i , α∗i )}mi=1 is an optimal neural network, then any re-scaling of θ∗ in the form {(u ∗ i
γi , γi α ∗ i )}mi=1 (with γ1, . . . , γm > 0) has the same objective value and is thus
optimal. With regularization, this manifold is reduced to a single point. It is then natural to expect that this minimal size of the hidden layer must increase. Further, the aforementioned analyses do not extend since regularization also penalizes the norms of the ui’s, and one cannot simply generate such a basis of Rn based on the features σ(Xu1), . . . , σ(Xum) by random sampling and then overfitting the labels.
Recently, Pilanci & Ergen (2020); Ergen & Pilanci (2020) show that two-layer ReLU neural networks can be optimized exactly via finite-dimensional convex programs with complexity polynomial in the number of samples and hidden neurons. As indicated in Pilanci & Ergen (2020), the worst-case complexity is exponential in the dimension of the training samples unless P = NP .

heading: 1.2 SUMMARY OF OUR CONTRIBUTIONS
text: In Section 2, we introduce the notions of minimal neural networks and nearly minimal neural networks. These two notions are closely related to the plateau and the edge of the plateau of the loss landscape.
In Section 3, we show that any minimal neural network θ can be represented, via an explicit map, in the convex feasible spaceW as a point W (θ) such that Lβ(θ) > Lcβ(W (θ)), and vice-versa. This structural result provides a mathematically rich perspective to characterize optimal neural networks through the lens of convexity. We then provide an exact characterization of the set of all global optima of the nonconvex problem, which include all nearly minimal neural networks generated via the optimal solutions of the convex program.
In Section 4, we show that any Clarke stationary point θ with respect to Lβ is a nearly minimal neural network. This provides a preliminary structure on the solutions found by stochastic gradient descent (SGD), as it has been recently shown (see, for instance, Corollary 5.11 in Davis et al. (2020)) that the limit points of SGD applied to neural network optimization are Clarke stationary. More importantly, we show that Clarke stationary point θ with respect to Lβ also corresponds to a global minimum of a subsampled convex problem. We also provide a polynomial-time algorithm (in the sample size n and the hidden-layer size m) in order to test whether a neural network is globally optimal.
In Section 5, we show that any neural network is path-connected to a succinct representation (with at most n + 1 non-zero neurons) and this path is with constant objective value. Then, from the convex perspective of two-layer ReLU neural networks, we provide an explicit path of non-increasing loss between θ and θ′, where θ′ is the global optimum of the non-convex training problem. This establishes that the training loss Lβ has no spurious local minima, provided that the number of neurons is sufficiently large.

heading: 1.3 NOTATIONS
text: We first present an alternative interpretation of the cones Ci and the diagonal matrices Di for i ∈ [p]. The ReLU activation function partitions the space of neurons u ∈ Rd into linearly separated regions, that is, given a binary vector s ∈ {0, 1}n, the set of neurons u ∈ Rd such that 1(Xu > 0) = s is a convex cone in Rd, if not empty. We enumerate the closures of all these cones as C1, . . . , Cp and we set Ci+p = Ci for i ∈ [p]. For i ∈ [p], we introduce the corresponding diagonal matrices Di = diag(1(Xu > 0)) for an arbitrary u ∈ Ci, and Di+p = −Di. Here the number p is the number of dichotomies that the data matrix X can realize. It is upper bounded by p 6 2r ( e(n−1)
r
)r where
r = rank(X), see (Cover, 1965).
Beyond the dichotomies of the space of neurons u ∈ Rd, we further introduce the partitions (trichotomies) {I+, I0, I−} of [n] such that there exists a solution vector u ∈ Rd verifying (Xu)k > 0 if k ∈ I+, (Xu)k = 0 if k ∈ I0 and (Xu)k < 0 if k ∈ I−. Clearly, there exists a finite number q of such trichotomies and q is trivially upper bounded by 3n. For the j-th trichotomy {I+, I0, I−}, we define the n× n diagonal matrix Tj with k-th diagonal element (Tj)kk = 1 if k ∈ I+, (Tj)kk = 0 if k ∈ I0 and (Tj)kk = 0 if k ∈ I−. Such trichotomies are also discussed in Phuong & Lampert (2020). For each j = 1, . . . , q, we define Qj as the closed convex cone of solution vectors for the j-th trichotomy {I+, I0, I−}. We consider a partition {B1, . . . , B2q} of the neurons’ parameter space whereBi : = Qi×R>0 for j = 1, . . . , q andBj : = Qj−q×R<0 for j = q+1, . . . , 2q. We augment the set of diagonal matrices {Tj}qj=1 by setting Tj = −Tj−q for j = q + 1, . . . , 2q.
For a neuron pair (u, α) ∈ Rd × R, we denote B(u, α) as the unique Bi such that (u, α) ∈ Bi. The notion of path-connected sublevel set is introduced as follows. Definition 1. We write θ I θ′ if the neural network θ′ ∈ Θm belongs to the path-connected sublevel set (or valley) of θ ∈ Θm. Namely, there exists a continuous path γ : [0, 1] → Θm such that γ(0) = θ, γ(1) = θ′ and t 7→ Lβ(γ(t)) is non-increasing. We denote the valley of θ as Ω(θ) : = {θ′ ∈ Θm | θ I θ′}. We say that θ ∈ Θm is non-spurious if θ I θ∗ for some θ∗ ∈ argminθ′∈Θm Lβ(θ ′). Otherwise, we say that θ and its valley Ω(θ) are spurious.

heading: 2 MINIMAL NEURAL NETWORKS AND NEARLY MINIMAL NEURAL NETWORKS
text: We start with the notion of minimal neural networks and nearly minimal neural networks. Minimal neural networks enjoy a well-structured representation which is useful to understand the optimality properties of two-layer neural networks. Definition 2 (Minimal neural networks). We say that a neural network θ is minimal if (i) it is scaled, i.e., ‖ui‖2 = |αi| for i ∈ [m] and (ii) the cones B(u, α) of each of its non-zero neurons (u, α) are pairwise distinct. That is, a minimal neural network has at most a single non-zero neuron per cone Bi. We denote by Θminm the set of minimal neural networks with m neurons.
Note that any minimal neural network has at most 2q non-zero neurons since there are 2q cones Bi and at most one neuron per cone. Next, we introduce a slightly less structured class of neural networks that one can interpret as ’split’ versions of minimal neural networks, and can have an arbitrary number of non-zero neurons. Definition 3 (Nearly minimal neural networks). We say that a neural network θ is nearly minimal if (i) it is scaled and (ii) for any two non-zero neurons (u, α), (v, β) of θ, if B(u, α) = B(v, β) then u and v are positively colinear, i.e., there exists λ > 0 such that u = λv. We denote by Θ̃minm the set of nearly minimal neural networks with m neurons. It trivially holds that Θminm ⊂ Θ̃minm .
For a nearly minimal neural network, by merging the neurons corresponding to the same trichotomies, we can reformulate it into a minimal neural network without changing the objective value.

heading: 2.1 FROM NEARLY MINIMAL TO MINIMAL NEURAL NETWORKS
text: Nearly minimal neural networks have the property that any two neurons which share at least one active cone must be positively colinear. As we establish next, these colinear neurons can be continuously merged together along a path of constant objective value, resulting in a minimal neural network.
Formally, we let θ ∈ Θ̃minm be a nearly minimal neural network with m neurons and we fix (w, γ) ∈ θ a non-zero neuron. Let (w2, γ2), . . . , (wk, γk) ∈ θ be the other non-zero neurons such that for each j = 2, . . . , k, we have sign(γ) = sign(γj), and, w and wj are positively colinear. Write
(w1, γ1) : = (w, γ), and define the merged neuron (wm, γm) as wm : = ∑k j=1 |γj |wj√
‖ ∑k j=1 |γj |wj‖2 and
γm : = sign(γ) ‖wm‖2. Let M(θ) be a copy of θ where each such set of k positively colinear neurons {(w1, γ1), . . . , (wk, γk)} is replaced by the k neurons {(wm, γm), (0, 0), . . . , (0, 0)}. We refer toM(θ) as the merged version of θ. The next result states relevant properties ofM(θ). Proposition 1. Let θ ∈ Θ̃minm . Then, the following results hold.
1. The merged neural networkM(θ) is a minimal neural network. 2. We have θ IM(θ), and the continuous path from θ toM(θ) has constant objective value. 3. IfM(θ) is a local minimum of Lβ , then θ is also a local minimum of Lβ .
Intuitively, merging the colinear neurons preserves the active cones and leaves a single neuron per cone, so that M(θ) is indeed minimal. The third property essentially follows from the fact that M(θ) has more degrees of freedom than θ since it has more neurons equal to 0. In addition, the continuous path of constant objective value from θ toM(θ) can be explicitly constructed (see the proof in Appendix B.1).

heading: 3 MAPPING MINIMAL NEURAL NETWORKS TO A CONVEX OPTIMIZATION LANDSCAPE
text: We provide here an explicit map from the set of minimal neural networks to the feasible setW of the convex program (4), and vice-versa. For W = (w1, . . . , w2p) ∈ W , we let ‖W‖0 be number of the non-zero vectors in w1, . . . , w2p. Define
Wm = {W ∈ W | ‖W‖0 6 m} , W∗m =Wm ∩W∗ . (6)
First, we introduce the map θ 7→W (θ) from Θminm toWm where for each i = 1, . . . , 2p, we set wi(θ) : = ∑
j=1,...,m B(uj ,αj)⊆Bi
|αj |uj , (7)
and such that each non-zero neuron (uj , αj) contributes only to a single wi. To understand the latter, note that each cone B(uj , αj) might be a subset of several (adjacent) cones Bi and hence, one might need to choose which wi a neuron (uj , αj) contributes to. These ties can be resolved arbitrarily without affecting any of our results.
Conversely, we construct a map W 7→ θ(W ) fromWm to Θminm by setting θ(W ) = {(ui, αi)}mi=1 where the (ui, αi) are defined as follows. Denote i1 < · · · < im the indices such that if i 6∈ {i1, . . . , im} then wi = 0. Take the index J (if any) such that iJ 6 p and iJ+1 > p + 1. Let {K1, . . . ,K`} be a partition of {i1, . . . , iJ} in terms of the repartition of wi1 , . . . , wiJ into the cones {Q1, . . . Qq}. Similarly, let {K`+1, . . . ,K`+`′} be a partition of {iJ+1, . . . , im} in terms of the repartition of wiJ+1 , . . . , wim into the cones {Q1, . . . Qq}. Then, for 16j6`+ `′, we set
(uj , αj) : =  ∑i∈Kj wi√ ‖ ∑ i∈Kj wi‖2 , γj · √ ‖ ∑ i∈Kj wi‖2  , (8) where γj = 1 if j 6 ` and γj = −1 if j > `. Finally, for `+ `′+ 16j6m, we set (uj , αj) = (0, 0). As stated in the next result, these mappings can only improve the training loss.
Proposition 2. It holds that for anyW ∈ Wm we haveLβ(θ(W )) 6 Lcβ(W ), and, for any θ̃ ∈ Θminm , we have Lcβ(W (θ̃)) 6 Lβ(θ̃). Furthermore, it holds that θ(W (θ̃)) ∈ Ω(θ̃).
These mappings between minimal neural networks and the convex feasible set provide a rich structure to address the optimality properties of neural networks. In Figure 1, we provide an illustration of the non-convex and convex landscapes on a toy neural network training model.

heading: 3.1 THE GLOBAL OPTIMAL SET OF NEURAL NETWORKS
text: Let m∗ = minW∈W∗ ‖W‖0. As a consequence of Caratheodory’s theorem, we have the following upper bound on the minimal cardinality m∗ of an optimal solution. Lemma 1. It holds that m∗ 6 n+ 1. Further, for any m > m∗, we have that P∗m = infk>1 P∗k .
From the definition of m∗, it clearly holds thatW∗m 6= ∅ for m > m∗. Then, we present the mapping from the optimal solution to the convex problem (4) to a globally optimal neural network for the non-convex problem (1). Lemma 2. Let W = (w1, . . . , w2p) ∈ W∗, and denote by I = {i1, . . . , i‖W‖0} ⊂ [2p] the set of indices such that w∗i 6= 0 for i ∈ I. We set
(uj , αj) = ( wij√ ‖wij‖2 , γij √ ‖wij‖2 ) , (9)
for ij ∈ I. Here γi = 1 if i 6 p and γi = −1 if i > p. Then, it holds that θ = {(ui, αi)}‖W‖0i=1 is an optimal neural network, i.e., Lβ(θ) = P∗.
We denote the above mapping (9) by ψ, and we set Θcvxm = ψ(W∗m). According to Lemma 2, it holds that Θcvxm ⊆ Θ∗m. Given a neuron (u, α), we say that a collection of neurons {(uj , αj)}kj=1 is a splitting of (u, α) if (uj , αj) = ( √ γju, √ γjα) for some γj > 0 and ∑k j=1 γj = 1. Given a neural network θ = {(ui, αi)}mi , a splitting of θ is any neural network θ′ ∈ Θm such that the non-zero neurons of θ′ can be partitioned into splittings of the neurons of θ. Similarly, split neurons can be merged back to their original form. We denote by Θ̃cvxm the set of splittings generated from Θ cvx m . We provide an exact characterization of the optimal set in the following theorem.
Theorem 1. Suppose that m > m∗. It holds that Θ∗m = Θ̃cvxm . Namely, all optimal solutions of the nonconvex loss can be found via the optimal solutions of the convex program (4) up to permutation and splitting/merging of the neurons as defined above.
We compare our result with the result in (Pilanci & Ergen, 2020) as follows. Essentially, Pilanci & Ergen (2020) show how to construct one globally optimal solution of the nonconvex loss by solving the convex program, while Theorem 1 shows how to construct the entire set of global optimum of the nonconvex loss. The relations amongW∗m,Θcvxm , Θ̃cvxm and Θ∗m is illustrated in Figure 2.
Example 1. We consider a toy example, where X = [ 1 0 0 1 1 1 ] , Y = [ 1 0 0 ] and β = 0.1. In this case, p = 6 and we can enumerate the diagonal matrices Di as
D1 = diag([0, 0, 0]), D2 = diag([0, 1, 0]), D3 = diag([0, 1, 1]), D4 = diag([1, 0, 0]), D5 = diag([1, 0, 1]), D6 = diag([1, 1, 1]). (10)
The optimal solution to the convex problem (4) is given by W ∗ = (w∗1 , . . . , w ∗ 2p), where W ∗ only consists of one non-zero block w∗5 = [0.86,−0.79]T . Therefore, the set of the global minimizers of the nonconvex loss Lβ consists of all nearly minimal neural network θ = {(ui, αi)}mi=1 satisfying
ui = √ γi w∗5√ ‖w∗5‖2 , αi = √ γi
√ ‖w∗5‖2, i ∈ [m] , (11)
where ∑m i=1 γi = 1 and γi > 0 are arbitrary. These correspond to the split versions of the single neuron w∗5 . We investigate numerically our result: for m = 5, we run gradient descent (GD) on the nonconvex loss Lβ until we find a nearly stationary neural network {(ui, αi)}5i=1. We plot the points αiui as well as w∗5 in Figure 3 in the Appendix.

heading: 4 CHARACTERIZATION OF ALL LOCAL MINIMA
text: Minimal neural networks form a subset considerably smaller than the entire space of neural networks, and they do contain all the global optima. In this section, we show that first-order methods can find networks that can be merged to a minimal representation. Moreover, we exhibit the existence of a path of strictly decreasing objective value from any neural network to a minimal representation. This may suggest that minimal neural networks are the right notion to study the complexity of the loss landscape.

heading: 4.1 SGD FINDS A NEARLY MINIMAL NEURAL NETWORK
text: The limit points of SGD are almost surely Clarke stationary with respect to Lβ (see, e.g., (Davis et al., 2020; Bolte & Pauwels, 2019)). We show next that any Clarke stationary point w.r.t. the loss L(θ) is in fact a nearly minimal neural network. This shows that SGD finds a neural network which can be merged to a minimal representation. Theorem 2. Fix m > 1. Any Clarke stationary point θ of the non-convex loss function Lβ over Θm is a nearly minimal neural network. Consequently, any local minimum of Lβ is nearly minimal.
As an additional motivation for studying nearly minimal neural networks, we establish the following. Proposition 3. Let θ ∈ Θm be any neural network. There exists a continuous path in Θm from θ to a nearly minimal neural network along which the loss function is (strictly) decreasing.
The proof of Theorem 2 is deferred to Appendix B.4 and that of Proposition 3 to Appendix B.5. Both proofs are based on the same transformations of a neural network θ which decreases the training loss: scaling the neural network and then aligning the non-zero neurons which belong to the same cones Bi so that they become positively colinear. These transformations leave the predictions unchanged due to the piecewise linear structure of the activation function but decrease the value of the regularization term. Thus, our notions of minimal representations are intimately related to (i) the piecewise linear structure of the activation function and (ii) the regularization effect. We emphasize again that these two features of neural network training are commonly used in practice (e.g., ReLU and weight decay).
Combining Proposition 3 and Proposition 1, we immediately obtain the following result.
Corollary 1. The valley Ω(θ) of any neural network θ contains a minimal one. Further, if the valley Ω(θ) is non-spurious, then it contains an optimal neural network which is minimal.
Interestingly, we are able to provide an explicit construction of the map from a neural network θ to a nearly minimal representation, and this map is based on the aforementioned transformations (scaling and aligning; see the proof of Proposition 3 for details).
Hence, the study of the optimality properties of a neural network can be narrowed down to the structured class Θ̃minm which contains the limit points of SGD. Next, we establish that we can go further by considering the class of minimal neural networks Θminm .

heading: 4.2 CLARKE’S STATIONARY POINT AND SUBSAMPLED CONVEX PROGRAM
text: Consider the convex program with trichotomies:
min ` ( q∑ j=1 TjX(wj − wj+q) ) + β 2q∑ j=1 ‖wj‖2,
s.t. wj , wj+q ∈ Qj , j ∈ [q].
(12)
The convex program with trichotomies also provides a convex optimization formulation of the regularized neural network training problem (1). Proposition 4. The convex program (12) with trichotomies has the optimal value P∗.
Given a subset I ⊆ [q], we can also consider a subsampled convex program with trichotomies: min ` (∑ j∈I TjX(wj − wj+q) ) + β ∑ j∈I (‖wj‖2 + ‖wj+q‖2),
s.t. wj , wj+q ∈ Qj , j ∈ I. (13)
We show the connection of the Clarke’s stationary point of the nonconvex loss function Lβ and the optimal solution of the subsampled convex program (13) as follows. Theorem 3. Suppose that θ is a Clarke’s stationary point of the nonconvex loss function Lβ . Let I = {i ∈ [q] | there exists k ∈ [m] such that Tj = diag(sign(Xuk))}. Then, θ corresponds to a global optimum of the subsampled convex program (13).
In other words, any local minimum of the nonconvex loss (1) can be characterized as a global minimum of a subsampled convex program (13); further, the optimality gap is equal to the gap between the subsampled problem (13) and the full convex program (12).

heading: 4.3 SUBSAMPLED CONVEX PROGRAM AND VERIFYING GLOBAL OPTIMALITY
text: We established that a stationary point of the non-convex training loss is a global optimum of a subsampled convex program. Here, we build on this observation to design a procedure to check whether a neural network is in fact a global minimizer. Our key theoretical contribution is to provide such an algorithm that runs in polynomial time of sample size n.
We first note that the set {Di}pi=1 can be constructed in polynomial time of n via standard results from geometry and hyperplane arrangements in (Cover, 1965; Winder, 1966; Ojha, 2000). Consider a feasible point W = (w1, . . . , w2p) ∈ W of the convex program (4). Note that each constraint wi ∈ Ci is a linear inequality constraint. Indeed, as described in Section 2, each Ci is the convex cone of solution vectors for a dichotomy {I+, I−} of {1, . . . , n}. Writing X(i)+ (resp. X (i) − ) the subset of rows of X indexed by I+ (resp. I−), we have u ∈ Ci if and only X(i)+ u 0 and X (i) − u 0. Using these notations, the convex program (4) can be reformulated as
min w1,...,w2p
` ( ŷc(W ) ) + β 2p∑ i=1 ‖wi‖2
s.t. X(i)+ wi 0, X (i) − wi 0 ∀i = 1, . . . , 2p ,
where ŷc(W ) = ∑2p i=1DiXwi. Hence, given a feasible point W
∗ = (w1, . . . , w2p) ∈ W to the convex program (4), it holds that W ∗ is a global minimizer if and only if W ∗ satisfies the KarushKuhn-Tucker (KKT) conditions (see (Boyd et al., 2004)) of (4). Here, W ∗ ∈ W satisfies the KKT conditions if, for each i = 1, . . . , 2p, there exist ζ(i)+ , ζ (i) − 0 such that 〈ζ (i) + , X (i) + w ∗ i 〉 = 〈ζ(i)− , X (i) − w ∗ i 〉 = 0 and
X>Di∇`(ŷc(W ∗)) + β w∗i ‖w∗i ‖2 +X (i) − > ζ (i) − −X (i) + > ζ (i) + = 0 , if w
∗ i 6= 0 (14)∥∥∥X>Di∇`(ŷc(W ∗)) +X(i)− >ζ(i)− −X(i)+ >ζ(i)+ ∥∥∥
2 6 β , otherwise . (15)
This amounts to solving a system with 2np variables of 2np linear inequalities, n0 convex quadratic inequalities and (2p−n0)(d+ 2) linear equalities, where n0 is the number of variables w∗i equal to 0, and this can be done efficiently using standard convex solvers, in time polynomial in the sample size n. The next result establishes the link between checking the KKT conditions of the above program and checking whether a neural network is a global optimum. Its proof is deferred to Appendix B.8.
Proposition 5. Let θ̃ ∈ Θminm be a minimal neural network. Suppose that W (θ̃) satisfies the KKT conditions as described above. Then, θ(W (θ̃)) is a global optimum of the loss Lβ .
In the above result, the minimal neural network assumption is not restrictive, since any local minima of the loss must be a nearly minimal neural network (Theorem 2), and then, any nearly minimal neural network can be reduced to a minimal one along a continuous path of constant value (Theorem 1).

heading: 5 NON-SPURIOUS VALLEYS AND CONVEX LANDSCAPE
text: The subsampled convex program relates to the optima of SGD. It is then of interest to understand the landscape when m is much smaller than the number of cones. Here we show that a critical threshold is n+ 1 +m∗ for having a path of non-increasing value. While this may be an open problem, it is reasonable to expect SGD to behave better in that case, and thus to find a global minimum. For an arbitrary neural network θ, we can find a point θ′ with at most n+ 1 non-zero neurons such that they are connected with a path with constant objective values.
Proposition 6. Given a scaled neural network θ ∈ Θm with m > n + 1, there exists a neural network θ′ with at most n+ 1 non-zero neurons and there exists a path with constant objective value between θ and θ′. Namely, θ I θ′ and θ′ I θ.
A direct corollary of Proposition 6 is that for any global optimum θ∗ of Lβ , we can find a succinct representation θ̃∗ with at most n + 1 non-zero neurons and there exists a path between θ̃∗ and θ∗ such that the objective value is constant. Based on Proposition 6, we can also show that there is no spurious valley. The following result states the absence of spurious valleys for the training loss as soon as m & n.
Proposition 7. Let m > n+ 1 +m∗. Then, it holds that for any neural network θ ∈ Θm, we have θ I θ∗ for some θ∗ ∈ Θ∗m.
In other words, provided that m > n+ 1 +m∗, all strict local minima are global. Compared to the standard lower bound m > n for the unregularized case in (Venturi et al., 2019; Livni et al., 2014), we have an additional term m∗ 6 n+ 1 induced by weight decay.
As known in the literature (Freeman & Bruna, 2016; Venturi et al., 2019; Vidal et al., 2017), the loss landscape of an over-parameterized shallow neural network is almost convex. Essentially, for a sufficiently wide neural network, for any θ0, θ1 and λ ∈ [0, 1], we can find θλ such that f(x; θλ) = λf(x; θ0) + (1 − λ)f(x; θ1). From a perspective of convex formulation of two layer neural network, we give a sufficient upper bound on the width of neural network to ensure the convex landscape in terms of realizations. Essentially, as long as m > 2(n+ 1), for any two neural network realizations f(x; θ0) and f(x; θ0), we can find succinct representations θ̃1, θ̃2 such that θi I θ̃i and θ̃i I θi for i = 1, 2. Then, for any λ ∈ [0, 1], we can construct θλ such that
f(x; θλ) = λf(x; θ̃0) + (1− λ)f(x; θ̃1) (16)
The construction of θλ is straightforward. From Proposition 6, we can take θ̃i as a neural network with at most n + 1 non-zero neurons for i = 1, 2. Given m > 2(n + 1), following the proof of Proposition 7, we can construct θλ satisfying (16).

heading: 6 CONCLUSION
text: We present a methodology to find all global solutions to the training problem of two-layer ReLU networks via solving a convex optimization problem. We provide an exact characterization of globally optimal solutions, and local minimizers in terms of convex problems. We provide a procedure to generate the entire global optimum. A polynomial-time algorithm is presented to examine whether a neural network is globally optimal to the nonconvex training loss. A current limitation is that the results apply to two-layer networks. However, we conjecture that our results can be extended to arbitrary depth with appropriate convex formulations.

heading: A FIGURE IN EXAMPLE 1
text: We plot the points αiui as well as w∗5 in Figure 3.

heading: B PROOFS OF MAIN RESULTS
text: Thoughout the appendix, we will use the following notations. For W = (w1, . . . , w2p), we define ŷc(W ) = ∑2p i=1DiXwi. For θ = (U,α), where U ∈ Rd×m and α ∈ Rm, we define ŷ(θ) =∑m
j=1 σ(Xuj)αj .

heading: B.1 PROOF OF PROPOSITION 1
text: According to the construction ofM(θ), there is at most one non-zero neuron per cone, and, each neuron (w, γ) satisfies ‖w‖ = |γ|, i.e.,M(θ) is minimal. Fix a cone B. Let (w1, γ1), . . . , (wk, γk) be the neurons of θ such that B(ui, wi) = B for i =
1, . . . , k, and let wm = ∑k j=1 |γj |wj√∑k j=1 |γj |wj and γm = sign(γ1) · √ ‖wm‖2 be the merged neuron. Since θ is nearly minimal, we know that w1, . . . , wk are positively colinear.
For t ∈ [0, 1], define θ(t) such that it has k neurons associated with the cone B given by
w1(t) : = (1− t)w1|γ1|+ twm|γm|√ ‖(1− t)w1|γ1|+ twm|γm|‖2
γ1(t) : = sign(γ1) · ‖w1(t)‖2 wj(t) : = √ 1− t · wj γj(t) : = √ 1− t · γj ,
where j > 2. Note that for all j > 1, all vectors wj(t), wj , wm are positively colinear, that ‖wj(t)‖2 = |γj(t)| and that sign(γj(t)) = sign(γ1). Further, note that (w1(0), γ1(0)) = (w1, γ1), (w1(1), γ1(1)) = (w
m, γm) and for j > 2, (wj(0), γj(0)) = (wj , γj), (wj(1), γj(1)) = (0, 0). Consider the neural networks θ(t) with neurons (wj(t), γj(t)) respectively defined for each cone B. It holds that θ(0) = θ and θ(1) = M(θ). Then, the contribution of the neurons in B to the predictions ŷ(θ(t)) are given by
k∑ j=1 σ(Xwj(t))γj(t) = sign(γ) · σ X(w1(t)|γ1(t)|+ k∑ j=2 wj(t)|γj(t)|)  = sign(γ) · σ
(1− t)Xw1|γ1|+ tXwm|γm|+ (1− t)X k∑ j=2 wj |γj |  = sign(γ) · σ(Xwm|γm|) .
Thus, the predictions ŷ(θ(t)) are constant as a function of t. Similarly, we claim that the regularization term R(θ(t)) is constant as a function of t. Since the neurons are scaled, the contribution of the cone B to the regularization term is given by (up to the constant β)
k∑ j=1 ‖wj(t)‖2|γj(t)| = ‖w1(t)‖2|γ1(t)|+ k∑ j=2 ‖wj(t)‖2|γj(t)|
= ‖(1− t)w1|γ1|+ t wm|γm|‖2 + (1− t) k∑ j=2 ‖wj‖2|γj | = ‖(1− t) k∑ j=1 wj |γj |+ t wm|γm|‖2
= ‖wm‖2|γm| , where the third equality follows from the triangular equality when all vectors are positively colinear. Thus, we have explicited a continuous path from θ toM(θ) such that Lβ is constant along that path. Now, we show that ifM(θ) is a local minimum then θ is also a local minimum. We proceed with the converse. Assume that θ is not a local minimum of Lβ . For a cone B, let (w1, γ1), . . . , (wk, γk) be the neurons of θ such that B(wi, γi) = B. Let (wm, γm) be the merged neuron. If θ is not a local minimum, then there exists a small perturbation θε : = {(uεi , αεi )}mi=1 of the neurons of θ such that (i) Lβ(θε) < Lβ(θ), (ii) sign(γεi ) = sign(γi) and (iii) for each i = 1, . . . ,m, we have I+(σ(Xui)) ⊆ I+(σ(Xuεi )) and I−(σ(Xui)) ⊆ I−(σ(Xuεi )), where we use the notation I+(z) : = {i ∈ {1, . . . , n} | zi > 0} and I−(z) : = {i ∈ {1, . . . , n} | zi < 0} for a vector z ∈ Rn. Then, we define for t ∈ [0, 1],
w1(t) = (1− t)wε1|γε1 |+ twm|γm|√ ‖(1− t)wε1|γε1 |+ twm|γm|‖2 , γ1(t) = sign(γ1) · ‖w1(t)‖2, wj(t) = √ 1− t · wεj , γj(t) = √ 1− t · γεj ,
where j > 2. Let θ(t) the neural network with neurons (wj(t), γj(t)) defined as above for each cone B. Then, the contribution of a cone B to the predictions ŷ(θ(t)) is given by k∑ j=1 σ(Xwj(t))γj(t) = sign(γ1) σ(X((1− t)wε1|γε1 |+ twm|γm|)) + (1− t) k∑ j=2 σ(Xwεj |γεj |)  Due to the above property (iii), we have that
σ(X((1− t)wε1|γε1 |+ twm|γm|)) = (1− t)σ(Xwε1|γε1 |) + t σ(Xwm|γm|) . Thus, the contribution of the cone B to the predictions is
k∑ j=1 σ(Xwj(t))γj(t) = (1− t) k∑ j=1 σ(Xwεj )γ ε j + t σ(Xw m)γm .
Summing over all the cones, we find that
ŷ(θ(t)) = (1− t)ŷ(θε) + t ŷ(M(θ)) . Similarly, the contribution of the cone B to the regularization term R(θ(t)) is
k∑ j=1 ‖wj(t)‖2|γj(t)| = ‖(1− t)wε1|γε1 |+ twm|γm|‖2 + (1− t) k∑ j=2 ‖wεj‖2|γεj |
6 (1− t) k∑ j=1 ‖wεj‖2|γεj |+ t ‖wm‖2|γm| ,
where the last inequality is due to the triangular inequality. Thus, we obtain that
R(θ(t)) 6 (1− t)R(θε) + tR(M(θ)) . Hence, we get that Lβ(θ(t)) 6 (1− t)Lβ(θε)+ tLβ(M(θ)). Since Lβ(θε) < Lβ(θ) = Lβ(M(θ)), we have that Lβ(θ(t)) < Lβ(M(θ)) for any t < 1. This concludes the proof.

heading: B.2 PROOF OF PROPOSITION 2
text: Let θ ∈ Θm, and consider the point W (θ), as defined in (7), whose expression is given by wi(θ) : = ∑
j=1,...,m B(uj ,αj)⊆Ci
|αj |uj , (17)
and such that each non-zero neuron (uj , αj) contributes only to a single wi(θ).
We prove that the mapping θ 7→W (θ) is well-defined. Each set Pi is a cone and wi(θ) is a positive linear combination of elements of Pi. It follows that wi(θ) ∈ Pi, and W (θ) ∈ W . Further, θ has m neurons and each neuron (uj , αj) contributes only to a single wi(θ). It follows that at most m variables among {w1(θ), . . . , w2p(θ)} are non-zero, and W (θ) ∈ Wm. Hence, the mapping θ 7→W (θ) is well-defined from Θm toWm. We show that Lcβ(W (θ)) 6 Lβ(θ). We note that
ŷc(W (θ)) = 2p∑ i=1 DiXwi(θ) = 2p∑ i=1 ∑ j=1,...,m
B(uj ,αj)⊆Ci
DiX|αj |uj .
Note that for a neuron (uj , αj) such that B(uj , αj) ⊆ Ci, we have that DiX|αj |uj = σ(Xuj)αj . It implies that
ŷc(W (θ)) = 2p∑ i=1 ∑ j=1,...,m
B(uj ,αj)⊆Ci
DiX|αj |uj = m∑ j=1 σ(Xuj)αj = ŷ(θ) ,
and consequently, `(ŷc(W (θ))) = `(ŷ(θ)). On the other hand, we have 2p∑ i=1 ‖wi‖2 = 2p∑ i=1 ∥∥∥ ∑ j=1,...,m
B(uj ,αj)⊆Ci
|αj |uj ∥∥∥
2 6 m∑ j=1 |αj |‖uj‖2 ,
where the last inequality follows from triangular inequality. Since the neurons (uj , αj) are scaled, we get that ∑m j=1 |αj |‖uj‖2 = 1 2 ∑m j=1 |αj |2 + ‖uj‖22, and we finally obtain that Lcβ(W (θ)) 6 Lβ(θ).
We show that the mapping W 7→ θ(W ) is well-defined. Based on the construction (8), it holds that the non-zero neurons (uj , αj) belong to pairwise distinct cones in {B1, . . . , B2q}. Further, the neurons are scaled. Hence, θ(W ) is a minimal neural network with m neurons.
We prove that Lβ(θ(W )) 6 Lcβ(W ). Denote by D(j) the diagonal matrix associated with B(uj , αj) for 1 6 j 6 l + l′. We have that
ŷ(θ(W )) = m∑ j=1 σ(Xuj)αj = l+l′∑ j=1 D(j)Xuj |αj | = l+l′∑ j=1 D(j)X ∑ i∈Kj vi .
It holds by construction that for each i ∈ Kj , D(j)Xwi = DiXwi. Therefore, we find that ŷ(θ(W )) = ŷc(W ) and `(ŷ(θ(W ))) = `(ŷc(W )). On the other hand, we have that
m∑ j=1 ‖uj‖2|αj | = `+`′∑ j=1 ∥∥∥ ∑ i∈Kj vi ∥∥∥ 2 6 (i) `+`′∑ j=1 ∑ i∈Kj ‖vi‖2 = 2p∑ i=1 ‖vi‖2 ,
where inequality (i) follows from triangular inequality. Hence, we obtain that Lβ(θ(v)) 6 Lcβ(v).

heading: B.3 PROOF OF THEOREM 1
text: First, we show that Θ̃cvxm ⊆ Θ∗m. Let θ ∈ Θcvxm , and consider θ′ a split version of θ. Let (u, α) be a neuron of θ, and {(uj , αj)}kj=1 the neurons of θ′ which correspond to the split of (u, α). We have ∑m j=1 σ(Xuj)αj = ∑m j=1 γjσ(Xu)α = σ(Xu)α because ∑k j=1 γj = 1. Furthermore, 1 2 ∑k j=1 ‖uj‖22 + |αj |2 = 1 2 ∑k j=1 γj(‖u‖22 + |α|2) = 1 2 (‖u‖ 2 2 + |α|2), whence L(θ) = L(θ′). Consequently, Θ̃cvxm ⊆ Θ∗m.
It remains to show that Θ∗m ⊆ Θ̃cvxm . Let θ ∈ Θ∗m. Due to the strong convexity of the regularization term and the re-scaling invariance of the term σ(Xuj)αj , we must have that ‖uj‖2 = |αj | for each neuron (uj , αj) of θ. We partition the neurons of θ such that the neurons in each partition {(ui, αi)}ki=1 belong to the same cone C (in the sense that uiαi ∈ C), and the cones are pairwise distinct across partitions. Due to the regularization term, it is straightforward to show that the neurons must be positively colinear, and that this corresponds to a split. Thus, Θm ⊆ Θ̃cvxm and this concludes the proof.

heading: B.4 PROOF OF THEOREM 2: CLARKE STATIONARY POINTS ARE NEARLY MINIMAL NEURAL NETWORKS
text: We review the definition of the Clarke subdifferential Clarke (1975) of f . At x ∈ Rd, this is defined as
∂Cf(x) : = conv { lim k→∞ ∇f(xk) | lim k→∞ xk = x, xk ∈ D } ,
where D : = {x ∈ Rd | f differentiable at x}. In particular, it holds that Rd \D has measure equal to zero Borwein & Lewis (2010) under mild assumptions on f . Then, we say that x ∈ Rd is Clarke stationary with respect to f if 0 ∈ ∂Cf(x).
Let θ ∈ Θm be Clarke stationary, i.e., there exist λ(1), . . . , λ(N) > 0 and sequences {θ(1)k }k, . . . , {θ (N) k }k such that ∑N j=1 λ (j) = 1, limk→∞ θ (j) k = θ for each j = 1, . . . , N , the loss function Lβ is differentiable at each θ(j)k and
0 = N∑ j=1 λ(j) lim k→∞ ∇Lβ(θ(j)k ) .
PART 1: THE NEURAL NETWORK θ MUST BE SCALED.
By contradiction, we assume first that the neural network θ is unscaled, i.e., there exists a neuron (u, α) such that ‖u‖2 6= |α|. Write (u(j)k , α (j) k ) the corresponding neuron of each θ (j) k . Since limk→∞(u (j) k , α (j) k ) = (u, α), up to extracting subsequences, we can assume that the neurons (u (j) k , α (j) k ) are also unscaled, i.e., ‖u (j) k ‖2 6= |α (j) k | for all k > 1 and j = 1, . . . , N .
CASE 1: α 6= 0
Since limk→∞ α (j) k = α, up to extracting subsequences, we can assume that α (j) k 6= 0 for all k > 1 and j = 1, . . . , N . Then, for each j = 1, . . . , N and k > 1 and for t ∈ [0, 1], we define the neural network θ(j)k (t) as a copy of θ (j) k except for the neuron (u (j) k , α (j) k ) that we replace by
u (j) k (t) =
u (j) k
γ (j) k (t)
, α (j) k (t) = γ (j) k (t) · α (j) k ,
where γ(j)k ∗ = √ ‖u(j)k ‖2 |α(j)k | , γ(j)k (t) = 1 + t(γ (j) k ∗ − 1) and we use the improper notation u (j) k γ (j) k (t) = 0 if u(j)k = 0. Note that θ (j) k (t) defines a continuous path from θ (j) k = θ (j) k (0) to the scaled neural network θ(j)k (1). Further, since σ is positively homogeneous, it holds that for any t ∈ [0, 1],
σ(Xu (j) k (t))α (j) k (t) = σ(Xu (j) k )α (j) k ,
so that that the function Lβ(θ(j)k (t)) is constant as a function of t ∈ [0, 1]. On the other hand, the regularization term satisfies
R(θ (j) k (t)) = R(θ (j) k )−
β 2 (‖u(j)k ‖ 2 2 + |α (j) k |
2)︸ ︷︷ ︸ : =C(k,j)
+ β
2  ‖u(j)k ‖22 γ
(j) k
2 (t)
+ γ (j) k 2 (t)|α(j)k | 2

= C(k, j)︸ ︷︷ ︸ independent of t + β 2  ‖u(j)k ‖22 γ (j) k 2 (t) + γ (j) k 2 (t)|α(j)k | 2  . Note that the function g(j)k (t) : = Lβ(θ (j) k (t)) is differentiable, and simple algebra yields
dg (j) k
dt (0) = β ·
 √ ‖u(j)k ‖2 − √ |α(j)k |√
|α(j)k |  · (|α(j)k |2 − ‖u(j)k ‖22) . Hence,
lim k→∞
dg (j) k
dt (0) = β ·
(√ ‖u‖2 − √ |α|√
|α|
) · (|α|2 − ‖u‖22) .
Since |α| 6= ‖u‖2, it follows that limk∞ dg
(j) k
dt (0) < 0. On the other hand, we have that
dg (j) k
dt (0) = 〈
dθ (j) k
dt (0),∇Lβ(θ(j)k )〉 .
Simple algebra yields that limk∞ du
(j) k (t=0) dt = ( 1− √ ‖u‖2 |α| ) · u and limk∞ dα (j) k (t=0)
dt =(√ ‖u‖2 |α| − 1 ) · α. Thus, the limit dθ : = limk∞ dθ (j) k
dt (0) is constant (independent of the index j) and
N∑ j=1 λ(j) lim k→∞ dg (j) k dt (0) =
〈 dθ,
N∑ j=1
λ(j) lim k∞ ∇Lβ(θ(j)k )︸ ︷︷ ︸
= 0
,
〉
= 0 .
This is contradiction with the fact that ∑N j=1 λ (j) limk→∞ dg (j) k
dt (0) < 0. Therefore, in the case u 6= 0 and α 6= 0, we must have that ‖u‖2 = |α|.
CASE 2: u 6= 0
The proof proceeds exactly in the same way, except that we define
u (j) k (t) = γ (j) k (t) · u (j) k , α (j) k (t) =
α (j) k
γ (j) k (t)
,
where γ(j)k ∗ = √ |α(j)k | ‖u(j)k ‖2 , γ(j)k (t) = 1 + t(γ (j) k ∗ − 1) and we use the convention α (j) k γ (j) k (t) = 0 if α (j) k = 0.
PART 2: NON-ZERO NEURONS WHICH SHARE THE SAME ACTIVATION CONE ARE POSITIVELY

heading: COLINEAR
text: According to the first part of the proof, we can assume that the neural network θ is scaled.
(SPECIAL CASE) THE NEURAL NETWORK θ IS A DIFFERENTIABLE POINT OF Lβ .
In order to provide some intuition about the proof, let us assume first that Lβ is differentiable at θ. By contradiction, we suppose that there exist two non-zero neurons (u, α) and (v, β) such that B(u, α) = B(v, β), and, u and v are not positively colinear. Further, let us assume that α, β > 0 (the case α, β < 0 follows the same lines).
Define w : = αu+ βv. Note that w has the same sign pattern as u and v. For t ∈ [0, 1], we set
ũ(t) : = (1− t)αu+ t 2 w , ṽ(t) : = (1− t)βv + t 2 w , u(t) : = ũ(t)√ ‖ũ(t)‖2 , α(t) : = √ ‖ũ(t)‖2 , v(t) : = ṽ(t)√ ‖ṽ(t)‖2 , β(t) : = √ ‖ṽ(t)‖2 .
Note that B(u(t), α(t)) = B(u, α) = B(v, β) = B(v(t), β(t)). Further, we define θ(t) as a copy of θ where we replace the two neurons (u, α) and (v, β) by (u(t), α(t)) and (v(t), β(t)). Note that θ(t) defines a continuous path in Θm starting at θ.
Then, we introduce the two functions
g(t) : = `(ŷ(θ(t))) ,
h(t) : = R(θ(t)) ,
so that Lβ(θ(t)) = g(t) + β · h(t). First, we claim that g(t) is constant over [0, 1]. Indeed, this follows from the fact
σ(Xu(t))α(t) + σ(Xv(t))β(t) = σ(X(ũ(t) + ṽ(t)︸ ︷︷ ︸ =αu+βv )) = σ(Xu)α+ σ(Xv)β ,
where the first equality comes from the fact that B(u(t), α(t)) = B(v(t), β(t)). Hence, we have ŷ(θ(t)) = ŷ(θ) and g(t) is constant.
On the other hand, the function h(t) is clearly differentiable, and simple algebra yields that
dh(0) dt = −‖αu‖2 2 − ‖βv‖2 2 + 1 2 (αu)>(βv)
( 1
‖αu‖2 +
1
‖βv‖2
) .
Since u and v are not colinear, it holds by Cauchy-Schwarz inequality that (αu)>(βv) < ‖αu‖2‖βv‖2, and thus,
dh(0) dt < −‖αu‖2 2 − ‖βv‖2 2 + ‖αu‖2‖βv‖2 2
( 1
‖αu‖2 +
1
‖βv‖2
) = 0 ,
that is, dh(0)dt < 0. Thus, we finally obtain that dLβ(θ(0)) dt < 0, which contradicts the stationarity of θ.
(GENERAL CASE) THE NEURAL NETWORK θ IS NOT NECESSARILY A DIFFERENTIABLE POINT OF Lβ .
Now, let us generalize the above proof to the case where Lβ is not necessarily differentiable at θ. For a vector z ∈ Rn, we use the notations I+(z) : = {i ∈ {1, . . . , n} | zi > 0}, I0(z) : = {i ∈ {1, . . . , n} | zi = 0} and I−(z) : = {i ∈ {1, . . . , n} | zi < 0}.
Since θ is a Clarke stationary point of Lβ , we know that there exist λ(1), . . . , λ(N) > 0 and sequences {θ(1)k }k, . . . , {θ (N) k }k such that ∑N j=1 λ (j) = 1, limk→∞ θ (j) k = θ for each j = 1, . . . , N , the loss function Lβ is differentiable at each θ(j)k and
0 = N∑ j=1 λ(j) lim k→∞ ∇Lβ(θ(j)k ) .
For each k > 1 and j = 1, . . . , N , up to extracting subsequences, we can assume that u
(j) k , α (j) k , v (j) k , β (j) k 6= 0, and, α (j) k and β (j) k have the same sign (let us say positive). Further,
up to extracting subsequences again, we can assume that the sign patterns I+(Xu (j) k ) and I−(Xu (j) k )) (resp. I+(Xv (j) k ) and I−(Xv (j) k ))) remain constant (independent of k). Since the sign patterns of Xu and Xv are equal by assumption, and, since limk∞ u (j) k = u and limk∞ v (j) k = v, it follows that
I+(Xu) = I+(Xv) ⊂ {I+(Xu(j)k ) ∩ I+(Xv (j) k )} , (18)
and
I−(Xu) = I−(Xv) ⊂ {I−(Xu(j)k ) ∩ I−(Xv (j) k )} . (19)
We denote T (j)(u) and T (j)(v) the diagonal matrices (as introduced in Section 2) which correspond to the sign patterns of u(j)k and v (j) k , and which are independent of k by assumption. Then, using (18) and (19), it follows that
T (j)(u)Xu = T (j)(v)Xv , T (j)(u)Xu = T (j)(v)Xv . (20)
The above equalities will be crucial later on in our analysis.
Then, for each neural network θ(j)k , we can construct a similar path θ (j) k (t) as in the differentiable case, that is, we set w(j)k : = α (j) k u (j) k + β (j) k v (j) k , and
ũ (j) k (t) : = (1− t)αu (j) k +
t 2 w (j) k ,
ṽ (j) k (t) : = (1− t)β (j) k v (j) k +
t 2 w (j) k ,
u (j) k (t) : = ũ (j) k (t)√ ‖ũ(j)k (t)‖2 , α (j) k (t) : =
√ ‖ũ(j)k (t)‖2 ,
v (j) k (t) : = ṽ (j) k (t)√ ‖ṽ(j)k (t)‖2 , β (j) k (t) : =
√ ‖ṽ(j)k (t)‖2 .
Similarly to the differentiable case, we also define the functions
g (j) k (t) : = `(ŷ(θ (j) k (t))) ,
h (j) k (t) : = R(θ (j) k (t)) .
First, we claim that limk→∞ dg
(j) k (0) dt = 0. Indeed, we have
dg (j) k (0)
dt =
1
2
〈 (T (j)(u)− T (j)(v))X(v(j)k − u (j) k ),∇`(ŷ(θ (j) k )) 〉 .
Taking the limit k →∞, we obtain that
lim k→∞
dg (j) k (0)
dt =
1
2
〈 (T (j)(u)− T (j)(v))X(v − u),∇`(ŷ(θ) 〉 .
Using (20), we get that (T (j)(u)− T (j)(v))X(v − u) = 0, and consequently, the claimed equality limk→∞ dg (j) k (0)
dt = 0.
On the other hand, the function h(j)k (t) is clearly differentiable, and simple algebra yields that
lim k→∞
dh (j) k (0) dt = −‖αu‖2 2 − ‖βv‖2 2 + 1 2 (αu)>(βv)
( 1
‖αu‖2 +
1
‖βv‖2
) .
Since u and v are not colinear, it holds by Cauchy-Schwarz inequality that (αu)>(βv) < ‖αu‖2‖βv‖2, and thus,
lim k→∞
dh (j) k (0) dt < −‖αu‖2 2 − ‖βv‖2 2 + ‖αu‖2‖βv‖2 2
( 1
‖αu‖2 +
1
‖βv‖2
) = 0 ,
that is, limk→∞ dh
(j) k (0) dt < 0. Thus, we finally obtain that
lim k→∞ dLβ(θ(j)k (0)) dt < 0 ,
and further, that N∑ j=1 λ(j) lim k→∞ dLβ(θ(j)k (0)) dt < 0 .
However, it holds that
lim k→∞ dLβ(θ(j)k (0)) dt = lim k→∞ 〈 dθ (j) k (0) dt , ∇Lβ(θ(j)k )〉
It is immediate to see that dθ : = limk∞ dθ
(j) k (0)
dt does not depend on the index j, so that N∑ j=1 λ(j) lim k→∞ dLβ(θ(j)k (0)) dt = 〈dθ, N∑ j=1 λ(j) lim k→∞
∇Lβ(θ(j)k )︸ ︷︷ ︸ = 0 〉 .
That is, we obtained both that ∑N j=1 λ (j) limk→∞ dLβ(θ(j)k (0))
dt < 0 and∑N j=1 λ (j) limk→∞ dLβ(θ(j)k (0))
dt = 0, which is a contradiction. This concludes the proof that θ must be a nearly minimal neural network.

heading: B.5 PROOF OF PROPOSITION 3: REDUCTION TO NEARLY MINIMAL NEURAL NETWORKS ALONG A PATH OF DECREASING OBJECTIVE VALUE
text: We consider reductions similar to those in the proof of Theorem 2, in order to construct a path θ(t) ∈ Θm for t ∈ [0, 1] such that θ(0) = θ, θ(1) ∈ Θ̃minm and Lβ(θ(t)) is strictly decreasing. Naturally, we assume that θ is not nearly minimal, otherwise, there is nothing to show.
PART 1: THE NEURAL NETWORK θ IS UNSCALED.
We claim that there exists a path θ(t) ∈ Θm for t ∈ [0, 1] such that θ(0) = θ, θ(1) is scaled and Lβ(θ(t)) is strictly decreasing. Suppose that the neural network is unscaled (if not, go directly to Part 2). Then, for each neuron (u, α) of θ such that ‖u‖2 6= |α|, define
u(t) =
{√ |α| · uγ(t) if u, α 6= 0,
0 otherwise,
α(t) =
{ γ(t) · α√
|α| if α 6= 0,
0 otherwise, where γ(t) = √ |α| + t( √ ‖u‖2 − √ |α|). Simple algebra yields that (u(0), α(0)) = (u, α) and
‖u(1)‖2 = √ |α|‖u‖2 = |α(1)|, so that θ(0) = θ and θ(1) is scaled. By positive homogeneity of σ, we have that σ(Xu(t))α(t) = σ(Xu)α, which further implies that ŷ(θ(t)) = ŷ(θ) and L(ŷ(θ(t))) is constant as a function of t.
We claim that the regularization term R(θ(t)) is strictly decreasing as a function of t. Indeed, it holds that
‖u(t)‖22 + |α(t)|2 = |α| γ2(t) ‖u‖22 + γ2(t) |α| |α|2 .
The minimizer of the function γ ∈ R 7−→ |α|γ2 ‖u‖ 2 2 + γ2 |α| |α| 2 is given by γ∗ = √ ‖u‖2, which is also equal to γ(1), and the minimal value of the latter function is given by 2‖u‖2|α|, which is strictly smaller than ‖u‖22 + |α|2 since ‖u‖2 6= |α|. Thus, the function t 7→ R(θ(t)) is minimized at t = 1, and R(θ(1)) < R(θ). Lastly, observe that t 7→ R(θ(t)) is a convex function, which implies that it must be strictly decreasing over [0, 1]. This concludes the first part of the proof.
PART 2: THE NEURAL NETWORK θ IS SCALED BUT NOT NEARLY MINIMAL.
If the neural network θ is scaled but not nearly minimal, we claim that there exists a continuous path θ(t) for t ∈ [0, 1] such that θ(0) = θ, θ(1) is nearly minimal, and Lβ(θ(t)) is strictly decreasing. For each cone B ∈ {B1, . . . , B2q}, we consider the non-zero neurons UB : = {(u, α)} of θ such that B(u, α) = B. By assumption, there exists at least one cone B such that UB has more than two elements which are not positively colinear. Then, for each cone B, we set w = ∑ (u,α)∈UB |α|u, and, for each (u, α) ∈ UB and for t ∈ [0, 1],
ũ(t) : = (1− t)|α|u+ t |UB | w, u(t) : = sign(α) · ũ(t)√ ‖ũ(t)‖2 ,
α(t) : = sign(α) · √ ‖ũ(t)‖2 ,
where |UB | is the cardinality of the set UB . Note that B(u(t), α(t)) = B(u, α) = B, and each neuron (u(t), α(t)) is scaled. Further, we define θ(t) the neural network with neurons (u(t), α(t)). It holds that θ(t) defines a continuous path in Θm starting at θ, and ending at a nearly minimal neural network. Then, we introduce the two function g(t) = L(ŷ(θ(t))) and h(t) : = R(θ(t)), so that Lβ(θ(t)) = g(t) + β · h(t). First, we claim that g(t) is constant over [0, 1]. Indeed, this comes from the fact that for each cone B,∑
(u,α)∈UB
σ(Xu(t))α(t) = sign(α) · σ(X · ∑
(u,α)∈UB
|α(t)|u(t)
︸ ︷︷ ︸ =w
)
= sign(α) · σ(Xw) = ∑
(u,α)∈UB
σ(Xu)α .
The first (resp. third) equality holds from the fact that the neurons (u(t), α(t)) (resp. (u, α)) have the same active cone B. Thus, ŷ(θ(t)) = ŷ(θ) and g(t) is indeed constant.
On the other hand, we claim that the function h(t) is strictly decreasing. Indeed, observe first that
h(t) = β
2 ∑ B ∑ (u,α)∈UB ‖u(t)‖22 + |α(t)|2
= β ∑ B ∑ (u,α)∈UB ‖u(t)‖2|α(t)|
= β ∑ B ∑ (u,α)∈UB ‖ũ(t)‖2 ,
where the second equality holds since the neurons (u(t), α(t)) are scaled. Thus, it is immediate to verify that the function h is differentiable, and
h′(t) = β · ∑ B ∑ (u,α)∈UB
1
‖ũ(t)‖2 ( t · ‖ w |UB | − |α|u‖22 + |α|u>( w |UB | − |α|u) ) .
Clearly, h′(t) is strictly increasing (since there exists, by assumption, at least one cone B and a neuron (u, α) ∈ UB such that w|UB | 6= |α|u). Therefore, it suffices to verify that h
′(1) 6 0. Simple algebra yields actually that h′(1) = 0, which concludes the proof.

heading: B.6 PROOF OF PROPOSITION 4
text: The proof with trichotomies is almost identical to the proof of dichotomies in Pilanci & Ergen (2020); Sahiner et al. (2020). We start with the dual representation of P∗:
P∗ = max `∗(λ), s.t. max w:‖w‖261 |λT (Xw)+| 6 β.
Here `∗(λ) : = maxv{λT v − `(v)} is the Fenchel conjugate function of `. We note that the singlesided dual constraint has an equivalent formulation using trichotomies:
max w:‖w‖261
λT (Xw)+
= max j∈[q] max w:‖w‖261,w∈Qj
λT (Tj)+Xw.
Similarly, the other side of the dual constraint can be formulated as
max w:‖w‖261
−λT (Xw)+
= max i∈[q] max w:‖w‖261,w∈Qi
λT (Tj)+X(−w)
Therefore, we can rewrite P∗ as P∗ = max `∗(λ),
s.t. max w:‖w‖261,w∈Qi λT (Tj)+Xw 6 β, i ∈ [q],
max w:‖w‖261,w∈Qi
λT (Tj)+X(−w) 6 β, j ∈ [q].
For simplicity, we denote Tj+q = Tj for j ∈ [q]. We now formulate the Lagrangian
P∗ = max λ min ν>0 min wj∈Qj ,‖wj‖261
wj+q∈Qj ,‖wj+q‖261
`∗(λ) + q∑ j=1 νj(β − λT (Tj)+Xwj)
+ q∑ j=1 νj+q(β − λT (Tj)+X(−wj+q)).
By Sion’s minimax theorem, we can switch the max and min, and then minimize over λ. Following this, we obtain
P∗ = min νj>0 min wj∈Qj ,‖wj‖261
wj+q∈Qi,‖wj+q‖261
`  q∑ j=1 (Ti)+X(νiwi − νj+qwj+q) + β 2q∑ j=1 νj .
By rescaling the variable wj = νjwj , we can reformulate P ∗ as
P∗ = min νi>0 min wj∈Qj ,‖wj‖26νj
wj+q∈Qj ,‖wj+q‖26νj+q
`  q∑ j=1 (Tj)+X(wj − wj+q) + β 2q∑ j=1 νj .
Minimizing with respect to ν yields
P∗ = min wj ,wj+q∈Qj `  q∑ j=1 (Tj)+X(νjwj − νj+qwj+q) + β 2q∑ j=1 ‖wj‖2.
This completes the proof.

heading: B.7 PROOF OF THEOREM 3
text: According to Proposition 1 and 2, we can assume that θ is a minimal neural network. Denote λ̃ = ∇` (∑m j=1(Xuj)+αj ) . From the definition of Clarke’s stationary point, for j ∈ [m] with uj 6= 0, we have
− βuj ∈ ∂◦uj `  m∑ j=1 (Xuj)+αj  , − βαj = λ̃T (Xuj)+.
(21)
The first line in (21) is equivalent to that there exists δj ∈ [0, 1]N such that
−βuj = αj(XT D̃j λ̃+XT S̃jdiag(δj)λ̃). (22)
Here D̃j = diag(I(Xuj > 0)) and S̃j = diag(I(Xuj = 0)). As uj 6= 0 and αj 6= 0, this implies that
−β uj αj = XT D̃j λ̃+X T S̃jdiag(δj)λ̃. (23)
For the second line in (21), we can also rewrite it as
−βαj =λT D̃jXuj =uTj X T D̃jλ
=uTj (X T D̃jλ+X T S̃jdiag(δj)λ) =− uTj ( β uj αj ) .
(24)
Therefore, we have ‖uj‖2 = |αj | and∥∥∥XT D̃jλ+XT S̃jdiag(δj)λ∥∥∥ 2 = 1. (25)
For the subsampled convex program (13), the KKT conditions are given by: for i ∈ I, there exists ζ(i) 0 and ξ(i) such that
XT ((Ti)+λ+ Tiζ (i) + Siξ (i)) + β wi ‖wi‖2
= 0, if wi 6= 0,∥∥∥XT ((Ti)+λ+ Tiζ(i) + Siξ(i))∥∥∥ 2 6 β, wi = 0, XT (−(Ti)+λ+ Tiζ(i) + Siξ(i)) + β wi+q ‖wi+q‖2
= 0, if wi+q 6= 0,∥∥∥XT (−(Ti)+λ+ Tiζ(i) + Siξ(i))∥∥∥ 2 6 β, if wi+q = 0.
(26)
Here Si is a diagonal matrix satisfying that (Si)jj = 1 if j ∈ I0 and (Si)jj = 0 if j ∈ I+ ∪ I−, where {I+, I0, I−} is the i-th trichotomy. The vector λ ∈ RN is defined as λ = ∇` (∑ i∈I(Ti)+X(wi − wi+q) ) . As θ is a minimal neural network, there exists a bijective mapping between non-zero neurons (uj , αj) and i ∈ I. For i ∈ I, suppose that Ti = diag(sign(Xuj)). If αj > 0, we let
wi = αjuj , wi+q = 0,
otherwise, we let wi = 0, wi+q = −αjuj , ζ(i) = 0. As the mapping between non-zero neurons (uj , αj) and i ∈ I is bijective, we note that∑m j=1(Xuj)+αj = ∑ i∈I X
T D̄i(wi − wi+q). This implies that λ̃ = λ. On the other hand, by taking ζ(i) = 0, ξ(i) = diag(δj)λ̃, ζ(i+q) = 0, ξ(i+q) = −diag(δj)λ̃, as D̃j = (Ti)+ and S̃j = Si, the KKT conditions (26) are satisfied. Therefore, W = {wi, wi+q|i ∈ I} is a global optimum of the subsampled convex program (13).

heading: B.8 PROOF OF PROPOSITION 5
text: Let θ̃ ∈ Θm be a minimal neural network, and suppose that W (θ̃) satisfies the KKT conditions of the optimization problem (4). Since the latter is a convex optimization problem, it follows that W (θ̃) is a global minimum. From Proposition 2, we have that P∗ 6 Lβ(θ(W (θ̃))) 6 Lcβ(W (θ̃)) = P∗c = P∗, it follows that Lβ(θ(W (θ̃)) = P∗ and θ(W (θ̃)) is a global minimizer of Lβ , which yields the claimed result.

heading: B.9 PROOF OF PROPOSITION 6
text: Without loss of generality, we can assume that θ is scaled. Otherwise, we know from the proof of Proposition 3 that θ can be reduced to a scaled neural network along a continuous path of non-increasing training loss.
We follow the same steps as in the proof of Lemma 1. Denote the neurons of θ by (u1, α1), . . . , (um, αm). We have that ŷ(θ) = ∑m i=1 λ̃i zi, where zi =
sign(αi) ( ∑m j=1 ‖uj‖|αj |)σ ( X ui‖ui‖ ) and λ̃i = ‖ui‖|αi|∑m j=1 ‖uj‖|αj | . Thus, ŷ(θ) ∈ Conv{z1, . . . , zm}.
From Lemma 3, we know that there exist i1, . . . , in+1 and λ1, . . . , λn+1 > 0 such that ∑n+1 j=1 λj = 1
and ŷ(θ) = ∑n+1 j=1 λjzij . Plugging-in the expressions of the zij , it follows that
ŷ(θ) = n+1∑ j=1 λj sign(αij )  m∑ j=1 ‖uj‖|αj | σ(X uij ‖uij‖ )
= n+1∑ j=1 α̃ijσ(Xũij ) ,
where  νj : = λj ‖uij ‖ ( ∑m k=1 ‖uk‖|αk|), ũij : = √ νj ‖uij ‖ uij ,
α̃ij : = sign(αij ) ‖ũij‖.
Further, we have that n+1∑ j=1 |α̃ij |‖ũij‖ = n+1∑ j=1 νj‖uij‖ = n+1∑ j=1 λj( m∑ k=1 ‖uk‖|αk|) = m∑ k=1 ‖uk‖|αk| ,
where the last equality follows from the fact that ∑n+1 j=1 λj = 1. Setting θ̃ the neural network with neurons (ũij , α̃ij ) for j = 1, . . . , n + 1 and (ũi, α̃i) = (0, 0) for i ∈ {1, . . . ,m} \ {i1, . . . , in+1}, we obtain that θ̃ ∈ Θm and Lβ(θ̃) 6 Lβ(θ).
Now, we define a continuous path between θ and θ̃, as follows. For t ∈ [0, 1], j = 1, . . . , n+ 1 and i ∈ {1, . . . ,m} \ {i1, . . . , in+1}, we set
uij (t) = (1− t)uij |αij |+ t ũij |α̃ij |√ ‖(1− t)uij |αij |+ t ũij |α̃ij |‖
αij (t) = sign(αij ) ‖uij (t)‖ ui(t) = √ 1− t ui αi(t) = √ 1− t αi ,
and θ(t) the neural network with neurons {(ui(t), αi(t))}mi=1. Note that θ(t) is scaled, and m∑ i=1 ‖ui(t)‖|αi(t)| = n+1∑ j=1 ‖(1− t)uij |αij |+ t ũij |α̃ij |‖+ ∑
i=1,...,n+1 i 6=i1,...,in+1
(1− t) ‖ui‖|αi|
= (i) (1− t) n+1∑ j=1 |αij |‖uij‖+ (1− t) ∑
i=1,...,n+1 i 6=i1,...,in+1
‖ui‖|αi|+ t n+1∑ j=1 |α̃ij |‖uij‖
= (ii)
(1− t)R(θ) + tR(θ̃)
= (iii) R(θ) ,
where equality (i) follows from the triangular inequality and the fact that ũij and uij are positively colinear; equality (ii) follows from the fact that θ̃ and θ are scaled; equality (iii) holds since R(θ) = R(θ̃). Thus, the function t 7→ R(θ(t)) is constant over [0, 1]. On the other hand, we have
ŷ(θ(t)) = n+1∑ j=1 σ ( X((1− t)uij |αij |+ t ũij |α̃ij |) ) sign(αij ) + (1− t) ∑ i=1,...,n+1 i 6=i1,...,in+1 σ(Xui)αi
= (i) (1− t) n+1∑ j=1 σ(Xuij )αij + t n+1∑ j=1 σ(Xũij )α̃ij + (1− t) ∑
i=1,...,n+1 i 6=i1,...,in+1
σ(Xui)αi
= (1− t) ŷ(θ) + t ŷ(θ̃) = (ii) ŷ(θ) ,
where equality (i) holds since the uij and ũij are positively colinear and the αij and α̃ij have same signs; equality (ii) holds since ŷ(θ̃) = ŷ(θ). Consequently, the function t 7→ Lβ(θ(t)) is constant over [0, 1], and this concludes the proof of the fact that θ I θ̃.

heading: B.10 PROOF OF PROPOSITION 7
text: First, according to Proposition 6, given θ ∈ Θm with m > n+ 1 +m∗, there exists a neural network θ̃ with at most n+ 1 non-zero neurons such that Lβ(θ̃) 6 Lβ(θ). According to Lemma 1, there exists θ∗ = {(u∗i , α∗i )}mi=1 an optimal neural network with at most m∗ non-zero neurons. Up to a permutation of the zero neurons of θ̃ and those of θ∗, sincem > n+1+m∗, we can assume without loss of generality that (u∗i , α ∗ i ) = (0, 0) for i = m
∗ + 1, . . . ,m and (ũi, α̃i) = (0, 0) for i = 1, . . . ,m∗.
Now, we define a continuous path between θ̃ and θ∗. For i = 1, . . . ,m∗ and j = m∗ + 1, . . . ,m, we set the neural network θ(t) ∈ Θm with neurons
ui(t) = √ t u∗i , αi(t) = √ t α∗i , uj(t) = √
1− t ũj , αj(t) = √ 1− t α̃j .
Clearly, we have θ(0) = θ̃ and θ(1) = θ∗. Further, θ(t) is scaled and it is easily verified that
R(θ(t)) = tR(θ∗) + (1− t)R(θ̃),
ŷ(θ(t)) = t ŷ(θ∗) + (1− t) ŷ(θ̃) .
This immediately implies that the function t 7→ Lβ(θ(t)) is convex over [0, 1]. Since it achieves a minimum at t = 1, it follows that it is non-increasing, and this concludes the proof of Proposition 7.

heading: C PROOFS OF INTERMEDIATE RESULTS

heading: C.1 PROOF OF LEMMA 2
text: Proof. It holds that ∑ i∈I σ(Xui)αi = ∑ i∈I γiσ(Xwi) = ∑ i∈I DiXwi, whence
`( ∑ i∈I σ(Xui)αi) = `( ∑ i∈I DiXwi). On the other hand, we have ‖wij‖2 = ‖uj‖2|αj |. Note that ‖uj‖2 = |αj | and thus, ‖uj‖2|αj | = 12 (‖uj‖ 2 2 + |αj |2). Consequently, Lβ(θ) = Lcβc(w∗). From Pilanci & Ergen (2020), we know that P∗ = P∗c . Hence, Lβ(θ) = P∗.

heading: C.2 PROOF OF LEMMA 1
text: We aim to show that m∗ 6 n+ 1 and P∗m for any m > m∗. We leverage the following result which is known as Caratheodory’s theorem.
Lemma 3. Let z1, . . . , zm ∈ Rn. Suppose that y ∈ Conv{z1, . . . , zm}. Then, there exist indices i1, . . . , in+1 ∈ {1, . . . ,m} such that y ∈ Conv{zi1 , . . . , zin+1}.
Suppose that θ is an optimal neural network with m > n + 1 neurons, and denote its neurons by (u1, α1), . . . , (um, αm). We have that ŷ(θ) = ∑m i=1 λ̃i zi, where zi =
sign(αi) ( ∑m j=1 ‖uj‖|αj |)σ ( X ui‖ui‖ ) and λ̃i = ‖ui‖|αi|∑m j=1 ‖uj‖|αj | . Thus, ŷ(θ) ∈ Conv{z1, . . . , zm}.
From Lemma 3, we know that there exist i1, . . . , in+1 and λ1, . . . , λn+1 > 0 such that ∑n+1 j=1 λj = 1
and ŷ(θ) = ∑n+1 j=1 λjzij . Plugging-in the expressions of the zij , it follows that
ŷ(θ) = n+1∑ j=1 λj sign(αij )( m∑ j=1 ‖uj‖|αj |)σ ( X uij ‖uij‖ )
= n+1∑ j=1 α̃ijσ(Xũij ) ,
where  νj : = λj ‖uij ‖ ( ∑m j=1 ‖uj‖|αj |) ũij : = √ νj ‖uij ‖ uij
α̃ij : = sign(αij ) ‖ũij‖
Further, we have that
n+1∑ j=1 |α̃ij |‖ũij‖ = n+1∑ j=1 νj‖uij‖ = n+1∑ j=1 λj( m∑ k=1 ‖uk‖|αk|) = m∑ k=1 ‖uk‖|αk| ,
where the last equality follows from the fact that ∑n+1 j=1 λj .
We define the neural network θ̃ with neurons (ũij , α̃ij ). We have that θ̃ ∈ Θn+1 and P∗n+1 6 Lβ(θ̃) = Lβ(θ) = P∗m. Since P∗n+1 > P∗m for any m > n+ 1, it follows from the previous set of inequalities that Lβ(θ̃) = P∗n+1 = P∗m, and this holds for any m > n+ 1. Therefore, P∗n+1 = P∗ and Lβ(θ̃) = P∗.
We set W̃ = W (θ̃). We know from Proposition 2 that W (θ̃) ∈ Wn+1 and Lcβ(W̃ ) 6 Lβ(θ̃). Hence, P∗c 6 P∗. We also know that Lβ(θ(W̃ )) 6 Lcβ(W̃ ). This implies that P∗c = P∗ and W̃ is an optimal solution to (4). Consequently, m∗ 6 n+ 1.
It remains to show that for any m > m∗, we have P∗m = P∗. This follows again from Proposition 2. Indeed, let W ∗ be an optimal solution to (4) such that W ∗ ∈ Wm∗ . Set θ∗ = θ(v∗). We know that θ∗ ∈ Θm∗ , and Lβ(θ∗) 6 Lcβ(W ∗) = P∗c = P∗. Hence, θ∗ achieves P∗ and this implies that for any m > m∗, we have P∗m = P∗.
D VERIFICATION OF THE OPTIMAL SET
We review a standard method to determine whether a convex optimization problem has unique solution. Consider a convex optimization problem
min f(x), s.t. fi(x) 6 0, i ∈ [m], (27)
in the variable x ∈ Rd. Here f and fi for i ∈ [m] are convex functions. Suppose that we calculate one optimal solution x∗ and the corresponding optimal value f∗. We can determine whether x∗ is the
unique optimal solution of (27) as follows. For j ∈ [d], consider the following convex optimization problems
plbj = minxj , s.t. fi(x) 6 0, i ∈ [m], f(x) 6 f∗, (28)
pubj = maxxj , s.t. fi(x) 6 0, i ∈ [m], f(x) 6 f∗. (29) These problems give the upper bound and the lower bound of the value of the i-th index in the optimal set of (27). Suppose that pubj − plbj 6 for certain small > 0, for instance, = 10−8. Then, the radius of the optimal set with respect to the `∞ norm is upper-bounded by . Therefore, we can be confident that x∗ is the unique optimal solution up to numerical tolerance.
We have verified numerically that the convex optimization problem in Example 1 in section 3.1 has a unique optimal solution.

Review summaries:
Along the line of Pilanci & Ergen (2020), this submission deals learning two-layer ReLU neural networks through convex optimization. It introduces a number of new notions such as (nearly) minimal neural networks, developing a set of interesting tools, and draws connections between the minimal neural networks and the convex optimization landscape. This paper provides a rich framework along with new analyses and solutions for learning two-layer ReLU networks through convex cone optimization. 

The paper explores the landscape of the objective function in training a single-hidden layer neural network with ReLU activation and L2 regularization. Impressively, the paper has the following contributions:  1. It advances the results of Pilanci and Ergen from 2020 by showing that all *global* optimum points can be found via the convex program introduced by Pilanci and Ergen.  2. It shows that for a large enough width of the hidden layer (at most 2*(n+1), where n is the number of training examples) there are no spurious valleys (i.e . all local minima are global), and GD won't get "stuck". 3. It defines a subclass of single-hidden layer neural networks which it terms "nearly minimal". It characterizes  stationary points of the optimization problem by showing that every such point must be a nearly minimal neural network. 4. It gives a polynomial time algorithm for checking whether a stationary point is a global optimum. 

This paper establishes some very interesting connections between the global optimizer of the two-layer ReLU neural networks with the solution of a convex optimization program with cone constraints. More concretely, the authors construct explicit mappings between a smaller class of neural networks called minimal neural networks (that contains all the global optima) and the optimal solutions of convex programming problem. They also show that first-order methods such as SGD can find networks that can be merged to a minimal representation. Lastly, they provide an explicit path of non-increasing loss between any point on the loss landscape to the global minimizer. With this, they prove that has no spurious local minima, provided that the number of neurons is sufficiently large.

In this paper, the authors study the training of two-layer ReLU networks with weight decay.  A previous paper (Pilanci and Ergen 2020) introduced a convex optimization problem that corresponds to this non-convex case.  In the present paper, the authors prove that all optimal solutions of the nonconvex formulation can be found via optimal solutions of this convex formulation.  (Whereas the Pilanci and Ergen paper only constructed a single solution).  The authors additionally show that a Clarke stationary point of the nonconvex objective corresponds to a global minimum of a subsampled version of the convex problem, and they provide a polynomial time algorithm to test if a neural network is globally optimal.  Finally, the authors prove that the nonconvex loss landscape has no spurious local minima provided the number of neurons is large enough.