The Hidden Convex Optimization Landscape of Regularized Two-Layer ReLU Networks: an Exact Characterization of Optimal Solutions
Authors: Yifei Wang
Jonathan Lacotte
Mert Pilanci
Venue: ICLR 2022 Oral (2022)
Keywords: Neural networks
global optimization
convex optimization
convex analysis

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.

Published as a conference paper at ICLR 2022
THE HIDDEN CONVEX OPTIMIZATION LANDSCAPE OF REGULARIZED TWO-LAYER RELU NETWORKS: AN EXACT CHARACTERIZATION OF OPTIMAL SOLUTIONS
Yifei Wang'
Jonathan Lacotte"
Department of Electrical Engineering
Department of Electrical Engineering
Stanford University
Stanford University
Bangyy118staaffod..co
lacote@@ranford.eee
Mert Pilanci
Department of Electrical Engineering
Stanford University
pilanci Saaancisttaffod.cco edu
ABSTRACT
We prove that finding all globally optimal two-layer ReLU neural networks be performed by solving convex optimization program with cone constraints. Our analysis is novel, characterizes all optimal solutions, and does not leverage maality-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 construct exactly the entire set of optimal neural networks. We provide 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 subsampled convex problem (ii) we provide a polynomial-time algorithm for checking a neural network a global minimum of the training loss (iii) we provide explicit construction of continuous path between any neural network and the global minimum of its sublevel set and (iv) characterize the minimal size of the hidden layer 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.
INTRODUCTION
Let X E Raxd and y E R be the data matrix and the label vector. Given number of neurons and regularization parameter 3 > O, consider the regularized optimization problem
3
m
P min DE
C3(())
Σ (Xuu)a
+
(1u:1 (lu:1++a2)
where O. = Rdxm x Rm 0 = a). is the i-th column of U E Bdxm and is the i-th coefficient
Rm Here we focus on the ReLU activation, i.e., (2)) = max(2, 0} and absorb the label E R" in the loss function & R - R. which is assumed to be convex (e.g., logistic, hinge, squared loss). The model Σn (Xuu, uz )as in T can be easily extended to the one with bias term by adding column of I'ss into the data X. We refer and to each pair (u, as) as a neuron. We denote the set of optimal neural network as
element & E O, neural network
e = (0 E Am (g) = P..))
(2)
We denote the hest training loss achievable by a neural as P = infma1 P
"qqual contributions

---

Published as a conference paper at ICLR 2022
The ReLU activation induces natural partition of the parameter space. We denote Dı..... Dp as all possible values of di >> 0)). We introduce the corresponding convex cones C, = {u E (2D: u) 0} for i [p] where we denote [p] {1, . .P). From this partition we have the local linearization
for C. o(Xu= = D,Xu,
We let Diep - D, for E [p] and Ci+p - C, for i E [p].
Such partition of the parameter space has regained attention in the recent literature. In Pilancii Ergen (2020) recently showed that an optimal neural network 0* Om for any m > 2y can be constructed based on a solution of the convex optimization problem
2p
: = min WeW
(WW) e (E D:Xwa + +
Σ | 10llla]
(4)
1=1
where we introduced the convex feasible set W: := ( = (W1, Wpp)) wy E C.J. In a nutshell,
this equivalence can be intuitively explained follows. From the constraint w; E C. we obtain the local linearization or (Xw;; = w, for E [p] and o (Xw;; = -D,Xw for E p + 1, 2p). By choosing neurons (ut, 03)) such that w; la (o//1,, 0g > 0 for [p] and a; for i p + further obtain by positive homogeneity of the ReL.U that
2p Σ DiXW; = - (XU..a..
2p
(5)
From the fact that the cones Ci...., Cp cover the entire space, Pilanci & Ergen (2020) establish the equality P. = =P" and show that an optimal neural network can be constructed from an optimal solution wi. w w:p-
In this work, we explore the mapping from the optimal set of solutions W of the convex program (4) to the set of optimal neural networks O Our main contribution is show how construct the 0% given W through simple transformations. 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).
1.1 PRIOR AND RELATED WORK
Several recent works considered over-parameterized neural networks in the infinite-widit limit. In particular, it is known that in this regime, gradient descent converges to an optimal solution, see (Jacot et al. 20188 Du et al. 2018 Allen-Zhu et al. 2018 Nguyen 2021). Further analysis in (Chizat & |achh 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. WWang& & Lin (2021) showed that with 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 al. 2006 Bach] (017)). 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 feinite-dimessione optimization problem, which requires solving non-convex problems at every step train shallow neural network. In contrast, 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. B = 0) objective C3 has no spurious local minima provided that the number of neurons satisties > and similar result was shown in (Livni et al. 2014). Similar results were derived for deep networks. For instance, Soudry & Carmon (0016) showed that under a dropout- noise assumption, there exist 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 neural network implement any dichotomy for inputs in general position. In
2

---

Published as a conference paper at ICLR 2022
similar vein, Nguyen & Hein (2017) showed that spurious minima occur provided that one of the layer's 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 let al. 2019 Du & Lee 2018 Soltanolkotabi et al. 2018). These analyses are typically based on the idea that when 2 then is very likely that the features o(Xux Uu)), wu),,..., o (X un.)) form basis of IR" so that the training problem reduces to finding a linear model with weights R1..... Om which perfectly fits the labels. For the hinge loss and linear separable data, (Wang 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 optimiza- tion 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] [harifnassab al., 2019). it is shown that there exists 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 & Brunal 2016, Venturi et al.
2019 guyen 2019: Nguyen et al. 2021) and there is no bad local valley (Nguyen & Hein (207))
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., 8 = 0), it should be noted that the set of optimal solutions always contains infinitely many points. For instance, with ReI. activations, it holds that if 6" ((,,,))) [])] is an optimal neural network, then any re-scaling of 0t in the form ( a (with ",..... 7m 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 u,'s s, and one cannot simply generate such a basis of R" based on the features a (Xu1), ...,....dd o (Xum) by random sampling and then overfitting the labels.
0) has the same objective value and is thus
Recently, Pilanci & Ergen 2020); Ergen pilanci (200)) show that two-layer ReLU neural networks can be optimized exactly via finite-dimen dimee-iimenional convex programs with complexity polynomial in the number of samples and hidden neurons. As indicated in PPilanci & Ergen (2020), the worst-case complexity is exponential in the dimension of the training samples unless P -NP.
1.2 SUMMARY OF OUR CONTRIBUTIONS
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 2
In Section B] we show that any minimal neural network A can be represented, via an explicit map, in the convex feasible space W as point W(f) such that (s) > C3 (O))). and vice-versa. This structural result provides a mathematically rich perspective to characterize optimal neural networks through the lens of convexity. We then provide 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 0 with respect to C3 is a nearly minimal neural network. This provides preliminary structure on the solutions found by stochastic gradient descent (SGD), as it has been recently shown (see, for instance, Corollary 5.1 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 0 with respect to La also corresponds to global minimum of 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 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 + 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 0 and f', where 6' is the global optimum of the non-convex training problem. This establishes that the training loss C, has no spurious local minima, provided that the number of neurons is sufficiently large.
3

---

Published as a conference paper at ICLR 2022
1.3 NOTATIONS
We first present an alternative interpretation of the cones C, and the diagonal matrices D; for i E [p]. The ReLU activation function partitions the space of neurons u E Rd into linearly separated regions, that is, given a binary vector E {0, 1)", the set of neurons u E R such that 1(xu > 0) a convex cone in Rd, if not empty. We enumerate the closures of all these cones as CI...., Cp and we set Ct+p = C₁ for i E [p]. For E [p). we introduce the corresponding diagonal matrices D; = d > 0)) for an arbitrary u E C₁, and D2+p = D, Here the number p the number
of dichotomies that the data matrix X can realize. It is upper bounded by p < 2r
where
r ran see (Cover 1965).
Beyond the dichotomies of the space of neurons u E Rd, we further introduce the partitions (trichotomies) (1+, Ju, I-] } of [n]] such that there exists a solution vector u E IRd verifying (Xu)): > if k E 1+, (Xu)}= = 0 if l E Io and (Xu)a < if & E I_. Clearly. there exists finite number 9 of such trichotomies and y is trivially upper bounded by 3". For the j-th trichotomy (/,, To, 1 }. we define the
diagonal matrix 7; with k-th diagonal element (T)) = 1 if k E T+. (T, (A)))) Ra 0 if E Lo and (I)) = 0if E I_. Such trichotomies are also discussed in Phuong & Lampeer (2020).
For each j 1, ........ 9. we define Qj as the closed convex cone of solution vectors for the j-th trichotomy {14, lo. J. We consider a partition {B),... B2a} of the neurons' parameter space where B, Qi x R> j =1,- ................................ q and B5 Qj ---g" x R <0 for j g+ g+.....,22 2q. We augment the set of diagonal matrices (T by setting T3 = TT- for = + 1, 1....,24. 2q.
For neuron pair (u, a) E IR' x I. we denote B(u, a)) the unique B, such that (u,a) E B,
The notion of path-connected sublevel set is introduced as follows.
Definition We write - 0' if the neural network 6' E Om belongs to the path-connected sublevel set (or valley) of 0 O Namely, there exists a continuous path 7 [0. - O.. such that 70)) = 8, 7(1) = 8' and t +> Ls(r((t)) is non-increasing. We denote the valley of O (2(0) : (0' E Om 0 0'). We say that 0 E Om is non-spurious if 0" for some 0" E angmingree. g... Ca( Otherwise, we say that 0 and its valley (10) are spurious.
MINIMAL NEURAL NETWORKS AND NEARLY MINIMAL NEURAL NETWORKS
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 (Minimal neural networks). We say that a neural network is minimal (i) is scaled, i.e., ||u=]|2= pairwise distinct. That is, a minimal neural network has at most a single non-zero neuron per cone B, We denote by mmin the set of minimal neural networks with neurons.
i E [m] and (ii) the cones B(u, a.) of each of its non-zero neurons (u, a) are
Note that any minimal neural network has at most 2q non-zero neurons since there are 2g cones B, and at most one neuron per cone. Next, we introduce a slightly less structured class of neural networks that one can interpret '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 neural network 0 is nearly minimal if (i) it is scaled and for any two non-zero neurons (u,a), (v, B) of 0, if B(u, a) = B(v, 8) then u and u are positively colinear, i.e., there exists X 2 0 such that u Nv. We denote by m the set of nearly minimal neural networks with m neurons. It trivially holds that @ynnn C G
For nearly minimal neural network, by merging the neurons corresponding the same trichotomies, we can reformulate it into a minimal neural network without changing the objective value.
2.1 FROM NEARLY MINIMAL TO MINIMAL NEURAL NETWORKS
Nearly minimal neural networks have the property that any two neurons which share 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 minimal neural network.
4

---

Published as a conference paper at ICLR 2022
Formally, we let 0 Omin be nearly minimal neural network with neurons and we fix (w, 7) a non-zero neuron. Let (w2,72).... ..... (wi,, "ik) E 9 be the other non-zero neurons such that for each k, we have sign(y) sign( (ny)) and, and Wj are positively colinear. Write (Wi, 71) : (w, 7), and define the merged neuron "w"",""" as wnth : 21=1 Insl:;
and y VIE ly myyll ymt = sign(7) /w" Let M(0) be copy of & where each such set of k positively colinear neurons {(w1, ......., (wk,70 }*)} is replaced by the k neurons { ,,m",, (0, 0).... (0. 0)). We refer to MM()) as the merged version of 0. The next result states relevant properties of M(0).
Proposition 1. Let f E Gmi.. Then, the following results hold.
1. The merged neural network M(0) is a minimal neural network.
2. We have 0 M(0), and the continuous path from 0 to M(0) has constant objective value.
3. If M(0) is a local minimum of Cg. then 0 is also a local minimum of Cg.
Intuitively, merging the colinear neurons preserves the active cones and leaves a single neuron per cone, so that MMP)) is indeed minimal. The third property essentially follows from the fact that M(0) has more degrees of freedom than 0 since it has more neurons equal to addition, the continuous path of constant objective value from I to M(0) can be explicitly constructed (see the proof in Appendix|B.. B.I.
3 MAPPING NEURAL NETWORKS TO A CONVEX OPTIMIZATION LANDSCAPE
We provide here explicit map from the set of minimal neural networks to the feasible set W of the convex program 44) and vice-versa. For W = (Wi,.... W2p) E W, we let [llo be number of the non-zero vectors in Wi...., ...., W2pp Define
Wm ( W ||lloo & m), W Wm. n W
(6)
First, we introduce the map (0) from Qmin Wm where for each 1,..., 2p, we set
w0( =
Σ
j= B(
and such that each non-zero neuron (uy, .2)) contributes only to a single uy. To understand the latter, note that each cone Bu,, a,) might be a subset of several (adjacent) cones B, and hence, one might need to choose which w; neuron (u,, az) contributes to. These ties can be resolved arbitrarily without affecting any of our results.
Conversely, construct a map W + 8(W) from Wm to Q by setting ((W) {(u,, 0ss) 1m where the (w, a,) are defined as follows. Denote i < ... < im the indices such that i & (i1,- -1.-.--. ,m then w; O. Take the index (if any) such that is & p and i 3 p + 1. Let [i1,...,K]] be a partition of (i1,...,4y) is} in terms the repartition of Wiy...,, Wi, into the cones (Qi....Q Similarly, let {K411.... Ke_er) } be partition of (i.41,..., im) in terms of the repartition of Wiy411..., Wim. into the cones
J, Then, for 1 [EjE+ we set
ExEK, Wi
(u
Σ iEK;
wall2
(8)
( LIEK, wallz
where 7; = 1 & and 7/ -1 i l. Finally, for E' 1 m. set (uj, az) (0.0).
As stated in the next result, these mappings can only improve the training loss.
Proposition 2. It holds that for any W Wm we have (B()) < CS),), and, for any Ø min we have Cg (Ō) & Co) Furthermore, it holds that O(W (()) E ((0).
These mappings between minimal neural networks and the convex feasible set provide rich structure to address the optimality properties of neural networks. In Figure [ we provide an illustration the non-convex and convex landscapes toy neural network training model.
5

---

Published as a conference paper at ICLR 2022
Figure 1: Comparison of the non-convex landscape (left) and the convex landscape (right) of program (4). Here, we consider the toy example with date
1, label y = and the l2 loss. Then, we have (u, a) (1 max(u, (u, 0} a)² [1ul² + |ox|)). The convex objective is then () (1
2²² + (l0) + /wl) subject to v, > 0. The set of minimal neural networks corresponds to [u] lal, which includes the optima. Further, the optimal values of the two functions match and are equal to 0.75, and attained at (u, o) (1 (1/v2,1 1/v2) and (v, w) (1/2, 0). Note that u/a: = v, and this indeed corresponds to our mapping
3.1 THE GLOBAL OPTIMAL SET OF NEURAL NETWORKS
Let m = minwew || As a consequence of Caratheodory's theorem, we have the following upper bound on the minimal cardinality m" of optimal solution.
Lemma 1. It holds that m & n + 1. Further, for any m > m², we have that P = inf Pj--
From the definition of m clearly holds that WT for 3 m'. Then, we present the mapping from the optimal solution to the convex problem (4) to globally optimal neural network for the non-convex problem II]
Lemma 2. Let W (W1,.. .... W2p) E W and denote by I tii...., i C [2p] the set of indices such that : + O for E I. We set
(u,, = ( Viuu, 12"
Wi;
Yis Ilw,, ll2
for i; E I. Here lifi & and %/2 -1 if > p. Then, it holds that 0 = {(us, as)) as))) [l is an optimal neural network, iee. ( =P-
We denote the above mapping 9 by sh, and we set O (( According to Lemma 2
holds that Ocx C O Given a neuron (u, a.), we say that collection of neurons {(ug, (,,,,,a)))) ,,)));
a splitting of (u, ai) if (uj, az) (vTju, TTa) for some 7 > and Σ " Given a neural network 0 = ((u,, ) a splitting of any neural network 0' On such that the non-zero neurons of 0' can be partitioned into splittings of the neurons of 8. Similarly, split neurons can be merged back to their original form. We denote by θcyx the set of splittings generated from Oevx We provide an exact characterization of the optimal set in the following theorem.
Suppose that m. > m'. It holds that O 6 Namely, all optimal solutions of the nonconvex loss can be found via the optimal solutions of the convex program (4) up permutation and splitting/merging of the neurons as defined above.
Theorem 1.
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 T shows how construct the entire set of global optimum the nonconvex loss. The relations among W m
evvx δevx and @*, is illustrated Figure
m
[]
07
Example 1. We consider a toy example, where x =
0
1
Y
0
and 3 = 0.1. In this case,
1
p 6 and we can enumerate the diagonal matrices D,
Di diag [0, 0, 0,0)), D2 ddiag((0 [0, 1, 0]), D3 (0, 1,1),,
(10)
D4 = diag [1, 0,)),, D; = diag [1, 0, 1]), De = diag([1,

---

Published as a conference paper at ICLR 2022
Proposition
Nearly minimal neural networks
merge
Minimal neural network @
m
split
Theorem
convexify
ReLU
Lemma
The set of global minimizers the nonconvex loss
Optimal set of convex problem W
Figure 2: Illustration of relations between W mxx x and O
The optimal solution to the convex problem (4) is given by W (wi,... W2p), where W only consists of one non-zero block w = [0.86, -..79] Therefore, the set of the global minimizers of the nonconvex loss Lg consists of all nearly minimal neural network 0 {[u, (il,,a;))e a=) satisfying
04 V
02 = V 1urill
i [m).
(11)
/uglle
where Ex - and 2 O are arbitrary. These correspond to the split versions of the single neuron Wy. We investigate numerically our result: for m = 5, we run gradient descent (GD) on the nonconvex loss L3 until find nearly stationary neural network {(us: We plot the points ar as well as wg in Figure) 3 in the Appendix.
4 CHARACTERIZATION OF ALL LOCAL MINIMA
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 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 minimal representation. This may suggest that minimal neural networks are the right notion to study the complexity of the loss landscape.
4.1 SGD FINDS A NEARLY MINIMAL NEURAL NETWORK
The limit points of SGD almost surely Clarke stationary with respect to La (see, e.g., (Davis et al. 2020; Bolte Pauwels 2019).. ) We show next that any Clarke stationary point w.r.t. the loss (()) is fact a nearly minimal neural network. This shows that SGD finds 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 La over O. nearly minimal neural nelwork. Consequently, any local minimum of Lg is nearly minimal.
As an additional motivation for studying nearly minimal neural networks, we establish the following. Proposition 3. Let f E 9m be any neural network. There exists a continuous path in from to 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 neural network 0 which decreases the training loss: scaling the neural network and then aligning the non-zero neurons which belong to the same cones B; 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 I we immediately obtain the following result.

---

Published as a conference paper at ICLR 2022
Corollary 1. The valley (1) of any neural network 9 contains minimal one. Further, if the valley ((0) is non-spure non-spurious, then contains an optimal neural network which is minimal.
Interestingly, we are able provide an explicit construction of the map from a neural network 0 to nearly minimal representation, and this map is based on the aforementioned transformations (scaling and aligning; see the proof of Proposition] for details).
Hence, the study of the optimality properties of neural network can be narrowed down to the structured class 6 which contains the limit points of SGD. Next, establish that can go further by considering the class of minimal neural networks m....
4.2 CLARKE'S STATIONARY POINT AND SUBSAMPLED CONVEX PROGRAM
Consider the convex program with trichotomies:
2q
min & Σ (((to)-wjtt)) + +33
Σ ||wll2,
s.t. Wy, W544 Qj, E [g).
(12)
The convex program with trichotomies also provides convex optimization formulation of the regularized neural network training problem (
Proposition 4. The convex program (12 with trichotomies has the optimal value P'.
Given a subset I S [4]. we can also consider a subsampled convex program with trichotomies:
min Σ T2 ((yn) w)+a)) + 3 E JEZ
(1ww5l12 + 1(wj-all2), s.t. Wij Wi+a E Qj,jEz EI.
(13)
JEZ
We show the connection of the Clarke's stationary point of the nonconvex loss function La and the optimal solution of the subsampled convex program (13 as follows.
Theorem 3. Suppose that is a Clarke's stationary point of the noncomvex loss function Lg. Let I= (j [4] there exists & E [m]] such that Т ding(sign(Xux)) Then, corresponds global optimum of the subsampled convex program 13
In other words, any local minimum of the nonconvex loss (T] can be characterized as a global minimum of subsampled convex program [3);; further, the optimality gap is equal to the gap between the subsampled problem (13) and the full convex program
4.3 SUBSAMPLED CONVEX PROGRAM AND VERIFYING GLOBAL OPTIMALITY
We established that a stationary point the non-convex training loss is a global optimum subsampled convex program. Here, build on this observation to design procedure check whether a neural network in fact a global minimizer. Our key thcoretical contribution to provide such algorithm that runs in polynomial time of sample size n.
We first note that the set { (D.) 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 = (W W2p) E W of the convex program 4). Note that each constraint wy E C is linear inequality constraint. Indeed, deseribed in Section each C, the convex cone
of solution vectors for dichotomy [-+ of (1.....n) n). Writing X (resp. x-!) the subset of
rows of indexed by L+ (resp. I-), we have u E C, if and only x u 2 0 and x( u I 0. Using these notations, the convex program (4)
can be reformulated as
min
(T)(WW) + 3 Σ wwll1
x w. > O. X m 3 Vi 1,..., 2p,
Wh Wi.... 102p
D, Hence, given feasible point W (wi,.... W2p) convex program it holds that W* is a global minimizer if and only if W satisfies the Karush- Kuhn-Tucker (K (T) conditions (see (Boyd et al. 2004)) of (4). Here, W W satisfies the
where (W)
2p
W2p) E W to the
8

---

Published as a conference paper at ICLR 2022
KKT conditions if, for each ,,..,, 2p, there exist (6) (0)
0 such that 14
(<_)) x = 0 and
X (.VE(T + B W.
+ x
-x(0(() + =0,
if of +
(14)
x XT D.VVE
(0) x <.0) 3
otherwise
(15)
This amounts to solving system with 2np variables of 2np linear inequalities, no convex quadratic inequalities and (2p - (d 2) linear equalities, where ng is the number of variables w equal to 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 neural network is global optimum. Its proof is deferred to Appendix [B88
Proposition 5. Let 0 E @min be a minimal neural network. Suppose that W (0) satisfies the KKT conditions as described above. Then, B(W (0) is global optimum of the loss Lg.
In the above result, the minimal neural network assumption is not restrictive, since any local minima of the loss must be 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 I
5 NON-SPURIOUS VALLEYS AND CONVEX LANDSCAPE
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 critical threshold is n + 1 + m for having a path of non-increasing value. While this may be an open problem. is reasonable expect SGD to behave better in that case, and thus to find a global minimum. For an arbitrary neural network 8 we can find a point 6' with at most n + -1 non-zero neurons such that they connected with path with constant objective values.
Proposition 6. Given scaled neural network O E Om with m 3 n + 1, there exists a neural network 6' with at most n + non-zero neurons and there exists path with constant objective value between 0 and 0', Namely, 0 0' and 0' 0.
direct corollary of Proposition 6 is that for any global optimum H* of Cg. we can find a succinct representation 0* with at most n + 1 non-zero neurons and there exists path between 0- and d 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 Z nl
Proposition 7. Let 2 n + 1 + m². Then, it holds that for any neural network 0 O have 0 0* for some 0" E E
In other words, provided that m > n + m², all strict local minima are global. Compared the standard lower bound m > for the unregularized case in (Venturi et al. 2019 Livni et al. 2014). we have an additional term m² < n ++ 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 aver-parameterized shallow neural network almost convex. Essentially, for sufficiently wide neural network, for any Og 01 and À E [o, 1]. we can find 0x such that ((:0,) = (z; 0o) + (1 - (1-x)f(= (z;(z; 01). From a perspective of convex formulation of two layer neural network, we give sufficient upper bound 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 [x;; 0b) and [(x; 0o), we can find succinct representations 0,, 0g such that 0 0, and 0, fg for i 1,2. Then, for any X E [0, 1], we can construct 0x such that
[(: = (s: 0o) + (1 {>)(;; 02)
(16)
The construction of 0x is straightforward. From Proposition 6 we can take ,, 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 0₂ satisfying (6).

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under grants ECCS-2037304, DMS-2134248, and the Army Research Office.
REFERENCES
Zeyuan Allen Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv:1811.03962 2018.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint 1rXiv:1611.01491 2016.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):6296681, 2017.
Eric B Baum. On the capabilities of multilayer perceptrons. Journal of complexity, 4(3):193-215, 1988.
Yoshua Bengio, Nicolas L Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. In Advances in neural information processing systems, pp.
2006.
Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning, arXiv preprint arXiv:1909.1000 10300, 2019.
Jonathan Borwein and Adrian S Lewis. Convex analysis and nonlinear optimization: theory and examples. Springer Science & Business Media, 2010.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for perrpparameeerized models using optimal transport. In Advances in neural information processing systems, pp. 3036- 3046, 2018.
Frank H Clarke. Generalized gradients and applications. Transactions of the American Mathematical Society, 205:247-262. 1975.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions electronic computers, (3):226-344, 1965.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason Lee. Stochastic subgradient method converges tame functions. Foundations of computational mathematics, 20(1): 2020.
Simon S Du and Jason Lee. the power overmaaraattiizatioon neural networks with quadratic activation. arXiv preprint 1803.0 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv: I 1810.20554 2018.
Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. In International Conference on Artificial Intelligence and Statistics, pp. 4024 4033. PMLR, 2020.
C Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint 10.05.161. 2016.
Benjamin D Haeffele and René Vidal. Global optimality in tensor factorization, deep learning, and beyond. arXiv preprint 1rXiv: 2015.
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 7331-7333 2017.
10

---

Published as a conference paper at ICLR 2022
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and
generalization neural networks. In Advances in neural information processing systems, pp- 8571-8580, 2018.
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in neural information processing systems, pp. 855-863, 2014.
Quynh Nguyen. On connected sublevel sets in deep learning. In International Conference on Machine PMLR, 2019.
Learning, pp.
Quynh Nguyen. On the proof global convergence gradient descent for deep relu networks with linear widths. arXiv preprint arX1v:2101.09//, 2021.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2603-2612. JMLR. org. 2017.
Quynh Nguyen, Pierre Brechet, and Mondelli Marco. When are solutions connected in deep networks?
arXiv preprini arXiv:2102.0900: 2021.
Piyush C Ojha. Enumeration of linear threshold functions from the lattice of hyperplane intersections. IEEE Transactions on Neural Networks, ((4):839-850, 2000.
Mary Phuong and Christoph H Lampert. The inductive bias of relu networks on orthogonally separable data. In International Conference on Learning Representations, 2020.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. arXiv preprint wwXiv:2002.10553 2020.
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John Pauly. Convex regularization behind neural reconstruction. arXiv preprint arXiv:2012.05169, 2020.
Arsalan Sharifnassab, Saber Salehkaleybar, and S Jamaloddin Golestani. Bounds on over- parameterization for guaranteed existence of descent paths in shallow relu networks. In In- ternational Conference on Learning Representations, 2019.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training guarantees for multilayer neural networks. arXiv preprint 11Xiv:660500866/ 2016.
Luca Venturi, Afonso S Bandeira, and Joan Bruna. Spurious valleys in one-hidden-layer neural network optimization landscapes. Journal of Machine Learning Research, 20(133):1-34, 2019.
Rene Vidal, Joan Bruna, Raja Giryes, and Stefano Soatto. Mathematics of deep learning. arXiv preprint arXiv: /71:: /1/../222.77711 2017.
Gang Wang, Georgios B Giannakis, and Jie Chen. Learning relu networks linearly separable data: Algorithm, optimality, and generalization. IEEE Transactions on Signal Processing, 67(9): 2357-2370, 2019.
Huiyuan Wang and Wei Lin. Harmless overparametrizzttoon in two-layer neural networks. arXiv preprint arXiv:2106.0479) 2021.
RO Winder. Partitions of n-space by hyperplanes. SIAM Journal on Applied Mathematics, 14(4): 81 111881 1966.
11

---

Published as a conference paper at ICLR 2022
A FIGURE IN EXAMPLE
We plot the points ag as well as wg in Figure 3
-0.1
PAUTE
optris neurs foo canio peeten
DALTES
-0.5
-0.
-0.1
optirs MAUTT farm CONAD probien
0. 0. -0.
23
00
04
05
00
Figure 3: Plots the neuron space of nerual networks trained by GD over two trials. Points a, of the neural network {(u am trained by GD, and non-zero block w of the global solution of the convex problem. The points ag lie in the convex hull of {0, wi and they satisfy equation (IT) up to numerical tolerance. This implies in particular that the neural network found by GD is optimal.
B PROOFS OF MAIN RESULTS
Thoughout the appendix, we will use the following notations. For W (Wi,..., W2p). we define (W) = E D,Xw, For 0 = (U, where U E Rd and a E R", we define 7(+) En= a (Xu,)o,
B.1 PROOF OF PROPOSITION II
According to the construction of M(0), there is at most one non-zero neuron per cone, and, each
neuron (w, 7) satisties ||w|| = (7), i.c., M(0) is minimal.
Fix cone B. Let (w1, ".)..... (wk, 7k) be the neurons of 0 such that Buu, wx) = B for i 1..... k and let n V hylles
1oslus and 7thh sign(11) v Iw 12 be the merged neuron. Since
nearly minimal, know that w1,...; wi positively colinear.
For E [0, 1). define (t) such that it has neurons associated with the cone B given by
(I( = (1 t) /7/l + tw by
VI((1 t) ww 1i two |y ll2
71 (t) sign (71) (t)ll2
wy w)( v1 L. Wi
(() = vT- f 1:5
where j > 2. Note that for all j > 1. all vectors (t), wj, wtth are positively colinear, that [w,(()) = 17 (4) and that sign(77(1) (1)) sign(71). Further, note that (w)(0), (0)) (w):71) (1)) = (wth m) and for j > 2, (0))(0) (0)
(y), (1), (1) = ().
Consider the neural networks 0(t) with neurons (wy (t), 7, (t) respectively defined for each cone
B. It holds that 0(0) = 0 and 0(1) = M()). Then, the contribution of the neurons in B to the
predictions (((())) are given by
(1w)()));;) sign(7) ((w)(()) + Σ (3(00s()0))
sign(7) (1-t)Xwilna ttx + (1 t)x Σ w 17/7
sign(7) ar (X
12

---

Published as a conference paper at ICLR 2022
Thus, the predictions (((()) constant function of Similarly, we claim that the regularization term R()(t)) is constant as 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 ()
(wy(t)lla))) = Iew (t)l2l(()) +
& = [I(1 t)w, 1u t) 1"" + (1-1)) t)
Σ j=2
Lwy |l2
[I(1 t)
Σ myy myyh + +t
|| |2|>""
where the third equality follows from the triangular equality when all vectors are positively colinear. Thus, we have explicited a continuous path from 0 to M(0) such that C3 is constant along that path.
Now, we show that if M(0) is local minimum then 0 is also a local minimum. We proceed with the converse. Assume that 0 not a local minimum of Lgg For a cone B, let (W1,7),.... 7.)..., (Wk, 7s) be the neurons of 0 such that B(w,, 74) B. Let (w. ynm) be the merged neuron. If 0 is not a local minimum, then there cxists a small perturbation 6 := ((),,))))= of the neurons of 0 such that (i) ((F) < (0). (ii) sign(?))
sign(%)) and (iii) for each i = 1,.-.y m, m, have I+ (xu,s)) S (X(NE() and (x(s)),)) C (x(X)))), where we use the notation (z) = (i [n, 2 > 0} and (z) = EiE (l, n z < 0} for vector R".
Then, we define for / E [0, 1].
(1 ()wf mil + //" |7
(t) VII t)w1 hi + tw 1 l12
(t) = sign(1) 11 1ll1 (t)ll2,
"y wt( = vI - 8. wj..
(t) VI 1
where j >> 2. Let O(t the neural network with neurons (t), (t({) defined as above for each cone B. Then, the contribution of a cone B to the predictions ((((t)) is given by
Σ ((Xu)(t)) sign(m)) ((X((L-t)(il)) tw 1>")) + (1 - t) Σ o (X wf 75l) j=1
Due to the above property (iii), we have that
a(x((1 - ()w hyl +
= -1- (1- "o"
Thus, the contribution of the cone B to the predictions is
&
Σ (xx = (1 - t) Σ +Xow)nftoo(Xi)
Summing over all the cones, we find that
(((()) = (1 10000)
Similarly, the contribution of the cone B to the regularization term R(O(t)) is
(w)())la)s(0)) = (I(1 t)wilif tw ">""" + (1 t)
& (1 - t)
Σ
| (1/11// /r + 121?""
1=1
13

---

Published as a conference paper at ICLR 2022
where the last inequality is due to the triangular inequality. Thus, obtain that R((()) < (1 - () L(M(()))
Hence, we get that (o( & (1 L( Since Cp < Lp(() (s(M)))). we have that Cs(((t)) < (z(M(()) for any < 1. This concludes the proof.
B.2 PROOF OF PROPOSITION
Let O E m, and consider the point W(0), defined in whose expression is given by
W/ (0)
Σ
az/uy
(17)
B(
and such that each non-zero neuron (u,, Q2) contributes only to single u;(().
We prove that the mapping + W()) is well-defined. Each set P. is a cone and (.) is a positive linear combination of elements of P.. It follows that w,(0) E P.. and W W. Further, 0 has m neurons and each neuron (uz contributes only to a single wx((). follows that at most variables among (w)( (0)..... (2) are non-zero, and (()) Wm. Hence, the mapping 0 + W (0) is well-defined from Om to Wm.
We show that (W (0)) (0). We note that
2p
2p
Te (W())) = Σ D;Xw;(0) =
Σ
Σ
DeX(aylug-
1=
B(Hy.ay)CC:
Note that for neuron (u,, az) such that Buu 04)) S Cs we have that D,X aa |uj o(Xu)) aj. It implies that
2p
Te (W = Σ
D.Xlaslus = Σ (Xug)aa 7(0),
j=
B(u, B(u,,,)) CCC
and consequently, ((e((W())) = (()())) On the other hand, we have
2p
Σ
well2
Σ 1= B(a
Laylu
1111,
2
j=1
where the last inequality follows from triangular inequality. Since the neurons (u) scaled, get that Σド= | Σ lay12 2 + ||u, 112. and we finally obtain that (W)())) (.).
We show that the mapping W O(W) is well-defined. Based on the construction ( holds that the non-zero neurons (u, a.) belong to pairwise distinct cones in (B....., B2 Further, the neurons are scaled. Hence, (W) ) is a minimal neural network with m neurons.
We prove that (o(W)) & (W). Denote by DO) the diagonal matrix associated with B(uj, (r))
for 1 E < V., We have that
4+10
148
(((W))) Σ [o(X))
Σ 1=1
D(i Xuylayl Σ D X Σ 1/4
j=1
ieK;
Du) D,Ww, Therefore, we find that ((((W) = F.(WW) and ((T()(W))) = E(Te (W)) On the other hand, we have that
It holds by construction that for each i Kj.
E+
E+e'
Σ 10llllaa
Σ f=1
||ulll
Σ 10
KEK,
j=1 Ke
1=1
where inequality (i) follows from triangular inequality. Hence, obtain that (o(())) & Lz(v).
14

---

Published as a conference paper at ICLR 2022
B.3 PROOF OF THEOREM
First, we show that @ox C Oin Let E o and consider a split version of O. Let (u, a) be neuron of 0, and ([) the neurons of O' which correspond to the split of (u,a).
We have 2j=1 (Xuj)a 2==1 (Xo(a =o(Xuaa because Ej- = 1. Furthermore, l E 1-1 1 + lay1 2 - + lal) = 2 (11ull + lal?), whence (()) = (()))
Consequently, 6xx 6
remains to show that 6 S O Let O E 0i.. Due to the strong convexity of the regularization term and the re-scaling invariance of the term a oXuu)a each neuron (uj,0y) of 0. We partition the neurons of such that the neurons in each partition {(u,, a,)) belong to the same cone C' (in the sense that u E 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 a split. Thus, O. Gev and this concludes the proof.
must have that ||u; ll |ay| for
B.4 PROOF OF THEOREM 2 CLARKE STATIONARY POINTS ARE NEARLY MINIMAL NEURAL NETWORKS
We review the definition of the Clarke subdifferential Clarke 1975) of f. At E Rdd this is defined as
lim (((x)) lim Ia x, Ik E D 10000
Ocf(x) : conv
1-+00
where D: fo e Fd
differentiable z). In particular, it holds that Rd has measure equal to zero Borwein & Lewis (2010) under mild assumptions on f. Then, we say that r e R is Clarke stationary with respect to J 0 fxx).
Let E Om be Clarke stationary, i.e., there exist A(), A(N) 0 and sequences such that Σラ= A = 1, lim ((1) = 0 for each j = 1,..., N, the
] ( (0(N))
loss function C3 is differentiable at each o( and
N
0 0=
1
lim (L
1400
PART 1: THE NEURAL NETWORK 0 MUST BE SCALED.
By contradiction, assume first that the neural network 0 is unscaled, i.e., there exists neuron (u, a) such that ||ul|2 * |a). Write (u aa) the corresponding neuron of each 060 Since limg- (ul (ule)) a ()) (u, a), up to extracting subsequences, we can assume that the neurons (ug), (1) are also unscaled, i.c., || 1|2 # |a
(i) for all k > 1 and j = I.
CASE 1: a #0
Since limn- Og and j = -I..., N. Then, for each j = I,..., N and > and for / E [o, 1), we define the neural
()) (1) a, up to extracting subsequences, we can assume that a + 0 for all k > 1 .
network ((0(()) (t) copy of o(4) except for the neuron (u .ak that replace by
(3)
u (i)
(t) ug
0k (t)
(i) (t) ag 9 Tk
7k (t)
G
(1)
( (t) 1 + t(11 1) and we use the improper notation
where 7k
Th
72 ())
if u = 0. Note that o6 (t) defines continuous path from o(4) = of.) (0) to the scaled neural network o (1). Further, since a is positively homogeneous, holds that for any t E [0, 1].
af (Xuu ()) (1))a ( o )a
15

---

Published as a conference paper at ICLR 2022
so that that the function (3( (1)) is constant function of [0, 1]. On the other hand, the regularization term satisfies
(t) R(
3 (1)
2
(11ug
12
12)
+
B
||
()
12
7
(t)la
12
(t)
:=
((k5)
C(k,
B
|
1
7
.)
(1)a
2
(1)
(t)
independent of
7k
Note that the function
ge (t) Co(0l) (t)) is differentiable, and simple algebra yiclds
(0) B ( (Viluf")n ll2 v vaa
dg dt
(1a6))2 -11uk 1
vlag21
Hence,
dg ()) (0) 3.
V/lulle vla
lim k-
-[a|2 - -1u1112)
di
|a|
Since |a| * |1l|2, follows that lim
(0) On the other hand, we have that
dt
dgb
()
(0)
(0), VL L
dt
di
du ( (x=0)
do 00 (t=0)
Simple algebra yields that limooo
14
u and lim
(V |للس Tol - -1) Thus, the limit do = lim
( de
(0) is constant (independent of the index
1) and
lim k
dg (0)
= d0,
N
(
lim VL (o( koo
di
j=1
0
0.
This is contradiction with the fact that Σx= and a f 0, we must have that ||u||2 = aa].
N
(
lim
dg dt (0)
Therefore, in the case u +
CASE 2: u *
The proof proceeds exactly in the same way, except that we define
① (t)
(3)
(1)())
a
u
ux
ag
% (t)
(7)
where -())
7
7
())) = 1 t(7 (0)
1) and we use the convention = if
Ok
(
O.
PART 2: NON-ZERO NEURONS WHICH SHARE THE SAME ACTIVATION CONE ARE POSITIVELY COLINEAR
According to the first part of the proof, we can assume that the neural network 0 is scaled.
16

---

Published as a conference paper at ICLR 2022
(SPECIAL CASE) THE NEURAL NETWORK 8 IS A DIFFERENTIABLE POINT OF Lg.
In order to provide some intuition about the proof, let assume first that Lg is differentiable 0.
By contradiction, we suppose that there exist two non-zero neurons (u, a) and (u, 9) such that B(u, o:) (v, (), and, u and are not positively colinear. Further, let us assume that a, 3 (the case a, B < 0 follows the same lines).
Define w au + Bu. Note that w has the same sign pattern and v. Fort t [0, 1], we set
1
m(t) = (1 t)wm
2
E(t) = (1 t)
+
2 w
((t) = i(t)
a(t) = (lū(())22,
Vilū(t)ll2
T())
(t) Vioo(t)ll2
B(1) V VI[((1)l2
Note that ((u(t), at)) = Buu, a) = (u, 3) (u(t)), (())). Further, we define 0(t) copy of
where we replace the two neurons (u, a)) and (v, B3 by (u((), (()) and (())).(())). Note that ((t)
defines a continuous path in O., starting at O
Then, introduce the two functions
g(t) ((((O(t)))
h(t) R(O(t)),
so that (=(()()) = g(() + 3- M()). First, we claim that g(l) is constant over [0, 1]. Indeed, this
follows from the fact
o(Xu(t))a(t) + (Xx(())))
(((((t)++ (X))) (Xuua
=au+3v where the first equality comes from the fact that B(u(I),a(1)) B(v(1),8(1) Hence, we have ((((1)) = (0) and g() constant.
On the other hand, the function h(t) is clearly differentiable, and simple algebra yields that dh(O) dt
|oull2 ||Sull2 + 2 (aa))(()))
1 (Bv) Tauul22 +
2
11300112
Since u and v are not colinear, holds by Cauchy- Schwarz inequality that (ac) (Bo) < || and thus,
dh(0)
|aau|2
|0v||2 ||au [au]|2||,@01
(TauL))
0,
Taul|2
1,Bull2)
that is, dh(O) 0. Thus, we finally obtain that (CC(((())
O, which contradicts the stationarity of
de
(GENERAL CASE) THE NEURAL NETWORK IS NOT NECESSARILY A DIFFERENTIABLE POINT OF
Lg.
Now, let us generalize the above proof to the case where La not necessarily differentiable at 0.
For vector RR, we use the notations (=) = {i E (1.....n) n) 0). In(z)
(1....,m) 2; = 0} and (z) = {i E (1....,.n n) 2, < 0}.
Since 0 a Clarke stationary point of C,,, we know that there exist (1) ( > and sequences (0(2) ..,.... ( ha such that ビ,,100 1, lime-+x of for each 1, 1,... N, the loss function C. is differentiable at each o(6) and
N
Σ
X0 lim (L)((())
4000
j=1
17

---

Published as a conference paper at ICLR 2022
For each & > 1 and I....,,, N, up to extracting subsequences, ( (3) P # O, and, a% and {() have the same sign (let us say positive). Further, up extracting subsequences again, (resp. I+ (Xxb)) and 1- (Xxx remain constant (independent of k). Since the sign patterns of Xu and Xe are equal by assumption, and, since lim ub( u and lim 2 v, it follows that (Xuu) = (Xv) C (X (2) n 1 (Xu 1
assume that
"k ag
assume that the sign patterns (Xu and (X )
(18)
and
L(Xx)=I((X)) C (1-(xx²) n (X
(19)
We denote (u) and (v) the diagonal matrices (as introduced in Section 2 which correspond to the sign patterns of ()) and u/ and which are independent of & by assumption. Then, using (18 and (9).. it follows that
(w) = T
(u) = (b)))
(20)
The above equalities will be crucial later on in our analysis.
Then, for each neural network ()) we can construct similar path o5 (t) as in the differentiable & (i) (i)
case, that is, we set w = ag u
+ alt) o and
(1) (t) (1 f)ou (1) (5) "
2 wk
0 (t) (1 t)o(()
(1)
l ()) ()
-
2 wk
(1)
" (1)= /im6 (1)l2
(() / (1)l,,
ag
(t)
& (t)
(t) :-
15 (t)ll2
VI (0)l2
Similarly to the differentiable case, also define the functions
ge (1) ( (1)), (1) (t) = R(O( (t))
dgk2) (0)
First, we claim that limp-ooo
0. Indeed, we have
dt
dg ( (0)
(w) - -2)),, ve(TOo()))
dt
Taking the limit + 0o, we obtain that
(0) 1 1 - -o- v),())))))))
lim
k+00
2
Using (00 we get that (T (T)( - u) 0, and consequently, the claimed equality
(0)
limp-+00
de 0.
On the other hand, the function (1) is clearly differentiable, and simple algebra yields that
lim an (0) | ||Bu||2 + (a()) (au) ||aul2 11,0o12
1
df
2
Since u and v are not colinear, holds by Cauchy-Schwar inequality that (on) (Bo) < || and thus,
(0) k0000 dt
||oau|2 || + ||ou| 100l21
T (1o + 11501122
lim
0,
2
18

---

Published as a conference paper at ICLR 2022
dn ( (0)
that is, limg-+oo
O. Thus, we finally obtain that
d (0))
lim
< 0,
dt
and further, that
N
dCa(0 <0.
A
lim
10000
dt
However, it holds that
dC (0))
de
lim
lim
100
dt
t00
dt
do(2)
It is immediate to that d0 limkoo
does not depend the index that
(C (0)) (d0,
Σ x lim
lim (L)()
k-000
5000
==1
That is,
we obtained both that
This concludes the proof Σn= A lim
dC (C22 (0)
and
di
Σj= A limg-
dC (o) O, which is contradiction. that f must be a nearly minimal neural network.
de
B.5 PROOF OF PROPOSITION 3 REDUCTION TO NEARLY MINIMAL NEURAL NETWORKS ALONG A PATH OF DECREASING OBJECTIVE VALUE
We consider reductions similar to those in the proof of Theorem in order to construct a path 0(t) E 4m for E [0, 1] such that ((0) = 0, ((1) E @min and (0(t)) strictly decreasing. Naturally, we assume that 0 is not nearly minimal, otherwise, there is nothing to show.
PART 1: THE NEURAL NETWORK 0 IS UNSCALED.
We claim that there exists a path (()) E Om for [0, 1] such that 0(0) = 0(1) scaled and Co Cp (B(t)) is strictly decreasing.
Suppose that the neural network is unscaled (if not, go directly to Part 2). Then, for each neuron (u, a) of 0 such that ||u]|2 * |a], define
Vial- if u. + 0,
n(t)
((0)
0
otherwise,
a(t) = (1))) if a + 0,
0 otherwise,
where (t) V/al + t(V||ulla Vaa)). Simple algebra yields that (u(0),a(0)) (u, and [lx(1)]l2 = / /|||u| = (a(1),, so that ((0) = A and ((1) scaled. By positive homogeneity of a, we have that a (Xu(t))a(t) o a(Xuaa which further implies that ((((t) = ((0) and L()(O(t)) constant as a function t.
We claim that the regularization term R(((L)) is strictly decreasing as function of L. Indeed, it holds that
|a| 7((()
2²(t) |1012 + [a lap2.
[[u(1) + (1))22
The minimizer of the function 7 E R ||] ||| 2 |a/2 is given by 7" / V/lul2. which is also
equal to 7(1), and the minimal value the latter function is given by 2||u||z|a|, which is strictly smaller than |/u]|2 + |a|2 since ||u]|2 # la|. Thus, the function t + R(((t)) is minimized at and ())) < R(0). Lastly, observe that + R(((t)) is a convex function, which implies that must be strictly decreasing [0, 1). This concludes the first part of the proof.
19

---

Published as a conference paper at ICLR 2022
PART 2: THE NEURAL NETWORK A SCALED BUT NOT NEARLY MINIMAL.
If the neural network 0 is scaled but not nearly minimal, we claim that there exists continuous path (() for [0, 1] such that ( 0, ((1) is nearly minimal, and L,(((()) is strictly decreasing.
For each cone E { [Bi..... ), we consider the non-zero neurons UB : {(u, a)} of such that Buu, a) B. By assumption, there exists least one cone B such that Ug has more than two elements which are not positively colinear. Then, for each cone B, we set w = L(,,)eets |alu, and, for each (u, a) Ug and for t [0, 1].
t
ū(t) (1 - --t)la/u+ +
W,
UB
ū(t)
(t) sign(a)
/|
(t)) sign(a) [ī(()]l2
where [MB] the cardinality of the Ug. Note that B(u(t), a(t) B(u, B, and each neuron (u(t), a(t)) is scaled. Further, we define #(t) the neural network with neurons (u(t), (t)). holds that (t) defines a continuous path in O. starting
and ending a nearly minimal neural
network. Then, we introduce the two function g(() ((T()(()) and h(() = R(((()), so that La (0(1) = g(I) + 3. lu()). First, we claim that g() is constant over [0, 1]. Indeed, this comes from the fact that for each cone B,
Σ
((u(t))a(() = sign(a) o(x.
Σ la(t)l((t)
(u,a)EUn
(u,a)EUa
= sign(a) ((Xw)
Σ o(Xu)a.
(u,a)EElp
The first (resp. third) equality holds from the fact that the neurons (u(t), a()) (resp. o)) have the same active cone B. Thus, (((()) = (0) and g(t) is indeed constant.
On the other hand, we claim that the function h(t) is strictly decreasing. Indeed, observe first that
8 Σ
h(1)
Σ
(1((1 + la(1))?
2
(u,a)
B
Σ
|u(O)lala())
(u,a)EUe
Σ
Σ |((())l2
(u,a)Elle
where the second equality holds since the neurons (u(t), at))) are scaled. Thus, is immediate to verify that the function h is differentiable, and
1((t) =
Σ Σ B (u,a)Eun
[ū(t)l2 (t-11(z)) w Jalul12 + lalu
uull - la/w)) -lal))
Clearly, (1()) is strictly increasing (since there exists, by assumption, at least one cone B and x
neuron (u, a: E UB such that [nal * |a/u). Therefore, it suffices to verify that h1(1) < 0. Simple algebra yields actually that h N((1) = 0, which concludes the proof.
B.6 PROOF OF PROPOSITION 4
The proof with trichotomies almost identical to the proof of dichotomies Pilanci & Ergen (2020):
Sahiner et al. 2020).. We start with the dual representation of p
P = max Er (A), s.t. max w1ll
(X7
20

---

Published as a conference paper at ICLR 2022
Here (A) max, a {(e)} is the Fenchel conjugate function of E. We note that the single- sided dual constraint has an equivalent formulation using trichotomies:
x²(Xw)+
max 11
X XT)
max eElyl
max 2
Similarly, the other side of the dual constraint can be formulated as
-X"(
max
XTT))+
max RElo] w.
max
Therefore, we can rewrite p as
P' max (A),
s.t.
max
X (TTz) < 3,i [g],
w:ll 1,
X (T;)4+X(-w) < 3,j E lg).
max
w:l|
For simplicity, we denote Tz+4 = T for j E [g]. We now formulate the Lagrangian
4
D max min #30
min my [Q
(*)A) + Σ 1, x
4544 EQgi 12
Pj+g - -3 (Z)))x
j=1
By Sion's minimax theorem, we can switch the max and min, and then minimize over A. Following this, we obtain
2g
pa min 20
min my ey 1is
Σ (Ti) X P5+0
+ Vj.
Σ
My E 1u.ll
5=1
By rescaling the variable wy = Vy we can reformulate p as
29 Σ
P min 2030
min
Σ (T,)+X(13 -wsto)
+ Uj-
1=1
Minimizing with respect yields
2q
p = min
- (sto
+ 3
|w
wy Wyy EQ,
J=1
This completes the proof.
B.7 PROOF OF THEOREM
According Proposition
D and
can assume that 0 is a minimal neural network. Denote From the definition of Clarke's stationary point, for j [m] with
= Ve C (Xug)+a;
Uy # O, we have
m
- Bu, E E
Σ
[(uu))+a3
(21)
- = XT (Xu;)++
21

---

Published as a conference paper at ICLR 2022
The first line in 21 is equivalent to that there exists 6y E [0, 11 such that
-Bu; = a X {ddiag(,))))
(22)
Here Dj diag(L(Xuu) uj > 0)) and S diag (Il (uj 0)). As uy and aj + 0, this implies that
3 " jj
= xT x Sydiag(b))
(23)
For the second line in 21) we can also rewrite as
Baz =X
=u =uā DĄA
=uf (XT DjA X Sddagg00)))
(24)
u- 3
Therefore, have ||uy ll2 layl and
x DT S" (aiag(,))2]] =1
(25)
For the subsampled convex program ((i) = and g(t) such that
13 the KKT conditions are given by: for E I, there exists
((T()++++ +TÇ0 + ()) +
+B
Wi 0,
if ws # 0,
1e 12
(T(()) + +
< <3,
W; 0,
(26)
x'(-(T)-++TC + +
+.8
Witg
0,
if w # 0,
11i+tll22
X*'((0T)+ + + /// &
if Wi+g 0.
Here S; is a diagonal matrix satisfying that (S:) = if E to and (S:);² = 0 j E I. U I_, where (4+, Jo }-} is the i-th trichotomy. The vector X E INN is defined as wi+g))- As is a minimal neural network, there exists bijective map-
== V= (T) ping between non-zero neurons a;) and E I. For i E I, suppose that T; (sigg( (sign(Xu;)) If ay > 0, we let
w, = Uj. Wit9 = O,
otherwise, let
w; = O, Witg = -K,
As the mapping between non-zero neurons (uz, and E I is bijective, we note that Ejn Xuu)+4j = Eier X Di(w; witg). This implies that X = Å. On the other hand, by taking (6) g()) diag(5,) ) ((i+a) 0, ((40)) (5 )² as D, = (Ti)+ and 5, S, the KKT conditions (26) are satisfied. Therefore, W {w,, witg Σ} is global optimum of the subsampled convex program [1).
B.8 PROOF OF PROPOSITION
Let Ø E O., be minimal neural network, and suppose that W (() satisfies the KKT conditions of the
optimization problem 4 Since the latter is convex optimization problem, it follows that W (0) is global minimum. From Proposition follows that (((W((()) = p and (() global minimizer of Lg. which yields the claimed result.
2 we have that P & (g()(W(())) < (g = P = P
22

---

Published as a conference paper at ICLR 2022
B.9 PROOF OF PROPOSITION 6
Without loss of generality, we can assume that is scaled. Otherwise, we know from the proof of Proposition that 0 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 I Denote the neurons of by (ui,a)),... (Um, am). We have that 7(0) = Σ A Ri. where 2o =
sign(a;) (a;; (E)= Iu5Ilaa]Do X w.ll and 7; Σイ w.lllod
|l, Thus, x(0) Conv(21..... 2m
From Lemma 3 we know that there exist i1,..., f and A1,..., An+1 2 0 such that 2j=1 X3- = 1
and (00) Σ A Plugging-in the expressions of the Zi,, it follows that
) oxx [x
7(0) = Σ A sign(ar,)
Σ | |
Mig |uu,
|
Σ ai or (Xūs,))
where
F/y : 1u. k=1 [ulllaxl);
Ui ||as, || Wiy:
01 sign(ar,) |0:;
Further, we have that
a+1
n+1
m
T ||:
||
Σ j=1
Ug
Mig
uu [xll)ade)=
Σ |ulllaal,
where the last equality follows from the fact that ΣØ x3- = Setting the neural network with
neurons (ūi, ās,)) for j = 1,...,,7 n + and (ūg ā.) = (0, 0) for E {1..... fii..... b4t1).
obtain that 0 E o. and (0) & (0))
Now, we define a continuous path between and as follows. For E [0, 11. I,..., n + 1 and i {I...., m) \ (i....., we set
ui (t) = (1- t)us, las,, + tū,,,,,,
VI[(1- - ()ue, locs,1 + Ui, (0.,
a, (t) sign(a:,,) Ilus, (t)ll
m((1) = v1 - I
(t()) vI 1tta
and (tt the neural network with neurons
Note that 0(t) is scaled, and
n+1
(t)(laaa =
Σ
(111 tau + tū, lā |ll
Σ
(1 - t) /slllad
1=1
m+1
a+1
n+1
1)
Jasy 11 + (1-1)
Σ
|allllas| +
|||u;,]]
3=1
El.... 1447
1=1
(1 ())
(4)
R(O),
(14)
23

---

Published as a conference paper at ICLR 2022
where equality (i) follows from the triangular inequality and the fact that ūh and u; are positively colinear; equality (ii) follows from the fact that and are scaled; equality (iii) holds since R(0) R(0). Thus, the function 1 - R()(()) is constant over [0, 1].
On the other hand, we have
a+1
T((()) = Σ o (x((1 -I)us, laa, + + Uūg ( sign(ar;)) + (1--)
Σ
o(uusao
j=1
n+1
n+
(1 t)
σ (Xuu Jai, +t Σ
oXiit Jāi, + (1--t)
E
o(Kuja
==1
j=1
-+1
(1 t) 000 +g
((0),
(68)
where equality (i) holds since the wa, and ūig positively colinear and the oú, and 0iş have same signs; equality (ii) holds since ((0) = ((0). Consequently, the function t - (e(())) is constant over [0, 1J. and this concludes the proof of the fact that 0
B.10 PROOF OF PROPOSITION
First, according to Proposition 6 given E Om with m > n + 1+ m"" there exists a neural network with at most n + non-zero neurons such that (g < Cz()).
According to Lemma there exists l ((u),0))) = optimal neural network with most m" non-zero neurons. Up to permutation of the zero neurons and those of 8*, since m 3 n- 1 mmm, can assume without loss of generality that (uf, af) (0, 0) for m 1...., m and (ū,, a;) = () for = 1,...,m"" m..
Now, we define continuous path between 0 and 0 For i = 1..... mn and j = m + 1, m, we set the neural network (()) E On,, with neurons
(1) vl u
(t) = Vtag
u (f) v1 - -tūjj
ay(t) vI vi-tāj.
Clearly, we have 8(0) Ø and ((1) 8" Further, f(t) scaled and is easily verified that
R(0(t)) t R(0*) + (1-t) R(Ø). ((((t)) t0(0) + (1-
This immediately implies that the function t + (O((t) is convex over [0, 1]. Since it achieves minimum at follows that it is non non-increasing, and this concludes the proof of Proposition 7
C PROOFS OF INTERMEDIATE RESULTS
C. PROOF OF LEMMA
Proof. It holds that o (Xusja ( o ((uuj)o:) ( D.Xwx)) On the other hand, we have ||wi,|12 122 ||u, [2]l12/a51 Note that |/u = |ayl and thus, || lulllalay (11u,113 layl?). Consequently, (s(() L3c(w").
EiEz D,Xw;, whence
From Pilanci & Ergen (2020), know that p P Hence, L=(() P'
24

---

Published as a conference paper at ICLR 2022
C.2 PROOF OF LEMMA
We aim to show that m² < T. + 1 and P for any m 2 m². We leverage the following result which known as Caratheodory's theorem.
Lemma 3. Let 21. 21...., 2m E R Suppose that y Conv {21 ....... 2m Then, there exist indices 2 1 E {1.....m} m such that y E Conv (2nv(2 ........ Zinti..
Suppose that is an optimal neural network with m 7 n + neurons, and denote its neurons by (u1,a1),.... (um, am)- We have that ((0) = E d 2i, where 2i = Mi mill) and X 2 w.lllo. ||ylllos! Thus, 7(0) E Conv }m
sign(as) (Ey=)
)== |myll |uglllay])o
From Lemma 3 know that there exist i,, B1,..., ,, and A ....... An+1 1 2 0 such that 2Ø=1 X3 1
and (70) 25=1 Aizi. Plugging-in the expressions of the Zi,, it follows that
110 = Σ
A sign( oi )
Muslllas
X
Wig
|uus
j=1
a+1
Σ j=1
āis (Xūi,))
where
Vj = A,
Mi j= [|u,][las|)
m
Ui | Miy
āi = sign(ai,) [1
Further, we have that
n+1
aa Ur = Σ Dy Ut, || =
lxxl) =
Σ k=1
|uillax),
1=1
1=1
where the last equality follows from the fact that ΣØ=1 Aj-
We define the neural network 8 with neurons (ūs, C. We have that 0 E On+1 and P & Co (0) = (0) = P Since Pa+1 e P for any m / n + 1, it follows from the previous set of inequalities that L. (0) Pū+1 P and this holds for any and (6) = P
1. Therefore, P P*
We set W = W (0). We know from Proposition that ( Wn41 and CW) & Cg(0). Hence, P: & Pa. We also know that (o(W) < CW(W.. This implies that P = P and W is an optimal solution to 4 Consequently, m n
remains show that for any m > m", we have P P This follows again from Proposition Indeed, let W be an optimal solution to { such that W E -.. Set 0* = O(o"). We know that 0 E O,,,, and (s((") < L (W*) P Pt. Hence, achieves D and this implies that for any m 2 m we have P pt
D VERIFICATION OF THE OPTIMAL SET
We review standard method to determine whether a convex optimization problem has unique solution. Consider a convex optimization problem
min f(x), s.t. fa(x) < 0, E [m],
(27)
in the variable x E Rdd Here f and f. for E [m]] are convex functions. Suppose that we calculate optimal solution x² and the corresponding optimal value f We can determine whether x" is the
25

---

Published as a conference paper at ICLR 2022
unique optimal solution of (7 as follows. For j [d]. consider the following convex optimization problems
min Ty, s.t. f((x) < 0, E [m]. f(x) f
(28)
Pj ub max Jj, s.t. f(()) < 0, i [m], f(x) <
(29)
These problems give the upper bound and the lower bound of the value of the i-th index in the optimal of (27). Suppose that pbb p/ for certain small e 0, for instance, 10 Then, the
radius of the optimal set with respect to the loe norm is upper-bounded by Therefore, we can be
confident that x* is the unique optimal solution up numerical tolerance.
We have verified numerically that the convex optimization problem in Example in section 3. has unique optimal solution.
26


Reviews:
[{"review_id": "fDbiD8q760i", "reviewer": "Reviewer_P5NY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nInteresting observations about and practical ways for constructing the optimal neural network set from the solution of the convex cone program.\n\nThe paper is mostly well-written and organized, and technically precise. \n\nThe analysis is mostly clean and easy to follow, which may be of interest for addressing related sets of nonconvex problems. \n\nWeaknesses:\n\nThe (or similar) regularized convex formulation has been studied in previous works, see e.g., Pilanci & Ergen (2020), Ergen & Pilanci (2021) among several recent others by Pilanci et al. Though a more-in-dept analysis as well as theoretical observations are provided, how technically novel and practical useful of these results shall be further compared and elaborated. \n\nErgen, Tolga, and Pilanci, Mert. \"Convex geometry of two-layer ReLU networks\", 2021.\n\nA number of related efforts dealing with learning two-layer ReLU networks by analyzing or modifying the landscape through introducing regularization terms are missing in the discussion; see e.g., Wang et al, 2019. Learning ReLU networks on linearly separable data: Algorithm, optimality, and generalization. \nMoreocver, the contributions can be considerably enhanced by providing experimental validations across different tasks such as regression, or classification tasks. \n\nOne of the key difficulties in deep learning theory is that learning of deep neural networks is nonconvex due to their compositional structure. How would the results extend to deep neural networks?\n\n\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "The paper contains some typos and grammar errors. \n\nin (1), the second summand should be m terms instead of d terms?\n\nI do not understand why the positive homogeneity of the ReLU activation function directly leads to σ(Xui)αi = σ(Xwi), as \\alpha_i's is not necessarily positive in general?\n\nThe paragraphs regarding the partions of D_i's are not easy to understand, which shall be improved. \n\n\n----------------------------------------------------\nAfter rebuttal: I have read the other reviews and authors' replies. My minor issues were addressed. I will keep my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZKryGI2DMD7", "reviewer": "Reviewer_VYzk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths.\nI find the results to be novel extensions of of Pilanci and Ergen from 2020 and important theoretically: characterization of the global and local optimum points of the objective function.\n\nWeaknesses.\nThe paper only considers a single-hidden later. Can this analysis method be extended to multiple layers? \n\n\nSeveral typos and corrections I found:\n- The upper bound in the rightmost summation in equation (1) should be 'm' not 'd'.\n- Page 1, penultimate line,  no definition for $C_i$ for $i\\in[p+1, 2p]$ is given.\n- Page 3, Section 1.3, first paragraph, third line:\n  - Fix the mismatching brace. \n  - I believe the $\\sigma$ should be dropped.\n  - The $1(Xu\\geq0)=s$ seems to be a slightly different definition of the cone corresponding to $s$ than the original definition in page 1. Namely, the entries of $Xu$ corresponding to $0$'s in $s$ are required to be negative in this definition and nonpositive in the definition in page 1.\n- In equation (5), B(u_j, \\alpha_j) has vectors with $d+1$ entries (the last entry comes from $R_{>0}$ or $R_{<0}$ from the definition of  $B_i$) and $C_i$ has vectors with $d$ entries, so the containment under the summation doesn't make much sense here.\n\n\n\n", "summary_of_the_paper": "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:\n\n1. 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. \n2. 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\".\n3. 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.\n4. It gives a polynomial time algorithm for checking whether a stationary point is a global optimum.\n", "summary_of_the_review": "See above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UHHFi-ey4t6", "reviewer": "Reviewer_DhNM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths of the paper:\n- The authors provide a complete characterization of the global minima to the nonconvex 2-layer ReLU network training problem, in terms of the solutions of a convex program\n- The approach does not rely on duality and/or lifting perspectives of previous convex perspectives on neural network training\n- The approach provides an algorithm for testing optimality of a neural network in the studied context\n- The work provides significant extensions of the work upon which it is based\n\nWeak points of the paper:\n- The method only applies to 2-layer neural networks with ReLU activation and weigh decay.    It is a great contribution that may inspire further developments to weaken these assumptions.\n\nQuestions for authors:\n\nOne of the technical themes of the paper is the idea of minimal / nearly minimal networks.  Several of the theorems are stated explicitly in terms of nearly minimal networks.  Is it necessary to have minimality in the theorem statements?  That is, could the primary claims be stated without reference to minimality (and where minimality would be a technical detail in the proofs)?\n\n\nAdditional feedback with the aim to improve the paper:\n\nIn the model there are no bias terms.  I presume this is because they can be tucked into X with a row of 1's.  Perhaps this is worth a comment in the paper.\n\nTypo: Sec 1.3 \"neruons\"\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "Clear accept.  It significantly clarifies the relationship of the solutions of the nonconvex ReLU neural network training problem with a corresponding convex program.  That relationship allows them characterize all global minima and to test whether particular networks are indeed global minima.  While the work only applies in the 2-layer case, it is nonetheless a significant theoretical extension that can inspire extensions to multi-layer cases.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RyapASf-dR1", "reviewer": "Reviewer_FbD2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "First of all I have to say this is a very interesting theoretical paper and is the best  among all submissions I have reviewed in ICLR 2022. This paper reveals an interesting hidden convexity structure in  two-layer ReLU neural networks by mapping minimal neural networks to a convex optimization problem and vice versa. The construction of the mapping is clean and elegant. The idea of connecting non-convex loss landscape with convex optimization can potentially be further explored to explain the success of deep learning.  This paper is strong enough and I do not see much weaknesses. But I left to the authors few minor comments which  can be seen as future considerations.\n\n- The first comment that comes to my mind is how the results obtained in the paper can be generalized to neural networks with other activation functions. It seems that the positive homogeneity of ReLU is the key to derive the convex programming problem. Can the authors comment on whether (and how) it is possible to establish similar results for smoother activation functios, e.g. $\\text{ReLU}^{k} $ or Sigmoid?\n\n- Can the authors comment on whether and how the results can be extended to deep ReLU neural networks? \n\nSome relevant references are missing.\n\n- Huiyuan Wang, Wei Lin, Harmless Overparametrization in Two-layer Neural Networks, arXiv:2106.04795.\n\n- Quynh Nguyen, On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths, arXiv:2101.09612. \n\n- Quynh Nguyen, Pierre Brechet, Marco Mondelli, When Are Solutions Connected in Deep Networks?, arXiv:2102.09671.\n \n", "summary_of_the_paper": "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\nnetworks that can be merged to a minimal representation. Lastly, they provide an explicit path of non-increasing\nloss 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.", "summary_of_the_review": "This paper provides novel tools and insights in revealing the convexity structure of non-convex loss landscape of two-layer neural networks. The ideas developed here can be used to explain the global convergence of gradient descent algorithm in training neural networks. I recommend accepting the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: A conceptually and technically highly innovative paper which reinforces an existing powerful connection between the critical set of two-layer ReLU networks and suitable convex programs with cone constraints. The reviewers are in strong consensus that the paper is sound and has merits for publication.
Decision: Accept (Oral)