The Convergence Behavior of Adam under Heavy-Tailed Noise

# The Convergence Behavior of Adam under Heavy-Tailed Noise
Source: [https://arxiv.org/html/2607.27383](https://arxiv.org/html/2607.27383)
###### Abstract

We establish the first convergence guarantees for the plain vector\-form*Adam*optimizer under heavy\-tailed stochastic noise\. While several Adam variants are known to achieve optimal iteration complexity in bounded\-variance nonconvex optimization, little is understood about their behavior when stochastic gradients admit only a boundedpp\-th central moment for somep∈\(1,2\]p\\in\(1,2\], a setting increasingly observed in modern deep learning\. To address this gap, we generalize the recent online\-to\-nonconvex conversion framework to accommodate heavy\-tailed martingale\-difference noise\. Building on this generalized framework, we develop a discounted regret analysis for Adam, without restrictive parameter coupling\. Our results show that Adam converges to\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationary points under heavy\-tailed noise\. However, it exhibits a suboptimal iteration complexity andpp\-dependent convergence, a suboptimality that persists even in the bounded\-variance case \(p=2p=2\)\. When the domain radius is known and used to control the online\-learner output, a standard setup in related literature, the convergence rate improves to match the optimal complexity\. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy\-tailed regimes\.

## 1Introduction

Adaptive gradient methods, most notably Adam\[kingma2014adam\], have become the de facto optimization tools for training modern deep neural networks\. Despite their remarkable empirical success, the theoretical understanding of Adam\-type algorithms remains incomplete, particularly in stochastic environments where gradient noise deviates from classical bounded\-variance assumptions\.

Recent empirical and theoretical studies\[battash2024revisiting,ahn2023linear,garg2021proximal\]suggest that stochastic gradients in deep learning often exhibit heavy\-tailed behavior\. Instead of satisfying a bounded\-variance condition, the noise may only admit a boundedpp\-th central moment for somep∈\(1,2\]p\\in\(1,2\]\. Such heavy\-tailed phenomena have been observed in large\-scale language model training and other high\-dimensional learning problems\. In these regimes, analyses relying on sub\-Gaussian or bounded\-variance assumptions are no longer applicable, and even classical stochastic gradient descent \(SGD\)\[robbins1951stochastic\]may suffer from instability or divergence\[zhang2020adaptive\]\.

Over the past few years, substantial progress has been made in understanding both non\-adaptive and adaptive methods under heavy\-tailed noise\. Clipped SGD, normalized gradient methods, and sign\-based optimizers have been shown to provide improved robustness in heavy\-tailed settings\[zhang2020adaptive,liu2023breaking,sun2024gradient,he2025complexity\]\. On the adaptive side, recent works analyze clipped or modified variants of AdaGrad and Adam\-type methods and establish \(high\-probability\) convergence guarantees\[chezhegov2024clipping,fradin2025tight\]\. More recently, classical algorithms have been shown to achieve optimal convergence guarantees in convex settings and near\-optimal rates for non\-smooth non\-convex optimization under heavy\-tailed noise\[liu2025online\]\.

Nevertheless, convergence guarantees for the Adam update under heavy\-tailed noise, without algorithmic modification, remain largely unexplored\. In fact, until very recently, rigorous convergence results for Adam\-type methods under heavy\-tailed stochastic gradients were unavailable\[yu2026sign\]\. Even in the bounded\-variance case \(p=2p=2\), many existing analyses focus on simplified or modified variants of Adam rather than the exact algorithm used in practice\.

A major conceptual development in recent years is the online\-to\-nonconvex conversion frameworkcutkosky2023optimal,ahn2024understanding,zhang2024random, which establishes a principled connection between adaptive optimization and online learning\. We briefly recall the fundamental setup\.

Online Linear Optimization \(OLO\) proceeds overTTrounds\. At roundtt, the learner selects𝐳t∈ℝd\{\\mathbf\{z\}\}\_\{t\}\\in\\mathbb\{R\}^\{d\}and then observes a linear lossℓt​\(⋅\):=⟨𝐯t,⋅⟩,\\ell\_\{t\}\(\\cdot\):=\\langle\{\\mathbf\{v\}\}\_\{t\},\\cdot\\rangle,where𝐯t\{\\mathbf\{v\}\}\_\{t\}is a cost vector revealed by the environment\. The goal is to minimize the*static regret*RegretT\(𝐮\):=∑t=1T⟨𝐯t,𝐳t−𝐮⟩,\\mathrm\{Regret\}\_\{T\}\(\{\\mathbf\{u\}\}\):=\\sum\_\{t=1\}^\{T\}\\langle\{\\mathbf\{v\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\-\{\\mathbf\{u\}\}\\rangle,for any comparator𝐮\{\\mathbf\{u\}\}in a domain𝒟\\mathcal\{D\}\. To connect online learning with non\-convex optimization, recent works introduce the notion of*β\\beta\-discounted regret*\. The discounted loss is defined asℓt\[β\]​\(⋅\)=⟨β−t​𝐯t,⋅⟩,\\ell\_\{t\}^\{\[\\beta\]\}\(\\cdot\)=\\langle\\beta^\{\-t\}\{\\mathbf\{v\}\}\_\{t\},\\cdot\\rangle,leading to the discounted regret

RegretT\[β\]​\(𝐮\)=∑t=1T⟨βT−t​𝐯t,𝐳t−𝐮⟩\.\\mathrm\{Regret\}\_\{T\}^\{\[\\beta\]\}\(\{\\mathbf\{u\}\}\)=\\sum\_\{t=1\}^\{T\}\\langle\\beta^\{T\-t\}\{\\mathbf\{v\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\-\{\\mathbf\{u\}\}\\rangle\.
Within this framework, effective nonconvex optimizers correspond to online learners achieving small discounted regret\. This perspective provides structural insight into adaptive methods\. For example, interpreting Adam as a Follow\-the\-Regularized\-Leader \(FTRL\) procedure clarifies its update structure and helps explain its empirical advantages over SGD when problem properties are unknown\[ahn2024adam\]\. Moreover, the conversion framework has enabled sharp iteration complexity results for Adam\. However, existing analyses often rely on technical simplifications, for example, removing bias\-correction terms1/\(1−β1t\)1/\(1\-\\beta\_\{1\}^\{t\}\)and1/\(1−β2t\)1/\(1\-\\beta\_\{2\}^\{t\}\)or imposing parameter couplings such asβ2=β12\\beta\_\{2\}=\\beta\_\{1\}^\{2\}for analytical tractability\. While these assumptions facilitate proof techniques, they depart from the exact algorithm used in practice and partially obscure its intrinsic behavior\. Furthermore, the current conversion framework does not directly accommodate heavy\-tailed noise\.

Given these developments, a central question remains open:

*What convergence guarantees can be established for the Adam update, without restrictive modifications? This question becomes even more compelling in heavy\-tailed settings\.*

#### Our contributions\.

In this work, we provide the first convergence guarantees for the Adam update under heavy\-tailed stochastic noise\. Our main contributions are summarized as follows:

- •Heavy\-tail conversion theory\.We generalize the online\-to\-nonconvex conversion framework to accommodate heavy\-tailed martingale\-difference noise\.
- •Vector\-form Adam regret analysis\.We establish a complete discounted regret analysis for the exact vector\-form Adam update without enforcing restrictive parameter coupling: \(a\) we only requireβ1≤β2\\beta\_\{1\}\\leq\\beta\_\{2\}; \(b\) the numerical stabilizerϵ\\epsilonin Adam’s denominator is treated as a fixed small constant and is not required to scale with eitherGGorσ\\sigma\.
- •Heavy\-tailed nonconvex convergence\.We show that Adam converges to\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationary points under heavy\-tailed noise\. The resulting complexity ispp\-dependent and suboptimal relative to the optimal nonsmooth stochastic rate; this suboptimality remains even in the bounded\-variance casep=2p=2\.
- •Optimal rates under known domain radius\.When the domain radius is known and used to clip the online\-learner output, a standard assumption in related literature, the iteration complexity improves to match optimal rates\.

## 2Related Work

#### Heavy\-tailed stochastic optimization

Heavy\-tailed gradient noise, typically modeled by assuming only a boundedpp\-th central moment for somep∈\(1,2\]p\\in\(1,2\], has been widely studied as a realistic alternative to bounded\-variance assumptions in deep learning\. In non\-adaptive optimization, a large body of work develops robust methods for this regime\.zhang2019gradientanalyzed clipped SGD and established convergence guarantees together with lower bounds under heavy\-tailed noise\.gorbunov2020stochasticandnguyen2023improvedstrengthened these results to high\-probability guarantees and studied accelerated variants\. Beyond explicit clipping,gorbunov2020stochasticandyu2026signanalyzed normalization\-based and sign\-based methods, showing that magnitude suppression can achieve optimal or near\-optimal rates without explicit truncation\. For adaptive methods, theoretical guarantees are comparatively limited\.chezhegov2024clippingstudied clipped AdaGrad\- and Adam\-type algorithms and established high\-probability convergence guarantees under heavy\-tailed noise\.ilboudo2023adatermproposed robust moment estimators based on heavy\-tailed modeling and analyzed their stability\. These works demonstrate that adaptive methods can be made robust in heavy\-tailed regimes, but require explicit algorithmic modifications\.

#### Online\-to\-nonconvex conversion and heavy\-tailed online learning

A major recent development in adaptive optimization is the online\-to\-nonconvex conversion framework\.cutkosky2023optimal,ahn2024understanding,zhang2024random,ahn2024generalconnected nonconvex stationarity guarantees to regret bounds of online learners through discounted regret\. These works established optimal iteration complexity in the bounded\-variance setting for carefully designed online learners with momentum\-type updates\. Parallel to these developments, heavy\-tailed online learning has also been studied\.zhang2022parameterestablished high\-probability regret guarantees via gradient truncation techniques for online convex optimization\.liu2025onlineestablished regret guarantees for classical online convex optimization algorithms without explicit truncation\.

## 3Preliminaries

In this section, we introduce the assumptions and basic notions used throughout the paper\. Our assumptions largely follow prior work on non\-smooth non\-convex stochastic optimization and adaptive methods\[cutkosky2023optimal,ahn2024adam,zhang2024random\], while explicitly allowing only boundedpp\-th moments of the stochastic gradient noise\. We also recall the notion of\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationarity, which serves as the optimality criterion in our analysis\. This notion is standard in recent studies of non\-smooth non\-convex stochastic optimization\[zhang2024random,ahn2024adam,zhang2019gradient,jordan2023deterministic,tian2022finite\]\. Although\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationarity relaxes Goldstein stationarity\[goldstein1977optimization\], it retains sufficient structure to recover first\-order stationarity under additional smoothness assumptions\.

###### Assumption 3\.1\.

LetF:ℝd→ℝF:\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}be a differentiable function with the following properties:

- •Thefunctionis bounded below:inf𝐱F​\(𝐱\)\>−∞\\inf\_\{\{\\mathbf\{x\}\}\}F\(\{\\mathbf\{x\}\}\)\>\-\\infty\. We defineΔ:=F​\(𝐱0\)−inf𝐱F​\(𝐱\)\\Delta:=F\(\{\\mathbf\{x\}\}\_\{0\}\)\-\\inf\_\{\{\\mathbf\{x\}\}\}F\(\{\\mathbf\{x\}\}\)\.
- •ThefunctionF is well\-behaved, i\.e\.,∀𝐱\\forall\{\\mathbf\{x\}\}and𝐲\{\\mathbf\{y\}\},F​\(𝐲\)−F​\(𝐱\)=∫01⟨∇F​\(𝐱\+t​\(𝐲−𝐱\),𝐲−𝐱\)⟩​𝑑tF\(\{\\mathbf\{y\}\}\)\-F\(\{\\mathbf\{x\}\}\)=\\int\_\{0\}^\{1\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\+t\(\{\\mathbf\{y\}\}\-\{\\mathbf\{x\}\}\),\{\\mathbf\{y\}\}\-\{\\mathbf\{x\}\}\)\\rangle dt\.
- •ThefunctionF isGG\-Lipschitz, i\.e\.,∀𝐱,‖∇F​\(𝐱\)‖≤G\\forall\{\\mathbf\{x\}\},\\\|\\nabla F\(\{\\mathbf\{x\}\}\)\\\|\\leq G\.
- •For every query point𝐱\{\\mathbf\{x\}\}, thestochastic gradient𝐠←StoGrad​\(𝐱,r\)\{\\mathbf\{g\}\}\\leftarrow\\mathrm\{StoGrad\}\(\{\\mathbf\{x\}\},r\)satisfies𝔼​\[𝐠∣𝐱\]=∇F​\(𝐱\),𝔼​\[‖𝐠−∇F​\(𝐱\)‖p∣𝐱\]≤σp\.\\mathbb\{E\}\[\{\\mathbf\{g\}\}\\mid\{\\mathbf\{x\}\}\]=\\nabla F\(\{\\mathbf\{x\}\}\),\\quad\\mathbb\{E\}\\\!\\left\[\\\|\{\\mathbf\{g\}\}\-\\nabla F\(\{\\mathbf\{x\}\}\)\\\|^\{p\}\\mid\{\\mathbf\{x\}\}\\right\]\\leq\\sigma^\{p\}\.

###### Definition 3\.2\(\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationary point\)\.

SupposingF:ℝd→ℝF:\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}is differentiable\. Then𝐱\{\\mathbf\{x\}\}is a\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationary point ofFFif‖∇F​\(𝐱\)‖\[ρ\]≤ϵ\\\|\\nabla F\(\{\\mathbf\{x\}\}\)\\\|^\{\[\\rho\]\}\\leq\\epsilonwhere‖∇F​\(𝐱\)‖\[ρ\]:=infp∈𝒫​\(ℝd\),𝔼𝐲∼p​\[𝐲\]=𝐱\{‖𝔼​\[∇F​\(𝐲\)\]‖\+ρ​𝔼​\[‖𝐲−𝐱‖2\]\}\.\\\|\\nabla F\(\{\\mathbf\{x\}\}\)\\\|^\{\[\\rho\]\}:=\\inf\_\{p\\in\\mathcal\{P\}\(\\mathbb\{R\}^\{d\}\),\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\\sim p\}\[\{\\mathbf\{y\}\}\]=\{\\mathbf\{x\}\}\}\\left\\\{\\\|\\mathbb\{E\}\[\\nabla F\(\{\\mathbf\{y\}\}\)\]\\\|\+\\rho\\mathbb\{E\}\[\\\|\{\\mathbf\{y\}\}\-\{\\mathbf\{x\}\}\\\|^\{2\}\]\\right\\\}\.

To facilitate an online\-learning interpretation of Adam, we introduce an equivalent assumption on the cost vectors corresponding to the stochastic gradients in Assumption[3\.1](https://arxiv.org/html/2607.27383#S3.Thmtheorem1)\.

###### Assumption 3\.3\.

For eacht∈\[T\]t\\in\[T\], let𝐯t∈ℝd\{\\mathbf\{v\}\}\_\{t\}\\in\\mathbb\{R\}^\{d\}denote a stochastic cost vector revealed after the historyℱt−1\\mathcal\{F\}\_\{t\-1\}\. Define

𝝁t:=𝔼​\[𝐯t∣ℱt−1\],𝝃t:=𝐯t−𝝁t\.\\bm\{\\mu\}\_\{t\}:=\\mathbb\{E\}\[\{\\mathbf\{v\}\}\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\],\\qquad\\bm\{\\xi\}\_\{t\}:=\{\\mathbf\{v\}\}\_\{t\}\-\\bm\{\\mu\}\_\{t\}\.Assume that, almost surely,

‖𝝁t‖≤G,𝔼​\[‖𝝃t‖p∣ℱt−1\]≤σp,𝔼​\[𝝃t∣ℱt−1\]=0\.\\\|\\bm\{\\mu\}\_\{t\}\\\|\\leq G,\\quad\\mathbb\{E\}\\\!\\left\[\\\|\\bm\{\\xi\}\_\{t\}\\\|^\{p\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\leq\\sigma^\{p\},\\quad\\mathbb\{E\}\\\!\\left\[\\bm\{\\xi\}\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]=0\.

###### Assumption 3\.4\(Ball\-constrained domain\)\.

Let𝒟⊆ℝd\\mathcal\{D\}\\subseteq\\mathbb\{R\}^\{d\}denote the Euclidean ball of radiusD\>0D\>0,𝒟:=\{x∈ℝd:‖x‖≤D\}\.\\mathcal\{D\}:=\\\{x\\in\\mathbb\{R\}^\{d\}:\\\|x\\\|\\leq D\\\}\.Any comparator𝐮∈𝒟\{\\mathbf\{u\}\}\\in\\mathcal\{D\}satisfies‖𝐮‖≤D\\\|\{\\mathbf\{u\}\}\\\|\\leq D\.

Assumption[3\.4](https://arxiv.org/html/2607.27383#S3.Thmtheorem4)is used to specify the comparator class in the online\-learning analysis\.

## 4Discounted\-to\-nonconvex conversion

Algorithm 1Discounted\-to\-nonconvex conversion algorithm\[zhang2024random\]1:Input:Initial point

𝐱0\{\\mathbf\{x\}\}\_\{0\},

TT, online learner

𝒜\\mathcal\{A\}outputting

𝐳\{\\mathbf\{z\}\}, and discounting factor

β∈\(0,1\)\\beta\\in\(0,1\)
2:for

t=1t=1to

TTdo

3:Receive

𝐳t\{\\mathbf\{z\}\}\_\{t\}from

𝒜\\mathcal\{A\}
4:Update

𝐱t←𝐱t−1\+κt​𝐳t\{\\mathbf\{x\}\}\_\{t\}\\leftarrow\{\\mathbf\{x\}\}\_\{t\-1\}\+\\kappa\_\{t\}\{\\mathbf\{z\}\}\_\{t\}, where

κt∼Exp\(1\)\\kappa\_\{t\}\\sim\\text\{Exp\(1\)\}i\.i\.d\.

5:Compute

𝐠t←StoGrad​\(𝐱t,rt\)\{\\mathbf\{g\}\}\_\{t\}\\leftarrow\\text\{StoGrad\}\(\{\\mathbf\{x\}\}\_\{t\},r\_\{t\}\)
6:Send

ℓt\[β\]​\(𝐳t\):=⟨β−t​𝐠t,𝐳t⟩\\ell\_\{t\}^\{\[\\beta\]\}\(\{\\mathbf\{z\}\}\_\{t\}\):=\\langle\\beta^\{\-t\}\{\\mathbf\{g\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\\rangleto

𝒜\\mathcal\{A\}
7:endfor

We now present a generalized discounted\-to\-nonconvex conversion framework that accommodates both heavy\-tailed and bounded\-variance noise\. The results of this section are of independent interest beyond the analysis of Adam\.

To obtain a\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationary point, both components in Definition[3\.2](https://arxiv.org/html/2607.27383#S3.Thmtheorem2)must be controlled: \(i\) the expected gradient norm/smoothed first\-order term‖𝔼​\[∇F​\(𝐲\)\]‖\\\|\\mathbb\{E\}\[\\nabla F\(\{\\mathbf\{y\}\}\)\]\\\|, and \(ii\) the variance term𝔼​\[‖𝐲−𝐱‖2\]\\mathbb\{E\}\[\\\|\{\\mathbf\{y\}\}\-\{\\mathbf\{x\}\}\\\|^\{2\}\]\. We bound these two terms separately\.

### 4\.1Bounding the Two Terms

#### Bounding the expected gradient norm via discounted regret

We first establish a heavy\-tailed analogue of the classical interaction between expected gradient norm and discounted regret\.

The proof follows the standard discounted\-to\-nonconvex conversion argument\[ahn2024adam\], with a key modification to accommodate heavy\-tailed noise\. In particular, we invoke the von Bahr–Esseen inequality for martingale differences\[von1965inequalities\]to control stochastic error terms without assuming bounded variance\. The key result is summarized in Proposition[4\.2](https://arxiv.org/html/2607.27383#S4.Thmtheorem2), together with its supporting Lemma[4\.1](https://arxiv.org/html/2607.27383#S4.Thmtheorem1); the proofs are deferred to Appendix[A](https://arxiv.org/html/2607.27383#A1)\.

###### Lemma 4\.1\.

Suppose Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3)holds\. Then for anyβ∈\(0,1\)\\beta\\in\(0,1\),n∈\[T\]n\\in\[T\], and comparator𝐮n∈𝒟\{\\mathbf\{u\}\}\_\{n\}\\in\\mathcal\{D\},

𝔼​∑t=1nβn−t​⟨𝝃t,𝐮n⟩≤2​\(1−β\)−1p​σ​D\.\\mathbb\{E\}\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\\bm\{\\xi\}\_\{t\},\{\\mathbf\{u\}\}\_\{n\}\\rangle\\leq 2\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D\.

###### Proposition 4\.2\.

SupposeFFsatisfies Assumption[3\.1](https://arxiv.org/html/2607.27383#S3.Thmtheorem1)\. For any comparator sequence\{𝐮t\}⊆𝒟\\\{\{\\mathbf\{u\}\}\_\{t\}\\\}\\subseteq\\mathcal\{D\}, Algorithm[1](https://arxiv.org/html/2607.27383#alg1)

𝔼τ​‖𝔼𝐲τ​∇F​\(𝐲τ\)‖≤2​\(1−β\+βT\)​\(1−β\)−1p​σ\+ΔD​T\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\left\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{\\tau\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{\\tau\}\)\\right\\\|\\leq 2\(1\-\\beta\+\\frac\{\\beta\}\{T\}\)\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma\+\\frac\{\\Delta\}\{DT\}\+1D​T​\(\(1−β\)​∑t=1T𝔼​Regrett\[β\]​\(𝐮t\)\+β​𝔼​RegretT\[β\]​\(𝐮T\)\)\\displaystyle\+\\frac\{1\}\{DT\}\\left\(\(1\-\\beta\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\+\\beta\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\)whereτ\\tauis a random index in\[T\]\[T\]with distributionℙ​\(τ=t\)=\{1−βtTift=1,⋯,T−1,1−βT\(1−β\)​Tift=T\\mathbb\{P\}\(\\tau=t\)=\\begin\{cases\}\\frac\{1\-\\beta^\{t\}\}\{T\}&\\text\{if\}\\quad t=1,\\cdots,T\-1,\\\\ \\frac\{1\-\\beta^\{T\}\}\{\(1\-\\beta\)T\}&\\text\{if\}\\quad t=T\\end\{cases\}\. Moreover,𝐲t\{\\mathbf\{y\}\}\_\{t\}is sampled from\{𝐱s\}s=1t\\\{\{\\mathbf\{x\}\}\_\{s\}\\\}\_\{s=1\}^\{t\}according toℙ​\(𝐲t=𝐱s\)=\(1−β\)​βt−s1−βt,s=1,…,t\\mathbb\{P\}\(\{\\mathbf\{y\}\}\_\{t\}=\{\\mathbf\{x\}\}\_\{s\}\)\\;=\\;\\frac\{\(1\-\\beta\)\\beta^\{t\-s\}\}\{1\-\\beta^\{t\}\},s=1,\\ldots,t\.

Whenp=2p=2, the above result recovers the existing discounted\-to\-nonconvex conversion under bounded variance \(Lemma 7 ofahn2024adam\)\.

#### Bounding the variance term

We now bound the second term in Definition[3\.2](https://arxiv.org/html/2607.27383#S3.Thmtheorem2)\. This result directly adapts existing analyses\[ahn2024general,zhang2024random\]and highlights the role of norm control in achieving optimal guarantees\.

###### Lemma 4\.3\(Lemma 8 ofahn2024general, Lemma 3\.2 ofzhang2024random\)\.

Using the notations of Proposition[4\.2](https://arxiv.org/html/2607.27383#S4.Thmtheorem2)\. Let𝔼​\[𝐲τ\]=𝐱~τ\\mathbb\{E\}\[\{\\mathbf\{y\}\}\_\{\\tau\}\]=\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}, then∀t\\forall t, it holds that

ρ​𝔼τ​𝔼𝐲τ​‖𝐲τ−𝐱~τ‖2\\displaystyle\\rho\\mathbb\{E\}\_\{\\tau\}\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{\\tau\}\}\\\|\{\\mathbf\{y\}\}\_\{\\tau\}\-\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\\\|^\{2\}≤2​ρ​β​supt∈\[T\]𝔼​\[‖𝐳t‖2\]\(1−β\)2\\displaystyle\\leq\\frac\{2\\rho\\beta\\sup\_\{t\\in\[T\]\}\\mathbb\{E\}\\left\[\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}\\right\]\}\{\(1\-\\beta\)^\{2\}\}

Thus, controlling‖𝐳t‖\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|, for example viaDD\-based clipping, directly controls the variance term in the stationarity measure

### 4\.2Optimization guarantee after conversion

Combining Proposition[4\.2](https://arxiv.org/html/2607.27383#S4.Thmtheorem2)and Lemma[4\.3](https://arxiv.org/html/2607.27383#S4.Thmtheorem3), we obtain the following\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationarity guarantee under heavy\-tailed noise:

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]≤2​\(1−β\+βT\)​\(1−β\)−1p​σ\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}\\leq 2\(1\-\\beta\+\\frac\{\\beta\}\{T\}\)\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma\+1D​T​\(\(1−β\)​∑t=1T𝔼​Regrett\[β\]​\(𝐮t\)\+β​𝔼​RegretT\[β\]​\(𝐮T\)\)\\displaystyle\+\\frac\{1\}\{DT\}\\left\(\(1\-\\beta\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\+\\beta\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\)\+ΔD​T\+2​ρ​β​supt∈\[T\]𝔼​\[‖𝐳t‖2\]\(1−β\)2\\displaystyle\\qquad\+\\frac\{\\Delta\}\{DT\}\+\\frac\{2\\rho\\beta\\sup\_\{t\\in\[T\]\}\\mathbb\{E\}\\left\[\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}\\right\]\}\{\(1\-\\beta\)^\{2\}\}\(1\)
From an algorithmic perspective, an effective method should: \(i\) achieve small discounted regret and \(ii\) control the magnitude of𝐳t\{\\mathbf\{z\}\}\_\{t\}\.

With this heavy\-tailed discounted\-to\-nonconvex conversion framework in place, our next focus is to establish a regret analysis for Adam under heavy\-tailed noise\. This constitutes the main technical contribution of the paper\.

Algorithm 2Online learner: Adam \(vector\-form\)1:Input:

β≜β1,β2∈\(0,1\)\\beta\\triangleq\\beta\_\{1\},\\beta\_\{2\}\\in\(0,1\), step\-size sequence

\{αt\}\\\{\\alpha\_\{t\}\\\}, learning\-rate sequence

\{ηt\}t∈\[T\]\\\{\\eta\_\{t\}\\\}\_\{t\\in\[T\]\}, and

ϵ\>0\\epsilon\>0\.

2:for

t=1t=1to

TTdo

3:

𝐳t=arg​min𝐳∈ℝd⁡‖𝐳‖22​αt\+∑s=1t−1⟨β1−s​𝐯s,𝐳⟩=−αt​∑s=1t−1β1−s​𝐯s\{\\mathbf\{z\}\}\_\{t\}=\\operatorname\*\{arg\\,min\}\_\{\{\\mathbf\{z\}\}\\in\\mathbb\{R\}^\{d\}\}\\frac\{\\\|\{\\mathbf\{z\}\}\\\|^\{2\}\}\{2\\alpha\_\{t\}\}\+\\sum\_\{s=1\}^\{t\-1\}\\left\\langle\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\},\\,\{\\mathbf\{z\}\}\\right\\rangle=\-\\alpha\_\{t\}\\sum\_\{s=1\}^\{t\-1\}\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\}\[a,b\]

4:Observe loss

ℓt​\(⋅\)=⟨𝐯t,⋅⟩\\ell\_\{t\}\(\\cdot\)=\\langle\{\\mathbf\{v\}\}\_\{t\},\\cdot\\rangle
5:endfor

\[a\]Selectingαt≜ηt​1−β11−β1t−1​β1t−11−β21−β2t−1​∑s=1t−1β2t−1−s​‖𝐯s‖2\+ϵ\\alpha\_\{t\}\\triangleq\\eta\_\{t\}\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{1\}^\{t\-1\}\}\\frac\{\\beta\_\{1\}^\{t\-1\}\}\{\\sqrt\{\\frac\{1\-\\beta\_\{2\}\}\{1\-\\beta\_\{2\}^\{t\-1\}\}\\sum\_\{s=1\}^\{t\-1\}\\beta\_\{2\}^\{t\-1\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}\+\\epsilon\}, the incremental𝐳t\{\\mathbf\{z\}\}\_\{t\}can be formulated as

𝐳t=−ηt​1−β11−β1t−1​∑s=1t−1β1t−1−s​𝐯s1−β21−β2t−1​∑s=1t−1β2t−1−s​‖𝐯s‖2\+ϵ⇒More familiar Adam updateRolling as EMA\{𝐦t=β1​𝐦t−1\+\(1−β1\)​𝐯t−1vt=β2​vt−1\+\(1−β2\)​‖𝐯t−1‖2𝐳t=−ηt​𝐦t/\(1−β1t−1\)vt/\(1−β2t−1\)\+ϵ\.\\boxed\{\{\\mathbf\{z\}\}\_\{t\}=\-\\eta\_\{t\}\\frac\{\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{1\}^\{t\-1\}\}\\sum\_\{s=1\}^\{t\-1\}\\beta\_\{1\}^\{t\-1\-s\}\{\\mathbf\{v\}\}\_\{s\}\}\{\\sqrt\{\\frac\{1\-\\beta\_\{2\}\}\{1\-\\beta\_\{2\}^\{t\-1\}\}\\sum\_\{s=1\}^\{t\-1\}\\beta\_\{2\}^\{t\-1\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}\+\\epsilon\}\\xRightarrow\[\\text\{More familiar Adam update\}\]\{\\text\{Rolling as EMA\}\}\\begin\{cases\}\{\\mathbf\{m\}\}\_\{t\}=\\beta\_\{1\}\{\\mathbf\{m\}\}\_\{t\-1\}\+\(1\-\\beta\_\{1\}\)\{\\mathbf\{v\}\}\_\{t\-1\}\\\\ v\_\{t\}=\\beta\_\{2\}v\_\{t\-1\}\+\(1\-\\beta\_\{2\}\)\\\|\{\\mathbf\{v\}\}\_\{t\-1\}\\\|^\{2\}\\\\ \{\\mathbf\{z\}\}\_\{t\}=\-\\eta\_\{t\}\\frac\{\{\\mathbf\{m\}\}\_\{t\}/\(1\-\\beta\_\{1\}^\{t\-1\}\)\}\{\\sqrt\{v\_\{t\}/\(1\-\\beta\_\{2\}^\{t\-1\}\)\}\+\\epsilon\}\.\\\\ \\end\{cases\}\}
\[b\]For the notation simplification purpose, we further define

𝐳t≜−ηt​𝐚tbt\+ϵwhere𝐚t=1−β11−β1t−1∑s=1t−1β1t−1−s𝐯s,bt=1−β21−β2t−1∑s=1t−1β2t−1−s∥𝐯s∥2\.\\boxed\{\{\\mathbf\{z\}\}\_\{t\}\\triangleq\-\\frac\{\\eta\_\{t\}\\,\{\\mathbf\{a\}\}\_\{t\}\}\{\\sqrt\{b\_\{t\}\}\+\\epsilon\}\\quad\\text\{where\}\\quad\{\\mathbf\{a\}\}\_\{t\}=\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{1\}^\{t\-1\}\}\\sum\_\{s=1\}^\{t\-1\}\\beta\_\{1\}^\{t\-1\-s\}\{\\mathbf\{v\}\}\_\{s\},\\quad b\_\{t\}=\\frac\{1\-\\beta\_\{2\}\}\{1\-\\beta\_\{2\}^\{t\-1\}\}\\sum\_\{s=1\}^\{t\-1\}\\beta\_\{2\}^\{t\-1\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\.\}

## 5Algorithm: Adam

In this section, we present Adam from an online\-learning perspective\. Algorithm[2](https://arxiv.org/html/2607.27383#alg2)gives an equivalent formulation of Adam as a Follow\-the\-Regularized\-Leader \(FTRL\) procedure with exponentially weighted costs and a quadratic regularizer\. Throughout the paper, we analyze this*vector*version of Adam; an extension to coordinate\-wise variants is discussed later\.

With the choice ofαt\\alpha\_\{t\}in Algorithm[2](https://arxiv.org/html/2607.27383#alg2)\[a\], the output admits the algebraically equivalent form to the standard vector\-form Adam update\. For later use, we adopt the shorthand𝐳t=−ηt​𝐚t/\(bt\+ϵ\)\{\\mathbf\{z\}\}\_\{t\}=\-\\eta\_\{t\}\{\\mathbf\{a\}\}\_\{t\}/\(\\sqrt\{b\_\{t\}\}\+\\epsilon\)defined in Algorithm[2](https://arxiv.org/html/2607.27383#alg2)\[b\]\.

Notation\.We summarize the key quantities used throughout the analysis:

- •𝐳t\{\\mathbf\{z\}\}\_\{t\}: Incremental / output of online learner Adam
- •\{αt\}\\\{\\alpha\_\{t\}\\\}: step\-size sequence
- •\{ηt\}\\\{\\eta\_\{t\}\\\}: learning\-rate sequence

Organization\.This section states three preparatory components used in the discounted regret analysis: heavy\-tail moment controls for Adam’s adaptive denominator and the discounted cost norms that appear in the regret bound, aβ2\\beta\_\{2\}\-selection rule that yields a deterministic bound on‖𝐳t‖\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|, and monotonicity of effective step sizeαt\\alpha\_\{t\}\.

### 5\.1Heavy\-tail control of discounted norms

We next record the heavy\-tail moment controls needed in the regret analysis\. Unlike bounded\-variance analyses, the quantitybt\+1\\sqrt\{b\_\{t\+1\}\}and the discounted norm aggregate∑s=1tβt−s​‖𝐯s‖2\\sqrt\{\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}cannot be bounded by second moments\. The key observation is that their expectations can still be controlled under a boundedpp\-th moment assumption by using the concavity ofxp/2x^\{p/2\}forp≤2p\\leq 2\. The resulting bounds quantify the heavy\-tail cost through the factor\(1−β\)−\(1/p−1/2\)\(1\-\\beta\)^\{\-\(1/p\-1/2\)\}, which is the price of replacing a second\-moment assumption by app\-moment assumption\.

###### Proposition 5\.1\.

Under Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3), for everyt∈\[T\]t\\in\[T\],

𝔼​bt\+1≤G\+σ​\(2p\)1/p​\(1−β2\)−\(1p−12\)\.\\mathbb\{E\}\\sqrt\{b\_\{t\+1\}\}\\leq G\+\\sigma\\left\(\\frac\{2\}\{p\}\\right\)^\{1/p\}\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\.

The proof of Proposition[5\.1](https://arxiv.org/html/2607.27383#S5.Thmtheorem1)is deferred to Appendix[B](https://arxiv.org/html/2607.27383#A2)\.

###### Corollary 5\.2\.

Assume Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3)holds\. Then for anyβ∈\(0,1\)\\beta\\in\(0,1\)andt∈\[T\]t\\in\[T\],

𝔼​∑s=1tβt−s​‖𝐯s‖2\\displaystyle\\mathbb\{E\}\\sqrt\{\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}≤1−βt1−β​\(G\+σ​\(2p\)1/p​\(1−β\)−\(1p−12\)\)\\displaystyle\\qquad\\leq\\sqrt\{\\frac\{1\-\\beta^\{t\}\}\{1\-\\beta\}\}\\left\(G\+\\sigma\\left\(\\frac\{2\}\{p\}\\right\)^\{1/p\}\(1\-\\beta\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)

### 5\.2Deterministic output bounds and effective step size control

In this subsection, we first state a simple parameter condition that yields a deterministic bound on‖𝐳t‖\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|\.

The following proposition \(Proof detailed in Appendix[B](https://arxiv.org/html/2607.27383#A2)\) shows that this mild relation betweenβ1\\beta\_\{1\}andβ2\\beta\_\{2\}implies a deterministic norm bound for Adam’s output, which will be crucial for our in\-expectation analysis\.

###### Proposition 5\.4\.

Under Remark[5\.3](https://arxiv.org/html/2607.27383#S5.Thmtheorem3), Adam’s output satisfies the deterministic bound‖𝐳t‖≤ηt​C​\(β\),∀t≥1\.\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|\\;\\leq\\;\\eta\_\{t\}\\sqrt\{C\(\\beta\)\},\\qquad\\forall t\\geq 1\.

It is also worth noting that Remark[5\.3](https://arxiv.org/html/2607.27383#S5.Thmtheorem3)and Proposition[5\.4](https://arxiv.org/html/2607.27383#S5.Thmtheorem4)allowC​\(β\)C\(\\beta\)to be small, or even equal to 1 whenβ2=β1\\beta\_\{2\}=\\beta\_\{1\}

Additionally, the following Proposition[5\.5](https://arxiv.org/html/2607.27383#S5.Thmtheorem5)records the natural monotonicity of the resulting effective step size\. Throughout the paper, we take a constant base step size, i\.e\.,ηt≡η\\eta\_\{t\}\\equiv\\eta\.

###### Proposition 5\.5\.

Letβ1≤β2\\beta\_\{1\}\\leq\\beta\_\{2\}, useηs=η\\eta\_\{s\}=\\eta, and initializeα1:=α2\\alpha\_\{1\}:=\\alpha\_\{2\}\. Thenαs=η​\(1−β1\)​β1s−1\(1−β1s−1\)​\(bs\+ϵ\),s≥2\\alpha\_\{s\}=\\frac\{\\eta\(1\-\\beta\_\{1\}\)\\beta\_\{1\}^\{s\-1\}\}\{\(1\-\\beta\_\{1\}^\{s\-1\}\)\(\\sqrt\{b\_\{s\}\}\+\\epsilon\)\},s\\geq 2, is non\-increasing:αs≥αs\+1\\alpha\_\{s\}\\geq\\alpha\_\{s\+1\}for alls≥1s\\geq 1\.

## 6Regret and Optimization Guarantees

This section presents our main performance guarantees for Adam under heavy\-tailed noise\. We first establish a discounted regret bound for the Adam online learner\. We then combine this regret bound with the heavy\-tailed discounted\-to\-nonconvex conversion \(Section[4](https://arxiv.org/html/2607.27383#S4)\) to obtain convergence guarantees to\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationary points\. Finally, we show how the guarantee improves when the domain radiusDDis available to the algorithm and is used to control the online\-learner output\.

### 6\.1Discounted Regret under Heavy Tails

We analyze Adam as an online learner receiving discounted linear losses and producing increments𝐳t\{\\mathbf\{z\}\}\_\{t\}as in Algorithm[2](https://arxiv.org/html/2607.27383#alg2)\. The comparator radiusDDspecifies the regret benchmark; in the Adam result,DDis not used to modify the algorithm\. Our goal is to bound the discounted regret

𝔼​\[Regrett\[β\]​\(𝐮\)\]=𝔼​\[∑s=1t⟨β1t−s​𝐯s,𝐳s−𝐮⟩\]\.\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]=\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\langle\\beta\_\{1\}^\{t\-s\}\{\\mathbf\{v\}\}\_\{s\},\\,\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{u\}\}\\rangle\\right\]\.The result of the regret bound under heavy\-tailed noise is summarized in Theorem[6\.2](https://arxiv.org/html/2607.27383#S6.Thmtheorem2), together with its supporting Proposition[6\.1](https://arxiv.org/html/2607.27383#S6.Thmtheorem1)\.

###### Proposition 6\.1\.

Under Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3), fort≥T0:=2\+log⁡\(1/\(1−β1\)\)log⁡\(β2/β1\)t\\geq T\_\{0\}:=2\+\\frac\{\\log\(1/\(1\-\\beta\_\{1\}\)\)\}\{\\log\(\\sqrt\{\\beta\_\{2\}\}/\\beta\_\{1\}\)\}, it holds that

𝔼​\[∑s=1tαs2​β1t−2​s​‖𝐯¯s‖2\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{t\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\\right\]≤η​2​β2​\(1−β1\)β1​\(1−β2\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\\displaystyle\\qquad\\leq\\eta\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)where𝐯¯s:=clip∑n=1s−1β22​s−2​n​‖𝐯n‖2​\(𝐯s\)\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}:=\\mathrm\{clip\}\_\{\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{2s\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\}\(\{\\mathbf\{v\}\}\_\{s\}\)\.

The proof of Proposition[6\.1](https://arxiv.org/html/2607.27383#S6.Thmtheorem1)is deferred to Appendix[C](https://arxiv.org/html/2607.27383#A3)\.

###### Theorem 6\.2\.

Assume Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3)holds, and employ theβ2,C​\(β\)\\beta\_\{2\},C\(\\beta\)selection strategy in Remark[5\.3](https://arxiv.org/html/2607.27383#S5.Thmtheorem3)\. For anyt≥T0t\\geq T\_\{0\}and any comparator𝐮∈𝒟\{\\mathbf\{u\}\}\\in\\mathcal\{D\}with‖𝐮‖≤D\\\|\{\\mathbf\{u\}\}\\\|\\leq D, if the online learner is Adam withη=D\(1−β1\)1/4\\eta=\\frac\{D\}\{\(1\-\\beta\_\{1\}\)^\{1/4\}\}, then the discounted regret satisfies

𝔼​\[Regrett\[β\]​\(𝐮\)\]≤C​\(R\)​D​\(G\+2​σ​\(1−β2\)−\(1p−12\)\+ϵ\)\(1−β1\)3/4\.\\mathbb\{E\}\\left\[\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]\\leq\\frac\{C\(R\)D\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\+\\epsilon\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{3/4\}\}\.whereC​\(R\):=max⁡\(12\+2​β2​\(1−β1\)3/2β1​\(1−β2\)\+8​C​\(β\),12\+2​β2​\(1−β1\)β1​\(1−β2\)\+8\)C\(R\):=\\max\\big\(\\frac\{1\}\{2\}\+\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)^\{3/2\}\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\sqrt\{8C\(\\beta\)\},\\frac\{1\}\{2\}\+\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\sqrt\{8\}\\big\)\.

###### Proof\.

We first establish the deterministic intermediate regret bound in equation[6\.1](https://arxiv.org/html/2607.27383#S6.Ex33), inspired by techniques presented inorabona2019modern,ahn2024adam,ahn2024understanding,Tim2021Why, and then control each component appearing in this bound\.

#### Part 1\. Intermediate result \(deterministic bound\) forRegrett\[β\]​\(𝐮\)\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\.

DefineFs​\(𝐳\):=12​αs​‖𝐳‖2\+∑n=1s−1⟨β1−n​𝐯n,𝐳⟩F\_\{s\}\(\{\\mathbf\{z\}\}\):=\\frac\{1\}\{2\\alpha\_\{s\}\}\\\|\{\\mathbf\{z\}\}\\\|^\{2\}\+\\sum\_\{n=1\}^\{s\-1\}\\langle\\beta\_\{1\}^\{\-n\}\{\\mathbf\{v\}\}\_\{n\},\{\\mathbf\{z\}\}\\rangleandαs:=ηs​\(1−β1\)​β1s−1\(1−β1s−1\)​\(bs\+ϵ\)\\alpha\_\{s\}:=\\eta\_\{s\}\\frac\{\(1\-\\beta\_\{1\}\)\\beta\_\{1\}^\{s\-1\}\}\{\(1\-\\beta\_\{1\}^\{s\-1\}\)\(\\sqrt\{b\_\{s\}\}\+\\epsilon\)\}, so

𝐳s=arg​min⁡Fs​\(𝐳\)=−αs​∑n=1s−1β1−n​𝐯n\{\\mathbf\{z\}\}\_\{s\}=\\operatorname\*\{arg\\,min\}F\_\{s\}\(\{\\mathbf\{z\}\}\)=\-\\alpha\_\{s\}\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{1\}^\{\-n\}\{\\mathbf\{v\}\}\_\{n\}is the Adam update\.

Using∑\(Fs​\(𝐳s\)−Fs\+1​\(𝐳s\+1\)\)=F1​\(𝐳1\)−Ft\+1​\(𝐳t\+1\)\\sum\(F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\}\)\-F\_\{s\+1\}\(\{\\mathbf\{z\}\}\_\{s\+1\}\)\)=F\_\{1\}\(\{\\mathbf\{z\}\}\_\{1\}\)\-F\_\{t\+1\}\(\{\\mathbf\{z\}\}\_\{t\+1\}\),F1​\(𝐳1\)=min𝐱⁡12​α1​‖𝐱‖2F\_\{1\}\(\{\\mathbf\{z\}\}\_\{1\}\)=\\min\_\{\{\\mathbf\{x\}\}\}\\frac\{1\}\{2\\alpha\_\{1\}\}\\\|\{\\mathbf\{x\}\}\\\|^\{2\}, andFt\+1​\(𝐳t\+1\)≤Ft\+1​\(𝐮\)F\_\{t\+1\}\(\{\\mathbf\{z\}\}\_\{t\+1\}\)\\leq F\_\{t\+1\}\(\{\\mathbf\{u\}\}\):

∑s=1t⟨β1−s​𝐯s,𝐳s−𝐮⟩\\displaystyle\\sum\_\{s=1\}^\{t\}\\langle\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{u\}\}\\rangle≤‖𝐮‖22​αt\+1\+∑s=1t\[Fs​\(𝐳s\)−Fs\+1​\(𝐳s\+1\)\+⟨β1−s​𝐯s,𝐳s⟩⏟Term B\]\.\\displaystyle\\qquad\\leq\\frac\{\\\|\{\\mathbf\{u\}\}\\\|^\{2\}\}\{2\\alpha\_\{t\+1\}\}\+\\sum\_\{s=1\}^\{t\}\\left\[\\underbrace\{F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\}\)\-F\_\{s\+1\}\(\{\\mathbf\{z\}\}\_\{s\+1\}\)\+\\langle\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\\rangle\}\_\{\\text\{Term B\}\}\\right\]\.
UsingFs​\(𝐳s\+1\)−Fs\+1​\(𝐳s\+1\)=−⟨β1−s​𝐯s,𝐳s\+1⟩\+12​αs​‖𝐳s\+1‖2−12​αs\+1​‖𝐳s\+1‖2F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\+1\}\)\-F\_\{s\+1\}\(\{\\mathbf\{z\}\}\_\{s\+1\}\)=\-\\langle\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\+1\}\\rangle\+\\frac\{1\}\{2\\alpha\_\{s\}\}\\\|\{\\mathbf\{z\}\}\_\{s\+1\}\\\|^\{2\}\-\\frac\{1\}\{2\\alpha\_\{s\+1\}\}\\\|\{\\mathbf\{z\}\}\_\{s\+1\}\\\|^\{2\}andαs≥αs\+1\\alpha\_\{s\}\\geq\\alpha\_\{s\+1\}\(Proposition[5\.5](https://arxiv.org/html/2607.27383#S5.Thmtheorem5)\),

Term B≤Fs​\(𝐳s\)−Fs​\(𝐳s\+1\)\+⟨β1−s​𝐯s,𝐳s−𝐳s\+1⟩\\displaystyle\\leq F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\}\)\-F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\+1\}\)\+\\langle\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\rangle=Fs​\(𝐳s\)−Fs​\(𝐳s\+1\)\+⟨β1−s​𝐯¯s,𝐳s−𝐳s\+1⟩⏟B\.1\\displaystyle=\\underbrace\{F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\}\)\-F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\+1\}\)\+\\langle\\beta\_\{1\}^\{\-s\}\\overline\{\{\\mathbf\{v\}\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\rangle\}\_\{\\text\{B\.1\}\}\+⟨β1−s​𝐯s−β1−s​𝐯¯s,𝐳s−𝐳s\+1⟩⏟B\.2\\displaystyle\\qquad\+\\underbrace\{\\langle\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\}\-\\beta\_\{1\}^\{\-s\}\\overline\{\{\\mathbf\{v\}\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\rangle\}\_\{\\text\{B\.2\}\}where𝐯¯s:=clip∑n=1s−1β22​s−2​n​‖𝐯n‖2​\(𝐯s\)\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}:=\\text\{clip\}\_\{\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{2s\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\}\(\{\\mathbf\{v\}\}\_\{s\}\)\.

#### Term B\.1:

- •Fs​\(𝐳s\)−Fs​\(𝐳s\+1\)≤−‖𝐳s−𝐳s\+1‖22​αsF\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\}\)\-F\_\{s\}\(\{\\mathbf\{z\}\}\_\{s\+1\}\)\\leq\-\\frac\{\\\|\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\\|^\{2\}\}\{2\\alpha\_\{s\}\}by strong convexity and the variational inequality for the minimizer𝐳s=arg​min⁡Fs​\(𝐳\)\{\\mathbf\{z\}\}\_\{s\}=\\operatorname\*\{arg\\,min\}F\_\{s\}\(\{\\mathbf\{z\}\}\)\. \(R1\)
- •Employing Young’s inequality,⟨β1−s​𝐯¯s,𝐳s−𝐳s\+1⟩≤αs2​β1−2​s​‖𝐯¯s‖2\+‖𝐳s−𝐳s\+1‖22​αs\\langle\\beta\_\{1\}^\{\-s\}\\overline\{\{\\mathbf\{v\}\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\rangle\\leq\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\+\\frac\{\\\|\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\\|^\{2\}\}\{2\\alpha\_\{s\}\}\. \(R2\)

Combining \(R1\)\+\(R2\):Term B\.1≤αs2​β1−2​s​‖𝐯¯s‖2\\text\{Term B\.1 \}\\leq\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\.

#### Term B\.2:

∑s=1tβ1−s​⟨𝐯s−𝐯¯s,𝐳s−𝐳s\+1⟩⏟Part B\.2\\displaystyle\\underbrace\{\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{\-s\}\\langle\{\\mathbf\{v\}\}\_\{s\}\-\\overline\{\{\\mathbf\{v\}\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\rangle\}\_\{\\text\{Part B\.2\}\}≤∑s=1tβ1−s​‖𝐯s−clip∑n=1s−1β22​s−2​n​‖𝐯n‖2​\(𝐯s\)‖​‖𝐳s−𝐳s\+1‖\\displaystyle\\leq\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\-\\text\{clip\}\_\{\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{2s\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\}\(\{\\mathbf\{v\}\}\_\{s\}\)\\\|\\\|\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{z\}\}\_\{s\+1\}\\\|≤\(a\)2​maxs∈\[t\]⁡‖𝐳s‖​∑s=1tβ1−s​\(‖𝐯s‖−∑n=1s−1β22​s−2​n​‖𝐯n‖2\)\+\\displaystyle\\stackrel\{\{\\scriptstyle\(a\)\}\}\{\{\\leq\}\}2\\max\_\{s\\in\[t\]\}\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{\-s\}\\left\(\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|\-\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{2s\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\\right\)\_\{\+\}≤\(b\)2​maxs∈\[t\]⁡‖𝐳s‖​∑s=1t\(β1−s​‖𝐯s‖−∑n=1s−1β1−2​n​‖𝐯n‖2\)\+\\displaystyle\\stackrel\{\{\\scriptstyle\(b\)\}\}\{\{\\leq\}\}2\\max\_\{s\\in\[t\]\}\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\sum\_\{s=1\}^\{t\}\\left\(\\beta\_\{1\}^\{\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|\-\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{1\}^\{\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\\right\)\_\{\+\}≤2​maxs∈\[t\]⁡‖𝐳s‖​∑s=1t\(∑n=1sβ1−2​n​‖𝐯n‖2−∑n=1s−1β1−2​n​‖𝐯n‖2\)\\displaystyle\\leq 2\\max\_\{s\\in\[t\]\}\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\sum\_\{s=1\}^\{t\}\\left\(\\sqrt\{\\sum\_\{n=1\}^\{s\}\\beta\_\{1\}^\{\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\-\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{1\}^\{\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\\right\)≤2​maxs∈\[t\]⁡‖𝐳s‖​∑s=1tβ1−2​s​‖𝐯s‖2,\\displaystyle\\leq 2\\max\_\{s\\in\[t\]\}\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\sqrt\{\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{\-2s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\},where\(a\)\(a\)uses the identity‖𝐯−clipR​\(𝐯\)‖=\(‖𝐯‖−R\)\+\\\|\{\\mathbf\{v\}\}\-\\mathrm\{clip\}\_\{R\}\(\{\\mathbf\{v\}\}\)\\\|=\(\\\|\{\\mathbf\{v\}\}\\\|\-R\)\_\{\+\}, and\(b\)\(b\)usesβ1≤β2\\beta\_\{1\}\\leq\\beta\_\{2\}\.

Combining the results of Term B\.1 and Term B\.2, it suffices to have

∑s=1t⟨β1−s​𝐯s,𝐳s−𝐮⟩\\displaystyle\\sum\_\{s=1\}^\{t\}\\langle\\beta\_\{1\}^\{\-s\}\{\\mathbf\{v\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{u\}\}\\rangle≤‖𝐮‖22​αt\+1\+∑s=1tαs2​β1−2​s​‖𝐯¯s‖2\\displaystyle\\leq\\frac\{\\\|\{\\mathbf\{u\}\}\\\|^\{2\}\}\{2\\alpha\_\{t\+1\}\}\+\\sum\_\{s=1\}^\{t\}\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\+2​maxs∈\[t\]⁡‖𝐳s‖​∑s=1tβ1−2​s​‖𝐯s‖2\.\\displaystyle\\qquad\+2\\max\_\{s\\in\[t\]\}\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\sqrt\{\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{\-2s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}\.Multiplyingβ1t\\beta\_\{1\}^\{t\}on both sides gives

Regrett\[β\]​\(𝐮\)\\displaystyle\\mathrm\{Regret\}\_\{t\}^\{\[\\beta\]\}\(\{\\mathbf\{u\}\}\)≤β1t​‖𝐮‖22​αt\+1\+∑s=1tαs2​β1t−2​s​‖𝐯¯s‖2\\displaystyle\\leq\\frac\{\\beta\_\{1\}^\{t\}\\\|\{\\mathbf\{u\}\}\\\|^\{2\}\}\{2\\alpha\_\{t\+1\}\}\+\\sum\_\{s=1\}^\{t\}\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{t\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\+2​maxs∈\[t\]⁡‖𝐳s‖​∑s=1tβ12​t−2​s​‖𝐯s‖2\\displaystyle\\quad\+2\\max\_\{s\\in\[t\]\}\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\sqrt\{\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{2t\-2s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}\(2\)where𝐯¯s:=clip∑n=1s−1β22​s−2​n​‖𝐯n‖2​\(𝐯s\)\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}:=\\mathrm\{clip\}\_\{\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{2s\-2n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\}\(\{\\mathbf\{v\}\}\_\{s\}\)\.

#### Part 2\. Final regret bound\.

Taking expectation over equation[6\.1](https://arxiv.org/html/2607.27383#S6.Ex33),

𝔼​\[Regrett\[β\]​\(𝐮\)\]\\displaystyle\\mathbb\{E\}\\left\[\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]≤D22​η​\(1−β1\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\\displaystyle\\leq\\frac\{D^\{2\}\}\{2\\eta\(1\-\\beta\_\{1\}\)\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\+η​2​β2​\(1−β1\)β1​\(1−β2\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\\displaystyle\\qquad\+\\eta\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\+2​η​C​\(β\)​11−β12​\(G\+2​σ​\(1−β12\)−\(1p−12\)\)\\displaystyle\\qquad\+2\\eta\\sqrt\{C\(\\beta\)\}\\sqrt\{\\frac\{1\}\{1\-\\beta\_\{1\}^\{2\}\}\}\\left\(G\+2\\sigma\(1\-\\beta\_\{1\}^\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)Here, the first term on the right\-hand side uses Proposition[5\.1](https://arxiv.org/html/2607.27383#S5.Thmtheorem1), the second term uses Proposition[6\.1](https://arxiv.org/html/2607.27383#S6.Thmtheorem1), and the last term uses Corollary[5\.2](https://arxiv.org/html/2607.27383#S5.Thmtheorem2)and the deterministic increment bound in Proposition[5\.4](https://arxiv.org/html/2607.27383#S5.Thmtheorem4)\.

The above inequality can be further reformulated as

𝔼​\[Regrett\[β\]​\(𝐮\)\]\\displaystyle\\mathbb\{E\}\\left\[\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]≤\(D22​η​\(1−β1\)\+η​2​β2​\(1−β1\)β1​\(1−β2\)\+η​C​\(β\)​81−β1\)\\displaystyle\\leq\\left\(\\frac\{D^\{2\}\}\{2\\eta\(1\-\\beta\_\{1\}\)\}\+\\eta\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\eta\\sqrt\{C\(\\beta\)\}\\sqrt\{\\frac\{8\}\{1\-\\beta\_\{1\}\}\}\\right\)×\(G\+2​σ​\(1−β2\)−\(1p−12\)\+ϵ\)\.\\displaystyle\\qquad\\times\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\+\\epsilon\\right\)\.\(3\)Settingη=D\(1−β1\)1/4\\eta=\\frac\{D\}\{\(1\-\\beta\_\{1\}\)^\{1/4\}\}gives

𝔼​\[Regrett\[β\]​\(𝐮\)\]\\displaystyle\\mathbb\{E\}\\left\[\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]≤D​\(G\+2​σ​\(1−β2\)−\(1p−12\)\+ϵ\)\(1−β1\)3/4\\displaystyle\\leq\\frac\{D\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\+\\epsilon\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{3/4\}\}×\(12\+2​β2​\(1−β1\)3/2β1​\(1−β2\)\+8​C​\(β\)\),\\displaystyle\\quad\\times\\left\(\\frac\{1\}\{2\}\+\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)^\{3/2\}\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\sqrt\{8C\(\\beta\)\}\\right\),which concludes the proof\. ∎

Next, we consider the regret bound when the learner output is explicitly controlled by the known radiusDD\.

###### Corollary 6\.3\.

Assume Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3)holds\. If the learner is the constrained\-FTRL form of Adam over the ball\{‖𝐳‖≤D\}\\\{\\\|\{\\mathbf\{z\}\}\\\|\\leq D\\\}, equivalently the Adam increment is clipped as𝐳←clipD​\(𝐳\)\{\\mathbf\{z\}\}\\leftarrow\\mathrm\{clip\}\_\{D\}\(\{\\mathbf\{z\}\}\), andη=D1−β1\\eta=\\frac\{D\}\{\\sqrt\{1\-\\beta\_\{1\}\}\}, then

𝔼​\[Regrett\[β\]​\(𝐮\)\]≤C​\(R\)​D​\(G\+2​σ​\(1−β2\)−\(1p−12\)\+ϵ\)1−β1\.\\mathbb\{E\}\\left\[\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]\\leq\\frac\{C\(R\)D\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\+\\epsilon\\right\)\}\{\\sqrt\{1\-\\beta\_\{1\}\}\}\.whereC​\(R\):=max⁡\(12\+2​β2​\(1−β1\)3/2β1​\(1−β2\)\+8​C​\(β\),12\+2​β2​\(1−β1\)β1​\(1−β2\)\+8\)C\(R\):=\\max\\big\(\\frac\{1\}\{2\}\+\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)^\{3/2\}\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\sqrt\{8C\(\\beta\)\},\\frac\{1\}\{2\}\+\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\sqrt\{8\}\\big\)\.

###### Proof\.

For the clipped method,𝐳s\{\\mathbf\{z\}\}\_\{s\}is the FTRL minimizer over the ball\{‖𝐳‖≤D\}\\\{\\\|\{\\mathbf\{z\}\}\\\|\\leq D\\\}, which is equivalent to clipping the unconstrained Adam increment\. The same decomposition as in Part 1 of Theorem[6\.2](https://arxiv.org/html/2607.27383#S6.Thmtheorem2)applies, and we begin from equation[6\.1](https://arxiv.org/html/2607.27383#S6.Ex38)but substitute deterministic increment bound termη​C​\(β\)\\eta\\sqrt\{C\(\\beta\)\}asDD

𝔼​\[Regrett\[β\]​\(𝐮\)\]\\displaystyle\\mathbb\{E\}\\left\[\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]≤\(D22​η​\(1−β1\)\+η​2​β2​\(1−β1\)β1​\(1−β2\)\+81−β1​D\)\\displaystyle\\leq\\left\(\\frac\{D^\{2\}\}\{2\\eta\(1\-\\beta\_\{1\}\)\}\+\\eta\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\sqrt\{\\frac\{8\}\{1\-\\beta\_\{1\}\}\}D\\right\)×\(G\+2​σ​\(1−β2\)−\(1p−12\)\+ϵ\)\.\\displaystyle\\qquad\\times\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\+\\epsilon\\right\)\.Settingη=D1−β1\\eta=\\frac\{D\}\{\\sqrt\{1\-\\beta\_\{1\}\}\}gives

𝔼​\[Regrett\[β\]​\(𝐮\)\]\\displaystyle\\mathbb\{E\}\\left\[\\text\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\)\\right\]≤D​\(G\+2​σ​\(1−β2\)−\(1p−12\)\+ϵ\)1−β1\\displaystyle\\leq\\frac\{D\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\+\\epsilon\\right\)\}\{\\sqrt\{1\-\\beta\_\{1\}\}\}×\(12\+2​β2​\(1−β1\)β1​\(1−β2\)\+8\)\.\\displaystyle\\qquad\\times\\left\(\\frac\{1\}\{2\}\+\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\+\\sqrt\{8\}\\right\)\.This concludes the proof\. ∎

In the stationarity results below,ϵ\\epsilondenotes the target accuracy\. The numerical stabilizer in the Adam denominator is treated as a fixed small constant and is omitted from the displayed convergence rates to avoid overloading notation\.

### 6\.2Convergence Guarantee under Heavy Tails

We now combine the discounted regret bound \(Theorem[6\.2](https://arxiv.org/html/2607.27383#S6.Thmtheorem2)\) with the heavy\-tailed discounted\-to\-nonconvex conversion \(Section[4](https://arxiv.org/html/2607.27383#S4)\) to obtain a\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationarity guarantee for Adam\. At a high level, the conversion inequality equation[4\.2](https://arxiv.org/html/2607.27383#S4.Ex8)mainly involves two terms: \(i\) a regret term, and \(ii\) a variance term controlled bysupt𝔼​‖𝐳t‖2\\sup\_\{t\}\\mathbb\{E\}\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}\. Theorem[6\.2](https://arxiv.org/html/2607.27383#S6.Thmtheorem2)controls \(i\), Proposition[5\.4](https://arxiv.org/html/2607.27383#S5.Thmtheorem4)controls \(ii\), and we choose\(β1,D,T\)\(\\beta\_\{1\},D,T\)to balance all contributions\.

###### Theorem 6\.4\.

AssumeFFsatisfies Assumption[3\.1](https://arxiv.org/html/2607.27383#S3.Thmtheorem1)and fix anyρ\>0\\rho\>0\. Run Algorithm[1](https://arxiv.org/html/2607.27383#alg1)with online learner Adam as in Algorithm[2](https://arxiv.org/html/2607.27383#alg2)\. Then, for anyp∈\(43,2\]p\\in\(\\frac\{4\}\{3\},2\], there exists a random indexτ∈\[T\]\\tau\\in\[T\]such that

𝔼τ​\[‖∇F​\(𝐱~τ\)‖\[ρ\]\]≤\(8\+C​\(R\)\+2​C​\(R\)​C​\(β\)1p−12\)​ϵ,\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\left\[\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}\\right\]\\leq\\left\(8\+C\(R\)\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\right\)\\epsilon,whereτ\\tauis a random index among\[T\]\[T\]such thatℙ​\(τ=t\)=\{1−β1tTift=1,⋯,T−1,1−β1T\(1−β1\)​Tift=T\\mathbb\{P\}\(\\tau=t\)=\\begin\{cases\}\\frac\{1\-\\beta\_\{1\}^\{t\}\}\{T\}&\\text\{if\}\\quad t=1,\\cdots,T\-1,\\\\ \\frac\{1\-\\beta\_\{1\}^\{T\}\}\{\(1\-\\beta\_\{1\}\)T\}&\\text\{if\}\\quad t=T\\end\{cases\}\. Moreover, the𝐲t\{\\mathbf\{y\}\}\_\{t\}is randomly distributed over\{𝐱s\}s=1t\\\{\{\\mathbf\{x\}\}\_\{s\}\\\}\_\{s=1\}^\{t\}asℙ​\(𝐲t=𝐱s\)=\(1−β1\)​β1t−s1−β1t,s=1,…,t\\mathbb\{P\}\(\{\\mathbf\{y\}\}\_\{t\}=\{\\mathbf\{x\}\}\_\{s\}\)\\;=\\;\\frac\{\(1\-\\beta\_\{1\}\)\\beta\_\{1\}^\{t\-s\}\}\{1\-\\beta\_\{1\}^\{t\}\},s=1,\\ldots,t\.

In particular, it suffices to choose:

β1=1−\(ϵG\+σ\)4​p3​p−4\\beta\_\{1\}=1\-\\left\(\\frac\{\\epsilon\}\{G\+\\sigma\}\\right\)^\{\\frac\{4p\}\{3p\-4\}\},β2\\beta\_\{2\}so that1−β1=C​\(β\)​\(1−β2\)1\-\\beta\_\{1\}=C\(\\beta\)\(1\-\\beta\_\{2\}\)for a fixed constantC​\(β\)≥1C\(\\beta\)\\geq 1,D=\(1−β1\)5/4​ϵ1/2C​\(β\)​ρ1/2D=\\frac\{\(1\-\\beta\_\{1\}\)^\{5/4\}\\epsilon^\{1/2\}\}\{C\(\\beta\)\\rho^\{1/2\}\}, and

T=𝒪​\(max⁡\{\(C​\(R\)​G\+σ\)8​p−43​p−4​ϵ−8​p−43​p−4​log⁡G\+σϵ,Δ​ρ12​\(C​\(R\)​G\+σ\)5​p3​p−4​ϵ−\(5​p3​p−4\+32\)\}\)T=\\mathcal\{O\}\\Big\(\\max\\Big\\\{\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{8p\-4\}\{3p\-4\}\}\\epsilon^\{\-\\frac\{8p\-4\}\{3p\-4\}\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\},\\\\ \\Delta\\rho^\{\\frac\{1\}\{2\}\}\(C\(R\)G\+\\sigma\)^\{\\frac\{5p\}\{3p\-4\}\}\\epsilon^\{\-\\left\(\\frac\{5p\}\{3p\-4\}\+\\frac\{3\}\{2\}\\right\)\}\\Big\\\}\\Big\)\.

Moreover, in the special casep=2p=2, the bound further reduces toT=𝒪​\(max⁡\{\(C​\(R\)​G\+σ\)6​ϵ−6​log⁡G\+σϵ,Δ​ρ12​\(C​\(R\)​G\+σ\)5​ϵ−132\}\)T=\\mathcal\{O\}\\Big\(\\max\\Big\\\{\\left\(C\(R\)G\+\\sigma\\right\)^\{6\}\\epsilon^\{\-6\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\},\\\\ \\Delta\\rho^\{\\frac\{1\}\{2\}\}\(C\(R\)G\+\\sigma\)^\{5\}\\epsilon^\{\-\\frac\{13\}\{2\}\}\\Big\\\}\\Big\)\.

For readability, the full max\-form conditions onTT, including lower\-order and burn\-in terms, and the proof of Theorem[6\.4](https://arxiv.org/html/2607.27383#S6.Thmtheorem4), are given in Appendix[C](https://arxiv.org/html/2607.27383#A3)\.

#### Discussion of rates\.

Theorem[6\.4](https://arxiv.org/html/2607.27383#S6.Thmtheorem4)implies that Adam converges in expectation to a\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationary with an𝒪​\(ϵ−3\)\\mathcal\{O\}\\left\(\\epsilon^\{\-3\}\\right\)gap compared to the optimal rate under the same framework\[zhang2024random,liu2025online\], in the bounded\-variance casep=2p=2\. This provides a rigorous convergence guarantee for the*plain*Adam update, albeit at a sub\-optimal rate\.

### 6\.3Guarantee with known domain radius

In this case, we use the constrained\-FTRL version of Adam over\{‖𝐳‖≤D\}\\\{\\\|\{\\mathbf\{z\}\}\\\|\\leq D\\\}, equivalently clipping the online\-learner output as𝐳t←clipD​\(𝐳t\)\{\\mathbf\{z\}\}\_\{t\}\\leftarrow\\mathrm\{clip\}\_\{D\}\(\{\\mathbf\{z\}\}\_\{t\}\)\. This directly controls the variance term in the conversion bound and improves the overall iteration complexity\.

###### Corollary 6\.5\.

Use the same notation and assumptions as in Theorem[6\.4](https://arxiv.org/html/2607.27383#S6.Thmtheorem4)\. Suppose the Adam online learner is run in constrained form over\{‖𝐳‖≤D\}\\\{\\\|\{\\mathbf\{z\}\}\\\|\\leq D\\\}, equivalently replacing𝐳t\{\\mathbf\{z\}\}\_\{t\}byclipD​\(𝐳t\)\\mathrm\{clip\}\_\{D\}\(\{\\mathbf\{z\}\}\_\{t\}\)in the conversion algorithm\. Then, for anyp∈\(1,2\]p\\in\(1,2\], the method guarantees a\(ρ,𝒪​\(ϵ\)\)\(\\rho,\\mathcal\{O\}\(\\epsilon\)\)\-stationary point when choosing

β1=1−\(ϵG\+σ\)pp−1\\beta\_\{1\}=1\-\\left\(\\frac\{\\epsilon\}\{G\+\\sigma\}\\right\)^\{\\frac\{p\}\{p\-1\}\},β2\\beta\_\{2\}so that1−β1=C​\(β\)​\(1−β2\)1\-\\beta\_\{1\}=C\(\\beta\)\(1\-\\beta\_\{2\}\)for a fixed constantC​\(β\)≥1C\(\\beta\)\\geq 1,D=\(1−β1\)​ϵ1/2ρ1/2D=\\frac\{\(1\-\\beta\_\{1\}\)\\epsilon^\{1/2\}\}\{\\rho^\{1/2\}\}, and

T=𝒪​\(max⁡\{\(G\+σ\)pp−1\+1​ϵ−\(pp−1\+1\)​log⁡G\+σϵ,Δ​ρ12​\(C​\(R\)​G\+σ\)pp−1​ϵ−\(pp−1\+32\)\}\)T=\\mathcal\{O\}\\Big\(\\max\\Big\\\{\\left\(G\+\\sigma\\right\)^\{\\frac\{p\}\{p\-1\}\+1\}\\epsilon^\{\-\\left\(\\frac\{p\}\{p\-1\}\+1\\right\)\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\},\\\\ \\Delta\\rho^\{\\frac\{1\}\{2\}\}\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{p\}\{p\-1\}\}\\epsilon^\{\-\\left\(\\frac\{p\}\{p\-1\}\+\\frac\{3\}\{2\}\\right\)\}\\Big\\\}\\Big\)\.

Moreover, in the special casep=2p=2, the bound further reduces toT=𝒪​\(max⁡\{\(G\+σ\)3​ϵ−3​log⁡G\+σϵ,Δ​ρ12​\(G\+σ\)2​ϵ−72\}\)T=\\mathcal\{O\}\\Big\(\\max\\Big\\\{\\left\(G\+\\sigma\\right\)^\{3\}\\epsilon^\{\-3\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\},\\\\ \\Delta\\rho^\{\\frac\{1\}\{2\}\}\(G\+\\sigma\)^\{2\}\\epsilon^\{\-\\frac\{7\}\{2\}\}\\Big\\\}\\Big\)\.

The proof of Corollary[6\.5](https://arxiv.org/html/2607.27383#S6.Thmtheorem5)is deferred to Appendix[C](https://arxiv.org/html/2607.27383#A3)\.

## 7Conclusion and Discussion

In this work, we established convergence guarantees for Adam under heavy\-tailed noise\. Our analysis proceeds by \(i\) extending the discounted\-to\-nonconvex conversion framework to heavy\-tailed martingale\-difference noise, and \(ii\) developing a discounted regret analysis for exact vector\-form Adam\. Together, these ingredients yield\(ρ,ϵ\)\(\\rho,\\epsilon\)\-stationarity guarantees under only boundedpp\-th moments\. For plain Adam, the current analysis applies forp\>4/3p\>4/3and gives the leading exponent5​p3​p−4\+32\\frac\{5p\}\{3p\-4\}\+\\frac\{3\}\{2\}in the target accuracy\. When the domain radius is known and used to control the online\-learner output, the exponent improves to the optimal heavy\-tail ratepp−1\+32\\frac\{p\}\{p\-1\}\+\\frac\{3\}\{2\}for allp∈\(1,2\]p\\in\(1,2\]\. In particular, forp=2p=2, the plain\-Adam bound scales as𝒪​\(ϵ−13/2\)\\mathcal\{O\}\(\\epsilon^\{\-13/2\}\), whereas the known\-radius version scales as𝒪​\(ϵ−7/2\)\\mathcal\{O\}\(\\epsilon^\{\-7/2\}\)\.

#### On the selection ofβ2\\beta\_\{2\}and numerical stabilizer\.

Our regret analysis uses a mild relation betweenβ1\\beta\_\{1\}andβ2\\beta\_\{2\}\(β1≤β2\\beta\_\{1\}\\leq\\beta\_\{2\}in Remark[5\.3](https://arxiv.org/html/2607.27383#S5.Thmtheorem3)\), written as1−β11−β2≤C​\(β\)\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{2\}\}\\leq C\(\\beta\), to obtain deterministic control of the Adam increment\. This condition allowsC​\(β\)C\(\\beta\)to be a small constant and does not require the restrictive coupling\. The numerical stabilizer in Adam’s denominator is treated as a fixed small constant and is not required to scale with eitherGGorσ\\sigma\.

#### An open question\.

Corollary[6\.5](https://arxiv.org/html/2607.27383#S6.Thmtheorem5)shows that explicit norm control of the increment suffices to close the optimality gap, yielding optimal iteration complexity\. This raises a natural question:*Can the plain Adam update, or a closely related variant such as AdamW, without access toDDfor output clipping, still attain optimal convergence rates under heavy\-tailed noise?*Answering this question would clarify whether explicit norm control is fundamentally necessary, or merely an artifact of the current analytical techniques\.

## References

Supplementary Material

## Appendix AMissing Proofs of Section[4](https://arxiv.org/html/2607.27383#S4)

See[4\.1](https://arxiv.org/html/2607.27383#S4.Thmtheorem1)

###### Proof\.

Using‖𝐮n‖≤D\\\|\{\\mathbf\{u\}\}\_\{n\}\\\|\\leq Dand Cauchy–Schwarz, we have

∑t=1nβn−t​⟨𝝃t,𝐮n⟩=⟨∑t=1nβn−t​𝝃t,𝐮n⟩≤D​‖∑t=1nβn−t​𝝃t‖\.\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\\bm\{\\xi\}\_\{t\},\{\\mathbf\{u\}\}\_\{n\}\\rangle=\\Bigl\\langle\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\bm\{\\xi\}\_\{t\},\\ \{\\mathbf\{u\}\}\_\{n\}\\Bigr\\rangle\\leq D\\Bigl\\\|\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\bm\{\\xi\}\_\{t\}\\Bigr\\\|\.Taking expectation and applying Jensen’s inequality \(sincex↦xpx\\mapsto x^\{p\}is convex forp≥1p\\geq 1\) yields

𝔼​∑t=1nβn−t​⟨𝝃t,𝐮n⟩\\displaystyle\\mathbb\{E\}\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\\bm\{\\xi\}\_\{t\},\{\\mathbf\{u\}\}\_\{n\}\\rangle≤D​𝔼​\[‖∑t=1nβn−t​𝝃t‖\]≤D​\(𝔼​\[‖∑t=1nβn−t​𝝃t‖p\]\)1/p\.\\displaystyle\\leq D\\,\\mathbb\{E\}\\left\[\\Bigl\\\|\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\bm\{\\xi\}\_\{t\}\\Bigr\\\|\\right\]\\leq D\\Biggl\(\\mathbb\{E\}\\left\[\\Bigl\\\|\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\bm\{\\xi\}\_\{t\}\\Bigr\\\|^\{p\}\\right\]\\Biggr\)^\{1/p\}\.\(R1\)
We now bound thepp\-moment of the weighted sum using the unbiasedness condition𝔼​\[𝝃t∣ℱt−1\]=𝟎\\mathbb\{E\}\[\\bm\{\\xi\}\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=\\mathbf\{0\}andp∈\(1,2\]p\\in\(1,2\]\. Define𝐝t≜βn−t​𝝃t\{\\mathbf\{d\}\}\_\{t\}\\triangleq\\beta^\{n\-t\}\\bm\{\\xi\}\_\{t\}\. Sinceβn−t\\beta^\{n\-t\}is deterministic,𝔼​\[𝐝t∣ℱt−1\]=βn−t​𝔼​\[𝝃t∣ℱt−1\]=𝟎\\mathbb\{E\}\[\{\\mathbf\{d\}\}\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=\\beta^\{n\-t\}\\mathbb\{E\}\[\\bm\{\\xi\}\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=\\mathbf\{0\}, so\{𝐝t,ℱt\}\\\{\{\\mathbf\{d\}\}\_\{t\},\\mathcal\{F\}\_\{t\}\\\}is a martingale\-difference sequence\.

By a von Bahr–Esseen type inequality for martingale differences forp∈\(1,2\]p\\in\(1,2\]\[von1965inequalities,pinelis2015best\], there exists a constantCp≤2C\_\{p\}\\leq 2such that

𝔼​‖∑t=1nβn−t​𝝃t‖p=𝔼​‖∑t=1n𝐝t‖p\\displaystyle\\mathbb\{E\}\\Bigl\\\|\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\bm\{\\xi\}\_\{t\}\\Bigr\\\|^\{p\}=\\mathbb\{E\}\\Bigl\\\|\\sum\_\{t=1\}^\{n\}\{\\mathbf\{d\}\}\_\{t\}\\Bigr\\\|^\{p\}≤Cp​∑t=1n𝔼​‖𝐝t‖p=Cp​∑t=1nβp​\(n−t\)​𝔼​‖𝝃t‖p\\displaystyle\\leq C\_\{p\}\\sum\_\{t=1\}^\{n\}\\mathbb\{E\}\\\|\{\\mathbf\{d\}\}\_\{t\}\\\|^\{p\}=C\_\{p\}\\sum\_\{t=1\}^\{n\}\\beta^\{p\(n\-t\)\}\\,\\mathbb\{E\}\\\|\\bm\{\\xi\}\_\{t\}\\\|^\{p\}≤Cp​σp​∑k=0n−1βp​k≤Cp​σp1−βp≤Cp​σp1−β\.\\displaystyle\\leq C\_\{p\}\\,\\sigma^\{p\}\\sum\_\{k=0\}^\{n\-1\}\\beta^\{pk\}\\leq\\frac\{C\_\{p\}\\,\\sigma^\{p\}\}\{1\-\\beta^\{p\}\}\\leq\\frac\{C\_\{p\}\\,\\sigma^\{p\}\}\{1\-\\beta\}\.\(R2\)
Combining \(R1\) and \(R2\) gives

𝔼​∑t=1nβn−t​⟨𝝃t,𝐮n⟩\\displaystyle\\mathbb\{E\}\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\\bm\{\\xi\}\_\{t\},\{\\mathbf\{u\}\}\_\{n\}\\rangle≤D⋅Cp1/p​σ\(1−βp\)1/p≤D⋅Cp1/p​σ\(1−β\)1/p≤2​\(1−β\)−1/p​σ​D,\\displaystyle\\leq D\\cdot\\frac\{C\_\{p\}^\{1/p\}\\sigma\}\{\(1\-\\beta^\{p\}\)^\{1/p\}\}\\leq D\\cdot\\frac\{C\_\{p\}^\{1/p\}\\sigma\}\{\(1\-\\beta\)^\{1/p\}\}\\leq 2\(1\-\\beta\)^\{\-1/p\}\\sigma D,where the last inequality usesCp≤2C\_\{p\}\\leq 2\. ∎

###### Lemma A\.1\.

Forβ∈\(0,1\)\\beta\\in\(0,1\), consider the iterates generated as per[1](https://arxiv.org/html/2607.27383#alg1)\. Then,∀n∈\[T\]\\forall n\\in\[T\], we have

𝔼​\[∑t=1nβn−t​\(F​\(𝐱t\)−F​\(𝐱t−1\)\)\]≤−D​1−βn1−β​𝔼​‖𝔼𝐲n​∇F​\(𝐲n\)‖\+2​\(1−β\)−1p​σ​D\+𝔼​Regretn\[β\]​\(𝐮n\),\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\bigl\(F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\)\\right\]\\leq\-D\\frac\{1\-\\beta^\{n\}\}\{1\-\\beta\}\\mathbb\{E\}\\Bigl\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{n\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{n\}\)\\Bigr\\\|\+2\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D\+\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{n\}\(\{\\mathbf\{u\}\}\_\{n\}\),where𝐲n\{\\mathbf\{y\}\}\_\{n\}is randomly distributed over\{𝐱t\}t=1n\\\{\{\\mathbf\{x\}\}\_\{t\}\\\}\_\{t=1\}^\{n\}asℙ​\(𝐲n=𝐱t\)=\(1−β\)​βn−t1−βn,t=1,…,n\\mathbb\{P\}\(\{\\mathbf\{y\}\}\_\{n\}=\{\\mathbf\{x\}\}\_\{t\}\)\\;=\\;\\frac\{\(1\-\\beta\)\\beta^\{n\-t\}\}\{1\-\\beta^\{n\}\},t=1,\\ldots,n\.

###### Proof\.

Following the fact about exponential random variable, Lemma 3\.1 inzhang2024random,𝔼​\[F​\(𝐱t\)−F​\(𝐱t−1\)\]=𝔼​⟨∇F​\(𝐱t\),𝐳t⟩\\mathbb\{E\}\\bigl\[F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\]=\\mathbb\{E\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\),\{\\mathbf\{z\}\}\_\{t\}\\rangle:

𝔼​\[F​\(𝐱t\)−F​\(𝐱t−1\)\]\\displaystyle\\mathbb\{E\}\\bigl\[F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\]=𝔼​⟨∇F​\(𝐱t\),𝐳t⟩\\displaystyle=\\mathbb\{E\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\),\{\\mathbf\{z\}\}\_\{t\}\\rangle=𝔼​⟨∇F​\(𝐱t\),𝐮n⟩\+𝔼​⟨∇F​\(𝐱t\)−𝐠t,𝐳t−𝐮n⟩\+𝔼​⟨𝐠t,𝐳t−𝐮n⟩\\displaystyle=\\mathbb\{E\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\),\{\\mathbf\{u\}\}\_\{n\}\\rangle\+\\mathbb\{E\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\-\{\\mathbf\{g\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\-\{\\mathbf\{u\}\}\_\{n\}\\rangle\+\\mathbb\{E\}\\langle\{\\mathbf\{g\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\-\{\\mathbf\{u\}\}\_\{n\}\\rangle=𝔼​⟨∇F​\(𝐱t\),𝐮n⟩⏟①\+𝔼​⟨∇F​\(𝐱t\)−𝐠t,−𝐮n⟩⏟②\+𝔼​⟨𝐠t,𝐳t−𝐮n⟩⏟③,\\displaystyle=\\underbrace\{\\mathbb\{E\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\),\{\\mathbf\{u\}\}\_\{n\}\\rangle\}\_\{\\text\{①\}\}\+\\underbrace\{\\mathbb\{E\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\-\{\\mathbf\{g\}\}\_\{t\},\-\{\\mathbf\{u\}\}\_\{n\}\\rangle\}\_\{\\text\{②\}\}\+\\underbrace\{\\mathbb\{E\}\\langle\{\\mathbf\{g\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\-\{\\mathbf\{u\}\}\_\{n\}\\rangle\}\_\{\\text\{③\}\},\(4\)where we used the fact𝔼​⟨∇F​\(𝐱t\)−𝐠t,𝐳t⟩=0\\mathbb\{E\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\-\{\\mathbf\{g\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\\rangle=0for the last equality\.

We bound the three pieces\.

①: Define𝐮n≜−D​∑t=1nβn−t​∇F​\(𝐱t\)‖∑t=1nβn−t​∇F​\(𝐱t\)‖,\{\\mathbf\{u\}\}\_\{n\}\\;\\triangleq\\;\-D\\,\\frac\{\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\}\{\\left\\\|\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\\right\\\|\},then

𝔼​∑t=1nβn−t​⟨∇F​\(𝐱t\),𝐮n⟩\\displaystyle\\mathbb\{E\}\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\),\{\\mathbf\{u\}\}\_\{n\}\\rangle=𝔼​⟨∑t=1nβn−t​∇F​\(𝐱t\),−D​∑t=1nβn−t​∇F​\(𝐱t\)‖∑t=1nβn−t​∇F​\(𝐱t\)‖⟩\\displaystyle=\\mathbb\{E\}\\Bigg\\langle\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\),\\,\-D\\frac\{\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\}\{\\left\\\|\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\\right\\\|\}\\Bigg\\rangle=−D​𝔼​‖∑t=1nβn−t​∇F​\(𝐱t\)‖\\displaystyle=\-D\\mathbb\{E\}\\Bigl\\\|\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\\Bigr\\\|≤−D​1−βn1−β​𝔼​‖𝔼𝐲n​∇F​\(𝐲n\)‖\\displaystyle\\leq\-D\\frac\{1\-\\beta^\{n\}\}\{1\-\\beta\}\\mathbb\{E\}\\Bigl\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{n\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{n\}\)\\Bigr\\\|where the last equality follows by probability conversion: the𝐲n\{\\mathbf\{y\}\}\_\{n\}is randomly distributed over\{𝐱t\}t=1n\\\{\{\\mathbf\{x\}\}\_\{t\}\\\}\_\{t=1\}^\{n\}asℙ​\(𝐲n=𝐱t\)=\(1−β\)​βn−t1−βn,t=1,…,n\\mathbb\{P\}\(\{\\mathbf\{y\}\}\_\{n\}=\{\\mathbf\{x\}\}\_\{t\}\)\\;=\\;\\frac\{\(1\-\\beta\)\\beta^\{n\-t\}\}\{1\-\\beta^\{n\}\},t=1,\\ldots,n\.

②:

𝔼​∑t=1nβn−t​⟨∇F​\(𝐱t\)−𝐠t,−𝐮n⟩=𝔼​∑t=1nβn−t​⟨𝝃t,𝐮n⟩≤2​\(1−β\)−1p​σ​D,\\mathbb\{E\}\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\\nabla F\(\{\\mathbf\{x\}\}\_\{t\}\)\-\{\\mathbf\{g\}\}\_\{t\},\-\{\\mathbf\{u\}\}\_\{n\}\\rangle=\\mathbb\{E\}\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\\bm\{\\xi\}\_\{t\},\{\\mathbf\{u\}\}\_\{n\}\\rangle\\leq 2\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D,where the last inequality uses the result𝔼​∑s=1tβt−s​⟨𝝃s,𝐮⟩≤2​\(1−β\)−1p​σ​D\\mathbb\{E\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\langle\\bm\{\\xi\}\_\{s\},\{\\mathbf\{u\}\}\\rangle\\leq 2\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma Din Lemma[4\.1](https://arxiv.org/html/2607.27383#S4.Thmtheorem1);

③:

𝔼​∑t=1nβn−t​⟨𝐠t,𝐳t−𝐮n⟩=𝔼​Regretn\[β\]​\(𝐮n\)\.\\mathbb\{E\}\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\langle\{\\mathbf\{g\}\}\_\{t\},\{\\mathbf\{z\}\}\_\{t\}\-\{\\mathbf\{u\}\}\_\{n\}\\rangle=\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{n\}\(\{\\mathbf\{u\}\}\_\{n\}\)\.
Combining the results in above three steps gives

𝔼​\[∑t=1nβn−t​\(F​\(𝐱t\)−F​\(𝐱t−1\)\)\]≤−D​1−βn1−β​𝔼​‖𝔼𝐲n​∇F​\(𝐲n\)‖\+2​\(1−β\)−1p​σ​D\+𝔼​Regretn\[β\]​\(𝐮n\),\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{n\}\\beta^\{n\-t\}\\bigl\(F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\)\\right\]\\leq\-D\\frac\{1\-\\beta^\{n\}\}\{1\-\\beta\}\\mathbb\{E\}\\Bigl\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{n\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{n\}\)\\Bigr\\\|\+2\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D\+\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{n\}\(\{\\mathbf\{u\}\}\_\{n\}\),\(5\)which completes the proof\. ∎

See[4\.2](https://arxiv.org/html/2607.27383#S4.Thmtheorem2)

###### Proof\.

We start from a change of summation and telescoping,

∑n=1T∑t=1n\(1−β\)​βn−t​\(F​\(𝐱t\)−F​\(𝐱t−1\)\)\\displaystyle\\sum\_\{n=1\}^\{T\}\\sum\_\{t=1\}^\{n\}\(1\-\\beta\)\\beta^\{n\-t\}\\bigl\(F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\)=F​\(𝐱T\)−F​\(𝐱0\)−∑t=1TβT−t\+1​\(F​\(𝐱t\)−F​\(𝐱t−1\)\)\.\\displaystyle=F\(\{\\mathbf\{x\}\}\_\{T\}\)\-F\(\{\\mathbf\{x\}\}\_\{0\}\)\-\\sum\_\{t=1\}^\{T\}\\beta^\{T\-t\+1\}\\bigl\(F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\)\.Rearranging and usingF​\(𝐱0\)−F​\(𝐱T\)≤ΔF\(\{\\mathbf\{x\}\}\_\{0\}\)\-F\(\{\\mathbf\{x\}\}\_\{T\}\)\\leq\\Deltagives

−Δ≤𝔼​\[∑n=1T∑t=1n\(1−β\)​βn−t​\(F​\(𝐱t\)−F​\(𝐱t−1\)\)⏟A\]\+𝔼​\[∑t=1TβT−t\+1​\(F​\(𝐱t\)−F​\(𝐱t−1\)\)⏟B\]\.\\displaystyle\-\\Delta\\leq\\mathbb\{E\}\\Bigg\[\\underbrace\{\\sum\_\{n=1\}^\{T\}\\sum\_\{t=1\}^\{n\}\(1\-\\beta\)\\beta^\{n\-t\}\\bigl\(F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\)\}\_\{A\}\\Bigg\]\+\\mathbb\{E\}\\Bigg\[\\underbrace\{\\sum\_\{t=1\}^\{T\}\\beta^\{T\-t\+1\}\\bigl\(F\(\{\\mathbf\{x\}\}\_\{t\}\)\-F\(\{\\mathbf\{x\}\}\_\{t\-1\}\)\\bigr\)\}\_\{B\}\\Bigg\]\.\(6\)
Using the result in Lemma[A\.1](https://arxiv.org/html/2607.27383#A1.Thmtheorem1), we have that

−Δ\\displaystyle\-\\Delta≤\(1−β\)∑t=1T\(−D1−βt1−β𝔼∥𝔼𝐲t∇F\(𝐲t\)∥\+2\(1−β\)−1pσD\+𝔼Regrett\[β\]\(𝐮t\),\)\\displaystyle\\leq\(1\-\\beta\)\\sum\_\{t=1\}^\{T\}\\left\(\-D\\frac\{1\-\\beta^\{t\}\}\{1\-\\beta\}\\mathbb\{E\}\\Bigl\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{t\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{t\}\)\\Bigr\\\|\+2\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D\+\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\),\\right\)\+β\(−D1−βT1−β𝔼∥𝔼𝐲T∇F\(𝐲T\)∥\+2\(1−β\)−1pσD\+𝔼RegretT\[β\]\(𝐮T\),\)\\displaystyle\\qquad\+\\beta\\left\(\-D\\frac\{1\-\\beta^\{T\}\}\{1\-\\beta\}\\mathbb\{E\}\\Bigl\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{T\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{T\}\)\\Bigr\\\|\+2\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D\+\\mathbb\{E\}\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\),\\right\)
Rearranging, we obtain

D​∑t=1T\(1−βt\)​𝔼​‖𝔼𝐲t​∇F​\(𝐲t\)‖\+D​β−βT\+11−β​𝔼​‖𝔼𝐲T​∇F​\(𝐲T\)‖\\displaystyle D\\sum\_\{t=1\}^\{T\}\(1\-\\beta^\{t\}\)\\mathbb\{E\}\\Bigl\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{t\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{t\}\)\\Bigr\\\|\+D\\frac\{\\beta\-\\beta^\{T\+1\}\}\{1\-\\beta\}\\mathbb\{E\}\\left\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{T\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{T\}\)\\right\\\|≤\(1−β\)​∑t=1T𝔼​\[Regrett\[β\]​\(𝐮t\)\]\+β​𝔼​\[RegretT\[β\]​\(𝐮T\)\]\+2​\(\(1−β\)​T\+β\)​\(1−β\)−1p​σ​D\+Δ\\displaystyle\\qquad\\leq\(1\-\\beta\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\+\\beta\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\]\+2\(\(1\-\\beta\)T\+\\beta\)\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D\+\\DeltaBy probability conversion over left hand side: since∑t=1T\(1−βt\)\+β−βT\+11−β=T\\sum\_\{t=1\}^\{T\}\(1\-\\beta^\{t\}\)\+\\frac\{\\beta\-\\beta^\{T\+1\}\}\{1\-\\beta\}=T,τ\\tauis a random index among\[T\]\[T\]such thatℙ​\(τ=t\)=\{1−βtTift=1,⋯,T−1,1−βT\(1−β\)​Tift=T\\mathbb\{P\}\(\\tau=t\)=\\begin\{cases\}\\frac\{1\-\\beta^\{t\}\}\{T\}&\\text\{if\}\\quad t=1,\\cdots,T\-1,\\\\ \\frac\{1\-\\beta^\{T\}\}\{\(1\-\\beta\)T\}&\\text\{if\}\\quad t=T\\end\{cases\}\. And, expectations are written as𝔼𝐲τ​\[⋅\]\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{\\tau\}\}\[\\cdot\]since we condition on the trajectory for the conversion analysis, and the only remaining randomness is the sampling of𝐲τ\{\\mathbf\{y\}\}\_\{\\tau\}\. It suffices to have

D​T​𝔼τ​‖𝔼𝐲τ​∇F​\(𝐲τ\)‖≤\(1−β\)​∑t=1T𝔼​\[Regrett\[β\]​\(𝐮t\)\]\+β​𝔼​\[RegretT\[β\]​\(𝐮T\)\]\+2​\(\(1−β\)​T\+β\)​\(1−β\)−1p​σ​D\+Δ\\displaystyle DT\\mathbb\{E\}\_\{\\tau\}\\left\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{\\tau\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{\\tau\}\)\\right\\\|\\leq\(1\-\\beta\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\+\\beta\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\]\+2\(\(1\-\\beta\)T\+\\beta\)\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma D\+\\Delta𝔼τ​‖𝔼𝐲τ​∇F​\(𝐲τ\)‖≤1D​T​\(\(1−β\)​∑t=1T𝔼​\[Regrett\[β\]​\(𝐮t\)\]\+β​𝔼​\[RegretT\[β\]​\(𝐮T\)\]\)\+2​\(1−β\+βT\)​\(1−β\)−1p​σ\+ΔD​T\.\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\left\\\|\\mathbb\{E\}\_\{\{\\mathbf\{y\}\}\_\{\\tau\}\}\\nabla F\(\{\\mathbf\{y\}\}\_\{\\tau\}\)\\right\\\|\\leq\\frac\{1\}\{DT\}\\left\(\(1\-\\beta\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\+\\beta\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\]\\right\)\+2\(1\-\\beta\+\\frac\{\\beta\}\{T\}\)\(1\-\\beta\)^\{\-\\frac\{1\}\{p\}\}\\sigma\+\\frac\{\\Delta\}\{DT\}\.This concludes the proof\. ∎

## Appendix BMissing Proof of Section[5](https://arxiv.org/html/2607.27383#S5)

See[5\.5](https://arxiv.org/html/2607.27383#S5.Thmtheorem5)

###### Proof\.

Letcs:=\(1−β1\)​β1s−1\(1−β1s−1\)​\(bs\+ϵ\),s≥2c\_\{s\}:=\\frac\{\(1\-\\beta\_\{1\}\)\\beta\_\{1\}^\{s\-1\}\}\{\(1\-\\beta\_\{1\}^\{s\-1\}\)\(\\sqrt\{b\_\{s\}\}\+\\epsilon\)\},\\quad s\\geq 2, and setc1:=c2c\_\{1\}:=c\_\{2\}\. Sinceαs=η​cs\\alpha\_\{s\}=\\eta c\_\{s\}, it suffices to provecs≤cs−1c\_\{s\}\\leq c\_\{s\-1\}fors≥3s\\geq 3\. The cases=2s=2holds by initialization\.

Fixs≥3s\\geq 3and setk=s−2k=s\-2\. By bias correction,

bs=ws​bs−1\+\(1−ws\)​‖𝐯s−1‖2,ws=β2​\(1−β2k\)1−β2k\+1,b\_\{s\}=w\_\{s\}b\_\{s\-1\}\+\(1\-w\_\{s\}\)\\\|\{\\mathbf\{v\}\}\_\{s\-1\}\\\|^\{2\},\\quad w\_\{s\}=\\frac\{\\beta\_\{2\}\(1\-\\beta\_\{2\}^\{k\}\)\}\{1\-\\beta\_\{2\}^\{k\+1\}\},hencebs≥ws​bs−1b\_\{s\}\\geq w\_\{s\}b\_\{s\-1\}\. Defineϕk​\(β\):=β​\(1−βk\)1−βk\+1\\phi\_\{k\}\(\\beta\):=\\frac\{\\beta\(1\-\\beta^\{k\}\)\}\{1\-\\beta^\{k\+1\}\}, so thatws=ϕk​\(β2\)w\_\{s\}=\\phi\_\{k\}\(\\beta\_\{2\}\)\.

Usingx\+ϵws​x\+ϵ≤1ws\\frac\{x\+\\epsilon\}\{\\sqrt\{w\_\{s\}\}x\+\\epsilon\}\\leq\\frac\{1\}\{\\sqrt\{w\_\{s\}\}\}forx≥0x\\geq 0,

cscs−1≤β1​\(1−β1k\)1−β1k\+1⋅bs−1\+ϵws​bs−1\+ϵ≤ϕk​\(β1\)ϕk​\(β2\)\.\\frac\{c\_\{s\}\}\{c\_\{s\-1\}\}\\leq\\frac\{\\beta\_\{1\}\(1\-\\beta\_\{1\}^\{k\}\)\}\{1\-\\beta\_\{1\}^\{k\+1\}\}\\cdot\\frac\{\\sqrt\{b\_\{s\-1\}\}\+\\epsilon\}\{\\sqrt\{w\_\{s\}b\_\{s\-1\}\}\+\\epsilon\}\\leq\\frac\{\\phi\_\{k\}\(\\beta\_\{1\}\)\}\{\\sqrt\{\\phi\_\{k\}\(\\beta\_\{2\}\)\}\}\.
It remains to showϕk​\(β1\)2≤ϕk​\(β2\)\\phi\_\{k\}\(\\beta\_\{1\}\)^\{2\}\\leq\\phi\_\{k\}\(\\beta\_\{2\}\)\. Sinceϕk​\(β\)=∑j=1kβj∑j=0kβj=1−1∑j=0kβj\\phi\_\{k\}\(\\beta\)=\\frac\{\\sum\_\{j=1\}^\{k\}\\beta^\{j\}\}\{\\sum\_\{j=0\}^\{k\}\\beta^\{j\}\}=1\-\\frac\{1\}\{\\sum\_\{j=0\}^\{k\}\\beta^\{j\}\}, we have0<ϕk​\(β\)<10<\\phi\_\{k\}\(\\beta\)<1, andϕk\\phi\_\{k\}is increasing on0,10,1\. Thus, usingβ1≤β2\\beta\_\{1\}\\leq\\beta\_\{2\},ϕk​\(β1\)2≤ϕk​\(β1\)≤ϕk​\(β2\)\\phi\_\{k\}\(\\beta\_\{1\}\)^\{2\}\\leq\\phi\_\{k\}\(\\beta\_\{1\}\)\\leq\\phi\_\{k\}\(\\beta\_\{2\}\)\.

hencecs/cs−1≤1c\_\{s\}/c\_\{s\-1\}\\leq 1, socs≤cs−1c\_\{s\}\\leq c\_\{s\-1\}for alls≥2s\\geq 2\. Thereforeαs=η​cs\\alpha\_\{s\}=\\eta c\_\{s\}is non\-increasing\. ∎

See[5\.4](https://arxiv.org/html/2607.27383#S5.Thmtheorem4)

###### Proof\.

Recall that

𝐳t=−ηt​∑s=1t−1w1,t−1,s​𝐯s∑s=1t−1w2,t−1,s​‖𝐯s‖2\+ϵ,\{\\mathbf\{z\}\}\_\{t\}=\-\\eta\_\{t\}\\frac\{\\sum\_\{s=1\}^\{t\-1\}w\_\{1,t\-1,s\}\{\\mathbf\{v\}\}\_\{s\}\}\{\\sqrt\{\\sum\_\{s=1\}^\{t\-1\}w\_\{2,t\-1,s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}\+\\epsilon\},where

w1,t,s:=\(1−β1\)​β1t−s1−β1t,w2,t,s:=\(1−β2\)​β2t−s1−β2t\.w\_\{1,t,s\}:=\\frac\{\(1\-\\beta\_\{1\}\)\\beta\_\{1\}^\{t\-s\}\}\{1\-\\beta\_\{1\}^\{t\}\},\\quad w\_\{2,t,s\}:=\\frac\{\(1\-\\beta\_\{2\}\)\\beta\_\{2\}^\{t\-s\}\}\{1\-\\beta\_\{2\}^\{t\}\}\.
Then discarding theϵ\\epsilonterm, we obtain

‖𝐳t‖2\\displaystyle\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}≤ηt2​‖∑s=1t−1w1,t−1,s​𝐯s‖2∑s=1t−1w2,t−1,s​‖𝐯s‖2≤ηt2​∑s=1t−1w1,t−1,s​‖𝐯s‖2∑s=1t−1w2,t−1,s​‖𝐯s‖2,\\displaystyle\\leq\\eta\_\{t\}^\{2\}\\frac\{\\bigl\\\|\\sum\_\{s=1\}^\{t\-1\}w\_\{1,t\-1,s\}\{\\mathbf\{v\}\}\_\{s\}\\bigr\\\|^\{2\}\}\{\\sum\_\{s=1\}^\{t\-1\}w\_\{2,t\-1,s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}\\leq\\eta\_\{t\}^\{2\}\\frac\{\\sum\_\{s=1\}^\{t\-1\}w\_\{1,t\-1,s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\}\{\\sum\_\{s=1\}^\{t\-1\}w\_\{2,t\-1,s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\}\},where the inequality follows from Jensen’s inequality since∑sw1,t−1,s=1\\sum\_\{s\}w\_\{1,t\-1,s\}=1\.

Rewriting the numerator gives

‖𝐳t‖2≤ηt2​max1≤s≤t−1⁡w1,t−1,sw2,t−1,s\.\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}\\leq\\eta\_\{t\}^\{2\}\\max\_\{1\\leq s\\leq t\-1\}\\frac\{w\_\{1,t\-1,s\}\}\{w\_\{2,t\-1,s\}\}\.A direct computation yields

max1≤s≤t−1⁡w1,t−1,sw2,t−1,s\\displaystyle\\max\_\{1\\leq s\\leq t\-1\}\\frac\{w\_\{1,t\-1,s\}\}\{w\_\{2,t\-1,s\}\}=1−β11−β21−β2t−11−β1t−1max1≤s≤t−1\(β1β2\)t−1−s≤1−β11−β2,\\displaystyle=\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{2\}\}\\frac\{1\-\\beta\_\{2\}^\{t\-1\}\}\{1\-\\beta\_\{1\}^\{t\-1\}\}\\max\_\{1\\leq s\\leq t\-1\}\\Bigl\(\\frac\{\\beta\_\{1\}\}\{\\beta\_\{2\}\}\\Bigr\)^\{t\-1\-s\}\\leq\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{2\}\},
where we usedβ1≤β2\\beta\_\{1\}\\leq\\beta\_\{2\}\. Finally, Remark[5\.3](https://arxiv.org/html/2607.27383#S5.Thmtheorem3)ensures1−β11−β2≤C​\(β\)\.\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{2\}\}\\leq C\(\\beta\)\.

It suffice to have‖𝐳t‖2≤ηt2​C​\(β\)\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}\\leq\\eta\_\{t\}^\{2\}C\(\\beta\)\. Taking square roots completes the proof\. ∎

See[5\.1](https://arxiv.org/html/2607.27383#S5.Thmtheorem1)

###### Proof\.

Recall that

bt\+1=∑s=1tws,t​‖𝐯s‖2,ws,t=1−β21−β2t​β2t−s\.b\_\{t\+1\}=\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|^\{2\},\\qquad w\_\{s,t\}=\\frac\{1\-\\beta\_\{2\}\}\{1\-\\beta\_\{2\}^\{t\}\}\\beta\_\{2\}^\{t\-s\}\.Since𝐯s=𝝁s\+𝝃s\{\\mathbf\{v\}\}\_\{s\}=\\bm\{\\mu\}\_\{s\}\+\\bm\{\\xi\}\_\{s\}, we have

bt\+1=\(∑s=1tws,t​‖𝝁s\+𝝃s‖2\)1/2\.\\sqrt\{b\_\{t\+1\}\}=\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\mu\}\_\{s\}\+\\bm\{\\xi\}\_\{s\}\\\|^\{2\}\\right\)^\{1/2\}\.By the triangle inequality in the product Hilbert space,

bt\+1≤\(∑s=1tws,t​‖𝝁s‖2\)1/2\+\(∑s=1tws,t​‖𝝃s‖2\)1/2\.\\sqrt\{b\_\{t\+1\}\}\\leq\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\mu\}\_\{s\}\\\|^\{2\}\\right\)^\{1/2\}\+\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{2\}\\right\)^\{1/2\}\.Since‖𝝁s‖≤G\\\|\\bm\{\\mu\}\_\{s\}\\\|\\leq Gand∑sws,t=1\\sum\_\{s\}w\_\{s,t\}=1,\(∑s=1tws,t​‖𝝁s‖2\)1/2≤G\.\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\mu\}\_\{s\}\\\|^\{2\}\\right\)^\{1/2\}\\leq G\.Therefore,

𝔼​bt\+1≤G\+𝔼​\(∑s=1tws,t​‖𝝃s‖2\)1/2\.\\mathbb\{E\}\\sqrt\{b\_\{t\+1\}\}\\leq G\+\\mathbb\{E\}\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{2\}\\right\)^\{1/2\}\.By Lyapunov’s inequality,

𝔼​\(∑s=1tws,t​‖𝝃s‖2\)1/2≤\[𝔼​\(∑s=1tws,t​‖𝝃s‖2\)p/2\]1/p\.\\mathbb\{E\}\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{2\}\\right\)^\{1/2\}\\leq\\left\[\\mathbb\{E\}\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{2\}\\right\)^\{p/2\}\\right\]^\{1/p\}\.Becausep/2≤1p/2\\leq 1, the mapx↦xp/2x\\mapsto x^\{p/2\}is subadditive onℝ\+\\mathbb\{R\}\_\{\+\}, and hence

\(∑s=1tws,t​‖𝝃s‖2\)p/2≤∑s=1tws,tp/2​‖𝝃s‖p\.\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{2\}\\right\)^\{p/2\}\\leq\\sum\_\{s=1\}^\{t\}w\_\{s,t\}^\{p/2\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{p\}\.Taking expectations and using𝔼​‖𝝃s‖p≤σp\\mathbb\{E\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{p\}\\leq\\sigma^\{p\}gives

𝔼​\(∑s=1tws,t​‖𝝃s‖2\)p/2≤σp​∑s=1tws,tp/2\.\\mathbb\{E\}\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{2\}\\right\)^\{p/2\}\\leq\\sigma^\{p\}\\sum\_\{s=1\}^\{t\}w\_\{s,t\}^\{p/2\}\.Thus

𝔼​bt\+1≤G\+σ​\(∑s=1tws,tp/2\)1/p\.\\mathbb\{E\}\\sqrt\{b\_\{t\+1\}\}\\leq G\+\\sigma\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}^\{p/2\}\\right\)^\{1/p\}\.
It remains to compute the weight sum\. We have

∑s=1tws,tp/2=\(1−β21−β2t\)p/2​∑s=1tβ2\(t−s\)​p/2=\(1−β21−β2t\)p/2​1−β2t​p/21−β2p/2\.\\sum\_\{s=1\}^\{t\}w\_\{s,t\}^\{p/2\}=\\left\(\\frac\{1\-\\beta\_\{2\}\}\{1\-\\beta\_\{2\}^\{t\}\}\\right\)^\{p/2\}\\sum\_\{s=1\}^\{t\}\\beta\_\{2\}^\{\(t\-s\)p/2\}=\\left\(\\frac\{1\-\\beta\_\{2\}\}\{1\-\\beta\_\{2\}^\{t\}\}\\right\)^\{p/2\}\\frac\{1\-\\beta\_\{2\}^\{tp/2\}\}\{1\-\\beta\_\{2\}^\{p/2\}\}\.Therefore,

𝔼​bt\+1≤G\+σ​\[\(1−β21−β2t\)p/2​1−β2t​p/21−β2p/2\]1/p\.\\mathbb\{E\}\\sqrt\{b\_\{t\+1\}\}\\leq G\+\\sigma\\left\[\\left\(\\frac\{1\-\\beta\_\{2\}\}\{1\-\\beta\_\{2\}^\{t\}\}\\right\)^\{p/2\}\\frac\{1\-\\beta\_\{2\}^\{tp/2\}\}\{1\-\\beta\_\{2\}^\{p/2\}\}\\right\]^\{1/p\}\.Since forq=p/2∈\(0,1\]q=p/2\\in\(0,1\]andx∈\[0,1\]x\\in\[0,1\],1−xq≤\(1−x\)q,1\-x^\{q\}\\leq\(1\-x\)^\{q\},we get1−β2t​p/2\(1−β2t\)p/2≤1\.\\frac\{1\-\\beta\_\{2\}^\{tp/2\}\}\{\(1\-\\beta\_\{2\}^\{t\}\)^\{p/2\}\}\\leq 1\.Hence

\(∑s=1tws,tp/2\)1/p≤\(1−β2\)1/2\(1−β2p/2\)1/p\.\\left\(\\sum\_\{s=1\}^\{t\}w\_\{s,t\}^\{p/2\}\\right\)^\{1/p\}\\leq\\frac\{\(1\-\\beta\_\{2\}\)^\{1/2\}\}\{\(1\-\\beta\_\{2\}^\{p/2\}\)^\{1/p\}\}\.Finally, by concavity ofxp/2x^\{p/2\},1−β2p/2≥p2​\(1−β2\),1\-\\beta\_\{2\}^\{p/2\}\\geq\\frac\{p\}\{2\}\(1\-\\beta\_\{2\}\),so

\(1−β2\)1/2\(1−β2p/2\)1/p≤\(2p\)1/p​\(1−β2\)12−1p\.\\frac\{\(1\-\\beta\_\{2\}\)^\{1/2\}\}\{\(1\-\\beta\_\{2\}^\{p/2\}\)^\{1/p\}\}\\leq\\left\(\\frac\{2\}\{p\}\\right\)^\{1/p\}\(1\-\\beta\_\{2\}\)^\{\\frac\{1\}\{2\}\-\\frac\{1\}\{p\}\}\.The claim follows\. ∎

## Appendix CMissing Proofs of Section[6](https://arxiv.org/html/2607.27383#S6)

See[6\.1](https://arxiv.org/html/2607.27383#S6.Thmtheorem1)

###### Proof\.

The proof consists of three parts\.

#### Part 1\.

We begin with

αs2​β1−2​s​‖𝐯¯s‖2\\displaystyle\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}≤η2​1−β11−β1s−1​1−β2s−11−β2​1β2s​β1−s−1​‖𝐯¯s‖2∑n=1s−1β2−n−1​‖𝐯n‖2\\displaystyle\\leq\\frac\{\\eta\}\{2\}\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{1\}^\{s\-1\}\}\\frac\{\\sqrt\{1\-\\beta\_\{2\}^\{s\-1\}\}\}\{\\sqrt\{1\-\\beta\_\{2\}\}\}\\frac\{1\}\{\\sqrt\{\\beta\_\{2\}^\{s\}\}\}\\frac\{\\beta\_\{1\}^\{\-s\-1\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\}\{\\sqrt\{\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{\-n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\}≤\(a\)η2​1−β11−β1s−1​1−β2s−11−β2​β1−s−1β2−s−1​1β2s​2​β2−s−1​‖𝐯¯s‖2β2−s−1​‖𝐯¯s‖2\+∑n=1s−1β2−n−1​‖𝐯n‖2\\displaystyle\\stackrel\{\{\\scriptstyle\(a\)\}\}\{\{\\leq\}\}\\frac\{\\eta\}\{2\}\\frac\{1\-\\beta\_\{1\}\}\{1\-\\beta\_\{1\}^\{s\-1\}\}\\frac\{\\sqrt\{1\-\\beta\_\{2\}^\{s\-1\}\}\}\{\\sqrt\{1\-\\beta\_\{2\}\}\}\\frac\{\\beta\_\{1\}^\{\-s\-1\}\}\{\\beta\_\{2\}^\{\-s\-1\}\}\\frac\{1\}\{\\sqrt\{\\beta\_\{2\}^\{s\}\}\}\\frac\{\\sqrt\{2\}\\,\\beta\_\{2\}^\{\-s\-1\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\}\{\\sqrt\{\\beta\_\{2\}^\{\-s\-1\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\+\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{\-n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\}≤\(b\)η2​1−β11−β2​1−β2s−11−β1s−1​β1−s−1β2−s−1​1β2s⋅2​2​\(β2−s−1​‖𝐯¯s‖2\+∑n=1s−1β2−n−1​‖𝐯n‖2−∑n=1s−1β2−n−1​‖𝐯n‖2\)\\displaystyle\\stackrel\{\{\\scriptstyle\(b\)\}\}\{\{\\leq\}\}\\frac\{\\eta\}\{2\}\\frac\{1\-\\beta\_\{1\}\}\{\\sqrt\{1\-\\beta\_\{2\}\}\}\\frac\{\\sqrt\{1\-\\beta\_\{2\}^\{s\-1\}\}\}\{1\-\\beta\_\{1\}^\{s\-1\}\}\\frac\{\\beta\_\{1\}^\{\-s\-1\}\}\{\\beta\_\{2\}^\{\-s\-1\}\}\\frac\{1\}\{\\sqrt\{\\beta\_\{2\}^\{s\}\}\}\\cdot 2\\sqrt\{2\}\\Bigl\(\\sqrt\{\\beta\_\{2\}^\{\-s\-1\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\+\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{\-n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\-\\sqrt\{\\textstyle\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{\-n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\\Bigr\)≤η2​1−β11−β2​1−β2s−11−β1s−1​β1−s−1β2−s−1​1β2s⋅2​2​\(∑n=1sβ2−n−1​‖𝐯n‖2−∑n=1s−1β2−n−1​‖𝐯n‖2\)⏟=Qs−Qs−1\\displaystyle\\leq\\frac\{\\eta\}\{2\}\\frac\{1\-\\beta\_\{1\}\}\{\\sqrt\{1\-\\beta\_\{2\}\}\}\\frac\{\\sqrt\{1\-\\beta\_\{2\}^\{s\-1\}\}\}\{1\-\\beta\_\{1\}^\{s\-1\}\}\\frac\{\\beta\_\{1\}^\{\-s\-1\}\}\{\\beta\_\{2\}^\{\-s\-1\}\}\\frac\{1\}\{\\sqrt\{\\beta\_\{2\}^\{s\}\}\}\\cdot 2\\sqrt\{2\}\\underbrace\{\\Bigl\(\\sqrt\{\\textstyle\\sum\_\{n=1\}^\{s\}\\beta\_\{2\}^\{\-n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\-\\sqrt\{\\textstyle\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{\-n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\\Bigr\)\}\_\{=\\;Q\_\{s\}\\,\-\\,Q\_\{s\-1\}\}=2​η​\(1−β1\)​1−β2s−1\(1−β1s−1\)​1−β2​β2s/2\+1β1s\+1⏟=Ps​\(Qs−Qs−1\)\\displaystyle=\\underbrace\{\\sqrt\{2\}\\eta\\,\\frac\{\(1\-\\beta\_\{1\}\)\\sqrt\{1\-\\beta\_\{2\}^\{s\-1\}\}\}\{\(1\-\\beta\_\{1\}^\{s\-1\}\)\\sqrt\{1\-\\beta\_\{2\}\}\}\\,\\frac\{\\beta\_\{2\}^\{s/2\+1\}\}\{\\beta\_\{1\}^\{s\+1\}\}\}\_\{=\\;P\_\{s\}\}\(Q\_\{s\}\-Q\_\{s\-1\}\)where\(a\)\(a\)usesβ2−s−1​‖𝐯¯s‖2≤∑n=1s−1β2s−2​n−1​‖𝐯n‖2≤∑n=1s−1β2−n−1​‖𝐯n‖2\\beta\_\{2\}^\{\-s\-1\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\\leq\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{s\-2n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\\leq\\sum\_\{n=1\}^\{s\-1\}\\beta\_\{2\}^\{\-n\-1\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}, which follows from the definition of𝐯¯s\\overline\{\{\\mathbf\{v\}\}\}\_\{s\};\(b\)\(b\)usesxx\+y≤2​\(x\+y−y\)\\frac\{x\}\{\\sqrt\{x\+y\}\}\\leq 2\(\\sqrt\{x\+y\}\-\\sqrt\{y\}\)forx,y\>0x,y\>0\.

From the result above, we have

∑s=1tαs2​β1t−2​s​‖𝐯¯s‖2≤β1t​\(∑s=1tPs​\(Qs−Qs−1\)\)=β1t​\(Pt​Qt\+∑s=1t−1\(Ps−Ps\+1\)​Qs\)\.\\displaystyle\\sum\_\{s=1\}^\{t\}\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{t\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\\leq\\beta\_\{1\}^\{t\}\\left\(\\sum\_\{s=1\}^\{t\}P\_\{s\}\(Q\_\{s\}\-Q\_\{s\-1\}\)\\right\)=\\beta\_\{1\}^\{t\}\\left\(P\_\{t\}Q\_\{t\}\+\\sum\_\{s=1\}^\{t\-1\}\(P\_\{s\}\-P\_\{s\+1\}\)Q\_\{s\}\\right\)\.

#### Part 2\.

Next, we show that the remainderR​\(t\):=∑s=1t−1\(Ps−Ps\+1\)​QsR\(t\):=\\sum\_\{s=1\}^\{t\-1\}\(P\_\{s\}\-P\_\{s\+1\}\)Q\_\{s\}is non\-positive fort≥T0:=2\+log⁡\(1/\(1−β1\)\)log⁡\(β2/β1\)t\\geq T\_\{0\}:=2\+\\frac\{\\log\(1/\(1\-\\beta\_\{1\}\)\)\}\{\\log\(\\sqrt\{\\beta\_\{2\}\}/\\beta\_\{1\}\)\}\.

#### Part 2\.1\. The sequence\{Ps\}s≥2\\\{P\_\{s\}\\\}\_\{s\\geq 2\}decreases and then increases\.

Extendh​\(s\):=log⁡Psh\(s\):=\\log P\_\{s\}to reals≥2s\\geq 2\. Letλi:=−log⁡βi\\lambda\_\{i\}:=\-\\log\\beta\_\{i\}andτ:=λ1/λ2≥1\\tau:=\\lambda\_\{1\}/\\lambda\_\{2\}\\geq 1\. Then

h′​\(s\)=λ22​\[\(2​τ−1\)\+1ey−1−2​τeτ​y−1\],y:=λ2​\(s−1\)\.h^\{\\prime\}\(s\)=\\frac\{\\lambda\_\{2\}\}\{2\}\\left\[\(2\\tau\-1\)\+\\frac\{1\}\{e^\{y\}\-1\}\-\\frac\{2\\tau\}\{e^\{\\tau y\}\-1\}\\right\],\\qquad y:=\\lambda\_\{2\}\(s\-1\)\.After multiplying by the positive quantity2​\(ey−1\)​\(eτ​y−1\)/λ22\(e^\{y\}\-1\)\(e^\{\\tau y\}\-1\)/\\lambda\_\{2\}, the sign ofh′​\(s\)h^\{\\prime\}\(s\)is the sign of

G​\(y\):=\(2​τ−1\)​\(ey−1\)​\(eτ​y−1\)\+\(eτ​y−1\)−2​τ​\(ey−1\)\.G\(y\):=\(2\\tau\-1\)\(e^\{y\}\-1\)\(e^\{\\tau y\}\-1\)\+\(e^\{\\tau y\}\-1\)\-2\\tau\(e^\{y\}\-1\)\.
To verify the claimed sign pattern, writex=ey≥1x=e^\{y\}\\geq 1\. A direct calculation gives

G′​\(y\)=x​Φ​\(x\),G^\{\\prime\}\(y\)=x\\Phi\(x\),where

Φ​\(x\)=\(2​τ−1\)​\(τ\+1\)​xτ−2​τ​\(τ−1\)​xτ−1−\(4​τ−1\)\.\\Phi\(x\)=\(2\\tau\-1\)\(\\tau\+1\)x^\{\\tau\}\-2\\tau\(\\tau\-1\)x^\{\\tau\-1\}\-\(4\\tau\-1\)\.Moreover,

Φ​\(1\)=−τ<0,Φ​\(x\)→∞,\\Phi\(1\)=\-\\tau<0,\\qquad\\Phi\(x\)\\to\\infty,and

Φ′​\(x\)=τ​xτ−2​\(\(2​τ−1\)​\(τ\+1\)​x−2​\(τ−1\)2\)\>0\(x≥1\),\\Phi^\{\\prime\}\(x\)=\\tau x^\{\\tau\-2\}\\left\(\(2\\tau\-1\)\(\\tau\+1\)x\-2\(\\tau\-1\)^\{2\}\\right\)\>0\\quad\(x\\geq 1\),because

\(2​τ−1\)​\(τ\+1\)−2​\(τ−1\)2=5​τ−3\>0\.\(2\\tau\-1\)\(\\tau\+1\)\-2\(\\tau\-1\)^\{2\}=5\\tau\-3\>0\.ThusG′G^\{\\prime\}has exactly one positive zero\. SinceG​\(0\)=0G\(0\)=0,G′​\(0\)<0G^\{\\prime\}\(0\)<0, andG​\(y\)→∞G\(y\)\\to\\infty, it follows thatGGhas exactly one positive zero\. Henceh′h^\{\\prime\}changes sign once, from negative to positive\.

Thereforehhfirst decreases and then increases on\[2,∞\)\[2,\\infty\)\. Consequently, there exists an integers⋆≥2s\_\{\\star\}\\geq 2such thatPs\+1≥PsP\_\{s\+1\}\\geq P\_\{s\}, we have

Ps\+1<Ps\(2≤s<s⋆\),Ps\+1≥Ps\(s≥s⋆\)\.P\_\{s\+1\}<P\_\{s\}\\quad\(2\\leq s<s\_\{\\star\}\),\\qquad P\_\{s\+1\}\\geq P\_\{s\}\\quad\(s\\geq s\_\{\\star\}\)\.

#### Part 2\.2\.

Write

ρ:=β2β1\>1,CL:=2​η​\(1−β1\)​β2β1\.\\rho:=\\frac\{\\sqrt\{\\beta\_\{2\}\}\}\{\\beta\_\{1\}\}\>1,\\qquad C\_\{L\}:=\\frac\{\\sqrt\{2\}\\eta\(1\-\\beta\_\{1\}\)\\beta\_\{2\}\}\{\\beta\_\{1\}\}\.From the definition ofPsP\_\{s\},

Ps≥CL​ρs,P2=CL​ρ21−β1\.P\_\{s\}\\geq C\_\{L\}\\rho^\{s\},\\qquad P\_\{2\}=\\frac\{C\_\{L\}\\rho^\{2\}\}\{1\-\\beta\_\{1\}\}\.Hencet≥T0t\\geq T\_\{0\}impliesPt≥P2P\_\{t\}\\geq P\_\{2\}\. By the monotonicity pattern established above, this givesPj≤PtP\_\{j\}\\leq P\_\{t\}for all2≤j≤t2\\leq j\\leq t\. Indeed, terms before the turning point are at mostP2P\_\{2\}, while terms after the turning point are nondecreasing and hence at mostPtP\_\{t\}\. Therefore,

∑s=1t−1\(Ps−Ps\+1\)​Qs\\displaystyle\\sum\_\{s=1\}^\{t\-1\}\(P\_\{s\}\-P\_\{s\+1\}\)Q\_\{s\}=−Pt​Qt−1\+∑s=1t−2Ps\+1​\(Qs\+1−Qs\)\\displaystyle=\-P\_\{t\}Q\_\{t\-1\}\+\\sum\_\{s=1\}^\{t\-2\}P\_\{s\+1\}\(Q\_\{s\+1\}\-Q\_\{s\}\)≤−Pt​Qt−1\+Pt​∑s=1t−2\(Qs\+1−Qs\)\\displaystyle\\leq\-P\_\{t\}Q\_\{t\-1\}\+P\_\{t\}\\sum\_\{s=1\}^\{t\-2\}\(Q\_\{s\+1\}\-Q\_\{s\}\)=−Pt​Q1≤0\.\\displaystyle=\-P\_\{t\}Q\_\{1\}\\leq 0\.Thus, fort≥T0t\\geq T\_\{0\},

∑s=1tαs2​β1t−2​s​‖𝐯¯s‖2≤β1t​Pt​Qt\.\\sum\_\{s=1\}^\{t\}\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{t\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\\leq\\beta\_\{1\}^\{t\}P\_\{t\}Q\_\{t\}\.

#### Part 3\.

It remains to bound the expectation of the terminal term\. ExpandingPt​QtP\_\{t\}Q\_\{t\},

β1t​Pt​Qt=2​β2​η​\(1−β1\)β1​1−β2​1−β2t−11−β1t−1​∑n=1tβ2t−n​‖𝐯n‖2\.\\beta\_\{1\}^\{t\}P\_\{t\}Q\_\{t\}=\\frac\{\\sqrt\{2\\beta\_\{2\}\}\\eta\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\\sqrt\{1\-\\beta\_\{2\}\}\}\\frac\{\\sqrt\{1\-\\beta\_\{2\}^\{t\-1\}\}\}\{1\-\\beta\_\{1\}^\{t\-1\}\}\\sqrt\{\\sum\_\{n=1\}^\{t\}\\beta\_\{2\}^\{t\-n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\.By Corollary[5\.2](https://arxiv.org/html/2607.27383#S5.Thmtheorem2),

𝔼​\[∑n=1tβ2t−n​‖𝐯n‖2\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\sqrt\{\\sum\_\{n=1\}^\{t\}\\beta\_\{2\}^\{t\-n\}\\\|\{\\mathbf\{v\}\}\_\{n\}\\\|^\{2\}\}\\right\]≤1−β2t1−β2​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\.\\displaystyle\\leq\\sqrt\{\\frac\{1\-\\beta\_\{2\}^\{t\}\}\{1\-\\beta\_\{2\}\}\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\.Therefore,

𝔼​\[∑s=1tαs2​β1t−2​s​‖𝐯¯s‖2\]≤𝔼​\[β1t​Pt​Qt\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\sum\_\{s=1\}^\{t\}\\frac\{\\alpha\_\{s\}\}\{2\}\\beta\_\{1\}^\{t\-2s\}\\\|\\overline\{\{\\mathbf\{v\}\}\}\_\{s\}\\\|^\{2\}\\right\]\\leq\\mathbb\{E\}\[\\beta\_\{1\}^\{t\}P\_\{t\}Q\_\{t\}\]≤2​β2​η​\(1−β1\)β1​\(1−β2\)​\(1−β2t−1\)​\(1−β2t\)1−β1t−1​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\\displaystyle\\leq\\frac\{\\sqrt\{2\\beta\_\{2\}\}\\eta\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\\frac\{\\sqrt\{\(1\-\\beta\_\{2\}^\{t\-1\}\)\(1\-\\beta\_\{2\}^\{t\}\)\}\}\{1\-\\beta\_\{1\}^\{t\-1\}\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)≤η​2​β2​\(1−β1\)β1​\(1−β2\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\.\\displaystyle\\leq\\eta\\frac\{2\\sqrt\{\\beta\_\{2\}\}\(1\-\\beta\_\{1\}\)\}\{\\beta\_\{1\}\(1\-\\beta\_\{2\}\)\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\.where the last inequality uses \(1\)1−β2t≤2​\(1−β2t−1\)1\-\\beta\_\{2\}^\{t\}\\leq 2\(1\-\\beta\_\{2\}^\{t\-1\}\)fort≥2t\\geq 2; \(2\)1−β2t−11−β1t−1≤1\\frac\{1\-\\beta\_\{2\}^\{t\-1\}\}\{1\-\\beta\_\{1\}^\{t\-1\}\}\\leq 1forβ1≤β2\\beta\_\{1\}\\leq\\beta\_\{2\}\.

This concludes the proof\. ∎

See[6\.4](https://arxiv.org/html/2607.27383#S6.Thmtheorem4)

###### Proof\.

Start from the conversion bound equation[4\.2](https://arxiv.org/html/2607.27383#S4.Ex8)\(withβ=β1\\beta=\\beta\_\{1\}\):

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤1D​T​\(β1​𝔼​\[RegretT\[β\]​\(𝐮T\)\]\+\(1−β1\)​∑t=1T𝔼​\[Regrett\[β\]​\(𝐮t\)\]\)\\displaystyle\\leq\\frac\{1\}\{DT\}\\left\(\\beta\_\{1\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\]\+\(1\-\\beta\_\{1\}\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\\right\)\+2​\(1−β1\+β1T\)​\(1−β1\)−1p​σ\+ΔD​T\+2​ρ​β1​supt∈\[T\]𝔼​\[‖𝐳t‖2\]\(1−β1\)2\.\\displaystyle\\qquad\+2\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\(1\-\\beta\_\{1\}\)^\{\-\\frac\{1\}\{p\}\}\\sigma\+\\frac\{\\Delta\}\{DT\}\+\\frac\{2\\rho\\beta\_\{1\}\\sup\_\{t\\in\[T\]\}\\mathbb\{E\}\\left\[\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}\\right\]\}\{\(1\-\\beta\_\{1\}\)^\{2\}\}\.Let

T0:=2\+log⁡\(1/\(1−β1\)\)log⁡\(β2/β1\),T\_\{0\}:=2\+\\frac\{\\log\(1/\(1\-\\beta\_\{1\}\)\)\}\{\\log\(\\sqrt\{\\beta\_\{2\}\}/\\beta\_\{1\}\)\},whereT0T\_\{0\}is rounded up if necessary\. We assumeβ1<β2\\beta\_\{1\}<\\sqrt\{\\beta\_\{2\}\}, so that the denominator is positive\.

For the firstT0T\_\{0\}rounds, we use a crude bound inferred directly from the regret definition\. Since

‖𝐳s‖≤C​\(β\)​D\(1−β1\)1/4,‖𝐮t‖≤D,\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\leq\\frac\{\\sqrt\{C\(\\beta\)\}D\}\{\(1\-\\beta\_\{1\}\)^\{1/4\}\},\\qquad\\\|\{\\mathbf\{u\}\}\_\{t\}\\\|\\leq D,we have, for anyt<T0t<T\_\{0\},

𝔼​\[Regrett\[β\]​\(𝐮t\)\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]=𝔼​\[∑s=1tβ1t−s​⟨𝐯s,𝐳s−𝐮t⟩\]\\displaystyle=\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{t\-s\}\\langle\{\\mathbf\{v\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{u\}\}\_\{t\}\\rangle\\right\]≤D​\(1\+C​\(β\)​\(1−β1\)−1/4\)​𝔼​\[∑s=1tβ1t−s​‖𝐯s‖\]\.\\displaystyle\\leq D\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{t\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|\\right\]\.By Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3),

𝔼​‖𝐯s‖≤‖𝝁s‖\+𝔼​‖𝝃s‖≤G\+\(𝔼​‖𝝃s‖p\)1/p≤G\+σ\.\\mathbb\{E\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|\\leq\\\|\\bm\{\\mu\}\_\{s\}\\\|\+\\mathbb\{E\}\\\|\\bm\{\\xi\}\_\{s\}\\\|\\leq G\+\\left\(\\mathbb\{E\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{p\}\\right\)^\{1/p\}\\leq G\+\\sigma\.Therefore, summing the firstT0T\_\{0\}rounds inside the conversion bound gives

1−β1D​T​∑t<T0𝔼​\[Regrett\[β\]​\(𝐮t\)\]\\displaystyle\\frac\{1\-\\beta\_\{1\}\}\{DT\}\\sum\_\{t<T\_\{0\}\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]≤1−β1T​\(1\+C​\(β\)​\(1−β1\)−1/4\)​∑t<T0∑s=1tβ1t−s​𝔼​‖𝐯s‖\\displaystyle\\qquad\\leq\\frac\{1\-\\beta\_\{1\}\}\{T\}\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\\sum\_\{t<T\_\{0\}\}\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{t\-s\}\\mathbb\{E\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|=1T​\(1\+C​\(β\)​\(1−β1\)−1/4\)​∑s<T0\(\(1−β1\)​∑t=sT0−1β1t−s\)​𝔼​‖𝐯s‖\\displaystyle\\qquad=\\frac\{1\}\{T\}\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\\sum\_\{s<T\_\{0\}\}\\left\(\(1\-\\beta\_\{1\}\)\\sum\_\{t=s\}^\{T\_\{0\}\-1\}\\beta\_\{1\}^\{t\-s\}\\right\)\\mathbb\{E\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|≤T0T​\(1\+C​\(β\)​\(1−β1\)−1/4\)​\(G\+σ\)\.\\displaystyle\\qquad\\leq\\frac\{T\_\{0\}\}\{T\}\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\(G\+\\sigma\)\.Fort≥T0t\\geq T\_\{0\}, Theorem[6\.2](https://arxiv.org/html/2607.27383#S6.Thmtheorem2)gives

𝔼​\[Regrett\[β\]​\(𝐮t\)\]≤D​C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)3/4\.\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\\leq\\frac\{DC\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{3/4\}\}\.Thus, forT≥T0T\\geq T\_\{0\},

1D​T​\(β1​𝔼​\[RegretT\[β\]​\(𝐮T\)\]\+\(1−β1\)​∑t=1T𝔼​\[Regrett\[β\]​\(𝐮t\)\]\)\\displaystyle\\frac\{1\}\{DT\}\\left\(\\beta\_\{1\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\]\+\(1\-\\beta\_\{1\}\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\\right\)≤\(1−β1\+β1T\)​C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)3/4\\displaystyle\\qquad\\leq\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\\frac\{C\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{3/4\}\}\+T0T​\(1\+C​\(β\)​\(1−β1\)−1/4\)​\(G\+σ\)\.\\displaystyle\\qquad\\quad\+\\frac\{T\_\{0\}\}\{T\}\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\(G\+\\sigma\)\.
Substituting the increment bound from Proposition[5\.4](https://arxiv.org/html/2607.27383#S5.Thmtheorem4)andη=D\(1−β1\)1/4\\eta=\\frac\{D\}\{\(1\-\\beta\_\{1\}\)^\{1/4\}\},

‖𝐳t‖≤C​\(β\)​η=C​\(β\)​D\(1−β1\)1/4,\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|\\leq\\sqrt\{C\(\\beta\)\}\\eta=\\frac\{\\sqrt\{C\(\\beta\)\}D\}\{\(1\-\\beta\_\{1\}\)^\{1/4\}\},and choosingD=\(1−β1\)5/4​ϵ1/2C​\(β\)​ρ1/2,D=\\frac\{\(1\-\\beta\_\{1\}\)^\{5/4\}\\epsilon^\{1/2\}\}\{C\(\\beta\)\\rho^\{1/2\}\},we obtain

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤\(1−β1\+β1T\)​C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)3/4\\displaystyle\\leq\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\\frac\{C\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{3/4\}\}\+T0T​\(1\+C​\(β\)​\(1−β1\)−1/4\)​\(G\+σ\)\\displaystyle\\qquad\+\\frac\{T\_\{0\}\}\{T\}\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\(G\+\\sigma\)\+2​\(1−β1\+β1T\)​\(1−β1\)−1/p​σ\+C​\(β\)​ρ1/2​Δ\(1−β1\)5/4​ϵ1/2​T\+2​ϵ\.\\displaystyle\\qquad\+2\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\(1\-\\beta\_\{1\}\)^\{\-1/p\}\\sigma\+\\frac\{\\sqrt\{C\(\\beta\)\}\\rho^\{1/2\}\\Delta\}\{\(1\-\\beta\_\{1\}\)^\{5/4\}\\epsilon^\{1/2\}T\}\+2\\epsilon\.Expanding the first and third terms gives

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)​\(1−β1\)1/4\+2​σ​\(1−β1\)1−1p\\displaystyle\\leq C\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\(1\-\\beta\_\{1\}\)^\{1/4\}\+2\\sigma\(1\-\\beta\_\{1\}\)^\{1\-\\frac\{1\}\{p\}\}\+C​\(R\)​β1​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)3/4​T\+2​β1​σ\(1−β1\)1/p​T\\displaystyle\\qquad\+\\frac\{C\(R\)\\beta\_\{1\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{3/4\}T\}\+\\frac\{2\\beta\_\{1\}\\sigma\}\{\(1\-\\beta\_\{1\}\)^\{1/p\}T\}\+C​\(β\)​ρ1/2​Δ\(1−β1\)5/4​ϵ1/2​T\+T0T​\(1\+C​\(β\)​\(1−β1\)−1/4\)​\(G\+σ\)\+2​ϵ\.\\displaystyle\\qquad\+\\frac\{\\sqrt\{C\(\\beta\)\}\\rho^\{1/2\}\\Delta\}\{\(1\-\\beta\_\{1\}\)^\{5/4\}\\epsilon^\{1/2\}T\}\+\\frac\{T\_\{0\}\}\{T\}\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\(G\+\\sigma\)\+2\\epsilon\.Hence, using1−β1≤C​\(β\)​\(1−β2\),1\-\\beta\_\{1\}\\leq C\(\\beta\)\(1\-\\beta\_\{2\}\),we have

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤C​\(R\)​G​\(1−β1\)1/4\+2​C​\(R\)​C​\(β\)1p−12​σ​\(1−β1\)34−1p\+2​σ​\(1−β1\)1−1p\\displaystyle\\leq C\(R\)G\(1\-\\beta\_\{1\}\)^\{1/4\}\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\sigma\(1\-\\beta\_\{1\}\)^\{\\frac\{3\}\{4\}\-\\frac\{1\}\{p\}\}\+2\\sigma\(1\-\\beta\_\{1\}\)^\{1\-\\frac\{1\}\{p\}\}\+C​\(R\)​β1​G\(1−β1\)3/4​T\+2​C​\(R\)​C​\(β\)1p−12​β1​σ\(1−β1\)14\+1p​T\+2​β1​σ\(1−β1\)1/p​T\\displaystyle\\qquad\+\\frac\{C\(R\)\\beta\_\{1\}G\}\{\(1\-\\beta\_\{1\}\)^\{3/4\}T\}\+\\frac\{2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\beta\_\{1\}\\sigma\}\{\(1\-\\beta\_\{1\}\)^\{\\frac\{1\}\{4\}\+\\frac\{1\}\{p\}\}T\}\+\\frac\{2\\beta\_\{1\}\\sigma\}\{\(1\-\\beta\_\{1\}\)^\{1/p\}T\}\+C​\(β\)​ρ1/2​Δ\(1−β1\)5/4​ϵ1/2​T\+T0T​\(1\+C​\(β\)​\(1−β1\)−1/4\)​\(G\+σ\)\+2​ϵ\.\\displaystyle\\qquad\+\\frac\{\\sqrt\{C\(\\beta\)\}\\rho^\{1/2\}\\Delta\}\{\(1\-\\beta\_\{1\}\)^\{5/4\}\\epsilon^\{1/2\}T\}\+\\frac\{T\_\{0\}\}\{T\}\\left\(1\+\\sqrt\{C\(\\beta\)\}\(1\-\\beta\_\{1\}\)^\{\-1/4\}\\right\)\(G\+\\sigma\)\+2\\epsilon\.
Now assumep\>43p\>\\frac\{4\}\{3\},0<ϵ≤C​\(R\)​G\+σ0<\\epsilon\\leq C\(R\)G\+\\sigma, andβ1≤β2<β2\\beta\_\{1\}\\leq\\beta\_\{2\}<\\sqrt\{\\beta\_\{2\}\}\. Choose

β1=1−\(ϵG\+σ\)4​p3​p−4\.\\beta\_\{1\}=1\-\\left\(\\frac\{\\epsilon\}\{G\+\\sigma\}\\right\)^\{\\frac\{4p\}\{3p\-4\}\}\.Then\(1−β1\)1/4≤ϵG\+σ\(1\-\\beta\_\{1\}\)^\{1/4\}\\leq\\frac\{\\epsilon\}\{G\+\\sigma\},\(1−β1\)34−1p=ϵG\+σ\(1\-\\beta\_\{1\}\)^\{\\frac\{3\}\{4\}\-\\frac\{1\}\{p\}\}=\\frac\{\\epsilon\}\{G\+\\sigma\}, and\(1−β1\)1−1p≤ϵG\+σ\.\(1\-\\beta\_\{1\}\)^\{1\-\\frac\{1\}\{p\}\}\\leq\\frac\{\\epsilon\}\{G\+\\sigma\}\.Thus, the first three non\-T−1T^\{\-1\}terms are bounded byC​\(R\)​ϵ\+2​C​\(R\)​C​\(β\)1p−12​ϵ\+2​ϵ\.C\(R\)\\epsilon\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\epsilon\+2\\epsilon\.Therefore,

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤C​\(R\)​β1​G​\(C​\(R\)​G\+σ\)3​p3​p−4ϵ3​p3​p−4​T\+2​C​\(R\)​C​\(β\)1p−12​β1​σ​\(C​\(R\)​G\+σ\)p\+43​p−4ϵp\+43​p−4​T\\displaystyle\\leq\\frac\{C\(R\)\\beta\_\{1\}G\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{3p\}\{3p\-4\}\}\}\{\\epsilon^\{\\frac\{3p\}\{3p\-4\}\}T\}\+\\frac\{2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\beta\_\{1\}\\sigma\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{p\+4\}\{3p\-4\}\}\}\{\\epsilon^\{\\frac\{p\+4\}\{3p\-4\}\}T\}\+2​β1​σ​\(C​\(R\)​G\+σ\)43​p−4ϵ43​p−4​T\+C​\(β\)​ρ1/2​Δ​\(C​\(R\)​G\+σ\)5​p3​p−4ϵ5​p3​p−4\+12​T\\displaystyle\\qquad\+\\frac\{2\\beta\_\{1\}\\sigma\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{4\}\{3p\-4\}\}\}\{\\epsilon^\{\\frac\{4\}\{3p\-4\}\}T\}\+\\frac\{\\sqrt\{C\(\\beta\)\}\\rho^\{1/2\}\\Delta\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{5p\}\{3p\-4\}\}\}\{\\epsilon^\{\\frac\{5p\}\{3p\-4\}\+\\frac\{1\}\{2\}\}T\}\+\(G\+σ\)​T0T⋅\(1\+C​\(β\)​\(C​\(R\)​G\+σ\)p3​p−4​ϵ−p3​p−4\)\\displaystyle\\qquad\+\\frac\{\(G\+\\sigma\)T\_\{0\}\}\{T\}\\cdot\\left\(1\+\\sqrt\{C\(\\beta\)\}\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{p\}\{3p\-4\}\}\\epsilon^\{\-\\frac\{p\}\{3p\-4\}\}\\right\)\+C​\(R\)​ϵ\+2​C​\(R\)​C​\(β\)1p−12​ϵ\+4​ϵ\.\\displaystyle\\qquad\+C\(R\)\\epsilon\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\epsilon\+4\\epsilon\.It is sufficient to choose

T≥max\{\\displaystyle T\\geq\\max\\Bigg\\\{2​\(1\+C​\(R\)​C​\(β\)1p−12\)​\(C​\(R\)​G\+σ\)4​p3​p−4​ϵ−4​p3​p−4,\\displaystyle 2\\left\(1\+C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\right\)\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{4p\}\{3p\-4\}\}\\epsilon^\{\-\\frac\{4p\}\{3p\-4\}\},C​\(β\)​ρ1/2​Δ​\(C​\(R\)​G\+σ\)5​p3​p−4​ϵ−\(5​p3​p−4\+32\),\\displaystyle\\sqrt\{C\(\\beta\)\}\\rho^\{1/2\}\\Delta\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{5p\}\{3p\-4\}\}\\epsilon^\{\-\\left\(\\frac\{5p\}\{3p\-4\}\+\\frac\{3\}\{2\}\\right\)\},\(G\+σ\)ϵ−1T0\+C​\(β\)\(C\(R\)G\+σ\)4​p−43​p−4ϵ−4​p−43​p−4T0\},\\displaystyle\(G\+\\sigma\)\\epsilon^\{\-1\}T\_\{0\}\+\\sqrt\{C\(\\beta\)\}\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{4p\-4\}\{3p\-4\}\}\\epsilon^\{\-\\frac\{4p\-4\}\{3p\-4\}\}T\_\{0\}\\Bigg\\\},where the last term can be further reformulated as𝒪​\(\(C​\(R\)​G\+σ\)8​p−43​p−4​ϵ−8​p−43​p−4​log⁡G\+σϵ\)\\mathcal\{O\}\\left\(\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{8p\-4\}\{3p\-4\}\}\\epsilon^\{\-\\frac\{8p\-4\}\{3p\-4\}\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\}\\right\)due toT0:=2\+log⁡\(1/\(1−β1\)\)log⁡\(β2/β1\)=𝒪​\(\(G\+σϵ\)4​p3​p−4​log⁡G\+σϵ\)T\_\{0\}:=2\+\\frac\{\\log\(1/\(1\-\\beta\_\{1\}\)\)\}\{\\log\(\\sqrt\{\\beta\_\{2\}\}/\\beta\_\{1\}\)\}=\\mathcal\{O\}\\left\(\\left\(\\frac\{G\+\\sigma\}\{\\epsilon\}\\right\)^\{\\frac\{4p\}\{3p\-4\}\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\}\\right\)\.

The third candidate ensures bothT≥T0T\\geq T\_\{0\}and that the burn\-in term is at mostϵ\\epsilon\. The first candidate controls the first threeT−1T^\{\-1\}terms by at most2​ϵ2\\epsilon, and the second candidate controls theΔ\\Delta\-term by at mostϵ\\epsilon\. Consequently,

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]≤\(8\+C​\(R\)\+2​C​\(R\)​C​\(β\)1p−12\)​ϵ\.\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}\\leq\\left\(8\+C\(R\)\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\right\)\\epsilon\.
Meanwhile, we observe that the second term in the selection of T dominates under fixed constants and nondegenerateΔ,ρ\\Delta,\\rhoasymptotically\. This proves the desired stationarity guarantee forp\>43p\>\\frac\{4\}\{3\}\. ∎

See[6\.5](https://arxiv.org/html/2607.27383#S6.Thmtheorem5)

###### Proof\.

Start from the unsimplified conversion bound equation[4\.2](https://arxiv.org/html/2607.27383#S4.Ex8)\(withβ=β1\\beta=\\beta\_\{1\}\):

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤1D​T​\(β1​𝔼​\[RegretT\[β\]​\(𝐮T\)\]\+\(1−β1\)​∑t=1T𝔼​\[Regrett\[β\]​\(𝐮t\)\]\)\\displaystyle\\leq\\frac\{1\}\{DT\}\\left\(\\beta\_\{1\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\]\+\(1\-\\beta\_\{1\}\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\\right\)\+2​\(1−β1\+β1T\)​\(1−β1\)−1p​σ\+ΔD​T\+2​ρ​β1​supt∈\[T\]𝔼​\[‖𝐳t‖2\]\(1−β1\)2\.\\displaystyle\\qquad\+2\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\(1\-\\beta\_\{1\}\)^\{\-\\frac\{1\}\{p\}\}\\sigma\+\\frac\{\\Delta\}\{DT\}\+\\frac\{2\\rho\\beta\_\{1\}\\sup\_\{t\\in\[T\]\}\\mathbb\{E\}\\left\[\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|^\{2\}\\right\]\}\{\(1\-\\beta\_\{1\}\)^\{2\}\}\.RecallT0:=2\+log⁡\(1/\(1−β1\)\)log⁡\(β2/β1\),T\_\{0\}:=2\+\\frac\{\\log\(1/\(1\-\\beta\_\{1\}\)\)\}\{\\log\(\\sqrt\{\\beta\_\{2\}\}/\\beta\_\{1\}\)\},whereT0T\_\{0\}is rounded up if necessary\.

For the firstT0T\_\{0\}rounds, we use a crude bound inferred directly from the regret definition\. Since

‖𝐳s‖≤D,‖𝐮t‖≤D,\\\|\{\\mathbf\{z\}\}\_\{s\}\\\|\\leq D,\\qquad\\\|\{\\mathbf\{u\}\}\_\{t\}\\\|\\leq D,we have, for anyt<T0t<T\_\{0\},

𝔼​\[Regrett\[β\]​\(𝐮t\)\]\\displaystyle\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]=𝔼​\[∑s=1tβ1t−s​⟨𝐯s,𝐳s−𝐮t⟩\]≤2​D​𝔼​\[∑s=1tβ1t−s​‖𝐯s‖\]\.\\displaystyle=\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{t\-s\}\\langle\{\\mathbf\{v\}\}\_\{s\},\{\\mathbf\{z\}\}\_\{s\}\-\{\\mathbf\{u\}\}\_\{t\}\\rangle\\right\]\\leq 2D\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{t\-s\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|\\right\]\.By Assumption[3\.3](https://arxiv.org/html/2607.27383#S3.Thmtheorem3),

𝔼​‖𝐯s‖≤‖𝝁s‖\+𝔼​‖𝝃s‖≤G\+\(𝔼​‖𝝃s‖p\)1/p≤G\+σ\.\\mathbb\{E\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|\\leq\\\|\\bm\{\\mu\}\_\{s\}\\\|\+\\mathbb\{E\}\\\|\\bm\{\\xi\}\_\{s\}\\\|\\leq G\+\\left\(\\mathbb\{E\}\\\|\\bm\{\\xi\}\_\{s\}\\\|^\{p\}\\right\)^\{1/p\}\\leq G\+\\sigma\.Therefore, summing the firstT0T\_\{0\}rounds inside the conversion bound gives

1−β1D​T​∑t<T0𝔼​\[Regrett\[β\]​\(𝐮t\)\]\\displaystyle\\frac\{1\-\\beta\_\{1\}\}\{DT\}\\sum\_\{t<T\_\{0\}\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]≤2​\(1−β1\)T​∑t<T0∑s=1tβ1t−s​𝔼​‖𝐯s‖\\displaystyle\\leq\\frac\{2\(1\-\\beta\_\{1\}\)\}\{T\}\\sum\_\{t<T\_\{0\}\}\\sum\_\{s=1\}^\{t\}\\beta\_\{1\}^\{t\-s\}\\mathbb\{E\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|=2T​∑s<T0\(\(1−β1\)​∑t=sT0−1β1t−s\)​𝔼​‖𝐯s‖\\displaystyle=\\frac\{2\}\{T\}\\sum\_\{s<T\_\{0\}\}\\left\(\(1\-\\beta\_\{1\}\)\\sum\_\{t=s\}^\{T\_\{0\}\-1\}\\beta\_\{1\}^\{t\-s\}\\right\)\\mathbb\{E\}\\\|\{\\mathbf\{v\}\}\_\{s\}\\\|≤2​T0T​\(G\+σ\)\.\\displaystyle\\leq\\frac\{2T\_\{0\}\}\{T\}\(G\+\\sigma\)\.Fort≥T0t\\geq T\_\{0\}, Corollary[6\.3](https://arxiv.org/html/2607.27383#S6.Thmtheorem3)gives

𝔼​\[Regrett\[β\]​\(𝐮t\)\]≤D​C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)1/2\.\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\\leq\\frac\{DC\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{1/2\}\}\.Thus, forT≥T0T\\geq T\_\{0\},

1D​T​\(β1​𝔼​\[RegretT\[β\]​\(𝐮T\)\]\+\(1−β1\)​∑t=1T𝔼​\[Regrett\[β\]​\(𝐮t\)\]\)\\displaystyle\\frac\{1\}\{DT\}\\left\(\\beta\_\{1\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{T\}\(\{\\mathbf\{u\}\}\_\{T\}\)\\right\]\+\(1\-\\beta\_\{1\}\)\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\left\[\\mathrm\{Regret\}^\{\[\\beta\]\}\_\{t\}\(\{\\mathbf\{u\}\}\_\{t\}\)\\right\]\\right\)≤\(1−β1\+β1T\)​C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)1/2\+2​T0T​\(G\+σ\)\.\\displaystyle\\qquad\\leq\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\\frac\{C\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{1/2\}\}\+\\frac\{2T\_\{0\}\}\{T\}\(G\+\\sigma\)\.
Substituting the clipped increment bound‖𝐳t‖≤D\\\|\{\\mathbf\{z\}\}\_\{t\}\\\|\\leq D, and choosingD=\(1−β1\)​ϵ1/2ρ1/2,D=\\frac\{\(1\-\\beta\_\{1\}\)\\epsilon^\{1/2\}\}\{\\rho^\{1/2\}\},we obtain

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤\(1−β1\+β1T\)​C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)1/2\\displaystyle\\leq\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\\frac\{C\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{1/2\}\}\+2​T0T​\(G\+σ\)\+2​\(1−β1\+β1T\)​\(1−β1\)−1/p​σ\\displaystyle\\qquad\+\\frac\{2T\_\{0\}\}\{T\}\(G\+\\sigma\)\+2\\left\(1\-\\beta\_\{1\}\+\\frac\{\\beta\_\{1\}\}\{T\}\\right\)\(1\-\\beta\_\{1\}\)^\{\-1/p\}\\sigma\+ρ1/2​Δ\(1−β1\)​ϵ1/2​T\+2​ϵ\.\\displaystyle\\qquad\+\\frac\{\\rho^\{1/2\}\\Delta\}\{\(1\-\\beta\_\{1\}\)\\epsilon^\{1/2\}T\}\+2\\epsilon\.Expanding the first and third terms gives

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤C​\(R\)​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)​\(1−β1\)1/2\+2​σ​\(1−β1\)1−1p\\displaystyle\\leq C\(R\)\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\(1\-\\beta\_\{1\}\)^\{1/2\}\+2\\sigma\(1\-\\beta\_\{1\}\)^\{1\-\\frac\{1\}\{p\}\}\+C​\(R\)​β1​\(G\+2​σ​\(1−β2\)−\(1p−12\)\)\(1−β1\)1/2​T\+2​β1​σ\(1−β1\)1/p​T\\displaystyle\\qquad\+\\frac\{C\(R\)\\beta\_\{1\}\\left\(G\+2\\sigma\(1\-\\beta\_\{2\}\)^\{\-\\left\(\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\\right\)\}\\right\)\}\{\(1\-\\beta\_\{1\}\)^\{1/2\}T\}\+\\frac\{2\\beta\_\{1\}\\sigma\}\{\(1\-\\beta\_\{1\}\)^\{1/p\}T\}\+ρ1/2​Δ\(1−β1\)​ϵ1/2​T\+2​T0T​\(G\+σ\)\+2​ϵ\.\\displaystyle\\qquad\+\\frac\{\\rho^\{1/2\}\\Delta\}\{\(1\-\\beta\_\{1\}\)\\epsilon^\{1/2\}T\}\+\\frac\{2T\_\{0\}\}\{T\}\(G\+\\sigma\)\+2\\epsilon\.Using1−β1≤C​\(β\)​\(1−β2\),1\-\\beta\_\{1\}\\leq C\(\\beta\)\(1\-\\beta\_\{2\}\),we obtain

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤C​\(R\)​G​\(1−β1\)1/2\+2​C​\(R\)​C​\(β\)1p−12​σ​\(1−β1\)1−1p\+2​σ​\(1−β1\)1−1p\\displaystyle\\leq C\(R\)G\(1\-\\beta\_\{1\}\)^\{1/2\}\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\sigma\(1\-\\beta\_\{1\}\)^\{1\-\\frac\{1\}\{p\}\}\+2\\sigma\(1\-\\beta\_\{1\}\)^\{1\-\\frac\{1\}\{p\}\}\+C​\(R\)​β1​G\(1−β1\)1/2​T\+2​\(1\+C​\(R\)​C​\(β\)1p−12\)​β1​σ\(1−β1\)1/p​T\\displaystyle\\qquad\+\\frac\{C\(R\)\\beta\_\{1\}G\}\{\(1\-\\beta\_\{1\}\)^\{1/2\}T\}\+\\frac\{2\\left\(1\+C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\right\)\\beta\_\{1\}\\sigma\}\{\(1\-\\beta\_\{1\}\)^\{1/p\}T\}\+ρ1/2​Δ\(1−β1\)​ϵ1/2​T\+2​T0T​\(G\+σ\)\+2​ϵ\.\\displaystyle\\qquad\+\\frac\{\\rho^\{1/2\}\\Delta\}\{\(1\-\\beta\_\{1\}\)\\epsilon^\{1/2\}T\}\+\\frac\{2T\_\{0\}\}\{T\}\(G\+\\sigma\)\+2\\epsilon\.
Now assume0<ϵ≤G\+σ0<\\epsilon\\leq G\+\\sigma, and chooseβ1=1−\(ϵG\+σ\)pp−1\.\\beta\_\{1\}=1\-\\left\(\\frac\{\\epsilon\}\{G\+\\sigma\}\\right\)^\{\\frac\{p\}\{p\-1\}\}\.Then\(1−β1\)1−1p=ϵG\+σ\(1\-\\beta\_\{1\}\)^\{1\-\\frac\{1\}\{p\}\}=\\frac\{\\epsilon\}\{G\+\\sigma\}and\(1−β1\)1/2≤ϵG\+σ\.\(1\-\\beta\_\{1\}\)^\{1/2\}\\leq\\frac\{\\epsilon\}\{G\+\\sigma\}\.Thus, the first three non\-T−1T^\{\-1\}terms are bounded byC​\(R\)​ϵ\+2​C​\(R\)​C​\(β\)1p−12​ϵ\+2​ϵ\.C\(R\)\\epsilon\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\epsilon\+2\\epsilon\.Therefore,

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]\\displaystyle\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}≤C​\(R\)​β1​G​\(C​\(R\)​G\+σ\)p2​p−2ϵp2​p−2​T\+2​\(1\+C​\(R\)​C​\(β\)1p−12\)​β1​σ​\(C​\(R\)​G\+σ\)1p−1ϵ1p−1​T\\displaystyle\\leq\\frac\{C\(R\)\\beta\_\{1\}G\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{p\}\{2p\-2\}\}\}\{\\epsilon^\{\\frac\{p\}\{2p\-2\}\}T\}\+\\frac\{2\\left\(1\+C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\right\)\\beta\_\{1\}\\sigma\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{1\}\{p\-1\}\}\}\{\\epsilon^\{\\frac\{1\}\{p\-1\}\}T\}\+ρ1/2​Δ​\(C​\(R\)​G\+σ\)pp−1ϵpp−1\+12​T\+2​\(G\+σ\)​T0T\+2​C​\(R\)​C​\(β\)1p−12​ϵ\+4​ϵ\.\\displaystyle\\qquad\+\\frac\{\\rho^\{1/2\}\\Delta\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{p\}\{p\-1\}\}\}\{\\epsilon^\{\\frac\{p\}\{p\-1\}\+\\frac\{1\}\{2\}\}T\}\+\\frac\{2\(G\+\\sigma\)T\_\{0\}\}\{T\}\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\epsilon\+4\\epsilon\.It is sufficient to choose

T≥max\{\\displaystyle T\\geq\\max\\Bigg\\\{2​\(1\+C​\(R\)​C​\(β\)1p−12\)​\(C​\(R\)​G\+σ\)pp−1​ϵ−pp−1,\\displaystyle 2\\left\(1\+C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\right\)\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{p\}\{p\-1\}\}\\epsilon^\{\-\\frac\{p\}\{p\-1\}\},ρ1/2​Δ​\(C​\(R\)​G\+σ\)pp−1​ϵ−\(pp−1\+32\),\\displaystyle\\rho^\{1/2\}\\Delta\\left\(C\(R\)G\+\\sigma\\right\)^\{\\frac\{p\}\{p\-1\}\}\\epsilon^\{\-\\left\(\\frac\{p\}\{p\-1\}\+\\frac\{3\}\{2\}\\right\)\},\(1\+2\(G\+σ\)ϵ−1\)T0\},\\displaystyle\\left\(1\+2\(G\+\\sigma\)\\epsilon^\{\-1\}\\right\)T\_\{0\}\\Bigg\\\},where the last term can be further reformulated as𝒪​\(\(G\+σ\)pp−1\+1​ϵ−\(pp−1\+1\)​log⁡G\+σϵ\)\\mathcal\{O\}\\left\(\\left\(G\+\\sigma\\right\)^\{\\frac\{p\}\{p\-1\}\+1\}\\epsilon^\{\-\\left\(\\frac\{p\}\{p\-1\}\+1\\right\)\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\}\\right\)due toT0:=2\+log⁡\(1/\(1−β1\)\)log⁡\(β2/β1\)=𝒪​\(\(G\+σϵ\)pp−1​log⁡G\+σϵ\)T\_\{0\}:=2\+\\frac\{\\log\(1/\(1\-\\beta\_\{1\}\)\)\}\{\\log\(\\sqrt\{\\beta\_\{2\}\}/\\beta\_\{1\}\)\}=\\mathcal\{O\}\\left\(\\left\(\\frac\{G\+\\sigma\}\{\\epsilon\}\\right\)^\{\\frac\{p\}\{p\-1\}\}\\log\\frac\{G\+\\sigma\}\{\\epsilon\}\\right\)when choosingβ1=1−\(ϵG\+σ\)pp−1\\beta\_\{1\}=1\-\\left\(\\frac\{\\epsilon\}\{G\+\\sigma\}\\right\)^\{\\frac\{p\}\{p\-1\}\}\.

The third candidate ensures bothT≥T0T\\geq T\_\{0\}and that the burn\-in term is at mostϵ\\epsilon\. The first candidate controls the first twoT−1T^\{\-1\}terms by at most2​ϵ2\\epsilon, and the second candidate controls theΔ\\Delta\-term by at mostϵ\\epsilon\. Consequently,

𝔼τ​‖∇F​\(𝐱~τ\)‖\[ρ\]≤\(8\+C​\(R\)\+2​C​\(R\)​C​\(β\)1p−12\)​ϵ\.\\mathbb\{E\}\_\{\\tau\}\\\|\\nabla F\(\\widetilde\{\{\\mathbf\{x\}\}\}\_\{\\tau\}\)\\\|^\{\[\\rho\]\}\\leq\\left\(8\+C\(R\)\+2C\(R\)C\(\\beta\)^\{\\frac\{1\}\{p\}\-\\frac\{1\}\{2\}\}\\right\)\\epsilon\.
Meanwhile, we observe that the second term in the selection of T dominates w\.r\.t\.ϵ\\epsilonunder fixed constants and nondegenerateΔ,ρ\\Delta,\\rhoasymptotically\. This proves the clipped stationarity guarantee forp∈\(1,2\]p\\in\(1,2\]\. ∎