Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
Authors: Abdurakhmon Sadiev
Peter Richtárik
Ilyas Fatkhullin
Venue: NeurIPS 2025 poster ()
Keywords: hessian clipping
gradient clipping
optimal complexity
stochastic
second-order optimization
heavy tailed noise
normalization
Primary area: optimization
TL;DR: matching upper and lower bounds for stochastic second order optimization under heavy tailed noise, high probability convergence

Abstract: Heavy-tailed noise is pervasive in modern machine learning applications, arising from data heterogeneity, outliers, and non-stationary stochastic environments. While second-order methods can significantly accelerate convergence in light-tailed or bounded-noise settings, such algorithms are often brittle and lack guarantees under heavy-tailed noise—precisely the regimes where robustness is most critical. In this work, we take a first step toward a theoretical understanding of second-order optimization under heavy-tailed noise. We consider a setting where stochastic gradients and Hessians have only bounded $p$-th moments, for some $p\in (1,2]$, and establish tight lower bounds on the sample complexity of any second-order method. We then develop a variant of normalized stochastic gradient descent that leverages second-order information and provably matches these lower bounds. To address the instability caused by large deviations, we introduce a novel algorithm based on gradient and Hessian clipping, and prove high-probability upper bounds that nearly match the fundamental limits. Our results provide the first comprehensive sample complexity characterization for second-order optimization under heavy-tailed noise. This positions Hessian clipping as a robust and theoretically sound strategy for second-order algorithm design in heavy-tailed regimes.

Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
Abdurakhmon Sadiey* KAUST Center of Excellence for Generative Al
Peter Richtárik KAUST
Center of Excellence for Generative Al
Ilyas Fatkhullin ETH Zurich, ETH AI Center, Georgia Institute of Technology
Abstract
Heavy-tailed noise is pervasive in modern machine learning applications, arising from data heterogeneity, outliers, and non-stationary stochastic environments. While second-order methods can significantly accelerate convergence in light-tailed or bounded-noise settings, such algorithms are often brittle and lack guarantees under heavy-tailed noise-precisely the regimes where robustness most critical. In this work, we take first step toward a theoretical understanding of second-order optimization under heavy-tailed noise. We consider setting where stochastic gradients and Hessians have only bounded p-th moments, for some p E (1, 2], and method. establish tight lower bounds on the sample complexity of any second-ored We then develop variant of normalized stochastic gradient descent that leverages second-order information and provably matches these lower bounds. address the instability caused by large deviations, we introduce novel algorithm based on gradient and Hessian clipping, and prove high-proo grobbbbbbbyyltyy upper bounds that nearly match the fundamental limits. Our results provide the first comprehensive sample complexity characterization for second-ord -odder optimization under heavy-tailes noise. This positions Hessian clipping as robust and theoretically sound strategy for second-order algorithm design in heavy-tailes regimes.
Introduction
We consider the stochastic optimization problem
min F(x), F(x) : : Eed([(r {)},
BERd
with F smooth (but potentially nonconvex) objective, and & random variable drawn from an unknown distribution. While first-order methods are widely used in practice due to their simplicity and scalability, the application of second-order methods remains limited in stochastic settings. This in stark contrast to their strong theoretical properties: second-oo -odeer methods such as Newton's method (Bennett, 1916, Kantorovich, 1948), cubic regularization [Nesterov and Polyak, 2006, Nesterov, 2008], their variants for finite-sum minimization [Kovalev et al., 2019], quasi-Newton [Dennis and Moré, 1977], and adaptive second-order algorithms [Doikov et al., 2024] can offer provably faster convergence rates. Furthermore, complexity theoretic results demonstrate that second-order methods can outperform first-order ones in noiseless (or finite sum) settings, often with moderate additional computational cost [Agarwal and Hazan, 2018, Arjevani et al., 2019, 2020] only.
-tnplexityttheoretic
Corresponning author: abdurakhmon. sadi evkkaust. edu. sa King Abdullah University of Science and Technology. Thuwal, Saudi Arabia.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Second-order methods are highly sensitive to noise. First-order stochastic optimization (FOSO) methods-such as stochastic gradient descent (SGD) and its adaptive variants- well understood. both algorithmically and from a complexity-theoneee
perspective. These methods enjoy optimal convergence guarantees under a broad class of noise models, including bounded variance and infinite variance regimes [Gower et al., 2019, Khaled and Richtárík, 2020, Yang et al., 2023, Wang et al., 2021, Fatkhullin et al., 2025]. In contrast, the development of second-order stochastic optimization (SOSO) methods has been significantly hampered by their extreme sensitivity to noise, particularly in Hessian estimation. Existing second-order methods suffer from both practical instability and overly restrictive theoretical assumptions. For instance, stochastic extensions of cubic regularization [Ghadimi et al., 2017. Tripurameni et al., 2018] and its momentum variants [Chayti et al., 2024] require bounded noise assumptions, which are rarely satisfied in modern large-scale learning tasks. Other frameworks-such as trust-region methods [Arjevani et al., 2020], recursive momentum schemes ('Tran and Cutkosky, 2021], and extrapolation-ban et al., 20eal this to bounded variance, but still fall short of handling more realistic heavy-tailds noise distributions. To the best of our knowledge, existing SOSO method can operate reliably under noise conditions with unbounded variance, highlighting a fundamental gap in the current landscape of stochastic optimization.
approaches Antonaaoopoulos et al., 2022, Agafonov
Heavy-tailes noise in gradients and Hessians. In recent years, the first-order optimization litera- ture has increasingly moved beyond the bounded variance assumption, adopting more general noise models that better reflect empirical observations in modern applications. A particularly influential framework is the bounded central moment condition (p-BCM) which assumes
E fllVf(2,E) - F()))ll o".
for some p (1.
thereby allowing for heavy-tailed noise with unbounded variance. This model aligns well with empirical findings in deep learning and reinforcement learning (RL), where heavy-tailed gradient noise is often observed [Garg al., 2021, Zhang et al., 2020, Ahn et al., 2024, Simsekli al., 2019. Battash et al., 2024]. Algorithms designed for robustness under p- p-BCM noise, such as those employing gradient clipping or normalization, have demonstrated both strong empirical performance and rigorous convergence guarantees [Zhang et al., 2020, Hübler et al., 2025]. These developments suggest that heavy-tailed noise models are not only practically relevant, but also theoretically tractable. providing principled foundation for algorithm design. Given that second-orde methods are even more sensitive to noise than first-order ones, this naturally motivates the extension of such robustness principles to the second-order setting. In this work, we take this step and aim to
develop a comprehensive theory of second-order stochastic optimization under heavy-tailed noise.
Specifically, we assume access to unbiased stochastic gradients and Hessian-vector products, each satisfying p-BCM-type condition:
[[) - S So for some p E (1,2).
Our goal is to characterize the fundamental performance limits and develop practical algorithms for minimizing F(x) in this setting, with focus on obtaining guarantees for finding points with small gradient norm [=())) S E, either in expectation or with high probability.'
From gradient to Hessian clipping. Gradient clipping has become standard tool in modern machine learning, particularly due to its empirical success in stabilizing training under heavy- noise and ill-conditioned objectives [Pascanu al., 2013, Schulman al., 2017]. Theoretically, has been shown to offer robustness under relaxed smoothness and moment assumptions [Polyak and Tsypkin, 1979, Jakovetić et al., 2023], and enable high- sigh-probbbility guarantees with logarithmic (sub-Gand Sab--aussian) dependence on the failure probability. The latter property of gradient clipping is in stark contrast to the classical linear algorithms, e.g., SGD, Momentum SGD, for which high probability lower bounds were recently established [Fatkhullin et al., 2025]. These properties are well-documented across both convex [Nazin et al., 2019. Gorbunov et al., 2020, Davis et al., 2021, Gorbunov et al., 2024b, Liu and Zhou, 2023, Gorbunov et al., 2024a, puchkin et al., 2024, Armacki et al., 2023] and nonconvex [Sadiev et al., 2023, Nguyen et al., 2023, Cutkosky and Mehta, 2021,
'It would be interesting to extend our results to finding second second-order stationary points [Nesterov and Polyak, 2006, Arjevani al., 2020]. but we leave this investigation for future work.

---

Hübler et al., 2025] regimes. Crucially, high-proben probability results are both theoretically and practically appealing as they guarantee the performance of individual runs rather than for the average-cast behavior.
Despite these advances, the robustness enabled by gradient clipping remains largely confined to first-order methods. In the second-order setting, where both gradients and Hessians may be corrupted by heavy-tailed noise, comparable algorithmic tools are conspicuously lacking. The core difficulty is not just technical but conceptual: existing SOSO algorithms do not include mechanisms to suppress the influence of extreme noise in Hessian estimates. This leads us to fundamental question for the design of robust second-ore -odeer stochastic methods:
Can we develop second-order algorithms with high-probability convergence guarantees under simultaneous heavy-tailed noise in both gradients and Hessians?
Second ord
Pirst-order
Complexity
2.0
1.0
Clip NSSiittass
Clip SGD
NEXDM
1.2
1.4
1.6
1.8
2.0
200
400
600
800
1000
Tail index P
Iteration.
Figure 1: Sample complexity comparison for FOSO and SOSO depending on the tail index p. Each line corresponds to the leading term in the sample complexity for each class of algorithms. These leading terms match in upper and lower bounds, so this characterization is exact. We establish the characterization along the entire green line complementing prior work [Arjevani et al., 2023] for p = 2.
Figure 2: Performance of algorithms ple problem, F(x) 0.5 || d 10 with synthetic noise generated from a two-sided Pareto distribution with tail index p 1.1. We observe that algorithms without clipping, NS- GDM and NSGDHess, suffer significantly from noise. This motivates our more in-depth study involving gradient and Hessian clipping for high probability convergence.
sim-
Contributions:
Tight lower bound. We establish minimax lower bound on the sample complexity of any SOSO algorithm under p-BCM noise model: Ω
Arn (g) (g)==T) where A denotes the initial
suboptimality, and a, σ denote the scale of noise in gradients and Hessians, respectively. This bound improves over the best known complexity for first-order methods [Zhang et al., 2020, Hübler al., 2025] by factor of 1/2 uniformly for all p E (1, 2], demonstrating that second-order methods can yield provable advantages even in the heavy-tailes regime; see Figure Moreover, our result implies that increasing the order of the algorithm (e.g.. using higher-order derivatives) cannot improve the rate under the same noise assumptions significantly.
Optimal algorithm. We develop second-orde stochastic algorithm that achieves the lower bound (up to constants) the regime I. < dh, where I. denotes the Lipschitz constant the )-T) and is, to the best of our knowledge, the first second-order method that provably works under p-BCM noise. Notably, our method does not require second-order smoothness of the objective. This result holds in the classical setting p highlighting the broader implications of the approach.
gradient. The algorithm attains the sample complexity O
22
groh-pprbbbbliity convergence via Hessian clipping. We propose a clipped variant of our algorithm that incorporates both gradient and Hessian clipping-the latter introduced here for the first time. We show that this variant achieves near-optimal sample complexity with high probability, incurring only poly-logarithmic overhead in the failure probability. This
3

---

significantly extends the robustness of SOSO methods, enabling strong guarantees not only in expectation but also with high confidence.
Our results are primarily theoretical and validated through synthetic experiments with controllable heavy-tailed noise. While one component of our algorithm (in its unclipped form) has previously been applied in reinforcement learning settings [Fatkhullin et al., 2023], its broader practical deployment remains an open challenge. In particular, several questions must be addressed to make these methods viable in real-world applications: How can we reduce hyperparameter tuning overhead? Are there default configurations that are robust across problem classes? Is clipping truly necessary. or can be systematically replaced by normalization techniques, as recent work suggests in the first-order context [Hübler et al., 2025]? We view our contributions as a foundational step towards a principled understanding of second-orde methods under realistic, heavy-tailed noise conditions, and hope they spur further theoretical and algorithmic advances in this direction.
2 Notations and Assumptions
We use the common notation for natural numbers N {0, 1....... and let [n] 2 21......... n Throughout this paper, d E Nン denotes the dimension of the optimization problem (1). We use O (+), (-) for sample complexity notations, which preserve the dominating term in the target accuracy > 0 along with the multiplicative constants such as initial suboptimality A, smoothness constants Ly. r 2 the variance of bigher-order stochastic oracles or, r 1. When we write O (+). we suppress the dependence on all parameters except for accuracy & in the dominating term. As in Carmon et al. [2020], for any q-th order tensor T E @d'd, we define the support of T as supp def {i E [d] T. + 0). where T; is the (q 1)-th order tensor, given by [Tildt...dq- T Trmnnooo-
We make the following assumptions throughout the paper.
Assumption (Lower Boundedness). The objective function F is lower bounded by F -00. Assumption 2 (T-smmothhness) The objective function F is T-smooth, i.e., F is differentiable and for all x. y E Rd,, we have F() - F S T. || - yll-
Assumption 3 (p-BCM). We have access stochastic gradients V f such that EE (V (x) V Fx)). Moreover, there exist E (1,2) and a > O such that
B flllf FF o" for all x E Rd.
Assumption 4 (p-BCM for Hessian). The function F is twice differentiable and we additionally have access stochastic Hessian-vector products V2 (2x(x,)) ()), v for any u E R2 such that E [ [)] Fz). Moreover, there exist p (1, 2] and on 0 such that
E I(,,)) - 2 F()) S oh
for all E Bd.
3 Lower Complexity Bounds for SOSO under p-BCM
To establish lower bounds, we build on a technique developed in series of works [Arjevani et al., 2023, Carmon et al., 2020, Arjevani et al., 2020], which introduced a worst-case non-convex function exhibiting the zero-chain property: starting from the origin, each algorithmic iteration reveals information about a single coordinate only. Leveraging this framework, Zhang et al. [2020] derived the first lower bounds for FOSO under heavy-tailed noise, assuming the p-th moment of the stochastic gradient is bounded, i.e., E [ f (z. 1) < GP, which differs from Assumption 3.
In work, we assume access to q-th order stochastic oracle, meaning that each query yields stochastic approximations of derivatives of orders 1 to q at a given point x. This oracle model was formally introduced by Arjevani et al. [2020]. Building on their proof technique, bounds under the assumption that each stochastic derivative has a bounded p-th central moment.
derive new lower
Function class. We consider the class of q-times differentiable functions (q 2 1) satisfying two key properties: (i) functional boundedness, i.e., P(O)- - F < A; and (ii) Lipschitz continuity of each derivative up to order q, i.e., for all x, y E Ed and r [q].
F F(x) V F(y) llop 1/ v/l.

---

We denote this function class by F(A, Li:g), where Lız4 (L1.L2, Lgg. Note that the constant from Assumption corresponds to L1 this notation.
Oracle class. We now define the oracle model. For fixed function E F(A, I1s)), a stochastic q-th order oracle is defined as follows: for any x E IR" and 5 ~ D,
(x, del (J(z, V/(r, (')(,,))....."((((........ ())(x,E)),
where each component satisfies the unbiasedness conditions: (xr F(r), and Eg~p[V" {)] = V'F()). rr [q]. We define the oracle class Og(F, 01:)) as the set of all such stochastic oracles for which the p-th moment of the estimation error (with E (1) satisfies
D ((x,)) F(
Sof
W [g], Vx E
For r this recovers 01 from Assumption 3, and for 2, we similarly have 02 oh from Assumption 4.
Algorithm class. To prove lower bounds, we will work with a class of zero-respecting algorithms. The formal definition provided below. The reason why this class of algorithms is interesting for us is based on its property: at each iteration of such an algorithm, at most one new coordinate can be revealed.
Definition 1. We call a stochastic q-th order algorithm A zero-respecting for any function and any p-th order oracle Op. the iterates {x* heN generated by A via querying 0% satisfy the following property: supp {x'} C Uiet supp (x), Vt N with probability one with respect to the randomness of the algorithm and the realizations of (5")
def (ol,..., Fg) and O(oi). Then, there exists F E F Lızg) and a corresponding noisy oracle O% E O(,, avs)) such that for any q-th order zero-respecting algorithm, the number of oracle queries required to find e-stationary point (with constant probability) is lower bounded by
Let E N21, and let A > 0, Ligg def (Li....; Lg), F1:g
Theorem 1.
3
2(1) A
Or
Top
min
min rE(2....g)
min rllll
01
Moreover,
this
lower
bounds
is
realized
by
construction of
dimension
A min min,e Oz min
The proof of Theorem deferred to Appendix D. In Theorem we provide lower bounds for any N21, which corresponds to the order of an oracle used in an optimization algorithm. When the oracle order satisfies q > 2, the algorithm gains access stochastic curvature information, enabling more accurate prediction of the function or gradient behavior between consecutive iterates. This richer information can potentially lead to tighter worst-case complexity limits compared to first-order methods. Since the main focus of our work is on the second-order setting, we now discuss the complexity result from Theorem 1 for q = For second-order methods, = 2, under Assumptions 2, 3, 4 and, additionally, (possibly) assuming the Hessian is Lipschitz continuous with constant Ln, we have
2(1) min
Aonh 2²
ALo
0
AVTnO 2/2
33
where the parameters satisfy a = 01, σh = 02 = L1, L = Lp. We will now discuss each term separately, in different regimes.
First-order optimization with Lipschitz gradient. When we not have access to the second-order information and the objective function has Lipschitz continuous gradient only, but not any higher derivative, our lower bounds (3) reduces to the second term:
ALo
Ω
33
5

---

This bound exactly matches (up to numerical constant factor) the previously known lower bounds for first-order stochastic optimization under p-BCM [Zhang al., 2020], and the corresponding upper bound achieved by normalized SGD [Hübler et al., 2025]. Several other algorithms, like Clip-SGID and NSGD with momentum and clipping also nearly match this complexity lower bound, up to additional polylogarithmic terms in 1/E and polynomial terms in 6, L and [Zhang et al., 2020, Cutkosky and Mehta, 2021, Nguyen et al., 2023].
First-order optimization under higher-order smoothness. The second case worth discussing is when we (still) do not have access to stochastic Hessian, but we know that the objective function has Lipschitz continuous second-order derivatives. Then our lower bound (3) becomes
(min min
{ ALo c3
AVIna ( 8//
Ω
The last term in the above bound nearly matches with the complexity of the method called NIGT with clipping, by Cutkosky and Mchta [2021], in terms of its dependence 1/s, up logarithmic factors. Unfortunately, there is still small discrepancy with the upper bound in the dependence on other parameters and with the fact that Cutkosky and Mehta [2021] use slightly stronger (non-central) assumption E [ (x, {) S G instead of our p-BCM. We believe our bound is tight and can be achieved with more careful analysis of NIGT type algorithm under the p-BCM assumption.
Second-order optimization with only Lipschitz gradient. Finally, we wish to discuss an important setting, which is rarely discussed in the literature second-order optimization. Higher-orde smoothness can be challenging to verify in practice. Moreover, even when is possible, the estimates of L, can be too large to be useful. Thus pay attention to the case when have access to stochastic Hessian, but the second derivative can be non-contimuous, i.e., Ln + +00. Our lower bound (3) provides new insights on this interesting setting, simplifying
Agh
ALo 0
}
Ω
min
As we can see, the first term corresponding to the second-order information has better dependence on an accuracy and can be potentially much smaller than the second term. Moreover, this complexity is not impacted with the constants corresponding to higher-order smoothness, which potentially gives us the possibility of designing second-order methods with complexity that does not depend on Ln and higher order smoothness constants. However, this is merely lower bound, which does not give us any algorithmic solution yet. The question we investigate in the next section is
Can we design an algorithum handling heavy-tailed noise with complexity O (A)) (9) (g)=t)²
4 Near-optimal Second-Order Method under P-BCM
In the last decade, the second-order stochastic optimization (SOSO) has been extensively studied under stronger noise assumptions. We will first review the existing approaches, particularly focusing on the development in the non-convex setup. First, Tripuraneni al. [2018] proposed and analyzed Stochastic Cubic Newton (SCN) method, achieving ((--%/a sample complexity. 'heyy require a strong bounded noise assumption, use large mini-batches and importantly, this complexity is not order-optimal. Later Arjevani et al. [2020] established lower bounds for SOSO for finding first-order stationary points and proposed two algorithms: SGD with recursive variance reduction and stochastic Hessian-vector products (HVP-RVR), and subsampled cubie-regularized trust-region method with HVP-RVR. Both algorithms achieve Ō sample complexities, which is minimax optimal when the variances of stochastic gradient and Hessian are bounded. Besides strong noise assumptions, their algorithms require large Hessian batch sizes, since they used HVP-RVE subroutine to update the momentum term. To overcome the large batch-size requirement, Tran and Cutkosky [2021] designed simpler algorithm: SGD with Hessian-corrected momentum (with optional normalization), called SGDHess. Thanks to the Hessian corrected momentum term, their methods also achieve ((s sample complexity with any batch size 2 1. Recently, Chayti et al. [2024] proposed a variant of SCN

---

with momentum without large batch requirement. However, their analysis requires the bounded noise assumption and only achieves (2) sample complexity.*
To summarize, all nbove-mentioned works require strong noise assumptions: bounded noise and bounded variance. Moreover, their sample complexities also depend on second-order smoothness La. which be potentially infinite, as discussed in the previous section. We refer to Table 1 for the summary of existing results.
Algorithm NSGDHess (Normalized SGD with Hessian correction)
1: Input: Starting point 2o E R vector 9u E R stepsize > 0, momentum parameters
a > the number of iterations T.
2: Io 7 Tooll
3: for 1= 1.2..... .... T
do
4:
Sample 9t ~ L1 (10, 1])
5:
i, - q1 (1 --)
6: Sample Er, E. ~ D independently
7: 9r (1 a) [9--1 V ((), -(( + (
8: T++1
7 |Bxll
9:
end for
10: Output:
To design an optimal second-order algorithm without these limitations, we take an inspiration from the recent developments in reinforcement learning (Salchkaleybar et al., 2022, Fatkhullin et al., 2023]. Their algorithms called SHARP and (N)HAR-PG are variants of SGDHess in [Tran and Cutkosky, 2021] with optional normalization step. We adapt variant of their method to general stochastic optimization setting and present in Algorithm 1. This algorithm computes a random interpolation point & uniformly distributed between consecutive iterates - and Ft- The method then evaluates stochastic gradient and stochastic Hessian vector product using independent samples & and &.- Finally, a recursive momentum is constructed before applying the normalization step. We are now ready state the convergence guarantee for Algorithm
Theorem 2. Suppose Assumptions and 4 hold. Let the initial gradient estimate be given by
Bu
fi(oo Eo.i), where Binit max {1, (2)
9o
Binit
Set stepsize as = /
Aatie (L+o.)T
momenium parameter
min {1, (1,g)), where Ceff
max
Ea Taa
T
AlL+on) T
& = B
p-1
Then, Algorithm guarantees that
ΣE Fx::)) s & with total sample complexity
(ALLON) 22
+ e2
(2)
o
The proof is deferred to Appendix E. We also investigate different choices of go and their influence on the total sample complexity rate in Appendix E. We find that while the initial batch size estimate Go is not necessary for convergence, helps to slightly improve the total sample complexity.
Comparing this result with Theorem 1, we observe that our upper bound (4) matches our lower bound-the first term in (3) in terms of the target accuracy e. Moreover, when ( ox) 2 as, we have tight upper bound, which exactly matches the lower bound from the previous section in
Discussion:
However, in the noiseless case their complexity has better O(e -3/3) iteration complexity compared ') for SGDHess.
Normalization step for this method is important for our analysis under p. pCBCM. However, it can be removed
when p 2, or when additional clipping used, as in the next section.
7

---

the leading term (up to numerical constant). Moreover, since our upper bound does not depend on constant Li, it explains our observations in Section 3 regarding the limit case L, oo, and answers the raised question affirmatively. We refer to Table for more technical comparison with prior work.
Hessian Clipping for High-probability Convergence
In Section we provided an in in-expectation guarantee for Algorithm While in-expectation guar- antees useful in the case when we are allowed average-case behavior, can be impractical. In may real-world scenarios, only a single run of a methods can be performed due computational or time constraints. Thus, our main goal in this section is to conduct high-probability analysis for Algorithm or its modification.
method multiple times to analyze its
Since we work in the unbounded variance case, which corresponds to heavy-tailed noise, it is important to ensure that the analyzed method is robust to such noise. Following works of Gorbunov et al. [2020]. Cutkosky and Mehta [2021]. Sadiev et al. [2023]. Nguyen et al. [2023]. we propose a new algorithm, called Normalized SGD with momentum and Hessian clipping. It is formally presented as Algorithm 2, where compared to Algorithm 1 also incorporate gradient clipping and Hessian clipping. Formally, a clipping operator (clipping for short) defined as
clip(e, A) = min 1,, ||l|| }r for any v + 0 from R.
(5)
where À > 0 is called the clipping level/threshold.
Algorithm 2 Clip NSGDHess (Normalized SGD with Hessian correction and clipping)
Input: Starting point 2g E Idd vector In E Rd. stepsize y > 0, momentum parameters
a 0, clipping levels À >> 0, λ > 0, the number of iterations T.
2: æ1 .i and go
3: for t= 1.
do
4: Sample q: ~ 4 (10, 1])
5: f. = 4: + (1 9t)
(t) xe-1
6: Sample E,, E.
independently
7: 9t (1-a) 9t-1 + ccli (7- ( xx-1),,))
6t 8: Jt+1 It. Tlsill
9: end for
10: Output:
As in Algorithm 1, we use normalization in the gradient update (line 8), which allows the next point Jr-1 to stay in the ball with center at I; of radius 7. The main difference between Algorithms I and 2 in the momentum term. To enhance robustness, we do not only clip the gradient, but also the Hessian-vects Hessian clipping is new, and it allows us to provide the first high-probability guarantees for second- order stochastic optimization without light-tail noise assumptions. It is worth to draw attention the term
product. As mentioned above, gradient clipping is common approach, but
y celip (~- xo-1),
(6)
Observe that clipping the entire Hessian based on its operator norm is very costly since typically
requires (dd2) arithmetic operations (e.g., using power iteration [Golub and Van Loan, 2013] or Lanezos algorithm [Lanezos, 1950, Saad, 201 Instead of clipping
stochastic Hessian, we clip the Hessian-vector product, which is computationally tractable, and only requires ((d) operations. Thus, the computation of this clipped Hessian-vector product can be easily implemented via backpropagation and subsequent "vector" clipping (5). Another reason why prefer to use this

---

form of clipping comes from the analysis; we want to preserve the following useful property:
E E (0e (x) x2-1)]
= Eg. E V (2 Eo) (at ( xc-1)
Egg V F' xt--1)]
F(g + (1 -) rt-1)dd
VF(x)) VF(x:-1).
(7)
This would not hold were we to use direct Hessian matrix clipping. Instead, we prove that the expectation of (6) will approximately be equal to (7) when 7 is selected properly. By smoothness and gradient step, we have VF(xz) F S Li|ar - It-1ll = Ly, meaning the expectation bounded. To provide the analysis, we need to rewrite the clipped Hessian-vector product as follows
yclip (7- 122 f(i,, Ed 2,-1). clip f(e, E.) - 21-1).
where we denote X = 7Aa- The former formulation the above formula useful for implementa- tion, since as we will see, An ~ O(ya -(ya-//r) and O(a O(a-//)) Thus, and X are of the same order (()=//)) O which makes it easier to tune these two parameters together in practice. The latter formulation will used in the high-probability analysis. We are now ready to state the main theorem of this section.
Theorem 3. Let Assumptions 1,2,3, and 4 hold, and define the initial optimality gap as A F( F.. Let E 10, and 2 1 be such that log(8T/8) 2 Suppose Algorithm executed with the following settings: momentum parameter a = T _ clipping levels = 2y(L+oa) stepsize 7 satisfying: max (AVLAI, } An al/p
7SO min {VA
V
A L'
VALL of log (T/5) F Tlog(T//
A
On) log(T/)) (og(T))))))))) ))
Aiat/r
LT a
Then, with probabiliy at least 1 1-8, the output of the algorithm satisfies: As a result, the grudient norm converges at the rale
T (VF(a)) $ 24, 78
T-1
V + σN) +
Σ [FF())] =0
log
T 2p-1
with high probability.
The complete proof of Theorem can be found in Appendix Disregarding the parameters L, a, Th, A in the choices of the stepsize and the clipping level, we see that the momentum parameter and the stepsize decrease with the same rate ~ O(1r==11) similarly to Algorithm 1. Also, as we
mentioned above, clipping levels and Xn have the same rate, and behave as O(T I).
Corollary 1. In the setting of Theorem 3, Algorithm 2 ensures that T EED /V S with probability least 8. To achieve this, the algorithm requires at most
o V VVAI(L (L + ((VArl log
1
3p-1
T-
furs//scoon-order oracle calls.
E
SE
According to the results of Theorem 3 and Corollary 1, we have shown that Algorithm 2 has near-optimal convergence rate the dependence on E. Moreover, the complexity has a logarithmic dependence on 3/4, which is better than polynomial dependence that can be achieved by directly translating the in-expectation result of Theorem 2 to high probability one using Markov's inequality, Unfortunately, the dependence on A L, a, σi does not match the lower bound (3).
Comparison with [Liu et al., 2023b]. Recently, and under additional strong assumptions, Liu al. [2023b] analyzed momentum-basee based, variance-reduced first-order method, and obtained rates

---

similar to those in our Corollary 1. However, they assume individual smoothness (i.e., / (2. V Vf(,, E) S f yll for all æ; E Rd and all realizations of the random variable Q). However, individual smoothness is a very strong assumption which implies boundedness of the stochastic Hessian, i... V E)ll S E a.s., for all E IR We also note that under individual smoothness, fast p-independent rates can obtained, e.g., Lei et al. [2019] achieve O complexity for SGD under individual smoothness.
6 Limitations and Future Work
While our proposed method with Hessian clipping has many desirable properties, such as near- -pta-ml sample complexity, batch-free and high-probability convergence, under mild statistical assumptions, it also has several limitations. First, it requires tuning three extra parameters compared to, e-g., vanilla SGD [Farkhullin et al., 2025] or Normalized SGI [Hübler et al., 2025]. would be interesting to investigate if such extensive tuning can be removed for second-order methods. Second, while our sample complexity is near optimal, it does not match our lower bound exactly all important parameters. Moreover, while we mainly pay attention to the leading stochastic terms in the complexity, our methods do not recover optimal deterministic complexities of second-order methods. Perhaps different analysis technique for clipping and some algorithmic modifications (like Newton type preconditioning [Chayti et al., 2024]) are required to exactly match the upper and lower bounds. Third, high probability upper bounds are derived for fixed confidence level ó rather than uniformly for all 8 E (0, 1) (as e.g., in [Liu et al., 2023a, Hübler et al., 2025]) and the algorithm's parameters depend on this choice. This is limiting it does not necessarily imply high probability convergence for a fixed parameter choice. Finally, while we make an important progress the fundamental understanding second-order stochastic optimization, such results should always be interpreted with caution. In practice, the overhead of second-order methods (computing Hessian information or even Hessian-vector products) and the challenge of tuning additional hyperparameters (such clipping thresholds for both gradients and Hessians) can be significant.
Acknowledgements
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) CRG Grant ORFS- CRG12-2024-666 and iii) Center of Excellence for Generative AI, under award number 5940. The work of I.F. supported by ETH AI Center Doctoral Fellowship.
References
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308 318, 2016.
A. Agafonov, D. Kamzolov, A. Gasnikov, A. Kavis, Antonakopoulos, V. Cevher, and M. Takáč. Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness. arXiv preprint arXiv:2309.01570 2023.
N. Agarwal and E. Hazan. Lower bounds for oigher-order convex optimization. In Conference On Learning Theory, pages 792- PMLR, 2018
K. Ahn, X. Cheng, M. Song, C. Yun, A. Jadbabaie, and S. Sra. Linear attention is (maybe) all you need (to understand transformer optimization). In International Conference on Learning Representations, 2024.
K. Antonakopoulos, A. Kavis, and V. Cevher. Extra-newton: A first approach to noise-adaptive accelerated second-order methods. Advances in Neural Information Processing Systems, 35: 29859- 29872, 2022.
Y. Arjevani, O. Shamir, and R. Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, 178(1):327-360, 2019.
10

---

Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, A. Sekhari, and K. Sridharan. Second-order information non-convex stochastic optimization: Power and limitations. Conference on Learning Theory, pages 242-299. PMLR, 2020.
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, (99(1-2):65 214, 2023.
A. Armacki, P. Sharma, G. Joshi, D. Bajovic, D. Jakovetic, and S. Kar. High-probabiliyy conver- gence bounds for nonlinear stochastic gradient descent under heavy-tailed noise. arXiv preprini arXiv:2310. 18784, 2023.
B. Battash, L. Wolf, and O. Lindenbaum. Revisiting the noise model stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pages 7780-4788 PMLR, 2024.
A. A. Bennett. Newton's method in general analysis. Proceedings of the National Academy of Sciences, 2(10):592-598, 1916.
S. Bubeck, N. Cesa-Bianche Bianchi, and G. Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(1 1)77711-7711,,000 2013.
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
S. Cayci and A. Eryilmaz. Provably robust temporal difference learning for heavy-tailed rewards. Advances in Neural Information Processing Systems, 36, 2024.
E. M. Chayti, N. Doikov, and M. Jaggi. Improving stochastic cubic newton with momentum. arXiv preprint arXiv:2410. 2024.
A. Cutkosky and Mehta. Momentum improves normalized SGD. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2260-2268. PMLR, 2020.
A. Cutkosky and H. Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883 4895, 2021.
A. Cutkosky and F. Orabona. Momentum based variance reduction non-convex sgd. Advances in neural information processing systems, 32, 2019.
D. Davis, D. Drusvyatskiy, L. Xiao, and J. Zhang. From low probability to high confidence in stochastic convex optimization. The Journal of Machine Learning Research, 22(1):2277-2274, 2021.
J. E. Dennis, Jr and J. Moré. Quasi-newton methods, motivation and theory. SIAM review, 19(1): 46-89, 1977.
N. Doikov, K. Mishchenko, and Y. Nesterov. Super-universal regularized newton method. SIAM Journal on Optimization, 34(1):27-56, 2024.
I. Fatkhullin, A. Barakat, A. Kireeva, and N. Hc. Stochastic policy gradient methods: Improved sample complexity for Fisher-non-dee -esdee-non-eeeenerate policies. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 9827-9869, 2023.
I. Fatkhullin, F. Hübler, and G. Lan. Can sgd handle heavy-tailed noise? arXiv preprint 2XXi:2508.048661 2025.
S. Garg, J. Zhanson, E. Parisotto, A. Prasad, Z. Kolter, Z. Lipton, S. Balakrishnan, R. Salakhutdinov, and Ravikumar. On proximal policy optimization's 's heavy-tailed gradients. In International Conference Machine Learning, pages 3610-3619, PMLR, 2021.
S. Ghadimi, Liu, and T. Zhang. Second-order methods with cubic regularization under inexact information. arXiv preprint arXiv:1770.05782,

---

G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 4th edition, 2013.
E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping, Advances in Neural Information Processing Systems, 33:15042- 15053, 2020.
E. Gorbunov, M. Danilova, I. Shibaev, P. Dvurechensky, and A. Gasnikov. High-probabilltyy com- plexity bounds for non-smooth stochastic convex optimization with heavy-tailed noise. Journal of Optimization Theory and Applications, pages 1-60, 2024a.
E. Gorbunov, A. Sadiev, M. Danilova, S. Horváth, G. Gidel, P. Dvurechensky, A. Gasnikov, and Richtárik. High-probabiilty convergence for composite and distributed stochastic minimization and variational inequalities with heavy-tailed noise. In International Conference on Machine Learning, pages 15951-16070, 2024b.
R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and Richtárik. SGD: General analysis and improved rates. In International Conference Machine Learning, pages 5200-5209, PMLR, 2019.
C. He, Z. Lu, D. Sun, and Z. Deng. Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise. arXiv preprint arXiv:2506. //2/4, 2025.
Hübler, I. Fatkhullin, and N. He. From gradient clipping to normalization for heavy tailed sgd. In International Conference on Artificial Intelligence and Statistics, 2025.
D. Jakovetić, D. Bajović, A. K. Sahu, S. Kar, N. Milosević, and D. Stamenković. Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise. SIAM Journal on Optimization, 33(2):394-423 2023.
L. V. Kantorovich. Functional analysis and applied mathematics. Uspekhi Matematicheskikh Nauk, (9)889-885, 1948.
A. Khaled and P. Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint 033:22,00..03329, 2020.
N. Kornilov, O. Shamir, A. Lobanov, D. Dvinskikh, A. Gasnikov, Shibaev, E. Gorbunov, and S. Horváth. Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance. Advances in Neural Information Processing Systems, 36, 2024.
D. Kovalev, K. Mishchenko, and Richtárik. Stochastic newton and cubic newton methods with simple local fimear-quadrate rates. arXiv preprint 11Xiv:1912.01197,200 2019.
C. Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of Research of the National Bureau of Standards, 45:255-282, 1950.
Y. Lei, T. Hu, G. Li, and K. Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE Transactions on Neural Networks and Learning Systems, 2019.
Z. Liu and Z. Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises. arXiv preprint arXiv:2303.12277 2023.
Z. Liu and Z. Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal conver- gence without gradient clipping. arXiv preprint arXiv:2412. 195299.41..1959., 2024.
Z. Liu, T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning, pages 21884- 21914, PMLR, 2023a.
Liu, J. Zhang, and Zhou. Breaking the lower bound with (little) structure: Acceleration in non- convex stochastic optimization with heavy-tailed noise. In Proceedings of Thirly Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2266-2290 PMLR, 12-15 Jul 2023b.
12

---

A. V. Nazin, A. S. Nemirovsky, A. B. Tsybakov, and A. B. Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80:1607-1627, 2019.
Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence (1/K" 2). In Doklady AN USSR, volume 269, pages 543-547, 1983.
Y. Nesterov. Accelerating the cubic regularization of newton's 's method on convex problems. Mathe- matical Programming, 11((1)159-18)) 2008
Y. Nesterov and B. T. Polyak. Cubic regularization of newton method and its global performance. Mathematical programming, 108(1):177-205, 2006.
T. D. Nguyen, A. Ene, and H. L. Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tails. arXiv preprint arXlv:2304.01119, 2023.
R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, pages 1310-1318. Pmlr, 2013.
B. T. Polyak and Y. Z. Tsypkin. Adaptive estimation algorithms: convergence, optimality, stability. Avtomatika telemekhanika, (3):71-84) 1979.
N. Puchkin, E. Gorbunov, N. Kutuzov, and A. Gasnikov. Breaking the heavy-tailed noise barrier in stochastic optimization problems. In International Conference on Artificial Intelligence and Statistics, pages 156-864. PMLR, 2024.
Y. Saad, Numerical Methods for Large Eigenvalue Problems. SIAM, 2011.
A. Sadiev, M. Danilova, E. Gorbunov, Horváth, G. Gidel, Dvurechensky, A. Gasnikov, and P. Richtárik. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In International conference on machine learning, 2023.
Salehkaleybar, Khorasani, N. Kiyavash, N. He, and Thiran, Adaptive momentum- policy gradient with second-order information. arXiv preprint wrXiv:2205.08255 2022.
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347 2017.
H. Sha, Y. Cao, Liu, Y. Wu, R. Liu, and H. Chen. Clip body and tail separately: High probability guarantees for DPSGD with heavy tails. arXiv preprint arXiv:2405. 1405:29905.,752,, 2024.
U. Simsekli, L. Sagun, and M. Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827-5837. PMLR, 2019.
H. Tran and A. Cutkosky. Better SGD using Second-order Momentum. arXiv preprint arXiv:2103.03265, 2021.
N. Tripuraneni, M. Stern, C. Jin, J. Regier, and M. Jordan. Stochastic cubic regularization for fast nonconvex optimization. Advances in neural information processing systems, 31, 2018.
H. Wang. M. Gurbuzbalaban, L. Zhu, U. Simsekli, and M. A. Erdogdu. Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance. In Advances in Neural Information Processing Systems, volume 34, pages 18866-1888 18877, 2021.
Yang, X. Li, Fatkhullin, and N. He. Two sides of one coin: the limits of untuned sgd and the power of adaptive methods. Advances in Neural Information Processing Systems, 36:74257-74288, 2023.
Zhang and Cutkosky. Parameter-free regret in high probability with heavy tails. Advances in Neural Information Processing Systems, 25:8000-800 2022.
J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? Advances Neural Information Processing Systems, 33: 15383-15393, 2020.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: yes, derive new sample complexity upper and lower bounds, the formal proofs are in the appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: yes, there limitations sections in the end of main part
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
Yes, all formals proofs are in the appendix, assumptions are clearly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, we describe the details of our experiments, although our experiments use very simple toy illustration.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

reproducible, they Answer: [NA]
Justification: Our work's focus is advancing theory of stochastic optimization, so this question not applicable. Our one numerical illustration is very toy experiment involving 10 dimensional quadratic problem with synthetic heavy-tailed noise.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.co
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips. wttpccccpppcccccccccccccccccccct ggtcci/g////////iiiioeooiii Sotdeeebmisssiiiieooeaa ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Yes, provide all necessary information reproduce our toy illustration.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, we include error bars as it is important to illustrate the confidence levels of optimization algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The illustration is toy and can be run on any device without advanced compute resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't It make it into the paper).
paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: : //weenrrrs.../// w
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: Yes, follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work advances theory of optimization, it has not immediate societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There are no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We don't 't use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We don't release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: we don't 't use crowdsoucing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the work does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We don't 't use LLM for method development.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https //tp:///nnuu./eeeeeee fatrps//nearips..ccooofffee / for what should or should not be described.
20

---

Contents
1 Introduction
2 Notations and Assumptions
3 Lower Complexity Bounds for SOSO under y-BCM
4 Near-optimal Second-Order Method under p-BCM
5 Hessian Clipping for High-probability Convergence
6 Limitations and Future Work
10
Additional Related Work
22
B About Normalized SGD and Different Variants of Momentum
22
Technical Lemmas
24
D Missing Proofs for Section 3
25
Missing Proofs for Section 4
28
F Missing Proofs for Section 5
33
F.1 Analysis: Optimization Part
33
F.2 Analysis: Statistical Part
34
G Experimental Results
44
21

---

Table 1: Summary of sample complexities of stochastic second-order (SOSO) methods for finding an E-stationary point, in high probability of in expectation, i.e., number of stochastic gradient and Hessian evaluations to find z with [>)][ S e. The column "p" indicates the range of moments in Assumptions 3, 4 for which the result holds, that is when p 2, the corresponding result holds only under bounded variance. When p = oo it means that at least for stochastic gradient or stochastic Hessian bounded noise assumption is required, which corresponds to all moments being bounded. We are not aware of any prior works for SOSO for p < 2. The column "HP?" denotes whether the high probability guarantee with polylogarithmic dependence on the inverse of failure probability 1/0 is available.
Algorithm
Sample Complexity
p
HP?
SCN
AVTTo² 8//2
(
(Tripuraneni et al., 2018]
00
SGD with HVP-RVR
Aggh 63
AyLnT e/2
AL g²
2
x
[Arjevani et al., 2020]
(2 with HVP-RVR
Angn
Av AvIao E/2
Ag
2
X
[Arjevani et al., 2020]
N-SGDHess
3
Andn
AVLno
+
Agh
2
X
[Tran and Cutkosky, 2021]
2
[Chayti et al., 2024]
SCN with IT-HB
AvTn 5//2
+
AL 1/4
e²14
on
1/2
+ AvLo
1712
0
X
Lower Bounds
min
Ana c²
ALo Avina
(1,2)
Theorem 1
g3;
ga/2
NSGDMHess
A(L+oN)
A(L+os)
+2
(g) p-1
(1,2)
X
Theorem 2
8²
2+p-
Clip NSGDMHess
V VAi
(1,2)
Theorem 3
0 Tripurameni et al. [2018] provide unalysis under stronger assumptions, which implies the noise has light tuils. Subsampled Newton.
A Additional Related Work
Gradient clipping and normalization. Gradient clipping has been applied successfully also in zero-order optimization [Kornilov et al., 2024], bandit and RL literature [Bubeck et al., 2013, Cayci and Eryilmaz. 2024], online learning [Zhang and Cutkosky, 2022] and differential privacy [Abadi et al., 2016, Sha et al., 2024]. Some other works, which use normalization and gradient clipping under heavy-tailed noise include [Armacki et al., 2023, Puchkin et al., 2024, Liu and Zhou, 2024].
B About Normalized SGD and Different Variants of Momentum
In this section, we present a general framework for momentum-bass methods. The study of momen- tum has a long history, particularly in convex optimization, where Nesterov [1983] demonstrated that an appropriate use of momentum in gradient descent can accelerate convergence. In contrast, our focus is momentum in the setting of stochastic non-convex optimization. The general update rule is given by
9t
T++1 = Zt Tit
where gr denotes the momentum term. Different choices of g, give rise to different algorithms, several of which we now describe.
NSGD is the standard stochastic gradient method. Setting 9: V f { in the general framework immediately recovers NSGD. is well known that NSGD converges only to a neighborhood of the solution, with radius proportional to [Yang et al., 2023, Hübler et al., 2025]. One possible remedy to employ mini-batching, which reduces the variance. However, this strategy cannot be applied only single sample per iteration is allowed.
22

---

NSGDM is the solution of the problem described above and was proposed and analyzed by Cutkosky and Mehta [2020]. The momentum term defined as
gt (1 a
In their work, the authors proved that NSGDM converges to e-stationary point and achieves sample complexity of (( which optimal according to the lower bound of Arjevani al. [2023]. Subsequently, Hübler et al. [2025] extended this result to the setting where the stochastic gradients have bounded p-th moments, deriving a sample complexity of O )
NSGDM with clipping was proposed for the general setting where the stochastic gradients have bounded p-th moments. The momentum term is modified as
9: = (1 a) clip (t),
Cutkosky and Mehta [2021] established high-probability convergence guarantees and showed that this method achieves a sample complexity of O( F which optimal and matches the lower bounds of Zhang et al. [2020]. It is worth noting that the clipping operator is not strictly necessary: normalization of the momentum term is sufficient to guarantee convergence under Assumption [Hübler et al., 2025, Liu and Zhou, 2024].
NIGT a variant of NSGD that incorporates momentum and implicit gradient transport, proposed by Cutkosky and Mehta [2020]. In this method, the momentum term is modified by changing the point at which the stochastic gradient evaluated:
a
gt = (1 - a)9-11 + VV (x), where y/ =
1t
Thanks to this modification, and under the assumption that the objective function has Lipschitz continuous Hessian, Cutkosky and Mehta [2020] proved that NIGT achieves sample complexity of O (s-V/)), which improves upon that of NSGDM.
NIGT with clipping was introduced by Cutkosky and Mehta [2021] to enable high-probability analysis under the assumption of bounded p-th moments of the stochastic gradients. The only modification compared to standard NIGT is the inclusion of a clipping operator, which required from a theoretical standpoint. As shown in Cutkosky and Mehta [2021], NIGT with clipping achieves 5p-3 23-2
sample complexity of O
which is optimal according to Theorem 1.
NSGD with MVR is a variant of NSGD that incorporates momentum variance reduction (MVR). The STORM/MVE method was proposed by Cutkosky and Orabona [2019] to improve the sample complexity compared standard SGD. More recently, He al. [2025] established that NSGD with
MVR achieves sample complexity of O 2n which matches ours in terms of dependence
& (Theorem 2).
The methods discussed above rely solely on first-order information. A natural question is whether incorporating second-order information can further improve the sample complexity.
NSGD-Hess is variant of Normalized SGD that incorporates flessian-correchi momentum, pro- posed by Tran and Cutkosky [2021]. this method, stochastic Hessian-vector product is introduced into the momentum update:
g: = (1 - a) (g--1 V2 f(),,))) Er) (x-- - 2イ-1)) + +a a
Refined NSGD-Hess. In refined version, the momentum term is modified by adjusting the point which the stochastic Hessian evaluated and by using independent fresh sample &, D for the Hessian-vector product computation:
ft = q: + (1 - -c) where qe ~ ((10011)))) 1]),
9t (1 a1) (91-1 (2f( (ot - xt-1) + aVf((z,
23

---

C
Technical Lemmas
We list the following technical lemmas, which useful for our analysis in the subsequent sections.
Lemma 1 (Lemma 10 from Hübler et al. [2025]). Let p [1;2]. and X,,..., Xx E TRd be martingale difference sequence, L.e. [X,
X1] = 0 a.s. for all j = -..... satisfying
E | < oo for all ,. n.
Define Sn Eラ=1 Xz, then
E I| ["] S
E |1IX,11]
Lemma 2 (Lemma 10 from Cutkosky and Mehta [2021J). Let XI.... X, E Rd be sequence of random vectors. Define the sequence of real numbers Wi,.... Un recursively
1. W0
2. If E X₁ + then set:
1= X X,
Wj sign
Σ wi
X1
3. 1f X; = O. set wy = O.
Then [.y S |Xil| for all j , n2, and
12
||S -
Σ Wi
+
max jEin]
|X,||
|X,1
(8)
Lemma 3 (Bernstein inequality). Let Xi,..., E Rd be a martingale difference sequence, X1) a.s. for all j= 1,..... Assume that conditional variances
i.e. E
def E x .1] exist and are bounded, and assume that there exists deterministic of
constant > 0 such that [xxl S almost surely for all j = =....., Define Sn dgf Ei=t Xg, then for all b 0, G
1 2G + 2cb/3
PP SSa > b and
2 of S
G
< 2exp
Lemma (Lemma 5.1 from Sadiev al. [2023]). Let X > 0 and X E Red be a random vector and x def (X, A). Then,
X - E. X < 2X. Moreover, for some and p (1:2) have
[ x Rd. |||X - x=|"] s oP, and | s A/2, then
Pa
F || x |"]
E + E [x]](] S 18P
X
x
--1
18X2-P0
24

---

D Missing Proofs for Section 3
In this section we provide lower bounds for the certain class of functions and the oracle class. Our prove is inspired by the paper of Arjevani et al. [2020].
Auxiliary Lemmas. Now we state two helpful lemmas prove lower bound. The first lemma is about the number of iteration to reveal all coordinates, when zero-respecting algorithms use the information received from the oracle forming probability-p zero-chain.
.... Definition collection of derivative estimators V=,(E,E), (2)( ..., V9f(2, E) for
function F forms a probubility-p zero-chain if
P 2(3z) prog (V'f(,, ((,(E))..,,V(((((E - trog (x) 1 2
and
IP f(3x) prog (), ...,, v)f(x,()) = prog (x) +1] (x)+ -0, i> 1.
The second lemma about the main properties of the worst function from the class F(A, L1sg)-
Lemma 5 ([Arjevani et al., 2020]). Let 4 f) 4 (xx 5) be a collection of probability- P zero-chain derivative estimators for F R. + E. and let 0% be an oracle with O', f(. rew) Let (x "log)) be a sequence of queries produced by zero-respecting algorithm A interacting with O², Then, with probability least
T log 1/2
prog
x (1)
A(03]
<T
for all
1
2p
Lemma 6 (Carmon et al. [2020]). Let h: ITT + R be the
function: f
h(x) -=((L))(2;) Σ
(1(-x-1))(--0 ((()-1)((Zi)),
where
(0,
and 4(x) - ve f 2- dt.
(x) = exp (1 (1- ---ーー11)))
Lexp
Then the function satisfies the following properties:
h(0) - inf -in) = A,T, where Au 12.
For q 2 1, the q-th order derivatives of are Li-Liscchitz continuous, where lg S
exp (5q log + eq) for a numerical constant c < oc.
For all RT, g and i [T', we have ([=) lq-1, where to 23.
For all x E RT and E N, prog (V"h(z)) S prog (x) +
For all x E RF, prog, (z) T. then [[Vh(=)] Z V pma (2) (z) h((x)
Lemma 7, Let the derivative estimator is defined as follows for each r E [g]
[v"h(x,)), def (1+Ifi> >prpi (108:())) (5. (5- Vih(z),
where Bernoulli(p). Then, (V"h(x, ()rre)) forms probability-p zero-chain, and for any p E [1,2] for each r E [g] the derivative estimator satisfies
28P
E 1''(I, 2)] = v"h(x), and EE [V"((x,))- vVh(=)) <
for all x E Rd.
I
25

---

Proof. First of all, it is easy to show that the proposed estimator is unbiased, i.e.
E [V {)] (1 0) V'h(x) = V'h(x))
According to Lemma 6, have prog (V+((z)) < prog (z) 1 S prog (2) + 1, where the last inequality is true because proga non-increasing with respect to a. Then, by Lemma we have
[Vh(,, = ViA(a)= = 0, Vi > progy (a) + 1.
Therefore, due that 5 Bernoulli(p) we obtain
P b prog (V) v*s(e=)) = prog (x) + 1] S p.
Le. (V h(1: (rr()) forms probability zero-chain.
Now we bound p-th moment of V"h(z, E) V h(x) for any E [1: Denoting is = prog; (x) + 1. for any E [q] we have
{ ix > progy (1)) (s (6-1)( \V7
E (2)( - V'h())lep)) = E
5
17
E
Vihh(>)
p
E
p)P + (1 p)P²
pP
2
@
p
Main Theorem. Now we are ready to state and prove the main theorem in this section, i.c. Theorem 1.
Proof. First of all, we fix all parameters: & E A, Ling: oig > 0 and >> 0. Next, rescale our function h as follows: h" (xx) = vh(3x), where v > 0 and 3 > 0. According to Lemma 6, selecting
we have for any r E [g- - 1]
ht (0) inf (x)
v (h) - inf h (Bx)) S VAOT SA;
1 h² hx)))((()) lop
h(3x)l S 1
DB v 2 n3 Vh(=))1 2 vB, Yx: prog, (x) < T. Since (V"h" (x, {) VB 3rep forms probability-p zero-chain, then by Lemma 6 with probability at least 8 = 1 we have
[x)[
E
vk Vh ( |||
wBE
vh (3
||
v 2
T-1 414
2p
The p-th central moment of the scaled derivatives estimators is bounded as
vp grPE |V'((3x.) V V"h(3x)
2v grp
p=-
where in the last inequality we applied Lemma 7. Thus, we have the set constraints for parameters and for all lg]:
VAOT < A;
vBr+11, S Tup
2g 2 ZE
up uP R
2
< o..
26

---

We will resolve the system of inequalities step by step. The first step is to set V= 2s have
For r 1, we
0
2 PP-
p min (()
U BPB.
of
To set 3, we need to find its specific value, which can satisfy the following constraints: for any r E (,....,9) .) and any r' [g]
ge+ S
I 3Lr vlr
up IP o
2
3p(-11)
(
p S o
2zl,'
pa-
where in the inequality (+) we used
2
S
of vegueg
Therefore, we obtain
p
foo,
-
Lyp' 2Ely
B
min r'Elals rE(2....))
min
1--101
Then, assuming 2 3 and
S 1, we get
01
T-1
1
A3
-1)
A
2p
2p
2A08
SpAge
-
lnor
-
Typ
min
min
2zlo
4A r'Elll (2......
1--101
2El.
A
Ly
2(1)
min
min (2......))
min E'
01
Since h and h* are functions of T arguments, the dimension of the problem is equal to T. This concludes the proof.
27

---

E Missing Proofs for Section 4
In this section we study Normalized SGD with Hessian correction (NSGD-Hess) (see Algorithm 1).
Auxiliary Lemmas. To show the convergence guarantees for Algorithm 1, we state and prove auxiliary lemmas. The first one is well-known Descent Lemma for Normalized SGD. The proof for this lemma can be found in Cutkosky and Mehta [2020], Hübler et al. [2025], but for completeness we restate and reprove it. The second one is devoted to the bounds on error term from Descent Lemma. Lemma 8. Let Assumptions I and hold. Then for any selection of stepsize y > the iterates (2=) generated by Algorithm I satisfy
12TIT
Σ [VF(())] + AA 2
|ell
+
(10)
2
1=
where functional gap is defined as A, def F(a)) - F., error term is defined as é def
9t V (x)))
Proof. According the update rule for 24 and Assumption 2, we have
F(1++1) S F(x,) + (V;) Jz+1 - -xa) +
|
x2,1 11
2
2²L
F(xt) 7 (z+,,
9t
+
|g
2
72L
F(x)) T|19a11 ~ VF(x))
9t
9t:
|1
72L
< F(x:) > 119e11 + ++/[)((x 9ell
2
2
< F(x.) - > + 2 / VF(x;) gell +
2
Using notation for the functional gap and the error term, we get
2L
>| / + +
+
2
Summing over & from 0 to T we obtain
T-1 1
T-1
1TT
VF (x))
+ A + 2
+
@ell +
(11)
2
t=0
1=
Next, we derive the lemma for eтrоr control for the Hessian corrected momentum estimator (lines 4-7 Algorithm 1). Similar lemma for the special case p = 2 appeared previously in [Salchkaleybar et al., 2022, Fatkhullin et al., 2023]. For the case < 2, similar recursion was derived by Hübler et al. [2025] for first-order momentum. Now we extend this idea to the case of second-order momentum.
Lemma 9. Let Assumptions 2, 3 and 4 hold. Then for all 2 0, we have
E [1|@ |] = (1 a) [|o + 2a a 12y(L + +ow)a_/
m-1
(12)
where é := 9t Fz.))
Proof. Define e, vf(2,, (x) VF(z,), S.,1 V (()1) (I++1 21) VF(04+1) +
Fxx)). We have E [ex] = 0, E [[e o², S 0, and
E s |r|
E VF(x,) (
4 f( (#141 (x441-101)) =z))l"]
3E V (..)
VF
|| + 3E ( (#++1 - Iz =1) [1]]
+3E
(#141 -22)
6L + 30
28

---

By the update rule for the gradient estimator:
& gt
(F(x))
= (1- -1-a)e + taz + (1 - a))
Unrolling the recursion, we have
[-1 (1-a)) es+1 + Σ [1--a) a) aa-=1a) S3+11
é (1- (1- a
1=0
/=
Then, taking the norm and the total expectation, we get
E [|]@||] s (1-a) 'EE [I
E
ej+1
-E
Σ (1 (1-a)
(13)
==0
To continue the proof, we need to bound the last two terms from the previous inequality. By Jensen's inequality, we obtain
est1 1T)
1/7
E
a
Σ
11 -
(1-0)
E
a
(1 a) -
j=
1/8
t-1
2a
(1 a
plll pp(t---1) [
j=0
1/7
2a
(1 a))((t---))pp op
j=0
(v.e)
S
2 20001 0z) 1/5
2a p=1 o,
(14)
where in (+) we used Lemma 1, in (**) we used E [[]ej+1ll0] |1'| s aPand in (* * x) we used the following inequality
t-1
r-1
(1-a))((---y <
a1-
a1-a)s -
1=0
j=0
j=0
We bound the third term in the same way as we did for the second term:
1/2
[-1
Σ 11 a) 11
E
(1 a)
1=0
1/8
(1 (((-)) 1E
|| [||++1l(]]]
1=0
1
12
(1 - (1-a))(t-))pppp + of)
)=
(one)
12 1ap + +oo))) 1/2 < 12(L + + 1/2, (15)
where in (+) we used Lemma 1, in (**) we used E ||| used the following inequality
17]
< 6L + 30" and in (* *) we
(1--a) ((--a)(t-1)
(1- <
Σ (1 a = =1
1=
j=0
Plugging (14) and (15) into (13), we obtain
E [||e: |]] < (1 a)' [|| + 2a a + 127(L + on)a
p=1
which concludes the proof.
29

---

Main Theorem. Now we are ready to state and to prove the main convergence theorem for Algo- rithm
Theorem Let Assumptions and 4 hold, and stepsize
Aa'in [I+
momentum parameter
min {1, aeg' where Oef max
(To)
Eo 20
( (A(Lton))
Then iterates { 1=0 of
Algorithm I satisfy
E
(V
ALL ( 0h)
[ ohl
55-
1-1
to a
+
T
To²
T
To
where Eg is defined as some upper bound on [1990
VF(xx)]l
Proof. Applying Lemma 9, we have
T-1 Σ o1- 2a - oT 12>(I + on)a VeT
E [ll
E ||lll
+ 2a -
oT 12 + 0n)a -VOT. VPT
Therefore, according to Lemma 8, we obtain
E
[IIV
A
2
Σ
E
[|@@|]]
7L
T
YT
T
t=
A
71.
2E
[|
4a a 24y tn)a
7T
2
af
2E
[|looll
p2 +4a x o (
7T
αT
0
ALL + +n))
E Illlolll
+a m1
ta:o.
aT
where in the last inequality we took y =
Aa (L+oa)7
Denoting E ||@@oll S Eo and taking momentum
parameter a min (1, aan), where Cer max
Eu To
(A(++on) To
we have
o (V ( on)
Eg p-1
T Σ EUVF
ta
1/rT
aT
AlL on)
&
+ ( (A(L+ +OL+ On)
11
Eg
T T
+
To²
0
To
Now we investigate how different choices of initial estimator go affect the total sample complexity bound.
Corollary Let all assumptions of Theorem hold and the step-size and momentum parameters are set according to this theorem statement.
1. If we set go FF(2)), then Eo = O, and the total sample complexity of Algorithm is equal to
( A(L oN)
ALL + on)
(g) (g) )
0
+
22
e2
30

---

2. If we set 9u 0. then Eo V2AL, and the total sample complexity of Algorithm I is equal
to
o |(T +o) σh) + +(
( VATa
3. If we set 90 Bun
Bua V (f with Biir max { (1) 7-1 (2) _ -
}. then
Eg 20/ B
aand the total sample complexity of Algorithm is equal to
o (
[ on)
+(L+
(
+
22
E²
Proof. The first case is ideal, when we can have access to the full gradient but once: set go = VF(xz)) then ég 0 and &g Thus we have
1 T E EIVD
on)
(A(L+ oh)
to
T
T
To²
In other words, we can guarantee + EET E [IIVF((t))) & after
( (AL ALL + o
2²
iterations of Algorithm 1.
The second case is that we select go vector. This choice implies that by smoothness of F, we have
E [|l [ S VLLA Eg-
Plugging the obtained value of & into the result of Theorem 2, we have
T
ALL+ + on)
A(L +
I
VLL
VAL
T
E (
T
to
To²
T
+
a
To
#
AALLoNN oN)
A(Lohh) σh))
VAL
o
to
to
T
To²
To
which implies that the total sample complexity
A + oN)
A(L + σh)
10
A
p-
+
e2
22
The third case is that we set 90
1
Σj=
Bus v f (To, Eo
By Lemma 1, we have
E [|@@ol]
(E
11T) 4/2 (E l1 (F(D)))
1/-
Bun
E [[IV/((zo. - VF(xo))11)
Buii
1=0
1/3
Bun
2
Σ op
20
En-
Binit
m-T
1=0
B
P
Plugging the obtained value of Eo into the result of Theorem 2, we have
o o
A(I + on)
A(L + oh)
1-
T E
V
to
o
T
To²
2-1
p-1 TB
TB
F
F
Init
init
31

---

from which we have that the total sample complexity is
o
A(
A(L
0
0
p-
+
Binit
62
g²
p-1
B
uni
Taking Binn max
{I, (g)
(
Ip-
we have that the total sample complexity is
0 0
(-)
o p
(2)
0
20
+
8²
32

---

Missing Proofs for Section 5
Now we start the bagh-probbbility convergence analysis for Algorithm We divide our analysis into two parts: Optimization part, where we prove descent lemma, and High-Probability part, where we use concentration inequality to bound several terms from Descent Lemma. Finally, combining results from both parts, we prove the main results of this section via induction. The idea is based on work of Sadiev et [2023] and Liu al. [2023b].
F.1 Analysis: Optimization Part
We start with Descent Lemma.
Lemma 10. Let Assumptions 1. hold. Then Algorithum with stepsize Y 0 and momentum
parameter E (0,1) generates iterates {xx } satisfying the following inequality
LT
3 a
VF + DT I A
LA
T-1
T-1
+2ya
Σ
Σ a)
10
+ +
Σ
a) 1
a)
for any j E [T -1] vectors 82 and wy are defined as follows
8 def clip (Vf(,, E,), VF(2)),
(16)
W def clip -.) VF(x)-1))
(17)
Proof. First, we notice that Lemma holds for Algorithm and can be proven in the same way as for Algorithm 1, since the gradient updates in the both methods are identical except for zı, and the update rule for momentum term does not play any role the proof Lemma 8. Therefore, the iterates {are 1 of Algorithm satisfy
2T
(x))) + 2
&ell
+
(18)
2
2=
where Ag A1, because To T1- Next we bound || in almost the same way did in Lemma 9. By update rule for momentum parameter, we have
0t VF(x))
clip (i 1.-1), = (1 a) 90-1
+aclip (VI( {t), A) F())))
(16
(1 a) + a&, + (1 a)w:
(1 a) + Σ (1-a)- + Σ
(1 a)) --5
1=1
j=1
Taking the norm, we obtain the following bound
||eell < (1 (1-a)*lloll++ +
Σ (1 a
+
Σ 1 - (1)))(-)t()
1=1
1=1
< (1- +a
Σ (1 (11-a))-8p) 10
+
Σ a -
(19)
where in the last inequality we used the following chain of inequalities
|| ll
VF(2))] = |F [VF()))] < (2L(F(Z))- F.) 2LL
33

---

Plugging (19) into (18), we acquire
T
7-1
LT
(a + Ar 1
A
2
+
Σ
|lērl +
2
1=0
LT
T-1
1
+
Σ
(1- /2L1,
2
1=0
T-1 Σ
+2
Σ
(1
0) 100
2
Σ
(1 ②
-))
1=1
/=1
t=1
LT
3y
$
A
+
LA
2
a
T-1
+2
Σ
a)
10
+ Σ
Σ a
where in the last inequality we used
27
T-1
Σ
(1-
(1-
S 27
Σ (1
2LA,
2/27
LA
S
37 a
LA
1- (1 -
1=
1=0
F22
Analysis: Statistical Part
According to Lemma 10, we have two new terms
Σ al--a)-1 10
and Σ a1-a)r-5th w/
To bound both of them, we use the same idea as in the work of Gorbunov et al. [2020], Sadiev et al. [2023], Liu et al. [2023b]: introduce unbiased and biased parts of 9r and w/, ie. for any E [T]
0.
0 + 0f,
where
def clip (Vf(z,, &i,, A) Ee, [clip (Vf(z,,))) A)..
0r
(20)
of
def
Ex [clip (VI(z,,))) A)] V F(());
(21)
Wt
wi + w/, where
def clip f(ter - x)-1), 2n) Egr.s clip (() - 21-1), m1-1).
An)
w
def Eg.si clip (2 (x) - -x--1), An)] (VF((,)) (F(e)-1))
(23)
Under Assumption for any À 2 V (x+))] Lemma 4 implies
Eg. [|]]]]]] < 1- and
| S 2"X'_Po" for all E [T].
(24)
It is worth to mention we have already shown in Lemma 8 that under Assumptions 2 and 4 the vector (xe x1-1) - VF(x+) + (F has zero expectation Eg.se [
S, = 42 ((r,,)
0, since
B & [v2s(Er - - = ES Eg S Et) (Fe -
= Ey
- I1]]]]]
F2F(gz; + (1 -1- (1- zt-1)dg
VF(x.) - VF(x.1)..
34

---

The p-central moment of Š, is bounded, i.c Bg Lemma 4, for all E [T] we have
| |||, ||] s 6LPAP + +30 Then, according to
||wل|| ||] < 18 P P61 + 30 and | S p (611++30f +300),
Eqg., for any 2 | Fx,) - VF(I=-I)| & 2 S An.
(25)
Lemma 11. Let Assumption 3 hold. For any 8' E 1/2 and any E (T), if clipping level satisfy
2 max ((3)) T
then with probability at least 1 -
28'
1
$ 222 log 2 8¹
Σ
(1
j=1
Proof. We start with bounding
Σ (1 a)" 50
Upper bound for
[)= - (1-))--100)
By (20) and (21), we have
Σ (1 (1-00 o)(
Σ 11 a) -0
+ Σ (1 aa)
5
Denote Yÿ def
- i00
Es,
[[(L - aa)-- [|] and |x|l| s [|(1 a0-5 for any
j E [t]
0,
i = 0:
Σ (0
j-1
j-1
Vj del
sign
Σ Vt
i + 0 and
(1 a) 0-00 #0;
Σ (1-a)--107 00
0,
j + 0 and
Σ (1 - 1000 =
Then to bound
Σ (1 - a)- (1-a))--00
we use Lemma 2 and obtain
a))
max [|(1 - a 100 + jE(()
Σ (1 -000 1?
j=1
j=1
Σ Vi
2 Σ [|(1 (11-aa)- 1001
+
j=1
1/2
Vt
+
Y +2
Eee [[(1-a)--0 00 10]1
5
Upper bound for @. The sequence Xf...., X is martingale difference sequence, since, by definition of 83 and Xj. for all j [t] we have E [X] X
Ee, [x]] 0. Also, according to Lemma 2, we have |X] S [1- - (1-a)'=003) 83 for all j E [t]. Using Lemma 4, we obtain that
Xi] -.......
X
< [[11 00) < ||0||| < 2x, where Ci 22.
(26)
35

---

Denoting o3 def [(x]]
X - Xi] Ee, [(Xx]]] Lemma 3 implies
2
s 2cxpp (- (-
bf
P 1 b and Σ oj - G1 log
8',
8'
2G log 2 8
+
2cyb1
(3cr + //a + +2G1) log S.. To define G1, need
where the last identity is true, if we set b1
to bound Σj= oj:
ΣS² 0 = Σ Eg, [(x]]] 1 1=1
Σ Bs, [I[11- 10)- = > (1 a) 2))((-3)) [1108]]]]
j=1
j=1
1=1
(24)
1
P G1.
Σ (1 ())((()))))))))))))))))) 18A2-PoP Pop v 1- (1 a1=
(27)
where we assumed [|V 2 for any j [t].
Upper bound for @. The sequence Yi, ......, Yf forms martingale difference sequence, since the definition of Y leads to E [Y] yi......, Yf] = Es, [Y]] 0 for all j [t] Also, according to Lemma 4, we obtain that
M S |1(1 - -0 + Re, [IK 10 < 4x2 + 4x2 = 8X2,
(28)
where we define
E C2 def 8x2.
Denoting the conditional variance of YJ as o3 def r Eg, [( we can bound 03 casily
8A2 E
[1 - -00 -Eg, Eg, [[[] 10--09 -0) |1] [|(2] a1)- -100-1)0-0
E6,?
Then, Lemma 3 implies
2
b2
P
2
b2 and
< G2 log
5 2exp
8',
2G2 log 2
or
+
20ab2
3
where the last identity is true, if we set ba to bound Σラ=03 73:
(/02 Vo22 + +2G2)
log 3. To define G2, need
03
S
16X2
Σ
Es,
[[[11- -88
1=1
j=1
161 Σ
(1 22
(itt-))BEE, 10
|001 [
j=1
161 18A2-PoP
16.
18A4-P00
G2.
where we assumed |/ \|
<
A for any j E [t].
2
Upper bound for @ Thanks the proof of the bound on 3 (see (27)), we have already shown what we need: with probability 1
Egg [ - a) - (27) 18X² 2
a
36

---

Upper bound on A Assuming
|VF(2;))] - for any j E [t], with probability 1 we have
Σ
t
Σ
(1
2 1000
S 41
R -
Σ
(1-a)+
41"
a
j=1
==1
To sum up, we introduce event E as follows
Fast
def
|0| S bi or Σ oj > G1 log 2
|0|
(29)
8 8)
5=1
where 61 = 2X, G1 = 1812 b1 = (3e + v l 2G
log f..
We have shown that
a
P ((Eii} 2 8'. The bound on bj
1
2
2
2
61 = 5 +
Vg
- 2G1
log 8
01
+
V2G
log
3
8
X2 PPP
log 2
1
(9)²
2 log
+ 36
= \
+ 6
81
3
a
8
Also we define event E as follows
2
E
(3)
S b2 or
Σ
0 > G2 log
(30)
d'
f=1
where C2 = =8x2, G2 =
16-1844-20" b2 = (tc2
+ / + +2G2) log S.
We have shown that
P P( (Fa,) 2 1 - 8'. We adjust the bound on b2:
1
1
2
2
2
b2 =
+
2 +
2G2
log I
C2
+ /2G
log 8'
3
9
8'
3
16
16 36A Pop
2
16
1
1(00 7
2 8
x2 +
log
= x2
+
24
log
3
8
3
Thus, the event Es,, n E implies
1
8
Σ 11 - (1-a)-10)
Σ (1- 500
Σ
11 - a3
+
j=1
1=1
(
+ 22-
@
+ 2 3 + +
4
1
2
+ 41 (9) "
A
+
6
log
3
8
16
[1
(0) )
2
36A2-PoP
+ 2x²
+
24
log 8
3
Taking A A> a. we have the event Ev,t O Exx, implies
a.v.
t Σ 1a- () S x
4
32
2 < 22A log
2 g
6
+
4
V
+
84
log 8
3
j=1
This concludes the proof.
37

---

Lemma 12. Let Assimptions 2and 4 hold. For any 8" E (0, and any t E [T), if clipping level satisfy
An 2 max 27L, 7L + 0hh
a
and with probability at least 28"
2 s 59hr log 8r
Σ (1 ())--())) ++1 Wj
j=1
Proof. By (22) and (23), we have
Σ 11 a) wo 5
Σ 0)) ww
Σ (1 a) 1 a
(31)
Denote Zj def [11 - a0)--+11) w/)l 1|2 Ees es [1(1-a)))++u)]] and Wy $ - (1-aa)--+lw))
for any j E [t]
0,
j = 0;
Σ (1-a))=(+) wi" (1- (1-a)*
j-1
j-1
W def sign
Σ W
if j * 0 and
Σ (1
it w0 * 0;
(1 (1-a) - +t
4-1
0,
if * 0 and
Σ (1
1- = 0.
Then to bound
Σ
(1 - a (wy
we use Lemma and obtain
W
max |[(1 - -u)-- jE[1]
Σ
|1(1 - ww
/
1=1
1=1
t
W
+
Σ
|11 (1- a1-))t+5)
1=1
j=1
1/2
W
+
2. Σ
Zj +2
Σ Eg [|(1-a)=++ [|]
j=1
Upper bound for G. The sequence Wi,... W. is martingale difference sequence, since, by definition of w/ and Wt for all j E [4] we have E [W W wi Wil = Eg [ 0. Also, according to Lemma 2, have |W5[ [[(1 a---ww) wwl || for all j E [t]. Using Lemma 4, we obtain that
W S (1 - - < || S 2Ah, where c3 def 2 (W
(32)
Denoting of def
W
Wi] = Eg, [( Lemma 3 implies
02 2G log
> by and
Σ
83 $ G3 log 8"
< 2xxp
8",
2
2cyba
j=1
38

---

where the last identity is true, we set by = (30s + v + 2Gss) log 2. To define G3, we need
to bound Σj= 07:
Σ
By Es [WW)]]]
(1 0)2(1 1-) Buyiks [|
j=1
j=1
==1
(25)
18 "(6L" + "0
E (1-aa)2(-
2(0
18 (6L + 300 -
1 (1 - ax)²
j=1
181 P (6L" + -30%) 7p h (2 - a)
181 (6L" + 30 7" = G3.
(33)
a
Upper bound for 6. The sequence 71,-.
7 forms a martingale difference sequence, since the definition of 23 leads to E | 4 -....... Li = E [zj] = 0 for all j E [t] Also, according to Lemma 4, we obtain that
| S [|(1 - a)- w/ + Egg,es [I(1 a) < 41,, + 4A = 8X (34)
where we
define 64
def
SAh.
Denoting the conditional variance of Z as o def
E
[2z)
2
Zi|
= Rg
[z we can bound o3 easily
(4) S
SA7. B
[||(1 - a) - i+ w - Engies [[KC [1(11a)) a)- [11
16 5
[I[C1 - (
(35)
Then, Lemma 3 implies
2
P by and
69 < G4 log
< 2exp
8",
8'
2G log 2 +
20aba 3
where the last identity is true, we set by = (Ies + /fees
/fees+200 + 2Gs
log 3.. To define G4, we need
to bound Ej= 73:
16X
E Es [1((1 1-1
w/y 1²] = 16A Σ (1 - 2 2(t-++111
11 Eas & ||الا1
j=1
j=1
j=1
18
2-P P (6IP + 30 70 16 181 1-p " + hoh GA.
16X3
Upper bound for C. Thanks to the proof of the bound on + (see (33)), we have already shown what we need: with probability 1
Eg, [1(--a)-5+1 (33) I
18X2-"(6IP + """
a
Upper bound on @, By definition of w/. with probability we have
t
Σ -1- w/
Σ - a) ( st1 |w,'||
(25)
< 4x (6LP + 70
1 (6L" + 30th) p Σ
(1 a)
39

---

To sum up, we introduce event E as follows
2
Esa- =
S by or
03 > G3 log
(36)
8"
==1
1813 " "0. (6r"++30))
where Cg =27t, G3-
[303 + V 133 +2Gs)
log J.- We have shown
that IP (Es,,) 2 1 111100 1-8".. We adjust the bound on b3:
1 2
2
2
log 2 8"
by
[ C3
3
+
V
9
c
+
2G3
log
8
<
g + /2Gs
4
2- (6LP + 300)) 7p
2 log 8"
An
+
36
3
4
(6LP + +300,
2 log
An
+
6/
3
adP
8"
Also we introduce event Eg, follows
2
ES
|8| ( S ba or
03 > G4 log
(37)
8"
==1
16 18 "(B1" """
where ca = c==
88 G4
ba (3c4+ + / + +2Ga log g.. We have shown
that IP [E 2 1-188 8 We adjust the bound on by:
b1
c
1 + V
o9 + 2G
log 8
2
-
2
c1 + 1/2G,
log 2 8"
9
16 2
16. 16A,
4- P (6LP + 30 7M
2 log
+
a
8"
16
(6LF + +30%) 70
2
+
21
log 8"
3
adi
Thus, the event Ex, n Eggt implies
4
1
Σ (1 - a) s
Σ (1 - - u
Σ (1 a) 1
$
+
j=1
6 + v22 . ② +2.0+ + 8
(6LP + nd
2 log 8"
(6I) + +00%)
An
+ 6
+ 4
atii
atP
16
(6LP + +300)) 7p + 24
2 log 8"
(6L) + +30%) at%
+
2x
+ 3622
3
at%
Assuming that Ao2 2
2(L+on) atr
we have the event Es, n E implies
Σ (1 - a)
An
4
+6V6+244 + 24 V
32
+ 48V6 + 216
2 log 8"
3
3
2 8"
s 59 log
40

---

Main Theorem Now we are ready to state and prove the main results of this section: high- probability convergence guarantees for Algorithm 2.
Theorem 5. Let Assumptions 2, 3 and 4 hold, and A Do F(woo) F.. parameters of Algorithm 2: stepsize
Then if the
A
A 12 L
A L
A
A
S min 2 LT
1408aT log
352 P T Tlog
ST V 168(1. + on 7 log
8T
(38)
momentum parameter and clipping levels
A max A VIDI
af
N
27
(39)
TT-
a²
for some T 2 1 and E (0, 1] such that log
ST 5
2 1. Then after T iterations of Algorithm the
iterates with probability least 1 - 8 satisfy
241 YT
Σ 1=0
IVF(=
(40)
T
Moreover. if we set (38) as identity, then the iterates generated by Algorithm 2 after T iterations with probability least 8 satisfy
max V on),
T log 8
[F(xx)]|
=0
(41)
T
T
implying that to achieve
E
[F I with probability least
5 Algorithm requires
2=_1 p-1
20_1
max
( +L
P-1
T=O
log
P-T
(42)
8
iterationsssapples
Proof. We remind in the proofs of Lemma 11 and Lemma 12 we have shown
2
2 G2 log
E
| < bi
Gi log
Ex.t
(2]
< bo or
0
gr
8
j=1
j=l
Ea.
(36)
3
< by
و3 >
G3 log
2
E
c < ba or
Σ
o3
G4 log
8"
8"1
j=l
j=l
where
181 2812-p0 D
4
2 log
6 = 2X, G1
b1 S
3 66
8'
16. 18A 4
POP
16
02 = 8A2, G2
b2 & X2
24
log gr
3
18A 2- (6IP + 30 7p
(6LF + 30
2
03 = 2Ap, G3
by S An
+ GV
log 8"
adP
16 181 4-P (6L" 30 7"
16
(6IL +30%) 7m
2
C1 = 8X2 G₁
bq $ X²
+ 24
log
3
z"
Moreover, according to Lemma 11 and Lemma 12, we have
IP (Eo.)) 1- 1', P (EE,)) 2 - 8', P [EE,t 2 1
-
8", PP
[(Es.) 1-8" 8".
41

---

The idea of the proof is based on technique form work of Gorbunov et al. [2020], Sadiev et al. [2023]. Liu et [2023b]: via mathematical induction we plan to show that for any {0, 1, ...... T 1} the event
G F F1,- n Pa,r F3,7 O Pa,r T. T where event E, is defined as
holds with probability at least
E
VF(2a) + A 22 VIST
and
F1,
n
Ea
E2,
M
Eagt
Fa,
Ea, n
F.
t=1
t=1
1=1
1=1
Basis of induction. Obviously, we have Go = Eg = 140 A S 2A1} holds with probability
1
Step of induction. Assume that the induction hypothesis is true for r 1: P 11 1r-10- One needs to prove TP {G+] 2 1 -r//T. We want mention that
E n F n E2,r 0 Es,r O Es.r = G O Eg,r n E n Es, n Em
Then, have
(Er-1 O FA,r O E2,r O Ea, O F4,7]
= PP (G,-1 1 O Forrr 0 E n BasT O F.B
= 1 - P (Gr-1 0 Ex,, n Ea,r O Fox O E
2 1 P {Gr-1 - -P/ Fai P (
- P (m
TP (EB
(T
1)0
2
-28'
28" -28"
T
Tō
6
=
+
28'
28"
T
T
7ō
T
where we have selected 8' 8"
The event E--1 implies for any S
47
S 7 A
[F + + < 2A1
Therefore, we have [|VF(x,)] < 2L4, < 2 S E/2 Assuming E, E E2.r Eg,r 0 E,,- happens, Lemma 10 implies
3y
72[(T +1)
([(r))l++Ar
S
A +
TA +
2
+2ya Σ
Σ (1
-i05
2
a [
1=1
37 LA +
[2L(T+11
< A
2
8T
8T
+447a(F + 1) log 8
+
118y(1 + 1) log
By setting clipping levels (39) and stepsize (38), have
A
A
VF A S +
-2A
4
4
42

---

Therefore, we obtain
[(G,) = P n F n F2,r 0 Fa,r n P
P [E,-1 1 2,, O Ea,r n E
2 Tō T
Thus, we have
P ( 2 P [GT] 1-
equivalently with probability at least - 6
1
2A1 7T
IVF(a)) + + S 24,
[VF(()))
T
Pugging (38) into the inequality above, have
2
[F((x))1
T
LA
VIA of
T
T
A1 + an) log T 1
1
max
T
ay
LAI log
g.
oa
log 8
Selecting 1/T-
p/20-1 1/1p-/2--111 (see (39)), obtain
1
VF(x:)]l
LA
A
VIA
T
T
A1 + on) Ing $
0
max
T T2p-1
T p-1
log
T
p-1
log
2/2p2/2p-1
max
(L + on)o
T log 5
Discussion. According Theorem 3, the sample complexity of Algorithm is
max { (L oo),
which has the same dependence on é as lower bounds do (see Theorem 1). However, the obtained upper bound has worst dependence on parameters L, G, Th. A₁ than lower bounds have. We suppose that this caused by the analysis techmique, since Algorithm has better convergence rate in terms of parameter dependence. This observation raises an interesting question: possible to conduct high-probabbilty analysis for Algorithm 1, or equivalently, Algorithm 2 without clipping?
43

---

G Experimental Results
We solve a simple quadratic problem. 2 ||>=|] in dimension 10, with synthetic noise sampled from two-sided Pareto distribution. Recall that two-sided Pareto distribution with tail index satisfies Assumption assumption with p < P. We consider different values of the tail index p ranging from 1.1 to 2.0. We start each algorithm from the same point sampled uniformly random from the standard normal distribution. Our empirical analysis consists of three experimental settings:
Cijy N9GDMtes
3000
Clip NSCIM
Clip NSCDiteas
1200
Iaratan
1000
2000
800
1500
600
1000
400
14
Clipping
Figure 3: Effect of Hessian Clipping Level
Figure 4: Number of iterations needed for Clip NSGDMHess and Clip NSGDM under Varying Tail Index to find a point with F S 3/2 starting with the same initial point. The perfor- mance of both algorithms decreases gradually with the decrease of the tail index. The iteration complexity of the second-order algorithm, Clip NSGDMHess is uniformly better for all values of p E (1.
A À on the Iteration Complexity. The plot shows the number of iterations required for Clip NSGDHess to find a point with F|)]( S 3/2. For extremely small and large values of X, more iterations are needed. The recommended value for this task A 10.
Effect of Clipping Level on Iteration Complexity. We run Algorithm (Clip NSGDHess) with A = À until it reached the target accuracy [[)(())] S 3/2. The stepsize and momentum parameters are set to y = 0.01 and a = 0.2. Clipping levels are varied from 10-16 to 10s in multiplicative steps of 10. In Figure 3, observe that intermediate clipping (A 10) yields the lowest iteration complexity, also refer to Table 2 for precise numerical values. Extremely small or large values lead to slower convergence. The proposed algorithm tolerates very small values of X, but very large values (e.g.. À > 10²) result in very slow convergence. This empirically confirms the need for Hessian clipping to stabilize convergence and achieve fast convergence.
Clipping Level,
10 16
10-8
8
10
10
10a
Iterations
632
471
315
560
1506
Table 2: Iteration complexity depending on the clipping level A An for Algorithm (Clip NSGDHess), cf. Figure 4.
2. Comparison with Clip NSGDM under Varying Tail Index. We compare Clip NSGDHess with Clip NSGDM (which was proposed Cutkosky and Mehta [2021]). For Clip NSGDM, we
T 3p-2 For both methods we fixed T = 4000, x = 0.5, and Å = 0.03. These experiments were conducted to complement Figure 1, which presents the theoretical iteration complexities. As shown in Figure the empirical results align with the theory: Clip NSGDHess consistently outperforms Clip NSGDM, and the performance gap becomes larger as p increases. This provides strong empirical support for our theoretical findings.
used the theoretical parameter choices: stepsize 7 T 3 and momentum
Sensitivity to Gradient Clipping for Fixed Hessian Clipping- this set of experiments, we test Clip NSGDHess (Algorithm 2). Our goal is to study how iteration complexity depends on the choice of the gradient clipping level when the Hessian clipping level is fixed. Specifically, we test three different values of the Hessian clipping level, and vary the gradient clipping threshold A:
44

---

For A = 0.01: À ranged from 10 to 102 (step 10).
For A 1.0: À ranged from 10-2 to 10 (step 10).
For A = 10: À ranged from 10 to 10 (step 10).
The results summarized in Figure 5.
Y- 0,01, a 6.1, 0.03
A.
17500
Citp S.50iiiii
15000
80000
12500
Iurarion
10000
7500
60000
5000
2500
0
Citpping
Citppiigg
NSCDdles
70000
50000
40000
30000
20000
10000
10"
100
10
107
100
100
Clipping level,
Figure 5: Iteration complexity of Clip NSGDHess (Algorithm 2) depending on gradient clipping for the three different fixed values of Hessian clipping Y E 1,
In all cases, the algorithm is tested until VF(x)]] < 5 We observe that intermediate values of À yield the best performance across all three regimes (small, medium, and large Hessian clipping levels). As shown in Figure 5, both extremely small and extremely large values of À lead to higher iteration complexity, while moderate choices minimize it. The optimal values are:
X = 1.0 for \, 0.01,
0.1 for A = 1.0,
A = 10.0 for d 100.0.
These findings confirm that moderate clipping levels are erucial for achieving the best performance aligning with our theoretical findings in Theorem 3.
45


Reviews:
[{"review_id": "q6DedcP2p5", "reviewer": "Reviewer_GxUC", "summary": "This paper studies nonconvex stochastic optimization for smooth functions where both stochastic gradients and Hessians have $p$-th bounded central moment for $p \\in (1, 2]$. The authors establish minmax lower bounds on the sample complexity of second order stochastic methods for the considered problem class and zero-respecting algorithms. A near optimal algorithm, i.e., Normalized SGD with Hessian correction, is proposed and shown to achieve in-expectation upper bounds that almost matches with the lower bound. In addition, the, a clipped variant of the previous algorithm, i.e., Normalized SGD with Hessian correction and clipping, is shown to achieve nearly optimal high-probability convergence.", "questions": "1. In line 160, is it $q$-th order?\n2. In definition 1, can the authors provide some examples on algorithms that belong to the defined algorithm family?", "limitations": "N.A.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: \n1. This paper for the first time proposes SOSO methods to address heavy-tailed noise. \n2. The minmax lower bound is shown to be tight in several special cases. \n3. Near-optimal algorithms are designed to match the lower bounds in the in-expectation, and high-probability sense with logarithmic failure probability dependence, respectively. \n\nWeakness:\n1. There is a lack of compelling numerical or analytical examples showcasing the advantages of SOSO over first-order methods.", "was_revised": true, "final_justification": "I have read the reviews from other reviewers and author's rebuttal. I decided to keep my original score.", "rebuttal": "Dear Reviewer GxUC,\n\nThank you very much for your detailed and encouraging review. We appreciate your positive assessment of the paper’s originality, theoretical rigor, and clarity. We are glad that you found the contributions—including the tight minimax lower bound and the near-optimal SOSO algorithms under heavy-tailed noise—novel and significant. Below, we address your thoughtful comments regarding numerical validation, clarify technical points (such as the algorithm family in Definition 1), and correct minor inconsistencies in the manuscript.\n\n> __Q1:__ In line 160, is it $q$-th order?\n\n\n__A1:__ Yes, this is a typo, thanks for catching this.\n\n\n>__Q2:__  In definition 1, can the authors provide some examples on algorithms that belong to the defined algorithm family?\n\n\n__A2:__ Examples of algorithms satisfying definition 1 include many common algorithm. For example, SGD (with and without momentum), stochastic BFGS and L-BFGS, Stochastic Newton’s method (with and without cubic regularization), first and second-order trust-region method. To support our claim we refer to Carmon et al., 2019 (page 80 in the published version), see also Arjevani et al., 2020. We will add a remark about this important question in our revision. \n\nY. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points I. Mathematical Programming, May 2019.\n\nYossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, Karthik Sridharan. Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations. COLT 2020."}, {"review_id": "SrlzXaYY3C", "reviewer": "Reviewer_oE5T", "summary": "In this submission, the authors present a theoretical analysis of second-order optimization in the presence of heavy-tailed noise, addressing the common issue that such methods often underperform and lack guarantees in this setting. They consider scenarios where stochastic gradients and Hessians have only bounded first- and second-order moments, and derive tight lower bounds on the sample complexity for any second-order method. To complement their analysis, the authors propose a normalized stochastic gradient descent algorithm that leverages second-order information and matches the established lower bounds. They also introduce a novel gradient and Hessian clipping technique, along with high-probability upper bounds to support its effectiveness.", "questions": "1. From assumptions one to four, this analysis seems to be independent of the convexity of the objective function. All results are applicable in the non-convex setting. If we add the assumption of convexity or even strong convexity, how will these convexity condition improve the lower bound and the sample complexity of the proposed algorithms? All assumptions from this submission are relevant to the smoothness or Lipshiz continuity of both gradients and Hessian. If we add some lower bounds for the smallest eigenvalue of the Hessian, how will the the number of oracle queries required to find an ε-stationary point be reduced? Will this be some future research direction?\n\n2. I'm not sure whether the proposed Normalized stochastic gradient decent with Hessian correction (with gradient clipping and Hessian clipping) belong to the class of second-order optimization algorithms. In fact this proposed algorithm utilize the second-order Hessian matrix information, but in general second-order optimization algorithm correspond to Newton type methods such as Newton's method, quasi-Newton method (BFGS, DFP ,SR1) or L-BFGS with iterations like: $x_{t + 1} = x_t - B_t \\nabla{f(x_t)}$ where $B_t$ is some matrix that approximates the exact Hessian matrix $\\nabla^2{f(x_t)}$. This Hessian approximation matrix $B_t$ is usually constructed using some first-order gradient informations.  However, the proposed variant SGD method has no such iteration updating forms. Hence, strictly speaking, the proposed Normalized SGD with Hessian correction belong to the first-order optimization algorithms which utilized some second-order Hessian queries. This method don't belong to the formal \"second-order\" optimization class.\n\n3. From Theorem 2 and Theorem 3, both the step size $\\gamma$ from the normalized SGD and the clipping threshold $\\lambda$ from the clipping technique requires the estimate the initial sub-optimality $\\delta = f(x_0) - f(x_*)$. How to estimate this initial sub-optimality in practice? Theorem 2 and 3 presented that $\\gamma$ and $\\lambda$ need to be set by values of this initial sub-optimality $\\delta$ to reach the corresponding sample complexity. Hence, the proposed methods are impractical since it is in general very difficult to estimate the initial sub-optimality accurately.", "limitations": "The authors have presented all the limitations of this work in the last section of the paper.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper makes several high-quality theoretical contributions, summarized as follows:\n\n1. It establishes a lower bound on the sample complexity for any second-order stochastic optimization algorithm under the p-BCM noise model, showing that using higher-order derivatives does not necessarily improve the convergence rate under the same noise assumptions.\n\n2. It proposes a stochastic gradient descent method that leverages second-order Hessian information and proves that its sample complexity matches the previously established lower bound.\n\n3. It introduces a gradient and Hessian clipping technique and demonstrates that this method can achieve near-optimal sample complexity with high confidence.\n\nThese theoretical advances contribute significantly to the optimization community’s understanding of second-order stochastic methods in high-noise settings.\n\nThe main weakness of this submission is the lack of sufficient empirical results. The paper should include more numerical experiments evaluating the proposed Normalized SGD with Hessian correction algorithm and the gradient and Hessian clipping methods. Presenting empirical performance would help verify whether these novel algorithms align with the theoretical predictions.\n\nFor instance, since the normalized SGD with Hessian correction combined with clipping requires a clipping threshold parameter $\\lambda$, the authors should explore the impact of varying $\\lambda$ values on the algorithm’s performance. This would help assess whether the clipping technique enhances robustness. Incorporating such numerical experiments would significantly strengthen the paper and, if the empirical results support the theory, greatly increase its publication potential.", "was_revised": true, "final_justification": "The rebuttal results of numerical experiments solve my concerns. I raised the score from 3 to 4.", "rebuttal": "Dear Reviewer oE5T,\n\nThank you for your detailed and thoughtful review. We sincerely appreciate your recognition of our theoretical contributions, including the lower bound under the p-BCM noise model, the matching upper bound via our second-order algorithm, and the development of the gradient and Hessian clipping technique that achieves near-optimal sample complexity with high probability.\n\nWe would like to address your main concern regarding the empirical evaluation:\n\n\n>__Q1:__ The main weakness of this submission is the lack of sufficient empirical results. The paper should include more numerical experiments evaluating the proposed Normalized SGD with Hessian correction algorithm and the gradient and Hessian clipping methods. Presenting empirical performance would help verify whether these novel algorithms align with the theoretical predictions.\n\n\n__A1:__ During the rebuttal period, we conducted several numerical experiments that are not included in the current version of the paper but will be added in the final revision. Due to NeurIPS policy, we are unable to include figures; however, we describe the results below.\nWe solved a simple quadratic problem, $\\frac{1}{2}\\|x\\|^2$, in dimension $d = 10$, with synthetic noise sampled from a symmetrized Pareto distribution. We considered both a fixed heavy-tailed regime with tail index $p = 1.1$ and a variable tail index ranging from $1.1$ to $2.0$. We start each algorithm from the same point sampled uniformly at random from the standard normal distribution.\nOur empirical analysis consists of three experimental settings:\n\n__1. Effect of Clipping Level on Iteration Complexity:__\nWe ran Algorithm 2 (Clip NSGDHess) with $\\lambda_h = \\lambda$ until it reached the target accuracy of $\\|\\nabla F(x)\\| \\leq 3/2$. The stepsize and momentum parameters were set to $\\gamma = 0.01$ and $\\alpha = 0.2$. Clipping levels were varied from $10^{-16}$ to $10^3$ using a multiplicative step of 10. The results are shown below:\n| $\\lambda$        | $10^{-16}$ | $10^{-8}$ | $10$ | $10^{2}$ | $10^{3}$ |\n|------------------|------------|-----------|------|----------|----------|\n| Iterations       | $632$        | $471$       | $\\mathbf{321}$ | $562$      | $1506$     |\n\nTable 1: Intermediate clipping ($\\lambda = 10$) yields the lowest iteration complexity. Extremely small or large values lead to slower convergence. The proposed algorithm can gracefully tolerate very small values of clipping parameter $\\lambda$, but using values larger than $\\lambda = 10^3$ leads to very slow convergence. This observation motivates the need for gradient and hessian clipping. \n\n__2.Comparison with Clip NSGDM under Varying Tail Index:__\nWe compared Clip NSGDHess with Clip NSGDM (as proposed in [2]). For Clip NSGDM, we used the stepsize $\\gamma = T^{-\\frac{2p-1}{3p-2}}$ and momentum $\\alpha = T^{-\\frac{p}{3p-2}}$ according to theory. For Clip NSGDHess, both parameters were set to $T^{-\\frac{p}{2p-1}}$. We fixed $\\lambda = 0.5$, $\\bar{\\lambda}_h = 0.05$, and $T = 4000$ iterations.\n\n| Tail index, $p$ | Iteration Complexity (Clip NSGDM) | Iteration Complexity (Clip NSGDHess) |\n|----------------|--------------------------------------------|--------------------------------------|\n| $1.2$            | $2476$                                       | $2128$                                 |\n| $1.6$            | $1183$                                       | $726 $                                 |\n| $2.0$            | $877$                                        | $444$                                  |\n\n\nTable 2: Clip NSGDHess consistently outperforms Clip NSGDM, with the gap increasing for smaller $p$, i.e., heavier-tailed noise. Visually the picture looks similar to theoretical complexities in Figure 1 of our original submission. \n\n[2] Cutkosky, Ashok, and Harsh Mehta. \"High-probability bounds for non-convex stochastic optimization with heavy tails.\" Advances in Neural Information Processing Systems 34 (2021): 4883-4895.\n\n\n\n\n> __Q2:__ From assumptions one to four, this analysis seems to be independent of the convexity of the objective function. All results are applicable in the non-convex setting. If we add the assumption of convexity or even strong convexity, how will these convexity condition improve the lower bound and the sample complexity of the proposed algorithms? \n\n__A2:__ In the convex case, under bounded variance ($p=2$) the upper and lower bounds were derived, e.g., in [1]. It turns out that when the function is convex, the use of second-order information does not improve the stochastic gradient complexity $O(\\varepsilon^{-2})$. Therefore, we do not expect further improvement for other $p\\in (1, 2)$ for our method as well. However, the situation in our non-convex setting is different and the sample complexity can be reduced uniformly for all $p\\in (1, 2]$ using the second-order information. \n\n[1] Artem Agafonov, Dmitry Kamzolov, Alexander Gasnikov, Ali Kavis, Kimon Antonakopoulos, Volkan Cevher, Martin Takáč. Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness. ICLR 2024.  \n\n> __Q3:__ All assumptions from this submission are relevant to the smoothness or Lipshiz continuity of both gradients and Hessian. If we add some lower bounds for the smallest eigenvalue of the Hessian, how will the the number of oracle queries required to find an $\\varepsilon$-stationary point be reduced? Will this be some future research direction?\n\n__A3:__ Since we assume $L$-Lipschitz continuous gradient (smoothness) and the function is twice-differentiable, we already have a lower bound for the smallest eigenvalue of the Hessian equal to $\\ell = -L$. Therefore, such assumption does not help improve the complexity in terms of the $\\varepsilon$. However, one can consider a more refined setting where the smallest eigenvalue is $\\ell > -L$ and improve the sample complexity in terms of dependence on $L$. We leave such refinement for future work. \n\n\n> __Q4:__  I'm not sure whether the proposed Normalized stochastic gradient decent with Hessian correction (with gradient clipping and Hessian clipping) belong to the class of second-order optimization algorithms. In fact this proposed algorithm utilize the second-order Hessian matrix information, but in general second-order optimization algorithm correspond to Newton type methods such as Newton's method, quasi-Newton method (BFGS, DFP ,SR1) or L-BFGS with iterations like: $x_{t+1}  = x_t - B_t \\nabla f(x_t)$ where $B_t$ is some matrix that approximates the exact Hessian matrix $\\nabla^2 f(x_t)$. This Hessian approximation matrix  is usually constructed using some first-order gradient informations. However, the proposed variant SGD method has no such iteration updating forms. Hence, strictly speaking, the proposed Normalized SGD with Hessian correction belong to the first-order optimization algorithms which utilized some second-order Hessian queries. This method don't belong to the formal \"second-order\" optimization class.\n\n\n__A4:__ Thank you for your thoughtful comment. We respectfully clarify that the use of second-order information is the defining characteristic of second-order optimization methods, and such methods are not necessarily restricted to the Newton-type update form $x_{t+1}  = x_t - B_t \\nabla f(x_t)$. For instance, cubic Newton methods and trust-region methods are widely recognized as second-order algorithms, yet they do not conform to this canonical iteration. Similarly, our proposed Normalized SGD with Hessian correction explicitly utilizes Hessian information to adapt the updates, thereby leveraging second-order curvature information.\nTherefore, while our method differs structurally from Newton and quasi-Newton schemes, it naturally belongs to the broader class of second-order optimization methods.\n\n\n> __Q5:__  From Theorem 2 and Theorem 3, both the step size $\\gamma$ from the normalized SGD and the clipping threshold $\\lambda$ from the clipping technique requires the estimate the initial sub-optimality $\\delta = f(x) - f(x_*)$. How to estimate this initial sub-optimality in practice? Theorem 2 and 3 presented that $\\gamma$ and $\\lambda$ need to be set by values of this initial sub-optimality \\delta to reach the corresponding sample complexity. Hence, the proposed methods are impractical since it is in general very difficult to estimate the initial sub-optimality accurately.\n\n__A5:__ We can propose two strategies. If a lower bound on $F(x_*) \\geq F^{\\text{LB}}$ is available (e.g., it is zero) we can replace $\\delta$ with $F(x) - F^{\\text{LB}}$, where $F(x)$ can be estimated, e.g., using a mini-batch. In general any upper bound on $\\delta$ suffices. Another valid strategy that will work for Algorithm 1 is to set step-size $\\gamma = \\sqrt{\\frac{ \\alpha^{\\frac{1}{p}}}{ T}}$, momentum $\\alpha = \\left(\\frac{1}{T}\\right)^{\\frac{p}{2p-1}}$ if $p$ is known or $\\gamma = \\sqrt{\\frac{ \\alpha^{\\frac{1}{2}}}{ T}}$, momentum $\\alpha = \\left(\\frac{1}{T}\\right)^{\\frac{2}{3}}$ if $p$ is unknown. Following the proof strategy similar to (Hübler et al, 2024), we can establish convergence of our algorithm. If $p$ is known the convergence rate of the algorithm will have the same dependence on $T$ and $p$ as Theorem 2, i.e., $\\mathcal{O}(T^{-\\frac{p-1}{2p-1}})$ and if $p$ is unknown, the method will still converge but slower, i.e., $\\mathcal{O}(T^{-\\frac{2(p-1)}{3p}})$. \n\nFlorian Hübler, Ilyas Fatkhullin, Niao He. From Gradient Clipping to Normalization for Heavy Tailed SGD. AISTATS 2025."}, {"review_id": "ooJ9iFRs33", "reviewer": "Reviewer_JJgW", "summary": "This paper studies second-order optimization algorithms with heavy-tailed noise. A lower bound on the sample complexity for second-order algorithms is established along with an algorithm to match it in terms of first moment error. A second algorithm with clipping with high probability guarantees for the estimation error is proposed and shown to achieve near-optimal sample complexity.", "questions": "- Is \\xi assumed to be i.i.d.? If not, is the expectation taken at steady-state (if \\xi is Markovian for example)?The authors need to explicitly state their assumptions on the noise. \n\n- Is the BCM assumption that much weaker than the p-moment bound assumption of [Zhang et al., 2020]? Why is the difference between these assumptions that important?\n\n-What is the difference between O(.) and \\Omega(.)? Why the need for two different notations? Also, Thm 1 uses \\Theta(.), what is that?", "limitations": "The assumptions of this paper are clearly identified and the authors provide a discussion on thee limitations of their work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This paper has interesting contributions which, as far as I am concerned, are indeed novel. The assumptions, contributions and setting of the paper are clearly identified early on, making it easy to read. I was not able to check the proofs in detail.\n\nRegardless, I would encourage the authors to proof-read their paper as I found a few typos while reading it. (e.g. E[  || \\nabla f(x,\\xi) || ]^p \\leq B when talking about bounds on pth moment).\n \nOne weakness of this submission is the lack of numerical studies to illustrate the theory developed in the paper. While, the authors provide two plots in page 3, very little discussion is provided regarding the setup of their experiments and how these plots are related to the theorems in their paper. I would encourage the authors to include a simple toy problem illustrating their sample complexity bound. Figure 1 shows a plot of the sample complexity, but not details on this experiment are provided.\n\nIn terms of clarity, I also think that there is some work needed. For example, the authors should explicit say which algorithm (i.e. first equation of section B) they focus on in the very beginning of the paper to engage the reader and avoid confusion. Also, the authors reference Table 1 in the main text, but do not mention this table is in the supplementary material, which might create confusion.\n\nI think a statement on how the choice of g_0 changes the sample complexity of algorithm 2 should be included in the main text. Fine details do not need to be included, but the fact that it only changes a constant on the sample complexity and not the dependency on \\epsilon.", "was_revised": true, "final_justification": "The authors' rebuttal addressed my concerns. I retain my initial score, which recommended acceptance.", "rebuttal": "Dear Reviewer JJgW,\n\nThank you for your review and for your positive evaluation of the novelty and clarity of our contributions. We are glad to hear that you found the setting, assumptions, and theoretical results clearly presented. We also appreciate your constructive suggestions regarding clarity, notation, and experimental presentation, and we address each of your comments and questions in detail below. \n\n\n> __Q1:__ I would encourage the authors to include a simple toy problem illustrating their sample complexity bound. \n\n__A1:__ We want to mention that Figure 1 is not an experiment. It is an illustration of theoretically optimal complexity bounds (upper and lower bounds are matching) for SOSO and FOSO in order to support understanding. This plot implies that for the entire range of tail indices $p \\in (1, 2]$, methods with access to second-order information have reduced sample complexity than methods that only have access to first-order information. Figure 2 is a toy experiment, which motivates us to study second-order methods and algorithms with clipping in depth. The most important information related to this experiment is provided in the caption to Figure 2. During the rebuttal phase, we conduct the following additional ablation studies on the same toy problem, which provide insights on theoretically derived complexities and the sensitivity to clipping threshold tuning. \n\nWe solved a simple quadratic problem, $\\frac{1}{2}\\|x\\|^2$, in dimension $d = 10$, with synthetic noise sampled from a symmetrized Pareto distribution. We considered both a fixed heavy-tailed regime with tail index $p = 1.1$ and a variable tail index ranging from $1.1$ to $2.0$. We start each algorithm from the same point sampled uniformly at random from the standard normal distribution.\nOur empirical analysis consists of three experimental settings:\n\n__1. Effect of Clipping Level on Iteration Complexity:__\nWe ran Algorithm 2 (Clip NSGDHess) with $\\lambda_h = \\lambda$ until it reached the target accuracy of $\\|\\nabla F(x)\\| \\leq 3/2$. The stepsize and momentum parameters were set to $\\gamma = 0.01$ and $\\alpha = 0.2$. Clipping levels were varied from $10^{-16}$ to $10^3$ using a multiplicative step of 10. The results are shown below:\n| $\\lambda$        | $10^{-16}$ | $10^{-8}$ | $10$ | $10^{2}$ | $10^{3}$ |\n|------------------|------------|-----------|------|----------|----------|\n| Iterations       | $632$        | $471$       | $\\mathbf{321}$ | $562$      | $1506$     |\n\n__Table 1:__ Intermediate clipping ($\\lambda = 10$) yields the lowest iteration complexity. Extremely small or large values lead to slower convergence. The proposed algorithm can gracefully tolerate very small values of clipping parameter $\\lambda$, but using values larger than $\\lambda = 10^3$ leads to very slow convergence. This observation motivates the need for gradient and hessian clipping. \n\n__2.Comparison with Clip NSGDM under Varying Tail Index:__\nWe compared Clip NSGDHess with Clip NSGDM (as proposed in [2]). For Clip NSGDM, we used the stepsize $\\gamma = T^{-\\frac{2p-1}{3p-2}}$ and momentum $\\alpha = T^{-\\frac{p}{3p-2}}$ according to theory. For Clip NSGDHess, both parameters were set to $T^{-\\frac{p}{2p-1}}$. We fixed $\\lambda = 0.5$, $\\bar{\\lambda}_h = 0.05$, and $T = 4000$ iterations.\n\n| Tail index, $p$ | Iteration Complexity (Clip NSGDM) | Iteration Complexity (Clip NSGDHess) |\n|----------------|--------------------------------------------|--------------------------------------|\n| $1.2$            | $2476$                                       | $2128$                                 |\n| $1.6$            | $1183$                                       | $726 $                                 |\n| $2.0$            | $877$                                        | $444$                                  |\n\n\n__Table 2:__ Clip NSGDHess consistently outperforms Clip NSGDM, with the gap increasing for smaller $p$, i.e., heavier-tailed noise. Visually the picture looks similar to theoretical complexities in Figure 1 of our original submission. \n\n[2] Cutkosky, Ashok, and Harsh Mehta. \"High-probability bounds for non-convex stochastic optimization with heavy tails.\" Advances in Neural Information Processing Systems 34 (2021): 4883-4895.\n\n\n__3.Sensitivity to Gradient Clipping for Fixed Hessian Clipping:__\nWe fixed the Hessian clipping level and varied the gradient clipping level $\\lambda$:\n\n- For $\\bar{\\lambda}_{h} = 0.1$: we set $\\lambda$ from $10^{-3}$ to $10^{3}$ with multiplicative step $10$;\n- For $\\bar{\\lambda}{h} = 1.0$: we set  $\\lambda$ from $10^{-2}$ to $10^{4}$ with multiplicative step $10$;\n- For $\\bar{\\lambda}{h} = 10$:  we set  $\\lambda$ from $10^{-1}$ to $10^{5}$ with multiplicative step $10$.\n\nIn all cases, the algorithm was run until $\\|\\nabla F(x)\\| \\leq \\frac{1}{2}$. We consistently observed that both extremely small and large values of $\\lambda$ led to higher iteration complexity. The optimal values were:\n\n- $\\lambda = 0.01$ for $\\bar{\\lambda}_h = 0.1$;\n- $\\lambda = 0.1$ for $\\bar{\\lambda}_h = 1.0$;\n- $\\lambda = 1.0$ for $\\bar{\\lambda}_h = 10$.\n\nThis pattern confirms that intermediate clipping levels are crucial for performance.\n\n\n\n> __Q2:__ I think a statement on how the choice of g_0 changes the sample complexity of algorithm 2 should be included in the main text. Fine details do not need to be included, but the fact that it only changes a constant on the sample complexity and not the dependency on \\epsilon.\n\n__A2:__ Thank you for the suggestion! We will add an additional discussion about it in the main text of the camera-ready version. \n\n>  __Q3:__  Is \\xi assumed to be i.i.d.? If not, is the expectation taken at steady-state (if \\xi is Markovian for example)? The authors need to explicitly state their assumptions on the noise. \n\n__A3:__ On each iteration we sample $\\xi$ independently from the same distribution, so the sequence $(\\xi_t)_{t \\geq 1}$ is assumed to be i.i.d. We will clarify this in the revision.\n\n>  __Q4:__  Is the BCM assumption that much weaker than the p-moment bound assumption of [Zhang et al., 2020]? Why is the difference between these assumptions that important?\n\n__A4:__ Our $p$-BCM assumption is weaker than $p$-th bounded moment. To see this, it is sufficient to show it for $p=2$. By bias-variance decomposition\n$\\mathbb E \\|\\nabla f(x, \\xi)\\|^2 = \\|\\nabla F(x)\\|^2 + \\mathbb E \\|\\xi\\|^2 \\geq \\mathbb E \\|\\xi\\|^2. $\nOn the other hand, $p$-th bounded moment assumption can be restrictive as it implies bounded gradients even in case $p=2$ as can be seen from the above decomposition. The class of Lipschitz smooth functions with unbounded gradients is much richer than the one with bounded gradients. In particular, it includes an important sub-class of quadratic functions.  \n\n> __Q5:__ What is the difference between O(.) and \\Omega(.)? Why the need for two different notations? Also, Thm 1 uses \\Theta(.), what is that?\n\n\n__A5:__ Thank you for your question, we will add this in the notations section. \n\n- $f(n) = \\mathcal{O}(g(n))$ if there exist $C >0$ and $n_0$ such that for all $n \\geq n_0$ the following inequality holds, $0\\leq f(n) \\leq C g(n)$;\n- $f(n) = \\Omega(g(n))$ if there exist $c>0$ and $n_0$ such that for all $n \\geq n_0$ the following inequality holds, $0\\leq cg(n) \\leq f(n) $;\n- $f(n) = \\Theta(g(n))$ if there exist $ C> 0$ and $c>0$ and $n_0$ such that for all $n \\geq n_0$ the following inequality holds, $0\\leq cg(n ) \\leq f(n) \\leq C g(n) $;\n\nFor more details, we refer to the book: Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022."}, {"review_id": "4cHaMcgUVE", "reviewer": "Reviewer_tAtg", "summary": "This paper studies the problem of second-order stochastic optimization (SOSO) under heavy-tailed noise, a setting where both stochastic gradients and Hessians only have bounded p-th moments, which is common in modern machine learning tasks with outliers or data heterogeneity. The paper establishes tight minimax lower bounds on the sample complexity for any second-order optimization algorithm under heavy-tailed noise. The results demonstrate that second-order methods can still achieve provable improvements over first-order methods, even in heavy-tailed regimes. The paper proposes a normalized SGD with Hessian correction algorithm that incorporates second-order information and provably achieves the established lower bond for finding approximate stationary points. The paper also introduces Hessian clipping, an extension of gradient clipping to handle extreme noise in Hessian estimates.", "questions": "Please refer the the weaknesses section.", "limitations": "No", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper is well-written and well-structured, easy to read and follow.\n- This paper provides rigorous theoretical contribution.\n- The analysis is technically sound and comprehensive, covering both in-expectation and high-probability results and addressing the impact of gradient and Hessian noise.\n- The originality of this paper is clear and solid.\nWeaknesses:\n- The experimental validation is minimal, consisting only of toy synthetic experiments in low dimensions. There is no evaluation on real-world machine learning tasks to demonstrate practical effectiveness.\n- The proposed methods require assumptions on hyperparameters and question setup, which may limit their practical usability.\n- While theory is strong, there is no discussion of computational costs for Hessian-vector products or clipping in large-scale models.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer tAtg,\n\nThank you for your thorough and thoughtful review, and for your positive evaluation of the paper’s clarity, originality, and theoretical contribution. We are especially grateful for your recognition of the strength of our analysis, including both in-expectation and high-probability results under heavy-tailed noise. Below, we respond to your comments regarding experimental validation, practical considerations, and assumptions, and we appreciate your suggestions for further strengthening the paper.\n\n\n> __Q1:__ The experimental validation is minimal, consisting only of toy synthetic experiments in low dimensions. There is no evaluation on real-world machine learning tasks to demonstrate practical effectiveness.\n\n\n__A1:__ We acknowledge the importance of empirical evaluation of the algorithms on real-world machine learning tasks, and we are planning to test our algorithms on more serious tasks in the future. However, the main goal of this work is to understand the theoretical complexity limits of second-order stochastic algorithms under challenging heavy-tailed settings. Our Algorithm 1 was already tested before in reinforcement learning literature [Salehkaleybar et al., 2022, Fatkhullin et al., 2023] with promising results. We are hopeful that our theoretical enhancement with gradient and Hessian clipping (Algorithm 2) will further improve the practical performance, and we leave this for future work. \n\nWe also find controlled synthetic experiments insightful and important, especially in the initial phase of algorithmic development. We conduct the following additional ablation studies, which provide insights on theoretically derived complexities and the sensitivity to clipping threshold tuning. \n\nWe solved a simple quadratic problem, $\\frac{1}{2}\\|x\\|^2$, in dimension $d = 10$, with synthetic noise sampled from a symmetrized Pareto distribution. We considered both a fixed heavy-tailed regime with tail index $p = 1.1$ and a variable tail index ranging from $1.1$ to $2.0$. We start each algorithm from the same point sampled uniformly at random from the standard normal distribution.\nOur empirical analysis consists of three experimental settings:\n\n__1. Effect of Clipping Level on Iteration Complexity:__\nWe ran Algorithm 2 (Clip NSGDHess) with $\\lambda_h = \\lambda$ until it reached the target accuracy of $\\|\\nabla F(x)\\| \\leq 3/2$. The stepsize and momentum parameters were set to $\\gamma = 0.01$ and $\\alpha = 0.2$. Clipping levels were varied from $10^{-16}$ to $10^3$ using a multiplicative step of 10. The results are shown below:\n| $\\lambda$        | $10^{-16}$ | $10^{-8}$ | $10$ | $10^{2}$ | $10^{3}$ |\n|------------------|------------|-----------|------|----------|----------|\n| Iterations       | $632$        | $471$       | $\\mathbf{321}$ | $562$      | $1506$     |\n\n__Table 1:__ Intermediate clipping ($\\lambda = 10$) yields the lowest iteration complexity. Extremely small or large values lead to slower convergence. The proposed algorithm can gracefully tolerate very small values of clipping parameter $\\lambda$, but using values larger than $\\lambda = 10^3$ leads to very slow convergence. This observation motivates the need for gradient and hessian clipping. \n\n__2.Comparison with Clip NSGDM under Varying Tail Index:__\nWe compared Clip NSGDHess with Clip NSGDM (as proposed in [2]). For Clip NSGDM, we used the stepsize $\\gamma = T^{-\\frac{2p-1}{3p-2}}$ and momentum $\\alpha = T^{-\\frac{p}{3p-2}}$ according to theory. For Clip NSGDHess, both parameters were set to $T^{-\\frac{p}{2p-1}}$. We fixed $\\lambda = 0.5$, $\\bar{\\lambda}_h = 0.05$, and $T = 4000$ iterations.\n\n| Tail index, $p$ | Iteration Complexity (Clip NSGDM) | Iteration Complexity (Clip NSGDHess) |\n|----------------|--------------------------------------------|--------------------------------------|\n| $1.2$            | $2476$                                       | $2128$                                 |\n| $1.6$            | $1183$                                       | $726 $                                 |\n| $2.0$            | $877$                                        | $444$                                  |\n\n\n__Table 2:__ Clip NSGDHess consistently outperforms Clip NSGDM, with the gap increasing for smaller $p$, i.e., heavier-tailed noise. Visually the picture looks similar to theoretical complexities in Figure 1 of our original submission. \n\n[2] Cutkosky, Ashok, and Harsh Mehta. \"High-probability bounds for non-convex stochastic optimization with heavy tails.\" Advances in Neural Information Processing Systems 34 (2021): 4883-4895.\n\n\n__3.Sensitivity to Gradient Clipping for Fixed Hessian Clipping:__\nWe fixed the Hessian clipping level and varied the gradient clipping level $\\lambda$:\n\n- For $\\bar{\\lambda}_{h} = 0.1$: we set $\\lambda$ from $10^{-3}$ to $10^{3}$ with multiplicative step $10$;\n- For $\\bar{\\lambda}{h} = 1.0$: we set  $\\lambda$ from $10^{-2}$ to $10^{4}$ with multiplicative step $10$;\n- For $\\bar{\\lambda}{h} = 10$:  we set  $\\lambda$ from $10^{-1}$ to $10^{5}$ with multiplicative step $10$.\n\nIn all cases, the algorithm was run until $\\|\\nabla F(x)\\| \\leq \\frac{1}{2}$. We consistently observed that both extremely small and large values of $\\lambda$ led to higher iteration complexity. The optimal values were:\n\n- $\\lambda = 0.01$ for $\\bar{\\lambda}_h = 0.1$;\n- $\\lambda = 0.1$ for $\\bar{\\lambda}_h = 1.0$;\n- $\\lambda = 1.0$ for $\\bar{\\lambda}_h = 10$.\n\nThis pattern confirms that intermediate clipping levels are crucial for performance.\n\n\n> __Q2:__ The proposed methods require assumptions on hyperparameters and question setup, which may limit their practical usability.\n\n__A2:__ This is a valid concern, and we can offer a strategy that avoids any tuning requirement in Algorithm 1. We can set step-size $\\gamma = \\sqrt{\\frac{ \\alpha^{\\frac{1}{2}}}{ T}}$, momentum $\\alpha = \\left(\\frac{1}{T}\\right)^{\\frac{2}{3}}$. Following the proof strategy similar to (Hübler et al, 2024), we can establish convergence of our algorithm with this step-size strategy. Similarly to the observations in (Hübler et al, 2024), our convergence rate will become slower: $\\mathcal{O}(T^{-\\frac{p-1}{3p}})$ instead of $\\mathcal{O}(T^{-\\frac{p-1}{2p-1}})$ (and the constant behind $\\mathcal{O}$) will be larger. Nevertheless, this strategy avoids any parameter tuning and ensures non-asymptotic convergence. In case of Algorithm 2, the situation is more complex and we do not have a good strategy for setting clipping thresholds when problem parameters are unknown. Since the main focus of our paper is understanding the sample complexity upper and lower bounds when all parameters are known, we omit the discussion of these details. \n\nFlorian Hübler, Ilyas Fatkhullin, Niao He. From Gradient Clipping to Normalization for Heavy Tailed SGD. AISTATS 2025.\n\n\n> __Q3:__ While theory is strong, there is no discussion of computational costs for Hessian-vector products or clipping in large-scale models.\n\n__A3:__ Thank you for your comment! The computational costs for Hessian-vector products is almost the same as the costs for gradients, refer to e.g., to (Pearlmutter, 1994). The idea is that let us imagine we have a backpropagation procedure for computing the gradient of $f(x)$. After this procedure we get $\\nabla f(x)$. To compute Hessian-vector product $\\nabla^2 f(x) v$ we need to construct a function $\\langle \\nabla f(x), v\\rangle$, and compute the gradient of the new function with respect to $x$ via backpropagation Therefore, we obtain the desired Hessian-vector $\\nabla^2 f(x) v$. Thus, the computational cost is $\\mathcal O(d)$. \n\n Pearlmutter, Barak A. \"Fast exact multiplication by the Hessian.\" Neural computation 6, no. 1 (1994): 147-160."}]

Author rebuttal:

Meta-review: The paper is an analysis of second-order stochastic optimization under the assumptions of heavy tailed stochastic gradients and hessians: it proposes a normalized SGD algorithms that achieves the established lower bounds on the sample complexity, and a novel gradient and Hessian clipping strategy to cope with large deviation instabilities, also achieving nearly-optimal performances. The main novelty of the paper consists in a sound and rigorous theoretical analysis of this relevant set-up, which has been appreciated for its clarity and originality. I recommend however the authors to integrate the text with the numerical experiments discussed with the Reviewers, as one of the weaknesses pointed out has been in fact the minimal experimental validation. Nevertheless, the relevance of the topic — essential for the construction of more realistic theoretical setup and more effective algorithmic solutions — makes the paper a valid and impactful contribution, and therefore I lean towards its acceptance.
Decision: Accept (poster)