THE EFFICACY OF L1 REGULARIZATION IN NEURAL NETWORKS
Authors: Gen Li
Yuantao Gu
Jie Ding
Venue:  (2021)
Keywords: Model selection
Neural Network
Regularization

Abstract: A crucial problem in neural networks is to select the most appropriate number of hidden neurons and obtain tight statistical risk bounds. In this work, we present a new perspective towards the bias-variance tradeoff in neural networks. As an alternative to selecting the number of neurons, we theoretically show that $L_1$ regularization can control the generalization error and sparsify the input dimension. In particular, with an appropriate $L_1$ regularization on the output layer, the network can produce a statistical risk that is near minimax optimal. Moreover, an appropriate $L_1$ regularization on the input layer leads to a risk bound that does not involve the input data dimension. Our analysis is based on a new amalgamation of dimension-based and norm-based complexity analysis to bound the generalization error. A consequent observation from our results is that an excessively large number of neurons do not necessarily inflate generalization errors under a suitable regularization.


Under review as a conference paper at ICLR 2021
THE EFFICACY OF L1 REGULARIZATION IN NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
A crucial problem in neural networks is to select the most appropriate number of hidden neurons and obtain tight statistical risk bounds. In this work. we present new perspective towards the bias-variance tradeoff in neural networks. As alternative to selecting the number of neurons, we theoretically show that T, reg- ularization can control the generalization error and sparsify the input dimension. In particular, with an appropriate L regularization on the output layer, the net- work can produce statistical risk that near minimax optimal. Moreover, an appropriate L1 regularization on the input layer leads to risk bound that does not involve the input data dimension. Our analysis based on new amalgamation of dimension-based and norm-based complexity analysis to bound the generaliza- tion
error. consequent observation from our results is that an excessively large number of neurons do not necessarily inflate generalization errors under suitable regularization.
INTRODUCTION
Neural networks have been successfully applied in modeling nonlinear regression functions in var- ious domains of applications. A critical evaluation metric for predictive learning model is to measure its statistical risk bound. For example, the Lı or L2 risks of typical parametric models such as linear regressions are at the order of (d/n)1/2 for small d (Seber & Lee, 2012), where d and n denote respectively the input dimension and number of observations. Obtaining the risk bound for nonparametric regression model such as neural networks is highly nontrivial. It involves an approxi- mation error (or bias) term well as generalization error (or variance) term. The standard analysis of generalization error bounds may not be sufficient to describe the overall predictive performance of model class unless the data assumed be generated from it. For the model class of two-layer feedforward networks and a rather general data eeta--enerating process, Barron (1993; 1994) proved an approximation error bound of 1/22 where r denotes the number of neurons. The author further developed a statistical risk error bound of ((d/n))//4) which is the tightest statistical risk bound for the class of two-layer neural networks up the authors' knowledge (for n1). This risk bound is based on an optimal variance tradeoff involving an deliberate choice of Note that the risk at a convergence rate much slower than the classical parametric rate. We will tackle the same problem from a different perspective, and obtain much tighter risk bound.
practical challenge closely related to statistical risks is select the most appropriate neural net- work architecture for particular data domain (Ding et al., 2018). For two-layer neural networks, this is equivalent to selecting the number of hidden neurons r. While small r tends to underfit, re- searchers have observed that the network is not overfitting even for moderately large Nevertheless, recent research has also shown that an overly large (e.g., when r > n)) does cause overfitting with high probability (Zhang al., 2016). It can be shown under some non-degeneracy conditions that a two-layer neural network with more than n hidden neurons can perfectly fit n arbitrary data, even in the presence of noise, which inevitably leads overfitting. A theoretical choice of r suggested by the asymptotic analysis in (Barron, 1994) is at the order of 1/2 and practical choice of often from cross-validttion with an appropriate splitting ratio (Ding et al., 2018). An alternative perspective that we advocate is to learn from a single neural network with sufficiently many neurons and an appropriate L, regularization on the neuron coefficients, instead of performing a selection from multiple candidate neural models. A potential benefit of this approach is easier hardware

---

Under review as a conference paper at ICLR 2021
implementation and computation since do not need to implement multiple models separately. Perhaps more importantly, this perspective of training enables much tighter risk bounds, as we will demonstrate. In this work, we focus on the model class of two-layer feedforward neural networks.
Our main contributions are summarized below. First, we prove that L1 regularization on the co- efficients of the output layer can produce a risk bound O((d/n) (up to a logarithmic factor) under the L1 training loss, which approaches the minimax optimal rate. Such rate has not been established under the L2 training loss so far. The result indicates a potential benefit of using L1 regularization for training neural network, instead of selecting from number of neurons. Addi- tionally, a key ingredient of our result is a unique amalgamation of dimension-basee and norm-based risk analysis, which may be interesting vation that an excessively large can reduce approximation error while not increasing generalization error under L1 regularizations. This implies that an explicit regularization can eliminate overfitting even when the specified number of neurons is enormous. Moreover, we prove that the L1 regulariza- tion on the input layer can induce sparsity by producing a risk bound that does not involve d, where d may be much larger compared with the true number of significant variables.
its right. The technique leads an interesting obser-
Related work on neural network analysis. Despite the practical success of neural networks, a systematic understanding of their theoretical limit remains an ongoing challenge and has motivated research from various perspectives. Cybenko (1989) showed that any continuous function could be approximated arbitrarily well by two-layer perceptron with sigmoid activation functions. Barron (1993; 1994) established an approximation error bound of using two-layer neural networks to fit arbitrary smooth functions and their statistical risk bounds. A dimension-free Rademacher com- plexity for deep ReLU neural networks was recently developed (Golowich et al., 2017; Barron & Klusowski, 2019). Based on a contraction lemma, series of norm-based complexities and their cor- responding generalization errors are developed (Neyshabur et al., 2015, and the references therein). Another perspective is to assume that the data are generated by neural network and convert its parameter estimation into a tensor decomposition problem through the score function of the known or estimated input distribution (Anandkumar al.. 2014; Janzamin et al., 2015; Ge et al., 2017; Mondelli & Montanari, 2018). Also, tight error bounds have been established recently by assuming that neural networks of parsimonious structures generate the data. In this direction, Schmidt- Hieberr (2017) proved that specific deep neural networks with few non-zero network parameters can achieve minimax rates of convergence. Bauer& Kohler (2019) developed an error bound that is free from the input dimension, by assuming generalized hierarchical interaction model.
Related work on I. regularization. The use of 7, regularization has been widely studied in linear regression problems (Hastic et al., 2009, Chapter 3). The use of Lı regularization for training neural networks has been recently advocated in deep learning practice. A prominent use of Lı regularization was to empirically sparsify weight coefficients and thus compress network that requires intensive memory usage (Cheng et al., 2017). The extension of L2 regularization to group- Li regularization (Yuan & Lin, 2006) has also been extensively used in learning various neural networks (Han et al., 2015; Zhao et al., 2015; Wen et al., 2016; Scardapane et al., 2017). Despite the above practice, the efficacy of L, regularization in neural networks deserves more theoretical study. In the context of two-layer neural networks, we will show that the 41 regularizations in the output and input layers play two different roles: the former for reducing generalization error caused by excessive neurons while the latter for sparsifying input signals in the presence of substantial redundancy. Unlike previous theoretical work, we consider the L, loss, which ranks among the most popular loss functions in, e.g., learning from ordinal data (Pedregosa et al., 2017) or imaging data (Zhao et al., 2016), and for which the statistical risk has not been studied previously. In practice, the use of L1 loss for training has been implemented in prevalent computational frameworks such as Tensorflow (Google, 2016), Pytorch (Ketkar, 2017), and Keras (Gulli & Pal, 2017).
2 PROBLEM FORMULATION
2.1 MODEL ASSUMPTION AND EVALUATION
Suppose we have n labeled observations {Z2, /=),......... where y are continuously-valued re- sponses or labels. We assume that the underlying data generating model is yı = fz,) + E, for some unknown function f.(-), where 2;'s E X dRd are independent and identically distributed,
2

---

Under review as a conference paper at ICLR 2021
Input layer
Hidden layer
Output layer
W
d2
x
a
Ag
b,
Input dimension d
Hidden dimension
Figure I: A graph showing the two-layer neural network model considered in (2).
and es's are independent and identically distributed that is symmetric at zero and
E (ef 24) S²
(1)
Here, X is bounded set that contains zero, for example {or ||0||00 M) for some constant M. Our goal is learn a regression model fn + fz(x) for prediction. The fn is obtained from the following form of neural networks
Σ aao(w] x bj) + ao:
where do, aj. by E R. W j= I,..., are parameters to estimate. We let a (ao, a1.............................. a, denote the output layer coefficients. An illustration is given Figure 1. The esti- mation is typically accomplished by minimizing the empirical risk n E Elii, (xx)). for some loss function 1(-) plus regularization term. We first consider the L1 regularization at the output layer. In particular, we search for such f by the empirical risk minimization from the function class
Fv = { S: R R S())()))))))))((
Σ aaj(w] x by) ao, ||a// S SV
==1
where V is constant. The following statistical risk measures the predictive performance of learned model f:
R(ʃ) RR (()) Ee(y,,
The loss function E(-) is petedener by data analysts, usually the L, loss defined by E(y. 9) ly 5l the L2 loss defined by f2(v. 5) (y /) Under the La loss, the risk is R() I= (z) + f(x) Jel, which nonnegative for symmetric random variables e. typical to use the same loss function for both training and evaluation.
2.2 NOTATION
Throughout the paper, variables or input dimension, the number significant input variables or sparsity level, the number of neurons (or hidden dimension), respectively. We write an 2 bn. by S ans b, O(an), if (bn/anl < for some constant for all sufficiently large n. We write x b, if an 2 b,, as well as an < b,. ((,, V) denote Gaussian distribution with mean f and covariance V. Let || /| and || denote the common L1 and L2 vector norms, respectively. Let X denote the essential support
d, k. denote the number of observations, the number of input
of X. For any vector z E dRd, we define || sup,ex |x: 2). which may or may not be infinity. If X far || < M). ||=||x is equivalent to M| Throughout the paper, fn denotes the estimated regression function with n being the number of observations.
2.3 ASSUMPTIONS AND CLASSICAL RESULTS
We introduce some technical assumptions necessary for our analysis, and state-of- the-art statistical risk bounds built through dimension-based complexity analysis.
3

---

Under review as a conference paper at ICLR 2021
Assumption 1. The activation function o-)) is bounded function the real line satisfying d (()) as x + oc and (z) + 0 as x + -00, and is L-Lipschitz for some constant L. Assumption 2. The regularization constant V is larger than 2C + fO)),, where C is any constant such that the Fourier transform of f., denoted by F, satisfies
fal [[llxF((d)) S.
(4)
Assumption ((x) approaches its limits least polynomially fast, meaning that (a(x) 1(x
0H < for all |x]] 2g where I, is polynomial of 1/E. Also, the value of _ sup, || |lx scales with n polynomially meaning that log 1 = Olog n.) as + Assumption 4. There exists constant > 0 and bounded subset S R such that P(X E 8) and infzes (x) > e. for X ~ (0..
We explain each assumption below. The above notation of C, V follow those in (Barron, 1993; 1994). Assumption specifies the class of the activation functions we consider. A specific case is the popular activation function (xx) = 1993), specifies the smoothness condition for f. ensure the approximation property of neural networks (see Theorem 2.1). In Assumption 3, the condition for w is for technical convenience. It could also be replaced with the following alternative condition: There exists a constant c such that the distribution of æ satisfies
Assumption 2, first introduced in (Barron,
sup ((oog[[w)) T x=]) < clogg) <
w:||w[||2=
for any (0. 1). Simply speaking, the input data x is not too small with high probability. This condition rather mild. For example, holds when each component function. This alternative condition ensures that for some small constant & > O and any w IR. there exists surrogate of w, E Rdd with log ||ll|| ( loge). such that
has a bounded density
(((o(w 2) - ( x)1 > e) <.
And this can be used to surrogate the assumption of w in Assumption 3 throughout the proofs in the appendix. Assumption 4 means that (-)) is not a nearly-constant function. This condition only used to bound the minimax lower bound in Theorem 3.2.
Theorem 2.1 (Approximation error bound (Barron, 1993)). Suppose that Assumptions 1, 2, 3 hold. We have
1/2 < 20
(1/
+ bn)
inf JEFv
where y denotes a probability measure on X.
{
2E 2 sup (()x) 1fx 001}.
8, inf o<e<1/2
(5)
|x|>
n is defined in Assumption 3, and defined (4).
Theorem 2.2 (Statistical risk bound (Barron, 1994)). Suppose that Assumptions hold. Then the La estimator fr in Fy satisfies (x( f=(x)] Z V2 + (rdlogn)/n. In particular, if we choose r x V //n/ (ogr)) then E (fx(x) - (z))² S V (Vdlogg)))
It known that typical parametric rate under the L2 loss is the order of Od/n)) much faster than the above result. This gap is mainly due to excessive model complexity in bounding generalization errors. We will show in Section 3 that the gap in the rate of convergence loss. Our technique will be based on the machinery of Rademacher complexity, and we bound this complexity through a joint analysis of the norm of coefficients ( (horm-based") as well as dimension of parameters ('dimension base-daa)))
be filled when using Lı
2.4 MODEL COMPLEXITY AND GENERALIZATION ERROR
The statistical risk consists of two parts. The first part is an approximation error term non-inoreatee increecsgg in the number of neurons and the second part describes generalization errors. The key issue for
4

---

Under review as a conference paper at ICLR 2021
risk analysis is to bound the second term using suitable model complexity and then tradeoff with the first term. We will develop our theory based on the following measure of complexity.
Let F denote class of functions each mapping from X to R, and 22,42..... Zn X. Following similar terminology as in (Neyshabur et al., 2015), the Rademacher complexity, or simply 'complex-
ity', of function class FF is defined by E sup In |n- E (xf(x,)); where &,, i = ..2,..., are independent symmetric Bernoulli random variables.
Lemma 2.3 (Rademacher complexity of Fv). Suppose that Assumptions 1, 3 hold. Then for the Rademacher complexity of Fv, have
Vvdlog Vn
E sup IEFv
x
(6)
The proof is included in Appendix A.I. The bound in (6) is derived from an amalgamation of dimension-based and norm-based analysis elaborated in the appendix. It is somewhat surprising that the bound does not explicitly involve the approximation error part (that depends on and n)).
This Rademacher complexity bound enables us derive tight statistical risk bounds in the following section.
MAIN RESULTS
3.1 STATISTICAL RISK BOUND FOR THE L1 REGULARIZED NETWORKS IN (3)
Theorem 3.1 (Statistical risk bound). Suppose that Assumptions 1, 2, 3 hold. Then the constrained
L1 estimator fu over Fy satisfies
R(fa) S ( VVdlogn
vn
where 8n is defined (5), and T was introduced in (1). Moreover, choosing the parameters r; large enough, we have
R(fa) V Vddlogn +
(8)
The proof is in Appendix A.2. We briefly explain main idea in deriving the risk bound (7). A standard statistical risk bound contains two parts which correspond to the approximation error and generalization error, respectively. The approximation error part in (7) is the first term, which involves the hidden dimension r and the norm of input coefficients through 7). This observation motivates us to the norm of output-layer coefficients through V and the input dimension d derive generalization error bound. In this way, the generalization error term does not involve r already used for bounding the approximation error, and thus bias-variance tradeoff through avoided. This thought leads to the generalization eттоr part in (7), which is the second term involving V and d. Its proof combines the machinery of both dimension-ber based and norm- norm-based complexity analysis. From our analysis, the error bound in Theorem 3.1 is a consequence of the 7., loss function and the employed L, regularization.
comparison with the previous result of Theorem 2.2, the bound obtained Theorem 3.1 is tight and it approaches the parametric rate / /d/n / for the d < n regime. Though we can only prove for L1 loss in this work, we conjecture that the same rate is achieved using L2 loss.
In the following, we further show that the above risk bound is minimax optimal. The minimax optimality indicates that deep neural networks with more than two layers will not perform much better than shallow neural networks when the underlying regression function belongs to Fv.
Theorem 3.2 (Minimax risk bound). Suppose that Assumptions and 4 hold, and æ x2, ... Fn (O La), then jn supjezr R(fx(z)) Z V dd/n.
iid
Here the Fy is the same one as defined in (3). All the smooth functions fa(-) that satisfy V > 2C+ (0) and (4) belong to Fv according to Theorem 2.1. The proof included in Appendix A.3.
5

---

Under review as a conference paper at ICLR 2021
3.2 ADAPTIVENESS TO THE INPUT SPARSITY
It is common to imput large dimensional signal to a neural network, while only few components are genuinely significant for prediction. For example, in environmental science, high dimensional weather signals are input for prediction while few are physically related (Shi et al., 2015). In image processing, the image label is relevant few background pixels (Han et al., 2015). In natural language processing, large number of redundant sentences sourced from Wikipedia articles are input for language prediction (Diao et al., 2019). The practice motivates our next results provide tight risk bound for neural networks whose input signals are highly sparse.
Assumption 5. There exists positive integer k S d and an index set S C (1....,d] with card(S) = k. such that f. (x) = g+ (z)) for some function g- g-(-) with probability one.
The subset S is generally unknown data analysts. Nevertheless, if know k, named the sparsity level, the risk bound could be further improved by a suitable regularization on the input coefficients. We have the following result where d replaced with in the risk bound of Theorem 3.1. Proposition 3.3. Suppose that that Assumptions 1, 2, 3, 5 hold. Suppose that fn is the L estimator over the following function class
{
{:: F: R f(x)
Σ ajo(w + by) + ao. ||a|] S sus |wyllo S kk)
Then R(fn) S (dnlog
The proof included in Appendix A.4. The above statistical risk bound is also minimax optimal according to similar argument in Theorem 3.2. From practical point of view, the above Lo constraint is usually difficult to implement, especially for a large imput dimension d. Alternatively, may impose L1 constraint instead of an Lo constraint on the input coefficients. Our next result concerned with the risk bound when the model is learned from joint regularization on the output and input layers. For technical convenience, we will assume that X a bounded set.
Theorem 3.4. Consider the following function class of two-layer neural networks
Fv. { S: -
5(x) Ee (w x + b,) + ao, |aa| VV sup (1w,ll + 1b5l) S Snj 1555
j=1
Suppose that V 2 C. where C is defined in (4). Then the constrained In estimator fn over Fv. satisfies
R(fa) S C ( +
Vn++
VT
where 8n is defined in (5). In particular, choosing large enough, we have
R(fn)) S Co + Vn+T
Vn. which does not involve the input dimension d and the number of hidden neurons r. Moreover, 1/3
suppose that (x) = +) n= (n (nlo""
,then R(fa) S ((ogmn)mn)
The proof is included in Appendix A.5. In the above result, the risk bound is at the order of O(n Onn-),3), which is slower than the Onn-1/2) in the previous Theorem 3.1 and Proposition 3.3 ignoring d and logarithmic factors of n. However, for a large input dimension that is even much larger than n, the bound can be much tighter than the previous bounds since it dimension-free
4 CONCLUSION AND FURTHER REMARKS
We studied the tradeoff between model complexity and statistical risk in two-layer neural networks from the explicit regularization perspective. We end our paper with two future problems. First, in Theorem 3.4, For small d, the order of - seems be an artifact resulting from our technical arguments. We conjecture that in the small d regime, this risk bound could be improved to O122 by certain adaptive regularizations. Second, it would be interesting to emulate the current approach to yield similarly tight risk bounds for deep forward neural networks.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. J. Mach. Learn. Res., 15:2773-2832, 2014.
Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Trans. Inf. Theory, 39(3):330999 1993.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 15-331, 1994.
Andrew R Barron and Jason M Klusowski. Complexity, statistical risk, and metric entropy of deep nets using total path variation. arXiv preprint 1902:00900000000 2019.
Benedikt Bauer and Michael Kohler. On deep learning as a remedy for the curse of dimensionality in nonparametric regression. Ann. Star., 47(4))2261-22 2019.
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. survey of model compression and acceleration for deep neural networks. arXiv preprint arXiv: 2017.
George Cybenko. Approximations by superpositions of sigmoidal function. Math. Control Signals Syst., 2:183-192, 1989.
Enmao Diao, Jie Ding, and Vahid Tarokh. Restricted recurrent neural networks. 2019 IEEE Conf. on Big Data, 2019.
Jie Ding, Vahid Tarokh, and Yuhong Yang. Model selection techniques: An overview. IEEE Signal Process. Mag., 35(6):16-34 2018.
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. arXiv preprint arXiv:1711.00501. 2017.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint arXiv: 2017.
Research Team Google. Tensorflow: A system for large-scale machine learning. Proc. 12th Symp. Operating Syst. Des. Implementation, pp. 265-283, 2016.
Antonio Gulli and Sujit Pal. Deep Learning with Keras. Packt Publishing Ltd, 2017.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advance. Neural Inf. Process. Sys., pp. 1135-1143, 2015.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity: Guar- anteed training of neural networks using tensor methods. arXiv preprint arXiv: 001.555060.333 08473, 2015.
Nikhil Ketkar. Introduction to pytorch. Deep learning with python, pp. 195-208, 2017.
Marco Mondelli and Andrea Montanari. On the connection between learning two-layers neural networks and tensor decomposition. arXiv preprint 1rXiv:180.007301, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. Conf. Learning Theory, pp. 1376-1401, 2015.
Fabian Pedregosa, Francis Bach, and Alexandre Gramfort. On the consistency of ordinal regression methods. J. Mach. Learn. Res., 1869):1799-180,, 2017.
Simone Scardapane, Danilo Comminiello, Amir Hussain, and Aurelio Uncini. Group sparse regu- larization for deep neural networks. Neuroconputing, 241:81-89, 2017.
Johannes Schmidt- Hiebber. Nonparametric regression using deep neural networks with relu activation function. arXiv preprint arXiv: 066333 2017.

---

Under review as a conference paper at ICLR 2021
George AF Seber and Alan J Lee. Linear regression analysis, volume 329. John Wiley & Sons, 2012.
Xingjian Shi, Zhourong Chen, Hao Wang, Dit- Yan Yeung, Wai-kin Wong, and Wang-chun Woo. Convolutional LSTM network: A machine learning approach for precipitation nowcasting. In Advance. Neural Inf. Process. Sys., pp. 802-810, 2015.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advance. Neural Inf. Process. Sys., pp. 2074 2074-2082, 2016.
Yuhong Yang and Andrew Barron. Information-theorrti determination of minimax rates of conver- gence. Ann. Stat., pp- 1564-1599, 1999.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. R. Stat. Soc. Ser. B Methodol., 68(1):49-6)) 2006.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16 2016.
Hang Zhao, Orazio Gallo, luri Frosio, and Jan Kautz. Loss functions for image restoration with neural networks. IEEE Trans. Comput., 3(1):47-57, 2016.
Lei Zhao, Qinghua Hu, and Wenwu Wang. Heterogeneous feature selection with multi modal deep neural networks and sparse group LASSO. IEEE Trans. Multimed,, 17(11):1936-11 2015.
A APPENDIX
A. PROOF OF LEMMA 2.3
We first prove (6), which uses an amalgamation of dimension-based and norm-based analysis. For the output layer, we use the following norm-based analysis
sup IEFv
Σ ()((Z)) 72
= sup Ka, FEFv
1
Σ
(w 2, + b))l
(9)
1=1
1=1
n
n Go(wy 21 1 bi)
suppla/iiB Jeīv
sup
So (
2i b)
S VE
sup max JEFv
n1
VE sup WERd
Σ Loww + b)
For notational convenience, we define wip 0, bo 0, and ag -000-1a00 = + bo) so that ag can be treated in similar manner other as's. Without loss of generality, we do not separately consider ag in the following proofs.
Next, we prove that
sup wERd
Σ
(
T 2, + 6)
$
d log
(10)
n
and thus conclude the proof. The proof will be based on an e-net argument together with the union bound. For any e, let W. C IRd denote the subset
(i,, i2 ia) : E E, || S mm }
We
w
2d
Then, for any w. there exists some element E W. such that
sup (w 2 + b) ovo z + i) zex
< sup (w T z + b) (vo T z + ر) < sup (w ú) 2| + 1--
< ||ll àt 1 sup || 1o0 + i1 ss
8

---

Under review as a conference paper at ICLR 2021
where b (e/2d) [2db/=)] and [-] is the floor function. By Bernstein's 's Inequality, for any w,
nt² 2(1 + 1/3) S
Σ (o
TwuTa 2, + 6)] >1) S 2exp
By taking the union bound over Wr, and use the fact that log card(W.)) S d dloo(nd/e), we obtain
1
Golw" 2; b) S V d log
nd log 8'
sup weRd
72 ==1
E
with probability at least Then the desired result is obtained by taking e ~ (ddlogn)/n.
A.2 PROOF OF THEOREM 3.1
The proof is based on the following contraction lemma used in (Neyshabur et al., 2015).
Lemma A.1 (Contraction Lemma). Suppose that g is L-Lipschitz and g(0) = O. Then for any function class F mapping from X. to le and any set (21, 2:22----0 -., Fnn, we have
Σ Eg((((s))) t=1
1
Eet((s))
E sup
S 2LE sup
(11)
SEF
SEF n2 1=1
With the above lemma, we have the following result.
Lemma A.2. The constrained Ln estimator In over F satisfies
R(fx) S min
min E -.)o + 2E sup 1 (((())))21
E
(12)
fer
JEF 1=1
Proof. Define the empirical risk as:
RT) = EE 2 [f. - =f(ail))))) -Ele
(13)
1=1
Since fn minimizes n -1 Σi= [fa (2x) + - f(x;)] in F, we have
R(fa) - R(f,) {R,, (fr) - Rn,(f) = (R(f)) - (n.(f + R, (fo).
(14)
where fo = arg min R()). We also have
R.((f)) Rfoo = min (lf. + E - fxxx) - (E|) s min [f(x) fa(2).
(15)
JEF
feF
In the following, we will analyze the term R(fn) Rn(( in (14). Let 2,'s 's denote independent and identically distributed copies of xz
R(fm) -n)(fa) =
- (a(())) - - (fa - fa(z;) Esl
< E sup fer
[f(x.) - fa(()) - -al 1f((x) fa(xs) - -Eal
1 Σ (lf(zz)) fl(2)) -ss
< 2E sup /EF 11
where Ei...., En are independent and identically distributed symmetric Bernoulli random variables that are independent with z; 's. According to Lemma A.1, since g(x) = |>| is 1-Lipschitz and g(0) 0, we have
sup - (x(x)) -aal < 2E sup feF 1m1
-(((z.)) - (z(z)) - -t:)
fEF
1
Ey²
< 2E sup FEF
fz(()))
+ +2
n
n
Combining this and (15), conclude the proof of Lemma A.2.
9

---

Under review as a conference paper at ICLR 2021
Proof of Theorem 3.1. The proof of (7) is direct consequence of Lemma 2.3, Lemma A.2, Theorem 2.1 and the fact that the first moment no more than the second moment. The proof of (8) follows from the fact that (() + 0 7 -
A.3 PROOF OF THEOREM 3.2
Define subclass of Fv by
Fo = f R. f((()) Vo(w" 2), 1owlll - =
In the following, we will prove the minimax bound for Fv by analyzing Fo. Notice that
E [o x) o (w) 2) 2 E inf o' o'(u)- |w] = æ I[ww] w x S) Z || -w
w2ll2.
Let (e) denote the packing e-entropy of Fo with L, distance, then (e) is greater than the packing e-entropy of Bf with L2 distance, which means Mi Z Let Vi((s) denote the covering e-entropy of Fo with the square root Kullback-Leibhe divergence, then according to its relation with the L2 distance shown in (Yang & Barron, 1999), we have
Vi(e) S M2(v2s) S dllog 1 T
where M2(e) denote the packing e-entropy of Fv with L2 loss function. The second inequality is proved in a similar way to the proof of Lemma 2.3, which is omitted here for brevity. Hence, according to (Yang & Barron, 1999, Theorem 1),
d
inf sup R(fx(z)) 2 inf sup R(f((s)) 2 VV fn fEFo
fn feFv
This concludes the proof.
A.4 PROOF OF PROPOSITION 3.3
To prove the proposition, sufficient to verify the following Rademacher complexity bound
E sup Σ (oow T 2; + b) z / log d dlogg.
which be derived easily by adjusting the proof in Lemma 2.3. Then the result follows with similar analysis as in Theorem 3.1.
A.5 PROOF OF THEOREM 3.4
can be verified from the identity (9) that
E sup Σ (.f())) JeAv 1=1
sup fEfv
la
( x, +b))
(16)
==
1=1
Then according to Lemma A.1, we have
E
sup JEFv
1
Σ (o x, bb)
<
log n (1wy + (b,l).
(17)
n
Combining (16) and (17), we obtain the following lemma that may be interesting on its own right.
Lemma A.3. We have
log [a + (b,l) 1b.) SVV
llgg n max || llx.
E sup JEFv
Σ Ef(()))
$
1=0
Since ||lllx ||10|a and {w || I n/} {w ||w||| S 7) the || llx be replaced with || II in the bounds Lemmas A.3 and A.2. Then, with a similar argument as in the proof of Theorem 3.1, conclude the proof of Theorem 3.4.
10


Reviews:
[{"review_id": "Wuap3M5xMd", "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 generalization bounds for neural networks with the following kind of setup:\n(0) 1 hidden layer and sigmoid-like activations. the weights in the input layer are bounded in either a general norm, or sometimes specifically the $\\ell_1$-norm.\n(1) the loss function is the L1 loss |y - \\hat{y}|, as opposed to the more common square loss.\n(2) the weights of the last layer of the network are bounded in the vector $\\ell_1$-norm. They also consider the case where the input layer is bounded in Sec 3.2.\n\nA small notational point: the authors use L1 to denote both cases, i.e. write L1 instead of $\\ell_1$ to denote the vector $\\ell_1$-norm\nof the weights (i.e. the sum of absolute values). Sometimes I do see the vector norm written L1 anyway, as in this paper. However, the vector norm is more commonly written as $\\ell_1$, and I think this would be a good idea to minimize confusion between (1) and (2) above, which are very different things. (E.g. In the linear regression world, the $\\ell_1$-norm is associated with sparsity and $L_1$ loss is associated with robustness to outliers.)\n\nThe main result of this paper is a generalization bound for this class of neural networks, which comes down to technical Lemma 2.3 bounding the Rademacher complexity of the class. This result follows in a relatively straightforward way, because L1 loss is lipschitz (so we can use contraction lemma) and because all of the weights are bounded in $\\ell_1$ norm; a small twist is they use that the input dimension is small to get a better bound on the term coming from the first layer of the network. They also state a result given by combining this generalization bound with Barron's approximation theorem.\n\nIt would be useful for the authors to compare their results further with previous work in this area. In particular, the idea of looking at the $\\ell_1$ norm of the output layer for generalization bounds has been considered as part of 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\", Bartlett '98. See e.g. Theorem 17.\n\nOverall, this paper doesn't seem to contribute many fresh ideas to the study of generalization bounds for neural networks and so I would tend towards rejection.\n\nminor notes:\n- contraction lemma & rademacher complexity are basic results in this area, so preferably they shouldn't be cited from neyshabur et al (2015). For example, you could cite a textbook in the area, like Shalev-Shwartz + Ben-David book.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QkKj7eV3fY", "reviewer": "AnonReviewer3", "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": "1. Summarize what the paper claims to contribute.\n\nThe paper bounds the excess L1 risk of two-layer neural networks when L1 regularization is applied to the second layer. The rates obtained are better than the rates with L2 risk and nearly optimal. Crucially, the L1 regularization removes the size of the hidden layer from the estimation error. \n\n2. List strong and weak points of the paper.\n\nPros:\n* The lower and upper bounds in the paper are almost matching. \n* The discussion of the assumptions and results are clear and informative. I'm quite happy about this.\n* The paper is overall clearly written and correctly executed (modulo minor issues that can be fixed).\n\nCons:\n* The contributions have limited impact.\n\n3. Clearly state your recommendation (accept or reject) with one or two key reasons for this choice.\n\nUnfortunately I am recommending rejection. The paper is well written and well executed, but I am concerned that the contributions are few and that their impact is limited.\n\n4. Provide supporting arguments for your recommendation.\n\nConcerns:\n* Limiting the setting to two-layer neural networks and excluding common activations like ReLU limits the impact of the results.\n* The paper applies existing results/analyses to a new setting (combining neural networks and L1 regularization). This setting does not pose any particular technical challenge. The findings are interesting but few, in my opinion. It is unclear whether they are enough for acceptance.\n\n5. Ask questions you would like answered by the authors to help you clarify your understanding of the paper and provide the additional evidence you need to be confident in your assessment.\n\nImportant questions/requests:\n* Please clarify the significance of the contributions, and their potential impact.\n* If the papers address a new technical challenge, please clarify.\n* Are they widely applicable as they are? \n* Has the paper opened up a path for future research to use the knowledge contributed, and to make the results more broadly applicable?\n\nTangential questions:\n* Assumption 2 seems to include the assumption \"our choice of V is appropriate\". So one does not need to do model selection on V. The results remove r and introduce V into the estimation error, but is V easier to choose than r? \n\n6. Provide additional feedback with the aim to improve the paper.\n\nThe paper uses Bernoulli random variables for the Rademacher complexity, but they should be Rademacher random variables (see Appendix A in Neyshabur et al., 2015).\n\n(5) makes me wonder whether most of the error happens around zero, and whether easy cases are significantly easier\n\n7. Typos/Minor questions\n\nFor eta in Assumption 3, should there be a sup over w?\nIn the definition of eta, maybe write \\log \\eta \\asymp \\log n ?\n\nWhat's the randomness inside the P in the alternative definition of Assumption 3? I'm assuming it's X, based on the explanation that follows the equation.\n\nThe quantifiers in Thm 3.2 look strange, but I think it's because in the original result the \\hat{\\theta} (mapped to \\hat{f}_n here) refers to the estimator and not the actual empirical minimizer. Could you please clarify the notation here?\n\nFor Assumption 5, I was wondering if you wouldn't want a sparse latent representation instead? I think the case where the inputs are actually sparse is not usual, but the case where you can learn a sparse representation at least from an empirical perspective seems more realistic.\n\np.8 typo in definition of a_0\n\nSigma's Lipschitz constant is missing from the derivation (first step to second) at the bottom of p.8. The derivations following that are missing some constants. Also, please cite sources for Bernstein's Inequality and the covering number of W_eps.\n\n(14): \\hat{f} -> f_0\n\nIn the equations following (15) for that derivation it would be useful to add how the second term (with y^2) came to be.", "extra_scores": {}, "extra_text": {}}, {"review_id": "B7ciORjgaLi", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the statistical risk bounds for two-layer neural networks with $L_1$-regularization. The authors consider two types of $L_1$-regularization: the $L_1$-regularization on output layer and the $L_1$-regularization on the input layer. For the $L_1$-regularization on output layer, the authors develop nearly minimax statistical risk bounds. For the $L_1$-regularization on input layers, the authors develop bounds with no-dependency on the input dimension. The paper is clearly written and easy to follow.\n\nComments\n\n1. This is a theory paper. However, as far as I can see, theoretical analysis is a bit standard. It seems that the authors do not introduce new techniques and idea in statistical learning theory (SLT). Furthermore, the results are a bit standard. For example, the statistical risk bound of the order $\\sqrt{d/n}$ in Thm 3.1 is standard in SLT for general machine learning models. It is not surprising that this holds for two-layer neural networks.\n\n2. In my opinion, eq (10) is not correct. Since there is no constraints on $w$, the left-hand side can be infinity by taking $w$ of infinite magnitude. Therefore, I think one should also imposes a constraint on $w$ in the definition of $F_v$ in eq (13)\n\n3. In the definition of $F_{v,\\eta}$ in Thm 3.4, there is a constraint on $w$. I think this constraint may affect the approximation error established in Thm 2.1. Then this can further affect the statistical risk in Thm 3.4.\n\n4. Eq (17) should be not correct. Indeed, the left-hand side depends on a function class, while the right-hand side depends on $w_j$ and $b_j$. This is not meaningful.\n\n5. In eq (14), $\\hat{f}$ should be $f_0$", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a generalization bounds for l1 regularized networks.  The reviewers thought the results were clear and sound, but on the other hand rely on rather standard technical tools, and their impact is limited.
One question is why this particular regularization is related to practical learning of neural nets where explicit regularization is not used. The authors may want to relate their results to e.g., Theorem 1 in https://arxiv.org/pdf/1412.6614.pdf.
 
Decision: Reject