Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
The submission presents convergence results for clipped stochastic gradient methods without the sub-Gaussian assumption.

The subject of the submission is of interest to the NeurIPS community. As we find that some of our most difficult problems exhibit heavy-tailed noise, how to handle it in stochastic optimization is becoming more and more relevant.


My understanding of the main contributions of the paper over existing work is that this submission considers $\nu$-Hölder continuity (interpolating between Lipschitz functions and function with Lipschitz gradients) without assuming the stochastic gradients be sub-Gaussian (but still having bounded variance)
- For the case $\nu = 0$ (Lipschitz functions), recovers tighter bounds (logarithmic dependence on the confidence level $\beta$ instead of polynomial) than naïve applications of Markov's inequality to results in expectation. 
- For the case of $\nu = 1$ (Lipschitz gradient), the claimed contribution over the existing results of Gorbunov et al. [14] is that the problem need only be smooth in a ball around a minimum. 


main_review: **Update:**

I thank the authors for their response. It addressed some of my concerns and I have increased my score. 

For a potential revision, I would recommend adding emphasis on the techniques used for the theoretical contribution (what are the key result needed to relax the assumptions, and what is the insight used in the proof), and discussing what practical problems can now be solved.



---

I think the contribution of the submission that is most likely to be of interest to the community is the $\beta$-independent results on non-smooth functions. Given the assumptions and selected parameters, the results are believable although there is limited technical details in the main paper. The presentation in terms of Holder-continuity and the discussion of the need to be smooth only around the minimizer, although more general, might be of limited interest. The manuscript suffers from additional clarity issues around its motivations and does not make obvious what the new key idea or contribution is, beyond listing results. 

**Detailled comments**

- Definitions of heavy-tails

	From the introduction, it is not clear what type of gradient noise/heavy-tail model the submission consider. The introduction motivates the papers of Simsekli et al. and Zhang et al. ([34, 35, 41]) who study heavy-tailed noise in NLP models. However, those papers use a definition of heavy-tailed noise that imply that the second-moment is unbounded, contrary to the assumption in Eq. (2). I assume the definition of Heavy-tailed used in this submission is any distribution that is not sub-Gaussian but still satisfies the bounded variance assumption? Could the authors could add an example of a problem with heavy-tailed distribution that fits the bounded variance criteria?

- Missing key idea; 

	The main technical contribution is controlling the error induced by stochasticity, without light-tails, through the clipping operator and controlling its bias. While this is briefly mentioned in Section 2, p5, the technical details are left vague and relegated to the appendix.

	Similarly, while smoothness (or Holder-contuinuity) on a ball is technically weaker than smoothness on the whole space, I do not see what new ideas or proof techniques are needed to drop this assumption. It seems like a distinction without a difference, but if new ideas are needed, those should be given to the reader. 

- Limitations and parameter settings

	From the appendix, it seems that the algorithm uses an increasing batch size. I understand there is a paragraph arguing that, given a target precision $\epsilon$, one can choose parameters and a sufficiently small step-size to ensure batch-size of 1.
	However, this is not what I think of when I think of convergence guarantees as running the algorithm longer does not improve the error. 
	
	A comment explaining those limitations in the main paper, and whether they are necessary and/or common in the high-probability litterature would help the reader. 

	Also, a clarification would help: I cannot figure out how to set the parameters of the method. For example, in the setting of Thm 2.1 with $\nu = 1$, $N$ is taken to be dependent to a constant $a$ through $\propto \sqrt{a}$ in Eq. (39) (ignoring the $+1$ and $\lceil\cdot\rceil$) but right after, in line 570, $a$ is taken to be $= 2^{14} \log(4N/\beta)$. It seems those two cannot hold at the same time?
	
- Space issues

	I realise the above requests for additional details would take space. If the authors are looking for some, I would suggest moving the experimental section to the appendix. In its current state, it seems disconnected from the theoretical contributions of the submission. While they run the algorithms studied here, the experimental setting do not match the theoretical framework and I do not understand what the experiments are supposed to show beyond that the algorithms can be made to work with step-size tuning.
	
	


**Minor comments**

- Why does the entry for SGD in Tables 1 and 2, with and without ♣, have different constraints on the unbounded domain column? From my understanding, the heavy-tail version (♣) is obtained through a Markov inequality on the first
- I do not understand how Alg. 3 is "a new variant of clipped-SGD [30] properly adjusted to the class of objectives with $(\nu, M_\nu)$-Hölder continuous gradients" (207). The algorithm looks just like standard clipping and does not depend on $\nu$?
- Please cite published works instead of arXiv submissions. [20] was published at ICLR'15, [35] at ICML'19, [38] in ACL'19.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper aims to obtain the high probability convergence for the convex stochastic optimization problem when the stochastic gradient of the objective function is not assumed to be sub-Gaussian. While this goal has been achieved in two recently proposed optimizers by exploiting the gradient clippings technique under the smoothness assumption on the objective, this paper considers the more general setting when corresponding gradient only satisfies a Holder continuity condition. This condition recovers the smooth and non-smooth settings when an extra parameter takes extreme values. In such a more general problem formulation, the authors propose new step-size schemes such that the convergence rate of the aforementioned optimizers (designed for smooth problems) can be smoothly extrapolated to the non-smooth setting. 




main_review: This work provides solid convergence analyses for the recently proposed clipped-SSTM and clipped-SGD under the more general Holder continuity condition. Interestingly, the convergence rate in the smooth setting is recovered by taking the parameter $\nu$ of the Holder continuity condition to the limit of $1$. 
 
Concern:
The proposed step size scheme for the clipped-SSTM requires knowledge of the Holder parameter $\nu$ which is in general unknown. As suggested by the experiment section of this paper, $\nu$ is set to $1$ which recovers the previous clipped-SSTM. I am wondering how $\nu$ affects the performance of clipped-SSTM when it is not set to $1$, as this sets apart this work and the previous work [15] algorithmically. For clipped-SGD, I have the same concern. I believe the more general Holder continuity condition introduces extra difficulty to the analysis of the algorithm, but if we will always use $\nu=1$, the significance of the convergence under the more general condition is limited.


limitations_and_societal_impact: This is a theoretical work and I see no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors proposed  clipped-SSTM and its restart version for stochastic nonsmooth optimization with heavy tailed noise. A detailed convergence analysis shows the theoretical advantage of the proposed algorithm. Experiments on real models (Bert) show that clipped-SSTM outperforms standard SGD methods.
main_review: The paper is very clearly structure, it has addressed an important issue in designing stochastic algorithms for heavy-tailed noise. However, although this paper makes some important theoretical contribution, I think it needs a major revision to justify the true advantage in non-smooth optimization. I would recommend rejection but I am also willing to hear the author's feedback.


- The paper makes a technical contribution in showing high probability result of stochasitc algorithms when the  gradient has an biased (clipped) estimator. However, the 10 pages proof of (Theorem 2.1) is very technical, I really suggest providing a brief highlight of the proof of Theorem 2.1, which will substantially improve the readability of the theory.
- In the experiment, the paper uses $\nu=1$, which essentially assumes that the problem is smooth. This is unintuitive because the goal of this paper is for non-smooth optimization, but the results of the experiments is only able to corroborate the study [15] for smooth optimization. I understand that the assumption of Holder continuity is more general, but it is still somewhat misleading since the aim is for non-smooth optimization. I strongly suggest adding empirical study of non-smooth problems to justify the advantage of the proposed methods.
- In the experiments, what are the loss functions used by Bert and Resnet, and are the models non-smooth?
- It appears that Adam, without much tuning, already exhibits great performance. How are the parameters of Adam is chosen? I wonder what Adam performs if lr is tuned as a hyperparameter.
- Another potential weakness is that the proposed algorithm has so many hyperparameters to tune. Can the authors ellaborate some intuition for tuning those parameters.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes the clipped SGD and clipped SSTM algorithm on generalized smooth objectives with Hölder-continuous gradients. They consider the case where the assumption of sub-Gaussian noise is not needed. They modified the stepsize in the clipped SSTM algorithm to fit the Hölder-continuity assumption. Theoretical analysis is conducted with convergence rates presented. 
main_review: This paper is well-written. I have several comments below.

1. They analyze the clipped-SSTM, clipped-SGD (with/without restart trick) algorithms. These algorithms are proposed in Gorbunov et al. (2020) , and the authors extend their assumption from Lipschitz continuous gradient ($\nu=1$) to Hölder continuous gradients ($\nu \in [0,1]$). They only make one slight modification to the the clipped-SSTM algorithm which fits the Hölder continuous gradient assumption. From my perspective, this paper is a direct extension of Gorbunov et al. (2020) with the same algorithms and similar theoretical analysis. It is interesting to include the case when $\nu=0$ and the objective function may not be differentiable, but the novelty of this paper is still questionable.

2. The numerical experiments are irrelevant to the theoretical parts. In theorems, the assumption of convexity is needed where in the experiments, the authors consider two non-convex tasks. This paper is focused on the theoretical analysis with relaxed assumption for convex optimization. It seems irrelevant to run these existing algorithms on some non-convex optimization tasks, especially for the clipped-SGD algorithm, which is a classical method for deep learning tasks in the differential privacy literature. It would be better if the authors consider some tasks with convex  and possibly non-smooth objective function and check if the empirical convergence rate matches the one in their analysis.

References mentioned above:

1. Gorbunov, Eduard, Marina Danilova, and Alexander Gasnikov. "Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping." *Advances in Neural Information Processing Systems* 33 (2020): 15042-15053.
limitations_and_societal_impact: None.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper tackles the important problem of high-probability convergence bounds for machine learning optimisation problems. Traditional analyses are done in expectation, which have been shown to not accurately represent all possible training outcomes; hence the need for tighter studies.
In this paper, in the specific setting of convex, non-smooth losses with heavy tailed noise, a new high-probability bound is introduced for two algorithms. What sets it apart from previous bounds is that there is no direct negative dependency on the confidence bound (only logarithmic ones); and that in some cases it matches the non-heavy tailed noise bound.
Numerical experiments illustrating the theoretical results are presented.
main_review: This paper is part of a rich literature tackling an important problem for machine learning practitioners: is my optimisation algorithm guaranteed to converge? The motivation is convincing, the related work appears to be thorough, and the results are nicely contrasted with previous work. The paper is nicely written, and the theoretical results represent a significant advance over previous work. One small note though is that given a whole new page for the submission, a small conclusion/discussion would not have gone amiss. As it stands, the paper ends rather abruptly.

The paper does present some weaknesses, including two serious ones. 

First, the problem setting is not as general as some elements of the presentation makes it sound. Crucially, the objective function has to be convex; which automatically exclude all but the simplest neural networks. Of course, this means the results are not as significant as they would be if they covered non-convex objectives (which is not to say that they're not significant; I do believe they are).
This restriction should be more prominently featured, e.g. in the title which mentions all other characteristics but this one. The insistence on neural network applications is also a bit problematic, as those problems are non-convex (e.g. BERT training is mentioned in the introduction, and it's only on the 9th page that it appears clearly that the BERT application is only for a convex finetuning problem). At the very least this would have to be plainly stated. As it stands, a careless reader might think that these theoretical results apply to their favorite neural network application, which they unfortunately do not.
On a similar note, insisting on non-smooth might not be the best idea since the analysis covers various amounts of smoothness including smooth functions.

The second, related, issue, is that the experimental section does not properly illustrate the theoretical results. We see that the methods seem to perform fine on a convex, somewhat artificial setting (only finetuning enough so that the problem remains convex) in NLP, and the vision application is not convex at all. The claim is then that the methods work well on heavy-tailed noise distribution and are less efficient on light-tailed ones, but it might also be that they simply work worse on non-convex problems? As it stands it's hard to disentangle these different aspects.
What would ideally be presented is results on convex problems for both heavy and light-tailed noise distributions; together with potentially non-convex applications to illustrate that the methods can perform well there even if it's outside the scope of the theoretical analysis.
On a related point, the SGD used in the experiments uses momentum, contrary to the SGD that is analysed. Again, this gap in between theory and practice makes both results less relevant.

A less serious issue is the fact that the strongly convex results still rely on a uniformly bounded gradient variance assumptions, which I think is contradictory unless the assumption only applies to a bounded set? While it might be the case that the assumption is only necessary on a bounded set, I haven't seen this clearly in the paper.

An interesting point is that in the analysed setup, the effective clipping constant goes up (as the learning rate typically goes down over time). This is rather counterintuitive: at the later stages of training one expects the gradient norms to go down rather than up, which means we could use smaller clipping factors, not larger.
This leads me to the following question: is this a practical recommendation, or rather an artefact of the proof? Having a larger clipping constant helps for the proof since it reduces the bias. But on the other hand, since we increase the clipping constant in the later stages of training, where we expect comparatively lower gradient norms, are we really clipping at all anymore?

All told, this is a nice if somewhat borderline paper. I believe it could be significantly improved by following the previous recommendations, and I am open to improving my score, should fixes materialise.


There are a number of smaller elements that should be fixed to improve the paper, which I list below
- in terms of clarity it would be helpful to compare the results with fixed \nu (either 0 or 1), because as it stands understanding the actual dependencies on various parameters is quite arduous. It would also make the message clearer.
- l84, the sentence containing the equation is missing a verb?
- the exponent on the logarithm (see equation l83 for instance) is a bit unclear. If it's indeed log(x)^y it'd be easier to read written this way explicitly rather than log^y(x), as the exponent is itself quite big.
- l176 alpha_k is only defined in the algorithm box. It should also be defined in the main text
- on a related topic, the step size is alpha for clipped-SSTM and gamma for clipped-SGD. Some consistency here would be appreciated by the reader, once again.
- l175 that --> which
- in algorithm 3, line 2 the gradient at x^{k+1} is computed but then l3 it's at x^k, which I'm assuming is a typo.

limitations_and_societal_impact: I see no particular potential negative impact of this work, besides those that are standard for theoretical machine learning papers. I don't think this deserves expanding upon.
Limitations could probably use a little bit more work, as detailed in the main review.
review_title: null

Meta-review: There was a lot of discussion around this papers. The reviewers were happy with many points brought up by the authors, such as the way Adam was tuned. I also discussed the paper with the senior area chair. Ultimately, the main concern was the novelty of the results compared to Gorbunov et al. (2020). The paper at least needs a re-write to emphasize the contributions. It was also pointed that experiments were included, but weren't designed to isolate the novel assumptions. While it is true that papers can be accepted without experiments on the strength of their theory alone, the reviewers did not feel that the theoretical results were sufficiently-different for that to be the case here. 

Decision: Reject