No Spurious Local Minima: on the Optimization Landscapes of Wide and Deep Neural Networks
Authors: Johannes Lederer
Venue:  (2021)

Abstract: Empirical studies suggest that wide neural networks are comparably easy to optimize, but mathematical support for this observation is scarce. In this paper, we analyze the optimization landscapes of deep learning with wide networks. We prove especially that constraint and unconstraint empirical-risk minimization over such networks has no spurious local minima. Hence, our theories substantiate the common belief that increasing network widths not only improves the expressiveness of deep-learning pipelines but also facilitates their optimizations.

Under review as a conference paper at ICLR 2021
No SPURIOUS LOCAL MINIMA: ON THE OPTIMIZATION LANDSCAPES OF WIDE AND DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Empirical studies suggest that wide neural networks comparably easy op- timize, but mathematical support for this observation is scarce. In this paper, we analyze the optimization landscapes of deep learning with wide networks. We prove especially that constraint and unconstraint empirical-risk minimization over such networks has no spurious local minima. Hence, our theories substantiate the common belief that increasing network widths not only improves the expressiveness of deep-learning pipelines but also facilitates their optimizations.
INTRODUCTION
Deep learning depends on optimization problems that seem impossible to solve, and yet, deep- learning pipelines outperform their competitors in many applications. A common suspicion is that the optimizations are often easier than they appear to be. In particular, while most objective functions nonconvex and, therefore, might have spurious local minima, recent findings suggest that optimizations are not hampered by spurious local minima as long as the neural networks are sufficiently wide. For example, Dauphin et al. (2014) suggest that saddle points, rather than local minima, are the main challenges for optimizations over wide networks; Goodfellow et al. (2014) give empirical evidence for stochastic- -tochastic-rradient descent converge to a global minimum of the objective function of wide networks; Livni et al. (2014) show that the optimizations over some classes of wide networks can be reduced a convex problem; Soudry Carmon (2016) suggest that differentiable local minima of objective functions over wide networks are typically global minima; Nguyen & Hein (2018) indicate that critical points in wide networks are often global minima; and Allen-Zhh et al. (2019) and Du et al. (2019) suggest that stochastic-gradies descent typically converges to global minimum for large networks.
These findings raise the question of whether common optimization landscapes over wide (but finite) neural networks have no spurious local minima altogother.
Progress in this direction has recently been made in Venturi et al. (2019) and then Lacotte & Pilanci (2020). Broadly speaking, we call a local minimum spurious if there is no nonincreasing path to global minimum (see Section 2.2 for formal definition). While the absence of spurious local minima does not preclude saddle points or suboptimal local minima in general, it means that one can move from every local minimum to global minimum without increasing the objective function at any point-see Figure for an illustration. Venturi et al. (2019) prove that there are no spurious local minima if the networks are sufficiently wide. Their theory has two main features that had not been established before: First, it holds for the entire landscapes caadhe rather than for subsets of them. This feature crucial: even randomized algorithms typically converge to sets Lebesgue measure zero with probability one, that is, statements about "almost all" local minima are not necessarily meaningful. Second, their theory allows for arbitrary convex loss functions. This feature is important, for example, in view of the trends toward robust alternatives of the least-squares loss (Belagiannis et al., 2015; Jiang et al., 2018; Wang et al., 2016). On the other hand, their theory has three major limitations: it is restricted to polynomial activation, which is convenient mathematically but much less popular than ReLU activation, it disregards regularizers and constraints, which have become standard in deep learning and in machine learning at large (Hastie et al., 2015), and it restricts to

---

Under review as a conference paper at ICLR 2021
[ppe)
global minima
saddle
spurious minimmun
Figure I: spurious local minimum of a hypothetical objective function
shallow networks, that is, networks with only one hidden layer, which contrasts the deep architectures that are used in practice (LeCun al., 2015).
Lacotte & Pilanci (2020) made progress two of these limitations: first, their theory caters to ReLU activation rather than polynomial activation; second, their theory allows for weight decay, which is standard way to regularize estimators. However, their work is still restricted to one-hidden-layer networks. The interesting question is, therefore, whether such results can also be established for deep networks. And more generally, it would be highly desirable have theory for the absence of spurious local minima in a broad deep-learning framework.
In this paper, establish such theory. We prove that the optimization landscapes of empirical-riss minimizers over wide feedforward networks have no spurious local minima. Our theory combines the features of the two mentioned works, as it applies to the entire optimization landscapes, allows for a wide spectrum of loss functions and activation functions, and constraint and unconstraint estimation. Moreover, it generalizes these works, as allows for multiple outputs and arbitrary depths. Additionally, our proof techniques are considerably different from the ones used before and, therefore, might be of independent interest.
Guide to the paper Sections 2 and 5 are the basic parts of the paper: they contain our main result and a short discussion of its implications. Readers who are interested in the underpinning principles should also study Section 3, and readers who want additional insights the proof techniques referred to Section 4. The actual proofs are stated in the Appendix.
2 DEEP-LEARNING FRAMEWORK AND MAIN RESULT
In this section, we specify the deep-learning framework and state our main result. The framework includes a wide range of feedforward neural networks; in particular, it allows for arbitrarily many outputs and layers, a range of activation and loss functions, and constraint as well as unconstraint estimation. Our main result guarantees that if the networks are sufficiently wide, the objective function of the empirical-rist, minimizer does not have any spurious local minima.
2.1 FREDFORWARD NEURAL NETWORKS
We consider input data from a domain Dz Rd and output data from a domain Dy R Typical examples are regression data with D, = Rm' and classification data with D, = = We model the data with layered, feedforward neural networks, that is, we study sets of functions
g = (ge
DD
m θ M) c G == {ge Dr - Rmm O with
gelz) = 0/p [0--1 ... [ for x E Dz
(1)
and
M McM = (e - (o'.....0)) e EERR "
The quantities pd d and p/+1 are the input and output dimensions, respectively, 7 the depth the minimal width of the networks. The functions
of the networks, and w = pi Iep IF' are called the activation functions. We assume that the activation functions elementwise functions in the sense that (bbb (f'(6))...., (.b...,,((bbb))) T for all b E RP where F' R + R is an arbitrary function. This allows for an unlimited variety in the type of activation, including ReI.U f b + max(0, b), leaky ReLU p b b max b) min cb) for fixed
2

---

Under review as a conference paper at ICLR 2021
E (0, polynomial f' + cb for fixed E (0, oo) and k [1), and sigmoid activation p : b 1/(1+ =) as popular examples, and it allows for different activation functions in each layer.
We study the most common approaches to parameter estimation in this setting: constraint and unconstraint empirical-risk minimization. The loss function I R R + R is assumed convex in its first argument; this includes all standard loss functions, such as the least-squares loss [ (a, b) + la - b|ž. the absolut-deviation loss [ (a. b) + ||a b/1 (both typically used for regression), the logistic loss I (a,b) + -(1 + b) log(1 + a] - (1 - b) log(1 - al. the hinge loss I: (a, b) max ab} (both typically used for binary classification Dy = {=1)), and so forth.
The optimization domain is the set
M:= f M: [
for a constraint t : M - IR. Given data (1), ..... (In, yn) E Dr x Dy, the empirical-risk with
minimizers then the networks a
Σ [0e [2,) 100
arg min θEM
erm
It has been shown that constraints facilitate the optimization well improve generalization see Krizhevsky et al. (2012) and Livni et al. (2014), among others. For ease of presentation, we limit ourselves the following class of constraints:
r [[]] := max for max jE(.....
||0' I1 b11",111"lll))
for all E M
for fixed tuning parameters a,, b E oo), a parameter E (0, oo). and || |l, the usual row-wise ey "-norm," that is, ||@'ll == max, E (e)) &ss ( for E (0, oo) and | [0]] == max (0) (0))
This class of constraints includes the following four important cases:
Unconstraint estimation: a, b,
In other words, M MM. Unconstraint estimation had been the predominant approach in the earlier days of deep learning and is still used today (Anthony & Bartlett, 1999).
Connection sparsity: q=1
This constraint yields connection-sparse networks, which have received considerable attention recently (Barron & Klusowski, 2018; 2019; Kim et al., 2016; Taheri et al., 2020).
Strong sparsity: q
Nonconvex constraints have been popular in statistics for many years (Fan Li, 2001: Zhang, 2010), but our paper is probably the first one that includes such constraints in a theoretical analysis in deep learning.
Impul constraints: dr O.
Some researchers have argued for applying certain constraints, such node-sparsity, only to the input level (Feng & Simon, 2017). In general, while our proof techniques also apply to many other types of constraints, there are two main reasons for using the mentioned sparsity-induiing constraints to illustrate our results: First, sparsity has become very popular in deep learning, because it can lower the burden on memory and optimization as well as increase interpretability (Hebiri & Lederer, 2020). And second, the above examples allow us to demonstrate that the discussed features of wide networks do not depend on smooth and convex constraints such as weight decay.
Our theory can also be adjusted to the regularized versions of the empirical-risk minimizers, that is, for the networks indexed by any parameter in the set
[ge x.), v.] + 1
arg min GEM
3

---

Under review as a conference paper at ICLR 2021
The proofs virtually the same as for the constraint version;; omit the details for the sake of brevity.
One line of research develops statistical theories for constraint and unconstraint empirical-ric -rik minimizers- sce Bartlett & Mendelson (2002) and Lederer (2020), among others. As detailed above, empirical-risk minimizers the networks whose parameters are global minima of the objective function
+ + [[9o]
Σ [zee v.
over M for fixed data (21, ..... (In: yn.) While the function ße + [ge] is convex by as- sumption, the objective function @ + [ge] is usually nonconvex. It is thus unclear, per se, whether deep-learning pipelines can be expected to yield global minima of the objective function and, therefore, whether the statistical theories valid in practice. Our goal is, broadly speaking, to establish conditions under which global minimization of (4) can indeed be expected.
2.2 ABSENCE OF SPURIOUS LOCAL MINIMA
We now show that the objective function (4) has no spurious local minima if the networks are sufficiently wide. Recall that a parameter O E M that satisfies
Iggl| < [[rr]
for all I E M with ||e- -
s s
for constant E (0, 00) and norm ||.| on MM is called local minimum of the objective function (4),
If the statement holds for every C (0, oo), the parameter θ is called a global minimum.. Objective functions in deep learning have typically many local and global minima; important question is whether there are "bad" local minima, that is, suboptimal local minima that are difficult to escape from. We formalize this notion follows:
Definition 1 (Spurious local minima). Let O M be local minimum of the objective function (4).
If there is no continuous function h : [0.1] + M that satisfies (i) b[0] = e and h[1] = I for
global minimum I M of the objective function (4) and (ii) t + [[6b4]] is nonincreasing, we call
the parameter θ a spurious local minimum.
See again Figure for an illustration.
The following theorem is our main result:
Theorem 1 (Absence of spurious local minima). Consider the setup of Section 2.1. I 2 2m(n+1)), the objective function (4) has no spurious local minima.
In other words, empirical-risk minimization over sufficiently wide networks does not involve spurious local minima. Hence, as long as there are means to circumvent saddle points (Dauphin et al., 2014), it is reasonable to expect that algorithms can find global minimum and, therefore, that the known statistical theories for empirical-risk minimizers apply in practice.
The theorem applies very broadly. First, it includes all local minima rather than "many" or "almost all" local minima. This feature is important, because even randomized algorithms usually converge to few, fixed points with high probability. Second, the framework allows for arbitrary convex loss functions. This feature caters, for example, to a current trend toward robust alternatives of the least-squares loss function (Barron, 2019; Lederer, 2020). Third, the framework includes ReLU activation. ReLU activation is nondifferentiable and, therefore, mathematically more challenging than, for example, linear and polynomial activation, but has become the predominant type of activation in practice. Forth, the framework includes constraint as well as unconstraint estimation. Constraint estimation particularly suitable for wide networks, and for overparameterized networks more generally, because it avoid overfitting and facilitate optimizations. Fifth, our statement holds for arbitrary output dimensions and depths. The latter is particularly important in view of the current trend toward deep architectures. In sum, result is sweeping proof of the fact that wide networks have no spurious local minima, and it sheds light on the optimization landscapes of deep learning more generally.
The bound on the network widths becomes 2m + +1) 2(n + +1) in the case of a single output (m = 1) and a single hidden layer (1 = 1), which coincides with the bounds that have been established for
4

---

Under review as a conference paper at ICLR 2021
shallow networks with one output and specific activation functions and estimators- Lacotte & Pilanci (2020) and references therein. Thus, our theory applies extremly broadly and still gives the expected results in the simple cases. In fact, proof' only require layer to have width of at least 2m + 1), but instead of losing ourselves in technical details about the condition, we focus on the main message of Theorem 1: optimizations become easier with increasing widths.
3 UNDERLYING CONCEPTS
In this section, we introduce concepts that we use in our proofs and that might also be of interest more generally. We first formulate the notion path equivalence, which yields a practical characterization of spurious local minima. We then formulate specific parameters that can act mediators between path-equivalent parameters. The main reason why our proof techniques are quite different from what can be found in the literature that cater deep networks and range of activation functions.
3.1 PATI RELATIONS
The objective functions for optimizing neural networks are typically continuous but not convex or differentiable. In the following. characterize the absence of spurious local minima in way that suits these characteristics of neural networks. The key concept is formulated in the following definition.
Definition 2 (Path relations). Consider Iwo parameters O, M. If there is continuous function herr [0, 1] + .M that satisfies he [0] θ be.r[1] I, and + l[gbe, [4] is constant, we say that O and are path constant and write @+T
If there is continuous fumction he.r [0, 1] + M that satisfies he.r r()r θ he.r I, and t + [[0h.. [t]] is convex, we say that O and I are path convex and write O-
there parameters Ø' I' M such that (i) @ and T and (ii) O' @',,, say that Q and I are path equivalent and write ② e
Path constantness means that two parameters are connected by continuous path of parameters that constant with respect the loss; path convexity relaxes "constant" to "convex:" path equivalence allows for additional mediators. The three relations are ordered in the sense that O++ + θ- + D. and they satisfy a number of other basic properties.
Lemma (Basic properties). holds for all o, E M that
1. @++; @ and 1 2 (reflexivity):
2. @+r = T T r-e; and m Pom (symmetry).
3. O+r and P+* +++ (transitivity).
The proof is straightforward and, therefore, omitted. The lemma illustrates that the path relations equip the parameter space with solid mathematical structures.
We finally the stove-stated concepts to characterize spurious local minima.
Proposition 1 (Characterization of spurious local minima). Assume that for all O E M, there is global minimum of the objective function (4), denoted by I, such that θ P. Then, the objective function (4) has spurious local minima.
Hence, path equivalence of all parameters to global minimum is sufficient condition for the absence of spurious local minima. This statement is the main result of Section 3.1.
3.2 BLOCK PARAMETERS
The parameterization of neural networks is typically ambiguous: many different parameters yield the same network. We leverage this ambiguity to make the networks more tractable. The key concept is formulated in the following definition.
5

---

Under review as a conference paper at ICLR 2021
6
6
8 e
6
Figure 2: Illustration of the parameters of an s-upper block parameter (left) and an s-lower block parameter (right) for = 2. The dark areas of the matrices can consist of arbitrary values; the light areas consist of zeros.
Definition (Block parameters), Consider a number & {0, ....) and a parameter E M. If
1. (0%); 0 for all j s;
2. (0"); = 0 for all u E (1,...,,I I- 13 and > s and all v E (1,.... - 1] and > 8;
3. (0"); for all > s.
we call O an s-upper-block parameter of depth L.
Similarly, if
1. (0%); = 0 for all j ppp - 8;
2. (0");; 0 for all v {l,...,,- 1) and i S p"+1- - and for all {1....., 1 1} and
j S p" 8;
3. (0') )ij for all S 8,
we call O an s-lower-block parameter of depth 1. We denote the sets of the s-upper-block and s-lower-block parameters of depth by Us and L. respectively.
Trivial examples are the 0-block parameters Ug Lo {0 (xpt Op' xyr) and the block parameters Us L..1 = .M for 2 max ..... p'}. More generally, the block parameters consist of block matrices: see Figure 2. We show in the following that block parameters can be mediators in the sense of path equivalence.
We first show that every parameter is path constant to block parameter.
Proposition 2 (Path connections to block parameters). For every θ E M and s == m(n + 1Y, there are θ + E MN with θ E Us.1 and @ L., such that θ and @
In particular, every parameter is path connected to both an upper-block parameter and lower-block parameter. The interesting cases are wide networks: for fixed s, the wider the network, the more pronounced the block structure.
We then show that there is connection between upper-block and lower-block parameters. Proposition 3 (Path connections among block parameters). Consider two block parameters O Us and r E L. If w > 2s, it holds that + @w...
Hence, every upper-block parameter path connected to every lower-block parameter-as long as the minimal width of the networks is sufficiently large.
We finally combine Propositions 2 and 3.
Corollary (All parameters are path equivalent). Consider two arbitrary parameters E. 2 2m(n 1)', it holds that O
See Figure for an illustration. The corollary ensures that long the minimal width is sufficiently large, all networks are path equivalent. This result, therefore, connects directly to the characterization of spurious local minima in Proposition I of the previous section.

---

Under review as a conference paper at ICLR 2021
M
* [g
Preposition
Propesitio
Proposition 2
T
r
Figure 3: path-equivalence between two parameters ② and T- see Corollary and Definition 2
4 AUXILLIARY RESULTS
In this section, we state four auxilliary results.
4.1 TWO-LAYER NETWORKS
Here, we show that two-layer networks can reparametrized such that they are indexed by block parameters. We first introduce the notation
- SIM asl
r[M, 9) = Ml = max aE(1....bb)
for all M E pxxe E (0, o0)
and r[M, oo] = MM = max,5] [Ma for all M Rbxc. These functions are the building blocks of the constraint on Page 3. Next, given permutation p {I....,ch {I....,c} and matrix M E R5xc, we define the matrix M, E R through (Mp)s == M apli]. Similarly, given permutation p {1....,6} {l..... b} and matrix M E Rxxe, we define the matrix MP b through (MP)) = PDJe The result is then the following:
Lemma (Two-Layer networks). Consider three matrices Ruxo B R and C E Roxt two constants 44 E (0, 1] and qB E (0, oo), and a function E - R. With some abuse of notation, define h uuxr > Rex through (h[M]);; == ji) all M E Roxr, Then, there are matrices E Ruxx and B E Roxo and permulation [I...., - {l....,v) such that
Ah[ Ap][BPC]:
E[A,qAl - I 9A1 and B 98. :gl::
= j u(r + 1); B5s = forrr j > u(r + 1) and B5, = (B*), otherwise.
Similarly, there are matrices A _axx and B E gexo and permutation {I...., 7 {I....,0) } such that
* Ab|BC] = Apb[BPC]:
t(A.qA] < A qa) and t B qn. S : 4n);
Ai = 0 for < u(r 1); By 0 for j S v +r 1) and By: = (B*), otherwise.
Hence, the parameter matrices of two-layer networks can be brought into the shapes illustrated in Figure 2. We apply this result repeatedly in the proof of Proposition 2.
4.2 SYMMETRY PROPERTY OF NEURAL NETWORKS
Next, we point out symmetry in setup for the neural networks.
Lemma 3 (Symmetry property). Consider permutations p¹ : {1.....,'' p²) - f1..... D') for for all j. The parameter O EM is a spurious local minimum of the objective function (4) if and only if T E .M defined through (I") (0²) ts hlp' (o) for all j E {0..... l}. {l,..., w +1 J, and
j E (0.....I+) 1}. Assume that pd and p are the identity functions: pD p
E (1,...,p') } is spurious local minimum of the objective function (4).
7

---

Under review as a conference paper at ICLR 2021
The proof follows readily from setup in Section 2.1 and, therefore, is omitted. The lemma illustrates that the parameterizations neural networks are highly ambiguous. But in this case, the ambiguity is convenient, because it allows us permute the rows and columns of the parameters to bring the parameters in shapes that are easy to manage.
4.3 PROPERTY OF CONVEX FUNCTIONS
We now establish simple property of convex functions.
Lemma 4 (Property of convex functions). Consider convex function h :00, + IR. [fb[o] > b[d] for a i E (0, 1]. there is e E arg (o. such that the fumction h [0, 1] + R defined
through b[4] = h| [cet] for all E [0, 1] is nonincreasing and 6[0] > 6[1].
This lemma connects the convexity from Definition 2 with the spurious local minima from Definition 1. We use this result in the proof of Proposition 1.
4.4 CARATIÉÉODORY-TVE RESULT
Carathéodory's theorem goes back to Carathéodory (1911); see Boltyanski & Martini (2001); Fenchel (1929); Hanner Rádström (1951) for related results. The following statement combines the classical theorem and the much more recent results Bastero et al. (1995, Theorem and Lemma 1).
Lemma (Carathéodory-Typp Type result). Consider a number q E (0, 1], vectors 21,..., 2h C RR, and
the vectors' q-convex hull conv lonvglzi....... == {E 1zzz i [0, 1), |8], =1]. Then, every
vector E conv fonvglz1...... can be written as v Ej=1 ビyæ with [0, 1]", ||t|, I 1, and # E (1.....h) h tj 0} rl
The cardinality of a A is denoted by # #[AA and the ny-nrmm of vector e R" by |0|g 15 (0, The lemma follows readily from the mentioned results; therefore, its proof is omitted. The lemma states that every vector in the q-convex hull is q-convex combination of at most r ++1 1 vectors from the set of vectors that generate the g-convex hull. (Note that for < 1, our definition of the g-convex hull more restrictive than the standard definition- Bastero et al. (1995, Remark on Page
it leads to concise statement and is sufficient for purposes.)
DISCUSSION
Empirical evidence has long suggested that wide networks are comparatively easy to optimize. In this paper, we underpin these observations with rigorous theory: we prove that the optimization landscapes of empirical-risk minimization over wide networks have no spurious local minima.
Standard competitors to deep learning are "classical" high-dimensional estimators, such as the ridge and the lasso (Hoerl Kennard, 1970; Tibshirani, 1996). that have been studied in statistics extensively (Zhuang & Lederer, 2018). 8). A common argument for these estimators is that their objective functions are often convex or equipped with efficient algorithms for optimization (Bien al., 2018; Friedman et al., 2010). but our results indicate that global optimization of the objective functions in deep learning can feasible as well.
Our framework allows for arbitrary depths, for constraint as well unconstraint estimation, essentially arbitrary activation, and for very wide spectrum of loss functions and input and output data. This generality demonstrates that the absence of spurious local minima is not feature of specific estimators, network functions, or data but, instead, universal property of wide networks. Our theory, therefore, supports the use of wide networks in general general-ppssibly together with regularization or constraints to avoid overfitting.
The main idea of most approaches in the field is to construct basis functions for the networks. In contrast, we formulate parametrizations that make the networks easy to work with. We could thus envision testing
concepts beyond the presented application.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-parraeeterizatio. In Proc. ICML, pp. 242-252, 2019.
M. Anthony and P. Bartlett Neural network learning: theoretical foundations. Cambridge University Press. 1999.
A. Barron and J. Klusowski. Approximation and estimation for high-dimensional deep learning networks. 1rX.v:1809.03990 2018.
A. Barron and Klusowski. Complexity, statistical risk, and metric entropy of deep nets using total path variation. arXiv: /9020000000 2019.
J. Barron, A general and adaptive robust loss function. In Proc. CVPR, pp. 0926-4334, 2019.
P. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, 2002.
Bastero, J. Bernués, and Pena. The theorems of Caratheodory and Gluskin for 0 < < 1, In Proc. Amer. Math. Soc., pp. 141-144, 1995.
V. Belagiannis, C. Rupprecht, G. Carneiro, and N. Navab. Robust optimization for deep regression. In Proc. ICCV, pp. 2830-2838, 2015.
Bien, Gaynanova, J. Lederer, and C. Müller. Non-convex global minimization and false discovery rate control for the trex. J. Comput. Graph. Statist., 27(1):23 2018.
V. Boltyanski and H. Martini. Carathéodory's theorem and h-convexity. J. Combin. Theory Ser. A, 93:292-309, 2001.
C. Carathéodory. Über den Variabilitätthereichh der Fourier' schen Konstanten von positiven harmonis- chen Funktionen. Rend. Circ. Mat. Palermo, 32(1):193-217, 1911.
Y. Dauphin, Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Proc. NIPS, pp. 2933-2941, 2014.
S. Du, X. Zhai, Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks. In Proc. ICLR, 2019.
J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc., 96(456): 13488 1041-13886601 1360, 2001.
W. Fenchel. Über Krümmung und Windung geschlossener Raumkurven. Math. Ann., 101:238-252. 1929.
J. Feng and N. Simon. Sparse-input neural networks for high- dige-dimensional nonparametric regression and classification. ar1 1.07992, 2017.
Friedman, T. Hastie, and R. Tibshirani. Regularization paths for generalized linear models via coordinate descent. J. Stat. Softw,, 33(1):1, 2010.
I. Goodfellow, O. Vinyals, and A. Saxe. Qualitatively characterizing neural network optimization problems. arXiv:1412.6544, 2014.
O. Hanner and H. Rådström. A generalization of theorem of Fenchel. In Proc. Amer. Math. Soc., volume 2, pp. 589-593, 1951.
T. Hastie, R. Tibshirani, and M. Wainwright. Statistical learning with sparsity: the lasso and generalizations. CRC press, 2015.
M. Hebiri and Lederer. Layer sparsity in neural networks. arXiv:2006.15604 2020.
A. Hoerl and R. Kennard. Ridge regression: biased estimation for nonorthogonal problems. Techno- metrics, 12 12(1):55-67, 1970.

---

Under review as a conference paper at ICLR 2021
L. Jiang, Z. Zhou, T. Leung, L.-J. Li, and L. Fei-Fei. Mentornet: learning data-driven curriculum for very deep neural networks on corrupted labels. In Proc. ICML, pp. 2304-2313, 2018.
J. Kim, V. Calhoun, E. Shim, and J.-H. Lee. Deep neural network with weight sparsity control and pre-training extracts hierarchical features and enhances classification performance: Evidence from whole-brain resting-state functional connectivity patterns of schizophrenia. Neuroimage, 124: 127-146, 2016.
A. Krizhevsky, Sutskever, and Hinton. Imagenet classification with deep convolutional neural networks. In Proc. NIPS, pp. 1097-1105, 2012.
J. Lacotte and M. Pilanci. All local minima global for two-layer ReLU neural networks: the hidden convex optimization landscape. arXiv:2006.05000, 2020.
Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. Nature, 521:436-44: 444443364444004 2015.
J. Lederer. Risk bounds for robust deep learning, arXiv:2009.06222,, 2020.
R. Livni, S. Shalev-Shwartz, and O. Shamir. On the computational efficiency of training neural networks, Proc. NIPS, pp. 855-863, 2014.
Q. Nguyen and M. Hein. Optimization landscape and expressivity of deep CNNs. In Proc. ICMI, pp. 3730-3739, 2018.
D. Soudry and Y. Carmon. No bad local minima: data independent training error guarantees for multilayer neural networks. arXiv:1605.08360 2016.
M. Taheri, F. Xie, and J. Lederer. Statistical guarantees for regularized neural networks. arXiv:2006.00220 00294, 2020.
R. Tibshirani. Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. Stat. Methodol., 58(1):267-288, 1996.
L. Venturi, A. Bandeira, and J. Bruna. Spurious valleys on-hiddeenllayer neural network optimiza- tion landscapes. J. Mach. Learn. Res., 20(133):1-34, 2019.
7. Wang, S. Chang, Y. Yang, D. Liu, and T. Huang. Studying very low resolution recognition using deep networks. Proc. CVPR, pp. 4792-4800, 2016.
C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. Ann. Statist,, 38(2): 2010.
R. Zhuang and Lederer. Maximum regularized likelihood estimators: general prediction theory and applications. Stat, 7(1):e186, 16, 2018.
10

---

Under review as a conference paper at ICLR 2021
A PROOFS
A.1 PROOF OF THEOREM 1 AND AN EXTENSION
Proof of Theorem I. The proof combines the main results Sections 3.1 and 3.2. Let O E M
be an arbitrary parameter and I M a global minimum of the objective function (4). In view of
Proposition in Section 3.1, we need to show that @m-,, and this follows directly from Corollary in Section 3.2.
Figure 1 illustrates that nonconvex objective function can have spurious local minima, but Theorem 1 proves that this is not the case for deep learning with wide networks. Figure also illustrates that a nonconvex objective function our results more generally, we can rule out this case as well. In other words, the set of global minima is "connected" in the sense that it is set of path-constant parameters. The connectedness of the global minima is of minor importance in practice but an interesting topological property nevertheless.
have "disconnected" global minima, but, in view of Corollary 1 and
A.2 PROOF OF PROPOSITION 1
Proof of Proposition 1. The key idea is to exploit the properties of monotone functions and convex functions. Let E .M be an arbitrary parameter and T E M a global minimum of the objective function (4) such that @m-I. Let O I' M and her. [0. + .M be described in Definition 2. Note first that, since T+T (see Definition 2), the parameter I' is also a global minimum of the objective function. We then use 1. simple algebra, 2. the assumed convexity of the function & + ![@her r (see Definition 2 again), 3. the assumed endpoints of the function he (see Definition 2 once more). 4. the fact that I' is a global minimum of (4), and 5, the fact that (1 - 1) + to derive for all E [0, 1] that
1[ [[ r r(1]
= 1 [[ [1 ((1-1))-++)) -0)-++1
S (1 t)l( 0 r [0]]
+ El (
(1 t)( 0 [0]
+ fl[gr
S (1 {)( [0]
+ El [he
[ r r0]
Assume first that the inequality is strict: ( < ([ [o]] for a 7 E [0, 1]. Then, by the assumed convexity of t + [[ (see Definition 2) and Lemma 4, there is E arg (o, ( r4]]) such that h [0 + R defined through b[d] = 1[0 r let]] for all E [0, 1] is nonincreasing, b[4] is a global minimum of the objective function (4), and 6[0] = [[ = [ > 6[1] = [[gber Ie]- Hence, the function h [o. 1] + M defined through 5][] = be r [ct] for all E [0, 1] is function that satisfies the conditions of Definition for the parameter O and the global minimum b[1]. Combining this result with the assumed relationship @++ (see Definition 2) yields see Definition 1-the fact that O is not spurious local minimum of the objective function (4).
We can thus assume that t ([hhrr [1] is constant, which implies O'+II' by Definition 2. The fact that O+0' (see Definition again) and the transitivity of the path constantness (see Property in Lemma 1) then yield the fact that e' Hence, e is global minimum and, therefore, not spurious local minimum see Definition again.
A.3 PROOF OF PROPOSITION 2
Proof of Proposition 2. Our proof strategy to apply Lemma 2, which is designed for one individual layer, layer by layer. We first introduce some convenient notation. We define, with some abuse of notation, f Tep' xn - TRE x through (MMM) = p ['[Mae) for all j E (1,...,4), u 1'....,p',, v (1,...,n) n), and M RR'' We also define the data matrix X E Rdx= through

---

Under review as a conference paper at ICLR 2021
x; (2,), for all {l....,d] df and i e {l....,m)) n), that is, each column of X consists of one sample. We fimally write
ge [ = (Be[zı]..... go x.) 1 PI E Rm for all O E M.
Hence, ge XX] summarizes the network's outputs for the given data.
Given a parameter E M, we establish corresponding upper-block parameter θ E Us, layer by layer, starting from the outermost layer. We write
ge [x|x- =
-'-1 1..000....
AERP
=cb
-ERR
=:Celrl
Lemma 2 for two-layer networks then gives (by Lemma 3, we can assume without loss of generality the fact that p is the identity function, that is, Ap = and 13 = B))
ge [X] (
Q (8))) 1 [[0--2..-PP[xx]]]]]
for a matrix O E IRee+ xp' that satisfies r 1| < <r(O', 1] (recall the definition of on Page 7) and meets Condition 3 in the first part of Definition on block parameters as long as s 2 pp (n
1) m(n + 1). and for a matrix @ E m=="n=1)xp'' that satisfies r/O'-1, ,1] S r(0/-1, 1] (or c(O'-1,g) g) =/Ol-1,g) - if
and consists of the first m(n rows of the matrix O (We
implicitly assume here and in the following p' 2 m(n + 1)1- for all j E (1....,))-wiice is the generic case in view of Corollary 1-to keep the notation manageable, but extending the proof the general case is straightforward.)
Now, define parameter I M through
r -6,00' .....,
, 09)
and function herr : [0.1] 1] + M through
be.r: [t] == - ( + /
for all t E [0,
The function he is continuous and satisfies he.r [0] O and he.r [4] r'. Moreover, we can 1. use the definitions of the function he,r' and the networks, 2. split the network along the outermost layer, 3. invoke the block shape of O and the definition of 6'-1 as the m(n + 1) first rows of the matrix 0 4. use the above-stated inequalities for the network go (X). and consolidate the terms to show for all E [0, 1] that
9b [4] ((1 1) + / [(00
(1 [1)0. (0
+ 10/p/ (0)-1) ... x.,
= (1
(1 1) X| (ge [X]
ge g [X]
Hence, the function f ++ (0 [t] is constant. Finally, we use the definition of the constraint
in (3), 2. the definition of the function be.r. 3. the convexity of the & -orm,, 4. the above stated fact
that r | 1] < r 1]. 5. consolidation, 6. again the definition of the regularizer, and 7. the fact that E M to show for all E [0, that
r[be.r = max ar max jE(I....)) (he (4) |l, by (be.r [4] 31
= =max ar max
| 11, a..a.1(11 - t + :55 6. 1,
jE(1...l-1)
< maxfa ar max
| 1 t)a=/ll'1, I, 111
je(1....!11)
12

---

Under review as a conference paper at ICLR 2021
$ max ar max jE(1...I11)
||0' 11. (1 t)a.Il*' I1 + ta,110'|1, b.10%
max
| a, 1
ar max jE(1.../11)
=r(O]
< 1.
Hence, h [t] E M for all E [0, 1]. In conclusion, we have shown see Definition 2 that θ and D' are path constant: O++I
We then move one layer inward. Lemma 2 ensures that (recall again Lemma 3)
( (()
[ -6-111111
f' x]
AERm(n 1)xp
BER 1xpl-2
CERP
Condition 3 in the first part of Definition 3 on block parameters as long as $ 2 m(n + 1)² and for 1 for matrix Ô R Im(n+1)xp" that satisfies r/ 1] I r|00-1, ,1] < r(0'-1, and meets
matrix e/-2 E 1mm(a+1)9pp' xpp= that satisfies r/@/-2, 1] S :/O'-2 1] (or =(O0-2,00) ,g] s 5r(e'= ?.9] if
I = 2) and consists of the first m(n + 1)a rows of the matrix O
Next, we define 6--1 E Re' xp'x through (Gi-)) == (él-1) )uo for u S m(n + 1) and O Duv := 0 otherwise. Combining this definition with the above-derived results yields
(0'-2) (80)
9 [ 5
O 1
p x
and the matrix 01-1 satisfies : 6 = ( S 101 1] and meets Condition 2 in the first part of Definition 3 on block parameters as long as 2 m(n + 1)2.
Similarly as above, define parameter r E .M through
r- = - e
00)
and function bri [0, 1] + M through
br r [+] (I t)r + for all E [0.
show that P' In view of Property 3 in Lemma 1, we can conclude that O+1 Finish the proof by induction over the layers, and note that the lower-block parameters can be established in the same way.
A.4 PROOF OF PROPOSITION 3
Proof of Proposition 3. The key ingredient of the proof is the assumed block structure of the parame- ters. Consider two block parameters θ Us and P E Las! and define the parameters
@' (e', 6 p--1 0 + r M;
I' = (r', r 1 ---1 0 r E M
and the function
berr [0, + M
+ (1 (1- +T (11 + +
+ "...,...., ro)
By the row-wise structure of the constraint (see Page 3 again), the convexity of the nnrmm, and the block shapes of the parameters (see Figure 2 again), we can find that rlhe: boberr//l [t] < max(r r[T]} < for all [0, 1]. that is, herr E M for all t E [0, 1]. One can also verify readily the fact that the function her r is continuous, her be O', and r r Next, we define
[O',T") T' (ar t2 00-1 pI-1 0" r M for all c E R,
13

---

Under review as a conference paper at ICLR 2021
which generalizes her, _r' in the sense that he r = j je',T")--tt for all t [0, 1]. We then invoke the definition of [Ø', Ic,,, and the definition the networks in (1), 2. split the network along the outer layer, 3. use the block structures of the parameters and the assumption that [ = (f(b.]..... f' 1bbp>)) for all (1.....}} and b E I 4. continue in this fashion, and 5. invoke again the defmiiiin of the networks in (1) to find for all c1, c R and æ E De that
_ e2 [x]]
= (G + ofl" - 100000 (0((0++1)))) +19a1]]
=colf (0 (20071110011
+ [00 +r))a]]
+c217p0 (0) - 1 - [(000 +1*0+ +1))a|]
= = (00-1p--11 1
10 + + |=1
+ r- [' 8 (6 + +1aaa]
g0' 0- p0--p--1--
t r- [r
ciee ac] c20r xz)
Finally, we use the definition of the function he r and of the parameter (0', I'le, lg 2. the above display with 6 - (1 - a)t at2 and 02 = (1 - a)t 1 + at2, 3. a rearrangement of the terms, the assumed convexity the loss function I, 5. again the above display, and 6. again the definition of be ,r, to find for all a, f1, t2 [0, 1] that
Phe r ((10))+
[[ger:
= [(1 (1 - at2) (11-00 a)1 + atz) atz))rr
= [((11 - a) - (1 - (1)))((11)))) (a- a02) + (1 1a--a)tis + al2or
= [(1 a01 - ti + + te + t2gr)
< (1 a) - f: + +ir + al[(1 f2) [2rr]
(1 a)l
+ -
r 1
= (1 a) [6] + al (0
which means that + (B [e] is convex. We conclude see Definition 2-that O'-r".
In view of Definition 2, is left to show that @ and P Consider now the function
he [0, 1] M
+ (0',0'- + ................................ O 11
By the row-wise structure of the constraint (see Page once more) and the block shapes of the parameters (see Figure 2 once more), we can find that r(be,er [4] S max(r(O), r((])) < for all E [0, IJ. that is, be.er [4] E M for all / E [0, 1]. One can also verify readily the fact that the function beeeer
O. and he.e [1] O'. Moreover, we can invoke the definition of heeer and the definition of the networks in (1), 2. use the block structures of the parameters and the elementwise structure of the activation function, 3. continue in this fashion, and
continuous, he.er
4. invoke the definitions of the function he,er e and the networks in (1) again to find for all E [0, 1] and æ E D, that
She [4 [2] = e'
(0 + r' 1 ... [(0 + )1)))
= -
01-1 [000 + )a)))]]
14

---

Under review as a conference paper at ICLR 2021
O'g 0- 1 [1
hhe [0] [z]
see Definition 2 which implies that the function t + 1 |/ is constant. We conclude that-see that @++0'.
We can show a similar way that T+T. Hence, given Definition 2, we find that eweT, as desired.
A.5 PROOF OF LEMMA 2
Proof of Lemma 2. The proof is essentially careful reparametrization. We proceed in three steps: see Figure for an overview.
Step 1: Fix k (1.....u).
u}. We first show that there a matrix Á E Rguxe such that
1. Ab[BC] = Ab[BC];
2. {(A, qAl S gA).
3. #(j [L...., o} Ars 0} rr
4. Anj Aaj for all a # k.
Hence, we replace the matrix A, which contains the "output parameters," by a matrix whose kth row has at most nonzero entries
the illustration in Figure 4.
The proof of this step is based on our version of Carathéodory's 's theorem in Lemma 5. For every k E {1....,u} ub and i {1,...,.7) r),, elementary matrix algebra yields that
(Ab(BC)) Σ Aky (b(BC)),; ==1
Denoting the row vectors of a matrix M E gaxb by Mi...... Ma E Rb, we then get
(Ab[BC)) = Σ (b(BC)))
j=1
The case || 1aA 0 is straightforward to deal with: all elements of Age are then equal to zero, and we can just set A = A.
We can thus assume the fact that ||Abo * O. We then get from the preceding equality that
ARj
(Ab(BCT)
Σ
Akelloa (b(BCT)
A
14
Since
1/4a
1/9a
1
Auj
aa
|8/ =
Σ 19
Σ
A Iaa
1/4a
1
AAxe
AAualla
AAxelax
1=1
the previous equality means that the vector (Ch[BC])Ro E R" is a q convex combination of the 2v vectors 21, 21.-..: Zuz 21, B1y..ry 2, E TR", that is, (Ah BC)) E conv,lz1,.... Zv, -1...., 2n]
15

---

Under review as a conference paper at ICLR 2021
Starting point
Step
Step 2
Step 3
B
B
A
B
π
Figure 4: overview of the proof of Lemma 2
Hence, by Lemma 5, there a t E [-1, 1] such that lt|qa I 1, #L E (1,....,0) : 1, and
(AblBCT) ke
tyllAka Iaa (b(BC)),.
Hence, by the definition of the row vectors,
" (b)1 j=1
(Ab(BC))
for all E (L....,r] r3. and, more generally, we find for all a {L,... (AblBCT) ai
u) and E {L...., r) that for k; otherwise.
1 AnolAlll (bIBC))
E Aay (b(BC1)
This motivates us to define À E _Ruxx through
Aaj [1slAkole Anj
for a a k
otherwise.
Properties 3, and then follow immediately. Property 2 can be derived by using 1. the definition of the basic regularizer Page 7, 2. the definition of Á, 3. the linearity of finite sums, 4. the definition of the no-nrsms on Page 8, 5. the above-derived property [t]]ga S 1, consolidation, and again the definition of the basic regularizer Page 7:
qal) aε(I....,uf
Aaj 44
1 Lkk lea
for a = k otherwise for a k otherwise
max aE(l.....u
j= Auy 99
Ak
14 Σ
Σj=10
194
max aE(1.....u
7.1
Ø= Aua 9
|Aky ((a)
|t/ga
for a k otherwise
max
af (
Ana 9a
ARg
for k otherwise
S max ac (l....))
== Aag
94
Aaj 94
aE aE(I....u
= 24 desired. This concludes the proof of the first step.
Step 2: We now show that there is matrix À Rux such that
1. Ab[BC] Ab[BC]:
16

---

Under review as a conference paper at ICLR 2021
2. =(A, qAl & gal;
3. #(i E .I,.....u}
o) Aos + 0) 1r+1 for all E {l,....u).
Hence, we replace the matrix A by matrix whose every has at most + 1 nonzero entries again the illustration in Figure 4.
Since Step changes only the kth row of (see Property 4 derived in Step 1), can apply it to row after another.
Step 3: We finally prove the first part of the lemma see again the illustration in Figure 4.
By Property of the previous step, the matrix A has most u(r + 1) nonzero columns. Verify that replacing by A, and B by B for a suitable permutation p leads to an whose entries outside first u(r + 1) columns
equal to zero sero-while all other properties remain intact. We denote this version of A by A. We then derive for all j {I...., v) and {I...., that
(h1 bb( =h (BP))S00 Coc
(CT )co()))))))))) Σ 1=1
= [b[ (BP) (B)))))]] (B%))(B)),,))))) = (BP)))))
where we define (with some abuse of notation) h : R" + IR" through (b/bl), = b|b,] for all R". Combining this result with the results of Step 2 (with A and B replaced by A, and BP, respectively) yields for all a E [I,...,u} and (1....,7] that
(Aph(BrC) (A
(Ap))s((lC (BP)a))) j=1
minfa(r+1),0) Σ
Aas (bic (B*),.l);- =
Aus (BICT(BB)),))
We then define B E R through
(B)) Bppbj for j S u(r + 1); otherwise.
B5 0
We then use the above-stated equality, the definition B, 3. similar derivation as above, block structure of A, and 5. similar derivation above to establish for all {l,..., u) and i E {1....,r) r the fact that
min min (1(e++))e))
(A.b(BPC))
Σ
Aas (BBC)(
min (in(
Σ
Aag (B]CTBBao)).
min(u(r+1).a)
Σ
Aas (h BC(),
Anj (bl BC))
= (bb ai
The other properties stated in the lemma follow readily.
The second part of the lemma be derived in the same way.
17

---

Under review as a conference paper at ICLR 2021
A.6 PROOF OF LEMMA 4
Proof of Lemma 4. The proof is a simple exercise in calculus. An illustration of the quantities involved in the proof given in Figure 5. The function h is convex by assumption; hence, it is continuous. Then, according to the extreme value theorem, there a number
E arg min [b[d}
Since b[0] h[00] for a (0, 1J. it holds that E (0, 1]. Now consider l2 [0, and 6 E (0,42).
that is, 22 > t1. Basic calculus ensures that
b [ta] b[ct2]
bctt + c2 chl
b ct + c2 ct (c - cti)
cl
t2 - t1
h
ct +
(c ct1)
1- t1
t t
t2 - t ct +
b
1 11 C
1 t
$ 1
1
blctt]
12 4 1 1 h/cl t2 t [cb 1 t
(1
82 t
b[cci]
+
t
b[ch1
6[6]]
Hence, h is nonincreasing.
Moreover,
6/0] = b/c. 0] = bj0] >
b 2 blc]
-bfc- 1] = b/1].
Hence, 6[0] 6[1]. This concludes the proof.
6[t]
h[4]
Figure 5: quantities in the proof of Lemma
18


Reviews:
[{"review_id": "qECKROy1K9A", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper demonstrates a claim \"No spurious local minima\" in the optimization landscapes of deep neural network given the width is O(n^l), where n is the number of training samples and l is the depth. \n\nStrong points: \n1. The \"No spurious local minima\" claim holds for all depth and quite general activation function. This greatly extends previous result and understanding.\n2. The proof is heavily based on a new concept \"path equivalence\" and the algebraic manipulation. It is nontrivial and different from previous techniques. I checked part of the proof, which are correct to me.\n\nWeak points:\n1. The paper is hard to read for the various calligraphic notations. Although there are some description of the proof, it is better to give more intuitive argument before going to details.\n2. The result requires extremely width O(n^l), under this regime each sample is guaranteed to be separable. This requirement is even larger than the NTK regime under which the gradient descent is guaranteed to find global minima. Thus it is doubtable of the theoretical/practical value of the work: use an even larger width and describe an optimization landscape that is not related with optimization methods.\n\nDespite of the above weakness, I will recommend its acceptance to foster diverse techniques.", "extra_scores": {}, "extra_text": {}}, {"review_id": "eK8OwfpHgPI", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary] This paper considers the optimization landscape of deep learning with very wide networks. The main contribution of this paper is the result that shows the empirical risk of very wide networks has no *spurious local minima*. The results hold for both constrained (like the norm or sparsity constraints on the network parameters) or unconstrained risks, but require the network width larger than $O(mn^\\ell)$, where $m$ is the output dimension, $n$ is the number of training samples, and $\\ell$ is the number of layers.\n\n[Pros] This paper provides interesting results on the optimization landscape of deep learning. These results could provide a better understanding of the training problems in deep learning and why the neural networks can be successfully trained by local search algorithms like SGD.\n\n[Cons] 1. My first major comment is about the definition of *spurious local minima* used in this paper. People usually say a local minimum as a spurious local minimum if it is not a global minimum, and hence say a function has no spurious local minima if every local minimum is global. This is different from what has been used in this paper (Definition 1), which only counts a subset of local minima and excludes other local minima that are also not global. For example, see the local minima in Figure 1.a in [A]. \n\n[A] On the Benefit of Width for Neural Networks: Disappearance of Basins (https://arxiv.org/abs/1812.11039)\n\n2. Indeed, I feel like the definition of *spurious local minima* used in this paper is similar to the so-called *set-wise strict local minimum* in the above-mentioned reference [A]. [A] provides similar results but is missing. The authors should compare the results with [A]. In particular, [A] also proves the empirical risk of networks has no spurious *set-wise strict local minimum* in the sense that every set-wise strict local minimum contains a global minimum, but only requires the width of the last hidden layer larger than $n$.\n\n3. The results require a huge-width network, i.e., the network width larger than $O(mn^\\ell)$. In this case, it is known that the network acts as a kernel method (also known as \"lazy training\") and many results have shown simple gradient descent converges to a global minimum. So in this sense, the result that the training problem in this regime has a nice optimization landscape is not that surprising. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZERu1NP4Ti6", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper studies the optimization landscape of the training loss of deep neural networks. For  a general setup, the paper shows that if the network width is greater than $2m(n+1)^l$, then any parameter value has a path to a global minimum on which the training loss does not increase. Here, $m$ is the output dimension, $n$ is the number of training examples, and $l$ is the number of hidden layers.\n\nStrength\n\nThe result presented in the paper holds for a surprisingly wide range of setups. The theorem holds for any convex loss function, any arbitrary activation, arbitrary output dimension and depth. The theorem holds for unconstrained optimization setup, and also some specific type of constrained setup (Eq (3)).\n\nThe paper is well-written and it delivers its key messages fairly well. The main text provides a good proof sketch that is easy to follow. After a quick perusal of the proof I am convinced that the proof is correct. Overall, I enjoyed reading this paper.\n\nWeakness\n\nThere are two main weaknesses of this paper: one is the huge width requirement that exponentially grows with depth, the other is too many missing (directly relevant) citations and the unconventional usage of the term “spurious local minima”.\n\nLet me start with the second one. There is a large body of literature that refers to non-optimal local minima as spurious/bad local minima, and investigates existence/nonexistence of such local minima in the context of neural networks [1, 2, 3, 4, and many more]. In fact, for deep networks with piecewise linear activations, no matter how wide the network is, it is known that there are non-optimal local minima in the training loss in the unconstrained case [3, 4]. The paper misses the entire body of literature and defines spurious local minima in a different way, which can confuse the readers. The title already sounds like a contradiction to [3, 4]!\n\nMore importantly, there are also other missing citations that are even more directly relevant, namely, the ones studying nonincreasing paths to global minima [5, 6, 7]. This set of results typically require that one of the hidden layers is wider than the number of data points $n$ and that the subsequent layers after the wide hidden layer only get narrower. Although these results hold for more specific setups than this paper, the difference in the width requirement is huge: $n$ vs $O(n^l)$.\n\nIn light of these existing results, I fear that the width requirement in this paper is too big, and it grows exponentially with the depth $l$. Although I liked the construction illustrated in this paper, this significant weakness of the main result makes me hesitate to recommend acceptance.\n\nOne minor weakness I also wanted to point out was that, “nonincreasing path to global minimum” alone is not enough, in the sense that this property does not rule out the existence of a local minimum in a locally constant region of the loss landscape (think of the case where all the ReLUs are turned off in a ReLU network). Although sufficient width can ensure the existence of a nonincreasing path to a global minimum from this locally constant region, there is no way that a gradient-based local search algorithm can escape this region.\n\nOverall Assessment\n\nAlthough I liked this paper as I read it, I believe the weaknesses of the main result are too significant. I also think that the paper could use a rewriting to contextualize the results relative to the missing citations. I lean slightly towards rejection at this time.\n\n\n[1] Kenji Kawaguchi. Deep Learning without Poor Local Minima, 2016\n\n[2] Itay Safran, Ohad Shamir. Spurious Local Minima are Common in Two-Layer ReLU Neural Networks, 2018\n\n[3] Chulhee Yun, Suvrit Sra, Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks, 2019\n\n[4] Fengxiang He, Bohan Wang, Dacheng Tao. Piecewise linear activations substantially shape the loss surfaces of neural networks, 2020\n\n[5] Benjamin D. Haeffele, Rene Vidal. Global optimality in neural network training, 2017\n\n[6] Quynh Nguyen. On Connected Sublevel Sets in Deep Learning, 2019\n\n[7] Henning Petzka, Cristian Sminchisescu. Non-attracting Regions of Local Minima in Deep and Wide Neural Networks, 2018\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "U65hwHRvcN", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work showed that for a wide deep neural network, the optimization landscapes of empirical-risk minimizers over wide feedforward networks have no spurious local minima. The theory combines the features of the two mentioned works, as it applies to the entire optimization landscapes, allows for a wide spectrum of loss functions and activation functions, and constraint and unconstraint estimation. The proof defines two important concepts: path relation and block parameters and utilizes these two concepts and propositions and lemmas developed upon them to prove the main result. \n\n\nThe major concern of this work is that the setting is far from practice. In other words, the theory cannot provide much practical guidance nor insights for improvement.\n\n1. First of all, the network width, $w >= 2m(n+1)^l$, is too large to be practical. Since $n$, the number of training examples, and $l$, the number of layers of a network, are large most of the times in the field today, the theorem is not very practical and not applicable in real networks.\n\n2. Second, from the work of Zhang et al. \"Understanding deep learning requires rethinking generalization”, we know that finding the global optimal solution for the training loss of overparameterized networks does not imply good generalization.  Therefore, it is not very meaningful to find the global solutions, since the network is highly overparameterized and not every global solution generalizes the same.\n\n3. Third, the result is far from practice in deep network training. In practice, people, in general, believe that there are spurious local minimizers in deep networks (see Itay et al. “Spurious local minima are common in two-layer relu neural networks”, “Visualizing the Loss Landscape of Neural Nets”), but the data has structures and the deep network is enforcing implicit regularizations to avoid those bad local minimizers. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "7Z6jePkf2A", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "It is still a myth about why neural networks can work without convexity (or, with many local minima). \nSome existing papers tried to explain it using “spurious” minima, which means that there is no non-increasing path to a global minimum.\nThis paper proved that the deep neural networks have no spurious minima with large width (>=2m(n+1)^l, l=#depth, n=#samples, m=#output dim), which is an extension of Venturi (2019) and Lacotte & Pilanci (2020).\nCompared with the previous works of two-layer neural networks, this paper considered deeper neural networks. \nHowever, I had several concerns about the conclusion and the techniques. Please refer to CONCERNS for more details.\n\n### CONTRIBUTIONS\na) This paper considers a general setting, including several activation functions (including ReLU) and constraint and unconstraint estimation.\n\nb) This paper considers deeper neural networks instead of two-layer neural networks, which is an extension of the existing works.\n\n### CONCERNS\nTo be honest, I did not check all the details in the proof. But I have several concerns:\n\n1. The major concern comes from the conclusion. I notice that the depth $l$ appears in the power. It seems that the bound is not tight and surprising enough. \n\n2. If the bound is tight, one needs wider neural networks in deeper neural networks. I do not think that is the reality.\n\n3. As for the technical part, I am afraid I missed some details. But after checking the proof, I found that the proof is finished by induction (page 13). It seems a little bit incremental. By the way, that is also why $l$ appears in the power.\n\n4. Therefore, I would like to raise my score if the authors can restate their technical novelty, or at least show more about the importance of the conclusions. \n\n### COMMENTS\nOverall, this is an interesting paper. But I am still concerned with its technical novelty and the conclusion importance. I tend to reject this paper without a convincing response.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies an interesting problem: the landscape of neural networks. I agree with the authors' comment that this work improves our understanding of one aspect of neural networks, and I do find the result of this paper is of interest to some extent. Reviewer 5 pointed out the technique used in the paper is interesting, and Reviewer 3 has shown interest in the techniques (and indicated the possibility of increasing the score). Nevertheless, a few reviewers questioned the requirement of the large width; I do not think having a large width itself is necessarily an issue (even in the presence of convergence results on NTK), but it is necessary to clearly explain the context and the relation/differences with closely related works in the literature. In the current form, the paper probably has not reached the bar of acceptance, thus I recommend reject. 
Decision: Reject