Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: **Strength**

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

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

**Weakness**

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

2. Does the algorithm parameters, $\mu$, $\sigma$ play an role in the generalization bound? In either case, it is worth discussion.

3. Besides the numerical experiments, can you provide some qualitative result that identify regimes where the proposed algorithm chaotic regularized GD works better than GD?


limitations: The authors adequately addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 
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. 
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. 

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

Theoretically, the authors:
 1. prove a generalization bound for their method that leverages recent generalization bounds for heavy-tailed SGD
 2. prove that their method approximately follows gradient flow on a regularized loss functional which implicitly penalizes the Hessian trace.  

Empirically, the authors:
1. 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.
2.  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.
3.  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.

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.

Regarding the impact on deep learning practice, 
 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?
 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.

Minor point: in motivating this study, the authors write in their introduction
> 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.

The paper CKL+21 is not about generalization or large learning rates.
questions: If you tune the step size for the baseline of deterministic GD, does the proposed method still work better?
limitations: Yes
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: 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.
strengths_and_weaknesses: *Strengths:*
The 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. 

*Weaknesses:* 
A 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.

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

Meta-review: metareview: A recent line of work on the role of stochasticity in ML suggests that variants of GD which use non-traditional step size schedules (a) may perform relatively well in certain settings (b) due to an implicit chaotic behavior. The present paper studies a variant of GD (MPGD) augmented with an explicit chaotic component, implemented by means of an external deterministic dynamical system, as a theoretical model for investigating these hypotheses. Recent results are shown to imply generalization bounds for the limiting stochastic process. Numerical results are provided for comparing the performance of MPGD to existing methods.

The reviewers have generally found the use of a GD variant with an explicit chaotic term, as well as the proposed analytic framework, interesting and appreciated the clarity and rigor of the results given in the paper. In later discussions, concerns regarding the relevance of the theoretical model to (a) and (b) above were raised by the reviewers, questioning more broadly the significance of MPGD and the respective limiting SDE to the general understanding of SGD/GD. All in all, I think this is a reasonable paper to accept if there is room. The authors are encouraged to revise the paper according to the important feedback given by the reviewers.




confidence: Less certain
Decision: Accept