Chaotic Regularization and Heavy-Tailed Limits for Deterministic Gradient Descent
Authors: Soon Hoe Lim
Yijun Wan
Umut Simsekli
Venue: NeurIPS 2022 Accept (2022)
Keywords: gradient descent
chaos
stochastic differential equations
heavy tails
homogenization

Abstract: Recent studies have shown that gradient descent (GD) can achieve improved generalization when its dynamics exhibits a chaotic behavior. However, to obtain the desired effect, the step-size should be chosen sufficiently large, a task which is problem dependent and can be difficult in practice. In this study, we incorporate a chaotic component to GD in a controlled manner, and introduce \emph{multiscale perturbed GD} (MPGD), a novel optimization framework where the GD recursion is augmented with chaotic perturbations that evolve via an independent dynamical system. We analyze MPGD from three different angles: (i) By building up on recent advances in rough paths theory, we show that, under appropriate assumptions, as the step-size decreases, the MPGD recursion converges weakly to a stochastic differential equation (SDE) driven by a heavy-tailed L\'{e}vy-stable process. (ii) By making connections to recently developed generalization bounds for heavy-tailed processes, we derive a generalization bound for the limiting SDE and relate the worst-case generalization error over the trajectories of the process to the parameters of MPGD. (iii) We analyze the implicit regularization effect brought by the dynamical regularization and show that, in the weak perturbation regime, MPGD introduces terms that penalize the Hessian of the loss function. Empirical results are provided to demonstrate the advantages of MPGD.

Chaotic Regularization and Heavy-Tailed Limits for Deterministic Gradient Descent
Soon Hoe Lim Nordita
KTH Royal Institute of Technology and Stockholm University soon. hoe. limelu..msss.... se
Yijun Wan
Département de Mathématiques et Applications École Normale Supérieure, Université PSI. wan@clipper. enst.enss...... fr
Umut Şimşekli
DI ENS, École Normale Supérieure, Université PSL, CNRS, INRIA umut. wwwsskiimiiiiii......mmmmima
Abstract
Recent studies have shown that gradient descent (GD) can achieve improved gener- alization when its dynamies exhibits chaotic behavior. However, obtain the desired effect, the step-size should be chosen sufficiently large, a task which is problem dependent and can be difficult in practice. In this study, incorporate a chaotic component to GD in controlled manner, and introduce multiscale per- turbed GD (MPGD). novel optimization framework where the GD recursion augmented with chaotic perturbations that evolve via an independent dynamical system. We analyze MPGD from three different angles: (i) By building up on re- cent advances in rough paths theory. we show that, under appropriate assumptions, as the step-size decreases, the MPGD recursion converges weakly stochastic differential equation (SDE) driven by a heavy-tailed Lévy-stable process. (ii) By making connections to recently developed generalization bounds for heavy-tailed processes, we derive generalization bound for the limiting SDE and relate the worst-case generalization error over the trajectories of the process to the parame- ters of MPGD, (iii) We analyze the implicit regularization effect brought by the dynamical regularization and show that, in the weak perturbation regime, MPGD introduces terms that penalize the Hessian of the loss function. Empirical results are provided to demonstrate the advantages of MPGD.
Introduction
Many important problems in supervised learning can be expressed by the following population risk minimization problem:
RR(x) EE]d[[((, ZER
min
where x E Rd denotes the learnable parameter, E Z denotes a data sample coming from an unknown data distribution D, Z denotes the space of data points, and é [2d x Z - RR, is the loss
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

function, measuring the quality of the parameter 2. Since the data distribution D is not known, as proxy for solving we consider the empirical risk minimization (ERM) problem, given as follows:
(R(,, Sw)) 1 l(a,, } T1
min ZER
where Sn ;- (Z1..... } denotes a training set of n points that are independently and identically distributed (i.i.d.) and sampled from D. To solve the ERM problem, typically gradient-based optimization algorithms are being used in practice.
In this study, we will consider the gradient descent (GD) algorithm C+47 which is based on the following deterministic recursion:
16 I T7 VR(IK, Sn), k = 0,
Here, k represents the iteration number, Th > 0 is the step-size (learning rate), and To E R is the initialization. Even though stochastic counterparts of GD (c.g., stochastic GD (BCNI8] have been more popular due to their reduced computational requirements, the GD algorithm has attracted increasing attention in the past few years, as it has been illustrated that GD can achieve similar generalization performance, as measured by the generalization error [R( - R(xx)), I as long as certain design choices are implemented 21) These design choices mainly include using large and/or oscillating learning rates and using explicit regularization of the empirical risk.
Contrary to the wisdom of optimization theory, which typically suggests using smaller learning rates, the fact that large learning rates often provide better generalization performance in modern non- convex optimization problems has opened up several research directions. In this context, [C showed that large learning rates drive the GD dynamics towards the 'edge of stability', meaning that the learning rate should be chosen large enough to make the algorithm diverge. Recently, the large learning rates have been extended to exotic learning rate schedules (i.e., non-trivial evolution of m))), such as fractal scheduling [AGZ21] and cyclic scheduling [0mm2l Smil7.
It has been shown that the use of large learning rates introduces chaotic behavior in the GD dynamies [KT20]. Hence, possible explanation for the improvements brought by large learning rates can be partially attributed to such chaotic behavior, since chaotic systems exhibit a stochastic-like evolutions (even though they are fully deterministic), which might be an underlying cause of the improvements in generalization obtained in non-convex settings. However, achieving the desired chaotic dynamics task and can be often difficult in practice.
is a
In this paper, we develop a novel optimization framework, coined multiscale perturbed gradient de- scent (MPGD), where a chaotic component is introduced to GD in a controlled manner. Our approach is based extending the GD recursion via generic regularization terms, where the regularization coefficients are modulated by using external deterministic dynamical systems that exhibit chaotic characteristics. Our main contributions are follows.
We build up on recent advances in rough paths theory and homogenization techniques GM13
CFK+1 16 CFKM200, and show that, under appropriate assumptions, the step-size decreases, the MPGD recursion converges weakly to a stochastic differential equation (SDE) driven by a heavy-tailed Lévy-stable process (Theorem 4.1 see also Theorem C. in Appendix).
We draw connections the recent theoretical links between heavy-tailed processes and generaliza- tion [SSG19 SSDEE0 HSKM21], and under certain topological regularity assumptions, we derive a generalization bound (Theorem 4.2) for the limiting SDE and relate the worst-case generalization error over its trajectories to the parameters of MPGD.
We show that MPGD exhibits a natural form of implicit regularization by deriving appropriate explicit regularizer in the weak perturbation regime (Theorem 4.3). Our analysis shows that, in this regime, the derived regularizer introduces terms that penalize the Hessian of the loss function.
We empirically demonstrate the advantages of MPGD on different settings and provide further support for the developed framework and the theory (see Section 5)
We emphasize that our primary goal is to understand the behavior of deterministic GD in chaotic setting. In this respect, we shall underline that, at this stage, our goal is not to develop a competitive algorithm that would outperform SGD, but rather to provide solid theoretical analysis for how stochastic behavior can emerge from GD with suitable deterministic components, as well as their implication in terms of generalization error.
2

---

2 Preliminaries and Technical Background
Notation. For vector IRd we denote its ith component by either o² or [u]* and the Euclidean norm by |e| (or [|v]]. diag(v) denotes the diagonal matrix with ith diagonal entry of (--)) denotes the dot product of two vectors. (d) denotes uniform distribution on d dimension, tr denotes trace, and the superscript denotes transposition. and @ denote composition and Hadamard product
respectively. V and V denote gradient and Hessian respectively. E denotes expectation. (d) and ! denote equivalence and convergence in the sense of distribution respectively. denotes the identity matrix, and IA denotes indicator function of the set A.
Stable distributions. Let a E (0, 2] be stability parameter and d 2 1. A random variable X Rd
is a-stable if X1, X2, ... are independent copies of X, then n 1/a Σソ= X, (d) X for all n 2 1 [Sam]7]. Stable distributions appear as the limiting distribution in the generalized central limit theorem (CLT) [GK54]. The case = 2 corresponds to the Gaussian distribution, while a 1 corresponds to the Cauchy distribution. The p-th moment of a stable random variable is finite if and only
Here we interested in the case a E (1, such that ||] < oc and [[ = co. If X is symmetric, then there exists a scale parameter с >> O and the characteristic function of X is given by E [exp(i({, X
(<f()) for all
R If X is random vector with independent c
E R4 and the characteristic function of components, then there exists a scale vector = (cl (cl.....c))
X is given by E [exp(i(ç, x = exp( exp(-E; ビ |c ()
Lévy processes. Lévy processes are stochastic processes (Le)120 with independent and stationary increments, and are defined as follows [App09]]
... < I,. the increments (I,, Lr, .) are independent for all i. 2. For any & >> > 0, (I,- - L.g) and Lt-, have the same distribution.
1. For N N and L <4 4 < ...
3. Ly is continuous in probability, i.e., for all 5 > 0 and s 2 0, P(LL, - Lgl > 5) - as t +
Typical examples of Lévy processes include Brownian motion and the a-stable processes. By the Lévy-Khintchinn formula, Lévy process (Le)e20 with Lo- is determined by a triplet (6, E, v) for some b Rdd Σ E Rdddd positive semi-definite and a measure on Fd \ {0} such that S240 min(1, (x(d)) < cc. The characteristic function of L, is therefore with the characteristic exponent : _Rd + defined by
(EE) = -i(b + 2 (S. ΣE> + S [1- + tixx, (|/ v(dx).
(4)
In the Lévy-Itô Itô decomposition of a Lévy process, denotes a constant drift, E is the covariance matrix of Brownian motion and v characterises a Lévy jump process, which is modified to be cådlåg (right-continuous and has left limits everywhere) with countably many jumps. In particular, if Oge. Σ = Ogaxa and v(zz) |a|] pel---ldd dx for some E (0,2), 2). then the triplet (0ge, Ogaxa, |a]| volloo dx) gives a symmetric a-stable process, denoted by (L (L2))-0-
Marcus differential equations. Passing to the limit of the driving processes with jumps in an SDE not trivial, as one needs to be careful with the meaning of integration (CP14). Unfortunately. the common Itô and Stratonovich integration (which are based on Siemann-Sticltipe sums with the
integrand evaluated the left end point and the midpoint of the partition intervals respectively) fail to provide the desired convergence. To this end, we resort to Marcus differential equations [ which in their basic form are given by:
dx, = b(X,) dL
where o denotes integration the Marcus sense. Marcus integrals involve sums over infinitely many jumps and transform under the usual laws of calculus [App09], and thus play similar role for Lévy processes as the Stratonovich integral for Brownian motion. The solution map of Mareus differential equations is continuous with respect to the driving process under certain variants of the Skorokhod topology. Note that if b(X,) is constant in X,, then there is no difference in the solutions of the SDE in the sense of Marcus, Itō and Stratonovich. We refer to Appendix B for more details these.
Generating stable laws using the Thaler map. Let == 1/a. It was shown in GG21 that a-stable laws with a E 21, can be generated using deterministic dynamical system whose states
3

---

Yh are obtained by iterating the Thaler map T [0, + [0, 1] Tha80
T(y) (1' (1+ -) 10 1)1((>>)))))))))))))))))))>))1) mod 1, yk+1 T(yk);
(5)
with any source of randommess coming solely from the initial condition yo E [0, 1]. The map has the following properties. Let yy E (0,1) be the unique solution to the equation
(w") + (1 + "²)² 2.
There are two increasing branches on the intervals [0, v/ [y"., 1]. For E [0, 1), there exists a unique invariant probability density hvy) - (y + (1 :)) Moreover, the density defines finite measure. For 7 E (0, 1). the map is nonuniformly expanding with a neutral fixed point at y 0 and correlations decay algebraically with rate 1/k (which is sharp) [GM21]. Hcuristically, the trajectory spends prolonged period of times near y (laminar dynamics near the fixed point), slowing down the decay of correlation as a decreases.
Let the observable v [0, 10 R be Hölder function with zero mean with respect to the invariant measure of T, i.e., dv = hdy,, and consider the sequence of random variables (v T (yo)) with the randomness coming from the initial state Vo- When y E (1/2, 1), the correlations summable and CLT breaks down if v0) * 0 (it "sees" the fixed point at 0). Heuristically, the Birkhoff sum Σf=u o T is ballistic with almost linear behavior æ = 0 and the small jumps of size (0) accumulate into single large jump, contradicting CLT GM21 Instead, if properly
normalized, then was shown in [Gou04] that the one-sided stable limit law L Σ T ( Xa.3 as + 0o, with 3 = sign(v(O)), holds instead, where Xa,3 denotes the stable law whose characteristic function is given by:
t[ exp((Id) i3 sign(t) tan(aT/2))).
(6)
In this paper, we focus on MPGD with chaotic components whose limiting behavior at each time
described by the class of stable laws Xa.3 whose characteristic function given by (6) with the stability parameter a E (1 (i.e., 7 E (1/2, 1)) and the skewness parameter 3 E [-1, 1]. The Xa.3
centered (i.e., EX = 0), totally skewed (or one-sided) if 3 +1, and symmetric if B =
Multiscale Perturbed Gradient Descent (MPGD)
In full generality, we start by considering the following family (parametrized by m 0) of determin- istic fast-slow dynamical systems on IR x Y, with Y a bounded metric space:
(m)
(m) + m
am (2) (m)
1 m 1/o b(9)
(5k (m²) (e (o(
2 k+1
()) yk+1
T(( i= = 1.
for h: =0,1,,, where the as (1,2), am Rdd - Rd ((0 Rd Rdxr, 03 R and
T: Y - The initial conditions Zi Yu are independent random variables. One important example of recursions of the form (7) is the GD defined in 3 Other than GD, the above family of recursions 7 includes various variants of GD as special cases upon specifying suitable choices of
(m) (4)
the am, b U; T,, and the dimensions.
Of particular interest are new algorithms that can be studied within the above framework. To this end, we introduce multiscale perturbed gradient descent (MPGD), whose dynamics are described by the following recursion:
(m) kkt
(m)
1
S. VR(x
(m))
1
U1 21(ve
(1)
(m)
02( (2)),
2
2
x
m
m
m
(8)
(1) Uk+1 = T(v
M T()) (2)
(2)
h: = 0, 1,2,
where 7 is the Thaler map with 7 = - E (1/2, the 0n 02 are observable maps, / 2 0 and IR are tunable parameters. The above recursion is of the form (7) with 9 2, ri r d.

---

600
0.75
0.50
0.25
0.00
100
300
400
100 300
400
500
-2
Figure 1: A realization of the Thaler iterates (left) and the observable (middle) for 0.6, 8 0.1. Empirical distribution of the corresponding Birkhoff sum &
Ej=o v00 with k 1000 (right).
ER
Om (z) (2( S,,,, byn (z) - diag(x), and b (x) of independent of m. Another class of algorithms that falls within this framework is when m is set to the number of training data points, in which case the empirical risk converges the population risk as m = n + 30.
To complete the description of MPGD, it remains to specify the choice for the observables u, (bk in (8) whose rescaled version can be shown to generate stable laws Xa,8, with a E (1,2) and B E 11, 1), in the limit m + co. Following [GM21], we take them to be independent realizations of the observable (,()) described as follows. Let d, a1 (1--)))((1-- cos(or/2) and d0. ó1.... be 2 independent copies of the random variable 8 where P( =1) = (1 B). The observables (A)
(0)
are then defined to be: (A))_ = (²)) I* where v [0, + R is the mean zero observable given by vyy) d 12-1) 10(0)) with
e(y) [1 21-
y S y", y > y²,
( = Xk-1 Xo E {+1} with Xy
{I if S y", 6, if y²"
In particular, the random variables x get updated only when the trajectory visits (y", 1] and are not changed during the phase in [0, y"
The initial condition can be, in theory, equally well chosen using the invariant probability measure V or the uniform Lebesgue measure. Empirically, convergence of the probability density is faster if it is drawn using v. Hence, we consider initial conditions drawn using v. Therefore, for MPGD we propagate uniformly distributed initial conditions vó E [0. under 10,000 iterations of the Thaler map and take the initial condition as Y/ = 710000 y6- Figure] 1 illlstrates the dynamics of a realization of the Thaler iterates and the observable (perturbations used in MPGD), as well as the asymmetry and heavy tail nature of the distribution of the corresponding Birkhoff sum.
Theoretical Analysis
In this section, we analyze MPGD via three differrnnt angles. We start by presenting results on superdiffusive limit (homogenization (PS08) for class of fast-slow deterministic systems that include MPGD special case in Subsection 4.1 We then study generalization properties of MPGD by deriving generalization bound for the limiting dynamics in Subsection 4.2 Lastly, we study the regularizing effects of MPGD via the lens of implicit regularization in Subsection 4.3
4.1 Superdiffusive Limits for the Fast-Slow Systems and MPGD
Without loss of generality, we set q = in 7 and consider the following family of recursions:
m am (m) 3k++1 = T())),
(m)) (m)
) + m (x (m) )o(s))
k+1 xx
where T is the Thaler map and v is the observable constructed Section
The following result shows that stochastic dynamics emerges in the above family of deterministic dynamical systems in the limit m - co. Moreover, the limiting dynamics are described by a stochastic differential equation (SDE) driven by heavy-tailed Lévy-stable process.
Theorem 4.1 (Superdiffusive Limit Informal), Let a E (1, and assume that the coefficients am- bm and the initial condition 20 (m)
well-behaved - Then, under certain regularity
5

---

conditions on the Omm Ums the process (1r (mm)) [mm))120 1120 converges in distribution to the solution (X1) of the SDE:
dx; xXx==(Xx)dd) a(X,)dl b(Xx) ... with Xg Io E R
as 0o, where lim am, b b= lim bm To zo= lim (mm denotes the Marcus integration. defined in Section B.2.1 and (L.")))2 ):20 is a Lévy process with the characteristic exponent
(E( ( - i sig tan((rt/2),
(10)
( to X, at fixed t. It is a special case of Theorem C. which covers a large class of the maps T and observables v, and extends the
In particular, Theorem
4.1 implies convergence in distribution of (m)
results in [GM21 CFKM20 to the case where the coefficients are dependent on m. We provide
technical details on the topology used for the convergence and the proof in Appendix B
Specializing Theorem 4.1 (extended the case of q 2) to the MPGD recursion rescaled MPGD iterate process, (xr (m) following SDE:
we see that the
[mm] ):20. converges in distribution to the solution (Xz)r20 of the
(m) dx, - VR(X, dd - diagi (X) dll," 1 + rodT....9 No = lim T0
m=+00
in the limit m + oo, which is equivalent to sending the step-size, n= := 1/m, in the MPGD to zero.
Here (L, (L 120 and 1] are the parameters appearing in the construction of the observables e1 and U2 respectively. Therefore, we see that MPGD converges to gradient flow driven by heavy-tailed stvyls processes in the considered scaling limit. The driving processes contain both additive and multiplicative components. The multiplicative component can be interpreted dynamical version of the weight decay, whereas the additive component can be viewed as gradient noise 1
are independent Lévy processes with characteristic exponent (10)
and B1. B2 E [1
4.2 Generalization Properties of MPGD
In this section, we shift our focus to the generalization properties of MPGD. Our main roadmap will be consider the limiting SDE arising from Theorem 4.1 (with 3 0) and relate it to the recently
developed generalization bounds for heavy-tailed random processes (SSDE20 HSKM21].
For mathematical convenience, we consider the following special case of 7
(12)
(m))
m am (x
(m) + m -- bm (mm) (u(v(2) (1) v(yl)))
1++1
I,k
(11)
(1)
Mh41 T(yk) (2))
Mk+1
In the light of Theorem 4.1 the recursion converges weakly to the following SDE:
dX, d( 6(X,) dL
(12)
where LE denotes the symmetric a-stable process in Rd (i.e., 0).
Following the previous work [SDE22 HSKM211. we are interested in bounding the worst-case generalization error over the trajectories of (1)) More precisely, let (Xe)agigı denote the solution of T2 and define the set X' that it contains all the points visited by the trajectory:
X = (x Rd Et [0, 1], x).
(13)
Then, our goal is to analyze sup=ex RZ, S.) R(x)). Since we are mainly interested in the case when a(x) vR(x,, (,,x,,)),, S,),, the SDE 12 and hence the trajectory X' will depend the dataset Sn, Therefore, in the generalization bound, we will need to control the statistical dependence of X' on Sn, through the notion of p-mutual information, defined as follows. Let X, Y.Y be two random elements, let Px,y denote their joint distribution, and let P Px, Iy denote their respective marginal distributions. Then the m-mutaal information between X and Y is defined as: T,(X, Y) (P x,y |Px x Pyy),
I We believe a similar result would hold for g without symmetrization, which we leave for future work. Here, the range [0, 1] is arbitrary and could be replaced with any range [0, T] for 0 < T < co.

---

where Dp is the p-Renyi divergence
Dp(n, v) p-1 log (Z) dx (Z) and
du dx
du denotes aA
the Radon- Radon-Nikodym derivative.
Finally, require technical regularity assumptions (Assumptions and given in Appendix D for our generalization bound. Informally, Assumption is topological regularity condition over the trajectory X, whereas Assumption 3 a statistical regularity assumption and imposes that in the neighborhood of local minimum x* of R(x, S.). the statistical behavior of the process X₃ can be approximated by the process solving the SDE dX,; b(x*) od.. This requires to regular the neighborhood of x" and further imposes that a(x*) = O, which natural when azx) = (R( S,). We now ready to present our generalization bound.
Theorem 4.2 (Generalization bound). Assume that Assumptions 2andd
3 given in Section D hold, and that & bounded by B > 0 and L-Lipschitz continuous. There exists a constant K₁ > such that with probability at least - 6,
suPnex Sx) - R(x) S Ki m, (Va
log(1/0) + Lo0 (Sr, 2)
(14)
n
where Loc (X == limp- Y), Furthermore, there exists K2 0 such that
(
(t; n2
Esupaex RR(,, S.)) R(x)) S K2 max max{BB L)
V +
(15)
This result shows that the generalization error is mainly bounded by two terms: the tail exponent of the limiting Lévy process Li, and the statistical dependence of X' on S,, The bound suggests that, provided the mutual information between X' and S, is fixed, the generalization error be reduced by using a smaller a in MPGD. However, it has been illustrated that a smaller a can induce significant error on R(x, S,,) [SZTG20) 21 hence a reasonable value of a should be chosen to balance both the empirical risk and the generalization error. The algorithm parameters p. interact with the bound via the constant terms K1, K2 and the mutual information terms /1, Inx- Unfortunately, their dependence quite implicit and we not able provide quantitative estimations.
Finally, the main difference between Theorem 4.2 and [$SDE20] H$KM2I] is that, in our bounds we have explicit access to the characteristic exponent of L; since construct it manually through our dynamics; whereas in the prior work generic processes were used as approximations for SGD, hence their results not explicit.
4.3 Implicit Regularization of MPGD
To understand MPGD and its connection to the vanilla GD 33 better, we provide additional analysis for the behavior of loss functions optimized under the recursion (8) via the lens of implicit regu- larization [Mah 12, LEHM21]. By this, we mean regularization imposed implicitly by the learning strategy, without explicitly modifying the loss. We shall achieve this by deriving an appropriate explicit regularizer through a perturbation analysis in the weak perturbation regime.
To this end, work in the regime where the parameters μr, small, keeping m fixed. We set = Mac and σ = dge, where e > 0 a small parameter, and analyze the loss optimized using the recursion in the small regime. In the sequel, we let
I((m) denote the states of the unperturbed (m) (m) 1 R(a
GD, satisfying the recursion J h++1 shall denote R(x) = R(x,, S.).
(m) Sn), for l = 0, 0,1, 1,..... To simplify notation,
The following result relates the loss function, averaged over realizations of the injected perturbations, evolved under training with MPGD to that of unperturbed GD in the weak perturbation regime.
Theorem 4.3 (Implicit regularization). Let > 0, & E N, and Sn be given. Assume that = 1 and r2 in Eq. (8), and Elv, (y1 () = Elvz(Vi (2) ) = 0 for all Then, for a scalar-valued loss function R2 with VR having Lipschitz continuous partial derivatives in each coordinate up to order
As 1. Do tends the Bullback-Leible divergence.
7

---

three (inclusive),
&
-R(
(tr
(ct
- )( + O
(16)
2
as E + where the expectation with respect to the realization of the y the Xmm) are the vector with the lth component:
1
d $ t (c--) V V
the (m())
}), with the empty product taken be the identity, and the
cl are covariance matrices with the (p. entryy of En Ed
Dr.e= ( (m)pp
pap i2 21.
where
((m)
Hg Bi (Wi, (2) Do ( [ [x
(m))
(2) Ellve] (Mi, [ (yiz .)
11,22, m2/01
2/02
Theorem 4.3 implies that the loss function optimized under MPGD at given iteration and m is, on average, approximately equivalent to a regularized objective functional. Moreover,
VR(T (/m)) CLT) ( (
C. for some constant C' independent of m, suggesting that the trace term
is the dominant explicit regularizer for large m. This explicit regularizer is solely determined by the discrete-time flow generated by the Jacobians I V ()))) ), the covariances clm), and the Hessian of the loss function, all evaluated along the dynamics of the unperturbed GD. We can therefore expect the use of the perturbations in MPGD
regularization mechanism should reduce the Hessian of the loss function according to the perturbation levels (No, oo) and the correlations [)] 1. E[ 022 (vl 00 (v/=- (2) )}. Reducing the Hessian of the loss func- tion can lead to flatter minima in the loss landscape, which widely believed to associate with better
0, Blu1 (y,
(1) )ee (m/2"))
generalization in deep learning KKNN* 16 JNM 19).
Lastly, we observe that in the weak perturbation regime and for non-convex losses, MPGD is more beneficial than GD in the sense that it reduces the Hessian of the loss, thereby promoting flatter minima. Hence, in order to observe the benefits of our scheme, we suspect that the optimization problem should be non-convex and local minima should have different curvatures.
5 Empirical Results
In this section, we illustrate the advantages of MPGD compared other schemes on the tasks of (1) minimizing the widening valley loss, (2) regression on the Airfoil Self-Noise Dataset, and (3) classification CIFAR-I0. We also provide additional results and details in Appendix FF]
5.1 Minimizing the Widening Valley Loss
We consider the problem of minimizing the widening valley loss, given by E(u, v) u u/|[uu] The gradient of is given by V u) = (2²u, [/]](r)), and the trace of the Hessian is du² + ||]l where is the dimension of u. The trace of the Hessian measures the flatness of the minima, which is monotonously changing in this case. The loss has valley of minima with zero loss for all (u, v) with v The smaller the norm of u, the flatter the minimum. Vanilla GD gets stuck when first enters this valley, and the intuition is that injecting suitable perturbations should help convergence to flat (with small [|u])) part of the valley. All (u, v) with v = are minima, but we also need ||//|| to be minimized in order to minimize the trace of the Hessian. In high dimension (large d), the GD path is biased towards making v small and not optimizing u since the direction along v is the most curved.
For the experiments, we start optimizing from the point (up, 0), where un 5 ((d( with d = 10, and use the learning rate 7) = 0.01. We study and compare the behavior of the following schemes: (i) baseline (vanilla GD), (ii) GD with uncorrelated Gaussian noise injection instead, and (iii) MPGD. Figure demonstrates that MPGD can lead to successful optimization of the widening loss whereas the baseline GD and GD with Gaussian perturbations lead to poor solutions. This is in agreement with our analysis of implicit regularization for MPGD, showing that the injected perturbations effectively favor small trace of the loss Hessian, thereby biasing the solution to flatter region of the loss landscape.
8

---

500
Dase 106
8003
usden
R380
5258
bost
22003
2033
7500
25000
300
1800
2000
200
33000
100
10.0 153
4000
6000
Figure 2: Evolution of GD with Gaussian perturbations (left plot) vs. that of MPGD with = 0.7. 3 3 0.5 (middle plot). using μ 0.02, = 0.05, and 17 = 0.01 (m 100). Here we see that MPGD leads to successful optimization of the widening valley loss whereas that with Gaussian perturbations fails to converge. Moreover, MPGD effectively reduces the trace of loss Hessian (see right plot), steering the GD iterates to flatter region of the loss landscape.
5.2 Airfoil Self-Noise Prediction
Table Shallow neural nets trained on the airfoil data set. The results in parenthesis are achieved with the variant (T]) All the results are averaged
We consider the Airfoil Self-Noise Dataset [GG77 from the UCI repository. It comprises of differently sized airfoils various wind tunnel speeds and angles of attack. This is a regression problem aiming to predict scaled sound pres- sure level, in decibels, of the airfoil based on the the features: frequency, angle of attack, chord length, free-stream velocity, and suction side displacement thickness. We use 1202 samples for training and 301 samples for testing.
over 5 models trained with different seed values.
Scheme
test RMSE
RMSE gap
Baseline
0,4309
0.2411
Gaussian
0,4279
0.2354
MPGD, 0.55
0.3916 (0,3865)
0.2256 (0.2305)
MPGD. 7 -0.6
0,3810 (0.4092)
0.2298 (0.2206)
MPGD. 7 = 0..5
0.3829 (0.3891)
0.2407 (0.2307)
MPGD, 7 = 0.7
0.4600 (0.3754)
0.2315 (0.2311)
For the training, we use a fully connected shal- low neural network of width 16 with ReLUU activation and train for 3000 epochs with the learning rate 77 0.1, using mean square error (MSE) as the loss and choosing 3 0.5. Table D reports the average root MSE (RMSE) and the RMSE gap (defined as test RMSE train RMSE) evaluated for models that are trained with different seed values for this task. We can see that MPGD leads to both lower test RMSE and RMSE gap when compared with vanilla GD (baseline) and GD with uncorrelated Gaussian perturbations (see the results not in parenthesis in Table T here μ 0.01, = 0.02). Using the form of the perturbations in (IT) instead can also give lower RMSE gap (see the results in parenthesis in Table [] here a = μ 0.01). Overall these results support our generalization theory for MPGD. Lastly, we note that using larger values of y naively does not guarantee better test performance: one has to fine tune the parameters 3, μr, a, !/ appropriately to achieve favorable trade-off between training stability and test performance.
5.3 CIFAR-10 Classification
We consider training a ResNet- 18 classifier [HZRS16] on the CIFAR-10 data set [Kri09] We follow the setup used in +1], where a 18 trained using batch size of 50K (the entire training dataset). As in (GL++11), we consider standard ResNet-18 with the parameters in the linear layer randomly initialized and the parameters in the batch normalization initialized with mean zero and unit variance, except for the last in each residual branch which is initialized to zero. The default random CIFAR-10 10 data ordering is kept as is, and every image is randomly augmented by horizontal flips and random crops after padding by 4 pixels.
Using the setup of [GGP+21), the reference mini-batch SGD is trained using a batch size of 128 (sampling without replacement), Nesterov momentum of 0.9 and weight decay of 0.0005. The learning rate warmed up from 0.0 to 0.1 over the first epochs and then reduced via cosine update
annealing to 0 over the course of training for 300 epochs (resulting in 390x300=117.00 steps). The validation accuracy obtained in [GGP=21 is 95.7%. For the full-batch GDs, we replace the mini-batch updates by full batches and accumulate the gradients over all mini-batches. For the Gaussian scheme and MPGD, we inject the perturbations into the GD recursion for parameters of the input layer of ResNet-18. 18, choosing μ 0.03, 0.01 and B 0.5 (for MPGD). In our experiments,

---

Table 2: ResNet-18 trained on CIFAR-10 for 1000 epochs. Here, accuracy gap training accuracy validation accuracy. The results in parenthesis are achieved with the variant of MPGD (1).. All the results are averaged over 5 models trained with different seed values.
Scheme
val. accuracy in accuracy gap
Baseline full batch GD
73.10
8.99
Gaussian
70.58
8.53
MPGD, 0.55
75.97 (74.51)
6.08 (6.58)
MPGD. 0.6
75.78 (74.60)
5.64 (6.15)
MPGD. 7 0.65
74.39 (72.96)
6.41 (6.85)
MPGD. 7 U.7
73.72 (73.27)
6.69 (6.04)
we fix the learning rate to 0.1 throughout training, and do not add momentum and weight decay. This is in constrast to (GGP*211 21), where the additional tricks applied in the mini-batch SGD are also used for the full-batch GD, leading to higher test accuracies (see Table 2 in [GGP 21)).
Table that MPGD can lead to better test performance and lower accuracy gap when compared to the baseline (full batch GD) and Gaussian noise-perturber GD. Using the perturbations in (IT) instead can also achieve lower accuracy gap. Therefore, adding perturbations of MPGD can be potentially a useful trick improve training of deep architectures on benchmark data sets. Lastly, we note that additional tricks, such as gradient clipping and tuning of optimization hyperparameters, can be applied to improve our test accuracies and close the gap to results obtained with the reference mini-batch SGD. However, our main focus here is not competitive performance, but rather on demonstrating the effects of the perturbations in MPGD when compared to full batch GDs and Gaussian perturee full-batch GD to support our theory.
Lastly, we remark that we did not tune the step-size for any of the algorithms. Since our generalization bound applies to the asymptotic SDE, which is obtained when the step-size goes to zero, in order to stay close to the theory, we chose a small enough step-size to be both not far from the continuous dynamics, and large-enough so that the algorithm converges in a reasonable amount of time. That being said, we have tried a range of step-sizes for both algorithms, and we observed that the proposed scheme consistently outperforms vanilla GD for smaller step-sizes. Whereas if we use large step- size, both algorithms perform similarly. In this regime, vanilla GD as well potentially emits a chaotic behavior, which might also indicate the importance of the "implicit randomness". However, as we indicated in the introduction, this regime is not easily controllable, and our purpose is to introduce a controlled chaotic component, with clear theoretical understanding.
6 Conclusion
In this paper, we introduce and study a class of slow-fast deterministic dynamical systems which homogenize to limiting SDE driven by heavy-tailed Lévy-stable process in an appropriate scaling limit as a rigorous framework for perturbed GDs. Within this framework, we introduce MPGD, novel version of perturbed GD, which we show to have good generalization and regularization properties. We further demonstrate the advantages of MPGD empirically in various optimization tasks. Our framework can provide useful tools for identifying implicit randomness in deterministic optimization algorithms and inspire other promising algorithms. It would be interesting to investigate the interactions of the chaotic perturbations in MPGD with the noise arising from mini-batel sampling in SGD [WH and other optimization tricks. Since this is a theoretical paper studying a framework for perturbed GDs, there are no potential negative societal impacts of our work.
Acknowledgements. We are grateful to the computational resources provided by the Swedish National Infrastructure for Computing (SNIC) at Chalmers Centre for Computational Science and Engineering (C3SE) partially funded by the Swedish Research Council through grant agreement no. 201 2018-05973. H. Lim would like to acknowledge the WINQ Fellowship, the SNIC AI/ML grant, and the Swedish Research Council (VR/2021 1 103648) for providing support of this work. U. Ş.' research was funded in part by the French government under management of Agence Nationale de la Recherche part of the "Investissements d' "'avenir" program, reference ANR- 18--199--A--000 (PRAIRIE 31A Institute), and the European Research Council Starting Grant DYNASTY 101039676.
10

---

References
[AGZ21] Naman Agarwal, Surbhi Goel, and Cyril Zhang. Acceleration via fractal learning rate schedules. arXiv preprint urXiv:2103.01335 2021.
[App09] David Applebaum. Lévy Processes and Stochastic Calculus. Cambridge University Press, 2009.
[BCN18] Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 6012):223-11,, 2018.
[C] Augustin Cauchy et al. Méthode générale pour la résolution des systemes d' d'équations simultanécs. Comp, Rend. Sci. Paris, 25(1847):536-33 538, 1847.
[CFK 16] Ilya Chevyrev, Peter K Friz, Alexey Korepanov, Ian Melbourne, and Huilin Zhang, Multiscale systems, homogenization, and rough paths. In International Conference in Honor of the 75th Birthday of SRS Varadhan, pages 17-48. Springer, 2016.
[CFKM20] Ilya Chevyrev, Peter K Friz, Alexey Korepanov, and Ian Melbourne. Superdiffusive limits for deterministic fast-slow dynamical systems. Probability Theory and Related Fields, 178(3)735-777, 2020.
[CKL-22 21] Jeremy M Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In ICLR, 2021.
[CP14] Alexei Chechkin and Ilya Pavlyukevich. Marcus versus Stratonovich for systems with jump noise. Journal Physics A: Mathematical and Theoretical, 47(34):34200,, 2014.
[CWZ-21] Alexander Camuto. Xiaoyu Wang, Lingjiong Zhu, Chris Holmes, Mert Gürbüzbalaban, and Umut Şimşekli. Asymmetric heavy tails and implicit bias in Gaussian noise injections. arXiv preprint 0rXiv:2102.07006 2021.
[DG17] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[FV10] Peter K. Friz and Nicolas B. Victoir. Multidimenssonal Stochostic Processes as Rough Paths: Theory and Applications. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2010.
[GAG]OR 00] Ary L. Goldberger, Luis AN Amaral, Leon Glass, Jeffrey M Hausdorff, Plamen Ch Ivanov, Roger G Mark, Joseph E Mietus, George B Moody, Chung- Kaang-Kang Peng, and H Eugene Stanley. PhysioBank, PhysioToolkit, and PhysioNet: components of new research resource complex physiologic signals. Circulation, 101(23):e215 e220, 2000.
[GGP 21] Jonas Geiping. Micah Goldblum, Phillip E Pope, Michael Moeller, and Tom Goldstein. Stochastic training is not necessary for generalization. arXiv preprint 1rXiv:2109.1 14119, 2021.
[GK54] Boris Vladimirovich Guedenko and Andrey Nikolaevich Kolmogorov. Limit Distributions for Sums of Independent Random Variables. Cambridge, Addison Wesley, 1954.
[GM13] Georg A Gottwald and Ian Melboume. Homogenization for deterministic maps and multiplicative noise. Proceedings of the Royal Sociery Mathematical, Physical and Engineering Sciences, 469(2156):20 30201,, 2013.
[GM21] Georg Gottwald and Ian Melhourne. Simulation non-Lipschitz stochastic differential equations driven by o-stable noise: A method hased on deterministic homogenization. Multiscale Modeling & Simulation, 19(2):665-68) 6876 2021.
[Gou04] Sébastien Gouëzel. Central limit theorem and stable laws for intermittent maps. Probability Theory and Related Fields, 128 2004.
[HşKM21] Liam Hodgkinson, Umut Şimşekli, Rajiv Khanna, and Michael W Mahoney, Generalization properties of stochastic optimizers via trajectory analysis. arXiv preprint arXiv:2108.0077 2021.
[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages
2016.
[NM 19] Yiding Jiang. Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where find them. arXiv preprint arXiv:1912.02178. 2019,

---

[KMN- 16] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy. and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 1rXiv:1609.04888 2016.
[Kri09] Alex Krizhevsky, Learning multiple layers of features from tiny images. 2009.
[KT20] Lingkai Kong and Molci Tao. Stochasticity of deterministic gradient descent: Large learning rate for multiscale objective function, Advances in Neural Information Processing Systems, 33:2625-2638,, 2020.
[LEHM2I] Soon Hoe Lim, N Benjamin Erichson, Liam Hodgkinson, and Michael W Mahoney. Noisy recurrent neural networks, Advances in Neural Information Processing Systems, 34, 2021.
[Mah12] M. W. Mahoney, Approximate computation and implicit regularization for very large-scale data analysis. In Proceedings of the 31st ACM Symposium on Principles of Dutabase Systems, pages 143-154, 2012.
[Mar81] Steven I Marcus. Modeling and approximation of stochastic differential equations driven by semimartingales. Stochastics: An International Journal of Probability and Stochastic Processes, 4(3):223- 2252 1981.
[NVL 15] Arvind Neclakantan, Luke Vilnis, Quoc V Le. llya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv:1511.0660 2015.
[0ym21] Samet Oymak. Provable super-convergence with large cyclical learning rate. IEEE Signal Processing Letters, 28: 1644, 2021.
[PSO8] Grigoris Pavliotis and Andrew Stuart. Multiscale Methods: Averaging and Homogenization. Springer Science& & Business Media, 2008.
[Sam17] G. Samoradnitsky. Stable Non-Gaussian Random Processes: Stochastic Models with Infinite Variance. CRC Press, 2017.
[Sch98a] René L Schilling. Feller processes generated by pseudo-differentaal operators: On the Hausdorff' dimension of their sample paths. Journal of Theoretical Probability. 11(2):303-330, 1998.
[Sch98b] Réné.L. Schilling. Conservativeness of semigroups generated by pscudo differntial operators. Potential Analysis, 9:91-104, 1998.
[Smi17] Leslic N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 464-472. IEBE, 2017.
[$SDE20] Umut Şimçekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. arXiv preprint 2XXX::20060033133 2020.
[SSG19] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827-5837. PMLR, 2019.
[SZTG20] Umut Simsekli, Lingjiong Zhu, Yee Whye Teh, and Mert Gurbuzbalaban. Fractional underdamped Langevin dynamics: Retargeting SGD with momentum under heavy-tailed gradient noise. In International Conference on Machine Learning, pages 8970-8980. PMLR, 2020.
[Tha80] Maximilian Thaler. Estimates of the invariant densities of endomorphisms with indifferent fixed points. Israet Journal of Mathematics, 37(4):303-31 314, 1980.
[WHX 20] Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing 7hu. On the noisy gradient descent that generalizes SGD. In International Conference on Machine Learning, pages 10367-10376. PMI.R 2020.
[You36] L. C. Young. An inequality of the Hölder type, connected with Stieltjes integration. Acta Mathematica, 67(none):251 -822, 1936.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We pointed out in Conclusion that our results only cover the setting of full-batch gradient descent, leaving the studies for the more challenging case of mini-batch SGD. We also do not study the interactions of the chaotic perturbations MPGD with other optimization tricks such as gradient clipping and adding momentum.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix for all the proofs and details.
3. If you ran experiments...
(a) Did you include the code. data, and instructions needed reproduce the main perimental results (either in the supplemental material or as a URL.)? [Yes] See the Appendix for such details.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g.. with respect the random seed after running experi- ments multiple times)? [Yes] We leave out such details the main paper due to page constraints, and report them in the appendix instead.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "wwlUh7eUu4u", "reviewer": "Reviewer_AQWb", "summary": "This paper proposes a modified gradient descent algorithm by adding a chaotic component in the algorithm in a careful manner. The authors relate the algorithm to its SDE limit with a heavy-tailed Levy process when the step size goes to zero, and derive its generalization error bound. They also show that the chaotic term has a desired regularization effect that penalizes the Hession matrix, which is then illustrated by empirics.", "questions": "1. For the generalization bound, does the propose algorithm benefit or loose anything, in terms of convergence rate, when the loss function is convex or strongly convex? \n\n2. Does the algorithm parameters, $\\mu$, $\\sigma$ play an role in the generalization bound? In either case, it is worth discussion.\n\n3. Besides the numerical experiments, can you provide some qualitative result that identify regimes where the proposed algorithm chaotic regularized GD works better than GD?\n\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n1. This is a well-written paper. Although I am not an expert in this field, I enjoy reading the paper. The main message is clear, and the authors pay close attention to mathematical rigor.\n\n2. The paper proposes a new variant of gradient descent algorithm and provides a comprehensive analysis on its SDE limit, the generalization bound and the regularization effect, and also demonstrate via numerical experiments.\n\n**Weakness**\n\n1. The paper contains a lot of technical results to me. Its readability may be improved by supporting some specialized examples and contrast with vanilla Gradient Descent.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e5dobeS0TZ0", "reviewer": "Reviewer_Za8N", "summary": "Stochastic gradient descent often generalizes better than deterministic gradient descent.  Motivated by the intuition that _chaotic_ deterministic systems act like stochastic systems, this paper proposes to train neural networks using a chaotic version of deterministic gradient descent.  In particular, the idea is to inject perturbations at each step which are driven by a chaotic dynamical process.  The authors argue that this approach may help deterministic gradient descent generalize better.\n\nTheoretically, the authors:\n 1. prove a generalization bound for their method that leverages recent generalization bounds for heavy-tailed SGD\n 2. prove that their method approximately follows gradient flow on a regularized loss functional which implicitly penalizes the Hessian trace.  \n\nEmpirically, the authors:\n1. Demonstrate that on a toy problem (the \"widening valley\"), their method finds a flat minimum even though gradient descent with a small learning rate finds the sharp minimum that it was initialized near.\n2.  Demonstrate that on a UCI regression problem, there exists a hyperparameter setting for their method (which has three hyperparameters)  and a corresponding hyperparameter setting for deterministic gradient descent (which has one parameter, the step size) where their method achieves lower RMSE than deterministic gradient descent.\n3.  Demonstrate that on CIFAR-10 classification with a ResNet-18, there exists a hyperparameter setting for their method (which has three hyperparameters) and a corresponding hyperparameter setting for deterministic gradient descent (which has one hyperparameter, the step size) for which their method achieves better test accuracy than deterministic gradient descent.\n", "questions": "If you tune the step size for the baseline of deterministic GD, does the proposed method still work better?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I don't understand most of the theory in this paper, and I will leave evaluation of the theory to the other reviewers.\n\nRegarding the impact on deep learning practice, \n 1. I am not convinced that the method actually does robustly generalize better than full-batch gradient descent.  It does not seem that the authors have tuned the step size for the gradient descent baseline, whereas the authors _have_ tuned the three hyperparameters for their method.  If one tunes the hyperparameters for both methods on a validation set and evaluates the performance of the optimal hyperparameters on a separate test set, does the proposed method actually generalize better than deterministic GD?\n 2. to whatever extent the method does robustly generalize better than full-batch gradient descent, I would be surprised if this is explained by the theory in the paper.  Concretely, I would wager that there are a huge number of schemes for injecting perturbations into gradient descent for which one can get a small boost in test accuracy.  I have a hard time believing that the fact that this particular scheme \"homogenizes to a limiting SDE driven by a heavy-tailed Levy stable process\" is relevant.  Note that the overall message of the Geiping et al paper is that there is nothing special about randomness that promotes generalization.  Do the authors agree with that message?   Please correct me if I am wrong, but the premise of this submission seems to be that there is something special about randomness that promotes good generalization, and that this magic can be mimicked by injecting chaos into the algorithm, since chaos $\\approx$ randomness.\n\nMinor point: in motivating this study, the authors write in their introduction\n> Contrary to the wisdom of optimization theory, which typically suggests using smaller learning rates, the fact that large learning rates often provide better generalization performance in modern nonconvex optimization problems has opened up several research directions. In this context, [CKL+21]  showed that large learning rates drive the GD dynamics towards the ‘edge of stability’, meaning that the learning rate should be chosen large enough to make the algorithm diverge.\n\nThe paper CKL+21 is not about generalization or large learning rates.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "anF7o11KgYB", "reviewer": "Reviewer_TqfM", "summary": "This paper introduces a multiscale perturbed gradient descent (MPGD) framework for global optimization, which aims to improve the generalization ability of the resulting predictive model. ", "questions": "1. What is advantage of the proposed method compared to SGD?   It seems that the proposed method works with full data at each iteration, which can be much slower than SGD. \n\n2. The performance of the proposed method is not clearly illustrated. The SGD and some regularized SGD algorithms should be used as the baseline in numerical experiments. ", "limitations": "Yes. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theoretical result makes sense to me, although I did not check the proof carefully.  Compared to stochastic gradient descent (SGD), the advantage of the proposed method is not clearly addressed. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "154PBnixGoK", "reviewer": "Reviewer_bLX6", "summary": "The paper considers a family of deterministic fast-slow dynamical systems. This family includes GD and some of its variants and the MPGD algorithm the authors introduce. The authors show that, as the learning rate vanishes, the MDGD dynamics converge weakly to an SDE driven by a heavy-tailed Levy stable process. Then, the authors derive a generalization bound for this limiting SDE for the symmetrical case. Finally, the authors analyze the implicit bias induced by these dynamics and show that, in a weak perturbation regime, it penalizes the Hessian of the loss function. These theoretical results are demonstrated empirically.", "questions": "Following my remark in the previous section, can you please elaborate on the different assumptions needed for the different theorems? ", "limitations": "The authors mentioned some of the limitations of their results.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\nThe paper is clear and well written, and it establishes several interesting results, detailed above. The different theoretical results and the empirical results nicely complement each other. In addition, I believe that the framework the authors suggested might be used to analyze other optimization methods. \n\n*Weaknesses:* \nA lot of the main assumptions for the different Theorems only appear in the appendix and without justification or explanation. While I understand this is probably due to space constraints, this makes it hard to evaluate how general or reasonable the assumptions are and the limitations of the results.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept