We thank the reviewer for the valuable comments. Below we address the reviewer's concerns.

W1&Second part of Questions. We provide a detailed comparison with [1] and [2] here.

• Comparison with [1]:
  • The major difference is that the studied problems are orthogonal. In detail, [1] considers smooth nonconvex optimization, i.e., optimizing a single objective and aiming at minimizing the gradient norm. However, we work on an online learning problem: Online Convex Optimization (OCO), where we handle a series of time-varying convex functions and want to minimize the regret. Therefore, for both objectives and metrics, [1] and our work are entirely different. Hence, whatever results [1] has obtained, they cannot be applied to our setting.
  • Next, from a technical view, [1] considers both gradient normalization and momentum, which is far from our work. Concretely, [1] has shown these tricks work for heavy-tailed smooth nonconvex optimization, but this doesn't mean they are effective for heavy-tailed OCO, since, again, the studied problems are distinct and their analysis is tailored for nonconvex problems. Moreover, the results in [1] cannot reflect whether OGD/DA/AdaGrad works for heavy-tailed OCO, as none of these algorithms employ normalization or momentum. So the technical ideas described in our Section 3 are independent of [1] and hence novel.
• Comparison with [2]:
  • Although [2] also considers OCO with heavy tails, their motivation largely differs from ours as discussed in Lines 83-88:

    They aim to solve heavy-tailed OCO with a new proposed method that contains many nontrivial technical tricks, including gradient clipping, artificially added regularization, and solving the additional fixed-point equation. However, their result cannot reflect why the existing simple OCO algorithms like OGD work in practice under heavy-tailed noise. In contrast, our goal is to examine whether, when, and how the classical OCO algorithms work under heavy tails, thereby filling the missing piece in the literature.

  • Next, from a technical view, OGD/DA/AdaGrad contains none of the tricks employed in the algorithm of [2] (i.e., gradient clipping, regularization, and solving the fixed-point equation as mentioned above). Therefore, any proof technique in [2] used to handle the heavy-tailed noise cannot be applied to show that OGD/DA/AdaGrad has a finite regret, not to mention the optimality of these algorithms. As such, we need to analyze from scratch and find a new approach. Due to this, the ideas presented in Section 3 should be viewed as the main technical innovation of our work, as they cannot be found in [2] or anywhere in the existing OCO literature.
  • Moreover, the novelty of our techniques can also be reflected in the results. First, the regret bound $GD\sqrt{T}+\sigma DT^{1/\mathsf{p}}$ of all three algorithms proved in our work is optimal in all parameters (see also our response to First part of Questions below). In contrast, the regret bound $(G+\sigma)DT^{1/\mathsf{p}}$ shown by [2] is not. This indicates that our analysis is tight, which is again due to our novel technique. Second, our result for AdaGrad is particularly interesting since it is adaptive to all problem-dependent parameters (i.e., $G$, $\sigma$, and $\mathsf{p}$). However, [2] requires all of them in their algorithm.

W2. We believe our study has its own worth even without newly proposed algorithms or any principled modification, due to the following reasons.

• First, from a purely theoretical perspective, we provide a new way to analyze classical OCO algorithms under heavy tails. Importantly, it helps us establish the first entirely optimal regret bound for heavy-tailed OCO, which we believe is an important contribution. Moreover, what we view as particularly valuable in the new analysis is its simplicity, while remaining insightful, which makes the proof clear and accessible, as pointed out by the reviewer. We believe this balance of depth and reader-friendliness is particularly precious in nowadays theoretical work.
• Next, applications in Section 4, based on our new optimal regret bounds established in Section 3, also provide interesting theoretical results. For example, the first optimal convergence rate of SGD for nonsmooth convex optimization under heavy tails, which even holds for the last iterate. As commented by another Reviewer pPe8, this may shed light on some phenomena during training LLMs. Furthermore, we also show how to optimize nonsmooth nonconvex objectives and give the first provable result without gradient clipping in Corollary 3, which not only improves over the best existing sample complexity of [4] but is also the first time to explain their experimental observation, i.e., good empirical performance of OGD + O2NC even without gradient clipping. Additionally, we also tackle the question explicitly asked by [4]: how to establish a provable result for the case where problem-dependent parameters are unknown in advance. For more details, we kindly refer the reviewer to Lines 310-312.
• Moreover, one important implication on the practical side is to reverse the popular view that gradient clipping is necessary for SGD when facing heavy tails, and (partially) answer why many existing algorithms already work very well in practice, which we believe can help the community understand more deeply about many popular optimizers. Hence, closing the gap between practice and theory, which is the aim of this study, is a valuable task.
• Lastly, we also want to mention that providing a better theoretical understanding of existing algorithms is important and popular among the optimization and even the broader ML community. To name a few:
  • SGD was invented last century [5]. Understanding its convergence theory remains a central topic among the optimization community. For example, its rate for nonconvex problems is not known until the seminal work [6], approximately 60 years after the birth of SGD. After another 10 years, [7] further explores the high-probability convergence of SGD and pushes forward the frontier of its theoretical study. Therefore, the way of showing new convergence theory for existing algorithms never ends.
  • Another popular algorithm, Adam, was introduced by [8] in 2014, perhaps the most famous variation of AdaGrad studied in this work. Even in recent years, many works are still trying to understand its convergence property for nonconvex optimization under various settings. For example, see [9, 10].
  • Going beyond optimization, let's take the classical mean estimation problem as an example, which plays an important role in different areas, e.g., ML/TCS/Statistics. The median of means estimator was introduced by [11] last century, but its theoretical research has remained popular in the past decades, as summarized in [12]. Even in 2025, the new study of it still shows up [13].

Based on the above points, we believe our work makes a solid contribution to the community.

First part of Questions. As described in our work, the optimal lower bound should be in the order of $GD\sqrt{T}+\sigma DT^{1/\mathsf{p}}$.

• The first part $GD\sqrt{T}$ is the standard lower bound for deterministic OCO. For its proof, see, e.g., Section 5.1 of [14].
• The second part is based on the reduction to stochastic convex optimization (SCO). Simply speaking, any lower bound for heavy-tailed SCO also applies to OCO. To see this fact, one can take $\ell_t=F, \forall t\in[T]$. Thus, standard lower bounds from heavy-tailed SCO can be translated to $\sigma DT^{1/\mathsf{p}}$. For its proof, see, e.g., Section 4 of [15], Theorem 3 of [16], or Section 5.3.1 of [11].
• Combining the above two results, we have the lower bound $GD\sqrt{T}+\sigma DT^{1/\mathsf{p}}$. A discussion essentially the same as above can be found in Lines 89-95.

References.

[1] Liu, Z., & Zhou, Z. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. ICLR 2025.

[2] Zhang, J., & Cutkosky, A. Parameter-free regret in high probability with heavy tails. NeurIPS 2022.

[3] Cutkosky, A., et al. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. ICML 2023.

[4] Liu, L., et al. High-probability bound for non-smooth non-convex stochastic optimization with heavy tails. ICML 2024.

[5] Robbins, H., & Monro, S. A stochastic approximation method. The annals of mathematical statistics 1951.

[6] Ghadimi, S., & Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIOPT 2013.

[7] Liu, Z., et al. High probability convergence of stochastic gradient methods. ICML 2023.

[8] Kingma, D. P., & Ba, J. Adam: A method for stochastic optimization. ICLR 2015.

[9] Li, H., et al. Convergence of adam under relaxed assumptions. NeurIPS 2023.

[10] Wang, B., et al. Closing the gap between the upper bound and lower bound of Adam's iteration complexity. NeurIPS 2023.

[11] Nemirovskij, A. S., & Yudin, D. B. Problem complexity and method efficiency in optimization. 1983.

[12] Lugosi, G., & Mendelson, S. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics 2019.

[13] Møller Høgsgaard, M., & Paudice, A. Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means. ICML 2025.

[14] Orabona, F. A modern introduction to online learning. arXiv:1912.13213.

[15] Vural, Nuri Mert, et al. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. COLT 2022.

[16] Raginsky, M., & Rakhlin, A. Information complexity of black-box convex optimization: A new look via feedback information theory. Allerton 2009.

We thank the reviewer for the detailed feedback. Below we address the reviewer's concerns.

Technical Contribution.

• We believe our technical ideas are novel and insightful (as also commented by Reviewers pPe8 and crhG) since they have not been proposed in the OCO literature before and could be extended to broader situations, e.g., Online Mirror Descent (see also our response to W2&Q1 for Reviewer crhG). Based on our ideas, we provide the first finite regret bounds for OGD/DA/AdaGrad and, remarkably, they are entirely optimal in all parameters, which has never been achieved in heavy-tailed OCO. Therefore, these new ideas address an almost empty part of the literature. Due to the above, we believe they contain sufficient technical contributions to the community, regardless of whether the ideas themselves are simple or not (indeed, we believe the simplicity is another advantage of our work, see below).

• The contribution of our techniques can also be evident in the results in Section 4. Our new bounds for both nonsmooth convex and nonconvex optimization are better than existing works. These improvements are again due to our novel techniques.

• Of course, our ideas are simple, but we view this simplicity as particularly valuable in today's theoretical research. One of the ultimate goals of a theoretical study, we believe, should help people understand/explain the algorithms, which is also the motivation for our work as asked in Line 53. Technical sophistication could be a part of theoretical research, but it is only a means, not the destination. Especially in the case where new but simple ideas are sufficient and effective like our work, technical complexity is unnecessary and should be avoided, in our opinion.

Organization (Related to W2).

• From a reader's perspective, especially one not familiar with theory, we believe the analysis in Section 3 is still necessary. Though it doesn't deviate from the standard way too much, it contains new technical ideas that we want to convey, and its structure is carefully designed for those knowing little about this area. It may seem redundant for experts like reviewers, but considering the broad audience of NeurIPS, we think it is still valuable.

• For Section 4, as its title suggests, all about applications based on the new regrets shown in Section 3. With no doubt, it contains new and interesting theoretical results, but we emphasize that heavy-tailed OCO is the primary focus of this work, then applications. Moreover, because Section 4 requires some external knowledge for readers (e.g., Lemma 1 or the basics of Section 4.1), it can be recognized as an advanced topic. Hence, we only give it necessary but less weight than Section 3 to prevent overburdening readers. Lastly, we kindly remind the reviewer that Appendix E includes more background, discussions, and details of Section 4.1.

• In summary, the current organization is to balance reader-friendliness and depth. But as suggested by the reviewer, we would try to condense Section 3 and, if more room is available, expand Section 4.

For other weaknesses:

W1. We are not sure what the reviewer meant by this point. For both Sections 4.1 and 4.2, we have included different related works in sentences, e.g., Lines 219, 220, 228, 229, 256, 264, 265, 267, 273. If the reviewer refers to the related works on heavy-tailed OCO, then [1] is the only work we know so far. If the reviewer thinks we missed any particular related work, we are happy to discuss and add it in the revision.

W3. For both Definition 1 and the concept of $K$-shifting regret, we borrow it from [2] without modification and point the reader to the corresponding place in [2]. We currently do this because:

• Definition 1 itself was also evolved from works even earlier than [2], as stated in Section 2.1 of [2]. Providing every detail is hence not tractable and could distract the reader from the central topic of our work.

• The $K$-shifting regret appears naturally in the proof of Theorem 7 of [2] (or Lemma 2 in our paper), which we invoke as a black box. Thus, the $K$-shifting regret is also presented in a black-box way.

As per the reviewer's suggestion, we plan to add some information on these two notions in the revision to improve the readability.

W4&W5. The main innovation of our work over [2] is showing 1. Theorem 4: O2NC is effective under heavy-tailed noise without any modification; 2. Theorem 5: Three concrete options for $\mathsf{A}$ in O2NC are given with provable rates, based on new regrets shown in Section 3.

• For the first point, the proof in [2] only works for $\mathsf{p}=2$. Specifically, a key step to analyze O2NC is bounding $\mathbb{E}\left[\left\Vert\sum_{n=1}^T\boldsymbol{\epsilon}\_n\right\Vert\right]$. If $\mathsf{p}=2$, [2] applies Hölder’s inequality to obtain $\mathbb{E}\left[\left\Vert\sum_{n=1}^T\boldsymbol{\epsilon}\_n\right\Vert\right]\leq\sqrt{\mathbb{E}\left[\left\Vert\sum_{n=1}^T\boldsymbol{\epsilon}\_n\right\Vert^2\right]}\leq\sigma\sqrt{T}$, where the last step is by $\mathbb{E}\left[\left\langle \boldsymbol{\epsilon}\_n,\boldsymbol{\epsilon}\_m\right\rangle\right]=0,\forall n\neq m$ and $\mathbb{E}\left[\left\Vert\boldsymbol{\epsilon}\_n\right\Vert^2\right]\leq\sigma^2$. However, this derivation fails immediately whenever $\mathsf{p}<2$, as $\mathbb{E}\left[\left\Vert\boldsymbol{\epsilon}\_n\right\Vert^2\right]$ can be $+\infty$ now. Thus, we have to bring up an alternative to bound $\mathbb{E}\left[\left\Vert \sum_{n=1}^T\boldsymbol{\epsilon}\_n\right\Vert\right]$. Fortunately, an existing inequality can be borrowed to deal with the case (see Lemma 3 in the paper). As such, the proof of Theorem 4 certainly differs from [2]. Due to the limited space, we cannot expand everything here and kindly refer the reviewer to Appendix E.2 for more details.

• The second point is also important. Because, to apply Theorem 4, we still need to find an OCO algorithm having a finite $K$-shifting regret in expectation under heavy tails. However, whether such an algorithm exists and, if so, what it is remains unclear, as, again, everything in [2] is only for $\mathsf{p}=2$ and hence cannot be directly applied in our setting. Luckily, due to our new regret bounds shown in Section 3, we can confidently set $\mathsf{A}$ to be OGD/DA/AdaGrad (though the $K$-shifting regret slightly differs from the standard regret, results in Section 3 are enough, see Lines 668-672 for details). In other words, the proof of Theorem 5 builds on top of Theorem 4 and Section 3, both of which cannot be obtained by [2].

• In summary, both Theorems 4 and 5 cannot be concluded from [2], and we prove them in a new way. From the results side, they generalize the case $\mathsf{p}=2$ in [2] to $1<\mathsf{p}\leq2$.

Remark. Due to character limitations for rebuttal, we also invite the reviewer to go through Appendix E, which includes more information about Section 4.1, particularly Theorems 4 and 5.

For other issues mentioned by the reviewer, we believe none of them have any technical flaws and would like to clarify them below.

Issue 1. It holds by $\boldsymbol{x}\_{t+1}=\Pi_{\mathcal{X}}(\boldsymbol{x}\_t-\eta\_t\boldsymbol{g}\_t)=\mathrm{argmin}\_{\boldsymbol{x}\in\mathcal{X}}\frac{1}{2}\left\Vert\boldsymbol{x}-\boldsymbol{x}\_t+\eta\_t\boldsymbol{g}\_t\right\Vert^2\overset{(a)}{\Rightarrow}\left\langle\boldsymbol{x}\_{t+1}-\boldsymbol{x}\_t+\eta\_t\boldsymbol{g}\_t,\boldsymbol{x}\_{t+1}-\boldsymbol{x}\right\rangle\leq0,\forall\boldsymbol{x}\in\mathcal{X}$, where $(a)$ is by the optimality condition (i.e., $\boldsymbol{y}=\mathrm{argmin}_{\boldsymbol{x}\in\mathcal{X}}h(\boldsymbol{x})\Rightarrow\left\langle\nabla h(\boldsymbol{y}),\boldsymbol{y}-\boldsymbol{x}\right\rangle \leq0,\forall\boldsymbol{x}\in\mathcal{X}$ for any convex $\mathcal{X}$). We then obtain the corresponding inequality after rearranging terms. We didn't see a way to conclude it directly from the non-expansive property of convex projection, but we are happy to discuss it with the reviewer.

Issue 2. The description “$1/\eta_0$ should be read as $0$” is to guarantee the inequality above Line 578 is well-defined. Concretely, we need to make sure that when $t=1$, the notation $1/\eta_0$ is well-defined in every step above Line 578. Therefore, this is not a typo.

Issue 3. We remark that the corresponding inequality can also be reasoned from Hölder’s inequality: for any random variable $X>0$, there is $\mathbb{E}\left[X^{1/\mathsf{p}}\right]\overset{(a)}{\leq}\left(\mathbb{E}\left[X\right]\right)^{1/\mathsf{p}}\left(\mathbb{E}\left[1^{\mathsf{p}\_\star}\right]\right)^{1/\mathsf{p}\_\star}=\left(\mathbb{E}\left[X\right]\right)^{1/\mathsf{p}}$, where $(a)$ is due to Hölder’s inequality and $\mathsf{p}\_\star=\mathsf{p}/(\mathsf{p}-1)$ is the conjugate of $\mathsf{p}$. Let $X=\sum_{t=1}^{T}\left\Vert \boldsymbol{\epsilon}_t\right\Vert ^{\mathsf{p}}$ recover the inequality under Line 582.

Issue 4. We call it suboptimal since it cannot automatically recover the optimal rate $GD/\sqrt{T}$ in the deterministic case (i.e., $\sigma=0$). In other words, the optimal rate should be in the form of $GD/\sqrt{T}+\sigma D/T^{1-1/\mathsf{p}}$ as achieved by our work ($\sigma^{\mathsf{p}}$ in both Corollaries 1 and 2 is a typo, we have fixed it to $\sigma$). A similar discussion can be found in Lines 220-222.

Issue 5. The output of $\mathsf{A}$ can be viewed as a displacement, and we have never referred to it as the location of the next step. We use $\boldsymbol{x}_t$ for consistency with the previous sections, and in particular with the notation system specified in Section 2 (especially, Remark 2).

References.

[1] Zhang, J., & Cutkosky, A. Parameter-free regret in high probability with heavy tails. NeurIPS 2022.

[2] Cutkosky, A., et al. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. ICML 2023.

We thank the reviewer for the further comments. However, we don't understand why the reviewer asserts that we ignored the reviewer's comment and showed unwillingness. We provide a detailed explanation below.

For W1, as in our rebuttal:

We are not sure what the reviewer meant by this point. For both Sections 4.1 and 4.2, we have included different related works in sentences, e.g., Lines 219, 220, 228, 229, 256, 264, 265, 267, 273. If the reviewer refers to the related works on heavy-tailed OCO, then [1] is the only work we know so far. If the reviewer thinks we missed any particular related work, we are happy to discuss and add it in the revision.

We are not even sure what the reviewer means. Could the reviewer clarify this point? Moreover, we also stated that we are happy to add any related references if the reviewer thinks we have missed.

For W2, as in our rebuttal:

In summary, the current organization is to balance reader-friendliness and depth. But as suggested by the reviewer, we would try to condense Section 3 and, if more room is available, expand Section 4.

As explained previously, we first summarized the behind mindset of the current structure, but second, we stated that we will try to condense Section 3 and expand Section 4.

For W3, as in our rebuttal:

As per the reviewer's suggestion, we plan to add some information on these two notions in the revision to improve the readability.

Hence, we also directly followed the point mentioned by the reviewer.

For W5, we have answered it with W4 together. If the reviewer thinks any point in that discussion about Theorems 4 and 5 is inadequate/unclear, please let us know, and we are happy to answer in more detail.

We hope the above explanation addresses the reviewer's concern, and we are always happy to discuss with the reviewer if there is anything unclear.

We thank the reviewer for the appreciation of our work and the proof technique. Below we address the reviewer's concerns.

W1. Thanks for bringing this point. It is worth noting that, in reality, people simply run SGD (i.e., OGD for stochastic optimization) and AdaGrad (or its successor, say, Adam) on $\mathbb{R}^d$ without any projection step for many tasks that have heavy tails, e.g., training LLMs. It is widely known that these algorithms perform well in practice. Hence, as discussed in Lines 47 to 52, their surprisingly effective performance highly motivates this work. In addition, we believe that the popularity of these algorithms is sufficient to reflect their good practical performance when the constraint is unbounded. Thus, we currently do not discuss much on this, but we are happy to add more if there is any point that the reviewer thinks particularly valuable. Of course, our current theory is inadequate to explain their success in this unbounded setting, which we would like to leave as future work, as mentioned in Section 5.

W2&Q1. Indeed, our work can generalize to Mirror Descent/Regularized Dual Averaging with almost no additional effort. More concretely, taking the proof for OGD as an example, the proof in Lines 136-153 does not involve any specific property of the Euclidean norm. Therefore, based on almost the same idea, one familiar with the proof of Online Mirror Descent (OMD) (even in the presence of a regularizer) can extend the analysis to OMD directly. In fact, we have also briefly mentioned this fact in Remark 1 (Lines 104-105), and are happy to elaborate more on this point in the revision when more space is permitted. Similarly, our core idea also works for Regularized Dual Averaging.

However, considering NeurIPS has a broad audience including those who may not be experts in optimization theory, we finally decided to keep it simple in the current form, as it already contains many results for the reader to digest. Moreover, the currently presented results can directly relate to SGD (i.e., OGD for stochastic optimization), which we believe could help the reader immediately catch one of the key messages conveyed by our work, that is, gradient clipping may be unnecessary for heavy-tailed noise.

In summary, showing more general results based on our new proof idea is doable, we finally chose the current form to balance depth and reader-friendliness of the work.

Q2. This is an insightful question. Adapting to the strongly convex parameter is an interesting topic that is worth studying. However, we currently don't think it could be easily achieved based on existing methods. This is because, as far as we know, all the existing algorithms that can achieve this desired property assume that $\boldsymbol{g}_t$ is bounded by a constant $G$ almost surely (or a time-varying constant $G_t$), including the MetaGrad algorithm mentioned by the reviewer. However, in our work, we only assume that $\mathbb{E}\left[\boldsymbol{g}_t\right]$ is bounded. These two conditions are essentially different, i.e., a random variable that has a finite mean value (regardless of whether it is heavy-tailed or not) doesn't imply it is almost surely bounded. Due to this, adapting to the strongly convex parameter based on existing algorithms would fail.

Moreover, even considering $\mathsf{p}=2$, the classical finite variance condition, we do not know of any OCO algorithm that can adapt to the strongly convex parameter. Therefore, achieving this point may not be an easy task, which we hope can be addressed in the future.

Q3. Thanks for the interesting question. Honestly, we are not familiar with second-order methods on either the theoretical or practical side. Therefore, to not mislead the reviewer, we can only answer that we don't know. But one point we would like to say is that the core inequalities (3), (4), and (5) hold independent of any OCO/stochastic optimization algorithm. Therefore, extending to second-order methods may be possible.

We thank the reviewer for the endorsement of our work. Below we address the reviewer's concerns.

Weakness. We thank the reviewer for suggesting the potential relationship between our work and other broader areas that we were not aware of before. We are happy to read, think about them, and add some discussions in the revision if more space is allowed.

Question. To clarify, [1] only proved an upper bound $(G+\sigma)DT^{1/\mathsf{p}}$ (up to extra logarithmic factors) and did not prove any lower bound. In the deterministic case (i.e., $\sigma=0$), their upper bound is still applicable and will degenerate to $GDT^{1/\mathsf{p}}$, which is however far from the optimal lower bound $GD\sqrt{T}$ for deterministic OCO. In other words, their bound is not entirely optimal. Our discussion in Section 1.2 aims to bring this issue to the reader's attention.

References.

[1] Zhang, J., & Cutkosky, A. Parameter-free regret in high probability with heavy tails. NeurIPS 2022.