Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
arXiv:2607.27073v1 [cs.LG] 29 Jul 2026
Vaneet Aggarwal∗
Abstract We study online convex optimization (OCO) in non-stationary environments under heavytailed noise, where the stochastic gradient oracle admits only a finite p-th central moment for some p ∈ (1, 2]. While static regret is well-understood, achieving universal dynamic regret in a parameter-free manner remains an open challenge. We resolve this by proposing HTPAder, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths with a pathwise meta-algorithm, AdaGrad-Hedge, which requires no moment conditions on meta-losses. For a domain of diameter D, Lipschitz constant G, noise level σ, and comparator path length PT , HT-PAder achieves an expected universal dynamic regret of p e GD T (1 + PT /D) + σDT 1/p (1 + PT /D)(p−1)/p . O The algorithm does not require prior knowledge of any of these problem parameters. Even in the special case of finite variance (p = 2), HT-PAder provides the first parameter-free minimax universal dynamic regret guarantee. We also prove a matching lower bound, establishing the optimality of the path-length exponent.
1
Introduction
Online Convex Optimization (OCO) is a foundational framework for sequential decision-making under uncertainty [Zinkevich, 2003, Hazan, 2016, Shalev-Shwartz, 2012, Pedramfar and Aggarwal, 2026]. In the standard formulation, a learner interacts with an environment over T rounds: at each round t, the learner selects a decision xt from a convex feasible set X ⊆ Rd with diameter D, the environment reveals a G-Lipschitz convex loss function ℓt : X → R, and the learner incurs loss ℓt (xt ). The classical performance measure is static regret, which compares the learner’s cumulative loss against the best fixed decision in hindsight. Under the standard bounded-domain assumption, √ Online Gradient Descent (OGD) achieves O(GD T ) static regret for G-Lipschitz losses, and this rate is minimax optimal. In non-stationary environments, however, static regret is insufficient. The appropriate measure is universal dynamic regret, defined as D-RegretT (u1 , . . . , uT ) =
T X
ℓt (xt ) −
t=1
T X
ℓt (ut ),
(1)
t=1
which compares against an arbitrary comparator sequence u1 , . . . , uT ∈ X . The difficulty of the problem is captured by the path length PT =
T X
∥ut − ut−1 ∥ ,
t=2 ∗
V. Aggarwal is with Purdue University, West Lafayette IN 47907, USA, email: [email protected]
1
(2)
which measures the non-stationarity of the environment. Zhang et al. [2018] established the minp imax optimal rate O(GD T (1 + PT /D)) for convex functions, resolving a gap left by the earlier √ O(GD T (1 + PT /D)) bound of Zinkevich [2003]. In parallel, a growing body of work has highlighted that the standard finite-variance assumption on stochastic gradients is often violated in practice. Empirical studies in deep learning [Simsekli et al., 2019] and finance [Mandelbrot, 2013] suggest that stochastic gradients frequently exhibit heavy tails, admitting only a finite p-th central moment bounded by σ p for some tail index p ∈ (1, 2] and noise level σ. Under this weaker condition, the classical analysis of OGD breaks down: the standard proof requires E[∥gt ∥2 ] < ∞, which may be infinite when p < 2. Indeed, Zhang et al. [2020] showed that SGD can provably diverge under heavy-tailed noise. Liu [2026] recently resolved this√tension for static regret, showing that OGD, DA, and AdaGrad all achieve the optimal rate O(GD T + σDT 1/p ) under heavy-tailed noise without any algorithmic modification, provided the domain is bounded. The key insight is a tighter one-step inequality, Lemma 2 below, that leverages the bounded-domain assumption to control the noise term via Young’s inequality, producing a term ∥ϵt ∥p with the correct exponent p rather than ∥ϵt ∥2 . Importantly, the AdaGrad result of Liu [2026] is parameter-free: it does not require knowledge of G, σ, or p. Our contribution. We extend the static regret result of Liu [2026] to the universal dynamic regret setting, and we do so in a parameter-free way. This extension is non-trivial because the existing algorithms for dynamic regret, namely, the Improved Ader algorithm of Zhang et al. [2018] and the Sword and Sword++ algorithms of Zhao et al. [2024], rely on exponential-weights metaalgorithms such as Hedge or Optimistic Hedge whose regret analysis requires E[∥ℓt ∥2 ] < ∞. Under heavy-tailed noise, this condition fails. Our solution has two key components. (1) A pathwise meta-algorithm. We use a meta-algorithm, AdaGrad-Hedge, given in Algorithm 1, whose regret bound holds deterministically for any realization of the meta-loss vectors, regardless of their distribution. This pathwise property is the key technical enabler that allows the meta-algorithm to interface with heavy-tailed gradient oracles. The update itself is an AdaGrad-FTRL and Hedge instantiation; our contribution is not the meta-algorithm in isolation, but rather its pathwise coupling with restarted AdaGrad experts under heavy-tailed noise. (2) Restarted AdaGrad experts. To obtain parameter-freeness, we replace the fixed-step OGD experts used in the known-G Improved Ader approach with AdaGrad experts that restart over blocks. A geometric pool of block lengths allows the algorithm to adapt to the unknown path length PT , while AdaGrad adapts to the unknown gradient scale. The main technical challenge is that AdaGrad has a variable stepsize, which introduces correction terms in the dynamicregret telescoping. We show that restarting localizes these correction terms and yields a clean pathwise block dynamic-regret bound. For comparison and to motivate our parameter-free construction, we also present a simpler known-G precursor algorithm, HT-IA, in Appendix A, which serves as an important pedagogical stepping stone before removing the dependence on the Lipschitz constant G. Under the problem setup described in Section 3, our parameter-free algorithm HT-PAder guarantees universal dynamic regret ! r p−1 p P P 1/p e GD T 1 + T + σDT E[D-RegretT ] = O 1 + DT . (3) D 2
p The bound has a natural decomposition into a deterministic term GD T (1 + PT /D), matching (p−1)/p . The noise term exhibits the minimax rate when σ = 0, and a noise term σDT 1/p 1 + PDT an interesting tradeoff: for p = 2, it matches the standard finite-variance √ rate. For p < 2, the exponent (p − 1)/p < 1/2 means the dependence on PT is weaker than PT , reflecting the fact that heavy-tailed noise makes it harder to track rapidly changing comparators. Our lower bound shows that this exponent is optimal. To establish the fundamental limits of online learning under heavy-tailed noise, we investigate information-theoretic lower bounds for universal dynamic regret. A key question is whether the noise-path tradeoff exponent (p − 1)/p is tight, or merely an artifact of our analysis. We resolve p−1
this by proving a matching expected dynamic regret lower bound of Ω σD1/p T 1/p PT p
for any
randomized online algorithm in the stochastic first-order oracle model. This lower bound matches the noise-dependence term in our upper bound up to polylogarithmic factors, demonstrating that the exponent (p − 1)/p is indeed optimal and cannot be improved by any algorithm. Our proof constructs a novel multi-block adversarial environment where heavy-tailed gradient noise is strategically calibrated to maximize the learner’s estimation error, establishing the result through a bespoke variational reduction to joint total variation distance over the block transcripts. This confirms that tracking rapidly changing comparators under heavy tails is fundamentally harder, with a limit strictly dictated by the tail index p. An important byproduct of our heavy-tail analysis is a new finite-variance result. When p = 2, HT-PAder gives s ! P T e (G + σ)D T 1 + E[D-RegretT ] = O , (4) D without knowing G, σ, or PT . To our knowledge, this is the first parameter-free minimax universal dynamic regret guarantee for standard finite-variance OCO. This resolves a practical limitation of Improved Ader [Zhang et al., 2018], which requires knowledge of G to construct its stepsize pool.
2
Related Work
Dynamic regret minimization. The √ study of dynamic regret dates back to Zinkevich [2003], who showed that OGD achieves O(GD p T (1 + PT /D)) dynamic regret. Zhang et al. [2018] closed the gap to the minimax rate O(GD T (1 + PT /D)) by proposing the Improved Ader algorithm, which maintains a pool of OGD experts with different stepsizes and uses a meta-algorithm to track the best one. Subsequently, Zhao et al. [2020, 2024] showed that for smooth functions, the dependence on T can be replaced by the gradient variation. All of these results assume either deterministic gradients or finite-variance stochastic gradients. Heavy-tailed stochastic optimization. The study of optimization under heavy-tailed noise has a long history in stochastic approximation [Nemirovski and Yudin, 1983]. For stochastic convex optimization, Vural et al. [2022] and Liu and Zhou [2024] established convergence rates for stochastic 1−1/p are suboptimal because they mirror descent under √ heavy tails, though their rates (G + σ)D/T do not recover GD/ T when σ = 0. For non-convex optimization, Liu et al. [2024] established highprobability bounds using gradient clipping, and Liu and Zhou [2025] showed optimal convergence without clipping. In the OCO setting, Zhang and Cutkosky [2022] established parameter-free regret bounds in high probability under heavy tails, but their algorithm requires gradient clipping and √ 1/p their bound (G + σ)DT does not recover the optimal GD T rate when σ = 0. 3
OGD and AdaGrad under heavy tails. The most directly relevant work who √ is Liu [2026], 1/p showed that OGD, DA, and AdaGrad achieve the optimal static regret O(GD T + σDT ) under heavy-tailed noise without any algorithmic modification. Their key technical contribution is a onestep inequality, our Lemma 2, that leverages the bounded-domain assumption to produce a ∥ϵt ∥p term rather than ∥ϵt ∥2 . They also showed that AdaGrad is parameter-free for static regret under heavy tails. Our work extends their static regret result to the universal dynamic regret setting, and retains parameter-freeness. Parameter-free and adaptive methods. AdaGrad [Duchi et al., 2011] is a classical parameterfree method for OCO in the sense that its stepsize adapts to the observed gradient norms. Liu’s static heavy-tail result shows that AdaGrad’s parameter-freeness survives heavy-tailed noise. Our contribution is to show that parameter-freeness can also be retained for universal dynamic regret under heavy tails, by combining restarted AdaGrad experts with a pathwise meta-algorithm. Online distributed optimization under heavy tails. Yang et al. [2025] studied online distributed optimization under heavy-tailed noise, establishing high-probability dynamic regret bounds using gradient clipping. Their setting is distributed and their algorithm requires clipping, in contrast to our centralized setting without clipping. Their rate is for worst-case dynamic regret, whereas our result is for universal dynamic regret. Comparison with existing results. and existing work.
3
Table 1 summarizes the comparison between our result
Problem Setup
We consider a nonempty, closed, convex decision set X ⊂ Rd with bounded diameter D = sup ∥x − y∥ < ∞.
(5)
x,y∈X
At each round t ∈ [T ], the environment reveals a convex and G-Lipschitz loss function ℓt : X → R, satisfying ∥∇ℓt (x)∥ ≤ G, ∀x ∈ X . (6) Upon playing a decision xt ∈ X , the learner queries a stochastic gradient oracle to receive an estimate gt ∈ Rd . We assume the stochastic gradient estimate is unbiased: E[gt | Ft−1 ] = ∇ℓt (xt ),
(7)
where Ft = σ(g1 , . . . , gt ) is the natural filtration. To model heavy-tailed noise, we assume that the conditional p-th central moment of the gradient noise ϵt = gt − ∇ℓt (xt ) is bounded: E[∥ϵt ∥p | Ft−1 ] ≤ σ p ,
(8)
for some tail index p ∈ (1, 2] and noise level σ ≥ 0. Under this condition, standard OCO algorithms can diverge due to the lack of finite variance when p < 2 [Zhang et al., 2020]. The special case 4
Table 1: Comparison of regret guarantees under stochastic gradients in OCO. Noise type: F = finite-variance noise, H = heavy-tailed noise. Clip-free indicates that no gradient clipping is required. PF indicates that the algorithm does not require prior knowledge of the problem constants G, σ, p, or the path-length budget PT ; unless otherwise noted, the horizon T is assumed known and can typically be removed by standard doubling with logarithmic factors. Regret type: S = static P regret, D = universal dynamic regret against an T arbitrary comparator sequence u1:T with path length PT = t=2 ∥ut −ut−1 ∥, and DW = worst-case dynamic PT ⋆ regret against the per-round minimizer sequence xt with path length CT = t=2 ∥x⋆t − x⋆t−1 ∥. Rates are in e hides logarithmic factors. expectation unless marked with †, which denotes a high-probability guarantee. O To our knowledge, the rows labeled “This work” give the first universal dynamic regret guarantees under heavy-tailed noise without gradient clipping; HT-PAder additionally removes knowledge of G. Reference
Noise
Clip-free
PF
Regret
Zhang et al. [2018]
F
✓
×
D
Zhao et al. [2024]
F
✓
×
D
†
H
×
×
DW
Zhang and Cutkosky [2022]†,∗
H
×
×
S
Liu [2026], AdaGrad
H
✓
✓
S
This work, known G
H
✓
×
D
This work, HT-PAder‡
H
✓
✓
D
Yang et al. [2025]
Expected regret q O GD T 1 + PDT p (1 + PT + VT )(1 + PT ) O 1+p e T 2p (CT + log T ) O 1/p e O (G√+ σ)DT O GD T + σDT 1/p q p−1 e GD T 1 + PT + σDT 1/p 1 + PT p O D D q p−1 e GD T 1 + PT + σDT 1/p 1 + PT p O D D
†
High-probability guarantee. Parameter-free in the comparator-norm sense used for unbounded domains, but not parameter-free with respect to G, σ, p, T under the definition used in this table. ‡ Assumes known horizon T and diameter D; the horizon dependence can be removed by standard doubling, e The algorithm does not require G, σ, p, or PT . with logarithmic factors hidden in O. ∗
p = 2 recovers the classical finite-variance setting. Crucially, the bounded-domain assumption is essential; as shown by Liu [2026], online gradient descent can diverge under heavy-tailed noise if the domain is unbounded. The learner’s performance is measured by universal dynamic regret against an arbitrary comparator sequence u1 , . . . , uT ∈ X : D-RegretT (u1 , . . . , uT ) =
T X
ℓt (xt ) −
t=1
T X
ℓt (ut ).
(9)
t=1
The non-stationarity of the environment is captured by the path length PT =
T X
∥ut − ut−1 ∥.
(10)
t=2
We aim to establish dynamic regret bounds that hold universally for all comparator sequences without prior knowledge of PT , G, σ, or p.
4
Key Technical Tools
4.1
Linearization of Expected Regret
The following simple lemma is used repeatedly. It makes explicit the standard reduction from convex regret to linearized regret under unbiased stochastic gradients. 5
Lemma 1 (Linearization). Let u1 , . . . , uT ∈ X be a fixed comparator sequence. Let xt be Ft−1 measurable. Under the setup described in Section 3, " T # X E[D-RegretT ] ≤ E ⟨gt , xt − ut ⟩ . (11) t=1
Proof. By convexity, ℓt (xt ) − ℓt (ut ) ≤ ⟨∇ℓt (xt ), xt − ut ⟩ . Taking conditional expectations and using unbiasedness, E[⟨gt , xt − ut ⟩ | Ft−1 ] = ⟨E[gt | Ft−1 ], xt − ut ⟩ = ⟨∇ℓt (xt ), xt − ut ⟩ . Summing over t and taking expectations gives the result.
4.2
Liu [2026]’s One-Step Inequality
The following inequality, established by Liu [2026], is the foundation of the known-G analysis. It is a tighter alternative to the standard OGD inequality that produces a ∥ϵt ∥p term with the correct exponent rather than ∥ϵt ∥2 . Lemma 2 (Liu [2026]). Under the setup described in Section 3, for OGD with fixed stepsize η > 0, for any x ∈ X , ∥xt − x∥2 − ∥xt+1 − x∥2 + ηG2 + C(p) η p−1 ∥ϵt ∥p D2−p , 2η
⟨gt , xt − x⟩ ≤ where
C(p) =
(4p − 4)(p−1)/p . p
(12)
(13)
Proof. By the optimality condition of the projection xt+1 = ΠX (xt − ηgt ), for any x ∈ X , ∥xt − x∥2 − ∥xt+1 − x∥2 − ∥xt − xt+1 ∥2 . ⟨gt , xt+1 − x⟩ ≤ 2η Adding and subtracting ⟨gt , xt+1 − x⟩ gives ⟨gt , xt − x⟩ ≤
∥xt − x∥2 − ∥xt+1 − x∥2 ∥xt − xt+1 ∥2 + ⟨gt , xt − xt+1 ⟩ − . 2η 2η
Decompose gt = ∇ℓt (xt ) + ϵt . For the deterministic part, by Cauchy–Schwarz, AM-GM, and ∥∇ℓt (xt )∥ ≤ G, ⟨∇ℓt (xt ), xt − xt+1 ⟩ ≤ G ∥xt − xt+1 ∥ ≤ ηG2 +
∥xt − xt+1 ∥2 . 4η
For the noise part, by Cauchy–Schwarz and Young’s inequality, together with ∥xt − xt+1 ∥ ≤ D, ⟨ϵt , xt − xt+1 ⟩ ≤ ∥ϵt ∥ ∥xt − xt+1 ∥ ≤ C(p)η p−1 ∥ϵt ∥p D2−p +
∥xt − xt+1 ∥2 . 4η
Combining the two bounds, ⟨gt , xt − xt+1 ⟩ −
∥xt − xt+1 ∥2 ≤ ηG2 + C(p)η p−1 ∥ϵt ∥p D2−p . 2η
Plugging this into the previous display yields the claimed inequality. 6
4.3
Pathwise Dynamic Regret of Restarted AdaGrad
The following lemma is the core new technical ingredient enabling parameter-free dynamic regret. It shows that AdaGrad, when restarted inside blocks, has a pathwise dynamic-regret bound depending only on the local gradient norm and the comparator path length inside the block. Lemma 3 (Pathwise block dynamic regret of AdaGrad). √ Fix D > 0 and a block of length m. Run AdaGrad-Norm inside the block with parameter η = D/ 2, restarting at the beginning of the block. That is, with local potential t X Vt = ∥gs ∥2 , (14) s=1
and stepsize
η ηt = √ , Vt
(15)
xt+1 = ΠX (xt − ηt gt ),
(16)
the update is with the convention that if Vt = 0, the update is skipped. Let m X
∥gt ∥2 ,
(17)
∥ut − ut−1 ∥ .
(18)
VB = Vm =
t=1
and PB =
m X t=2
Then for any comparator sequence u1 , . . . , um ∈ X , m X
⟨gt , xt − ut ⟩ ≤ C
p VB (D + PB ),
(19)
t=1
√ where C > 0 is a universal constant. In particular, one may take C = 3 2/2. Proof. For any ut ∈ X , by nonexpansiveness of the projection, ∥xt+1 − ut ∥2 ≤ ∥xt − ηt gt − ut ∥2 . Expanding, ∥xt+1 − ut ∥2 ≤ ∥xt − ut ∥2 − 2ηt ⟨gt , xt − ut ⟩ + ηt2 ∥gt ∥2 . Rearranging, ⟨gt , xt − ut ⟩ ≤
∥xt − ut ∥2 − ∥xt+1 − ut ∥2 ηt ∥gt ∥2 + . 2ηt 2
Define
√ 1 Vt at := = . 2ηt 2η
Since Vt is nondecreasing, at is nondecreasing. Summing over t = 1, . . . , m, m X
⟨gt , xt − ut ⟩ ≤ T1 + T2 ,
t=1
7
(20)
where T1 :=
m X
at ∥xt − ut ∥2 −
m X
t=1
at ∥xt+1 − ut ∥2 ,
t=1
and T2 :=
m X ηt ∥gt ∥2 t=1
2
.
We first bound T1 . Separate the last term in the second sum: 2
T1 = a1 ∥x1 − u1 ∥ +
m X
at ∥xt − ut ∥2 − at−1 ∥xt − ut−1 ∥2
t=2
− am ∥xm+1 − um ∥2 . Dropping the final negative term, T1 ≤ a1 ∥x1 − u1 ∥2 +
m X
at ∥xt − ut ∥2 − at−1 ∥xt − ut−1 ∥2 .
t=2
For each t ≥ 2, write at ∥xt − ut ∥2 − at−1 ∥xt − ut−1 ∥2 = (at − at−1 ) ∥xt − ut−1 ∥2 + at ∥xt − ut ∥2 − ∥xt − ut−1 ∥2 . Because xt , ut , ut−1 ∈ X and diam(X ) = D, ∥xt − ut−1 ∥2 ≤ D2 . Also, ∥xt − ut ∥2 − ∥xt − ut−1 ∥2 = 2 ⟨xt − ut−1 , ut−1 − ut ⟩ + ∥ut − ut−1 ∥2 ≤ 2D ∥ut − ut−1 ∥ + ∥ut − ut−1 ∥2 ≤ 3D ∥ut − ut−1 ∥ , where the last step uses ∥ut − ut−1 ∥ ≤ D. Therefore, at ∥xt − ut ∥2 − at−1 ∥xt − ut−1 ∥2 ≤ (at − at−1 )D2 + 3Dat ∥ut − ut−1 ∥ . Summing over t = 2, . . . , m, m m X X 2 T1 ≤ a1 D + (at − at−1 )D + 3D at ∥ut − ut−1 ∥ . 2
t=2
t=2
The first two terms telescope: a1 D 2 +
m X (at − at−1 )D2 = am D2 . t=2
Thus T1 ≤ am D2 + 3D
m X t=2
8
at ∥ut − ut−1 ∥ .
Now substitute at =
√
Vt /(2η). Since Vt ≤ Vm = VB , am D 2 =
and 3Dat = √ Using η = D/ 2,
D2 p VB , 2η
3D p 3D p Vt ≤ VB . 2η 2η √ 3D 3 2 = . 2η 2
D2 D =√ , 2η 2 Hence
√ 3 2p Dp VB + VB PB . T1 ≤ √ 2 2 √ Next we bound T2 . Since ηt = η/ Vt , T2 =
m X ηt ∥gt ∥2
2
t=1
m
=
η X ∥gt ∥2 √ . 2 Vt t=1
Because Vt = Vt−1 + ∥gt ∥2 , we have p p Vt − Vt−1 ∥gt ∥2 √ √ = ≤ 2( Vt − Vt−1 ). Vt Vt Summing,
m X p p ∥gt ∥2 √ ≤ 2 Vm = 2 VB . Vt t=1
Therefore, T2 ≤ η
p Dp VB = √ VB . 2
Combining the bounds for T1 and T2 , m X
⟨gt , xt − ut ⟩ ≤
t=1 √
Since 3 2 2 ≥
√
√
√ p 3 2p 2 D VB + V B PB . 2
2, this implies m X t=1
√ 3 2p ⟨gt , xt − ut ⟩ ≤ VB (D + PB ). 2
This completes the proof. Remark 1 (Why restart?). Without restarting, AdaGrad’s variable stepsize produces global correction terms that are difficult to combine with comparator movement. In particular, the telescoping coefficient at time t depends on all gradients observed since the beginning of the run, P so a bound P over an interval [s, e] would depend on et=1 ∥gt ∥2 rather than the interval-local quantity et=s ∥gt ∥2 . Restarting resets the AdaGrad potential and √ localizes the correction terms to each block. The perblock initialization cost contributes the D VB term, which after summing over blocks becomes the DK term in the expert regret bound. 9
4.4
Moment Bounds
Lemma 4. Under the setup described in Section 3, for any interval B ⊆ [T ] of length |B|, !1/p X ≤ σ |B|1/p . E ∥ϵt ∥p
(21)
t∈B
Proof. By Jensen’s inequality, since x 7→ x1/p is concave for p ≥ 1, !1/p " #!1/p X X ≤ E E ∥ϵt ∥p ∥ϵt ∥p ≤ (σ p |B|)1/p = σ |B|1/p . t∈B
t∈B
The following lemma is used repeatedly. Lemma 5. Under the setup described in Section 3, for any interval B ⊆ [T ] of length |B|, sX p E ∥gt ∥2 ≤ G |B| + σ |B|1/p .
(22)
t∈B
Proof. We apply Minkowski’s inequality in ℓ2 (R|B| ) followed by the monotonicity of ℓq -norms: sX ∥gt ∥2 = ∥(∥gt ∥)t∈B ∥ℓ2 t∈B
= ∥(∥∇ℓt (xt ) + ϵt ∥)t∈B ∥ℓ2 ≤ ∥(∥∇ℓt (xt )∥)t∈B ∥ℓ2 + ∥(∥ϵt ∥)t∈B ∥ℓ2 sX G2 + ∥(∥ϵt ∥)t∈B ∥ℓp ≤ t∈B
!1/p p = G |B| +
X
∥ϵt ∥p
.
t∈B
Taking expectations and applying Lemma 4 yields the result.
4.5
AdaGrad-Hedge: A Pathwise Meta-Algorithm
We now describe the pathwise meta-algorithm used to combine multiple experts. The pseudocode is given in Algorithm 1. Algorithm 1 maintains a probability distribution wt over M experts. At each round, it receives a meta-loss vector mt ∈ RM . Instead of using a fixed learning rate as in standard Hedge, it adapts the learning rate according to the accumulated magnitude of the observed meta-losses. The cumulative scale variable Wt in (23) tracks the squared ℓ∞ norm of all past meta-loss vectors. The adaptive learning rate εt in (24) decreases as Wt grows. The weight update in (25) is an exponential-weights update applied to the cumulatively scaled losses. Because the regret bound in Lemma 6 depends on WT pathwise, no moment assumption on mt is required. This property is essential for compatibility with heavy-tailed stochastic gradients. 10
Algorithm 1 AdaGrad-Hedge: Pathwise Meta-Algorithm Require: Number of experts M , parameter a ≥ ln M + 1 1: Initialize weights uniformly: w1,i = 1/M for all i ∈ [M ]. 2: Initialize cumulative scale: W0 = 1. 3: for t = 1, 2, . . . do 4: Output the current weight vector wt . 5: Receive meta-loss vector mt ∈ RM . 6: Update cumulative scale: Wt = Wt−1 + ∥mt ∥2∞ . 7:
Set adaptive learning rate: r εt =
8:
a . Wt
For each expert i ∈ [M ], update wt+1,i ∝ exp −εt
t X
! ms,i
.
s=1
9: end for
Lemma 6 (AdaGrad-Hedge). Let m1 , . . . , mT ∈ RM be any sequence of loss vectors, with no distributional assumptions. Let wt be generated by Algorithm 1. Define Wt = 1 +
t X
∥ms ∥2∞ ,
(23)
a . Wt
(24)
s=1
let a ≥ ln M + 1, and set r εt = The weights satisfy t X
wt+1,i ∝ exp −εt
! ms,i
,
∀ i ∈ [M ].
(25)
s=1
Then for any expert i ∈ [M ], T X
⟨wt , mt ⟩ −
T X
t=1
p mt,i ≤ 3 a WT .
t=1
Proof. This is FTRL with shifted negative entropy ϕ(w) =
M X
wi ln wi + ln M,
i=1
which is 1-strongly convex with respect to ∥·∥1 on the simplex. The update is equivalently ( ) t X wt+1 = arg min εt ⟨w, ms ⟩ + ϕ(w) . w∈∆M
s=1
11
(26)
By the standard AdaGrad-FTRL inequality [Orabona, 2019, Theorem 7.35], for any q ∈ ∆M , T X
⟨wt , mt ⟩ −
t=1
T X
T
⟨q, mt ⟩ ≤
ϕ(q) X + εt ∥mt ∥2∞ . εT
(27)
t=1
t=1
Taking q = ei , we have ϕ(ei ) = ln M ≤ a. Since εT =
p a/WT ,
p ϕ(ei ) a ≤p = aWT . εT a/WT Also, T X
√ εt ∥mt ∥2∞ = a
t=1
For at ≥ at−1 ≥ 0,
T X Wt − Wt−1 √ . Wt t=1
√ at − at−1 √ ≤ 2( at − at−1 ). √ at
Therefore, T X p Wt − Wt−1 √ ≤ 2 WT . Wt t=1
Hence
T X
p εt ∥mt ∥2∞ ≤ 2 aWT .
t=1
Combining the two terms in (27) gives T X t=1
⟨wt , mt ⟩ −
T X
p mt,i ≤ 3 aWT .
t=1
Remark 2 (Why standard Hedge fails under heavy tails). Standard Hedge with fixed learning rate ε gives meta-regret X ln M ≤ +ε ∥mt ∥2∞ . ε t Taking expectations requires E[∥mt ∥2∞ ] < ∞. In our setting, √ ∥mt ∥∞ ≤ D ∥gt ∥, and E[∥gt ∥2 ] may be infinite when p < 2. AdaGrad-Hedge avoids this by bounding WT pathwise and taking expectations only at the final step, where Lemma 5 applies. Remark 3 (Novelty of AdaGrad-Hedge). The AdaGrad-Hedge update is an AdaGrad-FTRL/Hedge instantiation, related to known parameter-free potentials. The novelty of this paper is not the metaalgorithm in isolation, but rather: (i) the pathwise refined form used here; (ii) its coupling with restarted AdaGrad experts; and (iii) the resulting parameter-free universal dynamic regret guarantee under heavy-tailed noise.
12
5
Parameter-Free Algorithm
We now present the main parameter-free algorithm, HT-PAder. It uses AdaGrad-Hedge from Algorithm 1 as its meta-algorithm and restarted AdaGrad experts as base learners. Algorithm 2 HT-PAder: Parameter-Free Heavy-Tailed Dynamic Regret Require: Horizon T , domain X , diameter D 1: Let N = ⌈log2 T ⌉ and M = N + 1. 2: for i = 0, . . . , N do 3: Define Ki = 2i ∧ T and Li = ⌈T /Ki ⌉. 4: Activate expert Ei : restarted AdaGrad with block length Li . 5: end for 6: Initialize AdaGrad-Hedge, Algorithm 1, with M experts and parameter a = ln M + 2. 7: for t = 1, . . . , T do (i) 8: Receive xt from each expert Ei . 9: Using the current AdaGrad-Hedge weights wt , play xt =
N X
(i)
wt,i xt .
i=0
10: 11:
Observe stochastic gradient gt . Define meta-loss vector D E (i) mt,i = gt , xt − xt ,
i = 0, . . . , N.
Update the meta-weights from wt to wt+1 using AdaGrad-Hedge, Algorithm 1, with meta-loss mt . 13: Send gt to each expert Ei . 14: end for 12:
The expert pool is indexed by i = 0, . . . , N . Expert Ei is associated with a number of blocks Ki and block length Li given by T i Ki = 2 ∧ T, Li = . (28) Ki Expert Ei partitions [T ] into consecutive blocks of length Li . At the beginning of each block, it resets its iterate to a fixed point x0 ∈ X and resets its local AdaGrad potential to zero. Inside a block starting at round s, it maintains (i)
t X
∥gr ∥2 ,
(29)
D (i) . ηt = q (i) 2Vt
(30)
(i) (i) (i) xt+1 = ΠX xt − ηt gt ,
(31)
Vt
=
r=s
and uses the stepsize
The expert update is
13
(i)
with the convention that the update is skipped if Vt = 0. At round t, the algorithm combines expert predictions according to xt =
N X
(i)
wt,i xt ,
(32)
i=0
where wt is produced by AdaGrad-Hedge. The meta-loss assigned to expert i is D E (i) mt,i = gt , xt − xt .
(33)
This choice ensures that the weighted average meta-loss is zero: * + N N X X (i) wt,i mt,i = gt , wt,i xt − xt = 0. i=0
i=0
Thus, AdaGrad-Hedge competes against each expert using the relative loss of that expert compared with the algorithm’s current mixture. Remark 4 (Parameter-free). Algorithm 2 uses only D and T . It does not require knowledge of G, σ, p, or PT . If T is unknown, a standard doubling trick can be applied, adding only logarithmic factors.
6
Main Result
Theorem 1 (Parameter-Free Dynamic Regret under Heavy-Tailed Noise). Under the setup described in Section 3, Algorithm 2 guarantees, for any comparator sequence u1 , . . . , uT ∈ X , r p p−1 √ p PT PT 1/p 1+ D + D 1 + G T + σT 1/p log log T . E[D-RegretT ] ≲ GD T 1 + D + σD T (34) Equivalently, ! r p−1 p P P 1/p e GD T 1 + T + σDT 1 + DT E[D-RegretT ] = O . D Corollary 1 (Finite-variance byproduct: double adaptivity). For p = 2, Theorem 1 gives s ! P e (G + σ)D T 1 + T E[D-RegretT ] = O . D
(35)
(36)
To our knowledge, this is the first parameter-free minimax universal dynamic regret guarantee for standard finite-variance OCO. Remark 5 (Special cases). • PT = 0 static comparator: recovers the static rate of Liu [2026], √ e matching O(GD T + σDT 1/p ). • σ = 0p deterministic gradients: recovers the minimax rate of Zhang et al. [2018], matching O(GD T (1 + PT /D)). The rest of this section proves Theorem 1. The matching lower bound is studied in Appendix B. The proof consists of five main steps: 14
(i) establishing the meta-expert decomposition to separate the meta-regret and the expert regret; (ii) bounding the meta-regret using the pathwise AdaGrad-Hedge guarantee; (iii) bounding the expert regret of a restarted AdaGrad expert for a fixed block length; (iv) selecting a near-optimal block-length expert from the geometric pool; and (v) combining the meta-regret and expert regret bounds. Step 1: Meta-Expert Decomposition.
By Lemma 1, specifically (11), " T # X E[D-RegretT ] ≤ E ⟨gt , xt − ut ⟩ . t=1
For any expert index i ∈ {0, . . . , N }, T X
⟨gt , xt − ut ⟩ =
t=1
T D X
(i) gt , xt − xt
E
T D X
+
(i)
gt , xt − ut
E
.
(37)
t=1
t=1
|
{z
}
meta-regret relative to i
|
{z
}
expert linear regret for i
Step 2: Bounding the Meta-Regret.
Recall the meta-loss vector from (33): D E (i) mt,i = gt , xt − xt .
Since xt =
(i) i wt,i xt , we have
P
N X
* wt,i mt,i =
+
gt ,
X
i=0
(i) wt,i xt − xt
= 0.
i
Therefore, D
(i) gt , xt − xt
E
=
N X
wt,j mt,j − mt,i .
(38)
E
(39)
j=0
By Lemma 6, specifically (26), pathwise, T D X
(i)
gt , xt − xt
p ≤ 3 aWT .
t=1
Now, D E (i) ∥mt ∥∞ = max | gt , xt − xt | ≤ D∥gt ∥, i
so WT = 1 +
T X
∥mt ∥2∞ ≤ 1 + D2
t=1
T X
∥gt ∥2 .
(40)
t=1
Thus, v u T uX p ∥gt ∥2 . WT ≤ 1 + D t t=1
15
(41)
Therefore, from (39) and (41), v u T u X √ meta-regret ≤ 3D a 1 + t ∥gt ∥2 .
t=1
Taking expectations and applying Lemma 5, specifically (22), √ √ E[meta-regret] ≤ 3D a (1 + G T + σT 1/p ). Since M = O(log T ) and a = ln M + 2 = O(log log T ), we obtain p √ E[meta-regret] ≲ D(1 + G T + σT 1/p ) log log T .
(42)
Step 3: Bounding the Expert Regret for a Fixed Block Length. We first record the expected regret bound for a restarted AdaGrad expert with a fixed block length. Lemma 7 (Expected √ expert regret for fixed block length). Fix a block length L. Run AdaGrad with parameter η = D/ 2, restarting every L rounds. For any fixed comparator sequence u1 , . . . , uT ∈ X with path length PT , " T # X √ T 1/p E ⟨gt , xt − ut ⟩ ≲ (G L + σL ) D + PT . (43) L t=1
Proof. Partition [T ] into K = ⌈T /L⌉ blocks B1 , . . . , BK , each of length at most L. For block Bb , define X X Vb = ∥gt ∥2 , Pb = ∥ut − ut−1 ∥ . (44) t∈Bb
t∈Bb t≥2
The quantity Pb counts only comparator movement internal to block Bb . Comparator movement across √ block boundaries is deliberately excluded: its effect is absorbed by the per-block restart cost D Vb , which after summing over blocks yields the DK term. By Lemma 3, specifically (19), pathwise, X p ⟨gt , xt − ut ⟩ ≤ C Vb (D + Pb ). (45) t∈Bb
Taking expectations and applying Lemma 5 to block Bb , p p √ E[ Vb ] ≤ G |Bb | + σ|Bb |1/p ≤ G L + σL1/p . Hence
E
(46)
X
√ ⟨gt , xt − ut ⟩ ≲ (G L + σL1/p )(D + Pb ).
t∈Bb
Summing over blocks, E
" T X
K X √ ⟨gt , xt − ut ⟩ ≲ (G L + σL1/p ) DK + Pb
#
t=1
Since
b=1
P
b Pb ≤ PT and K = ⌈T /L⌉, (47) implies (43).
16
! .
(47)
Step 4: Choosing the Right Block-Length Expert. K⋆ = 1 +
Define
PT . D
(48)
Since any comparator sequence in X satisfies PT ≤ D(T − 1), we have K ⋆ ≤ T . The expert pool contains experts with Ki = 2i ∧ T , for i = 0, . . . , N . Therefore, there exists an index i⋆ such that Ki⋆ ∈ [K ⋆ , 2K ⋆ ].
(49)
The corresponding block length is T . Li⋆ = Ki⋆
Since Ki⋆ ≥ K ⋆ , we have
T 2T + 1 ≤ ⋆. K⋆ K By Lemma 7, specifically (43), the expected linear regret of expert i⋆ satisfies Li⋆ ≤
E[expert regret for i⋆ ] ≲ (G
p 1/p Li⋆ + σLi⋆ )(DKi⋆ + PT ).
(50)
Using Ki⋆ ≤ 2K ⋆ , PT = D(K ⋆ − 1) ≤ DK ⋆ , and Li⋆ ≤ 2T /K ⋆ , we have DKi⋆ + PT ≲ DK ⋆ , and
r p T 1/p T 1/p G Li⋆ + σLi⋆ ≲ G +σ . K⋆ K⋆
Therefore, (50) gives r ⋆
E[expert regret for i ] ≲ DK Simplifying,
⋆
G
T +σ K⋆
T K⋆
1/p ! .
√ E[expert regret for i⋆ ] ≲ GD T K ⋆ + σDT 1/p (K ⋆ )1−1/p .
Substituting K ⋆ = 1 + PT /D from (48), we obtain s ⋆
E[expert regret for i ] ≲ GD
T
PT 1+ D
+ σDT
1/p
PT 1+ D
p−1 p
.
(51)
Step 5: Combining. From the decomposition (37), the meta-regret bound (42), and the expertregret bound (51), s p−1 p √ p PT PT 1/p E[D-RegretT ] ≲ GD T 1 + +σDT 1+ +D(1+G T +σT 1/p ) log log T . (52) D D This completes the proof of Theorem 1.
17
7
Conclusion
We showed that parameter-free universal dynamic regret is achievable for online convex optimization under heavy-tailed noise without gradient clipping. The key idea is to combine restarted AdaGrad experts with the pathwise AdaGrad-Hedge meta-algorithm from Algorithm 1. The resulting rate recovers the minimax deterministic dynamic regret rate, the optimal static rate of Liu [2026], and, as a byproduct, gives the first parameter-free minimax universal dynamic regret guarantee for finite-variance OCO.
A
Known-G Precursor: HT-IA
For comparison, we record here the simpler known-G precursor algorithm, HT-IA. This algorithm is useful because it isolates the role of the heavy-tail-compatible meta-algorithm from the additional parameter-free difficulty of not knowing G. The design of HT-IA is as follows. Since G is known, one can construct a geometric pool of fixed-step OGD experts whose stepsizes cover the natural optimal scale balancing the deterministic and noise terms. Expert i uses stepsize ηi from (53) below and updates by projected stochastic gradient descent as in (55). The meta-algorithm is exactly AdaGrad-Hedge from Algorithm 1. At each round, AdaGrad-Hedge assigns larger weight to experts whose fixed stepsize has performed well so far. Because the meta-regret bound of Lemma 6 is pathwise, the same heavy-tailed gradient oracle can be handled without assuming finite variance of the meta-losses. The key distinction from HT-PAder is that HT-IA’s expert stepsizes depend explicitly on G. Therefore, HT-IA is not parameter-free. HT-PAder removes this dependence by replacing fixedstep OGD experts with restarted AdaGrad experts and using a geometric pool of block lengths instead of stepsizes.
18
Algorithm 3 HT-IA: Heavy-Tailed Improved Ader, requires G Require: Horizon T , domain X , diameter D, Lipschitz constant G 1: Let r D2 ηi = 2i−1 , i = 1, . . . , N, 8G2 T where 2 8G T 1 + 1. log2 N= 2 D2 2: Activate fixed-step OGD experts Ei with stepsize ηi : (i)
(i)
xt+1 = ΠX (xt − ηi gt ). 3: Initialize AdaGrad-Hedge, Algorithm 1, with M = N experts and parameter a = ln N + 2. 4: for t = 1, . . . , T do 5: 6:
(i)
Receive xt from each expert Ei . Using the current AdaGrad-Hedge weights wt , play xt =
N X
(i)
wt,i xt .
i=1
7: 8:
Observe stochastic gradient gt . Define meta-loss vector
D E (i) mt,i = gt , xt − xt .
Update the meta-weights from wt to wt+1 using AdaGrad-Hedge, Algorithm 1, with meta-loss mt . 10: Send gt to each expert. 11: end for 9:
More explicitly, the stepsize pool is r i−1
ηi = 2
D2 , 8G2 T
i = 1, . . . , N,
(53)
with pool size
1 N= log2 2
8G2 T D2
+ 1.
(54)
Each expert Ei runs fixed-step OGD: (i)
(i)
xt+1 = ΠX (xt − ηi gt ).
(55)
The meta-level weight update is handled by Algorithm 1. Thus, HT-IA can be viewed as a heavytailed version of Improved Ader: it keeps the fixed-step expert pool of Improved Ader but replaces the usual finite-variance Hedge analysis with the pathwise AdaGrad-Hedge guarantee.
19
Theorem 2 (Known-G dynamic regret). Under the setup of Section 3, Algorithm 3 guarantees: s p−1 p √ p PT PT 1/p 1+ + σDT E[D-RegretT ] ≲p GD T 1 + + D(1 + G T + σT 1/p ) log log T . D D (56) Proof. By the meta-expert decomposition, as in (37), the expected dynamic regret of Algorithm 3 is bounded by E[D-RegretT ] ≤ E[meta-regret] + E[expert regret for ηi⋆ ], (57) where i⋆ is the index of the expert in the stepsize pool closest to the optimal stepsize. First, we bound the meta-regret. The meta-losses are D E (i) mt,i = gt , xt − xt .
(58)
Using Lemma 6, specifically (26), with WT = 1 +
T X
∥mt ∥2∞ ,
t=1
we have pathwise T D X
(i)
gt , xt − xt
E
p ≤ 3 aWT .
(59)
t=1
Using ∥mt ∥∞ ≤ D∥gt ∥, we obtain WT ≤ 1 + D 2
T X
∥gt ∥2 .
(60)
t=1
Taking expectations and applying Lemma 5 over the full horizon [T ] yields v u T u X √ E[meta-regret] ≤ 3D a 1 + E t ∥gt ∥2 t=1
√ √ ≤ 3D a 1 + G T + σT 1/p . Since N = O(log T ) and a = ln N + 2 = O(log log T ), we have p √ E[meta-regret] ≲ D(1 + G T + σT 1/p ) log log T .
(61)
Next, we bound the expert regret. For any fixed stepsize ηi from the expert pool, summing the one-step inequality (12) from Lemma 2 over t = 1, . . . , T with comparator ut yields T D X t=1
(i) (i) T T E X X ∥xt − ut ∥2 − ∥xt+1 − ut ∥2 (i) + ηi G2 T + C(p)ηip−1 D2−p ∥ϵt ∥p . gt , xt − ut ≤ 2ηi t=1
(62)
t=1
By standard moving-comparator telescoping, (i) (i) T X ∥xt − ut ∥2 − ∥xt+1 − ut ∥2 t=1
2ηi 20
≤
D2 + 2DPT . 2ηi
(63)
Taking expectations in (62) and using (8) gives " T # E XD D2 + 2DPT (i) + ηi G2 T + C(p)ηip−1 D2−p σ p T. E ≤ gt , xt − ut 2ηi
(64)
t=1
To optimize the stepsize, we apply Lemma 8 with A=
D2 + 2DPT , 2
B = G2 T,
C = C(p)D2−p σ p T.
(65)
This implies that the optimal stepsize η ⋆ satisfies √ A + Bη ⋆ + C(η ⋆ )p−1 ≲p AB + A(p−1)/p C 1/p . ⋆ η
(66)
Substituting the values of A, B, and C from (65), s √ PT AB = GD T 1 + , D and A
(p−1)/p
C
1/p
≤ σDT
1/p
p−1 p PT 1+ . D
The geometric stepsize pool constructed in (53)–(54) covers the relevant interval up to a factor of 2. Hence, there exists an expert stepsize ηi⋆ in the pool such that ηi⋆ ≤ η ⋆ ≤ 2ηi⋆ . This ensures that s p−1 p PT PT 1/p E[expert regret for ηi⋆ ] ≲p GD T 1 + + σDT 1+ . D D Combining (57), (61), and (67) completes the proof. Lemma 8 (Optimization lemma). For A, B, C > 0 and p ∈ (1, 2], √ A p−1 min + Bη + Cη ≲p AB + A(p−1)/p C 1/p . η>0 η p Proof. Set η1 = A/(2B) and η2 = (A/(2C))1/p . Let η ⋆ = η1 ∧ η2 . Case 1: η ⋆ = η1 ≤ η2 . Then √ A + Bη1 ≲ AB. η1 Also, η1 ≤ η2 implies C ≤ B p/2 (A/2)1−p/2 , and therefore Cη1p−1 ≤ B p/2 (A/2)1−p/2
21
A 2B
(p−1)/2
√ ≲
AB.
(67)
Case 2: η ⋆ = η2 ≤ η1 . Then A + Cη2p−1 ≲p A(p−1)/p C 1/p . η2 Also, using η2 ≤ η1 , Bη2 = B
A 2C
1/p
≤B
A 2B
1/2
√ ≲
AB.
Combining the cases proves the lemma.
B
Lower Bound
We now prove a lower bound matching the noise-path term in Theorem 1. Lemma 9 (Abstract block regret lower bound). Fix D, Z, δ, L > 0. For each hidden sign ν ∈ {−1, +1}, define the comparator (ν) ut = −Dν and the deterministic linear loss (ν)
ℓt (x) = µν x,
µν = 2Zδ ν.
Let TL be a measurable space of complete interaction transcripts over L rounds. For ν ∈ {−1, +1}, let PνL be a probability measure on TL . A transcript τ ∈ TL determines the learner’s decisions xt (τ ) ∈ [−D, D], t = 1, . . . , L. The measures P+L and P−L may arise from learner randomness, environmental randomness, or both; no further probabilistic structure is required. Define the expected block regret under environment ν by " L # X (ν) (ν) (ν) ℓt (xt (τ )) − ℓt (ut ) . Rν = Eτ ∼PνL t=1
Then R+ + R− ≥ 4DZδL 1 − TV(P+L , P−L ) . (ν)
Proof. For any transcript τ , since ℓt (x) = µν x, (ν)
(ν)
(ν)
(ν)
ℓt (xt (τ )) − ℓt (ut ) = µν (xt (τ ) − ut ). (ν)
Using ut
= −Dν and µν = 2Zδ ν, (ν)
µν (xt (τ ) − ut ) = 2Zδ ν(xt (τ ) + Dν) = 2Zδ(D + νxt (τ )). Thus the instantaneous regret under environment ν is (ν)
(ν)
(ν)
ℓt (xt (τ )) − ℓt (ut ) = 2Zδ(D + νxt (τ )).
22
(68)
Define the transcript functional L X F (τ ) := (D + xt (τ )). t=1
Because xt (τ ) ∈ [−D, D], we have F (τ ) ∈ [0, 2DL]. Under ν = +1, the instantaneous regret is 2Zδ(D + xt ), so R+ = 2Zδ E+ [F ]. Under ν = −1, the instantaneous regret is 2Zδ(D − xt ). Since D − xt = 2D − (D + xt ), we have
L X (D − xt ) = 2DL − F, t=1
and therefore R− = 2Zδ E− [2DL − F ] = 2Zδ (2DL − E− [F ]) . Thus R+ + R− = 2Zδ 2DL − E− [F ] − E+ [F ] . We now bound E− [F ] − E+ [F ] using total variation. Let A := 2DL. We use the layer-cake representation: Z 1 F = 1{F >As} ds. A 0 Hence E− [F ] − E+ [F ] = A
Z 1 (P− (F > As) − P+ (F > As)) ds. 0
For every s ∈ [0, 1], P− (F > As) − P+ (F > As) ≤ TV(P+L , P−L ). Therefore, E− [F ] − E+ [F ] ≤ A TV(P+L , P−L ) = 2DL TV(P+L , P−L ). Substituting, R+ + R− ≥ 4DZδL 1 − TV(P+L , P−L ) .
Theorem 3 (Lower bound for dynamic regret under heavy-tailed noise). Let X = [−D, D] with D > 0, let σ > 0, and let p ∈ (1, 2]. For every possibly randomized online algorithm in the stochastic first-order oracle model, every horizon T , and every feasible path-length budget satisfying 2D ≤ PT ≤ 2D(T − 1), there exist deterministic linear losses ℓt (x) = µt x, so that ∇ℓt (x) = µt
for all x ∈ X , 23
and a stochastic first-order oracle returning gradient estimates gt such that, for the natural filtration Ft = σ(g1 , . . . , gt ), E[gt | Ft−1 ] = ∇ℓt (xt ) = µt , and the conditional p-th central moment condition holds: E[|gt − µt |p | Ft−1 ] ≤ σ p . Moreover, there exists a comparator sequence u1 , . . . , uT ∈ X with path length at most PT such that p−1
E[D-RegretT ] ≥ cp σD1/p T 1/p PT p ,
(69)
where the expectation is over the stochastic first-order oracle and the learner’s internal randomness, and 41/p . (70) cp = 128 If PT > 2D(T − 1), the same statement holds with PT replaced by 2D(T − 1). Proof. Fix an arbitrary possibly randomized online algorithm. Its internal randomness is included in the transcript distributions below. Step 1: Blocking and padding. Define the capped path length P̄T := min{PT , 2D(T − 1)}. Set
P̄T K := + 1. 2D
Because P̄T ≤ 2D(T − 1), we have K ≤ T . Let T , L := K
T ′ := KL.
We use the first T ′ rounds for the construction and pad the remaining T − T ′ rounds with zero losses, zero gradients, and a constant comparator. The padding adds zero expected regret and does not increase the path length. Since K ≤ T , we have L ≥ 1 and T ′ ≥ T /2. Partition the first T ′ rounds into K consecutive blocks of length L. For t in block k, write b(t) := k. In block k, choose an independent hidden sign νk ∈ {−1, +1} uniformly at random. The comparator and mean gradient inside block k are ut = −Dνb(t) ,
µt = 2Zδ νb(t) .
The deterministic loss is ℓt (x) = µt x. For any realization of ν1 , . . . , νK , the path length satisfies ′
T X t=2
|ut − ut−1 | ≤
K X
| − Dνk + Dνk−1 | ≤ 2D(K − 1) ≤ P̄T ≤ PT .
k=2
Step 2: One-block heavy-tailed construction. Inside each block of length L, define the constants 1 1 σ q := , δ := , Z := (4L)1/p . (71) 4L 32L 2 24
Conditional on the hidden sign ν ∈ {−1, +1}, the stochastic first-order oracle returns a gradient estimate g distributed as Pν (g = νZ) =
q + δ, 2
Pν (g = −νZ) =
The mean gradient is µν = νZ
q − δ, 2
Pν (g = 0) = 1 − q.
q + δ + (−νZ) − δ = 2Zδ ν. 2 2
q
Thus, for t in block k, µt = µνk = 2Zδ νk . For a fixed deterministic sign sequence ν1 , . . . , νK , the gradient estimates are independent of the past inside each block, so E[gt | Ft−1 ] = µt = ∇ℓt (xt ). Step 3: Verification of the conditional p-th central moment condition. First, Eν |g|p = qZ p =
σ p 1 σ p (4L) = . 4L 2 2
Also, |µν | = 2Zδ = 2 ·
1 σ(4L)1/p σ (4L)1/p · = . 2 32L 32L
Since p ≥ 1 and L ≥ 1, (4L)1/p 41/p 1/p−1 4 1 = L ≤ = . 32L 32 32 8 Hence |µν | ≤ σ/8. By Minkowski’s inequality, (Eν |g − µν |p )1/p ≤ (Eν |g|p )1/p + |µν | ≤
5σ σ σ + = < σ. 2 8 8
Therefore, Eν |g − µν |p ≤ σ p . For a fixed deterministic sign sequence, the same bound holds conditionally on Ft−1 . Hence E[|gt − ∇ℓt (xt )|p | Ft−1 ] ≤ σ p . Also, since |µt | ≤ σ/8, the deterministic linear losses are G-Lipschitz with G ≤ σ/8. Step 4: KL divergence, total variation, and data processing. For one round, the two laws P+ and P− differ by swapping the probabilities of +Z and −Z. Thus q q + δ q −δ + δ log 2q + − δ log 2q 2 2 2 −δ 2 +δ q +δ = 2δ log 2q . 2 −δ
KL(P+ ∥P− ) =
q
With q = 1/(4L) and δ = 1/(32L), q 5 +δ = , 2 32L
q 3 −δ = . 2 32L 25
Therefore, 1 5 log . 16L 3 For a block of length L, since the gradient estimates are i.i.d. inside the block, KL(P+ ∥P− ) =
KL(P+L ∥P−L ) = L · KL(P+ ∥P− ) =
5 1 log . 16 3
By Pinsker’s inequality, r TV(P+L , P−L ) ≤
1 KL(P+L ∥P−L ) = 2
r
1 5 1 log < . 32 3 2
(72)
Now fix a block k. Let H denote the complete pre-block history, including all previous observations, actions, and learner randomness. Let g denote the gradient sequence inside block k, and let τ denote the block-k transcript consisting of the learner’s actions and observations inside that block. Because the current sign νk is chosen independently of the past, the law of H is the same under νk = +1 and νk = −1. Let Q denote this common law. Under νk = ν, the joint law of (H, g) is Q ⊗ PνL . The block transcript τ is obtained from (H, g) by applying the learner’s policy, which is the same under νk = +1 and νk = −1. By the data-processing inequality for total variation, TV(τ+ , τ− ) ≤ TV(Q ⊗ P+L , Q ⊗ P−L ). Since tensoring with a common probability measure does not change total variation, TV(Q ⊗ P+L , Q ⊗ P−L ) = TV(P+L , P−L ). Hence, for every block k, using (72), 1 TV(τ+ , τ− ) < . 2 (k)
(k)
Step 5: Apply the abstract block lower bound. For block k, let P+ and P− denote the unconditional marginal laws of the block transcript τ under νk = +1 and νk = −1, respectively. (k) (k) Let R+ and R− be the corresponding expected block regrets. By Lemma 9, specifically (68), (k) (k) (k) (k) R+ + R− ≥ 4DZδL 1 − TV(P+ , P− ) . (k)
(k)
From Step 4, TV(P+ , P− ) < 1/2. Therefore, (k)
(k)
R+ + R− ≥ 2DZδL. Since νk is uniform on {−1, +1}, the unconditional expected regret in block k is 1 (k) (k) R+ + R− ≥ DZδL. 2 Substituting the chosen constants from (71), DZδL = D ·
σ 1 41/p (4L)1/p · ·L= σDL1/p . 2 32L 64 26
Thus each block contributes at least
41/p σDL1/p 64
expected regret. Step 6: Sum over blocks. By linearity of expectation, the total expected regret over the active T ′ rounds in the Bayesian construction satisfies 41/p σDL1/p . 64 Since L = ⌊T /K⌋ and K ≤ T , we have L ≥ T /(2K). Therefore, from (73), 41/p 41/p T 1/p E[D-RegretT ′ ] ≥ σDT 1/p K 1−1/p . = σDK 64 2K 64 · 21/p E[D-RegretT ′ ] ≥ K ·
Because
K=
(73)
P̄T P̄T +1≥ , 2D 2D
we obtain 41/p E[D-RegretT ′ ] ≥ σDT 1/p 64 · 21/p
P̄T 2D
p−1 p .
Equivalently, p−1 41/p σD1/p T 1/p P̄T p . 128 The padding rounds contribute zero expected regret, so the same lower bound holds for the full horizon T . When PT ≤ 2D(T − 1), we have P̄T = PT , giving
E[D-RegretT ′ ] ≥
E[D-RegretT ] ≥
p−1 41/p σD1/p T 1/p PT p . 128
Step 7: From random signs to a deterministic comparator. The construction above first chooses random signs ν1 , . . . , νK . We have shown that p−1 41/p σD1/p T 1/p PT p , 128 where the expectation is over the random signs ν1 , . . . , νK , the stochastic first-order oracle g, and the learner’s internal randomness. ⋆ ) such that Therefore, by averaging, there exists a deterministic sign sequence ν ⋆ = (ν1⋆ , . . . , νK
Eν,g,alg [D-RegretT ] ≥
p−1 41/p σD1/p T 1/p PT p . 128 For this deterministic sign sequence, the comparator path length is at most PT , the losses ℓt (x) = µt x are deterministic linear losses, and the stochastic first-order oracle satisfies the conditional p-th central moment condition. This proves the theorem.
⋆ Eg,alg [D-RegretT | ν1 , . . . , νK = ν1⋆ , . . . , νK ]≥
Remark 6 (Matching upper and lower bounds). For PT ≳ D, the noise term in Theorem 1, specifically (35), satisfies p−1 p−1 p 1/p PT = σD1/p T 1/p PT p , σDT D which matches the lower bound in Theorem 3, specifically (69). Thus the exponent (p − 1)/p on PT is optimal. 27
References John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011. Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157–325, 2016. Langqi Liu, Yibo Wang, and Lijun Zhang. High-probability bound for non-smooth non-convex stochastic optimization with heavy tails. In Forty-first International Conference on Machine Learning, 2024. Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In International Conference on Learning Representations, volume 2024, pages 40394– 40428, 2024. Zijian Liu and Zhengyuan Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. In International Conference on Learning Representations, volume 2025, pages 92529–92554, 2025. Ziyi Liu. Online convex optimization with heavy tails: Old algorithms, new regrets, and applications. arXiv preprint arXiv:2508.07473v3, 2026. Benoit B Mandelbrot. Fractals and scaling in finance: Discontinuity, concentration, risk. Selecta volume E. Springer Science & Business Media, 2013. Arkadi S. Nemirovski and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, New York, 1983. ISBN 0-471-10345-4. Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019. Mohammad Pedramfar and Vaneet Aggarwal. A generalized approach to online convex optimization. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2026. Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends® in Machine Learning, 4(2):107–194, 2012. Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827– 5837. PMLR, 2019. Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Conference on Learning Theory, pages 65–102. PMLR, 2022. Yuchen Yang, Kaihong Lu, and Long Wang. Online distributed optimization with clipped stochastic gradients: High probability bound of regrets. Automatica, 182:112525, 2025. Jingzhao Zhang and Ashok Cutkosky. Parameter-free regret in high probability with heavy tails. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
28
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J. Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems (NeurIPS), 2020. Lijun Zhang, Sheng Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems (NeurIPS), 2018. Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems (NeurIPS), 2020. Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25:1–52, 2024. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning (ICML), 2003.
29