Some Fundamental Aspects about Lipschitz Continuity of Neural Networks
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.
Grigory Khromov, Sidak Pal Singh
# Some Fundamental Aspects about Lipschitz Continuity

###### Abstract

Lipschitz continuity is a simple yet pivotal functional property of any predictive model that lies at the core of its robustness, generalisation, and adversarial vulnerability. Our aim is to thoroughly investigate and characterise the Lipschitz behaviour of the functions learned via neural networks. Despite the significant tightening of the bounds in the recent years, precisely estimating the Lipschitz constant continues to be a practical challenge and tight theoretical analyses, similarly, remain intractable. Therefore, _we shift our perspective and instead attempt to uncover insights about the nature of Lipschitz constant of neural networks functions_ -- by relying on the simplest and most general upper and lower bounds. We carry out an empirical investigation in a range of different settings (architectures, losses, optimisers, label noise, etc.), which reveals several fundamental and intriguing traits of the Lipschitz continuity of neural networks functions, In particular, we identify _a remarkable double descent trend in both upper and lower bounds to the Lipschitz constant_ which tightly aligns with the typical double descent trend in the test loss.

## 1 Introduction & Related Work

Lipschitz continuity of a function is a key quantity that reflects its smoothness as the input is perturbed (or more accurately, the maximum absolute change in the function value for a unit norm change in the input). Typically, in machine learning, our hope is that the learned predictive function is not overly sensitive to (non-adversarial) input changes. Otherwise, if the function changes too drastically for minuscule changes in the input, we can hardly hope that the learned function would generalise to unseen data drawn from the underlying distribution. On the flip side, when the value of the Lipschitz constant is extremely small (for the sake of the argument, think close to zero), this would imply a large bias [1] and essentially a useless function.

From these arguments sketched above, it is not hard to see why the Lipschitz constant plays a crucial role in various topics such as generalisation [2], robustness [3], vulnerability to adversarial examples [4], and more. As a result, there is also a significant body of literature in both theoretical [2; 5; 6; 7; 8; 9] and applied [10; 11; 12; 13; 14] directions, as discussed below in more detail.

The focus of our current study is on uncovering the fundamental aspects of Lipschitz continuity of neural network functions -- and thus contribute towards a better understanding of modern over-parameterised neural networks. Despite much progress achieved over the years -- owing to which we have a better estimate of the true Lipschitz constant [5] -- insights about their behaviour and characteristics for neural networks have been hard to come by. For instance, a plethora of fundamental questions, in the context of Lipschitz continuity of neural functions, remain to be understood:
* How does the Lipschitz constant behave for a wider versus narrow network? Shallow versus deeper networks? More broadly, how does it vary across different network architectures?
* Does the Lipschitz constant change significantly over the course of training or is it largely governed by the value at initialisation?
* How does its behaviour vary across different loss functions? Since, of course, we don't want to be misled by the nature of a particular loss function, and rather obtain 'functional' properties.
* Are there any notable differences between the Lipschitz continuity for different choices of optimisers?
* How does the nature of the learning task (i.e., in terms of the amount of signal or noise present) affect the Lipschitz continuity?

Our objective is precisely to contribute towards this end, with an emphasis on over-parameterised deep neural networks as trained in practice.

Approach.Part of the reason why important insights have been hard to come by through recent studies on the Lipschitz constant is that the newer methods, which produce tighter estimates of the true Lipschitz, are, more often than not, rather expensive computationally -- limiting their use. Or when simple bounds are utilised, there is an element of uncertainty whether the findings apply to the true Lipschitz constant or just that particular bound. We propose a simple way around this problem: track and investigate both upper and lower bounds to the Lipschitz constant. We will show this embarrassingly simple fix nevertheless lets us showcase intriguing traits about the Lipschitz constant of neural network functions in a multitude of settings. A key highlight is that we discover a double descent trend in both upper and lower bounds to the Lipschitz constant, which bears an intimate relationship with double descent trend in test loss [15].

Contributions:
* We begin by investigating the evolution of upper and lower bounds to the Lipschitz constant during the course of training for fully-connected and convolutional networks. In this setting, we also showcase the fidelity of the lower bounds to represent the true Lipschitz constant by evaluating them in a much wider vicinity of the training samples.
* We then study the effect of increasing network widths on the Lipschitz constant, within an extensive range of widths spanning about \(14\) orders of magnitude. Interestingly, we observe that double descent trend in the test loss is also mirrored through the upper and lower Lipschitz bounds.
* We also present a theoretical argument based on the bias-variance tradeoff and show that the variance is upper bounded by the squared Lipschitz constant (something which we also establish empirically).
* Next, we probe the effect of different loss functions and optimisers on the behaviour of Lipschitz continuity and hypothesise the reasons for the same. We find that with Cross-Entropy (CE) loss, the Lipschitz bounds are higher as compared to that when using Mean-Squared Error (MSE) loss. On the other hand, training with adaptive methods like Adam [16] results in higher values of the Lipschitz constant as compared to just using stochastic gradient descent (SGD).
* Furthermore, we also do another set of studies that illustrates the effect of depth, training set size, and label noise on the Lipschitz continuity of neural networks. This reveals an interesting trend where Lipschitz constant increases with more signal in the dataset (more clean training samples) and decreases in the presence of more noise.
* Lastly, we find that the distance of the network from the initialisation can capture many of the interesting trends in the Lipschitz constant.

Related Work.Theoretical interest in the Lipschitz constant of neural networks has been revived since Bartlett et al. [2] described how margin-based generalisation bounds are linearly dependent on the Lipschitz constant. Since generalisation bounds and robustness guarantees [3] are expressed in terms of the upper bound estimates of the true Lipschitz constant, extensive research has been done in
the field of its efficient and accurate estimation [5; 6; 8; 17]. As opposed to this direction of finding the tightest possible bounds, our aim in this work is rather to identify and uncover intriguing aspects of Lipschitz continuity in neural networks. But, in the future, we also aim to explore these tighter bounds in the context of neural networks.

On the practical side, Lipschitz constant has also been useful as a regularise while training regular neural networks [10; 11], but also for Generative Adversarial Networks (GANs) [13; 18], as well as addressing robustness to adversarial examples [12] and perturbations in input [14]. Most of these regularisation techniques enforce constraints on the parameters or the architecture in order to constrain the Lipschitz constant or its estimate.

Very recently, concurrent to our work, Gamba et al. [19] have also noted the connection between Lipschitz constant and the phenomenon of double descent [15]. In contrast to their work, which only tracks a reasonable yet heuristic estimate of the Lipschitz constant, we painstakingly track both lower and upper Lipschitz bounds. Besides, our focus is also much broader and covers many other settings where we explore the behaviour of Lipschitz constant.

## 2 Lipschitz constant of Neural Network functions

Before we start investigating the Lipschitz constant for neural networks, let us first recall the definition of Lipschitz-continuous functions.

**Definition 2.1** (Lipschitz continuous function).: _For function \(f:\mathbb{R}^{n}\mapsto\mathbb{R}^{m}\), defined on some domain \(dom(f)\subseteq\mathbb{R}^{n}\), \(f\) is called \(C\)-Lipschitz continuous, \(C>0\), w.r.t some \(\alpha\) norm if:_

\[\forall\mathbf{x},\mathbf{y}\in dom(f):\|f(\mathbf{x})-f(\mathbf{y})\|_{ \alpha}\leq C\|\mathbf{x}-\mathbf{y}\|_{\alpha}\]

Note that we are usually interested in the smallest \(C\), such that the above condition holds. This is what we call the Lipschitz constant of the function \(f\).

Unfortunately, the exact value of the Lipschitz constant is proven to be NP-hard to compute [17]. Therefore we focus on the upper and the lower bounds of the true Lipschitz constant. To lower bound the Lipschitz constant, we use another definition of the Lipschitz constant (see theorem 1 in [20] or proceed with [21]).

**Theorem 1** (Alternative definition of the Lipschitz constant).: _Let function \(f:\mathbb{R}^{n}\mapsto\mathbb{R}^{m}\), be defined on some domain \(dom(f)\subseteq\mathbb{R}^{n}\). Let \(f\) also be differentiable and \(C\)-Lipschitz continuous. Then the Lipschitz constant \(C\) is given by:_

\[C=\sup_{\mathbf{x}\in dom(f)}\|\nabla_{\mathbf{x}}f\|_{\alpha^{*}}\]

_where \(\nabla_{\mathbf{x}}f\) is the Jacobian of \(f\) w.r.t. to input \(\mathbf{x}\) and \(\alpha^{*}\) is the dual norm of \(\alpha\)._

For simplicity, we will focus on computing the 2-norm for the rest of the paper. Note that the dual norm for the 2-norm is also 2-norm. Hereafter, all the norms will denote the 2-norm, and thus we will omit it in the expressions.

In a typical machine learning setting, we would like to train a model that generalises well to samples drawn from the underlying distribution \(\mathcal{D}\). Thus, for our model \(f_{\boldsymbol{\theta}}\), we are interested in finding,

\[C=\sup_{\mathbf{x}\in\mathcal{D}}\|\nabla_{\mathbf{x}}f_{\boldsymbol{\theta}} \|_{2}\leq\sup_{\mathbf{x}\in dom(f)}\|\nabla_{\mathbf{x}}f_{\boldsymbol{ \theta}}\|_{2}\,,\]

where in the last step we consider the supremum over the entire domain of the function \(f\), i.e., even outside of the true data distribution \(\mathcal{D}\), which is usually unknown.

However, we can find a lower bound for our Lipschitz constant by limiting the supremum computation to the training set \(S\subseteq\mathcal{D}\):

\[C_{\text{lower}}=\sup_{\mathbf{x}\in S}\|\nabla_{\mathbf{x}}f_{\boldsymbol{ \theta}}\|_{2}\leq\sup_{\mathbf{x}\in\mathcal{D}}\|\nabla_{\mathbf{x}}f_{ \boldsymbol{\theta}}\|_{2}=C \tag{1}\]

Tight upper bounds to the Lipschitz constant, however, are far from trivial to compute. A lot of recent research has focused on producing different methods of upper bound estimation (as it has been discussed in the Section 1, under related work), each aiming to improve the tightness of the bound
and its computation speed. While this is a fascinating direction, in this paper, our aim is slightly different. Instead of getting encumbered by the demands of tighter bounds to the Lipschitz constant, _we shift the perspective towards understanding the nature and behaviour of the Lipschitz constant_ in a host of different settings. We do this by'sandwiching' the true Lipschitz by suitable lower and upper bounds to it, and tracking them both. Rather remarkably, we find that just focusing on the simplest possible bounds delivers intriguing insights which we will elaborate through the coming sections.

We start with describing our approach to compute the upper bound of the Lipschitz constant, inspired by the AutoLip algorithm introduced by [17]. To give a simple overview, let us analyse the case of sequential neural networks where each layer has a zero bias. Let our model \(f_{\mathbf{\theta}}\) with \(L\) layers be defined as \(f_{\mathbf{\theta}}:=f_{L}\circ f_{L-1}\circ\cdots\circ f_{1}\), which is a sequence of linear and non-linear transformations. For this case, the Lipschitz constant upper bound would be the product of Lipschitz constants of each individual layer:

\[C\leq\prod_{i=1}^{L}C_{f_{i}}=\prod_{i=1}^{L}\sup_{t_{i}\in dom(f_{i})}\| \nabla_{t_{i}}f_{i}\|_{2}\leq\prod_{i=1}^{L}\sup\|\nabla_{t_{i}}f_{i}\|_{2}=C _{\text{upper}} \tag{2}\]

More pedantically, one can see this by using Theorem 1 and chain rule as follows:

\[C =\sup_{\mathbf{x}\in\mathbf{D}}\|\nabla_{\mathbf{x}}f_{\mathbf{ \theta}}\|_{2}=\sup_{\mathbf{x}\in\mathcal{D}}\|\nabla_{f_{L-1}}f_{L}\cdot \nabla_{f_{L-2}}f_{L-1}\cdot\ \ldots\ \cdot\nabla_{f_{1}}f_{2}\cdot\nabla_{\mathbf{x}}f_{1}\|_{2}\] \[\leq\sup_{f_{L-1}(\mathbf{x})}\|\nabla_{f_{L-1}}f_{L}\|_{2}\cdot \sup_{f_{L-2}(\mathbf{x})}\|\nabla_{f_{L-2}}f_{L-1}\|_{2}\cdot\ \ldots\ \cdot\sup_{f_{1}(\mathbf{x})}\|\nabla_{f_{1}}f_{2}\|_{2}\cdot \sup_{\mathbf{x}\in\mathcal{D}}\|\nabla_{\mathbf{x}}f_{1}\|_{2} \tag{3}\] \[\leq\sup\|\nabla_{f_{L-1}}f_{L}\|_{2}\cdot\sup\|\nabla_{f_{L-2}}f _{L-1}\|_{2}\cdot\ \ldots\ \cdot\sup\|\nabla_{f_{1}}f_{2}\|_{2}\cdot\sup\|\nabla_{ \mathbf{x}}f_{1}\|_{2}=:C_{\text{upper}}\, \tag{4}\]

where in the last line we consider the unconstrained supremum. For each linear layer \(f_{i}(\mathbf{x})=\mathbf{W}_{i}\,\mathbf{x}\), we know that the upper bound to the Lipschitz constant is equal to \(\|\mathbf{W}_{i}\|_{2}\), since the Jacobian matrix for \(f_{i}\) is equal to the weight matrix. Note that convolution layers can be represented as suitable linear transformations [22] using doubly block Toeplitz matrices. As a result, the upper bound to their Lipschitz constant can be recovered as the 2-norm of this equivalent matrix that is only dependent on kernel weights. Meanwhile, activation functions (like ReLU) and pooling layers (such as max-pooling) are just \(1\)-Lipschitz. Therefore, for such sequential neural networks, where each layer has a \(1\)-Lipschitz activation function, the upper bound is just the product of the norms of the corresponding linear transformation matrices.

Deep CNN layers have rather large respective linear transformation matrices due to a high number of input and output channels, which complicates the calculation of the matrix 2-norm using standard tools. To speed the computation we have therefore implemented Power Method, which, in some cases, resulted in up to 10 times faster calculations.

Empirical evaluation of the evolution of Lipschitz constant.Having introduced the main concepts, let us begin by first exploring how the Lipschitz constant behaves during training. In other words, we would like to investigate the evolution of the Lipschitz constant during training for a given neural network. In Figure 1, we present the results of training a feed-forward neural network with ReLU activations (we will call such network FF ReLU later) and 1 hidden layer of width 256. The model was trained on MNIST1D dataset [23] using the SGD optimiser and Cross-Entropy loss until convergence and zero training loss.

We include the line for \(C_{\text{avg\_norm}}=\mathbb{E}_{\mathbf{x}\in\mathcal{S}}\|\nabla_{\mathbf{x} }f_{\mathbf{\theta}}\|_{2}\) to indicate that the supremum bound is relatively close to the expected value of the Jacobian norm, which indicates that the supremum computation is not heavily affected by potential outliers.

From Figure 1 we can see that the \(C_{\text{lower}}\) and the \(C_{\text{upper}}\) are increasing with epochs, diverging rapidly from each other. Similar Lipschitz evolution trends are depicted by networks in other settings as well. In later sections, we give more details on how the Lipschitz constant evolution changes with the choice of width (section 3) or depth of the network (section 6), as well as the loss and the optimiser (section 5). Similar trends seem to hold even for other network architecture choices, such as Convolutional Neural Networks (CNNs), as illustrated in Figure 4.
Fidelity of the lower bound to the Lipschitz.As the true Lipschitz constant lies somewhere between the upper and the lower bounds, one may ask: how loose are those bounds and where does the true Lipschitz constant lie?

To give more insight into this, we compute bound 1 on a larger set of examples \(S^{*}\). This set includes, apart from the previously presented training set \(S\), (a) the test1 set \(S^{\prime}\), and (b) random 100,000 convex combinations of samples from the train set and test set. The set of convex combinations (\(\lambda\mathbf{x}_{i}+(1-\lambda)\mathbf{x}_{j}\)) is computed for each \(\lambda=\{0.1,0.2,0.3,0.4,0.5\}\), making it 500,000 samples for the train and 500,000 samples for the test set. In the end, \(S^{*}\) contains 1,005,000 samples. Results are presented in Figures 2 and 3. We denote \(C_{S^{*}}\) as the Lipschitz constant computed on the set \(S^{*}\).

Footnote 1: MNIST1D train dataset contains 4000 samples, test dataset contains 1000 samples.

It is evident from the above Figure 2 that the bound for the Lipschitz constant computed on set \(S^{*}\) lies closer to the lower bound \(C_{\text{lower}}\). This indicates that even though the upper bound \(C_{\text{upper}}\) gives a loose Lipschitz constant bound for the model for the whole functional domain \(dom(\mathbf{f}_{\mathbf{\theta}})\), _the true Lipschitz constant lies relatively closer to the lower bound \(C_{\text{lower}}\)_.

This statement is important, as the gap between the upper and the lower bound can become extremely large in some cases, leading to a significant overestimation of the Lipschitz constant of the network function. For instance, this may be observed in the case of CNNs. Figure 4 shows the Lipschitz constant trend for the CNN model with width (i.e., number of channels) 7, trained on CIFAR-10 [24] using Cross-Entropy loss and SGD optimiser until convergence and zero training loss.

Figure 1: Plot of Lipschitz constant bounds by training epoch for **FF ReLU network** with 1 hidden layer with 256 neurons. The model was trained on MNIST1D using Cross-Entropy loss and SGD optimiser. Results are averaged over 4 runs. More details in appendix S1.

Figure 2: Plot of Lipschitz constant bounds on the **train set \(S\) and set \(S^{*}\)** by training epoch for **FF ReLU network** with 1 hidden layer with 256 neurons. The model was trained on MNIST1D using Cross-Entropy loss and SGD optimiser. Results are averaged over 4 runs. More details in appendix sections S1.
We have presented both linear and log scales to show that even though the upper bound is growing much faster than the lower and the average norm bounds, all three bounds still follow the same trend as it was first shown in Figure 1.

For the rest of the paper, we will present both upper and lower Lipschitz constant bounds. However, we would like to mention that since the lower bound \(C_{\text{lower}}\) is closer to representing the Lipschitz constant for the distribution \(\mathcal{D}\), it would serve the reader to pay more attention to it compared to other bounds. In fact, this fact can also be seen in some of the works which propose tighter upper-bounds to the Lipschitz [9].

Remark.As can be seen, we have evaluated the fidelity of our lower bound on samples in the input space that are outside of the data distribution (but are still somewhat meaningful). It would also be interesting to consider the case of adversarially generated samples [4] and see how much can the lower bounds be pushed up. We leave this for a future investigation.

## 3 Double Descent in Lipschitz constant: Effect of Width

To study how the Lipschitz constant changes with the width of the hidden layers of the model, we conduct an experiment where we trained 16 FF ReLU networks, with 1 hidden layer, of increasing width. All the networks were trained on MNIST1D using Cross-Entropy loss and SGD optimiser.

This experimental setting, where networks with increasing number of parameters are compared to one another, should be reminiscent of the Double Descent phenomenon [15]. In this study, we replicated Double Descent for the setting above, which requires us to train all models until convergence. In order to keep the hyperparameters consistent across all settings while still being able to handle networks

Figure 4: Plots of Lipschitz constant bounds by training epoch for **CNN network** with width 7. The model was trained on CIFAR-10 using Cross-Entropy loss and SGD optimiser. Results are averaged over 4 runs. More details in appendix S1.

Figure 3: Plot of lower Lipschitz constant bounds **on different dataset combinations** by training epoch for **FF ReLU network** with 1 hidden layer with 256 neurons. The model was trained on MNIST1D using Cross-Entropy loss and SGD optimiser. Results are averaged over 4 runs. More details in appendix sections S1.
with such varying widths, we utilize an initial learning rate warmup to the base learning rate (LR) of 0.005 (referred to as Warmup20000Step25 LR Scheduler) for our runs. More details on models and the training strategy are listed in the appendix S1.

Figure 5 clearly displays how all three Lipschitz constant bounds display a shape similar to Double Descent. The interpolation threshold for both Lipschitz bounds and the test loss is at width 80, which is also the theoretical threshold, as FF ReLU with no bias and 1 hidden layer with width 80, 40 values on input and 10 values on output, has \(40\cdot 80+80\cdot 10=4000\) parameters, which is the exact number of training samples in the MNIST1D dataset.

Similar trends in the Lipschitz constant could be seen for FF ReLU networks trained using MSE, as well as other models like CNNs. In Figures 6 and 7, we present the Lipchitz constant bounds of the models at their last epoch for these two settings. We also include additional experiments on top of previously observed double descent in test loss in the literature [25], where we simply plot the Lipschitz bounds and even observe a double descent trend for them. These figures are located in appendix S2.1. Besides, a few remarks are in order:

Location of Interpolation threshold.It should be noted that, in both of these cases, the empirical interpolation thresholds appear slightly before the theoretical ones. For MSE loss, the interpolation threshold should theoretically occur at \(p=K\cdot n\) where \(p\) denotes the number of parameters, \(n\) is the number of training samples, and \(K\) is the output dimension. This corresponds to a width of \(800\) in the case of a one-hidden layer fully connected network, while empirically the interpolation threshold already seems near width \(~{}256\). Likewise, for the CNN model trained on CIFAR10 with 50000 samples, theoretically, the interpolation threshold should occur between width 11 (with \(p=46915\)) and width 12 (with \(p=55716\)). However, empirically, we see that it occurs at width \(10\). But besides

Figure 5: Log-Log plots of Lipschitz constant bounds and train and test losses by width for **FF ReLU networks** with 1 hidden layer with varying number of hidden neurons. Models were trained using **Cross-Entropy loss** and SGD optimiser with learning rate 0.005 and Warmup20000Step25 learning rate scheduler. Results are presented for the last epoch for each individual model and are averaged over 4 runs. More details in appendix S1.
this slight difference in the location of the interpolation threshold, we can clearly see that both the test loss and Lipschitz constant (as seen through the upper and lower bounds) show a double descent trend. As a matter of fact, such a behaviour of the interpolation threshold is also implicit in past works [26].

Trend of the entire generalization bounds.The fact that Lipschitz constant shows the same trend as the test loss is in a way expected, given that several generalization bounds include it as a term [2]. It would also be interesting to investigate if such proposed bounds also capture double descent in their entirety, and not just when the trend of the Lipschitz constant is noted in isolation.

Potential indication of Triple Descent.Lastly, unlike the test loss, the upper Lipschitz for FF ReLU networks (and even the lower Lipschitz sometimes, although more faintly relative to the upper bound) seems to continue to increase after the second descent, which could be a connection to the Triple Descent phenomenon [27]. We leave this observation as a future research question.

## 4 Bias-Variance Tradeoff

### A textbook theoretical analysis

To give some theoretical ground for the observations in the previous section, we present how bias-variance tradeoff connects with the Lipschitz constant of the network. Let us denote the neural network function as \(f_{\mathbf{\theta}}(\mathbf{x},S,\zeta)\) and the ground-truth function as \(\mathbf{y}^{\star}(\mathbf{x})\). Here, \(S\) denotes the training set and \(\zeta\) indicates the noise in the function due to the choice of random initialization and the noise

Figure 6: Log-Log plots of Lipschitz constant bounds and train and test losses by width for **FF ReLU networks** with 1 hidden layer with varying number of hidden neurons. Models were trained using **MSE loss** and SGD optimiser with learning rate 0.005 and Warmup20000Step25 learning rate scheduler. Results are presented for the last epoch for each individual model and are averaged over 4 runs. More details can be found in appendix S1.

Figure 7: Log-Log plots of Lipschitz constant bounds and train and test losses by width for **CNN networks** with varying width parameter. Models were trained using **Cross-Entropy loss** and SGD optimiser with learning rate 0.01 and Cont100 learning rate scheduler. Results are presented for the last epoch for each individual model and are averaged over 4 runs. More details can be found in appendix S1.
introduced by a stochastic optimizer, like stochastic gradient descent (SGD). Or said differently, one can take \(\zeta\) as denoting the random seed used in practice. Then let us assume we have the square loss, i.e., \(\ell(\mathbf{x};\mathbf{f}_{\mathbf{\theta}})=\|y(\mathbf{x})-f_{\mathbf{\theta}}(\mathbf{x },S,\zeta)\|^{2}\). We can write the loss evaluated on a test set, \(S^{\prime}\), i.e., the test loss, as follows:

\[\mathcal{L}(\mathbf{\theta},S^{\prime},\zeta)=\mathbb{E}_{\,\mathbf{x}\sim S^{ \prime}}\left[\|y(\mathbf{x})-f_{\mathbf{\theta}}(\mathbf{x},S,\zeta)\|^{2}\right] \tag{5}\]

In practice, we typically average the test loss over several random seeds, hence inherently involving an expectation over the noise \(\zeta\). We derive a bias-variance tradeoff [1, 28] that rests upon this as the noise source. Also, we 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 a suitably large training set size, this is expected not to introduce a lot of fluctuations and in particular, for the phenomenon at hand, i.e. double descent the training set is generally considered to 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:

\[\mathcal{L}(\mathbf{\theta},S^{\prime},\zeta) =\mathbb{E}_{\,\mathbf{x}\sim S^{\prime}}\left[\|y(\mathbf{x})- \mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]+\mathbb{E}_{\,\zeta}[ f_{\mathbf{\theta}}(\mathbf{x},\zeta)]-f_{\mathbf{\theta}}(\mathbf{x},\zeta)\|^{2}\right]\] \[=\mathbb{E}_{\,\mathbf{x}\sim S^{\prime}}\left[\|y(\mathbf{x})- \mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]\|^{2}\right]+\mathbb{ E}_{\,\mathbf{x}\sim S^{\prime}}\left[\|\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}( \mathbf{x},\zeta)]-f_{\mathbf{\theta}}(\mathbf{x},\zeta)\|^{2}\right]\] \[+2\,\mathbb{E}_{\,\mathbf{x}\sim S^{\prime}}\left[\left(y( \mathbf{x})-\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]\right)^{ \top}\,(\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]-f_{\mathbf{\theta }}(\mathbf{x},\zeta))\right)\right]\]

Next, we take the expectation of the above test loss with respect to the noise source \(\zeta\) -- mirroring the empirical practice of reporting results averaged over multiple seeds. It is easy to see that when taking expectation, the cross-term vanishes and we are left with the following expression:

\[\mathbb{E}_{\,\zeta}\,\mathcal{L}(\mathbf{\theta},S^{\prime},\zeta) =\mathbb{E}_{\,\mathbf{x}\sim S^{\prime}}\left[\|y(\mathbf{x})- \mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]\|^{2}\right]+\mathbb{ E}_{\,\zeta}\,\mathbb{E}_{\,\mathbf{x}\sim S^{\prime}}\left[\|\mathbb{E}_{\, \zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]-f_{\mathbf{\theta}}(\mathbf{x},\zeta)\|^ {2}\right] \tag{6}\] \[=\mathbb{E}_{\,\mathbf{x}\sim S^{\prime}}\left[\|y(\mathbf{x})- \mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]\|^{2}\right]+\mathbb{ E}_{\,\mathbf{x}\sim S^{\prime}}\mathbb{E}_{\,\zeta}\left[\|\mathbb{E}_{\,\zeta}[f_{ \mathbf{\theta}}(\mathbf{x},\zeta)]-f_{\mathbf{\theta}}(\mathbf{x},\zeta)\|^{2}\right]\] (7) \[=\mathbb{E}_{\,\mathbf{x}\sim S^{\prime}}\left[\|y(\mathbf{x})- \mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]\|^{2}\right]+\mathbb{ E}_{\,\mathbf{x}\sim S^{\prime}}\,\mathrm{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{x}, \zeta)) \tag{8}\]

As a shorthand, we denote the above expected test loss as \(\overline{\mathcal{L}}(\mathbf{\theta},S^{\prime}):=\mathbb{E}_{\,\zeta}\,\mathcal{ L}(\mathbf{\theta},S^{\prime},\zeta)\). Overall, this results in the bias-variance tradeoff under our setting.

Upper-bounding the Variance term.Now, we want to a do a finer analysis of the variance term by involving the Lipschitz constant of the network function. Moreover, let's for the moment focus only on the part \(\mathrm{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{x},\zeta))\).

\[\mathrm{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{x},\zeta))=\mathbb{ E}_{\,\zeta}\left[\|\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]-f_{\mathbf{ \theta}}(\mathbf{x},\zeta)\|^{2}\right] \tag{9}\] \[=\mathbb{E}_{\,\zeta}\left[\|\underbrace{\mathbb{E}_{\,\zeta}[f_ {\mathbf{\theta}}(\mathbf{x},\zeta)]-\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x }^{\prime},\zeta)]}_{a}+\underbrace{\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}( \mathbf{x}^{\prime},\zeta)]-f_{\mathbf{\theta}}(\mathbf{x}^{\prime},\zeta)}_{b}+ \underbrace{f_{\mathbf{\theta}}(\mathbf{x}^{\prime},\zeta)-f_{\mathbf{\theta}}(\mathbf{x },\zeta)}_{c}\|^{2}\right] \tag{10}\]

where, we have considered some auxiliary point \(\mathbf{x}^{\prime}\), and added and subtracted some terms. Further recalling that for \(n\) vectors, \(\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\), we can utilize the simple inequality:

\[\|\mathbf{x}_{1}+\cdots+\mathbf{x}_{n}\|^{2}\leq n\sum_{i=1}^{n}\|\mathbf{x}_{i }\|^{2}\]

which follows from \(n\) applications of the Cauchy-Schwarz inequality. Hence, the variance above can be upper-bounded as:

\[\mathrm{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{x},\zeta)) \leq 3\,\|\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)]- \mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x}^{\prime},\zeta)]\|^{2}+3\, \mathbb{E}_{\,\zeta}\,\|\mathbb{E}_{\,\zeta}[f_{\mathbf{\theta}}(\mathbf{x}^{ \prime},\zeta)]-f_{\mathbf{\theta}}(\mathbf{x}^{\prime},\zeta)\|^{2}\] \[+3\,\mathbb{E}_{\,\zeta}\,\|f_{\mathbf{\theta}}(\mathbf{x}^{\prime}, \zeta)-f_{\mathbf{\theta}}(\mathbf{x},\zeta)\|^{2}\]
We can think of \(\mathbb{E}\,_{\zeta}f_{\mathbf{\theta}}(\mathbf{x},\zeta)\) as the ensembled function mapping, and denote it by say \(\overline{f_{\mathbf{\theta}}}(\mathbf{x}):=\mathbb{E}\,_{\zeta}f_{\mathbf{\theta}}( \mathbf{x},\zeta)\), and let's assume that it is \(\overline{C}\)-Lipschitz. On the other hand, let's say that each individual function \(f_{\mathbf{\theta}}(\mathbf{x},\zeta)\) has Lipschitz constant \(C_{\zeta}\). Hence we can further reduce the upper bound to

\[\operatorname{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{x},\zeta))\leq 3\, \overline{C}^{2}\,\|\mathbf{x}-\mathbf{x}^{\prime}\|^{2}+3\,\operatorname{ Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{x}^{\prime},\zeta))+3\,\mathbb{E}\,_{ \zeta}\,C_{\zeta}^{2}\|\mathbf{x}-\mathbf{x}^{\prime}\|^{2}\,. \tag{11}\]

Now, we bring back the outer expectation with respect to samples from the test set, i.e., \(\mathbf{x}\sim S^{\prime}\):

\[\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\operatorname{Var}_{\zeta}(f_{\mathbf{ \theta}}(\mathbf{x},\zeta))\leq 3\,\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}} \operatorname{\overline{C}^{2}}\,\|\mathbf{x}-\mathbf{x}^{\prime}\|^{2}+3\, \mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\,\operatorname{Var}_{\zeta}(f_{\mathbf{ \theta}}(\mathbf{x}^{\prime},\zeta))+3\,\mathbb{E}\,_{\mathbf{x}\sim S^{ \prime}}\,\mathbb{E}\,_{\zeta}\,C_{\zeta}^{2}\|\mathbf{x}-\mathbf{x}^{\prime}\| ^{2}\]

Notice that while the Lipschitz constant of 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 \(\mathbf{x}\sim S^{\prime}\) and so the expectation goes away. Overall, this yields,

\[\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\operatorname{Var}_{\zeta}(f_{\mathbf{ \theta}}(\mathbf{x},\zeta))\leq 3\,(\overline{C}^{2}+\overline{C_{\zeta}^{ \prime}}^{2})\,\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\,\|\mathbf{x}-\mathbf{ x}^{\prime}\|^{2}+3\,\operatorname{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{x}^{ \prime},\zeta)) \tag{12}\]

where, for simplicity, we have denoted the Lipschitz constant \(C_{\zeta}\) averaged over the random seeds \(\zeta\), as \(\overline{C_{\zeta}}\). We can simplify the above upper bounds by taking \(\mathbf{x}^{\prime}=\mathbf{0}\) as the vector of all zeros, resulting in:

\[\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\operatorname{Var}_{\zeta}(f_{\mathbf{ \theta}}(\mathbf{x},\zeta))\leq 3\,(\overline{C}^{2}+\overline{C_{\zeta}^{ \prime}}^{2})\,\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\,\|\mathbf{x}\|^{2}+3 \,\operatorname{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{0},\zeta)) \tag{13}\]

and which now contains the variance of the network function at the input \(\mathbf{0}\) computed over the various seeds. As a shorthand let's denote \(\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\,\|\mathbf{x}\|^{2}\) as the \(r_{S^{\prime}}^{2}\).

At the cost of loosening the above upper bound, we can simplify it by using the fact that \(\overline{C}\leq\overline{C_{\zeta}}\). This is because (using Jensen's inequality):

\[\|\overline{f_{\mathbf{\theta}}}(\mathbf{x})-\overline{f_{\mathbf{\theta }}}(\mathbf{x}^{\prime})\| =\|\mathbb{E}\,_{\zeta}[f_{\mathbf{\theta}}(\mathbf{x},\zeta)-f_{\mathbf{ \theta}}(\mathbf{x}^{\prime},\zeta)]\|\] \[\leq\mathbb{E}\,_{\zeta}\|f_{\mathbf{\theta}}(\mathbf{x},\zeta)-f_{ \mathbf{\theta}}(\mathbf{x}^{\prime},\zeta)\|\] \[\leq\mathbb{E}\,_{\zeta}C_{\zeta}\|\mathbf{x}-\mathbf{x}^{\prime} \|=\overline{C_{\zeta}}\|\mathbf{x}-\mathbf{x}^{\prime}\|\,.\]

Hence, we have:

\[\mathbb{E}\,_{\mathbf{x}\sim S^{\prime}}\operatorname{Var}_{\zeta}(f_{\mathbf{ \theta}}(\mathbf{x},\zeta))\leq 6\,r_{S^{\prime}}^{2}\,\overline{C_{\zeta} }^{2}+3\,\operatorname{Var}_{\zeta}(f_{\mathbf{\theta}}(\mathbf{0},\zeta)) \tag{14}\]

As \(r_{S^{\prime}}^{2}\) is going to be network size agnostic (or e.g., when the data is on the unit sphere, simply unity), we can see that the variance term in the bias-variance tradeoff will be largely dictated by the average Lipschitz constant of the function over various seeds. Plus, close to interpolation and after, the bias term will be rather small. So, it is the Lipschitz constant which will control the upper bound on the generalization error.

### Empirical Evaluation

Bias-Variance tradeoff.In Figure 8, we present the empirical calculation for the relation of Variance and test loss. We use the same sweep of FF ReLU networks with varying width on the MNIST1D dataset using MSE loss from the Double Descent section 3.

Variance upper bounds.We also show empirical calculations for the bounds in the equations 13 and 14, presented in Figure 9. Empirical data was collected from the same models introduced in the previous paragraph.

## 5 Lipschitz Constant and the Optimisation procedure

In this section we explore how the choice of the optimisation strategy affects the Lipschitz constant of the Network. By optimisation strategy we mean the choice of the loss function and the optimisation algorithm. We will observe the effect of each choice separately.
Figure 8: Log-log plots of Variance and test loss against model width. Results are presented from training FF ReLU networks with varying width on MNIST1D using MSE loss and SGD optimiser. The expectations over random initialisations were computed as an average of 4 seeds. More details in appendix S1.

Figure 10: Plot of Lipschitz constant bounds for FF ReLU network with 1 hidden layer with 256 neurons, trained using **Cross-Entropy loss and MSE loss**. Both models were trained on MNIST1D with SGD using the same LR and LR scheduler. Results are averaged over 4 runs. More details in appendix S1.

Figure 9: Log-log plot of Variance and its upper bounds against model width. Results are presented from training FF ReLU networks with varying width on MNIST1D using MSE loss and SGD optimiser. The expectations over random initialisations were computed as an average of 4 seeds. More details in appendix sections S1 and S2.2.
### Effect of the loss function: CE vs MSE

Figure 10 shows the evolution of the Lipschitz constant for the FF ReLU models, trained on MNIST1D with SGD using Cross-Entropy and MSE loss.

The plots show that the bounds for MSE loss are by an order of magnitude smaller than the ones for Cross-Entropy. Our hypothesis is that this occurs due to the magnitude of possible values on the output. Since for the classification task with MSE loss our model has to ideally output a one-hot vector, the range of the norm of possible output values is smaller than in the case of Cross-Entropy, where outputs are further Softmax-ed. Note that we compute the Lipschitz constant with respect to the output of the model without Softmax, since classification could still be done by finding the argmax of the output.

Lipschitz evaluation including Softmax.To support our argument, we also compute the value of the lower Lipschitz constant bound on the FF ReLU 256 network trained on Cross-Entropy with an additional layer of Softmax applied. Results in Figure 11 empirically verify that Softmax pushes the lower bound for the Cross-Entropy trained network closer to the range of values of the MSE trained network.

### Effect of the optimisation algorithm: SGD vs Adam

In Figure 12, we show evolution of the Lipschitz constant for the FF ReLU models, trained on MNIST1D using Cross-Entropy with SGD and Adam optimisers.

Figure 11: Plot of lower Lipschitz constant bounds for FF ReLU network with 1 hidden layer with 256 neurons, trained using **Cross-Entropy loss and MSE loss**. A variant of **FF ReLU trained on Cross-Entropy with Softmax applied** is included as well. All models were trained on MNIST1D with SGD using the same LR and LR scheduler. Results are averaged over 4 runs. More details in appendix S1.

Figure 12: Plot of Lipschitz constant bounds for FF ReLU network with 1 hidden layer with 256 neurons, trained using **SGD and Adam**. Both models were trained on MNIST1D with Cross-Entropy, using the same LR and LR scheduler. Results are averaged over 4 runs. More details in appendix S1.
Figure 12 displays how Adam significantly increases all Lipschitz bounds, and we hypothesize that this might be linked to the nature of Adam optimisation. More concretely, we find that in the case of training with Adam the final model parameters travel further from initialisation as compared to that with SGD. This is illustrated in Figure 13, where we plot the norm of the parameter vector difference between current epoch and initialisation \(\|\mathbf{\theta}_{t}-\mathbf{\theta}_{0}\|_{2}\) over the epochs. But we leave a thorough exploration of this facet for future work.

We note that this trend also holds even if train the network with SGD for more epochs and the respective plots are in appendix S2.

An interesting by-product of the above finding is that actually \(\|\mathbf{\theta}_{t}-\mathbf{\theta}_{0}\|_{2}\) also exhibits Double Descent as in the setting of increasing network width. Results of the sweep are shown in Figure 14.

## 6 Miscellaneous Experiments

In this section we present more experiments to find dependencies between the Lipschitz constant of the network and other learning parameters. In particular, we present how Lipschitz depends on depth, number of training samples and different amounts of label noise.

### Lipschitz constant and the effect of Depth

To study the effects of depth we train a series of FF ReLU models with various number of hidden layers, from 1 to 5. Comparison of the evolution of Lipcschitz constant bounds are presented in Figure 15 and a summary plot is displayed in Figure 16.

Figure 14: Log-Log plots of Norms of the parameter difference and train and test losses by width for **FF ReLU networks** with 1 hidden layer with varying number of hidden neurons. Models were trained using **Cross-Entropy loss** and SGD optimiser with learning rate 0.005 and Warmup20000Step25 learning rate scheduler. Results are presented for the last epoch for each individual model and are averaged over 4 runs. More details in appendix S1.

Figure 13: Plot of the difference Lipschitz constant bounds for FF ReLU network with 1 hidden layer with 256 neurons, trained using **SGD and Adam**. Both models were trained on MNIST1D with Cross-Entropy, using the same LR and LR scheduler. Results are averaged over 4 runs. More details in appendix S1.
#### 6.1.1 At Convergence

#### 6.1.2 At Initialization

According to the plots, all Lipschitz bounds start to multiplicatively increase with each subsequent layer. Note that the increase is not immediate: deeper models start rapidly increasing the Lipschitz later than more shallow models, especially in the case for the lower bound. An interesting fact is that

Figure 16: Summary plot of Lipschitz constant bounds against the **number of hidden layers** of FF ReLU network **at the last epoch**. All models are trained on MNIST1D using Cross-Entropy loss and SGD. More details in appendix S1.

Figure 17: Summary plot of Lipschitz constant bounds against the **number of hidden layers** of FF ReLU network **at initialisation**. All models are trained on MNIST1D using Cross-Entropy loss and SGD. More details in appendix S1.

Figure 15: Plots of Lipschitz constant bounds against epochs for **various number of hidden layers** of FF ReLU network. All models are trained on MNIST1D using Cross-Entropy loss and SGD. More details in appendix S1.
the aforementioned trend does not hold for networks at initialisation, both for the case of increasing depth (Figure 17) and increasing width (Figure 18). Consequently, we also see how the effect of feature learning gets manifested in the bounds of the Lipschitz constant and that looking solely at initialisation (as in the style of the lazy regime [29]) would be insufficient.

### Lipschitz constant and the effect of the number of training samples

In this section we present Lipschitz constant bounds for FF ReLU model with width 256 on various sizes of MNIST1D: 4000, 1000, 500 and 100 training samples. Results are presented on Figure 19.

Figure 19 shows that increasing the number of samples in the training dataset increases the Lipschitz constant. This suggests that the networks need to become "less smooth" as the complexity of function increases to fit a larger number 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.

### Lipschitz constant and the effect of Label Noise

In this paragraph we have trained an FF ReLU model with width 256 on the modified version of MNIST1D, where labels are shuffled. We used datasets, where 0%, 10%, 15%, 20%, 25%, 50%, 75% and 100% of labels are shuffled. Results are presented on Figure 21.

Figure 21 shows that increasing the amount of shuffling reduces the lower and average norm Lipschitz constant bounds. These observations show that increasing label noise makes the function become injuriously smooth, which interferes with the ability of the network to generalize.

Figure 19: Plots of Lipschitz constant bounds against epochs for **various number of samples in the training dataset** for FF ReLU 256 network. All models are trained on MNIST1D using Cross-Entropy loss and SGD. Results are averaged over 4 runs. More details in appendix S1.

Figure 18: Log-log plot of Lipschitz constant bounds against the **width** of FF ReLU network **at initialisation**. All models are trained on MNIST1D using Cross-Entropy loss and SGD. More details in appendix S1.
## 7 Conclusion

To conclude, we have presented a wide-ranging study of the trends of the Lipschitz constant in various learning settings. First, we have shown evolution trends of various Lipschitz constant bounds for different networks, displaying the tightness of the simple lower bound with respect to the true Lipschitz constant. Second, we looked at the behaviour of Lipschitz constant in the Double Descent setting and have shown that both lower and upper Lipschitz bounds exhibit trends similar to test loss. We next presented theoretical statements, connecting Lipschitz constant with the variance term in the generalisation bound, and also gave experimental proof to those statements. In the subsequent sections, we discussed the effect of the choice of loss (between Cross-Entropy and MSE), optimisation algorithm (SGD versus Adam), depth of the network and training sample modifications, like variable dataset lengths and label noise.

Further research directions.We hope that this work inspires further research on uncovering and understanding the characteristics of the Lipschitz constant. One potential avenue for investigation is to explore more complex model classes, such as ResNets or different types of Transformers [30]. Additionally, it would be of great interest to compare tighter Lipschitz constant bounds, proposed in the literature, with the results presented in this study. Another promising area for future research is to examine how various forms of input noise affect the Lipschitz constant.

Figure 21: Plots of Lipschitz constant bounds against epochs for **various amounts of label shuffling of the training dataset** for FF ReLU 256 network. Results are averaged over 4 runs. All models are trained on MNIST1D using Cross-Entropy loss and SGD. More details in appendix S1.

Figure 20: Summary log-log plot of Lipschitz constant bounds against the **number of training samples** in MNIST1D. Plotted for the FF ReLU 256 networks at their last epoch. All models are trained using Cross-Entropy loss and SGD. Results are averaged over 4 runs. More details in appendix S1.
## Acknowledgements

We would like to thank Thomas Hofmann, Bernhard Scholkopf, 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 to acknowledge the financial support from Max Planck ETH Center for Learning Systems.
