Statistical guarantees for sparse deep learning

Lederer, Johannes Article — Published Version Statistical guarantees for sparse deep learning AStA Advances in Statistical Analysis Provided in Cooperation with: Springer Nature Suggested Citation: Lederer, Johannes (2023) : Statistical guarantees for sparse deep learning, AStA Advances in Statistical Analysis, ISSN 1863-818X, Springer, Berlin, Heidelberg, Vol. 108, Iss. 2, pp. 231-258, https://doi.org/10.1007/s10182-022-00467-3 This Version is available at: https://hdl.handle.net/10419/318001 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) AStA Advances in Statistical Analysis (2024) 108:231–258 https://doi.org/10.1007/s10182-022-00467-3 1 3 ORIGINAL PAPER Statistical guarantees forsparse deep learning JohannesLederer1 Received: 21 April 2022 / Accepted: 17 December 2022 / Published online: 24 January 2023 © The Author(s) 2023 Abstract Neural networks are becoming increasingly popular in applications, but our mathematical understanding of their potential and limitations is still limited. In this paper, we further this understanding by developing statistical guarantees for sparse deep learning. In contrast to previous work, we consider different types of sparsity, such as few active connections, few active nodes, and other norm-based types of sparsity. Moreover, our theories cover important aspects that previous theories have neglected, such as multiple outputs, regularization, and 𝓁2 -loss. The guarantees have a mild dependence on network widths and depths, which means that they support the application of sparse but wide and deep networks from a statistical perspective. Some of the concepts and tools that we use in our derivations are uncommon in deep learning and, hence, might be of additional interest. Keywords Sparsity· Regularization· Oracle inequalities· High-dimensionality 1 Introduction Sparsity reduces network complexities and, consequently, lowers the demands on memory and computation, reduces overfitting, and improves interpretability(Changpinyo etal. 2017; Han etal. 2016; Kim etal. 2016; Liu etal. 2015; Wen etal. 2016). Sparsity is at the heart of many current techniques in deep learning, such as dropouts(Srivastava etal. 2014), lottery tickets(Frankle and Carbin 2019), augmenting small networks(Ash 1989; Bello 1992), pruning large networks(Simonyan and Zisserman 2015; Han etal. 2016), sparsity constraints(Ledent etal. 2019; Neyshabur etal. 2015; Schmidt-Hieber 2020), and sparsity regularization(Taheri etal. 2021). The many empirical observations of the benefits of sparsity have sparked interest in mathematical support in the form of statistical theories. Two current approaches are based on Rademacher complexities (Bartlett and Mendelson 2002; Neyshabur et al. 2015) and ideas from nonparametric statistics (Schmidt-Hieber 2020), * Johannes Lederer [email protected] 1 Department ofMathematics, Ruhr-University Bochum, Bochum, Germany 232 J.Lederer 1 3 respectively. While their results provide important support for sparse deep learning, they still have major limitations: The first approach is restricted to bounded loss functions (which excludes the 𝓁2 -loss, for example), is either restricted to a simple form of sparsity (which we will call “connection sparsity” later) or suffers from an exponential dependence on the number of layers (which contradicts the current interest in very deep networks), caters to constraints rather than regularization (which is the predominant implementation in practice), and is limited to a single output node and ReLU activation. The second approach is restricted to 𝓁0 -constraints (which are infeasible in practice), assumes bounded weights, and is also limited to a single output node and ReLU activation. In short, while some progress in the statistical understanding of sparse deep learning has been made already, many aspects have not yet been considered. The goal of this paper is to establish a statistical theory that accounts for these missing aspects. For this, we follow a third, very recent approach introduced in Taheri etal. (2021). This approach is based on ideas from high-dimensional statistics and empirical-process theory(Lederer 2022). The main feature of their results is that they apply to 𝓁2 -loss, regularization instead of constraints, and a variety of activation functions. But they still miss some aspects, such as the inclusion of more complex notions of sparsity (we will speak of “node sparsity” later) and the restriction to a single output node. Moreover, their estimator involves an additional, arguably unnatural parameter. In this paper, we remove these limitations fromTaheri etal. (2021). We focus on regression-type settings with layered, feedforward neural networks. The estimators under consideration consist of a standard least-squares estimator with regularizers that induce different types of sparsity—without the need for an additional parameter. We then derive prediction and generalization guarantees by using techniques from high-dimensional statistics(Dalalyan etal. 2017) and empirical-process theory(vande Geer 2000). In the case of sub-Gaussian noise, we find the rates for the connection-sparse and node-sparse estimators (see the following section for the notions of sparsity), respectively, where l is the number of hidden layers, m the number of output nodes, n the number of samples, p the total number of parameters, and p the maximal width of the network. The rates suggest that sparsity-inducing approaches can provide accurate prediction even in very wide (with connection sparsity) and very deep (with either type of sparsity) networks while, at the same time, ensuring low network complexities. These findings underpin the current trend toward sparse but wide and especially deep networks from a statistical perspective. More generally speaking, our paper complements the existing statistical theories for sparse deep learning with new results, and it refines the techniques that were introduced in(Taheri etal. 2021). Outline of the paper Section2 recapitulates the notions of connection and node sparsity and introduces the corresponding deep learning framework and estimators. √ l ( log[mnp] ) 3 n and √ mlp(log[mnp] ) 3 n 233 1 3 Statistical guarantees forsparse deep learning Section 3 confirms the empirically observed accuracies of connection- and nodesparse estimation in theory. Section4 discusses connections of our theoretical results and weight initialization. Section5 summarizes the key features and limitations of our work. The Appendix contains all proofs. 2 Connection‑ andnode‑sparse deep learning We consider data ( y 1 ,x 1 ),…,(y n ,x n )∈ℝ m ×ℝ d that are related via for an unknown data-generating function g∗∶ ℝ d →ℝ m and unknown, random noise u1,…,un∈ℝm . We allow all aspects, namely yi , g∗ , xi , and ui , to be unbounded. Our goal is to model the data-generating function with a feedforward neural network of the form indexed by the parameter space M∶= { 𝚯 = (Θ l ,…,Θ 0 )∶Θ j ∈ ℝp j+1 ×p j} . The functions fj∶ ℝp j →ℝp j are called the activation functions (Lederer 2021), and p0∶= d and pl+1∶= m are called the input and output dimensions, respectively. The depth of the network is l , the maximal width is p∶= maxj∈{0,…,l−1}p j+1 , and the total number of parameters is p∶= ∑l j=0 pj+1p j . In practice, the total number of parameters often rivals or exceeds the number of samples: p≈n or p≫n . We then speak of high dimensionality. A common technique for avoiding overfitting in high-dimensional settings is regularization that induces additional structures, such as sparsity. Sparsity has the interesting side-effect of reducing the networks’ complexities, which can facilitate interpretations and reduce demands on energy and memory. Three common notions of sparsity are connection sparsity, which means that there is only a small number of nonzero connections between nodes, node sparsity, which means that there is only a small number of active nodes(Alvarez and Salzmann 2016; Changpinyo etal. 2017; Feng and Simon 2017; Kim etal. 2016; Lee etal. 2008; Liu etal. 2015; Nie etal. 2015; Scardapane etal. 2017; Wen etal. 2016), and layer sparsity, which means that there is only a small number of active layers(Hebiri and Lederer 2020). In the following, we focus on connection- and node sparsity. Our first sparse estimator is for a tuning parameter rcon ∈[0, ∞) , a nonempty set of parameters and the 𝓁1 -norm (1) yi=g∗[xi]+uifor i∈{1, …,n} (2) g 𝚯[x] ∶= Θlf l[ Θl−1 ⋯f 1 [Θ0x] ] for x∈ℝ d (3)  𝚯 con ∈ arg min 𝚯∈M1 {n ∑ i=1|||| yi−g𝚯[xi] |||| 2 2+rcon ||| Θl ||| 1 } M 1⊂ { 𝚯∈M∶max j∈{0,…,l−1}||| Θj ||| 1≤1 }, 234 J.Lederer 1 3 This estimator is an analog of the lasso estimator in linear regression(Tibshirani 1996). It induces sparsity on the level of connections: the larger the tuning parameter rcon , the fewer connections among the nodes. Deep learning with 𝓁1 -regularization has become common in theory and practice(Kim etal. 2016; Taheri etal. 2021). Our estimator(3) specifies one way to formulate this type of regularization. The estimator is indeed a regularized estimator (rather than a constraint estimator), because the complexity is regulated entirely through the tuning parameter rcon in the objective function (rather than through a tuning parameter in the set over which the objective function is optimized). But 𝓁1 -regularization could also be formulated slightly differently. For example, one could consider the estimators or The differences among the estimators(3)–(5) are small: for example, our theory can be adjusted for(4) with almost no changes of the derivations. The differences among the estimators mainly concern the normalizations of the parameters; we illustrate this in the following proposition. Proposition 1 (Scaling of Norms) Assume that the all-zeros parameter (𝟎p l+1 ×p l ,…,𝟎p 1 ×p 0 )∈M1 is neither a solution of(3) nor of(5), that rcon >0 , and that the activation functions are nonnegative homogenous: fj[ab]=afj[b] for all j∈{1, …,l} , a∈[0, ∞) , and b∈ ℝp j . Then, ||| (  Θcon) 0 ||| 1,…,||| (  Θcon) l−1 ||| 1=1 (concerns the inner layers) for all solutions of(3), while ||| (  Θcon) 0 ||| 1= ⋯ =||| (  Θcon) l ||| 1 (concerns all layers) for at least one solution of(5). In brief, the goal of our paper is not to promote a new way of implementing sparsity in practice but to reproduce practical implementations as accurately as possible in theory. Another way to formulate 𝓁1 -regularization was proposed in Taheri etal. (2021): they reparametrize the networks through a scale parameter and a constraint version of M and then to focus the regularization on the scale parameter only. Our abovestated estimator(3) is more elegant in that it avoids the reparametrization and the additional parameter. The factor ||| Θl||| 1 in the regularization term of(3) measures the complexity of the network over the set M1 , and the factor rcon regulates the complexity of the resulting ||| Θj ||| 1∶= p j+1 ∑ i=1 p j ∑ k=1| (Θj)ik | for j∈{0, …,l},Θj∈ℝpj+1×pj . (4) 𝚯 con ∈ arg min 𝚯∈M {n ∑ i=1|||| yi−g𝚯[xi] |||| 2 2+rcon l ∏ j=0||| Θj ||| 1 } (5)  𝚯 con ∈ arg min 𝚯∈M {n ∑ i=1|||| yi−g𝚯[xi] |||| 2 2+rcon l ∑ j=0||| Θj ||| 1 }. 235 1 3 Statistical guarantees forsparse deep learning estimator. This provides a convenient lever for data-adaptive complexity regularization through well-established calibration schemes for the tuning parameter, such as cross-validation. This practical aspect is an advantage of regularized formulations like ours as compared to constraint estimation over sets with a predefined complexity. The constraints in the set M1 of the estimator (3) can also retain the expressiveness of the full parameterization that corresponds to the set M : for example, assuming again nonnegative-homogeneous activation, one can check that for every 𝚪∈M , there is a 𝚪� ∈{𝚯∈M∶max j∈{0,…,l−1}||| Θ j||| 1 ≤1 } such that g𝚪=g𝚪� —cf.(Taheri etal. 2021, Proposition 1). In contrast, existing theories on neural networks often require the parameter space to be bounded, which limits the expressiveness of the networks. Our regularization approach is, therefore, closer to practical setups than constraint approaches. The price is that to develop prediction theories, we have to use different tools than those typically used in theoretical deep learning. For example, we cannot use established risk bounds such as(Bartlett and Mendelson 2002,Theorem8) (because Rademacher complexities over classes of unbounded functions are unbounded) or(Lederer 2020a,Theorem1) (because our loss function is not Lipschitz continuous) or established concentration bounds such as McDiarmid’s inequality in(McDiarmid 1989,Lemma(3.3)) (because that would require a bounded loss). We instead invoke ideas from high-dimensional statistics, prove Lipschitz properties for neural networks, and use empirical-process theory, specifically concentration inequalities that are based on chaining (see the Appendix). Our second estimator is for a tuning parameter rnode ∈[0, ∞) , a nonempty set of parameters and the 𝓁2∕𝓁1 -norm This estimator is an analog of the group-lasso estimator in linear regression(Bakin 1999). Again, to avoid ambiguities in the regularization, our formulation is slightly different from the standard formulations in the literature, but the fact that grouplasso regularizers leads to node-sparse networks has been discussed extensively before (Alvarez and Salzmann 2016; Liu etal. 2015; Scardapane etal. 2017): the larger the tuning parameter rnode , the fewer active nodes in the network. (6)  𝚯 node ∈ arg min 𝚯∈M2,1 {n ∑ i=1|||| yi−g𝚯[xi] |||| 2 2+rnode ||| Θl ||| 2,1 } M 2,1 ⊂ { 𝚯∈M∶max j∈{0,…,l−1}||| Θj ||| 2,1 ≤1 }, ||| Θj ||| 2,1 ∶= pj ∑ k=1 √ √ √ √pj+1 ∑ i=1 | (Θj)ik | 2 for j∈{0, …,l−1},Θ j ∈ ℝpj+1×pj . 236 J.Lederer 1 3 The above-stated comments about the specific form of the connection-sparse estimator also apply to the node-sparse estimator. An illustration of connection and node sparsity is given in Fig.1. Connection-sparse networks have only a small number of active connections between nodes (left panel of Fig.1); node-sparse networks have inactive nodes, that is, completely unconnected nodes (right panel of Fig.1). The two notions of sparsity are connected: for example, connection sparsity can render entire nodes inactive “by accident” (see the layer that follows the input layer in the left panel of the figure). In general, node sparsity is the weaker assumption, because it allows for highly connected nodes; this observation is reflected in the theoretical guarantees in the following section. The optimal network architecture for given data (such as the optimal width) is hardly known beforehand in a data analysis. A main feature of sparsity-inducing regularization is, therefore, that it adjusts parts of the network architecture to the data. In other words, sparsity-inducing regularization is a data-driven approach to adapting the complexity of the network. While versions of the estimators(3) and(6) are popular in deep learning, statistical analyses, especially of node-sparse deep learning, are scarce. Such a statistical analysis is, therefore, the goal of the following section. 3 Statistical prediction guarantees We now develop statistical guarantees for the sparse estimators described above. The guarantees are formulated in terms of the squared average (in-sample) prediction error which is a measure for how well the network g𝚯 fits the unknown function g∗ (which does not need to be a neural network) on the data at hand, and in terms of the prediction risk (or generalization error) for a new sample (y,x) that has the same distribution as the original data which measures how well the network g𝚯 can predict a new sample. We first study the prediction error, because it is agnostic to the distribution of the input data; in the end, we then translate the bounds for the prediction error into bounds for the generalization error. err [𝚯] ∶= 1 n n ∑ i=1| || | g∗[xi]−g𝚯[xi] | || | 2 2for 𝚯∈M , risk [𝚯] ∶= E y,x|| y−g𝚯[x] || 2 2 for 𝚯∈M , Fig. 1 exemplary networks produced by the connection-sparse estimator(3) and the node-sparse estimator(6) 237 1 3 Statistical guarantees forsparse deep learning We first observe that the networks in(2) can be somewhat “linearized:” For every parameter 𝚯∈M1 , there is a parameter such that for every x∈ℝd This additional notation allows us to disentangle the outermost layer (which is regularized directly) from the other layers (which are regularized indirectly). More generally speaking, the additional notation makes a connection to linear regression, where the above holds trivially with g𝚯[x]=x . We also define accordingly. In high-dimensional linear regression, the quantity central to prediction guarantees is the effective noise(Lederer and Vogt 2020). The effective noise is in our notation (with l=0 and m=1 to describe linear regression) 2�� ∑n i=1 u i x i��∞ . The above linearization allows us to generalize the effective noise to our general deep learning framework: where ||| A||| ∞ ∶= max (i,j)∈{1, …,m}×{1, …,p l }|A ij | for A∈ℝ m × p l . The effective noises, as we will see below, are the optimal tuning parameters in our theories; at the same time, the effective noises depend on the noise random variables u1,…,un , which are unknown in practice. Accordingly, we call the quantities r∗ con and r∗ node the oracle tuning parameters. We take a moment to compare the effective noises in(8) to Rademacher complexities (Koltchinskii 2001; Koltchinskii and Panchenko 2002). Rademacher complexities are the basis of a line of other statistical theories for deep learning (Bartlett and Mendelson 2002; Golowich et al. 2018; Lederer 2020a; Neyshabur etal. 2015). In our framework, the Rademacher complexities in the case m=1 are (Lederer 2020a,Definition1)  Θ∈ M∶= {  Θ=(  Θl−1,…,  Θ0)∶  Θj∈Rp j+1 ×p j , max j∈{0,…,l−1}|||  Θj ||| 1≤1 } (7) g 𝚯[x]=Θ l g𝚯[x] with g 𝚯 [x] ∶= fl [ Θl−1 ⋯f1[Θ 0 x] ] ∈ℝpl .  M 2,1 ∶= {Θ=(Θ l−1 ,…,Θ 0 )∶Θ j ∈Rpj+1×pj, max j∈{0,…,l−1}||| Θ j||| 2,1 ≤1 } (8) r ∗ con ∶= 2 sup Ψ∈  M1��� n � i=1 ui(gΨ[xi])⊤���∞ r ∗ node ∶= 2 √ msup Ψ∈  M 2,1 ��� n � i=1 ui(gΨ[xi])⊤ ��� ∞ , 238 J.Lederer 1 3 for i.i.d.Rademacher random variables k1,…,kn . The effective noises might look like (rescaled) empirical versions of these quantities at first sight, but this is not the case. Two immediate differences are that(8) apply to general m and circumvent the outermost layers of the networks. But more importantly, Rademacher complexities involve external i.i.d. Rademacher random variables that are not connected with the statistical model at hand, while the effective noises involve the noise variables, which are completely specified by the model and, therefore, can have any distribution (see our sub-Gaussian example further below). Hence, there are no general techniques to relate Rademacher complexities and effective noises. Not only are the two concepts distinct, but also they are used in very different ways. For example, existing theories use Rademacher complexities to measure the size of the function class at hand, while we use effective noises to measure the maximal impact of the stochastic noise on the estimators. (Our proofs also require a measure of the size of the function class, but this measure is entropy— cf.Lemma1.) In general, our proof techniques are very different from those in the context of Rademacher complexities. We can now state a general prediction guarantee. Theorem1 (General Prediction Guarantees) If rcon ≥r∗ con , it holds that Similarly, if rnode ≥r∗ node , it holds that Each bound contains an approximation error err[𝚯] that captures how well the class of networks can approximate the true data-generating function g∗ and a statistical error proportional to rcon ∕n and rnode∕n , respectively, that captures how well the estimator can select within the class of networks at hand. In other words, Theorem1 ensures that the estimators(3) and(6) predict—up to the statistical error described by rcon ∕n and rnode∕n , respectively—as well as the best connection- and node-sparse network. This observation can be illustrated further: Corollary 1 (Parametric Setting) If additionally g∗=g𝚯∗ for a 𝚯∗∈M1 , it holds that E x1,…,xn,k1,…,kn [ sup 𝚯∈M1||| 1 n n ∑ i=1 kig𝚯[xi]||| ] and Ex1,…,xn,k1,…,kn[sup 𝚯∈M 2,1||| 1 n n ∑ i=1 kig𝚯[xi] |||] err [  𝚯con]≤inf 𝚯∈M 1{ err[𝚯]+ 2r con n||| Θl ||| 1 }. err [  𝚯node]≤inf 𝚯∈M 2,1{ err[𝚯]+ 2r node n||| Θl ||| 2,1 }. 245 1 3 Statistical guarantees forsparse deep learning other hand, our techniques do not seem appropriate for “hard-coded” types of sparsity, such as 2:4 (“two-to-four”) sparsity (Mishra etal. 2021). Connection sparsity limits the number of nonzero entries in each parameter matrix, while node sparsity only limits the total number of nonzero rows. Hence, the number of columns in a parameter matrix, that is, the width of the preceding layer, is regularized only in the case of connection sparsity. Our theoretical results reflect this insight in that the bounds for the connection- and node-sparse estimators depend on the networks’ width logarithmically and sublinearly, respectively. Practically speaking, our results indicate that connection sparsity is suitable to handle wide networks, but node sparsity is suitable for wide networks only when complemented by connection sparsity or other strategies. The mild logarithmic dependence of our connection-sparse bounds on the number of output nodes illustrates that networks with many outputs can be learned in practice. Our prediction theory is the first one to consider multiple output nodes; a classification theory with a logarithmic dependence on the output nodes has been established very recently inLedent etal. (2019). The mathematical underpinnings of our theory are very different from those of most other papers in theoretical deep learning. The proof of the main theorem shares similarities with proofs in high-dimensional statistics, such as the concept of the effective noise (Lederer 2022). The treatments of the relevant empirical-processes use metric entropy, chaining, and Lipschitz properties of neural networks. These concepts and tools are not standard in deep learning and, therefore, might be of more general interest (see again Appendix1 for further ideas). Our theory has three limitations: First, the bounds apply only to global optima of the optimization landscapes rather than local optima or other points in which certain algorithms might be trapped. However, there is evidence that global optimization can be feasible at least in wide and deep networks (Lederer 2020b). Second, the theory does not entail a practical scheme for the calibration of the tuning parameters. However, the inclusion of regularization (rather than constraints) is already a step forward, because it reveals how the tuning parameters should scale with the problem dimensions (see our Proposition2). Third, the network architecture is limited to fully connected feedforward layers, which excludes some aspects of modern pipelines (such as convolutions, dropout, and so forth). In any case, all three limitations are open problems in the literature; in particular, the mentioned limitations are shared by most theories on the topic. We can summarize what this paper contributes—and what it does not—as follows: From a practical perspective, it is well established that sparsity can benefit deep learning, and there are several methods to generate sparsity in practice. Thus, this paper does not provide new practical insights or methods. Instead, our paper (i)backs up these practical observations with statistical theories that are more general and closer to practice than previous theories, and it (ii)establishes refined concepts and techniques for the statistical analysis of deep learning more generally. 246 J.Lederer 1 3 Appendix The Appendix consists of two auxiliary results and the proofs of Theorem1 and Propositions1 and2. Our approach combines techniques from high-dimensional statistics and empirical-process theory that are very different from the techniques used in most other approaches in the literature. A Lipschitz property In this section, we prove a Lipschitz property that we use in the proof of Proposition2. Proposition 4 (Lipschitz Property) In the framework of Sections2 and3, it holds for all 𝚯 ,𝚪∈M 1 that and for all 𝚯 ,𝚪∈M 2,1 that The Frobenius norm is defined as Proposition4 generalizes (Taheri etal. 2021,Proposition2) to vector-valued network outputs and to node sparsity, and it replaces their || x|| 2 with the smaller || x|| ∞ in the connection-sparse case. Proof of Proposition4 This proof generalizes and sharpens the proof of Taheri etal. (2021), and it simplifies some arguments of that proof. We define the “inner subnetworks” of a network g𝚯 with 𝚯 ∈M 2,1 as the vector-valued functions and � �� � g 𝚯 [x]−g 𝚪 [x] � �� �∞ ≤ √ l �� x ��∞��� 𝚯−𝚪 ���F � �� � g 𝚯 [x]−g 𝚪 [x] � �� �2 ≤ √ l �� x �� 2 ��� 𝚯−𝚪 ��� F . ||| 𝚯 ||| F∶= √ √ √ √ l−1 ∑ j=0 ||| Θj ||| 2 F∶= √ √ √ √ √ l−1 ∑ j=0 pj+1 ∑ i=1 pj ∑ k=1 | (Θj)ik | 2for 𝚯∈M2,1 =M1∪M2,1 . S 0g𝚯∶ℝd→ℝp 1 x↦S 0 g 𝚯 [x] ∶= Θ 0 x S jg𝚯∶ℝd→ℝp j+1 x↦S j g 𝚯 [x] ∶= Θjfj [ ⋯f1[Θ 0 x] ] 247 1 3 Statistical guarantees forsparse deep learning for j∈{1, …,l−1} . Similarly, we define the “outer subnetworks” of g𝚯 as the real-valued functions for j∈{1, …,l−1} and The initial network can be split into an inner and an outer network along every layer j∈{1, …,l} : We call this our splitting argument. To exploit the splitting argument, we derive a contraction result for the inner subnetworks and a Lipschitz result for the outer subnetworks. We denote the 𝓁2 -operator norm of a matrixA, that is, the largest singular value ofA, by ||| A||| op . Using then the assumptions that the activation functions are 1-Lipschitz and f j [𝟎 p j]=𝟎 pj , we get for every 𝚯 =(Θ l−1 ,…,Θ 0 )∈M 2,1 and x∈ ℝ d that for all j∈{2, …,l} . Now, since ||| Θ k ||| op ≤ ||| Θ k ||| F ≤ ||| Θ k ||| 2,1 and 𝚯 ∈M 2,1 , we can deduce from the display that This inequality is our contraction property. By similar arguments, we get for every z1 ,z 2 ∈ℝp j that S jg𝚯∶ℝp j →ℝp l z↦Sjg 𝚯 [z] ∶= fl [ Θl−1 ⋯fj[z] ] S lg𝚯∶ℝp l →ℝp l z↦Slg 𝚯 [z] ∶= fl[z] . g 𝚯 [x]=S j g 𝚯[ S j−1 g 𝚯 [x] ] for x∈ℝ d. || ||Sj−2g𝚯[x]||||2=||||Θ j−2 fj−2 [ Sj−3g𝚯[x] ] ||||2 ≤|||Θj−2|||op||||fj−2[Sj−3g𝚯[x]]|||| 2 ≤|||Θj−2|||op||||Sj−3g𝚯[x]||||2 ≤⋯ ≤(j−2 ∏ k=1|||Θk|||op)||Θ0x||2 ≤ ( j−2 ∏ k=0||| Θk ||| op )|| x || 2 |||| Sj−2g𝚯[x] |||| 2≤ (j−2 ∏ k=0||| Θk ||| 2,1 )|| x || 2 . 248 J.Lederer 1 3 for j∈{1, …,l} , where ∏ l−1 k=l��� Θ k ���op ∶= 1 . Hence, similarly as above, This inequality is our Lipschitz property. We now use the contraction and Lipschitz properties of the subnetworks to derive a Lipschitz result for the entire network. We consider two networks g𝚯 and g𝚪 with parameters 𝚯 =(Θ l−1 ,…,Θ 0 )∈M 2,1 and 𝚪 =(Γ l−1 ,…,Γ 0 )∈M 2,1 , respectively. Our above-derived splitting argument applied with j=1 and j=l , respectively, yields Elementary algebra and the fact that S j−1g 𝚯 [S j−2 g 𝚪 [x]] = Sjg 𝚯 [Θ j−1 fj−1[S j−2 g 𝚪 [x ]] for j∈{2, …,l} then allow us to derive |||| S j g𝚯[z1]−S j g𝚯[z2] | | | |2 =||||fl[Θl−1 ⋯fj[z1]]−fl[Θl−1 ⋯fj[z2]]||||2 ≤||||Θl−1[fl−1⋯fj[z1]]−Θl−1[fl−1⋯fj[z2]]|||| 2 ≤|||Θl−1|||op||||fl−1[⋯fj[z1]]−fl−1[⋯fj[z2]]||||2 ≤⋯ ≤ ( l−1 ∏ k=j||| Θk ||| op )|| z1−z2 || 2 |||| Sjg𝚯[z1]−Sjg𝚯[z2] |||| 2≤ (l−1 ∏ k=j||| Θk ||| 2,1 )|| z1−z2 || 2 . | || | g 𝚯 [x]−g 𝚪 [x] | || |2 = | || | S 1 g 𝚯[ S 0 g 𝚯 [x] ] −S l g 𝚪[ S l−1 g 𝚪 [x] ]| || |2. 249 1 3 Statistical guarantees forsparse deep learning We bound this further by using the above-derived Lipschitz property of the outer networks and the observation that Sl g 𝚯 [S l−1 g 𝚪 [x]] = S l g 𝚪 [S l−1 g 𝚪 [x ]] : which is by the definition of the inner networks equivalent to Using the properties of the operator norm, we can deduce from this inequality that |||| g𝚯[x]−g𝚪[x] | | | |2 =||||||S1g𝚯[S0g𝚯[x]]− l ∑ j=1(Sjg𝚯[Sj−1g𝚪[x]]−Sjg𝚯[Sj−1g𝚪[x]])−Slg𝚪[Sl−1g𝚪[x]]|||||| 2 =||||||S1g𝚯[S0g𝚯[x]]−S1g𝚯[S0g𝚪[x]] − l ∑ j=2(Sjg𝚯[Sj−1g𝚪[x]]−Sj−1g𝚯[Sj−2g𝚪[x]]) +Slg𝚯[Sl−1g𝚪[x]]−Slg𝚪[Sl−1g𝚪[x]]||||||2 =||||||S1g𝚯[S0g𝚯[x]]−S1g𝚯[S0g𝚪[x]] − l ∑ j=2(Sjg𝚯[Sj−1g𝚪[x]]−Sjg𝚯[Θj−1 fj−1[Sj−2g𝚪[x]]]) +Slg𝚯[Sl−1g𝚪[x]]−Slg𝚪[Sl−1g𝚪[x]]||||||2 ≤||||S1g𝚯[S0g𝚯[x]]−S1g𝚯[S0g𝚪[x]]||||2 + l ∑ j=2| | | | Sjg𝚯[Sj−1g𝚪[x]]−Sjg𝚯[Θj−1 fj−1[Sj−2g𝚪[x]]]| | | | 2 + |||| Slg 𝚯[ S l−1 g 𝚪 [x] ] −Slg 𝚪[ S l−1 g 𝚪 [x] ]||||2 . || ||g𝚯[x]−g𝚪[x]||||2≤ (l−1 ∏ k=1|||Θk|||2,1 ) ||||S0g𝚯[x]−S0g𝚪[x]||||2 + l ∑ j=2( l−1 ∏ k=j||| Θk ||| 2,1 )|||| Sj−1g𝚪[x]−Θj−1fj−1 [ Sj−2g𝚪[x] ]|||| 2 , |||| g𝚯[x]−g𝚪[x]||||2≤ (l−1 ∏ k=1|||Θk|||2,1 ) ||Θ0x− Γ0x||2 + l ∑ j=2( l−1 ∏ k=j||| Θk ||| 2,1 )|||| Γj−1fj−1 [ Sj−2g𝚪[x] ] −Θj−1fj−1 [ Sj−2g𝚪[x] ]|||| 2 . 250 J.Lederer 1 3 Invoking the mentioned conditions on theactivation functions and the contraction property for the inner subnetworks then yields The proof for the connection-sparse case is almost the same. The main difference is that one needs to use the || ⋅|| ∞ - and ||| ⋅||| 1 -norms (rather than the || ⋅|| 2 - and ||| ⋅||| op -norms) and the inequality || Ab|| ∞≤||| A||| 1|| b|| ∞ (rather than the inequality || Ab|| 2≤||| A||| op|| b|| 2 ) to establish suitable contraction and Lipschitz properties. ◻ B Entropy bound In this section, we establish bounds for the entropies of M1 and M2,1 . The distance between two networks g𝚯 and g𝚪 is defined as dist[ g 𝚯, g 𝚪]∶ =�∑ n i=1 �� g𝚯[xi]−g𝚪[xi] �� 2 ∞∕ n . Given this distance function and a radius t∈(0, ∞) , the metric entropy of a nonempty set A ⊂ { 𝚯 =(Θl−1 , … , Θ0)∶Θj∈ ℝpj+1×pj } is denoted by H[t,A] . We then get the following entropy bounds. Lemma 1 (Entropy Bounds) In the framework of Sections2 and3, it holds for a constant cH∈(0, ∞) and every t∈(0, ∞) that and || ||g𝚯[x]−g𝚪[x]||||2≤ (l−1 ∏ k=1|||Θk|||2,1 ) |||Θ0− Γ0|||op||x||2 + l ∑ j=2( l−1 ∏ k=j||| Θk ||| 2,1 )||| Γj−1− Θj−1 ||| op |||| fj−1 [ Sj−2g𝚪[x] ]|||| 2 . ���� g𝚯[x]−g𝚪[x] � � � �2 ≤�max v∈{0,…,l−1}� k∈{0, …,l−1} k≠v max����Θk���2,1,���Γk���2,1� � � l−1 � j=0���Γj− Θj���op���x��2 ≤ √ l �� x ��2��� 𝚯−𝚪 ���F . H [t,M1]≤cH ⌈ (v∞) 2 l t 2 ⌉ log [ pt 2 (v∞) 2 l +2 ] H [t,M2,1]≤cH ⌈ (v∞) 2 lp t2 ⌉ log [ pt2 (v ∞ )2l+2 ]. 251 1 3 Statistical guarantees forsparse deep learning Proof of Lemma1 The first bound can be derived by combining established deterministic and randomization arguments (Carl 1985);(Lederer 2010, Proof of Theorem1.1);(Taheri etal. 2021,Proposition3). For the second bound, observe that for all j∈{0, …,l−1} and Θ j ∈ℝ p j+1 ×p j . We used in turn 1.the definition of the ||| ⋅||| 1 -norm on Page2, 2.the linearity and interchangeability of finite sums and the inequality �� a ��1 ≤ √ b �� a ��2 for all a∈ℝb , 3. the definition of the ||| ⋅||| 2,1 -norm on Page??, and 4.the definition of the width p on Page2. Hence, M 2,1 ⊂ √ pM 1 . A bound for the entropies of M2,1 can, therefore, be derived from the first bound by replacing the radii t on the right-hand side by t∕√p . C Proof ofTheorem1 In this section, we state a proof for Theorem 1. The proof is inspired by derivations in high-dimensional statistics—see, for example, (Zhuang and Lederer 2018; Lederer 2022) and references therein. Proof of Theorem1 The main idea of the proof is to contrast the estimators’ objective functions evaluated at their minima with the estimators’ objective functions at other points. Our first step is to derive what we call a basic inequality. By the definition of the estimator in(6), it holds for every 𝚯∈M2,1 that where we use the shorthand  𝚯 ∶=  𝚯 node . We then invoke the model in(1) to rewrite this inequality as Expanding the squared terms and rearranging the inequality then yields This is our basic inequality. ��� Θj ��� 1= pj+1 � i=1 pj � k=1� (Θj)ik � ≤ √ pj+1 pj � k=1 � � � � pj+1 � i=1� (Θj)ik � 2= √ pj+1 ��� Θj ��� 2,1 = √ p ��� Θj ���2,1 n ∑ i=1| || | yi−g 𝚯[xi] | || | 2 2+rnode |||  Θl ||| 2,1 ≤ n ∑ i=1| || | yi−g𝚯[xi] | || | 2 2+rnode ||| Θl ||| 2,1 , n ∑ i=1| || | g∗[xi]+ui−g 𝚯[xi] | || | 2 2+rnode |||  Θl ||| 2,1 ≤ n ∑ i=1| || | g∗[xi]+ui−g𝚯[xi] | || | 2 2+rnode ||| Θl ||| 2,1 . n ∑ i=1| || |g∗[xi]−g� 𝚯[xi]| || | 2 2≤ n ∑ i=1| || |g∗[xi]−g𝚯[xi]| || | 2 2 +2 n ∑ i=1 ( g� 𝚯[xi] ) ⊤ ui−2 n ∑ i=1 ( g𝚯[xi] ) ⊤ ui+rnode ||| Θl ||| 2,1 −rnode ||| � Θl ||| 2,1 . 252 J.Lederer 1 3 In the remainder of the proof, we need to bound the first two terms in the last line of the basic inequality. We call these terms the empirical-process terms. Using the reformulation of the networks in(7), we can write the empirical-process term of a general parameter 𝚪∈M2,1 according to with 𝚪 ∈M 2,1 . Using the 1.the properties of transpositions, 2.the definition of the trace function, 3.the cyclic property of the trace function, and 4.the linearity of the trace function yields further Now, 1.denoting the column-vector that corresponds to the kth column of a matrixA by A∙k , 2.using Hölder’s inequality, 3.using Hölder’s inequality again, and 4.again Hölder’s inequality and our definitions of the elementwise 𝓁∞ -and 𝓁1 -norms, we find which implies in view of the definition of the effective noise in(8) This inequality is our bound on the empirical-process terms. 2 n ∑ i=1 ( g𝚪[xi] ) ⊤ ui=2 n ∑ i=1 ( Γlg𝚪[xi] ) ⊤ u i 2 n ∑ i=1(g𝚪[xi])⊤ ui=2 n ∑ i=1(g𝚪[xi])⊤(Γl)⊤ui =2 n ∑ i=1 trace[(g𝚪[xi])⊤(Γl)⊤ui] =2 n ∑ i=1 trace[ui(g𝚪[xi])⊤(Γl)⊤] =2trace [( n ∑ i=1 ui ( g𝚪[xi] ) ⊤ ) (Γl)⊤ ]. 2 n � i=1�g𝚪[xi]�⊤ ui=2 p l � k=1 �� n � i=1 ui�g𝚪[xi]�⊤ � ∙k ,(Γl)∙k � ≤2 pl � k=1���������n � i=1 ui�g𝚪[xi]�⊤�∙k��������2����(Γl)∙k����2 ≤2 max k∈{1,…,pl}���������n � i=1 ui�g𝚪[xi]�⊤�∙k��������2 pl � k=1����(Γl)∙k���� 2 ≤2 √ m ������������ n � i=1 ui � g𝚪[xi] � ⊤ ������������ ∞ ��� Γl ��� 2,1 , 2 n ∑ i=1 ( g𝚪[xi] ) ⊤ ui≤r∗ node ||| Γl ||| 2,1 . 253 1 3 Statistical guarantees forsparse deep learning We can combine the bound on the empirical-process term and the basic inequality to find Using then the assumption rnode ≥r∗ node yields Multiplying both sides by 1∕n and taking the infimum over 𝚯∈M2,1 on the righthand side then gives Invoking the definition of the prediction error on Page3 gives the desired result. The proof for the connection-sparse estimator is virtually the same. ◻ D Proof ofProposition1 In this section, we give a short proof of Proposition1. Proof of Proposition1 Verify the fact that if the all-zeros parameter is neither a solution of(3) nor of(5), all solutions  𝚯con and  𝚯con of(3) and(5), respectively, satisfy (  Θ con )j,(  Θ con )j≠𝟎 p j+1 ×pj for all j∈{0, …,l} . It then follows from the assumed nonnegative homogeneity, rcon >0 , and the definition of the estimator in(3) that ||| (  Θcon) 0 ||| 1,…,||| (  Θcon) l−1 ||| 1=1 for all solutions  𝚯con . Given a solution  𝚯con of(5), define a∶= ||| (  Θcon) 0 ||| 1∕( l + 1 )+ ⋯ +||| (  Θcon) l ||| 1∕( l + 1 ) a∶= ||| (  Θcon) 0 ||| 1∕( l + 1 )+ ⋯ +||| (  Θcon) l ||| 1∕( l + 1 ) and verify the fact that 𝚪∈M with Γ 0 ∶= a (  Θcon) 0 ∕||| (  Θcon) 0 ||| 1 , Γ 1 ∶= a (  Θcon) 1 ∕||| (  Θcon) 1 ||| 1 , … has the same value in the objective function as  𝚯con . ◻ E Proof ofProposition2 In this section, we establish a proof of Proposition2. The key tools are the Lipschitz property of Proposition4 and the entropy bounds of Lemma1. n ∑ i=1| || |g∗[xi]−g 𝚯[xi]| || | 2 2 ≤ n ∑ i=1| || |g∗[xi]−g𝚯[xi]| || | 2 2 + r∗ node|||  Θl ||| 2,1 +r∗ node||| Θl ||| 2,1 +rnode ||| Θl ||| 2,1 −rnode |||  Θl ||| 2,1 . n ∑ i=1| || | g∗[xi]−g 𝚯[xi] | || | 2 2≤ n ∑ i=1| || | g∗[xi]−g𝚯[xi] | || | 2 2+2rnode ||| Θl ||| 2,1 . 1 n n ∑ i=1|||| g∗[xi]−g 𝚯[xi] |||| 2 2≤inf 𝚯∈M2,1 { 1 n n ∑ i=1|||| g∗[xi]−g𝚯[xi] |||| 2 2+2rnode n ||| Θl ||| 2,1 }. 254 J.Lederer 1 3 Proof of Proposition2 The main idea is to rewrite the event under consideration in a form that is amenable to known tail bounds for suprema of empirical-processes with sub-Gaussian random variables. The connection-sparse bound follows from where we use in turn 1.the definition of r∗ con in(8), 2.the union bound, 3.(vande Geer 2000,Corollary8.3) and our Proposition4 and Lemma1, and 4.the inequality pl≤p= ∑l j=0 pj+1p j and consolidating the factors. The key concept underlying (vande Geer 2000,Corollary8.3 on Page128) is chaining(vander Vaart and Wellner 1996,Page90). The same considerations also apply to the node-sparse case, but we get an additional factor √m from the definition of the effective noise in(8) and a factor √p from the entropy bound in Lemma1. The differences between the bounds for the connection- and node-sparse cases in terms of v∞ vs. v2 stem from the different Lipschitz constants in Proposition4. ◻ F Proof ofProposition3 Proof of Proposition3 The proof is based on standard empirical-process theory, including contraction and symmetrization arguments. Using basic algebra and measure theory, one can easily show that P{ r∗ con ≥cv∞ √ nl ( log[2mnp] ) 3 } =P{2 sup 𝚿∈M1|||||||||||| n ∑ i=1 ui(g𝚿[xi])⊤||||||||||||∞ ≥cv∞√nl(log[2mnp])3} ≤mplmax j∈{1, …,m} k∈{1, …,pl} P{2 sup 𝚿∈M1||||(n ∑ i=1 ui(g𝚿[xi])⊤)jk|||| ≥cv∞√nl(log[2mnp])3 } ≤mpl⋅ 1 mnp ≤1 n , risk [  𝚯con]≤(1+b)risk[𝚯∗]+cberr[  𝚯con ] +cb|||| 1 n n ∑ i=1(||||g∗[xi] −g 𝚯con [xi]|||| 2 2−E||||g∗[xi] −g 𝚯con [xi] |||| 2 2) ||||