{'fraction_non_alphanumeric': 0.058463413218824346, 'fraction_numerical': 0.021557476933789822, 'mean_word_length': 3.8737273755656108, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Statistical Guarantees for Approximate Stationary Points of Simple Neural Networks

Since statistical guarantees for neural networks are usually restricted to global optima of intricate objective functions, it is not clear whether these theories really explain the performances of actual outputs of neural-network pipelines. The goal of this paper is, therefore, to bring statistical theory closer to practice. We develop statistical guarantees for simple neural networks that coincide up to logarithmic factors with the global optima but apply to stationary points and the points nearby. These results support the common notion that neural networks do not necessarily need to be optimized globally from a mathematical perspective. More generally, despite being limited to simple neural networks for now, our theories make a step forward in describing the practical properties of neural networks in mathematical terms.


Introduction
Statistical theories for deep learning usually apply to exact, global optima of certain objective functions (Bartlett, 1998;Bartlett and Mendelson, 2002;Bauer and Kohler, 2019;Lederer, 2020a;Taheri et al., 2021;Schmidt-Hieber, 2020). But those objective functions cannot be solved explicitly and are highly non-convex, so that in practice, exact, global optimization is-at least to date-out of reach, and we can expect only approximate stationary points from current algorithms (see Figure 1). In other words, it is unclear whether the known theories have any meaning for the outputs of actual deep-learning pipelines.
Also other parts of machine learning face optimization problems that are challenging to optimize globally and to full precision. Accordingly, some statistical insights have already been established. For example, Bien et al. (2018Bien et al. ( , 2019 solve a non-convex problem in linear regression in a "convex" way and develop statistical theories for their solution. Loh and Wainwright (2015); Loh (2017) develop statistical theory for stationary points in another regression setup under curvature assumptions. Elsener and van de Geer (2018) establish more general theories for stationary points also under curvature assumptions. Taheri et al. (2019) propose an algorithm and statistical theory for approximate solutions in a convex setting. But it is currently unclear how to extend these insights to deep learning-if at all possible. In this paper, we develop statistical guarantees for the stationary points of simple neural networks (Theorem 1) and for the points in the vicinity of a stationary point (Theorem 2). Strikingly, the statistical rates match the "theoretical" rates in Taheri et al. (2021) up to log-terms. Hence, although our theories here are limited to simple networks, our paper makes a significant step toward the mathematical understanding of practical neural-network pipelines.
Motivation Let us briefly motivate our study in a very simple example. Consider regression data consisting of the two input-output pairs (x 1 , y 1 ) = (−1, 0) and (x 2 , y 2 ) = (1, 1). On the one hand, we can relate the inputs and outputs through a simple linear-regression model y i = ω * x i + u i parameterized by ω * ∈ R. The least-squares estimate for ω * minimizes the objective function f 1 : ω → ω 2 + (1 − ω) 2 . The function f 1 is benign; in particular, it is smooth and convex (see the left panel of Figure 2).
On the other hand, we can also relate the inputs and outputs through a very simple linear neuralnetwork model y i = γ * θ * x i + u i parametrized by γ * , θ * ∈ R. The least-squares estimate for γ * , θ * minimizes the objective function f 2 : (γ, θ) → (γθ) 2 + (1 − γθ) 2 . The earlier estimate and the one here are equivalent from a statistical perspective: we can simply identify ω with the product γθ. But the reparametrization changes the computational properties: the function f 2 is not benign any more; in particular, it is not convex (see the right panel of Figure 2).
This simple example illustrates that going from linear regression and other standard models to neural networks naturally leads to computational challenges; in particular, the corresponding objective functions are usually non-convex, which means that optimization algorithms may easily get stuck in non-optimal stationary points. Thus, we argue that statistical guarantees in deep learning should concern stationary points rather than just global optima.
Paper outline In Section 2, we state the statistical guarantees for the stationary points of the neural-network objectives (Theorem 1) and the statistical guarantees for approximations of a stationary point (Theorem 2). We provide some numerical observations in Section 3. In Section 4, we study the behavior of the Hessian matrix of the population risk (Proposition 3) and then employ tools from empirical-process theory to bound the absolute difference between the gradient vector of the prediction and population risk (Lemma 4); these are the main ingredients for proving our Theorem 1. In Section 5, we provide an overview of the related works. More technical results and detailed proofs are deferred to the Section 6. We conclude our paper in Section 7.

Main results
Consider inputs x 1 , . . . , x n ∈ R d and corresponding outputs y 1 , . . . , y n ∈ R that are connected via for an unknown target function f : R d → R and unknown stochastic noise u 1 , . . . , u n ∈ R. Deep learning is about using the available data to approximate the unknown target function f by a neural network. In this paper, we consider shallow and linear neural networks of the form where (γ, Θ) ∈ B · · = (γ, Θ) ∈ R w × R w×d .
We assume that the target function can be approximated by such a neural network in the first place: there is a pair (γ * , Θ * ) ∈ B such that f[x] ≈ γ * Θ * x. In fact, to have a sharp focus on statistical guarantees rather than the approximation properties of neural networks, we simply assume that ||γ * || 1 , |||Θ * ||| 1 ≤ √ log n and f[x] = γ * Θ * x for all x ∈ R d , that is, the target function is itself a neural network with reasonably small parameters. 1 Note that parametrization of neural networks is ambiguous: there are typically infinitely many pairs (γ * , Θ * ) ∈ B that satisfy those conditionscompare to Taheri et al. (2021, Proposition 1); for further reference, we define β * · · = vec(γ * , Θ * ) for a fixed but arbitrary such pair of parameters. Note that the concentration of this study is on linear neural networks. Although linear neural networks are not used in practice, theoretical understanding of them is important because, they may reveal some properties of non-linear models (see our Section 3), while theoretical study of them is more simple.
The network parameters in deep learning are usually estimated via standard statistical techniques, such as least-squares or logistic loss, complemented by some type of regularization, such as dropout (Hinton et al., 2012;Neklyudov et al., 2017;Salehinejad and Valaee, 2019), batch normalization (Ioffe and Szegedy, 2015), explicit regularization (Alvarez and Salzmann, 2016;Feng and Simon, 2017;Liu et al., 2015;Scardapane et al., 2017), or low-rank approximation (Denil et al., 2013;Denton et al., 2014;Jaderberg et al., 2014). To fix ideas, we focus on least-squares 1. The bound √ log n here and on the next page is merely for convenience: it can be replaced by any fixed constant or another function that is increasing mildly in the sample size n. complemented by (elementwise) 1 -regularization: where r ∈ [0, ∞) is a tuning parameter to be calibrated (see Sardy et al. (2020) for some theory insights). Such estimators are standard in machine learning and statistics (Lederer, 2022;Eldar and Kutyniok, 2012). As usual, we measure the (in-sample-)prediction risk by with X · · = (x 1 , . . . , x n ) ∈ R n×d and the generalization risk by with the expectation over a new sample (x, y) (that has the same distribution as x 1 , . . . , x n and y 1 , . . . , y n ). We call β · · = vec( γ, Θ) a stationary point of the objective in (2) if it satisfies (Elsener and van de Geer, 2018, Equation 6); (Loh and Wainwright, 2015, Equation 5) for appropriatez ∈ ∂|| β|| 1 (where ∂|| β|| 1 is the subdifferential of the regularizer at β). We call a stationary point β reasonable once || γ|| 1 , ||| Θ||| 1 ≤ √ log n-again to avoid unnecessary complication. Due to the ambiguity of neural networks, there are infinitely many equivalent stationary and reasonable stationary points; importantly, our guarantees hold for every (reasonable) stationary point and target β * .
We say that a network indexed by ( γ, Θ) generalizes well if that is, the network generalizes essentially as well as the best network. In the following, we show that not only the "statistical" network indexed by ( γ, Θ) but also every "practical" network indexed by a reasonable stationary point ( γ, Θ) of the objective function in (2) generalizes well. For simplicity, we assume that x 1 , . . . , x n ∈ N (0, I d×d ) are i.i.d. standard Gaussian random vectors and that u 1 , . . . , u n ∈ N (0, σ 2 ) are centered and Gaussian random variables and independent of x i . Moreover, we call the total number of parameters in the network p · · = w+w·d the problem's effective dimension and r orc · · = ν(log n) 3/2 log(np) n (4) the oracle tuning parameter, where ν ∈ (0, ∞) is a constant that depends only on the distributions of the inputs and noises. It has been shown that r orc is indeed an optimal tuning parameter of (2) in some sense (Taheri et al., 2021). We then get the following result for a new sample pair (x, y) with the same distribution as x 1 , . . . , x n and y 1 , . . . , y n .
Theorem 1 (Statistical Guarantees for All Reasonable Stationary Points) Any reasonable stationary point ( γ, Θ) of the objective function in (2) with r ≥ r orc satisfies the risk bound with probability at least 1 − 1/2n. If r = r orc , the bound becomes The proof of Theorem 1 is given in Section 6.2. Theorem 1 proves the fact that for properly chosen tuning parameter r and large enough sample sizes, any reasonable stationary point of (2) generalizes essentially as well as β * . Our results essentially have the same rates as the ones in the literature (Taheri et al., 2021, Theorem 3) but, in stark contrast to those results, apply to all reasonable stationary points (including saddle points) rather than to the global optimum of the objective function only.
The assumption of Gaussian noise can be relaxed readily by replacing the Gaussian-type results in the empirical-process derivations by more general results (Adamczak, 2008;Lederer and van de Geer, 2014;van de Geer and Lederer, 2013;Wellner, 2017).
Note that in finite time, stationary points can be computed just approximately using gradientbased algorithms. Now we extend our results in Theorem 1 to the points that are close but not necessarily equal to a stationary points. We define a pair ( γ, Θ) as a τ −approximate stationary for a τ ∈ [0, ∞). Employing gradient based algorithms (in finite time), we can expect to get close to a stationary point in the sense that β ≈ β (Lei et al., 2019). Then also || β|| 1 ≈ || β|| 1 , which means that an approximation of a reasonable stationary point is also reasonable once τ is small enough. Then, we extract statistical guarantees for every practical network indexed by an approximate-reasonable stationary as following: Theorem 2 (Statistical Guarantees for Approximate Stationary Points) Suppose that ( γ, Θ) is a τ −approximate stationary point and that the conditions of Theorem 1 are satisfied. Then, we have with probability at least 1 − 1/n. If r = r orc , the bound becomes The proof of Theorem 2 is given in Section 6.2. The bounds match the earlier ones with only two small differences: 1. a summand τ is added to our statistical bounds and 2. the factor 5 in Equation (5) is replaced by a factor of 8 in Equation (8). Theorem 2 might look like a trivial extension of Theorem 1, but seem to be a trivial observation, but the fact that Equation (7) involves the (in-sample-)prediction risk and the sparsity factors make the proof considerably more involved.

Numerical observations
We provide here some numerical observations to clarify theories of Section 2. We minimize a leastsquares complemented by 1 -regularization for shallow neural networks with 1. linear and 2. ReLU activation functions. We consider neural networks with d = w = 10, that are trained over 500 and tested over 300 data sample generated from a standard normal distribution and labeled by a sparse-target network (having the same structure as above) plus a Gaussian noise. Note that here, we train the networks in a finite time, that means, trained networks are just an approximation of a stationary point (due to the non-convexity). We report the relative training error and the relative test error for a potential global optima and an approximate stationary point for linear and ReLU networks in Table 1. Let note that the potential global optima and approximate stationary point are reached over multiple times of training on a fixed data set and assigned by the trained networks with the lowest and highest training error, respectively (we reference to Figure 3 in Section 6.2 for a graphical view of convergence in training). Due to the non-convexity of the objective function,

Technical results
In this section, we provide technical results that are essential for proving our Theorem 1 but might also be of interest by themselves.
The proof of Lemma 4 is given in Section 6.2. The result above establishes a bound for the absolute difference between ∇risk X [ γ, Θ] and ∇risk[ γ, Θ] for every reasonable stationary point ( γ, Θ) ∈ B. We employ the result above for choosing the optimal tuning parameter. Proposition 3 and Lemma 4 are the main ingredients for proving our Theorem 1.

Related literature
Statistical theories for neural networks have widely been studied (Bartlett, 1998;Bartlett and Mendelson, 2002;Bauer and Kohler, 2019;Beknazaryan, 2021;Lederer, 2020a;Ma et al., 2022;Taheri et al., 2021;Schmidt-Hieber, 2020), but due to the non-convexity of neural-network objectives, it is unclear whether these theories can be applied for the outputs of actual deep-learning pipelines.
Non-convex objectives are also of interest in other parts of machine learning: Bien et al. (2018Bien et al. ( , 2019 solve a non-convex problem in linear regression in a "convex" way and they develop statistical theories for their solution. Loh and Wainwright (2015, Theorems 1,2) extract statistical guarantees for stationary points of non-convex objectives (allowing for non-convexity in both loss and penalty functions) in a regression-type settings, under a so-called "restricted-strong convexity" condition over the empirical loss (see their Display (4)). Loh (2017, Theorem 1) studies the behavior of stationary points of penalized robust estimators in a linear-regression setting. They prove that under a local "restricted-strong convexity" condition, stationary points within the region of restricted curvature are statistically consistent with the target. Also Elsener and van de Geer (2018, Theorem 1) derive sharp oracle inequalities for stationary points of general non-convex objectives made by a non-convex loss plus a convex penalty, under a restrictive condition called "two point marginal condition" on the theoretical loss. They exemplify their bounds for simple models like robust regression and binary classification. Their condition is kinda similar to the restricted-strong convexity but on the theoretical loss (and not on the empirical loss). Unfortunately, the curvature assumptions in these papers are infeasible for neural network settings, which means that their approaches cannot be applied here.
Another interesting direction is studying optimization landscape of non-convex objectives in deep learning (Eftekhari, 2020;Hardt and Ma, 2016;Kawaguchi, 2016;Lederer, 2020c;Mei et al., 2018;Zhou and Liang, 2018;Zhang et al., 2016;Yun et al., 2017). Yun et al. (2017) study the optimization landscape of deep and linear neural networks. They extract necessary and sufficient conditions for a critical point to be the global optima of the least-squares loss under some assumptions (input dimensions upper bounded by the number of data examples, XX and Y X have full rank). They prove that for wide enough networks, a critical point of the empirical risk is a global minimum, if and only if the product of all the parameter matrices is of full rank (Yun et al., 2017, Theorem 1). Their result actually provide an efficiently checkable test for global optimality and also is extended for nonlinear networks. Kawaguchi (2016, Theorem 2.3) proves that for deep and linear neural networks and under some assumptions (XX and XY have full rank), every local minimum is a global minimum and every critical point that is not a global minimum is a saddle point. They also prove that the same results hold for nonlinear-neural networks but under unrealistic assumptions (Kawaguchi, 2016, Corollary 3.2). Zhou and Liang (2018, Theorem 2) also prove that linear neural networks with leastsquares loss have no spurious local minimum. In any case, while interesting, these works do not provide statistical insights into the problem.

More technical results and proofs
In this section, we establish five auxiliary results and then the proofs of all our claims.

More technical results
We first differentiate the empirical risk risk X [γ, Θ] with respect to the parameters β = vec(γ, Θ). We use the indices j, k for the first-order partial derivatives and indices j , k for the second-order partial derivatives.
Lemma 5 (First-and Second-Order Partial Derivatives of the Empirical Risk) It holds for each j, j ∈ {1, . . . , w} and k, k ∈ {1, . . . , d} that These derivatives are basic tools for us given that we work with stationary points. The proof of Lemma 5 is given in Section 6.2. The next result is essentially a population version of the partial derivatives in Lemma 5, that is, sums are replaced by expectations.
The proof of Lemma 7 is given in Section 6.2.
The set C η, contains all parameters in a neighborhood of β * ; in particular, the bound applies to β * = vec(γ * , Θ * ) itself-without any further assumption on β * . The lemma is the main ingredient of our proof of Lemma 4.
We derive a uniform bound on the absolute difference between risk X [γ, Θ] and risk[γ, Θ].
Lemma 8 is the main ingredient of our proof of Theorem 2. The proof of Lemma 8 is given in Section 6.2. We finally derive a lemma studying invertibility of the line segment between two matrices. This lemma is employed in the proof of Theorem 1.
The proof of Lemma 9 is given in Section 6.2.

Proofs
Here, we provide the proofs of our main claims.

Proof of Theorem 1
Proof The proof approach is based on Taylor's theorem and the definition of stationary points.
We start by defining some notations: We use the notation γ Θ Ax · · = γ [Θ, A]x to generate an extended network indexed by (γ, is a matrix whose columns are basis of R w−1 such that γ v 1 = · · · = γ v w−1 = 0. It means, the input's dimension of the network is extended from d to d + w − 1 and so the inner-layer matrix need also to be extended from Θ ∈ R w×d to [Θ, A] ∈ R w×(d+w−1) . We also use the notation γ α Θ α,Ax to make an extended network that is also rescaled across the layers by a suitable α. Note that the notation Θ α,A is equivalnet with (Θ A ) α , both means we rescale a matrix Θ A ∈ R w×(d+w−1) with a vector α ∈ R w (see more details about rescaled networks in Section 4). Using the above definitions, it is easy to see that γ α Θ α,Ax = γ Θx, that means, the output of the extended and rescaled network is exactly the same as the original network (using the definition of A and rescaled weights). In other words, we have a network that is first extended and then rescaled while the output of the network is still the same as the original one. We use the notation risk[γ α , Θ α,A ] · · = E (x,y) [(y − γ α Θ α,Ax ) 2 ] to compute the population risk in an extended and rescaled network. We also define p · · = w + w · (d + w − 1) as the effective dimension of the extended network. Now, let start the proof by writing a second-order Taylor expansion of risk[γ * α , Θ * α,A ] (the risk in an extended and rescaled version of the target with β * α,A = vec(γ * α , Θ * α,A ) ∈ R p ) around an extended and rescaled version of a reasonable stationary β α,A = vec( γ α , Θ α,A ) ∈ R p with suitable α ∈ R w and A, A ∈ R w×w−1 (we see later how to assign suitable value for α) to get for some t ∈ (0, 1) (Bertsekas et al., 2003, Proposition 1.1.13.a), where we use the notation ∇risk[ γ α , Θ α,A ] ∈ R p and ∇ 2 risk[ γ α , Θ α,A ] ∈ R p ×p to collect the first and second order partial derivatives of risk[ γ α , Θ α,A ] with respect to the β α,A , respectively (note that we have no assumption on (γ Then, we employ the property of extended and rescaled networks that is risk , and use the shorthand notation To do so, we use 1. our Lemma 6 (for an extended and rescaled network), 2. the property of extended and rescaled networks, 3. linearity of expectations, 4. our assumption onx that makes the first expectation zero, 5. some rewriting, 6. linearity of expectations, 7. our assumption onx (let recall thatx = (x ,x ) ∈ R d+w−1 withx ∼ N (0, I w−1×w−1 ) that are also independent of x) that makes the second expectation zero, and 8. some rewriting to obtain that Then, we 1. imply our result above for all j ∈ {1, . . . , w}, 2. use the definition of rescaled parameters and linearity of expectations to cancel α's, and 3. use our results in Lemma 6 to obtain Implying a similar argument as above for all partial derivatives, we conclude that Rearranging the display above we obtain

Now, let recall the definition of stationary points in (3) that implies
We 1. rearrange above inequality and expand the bracket, 2. use Hölder's inequality and the fact thatz β = || β|| 1 (recall thatz ∈ ∂|| β|| 1 ), and 3. use ||z|| ∞ ≤ 1 to obtain Display above reveals the positiveness of the terms in its left hand side and so we can obtain Now, let use our display earlier (obtained by Taylor expansion) rewriting the left hand side of the display above as By some rearranging on the display above we obtain For the right hand side of the inequality above we 1. get an absolute value of the third term, 2. add a zero-valued factor, 3. use triangle inequality, and 4. use our results in Lemma 4 to obtain with probability at least 1 − 1/2n. The third and fifth terms in the last inequality above can be canceled if we choose the tuning parameter large enough. Hence, we obtain The rest of the proof is analysing the behavior of m.
Now, we are motivated to employ our results in Proposition 3. To do so, we need to make sure about invertibility of matrix ( . Using the definition of the extended networks, it is easy to see that Θ A and Θ * A have full row rank. Then, using Lemma 9, we obtain that the line segment between two matrices Θ A and Θ * A is not invertible at most in finitely many t. It means, if we shift t by a tiny value ς ≈ 0 then, we can make sure that in the new point t = t − ς the corresponding matrix is invertible, that is, where the second equation is reached by assuming ς is very close to zero and so we can ignore the remaining terms. Then, we have ( Θ A +t (Θ * A − Θ A ))( Θ A +t (Θ * A − Θ A )) as an invertible matrix. Implying Proposition 3 (with a = (β * α,A − β α,A )/||β * α,A − β α,A || 2 and d + w − 1 and p as the dimension of the input and the effective dimension, respectively) we obtain that m ∈ [0, ∞) for appropriate α, that is, α with large enough c). The observation that m ∈ [0, ∞) together with the definition of m implies that m ∈ [0, ∞) as well.
Tabulating this observation to the display earlier together with our assumption on β * (||β * || 1 = ||γ * || 1 + |||Θ * ||| 1 ≤ 2 √ log n) and the fact that 1/2n ≤ 4 √ log n, we obtain for all r ≥ r orc that Second claim is a trivial consequence of the first claim by 1. using r = r orc and 2. absorbing the constant 5 in ν and simplifying to obtain with probability at least 1 − 1/2n, which completes the proof.

Proof of Proposition 3
Proof The proof is based on basic algebra and property of scaling weights across the layers in neural networks.
Let consider all the network parameters as a vector of length p (recall that p = w + w · d). Then, we can tabulate the second order partial derivatives of risk[γ, Θ] in a matrix called ∇ 2 risk[γ, Θ] ∈ R p×p (for notational simplicity, we focus on ∇ 2 risk[γ, Θ] for the moment and then we move to ∇ 2 risk[γ α , Θ α ] at the end of the proof) of the form for j, j ∈ {1, . . . , w} and k, k ∈ {1, . . . , d}.
Note that C = B (see Lemma 6), so, we are left to analyze the behavior of a ∇ 2 risk[γ, Θ]a = (a 1 ) Aa 1 + 2(a 2 ) Ca 1 + (a 2 ) Da 2 for all a ∈ R p with ||a|| 2 = 1. We do the proof in steps: We start by going through the three terms in the right hand side of display above separately, to write them in a mathematically nice formulation (Steps 1:3). In Step 4, we sum up over the results calculated in Steps 1:3. Finally in Step 5, we use our result in Steps 1:4 to prove the main claims of the proposition.
Step 1: We show that for a 1 ∈ R w·d and A ∈ R (w·d)×(w·d) , where we denote (a 1 ) k := (a 1 ) k , (a 1 ) d+k , . . . , (a 1 ) (w−1)d+k ∈ R w (as a sub-vector of a 1 ) for each k ∈ {1, . . . , d}. We start by writing matrix product in the form of sums and fill the entries of matrix A with the corresponding values from the definition to get By Lemma 6 we have which using our assumption on x (identity covariance matrix) implies ∂ 2 ∂θ j k ∂θ jk risk[γ, Θ] = 2γ j γ j for k = k and zero otherwise (for k = k ). We use 1. our display earlier, 2. the result above, 3. the linearity of sums, 4. some rewriting (using multinomial theorem), and 5.implying our notation (a 1 ) k for writing the sum in the form of product to obtain Step 2: We prove that for a 2 ∈ R w and D ∈ R w×w , (a 2 ) Da 2 = 2 d k=1 (Θ .,k ) a 2 2 , where Θ .,k denotes the k-th column of Θ. For each j, j ∈ {1, . . . , w}, we use 1. the result of Lemma 6, 2. the definition of covariance, 3. the fact that Cov(Θx) = ΘCov(x)Θ , 4. the assumption on x (identity covariance), and 5. rewriting to obtain We use 1. the definition of sub-matrix D to write the matrix product in the form of a sum, 2. tabulating above result and using the linearity of sums, 3. some rewriting (using the multinomial theorem), and 4. writing the sum in the form of product to obtain Step 3: We show that for a 2 ∈ R w , a 1 ∈ R w·d , and C ∈ R w×(w·d) , Expanding (a 2 ) Ca 1 yields Now, we need to consider two different cases: Case 1: (j = j ) We use 1. the result of Lemma 6, 2. writing matrix product in the form of a sum, 3. linearity of sums and expectations, and 4. our assumption on x to get for each j, j ∈ {1, . . . , w} and k ∈ {1, . . . , d} with j = j that Case 2: (j = j ) We use 1. the result of Lemma 6, 2. linearity of expectations, 3. linearity of expectations and our assumption on x (same argument as above), 4. linearity of expectations, 5. linearity of expectations and our assumption on x, 6. adding a zero-valued term, and 7. again linearity of expectations, our assumption on x, and some rearranging to obtain Now, we 1. use our earlier expansion, 2. separate the innermost sum in two cases, 3. use the result above (Case 1 and Case 2), 4. do some rearranging, 5. use linearity of sums and some rewriting, and 6. write sums in the form of vector product and rearranging to obtain Step 4: We prove that for any a = [(a 1 ) , (a 2 ) ] ∈ R p and (γ, Θ) ∈ B, it holds that We use 1. the block-wise structure of the Hessian matrix and some rearranging, 2. our results in Steps 1:3, and 3. multinomial theorem to obtain a ∇ 2 risk[γ, Θ]a = (a 1 ) Aa 1 + (a 2 ) Da 2 + 2(a 2 ) Ca 1 Step 5: Now, we employ our result in Steps 1:4 to prove the main claims of the proposition. Claim 1: (a 1 = 0 and a 2 = 0) We use 1. the block-wise structure of the Hessian, 2. the assumption that a 2 = 0, 3. our result in Step 1, and 4. the fact that sum of non-negative terms is also non-negative to obtain a ∇ 2 risk[γ, Θ]a = (a 1 ) Aa 1 + 2(a 2 ) Ca 1 + (a 2 ) Da 2 Above display can also reveal that for all α ∈ R w \{0} (moving to a scaled version of the parameters) Claim 2: (a 1 = 0 and a 2 = 0) The proof is similar with Claim 1 and so we omit the proof. Claim 3: (a 1 = 0 and a 2 = 0) We use our results in Step 4 together with getting an absolute value of the two last terms to obtain First let us concentrate on the second term of display above and 1. use the triangle inequality and properties of absolute values, 2. use Hölder inequality, 3. get a factor ||a 2 || 2 out of the summation, 4. use Cauchy-Schwarz inequality, and 5. some rewriting to obtain Then, we use 1. our assumption that y = γ * Θ * x + u, 2. independence of u and x, and 3. our assumption that E[x] = 0 (also we have E[u] = 0) to obtain Tabulating two observations above in the previous display we obtain Now, let define for each k ∈ {1, . . . , d} that A k · · = (Θ .,k ) a 2 , B k · · = γ (a 1 ) k , and using the fact Now, we analyze the first two terms in the right hand side of the last inequality above. We use 1. the definition of A k , 2. some rewritings, 3. the linearity of sums, 4. the definition of matrix product, 5. property of eigenvalues (e min [ΘΘ ] denotes the smallest eigenvalue of ΘΘ ), and 6. the norm definition to obtain Also, using 1. the definition of B k , 2. the Cauchy-Schwarz inequality, 3. the linearity of sums, and 4. the definition of norms we obtain Collecting two displays above together with the earlier one we obtain a ∇ 2 risk[γ, Θ]a ≥ e min ΘΘ ||a 2 || 2 2 − 2 γ 2 2 a 1 2 2 − 4 a 1 2 a 2 2 γ Θ − γ * Θ * 2 .
Now, it is time to concentrate on the Hessian behavior of ∇ 2 risk[γ α , Θ α ] (and not ∇ 2 risk[γ, Θ]). We use the known fact in neural networks that weights can be rescaled across the layers once activations are nonnegative-homogeneous. It says for a neural network parameterized by (γ, Θ), there is another network with the same objective value such that the covariates of γ are multiplied by the covariates of α and the covariates in each column of Θ are divided by the covariates of α. We use this fact with α j = 1/c for all j ∈ {1, . . . , w}, which c ∈ (1, ∞), together with the above result to analyse the behavior of Hessian in (γ α , Θ α ) and get where for the last line we use factorizing and the definition of scaled parameters. Using above display, we can guarantee positive semidefinite Hessian once c is selected large enough because, the first term can dominate the other two terms. So, we use c ∈ [1, ∞) and our assumption on ΘΘ to obtain that for c 2 ≥ 2 γ 2 2 a 1 2 2 + 4 a 1 2 a 2 2 γ Θ − γ * Θ * 2 e min ΘΘ ||a 2 || 2 2 , we can guarantee positive semidifinite Hessian, as desired.
Then, we use the fact that d ≤ p and simplifying display above to obtain We finally absorb all the constants (180/ √ κ) in ν and use the definition of r orc to complete the proof.

Proof of Lemma 5
Proof The proof consists of basic algebra.
Claim 1: We use 1. the definition of risk X [γ, Θ], 2. the chain rule, and 3. taking the derivatives to obtain as desired. Claim 2: We use 1. the definition of risk X [γ, Θ], 2. the chain rule, and 3. taking the derivatives to obtain as desired. Claim 3: We 1. use Claim 1, and 2. remove the term with zero derivative and use the chain rule to obtain as desired.
Claim 4: We 1. use Claim 2, 2. remove the term with zero derivative, and 3. take the derivative of the bracket, and 4. do some rearranging to obtain ∂γ j ∂θ jk risk X [γ, Θ] can be obtained using the same arguments.
We consider two cases: Case 1: if j = j, we use 1. Claim 1, 2. the chain rule, and 3. taking the derivatives and simplifying to obtain Case 2: if j = j, we use 1. Claim 1, 2. the chain rule, and 3. taking the derivatives an rearranging to obtain as desired.

Proof of Lemma 6
Proof The proof for this lemma follows the same steps as in Lemma 5, just sums are replaced by expectations and so we omit the proof.
6.2.9 Proof of Lemma 9 Proof The proof follows just basic linear algebra.
Since H(t) is invertible exactly when (A + tC) have full (column) rank, we are left to study the rank of (A + tC) = A + tC . To do so, we employ the Singular Value Decomposition (SVD) of A T ∈ R d ×w , that is, A = U DV with U ∈ R d ×w , V ∈ R w ×w , and D ∈ R w ×w that U, V are semi-orthogonal matrices and D has the same rank as A, in this case full rank. Now, we are motivated to make a squared matrix as where we used the SVD form of matrix A, orthogonal property of U, V , and some rewriting. Since matrices U and V have rank w, for studying the rank of A + tC it is enough to study determinant of U (A +tC )V . We then use our display above, properties of determinants for squared matrices, and characteristic polynomial to obtain det U (A + tC V ) = det tD(t −1 I w + D −1 U C V ) = det(tD) det t −1 I w + D −1 U C V = t w det(D)p Z · · =D −1 U C V (−t −1 ) .
Since, det(D) = 0 and t = 0, then the t which H(t) is singular are the roots of p Z (−t −1 ), where Z = D −1 U C V . Since the roots of p Z are the eigenvalues of Z, we have found that the only t for which H(t) fails to be invertible are the negative reciprocals of the (nonzero) eigenvalues of Z. Since, any w × w matrix has at most w distinct eigenvalues, there are just finitely many t such that H(t) is not invertible, as desired.

Discussion
This paper establishes statistical guarantees for approximate stationary points of regularized neural networks. Despite being limited to linear networks, the theory is a considerable step forward in three ways: First, previous empirical studies show that the optimization theory of linear-neural networks may exhibit some properties of non-linear models as well (Saxe et al., 2013), which means that our theories should also give some insights into non-linear networks (see also our Section 3). Second, several papers consider the existence or non-existence of spurious local minima, but importantly, our theory also applies to saddle points, which can be also hard to escape from in optimization. And third, our new statistical approach inspired by high-dimensional statistics will hopefully spark further progress in the mathematical understanding of deep learning.