Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes fractional perturbed gradient descent (fPGD), which corresponds to the discretization of a stochastic differential equation driven by fractional Brownian motion. 
fPGD (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$).

In 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.

In terms of experiments, the paper shows that, at least in simulated dataset, fPGD achieves a better tradeoff between the extremes PGD and anti-PGD. 

strengths_and_weaknesses: # Strengths

+ The fPGD algorithm is quite novel (and very interesting to me!), at least in the machine learning field, to my knowledge. 
+ The fPGD algorithm has a nice theory background of being an discretization of a SDE driven by fractional Brownian motion. 
+ FPGD interpolates two existing algorithms, and is verified in simulations that can achieve a better tradeoff than both of them. 

# Weakness
- The time and space complexity of generating noise for fPGD is not discussed. 
- The upper and lower bounds have multiple limitations. Please see more discussion below. 
- No real machine learning experiments. 
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. 

2. Thm1. In fact the integral can be solved in an analytic form --- please simply the expression in this regard. 

3. 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? 

4. Line 160 seems to be overclaiming: the bound might not be tight in terms of $H$, if the noise is small. 

5. Remark 1. Can you clarify whether or not remark 1 applies to multi-dim cases? 

6. 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? 

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

8. Thms 3 and 4. The condition of $C_2$ or $C_1$ is hard to interpret. Could you please explain the intuition behind them?

9. 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. 

10. 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. 

11. 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". 

12. Remark 3, could you comment on how the bounds are affected by considering a time-dependent $A$ and $\Sigma$?

13. Remark 4. Could you explain how this result compares to your results? 

limitations: See above. 


===Post-Rebuttal

Some 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

While 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.
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?
2. In equation (5), should the characteristic function in the middle term in RHS be $\chi_{a \le x \le c}$?
limitations: Not relevant
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
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. 

Unfortunately, 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. 

The 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. 

The 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.

Some minor comments:
- In each of the SDEs, the $X_t$ in the drift term is missing the superscript $H$.
- 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). 
- Please consider removing the italicization in the remarks, as it makes them quite challenging to read. 
- line 226: 'the bound is right' -> 'the bound is tight' ?

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. 

Can 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? 

Does 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.
review_title: null

Meta-review: metareview: This paper investigates the use of non-Gaussian (specifically "fractional Brownian") noise in SDEs.  The reviewers found a variety of weaknesses, but overall were positive; I point in particular to the many valuable comments left by reviewer XeCx.  As such, I mark this paper as accept, though I strongly urge the authors to further refine their work based on the copious review feedback below.  
confidence: Less certain
Decision: Accept