Year: 2020

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.

text: 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.

heading: 1 INTRODUCTION
text: Deep learning depends on optimization problems that seem impossible to solve, and yet, deeplearning 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 are 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-gradient descent to 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 to 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-Zhu et al. (2019) and Du et al. (2019) suggest that stochastic-gradient descent typically converges to a 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 altogether.
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 a global minimum (see Section 2.2 for a 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 a global minimum without increasing the objective function at any point—see Figure 1 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—rather than for subsets of them. This feature is crucial: even randomized algorithms typically converge to sets of 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
shallow networks, that is, networks with only one hidden layer, which contrasts the deep architectures that are used in practice (LeCun et al., 2015).
Lacotte & Pilanci (2020) made progress on two of these limitations: first, their theory caters to ReLU activation rather than polynomial activation; second, their theory allows for weight decay, which is a 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 to have a theory for the absence of spurious local minima in a broad deep-learning framework.
In this paper, we establish such a theory. We prove that the optimization landscapes of empirical-risk 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 it 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 on the proof techniques are referred to Section 4. The actual proofs are stated in the Appendix.

heading: 2 DEEP-LEARNING FRAMEWORK AND MAIN RESULT
text: 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-risk minimizer does not have any spurious local minima.

heading: 2.1 FEEDFORWARD NEURAL NETWORKS
text: We consider input data from a domain Dx ⊂ Rd and output data from a domain Dy ⊂ Rm. Typical examples are regression data with Dy = Rm and classification data with Dy = {±1}m. We model the data with layered, feedforward neural networks, that is, we study sets of functions G ··= {gΘ : Dx → Rm : Θ ∈M} ⊂ G ··= {gΘ : Dx → Rm : Θ ∈M} with
gΘ[x] ··= Θlfl [ Θl−1 · · · f1[Θ0x] ] for x ∈ Dx (1)
and M⊂M ··= { Θ = (Θl, . . . ,Θ0) : Θj ∈ Rp j+1×pj} . The quantities p0 = d and pl+1 = m are the input and output dimensions, respectively, l the depth of the networks, and w ··= min{p1, . . . , pl} the minimal width of the networks. The functions fj : Rpj → Rpj are called the activation functions. We assume that the activation functions are elementwise functions in the sense that fj [b] = (fj [b1], . . . , fj [bpj ])> for all b ∈ Rp j
, where fj : R→ R is an arbitrary function. This allows for an unlimited variety in the type of activation, including ReLU fj : b 7→ max{0, b}, leaky ReLU fj : b 7→ max{0, b} + min{0, cb} for a fixed
c ∈ (0, 1), polynomial fj : b 7→ cbk for fixed c ∈ (0,∞) and k ∈ [1,∞), and sigmoid activation fj : b 7→ 1/(1 + e−b) 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 l : Rm × Rm → R is assumed convex in its first argument; this includes all standard loss functions, such as the least-squares loss l : (a, b) 7→ ||a − b||22, the absolut-deviation loss l : (a, b) 7→ ||a − b||1 (both typically used for regression), the logistic loss l : (a, b) 7→ −(1 + b) log[1 + a] − (1 − b) log[1 − a], the hinge loss l : (a, b) 7→ max{0, 1− ab} (both typically used for binary classification Dy = {±1}), and so forth. The optimization domain is the set
M ··= { Θ ∈M : r[Θ] ≤ 1 } for a constraint r : M → R. Given data (x1,y1), . . . , (xn,yn) ∈ Dx × Dy, the empirical-risk minimizers are then the networks gΘ̂erm with
Θ̂erm ∈ arg min Θ∈M
{ n∑
i=1
l [ gΘ[xi],yi ]} . (2)
It has been shown that constraints can facilitate the optimization as well as improve generalization— see Krizhevsky et al. (2012) and Livni et al. (2014), among others. For ease of presentation, we limit ourselves to the following class of constraints:
r[Θ] ··= max { ar max
j∈{1,...,l} |||Θj |||1, br|||Θ0|||q
} for all Θ ∈M (3)
for fixed tuning parameters ar, br ∈ [0,∞), a parameter q ∈ (0,∞], and ||| · |||q the usual row-wise `q“-norm,” that is, |||Θj |||q ··= maxk( ∑ i|(Θj)ki|q)1/q for q ∈ (0,∞) and |||Θj |||∞ ··= maxki|(Θj)ki|. This class of constraints includes the following four important cases:
• Unconstraint estimation: ar = br = 0.
In other words,M =M. 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 < 1.
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.
• Input constraints: ar = 0.
Some researchers have argued for applying certain constraints, such as 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-inducing 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
arg min Θ∈M
{ n∑
i=1
l [ gΘ[xi],yi ] + r[Θ] } .
The proofs are virtually the same as for the constraint versions; we omit the details for the sake of brevity.
One line of research develops statistical theories for constraint and unconstraint empirical-risk minimizers—see Bartlett & Mendelson (2002) and Lederer (2020), among others. As detailed above, empirical-risk minimizers are the networks whose parameters are global minima of the objective function
Θ 7→ l[gΘ] ··= n∑
i=1
l [ gΘ[xi],yi ] (4)
over M for fixed data (x1,y1), . . . , (xn,yn). While the function gΘ 7→ l[gΘ] is convex by assumption, the objective function Θ 7→ l[gΘ] 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 are valid in practice. Our goal is, broadly speaking, to establish conditions under which global minimization of (4) can indeed be expected.

heading: 2.2 ABSENCE OF SPURIOUS LOCAL MINIMA
text: We now show that the objective function (4) has no spurious local minima if the networks are sufficiently wide. Recall that a parameter Θ ∈M that satisfies
l[gΘ] ≤ l[gΓ] for all Γ ∈M with |||Θ− Γ||| ≤ c
for a constant c ∈ (0,∞) and a norm |||·||| onM is called a local minimum of the objective function (4). If the statement holds for every c ∈ (0,∞), the parameter Θ is called a global minimum. Objective functions in deep learning have typically many local and global minima; an important question is whether there are “bad” local minima, that is, suboptimal local minima that are difficult to escape from. We formalize this notion as follows: Definition 1 (Spurious local minima). Let Θ ∈M be a local minimum of the objective function (4). If there is no continuous function h : [0, 1] → M that satisfies (i) h[0] = Θ and h[1] = Γ for a global minimum Γ ∈M of the objective function (4) and (ii) t 7→ l[gh[t]] is nonincreasing, we call the parameter Θ a spurious local minimum.
See again Figure 1 for an illustration.
The following theorem is our main result: Theorem 1 (Absence of spurious local minima). Consider the setup of Section 2.1. If w ≥ 2m(n+1)l, 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 a 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 a 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 it has become the predominant type of activation in practice. Forth, the framework includes constraint as well as unconstraint estimation. Constraint estimation is particularly suitable for wide networks, and for overparameterized networks more generally, because it can 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, our result is a 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(n+1)l = 2(n+1) in the case of a single output (m = 1) and a single hidden layer (l = 1), which coincides with the bounds that have been established for
shallow networks with one output and specific activation functions and estimators—see Lacotte & Pilanci (2020) and references therein. Thus, our theory applies extremly broadly and still gives the expected results in the simple cases. In fact, our proofs only require one layer to have a width of at least 2m(n + 1)l, 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.

heading: 3 UNDERLYING CONCEPTS
text: 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 of path equivalence, which yields a practical characterization of spurious local minima. We then formulate specific parameters that can act as mediators between path-equivalent parameters. The main reason why our proof techniques are quite different from what can be found in the literature is that we cater to deep networks and a range of activation functions.

heading: 3.1 PATH RELATIONS
text: The objective functions for optimizing neural networks are typically continuous but not convex or differentiable. In the following, we characterize the absence of spurious local minima in a way that suits these characteristics of neural networks. The key concept is formulated in the following definition.
Definition 2 (Path relations). Consider two parameters Θ,Γ ∈M. If there is a continuous function hΘ,Γ : [0, 1] → M that satisfies hΘ,Γ[0] = Θ, hΘ,Γ[1] = Γ, and t 7→ l[ghΘ,Γ[t]] is constant, we say that Θ and Γ are path constant and write Θ↔Γ. If there is a continuous function hΘ,Γ : [0, 1]→M that satisfies hΘ,Γ[0] = Θ, hΘ,Γ[1] = Γ, and t 7→ l[ghΘ,Γ[t]] is convex, we say that Θ and Γ are path convex and write Θ^Γ.
If there are parameters Θ′,Γ′ ∈M such that (i) Θ↔Θ′ and Γ↔Γ′ and (ii) Θ′^Γ′, we say that Θ and Γ are path equivalent and write Θ!Γ.
Path constantness means that two parameters are connected by a continuous path of parameters that is constant with respect to the loss; path convexity relaxes “constant” to “convex;” path equivalence allows for additional mediators. The three relations are ordered in the sense that Θ↔Γ⇒ Θ^Γ⇒ Θ!Γ, and they satisfy a number of other basic properties.
Lemma 1 (Basic properties). It holds for all Θ,Γ,Ψ ∈M that
1. Θ↔Θ; Θ^Θ; and Θ!Θ (reflexivity);
2. Θ↔Γ⇒ Γ↔Θ; Θ^Γ⇒ Γ^Θ; and Θ!Γ⇒ Γ!Θ (symmetry).
3. Θ↔Γ and Γ↔Ψ⇒ Θ↔Ψ (transitivity).
The proof is straightforward and, therefore, omitted. The lemma illustrates that the path relations equip the parameter space with solid mathematical structures.
We can finally use the above-stated concepts to characterize spurious local minima.
Proposition 1 (Characterization of spurious local minima). Assume that for all Θ ∈M, there is a global minimum of the objective function (4), denoted by Γ, such that Θ!Γ. Then, the objective function (4) has no spurious local minima.
Hence, path equivalence of all parameters to a global minimum is a sufficient condition for the absence of spurious local minima. This statement is the main result of Section 3.1.

heading: 3.2 BLOCK PARAMETERS
text: 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.
Definition 3 (Block parameters). Consider a number s ∈ {0, 1, . . . } and a parameter Θ ∈M. If
1. (Θ0)ji = 0 for all j > s;
2. (Θv)ij = 0 for all v ∈ {1, . . . , l − 1} and i > s and for all v ∈ {1, . . . , l − 1} and j > s;
3. (Θl)ij = 0 for all j > s,
we call Θ an s-upper-block parameter of depth l.

heading: Similarly, if
text: 1. (Θ0)ji = 0 for all j ≤ p1 − s;
2. (Θv)ij = 0 for all v ∈ {1, . . . , l − 1} and i ≤ pv+1 − s and for all v ∈ {1, . . . , l − 1} and j ≤ pv − s;
3. (Θl)ij = 0 for all j ≤ pl − s,
we call Θ an s-lower-block parameter of depth l. We denote the sets of the s-upper-block and s-lower-block parameters of depth l by Us,l and Ls,l, respectively.
Trivial examples are the 0-block parameters U0 = L0 = {0 = (0pl+1×pl , . . . ,0p1×p0)} and the sblock parameters Us,l = Ls,l =M for s ≥ max{p1, . . . , pl}. 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 a block parameter.
Proposition 2 (Path connections to block parameters). For every Θ ∈M and s ··= m(n+ 1)l, there are Θ,Θ ∈M with Θ ∈ Us,l and Θ ∈ Ls,l such that Θ↔Θ and Θ↔Θ.
In particular, every parameter is path connected to both an upper-block parameter and a 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 a connection between upper-block and lower-block parameters.
Proposition 3 (Path connections among block parameters). Consider two block parameters Θ ∈ Us,l and Γ ∈ Ls,l. If w ≥ 2s, it holds that Θ!Γ.
Hence, every upper-block parameter is 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 1 (All parameters are path equivalent). Consider two arbitrary parameters Θ,Γ ∈M. If w ≥ 2m(n + 1)l, it holds that Θ!Γ.
See Figure 3 for an illustration. The corollary ensures that as long as 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 1 of the previous section.

heading: 4 AUXILLIARY RESULTS
text: In this section, we state four auxilliary results.

heading: 4.1 TWO-LAYER NETWORKS
text: Here, we show that two-layer networks can be reparametrized such that they are indexed by block parameters. We first introduce the notation
r[M, q] ··= |||M |||q = max a∈{1,...,b}
( c∑
j=1
|Maj |q )1/q
for all M ∈ Rb×c, q ∈ (0,∞)
and r[M,∞] ··= |||M |||∞ = maxaj |Maj | for all M ∈ Rb×c. These functions are the building blocks of the constraint on Page 3. Next, given a permutation p : {1, . . . , c} → {1, . . . , c} and a matrix M ∈ Rb×c, we define the matrix Mp ∈ Rb×c through (Mp)ij ··= M ip[j]. Similarly, given a permutation p : {1, . . . , b} → {1, . . . , b} and a matrix M ∈ Rb×c, we define the matrix Mp ∈ Rb×c through (Mp)ji ··= Mp[j]i. The result is then the following: Lemma 2 (Two-Layer networks). Consider three matrices A ∈ Ru×v, B ∈ Rv×o, and C ∈ Ro×r, two constants qA ∈ (0, 1] and qB ∈ (0,∞], and a function h : R→ R. With some abuse of notation, define h : Rv×r → Rv×r through (h[M ])ji ··= h[M ji] for all M ∈ Rv×r. Then, there are matrices A ∈ Ru×v and B ∈ Rv×o and a permutation p : {1, . . . , v} → {1, . . . , v} such that
• Ah[BC] = Aph[BpC];
• r[A, qA] ≤ r[Ap, qA] and r[B, qB ] ≤ r[Bp, qB ];
• Aij = 0 for j > u(r + 1); Bji = 0 for j > u(r + 1) and Bji = (Bp)ji otherwise.
Similarly, there are matrices A ∈ Ru×v and B ∈ Rv×o and a permutation p : {1, . . . , v} → {1, . . . , v} such that
• Ah[BC] = Aph[BpC];
• r[A, qA] ≤ r[Ap, qA] and r[B, qB ] ≤ r[Bp, qB ];
• Aij = 0 for j ≤ v − u(r + 1); Bji = 0 for j ≤ v − u(r + 1) and Bji = (Bp)ji 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.

heading: 4.2 SYMMETRY PROPERTY OF NEURAL NETWORKS
text: Next, we point out a symmetry in our setup for the neural networks. Lemma 3 (Symmetry property). Consider permutations pj : {1, . . . , pj} → {1, . . . , pj} for j ∈ {0, . . . , l + 1}. Assume that p0 and pl+1 are the identity functions: p0[j] = pl+1[j] = j for all j. The parameter Θ ∈M is a spurious local minimum of the objective function (4) if and only if Γ ∈ M defined through (Γj)uv ··= (Θj)pj+1[u]pj [v] for all j ∈ {0, . . . , l}, u ∈ {1, . . . , pj+1}, and v ∈ {1, . . . , pj} is a spurious local minimum of the objective function (4).
The proof follows readily from our setup in Section 2.1 and, therefore, is omitted. The lemma illustrates that the parameterizations of neural networks are highly ambiguous. But in this case, the ambiguity is convenient, because it allows us to permute the rows and columns of the parameters to bring the parameters in shapes that are easy to manage.

heading: 4.3 PROPERTY OF CONVEX FUNCTIONS
text: We now establish a simple property of convex functions.
Lemma 4 (Property of convex functions). Consider a convex function h : [0, 1]→ R. If h[0] > h[̄t] for a t̄ ∈ (0, 1], there is a c ∈ arg mint∈(0,1]{h[t]} such that the function h̃ : [0, 1] → R defined through h̃[t] ··= h[ct] for all t ∈ [0, 1] is nonincreasing and h̃[0] > h̃[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.

heading: 4.4 CARATHÉODORY-TYPE RESULT
text: Carathéodory’s theorem goes back to Carathéodory (1911); see Boltyanski & Martini (2001); Fenchel (1929); Hanner & Rådström (1951) for related results. The following statement combines the classical theorem and the much more recent results Bastero et al. (1995, Theorem 1 and Lemma 1).
Lemma 5 (Carathéodory-Type result). Consider a number q ∈ (0, 1], vectors z1, . . . ,zh ⊂ Rr, and the vectors’ q-convex hull convq[z1, . . . ,zh] ··= { ∑h j=1 t̃jzj : t̃ ∈ [0, 1]h, ||t̃||q = 1}. Then, every
vector v ∈ convq[z1, . . . ,zh] can be written as v = ∑h
j=1 tjzj with t ∈ [0, 1]h, ||t||q ≤ 1, and #{j ∈ {1, . . . , h} : tj 6= 0} ≤ r + 1.
The cardinality of a set A is denoted by #{A} and the `q-norm of a vector v ∈ Ra by ||v||q ··= ( ∑a
j=1|vj |q)1/q. 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 a q-convex combination of at most r + 1 vectors from the set of vectors that generate the q-convex hull. (Note that for q < 1, our definition of the q-convex hull is more restrictive than the standard definition—cf. Bastero et al. (1995, Remark on Page 142)—but it leads to a concise statement and is sufficient for our purposes.)

heading: 5 DISCUSSION
text: 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). A common argument for these estimators is that their objective functions are often convex or equipped with efficient algorithms for optimization (Bien et al., 2018; Friedman et al., 2010), but our results indicate that global optimization of the objective functions in deep learning can be feasible as well.
Our framework allows for arbitrary depths, for constraint as well as unconstraint estimation, essentially arbitrary activation, and for a very wide spectrum of loss functions and input and output data. This generality demonstrates that the absence of spurious local minima is not a feature of specific estimators, network functions, or data but, instead, a universal property of wide networks. Our theory, therefore, supports the use of wide networks in general—possibly 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 our new concepts beyond the presented application.

heading: A PROOFS

heading: A.1 PROOF OF THEOREM 1 AND AN EXTENSION
text: Proof of Theorem 1. The proof combines the main results of Sections 3.1 and 3.2. Let Θ ∈ M be an arbitrary parameter and Γ ∈ M a global minimum of the objective function (4). In view of Proposition 1 in Section 3.1, we need to show that Θ!Γ, and this follows directly from Corollary 1 in Section 3.2.
Figure 1 illustrates that a 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 1 also illustrates that a nonconvex objective function can have “disconnected” global minima, but, in view of Corollary 1 and 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 a set of path-constant parameters. The connectedness of the global minima is of minor importance in practice but an interesting topological property nevertheless.

heading: A.2 PROOF OF PROPOSITION 1
text: Proof of Proposition 1. The key idea is to exploit the properties of monotone functions and convex functions. Let Θ ∈ M be an arbitrary parameter and Γ ∈ M a global minimum of the objective function (4) such that Θ!Γ. Let Θ′,Γ′ ∈ M and hΘ′,Γ′ : [0, 1] → M be as described in Definition 2. Note first that, since Γ↔Γ′ (see Definition 2), the parameter Γ′ is also a global minimum of the objective function. We then use 1. simple algebra, 2. the assumed convexity of the function t 7→ l[ghΘ′,Γ′ ] (see Definition 2 again), 3. the assumed endpoints of the function hΘ′,Γ′ (see Definition 2 once more), 4. the fact that Γ′ is a global minimum of (4), and 5. the fact that (1− t) + t = 1 to derive for all t ∈ [0, 1] that
l [ ghΘ′,Γ′ [t] ] = l [ ghΘ′,Γ′ [(1−t)·0+t·1] ] ≤ (1− t)l [ ghΘ′,Γ′ [0] ] + tl [ ghΘ′,Γ′ [1]
] = (1− t)l [ ghΘ′,Γ′ [0] ] + tl[gΓ′ ]
≤ (1− t)l [ ghΘ′,Γ′ [0] ] + tl [ ghΘ′,Γ′ [0] ] = l [ ghΘ′,Γ′ [0] ] .
Assume first that the inequality is strict: l[ghΘ′,Γ′ [̄t]] < l[ghΘ′,Γ′ [0]] for a t̄ ∈ [0, 1]. Then, by the assumed convexity of t 7→ l[ghΘ′,Γ′ [t]] (see Definition 2) and Lemma 4, there is a c ∈ arg mint∈(0,1]{l[ghΘ′,Γ′ [t]]} such that h̃ : [0, 1] → R defined through h̃[t] ··= l[ghΘ′,Γ′ [ct]] for all t ∈ [0, 1] is nonincreasing, h̃[1] is a global minimum of the objective function (4), and h̃[0] = l[ghΘ′,Γ′ [0]] = l[gΘ′ ] > h̃[1] = l[ghΘ′,Γ′ [c]]. Hence, the function h : [0, 1] → M defined through h[t] ··= hΘ′,Γ′ [ct] for all t ∈ [0, 1] is a function that satisfies the conditions of Definition 1 for the parameter Θ′ and the global minimum h̃[1]. Combining this result with the assumed relationship Θ↔Θ′ (see Definition 2) yields—see Definition 1—the fact that Θ is not a spurious local minimum of the objective function (4).
We can thus assume that t 7→ l[ghΘ′,Γ′ [t]] is constant, which implies Θ ′↔Γ′ by Definition 2. The fact that Θ↔Θ′ (see Definition 2 again) and the transitivity of the path constantness (see Property 3 in Lemma 1) then yield the fact that Θ↔Γ′. Hence, Θ is a global minimum and, therefore, not a spurious local minimum—see Definition 1 again.

heading: A.3 PROOF OF PROPOSITION 2
text: Proof of Proposition 2. Our proof strategy is 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, fj : Rpj×n → Rpj×n through (fj [M ])uv ··= fj [Muv] for all j ∈ {1, . . . , l}, u ∈ {1, . . . , pj}, v ∈ {1, . . . , n}, and M ∈ Rpj×n. We also define the data matrix X ∈ Rd×n through
Xji ··= (xi)j for all j ∈ {1, . . . , d} and i ∈ {1, . . . , n}, that is, each column of X consists of one sample. We finally write
gΘ[X] ··= ( gΘ[x1], . . . , gΘ[xn] ) = Θlfl [ Θl−1 · · · f1[Θ0X] ] ∈ Rm×n for all Θ ∈M .
Hence, gΘ[X] summarizes the network’s outputs for the given data.
Given a parameter Θ ∈M, we establish a corresponding upper-block parameter Θ ∈ Us,l layer by layer, starting from the outermost layer. We write
gΘ[X] = Θ l︸︷︷︸
=:A∈Rpl+1×pl fl︸︷︷︸ =:h
[ Θl−1︸ ︷︷ ︸
=:B∈Rpl×pl−1
fl−1 [ Θl−2 · · · f1[Θ0X] ]︸ ︷︷ ︸ =:C∈Rpl−1×n ] .
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 = A and Bp = B)
gΘ[X] = Θ lfl
[( Θ̃l−1
0
) fl−1 [ Θl−2 · · · f1[Θ0X] ]]
for a matrix Θl ∈ Rpl+1×pl that satisfies r[Θl, 1] ≤ r[Θl, 1] (recall the definition of r on Page 7) and meets Condition 3 in the first part of Definition 3 on block parameters as long as s ≥ pl+1(n + 1) = m(n + 1), and for a matrix Θ̃l−1 ∈ Rm(n+1)×pl−1 that satisfies r[Θ̃l−1, 1] ≤ r[Θl−1, 1] (or r[Θ̃l−1, q] ≤ r[Θl−1, q] if l = 1) and consists of the first m(n + 1) rows of the matrix Θl−1. (We implicitly assume here and in the following pj ≥ m(n + 1)l−j+1 for all j ∈ {1, . . . , l}—which is the generic case in view of Corollary 1—to keep the notation manageable, but extending the proof to the general case is straightforward.)
Now, define a parameter Γl ∈M through
Γl ··= (Θl,Θl−1, . . . ,Θ0)
and a function hΘ,Γl : [0, 1]→M through
hΘ,Γl [t] ··= (1− t)Θ + tΓl for all t ∈ [0, 1] .
The function hΘ,Γl is continuous and satisfies hΘ,Γl [0] = Θ and hΘ,Γl [1] = Γl. Moreover, we can 1. use the definitions of the function hΘ,Γl and the networks, 2. split the network along the outermost layer, 3. invoke the block shape of Θl and the definition of Θ̃l−1 as the m(n + 1) first rows of the matrix Θl−1, 4. use the above-stated inequalities for the network gΘ[X], and 5. consolidate the terms to show for all t ∈ [0, 1] that
gh Θ,Γl
[t][X] = ( (1− t)Θl + tΘl ) fl [ Θl−1 · · · f1[Θ0X] ] = (1− t)Θlfl [ Θl−1 · · · f1[Θ0X] ] + tΘlfl [ Θl−1 · · · f1[Θ0X]
] = (1− t)Θlfl [ Θl−1 · · · f1[Θ0X] ] + tΘlfl [( Θ̃l−1
0
) · · · f1[Θ0X] ] = (1− t)gΘ[X] + tgΘ[X] = gΘ[X] .
Hence, the function t 7→ l[gh Θ,Γl [t]] is constant. Finally, we use 1. the definition of the constraint in (3), 2. the definition of the function hΘ,Γl , 3. the convexity of the `1-norm, 4. the above stated fact that r[Θl, 1] ≤ r[Θl, 1], 5. a consolidation, 6. again the definition of the regularizer, and 7. the fact that Θ ∈M to show for all t ∈ [0, 1] that
r [ hΘ,Γl [t] ] = max { ar max
j∈{1,...,l} ∣∣∣∣∣∣(hΘ,Γl [t])j∣∣∣∣∣∣1, br∣∣∣∣∣∣(hΘ,Γl [t])0∣∣∣∣∣∣q} = max { ar max
j∈{1,...,l−1} |||Θj |||1, ar|||(1− t)Θl + tΘl|||1, br|||Θ0|||q } ≤ max { ar max
j∈{1,...,l−1} |||Θj |||1, (1− t)ar|||Θl|||1 + tar|||Θl|||1, br|||Θ0|||q
}
≤ max { ar max
j∈{1,...,l−1} |||Θj |||1, (1− t)ar|||Θl|||1 + tar|||Θl|||1, br|||Θ0|||q } = max { ar max
j∈{1,...,l−1} |||Θj |||1, ar|||Θl|||1, br|||Θ0|||q } = r[Θ]
≤ 1 . Hence, hΘ,Γl [t] ∈ M for all t ∈ [0, 1]. In conclusion, we have shown—see Definition 2—that Θ and Γl are path constant: Θ↔Γl. We then move one layer inward. Lemma 2 ensures that (recall again Lemma 3)
Θ̃l−1︸ ︷︷ ︸ A∈Rm(n+1)×pl−1 fl−1︸︷︷︸ h
[ Θl−2︸ ︷︷ ︸
B∈Rpl−1×pl−2 · · · f1[Θ0X]︸ ︷︷ ︸ C∈Rpl−2×n
] = Θ̇l−1fl−1
[( Θ̃l−2
0
) · · · f1[Θ0X] ]
for a matrix Θ̇l−1 ∈ Rm(n+1)×pl−1 that satisfies r[Θ̇l−1, 1] ≤ r[Θ̃l−1, 1] ≤ r[Θl−1, 1] and meets Condition 3 in the first part of Definition 3 on block parameters as long as s ≥ m(n + 1)2, and for a matrix Θ̃l−2 ∈ Rm(n+1)2×pl−2 that satisfies r[Θ̃l−2, 1] ≤ r[Θl−2, 1] (or r[Θ̃l−2, q] ≤ r[Θl−2, q] if l = 2) and consists of the first m(n + 1)2 rows of the matrix Θl−2.
Next, we define Θl−1 ∈ Rpl×pl−1 through (Θl−1)uv ··= (Θ̇l−1)uv for u ≤ m(n + 1) and (Θl−1)uv ··= 0 otherwise. Combining this definition with the above-derived results yields
gΘ[X] = Θ lfl [ Θl−1fl−1 [( Θ̃l−2
0
) · · · f1[Θ0X] ]] ,
and the matrix Θl−1 satisfies r[Θl−1, 1] = r[Θ̇l−1, 1] ≤ r[Θl−1, 1] and meets Condition 2 in the first part of Definition 3 on block parameters as long as s ≥ m(n + 1)2.
Similarly as above, define a parameter Γl−1 ∈M through
Γl−1 ··= (Θl,Θl−1,Θl−2, . . . ,Θ0)
and a function hΓl,Γl−1 : [0, 1]→M through
hΓl,Γl−1 [t] ··= (1− t)Γl + tΓl−1 for all t ∈ [0, 1]
to show that Γl↔Γl−1. In view of Property 3 in Lemma 1, we can conclude that Θ↔Γl−1. Finish the proof by induction over the layers, and note that the lower-block parameters can be established in the same way.

heading: A.4 PROOF OF PROPOSITION 3
text: Proof of Proposition 3. The key ingredient of the proof is the assumed block structure of the parameters. Consider two block parameters Θ ∈ Us,l and Γ ∈ Ls,l and define the parameters
Θ′ ··= (Θl,Θl−1 + Γl−1, . . . ,Θ0 + Γ0) ∈M ; Γ′ ··= (Γl,Θl−1 + Γl−1, . . . ,Θ0 + Γ0) ∈M
and the function
hΘ′,Γ′ : [0, 1] → M t 7→ (1− t)Θ′ + tΓ′ = ( (1− t)Θl + tΓl,Θl−1 + Γl−1, . . . ,Θ0 + Γ0 ) .
By the row-wise structure of the constraint (see Page 3 again), the convexity of the `1-norm, and the block shapes of the parameters (see Figure 2 again), we can find that r[hΘ′,Γ′ [t]] ≤ max{r[Θ], r[Γ]} ≤ 1 for all t ∈ [0, 1], that is, hΘ′,Γ′ [t] ∈ M for all t ∈ [0, 1]. One can also verify readily the fact that the function hΘ′,Γ′ is continuous, hΘ′,Γ′ [0] = Θ′, and hΘ′,Γ′ [1] = Γ′. Next, we define
[Θ′,Γ′]c1,c2 ··= (c1Θl + c2Γl,Θl−1 + Γl−1, . . . ,Θ0 + Γ0) ∈M for all c1, c2 ∈ R ,
which generalizes hΘ′,Γ′ in the sense that hΘ′,Γ′ [t] = [Θ′,Γ′]1−t,t for all t ∈ [0, 1]. We then 1. invoke the definition of [Θ′,Γ′]c1,c2 and the definition of the networks in (1), 2. split the network along the outer layer, 3. use the block structures of the parameters and the assumption that fj [b] = (fj [b1], . . . , f j [bpj ]) > for all j ∈ {1, . . . , l} and b ∈ Rpj , 4. continue in this fashion, and 5. invoke again the definition of the networks in (1) to find for all c1, c2 ∈ R and x ∈ Dx that g[Θ′,Γ′]c1,c2 [x]
= (c1Θ l + c2Γ l)fl [ (Θl−1 + Γl−1)fl−1 [ · · · f1 [ (Θ0 + Γ0)x ]]] = c1Θ lfl [ (Θl−1 + Γl−1)fl−1 [ · · · f1 [ (Θ0 + Γ0)x
]]] + c2Γ lfl [ (Θl−1 + Γl−1)fl−1 [ · · · f1 [ (Θ0 + Γ0)x
]]] = c1Θ lfl [ Θl−1fl−1 [ · · · f1 [ (Θ0 + Γ0)x ]]] + c2Γ lfl [ Γl−1fl−1 [ · · · f1 [ (Θ0 + Γ0)x
]]] = · · · = c1Θlfl [ Θl−1fl−1 [ · · · f1 [ Θ0x ]]] + c2Γ lfl [ Γl−1fl−1 [ · · · f1 [ Γ0x
]]] = c1gΘ[x] + c2gΓ[x] .
Finally, we use 1. the definition of the function hΘ′,Γ′ and of the parameter [Θ′,Γ′]c1,c2 , 2. the above display with c1 = 1− (1− a)t1 − at2 and c2 = (1− a)t1 + at2, 3. a rearrangement of the terms, 4. the assumed convexity of the loss function l, 5. again the above display, and 6. again the definition of hΘ′,Γ′ , to find for all a, t1, t2 ∈ [0, 1] that
l [ ghΘ′,Γ′ [(1−a)t1+at2] ] = l [ g[Θ′,Γ′]1−(1−a)t1−at2,(1−a)t1+at2
] = l [( 1− (1− a)t1 − at2 ) gΘ + ( (1− a)t1 + at2 ) gΓ
] = l [( (1− a)− (1− a)t1 ) gΘ + (a− at2)gΘ + (1− a)t1gΓ + at2gΓ
] = l [ (1− a) ( (1− t1)gΘ + t1gΓ ) + a ( (1− t2)gΘ + t2gΓ
)] ≤ (1− a)l [ (1− t1)gΘ + t1gΓ ] + al [ (1− t2)gΘ + t2gΓ
] = (1− a)l [ g[Θ′,Γ′]1−t1,t1 ] + al [ g[Θ′,Γ′]1−t2,t2
] = (1− a)l [ ghΘ′,Γ′ [t1] ] + al [ ghΘ′,Γ′ [t2] ] ,
which means that t 7→ l[ghΘ′,Γ′ [t]] is convex. We conclude—see Definition 2—that Θ ′^Γ′.
In view of Definition 2, it is left to show that Θ↔Θ′ and Γ↔Γ′. Consider now the function hΘ,Θ′ : [0, 1] → M
t 7→ (Θl,Θl−1 + tΓl−1, . . . ,Θ0 + tΓ0) . By the row-wise structure of the constraint (see Page 3 once more) and the block shapes of the parameters (see Figure 2 once more), we can find that r[hΘ,Θ′ [t]] ≤ max{r[Θ], r[tΓ]} ≤ 1 for all t ∈ [0, 1], that is, hΘ,Θ′ [t] ∈ M for all t ∈ [0, 1]. One can also verify readily the fact that the function hΘ,Θ′ is continuous, hΘ,Θ′ [0] = Θ, and hΘ,Θ′ [1] = Θ′. Moreover, we can 1. invoke the definition of hΘ,Θ′ 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 4. invoke the definitions of the function hΘ,Θ′ and the networks in (1) again to find for all t ∈ [0, 1] and x ∈ Dx that
ghΘ,Θ′ [t][x] = Θ lfl [ (Θl−1 + tΓl−1)fl−1 [ · · · f1 [ (Θ0 + tΓ0)x ]]] = Θlfl [ Θl−1fl−1 [ · · · f1 [ (Θ0 + tΓ0)x ]]]
= · · · = Θlfl [ Θl−1fl−1 [ · · · f1 [ Θ0x ]]] = ghΘ,Θ′ [0][x] ,
which implies that the function t 7→ l[ghΘ,Θ′ [t]] is constant. We conclude that—see Definition 2— that Θ↔Θ′. We can show in a similar way that Γ↔Γ′. Hence, given Definition 2, we find that Θ!Γ, as desired.

heading: A.5 PROOF OF LEMMA 2
text: Proof of Lemma 2. The proof is essentially a careful reparametrization. We proceed in three steps: see Figure 4 for an overview.
Step 1: Fix a k ∈ {1, . . . , u}. We first show that there is a matrix Ȧ ∈ Ru×v such that
1. Ȧh[BC] = Ah[BC];
2. r[Ȧ, qA] ≤ r[A, qA];
3. #{j ∈ {1, . . . , v} : Ȧkj 6= 0} ≤ r + 1;
4. Ȧaj = Aaj for all a 6= k.
Hence, we replace the matrix A, which contains the “output parameters,” by a matrix whose kth row has at most r + 1 nonzero entries—see the illustration in Figure 4.
The proof of this step is based on our version of Carathéodory’s theorem in Lemma 5. For every k ∈ {1, . . . , u} and i ∈ {1, . . . , r}, elementary matrix algebra yields that
( Ah[BC] ) ki = v∑ j=1 Akj ( h[BC] ) ji .
Denoting the row vectors of a matrix M ∈ Ra×b by M1•, . . . ,Ma• ∈ Rb, we then get( Ah[BC] ) k• = v∑ j=1 Akj ( h[BC] ) j• .
The case ||Ak•||qA = 0 is straightforward to deal with: all elements of Ak• are then equal to zero, and we can just set Ȧ ··= A. We can thus assume the fact that ||Ak•||qA 6= 0. We then get from the preceding equality that(
Ah[BC] ) k• = v∑ j=1 Akj ||Ak•||qA︸ ︷︷ ︸
=:t̃j
||Ak•||qA ( h[BC] ) j•︸ ︷︷ ︸
=:zj
.
Since
||t̃||qA =
( v∑
j=1
|t̃j |qA )1/qA = ( v∑
j=1
∣∣∣∣ Akj||Ak•||qA ∣∣∣∣qA )1/qA
= 1
||Ak•||qA
( v∑
j=1
|Akj |qA )1/qA
= ||Ak•||qA ||Ak•||qA = 1 ,
the previous equality means that the vector (Ah[BC])k• ∈ Rr is a qA-convex combination of the 2v vectors z1, . . . ,zv,−z1, . . . ,−zv ∈ Rr, that is, (Ah[BC])k• ∈ convq[z1, . . . ,zv,−z1, . . . ,−zv].
Hence, by Lemma 5, there is a t ∈ [−1, 1]v such that ||t||qA ≤ 1, #{j ∈ {1, . . . , v} : tj 6= 0} ≤ r + 1, and (
Ah[BC] ) k• = v∑ j=1 tj ||Ak•||qA ( h[BC] ) j• .
Hence, by the definition of the row vectors,( Ah[BC] ) ki = v∑ j=1 tj ||Ak•||qA ( h[BC] ) ji
for all i ∈ {1, . . . , r}, and, more generally, we find for all a ∈ {1, . . . , u} and i ∈ {1, . . . , r} that( Ah[BC] ) ai = {∑v j=1 tj ||Ak•||qA ( h[BC] ) ji for a = k ;∑v j=1 Aaj ( h[BC] ) ji otherwise .
This motivates us to define Ȧ ∈ Ru×v through Ȧaj ··= { tj ||Ak•||qA for a = k ; Aaj otherwise .
Properties 1, 3, and 4 then follow immediately. Property 2 can be derived by using 1. the definition of the basic regularizer r on Page 7, 2. the definition of Ȧ, 3. the linearity of finite sums, 4. the definition of the `q-norms on Page 8, 5. the above-derived property ||t||qA ≤ 1, 6. a consolidation, and 7. again the definition of the basic regularizer r on Page 7:(
r[Ȧ, qA] )qA
= max a∈{1,...,u} v∑ j=1 |Ȧaj |qA
= max a∈{1,...,u}
{∑v j=1 ∣∣tj ||Ak•||qA∣∣qA for a = k∑v j=1|Aaj |qA otherwise
= max a∈{1,...,u}
{ ||Ak•||qAqA ∑v j=1|tj |qA for a = k∑v
j=1|Aaj |qA otherwise
= max a∈{1,...,u}
{(∑v j=1|Akj |qA ) ||t||qAqA for a = k∑v
j=1|Aaj |qA otherwise
≤ max a∈{1,...,u} {∑v j=1|Akj |qA for a = k∑v j=1|Aaj |qA otherwise
= max a∈{1,...,u} v∑ j=1 |Aaj |qA
= ( r[A, qA] )qA ,
as desired. This concludes the proof of the first step.
Step 2: We now show that there is a matrix Ã ∈ Ru×v such that
1. Ãh[BC] = Ah[BC];
2. r[Ã, qA] ≤ r[A, qA];
3. #{j ∈ {1, . . . , v} : Ãaj 6= 0} ≤ r + 1 for all a ∈ {1, . . . , u}.
Hence, we replace the matrix A by a matrix whose every row has at most r + 1 nonzero entries—see again the illustration in Figure 4.
Since Step 1 changes only the kth row of A (see Property 4 derived in Step 1), we can apply it to one row after another.
Step 3: We finally prove the first part of the lemma—see again the illustration in Figure 4.
By Property 3 of the previous step, the matrix Ã has at most u(r + 1) nonzero columns. Verify that replacing A by Ap and B by Bp for a suitable permutation p leads to an Ã whose entries outside the first u(r + 1) columns are equal to zero—while all other properties remain intact. We denote this version of Ã by A. We then derive for all j ∈ {1, . . . , v} and i ∈ {1, . . . , r} that
( h[BpC] ) ji = h [ (BpC)ji ] = h
[ o∑
b=1
(Bp)jbCbi ] = h [ o∑
b=1
(C>)ib(B p)jb ] = h [ (C>(Bp)j•)i ] = ( h[C>(Bp)j•] ) i ,
where we define (with some abuse of notation) h : Rr → Rr through (h[b])i ··= h[bi] for all b ∈ Rr. Combining this result with the results of Step 2 (with A and B replaced by Ap and Bp, respectively) yields for all a ∈ {1, . . . , u} and i ∈ {1, . . . , r} that
( Aph[B pC] ) ai = v∑ j=1 (Ap)aj ( h[BpC] ) ji = v∑ j=1 (Ap)aj ( h[C>(Bp)j•] ) i
= v∑ j=1 Aaj ( h[C>(Bp)j•] ) i = min{u(r+1),v}∑ j=1 Aaj ( h[C>(Bp)j•] ) i .
We then define B ∈ Rv×o through
Bji ··= {
(Bp)ji = Bp[j]i for j ≤ u(r + 1) ; 0 otherwise .
We then use 1. the above-stated equality, 2. the definition of B, 3. a similar derivation as above, 4. the block structure of A, and 5. a similar derivation as above to establish for all a ∈ {1, . . . , u} and i ∈ {1, . . . , r} the fact that
( Aph[B pC] ) ai = min{u(r+1),v}∑ j=1 Aaj ( h[C>(Bp)j•] ) i
= min{u(r+1),v}∑ j=1 Aaj ( h[C>Bj•] ) i
= min{u(r+1),v}∑ j=1 Aaj ( h [ BC ]) ji
= v∑ j=1 Aaj ( h [ BC ]) ji
= ( Ah[BC] ) ai .
The other properties stated in the lemma follow readily.
The second part of the lemma can be derived in the same way.

heading: A.6 PROOF OF LEMMA 4
text: Proof of Lemma 4. The proof is a simple exercise in calculus. An illustration of the quantities involved in the proof is given in Figure 5. The function h is convex by assumption; hence, it is continuous. Then, according to the extreme value theorem, there is a number
c ∈ arg min t∈[0,1]
{ h[t] } .
Since h[̄t] < h[0] for a t̄ ∈ (0, 1], it holds that c ∈ (0, 1]. Now consider t2 ∈ [0, 1] and t1 ∈ [0, t2), that is, t2 > t1. Basic calculus ensures that
h̃[t2] = h[ct2] = h [ ct1 + ct2 − ct1 ] = h [ ct1 +
ct2 − ct1 c− ct1
(c− ct1) ]
= h [ ct1 +
t2 − t1 1− t1
(c− ct1) ]
= h [( 1− t2 − t1
1− t1
) ct1 +
t2 − t1 1− t1 c ] ≤ (
1− t2 − t1 1− t1
) h[ct1] +
t2 − t1 1− t1 h[c]
≤ (
1− t2 − t1 1− t1
) h[ct1] +
t2 − t1 1− t1 h[ct1]
= h[ct1]
= h̃[t1] .
Hence, h̃ is nonincreasing.
Moreover, h̃[0] = h[c · 0] = h[0] > h[̄t] ≥ h[c] = h[c · 1] = h̃[1] .
Hence, h̃[0] > h̃[1]. This concludes the proof.

Review summaries:
This 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.

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. 

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