Tight High-Probability Bounds for Nonconvex Heavy-Tailed Scenario under Weaker Assumptions

Our analysis is non-trivial.

$\bullet$ Based on the bounded gradient assumption and the criterion in expectation, it is trivial to extend to $(L_0, L_1)$-smoothness by choosing the step size. There are works [4, 5] to extend the standard smoothness to the $(L_0, L_1)$-smoothness in the heavy-tailed noise. They are all based on criterion in expectation and even rely on bounded stochastic gradients. The criterion in expectation helps to tighten the upper bound of the error. For example, there is $\mathbb{E}_t\|\theta_t^a\|^2 \leq 10\sigma^p\lambda^{2-p}$ but only $\|\theta_t^a\|^2 \leq 4\lambda^2$ without expectation operation, where $\lambda = \mathcal{O}(T^{\frac{1}{3p-2}})$. The bounded stochastic gradient can be used to handle unbounded variance by decomposing it into $p$-th moment and gradient norm. However, based on the high-probability analysis, it is non-trivial to extend the standard smoothness to the $(L_0, L_1)$-smoothness. On the one hand, some error terms in high-probability criterion are larger than those in expectation criterion. For example, there is $\mathbb{E}_t\|\theta_t^a\|^2 \leq 10\sigma^p\lambda^{2-p}$ in expectation but only $\|\theta_t^a\|^2 \leq 4\lambda^2$ in high-probability. On the other hand, we remove the bounded gradient assumption. Thus, it is difficult to handle $(L_0, L_1)$-smoothness only by choosing step sizes. Nevertheless, we provide an improved high-probability analysis only under $(L_0, L_1)$-smoothness and heavy-tailed noise assumptions.

$\bullet$ Eq. (15) is a basic tool for handling heavy-tail noise. Many works [1, 2, 3] also depend on such results. Although our analysis depends on Eq. (15), there are many differences compared with [29].

New challenges

$(L_0, L_1)$-smoothness leads to the following challenges: Firstly, obtaining an upper bound on the gradient $\|\nabla F_S(x_t)\|$ is difficult because it is hidden in an inequality. Secondly, we need to construct a new martingale difference sequence to handle the term $L_1\|\nabla F_S(x)\|$ in $(L_0, L_1)$-smoothness. The two factors complicate choosing hyper-parameters $\lambda$ and $\eta$.

Novel contributions

By induction, we deduce that the gradient $\|\nabla F_S(x_t)\|$ needs to satisfy the quadratic inequality, $\|\nabla F_S(x_t)\| \leq \sqrt{4(L_0 + L_1\|\nabla F_S(x_t)\|)\Delta_1}$, so that the gradient $\|\nabla F_S(x_t)\|$ can be controlled under the $(L_0, L_1)$-smoothness when $\lambda$ is greater than a constant. In addition, we construct a new martingale difference sequence, $\sum_{t=0}^{l-1}(2\eta - L_0\eta^2 - L_1\eta^2\|\nabla F_S(x_t)\|)\langle X_t, \theta_t^a\rangle$, where X_t = \left\\{\begin{matrix}-\nabla F_S(x) & \text{if } \Delta_t \leq 2\Delta_1 \newline 0 &\text{otherwise} \end{matrix}\right., and bound it by the Freedman’s inequality. Finally, by solving the inequality w.r.t. the clipping parameter $\lambda$, we obtain a better parameter setting for step size $\eta$, thereby achieving a better convergence rate $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^\frac{2p-2}{2p-1}\frac{T}{\delta})$, compared with$\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^2\frac{T}{\delta})$ in work [29].

Detailed comparisons between our paper and [29].

(1) Different technologies. Under standard smoothness, [29] uses induction and construct a martingale difference sequence

U_s^t = \left\\{\begin{matrix} 0 & s = 0\newline \text{sgn} \left(\sum_{i=1}^{s-1} U_i^t\right) \frac{\langle \sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a, \beta^{t-s}\theta_s^a\rangle}{\|\sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a\|} & s\neq 0 \text{ and } \sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a \neq 0\newline 0 & s\neq 0 \text{ and } \sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a = 0\end{matrix}\right.

to bound errors, where $s \in \{0\} \cup [t]$ and $\beta = 1 - T^{-\frac{p}{3p-2}}$, while we construct a new martingale difference sequence $\sum_{t=0}^{l-1}(2\eta - L_0\eta^2 - L_1\eta^2\|\nabla F_S(x_t)\|)\langle X_t, \theta_t^a\rangle$ and solve a quadratic inequality about gradient $\|\nabla F_S(x_t )\|$ to bound errors.

(2) Different intermediate results. As we propose new technologies above to deal with $(L_0, L_1)$-smoothness, our inductive Lemma 6 is very different from Lemma 8 in [29], which plays a key role in proving convergence rate. Due to different martingale difference sequences, each term in our Lemma 6 needs to be rebounded rather than simply extending the results in Lemma 8 in [29].

(3) Better convergence rates under weaker assumptions. [29] achieves the convergence rate $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^2\frac{T}{\delta})$ but depends on standard smoothness of $F_S(x)$. Our analysis is based on the general $(L_0, L_1)$-smoothness and achieves better convergence rate $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^{\frac{2p-2}{2p-1}}\frac{T}{\delta})$ as shown in Table 1.

(4) Generalization. We prove the generalization bounds for CL and FL but the work [29] did not discuss this issue. To the best of our knowledge, our paper is the first work that provides the generalization bound under the heavy-tailed noise and $(L_0, L_1)$-smooth setting.

(5) Federated case. We propose the novel FedCBG algorithm for heavy-tailed federated setting. More importantly, we propose novel error estimations as shown in Lemmas 1 and 2 to obtain the nearly optimal convergence rate. Thus, it is non-trivial to extend our technology to the federated setting. But [29] did not consider the federated case.

[1] Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS.

[2] Li. High probability analysis for non-convex stochastic optimization with clipping. ECAI 2023.

[3] Cutkosky. High-probability bounds for non-convex stochastic optimization with heavy tails. NeurIPS, 2021.

[4] Liu. Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping. ICLR.

[5] Zhang. Why are adaptive methods good for attention models? NeurIPS, 2020.

Estimation techniques for $(L_0, L_1)$-smoothness.

Challenges

$(L_0, L_1)$-smoothness leads to the following challenges:

1. Obtaining an upper bound on the gradient $\|\nabla F_S(x_t)\|$ is difficult because it is hidden in an inequality.
2. We need to construct a new martingale difference sequence to handle the term $L_1\|\nabla F_S(x)\|$ in $(L_0, L_1)$-smoothness.

These two factors complicate the selection of hyper-parameters $\lambda$ and $\eta$.

Novel estimation techniques

1. By induction, we deduce that the gradient $\|\nabla F_S(x_t)\|$ needs to satisfy the quadratic inequality $\|\nabla F_S(x_t)\| \leq \sqrt{4(L_0 + L_1\|\nabla F_S(x_t)\|)\Delta_1}$ so that the gradient $\|\nabla F_S(x_t)\|$ can be controlled when $\lambda$ is greater than a constant.
2. We construct a new martingale difference sequence $\sum_{t=0}^{l-1}(L_1\eta^2\|\nabla F_S(x_t)\| - \eta)\langle \nabla F_S(x_t), \theta_t^a\rangle$ and bound it by the Freedman’s inequality.
3. By solving the inequality w.r.t. $\lambda$, we obtain a better parameter setting about $\eta$, thereby achieving a better convergence rate $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^\frac{2p-2}{2p-1}\frac{T}{\delta})$.

We will add these details to the revised version.

The first generalization result under $(L_0, L_1)$-smoothness

To the best of our knowledge, there is no work to analyze the generalization bound under $(L_0, L_1)$-smoothness. We propose a new analytical method base on uniform convergence to quantify generalization ability only under weaker assumptions (i.e., $(L_0, L_1)$-smoothness and heavy-tailed noise), which is shown in Section 4.2.

It is non-trivial to extend the analysis in CL to FL.

Extending CL to FL will cause the error term $A \leq \mathcal{O}((mKT)^\alpha), \alpha > 0$ in Eq. (66), which restricts $\gamma \leq \mathcal{O}((mKT)^{\frac{-p-1}{3p-2}})$. A nearly optimal convergence rate requires $\gamma \geq \mathcal{O}((mKT)^{\frac{-p}{3p-2}})$, resulting in a contradiction. Firstly, we proposed the clipped mini-batch gradient and analyzed the batch gradient variance under heavy-tailed setting in Lemma 1, which open the door to analyze the mini-batch methods in the heavy-tailed noise. Secondly, different from Eq. (15) in the CL, we prove the upper bound for errors $\epsilon_t^a$ and $\epsilon_t^b$ as shown in Lemma 2. They are the new results under the federation setting. Thirdly, we propose a "sum-aggregation" as shown in Algorithm 2 to facilitate our proof. Finally, $(L_0, L_1)$-smoothness makes the gradient implicit in Ineq. (61) and we handle it by solving a quadratic inequality. Thus, such expansion is non-trivial. To address your concerns, we will add a discussion in our revised version.

About the logarithm factor $\log(\frac{T}{\delta})$.

It is possible to obtain a convergence bound with $\log(T/\delta)$ order as in [1]. In fact, the work [29] achieves this result. Note that they are all based on the criteria $\frac{1}{T}\sum_{t=1}^T\|\nabla F_S(x_t)\|$. According to Jensen's inequality, our convergence rate is $\mathcal{O}(T^\frac{1-p}{3p-2}\log^\frac{p-1}{2p-1}\frac{T}{\delta})$ based on this criteria, which is better than [6] [29] w.r.t. $\log(T/\delta)$ order due to $\frac{p-1}{2p-1} \in (0, \frac{1}{3}]$. Although this improvement is not significant, it is achieved under the weaker $(L_0, L_1)$-smoothness assumption.

In the heavy-tailed noise, the lower bound in expectation is $\mathcal{O}(T^{\frac{2-2p}{3p-2}})$ [2] and it proves that global clip (GClip) algorithm can achieves this lower bound. But in high-probability analysis, the lower bound is unknown, and it is not clear whether the logarithm factor can be completely removed. This is also one of our future research directions.

[6] Ashok. High-probability bounds for non-convex stochastic optimization with heavy tails. NeurIPS, 2021.

[7] Zhang. Why are adaptive methods good for attention models?. NeurIPS, 2020.

About weaknesses

$\bullet$ Under the bounded variance assumption, SGD can achieve convergence rate $\mathcal{O}(T^{-1/4})$, which is consistent with our results when $p = 2$. However, under the heavy-tailed noise assumption, clipped SGD performs better than SGD. Clipped SGD converges under heavy-tailed noise, while standard SGD may diverge [1].

$\bullet$ Thanks for your comments. The work [2] proposed a high-probability analysis for clipped SGD and achieved the convergence rate of $\mathcal{O}(T^{\frac{1-\alpha}{\alpha}})$. Although it eliminates the bounded gradient assumption, its convergence rate is worse than advanced one in [3]. The work [4] considers the distributed setting but under the convexity assumption, which limits its scope of application. To address your concerns, we will discuss the two works in our revised version.

$\bullet$ Thanks for your comments. $\Delta_t = F_S(x_t) - F^*$ and $R$ and $\mathcal{R}$ are constants. They do not affect the convergence rate results. $A_1$ $A_2$ $A_3$ are defined in Eq. (88). For readability and space limitations, we put some detailed parameter dependencies in the Appendix. For example, $\lambda = \max\{\big(\frac{64}{\mathcal{R}\rho}\big)^{\frac{1}{2p-1}}\sigma^{\frac{2p}{2p-1}}T^{\frac{1}{3p-2}}, \frac{(2\Delta_1)^{\frac{1}{p}}\sigma T^{\frac{1}{3p-2}}}{(\mathcal{R}\rho^2)^{\frac{1}{p}}}, 40^{\frac{1}{p}}{T^{\frac{1}{3p-2}}}\rho^{-\frac{2}{p}}\sigma (1+\frac{L_1\Delta_1}{32\mathcal{R}})^\frac{2}{p}, 4R\}$ as shown in Eq. (31) in Line 603, where $\mathcal{R} = L_0 + 2(L_1 + 1)R$, $R = \frac{1}{2}(L_0 + (4L_1+1)\Delta_1)$ and $\rho = \max\{\log\frac{4T}{\delta}, 1\}$. To address your concerns, we will add them to our main paper.

$\bullet$ Thanks for your comments. We will consider to study the convergence properties and generalization bounds under symmetric $(L_0, L_1)$-smoothness assumption in future work.

[1] Marshall N, Xiao K L, Agarwala A, et al. To Clip or not to Clip: the Dynamics of SGD with Gradient Clipping in High-Dimensions[C]//The Thirteenth International Conference on Learning Representations.

[2] Sadiev A, Danilova M, Gorbunov E, et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance[C]//International Conference on Machine Learning. PMLR, 2023: 29563-29648.

[3] Liu Z, Zhang J, Zhou Z. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise[C]//The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023: 2266-2290.

[4] Gorbunov E, Sadiev A, Danilova M, et al. High-probability convergence for composite and distributed stochastic minimization and variational inequalities with heavy-tailed noise[J]. arXiv preprint arXiv:2310.01860, 2023.

About Questions

$\bullet$ Thanks for your comments. We will reposition Assumptions 2 and 3 in our revised version.

$\bullet$ Extending the results in the convex case to the non-convex case remains a significant challenge. Although the convex case can achieve the optimality, the non-convex problem is very difficult due to the existence of multiple local optimal points. The convergence rate we have proved is state-of-the-art so far and whether it can be achieved optimally is still an open question.

$\bullet$ This is due to the novelty of our proof technique. We decompose the quadratic term into errors $\epsilon_t^a$ and $\epsilon_t^b$ in the inductive Lemma 3. Then, we construct new martingale difference sequences and use the Freedman’s inequality, which removes the gradient-similarity-type assumption.

$\bullet$ There is no lower bound for high-probability analysis, it is unknown whether the power of $\log$ terms can be improved.

$\bullet$ Table 4 is more detailed. Table 4 contains more related work and compares several results based on the criteria in expectation. Due to space limitations, we put the main compared methods in the main paper.

$\bullet$ The improvement come from our new martingale difference sequences and a more careful choice of hyper-parameters. We construct a new martingale difference sequence, $\sum_{t=0}^{l-1}(2\eta - L_0\eta^2 - L_1\eta^2\|\nabla F_S(x_t)\|)\langle X_t, \theta_t^a\rangle$, where X_t = \left\\{\begin{matrix}-\nabla F_S(x) & \text{if } \Delta_t \leq 2\Delta_1 \newline 0 &\text{otherwise} \end{matrix}\right.. The new sequence requires us to solve new inequalities about the clipping parameter $\lambda$. Then, we can obtain a better parameter setting about step size $\eta$, thereby achieving a better convergence rate $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^\frac{2p-2}{2p-1}\frac{T}{\delta})$.

$\bullet$ Under the bounded variance assumption, the work [5] can achieve convergence rate $\mathcal{O}(T^{-1/4})$, which is consistent with our results when $p = 2$. The work [5] needs the bounded variance assumption but our results are based on heavy-tailed noise assumption. The explicit rate for CL is $\mathcal{O}(\max\\{\frac{\sigma^{\frac{2p}{2p-1}}{\mathcal{R}}^{p}}{T^{\frac{2-2p}{3p-2}}}, \frac{\sigma(2\Delta_1)^{\frac{1}{p}}}{\mathcal{R}^{\frac{1}{p}}T^{\frac{2p-2}{3p-2}}}, \frac{\sigma(1+\frac{L_1\Delta_1}{\mathcal{R}})^\frac{2}{p}}{T^\frac{2p-2}{3p-2}}\\}\log^{\frac{2p-2}{2p-1}}\frac{T}{\delta})$. Similarly, we can also get the results under FL. To address your concerns, we will move them in our revised version.

$\bullet$ The heavy-tailed phenomenon can be verified by the two right plots on the right side of Figure 2. To address your concerns, we will estimate the value of $p$ in our revised version.

$\bullet$ In the federated learning, CIFAR-10 occasionally performs heavy-tailed phenomenon. Similar experiments can be found in [6]. To address your concerns, we will delete "heavy-tailed noise" in the caption of Table 3.

$\bullet$ We use the FedAvg algorithm to obtain Figure 2.

$\bullet$ "recursive momentum" was proposed by the work [7], which is a technique that can achieve variance reduction using only a single stochastic sample.

$\bullet$ There is no difference between the settings of the two left and two right plots in Figure 2.

[5] Hübler et al. "Parameter-agnostic optimization under relaxed smoothness." AISTATS, 2024

[6] Yang H, Qiu P, Liu J. Taming fat-tailed (“heavier-tailed” with potentially infinite variance) noise in federated learning[J]. Advances in Neural Information Processing Systems, 2022, 35: 17017-17029.

[7] Cutkosky A, Orabona F. Momentum-based variance reduction in non-convex sgd[J]. Advances in neural information processing systems, 2019, 32.

Detailed comparison with work [29]

1. New challenges for adapting the theoretical framework of [29] to the $(L_0, L_1)$-smoothness

$(L_0, L_1)$-smoothness leads to the following challenges: Firstly, obtaining an upper bound on the gradient $\|\nabla F_S(x_t)\|$ is difficult because it is hidden in an inequality. Secondly, we need to construct a new martingale difference sequence to handle the term $L_1\|\nabla F_S(x)\|$ in $(L_0, L_1)$-smoothness. These two factors also complicate the selection of hyper-parameters such as the clipping parameter $\lambda$ and step size $\eta$.

2. Novel contributions and direct extensions from [29]

$\bullet$ Novel contributions. By induction, we deduce that the gradient $\|\nabla F_S(x_t)\|$ needs to satisfy the quadratic inequality, $\|\nabla F_S(x_t)\| \leq \sqrt{4(L_0 + L_1\|\nabla F_S(x_t)\|)\Delta_1}$, so that the gradient $\|\nabla F_S(x_t)\|$ can be controlled when $\lambda$ is greater than a constant. In addition, we construct a new martingale difference sequence, $\sum_{t=0}^{l-1}(2\eta - L_0\eta^2 - L_1\eta^2\|\nabla F_S(x_t)\|)\langle X_t, \theta_t^a\rangle$, where X_t = \left\\{\begin{matrix}-\nabla F_S(x) & \text{if } \Delta_t \leq 2\Delta_1 \newline 0 &\text{otherwise} \end{matrix}\right., and bound it by the Freedman’s inequality. Finally, by solving the inequality about the clipping parameter $\lambda$, we obtain a better parameter setting about step size $\eta$, thereby achieving a better convergence rate $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^\frac{2p-2}{2p-1}\frac{T}{\delta})$, compared with $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^2\frac{T}{\delta})$ in work [29].

$\bullet$ Direct extensions from [29]. Eq. (15) is a direct extension from [29]. Eq. (15) is a basic tool for handling heavy-tail noise. Many works [1, 2, 3] also depend on such results. Although our analysis depends on Eq. (15), there are many differences compared with [29]. The comprehensive comparisons are provided as following.

[1] Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS.

[2] Li. High probability analysis for non-convex stochastic optimization with clipping. ECAI 2023.

[3] Cutkosky. High-probability bounds for non-convex stochastic optimization with heavy tails. NeurIPS, 2021.

3. Comparisons of theoretical results between our paper and [29].

(1) Different technologies. Under standard smoothness, [29] uses induction and constructs a martingale difference sequence

U_s^t = \left\\{\begin{matrix} 0 & s = 0\newline \text{sgn} \left(\sum_{i=1}^{s-1} U_i^t\right) \frac{\langle \sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a, \beta^{t-s}\theta_s^a\rangle}{\|\sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a\|} & s\neq 0 \text{ and } \sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a \neq 0\newline 0 & s\neq 0 \text{ and } \sum_{i=1}^{s-1}\beta^{t-i}\theta_i^a = 0\end{matrix}\right.

to handle the heavy-tailed noise, where $s \in \{0\} \cup [t]$ and $\beta = 1 - T^{-\frac{p}{3p-2}}$, while we construct a new martingale difference sequence $\sum_{t=0}^{l-1}(2\eta - L_0\eta^2 - L_1\eta^2\|\nabla F_S(x_t)\|)\langle X_t, \theta_t^a\rangle$, and solve a quadratic inequality about gradient $\|\nabla F_S(x_t )\|$ to handle the heavy-tailed noise.

(2) Different intermediate results. As we propose new technologies mentioned above to deal with $(L_0, L_1)$-smoothness, our inductive Lemma 6 is very different from Lemma 8 in [29], which plays a key role in proving convergence rate. Specifically, due to different martingale difference sequences, each term in our Lemma 6 needs to be rebounded rather than simply extending the results in Lemma 8 in [29].

(3) Respective advantages for convergence rates. Our goal is to achieve faster convergence rates under weaker assumptions. Our analysis achieves better convergence rate $\mathcal{O}(T^{\frac{2-2p}{3p-2}}\log^{\frac{2p-2}{2p-1}}\frac{T}{\delta})$ under the weaker $(L_0, L_1)$-smoothness as shown in Table 1. But [29] did not discuss this weaker assumption. On the contrary, under the stronger smoothness assumption, i.e., smoothness of individual stochastic function $f(x;\xi)$, [29] achieves a convergence rate $\mathcal{O}(T^{\frac{2-2p}{2p-1}}\log^2\frac{T}{\delta})$, which breaks the lower bound. But we did not discuss this stronger assumption.

(4) Generalization. We prove the generalization bound but the work [29] did not discuss this issue. To the best of our knowledge, our paper is the first work that provides the generalization bound under the heavy-tailed noise and $(L_0, L_1)$-smooth setting.

(5) Federated setting. We propose the novel FedCBG algorithm for heavy-tailed federated setting. More importantly, we propose novel error estimations as shown in Lemmas 1 and 2 to obtain the nearly optimal convergence rate and the first generalization bound. But [29] did not consider the federated case.

To address your concerns, we will add a detailed discussion in our revised version.

About related works.

Thanks for your comments about related work. To address your concerns, we will add the following descriptions.

As for federated learning, heavy-tailed noise also exists. The works [4, 5, 6] focus on this issue. [4] proposed a Adaptive Over-the-air Federated Learning (ADOTA-FL) algorithm for over-the-air model training. But it require both bounded gradient and bounded $p$-th moment for stochastic noise, which are stronger than our assumptions. [5] studied Byzantine resilience, communication efficiency and the optimal statistical error rates for edge federated learning under the heavy-tailed noise setting. For the non-convex analysis, in addition to requiring the boundedness of the gradient, it also requires the smoothness and second-order information of the stochastic gradient. The most related work to our paper is [6].

[4] Wang C, Chen Z, Pappas N, et al. Adaptive federated learning over the air[J]. IEEE Transactions on Signal Processing, 2025.

[5] Tao Y, Cui S, Xu W, et al. Byzantine-resilient federated learning at edge[J]. IEEE Transactions on Computers, 2023, 72(9): 2600-2614.

[6] Yang H, Qiu P, Liu J. Taming fat-tailed (“heavier-tailed” with potentially infinite variance) noise in federated learning[J]. Advances in Neural Information Processing Systems, 2022, 35: 17017-17029.

For readability and some typos

$\bullet$ $\Delta_t = F_S(x_t) - F^*$. Thank you for pointing out the typos, we will revise them in our final paper.

$\bullet$ We confirm that the bound in line 158 can be obtained by the Jensen's inequality or the Cauchy-Schwarz inequality. For the Jensen's inequality, $f\left(\frac{\sum_{t=1}^T a_t}{T}\right) \leq \frac{\sum_{t=1}^T f(a_t)}{T}$, we let $f(a) = a^2$ and $a_t = \|\nabla F_S(x_t)\|$, thus $\frac{1}{T}\sum_{t=1}^T\|\nabla F_S(x_t)\| = ((\frac{1}{T}\sum_{t=1}^T\|\nabla F_S(x_t)\|)^2)^{1/2} \leq (\frac{1}{T}\sum_{t=1}^T\|\nabla F_S(x_t)\|^2)^{1/2} \leq \mathcal{O}(\log^{\frac{p-1}{2p-1}}\frac{T}{\delta}/ T^{\frac{p-1}{3p-2}})$. For the Cauchy-Schwarz inequality, $\left(\sum_{t=1}^T a_t b_t\right)^2 \leq \left(\sum_{t=1}^T a_t^2\right)\left(\sum_{t=1}^T b_t^2\right)$, we let $a_t = \frac{1}{T}$ and $b_t = \|\nabla F_S(x_t)\|$ and can obtain the same result. Thus, both Jensen's inequality and Cauchy-Schwarz inequality can derive the result.

$\bullet$ $\widetilde{\Delta}_t$ should be $\widetilde{\Delta}_t^i$. We modify the bracket error in line 294. Thank you very much for your detailed review.

In summary, we will complete missing definitions, standardize the notation, and thoroughly proofread the manuscript in our revised version.