A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations

Thank you for your review. We address your points below.

1. what if there is a normalization layer on the input

We 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.

2. mentioning the relation to sharpness

Sharpness 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. We will add this to the final version.

3. I found the support for the usefulness of a Lipschitz bound weak in the paper

If 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.

[1] How Does Sharpness-Aware Minimization Minimize Sharpness? Wen et al. 2023. Table 1.

[2] A Modern Look at the Relationship between Sharpness and Generalization. Andriushchenko et al. 2023. Equation (1).

[3] Liebenwein et al., Provable Filter Pruning for Efficient Neural Networks, ICLR 2020.

[4] Baykal et al., Data-dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds, ICLR 2019.

[5] SiPPing Neural Networks: Sensitivity-informed Provable Pruning of Neural Networks. Baykal et al. 2019.

[6] Arora et al., Stronger Generalization Bounds for Deep Nets via a Compression Approach, ICML 2018.

[7] Zhang et al., Post-training Quantization for Neural Networks with Provable Guarantees, 2023.

[8] Lybrand and Saab, A Greedy Algorithm for Quantizing Neural Networks, JMLR 2021.

[9] Schnoor et al., Generalization Error Bounds for Iterative Recovery Algorithms Unfolded as Neural Networks, 2022.

Thank you for your review. We address your points below.

1. assumption of sign consistency and extension to cases where only a few edges have different signs?

As 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. Besides, 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).

2. extension to networks with activations beyond the ReLU

The 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.

3. meaningful bound when deep/overparameterized networks, as path-coefficients are large

You 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.

Thank you for your review. We address your points below.

1. The major limitation is the assumption of parameters/assumption of sign consistency

As 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. Besides, 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.

2. limited empirical evidence

The 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.