A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations
Authors: Antoine Gonon
Nicolas Brisebarre
Elisa Riccietti
Rémi Gribonval
Venue: ICML 2025 poster (2025)
Keywords: relu neural networks
Lipschitz
rescaling-symmetry
path-lifting
Primary area: theory->deep_learning
TL;DR: This paper bounds function distances between ReLU networks via a metric that is invariant to rescaling-symmetries.

Abstract: Robustness with respect to weight perturbations underpins guarantees for generalization, pruning and quantization. Existing
guarantees rely on *Lipschitz bounds in parameter space*, cover only plain feed-forward MLPs, and break under the ubiquitous neuron-wise rescaling symmetry of ReLU networks. We prove a new Lipschitz inequality expressed through the $\ell^{1}$-*path-metric* of the weights.  The bound is (i) *rescaling-invariant* by construction and (ii) applies to any ReLU-DAG architecture with any combination of 
convolutions, skip connections, pooling, and frozen (inference-time) batch-normalization —thus encompassing ResNets, U-Nets, VGG-style CNNs, and more. By respecting the network’s natural symmetries, the new bound strictly sharpens prior parameter-space bounds and can be computed in two forward passes. To illustrate its utility, we derive from it a symmetry-aware pruning criterion and
show—through a proof-of-concept experiment on a ResNet-18 trained on ImageNet—that its pruning performance matches that of classical magnitude pruning, while becoming totally immune to arbitrary neuron-wise rescalings.

A Rescaling-Invarian Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations
Antoine Gonon 12
Nicolas Brisebarre
Elisa Riccietti
Rémi Gribonval
Abstract
distance d(0, 0) and a constant Cz:
Robustness with respect to weight perturbations underpins guarantees for generalization, pruning and quantization. Existing guarantees rely on Lipschitz bounds in parameler space, cover only plain feed-forward MIPs, and break under the ubiquitous neuron-wise rescaling symmetry of ReLU networks. We prove a new Lipschitz in- equality expressed through the -epttth-metric of the weights. The bound (i) rescaling-invariaa by construction and (ii) applies any ReLU- DAG architecture with any combination of con- volutions, skip connections, pooling, and frozen (inference-time) batch-normalizztion -hhus en- compassing ResNets, U-Nets, VGG-style CNNs, and more. By respecting the network's natural symmetries, the new bound strictly sharpens prior parameter-space bounds and can be computed in two forward passes. To illustrate its utility, we pruning crite-
[R(()) - Ror & Czd(0,0).
(I)
This controls the robustness of the function Rg with re- spect to changes the parameters 0, which can be crucially leveraged to derive generalization bounds (Neyshabur et al., 2018) or theoretical guarantees about pruming or quantiza- tion algorithms (Gonon et al., 2023). Yet, to the best of our knowledge, such bounds remain relatively little explored in the literature, and existing ones are expressed with ge metrics on parameters (Gonon et al., 2023; Neyshabur et al., 2018; Berner et al., 2020). For example, such bound is known (Gonon et al., 2023, Theorem III.1 with oc and q = 1) with
d(0, (' = 110 0' loc C₂ = (W]|=]l< + 1)WI2R
(2)
in the case of a layered fully-connected neural network Rø(x) = My. ReLU(M,,-1
derive from it a symmetry proof-of-coneeee exper-
ReLU(M,x)) with L lay- ers, maximal width W, and with weight matrices M, having some operator norm bounded by R. Moreover, these known bounds are not satisfying for at least two reasons:
rion and show-throwe iment on a R 8 trained on ImageNet- that its pruning performance matches that of classi- cal magnitude pruning, while becoming totally immune arbitrary neuron- wise rescalings.
they are not invariant under neuron-wis wise rescalings of the parameters 0 that leave unchanged its realization Rg. As we will show, this implies that numerical evaluations of such bounds can be arbitrarily large;
1. Introduction
An important challenge about neural networks is to upper bound as tightly as possible the distances between the so- called realizations (i.e., the functions implemented by the considered network) Ro, Ra. with parameters 0, O' when
they only hold for simple fully-connected models orga- nized in layers, but not for modern networks that include pooling, skip connections, etc.
evaluated at input vector x, in terms of a (pscudo-)>
To circumvent these issues, we leverage the so-called path- lifting, a tool that has recently emerged (Stock Gribonval, 2023; Cola-Pelisssier et al., 2022; Marcotte et al., 2023; Gonon et al., 2024a) in the theoretical analysis of modern neural networks with positively homogeneous activations.
'ENS de Lyon, CNRS, Inria, Université Claude Bernard Lyon LIP, UMR 5668, 69342, Lyon cedex 07, France IInstitute Mathe- matics, EPFL, Lausanne, Switzerland 'CNRS, ENS de Lyon, Inria, Université Claude Bernard Lyon 1, LIP. UMR 5668, 69342, Lyon cedex 07, France "Inria, CNRS, ENS de Lyon, Université Claude Bernard Lyon LIP, UMR 5668, 69342, Lyon cedex France. Correspondence to: Antoine Gonon <antoine, gonon @ epfl.ch>.
Main contribution. We introduce natural (rescaling- invariant) metric based on the path-lifting, and shows that it indeed yields a rescaling invariant upper bound for the distance of two realizations of a network. Specifically, denot- ing (v() the path-lifting (a
bascaling-invarian
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
vector whose

---

A Descaling-Invariin Lipschitz Bound using Path-Metries
Table 1: The path-lifting provides an intermediate space between parameters and function spaces.
0
$(0)
Rø
parameters space
path-lifting space
function space
what we end up analyzing
what we should analyze?
what we want to analyze
dim<; oo? rescaling-invarianti relation to Rs
locally polynomial
locally linear
definition will be recalled in Section 3) of the network pa- rameters 8, we establish (Theorem 4.1) that for any input æ, and network parameters 0, 0' with the same entrywise signs:
ization error control. We review these three different use of parameter-space Lipschitz bounds in Section 2.1, and then highlight in Section 2.2 how our new, sescaling-invarian bound (Theorem 4.1) interfaces with recent notions of scale- invariant sharpness.
[1) (x)lla
< max (1=21|00: 1) (0) - 111- (3)
2.1. Parameter-Space Lipschitz Bounds in Practice
We call d(0, (10,,0)= = ( (10 the el -path-metric, by analogy with the so-called e² -path-oor [0)]],, see egg. (Neyshabur et al., 2015; Barron Klusowski, 2019; Gonon et al., 2024a). Of course, since the -norm is the largest e norm (q > 1), this also implies the same inequality for any (4-norm the left-hand side. Besides being intrinsically asscaling-invarian Inequality (3) holds for the very same general neural network model as in Gonon et al. (2024a) that encompasses pooling, skip connections and so on. This solves the two problems mentioned above and improves on Equation (2). Finally, we show that, under conditions that hold in practical pruning and quantization scenarios, the path-metric is easy compute in two forward passes, and we provide the corresponding pytorch implementation.
Parameter- space Lipschitz (or "perturbation" / "sensitiv- ity") bounds already underpin several practical guarantees, but prior results are restricted to plain MLPs and ignore rescaling symmetry.
(i) Pruning. Provable pruning schemes quantify how much the output drifts when weights set to zero. (Liebenwein et al., 2020) and (Baykal et al., 2019) derive such guaran- tees from layer-wise-but constants, and the same mechanism underlies Theorem 5.4 of (Baykal et al., 2022). Our Theorem 4.1 offers an architecture-agnostii, symmetry-aware alternative; Sec- tion illustrates this ResNet-18.
(ii) Quantization. Bounding the error induced by weight rounding likewise depends on how the network reacts to small parameter perturbations. Gonon et al. (2023) provide such bounds for fully-connected nets, while Zhang et al. (2023) and Lybrand & Saab (2021) control the error at the neuron level. Extending those guarantees to CNNs, ResNets or U-Nets requires global, symmetry-invariant Lipschitz constant- what provide in Theorem 4.1.
Our main theoretical finding, Inequality (3), together with the known properties of & (Gonon et al., 2024a) confirms that the path-lifting & provides an intermediate space be- tween the parameter space and the function space, that shares some advantages of both, see Table 1.
Plan. Section 2 places contribution in context. Section 3 recalls the path-lifting framework of Gonon et al. (2024a) and the notational tools we will use. Section 4 presents our central result-a rescaling-invarii invariant Lipschitz bound expressed through the e ee--path-mette (Theorem 4.1)-and and explains how sharpens existing bounds and can com- puted in two forward passes. Finally, Section 5 shows how the new bound yields symmetry- aware pruning criterion, shown to match in ofooeeef-concept experiment the accu- racy of magnitude pruning, while becoming totally immune to neuron-wise rescalings.
(iii) Generalization via covering numbers. Several compression-stylee analyses (e.g., Arora et al., 2018; Bartlett et al., 2017; Schnoor et al., 2021) follow two steps: (1) parameter-space Lipschitz bound shows that the e-ball around a weight vector maps into an e'-ball around its realization Rg in function space, yielding upper bound that function-space covering number; (2) this covering bound is plugged into Dudley's entropy integral to obtain Raadmacher-complee
(and thus generalization) bound. Because our Lipschitz constant is rescaling-invarian and holds for modern DAG networks, the same pipeline runs without restricting to MLPs and without the looseness intro-
2. Related Work
Understanding how small weight changes affect a network's 's output cnucial, e.g., for pruning, quantization, or general-
2

---

A Rescaling-Invariin Lipschitz Bound using Path-Metries
duced when one first factors out rescaling symmetries.
3.1. Rescaling Symmetries.
Across pruning, quantization and generalization, two limitations of previous parameter-space bounds-latt of rescaling-inves invariance and restriction to plain MLPs are precisely the issues addressed by Theorem 4.1.
All network parameters (weights and biases) are gathered in parameter vector 6, and we denote Rø(x) the output of the network when evaluated at input (the function + Rg(x) is the so-called realization of the network with parameters 0). Due to positive-homogeneityy of the ReLU function + (t) == max(0, t). in the simple case of a single neuron with no bias we have (a) = v max(0, (u, x)) with 0 (u. v), and for any > O, the "rescaled" parameter 0 (Au, }) implements the same function R3 Ro. A similar
2.2. Relation to Scale-Invariaas Sharpness
Sharpness metries (Tsuzuku et al., 2020: Rangamani et al., 2021; Kwon et al., 2021; Wen et al., 2023; Andriushchenko et al., 2023) measure how much the loss increases under parameter perturbations, often normalizing those perturba- tions to remove rescaling dependencies. Our perspective is complementary:
property holds for the general model of (Stock & Gribonval, 2023; Gonon, 2024) leading to the notion of rescaling rescaling-equivalent parameters, denoted ~ 0, which still satisfy Rg Ro-
directly bound the output change [[(x)) Ra (x)]] independent of any loss or data distri- bution. As shown in Section 4.4, whenever the loss C(ú. y) is Lipschitz in its first argument (e.g., cross-entropy or MSE on a compact domain), Theorem 4.1 yields an immediate upper bound on several scale-invariant sharpness definitions, thus providing loss-agnostic control over the same pertur- bation neighborhoods.
Need for rescaling-ivarrian Lipschitz bounds. Consider our initial problem of finding pseudo-metrie d(0, 8') and constant C2 for any input x; for which (1) holds. The left hand-side of (1) is invariant under rescaling-symmettee
if i ~ 0 then [[) - Rg (1)]l = [[)o(x) - Ro (z)lli- However, when d(.,)) is based on a standard t" norm, the right hand-side of (1) is not invariant, and in fact supsre |10 - 1'I,,- = +oc, so the bound can in fact arbi- trarily pessimistic:
3. ReLU DAGs, Invariances, and Path-Lifting
The neural network model we consider generalizes and unifies several models from the literature, including those from Neyshabur et al. (2015); Kawaguchi et al. (2017); DeVore et al. (2021); Bona-Pellissier et al. (2022); Stock & Gribonval (2023), detailed in Gonon et al. (2024a, Definition 2.2). This model allows for any Directed Acyelic Graph (DAG) structure that combines standard setrss-max-poolinng average-pooling, skip connections, convolution, and (inference-time / frozen form) batch nor- malization-theree covering modern networks such as ResNets, VGGs, AlexNet, and many others. The complete formal definition appears in Appendix A.!
d(0 0')
sup 8~0
[[((x) - Rø (I)
OC.
Although in general one could make a bound such as (1) invariant by considering the infimum
inf d(0, 0))
8-0.0' 0m000'000 8g
this infimum may be difficult to compute in practice. There- fore, a "good" bound should ideally be both invariant under rescaling symmetries and easy compute. Invariance to rescaling symmetries is precisely the motivation for the introduction of the path-lifting.
Skip
Skip
3.2. Path-Lifting & and Path-Activation Matrix A
MaxPool
AvgPool
Background. The path-lifting map Tb and its associated f'-path-norm were introduced to equip ReLU networks with a coordinate system that is invariant under neuron-wise rescaling. This construction has enabled advances in iden- tifiability (Stock & Gribonval, 2023; Bona-Pellissier et al., 2022), analysis of training dynamies (Marcotte et al., 2023), input-space Lipschitz bounds (Gonon et al., 2024a), and (PAC- and Rademacher) generalization guarantees (Neyshabur et al., 2015; Gonon et al., 2024a).
Affine
Affine
ReLU
Affine
ReLU
Affine
Figure 1: A network with the same ingredients ResNet.
This DAG-ReLU framework does not cover (i) attention mech- invariant
anisms and (ii) normalization layers that are not rescaiing-invariant (c.g., layer normalization, group normalization). Batch normal- ization is covered because at inference time its statistics are fixed, so it hehaves an affine layer and remains compatible with the path-lifting framework of (Gonon et al., 2024a).
This paper does not redefine the path-lifting but leverages it to derive, for the first time, a rescaling-invariant invariant parameter- space Lipschitz bound that holds for general DAG-ReLU architectures.
3

---

A Rescalling Lipschitz Bound using Path-Metrics
Definitions (informal). Given network parameters 0 and input v; we consider two objects from Gonon et al. (2024a, Definition A.I): the path-lifting vector (0) and the path- activation matrix A(0, æ). Below we give simplified de- scription sufficient for understanding our main results; full definitions are deferred to Appendix A.
0 (#1 Mi..... "k 01...., Uk) where uy IRd,, vs E IRu,, and realization
Ro (x))) max(0, (c, wi)) Rdu,
Then, the path-lifting is
( - (u.v, (EE( E Haddddar
u gu
The path-activation matrix is
A(0, = Ia,, @ (1 (1(m))))0) O Idnn
W
concatenated with a zero column (no biases here). Here, La is the x d identity matrix, and 1a (resp. 0a) is the vector of ones (resp. zeros) of size
Figure 2: The path-lifting coordinate ()) for the path p= u - e + w the product of the weights along that path: $ (0) Ou-vv 00-bw.
It is straightforward to verify that both o(0) and A(0,z) remain unchanged under the neuron-wise rescaling 0 + o 0, defined by (v,, u;) + (2, Aau;) for any À E (B>z))* ) This transformation leaves the function Rg unchanged, i.c., Rg = Rxoe (Gonon et al., 2024a).
The vector (0) E R is indexed by the set P of paths in the network-iee. sequences of neurons from an input to an output. For each path, its coordinate in ((0) is simply the product of the weights along that path (ignoring non- linearities). For example, if p - + is path starting from input neuron and ending at an output neuron w. and if Oa-b denotes the weight on edge + b, then (0) = 0u- as illustrated in Figure 2.
4. A Rescaling Invariant Lipschitz Bound
Our main result, Theorem 4.1, is Lipschitz bound with respect to the parameters of the network, as opposed to widespread Lipschitz bounds with respect to the inputs. It precisely proves that (1) holds with a rescaling-invarian pscudo-distance (called the e -path metric) defined via & as d(0, 8') == (0) (0f') 1l and C, max([| 1).
The path-activation matrix A(0,z) x)) E (),1]Pxdl xda encodes the information about non- non-lineasssies, storing which paths are active (i.e., all ReLUS along them are on) for a given input v. Entry (0, coordinate u and all neurons along p are activated.
if path p starts at input
Theorem 4.1. Consider a ReLU DAG neural network, cor- responding to an arbitrary DAG network with max-pool etc. as in Section 3, see Figure I for illustration and Defini- tion A.2 in the appendix for precise definition. Consider parameters vectors 0, 6' for every coordinate i, it holds 0,6% > 0, thenfor every input x:
In networks with biases, additional paths starting from hid- den neurons are included in P, and A(0, .) is extended to {0. 1) +x) to include bias contributions.
Key properties of (F. These two objects enjoy the following critical features:
|| (x) - Ro (x)]l
((0) is vector of monomials in the weights.
< max([]>]]b>. 1))( ((0')l (5)
A(0, æ)) is binary, piecewise-constene
matrix of (0, z).
Moreover, for every such neural network architecture, there are non-negative parameters 9 # 8' and non-negative input x such that Inequality (5) is an equality.
* Both ((#) and A(B, z) are rescaling-invant invariant: if f ~ 0
(i.e., 0 and 0 only differ by neuron-wise rescaling, leaving
Rg = R3 unchanged), then (0))= = (0) and A(O, x)) =
A(f, .z) for all (Gonon, 2024, Theorem 2.4.1).
Since || 1l, & ||. 111 for any > 1, Inequality (5) implies the same bound with the (4-morm on the left hand-side.
The network output can be recovered directly from these quantities. For scaler-valued outputs Ro(x))
We sketch the proof in Section 4.5. The complete proof is in Appendix B we actually prove something slightly stronger, but we stick here to Inequality (5) for simplicity.
( )
[z) = (b(6),
(4)
and similar form holds for vector-valued networks (Gonon et al., 2024a, Theorem A.
As discussed in Section 2.1, the parameter-space Lipschitz bound (5), like any such bound, can be incorporated into various pipelines- either to establish theoretical guaran- tees or to guide practical methods (e.g., algorithms that
Example (ome-hidden-layer network). Consider a one- ladden-layer ReLU network without bias, with parameters

---

A Descallig-Invariin Lipschitz Bound using Path-Metrics
minimize these bounds), with applications to pruning. quan- tization, generalization. In Section 5, we will focus on pruning, Regarding generalization, let us briefly note that this bound can be used to derive Rademacher complexity bound for the class of functions F == {Ro [1)l1 & r} = Usigns [R. [1)(0 < r, (0) = s}. To bound this complexity, Dudley's 's integral reduces the task to bounding the covering numbers of each fixed-sign sub-ball (Ro, [1](1 & r, sgn(0) ()) s}. The inequality (5) enables exactly this, by linking the covering numbers of these func- tion classes to those of the corresponding finiteddimensional sets (0) (0) = s, (0)ll & rj. A full derivation of this approach can be found in Theorem 4. of (Gonon, 2024). That said, the resulting (Rademacher) generaliza- tion bounds are typically booser-by factor of roughly / ttparams-than those of Gonon et al. (2024a), who also leverage the path-norm but through a more refined analysis.
path-metric that turn out yield exact implementations in cases of practical interest.
A key fact on which the approach is built is that the e' e'-ptth- norm can be computed in one forward pass (Gonon et al., 2024a). Since, by the lower triangle inequality, we have
[ [((()) < [ ((0))l,,
(6)
the left-hand side of (6) serves an approximation that can be computed in two forward passes of the network?.
As we now show, this is an exact evaluation of the e- f--path- metric under practical assumptions, and completed by a rescaling-invant invariant upper bound (cf. Inequality (8) below).
Lemma 4.2. Inequality (6) is an equality as soon as [ > [+'))) coordinatewise: in this case we have
[ (00))l = (0) - (1'
In the rest of this section, we discuss the assumptions of the theorem, the practical computation of the bound and the positioning with respect to previously established Lipschitz bounds.
Proof. For vectors a, with |as| > |bx| for every i, we have
|alli - 116111 = Σ lai| - 1b,1 = Σ la, bul = ||a 6111.
4.1. Why the same-sign assumption is necessary
A hard impossibility (new contribution). Let us highlight that the condition 020, > O Vi in Theorem 4. is not tech- nical convenience. We exhibit in Figure 6 (Appendix B) minimalistic ReLU network for which no finite constant C, can satisfy (1) once two weights change sign. By prepend- ing and appending arbitrary sub-networks to that minimal counter-example, one gets families where all but two edges keep their sign, yet the same divergence occurs. This impos- sibility shows that every rescaling-invarian invariant parameter-space Lipschitz bound based on the path-lifting must, at min- imum, control sign changes. We are not aware of a prior formal statement of this theoretical impossibility.
An important scenario where [+(0)| > |0(6') indeed holds is when [0] > 10'| coordinatewise. The latter is true in at least two significant situations: when 8' is obtained from 0 by pruning, or through quantization provided that rounding is done either systematically towards zero or sys- tematically away from zero
Note that 0 > |0'| is not the only situation where [2(0) > / ((').. J. For instance, due to the rescaling -ivaaiinnnnviiancee of (-)., if Ô is rescaling-equiivalnnt to 0 the coordinatewise inequality (b (+) > [+((') remains valid, even though in general such
0 non longer satisfies [0] > |0'| coordinatewise.
Even out of such practical scenarios, the e -path-mmetric also satisfics an invariant upper bound.
Practical relevance. Many real-world workflows preserve the signs: pruning, uniform quantization, and small SGD steps preserve them; locally, any non-zero 0 admits an & ball where signs are fixed. When occasional flips do occur, Theorem 4.1 I remains useful as a local building block: one may use it each fixed-sign quadrant individually and then glue the results established on each quadrant together exactly the strategy evoked for covering-number number general- ization proofs (see the discussion after Theorem 4.1).
Lemma 4.3 (Informal version of Lemma F.3). Consider a DAG ReLU network with L layers and width W. For any parameter O, denote by ((O) its normalized version, deduced from 0 by applying each neuron has its vector of incoming weights equal to 1, except for output neurons. It holds for all parameters B 8':
such that
[b)(0) - .(0')l
4.2. Approximation and exact computation of l --path-metrice
< (()
Since (0) is a vector of combinatorial dimension (it is indexed by paths), it would be intractable to compute the ll -appath metric (0) - ((0')l, by direct computation of the vector ((0)= (60). In this section we investigate efficient and saccaling-invariaa approximations of the (1_
"For a ResNet18, we timed it to 15ms. Specifically. we timed the function get.path.norm available at github. con/ aaponor/pathnnom_toookce. pytorch. utils benchmark. Experiments were made on an NVIDIA GPU A100-40GB, with processor AMD EPYC 7742 64-Core.
using
5

---

A Rescaling-Invariinn Lipschitz Bound using Path-Metries
The proof is in Appendix F. In all the cases of interest we consider, the lower bound (6) is exact consequence of Lemma 4.2. We leave it to future work to compare the lower bound with the upper bound of Lemma 4.3 in specific cases where the lower bound is inexact.
4.4. Implication for scale-invariant sharpness
Let é: Rdd"xg44 Rx be x-Lipschitz in its first argument with respect to e -norm, and assume data distribution 'D over (æ, (). For any parameter 0 and perturbation radius p > O, consider the scale-adaptatin worst-case sharpness (see Definition 2 in Kwon et al. (2021), or Equation 1 in Andriushchenko et al. (2023)):
((fm)
((00)))))
Sharp, sup |00 -1,
(1e il
BOODD ((Ro+s(x))))) ((Ro(x).
((ta)
4: (10
o(((
Lemma 4.5. For every E (0, and every 0,
((4))
+ O(t)
t (()())
Sharpp(0) & K B.ED,, | 1)] | + - -
sup |10|
Figure 3: Illustration of the proof of Theorem 4.1, see Sec-
tion 4.5 for an explanation.
Proof. Lipschitzness of the loss yields (Ro)a())),)) (Roo()),
Æ|] Ro+o(x) - Ro(=)]l1- The condition 1 の 10 || < p implies || o 10 & p. Thus 8, < 10:|p < 10,l for every coordinate i and we get sgn(0; + 5,) = =gn(..). Therefore Theorem 4.1 applies
4.3. Improvement over previous Lipschitz bounds
Inequality (5) improves on the Lipschitz bound (1) specified with Equation (2), as the next result shows.
and gives [Ro+((x) (o(x) & max([]=]]a>: 1) 8) (0)
Lemma 4.4. Consider a simple layered fulll-coonnectr neu- ral network architecture with I. > 1 layers, corresponding to functions Ro(x)= M2 ReLU(M,-1 ... (M, with each Me denoting matrix, and parameters 0 (M1....,MB) ML) For matrix M, denote by ||M|| 1, the maximum -norm of row of M. Consider R 3 1 and define the set θ of parameters = (MI,..., ML) such that | & R for every C E []. Then, for every parameters 0,0 e
Lemma 4.5 shows that our path- metric controls the scale- adaptative sharpness notions used, e.g., in (Kwon al., 2021) and (Andriushchenko et al., 2023).
4.5. Proof sketch of Theorem 4.1 (full proof in Appendix B)
Given input xr, the proof of Theorem 4.1 consists in defining trajectory t E [0, 1] + O(t) E θ (red curve in Figure 3) that starts at 0, ends at 0', and with finitely many breakpoints 0 = to < 4 < ... < 4m = such that the path-activations A(((t), x) are constant on the open intervals & E (42, f1+1). Each breakpoint corresponds to value where the activation of least one path (hence at least one neuron) changes in the neighborhood of O(t). For instance, in the left part of Figure 3, the straight green line (resp. quadratic green curve) corresponds to a change of activation of ReLU neuron (for given input x to the network) in the first (resp. second) layer.
(0) (0')l &
8'11oo.
Moreover the right hand-side side can be arbitrarily worse that the el -pseudo-metrt in the left hand side: over all rescaling- equivalent parameters 0 ~ 0, it holds
110 - 801 00. [0) (0'))
sup 6~0
The proof of Lemma 4.4 is in Inequality (23) in Appendix G.
The invariant Lipschitz bound (5) combined with (9) yields a (non-invariant) bound on |R (xx) ))- (x:]li:
With such a trajectory, given the key property (4), each quan- tity Rooe, (z) Rott (2)] can be controlled in terms of ((((tt)) ((((t=-)) 1)] and if the path is "nice enough", then this control can be extended globally from to to 4m-
max([|=]|>>>)) 1)LW R= 110 0' lol
In comparison the generic bound (1) specified with (2) reads
(W|l + 12 0'
There are two obstacles: 1) proving that there are finitely many breakpoints t4 as above (think of t +> 2 sin 1/t) that is n-times continuously differentiable but still crosses = an infinite number of times around zero), and 2)
As soon as || > the latter is a looser bound than the former.
6

---

A Descaling-Invariin Lipschitz Bound using Path-Metries
proving that the length - of the broken line with vertices ((((tz)) (dashed line the right part of Figure 3) is bounded from above by [))
(((()))) (00()++)))l
into account these global dependencies (Singh & Alistarh, 2020; Yu et al., 2022; Benbaki et al., 2023). This line of work recently culminated in CHITA (Benbaki et al., 2023), pruning approach that scales up to millions of parameters through substantial engineering effort.
((0')lzz 112 times reasonable factor. Trajectories satisfying &
these two properties are called "admissible" trajectories.
The first property is true as soon as the trajectory H (t) is smooth enough (analytie, say). For this, we will notably exploit that the output of ReLU neuron in the d-th layer of layered fully-connected network is piecewise polynomial function of the parameters 0 of degree at most d (Gonon et al., 2024a, consequence of Lemma A.1). (Bona- Pellissier et al., 2022, consequence of Propositions and 2). The property second is true with factor one thanks to a monotonicity property of the chosen trajectory.
Here, we introduce a path manh-magnitude cost defined for each individual weight but that depends on the global configura- tion of the weights. Just as sensitivity- costs (LeCun et al., 1989), these costs should in principle be re-computed after each pruning decision. While taking these global de- pendencies into account is expected to provide better perfor- mance, this is also expected to require a huge engineering effort, similar to what has been done in (Singh & Alistarh, 2020; Yu et al., 2022; Benbaki et al., 2023), which is be- yond the scope of this paper. Our goal here more modest: we aim at providing simple proof-of-concep to show the promises of the path-lifting for seccalingiivvrrinn pruning.
The core of the proof consists in exhibiting a trajectory with these two properties. To the best of our knowledge, the proof of Inequality (3) is the first to practically leverage the idea of "adequately navigating" through the different regions in where the network is polynomial' by respecting the geometry induced by 4, see Figure 3 for an illustration.
Notion of pruned parameter. Considering a neural net- work architecture given by a graph G. we use the short- hand RC to denote the corresponding set of parameters (see Definition A.2 for a precise definition). By definition, pruned version O' of 0 R is a "Hadamard" product 0' = == @ 0, where denote 1G E BRC the vector filled with ones, e; E RR the i-th canonical vector, s; == 1 Cg. and introduce the specialized notation 0_, == 8; @ 0 for the vector where a single entry (the weight of an edge or the bias of a hidden or output neuron) of 8, indexed by i, set to zero
5. Rescaling-Invariant Pruning
{0, 1] and ||s||a is "small". We
We exploit Inequality (3) to design a pruning rule that is both effective and invariant to neuron-wise rescaling. Instead of ranking weights by their magnitude, we rank them by their l' --path-metric contribution. We show in a proof-of-coneept on a ResNet-18 trained on ImageNet- Ik under the lottery- ticket "rewind-and -aiiid------i----une fine-tune" schedule (Frankle al., 2020) that this auth-magnitude rule achieves the same accuracy as classical magnitude pruning while becoming totally immune to arbitrary rescalings.
5.2. Proposed rescaling-invane
pruning criterion
The starting point of the proposed pruning criterion is that, given any 0 the pair 0, 0' with 8' == 8 @ 0 satisfies the assumptions of Theorem 4.1, hence for all input x we have [R((x) - Rg (x)) < (0) +<0')]l max(1, [|rl|=)))) Spe- cializing this observation to the case where single entry (the weight of an edge, or the bias of hidden or output neu- ron indexed by i) of 0 is pruned (i.e., 0' = 0-:) suggests the following definition, which will serve as a pruning criterion:
5.1. Pruning: a quick overview
Pruning typically involves ranking weights by a chosen cri- terion and removing (setting to zero) those deemed less important (Han et al., 2016). Early criteria considered either weight magnitudes (Hanson& & Pratt, 1988; Han et al., 2016) or the loss's ss sensitivity to each weight (LeCun et al., 1989; Hassibi & Stork, 1992). Building on these foundations, more sophisticated pruning methods have emerged, often formulated as complex optimization problems solved via advanced algorithms. For example, consider the entrywise loss's 's sensitivity criterion of (LeCun et al., 1989). In princi- ple, all the costs should be recomputed after each pruning decision, since removing one weight affects the costs of the others. A whole literature focuses on turning the cost of (LeCun et al., 1989) into an algorithm that would take
Definition 5.1. We denote
(10) This measures the contribution to the poth-norm of all paths p containing entry i: when i & p we have (0_.)) = (,),),
Path-Mag(0, () = (0) (0--))l
while otherwise (,,(0_,) = O. Since f and f_, satisfy the assumptions of Lemma 4.2 we have
Path Path-Mag(0,3) i) = ||0(0)]1 - (10(0_)))1
(1I)
(7)
'The mapping (0, x) + (x) is indeed known to he piece- wise polynomial in the coordinates of 0 (Gonon et al., 2024a, consequence of Lemma A. BooaaaaaaPlll et al., 2022, conse- quence of Propositions and 2).
Σ
(,,
Σ
[0)(
pEP
DEPREPD
Σ [,,())
(12)
PEPREP
7

---

A Rescaling-Invarian Lipschitz Bound using Path-Metrics
Table 2: Comparison of pruning criteria across key properties. Being data-specific or loss-specific can be both strength (leveraging the training loss and data for more accurate pruning) and a limitation (requiring access to additional invariant ensures the pruning mask is unaffected by neuron- wiie weight rescaling.
information). Being rescaling-ivvarian
Criterion
Rescaling- Invariant
Error bound
Data-
Loss-
Efficient to
Versatile"
Specifie
Specifie
Compute
Magnitude
No
Yes (1)-(2)
No
No
Yes
Yes
Coss-Sensittvvtty
Yes in theory
No
Yes
Yes
Depends*
Yes
(Taylor Expansion)
Not in practice
Path-Magnitude
Yes
Yes - (13)
No
No
Yes
Yes
Can be used to design greedy approaches (including e -based methods) and supports both structured and unstructured pruning. Depends on how higher-order derivatives of the loss are taken into account. B.g. using only the diagonal of the Hessian can be
relatively quick. but computing the full Hessian is infeasible for large networks. See Table 3 for experiments.
See Equation (16) in Appendix E for invariance in theory, and end of Appendix E for non-invariance in practice.
In light of (5), to limit the impact of pruning on the pertur- bation of the initial function Rg, it is natural to choose coordinate of 9 leading to a small value of this criterion.
To the best of our knowledge, this is the first practical net- work pruning method that is both invariant under rescaling symmetries and endowed with guarantees such as (11) on modern networks
Lemma 5.2. Path-Mag enjoys the following properties:
Table 3: Run-time (in milliseconds) to score all weights.
recaaing-invarrance:: for each 0 BC and index Path-Mag(0. Path-Mag(B, for every rescaling- equivalent parameters 0 0;
Time of a forward pass included for reference. Entries in "OBD" and "Forward" columns show times for batch-sizes and 128 (e.g.. "13-60 60" means 13 ms at batch size 1 vs. 60 ms batch size 128). See Appendix E for details.
error bound:
denote s == lG EiEr es where
indexes entries of RC be pruned. We have
Network
Forward
Mag
OBD
Path-Mag
[R) -Rooo(x)
AlexNet
1.7-133
0.5
13-60
14
Σ .ET
PathhMMg((f,11) i)) max(1, [[=)) (13)
VGG16
2.3-198
1.4
31-675
61
ResNer18
3.6-142
3.2
51-155
32
computation with only two forward passes: using Equation (11) and the fact that (1 is computable in one forward pass (Gonon et al., 2024a).
While Table shows that path malt-tmmgnnieee pruming is compu- tationally feasible, we must also verify that when injected in usual pruning pipelines, it yields acceptable accuracies.
efficient joint computation.for all entries: we have
5.4. Proof-of-concept study
(Path-Mag(Oo (0, i)); = (0)ll
(14)
As a simple proof-of-concept, we prune a dense ResNet- 18 trained on ImageNet-Ik.
that enables computation via auto-differentiation.
Setup. Dense ResNet-18 ImageNet- 1k, standard train- ing hyper-parameters, lottery-ticket schedule (Frankle et al., 2021). We benchmark three prun- ing criteria: (i) magnitude, (ii) magnitude after a random neuron- wise rescaling. (iii) our path-magnitudce See Ap- pendix for details.
The proof is given in Appendix C. We summarize these properties in Table 2.
fine-iinttue"
5.3. Considered (basic) path-magnitude pruning method
Equipped with Path-Mag. a basic rescaling-inven invariant prun- ing approach is minimize the upper-bound (13). This is achieved via simple reverse hard thresholding:
Results. Table reports top-1 accuracy after fine-tuning when pruning either 40, 60 80% of the weights. Path- magnitude matches magnitude pruning on the un-rescaled network and completely eliminates the 5-50% accuracy drop
1. Score all weights. The entire vector [Path-Mag(H,, i)); can be produced in one reverse-mode autograd pass via Eq (14).
*We performed no extra hyper-parameter tuning for path- magnitude; reused the lottery-ticket settings published for magnitude pruning Frankle et al. (2021).
2. Prune, our the weights with the smallest scores.
8

---

A Rescaling-Invarre Lipschitz Bound using Path-Metries
Table 4: Top-1 ImageNet accuracy (%) on ResNet-18 after one-shot pruning, rewind, and 85-epoch fine-tune. Original accuracy: 67.7%. Three pruning levels shown; more in Appendix D.
has developed techniques attempting globally minimize (a surrogate of) {(s 0) {()) over the (combinatorial) choice of support satisfying an e--constraint. Such ap- proaches have been scaled up to million of parameters in (Benbaki et al., 2023) by combining a handful of clever algo- rithmic designs, Similar iterative or greedy strategies could be explored to aim at solving the (seemingly) combinatorial e opottiiiiationn problem [ o 0) (00)1l1.
Pruning level
40%
60%
80%
Path-magnitude
68.6
67.9
66.0
Magnitude
68.8
68.2
66.5
Magnitude (rescaled)
63.1
57.5
15.8
6. Conclusion
incurred when magnitude is applied after rescaling. Figure 4 shows the full training trajectory at 40 % sparsity.
We introduced a new Lipschitz bound on the distance be- tween two neural network realizations, leveraging the path- lifting framework of Gonon et al. (2024a). By formulating this distance in terms of the -epath-mmtrri,, our result ap- plies to broad class of modern ReLU networks-including ones like ResNets or AlphaGo- and crucially overcomes the arbitrary pessimism arising in non-invariant parameter- based bounds. Beyond providing a theoretical guarantee, we also argued that this metric can be computed efficiently in practical scenarios such as pruning and quantization.
Runtime. Path Path-magnitude scores for all weights are com- puted in 32 ms (Table 3), comparable single forward pass (see Appendix E for details).
These results confirm that rescaling invariance is not just cosmetic: it prevents large accuracy losses under benign weight re-scalings while keeping the computational cost low. A broader comparison with structured and iterative methods such as CHITA is left for future work.
We then demonstrated how to apply path-lifting to pruning: the path-magnitude criterion defines descaling-invariane measure of the overall contribution of a weight. In proof- of-concept on a ResNet-18 trained on ImageNet, path- magnitude pruning yields an accuracy on par with standard magnitude pruning. This connects the theoretical notion of path-lifting to a practical goal: making pruning decisions that cannot be undermined by mere neuron- wise rescaling.
Pruning 40%
70
60-
55-
Tost topp
50-
This work raises several directions for future research. First, natural challenge is to establish sharper versions of our core result (Theorem 4.1). typically with metrics still based on the path-lifting but using (P-norms with p > 1, or by deriving functional bounds in expectation (over a given probability distribution of inputs).
45
Magnitude
35-
Magnitudee Rescale
Pach-Wapritude
60
Epoch
Second, more advanced iterative algorithms, akin to second- order pruning techniques, might benefit from path-lifting as a fundamental building block, improving upon the sim- ple one-pass approach used in our proof-offconcept while retaining invariance properties (see Section 5.5).
Figure 4: Top-1 accuracy during fine-tuning at 40 % sparsity. Path-magnitude overlaps exactly with itself after random neuron-wist wise rescaling, while magnitude pruning degrades.
5.5. Discussion and possible future extension
Finally, although our main theorem improves existing Lips- chitz bounds and extends them to a wide range of network architectures, the potential applications of the path-lifting perspective-and its invariance under rescaling are far from exhausted. Quantization and generalization, in particular, are two important areas where the present findings might stimulate further developments on metrics that offer both thcoretical grounding and compelling practical propertics.
The cost Path-Mag(81 i) is defined per weight, but its value for a given weight indexed by i also depends on the other weights. Therefore, one could hope to achieve better pruning properties if, once a weight is pruned, the path- magnitude costs of the remaining weights were updated. This is reminiscent of the loss loss-sensitivity cost (LeCun et al., 1989) that associates to each weight (a surrogate of) the difference E(0_.) - E(0), where f is a given loss function. The challenge is similar in both cases: how to account for global dependencies between the pruning costs associated to each individual weight? In this direction, whole literature
9

---

A Descaling-Invarian Lipschitz Bound using Path-Metrics
Acknowledgements
D., and Rus, D. Data-dependent coresets for compress- ing neural networks with applications to generalization bounds. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: / //openrevieww.o//mmm www.eeeeeooommmmdndddddaeieeeeee
This work was supported in part by the AssegroAssai ANR-19-CHIA-ON by the NuSCAP ANR-20-CEAN projects of the French Agence Nationale de la Recherche and by the SHARP ANR project LAN-23-PPIA--OE in the context of the France 2030 program.
Baykal, C., Liebenwein, L., Gilitschenski, I., Feldman, D., and Rus, D. Sensitivity-informeed provable pruning of neu- ral networks. SIAM Journal on Mathematics of Data Sci- ence, 4(1):26-45, 2022. doi: 10. 10.1137720M133822299 URL https: https::/ddi..o org/ 10. 1 22
The authors thank the Blaise Pascal Center for the compu- tational means. It uses the SIDUS solution (Quemener & Corvellec, 2013) developed by Emmanuel Quemener.
Impact Statement
Bekas, C., Kokiopoulou, E., and Saad, Y. An estimator for the diagonal of a matrix. Applied Numerical Mathematics, 57(11):1214-222) 2007. ISSN 0168-9274.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
doi:
URL https://wwwt httpps//www.sceeneeddreee.t science httpa////rrttaeeee///////1999990
References
Numerical Algorithms, Parallelism and Applications (2).
Andriushchenko, M., Croce, F., Müller, M., Hein, M., and Flammarion, N. A modern look at the relation- ship between sharpness and generalization. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu. Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 840-902. PMLR, mlr.press/
Benbaki, R., Chen, W., Meng. X., Hazimeh, H., Pono- mareva, N., Zhao, Z., and Mazumder, R. Fast as CHITA: neural network pruning with combinatorial optimization. Krause, A., Brunskill, E.,, Cho, K., Engelhardt, B., Sabato, S., and Scarlett, (eds.), International Confer- ence on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 2031-2049. PMLR. 2023. /tatttss:/procceeeeee 2202/benbaki23e html.
2023. URL htthtttps///prceeeeiee html.
ml mlr.. press/
v202 / andriushchenko22
Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. Stronger generalization bounds for deep nets via a compression approach. In Dy, J. G. and Krause, A. (eds.), Proceed- ings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssuun Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 254-263. PMLR, 2018. URL Auttp:/a pggs mar.press/ v80 a rooaa 8b. html.
Berner, J., Grohs, P., and Jentzen, A. Analysis of the gen- eralization error: Empirical risk minimization over deep artificial neural networks overcomes the curse of dimen- sionality in the numerical approximation of black-scholes partial differential equations. SIAM J. Math. Data Sci., 2(3):631 657, 2020. doi: 10.1137/19M1255499X URL https: //tp:://doi... /ooi wrgg10....... 1 9M1 2564
Bona-Pellissier, J., Malgouyres, F., and Bachoc, F. Local identifiability of deep relu neural networks: the theory. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D.. Cho, K., and Oh, A. (eds.), Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022,0222222 2022.
Barron, A. R. and Klusowski, M. Complexity, statistical risk, and metric entropy of deep nets using total path variation. CoRR, 1tt//9922.000000 2019. URL http: //arxiv. serxxiv.org/aae. /11//99022.0 00800.
Bartlett, P. L., Foster, D. J., and Telgarsky, M. Spectrally- normalized margin bounds for neural networks. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6240-6249, 2017.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 3rd Edi- tion. MIT Press, 2009. ISBN 978-0-262-03384 8. URL http::/mitprest mit. www.tiiu.ttmttie.emme edu/books/ ineroductionnaalgritme
De Vore, R. A., Hanin, B., and Petrova, G. Neural network approximation. Acta Numer,, 30:327-444, 2021. doi:
Baykal, C. Liebenwein, L., Gilitschenski, I., Feldman,
10

---

A Rescaling-Invarian Lipschitz Bound using Path-Metries
10. 10.0017/0002249992000005 URL https: //oi.. org/10. 0tt.:/1111//09924229299999
quantization and huffman coding. In Bengio, Y. and Le- Cun, Y. (eds.), 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http: / /tte//axxiin aaaaaiivvvoooo org/ abs /150 001 49.
Frankle, J., Schwab, D. J., and Morcos, A. S. The early phase of neural network training. In 8th International Conference on Learning Representations, ICLR 2020, Ad- dis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net 2020. URL https: httpp/pppeeeeee.eeeeeeeeee http://wwwweee/ooooreoeee [d=Hk11iRNFws
Hanson, S. J. and Pratt, L. Y. Comparing biases for min- imal network construction with back-pree propppaapaaaionn In Touretzky, D. S. (ed.), Advances in Neural Information Processing Systems I, [NIPS Conference, Denver, Col- orado, USA, 1988), pp. 177-185, Morgan Kaufmann, 1988.
Frankle, J., Dziugaite, G. K., Roy, D. M., and Carbin, M. Pruning neural networks at initialization: Why missing the mark? In 9th International Con- ference on Learning Representations, ICLR 2021, Vir- tual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https:t/////////t http://ppeeeeeee..eeeee. forum? id-Ig- Vao---yQCK-K-K-
Hassibi, B. and Stork, D. G. Second order derivatives for network pruning: Optimal brain surgeon. In Hanson, S. J., Cowan, D., and Giles, C. L. (eds.). Advances in Neural Information Processing Systems 5, INIPS Conference, Denver, Colorado, USA, November 30 December 3, 1992], pp. 164-171. Morgan Kaufmaan,, 1992.
Gonon, A. Harnessing symmetries for modern deep learn- ing challenges a path-lifting perspective. Theses, Ecole normale supérieure de lyon - ENS LYON, Novem- ber 2024. URL https: http:::////ssssss/ hal. science/ te1-04784426.
He, K., Zhang, X., Ren, S., and Sun, J. Deep resid- ual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recogni- tion, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770-778. IEEE Computer Society, 2016. doi: 10.1109/CVPR..211.9900 URL https://dol org/ 20.1109/CVPR..200 90.
Gonon, A., Brisebarre, N., Gribonval, R., and Riccietti, E. Approximation speed of quantized versus unquan- tized relu neural networks and beyond. IEEE Trans. Inf. Theory, 69(6)3360-3377 2023. doi: 10.1109/TTT.023.. 1109/TIT.
3240360. URL https: 2023. 3240360.
Kawaguchi, K., Kaelbling, L. P., and Bengio, Y. General- ization in deep learning. CoRR, abs/1710.05468 2017. URL http: a/aaaxxivv www.iiivrrrre..o wtt.v//rrggbbbbb/a/o/o/oo/ss 1710. 05468.
Gonon, A., Brisebarre, N., Riccietti, E., and Gribonval, R. A path-norm toolkit for modern networks: con- sequences, promises and challenges. In International Conference on Learning Representations, ICLR 2024 Spotlight, Vienna, Austria, May 7-11. OpenReview.net, / ?
Kwon, J., Kim, J., Park, H., and Choi, K. ASAM: adaptive sharpness-aware aware minimization for ccale-invariant learn- ing of deep neural networks. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Con- ference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Ma- chine Learning Research, pp. 5905-5914. PMLR, 2021. URL http:://proceeding/ mlr www.s//ssss3 kwon21b. html.
2024a. URL https://openrest id=hiH2VUIYiA
Gonon, A., Brisebarre, N., Riccietti, E., and Gribonval, R. Code for reproducible research A path-norm toolkit for modern networks: consequences, promises and challenges, March 2024b. URL https: //hal. scie seiiencehhal-aee 044495997 It is the code tagged with v1.0.0 at https:://// httpp::///gttttt com/ agonon/ pathno rm tomkoookit, and any updates will be avail- able directly on that git repository.
LeCun, Y., Denker, J. S., and Solla, S. A. Opti- mal brain damage. In Touretzky, D. S. (ed.), Ad- vances in Neural Information Processing Systems 2, [NIPS Conference, Denver, Colorado, USA, Novem- ber 27-30, 1989], pp. 598-605. Morgan Kaufmann, 1989. URL http: http::/paperss http://apprr..e/// .nceersniniii mips.cc cc/paper/ 250 aptimal-bbaaii damage.
Gonon, A., Brisebarre, N., Riccietti, E., and Gribon- val, R. Code for reproducible research A rescaling- invariant Lipschitz bound using path-metrics, May 2025. Deposited on HAL and Software Heritage. Updates will be available directly at httpp::///// /tts:///gthhss com/ agonon/pathnoi wwt.://aaahttoatpoeao wtw.rahooooooooooottoooooooo
Liebenwein, L., Baykal, C., Lang, H., Feldman, D., and Rus, D. Provable filter pruning for efficient neural net- works. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: / //opnrevvii ew net forum? d=BJxkO1 SYDH.
Han, S., Mao, H., and Dally, W. J. Deep compression: Compressing deep neural network with pruning, trained

---

A Rescallig-Invvaiing Lipschitz Bound using Path-Metrics
Lybrand, E. and Saab, R. A greedy algorithm for quan- tizing neural networks. J. Mach. Learn. Res., 22:156:1- 156:38, 2021. URL https:/ jmlr. patrg//aarr/////e v22/20-122 html.
Approx., 57(2):853-899 2023. ISSN 0176-4276,1432
0940. doi: 10.1007400065-00-09558.. URL https: //doi. .0t/:/11.110000 1007/ 022 1222-00 025778-9-111
Tsuzuku, Y., Sato, I., and Sugiyama, M. Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using pac-bayesian analy- sis. In Proceedings of the 37th International Confer- ence on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Ma- chine Learning Research, pp. 9636-9647. PMLR, 2020. URL htttttttp/pppceeeee http::///coccceeesss///o mwr. mmr.ppres/vv19/ tsuzuku20a. html.
Marcotte, S., Gribonval, R., and Peyré, G. Abide by the law and follow the flow: Conservation laws for gradient flows. CoRR, abs/2307 00044, 2023. doi: 10.48550arxivv 2307.00144. URL https: /oi. org/10...... 10 48550/ arXiv. 2307 00144.
Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. In Grünwald, P., Hazan, E., and Kale, S. (eds.), Proceedings 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. Jorg. 2015, URL http: /ttpp/peeoooeeeeeeeeeeeeeeee mlr. press/ v40 w=0/NNyshaabrr5..6
Wen, K., Ma. T., and Li, Z. How sharpness-aware minimization minimizes sharpness? In Interna- tional Conference on Learning Representations (ICLR), 2023. URL https: /ttp::///pppeeeeeeeeee net/forunt: i id=5spDgwmpXXx
Yu, X., Serra, T., Ramalingam, S., and Zhe, S. The combi- natorial brain surgeon: Pruning weights that cancel one another neural networks. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), International Conference Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, vol- ume 162 of Proceedings of Machine Learning Research, pp. 25668-25683 PMLR, 2022. URL https: // proceedings mlr wwtpss/els//sy222//222 html.
Neyshabur, B., Bhojanapalli, S., and Srebro, N. A PAC-Bayesian approach to spectrally-norrmaizee margin bounds for neural networks. In 6th International Con- ference on Learning Representations, ICLR 2018, Van- couver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.net, 2018. Utthttps: WFbC2.
Quemener, E. and Corvellec, M. Sidus-the solution for extreme deduplication of an operating system. Linux Journal, 2013.
Zhang. J., Zhou, Y., and Saab, R. Post-training quantization for neural networks with provable guarantees. SIAM J. Math. Data Sci., 5(2):373-399, 2023. doi: 10.1137/ 22M1511709. URL https::/// http:///.o.o//.113/////////////1
Rangamani, A., Nguyen, N. H., Kumar, A., Phan, D. T., Chin, S. P., and Tran, T. D. A scale invariant measure of flatness for deep network minima. In IEEE Inter- national Conference on Acoustics, Speech and Signal Processing, ICASSP 2021, Toronto, ON, Canada, June 6- 11, 2021, pp. 1680-1684. IEEE, 2021. doi: 10.1 109/ ICASSP39728. 2218 STAASPP39728.202199413777 URL https: //ts::///d//// doi.. htte/10.1109/CCASSPP3
22m1 511709.
9411.711377..
Schnoor, E., Behboodi, A., and Rauhut, H. Generalization сгтor bounds for iterative recovery algorithms unfolded as neural networks. CORR, 12.04344, 2021. URL https: http://axxvvv.roo
htt.ps:/aaxxiv.ooo hwtg//b////// 211/2.11.. 04364.
Singh, S. P. and Alistarh, D. Woodfisher: Efficient second- order approximation for neural network compression. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Informa- tion Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Stock, P. and Gribonval, R. An embedding of ReLU net- works and an analysis of their identifiability. Constr:
12

---

A Eascaling-Invariin Lipschitz Bound using Path-Metric
Appendices
A. Path-lifting, activations, and a fixed incidence matrix
We recall the construction of Gonon et al. (2024a), but instead of considering the path-activation matrix A(0, x) as in Gonon et al. (2024a), we introduce two new objects A and a(0, x)) that lead to mathematically equivalent formulas but to a lighter proof of Theorem 4.1:
the path-activation vector a(0, x), and
a fixed incidence matrix that depends only on the DAG architecture, never on 0 or x.
A.1. Network architecture
Definition A.1 (ReLU and k-max-pooling activation functions). The ReLU function is defined as ReLU(z)= = x1230 for R. The k-max-pooling function k=pool(x) :- =(k) returns the k-th largest coordinate of x E Rd
Definition A.2 (DAG-ReLU neural network (Gonon al., 2024a)). Consider Directed Acyclic Graph (DAG) G (N, E) with edges E, and vertices N called neurons. For neuron v, the sets ant(v), suc(v) of antecedents and successors of v are ant(v) : {u E NN u + E suc(v) == {u E N, - u E E}. Neurons with no antecedents (resp. no successors) are called input (resp. output) neurons, and their set is denoted Ni (resp. Nou).. Neurons in N \ (Ni U Now) are called hidden neurons. Input and output dimensions are respectively dm := [N and dour := |ooul
A ReLU neural network architecture is a tuple (G, (po)oENN, composed of DAG G = (N,E) with attributes Pe E fid, RcLU) U [k-pool, & E Nso} for v E N \ (No U (Ni)) and P. = id for Nour- We will again denote the tplle (G, (po)veN N. by G, and it will be clear from context whether the results depend only G (N, E) or also on its attributes. Define N₂ == (v E N, Ps= p} for an activation p. and No == UREN Noop A neuron in N. pool is called a e-max-pooling neuron. For u E Ne-pooo, its kernel size is defined as being ant(r))]
Parameters associated with this architecture are vectors 9 E R := BUNN,, NNs We call bias b, == 6, the coordinate associated with a neuron v (input neurons have no bias), and denote fu-+v the weight associated with an edge u - v E. We will often denote 0~+ = (0*=+")
)u)ant(e) and 0- (0a-+)) uEsue(u))
(Qu+t))uEsu((v))
The realization of neural network with parameters 0 RC is the function Rg R. - R2 (simply denoted Rg when G is clear from the context) defined for every input R.N, as
Ro (z) = (v x) )eNN..
where we use the same symbol v to denote a neuron v E N and the associated function v(0,z), defined as v(0, 2t) = I. for an input neuron v, and defined by induction otherwise
v(0,z)) :
(b + Eueantt(o u(0, x)0 k-pool ((b, + u(0, z)0-))) (ucantt)))))
if = ReLU or p. = =i, if p. k-pool.
A.2. Paths and the path-lifting
Definition A.3 (Paths and depth in DAG (Gonon et al., 2024a)). Consider DAG G (N, E) as in Definition A.2. A path of G is any sequence of neurons uo...., ea such that each o; Us41 is an edge in G. Such path is denoted N, denoted p v. The length of path is length(p) d
p == to + ... va. This includes paths reduced to a single (the number of edges). We will denote pe == the f-th neuron for general & E (O....,Iengttte length(p)) and use the shorthand Pend = Vlengeh(p) for the last neuron. The depth of the graph G is the maximum length over all of its paths. If Ud41 E sTc((eea)) then pan - Ud+1 denotes the path to .... + Vs + Ud+1-
We denote by pe (or simply P) the set of
paths ending at an output neuron of G.
Definition A.4 (Sub-graph ending at given neuron). Given a neuron v of a DAG G, we denote - the graph deduced from G by keeping only the largest subgraph with the same inputs G and with e as single output: every neuron u with no path to reach through the edges of G is removed, well as all its incoming and outcoming edges. We will use the shorthand p-+ : po- to denote the set of paths in G ending at v.
FFor an index set J, denote T = ((0:)ieI, 0; R).
13

---

A Rescaling-Invarian Lipschitz Bound using Path-Metries
Definition A.S (Path-lifting (0)).. Consider DAG-ReLU neural network G as in Definition A.2 and parameters 0 E IRG associated with G. For porpe E P, define
length(p)
II
04-11
Po Ni::
(0)
length(p)
Opo
8- 1-
otherwise,
where an empty product equal to by convention. The path-lifting & (0) 0
(0) = (p)))))
This is often denoted & when the graph clear from the context. We will use the shorthand -- -2 path-lifting associated with G-v (Definition A.4).
to denote the
A.3. Path-activation vector and fixed incidence matrix
Definition A.6 (Activation edges, neurons, and paths), Given 8 x, the activation an edge u - 0 is (0,+0(0,2) ) := 1 is identity, =)) if is ReL.U, and for k-max-poo -oool is only for the (lexicographically) first antecedent achieving the k-th maximum. For neuron set (0, x) 1 if is input, identity, max-pool, and ==(0 if is ReLU, For path p to Da define
(0,)) :- ano (0,
II the (0,x) E 10.
The path-activation vector is a(0, = (ap(0, x)) {0,1)".
Definition A.7 (Fixed incidence matrix A). Consider new symbol Ubias that is not used to denote neurons. Instead of considering as in (Gonon et al., 2024a) the path-activations matrix A(8, x) E R (M.((ul((saa))) whose coordinates are indexed by paths P and neurons u E Nin U (Weies and are given by
if E Nin: ap (0,z)) xr11 Po otherwise when u = thiaa-
ap(0, ((0,,)11p==
(A(0, x)) :
we define fixed incidence matrix A, which corresponds to the all-activated case the definition of A(0, above, and which maps input neurons the path they belong to:
if E Nin and po u,
Apa if Usias and Po & Ni. otherwise,
so A P0.()Px() depends only on the graph.
A.4. Key inner-product identity
With our new notations, Equation (4) (corresponding Theorem A.1 in (Gonon al., 2024a)) can be rewritten as:
Ra(x) (()) o ((,
x
(4)
weights
fixed incidence
B. Proof of Theorem 4.1
In this section, we prove slightly stronger version of Theorem 4.1. We do not state this stronger version in the main body as it requires having in mind the definition of the path-lifting 4b recalled in Definition A.5, to understand the following notations. For parameters we will denote 4' (#) (resp. & (()))) the sub-vector of (()) corresponding to the coordinates associated with paths starting from an input (resp. hidden) neuron. Thus, (0)) is the concatenation of t (f) and क (0).
14

---

A Rescaling-Invanee Invariant Lipschitz Bound using Beth-Metries
6
U/
2/1
U3
W2
bus
fh 744
W
Nin
Ubias
P1 p
0
0
0
0
A
Pn p'
Figure 5: The coordinate of the path-lifting associated with the path p 01 + + 03 is ( f pon-+ 002
since it starts from an input neuron (Definition A.5). While the path p' wi - W2 + wa starts from a hidden neuron (in N (Nn U Now)), so there is also the bias of wi take into account: Φpr (0) bw,, 8mm -202 g -ws, As specified in Definition A.6, the columns of the incidence matrix A are indexed by N [Mbiss and its P Pi U Pa. with Py the set of paths in P starting from input neuron, and Py the set of paths starting from hidden neuron.
indexed by
15

---

A Eascaling-Invariinn Lipschitz Bound using Path-Metries
Theorem B.1. Consider ReLU neural network as in Definition A.2, with oulput dimension equal to one. Consider
associated parameters 0, 0' for every coordinate i, Og and f have the same signs at least one of them is zero (0,0; > 0}, we have for every input x:
Ro(x) Ro (x)] & +0)0))
+ (0')ll
(15)
Moreover, for every neural network architecture, there are non-negative parumeters 0 o O' and a non-negative input æ such that Inequality (5) is an equality.
Theorem B.1 1 is intentionally stated with scalar output to avoid imposing a specific norm on the outputs; readers can naturally extend it to the vector-valued setting using the norm most relevant to their application. As an example, we derive the next corollary for fo-norms on the outputs, which corresponds to the Theorem 4. given in the text body (except for the equality case, which is also an easy consequence of the equality case of Inequality (15)).
Corollary B.2. Consider an exponent E [1, 0o) and a ReLU neural network as in Definition A.2. Consider associated parameters 0, for every coordinate i, holds 0,0, > then every input x Rdw;
[R(()) -Ra (x)]ll < max([]=]]oo) 1)] (0')ll.
Proof of Corollary B.2. By definition of the model, holds:
(x) Ro (x)11
Σ
10(0,z) v(0',x)11
N
Recall that क- is the path-lifting associated with the sub-graph G (Definition A.5). By Theorem B.1, it holds:
[v(0,x) v00',z)11 < max([1=18, -0 (0) 10**((0)1
Since (0)) = - (0)+) Now this implies:
[R((x>) Ro (x) < max([1>:11. (()) (0))
Figure 6: Counter-example showing that the conclusion of Theorem 4.1 does not hold when the parameters have opposite
signs. If the hidden neurons ReLU neurons, the left network implements Rg (x) ReLU(x)) (with @ (1 1)7) and the right network implements Rgr(2) is single path and the product of the weights along this path is equal to one in both cases, so that (()) (00) 1 (cf
ReLU(-z) (with f' (-1 ))"). Inequality (5) does not hold since there
Section 3) while these two functions are nonzero and have disjoint supports.
Proof of Theorem B.I. A geometric illustration of the spirit of the proof is given in Figure 3, as detailed in the figure caption.
Step 1 Reduction to non-zero coordinates. Since both sides of (15) are continuous in (0, (0,8"), without loss of generality it enough to prove it for weight vectors 0, 0' with zero entries.
Step 2 - Proof for parameters leading to the same activations a00, aa0', .). If the two parameters activate exactly the same paths on then (4') yields
x 1
[R(()) Ro (x)) = ( (0) - ((8') O (a()x)), A
< [[((()) a(0)))
llae.
1
11 || |11. Moreover, a(0,z) x:) is a binary vector so (0) - ((') @ a(f,x))l x)ll < (((()) (()')l This gives the bound of Theorem 4.1 in the simple case where
Because A is binary with at most one "1" per row, A
a(0, x) = a(0',z)) .)::
Ro(x)) Ro (x)) < max([ (0) <00')ll1
16

---

A Rescaling-Invariin Lipschitz Bound using Path-Metries
To prove the slightly stronger bound appearing in Theorem B.I, first split the paths depending on whether they start an input neuron or hidden neuron:
(+)) < (()
[( x (0')) 3 @a(0.))) A
*x)|+((((0(00) a (00)) Oa (0,2), A
and then apply the same argument on each part to get:
[R(r)) - (x)) < || - + +0 (0'0'))
Step 3 bound for a trajectory with finitely many break-points. Let + ((t) be any continuous eurve from
0 0' such that the activation vector a(((t),x) x) is constant on finitely many intervals (tx, tx+1) with ts < tx+1 and [0, = =k tx+1]. Applying Step 2 every interval and summing gives
[R) - (x)) < | Σ (0((00()))) - "a'd--p''0000 (0(4x)) + Σ (0(E+)()) - (0(((((()) (0(4)))
(A.2)
Step 4 Construction monotone path in log-space. For each coordinate index of the vector define
(t) (0, 10,1--* |09|",
t E [0, 1].
(A.3)
This trajectory (t) is well-defined since by Step we assumed without loss of generality that the coordinates of 0 and O' are non-zero. Moreover, since sgn(0) sgn( this trajectory goes from O' and we use (A.2) provided that this path has only finitely many break- break-points.
For every path the scalar function t + (b(tt) yields sums that telescope exactly:
is monotone, so developing the -norms in (A.2)
= 11 (0) 50 (0')l, and similarly for Th Σ -(00)
Thus Theorem B. follows from (A.2) provided the path has only finitely many break-points.
Step 5 3- Proving the existence of finitely many break-points (technical). Each coordinate in (A.3) is an analytic function of t, and the activation ReLU or max max-pool neuron evaluated on an analytic input can only change at isolated roots. On the compact interval [0, 1] there can be only finitely many such roots. Lemma B.3 formalizes this argument and completes the proof of (15).
To prove Theorem B. it remains to prove the claim about the equality case: must find 0 * 0' and input such that the inequality is actually an equality.
Sharpness of the bound (equality cases) in Theorem B.1 Consider an input neuron un and a path vo + + + vd. Define two parameter vectors that differ only on that path:
0 Our = a O,
0' Ce = 6 0, 8= 0=.,...,c 1,
and set every other coordinate of 0, 0' to O.
Choose the input æ with Trg > 0 and all other coordinates equal to O. Because the signal propagates solely along p.
Ro(x) a² Tnor
Ro (x) 18a xmo-
For the path-lifting only the coordinate @p changes, hence | (0) s' (0)'ll lad - -0%,
| - "0((0))1 0.
Since || Tog. inequality (15) is an equality:
la - 6d| Zeo = ||~|| || (0) 1000-41100 (0)'l1 + (1) 3 (0')l0)
Thus the bound of Theorem B.1 cannot be improved in general.
Formally, apply Step 2 pair 0(t), ((t),, with e' in the open interval (fs, fx+1); let th and t' tat1, and conclude by continuity of both sides.
17

---

A Descaling-Invariin Lipschitz Bound using Path-Metrice
Lemma B.3. Fix E imputs 21,....; Uy E BR and two parameter vectors 0, O' with zero coordinates. Let O(1) be the geometric trajectory (A.3). There are finitely many points 0 to l1 .... < lm 1 such that for every input 3a the path-activation vector a a00(t), (z)) is constant on each open interval (x+).
Proof of Lemma B.3. Step 1- reduce to single input. If finite breakpoint set works for each x; individually, their union works for all inputs. We therefore fix one arbitrary input z.
Step 2 property to prove for each neuron. For a neuron u define
there exist finitely many breakpoints - to t1 < <.... tm
such that
t + u (0(t), is analytic on every [tz, tx+1l: (0(1).)) (a())(((1),,))
P(o):
ト a. (0(1), and & ++ au-so constant (tg, tx+1)-
Vu E ant(v)
If Pw) holds for every neuron v, the union of their breakpoints gives finitely many intervals on which all edge and path activations are frozen, completing the lemma.
Step 3 prove P(v) by topological induction.
We perform induction on topological sorting (Cormen et al., 2009, Section 22.4) of the underlying DAG. We start with input neurons since by Definition A.2, these are the ones without antecedents so they are the first to appear in a topological sorting.
Initialization: Input neurons. v00,x)) = Ty does not depend on 0, hence (.,x) 1; Pvv) holds with m 1.
Induction: Now consider a neuron é Nm and assume P(u) hold for every neuron coming before in the topoligical sorting. There are finitely many breakpoints 0 < t < < I'm = 1 such that for every E ant and every k the map E [4x, (e]] + ((((t), x)) is analytic. We distinguish three cases depending the activation function of the neuron v.
(i) Identity neuron. vf(t), x) = by + +E u(((t), x (t)+o(t) is analytic on the same intervals [fx, tx+1 because each factor is analytic; 02 = 1. Thus P(v) inherits the finite breakpoint set of its antecedents.
(ii) ReLU neuron. The pre-activation (t) := by + Evgant(u) u(O(t), .0)...0 (t) is analytic on each [tx, te+1] by induction. Either pre, is identically zero, which case au = 0, or its zero set is finite (as an analytic function on a compact domain), so the sign of pre,, (and therefore ag and each a is constant between consecutive zeros. Hence P(v) holds.
(iii) K- X--mxxppoo neuron. The output of is the K-th largest component of pre, == (u(0(t), x =)) ue) Each coordinate of pre, is analytic on each [4x, 4++1] by induction. Two coordinates can swap order only at isolated t where their analytic difference becomes zero, so the ranking-ant and thus the selected K-th dalue-changes only finitely many times. Thus ((r) holds.
By topological induction P(v) true for every neuron. The argument in Step then gives the desired global breakpoint set.
C. Proof of Lemma 5.2
Descaling-invariane is a direct consequence of the known properties of the path-lifting & (Gonon et al., 2024a).
In the case a singleton / = {i}, as already evoked, (13) simply follows from (5) and the definition of Path-Mag When [ > 2, consider any enumeration iz. 1 < j < [7] of elements in I, and 8j := 1 Σ ei = lG -1 -1 (tc) (as well as Sg := 1g): since the pair (0, ④ f) -as well as the pairs (s)-1 & 0, 8g @ 0)- satisfies the assumptions of Lemma 4.2, and
18

---

A Rescaling-Invanee Invariant Lipschitz Bound using Path-Mette Weth-Metries
88-1 5j have
[0(0)
((s +
0)1
[0)(0)
[| @ 0)]]
11
[ o 0)1l - [3 e @0
[| 00) {s, о (s 2 8))l
Path-Mag(sj-1000.
Path-Mag (0)
Finally, to establish (14), observe that for each path p we have (0) = I1,ep 10 so, for each i E (NB: can index either an edge in the path or the first neuron of p when starts from a hidden or output neuron, in which case 6g is the associated bias) holds
L (0) sgn
II 10).
a0,
jEP.j$$
Because sgn(0,)0, |0,| we get that, when i p.
8
0,
c (0) (0)(
00:
Summing over all paths for a given index i shows that
(0 voll(())l1 = 0,
(0)
00:
PEP
i
A
Σ
(p))
00,
PEPRiEP
Σ pEPsiP
Path-Mag(0,.)) (0,1). i).
(12)
D. Proof-of-concept: accuracy of path-magnitude pruning
To provide a proof-of-concept the utility the main Lipschitz bound Theorem 4.1 for pruning, we implement following "prune and finetune" procedure:
1. train: we train a dense network,
2. rescale (optional): apply random rescale the trained weights (this includes biases),
3. prune: we prune the resulting network,
4. rewind: we rewind the weights their value after few initial epochs (standard in the lottery ticket literature
enhance performance (Frankle et al., 2020)),
5. finetune:
we retrain the pruned network, with the pruned weights frozen to zero and the other ones initialized from their rewinded values.
19

---

A Rescaling-Invarian Lipschitz Bound using Path-Metrics
Doing that to prune p 40% of the weights once of ResNet18 trained ImageNer-1k, observe that (Figure 4):
without random rescale (plain lines), the test accuracy obtained at the end is similar for both magnitude pruning and path-magnitude pruning;
with random rescale (dotted lines the one associated with path- magnitude pruning is invisible as it coincides with the corresponding plain line), magnitude pruning suffers a large drop of top-1 test accuracy, which is not the case of path-magnitude pruning since it makes the process invariant to potential rescaling.
We observe similar results when pruning between p 10% and p 80% of the weights at once, see Table 5.
Table 5: Extended version of Table 4. Top-1 accuracy after pruning, optional rescale, rewind and retrain, function of the pruning level. (+) results valid with well as without rescaling, path-magnitude pruning is invariant to rescaling.
Pruning level
none
10%
20%
40%
60%
80%
Path- Mothh-Mag (*)
68.6
68.8
68.6
67.9
66.0
Magnitude w/o Random Rescale
67.7%
69.0
69.0
68.8
68.2
66.5
Magnitude w/ Random Rescale
68.8
68.7
63.1
57.5
15.8
We now give details each stage of the procedure.
1. Train. We train dense 8 (He et al.. 2016) on ImageNet- using 99% of the 1,281,167 images of the training set for training, the other 1% for validation. We use SGD for 90 epochs, learning rate 0.1, weight-decay 0.0001, batch size 1024, classical ImageNet data normalization, and a multi-step scheduler 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. Doing 90 epochs took us about 18 hours on a single A100-40GB GPU.
2. Random rescaling. Consider pair of consecutive convolutional layers in the same basic block of the ResNet18 architec- ture, for instance the ones of the first basic block: model layer1 [0] convv and model. layer1 [ Py PoTrch, with model being the ResNet18. Denote by C' the number of output channels of the first convolutional layer, which is also the number of input channels of the second one. For each channel c E CI]. we choose uniformly at random a rescaling factor À E {1, 128, 4096} and multiply the output channel c of the first convolutional layer by A, and divide the input channel of the second convolutional layer by X. In order to preserve the input-output relationship, we also multiply by the running mean and the bias of the batch normalization layer that is in between (model lllyerlllll [0] .bnl in the previous example). Here is an illustrative Python code (that should be applied to the correct layer weights described above):
conv2 in
factors = np. array ( [1, 128, 4096))
out out_chhnnelsl, _f - weigats_convl shape
for out in range (out_channeesll) factor = np. random. choice (occeffaccto (factors)
weights_conve [out, i, :, *= factor
weights_conte [;, out, :, /= factor
running_meat mean [out] factor
10
bias [out] == factor
3. Pruning. At the end of the training phase, we globally prune (i.e. zero) p% of the remaining weights in all the convolutional layers plus the final fully connected layer.
4. Rewinding. We 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. This exactly corresponds to the hyperparameters and pruning algorithm of the lottery ticket literature (Frankle et al., 2021).
5. Finetune, This done the same conditions as the training phase.
20

---

A Rescaling-Invariian Lipschitz Bound using Path-Metrics
E. Computational cost: comparing pruning criteria
This section details how the results of Table were obtained.
E.1. Hardware and software
All experiments were performed on an NVIDIA A100-PCIE-40GB GPU, with CPU Intel(R) Xeon(R) Silver 4215R CPU 3.20GHz. We used PyTorch (version 2.2, with CUDA 12.1 and CuDNN 8.9 enabled) to implement model loading, inference, and custom pruning-coss computation. All timings were taken using the torch. utils benchmark module, synchronizing the GPU ensure accurate measurement of wall-clock time.
E.2. Benchmarked code
Single-forward pass. We fed a tensor torch. randn 3, 224, 224) to each model (batch size B or B 128, 224 x 224 RGB image).
Path-magnitude scores. We followed the recipe given in (14): (Path-Mag(O,0)). l Va (O)]l To do that, we computed the path-norm | using the function get-path.norm. pathnorm_tove kit (Gonon et al., 2024b). And we simply added one line to auto-differentiate the computations and multiply the result pointwise with the parameters 0. Thus, our code (see (Gonon et al., 2025) and github. com/ cwm/agonon..toooceoooooooooooooe agonon/ hwwphoooonoooooooooo for updates) has the following structure:
released online at github com/ /agnoon
it starts by replacing max- max-pooling neurons by summation neurons, or equivalently max- max-pooling layers by convolutional layers (following the recipe given in (Gonon et al., 2024a) to compute correctly the path-norm),
it replaces each weight by its absolute value,
it does a forward pass to compute the path-norm,
here we added auto-differenniiatio (backwarding the path-norm computations), and pointwise multiplication with original weights,
and it finally reverts to the original maxpool layers and the weights' value to restore the original network.
Table 3 reports the time to do all this.
Magnitude scores. It takes as input torch model, and does simple loop over all model's parameters:
to check these are the parameters torch nn Linear or torch. nn. Conv2d module,
if this is the case, it adds to a list the absolute values of these weights.
Loss-sensitivity scores (LeCun et al., 1989). In the Optimal Brain Damage (OBD) framework introduced in (LeCun et al., 1989), each weight 0g in the network assigned a score approximating the expected increase in loss if 0; were pruned (set to zero). The score of 0g is defined by:
1
OBD(#, i) h.:??.
where h; is the diagonal entry of the Hessian matrix = - of the empirical loss
(()) Σ {(Ro(xx)
with respect to the parameters 0. As we could not locate a proof of the rescaling-invariance of OBD we give below short proof, before discussing its numerical computation.
Rescaling
Descallng-imvarianne invariance. Denote D = diag(Ax) a diagonal rescaling matrix such that for each 0 the parameters := De are rescaling-equivall 0. This implies that Ro(xx) RDo(ok) for each training sample ag and every 0, hence
21

---

A Rescaling- Lipschitz Bound using Path-Metries
(()) ((D)) for every 0. Simple calculus then yields equality of the Jacobians dE(0) De(DO) i.e., since D is symmetric, taking the transpose
V((0)= DVI(DO),
vO,
that is to say V((-)= = (.). Differentiating once more yields
- - -DIV(())100) -DVV)())()))))) DDH(D)DD,
Extracting the i-th diagonal entry yields h,;(0) - , (DO) (and more generally hi -
hence
1 hu (DO) ブタ (1o 2 h0)0 -BBD(0, i).
OBD(DO, 0) 2 ha:(
(16)
Computation. Computing the full Hessian matrix H exactly would be prohibitive for large networks. Instead, well-known variant of Hutchinson's s trick (Bekas et al., 2007) is that its diagonal can be computed as
diag( H)) = E., (F)) o
where the expectation is over Rademacher vectors (i.i.d uniform 24 E (-1,1]) and where : denotes pointwise multiplication. In practice, we approximate it as follows:
draw a single vector as above.
compute the Hessian-vector product Hu using the "teverse-over-oorwandd" higher-order autodiff in PyTorch's farch.fune API,
deduce the estimate diag H (Hv) O u.
finally estimate OBD fu 2 0
(Hv) 000000
The performance do all this depends on the size of the batch on which is computed the loss, as the cost of the Hessian- vector product Hu depends on it. Table reports the milliseconds required for this entire procedure on batch sizes of 1 and 128, listing corresponding values as x y-
This approximation is not rescaling-invariant in general. Indeed, we have
((Hv) ( @v0000) (Hv): 00
Σ hir(0)oz
0,0
Σ
v183 =
Σ Exyhs(D0)o))
(16)
which would be the same as the estimate made for DØ if and only if were equal to
Σ (Dg(D)) 22200P.
There is no reason for this to happen (and it did not happen in any of our experiments). For instance, take v; = 8; = for every i, we would need E, (DO) = > E3 (D0),, which same as saying that À is an eigenvector of HDD)) with eigenvalue
F. Lipschitz property of Φ: proof of Lemma 4.3
We first establish Lipschitz properties of 0 + (0)). Combined with the main result of this paper, Theorem 4.1, or with Corollary B.2, they establish a Lipschitz property of - R₂(z) for each x, and of the functional map 0 + Rg(-) in the uniform norm on any bounded domain. This is complementary to the Lipschitz property of x + Ra(x) studied elsewhere in the literature, see e.g. (Gonon et al., 2024a).
22

---

A RescalingIInvarian Invariant Lipschitz Bound using Path-Metric
Lemma F.I. Consider q [1, (o), parameters 0 and O', and neuron v. Then, it holds:
( Φ (0))
length(p)
length(p)
(1h.- 1p 110 (0')
(17)
Σ
II
100 PK 11
max pEP-s
max uEant((p)
k=
with the convention that an empty sum and product are respectively equal to zero and one.
Note that when all the paths in p have the same length L, Inequality (17) is homogeneous: multiplying both 0 and O' coordinate-wise by scalar À scales both sides of the equations by X
Proof. The proof of Inequality (17) goes by induction on a topological sorting of the graph. The first neurons of the sorting are the neurons without antecedents, i.e., the imput neurons by definition. Consider input neuron v. There is only single path ending at e: the path p v. By Definition A.5, $ (-)- = (-) 1 so the left hand-side is zero. On the right-hand side, there is only a single choice for a path ending at e: this is the path p = v that starts and ends at v. Thus D = 0, and the maximum is zero (empty sum). This proves Inequality (17) for input neurons.
Consider a neuron É Ni and assume that this is true for every neuron before v in the considered topological sorting. Recall that, by definition, h- is the path-lifting of G (see Definition A.5). The paths in G are p v, and the paths going through antecedents of (u has antecedents since it is not an input neuron). So we have + Φ-) (o-t x (u-t") /ueant(r) ).
where we again recall that + (-) 1 for input neurons and b, = 0 for *-max- *-max-pooling
by
neurons. Thus, we have:
Φ (0) $ (0'))
=bb,- 11,10
Σ
$ (0) -u - - (8)) x 10)
vEant(v)
< 1bg 1
Σ
(1) (0) - + 300) (0)) 00 + | (0')11'0) -(0))-0)0)
(E (1)
< <b6 6,11 + |10
max (E)
1 + (0')l + 10~ (0))
max
(0))1)
eEant(()
Using the induction hypothesis (Inequality (17)) the antecedents of v and observing that p E p if, and only if there are u E ant(u),r r E P-* such that r + v gives (we highlight in blue the important changes):
| (00) - 1 a4 (0) < 1b. 6.100 + 110
(0')~*'11
+ 11
max wEant(U)
| ((0)"
longth(r)
langth(r))
max max nc EEnnt v)) rEP
|10~>r> 113
(br - -b,,1 10 + 110
max (Eant((2)
(0')11
k=
[b
b 1 + 110
(0')~>113 max
uEant(u)
langth(p)-
langth(p)
+ max PEP-1
Σ t=1
110
10-0po12 112
(1ppe - 1/ + 110 110- (0') - ||
max (pant((p))
| |,0000000)103
k=f+1
length(p)
length(pp)
(122- 11pp-1/pm 1/ +110-1110 110 1(8'm
max pEP
[1g
|| max w eannt(ps)
| "0=*"(())1))
A-=++1
This proves Inequality (17) for v and concludes the induction.
In the sequel it will be useful to restrict the analysis to normalized parameters, defined as parameters 0 such that (% م-v b
)l, E 10 for every u E N (Nom U Ni... Thanks to the rescaling-invariance of ReL.U neural network
23

---

A Rescaling-Invarian Lipschitz Bound using Path-Metries
parameterizations, Algorithm in Gonon et al. (2024a) allows to rescale any parameters into normalized version Ô such that R3 Ro and (0) (0) (Gonon et al., 2024a, Lemma B.2). This implies the next simpler results for normalized parameters.
Theorem F.2. Consider q 00). For every normalized parameters 0, 0' obtained the output of Algorithm 1 in Gonon et al. (2024a), it holds:
(0) 100')1
lb -,,1% + -1
111
" N Nar
longth (p)
min (11((0)1 (0))1
max p Nie
(16pe bppl +
-(00)~--11)) (1) -(0)
(18)
Denote by N()) the normalized version of 6, obtained as the output of Algorithm 1 in Gonon et al. (2024a). It can be checked that if 0 = N(Ō) and N(O)), and if all the paths have the same lengths L, then multiplying both and O' coordinate-wic wise by a scalar À does not change their normalized versions 9 and 0', except for the biases and the incoming weights of all output neurons that are scaled by X As a consequence, Inequality (18) homogeneous: both path-liftings on the
and the right- right-hand-sin hand-side are multiplied by X", and so the sum over e E Nour \ Nn in the gight-hand-side while the maximum over p is unchanged since it only involves normalized coordinates that do not change.
For networks used in practice, it holds Nowr n Ni = 0 so that Nour \ Nin is just Nour but the above theorem also covers the somewhat pathological case of DAG architectures G where one more input neurons are also output neurons.
Proof of Theorem F2. Since ((0) ve No."
it holds
((() ((80)
Σ
+ ( 4 (0))1))
W Non
By Definition A.5, it holds for every input neuron o: + (.)) = 1. Thus, the sum can be taken over e E Nou \ Nin:
[ - 600)11 =
DE Nau M Nin
Besides, observe that many norms appearing in Inequality (17) are at most one for normalized parameters. Indeed, for such parameters it holds for every E N \ (N U Nou):: |10 [100111g < 1 (Gonon et al., 2024a, Lemma B.2). As consequence, for p E P and any & E [0, length(p) - 1] we have:
length(p)
length(p)
0 PI
11
||0
119 <
Poos 1|@
Moreover, for normalized parameters and u & Nouts it also holds ([00>~ < 1 (Gonon et al., 2024a, Lemma B.3). Thus, Inequality (17) implies for any Nouts and any normalized parameters and 0':
+ (t) क ( 11
langth(p)-1
by 61,1 10 -0 (0')~
110 + l1g
max PEP-
(1bbc 16211 11 10 -00) -P (1
24

---

A Descaling-Invariin Lipschitz Bound using Path-Metric
Thus, get:
||((0) - 110
Σ 1|b- - Φ 15~0 (1)
oENur
(1b,- 6,1% + 11000 20 - -
vENar Nia
langth(p)
max 110011 pEP
(16pe 1/211 11
10- (0') (1))
VEN (N4
(br 8618 + 10 (0') =011))))
DENur Min
longtb(p)-1
+
1100111
max PEP: Nin
(10pe 1/y11 + 1l0 - (8')- (1)
PEN Min
remains to use that Eve Ni. case of equality) to conclude that:
110(0)11 11001.11 < 10
for normalized parameters (Gonon et al., 2024a, Theorem B.
[b) (0))18
Σ
(lb- 121 + 110~ - (0') (01)~
vENonAM No
longth(p)-1
+ (0)]1
max PEP P Nin
(1bpe 1/ 110
110 +p (0') PPr 18)
The term blue can be replaced by min else invariant under this exchange).
(1)(()) 1 by repeating the proof with 0 and 6 exchanged (everything
Lemma F.3. Consider a DAG ReLU network with L := D where the depth D maxpat pEp [length(p) and width W max(dou: maXneuron vEN ant(v)l) where ant(v) is the of antecedents of v in the DAG. Denote by @ the normalized parameters of 9 as obtained as the output of Algorithm 1 in (Gonon et al., 2024a) with q 1, i.e., is obtained from 0 by rescaling neurons from the input to output layer, ensuring every neuron has a vector of incoming weights equal to one on all layers except the last one. It holds for every 0, O' and every q E (o)
(0) - 200')1 & (W2 min (0) 1 (0))) LW) -0' 11
Lemma 4.3 corresponds Lemma F.3 with q
Proof of Lemma F.3. Lemma B.1 of (Gonon et al., 2024a) guarantees that ((N(O)) = = for every 0. In particular,
( ( = (N()) - (x(('))
so it is enough to prove Lemma F.3 for normalized parameters, so we may and will assume -N(0) 0' =N(0".. Denote
25

---

A Rescaling-Invariinl Lipschitz Bound using Path-Metrics
-= -0
(ote,by) by). With this notation, (18) implies (for normalized parameters 0,0")
langth(n)) -1
(9(0) 10000000111 200')11' <
100+0 - 10')~111 min[ (0) (0))))
110 - -p
maxX pe PiPPe & Ni
WE Now (Na VE Nou NNa
aant(v)l 1101-11100 110 (00)
length(p)-1 -1
min[1] (0))))
Σ
aan((pe)] -ant(pe)1-110- 11000 -00
max
PEP:Ped Nin
length(p)-1
Jant(pe)] ))
lant(v)] + mimmi (0)) m
(0())
max DEP: N
Σ
110 11
NeN NNa
The maximum length of a path is D = L + 1. Moreover W > down = |Noal and W > [nn for every neuron, so this yields
(0) (00)1 < (W2 + min 4
m (0)1 (+())1 LW) 11
G. Recovering a known bound with Theorem 4.1
It is already known in the literature that for every input and every parameters 0, (even with different signs) of layered fully-connected neural network with L affine layers and L + 1 layers of neurons, No ,,m...,N,, = No width W := maxogegt [NVe], and each matrix having some operator norm bounded by R > 1, it holds (Gonon et al., 2023, oo and = || (Neyshabur et al., 2018; Berner et al., 2020):
Theorem III.1 with
Rg (z) Rgy (x)]l1 < (W]l= + @WW.2RL--11 -
Can it be retrieved from Theorem 4.1? Next corollary almost recovers it: with W max([|=/]o<] 1) instead of W|| 1, and 27. instead of T.2. This is better
there are at least I. > 2 layers and as soon the input satisfies | 1. Corollary G.1. (Gonon et al., 2023, Theorem III.1) Consider simple layered fully fully-connected neural network architecture with L > 1 layers, corresponding to functions Re(x)= = Mr ReLU ReLU( with each Mr denoting matrix, and parameters f = (M1,..., M,M)- For a matrix M, denote by ||M] the maximum el nnorm of a row of M. Consider R > and define the set O of parumeters = (M1, Mr. such that ||Mell & Roror every & [1, Then, for every parameters 0, 6' θ and every input x:
[Ro(x) Ro (x)]li max([|=|]oo) 12- - 0'1
Proof. For every neuron v. define f() == l such that neuron belongs to the output neurons of matrix Me (i.e., of layer E
By Lemma F.1 with q 1, we have for every neuron
c (0) + * (0')
length(p)
length(p)
max pEP PM
0
111
k=
M 1m & R
Up - 1gy
10
(0e)-
max
-
(19)
wEant(p2)
=0 (no biases)
< ant(p:)) (100ppp))110011111 &W CW
langth(p)
wW10-011 0'1bo max
Σ
R plength(p)-E
max wEant(pe)
| (0''ll
(20)
PEP-
26

---

A Rescallin-Innvariin Lipschitz Bound using Path-Metries
with the convention that empty and product are respectively equal to zero and one. Consider 0' It holds (6')() 0 for every Ni. and ()=*((") for input neurons u (Definition A.5). Therefore, have:
max wEant(pe)
|| (0')ll = (nn e and po Nia
(21)
Specializing Inequality (19) to 0' = 0 and using Equation (21) yields
length(r)
langth(p)
i (0)l <
max Pe p
Σ
II
R
10PP
max eEnnt(pe)
| 50 (0''lll
t=1
k=(+1
Reg &R
max PEP-R
(lengtb(p))
(22)
Since the network is layered, every neuron ant(pe) is on the f - 1-th layer, and every p' p- is of length / 1, hence we deduce using Inequality (20), Equation (22) for 0 and u:
langth(p)
| (00) - + (0')1 < 1 1100
plangeh(p)-
Rl aanghh(y')
max pEP
max #Eant(pe) EP-+ - E.
max
t=1
length(p) Σ
11 - 1100
max
R plangth(p)-1
PEP
ELRC-1
IWR.-111 -10 111100.
We get:
[8((0) +(0')1
Σ 1 - T (0''
Ner's Nin
< NNort \ Nin LW R 1 110 0x1
L R ||0 6 bloo
(23)
Using Corollary B.2 with q = 1, we deduce that as soon as 0, 0 satisfy 0.0% > 0 for every parameter coordinate i, then for every input x:
|R (z) - Rg (z)ll1 < m 1) 0' ol.
(24)
Now, consider general parameters 0 and 6', Define ginter be such that for every parameter coordinate i
{
0f if 0 0, 0 otherwise.
Oimler
By definition, it holds for every parameter coordinate i: (imterg, > and ginter 3 0 so we can apply Incquality (24) to the pairs (8, ginter) and (ginter, 8') to get:
[R)())) Ro (x)111 < [R((x:) Ryun (x) + Ropur (x) Rg (x)
< mmxx (10011000000) 1. R (110 ginter |1 + ||ginter 0'11x0)
It remains that ||e ginter| || 3o ||ginter Bllloc 22|0 0'11o0- Consider parameter coordinate i.
If 0,0% > 0 then ginter 0 and:
10, 0,1 =10, Ointer + 10inter 0,/-
27

---

A Rescaling-Invanee Invariant Lipschitz Bound using Path-Metrics
Otherwise, 0ftier 0 and:
10, 8,1 =10.| + 10%1
= 10; Oimeer
+ [fimee
- 0//-
This implies |10 18--0m Gintte ll max; 88; ||0 0' This yields the desired result:
0itter|
< max; 10: 6imer + 10mmer
841 -10-8') 00o and similarly || - 8 &
[R)(x)) Rg (z))11 max([1>]loo. 1)2 0
28


Reviews:
[{"review_id": "N0qXnXHHJE", "reviewer": "Reviewer_NY8v", "summary": "This paper introduces a novel Lipschitz bound for modern ReLU neural networks that is invariant under neuron-wise rescaling transformations. The key idea is to leverage a \"path-lifting\" function which transforms the network parameters into a high-dimensional path space, where each coordinate corresponds to the product of weights along a path. While the path‑lifting function and the associated path‑norm have been introduced in previous works [1], this paper extends these ideas by establishing a rescaling‐invariant Lipschitz bound and deriving a practical pruning criterion. In other words, it is not the tool itself that is new, but its effective integration into a Lipschitz analysis framework that remains invariant under neuron‐wise rescaling and its subsequent application.\nAnd the paper further illustrates the utility of this invariant bound by deriving a new rescaling-invariant pruning criterion termed “Path-Magnitude Pruning,” and reports experiments demonstrating that this approach maintains performance under adversarial rescaling that would affect conventional magnitude pruning.\n\n[1] Gonon, A., Brisebarre, N., Riccietti, E., & Gribonval, R. (2023). A path-norm toolkit for modern networks: consequences, promises and challenges. arXiv preprint arXiv:2310.01225.\n\n## Update after rebuttal\n - I thank the authors for their response, which generally resolved my concerns. I will maintain my Overall Recommendation for the manuscript, standing on the acceptance side.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your points below.\n\n1. > The major limitation is the assumption of parameters/assumption of sign consistency\n\nAs shown by the example in Figure 5, page 13 (that we will move to the main text), the sign assumption cannot be simply removed in Theorem 3.1. This is thus not a limitation of the approach but a limitation of the achievable Lipschitz bound. We will highlight this fact, which is indeed a contribution.\nBesides, we highlight that this is not a limitation in practice for applications to quantization and pruning, and that it allows to obtain generalization bounds with *free* signs.\n\n2. > limited empirical evidence\n\nThe pruning experiment on a ResNet-18 is intended to be a proof-of-concept illustration of *one* possible application of our main contribution, which is theoretical: the nontrivial proof of Theorem 3.1. To avoid unnecessary energy consumption, we voluntarily avoided extensive comparisons which are clearly out of the scope of our claimed research contribution. In fact, the code that we will release on a non-anonymous repository allows to apply the same approach to more than 37 architectures available on torch.", "claims_and_evidence": "1. Novel Lipschitz Bound and Rescaling-Invariance:\nThe paper introduces a new Lipschitz upper bound based on path-metrics that is invariant to neuron-wise rescaling. The authors provide mathematical proofs (e.g., Theorem 3.1 and supporting lemmas) demonstrating that, under the assumption that parameter pairs maintain the same sign, the derived bound is both tighter and robust compared to traditional bounds based on standard ℓₚ norms.\n\n2. Path-Magnitude Pruning Criterion:\nThe paper proposes a pruning criterion (Path-Mag) derived from the proposed Lipschitz bound. The authors offer both an analytical justification (Lemma 4.2) and experimental results on ResNet-18 trained on ImageNet, demonstrating that the approach maintains performance under random rescaling—a scenario where conventional magnitude pruning fails.\n\n3. The major limitation is the assumption of parameters. Although practically justifiable in many scenarios (e.g., during pruning or with small gradient steps), this condition restricts the generality of the claim. Additionally, empirical evidence is limited to a single network (ResNet-18), leaving some uncertainty about applicability to other architectures.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for obtaining a rescaling-invariant Lipschitz bound based on path-lifting functions.", "theoretical_claims": "Overall, the proofs for the primary theoretical claims—including Theorem 3.1 (and its extensions) and the supporting lemmas—are correct and employ rigorous mathematical reasoning. The primary concern lies in the necessary assumption of sign consistency, which, although justifiable in many practical applications, narrows the scope of the theoretical claims. Furthermore, some steps in the proofs could benefit from enhanced clarity to assist readers less familiar with the underlying techniques.", "experimental_designs_or_analyses": "The experimental design and analyses are valid and sufficiently support the theoretical claims. The approach is well-motivated and the comparative evaluation is clear, despite being limited to a single network architecture (ResNet-18) and lacking extensive hyperparameter exploration.", "relation_to_broader_scientific_literature": "This work contributes to the broader literature in several ways:\n\n- **Theoretical Insight:** It builds on and extends prior work on the path-norm and Lipschitz analysis of neural networks (e.g., by Neyshabur et al., Gonon et al.).\n\n- **Practical Applications:** The method provides a new tool for pruning and potentially quantization, addressing known issues with conventional parameter norm bounds.\n\n- **General Applicability:** It successfully generalizes to modern network architectures that include pooling and skip connections, areas where traditional bounds are less effective.\n  \nOverall, the contribution is well situated within the existing literature on neural network generalization and robustness.", "essential_references_not_discussed": "I did not identify any major omissions of essential references. The manuscript appears to adequately cover the relevant literature.", "other_strengths_and_weaknesses": "### Strengths\n\n- **Innovative Theoretical Approach:**  \n  The use of path-lifting to achieve a rescaling-invariant Lipschitz bound is a clever idea that addresses a long-standing limitation in norm-based bounds.\n\n- **Broad Applicability:**  \n  The theoretical results extend to modern network architectures beyond simple feedforward models, encompassing pooling layers and skip connections.\n\n- **Practical Utility:**  \n  The derived bound is directly applied to design a rescaling-invariant pruning method, and experimental results confirm its practical benefits.\n\n### Weaknesses\n\n- **Assumption Limitations:**  \n  The theoretical guarantees require that corresponding parameters share the same sign, which might limit applicability in some practical settings.\n\n\n- **Clarity in Presentation:**  \nThere are some typos, for example, in Definition A.2, the definition of $\\theta^{v\\rightarrow}$ appears to be incorrect.", "other_comments_or_suggestions": "- **Further Discussion on Assumptions:**  \n  The authors should include more discussion on the practical impact of the sign consistency condition and potential extensions when this assumption is relaxed.\n\n\n- **Enhanced Experimental Comparisons:**  \n  It would be beneficial to include additional comparisons with other norm-based or invariance-aware methods, especially under diverse conditions of weight perturbation.", "questions_for_authors": "No other comments.", "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": "A3bVdOgQ88", "reviewer": "Reviewer_duh5", "summary": "The paper derives a Lipschitz upper bound for neural networks with ReLU and k-max-pooling activations. For two parameters $\\Theta$ and $\\Theta'$, the paper shows that $||R_{\\Theta}(x)-R_{\\Theta'}(x)||_1\\leq max(||x||_∞,1) ||\\Phi(\\Theta)-\\Phi(\\Theta')||_1$, with an assumption that $\\mathrm{sign}(\\Theta)=\\mathrm{sign}(\\Theta')$.\n\n\nHere the new vector $\\Phi(\\Theta)$ is the lifting of the original parameter $\\Theta$. This upper bound is rescaling-invariant, meaning that the upper bound only relies on the intrinsic property of the network, instead of the parameter. For any two parameters $\\Theta_1$ and $\\Theta_2$ such that $R_{\\Theta_1}=R_{\\Theta_2}$, then their liftings $\\Phi(\\Theta_1)=\\Phi(\\Theta_2)$.\n\nThis inequality can be used to prune a dense network into a sparse one, while ensuring it has similar performance compared with the dense network.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your points below.\n\n1. > assumption of sign consistency and extension to cases where only a few edges have different signs?\n\nAs shown by the example in Figure 5, page 13 (that we will move to the main text), the sign assumption cannot be simply removed in Theorem 3.1. This is thus not a limitation of the approach but a limitation of the achievable Lipschitz bound. We will highlight this fact, which is indeed a contribution. It is not difficult to design variants of the counterexample of Figure 5 with network parameters sharing the same sign on every edge except two, by \"prepending\" and \"appending\" arbitrary networks to the example.\nBesides, we highlight that this is not a limitation in practice for applications even beyond pruning (for example quantization), and it allows one to obtain generalization bounds with *free* signs (the proof sketch is given line 202, and could certainly be detailed in the supplementary in the final version if requested).\n\n2. extension to networks with activations beyond the ReLU\n\nThe leaky ReLU remains rescaling invariant and piecewise linear. Although the current path-lifting framework used to derive Theorem 3.1 does not cover the leaky ReLU, it is possible that a complete re-examination of this framework might allow for a generalisation of Theorem 3.1 to this activation. Regarding non rescaling-invariant activations, we cannot expect any bound of the same type as in Theorem 3.1 to directly hold as the right-hand-side is rescaling invariant.\n\n3. meaningful bound when deep/overparameterized networks, as path-coefficients are large\n\nYou are perfectly right: although the provided bound is the sharpest of its kind, it somehow remains a worst case over all weights with a prescribed path-norm. It now raises the challenge of obtaining tighter \"average\" bounds.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, the proof of the main theorem 3.1 is correct", "experimental_designs_or_analyses": "Didn't find any issue.", "relation_to_broader_scientific_literature": "It is a deep learning theory paper that might be useful for pruning.", "essential_references_not_discussed": "I didn't discover this issue.", "other_strengths_and_weaknesses": "Strength: The paper introduces a scaling invariant Lipschitz upper bound using parameter lifting. It is very clear and rigorous. The proof is well written.\n\nWeakness: The main result theorem 3.1 in this paper seems quite simple. The generalization bound derived from this theorem is not clearly stated and proved. (I am actually curious about that.) This theorem 3.1 has an application in pruning, but I am not very certain whether this theorem can be very impactful in other applications.", "other_comments_or_suggestions": "see 'Questions For Authors'.", "questions_for_authors": "1. The assumption that $\\mathrm{sign}(\\Theta)=\\mathrm{sign}(\\Theta')$ seems very strong. If we no longer assume this, is it possible to derive a looser upper bound? If we assume there are only a few edges $i$ such that the weights $\\Theta_i\\Theta'_i<0$, what bound can you get?\n\n2. Without requiring rescaling invariance, is it possible to extend the activation to leaky ReLU or some smooth activation functions? In that case, what is your upper bound?\n\n3. Is it possible that when the network is very deep and over-parameterized, the output of the network $R_{\\Theta}(x)$ is small, but every entry in your lifting $\\Phi(\\Theta)$ is very large ($\\Phi_p(\\Theta)\\gg0$), so you do not get a meaningful bound when you do pruning using equation (13)? In this case, is it possible to do some pruning while ensuring the output $R_{\\Theta}(x)$ doesn't change much?\n\nI will adjust the rating based on the answers and also the comments from other reviewers.", "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": "JZHLLRjyq1", "reviewer": "Reviewer_XzWf", "summary": "The paper proves a new reparameterization invariant Lipschitz bound in terms of the “path-metrics” of the parameters. The bound applies generally to network architectures with pooling and skip connections. Using the bound, the authors propose a rescaling-invariant pruning criterion.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your points below.\n \n1. > what if there is a normalization layer on the input \n\nWe assume you refer to batch normalization. As detailed in Gonon et al. 2024, batch normalization layers *as they behave at inference* are indeed covered in the path-lifting framework. While at training batch normalization dynamically adapts its weights to batches, this is no longer the case at inference where it acts as a plain affine layer. As a result, *the problem you raise does not appear*. The revision will make it clear.\n\n \n2. > mentioning the relation to sharpness\n\nSharpness measures [1, 2] are typically defined in terms of (averaged) loss differences  $L(\\theta+\\delta) - L(\\theta)$ over perturbations $\\delta\\in B(0,r)$ around a local minima $\\theta$. As such, they are not rescaling-invariant measures of $\\theta$ *alone*, since rescaling only $\\theta$ but not the perturbation $\\delta$ will change this quantity in general.  *One* consequence of our main Theorem 3.1 is to further bound this type of sharpness measure  (again by something which is not invariant in $\\theta$ alone, but invariant in both $\\delta,\\theta$). Indeed, if $L(\\theta) = \\sum_{i=1}^n \\ell(R_{\\theta}(x_i), y_i)$ with $\\ell$ Lipschitz in its first argument (e.g., cross-entropy, or squared loss on a compact), it holds $\\|\\ell(R_{\\theta+\\delta}(x_i), y_i) - \\ell(R_{\\theta}(x_i), y_i)\\| \\leq c \\|\\|R_{\\theta+\\delta}(x_i) - R_{\\theta}(x_i)\\|\\|$ and the latter is bounded by $c \\|x_i\\| \\|\\|\\Phi(\\theta+\\delta) - \\Phi(\\theta)\\|\\|$ according to Theorem 3.1.\nWe will add this to the final version.\n \n3. > I found the support for the usefulness of a Lipschitz bound weak in the paper\n\nIf we understood correctly, you are asking about the usefulness of Lipschitz bounds beyond their use to bound sharpness as above. The revision will cite additional papers [3-9] that use *non-invariant* Lipschitz bounds of the same type as those in (Neyshabur et al., 2018; Gonon et al, 2023) to design new algorithms and guarantees on pruning, quantization and generalization (not through sharpness, but via covering numbers). In all of these papers, Lipschitzness comes in as a crucial property to control how the function changes with small weight perturbations. However, these papers unfortunately suffer from the two problems motivating our paper: 1) they use non-invariant bounds, which not only can be made arbitrarily pessimistic but that might also yield algorithms with huge performance drops when run on rescaling-equivalent parameters (Figure 6), and 2) they only hold for simple fully-connected models organized in layers.\n\n\n[1] How Does Sharpness-Aware Minimization Minimize Sharpness? Wen et al. 2023. Table 1.\n\n[2] A Modern Look at the Relationship between Sharpness and Generalization. Andriushchenko et al. 2023. Equation (1).\n\n[3] Liebenwein et al., Provable Filter Pruning for Efficient Neural Networks, ICLR 2020.\n\n[4] Baykal et al., Data-dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds, ICLR 2019.\n\n[5] SiPPing Neural Networks: Sensitivity-informed Provable Pruning of Neural Networks. Baykal et al. 2019.\n\n[6] Arora et al., Stronger Generalization Bounds for Deep Nets via a Compression Approach, ICML 2018.\n\n[7] Zhang et al., Post-training Quantization for Neural Networks with Provable Guarantees, 2023.\n\n[8] Lybrand and Saab, A Greedy Algorithm for Quantizing Neural Networks, JMLR 2021.\n\n[9] Schnoor et al., Generalization Error Bounds for Iterative Recovery Algorithms Unfolded as Neural Networks, 2022.", "claims_and_evidence": "The authors claim that their bound is rescaling invariant, while it is theoretically sound due to the construction of path-lifting space, there is no experimental evidence that the bound is non-vacuous, e.g. both sides of the bound correlate with one another. \n\nLine 311-315 left column: “We show this to match the accuracy of magnitude pruning when applied to ResNets trained on Imagenet in the lottery ticket context (Frankle et al., 2020), while being rescaling-invariant”. I cannot find any figures/tables that support this claim, except what is briefly mentioned in line 396-399.", "methods_and_evaluation_criteria": "There is no empirical evaluation.", "theoretical_claims": "I have checked the proof sketch of theorem 3.1, and it looks sound to me.", "experimental_designs_or_analyses": "There is little or no experimental result shown.", "relation_to_broader_scientific_literature": "The authors claim that they are the first in literature that propose a scale invariant Lipschitz bound. I found the support for the usefulness of a Lipschitz bound weak in the paper, and only two papers are mentioned (Neyshabur et al., 2018; Gonon et al, 2023). Moreover, the Lipschitz bound in Neyshabur et al., 2018 is only used to bound sharpness, which in turn connects to generalization. On the sharpness side, there are plenty of rescaling invariant bound proposed since Dinh et al., 2017, and I feel that the authors should more thoroughly discuss this connection with sharpness bounds, and see how their bound is relevant. In fact, if MSE loss is used, sharpness is exactly the norm of gradient of the output of networks w.r.t. the parameters (see e.g. Wen et al., 2023, lemma 4.1; Ma & Ying, 2021, Equation 3).", "essential_references_not_discussed": "No work absolutely needs to be brought up. But I think work related to rescaling invariant sharpness is worth mentioning due to the reason above. Similarly, more work that shows the usefulness of a Lipschitz bound can be mentioned.", "other_strengths_and_weaknesses": "For the main inequality (3), if we have a normalization layer on the input (which is valid according to line 77), wouldn’t it make the inequality vacuous, since we can arbitrarily scale the input with R and \\theta stays the same?", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "No other questions.", "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:

Meta-review: This article presents bounds on the Lipschitz constant of a ReLU network that is invariant to multiplicative reparameterizations. The core construction is based on a lifting to "path space," in which the output of the network is written as a sum over paths from input to output of a product of weights along the path. Some empirical applications to pruning and robustness are presented. While not extensive, they are reassuring.
Decision: Accept (poster)