Why neural networks find simple solutions:  The many regularizers of geometric complexity
Authors: Benoit Dherin
Michael Munn
Mihaela Rosca
David GT Barrett
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep Learning
Deep Learning Theory
Theory
Neural Networks
Regularization
Implicit Regularization
Smoothness
Complexity
Double-Descent

Abstract: In many contexts, simpler models are preferable to more complex models and the control of this model complexity is the goal for many methods in machine learning such as regularization, hyperparameter tuning and architecture design. In deep learning, it has been difficult to understand the underlying mechanisms of complexity control, since many traditional measures are not naturally suitable for deep neural networks. Here we develop the notion of geometric complexity, which is a measure of the variability of the model function, computed using a discrete Dirichlet energy. Using a combination of theoretical arguments and empirical results, we show that many common training heuristics such as parameter norm regularization, spectral norm regularization, flatness regularization, implicit gradient regularization, noise regularization and the choice of parameter initialization all act to control geometric complexity, providing a unifying framework in which to characterize the behavior of deep learning models.

Why neural networks find simple solutions: the many regularizers of geometric complexity
Benoit Dherin'
Michael Munn" Google munn@google.cm com
Mihaela Rosca DeepMind, London University College London
Google dherin@google.com com
mihaelacrrdeeppinnd com
David G.T. Barrett
DeepMind, London barrettdavidddeeepmiin com
Abstract
In many contexts, simpler models preferable to more complex models and the control of this model complexity is the goal for many methods in machine learning such regularization, hyperparameter tuning and architecture design. In deep learning. has been difficult to understand the underlying mechanisms of complexity control, since many traditional measures not naturally suitable for deep neural networks. Here we develop the notion of geometric complexity, which is measure of the variability of the model function, computed using a discrete Dirichlet energy. Using a combination of theoretical arguments and empirical results, show that many common training heuristics such parameter regularization, spectral norm regularization, flatness regularization, implicit gradi- ent regularization, noise regularization and the choice of parameter initialization all act to control geometric complexity, providing unifying framework in which characterize the behavior of deep learning models.
Introduction
Regularization is an essential ingredient in the deep learning recipe and understanding its impact on
the properties of the learned solution is very active area of research 36
46
79 [00] Regularization
can assume a multitude of forms, either added explicitly as a penalty term in loss function 36 or
implicitly through our choice of hyperparameters
39 model architecture 66
63 64
or initialization 34 40 41 (2]
74, 99 100). These forms are generally not designed to be analytically
tractable, but in practice, regularization is often invoked in the control of model complexity, putting
pressure on a model to discover simple solutions more so than complex solutions.
To understand regularization in deep learning, need to precisely define model 'complexity' for deep neural networks. Complexity theory provides many techniques for measuring the complexity of model, such simple parameter count, parameter norm measurement
25
77 76 but
many of these measures can be problematic for neural networks 48
77 The recently observed
phenomena of 'double-descent' [22 7 illustrates this clearly: neural networks with high model complexity, as measured by parameter count, can fit training data closely (sometimes interpolating the data exactly), while simultaneously having low error 75 97.. Classically,
expect that interpolation of training data is evidence of overfitting, but yet, neural networks seem to be capable of interpolation while also having low test error. It is often suggested that some form of implicit
equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

regularization or explicit regularization is responsible for this, but how should we account for this in theory, and what complexity measure most uppropriate?
In this work, we develop a measure of model complexity, called Geometric Complexity (GC), that has properties that suitable for the analysis of deep neural networks. We use theoretical and empirical techniques to demonstrate that many different forms of regularization and other training heuristics can act control geometric complexity through different mechanisms. We argue that the geometric complexity provides a convenient proxy for neural network performance.
Our primary contributions are:
We develop a computationally tractable notion of complexity (Section 2
which we call
Geometric Complexity (GC), that has many close relationships with many areas in deep learning and mathematics including harmonic function theory, Lipschitz smoothness (Section and regularization theory (Section
We provide evidence that common training heuristics keep the geometric complexity low, including: (i) common initialization schemes (Section ( (ii) the use of overparametrized models with a large number of layers (Fig. (iii) large learning rates, small batch sizes, and implicit gradient regularization (Section 5 and Fig. (iv) explicit parameter norm regular-
ization, spectral norm regularization, flatness regularization, and label noise regularization
(Section 1 and Fig. +
We show that the geometric complexity captures the double-descent behaviour observed in the test loss as model parameter count increases (Section 3 and Fig.
The aim of this paper is to introduce geometric complexity, explore its properties and highlight its connections with existing implicit and explicit regularizers. To disentangle the effects studied here from optimization choices, we use stochastic gradient descent without momentum to train all models. We also study the impact of a given training heuristic on geometric complexity in isolation of other techniques to avoid masking effects. For this reason we do not use data augmentation or learning rate schedules in the main part of the paper. In the Supplementary Material (SM) we redo most experiments using SGD with momentum (Section C7 and Adam (Section C.8 with very similar conclusion. We also observe the same behavior of the geometric complexity in a setting using learning rate schedule, data augmentation, and explicit regularization in conjunction to improve model performance (Section C.6p. The exact details of all experiments in the main paper are listed in SM Section B All additional experiment results and details can be found in SM Section
Geometric complexity and Dirichlet energy
Although many different forms of complexity measures have been proposed and investigated (e.g.. [2 48 76)), it is not altogether clear what properties they should have, especially for deep learning. For instance, number of them like the Rademacher complexity [2]] the VC dimension [93 or the simple model parameter count focus on measuring the entire hypothesis space, rather than a specific function, which can be problematic in deep learning [4] 977. Other measures like the number of linear pieces for ReLU networks B [6) or various versions of the weight matrix norms (76) measure the complexity of the model function independently from the task at hand, which is not desirable [8]. An alternative approach is to learn a complexity measure directly from data (60] or to take the
whole training procedure over dataset into account 775) Recently, other measures focusing on the
model function complexity over a dataset have been proposed in RD and (67 to help explain the
surprising generalization power of deep neural networks. Following that last approach and motivated
by frameworks well established in the field of geometric analysis [50]. we propose a definition of
complexity related to the theory of harmonic functions and minimal surfaces. Our definition has the advantage of being computationally tractable and implicitly regularized by many training heuristics in the case of neural networks. It focuses measuring the complexity of individual functions rather than that of the whole function space, which makes it different from the Radamacher or VC complexity.
Definition 2.1. Let go RRd + & be a neural network parameterized by We can write go(x:) = (z)) where denotes the last layer activation, and fe its logit network. The GC of the network
2

---

over a dataset D is defined to be the discrete Dirichlet energy of its logit network:
(So, DiG
1 - IV [D]
Σ ZED
(I)
where [>fo(xx]] is the Frobenius norm of the network Jacobian.
Note that this definition is well-defined for any differentiable model, not only neural network, and incorporates both the model function and the dataset over which the task is determined.
Next, we discuss how GC relates to familiar concepts in deep learning.
Geometric complexity and linear models: Consider linear transformation f(x) Ar + b from I to R and dataset D {ri) where æ; E R4 At each point E D, we have that [[=](<)] = || [/. hence the GC for línear transformation is (Je, D)c || Note, this implies that GC for linear transformations (and more generally, affine maps), is independent of the dataset D and zero for constant functions. Furthermore, note that the GC in this setting coincides precisely with the L2 norm of the model weight matrix. Thus, enforcing equivalent to regularizing the GC for linear models (see Section for more on that point).
L2 norm penalty is
Geometric complexity and ReLU networks: For a ReLU network R - R* as defined in Definition 2.T] the GC over dataset D has very intuitive form. Since a ReLU network parameterizes piece-wise linear functions B., the domain can be broken into a partition of subsets X; C R where So an affine map A, + bü- Now denote by D, the points in the dataset that fall in the linear piece defined on X, For every point x in X,, we have that [/ = ||A: 13. Since the D''s partition the dataset D, we obtaín
Di.. - 1
n D
IA
where n, is the number of points in the dataset D falling in X,. We see from Eqn. 2 that for ReLU networks the GC over the whole dataset coincides exactly with the GC batch B D, provided that the proportion of points in the batch falling into each of the the linear pieces are preserved. This makes the evaluation of the GC large enough batches very good proxy to the overall GC over the dataset, and computationally tractable during training.
Geometric complexity and Lipschitz smoothness: One way to measure the smoothness of function f Rd + R² on subset X C Rd is by its Lipschitz constant; i.e., the smallest ft. 2 0 such that []]( f(x2))l < fT.1|<i 22l1, for all æ1, #2 E X. Intuitively, the constant fr. measures the maximal amount of variation allowed by f when the inputs change by a given amount. Using the Lipschitz constant, one define complexity measure of function f as the Lipschitz constant fL of the function over the input domain Rd. Since V (x) 1/ S min(k, d') V a (=) < min(k, f2 where || olop is the operator norm, we obtain a general bound on the GC by the Lipschitz complexity:
(,, = D
Σ (v)(()) S min(k, d)f?
(3)
RED
While the Lipschitz smoothness of a function provides upper bound on GC, there are few fundamental differences between the two quantities. Firstly, GC 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. Secondly, the GC can be computed exactly given a model and dataset, while for neural networks only loose upper bounds are available to estimate the Lipschitz constant.
Geometric complexity, are length and harmonic maps: Let us start with a motivating example: Consider a dataset consisting of 10 points lying on parabola in the plane and large ReLU deep neural network trained via gradient descent learn a function f -> IR that fits this dataset (Fig. D. Throughout training the model function seems to attain minimal are length for a given level of training error. Recalling the formula for are length of f, which is the integral of over [-1, of +I+ (z))² and using the Taylor approximation V1+ x² R 1 + = it follows that minimizing the are length is equivalent to minimizing the classic Dirichlet energy:
E(f) - / [
(4)
3

---

epechs. GC=0.01
10 epochs, GC=0 63
1000 spechs, GC=1.17
10000 epechs, GC=1.33
1.0
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.8
0.4
0.4
0.4
0.4
6.2
0.2
0.2
0.2
0.0
0.0
0.0
-0.2
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Figure I: For a large MLP fitting 10 points, the complexity of the function being learned gradually grows in training. while avoiding unnecessary complexity by keeping the function are length minimal.
where Ω [-1,1] 1]. The Dirichlet energy can be thought intuitively of as measure of the variability of the function f on Q2 Its minimizers, subject to a boundary condition flan = h. are called harmonic maps, which are maps causing the "least intrinsic stretching" of the domain f2 [91]. The geometric complexity in Definition 2. an unbiased estimator of a very related quantity
Ex (1 Va. [ [[ Px (x)dx,
(5)
where the domain Ω is replaced by the probability distribution of the features px and the boundary condition is replaced by the dataset D. We could call the quantity defined in Eqn. (5) the theoretical
geometric complexity as opposed to the empirical geometric complexity in Definition 2. The
theoretical geometric complexity is very close the Jacobian of the full network is considered rather than just the logit network as we do here. In their work, the expectation is also evaluated on the test distribution. They observe a correlation between this complexity measure and generalization empirically in a set of extensive experiments. In our work, we use the logit network (rather than the full network) and we evaluate the empirical geometric complexity on the train set (rather than on the test set) in order to derive theoretically that the implicit gradient regularization mechanism from 7 creates a regularizing pressure on GC (see Section 5
complexity measure investigated in 77]. where
In the remaining sections we provide evidence that common training heuristics do indeed keep the GC low, encouraging neural networks find intrinsically simple solutions.
3 Impact of initialization on geometric complexity
Parameter initialization choice is an important factor in deep learning. Although we are free to specify exact parameter initialization values, in practice, small number of default initialization schemes have emerged to work well across a wide range of tasks 34 41]. Here, we explore the relationship between some of these initialization schemes and GC.
To begin, consider the one dimensional regression example that we introduced in Figure [ In this experiment, we employed a standard initialization scheme to initialise the parameters: them from a truncated normal distribution with variance inversely proportional to the number of input units and the bias terms were set to zero. We observe that the initialised function on the interval [-1, 11,1]is is very close to the zero function (Fig. D. and the zero function has zero GC. This observation suggests that initialization schemes that have low initial GC are useful for deep learning.
sample
To explore this further, we consider deep ReLU networks with larger input and output spaces initialized using the same scheme above, and measure the GC of the resulting model. Specifically, consider the initialized ReLU network given by So, : Rdd - R with 150528 and k = 1000, with parameter initialization 0g and varying network depth. We measure the ReLU network output size by recording the mean and maximum output values, evaluated using input values along the line P1 + (P2- Pr)x with
[0, 1] between two diagonal points P1 and P3 of the hyper-cube []., We observe that these ReLU networks initialize to functions close to the zero function, and become progressively closer to zero valued function as the number layer increases (Fig. 2 For ReLU networks, this is not entirely surprising. With biases initialised to zero, we can express ReLU network in a small neighborhood of given point a E Rd as a product of matrices (x) = W, P.WW ... P.WE,, where the W. 's are the weight matrices and the P. 's diagonal matrices

---

Outout Mean at Initaalizatonn
Outout Max at Intitialization
Network Complexity at Intitielization
0.020
number layers
activation--itaaliiaaoo
0.015
1.75
aalu-tandard
0.010
1.50
Geometric Complexity
20
relu-glorot
sigmoid standard
0.005
1.25
8
sigmold glorot
meanty/
maxIiv
0.000
1.00
32
10
-0.010
0.50
0.015
0.25
-0.020
0.00
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4 0.6
X 0.8
1.0
16 32 64
Number of Layers
Figure 2: MLP's given by y fa, (x) initialize closer the zero function and closer zero GC, as the number of layers increases. Left and Middle: The ReLU MLP's initialized with the standard scheme are evaluated using input values along the line P1 + (P2 Pı)æ with E [0, 1] between two diagonal points Pi and P2 of the hyper-cube [-1, 1j Right: GC is computed dataset D of 100 normalized data points. All MIP's have 500 neurons per layer.
with 0 and 1 their diagonals. This representation makes it clear that at initialization the ReLU network passes through the origin; i.e., fo, (0) = O. Furthermore, with weight matrices initialised around zero, using scaling that can reduce the spread of the distribution the matrices grow, expect that deeper ReLU networks generated by multiplying a large number of small-valued weights, can produce output values close to zero (for input values taken from a hyper-cube [-1, 1J We extend these results further to include additional initialization schemes and experimentally confirm that the GC can be brought close to zero with sufficient number of layers. In fact, this is true not only for ReLU networks with the standard initialization scheme, but for a number of other common activation functions and initialization setups (3 4T and even on domains much larger than the normalized hyper-cube (Fig. g and SM Section C.I. Theoretically. it has been shown very recently (their Theorem 5), that under certain technical conditions, neural network at random initialization will converge to a constant function (which has GC equal to zero) as the number of layers increases.
Impact of explicit regularization on geometric complexity
Next, explore the relationship between GC and various forms of explicit regularization using combination of theoretical and empirical results.
CIFAR1O ResNet10
MNIST
0.20
0.200
Geometric Camploxity
Gecomeetic Camplexity
0.18
Geametric Complexity
0.20
0.16
0,350
Regularization Type
0.15
0.125
fetness
spectral
0.12
0.30
0.075
0.05
0.08
0.050
0.06
0.00
0.00
0.07
0.04
0.06
0.08
0.10
0.00
0.05 0.10
0.15 0.20 0.25 0.00
0.10
0.20
0.25
Regularization Rate
Proportion of Label Noise
Proportion of Label Noise
As the L., flatness, and spectral regularization increase, GC decreases. (See SM Section C.5 for additional experiments on explicit regularization with ranges targeted to each regularization type.) Middle and Right: As label noise regularization increases, GC decreases.
Figure 3: Explicit regularization and GC. Left:
L2 regularization: In 1.2 regularization, the Euclidean norm of the parameter vector is explicitly added loss function, so as to penalize solutions that have excessively large parameter values. This is one of the simplest, and most widely used forms of regularization. For linear models
5

---

(f(()) = Ar + b), we saw in Section 2 that the GC coincides with the Frobenius norm of the matrix A. This means that standard L2 norm penalties on the weight matrix coincide in this case with a direct explicit regularization of the GC of the linear model. For non-linear deep neural networks, we cannot directly identify the 1.2 norm penalty with the model GC. However, in the case of ReLU networks, for each input point z, the network output y can be written in a neighborhood of x as y = P.W.... P1 W æ + C, where c is a constant, the P''s are diagonal matrices with O and I on the diagonal, and the W,'s 's are the network weight matrices. This means that the derivative at z of the network coincides with the matrix P.W.... .. Pi W, Therefore, the GC is just the Frobenius norm of the product of matrices. Now, an L2 penalty [| + ... + ||a ? encourages small numbers in the values of the weight matrices, which in turn is likely to encourage small numbers for the values in the product P.W. ... Pi W1. resulting in lower GC.
We can demonstrate this relationship empirically, by training a selection of neural networks with 1.2 regularization, each with different regularization strength. We measure the GC for each network at the time of maximum test accuracy. We observe empirically that strengthening L.2 regularization coincides with decrease in GC values (Fig.
Lipschitz regularization via spectral norm regularization: A number of explicit regularization
schemes have been used to tame the Lipschitz smoothness of the model function and produce smoother models with reduced test error 2 2T
28
39
[53] 171 81 (6]. Smoothness regularization
has also been shown to be beneficial outside the supervised learning context, in GANs 17 71 |
and reinforcement learning 14. 355. One successful approach to regularising the Lipschitz constant of neural network with I-Lipschitz activation functions (e.g. ReLU, ELU) is to constrain the spectral norm of each layer of the network (i.e.. the maximal singular values max (W,) of the weight matrices Wi), since the product of the spectral norms of the networks weight matrices is an upper bound to the Lipschitz constant of the model: fL S m (W1) ... max (Wi). Using inequality B we see that any approach that constrains the Lipschitz constant of the model constrains GC. To confirm this theoretical prediction, we train ResNet1 8 model on CIFARIO 10 (58) and regularize using spectral regularization (o). an approach which adds the regularizer 2/ (x(mmxx(W)) to the model loss function. We observe that GC decreases as the strength of spectral regularization increases (Fig.
The addition of noise during training is known to be an effective form of regularization. For instance, it has been demonstrated [13] that the addition of noise to training labels during the optimization of least-square loss using SGD exerts a regularising pressure EegyED |l f D|. Here, we demonstrate empirically that the GC of a ResNet18 8 trained
Noise regularization:
on CIFARIO reduces as the proportion of label noise increases (Fig. B middle). The same is true of MI.P trained on MNIST (22) (Fig. 3 right). In Section 5 we provide a theoretical argument which justifies these experiments, showing that a regularizing pressure on [ox))( transfers to a regularizing pressure V (a:) 12_ Thus, label noise in SGD in turn translates into regularizing pressure on the GC in the case of neural networks.
flatness regularization, an explicit gradient penalty term, / || is added to the loss (where J.n is the loss evaluated across batch B). It has been observed in practice that flatness regularization can be effective in many deep learning settings, from supervised learning Flatness regularization penalizes Icarning trajectories that follow steep slopes across the loss surface, thereby encouraging learning to follow shallower slopes toward flatter regions of the loss surface. We demonstrate empirically that GC decreases the strength of flatness regularization increases (Fig. 3. In the next section, we will provide a theoretical argument that flatness regularization can control GC.
Flatness regularization:
B1G to GAN training 1 70 73 8C {
Explicit GC regularization and Jacobian regularization: All the forms of regularization above have known benefits for improving the test accuracy in deep learning. As we saw, they all also implicitly regularize GC. This raises the question as whether regularizing for GC directly and independently of any other mechanism is sufficient improve model performance. Namely, we
can add GC computed on the batch to the loss Leg((1) (f) (g(() + a > B V fo (z)]] This is actually a known form of explicit regularization, called Jacobian regularization, which has been
correlated with increased generalization but also robustness to input shift 46 90 25 [6]. [90]
specifically shows that adding Jacobian regularization to the loss function can lead to an increase in test set accuracy (their Tables III, IV, and V). In SM Section
we train MLP on MNIST and

---

R8 on CIFARIO regularized explicitly with the geometric complexity. We observe an increase of test accuracy and a decrease GC with more regularization. Related regularizers include gradient penalties of the form Σ. fo)) - K)² which have been used for GAN training (28, 39 52
We leave the full investigation of the importance of GC outside supervised learning for future work.
5 Impact of implicit regularization on geometrie complexity
Implicit regularization is a hidden form of regularization that emerges as a bi-product of model training. Unlike explicit regularization, is not explicitly added to loss function. In deep learning settings where no explicit regularization is used, it is the only form of regularization. Here, we use combination of theoretical and empirical results to argue that some recently identified implicit exert a regularization pressure geometric complexity. Our argument proceeds as follows: 1) we identify a mathematical term (the implicit gradient regularization term) that characterizes implicit regularization in gradient descent, 2) we demonstrate that this term depends on model gradients, 3) we identify the conditions where model gradient terms apply regularization pressure geometric complexity.
regularization mechanisms in gradient descent 7 65. S
Step 1:
The implicit regularization that we consider emerges as bi-product of the discrete nature of gradient descent updates. particular has been shown that a discrete gradient update 0' L over a batch of data implicitly minimizes a modified loss, LB = LB + 1 V ll? where the second term is called the Implicit Gradient Regularizer (IGR) 77]. Gradient descent optimization is better characterized as a continuous flow along the gradient of the modified loss, rather than the original unmodified loss. By inspection, the IGR term implicitly regularizes training toward trajectories with smaller loss gradients toward flatter region on the loss surface
Step 2: Next, we develop this implicit regularizer term for a multi-class classification cross-entropy loss term. We can write (see SM Section A.2 for details):
h
1 1
" Cz(O). + + h AB(
LB LB LB
(6)
4B
B
where (0) measures the batch gradient alignment
CB =
Σ
(VoI(E,U,0), VoLc',
(7)
B
(# wf)
and Ag()) measures the label gradient alignment:
Ag
(Vol B
(8)
JEB
where e (z) a(fo(=))) Y is the signed residual and denotes the activation function of the last layer. Note that this residual term arises in our calculation using VeL(x, 0) = e ( Vef (x)
...+ e (0)V,, a / (x) (see SM Section A. Eqn. [4h). This development also extends to other widely used loss functions such as the cross entropy and least-square loss.
Step 3: Now, from the modified loss in Eqn. 6 we can observe the conditions under which SGD [z))l to be small: the batch gradient alignment
puts an implicit pressure on the gradient norms V and label gradient alignment terms must be small relative to the gradient norms, positive valued.
We also derive conditions under which this implicit pressure on [ transfers to a regulariz- ing pressure (z)]l (see SM Section A.3 for the proof):.
Theorem 5.1. Consider a logit network fo Rd + g& with layers, then we have the following inequality
(o) Tf(x) +.. (x)
V V=fo(>)
7

---

0.75
0.45
Learning Rate
0.40
0.005
Complexity
0.01
Tast Accuracy
0.4
Train Loss
0.1
0.65
0.3
0.2
0.25
Gsometric
0.60
0.20
0.15
0.50
5000
100001
1000015000200003500
5000 1000015000200001100000
5000 10000 20000 25000
Iteration
Iteration
Iteration
Batch Size
0.75
0.70
0.6
Test Accuracy
0.665
Train Loss
0.5
0.60
128
0.4
0.55
0.3
512
0.50
0.15
0.45
0.10
0.05
0.1
0.00
0.0
20000 40000 60000 100000
20000
40000 60000 Iteration
80000 100000
20000 40000 60000 80000 100000
Iteration
Iteration
Figure 4: Impact of IGR when training ResNet18 on CIFARIO. Top row: As IGR increases through higher learning rates, GC decreases. Bottom row: Similarly, lower batch size leads decreased GC.
where T, is the transfer function for layer given by
1
V (x))2
(x,
(10)
/min(d, k) T (W, (We)o m (h((x)))
where h4 is the subnetwork to layer i and mmax(A) is the maximal singular value of matrix A (i.e., its spectral norm).
Here, we can see that for any settings where the sum Tf(x) +... +... (z) of squared transfer functions diminishes slower than the gradient norm (e during training, we expect that implicit gradient regularization will apply a regularization pressure on GC.
An immediate prediction arising under these conditions is that the size the regularization pressure geometric complexity will depend the implicit regularization rate h/ B in Eqn. (Note that the ratio h/B has been linked to implicit regularization strength in many instances [37
88 69 59 (65).
Specifically, under these conditions, networks trained with larger learning rates smaller batch sizes, or both, will apply a stronger regularization pressure on geometric complexity,
We test this prediction by performing experiments ResNet18 88 trained on CIFARI0 and show results in Figure The results show that while all models achieve a zero train loss, consistently the higher the learning rate, the higher the test accuracy and the lower the GC. Similarly, we observe that the lower the batch size, the lower the GC and the higher the test accuracy.
The increased performance of lower batch sizes has been long studied in deep learning, under the name 'the generalisation gap' 45 51. Crucially however, this gap was recently bridged [32]. showing that full batch training can achieve the same test set performance as mini-batch gradient descent. obtain these results, they use an explicit regularizer similar to the implicit regularizer in Eqn. (6) introduced to compensate for the diminished implicit regularization in the full batch case.
Their results further strengthen our hypothesis that implicit regularization via GC results in improved generalisation.

---

Geometric complexity and double descent
When complexity is measured using a simple parameter count, a double descent phenomena has been consistently observed: as the number of parameters increases, the test accuracy decreases at first, before increasing again, followed by a second descent toward a low test error value [12] excellent overview of the double descent phenomena in deep learning can be found in [12 together with connections to smoothness as an inductive bias deep networks and the role optimization.
751
An
To explore the double descent phenomena using GC we follow the set up introduced in 75 we train multiple ResNet18 networks on CIFAR1O with increasing layer width, and show results in Fig. 5 We make two observations: first, like the test loss, GC follows double descent curve as width increases; second, when plotting GC against the test loss, we observe U-shape curve, recovering the traditional expected behaviour of complexity measures. Importantly, we observe the connection between the generalisation properties of overparametrized models and GC: after the critical region, increase in model size leads to a decrease in GC. This provides further evidence that GC is able capture model capacity in meaningful way, suggestive of a reconciliation of traditional complexity theory and deep learning.
All models
Train/Test Loss
Test Loss
Test loss
2
Train Loss
Train loss
Test Loss
critical region
Seed average
4
0.4
Loss
Train Loss
0.2
Test Loss
0.0
25
50
75
100
125
2 Geometric Complexity le-1
Network Width
Figure 5: Double descent and GC. Left: GC captures the double descent phenomenon. Right: GC captures the traditional U-shape curve, albeit with some noise, showing (top) GC vs Test Loss for all models and (bottom) GC Test Loss averaged across different seeds. We fit 6 degree polynomial to the curves to showcase the trend.
7 Related and Future Work
The aim this work is to introduce a measure which captures the complexity of neural networks. There many other approaches aiming at doing so, ranging from naive parameter count and more data driven approaches [47
to more traditional measures such as the VC dimension and which focus the entire hypothesis space. [77] analyzes existing measures of complexity and shows that they increase as the size of the hidden units increases, and thus cannot explain behaviours observed in over- perammeeeeete neural networks (their Figure 5). 48 performs an extensive study of existing complexity measures and their correlation with generalization. They find that flatness has the strongest positive connection with generalization. M provides generalization bound depending on classification margins and the product of spectral norms of the model's weights and shows how empirically the product of spectral norms correlates with empirical risk. [20] connects Lipschitz smoothness with overparametrization. by providing probabilistic lower bound on the model's Lipschitz constant based on its training performance and the inverse of its number of parameters. In concurrent work (29] discusses the connection between the Jacobian and the Hessian of the loss with respect to inputs, namely the empirical average of ||V and || 1V3LI, over the training set and shows that they follow double-descent curve. [78] investigates empirically complexity measure similar to GC using the Jacobian norm of the full network (rather than the logit network) and evaluating it on test distribution (rather than the train distribution). They show correlation between this measure and generalization in extensive set of experiments.
60
67
Rademacher complexity [
57

---

As we saw in Fig. 1, the interpolating ReLU network with minimal GC is also the piecewise linear function with minimal volume or length [5 In ID this minimal function can be described only with the information given by the data points. This description with minimal information is reminiscent of the Kolmogorov complexity [4 and the minimum description length [3), and we believe that the exact re relationship between these notions, GC, and minimal volume is worth investigating. Similarly,
I argues that flat solutions have low information content, and for neural networks these flat regions are also the regions of low loss gradient and thus of low GC, as explained by the Transfer Theorem in Section 5 Another recent measure of complexity is the effective dimension which is defined in relation to the training data, but is computed using the spectral decomposition of the loss Hessian [67]. making flat regions in the loss surface also regions of low complexity w.r.t. this measure. This hints toward the effective dimension being related to GC. Note that similarly to GC, the effective dimension can also capture the double descent phenomena. The effective dimension is an efficient mechanism for model selection 677. which our experiments seem also to indicate may be the case for GC. Note that the generalized degrees of freedom (which considers the sensitivity of a classifier to the labels, rather than the features GC does) explored in 38 in the context of deep learning also captures the double-descent phenomena.
GC close to considerations about smoothness [8] and the Sobolev norm implicit regularization 165] While GC and Lipchitz smoothness are connected, here we focused on a tractable quantity for neural networks and its connections with existing regularizers. Smoothness regularization has been particularly successful in the GAN literature [88 33 (52) M 128,, and the connection between Lipschitz smoothness and GC begs the question of whether their success is due to their implicit regularization of GC, but we leave the application of GC outside supervised learning for future work.
The Dirichlet energy in Eqn. is well-known quantity in harmonic function theory 27 and a fundamental concept throughout mathematics, physics and, more recently. 3D modeling 19I), manifold learning [1]] and image processing 33 3J. Minimizers of the Dirichlet energy are harmonic and thus enjoy certain guarantees in regularity; i.e. any such solution is a smooth function. It has been demonstrated that for mean squared error regression on wide-shallow ReLU networks, gradient descent is biased towards smooth functions at interpolation [4 Similarly, our work suggests that neural networks, through mechanism of implicit regularization of GC, are biased towards minimal Dirichlet energy and thus encourage smooth interpolation. It may be interesting to understand how the relationship between GC, Dirichlet energy, and harmonic theory can help futher improve the learning process, in particular in transfer learning, or in out-of-distribution generalization.
8 Discussion
In terms of limitations, the theoretical arguments presented in this work have a focus ReLU activations and DNN architectures, with log-likelihood losses coming from the exponential family, such as cross-entropy loss. The experimental results are obtained on the image datasets MNIST and CIFAR using DNN and ResNet architectures.
regression with least-square losses, multi-class classification with
In terms of societal impact, we are not introducing new training methods, but focus on providing better understanding of the impact of common existing training methods. We hope that this understanding will ultimately lead to more efficient training techniques. While existing training methods may have their own risk, we do not foresee any potential negative societal impact of this work.
In conclusion, altogether, geometric complexity provides a useful lens for understanding deep learning and sheds light into why neural networks are able to achieve low test error with highly expressive models. We hope this work will encourage further research around this new connection, and help to better understand current best practices in model training as well as discover new ones.
Acknowledgments and Disclosure of Funding
We would like to thank Chongli Qin, Samuel Smith, Soham De, Yan Wu, and the reviewers for helpful discussions and feedback as well as Patrick Cole, Xavi Gonzalvo, and Shakir Mohamed for their support.
10

---

References
[1] Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep representations. In 2018 Information Theory and Applications Workshop (ITA), pages 1-9, 2018.
[2] Michael Arbel, Danica Sutherland, Mikotaj Binkowski, and Arthur Gretton. On gradient regularizers for mmd gans. Advances in neural information processing systems, 31, 2018.
[3] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Represen- tations, 2018.
[4] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference on Machine Learning. pages 253. PMLR, 2018.
[5] Benny Avelin and Anders Karlsson. Deep limits and a cut-off phenomenon for neural networks. Journal of Machine Learning Research, 23(191), 2022.
[6] David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. International Conference on Muchine Learning, 2018.
[7] David G.T. Barrett and Benoit Dherin. Implicit gradient regularization. In International Conference on Learning Representations, 2021.
[8] Peter L Bartlett, Stéphane Boucheron, and Gábor Lugosi. Model selection and error estimation. Machine Learning, 48 (1):851111333 13, 2002.
[9] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectraaly-normaiizeed margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[10] Peter I. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve- dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-2311, 2019.
[11] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 48244633424411 2002.
[12] Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. 2021.
[13] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 166(3)) 2019.
[14] Johan Bjorck, Carla Gomes, and Kilian Q Weinberger. Towards deeper deep reinforcement learning. arXiv preprint arXiv:2106. 01511, 2021.
[15] Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an omssteinuuhlenbekk like process. In Conference on Learning Theory, 2020.
[16] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension, Journal of the ACM (JACM), 36(4):929-965, 1989.
[17] Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. arXiv preprint arXiv: 1096, 2018.
[18] Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. In International Conference Learning Representations, 2018.
[19] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4): 18-42, 2017.
11

---

[20] Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34:28811 1-28822, 2021.
[21] AIA Chervonenkis and VN Vapnik. Theory of uniform convergence of frequencies of events to their probabilities and problems of search for optimal solution from empirical data(average risk minimization based on empirical data, showing relationship of problem to uniform convergence of averages toward expectation value). Aulomation and Remote Control, 32:207- 217, 1971.
[22] Li Deng. The mnist database of handwritten digit images for machine learning research [best the web]. IEEE signal processing magazine, 2966):141-14, 2012.
[23] Benoit Dherin, Michael Munn, and David G.T. Barrett. The geometric occam's 's razor implicit in deep learning. In Proceedings on "Optimization for Machine Learning" at NeurIPS Workshops, 2021.
[24] Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Joannis Mitliagkas, and Daniel M Roy. In search of robust measures of generalization. Advances in Neural Information Processing Systems, 13:11733-1773, 2020.
[25] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint 1rXiv:1703.11006 2017.
[26] Gamaleldin Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. Advances in neural information processing systems, 31, 2018.
[27] Lawrence C Evans. Partial differential equations, volume 19. American Mathematical Soc., 2010.
[28] William Fedus, Mihaela Rosca, Balaji Lakshminarayanan, Andrew M Dai, Shakir Mohamed, and Ian Goodfellow. Many paths to equilibrium: Gans do not need to decrease a divergence at every step. arXiv preprint arXiv: 1710:0170 2017.
[29] Matteo Gamba, Erik Englesson, Marten Björkman, and Hossein Azizpour. Deep double descent via smooth interpolation. arXiv preprint arXiv:2209. 10080, 2022.
[30] Tianxiang Gao and Vladimir Jojic. Degrees of freedom in deep neural networks. In Proceedings of the Thirdy-Second Conference Uncertainty in Artificial Intelligence, 2016.
[31] Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein. Stochas- tic training is not necessary for generalization. In International Conference on Learning Representations, 2022.
[32] Jonas Geiping, Micah Goldblum, Phillip E Pope, Michael Moeller, and Tom Goldstein. Stochastic training not necessary for generalization. arXiv preprint arXiv:2109.144: 14119, 2021.
[33] Pascal Getreuer. Rudin-osher-fateen total variation denoising using split bregman. Image Processing On Line, 2:74-95, 2012.
[34] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.
[35] Florin Gogianu, Tudor Berariu, Mihaela C Rosca, Claudia Clopath, Lucian Busoniu, and Razvan Pascanu. Spectral normalisation for deep reinforcement learning: optimisation perspective. In International Conference on Machine Learning, pages 3734-3744. PMLR, 2021.
[36] Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning. MIT Press, Cam- bridge, MA, USA, 2016.
12

---

[37] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in I hour. arXiv preprint arXiv: arXiv:/006.02677 2017.
[38] Erin Grant and Yan Wu. Predicting generalization with degrees of freedom in neural networks. In ICML 2022 2nd for Science Workshop. 2022.
[39] Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
[40] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR, 2018.
[41] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In 2015 IEEE International Conference on Computer Vision (ICCV), 2015.
[42] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pages 630-645. Springer, 2016.
[43] Geoffrey E Hinton and Richard Zemel. Autoencoders, minimum description length and helmholtz. free energy. In J. Cowan, G. Tesauro, and J. Alspector, editors, Advances in Neural Information Processing Systems, volume 6. Morgan-Kauffann 1994.
[44] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1-42 1997.
[45] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap large batch training of neural networks. Advances in neurul information processing systems, 30, 2017.
[46] Judy Hoffman, Daniel A. Roberts, and Sho Yaida, Robust learning with jacobian regularization. 2020.
[47] Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distributions. arXiv preprint arXiv: 13, 2018.
[48] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where to find them. In International Conference on Learning Representations, 2020.
[49] Hui Jin and Guido Montúfar. Implicit bias of gradient descent for mean squared error regression with wide neural networks. arXiv preprint arXiv:2006.00 07356, 2020.
[50] Jürgen Jost and Jeurgen Jost. Riemannian geometry and geometric analysis, volume 42005. Springer, 2008
[51] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 1609:v:609.04880 2016.
[52] Naveen Kodali, Jacob Abernethy, James Hays, and Zsolt Kira. On convergence and stability of gans. arXiv preprini
2017.
[53] Naveen Kodali, James Hays, Jacob Abernethy, and Zsolt Kira. On convergence and stability of GANs. In Advances in Neural Information Processing Systems, 2018.
[54] V. Koltchinskii and D. Panchenko. Rademacher processes and bounding the risk of function learning. In High Dimensional Probability II. pages 443-459, Birkhäuser, 1999.
[55] Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transac- tions Information Theory, 1994, 2001.
13

---

[56] Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability II. pages 443-457. Springer, 2000.
[57] Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
[58] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[59] Yoonho Lee, Juho Lee, Sung Ju Hwang, Eunho Yang, and Seungjin Choi. In Advances in Neural Information Processing Systems, 2020.
[60] Yoonho Lee, Juho Lee, Sung Ju Hwang, Eunho Yang, and Seungjin Choi. Neural complexity measures. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9713-9724. Curran Associates, Inc., 2020.
[61] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, volume 31, 2018.
[62] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, 31, 2018.
[63] Henry Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work so well? Journal of Statistical Physics, 168(6): 1223-1247, 2017.
[64] Chao Ma, Lei Wu, et al. The quenching-activation behavior of the gradient descent dynamics for two-layer neural network models. arXiv preprint arXiv:2006. 14450, 2020.
[65] Chao Ma and Lexing Ying. The sobolev regularization effect of stochastic gradient descent. 2021.
[66] David MacKay. Bayesian model comparison and backprop nets. Advances in neural informa- tion processing systems, 4, 1991.
[67] Wesley J Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting in deep models: Effective dimensionality revisited, arXiv preprint arXiv:2003.00 0.00000021399 139, 2020.
[68] David A McAllester. Pac-bayesian model averaging. Proceedings of the twelfth annual conference Computational learning theory, pages 164-170, 1999.
[69] Sam McCandlish, Jared Kaplan, Dario Amodei, and OD Team. An empirical model of large-batch training. arxiv 2018. arXiv preprint
2018
[70] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, 2017.
[71] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral nor- malization for generative adversarial networks. In International Conference Learning Representations, 2018
[72] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of machine learning. MIT press, 2018
[73] Vaishnavh Nagarajan and Zico Kolter. Gradient descent gan optimization locally stable. In Advances in neural information processing systems, 2017.
[74] Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint arXiv:1901.0167,, 2011 2019.
14

---

[75] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.
[76] Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv: 1709.0999,. 2017.
[77] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrization in generalization of neural networks. In International Conference on Learning Representations, 2018.
[78] Roman Novak. Yasaman Bahri, Daniel A Abolañia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: an empirical study. In Interna- tional Conference on Learning Representations, 2018.
[79] Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Krishnamurthy Dvijotham, Alhus- sein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. In Advances in Neural Information Processing Systems, 2019.
[80] Chongli Qin, Yan Wu, Jost Tobias Springenberg, Andy Brock, Jeff Donahue, Timothy Lillicrap, and Pushmeet Kohli. Training generative adversarial networks by solving ordinary differential equations. In Advances in Neural Information Processing Systems, volume 33, 2020.
[81] Mihaela Rosca, Theophane Weber, Arthur Gretton, and Shakir Mohamed. A case for new neural network smoothness constraints. In Proceedings on "I Can't Believe It's Not Better!" at NeurIPS Workshops, volume 137 of Proceedings of Machine Learning Research, 2020.
[82] Mihaela Rosca, Yan Wu, Benoit Dherin, and David G.T. Barrett. Discretization drift in two- player games. In Proceedings of the 38th International Conference on Machine Learning, volume 2021.
[83] Leonid I Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):299-268 1992.
[84] J. Schmidhuber. Discovering neural nets with low kolmogorov complexity and high general- ization capability. Neural networks: the official journal of the International Neural Network Society, 10 5, 1997.
[85] Sihyeon Seong, Yegang Lee, Youngwook Kee, Dongyoon Han, and Junmo Kim. Towards flatter loss surface via nonmonotonic learning rate scheduling. In Proceedings of the Thirty- Fourth Conference on Uncertainty in Artificial Intelligence, 2018
[86] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks, 2018
[87] Samuel I. Smith, Benoit Dherin, David G.T. Barrett, and Soham De. On the origin of implicit regularization in stochastic gradient descent. In International Conference on Learning Representations, 2021.
[88] Samuel L. Smith, Pieter-Jan Kindermans, and Quoe Le. Don't decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018.
[89] Samuel L Smith and Quoe V. Le. A bayesian perspective on generalization and stochastic gradient descent. 2018
[90] Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65:4265-4222 2017.
[91] Justin Solomon,
Leonidas Guibas, and Adrian Butscher. Dirichlet energy for analysis and synthesis of soft maps. In Computer Graphics Forum, volume 32, pages 197-206. Wiley Online Library, 2013.
[92] Eduardo D Sontag et al. Ve dimension of neural networks. NATO ASI Series Computer and Systems Sciences, 168:69-96,, 1998.
15

---

[93] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, XV1(2):244-280, 1971.
[94] VN Vapnik and A Ya Chervonenkis. The method of ordered risk minimization, Avtomatika i Telemekhanika, 8:21-30, 1974.
[95] Dániel Varga, Adrián Csiszárik, and Zsolt Zombori. Gradient regularization improves accuracy discriminative models. 2018.
[96] Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generaliz- ability of deep learning. ArXiv, (DV17005119411 2017.
[97] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
[98] Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena. Self-attention generative adversarial networks. In International conference machine learning, pages 7354-7363. PMLR, 2019.
[99] Yaoyu Zhang, Zhi-Qin John Xu, Tao Luo, and Zheng Ma. A type of generalization error induced by initialization in deep neural networks. In Mathematical and Scientific Machine Learning, pages 144-164. PMLR, 2020.
[100] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109(3):467-492 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [No] The data is widely available (MNIST and CIFAR10). The code we use to train the model is stan- dard training code using standard neural network architectures (MLP and ResNet18) available out-of-the-boo in most ml libraries. We included detailed instructions with all used in the supplemental material to reproduce them.
the hyper-parament
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We use the
CIFAR10 and MNIST datasets for some of our experimental results. We cite both in the paper, for CIFAR following the guidance on Krizhevsky's homepage: https://www.cs www.stooooooooiooo kriz.
16

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
17


Reviews:
[{"review_id": "V7wRWuHw9xH", "reviewer": "Reviewer_UHLw", "summary": "The authors introduce the Geometric Complexity (GC), a novel measure/predictor of neural network performance, based on the evaluation of a discrete Dirichlet energy on the logits in the output of the network. Given that the Dirichlet energy is a measure of how variable a function is, the Geometric Complexity is closely linked to many more common ML notions e.g. regularization and smoothness.\nThe authors argue that keeping a low GC, while training the NN model, allows a test performance improvement. This conclusion is drawn from the observation that a variety of well-known Deep Learning heuristics, including initialization, regularization and fine-tuning of the parameters of the learning algorithm seem to produce models with low GC that generalize well.\nFinally, the authors show that GC can be used to trace the double-descent behavior, in the transition to the over-parametrized regime. \n\nAFTER REBUTTAL\nThe authors have addressed most of the concerns raised in the review process and clarified and expanded upon their work. ", "questions": "- Figure 3: The curve related to L2 norm does not seem to show the expected behavior, can the authors comment on it, or provide a plot where more values are shown in the range of regularization intensity where the GC drops?\n- The accuracies shown in figure 4 seem to be way below the reference performance of a Resnet 18 on CIFAR10. The effect shown in the plot seems very clean, with lower GC and better generalization, but does this apply also close to state-of-the-art performance?\n- Since GC can be explicitly evaluated and the authors argue that many heuristics implicitly minimize it, I think the authors should try a set of experiments where this minimization is done explicitly (even though the required computations may be very expensive). Otherwise, the correlation vs causation question remains open. Is there a reason why such a test was not performed, at least in a small network setting?\n- Is there any other way of using the Dirichlet energy and harmonic theory to guide the learning process?\n- Since the GC is data-dependent, how can it be used in the context of transfer learning and in OOD generalization settings? Could it still provide some useful insight, and would the smoothness vs generalization relationship still hold, even though the network was not trained on that data?\n- Given two different DNN architectures, can their GC still be informative on which will perform best? Can GC be used for model selection? ", "limitations": "I think that the main unaddressed limitation of this work is that the authors do not spend enough time trying to disprove their claim. This could only be achieved by explicitly controlling the GC and finding out whether its minimization is a sufficient drive for effective training.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Computability is an essential property for any performance metric that is proposed to predict NN performance. The authors argue that the Dirichlet energy, while being conceptually close to other smoothness assessment metrics, is much simpler to estimate, as it is simply defined as an expectation over the training set. Moreover, the theoretical connection with harmonic theory allows for a very simple intuition of the concept of smooth interpolators and might be useful for designing better (more explicit) training algorithms.\nWhat seems to be the main weakness of this work is that the assumption of the authors, of the fundamental importance of GC minimization in training DNNs, is only supported through a limited set of positive observations. The authors go through a range of well-known and functioning deep learning heuristics and show the relationship/correlation with a GC decrease. However, it remains unclear whether this decrease is a sufficient/necessary condition for achieving better performance. What would complete this study is a set of experiments where the GC is explicitly controlled and competitive performance is reached, either with an exact GC minimization (probably too computationally expensive), or with some novel regularization technique that aims at GC minimization.\nAnother weak point of this work is in the presented experiments, involving relatively small models and semi-obsolete datasets (MNIST, CIFAR).    ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "B25vBrdkiKy", "reviewer": "Reviewer_jmMn", "summary": "Regularization is key when it comes to model selection; if we seek models that generalize well, choosing the less complex one tends to be a good heuristic in classical machine learning. In deep learning, however, it is not clear what is a good metric to measure the \"complexity\" of a given model, as the classic ones tend to be unreliable (e.g. parameter counting and the double-descent effect), and/or intractable (e.g. VC dimension). \n\nThis work presents a new complexity metric, the Geometric Complexity (GC). Throughout the paper, the authors present their metric in simple scenarios (ReLU and linear networks), relate it with other metrics (Lipschitz smoothness and Dirichlet energy), and empirically demonstrate that many common regularization techniques in DL minimize the GC under the hood. Finally, the authors reproduce the original double descent experiments, and show that GC recovers the traditional U-shaped curve.", "questions": "**Questions (Q)**\n1. What is the training error in section 6? I assume that it is zero, but otherwise I think it is important to show the training error as well. Given that the U-shaped curve explains overfitting, I don't find useful to recover the curve with GC if that does not explain overfitting as in traditional ML. \n\n**Nitpicks (N)**\n1. The quantity $h/B$ in line 246 has been studied before, maybe you want to add a few lines commenting on it. See, e.g., [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://arxiv.org/pdf/1706.02677.pdf), [Don't Decay the Learning Rate, Increase the Batch Size](https://arxiv.org/pdf/1711.00489.pdf), or [An Empirical Model of Large-Batch Training](https://arxiv.org/pdf/1812.06162.pdf).\n2. The font of the figures should be increased.\n3. You should point to specific parts of the SM in the main text, not just the SM in general.\n", "limitations": "I think the authors correctly addressed the limitations of the method.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths (S)**\n1. The main contribution of the paper can be fairly impactful. GC is computable, and it seems to be well correlated with the test error. More importantly, previous work does not need to be thrown away. The authors related GC with other metrics, and showed that effectiveness regularization techniques greatly affect the GC. I expect this work to be impactful.\n2. The paper has a strong empirical flavour, which I find necessary for a paper on this topic. Moreover, the range of methods tested is broad and is well-structured in different sections (initialization, implicit regularization, and explicit regularization).\n3. The theoretical results and claims look sound to me. Specially, the connection of GC with Dirichlet energy is really appealing. However, I have only fully read the main paper and the proofs until A3.\n4. The paper is well written and easy to follow.\n\n**Weaknesses (W)**\n1. While I agree with the authors on removing extra sources of noise for the main experiments (e.g. not using momentum or lr schedulers), there should a section/experiment where all the DL machinery is put together, and compare the GC of those new models with the ones already on the paper. Otherwise, the performance gap is too big compared to other works. For example, test accuracy on CIFAR10 is around 75% in the paper (Figure 4), while using the same model **other works achieve an accuracy of 95.55%** (according to [papers with code](https://paperswithcode.com/sota/image-classification-on-cifar-10?tag_filter=3)).\n2. I feel the paper glosses over connections with the proposed metric. For example, line 186 says that Jacobian regularization basically _minimizes the proposed metric (GC) explicitly_ on the loss, but the topic is covered with 4 lines. This is _really_ important, Jacobian regularization is not just another regularization method to mention. Similarly, section 7 says that GC is similar to Kolmogorov complexity and MDL, but these similarities are not explained anywhere.\n3. I miss some motivation and intuition for the proposed metric, Def. 2.1 feels arbitrary until you read the end of section 2. I think introducing the metric as a modification of Dirichlet energy minimization would feel more natural.\n\n_Note:_ While I can understand and follow all the paper, I am not that well-versed in the topic, and therefore I cannot fully assess the novelty of the proposed metric as I could miss well-known literature. To me, the metric seems novel for this purpose, but strong connections were vaguely mentioned, which I find concerning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6y6fpiPRv6u", "reviewer": "Reviewer_wsiC", "summary": "Summary \n\nThe paper proposes a new notion of complexity measure called geometric complexity (GC) . The paper discusses how GC relates to the familiar concepts in deep learning literature and made extensive links to existing regularizer methods. I enjoyed a lot reading this paper, and found it helpful to understand the connections among all the mentioned regularizers. \n\n\n", "questions": "Please see the above comments for questions. ", "limitations": "The author has addressed the limitations. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Major strength \n1. The paper is well organized and well written. \n2. The authors made extensive analysis to link GC with typical deep learning architectures, demonstrating the connections between existing training regularizers and GC. These links explicitly demonstrate that GC , to some extent,  unify the regularizers in the sense that penalizing these regularizers would simultaneously penalize GC.\n3. In comparison to other complexity measures, GC is more computationally tractable.   \nThe paper empirically evaluates the connection between the generalization property and GC: after the critical region, increasing model size would necessarily decrease GC, showing the usefulness of GC in estimating the generalization error, showing potential benefits of using GC to improve generalization.  \n\nQuestions. \nI am not expert on this complexity measurement topic, but I have some basic understanding of complexity measures. If you don’t mind me asking, what is the advantage of GC over Rademacher complexity? Is it because GC is more computationally convenient?  Is it possible to compare these two types of complexity in some sense empirically or theoretically? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept