Here, $c^{sat}_{i,j}$ is high for $\vz^i_t$ and $\vz^j_{t-1}$ where the generator was fooling the discriminator—i.e. low $1-D(G(\vz^j_{t-1}; \vtheta_{t-1}); \vphi_{t-1})$ and $1 - D(G(\vz^i_t; \vtheta); \vphi)$. Thus, instead of moving $\nabla_{\vtheta}  D(G(\vz^i_t; \vtheta); \vphi)$ away from directions where the generator was doing poorly previously as is the case for the non-saturating loss, it is moving it away from directions where the generator was performing well, which could lead to instabilities or loss of performance. Moreover, unlike for the non-saturating loss, the implicit regularisation will have a strong effect on the generator's update $- {\nabla_{\vtheta} E_{\vtheta} = \mathbb{E}_{p(\vz)} \frac{1}{1-D(G(\vz; \vtheta); \vphi)} \nabla_{\vtheta}  D(G(\vz; \vtheta); \vphi)}$, since gradients $\nabla_{\vtheta}  D(G(\vz; \vtheta); \vphi)$ that have a high weight in the generator's update are those where the interaction term coefficient in Eq (<ref>) is high. This is inline with our results in Section <ref>, showing that in zero-sum games (such as the one induced by the saturating loss), the regularisation induced by the discretisation error of gradient descent is strong, and can hurt performance and stability.

§ CONCLUSION

We provided a novel approach of interpreting backward error analysis and used it to find implicit regularisers induced by gradient descent in the single objective setting and in two-player games.
In the single objective case, we found implicit regularisation terms revealing importance of the alignment of gradients at the exact data batches used in multiple steps of stochastic gradient descent, while in two-player games we highlighted the need to examine the game structure in order to determine the effects of implicit regularisation.
We hope future work can empirically verify the effects of these implicit regularisers in deep learning.
We believe that our observations in this chapter might unlock future research, including verifying whether the dot product alignment regularisation we found explains the benefits of using stochastic gradient descent in deep learning, and what the empirical effect of the interaction terms is on generally differentiable two-player games.

In previous chapters, we used continuous-time approaches to model gradient descent optimisation dynamics and empirically assessed the effect of these dynamics on neural network training.
We have seen how improvements to optimisation lead to increased stability and better performance across problem domains, from supervised learning to two-player games such as GANs.
Optimisation also interacts with the choice of model through neural architectures and model regularisation: some neural architectures are easier to optimise than others [He et al., 2016, Liu et al., 2020], and model regularisation techniques can improve training stability [Bjorck et al., 2018, Miyato et al., 2018, Vahdat and Kautz, 2020].
For the rest of this thesis, we explore interactions between optimisation and models, and in particular model smoothness and smoothness regularisers. While smoothness quantifies sensitivity to changes in model inputs and optimisation is concerned with changes to model parameters, we show that in neural network training smoothness regularisation can improve optimisation and that implicit regularisation effects induced by optimisation—such as those discussed in previous chapters—can increase model smoothness.

§ WHY MODEL SMOOTHNESS?

How certain should a classifier be when it is presented with out of distribution data?
How much mass should a generative model assign around a datapoint?
How much should an agent's behaviour change when its environment changes slightly?
Answering these questions shows the need to quantify the manner in which the output of a
model varies with changes in its input, a quantity we will
intuitively call the smoothness of the model.
In deep learning,
neural network smoothness has been shown to boost generalisation and robustness of classifiers and
increase the stability and performance of generative models, as well as provide better priors for representation learning and reinforcement learning agents [Bartlett et al., 2017, Cisse et al., 2017, Novak et al., 2018, Sokolić et al., 2017, Lassance et al., 2018, Vahdat and Kautz, 2020, Miyato et al., 2018, D'Oro and Jaśkowski, 2020, Tschannen et al., 2020]. After providing an overview of the benefits of smoothness in deep learning and motivated by its impact across problem domains,
later in the chapter we investigate some of the previously unexplored effects of smoothness regularisation: strong interactions with optimisation, reduced model capacity, and interactions with data scaling.

§ MEASURING SMOOTHNESS

Neural network “smoothness” is a broad, vague, catch all term.
We use it to convey formal definitions, such as differentiable, bounded, Lipschitz,
as well as intuitive concepts such as invariant to data dimensions or projections, robust to input perturbations, and others.
One definition states that a function $f: \mathcal{X} \rightarrow \mathcal{Y}$ is $n$ smooth if is $n$ times differentiable with the $n$-th derivative being continuous.
The differentiability of a function
is not a very useful inductive bias for a model, as it is both very local and constructed according to the metric of the space where limits are taken.
What we are looking for is the ability to choose both the distance metric and how local or global our smoothness inductive biases are.
With this in mind,
Lipschitz continuity is appealing as it defines a global property and provides the choice of distances in the domain and co-domain of $f$. It is defined as:

\begin{align}
\norm{f(\vx_1) - f(\vx_2)}_{\mathcal{Y}} \le K \norm{\vx_1-\vx_2}_{\mathcal{X}}  \hspace{3em} \forall \vx_1, \vx_2 \in \mathcal{X},
\label{eq:lip_def}
\end{align}

where $K$ is denoted as the Lipschitz constant of function $f$.
To avoid learning trivially smooth functions and maintain useful variability, it is often beneficial to constrain the function variation both from above and below. This leads to bi-Lipschitz continuity:

\begin{align}
K_1 \norm{\vx_1-\vx_2}_{\mathcal{X}} \le \norm{f(\vx_1) - f(\vx_2)}_{\mathcal{Y}} \le K_2 \norm{\vx_1-\vx_2}_{\mathcal{X}}.
\end{align}

Enforcing Eq (<ref>) can be difficult, but according to Rademacher's theorem [Federer, 1996] if $\mathcal{X} \subset \mathbb{R}^I$ is an open set and $\mathcal{Y} = \mathbb{R}^O$ and $f$ is $K$-Lipschitz then $\norm{\frac{d f(\vx)}{d \vx}}_{op} \le K$ wherever the total derivative $D_{\vx}f(\vt) = \frac{d f(\vx)}{d \vx} \vt$ exists, which is almost everywhere.
Conversely, a function $f$ that is differentiable everywhere with $\norm{\frac{d f(\vx)}{d \vx}}_{op} \le K$ is $K$-Lipschitz.
Since the operator norm is not always easily computable, at times the Frobenius norm of the Jacobian $\frac{d f(\vx)}{d \vx}$ is constrained instead, since the Frobenius norm bounds the operator norm from above: $\norm{\frac{d f(\vx)}{d \vx}}_{op} \le \norm{\frac{d f(\vx)}{d \vx}}_{2}$; for $O=1$, $\norm{\nabla_\vx f(\vx)}_{op} = \norm{\nabla_\vx f(\vx)}_2$. Thus, a convenient strategy to make a differentiable function $K$-Lipschitz is to ensure $\norm{\frac{d f(\vx)}{d \vx}}_{2} \le K, \forall \vx \in \mathcal{X}$.

If $f$ and $g$ are Lipschitz with constants $K_f$ and $K_g$, $f \circ g$ is Lipschitz with constant $K_f K_g$. Since commonly used activation functions are 1-Lipschitz, a neural network can be made Lipschitz by constraining each learneable layer to be Lipschitz. Many neural networks layers are linear operators (linear and convolutional layers, BatchNormalisation [Ioffe and Szegedy, 2015]), and to compute their Lipschitz constant we can use that the Lipschitz constant of a linear operator $A$ under common norms such as $l_1, l_2, l_{\infty}$ is $\sup_{\vx \ne 0} \frac{\norm{A\vx}}{\norm{\vx}}$ [Petersen and Pedersen, 2008]. For the $l_2$ norm, most commonly used in practice, this leads to finding the spectral norm of $A$.

§ SMOOTHNESS REGULARISATION IN DEEP LEARNING

Smoothness regularisers have long been part of the toolkit of the deep learning practitioner:
early stopping encourages smoothness by stopping optimisation before the model overfits the training data;
dropout [Srivastava et al., 2014] makes the network more robust to small changes in the input by randomly masking hidden activations; max pooling encourages smoothness with respect to local changes;
$L_2$ weight regularisation and weight decay [Loshchilov and Hutter, 2018] discourage large changes in output by not allowing individual weight norms to grow;
data augmentation allows us to specify what changes in the input should not result in large changes in the model prediction and thus is also closely related to smoothness and invariance to input transformations.
These smoothness regularisation techniques are often introduced as methods that directly target generalisation and other beneficial effects of smoothness discussed in Section <ref>, instead of being seen through the lens of smoothness regularisation.

Methods that explicitly target smoothness on the entire input space focus on restricting the learned model family.
A common approach is to ensure Lipschitz smoothness with respect to the $l_2$ metric by individually restricting the Lipschitz constant of each layer; for layers that are linear operators, this entails restricting their spectral norm.
Spectral regularisation [Yoshida and Miyato, 2017] uses the sum of the spectral norms—the largest singular value—of each layer as a regularisation loss to encourage Lipschitz smoothness.
Spectral Normalisation [Miyato et al., 2018] ensures the learned models are 1-Lipschitz by adding a node in the computational graph of the model layers by replacing the weights with their normalised version:

\begin{align}
\vW \rightarrow \vW/||\vW||_{op},
\end{align}

$||\vW||_{op}$ is the spectral norm of $\vW$. Both Spectral Normalisation and Spectral Regularisation use power iteration [Mises and Pollaczek-Geiringer, 1929] to compute the spectral norm of weight matrices $||\vW||_{op}$ for layers which are linear operators, such as convolutional or linear layers.  Gouk et al., 2020 use a projection method by dividing the weights by the spectral norm after a gradient update. This is unlike Spectral Normalisation, which backpropgates through the normalisation operation.
The majority of this line of work has focused on constraints for linear and convolutional layers, and only recently attempts to expand to other layers, such as self attention, have been made [Kim et al., 2021].
Efficiency is always a concern and heuristics are often used even for popular layers such as convolutional layers [Miyato et al., 2018] despite more accurate algorithms being available [Gouk et al., 2020, Tsuzuku et al., 2018].
Parseval networks [Cisse et al., 2017] ensure weight matrices of linear and convolutional layers are 1-Lipschitz by enforcing a stronger constraint, an extension of orthogonality to non-square matrices. Bartlett et al., 2018 show that
any bi-Lipschitz function can be written as a composition of residual layers [He et al., 2016].

Instead of restricting the learned function on the entire space, another approach of targeting smoothness constraints is to regularise the norm of the gradients of a predictor $f: \mathbb{R}^I \rightarrow \mathbb{R}$ with respect to inputs of the network $\norm{\nabla_{\vx}f(\vx;\vtheta)}$, at different regions of the space [Sokolić et al., 2017, Gulrajani et al., 2017, Fedus et al., 2018, Arbel et al., 2018, Kodali et al., 2017].
This is often enforced by adding a gradient penalty to the loss function $\mathcal{L(\vtheta)}$:

\begin{align}
\mathcal{L(\vtheta)} + \zeta \mathbb{E}_{p_{reg(\vx)}} \left(\norm{\nabla_{\vx}f(\vx;\vtheta)}^2 - K^2\right)^2,
\label{eq:grad_penalties}
\end{align}

where $\zeta$ is a regularisation coefficient,
$p_{reg(\vx)}$ is the distribution at which the regularisation is applied,
which can either be the data distribution [Sokolić et al., 2017, Arbel et al., 2018] or around it [Kodali et al., 2017, Fedus et al., 2018],
or, in the case of generative models, at linear interpolations between data and model samples [Gulrajani et al., 2017].
Gradient penalties encourage the function to be smooth around the support of $p_{reg(\vx)}$ either by encouraging
Lipschitz continuity ($K \ne 0$) or by discouraging drastic changes of the function as the input changes ($K=0$).

Smoothness for classification tasks is defined by Lassance et al., 2018 as preserving features similarities within the same class as we advance through the layers of the network.
The penalty used is $\sum_{l=1}^{L} \sum_{c=1}^{C}|\sigma^l(s_c) - \sigma^{l+1}(s_c)|$, where $\sigma^l(s_c)$ is the signal of features belonging to class $c$ computed using the Laplacian of layer $l$.
The Laplacian of a layer is defined by constructing a weighted symmetric adjacency matrix of the graph induced by the pairwise most similar layer features in the dataset.

§ THE BENEFITS OF LEARNING SMOOTH MODELS

Generalisation. Learning models that generalise beyond training data is the goal of machine learning.
The study of generalisation has long been connected with the study of model complexity, as models with small complexity generalise better [Vapnik, 2013].
Despite this, we have seen that deep, over-parametrised neural networks tend to generalise better than their shallow counterparts [Novak et al., 2018] and that for Bayesian methods, Occam's razor does not apply to the number of parameters used, but to the complexity of the function [Rasmussen and Ghahramani, 2001].
A way to reconcile these claims is to incorporate smoothness into definitions of model complexity and to show that smooth, over-parametrised neural networks generalise better than their less smooth counterparts.
Methods that encourage smoothness—such as weight decay, dropout, and early stopping —have been long shown to aid generalisation [Bartlett, 1997, Golowich et al., 2018, Hardt et al., 2016, Nakkiran et al., 2019, Srivastava et al., 2014].
Data augmentation
has been shown to increase robustness to random noise or to modality specific transformations, such as image cropping and rotations [Krizhevsky et al., 2012, Simonyan and Zisserman, 2015, Jun et al., 2020].
Sokolić et al., 2017 show that the generalisation error of a network with linear, softmax, and pooling layers is bounded by the classification margin in input space.
Since classifiers are trained to increase classification margins in output space, smoothing by bounding the spectral norm of the model's Jacobian increases generalisation performance; this leads to empirical gains on standard image classification tasks. Bartlett et al., 2017 provide a generalisation bound depending on classification margins and the product of spectral norms of the model's weights and show how empirically the product of spectral norms correlates with excess risk.

[Traditional U-shaped curve. ]

[Double descent in neural networks.]

[Double descent in deep learning compared to the traditional U-shaped complexity curve.]Double descent in deep learning compared to the traditional U-shaped complexity curve. fig:u_shape_p: traditional U-shaped curve associated with increased capacity; as we increase capacity, the test error first decreases after which it increases due to overfitting—the example we show here is that from Figure <ref>. Figure <ref>: when the complexity of neural networks is measured using the number of model parameters a double descent is observed, where a first descent is followed by a second descent.

Generalisation in deep learning has been recently re-examined under the light of double descent [Nakkiran et al., 2019, Belkin et al., 2019],
a phenomenon named after the shape of the generalisation error
plotted against the size of a deep neural network: as the size of the network increases the generalisation error decreases (first descent), then increases, after which it decreases again (second descent). This is unlike the traditional U-shaped curve associated with non-neural models, where the second descent does not occur.
We plot the traditional U-shaped curve in Figure <ref> and contrast it with the double descent phenomenon shown in Figure <ref>.
We postulate there is a strong connection between double descent and smoothness:
in the first descent, the generalisation error is decreasing as the model is given extra capacity to
capture the decision surface; the increase happens when the model has enough capacity to fit the training data, but it cannot do so and retain smoothness; the second descent occurs as the capacity increases and smoothness can be retained.
This view of double descent is supported by empirical evidence that shows that its effect
is most pronounced on clean label datasets and when early stopping and other regularisation techniques are not used [Nakkiran et al., 2019]. Later in this chapter, we show that smoothness constraints heavily interact with optimisation. This further suggests that empirical investigations into the impact of smoothness on the double descent phenomenon are needed, since implicit regularisation effects induced by optimisation might act as  smoothness regularisers affecting model complexity. We will come back to this question in Chapter <ref>.

Reliable uncertainty estimates. Neural networks trained to minimise classification losses provide notoriously unreliable uncertainty estimates;
an issue which gets compounded when the networks are faced with out of distribution data.
However, one can still leverage the power of neural networks to obtain reliable uncertainty estimates by combining smooth neural feature learners with non-softmax decision surfaces
[van Amersfoort et al., 2020, Liu et al., 2020].
The choice of smoothness regularisation or classifier can vary,
from using
gradient penalties on the neural features with a Radial Basis Function classifier [van Amersfoort et al., 2020],
to using Spectral Normalisation on neural features
and a Gaussian Process classifier [Liu et al., 2020].
These methods
are competitive with standard techniques used for out-of-distribution detection [Lakshminarayanan et al., 2017]
on both vision and language understanding tasks.
The importance of smoothness regularising neural features indicates that having a smooth decision surface, such as a Gaussian Process, is not sufficient to compensate for sharp feature functions when learning models for uncertainty estimation [Lakshminarayanan et al., 2017].

Robustness to adversarial attacks. Adversarial robustness has become an active area of research in recent years [Szegedy et al., 2013, Goodfellow et al., 2015, Papernot et al., 2016, Chakraborty et al., 2018].
Early works have observed that the existence of adversarial examples is related to the magnitude of the
gradient of the hidden network activation with respect to its input, and suggested that constraining
the Lipschitz constant of individual layers can make networks more robust to attacks [Szegedy et al., 2013].
Initial approaches to combating adversarial attacks, however, focused on data augmentation methods [Kurakin et al., 2016, Goodfellow et al., 2015, Moosavi-Dezfooli et al., 2017, Madry et al., 2018],
and only more recently smoothness has come into focus [Cisse et al., 2017, Novak et al., 2018, Sokolić et al., 2017, Lassance et al., 2018].
We can see the connection between smoothness and robustness by looking at the desired robustness properties of classifiers, which aim to ensure that inputs in the same $\epsilon$-ball result in the same function output:

\begin{align}
\norm{\vx - \vx'} \le \epsilon \implies \arg \max f(\vx) = \arg \max f(\vx').
\label{eq:adv_examples}
\end{align}

The aim of adversarial defences and robustness techniques is
to have $\epsilon$ be as large as possible without affecting classification accuracy.
Robustness against adversarial examples has been shown to correlate with generalisation [Gilmer et al., 2018], and with the sensitivity of the network output with respect to the input as measured by the Frobenius norm of the Jacobian of the learned function [Novak et al., 2018, Sokolić et al., 2017].
Lassance et al., 2018 show that robustness to adversarial examples is enhanced when the function approximator is smooth as defined by the Laplacian smoothness signal discussed in Section <ref>.
Tsuzuku et al., 2018 show that  Eq (<ref>)
holds when the $l_2$ norm is used if $\epsilon$ is smaller than the ratio of the classification margin and the
Lipschitz constant of the network times a constant, and thus they increase robustness by ensuring the margin is larger than the Lipschitz constant.

Improved generative modelling performance.
Smoothness constraints through gradient penalties or Spectral Normalisation have become a
recipe for obtaining state of the art generative models.
In Generative Adversarial Networks (GANs) [Goodfellow et al., 2014], smoothness constraints on
the discriminator and the generator have played a big part in scaling up training on large,
diverse image datasets at high resolution [Brock et al., 2018] and a combination of smoothness
constraints has been shown to be a requirement to get GANs to work on discrete data such as text [de Masson d'Autume et al., 2019].
The latest variational autoencoders [Kingma and Welling, 2014, Rezende et al., 2014] incorporate Spectral Regularisation to boost performance and stability [Vahdat and Kautz, 2020].
Explicit likelihood tractable models like normalizing flows [Rezende and Mohamed, 2015] benefit from smoothness constraints through powerful invertible layers built using residual connections
$g(\vx) = \vx + f(\vx)$ where $f$ is Lipschitz
[Behrmann et al., 2019].

More informative critics. Critics, learned approximators to intractable decision functions, have become a fruitful endeavour in generative modelling, representation learning, and reinforcement learning.

Critics are used in generative modelling to approximate divergences and distances between the learned model and the true unknown
data distribution, and have been mainly popularised by GANs.
A critic in a function class $\mathcal{F}$ can be used to approximate the KL divergence by minimizing the bound [Nguyen et al., 2010, Nowozin et al., 2016]:

\begin{align}
\mathrm{KL}(p||q) &= \mathbb{E}_{p(\vx)} \log\frac{p(\vx)}{q(\vx)} = \sup_{f} \mathbb{E}_{p(\vx)} f(\vx) - \mathbb{E}_{q(\vx)} e^{f(\vx)-1} \\&\ge \sup_{f \in \mathcal{F}} \mathbb{E}_{p(\vx)} f(\vx) - \mathbb{E}_{q(\vx)} e^{f(\vx)-1}.
\label{eq:kl_bound}
\end{align}

Due to the density ratio $p(\vx)/q(\vx)$ in its definition, the KL divergence provides no learning signal when the model and data distributions do not have overlapping support. Choosing $\mathcal{F}$ to be a family of smooth functions in Eq (<ref>), however, results in a bound on the KL that provides useful gradients and can be used to train a model, even when the two distributions do not have overlapping support [Fedus et al., 2018, Arbel et al., 2021].
We show an illustrative example in Figure <ref>: the true decision surface jumps from zero to infinity,
while the approximation provided by the MLP is smooth.
Similarly, training the critic more and making it better at estimating the true decision surface but less smooth can hurt training [Schäfer et al., 2020]. It's not surprising that imposing smoothness constraints on critics has become part of many flavours of GANs [Arjovsky et al., 2017, Gulrajani et al., 2017, Fedus et al., 2018, Brock et al., 2018, Arbel et al., 2018, Zhou et al., 2019, Yoshida and Miyato, 2017].

The same conclusions have been reached in unsupervised representation learning, where
parametric critics are trained to approximate another intractable quantity, the mutual information, using
the Donsker–Varadhan or similar bounds [Belghazi et al., 2018, Oord et al., 2018].
An extensive study on representation learning techniques based on mutual information showed that tighter bounds do not lead to better representations [Tschannen et al., 2020]. Instead, the success of these methods is attributed to the inductive biases of the critics employed to approximate the mutual information.
In reinforcement learning, neural function approximators or neural “critics” approximate
state-value functions or action-state value functions and are then used to train a policy to maximise the expected reward. Directly learning a neural network parametric estimator of the action value gradients
—the gradients of the action value with respect to the action—results in more accurate gradients (Figure 3 in [D'Oro and Jaśkowski, 2020]),
but also makes gradients smoother.
This provides an essential exploration prior in continuous control,
where similar actions likely result in the same reward and observing the same action twice is
unlikely due to size of the action space;
encouraging the policy network to extrapolate from the closest seen action
improves performance over both model free and model based continuous control approaches [D'Oro and Jaśkowski, 2020].

[KL divergence optimal critic $f^* = \frac{p}{q}$ and smooth critic estimate. ]

[Optimal Wasserstein critic is smooth.]

[The importance of critic smoothness when estimating divergences and distances.]The importance of critic smoothness when estimating divergences and distances. fig:kale_gan: When the two distributions do not have overlapping support, the KL divergence provides no learning signal, while a smooth approximation via a learned critic does. fig:optimal_critic_wasserstein: The optimal Wasserstein critic has a smoothness Lipschitz constraint in its definition.

Distributional distances. Including smoothness constraints in the definition of distributional distances by using optimal transport has seen a uptake in machine learning applications in recent years,
from generative modelling [Arjovsky et al., 2017, Gulrajani et al., 2017, Tolstikhin et al., 2018, Ostrovski et al., 2018]
to reinforcement learning [Bellemare et al., 2017, Dabney et al., 2018], neural flows [Finlay et al., 2020]
and fairness [Silvia et al., 2020, Jiang et al., 2020].
Optimal transport is connected to Lipschitz smoothness as the Wasserstein distance can be computed via the Kantorovich-Rubinstein duality [Villani, 2008]:

\begin{align}
W_1(p(\vx), q(\vx)) = \sup_{f: \norm{f}_{\text{Lip}} \le 1} \mathbb{E}_{p(\vx)} f(\vx) - \mathbb{E}_{q(\vx)} f(\vx).
\label{eq:wasserstein}
\end{align}

The Wasserstein distance finds the critic that can separate the two distributions in expectation,
but constraints that critic to be Lipschitz in order to avoid pathological solutions.
The importance of the Lipschitz constraint on the critic can be seen in Figure <ref>:
unlike the KL divergence,
the optimal Wasserstein critic is well defined when the two distributions do not have overlapping support, and does not require an approximation to provide useful learning signal for a generative model.

§ CHALLENGES WITH SMOOTHNESS REGULARISATION

Despite the many benefits of learning smooth models we outlined in the previous section, many of the effects of smoothness regularisation have not been extensively studied. In this section, we lay the ground work for the next chapters by looking at some of the unexplored effects of smoothness regularisation, from reduced model capacity to interactions with optimisation.
Figure reproduction details for this chapter are available in Appendix Chapter <ref>.

§.§ Too much smoothness hurts performance

Needlessly limiting the capacity of our models by enforcing smoothness constraints is a significant danger:
a constant function is very smooth, but not very useful.
Beyond trivial examples, Jacobsen et al., 2018 show that one of the reasons  neural networks are vulnerable to adversarial perturbations is invariance to task relevant changes—too much smoothness with respect to the wrong metric. A neural network can be “too Lipschitz”:
methods aimed at increasing robustness to adversarial examples do indeed decrease the Lipschitz constant of a classifier,
but once the Lipschitz constant becomes too low, accuracy drops significantly [Fazlyab et al., 2019].

There are two main avenues for being too restrictive in the specification of smoothness constraints,
depending on where and how smoothness is encouraged.
Smoothness constraints can be imposed on the entire input space or
only in certain pockets, often around the data distribution.
Methods that impose constraints on the entire space throw away useful information about the input distribution and restrict the learned function needlessly by forcing it to be smooth in areas of the space where there is no data. This is especially problematic when the input lies on a small manifold in a large dimensional space, such as in the case of natural images, which are a tiny fraction of the space of all possible images.
Model capacity can also be needlessly restrained by imposing strong constraints on the individual components of the model, often the network layers, instead of allowing the network to allocate capacity as needed.

[2 layer MLP.]

[4 layer MLP.]

[Gradient penalty at data;

[Spectral norm;

[Spectral norm;

[Spectral norm; scaling the data by 10.]

[Decision surfaces on two moons under different regularisation methods.]Decision surfaces on two moons under different regularisation methods.
Unless otherwise specified the model architecture is a 4 layer MLP. We observe that network depth can decrease smoothness fig:two_moons_decision_surface_deep_mlp; that data dependent smoothness penalties can increase smoothness fig:two_moons_decision_surface_grad_penalty; that hard smoothness constraints can lead to smooth surfaces but hurt performance fig:two_moons_decision_surface_sn, but that this effect can be mitigated by increasing the Lipschitz constant of the constraint fig:two_moons_decision_surface_sn_10 or scaling the range of the input data fig:two_moons_decision_surface_sn_data_scaling.

[Gradient penalty. $K=1$.]

[Spectral Normalisation. $K=1$.]

[Lipschitz constant of each layer of an MLP trained on the two moons dataset.]Lipschitz constant of each layer of an MLP trained on the two moons dataset.
The decision surfaces for the same models can be seen in Figure <ref>. Smaller means smoother. Soft regularisation via the gradient penalty leads to a decrease in spectral norm of the  model's weight matrices, with each layer adjusting differently to the constraint. In contrast, for Spectral Normalisation the spectral norm of the weight matrix for every layer is equal to 1.

[Gradient penalty. $K=1$.]

[Spectral Normalisation. $K=1$.]

[The effect of regularisation on local smoothness.]The effect of regularisation on local smoothness. We plot the local Lipschitz constants obtained using an exhaustive grid search in local neighbourhoods, instead of loose bounds. We use different colours to emphasise the different scale of the constants for the different methods. While gradient penalties increase smoothness, they do so primarily around the data, where the constraint is active, while Spectral Normalisation affects a large part of the input space.

We can exemplify the importance of where and how constraints are imposed with an example, by contrasting gradient penalties—end to end regularisation applied around the training data—and Spectral Normalisation—layer-wise regularisation applied to the entire space. Figure <ref> shows that using Spectral Normalisation to restrict the Lipschitz constant of an MLP to be 1 decreases the capacity of the network and severely affects accuracy compared to the
baseline MLP—Figure <ref>—or the MLP regularised using gradient penalties—Figure <ref>.
Further insight comes from Figure <ref>, which shows that the gradient penalty only enforces a
weak constraint on the model and does not heavily restrict the spectral norms of individual layers; this is in stark contrast with Spectral Normalisation, which, by construction, ensures each network layer has spectral norm equal to 1. To show the effect of data dependent regularisation on local smoothness we plot the Lipschitz constants of the model at neighbourhoods spanning the entire space in Figure <ref>. Each Lipschitz constant is
computed using an exhaustive grid search inside each local neighbourhood rather than a bound—details are provided in Appendix <ref>.
As expected, gradient penalties impose stronger constraints around the training data, while Spectral Normalisation has a strong effect on the smoothness around points in the entire space.
This simple example suggests that the search for better smoothness priors needs
to investigate where we want functions to be smooth
and re-examine how smoothness constraints should account for the compositional aspect of neural networks,
otherwise we run the risk of learning trivially smooth functions. In the next chapter, we will first hand encouter the need to avoid enforcing too strong smoothness constraints when applying Spectral Normalisation to reinforcement learning.

§.§ Interactions between smoothness regularisation and optimisation

We show that viewing smoothness only through the lens of the model is misleading, as smoothness constraints have a strong effect on optimisation.
The interaction between smoothness and optimisation has been mainly observed when training generative models;
encouraging the smoothness of the encoder through Spectral Regularisation increased the stability of hierarchical VAEs and led variational inference models to the state of the art of explicit likelihood non autoregressive models [Vahdat and Kautz, 2020],
while smoothness regularisation of the critic (or discriminator)
has been established as an indispensable stabiliser of GAN training, independently of the training criteria used [Yoshida and Miyato, 2017, Arbel et al., 2018, Fedus et al., 2018, Brock et al., 2018, Kurach et al., 2019].

Some smoothness regularisation techniques affect optimisation by
changing the loss function (gradient penalties, Spectral Regularisation) or the optimisation regime directly (early stopping, projection methods). Even if they don't explicitly change the loss function or optimisation regime,
smoothness constraints affect the path the model takes to reach convergence.
We use a simple example to show why smoothness regularisation interacts with optimisation in Figure <ref>. We use different learning rates to train two unregularised MLP classifiers on MNIST [LeCun et al., 1999]  and observe that the learning rate used affects its smoothness throughout training, without changing testing accuracy. Here, we measured the model's smoothness as the upper bound on its Lipschitz constant given by product of spectral norms of learnable layers. These results show that
imposing similar smoothness constraints on two models that share the same architecture but are trained with  different learning rates would lead to very different strengths of regularisation and drastically change the trajectory of optimisation. This is particularly true for methods such as Spectral Normalisation, which directly impact the spectral norms of individual layers we measured here.

[Smoothness constraints interact with learning rates.] Smoothness constraints interact with learning rates. MNIST classifiers trained with different learning rates exhibit different smoothness behaviour throughout training, even at the same test accuracy. We measured the model's smoothness as the upper bound on its Lipschitz constant given by product of spectral norms of learnable layers. This example shows that imposing the same smoothness constraint on the same model architecture trained with different learning rates will have different effects on optimisation dynamics. This can be particularly the case for methods that impact the spectral norms of individual layers we measured here.

[Momentum decay rate $\beta_1 = 0.5$.]

[Momentum decay rate $\beta_1 = 0.9$.]

[Smoothness constraints interact with momentum decay rates.]Smoothness constraints interact with momentum decay rates: Spectral Normalisation requires low momentum in GAN training. The effects of momentum decay rate $\beta_1$ in the Adam optimiser on Spectral Normalisation applied to the GAN discriminator on CIFAR-10, over a sweep of learning rates. Higher is better. Individual learning curves are obtained from a sweep over seeds and learning rates.

Beyond learning rates, smoothness constraints also interact  decay rate hyperparameters in optimisers that use momentum. When the Adam optimiser is used, this is the $\beta_1$ hyperparameter; for an overview of Adam and momentum we refer the reader to Section <ref>.
When training GANs, Gulrajani et al., 2017 observed that weight clipping in the Wasserstein GAN critic requires low to no momentum. Weight clipping has since been abandoned in the favour of other methods, but as we show in Figure <ref>, current methods like Spectral Normalisation
applied to GAN critics trained with low momentum decrease sensitivity to learning rates but perform poorly in conjunction with high momentum, leading to slower convergence and higher hyperparameter sensitivity.

We have shown that smoothness constraints interact with optimisation parameters, such as learning rates and momentum, and argue that we need to reassess our understanding of smoothness constraints, not only as constraints on the final model, but as methods that influence the optimisation path. We will study this in detail in the next chapter.

§.§ Sensitivity to data scaling

Sensitivity to data scaling of smoothness constraints can
make training neural network models sensitive to additional hyperparameters.
Let $f^*$ be the optimal decision function for a task obtained from using i.i.d. samples from random variable $X$, and
$f_c^*$ obtained similarly from i.i.d. samples obtained from $c X$.
Since $f^*$ and $f_c^*$ can be highly non linear, the relationship between the smoothness of the two functions is unclear.
This gets further complicated when we consider their closest approximators under a neural family.
The effect of data scaling on the smooth constraints
required to fit a model can be exemplified using the two moons dataset:
with a Lipschitz constraint of 1 on the model the data is poorly fit—Figure <ref>—but a much better fit can be obtained by changing the Lipschitz constant to 10—Figure <ref>—or scaling the data—Figure <ref>.

§ CONCLUSION

In this chapter, we outlined the many benefits of neural network smoothness across multiple problem domains. Motivated by these benefits and the wide use of smoothness regularisation in deep learning, we highlighted areas where the effects of smoothness have not been fully understood, from connections to the double descent phenomenon to interactions between smoothness regularisation and optimisation. We continue this line of inquiry in the following chapters.

CHAPTER: SMOOTHNESS AND OPTIMISATION EFFECTS OF SPECTRAL NORMALISATION

Despite the many benefits of smoothness in supervised learning and generative modelling outlined in the previous chapter, smoothness regularisation has only been briefly studied in deep reinforcement learning (DRL).
In this chapter, we study the effects of Spectral Normalisation, a common smoothness regularisation method described in Section <ref>, on DRL.  We use Spectral Normalisation as it has shown tremendous success in GANs, and DRL and GANs share common characteristics, such as operating in non-stationary settings and challenges with optimisation [Czarnecki et al., 2019, Bengio et al., 2020, Mescheder et al., 2017, Miyato et al., 2018]. We find that Spectral Normalisation can lead to improved performance in DRL, as long as it is only applied selectively to a few layers in order to avoid the reduced capacity effects discussed in Section <ref>. Building upon results in Section <ref>, we find interactions between Spectral Normalisation and optimisation dynamics, and show that in DRL the improvements brought by Spectral Normalisation can be obtained by optimisation only changes.
Equipped with this knowledge, we reinvestigate the effect of Spectral Normalisation on GANs, and observe that there Spectral Normalisation plays a compounded role, with model and optimisation changes interacting with the choice of loss function
in intricate ways.

§ INTRODUCTION

Reinforcement Learning (RL) has made astounding progress in recent years, showcasing the ability to play games where alternatives, such as handcrafted search or brute force approaches, are intractable [Silver et al., 2017, Berner et al., 2019, Vinyals et al., 2019].
While this progress could not be achieved without the feature learning aspect of DRL due to a prohibitively large state space or number of actions, research focus has been on RL-specific algorithmic improvements, such as objective functions, exploration strategies, and replay prioritisation [Schaul et al., 2016, 247, Osband et al., 2016, Ostrovski et al., 2017, Bellemare et al., 2017, Dabney et al., 2018, Hessel et al., 2018].
We take a different approach, and focus on the deep aspect of DRL, by investigating the interplay between training neural networks and RL objectives. We do so by exploring the use Spectral Normalisation in DRL; as we have done in previous chapters, we hone in on interactions between smoothness regularisation and optimisation. To this effect, we make the following contributions:

* We show that Spectral Normalisation, when applied to a subset of layers, can improve performance of DRL agents and match the performance of Rainbow [Hessel et al., 2018], a competitive agent combining multiple RL algorithmic advances.

* We show that the effect of selectively applying of Spectral Normalisation to a subset of layers is not solely a smoothness one, but an optimisation one, and can decrease sensitivity to optimisation hyperparameters.

* We introduce a set of adaptations to optimisation methods based on Spectral Normalisation, which without changing the model, can recover and sometimes improve the results of Spectral Normalisation in DRL.

* We use our new insights to re-examine the effects of Spectral Normalisation in GANs, where we observe that normalising the discriminator avoids loss areas of low or high gradient magnitudes, and that Spectral Normalisation interacts with optimisation hyperparameters in important ways.

§ REINFORCEMENT LEARNING

RL translates the problem of acting sequentially in an environment in order to maximise reward into a formal optimisation problem, usually defined via Markov Decision Processes (MDP). An MDP is a tuple
$(\mathcal{S}, \mathcal{A}, P, r, \gamma)$ with $\mathcal{S}$ a set of available states,
$\mathcal{A}$ a set of available actions (which throughout this thesis we will assume to be discrete), $P$ a conditional transition probability or density
$P: \mathcal{S} \times \mathcal{A} \times {S} \rightarrow \mathbb{R}^{+}$, such that
$P(s'|s, a)$ defines the density to transition to state $s'$ from state $s$ if action $a$
is taken by the agent, as well as the unconditional $P(s_0)$ defining the density over initial states. For our use cases, we assume that $P$ is not available in closed form but can be sampled from by obtaining $s' \sim P(\cdot|s, a)$ from an environment simulator. The reward function $r: \mathcal{S} \times \mathcal{A} \rightarrow  \mathbb{R}$ defines the reward $r(s, a)$ obtained by the agent if it takes action $a$ from state $s$ and the discount factor $\gamma \in \mathbb{R}$, with $\gamma \in (0, 1)$.  The goal of RL is to find a policy $\pi$ defined as the conditional probability distribution $\pi: \mathcal{S}\times \mathcal{A} \rightarrow \mathbb{R}^{+}$, where  $\pi(a|s)$ encodes the probability of taking action $a$ if in state $s$ under policy $\pi$, such that the time discounted reward over an episode is maximised:

\begin{align}
\max_{\pi} \mathbb{E}_{P(s_0)} \mathbb{E}_{\pi(a_0|s_0)} \left[r(s_0, a_0) + \sum_{t=1}^{\infty} \mathbb{E}_{P(s_{t}|s_{t-1}, a_{t-1})} \mathbb{E}_{\pi(a_t|s_t)}   \gamma^t r(s_t, a_t) \right].
\label{eq:rl_def}
\end{align}

Directly optimising Eq (<ref>) via Monte Carlo estimation can be challenging as it can lead to high variance estimates of the objectives, as well as slow learning in the case of long episodes [Sutton and Barto, 2018]. Instead, it is common to define state-action value functions as

\begin{align}
Q_{\pi}(s, a) = r(s, a) + \sum_{\substack{t=1,\\ a_0 = a, s_0=s}}^{\infty} \mathbb{E}_{P(s_{t}|s_{t-1}, a_{t-1})} \mathbb{E}_{\pi(a_t|s_t)}   \gamma^t r(s_t, a_t).
\end{align}

State-action value functions satisfy the recurrence relation

\begin{align}
Q_{\pi}(s, a) = r(s, a)+  \gamma \mathbb{E}_{P(s'|s, a)} \mathbb{E}_{\pi(a'|s')} Q_{\pi}(s', a'), \hspace{1em} \forall s \in \mathcal{S}, a \in \mathcal{A},
\label{eq:belman_eq}
\end{align}

known as the Bellman equation.
The objective in Eq (<ref>) can now be written as

\begin{align}
\max_{\pi} \mathbb{E}_{P(s_0)} \mathbb{E}_{\pi(a_0|s_0)} Q_{\pi}(s_0, a_0).
\end{align}

If we denote the optimal policy as $\pi^*$, another Bellman recurrence equation can also be used to find the $Q_\pi^*$, namely the Bellman optimality equation

\begin{align}
Q_{\pi^*}(s, a) = r(s, a)+  \gamma \mathbb{E}_{P(s'|s, a)} \max_{a'} Q_{\pi^*}(s', a'), \hspace{1em} \forall s \in \mathcal{S}, a \in \mathcal{A}.
\label{eq:belman_optim_eq}
\end{align}

Iterative updates ensuring Bellman optimality consistency of the current estimate $Q$ of $Q_{\pi^*}$ form the basis for $Q$-learning algorithms [Watkins and Dayan, 1992]. Since $P(\cdot| s, a)$ is unknown, the expectation in Eq (<ref>) is replaced with a Monte Carlo estimate obtained by performing action $a$ in state $s$ and obtaining $s'$ from the environment; actions are often obtained using the $\epsilon$-greedy policy

\begin{align}
\pi(a|s) = \begin{cases}
1 - \epsilon, \text{if } a = \arg\max_{a'} Q(s, a') \\
\epsilon/(|\mathcal{A}| - 1), \text{otherwise}
\end{cases}
\end{align}

and thus the Bellman optimality updates are evaluated at tuples
${(s, a\sim \pi(\cdot|s), s' \sim P(\cdot| s, a), r = r(s, a))}$.

We note that while here we focus on value based, model-free, offline algorithms, other popular formulations of RL exist, and investigating the effect of smoothness for other algorithm families, including actor-critic and model-based RL, is a worthy area of study; for an overview of RL algorithms, see Sutton and Barto, 2018.

§.§ Deep reinforcement learning

While in traditional RL, often called tabular RL, when estimating a state-action value function individual values are approximated for each $s \in \mathcal{S}$ and $a \in \mathcal{A}$, in DRL $Q(s, a)$ is modelled using a neural network. The advantage of this approach is two fold: first, it makes large state and action spaces—which otherwise would be prohibitive due to memory requirements of storing a value for each state and each action—tractable; and second, it benefits from the generalisation provided by neural network features by learning a similarity measure between states.

One approach to DRL is DQN [Mnih et al., 2015], which adapts the $Q$-learning algorithm to the neural setting, with the objective

\begin{align}
\min_{\vtheta} E(\vtheta) = \mathbb{E}_{(s, a, s', r)\sim \mathcal{R}} \left(Q(s, a; \vtheta) -  \left(r+  \gamma \max_{a'} Q(s', a'; \vtheta)\right)\right)^2,
\label{eq:dqn_loss}
\end{align}

where $\mathcal{R}$ is a replay buffer that stores experiences obtained by acting according to an $\epsilon$ greedy policy induced by $Q$. Since computing the maximum operator requires computing $Q(s, a) \hspace{1em} \forall a \in \mathcal{A}$, the neural critic implementation takes as input a state $s$ and predicts using a forward pass all state-action value functions, thus implementing $Q(\cdot; \vtheta): \mathcal{S} \rightarrow \mathbb{R}^{|\mathcal{A}|}$.
Due to instabilities in training, the target value $r+  \gamma \max_{a'} Q(s', a'; \vtheta)$ is often replaced with a target network $r+  \gamma \max_{a'} Q(s', a'; \vtheta_{old})$, where $\vtheta_{old}$ are a set of parameters obtained previously in training. The target network parameters $\vtheta_{old}$ get updated at regular intervals in training.

Many improvements in DRL have focused on changing RL specific aspects of training, such as finding better approaches to sample from the replay buffer $\mathcal{R}$, by weighing experiences either according to recency or estimated importance [Schaul et al., 2016] [Ostrovski et al., 2018, 247]. Significant progress has also been achieved by changes in loss functions and parametrisations, particularly through a distributional approach to value based learning [Bellemare et al., 2017, Dabney et al., 2021], which updates the Bellman operators to act on a distributional space rather than in expectation as shown in Eq (<ref>). The resulting DQN style agent obtained from the distributional perspective is called CategoricalDQN.
Rainbow [Hessel et al., 2018] is an agent collating many of the above improvements, by combining categorical losses, improved prioritised replay strategies [Schaul et al., 2016], exploration bonuses [247], and other RL specific advances such as double $Q$-learning [Van Hasselt et al., 2016] and disambiguation of state-action value estimates [Wang et al., 2016]. We will show how similar performance improvements can be obtained by focusing on the neural training aspects via changes to the critic modelling the state-action value,
instead of taking an RL centric view.

§.§ Challenges with optimisation in DRL

DRL presents its own unique set of optimisation challenges within the deep learning family.
One challenge stems from non-stationarity and the lack of a unique objective throughout training:
due to the expectation under the policy in loss functions, the loss function itself changes as training progresses; in this aspect, RL is similar to GANs, as the GAN loss also changes as the distribution induced by the generator changes.
In DRL the i.i.d. assumption required to obtain an unbiased estimate of the gradient (see Section <ref>) is also often violated, as data instances might come from the same episode; furthermore it can be shown that in RL the parameter updates might not form a gradient vector field [Czarnecki et al., 2019, Bengio et al., 2020].
Both of these aforementioned issues are mitigated, but not fully resolved, through the use of replay buffers, which accumulate transition pairs required to perform the $Q$-learning update (Eq <ref>) across a long horizon of agent experience. The loss formulation in RL can present an additional challenge: consistency losses where the target value of the function approximator depends on itself, as can be seen in Eq (<ref>), are harder to optimise than standard regression losses where the regression target is provided by the dataset, as is the case in supervised learning.

Despite these specificities of DRL, the optimisation algorithms used are those in standard deep learning and described in Section <ref>, which assume i.i.d. data and the existence of a unique function to optimise. Many a practical implication result as a consequence, including sensitivity to hyperparameterameters [Henderson et al., 2018], the lack of performance of regularisation methods that have been shown to improve optimisation in supervised learning [Bjorck et al., 2018], the heavy reliance on adaptive optimisers such as Adam and RMSprop compared to supervised learning where similar results can be obtained with gradient descent with momentum [Hessel et al., 2018, Hessel et al., 2019].

Inspired by the certain similarities between DRL and GANs, such as non-stationarity, together with the observed common challenges such as sensitivity to hyperparameters, we investigate the use of Spectral Normalisation to alleviate some of the optimisation challenges in DRL. In GANs, Spectral Normalisation has been shown to improve sensitivity to hyperparameters such as learning rate ranges [Miyato et al., 2018], and has been integrated in many state of the art algorithms; for a wider overview of the effects of Spectral Normalisation outside RL, we refer the reader to Chapter <ref>.

§.§ Reinforcement learning environments

We evaluate agents on the Atari ALE benchmark [Bellemare et al., 2013], containing 51 Atari games. The Atari benchmark is often used in DRL, and thus provides useful baselines to serve as a comparison against our methods. Here we use as baselines C51—the CategoricalDQN agent introduced by Bellemare et al., 2017 trained on Atari ALE—and the Rainbow agent [Hessel et al., 2018]—which improves C51 with additional enhancements, providing a strong baseline on this environment. Unless otherwise specified, experiments on Atari use the standard DQN critic architecture and the experimental setting provided by the C51 baseline, shown in the Appendix in Table <ref> and Section <ref>, respectively.

When performing ablation studies using a large setting such as ALE is computationally prohibitive, and we thus use the MinAtar environment [Young and Tian, 2019] instead. MinAtar reproduces five games from ALE without the visual complexity and has been found to be a good testing ground for reproducing ablations made using ALE [Ceron and Castro, 2021]. Unless otherwise specified, MinAtar experiments use the critic architecture described in Table <ref> in the Appendix.

§ SPECTRAL NORMALISATION IN RL

Our aim is to investigate whether the application of Spectral Normalisation in DRL can improve performance, as has been observed in other deep learning domains. To do so, we use Spectral Normalisation applied to neural critics in Q learning algorithms; for a description of Spectral Normalisation, see Section <ref>. The Spectral Normalisation formulation we use is largely based on the one proposed in the original paper Miyato et al., 2018, with a few alterations: we do not backpropagate through the power iteration operation; we only apply the normalisation if the spectral norm of a layer is larger than 1; for convolutional layers we do not reshape the 4 dimensional filter tensors to a two-dimensional matrix and compute the spectral norm of the newly obtained linear operator but estimate the of the original convolutional operator instead [Gouk et al., 2020][This only applies to the RL experiments in this section, and not to any other Spectral Normalisation experiments in the thesis. We also note that the majority of the results in this section apply normalisation to linear layers, yielding them comparable with the other presented results.].
Code available to reproduce our results is available at <https://github.com/floringogianu/snrl>.

§.§ Applying Spectral Normalisation to a subset of layers

When we started experimenting with applying Spectral Normalisation to the DQN critic, we applied Spectral Normalisation to all layers, as is standard in GANs [Miyato et al., 2018]. We quickly noticed, however, that imposing the hard smoothness constraint on the state-action value function to be 1-Lipschitz can substantially decrease performance. As we have observed in Section <ref>, enforcing a 1-Lipschitz constraint can reduce a model's capacity to capture the decision surface and decrease performance (Figure <ref>);  relaxing the constraint by forcing the model to be 10-Lipschitz can mitigate this loss of performance (Figure <ref>). Similar observations have been made by Gouk et al., 2020, who propose introducing a hyperparameter that determines the strength of the Lipschitz constraint.
We take a different approach here, where instead of changing the Lipschitz constant as a hyperparameter, we choose to only normalise certain layers of the network, most often just one. In particular we observe that normalising the last layer of the network is detrimental. This suggests that imposing a smoothness constraint on the $Q$ function is prohibiting the model from approximating the required decision surface. In the case of Atari games we study here  this is not entirely unexpected, since similar input states can lead to a drastically different game outcome. The expected reward of a particular action $a$ can be determined by a few pixels, such as the location of the ball and paddle in Pong, and that of the ghost in MS-PacMan. Thus, even for states $s, s'$ such that $||s - s'||$ is small, $||Q(s, a; \vtheta) - Q(s', a; \vtheta)||$ can be large, making the optimal $Q$ function non-smooth.

Instead of normalising the entire network, we instead normalise only a few layers.
Experimentally we found that Spectral Normalisation applied to a DRL critic performs best on the layer with the largest number of parameters; for the standard DQN architecture this is the penultimate layer [Mnih et al., 2015, Hessel et al., 2018]. We thus denote the index of the Spectral Normalised layers from the bottom of the network, i.e.  will refer to a critic where Spectral Normalisation is applied to the output layer and  to the penultimate layer, while  refers to a network where Spectral Normalisation is applied both the penultimate layer and the one preceding it.

§.§ Experimental results on the Atari benchmark

[Average HNS in training.]

[Mean and Median HNS.]

Agent                                      Mean                 Median

DQN [Wang et al., 2016]                 216.84               78.37

DQN-Adam$^{\ast}$                          358.45               119.45

DQN-Adam SN[-2]                            719.95      178.18

C51 [Hessel et al., 2018]             523.06               146.73

C51 [Bellemare et al., 2017]     633.49               174.84

C51$^{\ast}$                               778.68               182.26

Rainbow [Hessel et al., 2018]         855.11               227.05

C51 SN[-2]                                 1073.18     248.45

[Adding Spectral Normalisation to C51 improves the agent's performance on Atari.]Selectivly adding Spectral Normalisation to RL agents improves their performance.
fig:c_51_icml_ale_g54_hns_cropped: Average Human Normalised Score (HNS) per time-step for C51 with Spectral Normalisation.
fig:c_51_icml_ale_g54_hns_cropped_avg: Mean and median Human Normalised Score on  Atari games with random starts evaluation. We observe that applying Spectral Normalisation to the penultimate layer of the critic leads to a significant performance boost both for DQN and C51, and rivals algorithm improvements obtained by Rainbow. References indicate the sources for the scores for each algorithm.
We mark our own implementations of the baseline with $^*$. Agents are evaluated with the protocol in [Hessel et al., 2018]; all results use an average over  ALE games.

We assess the effect of applying Spectral Normalisation to the critic both for the standard DQN as well as its distributional counterpart (C51) when trained on the ALE benchmark containing 54 Atari games and show results in Figure <ref>.
We consistently observe that  improves over the baseline significantly. Furthermore,  provides a significant improvement over  Rainbow [Hessel et al., 2018], a competitive RL agent based on C51 combining multiple competitive RL specific techniques.
We further show in Figure <ref> that  leads to better results when trained longer, as opposed to the un-normalised DQN which plateaus earlier in training, and towards the end of training has a decrease in performance. Figures <ref> and <ref> show that, while normalising the layer with the largest number of parameters——performs best, normalising other layers also significantly improves performance over the baseline DQN agent. For all experiments in Figure <ref>, when applying Spectral Normalisation we use the same hyperparameters as the baseline, without retuning hyperparameters. These results suggest that Spectral Normalisation can be added to existing performant DRL training configurations without requiring a new hyperparameter search.

[Atari environment.]

[MinAtar environment.]

[Selectively applying Spectral Normalisation to one layer leads to significant improvements over a DQN agent trained with Adam.]Selectively applying Spectral Normalisation to one layer leads to significant improvements over a DQN trained with Adam. While the baseline plateaus early in training, when applying Spectral Normalisation the agents continue to improve throughout training. fig:atari_dqn_ale_g54_hns: Human Normalised Score for a DQN-Adam baseline with Spectral Normalisation applied on three different layers. Average over  Atari games.
fig:min_atar_dqn_ale_g54_hns: On a $15$M steps training on MinAtar; each line is an average of 10 seeds over four MinAtar games and four different model sizes.

[Spectral Normalisation shows gains for all model sizes when applied to a DQN agent on MinAtar.]Spectral Normalisation shows gains for all model sizes. Looking at the baseline (solid,line width=1.5pt,538blue DQN), we observe two performance regimes on MinAtar: for shallow, depth 3 models, performance increases with the width of the model; for deeper models performance generally stagnates with increasing depth and width. In both regimes applying SN on individual (solid,line width=1.5pt,538red, solid,line width=1.5pt,538yellow) or multiple (solid,line width=1.5pt,538purple) layers improves upon the baseline suggesting a regularisation effect we could not reproduce with other regularisation methods. Notice that the strong regularisation resulted from applying Spectral Normalisation to input layers (solid,line width=1.5pt,538green) or too many layers (solid,line width=1.5pt,538grey) can however degrade performance. Each line is an average over normalised scores of 4 games $\times$ 10 seeds.

In order to assess the performance of Spectral Normalisation beyond the standard DQN network, we perform a sweep over architectures and consistently observe that Spectral Normalisation improves performance when applied to a range of architectures, as shown in Figure <ref>; here we use 12 different model sizes of three different model depths and four different layer widths.

§.§ An optimisation effect

While selectively applying Spectral Normalisation to a subset of layers of a $Q$-learning critic is a simple intervention, we have seen in the previous section that it has a strong effect on performance. We now aim to understand why Spectral Normalisation leads to these improvements. We first start with the smoothness hypothesis, considering whether the performance improvement is due to an increased smoothness of the critic. We note, however, that unlike other applications of Spectral Normalisation which normalise the entire network, selectively applying Spectral Normalisation to a subset of layers as we do here does not lead to any guarantee regarding the smoothness of the entire critic. Indeed, since there are no constraints on the other layers, the smoothness of those layers could increase throughout training to compensate for the constraint on the normalised layers. When aggregating over the games in MinAtar  we observe $75\%$ of applications of  decrease the smoothness of the model—as approximated by the maximum norm of the critic's Jacobian with respect to inputs over a large set of state-action pairs, for a connection between input Jacobians and Lipschitz smoothness, see Section <ref>—when controlling over hyperparameters; for certain games it is as high as 90%, while for others as low as $58\%$. We also observe that applying Spectral Normalisation to more layers do not always increase smoothness in Table <ref>.  Furthermore, we notice that while applying Spectral Normalisation increased performance for all games in MinAtar, there is not a strong effect between smoothness and performance as measured by the Spearman-rank correlation between the smoothness of the learned model and the best performance obtained by the agent in all games, as we show in Table <ref>. To further assess the effect of the critic smoothness on performance, we used gradient penalties as a soft constraint to encourage smoothness (see Section <ref> for more details on gradient penalties), which did not result in any significant benefit compared to the baseline, as we show in Figure <ref> in the Appendix.

3cLess or no normalisation

1|cNo normalisation     1|cSN[-2]    1|c|SN[-3]

[t]2mm3*[origin=c]90More SN       1|cSN[-2]     1|c|74.6%     1c|     1c|

1|cSN[-3]    1|c|69.2%      1c|      1c|

1|cSN[-2, -3]      1|c|75%     1c|57%      1c|60%

[The percentage of training settings for which applying Spectral Normalisation to more layers leads to smoother networks, as measured by the model's Jacobian at peak performance.]The percentage of training settings (architectures and seeds) for which applying Spectral Normalisation to more layers leads to smoother networks, as measured by the model's Jacobian at peak performance. Selectively applying Spectral Normalisation to only a subset of layers does not consistently lead to an increase in smoothness, and neither does applying Spectral Normalisation to two layers compared to only one layer.
Results are obtained from a sweep over architectures detailed in Table <ref>, with 10 seeds each.

Game       Spearman Rank

Asterix             0.129

Breakout            0.199

Seaquest            0.151

Space Invaders      0.453

[Spearman Correlation coefficient between the negative norm of the Jacobian and peak performance for each game.]
Spearman Correlation coefficient between the negative norm of the Jacobian (our measure of decreased smoothness) and peak performance for each game. Higher means more correlation. We don't consistently observe a strong correlation between performance and increased smoothness across games.

The above evidence suggests that the increased performance from the application of Spectral Normalisation to certain critic layers in DRL might not be fully explainable due to an increased smoothness effect. To better understand why Spectral Normalisation helps DRL, we turn our attention to the possibility of an increase in performance due to an improvement in optimisation; we have already seen in Section <ref> that Spectral Normalisation can interact with learning rate and momentum decay rates in supervised learning and in GANs. In RL, we show in Figure <ref> that using Spectral Normalisation allows for longer training without early plateaus, and that applying Spectral Normalisation to existing choice of hyperparameters leads to an increase of performance without requiring an additional hyperparameter sweep, as shown in the results in Figure <ref>. To investigate whether Spectral Normalisation has an effect  on hyperparameter sensitivity of DQN agents, we perform a large sweep over Adam hyperparameters learning rate $h$ and $\epsilon$ (for an overview of Adam see Section <ref>) and show that indeed, applying Spectral Normalisation increases the range of performant hyperparameters significantly; results are shown in Figure <ref>.

[Spectral Normalisation can significantly decrease hyperparameter sensitivity of DQN when the Adam optimiser is used.] SN[-2] applied to DQN, Spectral Normalisation applied to the largest layer in the DQN critic, can significantly decrease sensitivity to the learning rate and $\epsilon$ hyperparameter of Adam. The cross product of learning rates in $h \in \{0.00001, ..., 0.00215\}$ and in $\epsilon \in \{0.00001, ..., 0.01\}$ is explored.

In order to further investigate the effect of Spectral Normalisation in DRL training, we develop a set of methods which independently assess its effects. To this end, consider the neural network to which Spectral Normalisation is applied, which we assume has $N$ layers, with weights $\vW_i \in \mathbb{R}^{d_{i+1} \times d_{i}}, \vb_i \in \mathbb{R}^{d_{i+1}}$:

\begin{align}
\vo & = \vW_N \vh_{N-1} + \vb_{N} \\
\vh_{N-1} &= a(\vz_{N-1}) = a(\vW_{N-1}\vh_{N-2} +  \vb_{N-1}) \\
& \cdots \\
\vh_{1} &= a (\vz_{1}) = a(\vW_{1} \vh_{0} +  \vb_{1}),
\end{align}

with $\vh_{0} = \vx$ and $a$ is an activation function applied element-wise to the input vector. The activation $a$ has to be a rectifier, such as ReLU [Nair and Hinton, 2010] or Leaky ReLU [Xu et al., 2015], since we rely on $a(\sigma_l \vx) = \sigma_l a(\vx)$, with $\sigma_l > 0$. We can write our optimisation problem as:

\begin{align}
\min_{\vtheta} E(\vtheta) = E(\vo;\vtheta = \{\vW_{1 \le i \le N}, \vb_{1 \le i \le N}\}).
\end{align}

We assess the effect of applying Spectral Normalisation to layer $l$,  but note the same derivation applies when multiple layers are normalised. We note that for simplicity we assumed above that the model is an MLP, though the same computation carries for convolutional layers.
The analysis that follows relies on the following observation:
In a neural network with recitifer activation functions, if the bias term of a layer where Spectral Normalisation is applied gets adjusted to account for the normalisation, Spectral Normalisation can be seen as scaling the output of the layer by the inverse of the spectral norm $\sigma_l$.

To see why, consider $\vh_{l+1} = a(\vW_{l} \vh_{l+1} + \vb_{l})$ and its normalised counterpart:  $\vh^{'}_{l+1} = a(\vW_{l}/\sigma_l \vh_{l+1} + \vb_{l})$. Since we chose the activations function such that $a(\vh/\sigma_l) = a (\vh)/\sigma_l$, we observe that if we also scale the bias $\vb_l$ by $1/\sigma_l$, we can obtain $\vh^{'}_{l+1} = \vh_{l+1}/\sigma_l$. Furthermore, if we apply the same bias scaling to subsequent layers $\vb_{i} \rightarrow \vb_{i} /\sigma_l, \forall i \ge l$, we obtain that $\vh'_i = \vh_i/\sigma_l$, including $\vo' = \vo/\sigma_l$. Thus if we assume that the bias vectors can be scaled by a constant in training, the effect of Spectral Normalisation is to scale each activation following the normalisation by the inverse of the spectral norm of the normalised layer; if multiple layers are normalised, activations are scaled by inverse of the product of the spectral norm of the normalised layers. We note that the bias scaling assumption does not change how expressive the model can be, as the bias term could learn such as scaling through training. Indeed, we test this assumption empirically and use a procedure we term divOut, in which instead of applying Spectral Normalisation, we divide the model output by the product of the spectral norms of the normalised layers $\mathcal{\rho}$:

\begin{align}
\textsc{divOut}[\mathcal{\rho}]: \hspace{1em} \min_{\vtheta} E(\vtheta)= E(\frac{\vo}{\prod_{s \in \mathcal{\rho}}{\sigma_s}}; \vtheta ).
\end{align}

We investigate where divOut can perform similarly to its Spectral Normalisation counterparts and show in Figure <ref> that in offline reinforcement learning $\textsc{divOut}[\mathcal{\rho}]$ and $\texttt{SN}[\mathcal{\rho}]$ have similar behaviours.

[One normalised layer.]

[Multiple normalised layers.]

[The effect of divOut, divGrad and mulEps on RL performance on MinAtar.]The effect of divOut, divGrad and mulEps on RL performance on MinAtar. Despite not changing the model, but only changing the optimisation procedure based on the effect Spectral Normalisation has on parameter updates, divGrad and mulEps perform comparable to, or better than, Spectral Normalisation. fig:mul_eps_1 shows results obtained from simulating optimisation effects of Spectral Normalisation when applied to one layer, where divGrad and mulEps and divOut obtain similar performance performance to Spectral Normalisation, and significantly improve over the baseline. fig:mul_eps_2 shows results obtained when looking at the optimisation effects of applying Spectral Normalisation to multiple layers; here Spectral Normalisation hurts performance, and so does divOut, but divGrad and mulEps still significantly improve performance compared to the baseline. This suggests that large changes model output obtained by Spectral Normalisation and divOut can be detrimental, while optimisation only changes are beneficial in that setting.

We now turn our attention towards the effects that Spectral Normalisation has on the model gradients. To do so, we would like to compute $\frac{d E}{d \vW_i}$ and $\frac{d E}{d \vb_i}$ for normalised and un-normalised networks. As before, for simplicity we consider the situation of one normalised layer $l$ and we assume bias scaling. We then have

\begin{align}
\vo' = \vo/\sigma_l; \hspace{3em} \vh'_{i} = \vh_{i} /\sigma_l, \hspace{0.5em}\forall i \ge l; \hspace{3em} \vh'_{i} = \vh_{i}, \hspace{0.5em}\forall i < l.
\label{eq:scaling_sn}
\end{align}

While the computational graph only changes at layer $l$ where the ${\vh_{l} = a(\vW_{l} \vh_{l-1} +  \vb_{l})}$ is now replaced with

\begin{align}
\vh_{l}' = a(\vz_{l}') = a(\vW_{l}/\sigma_l \vh_{l-1} +  \vb_{l}/\sigma_l)= a(\vW_{l}\vh_{l-1} +  \vb_{l})/\sigma_l,
\label{eq:normalisation_sn}
\end{align}

the evaluation of the higher level derivatives will also change due to the scaling effect in Eq (<ref>). To make the changes in the computational graph due to the normalisation explicit, we will call the loss with the normalisation $E'$. We are interested in computing $\frac{d E'}{d \vW_i}$ and $\frac{d E'}{d \vb_i}$, and comparing it with the backpropagation in an un-normalised model

\begin{align}
\frac{d E}{d \vW_N} &=   \frac{d E}{d \vo} \vh_{N-1} ^T \label{eq:backprop_first}\\
\frac{d E}{d \vh_{N-1}} &= \frac{d \vo}{d \vh_{N-1}}^T \frac{d E}{d \vo} = \vW_{N}^T \frac{d E}{d \vo}  \\
\frac{d E}{d \vW_i}
&= \frac{d E}{d \vz_{i}} \vh_{i-1}^T =  \left(\frac{d E}{d \vh_{i}} \odot a'(\vz_{i})\right)\vh_{i-1}^T \hspace{2em} i < N \\
\frac{d E}{d \vh_{i-1}} &= \frac{d \vz_{i}}{d \vh_{i-1}}^T \frac{d E}{d \vz_{i}}   = \vW_i^T \left(\frac{d E}{d \vh_{i}} \odot a'(\vz_{i})\right) \hspace{2em} i < N. \label{eq:backprop_last}
\end{align}

When normalisation is applied, the computational graph does not change for the layers following the normalisation compared to the un-normalised case, but the evaluation of the derivatives changes due to the scaling  in Eq (<ref>)

\begin{align}
& \frac{d E'}{d \vo'}(\vo') = \frac{d E}{d \vo}(\vo / \sigma_l) \label{eq:jacobian_out_change} \\
&\frac{d E'}{d \vW_N} = \frac{d E'}{d \vo'} {\vh'_{N-1}} ^T =  \frac{d E'}{d \vo'} \left( \underbrace{\vh_{N-1}/\sigma_l}_{\eqref{eq:scaling_sn}} \right)^T =  \frac{1}{\sigma_l} \frac{d E'}{d \vo'} \vh_{N-1} ^T \\
&\frac{d E'}{d \vh'_{N-1}} = \vW_{N}^T \frac{d E}{d \vo}(\vo / \sigma_l)   \\
&\frac{d E'}{d \vW_{i}} =\left(\frac{d E'}{d \vh'_{i}} \odot a'(\vz'_{i}) \right){\vh'_{i-1}}^T = \frac{1}{\sigma_l}\left(\frac{d E'}{d \vh'_{i}} \odot a'(\vz_{i}) \right){\vh_{i-1}}^T, \hspace{1em} i > l. \label{eq:normalisation_sn_after}
\end{align}

For the normalised layer $l$, we have that due to Eq (<ref>)

\begin{align}
&\frac{d E'}{d \vW_l}
=  \frac{d E'}{d \vz'_{l}} \underbrace{{\vh'_{l-1}}^T/\sigma_l}_{normalisation, \eqref{eq:normalisation_sn}} = \frac{1}{\sigma_l} \left(\frac{d E'}{d \vh'_{l}} \odot a'(\vz_{l})\right)\vh_{l-1}^T  \label{eq:normalisation_sn_exact_layer}\\
&\frac{d E'}{d \vh'_{l-1}} = \underbrace{\frac{1}{\sigma_l} \vW_l^T}_{normalisation, \eqref{eq:normalisation_sn}} \left(\frac{d E'}{d \vh'_{l}} \odot a'(\vz'_{l})\right) .
\end{align}

For the layers before the normalisation, we have

\begin{align}
\frac{d E'}{d \vW_i}
&=  \left(\frac{d E'}{d \vh'_{i}} \odot a'(\vz_{i})\right)\vh_{i-1}^T \hspace{2em} i < l \label{eq:eq:normalisation_sn_before}\\
\frac{d E}{d \vh'_{i-1}} &=  \vW_i^T \left(\frac{d E'}{d \vh'_{i}} \odot a'(\vz_{i})\right) \hspace{2em} i < l.
\end{align}

Thus, when comparing the gradients obtained with the normalised network with those in an un-normalised network, we observe two changes: first, a change in the output Jacobian (Eq (<ref>)), and second, a scaling effect which applies to all layers in the network, either through the scaling of the activations for layers following the normalisation (Eq (<ref>)), through the changes in the computational graph for the normalised layer (Eq (<ref>)), or through the effect of backpropagation of the scaling of $\frac{d E'}{d \vh'_{l-1}}$, for the layers preceding the normalisation (Eq (<ref>)).  A similar argument can be made for biases.
While the change in Jacobian is difficult to obtain without affecting the model as we have done with divOut, to capture the gradient scaling effect we propose divGrad, a normalisation scheme based on the effects of applying Spectral Normalisation which does not change the model, but only changes the optimisation procedure, by scaling the gradients of the parameters:

\begin{align}
\textsc{divGrad}[\mathcal{\rho}]: \hspace{1em} \frac{d E}{d \vtheta_i} \rightarrow \frac{1}{\prod_{i \in \mathcal{\rho}} \sigma_i}\frac{d E}{d \vtheta_i}.
\label{eq:div_grad}
\end{align}

Results in Figure <ref> show that divGrad performs well and that it can outperform Spectral Normalisation or divOut on MinAtar; further results supporting this hypothesis are shown in Figure <ref> in the Appendix.

The above observation regarding gradient scaling also allows us to intuit the effect of Spectral Normalisation in conjunction with optimisers like Adam (for a detailed description of the Adam optimiser, see Section <ref>). If we consider that the spectral norm of a weight matrices changes slowly in training (which we verify empirically in Figure <ref>), under the bias scaling assumption, the effect of Spectral Normalisation on the Adam update can be seen as

\begin{align}
\vm'_t &= \beta_1 \vm'_{t-1} + (1 - \beta_1) \nabla_{\vtheta}E(\vtheta_{t-1})/ \sigma \approx \vm'_t/\sigma \\
\vv'_t &= \beta_2 \vv_{t-1} + (1 - \beta_2) \nabla_{\vtheta}E(\vtheta_{t-1})^2 \approx \vv'_t/\sigma^2\\
\Delta \vtheta'_t &=  h \frac{\frac{1}{1 - \beta_1^t} \vm'_t}{\sqrt{\frac{1}{1 - \beta_2^t}\vv'_t} + \epsilon} =  h \frac{\frac{1}{1 - \beta_1^t} \vm_t}{\sqrt{\frac{1}{1 - \beta_2^t}\vv_t} + \sigma \epsilon},
\label{eq:mul_eps}
\end{align}

where $\sigma = \prod_{i \in \mathcal{\rho}} \sigma_i$, the product of the spectral norms of the normalised layers and we used element-wise operations. Thus, the effect on the Adam update is reflected in a scaling of the hyperparameter $\epsilon$ by $\sigma$.
To investigate this effect on the Adam optimiser, we introduce mulEps, which changes the Adam update by multiplying $\epsilon$ by the product of the spectral norms of the normalised layers. We show in Figure <ref> that mulEps performs similarly to selectively applying Spectral Normalisation in DRL, and can improve upon it. A strong effect is particularly observed when mulEps and Spectral Normalisation are applied to multiple layers (Figure <ref>), where Spectral Normalisation decreases performance compared to the baseline, while mulEps increases it. Thus, mulEps, provides another example of how we can use Spectral Normalisation to derive optimisation only changes that lead to improvements in performance in DRL.

§ REVISITING SPECTRAL NORMALISATION IN GANS

By analysing the effect of Spectral Normalisation in the previous section, we have uncovered multiple effects: model effects such as output scaling (Eq (<ref>)), and optimisation effects such as gradient scaling (Eq (<ref>)) and interactions with optimisation hyperparameters such as $\epsilon$ in Adam (Eq (<ref>)). We saw that in DRL the effects of Spectral Normalisation can be recovered through the use of optimisation schemes, such as  divGrad and mulEps, derived based on the optimisation only effects of Spectral Normalisation. Since Spectral Normalisation was first introduced for GANs, and indeed is a key component of many successful GANs [Zhang et al., 2019, Brock et al., 2018], it is only natural to ask whether the same optimisation methods perform equally well when training GANs. We studied GANs previously and described them in Section <ref>, and the interactions between smoothness normalisation and optimisation in GANs have been discussed in Chapter <ref>. The application of Spectral Normalisation is different in the GAN setting compared to RL, in that in GANs it is applied to every layer of the model[When Spectral Normalisation was introduced, it was only applied to the discriminator, but since it has also been applied to the generator; here, for consistency with the Spectral Normalisation baseline in Miyato et al., 2018, we apply it only to the discriminator.]. This difference between the DRL and GANs is significant, since applying Spectral Normalisation on every layer ensures the model is Lipschitz (at least when Spectral Normalisation is applied on the linear operator given by convolutional layers and not on the reshaped filters), while applying it to only one layer leads to no such assurances, as we have seen in the previous section. This difference in application of Spectral Normalisation suggests perhaps that the change in the model is important in GANs. To test this intuition, we experimented with optimisation only methods divGrad and mulEps in GAN training. We note that as the generator's backpropagation requires a backward pass through the discriminator, any normalisation applied to the discriminator in mulEps and divGrad will also affect the generator, as was the case with un-normalised early layers in the RL critic (see Eqs (<ref>) and (<ref>)).
Results in Figure <ref> confirm that indeed, methods that only make changes to optimisation dynamics and do not account for model changes induced by Spectral Normalisation do not recover its performance in GAN training.

[Spectral Normalisation.]

[No normalisation.]

[Optimisation changes based on Spectral Normalisation do not recover the performance of Spectral Normalisation in GANs.]Optimisation changes based on Spectral Normalisation do not recover the performance of Spectral Normalisation in GANs. Different units indicate different learning rates for the discriminator and generator.

§.§ Spectral Normalisation and the discriminator output

Since optimisation only changes do not recover the performance of Spectral Normalisation in GAN training, we now investigate whether Spectral Normalisation alters the loss prediction landscape in a substantial way.
We start by considering the effect of Spectral Normalisation on the range of discriminator outputs. Since Spectral Normalisation applies a global constraint on the entire space, this applies
between pairs of data instances, pairs of samples, and pairs of data and samples.
If we write $D(\cdot;\vphi) = \varsigma(D_L(\cdot;\vphi))$, with $\varsigma$ being the sigmoid function, Spectral Normalisation ensures that $D_L(\cdot;\vphi)$ is 1-Lipschitz by normalising each layer in the discriminator's network. Given
a generator sample $G(\vz;\vtheta)$ and a data instance $\vx$, $\norm{D_L(G(\vz;\vtheta);\vphi) - D_L(\vx;\vphi)}_2$ is bound by $\norm{G(\vz;\vtheta) - \vx}_2$.
Thus, while with no normalisation the discriminator has an easier task of separating the data and samples by using the saturating areas of the sigmoid function, this is harder to do when Spectral Normalisation is used;
we visualise this effect in Figure <ref>.

[No normalisation.]

[Spectral Normalisation.]

[The effect of Spectral Normalisation on discriminator predictions.]Visualisation of the effect of Spectral Normalisation on discriminator predictions: Spectral Normalisation is making the discriminator output less likely to reach the saturating areas of the sigmoid function, denoted here by $\varsigma$.

We now turn to empirically investigating this effect in GAN training. We measure the output of the discriminator throughout training both on samples and data batches and create a binned-histogram of the outputs obtained from a batch. That is, for each $\vx_i$ in a data batch with $D(\vx_i;\vphi) \in [0, 1]$ we assign it the interval $[0.1 p, 0.1 (p+1)]$ with $p \in \{0, ..., 9\}$ if $D(\vx_i;\vphi) \in [0.1 p, 0.1 (p+1)]$; we do the same for samples $D(G(\vz_i;\vtheta);\vphi)$ where $\vz_i$ are the latent vectors used to obtain the sample batch.
This allows us to measure the variability of the discriminator prediction inside data and sample batches; we measure the entropy of the discriminator output across a batch with and without Spectral Normalisation by measuring the entropy of the distribution induced by the histogram. We show aggregate results throughout training over a hyperparameter sweep in Figure <ref>, and individual results with a fixed set of hyperparameters in Figures <ref> and <ref>.
As we intuited, Spectral Normalisation increases the entropy of the discriminator output throughout training, both on data (Figure <ref>) and samples (Figure <ref>). Early in training (Figure <ref>), discriminators trained with Spectral Normalisation are less likely to assign high probability to real data being real, or to samples being fake. Late in training (Figure <ref>), GANs trained with Spectral Normalisation also exhibit higher entropy of discriminator outputs; this end of training behaviour is more consistent to that of a Nash equilibrium (see Section <ref> for a definition and discussion on Nash equilibria), where
the discriminator should not be able to distinguish between samples and data.

Given the effect of Spectral Normalisation on the discriminator's predictions, it's natural to ask how this impacts training. We turn to this question next.

[Entropy on data.]

[Entropy on samples.]

[Spectral Normalisation increases the entropy of the discriminator's predictions on data and samples throughout training.]Spectral Normalisation increases the entropy of the discriminator's predictions on data fig:spectral_norm_entropy_data and samples fig:spectral_norm_entropy_samples. The results are obtained over a sweep of learning rates.

[Spectral Normalisation increases the entropy of the discriminator's predictions on data and samples in the early stages of training.]Early in training. Spectral Normalisation increases the entropy of the discriminator's predictions on data fig:data_hist_early and samples fig:samples_hist_early in the early stages of training. Without Spectral Normalisation the discriminator is confident that the generator samples are fake, with most samples being assigned less than 0.3 probability of being real.

[Spectral Normalisation increases the entropy of the discriminator's predictions on data and samples in the late stages of training.]Late in training. Spectral Normalisation increases the entropy of the discriminator's predictions on data fig:data_hist_late and samples fig:samples_hist_late in the late stages of training. Without Spectral Normalisation the discriminator is confident that real data is real and generator samples are fake. When Spectral Normalisation is used, the discriminator  assigns both data and samples a wide range of probability of being real.

§.§ Interactions with loss functions

[Understanding the landscape of GAN losses and gradients: comparing the saturating and non-saturating generator loss. ]Understanding the landscape of GAN losses and gradients. fig:losses_gan_losses: comparing the saturating and non-saturating generator loss. fig:grads_gan_losses: unlike the saturating loss, the non-saturating loss provides stronger gradients when the discriminator can easily classify generated data as fake.

To examine the effect of the increased entropy on the discriminator's output, we use two formulations of GAN losses: the non-saturating loss (Eq (<ref>)),  more commonly used in practice and in the above experiments; and the original zero-sum formulation of GANs (Eq (<ref>)), which has been known to be harder to train than other losses.
The low performance of this original loss has been attributed to the lack of learning signal the generator early in training, since when the generator performs poorly and the discriminator easily classifies its data as fake, the discriminator does not provide strong gradients for the generator to improve, as we visualise in Figure <ref>;
for this reason, the generator loss in this formulation is sometimes called the `saturating loss'.
Moreover, strong gradients are provided when the generator is doing well, which can lead to unstable behaviour and exiting areas of good performance. Figure <ref> also highlights why the increased entropy effect in the discriminator's output induced by Spectral Normalisation—and specifically the decreased probability of assigning outputs close to $0$ or $1$ observed in Figures <ref> and <ref>—can be beneficial, as for both losses, it avoids areas with large or small gradient magnitudes.

By analysing the interaction between the loss function and the behaviour of the discriminator, we can now make predictions about the empirical behaviours of the two losses. For the saturating loss, without Spectral Normalisation the challenge is that early in training there is no learning signal for the generator; we thus would expect that without Spectral Normalisation the performance is low, and that Spectral Normalisation improves is significantly by avoiding the saturated areas early in training. We observe this in Figure <ref>, which shows that without Spectral Normalisation the saturating loss exhibits extremely poor performance, but that adding Spectral Normalisation significantly decreases the gap between the saturating and non-saturating losses. For the non-saturating loss, we expect that without Spectral Normalisation, the discriminator can be too confident in its prediction that generated data is fake late in the game, as we observed in Figure <ref>. This leads to large gradients—see Figure <ref>—which can destabilise training and exit areas of good performance. This expectation is consistent with what we observe empirically in Figure <ref>: adding Spectral Normalisation improves stability later in training.

[Spectral Normalisation.]

[No normalisation.]

[DivOut, discriminator update only.]

[Only applying the Jacobian change to the discriminator only leads to extremely poor performance when the saturating loss is used.]Saturating loss. Spectral Normalisation improves performance of GANs trained with the saturating loss. divOut obtains similar performance as Spectral Normalisation, but only when applied to both the discriminator and the generator. Only applying the output scaling from divOut to the discriminator only leads to extremely poor performance, as it does not affect the generator update, and thus does not avoid the areas with poorly conditioned generator gradients. Different units indicate different learning rates for the discriminator and generator. The training optimiser is Adam, used with simultaneous updates.

[Spectral Normalisation.]

[No normalisation.]

[DivOut, discriminator update only.]

[DivOut obtains similar performance to Spectral Normalisation for GANs on CIFAR-10 when the non-saturating loss is used.]Non-saturating loss. DivOut obtains similar performance to Spectral Normalisation for GANs on CIFAR-10 when the non-saturating loss is used. Different units indicate different learning rates for the discriminator and generator. Only applying the output scaling from divOut to the discriminator leads to similar performance as when applying it to both the discriminator and the generator, since the non-saturating loss makes the generator less susceptible to the scale of the discriminator output, unlike for the saturating loss as we saw in Figure <ref>.  The training optimiser is Adam, used with simultaneous updates.

We are now ready to return to the optimisation methods we derived in Section <ref> based on Spectral Normalisation. Since divOut captures the changes in the model output induced by Spectral Normalisation,
we would expect divOut to perform well for GANs trained on CIFAR-10. In particular, by dividing the discriminator output by the product of the spectral norms of the discriminator's weights, divOut captures the intuition present in Figure <ref>: it ensures that data and generator samples are less likely to be separated and reach the saturating areas of the sigmoid function.  Indeed, as we show in Figures <ref> and <ref>, divOut obtains a similar performance to Spectral Normalisation both for the saturating and non-saturating loss. Importantly, however, when applying divOut only to the discriminator update, divOut obtains extremely poor performance in the case of the saturating loss as we show in Figure <ref>, but
still performs on par with Spectral Normalisation when the non-saturating loss is used, as seen in Figure <ref>. This further confirms that in the case of the saturating loss, one of the effects of Spectral Normalisation is to change the conditioning of the generator by avoiding the areas with low magnitude gradients early in training. We are also ready to revisit the mulEps results with the non-saturating loss presented in Figure <ref>; since mulEps does not capture the changes in discriminator output, it will not be able to avoid the decrease in performance observed when no Spectral Normalisation is used.

We thus see that in the GAN case, there is a strong effect in model training brought  by Spectral Normalisation, which does not come from an only optimisation change. We now turn our attention to the following question: even if in GANs Spectral Normalisation does not lead to a primarily optimisation effect, are GANs potentially benefiting from the optimisation changes brought by Spectral Normalisation?

§.§ Hypothesis: Adam in the low-curvature regime

We have seen in previous sections that Spectral Normalisation can be seen as acting to multiply the hyperparameter $\epsilon$ of Adam (Eq (<ref>)). Since the spectral norms of weight matrices grow in training, this can be seen as an anneal of $\epsilon$ from small to large. In the previous section we have seen that in the GAN case the scheduler derived from this observation,  MulEps, does not recover the performance of Spectral Normalisation in GANs. Now we ask whether the $\epsilon$ annealing behaviour of Spectral Normalisation can still have a positive effect on GAN training, despite not being the only effect.

We start with a few observations. First, when a small $\epsilon$ is used, for dimensions of low-curvature Adam leads to a constant update given by the learning rate. Second, GANs trained with Adam exit the area of high performance, even when Spectral Normalisation and the non-saturating losses are used, as we show in Figure <ref>. Third, this behaviour is not observed when gradient descent or Runge–Kutta4 are used (see Figure <ref> and Qin et al., 2020), so this behaviour seems specific to the use of the Adam optimiser. These observations lead to us to postulate the following hypothesis: Is Adam exiting the areas of high performance in GAN training because many parameters are in a low-curvature regime, and taking a step of size given by the learning rate is then leading to an exit from the high performance area?

To first understand the effect of $\epsilon$ in Adam in the low-curvature regime, we use the arguments from Section <ref>. If we are in a low-curvature regime for parameter $\vtheta_{[l]} \in \mathbb{R}$, then by definition its gradient $\nabla_{\vtheta_{[l]}} E$ does not change between iterations. We use this to expand $\vm_t$ in the Adam update, defined in Eq (<ref>), at iteration $t$:

\begin{align}
{\left(\vm_t\right)}_{[l]} &= (1 - \beta_1) \sum_{i=1}^t \beta_1^{i-1} \nabla_{\vtheta_{[l]}}E(\vtheta_{t-i})
\approx (1 - \beta_1) \sum_{i=1}^t \beta_1^{t-i} \nabla_{\vtheta_{[l]}} E \\
& = (1 - \beta_1^{t}) \nabla_{\vtheta_{[l]}} E.
\label{eq:low_curvature_m}
\end{align}

With the same arguments we have

\begin{align}
{\left(\vv_t\right)}_{[l]} & \approx (1 - \beta_2^{t}) (\nabla_{\vtheta_{[l]}} E)^2.
\label{eq:low_curvature_v}
\end{align}

We thus have that the Adam update for parameter $\vtheta_{[l]}$ is

\begin{align}
\Delta \vtheta_{[l]} = h \frac{\frac{1}{1 - \beta_1^t} {\left(\vm_t\right)}_{[l]}}{\sqrt{\frac{1}{1 - \beta_2^t} {\left(\vv_t\right)}_{[l]}} + \epsilon} \approx h \frac{\nabla_{\vtheta_{[l]}} E}{\sqrt{(\nabla_{\vtheta_{[l]}} E)^2} + \epsilon}.
\label{eq:adam_low_curve}
\end{align}

This result shows the importance of $\epsilon$ in Adam in the low-curvature regime: if $\epsilon$ is small then the update is given by the learning rate $h$; this makes the update independent of the gradient magnitude. We plot this in Figure <ref>, and show how increasing $\epsilon$ can reinstate the dependence on gradient magnitudes. Importantly, even if the model is in the neighbourhood of a local equilibrium and the gradient is close to $\mathbf{0}$, the size of the Adam update with default $\epsilon = 10^{-8}$ is given by the learning rate.  Thus, if there are many parameters in the low-curvature regime around an area of high performance, Adam can exit that area of high performance
by taking large steps when gradients are small; we have seen examples of this behaviour in a simple setting in Figure <ref>. Since SGD and Runge–Kutta4 only use local information about the gradient, they would not exit the high performance area if gradients are small there.

[Before applying fixed $h$.]

[The effect of the learning rate and $\epsilon$  on the magnitude of the update in the low-curvature regime in Adam.]The effect of the learning rate fig:adam_lr_effect and $\epsilon$ fig:adam_eps_effect on the magnitude of the update in the low-curvature regime in Adam: while the learning rate scales the gradient by a constant, the effect of $\epsilon$ strongly depends on the magnitude of the gradient, particularly for large $\epsilon$.

At peak: $\epsilon=10^{-8}$.]

[$\epsilon$ annealed from $10^{-8}$ to $10^{-4}$.
At peak: $\epsilon\approx 10^{-5}$.]

[$\epsilon$ annealed from $10^{-8}$ to $10^{-2}$.
At peak: $\epsilon\approx 10^{-3}$.]

[The effect of $\epsilon$ on Adam performance in GAN training.]The effect of $\epsilon$ on Adam performance. Increasing $\epsilon$ in training ensures that Adam does not exit areas of good performance, even with many parameters in the low-curvature regime, particularly for the discriminator. We note that using a large $\epsilon$ from early in training leads to extremely low performance (likely due to small gradients training does not pick up) and we do not show it here.

In order to understand whether this effect occurs when training GANs in practice, we need to measure whether there are many parameters in a low-curvature regime, as well as investigate the effect of $\epsilon$ on GAN training.
To answer the first question, we measure

\begin{align}
\left|\nabla_{\vtheta_{[l]}} E(\vtheta_t) - \frac{1}{1-\beta_1^t} {\left(\vm_t\right)}_{[l]} \right| \hspace{1em} \text{and}  \hspace{1em} \left|\left(\nabla_{\vtheta_{[l]}} E(\vtheta_t)\right)^2 - \frac{1}{1-\beta_2^t} {\left(\vv_t\right)}_{[l]}\right|
\end{align}

for all discriminator and generator parameters. These quantities are readily available when using Adam, we know they are $0$ for parameters in areas of low curvature (Eq <ref> and Eq <ref>), and we know how they affect the Adam update (Eq <ref>). We define a parameter as being in an area of low curvature at iteration $t$ if ${\left|\nabla_{\vtheta_{[l]}} E(\vtheta_t) - \frac{1}{1-\beta_1^t} {\left(\vm_t\right)}_{[l]} \right|< 10^{-5}}$ and ${\left|\left(\nabla_{\vtheta_{[l]}} E(\vtheta_t)\right)^2 - \frac{1}{1-\beta_2^t} {\left(\vv_t\right)}_{[l]}\right|< 10^{-5}}$. Results in Figure <ref> show that when training GANs with Adam on CIFAR-10 many parameters are in the low-curvature regime when the high performance area is reached, particularly for the discriminator. When using $\epsilon=10^{-8}$, Figure <ref> shows that after the area of high performance is reached, the model exits it and performance degrades; this is consistent with our hypothesis that, due to large updates in areas of low curvature, Adam using a small $\epsilon$ can exit areas of high performance.
By annealing $\epsilon$ throughout training we can ensure that a larger $\epsilon$ is used areas of high performance, and thus the Adam update is more sensitive to the gradient magnitude, especially for parameters with small gradients, as we show in Figure <ref>. We show results in GAN training by annealing the Adam $\epsilon$ in Figures <ref> and <ref>:
the rate at which the high performance area is left decreases, and for $\epsilon$ annealed to as high as $10^{-2}$, the high performance area is no longer exited.

These results suggest that indeed, even though Spectral Normalisation does not have a purely optimisation effect, its annealing of $\epsilon$ when using the Adam optimiser has a beneficial effect, by avoiding large steps in areas of high performance. Furthermore, these results are consistent with what we observed in the DRL case, where Spectral Normalisation ensures that performance increases for longer in training (Figure <ref>).
While here we focused on the effect of $\epsilon$ in the low-curvature regime, we want to emphasise that this is not the only effect of $\epsilon$, but simply one easy to analyse. As $\epsilon$ dampens the size of parameter updates regardless of curvature, increasing $\epsilon$ has an effect on all parameters. From that perspective, increasing $\epsilon$ in training is akin to decreasing to learning rate. We do note significant differences, however: as we show in Figure <ref>, a small $\epsilon$ in the low-curvature regime always leads to a lack of sensitivity to the gradient magnitude, regardless of learning rate, while changing $\epsilon$ can lead to increased sensitivity to gradient magnitudes. We believe more studies in the role of $\epsilon$ in Adam are needed, specifically in the context of DRL, where it has empirically been shown (here and elsewhere) to play an important role.

§ RELATED WORK

For an overview of the use of smoothness regularisation and normalisation in deep learning, together with benefits and downsides, see Chapter <ref>. The relaxation of the 1-Lipschitz constraint in the application of Spectral Normalisation has been previously done by  Gouk et al., 2020, who relax the Lipschitz constant but in contrast to our approach in DRL, still regularise the entire network.

Other normalisation methods, such as Weight Normalisation and Batch Normalisation have been studied from an optimisation perspective [Salimans and Kingma, 2016, Bjorck et al., 2018]. Unlike Spectral Normalisation however, these normalisation techniques are not hard normalisations, as their parametrisation allows recovering the un-normalised approaches. Weight Normalisation [Salimans and Kingma, 2016] decouples the learning of the Frobenius norm of the matrix from its direction; in DRL, the authors show that applying Weight Normalisation improves the performance of DQN on a subset of Atari games. When introducing Spectral Normalisation, Miyato et al., 2018 compare Spectral Normalisation and Weight Normalisation empirically and in the GAN case obtain significant gains using Spectral Normalisation compared to Weight Normalisation (their Table 2).
The connection between optimisation hyperparameters in Adam and normalisation—as we have done with $\textsc{mulEps}$—has been previously made for Batch Normalisation and Weight Normalisation [Van Laarhoven, 2017, Hoffer et al., 2018, Arora et al., 2019]; in contrast to our approach, these works require $L_2$ regularisation and obtain the $\epsilon$ scaling effect jointly with a learning rate scaling effect, while we obtained no change on the learning rate (Eq (<ref>)). The connection between $\epsilon$ and low-curvature is connected to existing works which track curvature during training [Martens and Grosse, 2015].

While optimisation specific issues in DRL have long been overlooked, recent works have studied the negative interplay between temporal difference learning methods such as $Q$-learning and adaptive optimisation methods including RMSprop and Adam [Bengio et al., 2020], while
others propose optimisers for DRL, but they are either restricted to linear estimators [Givchi and Palhang, 2014, Sun et al., 2020], or they show no empirical advantages [Romoff et al., 2020].

Inspired by the insights obtained when investigating the effects of Spectral Normalisation in DRL, we also analysed its effects on GANs. A study of the effects of Spectral Normalisation was similarly performed recently, with Lin et al., 2021 exploring the effects of Spectral Normalisation theoretically and uncovering its connections with exploding and vanishing gradients. Their work is related to our approach, which similarly uncovered the effects of Spectral Normalisation on training dynamics, as well as explored the effect of optimisation methods based on Spectral Normalisation, such as divOut, and the interaction with loss function choices and optimisers such as Adam.

§ CONCLUSION

We investigated the use of Spectral Normalisation in DRL and showed that normalising one layer of the learned neural critic in $Q$-learning agents can substantially improve performance over methods which collate multiple RL specific improvements. We then investigated why Spectral Normalisation helps DRL. By using the compositional structure of neural networks we uncovered strong optimisation effects,
including interactions with optimiser hyperparameters. Inspired by these optimisation effects, we developed novel optimisation updates that recover, or even outperform, the effects of Spectral Normalisation in DRL. Equipped with this knowledge we re-examined the effects of Spectral Normalisation in GANs, another domain where Spectral Normalisation has been applied with success, but where the normalisation procedure is applied to the entire network. We observed that for GANs optimisation only changes do not recover Spectral Normalisation performance, and that a strong effect of Spectral Normalisation is avoiding poor-conditioned areas of loss functions. Despite not recovering its performance however, optimisation changes due to Spectral Normalisation can help training when the Adam optimiser is used, particularly for parameters which exhibit low-curvature during training.

CHAPTER: GEOMETRIC COMPLEXITY: A SMOOTHNESS COMPLEXITY MEASURE IMPLICITLY REGULARISED IN DEEP LEARNING

Machine learning methods have long faced the challenge of finding the right balance between fitting the training data and generalising beyond said training data [Fortmann-Roe, 2012].
The need to avoid overly complex models that overfit by memorising training datasets has led to the need to measure model complexity, closely followed by the desire to construct regularisation methods that control said model complexity.
The aim of complexity measures is thus to capture generalisation (often measured via test set error, where lower is better) via a U-shaped curve: when complexity is low, the model is underfitting the training data and underperforming on the test data leading to a high test error (high bias), but as complexity increases the test error decreases, followed by an increase in test error once the model is overly complex and overfitting (high variance); we have observed this behaviour in Figure <ref> of Chapter <ref>.  While this traditional U-shaped curve has been long associated with complexity measures in machine learning, deep learning has led to a few puzzling observations. For deep or over-parametrised networks, overfitting is less of an issue than we would expect under the traditional U-shape curve, and the models both fit and the data and generalise [Neyshabur et al., 2014, Zhang et al., 2021, Nakkiran et al., 2019].  Deep neural networks present an additional challenge for complexity measures, as many existing measures are either too simplistic, such as number of learnable parameters or weight norms, or intractable to compute for the neural network class of models, such as classical measures like Rademacher [Koltchinskii and Panchenko, 1999, Bartlett and Mendelson, 2002] complexity and VC dimensions [Vapnik and Chervonenkis, 1971, Vapnik, 2013].

Recent work has also uncovered connections between optimisation and generalisation in deep learning, while previously optimisation was viewed purely from a training objective minimisation perspective; these works broadly fall under the umbrella of implicit regularisation [Neyshabur, 2017, Barrett and Dherin, 2021, Smith et al., 2021, Kunin et al., 2021, Ma and Ying, 2021]. Since many existing complexity measures measure the capacity of a family of functions [Koltchinskii and Panchenko, 1999, Vapnik and Chervonenkis, 1971, Vapnik, 2013], they cannot capture implicit regularisation effects induced by optimisation inside a model class, such as the implicit regularisation induced by discretisation drift we studied in previous chapters.

Motivated by the need to reconcile complexity measures and deep learning, and emboldened by our previous study of implicit regularisation and interactions between smoothness and optimisation,
we make the following contributions:

* We introduce a new measure of model complexity for deep neural networks, which we call Geometric Complexity (GC). GC captures the complexity of a model rather than function class, can be computed exactly during training, and has connections to Lipschitz smoothness.

* We show that GC is connected with or implicitly regularised by many aspects of deep learning, including initialisation, explicit regularisation, and implicit regularisers induced by the discretisation drift of optimisation methods.

* We show that through implicit regularisation induced by discretisation drift, the implicit minimisation of GC in neural network training can be strengthened through hyperparameter choices such as batch size or learning rate.

* We show that GC captures the double descent phenomenon, and restores the classical complexity versus performance U-shaped curve.

§ INTRODUCTION

Existing complexity measures. Many existing complexity measures target the complexity of a class of functions. These types of complexity measures range from the very simple, such as number of learned parameters, to more sophisticated, such as Rademacher complexity and VC dimensions [Koltchinskii and Panchenko, 1999, Vapnik and Chervonenkis, 1971, Vapnik, 2013, Bartlett et al., 2002, Bartlett and Mendelson, 2002].
While convenient and inexpensive, using the number of learned parameters as a complexity measure does not account for architectures and expressivity; when using the number of parameters to measure the capacity of a neural network, the now famous double descent phenomenon [Belkin, 2021, Belkin et al., 2019, Nakkiran et al., 2019] occurs in deep learning: as the number of parameters exceeds a critical threshold, the test error of the model decreases again, as opposed to increasing as expected under the U-shaped complexity curve. Rademacher complexity [Koltchinskii and Panchenko, 1999, Bartlett and Mendelson, 2002] and VC dimension do account for model class [Vapnik and Chervonenkis, 1971, Vapnik, 2013], but are geared towards measuring capacity of fitting random labels. They thus do not account for the specific task and cannot leverage the inherent structure in the data present in many deep learning problems, and are also challenging to compute for specific deep learning architectures, though bounds do exist [Neyshabur et al., 2018, Anthony and Bartlett, 1999]. Additional challenges get presented by the fact that neural networks have been shown to consistently be able to learn mappings to random labels [Zhang et al., 2021], making it hard to distinguish between classes of neural networks.

Metrics for measuring the complexity of a single model rather than model family are available. They range from simple approaches, such as the norm of the learned parameters [Neyshabur, 2017], to the more complex such as classification margins [Jiang et al., 2018] or flatness [Keskar et al., 2017, Jiang et al., 2019], Kolmogorov complexity [Schmidhuber, 1997] and relatedly minimum description length [Hinton and Zemel, 1994, Blier and Ollivier, 2018], the number of linear pieces for ReLU networks [Arora et al., 2018, Serra et al., 2018], but they are not without limitations. Metrics based on parameter norms, such as weight norms, are independent of model architectures and for large models it is not inherently clear how changing the parameter norm changes the model predictions. Norm-based metrics have also been shown to correlate poorly with generalisation, especially when stochastic optimisation is used [Jiang et al., 2019]; classification margins can be challenging to compute for data with a high number of dimensions or classes; while flatness (or equivalently low sharpness) has been shown to be connected with generalisation [Hochreiter and Schmidhuber, 1997, Keskar et al., 2017, Jastrzebski et al., 2019, Barrett and Dherin, 2021, Jiang et al., 2019], limitations have been noted [Dinh et al., 2017, Kaur et al., 2022]. We previously discussed flatness—defined there as the leading eigenvalue of the Hessian—as a measure of generalisation in Chapter <ref>. Complexity measures for distributions over models, such as PAC-Bayes [Alquier, 2021], have also been adapted to neural networks [Dziugaite and Roy, 2017], but they are outside of the scope of this thesis.

Neyshabur et al., 2018 analysed many existing measures of complexity and showed that they increase alongside the number of the hidden units, and thus cannot explain behaviours observed in over-parametrised neural networks, where increasing the number of hidden units does not lead to increased overfitting (their Figure 5). Jiang et al., 2019 perform an extensive study of existing complexity measures and their correlation with generalisation as well as aim to find causal relationships and find that flatness has the strongest positive connection with generalisation.

Explicit and implicit regularisation.
Explicit regularisation in deep learning takes many forms, either through adding terms to loss functions or regularising the model architecture [Srivastava et al., 2014, Yoshida and Miyato, 2017, Goodfellow et al., 2016, Geiping et al., 2022, Balduzzi et al., 2018, Mescheder et al., 2017, Nagarajan and Kolter, 2017]. Explicit regularisation can affect model capacity in intricate ways and its effect can strongly depend on the magnitude of regularisation coefficients, with no  straightforward method of translating regularisation effects into restrictions on a model class.
Thus, despite their practical significance in obtaining increased generalisation performance, the effect of common explicit regularisers has not been unified by existing complexity measures.

Recent years have seen an expansion in the discovery of implicit regularisation effects in deep learning, from the implicit regularisation effects of learning rates [Li et al., 2019, Barrett and Dherin, 2021, Jastrzebski et al., 2019, Neyshabur, 2017, Seong et al., 2018, Smith et al., 2021, Smith et al., 2018], mini-batch optimisation noise [Smith et al., 2020, Ziyin et al., 2022, Roberts, 2018] or initialisation  [Glorot and Bengio, 2010, Gunasekar et al., 2018, He et al., 2015, Li and Liang, 2018, Nagarajan and Kolter, 2019, Zhang et al., 2020, Zou et al., 2020]. We previously explored implicit regularisation induced by the discretisation drift of optimisers in Chapters <ref> and <ref>.
Implicit regularisation effects have been largely unexplained by existing complexity measures; by construction complexity measures of function classes rather than individual models cannot capture the effects of optimisation inside a function class. Novel connections between optimisation hyperparameters such as learning rates and per-model complexity measures such as sharpness have been recently found (Cohen et al., 2021 and Chapter <ref>), but more investigation into its connection with stochasticity is needed [Kaur et al., 2022].
The role of network depth and overparametrisation as an implicit regulariser has also been studied [Neyshabur et al., 2018, Li and Liang, 2018, Du et al., 2018], and has been shown to play an important role in the generalisation properties of neural networks as well as the double descent phenomenon; in Chapter <ref> we postulated a connection between depth, overparametrisation, and smoothness, which we will make concrete here.

Smoothness: We highlighted the benefits of smoothness for neural networks extensively in Section <ref> and intuited its deep connection with generalisation and double descent. Existing works have shown that generalisation bounds can be obtained from smoothness constraints [Sokolić et al., 2017]. The connection between smoothness and many implicit and explicit regularisers has been highlighted in Chapter <ref>; here we will define a smoothness based complexity measure and make this association concrete through theoretical arguments and experimentation.

§ GEOMETRIC COMPLEXITY

We are now ready to define a novel metric of complexity for neural models, with the aim of finding a measure that can capture some of the implicit and explicit regularisation effects previously discussed.
For a neural network $g(\cdot;{\vtheta}): \mathbb{R}^I \rightarrow \mathbb{R}^O$ with parameters $\vtheta \in \mathbb{R}^D$, we write $g(\cdot;{\vtheta})= \tau(f(\cdot;{\vtheta}))$ where $\tau$ is the last layer activation function (such as the softmax for multi-label classification). Given a dataset $\mathcal{D}$ with elements $\vx$ i.i.d. realisations of random variable $\mathcal{X}$, we define Geometric Complexity (GC) as

\begin{align}\label{eqn:geometric_complexity}
GC(f;\vtheta, \mathcal{D}) = \frac{1}{|\mathcal{D}|}\sum_{\vx\in \mathcal{D}} \left\|\jacparam{\vx}{f(\vx; \vtheta)}\right\|_2^2,
\end{align}

where $||\vv||_2$ denotes the Frobenius norm.

GC measures the complexity of a single model $f(\cdot; \vtheta)$, not a model class, can be computed efficiently, and depends on the task at hand through the training dataset $\mathcal{D}$. While GC is defined based on the training data, it is an estimate of an expectation:
GC is the unbiased estimate of the underlying expectation under $p(\vx)$ the density of $\mathcal{X}$:

\begin{align}
\mathbb{E}_{p(\vx)} \left[\left\| \jacparam{\vx}{f(\vx; \vtheta)}\right\|_2^2 \right] = \int \left\| \jacparam{\vx}{f(\vx; \vtheta)}\right\|_2^2 p(\vx) d \vx.
\end{align}

GC can be connected to Lipschitz smoothness—which we discussed at length in Chapter <ref>—using the following bound:
If $K$ is the Lipschitz constant of $f(\cdot;\vtheta):\mathbb{R}^I \rightarrow \mathbb{R}^O$ w.r.t. the Frobenius norm then we have that:

\begin{align}
GC(f;\vtheta, \mathcal{D}) &= \frac{1}{|\mathcal{D}|}\sum_{\vx\in \mathcal{D}} \left\|\jacparam{\vx}{f(\vx; \vtheta)}\right\|_2^2 \\
&\le \min(I, O) \frac{1}{|\mathcal{D}|}\sum_{\vx\in \mathcal{D}} \left\|\jacparam{\vx}{f(\vx; \vtheta)}\right\|_{op}^2
\le \min(I, O) K^2,
\end{align}

where $\norm{A}_2$ and $\norm{A}_{op}$ denote the Frobenius and operator norms of $A$, respectively.

This result follows from $\norm{A}_2^2 \le \text{rank}(A) \norm{A}_{op}^2 \le \min(I, O) \norm{A}_{op}^2, \hspace{1em} \forall A \in \mathbb{R}^I \times \mathbb{R}^O$ and $\left\|\jacparam{\vx}{f(\vx; \vtheta)}\right\|_{op}^2  \le K^2$. For many problems of concern we have that $\min(I, O) = O$ and thus Remark <ref> exposes that the tightness of the bound between GC and Lipschitz smoothness depends on the number of outputs of the network.

While the Lipschitz smoothness of a function provides an upper bound on GC, there are a few fundamental differences between the two quantities. Firstly, GC is data dependent: a model can have low  GC while having high Lipschitz constant due to the model not being smooth in parts of the space where there is no training data. Measures on the entire space, such as Lipschitz constants, are unlikely to explain implicit and explicit regularisation effects when many of the regularisers are applied around data instances.
Secondly, GC can be computed exactly given a model and dataset, while for when estimating the Lipschitz constant of neural networks loose upper and lower bounds that rely on function composition are often used [Virmaux and Scaman, 2018, Combettes and Pesquet, 2019].
Fazlyab et al., 2019 provide an algorithm with tighter bounds by leveraging that activation
functions are derivatives of convex functions and cast finding the Lipschitz constant as the result of a convex
optimisation problem;
however, their most accurate approach scales quadratically with the number of neurons and only applies to feed forward networks.
Sokolić et al., 2017 provide an upper bound for the Lipschitz constant of a neural network with linear,
softmax and pooling layers restricted to input space $\mathcal{X}$ via $\norm{f(\vx) - f(\vy)}_{2} \le \sup_{\vz \in \text{convex\_hull}(\mathcal{X})} \norm{\frac{d f}{d\vz}}_2 \norm{\vx-\vy}_2,  \hspace{1em} \forall \vx, \vy \in \mathcal{X}$,
but empirically resort to layer-wise bounds.
In contrast, GC can be computed exactly regardless of network architecture and can be easily implemented using modern machine learning software frameworks.

§.§ GC for deep linear models

Consider a deep linear network $lin(\vx, \vtheta) = \vW_n \dots \vW_1 \vx + \vb$, with $\vtheta = \{\vb\}  \union \{\vW_i, i \in \{1, \dots, n\}\}$ We then have that

\begin{align}
GC(lin;\vtheta, \mathcal{D}) = \| \vW_n \dots \vW_1\|_2^2.
\end{align}

This shows that the GC of an affine transformation does not depend on the data and recovers the standard Frobenius norm, which is often used as a regulariser, particularly in ridge regression.

§.§ GC for rectifier feed-forward networks

Networks with rectifier activations, such as ReLu [Agarap, 2018] and Leaky Relu [Maas et al., 2013], are piecewise affine models, that is for each $\vx_i$ we have that $f(\vx_i;\vtheta) = \vA_i \vx_i + \vb_i$, where $\vA_i$ and $\vb_i$ depend on where in the partition of the input space input $\vx_i$ falls in. We can then write

\begin{align}
GC(f;\vtheta, \mathcal{D}) &= \frac{1}{|\mathcal{D}|}\sum_{\vx\in \mathcal{D}} \left\|\jacparam{\vx}{f(\vx; \vtheta)}\right\|_2^2 = \sum_{p=1}^P \frac{n_p}{|\mathcal{D}|} \|\vA_p\|_2^2,
\label{eq:relu_gc}
\end{align}

where $n_p$ is the number of times an input is in the partitioning corresponding to the linear piece $\vA_p \vx + \vb_p$ in the piecewise model. Eq (<ref>) shows that for models with rectifier activations, GC can be approximated by using batches, instead of the entire dataset, as long as the batch size is large enough to include representation from many piecewise branches of the network.

To further understand the form of GC for rectifier models, let's consider a simple two-layer network, where we have $f(\vx; \vtheta) = \vW_2 a(\vW_1 \vx + \vb_1) + \vb_2$ with $\vtheta = \{\vW_1, \vW_2, \vb_1, \vb_2\}$. Denote $\vh = a(\vz) = a(\vW_1 \vx + \vb_1)$, where $a$ is the rectifier activation function. We then have

\begin{align}
\jacparam{\vx}{f} = \vW_2 \diag(a'(\vz)) \vW_1 ,
\label{eq:gc_two_layers}
\end{align}

where $\diag(\vv)$ is the diagonal matrix with diagonal entries given by $\vv$. Since $\left(\diag(a'(\vz)) \vW_1\right)_{i,j} = a'(\vz_i) \vW_{i,j}$ and since in the case of rectifiers $a'(\vz_i)$ is a piecewise constant function (such as $a'(x) = 0$, if $x < 0$ or $1$ otherwise for ReLu activations), we see the connection between  $L_2$ regularisation and weight decay in rectifier networks, and how decreasing the norm of the weight matrices will decrease GC.
We observe that unlike weight norms, GC is sensitive to the impact the weight has on the output of the network. This can be most clearly seen for the ReLU activation, where the activation derivative $a'$ can be $0$ and thus for units that do not contribute to the output of a data instance, no norm penalty is imposed.
Consider the case of unit $\vh_i = 0$, where $\vz_i  = {\left(\vW_1\right)}_{i}^T \vx + {(\vb_1)}_i < 0$. Then the entries of row ${\left(\vW_1\right)}_{i}$, which don't contribute to the model output, will not be penalised by $\norm{\jacparam{\vx}{f}}$ in GC, since they are modulated by $a'(\vz_i) = 0$ in Eq <ref>. The same can be said about the column $i$ of $\vW_2$, which does not contribute to the model output as $\vo = \vW_2 \vz + \vb_2$. Thus, GC is robust to weights that do not contribute to model output, such as when a weight matrix has an entry with negative but large absolute value, which leads to a negative pre-activation and a zero hidden unit for all inputs in the dataset. In contrast, the weight norm will be heavily skewed by such a weight due to its large absolute value; this insight might help explain why parameter norm measures are not indicative of generalisation performance [Jiang et al., 2019].

§.§ GC for convolutional and residual layers

Since convolutional layers are linear operators, the form of GC when convolutional layers are used is that of Eq (<ref>), where the linear operator $\vA_p$ will be determined by the linear operators of the convolutional layers. A significant difference between convolutional and linear layers will be that each parameter of a convolutional filter will appear repeatedly in the linear operator present in GC, which further highlights the difference between GC and weight norms discussed above.

Residual layers [He et al., 2016] have the form of $a(\vM \vx + \vx)$, where $\vM$ is a composition of convolutional layers followed by the activation function $a$, usually a rectifier [Nair and Hinton, 2010, Maas et al., 2013]. Alternatively, they can use an additional projection $\vR$ leading to  $a(\vM \vx + \vR \vx)$.  Thus, networks rectifier activations with residual layers will also be piecewise linear models and Eq (<ref>) holds.

§ GC INCREASES AS TRAINING PROGRESSES

We now focus on the value of GC at network initialisation, and we show that for deep networks with rectifier activations and commonly used initialisers, the GC of the model is close to $0$ at initialisation. To see why, we again leverage the piecewise nature of networks with rectifier activations, together with the fact that network biases are initialised to be $0$: at initialisation rectifier MLPs can be written as $f(\vx; \vtheta) = \vW_n \vP_{n-1} \vW_{n-1} \dots  \vP_1 \vW_1 \vx$ where $\vP_i = \diag(a'(\vz_i)) = \diag(a'(\vW_i \vz_{i-1}))$.
For ReLu networks, since the diagonal entries of $\vP_i$ will be 0 if $\vz_{i-1}$ is negative, as the depth of the network increases, the chance that the output is not 0 diminishes.
Consider the 1-dimensional case where $f(x; \vtheta) = w_n a(w_{n-1} \dots a(w_1 x))$ and $a$ is the ReLu activation function. If we assume standard Gaussian initialisations of the form $w_i \sim \mathcal{N}(0, \sigma_i^2)$ we have that $P(w_1 x > 0) = \tfrac{1}{2}$, thus $P(a(w_1 x) \ne 0) = \tfrac{1}{2}$. With similar arguments, $P(a(w_2 z_1) \ne 0| z_1 \ne 0) = \tfrac{1}{2}$ leading to $P(a(w_2 z_1) \ne 0) = \frac{1}{2}^2$. By induction we can then show that for $n$ layers
$P(f(x; \vtheta) \ne 0) = \frac{1}{2^n}$; this shows that as we add one layer, the probability of the output of the network not being $0$ is exponentially decreasing.
When we consider higher dimensional weight matrices, the chance of hitting exactly $0$ decreases, but the obtained function values will be small due to the decreased chance of consistently obtaining positive numbers under the random initialisation. Thus, we expect GC, as the average norm  of $\jacparam{\vx}{f(\vx; \vtheta)} = \vW_n \vP_{n-1} \vW_{n-1} \dots  \vP_1 \vW_1$, to be low at initialisation and decrease as the number of layers in the network increases. In Figure <ref> we confirm this by looking at the effect of depth on the output of an MLP with input dimensions given by those of input dimension $I=150528 = 224 \times 224 \times 3$ and $O=1000$ (as from the Imagenet dataset), and show how both the mean and the maximum output obtained from 100 samples are decreasing as the number of layers increases.

[Mean model output.]

[Max model output.]