Coordinatewise Epsilon for Adam under Heavy-Tailed Noise

Coordinatewise Epsilon for Adam under Heavy-Tailed Noise

arXiv:2611.09596v1 [cs.LG] 6 Nov 2026

Jeonseong Kim Yonsei University Seoul, Korea JeonseongKim@gmail.com

Chenglin Fan Seoul National University Seoul, Korea fanchenglin@snu.ac.kr

Abstract Adam estimates second moments coordinatewise, but typically adds the same scalar ε to every denominator. We study how this shared ε affects convergence when noise and curvature vary across coordinates. Under coordinatewise finite-p noise moments, p ∈ (1, 2], choosing εi from the noise and curvature bounds for each coordinate attains the heavy-tailed ℓ1 -stationarity p−1 benchmark O(T − 3p−2 ), matching the known optimal time exponent for smooth nonconvex stochastic optimization. For 1 < p < 2, Adam with a shared εt admits a lower bound of order p−1 Ω(T − 2p ). This lower bound holds for every predictable scalar choice of ηt , β1,t , β2,t , and εt , precluding a dimension-uniform benchmark rate for this class.

1

Introduction

Adam and AdamW (Kingma and Ba, 2015; Loshchilov and Hutter, 2019) are standard optimizers in large-scale language-model training (Brown et al., 2020; Touvron et al., 2023). Heavy-tailed stochastic-gradient noise has been observed in deep networks and attention-model training (Simsekli et al., 2019; Zhang et al., 2020), including recent language-model pretraining runs (Yu et al., 2026b). For linear models with cross-entropy loss, class imbalance produces heterogeneous gradients and Hessians (Kunstner et al., 2024). These observations motivate studying how Adam’s coordinatewise normalization behaves when noise and curvature vary across coordinates. Adam estimates the second moment separately in each coordinate. Its update adds the same scalar to every denominator: mt,i xt+1,i = xt,i − ηt √ . vt,i + εt The additive term εt prevents small denominators and determines how strongly the update responds to the second-moment estimate (Zaheer et al., 2018; Tong et al., 2022). If εt dominates, differences between the second-moment estimates have little effect on the denominators. If εt is small, those differences directly shape the updates. Yu et al. (2026a, Eq. (2)) ask whether AdamW can attain the heavy-tailed ℓ1 -stationarity benchmark of sign-based methods. We adopt the same curvature and noise assumptions as their gradient-independent setting, with one stochastic gradient per step and zero weight decay. Write P P L = i Li for the total coordinatewise curvature bound and Σ = i σi for the total finite-p noise scale, where p ∈ (1, 2]. We compare shared and coordinatewise choices of ε at fixed L, Σ, allowing the dimension and the allocation of these scales to vary. Our target is their benchmark uniformly − p−1 over these choices. We refer to T 3p−2 as the sharp heavy-tailed rate, since this time exponent is known to be optimal for smooth nonconvex stochastic optimization (Liu and Zhou, 2025). 1

For 1 < p < 2, Adam with a shared εt has a lower bound with the slower exponent (p − 1)/(2p) on instances whose dimension grows with T , even when all scalar hyperparameters may depend on the past. In contrast, choosing εi according to the coordinatewise noise and curvature bounds attains the benchmark for every p ∈ (1, 2]. The upper bound balances two goals: choosing εi large enough to control momentum noise and P gradient drift in each coordinate, while keeping i εi small. Given the coordinatewise bounds, we take, with ρ2 = 1 − β2 ,   − 2−p Li εi ≍ ρ2 2p max σi , Σ . (1) L n

o

The maximum combines the noise and curvature requirements, and i max σi , LLi Σ ≤ 2Σ controls the total. The lower-bound construction pairs coordinates and adds a control coordinate. On an event of constant probability, the control coordinate offsets the progress of all pairs, keeping the iterates in a region with constant nonzero gradient. P

Contributions. 1. Coordinatewise upper bound. Theorem 4.1 attains the benchmark dependence on ∆, L, Σ, T , and in particular matches the known optimal heavy-tailed time exponent. A self-normalized tracking estimate controls heavy-tailed momentum noise while retaining the random denominator for large observations. 2. Lower bound for a shared ε. Theorem 4.2 gives a lower bound for 1 < p ≤ 2 through a pathwise comparison of normalized updates. The oracle outputs are gradients of scalar sample functions.

2

Related work

Adaptive normalization and Adam theory. AdaGrad introduced diagonal scaling by accumulated coordinatewise gradients; Adam uses exponential moving averages to estimate first and second moments (Duchi et al., 2011; Kingma and Ba, 2015). The classical counterexample of Reddi et al. (2018) concerns exponential forgetting and nonmonotone effective stepsizes. Heilman and Mohanty (2026) extend this phenomenon to fixed β1 , β2 , ε, while Zhou et al. (2019) study same-time correlation between the gradient and its second-moment estimate. Convergence analyses address bounded gradients, finite or affine variance, generalized smoothness, and suitable schedules (Chen et al., 2019; Défossez et al., 2022; Zhang et al., 2022; Hong and Lin, 2024). Under √ Euclidean smoothness and coordinatewise bounded variance, Li et al. (2025) establish an O( d T −1/4 ) expected ℓ1 -gradient rate for AdamW, with Adam as a special case. Liu et al. (2025) analyze AdaGrad under anisotropic smoothness and noise conditions, while Jiang et al. (2025) combine coordinatewise smoothness and variance with ℓ1 stationarity to compare AdaGrad and SGD. Together, these works motivate expressing guarantees in a coordinatewise geometry and tracking how dimension enters when the coordinate scales are aggregated. We use P P this viewpoint to compare shared and coordinatewise choices of ε at fixed L = i Li and Σ = i σi . Heavy-tailed nonconvex optimization. For 1 < p < 2, a finite pth noise moment need not imply finite variance. Gradient clipping gives expectation and high-probability guarantees in this regime (Zhang et al., 2020; Cutkosky and Mehta, 2021). Zhang et al. (2020) establish the classical

2

heavy-tailed time exponent (p − 1)/(3p − 2) under a global-norm nonconvex model and also study coordinatewise clipping. Later work develops refined clipping and normalization methods (Liu et al., 2023; Hübler et al., 2025; Liu and Zhou, 2025). Models in this literature vary in whether moments are imposed on stochastic gradients or centered noise, and in whether control is global or coordinatewise. Sign-based methods provide the coordinatewise ℓ1 comparison relevant here (Yu et al., 2026b;a). Adaptive methods under heavy-tailed noise. Heavy-tailed guarantees for adaptive methods cover several algorithms and stationarity notions. Chezhegov et al. (2025) show that explicit clipping improves the high-probability confidence dependence of Adam-Norm and AdaGrad-Norm. Liu (2026a) proves an expected rate for coordinatewise AdaGrad when p > 4/3 and gives an algorithm-dependent lower bound. Recent online-to-nonconvex analyses establish guarantees for Adam under relaxed stationarity criteria (Liu, 2026b; Pang, 2026). The setting considered here uses the expected ℓ1 norm of the true gradient, coordinatewise smoothness, and centered coordinatewise noise moments. The choice of ε. The effect of ε has also been studied: it can suppress adaptivity and enter convergence constants (Zaheer et al., 2018), while softplus transformations and alternative placements change anisotropic effective steps (Tong et al., 2022; Yuan and Gao, 2020). Yu et al. (2026a) formulate the AdamW benchmark and give a corridor obstruction under specified conditions on β1 , β2 and the stepsize. This motivates treating ε as part of the optimizer’s geometry and comparing a shared stabilization scale with coordinatewise ones.

3

Preliminaries and problem setup

3.1

Notation and objective geometry 1

For a positive definite matrix D, write ∥x∥D = (x⊤ Dx) 2 ; ⊙ denotes coordinatewise multiplication. We use a ≲ b and a ≍ b for one-sided and two-sided bounds up to positive constants. Unless stated otherwise, constants may depend on p and the fixed compact set K of ratios ρ2 /ρ1 introduced below, but not on d, T, ∆, L, Σ or the allocation of the coordinatewise scales. Let f : Rd → R be differentiable and lower bounded. Fix a diagonal geometry DL = Diag(L1 , . . . , Ld ),

Li > 0,

L=

d X

Li .

i=1

Assumption 3.1 (Coordinatewise smoothness). We assume ∥∇f (y) − ∇f (x)∥D−1 ≤ ∥y − x∥DL , L

x, y ∈ Rd .

(2)

For twice continuously differentiable f , this condition is equivalent to −DL ⪯ ∇2 f (x) ⪯ DL ,

x ∈ Rd .

Assumption 3.1 implies the descent inequality 1 f (y) ≤ f (x) + ⟨∇f (x), y − x⟩ + ∥y − x∥2DL . 2

(3)

Assumption 3.2 (Initial gap). The initial point satisfies f (x1 ) − inf f (x) ≤ ∆. x

3

(4)

3.2

Stochastic oracle and stationarity

Let Ft−1 denote the history before the tth oracle query, including the initialization, past oracle observations, and algorithmic randomness available before that query. We require xt and all time-t parameters to be Ft−1 -measurable and call such parameter choices predictable. Assumption 3.3 (Finite-moment oracle). At time t, the oracle returns gt = ∇f (xt ) + ξt , where, coordinatewise, E[ξt,i | Ft−1 ] = 0,

E[|ξt,i |p | Ft−1 ] ≤ σip ,

p ∈ (1, 2].

(5)

P

Write Σ = i σi and assume ∆, L, Σ > 0. The moment condition controls the centered noise and allows unbounded gradients. Coordinates may be dependent, and the noise distribution may depend on the past. At p = 2 this is a coordinatewise conditional variance bound; for p < 2 it permits infinite variance. Stationarity criterion. We use the ℓ1 -stationarity criterion in the open problem of Yu et al. (2026a), T 1X RT = E∥∇f (xt )∥1 . (6) T t=1

3.3

Adam families

Starting from m0 = v0 = 0, consider the family mt = β1,t mt−1 + (1 − β1,t )gt ,

(7)

vt = β2,t vt−1 + (1 − β2,t )gt⊙2 , mt,i xt+1,i = xt,i − ηt √ . vt,i + εt,i

(8) (9)

The upper bound uses fixed ηt ≡ η, βk,t ≡ βk , and εt,i ≡ εi ; write ρk = 1 − βk . For the lower bound, ηt ≥ 0, βk,t ∈ [0, 1), and εt ≥ 0 may be arbitrary Ft−1 -measurable scalars, with the restriction εt,i ≡ εt . This class includes fixed-parameter Adam and standard scalar bias correction after its deterministic factors are absorbed into ηt and εt . We require updates to be finite and well defined almost surely on the problem class. We study the zero-weight-decay setting.

4

Main results

4.1

Upper bound with coordinatewise εi

Define 

ρ⋆ =

∆L Σ2 T

4



p 3p−2

.

(10)

Choosing εi .

Write S=

X

εi ,

κ = max i

i − 2−p 2p

For the stepsize η = λρ1 Σρ2 requirements:

Li . εi

/L, with λ > 0 sufficiently small, the upper proof uses three sufficient

1. Momentum noise. Each coordinate satisfies − 2−p

εi ≥ ρ2 2p σi . 2. Gradient drift. The updates satisfy ηκ ≤ λρ1 . − 2−p

The coordinatewise bound εi ≥ ρ2 2p (Li /L)Σ ensures this inequality and allows the drift contribution to be absorbed. 3. Total size. The sum satisfies

− 2−p

S ≲ ρ2 2p Σ. After balancing the stepsize and averaging parameters, the proof gives RT ≲

√

ρ1 S.

Taking the larger of the two coordinatewise lower bounds meets the first two requirements. Their − 2−p

sums are both ρ2 2p Σ, so this choice also meets the third. Theorem 4.1 (Coordinatewise choices of εi attain the sharp rate). Fix p ∈ (1, 2]. Let K be a compact subset of (0, 4/(2 − p)) when p < 2, or of (0, ∞) when p = 2. There exist constants c, C, λ > 0, depending only on p and K, such that the following holds whenever ρ⋆ ≤ c. Choose ρ1 = ρ⋆ ,

ρ2 ∈ K, ρ1

η=λ

ρ1 − 2−p ρ 2p Σ, L 2

using the constant λ above, and set − 2−p εi = ρ2 2p max

Then



Li σi , Σ . L 

T p−1 p 1X − p−1 E∥∇f (xt )∥1 ≤ C(∆L) 3p−2 Σ 3p−2 T 3p−2 . T t=1

(11)

(12)

The bound is uniform over all objectives and oracles satisfying Assumptions 3.1–3.3. The choice (11) gives X

− 2−p

εi ≤ 2ρ2 2p Σ.

i

5

(13)

4.2

Lower bound for a shared ε

Theorem 4.2 (Lower bound for a shared ε). Fix 1 < p ≤ 2. There are constants c, δ0 > 0, depending only on p, such that for every horizon T , every rule in the predictable Adam class with a shared εt , and every − p−1 0 < δ ≤ min{δ0 , T p }, there exist a dimension d, a convex continuously differentiable objective, an initial point, and a stochastic first-order oracle whose realizations are gradients of convex continuously differentiable scalar sample functions, satisfying f (x1 ) − inf f ≤ 1,

L ≤ 1,

Σ ≤ 1,

for which T √ 1X E∥∇f (xt )∥1 ≥ c δ. T t=1

For sufficiently large T , taking δ = T

4.3

− p−1 p

(14)

gives a fixed-gap lower bound with exponent (p − 1)/(2p).

Consequences

Corollary 4.3 (Shared ε under balanced coordinate scales). Under the assumptions of Theorem 4.1, suppose Σ L max σi ≤ C0 , max Li ≤ C0 (15) i i d d for a constant C0 . Set − 2−p Σ εi ≡ ε = C0 ρ2 2p . d Then Adam with a shared ε satisfies, for a constant C depending only on p, K, and C0 , p−1

p

RT ≤ C(∆L) 3p−2 Σ 3p−2 T

p−1 − 3p−2

.

The upper bound for arbitrary coordinate scales at fixed dimension is derived in Appendix A.4.

5

Proof overview

The upper bound uses the random denominator to control heavy-tailed momentum noise. The lower bound uses paired coordinates and a control coordinate to bound progress under shared scalar tuning. We give the key estimates here; the appendices contain the full proofs.

5.1

Upper bound: controlling momentum noise

Under the tuning of Theorem 4.1, the proof first bounds the weighted gradient term, then the √ average denominator, and finally the true gradient norm. Write ht = ∇f (xt ) and Dt,i = vt,i + εi .

6

With S =

P

i εi , the three key relations are

∆ 1 X h2t,i ≲ E + ρ1 S, T t,i Dt,i ηT

(16) 



1X 1 X h2t,i  + CS, EDt,i ≤ 2  E T t,i T t,i Dt,i 







(17) 

1 X h2t,i   1 X RT2 ≤  E EDt,i  T t,i Dt,i T t,i 

1 X h2t,i   1 X h2t,i + CS  . E E 2 ≤ T t,i Dt,i T t,i Dt,i

(18)

The first follows from momentum tracking and smooth descent; the second controls the denominators without an additional dimension factor; the third is Cauchy–Schwarz over time, coordinates, and probability. The prescribed parameters balance ∆/(ηT ) with ρ1 S. Thus (16)–(18) give RT2 ≲ ρ1 S(ρ1 S + S) ≲ ρ1 S 2 ,

RT ≲

√

p−1

ρ1 S ≍ Σρ1 p .

Tracking under heavy-tailed noise. The main difficulty in (16) is controlling et = mt − ht when the noise may have infinite variance. Fix a coordinate and suppress its index. The noise part of the first moment is nt = ρ1

t X

β1t−s ξs .

s=1

The coordinatewise choice of ε permits the self-normalized estimate T X t=1

E

T X h2 n2t E t. ≤ Cρ1 T ε + Cρ1 ρ2 Dt Dt t=1

(19)

Its right-hand side contains the same weighted gradient term as (16), with a coefficient that can be absorbed. Initialization and gradient drift form the other parts of et . Lemma A.1 controls them, using ηκ ≤ λρ1 for the drift. √ √ For 1 < p < 2, the proof splits the noise at ε/ ρ2 . At this threshold, the term ρ2 |ξt | becomes comparable to ε. Below this threshold, truncated second moments and conditional centering control the contribution. Above it, the random denominator controls large observations: on |ξt | > 2|ht |, √ Dt ≥

ρ2 |ξt | , 2

ξt2

2−p ≤

εp−1 Dt

C|ξt |p (2−p)/2

εp−1 ρ2

.

On the complementary event, the bound contributes to the weighted gradient term in (19). (t−s)/2

Propagation through the moment recursions. For t ≥ s, Dt ≥ β2 Ds . Combined with (2−p)/2 2 the first-moment weights, this produces a geometric series with ratio β1 /β2 . Write δp = 1 −

β12 (2−p)/2

β2

7

.

(20)

For ρ2 /ρ1 ∈ K and sufficiently small ρ1 , δp ≍ ρ1 > 0; the time sum is therefore at most 1/δp . Appendix A.3 gives the centered noise decomposition, cross-term bounds, and full time summation proving (19). At p = 2, the same estimate follows directly from conditional variance and orthogonality. The average denominator. To obtain (17), the recursion bounds past gradient contributions by −(2−p)/(2p) the weighted gradient term in (16). The finite-p noise moments contribute at most Cσi ρ2 ≤ Cεi in coordinate i. Summing over coordinates gives CS, controlled by (13). Appendix A.2 proves the descent and denominator bounds in (16)–(17).

5.2

Lower bound: a pathwise comparison

We construct an objective f (z) = ϕ(Y (z)),

ϕ′ (y) = clip(y, 0, 1),

ϕ(0) = 0,

where Y is affine with a nonzero coefficient vector. On Y (z) ≥ 1, the gradient of f equals this fixed vector. Starting from Y (z1 ) = 1, the construction maintains, on an event of constant probability, Y (zt+1 ) ≥ Y (zt ) ≥ 1

(1 ≤ t ≤ T ).

This gives a lower bound on the gradient norm at every iterate. The construction has three parts. A control coordinate receives wrong-sign observations throughout this event and moves in a direction that increases Y . Coordinate pairs have a uniformly bounded total decrease under arbitrary shared averaging weights. Pairing makes this bound depend only on the totals of the common first- and second-moment weights, allowing the same comparison to cover arbitrary predictable scalar tuning. The affine function Y combines these contributions so that the increase offsets the decrease. Objective and coordinate scales. Fix δ as in Theorem 4.2. With a fixed positive constant γ chosen in Appendix B, set √ γ γ δ −1 b= . N = ⌈δ ⌉, A= , N N Use one control coordinate u and N pairs (wi,+ , wi,− ). With si = (wi,+ + wi,− )/2, define Y (z) = 1 + γδ u + b

N X

si .

i=1

At z1 = 0, Y (z1 ) = 1 and the initial gap is 1/2. On Y (z) ≥ 1, the gradient is the coefficient vector ϱ of Y and √ √ ∥∇f (z)∥1 = γδ + N b = γ(δ + δ) ≥ γ δ. Oracle and averaging weights. Let θ = 1/(8T ) and draw fresh randomness independently at each step. The control observation is −γδ with probability 1 − θ and γδ(2/θ − 1) otherwise. Each pair receives a uniformly random permutation of {A + b, −A}, using one common sign independent of the control draw. These observations form a vector qt with Eqt = ϱ. Globally, set 



gt (z) = ∇f (z) + qt − ϱ = ∇ f (z) + ⟨qt − ϱ, z⟩ . 8

Let A be the event that all control observations take their common value; independent draws give Pr(A) = (1 − θ)T ≥ 7/8. Along any realized history, the recursions express mt and vt as nonnegative weighted sums of past gradients and squared gradients. Write the common scalar weights as αt,s , νt,s and their totals as X X Pt = αt,s , Vt = νt,s > 0. s≤t

s≤t

Lemma 5.1 (Sum of the two normalized updates). Suppose a coordinate pair receives a permutation of {A + b, −A} atq each step up to time t. For A, b > 0, the averaging weights above, and a shared ± ± εt ≥ 0, let Dt,i = vt,i + εt . Then 0≤

m+ t,i

m− t,i

2bP √ t . − ≤ + + A Vt + ε t Dt,i Dt,i

(21)

The pair has a positive first-moment sum. The absolute difference between its denominators, divided by their sum, is at most b/(2A + b). This limits the effect of unequal normalization on the sum of the two updates. The proof is in Appendix B.4. The pathwise invariant. On A, suppose Y (zs ) ≥ 1 up to time t, so the observations equal qs . The control moments are mt,0 = −γδPt and vt,0 = γ 2 δ 2 Vt . Since Vt > 0 and each pair has ± vt,i ≥ A2 Vt , all denominators are positive even when εt = 0. The control contribution and the total contribution of the pairs satisfy γ 2 δηt Pt , γδ(ut+1 − ut ) = √ γ Vt + εδt 0 ≤ −b

X

(st+1,i − st,i ) ≤

N b2 ηt Pt γ 2 δηt Pt √ = √ . A Vt + εt γ Vt + N εt

"

#

i

Consequently, 2

Y (zt+1 ) − Y (zt ) ≥ γ δηt Pt

1 1 √ √ ≥ 0, εt − γ Vt + δ γ Vt + N ε t

(22)

because N ≥ δ −1 . Starting from Y (z1 ) = 1, induction keeps every iterate in the affine region on A. √ Hence RT ≥ (7/8)γ δ. Appendix B gives the full construction and induction, and Appendix B.6 verifies L ≤ 1 and Σ ≤ 1. − p−1 Choosing δ = T p for sufficiently large T gives the stated time exponent with d = 1 + 2⌈δ −1 ⌉.

6

Conclusion

Adam is usually viewed as a coordinatewise adaptive method because its second-moment estimate is coordinatewise. The results here show that this view is incomplete. The denominator contains √ two scales, vt,i and ε. When ε is shared, the normalization is only as coordinatewise as a single stabilization scale allows it to be. If the relevant noise and curvature scales differ substantially across coordinates, one scalar is asked to regularize several incompatible local regimes. This points to a distinction that is easy to miss in adaptive methods. Coordinatewise statistics do not by themselves imply coordinatewise tuning. A global regularization applied after those statistics can reintroduce a common scale and limit the adaptivity that the coordinatewise estimator was meant to provide. For Adam, ε is a particularly simple instance of this mismatch. 9

References Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages 1877–1901, 2020. Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of Adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019. Savelii Chezhegov, Yaroslav Klyukin, Andrei Semenov, Aleksandr Beznosikov, Alexander Gasnikov, Samuel Horváth, Martin Takáč, and Eduard Gorbunov. Clipping improves Adam-norm and AdaGrad-norm when the noise is heavy-tailed. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 10269–10333, 2025. Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. In Advances in Neural Information Processing Systems, volume 34, pages 4883–4895, 2021. Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of Adam and AdaGrad. Transactions on Machine Learning Research, 2022. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121–2159, 2011. Steven Heilman and Sampad Mohanty. On the convergence of Adam, revisited. arXiv preprint arXiv:2607.03519, 2026. Yusu Hong and Junhong Lin. On convergence of Adam for stochastic optimization under relaxed assumptions. In Advances in Neural Information Processing Systems, volume 37, 2024. Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed SGD. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 2413–2421, 2025. Ruichen Jiang, Devyani Maladkar, and Aryan Mokhtari. Provable complexity improvement of AdaGrad over SGD: Upper and lower bounds in stochastic non-convex optimization. In Proceedings of the Thirty-Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 3124–3158, 2025. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. Frederik Kunstner, Alan Milligan, Robin Yadav, Mark Schmidt, and Alberto Bietti. Heavy-tailed class imbalance and why Adam outperforms gradient descent on language models. In Advances in Neural Information Processing Systems, volume 37, pages 30106–30148, 2024.

10

√ Huan Li, Yiming Dong, and Zhouchen Lin. On the O( d/K 1/4 ) convergence rate of AdamW measured by ℓ1 norm. In Advances in Neural Information Processing Systems, volume 38, 2025. Yuxing Liu, Rui Pan, and Tong Zhang. AdaGrad under anisotropic smoothness. In International Conference on Learning Representations, 2025. Zijian Liu. Can adaptive gradient methods converge under heavy-tailed noise? A case study of AdaGrad. arXiv preprint arXiv:2605.18694, 2026a. Accepted at the 43rd International Conference on Machine Learning (ICML 2026). Zijian Liu. Adam converges in nonsmooth nonconvex optimization. arXiv preprint arXiv:2606.22326, 2026b. Zijian Liu and Zhengyuan Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. In International Conference on Learning Representations, 2025. Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. In Proceedings of the Thirty-Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2266–2290, 2023. Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. Yijiang Pang. The convergence behavior of Adam under heavy-tailed noise. In Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, volume 337 of Proceedings of Machine Learning Research, pages 5244–5265, 2026. Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018. Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5827–5837, 2019. Qianqian Tong, Guannan Liang, and Jinbo Bi. Calibrating the adaptive learning rate to improve convergence of Adam. Neurocomputing, 481:333–356, 2022. doi: 10.1016/j.neucom.2022.01.014. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023. Dingzhi Yu, Hongyi Tao, Yuanyu Wan, Luo Luo, and Lijun Zhang. Open problem: Is AdamW effective under heavy-tailed noise? arXiv preprint arXiv:2606.23676, 2026a. Dingzhi Yu, Hongyi Tao, Yuanyu Wan, Luo Luo, and Lijun Zhang. Sign-based optimizers are effective under heavy-tailed noise. arXiv preprint arXiv:2602.07425, 2026b. Wei Yuan and Kai-Xin Gao. arXiv:2011.02150, 2020.

EAdam optimizer:

11

How ϵ impact Adam.

arXiv preprint

Manzil Zaheer, Sashank J. Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 31, 2018. Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J. Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems, volume 33, pages 15383–15393, 2020. Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can converge without any modification on update rules. In Advances in Neural Information Processing Systems, volume 35, pages 28386–28399, 2022. Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. AdaShift: Decorrelation and convergence of adaptive learning rate methods. In International Conference on Learning Representations, 2019.

12

A

Upper bound and balanced-scale corollary

The proof has two stages. First, we control the accumulated tracking error and use smooth descent to P bound T −1 t,i E[h2t,i /Dt,i ]. Second, we bound the average denominator and apply Cauchy–Schwarz to recover the unweighted ℓ1 criterion. Appendix A.3 proves the noise estimate used in the first stage. Appendix A.4 proves the balanced-scale corollary. Throughout the appendices, c and C may change from line to line and may depend on p and K. Additional dependence is stated when it first appears. For brevity, write p−1

p

R⋆ = (∆L) 3p−2 Σ 3p−2 T Also write ht = ∇f (xt ),

Dt,i =

p−1 − 3p−2

√

.

vt,i + εi .

Set x0 = x1 , h0 = h1 , e0 = −h1 , and, for t ≥ 1, et = mt − ht . Subtracting ht from the first-moment update separates gradient drift from momentum noise: et = mt − ht = β1 (mt−1 − ht−1 ) + β1 (ht−1 − ht ) + ρ1 ξt = β1 et−1 + β1 (ht−1 − ht ) + ρ1 ξt . Define κ = max i

Li . εi

(23)

(24)

The choice of εi gives X

− 2−p εi ≤ ρ2 2p

ΣX σi + Li L i i

i

κ ≤ max i

!

X

Li − 2−p 2p

ρ2

=

(Li /L)Σ

− 2−p

= 2Σρ2 2p ,

L 2−p ρ 2p , Σ 2

(25)

− 2−p

λρ1 Σρ2 2p L 2−p ηκ ≤ ρ 2p = λρ1 . L Σ 2 All expectations below are finite on each fixed horizon. For 0 < β2 < 1, weighted Cauchy–Schwarz in the moment recursions gives 

t−1 X ρ1 β12 |mt,i | ≤√  Dt,i ρ2 k=0 β2

!k  12  .

Thus the displacements, true gradients, and objective values are bounded on that horizon. Finite √ first moments of the noise give E vt,i < ∞; the same Cauchy–Schwarz bound and εi > 0 imply integrability of Dt,i , m2t,i /Dt,i , and e2t,i /Dt,i .

13

A.1

Coordinatewise tracking

The descent argument needs the weighted tracking error to be a small fraction of the weighted gradient term, up to noise, initialization, and drift terms. The following estimate provides this form √ by expanding the momentum and splitting its noise at εi / ρ2 . Lemma A.1 (Coordinatewise tracking estimate). For every τ ∈ (0, 1), there exists ρ̄ > 0, depending on p, K, and τ , such that, whenever ρ2 /ρ1 ∈ K and 0 < ρ1 ≤ ρ̄, T X X t=1

T X X X X e20,i e2t,i h2t,i E ≤τ E + C ρ1 T εi + Dt,i Dt,i εi δ p t=1 i i i i

+

!

T X 2 β1 E(ht−1,i − ht,i )2 C X . δp2 t=1 i εi

(26)

Appendix A.3 derives the lemma from the conditional moment assumption. We next control the initial state and the gradient drift.

A.2

Proof of Theorem 4.1

Proof. We first control tracking, then bound the weighted gradient term, and finally recover the unweighted stationarity criterion. Tracking error.

−1 With e0 = −h1 and y = x1 − DL h1 , smooth descent gives

1 1 inf f ≤ f (y) ≤ f (x1 ) − ∥h1 ∥2D−1 + ∥h1 ∥2D−1 = f (x1 ) − ∥h1 ∥2D−1 , L L L 2 2 X e20,i ≤ κ∥h1 ∥2D−1 ≤ 2κ(f (x1 ) − inf f ) ≤ 2κ∆. L ε i i Coordinatewise smoothness, the Adam update, and Dt,i ≥ εi give T X X t=1

T X β 2 (ht−1,i − ht,i )2 E 1 ≤ β12 κ E∥ht−1 − ht ∥2D−1 L ε i t=1 i

≤ β12 η 2 κ

T X

E

t=1

≤ β12 η 2 κ

mt−1,i Dt−1,i

T X X t=1

≤ 2β12 η 2 κ2

! 2 i DL

"

Li (ht,i + et,i )2 E Dt,i Dt,i i

T X X t=1 i

E

#

h2t,i + e2t,i . Dt,i

The shift of the update sum uses m0 = 0. The drift estimate reintroduces tracking error on the right. We make its coefficient small using ηκ ≤ λρ1 . Uniformly over ρ2 /ρ1 ∈ K, choose cδ > 0 with δp ≥ cδ ρ1 for small ρ1 . Fix τ = 1/16 and

14

then λ small enough that Cη 2 κ2 /δp2 ≤ Cλ2 /c2δ ≤ 1/16. Substitution into Lemma A.1 gives T X h2t,i e2t,i τ + Cη 2 κ2 /δp2 X ≤ E E Dt,i 1 − Cη 2 κ2 /δp2 t=1 i Dt,i i

T X X t=1

C + 1 − Cη 2 κ2 /δp2

κ∆ ρ1 T εi + δp i

!

X

X 2 X h2t,i κ∆ ≤ + C ρ1 T εi + E 15 t,i Dt,i ρ1 i

!

T X X h2t,i 1X κ∆ ≤ + C ρ1 T εi + . E 4 t=1 i Dt,i ρ 1 i

!

(27)

Weighted descent. Young’s inequality |ab| ≤ a2 /4 + b2 gives ht,i (ht,i + et,i ) ≥ (3/4)h2t,i − e2t,i . Therefore (27) gives T X X

E

t=1 i

T X ht,i (ht,i + et,i ) ht,i mt,i X E = Dt,i Dt,i t=1 i

≥

T X T X X h2t,i e2t,i 3X E E − 4 t=1 i Dt,i t=1 i Dt,i

T X X h2t,i κ∆ 1X E εi + ≥ − C ρ1 T . 2 t=1 i Dt,i ρ1 i

!

Similarly, T X X

Li E

t=1 i

T X X m2t,i h2t,i + e2t,i ≤ 2κ E 2 Dt,i Dt,i t=1 i T X X h2t,i 5 X κ∆ E ≤ κ + Cκ ρ1 T εi + . 2 t=1 i Dt,i ρ1 i

!

Applying (3) to the Adam update and summing over t now gives ∆≥

T X

E[f (xt ) − f (xt+1 )]

t=1 T X X

≥η

t=1 i

E

T X m2t,i ht,i mt,i η 2 X − Li E 2 Dt,i 2 t=1 i Dt,i

X T X X h2t,i 1 5 κ∆ ≥η − ηκ E − Cη(1 + ηκ) ρ1 T εi + . 2 4 Dt,i ρ1 t=1 i i !



For λ ≤ 1/5, we have ηκ ≤ 1/5, and therefore T X X h2t,i 1X 4∆ Cκ∆ E ≤ + Cρ1 εi + T t=1 i Dt,i ηT ρ1 T i

X (4 + Cλ)∆ ≤ + Cρ1 εi ≤ C ηT i

15

!

X ∆ + ρ1 εi . ηT i

(28)

Write X

S=

εi .

i − 2−p

By (11) and (25), S ≍ Σρ2 2p , η ≍ ρ1 S/L, and ρ1 ≍ ρ2 ≍ ρ⋆ . By the definition of ρ⋆ , 3p−2

∆L , T ∆ ∆L ρ2 S 2 ≍ ≍ 1 = ρ1 S, ηT ρ1 ST ρ1 S

ρ21 S 2 ≍ Σ2 ρ⋆ p

T X h2t,i 1X ≤C E T t=1 i Dt,i



=

∆ + ρ1 S ηT

(29)



≤ Cρ1 S.

Average denominator. We bound past gradient contributions using the weighted gradient term from (29). The recursion and εi > 0 give, for s ≤ t, Dt,i = ρ2

t X

√

t−s

vt,i + εi ≥ β2 2

β2t−s h2s,i = ρ2

t X

β2t−s Ds,i

s=1

s=1

≤ Dt,i ρ2

t X

t−s

β2 2

s=1

√

t−s

vs,i + εi ≥ β2 2 Ds,i ,

h2s,i Ds,i h2s,i . Ds,i

√ Using v0,i = 0, the weighted Euclidean triangle inequality, and 2 ab ≤ a + b, we obtain Dt,i =

ρ2

t X

!1/2

β2t−s (hs,i + ξs,i )2

+ εi

s=1

≤

ρ2

t X

!1/2

β2t−s h2s,i

+ ρ2

t X

!1/2 2 β2t−s ξs,i

+ εi

s=1

s=1

t t t−s h2 X Dt,i ρ2 X s,i 2 ≤ + β2 2 + ρ2 β2t−s ξs,i 2 2 s=1 Ds,i s=1

!1/2

+ εi .

Consequently, t X

Dt,i ≤ ρ2

t−s 2

β2

s=1

t X h2s,i 2 + 2 ρ2 β2t−s ξs,i Ds,i s=1

!1/2

+ 2εi .

(30)

Exchanging the time sums gives ρ2

T X t X t=1 s=1

t−s 2

β2

T −s X h2s,i h2s,i TX k/2 = ρ2 β2 Ds,i Ds,i k=0 s=1

≤

T X h2s,i ρ2 √ 1 − β2 s=1 Ds,i

= (1 +

p

β2 )

T X h2s,i s=1

16

Ds,i

≤2

T X h2s,i s=1

Ds,i

.

(31)

p

For the noise term, subadditivity of z 7→ z 2 , (5), and Lyapunov’s inequality give E ρ2

t X

!1/2 2 β2t−s ξs,i



≤ E ρ2

s=1

t X

!p/2 1/p 2 β2t−s ξs,i



s=1

!1/p t (t−s)p p/2 X ρ2 β2 2 E|ξs,i |p s=1 !1/p p p/2 − 2−p σi ρ2 2p ≤ Cσ ρ ≤ Cεi . i 2 p/2 1 − β2

≤

≤ p/2

Here concavity gives 1 − β2 ≥ (p/2)(1 − β2 ) = (p/2)ρ2 . Combining this noise bound with (30)–(31) proves T X T X h2t,i 1X 1X EDt,i ≤ 2 E T t=1 i T t=1 i Dt,i

p

!

+ CS.

(32)

p

Recovering stationarity. Write |ht,i | = (|ht,i |/ Dt,i ) Dt,i . Cauchy–Schwarz jointly over time, coordinates, and probability, followed by (32) and (29), gives !

RT2 ≤

T X h2t,i 1X E T t=1 i Dt,i

T X 1X EDt,i T t=1 i

!

≤

T X h2t,i 1X E T t=1 i Dt,i

T X h2t,i 1X E 2 + CS T t=1 i Dt,i

!

!

≤ Cρ1 S(ρ1 S + S) ≤ Cρ1 S 2 . Taking square roots gives p−1 √ RT ≤ C ρ1 S ≤ CΣρ⋆ p

∆L = CΣ Σ2 T This proves the theorem. 

A.3

 p−1

p−1

3p−2

p

= C(∆L) 3p−2 Σ 3p−2 T

p−1 − 3p−2

= CR⋆ .

Proof of the coordinatewise tracking estimate

We prove Lemma A.1 by expanding the momentum. The noise decomposition controls small observations through their truncated second moments. For large observations, we retain the random denominator and sum over subsequent iterations using the recursions for mt and vt . Fix a coordinate √ and suppress its index. Write ht = ∂i f (xt ), Dt = vt + ε, and h0 = h1 . The condition on ε is 2−p

σ p ≤ εp ρ2 2 .

(33)

All estimates below are uniform over ρ2 /ρ1 ∈ K for sufficiently small ρ1 , so δp ≍ ρ1 . Put r = ρ2 /ρ1 . Taylor expansion uniformly for r ∈ K gives β12

= (1 − 2ρ1 + ρ21 ) (2−p)/2 β2 

=1− 2−



(2 − p)r 1+ ρ1 + O(ρ21 ) 2

(2 − p)r ρ1 + O(ρ21 ). 2 

17



The coefficient 2 − (2 − p)r/2 has a strictly positive minimum on K; at p = 2 it equals 2. Thus there are constants cδ , Cδ > 0 such that cδ ρ1 ≤ δp ≤ Cδ ρ1 for sufficiently small ρ1 . A.3.1

The accumulated noise

Let nt = ρ1

t X

β1t−s ξs .

s=1

We show that

T X

E

t=1

T X h2 n2t ≤ Cρ1 T ε + Cρ1 ρ2 E t. Dt Dt t=1

(34)

At p = 2, conditional centering makes distinct noise terms orthogonal. Indeed, for s < j, E(ξs ξj ) = E[ξs E(ξj | Fj−1 )] = 0. We first remove the random denominator using Dt ≥ ε, and then apply this orthogonality. Since σ ≤ ε, E

t ρ21 ε n2t ρ2 X 2(t−s) β1 Eξs2 ≤ ≤ 1 ≤ ρ1 ε. Dt ε s=1 1 − β12

This proves (34) at the endpoint. Assume 1 < p < 2 for the rest of this subsection. Small and large noise.

√ Set B = ε/ ρ2 and define

at = ξt 1{|ξt |≤B} − E[ξt 1{|ξt |≤B} | Ft−1 ],

bt = ξt − at .

To see both the centering and the moment bounds, write µt = E[ξt 1{|ξt |≤B} | Ft−1 ] = −E[ξt 1{|ξt |>B} | Ft−1 ]. Then bt = ξt 1{|ξt |>B} + µt , and both at and bt have conditional mean zero. Their moments satisfy E[a2t | Ft−1 ] ≤ E[ξt2 1{|ξt |≤B} | Ft−1 ] ≤ B 2−p σ p ≤ ε2 ,

√ E[|bt | | Ft−1 ] ≤ 2E[|ξt |1{|ξt |>B} | Ft−1 ] ≤ 2B 1−p σ p ≤ 2ε ρ2 .

(35)

For the small-noise sum, remove the denominator before using orthogonality: E

ρ1

t−s
2 s≤t β1 as

≤

ρ21 X 2(t−s) 2 β Eas ε s≤t 1

≤

ρ21 ε ≤ ρ1 ε. 1 − β12

P

Dt

For s < j, bs is Fj−1 -measurable, so   √ E|bs bj | = E |bs |E(|bj | | Fj−1 ) ≤ 2ε ρ2 E|bs | ≤ 4ε2 ρ2 .

Using Dt ≥ ε, the cross terms in the large-noise square satisfy 



2ρ21

|bs bj | β12t−s−j E ≤ 4ερ2 2ρ21 β1t−s β1t−j  D t s<j≤t s<j≤t X

X

2



≤ 4ερ2 ρ1

X s≤t

18

β1t−s  ≤ 4ερ2 .

(36)

A single diagonal term. Put D̄t = single squared noise term by "

E

p

β2 vt−1 + ε and Jt = E[h2t /Dt | Ft−1 ]. First we bound a √



#

ξt2

Ft−1 ≤ Cε 1 +

εp−1 Dt2−p

Indeed, on |ξt | > 2|ht |, the bound Dt ≥

√

ρ2 |ht | D̄t

!2−p  .

(37)

ρ2 |ξt |/2 gives

ξt2

2−p ≤

εp−1 Dt

C|ξt |p 2−p

.

εp−1 ρ2 2

On the complement, use |ξt |2 ≤ (2|ht |)2−p |ξt |p and Dt ≥ D̄t . Both ht and D̄t are Ft−1 -measurable. Thus the conditional contributions of the two events are bounded, respectively, by Cσ p

≤ Cε,

(2−p)/2

εp−1 ρ2

(2|ht |)2−p σ p εp−1 D̄t2−p

√ ≤ Cε

ρ2 |ht | D̄t

!2−p

.

Adding these bounds proves (37). √ To control its gradient-dependent term, use Dt ≤ D̄t + ρ2 |ht + ξt | together with the conditional first-moment bound E[|ξt | | Ft−1 ] ≤ σ to obtain E[Dt | Ft−1 ] ≤ D̄t +

√

ρ2 (|ht | + σ) √ ≤ 2D̄t + ρ2 |ht |.

Here the condition on ε implies denominator bound give

√

1/p

ρ2 σ ≤ ερ2

≤ ε ≤ D̄t . Conditional Jensen and the preceding

h2t E[Dt | Ft−1 ] √ 2 ht D̄t ( ρ2 |ht |/D̄t )2 ≥ = √ √ ρ2 2 + ρ2 |ht |/D̄t 2D̄t + ρ2 |ht | √ D̄t ( ρ2 |ht |/D̄t )2 ≥ . √ 2ρ2 1 + ρ2 |ht |/D̄t

Jt = h2t E[Dt−1 | Ft−1 ] ≥

(38)

For 1 < p < 2 and every x ≥ 0, x2−p ≤ 1 +

2x2 : 1+x

the constant term suffices for x ≤ 1, and for x ≥ 1 use x2−p ≤ x ≤ 2x2 /(1 + x). Applying this √ inequality with x = ρ2 |ht |/D̄t and using ε ≤ D̄t gives √ ε

ρ2 |ht | D̄t

!2−p

√ √ 2ε( ρ2 |ht |/D̄t )2 2D̄t ( ρ2 |ht |/D̄t )2 ≤ε+ ≤ε+ ≤ ε + 4ρ2 Jt . √ √ 1 + ρ2 |ht |/D̄t 1 + ρ2 |ht |/D̄t

√ In the decomposition of bt , conditional centering gives |µt | ≤ B 1−p σ p ≤ ε ρ2 . The centering correction contributes at most µ2t µ2t ≤ ≤ ερ2 . ε εp−1 Dt2−p 19

Combining b2t ≤ 2ξt2 + 2µ2t with (37) and the preceding bounds gives "

E

#

b2t εp−1 Dt2−p

"

#

ξt2

Ft−1 ≤ 2E

2µ2t ε

Ft−1 +

εp−1 Dt2−p !2−p  √ ρ2 |ht |  + 2ερ2 ≤ Cε + Cρ2 Jt . ≤ Cε 1 + D̄t 

(39)

t−s

Summing over time. with Dt ≥ ε, this yields

For t ≥ s, the second-moment recursion gives Dt ≥ β2 2 Ds . Together b2s b2 b2s = p−1 s 2−p ≤ Dt Dt Dt εp−1 Dt2−p −

≤ β2 (2−p)/2

Using β12 /β2

b2s

(t−s)(2−p) 2

εp−1 Ds2−p

.

= 1 − δp and EJs = E[h2s /Ds ], summation gives T X X 2(t−s) 2

β1

ρ1

t=1 s≤t

k



−s T TX X b2 β12  b2s  2−p E s ≤ ρ21 E Dt εp−1 Ds2−p s=1 k=0 β2 2

Cρ21 ≤ δp

T X

h2 E s T ε + ρ2 Ds s=1

!

.

To combine the estimates, write nt as its small- and large-noise sums and use (x + y)2 ≤ 2x2 + 2y 2 . Within the large-noise square, bound the cross terms in absolute value by (36). This gives T X

n2 Cρ21 E t ≤ C(ρ1 + ρ2 )T ε + Dt δp t=1 ≤ Cρ1 T ε + Cρ1 ρ2

T X s=1

E

T X

h2 T ε + ρ2 E s Ds s=1 h2s . Ds

This proves (34). A.3.2

Initialization and gradient drift

Expanding (23) gives et = β1t e0 +

t X

β1t−s+1 (hs−1 − hs ) + nt .

s=1

The initial contribution obeys T X

T e2 X e2 β12 e20 β 2t e2 E 1 0 ≤ 0 β12t ≤ 0 ≤ . Dt ε t=1 ε 1 − β12 ερ1 t=1

20

!

For the drift, put ds = hs−1 − hs . Using Dt ≥ ε and weighted Cauchy–Schwarz gives T X t=1

t−s+1 ds s≤t β1 Dt

P

E



2





T X X β2 X  ≤ 1 β1t−s   β1t−s Ed2s  ε t=1 s≤t s≤t T X β12 X β t−s Ed2s ≤ ερ1 t=1 s≤t 1

=

T T X β12 X β1t−s Ed2s ερ1 s=1 t=s

≤

T β12 X E(hs−1 − hs )2 . ερ21 s=1

Apply (x + y + z)2 ≤ 3(x2 + y 2 + z 2 ) to the three terms in et . The preceding estimates and (34) yield T X

E

t=1

T T X h2 e2t Ce20 Cβ12 X E t + Cρ1 T ε + ≤ Cρ1 ρ2 + E(ht−1 − ht )2 . 2 Dt D ερ ερ t 1 1 t=1 t=1

Choose ρ1 small enough that Cρ1 ρ2 ≤ τ . This is possible uniformly over ρ2 /ρ1 ∈ K. Using δp ≍ ρ1 and summing over coordinates proves (26).

A.4

Shared ε: balanced scales and fixed dimension

For Corollary 4.3, (15) and the common choice of εi give − 2−p εi ≥ ρ2 2p max



Li σi , Σ , L 

X

− 2−p

εi = C0 ρ2 2p Σ.

i 2−p

These are the two bounds on εi used in (25). In particular, κ ≤ (L/Σ)ρ22p and ηκ ≤ λρ1 still hold. Thus the descent estimate and the denominator estimate in Appendix A.2 give T X h2t,i 1X E ≤C T t=1 i Dt,i

and RT2 ≤



∆ + ρ1 S , ηT

T X h2t,i 1X E T t=1 i Dt,i



!

− 2−p

S = C0 Σρ2 2p ,

T X h2t,i 1X 2 E + CS . T t=1 i Dt,i

!

Summing the balance inequalities shows C0 ≥ 1. The same prescribed η and ρ1 = ρ⋆ satisfy − 2−p

∆/(ηT ) ≲ ρ1 Σρ2 2p ≤ ρ1 S. Consequently, RT2 ≤ Cρ1 S(ρ1 S + S) ≤ Cρ1 S 2 , RT ≲

2−p √ 1/2 − (p−1)/p ρ1 S = C0 Σρ1 ρ2 2p ≍ C0 Σρ⋆ = C0 R⋆ ,

as claimed.

21

Fixed dimension. For arbitrary coordinate scales, (15) holds with C0 = d, since maxi σi ≤ Σ and − 2−p

maxi Li ≤ L. Corollary 4.3 therefore applies with the shared choice ε = Σρ2 2p and the remaining parameters of Theorem 4.1. The preceding estimate is linear in C0 , so setting C0 = d gives p−1

p

RT ≤ Cd(∆L) 3p−2 Σ 3p−2 T

p−1 − 3p−2

whenever ρ⋆ ≤ c, with C depending only on p and K. At every fixed dimension, a shared ε thus attains the benchmark time exponent uniformly over coordinate scales, with a factor linear in d.

Proof of the lower bound for a shared ε

B

We give the objective, oracle, and pathwise invariant for Theorem 4.2.

B.1

Parameters and objective

Fix 0 < δ ≤ min{δ0 , T

− p−1 p

} and set

1 γ= , 128

N = ⌈δ

−1

⌉,

γ A= , N

√ γ δ b= . N

(40)

Let z = (u, w1,+ , w1,− , . . . , wN,+ , wN,− ), write si =

wi,+ + wi,− , 2

and define Y (z) = 1 + γδ u + b

N X

si .

(41)

i=1

Let

  0, 

y ≤ 0,

2 ϕ(y) = y2 , 

 y − 1 , 2

0 < y < 1, y ≥ 1,

f (z) = ϕ(Y (z)).

(42)

The function ϕ is convex and continuously differentiable, with ϕ′ (y) = min{1, max{0, y}}. Since ϕ ≥ 0 and Y (z) can take any real value, inf f = 0. At z1 = 0, Y (z1 ) = 1, so 1 f (z1 ) − inf f = . 2

(43)

Let ϱ be the coefficient vector in (41), with ϱ0 = γδ and ϱi,+ = ϱi,− = b/2. The chain rule gives ∇f (z) = ϕ′ (Y (z))ϱ. Whenever Y (z) ≥ 1, √ √ ∇f (z) = ϱ, ∥∇f (z)∥1 = γδ + N b = γδ + γ δ ≥ γ δ. (44)

B.2

Sample-function construction

Let θ = 1/(8T ). Independently over time, define a random vector qt as follows. Its control coordinate is ( −γδ, with probability 1 − θ, qt,0 = (45) 2 γδ( θ − 1), with probability θ. 22

Draw one sign ζt ∈ {−1, 1} with equal probabilities, independently of the control coordinate, and use it for all pairs: ( (A + b, −A), ζt = 1, + − (qt,i , qt,i ) = (46) (−A, A + b), ζt = −1. The two coordinates therefore receive a uniformly random permutation of {A + b, −A}. Their means satisfy   2 Eqt,0 = (1 − θ)(−γδ) + θγδ − 1 = γδ, θ (47) b (A + b) + (−A) ± = , hence Eqt = ϱ. Eqt,i = 2 2 Put ωt = qt − ϱ and define the random sample function Ft (z) = f (z) + ⟨ωt , z⟩.

(48)

Every Ft is convex and continuously differentiable, and its gradient gt (z) = ϕ′ (Y (z))ϱ + ωt

(49)

satisfies E[gt (z)] = ∇f (z). The noise ωt is independent of z and of the past. Appendix B.6 verifies its coordinatewise pth moments. Define the event A = {qt,0 = −γδ for every 1 ≤ t ≤ T }. (50) The union bound gives 7 Pr(A) = (1 − θ)T ≥ 1 − T θ = . 8

B.3

(51)

Averaging coefficients for a realized history

For the time-varying β1,t , β2,t in (9), define, for 1 ≤ s ≤ t, αt,s = (1 − β1,s )

t Y

νt,s = (1 − β2,s )

β1,r ,

r=s+1

Pt =

t X

t Y

β2,r ,

(52)

r=s+1

αt,s ,

Vt =

t X

νt,s .

(53)

s=1

s=1

These coefficients are nonnegative. Iterating the two moment recursions from m0 = v0 = 0 gives mt,j =

t X

αt,s gs,j ,

vt,j =

s=1

t X

2 νt,s gs,j .

s=1

In particular, αt,t = 1 − β1,t > 0 and νt,t = 1 − β2,t > 0, so Pt , Vt > 0. Suppose Y (zs ) ≥ 1 for s ≤ t. Then (49) equals qs at those iterates. On A, the control coordinate therefore satisfies mt,0 = −γδPt , vt,0 = γ 2 δ 2 Vt . (54) The resulting contribution to Y is γδ(ut+1 − ut ) =

η t γ 2 δ 2 Pt γ 2 δηt Pt √ = √ . γδ Vt + εt γ Vt + εδt 23

(55)

B.4

Proof of the paired-update lemma

Proof of Lemma 5.1. Suppress the pair and time indices. Since each observation pair sums to b and its difference has magnitude 2A + b, m+ + m− = bP,

|m+ − m− | ≤ (2A + b)P.

Each squared observation lies between A2 and (A + b)2 , so √ √ A V + εt ≤ D± ≤ (A + b) V + εt . Since A, V > 0, both denominators are positive even when εt = 0. If ℓ ≤ d2 ≤ d1 ≤ u and ℓ > 0, then (d1 − d2 )/(d1 + d2 ) ≤ (u − ℓ)/(u + ℓ): the ratio increases with d1 and decreases with d2 . Applying this to the preceding interval, √ |(D+ )−1 − (D− )−1 | b |D+ − D− | b V √ ≤ = ≤ . (56) + −1 − −1 + − (D ) + (D ) D +D 2A + b (2A + b) V + 2εt The potentially negative term in the normalized pair sum satisfies m+ − m − 2



1 1 − − + D D



(2A + b)P b 1 1 ≤ + − + 2 2A + b D D   1 1 bP + − . = + 2 D D 



Consequently, m+ m− + − D+ D     1 1 m+ − m − 1 1 bP + + − = 2 D+ D− 2 D+ D−   1 1 2bP ≤ bP + − ≤ √ . + D D A V + εt

0≤

B.5

The iterates remain in the affine region

On A, suppose Y (zs ) ≥ 1 for s ≤ t. The mean of pair i changes by ηt st+1,i − st,i = − 2

m+ t,i + Dt,i

+

m− t,i − Dt,i

!

.

Lemma 5.1 bounds their total contribution by 0 ≤ −b

N X

(st+1,i − st,i ) ≤

i=1

γ 2 δηt Pt N b2 ηt Pt √ = √ . A Vt + εt γ Vt + N εt

(57)

Combining this with (55) gives Y (zt+1 ) − Y (zt ) = γδ(ut+1 − ut ) + b

N X

(st+1,i − st,i )

i=1

"

≥ γ 2 δηt Pt

#

1 1 √ √ ≥ 0. εt − γ Vt + δ γ Vt + N ε t 24

(58)

The bracket is nonnegative because N ≥ δ −1 . At z1 = 0, Y (z1 ) = 1. Suppose inductively that Y (zs ) ≥ 1 for s ≤ t. The preceding calculation gives Y (zt+1 ) ≥ Y (zt ) ≥ 1. On A, √ Y (zt ) ≥ 1 and ∥∇f (zt )∥1 ≥ γ δ (1 ≤ t ≤ T ). (59) Using (51),

√ T √ 7 δ 1X . E∥∇f (zt )∥1 ≥ Pr(A)γ δ ≥ T t=1 8 128

(60)

To complete the proof, we verify Assumptions 3.1 and 3.3 with L ≤ 1 and Σ ≤ 1 in the next subsection.

B.6

Verification of the lower-bound assumptions

We verify the two quantitative assumptions in Theorem 4.2. Equation (43) gives the initial-gap bound. B.6.1

Coordinatewise smoothness

Set L⋆j = ∥ϱ∥1 ϱj .

(61)

All coordinates of ϱ are positive. Substituting the definition of L⋆j gives X ϱ2j

1

X

X

L⋆j = ∥ϱ∥1

X

ϱj = ∥ϱ∥21 .

(62)

∥∇f (z ′ ) − ∇f (z)∥(DL⋆ )−1 = |ϕ′ (Y (z ′ )) − ϕ′ (Y (z))|∥ϱ∥(DL⋆ )−1

(63)

j

= L⋆j ∥ϱ∥1

ϱj = 1,

j

j

j

Because ϕ′ in (42) is 1-Lipschitz,

≤ |⟨ϱ, z ′ − z⟩|

(64) ′

If δ0 ≤ 1, then ∥ϱ∥1 = γ(δ + B.6.2

√

≤ ∥ϱ∥(DL⋆ )−1 ∥z − z∥DL⋆

(65)

= ∥z ′ − z∥DL⋆ .

(66)

δ) ≤ 2γ = 1/64. Thus L⋆ satisfies Assumption 3.1 and ∥L⋆ ∥1 ≤ 1.

Coordinatewise moment bounds

The oracle noise is ωt = qt − ϱ. In the control coordinate it equals −2γδ on the common outcome and 2γδ(1/θ − 1) on the rare outcome. Therefore   1 E|ωt,0 |p = (2γδ)p (1 − θ) + θ( − 1)p θ  p 1−p = (2γδ) (1 − θ) + θ (1 − θ)p

≤ (2γδ)p (1 + θ1−p ).

25

(67)

Choosing σ0 = (E|ωt,0 |p )1/p , we obtain σ0 ≤ 2γδ(1 + θ1−p )1/p ≤ 2γδ(1 + θ   p−1 δ p 1 + (8T ) = 64 1 + 8(p−1)/p 9 ≤ ≤ . 64 64

− p−1 p

) (68) (69)

Here δ ≤ 1 and δT (p−1)/p ≤ 1 by the choice of δ. In pair i, each coordinate has mean b/2. Its two centered outcomes are (A + b) − b/2 = A + b/2 and −A − b/2 = −(A + b/2), each with probability 1/2. Thus its pth absolute moment is exactly (A + b/2)p . We may take σi,+ = σi,− = A + b/2. From (40), N X

(σi,+ + σi,− ) = 2N A + N b

i=1

√

(70)

3 . (71) 128 The sampling at time t is independent of Ft−1 , so these unconditional moment calculations also hold conditionally, as required by Assumption 3.3. Combining (69) and (71) gives = γ(2 +

Σ = σ0 +

N X

(σi,+ + σi,− ) ≤

i=1

δ) ≤

9 3 21 + = < 1. 64 128 128

(72)

This completes the proof of Theorem 4.2.

C

One-dimensional optimality for fixed-parameter Adam

When d = 1, shared and coordinatewise choices of ε coincide. We record the corresponding family-specific minimax statement as a supplementary result. Proposition C.1 (Minimax rate within a fixed-parameter Adam family). Fix p ∈ (1, 2] and let K be a compact subset of (0, 4/(2 − p)) when p < 2, or of (0, ∞) when p = 2. There exist c, C, ρ̄, λ̄ > 0, depending only on p and K, such that, for each fixed ratio r = ρ2 /ρ1 ∈ K, the admissible parameters satisfy ρ2 = rρ1 ≤ 12 , 0 < ρ1 ≤ ρ̄, 0 < λ ≤ λ̄, − 2−p

λρ1 Σρ2 2p λρ1 ε η= = . L L

− 2−p ε = Σρ2 2p ,

(73)

Whenever ρ⋆ ≤ c and T ρ⋆ ≥ C, T p−1 p 1X − p−1 inf sup E|f ′ (xt )| ≍ (∆L) 3p−2 Σ 3p−2 T 3p−2 . ρ1 ,λ f,O T t=1

The infimum is over (ρ1 , λ) satisfying (73), and the supremum is over scalar objective–oracle pairs satisfying Assumptions 3.1–3.3. The comparison is uniform over r ∈ K. − 2−p

In one dimension, (11) gives ε = Σρ2 2p . The upper half of Proposition C.1 follows directly from Theorem 4.1. For the matching lower bound, we use sparse observations and measure each nonzero observation by the total displacement it induces. Small displacements limit travel, while large displacements permit a two-sign comparison with identical denominators. 26

C.1

Lower-bound construction

Fix r ∈ K and a pair (ρ1 , λ) satisfying (73). We show that every such pair has worst-case stationarity at least a constant multiple of R⋆ . Choose fixed small constants α, µ > 0 and set θ = αρ⋆ , (p−1)/p

Since R⋆ = Σρ⋆

A = µΣθ

− p1

,

H = θA.

(74)

, p−1

3p−2

p−1

T ρ⋆ R⋆2 = T Σ2 ρ⋆ p

H = θA = µΣθ p = µα p R⋆ ,

= ∆L.

Fix α, µ small enough that θ ≤ 1/2 and µ ≤ 1/2 under (73) and ρ⋆ ≤ c. Define 1 1 , ψ(y) = clip y, − , 2 2 



f ′ (z) = Hψ



Lz . H 

(75)

This derivative is nondecreasing and L-Lipschitz, so f is convex and L-smooth: |f ′ (z) − f ′ (z ′ )| ≤ H|Lz/H − Lz ′ /H| = L|z − z ′ |. Integrating and normalizing f (0) = 0 gives (

f (z) =

Lz 2 /2, H|z|/2 − H 2 /(8L),

|z| ≤ H/(2L), |z| ≥ H/(2L).

Thus inf f = f (0) = 0. Start from z1 =

H + W, 2L

W =

∆ . H

(76)

Since f ′ (z) = H/2 for z ≥ H/(2L), H 2 HW H2 ∆ + = + 8L 2 8L 2 2 2(p−1)/p µ α ∆ = ≤ ∆. ∆+ 8T ρ⋆ 2

f (z1 ) − inf f =

(77)

The gap bound holds for T ρ⋆ ≥ C and sufficiently small α and µ. At time t, independently draw Bt ∼ Bernoulli(θ). Conditional on Bt = 1 and the past, draw ζt ∈ {−1, 1} with 1+ψ Pr(ζt = 1 | Ft−1 , Bt = 1) =



Lzt H

2

Then



E[gt | Ft−1 ] = θAψ

Lzt H





,

gt = Bt Aζt .

= f ′ (zt ).

(78)

(79)

The denominator process depends only on the variables Bt , because gt2 = Bt A2 . Since |ψ| ≤ 1/2, both signs have conditional probability at least 1/4 whenever Bt = 1.

27

C.2

Displacement from one nonzero observation

Starting from m = v = 0, give the algorithm one observation A and zeros thereafter. The total absolute displacement of this trajectory is D=η

∞ X

ρ1 Aβ1k q

k=0

Set χ=

.

(80)

ρ2 A2 β2k + ε LD . H

(81)

Since every denominator in (80) is at least ε, D≤

∞ ηA ηρ1 A X βk = , ε k=0 1 ε

(82)

LD LηA Lη ρ1 χ= ≤ = =λ . H Hε θε θ

C.3

Small-displacement case

Suppose χ ≤ χ0 . Let τ1 , . . . , τN be the times at which Bt = 1. Write the first moment as the sum of the signed contributions from these observations. At every time t, (j)

N X |mt | |m | q t ≤ . √ (j) vt + ε j=1 vt + ε (j)

Here, for t ≥ τj , mt Thus mt =

t−τj

= ρ1 Aζτj β1

(j)

and vt

P (j) (j) j mt and vt = j vt .

P

t−τj

= ρ2 A2 β2

(83)

; both contributions are zero before τj .

The displayed inequality follows because |mt | ≤

(j) j |mt |

P

(j)

and the full second moment is at least each nonnegative contribution vt . Summing over time and extending each individual displacement contribution to an infinite horizon gives the pathwise bound T X

|zt+1 − zt | ≤ N D.

(84)

t=1

Since EN = T θ, Markov’s inequality gives T θD T θH 2 =χ W ∆L 2(p−1) T αρ⋆ µ2 α2(p−1)/p R⋆2 1+ p =χ = χµ2 α . 2 T ρ⋆ R⋆

Pr(N D ≥ W ) ≤

(85)

Choose α, µ and then χ0 so that (85) is at most 1/4. On the complementary event, (84) and (76) imply zt ≥ H/(2L) for every t, so |f ′ (zt )| = H/2. Hence T 1X 3 E|f ′ (zt )| ≥ H ≥ cR⋆ . T t=1 8

28

(86)

C.4

Large-displacement case

Suppose χ > χ0 . Put q = ρ2 /θ. Equation (82) and (73) imply q=r

(inf K)χ0 ρ1 ≥ =: q0 > 0. θ λ̄

(87)

We first show that a block of length O(1/θ) captures a fixed fraction of (80). Lemma C.2 (Finite-horizon displacement bound). Fix q0 > 0. There are constants B, c > 0, −1 depending only on p, K, q0 , with the following property. Let θ > 0, ρ2 /θ ≥ q0 , and A = µΣθ p . Consider a block of length ℓ = ⌈B/θ⌉. Suppose its initial second-moment state satisfies v ≤ 4θA2 , there is no nonzero observation in the first quarter, exactly one observation ζA in the second quarter, and no other nonzero observation. For every time in the last quarter, the positions obtained with ζ = 1 and ζ = −1 differ by at least 2cD(θ, A), where D(θ, A) is defined as in (80). The bound is independent of the initial position and first-moment state. Proof. Let Dn (θ, A) = η

n−1 X

ρ1 Aβ1j q

ρ2 A2 β2j + ε

j=0

D(θ, A) = lim Dn (θ, A).

,

n→∞

− 2−p

Writing q = ρ2 /θ and using ε = Σρ2 2p gives √

1 ρ2 A ρ2 = µρ2p θ−1/p = µ ε θ



Let



j0 = j/2

Here log+ u = max{0, log u}. Since β2 √

1/p

= µq 1/p .

(88)

 1 2 log+ 2µq p . ρ2 

≤ e−ρ2 j/2 , for j ≥ j0 we have j/2

ρ2 Aβ2 ε

1 ≤ µq 1/p e−ρ2 j0 /2 ≤ . 2

For j ≥ j0 , the square-root term in the denominator is at most ε/2. Summing only the terms with j ≥ j0 gives ∞ 2ηρ1 A X 2ηA j0 ηA j0 D(θ, A) ≥ β1j = β1 ≥ c β . (89) 3ε j=j 3ε ε 1 0

Also, D(θ, A) − Dn (θ, A) ≤

∞ ηρ1 A X ηA n β1j = β . ε j=n ε 1

Hence Dn (θ, A) ≥ D(θ, A)/2 whenever n ≥ j0 + C/ρ1 . Indeed, D − Dn 3 3 1 ≤ β1n−j0 ≤ e−ρ1 (n−j0 ) ≤ D 2 2 2 as soon as n − j0 ≥ (log 3)/ρ1 .

29

(90)

Both terms in this lower bound for n are O(1/θ): j0 ≤ 1 +

r 1 sup K = ≤ . ρ1 qθ q0 θ

C(1 + log+ q) C ≤ , qθ θ

The function (1 + log+ q)/q is bounded on [q0 , ∞), and θ = ρ2 /q ≤ 1/(2q0 ) absorbs the constant 1 in the bound for j0 . Partition each block into four consecutive sets with endpoints ⌊jℓ/4⌋, j = 0, . . . , 4. Choose B large enough that a nonzero observation in the second quarter precedes every time in the last quarter by at least this many iterations. Such a choice is possible since t − s ≥ ℓ/4 − 1 for these two quarters. Now account for the inherited second moment. If the observation occurs at time s, then for j ≥ 0 the two sign trajectories have the same denominator and (ζ)

ms+j = β1j+1 ms−1 + ρ1 Aβ1j ζ, vs+j = β2j (β2 vs−1 + ρ2 A2 ). Since vs−1 ≤ 4θA2 and ρ2 /θ ≥ q0 , 

β2 vs−1 + ρ2 A2 ≤ 1 +

4 ρ2 A2 . q0 

The inherited numerator is identical for the two signs and cancels when their positions are subtracted. The inherited second moment satisfies √

vs+j + ε ≤

q

1 + 4/q0

q

ρ2 A2 β2j + ε



.

Since the trajectories agree at time s, their separation is therefore (+)

|zt

(−)

− zt

| = 2ηρ1 A

t−s−1 X j=0

√

β1j vs+j + ε

X 2ηρ1 A t−s−1 β1j q ≥p 1 + 4/q0 j=0 ρ A2 β j + ε 2

2

1 2 =p Dt−s (θ, A) ≥ p D(θ, A). 1 + 4/q0 1 + 4/q0 The truncation estimate applies because t − s exceeds the number of iterations required to capture half of D. This proves the lemma. Partition the horizon into complete blocks of length ℓ = ⌈B/θ⌉. Since Evt = β2 Evt−1 + ρ2 θA2 ,

Evt = ρ2 θA2

t−1 X j

β2 = θA2 (1 − β2t ) ≤ θA2 ,

j=0

Markov’s inequality shows that a block starts with v ≤ 4θA2 with probability at least 3/4: for a block starting at step t0 , Pr(vt0 −1 > 4θA2 ) ≤ Evt0 −1 /(4θA2 ) ≤ 1/4. The future Bernoulli variables are independent of this event. Let I2 denote the second quarter of the block. Increase B so that

30

ℓ ≥ 8. Then |I2 | ≥ ℓ/8, B ≤ ℓθ ≤ B + 1, and θ ≤ 1/2. The probability of exactly one nonzero observation in the second quarter and none elsewhere in the block is bounded by ℓθ −2θ(ℓ−1) e 8 B ≥ e−2(B+1) ≥ c > 0. 8

|I2 |θ(1 − θ)ℓ−1 ≥

(91)

The first inequality uses log(1 − θ) ≥ −2θ. Thus the joint event consisting of a small initial second moment and the prescribed observation pattern has probability at least c > 0. Fix the history before a block with v ≤ 4θA2 , and condition on its Bernoulli pattern and on the time s of the unique observation. Before s the two sign trajectories coincide, and after s all oracle observations in this block are zero. The remaining randomness relevant to their positions is the sign ζ at time s. For every t in the last quarter, Lemma C.2 gives (ζ)

Lzt H

= Ct − ζas,t ,

as,t ≥ c

LD ≥ cχ0 , H

(92)

where Ct is the midpoint of the two scaled positions and is fixed under this conditioning. For every C ∈ R and a ≥ 0,   1 |ψ(C − a)| + |ψ(C + a)| ≥ min 2a, . (93) 2 To verify this inequality, if either |C − a| or |C + a| is at least 1/2, its clipped magnitude is 1/2. Otherwise both terms are unclipped, and |C − a| + |C + a| ≥ |(C + a) − (C − a)| = 2a. At time s, both signs have conditional probability at least 1/4. The future Bernoulli variables are independent of this sign, so conditioning on the rest of the pattern preserves that probability bound. Writing Eζ for expectation over these two signs, we therefore have
H |ψ(Ct − as,t )| + |ψ(Ct + as,t )| 4 H ≥ min{2cχ0 , 1/2}. 4

Eζ |f ′ (zt )| ≥

Integrating over the histories and patterns, whose joint probability is at least c > 0, yields E|f ′ (zt )| ≥ cH at each time in the last quarter of a complete block. There are M = ⌊T /ℓ⌋ complete blocks, each with at least ℓ/8 such times. The assumption T θ ≥ C ensures T ≥ 2ℓ after increasing C, since ℓ ≤ (B + 1)/θ. Hence M ≥ T /(2ℓ), and T 1X cH Mℓ E|f ′ (zt )| ≥ cH ≥ ≥ cR⋆ . T t=1 8T 16

C.5

(94)

Sample functions and the moment bound

To construct sample functions for (78), draw Ut ∼ Unif[−1, 1] independently and define, for every query point z,   Lz ζt (z) = sign(ψ − Ut ), gt (z) = Bt Aζt (z). (95) H The function z 7→ gt (z) is nondecreasing. Hence Ft (z) = 0z gt (y) dy is convex and has gt as a subgradient everywhere (and as its derivative except at finitely many points). Also, Pr(Ut < R

31

ψ(Lz/H)) = (1 + ψ(Lz/H))/2, and therefore EU ζt (z) = ψ(Lz/H). Independence of Bt and Ut proves (79). Finally, E[|gt |p | Ft−1 ] = θAp and |f ′ (zt )| ≤ H/2 ≤ H. Thus E[|gt − f ′ (zt )|p | Ft−1 ] ≤ 2p−1 (θAp + H p ) p

p

p p

p

(96) p

≤ 2 θA = 2 µ Σ ≤ Σ

(97)

after choosing µ ≤ 1/2. Equations (86) and (94) cover all admissible (ρ1 , λ) and prove Proposition C.1.

32

Related documents

• Saddle Point Approximation and Central Limit Theorem for Densities in High Dimensions#1155069
• Uniform convergence at optimal rate and scale#1388902
• A Weighted Kolmogorov Metric under Sub-Cubic Moments: Admissible Parameters and an Obstruction#793546
• A Weighted Kolmogorov Metric under Sub-Cubic Moments: Admissible Parameters and an Obstruction#789542
• Bias-variance decompositions: the exclusive privilege of Bregman divergences#1075972