The Implicit Bias of Minima Stability: A View from Function Space
Authors: Rotem Mulayoff
Tomer Michaeli
Daniel Soudry
Venue: NeurIPS 2021 Poster (2021)
Keywords: Implicit bias
learning rate
step size
stability
Hessian
dynamical system

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 $L_1$ 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.

The Implicit Bias of Minima Stability: A View from Function Space
Rotem Mulayoff
Tomer Michaeli
Technion Israel Institute of Technology
Technion - Israel Institute of Technology
rotem aalllyyf@@gaall com
tomer m@ee. technion, ac
Daniel Soudry
Technion Israel Institute of Technology
daniel. soudry@gmail....... com
Abstract
The loss terrains of over-parameterized neural networks have multiple global min- ima. 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, show that SGD is biased towards functions whose second derivative (w.r.t the input) has bounded weighted L1 norm, and this is regardless initialization. In particular, we show that the function implemented by the net- work 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.
the
Introduction
Understanding the overwhelming success of deep learning requires unveiling the mechanisms that allow aver-parametrized models to generalize well, a phenomenon that 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- wer-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
regularization term that is added to the training loss [14]. This turned out to be true for several settings, such as over- wer-parametrized linear regression with the quadratic loss [57], matrix factorization under certain assumptions [26], and linear classification 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 (NcurIPS 2021).

---

10
[ (smnothedd)
15 x10
0.3
10a
((O.)
10:
0.2
109
5-
0.1
-10
10-
0.5
1
1.5
x10
(a) Loss vs. iteration
(b) Interpolating functions found by GD
(c) Second derivative and the weight function
Figure We train a univariate single hidden layer ReLU network using GD. one experiment (black) we use a constant learning rate 7,. In second experiment (green) we use the same step size and initialization, but when GD arrives near the minimum we increase the step size by a factor 3. This is equivalent to initializing near the minimum and training with two different step sizes. Panel (a) shows the losses during training. Before the step-size changes, the loss curves coincide. After the change, GD with the larger step-size experiences abrupt increase in the training loss, and the optimization eventually ends in a different minimum, as evident from Panels (b) and (c). Panel (b) shows the resulting functions implemented by the net, where the cross marks are the training points. The function obtained with the large step size is smoother, in line with our main result (1). Panel (c) depicts (a smoothed version of) (x)] for the two solutions, well as the weight function g(x) in (1). The If" [x)) obtained with the larger step-size is smaller, especially where g(x) is high.
by illustrating that the implicit bias of GD is often not equivalent to loss term of the form of any function of the network's weights [40, 44].
The current paradigm for analyzing implicit bias seeks ensure convergence to global minima as 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-eeee deepaddnn and relevant only to small step-sizes. Unfortunately, these type of analyses fail to capture phenomena that are known be directly related to the step size in practical training, e.g. [8. 17, 19, 24, 29, 45, 46, 53). For instance, Fig. demonstrates that when initializing GD near 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 intraalization-iddeeedeeen 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 which stochastic GD (SGD) can converge. Specifically, it 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 [53] for twice differential minima, but its implication on the learned function has not been discussed. Here we extend this analysis to non-diffeerntiaalee 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 pver-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 ff that globally minimize the loss (i.e. interpolate the data). Our key result (see Theorem 1) is that when using a step size of 1). SGD can only converge to solutions satisfying
f (15 < 2
1
(1)
with some particular weight function (see Fig. 1). In other words, the larger the step size, the smoother the solutions that network learns. The weight y is larger around the center of the support of the training distribution, and smaller towards boundaries. This implies that the solutions found by SGD tend to be smoother around the center of the distribution.

---

2 Minima stability
SGD is routinely used 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 dynamies the vicinity of minima. once SGD arrives near minimum, it converges to it, then we say that this is stable minimum. If SGD repels from the minimum, then we say that this an unstable minimum. Here we briefly survey and extend the existing knowledge about stable minima for SGD.
Let E Rd + R be differentiable almost everywhere for all j [n]. Consider a loss function L and its stochastic counterpart É, given by
(()) = Σ ()) 3=1
1 and ()) - B
Σ O)) JE
(2)
where B, is batch of size B sampled at iteration 1. We assume that the batches {2r} are drawn uniformly from the training set, independently across iterations. SGD's update rule given by
θ.t 0. (Q,)).
where 17 is the step size. In the following we define the notion of stability for minima, and provide conditions for a minimum to be stable.
2.1 Twice differentiable minima
We start by examining a twice differentiable minimum 0". Using Taylor expansion about 0", we have
1 10 (0) = + (0- - 0*),
(4)
where 0²) and V (0") are the gradient and Hessian of Ê, 0", Therefore, in the vicinity of the minimum, (3) is approximately given by
011 0. - V'
(5)
This approximation gets accurate as θ, gets closer to 0". We can thus this linearized dynamics to learn about the stability of minima [53].
Definition (Linear stability). Let 0* be twice differentiable minimum of Consider the linearized stochastic dynamical system
0++ = 1 V (0.)
(6)
Then 0" said be linearly stable if for any Oo in the e-ball B,(0"), we have lim sup O, 0l] E.
t-000
In other words, 0* is linearly stable if once we have arrived at a distance of from it (at without loss of generality), we end up at distance no greater than E around it in expectation. Some of our results do not depend on E, which case we simply refer to "linear stability" (without the s).
Wu et al. [53] provided a sufficient condition for linear stability under the assumption that (O*) 0 for all t 2 1. For our analysis, we need a necessary condition. This is simple obtain from the well known stability criterion for GD and the fact that GD's trajectory corresponds to the expectation of SGD's 's steps. Specifically, we have the following condition (which only requires that (E/V (. O; see formal proof in Appendix II).
Lemma (Necessary condition for stability). Consider SGD with step size n, where batches are drawn uniformly from the training set, independently across iterations. 0 is an a linearly stable minimum of L. then
Amax (V2C(0-) < -
Note that this condition is also sufficient when considering GD (i.e. full batch SGD).
3

---

2.2 Non-differentiable minima
We now generalize the definition of linear stability non dinfeffeerntiable minima. In deep learning. non non-differentiabiiiyy is typically caused by mode switch in the system, e.g. switching of ReLU activations or max max-looling 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 SGI''s dynamics as a switching dynamical system.
Let { be partition of IRd that represents the regions of the different modes, i.e.
vi + j S S, = Ø and Um Sm = R
(8)
Additionally, let 2b m R + R be an analytic function representing the loss for the mth mode. We assume the overall loss (and its stochastic version) can be written as'
( = V (0), (x
304) m (0)
if 0 Sm:
where v/m is the stochastic counterpart of a at time t. Therefore, near minimum 0 we can approximate the loss as
(0) (0)) + (0- 0"' (2) 90
1 20 0- H 0");
(10)
2
where (defining [n) as the interior of A)
A0 Int((mm)
Do
(()
v t0 (0")
and
H a 42 (0))0
(11)
The update rule of SGD (3) can thus be approximated as
0++1 0, 7 (9.. H (0. (0.
(12)
Note that this approximation is relevant only when O, is close to 0-, Let the indices of the sets around 0", and let A = Umez Sm be their union. We assume there finite number of modes in A (this is always the case for ReLU networks with a finite number of parameters). Consider E-neighborhood around the minimum such that (0)) C A. We define linear stability in this neighborhood as follows.
0" E Sm) } be
Definition 2 (Generalized linear stability). Let 0" be a minimum point of C. Consider the switching stochastic dynamical system
0 0: n (9 + Ho. (0: (0.-
(13)
and assume that O: E A with probability one for all 0.
0* is said be linearly stable if lim sup B[[|0, 0'll] S for any 0, E (0")
t-:00
0 is said to be linearly strongly stable if sup E[l 0" II| S for any Oo E (0").
In other words, we consider a situation where at some point in time (which call t without loss of generality), the parameter vector is E-close to 0" If this guarantees that from that moment on, A, is always e-close 0" in expectation, then 0" is called strongly stable. If this only guarantees that from some later point in time, 0, is always c-close to 0 in expectation, then 0" called stable.
Our results are stated in terms of H m Vi m (0") and 9 = bi (0*). The next lemma gives 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 0" be a minimun point of L. for which there is a finite number of modes in I. Suppose there exist E Sd-1 and {Sm) such that H mm Am < for all m I and denote
Nlower
min {dm}. mEI
(14)
and 7 maxmer T If
A lower
2 - 7
(15)
E'
then 0* is not an strongly stable minimum. Furthermore, if 0 fi.e. q is common eigenvector) then 0* is not an stable minimum.
'This is true since the modes corresponding to batch are a subset of those of the full data.
SS.,. denotes the closure of Sm..
NNote that (t( It=1 1 are i.i.d. and therefore Ella" ( [] is time invariant.

---

Note that the lemma considers the case where the Hessians of all subsystems have an approximate common cigenvector q. In this setting, necessary condition for stability is that the smallest (approximate) eigenvalue associated with q is not too large w.r.t. 2/1z. 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 sufficient condition for stability in the special case of GD where Vah,,, (0") = O for all m E 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 (Sufficient conditions for stability). Consider full batch SGD (i.e. GD) with step size n). Let 0* be minimum point of L, for which mm 0 for all m E I. Denote
upper
max Amax H m) MEZ
(16)
max
If
upper 2
(17)
max
?
then 0* is linearly strongly stable.
Here we see that if all the subsystems are stable, then the overall switching system is strongly stable.
The implicit bias of minima stability
We now results 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: f/:R 5={1:
k
f(z)=
f(x)
Σ wi (0
(2)
x x 6(2)
(18)
where (.) is the ReLU activation function. Each F a wisce-wise linear function with at most k knots. We are interested in functions that minimize the quadratic loss,
n C())
Σ (f(xz) 2n 1=1
1
- -
(19)
where {(zj, 91) D;)) are training samples such that' 2; + xι whenever i i
Definition 3. We say that f F is a solution if L(f) 0. In this case the function satisfies f(zz) = yj for all E [n].
When & 2 there 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 minimize the loss w.r.t. the parameter vector
(1) = w
(1) Wi bb1
E 33++1
(20)
What are the properties of the solutions (in function space) to which we converge?
In Sec. 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 FF may have infinitely many different implementations 0, and each such implementation may have different Hessian. Since 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 stable minimum for SGD (see Definition 1 and 2).
Definition 4. We say that a solution f E F is (strongly) stable for step-size if there exists minimum point 0r of the loss that corresponds to where O* is linearly (strongly) stable for SGD with step-size size n.
'In this work we focus on cases in which perfect fit is possible. Note that when = xy. if 7 yy then perfect interpolation is impossible, and if y y) then the ýth training sample is redundant.
5

---

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, (x) should be interpreted in the weak sense (i.e. it is sum of weighted Dirac delta functions). Theorem (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
pc
1
(())) 1
(21)
2
where
min (
x E [Tmin Tmax]; otherwise,
g(x) 10,
(22)
with
g (()) = P (X < x E X < d) (E[ < x))²
= (xxx)= (x x) E[x - x X x] V1 ( > 2²)²
(23)
Here X is drawn from the empirical distribution of the data (a sample chosen uniformly from {z₂})
This theorem shows that stable solutions of SGD correspond to functions whose second derivative has bounded weighted norm. Importantly the bound depends 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 g's mass is located the center of the training data. Furthermore, 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 restrictions the function's 's smoothness outside the support of the data distribution.
limitation of Theorem 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 's assumption that the minimum is twice differentiable. To cope with such settings, we now present 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 (Properties of non -in-differenti strongly stable solutions). Let f E F be a piece-wise linear function with L < k knots. Assume that f has an implementation 0 such that ||0' S p. ( (1, p(1 + M)}. If is a linearly strongly stable solution
Define M = maxje[n] [æz] and C = max for SGD with step-size 77, then
((())) < 1 +A,
(24)
"1
where g(z) is defined in (22) and
A = 02 1 + k
31+k L
1 1
2 +
+ C
302
(25)
4 n
Note that in the small over parametrizatioon regime. A 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 and number of neurons grow while (A: - L)/n n > O, we have that - 0 provided that is bounded. The latter happens, for example, when the training data are bounded and generated by a smooth function".
4
Proof outlines
4.1 Twice differentiable minima
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 twice differentiable global minimum with zero error
Savvress al. [42] showed that 0/ is bounded in this case, implying that ||0'| p as well.

---

0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
0
-2
1
-2
2
-1
2
22
(a) Uniform distribution
(b) Gaussian distribution
(c) Laplace distribution
Figure 2: Graphs of g(x) for different distributions. For each distribution, the empirical graph of (red) is based on n = 20 i.i.d. samples, where we normalized them to zero average and standard deviation one. The theoretical graph (blue) computed by using the population distribution of X in (via numerical integration).
(so f(z,)) yy for all j E [n)). The gradient of the loss (19) w.r.t. 0 is given by
Vel 1 Σ (f(x,) yj) Vof(zy),
(26)
where Vof(x) is written explicitly in Appendix V. Thus, the Hessian is given by
V&c
Σ
[of(ez)
1 Σ (f(z,) 41) Vof(a,)
1
m Σ
(27)
where we used the fact that f(x;) = M for all j E [n]. Let us denote the tangent features matrix by + [of(x1), Vol(xz), ..... Vol(a,)) Then the Hessian can be expressed as Vo = ΦΦ"" /n,
and maximal eigenvalue can be written as
Amax (22C)
max v' (V2C) v max - wESSE
v - max Pu
(28)
ueS"
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. and different parameter sets can have different top Hessian eigenvalues. However, recall from Definition that we only whether there exists one implementation of f E 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 Amax- Mathematically, we denote the set of all parameters corresponding
{ f I 333++1
R() -
f(x)
Σ i=1
(wf x x xb,)) ((2)
(29)
By using the right-hant hand side of (28) for Amaxx we show the following (see proof in Appendix VI). Lemma (Top eigenvalue lower bound), Let f E be a twice difce-iiffreentiable minimizer of the loss function, then
min Amai (224)21+3 GEA(J)
2 122
15" (())))g())dr,
(30)
where g is defined in (22).
Now we can prove Theorem based on Lemma and 4.
Proof of Theorem I. Since f is a stable solution, there exists linearly stable minimum point 0" of L such that 0* E Es()). Therefore,
2
1+2 (x))) S min Aeaix (V2C(8)) & Amax (VZL(0")) - DEA(f)
(31)
7

---

Pmax 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
1 (()))) S 11 2
(32)
which completes the proof.
4.2 Non-differentiable minima
minimum 0" that is twice differentiable corresponds 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: inactive. At the interior of each such region, the loss function is twice differentiable w.r.t parameters. If we denote by Рj the number of neurons that toggle precisely on Ij. then the total number of toggling neurons for 0" is p _j-1 Pj and the switching system in Definition 2 has 2 relevant "modes". We denote by 7. the set of 2" Hessian matrices corresponding to these modes. Additionally, we denote the analytic function representing (z;;;) 0) for the mith mode by p(xj, 0, m2). For more details,
where the neuron is active, and where it is
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 H tend to align (see proof in Appendix VIII).
Lemma 5. Assume that [[V 0", ml)) I C for all j E [n] and m I. Denote the maximal number of neurons that toggle on any single data point by Pmax = max{p;} }. Let H be some matrix in H having top eigen-pair E 93k and (H). Then for all other H H.
(V (H) + V /Amax((ft)
Hqq - Xmax (m)) S v3C
(33)
n
Note that if choose H to be the one with the largest top eigenvector, Auppe from the lemma that for all Hm E H.
(see (16)), then get
H m
all S /3C max
upper
Amaax
upper
V Amax (H m))
V Pmax
S 2V33VV
Amax
Pmax
(34)
n
Y
To use Lemma 2, we would like to find an explicit expression for this bound. Under the assumption ||0'|| S P we have that [V 0, ml))l S max (1, M)). where M maxxe(x] [zyl-
Thus, C can be taken max p(1 + M)). Note that _ for all m E I and t > 0 (see Appendix VII). Thus, using Lemma 2 with 7 = 0, ô == 2/3C Amax Pmaxx and Am Amax for all m (such that llower Amme)) ) we get that if 0" is strongly stable then (see Appendix IX)
(0') A max
- 2 17
2 n 3maxxxxx + c Pmax (3c2Pruax +
Pmax
(35)
n
If f E F has L S knots, then Pmax S 11 k L. Substituting this upper-bound in (35), the necessary condition becomes
1 - k - L A (0)) (0') 30 1 + C 3 max
2 17
3C2 1 + L
2 ;
(36)
Finally, we show in Appendix X that, similarly to the twice differentiable case of Lemma 4, here as well
upper (0) 2 1 / g()))) g(z)dr.
min
(37)
EEA()
max
Combining (37) and (36), shows that any strongly stable solution that meets the assumptions must satisfy (24).
"Moess that near the minimum. i.e. that in I.

---

x10
20
0.0001
(2)()) (smoothed)
30-
77
0.0001
0.003
0.003
0.4
10
0.05
0.05
20
0.3
0.2
-10
10
0.1
-2
22
(a) Examples of interpolating functions
(b) Corresponding second derivative and weight function
10
2/1 Ause convergence
mintsry: Awar
2 se (())
108
10 10-4
10-5
10-2
10
10
7
(c) Sharpness versus learning rate
Figure 3: GD training of a one-hidden-layer ReLU network using various step sizes. Panel (a) shows
the training data and the solutions to which GD converged for three different step sizes. Panel (b) depicts the corresponding weight function y. and the second derivative of the solutions. Panel (c) visualizes the sharpness of the solutions versus the learning rate. From these plots we see that the GD solution gets smoother the step size increases, particularly at the center of the training data.
Experiments
We now verify 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 which GD converged. Figure 3(b) depicts the corresponding weight function 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 high, which is in accordance with (21). When trained with 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 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 's smoothness outside of the support.
function of the learning rate. Specifically, the red line marks the edge of the stable region, 2/1.. Recall that GD cannot converge to 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 known be a common phenomenon [8]. 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, also quite close the actual sharpness upon convergence (yellow curve). Additionally, since our bound is the weighted L, norm of the second derivative of f.
Figure 3(c) visualizes the sharpness of the solution

---

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.
Related work
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, 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 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 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, 35J. 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 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-widd shallow ReLU networks, solution which minimizes the parameter norm also minimizes max(J J' If" (')x)) [oo + f'(-))))) (this was generalized 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 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 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.
7 Conclusion
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 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 L, 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, demonstrated our theoretical results in experiments.
10

---

Acknowledgements The research of Rotem Mulayoff was supported by the Planning and Budget- ing Committee of the Israeli Council for Higher Education, and by the Andrew and Emna 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).
References
[1] Arora, S., Cohen, N., and Hazan, E. E. On the optimization of deep networks: Implicit acceleration by overparameterization. In 35th International Conference on Machine Learning, ICML 2018, pp. 372-389 International Machine Learning Society (IMLS), 2018.
[2] Arora, S., Cohen, N., Hu, W., and Luo, Y. Implicit regularization deep matrix factorization. arXiv preprint 1905. 2019.
[3] Azulay, S., Moroshko, E., Nacson, M. S., Woodworth, B. E., Srebro, N., Globerson, A., and Soudry, D. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 468-477. PMLR, 18-24 Jul 2021.
[4] Barrett, D. and Dherin, Implicit gradient regularization. International Conference on Learning Representations, 2021.
[5] Belabbas, M. A. On implicit regularization: Morse functions and applications matrix factorization, arXiv preprint arXiv:2001 2020.
[6] Chizat, L. and Bach, Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pp. 1305-1338, PMLR, 2020.
[7] Chizat, L., Oyallon, E., and Bach, F. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pp. 2937-2947, 2019.
[8] Cohen, J., Kaur, S., Li, Y., Kolter, J. Z., and Talwalkar, A. Gradient descent neural networks typically occurs at the edge of stability. International Conference on Learning Representations, 2021.
[9] Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations, 2019.
[10) Eftekhari, A. and Zygalakis, K. Implicit regularization in matrix sensing: A geometric view leads to stronger results. arXiv preprint arXiv:2008. /2091, 2020.
[11] Gidel, G., Bach, F., and Lacoste-Julien, S. Implicit regularization of discrete gradient dynamics in linear neural networks. arXiv preprint arXiv: /904. 33262, 2019.
[12] Giladi, N., Nacson, M. S., Hoffer, E., and Soudry, D. At stability's edge: How to adjust hyperparameters preserve minima selection in asynchronous training of neural networks? ICLR, pp. 1-21, sep 2020. ISSN 23318422.
[13] Goh, G. Why momentum really works. Distill, 2(4))e6, 2017.
[14] Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
[15] Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. Characterizing implicit bias in terms of optimization geometry, arXiv preprint arXiv: 1802.08800 2018
[16] Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018.

---

[17] Hoffer, E., Hubara, I., and Soudry, D. Train longer, generalize better: Closing the generalization gap in large batch training neural networks. Advances in Neural Information Processing Systems, pp. 1731-1741, 2017.
[18] Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, pp. 8571-8580, 2018.
[19] Jastrzebski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. Three factors influencing minima in SGD, arXiv preprint arXiv:/711.04622; 2017.
[20] Ji, Z. and Telgarsky, M. Risk and parameter convergence of logistic regression. arXiv preprint 18Xxv:803300700, 2018.
[21] Ji, Z. and Telgarsky, M. J. Gradient descent aligns the layers of deep linear networks. In 7th International Conference Learning Representations, ICLR 2019, 2019.
[22] Ji, Z., Dudík, M., Schapire, R. E., and Telgarsky, M. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pp. 2109-2136. PMLR, 2020.
[23] Jin, H. and Montúfar, G. Implicit bias of gradient descent for mean squared error regression with wide neural networks. arXiv preprint arXiv:2006.07:33 2020.
[24] Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. T. P. On large- batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 16X1v:6609004866, 2016.
[25] Lewkowyez, A., Bahri, Y., Dyer, E., Sohl-Dickstein, J., and Gur-Ari, G. The large learning rate phase of deep learning: The catapult mechanism. arXiv, 2020.
[26] Li, Y., Ma, T., and Zhang, H. Algorithmic regularization in over- parammettteez matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pp. 47. PMLR, 2018.
[27] Lyu, K. and J. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.
[28] Ma, C.,, Wang, K., Chi, Y., and Chen, Y. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 3345-3354. PMLR, 2018.
[29] Masters, D. and Luschi, C. Revisiting small batch training for deep neural networks. arXiv preprint 1r..vv1104.0000 07612, 2018.
[30] Morgan, N. and Bourlard, H. Generalization and parameter estimation in feedforward nets: Some experiments. In Advances in neural information processing systems, pp. 630-637, 1990.
[31] Moroshko, E., Gunasekar, S., Woodworth, B., Lee, J. D., Srebro, N., and Soudry, D. Implicit bias in deep linear classification: Initialization scale training accuracy. arXiv preprint arXiv:2007.06738 2020.
[32] Mulayoff, R. and Michaeli, T. Unique properties of flat minima in deep networks. In Interna- tional Conference on Machine Learning, pp. 7108-7118. PMLR, 2020.
[33] Nacson, M. S., Lee, J., Gunasekar, S., Savarese, P. H. P., Srebro, N., and Soudry, D. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2428. PMLR, 2019.
[34] Nakkiran, Learning rate annealing can provably help generalization, even for convex problems. arXiv, pp. 1-9, 2020.
[35] Nar, K. and Sastry, S. Step size matters in deep learning. In Advances in Neural Information Processing Systems, pp. 1436-3444 2018.
[36] Neyshabur, B., Tomioka, R., and Srebro, N. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1rXiv:1412.6614. 2014.
12

---

[37] Nguyen, Q. On the proof of global convergence of gradient descent for deep relu networks with linear widths. arXiv preprint arXiv:2101.09612, 2021.
[38] Ongie, G., Willett, R., Soudry, D., and Srebro, N. A function space view of bounded norm infinite width ReL.U nets: The multivariate case. In International Conference on Learning Representations, 2020.
[39] Oymak, S. and Soltanolkotabi, M. Overparameterized nonlinear learning: Gradient descent takes the shortest path? In International Conference Machine Learning, pp. 4951-4960. PMLR, 2019.
[40] Razin, N. and Cohen, N. Implicit regularization in deep learning may not be explainable by norms, arXiv preprint arXiv:2005.06399 2020.
[41] Razin, N., Maman, A., and Cohen, N. Implicit regularization in tensor factorization. arXiv preprint arXiv: 102.0990, 2021.
[42] Savarese, P., Evron, I., Soudry, D., and Srebro, N. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pp. 2667-2690. PMLR, 2019.
[43] Shamir, O. Gradient methods never overfit on separable data. Journal of Machine Learning Research, 22(85):1-20) 20, 2021.
[44] Shamir, O. and Vardi, G. Implicit regularization in ReLUU networks with the square loss. arXiv preprint arXiv:20/2.05//56 2020.
[45] Simsekli, U. Sagun, L., and Gurbuzbalaban, M. A tail-index analysis of stochastic gradient noise in deep neural networks. arXiv preprint arXiv:1901.06000 2019.
[46] Smith, S. L. and Le, Q. V. A bayesian perspective on generalization and stochastic gradient descent. arXiv preprint arXiv:1710.064511 2017.
[47] Smith, S. L., Dherin, B., Barrett, D. G. T., and De, S. On the origin of implicit regularization in stochastic gradient descent. ICLR, pp. 1-14, 2021.
[48] Soudry, D., Hoffer, E.,, Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-2878, 2018.
[49] Strand, O. N. Theory and methods related to the singular-function expansion and landweber's iteration for integral equations of the first kind. SIAM Journal on Numerical Analysis, 11(4): 798-825, 1974.
[50] Tugay, M. A. and Tanik, Y. Properties of the momentum Ims algorithm. Signal Processing, 18 12):177-127, 1989.
[51] Williams, F., Trager, M., Silva, C., Zorin, D., Panozzo, D., and Bruna, J. Gradient dynamics of shallow univariate ReLU networks. Advances in neural information processing systems, 2019.
[52] Wu, J., Zou, D., Braverman, V., and Gu, Q. Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate. ICLR, 2021.
[53] Wu, I.., Ma, C., and Weinan, E. How SGD selects the global minima in avrr-parameterized learning: dynamical stability perspective. In Advances in Neural Information Processing Systems, pp. 8279-8288. 2018.
[54] Wu, X., Dobriban, E., Ren, T., Wu, S., Li, Z., Gunasekar, S., Ward, R., and Liu, Q. Implicit regularization of normalization methods. arXiv preprint arXiv:191 2019.
[55] Xu, T., Zhou, Y. Ji, K., and Liang, Y. When will gradient methods converge to max-margin classifier under ReLU models? Stat, 10(1))e354, 2021.
[56] Yun, C., Krishnan, S., and Mobahi, H. A unifying view on implicit bias in training linear neural networks. International Conference on Learning Representations, 2021.
[57] Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
13


Reviews:
[{"review_id": "lBtn56Z5Kdk", "reviewer": "Reviewer_g3RQ", "summary": "\nThis 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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper presents an interesting result about implicit regularization of SGD, that the stable local minimum which can be found by SGD must be smooth enough, depending inversely on the learning rate. The key observation is that for this specific single layer univariate network, the spectrum of the hessian at interpolating solution forms an upper bound for the weighted integral of the absolute value of the second derivative with respect to the input. One main technical contribution is that the authors also manage to deal with the case of non-smooth case. Experiments in Figure 1 also suggest the theory in this paper captures the phenomena in practical training pretty well.\n\nHowever, the analysis in the paper doesn't give a complete story for the implicit bias of SGD, because a priori, it's not clear if SGD is always converging to a linearly stable solution. Moreover, it's not even clear if SGD is converging to any solution. On the other hand, note both the gradient and its noise vanish at any interpolation solution, thus even if a solution is not stable, SGD will not necessarily deviate it without stronger noise assumptions, which is non-vanishing at global minimum. In the analysis of the paper, the authors actually don't use any property about the noise, no matter if it's SGD noise, isotropic noise, or even just noiseless full-batch GD. The stability result still applies.\n\nTherefore, the main message of this paper should be interpreted as, strong stability solution of SGD with a large learning rate is smooth but not \"the function implemented by the network upon convergence gets smoother as the learning rate increases\", as stated in the abstract, which is kind of overselling.\n\nI also have a question about the claim that \"a trained model tends to be smoother at the center of the training distribution\". Is this verified by experiments or only from the upper bound? As far as I can see, the derivation of the upper bound is quite crude (e.g. fixing $u$ to be all one vector) and use $\\min(g^+,g^-)$ to lower bound $g^+$ or $g^-$ and there's room to further tighten the bound. For example, if the authors don't use $\\min(g^+,g^-)$ but $g^+$ or $g^-$ directly, does the weight in the bound still peak in the middle?\n\nOverall, I found the idea of this paper quite novel and interesting. The writing is also clear and the paper is easy to follow. Thus I tend to accept the paper and would like to improve the score if the authors could give satisfactory answers to my above questions.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "jesohDCWoVF", "reviewer": "Reviewer_hfKq", "summary": "The goal of this paper is to extend existing results on stable minima found by SGD to the non-differentiable setting of ReLU networks. \n\nIn 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.\n\nThis implies that also for ReLU networks, SGD with large learning rate is biased towards smooth solutions. ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is to best of my knowledge the first work which analyzes minima stability in the non-differentiable setting of 1D ReLU networks. I found Theorem 1 a rather interesting and (to me) non-trivial result. \n- The theoretical results are to some extend confirmed by the experiments in Fig. 2. \n\nWeaknesses:\n- The mathematical analysis framework used to deal with the non-differentiable setting appears not fully rigorous. \n- As mentioned in the paper, for ReLU nets f'' is a sum of Dirac measures, so it does not makes sense to talk about f''(x). This is due to the fact that the singular measure f'' does not have a density with respect to the Lebesgue measure dx. The mathematically rigorous formulation of the integral would be \\int g(x) d|f''|(x), where |.| denotes the total variation of the measure f''.  In that context, I did not fully understand the meaning of |f''(x_j)| < \\infty in Theorem 1. Does it mean that the input data points do not lie at the \"jump points\" of the function? This would seem like a quite strong restriction.  \n- A more extensive empirical evaluation/demonstration of Theorem 1 would in my opinion greatly improve the work, e.g., plotting \\int g(x) d|f''|(x) for different step-sizes \\eta, and comparing it to 1 / \\eta. \n\nComments:\n- I believe it needs to be assumed somewhere in Sec. 2.2 that \\theta* is in the interior of one of the S_m? Otherwise, its gradient in (11) is not uniquely defined. Most likely this is not a strong assumption, since a tiny perturbation of \\theta* should not influence the result. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In this paper, a rather simplified setting is considered (1-hidden layer ReLU networks with one-dimensional inputs and outputs). Perhaps it can be mentioned to what extend the results can be generalized to the higher-dimensional setting. \n\nTo me, it seems that the analysis does not seem to easily extend to this higher-dimensional setting. In the one-dimensional case, the second derivative of the function can be represented by a sum of Dirac measures, while in the higher-dimensional setting quite complicated scenarios can appear. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "cjsvEVEkGs", "reviewer": "Reviewer_m6GT", "summary": "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. \n\nFor 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. \n\nNumerical 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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Flat minima are widely known to have better generalization performance than their sharp counterparts. Many works have explored the connection between algorithms and flatness. Some of them build connection between algorithms and the flatness of the minima they found, while others design new algorithms which can find flatter minima. This work, however, build a more complete theoretical understanding by also addressing another problem: the implicit regularization mechanism of flat minima. The authors show that models at flat minima usually represent smoother functions, which (partially) explains why flat minima generalize better. Exploring the connection between the landscape in the parameter space and the landscape in the input data space seems like a promising way to study the implicit regularization of optimization algorithms. \n\nSome major comments and concerns are:\n1. The bounds on \\lambda_max only depend on the learning rate, and are independent with batch size, and actually this bound is trivial. Hence, the bounds work for full batch GD and do not distinguish GD and SGD, which means the additional implicit regularization effect of SGD is not shown by the results. In practice, though, SGD is usually observed to have better performance than GD. Bounds for the minima found by SGD depending on both the learning rate and the batch size are derived in existing works, such as [52] cited in the paper. Is it possible to derive similar finer bounds for the smoothness of the model functions? \n\n2. The analysis is conducted in a restrictive setting: single variate two-layer neural networks. This limits the insights provided by and the potential application of the theory. What is the hardness of extending the analysis to high dimensional setting? If theoretical extension is nontrivial, numerical experiments of the high dimensional problem may also show the generality of the theory. \n\n3. On line 135-136, the authors said \"in the setting of ReLU networks, this (approximate) common eigenvector assumption holds true\" regarding to the assumptions in Lemma 2 above. It there any justification of this claim?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations. Since this is a theoretical study, I do not think there will be any direct negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}, {"review_id": "HNd0Qq6r7JO", "reviewer": "Reviewer_d3sA", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper shows that the earned stable solutions will be smoother if we increase the learning rate. Overall this paper is well organized. The results are interesting and seem solid. However, I still have the following concerns:\n\n1.  Because the NN function f is a pice-wise linear function for both input x and parameter \\theta. Thus the classical second derivative |f''(x)| doesn't exist. It would be much better if the authors can give the weak definition of |f''(x)| in the main part of the paper rather than in the appendix(line 112). Besides, I get quite confused about the condition |f''(x_j)| < \\infty (line 174) because f''(x) is sum of weighted Dirac delta function. The authors may want to add some comments on it.\n\n2. In the definition of linear stability and generalized linear stability(Definition 1 &2), there is a parameter $\\epsilon$. Why doesn't $\\epsilon$ show up in the condition of Theorem 1&2?\n\n3. Currently, the result of theorem 2 could not hold for the overparameterized setting where the neuron number k > > n, the input dimension also needs to be set as 1.  Could the result of this paper be generalized to the setting without those limitations?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative social impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work analyzes the prediction surface of weights reached by descent methods, arguing it is smooth on average (integral of second derivative is small).  Reviewers are supportive, but had many detailed comments, to which the authors in turn gave detailed responses. 
 I believe incorporating these discussions and comments in revisions will greatly strengthen the paper, and urge the authors to do so.
Decision: Accept (Poster)