Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape
Authors: Kedar Karhadkar
Michael Murray
Hanna Tseran
Guido Montufar
Venue: Accepted by TMLR ()

Abstract: We study the loss landscape of both shallow and deep, mildly overparameterized ReLU neural networks on a generic finite input dataset for the squared error loss. We show both by count and volume that most activation patterns correspond to parameter regions with no bad local minima. Furthermore, for one-dimensional input data, we show most activation regions realizable by the network contain a high dimensional set of global minima and no bad local minima. We experimentally confirm these results by finding a phase transition from most regions having full rank Jacobian to many regions having deficient rank depending on the amount of overparameterization.

Published in Transactions on Machine Learning Research (06/2024)
Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape
Kedar Karhadkar
karhadkar@mathh ucla. edu
University of Colifornia, Los Angeles
Michael Murray
mmurray@matth. ucla. edu
University of California, Los Angeles
Hanna Tseran
hanna. tseran@gmatl com
University of Tokyo
Guido Montúfar
montufar@ma th, uc la. edu
University of California, Los Angeles
Max Planck Institute for Mathematics in the Sciences
Reviewed on OpenReview: https: // openreview. net/ forum? id- I0WARaIuFa
Abstract
We study the loss landscape of both shallow and deep, mildly overparameterized ReLU neural networks by count and volume that most activation patterns correspond to parameter regions with no bad local minima. Furthermore, for one-dimensional input data, we show most activation regions realizable by the network contain a high dimensional set global minima and no bad local minima. We experimentally confirm these results by finding a phase transition from most regions having full rank Jacobian to many regions having deficient rank depending on the amount of overparamelerization..
generic finite imput dataset for the squared error loss. We show both
1 Introduction
The optimization landscape of neural networks has been a topic of enormous interest over the years. A particularly puzzling question is why bad local minima do not seem to a problem for training. In this context, an important observation is that overparameterization can yield more benevolent optimization landscape. While this type of observation can be traced back at least to the works of Poston et al. (1991); Gori & Tesi (1992), it has increasingly become focus of investigation in recent years. In this article we follow this line of work and describe the optimization landscape of moderately overparameterizel ReLU network with a view on the different activation regions of the parameter space.
Before going into the details our results we first provide some context. The existence of non-globa local minima has been documented numerous works. This the case even for networks without hidden units (Sontag & Sussmann 1989) and single units (Auer al.) 1995). For shallow networks, Fukumizu & Amari (2000) showed how local minima. and plateaus arise from the hierarchical structure of the model for general types of targets, loss functions and activation functions. Other works have also constructed concrete examples of non-global local minima for several architectures (Swirszez et al. 2017). While these works considered finite datasets, Safran & Shamir (2018) observed that spurious minima are also common for the student-tena teacher population loss of a lwo-layer ReLU network with unit output weights. In fact, for ReLU networks Yun et al. (2019b); Goldblum et al. (2020) show that linear models cannot perfectly fit the data, one can construct local minima that are not global. He al. (2020) shows the existence of spurious minima for arbitrary piecewise linear (non-linear) activations and arbitrary continuously differentiable loss functions.

---

Published in Transactions on Machine Learning Research (06/2024)
A number of works suggest overparameterized networks have more benevolent optimization landscape than underparameterized ones. For instance, Soudry & Carmon (0166) show for mildly overparameterized networks with leaky ReLUs that for almost every dataset every differentiable local minimum of the squared error training loss is a zero-loss global minimum, provided a certain type of dropout noise is used. In addition, for the case of one hidden layer they show this is the case whenever the number of weights in the first. layer matches the number of training samples, dod1 2 n. In another work, /aafran & Shamir (2016) used a computer aided approach to study the existence of spurious local minima, arriving at the key finding that when the student and teacher networks are equal in width spurious local minima are commonly encountered. However, under only mild overparancterization, no spurious local minima were identified, implying again that vverparameterization leads to a more benign loss landscape. In the work of Tian (0017), the student and teacher nerwsrks are assumed to be equal in width and it is shown that if the dimension of the data is sufficiently large relative to the width, then the critical points lying outside the span of the ground truth weight vectors of the teacher network form manifolds. Another related line of works studies the connectivity of sublevel sets (Nguyen 2019) and bounds on the overparameterization that ensures existence of descent. paths (Sharifnassab et al. 2020).
The key objects in our investigation will be the rank of the Jacobian of the paramctrization map over a finite input dataset, and the combinatorics of the corresponding subdivision of parameter space into pieces where the loss is differentiable. The Jacobian map captures the local dependency of the functions represented over the dataset on their parameters. The notion of connecting parameters and functions is prevalent in old and new studies of neural networks: for instance, in discussions of parameter symmetries (Chen et al. 1993), functional equivalence (Phuong & Lampert 2020). functional dimension (Grigshy et al.] 2022). the question of when ReLU network is universal approximator over finite input datasct (Yun et al. 2019a ; as well as in studies involving the neural langent. kernel (Jacol et al. 2018).
We highlight a few works that take a geometric or combinatorial perspective to discuss the optimization land- scape. Using dimension counting arguments, Cooper (2021) showed that, under suitable overparamctorization and smoothness assumptions, the set of vero-training loss parameters has the expected codimension, equal to the number of training data points. In the case of ReLU networks, [aurent & von Brecht (2018) used the piecewise multilincar structure of the parametorization map to describe the location of the minimizers of the hinge loss. Further, for piecewise linear activation functions Zhou & Liang] (2018) partition the parameter space into cones corresponding to different activation patterns of the network to show that, while linear networks have no spurious minima, shallow ReLU networks do. In similar vein, Liu (2021) study one hidden layer ReLU networks and show for a convex loss that differentiable local minima in an activation region are global minima within the region, as well as providing conditions for the existence of differentiable local minima, saddles and non differentiable local minima. Considering the parameter symmetries, [Simsek et al. (2021) show that the level of overparameeeerization changes the relative number of subspaces that make up the set of global minima. As a result, overparameterizztiion implies a larger set of global minima relative to the set of critical points, and underparameterization the reverse. Wang et al. (2022) studied the optimization landscape in two-layer RcLU networks and showed that all optimal solutions of the non-convex loss can be found via the optimal solutions of a convex program.
1.1 Contributions
For both shallow and deep neural networks we show most linear regions of parameter space have no bad local minima and often contain a high-dimensional space of global minima. We examine the loss landscape for various scalings of the input dimension do, hidden dimensions di, and number of data points
Theorem 5 shows for two-layer networks that if dodı 2 n and d, = R(log( ( )), then all activation regions, except for a fraction of size at most e, have no bad local minima. We establish this by studying the rank of the Jacobian with respect to the parameters. By appealing to results from random matrix theory on binary matrices, we show that the Jacobian will have full rank for most choices of activation patterns. Given this, all local minima within a region will be zero-loss global minima. For generic high-dimensional input data do 2 n, this implies most non-emply activation regions will have no bad local minima as all
2

---

Published in Transactions on Machine Learning Research (06/2024)
activation regions non-empty for generic data in high dimensions. We extend these results to the deep case in Theorem 14
In Theorem 10 we specialize to the case of one-dimensional input data dg = 1, and consider (wo-layer networks with bias term. We show that if d1 l))))))))) all but at most a fraction of non-emply linear regions in parameter space will have no bad local minima. We remark that this includes the non-differentaable local minima on the boundary between activation regions as per Theorem 13 Further, in contrast to Theorem S which looks at all binary matrices of potential activation patterns, in the one- dimensional case we are able to explicitly enumerate the binary matrices which correspond to non-empty activation regions.
Theorem 12 continues our investigation of one-dimensional input data, this time concerning the existence of global minima within a region. Suppose that the output head v has d, positive weights and d_.. negative weights and d4 + -_ = d1. We show that if d4, d_ = (n log())), then all but at most a fraction e of non-empty lincar regions in parameter space will have global minima. Morcover, the regions with global minima will contain an affine set of global minima of codimension n1
In addition to counting the number of activation regions with bad local minima, Proposition 15 and
Theorem 17 provide bounds on the fraction of regions with bad local minima by volume under additional assumptions on the data, notably anti-conceutrateddnes. These results imply that mild overparameterization suffices again to ensure that the 'size' of activation regions with bad local minima is small not only measured by number but also by volume.
1.2 Relation to prior works
As indicated above, several works have studied sets of local and global critical points of two-layer ReLU networks. We take a different approach by identifying the number of regions which have a favorable optimization landscape, and as result are able to avoid having to make certain assumptions about the dataset or network. Since we are able to exclude pathological regions with many dead neurons, we formulate our results for ReLU activations rather than leaky ReLU or other smooth activation functions. In contrast to Soudry & Carmon (2016), we do not assume dropout noise on the outputs of the network, and as a result global minima in our setting typically attain zero loss. Unlike Safran & Shamir (2018). we do not assume any particular distribution on our datasets; our results hold for almost all datasets (a set of full Lebesgue measure). Extremely overparameterized networks, with dj (nn for smooth activations (Song al, 2021) or di 2) for ReLU (Oymak & Soltanolkotabi 2019), are known to follow lazy training (see Chizal, et al. 2019): ;; our theorems hold under more realistic assumptions of mild overparameterrzation d1 12 log n) or even d 22(1) for high-dimensional inputs. We are able to avoid excessive overparamcterization by emphasizing qualitative aspects of the loss landscape, using only the rank of the Jacobian rather than the smallest eigenvalue of the neural tangent kernel, for instance.
2 Preliminaries
Before specializing to specific neural network architectures, we introduce general definitions which encompass of the models we will study, For any E N we will write [d] := {l,....,d) .d]. We will write 1, for a vector of d ones, and drop the subscript when the dimension is clear from the context. The Hadamard (entry-wise)
product of two matrices A and B of the same dimension is defined as A A B == (Ai Bıy)- The Kronecker product of two vectors Rd and R is defined as & u (uw2) Rum.
Let R| denote the set of polynomials in variables F1, II, In with real coefficients. We say that a set V C R" is an algebraic set if there exist fi...., fm E R[ such that V is the zero locus of the polynomials fú that is,
y far E f(xx) = 0 for all i [m]].
Clearly, and R" are algebraic, being zero sets of f and f = respectively. A finite union of algebraic subsets is algebraic, well as arbitrary intersection of algebraic subsets. In other words, algebraic sets
3

---

Published in Transactions on Machine Learning Research (06/2024)
form topological space. Its topology is known the Zariski topology. The following lemma is basic fact of algebraic geometry, and follows from subdividing algebraic sets into submanifolds of R
Lemma 1. Let V be an algebraic subset of R". Then either V = R" or V has Lebesgue measure 0.
For more details on the above facts, we refer the reader to Harris 2013) Justified by Lemma we say that a property P depending on 2 E I= holds for generic there exists a proper algebraic set 1 such that P holds whenever $ V. So if is a property that holds for generic æ, then in particular it holds for of full Lebesgue measure.
We consider input data
X = (x (.0).. Bdxn
and output data
y = (y (1) ....,,. (()) lxn
A parameterized model with parameter space In' is a mapping
F:R Rd + R.
We overload notation and also define F as a map from R x IRdxn to Rix by
F(0, (xx11 ,.... (e."",,.,""))))
(F(0,=()), (()) (()))(")))
Whether we are thinking of F as a mapping on individual data points or on datasets will be clear from the context. We define the mean squared error loss L: Rm x Rdxa x 12xx + R by
n
L(O, X,,) 2
(F(0, x00) 12
1=1
1
F X) yll?
(1)
For a fixed dataset (X,y), let Ix.y C I denote the set of global minima of the loss Ig that is,
Gx 0 B th I(0, X,9) inf 6E
L(Ø, X.u)
If there exists 8* E R such that F(O", X) = y, then L(O", X, y) = 0, so 0r is a global minimum. such a case,
GX 10 R" F) =
For a dataset (X, v), we say that 0 E Rm is a local minimum if there exists an open set C IRm containing 0 such that L(B, X, S L(ø, X, for all U. We say that is a bad local minimum if it is local minimum but not global minimum.
A key indicator of the local optimization landscape of neural network is the rank of the Jacobian of the map F with respect to the parameters 9. We will use the following observation.
Lemma 2. Fix a dataset (X,v) E Iddxn x Rlxn, Let F be parameterized model and let O E Rm be differentiable crilical point of the squared error loss equation 1 If (V, n, then 0 is a global minimizer.
Proof. Suppose that e 1 is a differentiable critical point of Then
0 VoL(O,X,))
VoF(B, (F(B,X) X) - y).
Since (an,(V)((, = n, this implics that F(B, X) - y = In other words, 0 is global minimizer.
We consider the squared error loss function f(y, 1 9) for concreteness, but most results hold for other satisfying Sy. @) if and only = 9.
4

---

Published in Transactions on Machine Learning Research (06/2024)
Finally, in what follows given data X study activation regions in parameter space. Informally, these are sets of parameters which give rise to particular activation patterns of the neurons of net over the dataset. We will define this notion formally for each setting we study in the subsequent sections.
3 Shallow ReLU networks: counting activation regions with bad local minima
Here we focus on a two-layer network with dg imputs, one hidden layer of dj ReLUs, and an output layer. The key lakeaway of this section is that moderate overparameterization is sufficient to ensure that bad local minima are scarce. With regard to setup, our parameter space is the input weight matrix in Rd1x4, Our input dataset will be an element X Rd and our output datasot an clement y E Rix", where n is the cardinality of the dataset. The model F: (IRdixdo x Rdi) x Rdo R is defined by
F(W, 1, v² (WW))
where is the ReLU activation function (w()), ..... w(dd))" where w+() Id is the ith row of W. Since a is piecewise linear, for any finite in- put dataset X we may split the parameter space into finite number of regions on which F is linear in W (and linear in v). For any binary matrix A E {0, I]dx and input dataset E Rdaxn, we define a corresponding activation region in parameter space by
max applied componentwise. We write W
2 s = (w( Rdixdo (2Ag - 1)( x000) for all i [dil,] e [n]].
This is a polyhedral cone defined by linear inequalities for each w(() For each A E {0, 1]dixn and E Rdoxx, we have F(W, X) = (A (WX)) for all W E St. which is linear in W. The Jacobian with respect to v is AG (W and with respoct W
VoF(W,X) = (0t 1 1 01) @ 200,, for all W E St A (0,1)dxxn
where ( denotes the jth column of A. To show that the Jacobian VoF has rank n, we need to ensure that the activation matrix A does not have too much linear dependence between its rows. The following result, due to Bourgain et al. (2010). establishes this for most choices of A.
Thcorem 3. Let A be d x d matrix whose entrics are sid random variables sampled uniformly from {0, 1}.
Then A is singular with probabilily al most
\ (1))
The next lemma shows that the specific values of e are not relevant to the rank of the Jacobian.
Lemma 4. Let ald) RRd, x05) Rdo for [n] and E Rdd be vectors, with va # for all i [di]. Then
rank(((u (1)) s (0) jj m)) rank((a!)) x0)) jj (m|))-
Using algebraic techniques, show that for generic X, the rank of the Jacobian is determined by A. Then by the above results, Lemma concludes that for most activation regions the smooth critical points are global minima (see full details in Appendix
Theorem 5. Let E > 0. If
nh 2 (log
n
))
di Z max
edo
then for generic datasets (X,y), y), the following holds. In all but at most [c2nd:] activation regions (i.e., an fraction of all regions), every differentiable critical point of L with Uj o for all j is a global minimum.
The proof of this result is presented in Appendix A The takeaway of Theorem b is that most activation regions do not contain local minima. However, for given dataset. X not all activation regions, each encoded

---

Published in Transactions on Machine Learning Research (06/2024)
by binary matrix A, may be realizable by the network. Equivalently, A is not realizable if and only if st = 0 and we call such activation regions emply. We therefore turn our attention to evaluating the number of non-empty activation regions. Different activation regions in parameter space are separated by the hyperplanes {W: (w(9, x00) = 0}. i [d1], j E [n]. We say that a set of vectors in a d-dimensional space is general position if any S d of them are linearly independent, which a generic properly. Standard results on hyperplane arrangements give the following proposition. Details are provided in Appendix B Proposition 6 (Number of non-empty regions). Consider a network with one layer of d1 ReLUs. If the columns of X are in gemeral position in d-dimensional linear space, then the number of non-empty activation E2= ("x)))4
regions in the parameter space is (2 k=
The formula provided above in Proposition is equal to 2nd if and only if S d, and is ((nd))) if n > d. We therefore observe that if large in relation to n and the data is in general position then by Proposition B most activation regions are non-empty. Thus we obtain the following corollary of Theorem
Corollary 7. Under the same assumptions as Theorem P if d 2 n, then for X in general position and arbilrary y, the following holds. In all but at most an fraction of all non-empty activation regions, every differentiable critical point of L with nonzero entries for is a zero loss global minimam.
More generally, for an arbitrary dataset that is not necessarily in general position the regions can be enumerated using a celebrated formula by Zaalavsky (1755), in terms of the intersection poset of the hyperplanes. Moreover, importantly one can show that the maximal number of non-empty regions attained when the datasct is in general position.
From the above discussion we conclude we have a relatively good understanding of how many activation regions are non-empty. Notably, the number is the same for any dataset that is in general position. However, it is worth reflecting on the fact that the identily of the non-emply regions, i.e., the sign patterns that are associated with them, depends more closely on the specific dataset and is harder to catalogue. For a given dataset X the non-empty regions correspond to the vertices of the Minkowski sum of the line segments with end points 0, (1), for j E [n]. as can be inferred from results in tropical geometry (see Joswigg 2021).
Proposition 8 (Identity of non-empty regions). Let A E 10, The corresponding activation region is non-emply if and only if Σ EjjAg= x(1) is a verlex of Eje(n) conv (0, (0,((0..00)) والار for all i E [d1]. Here conv(S) denotes the conver hull of a set S.
We provide a proof in Appendix B This result provides a sense of which activation regions are non-empty, depending on X. The explicit list of non-emply regions known in the literalure as the list of maximal covectors of an oriented matroid (see Björner et al., 1999), which can be interpreted as a combinatorial type of the dataset.
4 Shallow univariate ReLU networks: activation regions with global vs local minima
In Section 3 we showed that mild overparamcterization suffices to ensure that most activation regions do not contain bad local minima. This result however does not discuss the relative scarcity of activation regions with global versus local minima. To this end in this section we take a closer look at the case of a single input dimension, do = 1. Importantly, in the univariate setting we are able to entirely characterize the realizable (non-empty) activation regions.
Consider two-layer ReLU network with input dimension do 1, hidden dimension d1, and dataset consisting of n data points. We suppose the network has bias term & E Rd4 The model F; (IRd) x Rdh x Rd ) R + R
is given by
F(w, b, v,x) = u" ow + b).
Since we include a bias term here, we define the activation region St by
2X = (w: (w. b) Rd Rd (2A., 1) ((0) > for all i e [dil.j E [ml]
In this oimeeimensi case, we first obtain new bounds on the fraction of favorable activation regions show that most non-emply activation regions have no bad differentiable local minima. We begin with
6

---

Published in Transactions on Machine Learning Research (06/2024)
characterization of which activation regions non-empty. For ls E [n + 1], we introduce the step vectors g(k.0), ((k.1) E IR", defined by
1 if k; and (g(h.))
0
if k. i k
(g(k.0)) )1
i
Note that g(1,0) = g(x+1.1) and g(n+1.0) {(1.1) = 1. There are 2n step vectors in total. Intuitively, step vectors describe activation regions because all data points on one side of a threshold value activate the neuron. The following lemma makes this notion precise.
Lemma 9. Fir dataset (X,y) with x(1) < x(2) <.... < x(1), Let A {0, 10,1)d be binary matria. Then S is non-empty if and only if the rows of A are step vectors. In particular, there are exactly (2n)di non-empty activation regions.
Using this characterization of the non-empty activation regions, we show that most activation patterns corresponding to these regions yield full-rank Jacobian matrices, and hence the regions have no bad local minima.
Theorem 10. e (0, Suppose that X consists of distinct data points, and
di 2 log (*)
Then in all but at most fraction e of non-empty octivation regions, V&F is full rank and every differentiable critical point of where has nonzero entries is global minimum.
Our strategy for proving Theorem 10 hinges on the following observation. For the sake of example, consider the step vectors g(l:)) ((2.))) ( g(n,1), This set vectors forms a basis of R", so if each of these vectors was a row of the activation matrix A, would have full rank. This observation generalizes to cases where some of the step vectors are taken be g(k,0) instcad of c(R.1), If enough step vectors are "collected" by rows of the activation matrix, it will be of full rank. We can interpret this condition in probabilistic way. Suppose that the rows of A are sampled randomly from the set of step vectors. We wish to determine the probability that after di samples, enough step vectors have been sampled to cover a certain set. We use the following lemma. Lemma 11 (Coupon collector's problem). Let e E (0, 1), and let n S m be positive integers. Let C1, C2...., Ca E [m] be iid random variables such that for all E [m] one has P(C1 =] 2 1f
d log n
then [n] C (C1,...,Cay with probability al least -
This gives us a bound for the probability that randomly sampled region is of full rank. We finally convert this into a combinatorial statement to obtain Theorem 10 For the details and complete proof, see Appendix C
In one-dimensional input space, the existence of global minima within region requires similar conditions to the region having full rank Jacobian. Both of them depend on having many different step vectors represented among the rows of the activation matrix. The condition we need to check for the existence of global minima is slightly more stringent, and depends on there being enough step vectors for both the positive and negative entries
Theorem 12 (Fraction of regions with global minima). Let c (0,1) and let R$ have nonzero entries. Suppose that X consists of dislinct dala points,
22n
Hi E [d1]: o00 >
001 2n log
and
2n
1(i E [di) o <0] 2n log
Then in all but most an fraction of non-empty activation regions Sy, the subset of global minimizers in (w, b), 9x.y SSA, A is non-empty affine set of codimension n. Moreover, all global minima of have zero loss.
7

---

Published in Transactions on Machine Learning Research (06/2024)
We provide the proof of this statement in Appendix C To conclude, for shallow ReLU networks and univariate data we have shown that mild overparameterivationn suffices to ensure that the loss landscape is favorable in the sense that most activation regions contain a set of global minima of significant codimension and do not contain any bad local minima. Furthermore, considering both Sections g and 4 we have shown in both the one-dimensional and higher-dimennional cases that most activalion regions have a full rank Jacobian and contain no bad local minima. This suggests that a large fraction of parameter space by volume should also have full rank Jacobian. This indeed turns out to be the case and is discussed in Section p Finally, highlight to the reader that provide discussion of the function space perspective of this setting in A Appendix D
4.1 Nonsmooth critical points
Our results in this section considered the local minima in the interior of given activation region. Here we extend our analysis to handle points on the boundaries between regions where the loss is non-differentiable. Recall that any locally Lipschitz function I + IR is differentiable on a set U of full measure. For such a function g, its Clarke subdifferential (Clarke 1990
Ög at a point 0 E R" is defined by
lim (g(( Og U. lim 02 = = k-000
0g(0) = conv
k-000
where conv denotes the convex hull. A point 0* E R is said to be Clarke stalionary poinl of if E 0y(("). Note that this is nonsmooth generalization of the notion of a critical point; if is smooth, then 0 is Clarke stationary point if and only if Vg((") = O.
We consider a network on univariate data F(w, b, u, w) as in Section Let sgn - [0, be the unit step function:
= if i 0
sgn(2) =
Here we define the activation regions to include the boundaries:
S = { (w, b) E dh x Rd sgn(w(() (000 + ((0)) = Ai for all i [di],j E [m]
We assume that the input dataset X consists of distinct data points (!)) (2) ... < x()). By the same argument as Lemma g an activation region S4 is non-empty and only if the rows of A are step vectors, and we derive the following result.
Theorem 13. Let e E (0, Tʃ
n (*)
di 2 2n log
then in all bud at most fruction of non-explly activation regions A, every Clarke stationary point of L in S x Rd is a global minimum.
5 Extension to deep networks
While the results presented so far focused on shallow networks, they admit generalizations to deep networks. These generalizations are achieved by considering the Jacobian with respect to parameters of individual layers of the network. In this section, we demonstrate this technique and prove that in deeper networks, most activation regions have spurious critical points. We consider fully connected deep networks with L layers, where layer maps from pdi-1 to Rd, and d₁ 1. The parameter space consists of tuples of matrices
W (W1, (W,,We..... W Wz).
where Wi E Rdixd-1, We identify the vector space of all such tuples with R", where Σls did;-1- For E {0.... L.}, we define the 1-th layer ft: R x IRdi-1 - Rd recursively by
So (W, .r) :=
8

---

Published in Transactions on Machine Learning Research (06/2024)
if [Z--1] 1), and
where Rd- is lixed vector whose entries are nonzero. Then Sr. is the final layer output of the network, so the model is given by F: fL. We denote the j-th row of Wi by wf The activation patterns a deep network are given by tuples
A (A1, A2.........................
(A.,AA...,AA AL-1),
where for each / E [L-1], 11, A E 10,n,, For activation pattern A, let St denote the subset of parameter space corresponding to A. More precisely,
SX ( e R" (2[Aily
f > 0 for all I [L- 11. e [di], [n]]}.
Assuming linear scaling of the second-to-last layer of the network in the number of data points, along with mild restrictions on the other layers, we prove that most activation regions for deep networks have full rank Jacobian
Theorem 14. Let X E Rd an input dataset with distinct points. Suppose that for all E [L - 2),
di = 2 (10g EL
and that
d1-11=++ = + (1088
log !)
Then for at least (1 e) fraction of all activation pullerns A, the following holds. For all W S
Vw (wW(W,X) has rank
We provide proof of this statement in Appendix
6 Volumes of activation regions
Our main results so far have concerned the number of activation regions containing bad local versus global minima. Here we compute bounds for the volume of the union of these bad versus good activation regions, which recall are subsets of parameter space. Proofs of all results in this section are provided Appendix F
6.1 mineddmensional input data
Consider the setting of Section 4 where we have network F F(w, b, v,æ) on one-dimensional input data. Recall that for A E {0, jdixn, we defined the activation region S by
2x = b) E RR x IR:,, (2A:, - 1) ()) (1) + ((0) 0 for all E [dal,] E [n]] For & E [n + 1), 8 E {0.1} and corresponding step vectors ((R,)), we also define the individual neuron activation regions Nk.0 by
Nk.3 (ww E R R (2c() () +b) > 0 for all j [n]].
Let μ denote the Lebesgue measure. First, we compute exact formula for the volume of the activation regions intersected with the unit interval. That is, we compute the Lebesgue measure of the set ( [| (-1,
Proposition 15. Let sb 1-o0, co] + [0, 2] be defined by
x -1
(x)) =
1 1 x
-
2
2
ff>11
9

---

Published in Transactions on Machine Learning Research (06/2024)
Consider data x(1) ... S.....h vx Then for & E [n + 1] and B E {0,1},
aNNo, n (1-1, x [-1, = (b(x()) - 2bx(((111)
Here we define x00) := -0; x(n-1) == oc.
We apply this result to bound the volume of activation regions with full rank Jacobian in terms of the amount of separation between the data points. For overparameterized networks with sufficient separation, the activation regions with full rank Jacobian fill up most of the parameter space by volume.
Proposition 16. Let n 2 Suppose that the entries of v are nonzero. Suppose that for all j, E [n] with ki have |all)) < and (a-6) r(h1| Φ.
T1 di 2 log 7
then
" UAEA S ([-1,11) x x-11,1141 (1-
where the union runs over the set A consisting of those activation potterns E {0, 13dixn such that W. has full rank on S
6.2 Arbitrary dimension input data
We now consider the setting of Section 3 Our model F; Rd xdo x Rdd x Rd + R defined by
F(W, u x) o (W.).
We consider the volume of the set of points (W, v) such that V ((w,)) F(W, v X) has rank n. We formulate this problem probabilistically. Suppose that the entries of W and sampled from the standard normal distribution (0 1). We wish to compule the probability that the Jacobian has full rank.
Let sgn R - {0, 1} denote the step function:
0
if = 0
sgn(2)
if 1f200*
For an input dataset E Ig consider the random variable
sgn (XT (XTw),
where w .N(0 7), and sgn is defined entrywise. This defines the distribution of activation patterns on the datasct, which we denote by Dx. We say that an input datasct X E Rdoxn is y-anticoncentrated if for all nonzero u E R",
PaNDY (u a = 0) S 1 7
We interpret this a condition on the amount of separation ion between data points. For example, suppose that two data points (11) and (R) are highly correlated: [| ||x((0]| = 1 and
p. Let take
E R" to be defined by uj = 1, up -, and 4n 0 for l + j. k. Then
Pa~Dy (uTa= 0 0) = Po-Dx (a, = ax)
P PunNion (sgn (w (TT 2010)
sgn(wT (+))
1
= 1 arccos( (z(1) (z())=(()) x0))z(()))))) (())))
< arccos(p)
10

---

Published in Transactions on Machine Learning Research (06/2024)
So in this case, the dataset is not y-anticoncentrateed for 7 arccos( At the other extreme, suppose that the dataset uncorrelated: (oli), ((1)) for all j, k E [n]. Then for all 2 E R,
PawDy (an = - (i,...., an-1
P wn (ww, x _ 2 0
(w, x(1), ,..., (ue, x s(a-111)
P ((w, - 0)
2
For Rd with un #0,
P PaNDx (u a = 0) = E[P((u 01.00,,.., an-1))
n-1
E
Un =
Uzag a1
On-1
==1
- E[1/2]
1/2.
So this case, the dataset is y-anticoncentrated with y = 1/2. In order to prove that the Jacobian has full rank with high probability, we must impose separation condition such as this one as data points get closer together, it becomes harder for the network to distinguish between them and the Jacobian drops rank. Once impose y-anticoncentration, mildly overparamcterized network will attain full rank at randomly selected parameters with high probability.
Theorem 17. Let 7 E (0, 1)- Suppose that X E Rdaxn is generic and y-antliconcentraled. Tf
8 72
do 2 ? do +1)
d1 log
then with probability al least e,, ((w.o) F(W, v, X) has rank n.
7 Experiments
Here we empirically demonstrate that most regions of parameter space have a good optimization landscape by computing the rank of the Jacobian for two-layer neural networks. We initialize our network with random weights and biases sampled iid uniformly on |- Va. v We evaluate the network on random dataset
X E Rd whose entries are sampled iid Gaussian with mean 0 and variance 1. This gives us activation region corresponding to the network evaluated at X, and we record the rank of the Jacobian of that matrix. For each choice of dg. d,, and n, we run 100 trials and record the fraction of them which resulted in a Jacobian of full rank. The results are shown in Figures and
For different scalings of and do, observe different minimal widths dj needed for the Jacobian achieve full rank with high probability. Figure 1 suggests that. the minimum value of d1 needed to achieve full rank increases roughly linearly in the dataset size n, and that the slope decreases increases. This is the behavior predicted by Thcorem 2 which finds full rank regions for d1 Z do Figure 2 operates in the regime do ~ and shows that the necessary hidden dimension d, remains constant in the dataset size n. This is again consistent with Theorem whose bounds depend only on the ratio z. Further do supporting experiments, including those involving rea world data, are provided in Appendix G
the input dimension do
11

---

Published in Transactions on Machine Learning Research (06/2024)
270
240
0.8
240
0.5
200
08
240
270
0.8
210
150
210
0.0
210
-06
210
100
0.2
00
0.2
60
-2
02
20 50 60 70 100
10 20
40 53 60 73
00 100
10 30 40 50 83
60 90 50
20 40 63 70 90 100
Dataset 6ize
Datamel B:20
Catarel size
Datasee 6iz0
(a) do
(b) da 2.
(c) da
(d) do 5.
Figure 1: The probability of the Jacobian being of full rank from random initialization for various values of d and where the input dimension do is left fixed.
0.8
0.0
-00
0.8
Aelmart with
Pootear mi0th
with
Noteort
3.4
-04
02
02
30 50 70 90 101001001111
10 30 TO 80 N0110150110180
10 30 T0 80 110130152700:50
30 50 70 90 11013110013110
Detasot aic
Datasct 5iz0
Colosct 922
Doteset 5030
(a)
(b) do 1
(c) do
(d) 2n.
Figure 2: The probability of the Jacobian being of full rank for various values of di and n, where the input dimension dg scales linearly in the number of samples
8 Conclusion
In this work we studied the loss landscape of both shallow and deep ReLU networks. The key takeaway is that mildly overparametorization in terms of network width suffices to ensure the loss landscape favorable in the sense that bad local minima exist in only a small fraction of parameter space. In particular, using random matrix theory and combinatorial techniques we showed that most activation regions have no bad differentiable local minima by determining which regions have full rank Jacobian. For univariate data we further proved that most regions contain high-dimensional set of global minimizers and also showed illustrated that the same takeaway is true when also considering potential bad non-differentiabe local minima on the boundaries between regions. Finally the combinatorial approach we adopted allowed us to prove results independent of the specific choice initialization of parameters, or on the distribution of the datasct. There are number of directions for improvement. Notably we obtain our stnnges results for shallow one-dimensional input. case, where we have a concrete grasp of the possible activation patterns; the case dj < n remains open. We leave strengthening our results concerning deep networks and high dimensional data to future work, and hope that our contributions inspire further exploration address them.
Reproducibility statement The computer implementation of the scripts needed to reproduce experiments can be found at https:/// httpghaw...../cca//////////aaaaa
Acknowledgments
This project has been supported by NSF CAREER 21 2145630, NSF 2212520, DFG SPP 2298 Grant 464109215, ERC Starting Grant 757983, and BMBF in DAAD project 57616814.
12

---

Published in Transactions on Machine Learning Research (06/2024)
References
Martin Anthony and Peter L. Bartlett. Newral Network Learning: Theoretical Foundations. Cambridge
University Press, 1999. URL https://doi. 00//000000/000577001644466
Peter Auer, Mark Herbster, and Manfred K. K Warmuth. Exponentially many local minima for single neurons.
In D. Touretzky, M.C. Mozer, and M. Hasselmo (eds.), Advances in Newral Information Processing Systems, volume 8. MIT Press, 1995. URL http://rp///p.reeeednggg... www.eeeddinnnn.uuiss..... http:://ww....riiiee..//pppppppe httpppppr..lleeeeppp////////eeee
Anders Björner, Michel Las Verguas, Bernd Sturmfels, Neil While, and Gunter M. Ziegler. Oriented Malroids.
Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 1999. URL https
Jean Bourgain, Van H Vu, and Philip Matchett Wood. On the singularity probability of discrete random
matrices. Journal of Functional Analysis, 258(2):559 603, 2010. URL
science/ science/article/piie /ttea////rrrceeee/////2222000000
An Mei Chen, Haw-minn Lu, and Robert error surfaces, Neurol Computation, 5(6):910 927, 1993. URL 6796044
On the geometry of feodforward neural network
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming, In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL hnttps// neurips. hat.l////aaaaaa.eoe//////atttaaa
Paper .pf
F.H. Clarke, Optimization and Nonsmooth Analysis. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, 1990. ISBN 9780898712568. URL htapas//bbooss.gggllll.ooo//o///
DVse-WVJVLYC
Yaim Cooper. Global minima of overparamettrrized neural networks. SIAM Journal on Mathemalics of Dala Science, 3(2):676-66)) (61666691161 2021. URL https::/doi. 111.9/99..117/11111089494
Thomas M. Cover. Geometricnl and Statistical Properties of Linear Threshold Devices. PhD thesis, Stanford
Electronics Laboratories Technical Report #6107-1, May 1964. URL httpss/::///s...... stta:///orssss.fordd. hta.a/al..staffrrreeee/e/oooerrr edu/-cover/ papers/papert.
Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, (CC-1((3)3226333 1965.
Lisandro D Dalcin, Rodrigo R Paz, Pablo A Kler, and Alejandro Cosimo. Parallel distributed computing using python. Advances in Water Resources, 34(9):1124 1139, 2011.
Kenji Fukumizu and Shun-ichi Amari. Local minima and platcaus hicrarchical structures of multilayer rerceptrons. Neurul Nelworks, 13(3):317 327, 2000. URL http::://ww..scinneeereeee.. wwtpe/eccttccccccieeeeeeeeeeeeee scienc/
atticl//11/5083660000003
Micah Goldblum, Jonas Geiping, Avi Schwarzschild, Michael Moeller, and Tom Goldstein. Truth backpropaganda?? an empirical investigation of deep learning theory. In International Conference Learning Represenlations, 2020. URL httpp::/ wtt.e//rrew..e..f.ooooooooylyyee
Marco Gori and Alberto Tesi. On the problem of local minima in backpropagation. JEEF Transactions on Pattern Analysis and Machine Intelligence, 14(1):76-86 1992. URL httpp::/leeeepplore leee. .ege.org/
document/107014
J. Elisenda Grigsby, Kathryn Lindsey, Robert Mcyerhoff, and Chenxi Wu. Functional dimension of feedforward ReLU neural networks. aiXiv preprint ar S5w:2209.44088 2022.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Charles R Harris, K Jarrod Millman, Stéfan J Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, et al. Array programming with numpy. Nature, 585(7825):357 362, 2020.
Joe Harris. Algebraic geometry: A first course, volume 133. Springer Science & Business Media, 2013. URL http://:/...aaaaaa.ooorooooooooa
Fengxiang He, Bohan Wang, and Dacheng Tao. Piecewise linear activations substantially shape the loss surfaces of neural networks. In International Conference on Learning Represenlations, 2020. URL
https://openrevier: net
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015. URL htttps://ppnacceess. thecvf com/content _iccetttt_iiiieeeeeee _015/ intiiintttoo Salie__0115__pppPP pappr.hmml
Beapl/HeeDelving..o
John D Hunter. Matplotlib: A 2D graphics environment. Computing science & engineering, 9(03): :90-599-95, 2007.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Bengio, H. Wallach, H. Larochelle, Grauman, N. Cesa- Bianchi, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 31. Cur- Associates, Inc., 2018. URL https::/prooceedngs. wwweeddinnnnuuriss.oomm www.rrips.ccppppppeeeeeee http:r/w...ccppppppp.aa/////ap/p /ttp.///lleaappp////////////// fa2befa5442200aee651117777112222
.dff
Michael Joswig. Essentials of tropical combinatorics, volume 219 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2021. httpss//:/ math. tw- wewberrii.deeejjsss.eee.eeeeeeee je/wjiivi//
etc/index. html
Thomas Laurent and James von Brecht. The multilinear structure of ReLU networks. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Mochine Learning Research, pp. 2908-2916. PMLR, 10-15 Jul 2018. URL
https://proceeedings www.inng..m......mmmmmm...mmmmmm wtt.smml......eeeeeeee wttpprre///001aauettt100...
Bo Liu. Understanding the loss landscape of one- aachhidden-layer relu networks. Knowledge- Systems, 220: 106923, 2021. URT. http:///wwwaaaaaaacccc......aaap
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of lin- ear regions of deep neural networks. Tn 7. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Cur- ran Associates, Inc., 2014. URL https://procceddngs. (1922088606660011111001111CcCCl3
pdf Guido Montúfar, Yue Ren, and Leon Zhang. Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums. STAM Journal on Applied Algebra and Geometry, 6(4):618 649, 2022.
URL atttp:://aol.org/1..11333 1131//1111111
Quynh Nguyen. On connected sublevel sets deep learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4790 4799. PMLR, 09-15 15 Jun 2019. URL htttp::/prroceeding..tt
presss/977nnuuyen19a. html
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization:: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1: 84-105, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in newral information processing systems, 32, 2019.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Mary Phuong and Christoph H. Lampert. Functional vs. parametric equivalence of ReLU networks. In International Conference on Learning Represendations, 2020. URL. httt:p///opeerrevieeeenef/rouooe
Bylx- Bylx-TNKvH
T. Poston, C.-N. Lec, Y. Choic, and Y. Kwon. Local minima and back propagation. In IJCNN-01- Seallle International Joint Conference on Newral Networke, volume ii, pp. 173 176 vol.2, 1991. URL
https://teexxpoore.eer orteeee.rg//ocueee htgg/dccumen/1155233
Itay Safran and Ohad Shamir. On the quality of the initial basin in overspecified neural networks. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machime Leurning, volume 48 of Proceedings of Machine Learning Reseurch, pp. 774 782, New York, mlr oaaa safran16.... htmml
New York, USA, 20-22 Jun 2016. PMLR. URL https::/prroceddingg
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer ReLU neural networks. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseurch, pp. 4433 4441, PMLR, 10 Jul 2018.
URL https://proceediing .waiingssmrr.....mmm mlr, www..pp..//e........ / wwas/aaaaaaaaaaeamaamamaaaa
Akito Sakurai. Tight bounds for the VC-dimension of piccewise polynomial networks. In M. Kearns, S. Solla, and D. Cohn (eds.), Advances in Newral Information Processing Systems, vol- ume 11. MIT Press, 1998. URL https: htttps://proceddugg.nt htt.igg..neurrpccc//eeeeeee filles/paper/1998//11
Ludwig Schläfli. Theorie der vielfachen Kontinuität, pp. 167-387. Springer Basel, Basel, 1950. URL
Arsalan Sharifnassab, Saber Salchkaleybar, and S. Jamaloddin Golestani. Bounds on over-parameterization for guaranteed existence of descent paths in shallow ReLU networks. In International Conference on Learning Representations, 2020. URL
Berfin Simsek, François Ged, Arthur Jacot, Francesco Spadaro, Clement Hongler, Wulfram Gerstner, and Johanni Brea. Geometry of the loss landscape in overparameterized neural networks: Symmetries and invariances. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9722 9732. PMLR, 18 24 Jul 2021. URL https::/proceedingg
mlr wwtppp/esseeeeeeeeeeeeeeepp wwwp://////mmmmmaaaaaa.ma html
ChaeHwan Song, Ali Gamezani-Kebryee Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Subquadratic overparameterrizttin for shallow neural networks. Tn M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 11247-11259. Curran Associates, Inc., 2021. URL http://////o http:igs.....rrrps..copppppppeee cctpeperfppleeeeee//////p files/ hptp://000.1./0eeee44ffffffffff1
Eduardo Sontag and Héctor J. Sussmann. Backpropagation can give rise to spurions local minima even for networks without hidden layers. Complex Syst., 3, 1989. URL htttp:://wwtt ceapplexxxysstem
abstracts/vo3_i01.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent. training error guaranlees for multilayer neural networks. arXio preprint Xiv: 08361, 2016.
Grzegorz Swirszez, Wojciech Marian Czarnecki, and Razvan Pascanu. Local minima in training of deep networks, 2017. URL https::/ooperrevies htt./forrummdddyyyooqe..r.
Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3404-3413. PMLR, 06-11 Aug 2017. URL https://proceedngs..ll press/v70/tians http:///0ttian1a....m html
15

---

Published in Transactions on Machine Learning Research (06/2024)
Yifei Wang, Jonathan Lacotte, and Mert Pilanci. The hidden convex optimization landscape of regularized two-layer reI.U networks: an exact characterization of optimal solutions. In International Conference Learning Representations, 2022. URL
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks powerful memorizers: tight analysis of memorization capacity. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019a. URL https://prooeeddiggg htt.://ww................//////a Qbea3bbeaaTTrrccc22/777777771552
peerrpps.c/ppppee http://ccccpppppeeee/////a/eeeea
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. In International Conference on Learning Representations, 2019b. URL
https://openrevien hetp://paa.raain..oooooooaaoaaaa YiRct7
Thomas Zaslavsky. Facing up to Arrangements: Face-Counl Formulas for Partilions of Space by Hyperplanes. American Mathematical Society: Memoirs of the American Mathematical Society. American Mathematical Society, 1975. URL https://books.. google.
Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry deep neural networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. Sweden, 10- 15 Jul 2018. PMLR. URL httpp://proceedings.. mlr ppresss/8802haag11.5. html
Stockholmsmässan, Stockholm
Zhou and Yingbin Liang- Critical points of linear neural networks: Analytical forms and landscape properties. In International Conference Learning Representations, 2018. URL https://openrevial
net/forum?idd-Syseoxxee
16

---

Published in Transactions on Machine Learning Research (06/2024)
A Details on counting activation regions with no bad local minima
We provide the proofs of the results presented in Section
Proof of Lemma 4 Suppose that 1 A(a) R. Since the entries of v are nonzero, the following are equivalent:
00 (v 0000=
16
1. =0
bj E [dg), E [d1]
Ukllk 2j
(1) (8)
vj E [do], h: [di]
0
(1) =
vj E [do), k: E [di)
1=1
Σ
a0 & (0) = 0.
So the kernel the matrix whose i-th row is (o al)) & xt) equal to the kernel of the matrix whose i-th row is al)) @ (.) follows that
rank(f(v (0 o (0) :ien)) rank((a!)) (00) : [m])).
)
Proof of Theorem 5 Suppose that dgd1 2 n. Consider a matrix A E {0, 1]dxxn which corresponds to one of the thelretically possible activation pattern of all di units across all n input examples, and denote its columns by a(d) E 10 = In...,n. n. For any given imput dataset X, the function F piecewise linear in W. More specifically, on each activation region St, v, is a lincar map in W of the form
do
F(W, 2())
m.y Wa.t
E [n]).
So on S the Jacobian of F(, is given by the Khatri-Rao (columnwise Kronecker) product VwF(W, v, X)= ((v@a()) x(1) ..... (v (()) 8 (*)).
(2)
In particular, VwF F is of full rank S exactly when the set.
((v (3) (0) i [n]]
consists of linearly independent elements of Rd xdo since dod1 2 By Lemma 4 this is equivalent to the set
[n]]
consisting of linearly independent vectors, in another words, the Khatri-Rao product A X having full rank.
For a given A E {0, 1]dxxn consider the set
J= (XE A X of full rank).
The expression A X corresponds to FWF e, X) in the case that W SR. Suppose that dj is large enough that dj 2 x. We will show that for most {0, 1idin, JA is non-empty and in fact contains
17

---

Published in Transactions on Machine Learning Research (06/2024)
almost every X. We may partition [n] into r: 2; subsets S1, S2....... Sr such that [S&] d1 for all & [r] and partition the set of columns of A accordingly into blocks (a(*)) for all & E [r]. Let us form a d1 x [Sk] matrix M whose columnss are the a 8 E Sy- We will use a probabilistic argument. For this, consider the entries of M as being iid Bernoulli random variables with parameter 1/2. We may extend M to a d, random matrix M whose entries are iid Bernoulli random variables with parameter 1/2. By Theorem M
will be singular with probability most
( ( di -C.20.7
where Ci is a universal constant. Whenever M is nonsingular, the veclors al*), 8 E Sq are linearly independent. Using a simple union bound, we have
IP (al))) are linearly independent for all k E (rl) 21-rCi
Now suppose that (a(*)) sES, are linearly independent for all & E [r]. Let el...., Edo be the standard basis of RRd0 Since r S do, there exists X do such that a00) ex whenever i E Sk- For such an X, we claim that the set
la x0 : [n])
consists of linearly independent elements of Rd ddb To see this, suppose that there exist a1, an such that
a:(a )z 0.
Then
0
ai(a & (0)
A= iES
(i(a 50 ex)
k= iESt
aial!) )
20 ek.
1=1
VESt
The above equation can only hold if
Σ a =0, for all [r].
By the linear independence of (a (a Jiesk, this implies that a, = 0 for all E [n]. This shows that the elements at @ (t))) are linearly independent for particular X whenever the )ess. are all linearly independent. In other words, J is non-empty with probability at least Cir(0.2241) when the activation region is chosen uniformly at random.
Let us define
A: (A (0,1)dix' J + 0].
We have shown that if A is chosen uniformly at random from {0, 11 then A A with high probability. Note that J is defined in terms of polynomials of X not vanishing, so J is the complement of a Zariski-closed subset of Rdoxn, Let
-==NAE
Then is a Zariski-open set of full measure, since is a finite intersection of non-empty Zariski-open sets (which are themselves of full measure by Lemma 1.. If X I and A E A, then Vw F(W, [W,X] X) is of full rank
18

---

Published in Transactions on Machine Learning Research (06/2024)
for all W Sx and therefore all local minima in SX will be global minima by Lemma X E J and d1 such that
So if we take
log
(x(+11) dot
d1 2
log 0.72
and choose E [0,1]a dd uniformly at random, then with probability at least
1 1 -- 2 11-Ch Cir (C. doe
crr (G(0t1))
1
o will have no bad local minima. We rephrase this as combinatorial result: if d, satisfies the same bounds above, then for generic datasets X we have the following: for all but at most [c2dad]] activation regions S S has no bad local minima. The theorem follows.
The argument that we used to prove that the Jacobian is full rank for generic data can be applied to arbitrary binary matrices. The proof is exactly the same as the sub-argument in the proof of Theorem
Lemma 18. For generic datasets X E IRdoxn, the following holds. Let a E {0, 1]dh for i E [n]. Suppose that there enists a portilion of [n] inlo r S do subsets S such that for all E [r],
rank((a :iESt))
St}) = -Sal--
Then
rank((a xx [n]}) n.
B Details on counting non-empty activation regions
We provide the proofs of the results presented in Section 3 The subdivisions of parameter space by activation
propertics of ncurons classically studiod in VC-dimension computation (Cover) 1965 Sakurai
1998 Anthony
& Bartlett 1999). This has similarities to the analysis of linear regions in input space for neural nelworks with piecewise linear activation functions (Montúfar al. 2014).
Proof of Proposition 0 Consider the map Rd + R": w r [wTTX] that takes the input weights w single ReLU to its activation values over n input data points given by the columns of X. This can equivalently interpreted as a map taking an input vector to the activation values of n ReLUs with input weights given by the columns of X. The linear regions of the latter correspond the (full-dimensional) regions of central arrangement of n hyperplanes in Rd with normals z(1),. , x(()), Denote the number of such regions by Nx. If the columns of X are in general position in d-dimensional linear space, meaning that they are contained in d-dimensional linear space and any columns are linearly independent, then
Nx Nd,n == 2
Σ k=
(3)
k
This is a classic result that can be traced back the work of Schläffi 1950)), and which also appeared in the discussion of linear threshold devices by Cover (1964).
Now for layer of dj ReLUs, each unit has its parameter space dd subdivided by equivalent hyperplane arrangement that is determined solely by X. Since all units have individual parameters, the arrangement of each unit essentially lives in different. set of coordinates. In turn, the overall arrangement in the parameter space de xd1 of all units a so-called product arrangement, and the number of regions is (Nx))1, This conclusion is sufficiently intuitive, but it can also be derived from Zaslavsky (1975) Lomma 4A3). If the input data X is in general position in d-dimensional linear subspace of the input space, then we can substitute equation into (Nx) dd and obtain the number of regions stated in the proposition.
19

---

Published in Transactions on Machine Learning Research (06/2024)
We also interested in the specific identity of the non-empty regions; that is, the sign patterns that are associated with them. As we have seen above, the set of sign patterns of layer of units is the dy-Cartesian power of the set of sign patterns of an individual unit. Therefore, it is sufficient to understand the set of sign patterns of an individual unit; that is, the set of dichotomics that can be computed over the columns of X by a bias-free simple perceptron x + sgn(w= x)) Note that this subsumes networks with biases as the special case where the first row of X consists of ones, in which case the first component the weight vector can be regarded as the bias. Let Lx be the Nx n matrix whose Nx rows are the different possible dichotomies +-1" If we extend the definition of dichotomies to allow not only +1 and -1 but also zeros for the case that data points fall on the decision boundary, then we obtain matrix Lx that is referred to as the oriented matroid of the vector configuration X, and whose rows are referred to as the covectors of X (Björner et al. 1999). This is also known as the list of sign sequences of the faces of the hyperplane arrangement.
(sgn w 2()), ;.... sgn w" wTx(())
(()))
To provide more intuitions for Proposition we give sclf-contained proof below.
Proof of Proposition For each unit, the parameter space de is subdivided by an arrangement of n hyperplanes with normals given by x(1), E [n]. A weight vector is in the interior of the activation region with pattern 10, if and only if (2a,- 1)wT>(00
for all [n]] Equivalently,
w ()) > w0 for all j with oj = +1
T > w 20)) for all j' with df = 0.
This means that is a point where the function w + w" Σj: a, xt,) attains the maximum value among of all linear functions with gradients given by sums of 2()) meaning that at this function attains the same value as
s:: w + Σ max (0, w 000 = max w sCIn]
())
(4)
JE
JES
Dually, the linear function + w x attains its maximum over the polytope
P = conv
00; S SSS [n]]
(5)
JES
precisely at Σj: a,=1 x() In other words, Ej: a,=1 z(i) is an extreme point vertex of P with supporting
hyperplane with normal w. For a polytope P C RR, the normal cone of P at a point æ E P is defined as the set of w E I such that wTx 2 wTT x' for all x' E P. For any S S [m] let us denote by 1ş E {0, 1)/1) the vector with ones at components in and zeros otherwise. Then the above discussion shows that the activation region S with a = 1g the interior of the normal cone of P at Zjes=(0) In particular, the activation region is non empty if and only if EEEs at is a vertex of P.
To conclude, we show that P is a Minkowski sum of line segments,
P= Σ Pj P = (0,
jE(N)
To see this note that x E P and only if there exist as 2 0, Eg ag = 1 with
Σ
(1)
x =
as
SCIn]
JES
(1)
jE
jeS
= Σ I( Σ as)0 + ( Σ as)
JE
S:
j:
Σ
[[1 8,)0 + B ,,0(001 Σ 201,
JE(N)
20

---

Published in Transactions on Machine Learning Research (06/2024)
111
P = Pi + P2 + P3
110
011
x(1)
(3)
(2)
100
001
000
Figure 3: Illustration of Proposition The polytope P for a ReLU on three data points x x(1, x0))
[x0)) (0) is the Minkowski sum of the line segments P. = conv(0, x0)] highlighted in red. The activation regions in parameter space are the normal cones of P at its different vertices. Hence the vertices correspond to the non-emply activation regions. These naturally labeled by vectors 1y that indicate which x(+) are added to produce the vertex and record the activation patterns.
+,,0++,x(01] Thus, E P if and only if x is a sum of points where By = EE: jes as and 200 = [[1-- 3,x(1),
200 E P, conv (0, 20), meaning that p= E; P, as was claimed.
EEP,
The polytope equation 5 may be regarded as the Newton polytope of the piecewise lincar convex function equation 4 in the context of tropical geometry (Joswig] 2021). This perspective has been used to study the linear regions in input space for ReLU (Zhang et al., 2018) and maxout networks (Montúfar et al. 2022
We note that cach vertex of a Minkowski sum of polytopes P= P1 +... Pr is a sum of vertices of the summands P,, but not every sum of vertices of the P3 results in vertex of P. Our polytope P is sum of line segments, which is a type of polytope known as a zonotope. Each vertex of P takes the form o = Σ ?/ where each 1 vertex of Pj. either the zero vertex 0 the nonzero vertex z(0), and is naturally labeled by a vector 1s {0, 13" = 2(d) that indicates the js for which v, = x(6), A zonotope can be interpreted the image of cube by linear map; in case it is the projection of the n-cube convfa (0, 1).] C R into Rdo by the matrix X E Rdxxn, The situation is illustrated in Figure 3
Example 19 eNon-empty activation regions for 1-dimensional inputs). In the case of one- mieeiiensio inputs and units with biases, the parameter space of cach unit is R We treat the data as points xx!)) r .....,,()))) E IR, where the first coordinate is to accommodate the bias. For generic data (i.e., no data points on top of each other), the polytope P EjE(,, conv (0, 2:1) is polygon with 2n vertices. The vertices have labels 1, indicating, for each à = 0, ....., n, the subsets C [n] containing the largest respectively smallest & elements in the dataset with respect to the non- bias coordinate.
C Details on counting non-empty activation regions with no bad minima
We provide the proofs of the statements in Section 4
Proof of Lemma g First we establish that the rows of the matrices A corresponding to non-emply activation regions must be step vectors. To this end, assume A E St and for an arbitrary row i [di] let A, = a E 1). If A, = a for all E [n]. then the i-th row of A is a step vector equal cither g(*+1.0) or g(x+1.1), Otherwise, there exists minimal ie in + 1] such that Aμ 1 a. We proceed by contradiction to prove in this setting that Ai 1 for all j 2 k. Suppose there exists a such that A a, then A 8 and
21

---

Published in Transactions on Machine Learning Research (06/2024)
(14) x05) this implies that the following two inequalities are simultancously satisfied,
0 < (2 - (1)) + b(8) (1 (w) + (0)) < (1 - 2a))(w + (())) 0 < (2A.g () ((0) (2a -1) + b()) -(1 (10) + b())..
However, these inequalities clearly contradict one another and therefore we conclude A, is a step vector equal to either g(*.0) or g(k.1)
Conversely, assume the rows of are all step vectors. We proceed to prove S non-emply under this assumption by constructing (w, b) such that sign(w(0)(() + b(9) A. for all j E [n] and any row i i [di]. To this end, let As a E {0, 1}. First, consider the case where Aij for all j E [n]. If a then with
w(() and b(*) --[[x()) it follows that
(0) + 800 < (n) + +000 < <|xx(m)
for all j E |n]. If = 1, then with w( and (6+) = 2//((0)| + 1 we have
(1) bl)) > (1) + 666) 1001++1 +1
for all j E [n]. Otherwise, suppose Ai, is not constant: then by construction there exists a k E {2, nn) such that Ag = a for all j E [ k - 1] and Aij = - a for all j E [k: n]. Letting
( = =22x- - 1),
(10) -(2a 1) (x(h-1) + x0(6)
2
then for any j E [n]
sgn (w 20) + b()) = sgn (2a-1) (2()) x(x--1) + x((k)
=Ay.
Aig.
2
Thus, for any A with step vector rows, given dataset consisting distinct dimensional points we construct network whose preactivations correspond to the activation pattern encoded by A.
In summary, given fixed, distinct one dimensional dataset we have established one-to-one correspondence between the non-empty activation regions and the set of binary matrices whose rows are step vectors. For convenience we refer to these as row-step matrices. As there are 2n step vector rows of dimension n and dj rows A, then there are (2n)di binary row-step matrices and hence (2n)di non-emply activation regions. J
Proof of Lemma 11
By the union bound,
P([n] g (t....,C.)) -
Σ
P(j & (Cr,
Ø=1
Σ (1 - 5)a
j=1
6d
Ø=1
ne
So d ))
P([m) S (Ci,...,CCh,
,,C))) 2 ne
2 E.
This concludes the proof.
22

---

Published in Transactions on Machine Learning Research (06/2024)
Proof of Theorem 10
Consider dataset (X, y) consisting of distinct data points. Without loss of generality
we may index these points such that
x0) < 22 ....6 xl(m)
Now consider a matrix A {0, 10 x whose rows are step vectors and which therefore corresponds a non-empty activation region by Lemma As in the proof of Theorem 5 denote its columns by a {0, 1]4 for [n]. On SX, the Jacobian of F with respect to b is given by
VoF(w,b,e, X) - (o o
vOa!").
We claim that if A has full rank, then VoF(w, u, X) has full rank for all b, u, X with the entries of nonzero. To see this, suppose that A is of full rank, and that
Σ (s(( j=1
for some 01,.... On R. Then for all e [d1],
n
Σ aju,A = 0,
5=1
Σ A,Ay =0.
But A is of full rank, so this implies that a; for all [n]. As result, A full rank then VaF(w, v, X) is full rank, and in particular (ie.b.,) F(w, b, v, X) is rank. Therefore, to show most non-empty activation regions have no bad local minima, it suffices to show most non-empty activation regions are defined by full rank binary matrix A.
To this end, is a binary matrix with step vector rows, we say that is diverse satisfies the following properties:
For all [n], there exists i [d:] such that A, (E(K:0),
2. There exists i [di] such that A,.. g(1,1),
We proceed by i) showing all diverse matrices are of full rank and then ii) non-empty activation regions are defined by a diverse matrix. Suppose is diverse and denote the span of the rows of A by row(A). Then g(l.1) = (1..... 1) E row(A) and for each [n] either g(k.0) or g(k.1) row(A). Observe g(*.0) row(A) then 1 ((k.0) ((k.1) row(A), therefore for all k E [n] g(k.1) E row(A). As the of vectors
(k.1.1) e [m]]
forms basis of I we conclude that all diverse matrices are full rank.
Now we show most binary matrices with step vector rows are diverse. Let A be a random binary matrix whose rows are selected mutually iid from the set of all step vectors. For i [d1], let C, [n + 1] defined as follows: A, E ((t,)) for some & E (2. n), C, 1; otherwise, we define C, = n 1. By definition is diverse if and only if
we define C, = k; if A,, = g(L.)) then we define
[n] C (C1, (C,,...,Ca,) C.,
As the rows of A are chosen uniformly at random from the set of all step vectors, the C₁ are iid and
P(C1 = k) 2 2n
23

---

Published in Transactions on Machine Learning Research (06/2024)
for all & E [n), then by Lemma 11 if d 2 2n log( 2),
((A is diverse) = P([n] S CC.,,,,,,...,).
21-6.
This holds for a randomly selected matrix with step vector rows. Translating this into a combinatorial statement, we see for all but at most a fraction e of matrices with step vector rows are diverse. Furthermore, in each activation region S corresponding to diverse the Jacobian full rank and every differentiable critical point of L is a global minimum.
Proof of Theorem weight,
Let e > 0. We define the following two sets of neurons based on the sign of their output
D1 {i [di] (9) > 0}, Do = {i [di] 000) < <}. Suppose that |Dil, 2 2n lonlog(2 ( Furthermore, without loss of generality, we index the points in the dataset such that
(1)) << x212
(1)).
Now consider a matrix A E {0, 1] xn whose rows are step vectors, then by Lemma 9 A corresponds to a non-empty activation region. We say that A complete if for all k E {O...., - 1} and 8 {0, 1} there exists i [di] such that A., = g(h.)) and sgn(v(()) B. We first show that if A is complete, then there exists global minimizer in Sx. Consider the linear map &p Rd Rd + Rixn defined by
di Σ
p(w,b)=
( (2A.) 1)(w((20)) 200 + ((0)
j=1.....7
Note for (w, b) S then p(w, b) F(w, b, X). As proved in Lemma 20 for every Rixa there exists (w, b) S such that F(w, X) In particular, this means that is surjective and therefore St contains zero-loss global minimizers. Define
V/ = (ww b) E gd x gd (ww 6) = =yh.
then Gx,y n V, ns and by the rank-nullity theorem
dim(V,) = dim(( (fvl)
2d n.
We therefore conclude that if A is complete, then 9x.9 nst is the restriction of a (2d1 - -immmenniin linear subspace to the open set Sg. This equivalent to 9x., n S being an affine set of codimension n as claimed.
To prove the desired result therefore suffices show that most binary matrices with step vector rows are complete. Let A be random binary matrix whose rows selected mutually iid uniformly at random from the set of all step vectors. For 3 {0, 1) and i D3 let Cg., E [n] be defined follows: if Ar, (kk-1,1) for some & E [n] then Cg = k, otherwise C3 n 1. Observe that A is complete if and only if
[n] C (Co, : E Do} and [n] C (Ci. : Di).
Since Uhere are 2n step vectors,
P(C = k)
2m
for all l E [n). So by the union bound and Lemma 11
(PAA is complete)
= P[mm] C (Co, Do}) and [m] S (i D1))
2 1 P[n]] & (Co,: Dol) - P(M] g (Ciii D1H)
c c
2 2 2
1 1-6
24

---

Published in Transactions on Machine Learning Research (06/2024)
As this holds for matrix with step vectors chosen uniformly random, it therefore follows that all but at most fraction e of such matrices are complete. This concludes the proof.
Lemma 20. Let A E (0,1)dxxm be complete, and let X E Rdoxx be an inpptt dalaset with distinct points. Then for any y E R!x", there evists (w, b) E SX such that F(w, b, D, x)) x)=xx)=0 y-
Proof. If A is complete then there exist row indices io.0, i..0.... in- 1,0 E [d1] and io.1, ii,b,... "aa..,naaaa in-1,1 E [di] such that for all & E {o..... 1} and B E 10 the i row of is equal to g(H,1) with ((i.,)) = B. For 3 E {0, 1}, we define
Ig = fio.s.... ................................ .n 1n
We will construct weights w(l), ...., w(d) and biases b(!)..., ,((1) such that (w, b) E S and F(w, b, = y. For i & To UI1, we define w and 6(0) arbitrarily such that
(g + b(0) = Aij
for all j E [n]. Note by Lemma that this is possible as each Ar, is step vector. Therefore, in order to show the desired result it suffices only to appropriately construct w(),bb b() for i E To UZ. To this end we proceed using the following sequence of steps.
First we separately consider the contributions to the output of the network coming from the slack neurons, those with index & To UI1, and the key neurons, those with index i To UZ1. For j E [n], we denote the residual of the target y leftover after removing the corresponding output from the slack part of the network z(J), We then recursively build sequence of functions (1)) in such a manner that (z(0)) = 2(0) for all j S n.
2. Based on this coustruction, select the parameters of the key neurons, i.e., and prove (w, 6) E Sg
for i E IoUZ,
3. Finally, using these paramcters and the function ((n-1) we show F(w, b, =
Step 1: for j E [n] we define the residual
25 =
Σ o0 )(w00))))) (066)+01 66))
(6)
iETOUT,
For j E t0,..., n - 1,, consider the values (60, w6) E R, and the functions g( : R - R, defined recursively across the dataset as
g(0) = sgn( (gn(2(1) (1)))
i (0)
((0) = 11 - (11)
g ( (x) (2 () ((0))
(60 = (gn(=(+1) - 110 (z()+
(ISSSn-1)
( 212(1+1) -1 (z(++)))
(ISsšn-1)
x0++) xbا)
300 (20+1) - 1 (z (xb+t) x0)))
(15jšn-1)
x0+1) zl
(0)(z) = E(23(0) - (8() x +b)
(1
2=
Observe for all j E {l,..., n 1} that wū)) 2 and
n (
الأر (wl) + x(++1)
B()) 0.
2
25

---

Published in Transactions on Machine Learning Research (06/2024)
In particular, x0))(1) 800 of j and w002ا0) 800) 0 otherwise. Moreover, for all j' [n]
i 0 21)) + ((0) = 200 + g00| - x00)
> 0.
We claim that for all j [n], gln-1))(/00) (x(()) z00 For the case j = we compute
((a-1)
Σ (2 1)0((00)))))) + b())
t=0
(2 () 20 x01) + b(0)
(2sgn(=(1) (x) + |301 - x(1))
z())
For j E (2,... , ,0-11 1},
mn 11 (x(d)
(2
1)0(w((0) + ))())
j-1
((2g( ()0 B10))
(2
() 1) (0) (0-11)) + 2
-28B0-1) 1) 1) 1(6 (1) + (15-1)) + (((22)(2())
(2880-2) - 1) + b(5-1)) + (x(6))
(230-11 1) (2)20) 9 (9-6) (x0-0)
11( (266)
+ 2(1-1))
z6) - x(--1
x(1 x(-1)
+ (b0))
(23(-11) -1)]20) -0 (x001)) + -
(2()) - (x)) + g (z
= 2())
Hence, g g(n-11(x(0) = ا00 for all j E [n].
Step 2: based on the construction above we define (w:00,b5 b(0) for i E To U., For k E (0,..., n 1} and
3 E {0, 1}, we define
((.s)) 3 (2g((k)
1)(2,3 1) (k)
2
[
3 (2,g(k)
1)((2
1) (A)
2
|
Now we show that this pair (w. b) satisfies the desired propertios. By construction, we have
(g b10)) Aij
26

---

Published in Transactions on Machine Learning Research (06/2024)
for i 4 IoUII, E [n]. If IJUIi [n], then can write i for some & {0................. .0.....,2 1/, B E {0,1).
Then
3 (2 - 1)(23 1) (z(()2(1)) + 8(())
sgn (g (5) + b(0) sgn
sgn
2/0(04.0)
(g + B(K)
1k<j
Aijz
where the sccond-to-last line follows from the construction of and d and the last line follows from the fact that A,, = g(k.1).
Step 3: finally, show that F(w, b, u, X) y. For j e [n].
F(u,, b, x())
Σ
o ( + b())
Σ
e (00(00)) + b(t)))
Σ
wl ((w(w()))) + b(0))
NEInUI
On o + (lbr,)))
k=0
where the last line follows from
6 By the definition of wlkk)) and ((0,2)) this is equal to
1)(23 - 1) o (1)(k))))) + b(0)). 3+ (23(k)
200 - y0) +
k=U 8=0
By construction sgn(v((..0)) = so the above is equal to
n-1
3 (2 - 1)(28 1)
( 200
Σ
Σ
(28
1)
or (k) + ((h)
2
8=
00 - 20 +
(2 1)0(1((0)2)) + b(0))
k=
90 200 + g (x(6))
0))
We have therefore successfully identified weights and biases (w, b) E $$ such that F(w, b, X) y.
Proof of Theorem 13 We say that binary matrix A with step vector rows is diverse if for all k E [n], there cxists i E [d1] such that A,, = (R..)) Suppose that A is a binary matrix uniformly selected among all binary matrices with step vector rows. Define the random variables Cı,... Cd, E [n + 1] by C, = for some & E [n], and C, = n + otherwise. Since the rows of are iid, the C, are iid. Moreover, for each
k if A,, = ((k.1)
[n], we have P(C, = k) Z L So by Lemma 11
di 2n log (m)
11
then with probability at least 1 -
[n] C (C1, C.
This means that for cach & E [n], there exists i such that C, = (kk,1), In other words, is diverse. Since we chose uniformly at random among all binary matrices with step vector rows, it follows that all but a fraction of such matrices are diverse.
27

---

Published in Transactions on Machine Learning Research (06/2024)
Now it suffices to show that when A is diverse, every Clarke stationary point of L in St x Rd is global minimum. Note that F is continuously differentiable with respect to e everywhere. We will show that (w, b, v, X) has rank n for all (w, b, E S x RRd,, Since A is diverse, there exist ,,,-.,, E [di] such that for all E [n], A = g(R.1), Consider the n x n submatrix M F(w, b, v, X) generated by the rows 1, An. That 18,
OF
Mp pq
(w, b, U, v,
du()))
Then
Mp- = (w + ((a)),
so the entries of M are non-negative, and
sgu(Mpg) = sgn(w (b) + b(b)))
Aipig
=(g(x.))) )4
=142p-
Hence, M is upper triangular with positive entries on its diagonals, implying that rank(M)- = n. Since M is a submatrix of v,, b, v, X), we have rank(V, F(w, b, v, x)) = n as well. Now suppose that (w, b) e S$ Rd is a Clarke stationary point of L. Then since L is continuously differentiable with respect to 1,
Vol(w, b, v, X) V. bl, (F(w, b, x) - 2) =. O.
Since V.F(W, b, v, X) has rank n, this implies that F(w, b, X) = and so (w, v) is global minimizer of F. So whenever A is diverse, the region S x RRd has no spurions Clarke stationary points. This concludes the proof.
Function space on one-dimensional data
We have studied activation regions in parameter space over which the Jacobian has full rank. We can give a picture of what the function space looks like as follows. We describe the function space of ReLU over the data and based on this the function space of network with hidden layer of ReLUs.
Consider single ReLU with one input with bias on n input data points in R. Equivalently, this is a ReLU with two input dimensions and no bias on input data points in 1 x RR For fixed X. denote by Fx = [f(x()),,... ((:")) the vector of outputs on all input data points, and by Fx = (0): 0} the set of all such vectors for any choice of the parameters. For a network with a single output coordinate, this is a subset of TRx As before, without loss of generality we sort the input data as (11 <... < (m()) (according to the non-constant component). We will use notation of the form X2i = [O...., 0, x()) .... x ('))), Further, we write ((()_ = [x] -1]. which is solution of the linear equation (w),x()) = O. Recall that a polyline is a list. of points with line segments drawn between consecutive points.
Since the parametrization map is piecewise linear, the function space the union of the images the Jacobian over the parameter regions where is constant. In the case of single ReLU one quickly verifies that, for 1, Fx R20, and for n 2, Fx R For general n, there will be equality and inequality constraints, coming from the bounded rank of the Jacobian and the boundaries of the linear regions in parameter space.
The function space of a single ReLU on 3 and 4 data points is illustrated in Figure
For a single ReLU, there are 2n non-emply activation regions in parameler space. One of them has Jacobian rank 0 and is mapped to the function, two others have Jacobian rank 1 and are mapped to non-negative scalar multiples of the coordinate vectors é, and c, and the other 2n regions have Jacobian rank 2 and are each mapped to the set of non-negative scalar multiples of line segment in the polyline. Vertices in the list equation 7 correspond to the extreme rays of the linear pieces of the function space of the ReLU.
28

---

Published in Transactions on Machine Learning Research (06/2024)
fa
f4
J2
Figure 4: Function space of a ReLU on data points in R, for 3, 4. The function space is polyhedral cone in the nen-negative orthant of R", We can represent this, up to scaling by non-negative factors, by functions f = (fi...., fa) with fi +... fn = 1. These form a polyline, shown in red, inside the (n - simimee..x The sum m ReLUs corresponds to non-negative multiples of convex combinations of any m points in the polyline, and arbitrary linear combinations of m ReLUs correspond to arbitrary scalar multiples of affine combinations of any points in this polyline.
They are the extreme rays of the cone of non-negative convex functions on X. Here a function on X is convex - )( _(11))=((1)) A non-negative sum of ReLUs is always contained in the cone of non-negative convex functions, which over data points an n-dimensional convex polyhedral cone. For overparameterized network, if activation region in parameter space has full rank Jacobian, then that region maps to n-dimensional polyhedral cone. It contains zero-loss minimizer if and only if the corresponding cone interseets the output data vector y E X
Proposition 21 (Function space on one oneedimenio data). Let X be a list of n distinct points in 1 x R sorted in increasing order with respect to the second coordinate.
Then the set of functions a ReLU represents on X is a polyhedral cone consisting of functions af, where a 2 0 and f an element of the polyline with vertices
z Xei i= 1....,, n and x10xxxx i 1=1, 1,...,
The set of functions represented by sum of m ReLUs consists of non-negative scalar multiples of conver combinations of any m points on this polyline.
The set of functions represented by arbitrary linear combinations of m ReLUs consists of arbitrary scalar multiples of affine combinations of any m points on this polyline.
Proof of Proposition 21 Consider first the case of a single ReLU. We write x00) for the input data points in R. The activation regions in parameter space are determined by the arrangement of hyperplanes H; = {w: (w,x(() 0}. Namely, the unit is active on the input data point z and only the parameter is contained in the half-space H {w: (w, x0)) > 0} and it is inactive otherwise. We write z(0) [x -1], which is row vector that satisfies (z(1), (2)()) O. We write 1s for a vector in Rixn with ones at the coordinates and zeros elsewhere, and write Xs = 1 * X for the matrix in dddn where we substitute columns of whose index is not in S by zero columns.
With these notations, in the following table we list, for each of the non-empty activation regions, the rank of the Jacobian, the activation pattern, the description of the activation region as an intersection half-spaces, the extreme rays of the activation region, and the extreme rays of the function space represented by the
29

---

Published in Transactions on Machine Learning Research (06/2024)
Parameter space
.0(1
x (2)
-20))
Function space
f2
x((2)
H H
HT 0 H
FF1
202
H n
Hj m H
(2)
fi
3:00
F
20)
Figure 5: Subdivision of the parameter space of a single ReLU on two data points 2(),xx( in 1 x R by values of the Jacobian (left) and corresponding pieces of the function space IR (right). The activation regions are intersections of half-spaces with activation patterns indicating the positive ones or, equivalently the indices of data points where the unit is active.
activation region, which is simply the image of the Jacobian over the activation region.
rank
A
extreme rays of S
extreme rays of F
10
Hi
0 H,
a(1) (z(m)
1
11
H nHz
.(), z(2)
e1
2
15
z(1) ((+1))
I00) x X z(1t))
(i = 2,...
2
[mm]
H NTT
f(1), -00)
(1) <n (1) X₂2
2
124
H
111) - 10-1)
x x X)x
(i (i= 2, ....n
1n HH
I(0) (()-1)
Gn
The situation illustrated in Figure 5 (see also Figure 4p. On one of the parameter regions the unit is inactive on all data points so that the Jacobian has rank 0 and maps 0. There are precisely two parameter regions where the unit is active on just one data point, x()) x!*), so that the Jacobian has rank 1 and maps to non-negative multiples of ej and en, respectively. On all the other parameter regions the unit is active at least on two data points. On those data points where the unit is active it can adjust the slope and intercept by local changes of the bias and weight and these are all the available degrees of freedom, so that the Jacobian has rank 2. These regions map to two-dimensional cones in function space. To obtain the extreme rays of these cones, we just evaluate the Jacobian on the two extreme rays of the activation region. This gives item in the proposition.
Consider d1 ReLUs. Recall that the Minkowski sum of two sets M, N in vector space is defined M - N = (f +:: f M,g E N). An activation region & with activation pattern A for all units corresponds to picking one region with pattern (9 for each of the units, = 1,...,d,, Since the paramctrization map is linear on the activation region, the overall computed function is simply the sum of the functions computed by each the units,
F(W, = (w X).
iEds
Here F(W, v, X) E; (XX) the overall function and Flw(() X) = ow the function computed by the ith unit. The parameters and activation regions of all units are independent of each other. Thus
F
Σ F EE|4]
30

---

Published in Transactions on Machine Learning Research (06/2024)
} for the function space of the ith unit over its activation region 8x" This is cone and thus it closed under nonegative scaling,
Here write Jx"
(9) ((af/ul00) wlo0)))
R²: wil Sx
FX = a for all a, 2 2.
Thus, for an arbitrary linear combination of di ReLUs we have
Σ iEId
v0
Σ
( 11
1
cE(di]: 10
Here (1) is an arbitrary function represented by the ith unit. We have Σ, = |1 and Σn E, 1 Thus if f satisfies fi +.....+ = then Σ, | plir of the functions Tyat. If all are non-negative, then 1 2 0 and the affine combination combination. Each of the summands is an element of the function space of single ReLU with entries adding to one.
1, and hence ʃ is an affine combination convex
In conclusion, the function space of a network with one hidden layer of di ReLUs with non-negative output weights is the set non- uon-negative scalar multiples of functions in the convex hull of any di functions in the normalized function space of a single RcLU. For a network with arbitrary output weights we obtain arbitrary scalar multiples of the affine hulls of any d1 functionn in the normalized function space of single ReLU. This is what claimed in items 2 and 3, respectively.
E Details on loss landscapes of deep networks
We provide details and proofs of the results in Section We say that a binary matrix is non-repeating if columns are distinct.
Proposition 22. Let E Rd be an imput dataset with distinct points. Suppose that A is an activation pattern such that At-1 has rank n, and such that Ar is nov-repeating for alll E Then for all E St. has rank n.
Proof. Suppose that A is an activation pattern satisfying the stated properties. We claim that for all W St. E {0..... L 2}, and k E [ni with j * k. that (((Wx00) * ((,,((1), We prove by induction on L The base case = 0 holds by assumption. Suppose that the claim holds for some 1 LE {0.... --33 3}. By assumption, A441 is non-repeating, so the columns (A41)) and (At1)). are not equal. Let i E [de+1] be such that (A+4))s * (Ai-i)ik- Then, since W ES$.
f x1)) + (g ((W,,
This implics that
( + ((( ( ()))
or in other words
(W, + (fin (W,
So fit1 (W, + (())),, proving the claim by induction.
Now we consider the gradient of F with respect to the (L 1)-th layer. Let X Rdc-2xn be defined by X : /1,2(W, X), and for j E [n] let a00 denote the j-th column of X. Let a(1), ... . (n)) denote the rows of Ar-11- Then for all W ESA
Vw F(W,)) ((v 2 a ()) s0 01) .... (v am))) 80 a(1)).
31

---

Published in Transactions on Machine Learning Research (06/2024)
By Lemma 1 the rank of this matrix is equal to the rank of the matrix
(a @ a(1), a!n) @ k!n)).
But A has rank by assumption, the set a (n) is lincarly independent, implying that the above matrix is full rank. Hence, Vwz ,F(,,X) has full rank, and so F(W, has full rank.
Now we count the number of activation patterns which satisfy the assumptions of Proposition 22 and hence correspond to regions with full rank Jacobian.
Lemma 23. Suppose that B E Rd has entries chosen tid uniformly from {0, 1}. If
d= 2 (og ")
then with probability at least 1 -- 6, B is non-repeating.
Proof. For any j.k E [n] with j + k.
P(B., B.,k) P(Bi,
Ba for all i [d]
= 2
So
P(B is non-repeating)
= P((B., + B. for all j, k E [n]] with j + k)
2 1 Σ
P(B., = B.,s))
j.ke(n) jyk
2d2-
If
2 log nt + log
d>
log
then the above expression is at least 1 8.
Lemma 24. Suppose that B Rdxx has entries chosen tid uniformly from f0, 1}. If
d=n+2 log
then with probability al. least. 1 - 8, B has rank n.
Proof. Suppose that d 2 Let B' be d x d matrix selected uniformly al random from {0. 1jddd and let B be the top d x minor of B'. Note that B has entries chosen iid uniformly from {0, 1}. Moreover, B has rank n whenever B' is invertible. Morcover, by Theorem 3 B' will be singular with probability at most C(0.72)4, where C² 2 1 is a universal constant. Then
P(rank B) n) 2 P(B' is invertible)
2 1 - (.0.72)
Setting
C log
d 2
8
log 0.72
we get that the above expression is at least.
C(0.72) lo/(///) log( (00.7)) 8.
Hence, if d 2(log }); then B has rank with probability at least 8.
32

---

Published in Transactions on Machine Learning Research (06/2024)
Proof of Theorem 14 By Proposition 22 it suffices to count the fraction of activation patterns A such that A is non-repeating for I E [T. 2] and A,- has rank n. Tet A be an activation pattern whose entries are chosen iid uniformly from {0, 10. Fix / E [L 2]. Since di = (2(1og(;7)) by Lemma 23 we have with probability at least 1- - 21
< that A is non-repeating. Hence, with probability at least 1- - 2. all of the A for
1 [z. 2] are non-repeating. Since d = n + Q(log ł), by Lemma 24 we have with probability at least. 1 that Ar-1 has rank n. Putting everything together, we have with probability at least
c that A is non-repeating for I E [ 2] and Ar- has rank n. So with this probability, Vw X) has rank n. Since generated the activation pattern uniformly at random from all activation regions, the fraction of patterns A with full rank Jacobian is at least - 6.
F Details on the volume of activation regions
We provide details and proofs of the statements in Section 6
F.1
One- dieeenimnnio input data
Proof of Proposition 15 Let us define vb : (-00, - -0,0 2] by
b(x) 1 (( (tcs.bb E x0.11x1-1,11]
b S })
For E R.
(''
1 [-] lbswedbdw
((0)
(1wS1/1e((1 + wwx) + w1r21 (2))
2
1+ 2
2 2z
ifx21
= (xx).
Moreover, (000 2 = xxx) and (00) = 0 = (oo)) So th = J. For all & E [m + 1), neuron (w, b) has
activation pattern c(k.0) if and only if wz + > 0 and (k) + < 0. So
M(Nu,o ([-1, x 1)) 1
(w: b) 1, 1] | 1| wr k- + 0, (1) b 0))
p ( (w, [0.1] |- wx b < 0, (x) + +b 0}) P (((w..)) [0.1] [-1,1] wi
b < 0, wr(()) - > of)
P (ftu.b b) E [0, x [-1.1] (11-1) <
b
x(() })
w
= ((((1))) (b((kk
Similarly, a neuron (w, b) has activation pattern (Rx,1) if and only if (k- 1) + b < 0 and (x)( + > 0. So
(k) M(Na,1 n ([-1, 1] x [)), = 1 (( (w., E [-1,, [-1, : wa (k + > 0, (k)
+ < 0})
(( (ww, b) E 1- x [-1,1] wa + > 0, wr + < 0))
= P (((w.)b) b) E [0, x [-1, wr (k- 1) + > 0, -wr (+) + b < 0))
(f ((u,))) E 10, 1] x [- (k-1) < < <((i)) })
(b(((()) - (b(x((111)) 1)).
33

---

Published in Transactions on Machine Learning Research (06/2024)
This establishes the result.
If the amount of separation between data points is large enough, the volume of the activation regions separating them should be large. The following proposition formalizes this.
Proposition 25. Let 2. Suppose that for all j, k [n] with k, have |z:00| S 1 and (x - (x) Φ. Then for all k E [n + 1] and B E {0,1},
n n (-1,1
Moreover, for all A E (0, 1jdixn whose rous are step vectors,
mSS n (1-1, x 1-1,11 2 0 di
Proof. Since n 2 2, |11l |22l $ 1, and |m - x2l 2 o, we have
s |
22
$ |.
[222
$ 2.
Let vú 201), (x())) be defined as in Proposition and the assumption that (x:61] < for j E [n],
15
Fix 3 E 13. If 32,3. ...,. then by Proposition
m(Na,3 ([-1,1] x [-1, 1J)) = (zz(t)) ((x(0-1))
(1) (1(-1)
>
4'
If k = L, then
P(N,, a ([-1.1] []), = ((x (2)(00))
x(1)
= 1
1
2
If k = n + 1, then
M(Ni, ([-1,1] x [-1,1]) ((x(n111) (z((1))
(x)
2
1
2
Hence, for all [n + 1] and B E (0. 1}, ((Nr,)) 2 &.
34

---

Published in Transactions on Machine Learning Research (06/2024)
The rows of A are step vectors, for each E [d1], there exists &s E [n 1] and Br {0,1) such that
A = glh..A).
Then
= e) [-1,1] (2Ag 1)(w())() + b() > for all i e [d1]. e [v])
41 III [[( [-1,1] (2Ag 1)(wx()) +b > 0 for all j [n]])
=1
-II [([((wbb) {(111))) [-1,1] (2efku.B)) 1) 1) b) for all e (n|})
d1
(.)
2
i=1
d1
4
Proof of Proposition 16. We use a probabilistic argument similar to the proof of Theorem 10 Let us choose a parameter initialization (w, b) E 1- [-1, uniformly at random. Then the i-th row A,, of the activation matrix random step vector. By Proposition 25 for all [n+ 1] and ,3 E (0,1),
P(A,. = ((K,))) 2 4
(8)
By the proof of Theorem 10 the Jacobian of St is full rank when A is diverse matrix. That is, for all & E [m]. there exists E [di such that A,, E {g(k.0), g(R:1)), and there exists i E [d1] such that A,, ((1.). For i E [d1], let C, E [n + 1] be defined as follows. If A,, E (E(k.0)), g(t.1)) for some k E 3,, ,n), then we define C, = k. A,, = gT,.), then we define C₁ = 1. Otherwise, we define C, = n + 1. By definition, is
diverse and only if
m C {C, : [di]].
By 18
if d1 2 log(()), then for all E [m],
P(C, = j) 2 +
4
Thus, by Lemma
P(A is diverse)
= P(n C (C, E [dil})
> 11-6
This holds for (w, b) selected uniformly from [-1, 1jds x 1- 1jdh Hence, the volume of the union of regions with full rank Jacobian at least
(1 - c) x 11,,1 = (1 - 2d
35

---

Published in Transactions on Machine Learning Research (06/2024)
F.2 Arbitrary dimension input data
Suppose that the entries of W and are sampled iid from the standard normal distribution (0, 1). We wish to show that the Jacobian of the network will be full rank with high probability. Our strategy will be to think a random process which successively adds ncurons to the network, and we will bound the amount of time necessary until the network has full rank with high probability.
Definition 26. For y (0,1), we say that a distribution D on 13" 7-anticcnneebbuule if for all nonzero u R"
Pa-D(u a 0) S 1 7-
Lemma 27. Let y,,c E (0, 1). Suppose that A {0, [0,1]ax is a random matrir whose rows are selected iid from distribulion D on {0, 1 which is a-anticoncentratel. If
8 8log(E
2n
d2
+ 7
7/2
then A has rank with probability at least 1 c.
Proof. Suppose that a!),, a²)) E 10, are selected iid from D. Define the filtration (Fi)ten by letting F, be the o-algebra generated by al2), ..... (!) For L E N, let D, denole the dimension of the vector space spanned by a!)) ... ,ttt), and let
Rs = Dj - yt.
Let w E F2 be an event in which (1),,
(t) do not span R Then there exists u(w) E R nonzero such
that u² (e) = 0 for all 8 S t. Then
P(D++1 D. = (i)(w)) ((a((+1) & ....na [i)((w)
2 PPu"" (0+1) #0 [T)
a (0+1) + 0)
7
where the third line from the independence of the a Hence, for all t E N,
EL (D:41 D.) Fi] LD. E(D41 De Fi]
1D P(De+1 D. Fi)
2 1D
Let be a stopping time with respect to (Fi)sen defined by
(tE:: ft=N D;= n)).
T T: m:=
We also define the sequence (Mi)en by Me Rmin(ter). Then for all i E N,
M| Fi] = Ej B(Rmin((+1.)) Fi]
Ri + 1ese | Fi]
Tr + 11 | Fi.
=I [1 4n (D,41 7(t 1))[F;
=1rsiR, ID 7t + 1) + E( Fi]
2 L.SRR, I 7tt + 1) + 1 D.yn 7 + E D, D, Fi]
= 1rs ID 76 + 1. De
Irse + De
Irg(Rr l,>, Rd
Rmin(te7)
M
36

---

Published in Transactions on Machine Learning Research (06/2024)
where used ( in the sixth line with properties of the conditional expectation. Moreover, have BJMd < co for all & E N. Hence, the sequence (Mi)en is submartinagle with respect. to the filtration for all 8 > 0 and E N,
(Fi)sen. We also have [M++1 - Mel S 1 for all t N. By
P(M: 0) S (M,
M1 S -6)
82
S exp
2(1 - 1)
8
S exp
2t
So for any (0,1); 1);
P(M: S -V 21 22log(()1) Se.
We also have
P(D: S n P(D, S n - 1,7 >1)
P(R
74, >)
P(M S 1 rt,
S P(M, S n 1 - yt)
S (MM S n yt)
So we have De with probability at most when
n - カー -
log(E-1))
Tf
2n 7
t 7
log(c-
then
rVt
7l - 21 logle
= 2 +
V1
v 21 log(6-1)
2
7 2n
7v6
8
+
(og(e-1)-
22
72
n.
Hence, for such values of have D, 2 with probability at least 1 1-e. In other words, with probability at
least 1 - c, the vectors
aa))) span R We can rephrase this as follows. If A E {0, 1)dxn is random matrix whose columns are selected iid from D and
8 d
2n 7
72 log(e 11) +
then with probability at least 1 e, A has full rank. This proves the result.
Now we apply this lemma to study the rank of the Jacobian of the network. We rely on the observation that an input dataset X is 7-anticoncentratee exactly when Dx is r-anticoncentrated.
Proof of Theorem 17 We employ the strategy used in the proof of Theorem
The Jacobian of F with
respect to W is given by
Vw FWW ((v ( & (,) (w (()) ((()).
where (0 is the activation pattern of the j-th data point. With probability 1, none of the entries of u are 0. So by Lemma 4 this Jacobian is of full rank when the set.
(a x : [n])
37

---

Published in Transactions on Machine Learning Research (06/2024)
consists of linearly independent elements of Rd We may partition [n]] into do subsets S1, Sd such + 1 for all k E [r] and partition the columns of A accordingly into blocks (a(*) ses. for each k E [r]. Let M₁. denote the d, x |S&] matrix whose columns the a(*), k. Then the rows of Mg are activation patterns of individual neurons of the network. So the rows of Mr are iid and distributed according to Dx. Since Dx is 7-anticoncentrated and
that |S -
n
do
do
n
di 2 72
log
+
+
do
do
S|5k
2 log
+
we have by Lemma 24 that with probability at least 1 - de Mr has rank |Sa]. So with probability at least e, all of the My have full rank. This means that for each k,
rank(fa :ia(((a:iEe :E Sz}) = |Sa|-
Then by Lemma 18
rank(fa 8x : [n|}) = n,
so the Jacobian has rank n.
G Details on the experiments
We provide details on the experiments presented in Section the number of activation regions that contain global optima, illustrating Theorem 12 Experiments were
7 In addition, we provide experiments evaluating
implemented in Python using PyTorch (Paszke et al. 2019), numpy (Harris al. 2020), and mpi4py (Dalcin)
et al. 2011). The plots were created using Matplotlib (Hunter 2007). The experiments in Section G.1 were
run the CPU of MacBook Pro with an M2 chip and &GB RAM. The experiments in Section G.2 were
run a CPU cluster that uses Intel Xeon IceLake-SP processors (Platinum 8360Y) with 72 cores per node
and 256 GB RAM. The computer implementation of the scripts needed to reproduce our experiments can be
found at httpps//anooymouss .ooee sclence/r/loss lanessspeeen
G.1 Non-empty activation regions with full rank Jacobian
We sample datasct X E R whose entries are sampled iid Gaussian with mean 0 and variance 1. We use a two-layer network with weights W dgd xdo and biases b E Rd initialized iid uniformly on [ va
We choose a random activation region by evaluating at parameters (W, and dataset X. Then we compute the Jacobian of F on this activation region, and record whether or not it of full rank. We repeat this 100 times to estimate the probability of the Jacobian being of full rank for randomly sampled activation region. We calculate this for various values of do, and dj. The results are reported in Figure and Figure
G.2 Non-empty activation regions with global minimizers
We sample data X, y follows. The input data X is generated as independent samples from uniform distribution on the cube 1]4, We consider three types of samples for the labels y::
Polynomial: We construct a polynomial of degree with the coefficients sampled from a uniform distribution on the interval [-1,1]: The labels then the evaluations of this polynomial at the points from X.
We construct a teacher network with an identical architecture to the main network used in the experiment. Then we initialize it with the same procedure as described below for the main network, which acts as a student network in this setup, and take the outputs of the teacher network X the labels.
Teacher:
38

---

Published in Transactions on Machine Learning Research (06/2024)
Random output: We sample labels from uniform distribution on the interval [-1,1].
We sample activation regions as follows. For each experiment trial, we construct a ReLU fully-connected network with do imputs, d1 hidden units, and 1 output. Weights and biases of the hidden units are sampled iid from the uniform distribution
the interval |- 6-v6/fan-in, v /6/fan-in] according to the uniform-He initialization (He et al. 2015 The weights of the output layer are initialized alternating and -1 and Additionally, we generate a new dataset X, for each experiment trial. Afterward, we consider an activation pattern A corresponding to the network and the input data X.
look like -1.-1.1.-1..
For a given dataset (X and activation pattern A, we look for a zero- loss global minimizer to the linear regres- 1 sion problem: minger 1)46 11 -- subject to f E St, where E [R(o++))dxx1 a flattened matrix of the first layer weights and X E R=x(do+1)d is a vector with entries Xjx = U mod di As(k di) x3(k/d.)+ y E R kn, Here we appended the first layer biases to the weight rows and appended to each network input. Following the descriptions given in Section 3 the second condition a system of linear inequalities. Thus, this linear regression problem corresponds to the next quadratic program:
min 6ER ((d+)((++))
where P P= 8 + 9"'0,
= xx
(2A.) - () x 20) > 0 for all E [di].j [m].
We record the percentage of sampled regions with a zero-loss minimizer. This is reported in Figures 6 7 for the three different types of data and dg = 1, 5. The result is consistent with Theorem 12 in that, for dg = 1, the minimal width d1, needed for most regions to have a global minimum, is close to di ~ n log predicted by the theorem. We believe that this dependence will be relatively precise for most datasets. However, for specific data distributions, the probability of being a region with a global minimum might be larger. In Figure 6 we see that, for instance, for data on a parabola, there are more interpolating activation regions than for data from teacher network random data. For higher input dimensions, observe in Figures and g that most of the regions contain global minimum which is consistent with Theorem 5 and Corollary by which any differentiable critical point in most non-empty activation regions is global minimum.
Complementary to the above experiments, we conduct a further experiment now using the MNIST data set, which consists of real data with dg = 784. The result reported in Figure 9b This again aligns well with the theory.
Our figures are reminiscent of figures in the work of Oymak Soltanolkotahi (2019) They showed for shallow ReLU networks that if the number of hidden units is large enough, ddi On² /do, then gradient descent from random initialization converges to global optimum. Empirically they observed phase transition at roughly (but not exactly) dodj = n for the probability that gradient descent from a random initialization succossfully fits n random labels. Note that, in contrast, we are rocording the number of regions that contain global optima.
39

---

Published in Transactions on Machine Learning Research (06/2024)
1000
1000
1000
Network width
800
80
Network width
800
80
Network width
800
80
60
60
60
600
600
600
40
40
40
400
400
400
20
20
20
200
200
0
40
50
Data size
Data size
Data size
(a) Polynomial data, degrve
(b) Polynomial data, degree 2.
(c)
Polynomial data, degree 10.
1000
100
1000
100
1000
100
Network width
80
Network width
800
80
Network width
800
80
60
60
60
600
600
40
400
20
20
20
200
200
0
200
10
20
30
40
10
20
30
40
50
10
20
30
Data size
Data size
Data size
(d) Polynomial data, degree 100.
(e) Teacher-student setup.
(f) Random output.
Figure 6: Percentage of randomly sampled activation regions that contain a global minimum of the loss for the networks with input dimension do 1, depending the size of the dataset and the width dj of the hidden layer. The results are based on 140 random samples of the activation region for each fixed value of n, dj. The target data is the same for each random network initialization for the same combination of n and dj. The black dashed line corresponds to the lower bound on di estimated for a given n and e 0.1 based on the condition on the number of the negative and positive weights in the last network layer from Theorem Preciscly, it represents the function d1 4n log(2n/c).
100
800
100
800
100
Network width
80
Network width
Network width
80
600
600
600
60
60
350
40
350
350
40
20
20
100
100
100
10
60
35
80
10
60
Data size
Data size
Data size
(a) Polynomial data, degree 2.
(b) Teacher-student setup.
(c) Random output.
Figure 7: Percentage of randomly sampled activation regions that contain a global minimum of the loss for networks with input dimension dg 2, depending on the size n of the dataset and the width d, of the hidden layer. The results based on 100 random samples of the activation region for each fixed value of n, dj. The target data is the same for each random network initialization for the same combination of n and d1.
40

---

Published in Transactions on Machine Learning Research (06/2024)
600
100
600
100
600
100
Network width
98
Network width
Network width
98
96
96
96
350
350
350
94
94
94
100
100
100
90
90
90
10
35 Data size
60
Data size
Data size
(a) Polynomial data, degree 2.
(b) Teacher-student setup.
(c) Random output.
Figure 8: Percentage of randomly sampled activation regions that contain a global minimum of the loss for networks with input dimension dg 5, depending on the size n the dataset and the width d1 of the hidden layer. The results based 100 random samples of the activation region for each fixed value of n, di. The target data is the same for each random network initialization for the same combination of and d1.
15
100
105
100
Network width
90
Network width
80
11
80
60
60
700
40
35
60
20
10
500
3000
5500
7500
50
200
350
500 620
Data size
Data size
(a) (%) Full rank Jacobian at initialization
(b) (%) Convergence of GD to global minimizer
Figure 9: Classification task on MNIST to predict one hot binary class vectors. These heatmaps show percentages out 100 trials of networks trainod with GD from a random Gaussian initialization which (a) have a full rank Jacobian at initialization, (b) achieve a cross-entropy loss of most 10-2 after 1000 epochs. The number of network parameters matches the training set size n when the width satisfies d, n//n, where for MNIST the input dimension is do 784. As do is large our results predict that there should exist some linear scaling of the network width d, and the data size such that in all but very small fraction of regions every critical point is global minimum.
41


Reviews:
[{"review_id": "Prb3zeVL9c", "reviewer": "Reviewer_KMaC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like this paper. It considers the largely studied problem of loss landscape of neural networks, by leveraging the piecewise linear structure of ReLU networks. The techniques of the main proofs are really nice and interesting. The technical results are sound and the setting is clear.\n\nThe main weakness in my opinion is the specificity of the considered settings/results, but analysis of even two layer ReLU networks is known to be very intricate. This specificity is thus not a major problem in my opinion.\n\nI just have one question. In Section 4, you allow for a bias term in the parametrisation. Could you adapt the results of Section 3 to the presence of such a bias term? In general, we argue that a bias can be added by appending a 1 coordinate to all the $x_k$. However, here it does not seem possible, as it would restrict the dataset to a zero measure set (and that the results hold up to a zero measure set). So I was wondering if there would be another way to still adapt the proof techniques/results of Section 3 if we also add a bias term in the parametrisation.\n\n---------------\nMinor remarks:\n - the mention of lazy training in the introduction is confusing. To me, this is a completely different problem as the NTK regime is about optimisation (training dynamics)\n - what does *proper* mean in proper algebraic subset? (Lemma 1). I guess this mean not $\\mathbb{R}^d$, but this should be clarified\n - Page 6, after introducing the step vectors, I guess the 0 and 1 should be in bold (vectors)\n - page 7: \"contain a set of global minima of significant codimension and do not contain any local minima\": I guess it should be any **bad** local minima", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims at describing the loss landscape of mildly overparametrized ReLU networks. It does so by studying the activation regions, where the network behaves linearly.\n\nThe authors first show that for a large fraction of these regions, any local minimum is actually a global minimum. However it does so by counting some regions that are actually empty (in the regime $d<n$). The authors then refine their analysis in the case of univariate data (allowing for a bias term in the parametrisation) to show that a large fraction *among the non-empty regions* satisfy the previous property. \n\nLastly, the authors extend their result to deeper architectures and non-differentiable points, as well as illustrate their findings with experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides my minor remark, I would like the authors to comment whether their results of Section 3 could be adapted to account for bias terms in the parametrisation", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xXiwSFJmNH", "reviewer": "Reviewer_X4xc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:** \n\nThe paper is well written. The required algebraic background is provided in Sections 2 and 3. In addition, providing some basic experiments for this theory paper is also positive. \n\n**Weaknesses:** \n\nLemma 2 does hold only for quadratic loss. How can the rank of the Jacobian of the map $F$ is used for a more general loss and setting for example cross-entropy loss?\n\n\nTheorem 5 does not show if we run gradient descent or stochastic gradient descent initialized at some point in the parameter space, which activation region is achieved. The bound on the number of good activation regions is useful but we do not know where the typical learning algorithms will converge. \n\n\nGiven that targets $y$ are single dimensional, scenarios with single dimension inputs, i.e., Section 4 are very limited in the scope. I am not sure about a concrete application where we use single input dimension and single output dimension problem with an overparameterized neural network.\n\n\nSome important and relevant references are missed although maybe under different settings such as the data distribution or type of activations, I think they are highly relevant to this paper: \n\nKenji Kawaguchi and Jiaoyang Huang. Gradient descent finds global minima for generalizable deep neural networks of practical sizes. In Annual Allerton Conference on Communication, Control, and Computing, 2019.\n\n\nChaehwan Song,, Ali Ramezani-Kebrya, Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Subquadratic overparameterization for shallow neural networks. In Advances in Neural Information Processing Systems, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study the rank of Jacobian of the parameterization map over a finite input dataset for ReLU neural networks. The authors examined the loss landscape for various scalings of input features, hidden dimensions, and number of data points, and establish lower bounds on the number of parameters that is sufficient to have no bad local minima. \n\nThe  main intuition behind their better scalings is due to  considering qualitative aspects of the loss landscape, using only the\nrank of the Jacobian rather than the smallest eigenvalue of the neural tangent kernel.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Addressing the weaknesses specified in the previous section.", "broader_impact_concerns": "No concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NC1PlcDyo1", "reviewer": "Reviewer_MJDY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* Overall, the theory of this paper is interesting and compelling.\n* The paper extends results from shallow nets to deep ReLU networks.\n\n## Weaknesses\n\n* Broadly, the motivation of this paper seems a little weak. In [1], the authors show that saddle points, not local minima, are the main impediments in gradient-based optimization. However, this paper focuses on (the lack of) local minima as the source of a favorable loss landscape.\n* In Page 5, the equation at the top has some odd notation. Specifically, $\\langle a, b \\rangle = a^T b$ is typically used for dot products between vectors of the same dimension; however, $w^{(i)} \\in \\mathbb{R}^{d_0}$ and $x^{(j)} \\in \\mathbb{R}^n$. I'm assuming you instead mean a standard matrix multiplication $x^{(j)} w^{(i)}$, which would yield a matrix of dimension $\\mathbb{R}^{n \\times d_0}$, so that the pre-multiplication would yield the correct dimensions.\n* It's unclear if Corollary 7 is broadly useful, since it requires a wide dataset.\n* Before Proposition 8, the authors should introduce the conv notation (which is only discussed in the proof in the appendix).\n* Typo: Page 5, after Theorem 5: \"The takeaway [...] do no contain\" --> \"do not contain\".\n\n[1] Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014). Identifying and  attacking the saddle point problem in high-dimensional non-convex  optimization. *Advances in neural information processing systems*, *27*.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents theoretical results showing that in a mildly overparameterized setting, only a small fraction of the loss landscape has local minima. These results are first shown on 2-layer ReLU networks, and then extended to the deep ReLU network setting. Bounds on the fraction of the volume with local minima are also provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please contextualize this work in the literature studying saddle points, especially the Dauphin et al. paper above, and distinguish why this paper's contributions are relevant in that context.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IK2K9JF4P5", "reviewer": "Reviewer_nzLH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**.\n\n- The mathematical description is accurate and carefully written. The proofs are easy to read and understand, as the proof sketch and supplementary explanations explain known results and concepts.\n- The number of parameters is $O(n)$ or $O(n \\log n)$ to suffice the non-existence of bad local minima with high probability. This order is relatively realistic for practical NNs.\n- No-bad-local-minima theorems are shown for multi-layer NNs.\n\n**Weaknesses**.\n\n- I have a question about the interpretation of numerical experiment results. Specifically, the boundary of whether or not an NN is in the no-bad-local-minima regime is identified as $d_1 \\sim \\frac{n}{d_0}$ (Figure 1) or $d_0\\sim n$ (Figure 2). However, if I do not miss any information, the procedure for determining the boundary is not stated. I suggest determining the boundary quantitatively.\n\n\n**Claims And Evidence**.\n\nThe main claim of this paper is that there are no bad local-minima theorems with mildly overparametrized ReLU NNs. The main theorems appropriately formulate this claim mathematically. Furthermore, the proof is correct as far as I have checked.\n\n**Audience**.\n\nIt is known that overparametrized NNs can achieve zero error (interpolation regime) and still have good generalization performance. So far, the non-existence of bad local minima has been shown for over-parameterized NNs under various settings. However, in most cases, the network size is unrealistically large compared with the sample size. This paper shows no-bad-local-minima theorems for ReLU NNs, with $O(n)$ or $O(n \\log n)$ units under appropriate conditions, where $n$ is the sample size. This result interests TMLR readers because it reveals the interpolation regime of overparametrized NNs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of learning one-layer or multi-layer over-parameterized ReLU neural networks (NNs) using squared error for regression problems. It is shown that mildly over-parametrized neural networks do not have bad local minima (i.e., local minima that are not global minima) under appropriate conditions with high probability in terms of the counts or volume of activation regions in the parameter space. More specifically, this paper shows the followings claims ($n$ is the sample size, $d_0$ is the input dimension $d_l$ is the number of units in the $l$-layer):\n\n- Suppose the NN has one hidden layer. If $d_1\\geq \\max (\\frac{n}{d_0}, \\Omega (\\log\\frac{n}{\\epsilon d_0}))$, then there is no bad local minima in activation regions with a fraction of $1-\\epsilon$ (Theorem 5). Furthermore, if $d_0\\geq n$, there are no bad local minima, and the global minima are zero loss in non-empty activation regions with a fraction of $1-\\epsilon$ (Corollary 7).\n- Suppose the NN has one hidden layer and one-dimensional input. If $d_1 \\geq 2n \\log(\\frac{n}{\\epsilon})$, there are no bad local minima in non-empty activation regions with a fraction of $1-\\epsilon$ (Theorem 10). Furthermore, if the second layer has positive and negative weights greater than $2n\\log \\frac{2n}{\\epsilon}$, respectively, then the global minima are zero-loss, and the codimension of the set of global minima is greater than or equal to $n$ (Theorem 12, 13).\n- Suppose the NN has $L-1$ hidden layers, and the input is one-dimensional. If $d_l=\\Omega (\\log \\frac{n}{\\epsilon L})$, and $d_{L-1}=n+\\Omega (\\log \\frac{1}{\\epsilon})$, there is no bad local minima in the activation region  with a fraction of $1-\\epsilon$ (Theorem 14)\n- Suppose the NN has one hidden layer and one-dimensional input. If the input data points are separated from each other by the distance $\\phi$ and $d_1\\geq \\frac{4}{\\phi}\\log \\frac{n}{\\epsilon}$, the fraction of volumes for which bad local minima can exist is at most $\\epsilon$ (Proposition 16). When the input dimension is arbitrary, if the input data is $\\gamma$-anti concentrated and $d_1\\geq \\frac{8}{\\gamma}\\log \\frac{d_0}{\\epsilon} + \\frac{2}{\\gamma}(\\frac{n}{d_0} + 1)$, then the fraction of volume for which bad local minima exist is at most $\\epsilon$ (Theorem 17).\n\nNumerical experiments investigate the relationship between the sample size, the number of units in hidden layers, and the number of global minima using randomly initialized or trained NNs and synthesis or MNIST datasets to check consistency of real NNs with the theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Section 1.1: *By appealing [...], we show for most choices of activation patterns that the Jacobian will have full rank*: I think *we show that the Jacobian will have full rank for most choices of activation patterns* is easier to read.\n- Section 1.2: *As indicated above, several works have studied sets of local and global critical points of two-layer ReLU networks, so it is in order to give a comparison.*: This sentence needs to be clarified. What does comparison mean, and which works does the authors intend?\n- Section 3: The paragraph before Proposition 8 discusses the identity of the non-empty region. However, I needed help understanding what the identity means in the first reading. It would be better to explain the term in more detail in the main text, similar to the following sentence in the Appendix.\n    - We are also interested in the specific identity of the non-empty regions, that is, the sign patterns that are associated with them.\n- Section 3, Theorem 5: *with nonzero entries for $v$*: Does it mean that we assume $v$ satisfies $v_i \\not = 0$ for all $i$?\n- Section 3: As with Sections 4--6, it is preferable to add the pointer to Appendix A and B, which have proofs for theorems in Section 3.\n- Section 4.1: $\\mathcal{S}^{A}_{X}$ denotes the activation region both with and without boundaries. Although readers likely identify which are referred from the context, using different notations to clarify that they are different concepts is preferable.\n- Section 6.1, Proposition 16: $\\mu(\\cup \\{ \\mathcal{S}^{A}\\_X \\cap [-1, 1]^{d\\_1} \\times [-1, 1]^{d\\_1} \\colon \\nabla\\_{w, b}F \\text{ has full rank on } \\mathcal{S}\\_{X}^{A}\\})$: I think this should be $\\mu(\\{(w, b)\\in [-1, 1]^{d_1} \\times [-1, 1]^{d\\_1} \\colon \\nabla\\_{w, b}F \\text{ has full rank on } \\mathcal{S}\\_{X}^{A}\\})$\n- Section 6.2: $(F: \\mathbb{R}^{d_1\\times d_0} \\times \\mathbb{R}^{d_1}) \\times \\mathbb{R}^{d_0} \\to \\mathbb{R}$ -> $F: \\mathbb{R}^{d_1\\times d_0} \\times \\mathbb{R}^{d_1} \\times \\mathbb{R}^{d_0} \\to \\mathbb{R}$\n- Section 6.2: Let us take $u\\in \\mathbb{R}^n$ to be defined by $u_i=1$ [...] -> $u_j = 1$\n- Section 6.2: $\\mathbb{P}\\_{a\\sim \\mathcal{D}\\_X}(u^T a = 0) = \\mathbb{P}\\_{a\\sim \\mathcal{D}\\_X}(a\\_i = a\\_k)$ -> $\\mathbb{P}\\_{a\\sim \\mathcal{D}\\_X}(u^T a = 0) = \\mathbb{P}\\_{a\\sim \\mathcal{D}\\_X}(a\\_j = a\\_k)$\n- Section 6.2: $\\mathbb{P}\\_{w\\sim \\mathcal{N}(0, I)}(\\left< w, x^{(n)} \\right> = 0)$ -> $\\mathbb{P}\\_{w\\sim \\mathcal{N}(0, I)}(\\left< w, x^{(n)} \\right> \\leq 0)$\n- Appendix G: There is no reference to Figure 9 in the paragraphs in the Appendix.", "broader_impact_concerns": "This study does not any concern on ethical implications specific to it.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After careful consideration of the reviewers' comments, I support the acceptance of this paper. It justifies its claims with precise mathematical descriptions and clear proofs. Despite the noted weaknesses regarding the lack of gradient descent analysis and the limitations of the model in Section 4, the paper's theoretical insights and new proof techniques make a valuable contribution to the field, meeting the acceptance criteria of TMLR.
Decision: Accept (poster)