{'fraction_non_alphanumeric': 0.03449058659725165, 'fraction_numerical': 0.018433319208184515, 'mean_word_length': 4.7413328699278825, 'pattern_counts': {'":': 0, '<': 9, '<?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': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Analyzing Monotonic Linear Interpolation in Neural Network Loss Landscapes

Linear interpolation between initial neural network parameters and converged parameters after training with stochastic gradient descent (SGD) typically leads to a monotonic decrease in the training objective. This Monotonic Linear Interpolation (MLI) property, first observed by Goodfellow et al. (2014) persists in spite of the non-convex objectives and highly non-linear training dynamics of neural networks. Extending this work, we evaluate several hypotheses for this property that, to our knowledge, have not yet been explored. Using tools from differential geometry, we draw connections between the interpolated paths in function space and the monotonicity of the network - providing sufficient conditions for the MLI property under mean squared error. While the MLI property holds under various settings (e.g. network architectures and learning problems), we show in practice that networks violating the MLI property can be produced systematically, by encouraging the weights to move far from initialization. The MLI property raises important questions about the loss landscape geometry of neural networks and highlights the need to further study their global properties.


Introduction
A simple and lightweight method to probe neural network loss landscapes is to linearly interpolate between the parameters at initialization and the parameters found after training. More formally, consider a neural network with parameters θ ∈ R d trained with respect to loss function L : R d → R on a dataset D. Let the neural network be initialized with some parameters θ 0 . Then, using a gradient descent optimizer, the network converges to some final parameters θ T . A linear path is then constructed between these two parameters denoted θ α = (1−α)θ 0 +αθ T . A surprising phenomenon, The MLI property is illustrated in Figure 1. The interpolated path (θ α ) exhibits the MLI property as the training loss monotonically decreases along this line. Even more surprising, linear interpolation between an unrelated random initialization and the same converged parameters also satisfies the MLI property. Goodfellow et al. (2014) showed that the MLI property persists on various architectures, activation functions, and training objectives in neural network training. They conclude their study by stating that "the reason for the success of SGD on a wide variety of tasks is now clear: these tasks are relatively easy to optimize." In our work, we observe that networks violating the MLI property can be produced systematically and are also trained without significant difficulty. Moreover, since the publication of their research, there have been significant developments both in terms of the neural network architectures that we train today (He et al., 2016;Huang et al., 2017;Vaswani et al., 2017) and our theoretical understanding of them (Amari et al., 2020;Draxler et al., 2018;Fort and Ganguli, 2019;Frankle and Carbin, 2018;Jacot et al., 2018). Hence, with a wider lens that addresses these developments, we believe that further investigation of this phenomenon is likely to yield new insights into neural network optimization and their loss landscapes.
We study three distinct questions surrounding the MLI property. 1) How persistent is the MLI property? 2) Why does the MLI property hold? 3) What does the MLI property tell us about the loss landscape of neural networks? To address these questions, we provide an expanded empirical and theoretical study of this phenomenon. To evaluate the persistence of the MLI property, we train neural networks with varying architectures, optimizers, datasets, initialization methods, and training mechanisms (e.g. batch normalization (Ioffe and Szegedy, 2015)). We find that the MLI property persists for the majority of these settings but can be consistently broken through mechanisms that encourage the weights to move far from initialization. As far as we know, ours is the first work to observe that MLI is not a stable property of the network architecture.
One hypothesis for the MLI property is that the networks are close to linear along the interpolation path. We formalize this notion using tools from differential geometry and provide sufficient conditions for neural networks trained under the MSE loss to satisfy the MLI property. In particular, we prove that if the length under the Gauss map (which we refer to as the Gauss length) of the interpolation trajectory in function space is small, then the network is guaranteed to have the MLI property. While the converse does not hold in general, we show that this quantity is correlated with monotonicity in practice. We connect this explanation to our prior observation that large distances moved in weight space encourage non-monotonic interpolations through a surprising power-law relationship between the distance moved and the average Gauss length.
Finally, we investigate the loss landscape of the neural networks we trained by evaluating the MLI property over alternative linear paths. For example, we examine the interpolation path connecting different initializations and final parameters (as in Figure 1). Surprisingly, when the MLI property holds for an initialization → final solution pair, the MLI property also holds for unrelated initializations to the same solution.
In summary, our primary contributions include: • We prove a sufficient condition for neural networks minimizing MSE to satisfy the MLI property.
• We show that the MLI property does not always hold and that we can systematically control for/against it.
• We identify several common training mechanisms that provide this control and connect them to our novel theoretical results.

Related Work
Monotonic linear interpolation. Goodfellow et al. (2014) were the first to observe that the MLI property persists on various architectures, activation functions, and training objectives in deep learning. In addition to their empirical evaluation, they provided a qualitative analysis of the MLI property in a toy model where they argued that the MLI property holds despite negative curvature about initialization and disconnected optima. Concurrent research (Frankle, 2020) extends the original work of Goodfellow et al. (2014) with evaluations on modern architectures trained with SGD.
In this work, we provide an expanded study of the MLI property. We first investigate the persistence of the MLI property on various tasks, including settings with modern architectures and techniques that were not invented at the time of the original investigation. Further, we show that despite the original work's claim, we can train networks that violate the MLI property without significant training difficulty. Our experiments yield new insights into neural networks' loss landscapes and uncover aspects of neural network training that correlate with the MLI property.
Linear connectivity. This work is connected to empirical and theoretical advancements in understanding the loss landscape of neural networks. Much of this recent work has involved characterizing mode connectivity of neural networks. In general, linear paths between modes cross regions of high loss (Goodfellow et al., 2014). However, Draxler et al. (2018); Garipov et al. (2018) show that local minima found by stochastic gradient descent (SGD) can be connected via piecewise linear paths. Frankle et al. (2019) further show that linearly connected solutions may be found if networks share the same initialization. Fort et al. (2020) demonstrate the connection between linear connectivity and the advantage nonlinear networks enjoy over their linearized version. Kuditipudi et al. (2019) posit dropout stability as one possible explanation for mode connectivity, with Shevchenko and Mondelli (2019) extending these result to show that the loss landscape becomes increasingly connected and more dropout stable with increasing network depth. Finally, Nguyen (2019) shows that every sublevel set of an overparameterized network is connected, implying that all global minima are connected.
Note that the MLI property we study is distinct from mode connectivity, where paths are drawn between different final solutions instead of initialization → solution pairs. As far as we are aware, no prior work has explored connections between the MLI property and mode connectivity. This would make for exciting future work.
Loss landscape geometry. Recent analysis argues that there exists a small subspace at initialization in which the network converges (Fort and Ganguli, 2019;Gur-Ari et al., 2018;Papyan, 2020). Li et al. (2018) show that some of these spaces can be identified by learning in a random affine subspace of low dimension. Fort and Scherlis (2019) show that the success of these random spaces is related to the Goldilocks zone that depends on the Hessian at initialization. In a loose sense, the MLI can be considered a special case of these results, wherein a 1D space is sufficient for training to succeed. However, this is not the only mechanism in which neural network training can succeedthe solutions that violate the MLI property can have good generalization capability and are found without difficulty.
It has long been argued that flatter minima lead to better generalization (Hochreiter and Schmidhuber, 1997a) with some caveats (Dinh et al., 2017). Recent work has shown that (full-batch) gradient descent with a large learning rate is able to find flatter minima by overcoming regions of initial high curvature (Lewkowycz et al., 2020). Intuitively, gradient descent breaks out of one locally convex region of the space and into another -suggesting that a barrier in the loss landscape has been surpassed. In this paper, we show that training with larger learning rates can lead to failure of the MLI property. And in doing so, identify a high loss barrier between the initial and converged parameters. Moreover, we show that these barriers do not appear when training with smaller learning rates.
Neural tangent kernel. Recent research has shown that over-parameterized networks appreciate faster and, in some cases, more linear learning dynamics (Lee et al., 2019;Matthews et al., 2018). The Neural Tangent Kernel (NTK) (Jacot et al., 2018) describes the learning dynamics of neural networks in their function space. Existing work argues that the NTK is near-constant in the infinite width setting (Sun, 2019), however recent work challenges this view in general (Liu et al., 2020). Fort et al. (2020 recently showed that the NTK evolves quickly early on during training but the rate of change decreases dramatically during training. In Appendix D.1, we draw connections between the NTK literature and the MLI property and show that sufficiently wide fully-connected networks exhibit the MLI property with high probability. Optimization algorithms. In this work, we investigate the role that optimization algorithms have on the MLI property (and thus the explored loss landscape more generally). Amari et al. (2020) recently showed that for linear regression, natural gradient descent (Amari, 1998) travels further in parameter space, as measured by Euclidean distance, compared to gradient descent. We verify this claim empirically for larger networks trained with adaptive optimizers and observe that this co-occurs with non-monotonicity along the interpolating path θ α .

The Monotonic Linear Interpolation Property
The Monotonic Linear Interpolation (MLI) property states that when a network is randomly initialized and then trained to convergence, the linear path connecting the initialization and converged solution is monotonically decreasing in the training loss. Specifically, we say that a network has the MLI property if, for all α 1 , α 2 ∈ [0, 1] with α 1 < α 2 , Here, θ 0 denotes the parameters at initialization and θ T denotes the parameters at convergence.

∆-Monotonicity
Goodfellow et al. (2014) found that the MLI property holds for a wide range of neural network architectures and learning problems. They provided primarily qualitative evidence of this fact by plotting L(θ α ) with discretizations of [0, 1] using varying resolutions. We instead propose a simple quantitative measure of non-monotonicity.
Intuitively, the above definition states that any bump due to increasing loss over the interpolation path should have a height upper-bounded by ∆. We are interested in the smallest ∆ ≥ 0 for which this definition holds. Notably, this minimum ∆ can be approximated well numerically by stepping along the interpolation path in fixed intervals to find α 1 and α 2 giving the largest positive gap L(α 2 ) − L(α 1 ).

Weight-space perspective
It is natural to attempt to reason about the MLI property in terms of the parameters of the neural network. Intuitively, the MLI property suggests that, during optimization, the parameters move into a nearby basin of low loss without encountering any high-loss barriers in their path.
We can formalize this intuition for "Lazy Training" (Chizat et al., 2018), where the weights find a minimum near their initial value. Consider the second-order Taylor series expansion about the converged minimum θ * , If the difference between the initial and converged parameters, θ 0 − θ * , is sufficiently small, then this quadratic approximation holds well throughout the linear interpolation. In this case, the linear interpolation yields a monotonic decrease in the loss (Lemma 8, Appendix D).
Experimentally, we investigate the connection between the distance moved in weight space and the monotonicity of the resulting interpolation. We find that networks that move further in weight space during training are significantly more likely to produce non-monotonic initialization→optimum interpolations. Theoretically, we investigate the MLI property for wide neural networks where lazy training occurs provably (Lee et al., 2019). In this setting, we prove that the MLI property holds with high probability for networks of sufficient width (Theorem 9, Appendix D).

Function-space perspective
We typically train neural networks with a convex loss function applied to the network's output. While the parameter space of neural networks is extremely high-dimensional and exhibits symmetries, the function space is generally simpler and easier to reason about (Jacot et al., 2018). To that end, we let denote the logit interpolation of a neural network f evaluated on data point x with parameters θ α = θ 0 + α(θ T − θ 0 ).
One special case that guarantees the MLI property is that of linear functions, f (x; θ) = θ x (with L(θ 0 ) > L(θ T )). In this case, the logit interpolations are also linear and, under a convex loss function, f will satisfy the MLI property (Boyd et al., 2004). In practice, we work with non-linear neural networks that have non-linear logit interpolations. However, we observed that the logit interpolations are often close to linear (in a sense that we formalize soon) and that this coincides with the MLI property ( Figure 3). Therefore, we raise the question: Can we guarantee the MLI property for logit interpolations that are close to linear? 'ORJLWWUDMHFWRULHVSURMHFWHGYLD3&$FRORUHGE\FODVV However, the first one (left) interpolates monotonically while the second one (right) does not. The only difference between these two networks is that the second was trained using batch normalization while the first was not.
Measuring logit linearity. There is no standard method to measure the linearity of a curve, but there are several tools from differential geometry that are applicable. In this work, we focus on the length under the Gauss map, which we refer to as the Gauss length, a unit-free measure that is related to the curvature. In the case of curves, the Gauss length is computed by mapping the normalized tangent vectors of the curve onto the corresponding projective space (through the so-called Gauss map), and then measuring the length of the curve in this space. This is described formally in the following definition.
We refer readers to Lee (2006) or Poole et al. (2016) for a more thorough introduction to these concepts. Intuitively, the Gauss length measures how much the curve bends along its path, with a Gauss length of zero indicating a linear path. In Theorem 3, we prove that a sufficiently small Gauss length guarantees the MLI property for MSE loss.
See Appendix A for the proof. Informally, this theorem can be understood through a simple physical analogy. Imagine that you are standing on the inside surface of a uniform bowl and wish to increase your height before reaching the bottom. To do so, you must walk at an angle that is at least π /2 relative to the line connecting you to the bottom. Now, the smallest total rotation that guarantees your return to the bottom is at least π /2 radians. Importantly, Theorem 3 applies to arbitrary smooth curves including those produced in the function space of neural networks when we interpolate in the weight space (z(α; x) above). As an application of Theorem 3, in Appendix A.1, we give sufficient conditions for the MLI property to hold for two-layer linear models (whose loss landscape is non-convex with disconnected globally optimal manifolds (Kunin et al., 2019)). Furthermore, we prove that these sufficient conditions hold almost surely for models satisfying the tabula rasa assumptions of Saxe et al. (2019).
One notable departure from the theory in our experiments is that we consider the average loss over the dataset. In this case, individual logit trajectories may be non-monotonic while the network satisfies the MLI property. Nonetheless, we find the average Gauss length to be a good indicator for the monotonicity of the network as a whole.

Exploring & Explaining the MLI Property
In this section, we present our empirical investigation of the following questions: 1) How persistent is the MLI property? 2) Why does the MLI property hold? 3) What does the MLI property tell us about the loss landscape of neural networks?
For all experiments, unless specified otherwise, we discretize α in the interval [0, 1] using 50 uniform steps. Here we report statistics from the training set throughout but note that the same observations hold for held-out datasets. Many additional results can be found in Appendix C.
A note on batch normalization. We experiment with networks that use batch normalization during training. These networks require additional care when interpolating network parameters as the running statistics will not align with the activation statistics during interpolation. Therefore, we opt to reset and warm up the running statistics for each interpolated set of parameters. This warm-up consists of computing the activation statistics over an epoch of the training data, meaning that each interpolation curve requires an additional 50 epochs (the number of discretizations of α) of data consumption to get accurate loss/accuracy estimates. Note that the learned affine transformation is interpolated as usual.
Experiment settings. We summarize the main settings here with full details of our experimental procedure given in Appendix B. We trained neural networks for reconstruction, classification, and language modeling. For the reconstruction tasks, we trained fully-connected deep autoencoders on MNIST (LeCun et al., 2010). For the classification tasks, we trained networks on MNIST, Fashion-MNIST (Xiao et al., 2017), CIFAR-10, and CIFAR-100 (Krizhevsky et al., 2009). On these datasets, we explored fully-connected networks, convolutional networks, and residual architectures (He et al., 2016). In the above cases, we provide substantial exploration over varying architectures and optimization. We also provide a short study on the language modeling setting by training

How persistent is the MLI property?
We first investigate the persistence of the MLI property. Goodfellow et al. (2014) showed that the MLI property persists in classification and language modeling tasks (with LSTMs (Hochreiter and Schmidhuber, 1997b)) when trained with SGD. However, several modern advances in neural network training remain unaddressed and the limits of the MLI property have not been characterized. We provide a secondary investigation of the MLI property on reconstruction, classification, and language modelling tasks using modern architectures and methods.
In summary, we found that the MLI property is persistent over most standard neural network training knobs, including (but not limited to): layer width, depth, activation function, initialization method and regularization. However, there were three mechanisms through which we regularly observed the failure of the MLI property: the use of large learning rates, the use of adaptive optimizers such as Adam (Kingma and Ba, 2014), and the use of batch normalization (Ioffe and Szegedy, 2015). For the remainder of this section, we focus on the effect of these mechanisms but refer readers to Appendix C for a wider view of our study. We defer further analysis of explanations for the MLI property to Section 4.2.
Using large learning rates. We found throughout that large learning rates were necessary to train networks that violated the MLI property. However, large learning rates alone were not always sufficient. In Table 1, we show the proportion of networks with non-monotonic interpolations over varying learning rate (including only those models that achieved better than 0.1 training loss). Models trained with SGD using smaller learning rates always exhibited the MLI property. On the other hand, models trained with SGD with larger learning rates often violated the MLI property. For example, 71% of the configurations with a learning rate of 1.0 were found to be non-monotonic. One hypothesis for this behaviour is due to the so-called catapult phase (Jastrzebski et al., 2020;Lewkowycz et al., 2020), where large learning rates encourage the parameters to overcome a barrier in the loss landscape. Additional results on the effect of using larger learning rates can be found in Appendix C.2.

THE EFFECT OF ADAPTIVE OPTIMIZERS
Prior work has only investigated the MLI property when training with SGD. To address this gap, we trained a wide variety of networks with adaptive optimizers (RMSProp (Hinton et al., 2012), Adam (Kingma andBa, 2014), andK-FAC (Martens andGrosse, 2015)). Across all settings, we found that adaptive optimizers with large learning rates frequently led to models violating the MLI property.
MNIST autoencoders. For image reconstruction, we evaluated the MLI property for deep fullyconnected autoencoders trained on MNIST. We trained autoencoders with SGD and Adam, with varying learning rates and with a varying number of hidden layer size.  In Figure 4, we show the training loss over the interpolated path for autoencoders with final loss (MSE) lower than 30. The majority of the networks trained with SGD retained the MLI property (with few failures at large learning rates). However, when trained with the Adam optimizer, a larger proportion of converged networks exhibited non-monotonic interpolations.
MNIST & Fashion-MNIST classifiers. On the MNIST and Fashion-MNIST datasets, we explored varying dataset size, network size (depth/width of hidden layers), activation function, choice of optimizer, optimization hyperparameters, initialization methods, and the use of batch normalization. In Table 1, we compare two-layer networks trained with SGD and Adam. Models trained with SGD typically retained the MLI property but those trained with Adam frequently did not. In Appendix C.3, we show additional results for models trained with RMSProp and K-FAC (Martens and Grosse, 2015) (whose behaviour is qualitatively close to Adam) along with the interpolated loss curves.  Table 2: Evaluation of effect of batch normalization, initialization, and choice of optimizer for residual networks trained on CIFAR-10 (achieving better than 1.0 training loss). We display the proportion of networks with non-monotonic interpolation and average min ∆ such that the network is ∆-monotonic over varying training settings. Full explanation of table is given in main text.
interpolation paths for different architectures and optimizers. Across all models, the average min ∆ was 0.016 and 0.626 for SGD and Adam respectively. Overall, Adam-trained models violated the MLI property 3.2 times more often than SGD.

THE EFFECT OF BATCH NORMALIZATION
Batch normalization's invention and subsequent ubiquity postdate the initial investigation of the MLI property. Even now, the relationship between the MLI property and the use of batch normalization has not been investigated. We provide the first such study in this section. We found that the use of batch normalization greatly increased the rate at which trained networks failed to satisfy the MLI property.
MNIST & Fashion-MNIST classifers. Table 1 shows the effect of batch normalization on the MLI property for fully connected classifiers trained on MNIST & Fashion-MNIST. The networks trained with batch normalization failed to satisfy the MLI property more frequently than those without. This is more pronounced with large learning rates and with Adam.
CIFAR-10 & CIFAR-100 classifers. Next, we trained ResNet models on CIFAR-10 & CIFAR-100 classification tasks. We evaluated ResNet-{20,32,44,56} trained with Adam and SGD and with varying learning rates. We also varied the distribution over initial parameters and whether or not batch normalization was applied. The results for CIFAR-10 are displayed in Table 2 (CIFAR-100 results are similar, and are presented in Appendix C). The column headers, "BN" and "NBN" indicate batch normalization and no batch normalization respectively. The suffices "I" and "F" indicate two alternative initialization schemes, block-identity initialization (Goyal et al., 2017) and Fixup initialization (Zhang et al., 2019b). For each configuration, we report the percentage of models violating the MLI property and the average minimum ∆ such that the model is ∆-monotonic (conditioning on ∆ > 0). Batch normalization led to significantly more networks with non-monotonic interpolations. We also observed that the initialization of the residual blocks plays an important role in shaping the loss landscape.

Why does MLI hold?
10 2 10 1 10 0 10 1 10 2 log|| T 0 || 2 log|| 0 || 2 In Section 3, we discussed the parameter-and function-space perspectives of the MLI property. In our experiments, we explore these two perspectives on reconstruction and classification tasks. We computed the average Gauss length of the logit interpolations and the weight distance travelled. In both cases, these measures are predictive of MLI in practice, even for values exceeding the limits of our theory.
In Appendix C.1, we provide the full set of results for all settings we explored. Additionally, we provide an investigation of the relationship between the MLI property and generalization. In summary, we did not find a clear relationship between the success of the MLI property and the generalization ability of the neural network.

WEIGHT DISTANCE VS. MONOTONICITY
Throughout our experiments, we found that weight distance was negatively correlated with the monotonicity of the interpolated network. In Figure 5 (left), we show the relationship between the (normalized) distance travelled in weight space and the minimum ∆ such that fully-connected classifiers are ∆−monotonic.
First, we note that larger learning rates encourage greater movement in weight space -a finding that also extends to batch normalization and the use of adaptive optimizers. Second, we observed that the networks that travelled short distances during optimization consistently satisfied the MLI property. Conversely, networks with larger distances travelled in weight space were more likely to exhibit non-monotonic loss interpolations. In Appendix C.5, we show similar results for the autoencoders, CIFAR-10 & CIFAR-100 classifiers, and comparisons over batch normalization and adaptive optimizers. We also observed a negative correlation between the Gauss length of the logit interpolations and the minimum ∆ such that the loss interpolation is ∆-monotonic. In Figure 5 (right), we make this comparison for classifiers trained on MNIST & Fashion-MNIST. As our analysis predicts, small Gauss lengths lead to monotonic interpolations. And beyond the strict limits of our theoretical analysis, we find that as the Gauss length increases, the non-monotonicity also increases.
We also observed that larger learning rates lead to much larger Gauss lengths. As with the weight distance, this finding extends to batch normalization and the use of adaptive optimizers too (see Appendix C.6). In Appendix C.4, we conduct an ablation study to investigate the relationship between Gauss length and the choice of optimizer by changing the optimizer in the middle of training (SGD → Adam and Adam → SGD). Switching to Adam at any point during training leads to large Gauss length and weight distance without a significant spike in the training loss -with little variation due to the time of the optimizer switch.

GAUSS LENGTH VS WEIGHT DISTANCE
When the distance moved in weight space is small, we would expect a small Gauss length as a linearization of the network provides a good approximation. However, it is not obvious what relationship (if any) should be expected more generally. Surprisingly, we consistently observed a power-law relationship between the average Gauss length and the distance moved in weight space ( Figure 7). We observed this relationship across all of the experimental settings that we explored. Full results are presented in Appendix C.7.

What does MLI say about loss landscapes?
Thus far, we focused on the monotonicity of paths connecting the initialization and final network solution. In this section, we ask: are (non-)monotonic interpolations unique to the initialization and final solution pair?
To this end, we evaluated linear interpolations between learned network parameters and unrelated random initializations (Figure 6). For a fully-connected MNIST classifier and a ResNet-20 trained on CIFAR-10, we found that random initializations display the same interpolation behaviour as the original initialization-solution pair. This suggests that the MLI property is not tied to a particular pair of parameters but rather is a global property of the loss landscape. We also explored linear interpolations between pairs of initializations, initialization to optima pairs, and pairs of optima in Figure 8. No barriers were observed between the pairs of initializations or the initialization→optimum pairs, but barriers are present between the optima. This highlights the rich structure present in the loss landscape of these models and aligns well with the qualitative predictions of Fort and Jastrzebski (2019).
Finally, we provide visualizations of the loss landscape via 2D projections of the parameter space. While low-dimensional projections of high-dimensional spaces are often misleading, in the case of linear interpolations, the entire path lies in the projected plane. Therefore, these visualizations give us valuable insight into connectivity in the loss landscape for multiple initialization → final solution paths. In

Conclusion
Goodfellow et al. (2014) first showed that linear interpolation between initial and final network parameters monotonically decreases the training loss. In this work, we provided the first evidence that this so called, Monotonic Linear Interpolation (MLI), is not a stable property of neural network training. In doing so, we provided a deeper theoretical understanding of the MLI property and properties of the loss landscape in general. Our empirical investigation of the MLI property explored variations in datasets, architecture, optimization, and other training mechanisms. We identified several mechanisms that systematically produce trained networks that violate the MLI property, and connected these mechanisms to our theoretical explanations of the MLI property. Additional results indicate that the MLI property is not unique to the initialization→solution pair produced by training, but rather is a global property of the loss landscape connecting arbitrary initialization→solution pairs. The empirical and theoretical analysis we presented highlights the intriguing properties of neural network loss landscapes.

Appendix A. Theoretical Gauss Length Analysis
In this section, we provide an analysis of the MLI property via the Gauss Length. In particular, we prove Theorem 3 that states that if the logit interpolation of a network (from initialization to optimum) has small Gauss length then it must satisfy the MLI property. Using Theorem 3, we provide sufficient conditions for the MLI property to hold for two-layer linear models. And prove, under a class of these models satisfying some standard assumptions, that the MLI property holds almost surely.
Let's first recall the definition of the Gauss length.
Explicitly, we have, where a = ∂v ∂α and κ denotes the curvature of z. Theorem 3 is reproduced below for convenience.
To prove this result, we will require the following Lemma.
Proof We prove the contrapositive statement: If for all t 1 ∈ [0, b) and t 2 ∈ (b, 1), we have By the fundamental theorem of calculus, we have, Now, notice that as x * − z(b) 2 2 ≥ 0, we must have x * − z(0), x * − z(b) > 0. Thus, by applying the Cauchy-Schwarz inequality, It follows immediately that for any b we must have, as required.
With this result, we proceed with the proof of Theorem 3.
Proof We prove this theorem by considering the contrapositive statement: if there exists a < b ∈ (0, 1) such that f (z(a)) < f (z(b)) then the Gauss length is greater than π/2.
Given such a pair (a, b), we consider the restriction of z to [a, 1). By Lemma 5, there exists t 1 and t 2 such that ż(t 1 ),ż(t 2 ) < 0.
Therefore, the normalized tangents also satisfy v(t 1 ),v(t 2 ) < 0. Thus, the angle between the two normalized tangents (considered in the plane containing these two points and x * ) is at least π/2. Therefore, the Gauss length of the curve on (a, 1) must be at least π/2 (with the minimum Gauss length path given by the shortest path on the projective plane connectingv(t 1 ) andv(t 2 )).
Finally, we note here that the converse of Theorem 3 does not hold. For example, one may define a curve that spirals towards the minima. This curve is monotonically decreasing but has arbitrarily large Gauss length.

A.1. Two-layer linear models and the MLI property
In this section, we apply Theorem 3 to two-layer linear models. In particular, we prove sufficient conditions on any two-layer linear model to satisfy the MLI property and then prove that under certain assumptions the MLI property holds almost surely.
Our focus is on two-layer linear models, of the form f (x) = V W x, for W ∈ R k×d and V ∈ R m×k . We consider optimizing these models with respect to the mean squared error.
where X ∈ R d×n and Y ∈ R m×n . Note that this model also captures the linear autoencoder, when we set X = Y with m = d.
We consider learning in the student-teacher setting, where the labels Y are provided by a twolayer linear model with k hidden units. This allows the application of Theorem 3, as the interpolation trajectory can reach the minimum of the objective. However, outside of this realizable setting we can still apply Theorem 3 to the surrogate objective with Y replaced by the minimum achievable target Y -this objective aligns with the original at the global minimum.

Now consider a linear interpolation over initial parameters
Going forwards, we write D 1 = (V T − V 0 ) and D 2 = (W T − W 0 ). We first observe that the tangent to this curve is a linear function of α: The Gauss length of the interpolated trajectory is given by the length of the projection of the tangent vectors onto the projective space, in this case the sphere with antipodal points identified. Immediately, we note that this line projects onto the sphere as an arc, with end points given by the projection of z (0) and z (1). Following this, the Gauss length is less than π/2 exactly when the (vectorized) inner product of the two endpoint is positive (implying the angle between them is at most π/2). Furthermore, the Gauss length of the interpolation path is at most π for any initial-final parameter pair.
The two endpoints are given by: Recall the Kronecker product identity vec(AX) = (I ⊗ A)vec(X), where vec(·) indicates column-major vectorization. Then we have, Now, noting that I ⊗ A has the same eigenvalues as A (with increased multiplicity), we have z (0), z (1) > 0 for all X if and only if all eigenvalues of (D 1 W 0 + V 0 D 2 ) (D 1 W T + V T D 2 ) are positive.
Proving that the MLI property holds with probability 1. Under the tabula rasa assumptions from Saxe et al. (2019) we can prove that the MLI property holds almost surely. The assumptions that underly this setting are as follows.

Initialization is balanced (V
3. The learning rate of gradient descent is sufficiently small (relative to the largest singular value of the input-output correlation matrix ( 1 n Y X = U SR ).
Under these assumptions, Saxe et al. (2019) prove that, Under these dynamics, we have, Thus, This matrix is positive definite, and thus has positive eigenvalues. Therefore, the found solution will satisfy the MLI property.

Appendix B. Experiment Details
In this section, we provide full details of our experimental set-up. For all experiments, we discretize α in the interval [0, 1] using 50 uniform steps to examine the MLI property. When training networks with SGD, we used a momentum coefficient of 0.9 and when training networks with the Adam optimizer, we used β 1 = 0.9, β 2 = 0.999 and = 1e − 08. Unless specified otherwise, we used a batch size of 128.

B.2. Image classification experiments
In the image classification experiments, we explored a large number of different architectures. We summarize all setting we explored below. Convolution Neural Network. We trained Simple CNN, VGG16, VGG19, and ResNet-{18, 20, 32, 44, 50, 56} with and without batch normalization, on CIFAR-10 and CIFAR-100. The Simple CNN had two convolutional layers with a 5 × 5 kernel followed by a single fully connected layer. We trained the networks with both SGD and the Adam optimizer. For all models, we used an initial learning rate in the set {0.3, 0.1, 0.03, 0.01, 0.003, 0.001, 0.0003, 0.0001}. For most models we fixed the learning rate throughout training but for the ResNets we used a waterfall learning rate decay (at 60, 90, and 120 epochs).
For the ResNet experiments without batch normalization, when using the Fixup (Zhang et al., 2019b) or block identity initialization (Goyal et al., 2017) we replaced the batch normalization layers with scale and bias parameters taking the role of the standard batch norm affine transformation. The block identity initialization essentially consists of setting the final scale/bias parameters in each residual block to zero, so that the block computes only the skip connection (with possible down-sampling).

B.3. Language modeling experiments
We trained a RoBERTa transfomer-based model (Liu et al., 2019) on the language modelling task on an Esperanto dataset with the Huggingface framework (Wolf et al., 2020), as described in their tutorial 1 and building on a notebook they published 2 . We trained the model from two distinct random initializations for 1 epoch (taking approximately 2 hours on a free Google Colab GPU).

B.4. Experiment specifics
MNIST & Fashion-MNIST batch norm comparison. We describe the experimental set-up used to produce Figure 3 and Figure 24. We trained fully-connected networks whose architecture consisted of 784 → 1024 → 1024 → 10 units in each layer. We explored ReLU, sigmoid, and tanh activation functions and trained the networks with and without batch norm layers, that when used were inserted after each linear layer (except the last layer). The networks were trained for 200 epochs using fixed learning rates in the set {3.0, 1.0, 0.3, 0.1, 0.03, 0.01, 0.003, 0.001} and with either the Adam optimizer or SGD with momentum.
Problem difficulty experiments. For the experiments evaluating problem difficulty (parameter complexity and label corruption), described in Appendix C.11, we trained fully-connected networks on the FashionMNIST dataset. In all cases, the networks used ReLU activations and were trained with batch sizes of at most 512 (depending on dataset size), and for 200 epochs. Learning rates were fixed throughout training. When varying the dataset size, we trained models on random subsets of FashionMNIST with sizes in the set {10, 30, 100, 300, 1000, 3000, 10000, 30000, 60000}. We evaluated networks trained with learning rates in the set {0.03, 0.1, 0.3, 1.0}. For the experiments with varying levels of label corruption, we trained fully-connected networks with 2 hidden-layers each of width 1024 and without batch normalization.

Appendix C. Extended empirical evaluation
In our exploration of the MLI property, we performed many additional experiments. Generally, we found that turning common knobs of neural network training did not have a significant impact on networks satisfying the MLI property. For example, varying activation functions, loss functions, batch size, regularization, and different forms of initialization had no significant effect on the MLI property. In this section, we present a few of the more interesting additional experiments that we performed.

C.1. Relationship between the MLI property and generalization
We are interested in whether the success/failure of the MLI property impacts the generalization ability of a neural network. To better understand this, we examined the test accuracy of the models we trained and studied the correlation with the MLI property on MNIST and CIFAR-10 datasets. Figure 10 shows the relationship between the test accuracy and min ∆. Note that we considered fully connected networks for MNIST dataset and VGG architectures for CIFAR-10. For the MNIST experiments, configurations that violated the MLI property had an average test accuracy of 96.94(±0.015) and those that satisfied the MLI property had the averaged test accuracy of 97.14(±0.018). Similarly, for CIFAR-10 experiments, configurations that violated the MLI property had an average test accuracy of 75.83(±0.084) and those that satisfied the MLI property had an average test accuracy of 76.99(±0.082). Overall, we did not identify a clear pattern between the MLI property and the generalization property of the neural network. At the very least, we ascertain that models violating the MLI property can achieve competitive test accuracy.

C.2. Impact of large learning rate
In Table 3, we show the proportion of ResNets trained on CIFAR-10 and CIFAR-100 that violated the MLI property. The experimental set up matches that used to produce Tables 2 and Table 4. There is a general trend towards higher learning rates encouraging non-monotonicity though the correlation is weaker than for the MNIST/Fashion-MNIST classifiers.  (9) 1.00 (6) 1.00 (1) No BN 0.00 (13) 0.00 (17) 0.00 (17) 0.62 (8) 0.00 (5) 0.00 (11) 0.00 (6) Table 3: Proportion of trained CIFAR-10 and CIFAR-100 classifiers (achieving better than 1.0/2.0 training loss respectively) that had non-monotonic interpolations from initialization to final solution. The total number of runs in each bin is displayed in parentheses next to the proportion. A dashed line indicates that no networks achieved the threshold loss. We provide additional evaluations of large learning rates in Figure 25, where we evaluate the effect of changing network depth and width over varying learning rates. Full details are given in Appendix C.10.

C.3. Impact of optimization algorithm
In Figure 11, we show the training loss over the line connecting the initial and final parameters. We found that adaptive optimizers such as RMSProp and Adam consistently find final solutions that violate the MLI property. To better understand this feature, we compare the distance travelled for all optimization methods. In Figure 12 (left), we show the distance travelled in weight space when trained with SGD and Adam for MNIST & Fashion-MNIST classification tasks. When trained with Adam, the optimizer moved further away from the initialization -confirming the results of Amari et al. (2020). On the other hand, models trained with SGD often traveled less. Moreover, non-monotonic configurations occurred more frequently for networks that travelled far from initialization, suggesting that the non-monotonicity of adaptive optimizers may be due to them encouraging parameters to travel far from initialization.
We also investigated the relationship between non-monotonicity and Gauss length over varying optimizers. In Figure 12 (right), we show the Gauss length for networks trained using SGD and the Adam optimizer. When trained with Adam, on average the interpolation paths have a larger Gauss length and lead to more failures of the MLI property.   Table 4 contains our evaluation of the MLI property for ResNets trained with different architectures, optimizers, and initialization schemes (as in Table 2 for CIFAR-10 in the main paper). The general trends observed align with those observed on CIFAR-10 in the main paper.  Figure 12: For each MNIST & Fashion-MNIST classifier, we compute the minimum ∆ such that the interpolated loss is ∆-monotonic. We plot models trained with SGD and Adam in the top and bottom rows respectively. On the left, we compare the distance moved in the weight space. On the right, we compare the Gauss length of the interpolated network outputs. Blue points represent networks where the MLI property holds and orange points are networks where the MLI property fails.

C.4. Optimizer Ablations
To get a better understanding of the influence of different optimization algorithms and the effects of moving in weight and function space, we conduct detailed experiments where we switch the optimizer during training. We use an architecture with 2 hidden layers of 1024 units on MNIST. The architecture has tanh activations and no batch normalization. We report the mean and standard error across five random seeds.
In the (SGD → Adam) experiments, we train the first t = {2, 10, 50} epochs with SGD, using learning rates in the set {0.001, 0.003, 0.01, 0.03, 0.1} and finish the training with Adam (with LR   Table 6: Average Gauss length (top) and distance traveled (bottom) for given Adam learning rate and switching to SGD with learning rate 0.03 during training.
0.001) for 200 − t epochs. While using just SGD leads to a monotonic interpolation, switching to Adam made all runs not monotonic. These results are reported in Table 5. Similarly, in Table 5, we report results for (Adam → SGD). We switch to SGD with a learning rate of 0.03.
As in Amari et al. (2020), we again find that Adam leads to much greater distance moved in weight space. Perhaps more surprisingly, the distance moved in weight space and the average Gauss length are largely consistent across different choices of the learning rate for SGD and the epoch at which we switch to Adam. In Table 6, we see that switching from Adam to SGD reduces both the average Gauss length and the distance travelled.
To investigate why Adam is responsible for breaking monotonicity further, we follow the "grafting" experiment described in Agarwal et al. (2020), where two optimizers are combined by using the step magnitude from the first and step direction from the second. Results where we use the SGD step magnitude (which varies with LR) and Adam direction are shown in 7. All the runs are monotonic, so the direction chosen by Adam is not the primary influence on the optimization lr \ Optimizer SGD Adam 0.001 9.198 ± 0.016 8.096 ± 0.012 0.003 10.932 ± 0.015 9.369 ± 0.015 0.01 12.978 ± 0.013 10.893 ± 0.021 0.03 16.619 ± 0.037 14.177 ± 0.041 Table 7: Average distance traveled where we use the SGD step magnitude and step direction given by SGD or Adam, respectively trajectory. In contrast, when we use the SGD step direction and the Adam magnitude we observe all runs to be non-monotonic and find the average distance traveled to be 381.65, suggesting that the magnitude of the updates is responsible for breaking monotonicity.

C.5. Additional weight distance experiments
In this section, we investigate the relationship between normalized weight distance and nonmonotonicity on image reconstruction (MNIST) and image classification (CIFAR-10 & CIFAR-100) tasks. In Figure 13, we show the correlation between the distance travelled in parameter space and the smallest ∆ such that the loss interpolation is ∆-monotonic (Definition 1) for image reconstruction task. As expected, a small distance moved (or Gauss length, respectively) leads to monotonic interpolation. And beyond the strict limits of our analysis, we observed that larger weight distances are correlated with non-monotonicity.
In Figure 14, we display the distance moved in weight space against the minimum ∆ such that ResNets trained on CIFAR-10 and CIFAR-100 have ∆-monotonic interpolations from initial to final parameters. In general, larger bumps occur at larger distances moved, as in our other experiments.
In this section, we investigate the relationship between Gauss length and non-monotonicity on image reconstruction and image classification (CIFAR-10 & CIFAR-100) tasks.
In Figure 13, we show the correlation between the Gauss length and the smallest ∆ such that the loss interpolation is ∆-monotonic for the image reconstruction task. Similar to the weight distances, a small Gauss length leads to monotonic interpolation. We also observe that larger Gauss length are correlated with the failure of MLI property.
In Figure 14, we display the distance moved in weight space against the minimum ∆ such that ResNets trained on CIFAR-10 and CIFAR-100 have ∆-monotonic interpolations from initial to final parameters. In general, larger bumps occur at larger distances moved, as in our other experiments.

C.7. Additional Gauss length vs weight distance
In this section, we investigate the relationship between Guass length and weight distance travelled for image reconstruction and image classification (CIFAR-10 & CIFAR-100) tasks.
In Figure 15, we plot the Gauss length of the interpolation path against the distance moved in weight space for autoencoders trained on MNIST. In this case, as in Figure 7, we observe a clear power-law relationship between the two.
In Figure 17, we plot the Gauss length of the interpolation path against the distance moved in weight space for ResNets trained on CIFAR-10 and CIFAR-100, over varying initialization schemes, optimizers, and the use of batchnorm (as in Tables 2 and 4 law relationship but nonetheless a clear positive correlation remains between the Gauss length and the distance moved in weight space.

C.8. Impact of batch normalization
In Figure 18, we compare the distance travelled between models trained with batch normalization and without batch normalization for classifiers trained on the MNIST & Fashion-MNIST datasets. We plot the minimum ∆ such that the interpolated loss is ∆-monotonic against the distance moved in weight space. We observe that models trained with batch normalization had a higher variance of distance travelled in weight space compared to models trained without batch normalization. Hence, when batch normalization is used, there are more configurations that travelled further in weight space. Consistent with our prior analysis, configurations that travelled far in parameter space tend to more break the MLI property. This hints that such behaviour of batch normalization can cause more frequent violation of the MLI property.

C.9. Additional loss landscape experiments
Loss landscape for network failing MLI. In Section 4.3, we showed loss landscape visualizations for networks that satisfied the MLI property. In Figure 19, we show the 2D projection of the loss landscape for a fully-connected FashionMNIST classifier that does not satisfy the MLI property. In this 2D slice, we observe a wide barrier in the loss landscape followed by a region of extremely flat curvature.
MLI over permutation symmetries. In addition to random initializations, we explored interpolations over the permutation symmetry group of initialization-solution pairs for fully-connected networks on MNIST. In Figure 21, we utilized the fact that adjacent linear layers can be permuted without modifying the output function to randomly permute the initialization and final solution. This leads to different paths through weight space but with the end-points of the interpolation fixed at the original values. We observed that these permutations preserve the MLI property.
Interpolations with different initialization distributions. In Figure 6, we showed that the monotonic (or non-monotonic) interpolations persist across different random initializations for a given final solution. However, it is possible that the monotonicity of the interpolations can change if we modify the initialization scheme. We took the network from the bottom right plot of Figure 6 and chose our initializations according to the scheme described in Goyal et al. (2017) -where the final batch norm layer in each residual block is initialized to be zero so that the network function is close  Figure 19: Loss landscape projection of a FashionMNIST classifier that does not satisfy the MLI property. We observe a barrier in the loss followed by a region of extremely flat curvature.  to the identity function. The result is shown in Figure 20, in this case, the random initializations are linearly connected to the solution while random samples from the original initialization distribution are not.
Additional landscape visualizations. In Figure 22, we show additional 2D projections of the loss landscapes for ResNet20v1 networks on CIFAR-10. This confirms results seen elsewhere: linear interpolation between unrelated initial points and optima yield monotonic decreases in training loss and monotonic increases in accuracy. In Figure 23, we show the same loss landscape projections as displayed in Figure 9. Additionally, here we include the loss over the interpolated paths.

C.10. Additional MNIST results
In Figure 24, we show the full set of network interpolations used to produce Table 1. Overall, we observed a significant effect from introducing batch normalization across all other settings considered, but particularly when the learning rate is large.
Varying depth and hidden size. We explored the effect of varying depth and hidden size on the MLI property. Overall, we did not observe any substantial correlation between these factors and the MLI property (especially, when taking into account implicit effects on the critical learning rate).
In Figure 25, we display heatmaps of min ∆ as a function of the learning rate, hidden size and depth of fully-connected neural networks trained on MNIST and Fashion-MNIST. Overall, we do not observe any significant effect from changing either the hidden size or the network depth -the learning rate accounts for the dominant changes in the monotonicity of the interpolation. We trained each network with ReLU activations for 200 epochs with batch sizes of 512, using both Adam and SGD and with/without batch normalization. Only those models that achieved a training loss of 0.1 are displayed (cyan patches indicate that no model met these criteria for the corresponding configuration).  Figure 26: Linear interpolations (green) for neural networks trained on varying dataset sizes (30, 300, 3000 from left-to-right), with loss during training overlaid (blue). Even when the training dynamics are unstable and highly non-linear, the interpolation produces a smooth monotonic curve.

C.11. Problem Difficulty
We revisited the conclusion of Goodfellow et al. (2014) that the MLI property holds due to the relative ease of optimization. We explored this question on three fronts. First, we used a fixed network size and varied the number of data points in the dataset. Second, we used a fixed dataset size and varied the number of hidden units in a network of fixed depth ( Figure 25). And third, we varied random corruption of labels in the training dataset.
Dataset size. We trained fully-connected networks on the Fashion-MNIST dataset using SGD with a learning rate of 0.1. The networks had a single hidden layer with 1000 hidden units, and we varied the dataset size from 10 up to the full size 60000. Figure 26 shows the linear interpolation trained on varying dataset sizes. We observed that even when the training dynamics are unstable and highly non-linear, the interpolation is still monotonically decreasing.
MLI vs. label corruption. When the dataset is sufficiently simple, the learning problem is easy and SGD consistently finds solutions with the MLI property. To explore this hypothesis, we trained neural networks with label corruption. We trained a neural network with two hidden layers each with 1024 units (more details can be found at Appendix B.4). The labels were corrupted by uniformly sampling labels for some proportion of the data points. We varied the label corruption from 0% to 100% in 2.5% intervals. We varied the proportion of label corruption from 0% up to 100%. At all levels of label corruption, the MLI property persisted. One possible explanation for this result follows from the fact that logit gradients cluster together by logit index -even for inputs belonging to different true classes (Fort and Ganguli, 2019). This provides an explanation for gradient descent exploring a low dimensional subspace relative to the parameter space. Therefore, corrupting the label will not disrupt this clustering at initialization and, as empirically verified, is unlikely to prevent the MLI property from holding.

C.12. Learning Dynamics
Lewkowycz et al. (2020) observed a region of critical large learning rates wherein gradient descent breaks out of high-curvature regions at initialization and explores regions of high-loss before settling in a low-loss region with lower curvature. We might expect that such trajectories lead to initializationsolution pairs that do not satisfy the MLI property. On one hand, in Figure 26, we observed several runs where SGD is seen to overcome large barriers but the MLI property holds. However, in Figure 19  we observe a projection of the loss landscape which aligns with the qualitative description of the catapult phase: a barrier in the loss, with SGD settling in a region of much lower curvature. Overall, we consider our findings inconclusive on this front.

C.13. MLI on held-out data
In this work, we are primarily concerned with better understanding of the interaction between the MLI property and the training loss. Therefore, all of the results that we have reported are based on statistics computed over the training set. However, the same observations also hold generally when evaluating using held-out data (up to overfitting effects). This was confirmed by Goodfellow et al. (2014), and in this section, we provide a short qualitative study verifying this for the settings that we have studied.
Image reconstruction. In Figure 27 (left two plots), we compare the loss interpolations on the training set and test set for two trained autoencoders. In the first plot, the network satisfies the MLI property but in the second it does not. In both cases, the test loss interpolation closely follows the training loss.
MNIST Classifiers. The third and fourth plots in Figure 27 show the train and test loss interpolations for fully-connected MNIST classifiers. In this case, the test loss increases towards the end of the interpolation path while the training loss stays small. This happens because the network becomes over-confident in its predictions and pays a larger cost for misclassification on the test-set (even though the accuracy remains the same). This observed behaviour is one reason why we favour exploration of the training loss throughout our work. Despite this, we do still observe the test loss following the general shape of the training loss for most of the interpolation path.
CIFAR-10 & CIFAR-100 Classifiers. In Figure 28, we compare the loss interpolations on the training set and test set for ResNets trained on CIFAR-10 and CIFAR-100. The first two plots show CIFAR-10 classifiers with the third and fourth plot showing CIFAR-100 classifiers. The first and third plots show networks that satisfy the MLI property on the training loss, while the second and fourth show networks that fail to satisfy the MLI property on the training loss. As with the MNIST Background. We utilize two results from Lee et al. (2019). The first of which bounds the Jacobian matrix in Frobenius norm about initialization.
In words, Lemma 6 guarantees that the Frobenius norm of the Jacobian is close to initialization as width grows and that it does not vary too quickly. The second of these two constraints also guarantees that the norm of the network Hessian is bounded (by considering θ and θ arbitrarily close).
The second result that we borrow provides a high-probability guarantee that infinitely wide neural networks find solutions near to their initialization (the lazy training regime Chizat et al. (2018)).
MLI for infinite width networks. From the above, we can prove that in the limit of infinite width, gradient descent with a suitably small learning rate finds a solution that is linearly connected to the initialization.
Intuitively, this result holds as in a region near a minimum the objective is locally convex. As the width of the network grows, the minimum found by gradient descent becomes arbitrarily close to initialization and thus the linear interpolation is acting over a convex function.
For completeness, we first provide a simple proof that linear interpolations satisfy the MLI property in convex loss landscapes. The result itself follows from standard techniques presented in, for example, Boyd et al. (2004).
Proof We have that g(α) is also a convex, differentiable function. Therefore, using the first-order convexity condition on g, g (α) ≤ g(1) − g(α) 1 − α ≤ 0 We now proceed with the main result of this section.
Proof For brevity, we write ∆θ = θ T − θ 0 , with θ α = θ 0 + α∆θ. Our approach is to linearize the loss in function-space and show that all remaining terms are quadratic in ∆θ and so are dominated by the linear terms for a sufficiently wide network.
The first term in the sum is negative as L is convex in f (and α 2 > α 1 ). It remains to show that the other terms behave asymptotically like ∆θ 2 . First, notice that we can decompose the Hessian of the loss as follows, Furthermore, by Lemma 7, there exists an M ∈ N such that for all m > M we have ∆θ ≤ O(m −1/2 ) with probability at least 1 − δ. Under this event, we can apply Lemma 6 to guarantee that the average Jacobian and Hessian norms are bounded about initialization: Therefore, there exists an M ≥ M , such that for all m > M the negative first-order term dominates the second order terms. Under the 1−δ probability event, this guarantees that the loss is monotonically decreasing along the linear interpolation.

D.2. A Noisy Quadratic Model
The noisy quadratic model (NQM) (Schaul et al., 2013;Wu et al., 2018;Zhang et al., 2019a) serves as a useful guide for understanding the effects of stochasticity in asymptotic neural network training. Indeed, Zhang et al. (2019a) demonstrate that the NQM makes predictions that are aligned with experimental results on deep neural networks. Using this model, we can provide an explanation for one possible cause of non-monotonicity: an inflection point of the interpolation curve with positive second derivative close to α = 1. Intuitively, we can imagine a bowl-shaped loss surface where the final parameters lies on the opposite side of the optima relative to the initialization. This non-monotonicity is likely to occur when training with smaller batch sizes and/or using larger (fixed) learning rates.
Let our loss function be as follows: where θ ∈ R d and K ∈ R d×d . The optimization algorithm receives stochastic gradients Kθ + c, where c ∼ N (0, K). Consider the iterates {θ i } i=0 produced by gradient descent. With a sufficiently small learning rate, the expected value of the iterate converges i.e. lim t→∞ E[L(θ t )] = 0.
Hence, the loss is monotonically decreasing if, for all α ∈ [0, 1], (θ 2 − θ 1 ) K(θ 1 + α(θ 2 − θ 1 )) < 0 In the one dimension case, this equation is saying that interpolation is non-monotonic when θ 1 and θ 2 are on the opposite side of the minima. More generally, note that because ∂L ∂α is linear in α, the interpolation is monotonically decreasing if and only if both of these conditions at the endpoints are satisfied: (θ 2 − θ 1 ) Kθ 1 < 0 (14) (θ 2 − θ 1 ) Kθ 2 < 0 These two conditions correspond to a negative derivative with respect to α at θ 1 and θ 2 . Since we choose a learning rate so that the loss decreases in expectation (and hence the derivative is anti-aligned with c 2 − c 1 at initialization), it suffices to check just the second condition.
We simulate learning in this model to measure the effect of stochasticity under varying learning rates on the MLI property. As in Zhang et al. (2019a), we use θ 1 := θ ∼ N (0, I) and K = diag{1, 1 2 , 1 3 , . . . , 1 d }. As t → ∞, the point θ 2 := θ T ∼ N (0, ηK), where η is the final learning rate and the random variable comes from the noise in the gradient. Through empirical simulations, we verify that this is approximately a symmetric distribution about 0, so the probability we have monotonic interpolation is roughly 1 2 . This is empirically verified in Figure 29. A smaller learning rate means that the distribution of (θ 2 − θ 1 ) Kθ 2 has less variance. Because we discretize α when we check for MLI, we have P ((θ 2 − θ 1 ) Kc 2 ) < ) increases as the learning rate decreases for some small .