Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper gives a theoretical study of the tail behavior of the SGD in a quadratic optimization problem and explores its relationship with the curvature, step size and batch size. To prove their results, the authors approximate the SGD recursion by a linear stochastic recursion and analyze the statistical properties by the tools from implicit renew theory. Under this setting, they show that the law of the SGD iterates converge to a heavy-tailed stationary distribution depending on the Hessian structure of the loss function at the minimum and choices of the step size and batch size. They take a further step to clarify the relationship and study the moment bounds and convergence rate. 

Overall, I vote for accepting. I think the study of heavy tail phenomenon in SGD is quite a novel field and full of interest. 
1.	This paper is the first one to study the originating cause of heavy tail phenomenon in SGD and give a rigorous proof of the relationship between tail index and the choice of step size and batch size. This helps a better understanding of the generalization properties of SGD. 
2.	The paper provides comprehensive experiments to support their result. Experiments are conducted on both synthetic data and neural networks. The design of experiments is reasonable, and the results of the experiment not only support the claim that the tail index is deeply linked to the curvature of the loss and the ratio of step size and batch size but also give an insight on more general cases besides the quadratic optimization.

However, I am still concerned about the setting in the theoretical frame. This paper completes its proof under the settings of quadratic optimization and infinite streaming data, which may limit the applicability of the theoretical result. Although these issues have been discussed in this paper, whether or why this extension is feasible remains questionable.

review_title: An Insightful Paper to be accpeted

final_score: rating: 5: Marginally below acceptance threshold
review_content: The main theme of this work is to study conditions under which SGD iterations result in random variables with heavy-tail random distributions. Specifically they focus on the step size, batch size and problem dimension. First they show theoretical results showing how the tail-index of the distribution generated by SGD depends on the chosen step size, batch size and problem dimension.
These results make several assumptions limiting their scope of applicability. Namely, they are limited to quadratic optimisation problems, normally distributed data and one-pass regime of SGD. However, the authors argue that since even in this simplest setting SGD results in a heavy-tail distribution, the more complex problems should not be expected to behave otherwise.
The experiments verify the correctness of the theoretical results, but they are also of limited value. For example, the deep learning section studies a shallow fully connected network on MNIST and CIFAR10. It would be more interesting to see a model performing closer to the state of the art here.
While the main results of this work are interesting, I have a few reservations. First, as I wrote above the setting (even in experiments) is limited to the simplest case and hence is of limited value. Second, it is quite difficult to follow the theoretical results, mostly because all details are given in the Appendix, which is 30 pages long. Perhaps, this work is better suited for a journal publication, where the authors will have more space to explain their work. And finally I have some rather minor comments:
- the paper refers to equation (3) in several places of the article and the Appendix, but there is no equation (3). I had to guess to which equation they refer each time, which made reading the already technically heavy paper more difficult.
- In Theorem 4, it is not clear how "the p-th moment of the iterates are of exponentially decaying nature", since in both cases the coefficient of $\mathbb{E}\Vert q_1\Vert^p$ is larger than 1.  Also, in the second case, the coefficient's value depends on whether $\alpha<2$. What is $q_1$ here?

review_title: SGB iterations can result in heavy-tail random distribution on certain quadratic optimisation problems

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the relations between the heavy tail phenomenon of SGD and the ‘flatness’ of the local minimum found by SGD and the ratio of the step size $\eta$ to the batch size $b$ for the quadratic and convex problem. They show that depending on the curvature, the step size, and the batch size, the iterates can converge to a heavy-tailed random variable.  They conduct experiments on both synthetic data and fully connected neural networks, and illustrate that the results would also apply to more general settings and hence provide new insights about the behavior of SGD in deep learning. 
I do not have time to check the proofs and are not familiar with this topic. However the results seem to be novel and interesting. 

pros: 1, They characterize the empirically observed heavy-tailed behavior of SGD with respect to the step size, mini batch size, dimensions, and the curvature, with explicit convergence rates. 

cons:1, The theoretical analysis is only for the quadratic and convex function. The input data is Gaussian, which is quite restrictive. 

After the rebuttal.

The authors addressed my concerns. I have read other reviewers' comments. I decide to remain the current score.
review_title: Reviews for The Heavy-Tail Phenomenon in SGD

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: This paper studies the heavy-tail phenomenon in SGD. In recent years, many works either empirically or theoretically showed that the heavy-tail property of SGD leads to a better generalization performance. But no rigorous theory has been developed to explain the cause of this phenomenon. 

In this paper, the authors studied SGD iterates in solving a quadratic linear regression problem with i.i.d (Gaussian) data. In this setting, they proved the main result that shows that the tails of SGD iterates become monotonically heavier for increasing curvature, decreasing stepwise, or increasing b, hence this tends to provide a rigorous explanation of the heavy-tail phenomenon. The authors also developed other results on the law convergence and variance bounds.

Comments: Overall I think the paper is technically sound and develops rigorous proof. My main comment is that the problem studied in the paper is very idealized, I.e., a regression with iid Gaussian data. I understand that this makes the proof cleaner with compact results. However, this may not have direct implications on the heavy-tail phenomenon in deep learning. In fact, it may be more meaningful and motivated to study other simpler problems, such as binary classification with linearly separable data, in which the data structure is more practical than iid Gaussian. 

Overall, I consider the results in this paper as rigorously exploring the heavy-tail of SGD in linear regression under iid Gaussian data. I suggest the authors consider other more practical problems, and the results need not be related to deep learning. Focusing on the heavy-tail phenomenon in standard machine learning problems is already an interesting problem. 
review_title: Official Review 1

Meta-review: This work seeks to describe the heavy-tail phenomenon observed for deep networks learned with SGD. The work presents proof of a relationship between curvature, step size, batch size, and a heavy-tail weight distribution. The proofs assume a quadratic optimization problem and the authors speculate that the results may also be relevant for non-convex deep learning settings. On the positive side the reviewers agreed that this work is one of the first, if not the first, to try to theoretically describe a poorly understood phenomenon in deep learning. On the less positive side, the reviewers believe that the proofs developed in this paper are for an idealized setting that is too different from the settings under which deep models are trained. As such, even though the authors provide some (somewhat mixed) experimental results to support the claim of relevance to deep learning, the reviewers were not convinced. Given that the stated goal of the work is to attempt to explain this phenomenon in deep models, the majority view is that this work, while promising, needs further development to convincingly claim some relevance to the original phenomenon being studied.
Decision: Reject