Some Fundamental Aspects about Lipschitz Continuity of Neural Networks
Authors: Grigory Khromov
Sidak Pal Singh
Venue: ICLR 2024 poster (2024)
Keywords: Lipschitz continuity
Double Descent
Label Noise
Generalization
Primary area: learning theory
TL;DR: An empirical investigation into the behaviour of the Lipschitz constant for Deep Learning models in various learning settings.

Abstract: Lipschitz continuity is a crucial functional property of any predictive model, that naturally governs its robustness, generalisation, as well as adversarial vulnerability. Contrary to other works that focus on obtaining tighter bounds and developing different practical strategies to enforce certain Lipschitz properties, we aim to thoroughly examine and characterise the Lipschitz behaviour of Neural Networks. Thus, we carry out an empirical investigation in a range of different settings (namely, architectures, datasets, label noise, and more) by exhausting the limits of the simplest and the most general lower and upper bounds. As a highlight of this investigation, we showcase a remarkable fidelity of the lower Lipschitz bound, identify a striking Double Descent trend in both upper and lower bounds to the Lipschitz and explain the intriguing effects of label noise on function smoothness and generalisation.

Published as a conference paper at ICLR 2024
SOME FUNDAMENTAL ASPECTS ABOUT LIPSCHITZ CONTINUITY OF NEURAL NETWORKS
Grigory Khromov* and Sidak Pal Singh*ab
Department of Computer Science ETH Zürich b Max Planck ETH Center for Learning Systems
ABSTRACT
Lipschitz continuity is crucial functional property of any predictive model, that naturally governs its robustness, generalisation, as well as adversarial vulnerability. Contrary to other works that focus obtaining tighter bounds and developing different practical strategies to enforce certain Lipschitz properties, we aim to thoroughly examine and characterise the Lipschitz behaviour of Neural Networks. Thus, we carry out an empirical investigation in a range of different settings (namely, architectures, datasets, label noise, and more) by exhausting the limits of the simplest and the most general lower and upper bounds. As a highlight of this investigation, we showcase remarkable fidelity of the lower Lipschitz bound, identify a striking Double Descent trend in both upper and lower bounds to the Lipschitz and explain the intriguing effects of label noise on function smoothness and generalisation.
INTRODUCTION
Lipschitz continuity of function is key property that reflects its smoothness the input is perturbed - since, to put it more accurately, it is the maximum absolute change in the function value per unit norm change in the input. Typically, in machine learning, we desire that the learned predictive function is robust, i.c., not overly sensitive to changes in the input. If achieving point-wise robustness in the entire input domain is difficult, then we would, at least, hope be robust over a large and representative subset of the input space with respect to the underlying data distribution (like in the vicinity of the training samples). Otherwise, we can expect that a function which varies too drastically in response to minuscule changes in the input, especially when the input is near the decision boundary or from another representative region, would struggle to generalise well on unseen test data. Also, the flip side, would be wary if the value of the Lipschitz constant (associated with the corresponding Lipschitz continuity) is extremely small (for the sake of the argument, think zero) over the entire input space, for this would imply excessively large bias (Geman al., 1992) and essentially a useless function.
This intuitively captures why the Lipschitz constant of the model function would shed light on the nature of its fit. Thus, not all too surprisingly, the Lipschitz constant has been shown to play a crucial role in various topics such as generalisation (Bartlett al., 2017), robustness (Weng al., 2018), vulnerability to adversarial examples (Goodfellow et al., 2015; Huster et al., 2018), and more. As a result, this has spurred significant body of literature. especially, in producing tighter estimates to the Lipschitz (Jordan & Dimakis, 2020; Virmaux & Scaman, 2018; Xu et al., 2020; Fazlyab et al., 2019; Gómez al., 2020) and applying different forms of explicit Lipschitz controls (Anil et al., 2018; Gouk et al., 2021; Cissé et al., 2017; Petzka et al., 2017; 7; Tsuzuku et al., 2018).
Aim of our study. In contrast, our work forms a slight departure from these (mainstreaam categories: we want to understand the inherent nature of the Lipschitz constant and its phenomenology as seen, in practice, Deep Neural Networks. Yet, most importantly, we not want to burden ourselves with tighter Lipschitz estimates that, however, restrict investigation to small datasets like MNIST (or at most CIFAR- 10) given their increased computational costs. Nor do we want to study networks where
* Equul Contribution. Correspondence to gkhromov@ethz.ch ssí dak@echz. ch. Our code is publicly available on GitHub.

---

Published as a conference paper at ICLR 2024
the Lipschitz explicitly regularised in numerous distinct ways, but want to arrive at whether there is an inherent or implicit regularity in the Lipschitz behaviour for the most common networks that are trained without any explicit regularisation at all (Lipschitz or otherwise). Thus, our motivation stems from striving for a better understanding of modern over-parament weeepparaeteerised deep networks, and we would like to explore and uncover fundamental aspects of Lipschitz continuity in this regard.
Approach. As we have discussed, on one hand, tighter estimates of the true Lipschitz are, more often than not, rather computationally expensive, which greatly limits their use. On the other hand, when simple bounds are utilised, there is an element of uncertainty about whether the findings apply to the true Lipschitz constant or just that particular bound. In this paper, however, we propose to sidestep this issue by first identifying the simplest possible bound whose fidelity to the Lipschitz constant can be reasonably established. Then, as a safeguard, we also track the (usual) upper bound to the Lipschitz- - and thereby effectively 'sandwiching' the true Lipschitz value in between. Having done so, we then completely turn our focus to extracting as many insights as possible via these bounds, which are demonstrated is but a simple conceptual shift in research perspective, which however lets us showcase intriguing traits about the Lipschitz constant of neural network functions in multitude of settings.
large-scale network-datasel settings (like, ResNet50 on ImageNet). This
Contributions. (i) We begin with investigating the nature of the Lipschitz constant, in terms of its deviation from the value at initialisation and how it behaves during the course of training. In this setup, we also show the fidelity of the local Lipschitz-basee lower bound, confirm the trends with larger models and datasets, as well as provide intuitive toy example explain our findings. (ii) Then, we investigate (and back) the folk wisdom about weer-parameterisation resulting in smooth interpolation through the lens of the Lipschitz, when networks of increasing width are trained in a Cuuble-Desceet-Piee setting. We supplement this empirical finding by sketching a theoretical argument for this behaviour using the bias-variance trade-off. (iii) Finally, we complete the existing picture surrounding the behaviour of the Lipschitz constant in the presence of label noise, across a wide range of network capacities and noise strengths. We find that there is an interesting interplay of network capacity, noise, functional smoothness, and memorisation that provides more nuanced and rounded view of ovvoovvveammnee parameterisation.
Ultimately, we hope that our work facilitates further theoretical advances by providing ground or, at least, scaffolding to base or refute theoretical hypotheses about the Lipschitzness of neural networks.
2 THEORETICAL PRELIMINARIES
This paper introduces multiple bounds on the Lipschitz constant, as well as various ways of computing it. To aid the reader, we include a list of all notations in Appendix S1. We start by recalling the definition of Lipschitz-continuuus functions:
Definition 2.1 (Lipschitz continuous function) Function f: HRRRRR RK, defined on some domain dom( C IRd, is called C-Lipschitz continuous, >>> O, w.r.l some a-norm if, V y dom(s) [I - f(y & C [[l
Note that we are usually interested in the smallest C, such that the above condition holds. This is what we call the (true) Lipschitz constant of the function f, which is, unfortunately, proven to be NP-hard to compute (Virmaux & Scaman, 2018). Therefore, we focus on the upper and lower bounds of the true Lipschitz constant. To give lower bound, we will need an alternative definition. For simplicity, we compute the 2-norm (i.e. ā = a = 2) throughout the rest of the paper.
Proposition 2.1 (Alternative definition (Federer, 1996; Gómez et al., 2020)) Let function f Rd + K be defined on some domain dom{( C Rdd Let I also be differentiable and C-Lipschitz continuous. Then the Lipschitz constant C is given by: C = SUPxEdom([]) VV where VxJ is the Jacobian of f w.E.t. to input x. â is the dual norm of a if K = 1, otherwise à a.
Lower bound via local Lipschitz continuity. Instead of considering the Lipschitz constant over the entire input domain dfm( we can restrict ourselves to the subspace of the domain where the underlying data distribution is supported, and its neighbourhood (denoted as D+). Under the i.i.d. (independent and identically distributed) assumption in which we typically operate, this definition of 'effective Lipschitz constant' (Cp+) carries a direct significance. Moreover, this also provides a natural way lower bound the effective Lipschitz. constant based finite-sampl evaluation, like
2

---

Published as a conference paper at ICLR 2024
on the training set S _ D
C2 CD+ sup Vx/olla > sup Vx =: Clower
XED+
XES
An alternative approach would be to use a straightforward Lipschitz computation: Calt. lower
[1/o())-oet>ll For the rest of the paper, we will focus computing (I), Calt. lower
suPx.yED+ xxy xx y requires (n²²) evaluations, and, as shown in Appendix S2.1, results in worse estimates.
We also track Caug norm Ex Vo la. i.e., the expected value of the Jacobian norm, to better contextualise recent work. For instance, this quantity is equivalent to Geometric Complexity, intro- duced by Dherin et al. (2022). Yet, this can be much less than the considered lower bound estimate Clower- Thus, on its own, it is insufficient to establish claims on the Lipschitz constant.
Upper bound via product of layer-wise upper bounds. Tight upper bounds the Lipschitz constant, however, are far from straightforward to compute, as can be seen in works mentioned in Section 6. Thus, as expected, we use the simplest upper bound, which just the product of per-layer Lipschitz constants. Let us assume we have network fo with L layers, 1-Lipschitz non-linearity a, such as ReLU, and parameters E Rp. The overall function can be then expressed as fe f(L) a o f((-1)
o o f())
We can then upper bound the Lipschitz constant:
L.
CS II
IV x 1 S II sup V x 1) 10 =: Cupper:
sup
(=1 gdm
where (i-11) denotes the input at the layer i, i... the post-activation at layer i 1. In the above equation, we just used I-Lipschitzness of the non-linearity and then considered an unconstrained supremum (see more details in Appendix S2.2). As simple example, take the case of single linear layer (x) ( x the upper bound to the Lipschitz constant is clearly equal to the spectral norm of the weight matrix, i.e., Cupper |W 2 Similarly, for an I--laer network, the upper bound
comes out to be the product of the spectral norms of the weight matrices: Cupper = I ||W
3 INSIGHTS INTO THE NATURE OF THE LIPSCHITZ CONSTANT
3.1 DOES THE LIPSCHITZ CONSTANT DEVIATE SIGNIFICANTLY FROM INIIIALISATION? WHAT ITS EVOLUTION REALLY LIKE?
For sufficiently wide neural networks, recent theoretical works often assume that the network function and its linearised version' around the initialisation (Chizat al., 2019) behave similar enough, while being identical in the limit of infinite-width (Jacot et al., 2018; Du et al., 2019). While it is still not entirely clear how close today's 's massively wer-parameterised networks actually approach this limit, it is widely acknowledged that such a limit does not adequately capture feature learning (Arora et al., 2019; Lee et al., 2020; Samarin et al., 2022). So, it is not apparent how much is the eventual Lipschitz constant of the network determined by that at initialisation. Moreover, if it does deviate significantly. does it in fact decrease or increase, or something completely else takes place? These are the kinds of questions we would like to settle in this section.
Evolution of the Lipschitz constant. Let us start simple by first exploring how the Lipschitz constant evolves when training fully fully-connected network (FCN) with ReLU activations (FCN ReLU for short) using cross-entropy (CE) loss. Figure shows this trend for a pair of networks with moderate and extreme hidden layer widths (i.e., 256 and 65,536 respectively). We can observe that both the Ckower and the Cupper keep increasing as the training proceeds. In particular, while they start from similar values at initialisation, they rapidly drift apart from each other. We explore this effect through the prism of network linearisation in Appendix S..1.
The Lipschitz behaviour seems to saturate at some point sufficiently further into the training process, but relative to the initialisation, the lower and the upper bound grow, for both widths, by a significant factor. This strictly increasing behaviour of the Lipschitz might be attributed the nature of the CE loss, for which convergence requires taking the parameters norms to infinity. But, as a matter of fact, we find that similar behaviour can be seen in the case of MSE loss in Figure S9. So, while the much wider network has smaller increase in Lipschitz, the growth is significant. Thus, it seems that even at such high widths, the network deviates far enough from its initial state, and the eventual Lipschitz constant overshadows the one at initialisation.
li.e., linearisation in the function space, f(x; 0) f(x: Oo. (xf(x;00))
3

---

Published as a conference paper at ICLR 2024
Cuper
Gueer
Cuagznns
Coloue
Cinee
01
333.00
4302
1C300
9000 (X003)
12000
updates
updases
Figure 1: Plot of Lipschitz constant bounds by training epoch for FCN ReLU network with hidden layer widths 256 (left) and 65,536 (right) on MNISTID. Cupper. Clower and Cavg are computed on train dataset S, whereas Cg- is the local Lipschitz computed on the S Relative to initialisation, the lower bound at convergence grows by a factor 63x, 40x, while the upper bound by 66x, 10x, for the widths 256; 65,536 respectively. Results are averaged over 4 runs. See Appendix $2.6.8.
Fidelity of the lower bound to the effective Lipschitz constant. Next, as the effective Lipschitz constant lies somewhere between the upper and the lower bounds, what still remains unclear is how loose are these bounds and where our quantity of interest lies. To give more insight into this, we compute the lower Lipschitz bound (1) a larger set of examples S*, which is the union of the training set S, the test set S", and a set of random convex combinations of samples from the train and test (see $2.6.8 for more details). The results presented in Figure 1, corresponding to the legend Cs-,, where it becomes evident that the bound for the Lipschitz constant computed on this expanded set S lies much closer the lower bound Clower than the upper bound Cupper- While the gap between the upper and the lower bound may not seem that drastic here, the upper bound can quickly become extremely large for deeper models (c.f., Figure and Appendix S3.8), leading to significant overestimation of the Lipschitz constant. In fact, this aspect about the fidelity of the lower bound can also be spotted some past works (Gómez et al., 2020), although it does not get a proper discussion. Overall, this seems to suggest that the trend of effective Lipschitz constant is more faithfully captured by the lower bound Clower, contrary to the upper bound Cupper-
A theoretical picture. To understand the increasing Lipschitz trends analytically, we develop upper bound on the Lipschitz constant in Appendix 1..1. short, given SGD updates with constant learning rate 7) (0, oo) and assuming the loss gradients
bounded by B E (0, oo) (which could be enforced by gradient clipping, for instance), we get the that the upper bound on the Lipschitz constant CT time step follows the trend Cr x BTTT. Although this bound only describes the behaviour of the upper bound to the Lipschitz constant, the analysis still shows the undeniable effect of training the function's Lipschitz continuity.
3.2 WHAT HAPPENS FOR BIGGER NETWORK DATASET SETTINGS?
Given the above experiments were based on simple network-datasee settings - primarily to allow us to elucidate the point about the Lipschitz of extremely wide Neural Network and its deviation from initialisation, we now test whether the trend about the growth of Lipschitz persists for more modern pee-pparaetrriedd networks bigger datasets as trained in practice.
To thoroughly establish whether our results carry over for networks with millions of parameters, we take the case of RESNET50 and a VISION TRANSFORMER (VIT) trained IMAGENET. Note that we are forced to slightly restrict the computation of the Lipschitz estimates to a smaller number of checkpoints during training, well the number of samples. In brief, this is due the high computational complexity 2 involved in the process of evaluating the Jacobian norms of significant number of large matrices. The results for these experiments can found in Figures 3. As ViTs do not possess theoretical upper bound (Kim et al., 2020) due to the presence of quadratic interactions in input and attention layers, only local Lipschitz- based estimates are presented in Figure 3.
CCmputing the lower Lipschitz on the entire ImageNet would require evaluating 1.2 million Jacobian matrices of size 1,000 x 150,528, for a single seed and single checkpoint. As a reference, training ResNet50 for 90 epochs with a 1024 batch size requires ~ 106,000 gradient evaluations. Hence, lower Lipschitz estimation at a single checkpoint is almost as expensive as one entire training run. This justifies the expediency of employing subsampling. Moreover, the variance of this procedure seems minimal (Appendix S3.6).
4

---

Published as a conference paper at ICLR 2024
Caper
Giae
Cruppc boaadd sahee
Clnos bounck valo.
10-
Cuzaaa
228
102
Guee
Cuyy
60
73
30 30
60
70
100cch
13arch
Lipschitz constant bounds for ResNet50 on subset of 200,000 samples of Im- ageNet. Results are averaged over 3 runs. More details in Appendix $2.6.9.
Figure 2:
Figure 3: Lower Lipschitz constant bounds evolution for VIT on a 50,000 sam- ples ImageNet subset. More details in Appendix S3.5.
The first thing that catches eye is that the upper bound gets almost vacuously large, with the gap between the lower and upper bounds, for instance in the case of ResNet50 in Figure 2, stretching to 40 orders of magnitude (mind the different y-axes). This suggests that upper bounds excessively lax (even at initialisation itself, is of the order 1e27, which can be attributed to the exponential increase with depth). It seems more plausible that the values of the (local Lipschitz) based lower bound are more revelatory about the effective Lipschitz, or the nature of the function in general.
Given the extremely high values of the upper bound, it can be argued whether our computed lower bounds are still representative of the effee- tive Lipschitz. To investigate this, we take the top 1, 000 samples that have the highest Jaco- bian norm, consider their convex combinations, and use that as a basis to evaluate the local Lip- schitz. In fact, in Figure S8, we show the entire distribution of norms for these 'hard' convex combinations, well as the entire ImageNet train set (See Appendix 12.6.10).
2100
Jacobion weme ImageNes
8.00
Jacobion seme cocakmatiaoos
c.05
c,00
30
100
355
303
390
Jacobion norm vilue
We find that while the distribution indeed shifts towards larger per-sample Jacobian norms for the hard convex combinations, the shift is not even a multiplicative factor of 2x more. This shift pales in comparison to the upper bound which is over tens of orders of magnitudes higher. Overall, this strengthens our claim that the lower bound is much more faithful to the effective Lipschitz value and can hence serve better explore various phenomena observed in over pee--aaramtteiieed Neural Networks. Lastly, we leave similar distribution plots for other models and datasets in Appendix 13.
Figure 4: Distribution of the per- sample Jacobian norms for ResNet18, computed the entire Ima- geNet and 1,000,000 hard convex combinations.
3.3 GATHERING INTUITION FROM TOY EXAMPLE
In the previous discussion, we have substantial evidence for the fidelity of the lower bound to the effective Lipschitz constant. In order to gather some intuition, we now consider toy example, that gets to the essence of our discovered findings and enhances our understanding of them.
We take a synthetic dataset on a two-dimensional closed set, for example D = [[-5, 5]2, with 3 equally spaced classes generated by a Gaussian distribution. Due the close proximity of the classes relative to the standard deviation of the distribution, some training points may lie in a region of another class. We now train an FCN ReLU classifier until 100% train accuracy and compute the lower and upper Lipschitz estimates, which come out to be 135.815 and 389.097, respectively. Thanks to the designed setup here, however, we can tractably compute an estimate of the effective Lipschitz constant CD by densely sampling 1 million points in the entire input domain and computing the maximum over the point-wise Jacobian norms. The estimate evaluates to 144.194, which is rather close to the Ctower estimate. In fact, we see the reason for this in Figure 5 - the highest function change occurs near the decision boundary, where, in turn, the local Lipschitz constant is the highest. Since the decision boundary lies in the vicinity of the training samples (this is supported by the existence of adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2015)). the lower bound manages to capture the effective Lipschitz constant quite well.
5

---

Published as a conference paper at ICLR 2024
Decasion boundary
136.5
109.5
9000
XX
Decision boundary
00.0
-2
66.6
Cllsss 1
Class 2
Cloes 3
26.
1500
Figure 5: Plot of function prediction (left) and the local Lipschitz constant bounds (right) for the whole input domain D [-5,, 5|2. More details in Appendix $2.6.1.
Adversarial and the lower bound on ad adversarially perturbed training samples for CIFAR-10 and OOD samples for MNISTID. As we show detail in Appendix $3.2 and S3.3, this evaluation only marginally improves the lower bound which does not quite justify the added computational burden if an efficient Lipschitz estimate is the focus.
(OOD) samples. Guided by the above intuition, also evaluate
4 IMPLICIT LIPSCHITZ REGULARISATION, OR LIPSCHITZ DOUBLE DESCENT
A commonly held view (Belkin, 2021) about the effectiveness of heavily over-parameterised neural networks, in the context of generalisation on unseen, is that with increasing parameter count the network, in tandem with simple optimisation algo- rithm like stochastic gradient descent (SGD), finds a solution where the extra capacity helps towards fitting the training sam- ples smoothly. contrast, with just as many parameters p as the number of training samples the smoothness of the interpola- tion is not within control and we observe worse generalisation. And, with parameters less than that, i..., p n, the network is even unable to fully fit the training samples. Figure 6 sketches the general shape of the model in these regimes.
Figure 6: Cartoon of the three model regime: underfitting, over- fitting, & smooth interpolation.
More concretely, this view has garnered significant evidence through the occurrence of what is known as the Double Descent (DD) phenomenon (Belkin al., 2019; Nakkiran et al., 2020; Bartlett et al., 2020; Montanari & Zhong, 2022; Singh et al., 2022). In particular, with increasing network capacity (say, via layer width) the test loss first decreases 3, then increases up certain threshold of capacity (known as the interpolation threshold, where theoretical works supporting double descent show - usually in fairly simplified settings that the test loss exhibits such a behaviour. However, it largely remains difficult to attribute or pinpoint the behaviour test loss to a core functional property of the network.
n), beyond which it further decreases. The
Given the above discussion about the smoothness of interpolating over peeepaarmmteeieed solutions, the Lipschitz constant forms natural candidate for a functional property that signifies smoothness, and we, thus, investigate if its trend with network width has similarities to DD. In Figure 7, conduct an experiment replicating the DD setup, by training Convolutional Neural Networks (CNNs) of increasing width (i.e., number of channels) to convergence CIFAR- 100. We notice the plot clearly shows how all three Lipschitz constant bounds grow until the interpolation threshold and decrease afterwards, while also mirroring the trend in the test loss.
Similar trends in the Lipschitz constant can also be seen for other network-datased settings (FCNs, ViTs;; MNISTID, MNIST, CIFAR-10), as well as the MSE loss, the results for which are located in Appendix $3.9.
'This is an idealised depiction of DD, since often the initial descent requires considering very small networks and may not even be visible (Nakkiran et al., 2020; Mei & Montanari, 2022; Singh et al., 2022). The more prominent DD signature is the test loss peak the interpolation threshold and the ensuing monooonot..,yity

---

Published as a conference paper at ICLR 2024
16
panars Se i
Cuper Cuneer
Ices valos
3014
paranis RS
10-1
16-1
Test loss
16
Truin loss
10-1
101
10 perametecs
101
10 parameterr
Figure 7: Comparison of various Lipschitz constant bounds with train and test losses with increasing network width, for CNN networks trained on CTFAR-100 with CE loss. Results are averaged over runs. More details about the networks and the training strategy are listed in Appendix $2.6.5.
Implicit Lipschitz regularisation. While significant number of works in the literature specifically set out to design new and more convenient ways to explicitly regularise the Lipschitz constant during training (Gouk et al., 2021; Bungert et al., 2021) or designing architectures with Lipschitz guarantees (Anil et al., 2018; Wang et al., 2021), the above finding highlights that, even without such explicit controls, aver-parruettrriiatiion seems to provide regularisation. This could also potentially hint why, despite copious work, the direction of explicit Lipschitz regularisation has seen a relatively muted practical impact and adoption, barring certain specialised areas (Arjovsky et al., 2017; Cissé et al., 2017; Terjék, 2019). Although the strength of this implicit Lipschitz regularisation is likely problem and architecture dependent, adding explicit regularisation (here enforcing Lipschitzness), as observed in usual DD settings (Nakkiran et al., 2021), can indeed reduce the DD trend in both loss and the Lipschitz bounds (see Appendix S3.12).
implicil pressure lowards Lipschitz
Besides, the above results provide additional backing for the intuition expounded around the smooth- ness of interpolating solutions by Belkin (2021). Lastly, this also restores hope for the established generalisation bounds based on the Lipschitz constant (Bartlett et al., 2017) and potentially reworking them on the basis of the effective Lipschitz constant, similar to Dherin et al. (2022).
A bias-vat varianaee trade-off argument. Understanding the exact mechanisms of the Lipschitz DD from a more theoretical avenue would form a great direction. While this would stretch far beyond the current scope, we nevertheless supplement our discussion with theoretical argument that connects the Lipschitz behaviour with the test loss as seen above.
The details of the analysis can be found in Ap- pendix 54.2, but let's present the gist of the argument here. We define a Neural Network function fe (x, (), where ( indicates the noise in the function due to the choice of random initialisation (i.e. random seed).
appros. Caper
Bound upprex by Caae Viriancs
vertence
We can then bound the variance term in the test loss as follows (Var bound 1): E x Varç ()) s
3 (C² + +T,') Ex ||x|2
+ const, where Cg is the mean Lipschitz constant across seeds and the Lipschitz constant C of the ensembled function
paranclass
To(.) [x( {)). Figure 8 presents an empiri- cal calculation for the variance bounds (results for the bias term can be found in Appendix S3.11), where the trend of the function variance aligns closely with the trend of our upper bounds, at least qualitatively. Since the above theoretical analysis only establishes an upper bound on the function variance with the Lipschitz constant, it would be very interesting to develop a corresponding lower bound that shows the dependence on the Lipschitz constant, but that is beyond our current confines.
Figure 8: Variance and its upper bounds, where Ce Var bound 1 is estimated using Clower and Cupper estimates. See Appendix 12.6.11.
5 NOISE, CAPACITY, AND
Zhang et al. (2021) emphatically show that the over- wer--arameterised Neural Networks have the ability completely memorise points when trained with random labels, but these are the same networks that
7

---

Published as a conference paper at ICLR 2024
also generalise when presented with clean data. However, they consider this in regard network with fixed capacity and certain amount of label noise. Now imagine that we keep increasing the proportion of randomly labelled points while keeping the network fixed. Will the Lipschitz keep increasing monotonically? Will the behaviour be the same we had a bigger or a smaller network? Introducing randomised labels should make the task harder (Bartlett et al., 2017), but does matter as long as the network has more parameters than training samples? In this section, we explore this interplay of the noise strength, network capacity, and the resulting level of generalisation.
Thought experiment. Consider a task, where labels >> and y -1 otherwise, and sampled uniformly on the reals in a certain range. Then, consider the case of an extreme amount of label noise (perhaps relative to network capacity), so that we effectively sample y = at the value of In such case, the best network can do to just predict ğ = O, vx. But for such prediction, the learned function is smooth it gets, with Lipschitz constant of O.
Low
Mediun Capacity
Cipaaitt
Csalus
Hlgh Capacity
without looking
0%
Isbel notor
100%
Figure 9: Outline of the behaviour of the Lip- schitz constant with label noise for networks with different capacities.
A hypothesis for Lipschitz behaviour with label noise. Based on the intuition above, we would hypothesise that while the network is able to fi the noise, the Lipschitz constant should increase. At some point, when the noise strength becomes sufficiently high relative to the network capacity, we would reach a 'memorisation threshold', beyond which the predictor starts collapsing to smoother function with smaller Lipschitz constant. We depict our hypothesis pictorially in Figure 9.
Empirical evidence. To test this hypothesis, we train a bunch CNNs on CIFAR- 10 with increasing width and label shuffling levels from 0% (clean) to 100% shuffled (fully random) targets. The results can be found in the Figure 10. (i) Firstly, looking at the rows, we notice that for every noise strength, the Lipschitz constant shows Double-Descent-Il can perhaps be expected for low noise strengths, though not all). (ii) But, more interestingly, if we look at the columns, we find that there is similar non-monotonicity, in line with our hypothesis above. (iii) There a shift of the memorisation threshold, which matches the movement of the interpolation threshold in Double Descent, towards a higher parameter count in the presence of label noise (Nakkiran et al., 2020). (iv) Lastly, heavily over peeepaaamtttrieed networks fit random labels more smoothly, compared networks with fewer parameters.
non-monotonicity with increasing width (which
Overall, we see a very intriguing interplay of noise, capacity, and memorisation on the Lipschitz behaviour, which highlights, quite uniquely, the intriguing benefits imparted by pre-paaramttrrisation.
20
% labola shuthel
23
100
1500
40
60
80
90
550
20
100
10
14
16
18
40
10
12
16
18
70
40
whith
width
Figure 10: Lower Lipschitz values (left) and the test loss (right) for CNN models at various levels of label shuffling, trained on CIFAR-10. More details in Appendix S2.6.16.
6 RELATED WORK
Theoretical works on the Lipschitz constant. Recent theoretical interest in the Lipschitz constant of Neural Networks has been revived since Bartlett et al. (2017) described how margin- based generalisation bounds are linearly dependent on the Lipschitz constant. Other Lipschitz constant- based generalisation bounds (Chuang al., 2021; Munn et al., 2023) were later developed. Bubeck
8

---

Published as a conference paper at ICLR 2024
& Sellke (2021) have also conjectured the phenomena of smooth interpolation in over- vee-parametrised networks with the underlying Lipschitz continuity of the network. Since generalisation bounds and robustness guarantees (Weng al., 2018) are upper bounded by expression containing the true Lipschitz, extensive research has been done in the field of its accurate estimation (Virmaux & Scaman, 2018; Jordan & Dimakis, 2020; Gómez et al., 2020; Fazlyab al., 2019; Wang al., 2022), but this is still an ongoing pursuit as more accurate estimates typically come at high computational costs.
Practical applications. On the practical side, this direction can be divided into three sub-categories. (i) Generative modelling: The Lipschitz constant has been utilised to stabilise Recurrent Neural Networks (Erichson al., 2021) and Generative Adversarial Networks (GANs) (Zhou al., 2019; Petzka et al., 2017; Miyato et al., 2018; Qin et al., 2018; Zhou et al., 2018; Cui & Jiang, 2017). (fi) Certificates for adversarial robustness: Enforcing certain Lipschitz constraints has proved useful in certifying robustness guarantees for fully-connected Neural Networks (Anil et al., 2018; Gouk et al., 2021; Li et al., 2019) and Convolutional Networks (Cissé et al., 2017; Wang et al., 2021; Singla & Feizi, 2021; Yu et al., 2021), as well in other areas like Equilibrium Networks (Revay et al., 2020). In order to certify certain Lipschitz values, one can simply modify internal layers so that the resulting network is C-Lipschitz (Kim et al., 2020), or
more general parametrisation (Meunier et al., 2022; Prach & Lampert, 2022; Araujo et al., 2023; Wang & Manchester, 2023). (iii) Lipschitz as a regularisation: Another way to ensure model robustness is through Lipschitz-based regularisation techniques (Terjék, 2019; Bungert et al., 2021; Pauli et al., 2021; Tsuzuku et al., 2018; Ono et al., 2018; Leino et al., 2021). Yet, as we have seen in the DD section, there is an inherent Lipschitz regularisation already at play in Neural Networks.
Recent works with similar focus. Concurrent with the release of our work, Gamba et al. (2023) have also noted the connection between Lipschitz constant and Double Descent (Belkin et al., 2019), albeit by tracking only an estimate of the Lipschitz. Likewise, in the context of Double Descent and evolution during training, Munn et al. (2023); Dherin et al. (2022) explored a quantity called Geometric Complexity, which is similar to our notion of the Cavg norn and the estimate of Gamba et al. (2023). But, as matter of fact, such estimates are even looser than the local Lipschitz lower bounds, as can be seen in our results. Whereas, by considering the lower and upper Lipschitz bounds simultancously, our results reveal the behaviour of the effecttvee Lipschitz more faithfully. Besides, our focus is much more comprehensive as, for instance, we elaborate on the nature of effective Lipschitz (on unprecedented evaluations on ImageNet with ResNet50 and ViT) and uncover new intriguing insights into the Lipschitz behaviour in high-noise regimes.
CONCLUSION
Summary. In this work, we have presented comprehensive study of some intriguing behaviours of the Lipschitz constant of Neural Networks. We first explored the nature of the effective Lipschitz constant, showcasing the evolution study (and its marked deviation from the value at initialisation) and the fidelity of the lower bound. Then, we witnessed the implicit Lipschitz regularisation effect with width in the form of ceuule-Desceet-like we examined the effect of label noise on function smoothness and generalisation, spanning across a wide range of network capacities and noise strengths.
monoooootny in the Lipschitz bounds. Finally,
What we could not touch upon. In Appendix S3, we replicate most of the experiments shown in the main part for other model classes and datasets, ensuring the consistency of presented results. Additionally, we also discuss the effect of the choice of loss (between Cross-Entropy and MSE), optimisation algorithm (SGD versus Adam), depth of the network, explicit regularisers such as weight decay and dropout, and the number of training samples.
Limitations & future research directions. One potential avenue for investigation would be to provide a detailed theoretical analysis for our uncovered findings which, although fell beyond the current scope, would be highly relevant (e.g. generalisation bounds based on the effective Lipschitz). It would also be rather interesting to explore the effect of large learning rates through the lens of the effective Lipschitz constant. Lastly, examining our findings outside of computer vision tasks - e.g.. in the language domain, in the framework of reinforcement learning would be fruitful endeavor.
All in all, we hope that this work inspires further research on uncovering and understanding the characteristics of the Lipschitz constant.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We would like to thank Thomas Hofmann, Bernhard Schölkopf, and Aurelien Lucchi for their useful comments and suggestions. We are also grateful to the members of the DALab for their support. Sidak Pal Singh would like acknowledge the financial support from Max Planck ETH Center for Learning Systems.
REFERENCES
Ben Adlam and Jeffrey Pennington. The Neural Tangent Kernel High Dimensions: Triple Descent and Multi-Scale Theory of Generalization, 2020.
Cem Anil, James Lucas, and Roger Baker Grosse. Sorting out Lipschitz function approximation. In International Conference on Machine Learning, 2018.
Alexandre Araujo, Aaron J. Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. Unified Algebraic Perspective on Lipschitz Neural Networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
URL
Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN, CoRR, abs/ 700.007777 2017. URL http::htpt//etee wwwpwwwwwwwwwoaaaa/aoo//aaaaaaaa 17001 07875.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019.
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally- norirallly--ommlizzedd margin bounds for neu- ral networks. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1240-62499 2017. URL hht.haaahhhaaeeaaaaa 2tt1:///a22222222221112145553333
neurips. cc/ html..
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(49):30033-3007) 2020.
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203- 248, 2021.
Mikhail Belkin, Daniel J. Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116: 15849 15854, 2019.
Louis Béthume. Thibaut Boissin, Mathieu Serrriier, Franck Mamalet, Corentin Friedrich, and Alberto Gonzalez Sanz. Pay attention to your loss: understanding misconceptions about I-Lipschitz neural networks. Advances in Neural Information Processing Systems, 35:20077-20091. 2022.
Sébastien Bubeck and Mark Sellke. A Universal Law of Robustness via Isoperimetry. Journal of the ACM, 70:1 18, 2021.
Leon Bungert, René Raab, Tim Roith, Leo Schwinn, and Daniel Tenbrinck. CLIP: Cheap Lipschitz Training of Neural Networks. In Scale Space and Variational Methods in Computer Vision, 2021.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Ching Yao Chuang, Youssef Mroueh, Kristjan Greenewald, Antonio Torraba, and Stefanie Jegelka. Measuring Generalization with Optimal Transport. Advances in Neural Information Processing Systems, 34:8294-8300 2021.
10

---

Published as a conference paper at ICLR 2024
Moustapha Cissé, Piotr Bojanowski, Edouard Grave, Yann N. Dauphin, and Nicolas Usunier. Parseval Networks: Improving Robustness to Adversarial Examples. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning. ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 854 863. PMLR, 2017. URL http: htttt::/prrcceeiiiie ngs ml www..peess////ciiesseess html.
Shaobo Cui and Yong Jiang. Effective Lipschitz constraint enforcement for Wasserstein GAN training. 2017 2nd IEEE International Conference on Computational Intelligence and Applications (ICCIA), pp. 74-78, 2017.
Benoit Dherin, Michael Munn, Mihacla Rosca, and David Barrett. Why neural networks find simple solutions: The many regularizers of geometric complexity. Advances in Neural Information Processing Systems, 35:2333-2349, 2022.
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient Descent Provably Optimizes Over-parameterizze Neural Networks. In 7th International Conference on Learning Represen- tations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
https: / wwppreeeeeeeeeeeee eee..w..eee net forum? dd=$1 ek eK3109Y0.
N. Benjamin Erichson, Omri Azencot, Alejandro F. Queiruga, Liam Hodgkinson, and Michael W. Mahoney. Lipschitz Recurrent Neural Networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https:://openree ew net/ /tt//forummm/// -
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George J. Pappas. Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks. In Neural Information Processing Systems, 2019.
Herbert Federer. Geometric Measure Theory, chapter 3.1.1, pp. 209. Springer Berlin, Heidelberg, 1 edition, 1996.
Matteo Gamba, Hossein Azizpour, and Märten Björkman. On the Lipschitz Constant of Deep Networks and Double Descent. CoRR, abs/2301. 2023. doi: 104855WARXX.2230.22300 URL https:////// //tp:///oiii///ooo
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma.
Neural computation, 4(1):1-58, 1992.
Fabian Latorre Gómez, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of Neural Networks via sparse polynomial optimization. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL /tttps:://peerevvviii net forum? id=rJe4 xSFDB.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning, chapter 9.1, pp. 329, MIT Press, 2016. http: /www. dwwpleerninggooeeecco org.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: /ttp///arvvvv/.////////e.///.av. org/ als /1412.111100 6572.
Henry Gouk, Fibe Frank, Berhard Pfahringer, and Michael J. Cree. Regularisation of neural networks by enforcing Lipschitz continuity. Machine Learning, 11012):393-416, Feb 2021. ISSN 1573-0565. doi: 10.10077.1199444000-0559.... URL s10994-
Sam Greydanus. Scaling down Deep Learning. CoRR, abs/2011.14439, 2020. URL https: wex.vv.org/bbs...... 22111.11111111 14439.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
11

---

Published as a conference paper at ICLR 2024
Todd Huster, Cho- Yu Jason Chiang, and Ritu Chadha. Limitations of the Lipschitz constant defense against adversarial examples. CoRR, abs/1807.09705, 2018. URL http:///axixx org/abs/ 10s/abs/1801 1807. 09705.
Yerlan Idelbayev. Proper ResNet implementation for CIFARIO/CIFARION in PyTTorch. https: O. Accessed: 2023-06-17.
//github.... wwt.//o///aaaaaaac http//aaaaaaaaereeeee
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Matt Jordan and Alexandros G Dimakis. Exactly Computing the Local Lipschitz Constant ReLU networks. Advances in Neural Information Processing Systems, 33:7344-73553 2020.
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The Lipschitz Constant of self-Attention. In International Conference on Machine Learning, 2020.
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. 2009.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial Machine Learning Scale. In 5th International Conference on Learning Representations, ICIR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL /tttps://openzeview net / Erruoorumii.. 4 4Kgx..
Jachoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study, 2020.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-Robe Robbust Neural Networks. In International Conference on Machine Learning, pp. 6212-6222. PMLR, 2021.
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jörn-Henrik Jacobsen. Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks. Advances in neural information processing systems, 32, 2019.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Laurent Meunier, Blaise Delattre, Alexandre Araujo, and Alexandre Allauzen. dynamical system perspective for Lipschitz neural networks. In International Conference on Machine Learning, pp. 15484-15500. PMLR, 2022.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral Normalization for Generative Adversarial Networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https:
httttps://peezeeieeee wwtp//pweweee.eee///p/ee net. /aet/ffoot forum? 1== QRgziT-
Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Mem- orization and generalization under lazy training. The Annals of Statistics, 2065):2816-2847, 2022.
Michael Munn, Benoit Dherin, and Javier Gonzalvo. A margin-based multiclass generalization bound via geometric complexity, 2023, URL http::::///peneeee.e.ttttt//// forrmm id= wtwp::/eewwxeeeeerreeeeeeeeeaea. wttpaaaseoppooeeeeeeeeeeeeeeeeee 5D (#2Fprofi ot Benoit_Dherinil.
Beno
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:://penzeeieer net/ Forum?
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal Regularization can Mitigate Double Descent. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https:// openreview. wwtprriwwwweeetteeeeeeeem wid=mr7fooodpd- oe
12

---

Published as a conference paper at ICLR 2024
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioamnis Mitliagkas. A Modern Take on the Bias- Variance Tradeoff Neural Networks. CoRR, abs/1810.08591, 2018. URL http:// aariiv org/ abs///b///// /0s//1111 1810 08591.
Hajime Ono, Tsubasa Takahashi, and Kazuya Kakizaki. Lightweight Lipschitz Margin Training for Certified Defense against Adversarial Examples. CoRR, 10.00800,,000,,,,, 2018. URL http:
//arxiva //aaxii.orggbbba....... 1811 08080.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. Training Robust Neural Networks Using Lipschitz Bounds. 2021 American Control Conference (ACC), pp. 2595-2600, 2021.
Henning Petzka, Asja Fischer, and Denis Lukovnikov. On the regularization of Wasserstein GANs. CoRR, 71011009988999 2017. URL http::t/a.x.....gegeeeooo/////// http:/bb///1/ /1009 08894.
Bernd Prach and Christoph H Lampert. Almost-Orthogonal Layers for Efficient General-Puupposs Lipschitz Networks. In European Conference on Computer Vision, pp. 350-365. Springer, 2022,
Yipeng Qin, Niloy Jyoti Mitra, and Peter Wonka. How Does Lipschitz Regularization Influence GAN Training? In European Conference on Computer Vision, 2018.
Max Revay, Ruigang Wang. and Ian R. Manchester. Lipschitz Bounded Equilibrium Networks. CoRR, abs/2010.01732, 2020. URL https: / /ttx/ixxvvv////////////// wwexiv.org/aaa /ab/ /2100.011..0000210 01732.
Maxim Samarin, Volker Roth, and David Belius. Feature learning and random features in standard finite-width convolutional neural networks: An empirical study. In Uncertainty in Artificial Intelligence, pp. 1718-1721 1727. PMLR, 2022.
Sidak Pal Singh, Aurélien Lucchi, Thomas Hofmann, and Bernhard Schölkopf. Phenomenology of Double Descent in Finite- Width Neural Networks. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https::////.... wpwp//wwwe..eeeeeeeppp/p. net fooum? i d= T
Sahil Singla and Soheil Feizi. Skew Orthogonal Convolutions. In International Conference on Machine Learning, pp. 9756-9766. PMLR, 2021.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http: /tattp:///axivvi www.orrggoooooooo / 1312. 6199.
Dávid Terjék. Adversarial Lipschitz Regularization. In International Conference Learning Representations, 2019.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-Margin Training: Scalable Certifica- tion of Perturbation Invariance for Deep Neural Networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL WtRLtttts:///oooo http:::::/ppppppppppssee wtw.zcceeeinggseeeiip.... cc/paper/201s 2018 htte//il////////// oat.4//0000.acccccccc..eeeeeeeee
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL https: http://oooeoeiceccco/oo/oo igg. nerss.neurii neurips d54e99a6c03 955.9996666007666666555555553339 655444995e565555eeee wwweeeecee--eppeeeeeeee Pbw-eabrr..ppp..e pdf.
Ruigang Wang and Ian Manchester. Direct Parameterization of Lipschitz- bounded Deep Networks. In International Conference on Machine Learning, pp. 36093-36111110 10. PMLR, 2023.
Yizhou Wang, Yue Kang, Can Qin, Xu, Huan Wang, Yulun Zhang, and Yun Fu. Adapting Stepsizes by Momentumized Gradients Improves Optimization and Generalization. CoRR, abs/2106.1 15114 2021. URL hwwph:tttt//rtteeeee wwwps/wwworrr/oeoooeee 021 11514.
13

---

Published as a conference paper at ICLR 2024
Zi Wang, Gautam Prakriya, and Somesh Jha. A Quantitative Geometric Approach to Neural-Netwond Smoothness. Advances in Neural Information Processing Systems, 35:34201-34215, 2022.
Tsui-Wei Weng, Huan Zhang, Pin-Yu Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the Robustness of Neural Networks: Extreme Value Theory Approach. In International Conference on Learning Representations, 2018. URL https:
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The Marginal
Value of Adaptive Gradient Methods in Machine Learning. In NIPS, 2017.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic Perturbation Analysis for Scalable Certi- fied Robustness and Beyond. Advances in Neural Information Processing Systems, 33:1 2020.
Tan Yu, Jun Li, Yunfeng Cai, and Ping Li. Constructing Orthogonal Convolutions in an explicit manner. International Conference on Learning Representations, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Zhiming Zhou, Yuxuan Song, Lantao Yu, and Yong Yu. Understanding the effectiveness of lipschitz constraint in training of gans via gradient analysis. CoRR, 0tss/1807.00755 2018. URL http:
//arxiv. org/ hts//bbs/110000 1807. 00751.
Zhiming Zhou, Jiadong Liang. Yuxuan Song, Lantao Yu, Hongwei Wang, Weinan Zhang, Yong Yu, and Zhihua Zhang. Lipschitz Generative Adversarial Nets. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7584-7593. PMLR, 2019, URL httt:::/proceeeingg.. mlr. p.r.ppress/v99 zhoul 9c. html.
14

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
S1 Table of notations
16
$1.1
Basic notations
16
$1.2
Lipschitz notations
16
S2 Experimental setup
16
$2.1
Local Lipschitz estimates vs. pairs of points
S2.2
Upper bound calculation
................................
$2.3
Model descriptions
18
$2.4
Training strategy
19
$2.5
Learning rate schedulers
20
S2.6
Description of experimental settings
20
S3
Additional experiments
26
$3.1
Linearisation of Neural Networks and the effect of training
26
S3.2
Using adversarially perturbed samples for the lower Lipschitz bound computation
26
Evaluating Lipschitz bounds out-of-distribttion (OOD) samples
S3.4
Evaluating the tightness of theoretical bound
$3.5
Lipschitz evolution of Vision Transformer subset of ImageNet
28
S3.6
Estimation of the potential error of evaluating lower Lipschitz bound by consid-
cring subsamplc of ImageNet
28
$3.7
The convex combination study for ResNet18
29
$3.8
Lipschitz evolution for other settings
29
S3.9
Lipschitz Double Descent for other settings
32
$3.10
More experiments on the Lipschitz constant in the Double Descent setting
34
S3.11
Bias Variance trade-off off evaluation
34
S3.12
Double Descent for Lipschitz constrained networks
34
S3.13
Optimising the upper bound for the Variance
35
S3.14
ResNet50 upper bound more checkpoints
35
S3.15
Jacobian norm distributions for other models and datasets.
36
S3.16
Lower Lipschitz bound as regulariser
37
$3.17
Effect of the loss function: CE vs MSE
37
S3.18
Effect of the optimisation algorithm: SGD vs Adam
38
$3.19
Effect of depth
39
S3.20
Effect of the number of training samples
$3.21
Effect of dropout
41
S3.22
Effect of weight decay
41
53.23
Lower Lipschitz bound samples with correct and incorrect predicted labels
42
S4 Theoretical proofs
43
$4.1
Theoretical analysis of Lipschitz evolution
43
$4.2
Bias- Variane tradeoff
44
15

---

Published as a conference paper at ICLR 2024
S1
TABLE OF NOTATIONS
S1.1
BASIC NOTATIONS
Table S1: A table of basic notations.
Notation
Definition
C
Lipschitz constant
f or fo
Neural Network, function at hand
0 E Ω
Parameter vector
C IRP
Parameter space
D
Input/data vector
D+ C Rd
Input/data space and its neighbourhood
K
Number of function outputs/classes
Training set
S
Test set Loss function
$1.2 LIPSCHITZ NOTATIONS
Table S2: A table of Lipschitz constant notations.
Notation of the bound
Parameter space
Input space
Formula
True Lipschitz, Ciue Effective Lipschitz, Cp+ Lower Lipschitz, Clower Local Lipschitz
at epoch f, i.e. 0f x E dom(s) D+ x XES E domn(s
SUPxedom(f) V x)]
at epoch f, i.e. or at epoch t, i.e. of at epoch I, i.e. or
SUPxED- V (0' x)
V f (0' x)]
supxES
[ ( x)]
Average, Cavg
at epoch i, i.e. o² at epoch f, i.e. 6²
XES
S ExES
VxJ x)|
Alt. lower, Calltower
x,y E S
sup SuPxyeSxxyy 11 x)= y)ll x-
Adversarial lower Adversarial alt. lower
at epoch t, i.c. at epoch i.c 0²
x E S
supxEs
V x x)
[ x) 1(0" xte)
x
supxeS
e
S2
EXPERIMENTAL SETUP
This section contains comprehensive details on the experiments in the paper - this includes summary of our strategy for Lipschitz upper bound calculation, models' architecture descriptions, hyperparameters and optimisation strategy choices for every experimental section in the main and supplementary parts of the paper. We also release our code GitHub for further reproducibility and transparency.
In short, we benchmark our findings in wide variety of settings, with different choices of (a) architec- tures: fully-connected networks (FCNs), convolutional neural networks (CNNs), Residual networks (ResNets) and Vision Transformers (VIT); (b) datasets: 11FAR-10 and CIFAR- (Krizhevsky, 2009), MNIST, MNISTID (Greydanus, 2020) (a harder version of usual MNIST), as well as ImageNet; (c) loss functions: Cross -ottroy (CE) and Mean-Squared Error (MSE) loss. Unless stated otherwise, the results the main paper are based on stochastic gradient descent with CE loss and the metrics have been averaged over 4 runs. All plots with shaded regions represent
16

---

Published as a conference paper at ICLR 2024
uncertainty of = standard deviation from the mean, which is computed across different seeds. When semi tami-transparent dotted lines are shown, the solid line represents the mean over seeds and each dotted line depicts data from individual seeds.
$2.1 LOCAL LIPSCHITZ ESTIMATES PAIRS POINTS
As mentioned in Section 2, another way to lower bound is to consider Definition 2.1 and restrict the supremum computation to the train set. essence, we want to compare the following lower bound estimates:
f - fo(y)]
Clower sup V/ellll XES
and
Calt.lower
sup x.yES
X y
These bounds only converge when the considered set includes the whole function domain. Therefore is not trivial to say which bound is better when a numerical estimation on a subset performed.
To address this issue, designed simple experiment where computed Clower and Caltlower for an FCN ReLU network from Section 3.1 for several training epochs. The results of this experiment, displayed in Table S3, provide evidence for the fact that the Clower estimate is tighter than Calrlower-
Table S3: Comparison of two Lipschitz lower bound estimates. Computed for seed.
Epoch
Clower
Calt. lower
0
0.369
0.165
1 000
1.336
0.865
000
3.762
2.752
3 000
5.775
4.257
4 000
7.142
5.120
5 000
7.974
5,591
000
9.928
6.361
50 000
19.390
8.840
S2.2 UPPER BOUND CALCULATION
We start by describing our approach to computing the upper bound of the Lipschitz constant, inspired by the Aut algorithm introduced by Virmaux & Scaman (2018). As briefly discussed in the main part of the paper (Section 2), we simply multiply per-layer Lipschitz bounds. For network fe with L layers, defined as fe == (()) a f(1-1)) o ...o f(1), where is 1 I-Lipschitz non- non-linear activation function, the upper bound looks as follows:
C S
II
sup Edom (F()
V/ n ff
S II sup V of =: Cupper
More pedantically,
this by using Theorem 2.1 and applying the chain rule:
C= sup xEdom(fo)
||Vxfol==
sup xfdom(fo)
|V f(L V yun- f(b-))((-1)) p(b-1)
V (2)) x
11 f(D)
VV (1)
sup (x)
sup (al())
sup xEdom(fe)
< suup
| f(unn ((1)
sup
A for lllei sup [ =: Cupper
(3)
where in the last line consider the unconstrained supremum.
Linear operations. Each linear layer of the form (0) w x has Lipschitz constant |WO l|,, since the Jacobian of f(() is simply the weight matrix. Convolutional layers are also linear operators and therefore can be similarly expressed as a linear transformation (considering that perform proper flattening of the input image and reshaping in the end). According Goodfellow
17

---

Published as a conference paper at ICLR 2024
et al. (2016), equivalent linear transformations represented by doubly block Toeplitz matrices which only depend on kernel weights. At the same time, Batch Normalisation layers are also per- feature linear transformations and, thus, the upper bound can be calculated maximum across per-feature Lipschitz constants.
Activation functions. All activation functions that are used in this paper ReLU, Leaky ReLU with slope 0.01, max and average pooling are also at most I-Lipschitz and thus are considered 1-Lipschitz for the upper bound computation.
Residual layers. Residual layers of the form f(x) g(x) + where f.g R R and is
Cg-Lipschitz continuous, simply have a Lipschitz constant equal to Cj C. + One can trivially derive this using the definition of Lipschitz continuity and the triangle inequality:
[l - f(y) = llg(x) g(y) + x||
S (1g(x) x) - -(y))l ||| + lly - x||
(Triangle inequality)
I Cgllx yyll + ||x yll
= =C,, + +)][> - yll
Attention layers. According Kim et al. (2020), standard Attention layers are not Lipschitz continuous (or, in other words, have an unbounded Lipschitz constant) for unconstrained inputs. Therefore the upper bound introduced in Equation 2 not applicable. Due to this reason, we only compute the lower Lipschitz bound in all experiments with Transformers.
Remark on computational challenges. Since equivalent linear weight matrices for convolutional operations assume flat input, the dimensions of this matrix grow rapidly with increasing image size and channel depth. This results in large memory consumption, which we leveraged by converting this matrix into the s scipy sparse CSR format and using scciyy-. sparse. linall library compute the norm. We also found that standard pytorch implementation of 2-norm computation works rather slowly for large matrices. We have therefore implemented Power method to compute 2-norms for linear layers and batched Jacobian matrices, resulting in almost 10x speedup in some cases.
$2.3 MODEL DESCRIPTIONS
$2.3.1 FCN RELU NETWORKS
fully Connected Network with ReLU activations (or FCN ReLU for short) consists of a sequence of Linear layers with zero bias term, each followed by ReLU activation layer, the last layer included. When it is specified that FCN ReLU has a width of 256, there are only two linear transformations involved: first, from an input vector to hidden vector of size 256, and second, from hidden layer of size 256 to the output dimension. When a sequence of widths is given (i.e. FCN ReLU with widths 64,64), FCN has several hidden layers, sizes of which are listed from the hidden layer closer the input to the hidden layer closer to the output.
Remark the Dead ReLU problem. Since we ReLU the last layer's activation, outputs of the model can in some cases become zero-vectors, specifically in scenarios with classification using MSE loss. To address this issue we use a modified version of the FCN model for all MSE experiments the last ReLU activation is substituted with Leaky ReLU function with a negative slope of 0.01.
Table S4 shows list of FCN ReLU realisations with various hidden layer widths and depths and the respective number of model parameters. All models in this table are configured for the MNISTIDS! dataset.
$2.3.2 CNN NETWORKS
Our version of Convolutional Neural Networks (or CNNs for short) follows an approach similar to Nakkiran et al. (2020). We consider a 5-layer model, with 4 Conv-ReLU-MaxPPod blocks. followed by a Linear layer with zero bias. All convolution layers have x 3 kernels with stride=1, padding=l and zero bias. Kernel output channels for convolution layers follow the pattern [w, 2w, 4w, 8w),
MNISTID input image is vector of size 40.
18

---

Published as a conference paper at ICLR 2024
Table S4: Table of the number of parameters of FCN ReLU models of various widths and depths. configured for the MNISTID dataset.
Model name
Number of parameters
FCN ReLU 16 FCN ReLU
800
1,600
FCN ReLU 80
4,000
FCN ReLU 256
12,800
FCN ReLU 800
40,000
FCN ReLU 131072
6,553,600
FCN ReLU 64.64
7,296
FCN ReLU 64,64,64
11,392
FCN ReLU 64,64,64466
15,488
FCN ReLU 64,64,64,64,64
19,584
where w is the width of the model. Mcanwhile, MaxPooling layers have kernels of sizes [1, 2, 2, for the case of CIFAR-10S2 and [1, 2, for the case of MNIST This configuration shrinks the input image to single vector that is then passed to the last Linear layer, yielding the output vector of size 10.
Table S5 displays list of CNN realisations with various hidden layer widths and the respective number of model parameters. Since configurations for CIFAR-10 Krizhevsky (2009) and MNIST differ only in the MaxPooling layer size, the number of trainable parameters remains the same for both datasets.
Table S5: Table of the number of parameters of the CNN network of various widths.
Model name
Number of parameters
CNN 5
9,985
CNN 7
19,271
CNN 10
38,870
CNN 11
46,915
CNN
55,716
CNN 13
65,273
:
CNN 20
153,340
CNN 60
1,367,220
S2.4 TRAINING STRATEGY
We present experiments that compare models that have substantially varying number of parameters. To minimise the effect of variability training, we painstakingly enforce the same learning rate, batch size and optimiser configuration for all models in one sweep. While this choice makes our
52 CIFARR-00 datasct input image has shape 32 x 32 x 3.
MNIST dataset input image has shape 28 x 28 3.
19

---

Published as a conference paper at ICLR 2024
claims the behaviour of the Lipschitz constant stronger, now have the challenge of setting reasonable stopping criterion to manage variable convergence rates.
For model fe with parameter vector 0 and loss the training set C(O, after the end of each epoch we compute (oC(0,S)]l which we call gradient norm for simplicity. In all experiments, unless stated otherwise, we control model training by monitoring the respective gradient norm if reaches small value (ideally zero), our model has negligible parameter change (i.e. | 8 is small) or, in other words, has reached local minimum. By means of experimentation, we found that stopping models 0.01 gradient norm value gives good results for most scenarios.
Possible pitfalls. In most cases, during the course of training, the gradient norm at first relatively small (in the range of 10 to 10-3), then rapidly increases and then slowly decreases. our only stopping criteria is minuscule gradient norm, we may end up early stopping models right after a few epochs. To avoid this we also introduce minimum number of epochs that each model has train for.
S2.5 LEARNING RATE SCHEDULERS
This section thoroughly describes learning rate schedulers (LR schedulers for short) that we use in our experiments. Each scheduler modifies variable "/s which is coefficient that is multiplied by some base learning rate (i.e. learning rate at time step is 7/+ = 7 y, where vj is the base learning rate). Note that we perform scheduler updates at every parameter update (which happens several times per epoch), and the schedulers are aware of the dataset length and batch size to adapt to spoch-basee settings accordingly.
25rmmu20000SSep225 LR Scheduler (Figure Sla). This scheduler linearly scales the learning rate from a factor of 20,006 to for 20,000 updates. Next, the scaling coefficient drops by a factor of 0.75 every 25% of the next 10,000 epochs. Afterwards, the coefficient remains at the constant factor of 0. 0.4218755.
Cont100 LR Scheduler (Figure S1b). This scheduler continuously drops the scaling coefficient by a factor of 0.95 every 100 epochs.
1.0
1.0
3.0
22000
50000
70000
100000
125000
150000
175000 (X000
10000
.0300
00000
80000
100000
updiatss
updattes
(a) 25mmp200000sep225 LR scheduler
(b) Cont100 LR scheduler
Figure S1: Learning rate scaling coefficient % against updates for two different learning rate schedulers. In each case there are 10 updates per epoch.
$2.6 DESCRIPTION OF EXPERIMENTAL SETTINGS
This section presents a detailed description of each experimental setup. We also include theoretical Double Descent interpolation thresholds for Double Descent experiments, where in each equation n stands for the number of training samples, K for the number of classes and for the number of parameters in the model.
20

---

Published as a conference paper at ICLR 2024
S2.6.1 A SIMPLE TOY EXAMPLE TO DEMONSTRATE THE FIDELITY THE LOWER LIPSCHITZ BOUND (FIGURE 5)
For this experiment, we set our data domain to be D = 5-, and the three equally spaced multinomial Gaussians. Each Gaussian's mean 1.5 units away from the origin and has Σ Iz. We sampled 15 points from each Gaussian, resulting in a dataset of 45 points. The dataset with the true labels is depicted in Figure S2.
Cloex
Closs
Closx
-2
Figure S2: The dataset and the true labels.
For the classifier, chose an FCN ReLU Network with hidden layers of width 100. We optimised the model on Cross-Entropy loss with Gradient Descent and constant learning rate of 0.02 for 100,000 epochs. To compute the Lipschitz bounds, sampled 1,000,000 points on the [-5, 5|2 grid. Additionally, we also computed the Jacobian norms outside of the data domain, i.e. on the [-10, 10]² grid, which resulted in the same estimate of 144.194. The results for the local Lipschitz computation are shown in Figure $3.
51.0
Decision boundary
1365
Tecision beandsry
1355
75
1250
1065
5.0
66.0
80.5
53.5
000
4200
28.5
59.0
000
17.
-50
-2.
0.0
2.6
10.0
(a) Local Lip. for D [-5, 5]²
(b) Local Lip. for [- 10, 10)²
Figure S3: Local Lipschitz constants of f for various input domains.
21

---

Published as a conference paper at ICLR 2024
S2.6.2 DOUBLE DESCENT ON MNISTID, FCN RELU NETWORKS, GROSS-ENTROPE LOSS (FIGURE S12)
For this experiment, we trained a sweep of FCN ReLU models (see S2.3.1) with widths [16, 32, 64, 80, 96, 128, 256, 512, 1024, 2048, 4096, 8192. 16384, 32768, 65536, 131072] on MNISTID with batch size 512 using Cross-Entropy loss and SGD optimiser without momentum. We used Warmup20000Step25 LR scheduler (see 52.5) and a base learning rate of 0.005. We trained our models for at least 10,000 epochs and stopped each model when either 0.01 gradient norm is reached or when 300,000 epochs have passed. We trained 4 seeds for each run. The theoretical threshold for this scenario is
p. which corresponds to FCN ReLU 80 (4000 parameters).
Comment on the hyperparameter choice. In this experiment, we used a very small learning rate to smoothly fit both under- and peeammaraetrre models. Therefore we require a significant amount of training epochs to secure convergence for all settings.
Comment Figure S12. In the figure, the training loss uncertainty for models from width 8192 to 65536 is lower bounded by zero (since training loss cannot be negative) and therefore is depicted as a vertical line in the log-log plot.
S2.6.3 DOUBLE DESCENT ON MNISTID, FCN RELU NETWORKS, MSE LOSS (FIGURE S13)
This experiment depicts sweep of FCN ReLU models (see S2.3. with widths [16, 32, 64, 80, 96, 128, 256, 512, 1024, 2048, 4096, 8192 16384, 32768, 65536], trained on MNISTID with batch size 512 using MSE loss and SGD optimiser without momentum. We used Warmup20000Step22 LR scheduler (see S2.5) and a base learning rate of 0.001. We trained our models for at least 10,000 epochs and stopped each model when 0.01 gradient norm is reached when 200,000 epochs have passed. We trained 4 seeds for each run. The theoretical threshold for this scenario is at n K =3 p. which corresponds FCN ReLU 800 (40,000 parameters).
$2.6.4 DOUBLE DESCENT ON CIFAR-10, CNN NETWORKS, CROSS-ENTROPY LOSS (FIGURE S14)
For this experiment, we trained a sweep of CNN models with widths [5, 7, 10, 11, 12, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] on CIFAR-10$5 with batch size 128 using Cross-Entropy loss and SGD optimiser without momentum. We used a Cont 100 LR scheduler (see S2.5) and a base learning rate of 0.01. We trained our models for at least 500 epochs and stopped each model when 0.01 gradient norm is reached or when 5000 epochs have passed. We trained 4 seeds for each run. The theoretical threshold for this scenario is at n p. which corresponds somewhere between CNN 11 (46.915 parameters) and CNN 12 (55,716 parameters).
S2.6.5 DOUBLE DESCENT ON CIFAR 100 WITH 20 SUPERCLASSES, CNN NETWORKS, CROSS-ENTROPE LOSS (FIGURE 7)
For this experiment, we trained a sweep of CNN models with widths [5, 7, 10, 11, 12, 13, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] on CIFAR- 10 with 20 superclasses, as described by Krizhevsky (2009) with batch size 128 using Cross-Entrops
loss and SGD optimiser without momentum. We used Cont100 LR scheduler (see S2.5) and a base learning rate of 0.005. We trained our models for at least 500 epochs and stopped each model when 0.01 gradient norm is reached or when 15 000 epochs have passed. We trained 4 seeds for each run. The theoretical threshold for this scenario is at p, which corresponds to somewhere between CNN 11 (47 795 parameters) and CNN 12 (56 676 parameters).
S2.6.6 DOUBLE DESCENT ON MNIST, CNN NETWORKS, CROSS-ENTROPY LOSSS (FIGURR S15)
For this experiment, we trained sweep of CNN models with widths [5, 7, 10, 11, 12, 13, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] on MN with a fixed 10% label shuffling (i.e. the dataset the
5 *MNISTID has 4000 training samples.
"CIFAR-10 10 has 50,000 training samples.
86 "CIFAR-100 100 has 50 000 training samples.
MNIST has 60,000 training samples.
22

---

Published as a conference paper at ICLR 2024
same across all seeds and models) with batch size 128 using Cross-Entropy loss and SGD optimiser without momentum. We used a Cont100 LR scheduler (see S2.5) and a base learning rate of 0.01. We trained our models for at least 100 epochs and stopped each model when 0.01 gradient norm is reached or when 1000 epochs have passed. We train 4 seeds for each run. The theoretical threshold for this scenario is at & p. which corresponds to somewhere between CNN 12 (55,500 parameters) and CNN 13 (65,039 parameters). Note that the parameter count is different due to different input size.
S2.6.7 DOUBLE DESCENT ON CIFAR-IO IO, VISION TRANSFORMER (VIT) NETWORKS (FIGURE S16)
For this experiment, we trained sweep of ViT models with widths [3. 5, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 50, 100, 500J. The width is used as the last dimension of output tensor after linear transformation, as well the dimension of the FeedForward layer (we multiply it by 4 in this case). No dropout is used. The patch size is equal to 8, and we use 6 heads with 6 Transformer blocks. We used the vit pyt--pytorc Python package implementation.
All models were trained on CIFAR-10" with batch size 128 using Cross-Entropy loss and SGD optimiser without momentum. We used Step LR scheduler (see S2.5) and base learning rate of 0.05, We trained our models for at least 2,000 epochs and stopped each model when 0.01 gradient norm is reached or when 10,000 epochs have passed. We train seeds for each run. The theoretical threshold for this scenario is at n R which corresponds to somewhere near VIT 5 (49,099 parameters).
Remark. Since the Attention layers are not Lipschitz continuous (Kim al., 2020), or, rather, the upper bound on the Lipschitz constant does not exist in Rd, we only present the results for the lower Lipschitz bounds. In order to provide proper upper bounds, modification to Attention layers are required, as described in detail by Kim et al. (2020).
$2.6.8
LIPSCHITZ BOUNDS EVOLUTION, FCN RELU, MNISTID WITH CONVEX COMBINATIONS (FIG. 1)
To showcase Lipschitz constant evolution we trained 4 FCN ReLU 256 with different seeds on the MNISTID dataset with batch size 512 for 83,000 epochs. Models were trained using Cross-Entropy loss and SGD optimiser with base learning rate of 0.005 and Warmup20000Stp25 LR scheduler (see S2.5). Each model achieved gradient norm of 0.01 up to 2 significant figures. Each epoch consists of 8 parameter updates.
For this scenario, we empirically defined the stable phase to begin from epoch 2500 (or after 20,000 updates). The slopes for the upper, lower, and average Lipschitz bounds are: 0.59, 0.46 and 0.44 respectively and are computed by examining the slope coefficient of a linear regression model fitted to the corresponding values in the log-log scale. The R values of the fit for the upper, lower, and average Lipschitz bounds are 0.9955, 0.9986 and 0.9980 respectively.
To compute the lower bound on convex combinations of samples from MNISTID constructed set S which contains: (a) training set $ - 4000 samples, (b) test set 5' - 1000 samples, (c) convex combinations Ax; + (1 A)x, from S 100,000 samples for each À = (0.1, 0.2, 0.3, 0.4, 0.5). and (d) convex combinations Xx; + (1 - X)x; from S - 100,000 samples for each À = {0.1, 0.3, 0.4, 0.5]. Altogether this makes S contain 1,005,000 samples.
S2.6.9 LIPSCHITZ BOUNDS EVOLUTION, RESNET50, SUBSET OF 200,000 IMAGENET SAMPLES (FIGURE 2)
For this experiment, we trained 3 ResNet50 models with different seeds for 90 epochs on full ImageNet with batch size 256, using Cross-Entropy loss and SGD optimiser with momentum of 0.9, weight decay of 0.0001 and base learning rate 0. We also used LR decay scheme where the learning rate is decreased 10 times every 30 epochs. We then evaluated lower Lipschitz bounds for epochs [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] on fixed random subset of 200,000 images from the ImageNet training set. During Lipschitz evaluation, all training samples are resized to 256 x 256 x 3. then center-cropped size 224 x 224 x 3 and then normalised using mean [0.485, 0.456, 0. 0.40
"CFFAR-1 has 50,000 training samples.
23

---

Published as a conference paper at ICLR 2024
and std [0.229, 0.224, 0.225]. During training, training samples randomly resized and cropped to 224 x 224 x 3 and then normalised using the same mean and std.
For this scenario, empirically defined the stable phase to begin from epoch 60. The slopes for the upper, lower, and average Lipschitz bounds are: 7.32. 0.49 and 0.48 respectively and are computed by examining the slope coefficient of a linear regression model fitted to the corresponding values the log-log scale. The R values of the fit for the upper, lower, and average Lipschitz bounds are 0.8441, 0.9718 and 0.8774 respectively.
10 DISTRIBUTION OF THE NORM OF THE PER-SAMPLE JACOBIAN FOR RESNETIS TRAINED ON IMAGENET (FIGURE S8)
For this experiment we first evaluated the norms of the Jacobian matrices (see 2.1) of ResNet18 for each sample of ImageNet. We took pretrained ResNet18 from pytorch hub. We then constructed another dataset, which took a mean of all possible pairs of 1,000 ImageNet samples with the highest Jacobian norm from the previous calculation, and evaluated the distribution once more the new dataset.
S2.6.11
VARIANCE UPPER BOUNDS AND BIAS- VARIANCE TRADEOFF (SECTIONS AND S3.11)
For this study used the same models that we have trained for the Double Descent MNISTID using FCN ReLU networks trained with MSE setting (see S2.6.3).
To compute variance bound estimates (see Eq. Var bound 1) in Figure 8, all expectations and variances are computed as their respective unbiased statistical estimates over 4 seeds. C is estimated as the norm of the average Jacobian among seeds the training
C sup xED
|x sup xED
V <lfo ()]]
sup | (xx c)]l xED
4
1
2 sup xE3
~ sup
(Vxfo(x(
(5)
xES
4
S2.6.12 EFFECT OF THE LOSS FUNCTION ON THE LIPSCHITZ CONSTANT (SECTION S3.17)
For this study we used the same models that we have trained for the Double Descent on MNISTID using FCN ReLU networks trained with Tross-Entropy setting (see $2.6.2) and with MSE setting (see S2.6.3). We plotted the evolution for the first 83,000 epochs for all models.
12.6.13 EFFECT THE OPTIMISATION ALGORITHM ON THE LIPSCHITZ CONSTANT (SECTION S3.18)
For this study, used the same models that have trained for the Double Descent on MNISTID using FCN ReLU networks trained with Cross-Entropy setting (see S2.6.2), as well as a set of 4 additionally trained FCN ReLU models with various seeds that were optimised with standard pytorch Adam optimiser (3 = 0.9, 32 0.999). Each of these models was trained on MNISTID with Cross-Entropy loss, 0.005 learning rate and Warmup20000Step25 LR scheduler (see S2.5). Parameter vector was computed as concatenation of flattened layer weights at each layer.
In Figure $29a showcase models up to epoch 10,000, while in figure S29b models stopped 83,000 and 1,100 epochs for the SGD and Adam case respectively. In the former plot, both models achieved gradient norm of most 0.01 up to 2 significant figures the end of their training.
Comment on Figure S29a. We display training up to 10,000 epochs even though Adam reached low gradient norm much earlier due slower rate of SGD by 1,100 epochs SGD is still in the early training phase.
$2.6.14 14 EFFECT OF DEPTH OF THE NETWORK ON ITS LIPSCHITZ CONSTANT (SECTION 19)
For this experiment we trained 5 types of FCN ReLU models with increasing depth. In particualr, we considered FCN ReL.U 64; FCN ReLU 64,64; FCN ReLU 64,64,64; FCN ReLU 64,64,64 64,644644 64 and
24

---

Published as a conference paper at ICLR 2024
FCN ReLU 64,64,64,64,644 Each model was trained on MNISTID with batch size 512 using Cross- Entropy loss and the SGD optimiser, 0.005 learning rate and Warmup20000Step25 LR scheduler (see S2.5). We trained our models for at least 10,000 epochs and stopped each model when either 0.01 gradient norm is reached or when 300,000 epochs have passed. We trained seeds for each run.
For this scenario, we computed slopes for Lipschitz bounds starting from depth 2. The slopes for the upper, lower, and average Lipschitz bounds for trained networks are: 3.33, 2.03, 1.19 respectively and are computed by examining the slope coefficient of a linear regression model fitted to the corresponding values in the log-log scale. The It² values of the fit for the upper, lower, and average Lipschitz bounds are: 0.9749, 0.9483 and 0.8798 respectively. For networks at initialisation, slopes from depth 2 for the upper. lower, and average Lipschitz bounds are 0.30, -2.52 and -2.84 respectively.
S2.6.15 EFFECT OF THE NUMBER OF TRAINING SAMPLES ON THE LIPSCHITZ CONSTANT (SECTION S3.20)
For this experiment we trained 4 types of FCN ReLU 256 models on different sizes of MNIST ID: 4000, 1000, 500 and 100 training samples. Sampling was performed by taking a random subsample from the main dataset. Each model was trained with batch size 512 using Cross-Entropy loss and the SGD optimiser, 0.005 learning rate and Warmup20000Step25 LR scheduler (see S2.5). We trained our models for at least 10,000 epochs and stopped each model when either 0.01 gradient norm is reached or when 300,000 epochs have passed. We trained 4 seeds for each run.
16 EFFECT OF SHUFFLING LABELS (SECTION 5)
For this experiment, we trained sweep of CNN models with widths [5, 7, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 40] on CIFAR-10 with various amounts of shuffled labels (ar parameter): 0%, 10%, 20%. 30%, 40%, 50%, 60%. 70%, 80%, 90% and 100%. Each shuffle is incremental, meaning that all shuffles from a dataset with a smaller a are contained in the dataset with a larger a. For each dataset, subsets and shuffles are fixed among seeds. Each model was trained with batch size 128 using Cross-Entropy loss and the SGD optimiser, 0.01 learning rate and Co LR scheduler (see S2.5), where the minimum learning rate was limited to 0.01 0.001 le-5. We trained the models for at least 1 000 epochs and stopped each model when either 0.01 gradient norm is reached or when 20 000 epochs have passed.
Comment on the minimum number of epochs. In comparison to the similar Double Descent setup (see S2.6.4) we use larger number of minimum epochs in this experiment, since smaller models require more updates to escape the initialisation well, especially in the presence of label noise (see S2.4).
12. EFFECT OF DROPOUT AND WEIGITT DECAY (SECTIONS S3.21 AND S3.23)
For the following set of experiments, we used the approach of Idelbayev, who carefully implements the approach by He et al. (2016). We refer to the original paper and the code repository cited before for implementation details. The only difference in our experimental setup is the inclusion of dropout layers (for the weight decay scenario, we do not use dropout). A 2D version of the Dropout layer is inserted before each ResNet block (i.e. a group of layers with a skip connection). leaving the first Convolution layer and BatchNorm intact. We also add a ID Dropout layer before the last linear map. All dropout layers use the same probability p. We use the following values of p for different runs: [0.0, 0.1, 0.2, 0.25, 0.3, 0.4). For all Dropout experiments, use the default value of 1e-4 for weight decay and train all models for 500 epochs.
For the weight decay experiments, we use the original setup and only change the weight decay parameter. We used the following set of values: [0.0, 1c-4, 2e-4, 3e-4, 4c-4, 5e-4, 1e-3, 2.5e-3], All models were trained for 500 epochs.
25

---

Published as a conference paper at ICLR 2024
S3
ADDITIONAL EXPERIMENTS
S3.1 LINEARISATION OF NEURAL NETWORKS AND THE EFFECT OF TRAINING
Using the first order of the Taylor expansion
Neural Network f(x; 0), get the following linearisation: f(x; 0) ~ f(x; 0o) + (0 0o, (x)))))) To see the effects of training on the lower take the derivative w.r.t. imput of the expression above and compute
Lipschitz constant bound,
the 2-norm:
0²
sup [x](x;0]| XES
x sup [x (0 fo:
fx: 0o)i1
0x00
XES
0
sup
V I 01 + 0oll
sup xES
Ox00
/ 0b)1
xES
We compute the bound above for an FCN ReLU 256 network trained on MNISTID with CE loss (see Appendix S2.6.2). It is worth noting that even in this experiment with a small network (12,800 params) and small dataset (4,000 train points wih 10 classes, input dimension is 40), computing the second derivative becomes very expensive, as we have to evaluate a 10 x 12,800 x 40 tensor for all 4,000 train points (that is more than half a billion gradient evaluations). We therefore restricted our computation to a subset of 470 training points that we managed to compute given our time constraints. We compute the norm of this tensor in its matrix representation, where we flatten the dimension (for this example, we have a 128,000 x 40 matrix).
The results are as follows: the lower bound the last epoch (LHS) is 24.228 while the lower bound at initialisation is almost 65 times smaller: 0.369. The second derivative term turns out to be only 4.685, which shows that the final Lipschitz constant changes significanly during training (due to large parameter vector change).
Remark. The mean + std. of || 3xx00 fx; 0o) is 3.127 + 0.619, showing that the estimate is very similar for most training points. This behaviour is expected, as we the network has not yet trained and is smooth around the whole domain due the random initialisation.
02
S3.2 USING ADVERSARIALLY PERTURBED SAMPLES FOR THE LOWER LIPSCHITZ BOUND COMPUTATION
One way improve the lower Lispchitz bound estimate (see Equation 1) is consider adversarial perturbations of the input instead of the inputs themselves. For this experiment, we perturb input samples using a slight modification of a PGD attack (He et al., 2016; Kurakin al., 2017) with c 0.5, where the learning rate of 10.0 is decayed by factor of 0.95 for each step in the algorithm. We use 1,000 iterations of PGD for each sample. We also compute the following Lipschitz estimates:
Cloweree=0 sup
V [xfo(x)]l2;
x
Clower,=00.5
sup
Vx (x + +)]l2,
xES
[l + + - f6(x)112
sup
||E||2
xES
where is noise vector, generated by the PGD attack (lelll S e).
Table S6 shows the computed bounds for CNN models from the Double Descent experiment on CIFAR-10 (see Appendix S2.6.4) on one fixed seed. The results clearly show that adversarial perturbations do not always result in tighter lower bounds, and they do, the increase in the estimate not substantial.
A similar behaviour can be observed for other values of e. Figure S4 shows how close the Ckower bounds lie for different attack strengths, while the loss perturbed test values increases significantly.
S3.3 EVALUATING LIPSCHITZ BOUNDS FOR OUT-OF-DISTRIBUTION (OOD) SAMPLES
To study the effects of models from the MNSITID, CE Double Descent study (Appendix $2.6.2) and computed the Lipschitz
(OOD) samples on the Lipschitz constant, we took the
26

---

Published as a conference paper at ICLR 2024
Table S6: Lipschitz bounds for various CNN models, trained on CIFAR-IO. Adversarial examples were generated using PGD attack with 0.5.
CNN
CNN
CNN 10
CNN 20
CNN 30
CNN 40
Jowerr 148.29
633.68
756.37
172.15
123.61
106.35
1owerre=0.55
139.54
658.03
739.00
173.07
129.13
102.
118.21
507.00
601.16
140.54
102.74
86.84
(a) Lip. bounds on perturbed train samples
(b) Loss on perturbed test samples
Figure S4: Comparison of various Lipschitz constant bounds with loss with increasing hidden layer width, in the case of CNN networks on perturbed CIFAR-10 samples.
constant bounds OOD train samples, well test loss OOD test samples. To generate an OOD sample, we added standard Gaussian noise with scale r to the sample. The results are shown in Figure S5, which confirm that lower Lipschitz bounds do not change significanly when evaluated at O0D points.
Caper
Quer
Tox loss
Cuaer F-
Tort Loss 0.5
Text lots
Congore
Thain losa
Cargorer
panatstecs
(a) Lipschitz bounds on OOD samples
(b) Train and test loss on OOD samples
Figure S5: Comparison of various Lipschitz constant bounds with test loss with increasing hidden layer width, in the case of FCN ReLU networks OOD MNISTID samples.
S3.4 EVALUATING THE TIGHTNESS OF THE THEORETICAL BOUND
To compare the bounds derived in Appendix $4.1, we trained FCN ReLU model with 6 hidden layers (widths 100, 100, 80, 80, 60 and 60) on MNISTID with SGD using batch size 1,000 (4 updates per epoch). We also used a learning rate of 0.04 and Cont50 LR scheduler (similar Cont100, but the decay applies every 50 epochs, or every 200 updates in this case).
Figure S6 shows the results of the evaluation. We denote Bound and Bound follows:
2 disscrtee
Bound I(T) = O
10'+1 0'112 + (2))
1=
2 discrete (7) BryT Cx(6%)
Bound 2(T) -
where Cg Cddsccrtte (7)
. (0"....0 supxes Vof x)| denotes the Lipschitz constant with re- spect model parameters up checkpoint 7, estimated at the train samples.
su
27

---

Published as a conference paper at ICLR 2024
Cuper Cuarr
Caper
Cuae
Cuggera
Congao
12"1
10
10
10t
updates
cpdatees
(a) Lipschitz bounds
(b) Lipschitz after 1000 updates
Figure S6: Evaluation of the theoretical bounds on the Lipschitz evolution and comparison with the actual upper and lower Lipschitz estimates. Computed for FCN ReLU 100,100080,0066 trained on MNISTID with SGD with batch size 1,000 (4 updates per epoch).
The results show that our both bounds follow a trend similar to the other Lipschitz estimates. Moreover, at the beginning of training, our bound comes out be smaller than the upper bound estimate.
S3.5 LIPSCHITZ EVOLUTION A VISION TRANSFORMER ON SUBSET OF IMAGENET
In this experiment, I evaluate the evolution of lower Lipschitz bounds for the Vision Transformer a subset of ImageNet. As previously discussed, Attention layers do not have theoretical I Lipschitz upper bound and hence only present the lower and average Lipschitz bounds. For this experiment, a subset of 50 000 train points from ImageNet was taken and only one seed is considered due to computational and time limitations. used a Simple eeviiii T model from the v t. tt..yttorh package, where the patch size is set to 16, the last dimension after linear transformation is 384, depth is set 12, number of heads 6, and the MLP dimension 536. The model was pretrained on full ImageNet. Figure S7 shows the results, with comparison to ResNet50 bound on the same 50 000 sample subset.
C Clover bouaais value
10a
10
Cheeer, VIT
Cloesr, ResNet
Cong. VIT
Can ResNot
10
50
opoch
Figure S7: Lower Lipschitz bounds evolution for VIT and ResNet50 50 000 samples ImageNet subset.
S3.6 ESTIMATION OF THE POTENTIAL ERROR OF EVALUATING LOWER LIPSCHITZ BOUND BY CONSIDERING A SUBSAMPLE OF IMAGENET
Due to computational limitations, in the ResNet50 evolution experiment (see Section 3.2) evaluate the lower Lipschitz bound on a subset of ImageNet. This decision would naturally produce a weaker estimate of the Lipschitz constant, compared to the full dataset evaluation, raising concerns the representativeness the lower bound in the first place. Therefore we conducted a small investigation into the magnitude of potential emor due ImageNet subsampling for the ResNet case.
28

---

Published as a conference paper at ICLR 2024
In this analysis, took the distribution of Jacobian norms for pretrained ResNet18, evaluated for the whole ImageNet training dataset (see S2.6.10 for more details), and estimated the lower bound for various random subsets of computed norms. Results depicted in Table S7. According to the obtained statistics, doubling the subset size decreases the relative error by around 5%, suggesting that moderate errors be achieved for rather small subsets. These results motivated decision of using 200,000 as our subsample size - a plausible trade-off between computational burden and estimation accuracy.
Table S7: Estimates of the lower bound for trained ResNet18 the different subsets of ImageNet. Estimates are averaged over 1000 random subsets.
Subset size
Estimate
St.dev.
Percentage difference to true estimate
50,000
220.50
23.72
20.87%
100,000
234.95
23.49
15.69%
200,000
249.28
21.24
10.54%
300,000
257.02
18.85
7.76%
400,000
262.15
16.86
5.92%
S3.7 THE CONVEX COMBINATION STUDY FOR RESNET 18
In this experiment, we take the top 1, 000 samples that have the highest Jacobian norm, consider their convex combinations, and use that as basis to evaluate the lower Lipschitz bounds. In fact, in Figure S8, we show the entire distribution of norms for these "hard" convex combinations as well as the entire ImageNet training set.
Jarohian ou ImageNet
Jacobian norms
convex comtinations
0.045
0.000
50
100)
150
200
250
Jacobian borm value
Figure S8: Distribution of the norm of the per-sample Jacobian for pretrained ResNet18, computed on the entire ImageNet and 1,000,000 hard convex combinations on ImageNet (See Appendix 12.6.10 for more).
We find that while the distribution indeed shifts towards larger per-sample Jacobian norms for the hard convex combinations, the shift not even a multiplicative factor of 2 more. This shift pales in comparison to the upper bound which is over tens of orders of magnitudes higher. Overall, this strengthens our claim that the lower bound is much more faithful the effective Lipschitz value and can hence serve better to explore various phenomenon observed in over- parameterized neural networks. Lastly, similar distribution plots for other models and datasets can be found in Appendix S3.15.
S3.8 LIPSCHITZ EVOLUTION FOR OTHER SETTINGS
In this section, we present evolution plots for settings that were mentioned in Section 3.1. We start with evolution plots for FCN networks with MSE loss and then continue with CNN evolution CIFAR-I0 and MNIST. Table S8 shows the values of the corresponding slopes with linear regression R² metrics for each setup.
29

---

Published as a conference paper at ICLR 2024
Table $8: Estimates of the slopes and linear regression R metrics for the upper, lower and average norm Lipschitz bounds for various evolution plots.
Evolution plot
Slopes
R metric
FCN, MNISTID, CE loss (Fig. 1)
0.59, 0.46, 0.44 0.80, 0.62, 0.52
0.9955, 0.9986, 0.9980 0.9982, 0.9914, 0.9991
FCN, MNISTID, MSE loss (Fig. S9)
CNN, CIFAR-10, CE loss (Fig. S10)
0.22, 0.29, 0.29
0.9461, 0.9327, 0.9460
ResNet50, subset of ImageNet, CE loss (Fig. 2)
7.32, 0.49, 0.48
0.8441, 0.9718, 0.8774
From Table S8, one can clearly see how the slope for the upper bound is larger for some more complex models and datasets. Consequently, simple upper bound is an excessively loose estimator of the Lipschitz constant - despite its theoretical full input domain coverage, this estimator has little practical value due to excessive overestimation. As discussed in detail in Section 3.1, we therefore suggest paying close attention to the lower bound estimator. It would intriguing to see how tighter upper bound estimates compare to lower and upper bounds, but we leave this investigation for future work.
Cuger
Cuper
17.5
Cuener
Caner
15.
Cona
Canaar
12.5
C. Caltne
C valoe
10.0
7.5
Stable phane
10
255
20000
50000
75000
100000
129000
150000
170000
200000
10P
10
epodl
spoce
(a) Lincar scale plot
(b) Log-log log scale plot
Figure S9: Lipschitz constant bounds evolution for FCN ReLU 256. The model was trained on MNISTID using MSE loss and SGD optimiser. Results are averaged over 4 runs. Stable phase is considered to start after epoch 75,000. We took this model form the Double Descent experiment (see Appendix $2.6.3).
35000
Carper
10
Coper
39036
Chnoee
Gueer
Cang
Canpuam
10'
101
C
Stable uluee
Stable plater
10
01
2101
2.31
330
832
300
30
307
spoch
epoch
(a) Linear scale plot
(b) Log- log scale plot
Figure S10: Lipschitz constant bounds evolution for CNN 20. The model was trained on C-FAR-10 using Cross-Entropy loss and SGD optimiser. Results averaged over 4 runs. Stable phase is considered to start after epoch 240. We used the same setup as in the Double Descent experiment (see Appendix $2.6.4).
30

---

Published as a conference paper at ICLR 2024
Carper
10
Caper
Ciancr
Obair
30030
10
Stable pluss
33096
volun
007
Stahls
.8088
10
5000
100
200
300
430
300
700
307
10P
10P
<pochh
spoch
(a) Lincar scale plot
(b) Log-log scale plot
Figure S11: Lipschitz constant bounds evolution for CNN 20. The model was trained on MNIST with 10% labels shuffled using Cross- Cross-Entropy loss and SGD optimiser. Results are averaged over 4 runs. Stable phase is considered to start after epoch 100. We took this model form the Double Descent experiment (see Appendix S2.6.6).
31

---

Published as a conference paper at ICLR 2024
S3.9 LIPSCHITZ DOUBLE DESCENT FOR OTHER SETTINGS
This section showcases Lipschitz constant (left) and train / test loss (right) Double Descent plots for more model class and dataset settings.
Remark on Figure S/2: Like the test loss, the upper Lipschitz for FCN ReLU networks seems to continue increase after the second descent, which could potentially be tied the Triple Descent phenomenon (Adlam & Pennington, 2020), where the test loss shows another peak for x n². We leave this interesting observation for future research.
Remark on Figure S16: For the case of VIT models on CIFAR-10, we also plot the lower Lipschitz constant estimates for set of 1,000,000 CIFAR-10 convex combinations (denoted S**) to further show the fidelity of the lower Lipschitz bound, even in a Double Descent setting.
C. valui
Cuger Cheor Curgaoere
pattams
Test
paraate
10"
10
10
10P
10
30"
107
patamelles
Figure S12: Comparison of various Lipschitz constant bounds with train and test losses with increasing hidden layer width, in the case of FCN ReLU networks on MNISTID, Results are averaged over runs. More details about the networks and the training strategy are listed in Appendix $2.6.2.
C. vnltee
Cager
params
params
Oyner
Cargusen
Test less
Thain loss
11P
30P
10F
perameters
Figure S13: Comparison various Lipschitz constant bounds with train and test losses with increasing hidden layer width, in the case of FCN ReLU networks are averaged over runs. More details about the networks and the training strategy are listed in Appendix $2.6.3.
on MNISTID with MSE loss. Results
32

---

Published as a conference paper at ICLR 2024
101
107
Caalbo
params
Cuppe
Cunerr
1071
JAUSIE RO
Test loss Train Joes
10P
Cugaren
107
10"4
10
11f
petramelezs
Figure $14: Comparison various Lipschitz constant bounds with train and test losses with increasing hidden layer width, in the case of CNN networks CIFAR-10. Results averaged over 4 runs. More details about the networks and the training strategy are listed in Appendix S2.6.4.
10
101
pacuns
C-vllx
Cuper
1n
Cunver
10
Curgaver
10:3
Test Joee
Train Jue6
parameters
Figure S15: Comparison of various Lipschitz constant bounds with train and test losses with increasing model width, in the case of CNN networks on MNIST with 10% of labels shuffled with Cross- Entropy loss. Results averaged over 4 runs. More details about the networks and the training strategy are listed in Appendix $2.6.6.
Cyeer
101
Cyn
16
1071
C c0000
10
2012
Train loes
Test loee
10
10
117
107
307
perzmeeess
Figure S16: Comparison of various Lipschitz constant bounds with train and test losses with increasing parameter count, the case of Vision Transformer networks on CIFAR-10 with Cross- Enntropy loss. Results are averaged over 4 runs. More details about the networks and the training strategy are listed in Appendix $2.6.7.
33

---

Published as a conference paper at ICLR 2024
S3.10 MORE EXPERIMENTS ON THE LIPSCHITZ CONSTANT THE DOUBLE DESCENT SETTING
This section includes experiments, where we compute Lipschitz constant bounds for set of models from another study (Singh et al., 2022). Results are produced from training a series of fully connected networks on CIFAR-10 and MNIST with MSE loss. This solidifies our findings on Lipschitz's Double Descent trends.
2030
19C
2000
703
(a) Models trained on CIFAR-10
(b) Models trained on MNIST
Figure S17: Plot of Lipschitz constant bounds for fully connected networks with hidden layer, trained using SGD with MSE loss.
S3.11 BIAS- VARIANCE TRADE-OF EVALUATION
In Section 4, we showed the equation for the bias- variance trade-off for the expected test loss. We then proceeded with upper bounding the variance, ignoring the effect of bias. In Figure $18 we display the results of the empirical bias-variance decomposition of the test loss for the MNISTID Double Descent scenario (see Appendix $2.6.3 for more details). The plot reveals that the Double Descent shape is mostly governed by the variance term, whereas the bias is almost constant across widths.
Test Iee
Bise
Viriance
Figure S18: Bias- VarisVariance decomposition of the expected test loss.
S3.12 DOUBLE DESCENT FOR LIPSCHITZ CONSTRAINED NETWORKS
In this experiment, inspired by the work of Gouk et al. (2021), we replicate the Double Descent scenario with FCN ReLU networks on MNISTID, where we regularise the product of spectral norms of the weight matrices to at most C Cupper
We do this by renormalising each individual weight matrix spectral norm to be at most sup C Ceenstr
upper In order to preserve the expressivity of highly
constrained networks, we multiply network output logits by a temperature т, as described by Béthune et al. (2022). For upper 10, we use r = 10, for upper = 1, we use T = 40, and for no constraint 7 (i.e. no temperature).
To optimise the models, we used SGD with batch size 512 and LR 0.001, with a LR scheduler 1ont100. The results are shown in Figure S19. As expected, the test loss follows the Lipschitz constant bounds.
34

---

Published as a conference paper at ICLR 2024
Cuper ocattezz
Tel Ted lost Cheeh
Guars noart1i2
Cupah
Thst
Vedk
Tidk conrteus
(a) Lipschitz constant bounds
(b) Train and test error
Figure S19: Comparison of various Lipschitz constant bounds with train and test loss with increasing hidden layer width, in the case of Lipschitz-constrained FCN ReLU networks on MNISTID with different upper constraint.
S3.13 OPTIMISING THE UPPER BOUND FOR THE VARIANCE
As discussed in Section 4 (and more comprehensively in Appendix S4.2), the variance of the learned function is related the Lipschitz constant by following equation:
E x Varç ()) 3 (C' + +C |x||
3 (fr,(fo(O,())
(Var bound 1)
According to Figure 8, variance bounds are rather loose compared to the variance itself. We contribute this dif- ference to the large value of dataset radius E x~ ||x| which can potentially be optimised by choosing better x' in bound (Var bound 0). For this case, the optimal
bouadd Via bouadd
upper buzzl valla.
minimum for E x~ ||x - x'I1 is x' E x= [x] = X, which utilised to recompute the bound in Fig- ure S20.
In the case of MNISTID, the bound is only almost negligibly better due to x being close to a zero vector for this particular dataset. We leave further analysis of improving the upper variance bound tightness for future work.
Figure S20: Optimised variance bound com- pared with (Var bound and variance.
S3.14 RESNET5O UPPER BOUND ON MORE CHECKPOINTS
Since computing the Lipschitz upper bound is significantly less expensive than the lower bound for the case of ResNet50 evolution, we have ad- ditionally evaluated the upper bound on a finer set of checkpoints for seed to present more complete picture the upper bound evolution. According the results in Figure $21, the up- per bound slope after epoch 60 is 7.04 with 1?
16
C upper bouad value
10:00
10
60
0.9624, supporting the representativeness of our previous estimation.
16
C
30
15
25
30
355
40
45
50
00
65
30
85
90
opoch
Figure S21: Upper Lipschitz constant bounds evo- lution for ResNet50. More details in Appendix $2.6.9.
35

---

Published as a conference paper at ICLR 2024
S3.15 JACOBIAN NORM DISTRIBUTIONS FOR OTHER MODELS AND DATASETS.
In Section 3.2 we have shown a distribution of the norm of the per-sample Jacobian for pretrained ResNet18. Here we provide additional plots for other types of models and datasets. In particular, we showcase the distribution plots for FCNs trained on MNISTID with Cross-Eitrropy and MSE losses, CNNs trained on CIFAR-10 and MNIST with 10% label noise and, finally, ResNets on CIFAR-10 (we used pretrained models from Idelbayev). All norms are evaluated on the datasets used for training. Each dotted line represents the maximum norm, or, in other words, the lower Lipschitz bound estimate.
In comparison to just the lower Lipschitz bound estimate, the Jacobian norm distribution plot provides more information on the continuity of the function in the training domain. If the distribution has long right tail, like in the case of ResNets in Figure S26, the corresponding function has to be rather smooth in the vicinity of most samples, while being more vulnerable to drastic changes for smaller subset of inputs. It would be fascinating to see if the skewness of this distribution bears a connection to the difficulty of generating adversarial examples, but we leave this direction for future research.
0.12
MNISTID, CE, PCN
MNISTID, MSE FCN GE MNISTUD. MSE, FCN 256
IN CE, FCN 250
0322
6:30
Fesquency
0.0
08
Jacolsan
Jacobion
value
Figure S22: Distribution of the norm of the per-sample Jacobian for FCN ReLU 64 and FCN ReLU 256, trained on MNISTID with Cross-Entee Cooss-Entropy loss. See Appendix S2.6.2 for training details.
Figure S23: Distribution of the norm of the per-sample Jacobian for FCN ReLU 64 and FCN ReLU 256, trained on MNISTID with MSE loss. See Appendix S2.6.3 for training details.
1.05
CIRVR-1O, UNN
600
MNIST, CNN ? MNIST, CNN 20
CIRAR-1O UNN
[requesc)
feqquecc
0.15
6312
0.00
035
680
0.00
Jacabisn
Jacokoar
valae
Figure S24: Distribution of the norm of the per-sample Jacobian for CNN 7 and CNN 20, trained on CIFAR-10. See Appendix $2.6.4 for training details.
Figure S25: Distribution of the norm of the per-sample Jacobian for CNN 7 and CNN 20, trained on MNIST with 10% label noise. See Appendix $2.6.6 for training details.
36

---

Published as a conference paper at ICLR 2024
CIFAR-IE, ResNet CIFAR-10, ResNet
3equesas
0.33
0.02
0831
100
200
Jacobian value
Figure S26: Distribution of the norm of the per-sample Jacobian for ResNet 20 and ResNet 56, trained on CIFAR-10. We refer to Idelbayev for training details.
S3.16 LOWER LIPSCIITZ BOUND AS REGULARISER
Although it is arguably easier to use the upper Lipschitz bound regulariser due to its lower computational complexity, could not be the best choice for larger models, where compensating for the exponential increase in the upper Lipschitz estimate by the À hyperparameter might be tricky. In Figure S27, we show the results training an FCN ReLU network on MNISTID, while adding A Clower regularisation term. The Clower estimate is recomputed every epoch using the complete training set.
Although the computational efficiency of this approach leaves much to be desired, still see positive effect on the test loss, despite almost no change in the upper Lipschitz bounds.
Caper Am 1.
Capor L.00
Queer 6.)
O m 2200
Tox
0100
Taer
200
(a) Lipschitz constant bounds
(b) Train and test loss
Figure S27: Plot of Lipschitz constant bounds and train/test loss by training epoch for FCN ReLU network with width 256 trained MNISTID. Networks were regularised using various values of the hyperparameter.
S3.17 EFFECT OF THE LOSS FUNCTION: CE VS MSE
Surprisingly, training networks with MSE loss results in marginally lower Lipschitz bounds than in the case of Cross-Entropy, shown in Figure S28a. We contribute this behaviour the constraints that MSE imposes on the function output in the case of classification. Since in the MSE scenario an ideal model should output a zero vector with only one entry of value 1, model's outputs are restricted to unit vectors for the domain of training samples. At the same time, Cross-Entropy loss does not impose this constraint as output logits are implicitly Softmax-ed Figure S28b shows that applying Softmax to the output of the Cross Cross-Entropy network shrinks the Lipschitz constant dramatically.
37

---

Published as a conference paper at ICLR 2024
Capery Cross Eairops
Crocs ChonEntoop
Crose-ninup
Coeer Cronantrop Soctmox
Conaaren CrossEalaup MSE
Goner MSE
Capaaren
100
12
cpoci
opoch
(a) Lipschitz bounds comparison: Cross-Entropy (b) Lower Lipschitz bounds for CE (with and with- out Softmax) and MSE
MSE
Figure S28:
Lipschitz constant bounds evolution for FCN ReLU network with I hidden layer with 256 neurons, trained using Cross-Entrood and MSE. Both models trained MNISTID with SGD, using the same learning rate and I.R scheduler. Results are averaged over runs. More details in Appendix S2.6.12.
S3.18 EFFECT OF THE OPTIMISATION ALGORITHM: SGD VS ADAM
When network is trained using the Adam optimiser, Lipschitz constant bounds escalate dramatically compared to the results from SGD. This finding supports the fact that Adam finds solutions that generalise significantly worse, despite great training performance (Wilson al., 2017; Wang et al., 2021). Note that this trend remains even if we account for Adam's faster convergence, i.e. compare networks at their respective last epochs of training, which are not the same due various convergence rates (see Figure S29).
Capers Adato
-
Cuper Adam
Adbin
Cuerri Adam
Adam 3GD
Aclum
SGD
Ownr
caloo
801
epoci
spoch
(a) Lipschitz bounds evolution for SGD and Adam (b) Lipschitz bounds evolution for SGD and Adam at the same epoch
at the end of training
Lipschitz constant bounds evolution for FCN ReLU network with hidden layer with 256 neurons, trained using SGD and Adam. Both models were trained on MNISTID with Cross-Entropy loss, using the same LR and LR scheduler. Results are averaged over 4 runs. We end training when the gradient norm reaches the critical value of 0.01. More details in Appendix S2.6.13.
Figure $29:
We suggest that this behaviour can be explained by observing how far models travel from their initial parameters. Figure S30 shows the evolution of parameter distances (i.c. param_dist, 0 0'11 2/ where i iterates through saved model checkpoints), which has similar trend to Lipschitz bounds. In fact, we show that Lipschitz constant can be indeed expressed in terms of parameter distance in theoretical analysis in Section 14.1. We leave thorough exploration of this facet for future work. As a bonus we also show that parameter distance also exhibits Double Descent, Figure S31.
38

---

Published as a conference paper at ICLR 2024
-27
13211 talle
107
1074
Pazameter distanoe, Adam
Parameter datance, Adamt
Proameter distansee SCD
Parameter distance, SCD
107
spoch
(a) Parameter displacement evolution for SGD and (b) Parameter displacement evolution for SGD and Adam at the same epoch
Adam at the end of training
Parameter displacement evolution for FCN ReLU network with 1 hidden layer with 256 neurons, trained using SGD and Adam. Both models were trained on MNISTID with Cross-Entropy loss, using the same LR and LR scheduler. Results averaged over 4 runs. We end training when the gradient norm reaches the critical value of 0.01. More details are in Appendix S2.6.13.
Figure S30:
Parameter distance
3+307
params St
2:307
paranss
pazumetens
parametess
(a) Double Descent with Cross-Entropy loss
(b) Double Descent with MSE loss
Figure $31: Parameter distance the last epoch for models from the Double Descent MNIST1D setting with Cross-Entropy (Fig. S12) and MSE (Fig. S13) losses. More details are in Appendices S2.6.2 and S2.6.3.
$3.19 EFFECT OF DEPTH
To study how depth affects the Lipschitz constant of the network we trained 5 fully-commected networks MNISTID with the same learning parameters. According to Figure S32a, all Lipschitz bounds for trained models start to increase with each subsequent layer after 2 layers, following a trend close to power law - R² linear regression metrics are 0.9749, 0.9483 and 0.8798 for upper, lower, and average Lipschitz bounds respectively. The slopes for the corresponding Lipschitz bounds are 3.33, 2.03 and 1.19, indicating a superlinear trend.
An interesting fact is that the aforementioned trend for lower Lipschitz bounds does not hold for networks initialisation, both for the case of increasing depth (Figure S32b) and increasing width (Figure S34). Consequently, we see how the effect of feature learning gets manifested in the bounds of the Lipschitz constant and that looking solely initialisation (as in the style of the lazy regime (Chizat et al., 2019)) would be insufficient. To visualise this 'trend flipping' behaviour we also present evolution plots for the upper and lower Lipschitz constant bounds in Figure $33.
39

---

Published as a conference paper at ICLR 2024
100
Capser Ciater nang
C value
100
Coeauee
Cupter
108
Cuaser
Cassonm
5
number of hidden layers
namber of hiddee leyers
(a) Trained networks
(b) initialisation
Figure S32: Lipschitz constant bounds for FCN ReLU network with various number of hidden layer with neurons for parameters at initialisation and after training. Results are averaged over 4 runs. More details are in Appendix 12.6.14.
Cowrr, 5 hiedde layors
Caperr 5 hiddeen Inyers
10a
Cueer hidden layess
Cupper 4 hidden lngers
Cleerr 3 hiodlen layens
107
Cupper 3 bidden lngers
Coeari 2 hilddm layoms
Copeer 2 hidden lnyers
0 valuee
Coser, hidden layee
Ciitee
Caperr hidden lnyer
10
10P
10'
10P
10*
10
10P
107
10=
epoch
spoch
(a) Lower Lipschitz bound
(b) Upper Lipschitz bound
Figure S33: Lipschitz constant bounds evolution for FCN ReLU networks with various number of hidden layer with 64 neurons for parameters. Results are averaged over 4 runs. More details are in Appendix S2.6.14.
Capsr
166
Cineer
vallee
100
Figure S34: Lipschitz constant bounds for FCN ReLU network with increasing hidden layer width at initialisation. Results are averaged over 4 runs. Here we used models from the Double Descent experiment, details in Appendix S2.6.2.
40

---

Published as a conference paper at ICLR 2024
S3.20 EFFECT OF THE NUMBER TRAINING SAMPLES
Increasing the number of samples in the dataset results in corresponding sublinear increase in all Lipschitz bounds. Figure S35 shows the Lipschitz bounds for FCN ReLU 256 networks trained on various random subsets of MNISTID. Using linear regression we estimated the slope of upper, lower and average Lipschitz bounds to be 0.53, 0.37 and 0.36 respectively, and the R metries are 0.9680, 0.9932 and 0.9928, implying a strong sublinear trend in all Lipschitz bounds. These results suggest that as the number of samples increases, the complexity of the function rises to fit a larger set of points. It would be interesting to precisely tease out this behaviour in terms of relevant theoretical quantities, but we leave that for future work.
Cuper
Closer
Canyooon
vallue
C
10
.00
5001
1001
1000
uamber of samples
Figure $35: Lipschitz constant bounds for FCN ReLU network with hidden layer with 256 neurons trained for various subsets of MNISTID, Results are averaged over 4 runs. More details are in Appendix 12.6.15.
S3.21 EFFECT OF DROPOUT
Intuitively, increasing the probability value in dropout further regularises the model, which should result in lower Lipschitz bounds. To that this hold even for the Clower metric, we conduct an experiment with ResNet20 model, trained on CIFAR-10 10. We impute Dropout layers before each ResNet block (i.e. group of Convolution and BatchNorm layers that has a skip connection) and before the last Linear layer. The details of the experiment are described in Appendix S2.6.17. Figure S36 shows the results, which indicate that our lower bound metric indeed follows the expected decreasing trend with increasing dropout regularisation.
Cunir Canynans
300
valux
0.03
0.06
0.10
0.15
0.20
0.26
0.30
0.55
0.31
drogout value
Figure S36: Lipschitz constant bounds for ResNec20, trained on CIFAR-I0 with various levels of dropout. More details are in Appendix $2.6.17.
S3.22 EFFECT OF WEIGHT DECAY
Similar to the previous experiment, we also test the Clower metric against increasing regularisation via weight decay. Once again, expect the Lipschitz constant to decrease with stronger regularisation.
41

---

Published as a conference paper at ICLR 2024
The results in Figure S38 are in line with our expectations: the lower Lipschitz bound indeed decreases (with some small noise) with higher values of weight decay.
Cuase
140
Canganore
120
VOLU1
C
010000
0.003
0.0015
0.0000
0.0075
weight denzy valuue
Figure S37: Lipschitz constant bounds for ResNet20, trained on CIFAR-10 with various levels of weight decay. More details are in Appendix $2.6.17.
S3.23 LOWER LIPSCHITZ BOUND SAMPLES WITH CORRECT AND INCORRECT PREDICTED LABELS
In this experiment, we compute the lower Lipschitz bounds on misclassified and correctly classified labels separately for the case of ResNet22 on CIFAR-10 with dropout and le-4 weight decay. As the results demonstrate, incorrectly classified samples indeed more frequently have higher values of the Jacobian norm, compared to the points with correct classes. However, since the lower bound is computed as the supremum, basing the calculation on either of the sets alone would yield a similar value. Moreover, there is simply no correlation between the loss and the Jacobian norm (the value is 0.03), which indicates that there is no clear benefit in only considering misclassified samples for lower Lipschitz bound estimation.
0.33
Carrectly classifued satugles
0.87
Incorrectly classified samples
0.88
Srequeaayy
0.31
0.83
0.32
Jacobian nome
Figure S38: Jacobian norm bounds for points with correct and incorrect labels, predicted by ResNet20, trained on CIFAR-10 with zero dropout and le-4 weight decay. More details are in Appendix $2.6.17.
42

---

Published as a conference paper at ICLR 2024
S4 THEORETICAL PROOFS
S4.1 THEORETICAL ANALYSIS OF LIPSCHITZ EVOLUTION
Let us denote/ f(0,x): TP x TR R as our network function, where 0 is our parameter vector.
We also denote L(0, S) as our loss and S as our training set. We are interested in finding bound for C' for the trained model at time step T':
vx E D: 1I x) f(0", xx)I S C| - x'1l S C
||x x--X x'Il x.X'ED
sup
Initial and Final points based analysis. Let us introduce simple upper bound on the LHS by adding and subtracting the network at initialisation:
(f x) -(0",, xx'Il 10= x) - f(0", x) + f(00; x) - f(0", ) + f(00, xx) - f(0": .x'Il
$ l1 ,) f(0", x)| + 1If(0" x) f(0", xx) )| + 11f(0" x) f(0", x)|
$ 20 0011 + Cx (0)) [ x- x'|
20
Cx yr
where Cx )x) is the Lipschitz constant in the input space for the model at initialisation and Co is the Lipschitz constant for the network in the parameter space. The latter quantity unfortunately hard to compute, since it requires to search through the space of both parameters and inputs to find the maximum norm. Morcover, it might not be as tight.
Intermediate-poine based analysis. We can tackle the above issue by applying the same trick iteratively to get a local Lipschitz constant in the parameter space:
(1 s(" x')l = 11
x)
(sio", x) -((0', x) + 5(0', x') -(00', x))) - -(0", x')ll Σ 0=
T-1
|10+11 x) -(0', x)]l+ Σ Il x)) - -(( ,x)l 11,(00) .x) 1(0 x'Il
$ 20 discrete
110 + (x) ||x - x1|
< 20 Cisicreeee
110 - 00'1 + (x
where Ci Cyliscrete ;= supge !" sup suPxedom((f)
(0. i.e., the supremum of parameter-wist Lipschitz constants for a discrete set of checkpoints. In comparison to Cg. Calserett is only evaluated for ( )²),
reducing the search space in the parameter dimension (thus it is marked as discrete).
We can further simplify the equation by considering the GD update rule: gz+1 = 0² nu V C(O', .) and introducing the bounded gradients assumption (i.c. || | x)| S B). Note that this constraint can be easily fulfilled by using gradient clipping. The term 7/ denotes the learning rate at time step t. Let 17 be the maximum learning rate throughout the epochs. Then we have the following:
[f x) -f(0".'0 (2)il < 20
110 - -0'11 + 00(1+Cx(00))
T-1
T-1
discrete
nell V C( .S)I + (x)) S dddiscete Σ nB Cx
0
= (220g O Cdiscrete BTT + C2(00))
43

---

Published as a conference paper at ICLR 2024
Therefore the Lipschitz constant grows in proportion the number of steps:
C ( Brj T
S4.2 BIAS- VARIANCE TRADEOFF
Let us denote the neural network function as fo S. and the ground-truth function as y* (xx. Here, S denotes the training set and indicates the noise in the function due to the choice of random initialisation and the noise introduced by a stochastic optimiser, like stochastic gradient descent (SGD). In other words, one can take Ç as denoting the random seed used in practice. Then let us assume we have the square loss, i.c., f(x; fe) = lyy (x) - fo S, O)1.. We can write the loss evaluated on a test set, S", i.e. the test loss, follows:
C(O, S' ex (xl fe S111
(6)
In practice, typically average the test loss several random seeds, hence inherently involving an expectation over the noise Ç. We derive a varsanariance tradeoff (Geman et al., 1992; Neal et al., 2018) that rests upon this as the noise source. Also, consider the fixed-design variant of the bias-variance tradeoff and as a result, we will not average over the choice of the training set sampled from the distribution. In any case, for suitably large training set size, this is expected not introduce a lot of fluctuations and in particular, for the phenomenon at hand, i.c. Double Descent, the training is generally considered be fixed. Hereafter, for convenience, we will suppress the dependence of the network function on the training set.
Now we do the usual trick of adding and subtracting the expected neural network function over the noise source. Hence, we can rewrite the above as:
C(0.S'.C)
E S
[lly* $ (x) E Exlfo(x () B [)] fx [²]
= E X
[lly" (x) Exlfo(x S)]1 + Ex [|EE [[] c)] - fo (x, c)1
2 E S
(xx(xx - Ec(fo(x,()) (Eclfo(x - fo(x, ()))
Next, we take the expectation of the above test loss with respect to the noise source ( mirroring the empirical practice of reporting results averaged over multiple seeds. It is easy see that when taking the expectation, the cross-term vanishes and we are left with the following expression:
Eç C(, S², S',() E S [lly" (x) E.lfo [)]]
+ B E X [I {) fe(x, <)
(7)
E s st [lly" (x) E 1Eclfo (x. [) + S E, [[,oxx <)] fo( 1)
(8)
E x [lly (x) (/oo []]] + Ex Varc ()) Overall, this results the bias-variance trade-off under our setting.
L'ondi-b the Variance term. Now, we want to do a finer analysis of the variance term by involving the Lipschitz constant of the network function.
Varç(fo(x, <)) E, [|EE () fo 13]
(10)
Ex
Ecllo ()] E (x 5) fo (x', fo(x', fo fx. 1|2
(11)
44

---

Published as a conference paper at ICLR 2024
where, we have considered auxiliary point x', and added and subtracted terms. For vectors, X1,"- X,,, we can utilize the simple inequality:
| +
x
which follows from applications of the Cauchy-Schwand inequality. Hence, the variance above can be upper-bounded as:
(fo ()) = 3 + +3 fx () [x( c)I
[)] (x <)]l 3
[B () 1 fo(x'. c)Il
We can think of EE <So(x, () as the ensembled function mapping, and denote it by saying Jo (x) E ce (x, C), and let's assume that it is C-Lipschitz. On the other hand, let's say that each individual function fx(x, <) has Lipschitz constant Cg. Hence we can further reduce the upper bound to
Varç (fo ()) & 3 x - x212 + Varç ()) + +3E Ca x'112
(12)
Now, we bring back the outer expectation with respect to samples from the test set, i.c., x ~ S":
xx-s' (Jrx( ()) S 33Ex~5 e ||x - x'12 3 x~s' Varç(Jo(x', ()) 33 x E Cf1xx x
Notice that while the Lipschitz constant the neural network function do depend on the training data, the above expectation is with respect to samples from the test set. Hence, we can take the Lipschitz constants that appear above outside of the expectation. Besides, the middle term on the right-hand side has no dependency on the test sample x ~ S' and so the expectation goes away. Overall, this yields.
E S Varç (Jo(x,) ()) <C² -Ce D Ex ||x- x'12 Varç ()) (Var bound 0)
where, for simplicity, we have denoted the Lipschitz constant C₃ averaged over the random seeds Cg. We can simplify the above upper bounds by taking x' = 0 as the vector of all zeros, resulting
in:
E Exns' Varç(fo(x, ()) $3( + +T²) X ||x|| +3 (0, ())
(Var bound 1)
45


Reviews:
[{"review_id": "DlBOp5hd6J", "reviewer": "Reviewer_F3fH", "summary": "The paper focus on the Lipschitz constant of Neural Networks, and in particular focus on different aspect: 1) how and what do we learn from different Lipschitz bounds from the literature and in particular the gap between lower and upper bounds and its evolution during training, 2) the impact of over-parametrisation on the Lispchitz constant and 3) the impact of noisy labels the network lipschitzness. \nThe author focus on an intense experimental protocol in order to shade some lights on many claims about the Lipschitz constant of neural networks.", "questions": "Definition 2.2 is more of a proposition following Definition 2.1.\n\nSection 3.2: How do you compute the convex combinations of the domain samples? Does it actually makes a lot of difference with looking at random points around the samples (say a gaussian centered at a specific sample)? Intuitively it is where one could find the steepest parts of the neural networks rather than convex combinations.\n\nFigure 8: does the practical variance follow the theoretical bound\n\nMore generally and in the actual context of the field, it would be very interesting to add experiments with Transformers (with constraint inputs to make it Lipschitz).\n\n**Appendix:**\n\nS4, Intermediate-points based analysis:  \nI am not sure about how to go from 2nd line to 3d line of the list of inequalities. It seems to me that $C^{discrete}$ is not the correct constant to consider and in order for the inequality to be correct, the supremum should be considered on all $\\theta$. It however doesn't seem to be critical to the result about the growth of the Lipschitz constant through training. Could you confirm or dismiss this comment?\n\nS3.17: I am very surprised with this and I agree with the comment made there, do you have any explanation to propose for such a marginal difference?\n\nS3.18: Have you try to apply the same methods as in S4.1 but for Adam (or maybe RMSprop as it might be easier) optimizer? With maybe minimum assumptions it could shade some lights on this difference of behaviour.\n\n## Typos:\n\nSection 5: 'emprical'\n\nAppendix S3.1: 'btheta' missing '' in tex file probably\n\n## Overall\n\nThe author present a very interesting experimental approach to many Lipschitz claims about neural network and are convincing at exploring, discussing and interpreting their finding. As such I think it is a good paper. My main limitation for a conference is the fact that the paper is mostly located within its own appendix.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is very nice to read (if the appendix had been printed aside), it covers the topic pretty well and its relationship with related works is well described.\n\nIt is mostly an experimental study and it seems to me that the methodology is correct. A lot of experiments in various regime with many different real life instances are quite convincing to me. All experiments lead to a reasonable or theoretically supported interpretation.  \nI quite appreciate that many experiences are real life: with trained network of descent size on well known datasets.", "weaknesses": "The article covers many subject and proposes many illustrations of their finding. However a limitation of this work relies in the lack of theoretical insights on the different findings that are discussed (which is an easy weakness to raise for any experimental paper, I admit).\n\nReading this article is a constant back-and-forth between the main article and its appendix. It often feel that the main article is a glossary to the appendix. As such it often feels like the article should be 'vectorized' and would be better put into a journal format.  \nFor this reason I find difficult to correctly judge the adequacy of this (paper+appendix) to a conference like ICLR and I am open to this discussion with my fellow reviewers and AC.\n\nBibliography:\n\n- many references are incomplete: they point at arXiv versions rather than their peer-reviewed publications.\n- Some references are doubled such as 'On lazy training in differentiable programming' by Chizat et al.\n- Are you certain that the reference to (Gomez et al. 2020) ('Lipschitz constant estimation of Neural network via sparse polynomial optimization') shouldn't be (Latorre et al.) as I do not see the name 'Gomez' in the original paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bxo3dMv8nT", "reviewer": "Reviewer_Jyw9", "summary": "This paper focuses on the importance of Lipschitz continuity in neural network models, which influences their robustness, generalization, and susceptibility to adversarial attacks. In contrast to previous research that aims to tighten Lipschitz bounds and enforce specific properties, this study delves into characterizing the Lipschitz behavior of Neural Networks. It conducts empirical experiments across various scenarios, including different architectures, datasets, label noise levels, and more, exploring the limits of lower and upper Lipschitz bounds. \n\nNotably, the paper highlights the strong adherence to the lower Lipschitz bound, identifies a noteworthy Double Descent trend in both upper and lower bounds for Lipschitz continuity, and offers insights into how label noise affects function smoothness and generalization.", "questions": "- As highlighted in the weaknesses section, my primary concern revolves around understanding how commonly-used and seemingly simple regularization techniques like \"weight decay\" and \"dropout\" influence the Lipschitz constants. The paper would benefit from thorough discussions in this regard, rather than solely focusing on scenarios without regularization.\n\n- In the context of classification problems, it would be advantageous for the paper to display C_lower values separately for mis-classified samples and correctly-classified samples.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper conducted extensive experiments to showcase its findings and offers a comprehensive exploration of experimental details and discussions.\n- The paper raised intriguing facets of Lipschitz continuity within neural network models, which are likely to attract substantial interest from the deep learning community aiming to develop theory and practical algorithms based on these observations.", "weaknesses": "- While the paper provides thorough experiments and in-depth discussions, its novelty might be subject to question. As also mentioned in the paper, there is concurrent research with a similar focus that has also highlighted the connection between the Lipschitz constant and Double Descent, although they tracked only an estimate of the Lipschitz constant. I appreciate the authors’ efforts in sharing more empirical observations and discussions. But I am not very confident that the paper is completely novel.\n\n- From the optimizer's perspective, this paper may have some shortcomings as it does not delve into the discussion of weight decay and dropout, which are widely employed regularization techniques in neural network training. It is noted in the paper that the intention is not to focus on regularization techniques, but there are a few concerns to address. The term \"weight decay\" is mentioned only once in S2.6.9 (Page 22) with non-zero values. This implies that all other experiments either employ zero weight decay or the paper lacks sufficient implementation details. Similarly, the term \"dropout\" appears only once in S2.6.7 (Page), and the paper does not provide any insights or discussions regarding the impact of dropout.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n9JEcHbV5U", "reviewer": "Reviewer_EeTb", "summary": "The paper discusses Lipschitz continuity of neural networks in the following aspects. Firstly, they show the fidelity of the local Lipschitz-based lower bound, by providing several experiments on different models and datasets (section 3.2, also in appendix), and provide their intuition based on a toy example (section 3.3). With that, they investigate the trend of the Lipschitz constant, from initialization and during the course of training. Secondly, they discuss the (implicit) Lipschitz regularisation and double descent behavior, mainly in the context of over parameterization setup of the deep models and a bias variance trade off argument is provided. Thirdly, they discuss about the Lipschitz constant in the presence of the label noise, with the main focus of the network capacities vs the noise strengths. A hypothesis is provided: “while the network is able to fit the noise, Lipschitz constant should increase”, beyond which the network will reach a memorization threshold, and collapse to a smoother function with a smaller Lipschitz constant. In all the 3 aspects discussed, empirical evidence is provided based on several models and datasets.", "questions": "1. Is it possible to provide theoretical explanation of the different aspects found?\n2. Is it possible to extend some of the experiment in any of the language models?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Extensive experiment to show the different aspects in the discussion, as well as to provide evidence for their intuition and hypothesis.", "weaknesses": "Less theoretical explanation of the different aspects discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mhgwo6oUIE", "reviewer": "Reviewer_Sk7T", "summary": "This paper presents some empirical studies on the Lipschitz constant of neural networks. The studies reveal three major results:\n1. the evolution of Lipschitz constant during training; 2. the double descent of Lipschitz constant of neural networks; 3. The Lipchitz contant variation with respect to random labels. The study also shows the fidelity of lower Lipschitz bound.", "questions": "The layerwise upper bound is known a loose measurement, and indeed there is a giant gap between the upper and lower bounds in the experiments. Is it possible to strengthen the measurement to have a more precise characterization of the Lipschitz constant?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The perspective and results are interesting: the Lipschitz constant of a function is an intrinsic property of neural networks, and it has connections with many learning theoretical properties. For example, the double descent of phenomenon of neural networks is known and understanding this phenomenon from the Lipschitz constant evolution can be an interesting persepctive.", "weaknesses": "1. Overall this paper lacks coherence. Though this paper studies the Lipschitz constant of neural networks, each question studied in the paper is quite independent. Also these questions are important and each deserves an in-depth study. The empirical result is interesting yet insufficient to understand the phenomenon per se.\n\n2. The paper is also not rigorous. For example, in the intro, the paper stated that \"to put it more accurately, it is the maximum absolute change in the function per unit norm change in the input\". This statement is only true when the function is scaling invariant. Also because of each question is not studied thourouly, many of the aspects are not rigorously studied. for example, the paper studies effective Lipschitz constant but in reality distributional shift may occur and how the effective Lipschitz constant may change is not known. The scope of this paper is too big and each of the questions requires an in-depth analysis.\n\n3. The paper is also not well-organized. This comes from that the paper lacks coherence. Even though each point is explained, it is still unclear about the message of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)