Summary
The paper addresses a problem of (generalized) smooth non-convex optimization with heavy-tailed noise in the stochastic gradients and provides new convergence guarantees for the Normalized SGD with Momentum (NSGDM). In particular, the authors assume $(L_0,L_1)$-smoothness, which is strictly more general than standard smoothness, of the objective function, its lower boundedness (classical assumption), and boundedness of the $p$-th moment of the gradient noise for some $p \in (1,2]$, i.e., $\mathbb{E}\|\| g(x) - \nabla F(x) \|\|^p \leq \sigma_0^p + \sigma_1^p \|\| \nabla F(x)\|\|^p$ for all $x \in \mathbb{R}^d$, where $F$ is the objective function. Then, the authors provide new results for (mini-batched) NSGDM - a method proposed by Cutcosky & Mehta (2020) - under these assumptions.
The first result establishes $O(T^{-\frac{p-1}{3p-2}})$ convergence rate for $\frac{1}{T}\sum_{t=1}^T\mathbb{E}\|\| \nabla F(x_t) \|\|$ in the case when $L_0, L_1, \sigma_0, \sigma_1, \Delta_1$, and, more importantly for the paper, $p$ are known. This result matches the known lower bound (when $L_1 = 0$ and $\sigma_1 = 0$) and the best-known rates for Clipped SGD. Moreover, the result extends the known ones to the case of $L_1 > 0$ and $\sigma_1 > 0$.
The second result establishes $O(T^{-\frac{p-1}{2p}})$ convergence rate but without any prior knowledge about all parameters except of $L_1$. This rate is worse than optimal but still matches it when $p = 2$ (since it is obtained for the parameters with the dependency on $T$ as in the case of $p=2$). This result demonstrates a noticeable robustness of NSGDM.
The authors also provide a refined formulation of the lower bound from Zhang et al. (2020), though the worst-case example and the proof are largely dependent on the previous results, i.e., on the proofs from Arjevani et al. (2023).
Strengths
S1. The paper addresses an important question and makes an important contribution to the literature on stochastic optimization with heavy-tailed noise. In particular, I would like to highlight Theorem 3.6, which gives the first convergence result in the considered setting without the knowledge of $p$, and Lemma 4.3, which generalizes Lemma 7 from [1] and gives an alternative and quite simple proof to a similar result.
S2. The generality of the results is also noticeable. While most of the existing works on the stochastic optimization with the heavy-tailed noise focus on smooth problems, this paper considers $(L_0,L_1)$-smooth setup, which is known to better reflect the properties of the minimization problems arising in the training of neural networks. Moreover, bound on the $p$-th moment of the noise contains an additive term proportional to $\|\| \nabla F(x)\|\|^p$, while the previous works assume uniform boundedness of the $p$-th moment of the noise.
S3. The paper is, in general, well-written and easy to follow. I also did not find any mistakes in the proofs (though some parts could be further improved). Moreover, the authors provide intuitive explanations in the main text and the sketch of the proof, allowing to understand the key steps of the proof and also to see what the main technical novelty of the paper (which I believe is Lemma 4.3; other parts of the proof are very similar to the previous works such as [2, 3]; nevertheless, it does not undermine the contribution of the paper, in my opinion).
---
References
[1] Kornilov et al. Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance. NeurIPS 2023
[2] Cutckosky & Mehta. Momentum Improves Normalized SGD. ICML 2020
[3] Hübler et al. Parameter-agnostic optimization under relaxed smoothness. AISTATS 2024
Weaknesses
W1. When $\sigma_1 > 0$, the result of Theorem D.1 requires the knowledge of $\|\| \nabla F(x_1) \|\|$. Moreover, the theorem is formulated in such a way that all problem-related parameters are required to be known precisely.
W2. When $\sigma_1 > 0$, the results hold only for $B > 1$.
W3. The paper lacks numerical experiments. In particular, it would be very interesting to see in some (even toy) experiments how NSGDM depends on the choice of $\beta$ and whether the rate $O(T^{-\frac{p-1}{2p}})$ is indeed tight *for NSGDM* when $p$ is unknown.
Nevertheless, I believe that the strengths outweigh the weaknesses.
Questions
**Questions.**
Q1. Is it possible to prove a version of Theorem D.1 when only some upper bounds on problem-related parameters are known, i.e., upper bounds on $L_0, L_1, \sigma_0, \sigma_1, \Delta_1, \|\| \nabla F(x_1) \|\|$?
Q2. Is it possible to generalize the results of the paper to the case of $B=1$ even when $\sigma_1 > 0$? If no, could the authors provide a counter-example or an experiment illustrating that $B$ has to be larger than $1$ in this case?
Q3. Is the result for NSGDM without the prior knowledge of $p$ tight?
Q4. What is the difference between Theorem 3.3 and the result from [1]? As far as I see, the proofs are almost identical to the one from [2] (up to the difference in the choice of $q$).
Q5. Is it possible to generalize the results of this paper to the case when parameters are horizon-independent, i.e., independent of the total number of steps $T$, like in [3]?
Q6. Could the authors comment on the differences between Lemma 4.3 and Lemma 7 from [4] and add this discussion to the paper?
Q7. Line 809: why is the assumption with $\|\| x - y\|\|| \leq c/L_1$ is stronger than the one for $\|\| x-y \|\| \leq 1/L_1$? Aren't they both equivalent (up to the redefinition of $L_0$ and $L_1$) to the so-called symmetric $(L_0,L_1)$-smoothness from [5]?
**Comments.**
C1. I recommend adding the statements of the main results in the full generality to the main text, i.e., with $\sigma_1 > 0$. In my opinion, they are quite understandable for the broad audience, so they can be placed in the main text.
C2. Lines 104-106: the rate from Nguen et al. (2023) in the noiseless regime is $O(T^{-\frac{2p-1}{3p-2}})$ (for the average of the expected squared norms of the gradients), which is worse than $O(T^{-\frac{1}{2}})$.
C3. I believe that the discussion of the related work on $(L_0,L_1)$-smoothness should be extended. In particular, the authors should discuss how their results can be compared to the known results for NSGDM from [3].
C4. Line 334, "following the existing literature": the authors should provide the reference to the paper.
C5. Sketch of the proof of Lemma 4.2 on page 8: $m_0$ is undefined. I assume that $m_0 = g_1$.
C6. I suggest adding in (10) more details about the last step (that the authors used $\sum_{t}a_t b_t \leq (\sum_t a_t)(\sum_t b_t)$ for non-negative sequences).
C7. The last step in (13) is a bit technical and requires the reader to do a lot of calculations on their own. I suggest adding more details on how you estimate each term.
C8. Regarding the proof of Theorem 3.3: essentially, the proof is almost identical to the one from [2] up to the replacement of $\sigma$ with $\frac{\sigma_0^{\frac{p}{2(p-1)}}}{4\gamma \varepsilon^{\frac{p}{2(p-1)}-1}}$ because for the considered example all moments exist (though they are different). I also encourage the authors to mention explicitly that the construction in the lower bound depends on the target accuracy $\varepsilon$.
**Minor comments.**
M1. Line 16: noise, that --> noise, which
M2. Line 48: Simsekli et al. 2019 -- the same reference appear twice
M3. Line 108: should be "the results from Cutkosky & Mehta (2021); Liu et al. (2024) also depend"
M4. Line 256: Theorem 3.2 is not perfectly adaptive to $\sigma_0$ since it requires its knowledge. I suggest to rewrite this sentence.
M5. Line 324: help --> helps
M6. Line 325: smooth --> smoothness
M7. Title of Appendix C: 4.4 --> 4.3
M8. Line 855: AM-GM - better to replace abbreviation with a full version.
---
References
[1] Zhang et al. Why are Adaptive Methods Good for Attention Models? NeurIPS 2020.
[2] Arjevani et al. Lower bounds for non-convex stochastic optimization. Mathematical Programming 2023.
[3] Hübler et al. Parameter-agnostic optimization under relaxed smoothness. AISTATS 2024
[4] Kornilov et al. Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance. NeurIPS 2023
[5] Chen et al. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. ICML 2023