On Measuring Excess Capacity in Neural Networks
Authors: Florian Graf
Sebastian Zeng
Bastian Rieck
Marc Niethammer
Roland Kwitt
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep learning theory
Rademacher complexity
Residual networks
Convolutions
Excess capacity

Abstract: We study the excess capacity of deep networks in the context of supervised classification. That is, given a capacity measure of the underlying hypothesis class - in our case, empirical Rademacher complexity - to what extent can we (a priori) constrain this class while retaining an empirical error on a par with the unconstrained regime? To assess excess capacity in modern architectures (such as residual networks), we extend and unify prior Rademacher complexity bounds to accommodate function composition and addition, as well as the structure of convolutions. The capacity-driving terms in our bounds are the Lipschitz constants of the layers and a (2,1) group norm distance to the initializations of the convolution weights. Experiments on benchmark datasets of varying task difficulty indicate that (1) there is a substantial amount of excess capacity per task, and (2) capacity can be kept at a surprisingly similar level across tasks. Overall, this suggests a notion of compressibility with respect to weight norms, complementary to classic compression via weight pruning. Source code is available at https://github.com/rkwitt/excess_capacity.

On Measuring Excess Capacity in Neural Networks
Florian Graf
Sebastian Zeng University of Salzburg sebastian.. sebastian.zeng@p.ll zeng@plus ac at
Bastian Rieck
University of Salzburg florian. graf@plus ac.at
Institute for and Health Helmholtz Munich
bastian@rieck me
Mare Niethammer
Roland Kwitt
UNC Chapel Hill mn@cs. unc edu
University of Salzburg roland kwitt@plus ac at
Abstract
We study the excess capacity of deep networks in the context of supervised classifi- cation. That is, given a capacity measure of the underlying hypothesis class - in our case, empirical Rademacher complexity
what extent can (a priori) constrain this class while retaining an empirical error on par with the unconstrained regime? To assess excess capacity in modern architectures (such residual networks), we extend and unify prior Rademacher complexity bounds to accommodate function composition and addition, as well as the structure of convolutions. The capacity- driving terms in our bounds are the Lipschitz constants of the layers and an (2, 1) group distance the initializations of the convolution weights. Experiments on benchmark datasets of varying task difficulty indicate that (I) there is substan- tial amount of excess capacity per task, and (2) capacity can be kept at surprisingly similar level across tasks. Overall, this suggests a notion of compressibility with respect to weight norms, complementary to classic compression via weight pruning. Source code is available at https: //github com/ www/cwwwttttteeeeeoooooooowowwoe
capacity.
Introduction
Understanding the generalization behavior of deep networks in supervised classification is still largely open problem, despite long history of theoretical advances. The observation that (over- parametrized) models can easily fit-i.e., reach zero training error-to randomly permuted training labels [45, 46] but, when trained on unpermuted labels, yield good generalization performance, has fueled much of the progress in this area. Recent works range from relating generalization to weight norms [3, 14. 26. 37, 38], measures of the distance initializations [34], implicit regularization induced by the optimization algorithm [8, 41], or model compression [2, 6, 42]. Other works study connections to optimal transport [9], generalization in the neural tangent kernel setting [1, 23).
When seeking to establish generalization guarantees within the classic uniform convergence regime, bounding capacity measure, such as the Rademacher complexity [4], of the hypothesis class is the crucial step. While the resultant generalization bounds are typically vacuous and can exhibit concerning behavior [36], the capacity bounds themselves offer invaluable insights through the behavior of the bound-driving quantities, such as various types of weight norms or Lipschitz constants.
Particularly relevant to work is the observation that the bound-driving quantities tend to increase with task difficulty. Fig. illustrates this behavior terms Lipschitz constants per layer and the dis- tance of each layer's weight to its initialization (measured via group norm we develop in Section 3.1).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

This raises two immediate questions: First (Q1), can a network maintain empirical testing performance a substantially lower capacity? Second (Q2). is the level of this lowered capacity inevitably tied to task difficulty, i.e., would reduced-capacity model for an easy task fail on a difficult task? Both of these questions aim at the amount of "unneeded" capacity, which we refer to as excess capacity in the remainder of this work.
Taay Imogemett 200 (hard)
CIFARIOI (mediaum)
CIFARIO 1D (eary)
10'
10e
(2.1) group distance initializaaion
Figure 1: I Layerwise Lipschitz constants and dis- tance initialization of ResNet18 model (see Section 4), trained on different datasets.
We will address questions (Q1) and (Q2) by means
of controlling the empirical Rademacher complexity of neural network. To this end, we consolidate and extend prior results from the literature on Rademacher complexity bounds to accommodate a broad range of network components in a unified way, including convolutions and skip connections, two ubiquitous elements in fate-of-the-an models.
Our contributions can be summarized as follows:
1. We establish two bounds (in Theorem 3.5) for the empirical Rademacher complexity of neural networks that use convolutions and implement functions built from composition and addition. Specifically, we introduce two novel, convolution-specifi,, single-layer covering number bounds in Section 3.2 and contrast them to prior art, then modularize the single-layer multi-layer covering approach of Bartlett et al. [3] in Section 3.3, and eventually present one incarnation of our framework for convolutional residual networks in Sections 3.4 and 3.5.
2. We present an extensive set of experiments (in Section 4) with a ResNet18 model across benchmark datasets of varying task difficulty, demonstrating that model capacity, when measured via our weight norm based bound, (1) can be kept surprisingly small per task, and (2) can be kept at roughly the same level regardless of task difficulty. Both observations suggest compressibility of neural networks with respect weight norms, complementary the well-known compressibility property of neural networks with respect to the number of parameters [2, 42].
2 Related Work
Many prior works establish uniform--convergenc type generalization bounds for neural networks through Rademacher complexity analysis. We review such approaches, highlighting challenges that arise with modern network architectures and the peculiarities of convolutional layers.
One direct approach to bound the empirical Rademacher complexity via a layer-peeling strategy [14, 38, 44] where the Rademacher complexity of L-layer networks is expressed by factor times the Rademacher complexity of (L- - 1) llyeer networks; in other words, the last layer is peeled off. This factor is typically matrix (p, 9) group norm, and thus the bounds usually scale with the product of the latter. Notably, the nonlincarities need to be element-wii wise operations, and some approaches only work for specific nonlinearities, such as ReLUs asymmetric activations. A second strategy is to bound the empirical Rademacher complexity via a covering numbers approach [3, 26, 29, 47]. typically achieved via Dudley's entropy integral [11], This strategy is partieularly flexible as it allows for arbitrary (but fixed) nonlinearities and various paths to bounding covering numbers of network parts, e.g., via Maurey's sparsification lemma or via parameter counting. The corresponding whole-network bounds typically scale with the product of each layer's Lipschitz constant or local empirical estimates thereof [43]. Irrespective of the particular proof strategy, most formal arguments only hold for neural networks constructed from function composition, i.e., maps of the form
where 0, : 1 + dd are nonlinearities and A, are weight matrices specifying the i-th linear map. However, modern architectures often rely on operations specifically tailored to the data, such as convolutions, and typically incorporate skip connections as in residual networks [20], rendering many results inapplicable suboptimal for such models. In this work, handle convolutions and skip connections, thus increasing the applicability and utility of such bounds.
For example, while residual networks have been studied extensively, theory mostly focuses on expressivity or optimization aspects [3, 18, 28, 44]. Yun et al. [44] provide Rademacher complexity bound via peeerng for fully-connected layers and element-wise activations. He et al. [19]

---

Product of ||-] norms
Product of [1 norms
Product of Lipschitz constants
Number of parameters
Gook al. [16]
Golowich et al. [14]
Neyshabur
Gouk al. [16]
layor-poeling
1,00
Golowich al. [14]
1,000
Neyshabur
[38]
Lin al. [29]
Ours, Theorem 3.5
Ledent et ul. (fined construints)
Ledent
resulr)
covering numbers
Bartlett et al.
[3]
Ours, Theorem 3.5
10
10
10a
10
Figure 2: Empirical Rademacher complexity bounds (grouped by proof strategy; lower is better), for 6- (M and an 11 11-layer () convolutional network, trained on CIFARIO. Bounds are listed in Section A.2 and quantities that typically appear in these bounds are highlighted in green (top part of figure) for reference.
establish a generalization bound for residual networks via covering number arguments, resting upon earlier work by Bartlett al. [3] for linear maps. However, when directly applied to convolutions, both bounds scale unfavorably w.r.t. the spatial input size (see Section 3.2). Other works provide generalization guarantees specifically tailored convolutional networks, ef. [16, 26, 29, 31], and, although such bounds scale benignly with input size, they only apply for models as in Eq. (1).
An initial numerical comparison. Bounds the empirical Rademacher complexity differ in their dependence on various quantities, such as matrix (p, 4) group norms, Lipschitz constants, or the number of parameters. Thus, precise formal comparison is challenging and, depending the setting, different bounds may be preferable. To provide some intuition about magnitude differences, evaluated several existing bounds (including from Section 3.5) two convolutional (ReLU) networks with and 11 layers, see Fig. and Section A.2 for details.
Rademacher Complexity Analysis
To derive bounds on empirical Rademacher complexity, we follow the margin-based multiclass learning formalism and the flexible proof strategy of Bartlett et al. [3]. Section 3.2 introduces novel single-layer covering number bounds for convolutions. Section 3.3 modularizes and extends the single- to multi-layer covering step to account for architectures such residual networks (Section 3.4). Last, Scction 3.5 presents and discusses our Rademacher complexity bounds.
3.1 Preliminaries
In a r-class classification task, we are given instance/label pairs S = ((11,81).... B1..... (Zn )) drawn iid from a probability measure on Rd x (I,....,k) For neural network f in a hypothesis class C. {f: Rd + }. a class label for input æ is obtained by taking the argmax over the components of f(x) T The margin operator M: RR* (1,...,,, + R. (v, vy mymayy U
leads, with margin 7 > O, to the ramp loss ey and the empirical ramp risk Re, defined
R r
1.30 and R, Σ (-M((((a))))) (2)
To derive generalization bounds via classical Rademacher complexity analysis [33], without having resort vector-contraction inequalities [32], we consider the hypothesis class
F, = (x, v) - (,-M : F)
Then, defining the empirical Rademacher complexity of any class H real-valuee functions as
ft = E sup NEW T2
o oz 91)
1=1
with iid Rademacher variables a (01,... an) from uniform distribution on (+1), facilitates to
study F,, via Eq. (4). The following lemma [3, Lemma 3.1] establishes the link to a margin- multiclass generalization bound for any f F.
3

---

Lemma 3.1. Given hypothesis class F of functions f: RR - RR" and margin parameter > 0,
then, with probability of least 8 over the choice of S DD" for any f F, holds that
log (3) 2n
IP[ arg max f(x); + v) R, + 29 (F₂) +3 ()........
To obtain computable expression for the right-hand side of Lemma 3.1, seek a bound on Rg(F, tied to some measurable quantities of the network realizing F. For our purposes, the relationship of (F,) and the covering number of F, turns out to be flexible approach. In general, given a normed space (9. ll-llg), the covering number Nig, & ll-lll)) ) is the cardinality of the smallest c-cover of G, i.e., of the smallest subset U C 9 such that, for any llg - - S e. In our setting, 9 is a class of functions g : (X, I1-Ilx) (V/, Il-lly) between normed spaces X' and y. Given data X (Z1, (z1....,ffr) Fn) E X", we define data dependennndent norm on gIx as
G, there exists u E l with
|1allx = v / |l(():)13
(6)
In other words, Eq. (6) is the 2/ norm on the restriction of G to X. Specifically, seek to bound (J,, (F,,,,, c, |l-,,s), as this facilitates to control the empirical Rademacher complexity of F, by means of Dudley's 's entropy integral. Typically, such covering number bounds depend on the norm of the data itself, i.e., || VIn 1 1.
3.2 Covering number bounds for convolutions
We consider 2D convolutions, acting on images with Can channels of width w and height h, i.e., E R For readability only, we discuss convolutions of stride and input-size preserving padding; this is not an assumption required for Theorem 3.2. Formally, a convolutional layer is a linear map Φx: Raaxxx + xhx (as we omit bias parameters), where Can and Cour denote the number of input and output channels. The map is parametrized by a tensor K RS X X xk of spatial extension/kernel size (kn, kw.). Since convolutions are linear maps, they can be specified by matrices which act on the (reshaped) inputs and one could invoke existing covering number bounds. However, this is suboptimal, as any structure specific to convolutions is ignored. In particular, norm- based gencralization bounds agnostic to this structure incur unfavorable scaling behavior w.r.t. the dimensionality of the input. To be more specific, the weight tensor K of convolutional layer does not directly specify the corresponding matrix; instead, it parametrizes Cour filters, i.e., local linear maps, which are applied to the (Gm x k2 x - pixel neighborhoods of the input. Hence, the matrix Mx x corresponding to the global linear map consists of many copies of the elements of this tensor, one for each of the hwo patches the filters are applied to. Thus, the I norm of the matrix Mr || Il, = (hw) /p || | Il, (see Section A.1). We mitigate this scaling issue by tying the covering number of a convolutional layer variant of the (2.1) group norm on the tensor K itself. We define this norm as the sum over the le norms taken along the imput channels of K, i.c.
K 1K11,
= Σ | [Kaull22 = =Σ cke
Σ ThI 3
Kij
For the special case of inputs of size (h, w) = (1, 1) and kernel size (kn, kw) = (1, 1), convolution is just matrix multiplication along the channels. In this case, Mr = K..1 and our norm from Eq. (7) agrees with the standard (2, 1) group norm on MT, i.e., | = | Theorem 3.2 establishes two covering number bounds for convolutions.
denote the class of 2D Theorem 3.2. Let b 0 and F {Φx| K Krow Xkw, |K] S
convolutions with Cia input channels, Cou output channels and kernel size k2 xk parametrized by tensors K with W = Co kew parameters. Then, for any X E IR" x x hxx w and covering radius >>0 0,
X 1222
log(2W)
(8a)
2²
|
82
2W log
1+
(8b)
2²

---

Eq. (8a) is analogous to the single-layer bound of Bartlett et al. [3, Lemma 3.2] for fully-connected layers, but replaces the (2, 1) group norm constraint on matrices M T with constraint on tensors K. This is tighter than invoking [3. Lemma 3.2] directly on MR E IR X Cauhw, as K" has only CourCn ke parameters and || 2| 2 / || || 1 see Section A.1. A thorough comparison between the two bounds in Theorem 3.2 is nuanced, though, as preferring one over the other depends on the ratio between the number of parameters W and || b² /22 The latter, in turn, requires to consider all covering radii e. Hence, we defer this discussion to Section 3.5, where differences manifest more clearly the overall empirical Rademacher complexity bounds.
Proof sketch. The statement of Theorem 3.2 follows from an application of Maurey's ' sparsification lemma, which guarantees the existence of an e-cover of F (of known cardinality) if there is a finite subset {Vi,.... Va} C F s.t. every f E F is convex combination of the V,. We show that one can find such a finite subset of cardinality determined by combinatorial quantity which additionally depends on || and the norm constraint b. Bounding this quantity, i.e., a binomial coefficient, in two different ways, establishes the bounds.
Cou ki = 2W. The cardinality of the cover is then
Relation to prior work. Closely related is recent work by Ledent et al. [26] who derive lee covering number bounds for convolutional layers based on a classic result by Zhang [47]. Similar to Eq. (8a), their bound depends on the square of weight norm directly on the tensor K, the square a data norm, as well as logarithmic term. The data norm is the maximal l2 norm of a single patch. Compared to our result, this implicitly removes a factor of the spatial dimension lw.. However, when transitioning to multi-layer bounds, this factor reenters in the form of the spatial dimension of the output (after subsequent pooling) via the Lipschitz constant. Overall, the quadratic terms across both results scale similarly (with our data norm being less sensitive to outliers), but we improve on Ledent et al. [26] in the logarithmic term. By contrast, the use of loc covers in [26] yields whole-network bounds with the number of classes; see Section A.6 for in-depth comparison. In other related work, Lin et al. [29] derive an l2 covering number bound for convolutional layers similar to Eq. (8b), which depends linearly on the number of parameters and logarithmically on norms. In their proof, Lin et al. [29] show that every cover of a convolutional layer's weight space (a subset of Euclidean space) induces cover of the corresponding function space w.r.t. the data dependent norm defined in Eq. (6). However, their approach incurs an additional factor inside the logarithm that corresponds to the number of how often each filter is applied, i.c., the spatial dimension of the output. Importantly, non-convolution specific approaches can equally mitigate undesirable scaling issues, e.g.. by utilizing (I, oo) group norms on the matrices representing the linear map [14, 16, 38]; as differences primarily manifest in the resulting bounds on the Rademacher complexity, we refer to our discussion in Section 3.5.
improved dependency
3.3 Covering number bounds for composition & addition
As many neural networks are built from composition and summation of layers, study covering numbers under these operations. The key building blocks are the following, easy to verify, inequalities.
Lemma 3.3. Let F1, be classes of functions on normed spaces (X' 11-1x)))x) + (11.1-lly) and let G be a class of c-Lipschitz functions (2), (111 11-11z). Then, for any X E x and ex, Eg > 0. it holds that
W(1h + f2 f E.
l+xx) (9)
and
MllooflgE FFG + tes, Fgh.eg
Ex,, & sup E (10)
JeF,
To establish these inequalities, one chooses minimal covers of the original function spaces and links their elements via the considered operation, i.e., addition or composition. The resulting functions correspond to tuples of elements of the original covers. Hence, the right-hand side of the inequalities a product of covering numbers. The crucial step is to determine a preferably small radius e such that these functions form an e-cover. In Lemma 3.3, this is achieved via standard properties of norms. Notably, iterative application of Lemma 3.3 allows bounding the covering numbers of any function class built from compositions and additions of simpler classes.
5

---

In Section C.3, we apply Lemma 3.3 on two examples, i.e., (1) F == o...o f and (2) H. {g + hr, o...o }1}. Instantiating the first example for o, o oi with o; fixed and d from a family of linear maps, yields covering number bounds for networks as in Eq. (1). As the second example corresponds to residual blocks (with g possibly the identity map), the combination of (1) and (2) yields covering number bounds for residual networks; see Example C.3.
Overall, this strategy not only allows to derive covering number bounds for broad range of architectures, but also facilitates integrating linkings between function spaces in a modular way. For instance, Lemma C.14 provides a variant of Lemma 3.3 for concatenation, used in DenseNets [22].
Relation to prior work. He et al. [19] investigate covering number bounds for function spaces considered above. They present covering number bounds for residual networks and show that the covering number WNF, e, II-1| x) of such models with layers Fo is bounded by the product II. supseg. MV.F,, EF_ (x)) ) for appropriately defined function spaces G.. Yet, the dependency of the whole-network covering radius e on the single-layer covering radii c,F, only derived for very specific residual network. Our addition to the theory is more modular and structured way of approaching the problem, which we believe be valuable on its own.
3.4 Covering number bounds for residual networks
We next state our whole-network covering number bounds for residual networks and then present the corresponding bounds on the empirical Rademacher complexity in Section 3.5. Accompanying generalization guarantees (obtained via Lemma 3.1) are given in Section C.5. The results of this section hold for hypothesis class F of networks implementing functions of the form
f = L o fr o ................................ o 01 o /1 with fa(x) = 9: (x) + (MLL, o hir, o... 0a o ha)(z) (11)
i.e., composition of L residual blocks. Here, the nonlinearities σ; and Øi are fixed and pi-, resp.. Psy Psy-Lipschitz continuous with (0) = O and oig (0) = O. We further fix the shortcuts to maps with (0) = 0. The map hi identifies the j-th layer in the i-th residual block with Lipschitz constraints
Siy and distance constraints bij (w.rt. reference weights My)). Specifically, if huj is collecccoeeee.d then
hig { Agaar Lip(ø) S 86g; || M5lle, $ $bis
(12)
and, in case huj is convolutional, then
hij E 0xx
Lip(ok,)) S 8ij, [Kgg - M1rl22,1 S <bis}
(13)
In terms of notation, 8, Lip(s.) II PijSty further denotes the upper bound on the Lipschitz constant of the i-th residual block f.. The Lipschitz constants are w.r.t. Euclidean norms; for fully-connected layer this coincides with the spectral norm of the weight matrix.
The covering number bounds in Theorem 3.4 below depend on three types of quantities: (1) the total number of layers L = Σ, L, (2) the numbers Wiy of parameters of the j-th layer in the i-th residual block, their maximum W max4, Wy, and (3) terms Ctj that quantify the part of layer's capacity attributed to weight and data norms. With respect to the latter, we define
C1)(X) =2 1I V
[I sipt
I 8t
8ikPak bij
(14)
Sij
max, || and so the Cip can be bounded independently of the sample size. Overall, this yields the following covering number bounds for residual networks.
and write Cjj = Ci() for brevity. Importantly, || S
Theorem 3.4. The covering number of the class of residual networks F as specified above, satisfies
J.
I
log(2W)
Σ
C2//3
2/3
(15a)
log (F,,
2Wij log (1+ [
(15b)

---

3.5 Rademacher complexity bounds
In combination with Dudley's entropy integral, Theorem 3.4 implies the empirical Rademacher complexity bounds in Theorem 3.5. These bounds equally hold for non non-residual networks as in Eq. (1), i... the special case of setting the shortcuts 9i to the zero map (with L =1 block).
Theorem 3.5. Let 7 > 0 and define Oi = 2C2//7 Further, let Hn-1 = Em=1 1/m = O (n))
denote the (n 1)-th harmonic number. Then, the empirical Rademacher complexity of Fry satisfies
3/2
12H,
L
L
(s(FF)
- 12
+ vn
v (2g)
and
L Li
12 Vn
25 log (1+ [2003] + ([1e0)))
Rs(FF) v
where ub is a monotonically increusing function, satisfying (0) = and Va: : vx(x) < 2.7.
The theorem considers the function class F., defined in Eq. (3). As a consequence, the bounds depend on the quotients C25 = 2C /7, which measure a layer's 's capacity (with respect to weight and data norms) relative to a classification margin parameter y- As will see in the experiments, constraining the layers' Lipschitz constants and weight norms, allows to substantially reduce the quantities Ciy while the margin parameter y decreases only moderately.
Theorem 3.5 also immediately implies generalization bounds for F , via Lemma 3.1. In a subsequent step one can gradually decrease the constraint strengths and invoke union bound argument over the corresponding generalization bounds, as for example done in [3, Lemma A.9]. This yields a generalization bound which does not depend on priori defined constraint strengths, but on the actual Lipschitz constants and group norms computed from a neural network's 's weights.
Interpretation. To facilitate clean comparison between the bounds in Theorem 3.5, we disregard the ceiling function and apply Jensen's 's inequality to the first bound (.), yielding
12Hn-1 Vn
/1oE(2W) Eny T2C3
Rs S
(16)
Denoting Ö = max,, Ozgy Eq. (16) reveals that the bounds essentially differ only in that (+) depends on (z and (() depends on (2W log(1 + L2² Thus, the question of which one is tighter, hinges on the ratio of 2W and i.2 i.e., tradeoff between the number of parameters and the weight norms. As we see Fig. 2, for simple, unconstrained networks, our second bound much tighter. However, due to the logarithmic dependency on C, it is less affected by constraining the distances b initialization and the Lipschitz constants s. In Section 4, we show that this effect causes (&) to be more faithful measure of excess capacity. As Ö' depends exponentially on the network depth via the product of Lipschitz constants, another perspective on the bounds is that Eq. (+) favors shallow architectures whereas Eq. favors narrow architectures. Notably, replacing the function class F, with a class of networks composed with a Lipschitz augmented loss function [43] facilitates deriving Rademacher complexity- and generalization bounds, which do not suffer from the exponential depth dependency via the product of Lipschitz constants. Instead, such bounds depend on data dependent empirical estimates thereof, which are typically much smaller.
Relation to prior work. Prior works [14, 16, 38] that tie generalization to (1, oo) group norms of matrices of fully-connected layers are equally applicable convolutional networks without unfavorable scaling w.r.t. input size. In particular, for (1, 20) group norms of MM, we have |M ||I = max, |Ko--Il. 1I, i.e., the maximum I norm over each (input channel, width, height) slice of K. Yet, due to the layer-peeling strategy common to these works, the bounds scale with the product of matrix group norms vs. the product of Lipschitz constants (as in the C.y in Theorem 3.5) for covering number based strategies. While one can construct settings where the product of (1, oc) group norms is smaller than the product of Lipschitz constants, this is typically not observed empirically, cf. Fig. 2. Alternatively, Long & Sedghi [31] derive generalization bound which does not depend on 4
7

---

norms or group norms, but only on the distance to initialization with respect to the spectral norm. Notably, an intermediate result in this reference yields a generalization bound of similar form as ()), scaling with the logarithm of the product of Lipschitz constants and with the square root of the number of parameters, see Section A.5. The distance to initialization then enters the main result [31, Theorem 3.1] at the cost of a Lipschitz constraint on the initialization. We argue that (A) incorporates the distance to initialization more naturally, as it comes without constraints on the initialization itself. Further, it holds for any sample size n and the numerical constants are explicit. Last, in the special case of fully-connected layers and no skip connections, (+) reduces to the Rademacher complexity bound from [3]. Yet, there are three differences to this result: (i) a different numerical constant, (ii) the logarithm is replaced with a harmonic number, and (iii) there are no ceiling functions. From understanding, these modifications are equally necessary when proving the special case directly. Nevertheless, these differences are only of minor importance, as they do not affect the asymptotic behavior of the bound. For more details, see Section A.4.
4 Empirical Evaluation
To assess the excess capacity of a neural network trained via standard protocol on some dataset, we seek hypothesis class that contains a network of the same architecture with comparable testing error but smaller capacity. Controlling capacity via the bounds in Theorem 3.5 requires simultaneously constraining the Lipschitz constants per layer and the (2, 1) group norm distance of each layer's 's weight to its initialization. We first discuss how to enforce the constraints. Then, we fix residual network architecture and train on datasets of increasing difficulty while varying the constraint strengths.
Capacity reduction. Controlling hypothesis class capacity necessitates ensuring that optimization yields a network parametrization that satisfies the desired constraints. To this end, we implement variant of projected stochastic gradient descent (SGD) where, after a certain number of update steps, we project onto the intersection of the corresponding constraint sets Cj and Cz. For convolutional layers, parametrized by tensors K, these are the convex sets C₁ = {K : || - 1 S b} and C2 = [K: Lip(@x) I s). Hence, jointly satisfying the constraints is a convex feasibility problem of finding a point in = C1 n2,, To ensure C + 0, we initially (prior to optimization) scale each layer's 's weight K so that Lip(@ko)= s. This starting point (per layer) resides in C by construction.
To project onto C, we rely on alternating orthogonal projections which map K to a tensor in C,, resp. C2 with minimal distance to K. Repeated application of these projections converges to point in the intersection C [5]. To implement the orthogonal projections onto C₁ and C2, we rely on work by Liu et al. [30] and Sedghi et al. [40], respectively. The latter requires certain architectural prerequisites, and in consequence, we need to use convolutions of stride 1 (though our bounds equally hold for strides >1) and to reduce spatial dimensionality only via max-pooling. Further, we circular padding and kernel sizes not larger than the input dimensionalities. For details on the projection algorithm and a comparison alternating radial projections, see Section B.2.
Architecture. We use slightly modified (pre-activation) ResNet18 [21]. Modifications include: (1) the removal of batch normalization and biases; (2) skip connections for residual blocks where the number of channels doubles and spatial dimensionality is halved are implemented via fixed map. Each half of the resulting channels is obtained via 2 x 2 spatial max max-pooling (shifted by one pixel). This map has Lipschitz constant /2 and is similar the shorteut variant (A) of [20]; finally, (3) we fix the weight vectors of the last (classification) layer at the vertices of a ks 1 unit simplex. Fixing the classifier is motivated by [18] and the simplex configuration is inspired by [17, 48] who show that this configuration corresponds to the geometric weight arrangement one would obtain at minimal cross-entropy loss. By construction, this classifier has Lipschitz constant Vefx-1. Notably, modifications (2) and (3) do not harm performance, with empirical testing errors on a par with a standard ResNet18 without batch normalization. Modification (1), i.c., the omission of normalization layers, was done to ensure that the experiments are in the setting of Eq. (11) and therefore that are faithful capacity measures. However, testing error. In principle, our theory could handle batch normalization, as, during evaluation, the latter is just an affine map parametrized by the running mean and variance learned during training. However, including normalization in our empirical evaluation is problematic, as normalizing batches of small variance requires the normalization layers to have a large Lipschitz constant. Consequently, considering normalization layers affine maps and enforcing Lipschitz constraints them could
accompanied by noticeable increase in
8

---

prevent proper normalization of the data. Another strategy would be to consider normalization layers as fixed nonlinearities which normalize each batch zero mean and unit variance. However, this map is not Lipschitz continuous, and again, modifications could hinder normalization (which defeats the very purpose of these layers). Hence, we decided to remove normalization layers in our empirical evaluation. Presumably, however, there is a middle ground where capacity is reduced, and normalization is still possible. If so, excess capacity could be assessed for very deep architectures, which are difficult to train without normalization layers.
Datasets & Training- We test on three benchmark datasets: CIFAR 10/100 [25], and -mag--mageNet- 200 [24], listed in order of increasing task difficulty. We minimize the cross-entropy loss using SGID with momentum (0.9) and small weight decay (1e-4) for 200 epochs with batch size 256 and follow CIFAR-typich stepwise learning rate schedule, decaying the initial learning rate (of 3e-3) by factor of 5x at epochs 60, 120 & 160 [10]. No data augmentation is used. When projecting onto the constraint sets, we found one alternating projection step every 15th SGD update to be sufficient to remain close to C. To ensure that a trained model is within the eapacity-constraiin perform 15 additional alternating projection steps after the final SGD update. For consistency, all experiments are run with the same hyperparameters. Consequently, hyperparameters are chosen so that training converges for the strongest constraints we assess. In particular, we train for 200 epochs even though unconstrained and weakly constrained models can be trained much faster. Importantly, this affects the assessment of excess capacity only marginally, as we observe that the testing error does not deteriorate in case of more update steps. Similarly, the Lipschitz constant and the distance to initialization stay almost constant once the close-to-zero training error regime is reached, which may happen way before 200 epochs are completed.
class, we
4.1 Results
First, we assess the espacity-driving quantities in our bounds for models trained without constraints! Table (top) lists a comparison across datasets, along with the capacity measures (d. 4), the training/testing error, and the empirical generalization gap (i.e., the difference between testing and training error). In accordance with our motivating figure from Section (Fig. 1), we observe an overall increase in both capacity-driving quantities as a function of task difficulty.
To assess excess capacity in the context of questions (Q1) and (Q2), first identify, per dataset, the most restrictive constraint combination where the testing error" is as close as possible to the unconstrained regime. We refer to this setting as the operating point for the constraints, characterizing the function class F that serves as a reference to measure excess capacity. The operating points per dataset, as well as the corresponding results are listed in Table 1 (bottom).
With respect to (Q1) we find that networks can indeed maintain, or even improve. testing error at substantially lowered capacity (see performance comparison in Fig. relative to )) Furthermore, the observation that the capacity of the constrained models (surprisingly) remains in the same order of magnitude across tasks of varying difficulty, suggests negative answer to question (Q2). A reduced-capacity model from an easy task can perform well on a difficult task. In consequence, when comparing the top ys. bottom part of Table with respect column (+), we do see that task difficulty primarily manifests as excess capacity. Another manifestation of task difficulty is evident from the more detailed analysis in Fig. 3 (bottom), where we see that tightening both constraints beyond the identified operating point leads to a more rapid deterioration of the testing eтror as the task difficulty increases. Interestingly, at the operating point, the constrained models do not only share similar capacity across datasets, but also similar empirical generalization gaps, primarily due to leaving the ubiquitous zero- aero--raininggeree
regime. The latter is particularly noteworthy, as strong regularization (e.g., via weight decay) can equally enforce this behavior, but typically at the cost of large increase in testing error (which we do not observe). Finally, the parameter-counting variant of our bound (see Table 1, column is, by construction, much less affected by the constraints and apparently fails to capture the observations above. This highlights the relevance of tying capacity to weight norms and underscores their utility in our context.
At evaluation time. Lipschitz constants are computed via power iteration for convolutional layers [15, 27]. We are primarily interested in what is feasible in terms of tolerable capacity reduction. Hence, leveraging the testing split of each dataset for this purpose is legitimate from this exploratory perspective.

---

CIFARIO difficulty: saag)
CIFARIO0 difficulty: medium)
Tiyy-ImageNet-200 (task difficulty: bard)
1.
Triiing UNNTIN
Tranker
Openating polle
Trablte
na
44
24
Operpting
15
005
0.5
0.40
Testing secusay
Testing sccerscy
Teating sonntey
(22) sxmp dutuuee
Overentt
035
Lipechite
Lipuchita
Lipuchite
Figure Fine-grained analysis of training/testing accuracy in relation the Lipschitz constraint and the (2, group norm distance to initialization constraint. We see that testing accuracy can be retained (relative for a range of fairly restrictive constraints (top row), compared to the unconstrained regime (cf. Lip//Dstt columns in the top part of Table 1). However, this range noticeably narrows with increasing task difficulty (bottom row).
Table I: Assessment of the capacity-driving quantities. We list the median over the Lipschitz constants (Lip.) and the (2, 1) group norm distances (Dist.) across all layers. Err. denotes the traininghesting error, Capacity denotes the measures (4, from Theorem 3.5 and Gap the empirical genoralization gap. The top part lists results in the unconstrained regime (see in Fig. 3). the bottom part lists results at the operating point of the most restrictive constraint combination where the testing emror not worse than in the unconstrained case. Mar. denotes the margin parameter 7 used for computing the capacity measures. As the constrained models not the training data anymore, they do not have a positive classification margin. Thus, we choose y such that the unconstrained and constrained models have the same ramp loss value.
Lip.
Dist.
Mar.
Err. (Tst)
Err. (Trn)
Capacity (4.
Gap
CIFARI0
1.63
60.3
11.2
0.24
0.00
1.0-10
/ 18
0.24
CIFAR 100
2.17
129.1
23.4
0.54
0.00
1.7-10" /9.3-10"
0.54
Tiny ImageNet
3.05
287.3
24.7
0.62
0.00
4. 1.1
0.62
CIFARIO
0.80
50.0
1.00
0.21
0.06
1.8-10 /7.8-102
0.15
CIFARIO0
0.80
70.0
1.00
0.52
0.36
2.6-10 /7.9-102
0.16
Tiny ImageNet
0.80
130.0
1.00
0.62
0.41
8.9-10 889--102
0.21
Discussion
Studying the capacity of neural networks hinges crucially on the measure that is used to quantify In our case, capacity rests upon two bounds on the empirical Rademacher complexity, both depending on weight norms and the number parameters, but to different extents. Hence, exerting control over the weight norms manifests in different ways: in case of the more weight norm dependent capacity measure, our results show substantial lask-dependent excess cupucity, while, when relying more on parameter counting, this effect is less pronounced. Although the latter measure yields tighter bounds, its utility in terms of explaining the observed empirical behavior is limited: in fact, capacity tied to weight norms not only better correlates with observed generalization gaps (both with and without constraints), but the amount of tolcrable capacity reduction also reflects the smaller generalization gaps in the constrained regime. Note that results rest upon carefully implementing constraint enforcement during optimization. Hence, numerical schemes to better account for this setting might pronounced excess capacity effect.
potentially reveal an
In summary, our experiments, guided by the theoretical bounds, strongly suggest a notion of com- pressibility of networks with respect to weight norms. This compressibility only moderately reduces with task difficulty. We believe these observations to be particularly relevant and we foresee them sparking future work along this direction.
Acknowledgments
This work was supported by the Austrian Science Fund (FWF) under project FWF P31799-N38 and the Land Salzburg under projects 0102-F1901 1-0--F9991166K22 and 2024-WW1S//255/17222099
10

---

References
[I] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- tine-grained analysis of optimization and generalization for overparameterrzed two-layer neural networks. In ICML, 2019.
[2] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang, Stronger generalization bounds for deep nets via compression approach. In ICML, 2018.
[3] Peter Bartlett, Dylan Foster, and Matus Telgarsky, Spectrally-normaaized margin bounds for neural networks. In NeurIPS, 2017.
[4] Peter Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res. (JMLR), 3(Nov):463-44 482,, 2002.
[5] Heinz H. Bauschke and Jonathan M. Borwein. On projection algorithms for solving convex feasibility problems. STAM Review, 36(3):367-426, 1996.
[6] Cenk Baykal, Lucas Liehenwein, Igor Gillischenski, Dan Feldman, and Daniela Rus. Data- dependent coresets for compressing neural networks with application to generalization bounds. In ICLR, 2019.
[7] D.P. Bertsekas.
Nonlinear Programming. Athena Scientific, 1999.
[8] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In NeurIPS, 2019.
[9] Ching-Yar Yao Chuang, Youssef Mroueh, Kristjan Greenwald, Antonio Torralba, and Stefanie Jegelka. Measuring generalization with optimal transport. In NeurlPS, 2021.
[10] Terrance Veiei and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout, 2017. arXiv preprint attpss//aate
orggabs///ie 1708. 04552..
[11] Richard M. Dudley, The sizes of compact subsets of Hilbert space and continuity of Gaussian processes, J. Funct. Anal., 1(3):200-330, 1967.
[12] Richard L. Dykstra. An algorithm for restricted least squares regression. Journal of the American Statistical Association, 78(384):837-842 1983.
[13] Evarist Giné and Armelle Guillou. On consistency of kernel density estimators for randomly censored data: rates holding uniformly over adaptive intervals. Annales de I'IHP Probabilités statistiques, 37(4):503-522, 2001.
[14] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In COLT, 2018.
[15] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree. Regularisation of neural networks by enforcing Lipschitz continuity. Machine Learning, I 110(2):93-416, Feb 2021.
[16] Henry Gouk, Timothy M. Hospedales, and Massimiliano Pontil. Distance-based regularization of deep networks for fine-tuning. In ICLR, 2021.
[17] Florian Graf, Christoph Hofer, Mare Niethammer, and Roland Kwitt. Dissecting supervised contrastive learning. In ICML, 2021.
[18] Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In ICLR, 2017.
[19] Fengxiang He, Tongliang Liu, and Dacheng Tao. Why ResNet works? Residuals generalize. IEEE Trans Neural Nenw Learn. Syst., (1(12):344-5366 2020.
[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings deep residual networks. In ECCV, 2016.

---

[22] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In CVPR, 2017.
[23] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In NeurIPS, 2018.
[24] Justin Johnson. Tiny ImageNet. hta.a:///naaaaaaarooaaae/e///aaa wdt./tiin-mmaggeeeeee-- 200 zipp cessed: 28.09.2022 via http://cs23in. stanford
Ac-
[25] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[26] Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for multi-class convolutional neural networks. In AAAI, 2021.
[27] Qiyang Li, Saminul Haque, Cem Amil, James Lucas, Roger Grosse, and Jörn-Herrik Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. NeurIPS, 2019.
[28] Hongzhou Lin and Stefanic Jegelka. ResNet with one-neuron hidden layers is a universal approximator. In NeurlPS, 2018.
[29] Shan Lin and Jingwei Zhang. Generalization bounds for convolutional neural networks, 2019. arXiv preprint https: / /wwpvv..ivvv...////v///////a.av/ org/abg.//////oo.oo.......o... https/191..018...... 01487.
[30] Jun Liu, Shuiwang Ji, and Jieping Ye. Multi-task feature learning via efficient 42 -nrm minimization. In UAI, 2009.
[31] Philip Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. In ICLR, 2020.
[32] Andreas Maurer. A vector-contraction inequality for Rademacher complexities. ALT, 2016.
[33] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[34] Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. In NeurIPS workshop Deep Learning: Bridging Theory and Practice, 2017.
[35] Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience. In ICIRR, 2019.
[36] Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In NeurIPS, 2019.
[37] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to opectrally-normalizee margin bounds for neural networks. In ICLR, 2018.
[38] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In COLT, 2015.
[39] Jonas Rauber, Roland Zimmermann, Matthias Bethge, and Wieland Brendel. Foolbox Native: Fast adversarial attacks to benchmark the robustness of machine learning models in PyTorch, TensorFlow, and JAX. J. Open Source Softw., 5(53):2607, 2020.
[40] Hanie Sedghi, Vineet Gupta, and Philip Long. The singular values of convolutional layers. In ICLR, 2019.
[41] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, and Nati Stebro. The implicit bias of gradient descent on separable data. In ICLR, 2018.
[42] Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for non- compressed network: unified generalization error analysis of large compressible deep neural network. In ICLR, 2020.
12

---

[43] Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In NeurlPS, 2019.
[44] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Are deep ResNets provably better than linear predictors? In NeurIPS, 2019.
[45] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
[46] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-
115, 2021.
[47] Tong Zhang. Covering number bounds of certain regularized linear function classes. J. Mach. Learn. Res. (JMLR), (2):527-550, March 2002.
[48] Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu. geometric analysis of neural collapse with unconstrained features. In NeurIPS, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] For all presented theoretical results, we discuss connections, as well as limitations or advaattggs/dissadvaaaage with respect to prior work. Furthermore, our supplementary material (Appendix) contains substantial extensions of these discussions. Regarding our experimental results, we discuss potential limitations in Section 4 and Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] All experiments throughout this work are conducted
well-established, publicly available benchmark datasets for image classification. We primarily address theoretical aspects of existing neural network models for which we do not see potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All key theoretical results (theorems, lemmas, etc.), including assumptions and definitions are listed in the main part of the paper.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs for all theoreti- cal results listed in the main part of the paper (theorems, lemmas, etc.) can be found in the supplementary material (Appendix). including any omitted technical details.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URLY? [Yes] Code to re-run experiments and reproduce results is included in the supplementary as part of this submission.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] We include caining/architectuurg details in Section 4 of the main part of the puper. Details for our initial bound comparison in Fig. 2 can be found in the supplementary material (Appendix). Throughout all experiments, we adhere to the common training/testing splits of the three datasets we used, i.e., CIFARION 10/1///10000 00 and Tiny- Peny-mmageNet-200
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A] We did run experiments multiple times (using the same network, dataset and training regime), but under varying constraint strengths (rather than different seeds). Fig. 3 visualizes all these runs.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Section B.4 lists all hardware resources used in our experiments.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] The datasets we used are publicly available and well-established benchmark datasets commonly used in computer vision research.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using//urating? [N/A] All datasets in our experiments are used as is. (c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "gvGxiLp2fO2", "reviewer": "Reviewer_BA91", "summary": "The authors propose an extension to prior Rademacher complexity bounds to account for more realistic neural network architectures used in practice, specifically convolution and skip connections, as found in Residual Networks, a modified form of which are also used in the empirical results. The extension relies on two capacity terms: the Lipschitz constants of each of the layers, and the (2, 1) group norm distance to the initialization of the conv filter weights. The authors show experiments based on training a modified ResNet-18 model without batch normalization across the CIFAR-10, CIFAR-100 and Tiny ImageNet classification datasets, and show that constrained models (i.e. models that have lower group norm and Lipschitz capacity terms) can achieve similar performance to models with excess capacity (reaching 100% training accuracy), while having similar capacity on what are presumed to be increasingly difficult tasks. The authors propose this indicates that, like known with parameter counts, neural networks are compressible w.r.t. weight norms.", "questions": "- The authors point to the fact that compressibility w.r.t. parameter counts is well known, but claim that their experimental results show a novel result — that neural networks are compressible w.r.t. weight norms. This presumes that weight norm and parameter counts are independent (or “orthogonal”). However, the authors use weight decay in their experiments, i.e. an L2 weight norm regularization term, and the variance of the common random initialization methods for NN layers (i.e. Xavier/He) explicitly depends on the parameter count of a layer. Can we really assume that weight norms and parameter counts are independent in the context of real-world neural network training?\n- While the authors acknowledge that a significant problem in the field is that complexity bounds are often vacuous, it’s not obvious to me why complexity measures and related capacity bounds such as those explored in this paper would be a good method of analyzing excess capacity? \n- I don’t see any details on how the Lipschitz constant for all layers in the results section (i.e. Table 1) is calculated empirically, making it difficult to repeat these results.\n- Training ResNets without batch norm often is problematic (increasing with depth), without using methods such as those outlined in the Fixup paper (Zhang et al., 2019). The authors don’t mention any such workarounds, and I’d just like to ask if the authors could comment on this?\n- It’s not clear to me why layer-wise Lipschitz constant is important intuitively, as we do not perform layer-wise optimization? Isn’t the Lipschitz constant over all parameters (i.e. dimensions in the loss landscape) more relevant?\n- Isn’t 1x1 convolution on a 1x1 spatial feature map a linear combination or dot product over the channels rather than matrix multiplication?", "limitations": "I saw no discussion of societal impact of this work. I think one potential question is if only looking at generalization, as done in this work, is an appropriate measure of compressibility. For example how different is the function learned in the constrained solution? Achieving similar accuracy over the entire test set doesn’t mean functions learned are similar or predictions on the same samples is similar (e.g. as analyzed in the Deep Ensembles work for different solutions). In particular, are the constrained models more/less biased in predictions to particular classes in a classification task?", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper is well written overall, with the motivation for the proposed capacity terms made clear, and appropriate background references\n* The authors extend a complexity measure to more realistic settings — convolution all layers and skip connections are used in most contemporary neural network architectures for learning from images.\n* The authors present a derivation of their proposed complexity measures\n\nWeaknesses\n* The intuition behind the capacity terms proposed was not obvious to me\n* There are some reproducibility issues in the experimental results presented, notably it’s not obvious to me how the Lipschitz constant is calculated for different layers (only the classifier is explicitly addressed by construction from what I can see).\n* The claim of independence of weight norm and parameter count doesn’t hold up in the real-world experimental setting. In particular, in the stated example of neural network pruning, it is often done in a manner explicitly attempting to preserve the weight norm (i.e. removing smallest magnitude weights).", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "chec8P62Klz", "reviewer": "Reviewer_RqdG", "summary": "This paper proves generalization bounds for both convolutional and ResNet networks. In both cases, both the parameter counting approach and the norm-based approach are explored. \n\nCNN-Norm based (Theorem 3.5, first equation): Similar to [1] expect that it relies on L2 norms instead of L\\infty norms and therefore scales slightly differently depending on the regime. The main aspects are that the dependence on the input to each layer is larger than in [1] since it involves the whole of the input rather than a single convolutional patch, but on the other hand there is a factor of the post pooling width from [1] which disappears. The two could compensate each other or be in favour of one or the other bound. The norm in the batch direction is L2 instead of L\\infty as well, which is an advantage in the presence of outliers, but makes the dependence on the number of classes worse. \n\nCNN-Parameter counting (Theorem 3.5, second equation): Similar to [3], better management of constants (it becomes explicit), cleaner proof. Other claimed improvements are not significant. Just like [2] the bound basically says that the sample complexity grows as the number of parameters.\n\n\nResent- Parameter counting: Similar to [3] in terms of the approach, but solves a different problem and offers some of the first bounds on resnets. Neat exercise but no significantly original content. Just like [2] the bound basically says that the sample complexity grows as the number of parameters.\n\nResnet- Norm based: similar extension of [1] but still a very long and tedious exercise (due to the larger number of connections in the architecture) which was successfully executed. \n\n\n\n\n\n\n\n\n\n\n\n[1] Antoine Ledent, Waleed Mustafa, Yunwen Lei and Marius Kloft. \" Norm-based Generalisation bounds for convolutional neural networks\"\n\n[2] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. \"Spectrally-normalized margin bounds for neural networks\". NeurIPS 2017.\n\n[3] Philip Long and Hanie Sedghi. \"Generalisation bounds for deep convolutional neural networks\". ICLR 2020.", "questions": "   ", "limitations": "Originality, though I don't think this should be viewed too negatively as the community also needs papers like this one, especially if the claims of originality are further toned down. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths: \n\n++This is a long paper with a lot of work and is quite clean and well organised. It contains a good encyclopaedic summary of the field and of many frequently misunderstood issues. \n\n+ A lot of progress since previous submission\n\nWeaknesses:  \n\n- No substantial originality in the techniques.\n- Some issues not corrected since last submission.\n\n\n\nNUMERICAL CONSTANTS: \n\nThere is some slight dishonesty going on, including an error, in the treatment of numerical constants here: the authors results involve a constant of 12, which looks better than the corresponding constant of 36 in Bartlett et al [2]. This is only partially true. \n\nFirst of all, there is an error in the constant in [2], and it should be 72 instead of 36 (the authors correctly divide the constant of 72 from [2] in Lemma A.8 because they are looking at Rademacher complexity without explicitly writing the results in terms of generalisation bounds. However, the correct version of Lemma A8 should be with a constant of 144. Indeed, the function class which is studied in Lemma 3.2 in [2] includes only a (2,1) norm constraint, but no constraint on the spectral norm. In the proof of Theorem 3.3, a cover on a function class including both constraints is used instead (such a cover can be obtained up to a factor of 2 by a simple extra argument).  This is a very subtle error, which is inherited in the present paper (not in [1]), so a priori anyone could be forgiven for overseeing this. However, I reviewed this paper for ICML this year, pointed out the error to the authors, and they agreed with me in the rebuttal and agreed to fix it, which they haven't done!\n\n\nNext, the improvement in the constant compared to [2] (and to a lesser extent to [1]) is partially illusory. Note that there is a factor of 2 in both [2] and [1] which comes from the 2-Lipschitzness of margin-based loss functions. Here the authors do not work with a last layer loss function and work directly with the Rademacher complexity of the function class defined by the network, so the improvement in the constant is just due to solving a slightly different problem. \n\nRegarding the comparison to [1] in terms of numerical constants, it is correctly pointed out in line 654 (sup) that some may be unavoidable but that the bound from [4], where, according to the current paper \"the constants are nor optimized\". This is quite a bold statement. The results in [4] are very different and much much harder to prove that the Maurey type results used here and in [2], since they rely on L\\infty norms. There is a good chance the constants are unavoidable if one goes for the L\\infty approach. \n\n\nIMPROVEMENT COMPARED TO [3]\n\n\nI guess we just have to agree to disagree here but again, the improvement in the parameter counting result compared to [3] is purely in terms of the proof technique and clarity of exposition (and maybe slightly in the constant). Both [3] and the present paper somewhat misleadingly claim that the results \"take distance to initialization into account\", with the present paper also claiming that they do so \"more naturally\" (see line 264), but fundamentally, in both bounds, the square root of the number of parameters is both conceptually and numerically the dominant term, and distance to initialization is only present in the logarithmic factors. The authors explain this quite clearly in other parts of the paper, so I think they understand the point. \n\n\n\nTWO LAST POINTS REGARDING COMPARISON TO [1]\n\nI would like to see a comparison with the two layer version of [1]. Indeed, the factor which comes from changing between norms and scales similarly in [1] and the present paper depending on the regime is intuitively parasitic (though it seems difficult to get rid of it entirely and neither the current paper nor [1] succeed). However, in the two layer case, it is absent from [1]. I would expect the bound from [1] to be uniformly superior in this case (of course since it only applies to 2 layers it doesn't make the present paper irrelevant in general). \nNote also that the parasitic  factor can be reasonably removed from [1] in the general case at the cost of extreme cost in terms of computations (rather than loss of statistical power) by simply certifying the Lipschitz constant of the network with respect the the appropriate norms in a sufficiently large neighbourhood of all inputs.\n\n\n\n\n\n\n\n\n\nSMALL TYPOS\n\nLine 1089, capital letter for \"For\"\n Line 213 \"we further fixate...\" --> \"we further fix\"\n\n\n\n\n\n\n[1] Antoine Ledent, Waleed Mustafa, Yunwen Lei and Marius Kloft. \" Norm-based Generalisation bounds for convolutional neural networks\"\n\n[2] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. \"Spectrally-normalized margin bounds for neural networks\". NeurIPS 2017.\n\n[3] Philip Long and Hanie Sedghi. \"Generalisation bounds for deep convolutional neural networks\". ICLR 2020.\n\n\n[4] Tony Zhang, \"Covering number bounds of certain regularised linear function classes\". ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DcfmEp59XkZ", "reviewer": "Reviewer_vwiQ", "summary": "This paper provides new bounds for Rademacher complexity for neural networks and analyses their effect empirically. Most importantly, skip connect and convolutions are handled jointly, whereas normalisation techniques are not considered. A comparison to the existing literature is implemented. Exp[eriments try to emphasise how there is an excess in capacity and how it can be reduced. However, implementations seems to be cumbersome for now and not fully practical.", "questions": "Why can we apply Lipshitz constraints for h around line 215? I would have expected h to be unconstrained in normal deep learning.\n\nHow can Rademacher boundaries be established for the different normalisation techniques like group and batch normalisation, which are crucial parts of the algorithm. Is it possible at all to address them? If not, why? If yes, how?\n\nWhy is it not possible to run the experiments with larger networks and more importantly larger datasets?\n\nWhy are the experiments run for 200 epochs, even though even ResNet50 is able to converge in 35 epochs?\n\nCan the limitation of norms for reducing the capacity also be achieved by different optimisers that consider layers separately like LARS or LAMB?", "limitations": "Complex networks, require normalisation techniques like batch norm or layer norm. These are not addressed by the paper, which is a major limitation. Whereas skip connections and convolutions are crucial for generating meaningful features and getting a large network depth, normalisation techniques are crucial for convergence.\n\nAnother limitation is that the reduced capacity in the experiments does not really have an impact on the model size and expressivity and seems more artificially related to the provided new Rademacher complexity bounds. They could be however more a sign of the insufficiency of the bounds and the benefits of regularization than the real power of the new bounds.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Significance\n************\n\nThe relation to the state of the art is well presented. Especially, the inclusion of convolutions and skip connections is making a difference as well as the paper addressing how the respective Rademacher Complexities can be actually used for real world decision like changing the capacity of networks.\n\nI really like Figure 1 and how it is representing the state of the art. Also, the \"Relation to prior work.\" sections are very valuable, because they put the theorems in relation to other work and discuss advantages and disadvantages. Thus providing some valuable kind of literature overview.\n\nAccording to my understanding of ResNet18, it is possible to linearly scale layers without impacting the decision boundaries. Hence, it is unclear how limiting the weight norm would impact capacity at all. What are the benefits of this \"compression\" and why is it called \"compression\" at all?\n\nPrevious work addressed convolutions and skip connections separately and it seems none addressed them sufficiently jointly.\n\nA major caveat Is the lack of addressing normalisation techniques in the network to have ResNet18 fully addressed.\n\nI feel like disagreeing on the necessity of data dependent bounds. I belief, model complexity and data complexity are strongly related.\n\n\nClarity\n*******\n\n\nThe paper is very well structured and the separate steps are clear. References to the appendix are provided where required.\n\nWhereas I am not experienced in Rademacher complexity proofs, I feel that the proof sketch fro Theorem 3.2 and the whole motivation are described very clearly.\n\nThe word \"vacuous\" should be replaced with a more common and less archaic word.\nThe figure on page 1 is missing a legend for the read dots and it is missing a caption/title/number/reference.\n\nTiny-ImageNet-200 is not sufficiently referenced and explained in line 304.\n\nThe experiments state that every 15th SGD update step, the projections procedure is applied but then the authors \"increase the alternating projection steps to 15\". 15 is not an increase of 15.\n\nTable 1 mentions \"the testing error is on a par with the unconstrained case\". However, the error is no the same. So I assume that it means \"the testing error is equal or better than the unconstrained case\"?\n\nSome more technical details on the experiments would be great.\n\nIt might be useful to quickly mention what the \"empirical generalization gap\" is and why it is important to measure.\n\nThe experiments need further clarification.\n\nOriginality\n***********\n\nThe paper points out quite clear the relation to existing state of the art and how its boundaries are better than theirs. This is a great contribution in itself.\n\nThe derived boundaries seem to be non-trivial, especially since previous literature resulted in higher bounds.\n\nIt is great effort of the authors, not being satisfied with some new bounds but implementing a comparison to related work as well as addressing the respective values in empirical evaluations.\n\n\nQuality\n*******\n\n\nThe first figure needs some fixing. Overall, the paper is well structured and readable.\nThe paper states \"Notably, modifications (2) and (3) do not harm performance, with\n302 empirical testing errors on a par with a standard ResNet18 w/o batch normalization.\", however, respective references are missing. Also, it is not clear, how much the quality of ResNet18 is reduced due to the lack of normalisation. This part needs much more discussion.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept