On the Theoretical Properties of Noise Correlation in Stochastic Optimization
Authors: Aurelien Lucchi
Frank Proske
Antonio Orvieto
Francis Bach
Hans Kersting
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic Optimization
Fractional Brownian Motion
Noise injection

Abstract: Studying the properties of stochastic noise to optimize complex non-convex functions has been an active area of research in the field of machine learning. Prior work~\citep{zhou2019pgd, wei2019noise} has shown that the noise of stochastic gradient descent improves optimization by overcoming undesirable obstacles in the landscape. Moreover, injecting artificial Gaussian noise has become a popular idea to quickly escape saddle points. 
Indeed, in the absence of reliable gradient information, the noise is used to explore the landscape, but it is unclear what type of noise is optimal in terms of exploration ability. In order to narrow this gap in our knowledge, we study a general type of continuous-time non-Markovian process, based on fractional Brownian motion, that allows for the increments of the process to be correlated. This generalizes processes based on Brownian motion, such as the Ornstein-Uhlenbeck process. We demonstrate how to discretize such processes which gives rise to the new algorithm ``fPGD''. This method is a generalization of the known algorithms PGD and Anti-PGD~\citep{orvieto2022anti}. We study the properties of fPGD both theoretically and empirically, demonstrating that it possesses  exploration abilities that, in some cases, are favorable over PGD and Anti-PGD. These results open the field to novel ways to exploit noise for training machine learning models.

On the Theoretical Properties of Noise Correlation in Stochastic Optimization
Aurelien Lucchi"
Frank Proske"
Department of Mathematics & Computer Science University of Basel, Basel, Switzerland.
Department of Mathematics University of Oslo, Oslo, Norway.
Antonio Orvieto
Francis Bach
Department of Computer Science ETH Zürich, Zürich, Switzerland.
Inria, Ecole Normale Supérieure
PSL Research University, Paris, France.
Hans Kersting
Inria, Ecole Normale Supérieure
PSL Research University, Paris, France.
Abstract
Studying the properties of stochastic noise to optimize complex non-convex func- tions has been active area of research in the field of machine learning. Prior work [55] 500 has shown that the noise of stochastic gradient descent improves optimization by overcoming undesirable obstacles in the landscape. Moreover, injecting artificial Gaussian noise has become a popular idea to quickly escape saddle points. Indeed, in the absence of reliable gradient information, the noise is used to explore the landscape, but it is unclear what type of noise is optimal in terms exploration ability. In order narrow this gap in our knowledge, we study a general type of continuous-time non-Markovian process, based on fractional Brow- nian motion, that allows for the increments of the process be correlated. This generalizes processes based on Brownian motion, such as the Ornstein- Uhlenbbeck process. We demonstrate how discretize such processes which gives rise to the new algorithm "fPGD". This method is generalization of the known algorithms PGD and Anti- BG We study the properties of fPGD both theoretically and empirically, demonstrating that it possesses exploration abilities that, in some cases, are favorable over PGD and Anti-PGD. These results open the field novel ways to exploit noise for training machine learning models.
Introduction
Injecting random noise to the parameters of a function has been a commonly used technique in optimization, dating back to at least 31 2. More recently, [2] demonstrated the empirical benefits of injecting Gaussian noise (a.k.a. Brownian motion noise) to the gradients while training deep networks. Injecting Gaussian noise has also been common technique used to show faster escape from saddle points [15]. Importantly, the noise of the optimizer also has an effect on the type of minima that can be reached, raising some important connections to flatness and generalization properties [24] A distinetive property of noise is its exploration ability which is crucial when the gradient of the objective function is not reliable, either due to saddles, valleys, plateaus, local minima. Despite a large body of work debating the distribution of the intrinsic noise of stochastic
Shared first authorship. Correspondence: Aurelien.lucchie unibas.ch, proske @ math. nio.no.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

gradient descent (SGD)
[3]. there is large gap in our knowledge regarding the role of noise to escape undesirable regions.
54 46
In order to address this question, we investigate the behavior of a general type of non-Markovian stochastic process known fractional Brownian motion (fBM). The latter is generalization of Brownian motion where the increments need not be independent but can instead be positively or negatively correlated. Interestingly, the processes that can be constructed from IBM recover known instances in the literature, including perturbed gradient descent (PGD) 555 22 and anticorrelated PGD (Anti-PGD) 36 37]. As we will see, the correlation between increments has a drastic effect of the behavior of the optimizer, and neither PGD or Anti-PGD are optimal in all cases.
Contribution. The first question we address is what is the effect of the noise correlation on the overall magnitude of the process and its ability to explore the landscape? In many applications, this is typically captured by ensuring a uniform control on the evolution the random process. This can be achieved by bounding its expected supremum, which is connected to the concept of exit time, see Rmk. 2 To conduct such an analysis. we will consider a well-known type of continuous time stochastic process with drift known the fractional
Uhteeene-hhleebeekkkkk (fOU) process, which is connected to SGD (see Section 3) We will also demonstrate how to discretize such a process to obtain practical optimization algorithm that we name fPGI) (for fractional PGD). Concretely, our main result will be to provide upper and lower bounds on the expected supremum of the fOU process. These bounds will give a precise characterization of the effect of the noise correlation on the magnitude of the process, Second, we experimentally investigate the practical behavior of fBM noise injection: In Section 5 we demonstrate that fBM perturbations indeed help optimizers to move faster from one local minimum to another as suggested by our theory. In Section 5.2, we demonstrate the existence of an optimization problem where non- Mar-ooaoova versions of fPGD indeed outperform the known Markovian special cases (PGD and Anti-PGD) first proof-of proof-of-concepp oo-coneept for the practical utility of Markkanoo noise injection.
2 Related work
Non-Markovian stochastic processes. The vast majority of the work done in stochastic opti- mization for machine learning focuses on Markovian processes. Yet, non-Markovian processes are known to appear naturally in many situations. They for instance describe the widths of consecutive annual rings of a tree the values of the log return of a stock [6] In this paper, we are especially interested in fractional Brownian Motion (fBM) as an example of a Markovvan process. fBM is generalization of Brownian motion where the increments need not be independent but can instead be positively or negatively correlated. The amount of correlation is captured by the Hurst parameter H E (o. 1) (a formal introduction to fBM is discussed in Section
Mathematical techniques for mon-Markovian processes are largely underdeveloped compared to their Markovian counterparts. There are two sets of results that are of relevance to the problem discussed in this work. The first set of results are escape times for fBM which are studied by [28 A 45 47],
but they are restricted to simple I-dimensional processes, and they are often applicable specific problems such as Kramer's problem, instead of more general problems of interest. Extending these results to multiple dimensions is difficult, and we are not aware of any existing result.
The second results of relevance are bounds on the expected supremum of the stochastic process, sometimes referred as maximal inequalities. There is large body of work focusing the expected supremum of "pure" fBM (i.e., without any drift term), including [34 30 For instance, g
establish both upper and lower bounds on the expected supremum of fBM scaling as O (I/VH)
Some limited results exist with time-dependent drift terms in the I-dimensional case, e.g. 39 gives an asymptotic result for H E (L. (1,1). 1). In the dilti--iieesionall case, 26 derive lower and upper bound for the distribution of fBM in the multii-immeniionll case, see Rmk. 4 In this work, our goal will be to provide sharp bounds for stochastic processes with more general drift terms than prior work and in the multi-dimensional case.
Brownian motion and Ornstein-Uhlenberd Uhlenbeck process. A well-studied type of stochastic process Brownian motion (BM), which is a special case of fBM (corresponding to H = } where the increments are not correlated. When also considering a stochastic process with drift, we obtain the well-known including both results on the exit time g 23
process, which has been the subject a large body of work, well as on the expected supremum Ho 211

---

0.25 H! 0.5
# 0.75
x(1)
-35
= 0.25
-14
= 0.5
05
time
(1
Figure 1: Discrctized path of fBM in dimension (left) and two dimensions (right) for different Hurst parameters. We observe that low values H yield stochastic processes that explore the space a denser way that is less "biased" by the direction of the first few perturbations. This can in fact be formalized through the concept of Hausdorff dimension which is given by = 2 H for all If E (0, 1), see Rmk.
Finally, 100 also derived maximal inequality for multi-dimensional although their result is restricted to the radial case.
process,
SGD & Noise Injection. The distribution of the noise of SGD is often subject of debate in the literature. In some cases, the noise of SGD appears to be heavy-tailed 38 17 which yields faster exit from sharp flat minima K3 Noise is also often added to (stochastic) gradient descent. For instance, Perturbed Gradient Descent (PGD) is a version of GD where artificial noise is added to the parameters after every step. Multiple PGD methods have been shown to help quickly escape spurious local minima [55] and saddle points [22]. Another way to add perturbations to SGD is to add noise to the labels of the data used for training. Recent work has demonstrated that such perturbations are
indeed beneficial for generalization by implicitly regularizing the loss 7 18
3 Background
Fractional Brownian Motion. Fractional Brownian motion (IBM) is a generalization of Brownian motion where the increments of the stochastic process need not be independent. This family of
Gaussian processes was developed for some hydrological modelling by [25). [99 later studied the
long term water flow characteristics of the Nile River that was affected by long periods of drought. In such a scenario, the self similarity of the process is related to a long term dependence in the water levels. Since then, fBM has also found applications in financial modeling 351 We now give formal definition of fBM, and discuss its main properties.
Definition 1. Fractional Brownian motion (fBM) is a centered Gaussian process (B" (t))ce(o))) for T > 0 with covariance function
E[BH (1) = (1 + +|s|2H -It 212H).
where H E (0, 1) is called the Hurst parameter.
Hence, IBM is a generalization of Brownian motion, which is recovered for = 3. If > the increments are positively correlated, while they are negatively correlated if H < }. For H + 1 the increments of fBM not independent, although they are stationary, with variance
2. then
2
E(I"" (t) - Bd (s) It s 2
(1)
A crucial property of negatively correlated increments is their ability fill in the space, illustrated in Fig. M see Rmk. [
Fractional Ornstein-Uhlenbedd (OU) process. We conduct analysis on the fractional process, which can be thought of as a generalization of the well-known Omstein-Uhlenbeer process that has already found many applications in the field of machine leamn ing 27 48 Formally, this process is a d-dimensional stochastic process X E Idd defined by
H = AX,dt dBH Xo= dxx
(2)
where A E Baxd and B = (B... ... BRddd is fBM with H E 1). For further information regarding the fractional Crnstein-Uhlenbes process, we refer the reader [1 instance later make use of the covariance of this process that has been derived by 20 3
29
M We will for
3

---

The fractional Orstein-Uhlenbeed process is relevant for optimization purposes as it corresponds to optimizing quadratic function of the form f(x) 1 Az. Indeed, the gradient of the function (z(x)= = Az then corresponds to the drift term in Eq. We also note that when the stochastic process reaches stationarity, the stationary distribution of the iterates is known to he approximated by quadratic function [27] [ This implies that such processes can be used to analyze the behavior of complex functions at stationarity, but also close to saddle points where quadratic functions often play crucial role to analyze the escape behavior of gradient descent methods 22
Discretization by fractional Perturbed Gradient Descent (fPGD). For standard Brownian motion B, (i.e. for Hurst parameter H = 1/2). the discretization of the continuous- time SDE d.,; dXt + adB, of any optimization problem argmin, f(xx), is written
Øn+1 = nn 7/ fxx) + o o[Bn(x+1) - Butnn)
(3)
with step size > 0. This method is called perturbed gradient descent (PGD) [22]. Here, by instead discretizing the fractional SDE dX, -V((X)d dt) + od for any H E (0, 1), obtain generalized version of PGD, called fractional PGD (fPGD):
In+11 = In T/V (x,,) + +o
q(*+1) +
B (())))
which is equal to PGD if H 1/2. The parameter H determines the correlation of noise in fPGD: anticorrelated noise for H E 10.1 positively correlated noise for H E (1/2, 1). and uncorrelated (independent) noise for H = 1/2. Importantly since B converges
white-noise process (in distribution) as H - O; see Lemma 4.1 by [ the method Anti-PGD (36 Section 2] can be considered as the limit case of fPGD H 1. O. Hence, fPGD with H 1/2) interpolates between PGD (H = 1/2) and Anti-PGD (H = 0). Positive correlations (H E (1/2, 1)) have not been shown to be useful yet, and indeed the below theorems and experiments will indicate that small H yields quicker escapes from difficult regions such as saddle points and local minima. While the next section will analyze the continuous-
model based on fBM, will return the optimizer fPGD in the experiments (Section 5 where we will illustrate how the theoretical properties relate to optimization, methods.
and why H might, some settings, be a useful tuning parameter for
Analysis
4.1 Preliminaries
Our analysis relies on a technique known as chaining that provides a general framework that can be used prove uniform bounds on a random process. The main tools we use are Dudley's 's inequality and Sudakov's 's inequality, which give upper and lower bounds on E [supter X.] in terms of the metric entropy of I denoted by log (T,, e). Both incqualities are stated in Appendix A.I
We will consider processes that have sub-Gaussian increments as defined below. For that, we recall the definition of the sub- Gaussian norm of random variable X, denoted by || [l as || = in > 0 E[eex(X22/()) < 2].
Definition 2. A random process (Xt)te defined on a metric space (T, d) has aub-auussian incre- ments if there exists K 0 such that || Xxllvz I Kd(t,s) Vt,s T.
4.2 One-dimensional case
In this section, we derive both upper and lower bounds on the expected supremum of the stochastic process defined in Eq. p Since the analysis is rather technical, we first present the main ideas in the I I-dimensional case. We then present the general result for the d-dimensional case.
Theorem (Upper bound, 1-D case). Consider the stochastic process X defined by
dx." = 3x,dt + tdd
with Xo = 0, E R and [3] < 1. Then, for E [0, 1).
< 1 Looovo + +ov H
Ca
E
sup [E|0.11
x."
where C3 = 39 and C' are positive constants (independent of H).

---

Theorem (Lower bound, 1-D case). Consider the stochastic process X defined by
dx = d3x + odB
with Xo = 0, E R and [3] < 1. Then
oC'
E
sup [EJo.1]
X
log
where C3 = 2218 and e are positive constants (independent of H).
Note that both upper and lower bounds scale with O (vH) which implies the bound is tight and can not be improved in terms of H. However, the lower bound requires > e2181 (large-noiss regime) be non-vacuous. We can also derive a lower bound for the small-noise regime as follows.
Corollary 3 (Small noise regime), In the case where where dY? H -BY dt + dB, Yo" = O. Therefore
e2101-3, we observe that X oY
Thm.
1 H
Ce -
E
X [E(0,1]
sup
E sup tE(o.1]
oY
oE
Y. [E(0,1]
sup
OC
e 2 V
log
We thus obtain a lower bound for (3] S 1. In the general case < 13) < 1, one gets principally lower bound in terms of entropy numbers (Thm. 7 or by means of so called Talagrand functionals (see e.g. [45]). However, the latter quantities cannot be computed explicitly, in general. In Appendix B.7 we however provide experiments that demonstrate the 1/VH in this case, for the example of 3
Remark 1 (Extension any finite interval). Although the theorems are stated for the interval T [0, 1]. one can extend the results to arbitrary finite interval using the self-similarity property of fBM, namely B a B for a > O. This implies that sup.e]o.r] _ t"E suppe((o.1] B In the multi-dimensional case, the same extension works by the independence of the dimensions.
4.3 Multi-dimensional case
We now generalize the bounds to the multi-dimensional case. The quantity of interest becomes the expected supremum of the norm, or more precisely E suprejo. ||x - =E[""1I] Similarly to the I-dimensional case, apply Sudakov's incquality to the Gaussian component of the multi- dimensional FOU process X #
Theorem 4 (Upper bound, d-dimensional case). Consider the d-dimensional stochastic process X. E RRd defined by
dx = AX,dt + dB Xo = E.
where AE IRdxd and BH (BH1.1 Blld) is JBM with H (0, 1). Denote by aiz(t) the matrix entries of exp(LA)) Then
E[X SCCC, + CdCOVA
E sup
| [E(0,1]
2/H
where C2 max -ax supie|o.1] lay (t)2 max - supre(o.1] |ai (t)( + 11 and C is conslant independent of H.
*n alternative option, which we do not pursue in this paper, would be to generalize the result of Sudakov's inequality to the case of sub- Sab-Gaussian or sub-expon aub-exponential processes. However, the proof technique presented by 4g strongly relies Gaussian comparison inequalities and might be difficult to generalize.
5

---

Theorem 5 (Lower bound, d-dimensional case). Consider the d- d-dimensional stochastic process X E TR defined by
dx;t = AX,dt + dB, Xo E:
where A Raxd and B (B.t..... ... ..I.....d.) (ty(t) (t) the matrix entries of exp(tA)A and assume that there exists ig E {l....d. d} such that min]e[o.1] Bioin (1) 2 -1 + C1, where 0 < C1 < Then
) is a fBM with H (0, 2)) Denote by
E
sup [E
| B[X
2 ce-
1 H
log
2C' c
where c is a constant independent of H.
We obtain upper bound of the form O VB
with matching lower bound, although we do require a condition on the entries of the matrix A, which we discuss further in Example Caroplleebbbooo below.
Example (Assumption lower bound). Let A diag Ad). Then e A = diag ( A1,.... 2a) If some diagonal element of non-negative, then the assumptions of the above theorem are satisfied. Suppose that all entries X!...., Xa are negative and that Xi for some in. Then min 0ioka (t) = min (E Xi.) 2 X > -1 + C1 for some C1 E (0, 1). Hence, if some diagonal element Aig 1 exists, then the conditions of the previous theorem are fulfilled.
We make few comments regarding the meaning of the bound, well some extensions.
First of all, the theorems discussed above bound the expected supremum of the process. We now explain how these are connected to what we call "exploration ability".
Remark 2 (Exploration ability). We give three different justifications for the concept of exploration. Expected behavior: Based on Theorem we have
E
||*||| [E
sup
sup B|X rE[o.1]
2 E
sup xE(0,1)
|| B[x#11] 2 ce
V
H
1
log
2C e
where c, C1 constant independent of H.
Since E.H solves the ODE <(t) = ++ S Ao(s)ds, the quantity == supte|o.1]
||[[|]]|
< co
independent of H. Thus E suppeeo.1) ||*#|| 2 ce-t V
2C log
a. Hence, for given
c
H1 E (0, 1). there an H < H2 such that E supieto.1]
[Xx
E
supte(o.1]
|x ||]
We conclude that the average maximal distance of X from the origin is larger than that of X. This is what we mean by the process having a better exploration ability. Better exploration, this sense, can help to escape suboptimal local minima more quickly (experiments in Section 5.1 or to explore the space around saddle point for an exit (experiments in Section 5.2
2) Exit time: First, note that E (suPte]o,1]
||x
= P suptejo,11 ||X > 8) ds, therefore
100h {o (suPre(o.]] ||x"1 > 8) - supte ||X > 8) ds 0.
Thus, we can find a so > 0 such that F (supieju,) ||X > (o) -P (suplelos))
and, since probability distributions are right-continuous, there exists > such that for all E [so, so + E). (Supeej,.]] ||x|| s) P (suPrejo.j) ||X || >
> 0. On the other hand,
P 1) where T!! denotes the first exit time of XH from the ball (0) of radius s. We conclude that P < P( 1) Vs E [s0, So + E) i.e. the
SuPtEjo.1] || >
probability of an exit before time of H is larger than that of H4.

---

3) Space-filling property: We note that fractional Brownian motion with low Hurst parameter H fills the space more densely. This behavior comes from the fact that the graph of the fBM has a Hausdorff dimension and box-counting dimension given by d = 2 H. The latter implies that N ([] x On for large n, where N(e) denotes the number of boxes with side length e, which is needed to cover the graph of the fBM. Therefore, the graph of a (-ddimensional) fBM "behaves" like 2 dimensional smooth manifold for small H. See [d2]. The above claim about the Hausdorff dimension and the box-filling dimension of fBM is proved by (5Ty. Further related articles are [5] and (52).
Remark 3 (More general version). Let us mention that the results in Theorems and can be also generalized the case of linear SDE's of the form
xx=x+ x [ A(s)X + [ E(s)dB
where A: [0,T] + Raxd locally bounded and measurable, E: :0, T) Raxd is continuous differentiable and H <. 4. Here the stochastic integral with respect to B. is given by the Young integral. In fact, one can show that Jo E(s) = B. So 0 as B. ds (see e.g. (6]). By
using the linear transformation Y, = X, ass))ds, where a(t)= == A(t) So I(s)dB Denote by (tt). 0 S t S T the fundamental solution associated with A(t), that is the unique (absolutely continuous) solution to the equation (t) (t)) (0) = Laxa- the d x d identity matrix. Hence.
E(s)dB we observe that Y, = x (A(s)Y,
X, (1)x + S Φ (s)Ass()))
[' E(w)dB ds I ((())B",,sISSS
(()
Although the solution X,, 0 S t S T is in general not stationary any longer, we can use similar arguments as in the proofs of Theorems laddn | and the latter representation of the process to derive a lower and upper bound for E [suposes]
Remark 4 (Known bounds for distribution of fBM in multi-dimensional case). In Theorems
and we obtained lower and upper bound for the expected supremum of the norm of a (centered)
mulii-dimensionl JOU process (without a drift term). In comparison to the latter we also mention the following corresponding result for distributions with respect to the [Bm (see Theorem 4.6 by (261): Let B O S S 1 be a fractional Brownian motion in Rd for H E (0, Then the following lower and upper bound of the distribution of supogeg1 B (II-I maximum norm) hold: There exist constants 0 < (HH S (2(H)
< oo such that for all 0 <651:
e c-dKg(1fe to S Pr sup ooeesi
|B
5 S -dddK
Remark (Tightness of the bound). As in the 1-D case, the bound right in terms of H, which is the most important quantity for the argument made in this paper. Regarding the dimension d, note that the lower bound does not depend on it (and thus it is not improvable) while the upper bound might not be light.
5 Experiments
The above analysis reveals some insights into the exploration capability of stochastic process X," driven by a fractional Brownian motion B." with Hurst parameter H. We have seen that the correlation between increments directly affects the expected supremum of X Concretely, lower values of the Hurst parameters are expected to yield processes with better exploration abilities, as we detailed in Remark 2 To demonstrate the relevance of our theoretical findings for optimization, run a series of experiments with the optimizer fPGD from Eq. 4
we show that fPGD with small H better explores a non-convex loss landscapes with multiple local minima better, as predicted by our theory (Rmk. D In Section 5.2 we will demonstrate on an embedded saddle point that different choices of Hl might be beneficial in different optimization phases - thus justifying the introduction of IPGD as a compromise between PGD and Anti-PGD. In the Appendix
In Section 5.1
we add experiments on how fPGD behaves on bi-stable optimization landscapes, where there are two adjacent minima of different desirability (also studied by :33; the results of these experiments confirm that small H yields faster escapes from local minima.
7

---

Styblinski-Tang function
deep min
-
-1
-
after 10% of steps
after all steps
Hed1
Medi5
Hel1
NedS5
15
-5
Figure 2: Exploration performance of fPGD the Styblinski-Tan Tang function, Eq. ( Upper left: contour plot. Upper right: contour plot with four local minima. The local minima are roughly captured by the black ellipses. The goal go from the shallow (upper right) through the medium ones to the deep one (lower left). Lower right: empirical distribution of fPGD for different H after 104 steps. Lower left: empirical distribution after all 10 steps. (A categorization by minima plotted in Fig. 3
We can see that small H deals better with this challenging escape task.
5.1 Demonstration exploration ability on Styblinski-Tang function
In this section, test the ability of fPGD escape local minima and explore the landscape. To this end, we consider the Styblinski-Tany function in two dimensions, which is written
1 (a+ 16x² + + y² 16y² + 5y)
fax v)
(5)
contour plot of this function is depicted on the upper left of Fig. This function has four minima: one shallow (upper right), two medium ones (upper left and lower right), and one global deep minimum (lower left); see upper right subfigure of Fig. 2 Since the direct way between the shallow and deep minimum blocked by large hill zero, gradient-based optimizers have go through the medium ones, to get to the shallow one. is therefore a suitable test problem to test the validity of the alleged exploration ability of fPGD with small H (as explained in Remark
We thus run experiments, where fPGD is initialized in the shallow minimum at 20 = 22.7, After enough iterations, iPGD will eventually take the following steps: First, it will escape the shallow minimum. Second, it will reach either the medium minima. Third, will exit the medium minimum. Fourth, it will reach the deep minimum. (This might, of course, take long time and the budget might not suffice.) Each these steps can be interpreted as stopping times whose distribution compare for different H to assess how good the exploration is: the lower each of these stopping times, the better the exploration for a given H.
The precise experimental setup is the following. For H E (0.1,0.3,0.5.0.77 times with a budget 10 steps. We chose a generic step size of 1 = 0.01. To zoom in on the effect, the perturbation scale is set to the highest level of noise admissible without divergence on this landscape, i.c. σ = 1.25. (Note that we here again re-scale the final time to = so that the final amount of variance is equal for all Hurst parameters.) For each run, determined after each step if fPGD is in the shallow, one the medium or the deep minimum (or outside of all of them). From this information, extracted the below summary statistics to study the exploration ability.
we run fPGD 103
As start, the lower row of Fig. shows for H E (0.1, 0.5. 0.9), where fPGD ends up after 10 and after all 10 steps. It is clearly visible that the smaller the Hurst parameter, the faster fPGD moves to better local minima. (For other values of H the same tendency would be visible, as the below figures will confirm.)

---

To give more quantitative assessment of this effect, we provide bar chart of the position of fPGD for all after 10* and 10 steps in the upper row of Fig- B It clearly shows that a small value of H is less likely to remain in the shallow minimum and is more likely to end up in the deep minimum. This is strong effect: after 10% of steps only H E (0.1. 0.3) have exited at all. Only = 0.1 has chance of reaching the deep minimum by then. While H E {0.3, 0.5) can eventually reach the deep minimum after an order of magnitude longer, E {0.7, 0.9} cannot reach at all 10 steps. The beneficial exploration of H is confirmed by the shape of the cumulative distribution functions (cdfs) the lower row Fig. g
FPGD after 10% of steps
FPGD after all steps
H-0.3
H-0.3
H.5
H- 0.5
H.7
H=0.9
0.0
rablo volune
rabl of voluees
6.
deep
deop
first-exit from shallow minimum
first-arrival medium minima
first-arrival deep minimum
10
0.8
Hm0
1-0
1m0
0.4
0.4
0.4
02
0.7
0.7
0.0
0.0
0.0
20000
40000 60000 Iterations
80000 300000
20000
40000 00000
50030
100000
20000
40000 50000
80000 200000
iteration
narations
Figure 3: Upper row: Bar graph showing where fPGD ends up after 10 (left) as well as all 103 steps (right). We consider the endpoints to be in local minimum if it ends up within the respective black ellipses (on upper right Fig. 2) can end up in the shallow, one of the medium, the deep, outside of these minima. We can see that it is much more likely for small H to reach the deep minimum. Lower row: Cumulative density functions (cdfs) for first exits from shallow/medium minima and first arrival to deep minimum. The upper left plot with only 10% computational budget highlights the potential for large savings in case of small H. Conversely, a large / is not expected to leave the shallow minimum at all (the edf for H 0.9 is smaller than 0.5 in lower left plot).
5.2 Non-Markovian fPGD as a trade-off between PGD and Anti-PGD
As discussed earlier, fPGD interpolates between two known Markovian methods: PGD [H 1/2) and Anti-PGD (ff = 0). Both PGD and Anti-PGD have unique advantages; see 55 or P for PGD and 36 for Anti-PGD. It thus natural to ask whether there are cases where non-Markovian iPGD (H E (0, 1/2)) is beneficial. While we do not have complete answer this question, we here present a setting that demonstrates that H E 1/2) can indeed outperform both PGD (H 1/2) and Anti-PGD (H 0) simultancously. We consider the following regularized quadratic: 3 1 Mæ + >Σ 2t. where z; is the i-th coordinate of Rd, M Rdxd 400, and À = 0.0001. If M has negative eigenvalues, this landscape has d-dim. saddle point at æ 0. stochastic optimizer can find the negative eigenvectors, will reach a global minimum away from zero while gradient descent remains stuck at zero. The problem gets increasingly hard as the number of negative cigendirections decreases [22]. Indeed, [[4] showed that vanilla gradient descent takes in the worst exponential time (in the number of dimensions) to escape such saddle points. We choose M as a diagonal matrix whose diagonal entries are uniformly sampled from [0, 1]. and - to make it challenging saddle multiply the 10 lowest of these entries by -1.
f())
We test fPGD on this problem. We initialise the saddle x and run fPGD with o 0.005 and 0.005 for 10" iterations with different Hurst parameters. (While in general a and H are tuning parameters that can be jointly tuned, here a = 0.005 a good choice for all values of H which we demonstrate in Appendix B.2 The results are presented in Fig. g In this problem, there is indeed a trade-off between uncorrelated (H = 0.5) and anticorrelated perturbations (H < 0.5): While large Hurst parameter (H 0.5) moves away from the saddle quickly, the non-Markovian (PGD

---

embedded saddle point
Inialaation
Landscape sketch 2d
0.5
not
-0.5
Hm0.1
H-0.2
-1.0
Hm0.3
H-0.4
H-0.5
-1.5
20000
40000
60000
80000 100000
Iteration (K)
Figure 4: the embedded saddle landscape, we see trade-off between first exiting the saddle quickly (with a larger H) and then converging to the bottom of the minimum (with a smaller H). We plot the average over 5 runs. Non- Mor-Markov versions of IPGD (with H = 0.3 or H = 0.4) perform better than both Markovian versions, PGD (H 0.5) and Anti-PGI (H 0). We use 0.005 for all H, as justified in Appendix B.2
(H = 00.4) finds the direction with negative curvature most quickly (in the sense that it gets below zero). Once they have exited, all H perform similarly for a while. Eventually, however, smaller Hurst parameters converge better to the bottom of the final minimum - thereby eventually catching up and surpassing the first faster higher Hurst parameters. Which H is best, will therefore depend on how many iterations the computational budget allows for. Here, the non-Markovian H = 0.3 and H 0.4 yield the best final accuracy.
This suggests that, if all other parameters are the same, different choices of Hurst parameters are beneficial in different situations. It can thus be advantagcous to tune and adapt the correlation of noise by choosing H. is especially interesting that both PGD (H = 1/2) and Anti-PGD (H = 0) have shortcomings in this experiment: PGD has increase the loss significantly in the beginning before exiting the saddle and does not converge to the bottom of the minimum in the end. Anti-PGD takes long time exit the saddle in the beginning. In contrast, Markovann fPGD (with H 0.3 or H = 0.4) stays clear of these two undesirable extremes. We stress, however, that the above experiment is proof of concept and only shows that there exist landscapes where Mar-Marko fPGD performs best. On many other landscapes, PGD or Anti-PGD will still be better.
To make fPGD efficient on general landscapes, further work is needed to better understand the interplay between the scale a and the correlation parameter H, which interact according to Eq. (
Using this knowledge, one could design an adaptive method that jointly tunes and H to maximize the efficiency of perturbed gradient methods. For the above experiments, we again emphasize that our constant choice of a is suitable for all H, as justified in Appendix B.2
6 Conclusion
We analyzed the behavior of new type of stochastic noise with correlated increments. We found that the amount of correlation, captured by the Hurst parameter H, has a direct effect on the overall magnitude of the process and its ability to explore. This insight opens the doors to new area of research where the noise of stochastic processes could be manipulated to speed up the convergence of an optimization method, as well target specific minima (e.g., depending on their flatness properties). Our experimental results validate our theoretical analysis. We showed, on some non-convex potentials, that injection of fractional noise with small H speeds up the escape from suboptimal minimum to a better one. Also, we showed that there are indeed settings where non-Markovian (somewhat anti-correlated) noise outperforms the standard Markovian (uncorrelated or perfectly anti-correlated) noise. Finally, one direction of interest would be to extend the analysis to more complex objective functions, which could potentially be achieved using the comparison theorem for SDEs (00
Acknowledgement We would like to thank Nacira Agram and Bernt Øksendal for some helpful discussions the early stage of this project, as well as the reviewers for their feedback that greatly helped us improve this manuscript. Frank Proske acknowledges the financial support of the Center for International Cooperation in Education, project No (PEA-LT-2016/10139 Norway. Hans Kersting and Francis Bach acknowledge support from the French government under the management of the Agence Nationale de la Recherche as part of the "Investissements d' d'avenir" program, reference ANR-19-P31A-000 (PRAIRIE 31A Institute), as well as from the European Research Council (grant SEQUOIA 724063). Aurelien Lucchi acknowledges the financial support of the Swiss National Foundation, SNF grant No 207392.
10

---

References
[1] Larbi Alili, Pierre Patic, and Jesper Lund Pedersen. Representations of the first hitting time density of orstein-uhlenbeck process. Stochastic Models, 21(4):667-980, 2005,
[2] Guozhong An. The effects of adding noise during backpropagation training generalization performance. Neural computation, 8(3):643-65) 674, 1996.
[3] Giacomo Ascione, Yuliya Mishura, and Enrica Pirozzi. Fractional ornstenn-ullebeec process with stochastic forcing, and its applications. Methodology and Computing Applied Probability, 23(1):33-84, 2021.
[4] Frank Aurzada et al. On the one-sided exit problem for fractional brownian motion. Electronic Communications in Probability, 16:392-404, 2011.
[5] Antoine Ayache and Yimin Xiao. Asymptotic properties and Hausdorff dimensions of fractional Brownian sheets. Journal of Fourier Analysis and Applications, 1 11:407-439 2005.
[6] Francesca Biagini, Yaozhong Hu, Bernt Øksendal, and Tusheng Zhang. Stochastic calculus for fractional Brownian motion and applications. Springer Science Business Media, 2008.
[7] Guy Blane, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by ornstenn-uhlenbeck like process. In Conference on learning theory, pages 483-513. PMLR, 2020.
[8] Konstantin Borovkov, Yuliya Mishura, Alexander Novikov, and Mikhail Zhitlukhin. Bounds for expected maxima of gaussian processes and their discrete approximations. Stochastics, 39(1):21-37,2011
[9] Konstantin Borovkov and Alexander Novikov. On exit times of lévy-driven urnstein- processes. Statistics & Probability Letters, 78(12):1517-1555, 2008
[10] Yu I. Botnikov. Davis-type inequalities for some diffusion processes. Journal of Mathematical Sciences, 137(1):4502-4509 2006.
[11] Patrick Cheridito, Hideyuki Kawaguchi. and Makoto Maejima. Fractional omstein-ublenbeck processes. Electronic Journal of probability. 8:1-14, 2003.
[12] Alex Damian, Tengyu Ma, and Jason Lee. Label noise SGD provably prefers flat global minimizers. arXiv preprint arXiv:2 11022000600630 2021.
[13] Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pages 1155-1164. PMLR, 2018
[14] Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances in neural information processing systems, 30, 2017.
[15] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points points-online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 797- 842, 2015.
[16] S Graversen and Goran Peskir. Maximal inequalities for the ornstein-uhlenbeck process. Proceedings of the American Mathematical Society, 128010):305-33411, 2000.
[17] Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in SGD, In International Conference on Machine Learning, pages 3964 3975, 2021.
[18] Jeff Z. HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, pages 1315-23577 2021.
[19] Harold Edwin Hurst. Methods of using long-term storage in reservoirs. Proceedings of the Institution of Civil Engineers, 5(5):519-543) 1956.

---

[20] Nobuyuki Ikeda and Shinzo Watanabe, Stochastic differential equations and diffusion processes. Elsevier, 2014.
[21] Chen Jia and Guohuan Zhao. Moderate maximal inequalities for the ornstein-uhlenbeck process. Proceedings of the American Mathematical Society, 148(8):3607-300 2020.
[22] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points, J. ACM, 68(2), 2021.
[23] Hans Kersting, Antonio Orvieto, Frank Proske, and Aurelien Lucchi. Mean first exit times of OrnsteinUUhlenbeck processes in high-dimensional spaces. arXiv preprint S2ti:2220..40222 2022.
[24] 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 arXiv: 04836, 2016.
[25] Andrei N Kolmogorov. Wienersche spiralen und einige andere interessante kurven in hilbertscen raum, cr (doklady). Acad. Sci. URSS (NS), 26:1 1188 1940.
[26] Wenbo V Li and Q-M Shao. Gaussian processes: inequalities, small ball probabilities and applications. Handbook of Statistics, 19:533-599 2001.
[27] Stephan Mandt, Matthew D Hoffman, and David M Blei. Stochastic gradient descent as approximate bayesian inference. arXiv preprint arXiv:
2017.
[28] Zbigniew Michna. On tail probabilities and first passage times for fractional brownian motion. Mathematical Methods of Operations Research, 49(2)3335-354 1999.
[29] Yuliya Mishura, Vladimir Piterbarg, Kostiantyn Ralchenko, and Anton Yurchenko--Tttrrenko. Stochastic representation and pathwise properties of fractional cox-ingersoll-ross process. arXiv preprint 170.::170..0221111 2017.
[30] George M Molchan. Maximum of a fractional brownian motion: probabilities of small values. Communications in mathematical physics, 201 1999.
[31] Alan F Murray and Peter Edwards. Synaptic weight noise during mlp learning enhances fault- tolerance, generalization and learning trajectory. Advances in neural information processing systems, pages 491-491, 1993.
[32] Arvind Neelakantan, Luke Vilnis, Quoc V Le, Ilya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint
2015.
[33] Thanh Huy Nguyen, Umut Simsekli, Mert Gurbuzbalaban, and Gaël Richard. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. Advances Neural Information Processing Systems, 2019.
[34] Alexander Novikov and Esko Valkeila. On some maximal inequalities for fractional brownian motions. Statistics & probability letters, 44(1):47-54, 1999.
[35] Bernt Øksendal. Fractional brownian motion in finance. Preprint series. Pure mathematics http://urm. nb. no/URN: NBN: no-8076, 2003.
[36] Antonio Orvieto, Hans Kersting, Frank Proske, Francis Bach, and Aurelien Lucchi. Anticor- related noise injection for improved generalization. In International Conference Machine Learning. PMLR, 2022.
[37] Antonio Orvieto, Anant Raj, Hans Kersting, and Francis Bach. Explicit regularization in overparametrized models via noise injection. arXiv preprint arXiv:2206. 220.:220000.46133 2022.
[38] Abhishek Panigrahi, Raghav Somani, Navin Goyal, and Praneeth Netrapalli. Non-Gaussianity of stochastic gradient noise. arXiv preprint arXiv:1910.09622 2019.
12

---

[39] BLS Prakasa Rao. Some maximal inequalities for fractional brownian motion with polynomial drift. Stochastic Analysis and Applications, 31(5):785-79, 2013.
[40] BLS Prakasa Rao. Maximal inequalities for fractional brownian motion: An overview. Stochas- tic Analysis and Applications, 32(3):450-47, 2014.
[41] Lloyd P Sanders and Tobias Ambjömsson. First passage times for tracer particle in single file diffusion and fractional brownian motion. The Journal of chemical physics, 136(17)005605, 2012.
[42] M. Schroeder. Fractals, chaos, power laws; Minutes from an infinite paradise. New York. W. H. Freeman, pages 41-45, 1991.
[43] Zeev Schuss. Theory and applications of stochastic processes: an analytical approach, volume 170. Springer Science & Business Media, 2009.
[44] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, 2019.
[45] Oleksii Yu Sliusarenko, Vsevolod Yu Gonchar, Aleksei V Chechkin, Igor M Sokolov, and Ralf Metzler. Kramers-like escape driven by fractional gaussian noise. Physical Review E, 8 81(4):041119 199, 2010.
[46] Samuel Smith, Erich Elsen, and Soham De. On the generalization benefit of noise in stochastic gradient descent. In International Conference on Machine Learning, pages
2020.
[47] Chengli Tan, Jiangshe Zhang, and Junmin Liu. Understanding long range memory effects in deep neural networks. arXiv preprint arXiv:2 2021.
[48] Prakhar Verma, ADAM Vincent, and Amo Solin. Sparse gaussian processes for stochastic differential equations. In The Symbiosis of Deep Learning and Differential Equations, 2021.
[49] Roman Vershynin. #ligh-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[50] Mingwei Wei and David J Schwab. How noise affects the Hessian spectrum in overparameterized neural networks. arXiv preprint arXiv:/910.00/95, 2019.
[51] Dong Sheng Wu and Yi Min Xiao. Dimensional properties of fractional Brownian motion. Acta Mathematica Sinica, English Series, 23(4):613-62 2007.
[52] Dongsheng Wu and Yimin Xiao. Geometric properties of fractional Brownian sheets. Journal of Fourier Analysis and Applications, 13(1):1-37, 2007.
[53] Zeke Xie, Issei Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. arXiv preprint weXiv:2002.03495 2020.
[54] Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George Dahl, Chris Shallue, and Roger B Grosse. Which algorithmic choices matter at which batch sizes? Insights from a noisy quadratic model. Advances in neural information processing systems, pages 8196-82000 2019.
[55] Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning, pages 7594-7602, 2019.
13


Reviews:
[{"review_id": "Ywo_Ubbniea", "reviewer": "Reviewer_XeCx", "summary": "To discuss the effect of temporally correlated noise on exploratory capacity of stochastic optimizers, the authors have conducted a theoretical study of a newly proposed optimization algorithm/model, called 'fractional PGD' (fPGD). Instead of Gaussian perturbations, fPGD perturbs each iteration according to a fractional Brownian motion, introducing temporally correlated noise. This method is motivated as a generalization of both perturbed gradient descent (PGD), and a recently proposed optimizer called 'Anti-SGD'. To investigate the potential of the optimizer to explore, upper and lower bounds are obtained for the supremum of an Ornstein-Uhlenbeck-type fractional Brownian motion, using Gaussian process theory. The bounds demonstrate higher potential for exploration with smaller Hurst parameters. The behaviour of fPGD is demonstrated using two synthetic experiments, first by traversing a one-dimensional loss landscape with two basins, and then a 400-dimensional regularized quadratic, showing that Hurst values which interpolate between PGD and Anti-SGD appear to exhibit improved performance. ", "questions": "As far as the linearity of the drift is concerned, would similar bounds not hold assuming the drift is bounded above and below by linear functions? I can't see anywhere in the proofs of Theorems 1 and 2 where this would be an issue, but I may be mistaken. This would significantly improve the applicability of the results. \n\nCan the experiment in Section 5.2 be extended to a more complex optimization problem, e.g. training a neural network (ideally large, but this depends on available resources) as in the Anti-SGD paper? \n\nDoes the multi-dimensional case directly generalize the one-dimensional case? If so, why include both?", "limitations": "There is some discussion at the end of the experiments concerning possible future work, and a few comments on the tightness of the bounds (e.g. the multivariate bound is likely not tight in the dimension). However, there is otherwise little discussion of the limitations of the work and, in particular, its lack of generality. As per above, I believe some further discussion on this is needed. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, clearly presented, and well-organized. Exploration in stochastic optimization is relatively under-appreciated, and I welcome new insights which provide new  I like how Anti-PGD provides a motivating factor for the choice of fractional Brownian motion. \n\nUnfortunately, there are a few errors in the proof which do change the results stated in the main body of the text. For example, the second line of (7) forgets the factorial terms in the expansion of $e^{\\beta z}$, leading to $C_\\beta = 1/(1-\\beta)$, when it should be $C_\\beta = e^\\beta$. This is much easier to get to actually, just by noting upfront that $z \\leq t - s \\leq 1$ and so $e^{\\beta z} \\leq e^\\beta$. A similar error occurs in the proof of Theorem 2. \n\nThe significance of the results, especially for the ML community, is also let down by their generality. I understand that obtaining bounds for these processes is challenging already, but Remark 3 states that a time-inhomogeneous extension is feasible; why is this not the version presented? I also suspect that even greater generality is achievable; see the Questions section. \n\nThe experiments are also promising, but I feel that they could be improved. I did not find Section 5.1 to be particularly helpful (I feel this might be improved with more and sharper basins in two dimensions). Section 5.2 displays some potential for improved empirical performance, but I am concerned that this experiment has been cherry-picked. Given the simplicity of the algorithm, I don't see why this couldn't be applied to more complex problems.\n\nSome minor comments:\n- In each of the SDEs, the $X_t$ in the drift term is missing the superscript $H$.\n- For consistency, it might be good to put a superscript $H$ for $x_n$, $x_{n+1}$ (e.g. $x_n^H$) in equation (4). \n- Please consider removing the italicization in the remarks, as it makes them quite challenging to read. \n- line 226: 'the bound is right' -> 'the bound is tight' ?\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": {}}, {"review_id": "Q7SeP763nM", "reviewer": "Reviewer_zaJL", "summary": "This paper proposes fractional perturbed gradient descent (fPGD), which corresponds to the discretization of a stochastic differential equation driven by fractional Brownian motion. \nfPGD (with a parameter $H \\in (0,1)$) has a nice property of interpolating two existing algorithms, i.e., PGD (with $H=0.5$) and anti-PGD (with $H = 0$).\n\nIn terms of theory, the paper provided upper and lower bounds for the expected supermum of fractional SDEs, in both one-dimension cases and multi-dim cases. Note that the expected supermum captures the escaping/exploration ability of the algorithm.\n\nIn terms of experiments, the paper shows that, at least in simulated dataset, fPGD achieves a better tradeoff between the extremes PGD and anti-PGD. \n", "questions": "1. Time and space complexity for generating the noise required by eq(4). Note that in eq(4), all noise is correlated. Suppose we need to run the algorithm for $N$ steps, i.e., we need to generate $N$ correlated noise, can you explain the time and space complexity for generating that noise? If the time/space complexity is overly large in terms of $N$, the fPGD algorithm might not be of practical interests. \n\n2. Thm1. In fact the integral can be solved in an analytic form --- please simply the expression in this regard. \n\n3. Thm2. For the lower bound to be non-negative, one needs to have that $\\sigma > \\exp(2 |\\beta| - 0.5)$. This seems to limit the applicability of the theorem: the bound is trivial when noise is small. Please clarify this during the rebuttal. Can we obtain some lower bounds for the small noise regime? \n\n4. Line 160 seems to be overclaiming: the bound might not be tight in terms of $H$, if the noise is small. \n\n5. Remark 1. Can you clarify whether or not remark 1 applies to multi-dim cases? \n\n6. Thms 3 and 4 assume that $X_0 = \\xi$. Why not assume that $X_0 = 0$ to be consistent with Thms 1 and 2? I believe this can be assumed without loss of generality? \n\n7. Thms 3 and 4 assume $\\sigma = 1$ or $\\Sigma = I$. It is not clear how a scaling/rotation on the fractional Brownian motion affects the final bounds. At least the effect of scaling (i.e., $\\Sigma = \\sigma I$ for general $\\sigma$) should be discussed, as Thms 1 and 2. \n\n8. Thms 3 and 4. The condition of $C_2$ or $C_1$ is hard to interpret. Could you please explain the intuition behind them?\n\n9. Thm 3 might be too loose in terms of $d$. In fact, appendix line 606 suggests that the authors control an $\\ell_2$ norm by a sum of $d$ $\\ell_\\infty$ norm. This inequality is too crude and loses the geometry of $\\ell_2$-norm.  I am not sure how useful the upper bound is. \n\n10. Similarly, for Thm 4 to be nontrivial, one needs to have $C_1 > 0.5 e^{-0.5}$. The comments on Example 1 need revision accordingly. \n\n11. Line 189. I feel this sentence overclaims the benefits of \"exploration\". I agree that more exploration helps escape from suboptimals, but on the other hand, the whole algorithm becomes more unstable. Perhaps the authors should comment here that there is a trade-off between exploration vs. convergence (in the sense that the algorithm stays in a basin of a good minima with good probability). Similarly the authors should revise the comments on the \"space-filling property\". \n\n12. Remark 3, could you comment on how the bounds are affected by considering a time-dependent $A$ and $\\Sigma$?\n\n13. Remark 4. Could you explain how this result compares to your results? \n", "limitations": "See above. \n\n\n===Post-Rebuttal\n\nSome of my concerns are addressed. The major issue is in the high-dim analysis, which does not make use of the right geometry and seems to be artificial in many aspects. I will raise my score from 4 to 5 but cannot give a higher score due to the mentioned limitations of this work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n+ The fPGD algorithm is quite novel (and very interesting to me!), at least in the machine learning field, to my knowledge. \n+ The fPGD algorithm has a nice theory background of being an discretization of a SDE driven by fractional Brownian motion. \n+ FPGD interpolates two existing algorithms, and is verified in simulations that can achieve a better tradeoff than both of them. \n\n# Weakness\n- The time and space complexity of generating noise for fPGD is not discussed. \n- The upper and lower bounds have multiple limitations. Please see more discussion below. \n- No real machine learning experiments. ", "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": "EPOSVPm6wDO", "reviewer": "Reviewer_9UJ2", "summary": "Generalization of gradient based algorithms for highly non-convex loss landscapes is poorly understood and there are many hypotheses explaining the empirical observations. One of them is that flat minima generalize better than sharp minima. The stochasticity of gradient based plays an important role in escaping sharp minima and settling on flat minima, and this paper studies the basic properties of fractional Ornstein-Uhlenbeck process and its dynamics on toy examples to better understand the importance of correlation in noise.", "questions": "1. In Remark 5, the paper says that the lower bound does not depend on $d$. I am not sure I understand since the lower bound clearly depends on $d$. Could you please explain what is meant here?\n2. In equation (5), should the characteristic function in the middle term in RHS be $\\chi_{a \\le x \\le c}$?", "limitations": "Not relevant", "rating": 7, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clear and easy to understand. It makes nice theoretical contributions in Section-4 on giving bounds for the expected suprema, which justifies the intuition that smaller Hurst parameter corresponds to a higher exploration ability of the stochastic process. It might be useful to mention that a fractional Ornstein-Uhlenbeck process is a Gaussian process because that fact is used in the proofs of the theorems implicitly.\n\nWhile the contribution of generalizing PGD and Anti-PGD is useful, I was expecting more experiments and more realistic examples to better understand the effect of $H$ strictly between $0$ and $1/2$. I was also expecting more analysis for the case $H > 1/2$, and when that could be useful if at all.", "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