A path-norm toolkit for modern networks: consequences, promises and challenges
Authors: Antoine Gonon
Nicolas Brisebarre
Elisa Riccietti
Rémi Gribonval
Venue: ICLR 2024 spotlight (2024)
Keywords: ReLU neural networks
path-norm
generalization
contraction lemma
peeling
Primary area: learning theory
TL;DR: We introduce the first path-norm toolkit encompassing modern DAG ReLU networks, leading to the sharpest known generalization bounds.

Abstract: This work introduces the first toolkit around path-norms that fully encompasses general DAG ReLU networks with biases, skip connections and any operation based on the extraction of order statistics: max pooling, GroupSort etc.
This toolkit notably allows us to establish generalization bounds for modern neural networks that are not only the most widely applicable path-norm based ones, but also recover or beat the sharpest known bounds of this type. 
These extended path-norms further enjoy the usual benefits of path-norms: ease of computation,  invariance under the symmetries of the network, and improved sharpness on layered fully-connected networks compared to the product of operator norms, another complexity measure most commonly used.

The versatility of the toolkit and its ease of implementation allow us to challenge the concrete promises of path-norm-based generalization bounds, by numerically evaluating the sharpest known bounds for ResNets on ImageNet.

Published as a conference paper at ICLR 2024
A PATH-NORM TOOLKIT FOR MODERN NETWORKS: CONSEQUENCES, PROMISES AND CHALLENGES
Antoine Gonon, Nicolas Brisebarre, Elisa Riccietti & Rémi Gribonval Univ Lyon, EnsL, UCBL, CNRS, Inria, LIP, F-69342, LYON Cedex 07, France
ABSTRACT
This work introduces the first toolkit around path-norms that fully encompasses general DAG ReLU networks with biases, skip connections and any operation based on the extraction of order statistics: max pooling, GroupSort etc. This toolkit notably allows to establish generalization bounds for modern neural networks that are not only the most widely applicable path-norm based ones, but also recover beat the sharpest known bounds of this type. These extended path-norms further enjoy the usual benefits of path- path-norms: ease of computation, invariance under the symmetries of the network, and improved sharpness lay- ered fully-connected networks compared to the product of operator norms, another complexity measure most commonly used.
The versatility of the toolkit and its ease of implementation allow us to challenge the concrete promises of path-norm-basee generalization bounds, by numerically evaluating the sharpest known bounds for ResNets on ImageNet.
INTRODUCTION
Developing a thorough understanding of theoretical properties of neural networks is key to achieve central objectives such as efficient and trustworthy training, robustness to adversarial attacks (e.g- via Lipschitz bounds), or statistical soundness guarantees (via so-called generalization bounds).
The so-called path-norms and path-lifting are promising concepts to theoretically analyze neural networks: the L path-norm has been used to derive generalization guarantees (Neyshabur et al., 2015; Barron & Klusowski, 2019), and the path-lifting has led for example to identifiability guar- antees (Bona-Pellissier et al., 2022; Stock & Gribonval, 2023) and characterizations of properties of the dynamics of training algorithms (Marcotte et al., 2023).
Yet, current definitions of path narm-norms and of path-lifting models unable to combine in a single framework pooling layers, skip connections, biases, or even multi-dimensional output (Neyshabur et al., 2015; Kawaguchi al., 2017; Bona-Pellissier et al., 2022; Stock & Gribonval, 2023). Thus, the promises existing theoretical guarantees based on these tools are currently out of reach: they cannot even be tested on standard modern networks.
severely limited: they only cover simple
Due to the lack of versatility of these tools, known results have only been tested on toy exam- ples. This prevents from both understanding the reach of these tools and from diagnosing their strengths and weaknesses, which is necessary to either improve them in order to make them actually operational, if possible, to identify without concession the gap between theory and practice, in particular for generalization bounds.
This work adresses the challenge of making these tools fully compatible with modern networks, and to concretely assess them on standard real-world examples. First, it formalizes a definition of path-lifting (and path-norms) adapted to very generic ReLU networks, covering any DAG archi- tecture (in particular with skip connections), including in the presence of max/average-pooliig (and even more generally k-max-poods moox-ng. which extracts the k-th largest coordinate, recovering max- pooling for A 1) and/or biases. This covers wide variety of modern networks (notably ResNets, VGGs, U-nets, ReLU MobileNets, Inception nets, Alexnet)', and recovers previously known defi- nitions of these tools in simpler settings such layered fully-connected networks.
TTe conclusion discusses networks not covered by the framework and adaptations needed them.

---

Published as a conference paper at ICLR 2024
The immediate interests of these tools are: 1) path-norms are easy to compute" modern net- works via a single seward-pass. 2) path-norms are invariant under neuron permutations and pa- rameter rescalings that leave the network invariant; and 3) the path-norms yield Lipschitz bounds. These properties were known (but scattered in the literature) in the restricted case of layered fully- connected ReL.U networks primarily without biases (and without average/k-max-pooliiee connections) (Neyshabur et al., 2015; Neyshabur, 2017; Furusho, 2020; Jiang et al., 2020; Dziugaite al., 2020; Bona-Pellissier et al., 2022; Stock & Gribonval, 2023). They are generalized here for generie DAG ReLU networks with most of the standard ingredients of modern networks (pooling, skip connections..... with the notable exception of the attention mechanism.
nor skip
Moreover, path-norms tightly lower bound products of operator norms, another complexity mea- sure that does not enjoy the same invariances as path-norms, despite being widely used for Lipschitz bounds (e.g., to control adversarial robusteness) (Neyshabur et al., 2018; Gonon et al., 2023) or gen- eralization bounds (Neyshabur et al., 2015; Bartlett et al., 2017; Golowich et al., 2018). This bound, which was only known for scalar-valued layered fully-connected ReLU networks without biases (Neyshabur et al., 2015), is again generalized here to generic vector-valued DAG ReLU networks. This requires introducing so-called mixed path- path-norms and extending products of operator norms.
Second, this work also establishes a new generalization bound for modern ReLU networks based on their corresponding L' path-norm. This bound covers arbitrary output dimension (while previous work focused on scalar dimension, see Table 1), generic DAG ReLU network architectures with parrage//-max-pooliin
skip connections and biases. The achieved generalization bound re- covers or beats the sharpest known ones of this type, that were so far only available in simpler restricted settings, see Table I for an overview. Among the technical ingredients used in the proof of this generalization bound, the new contraction lemmas and the new peeling argument are among the main theoretical contributions of this work. The first new contraction lemma extends the clas- sical ones with scalar t; E I. and contractions fi of the form Eeg (suPıer Eier (tf)(t))) < Eeg (supier Eier e,t,) (Ledoux & Talagrand, 1991, Theorem 4.1,), with convex non-decreasing g. to situations where there are multiples independent copies indexed by 2 E Z of the latter: Eg max 9 (SuPreT= Eier (tt)), & Eg max 9 (supreT= Σier Es.sti). The second new contraction lemma deals with vector-valued t; E RW, and functions f. that compute the k-th largest input's 's coordinate, to cope with k-max-pooling neurons, and it also handles multiple inde- pendent copies indexed by 2 E Z. The most closely related lemma we could find the vector-valued one in Maurer (2016) established with a different technique, and that holds only for g id with a single copy (Z) = 1). The peeling argument reduces the Rademacher complexity of the whole model to that of the inputs by peeling off the neurons of the model one by one. This is inspired by the peeling argument of Golowich et al. (2018), 8), which is however specific to layered conneccd ReLU networks with layer-wise constraints on the weights. Substantial additional ingredients are developed to handle arbitrary DAG ReL.U networks (as there is no longer such a thing as a layer to peel), with not only ReL.U but also k--ax- t-max-pooling and identity neurons (where Golowich et al. (2018) has only ReLU neurons), and leveraging only global constraint through the path-norm (in- stead of layerwise constraints on operator norms). The analysis notably makes use of the rescaling invariance of the proposed generalized path-lifting.
The versatility of the proposed tools enables us to compute for the first time generalization bounds based on the L' path-norm on networks really used in practice. This is the opportunity to assess the current state of the gap between theory and practice, and diagnose possible room for improvements. As a concrete example, we demonstrate that on ResNet1 8 trained on ImageNet: 1) the proposed generalization bound can be numerically computed; 2) for a (dense) ResNet18 trained with standard tools, roughly 30 orders of magnitude would need to be gained for this path-norm based bound to match practically observed generalization error; 3) the same bound evaluated on a sparse ResNet18 (trained with standard sparsification techniques) is decreased by up to 13 orders of magnitude. We conclude the paper by discussing promising leads to reduce this gap.
Paper structure. Section 2 introduces the ReLU networks being considered, and generalizes to this model the central definitions and results related to the path-lifting the path-activations and path- norms. Section 3 state a versatile generalization bound for such networks based on path-norm, and sketches its proof. Section 4 reports numerical experiments on ImageNet and ResNets. Related works are discussed along the way, and we refer to Appendix K for more details.
"Code for reproducibility is in Gonon et al. (2024).
2

---

Published as a conference paper at ICLR 2024
Table 1: Generalization bounds (up to universal multiplicative constants) for a ReLU network esti- mator with parameters restricted to belong to some subset Q C R (Definition 2.2), learned from iid training points when 1) the loss 1 E (R || [12) + E(..y) R is L-Lipschitz for every y, and 2) inputs are bounded in -nrm by B 1. Here, /mn/dout are the input/output dimen- [n)( is the maximum kernel size (Definition 2.2) of the +-max-pooling neurons, Ma is the matrix of layer d for a layered fully-connected network (LFCN) without bias (eLU(M, D is the depth. Note that having r in the bound is more desirable than having R since & R and R. can be arbitrarily large even when r 0 (The- orem C. I and Figure 2 in appendix). This is because R decouples the layers without taking into account rescaling invariances.
sions, K- = maxien.
(x(x) a)) = Mp ReLU(Mp-1
Architecture
Parameter set e
Generalization bound
(Kakade et al., 2008, Eq. (5)) (Bach, 2024, Sec. 4.5.3)
LFCN with depth D = 1, no bias, d = [b(O]]] &
|0|| =
LB rV Vln(da)
vn
(linear regression)
(E ct al., 2022, Thm, 6)
LFCN with D 2, no bias, dust =1
[0(0]] &
L vR rr //n(dm))
(Bach, 2017, Proposition 7)
(two-layer network)
(Neyshabur et al., 2015,
DAG, no bias, dear.
[+(0]]] gr
vn 2"rv/n(dm
Corollary 7)
(Golowich et al., 2018,
LFCN with arbitrary D. no bias, dea
I ||Malla & R
L8 vn
R/DD D + In((w))
Theorem 3.2)
d-1
(Barron Klusowski, 2019,
LFCN with arbitrary D. no bias, daa
[+(0]]] &r
rv D In(dw)
vn
Corollary 2)
Here, Theorem 3.1
DAG. with biases, arbitrary dua, with ReLU, identity and k-max-pooling neurons for k & {Ki,...,pp) kp) C (1...., K}
[ &
LB
vn x TV Dlu(PK) + Iuf (didd
2 RELU MODEL AND PATH-LIFTING
Section 2.1 defines general DAG ReLU model that covers modern architectures. Section 2.2 then introduces the so-called path-norms and extends related known results to this general model.
2.1 RELU MODEL THAT COVERS MODERN NETWORKS
Definition 2.2 introduces the model considered here (extending, egg., Devere et al. (2021)).
Definition 2.1. The ReLUffuction is defined as ReLU(x)) x11.20 for x R. The k k-max-pooling function k- t-oooolaa px) := (k) returns the k-th largest coordinate of E Rd.
Definition 2.2. Consider a Directed Acyelic Graph (DAG) G = (N, F)) with edges E, and vertices N called neurons. For a neuron v, the sets (aut(v)ss((( of antecedents and successors of u are ant(v) := (u E N,u + u E suc(v)) == {u E U- u E}. Neurons with no antecedents (resp. no successors) are called input (resp. output) neurons, and their set is denoted Nin (resp. Now). Input and output dimensions are respectively d := |Niel and dona := (Naul
A ReLU neural network architecture is tuple (G, (Po)OEN composed of a DAG G =
(N, with attributes Pe E (id, ReI.U] U (k-pool, k E N5o} for v E N (Now U Nm) and pr id for u E Nou- We will again denote the tuple (G, (Po)VEN)NN)) by G, and it will be clear from context whether the results depend only G (N,E)
also its attributes. Define N₂ = {u E N,P p} for an activation p. and No.poo1 == UKEN Nk-poo1. A neuron in N..poor is called a t-max-pooling neuron. For a E Ne.poor, its kernel size is defined as being [n)(()).
Parameters associated with this architecture are vectors O E RG == R EUNNNN We call bias b. := 0, the coordinate associated with neuron v (input neurons have no bias), and denote 6u-r the weight associated with an edge + E E. We will often denote O - (0">)) )weant(v) and 0 (0-->") (0"""")esuctt" Desuuc(p)
The realization of a neural network with parameters 9 E T is the function R RN - N... (simply denoted Ro when G is clear from the context) defined for every input x E RN as
[z) (v(0,z)) 2)),, Nos:
For index set J, denote TR' {(0x))eI, 0: E RR.
3

---

Published as a conference paper at ICLR 2024
where we use the same symbol to denote neuron N and the associated function v(0,
defined as v(0,z) == Tv for an input neuron v, and defined by induction otherwise
v00,z) = { Pu(br + Eugantio) u(0, (00
Pr = ReLU or pa = id,
(1)
k-pool ((b, + =(0,0))0000000 x)00))))m)))))))) )uEant(r)
if p = k-pool.
Such a model indeed encompasses modern networks via the following implementations: Max-pooling: set Pv k-pool for k 1, by 0 and 0u-v for every E ant(v).
Average-pooling: set p. = id, by and @u- = 1/1 ant(u) for every u E ant(v))
GroupSort/lop-k operator: use the DAG structure and *-max-pooling neurons (Anil et al., 2019; Sander et al., 2023).
Batch normalization: set P. id and weights accordingly. Batch normalization layers only differ from standard affine layers by the way their parameters are updated during training.
Skip connections: via the DAG structure, the outputs of any past layers can be added to the pre- activation of any neuron by adding connections from these layers to the given neuron.
Convolutional layers: consider them as (doubly) circulant/Toeplizz fully connected layers.
2.2 PATH-LIFTING, PATH-ACTIVATION AND PATH-NORMS
Given a general DAG ReLU network G as in Definition 2.2, it is possible to define set of paths PG; a path-lifting ΦC and path-activations A see Definition A.3 in the supplementary. The L path- norm is simply || (0)l.. Some bounds we later establish also exploit so-called mixed path-norms when = r) introduced in Definition A.4. Superscript G is omitted when obvious from the context. The interest is that (mixed) path norh- which are easy compute, can be interpreted as Lipschitz bounds of the network, smaller than another Lipschitz bound based on products of operator norms. We give here a high-level overview of the definitions and properties, and refer to Appendix A for formal definitions, proofs and technical details. We highlight that the definitions and properties coincide with previously known ones in classical simpler settings.
| (0)ll (= |
Path-lifting and path-activations: fundamental properties. The path-lifting & and the path- activations A are defined to ensure the next fundamental properties: 1) for each parameter O, the path-lifting (()) R² is independent of the inputs x, and polynomial in the parameters 0 in way that it is invariant under all neuron- wise rescaling symmetries* networks.; 2) A(,, x) E (da++)) takes a finite number of values and is piece-wise constant as a function of (0, r): and 3) denoting +-* and A to be the same objects but associated with the graph deduced from G by keeping only the largest subgraph of G with the same inputs as G and with single output v, the output of every neuron can be written as
② (0), 4 (0, ( x
(1))
v (0,
(2)
Compared to previous definitions given in simpler models (no k--mx- k--max-oolling even for single given k. no skip connections, no biases, one-dimensional output and/or layered network) (Kawaguchi al., 2017; Bona-Pellissier al., 2022; Stock & Gribonval, 2023), the main novelty is essentially to properly define the path-activations A(0, .) in the presence of x-max-pooling neurons: when going through a k-max-pooling neuron, a path stays active only if the previous neuron of the path is the first in lexicographic order to be the k-th largest input of this pooling neuron.
Path-norms are easy to compute. It is mentioned in Dziugaite et al. (2020, Appendix C.6.5) and Jiang et al. (2020, Equation (44)) (without proof) that for layered colyecconneeted ReLU net- works without biases, the L path-norm can be computed in a single forward pass with the formula: (0) || e (1)]|1, where |ax| is the vector with - |æ]| applied coordinate- wise and where 1 is the constant input equal to one. This can be proved straightforward way, using Equa- tion (2), and extended mixed path-norm: (0) gl.r
R (1))²/4 ||r. However, Appendix A
Because of Sesttiv-hhmooeneityy of the considered activations functions, the realized function is preserved (Stock & Gribonval, 2023) when the incoming weights and the bias of a neuron are multiplied by X > 0, while its outgoing weights are divided by A. Path-norms inherit such symmetries and are further invariant to certain neuron permutations, typically within each layer the case of layered fully-connected
4

---

Published as a conference paper at ICLR 2024
shows that this formula is false soon as there is at least one s-max-pooling neuron, and that easy computation remains possible by first replacing the activation function of *-max max-pooling neurons with the identity before doing the forward pass. Average-pooling neurons also need to be explicitly modeled as described after Definition 2.2, to apply x: >> | to their weights.
The mixed T path-norm is Lipschitz bound. Equation (2) is fundamental to understand the role of path-norms. It shows that & contains information about the slopes of the function realized by the network on each region where A is constant. A formal result that goes in this direction is the Lipschitz bound (x)) specific case = 1, for scalar-valued layered fully- cully-connected ReLU networks (Neyshabur, 2017, before Section 3.4) (Furusho, 2020, Theorem 5), which does not require mixed path-norms since [ 11. = (0))la llq for scalar-valued networks. This generalized the more general case of Definition 2.2 in Lemma A.2. This allows for leveraging generic generalization bounds that apply to the set of all I.-Lipschitz functions/ f [0, 1j - [0, 1], however these bounds suffer from the curse of dimensionality (von Luxburg & Bousquet, 2004), unlike the bounds established in Section 3.
Ro (x')ll I|- < [[((O]]
ool previously only known in the
Path-norms tightly lower bound products of operator norms. For layered fully-connected ReLU networks (LFCN) with no bias, i.e., (x)x)) = MD ReLUUMD-11 ReL.U(Max)) with matrices Mi,...,,pp another known Lipschitz bound is (Neyshabur et al., 2018; Gonon et al,, 2023) 11 [|Mall..o with q = 1, where || is the maximum L norm of a row of ma- trix M. This product is also used derive generalization guarantees (Neyshabur et al., 2015; Bartlett et al., 2017; Golowich et al., 2018). So which one of path-norm and products of opera- tor norms should be used? There are at least three reasons to consider the path-norm. First, holds (1)0))
< 11:-1 ||Malla.so (Theorem C.I), with equality the parameters are properly rescaled. This is known for scalar-valued LFCNs without biases (Neyshabur et al., 2015, Theorem 5). Appendix generalizes to DAGs as in Definition 2.2. The difficulty is to define the equivalent of the product of operator norms with an arbitrary DAG and in the presence of biases. Apart from that, the proof is essentially the same as in Neyshabur et al. (2015), with a similar rescaling that leads to equality of both measures, see Algorithm 1. Second, there are cases where the product of operator norms is arbitrarily large while the path-norm is zero (see Figure 2 in Appendix C). Thus, not desirable to have a generalization bound that depends on this product of operator norms since, compared to the path-norm, it fails to capture the complexity of the network end-to-end by decoupling the layers of neurons one from each other. Third, it has been empirically observed that products of operator norms negatively correlate with the empirical generalization error while the path-norm positively correlates (Jiang et al., 2020, Table ()(zuugeee et al., 2020, Figure 1).
3 GENERALIZATION BOUND
The generalization bound of this section is based on path-norm for general DAG ReLU network. It encompasses modern networks, recovers or beats the sharpest known bounds of this type, and applies to the cross-entropy loss. The top-one accuracy loss not directly covered, but can be controlled via a bound on the margin-loss, as detailed at the end of this section.
3.1 MAIN RESULT
To state the main result let us recall the definition of the generalization error.
Definition 3.1. (Generalization error) Consider an architecture G (Definition 2.2) with input and output dimensions dip and dous. and a so-called loss function E : Ridas x Rdda - R. The (-generalization error of parameters O on a collection Z of n Nso pairs of input/output zi = (Ii, vi) E du x Rdar and with respect to a probability measure je on IRda x Rdd is:
1 n
L- t-generalization error(0, Z.p) := E.xo. (Re (Xo), Yo))
e (Ro(z)))
test error
training error when trained 2
While all the other results hold for arbitrary biases, the next theorem holds only if the *-max- pooling neurons have null biases. For simplicity, we state the result when all the biases are null. We then explain how to extend the result when neurons & Ne-poo1 may have b, # 0.
Theorem 3.1. Consider a ReLU neural network architecture G (Definition 2.2) with null biases, with input/output dimensions do Denote D its depth (the maximal length of path from an
5

---

Published as a conference paper at ICLR 2024
input to output), P := (kk E Nzo, Eu E NN--poo)) the number of distinct rypes of s-max-pooling
neurons in G. K := maXuEN. poor aat(u)] its maximal kernel size (K == 1 if P = 0). Assume
Nia O Nout = 0. Consider a so-called loss function f: 1d x Rd + R and L > 0 such that
((),y) - E(22, y) & LIli - 122l22 Vy, 92 E support(Y)
(3)
Consider + iid random variables Z
Y.) M4 0 & i & with μ a prob- ability measure on input/output pairs in Rd x R and denote = (Z,) (=))==1....pp Define
a = (Exx max(n, Ei=1 (xxII1=)) 1/2
For any set of parameters O and any estimator : - O(Z) E θ it ho
40
fag-ggeneralization error (Z), (4) <
LC sup [+((0)] n ag
with flog being the natural logarithm)
3 + 2P
1/2
C = (log((3++2P))) (or(((++P)))) + log
din
1 P
Any neural network with nonzero biases can be transformed into an equivalent network (with same path-norms and same Rş) with null biases for every NN-pool: add input neuron Ubiss with constant input equal to one, add edges between this input neuron and every neuron v & N No with parameter 0 0 == b,, and set b, 0. Thus the same result holds with b, # 0 for É N No.pool. with din replaced by din + in the definition of C, and with an additional constant input coordinate
equal one in the definition of so that a = (Ex max (n, max Σ.= (x)) 1/2 > vn. The proof in Appendix F is directly given for networks with nonzero biases (except m-axxpooling neurons), using this construction.
Theorem 3.1 applies to the cross-entropy loss with = /2 (see Appendix G) if the labels y are one-hot encodings". A final softmax layer can be incorporated for free to the model by putting it in the loss. This does not change the bound since is 1-Lipschitz with respect the n.2-norm (this a simple consequence of the computations made in Appendix G).
On ImageNet, it holds 1//n= & a/n & 2.6/ /n (Section 4). This yields bounds that decays in 1/22) which is better than the generic O(n -/daa) generalization bound for Lipschitz functions (von Luxburg & Bousquet, 2004, Thm. 18) that suffer from the curse of dimensionality. Besides its wider range of applicability, this bounds also recovers or beats the sharpest known ones based on path-norm, see Table 1.
Finally, note that Theorem 3.1 can be tightened: the same bound holds without counting the identity neurons when computing D. Indeed, for any neural network and parameters 0, it is possible to remove all the neurons v E Na by adding a new edge u - w for any u E ant(v), w E suc(v) with new parameter 0n~r0"~-" (if this edge already exists, just add the latter to its already existing parameter). This still realizes the same function, with the same poth-norm, but with less neurons, and thus with D possibly decreased. The proof technique would also yield tighter bound but not by much: the occurences of 3 in C' would be replaced by 2.
Sketch of proof for Theorem 1.1. The proof idea explained below. Details are in Appendix F.
Already known ingredients. Classical arguments (Shalev-Shwartz & Ben-David, 2014, Theorem (M.rrr, 2016), that are valid for any model, bound the expected generalization error by the Rademacher complexity of the model. It remains to bound the latter, and this gets specific to neural
'The definition of the generalization error (Definition 3.1) has been given for deterministic 0 keep things simple. The careful reader will have noted that the term corresponding to the test error in Definition 3.1 to be modified when 0 is a function of Z. Indeed, the expectation has to be taken on an iid copy Z, conditionally on each Z,, i = I,..., n2: the test error should be defined as Ezo-g (E(Raiz) (Xv), Yo)IZ) ). This correct definition will he used in the proof, but it has importance here understand the statement of the theorem.
6 CClassical concentration results (Boucheron et al., 2013) can be used to deduce bound that holds with high probability under additional mild assumptions on the loss.
A vector y a one-hot encoding of class if y = (de==e)d

---

Published as a conference paper at ICLR 2024
networks. In the case of layered fully-connected ReLU neural network with no biases and scalar output (and no skip connections nor s-max-pooling even for a single given k), Golowich et al. (2018) proved that it is possible to bound this Rademacher complexity with exponential factor in the depth, by peeling, one by one, each layer off the Rademacher complexity. To get more specific, for a class of functions F and function V R IR, denote Rad o oV (F) E. (s(Ssppee Di=1 E: (2;)) the Rademacher complexity of F associated with n inputs z; and v where the E; are iid Rademacher variables (e; 1 or -1 with equal probability). The goal for generalization bound is to bound this in the case V (z) = id(x)= = z. In the specific case where FD is the class of functions that correspond to layered fully- coll--coneected ReLU networks with depth D. assuming that some operator norm of each layer d' is bounded by ra. Golowich et al. (2018) 8) basically guarantees Rad o (FD) < Rad of Arp (Fn-1) for every > O, where (x(r) = exp(Xr). Compared to previous works of Golowich et al. (2018) that were directly working with V/ = id instead of Vx,, the important point is that working with V gets the 2 outside of the exponential. Iterating over the depth D. optimizing over X, and taking a logarithm at the end yields (by Jensen's 's inequality) a bound on Rad (D)))) with a dependence on D that grows as v (2) instead of 2D for previous approaches.
Novelties for general DAG ReLU networks. Compared to the setup of Golowich et al. (2018), there are least three difficulties to do something similar here. First, the neurons are not organized in layers as the model can be an arbitrary DAG. So what should be peeled off one by one? Second, the neurons are not necessarily ReLU neurons as their activation function might be the identity (average-pool -ooggegpoonig) or *-max mnoxippooing. Finally, Golowich et al. (2018) has a constraint on the weights of each layer, which makes it possible to pop out the constant ra when layer is peeled off. Here, the only constraint is global, since it constrains the paths of the network through [+)]] & r. In particular, due to rescalings, the weights of given neuron could be arbitrarily large or small under this constraint.
The first difficulty is primarily addressed using new peeling lemma (Appendix E) that exploits new contraction lemma (Appendix D). The second difficulty is resolved by splitting the ReLU, t-max-pooling and identity neurons in different groups before each peeling step. This makes the 12g(2) term in Golowich et al. (2018) a log(3 + 2P) term here (P being the number of different k's for which t-max-pooling neurons are considered). Finally, the third obstacle is overcome by rescaling the parameters normalize the vector of incoming weights of each neuron. This type of rescaling has also been used in Neyshabur et al. (2015); Barron & Klusowski (2019).
O
Remark 3.1 (Improved bound with assumptions on *-max-pooling neurons). In the specific case where there is a single rype of k-max-pooling neurons (P 1). assuming that these k-max-pooling neurons are grouped in layers, and that there are no skip connections go- ing over these k-max-pooling layers (satisfied by ResNets, not satisfied by U-nets), sharp- ened peeling argument can yield the same bound but with C replaced by Csharpened = (Dlog(3) + MM log(K) + log((din + 1)dou))) 1/2 with M being the number of k-max-pooling lay- ers (af. Appendix E). The details are tedious so we only mention this result without proof. This basically improves /D log(5K) into vD (3) + M log(K). For Resnet152, K = 9, D = 152 and M = 1, /D 15g(5K) = 24 while vD log(3) + M log(H) K) 13.
3.2 HOW TO DEAL WITH THE TOP-1 ACCURACY LOSS?
Theorem 3.1 does not apply to the top-1 accuracy loss as Equation (3) cannot be satisfied for any finite > 0 in general (see Appendix H). It is still possible bound the expected (test) top-1 accuracy by the so-called margin loss achieved at training (Bartlett et al., 2017, Lemma A.4). The margin-loss a relaxed definition of the 1 accuracy loss. corollary of Theorem 3.1 is the next result proved in Appendix I.
Theorem 3.2 (Bound on the probability of misclassification) Consider the setting of Theorem 3.1. Assume that the labels are indices y E (1...., dout). ). For any ty >> 0, it holds
PP argmax Ro (x( # #Y,
1 (Raz (X,)),, &T+maxezy, (Rocz) (X,))
(4)
8o supe [10(0)] 1l
Y
7

---

Published as a conference paper at ICLR 2024
Table 2: Numerical evaluations on ResNets and ImageNetIk with significant digits. Multiplying by the Lipschitz constant L of the loss and the path-norm gives the bound in Theorem 3.1. The sec- ond line reports the values when the analysis is sharpened for max pooling neurons, see Remark 3.1.
ResNet CB=
18
34
50
101
152
0.088
0.11
0.14
0.19
0.23
Vn sharpened
0.060
0.072
0.082
0.11
0.13
Table 3: Path-norms of pretrained ResNets available on PyTorch, computed in float32.
ResNet
18
34
50
101
152
1
1.3 x 10.00
overflow
overflow
overflow
overflow
{(0) 2
2.5 10a
1.1 X 102
2.0
10
2.9 x 10
8.9 x 10
(0)44 x.2
4.9 x 10
6.7 10-
3.0 x 10
1.5 x 10
Note that the result is homogeneous: scaling both the outputs of the model and y by the same scalar leaves the classifier and the corresponding bound unchanged.
4 EXPERIMENTS
Theorem 3.1 gives the first path-norm generalization bound that can be applied to modern networks (with wverage/=-max-pooleee
skip connections etc.). This bound is also the sharpest known bound of this type (Table 1). Since this bound is also easy to compute, the goal of this section is to numer- ically challenge for the first time the sharpest generalization bounds based on path-norm on modern networks. Note also that path-norms tightly lower bound products of operator norms (Appendix C) so that this also challenges the latter.
When would the bound be informative? For ResNets trained on ImageNet, the training error associated with cross-entropy typically between and 2, and the top-1 training error is typically less than 0.30. The same orders of magnitude apply to the empirical generalization error. To ensure that the test error (either for cross-entropy or top-1 accuracy) is of the same order as the training error, the bound should basically be of order 1.
For parameters learned from training data, Theorem 3.1 and Theorem 3.2 allow to bound the expected loss in terms of a performance measure (that depends on free choice of y >> 0 for the top-1 accuracy) on training data plus a term bounded by 1a 1 Lx (00]]] The Lipschitz constant L is v2 for cross-entropee and 2/7 for the top-1 accuracy.
Evaluation of 1e C' for ResNets on ImageNet. We further bound o/n by B/ where is the maximum T,00_ -norm of the images of ImageNet normalized for inference. We at most lose factor B compared to the bound directly involving since it also holds a/n > 1/ //vn by definition of a. We train 99% of ImageNet that 1268355. Moreover, recall that C (D log((3 + 2)) + log( 3+2P I+P (din + 1)ddoa)) ) For ResNets, P 1 (as there are only classical max-pooling neurons, corresponding to k-max-pooll d--max-pooling with A: 1), the kernel size is K = 9, d,m 224 x 224 x3, des 1000, and the depth is D = 2 + basic blocks # conv per basic block, with the different values available in Appendix J. The values for 4BC/ /n are reported in Table 2. Given these results and the values of the Lipschitz constant L. on ResNet18, the bound would be informative only when | (0) 2 10 (0)) /v & 10 respectively for the cross-entropy and the top-1 accuracy.
2.6
We now compute the path-norms norms of trained ResNets, both dense and sparse, using the simple for- mula proved in Theorem A. in appendix.
L path-norm of pretrained ResNets are 30 orders of magnitude too large. Table 3 shows that the L path-norm is 30 orders of magnitude too large to make the bound informative for the cross- entropy loss. The choice of y is discussed in Appendix J, where we observe that there is no possible choice that leads to informative bound for 1 accuracy in this situation.
Sparse ResNets can decrease the bounds by 13 orders of magnitude. We jusu saw that pretrained ResNets have very large 7.A path-norm. Does every network with good test top-1 accuracy have
8

---

Published as a conference paper at ICLR 2024
such a large L' path-norm? Since any zero in the parameters @ leads to many zero coordinates in ((0). we now investigate whether sparse versions of ResNet18 trained on ImageNet have a smaller path-norm. Sparse networks are obtained with iterative magnitude pruning plus rewinding, with hyperparameters similar to the one in Frankle et al. (2021, Appendix A.3). Results show that the I. path-norm decreases from = 1030 for the dense network to 10T7 after 19 pruning iterations, basically losing between half and one order of magnitude per pruning iteration. Moreover, the test top-1 accuracy better than with the dense network for the first 11 pruning iterations, and after 19 iterations, the test top-1 accuracy is still way better than what would be obtained by guessing at random, so this is still a non-trivial matter bound the generalization error for the last iteration. Details are in Appendix J. This shows that there are indeed practically trainable networks with much smaller I,a path-norm that perform well. remains open whether alternative training techniques, possibly with path-norm regularization, could lead to networks combining good performance and informative generalization bounds.
Additional observations: increased depth and train size. In practice, increasing the size of the network (i.e. the number of parameters) or the number of training samples can improve generaliza- tion. We can, again, assess for the first time whether the bounds based on path- follows the same trend for standard modern networks. Table 3 shows that path-norms of pretrained ResNets available PyTorch roughly increase with depth. This is complementary to Dziugaite et al. (2020, Figure 1) where it is empirically observed on simple layered fully-comeectdd models that path-norm has difficulty to correlate positively with the generalization error when the depth grows. For increas- ing training sizes, we did not observe a clear trend for the L path-norm, which seems to mildly evolve with the number of epochs rather than with the train size, see Appendix J for details.
5 CONCLUSION
Contribution. To the best of our knowledge, this work is the first to introduce path-norm related tools for general DAG ReLU networks (with average/s-max-pooliss rem 3.1 the first generalization bound valid for such networks based on path-norm. This bound recovers or beats the sharpest known ones of the same type. Its ease of computation leads to the first experiments on modern networks that assess the promises of such approaches. A gap between theory and practice is observed for a dense version of ResNet18 trained with standard tools: the bound is 30 orders of magnitude too large on ImageNet.
skip connections), and Theo-
Possible leads to clase the gap between theory and practice. 1) Without changing the bound of Theorem 3.1, sparsity seems promising to reduce the path-norm by several orders of magnitude without changing the performance of the network. 2) Theorem 3.1 results from the worst situation (that can be met) where all the inputs activate all the paths of the network simultaneoouly. Bounds involving the expected anth-activations could be tighter. The coordinates of ((0) are elementary bricks that can be summed to get the slopes of Rg on the different region where Rg is affine (Arora et al., 2017). [0))) is the sum of all the bricks in absolue value, resulting in a worst-case uniform bound for all the slopes. Ideally, the bound should rather depend on the expected slopes over the different regions, weighted by the probability of falling into these regions. 3) Weight sharing may leave room for sharpened analysis (Pitas et al., 2019; Galanti et al., 2023). 4) A k-max-pooling neuron with kernel size K only activates 1/K K of the paths, but the bound sums the coordinates of i related to these K paths. This may lead to a bound K times too large in general (or even more in the presence of multiple maxpooling layers). 5) Possible bounds involving the L path-norm for q >>> deserve a particular attention, since numerical evaluations show that they are several orders of magnitude below the T,- norm.
Extensions to other architectures. Despite its applicability to wide range of standard modern networks, the generalization bound in Theorem 3.1 does not cover networks with other activations than ReLU, identity, and s-max-pooling The same proof technique could be extended to new acti- vations that: 1) are positively homogeneous, so that the weights can be rescaled without changing the associated function; and 2) satisfy contraction lemma similar to the one established here for ReLU and max neurons (typically requiring the activation to be Lipschitz). A plausible candidate is Leaky ReLU. For smooth approximations of the ReI.U, such as the SiL.U (for Efficient Nets) and the Hardswish (for MobileNer- V3), parts of the technical lemmas related to contraction may extend since they are Lipschitz, but these activations are not positively homogeneous.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by the AllegroAssai ANR-19-CHIA-0009 and NuSCAP ANR-20- CE48-0014 projects of the French Agence Nationale de la Recherche.
The authors thank the Blaise Pascal Center for the computational means. uses the SIDUS (Quemener & Corvellec, 2013) solution developed by Emmanuel Quemener.
REFERENCES
Pierre Alquier. User- User-friendly introduction PAC-Bayes bounds. CoRR, abs/2110.11216, 2021. URL
atsp/bs//2211 2210. 11216.
Cem Anil, James Lucas, and Roger B. Grosse. Sorting out Lipschitz function approximation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning, ICML. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 291-301. PMLR, 2019. URL www. wa...pees/v977 aaa//annnl1l.. html.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. Electron. Colloquium Comput. Complex. 24:98, 2017. URL
https://eccc. wei zmann ac ama.n.a..../reprr...t..o....
Francis Bach. Learning from first principles, 2024. URL https:///wet ens..iiieed...............e fr/
Francis R. Bach. Breaking the curse of dimensionality with convex neural networks. J. Mach. Learn.
Res., 18: 19:19911, 2017. URL http: //tp://mmmrrr www.m.orr......oo....o...oo.oooo http://w...o.pppp//////////////e 1414-444..6111 htmmm...t1...
Andrew R. Barron and Jason M. Klusowski. Complexity, statistical risk, and metric entropy of deep nets using total path variation. CoRR, abs/1902.008000, 2019. URL http::/arxiv.ort
abss19003 00800.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities Risk bounds and structural results. Mach. Learn. Res., 3:463-482, 2002. URL http://jmll http:://mmmr.rrr//.//e org/ papers/ve ///////aeettttteeeeeeeeeeeaaaaae 02a html.
Peter L. Bartltt, Dylan J. Foster, and Matus Telgarsky. Spectrally-normaizzed margin bounds for neural networks. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gameet (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural In formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA, pp. 6240-6249, 2017. URL httpt::://///ooeo http://///ooeeeeeeeeeeeee tewerrrss... cc pappp/ppp1/////////// b226257ad05 9d4 90d4000000dacccccccoooooooo Abst html.
Joachim Bona-Pellissier, François Malgouyres, and François Bachoc. Local identifiabil- ity of deep relu neural networks: the theory. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems 35: Annual Conference on Neural Information Process- ing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022. URL http:::/ppppes...t. b0ae04 Baa.aa/e...aaa11111110000ee---a.
httpppppe_flllsspppppre////////e html.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities. Oxford Uni- versity Press, Oxford, 2013. ISBN 978-0-19-953525..
doi: 10. 00110993hhpm00000077719993333333 fr/10. A nonasymptotic theory of indepen-
001.0001. URL ht https: http:::///doooorggdda. acces. bibliiiibi 1093/acpros : oso/ 90 dence, With a foreword by Michel Ledoux.
001. 0001.
Patrick L. Combettes and Jean- -hrrishistepphe Pesquet. Lipschitz certificates for layered network struc- tures driven by averaged activation operators. SIAM J. Math. Data Sei., 2(2))529-557, 2020. doi: 10.1137/1MM127221 URL https:://///..... /ttp///o....o org / / 9M1 272780.
10

---

Published as a conference paper at ICLR 2024
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. ISBN 978-0-262-03388--. URL http:
//mitt/taae/t //mitppess.... mmittsss.it............
Ronald A. Verere Boris Hanin, and Guergana Petrova. Neural network approximation. Acta Numer. 30:327 444, 2021. doi: 101007750062242220000522 URL attps://doi..
10. wwe.1111770062222229000
Gintare Karolina Dziugaite. Revisiting Generalization for Deep Learning: PAC-Bayes, Flat Minima, and Generative Models. PhD thesis, Department of Engineering University of Cambridge, 2018.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Gal Elidan, Kristian Kersting, and Alexander Ihler (eds.). Proceedings of the Thirty-Third Conference on Uncertainty Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017. AUAI Press, 2017. URL http: /al:://auuss auaa.
uai www.uiiii....... 2017 http://pcceeee/////pe//e http://///....//////eeeeoo.gggg.
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M. Roy. In search of robust measures of gen- eralization. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien -iean Lin (eds.), Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL (6d7c8008bb aaa ctt.llcccc9999955555 Abst html.
neurips.......... ccc
Weinan E, Chao Ma, and Lei Wu. The Barron space and the flow-induced function spaces for neu- ral network models. Constr: Approx., 55(1):369-406, 2022. ISSN 0176-4276. doi: 10.1007/ URL https: /ttp://doooop/ htttps://doioogg.ooeee acces. www.:ee..bbbllttteeueuueeeee.eer Er/10. 500000000000005000000000 020-00036--2---55----030
000365-021-0954944
Jonathan Frankle, David Schwab, and Ari S. Morcos. The early phase of neural network training. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL WRRLtttss//ppeeeer//ee /wwp///ppneeeeeeeeeeee net forum? id= Hkll Mkl1iRNEWss wS.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https::/ net/ http://wwwweeeeettteteeeeea forum?id=Ig VyQc-MLK.
Yasutaka Furusho. Analysis of Regularization and Optimization for Deep Learning. PhD thesis, Nara Institute of Science and Technology, 2020.
Tomer Galanti, Mengjia Xu, Liane Galanti, and Tomaso A. Poggio. Norm-based generalization bounds for compositionally sparse neural networks. CoRR, abs/2301. 2023. doi: 10. 48550kacrXiv2331..1220 URL https: /oi.. oog///lgg./oooooo.oo w18550/aaXiii. 2301. 12033.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume of Proceedings of Machine Learning Research, pp. 297-299. PMLR, 2018. URL http: http://pooceeeeeee ngs. /vteess/v5/// / ool oow ch Ba html.
m1 r. w..pres//vv
Antoine Gonon, Nicolas Brisebarre, Rémi Gribonval, and Elisa Riccietti. Approximation speed of quantized versus unquantized relu neural networks and beyond. IEEE Trans. Inf. Theory, 69(6): 3960-3977, 2023. doi: 10. 11199TTT2202332440366 URL https: /tt:://dciiioo wtriddi..og/o...11
3240360.
Antoine Gonon, Nicolas Brisebarre, Elisa Riccietti, and Rémi Gribonval. Code for reproducible research A path-norm toolkit for modern networks: consequences, promises and challenges, March 2024. URL http::/s//.aaa..ccccccc/aaaaaaa. v1.0.0 at https: // //gttub.... com/ available directly that git repository.
It is the code tagged with wtw.:hhoooomtoooooeeeooooo and any updates will be
11

---

Published as a conference paper at ICLR 2024
Benjamin Guedj. A primer PAC-Bayesian learning. CoRR, abs/ 1asss/9900.0555,, 2019. URL http: //arxivv.. oxg/ aba/ /
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770-778. IEEE Computer Society, 2016. doi: 10.1109/CVPR.2016.900 URL https: htt////oii./ org/logg///oooooooooooooo /0009///2.222.....
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nel, 2020. URL https:://ppereetteeee
net forum? S JBPVH..
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear predic- tion: Risk bounds, margin bounds, and regularization. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou (eds.), Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference Neural Information Processing Sys- tems, Vancouver, British Columbia, Canada, December 8-11, 2008, pp. 793-800. Curran As- sociates, Inc., 2008 URL https: http///tceeeeggggeeee//e heuripppss cc/ pccppaper/2008 //ash// 5b69b9cb830 0aa.a/88666646113333333337378300 700955 oatt Abtteeat.tttttttttttaamt
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning.
CoRR, abs/1710.05468. 2017. URL http:// http///axvvv... wwwg/bs./////ooooooeeo//oo//ebbe abs/1710, 05468.
Michel Ledoux and Michel Talagrand. Probability in Banuch spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results Mathematics and Related Areas (3)J. Springer- Verlag, Berlin, 1991. ISBN 3- / //doi.org/// 10. 1007/978 3- 642 20212- 4. Isoperimetry and processes.
doi: 10.1007/978-3- 20212-4. URL https:
Sibylle Marcotte, Rémi Gribonval, and Gabriel Peyré. Abide by the law and follow the flow: Conser- vation laws for gradient flows. CoRR, abs/2307.001144 2023. doi: 10.485550/rXx1:2337.0001
URL https: / doi org/ 485.0/.8555//88 arriv...ivvvv.////i 2307. 00144.
Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles (eds.), Algoritumic Learning Theory 27th International Conference, ALT 2016, Bari, Italy October 19-21, 2016, Proceedings, volume 9925 of Lecture Notes in Computer Science, pp. 3-17, 2016. doi: 10.
URL https:
//doi.org/////// www.oogg/1.... 10011000//90 978 31108833-330 3-1--1---0 46379-7_1.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pp. 11611-11622, 2019. URL 2a555//cccebbb444ccoo0bbbbbbbbb. Abbtt html.
neurips. wewrips..ccpapee//aaa... cc/paper/2019/
Behnam Neyshabur. Implicit regularization in deep learning. CoRR, abss/179.00195 2017. URL http://arxivv
abs//b09.000
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neu- ral networks. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.). Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pp. 1376-1401. JMLR.org. 2015. URL http:/
http://proceed/ /ttp///eeoeccn.epee/eeeeeee mll...r...... press/v40 /t/p//////NNyyya 1..ml..
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gamett (eds.). Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA, pp- 5947-5956, 2017. URL Dee
http://ppp....cppaa//11111111111 pttpp//pppp///////////p //ah//hhhhh/////// html.
12

---

Published as a conference paper at ICLR 2024
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to opectraly-normaalzee margin bounds for neural networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: wtt.tttpss//ppeerreeee// http:///eeeeeeeeeeeeeeeeee
Forum?id=Skz d_wbcck
Guillermo Valle Pérez and Ard A. Louis. Generalization bounds for deep learning. CoRR, abs/2012.04115, 2020. URL https: wwtp...wog//a///222..002
Konstantinos Pitas, Andreas Loukas, Mike Davies, and Pierre Vandergheynst. Some limitations of norm based generalization bounds in deep neural networks. CoRR, abs/1905.0960 099977700777, 2019. URL
http:/ /arxiv arxiv org/abs/////ooooooor.t...//..r abs /1905 0tte/19555006......
E. Quemener and M. Corvellec. SIDUS the Solution for Extreme Deduplication of an Operating System. Linux Journal, 2013.
Michael Eli Sander, Joan Puigcerver, Josip Djolonga, Gabriel Peyré, and Mathieu Blondel. Fast, dif- ferentiable and sparse top-k: a convex analysis perspective. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, vol- ume 202 of Proceedings of Machine Learning Research, pp. 29919-29936. PMLR, 2023. URL /ttt::://proceeeeeee htt.::/s..........//..m.e /v202/ http///22222aaaaaaaeeeee
mlr
sander2 aatieerr3aahtt..
From Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning
URL Theory to Algorithms. Cambridge
University Press, 2014.
ISBN 978-1-10-
705713-5.
det
httpe////aaaame//acaeeeeeeeeee subjects/
Pierre Stock and Rémi Gribonval. An embedding of ReLU networks and analysis of their iden- tifiability, Constr: Approx. 57(2):853-899, 2023. ISSN 0176-4276,,433--999.. doi: 10.1007/
s00365-022-09578- URL httpps:///ot http:////......o.......//0000000
Ulrike von Luxburg and Olivier Bousquet. Distance- based classification with Lipschitz functions. Mach. Learn. Res., 5:669-695 695, 2004. URL /ttp://jmmr.. hwwpal..rrpppprr//////eeaaesssss (aappers/vouums//
luxburg04br http//luuur000.... pdf.
Martin Wainwright. High-dimensional statistics, volume 48 of Cambridge Series Statis- tical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019. ISBN
978-1-108-49802-99 doi: 10.1017/978100862771. URL https:://tii-eee acces. point.
A non-asymptotic view-
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3):107-115, 2021. doi: 10. 10.1145/3 URL https: doii.....///
Shuxin Zheng, Qi Meng, Huishuai Zhang, Wei Chen, Nenghai Yu, and Tie-Yan Liu. Capac- ity control of ReLU neural networks by basis-path norm. In The Thirty- Third AAAI Con- ference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Ar- tificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Ad- vances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 Febru- ary 2019, pp. 5925-55559999 5932. AAAI Press, 2019. doi: 10. 10.1609/aaai.v333 a33iaii.v33311... 0330011.3301925, URL. https: http://ooooo.....//// /aaai 033101.33015922
13

---

Published as a conference paper at ICLR 2024
Supplementary material
A MODEL'S S BASICS
Definition A.3 introduces the path-lifting and the path-activations associated with the general model described in Definition 2.2. We choose to call path-lifting as in Bona- cona-Pellissser et al. (2022) (and not embedding as initially named in Stock & Gribonval (2023), since is not injective). Formally, a lifting in the sense category theory would factorize the mapping 0 + Rg. which is not the case of 0 (0). but the case with the extended mapping (0), (()).. We chose the name lifting for (0) for the sake of brevity.
in Definition 2.2. A path of G is any sequence of neurons Up...., .aa such that each 1; + V/+1 is an edge in G. Such path is denoted p Up - ... - Ud. This includes paths reduced to a single v N. denoted p = v. d (the number of edges). We will denote Pe == ve the l-th
Definition A.1 (Paths and depth in DAG). Consider a DAG G (N,
The length of a path is length(p) newron for a general & E {O...., length(p)) and use the shorthand Pand = Viength(p) for the last neuron. The depth of the graph G is the maximum length over all of its paths. If ud+1 E suc(pena) + vat1- We denote by pG (or simply P) the set of
then - vd+1 denotes the path to +
paths ending at an output neuron of G.
Definition A.2 (Sub-graph ending at given neuron). Given neuron v of DAG G, we denote G the graph deduced from G by keeping only the largest subgraph with the same inputs as G and with single oulput: every neuron u with path reach through the edges of G is removed, as well as all its incoming and outcoming edges. We will use the shorthand p-v = pG- to denote the set of paths in G ending
Definition A.3 (Path-lifting and aath-activations). Consider a ReLU neural network architecture G as in Definition 2.2 and parameters 0 BC associated with G. For p E P, define
langth(p)
0 0
io E Ni:
(0)
(ength(p)
Upo
otherwise,
where an empty product is equal to by convention. The path-lifting & (0) of
(0) (0) pEpa.
This is often denoted 4 when the graph G is clear from the context. We will use the shorthand t = to denote the path-lifting associated with - (Definition A.2).
G. The activation of an edge + (0, x) is defined to be Ou-ro (0,x) when v is an identity neuron; (0, )) = 1 x(0xx)>0 when u is a ReLU neuron; and when v a --max-pooling neuron, define au-+0 (0, ) the neuron u is the first ant(v) lexico- graphic order to satisfy u(O u(0,z) = k-pool (ww(0, wee)t((v)) and an-so x) 0 otherwise. The activation of neuron on (0, x) is defined to be (0.zz)
Consider input G.
1 if u is an input neuron, an identity neuron, or a k-max-pooling neuron, and 0,((0 == (e(0,))>0 if v is a ReLU neu- ron. We then define the activation of path p E P with respect input x and parameters as: length(p))
a,,(6 (,,0.x) := app (0, I a.y-1-v, (0, x) (with an empty product set to one by convention). Consider a new symbol Unias that is not used for denoting neurons. The path-activations matrix A(O œ) is defined as the matrix in Px (Nau(vaaa)) such that for any path E P and neuron
Non {Vossa)
1 1 (0(0 x)
if E Nin otherwise when u Ubias-
(A(O,x))p. =
The next lemma shows how the path-lifting and the path-activations offer an equivalent way to define the model of Definition 2.2.
Lemma A.1. Consider a ReLU network as in Definition 2.2. For every neuron v, every input a and every parameters 0:
v v00.)) (t)) >' (0,x)
(5)
14

---

Published as a conference paper at ICLR 2024
Proof of Lemma A.I. For any neuron e, recall that p- is the set of paths ending neuron (Def-
inition A.2). We want to prove
1 )
v(0,z) x)
1 (0), A 10 (0,z)
Σ 1 ap 0 po рEР-
(6)
where we recall that po denotes the first neuron of a path p (Definition A. For paths starting input neuron, Tpo is simply the corresponding coordinate of x. For other paths, convention Zu == for any neuron u E N Ni.
the
The proof of Equation (6) goes by induction neurons. We start with input neurons since by Definition 2.2, these are the ones without antecedents so they the first to appear in topological sorting. Consider input neuron v. The only path in pp* y v. By Definition A.3, it holds (0) (empty product) and 0p (0, x) = (f. 1. Moreover, have v(0,z) z) Ty (Definition 2.2). This proves Equation (6) for input neurons.
topological sorting Cormen et al. (2009) of the
Now, consider v & Ni and assume that Equation (6) holds true for every neuron u E ant(v). We first prove by cases that
r0 x) (0,0
Σ
(0
(Eant(v)
Case an identity neuron. is an identity neuron, then by Definition 2.2
u ( x by +
Σ (Eant(v)
u(f, (00
Moreover, by Definition A.3 we have og (0,xz) = and On 0n--v = 1, since v is an identity neuron, so that the previous equality can also be written as
v0 x) = (0, + Σ
(0.
MEant(n)
This shows Equation (7) in this case.
Case of ReLU neuron. is ReLU neuron then similarly
v(0,x) = ReLU by +
Σ
u(0,z)00
000++
100,2)00
bu+ Σ
u(0, x) vu
uEant(v)
wEant(u)
10(0x)200 bv
Σ u(0,x))
1 ()0 0"
(Eant(o)
=a.(0.z)
(0.z)
This shows again Equation (7).
Case of a k- k-max-pooling neuron. When a k-max-pooling neuron, it holds:
v00, .)) = k-pool (bb, + u(0, 0" (uaan(())
b, +
Σ
I
realize this k-poo1 a00xz)00~v
(Definition 2.1)
(n)
mo (0 (0..) (Definition A.3)
Og (
by +
Σ
(0.
=1 (Definition A.3)
uEant(v)
This finishes proving Equation (7) in every case. Using the induction hypothesis on the antecedents of v, Equation (7) implies
v0,x)) a. x),
Σ
Σ
(0(0)a,(0,x)))) 2)
20)
wEant(w)
pEP-
15

---

Published as a conference paper at ICLR 2024
We want to prove that this is equal to
Σ (0,0)ap(0,x))p)) pEP
path p E P either the path p = e starting and ending at v, or it can be written a unique way antecedent of For the simple path ý
as p = p - where p E p- is a path ending (0, (0.z), Φp( ( = b, and by the convention used holds by definition (Definition A.3): az(0, .) = a,
in this proof we have 3io = Ii since is not input neuron. This shows:
a. ( bb (0)00a 2x)
When p= as above, it holds by definition: Ipo 2j pp(() (p)00)"~ and ap(0,z) x) (0, x). It then holds:
c 0 ap 0, x x) Qu- (0, 0) $
This concludes the induction and proves the result.
straightforward consequence of Lemma A.1 that path- path-norms norms can be used bound from above the Lipschitz constant of x + Ro(x).
Definition A.4. (Mixed path-norm) For 0 < 9. < oo, define:
[0(()) = (1] (1)l))))))))))
(8)
Lemma A.2. Consider < < cc. For every parameters and inputs I, x²:
[[)(2)) - Re x ||, < |1 2011
For 1, we simply have [0))),,,- [0))]] For this specific value of and in the specific case of layered fully-connected neural networks without biases, the conclusion of Lemma A.2 is already mentioned in Neyshabur (2017, before Section 3.4), and proven in Furusho (2020, Theorem 5). Lemma A.2 extends it to arbitrary DAG ReLU networks, and to arbitrary E (0, oo]. This requires the introduction of mixed path-norms, which, to the best of our knowledge, have not been considered before in the literature.
Proof of Lemma A.2. Consider parameters 0. Consider inputs x, with the same path-activations with respect to 0: A(O, x) A(O, x'). For 0 < < oo:
)
A - (0, ( x'
)
Ro(x) (x) - Ro(x')1l
Σ
+
A (0,x) x))
Lemma A.I.
NEN
| (0)]i
(0,z)
1
A 0
(0, x¹)
x'
Hölder NeN.
A A (0,r)) ((
x'
T (0)
1
A(0,, VEN
1 (0)
x 2/
|A 10- <1 NeN
(0) x 1'1
When 0 < < 00, we just proved the claim locally on each region where the path-activations A(,,) -) are constant. This stays true on the boundary of these regions by continuity. It then expands to the whole domain by triangular inequality because on any segment joining any pair of inputs, there a finite number of times when the region changes. The proof can be easily adapted to
Another straightforward but important consequence of Lemma A.1 is that mixed path-norm can be computed in a single forward pass, up replacing e-maxppoling neurons with linear ones.
16

---

Published as a conference paper at ICLR 2024
Figure I: Example of a network where one must replace the max-pooling neuron to compute the path-norm with single forward pass in Equation (9).
Theorem A.1. Consider an architecture G = (N, E, (Po)OEN(NN) as in Definition 2.2. Consider
the architecture G == (N, E, (Po)ueN)N..) with pa == id if E No.pool. and Pa == Pv otherwise. Consider y E (0, (z), r E (0, oo] and arbitrary parameters 0 E RC = R For vector denote |a|a the vector deduced from a by applying x + |x11 coordinate- Denote by 1 the input full of ones. It holds:
(0) = | (1))1/4 1|r.
(9)
Moreover, the formula is false in general if the x-max-pooling neurons have not been replaced with identity ones (i.e. if the forward pass done on G rather than G).
Proof of Theorem A.I. Figure shows that Equation (9) is false if the --max-pooliinn neurons have not been replaced with identity ones as the forward pass with input yields output 1 while the L' path-norm is 2.
We now establish Equation (9). By continuity in 0 of both sides of Equation (9), it is sufficient to prove it when every coordinate of 0 in E is nonzero. Note that by Definition A.3, the path-lifting &C and &G associated respectively with G and G are the same since G and & have the same underlying DAG. Denote by & &C Φ the common path-lifting, and by a the path-activations associated with G. Denote by p the set of paths ending at given neuron of G. According Lemma A.1, it holds for every output neuron of G with 1, using the convention Tu = if Nin
(1 (1)). = Σ
2,(10)) (101 = Σ PEP-"
( (109,,1)
PEP-"
Since we restricted to 0g with nonzero coordinates, 0gl has positive coordinates. As G has only identity or ReLU neurons, it follows by simple induction the neurons that u(10 9, 1) for every neuron u of G. Thus, every path E pG is active, ie., (10 = Definition A.3, ((01)) = (0)1%, we obtain:
Since by
(R (1)) PEP
Σ
(0) 1 (
The claim follows by Definition A.4.
B NORMALIZED PARAMETERS
In the sequel will be useful to restrict the analysis to normalized parameters.
Definition B.1. Consider q & co. Parameters O are said q-normalized if for every N \ (Now U Nn):
s +x (0))l) = (1(())
(0,
and if this is 0 then it also holds 00 = (outgoing edges v).
Thanks to the rescaling rescaling-ivvariance of ReLU neural network parameterizations, Algorithm allows to rescale any parameters 0 into normalized version i such that Rg Ro and +(0) +()))
17

---

Published as a conference paper at ICLR 2024
(Lemma B.1). The function p E {id, ReLU, k-pool}: p(z) = p(Ar) for every X > 0 and x R.
due to the positive-homenn homooeeeitt of every activation
Algorithm The first line of the algorithm considers topological sorting of the neurons (Cormen et al., 2009, Section 22.4), i.e. an order on the neurons such that u + v is an edge then u comes before in this ordering. Such order always exists (and it can be computed in linear time). Moreover, note that a classical max-pooling neuron (corresponding to a k-max-pooling neuron with & constant incoming weights all equal one, and biases set zero) has anymore its incoming weights equal to one after normalization, in general. This has no incidence on the validity of the generalization bound on classical max pooling neurons: rescaling is only used in the proof to reduce to another representation of the parameters that realize the same function and that is more handy to work with.
Algorithm Normalization of parameters for norm y (0, oo]
1: Consider a topological sorting U1,-.., Uk of the neurons
2: for U...... do
3: if of N Nour then
4:
A
bv
5:
if Ao
0 then +
6:
7:
else
0 +
g+
8:
normalize incoming weights and bias
by
to
by
9:
An
x Ou+
b rescale outgoing weights to preserve the function Ra
Lemma B.1. Consider q (0, 00). If 0 is the output of Algorithm for the imput Ô then 0 is q-normalized (Defimition B. I), Ro Rg and + (0) (()).
Proof. Step 1. We first prove that for every v E N (N U Nou)):
I(
0 b, )l, 10.
(10)
Consider v $ Nin U Nout- Right after v has been processed by the loop of Algorithm (line 2), it is clear that Equation (10) holds true for It remains to that b, and 0-* not modified until the end of Algorithm 1. A bias can only be modified when this is the turn of the corresponding neuron, b, is untouched after the iteration corresponding to And 0~ can only be modified when treating antecedents of v, but since antecedents must be before e in any topological sorting,
( )l.
0 0+
they cannot be processed after v. This proves that
E 10.
by
Step 2. We now prove that if (
+"
)l.
0 then it also holds 00- O (outgoing edges of v).
by
Indeed. ( 0~+
by ][{
= 0 implics A, = in Algorithm 1, which implics that - = 0 right after
rescaling (line 6) at the end of the iteration corresponding to v. Because the next iterations can only involve multiplication of the coordinates of go by scalars, - 0 is also satisfied the end of the algorithm. This proves the claim.
Step 3. In order prove that O is g-normalized, it only remains establish that (
- b,
llg- We prove this by induction on topological sorting of the neurons.
A useful fact for the induction is that for every u & Ni:
( (0) (uenn(()) )
(11)
by
18

---

Published as a conference paper at ICLR 2024
where recall that 4 "-)"()) = for input neurons Equation (11) holds because & -M is the path-lifting of G (see Definition A.2), and the only paths in G are p = v, and the paths going through antecedents of (t has antecedents since it is not an input neuron).
Let's now start the induction. By definition, the first neuron v & Nu in topological sorting has only input neurons antecedents. Therefore, + ("*"(0) (0) 1 for every ant(u). Using Equation (11), we get
1u = |( 0~ by
(0)0(0))1 = 16,19 +
Σ (Eant(
This shows the claim for v.
Assume the result to true for & Mi and all the neurons before y in the considered topological order (in particular, for every E ant(u)). By Equation (11), we have
+ "2 (0)1g g- = |b,1 +
Σ
(0)))
21..
aEAnt(v)
|| 1- (0) =1 gu
The induction hypothesis guarantees that Cu
11g for every
bu
an)(v). By Equation (10), we also have Cu. E 1) for every E an)( When 1, it clearly as proved above, and
holds | 0 0u-019
100019 Otherwise, Gu = O, hence 0u
we also obtain $ +* (0)ll 1 10 1 We deduce that
(0)
0 - 1'r by
④ (0) |bol
Σ wEant(v)
10-0011
This concludes the induction.
Step Each the activation functions E {id, ReLU, k-pool} is positive homogeneous, so clas- sical arguments for layered fully-connected networsk (see e.g. (Stock & Gribonval, 2023, Lemma and Theorem 1)) are easily adapted to show that Rg and ((0) are both unchanged at each itera- tion of Algorithm where X * O. Inspecting the iterations involving neuron such that X reveals that: (i) (,) = O is unchanged for all paths going through this neuron; (ii) ( is also unchanged for other paths since they only involve entries of 0 that are kept identical. As result, ((0) is also preserved at each such iteration. Finally, for each of the considered activations, A for any x (Equation (1)), so setting the outgoing weights 0 0 does not change Rg. This completes the proof.
implies that v0,
C PATH-NORMS AND PRODUCTS OF OPERATOR NORMS
For < q & 0o, recall that the mixed (quasi-)norm ||M ol of matrix M is:
|| 1l,.o
max ||row|lq- zow of M
For 1, this is the operator norm of M induced by the -nrm on the input and output spaces. As consequence, this is the Lipschitz constant of Mr b with respect to these norms, and by composition, it is well-known (see, e,g., Combettes & Pesquet (2020), where tighter bounds are also provided) that it can be used to derive bound on the Lipschitz constant of layered fully-connected ReLU networks.
Lemma C.1 (see, egg., Combettes & Pesquet (2020)). For a foxyeredfullly-coneeetee. ReLU network with biases of the form
Ro(x)= Mr ReLU Rel..RRRLL b1) + bb-1) ))-r)))))) + bL.
holds for every x, x' and for q ==
L
|| [o(x)) Ro &
I
[ [|Mellg.00 || - 10-x'l I'looo
19

---

Published as a conference paper at ICLR 2024
Proof. As this is well-known only reproduce the proof for L 2, and the general case easily follows by an induction: (highlighting in orange x and x'):
|Ro (a) Ro(x'' ||M₂ ReLU(M æ + b2) b2 - M2 ReLU b1) + b2llo
||M2 (ReLU + bi) ReLUUM + +b1))lls
|, [RLLU(M<= + b1) - ReLU(M{2 + b,)l
[M2]]1, |M b1 - -M billo
ReLU is I-Lipschitz
| [M (æ (xl22
|, Mi 1,00 || - x' 2ll
L
Another bound on the Lipehitz constant with respect to the -nrm on both the input and the output is the mixed path-norm (0) (Lemma A.2), which is even valid for an arbitrary DAG ReLU network. Is there any relation between the mixed path-norm (0)]) and the product of operator norm I se for layered fully-connected networks (LFCNs))
Comparing the Lipschitz constants for a scalar-valued LFCN. It is known that for scalar-valued (i.e., with dost = 1) LFCN without biases, corresponding to Rg Rx(x) Mr. M Re),,(M,z)), the bound [[ < I ||Mellg,oo holds (Neyshabur et al., 2015, Theorem 5) for every 0 < q & oc, with equality if the parameters have been rescaled properly. In the specific case of scalar-valued DAG ReLU network. it holds (0))l,, = (0) ll (Defini- tion A.4). Thus, the result from Neyshabur et al. (2015) shows that the mixed path-norm [f
a tighter Lipschitz bound than the product of operator norms I |Mell. in the specific case of scalar- LFCN.
We now extend the comparison made in Neyshabur et al. (2015) from a scalar-valued LFCN without biases to an arbitrary DAG ReLU network. We will again derive that the mixed path-norm is lower bound on (an extension of) the product of layers' norm for a general DAG ReLU network. Compared Neyshabur al. (2015), this requires both our extension of the notion of path-norm to mixed path- norms, and extending the notion of product of layers' norm to deal with DAG.
From now on, we always consider g E (0, oo) and E (0, 5o) if not specified otherwise.
From scalar-valued to vector-valued networks: from standard to mixed L'-norms. Lemma A.2 shows that going from scalar-valued network (LFCN or, more generally a DAG) to vector- valued network requires going from standard Ls-norms (()))) as considered in Neyshabur et al. (2015), to mixed Lo-norms (0))llg which is, to the best of our knowledge, first introduced in Definition A.4.
From LFCN to DAG: extending the product of layers' norm. There no notion "layer" M, in a general DAG, hence the product II ||Mell makes no sense anymore in this general context. We now introduce quantity that generalizes this product for general DAG.
Definition C.1. Consider q E (0, oo). For practical purposes, we denote to by when e N \ Nm. and To == 1 if E Ni. For every puth p P, consider
1/4
langth(p) Σ
langth(p) II
[TO0 p. g)= =
hime
10
+P
11
(12)
t=
k=
with the convention that empty product is equal one. For q E (0, oo) and (0), define:
(0)) = [ mmx
((O.P.4)
(13)
PEP-10
vEN
Let us check that IT 0. generalizes the product of layers' norm to arbitrary DAG.
20

---

Published as a conference paper at ICLR 2024
Lemma C.2. Consider (0, oo). In a LFCN Ro(x) My ReL ... (cLU(M2)) with layers and without biases, it holds:
9:00 (0)
Mellg.
Proof. In LFCN, all the neurons of two consecutive layers are connected, so I Mel is also the maximum over all paths starting from an input neuron (and ending at an output neuron, by definition of P)) of the product of L--norms:
length(p)
II
Me
max Pe PEP.PoENa
II Em1
0
Zmi
Since there are no biases (corresponding to Thu = bu = for every & Nin) we have
length(p) t=1
110 10000 l1g
if Po E Nm. otherwise.
11 (.9)
This shows the claim:
IT 9,00 (0)
max max IT(O, max IT(O, PEP
4)
NoNo PEP-+0
length(p)
length(p)
max PEP
00 PE 11g
II 8=1
Mell
The next theorem proves that the mixed path-norm is a lower bound on this extended product of layers' norm. In particular, this shows that the Lipschitz bound given by (0)()) (which is computable in a single forward-pass by Theorem A.I) is always at least as good as the one given by II | for LFCN without biases. This extends as claimed the result from Neyshabur et al. (2015) to the vector valued case.
Theorem C.1. Consider q (0, 00) and 00]. For every DAG ReLU network (Definition 2.2)
and every parameters 0:
[1+(0))l.rr (o).
If 0 is q-normalized (Definition B.I) then:
=]((((
θ by Ne.
[b0(0)l = Tgg.(())
Input x XER
Output
R
0 M
Figure 2: A network which path-norm is zero while the product of operator norms scales as M
Proof of Theurem C.I. First, when 0 is g-normalized, by Definition B. and Equation (8):
(1(( 0 b, )I!) NEN...
Φ (
Let us prove by induction on a topological sorting of the neurons that for every u E N:
| (0))l & max ITO,p.
(14)
pEP-
21

---

Published as a conference paper at ICLR 2024
with equality if 0 is g-normalized. As direct consequence of Equations (8) and (13), this will prove that [[ g.r & [lq.r(0). with equality when 0 is g-normalized, yielding all the claimed results.
We start with Nin since imput neurons the first to appear in topoloical sorting. In this casc, the only path in p is = 2, for which holds II(0, p. q) = Pypol = |no = by Definition C.I. Moreover, also have Φ (0)(() equality for input neurons even 0 is not normalized.
1 (Definition A.3). This proves Equation (14) and the case of
Now, consider & Nin and assume Equation (14), and the case of equality for g-normalized parameters, to be true for every antecedent of v. In this case, we have (0) (0> (0)=(())>>") (ueat(t))))))) ) by
so it holds
| (0)1 = 16,19
Σ (Cant(v)
1 (0)1000" & 1619 + 110
max aEant(n)
| (0)1
Using the induction hypothesis on every u E anl()) yields:
| (0)1 < 16,1% 9 + 10001 max max (I.(,,),)))*
wEant(e) PEP-
Consider E ant(v) and p E p and denote by 5 p e the path p concatenated with the edge u + v. By Definition C.I, we have (highlighting orange the important changes)
1 + 110 p. q))²
length(p)
longth(p)
b
+1 "
hipe
|
k=8+1
=bro usince & Nin
length(#)-1
length((i)
9 + 110 Pmm
h
II
0 0
(I(0,,))))
k=(+1
We deduce that
I (0)
<
max max (II(O,p + u. u. max (II(O. 9))" PEP
wEant(o) PEP
This proves Equation (14) for v. To conclude the induction, remains to treat the equality case for assuming that 0 is n-normalized. Since & Nin. ant(v) * 0. and since each neuron (v) cannot be an output neuron, the fact that 0 is q-normalized implies by Definition B.1 that (0)ll, E {0, 1}, with 0 as (1
0. This implies
| (0)
1
10-
As result
(0) 0u
1u- 1011 110
[0)+()))
(Eaat((1)
(w)
w
By the induction hypothesis, we also have
max wEant(e)
|1+~>((0) (0)11
max max (TT(O.p.g))
uEant(v) PEP-1
Putting everything together yields
+ (0)1 = |b,1% +
Σ
(0) + 11000/1
(Eant(e)
=b,,1" + | 110++
max max (LI(O, (((0,p.))) 9)) (Eant( P-
max II 9.
PEP
This shows the case of equality and concludes the induction.
22

---

Published as a conference paper at ICLR 2024
D RELEVANT (AND APPARENTLY NEW) CONTRACTION LEMMAS
The main result Lemma D.1.
Lemma D.1. Consider finite sets W. and for each Z. consider a set T denote t. = (ti)eer E T with ta (ti,w) E RWW Consider functions fú,2 T - R and a finite family & = (Ej)zeJ of independent identically distributed Rademacher variables, with the index set J that will be clear from the context. Finally, consider convex and non-decreasing function R + R. Assume that at least one of the following setting holds.
(RWW) We
Setting 1: scalar input case. [W] and for every E and Z. Jū,z is 1-Lipschitz with ft.z (0)
Setting 2: t-max-pooling case. For every i 1 and Z, there is ki, Ny0 such that for every t e T (t) (kr,,) is the ki, -th largest coordinate of
Then have:
E max sup 9 zE2 1ET
Σ Eensltrahh) VEI
< E max sup g zE2 1ET
Σ SEL
Ei,w,ali,
(15)
The scalar input case simple application Theorem 4.12 Ledoux & Talagrand (1991). Indeed, for Z and / E T define s(z, !) IR/x2 to be the matrix with coordinates (i, v) E x Z given by (s(2, ().. = 14 if 2, otherwise. Define also fr,0 = ft. Since ((, 0, it holds:
(tt.)
Σ VEI
E..rf..((s(2,t)))..))
ET
S {s(2,t,, Z,t T and J== x Z then the result claimed in the scalar case reads
Esup g #
Σe1(((s)) jeJ
Esup g BES
Σgys} E3S
jEJ
The latter is true by Theorem 4.12 of Ledoux & Talagrand (1991). However, we present an addi- tional proof below, which employ establish the new scenario involving *-max-pooling. This alternative proof closely follows the structure of the proof outlined in Theorem 4.12 of Ledoux & Talagrand (1991): the beginning of the proof the same for the scalar case and the +-max-poliing case, and then the arguments become specific to each case.
Note that Theorem 4.12 of Ledoux & Talagrand (1991) does apply for the *-max-pooling case because the t, 's are now vectors. The most related result we could find is vector-valuee contraction inequality (Maurer, 2016) that is known in the specific case where [Z| 1, g the identity, and for arbitrary 1-L-iscchizz functions fi,- such that (0) O (with a different proof, and with factor /2 the right-hand side). Here, the vector-valued and g = exp, which is covered by Lemma D. We could not find it stated elsewhere.
interested in is fi, -ool
In the proof of Lemma D.I, reduce the simpler case where |Z| 1 and = that cor- responds to the next lemma. Again, the scalar imput case given by Ledoux & Talagrand (1991, Equation (4.20)) while the x-max-pooling case is apparently new.
Lemma D.2. Consider finite set W, a set T of elements t = (t1, (1,,t) E RW, x IR and a function and family of iid
f R.W + Consider also a convex non non-decreasing function Rademacher variables (Ej)jeJ where J will be clear from the context. Assume that we are in one of the two following situations.
Scalar input case. f is 1-Lipschitz, satisfies f(0) = 0 and has scalar input ([W
--max-pooling case. There l E Nyo such that f computes the k-th largest coordinate of its imput.
Denoting t = wf., it holds:
Esup F (EI +22 < Esup F teT
tET
23

---

Published as a conference paper at ICLR 2024
The proof of Lemma D.2 is postponed. We now prove Lemma D.1.
Proof of Lemma D.I. First, because of the Lipschitz assumptions on the fi's and the convexity of g, everything is measurable and the expectations well defined.
We prove the result by reducing to the simpler case of Lemma D.2. This is inspired by the reduction done in the proof of Ledoux Talagrand (1991, Theorem 4.12) in the special case of scalar t, (W) = 1).
Reduce to the case |Z| by conditioning and iteration. For E Z, define
A sup 9 tET
Σ Canahrllh)
B2 = sup g tET
Eipm,alig
EELwEE
Lemma D.3 applies since these random variables are independent. Thus, it is enough to prove that for every c E [-o0,
E maxx(A,,c) & E max(B2,, c).
Define F(z) = max(g(z), c). This can be rewritten as (inverting the supremum and the maximum)
E sup F 1ET=
Etneeiia(ti)) RE!
<
E sup F IET=
Σ WEL.
,i,,,
(16)
We just reduced to the case where there is single to consider, up the price of replacing by F. Since and æ + max(æ, c) are non-decreasing and convex, so is F by composition. Alternatively, note that we could also have reduced to the case |z| = by defining S : (s(2, (), E Z, E T* just as it is done right after the statement of Lemma D.1. In order to apply Lemma D.2, it remains to reduce to the case [ =
Reduce to the case [Z] prove Equation (16), is enough to prove that for every I and every subset R C RRW x R, denoting r2) E RWW R, it holds
by conditioning and iteration. Lemma D.4 shows that in order to
Esup F (1. +12) & Esup F reR
Σ ei, +r2) WEW
rER
We just reduced the case || 1 since inequality is now a direct consequence of Lemma D.2. This proves the result.
consider the indices one by one. The latter
L
Lemma D.3. Consider a finite set and independent families of independent real random vari- ables (Az)zz and (Bz)aEZ. If for every Z and every constant 00),, it holds max (Ag, c) < <Emax(B, c), then
E max Ag < E max Bg. ZEZ
zEZ
Proof of Lemma D.3. The proof is by conditioning and iteration. To prove the result, it is enough to prove that if
max A < E max 2
max Ag, max B3
=E
zE22
for some partition Z1, Zo of Z, with Ze possibly empty for the initialization of the induction, then for every 20 Zı:
E max A, & E max 2EZ
max Az, max B =EZi\<=>>
with the convention that the maximum over an empty set is 0o. Indeed, the claim would then come directly by induction the size of Zzz
24

---

Published as a conference paper at ICLR 2024
Now, consider arbitrary partition Z1, Z2 of Z, with Zz possibly empty, and consider &u Z1. It then enough to prove that
max
max #EZ1
Az, max B3
< E max
max Az, ==01)(20)
max Bz =EZ2U(20)
(17)
2E
Define the random variable C max (max;eZ, Mza), A,, max B₂) which may be equal to -oo when the maximum is over empty sets, and which is independent of Ag, and Bzg. It holds:
max Ag, max B3) BE21 xE22
max (Azo: C)
and
max
max #E (=a)
Azs max
Bz max (Bzo: C).
2e 2E72U(za)
Equation (17) is then equivalent
E max A 0) E Emma C)
with C independent of Az, and Bz For constant [-00, denote A(c) max((A20 c)
and (cc) E max Bz., c). We have:
E max( Azo, C) E (E (max (Asg (A))))
law of total expectation independence of C and Azo
(EA(C)
and similarly E max sn C) EB(C). It is then enough prove that A(C) B(C) almost surely. Since C' E [- oo), this is true by assumption. This proves the claims.
Lemma D.4. Consider finite sets I, W and independent families of independent real random vari- ables (e:)ser and (ei,w)ieI,,ell Consider functions fi TRW + and F R + R that are continuous. Assume that for every E I and every subset R C RCW R, denoting r = (21,22) E R with r1 (Fi,w) E RW and r2 R the components of r, it holds
Sup F(e:f((r)) +22 Esu F Σ rER
1i, r2).
ren
Consider an arbitrary T c yz and for = (4i)ier T, denote lip the with coordinate of I E RRW. It holds:
Esup F
Σ ((f((())) & Esup F(
Σ
sE
Nel
1ET iEL.wEW
Proof of Lemma D.4. The continuity assumption on F and the ft's is only used make all the considered suprema measurable. The proof goes by conditioning and iteration. For any J C I, denote e, the family that contains both (Ey)ges and (ee.wwe. Define
ht(t,e)) = EESA(())
jEJ
H,(t,e)) =
Σ
Ej
JEJ.EEW
with the convention that an empty sum zero. To make notations lighter, if = {i} then we may write hy and H, instead of h and H,,. We also omit write the dependence eu as possible. What we want to prove thus equivalent to
Esup ((hr(()) Essu ((Hr(())
tET
is enough to prove that for every partition I, Iz of I, with ln possibly empty,
E Euu F(hr(t)) & Esup F(1,, (t) + (t), rET
1ET
25

---

Published as a conference paper at ICLR 2024
then for every j I1,
Suu (()) & sup F(h))))()) + H ()) tET
LET
Indeed, the result would then come by induction the size of Iz. Fix an arbitrary partition J, 72 of with 22 possibly empty, and j E [1- then enough to prove that
Supp (h1, (t) H1, (t)) LET
Ssu F(hr)o)(()) (ru00) (ruu)))))) LET
(18)
Denote E-j == En(() and
= hn + 11, = (t,(t,) =(t,,=_))
+ HI, (t, EL,)). holds:
and, writing E = (Ej
hn) +
+(t,e)))
Consider the measurable functions
sup e(bytt,e,) e(t,e-))) 1ET
and
E(E), = sup ('I (t,,, ((t,e_))).
LET
Denote A the ambiant space of E-j and consider constant 8 A. Define ğ(6) Eg(e,, 6) and (()) (E, 8). It holds
Esup F(hn, (1) + (1) Eg(e,)e-s) 1ET
by definition of g
R =B(B(g(e,,E)))l Eg(E-j)
law of total expectation independence of ej and E-j
and similarly Esupper ((h + Hiuus) = E&(())) Thus, Equation (18) is equivalent to (E(s=,) & BG((=,). For every d E A, we can define R(O)) ((t,, gw XR, T} and it holds
g(6) Esup F( F(E;(s(ri) + r2)
and
( = Esup F
Σ
L r2).
rell WE
Thus, ((8) & (()) for every d E A by assumption. This shows the claim.
Proof of Lemma D.2. Recall that we want to prove
Sup F (())(()) + (2) < tET
Esup F EE
Σ
El,utt 1,w + 12
(19)
WEW
i.e. the inputs & are scalar and the result is well-known, see Ledoux & Talagrand (1991, Equation (4.20)).
Scalar input case. In this case, |W|
k-max-pooling case. In this case, f computes the k-th largest coordinate of its input. Comput- ing explicitly the expectation where the only random thing is e E {-1, the left-hand side of Equation (19) is equal to
sup F (f((i) + +12 + F (-f(8)) + 82).
2 RET
2 2
Consider s, E Recall that $1, s R Denote $1,()) the k-th largest component of vector $1- The set (w W 81, & 81,0)) has at least [ k + elements, and (w E W (1,(0) & h,,)
26

---

Published as a conference paper at ICLR 2024
has at least l elements, their intersection is not empty. Consider any w(s, t) in this intersection. We are now going to use that both ft1) = f1,(k) & (1,.(..)) and -f(s1) = -1,,() & - -1,,(().)) Even if we are not going use it, note that this implies f(t) - f(s) & (1,w(a.)) ((,,()))) we are
exactly using an argument that establishes that is 1-Lipschitz. Since f(t1) t1,(0) (1,0((,))) and F is non non-decreasing, it holds:
F (f(tt) +t2) & (f1,))().)) + t2)
F
(1,0(s.))) +E
E1wtt1 +t2
< EF
(1, +
Σ
1 +
Jensen
Moreover, (((cover,-f(s1)) =81,(k) -1,,w() so that in similar way:
F (--((s)) + 82) $F (1,w(,,1) + 82)
<F
(1,((s,)) +E
Σ
81,
82
<EF
-81,w((,1)
81, + 82
At the end, get
F (f(tt) + + F-(f((1))) 82)
1 EF
(1w((,11) Σ
El,w01 + l2
2
neston(s,t)
+ EF
-1,,0(s,1) +
Σ
11, 52
Esup F 2 rET
(1,u(s,0) +
Σ
11,101 +
+ E sup F 2 rET
-T1,((sd)) +
Σ
f1, + 12
(
Sup F rET
1,,(,))) +
Σ
11,w0 + 12
E +
Sup F rET
The latter is independent of s, t. Taking the supremum over all s, E T yields Equation (19) and thus the claim.
E PEELING ARGUMENT
First, state simple lemma that will be used several times.
'The choice of specific w has importance, unlike when defining the activations of k-max-pooling
27

---

Published as a conference paper at ICLR 2024
Lemma E.1. Consider vector R with iid Rademacher coordinates, meaning that PP(e; 1) P(E, = -1) = 1/2. Consider a function g R + -R3- Consider a set C. RR. It holds:
n Eepti
g sup 9 =EX
Σ
< 2Eg sup g Te
Proof of Lemma E.I. Since ! O, it holds g((xl) g(x)) (-(-)) Thus
Eg sup #EX
Σ e
Ee sup #EX
Σ
E
+ Ee sup xEX
Σ
(-Ex))
Since is symmetric, that is has the same distribution e, deduce that the latter is just 21E supzex 9 (E E,T;). This proves the claim.
Notations We now fix for all the next results of this section vectors .1,..., E Red for some din E Nyo. We denote Ti,u the coordinate u of Ti-
For any neural network architecture, recall that v(0,z) ) is the output of neuron v for parameters and input x, and (r) is the set neurons for which there exists a path from u to v of distance d. For a set of neurons V, denote (v x) ())0.))).EV.
Introduction to peeling This section shows that some expected sum over output neurons v can be reduced to expected maximum over ant(v), and iteratively over an expected maximum over (n) for increasing d's. Eventually, the maximum is only over input neurons enough. We start with the next lemma which is the initialization of the induction over d: peels off the output neurons v to reduce their antecedents ant(v).
d is large
Lemma E.2. Consider a neural network architecture as in Definition 2.2 with Nin n Nout 0. Consider an associated set of parameters such that 1 + [bel & Consider
family of independent Rademacher variables (æz)jEJ with J that will be clear from the context.
Consider non-decreasing function 9 R - Rzo Consider new neuron Ubias and set by convention Vveias = 1 for every input x. It holds
Egg
sup 0-
Σ
(0,000,,000
NEN
Eeg
max eE
Eippiii
WE(ant(v)nNN (
Eeg
sup
Σ E E1 20,
VE Naw uEant(e) NN. 0
where in the last term if on) Nn = 0. by convention max = -0, and g( g(-oc) = O.
Proof of Lemma E.2. Recall that for a set of neurons V, we denote Ry (0, x)) = (v(0,x))ve Recall that by Definition 2.2, output neurons have P. id for every N θ and every input x:
v0,z)) = by ) Rant(w) (0, ))
(0-
28

---

Published as a conference paper at ICLR 2024
Denote by Ubias neuron that computes the constant function equal to (0. 1), we get:
B
sup
Σ
(0,
im
VENNa
O++
Rant(o) (0, x4)
Eeg
sup
by
Σ i=1
Ei.
n Σ
<
Beg
sup
Σ
10000
+1bal
max DENi
Ei
max (Eant(v)
Σ
Ei E
Holder
Not
Er by assumpptio
< Eeg
sup A
Σ E, 00,;;
Everything is non-negative so the maximum over u E ant(v) U {Uptaa is smaller than the sum of the maxima over u (ant(v) n Nm) (Vbras) and u E ant(r) \ Nin- Note that when u is an input neuron, it simply holds u( (0, x:4) Vi,u- This proves the result.
We now show how peel neurons to reduce the maximum over (n) to ant (v). Later, will repeat that until the maximum is only on input neurons, Compared to the previous lemma, note the presence of an index (when the maximum over u has been reduced to u ant),v)), we will have M = Kdd where K the kernel size. Indeed, the number of copies indexed by m gets multiplied by K after each peeling step.
.....; M in the maxima. This is because after d steps of peeling
Lemma E.3. Consider a neural network architecture with an associated set of parameters such that every neuron & Now U Ni satisfies ||0~01|| + |b.l 1. Assume that b, for every v E Ne.poo1-- Consider a family of independent Rademacher variables (Ej)jeJ with that will be clear from the context. Consider arbitrary M, d E N and a convex non-decreasing function - R20. Take symbol Uoias which does not correspond to a neuron (Ubtas & N) and set by convention Ivoux 1 for every input x. Define P (k N>o. Eu NNkpool) } as the number of different types of x-max- mooxing neurons in G, and K = maX N. geat size of the network (K = i = 0). It holds:
aan((u) ] the maximal kernel
Egg
max wEant (Ej]t m=1......
sup
Ei ua (0,z;) (0)
BENee
1=1
< (3 (3+2P)
max NEN m= mm=I.....AA. RM
Es mu
ME(ant"+1 (N N.. Massr
+ (3 +3+22 2P)
max BE m= I.......MM
max #Eant (m)) NN,
supp
f u u (0,2z)
i=1
with similar convention as in Lemma E.2 for emply maxima.
Proof. Step 1: split the neurons depending on their activation function. In the term that we want to bound from above, the neurons E an) \ Nin are not input neurons they compute something of the form (...)) where Pa is the activation associated with u, 1-Lipschitz, and satisfies (0) = 0. The first step of the proof is to get rid of Pu. using contraction lemma similar to Theorem 4.12 in Ledoux & Talagrand (1991). However, here, the function Pa. depends on the neuron u, what taking maximum over so that classical contraction lemmas do not apply directly. To resolve
29

---

Published as a conference paper at ICLR 2024
this first obstacle, split the neurons according their activation function. Below, we highlight in orange what is important and/or the changes from one line to another. Denote N₂ the neurons that have p their associated activation function, and the term with maximum over all N, is denoted:
c(p) = Egg
max vENon,
max (e)t M
sup
E Ei u u(0
with the convention e(p) Of N₂ is empty. This yields a first bound
Eeg
max
max uEant NN)
sup
Ei ui,, xi)) < <(RRLUU)+ + e(id) + Σ ekkpppol)
VE mm= 1
where the sum of the right-hand side is on all the & E N such that there at least one neuron in Nk-pool- Define E(p) to be the same thing as e(p) but without the absolute values:
E(p)= Egg
max
max uE(ant ( 0
sup
m.m.m (00,zz))
DE Neut m=I....M.
Lemma E.1 gets rid of the absolute values by paying factor 2:
e(p) & 2F(p).
We now want to bound each E(p).
Step 2: get rid of the =-max-pooling and ReLU activation functions. Since the maximal kernel size K, any *-max -polling neuron u must have at most antecedents. When a N. N. has less than K antecedents, we artificially add neurons w to ant(u) to make it of cardinal K, and we set by convention 0=-+ O. We also fix an arbitrary order on the antecedents of u and write ant (u)) for the antecedent number w, with Ra the function associated with this neuron. For ReLU or =-max-poue mnox--ooling neuron u, define the pre-activation of to be
pre, , (0,x) = {{ ((00) by (bn Jant(w)u RRat(u)) (0, x)) w- otherwise when MM.pool
θ *x (OO)).
( Rant(u) (
if E NReLUS
where we recall that bu = 0 for u E Noppoo by assumption. We nevertheless keep by in the computation until the point where this assumption is apparently actually needed continue. Note that the pre-activation has been defined to satisfy u(0, z)) Pu (pre,, (0,x)). When p is the ReLU or k-pool, we can thus rewrite E(p) in terms of the arevvatiittions:
E(p) Eeg
max vENar: uE(ant" N,), mm=1...,,M
max
sup
en (pre, (0,
xx:))
Consider the finite set Z {(V, m)) E Now, m I.....M M] and for every 2 (v, m) Z, define T (0,,r,,0,, (i,
(v) N₂) Ni,, 0 E θ). An element of T will be denoted (4,) T IR" if p ReLU, and t (t) T (R&y" with (b E R if u E Napool. We can again rewrite E(p) as
F((p) Egg
max sup SEZ LET
We now want to get rid of the activation function with a contraction lemma. There is second difficulty that prevents us from directly applying classical contraction lemmas such as Theorem 4. 12 of Ledoux & Talagrand (1991). It is the presence of maximum over multiple copies indexed by 2 E Z of a supremum that depends on iid families (E,,s)i=1..n- Indeed, Theorem 4.12 of Ledoux & Talagrand (1991) only deals with single copy (|Z) = 1). This motivates the contraction lemma established for the occasion in Lemma D.I. Once the activation functions removed, we can conclude separately for p ReLU, id and p k-pool.
30

---

Published as a conference paper at ICLR 2024
Step 3a: deal with p k-pool via rescaling. In the case p k-pool, Lemma D.1 shows that
Eeg
max sup 2EZ tET
E (-oo--poo(tt)
==1
&
Egg
max sup SE4
Σ
Es
w=I....K
The right-hand side is equal to
E.g
max V.EN
sup NN. i=
Σ
E, (b, + ganc(u)) (anni(a) Rant(u) (0, 2;))
m= M oE (aut" (a (e) peat)
0
(20)
We now deal with this using the assumption the norm of incoming weights. Recalling that b. for every u E poo1:
Ei by
gaant(u) +u Rant(u) (0, xi))
gant(u) -a
Σ
Eiuum, (w (0,
0
max w=I....KK
Σ
Es Rantm 00,x,)
Hilder
i1....
<1 by assumption
max
Ein.m w (0,
decoupling to and an) wrEant(w)
Note for the curious reader that this inequality is the current obstacle when the biases are nonzero since we would end up with K|bbll + | and we could not anymore use that this is & 1. We deduce that Equation (20) bounded from above by
E.g
max NENon mi= M
max ue (c)) Na wEant(a) wo wI.......
max
m.m.m.. w xi)
Instead of having E, with m I, and w/ 1...., K, we re-index it as Es,om with m I,..., K.M. Note also that u E (ant"(v) n N.-poo2) \ Ni and w ant(u) im- plies w E ant so considering a maximum over w E ant (v) can only yield something larger. Moreover, one (Ubta = 1) and add tbias to the maximum over w. Implementing all these changes, Equation (20) is bounded by
add new neuron Vaias that computes the constant function equal to
mm w(O xi:) )
H = Eeg
max VE
sup weantd++ (n) (tatae)
sup O0G
Σ
We now derive similar inequalities when p id and p ReLU.
31

---

Published as a conference paper at ICLR 2024
Step 3b: deal with p id, ReLU via rescaling. In the case p ReLU, Lemma D.I shows that
Eg max sup #EZ 1ET
Ei Re.UR()
max sup Eg
Σ ei i=
sEZ 1ET
The difference with the *-max-poot --max-pooling case is that each t scalar so this does not introduce an additional index w to the Rademacher variables. The right-hand side can be rewritten as
Ei,,, ((O)) bu )
(0TT
Rant(() (0, xz))
Egg
max N.N m=
sup N. i= im
Σ
We can only increase the latter by considering a maximum over all u E (v), not only the ones in NUaLU- We also add absolutes values. This is then bounded by
((
)
Rant( (0, x:))
(O
F = Egg
sup (m= I MEant Nv.
max DENNa
Σ
Eipom
bu
i=
(21)
This means that E(ReLU) & F. Let us also observe that e(id) < F. Indeed, recall that by definition
e(id) = Eeg
max
max VE(ant" (M) 0
sup
Σ 1=1
Etu u( Et..mu(0, xx))
DE m=I...MMM
We can only increase the latter by considering a maximum over all u E an) Moreover, for an g Rant(w)(O (0, (
identity neuron u, holds u(0, x)
This shows that e(id) < F. It remains to bound F using that the assumption on the norm of the parameters. Introduce new neuron Upias that computes the constant function equal to one: Upiae (0, x) Note that
bw
Σ Eiu,m
i 0-1 ) (
Rant(u) (0,
bu
k= 1=.....
Rant(wy (0, x;)
by
ui
i= I....!
(1 1 1 + (bul)
max (Vsaee)
Σ mmu wl x;))
1 by ussumption
This shows that
F F&E
sup I.Il....MM M wEant (w) e (
max VEN
max
E. w (0, xx.)
Obviously, introducing additional copies of e to make the third index going from m to K KM only make it larger. Moreover, ant Nm and w ant(u) implies E ant (u)) so we can instead consider maximum over E an (v). This gives the upper-bound
F Egg
sup Σ BEO
fin.m (0,z;)
BEN mm=l..KKM
H.
32

---

Published as a conference paper at ICLR 2024
Step 4: putting everything together. At the end, recalling that there most P different k No associated with an existing m-max-polling neuron, we get the final bound
Exg
max vE,Nout, m= M
max "Cant-(a)) No
sup
Σ E fi u(O, xi)
< <e(id) + <(ReLU) + Σ e ekk-pool)
<<(id) + 2E(ReLU) + Σ E(k-pool)
F +2 Σ E(k-pool)
< 2H +2 Σ H
H + 2H + 2PH = (3 + 2P)H.
The term (3+2P) H can again be bounded by splitting the maximum over w E ant d+1 (v)U(rssas between the w's 's that are input neurons, and those that not, since everything is non-negative. This yields the claim.
Remark E.1 (Improved dependencies the kemne size). Note that in the proof of Lemma E.3, the multiplication of M by K can be avoided if there are no t-max-pooling neurons in ant Because skip connections, even if there single t-max-pooling neuron in the architecture, can be in ant (v) for many d's. A more advanced version of the argument is to peel only the ReLU and identity neurons, by leaving the +-max-pooke maxx-pooling neurons as they are, until we reach a set of x- max-pooling neurons large enough that we decide to peel simultaneously. This would prevent the multiplication by K every time d increased.
We can now state the main peeling theorem, which directly result from Lemma E.2 and Lemma E.3 by induction on d. Note that these lemmas contain assumptions on the size of the incoming weights of the different neurons. These assumptions are met using Algorithm which rescales the parame- ters without changing the associated function nor the path-
Theorem E.1. Consider neural network architecture as in Definition 2.2 with Now O N v. Assume that by 0 for every U E Nx-pool- Define P == [[ E N>u, Bu E Nk-pool H the number of different types of t-mux-pooling neurons in G, and K == maxueN- the maximum kernel size (K := 1 by convention P 0). Denote by Gasas a new impul neuron and define Eeyiig for any input For any set of parameters θ associated with the network, such that || [0)(f)] & r for every 0 E θ holds for every convex non- non-ddcreasing function R + Rz0
Eeg
sup 00
Σ
(0,
i=l..... # New
(3 2P)
Eeg
r
max DE Nav.
max (
Es Ei
2 + 2P
m= I.......K
Proof of Theorem E.1. Without loss of generality, we can replace O by its image under Algorithm with q = 1, as Algorithm does not change the associated function Ro nor the path-norm [[)()) | (Lemma B) so that we still have [1)(0) & and the supremum over E e on the left- hand side can be taken over rescaled parameters. By Lemma B.I, the parameters are 1 1-normalized (Definition B. so we will be able to use Lemma E.2 and Lemma E.3. Indeed, 1-normalized parameters satisfy EVEN... ||0 [1l="l|a + [bal = ( | & r so Lemma E.2 applies. We also have ||e (00> ||| + |b,l & 1 for every u & Nm, Now. by definition of 1-normalization, so Lemma E.3 also applies.
33

---

Published as a conference paper at ICLR 2024
By induction d > 1, we prove that (highlighting in orange what is important)
Egg
sup AE
Σ
(1,0((0,zz) 23))
V
(3 + (2 REg
mi aa
vE
WE(ant Ju PaLLo
t=1
m=1.....f K'
i=1
+ (3+ + (1)+
mnax VENNoa
max (e) Ni. AE
sup
Eiu U (0, (i)
m=
with the same convention in Lemma E.2 for maxima over empty sets. This is true for d = 1 by Lemma E.2. The induction step is verified using Lemma E.3. This concludes the induction. Applying the result for d = D, and since ant
PutP())) (u) Ni 0, we get:
Egg
sup AE
Σ
(0,
i= I..... VeN
[3 22)
MAN vE
max (e)
We can only increase the right-hand side by considering maximum over all Nin {Ubias) and by adding independent copies indexed from m m K D-1, Moreover, (3+2))d-- ((3 2 () + 2P). This shows the final bound:
Eeg
sup O0
Σ
((,
i= I=,..... N
(3 D
Eeg
r
max DE Non
max WE N. (Maiaas)
Li
2 + 2P
m= D-1
F DETAILS TO DERIVE THE GENERALIZATION BOUND (THEOREM 3.1)
Proof of Theorem 3.1. The proof is given directly in the general case with nonzero biases ev- ery & Noop and uses an additional input neuron Usias. We highlight along the proof where improved results can be obtained assuming zero biases, yielding Theorem 3.1 as consequence. Define the random matrices E (E,,)),r E Baxda and R(0, X) (v(O, X,)),, Ruxda so that (E, R X)) = Ei Ei (Ro(R))) holds:
n e, (X,, Y.)
Ez f-generalization error of (Z)
<
Ez,
sup
n
i=1
2/2L Ez,s
sup (E, R(O ((00))))
The first inequality is the symmetrization property given by Shalev-Shwarde & Ben-Davic (2014, Theorem 26.3), and the second inequality is the vector-valued contraction property given by Mau- (2016). These are the relevant versions of very classical arguments that widely used to
34

---

Published as a conference paper at ICLR 2024
reduce the problem the Rademacher complexity of the model (Bach, 2024, Propositions 4.2 and Waanwwhnrr,, 2019, Equations (4.17) and (Barlett & Mendelson, 2002, Proof of Theo- rem 8/Shaale-Shwartz & Ben-David 2014, Theorem 26.3)Ledoux & Talagrand, 1991, Equation (4.20)). In particular, this step has nothing specifie with neural networks. Note that the assumption on the loss is used for the second inequality.
We now condition on Z = (X, Y) and denote Eg the conditional expectation. For any random variable A(Z) O measurable in Z, holds
Eg sup (E, R, x))
log exp
A(Z)EE sup (E, ((O,
X
log exp
Eg A(ZZ) sup (E, R X))
A mensurable in z ZAZZ)
log Eg exp
A(Z) sup (,, R(O,
A(Z)
For ((24, 9:)), E (R Rdu )mh denote
E(2) = Ee exp (E,
Since independent of e, holds
Eg exp ((Z) sup (E, RiO, x))) = =
Denote s (0) For above, simply denote À == A(z). Since Nm n Nowt and the biases of --mx--poling neurons are null, the peeling argument given by Theorem E. for g:te E R + exp(Xt) guarantees:
(P+
<(2) <
Eg exp
Ar
max #EN m=1.....K KD D-
max uENN,U(
Σ Eioum
2+ 2P
where Ti,a is coordinate u of vector E Rdu, and where Vatas is an added neuron for which we set by convention Prii for any input æ. It is easy check that the same bound holds true with a maximum only over E N (not considering Ubias in the maximum) when all biases are constrained to be null. such a setting, all the maxpEN, below can replaced by maX.eN,. Denote
1/2
Σ 2t
(x)
Vn.
ae Ne fusiaa) Dasas)
Using Lemma F.1, it holds
m Σ
(r)(2)
Eg exp
Ar
max VE VE U, 1==.....K""" KDD1
Ei (X;)
< 2KK- + 1)dout exp
2
When biases are constrained to be null, din + 1 is replaced by din Putting everything together, we get:
F sup (F, R(0, x)x =((2) =
( (
with
2PDD
3+
G 22 2-D-1 1)d
1+ ((3 (3+2P)K)D-1(4) + 1)dcut
2+2P
35

---

Published as a conference paper at ICLR 2024
(again with du + 1 replaced by dn when all biases null) and
C2(X) = (ro(X))²
1
Choosing A(Z)
V
[r] C2(X]
yields:
Eg sup (E, RRO, x))
< 22Vlog( (o)(CC))(C2
2P
1/2
(X)r
log
1+ (dm + 1)daa Dlog (3+2P))
C2(X)
log(Ch)
with di, + replaced by di when all biases null. Taking the expectation both sides over Z, and multiplying this by 2v21. yields Theorem 3.1.
The next lemma is classical (Golowich al., 2018, Section 7.1) and is here only for completeness. Lemma F.1. For any d, k E Nyo and X >> 0, it holds
X2 n
E exp
max m= l.ink
Σ Ein (Xi)a)
<
2kd max exp w=l....d
-0xx (x))
Proof. It holds
n
m
Eimm (Xi)a )
Egg exp
A max m=.....kk I.......
Σ 1=1
Eim (Xi)a
Σ
Ee exp
Σ 1=1
m=1...
u=1. I=
For given u and m
Eg exp
Σ
eim (eeim(X))) (Xi)a)
2E exp A Σ Eim (Xi)u
Lomma
1=1
i=1
2
exp (.) + exp (xxp(->(XX (-X(Xx)a) < 2exp
2 (x))
X²
Σ())
2
2 1=1
1=1
using exp(x) exp(-2) & 2 exp(2>² 2 /2) the last inequality.
G THE CROSS-ENTRONE LOSS IS LIPSCHITZ
Theorem 3.1 applies to the cross-entropy loss with I = 2. To see this, first recall that with C classes, the cross-entropy loss is defined as
exp(xe) exp((ra)
e: (I,3)) x 10
Me log
Consider E {0, 1] with exactly one nonzero coordinate and an exponent p E [1, oo] with conju- gate exponent p' (1/p 1/p' 1). For every x, x' E R.:
((x.v) v) (x'.v) < 2//2 || - ='1l.-
Consider a class e E (1...., C} and take E {0, 1 to be a one-hot encoding of (meaning
that Ye =)) Consider exponent p E [1, oa] with conjugate exponent p' (1/p 1/p'
36

---

Published as a conference paper at ICLR 2024
1). The function f + ((x,)) = = ye log
20 explar)) - -log
exp(ze)
exp(xe)
is
-eع exp(e
continuously differentiable so that for every 2, x' E :
f(=) L.' (V + (1- x²) dt & sup
Vf(tt (1 "bp')lp x 2'1lp'-
ref0.1]
In order to differentiate f. let's start to differentiate g(x) = Σ exp(x.)) derivative with respect to coordinate i. For +
exp(ze)
Denote ò the partial
Org(a)= exp(xc) CE exp(xe:)) exp(x.) (exp(xe))
(Eor exp(xx)))
Exteexp(xx)) exp(xcr
=((x) Ee exp(xae)
0g(a)) (E exp(xx)) exp(x.) (exp(zi))
Ew exp(xx)))
exp(x;;)
= ((x)
Ee exp(ste)
Since f(x) (- log (z)(
0.f(x) 0,g(z)
g(x)
-Engee e
i otherwise.
Ed=1expla exp(xx)
Thus
|V[+)} Σ (x)(
(Eordo exp(xe)) ) Eoseo exp(xe)
Ec exp(xx))
Eeto exp(xxe)
2
Ee=1 exp(ste))
Eeto exp(sec) F Ee'te exp(xx))
2
= 2.
where we used in the first inequality that Illll < ||ll for any vector v. This shows that for every I, RCC
(x. l(x, .)) & / ll
H THE TOP-1 ACCURACY LOSS IS NOT LIPSCHITZ
Theorem 3.1 does not apply to the top-1 accuracy loss É(g. y) = 1 arr as Equation (3)
cannot be satisfied by É. Indeed, it is easy to construct situations where タ1 (o(x)) is arbitrarily close to 82 = Re (x2) with Iz correctly classified, while 21 is not (just take 22 on the boundary decision of the network and 21 the wrong side of the boundary), equal to 1 and the right-hand side arbitrarily small. Thus, there is no finite L >> that could satisfy Equation (3).
that the left-hand side is
37

---

Published as a conference paper at ICLR 2024
1 THE MARGIN-LOSS IS LIPSCHITZ
For i E gdou and one-hot encoding y E Rd the class c of æ (meaning that ye = Lo'=o for every c)), the margin M (ū. v) is defined by
M v) = bo max (ū]er.
For > 0, recall that the m-margin-loss is defined by
{
if y ((.
E(
1 M(G.2)
if & M y) & 7,7
(22)
if M y) < 0.
For any class and one-hot encoding y of it known that 9 E Rdd + M y) is 2-Lipschitz with respect to the norm on ý (Bartlett et al., 2017, Lemma A.3). Moreover, the function
{
0
ifr < -?, if - E 2r60
E R -
1+
ifr > O.
-Liisschitz By composition, this shows that R Lg v) is 2 -Lpischhtzz with respect to the Ln-mm
Proof of Theorem 3.2. Since the labels Y one-hot encodings, equivalently consider Y either in Rd or in (1...., dout)- It holds (Bartlett et al., 2017, Lemma A.4)
IP arg max Ro (X)] Y
< (C, Y))
for any > 0 and associated 7-margin-loss by Thus, considering the generalization error for ly:
PP arg max Ra + Y
by (Roiz) (Xi), Y.) +Bz E, gegeraaalizatonn error of (Z).
training 6(2)
By definition of byp the training error
((Z) is at most
D [R (Xily, +n+max Razz (X,))e- Moreover, Theorem 3.1 can be used bound
the generalization eтror associated with E, with T, = 2/7. This proves the claim.
J DETAILS ON THE EXPERIMENTS OF SECTION 4
Details for Table 2. All the experiments are done on ImageNet-Ie Ik using 99% of the 1,281,167 images of the training set for training, the other 1% is used for validation. Thus, [0.99 x 1281 167 in our experiments, dm = 224 x 224 x = 150528, dumt = 1000. We also estimated B 2.640000149044177 by taking the maximum of the I norms of the training images normalized for inference". The PyTorch code for normalization at inference is standard:
1268355
inference_necee mow.aeeennommliitiinn = transforms Compose (
Resnsf (256),
transforms Centrrrrrreeetttrrrrrroo (224),
transforms. (),
transforms. Normal 1 ze (mean-(0 485, 0. 456, D. 0.406], std- 229,
0.224, 0. 0.2251),
1)
9The constant in Theorem 3.1 corresponds to data Z, drawn from the distribution for which we want evaluate the test error. This is then the data normalized for inference. Thus, the training loss appearing Theorem 3.1 is also evaluated on training data normalized for inference. ignore this fact and still evaluate the training loss on the data augmented for training. Moreover, note that it is not possible to recover the training images augmented for training from the images normalized for inference, because cropping is done at random for training. Thus, the real life estimator is not function of the images Z, normalized for inference, and Theorem 3.1 does apply stricto sensu. This fact ignored here.
the experiments, we
38

---

Published as a conference paper at ICLR 2024
We consider ResNets. They have single max- max-pooling layer of kernel size 3 x 3 so that K 9. The depth is D = 3+# # basic blocks x # conv per basic block, where 3 accounts for the conv1 layer, the average-pooling layer, the fe layer, and the rest accounts for all the convolutional layers in the basic blocks. Note that the average-pooling layer can be incorporated into the next fe layer as it only contains identity neurons, see the discussion after Theorem 3.1, we can actually consider D = 2+ + # basic blocks x # conv per basic block. Table 4 details the relevant values related to basic blocks.
Table 4: Number of basic blocks, of convolutional layer per basic blocks and associated D for ResNets (He et al., 2016, Table 1).
ResNet
18
34
50
101
152
basic blocks
8
16
33
50
# conv per basic block D
2
3
18
34
50
101
152
Pretrained ResNets. The PyTorch pretrained weights that have been selected are the ones with the best performance: ResNetX_liei wei.s MMAGENETI_VV vI for ResNets 18 and 34, and ResNetX__e
IMAGENETIK V2 otherwise.
Choice 7 > for Theorem 3.2. In Equation (4), note that there is a trade-off when choosing Y > 0. Indeed, the first term of the right-hand side is non-decreasing with y while the second one is non-increasing. The first term is simply the proportion of datapoints that are not correctly classified with a margin at least equal to y. Defining the margin of input i on parameters O to be Rs (X,),, arg max Rg ). this means that the first term is (approximately) equal to q if 7 = (4) is the q-quantile of the distribution of the margins over the training set.
Note that since the second term in Equation (4) is of order 1/v it would be desirable to choose the 1/ i/uantuee (up to a constant) for y. However, this is not possible in practice as soon as the training top-1 accuracy is too large compared to 1/vT (eg. on ImageNet). Indeed, if the training top-1 error is equal to E [0, 1). then at least a proportion e of the data margins should be negative 10 so that any q-quantile with q < e is negative and cannot be considered for Theorem 3.2
The distribution of the margins on the training set of ImageNet can be found in Figure 3. The maximum training margin is roughly of size 30, which is insufficient to compensate the size of the L path-norm of pretrained ResNets reported in Table 3. For 7 >> 30, the first term of the right-hand side of Theorem 3.2 is greater than one, so that the bound is not informative. This shows that there is no possible choice for 7 > 0 that makes the bound informative on these pretrained ResNets. Table 5 reports a quantile for these pretrained ResNets.
Table 5: The q-quantile (()) for q = fe+ 3. with e being the top-1 error, ImageNet, of pretrained ResNets available on Py Torch.
ResNet
18
34
50
101
152
7(g)
5.0
5.6
4.2
5.6
5.8
Details for sparse networks. ResNet18 is trained on 99% of ImageNet with single GPU using SGD for 90 epochs, learning rate 0.1, weight-decay 0.0001, batch size 1024, and a multi-step sched- uler where the learning rate is divided by 10 at epochs 30, 60 and 80. The epoch out of the 90 ones with maximum validation top-1 accuracy is considered as the final epoch. Pruning is done iteratively accordingly to Frankle al. (2021). We prune 20% of the remaining weights of each convolutional layer, and 10% of the final fully connected layer, at each pruning iteration, save the mask and rewind the weights to their values after the first 5 epochs of the dense network. and train for 85 remaining epochs, before pruning again etc. Results for a single run are shown in Figure 4.
Details for increasing the train size. Instead of training on 99% of ImageNet (n 1268355), trained a ResNet18 on n/2² samples drawn at random, for < < 5. For each given k the results
A data margin is negative if and only if it misclassified.
39

---

Published as a conference paper at ICLR 2024
resnetis, cain j.0.79
resnetis, resnet34, tnin 1=b.55 resnet5,, rain 1= monnt1l1, toa
tain 1=d
resnetto, tmin 1=d.91
1oone1111 0.
60202
60.00
40309
40009
20300
20203
-30
-20
20
Figure 3: Distribution of the margins on the training set of ImageNet, with the pretrained ResNets available on PyTorch.
averaged over seeds. The hyperparameters are the same as for sparse networks (except that do not perform any pruning here): 90 epochs etc. Results are in Figure 5,
K MAIN RELATED WORKS
Given the extent of the literature on generalization bounds, we apologize in advance for papers the reader may find missing below.
Previous definitions of the path-lifting and the path-activations In the work of Kawaguchi et al. (2017, Section 5.1) the path-lifting and the path-activations are evoked in the case of ReLU DAG with max- ppoolig neurons and no biases, but with no explicit definitions. Definition A.3 gives formal definition for these objects, and extend it to the case where there are biases, which requires extending the path-lifting to paths starting from neurons that are not input neurons. Moreover, Defi- nition A.3 extends it arbitrary k-max-pone t-max-pooling neurons (classical max-pooling neurons correspond to k = 1).
Note also that the formula Equation (5) is stated in the specific case of Kawaguchi al. (2017, Section 5.1) (as an explicit sum rather than an inner product), without proof since the objects are not explicitly defined in Kawaguchi al. (2017).
formal definition of the math-lifting is given in the specific case of layered fully- fully-connected ReLU neural networks with biases in the work of Stock Gribonval (2023, Definition 6). Moreover, is proved that Equation (5) holds in this specific case in Stock & Gribonval (2023, Corollary 3). Definition A.3 and Equation (5) generalize the latter to an arbitrary DAG with s-max-pooling or identity neurons (allowing in particular for skip connections, max-pooling and average-poolin prerage-pooling).
The rest of the works we are aware of only define and consider the norm of the path-lifting, but not the lifting itself. The most general setting being the one of Neyshabur et al. (2015) with general DAG, but without max or identity neurons, nor biases. Not defining the path-lifting and the path-activations makes notations arguably heavier since Equation (5) is then always written with an explicit sum over all paths, with explicit product of weights along each path, and so on.
Previous generalization bounds based on path-norm See Table for comparison. Appendix I. tackles some other bounds that not appear Table
Empirical evaluation of path-norm The formula given in Theorem A.1 is the first one to fully encompass modern networks with biases, weeaag/s-max-pooling and skip connections, such as ResNets. An equivalent formula is stated for layered fully-connected ReLU networks without biases (and no pooling/skip connections) in Dziugaite et al. (2020, Appendix C.6.5) and Jiang et al. (2020, Equations (43) and (44)) but without proof (and only for L L''-ptt-nomm instead of general mixed L norm. Actually, this equivalent formula turns out to be false when there are * s-max-pont maxxppoolng neurons one must replace k-max-pooling neurons with identity ones, see Theorem A. Care must.
40

---

Published as a conference paper at ICLR 2024
107
12
109
patt mmmm
10
10
10a
Epoch
10r4
-15
Epoch
Thin Pip ACCEPRC
22
19
18
20
40
20 40
60
80
19
Spach
Spach
Figure 4: L path-norm (g 1, 2, 4), test top-1 accuracy, training top-1 accuracy, and the top-1 gen- eralization error (difference between test top-1 and train top-1) during the training of a ResNetl on ImageNet. The pruning iteration indicated in legend, with 0 corresponding to the dense network. The color also indicates the degree of sparsity: from dense (black) to extremely sparse (yellow).
41

---

Published as a conference paper at ICLR 2024
1/32
1/16
10
1/8
1/4
1/2
1030
path-norm
1029
1020
1027
20
40
60
80
Epoch
30
censentteettnn the (Ow.-ATPP
23
Convesttttinn for
0.5
Epoch
Epoch
Figure 5: I,1 path-norm, and empirical generalization errors for both the top-1 accuracy and the cross-entropy during the training of ResNet18 on a subset of the training images ImageNet. The legend indicates the size of the subset considered, e.g. 1/m corresponds to 1/m of 99% of ImageNet, leaving the other 1% out for validation. The color also indicates the size of the subset: from small (black) to large (yellow).
42

---

Published as a conference paper at ICLR 2024
also be taken with average- pootling neurons that must be rescaled by considering them identity neurons.
We could not find reported numerical values of the path-norm except for toy examples (Dziugaite, 2018; Furusho, 2020; Zheng et al., 2019). Details are in Appendix L.
Appendix L also discusses 1) inherent limitations of Theorem 3.1 which common to many gen- eralization bounds, and 2) the applicability of Theorem 3.1 compared to PAC-Bayes bounds.
L MORE RELATED WORKS
More generalization bounds using path-norm In Et (2022) is established additional bound to the one appearing in Table I, for class of functions and a complexity measure that are related to the infinite-depth limits of residual networks and the path-norm. However, it is unclear how this result implies anything for actual neural networks with the actual path-norm 11,
The bound in Zheng al. (2019) only holds for layered dully-connected ReLU neural networks (no max or identity neurons) with no biases and it grows exponentially with the depth of the network. not included in Table because it requires an additional assumption: the coordinates of the path- lifting must not only be bounded from above, but also from below. The reason for this assumption not discussed in Zheng et al. (2019), and it is unclear whether this is at all desirable, since a small path-norm can only be better for generalization in light of Theorem 3.1.
Theorem 4.3 in Golowich et al. (2018) is a bound that holds for layered fully-connected ReLU neural networks with no biases (no max and no identity neurons) and it depends on the product of operator norms of the layers. has the merit of having no dependence on the size of the architecture (depth, width, number of neurons etc.). However, it requires an additional assumption: each layer must have an operator norm bounded from below, so that it only applies to a restricted set of layered fully-connected networks. Moreover, it is unclear whether such an assumption is desirable: there are networks with arbitrary small operator norms that realize the zero function, and the latter has a generalization error equal to zero.
Theorem 8 in Kawaguchi et al. (2017) gives a generalization bound for scalar-valued (dout = 1) models with an output of the form (#))), A(0', .x)²) for some specific parameters 0, 0' that have no reason to be equal. This is orthogonal to the case of neural networks where one must have 0= 0', and is therefore not included Table 1. Theorem 5 in Kawaguchi et al. (2017) can be seen as a possible first step to derive a bound based on path-norm in the specific case of the mean squared error loss. However, discussed in more details below, Theorem 5 in Kawaguchi et al. (2017) is a rewriting of the generalization eиror with several terms that are as complex to bound as the original generalization error, resulting bound being as hard as the generalization error to evaluate/estimate.
More details about Theorem Kawaguchi al. (2017) We start by re-deriving Theorem 5 in Kawaguchi et al. (2017). In the specific case of mean squared error, using that
[R( v112 ||o (2) 1lvlž 2 (Ro(
"E (2022) starts from the fact that the infinite-depth limits of residual networks can characterized with partial differential equations. Thus E et al. (2022) establishes a bound for functions characterized by similar, but different, partial differential equations, using what seems to be an analogue of path norm for these new functions. However, even if the characterizations of these functions are closed, as it is said in E et al. (2022), "it is unclear how the spaces are related".
43

---

Published as a conference paper at ICLR 2024
it is possible to rewrite the generalization error as follows:
generalization error of ((Z) =F
(1 Raiz) (X)
z
Σ
[ (X:) Y.1l2
7
= E ( R 0 (x)1
Σ
|| Raazz (x,)
+ E |
im
1 Roi2) (Xi), X.).
22 ( (Rozz) (X), Y
[z)
π
It is then possible to make the 1,2 path-norm appear. For instance, for one-dimensional output networks, it can be proven (see Lemma A. that (x) = (6 =(x, 0)) with (()) the path- lifting of parameters 0, and z that typically depends on the path-activations and the input, so that the first term above can be rewritten
((0())))
E 2 ((Z)) (())
ni Σ xX,
((((Z)).
Let us call "generalization error like quantity" any term of the form
E (Jorz) (Z))z) - Σ Sóiz) (Z:),
that is, any term that can be represented as a difference between the estimator learned from training data Z evaluated on test data Z, and the evaluation on the training data. We see that the derivation above replaces the classical generalization error with two others quantities similar in definition to the generalization error. This derivation, which is specific to mean squared error, leads to Theorem 5 in Kawaguchi et al. (2017). Very importantly, note that this derivation trades single quantity similar to generalization error for two new such quantities. There is no discussion in Kawaguchi al. (2017) on how bound these two new terms. Without any further new idea, there is no other way than the ones developed in the literature so far: reduce the problem to bounding a Rademacher complexity (as it is done in Theorem 3.1), or use the PAC- -AC-Bayes framework, and so on.
More on numerical evaluation of path-norm In Dziugaite (2018, Section 2.9.1) is reported nu- merical evaluations after epochs of SGD on a one hidden layer network trained on a binary variant of MNIST. Furusho (2020, Figure 9 and Section 3.3.1) deals with 1d regression with 5 layers and 100 width. Experiments in Zheng et al. (2019) are on MNIST. Note that it is not clear whether the path-norm used in Zheng et al. (2019) corresponds to the one defined in Definition A.3. Indeed, the references given in Zheng et al. (2019) for the definition of the path-norm are both Neyshabur et al. (2015) and Neyshabur et al. (2017). but these two papers have two different definitions of the path-norm. The one in Neyshabur et al. (2015) corresponds to the norm of the path-lifting as defined in Definition A.3 (but in simpler settings: no pooling etc.), while the one in Neyshabur et al. (2017) corresponds to the latter divided by the margin of the estimator.
For completeness, let us also mention that it is reported in Dziugaite al. (2020); Jiang et al. (2020) whether the path-norm correlates with the empirical generalization error or not, but there is no report of numerical values of the path-norm. In Neyshabur et al. (2017) are reported the quotient of path- norms with margins, but not the path-norms alone.
Inherent limitations of uniform convergence bounds Theorem 3.1 has some inherent limitations due to its nature. It is date-dependent as it depends on the input distribution. However, it does not depend on the label distribution, making it uninformative as soon as θ is so much expressive that it can fit random labels. Networks that can fit random labels have already been found empirically (Zhang et al., 2021), and it is open whether this stays true with constraint on the path-norm.
Theorem 3.1 is based on uniform convergence bound 12 as any other bound also based on a control of a Rademacher complexity. Nagarajan & Kolter (2019) empirically argue that even the tightest
A uniform convergence hound on model class F is a bound on Ez su2)( generalization error f(7). This worst-case type of bound can lead potential limitations when F is too expressive.
44

---

Published as a conference paper at ICLR 2024
uniform convergence bound holding with high probability must be loose some synthetic datasets. If this was confirmed theoretically, this would still allow uniform bounds to be tight when con- sidering other datasets than the one in Nagarajan & Kolter (2019), such as real-world datasets, or when the estimator considered in Nagarajan & Kolter (2019) is not in @ (for instance because of constraints on the slopes via the path-norm).
Finally, Theorem 3.1 can provide theoretical guarantees on the generalization error of the output of learning algorithm, but only a posteriori, after training. In order to have priori guarantees, one should have to derive a priori knowledge on the path-norm at the end of the learning algorithm.
Comparison to PAC-Bayes bounds Another interesting direction to understand generalization of neural networks is the PAC-Bayes framework (Guedj, 2019; Alquier. 2021). Unfortunately, PAC- Bayes bounds cannot be exactly computed on networks that are trained in usual way. Indeed, these bounds typically involve a KL--dieegeene,, or something related, for which there is no closed form except for very specific distributions (iid Gaussian/Cauchy weights...) that do not correspond the distributions of the weights after usual training 1314, We are aware of two research directions that try to get over this issue. The first way is to change the learning algorithm by enforeing the weights to be iid normally distributed, and then optimize the parameters of these normal distributions, see for instance the pioneer work of Dziugaite & Roy (2017). The merit of this new learning algorithm is that it has explicitly been designed with the goal of having small generalization error. Practical performance are worse than with usual training, but this leads to networks with an associated non- vacuous generalization bound. To the best of our knowledge, this is the only way get vacuous bound and unfortunately, this does not apply to usual training. The second way to get over the intractable evaluation of the KL-divergence is try approximate the bound within reasonable time, and 2) try to quantify the error made with the approximation (Pérez & Louis, 2020). Unfortunately, to the best of our knowledge, approximation assumption of the weights that is not met in practice (e.g. iid Gaussian weights), approximation is costly, and the error is unclear when applied networks trained usually. For instance, the bound in Pérez& & Louis (2020, Section 5) 1) requires at least ((n²) operations to be evaluated, with being the number of training examples, thus being prohibitive for large n (Pérez & Louis, 2020, Section 7), and 2) it is unclear what error is being made when using a Gaussian process approximation of the neural network learned by SGD.
often based on a distribution
The randomness of the weights after training comes from the random initialization and the randomness in the algorithm (e.g. random batch in SGD). 14 For instance, independence is not empirically observed, see Frankle et al. (2020, Section 5.2)
15 Except, of course, for methods that are hased on the evaluation of the performance held-out data.
45


Reviews:
[{"review_id": "VgqUDcmjuv", "reviewer": "Reviewer_wKAQ", "summary": "The author extends the embedding in \"Stock & Gribonval, 2022\" to handle max pooling, averaging and bias in general neural network DAGs. The author uses the fact that neural networks are locally affine to introduce generalization bounds on modern architectures such as ResNets, VGGs, etc. The paper includes the embedding's definition and basic properties, the generalization bound and numerical experiments on multiple pre-trained ResNet models. It is evident from the experiments that the bound is tight and meaningful when the network is sparse, and irrelevant for deep dense networks. Despite this drawback, the work done in this paper takes the theory a step closer to practice.", "questions": "No questions", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and provide an important contribution for the understanding of generalization bounds. The included mathematical proofs and definitions are accessible and easy to read.", "weaknesses": "1) The numerical experiments were partial, and I would expect to see how the theoretical bound differs from an estimation of the generalization using some validation dataset.\n\n2) \"Proof of the Lipschitz Property\" in page 14 ends with an incorrect statement (IMHO). The boundaries of the constant regions must be examined, and the proof holds because there is a finite number of such regions.", "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": "", "extra_scores": {}}, {"review_id": "z90bUv06dr", "reviewer": "Reviewer_fyuf", "summary": "This paper presents the state of art result on generalizaiton bound of deep neural networks using path norm. In detail, it allows to consider any neural netowrks whose backbone is a DAG and the activation function is either identity, ReLU, or max pooling. Because this result handles any DAG, one can append a dimension of value equal to constant 1 for all data to extend the analysis networks with bias. Because the theoretical result in thie paper is so general, for the first time, the authors are able to evaluate the actual generalization bound on ResNet trained on Imagenet. Though the path norm based bound presented in this paper is still vacuous, this paper contains several instereting experimental findings and shed light to future researches.", "questions": "1. measurable condition in Lemma D.1 seems unnecessary?\n\n2. Why 2-norm of $\\Phi(\\theta)$ is relevant? Isn't it small just because the number of paths is huge? It doesn't seem to be a valid generalization bound even for a very simple 2-layer linear network. Is there any real evidence that 2-norm of $\\Phi(\\theta)$ could be useful for indicating generalization?\n\n3. Some minor typos: (1). $\\overline N_{in}$ seems not defined in appendix A; (2). The third row of the first equation on page 29 seems missing a factor of $5^d$\n\n4. I wonder if the authors can just ignore all the linear activations by linking the incoming nodes of the current nodes to the outgoing nodes of the current node. This should not change the path norm. If this is true, then we should not count the number of Conv layers in ResNet, but the max number of ReLU and max pooling along the path, which is smaller than the former for ResNets.\n\n5. Though the writing quality is already great, I still feel like the paper can benefit from first providing a result without any bias, which would greatly simplify the notations in the theoretical statement and the proof. Then the authors can point out that the results can be generalized to networks with bias by appending a constant 1 dimension in the input (as it is done now), adding an edge between the constant 1 input dimension to the neuron, and then calling the main result. Writing the theorem in this way would clearly explain to the readers where the plus one in $d_{in}+1$ and the $\\max(n,\\ldots)$ in $\\sigma$ comes from. (Theorem 3.1)\n\n\n6. The statement of Lemma D.2 is a little bit confusing because $\\Theta$ is not arbitrary, but the one preprocessed by Algorithm 1. Maybe it is more clear to just define $r$ as the sup of 1-norm of the last layer of $\\Theta$? A similar issue occurs for Lemma D.3, where the authors can just say the 1-norm of incoming weights of non-output node in $\\Theta$ are bounded. In this way, Lemma D.2 and Lemma D.2 will together motivate Algorithm 1 and the path norm as a generalization metric.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper is very well-written. It is very easy for me to understand the main result and the main theoretical challenges to overcome. The notations are consistent and the mathematical statements are precise. I checked the proofs of several core lemmas and they all look correct to me.\n\n2. The result presented in this paper is very elegant, which unifies several previous results on path-norm. The core proof strategy is a new peeling argument, which relates the Rademacher complexity over a set of nodes to that of the incoming nodes of the set of nodes. The proof uses several new lemmas, which generalizes previous results.\n\n3. The authors not only derive a better and unified path-norm generalization bound but also apply their bound on real datasets and architectures, i.e. ResNets of various sizes on Imagenets. Though their experimental results indicate that the new path norm-based bounds are still vacuous, they note that sparse networks greatly reduce the bound, which may shed light for future research.", "weaknesses": "1. I think Setting 1 of Lemma C.1 can be obtained by a simple application of the well-known scalar contraction inequality (Ledoux & Talagrand, 1991). Given $v\\in V$ and $t\\in T^v$, we can embed it into a higher dimensional space $\\mathbb{R}^{I\\times T}$ by defining $\\tilde t(v,t) = [0, 0 ,\\ldots, v,\\ldots, 0]$ as a $I\\times T$ matrix. We further define $\\tilde f_{i,v}(x) = f_i(x)$ for all $x\\in\\mathbb{R}$. Therefore we have the following which is exactly the conclusion of Setting 1 of Lemma C.1 \n\n$$\\mathbb{E} \\max_{v \\in V} \\sup_{t \\in T^v} G \\left( \\sum_{i \\in I} \\varepsilon_{i,v} f_i(t_i) \\right) $$\n\n$$=\\mathbb{E} \\max_{v \\in V} \\sup_{t \\in T^v} G \\left( \\sum_{i \\in I} \\varepsilon_{i,v} f_i([\\tilde t(v,t)] _{i,v}) \\right)$$\n\n$$=\\mathbb{E} \\max_{v \\in V} \\sup_{t \\in T^v} G \\left( \\sum_{i \\in I, v' \\in V} \\varepsilon_{i,v'} \\tilde f_{i,v'}([\\tilde t(v,t)] _{i,v'}) \\right)$$ \n\n$$= \\mathbb{E} \\max_{v \\in V} \\sup_{t \\in T^v} G \\left( \\sum_{i \\in I, v' \\in V} \\varepsilon_{i,v'} [\\tilde t(v,t)] _{i,v'} \\right) $$\n\n$$=\\mathbb{E} \\max_{v \\in V} \\sup_{t \\in T^v} G \\left( \\sum_{i \\in I} \\varepsilon_{i,v} [\\tilde t(v,t)] _{i,v} \\right)$$\n\n$$=\\mathbb{E} \\max_{v \\in V} \\sup_{t \\in T^v} G \\left( \\sum_{i \\in I} \\varepsilon_{i,v} t_i \\right) $$", "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": "", "extra_scores": {}}, {"review_id": "VGqfKxTSR2", "reviewer": "Reviewer_m3hb", "summary": "Motivated by the fact that path-norms provide a way to bound generalization errors and satisfy several nice properties (e.g. easy to compute, invariant under parameter rescalings and neuron permutations, etc), the paper introduces a notion of path-norms that can handle general ReLU networks with biases, skip connections, and max pooling. Furthermore, they provide path-norm based generalization bounds that match or beat existing path-norm based generalization bounds. Along the way, they prove new peeling and contraction lemmas for computing Rademacher complexities.", "questions": "Can similar generalization bounds be proven for more general $L^p$ path-norms without incurring a large dimension dependence?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Peeling and contraction lemmas for computing Rademacher complexities for more complex networks are novel and interesting. \n\nThe notion of path-norms the paper introduces can handle very general ReLU networks, and the generalization bounds depending on the more general path-norm do better or recover existing path-norm based generalization bounds.", "weaknesses": "The paper establishes generalization bounds with respect to $L^1$ path-norms (as opposed to general $L^p$ path-norms). \nIn the experiments, $L^1$ path-norms tend to be extremely large (at least $10^{30}$) which makes the generalization bounds vacuous.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)