The Implicit Bias of Minima Stability: A View from Function Space
Year: 2021

Abstract:
The loss terrains of over-parameterized neural networks have multiple global minima. However, it is well known that stochastic gradient descent (SGD) can stably converge only to minima that are sufficiently flat w.r.t. SGD’s step size. In this paper we study the effect that this mechanism has on the function implemented by the trained model. First, we extend the existing knowledge on minima stability to non-differentiable minima, which are common in ReLU nets. We then use our stability results to study a single hidden layer univariate ReLU network. In this setting, we show that SGD is biased towards functions whose second derivative (w.r.t the input) has a bounded weighted L1 norm, and this is regardless of the initialization. In particular, we show that the function implemented by the network upon convergence gets smoother as the learning rate increases. The weight multiplying the second derivative is larger around the center of the support of the training distribution, and smaller towards its boundaries, suggesting that a trained model tends to be smoother at the center of the training distribution.

heading: 1 Introduction
text: Understanding the overwhelming success of deep learning requires unveiling the mechanisms that allow over-parametrized models to generalize well, a phenomenon that is in sharp contrast to classical wisdom. It has been suggested that one of the sources for this behavior is the implicit bias that training algorithms have towards certain solutions. Implicit biases of generic optimization methods had been known for decades [49] and have also been discussed in the context of neural network training already in [30]. However, their dramatic effect on modern deep learning has only recently started to unveil [36, 57]. For example, in binary classification tasks with linearly separable data, it has been shown that among all global minima, gradient descent (GD) converges to the maximum margin separator [48]. Similarly, in over-parametrized linear regression, GD converges to the minimum norm solution when initialized at zero [57].
Implicit biases were recently studied in many different settings, including in linear convolutional networks [16], matrix and tensor factorization [14, 41], with weight normalization [54] and with various loss functions [15]. Some works have drawn analogies between these biases and traditional regularization schemes. For example, it has been conjectured that the implicit bias of GD can be expressed as some regularization term that is added to the training loss [14]. This turned out to be true for several settings, such as over-parametrized linear regression with the quadratic loss [57], matrix factorization under certain assumptions [26], and linear classification on separable data using losses with an exponential tail [48]. But recent work has pointed out that this is not true in general,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
by illustrating that the implicit bias of GD is often not equivalent to a loss term of the form of any function of the network’s weights [40, 44].
The current paradigm for analyzing implicit bias seeks to ensure convergence to global minima as a first step. This requires making sure that GD is well behaved, i.e. does not escape the minimum. A common way to guarantee this is by considering a sufficiently small learning rate, or even the limit of infinitesimal step size, known as gradient flow (GF). In this case, the minima to which GD converges tend to be close to the initialization [39]. Therefore, existing results are initialization-dependent and relevant only to small step-sizes. Unfortunately, these type of analyses fail to capture phenomena that are known to be directly related to the step size in practical training, e.g. [8, 17, 19, 24, 29, 45, 46, 53]. For instance, Fig. 1 demonstrates that when initializing GD near a minimum, different step sizes lead to convergence to completely different solutions. This behavior is not reflected by current studies.
Following this understanding, here we seek an initialization-independent analysis that explicitly takes into account the learning rate and reveals its effect on the learned model. To this end, instead of analyzing the trajectory of the parameters from initialization to convergence, we study the properties of the minima to which stochastic GD (SGD) can converge. Specifically, it is well known that SGD cannot stably converge to minima that are too sharp relative to its step size [8, 19, 45, 53]. This property has been studied in [53] for twice differential minima, but its implication on the learned function has not been discussed. Here we extend this analysis to non-differentiable minima, which are common in ReLU networks, and use this property to characterize the end-to-end functions that a neural network can implement upon convergence.
As in [23, 42, 51], we study an over-parameterized single-hidden-layer univariate ReLU network, and focus on the quadratic loss. Under this setting, the network can implement infinitely many piecewise linear functions f that globally minimize the loss (i.e. interpolate the data). Our key result (see Theorem 1) is that when using a step size of η, SGD can only converge to solutions satisfying∫
R |f ′′(x)|g(x)dx ≤ 1 η − 1 2 , (1)
with some particular weight function g (see Fig. 1). In other words, the larger the step size, the smoother the solutions that a network learns. The weight g is larger around the center of the support of the training distribution, and smaller towards its boundaries. This implies that the solutions found by SGD tend to be smoother around the center of the distribution.

heading: 2 Minima stability
text: SGD is routinely used to minimize objective functions that have multiple global minima. However, it is well known that not all minima are accessible to SGD [53]. Understanding to which minima SGD can converge, requires analyzing its dynamics in the vicinity of minima. If once SGD arrives near a minimum, it converges to it, then we say that this is a stable minimum. If SGD repels from the minimum, then we say that this is an unstable minimum. Here we briefly survey and extend the existing knowledge about stable minima for SGD.
Let `j : Rd 7→ R be differentiable almost everywhere for all j ∈ [n]. Consider a loss function L and its stochastic counterpart L̂, given by
L(θ) = 1 n n∑ j=1 `j(θ) and L̂t(θ) = 1 B ∑ j∈Bt `j(θ), (2)
where Bt is a batch of size B sampled at iteration t. We assume that the batches {Bt} are drawn uniformly from the training set, independently across iterations. SGD’s update rule is given by
θt+1 = θt − η∇L̂t(θt), (3) where η is the step size. In the following we define the notion of stability for minima, and provide conditions for a minimum to be stable.

heading: 2.1 Twice differentiable minima
text: We start by examining a twice differentiable minimum θ∗. Using a Taylor expansion about θ∗, we have
L̂t(θ) ≈ L̂t(θ∗) + (θ − θ∗)T∇L̂t(θ∗) + 1 2 (θ − θ∗)T∇2L̂t(θ∗)(θ − θ∗), (4)
where∇L̂t(θ∗) and∇2L̂t(θ∗) are the gradient and Hessian of L̂t at θ∗. Therefore, in the vicinity of the minimum, (3) is approximately given by
θt+1 ≈ θt − η ( ∇L̂t(θ∗) +∇2L̂t(θ∗)(θt − θ∗) ) . (5)
This approximation gets more accurate as θt gets closer to θ∗. We can thus use this linearized dynamics to learn about the stability of minima [53]. Definition 1 (Linear stability). Let θ∗ be a twice differentiable minimum ofL. Consider the linearized stochastic dynamical system
θt+1 = θt − η ( ∇L̂t(θ∗) +∇2L̂t(θ∗)(θt − θ∗) ) . (6)
Then θ∗ is said to be ε linearly stable if for any θ0 in the ε-ball Bε(θ∗), we have lim sup t→∞ E[‖θt − θ∗‖] ≤ ε.
In other words, θ∗ is ε linearly stable if once we have arrived at a distance of ε from it (at t = 0 without loss of generality), we end up at a distance no greater than ε around it in expectation. Some of our results do not depend on ε, in which case we simply refer to “linear stability” (without the ε).
Wu et al. [53] provided a sufficient condition for linear stability under the assumption that ∇L̂t(θ∗) = 0 for all t ≥ 1. For our analysis, we need a necessary condition. This is simple to obtain from the well known stability criterion for GD and the fact that GD’s trajectory corresponds to the expectation of SGD’s steps. Specifically, we have the following condition (which only requires that E[∇L̂t(θ∗)] = 0; see formal proof in Appendix II). Lemma 1 (Necessary condition for stability). Consider SGD with step size η, where batches are drawn uniformly from the training set, independently across iterations. If θ∗ is an ε linearly stable minimum of L, then
λmax ( ∇2L(θ∗) ) ≤ 2 η . (7)
Note that this condition is also sufficient when considering GD (i.e. full batch SGD).

heading: 2.2 Non-differentiable minima
text: We now generalize the definition of linear stability to non-differentiable minima. In deep learning, non-differentiability is typically caused by a mode switch in the system, e.g. switching of ReLU activations or max-pooling layers. However, if we fix the mode (e.g. constant activation or pooling selection patterns per sample), then the loss becomes infinitely differentiable everywhere. In these cases, we can therefore model SGD’s dynamics as a switching dynamical system.
Let {Sm} be a partition of Rd that represents the regions of the different modes, i.e. ∀i 6= j Si ∩ Sj = ∅, and ⋃ m Sm = Rd. (8)
Additionally, let ψm : Rd 7→ R be an analytic function representing the loss for the mth mode. We assume the overall loss (and its stochastic version) can be written as1
L(θ) = ψm(θ), L̂t(θ) = ψ̂(t)m (θ) if θ ∈ Sm, (9)
where ψ̂(t)m is the stochastic counterpart of ψm at time t. Therefore, near a minimum θ ∗ we can approximate the loss as L̂t(θ) ≈ L̂t(θ∗) + (θ − θ∗)T ĝ(t)θ + 1
2 (θ − θ∗)T Ĥ
(t) θ (θ − θ ∗), (10)
where (defining Int(A) as the interior of A)
∀θ ∈ Int(Sm) ĝ(t)θ , ∇ψ̂ (t) m (θ ∗), and Ĥ (t) θ , ∇2ψ̂(t)m (θ ∗). (11)
The update rule of SGD (3) can thus be approximated as θt+1 ≈ θt − η ( ĝ (t) θt + Ĥ (t) θt (θt − θ ∗) ) . (12) Note that this approximation is relevant only when θt is close to θ∗. Let2 I = {m : θ∗ ∈ S̄m} be the indices of the sets around θ∗, and let A = ⋃ m∈I Sm be their union. We assume there is a finite number of modes inA (this is always the case for ReLU networks with a finite number of parameters). Consider an ε-neighborhood around the minimum such that Bε(θ∗) ⊆ A. We define linear stability in this neighborhood as follows. Definition 2 (Generalized linear stability). Let θ∗ be a minimum point of L. Consider the switching stochastic dynamical system
θt+1 = θt − η ( ĝ (t) θt + Ĥ (t) θt (θt − θ ∗) )
(13)
and assume that θt ∈ A with probability one for all t > 0.
• θ∗ is said to be ε linearly stable if lim sup t→∞ E[‖θt − θ∗‖] ≤ ε for any θ0 ∈ Bε(θ∗). • θ∗ is said to be ε linearly strongly stable if sup t E[‖θt − θ∗‖] ≤ ε for any θ0 ∈ Bε(θ∗).
In other words, we consider a situation where at some point in time (which we call t = 0 without loss of generality), the parameter vector is ε-close to θ∗. If this guarantees that from that moment on, θt is always ε-close to θ∗ in expectation, then θ∗ is called strongly stable. If this only guarantees that from some later point in time, θt is always ε-close to θ∗ in expectation, then θ∗ is called stable.
Our results are stated in terms ofHm = ∇2ψm(θ ∗) and ĝ(t)m = ∇ψ̂ (t) m (θ ∗). The next lemma gives a necessary condition for linear stability (see proof in Appendix III). Lemma 2 (Necessary condition for stability). Assume that SGD with step size η draws batches uniformly from the training set, independently across iterations. Let θ∗ be a minimum point of L, for which there is a finite number of modes in I. Suppose there exist q ∈ Sd−1 and {λm} such that ‖Hmq − λmq‖ ≤ δ for all m ∈ I and denote
λlower = min m∈I {λm}, (14)
and3 γ = maxm∈I E[|qT ĝ(t)m |]. If λlower > 2
η + δ +
γ ε , (15)
then θ∗ is not an ε strongly stable minimum. Furthermore, if δ = 0 (i.e. q is a common eigenvector) then θ∗ is not an ε stable minimum.
1This is true since the modes corresponding to a batch are a subset of those of the full data. 2S̄m denotes the closure of Sm. 3Note that {ĝ(t)m }∞t=1 are i.i.d. and therefore E[|qT ĝ (t) m |] is time invariant.
Note that the lemma considers the case where the Hessians of all subsystems have an approximate common eigenvector q. In this setting, a necessary condition for stability is that the smallest (approximate) eigenvalue associated with q is not too large w.r.t. 2/η. Interestingly, in the setting of ReLU networks, this (approximate) common eigenvector assumption holds true (see Lemma 5). We thus make use of this property in our analysis of the solutions to which SGD can converge.
For completeness, we also present here a sufficient condition for stability in the special case of GD where ∇ψm(θ
∗) = 0 for all m ∈ I (see proof in Appendix IV). This setting is of interest in our case, since the global minima of overparameterized ReLU networks under the quadratic loss always satisfy this condition (see proof in Appendix VII for our setting). Lemma 3 (Sufficient conditions for stability). Consider full batch SGD (i.e. GD) with step size η. Let θ∗ be a minimum point of L, for which∇ψm(θ
∗) = 0 for all m ∈ I. Denote λuppermax = max
m∈I λmax(Hm). (16)
If λuppermax ≤ 2
η (17)
then θ∗ is linearly strongly stable.
Here we see that if all the subsystems are stable, then the overall switching system is strongly stable.

heading: 3 The implicit bias of minima stability
text: We now use our results to study the implicit bias of minima stability in the context of training of univariate ReLU networks. Specifically, consider the set of functions that can be implemented by a one-hidden-layer neural network with k neurons,
F = { f : R 7→ R ∣∣∣∣∣ f(x) = k∑
i=1
w (2) i σ
( w
(1) i x+ b (1) i
) + b(2) } , (18)
where σ(·) is the ReLU activation function. Each f ∈ F is a piece-wise linear function with at most k knots. We are interested in functions that minimize the quadratic loss,
L(f) = 1 2n n∑ j=1 (f(xj)− yj)2 , (19)
where {(xj , yj)}nj=1 are n training samples such that4 xi 6= xj whenever i 6= j. Definition 3. We say that f ∈ F is a solution if L(f) = 0. In this case the function satisfies f(xj) = yj for all j ∈ [n].
When k ≥ n there are infinitely many solutions. However, as discussed above, when training the network using SGD, not all of these global minima can be reached. Particularly, assume we use SGD to minimize the loss w.r.t. the parameter vector
θ = [ w
(1) 1 , . . . , w (1) k , b (1) 1 , . . . , b (1) k , w (2) 1 , . . . , w (2) k , b
(2) ]T ∈ R3k+1. (20)
What are the properties of the solutions (in function space) to which we can converge?
In Sec. 2 we saw that dynamic stability is associated with the Hessian of the loss at the minimum. Our goal is thus to link the Hessian to properties of the solution f in function space. A major challenge, however, is that each f ∈ F may have infinitely many different implementations θ, and each such implementation may have a different Hessian. Since we are only interested in the functionality f and not in its particular implementation, we consider a solution to be accessible by SGD if there exists some implementation of that solution which is a stable minimum for SGD (see Definition 1 and 2). Definition 4. We say that a solution f ∈ F is (strongly) stable for step-size η if there exists a minimum point θ∗ of the loss that corresponds to f , where θ∗ is linearly (strongly) stable for SGD with step-size η.
4In this work we focus on cases in which perfect fit is possible. Note that when xi = xj , if yi 6= yj then perfect interpolation is impossible, and if yi = yj then the jth training sample is redundant.
Our first result characterizes solutions in F that correspond to twice differentiable minima. For this type of minima, the knots of f do not coincide with any training point in the data set. In the following, f ′′(x) should be interpreted in the weak sense (i.e. it is a sum of weighted Dirac delta functions). Theorem 1 (Properties of twice differentiable stable solutions). Let f be a linearly stable solution for SGD with step-size η. Assume that the knots of f do not coincide with any training point. Then∫ ∞
−∞ |f ′′(x)| g(x)dx ≤ 1 η − 1 2 , (21)
where
g(x) = { min {g–(x), g+(x)} , x ∈ [xmin, xmax], 0, otherwise,
(22)
with
g–(x) = P2 (X < x)E [x−X|X < x] √ 1 + (E[X|X < x])2,
g+(x) = P2 (X > x)E [X − x|X > x] √
1 + (E[X|X > x])2. (23) Here X is drawn from the empirical distribution of the data (a sample chosen uniformly from {xj}).
This theorem shows that stable solutions of SGD correspond to functions whose second derivative has a bounded weighted norm. Importantly, the bound depends on the step size. As the learning rate increases, the set of stable solutions contains less and less non-smooth functions. Figure 2 depicts the weight g for various distributions of the training data. We can see that most of g’s mass is located at the center of the training data. Furthermore, g decays towards the extreme data points, and vanishes beyond them. This implies that stable solutions tend to be smoother for instances near the center of the data distribution, and less smooth for instances near the edges. Particularly, minima stability imposes no restrictions on the function’s smoothness outside the support of the data distribution.
A limitation of Theorem 1 is that when training with a very large step size, the set of stable solutions contains only very smooth interpolating functions. But such functions tend to have their knots coincide with data points [42], which contradicts the theorem’s assumption that the minimum is twice differentiable. To cope with such settings, we now present a result for non-differentiable minima. This result requires assumptions on the maximal number of neurons that can coincide with each data point, and is thus stated in terms of the number of knots of the function f (see Sec. 4.2 for detail). Theorem 2 (Properties of non-differentiable strongly stable solutions). Let f ∈ F be a piece-wise linear function with L ≤ k knots. Assume that f has an implementation θ∗ such that ‖θ∗‖∞ ≤ ρ. Define M = maxj∈[n] |xj | and C = max{1, ρ(1 +M)}. If f is a linearly strongly stable solution for SGD with step-size η, then ∫ ∞
−∞ |f ′′(x)| g(x)dx ≤ 1 η − 1 2 + ∆, (24)
where g(x) is defined in (22) and
∆ = 3
2 C2 1 + k − L n + C
√ 3
4 1 + k − L n
( 3C2
1 + k − L n + 2 η
) . (25)
Note that in the small over-parametrization regime, ∆ is small. Indeed, k − L is the number of excess neurons, i.e. the number of neurons employed by the network beyond the minimum required to realize an L-knot function. Therefore, in the regime where the number of samples n and number of neurons k grow while (k − L)/n → 0, we have that ∆ → 0 provided that C is bounded. The latter happens, for example, when the training data are bounded and generated by a smooth function5.

heading: 4 Proof outlines

heading: 4.1 Twice differentiable minima
text: Our goal is to characterize the minima to which SGD with step size η can converge, by using Lemma 1. We start by computing the Hessian matrix at a twice differentiable global minimum with zero error
5Savarese et al. [42] showed that ||θ∗||2 is bounded in this case, implying that ||θ∗||∞ ≤ ρ as well.
(so f(xj) = yj for all j ∈ [n]). The gradient of the loss (19) w.r.t. θ is given by
∇θL = 1
n n∑ j=1 (f(xj)− yj)∇θf(xj), (26)
where∇θf(x) is written explicitly in Appendix V. Thus, the Hessian is given by
∇2θL = 1
n n∑ j=1 (∇θf(xj)) (∇θf(xj))T + 1 n n∑ j=1 (f(xj)− yj)∇2θf(xj)
= 1
n n∑ j=1 (∇θf(xj)) (∇θf(xj))T , (27)
where we used the fact that f(xj) = yj for all j ∈ [n]. Let us denote the tangent features matrix by Φ = [∇θf(x1),∇θf(x2), . . . ,∇θf(xn)]. Then the Hessian can be expressed as ∇2θL = ΦΦ
T /n, and its maximal eigenvalue can be written as
λmax(∇2θL) = max v∈S3k
vT ( ∇2θL ) v = max
v∈S3k 1 n ‖ΦTv‖2 = max u∈Sn−1 1 n ‖Φu‖2 . (28)
Notice that this eigenvalue is implementation dependent. Namely, there are uncountably many sets of network parameters which correspond to the same end-to-end function f ∈ F , and different parameter sets can have different top Hessian eigenvalues. However, recall from Definition 4 that we only care whether there exists one implementation of f ∈ F whose top eigenvalue is small enough to allow convergence of SGD to that minimum. We would therefore like to analyze the implementation that minimizes λmax. Mathematically, we denote the set of all parameters corresponding to f as
Ω(f) = { θ ∈ R3k+1 ∣∣∣∣∣f(x) = k∑
i=1
w (2) i σ
( w
(1) i x+ b (1) i
) + b(2) } . (29)
By using the right-hand side of (28) for λmax, we show the following (see proof in Appendix VI). Lemma 4 (Top eigenvalue lower bound). Let f ∈ F be a twice-differentiable minimizer of the loss function, then
min θ∈Ω(f) λmax(∇2θL) ≥ 1 + 2 ∫ ∞ −∞ |f ′′(x)| g(x)dx, (30)
where g is defined in (22).
Now we can prove Theorem 1 based on Lemma 1 and 4.
Proof of Theorem 1. Since f is a stable solution, there exists a linearly stable minimum point θ∗ of L such that θ∗ ∈ Ω(f). Therefore,
1 + 2 ∫ ∞ −∞ |f ′′(x)| g(x)dx ≤ min θ∈Ω(f) λmax(∇2θL(θ)) ≤ λmax(∇2θL(θ ∗)) ≤ 2 η , (31)
where the first inequality follows from Lemma 4 and the last inequality follows from Lemma 1. From the leftmost and rightmost sides of (31), we get∫ ∞
−∞ |f ′′(x)| g(x)dx ≤ 1 η − 1 2 , (32)
which completes the proof.

heading: 4.2 Non-differentiable minima
text: A minimum θ∗ that is not twice differentiable corresponds to a network that interpolates the data, while at least one of its knots coincides with a data point. The neuron corresponding to each such knot, divides the parameter space into two regions: one where the neuron is active, and one where it is inactive. At the interior of each such region, the loss function is twice differentiable w.r.t. parameters. If we denote by pj the number of neurons that toggle precisely on xj , then the total number of toggling neurons for θ∗ is p = ∑n j=1 pj and the switching system in Definition 2 has 2 p relevant6 “modes”. We denote byH the set of 2p Hessian matrices corresponding to these modes. Additionally, we denote the analytic function representing f(xj ;θ) for themth mode by φ(xj ,θ,mj). For more details, see our switching system formulation in Appendix VII.
Our key observation is that when a neuron switches its mode, it hardly affects the Hessian matrix, let alone its top eigenvector. Therefore, if not too many neurons toggle, then the principal directions of all matrices inH tend to align (see proof in Appendix VIII). Lemma 5. Assume that ‖∇θφ(xj ,θ∗,mj)‖∞ ≤ C for all j ∈ [n] andm ∈ I . Denote the maximal number of neurons that toggle on any single data point by pmax = max{pj}. LetH be some matrix inH having a top eigen-pair q ∈ S3k and λmax(H). Then for all other H̃ ∈ H,∥∥∥H̃q − λmax(H)q∥∥∥ ≤ √3C (√λmax(H)+√λmax(H̃))√pmax
n . (33)
Note that if we chooseH to be the one with the largest top eigenvector, λuppermax (see (16)), then we get from the lemma that for allHm ∈ H,
‖Hmq − λuppermax q‖ ≤ √ 3C (√ λuppermax + √ λmax(Hm) )√pmax n ≤ 2 √ 3C √ λuppermax √ pmax n . (34)
To use Lemma 2, we would like to find an explicit expression for this bound. Under the assumption ‖θ∗‖∞ ≤ ρ we have that ‖∇θφ(xj ,θ,mj)‖∞ ≤ max{1, ρ(1 + M)}, where M = maxj∈[n] |xj |. Thus, C can be taken as max{1, ρ(1 + M)}. Note that ĝ(t)m = 0 for all m ∈ I and t > 0 (see Appendix VII). Thus, using Lemma 2 with γ = 0, δ = 2 √ 3C √ λuppermax √ pmax n and λm = λ upper max for allm (such that λlower = λuppermax ), we get that if θ∗ is strongly stable then (see Appendix IX)
λuppermax (θ ∗) ≤ 2
η + 3C2 pmax n + C √ 3 pmax n ( 3C2 pmax n + 2 η ) . (35)
If f ∈ F has L ≤ k knots, then pmax ≤ 1 + k − L. Substituting this upper-bound in (35), the necessary condition becomes
λuppermax (θ ∗) ≤ 2
η + 3C2 1 + k − L n + C
√ 3
1 + k − L n
( 3C2
1 + k − L n + 2 η
) . (36)
Finally, we show in Appendix X that, similarly to the twice differentiable case of Lemma 4, here as well
min θ∈Ω(f) λuppermax (θ) ≥ 1 + 2 ∫ ∞ −∞ |f ′′(x)| g(x)dx. (37)
Combining (37) and (36), shows that any strongly stable solution that meets the assumptions must satisfy (24).
6Modes that are near the minimum, i.e. that are in I.

heading: 5 Experiments
text: We now verify our theoretical predictions in experiments. We train a single-hidden-layer ReLU network using GD with varying step sizes, all initialized at the same point. Figure 3(a) shows the training data and solutions to which GD converged. Figure 3(b) depicts the corresponding weight function g and the (smoothed) absolute value of the second derivative of the solutions. When trained with a very small step size, GD converges to the black function, whose second derivative is quite large. However, even in this extreme case, the second derivative is small where the weight function g is high, which is in accordance with (21),(24). When trained with a medium step size, GD converges to the blue function, which is much smoother, particularly at the center of the training data. This trend continues as we increase the learning rate. Note that the green function, which is obtained with a large step size, is flat at the center, but has relatively large second derivative outside the support of the training data. This demonstrates that while minima stability restrains the solution within the support of the training data, it imposes no restrictions on the function’s smoothness outside of the support.
Figure 3(c) visualizes the sharpness of the solution as a function of the learning rate. Specifically, the red line marks the edge of the stable region, 2/η. Recall that GD cannot converge to a minimum whose sharpness exceeds this value. The yellow dashed line depicts the sharpness of the minima to which GD converged in practice. Here the two lines coincide, indicating that GD converged on the edge of the stable region. This is known to be a common phenomenon [8]. In blue, we plot the sharpness of the flattest implementation for each converged network (see Appendix XI for details). Finally, the purple curve depicts our lower bound on the sharpness of the flattest implementation, presented in Lemma 4. Note that our bound is relatively tight (purple curve close to the blue curve). Moreover, at the large step size regime, it is also quite close to the actual sharpness upon convergence (yellow curve). Additionally, since our bound is the weighted L1 norm of the second derivative of f ,
the decay of the purple line indicates that f indeed gets smoother as the step size increases, just like our theoretical results predict. Please refer to Appendix I for more details and additional experiments.

heading: 6 Related work
text: The implicit regularization of GD was widely studied in the context of matrix factorization and deep linear networks in regression tasks, e.g. in [1, 2, 5, 10, 11, 14, 26, 28, 40]. This standard problem was considered to be the key to understanding the inherent bias of GD. Another popular setting which was extensively studied is binary classification of linearly separable data. Soudry et al. [48] showed that among all linear separators that achieve the global minimum of the training loss, GD converges to the maximum margin separator. This result was extended and studied in other settings such as non-separable data, other loss functions, deep linear models, nonlinear networks with homogeneous activations, etc. [3, 6, 15, 16, 20–22, 27, 31, 33, 43, 55, 56]. Another long line of works focused on the “Neural Tangent Kernel” regime, which arises with large width or initialization, and a small learning rate (e.g., [7, 9, 18, 23, 37]). In this regime, networks converge to a linear predictor minimizing the RKHS norm, where the (“Tangent”) kernel is determined by the initialization.
Several works studied theoretically the implicit bias induced by the learning rate. Barrett & Dherin [4] and Smith et al. [47] respectively showed that GD and SGD, for a small step-size, approximately follow the GF trajectory on the modified loss, which is the sum of the original loss and a regularization term on the parameters. This regularization scales with the step-size and vanishes at any stationary point. Other works focused on linear models, such as linear regression [34, 52], univariate two-layer linear models [25], and deep linear models [32, 35]. Nar & Sastry [35] analyzed deep linear model trained with the quadratic loss and showed that GD cannot converge to certain minima, according to the step size. Mulayoff & Michaeli [32] considered the same setting, and showed that stable solutions (which correspond to flat minima) have special properties. However, for deep linear nets, minima corresponding to different functions, can be equally sharp. This means that minima stability does not promote certain functionalities over others. Accordingly, their results only state that the algorithm has a bias towards certain implementations. This is in contrast to our setting, in which we show that SGD is biased towards certain functions.
Minima stability was addressed in past work only for twice differentiable minima. Wu et al. [53] proved a sufficient condition under SGD, Tugay & Tanik [50] and Goh [13] gave a stability condition (sufficient and necessary) for GD with Polyak “heavy ball” momentum, Cohen et al. [8] extended his result to Nesterov acceleration, and Giladi et al. [12] derived similar results for asynchronous training. Here we present a new approach for analyzing non-differentiable minima, where we provide both necessary and sufficient conditions for stability.
The implicit bias of shallow ReLU networks trained with the quadratic loss, was studied in several works. However, none analyzed the effect of the learning rate. Perhaps most related to our result is [42], which showed that for univariate infinite-width shallow ReLU networks, a solution which minimizes the parameter norm also minimizes max( ∫ |f ′′(x)|dx, |f ′(∞) + f ′(−∞)|) (this was generalized to multivariate inputs in [38]). However, our result does not rely on the assumption that SGD converges to such a min-norm solution, and it is not yet clear when such an assumption holds. For example, [51] suggests that GF on shallow ReLU nets converges to a min-norm solution only with a vanishing initialization — while for larger initializations, we move closer to a kernel regime, and a very different implicit bias [23, 51]. Additionally, Shamir & Vardi [44] examined GF for a single ReLU neuron, and proved that the implicit bias cannot be exactly expressed as a (non-constant) function of the weights. However, bounds like we proved here, do not contradict this result.

heading: 7 Conclusion
text: SGD cannot converge stably to any minimum of the loss terrain. Prior work pointed out that stable minima are flat with respect to the step size. Here we presented a new approach for analyzing the stability of non-differentiable minima. Using our results, we examined a simple model of a single hidden layer univariate ReLU network. We showed that in this setting, stable solutions correspond to functions whose second derivative has a bounded weighted L1 norm. Particularly, we showed that the implemented function gets smoother as the learning rate increases, especially near the center of the support of the training distribution. Finally, we demonstrated our theoretical results in experiments.
Acknowledgements The research of Rotem Mulayoff was supported by the Planning and Budgeting Committee of the Israeli Council for Higher Education, and by the Andrew and Erna Finci Viterbi Graduate Fellowship. The research of Tomer Michaeli was supported by the Technion Ollendorff Minerva Center. The research of Daniel Soudry was supported by the Israel Science Foundation (grant No. 1308/18), and by the Israel Innovation Authority (the Avatar Consortium).

Review summaries:
 This paper attempts to answer the implicit bias of SGD via a stability analysis on a single hidden layer univariate ReLU network. The main result is that a stable solution that can be found by a larger learning rate must be smoother. In detail, they show the weighted L1 norm of the second derivative is upper bounded by roughly $2/\eta$, where $\eta$ is the learning rate. 

This paper studies a single hidden layer univariate ReLU network. The authors show that stable solutions learned by SGD will be functions whose second derivative has bounded weighted L1 norm. Besides, the learned function gets smoother as the learning rate increases.

The goal of this paper is to extend existing results on stable minima found by SGD to the non-differentiable setting of ReLU networks.   In particular, in its main contribution (Theorem 1) the paper shows that the solution found by SGD for 1-dimensional ReLU networks has bounded second derivative, under a weighted total variation norm. Moreover, this weighted norm is controlled by the step-size of SGD.  This implies that also for ReLU networks, SGD with large learning rate is biased towards smooth solutions. 

This paper studies the smoothness of the functions represented by single variate two-layer neural networks at minima with different flatness, and connect this smoothness with the implicit bias of (stochastic) gradient descent to flat minima. Firstly, for a twice differentiable minimum found by SGD, an upper bound for the leading eigenvalue of the loss function's Hessian matrix (with respect to parameters) is derived depending on the learning rate. Then, a weighted L1 norm of the second derivative of the model function (with respect to input data) is upper bounded by the Hessian's leading eigenvalue. Combining these two bounds, the weighted L1 norm of the model function's second derivative is bounded by a quantity depending on the learning rate. This result implies that SGD with bigger learning rate finds flatter minima, and thus finds smoother functions. The result only considers the minima found by optimization algorithms, hence it is independent with initialization.   For neural networks with ReLU activation, minima are sometimes not differentiable. The analysis above is extended to this case and similar bounds are also provided. The theorem works in the mildly over-parameterized case in which the number of neurons is slightly bigger than the number of training data.   Numerical experiments show that GD with bigger learning rate can indeed find smoother functions, especially in the region where training data are densely distributed. This observation is consistent with the theoretical results.