Connection- and Node-Sparse Deep Learning: Statistical Guarantees
Authors: Johannes Lederer
Venue:  (2021)

Abstract: Neural networks are becoming increasingly popular in applications, but a comprehensive mathematical understanding of their potentials and limitations is still missing. In this paper, we study the prediction accuracies of neural networks from a statistical point of view. In particular, we establish statistical prediction guarantees for deep learning with different types of sparsity-inducing regularization. Our bounds feature a mild dependence on network widths and depths, and, therefore, support the current trend toward wide and deep networks. The tools that we use in our derivations are uncommon in deep learning and, hence, might be of additional interest.

Under review as a conference paper at ICLR 2021
CONNECTION- AND NODE-SPARSE DEEP LEARNING: STATISTICAL GUARANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Neural networks are becoming increasingly popular in applications, but a com- prehensive mathematical understanding of their potentials and limitations is still missing. In this paper, we study the prediction accuracies of neural networks from statistical point of view. In particular, we establish statistical guarantees for deep learning with different types of sparsity-inducing regularization. Our bounds feature mild dependence on network widths and depths, and, therefore, support the current trend toward wide and deep networks. The tools that we use in our derivations are uncommon deep learning and, hence, might be of additional interest.
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). Three common notions of sparsity are connection sparsity, which means that there is only small number of nonzero connections between nodes, node sparsity, which means that there is only a small number of active nodes (Alvarez & Salzmann, 2016; Changpinyo et al., 2017: Feng & Simon, 2017; Kim al., 2016; Lee 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 only a small number of active layers (Hebiri & Lederer, 2020). Approaches to achieving sparsity include augmenting small networks (Ash, 1989; Bello, 1992), pruning large networks (Simonyan & Zisserman, 2015; Han al., 2016), constraint estimation (Ledent et al., 2019; Neyshabur et al., 2015; Hiibee, 2020), and statistical regularization (Taheri et al., 2020).
The many empirical observations of the benefits of sparsity have sparked interest in mathematical support in the form of statistical theories. But such theories are still scarce and, in any case, have severe limitations. For example, statistical guarantees for deep learning with connection-sparse regularization have been established in Taheri et al. (2020), but they do not cover node sparsity, which, in view the removal of entire nodes, has become especially popular. Morcover, their estimator involves additional parameter, their theory is limited to single output node, and their results have a suboptimal dependence on the input vectors. Statistical guarantees for constraint estimation over connection- and node-sparse networks follow from combining results in Neyshabur al. (2015) and Bartlett & Mendelson (2002). But for computational and practical reasons, regularized estimation is typically preferred over constraint estimation in deep learning well in machine learning at large (Hastie et al.. 2015). Moreover, their theory is limited to single output node and ReLU activation, scales exponentially in the number of layers, and requires bounded loss functions. Statistical prediction guarantees for constraint estimation over connection-sparee networks have been derived Schmidt-Hiese
(2020), but their theory is limited to a single output node and ReLU activation and assumes bounded weights. In short, the existing statistical theory for deep learning with connection and node sparsity is still deficient.
The goal of this paper is to provide an improved theory for sparse deep learning. We focus on regression ptpression-type settings with layered, feedforward neural networks. The estimators under considera- tion consist of a standard leaat-squares estimator with additional regularizers that induce connection or node sparsity. We then derive our guarantees by using techniques from high-dimensions statis- ties (Dalalyan et al., 2017) and empirical process theory (van de Geer, 2000). In the case of

---

Under review as a conference paper at ICLR 2021
subgaussian noise, we find the rates
(log[mmp))
and mlp(log[mnp)) 3
n
for the connection-sparse and node-sparse estimators, respectively, where is the number of hidden layers, the number of output nodes, n the number of samples, p the total number of parameters, and p the maximal width the network. The rates suggest that sparsity-inducing approaches can provide accurate prediction 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 statistical perspective.
in very wide (with connection sparsity) and very deep (with either
Outline of the paper Section 2 recapitulates the notions of connection and node sparsity and introduces the corresponding deep learning framework and estimators. Section 3 confirms the empirically-obsery accuracies connection- and node-sparse estimation in theory. Section summarizes the key features and limitations of our work. The Appendix contains all proofs.
2 CONNECTION- AND NODE-SPARSE DEEP LEARNING
We consider data (3/1 ........ (yn Inn E R x Rd that are related via
y. = g- [.a + u
for i [I....,m}
(1)
for an unknown data getta-genrating function g. R + RM and unknown, random noise ......; Un R". We allow all aspects, namely y: 9.. T, and u, to be unbounded. Our goal is to model the data-generating function with a feedforward neural network of the form
gelz] = O' f' f'(0''''1-- f0
for x E IRd
(2)
indexed by the parameter space .M == 10 (O'...., 00) Ui E pe''"xp', The functions
f Re' + R²' are called the activation functions, and pd := d and p!+ == m are called the input and output dimensions, respectively. The depth of the network is I, the maximal width is
= ma p and the total number of parameters is p= = p/tp.
In practice, the total number of parameters often rivals or exceeds the number samples: p Rs n or >> 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, Our first sparse estimator
Σ 1 ge pe(= Teon ||@' }
+
con arg min @EM1
for tuning parameter reon
10, o0), nonempty set of parameters
Mi c f M:
||0' 1l1 S $1}
max
and the -nomm
Df+1 pf
||00| =
(O))
for j E (O....,,}, O Rp'
This estimator is an analog the lasso estimator in linear regression (Tibshirani, 1996). induces sparsity the level of connections: the larger the tuning parameter Teons the fewer connections among the nodes.
Deep learning with & re-eguuariizttinn has become common in theory and practice (Kim al., 2016; Taheri et al., 2020). Our estimator (3) specifies one way to formulate this type of regularization. The estimator is indeed regularized estimator (rather than constraint estimator), because the complexity
2

---

Under review as a conference paper at ICLR 2021
Estimatoor
Estimator
input
oulpul y
inpot
output y
Figure I: exemplary networks produced by the connection -pparee estimator (3) and the node-sparse estimator (6)
is regulated entirely through the tuning parameter Teon in the objective function (rather than through a tuning parameter in the set over which the objective function optimized). But & E-regularizzaiin could also be formulated slightly differently. For example, one could consider the estimators
G
con E arg min OEM
Ely so|w:112 + Toon II 10'11 Y=1
(4)
3=0
or
|y g g0 10:2:1112 con Σ 1
con E Earg min
(5)
9EM
==
The differences among the estimators (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 the parameters; we illustrate this in the following proposition.
Proposition 1 (Scaling of Norms). Assume that the all-zeros parameter (0pt-1xpt Opp xx)) E Mi is neither solution of (3) nor of (5), that Teon > O, and that the activation functions are nonnegative homogenous: f
E [0, and b TR. Then, I(@ Ill.........................II [((eem)) - || = 1 (concerns the inner layers) for all solutions of (3), while ((Oco))'ll (concerns all layers) for at least one solution of (5).
f for all E (1.....I),,
(1(Ocon) )0
Another way to formulate 4 l--regularization was proposed in Taheri et al. (2020): they reparametrize the networks through a scale parameter and a constraint version M and then to focus the regular- ization the scale parameter only. Our above-stated estimator (3) is more elegant in that it avoids the reparametrization and the additional parameter.
The factor |6'|| || in the regularization term of (3) measures the complexity of the network over the set M₁, and the factor Fcon regulates the complexity of the resulting 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 constraint estimation over sets with a predefined complexity.
The constraints in the set Mj of the estimator (3) can also retain the expressiveness of the full param- eterization that corresponds to the set M: for example, assuming again nomeegaive-hoomogeenn ac- tivation, one can check that for every T E M, there is r' E (O M : max ||@*|] [| S }} such that gr -r. Taheri et al. (2020, Proposition 1). 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 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 bounded loss). We instead invoke ideas from high-dimensional statistics, prove Lipschitz properties for neural networks, and use empirical process theory that is based on chaining (see the Appendix).
3

---

Under review as a conference paper at ICLR 2021
Our second estimator is
node E arg min
Σ v - ge(zi] mode | 2,,1
(6)
@6M2,1
for tuning parameter Nnode E 10, oc), nonempty of parameters
M2 c M
| 5
max (e(
and the noom
p
||0 11.11
(0)
for (0...., 1}, @r B
This estimator is analog of the group-lasso estimator in linear regression (Bakin, 1999). Again, to avoid ambiguitics in the regularization, our formulation is slightly different from the standard formulations in the literature, but the fact that group- regularizers leads to node-sparse networks has been discussed extensively before (Alvarez & Salzmann, 2016; 6; Liu et al., 2015; Scardapane et al., 2017): the larger the tuning parameter Tnode, the fewer active nodes the network.
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 Figure 1. Connection-sparss networks have only small number of active connections between nodes (left panel of Figure I); node-sparse networks have inactive nodes, that is, completely unconnected nodes (right panel of Figure 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) hardly known before- hand in data analysis. A main feature of sparsity-inducing regularization is, therefore, that it adjusts parts of the network architecture to the data. other words, sparsity-inducing regularization is 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, scarce. Such statistical analysis is, therefore, the goal of the following section.
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
err O
Σ 9. [|]]]]]>><>>]]
for O E M,
which is measure for how well the network ge fits the unknown function g* (which does need to be neural network) on the data at hand, and in terms of the prediction risk (or generalization error) for new sample (y, x) that has the same distribution the original data
risk = Ely 90(2)1
for O E M,
which measures how well the network ge can predict 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.
sample. We first study the prediction
We first observe that the networks in (2) can be somewhat "linearized:" For every parameter e E MM1 there is parameter
2 E Mi == -60'
θ²) : e R
max (01.....!-1
| S
4

---

Under review as a conference paper at ICLR 2021
such that for every R
ge [x] θ gg with f f' ER
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 connection to linear regression, where the above holds trivially with [2 æ.
also define
M2.1 == - 10=(0'-1 Ø @ E
ER Xp
|01|,2,1 s
max (0...,111)
accordingly.
In high-dimensional linear regression, the quantity central to prediction guarantees is the effective noise (Lederer & Vogt, 2020). The effective noise is in our notation (with / 0 and 1 to describe linear regression) 2| Ei= u, The above linearization allows us to generalize the effective noise to general deep-learning framework:
con = 2 sup WEM,
Σ u (oll::) i=
(8)
T nade
= 2/m sup
Σ u f [z,]
Ve,aa
where ||A||>> == max, (a.(e.))(........... (L.)) (............../// |4ا for A E Rm'''. 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,..., ths which are unknown in practice. Accordingly, we call the quantities roon and rode the oracle funing parameters.
We take a moment to compare the effective noises in (8) to Rademacher complexities (Koltchinskii, 2001; Koltchinskii & Panchenko, 2002). Rademacher complexities are the basis of a line of other statistical theories for deep learning (Bartlett & Mendelson, 2002; Golowich et al., 2017; Lederer, 2020a; Neyshabur et al., 2015). In our framework, the Rademacher complexities in the case 1 are (Lederer, 2020a, Definition 1)
sup LeMM;
kigela [ and
E Exi..... Ren
sup .
kg [.:]
for i.i.d. Rademacher random variables bi,...,ki, 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-Gr 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 while we use effective noises to measure the maximal impact of the stochastic noise on the estimators. (Our proofs also require 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.
Rademacher complexities to measure the size of the function class hand,
We can now state a general prediction guarantee. Theorem (General Prediction Guarantees). If 2 rtom holds that
{ /er[[e] 2roon | 110111
err con
inf @
Similarly, if Tnode 2 node it holds that
2 nodee
err(@node
inf @EM2.11
10 10'12.1)
n
5

---

Under review as a conference paper at ICLR 2021
Each bound contains approximation enror err[@] that captures how well the class of networks can approximate the true data-generan generating function 9. and a statistical error proportional to r Tcon/M and Tnode/ n, respectively, that captures how well the estimator at hand. In other words, T'heorem ensures that the estimators (3) and (6) predict-up to the statistical emror described by /eom/ o and moode n, respectively network. This observation can be illustrated further:
select within the class of networks
well as the best connection- and node-sparse
Corollary (Parametric Setting). If additionally 9 for a a E M11 it holds that
2rcon 1(0%)
err con
n
If insttedd g. = ge for a O' E M2,1, holds that errl node]
nnnode 1(0 1(0"))l2,
Hence, if the underlying data-generating function is a sparse network itself, the prediction errors of the estimators are essentially bounded by the statistical errors Tcon/ and Toode n.
The above-stated results also identify the oracle tuning parameters rcon and Fode as optimal tuning parameters: they give the best prediction guarantees in Theorem 1. But since the oracle tuning parameters are unknown in practice, the guarantees implicitly presume a calibration scheme that satisfies Tcon RS roon in practice. A natural candidate is cross-validation, but there are no guarantees that cross-validation provides such tuning parameters. This is limitation that our theories share with all other theories in the field.
Rather than dealing with the practical calibration of the tuning parameters, we exemplify the oracle tuning parameters in specific setting. This analysis will illustrate the rates of convergences that we can expect from Theorem 1, and it will allow us to compare our theories with other theories in the literature. Assume that the activation functions satisfy f0 Opp and 1-Lipschitz
continuous with respect to the Euclidean norms on the functions' input and output spaces R A popular example is ReLU activation (Nair Hinton, 2010), but the conditions are met by many other functions as well. Also, assume that the noise vectors Uı,.... ,..... Uh are independent and centered and have uniformly subgaussian entries (van de Geer, 2000, Display (8.2) Page 126). Keep the input vectors fixed and capture their normalizations by
U
x 12
and
71
Then, we obtain the following bounds for the effective noises. Proposition 2 (Subgaussian Noise). There is constant E (0, 20) that depends only on the subgaussian parameters of the noise such that
pfrea S cUx V (log (2mmp))
2 1 2
n
and
pf Pfrioote Poode S <C22 V wwwpmmmlllllllaa (logg/lggm2m)))
n
Broadly speaking, this result combined with Theorem illustrates that accurate prediction with connection- and node-sparse estimators is possible even when using very wide and deep networks. Let us analyze the factors one by one and compare them to the factors in the bounds of Taheri et al. (2020) and Neyshabur et al. (2015), which are the two most related papers. The connection-spars. case compares to the results in Taheri al. (2020), and it compares to the results in Neyshabur et al. (2015) when setting the parameters in that paper to p q (which gives setting that is slightly more restrictive than ours) or p = 1: = oc (which gives setting that is slightly less restrictive than ours). The node-sparse case compares Neyshabur et al. (2015) with p 2: oo (which gives a setting that is more restrictive than ours, though). Our setup is also more general than the one in Neyshabur al. (2015) in the sense that it allows for activation other than ReL.U.

---

Under review as a conference paper at ICLR 2021
The dependence on n is, as usual, // up logarithmic factors.
In the connection-sparse case, our bounds involve V/e= v Ei=1 | 12 rather than the factor Uso = ma...(.......) | of Neyshabur et al. (2015) or the factor V/2 = vE | of Taheri et al. (2020). In principle, the improvements of Uoe over Vhe and 72 can be up to a factor vn and up to a factor v vd, respectively; in practice, the improvements depend on the specifics on the data. For example, the training data of MNIST (LeCun et al., 1998) and Fashion-MMy
(Xiao et al., 2017) (Vπ- 250; vd 28 in both data sets), it holds that 20 Voo 2 U2/9 and Voe x V/so R 12/ respectively. In the node-sparse case, our bounds involve 722 which is again somewhat smaller than the factor U2 == mI... | in Neyshabur et al. (2015).
The main difference between the bounds for the connection-sparse and node-sparse estimators their dependencies on the networks' maximal width p. The bound for the connection-sparse estimator (3) depends on the width only logarithmically (through p), while the bound for the node-sparse estimator (6) depends on p sublinearly. The dependence the connection-sparse case is the same as in Taheri et al. (2020), while Neyshabur et al. (2015) can avoid even that logarithmic dependence (and, therefore, allow for networks with infinite widths). The node-sparse case in Neyshabur et al. (2015) does not involve our linear dependence on the width, but this difference stems from the fact that they use a more restrictive version of the grouping-we take the maximum over each layer, while they take the maximum over each node- and our results can be readily adjusted to their notion of group sparsity. These observations indicate that node sparsity as formulated above is suitable for slim networks (p < n)) but should be strengthened or complemented with other notions of sparsity otherwise. To give a numeric example, the training data in MNT ST (LeCun et al., 1998) and Fashion - ST (Xiao et al., 2017) comprise n 60 000 samples, which means that the width should be considerably smaller than 60 000 when using node sparsity alone. (Note that the input layer does not take part p. which means that d could be larger.)
For unconstraint estimation, one can expect a linear dependence of the error on the total number of parameters (Anthony & Bartlett, 1999). Our bounds for the sparse estimators, in contrast, only have a log [p] dependence on the total number of parameters. This difference illustrates the virtue of regularization in general, and the virtue of sparsity particular.
Both of our bounds have a mild vi dependence on the depth. These dependencies considerably improve on the exponentially- snporentially-iccrrasingg dependencies on the depth in Neyshabur et al. (2015) and, therefore, are particularly suited to describe deep network architectures. Replacing the conditions max; | I < 1 and max, (0'|22 < in the definitions of the connection-sparse and node-sparse estimators by the stricter conditions Σ, | |1 S. 1 and Ej | 12,1 < 1, respectively (cf. Taheri et al. (2020) and our discussion in Section 2). the dependence on the depth can be improved further from vi to (2/1)'vī (this only requires a simple adjustment of the last display in the proof of Proposition 4), which is exponentially decreasing in the depth.
Our connection-sparse bounds have a mild log[m] dependence on the number of output nodes; the node-sparse bound involve an additional factor vm. The case of multiple outputs has not been considered in statistical prediction bounds before.
Proposition 2 also highlights another advantage of our regularization approach over theories such as Neyshabur et al. (2015) that apply to constraint estimators. The thcories for constraint estimators require bounding the sparsity levels directly, but in practice, suitable values for these bounds are rarely known. In our framework, in contrast, the sparsity is controlled via tuning parameters indirectly, and Proposition a- not providing a complete practical calibration scheme-giver insights into how these tuning parameters should scale with d, I, and so forth.
We also note that the bounds in Theorem can be generalized readily to every estimator of the form
Σ lI ge [=. + ggen 0
arg min M.Maon
gen
where r rgen E [0, oo) is a tuning parameter, M The bound for such an estimator is then
Mgen gen any nonempty subset of M, and ||
any norm.
err gen] < inf
err θ +
2r 2rgen
[o00}
M.Mg
gon
n
7

---

Under review as a conference paper at ICLR 2021
Approach
Basis
References
FatShat
Fat- shattertg dimension
Bartleu (1998)
Rad1
Rademacher complexity
Bartlett Mendelson (2002); Lederer (2020a): Neyshabur et al. (2015)
Rad2
Rademacher complexity
Bartlett & Mendelson (2002); Golowich et al. (2017); Lederer (2020a)
NonPar
non-parametric statistics
Schmidt- Hicher (2020)
HighDim
High-di High-dimeessinal statistics
Taheri et al. (2020)
multiple outputs
Regularized
(sub)linear in
node sparsity
Approach
Feasible
P -o-loss
FatShat
Radi
Rad2
NonPar
HighDim
Table I: presence (V) or absence of certain features in previous statistical theories for sparse deep learning
for Tgen 2 gen where "gen is as roo but based on the dual norm of | instead of the dual norm of || ||.. For example, one could impose connection sparsity on some layers and node sparsity on others, or could impose different regularizations altogether. We omit the details to avoid digression.
We finally illustrate that the bounds for the prediction errors also entail bounds for the generalization errors. For simplicity, we consider a parametric setting and subgaussian noise again.
Proposition 3 (Generalization Guarantees). Assume that the imputs x, $1,..., In are i.i.d. random vectors, that the noise vectors Ui,...; Un are independent and centered and have uniformly sub- gaussian entries, and that reons Toode - as n + cc. Consider an arbitrary positive constant b E 00). If f- g for O' E Mi that independent of the sample size n, it holds with probability at least 1/n that
(log (log(2mmpp)) 3 1(0r)))
risk risk(@rrn) @ron) S (11+ risk((") + co
n2
for a constant e E (0, 00) that depends only on and the subgaussian parameters of the noise. Similarly. if = ge- for O E M221 that is independent of the sample size n, it holds with probability at least i/n that
mlp mlpp(og((2m77)
risk con] I (1 + risk + cT2
for a constant e (0, oo) that depends only on b and the subgaussian parameters of the noise.
Hence, the generalization errors are bounded by the same terms as the prediction errors.
4 DISCUSSION
Our statistical theory for sparse deep learning incorporates node sparsity as well connection sparsity, scales favorably in the number of layers, provides insights into how the tuning parameters should scale with the dimensions of the problem, and applies unbounded loss functions. It is the first statistical theory that has all of these features cf. Table 1. Additionally we avoid the introduction of an additional scaling parameter and improve the dependence of the rates the input data. Finally, our novel proof approach based on high-dimensional statistics and empirical impirical-process theory of independent interest.
8

---

Under review as a conference paper at ICLR 2021
Evidence for the benefits of deep networks has been established in practice (LeCun et al., 2015; Schmidhuber, 2015), approximation theory (Liang & Srikant, 2016; Telgarsky, 2016; Yarotsky, 2017), and statistics (Golowich et al., 2017; Taheri et al., 2020). Since our guarantees scale at most sublinearly in the number of layers (or even improve with increasing depth see our comment on Page 7), our paper complements these lines of research and shows that sparsity-indueing regularization is an effective approach to coping with the complexity of deep and very deep networks.
Connection sparsity limits the number of nonzero entries in each parameter matrix, while layer 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 suitable 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 the first one that considers multiple output nodes; classification theory with a logarithmic dependence on the output nodes has been established very recently 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 similaritics with proofs in high- dimensional statistics; to formulate and control the relevant empirical processes, we use the concept of effective noise, chaining, and Lipschitz properties of neural networks. These tools are not standard in deep learning theory and, therefore, might be of more general interest (see Appendix A.7 for further details).
Our theory shares some limitations with all other current theories in deep learning: the network architectures are simpler than the ones typically used in practice (cf.. Lederer (2020b), though); the bounds concern global optima rather than the local optima or saddle points provided by many practical algorithms; and the theory does not entail a practical scheme for the calibration of the tuning parameters. Nevertheless, our theory, and mathematical theory general, provides insights about what accuracies to expect in practice and about what network types and estimators might be suitable for a given problem.
In summary, our paper highlights the benefits of sparsity in deep learning and, more generally, showcases the usefulness of statistical analyses for understanding neural networks.
REFERENCES
J. Alvarez and M. Salzmann. Learning the number of neurons in deep networks. In Adv. Neural Inf. Process Syst., pp. 2270-2276 2016.
M. Anthony and P. Bartlett. Neural network learning: theoretical foundatioon.. Cambridge University Press. 1999.
T. Ash. Dynamic node creation in backpropagation networks. Connect. Sci., 1(4):365-375, 1989.
S. Bakin. Adaptive regression and model selection in data mining problems. PhD thesis, The Australian National University, 1999.
P. Bartlett. weights is more important than the size of the network. IEEE Truns. Inform. Theory, 44(2): 525-536, 1998.
The sample complexity of pattern classification with neural networks: the size of the
P. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, 2002.
M. Bello. Enhanced training algorithms, and integrated training/architecture selection for multilayer perceptron networks. IEEE Trans. Neural Netw,, 3(6):664-877 875, 1992.
S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press, 2013.

---

Under review as a conference paper at ICLR 2021
B. Carl. Inequalities of Bernstein matnstein-Jackoo--yyye and the degree of compactness of operators in Banach spaces. Ann. Inst. Fourier, volume 35, pp. 19-118, 1985.
S. Changpinyo, M. Sandler, and A. Zhmoginov. The power of sparsity in convolutional neural networks. arXiv:1702.06257, 2017.
A. Dalalyan, M. Hebiri, and Lederer. On the prediction performance the lasso. Bernoulli, 23(1): 552-581, 2017.
J. Feng and N. Simon. Sparse-input neural networks for high-dimensional nomparametric regression and classification. arXiv: /rX1v:/711.07522 2017.
N. Golowich, A. Rakhlin, and O. Shamir. Size bize-independent sample complexity of neural networks. 1:21::171,.06511, 2017.
Han, H. Mao, and W. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In Proc. ICML, 2016.
T. Hastie, R. Tibshirani, and M. Wainwright. Statistical learning with sparsity: the lasso and generalizations. CRC press, 2015.
M. Hebiri and J. Lederer. Layer sparsity in neural networks. arXiv2006. 15604, 2020.
J. Kim, V. Calhoun, E. Shim, and J.-H. Lee. Deep neural network with weight sparsity control and pre-trate pre-training extracts hierarchical features and enhances classification performance: evidence from whole-brain resting-state functional connectivity patterns of schizophrenia. Neuroimage, 124: 127-146, 2016.
V. Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Trans. Inform. Theory, 47($):1902-1914, 2001.
Koltchinskii and Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. Ann. Statist., 30(1):1-50, 2002.
Y. LeCun, L. Bottou, Y. Bengio, and Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))2278-3324 1998.
Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. Nature, 521:436 444, 2015.
A. Ledent, Y. Lei, and M. Kloft. Norm-based generalisation bounds for multi-class convolutional neural networks. arXiv: 12430, 2019.
J. Lederer. Bounds for Rademacher processes via chaining. arXiv: 2010.
J. Lederer. Risk bounds for robust deep learning. arXiv:2009.06202 2020a.
J. Lederer. No spurious local minima: on the optimization landscapes of wide and deep neural networks. arXiv:2010.00883 2020b.
J. Lederer and S. van de Geer. New concentration inequalities for suprema of empirical processes. Bernoulli, 20(4), 2014.
Lederer and M. Vogt. Estimating the lasso's effective noise. arXiv:2004. 1554, 2020.
H. Lee, C. Ekanadham, and A. Ng. Sparse deep belief net model for visual area V2. In Adv. Neural 2008.
Inf. Process. Syst., pp.
W. Li and J. Lederer. Tuning parameter calibration for é reegullrdd logistic regression. J. Statist, Plann. Inference, 202:80-98, 2019.
S. Liang and R. Srikant. Why deep neural networks for function approximation? arXir:1610.0416/ 2016.
B. Liu, M. Wang, H. Foroosh, M. Tappen, and M. Pensky. Sparse convolutional neural networks, In IEEE Int. Conf. Comput. Vis. Pattern Recognit., pp. 806-814, 2015.
10

---

Under review as a conference paper at ICLR 2021
C. McDiarmid. On the method of bounded differences. Surv. Comb., 141(():148-185)) 1989.
V. Nair and G. Hinton. Rectified linear units improve restricted Boltzmann machines. In Int. Conf. Mach. Learn., pp. 807-814, 2010.
B. Neyshabur, R. Tomioka, and N. Srebro. Norm-base capacity control in neural networks. In Conf. Learn. Theory, pp. 1376-1401, 2015.
Nie, M. Wang. Zhang, S. Yan, B. Zhang, and T.-S. Chua. Disease inference from health-related questions via sparse deep learning. IEEE Trans. Knowl. Data Eng., 27(8):2107-2199 2015.
S. Scardapane, D. Comminiello, A. Hussain, and A. Uncini Group sparse regularization for deep neural networks. Neurocomputing, 241:81-89, 2017.
J. Schmidhuber. Deep learning in neural networks: An overview. Neural Networks, 61:85-117, 2015.
J. Schmidt-Hieher. Nonparametric regression using deep neural networks with ReLU activation function. Ann. Statist. 48(4):1875-1897, 2020.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In Int. Conf. Learn. Representations, 2015. 2015.
M. Taheri, F. Xie, and J. Lederer. Statistical guarantees for regularized neural networks. arXiv:2006.00294, 2020.
M. Telgarsky. Benefits of depth in neural networks. In Proc. Mach. Learn, Res., volume 49, pp. 1517-1539, 2016.
R. Tibshirani. Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. Stat, Methodol., 58(1):267-288, 1996.
S. van de Geer. Empirical processes in M-estimation. Cambridge Univ. Press, 2000.
A. van der Vaart and J. Wellner. Weak convergence and empirical processes. Springer, 1996.
W. Wen, Wu, Y. Wang, Y. Chen, and Li. Learning structured sparsity deep neural networks. In Adv. Neural Inf. Process Syst., pp. 2082-2090, 2016.
H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms.
2017.
D. Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94: 103-114, 2017.
R. Zhuang and J. Lederer. Maximum regularized likelihood estimators: general prediction theory and applications. Stat, ((1)=e186,, 2018.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
The Appendix consists two auxiliary results and the proofs of Theorem and Propositions and 2. Our approach combines techniques from high-dimensional statistics and empirical imprrical-process that are very different from the techniques used in most other approaches in the literature.
process theory
A.1 LIPSCHITZ PROPERTY
In this section, we prove Lipschitz property that we use in the proof of Proposition 2. Proposition 4 (Lipsehitz Property). the framework of Sections and 3, holds for all O, e. M1 that
Io [|] - --r To S < F|F
and for all G, M2,1 that
|o| gr S | r|F.
The Frobenius norm is defined as
p p
Σ
Σ j=0
O 1x12
for θ E M2,1 M1 M2,1
P
Proposition generalizes (Taheri et al., 2020, Proposition 2) to vector-valued network outputs and to node sparsity, and it replaces their | with the smaller | in the connection-spaan -eprtiioo---ssseeeeeeeee case.
Proof of Proposition 4. This proof generalizes and sharpens the proof of Taheri et al. (2020), and simplifies some arguments of that proof. We define the "inner subnetworks" of network Ie with O M2, as the vector-valued functions
Soge
IR" +
Rd
Su9e
and
g : gd + RF
a + 5 x == 0¹ 0'8 f'
for j {1...., 1}. functions
Similarly, we define the "outer subnetworks" of Is as the real-valued
5'g Re R
z + Sagalz) -' [[]]]
for j E {I....,.- 1} and
s' Te
RF R
S
- f'
The initial network can be split into an inner and an outer network along every layer j E {l,...,4].
Tolø| = S S' S 10
for x E Rd
We call this our splitting argument.
To exploit the splitting argument, we derive contraction result for the inner subnetworks and Lipschitz result for the outer subnetworks. We denote the fz-operator norm of matrix A, that is, the largest singular value of A, by |Al Using then the assumptions that the activation functions are
1 I-Lipschitz and [' Opt. get for every O (0l-1 θo) M2,1 and idd that
(5)-20a(m]) | = 2 -
2o [
12

---

Under review as a conference paper at ICLR 2021
| 1l
2
-
x
|
j
3
j-2
|
10
k=1
j-2
| llop
|0||
for all j E .2.....I}. Now, since from the display that
| lop
| F I
| 12,1 and 2 M221,, we can deduce
j-2 II k=
S
R |2,1
|,0|
This inequality our contraction property.
By similar arguments, we get for every ø1, 22 E RP that
S go 21 5 gzl 22122
= | fl
f f ... f [222]]] l
( f\
(f- (00.1...[((()))
1
|op|| f 1 ( [|22]] l2
I Hlop || 2212
f (1....,(}. where
I
| lpp 1. Hence, similarly as above,
1S'Telza 2/] "ooalzal -
| |
| 1121 121
-2212-
This inequality is 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 De and Ir with parameters Ø = (0--1 ,.... ØD)
M2,1 and F (T'-1 .........T".... To) E .2,11, respectively. Our above-derived splitting argument applied with j and j I, respectively, yields
| [x] g-|>|||
[S St'gg---g-spaaarr [5-
Elementary algebra and the fact that S (3- S' 1 - [x]] j E (,.....I} then allow us to derive
for
st -e
S x=]]
S S'g ge [S)-19/[01]
s' [ 2
5 Tāl
5 x - S' 9 S x]]
=
Σ
S 15)11
- Ie [S -
2 2 [m]]]
1=2
+ + [-
S'gr [ 15-1gm Tr xe]
13

---

Under review as a conference paper at ICLR 2021
= s' Je Soggla] - S' (uggr [c]
T ge || ge 0 15-1
( 2- [=]]])
+ Te St 11 [0]]
S' S 1 2
<
S 96 S00 ||] - 5 66 Sngr x: 1/2
S 96 [S [9
5 g3
O 1f
- [z]]
[=]]]]|
+ [ [1-
S'
We bound this further by using the above-derived Lipschitz property of the outer networks and the observation that S 1 [x]]]
S
S' 10
1-1
Te [c]
Tr
( <
I k=1
| |2,
Soge [a)]
Σ
O 2..1 ||||-19[(]
- (S-299 |z1]]||
which is by the definition of the inner networks equivalent to
Tola] gr
2.1
10
h
[S)- 29F [
- [0]]]l
2.1
j=2
k=j
Using the properties of the operator norm, we can deduce from this inequality that
[ T-
00|1112 s
II
12.
|100 -
+
Σ J=2
II
12,1
Invoking the mentioned conditions the activation functions and the contraction property for the inner subnetworks then yields
I [c) J-(m)) 3ل[2=|12= -
max (E(0.....!))
II
max e 12,1
12, II (2.))))
Σ
| θ 11pp
|ø|2
kE 2-11
$ < FIle
The proof for the connection-sparse case is almost the same. The main difference is that one needs to use the | and 1|1 -nomms (rather than the | 1-12-- and IIollop- -orms))rms) and the inequality |Abl < ||A|| Lipschitz properties.
(rather than the inequality |Ab|2 S |Aloppbb [b22) establish suitable contraction and
A.2 ENTROPY BOUND
In this section, we establish bounds for the entropies of Mn and M2,1- The distance between two networks ge and 9F defined as dist | Trl == VE [9 m. 9r [...I.///// Given this distance function and radius E co), the metric entropy of nonempty set A C - =
(Q'-1.... ...... k9) O E TRRp"" xx is denoted by H(I, A). We then get the following entropy bounds.
14

---

Under review as a conference paper at ICLR 2021
Lemma (Entropy Bounds). In the framework of Sections 2 and 3, it holds for constant cи (0, oo) and every E (0, oo) that
(ox 2
T
H S CH
log
+
2
(0x) )
and
(Toc) 12
po
H M2,. S CH
log
2
t²
(o )2(
Proof of Lemma 1. The first bound can be derived by combining established deterministic and randomization arguments (Carl, (Leder,,,,r,,, 2010, Proof of Theorem I.1)r(Taheri al., 2020, Proposition 3).
For the second bound, observe that
p++1 pd
Pd
p++l
(00) 10'1== = Σ E
S p
(0)pB=
10 = /pll0'
1=1 1=1
for all j (0,..../-11] and @ E R xp
We used turn definition of the || 1|| -norm on
Page 2, the linearity and interchangeability of finite sums and the inequality |alii S Vollal12 for all
R 3. the definition of the || 112,1-norm Page 4, and 4. the definition of the width y on Page 2.
Hence, M2,1 C. CpMM A bound for the entropies of M2,1 can, therefore, be derived from the first bound by replacing the radii t on the right-hann hand side by t/ t/PP.
A.3 PROOF OF THEBREM 1
In this section, we state a proof for Theorem 1. The proof is inspired by derivations high- dimensional statistics see, for example, (Zhuang & Lederer, 2018) and references therein.
Proof of Theorem I. The main idea of the proof is to contrast the estimators' objective functions evaluated at their minima with the estimators' objective functions other points. Our first step is to derive what we call basic inequality. By the definition of the estimator in (6), it holds for every E M2,1 that
Σ y. galx;ll12 + Tuode 16 11,1 S
@'112.
Σ
y:
go ge|zi]|| + Tnode |0'
where we use the shorthand θ = ② pode. We then invoke the model in (1) to rewrite this inequality as
D [g-[xx] + u. 96 9810;]1 : + Tnode 12.12.. <
Σ 9 [xx]] + go [2:1112 Tnode pooodelO'll 1011,2,1
Expanding the squared terms and rearranging the inequality then yields
[as]]
96 <
|g- g
am1
(2:))) T u. 2 > (go T u: + @nndelllO 12,1 Tnode 1 112.1
+
This is our basic inequality.
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 general parameter P E M2,1 according to
gr (x.)) u; = 2 Σ (
9- (x.)) T u
15

---

Under review as a conference paper at ICLR 2021
with I E M2,1 Using the 1. the properties of transpositions, 2. the definition of the trace function, the cyclic property of the trace function, and 4. the linearity the trace function yields further
2 gr (r) u, 2
| (a.)) ((r))Tu:
u
trace (gr(a:)) (T)) ui
2
i=1
Σ (race ue (FF((:)))) _ (T
2
im1
( (Trl [T>)]]
2 trace
u.
Now, 1. denoting the column-vecton vector that corresponds to the kthh column of matrix A by Aak. using Hölder's inequality, 3. using Hölder's 's inequality again, and 4. again Hölder's inequality and our definitions of the elementwise lx -norm,, we find
p'
u. (0:) ) (T))
2 (gr(x;])
u: =
Σ k=
2 p¹
us O (ol)))) ))
|ITT))ol22
2
Σ uu (gT(oal)))
Σ [(T))
kE(L....)))
< m
Tr (x.1)
||
which implies in view of the definition of the effective noise in (8)
2 (gr(z))) u, S r nide l 12.1.
This inequality our bound on the empirical process terms. We can combine the bound on the empiricial process term and the basic inequality to find
[x.] 96 [
| - ge [x:3:
+ miode @ 12.11 + riode r 11'122.1 + Tnodell0'l2. 12,1 Tuode G 1l..
Using then the assumption Tnode Tnodo yields
x
Σ
[x:] - 9 1alaill S
E1...10 go [x:12:1122 + 2r node 1
Multiplying both sides by 1/n and taking the infimum over O E M2,1 on the right-hand side then gives
Σ |--] - [o]æ:l11
- < inf MEMa,1
[
Σ 9 [ ge [x: 2rnode (e'1l2.))
Invoking the definition of the prediction error on Page gives the desired result. The proof for the connection-sparse estimator is virtually the same.
16

---

Under review as a conference paper at ICLR 2021
A.4 PROOF OF PROPOSITION 1
In this section, we give 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 4 con and ② Ocn of (3) and (5), respectively, satisfy (Q.on) (0con) o 25 xy for all j E (O.....1).
It then follows from the assumed nonnegative homogeneity, Teon > 0, and the definition of the estimator in (3) that (1. (0' 1 for all solutions A con-
Given solution Ocon of (5), define 1(0 "0mm)))111111 /111 (1+ +.... ((()on)'l1// /1/ 1) and verify the fact that r M with 1 = a(o))))" /lo() 10 I = a(Ocon) el((@ "Il IlI.... has the same value in the objective function as Ocon-
A.5 PROOF OF PROPOSITION 2
In this section, we establish proof of Proposition 2. The key tools are the Lipschitz property of Proposition 4 and the entropy bounds of Lemma 1.
The main idea is to rewrite the event under consideration in a form that amenable known tail bounds for suprema of empirical processes with subgaussian random variables.
Proof of Proposition 2.
The connection-sparse bound follows from
P r cV V nll (log 2mmp))) 3
P sup
ui (g x2l) Σ i=1
2 c v nl((ogg2mmmp)
MEM.
S mp'
max
pl2 sup WEM,
Σ u. ( (ool
2 cT v nll (log/2mmm))
je(I....m
kE(L...pp
S mmp'
mnp
where we use in turn 1. the definition of on in (8). 2. the union bound, 3. van de Geer (2000, Corollary 8.3) and Proposition and Lemma 1, and the inequality p' < p = Σj=n Ein p and consolidating the factors. The key concept underlying van de Geer (2000, Corollary 8.3 Page 128) chaining (van der Vaart & Wellner, 1996, Page 90).
The same considerations also apply to the node-sparse case, but get additional factor / vm 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 terms of Toe vs. T2 stem from the different Lipschitz constants in Proposition 4.
A.6 PROOF OF PROPOSITION 3
Proof of Proposition 3. The proof is based on standard empirical-procee theory, including contrac- tion and symmetrization arguments.
17

---

Under review as a conference paper at ICLR 2021
Using basic algebra and measure theory, it is easy show that
risk [oon] S (1 + b) risk risk((")) + cb err corr(@con]
Cb
1 Σ [1g-(2z) 96....
[2 -. 9 (2m1112)
[2x,]
for constant с E (0, 20) that depends only b. The first term in this bound is the minimal risk as stated in the proposition, and the second term can be bounded by Corollary and Proposition 2. Hence, it remains to bound the third term.
In view of the law of large numbers, it is reasonable to hope for the third term to be small. But to make this precise, we have keep mind that the estimator itself depends on the input vectors. We, therefore, need to prepare the third term for the application of uniform version of the law of large numbers. Using standard contraction arguments- see (Boucheron al., 2013, Chapter 11.3), for example-an and Hölder's inequality, we can bound the third term by bounding
max(I 1 conn))lll
sup BEM1
Σ ge
[c.]
I6
E
ge
[c)]
ge
(::
which removes the dependence on the estimator θ con up the leading factor. To see that we can also neglect that factor, verify (see Proposition and the proof of Theorem 1) that ((@ < 2 with high probability as long as rion 2 Cu (oloo/nl(l/22mmpp) with e large enough. Consequently, just need consider the quantity
sup McM1
Σ 1=1
g [ 9alæ,
E Elgo-
[x>]]
- g0lun fel
in the following.
The last step is bring this term in form that is amenable earlier proofs. Using standard symmetrization arguments see van der Vaart & Wellner (1996, Chapter 2.3), for example) we can bound this quantity by bounding
sup M
ly To [x.]]
Ie (x)))
where k,,...,,, are i..d. Rademacher random variables. But even though kj.-.., ii.d. Rademacher random variables, we do resort Rademacher complexities; instead, use that Rademacher random variables are subgaussian, so that we can then proceed similarly as in the proof of Proposition? 2.
.....,,, kn are
The node-sparse case can be treated along the same lines.
A.7 EXTENSIONS
Our proof approach disentangles the specifics the objective function (proof of Theorem 1), of the network structure (proof of Proposition 4), and of the stochastic terms (proofs of Lemma I and Proposition 2). This feature allows one to generalize and extend the results of this paper in straight- forward ways. For example, extensions different noise distributions only need a corresponding version of Proposition 2-with everything else unchanged. One could envision, for example, using concentration inequalities for heavy-tailed distributions such in Lederer & van de Geer (2014). Extensions to different loss functions, to give another example, can be established by adjusting Theorem accordingly. This can be done, for example, by invoking ideas from specialized literature on high- nigh-dimmnsiooal logistic regression such as Li & Lederer (2019). We avoid going into further details avoid digression; the key message is that the flexibility of the proofs is yet another advantage of our approach.
18


Reviews:
[{"review_id": "mo4yEDWeTYn", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\nThis paper studies the problem of estimating a vector valued regression function by neural networks. They provide a bound on the in-sample prediction error for a neural network estimator under two types of regularizations; one that induces connection sparsity and another that induces node sparsity. The in-sample error is bounded by the in sample error of an estimator computed in the noiseless case.\n\n# Strengths\nStatistical theory of the success of deep learning is an important problem currently. Moreover, studying the performance of neural network estimators under appropriate regularization provides insights into their practical success. \n\nThis paper provides some insights into the workings of different types of regularization commonly used.\n\nThe paper is well written and organized. The proofs are concise and clear. \n\n# Weaknesses\nHowever, my main concerns with this paper are as follows:\n -  The study of the in-sample prediction error and not the generalization error. A crucial problem in deep learning is to discover why neural networks that are over-parametrized have low generalization error. In fact, it has been suggested, for eg in Arora et. al. (\tarXiv:1905.13655 ) that specific norm regularization may not lead to optimal generalization. \n -  The related work, specifically Neyshabur2015, study the generalization error or out of sample error so the comparison with their bound does not seem to be direct. \n - In general, it is not clarified how this work supersedes previous work. In particular while the dependence on the input vector is shown to be better, a concrete example of when such an improvement would manifest itself would be very helpful. \n - There seems to be other work that seems relevant but of this I am not certain for eg. Mhaskar and Poggio (arXiv:1802.06266). Also, a large amount of literature on bounds on generalization error in the case of classification i.e. Neyshabur 2017a (arXiv:1707.09564), Arora et. al. (arXiv:1802.05296).", "extra_scores": {}, "extra_text": {}}, {"review_id": "hr5zaCgrmeL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\nThis paper introduces theoretical statistical guarantees for different types of sparsity inducing regularization in regression type settings for deep layered feedforward networks, using techniques of high-dimensional statistics and empirical process theory. \n\n##########################################################################\n\nPros:\n1. The paper introduces techniques well-known in high dimensional linear regression for deriving guarantees in deep learning. \n2. The paper introduces methods that are more elegant and simpler than previous methods. \n3. The paper is well written, easy to understand and with clear definitions and connections between sections. \n4. The comparisons with related work are well-addressed. \n\n##########################################################################\n\n\nCons:\n1. While the paper provides interesting theoretical results, it  would be interesting if the authors can show empirical consistency for some of their claims, for example, their conclusion that connection sparsity is suitable to handle wide networks, but node\nsparsity is suitable only when complemented by connection sparsity or other strategies. Similarly, while the paper cannot provide ways to select regularization parameters, the dependence on m,n,p should be compared empirically. \n2. The authors should clarify clearly the assumptions that makes their mathematical treatment feasible. The authors should also clarify the conditions under which their guarantees do not hold. \n3. Are the authors' methods extendable to settings other than regression for example classification?\n \n\n\n##########################################################################\n\nQuestions during rebuttal period: \n\n \nPlease address and clarify the cons above ", "extra_scores": {}, "extra_text": {}}, {"review_id": "CV7o8VYpqh8", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies mean-squared-error bounds for neural networks with small $\\ell_1$-norm. The use of $\\ell_1$-norm constraint is analogous to the use of LASSO in sparse linear regression. They give a \"mean-squared-error\" bound because they only analyze a fixed-design setting (where the goal is only to analyze the effect of noise) instead of the random-design setting which requires an additional analysis of generalization to fresh data. \n\nThey emphasize that they study the case where the returned network is regularized using an $\\ell_1$-penalty (as in eqn (3)) instead of the case where the minimization is explicitly constrained to an $\\ell_1$-ball.  As the authors say, regularization is more convenient to implement than constrained optimization in practice. They claim that this makes the problem they analyze quite different from analyzing the explicitly constrained version, because the minimization is technically over an unbounded class of functions. However, we know from the basic theory of Lagrange multipliers that the optimizer of the $\\ell_1$-regularized version is also the optimal solution under some $\\ell_1$-norm constraint. So conceptually, the difference between the regularized and constrained versions is not that important, although analyzing the regularized version creates some extra technical difficulties.\n\nThis paper makes some other overstated claims about the novelty of their result and analysis. The authors claim that their analysis is based off of some new techniques from high-dimensional statistics which have not appeared in the neural net generalization literature. However, their analysis is in fact almost the same as the usual generalization bounds. For example, the \"generalized noise\" (8) which they are concerned with is basically just the empirical Rademacher complexity of a single neuron of the last hidden layer (consider the case where the noise u is Rademacher).\n\nOverall, I think this work does not provide much fresh insight into generalization bounds for neural networks, and I would tend towards rejection.\n\nMinor notes:\n- Older related work. The idea of analyzing generalization error based on $\\ell_1$-norm (which associates with sparsity) can be traced back at least to the paper 'The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network' by Bartlett '98. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of using sparse coding to create better generalization in neural networks. The new generalization bound of the neural network only depends on the l1 norm of the weight, instead of the original \ell_2 version as in previous papers. 


Well this direction is promising, the major concern about this work is that how they compare with existing generalization bounds empirically. There are definitely some hand-crafted instances where this bound excel, but the authors did not provide enough evidence that this bound would actually be better than others for neural networks trained in practice: For example, would adding a relatively large \ell_1 regularizer resulted in a drastic decrement in test accuracy? How does the bound compare with compression based approach such as VC dimension + weight pruning (since the weights are somewhat sparse, so the VC dimension is lower) -- One might argue that those pruning techniques do not have theoretical guarantees that they can work -- Well this technique does not have theoretical guarantees either (whether this objective can be minimized efficiently): The theorem, at least in the current form, seems to only apply to networks that are the "global optimals" of some non-convex training objective (MSE-loss involving a non-linear neural network +  ell_1 regularizer on its weights). It is also unclear whether such global optimals can be found efficiently in practice. At very least, the authors should devote some effort demonstrating the superiority of their bound empirically.



Decision: Reject