Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors analyze SGD for a class of strongly-convex functions and under (possibly) infinite noise variance, i.e., the pth moment of the noise exists for $p \in [1,2)$, but noise variance is not assumed to be bounded. Such noise behavior is defined as heavy-tailed. Additionally, the noise is assumed to be state-dependent such that the noise vector has a component whose variance is bounded by a function of the query point (iterates). For standard analysis of SGD, noise vectors are assumed to be independent of query points and of each other.
Specifically, for a class of strongly convex functions (denoted as p-positive definite (p-PD), p=2 being positive definite Hessian) and under heavy-tailed noise, the authors:

-	Quantify the convergence rate with respect to (w.r.t.) distance to unique optimum in $L^p$, which approaches the optimal rate in strongly convex setting as $p \rightarrow 2$. This result is achieved for SGD without any modifications and under state-dependent noise model.
-	Prove that normalized Polyak-Ruppert average (uniform average) converges weakly to an $\alpha$-stable distribution, under additional assumptions on the noise and the Hessian. Central Limit Theorem (CLT) does not hold under heavy-tailed noise model.

In order to reinforce the setting they consider and verifiability of their assumptions in practice, authors discuss about the real-world examples that admit heavy-tailed noise and satisfy p-PD assumption.

main_review: This work tries to extend SGD for heavy-tailed noise for a class of strongly-convex problems satisfying p-PD condition. This condition could be interpreted as a generalization of positive definiteness of Hessian and interpolates between diagonally dominant matrices with non-negative diagonal and positive definite matrices. They also consider a more general noise model where they assume there exists a component of the noise vector that grows with the norm of the query point. In my opinion, these are the main novelties of this paper that builds onto existing work and approaches.

In that perspective, to the best of my knowledge, they adequately cite related work and explain the differences/similarities between their work and the prior ones while emphasizing their improvements.

Authors provide a set of main convergence results as well as limit behavior of the sequence generated b SGD. These results are proven in the supplementary material, however, the implications of these results are provided in the main text through intuitive remarks and technical discussions following the main theorems. Authors also try to verify their setting and validity of the assumptions via particular examples; least squares and generalized linear models.

Overall, the paper is written in a clear way. Problem setting, as well as the assumptions accompanying it are clearly stated and discussed in comparison to existing work. Main contributions are presented to the reader in a separate paragraph at the end of introduction. Main results are organized in a proper way and it is easy to follow the core contributions. Assumption 1 is not defined but referred to several times in the appendix. It is possible to deduce what was meant by Assumption 1 from the context, but it should be defined and referenced clearly. 

Relying on the existing results, behavior of stochastic methods under heavy-tailed noise has attracted attention again recently and has been studied in different contexts. 

[Zhang et al., 2020] considers heavy-tailed noise without state-dependence. Under $L$-smoothnness, they prove convergence rates for non-convex functions. Under heavy-tailed $\text{\bf stochastic gradients}$ rather than heavy-tailed noise, they show comparable convergence rate for strongly-convex functions. This paper focuses on a class of strongly-convex functions and show convergenve rates under state-dependent heavy-tailed noise. Given the results proposed by [Zhang et al., 2020], this work provides a nice generalization on the heavy-tailed noise model, but its impact is comparatively limited in terms of convergence analysis.

[Simsekli et al., 2019] considers nonconvex problems under heavy-tailed stochastic gradients. With Holder smoothness assumption on the gradient of the objective, they show convergence rates to first-order stationary points. The setting of this paper and [Simsekli et al., 2019] do not overlap and we might say the results are complementary.

As for the limiting behavior of the normalized average iterate, given the results by [Polyak and Juditsky, 1992], Assumption 3 and assumption in Eq. (4.3), Theorem 5 and 6 provide some nice results, but their significance is limited in my opinion.

Please find some of my particular comments below:
- The authors say that Eq. (4.3) is a standard assumption. I do not completely agree with this statement. Authors also state that this condition holds for Hessian Lipschitz objective, but Hessian-Lipschitzness is a rather strong assumption already.
- For proving $\alpha$-stability results, it is assumed that i.i.d. component of the noise is assumed to be in the domain of normal attraction of
an $\alpha$-stable distribution. In my opinion, this makes the results of Theorem 5 and 6 less interesting from a theoretical point of view.

limitations_and_societal_impact: They address some limitations of their results in comparison to prior work. The authors do not mention potential negative societal impact of their work. Given that this is a theory paper, the authors might have thought that it is less likely to have foreseeable negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper concerns the convergence rate of SGD with heavy-tail noise. In particular, the considered gradient noise consists of a finite-variance part (corresponds to the multiplicative noise in SGD for least square) and an infinite-variance part (corresponds to the additive noise in SGD for least square). The main results can be viewed as a law of large number and a central limit theorem in the absence of finite-variance. First the authors show that when the loss is "strongly convex" and "smooth" in the $p$-PD sense and the heavy-tail part noise has finite $p$-moment, SGD (with decaying stepsize) iterates converges to the correct optimum, and the convergence rate is justified in the p-norm sense. Moreover, if the heavy-tail noise is the domain of normal attraction of some stable distribution, then the properly normalized SGD iterates also converges to the stable distribution. Finally, the heavy-tailed noise model is justified from two linear model examples.
main_review: # Pros:
+ The paper is organized well and is particularly clear in its math (as a CS paper).
+ The presented convergence rate and CLT for SGD with heavy-tailed noise are novel in machine learning to my knowledge. I am not sure how novel these are in probability theory. 
+ Technically, the introduced p-PD notions could be interesting tools for ML people to know. Again, not sure whether or not these are interesting for probability theorists.


# Cons:
- Several important quantities are hidden in the rate in Thm3, e.g., dependence on $x_1$, condition numbers (as the hessian is assumed to be uniform $p$-PD), dimension factors, the noise $p$-moment bound, etc. This limits the importance of the theorem. The presented rate is interesting assuming the above are all constants, but more discussions on the roles of these quantities could make the result even more interesting & inspiring.
- Could you comment on SGD with constant, large stepsize and with iterate-averaging/tail-averaging? In the finite-variance cases such SGD setup achieves optimal rate & I am wondering how it would be in the infinite-variance cases. Is there essential difference other than switching to a different norm?

# Small issues:
* Eq below l.145. $delta$ could be boldface.
* l.322. coefficients -> coefficient.
* Eqs below l.652. The first inequality is not rigorous as $x^b_t$ depends on $x_t$. I believe this is easily fixable and should not affect the correctness of the final claim. Please confirm.

# Overall:
As an ML person who has limited probability background, I think this paper is clear and clean, and is a good reading for understanding SGD in the heavy-tail noise cases. However I am not sure how novel the results to probability theorists. On the one hand, the two main results, Thm3 and Thms 5/6, seem to be applications of developed large number thm and CLT from existing (and quite old) probability papers (perhaps with a little bit standard optimization tricks) --- I could miss some points here and please correct me if so. Thus I am not sure how probability theorists view these results. On the other hand, the effects of initialization, condition numbers, dimension factors, noise bound are very important for rates for ML problems, but these are all hidden in the presented result. Thus the current version is a bit unsatisfactory. It is very hard for me to make a decision, currently I lean slightly to a weak acceptance.







-----
Post-Rebuttal: I tend to maintain my original evaluation for this paper after discussions with the authors. The contribution is solid in my perspective. But there are also several technical dissatisfactions about the current results (e.g., unable to track important constants like condition number).
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the convergence theory of SGD under assumptions that does not imply finite variance of the noise of the stochastic gradient for a class of strongly convex functions. A convergence rate is proven for an existing moment of the iterates of SGD and a CLT is proven for the averaged of the iterates (towards an alpha stable distribution). 

main_review: Originality: This work studies the convergence of SGD in the case where the noise has infinite second moment. While this covers interesting practical cases, this is in contrast with most of the works on the convergence of SGD.

Quality: The convergence results are discussed in details and the paper is well written, although technical. A good literature review is provided for stochastic approximation under assumptions that do not imply finite variance of the noise. Besides, a CLT is provided for the average of the iterates, towards an alpha stable distribution. My main concern is wrt to the assumptions made in theorems. First, the work is limited to strongly convex functions and second the assumptions made on the noise do not seem easy to check. I must admit that a real effort is made to prove that the assumptions are satisfied for Ordinary Least Square and Generalized Linear Models, but this still relies on some hypotheses.

Clarity: The work is technical and more effort should be made on clarifying the paper. The intro and literature review are quite technical. The choice of alpha stable distribution in Assumption 3 is not really justified. It seems specific. Why this choice? Do we know the parameters of the alpha stable distribution? Specific questions:
- Th 5: Alpha is given by assumption 3, am I correct? Do we know alpha easily?
- l.290: "Indices"?
- Could you explain how to obtain 5.3 and l.363 ?

Significance: The work considers the infinite variance noise, which an important setting is practice. However it still requires some assumptions, so the work is not that general.
limitations_and_societal_impact: Some limitations are discussed. Another limitation is that this work relies on a lot of modelization/assumptions about the noise. Even if it is proven that this work covers OLS and GLM, I am not sure that it can go beyond.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Previous theoretical analysis of SGD algorithms for convex functions have in general assumed the finitness of the second moment of the stochastic gradient.  The current paper provides convergence rates and generalized central limit theorems under alternative assumptions on the stochastic gradient and the hessian matrices. 
main_review: The paper defines the concept of $p$-positive definitness for square symmetric matrices, for $p\ge1$. This concept generalizes the concept of positive definite matrices, and the two concepts are the same when $p=2$. Assumption 1 says that the Hessian matrices are uniformly $p$-positive definite. Assumption A2 says that the gradient noise is the sum of two components, the second of which has a finite $p$ moment. Theorem 3 shows convergence results for the SGD algorithm under Assumptions A1 and A2 for a suitable step-size. Under certain assumptions, Theorems 5 and 6 prove central limit theorems for a normalized average of iterates. The paper uses SGD without any modification. 

Theorem 3 in the paper is in the same spirit as Theorem 4 of Zhang et al Neurips 2020. While Theorem 3 in the paper requires $p$-positive definitness assumptions on the Hessians and certain assumptions on the stochastic gradients, Theorem 4 in Zhang et al requires a strong-convexity assumption and the unifom finiteness of moments of the stochastic gradients. 

The results in the paper are interesting and new to me. On the negative side, the paper contains no numerical experiments, and it is not clear whether the $p$-positive definitness assumption holds in practical applications. Below are more detailed comments or questions.

--In Assumption A2, is $\\{m_t\\}$ a martingale difference sequence with respect to $\\{\cal F_t\\}$?

--The definition of the domain of normal attraction in (4.2) does not coincide with the definition in (2.2).

--line 273: why does Assumption A3 imply that $E[|\xi_t|^p]< \infty$?

--line 340: The calculation of $E[|m_t|^2|x_{t-1}]$ involves  $E[||z_t||^2z_tz_t^T]$. So $E[|m_t|^2|x_{t-1}]$ is not always finite if the second moment of $z$ is finite.

--line 358: for logistic regressions, $y_t$ is binary in practice, and has finite second moment.

--line 112 : typo in "the only a few"


----After feedback, I increased my score----
limitations_and_societal_impact: I am not aware of negative societal impact of their work.
review_title: null

Meta-review: This paper examines the convergence of stochastic gradient descent in strongly convex minimization problems. The novelty of the analysis is that the authors do not assume that the variance of the gradient queries is finite; instead, they consider "heavy-tailed" gradient noise models with bounded moments for some $p\in[1,2)$ - but not necessarily for $p=2$ or higher.

This paper received almost universally positive reviews during the review phase, and the only "weak reject" recommendation was changed to a "weak accept" after the authors addressed the reviewer's concerns. As a result, during the committee discussion, a consensus was reached early on to make an "accept" recommendation.
Decision: Accept (Poster)