{'fraction_non_alphanumeric': 0.04170850234949195, 'fraction_numerical': 0.012711353869633318, 'mean_word_length': 4.211826268969126, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
What training reveals about neural network complexity

This work explores the Benevolent Training Hypothesis (BTH) which argues that the complexity of the function a deep neural network (NN) is learning can be deduced by its training dynamics. Our analysis provides evidence for BTH by relating the NN's Lipschitz constant at different regions of the input space with the behavior of the stochastic training procedure. We first observe that the Lipschitz constant close to the training data affects various aspects of the parameter trajectory, with more complex networks having a longer trajectory, bigger variance, and often veering further from their initialization. We then show that NNs whose 1st layer bias is trained more steadily (i.e., slowly and with little variation) have bounded complexity even in regions of the input space that are far from any training point. Finally, we find that steady training with Dropout implies a training- and data-dependent generalization bound that grows poly-logarithmically with the number of parameters. Overall, our results support the intuition that good training behavior can be a useful bias towards good generalization.


Introduction
Though neural networks (NNs) trained on relatively small datasets can generalize well, when employing them on unfamiliar tasks significant trial and error may be needed to select an architecture that does not overfit [1]. Could it be possible that NN designers favor architectures that can be easily trained and this biases them towards models with better generalization?
In the heart of this question lies what we refer to as the "Benevolent Training Hypothesis" (BTH), which argues that the behavior of the training procedure can be used as an indicator of the complexity of the function a NN is learning. Some empirical evidence for BTH already exists: (a) It has been observed that the training is becoming more tedious for high frequency directions in the input space [2] and that low frequencies are learned first [3]. (b) Training also slows down the more images/labels are corrupted [4], e.g., the Inception [5] architecture is 3.5× slower to train when used to predict random labels than real ones. (c) Finally, Arpit et al. [6] noticed that the loss is more sensitive with respect to specific training points when the network is memorizing data and that training slows down faster as the NN size decreases when the data contain noise.
From the theory side, it is known that the training of shallow networks converges faster for more separable classes [7] and slower when fitting random labels [8]. In addition, the stability [9] of stochastic gradient descent (SGD) implies that (under assumptions) NNs that can be trained with a small number of iterations provably generalize [10,11]. Intuitively, since each gradient update conveys limited information, a NN that sees each training point few times (typically one or two) will not learn enough about the training set to overfit. Despite the elegance of this claim, the provided explanation does not necessarily account for what is observed in practice, where NNs trained for thousands of epochs can generalize even without rapidly decaying learning rates.

Quantifying NN complexity
This work takes a further step towards theoretically grounding the BTH by characterizing the relationship between the SGD trajectory and the complexity of the learned function. We study neural networks with ReLU activations, i.e., parametric piece-wise linear functions. Though many works measure the complexity of these networks via their maximum number of linear regions [12][13][14][15], it is suspected that the average NN behavior is far from the extremal constructions usually employed theoretically [16].
We instead focus on the Lipschitz continuity of a NN at different regions of its input. For networks equipped with ReLU activations, the Lipschitz constant in a region is simply the norm of the gradient at any point within it. The distribution of Lipschitz constants presents a natural way to quantify the complexity of NNs. Crucially, NNs with a bounded Lipschitz constant can generalize beyond the training data, a phenomenon that has been demonstrated both theoretically [17][18][19] and empirically [20]. The generalization bounds in question grow with the Lipschitz constant and the intrinsic dimensionality of the data manifold, but not necessarily with the number of parameters 1 , which renders them ideal for the study of overparameterized networks.

Main findings: connecting training behavior and neural network complexity
We link training dynamics and NN complexity close and far from the training data (see Figure 1).
NN complexity close to the training data. Section 4 commences with a simple observation: SGD updates the 1st layer bias more quickly if the learned function has a large Lipschitz constant near a sampled data point. This implies that the length of the bias trajectory grows linearly with the Lipschitz constant of the NN on its linear regions that contain training data (Theorem 1). Based on this insight, we deduce that (a) near convergence, the parameters of more complex NNs vary more across successive SGD iterations (Corollary 2), and (b) the distance of the trained network to initialization is small if the learned NN has a low complexity (near training data) throughout its training, with the first few high-error epochs playing a dominant role (Corollary 3).
NN complexity far from the training data. Section 5 focuses on the relationship between training and the Lipschitz constant in empty regions of the input space, i.e., linear regions of the NN that do not contain training points. We first show that the Lipschitz constants in empty regions are linked with those of regions containing training points (Theorem 2). Our analysis implies that NNs whose parameters are updated more slowly during training have bounded complexity in a larger portion of the input space. We then demonstrate how training NNs with Dropout enables us to grasp more information about the properties of the learned function and, as such, to yield tighter estimates for the global Lipschitz constant. Our findings yield a dataand training-dependent generalization bound that features a poly-logarithmic dependence on the number of parameters and depth (Theorem 3). On the contrary, in typical NN generalization bounds the number of samples needs to grow nearly linearly with the number of parameters [23][24][25] or exponentially with depth [26][27][28][29][30].
All proofs can be found in Appendix B, whereas Appendices A and C contain additional empirical and theoretical results, respectively.

Related works
The Lipschitz constant of NNs. Since exactly computing the Lipschitz constant is NP-hard [31], its efficient estimation is an active topic of research [31-34, 22, 35]. Our work stands out from these works both in motivation (i.e., we connect training behavior with NN complexity) and in the techniques developed (we are not employing any complex algorithmic machinery to estimate the Lipschitz constant of a trained model, but we bound it as the NN is being trained based on how weights change). Empirically, Lipschitz regularization has been used to bias training towards simple and adversarially robust networks [36][37][38][39][40][41][42]. Theoretically, the Lipschitz constant is featured prominently in the generalization analysis of NNs (e.g., [26][27][28]), but most analyses depend on sensitivity w.r.t. parameter perturbation, which is related but not identical to the Lipschitz constant.
Dropout and generalization. The Dropout mechanism and its variants are standard tools of the NN toolkit [43-45] that regularize training [46,47] and help prevent memorization [6]. The effect of Dropout on generalization have been theoretically studied primarily for shallow networks [48,49,47] as well as for general classifiers [50]. The generalization bounds that apply to deep networks are normbased and generally grow exponentially with depth [51,52] or are shown to scale the Rademacher complexity by the Dropout probability (for Dropout used in the last layer) [53]. We instead base our analysis on arguments from [18,19] and exploit the properties of ReLU networks to derive a bound that features a significantly milder dependency on the NN depth.
Flat and sharp minima. Flat minima correspond to large connected regions with low empirical error in weight space and have been argued to correspond to networks of low complexity and good generalization [54]. It has also been shown that SGD converges more frequently to flat minima [55][56][57][58][59]. Different from the current work that focuses on the sensitivity w.r.t. changes in the data, flatness corresponds to a statement about local Lipschitz continuity w.r.t. weight changes. In addition, whereas flat minima are regions of the space where the loss is low, our main results account for more complex loss behaviors (by means of an appropriate normalization). Note also that some works argue that the flat/sharp dichotomy may not capture all necessary properties [60][61][62] as flat minima can be made sharp by a suitable reparameterization [61], and flat and sharp minima may be connected [61].
Training dynamics of NNs. Many authors have studied the training dynamics of NNs [63][64][65][66][67][68][69], arguing that, with correct initialization and significant overparameterization, SGD converges to a good solution that generalizes. Our work complements these studies by focusing on how the SGD trajectory can be used to infer NN complexity. Arora et al. [8] connect the trajectory length and generalization performance via the Neural Tangent Kernel (NTK). Most analyses based on the NTK ("lazy" regime) or mean field approximation ("adaptive" regime) focus on 2-or 3-layer networks. In contrast to these works, we make no assumptions on initialization or NN size.

Preliminaries and background
Suppose that we are given a training dataset (X, Y ) consisting of N training points X = (x 1 , . . . , x N ) and the associated labels Y = (y 1 , . . . , y N ), with x i ∈ X ⊆ R n and y i ∈ Y ⊆ R.
We focus on NNs defined as the composition of d layers Above, W l ∈ R n l ×n l−1 and b l ∈ R n l with n 0 = n and n d = 1, and w = (W 1 , b 1 , . . . , W d , b d ) are the network's parameters. For all layers but the last, ρ l will be the ReLU activation function, whereas ρ d may either be the identity ρ d (x) = x (regression) or the sigmoid function ρ d (x) = 1/(1 + e −x ) (classification).
We optimize w to minimize a differentiable loss function using stochastic gradient descent (SGD). The optimization proceeds in iterations t and each parameter is updated as follows: where x (t) ∈ X is a point sampled with replacement from the training set at iteration t, y (t) is its label, and α t is the learning rate. It will also be convenient to refer to f (·, w (t) ) as f (t) .

Linear regions
A well-known property of NNs with ReLU activations is that they partition the input space into regions (convex polyhedra) R ⊆ R n within which f is linear. This viewpoint will be central to our analysis.
There is a simple way to deduce this property from first principles. When ρ d is the identity, each f can be equivalently expressed as where we have defined the input-dependent binary diagonal matrices being the indicator function applied element-wise. The key observation is that, when the neuron activations S l (x) are fixed for every layer, the above function becomes linear. Thus, each linear region R of f contains those points that yield the same neuron activation pattern.
Since the activation pattern of any region is uniquely defined by a single point in that region, we write R x to refer to the region that encloses x.

Local and global Lipschitz constants
A function f is Lipschitz continuous with respect to a norm · 2 if there exists a constant λ such that for all x, The Lipschitz constant of f is then simply the largest gradient within any linear region λ f = sup x∈X ∇f (x, w) 2 . The latter is typically upper bounded by λ prod f = l W l 2 which is known to be a loose bound [21,22]. For a more formal treatment that also accounts for different types of activation functions and vector-valued outputs, the reader may refer to [22]. 4 Relating training behavior to NN complexity close to the training data Our analysis commences in Section 4.1 by deriving a general result that bounds the (appropriately normalized) length of the SGD trajectory over any training interval with the Lipschitz constant of the NN close to training data. Our results on the distance to initialization and weight variance will be implied as corollaries in Section 4.2.

Bounding the length of the SGD trajectory
Theorem 1 formalizes a simple observation: the gradient of a neural network with respect to its input is intimately linked to that with respect to the bias of the first layer. This implies that, by observing how fast the bias of the network is updated, we can deduce what is the Lipschitz constant of the learned function on the linear regions of the input space encountered during training.
Theorem 1 (Trajectory length). Let f (t) be a d-layer NN being trained by SGD. Further, denote by the gradient of the loss with respect to the NN's output at iteration t. For any set T of iteration indices within which the gradient is not zero, the (normalized) bias trajectory is upper/lower bounded as Theorem 1 shows that lower complexity learners will have a shorter (normalized) bias trajectory. If , y (t) ) and α t remain approximately constant throughout T , the trajectory will grow linearly with the Lipschitz constant of the learner close to the training data.
Why we focus on the first layer bias. It might be originally surprising that the gradient w.r.t. b 1 is indicative of NN complexity. While the value of b 1 is not particularly informative, it turns out that the way it changes over successive SGD iterations reflects the operation of the entire NN: since b 1 and x are processed by the NN in a similar fashion, the sensitivity of the NN output w.r.t. changes in the bias relates to those induced by changes in the input. Indeed, via the chain rule, we have where, for simplicity of exposition, we consider here the case in which ρ d is the identity function and thus S d (x) = 1. The above equation also explains why the singular values of W 1 appear in the bound: since the gradient of b 1 does not yield information about W 1 , we account for it separately. Alternatively, as explained in Appendix C.2, the first layer Lipschitz constant can be controlled by also taking into account the dynamics of W 1 and W 2 . We also note that an identical argument can be utilized to connect the gradient of b l with the Lipschitz constant of f d • · · · • f l+1 (x).
Understanding the normalization. The normalization by α t f (t) (x (t) , y (t) ) renders the bound independent of the learning rate α t as well as of how well the network fits the training data. When a mean-squared error (MSE) and a binary cross-entropy (BCE) loss is employed with y,ŷ ∈ R and y,ŷ ∈ [0, 1], respectively, we have In both cases, f (x, y) measures the distance between the true label and the NN's output.
Applicability to other architectures. Beyond fully-connected layers, Theorem 1 directly applies to layers that involve weight sharing and/or sparsity constraints, such as convolutional and locallyconnected layers, as long as b 1 remains non-shared. In addition, the result also holds unaltered for networks that utilize skip connections or max/average pooling after the 1st layer, as well as for NNs with general element-wise activation functions (see Appendix C.1).
Dependence on the singular values of W 1 . The lower bound presented in Theorem 1 can be expected to be much tighter than the upper bound since the largest singular value is usually a reasonably small constant, whereas the smallest may be (close to) zero. Fortunately, the upper bound can be tightened when the data fall within some lower-dimensional space S. In that case, one may substitute the minimum singular value with the minimum of W (t) 1 x 2 for all x ∈ S of unit norm.

Corollaries: steady learners, variance of bias, and distance to initialization
Suppose that after some iteration our NN has fit the training data relatively well. We will say that the NN is a "steady learner" if its 1st layer bias is updated slowly: The following is a simple corollary: Consider an interval T of iterations after τ and suppose that σ 1 (W (t) 1 ) ≤ β for every t ∈ T . Select an iteration t ∈ T at random. The Lipschitz constant of f (t) at every training point x ∈ X will be bounded by λ f (t) (R x ) ≤ β ϕ, generically, i.e., with probability that converges to 1 as |T | grows.
Crucially, the bound of Corollary 1 can be exponentially tighter than the product-of-norms bound λ prod f : whereas βϕ does not generally depend on depth, λ prod f (R x ) = w d when W l 2 = w. We will also use Theorem 1 to characterize two other aspects of the training behavior: the parameter variance as well as the distance to initialization. The following corollary shows that the weights of high complexity NNs cannot concentrate close to some local minimum: Corollary 2 (Variance of bias). Let f (t) be a d-layer NN with ReLU activations being trained by SGD. Let T be a set of iteration indices and write for the square-root of the harmonic mean of the squared loss derivatives within T . Then, the bias of the first layer will exhibit variance at least: (1) Therefore, a larger complexity NN will need to fit the training data more closely (so that harm (T ) decreases) to achieve the same variance as that of a lower complexity NN.
We can also deduce that the bias will remain closer to initialization for NNs that have a smaller Lipschitz constant: Corollary 3 (Distance to initialization). Let f (t) be a d-layer NN being trained by SGD with an MSE loss and fix some iteration τ . The first layer bias may move from its initialization by at most .
The latter result is only meaningful in a regression setting. When using the BCE loss, the loss derivative can grow exponentially when the classifier is confidently wrong. On the contrary, with an MSE loss in place the loss derivative grows only linearly with the error, rendering the bound more meaningful.
When α t and f (t) (x (t) , y (t) ) decay sufficiently fast, the bound depends on σ n (W (t) 1 ) and the (normalized) Lipschitz constant at and close to initialization. Therefore, the corollary asserts that SGD with an MSE loss can find solutions near to initialization if two things happen: the NN fits the data from relatively early on in the training while implementing a low-complexity function close to the training data.

NN complexity far from the training data
Our exploration on the relationship between training and the complexity of the learned function thus far focused only on regions of the input space that contain at least one training point. It is natural to ask how the function behaves in empty regions. After all, to make generalization statements we need to ensure that the learned function has, with high probability, bounded Lipschitz constant close to any point in the training distribution.
Next, we provide conditions such that a NN that undergoes steady bias updates, as per Definition 1, also has low complexity in linear regions that do not contain any training points. Our analysis starts in Section 5.1 by relating the Lipschitz constant of regions in and outside the training data. We then show in Section 5.2 how learners that remain steady while trained with Dropout have a bounded generalization error.
A central quantity in our analysis is the activation s t (x) associated with each x: Thus, s t (x) is the Kronecker product of all activations when the NN's input is x.
We will also assume that the learned function f (t) eventually becomes consistent on the training data: Assumption 1 is weaker than requiring that the parameters have converged: the parameters are allowed to keep changing as long as the slope and activation pattern on each training point remains similar. We also stress that the NN can still have different activation patterns at different points (and thus be highly non-linear), as long as these activations stay persistent over successive iterations. Naturally, it is always possible to satisfy our assumption by decaying the learning rate appropriately.

The Lipschitz constant of empty regions
As we show next, the Lipschitz constant of a NN can be controlled for those regions whose neural activation can be written as a combination of activations of training points. Theorem 2. Let T be any interval of SGD iterations that satisfies Assumption 1, and suppose that the binary matrix whose columns are the neural activations of all points sampled within T , the vector containing the normalized bias updates, and the distance to integrality if a sigmoid is used in the last layer. Select a point x ∈ R n that is not in the training set. For all t ∈ T , the Lipschitz constant of f (t) in R x is bounded by the following Basis Pursuit problem: where is the Hadamard product, ξ = 0.25 if a sigmoid is used and ξ = 1, otherwise.
To grasp an intuition of the bound, suppose that we are in a regression setting (ξ = 1) and that the interval T is large enough so that we have seen all training points. Theorem 2 then implies: By itself, Theorem 2 does not suffice to ensure that the function is globally Lipschitz because the theorem does not have predictive power for points x whose activation s t (x) cannot be written as a linear combination S T a of activations of the training points. A sufficient condition for the theorem to yield a global bound is that S T is full rank, but the latter can only occur for N ≥ n d · · · n 1 , a quantity that grows exponentially with the depth of the network. Section 5.2 will provide a significantly milder condition for networks trained with Dropout.

Learners that remain steady with Dropout generalize
Dropout entails deactivating each active neuron independently with probability p. We here consider the variant that randomly deactivates each neuron independently 2 at the end of the forward-pass with probability 1 /2. We focus on binary NN classifiers trained with a BCE loss, and with the NN's last layer using a sigmoid activation. The empirical and expected classification error is, respectively, given by Theorem 3 controls the generalization error in terms of the number N (X ; 2 , r t (X)) of 2 balls of radius r t (X) needed to cover the data manifold X . The radius is shown to be larger for more steadily trained classifiers (through 1/ϕ) and to depend logarithmically on the number of neurons: Theorem 3. Let f (t) be a depth d NN with ReLU activations being trained with SGD, a BCE loss and 1 /2-Dropout.
Suppose that f (t) is (τ, ϕ)-steady and that for every t ≥ τ the following hold: l (x))] i > 0 is the minimum frequency that any neuron is active before Dropout is applied.
For any δ > 0, with probability at least 1 − δ over the Dropout and the training set sampling, the generalization error is at most where N (X ; 2 , r) is the minimal number of 2 -balls of radius r needed to cover X .

Intuition.
Recall that the bounds derived in Section 4 only concern the regions of the NN that contain at least one training point. However, due to the geometry of these regions, it is possible (and likely) that small empty regions will be located near those that have training data inside them. Deriving a generalization bound would require upper bounding the Lipschitz constant of the NN on these empty regions. Unfortunately, to our knowledge, the latter is not possible without resorting to loose product-of-norms bounds or imposing strong additional assumptions that assert that the training regions are sufficiently diverse (as Theorem 2 does). Here is where Dropout comes in. Dropout introduces stochasticity in the training procedure that provides information of the NN function in the gaps between training data. This allows us to infer the Lipschitz constant of the function in larger portions of the space from the training behavior -and thus to relax the assumptions of Theorem 2. Specifically, the proof approximates the global Lipschitz constant as follows: It then invokes a robustness argument [18, 19] to control the generalization error. The bound above comes in sharp contrast with the product-of-norms bound λ prod f , which grows exponentially with d and can be arbitrary larger than λ f (t) , since there exists parameters for which λ f = 0 and λ prod f > 0.
Understanding the assumptions made. The strongest requirement posed by Theorem 3 is that every neural pathway is activated for each training point: for every x ∈ X . In contrast to Theorem 2, the latter can be satisfied even when N = 1, e.g., if there exist some training point for which all neurons are active. However, the assumption will not hold when some entries of s t (x) are never activated after iteration τ . Little can also be said about the global behavior of f (t) when there are neurons that are not periodically active (which would also imply p min = 0). We argue however that such neurons can be eliminated without any harm as, by definition, they are not affecting the NN's output after τ .
Dependence on the classifier's confidence. According to Theorem 3, the best generalization is attained when the classifier has some certainty about its decisions on the training set (so that |1 − 2f (t) (x i )| = Ω(1)), while also not being overconfident (so that µ (1 − µ) = O(1)).
Dependence on the data distribution and the number of parameters. A interesting property of the bound is that it depends on the intrinsic dimension of the data rather than the ambient dimension.
training points suffice to ensure generalization. This sample complexity bound grows polylogarithmically with the number of neurons n d · · · n 1 and the number of parameters when c ϕ = O(1).
On the contrary, since the radius r of the 2 balls used in the covering grows inversely proportionally to the Lipschitz constant, if the product-of-norms bound was used in our proof, then the sample complexity would be exponentially larger:

Experiments
We test our findings in the context of two tasks: Task 1. Regression of a sinusoidal function with increasing frequency. In this toy problem, a multi-layer perceptron (MLP) is tasked with fitting a randomly-sampled 2D sinusoidal function with increasing frequency (0.25, 0.5, 0.75, 1) isometrically embedded in a 10-dimensional space. More details can be found in Appendix A.1. The setup allows us to test our results while precisely controlling the complexity of the ground-truth function: fitting a low-frequency function necessitates a smaller Lipschitz constant than a high-frequency one. We trained an MLP with 5 layers consisting entirely of ReLU activations and with the 1st layer weights being identity. We repeated the experiment  Figure 3: A closer inspection of how the bias is updated. The variance is computed over the last 10 epochs. As seen, the bias of higher complexity NNs varies more close to convergence (Corollary 2). Further, with an MSE loss, high complexity NNs may veer off further from initialization (Corollary 3).
10 times, each time training the network with SGD using a learning rate of 0.001 and an MSE loss until it had fit the sinusoidal function at 100 randomly generated training points.
Task 2. CIFAR classification under label corruption. In our second experiment, we trained a convolutional neural network (CNN) to classify 10000 images from the 'dog' and 'airplane' classes of CIFAR10 [74]. The classes were selected at random. We focus on binary classification to remain consistent with the theory. Inspired by [4], we artificially increase the task complexity by randomly corrupting a (0, 0.2, 0.4, 0.6) fraction of the training labels. Thus, a higher corruption implies a larger complexity function. Differently from the first task, we used a CNN with 2 convolutional layers featuring ReLU activations in intermediate layers and a sigmoid activation in the last. We set the first layer identically with the regression experiment. We repeated the experiment 8 times, each time training the network with SGD using a BCE loss and a learning rate of 0.0025.
In agreement with previous studies [4,6,3,2], Figure 2 shows that training slows down as the complexity of the fitted function increases. Figures 2b and 2e depict the per-epoch bias trajectory: , y (t) ) According to Theorem 1, this measure captures the Lipschitz constant λ f (t) (R x (t) ) of the NN during each epoch and across all training points. In agreement with our theory, the bias trajectory is significantly longer when fitting higher complexity functions. The length of the total trajectory is the integral of the depicted curve, see Appendix A.4. Moreover, as shown in Fig 2c, the trajectory length also correlates with the loss of the network on a held-out test set, with longer trajectories consistently corresponding to poorer test performance.
We proceed to examine more closely the behavior of b (t) 1 during training. Figures 3a and 3b corroborate the claims of Corollaries 2 and 3, respectively: when fitting a lower complexity function and an MSE loss is utilized, the bias will remain more stable (here we show the variance in the last 10 epochs) and closer to initialization. The same variance trend can be seen in Figure 3c for image classification. The distance-to-initialization analysis is not applicable to classification (due to the BCE gradient being unbounded), but we include the figure in Appendix A.2 for completeness.
Additional results. The interested reader can refer to Appendices A.3 and A.4 for visualizations of the Lipschitz constants within linear regions and of the total bias trajectory length. Appendices A.6 and A.5 test how our findings are affected by the batch size and architecture, whereas Appendix A.7 examines the training dynamics associated with deeper layer biases.

Conclusion
This paper showed that the training behavior and the complexity of a NN are interlinked: networks that fit the training set with a small Lipschitz constant will exhibit a shorter bias trajectory and their bias will vary less. Though our study is of primarily theoretical interest, our results provide support for the Benevolent Training Hypothesis and suggest that favoring NNs that exhibit good training behavior can be a useful bias towards models that generalize well.
At the same time, there are many aspects of the BHT that we do not yet understand: what is the effect of optimization algorithms and of batching on the connection between complexity and training behavior? Does layer normalization play a role? What can be glimpsed by the trajectory of other parameters? We believe that a firm understanding of these questions will be essential in fleshing out the interplay between training, NN complexity, and generalization.

A.1 Description of Task 1
The input data of Task 1 are generated by the following two step procedure: First, we sample N = 100 points z i ∈ [−1, 1] 2 uniformly at random and assign them a ground truth label according to the sinusoidal function: where ω is interpreted as a frequency and we set ω ∈ {0.25, 0.5, 0.75, 1.0} in our experiments. The four resulting functions are visualized in Figure 5.
We then determine {x i } N i=1 by isometrically embedding {z i } N i=1 into R 10 . We achieve this by selecting the first 2 columns R ∈ R 10×2 of a random 10 × 10 unitary matrix and setting x i = R z i . This procedure ensures that the distances between points remains the same in high dimensions.  As explained in Section 4.2, when a BCE loss is utilised, the derivative of the loss becomes unbounded which stops Corollary 3 from applying. Interestingly, Figure 4 confirms this by showing that the distance is not an increasing function of complexity. The reverse phenomenon can be observed when an MSE loss is utilized (see Figure 3b).

A.3 Visualizing linear regions
Aiming to gain intuition about the behavior of NNs in linear regions close and far the training data, we take a closer look at the function an MLP is learning when trained to solve task 1 (ω = 0.5, 2 hidden layers, N = 200). Figures 6a and 6b depict, respectively, the real and learned function projected in 2D (recall that the true function is isometrically embedded in 10D). Blue dots are training data points. The boundaries between region are indicated with black lines. As observed, there is a large number of linear regions of varying sizes with the smaller and more densely packed regions being found close to the (0,0) point.
The bottom two panels display the local Lipschitz constants (i.e., the magnitude of the gradient within every region). In Figure 6c we can see the real constants at all regions. Interestingly, it appears that low-and high-Lipschitz constants are clustered, which likely follows from the hierarchical region formation process: in other words, regions within the same cluster fall within the same region of a shallower sub-network and are split by a higher layer.

Figure 6d distinguishes between regions containing training points (in white) and the rest (in color).
We color empty regions depending on the bound given by Theorem 2 and black regions are those for which the theorem does not have predictive power. We observe that, though the proposed theory allows us to make statements about the function behavior far from the training data, the theory does not explain the global behavior of the NN. This motivates the introduction of Dropout in the analysis of Section 5.2: by exploiting stochasticity we can infer more properties about the NN complexity from the training trajectory. Intuitively, using Dropout during a sufficiently long training, one is able to deduce from the observed bias updates (specifically vector ϕ T in Theorem 2) the Lipschitz constants within more regions (thus they would also bound the Lipschitz constant within some of the non-white regions in Fig 6d). Moreover, though encountering each and every region in the training would likely take a very long time, Theorem 2 implies that only a small subset of regions suffice to approximate the global Lipschitz constant up to a logarithmic factor.
We finally observe that, in the regions were it applies, Theorem 2 yields a bound that is a constant factor away from the real local Lipschitz constants: the bound overestimates the constants by roughly a factor of four.  A side-by-side comparison with Figures 2a and 2d reveals that, between any two NNs that have fitted the training data equally well, the one that implements a higher complexity function has consistently a longer trajectory.

A.5 Effect of architecture on bias trajectory
We next evaluate the effect of the NN architecture on the optimization trajectory. We focus on the MNIST dataset [75] and train an MLP and a CNN to distinguish between digits '3' and '6' based on a training set consisting of 100 and 1000 images per class. For consistency with the previous experiments, we used the same NN architectures for the MLP and CNN as those employed for Tasks 1 and 2, respectively (though both NNs now feature a sigmoid activation in the last layer). The networks are trained using SGD with a BCE loss and a learning rate of α t = 0.002. Figure 8 depicts the training loss, normalized bias trajectory length, and test loss for each dataset. Note that, in contrast to Figure 2, here all three measures are computed over time-intervals of 100 iterations (rather than per epoch). As expected, when the training set is small, both architectures fit the training data equally well after roughly 20k iterations, but the CNN overfits less. By observing the length of the bias trajectory, we deduce that the MLP is learning a more complex function than the CNN. Thus, in the MNIST100 case, there is a correlation between trajectory length and generalization with the NN architecture that is more appropriate for the task exhibiting a shorter trajectory. It is important to remark that the complexity of the learned function is not the sole factor driving generalization (though it is can be a crucial factor all other things being equal). Convolutional layers are indeed more constrained and better suited to image data than fully convolutional ones -thus it is reasonable to expect better generalization than MLPs. Nevertheless, our experiment shows that the CNN, beyond having the right architecture for the task, also learns a slightly lower complexity function than the MLP while fitting the training data equally well or better. Thus, here we mainly use the bias trajectory length as a diagnostic tool that helps us understand what functions the two architectures are learning.

A.6 Effect of batch size on bias trajectory
This experiment investigates the effect of different batch sizes on the bias trajectory. We adopt the same setup as that of Task 1 (specifically ω = 0.25 and 0.75 in Figure 9) and train NNs with SGD using batch sizes of 16 and 32, whereas our original experiment used a batch size of 1.  The results are consistent with those of Figure 2, with a longer bias trajectory indicating that the NN is fitting a more complex hypothesis and correlating with higher test loss. Increasing the batch size from 1 to 32 also leads to a slight increase in trajectory length, though we currently lack mathematical evidence that support this empirical observation.

A.7 The trajectory of higher layer biases
Our last experiment examines the training dynamics associated with the biased of higher layers. We focus on Task 1 and replicate the experiment described in Section 6, but now we track the normalized bias trajectory length of all biases and optimize W 1 freely. Figure 10 reports the obtained results. It can be observed that the bias dynamics correlate with task complexity for the first three layers, while being uncorrelated for the last two. To interpret these results, we recall that in the proof of Lemma 1 the trajectory length of b l relates to the Lipschitz constant of subnetwork f d←l+1 = f d • · · · • f l+1 close to the training data. Then, noticing how the trajectory length decays by almost an order of magnitude at each layer, we may infer that the Lipschitz constant of f d←l+1 decays quickly with l. The latter implies that the NN predominantly employs the first few layers to solve the task, whereas the last two layers implement very simple functions.

B Deferred technical arguments B.1 A simple Lemma
Lemma 1. Let f (t) be a d-layer NN at the t-th SGD iteration, denote by x (t) ∈ X the point of the training set sampled at that iteration, and set The Lipschitz constant of 1 .
Let us start with some basics. By the chain rule, we have , whereas the gradient w.r.t. the bias of the -th layer is given by l (x (t) ).
Note that the above equation abuses notation for the last layer activation S (t) d (x (t) ). Specifically, depending on whether we are using an identity or sigmoid activation function in the last layer, we set where Part 1. Define the following shorthand notation: It follows from definition that .

(4)
Part 2. We are interested in upper bounding the Lipschitz constant λ f (t) of the NN close to the training data X.
Let R x (t) be the region associated with point x (t) and R f (t) 1 (x (t) ) the region of the NN f associated with point f d←2 and f (t) are related as follows: whereas .
Combining (5) with (6), we obtain Part 3. Re-organizing the SGD expression and taking the norm, we have implying also as claimed.

B.2 Proof of Theorem 1
The proof of the theorem follows directly from Lemma 1 by summing over the training trajectory: .

B.3 Proof of Corollary 1
For any point x with label y and iteration t ∈ T , we say that condition The above is the same condition as in the corollary statement but applied to an arbitrary point x.
Write κ t to refer to the number of training points where N is the size of the training set.
We also suppose that there are ξ iterations within T for which κ t < N : these are the iterations where the Lipschitz constant is larger than βϕ for at least one point in the training set.
Since we sample x (t) i.i.d. from X, the probability that c t (x (t) ) is satisfied for every t ∈ T is at most By noting that above corresponds to the probability that the NN is (τ, ϕ)-steady, we deduce that ξ cannot grow with |T | (otherwise, the probability that the NN is (τ, ϕ)-steady would become zero as |T | → ∞, which contradicts the corollary assumptions).
To complete the derivation, we note that if we select the iteration t at random from T , the probability that there will be some , which converges to 0 as |T | grows.

B.4 Proof of Corollary 2
We consider the interval T = {t 1 + 1, . . . , t 2 } and fix |T | to be the average bias. Working as in the proof of Theorem 1, we deduce .
We then proceed to upper bound the trajectory length studied in Theorem 1 in terms of the (empirical) variance of the bias: Thus, we have The proof concludes by noticing that the right-most term corresponds to a harmonic mean of

B.5 Proof of Corollary 3
Suppose that we train our NN for τ iterations and set T = {0, . . . , τ −1}. The distance to initialization is bounded by . We obtain the final expression by arguing as in the proof of Theorem 1 to write: .

B.6 Proof of Theorem 2
We will start by proving the following Lemma: Lemma 2. Let R x be a linear region of f (t) and suppose that there exists a vector a ∈ R |T | such that for all indices {i l } l=1,··· ,d−1 , with i l ∈ {1, . . . , n l }. Then, f (t) is Lipschitz continuous within R x and its Lipschitz constant is at most Proof. The gradient of a network f (t) at at point x is simply Term q (t) (x) can be expanded as follows: Thus, under the main Lemma condition it is also true that Note that in the second step above we have used Assumption 1 to argue that the training point activation patterns do not change within T .
The above analysis implies that with the 3rd step being true due to the triangle inequality and the 5th follows from Assumption 1.
The proof continues by realizing that, for every index set i d−1 , · · · , i 1 there exists an entry i such that Therefore, condition (9) is equivalent to asserting that Let us focus on |S (t) When there is no activation in the last layer, the term is trivially ξ = 1. We next derive an upper bound to also account for the sigmoid activation: To do this, Function ψ takes its maximum value for z = 0, with ψ(z) ≤ ψ(0) = 0.25. We notice that ψ is symmetric around 0 and monotonically decreasing on either side. Its minimum is thus given when |z| is as large as possible. However, since our classifier's output is bounded in for all points seen within T , we have |z| ≤ log(1/µ T − 1) and thus We then rely on Lemma 1 to upper bound each local Lipschitz constant in terms of the bias update: matching the claim of the theorem.

B.7 Proof of Theorem 3
We repeat the theorem statement here for easy reference: Theorem 3. Let f (t) be a depth d NN with ReLU activations being trained with SGD, a BCE loss and 1 /2-Dropout.
Suppose that f (t) is (τ, ϕ)-steady and that for every t ≥ τ the following hold: (a) Assumption 1, (b) where p min = min l<d,i≤n l ,t≥τ [avg x∈X diag(S (t) l (x))] i > 0 is the minimum frequency that any neuron is active before Dropout is applied.
For any δ > 0, with probability at least 1 − δ over the Dropout and the training set sampling, the generalization error is at most where N (X ; 2 , r) is the minimal number of 2 -balls of radius r needed to cover X .
The proof consists of two parts. First, Lemma 3 provides a bound on the global Lipschitz constant of a NN trained with Dropout as a function of the bias updates observed during a sufficiently long training. Then, Lemma 4 uses techniques from the robustness framework [18, 19] to derive a generalization bound.

B.7.1 The global Lipschitz constant
We prove the following: Lemma 3. In the setting of Theorem 2, suppose that the network is trained using 1 /2-Dropout and denote by p l = avg x∈X diag S The inequality provided above is unexpectedly tight: combining where we have assumed that c/σ n (W 1 ) = O(1) and n l = n for all l < d.
Proof. Let x be a point within a region where f (t) assumes its maximum gradient norm.
The activationS T (:, t) =s t (x (t) ) at the t-th SGD iteration is obtained by a two step procedure: 1. Sample a point x (t) from X with replacement. Let s t (x (t) ) = 1 l=d−1 s t,l (x (t) ) be its activation pattern (before dropout), where s t,l (x (t) ) := diag S (t) l (x (t) ) .
Let S be a binary matrix containing neuron activations as columns. We introduce the following definitions: • We call S a covering set if S1 ≥ 1 with the inequality taken element-wise.
• We call S a basis of s t (x) if S1 = s t (x).
Our proof hinges on two observations: Observation 1. Every basis yields a bound on the Lipschitz constant of f (t) (this can be seen from the proof of Theorem 2). Specifically, for any k training points x 1 , . . . , x k whose activations S = [s t (x 1 ), . . . , s t (x k )] is a basis of s t (x), we have accounts for the sigmoid.
Thus, if we don't use dropout and within the columns of S T there exist k that form a basis of s t (x), then this also implies that the global Lipschitz constant will be bounded by where, in an identical fashion to Theorem 2, the 1 + γ factor is added due to Assumption 1 in order to account for f (t) not having completely converged, and we have also used Lemma 1 and the uniform bound W (t) 1 2 ≤ β. Observation 2. Let us consider the effect of Dropout. Suppose that S T does not contain a basis of s t (x) = 1 l=d−1 s t,l (x), but there exist a set of columns S that is a covering set (as we will see, this is a much easier condition to satisfy). Denote byS the same matrix after the Dropout sampling. Then, with some strictly positive probability,S can become a basis. Claim 1. For any k training points x 1 , . . . , x k whose activations S = [s t (x 1 ), . . . , s t (x k )] form a covering set, there must exist Q = [q 1 , . . . , q k ] with q i = 1 l=d−1 q i,l and q i,l ≤ s t,l (x i ) (i.e., that Dropout can sample) such that Q is a basis of s t (x).
Proof. To deduce this fact, we notice that since to ensure that Q is a basis we need to show that, for every l, there exists [q 1,l · · · q k,l ] with q i,l ≤ s t,l (x i ) such that k i=1 q i,l = s t,l (x). The latter can always be satisfied when k i=1 s t,l (x) ≥ 1. When S is a covering set we have To obtain an upper bound for the Lipschitz constant of f (t) , our strategy will entail lower bounding the probability that such a basis of s t (x) will be seen within T .
Consider any k training points x 1 , . . . , x k sampled with replacement from X and let S = [s t (x 1 ), . . . , s t (x k )] be the corresponding (random) matrix of neural activations. Further, denote by p cover (S) the probability that S is a covering set.
The probability p basis (S T ) thatS T contains a basis of s t (x) is given by p basis (S T ) = 1 − P S T does not contain a basis ≥ 1 − |T | k p=1 P S T (:, (p − 1)k + 1 : pk) is not a basis For everyS T (:, (p − 1)k + 1 : pk) we have: P S T (:, (p − 1)k + 1 : pk) is a basis = P S is a basis = P S is a basis | S is a covering set P(S is a covering set) = P S is a basis | S is a covering set p cover (S).
By Observation 2, if S is a covering set then there must exist We proceed to compute the probability that the activation pattern sampled by Dropouts t (x i ) = 2 l=d (z i,l • s t,l (x i )), where z l,t are random binary vectors, is a basis of s t (x (t) ) due toS = Q: P S is a basis | S is a covering set = P S = Q = P(s t (x i ) = q i for i = 1, . . . , k) where the second to last step is a consequence of Dropout with probability 0.5 sampling for each layer uniformly at random from the set of all possible neuron activation patterns that can obtained by disabling some neurons of s t,l (x i ).
The final step of the proof entails bounding µ and p cover (S). We will think of neuron i at layer l as a (dependent) Bernoulli random variable with activation probability p l (i). The probability that neuron i in layer l is not activated within k independent trials is (1 − p l (i)) k . Taking a union bound over all neurons in all layers, results in:
Proof. For convenience, we drop the iteration index.
Following Xu and Mannor [18], we define the input margin γ i of classifier g at x i to be which is the distance (in input space) to the classification boundary. For completeness, we also repeat the definition of a robust classifier: Definition 2 (Adapted from Definition 2 [18]). Classifier g is (K, )-robust if X × Y can be partitioned into K disjoint sets, denoted as C K k=1 , such that ∀i = 1 · · · , N , (x i , y i ), (x, y) ∈ C k =⇒ |er(g(x i ), y i ) − er(g(x), y) | ≤ .
Denote by x * i a point with x * i − x i 2 = γ i with g(x * i ) = g(x i ) and notice that f (x * i ) = 0.5 (due to the definition g(x) = 1[f (x) > 0.5]). We use the argument of Sokolić et al. [19] and bound the input margin as follows: with probability at least 1 − o(1). From Example 1 in [18] we then deduce that g is (2N (2X , 2 , r t (X)), 0)-robust for Theorem 3 [18] implies that if g is (K, 0)-robust then, for any δ > 0, the following holds: with probability at least 1 − δ. We obtain the final bound by substituting K = 2N (2X , 2 , r t (X)) and taking a union bound on the events that inequalities (12) and (13)  .
By the main assumption, we can bound the rightmost term by x * − x (t ) λ f (t) 1 ≤ δ λ f (t) 1 . We thus get where, due to Assumption 1, S 1 (x (t ) ) = S (t) 1 (x (t ) ). The final bound is obtained re-arrangement and by the convergence assumption W ≤ β.