Paper deep dive
Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
Vaneet Aggarwal
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise, where the stochastic gradient oracle admits only a finite $p$-th central moment for some $p \in (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 \textbf{HT-PAder}, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths with a pathwise meta-algorithm, \textbf{AdaGrad-Hedge}, which requires no moment conditions on meta-losses. For a domain of diameter $D$, Lipschitz constant $G$, noise level $\sigma$, and comparator path length $P_T$, HT-PAder achieves an expected universal dynamic regret of \[ \widetilde O\left( GD\sqrt{T(1+P_T/D)} + \sigma D T^{1/p}(1+P_T/D)^{(p-1)/p} \right). \] 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.
Tags
Links
- Source: https://arxiv.org/abs/2607.27073v1
- Canonical: https://arxiv.org/abs/2607.27073v1
Trouble viewing inline? Open PDF directly →
Full Text
74,295 characters extracted from source content.
Expand or collapse full text
Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise Vaneet Aggarwal111V. Aggarwal is with Purdue University, West Lafayette IN 47907, USA, email: vaneet@purdue.edu Abstract We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise, where the stochastic gradient oracle admits only a finite p-th central moment for some p∈(1,2]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 HT-PAder, 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 PTP_T, HT-PAder achieves an expected universal dynamic regret of O~(GDT(1+PT/D)+σDT1/p(1+PT/D)(p−1)/p). O (GD T(1+P_T/D)+σ DT^1/p(1+P_T/D)^(p-1)/p ). The algorithm does not require prior knowledge of any of these problem parameters. Even in the special case of finite variance (p=2p=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 xtx_t from a convex feasible set ⊆ℝdX ^d with diameter D, the environment reveals a G-Lipschitz convex loss function ℓt:→ℝ _t:X , and the learner incurs loss ℓt(xt) _t(x_t). 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(GDT)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=1Tℓt(xt)−∑t=1Tℓt(ut),D -Regret_T(u_1,…,u_T)= _t=1^T _t(x_t)- _t=1^T _t(u_t), (1) which compares against an arbitrary comparator sequence u1,…,uT∈u_1,…,u_T . The difficulty of the problem is captured by the path length PT=∑t=2T‖ut−ut−1‖,P_T= _t=2^T \|u_t-u_t-1 \|, (2) which measures the non-stationarity of the environment. Zhang et al. (2018) established the minimax optimal rate O(GDT(1+PT/D))O(GD T(1+P_T/D)) for convex functions, resolving a gap left by the earlier O(GDT(1+PT/D))O(GD T(1+P_T/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σ^p for some tail index p∈(1,2]p∈(1,2] and noise level σ. Under this weaker condition, the classical analysis of OGD breaks down: the standard proof requires [‖gt‖2]<∞E[ \|g_t \|^2]<∞, which may be infinite when p<2p<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(GDT+σDT1/p)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 \| _t \|^p with the correct exponent p rather than ‖ϵt‖2 \| _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 meta-algorithms such as Hedge or Optimistic Hedge whose regret analysis requires [‖ℓt‖2]<∞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 PTP_T, 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 dynamic-regret 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 [D-RegretT]=O~(GDT(1+PTD)+σDT1/p(1+PTD)p−1p).E[D -Regret_T]= O (GD T (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p ). (3) The bound has a natural decomposition into a deterministic term GDT(1+PT/D)GD T(1+P_T/D), matching the minimax rate when σ=0σ=0, and a noise term σDT1/p(1+PTD)(p−1)/pσ DT^1/p (1+ P_TD )^(p-1)/p. The noise term exhibits an interesting tradeoff: for p=2p=2, it matches the standard finite-variance rate. For p<2p<2, the exponent (p−1)/p<1/2(p-1)/p<1/2 means the dependence on PTP_T is weaker than PT P_T, 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(p-1)/p is tight, or merely an artifact of our analysis. We resolve this by proving a matching expected dynamic regret lower bound of Ω(σD1/pT1/pPTp−1p) (σ D^1/pT^1/pP_T p-1p ) 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(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=2p=2, HT-PAder gives [D-RegretT]=O~((G+σ)DT(1+PTD)),E[D -Regret_T]= O ((G+σ)D T (1+ P_TD ) ), (4) without knowing G, σ, or PTP_T. 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(GDT(1+PT/D))O(GD T(1+P_T/D)) dynamic regret. Zhang et al. (2018) closed the gap to the minimax rate O(GDT(1+PT/D))O(GD T(1+P_T/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 mirror descent under heavy tails, though their rates (G+σ)D/T1−1/p(G+σ)D/T^1-1/p are suboptimal because they do not recover GD/TGD/ T when σ=0σ=0. For non-convex optimization, Liu et al. (2024) established high-probability 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 their bound (G+σ)DT1/p(G+σ)DT^1/p does not recover the optimal GDTGD T rate when σ=0σ=0. OGD and AdaGrad under heavy tails. The most directly relevant work is Liu (2026), who showed that OGD, DA, and AdaGrad achieve the optimal static regret O(GDT+σDT1/p)O(GD T+σ DT^1/p) under heavy-tailed noise without any algorithmic modification. Their key technical contribution is a one-step inequality, our Lemma 2, that leverages the bounded-domain assumption to produce a ‖ϵt‖p \| _t \|^p term rather than ‖ϵt‖2 \| _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 parameter-free 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. Table 1 summarizes the comparison between our result and existing work. Table 1: Comparison of regret guarantees under stochastic gradients in OCO. Noise type: F=F= finite-variance noise, H=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 PTP_T; unless otherwise noted, the horizon T is assumed known and can typically be removed by standard doubling with logarithmic factors. Regret type: S=S= static regret, D=D= universal dynamic regret against an arbitrary comparator sequence u1:Tu_1:T with path length PT=∑t=2T‖ut−ut−1‖P_T= _t=2^T\|u_t-u_t-1\|, and DW=DW= worst-case dynamic regret against the per-round minimizer sequence xt⋆x_t with path length CT=∑t=2T‖xt⋆−xt−1⋆‖C_T= _t=2^T\|x_t -x_t-1 \|. Rates are in expectation unless marked with † , which denotes a high-probability guarantee. O~ O hides logarithmic factors. 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 Expected regret Zhang et al. (2018) FF ✓ × DD O(GDT(1+PTD))O\! (GD T\! (1+ P_TD ) ) Zhao et al. (2024) FF ✓ × DD O((1+PT+VT)(1+PT))O\! ( (1+P_T+V_T)(1+P_T) ) Yang et al. (2025)† HH × × DWDW O~(T1+p2p(CT+logT)) O\! (T 1+p2p\! (C_T+ T ) ) Zhang and Cutkosky (2022)†,∗ HH × × SS O~((G+σ)DT1/p) O\! ((G+σ)DT^1/p ) Liu (2026), AdaGrad HH ✓ ✓ SS O(GDT+σDT1/p)O\! (GD T+σ DT^1/p ) This work, known G HH ✓ × DD O~(GDT(1+PTD)+σDT1/p(1+PTD)p−1p) O\! (GD T\! (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p ) This work, HT-PAder‡ H ✓ ✓ D O~(GDT(1+PTD)+σDT1/p(1+PTD)p−1p) O\! (GD T\! (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p ) † High-probability guarantee. ∗ Parameter-free in the comparator-norm sense used for unbounded domains, but not parameter-free with respect to G,σ,p,TG,σ,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, with logarithmic factors hidden in O~ O. The algorithm does not require G, σ, p, or PTP_T. 3 Problem Setup We consider a nonempty, closed, convex decision set ⊂ℝdX ^d with bounded diameter D=supx,y∈‖x−y‖<∞.D= _x,y \|x-y\|<∞. (5) At each round t∈[T]t∈[T], the environment reveals a convex and G-Lipschitz loss function ℓt:→ℝ _t:X , satisfying ‖∇ℓt(x)‖≤G,∀x∈.\|∇ _t(x)\|≤ G, ∀ x . (6) Upon playing a decision xt∈x_t , the learner queries a stochastic gradient oracle to receive an estimate gt∈ℝdg_t ^d. We assume the stochastic gradient estimate is unbiased: [gt∣ℱt−1]=∇ℓt(xt),E[g_t _t-1]=∇ _t(x_t), (7) where ℱt=σ(g1,…,gt)F_t=σ(g_1,…,g_t) 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) _t=g_t-∇ _t(x_t) is bounded: [‖ϵt‖p∣ℱt−1]≤σp,E[\| _t\|^p _t-1]≤σ^p, (8) for some tail index p∈(1,2]p∈(1,2] and noise level σ≥0σ≥ 0. Under this condition, standard OCO algorithms can diverge due to the lack of finite variance when p<2p<2 (Zhang et al., 2020). The special case p=2p=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∈u_1,…,u_T : D-RegretT(u1,…,uT)=∑t=1Tℓt(xt)−∑t=1Tℓt(ut).D -Regret_T(u_1,…,u_T)= _t=1^T _t(x_t)- _t=1^T _t(u_t). (9) The non-stationarity of the environment is captured by the path length PT=∑t=2T‖ut−ut−1‖.P_T= _t=2^T\|u_t-u_t-1\|. (10) We aim to establish dynamic regret bounds that hold universally for all comparator sequences without prior knowledge of PTP_T, 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. Lemma 1 (Linearization). Let u1,…,uT∈u_1,…,u_T be a fixed comparator sequence. Let xtx_t be ℱt−1F_t-1-measurable. Under the setup described in Section 3, [D-RegretT]≤[∑t=1T⟨gt,xt−ut⟩].E[D -Regret_T] [ _t=1^T g_t,x_t-u_t ]. (11) Proof. By convexity, ℓt(xt)−ℓt(ut)≤⟨∇ℓt(xt),xt−ut⟩. _t(x_t)- _t(u_t)≤ ∇ _t(x_t),x_t-u_t . Taking conditional expectations and using unbiasedness, [⟨gt,xt−ut⟩∣ℱt−1]=⟨[gt∣ℱt−1],xt−ut⟩=⟨∇ℓt(xt),xt−ut⟩.E[ g_t,x_t-u_t _t-1]= [g_t _t-1],x_t-u_t = ∇ _t(x_t),x_t-u_t . 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 \| _t \|^p term with the correct exponent rather than ‖ϵt‖2 \| _t \|^2. Lemma 2 (Liu (2026)). Under the setup described in Section 3, for OGD with fixed stepsize η>0η>0, for any x∈x , ⟨gt,xt−x⟩≤‖xt−x‖2−‖xt+1−x‖22η+ηG2+C(p)ηp−1‖ϵt‖pD2−p, g_t,x_t-x ≤ \|x_t-x \|^2- \|x_t+1-x \|^22η+η G^2+C(p)\,η^p-1\, \| _t \|^p\,D^2-p, (12) where C(p)=(4p−4)(p−1)/p.C(p)= (4p-4)^(p-1)/pp. (13) Proof. By the optimality condition of the projection xt+1=Π(xt−ηgt)x_t+1= _X(x_t-η g_t), for any x∈x , ⟨gt,xt+1−x⟩≤‖xt−x‖2−‖xt+1−x‖2−‖xt−xt+1‖22η. g_t,x_t+1-x ≤ \|x_t-x \|^2- \|x_t+1-x \|^2- \|x_t-x_t+1 \|^22η. Adding and subtracting ⟨gt,xt+1−x⟩ g_t,x_t+1-x gives ⟨gt,xt−x⟩≤‖xt−x‖2−‖xt+1−x‖22η+⟨gt,xt−xt+1⟩−‖xt−xt+1‖22η. g_t,x_t-x ≤ \|x_t-x \|^2- \|x_t+1-x \|^22η+ g_t,x_t-x_t+1 - \|x_t-x_t+1 \|^22η. Decompose gt=∇ℓt(xt)+ϵtg_t=∇ _t(x_t)+ _t. For the deterministic part, by Cauchy–Schwarz, AM-GM, and ‖∇ℓt(xt)‖≤G\|∇ _t(x_t)\|≤ G, ⟨∇ℓt(xt),xt−xt+1⟩≤G‖xt−xt+1‖≤ηG2+‖xt−xt+1‖24η. ∇ _t(x_t),x_t-x_t+1 ≤ G \|x_t-x_t+1 \|≤η G^2+ \|x_t-x_t+1 \|^24η. For the noise part, by Cauchy–Schwarz and Young’s inequality, together with ‖xt−xt+1‖≤D \|x_t-x_t+1 \|≤ D, ⟨ϵt,xt−xt+1⟩≤‖ϵt‖‖xt−xt+1‖≤C(p)ηp−1‖ϵt‖pD2−p+‖xt−xt+1‖24η. _t,x_t-x_t+1 ≤ \| _t \| \|x_t-x_t+1 \|≤ C(p)η^p-1 \| _t \|^pD^2-p+ \|x_t-x_t+1 \|^24η. Combining the two bounds, ⟨gt,xt−xt+1⟩−‖xt−xt+1‖22η≤ηG2+C(p)ηp−1‖ϵt‖pD2−p. g_t,x_t-x_t+1 - \|x_t-x_t+1 \|^22η≤η G^2+C(p)η^p-1 \| _t \|^pD^2-p. Plugging this into the previous display yields the claimed inequality. ∎ 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>0D>0 and a block of length m. Run AdaGrad-Norm inside the block with parameter η=D/2η=D/ 2, restarting at the beginning of the block. That is, with local potential Vt=∑s=1t‖gs‖2,V_t= _s=1^t \|g_s \|^2, (14) and stepsize ηt=ηVt, _t= η V_t, (15) the update is xt+1=Π(xt−ηtgt),x_t+1= _X(x_t- _tg_t), (16) with the convention that if Vt=0V_t=0, the update is skipped. Let VB=Vm=∑t=1m‖gt‖2,V_B=V_m= _t=1^m \|g_t \|^2, (17) and PB=∑t=2m‖ut−ut−1‖.P_B= _t=2^m \|u_t-u_t-1 \|. (18) Then for any comparator sequence u1,…,um∈u_1,…,u_m , ∑t=1m⟨gt,xt−ut⟩≤CVB(D+PB), _t=1^m g_t,x_t-u_t ≤ C\, V_B\,(D+P_B), (19) where C>0C>0 is a universal constant. In particular, one may take C=32/2C=3 2/2. Proof. For any ut∈u_t , by nonexpansiveness of the projection, ‖xt+1−ut‖2≤‖xt−ηtgt−ut‖2. \|x_t+1-u_t \|^2≤ \|x_t- _tg_t-u_t \|^2. Expanding, ‖xt+1−ut‖2≤‖xt−ut‖2−2ηt⟨gt,xt−ut⟩+ηt2‖gt‖2. \|x_t+1-u_t \|^2≤ \|x_t-u_t \|^2-2 _t g_t,x_t-u_t + _t^2 \|g_t \|^2. Rearranging, ⟨gt,xt−ut⟩≤‖xt−ut‖2−‖xt+1−ut‖22ηt+ηt‖gt‖22. g_t,x_t-u_t ≤ \|x_t-u_t \|^2- \|x_t+1-u_t \|^22 _t+ _t \|g_t \|^22. Define at:=12ηt=Vt2η.a_t:= 12 _t= V_t2η. (20) Since VtV_t is nondecreasing, ata_t is nondecreasing. Summing over t=1,…,mt=1,…,m, ∑t=1m⟨gt,xt−ut⟩≤T1+T2, _t=1^m g_t,x_t-u_t ≤ T_1+T_2, where T1:=∑t=1mat‖xt−ut‖2−∑t=1mat‖xt+1−ut‖2,T_1:= _t=1^ma_t \|x_t-u_t \|^2- _t=1^ma_t \|x_t+1-u_t \|^2, and T2:=∑t=1mηt‖gt‖22.T_2:= _t=1^m _t \|g_t \|^22. We first bound T1T_1. Separate the last term in the second sum: T1 T_1 =a1‖x1−u1‖2+∑t=2m(at‖xt−ut‖2−at−1‖xt−ut−1‖2) =a_1 \|x_1-u_1 \|^2+ _t=2^m (a_t \|x_t-u_t \|^2-a_t-1 \|x_t-u_t-1 \|^2 ) −am‖xm+1−um‖2. -a_m \|x_m+1-u_m \|^2. Dropping the final negative term, T1≤a1‖x1−u1‖2+∑t=2m(at‖xt−ut‖2−at−1‖xt−ut−1‖2).T_1≤ a_1 \|x_1-u_1 \|^2+ _t=2^m (a_t \|x_t-u_t \|^2-a_t-1 \|x_t-u_t-1 \|^2 ). For each t≥2t≥ 2, write at‖xt−ut‖2−at−1‖xt−ut−1‖2 a_t \|x_t-u_t \|^2-a_t-1 \|x_t-u_t-1 \|^2 =(at−at−1)‖xt−ut−1‖2+at(‖xt−ut‖2−‖xt−ut−1‖2). =(a_t-a_t-1) \|x_t-u_t-1 \|^2+a_t ( \|x_t-u_t \|^2- \|x_t-u_t-1 \|^2 ). Because xt,ut,ut−1∈x_t,u_t,u_t-1 and diam()=Ddiam(X)=D, ‖xt−ut−1‖2≤D2. \|x_t-u_t-1 \|^2≤ D^2. Also, ‖xt−ut‖2−‖xt−ut−1‖2 \|x_t-u_t \|^2- \|x_t-u_t-1 \|^2 =2⟨xt−ut−1,ut−1−ut⟩+‖ut−ut−1‖2 =2 x_t-u_t-1,u_t-1-u_t + \|u_t-u_t-1 \|^2 ≤2D‖ut−ut−1‖+‖ut−ut−1‖2 ≤ 2D \|u_t-u_t-1 \|+ \|u_t-u_t-1 \|^2 ≤3D‖ut−ut−1‖, ≤ 3D \|u_t-u_t-1 \|, where the last step uses ‖ut−ut−1‖≤D \|u_t-u_t-1 \|≤ D. Therefore, at‖xt−ut‖2−at−1‖xt−ut−1‖2≤(at−at−1)D2+3Dat‖ut−ut−1‖.a_t \|x_t-u_t \|^2-a_t-1 \|x_t-u_t-1 \|^2≤(a_t-a_t-1)D^2+3Da_t \|u_t-u_t-1 \|. Summing over t=2,…,mt=2,…,m, T1≤a1D2+∑t=2m(at−at−1)D2+3D∑t=2mat‖ut−ut−1‖.T_1≤ a_1D^2+ _t=2^m(a_t-a_t-1)D^2+3D _t=2^ma_t \|u_t-u_t-1 \|. The first two terms telescope: a1D2+∑t=2m(at−at−1)D2=amD2.a_1D^2+ _t=2^m(a_t-a_t-1)D^2=a_mD^2. Thus T1≤amD2+3D∑t=2mat‖ut−ut−1‖.T_1≤ a_mD^2+3D _t=2^ma_t \|u_t-u_t-1 \|. Now substitute at=Vt/(2η)a_t= V_t/(2η). Since Vt≤Vm=VBV_t≤ V_m=V_B, amD2=D22ηVB,a_mD^2= D^22η V_B, and 3Dat=3D2ηVt≤3D2ηVB.3Da_t= 3D2η V_t≤ 3D2η V_B. Using η=D/2η=D/ 2, D22η=D2,3D2η=322. D^22η= D 2, 3D2η= 3 22. Hence T1≤D2VB+322VBPB.T_1≤ D 2 V_B+ 3 22 V_B\,P_B. Next we bound T2T_2. Since ηt=η/Vt _t=η/ V_t, T2=∑t=1mηt‖gt‖22=η2∑t=1m‖gt‖2Vt.T_2= _t=1^m _t \|g_t \|^22= η2 _t=1^m \|g_t \|^2 V_t. Because Vt=Vt−1+‖gt‖2V_t=V_t-1+ \|g_t \|^2, we have ‖gt‖2Vt=Vt−Vt−1Vt≤2(Vt−Vt−1). \|g_t \|^2 V_t= V_t-V_t-1 V_t≤ 2( V_t- V_t-1). Summing, ∑t=1m‖gt‖2Vt≤2Vm=2VB. _t=1^m \|g_t \|^2 V_t≤ 2 V_m=2 V_B. Therefore, T2≤ηVB=D2VB.T_2≤η V_B= D 2 V_B. Combining the bounds for T1T_1 and T2T_2, ∑t=1m⟨gt,xt−ut⟩≤2DVB+322VBPB. _t=1^m g_t,x_t-u_t ≤ 2\,D V_B+ 3 22 V_B\,P_B. Since 322≥2 3 22≥ 2, this implies ∑t=1m⟨gt,xt−ut⟩≤322VB(D+PB). _t=1^m g_t,x_t-u_t ≤ 3 22 V_B(D+P_B). 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, so a bound over an interval [s,e][s,e] would depend on ∑t=1e‖gt‖2 _t=1^e\|g_t\|^2 rather than the interval-local quantity ∑t=se‖gt‖2 _t=s^e\|g_t\|^2. Restarting resets the AdaGrad potential and localizes the correction terms to each block. The per-block initialization cost contributes the DVBD V_B term, which after summing over blocks becomes the DKDK term in the expert regret bound. 4.4 Moment Bounds Lemma 4. Under the setup described in Section 3, for any interval B⊆[T]B [T] of length |B||B|, [(∑t∈B‖ϵt‖p)1/p]≤σ|B|1/p.E\! [ ( _t∈ B \| _t \|^p )^\!1/p\, ]≤σ\,|B|^1/p. (21) Proof. By Jensen’s inequality, since x↦x1/px x^1/p is concave for p≥1p≥ 1, [(∑t∈B‖ϵt‖p)1/p]≤([∑t∈B‖ϵt‖p])1/p≤(σp|B|)1/p=σ|B|1/p.E\! [ ( _t∈ B \| _t \|^p )^\!1/p ]≤ (E\! [ _t∈ B \| _t \|^p ] )^\!1/p≤(σ^p|B|)^1/p=σ\,|B|^1/p. ∎ The following lemma is used repeatedly. Lemma 5. Under the setup described in Section 3, for any interval B⊆[T]B [T] of length |B||B|, [∑t∈B‖gt‖2]≤G|B|+σ|B|1/p.E\! [ _t∈ B \|g_t \|^2\, ]≤ G |B|+σ\,|B|^1/p. (22) Proof. We apply Minkowski’s inequality in ℓ2(ℝ|B|) _2(R^|B|) followed by the monotonicity of ℓq _q-norms: ∑t∈B‖gt‖2 _t∈ B \|g_t \|^2 =‖(‖gt‖)t∈B‖ℓ2 = \|( \|g_t \|)_t∈ B \|_ _2 =‖(‖∇ℓt(xt)+ϵt‖)t∈B‖ℓ2 = \|( \|∇ _t(x_t)+ _t \|)_t∈ B \|_ _2 ≤‖(‖∇ℓt(xt)‖)t∈B‖ℓ2+‖(‖ϵt‖)t∈B‖ℓ2 ≤ \|( \|∇ _t(x_t) \|)_t∈ B \|_ _2+ \|( \| _t \|)_t∈ B \|_ _2 ≤∑t∈BG2+‖(‖ϵt‖)t∈B‖ℓp ≤ _t∈ BG^2+ \|( \| _t \|)_t∈ B \|_ _p =G|B|+(∑t∈B‖ϵt‖p)1/p. =G |B|+ ( _t∈ B \| _t \|^p )^\!1/p. 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 wtw_t over M experts. At each round, it receives a meta-loss vector mt∈ℝMm_t ^M. 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 WtW_t in (23) tracks the squared ℓ∞ _∞ norm of all past meta-loss vectors. The adaptive learning rate εt _t in (24) decreases as WtW_t 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 WTW_T pathwise, no moment assumption on mtm_t is required. This property is essential for compatibility with heavy-tailed stochastic gradients. Algorithm 1 AdaGrad-Hedge: Pathwise Meta-Algorithm 0: Number of experts M, parameter a≥lnM+1a≥ M+1 1: Initialize weights uniformly: w1,i=1/Mw_1,i=1/M for all i∈[M]i∈[M]. 2: Initialize cumulative scale: W0=1W_0=1. 3: for t=1,2,…t=1,2,… do 4: Output the current weight vector wtw_t. 5: Receive meta-loss vector mt∈ℝMm_t ^M. 6: Update cumulative scale: Wt=Wt−1+‖mt‖∞2.W_t=W_t-1+ \|m_t \|_∞^2. 7: Set adaptive learning rate: εt=aWt. _t= aW_t. 8: For each expert i∈[M]i∈[M], update wt+1,i∝exp(−εt∑s=1tms,i).w_t+1,i \! (- _t _s=1^tm_s,i ). 9: end for Lemma 6 (AdaGrad-Hedge). Let m1,…,mT∈ℝMm_1,…,m_T ^M be any sequence of loss vectors, with no distributional assumptions. Let wtw_t be generated by Algorithm 1. Define Wt=1+∑s=1t‖ms‖∞2,W_t=1+ _s=1^t \|m_s \|_∞^2, (23) let a≥lnM+1a≥ M+1, and set εt=aWt. _t= aW_t. (24) The weights satisfy wt+1,i∝exp(−εt∑s=1tms,i),∀i∈[M].w_t+1,i \! (- _t _s=1^tm_s,i ), ∀\,i∈[M]. (25) Then for any expert i∈[M]i∈[M], ∑t=1T⟨wt,mt⟩−∑t=1Tmt,i≤3aWT. _t=1^T w_t,m_t - _t=1^Tm_t,i≤ 3 a\,W_T. (26) Proof. This is FTRL with shifted negative entropy ϕ(w)=∑i=1Mwilnwi+lnM,φ(w)= _i=1^Mw_i w_i+ M, which is 11-strongly convex with respect to ∥⋅∥1 \|· \|_1 on the simplex. The update is equivalently wt+1=argminw∈ΔMεt∑s=1t⟨w,ms⟩+ϕ(w).w_t+1= _w∈ _M \ _t _s=1^t w,m_s +φ(w) \. By the standard AdaGrad-FTRL inequality (Orabona, 2019, Theorem 7.35), for any q∈ΔMq∈ _M, ∑t=1T⟨wt,mt⟩−∑t=1T⟨q,mt⟩≤ϕ(q)εT+∑t=1Tεt‖mt‖∞2. _t=1^T w_t,m_t - _t=1^T q,m_t ≤ φ(q) _T+ _t=1^T _t \|m_t \|_∞^2. (27) Taking q=eiq=e_i, we have ϕ(ei)=lnM≤aφ(e_i)= M≤ a. Since εT=a/WT _T= a/W_T, ϕ(ei)εT≤a/WT=aWT. φ(e_i) _T≤ a a/W_T= aW_T. Also, ∑t=1Tεt‖mt‖∞2=a∑t=1TWt−Wt−1Wt. _t=1^T _t \|m_t \|_∞^2= a _t=1^T W_t-W_t-1 W_t. For at≥at−1≥0a_t≥ a_t-1≥ 0, at−at−1at≤2(at−at−1). a_t-a_t-1 a_t≤ 2( a_t- a_t-1). Therefore, ∑t=1TWt−Wt−1Wt≤2WT. _t=1^T W_t-W_t-1 W_t≤ 2 W_T. Hence ∑t=1Tεt‖mt‖∞2≤2aWT. _t=1^T _t \|m_t \|_∞^2≤ 2 aW_T. Combining the two terms in (27) gives ∑t=1T⟨wt,mt⟩−∑t=1Tmt,i≤3aWT. _t=1^T w_t,m_t - _t=1^Tm_t,i≤ 3 aW_T. ∎ Remark 2 (Why standard Hedge fails under heavy tails). Standard Hedge with fixed learning rate ε gives meta-regret ≤lnMε+ε∑t‖mt‖∞2.≤ M + _t \|m_t \|_∞^2. Taking expectations requires [‖mt‖∞2]<∞E[ \|m_t \|_∞^2]<∞. In our setting, ‖mt‖∞≤D‖gt‖ \|m_t \|_∞≤ D \|g_t \|, and [‖gt‖2]E[ \|g_t \|^2] may be infinite when p<2p<2. AdaGrad-Hedge avoids this by bounding WT W_T 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 meta-algorithm in isolation, but rather: (i) the pathwise refined form used here; (i) its coupling with restarted AdaGrad experts; and (i) the resulting parameter-free universal dynamic regret guarantee under heavy-tailed noise. 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 0: Horizon T, domain X, diameter D 1: Let N=⌈log2T⌉N= _2T and M=N+1M=N+1. 2: for i=0,…,Ni=0,…,N do 3: Define Ki=2i∧TK_i=2^i T and Li=⌈T/Ki⌉L_i= T/K_i . 4: Activate expert EiE_i: restarted AdaGrad with block length LiL_i. 5: end for 6: Initialize AdaGrad-Hedge, Algorithm 1, with M experts and parameter a=lnM+2a= M+2. 7: for t=1,…,Tt=1,…,T do 8: Receive xt(i)x_t^(i) from each expert EiE_i. 9: Using the current AdaGrad-Hedge weights wtw_t, play xt=∑i=0Nwt,ixt(i).x_t= _i=0^Nw_t,i\,x_t^(i). 10: Observe stochastic gradient gtg_t. 11: Define meta-loss vector mt,i=⟨gt,xt(i)−xt⟩,i=0,…,N.m_t,i= g_t,x_t^(i)-x_t , i=0,…,N. 12: Update the meta-weights from wtw_t to wt+1w_t+1 using AdaGrad-Hedge, Algorithm 1, with meta-loss mtm_t. 13: Send gtg_t to each expert EiE_i. 14: end for The expert pool is indexed by i=0,…,Ni=0,…,N. Expert EiE_i is associated with a number of blocks KiK_i and block length LiL_i given by Ki=2i∧T,Li=⌈TKi⌉.K_i=2^i T, L_i= TK_i . (28) Expert EiE_i partitions [T][T] into consecutive blocks of length LiL_i. At the beginning of each block, it resets its iterate to a fixed point x0∈x_0 and resets its local AdaGrad potential to zero. Inside a block starting at round s, it maintains Vt(i)=∑r=st‖gr‖2,V_t^(i)= _r=s^t \|g_r \|^2, (29) and uses the stepsize ηt(i)=D2Vt(i). _t^(i)= D 2V_t^(i). (30) The expert update is xt+1(i)=Π(xt(i)−ηt(i)gt),x_t+1^(i)= _X (x_t^(i)- _t^(i)g_t ), (31) with the convention that the update is skipped if Vt(i)=0V_t^(i)=0. At round t, the algorithm combines expert predictions according to xt=∑i=0Nwt,ixt(i),x_t= _i=0^Nw_t,ix_t^(i), (32) where wtw_t is produced by AdaGrad-Hedge. The meta-loss assigned to expert i is mt,i=⟨gt,xt(i)−xt⟩.m_t,i= g_t,x_t^(i)-x_t . (33) This choice ensures that the weighted average meta-loss is zero: ∑i=0Nwt,imt,i=⟨gt,∑i=0Nwt,ixt(i)−xt⟩=0. _i=0^Nw_t,im_t,i= g_t, _i=0^Nw_t,ix_t^(i)-x_t =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 PTP_T. 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∈u_1,…,u_T , [D-RegretT]≲GDT(1+PTD)+σDT1/p(1+PTD)p−1p+D(1+GT+σT1/p)loglogT.E[D -Regret_T] GD T\! (1+ P_TD )+σ D\,T^1/p\! (1+ P_TD )^\! p-1p+D\! (1+G T+σ T^1/p )\! T. (34) Equivalently, [D-RegretT]=O~(GDT(1+PTD)+σDT1/p(1+PTD)p−1p).E[D -Regret_T]= O (GD T (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p ). (35) Corollary 1 (Finite-variance byproduct: double adaptivity). For p=2p=2, Theorem 1 gives [D-RegretT]=O~((G+σ)DT(1+PTD)).E[D -Regret_T]= O ((G+σ)D T (1+ P_TD ) ). (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=0P_T=0 static comparator: recovers the static rate of Liu (2026), matching O~(GDT+σDT1/p) O(GD T+σ DT^1/p). • σ=0σ=0 deterministic gradients: recovers the minimax rate of Zhang et al. (2018), matching O(GDT(1+PT/D))O(GD T(1+P_T/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: (i) establishing the meta-expert decomposition to separate the meta-regret and the expert regret; (i) bounding the meta-regret using the pathwise AdaGrad-Hedge guarantee; (i) 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), [D-RegretT]≤[∑t=1T⟨gt,xt−ut⟩].E[D -Regret_T] [ _t=1^T g_t,x_t-u_t ]. For any expert index i∈0,…,Ni∈\0,…,N\, ∑t=1T⟨gt,xt−ut⟩=∑t=1T⟨gt,xt−xt(i)⟩⏟meta-regret relative to i+∑t=1T⟨gt,xt(i)−ut⟩⏟expert linear regret for i. _t=1^T g_t,x_t-u_t = _t=1^T g_t,x_t-x_t^(i) _meta-regret relative to i+ _t=1^T g_t,x_t^(i)-u_t _expert linear regret for i. (37) Step 2: Bounding the Meta-Regret. Recall the meta-loss vector from (33): mt,i=⟨gt,xt(i)−xt⟩.m_t,i= g_t,x_t^(i)-x_t . Since xt=∑iwt,ixt(i)x_t= _iw_t,ix_t^(i), we have ∑i=0Nwt,imt,i=⟨gt,∑iwt,ixt(i)−xt⟩=0. _i=0^Nw_t,im_t,i= g_t, _iw_t,ix_t^(i)-x_t =0. Therefore, ⟨gt,xt−xt(i)⟩=∑j=0Nwt,jmt,j−mt,i. g_t,x_t-x_t^(i) = _j=0^Nw_t,jm_t,j-m_t,i. (38) By Lemma 6, specifically (26), pathwise, ∑t=1T⟨gt,xt−xt(i)⟩≤3aWT. _t=1^T g_t,x_t-x_t^(i) ≤ 3 aW_T. (39) Now, ‖mt‖∞=maxi|⟨gt,xt(i)−xt⟩|≤D‖gt‖,\|m_t\|_∞= _i| g_t,x_t^(i)-x_t |≤ D\|g_t\|, so WT=1+∑t=1T‖mt‖∞2≤1+D2∑t=1T‖gt‖2.W_T=1+ _t=1^T \|m_t \|_∞^2≤ 1+D^2 _t=1^T \|g_t \|^2. (40) Thus, WT≤1+D∑t=1T‖gt‖2. W_T≤ 1+D _t=1^T \|g_t \|^2. (41) Therefore, from (39) and (41), meta-regret≤3Da(1+∑t=1T‖gt‖2).meta-regret≤ 3D a (1+ _t=1^T \|g_t \|^2 ). Taking expectations and applying Lemma 5, specifically (22), [meta-regret]≤3Da(1+GT+σT1/p).E[meta-regret]≤ 3D a\,(1+G T+σ T^1/p). Since M=O(logT)M=O( T) and a=lnM+2=O(loglogT)a= M+2=O( T), we obtain [meta-regret]≲D(1+GT+σT1/p)loglogT.E[meta-regret] D(1+G T+σ T^1/p) 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η=D/ 2, restarting every L rounds. For any fixed comparator sequence u1,…,uT∈u_1,…,u_T with path length PTP_T, [∑t=1T⟨gt,xt−ut⟩]≲(GL+σL1/p)(D⌈TL⌉+PT).E [ _t=1^T g_t,x_t-u_t ] (G L+σ L^1/p) (D TL +P_T ). (43) Proof. Partition [T][T] into K=⌈T/L⌉K= T/L blocks B1,…,BKB_1,…,B_K, each of length at most L. For block BbB_b, define Vb=∑t∈Bb‖gt‖2,Pb=∑t∈Bbt≥2‖ut−ut−1‖.V_b= _t∈ B_b \|g_t \|^2, P_b= _ subarrayct∈ B_b\\ t≥ 2 subarray \|u_t-u_t-1 \|. (44) The quantity PbP_b counts only comparator movement internal to block BbB_b. Comparator movement across block boundaries is deliberately excluded: its effect is absorbed by the per-block restart cost DVbD V_b, which after summing over blocks yields the DKDK term. By Lemma 3, specifically (19), pathwise, ∑t∈Bb⟨gt,xt−ut⟩≤CVb(D+Pb). _t∈ B_b g_t,x_t-u_t ≤ C V_b(D+P_b). (45) Taking expectations and applying Lemma 5 to block BbB_b, [Vb]≤G|Bb|+σ|Bb|1/p≤GL+σL1/p.E[ V_b]≤ G |B_b|+σ|B_b|^1/p≤ G L+σ L^1/p. (46) Hence [∑t∈Bb⟨gt,xt−ut⟩]≲(GL+σL1/p)(D+Pb).E [ _t∈ B_b g_t,x_t-u_t ] (G L+σ L^1/p)(D+P_b). Summing over blocks, [∑t=1T⟨gt,xt−ut⟩]≲(GL+σL1/p)(DK+∑b=1KPb).E [ _t=1^T g_t,x_t-u_t ] (G L+σ L^1/p) (DK+ _b=1^KP_b ). (47) Since ∑bPb≤PT _bP_b≤ P_T and K=⌈T/L⌉K= T/L , (47) implies (43). ∎ Step 4: Choosing the Right Block-Length Expert. Define K⋆=1+PTD.K =1+ P_TD. (48) Since any comparator sequence in X satisfies PT≤D(T−1)P_T≤ D(T-1), we have K⋆≤TK ≤ T. The expert pool contains experts with Ki=2i∧TK_i=2^i T, for i=0,…,Ni=0,…,N. Therefore, there exists an index i⋆i such that Ki⋆∈[K⋆,2K⋆].K_i ∈[K ,2K ]. (49) The corresponding block length is Li⋆=⌈TKi⋆⌉.L_i = TK_i . Since Ki⋆≥K⋆K_i ≥ K , we have Li⋆≤TK⋆+1≤2TK⋆.L_i ≤ TK +1≤ 2TK . By Lemma 7, specifically (43), the expected linear regret of expert i⋆i satisfies [expert regret for i⋆]≲(GLi⋆+σLi⋆1/p)(DKi⋆+PT).E[expert regret for i ] (G L_i +σ L_i ^1/p)(DK_i +P_T). (50) Using Ki⋆≤2K⋆K_i ≤ 2K , PT=D(K⋆−1)≤DK⋆P_T=D(K -1)≤ DK , and Li⋆≤2T/K⋆L_i ≤ 2T/K , we have DKi⋆+PT≲DK⋆,DK_i +P_T DK , and GLi⋆+σLi⋆1/p≲GTK⋆+σ(TK⋆)1/p.G L_i +σ L_i ^1/p G TK +σ ( TK )^1/p. Therefore, (50) gives [expert regret for i⋆]≲DK⋆(GTK⋆+σ(TK⋆)1/p).E[expert regret for i ] DK (G TK +σ ( TK )^1/p ). Simplifying, [expert regret for i⋆]≲GDTK⋆+σDT1/p(K⋆)1−1/p.E[expert regret for i ] GD TK +σ DT^1/p(K )^1-1/p. Substituting K⋆=1+PT/DK =1+P_T/D from (48), we obtain [expert regret for i⋆]≲GDT(1+PTD)+σDT1/p(1+PTD)p−1p.E[expert regret for i ] GD T (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p. (51) Step 5: Combining. From the decomposition (37), the meta-regret bound (42), and the expert-regret bound (51), [D-RegretT]≲GDT(1+PTD)+σDT1/p(1+PTD)p−1p+D(1+GT+σT1/p)loglogT.E[D -Regret_T] GD T (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p+D(1+G T+σ T^1/p) T. (52) This completes the proof of Theorem 1. 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. Appendix 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 _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 fixed-step OGD experts with restarted AdaGrad experts and using a geometric pool of block lengths instead of stepsizes. Algorithm 3 HT-IA: Heavy-Tailed Improved Ader, requires G 0: Horizon T, domain X, diameter D, Lipschitz constant G 1: Let ηi=2i−1D28G2T,i=1,…,N, _i=2^i-1 D^28G^2T, i=1,…,N, where N=⌈12log2(8G2TD2)⌉+1.N= 12 _2 ( 8G^2TD^2 ) +1. 2: Activate fixed-step OGD experts EiE_i with stepsize ηi _i: xt+1(i)=Π(xt(i)−ηigt).x_t+1^(i)= _X(x_t^(i)- _ig_t). 3: Initialize AdaGrad-Hedge, Algorithm 1, with M=NM=N experts and parameter a=lnN+2a= N+2. 4: for t=1,…,Tt=1,…,T do 5: Receive xt(i)x_t^(i) from each expert EiE_i. 6: Using the current AdaGrad-Hedge weights wtw_t, play xt=∑i=1Nwt,ixt(i).x_t= _i=1^Nw_t,ix_t^(i). 7: Observe stochastic gradient gtg_t. 8: Define meta-loss vector mt,i=⟨gt,xt(i)−xt⟩.m_t,i= g_t,x_t^(i)-x_t . 9: Update the meta-weights from wtw_t to wt+1w_t+1 using AdaGrad-Hedge, Algorithm 1, with meta-loss mtm_t. 10: Send gtg_t to each expert. 11: end for More explicitly, the stepsize pool is ηi=2i−1D28G2T,i=1,…,N, _i=2^i-1 D^28G^2T, i=1,…,N, (53) with pool size N=⌈12log2(8G2TD2)⌉+1.N= 12 _2 ( 8G^2TD^2 ) +1. (54) Each expert EiE_i runs fixed-step OGD: xt+1(i)=Π(xt(i)−ηigt).x_t+1^(i)= _X(x_t^(i)- _ig_t). (55) The meta-level weight update is handled by Algorithm 1. Thus, HT-IA can be viewed as a heavy-tailed 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. Theorem 2 (Known-G dynamic regret). Under the setup of Section 3, Algorithm 3 guarantees: [D-RegretT]≲pGDT(1+PTD)+σDT1/p(1+PTD)p−1p+D(1+GT+σT1/p)loglogT.E[D -Regret_T] _pGD T (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p+D(1+G T+σ T^1/p) T. (56) Proof. By the meta-expert decomposition, as in (37), the expected dynamic regret of Algorithm 3 is bounded by [D-RegretT]≤[meta-regret]+[expert regret for ηi⋆],E[D -Regret_T] [meta-regret]+E[expert regret for _i ], (57) where i⋆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 mt,i=⟨gt,xt(i)−xt⟩.m_t,i= g_t,x_t^(i)-x_t . (58) Using Lemma 6, specifically (26), with WT=1+∑t=1T‖mt‖∞2,W_T=1+ _t=1^T\|m_t\|_∞^2, we have pathwise ∑t=1T⟨gt,xt−xt(i)⟩≤3aWT. _t=1^T g_t,x_t-x_t^(i) ≤ 3 aW_T. (59) Using ‖mt‖∞≤D‖gt‖\|m_t\|_∞≤ D\|g_t\|, we obtain WT≤1+D2∑t=1T‖gt‖2.W_T≤ 1+D^2 _t=1^T\|g_t\|^2. (60) Taking expectations and applying Lemma 5 over the full horizon [T][T] yields [meta-regret] [meta-regret] ≤3Da(1+[∑t=1T‖gt‖2]) ≤ 3D a (1+E [ _t=1^T\|g_t\|^2 ] ) ≤3Da(1+GT+σT1/p). ≤ 3D a (1+G T+σ T^1/p ). Since N=O(logT)N=O( T) and a=lnN+2=O(loglogT)a= N+2=O( T), we have [meta-regret]≲D(1+GT+σT1/p)loglogT.E[meta-regret] D(1+G T+σ T^1/p) T. (61) Next, we bound the expert regret. For any fixed stepsize ηi _i from the expert pool, summing the one-step inequality (12) from Lemma 2 over t=1,…,Tt=1,…,T with comparator utu_t yields ∑t=1T⟨gt,xt(i)−ut⟩≤∑t=1T‖xt(i)−ut‖2−‖xt+1(i)−ut‖22ηi+ηiG2T+C(p)ηip−1D2−p∑t=1T‖ϵt‖p. _t=1^T g_t,x_t^(i)-u_t ≤ _t=1^T \|x_t^(i)-u_t\|^2-\|x_t+1^(i)-u_t\|^22 _i+ _iG^2T+C(p) _i^p-1D^2-p _t=1^T\| _t\|^p. (62) By standard moving-comparator telescoping, ∑t=1T‖xt(i)−ut‖2−‖xt+1(i)−ut‖22ηi≤D2+2DPT2ηi. _t=1^T \|x_t^(i)-u_t\|^2-\|x_t+1^(i)-u_t\|^22 _i≤ D^2+2DP_T2 _i. (63) Taking expectations in (62) and using (8) gives [∑t=1T⟨gt,xt(i)−ut⟩]≤D2+2DPT2ηi+ηiG2T+C(p)ηip−1D2−pσpT.E [ _t=1^T g_t,x_t^(i)-u_t ]≤ D^2+2DP_T2 _i+ _iG^2T+C(p) _i^p-1D^2-pσ^pT. (64) To optimize the stepsize, we apply Lemma 8 with A=D2+2DPT2,B=G2T,C=C(p)D2−pσpT.A= D^2+2DP_T2, B=G^2T, C=C(p)D^2-pσ^pT. (65) This implies that the optimal stepsize η⋆η satisfies Aη⋆+Bη⋆+C(η⋆)p−1≲pAB+A(p−1)/pC1/p. Aη +Bη +C(η )^p-1 _p AB+A^(p-1)/pC^1/p. (66) Substituting the values of A, B, and C from (65), AB=GDT(1+PTD), AB=GD T (1+ P_TD ), and A(p−1)/pC1/p≤σDT1/p(1+PTD)p−1p.A^(p-1)/pC^1/p≤σ DT^1/p (1+ P_TD ) p-1p. The geometric stepsize pool constructed in (53)–(54) covers the relevant interval up to a factor of 22. Hence, there exists an expert stepsize ηi⋆ _i in the pool such that ηi⋆≤η⋆≤2ηi⋆. _i ≤η ≤ 2 _i . This ensures that [expert regret for ηi⋆]≲pGDT(1+PTD)+σDT1/p(1+PTD)p−1p.E[expert regret for _i ] _pGD T (1+ P_TD )+σ DT^1/p (1+ P_TD ) p-1p. (67) Combining (57), (61), and (67) completes the proof. ∎ Lemma 8 (Optimization lemma). For A,B,C>0A,B,C>0 and p∈(1,2]p∈(1,2], minη>0(Aη+Bη+Cηp−1)≲pAB+A(p−1)/pC1/p. _η>0 ( Aη+Bη+Cη^p-1 ) _p AB+A^(p-1)/pC^1/p. Proof. Set η1=A/(2B) _1= A/(2B) and η2=(A/(2C))1/p _2=(A/(2C))^1/p. Let η⋆=η1∧η2η = _1 _2. Case 1: η⋆=η1≤η2η = _1≤ _2. Then Aη1+Bη1≲AB. A _1+B _1 AB. Also, η1≤η2 _1≤ _2 implies C≤Bp/2(A/2)1−p/2,C≤ B^p/2(A/2)^1-p/2, and therefore Cη1p−1≤Bp/2(A/2)1−p/2(A2B)(p−1)/2≲AB.C _1^p-1≤ B^p/2(A/2)^1-p/2 ( A2B )^(p-1)/2 AB. Case 2: η⋆=η2≤η1η = _2≤ _1. Then Aη2+Cη2p−1≲pA(p−1)/pC1/p. A _2+C _2^p-1 _pA^(p-1)/pC^1/p. Also, using η2≤η1 _2≤ _1, Bη2=B(A2C)1/p≤B(A2B)1/2≲AB.B _2=B ( A2C )^1/p≤ B ( A2B )^1/2 AB. Combining the cases proves the lemma. ∎ Appendix 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>0D,Z,δ,L>0. For each hidden sign ν∈−1,+1ν∈\-1,+1\, define the comparator ut(ν)=−Dνu_t^(ν)=-Dν and the deterministic linear loss ℓt(ν)(x)=μνx,μν=2Zδν. _t^(ν)(x)= _νx, _ν=2Zδ\,ν. Let LT_L be a measurable space of complete interaction transcripts over L rounds. For ν∈−1,+1ν∈\-1,+1\, let PνLP_ν^L be a probability measure on LT_L. A transcript τ∈Lτ _L determines the learner’s decisions xt(τ)∈[−D,D],t=1,…,L.x_t(τ)∈[-D,D], t=1,…,L. The measures P+LP_+^L and P−LP_-^L may arise from learner randomness, environmental randomness, or both; no further probabilistic structure is required. Define the expected block regret under environment ν by Rν=τ∼PνL[∑t=1L(ℓt(ν)(xt(τ))−ℓt(ν)(ut(ν)))].R_ν=E_τ P_ν^L [ _t=1^L ( _t^(ν)(x_t(τ))- _t^(ν)(u_t^(ν)) ) ]. Then R++R−≥4DZδL(1−TV(P+L,P−L)).R_++R_-≥ 4DZδ L (1-TV(P_+^L,P_-^L) ). (68) Proof. For any transcript τ, since ℓt(ν)(x)=μνx _t^(ν)(x)= _νx, ℓt(ν)(xt(τ))−ℓt(ν)(ut(ν))=μν(xt(τ)−ut(ν)). _t^(ν)(x_t(τ))- _t^(ν)(u_t^(ν))= _ν(x_t(τ)-u_t^(ν)). Using ut(ν)=−Dνu_t^(ν)=-Dν and μν=2Zδν _ν=2Zδ\,ν, μν(xt(τ)−ut(ν))=2Zδν(xt(τ)+Dν)=2Zδ(D+νxt(τ)). _ν(x_t(τ)-u_t^(ν))=2Zδ\,ν(x_t(τ)+Dν)=2Zδ(D+ν x_t(τ)). Thus the instantaneous regret under environment ν is ℓt(ν)(xt(τ))−ℓt(ν)(ut(ν))=2Zδ(D+νxt(τ)). _t^(ν)(x_t(τ))- _t^(ν)(u_t^(ν))=2Zδ(D+ν x_t(τ)). Define the transcript functional F(τ):=∑t=1L(D+xt(τ)).F(τ):= _t=1^L(D+x_t(τ)). Because xt(τ)∈[−D,D]x_t(τ)∈[-D,D], we have F(τ)∈[0,2DL]F(τ)∈[0,2DL]. Under ν=+1ν=+1, the instantaneous regret is 2Zδ(D+xt)2Zδ(D+x_t), so R+=2Zδ+[F].R_+=2Zδ\,E_+[F]. Under ν=−1ν=-1, the instantaneous regret is 2Zδ(D−xt)2Zδ(D-x_t). Since D−xt=2D−(D+xt),D-x_t=2D-(D+x_t), we have ∑t=1L(D−xt)=2DL−F, _t=1^L(D-x_t)=2DL-F, and therefore R−=2Zδ−[2DL−F]=2Zδ(2DL−[F]).R_-=2Zδ\,E_-[2DL-F]=2Zδ (2DL-E_-[F] ). Thus R++R−=2Zδ(2DL−(−[F]−+[F])).R_++R_-=2Zδ (2DL- (E_-[F]-E_+[F] ) ). We now bound −[F]−+[F]E_-[F]-E_+[F] using total variation. Let A:=2DLA:=2DL. We use the layer-cake representation: FA=∫01F>Ass. FA= _0^11_\F>As\\,ds. Hence −[F]−+[F]A=∫01(P−(F>As)−P+(F>As))s. E_-[F]-E_+[F]A= _0^1 (P_-(F>As)-P_+(F>As) )\,ds. For every s∈[0,1]s∈[0,1], P−(F>As)−P+(F>As)≤TV(P+L,P−L).P_-(F>As)-P_+(F>As) (P_+^L,P_-^L). Therefore, −[F]−+[F]≤ATV(P+L,P−L)=2DLTV(P+L,P−L).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)).R_++R_-≥ 4DZδ L (1-TV(P_+^L,P_-^L) ). ∎ Theorem 3 (Lower bound for dynamic regret under heavy-tailed noise). Let =[−D,D]X=[-D,D] with D>0D>0, let σ>0σ>0, and let p∈(1,2]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),2D≤ P_T≤ 2D(T-1), there exist deterministic linear losses ℓt(x)=μtx, _t(x)= _tx, so that ∇ℓt(x)=μtfor all x∈,∇ _t(x)= _t all x , and a stochastic first-order oracle returning gradient estimates gtg_t such that, for the natural filtration ℱt=σ(g1,…,gt)F_t=σ(g_1,…,g_t), [gt∣ℱt−1]=∇ℓt(xt)=μt,E[g_t _t-1]=∇ _t(x_t)= _t, and the conditional p-th central moment condition holds: [|gt−μt|p∣ℱt−1]≤σp.E\! [|g_t- _t|^p _t-1 ]≤σ^p. Moreover, there exists a comparator sequence u1,…,uT∈u_1,…,u_T with path length at most PTP_T such that [D-RegretT]≥cpσD1/pT1/pPTp−1p,E[D -Regret_T]≥ c_p\,σ D^1/pT^1/pP_T p-1p, (69) where the expectation is over the stochastic first-order oracle and the learner’s internal randomness, and cp=41/p128.c_p= 4^1/p128. (70) If PT>2D(T−1)P_T>2D(T-1), the same statement holds with PTP_T replaced by 2D(T−1)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:=minPT, 2D(T−1). P_T:= \P_T,\,2D(T-1)\. Set K:=⌊P¯T2D⌋+1.K:= P_T2D +1. Because P¯T≤2D(T−1) P_T≤ 2D(T-1), we have K≤TK≤ T. Let L:=⌊TK⌋,T′:=KL.L:= TK , T :=KL. We use the first T′T rounds for the construction and pad the remaining T−T′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≤TK≤ T, we have L≥1L≥ 1 and T′≥T/2T ≥ T/2. Partition the first T′T rounds into K consecutive blocks of length L. For t in block k, write b(t):=kb(t):=k. In block k, choose an independent hidden sign νk∈−1,+1 _k∈\-1,+1\ uniformly at random. The comparator and mean gradient inside block k are ut=−Dνb(t),μt=2Zδνb(t).u_t=-D _b(t), _t=2Zδ\, _b(t). The deterministic loss is ℓt(x)=μtx _t(x)= _tx. For any realization of ν1,…,νK _1,…, _K, the path length satisfies ∑t=2T′|ut−ut−1|≤∑k=2K|−Dνk+Dνk−1|≤2D(K−1)≤P¯T≤PT. _t=2^T |u_t-u_t-1|≤ _k=2^K|-D _k+D _k-1|≤ 2D(K-1)≤ P_T≤ P_T. Step 2: One-block heavy-tailed construction. Inside each block of length L, define the constants q:=14L,δ:=132L,Z:=σ2(4L)1/p.q:= 14L, δ:= 132L, Z:= σ2(4L)^1/p. (71) Conditional on the hidden sign ν∈−1,+1ν∈\-1,+1\, the stochastic first-order oracle returns a gradient estimate g distributed as Pν(g=νZ)=q2+δ,Pν(g=−νZ)=q2−δ,Pν(g=0)=1−q.P_ν(g=ν Z)= q2+δ, P_ν(g=-ν Z)= q2-δ, P_ν(g=0)=1-q. The mean gradient is μν=νZ(q2+δ)+(−νZ)(q2−δ)=2Zδν. _ν=ν Z ( q2+δ )+(-ν Z) ( q2-δ )=2Zδ\,ν. Thus, for t in block k, μt=μνk=2Zδνk. _t= _ _k=2Zδ\, _k. For a fixed deterministic sign sequence ν1,…,νK _1,…, _K, the gradient estimates are independent of the past inside each block, so [gt∣ℱt−1]=μt=∇ℓt(xt).E[g_t _t-1]= _t=∇ _t(x_t). Step 3: Verification of the conditional p-th central moment condition. First, ν|g|p=qZp=14L(σ2)p(4L)=(σ2)p.E_ν|g|^p=qZ^p= 14L ( σ2 )^p(4L)= ( σ2 )^p. Also, |μν|=2Zδ=2⋅σ2(4L)1/p⋅132L=σ(4L)1/p32L.| _ν|=2Zδ=2· σ2(4L)^1/p· 132L= σ(4L)^1/p32L. Since p≥1p≥ 1 and L≥1L≥ 1, (4L)1/p32L=41/p32L1/p−1≤432=18. (4L)^1/p32L= 4^1/p32L^1/p-1≤ 432= 18. Hence |μν|≤σ/8| _ν|≤σ/8. By Minkowski’s inequality, (ν|g−μν|p)1/p≤(ν|g|p)1/p+|μν|≤σ2+σ8=5σ8<σ. (E_ν|g- _ν|^p )^1/p≤ (E_ν|g|^p )^1/p+| _ν|≤ σ2+ σ8= 5σ8<σ. Therefore, ν|g−μν|p≤σp.E_ν|g- _ν|^p≤σ^p. For a fixed deterministic sign sequence, the same bound holds conditionally on ℱt−1F_t-1. Hence [|gt−∇ℓt(xt)|p∣ℱt−1]≤σp.E\! [|g_t-∇ _t(x_t)|^p _t-1 ]≤σ^p. Also, since |μt|≤σ/8| _t|≤σ/8, the deterministic linear losses are G-Lipschitz with G≤σ/8G≤σ/8. Step 4: KL divergence, total variation, and data processing. For one round, the two laws P+P_+ and P−P_- differ by swapping the probabilities of +Z+Z and −Z-Z. Thus KL(P+∥P−) (P_+\|P_-) =(q2+δ)logq2+δq2−δ+(q2−δ)logq2−δq2+δ = ( q2+δ ) q2+δ q2-δ+ ( q2-δ ) q2-δ q2+δ =2δlogq2+δq2−δ. =2δ q2+δ q2-δ. With q=1/(4L)q=1/(4L) and δ=1/(32L)δ=1/(32L), q2+δ=532L,q2−δ=332L. q2+δ= 532L, q2-δ= 332L. Therefore, KL(P+∥P−)=116Llog53.KL(P_+\|P_-)= 116L 53. For a block of length L, since the gradient estimates are i.i.d. inside the block, KL(P+L∥P−L)=L⋅KL(P+∥P−)=116log53.KL(P_+^L\|P_-^L)=L·KL(P_+\|P_-)= 116 53. By Pinsker’s inequality, TV(P+L,P−L)≤12KL(P+L∥P−L)=132log53<12.TV(P_+^L,P_-^L)≤ 12KL(P_+^L\|P_-^L)= 132 53< 12. (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 _k is chosen independently of the past, the law of H is the same under νk=+1 _k=+1 and νk=−1 _k=-1. Let Q denote this common law. Under νk=ν _k=ν, the joint law of (H,)(H,g) is Q⊗PνLQ P_ν^L. The block transcript τ is obtained from (H,)(H,g) by applying the learner’s policy, which is the same under νk=+1 _k=+1 and νk=−1 _k=-1. By the data-processing inequality for total variation, TV(τ+,τ−)≤TV(Q⊗P+L,Q⊗P−L).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).TV(Q P_+^L,\,Q P_-^L)=TV(P_+^L,P_-^L). Hence, for every block k, using (72), TV(τ+,τ−)<12.TV( _+, _-)< 12. Step 5: Apply the abstract block lower bound. For block k, let P+(k)P_+^(k) and P−(k)P_-^(k) denote the unconditional marginal laws of the block transcript τ under νk=+1 _k=+1 and νk=−1 _k=-1, respectively. Let R+(k)R_+^(k) and R−(k)R_-^(k) be the corresponding expected block regrets. By Lemma 9, specifically (68), R+(k)+R−(k)≥4DZδL(1−TV(P+(k),P−(k))).R_+^(k)+R_-^(k)≥ 4DZδ L (1-TV(P_+^(k),P_-^(k)) ). From Step 4, TV(P+(k),P−(k))<1/2TV(P_+^(k),P_-^(k))<1/2. Therefore, R+(k)+R−(k)≥2DZδL.R_+^(k)+R_-^(k)≥ 2DZδ L. Since νk _k is uniform on −1,+1\-1,+1\, the unconditional expected regret in block k is 12(R+(k)+R−(k))≥DZδL. 12 (R_+^(k)+R_-^(k) )≥ DZδ L. Substituting the chosen constants from (71), DZδL=D⋅σ2(4L)1/p⋅132L⋅L=41/p64σDL1/p.DZδ L=D· σ2(4L)^1/p· 132L· L= 4^1/p64\,σ DL^1/p. Thus each block contributes at least 41/p64σDL1/p 4^1/p64\,σ DL^1/p expected regret. Step 6: Sum over blocks. By linearity of expectation, the total expected regret over the active T′T rounds in the Bayesian construction satisfies [D-RegretT′]≥K⋅41/p64σDL1/p.E[D -Regret_T ]≥ K· 4^1/p64\,σ DL^1/p. (73) Since L=⌊T/K⌋L= T/K and K≤TK≤ T, we have L≥T/(2K)L≥ T/(2K). Therefore, from (73), [D-RegretT′]≥41/p64σDK(T2K)1/p=41/p64⋅21/pσDT1/pK1−1/p.E[D -Regret_T ]≥ 4^1/p64\,σ DK ( T2K )^1/p= 4^1/p64· 2^1/p\,σ DT^1/pK^1-1/p. Because K=⌊P¯T2D⌋+1≥P¯T2D,K= P_T2D +1≥ P_T2D, we obtain [D-RegretT′]≥41/p64⋅21/pσDT1/p(P¯T2D)p−1p.E[D -Regret_T ]≥ 4^1/p64· 2^1/p\,σ DT^1/p ( P_T2D ) p-1p. Equivalently, [D-RegretT′]≥41/p128σD1/pT1/pP¯Tp−1p.E[D -Regret_T ]≥ 4^1/p128\,σ D^1/pT^1/p P_T p-1p. The padding rounds contribute zero expected regret, so the same lower bound holds for the full horizon T. When PT≤2D(T−1)P_T≤ 2D(T-1), we have P¯T=PT P_T=P_T, giving [D-RegretT]≥41/p128σD1/pT1/pPTp−1p.E[D -Regret_T]≥ 4^1/p128\,σ D^1/pT^1/pP_T p-1p. Step 7: From random signs to a deterministic comparator. The construction above first chooses random signs ν1,…,νK _1,…, _K. We have shown that ν,g,alg[D-RegretT]≥41/p128σD1/pT1/pPTp−1p,E_ν,g,alg[D -Regret_T]≥ 4^1/p128\,σ D^1/pT^1/pP_T p-1p, where the expectation is over the random signs ν1,…,νK _1,…, _K, the stochastic first-order oracle g, and the learner’s internal randomness. Therefore, by averaging, there exists a deterministic sign sequence ν⋆=(ν1⋆,…,νK⋆)ν =(ν _1,…,ν _K) such that g,alg[D-RegretT|ν1,…,νK=ν1⋆,…,νK⋆]≥41/p128σD1/pT1/pPTp−1p.E_g,alg [D -Regret_T\; |\; _1,…, _K=ν _1,…,ν _K ]≥ 4^1/p128\,σ D^1/pT^1/pP_T p-1p. For this deterministic sign sequence, the comparator path length is at most PTP_T, the losses ℓt(x)=μtx _t(x)= _tx are deterministic linear losses, and the stochastic first-order oracle satisfies the conditional p-th central moment condition. This proves the theorem. ∎ Remark 6 (Matching upper and lower bounds). For PT≳DP_T D, the noise term in Theorem 1, specifically (35), satisfies σDT1/p(PTD)p−1p=σD1/pT1/pPTp−1p,σ DT^1/p ( P_TD ) p-1p=σ D^1/pT^1/pP_T p-1p, which matches the lower bound in Theorem 3, specifically (69). Thus the exponent (p−1)/p(p-1)/p on PTP_T is optimal. References J. Duchi, E. Hazan, and Y. Singer (2011) Adaptive subgradient methods for online learning and stochastic optimization.. Journal of machine learning research 12 (7). Cited by: §2. E. Hazan (2016) Introduction to online convex optimization. Foundations and Trends in Optimization 2 (3-4), p. 157–325. Cited by: §1. L. Liu, Y. Wang, and L. Zhang (2024) High-probability bound for non-smooth non-convex stochastic optimization with heavy tails. In Forty-first International Conference on Machine Learning, Cited by: §2. Z. Liu and Z. Zhou (2024) Revisiting the last-iterate convergence of stochastic gradient methods. In International Conference on Learning Representations, Vol. 2024, p. 40394–40428. Cited by: §2. Z. Liu and Z. Zhou (2025) Nonconvex stochastic optimization under heavy-tailed noises: optimal convergence without gradient clipping. In International Conference on Learning Representations, Vol. 2025, p. 92529–92554. Cited by: §2. Z. Liu (2026) Online convex optimization with heavy tails: old algorithms, new regrets, and applications. arXiv preprint arXiv:2508.07473v3. Cited by: §1, §1, §2, Table 1, §3, §4.2, §4.2, 1st item, §7, Lemma 2. B. B. Mandelbrot (2013) Fractals and scaling in finance: discontinuity, concentration, risk. selecta volume e. Springer Science & Business Media. Cited by: §1. A. S. Nemirovski and D. B. Yudin (1983) Problem complexity and method efficiency in optimization. John Wiley & Sons, New York. External Links: ISBN 0-471-10345-4 Cited by: §2. F. Orabona (2019) A modern introduction to online learning. arXiv preprint arXiv:1912.13213. Cited by: §4.5. M. Pedramfar and V. Aggarwal (2026) A generalized approach to online convex optimization. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Cited by: §1. S. Shalev-Shwartz (2012) Online learning and online convex optimization. Foundations and Trends® in Machine Learning 4 (2), p. 107–194. Cited by: §1. U. Simsekli, L. Sagun, and M. Gurbuzbalaban (2019) A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, p. 5827–5837. Cited by: §1. N. M. Vural, L. Yu, K. Balasubramanian, S. Volgushev, and M. A. Erdogdu (2022) Mirror descent strikes again: optimal stochastic convex optimization under infinite noise variance. In Conference on Learning Theory, p. 65–102. Cited by: §2. Y. Yang, K. Lu, and L. Wang (2025) Online distributed optimization with clipped stochastic gradients: high probability bound of regrets. Automatica 182, p. 112525. Cited by: §2, Table 1. J. Zhang and A. Cutkosky (2022) Parameter-free regret in high probability with heavy tails. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2, Table 1. J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. J. Reddi, S. Kumar, and S. Sra (2020) Why are adaptive methods good for attention models?. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §3. L. Zhang, S. Lu, and Z. Zhou (2018) Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §1, §1, §2, Table 1, 2nd item. P. Zhao, Y. Zhang, L. Zhang, and Z. Zhou (2020) Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. P. Zhao, Y. Zhang, L. Zhang, and Z. Zhou (2024) Adaptivity and non-stationarity: problem-dependent dynamic regret for online convex optimization. Journal of Machine Learning Research 25, p. 1–52. Cited by: §1, §2, Table 1. M. Zinkevich (2003) Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning (ICML), Cited by: §1, §1, §2.