Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors analyse the behavior of SGD under gradient clipping. Their analysis in the univariate case shows that gradient clipping in the heavy-tailed gradient noise (almost) eliminates the algorithm's tendency to stay at sharp minima. The authors support their analysis with synthetic experiments. The authors then conduct experiments on real data where they add heavy tailed noise to the gradient, and clip it afterwards.
main_review: I believe that the topics of SGD-trained networks' generalization in general, and the role of heavy-tailed parameter statistics in this in specific are very timely and worthy of attention, since our understanding of the dynamics that lead to generalization is not on par with the empirical success of SGD-based methods. 

I find the authors' analyses and results interesting and well-presented. I think it has potential to improve our understanding of the generalization characteristics of SGD-trained networks. Although their analyses mostly focus on the univariate case, I believe that this is acceptable as they provide some seminal results regarding truncated-gradient SGD. 

However, I have a hard time understanding the authors' characterization of recent results in the literature (or lack thereof), which also informs their experiment design. My point can be most dramatically made by drawing attention to the choice of baseline that the authors present. While the recent theoretical and empirical findings in literature emphasize the relationship between learning rate, and tail index and/or generalization, the authors somehow base their methodology and experiments on the supposed absence of heavy tails in gradient noise in image classification tasks. This is not necessarily true, and this fact is well-documented. Given this fact, the fact that the authors present the baselines as thin-tailed noise algorithms (without any detailed analysis of learning rate / batch size and their effects on generalization), as well as not estimating the tail index of these noises is surprising. I think the authors need to take into account more recent results in the literature and possibly alter their experimental settings and discussion accordingly. This is especially important since the authors aim to analyse why a specific modification of SGD leads to improvements.

- Hodgkinson, Liam, and Michael W. Mahoney. 2020. “Multiplicative Noise and Heavy Tails in Stochastic Optimization.” ArXiv:2006.06293 [Cs, Math, Stat], June. http://arxiv.org/abs/2006.06293.
- Gurbuzbalaban, Mert, Umut Şimşekli, and Lingjiong Zhu. 2021. “The Heavy-Tail Phenomenon in SGD.” ArXiv:2006.04740 [Cs, Math, Stat], June. http://arxiv.org/abs/2006.04740.
- Lewkowycz, Aitor, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. 2020. “The Large Learning Rate Phase of Deep Learning: The Catapult Mechanism,” March. https://arxiv.org/abs/2003.02218v1.
summary_of_the_review: The authors present interesting analyses and results regarding a modified version of SGD in optimization. Their characterization of the recent literature, and the experimental design based thereupon seems to need more attention.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper study the long-time behavior of heavy-tailed SGD with gradient clipping. It is found that gradient clipping is crucial for heavy-tailed SGD to avoid sharp minima. The basic intuition is that the clipping operation reduces the distance moved by each SGD update. Therefore, for minima narrow than the threshold, the clipping does not change the first exit time. However, for wide minima, SGD is slowed down and takes more time to escape. Consequently, it is more likely that SGD locates in wide minima. 


main_review: ### Pros

- A beautiful theoretical analysis is provided for a one-dimensional landscape under some structure assumptions. 
- Very insightful synthetical experiments are provided to justify the intuitions and theory.
- Inspired by the above analysis, the authors proposed two variants of SGD with injected heavy-tailed noise + gradient clipping. These modified SGDs are expected to converge to flatter minima, thereby generalizing better. 
- The experiments for deep nets on (Fashion)MNIST and CIFAR-10/CIFAR-100 are sufficient and show promising improvements over vanilla SGD.

### Cons

It seems that all the analyses ignore the noise structure and are only concerned with the magnitude. For instance, for even a one-dimensional problem, the gradient noise of vanilla mini-batch SGD is state-dependent. However, gradient noises in the prototypical dynamics analyzed in this paper (see Eq. (2)) are iid random variables. As another example, Figure 1 can be misleading since the light-tailed SGDs only use state-independent noise. It is possible that SGD with structured noise can avoid those sharp minima (completely). The authors should disentangle the effect of noise magnitudes and noise structures, and state clearly what is concerned in this paper. 



For the related work, previous work studying the stability-driven escaping from sharp minima is completely ignored. I would suggest comparing with them (see [1,2,3] and the reference therein). For example, the stability-driven escaping can tell us that, in Figure 1, GD with a relatively large learning rate never converge to the sharp minima: m1, m2.  


### Other comments

- In Figure 1, please make it clear in the caption that where the SGD starts from. 

- In the second paragraph of page 2, I am not sure why SGD with light-tailed noise never escape the sharp minima m3. I suppose that by adding large enough noise, SGD at least can escape from it, although it is as efficient as the heavy-tailed SGD. 

- " if we stop training SGD at an arbitrary time point, it is almost guaranteed that it won’t be at a sharp minimum". This claim seems wrong to me. Although heavy-tailed SGD with gradient clipping can avoid the sharp minima completely, it may take a very long time. 

- In Section 4, "Contrary to the report in (S ̧ims ̧ekli et al., 2019a), heavy-tailed noise may not be ubiquitous in image classification tasks.". Why is there this contradiction? In particular, Table 1 suggests that SGD+heavy-tailed noise performs very badly, even worse than large-batch SGD. Can you explain it? This also contradicts the synthetical experiments, where the heavy-tailed SGD converges to flat minima more likely than light-tailed SGD.

- In paragraph above Section 5, "event"-> "even".

  

[1] Wu, Lei, et al.,  How sgd selects the global minima in over-parameterized learning: A dynamical stability perspective.

[2] Jastrzebski et al. The Break-Even Point on Optimization Trajectories of Deep Neural Networks.

[3] Cohen, et al. Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability
summary_of_the_review: This paper reveals that heavy-tailed noise+gradient clipping can help SGD eliminate the sharp minima. Beautiful theoretical analysis and insightful numerical experiments are provided.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies gradient descent with injected power-law tail noise. The work shows that in the infinitesimal learning rate regime, the heavy tail noise can cause GD to not to converge to sharp minima. 

Based on this theory, the paper proposes a technique to inject noise to GD to help training

main_review: I appreciate the mathematical rigor of the work, but I am not convinced by its machine learning / deep learning relevance.

Specifically, I find the following points problematic.
1. The title seems inappropriate. The word SGD is taken to mean a special kind of noise that is due to minibatch sampling. This work, however, only studies GD with injected power-law noise. I think it is misleading to say "SGD" in the title

2. The assumptions seem too strong and deep learning irrelevant. One of my main objections is that the paper assumes finitely many minima, yet, neural networks, both underparametrized and overparametrized, should have infinitely many minima, and the fact that the minima of neural networks are degenerate makes it inappropriate to apply a transition graph analysis. This then makes me think that the theoretical analysis is not relevant for deep learning

3. The main result in Theorem 2 only applies to the case when the learning rate is infinitesimal (and the limit needs to be taken under certain scaling conditions). This amounts to a continuous-time approximation, and I think is a crucial limitation of the theoretical results. The theorems reveal nothing about the behavior of SGD at a finite learning rate, which is the actual regime that SGD is run in practice. 
- Also, I feel that this continuous-time condition should be stated much earlier in the draft

4. I am unconvinced by the experiment section. Both LeNet and VGG are outdated architectures because they lack the residual structure. I would ask for evaluation on at least a modern ResNet to demonstrate the effectiveness of the proposed method
- Even if evaluated on ResNet, I still think it would not suffice because it is quite easy to improve a vanilla model; I would really want to see being able to improve some state-of-the-art results for the paper to be experimentally convincing

Other important questions (but may not constitute reasons for rejection):
1. It has been found that the power-law index of SGD noise crucially depends on the learning rate of SGD (see https://arxiv.org/abs/2106.02588, or https://arxiv.org/abs/2105.09557). How does this fact affect the theoretical results of this work?


Minor question:
1. page 3: what is "regeneration structure"?
summary_of_the_review: The following two reasons are the main weaknesses, based on which I recommend rejection:
1. The theory seems irrelevant for machine learning / deep learning
2. The experimental evaluation is weak because it uses outdated architecture and because the result only improves on badly performing vanilla training strategies

Therefore, taken as a theoretical paper, I find the theory limited and irrelevant. Taken as an experimental/method paper, I find the improvement and methodology unconvincing.
review_title: null

Meta-review: Motivated by empirical observations that SGD performed on deep networks converge to regions of flatter loss curvature relative to large or full batch GD, the authors perform a theoretical analysis of trajectories of SGD with the presence of heavy tailed noise. The primary observation of the theory is that heavy tailed noise has a higher probability of "kicking" the current parameters to a new region of the input space, which has some probability of lying in a sharper region. However, it's important to note that in this analysis SGD with heavy tailed noise doesn't stay in the sharp regions, but will eventually be kicked back out of it back to other regions. In a sense, this defines a transition graph which predicts that the steady state distribution should spend some fraction of time in different regions of the input space (and different sharpness) while never "converging" anywhere. This is shown most clearly in Figure 1 top center where the heavy tailed SGD randomly jumps between different regions of the input space throughout the entire training trajectory. Experiments are then run on deep networks showing that heavy-tailed SGD with gradient clipping converges to regions of flatter curvature. 

Reviews of the work were generally positive, the theory is well presented and Figure 1 does a solid job demonstrating the main idea. The primary criticism was raised by reviewer HGyL, arguing that the results should be largely irrelevant to deep learning. Most of the debate between this reviewer and the authors centered around whether or not ReLU networks have minima which extend off to infinity. The AC will not dig into the details of the argument. It seems clear, however, that if there were a deep learning workload with heavy tailed noise that the authors results will have some relevancy, though the exact nature of the resulting transition graph may have a complicated dependence on the loss surface. Unfortunately the authors were unable to find a such a workload in image classification (there is some prior work suggesting the NLP models with rare tokens may be a better fit) and so needed to artificially induce heavy tailed noise to test their theory. This is a bit of a limitation, but given the clear writing and interesting experiments as noted by reviewers the work seems worth accepting. The AC strongly urges the authors though to include a more lengthy discussed of Wu. et. al. as that work seems to agree with experiment of the sharpness of stable regions selected by SGD when run on deep models without heavy tailed noise.
Decision: Accept (Poster)