Paper deep dive
Tail-Aware Information-Theoretic Generalization for RLHF and SGLD
Huiming Zhang, Binghan Li, Wan Tian, Qiang Sun
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 4/14/2026, 2:24:28 AM
Summary
The paper introduces a tail-dependent information-theoretic framework for generalization bounds in machine learning, specifically addressing heavy-tailed distributions (sub-Weibull) where classical KL-based mutual information and MGF-based tools fail. The authors develop a shifted-log f-divergence and a decorrelation lemma to bound generalization gaps, establish sharp maximal inequalities and Dudley-type chaining bounds for sub-Weibull processes, and apply these to Rényi-regularized RLHF and SGLD.
Entities (5)
Relation Signals (3)
sub-Weibull processes → analyzedvia → Dudley-type chaining bound
confidence 95% · We establish sharp maximal inequalities and a Dudley-type chaining bound for sub-Weibull processes
RLHF → regularizedby → Rényi divergence
confidence 92% · We illustrate the consequences in Rényi-regularized RLHF under heavy-tailed rewards
shifted-log f-divergence → bounds → Generalization Gap
confidence 90% · We develop a tail-dependent information-theoretic framework... bounds change-of-measure expectations using a shifted-log fθ-divergence
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Classical information-theoretic generalization bounds typically control the generalization gap through KL-based mutual information and therefore rely on boundedness or sub-Gaussian tails via the moment generating function (MGF). In many modern pipelines, such as robust learning, RLHF, and stochastic optimization, losses and rewards can be heavy-tailed, and MGFs may not exist, rendering KL-based tools ineffective. We develop a tail-dependent information-theoretic framework for sub-Weibull data, where the tail parameter $\theta$ controls the tail heaviness: $\theta=2$ corresponds to sub-Gaussian, $\theta=1$ to sub-exponential, and $0<\theta<1$ to genuinely heavy tails. Our key technical ingredient is a decorrelation lemma that bounds change-of-measure expectations using a shifted-log $f_\theta$-divergence, which admits explicit comparisons to Rényi divergence without MGF arguments. On the empirical-process side, we establish sharp maximal inequalities and a Dudley-type chaining bound for sub-Weibull processes with tail index $\theta$, with complexity scaling as $\log^{1/\theta}$ and entropy$^{1/\theta}$. These tools yield expected and high-probability PAC-Bayes generalization bounds, as well as an information-theoretic chaining inequality based on multiscale Rényi mutual information. We illustrate the consequences in Rényi-regularized RLHF under heavy-tailed rewards and in stochastic gradient Langevin dynamics with heavy-tailed gradient noise.
Tags
Links
- Source: https://arxiv.org/abs/2604.10727v1
- Canonical: https://arxiv.org/abs/2604.10727v1
Trouble viewing inline? Open PDF directly →
Full Text
222,738 characters extracted from source content.
Expand or collapse full text
Tail-Aware Information-Theoretic Generalization for RLHF and SGLD Huiming Zhang Institute of Artificial Intelligence, Beihang University; Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing; Email: zhanghuiming@buaa.edu.cn Binghan Li Huiming Zhang and Binghan Li are co-first authors. Institute of Artificial Intelligence, Beihang University; Email: 22421018@buaa.edu.cn. Wan Tian Advanced Institute of Information Technology, Peking University; Wangxuan Institute of Computer Technology, Peking University; Email: wantian61@pku.edu.cn. Qiang Sun Computer and Mathematical Sciences, Computer Science, and Statistics, University of Toronto and MBZUAI; Email: qsunstats@gmail.com. Abstract Classical information-theoretic generalization bounds typically control the generalization gap through KL-based mutual information and therefore rely on boundedness or sub-Gaussian tails via the moment generating function (MGF). In many modern pipelines, such as robust learning, RLHF, and stochastic optimization, losses and rewards can be heavy-tailed, and MGFs may not exist, rendering KL-based tools ineffective. We develop a tail-dependent information-theoretic framework for sub-Weibull data, where the tail parameter θ controls the tail heaviness: θ=2θ=2 corresponds to sub-Gaussian, θ=1θ=1 to sub-exponential, and 0<θ<10<θ<1 to genuinely heavy tails. Our key technical ingredient is a decorrelation lemma that bounds change-of-measure expectations using a shifted-log fθf_θ-divergence, which admits explicit comparisons to Rényi divergence without MGF arguments. On the empirical-process side, we establish sharp maximal inequalities and a Dudley-type chaining bound for sub-Weibull processes with tail index θ, with complexity scaling as log1/θ ^1/θ and entropy1/θ. These tools yield expected and high-probability PAC-Bayes generalization bounds, as well as an information-theoretic chaining inequality based on multiscale Rényi mutual information. We illustrate the consequences in Rényi-regularized RLHF under heavy-tailed rewards and in stochastic gradient Langevin dynamics with heavy-tailed gradient noise. Keywords: heavy-tailed distributions, sub-Weibull processes, Rényi divergence, information-theoretic generalization bounds, RLHF 1 Introduction The generalization gap, namely the difference between population risk and empirical risk, has traditionally been analyzed by uniform-convergence arguments based on classical complexity measures such as VC dimension and Rademacher or Gaussian complexity; see Koltchinskii (2011); Wainwright (2019); Shalev-Shwartz and Ben-David (2014). While powerful, these tools are inherently worst-case: they control an entire hypothesis class rather than the smaller, sample-dependent region actually explored by a modern learning algorithm. As a result, they can be overly pessimistic for data-adaptive procedures, which often generalize well even when the ambient class has large worst-case complexity (Zhou et al., 2021). Information-theoretic generalization bounds replace global complexity by an algorithm-dependent quantity: how much information the algorithm’s output reveals about the sample (Xu and Raginsky, 2017; Russo and Zou, 2020; Bu et al., 2020). In light-tailed settings, under sub-Gaussian assumptions, KL-based mutual information yields clean bounds in expectation and with high probability, and these guarantees can be further sharpened through multiscale or chaining arguments (Asadi et al., 2018; Hellström et al., 2025). A major obstacle is that KL-based arguments are tightly coupled to moment generating functions (MGFs). Many modern pipelines, however, exhibit heavy-tailed behavior, so the relevant MGFs may fail to exist. This issue arises in reward-model scores for RLHF (Kwa et al., 2024), gradient noise in large-scale optimization (Raj et al., 2023), and losses induced by heavy-tailed data (Lerasle, 2019; Xu et al., 2023). In such settings, KL mutual information can remain small even when rare but extreme events dominate generalization or stability; see Example 4.1.1. A convenient tail model that interpolates between sub-Gaussian and heavy-tailed behavior is the sub-Weibull family. A random variable X is called sub-Weibull with parameter θ>0θ>0, denoted X∼subW(θ)X (θ), if its Orlicz norm ‖X‖ψθ\|X\|_ _θ is finite, where ψθ(x)=exp(xθ)−1 _θ(x)= (x^θ)-1. Equivalently, there exists K>0K>0 such that exp(|X|θ/Kθ)≤2E (|X|^θ/K^θ)≤ 2. Sub-Weibull variables also satisfy the tail estimate ℙ(|X|≥t)≤2exp(−tθ/Kθ),t≥0,P(|X|≥ t)≤ 2 (-t^θ/K^θ ), t≥ 0, (1.1) for some K>0K>0. The θ controls tail thickness: θ=2θ=2 corresponds to sub-Gaussian tails, θ=1θ=1 to sub-exponential tails, and 0<θ<10<θ<1 to genuinely heavy-tailed regimes. Our focus is on deriving information-theoretic generalization tools that remain meaningful throughout the sub-Weibull family, including 0<θ<10<θ<1 where MGF-based techniques break down. This work develops an information-theoretic generalization framework for modern learning algorithms under heavy-tailed distributions. Our main contributions are as follows. 1. Tail-adaptive decorrelation via shifted-log divergences. We introduce a shifted-log fθf_θ-divergence fθ(x)=xlog1/θ(x+A)f_θ(x)=x ^1/θ(x+A) and prove a decorrelation (change-of-measure) lemma that bounds expectations under a dependent coupling through this tail-adaptive divergence. We further show that it admits explicit upper bounds in terms of Rényi divergence, leading to usable bounds in terms of Rényi mutual information (Section 3). 2. Maximal and chaining bounds for sub-Weibull processes. For 0<θ<10<θ<1, we prove a sharp maximal inequality for a finite family of sub-Weibull random variables and a Dudley-type entropy integral for (θ,C)(θ,C)-sub-Weibull processes (Section 2). 3. Information-theoretic generalization under sub-Weibull tails. Combining the decorrelation lemma with the new sub-Weibull maximal/chaining bounds, we derive expected and high-probability generalization bounds for sub-Weibull losses, as well as an information-theoretic chaining inequality that remains non-vacuous even for deterministic continuous learners (Section 4). 4. Applications to RLHF under heavy-tailed rewards. We show that KL trust regions can fail to control reward inflation under heavy-tailed rewards (catastrophic Goodhart) and develop reward guarantees for Rényi-regularized RLHF and for best-of-n policies under sub-Weibull reward assumptions (Section 5). In numerical studies, we treat heavy-tailed reward constructions as controlled stress tests and show that the observed stabilizing effect of higher-order Rényi regularization persists across multiple heavy-tail constructions (Section 6.2 and Appendix I). 5. Applications to stochastic optimization. We apply the framework to stochastic gradient Langevin dynamics (SGLD) under heavy-tailed stochastic-gradient noise, yielding stability-based generalization bounds that expose the interaction between step sizes, injected noise, and tail heaviness (Appendix F). Related Work Concentration and maximal inequalities for heavy tails. Maximal inequalities and chaining are classical tools in empirical process theory (Talagrand, 2005; van Handel, 2016). A comprehensive treatment of concentration for sub-Weibull random variables is given by Zhang and Wei (2022). While maximal inequalities for sub-Weibull processes are well-understood for θ≥1θ≥ 1 (Kuchibhotla and Chakrabortty, 2022), the heavy-tailed regime 0<θ<10<θ<1 is more delicate because MGFs can be infinite and many standard arguments fail. Recent works provide concentration bounds with explicit prefactors (Mendes and Lopes, 2023) and sharp Orlicz norm bounds (Zhang and Wei, 2022). We complement these results by giving a direct expectation bound for maxima (avoiding an additional norm-to-moment factor) and by extending Dudley-type chaining bounds to (θ,C)(θ,C)-sub-Weibull processes for 0<θ<10<θ<1. Information-theoretic generalization. Information-theoretic generalization bounds date back to Russo and Zou (2020) and Xu and Raginsky (2017). Variants based on f-divergences and related dependence measures have been developed in (Jiao et al., 2017; Hellström et al., 2025; Bu et al., 2020) and references therein. Most existing information-theoretic bounds rely on KL-based mutual information (or MGF-based change-of-measure arguments) and are therefore tailored to bounded or sub-Gaussian losses. Our goal is to extend this toolkit to sub-Weibull tails by combining a tail-adaptive divergence and a multiscale information-theoretic chaining analysis. Overview Section 2 develops maximal and chaining tools for sub-Weibull processes. Section 3 introduces the shifted-log divergence and decorrelation lemma, together with Rényi comparison bounds. Section 4 combines these ingredients to obtain tail-adaptive information-theoretic bounds for selection, generalization in expectation, PAC-Bayes-style high-probability bounds, and multiscale (chaining) generalization. Section 5 illustrates the framework in RLHF under heavy-tailed rewards; numerical studies appear in Section 6. Additional proofs and experiments are deferred to the appendix. Table 1 summarizes the main results. Setting Classical (subG/KL) Ours (sub-Weibull/Rényi) Maximal inequality (finite) [maxiXi]≲lognE[ _iX_i] n [maxiXi]≲(logn)1/θE[ _iX_i] ( n)^1/θ (Lemma 2.1) Dudley bound (process) ∫logN(T,d,ε)ε N(T,d, )\,d ∫(logN(T,d,ε))1/θε ( N(T,d, ))^1/θ\,d (Thm. 2.2) Selection/max Russo bound I(W;S) I(W;S) Tail-adaptive fθf_θ/Rényi (Thm. 4.1.2) Information-theoretic chaining Asadi et al. (sub-Gaussian) Sub-Weibull multiscale Rényi (Thm. 4.1.3) Expected generalization I(S;W)/n I(S;W)/n (Ifθ(S;W))/n(I_f_θ(S;W))/ n (Thm. 4.2.3) High-probability (PAC-Bayes) KL PAC-Bayes Sub-Weibull PAC-Bayes (Thm. 4.2.4) Chaining generalization Asadi et al. (sub-Gaussian) Sub-Weibull chaining gen. (Thm. 4.2.5) RLHF trust region KL-constrained RLHF Rényi-regularized RLHF (Thm. 5.2) Table 1: Roadmap of results. Here θ is the sub-Weibull tail parameter. Notation For a positive integer n, we write [n]=1,…,n[n]=\1,…,n\. We use E for expectation and ℙP for probability. We denote by KLD_KL the KL divergence and by αD_α the Rényi divergence of order α>1α>1. We write ‖X‖ψθ\|X\|_ _θ for the Orlicz norm associated with ψθ(x)=exθ−1 _θ(x)=e^x^θ-1. We use ≲ to hide universal positive constants. Let (T,d)(T,d) be a metric space and let K⊂TK⊂ T. A subset ⊂TN⊂ T is called an ε -net for K if, for every x∈Kx∈ K, there exists y∈y such that d(x,y)≤εd(x,y)≤ . The covering number, denoted by N(K,d,ε)N(K,d, ), is the minimum cardinality of such an ε -net. Then e(T):=infε>0:N(T,d,ε)=1e(T):= \ >0:N(T,d, )=1\ is the minimum covering radius of T. Let X be the range of a random variable X. A partition P of X is a finite collection of disjoint sets PiP_i such that ⋃iPi= _iP_i=X. 2 Sub-Weibull Process Theory This section develops empirical-process tools for controlling maxima and suprema of sub-Weibull random variables and processes, with an emphasis on the heavy-tailed regime 0<θ<10<θ<1. In this regime, MGFs may be infinite, so many classical MGF-based arguments must be replaced by Orlicz-norm methods. We establish (i) a sharp maximal inequality for a finite family of sub-Weibull variables and (i) a Dudley-type chaining bound for (θ,C)(θ,C)-sub-Weibull processes. These are uniform (worst-case) bounds; Section 4 will refine them for data-adaptive algorithms using information measures. 2.1 A sharp maximal inequality Lemma 2.1 (Maximal inequality for heavy-tailed sub-Weibull variables) Let 0<θ<10<θ<1 and ψθ(x)=exθ−1 _θ(x)=e^x^θ-1. Let Xii=1n\X_i\_i=1^n be random variables with maxi∈[n]‖Xi‖ψθ<∞. _i∈[n]\|X_i\|_ _θ<∞. Then [maxi∈[n]|Xi|]≤ψθ−1(ψθ(xθ)+n)maxi∈[n]‖Xi‖ψθ=O((logn)1/θ), [ _i∈[n]|X_i| ]\;≤\; _θ^-1 ( _θ(x_θ)+n )\, _i∈[n]\|X_i\|_ _θ\;=\;O (( n)^1/θ ), (2.1) where ψθ−1(ψθ(xθ)+n)=[log(1+ψθ(xθ)+n)]1/θ _θ^-1 ( _θ(x_θ)+n )= [ (1+ _θ(x_θ)+n ) ]^1/θ with xθ:=(1−θ)1/θx_θ:= ( 1-θ )^1/θ. The 1/θ1/θ in (2.1) is sharp: for i.i.d. Weibull(θ)Weibull(θ) variables, [maxi∈[n]Xi]≍(logn)1/θE[ _i∈[n]X_i] ( n)^1/θ; see Appendix B.2. Thus, heavier tails (smaller θ) necessarily worsen the growth rate of the maximum. A useful heuristic is that sub-Weibull variables behave like power transforms of unbounded sub-Gaussian variables, so decreasing θ makes rare extremes more influential. A common route is to first control the Orlicz norm of the maximum and then convert that Orlicz bound to an expectation bound via a norm-to-moment inequality (Mendes and Lopes, 2023; Zhang and Wei, 2022). This often introduces an additional factor Γ(1/θ+1) (1/θ+1), which grows rapidly as θ↓0θ 0 and can noticeably loosen prefactors in the heavy-tailed regime. Lemma 2.1 bounds the expectation directly and avoids this extra loss while retaining the optimal O((logn)1/θ)O (( n)^1/θ ) scaling; a quantitative comparison is given in Appendix B.3. 2.2 From maxima to suprema: sub-Weibull processes Passing from finite maxima to suprema over a general index set raises measurability issues: ω↦supt∈TXt(ω)ω _t∈ TX_t(ω) need not be measurable. A standard way to avoid outer expectations is to assume separability, which reduces the supremum to one over a countable dense subset (van Handel, 2016, Definition 5.22). Definition 2.2 (Separable process) Let (T,d)(T,d) be a metric space. A stochastic process Xtt∈T\X_t\_t∈ T is separable if there exists a countable set T0⊆T_0 T such that Xt∈lims→t,s∈T0Xsfor all t∈Ta.s.X_t∈ _s→ t,~s∈ T_0X_s\;\;for all t∈ T\;a.s. Equivalently, for every t∈Tt∈ T there exists sk⊆T0\s_k\ T_0 with sk→ts_k→ t and Xsk→XtX_s_k→ X_t a.s.. Empirical process theory typically controls oscillations of a process via tail bounds on increments relative to a metric. In the sub-Gaussian case, an increment condition of the form ‖Xt−Xs‖ψ2≲d(t,s)\|X_t-X_s\|_ _2 d(t,s) leads to Dudley’s entropy bound supt∈TXt≲∫0∞logN(T,d,ε)εE _t∈ TX_t _0^∞ N(T,d, )\,d . In heavy-tailed settings, MGFs may fail to exist, yet increments are still often controlled by an exponential-of-a-power tail, motivating the following definition. Definition 2.3 (Sub-Weibull process) Let θ>0θ>0, C>0C>0, and let (T,d)(T,d) be a metric space. A mean-zero process Xtt∈T\X_t\_t∈ T is a (θ,C)(θ,C)-sub-Weibull process (with respect to d) if exp(|Xt−Xs|θ[Cd(t,s)]θ)≤2,∀s,t∈Ts.t.s≠t.E \! ( |X_t-X_s|^θ[Cd(t,s)]^θ )≤ 2, ∀ s,t∈ T~s.t.~s≠ t. Equivalently, ‖Xt−Xs‖ψθ≤Cd(t,s)\|X_t-X_s\|_ _θ≤ C\,d(t,s) for all s,t∈Ts,t∈ T. For θ≥1θ≥ 1, such increment control implies suitable log-MGF bounds and classical chaining machinery applies. When 0<θ<10<θ<1, MGF-based arguments generally break down; nevertheless, Orlicz increment control remains sufficient to develop a Dudley-type entropy bound once we can control maxima at each scale (Lemma 2.1). Theorem 2.4 (Heavy-tailed Dudley inequality) Let (T,d)(T,d) be a finite metric space and let Xtt∈T\X_t\_t∈ T be a mean-zero (θ,C)(θ,C)-sub-Weibull process with 0<θ<10<θ<1. Then [supt∈TXt]≤4CKθ∫0∞[logN(T,d,ε)]1/θε, [ _t∈ TX_t ]≤ 4CK_θ _0^∞ [ N(T,d, ) ]^1/θ\,d , (2.2) where N(T,d,ε)N(T,d, ) is the covering number and Kθ:=supx≥2(log(1+ψθ(xθ)+x)logx)1/θ<∞,xθ=(1−θ)1/θ.K_θ:= _x≥ 2 ( (1+ _θ(x_θ)+x) x )^1/θ<∞, x_θ= ( 1-θ )^1/θ. Theorem 2.2 is stated for finite T to keep discretization explicit. For general index sets, separability allows one to pass to a countable dense subset, yielding the following corollary (proved in Appendix B.5). Corollary 2.5 Let Xtt∈T\X_t\_t∈ T be a separable, mean-zero (θ,C)(θ,C)-sub-Weibull process on (T,d)(T,d). If we assume that γ<∞γ<∞, then [supt∈TXt]≤4CKθ∫0∞[logN(T,d,ε)]1/θdε=:γ.E [ _t∈ TX_t ]≤ 4CK_θ _0^∞ [ N(T,d, ) ]^1/θ\,d =:γ. The finiteness of γ implies [supt∈TXt]<∞E[ _t∈ TX_t]<∞. When θ=2θ=2 (sub-Gaussian), (2.2) reduces to Dudley’s classical entropy integral; θ=1θ=1 matches the usual sub-exponential analogue. For 0<θ<10<θ<1, the exponent 1/θ>11/θ>1 inflates the entropy integrand, quantitatively capturing the degradation in supremum control induced by heavier tails. 2.3 Maximal and Dudley bounds are insufficient for data-adaptive algorithms Lemma 2.1 and Theorem 2.2 control maxima and suprema via global complexity terms (e.g., logn n or an entropy integral). This worst-case nature is intrinsic: replacing a data-dependent choice by a supremum over all candidates necessarily pays for the size/entropy of the ambient class. In modern learning problems, however, algorithms are typically data-adaptive and probe only a localized, sample-dependent region of the hypothesis space. Consequently, purely uniform maximal inequalities can be overly conservative and may become vacuous when used as surrogates for generalization control. This motivates the information-theoretic approach developed next: rather than bounding a random, data-dependent choice by a global supremum, we control it in terms of how much information the algorithm extracts from the data. Section 4 develops tail-adaptive information bounds and a multiscale (chaining) refinement; Section 6 provides a numerical illustration of the gap between uniform and information-theoretic chaining bounds. 3 Preliminaries on f-Divergence and Rényi Divergence This section collects divergence notions and change-of-measure tools used in the heavy-tailed analysis. Classical information-theoretic generalization proofs typically combine (i) an MGF bound for the loss and (i) a KL-based variational representation (Donsker–Varadhan). When MGFs do not exist, this route breaks down. We instead use a shifted-log fθf_θ-divergence tailored to sub-Weibull tails and compare it to Rényi divergence. The key payoff is a decorrelation lemma: it bounds expectations under a dependent coupling (e.g., W depends on S) by a divergence term plus a decoupled moment term. 3.1 f-divergence and Rényi divergence Definition 3.1 (f-divergence) Let P and Q be probability measures on a measurable space (Ω,ℱ)( ,F). For a convex function f:(0,∞)→ℝf:(0,∞) with f(1)=0f(1)=0, the f-divergence is defined as f(P∥Q):=∫f(dPdQ)Q,if P≪Q,∞,otherwise. _f(P\|Q)\;:=\; cases f\! ( dPdQ )dQ,&if P Q,\\ ∞,&otherwise. cases (3.1) Important special cases include KL divergence (f(x)=xlogxf(x)=x x) and the family of Rényi divergences. For α>1α>1, the Rényi divergence is α(P∥Q)=1α−1log(∫(dPdQ)αQ).D_α(P\|Q)= 1α-1 \! ( ( dPdQ )^αdQ ). (3.2) When α=2α=2, 2(P∥Q)=log(1+χ2(P∥Q))D_2(P\|Q)= (1+χ^2(P\|Q) ), and as α→∞α→∞ one obtains ∞(P∥Q)=log‖dP/dQ‖∞D_∞(P\|Q)= \|dP/dQ\|_∞. Lemma 3.2 (Basic properties of Rényi divergence) For any P,QP,Q on the same measurable space, α(P∥Q)D_α(P\|Q) is nondecreasing in α. Moreover, (i) for 0<α1≤α20< _1≤ _2, α1(P∥Q)≤α2(P∥Q)D_ _1(P\|Q) _ _2(P\|Q); (i) limα→1α(P∥Q)=KL(P∥Q) _α→ 1D_α(P\|Q)=D_KL(P\|Q). Definition 3.3 (Rényi mutual information) Let (W,S)(W,S) be a pair of random variables with joint distribution PW,SP_W,S. For α>1α>1, the Rényi mutual information is Iα(W;S):=α(PW,S∥PW⊗PS). I_α(W;S):=D_α(P_W,S\|P_W P_S). (3.3) 3.2 Shifted-log divergences and Rényi upper bounds To obtain tail-adaptive bounds under sub-Weibull index θ, we will use the following family of convex functions with additive shift A, fθ(x)=xlog1θ(x+A),θ>0,A≥1.f_θ(x)=x 1θ(x+A), θ>0,\ A≥ 1. (3.4) The A prevents singular behavior near 0 and the power θ−1θ^-1 matches the power in the optimal scaling O((logn)1/θ)O (( n)^1/θ ) for sub-Weibull maximum inequality (Lemma 2.1) in the following heavy-tailed decorrelation arguments. 3.2.1 Rényi divergence-based upper bounds Lemma 3.4 Let P≪QP Q be probability measures on a measurable space (,ℱ)(X,F), and suppose that α(P∥Q)<∞D_α(P\|Q)<∞ for some α>1α>1. Fix θ>0θ>0 and define fθ(x):=xlog1/θ(x+A)f_θ(x):=x ^1/θ(x+A). Assume that A=1A=1 when θ≥1θ≥ 1; and when θ<1θ<1 A≥exp(1α−1(1θ−1))for 1<α≤2,andA≥exp(1θ−1)for α>2.A≥ \! ( 1α-1 ( 1θ-1 ) ) 1<α≤ 2, A≥ \! ( 1θ-1 ) α>2. Then fθ(P∥Q)≤[α(P∥Q)+Cα,θ]1/θ, _f_θ(P\|Q)≤[D_α(P\|Q)+C_α,θ]^1/θ, (3.5) where, for 1<α≤21<α≤ 2, Cα,θ:=1α−1log(1+Aα−1),0<θ<1,log2,θ≥1,andCα,θ=C2,θfor α>2.C_α,θ:= cases 1α-1 (1+A^α-1 ),&0<θ<1,\\[8.99994pt] 2,&θ≥ 1, cases C_α,θ=C_2,θ\ for α>2. Lemma 3.2.1 provides a clean power-type comparison: fθD_f_θ is controlled by a 1/θ1/θ power of Rényi divergence (up to an additive constant). In the regime 0<θ<10<θ<1, we will also use a second comparison that yields an additive bound without an extra factor of 21/θ−12^1/θ-1. Lemma 3.5 Let P≪QP Q be two probability measures defined on a measurable space (,ℱ)(X,F) with α(P∥Q)<∞D_α(P\|Q)<∞ for some α>1α>1. When 0<θ<10<θ<1, set A≥exp(1α−1(1θ−1))1<α≤2e1θ−1α>2. A≥ cases \! ( 1α-1( 1θ-1) ) 1<α≤ 2\\ e 1θ-1 α>2. cases (3.6) and when θ≥1θ≥ 1 set A≥1A≥ 1. For fθ(x)=xlog1θ(x+A)f_θ(x)=x 1θ(x+A), we have fθ(P∥Q)≤[α(P∥Q)]1θ+Bα,θ, _f_θ(P\|Q)≤[D_α(P\|Q)] 1θ+B_α,θ, (3.7) where Bα,θB_α,θ depends only on θ and α (see Appendix C.2). 3.3 Decorrelation inequalities We now state the main change-of-measure tool used throughout the paper. Given a joint law μ (e.g., of (W,S)(W,S)) and a product reference law ν (e.g., PW⊗PSP_W P_S), we want to control μ[r]E_μ[r] by a divergence between μ and ν plus a moment term under ν. In the sub-Gaussian case, this is commonly done via the Donsker–Varadhan representation of KL divergence. Here we use a Young-type inequality based on fθf_θ, which does not require MGFs. Lemma 3.6 (Decorrelation lemma) Let θ>0θ>0 and A≥1A≥ 1. Let μ and ν be probability measures on a measurable space (Ω,ℱ)( ,F). Let r≥0r≥ 0 be measurable and assume r∈L1(μ)r∈ L^1(μ) and exp(rθ)∈L1(ν) (r^θ)∈ L^1(ν). Then μr≤21/θfθ(μ∥ν)+νexp(rθ), _μr≤ 2^1/θD_f_θ(μ\|ν)+E_ν (r^θ), (3.8) where fθ(x)=xlog1/θ(x+A)f_θ(x)=x ^1/θ(x+A). Lemma 3.3 will be applied with μ=PW,Sμ=P_W,S and ν=PW⊗PSν=P_W P_S and with r equal to a (scaled) loss or reward; the first term captures dependence between W and S, while the second term is a sub-Weibull moment under the product measure. In some heavy-tailed settings, it is useful to replace the full exponential moment νexp(rθ)E_ν (r^θ) by a truncated version. The next lemma provides such a refinement. Lemma 3.7 (Truncated decorrelation lemma) Let θ∈(0,2]θ∈(0,2]. Define h(y)=eyθ−∑k=0⌊2/θ⌋ykθk!,y≥0.h(y)=e^y^θ- _k=0 2/θ y^kθk!, y≥ 0. Let A≥1A≥ 1 and define fθ(x)=xlog1/θ(x+A)f_θ(x)=x ^1/θ(x+A). Let μ and ν be probability measures on (Ω,ℱ)( ,F), and let r≥0r≥ 0 be measurable. Assume r∈L1(μ)r∈ L^1(μ) and h(r)∈L1(ν)h(r)∈ L^1(ν). Then μr≤21/θfθ(μ∥ν)+2νh(r). _μr≤ 2^1/θD_f_θ(μ\|ν)+2E_νh(r). (3.9) Moreover, if A satisfies the conditions of Lemma 3.2.1, then for α>1α>1, μr≤21/θ(α(μ∥ν)+Cα,θ)1/θ+2νh(r). _μr≤ 2^1/θ(D_α(μ\|ν)+C_α,θ)^1/θ+2E_νh(r). (3.10) If A satisfies the conditions of Lemma 3.2.1, then for 0<θ<10<θ<1, μr≤21/θ(α(μ∥ν))1/θ+21/θBα,θ+2νh(r). _μr≤ 2^1/θ(D_α(μ\|ν))^1/θ+2^1/θB_α,θ+2E_νh(r). (3.11) The proofs of Lemmas 3.3 and 3.3 are based on a new Young-type inequality and are deferred to Appendix C. 4 Information-Theoretic Generalization Bounds under Sub-Weibull Tails This section combines the sub-Weibull empirical-process tools from Section 2 with the shifted-log divergence and decorrelation lemmas in Section 3 to derive algorithm-dependent bounds that remain meaningful under sub-Weibull (including heavy-tailed) losses. We proceed in two steps. We first revisit a basic selection problem: bounding [XW]E[X_W] when W is a data-dependent index to be selected. In the sub-Gaussian setting, this is controlled by KL mutual information (Russo and Zou, 2020), but this fails under heavy tails (Section 4.1.1). We then show how shifted-log fθf_θ-divergences and Rényi mutual information yield sharp substitutes, including a multiscale (chaining) refinement (Theorems 4.1.2 and 4.1.3). In the second step, we apply the same mechanism to the generalization error process gen(w,S)gen(w,S). This yields expected and high-probability generalization bounds (Theorems 4.2.3 and 4.2.4) and a multiscale chaining bound that remains non-vacuous for deterministic continuous learners (Theorem 4.2.5). 4.1 Rényi information refinements of maximal and Dudley-type bounds 4.1.1 Why KL mutual information fails under heavy tails Let S=Xii=1nS=\X_i\_i=1^n and let W=W(S)W=W(S) be a (possibly randomized) data-dependent index taking values in [n][n]. When the XiX_i are zero-mean i.i.d. sub-Gaussian with variance proxy σ2σ^2, Russo and Zou (2020) showed that [XW]≤2σ2I(W;S),E[X_W]≤ 2σ^2I(W;S), (4.1) where I(⋅;⋅)I(·;·) is KL-based mutual information. In particular, choosing W=argmaxi∈[n]XiW= _i∈[n]X_i and using I(W;S)≤lognI(W;S)≤ n recovers the classical maximal inequality [maxi∈[n]Xi]≲logn.E[ _i∈[n]X_i] n. In heavy-tailed regimes, KL mutual information may no longer control [XW]E[X_W]. The following example constructs a randomized maximum selector W for which I(W;S)=O(1)I(W;S)=O(1) while [XW]E[X_W] diverges with n. Example 1 Let S=Xii=1nS=\X_i\_i=1^n be i.i.d. Weibull(θ)Weibull(θ) random variables with θ∈(0,1)θ∈(0,1), i.e. ℙ(X1≥x)=exp(−xθ)P(X_1≥ x)= (-x^θ) for x>0x>0. Define a randomized selector W by W=argmaxi∈[n]Xi,with probability ε,U,with probability 1−ε,W= cases _i∈[n]X_i,&with probability ,\\ U,&with probability 1- , cases where U is uniform on [n][n] and independent of S. A direct computation gives I(W;S) I(W;S) =KL(PW,S∥PW⊗PS) =D_KL(P_W,S\,\|\,P_W P_S) =n−1n(1−ε)log(1−ε)+(n−1)ε+1nlog((n−1)ε+1). = n-1n(1- ) (1- )+ (n-1) +1n ((n-1) +1 ). Choosing ε=c/logn =c/ n for any fixed c>0c>0 yields I(W;S)=O(1)I(W;S)=O(1) as n→∞n→∞. On the other hand, [maxi∈[n]Xi]≍(logn)1/θE[ _i∈[n]X_i] ( n)^1/θ (see Appendix D), and therefore [XW]≥ε[maxi∈[n]Xi]=Ω((logn)1/θ−1).E[X_W]\;≥\; \,E[ _i∈[n]X_i]= (( n)^1/θ-1 ). Thus, for heavy-tailed Weibull data, the selection bias [XW]E[X_W] can diverge while the KL mutual information remains bounded. 4.1.2 Why Rényi mutual information and shifted-log f-divergences Example 4.1.1 reflects a general phenomenon: when MGFs do not exist, KL-based information can be too weak to control the contribution of rare but extreme events. To obtain a tail-adaptive substitute, we introduce the shifted-log family fθ(x)=xlog1/θ(x+A),θ>0,A≥1,f_θ(x)=x ^1/θ(x+A), θ>0,\ A≥ 1, and use the associated fθf_θ-mutual information Ifθ(W;S)I_f_θ(W;S). It matches sub-Weibull tails and, via Lemmas 3.2.1 and 3.2.1, admits explicit upper bounds in terms of Rényi mutual information. Theorem 4.1 (Tail-adaptive selection bound) Let S=Xii=1nS=\X_i\_i=1^n with Xi∼i.i.d.subW(θ)X_i i.i.d. subW(θ) for θ>0θ>0, and let W=W(S)W=W(S) be any [n][n]-valued, possibly randomized, selector. Let Ifθ(W;S)I_f_θ(W;S) be the fθf_θ-mutual information associated with fθ(x)=xlog1/θ(x+A)f_θ(x)=x ^1/θ(x+A) for some A≥1A≥ 1. Then |XW|≤maxi∈[n]‖Xi‖ψθ(21/θIfθ(W;S)+2).E|X_W|\;≤\; _i∈[n]\|X_i\|_ _θ\, (2^1/θI_f_θ(W;S)+2 ). Moreover, if A satisfies the conditions of Lemma 3.2.1, then |XW|≤maxi∈[n]‖Xi‖ψθ(21/θ(Iα(W;S)+Cα,θ)1/θ+2),E|X_W|\;≤\; _i∈[n]\|X_i\|_ _θ\, (2^1/θ (I_α(W;S)+C_α,θ )^1/θ+2 ), and if A satisfies the conditions of Lemma 3.2.1, then |XW|≤maxi∈[n]‖Xi‖ψθ(21/θ(Iα(W;S))1/θ+21/θBα,θ+2),E|X_W|\;≤\; _i∈[n]\|X_i\|_ _θ\, (2^1/θ (I_α(W;S) )^1/θ+2^1/θB_α,θ+2 ), where Iα(W;S)I_α(W;S) is the Rényi-α mutual information and Bα,θ,Cα,θB_α,θ,C_α,θ depend only on (α,θ)(α,θ). When θ=2θ=2 and α→1α→ 1, Theorem 4.1.2 recovers Russo and Zou’s bound (4.1) up to universal constants. Taking W=argmaxi∈[n]|Xi|W= _i∈[n]|X_i| also recovers the optimal maximal growth rate [maxi|Xi|]≲(logn)1/θE[ _i|X_i|] ( n)^1/θ; see Example B.3 in Appendix B. 4.1.3 A Dudley-type bound via multiscale information Theorem 4.1.2 bounds a single data-dependent selection. To obtain a Dudley-type bound for a data-dependent index in a general metric space, we combine Theorem 4.1.2 with a multiscale chaining construction, following Asadi et al. (2018); Hellström et al. (2025). Definition 4.2 (ε -partitions and increasing sequences) Let (,d)(W,d) be a metric space. A partition =A1,…,AmP=\A_1,…,A_m\ of W is called an ε -partition if for every i∈[m]i∈[m] there exists wi∈w_i such that Ai⊆ℬd(wi,ε),ℬd(wi,ε):=w∈:d(w,wi)≤ε.A_i _d(w_i, ), _d(w_i, ):=\w :d(w,w_i)≤ \. A sequence of partitions kk=k′∞\P_k\_k=k ^∞ is called increasing if for all k≥k′k≥ k and every A∈k+1A _k+1 there exists B∈kB _k such that A⊆BA B. For each w∈w and k≥k′k≥ k , let [w]k[w]_k denote the unique set A∈kA _k containing w. Examples of k\P_k\ can be found in Example 4.2.5 and Appendix G. Theorem 4.3 (Information-theoretic Dudley bound under sub-Weibull tails) Let X=Xtt∈TX=\X_t\_t∈ T be a separable (θ,C)(θ,C)-sub-Weibull process on (T,d)(T,d) (Definition 2.2), with finite Dudley integral in Corollary 2.2. Let W=W(S)W=W(S) be a T-valued random index (equivalently, W is measurable with respect to X). Let kk≥0\P_k\_k≥ 0 be an increasing sequence of partitions such that 0=TP_0=\T\ and kP_k is an e(T)2−ke(T)2^-k-partition for k≥1k≥ 1. For each A∈kA _k, choose tA∈Tt_A∈ T so that A⊂ℬd(tA,e(T)2−k)A _d (t_A,e(T)2^-k ), and if A⊂B∈k−1A⊂ B _k-1, then tA∈Bt_A∈ B. Let [W]k∈k[W]_k _k be the cell-valued variable containing W. Then [XW]≤Ce(T)∑k=1∞2−(k−1)(21/θIfθ([W]k;S)+2).E[X_W]\;≤\;Ce(T) _k=1^∞2^-(k-1) (2^1/θI_f_θ([W]_k;S)+2 ). Moreover, the bound admits the following Rényi mutual-information refinements. (i) Assume A satisfies the conditions of Lemma 3.2.1. Then, for any α>1α>1 such that Iα([W]k;S)<∞I_α([W]_k;S)<∞ for all k, [XW]≤Ce(T)∑k=1∞2−(k−1)(21/θ(Iα([W]k;S)+Cα,θ)1/θ+2), [X_W]\;≤\;Ce(T) _k=1^∞2^-(k-1) (2^1/θ (I_α([W]_k;S)+C_α,θ )^1/θ+2 ), (4.2) where Cα,θC_α,θ is the constant in Lemma 3.2.1. (i) Assume A satisfies the conditions of Lemma 3.2.1. Then, for any α>1α>1 such that Iα([W]k;S)<∞I_α([W]_k;S)<∞ for all k, [XW]≤Ce(T)∑k=1∞2−(k−1)(21/θ(Iα([W]k;S))1/θ+21/θBα,θ+2),E[X_W]\;≤\;Ce(T) _k=1^∞2^-(k-1) (2^1/θ (I_α([W]_k;S) )^1/θ+2^1/θB_α,θ+2 ), where Bα,θB_α,θ is the constant in Lemma 3.2.1. When θ=2θ=2, Theorem 4.1.3 recovers the mutual-information chaining bound of Asadi et al. (2018, Theorem 4) up to universal constants. When θ=1θ=1, it yields the information-theoretic chaining bound under sub-exponential tails. For θ∈(0,1)θ∈(0,1), the exponent 1/θ>11/θ>1 inflates the per-scale complexity term, quantifying the deterioration caused by heavier tails. The proof uses only Orlicz-norm control of increments and multiscale information, avoiding MGFs and circumventing the KL-based failure exhibited in Example 4.1.1. 4.2 Information-theoretic generalization bounds under sub-Weibullity 4.2.1 Loss function, empirical risk, and generalization error Let D denote the data space, W the hypothesis class with a metric space (,d)(W,d), and ℓ:×→ℝ+ :W×D _+ a loss function. Given a sample S=Zii=1nS=\Z_i\_i=1^n of i.i.d. random variables with common distribution μ, the goal is to choose w∈w that minimizes the population risk Lμ(w)=μ[ℓ(w,Z)]L_μ(w)=E_μ[ (w,Z)]. Since μ is unknown, one instead works with the empirical risk LS(w)=1n∑i=1nℓ(w,Zi)L_S(w)= 1n _i=1^n (w,Z_i). A learning algorithm is modeled as a Markov kernel PW∣SP_W S mapping the data S to a hypothesis W∈W . When S∼μ⊗nS μ n, the joint law is PS,W=μ⊗n⊗PW∣SP_S,W=μ n P_W S. The generalization error is gen(W,S):=Lμ(W)−LS(W)=1n∑i=1nℓ¯(W,Zi),gen(W,S):=L_μ(W)-L_S(W)= 1n _i=1^n (W,Z_i), where the centered loss is ℓ¯(w,Z)=μ[ℓ(w,Z)]−ℓ(w,Z) (w,Z)=E_μ[ (w,Z)]- (w,Z). 4.2.2 Classical information-theoretic bounds For sub-Gaussian losses, information-theoretic bounds control generalization through KL mutual information (Xu and Raginsky, 2017). Proposition 4.4 (Xu and Raginsky (2017)) Suppose that for every w∈w , the centered loss ℓ(w,Z)−ℓ(w,Z) (w,Z)-E (w,Z) is σ-sub-Gaussian under Z∼μZ μ. Then |gen(W,S)|≤2σ2nI(S;W).E |gen(W,S) |\;≤\; 2σ^2n\,I(S;W). If the learner is deterministic and W=φ(S)W= (S), then I(S;W)=H(W)I(S;W)=H(W) measures how much the output varies across samples. If W is independent of S, then I(S;W)=0I(S;W)=0 and the bound yields zero generalization error. 4.2.3 From sub-Gaussianity to sub-Weibullity Proposition 4.2.2 relies critically on sub-Gaussian tails (and hence MGFs). In the heavy-tailed sub-Weibull regime, KL mutual information can be too weak to control generalization—it may remain small even when the generalization error is large (cf. Example 4.1.1). We therefore replace KL by the shifted-log divergence induced by fθ(x)=xlog1/θ(x+A)f_θ(x)=x ^1/θ(x+A). Theorem 4.5 (Generalization bounds for sub-Weibull losses) Let S:=Zii=1nS:=\Z_i\_i=1^n be i.i.d. with law μ, and let W:=W(S)W:=W(S) be a (possibly randomized) learner measurable from data to a metric space (,d)(W,d). Assume supw∈‖ℓ¯(w,Z)‖ψθ<∞. _w \| (w,Z)\|_ _θ<∞. (4.3) Then there exists a constant Mθ>0M_θ>0 that depends only on θ (see (D.4) in Appendix) such that |gen(W,S)|≤Mθnsupw∈‖ℓ¯(w,Z)‖ψθ(21/θIfθ(S;W)+4),0<θ≤2.E |gen(W,S) |\;≤\; M_θ n\, _w \| (w,Z)\|_ _θ\, (2^1/θI_f_θ(S;W)+4 ),~0<θ≤ 2. Moreover, under the conditions of Lemma 3.2.1 or Lemma 3.2.1, Ifθ(S;W)I_f_θ(S;W) can be further bounded in terms of Rényi mutual information Iα(S;W)I_α(S;W). When θ=2θ=2 and α→1α→ 1, Theorem 4.2.3 recovers Proposition 4.2.2 up to constants. For θ∈(0,1)θ∈(0,1), the dependence on Ifθ(S;W)I_f_θ(S;W) makes the information–tail tradeoff explicit. Remark 1 (On the uniform sub-Weibull loss assumption) For many models, (4.3) can be verified by combining sub-Weibull tails of the data with Lipschitz/ boundedness properties of the predictor; see Example I.4 in Appendix I.4 for a square-loss illustration. The global supremum in (4.3) keeps the statement simple but can be conservative: in practice it may suffice to control the sub-Weibull scale locally on the region of W explored by the algorithm (e.g., in expectation under a posterior or on a data-dependent neighborhood of W). We keep the uniform form to emphasize the core information–tail mechanism and to facilitate comparisons with KL-based results. 4.2.4 High-probability bounds and PAC-Bayes perspective Beyond bounds in expectation, PAC-Bayes theory provides high-probability generalization guarantees. Existing PAC-Bayes bounds typically rely on bounded, sub-Gaussian or sub-exponential assumptions (Alquier et al., 2016; Alquier and Guedj, 2018; Germain et al., 2016; Catoni, 2004). Heavy-tailed losses have also been studied under finite moment conditions (Alquier and Guedj, 2018), but finite q-moment-based bounds generally scale polynomially in n (Zhang and Chen, 2021, Corollary 7.1) and can be much weaker than the logarithmic dependence (logn)1/θ( n)^1/θ available under sub-Weibull tails (see Example B.3 in Appendix B). The following theorem extends Chu and Raginsky (2023, Theorem 6) to sub-Weibull losses. Theorem 4.6 (High-probability sub-Weibull bound) Write log+(u):=maxlogu,0 _+(u):= \ u,0\. Let S=Zii=1nS=\Z_i\_i=1^n be i.i.d. with law μ, and let W=W(S)W=W(S) be specified by PW∣SP_W S in a metric space (,d)(W,d). Assume supw∈‖ℓ¯(w,Z)‖ψθ<∞for some 0<θ≤2. _w \| (w,Z)\|_ _θ<∞ some 0<θ≤ 2. Then there exists Eθ>0E_θ>0 such that for any δ∈(0,1)δ∈(0,1), with PSP_S-probability at least 1−δ1-δ, PW∣S|gen(W,S)|≤Mθnsupw∈‖ℓ¯(w,Z)‖ψθ(PW∣S[log+(dPW∣S/dPW)]1/θ+Eθ+(log(3/δ))1/θ),E_P_W S |gen(W,S) |≤ M_θ n\, _w \| (w,Z)\|_ _θ (E_P_W S [ _+(dP_W S/dP_W) ]^1/θ+E_θ+( (3/δ))^1/θ ), where Mθ>0M_θ>0 is given in (D.4) in Appendix. From conditional complexity to mutual information. For any A≥1A≥ 1, log+(dPW∣SdPW)≤log(dPW∣SdPW+A) _+\! ( dP_W SdP_W )≤ \! ( dP_W SdP_W+A ), so PW∣S[log+(dPW∣S/dPW)]1/θ≤PW∣S[log(dPW∣SdPW+A)]1/θ=fθ(PW∣S∥PW).E_P_W S [ _+(dP_W S/dP_W) ]^1/θ _P_W S [ \! ( dP_W SdP_W+A ) ]^1/θ=D_f_θ(P_W S\|P_W). Averaging over S yields Sfθ(PW∣S∥PW)=Ifθ(W;S)E_SD_f_θ(P_W S\|P_W)=I_f_θ(W;S), which can be upper bounded by Rényi mutual information using Lemma 3.2.1 or Lemma 3.2.1. 4.2.5 From a single hypothesis to metric chaining Theorems 4.2.3 and 4.2.4 are single-scale bounds: they measure data dependence through Ifθ(W;S)I_f_θ(W;S) (or Iα(W;S)I_α(W;S)) for the final output W. This can be vacuous when W is a continuous deterministic function of S, because then PW∣SP_W S is singular with respect to PWP_W and Iα(W;S)=∞I_α(W;S)=∞. To address this, we use a multiscale discretization of W in the spirit of Asadi et al. (2018), adapted here to sub-Weibull tails. Assume the centered loss ℓ¯(w,Z)w∈\ (w,Z)\_w has sub-Weibull increments with respect to d: ‖ℓ¯(u,Z)−ℓ¯(v,Z)‖ψθ≤d(u,v),u,v∈.\| (u,Z)- (v,Z)\|_ _θ≤ d(u,v), u,v . Combining this increment condition with the information-theoretic chaining result (Theorem 4.1.3) yields the following multiscale generalization bound. Theorem 4.7 (Chaining generalization bound) Let S=Zii=1nS=\Z_i\_i=1^n be i.i.d. with law μ, and let W=W(S)W=W(S) be measurable. Assume ℓ¯(w,Z)w∈\ (w,Z)\_w is a separable (θ,1)(θ,1)-sub-Weibull process on (,d)(W,d) with θ∈(0,2]θ∈(0,2], and assume the Dudley integral in Corollary 2.2 is finite. Let kk≥0\P_k\_k≥ 0 be an increasing sequence of partitions of W, where kP_k is an e()2−ke(W)2^-k-partition. For each A∈kA _k, choose tA∈t_A such that A⊂ℬd(tA,e()2−k),A _d (t_A,e(W)2^-k ), and if A⊂B∈k−1A⊂ B _k-1, then tA∈Bt_A∈ B. Let [W]k∈k[W]_k _k be the cell-valued variable containing W. Then there exists Mθ>0M_θ>0 (see (D.4) in Appendix) such that [gen(W,S)]≤e()Mθn∑k=1∞2−(k−1)(21/θIfθ([W]k;S)+4). [gen(W,S) ]≤ e(W)M_θ n _k=1^∞2^-(k-1) (2^1/θI_f_θ([W]_k;S)+4 ). (4.4) When θ=2θ=2, (4.4) recovers (up to constants) the chaining mutual-information bound of Asadi et al. (2018). When θ=1θ=1, it yields the sub-exponential analogue; see also Zhou et al. (2023) for finite-MGF settings. For 0<θ<10<θ<1, the exponent 1/θ>11/θ>1 enlarges each scale contribution, quantifying the impact of heavier tails. Example 2 (Quadratic mean estimation; deterministic ERM) Let =[−1,1]W=[-1,1] and consider ℓ(w,Y)=(w−Y)2 (w,Y)=(w-Y)^2, where Y is symmetric Weibull with ℙ(|Y|≥t)=12e−tθP(|Y|≥ t)= 12e^-t^θ for θ∈(0,1)θ∈(0,1). Given S=Yii=1nS=\Y_i\_i=1^n, define the ERM W=argminw∈[−1,1]LS(w)=clip(1n∑i=1nYi,[−1,1]).W= _w∈[-1,1]L_S(w)=clip\! ( 1n _i=1^nY_i,\;[-1,1] ). This W is deterministic and continuous in S, so PW∣SP_W S is singular w.r.t. PWP_W and Iα(W;S)=∞I_α(W;S)=∞ for every α>1α>1; hence Theorem 4.2.3 is vacuous. Now discretize [−1,1][-1,1] by dyadic partitions k=[m2−(k−1),(m+1)2−(k−1))∩[−1,1]:m∈ℤ,k≥1,P_k= \[m2^-(k-1),(m+1)2^-(k-1))∩[-1,1]:m \, k≥ 1, and let Wk=[W]kW_k=[W]_k be the cell containing W. Although Iα(W;S)=∞I_α(W;S)=∞, WkW_k is discrete and its Rényi mutual information grows at most linearly in k under mild regularity (e.g., a bounded-below density for the sample mean on [−1,1][-1,1]; see the proof in Appendix G). Since ∑k≥1k 2−k<∞ _k≥ 1k\,2^-k<∞, the multiscale sum in Theorem 4.2.5 is finite and yields a finite bound. 5 Applications to RLHF with Heavy-Tailed Rewards This paper gives two applications of our heavy-tailed information-theoretic bounds: (i) safety alignment of large language models (LLMs) under heavy-tailed reward functions, and (i) generalization analysis for stochastic optimization under heavy-tailed data (Appendix F). We study reinforcement learning from human feedback (RLHF) for aligning LLMs. Let π(y∣x)π(y x) denote a policy (a Markov kernel from prompts to responses), where x∈x is a prompt and y∈y is a generated response. Prompts are drawn from a distribution ρX _X on X, and π(⋅∣x)π(· x) specifies the conditional distribution of responses. In this sense, RLHF can be viewed as a contextual bandit problem. Given a reference policy π0(⋅∣x) _0(· x) (typically a pretrained model), the goal is to construct a new policy π that achieves higher expected reward r(x,y)r(x,y). In practice, r is learned from preference data and can be misspecified; we refer to the true human-aligned objective as the gold reward and the learned reward model as the proxy reward. 5.1 KL-constrained and best-of-n alignment A standard formulation of RLHF is the KL-constrained optimization (Ouyang et al., 2022): maxπx∼ρX,y∼π(⋅∣x)[r(x,y)]s.t.KL(π(⋅∣x)∥π0(⋅∣x))≤ϵ∀x, _π\;E_x _X,\;y π(· x)[r(x,y)] .t. _KL (π(· x)\,\|\, _0(· x) )≤ε ∀ x, (5.1) where ϵ>0ε>0 is an information budget. By Donsker–Varadhan representation, the optimizer is an exponentially tilted distribution (Yang et al., 2024b): πKL∗(y∣x)=π0(y∣x)exp(r(x,y)/λ)Y∼π0(⋅∣x)exp(r(x,Y)/λ),π^*_KL(y x)= _0(y x) (r(x,y)/λ)E_Y _0(· x) (r(x,Y)/λ), (5.2) with a Lagrange multiplier λ>0λ>0. An alternative inference-time strategy is the best-of-n policy (Stiennon et al., 2020; Nakano et al., 2021). Given a prompt x, one samples n i.i.d. responses Y1,…,Yn∼π0(⋅∣x)Y_1,…,Y_n _0(· x) and selects Yn∗∈argmaxi∈[n]r(x,Yi)Y_n^*∈ _i∈[n]r(x,Y_i). The resulting policy πn(⋅∣x) _n(· x) is the distribution of Yn∗Y_n^*. Under bounded rewards and regularity assumptions, best-of-n policies are asymptotically close to the KL-constrained optimizer (Mroueh and Nitsure, 2025; Yang et al., 2024b). 5.2 Catastrophic Goodhart and Rényi -regularized RLHF Under light-tailed assumptions, one can derive reward guarantees using KL-based arguments and data processing (Mroueh and Nitsure, 2025). When the proxy reward is heavy-tailed, however, KL regularization can fail catastrophically: the proxy reward can diverge even when the KL constraint is small, a phenomenon known as catastrophic Goodhart (Kwa et al., 2024). Formally, for any heavy-tailed distribution Q and any ϵ>0ε>0, there exist distributions P with arbitrarily large mean such that KL(P∥Q)≤ϵD_KL(P\|Q)≤ε. Intuitively, exponential tilting (5.2) can place disproportionate mass on extreme-reward events, while the KL penalty—an average discrepancy under the candidate policy—need not scale proportionally with such rare tail shifts. To mitigate this, we consider RLHF with Rényi-α regularization: maxπx∼ρX,y∼π(⋅∣x)[r(x,y)]s.t.α(π(⋅∣x)∥π0(⋅∣x))≤ϵ∀x, _π\;E_x _X,\;y π(· x)[r(x,y)] .t. _α (π(· x)\,\|\, _0(· x) )≤ε ∀ x, (5.3) for some α>1α>1. Compared to KL, the Rényi penalizes high density ratios more aggressively through a power α, which induces a qualitatively different structure in the optimizer. Lemma 5.1 (Solution to Rényi-constrained optimization) Let α>1α>1 and (⋅)+=max⋅,0(·)_+= \·,0\. Let the response space (,ℬ)(Y,B) be measurable and assume Y∼π0|r(x,Y)|1α−1<∞E_Y _0|r(x,Y)| 1α-1<∞. Then, for fixed x∈x , the optimizer π∗(⋅∣x)∝π0(y∣x)(r(x,y)−t)+1α−1)π^*(· x) _0(y x)\, (r(x,y)-t )_+ 1α-1) in (5.3), i.e. π∗(y∣x)=π0(y∣x)(r(x,y)−t)+1α−1Y∼π0(⋅∣x)(r(x,Y)−t)+1α−1,π^*(y x)= _0(y x) (r(x,y)-t )_+ 1α-1E_Y _0(· x) (r(x,Y)-t )_+ 1α-1, where the threshold t∈ℝt (and an associated Lagrange multiplier) is chosen so that π∗(⋅∣x)π^*(· x) satisfies the constraint α(π∗(⋅∣x)∥π0(⋅∣x))=ϵD_α(π^*(· x)\| _0(· x))=ε. Lemma 5.2 highlights the key structural difference from KL: Rényi regularization yields a truncated power-law reweighting of the reference policy, whereas KL yields exponential tilting. The truncation limits the influence of extreme-reward tail events, which is precisely the regime where KL can be vulnerable. The special case α=2α=2 corresponds to χ2χ^2-preference optimization, for which π∗(y∣x)∝π0(y∣x)(r(x,y)−t)+π^*(y x) _0(y x)(r(x,y)-t)_+; see Huang et al. (2025). Theorem 5.2 (Reward guarantees for RLHF with Rényi regularization) Fix x∈x and let π0(⋅∣x) _0(· x) be the reference policy. Abbreviate π(⋅∣x)π(· x) and π0(⋅∣x) _0(· x) by π and π0 _0. Define the centered reward r¯(x,y)=r(x,y)−Y∼π0[r(x,Y)]. r(x,y)=r(x,y)-E_Y _0[r(x,Y)]. Assume ‖r¯(x,Y)‖ψθ≤C\| r(x,Y)\|_ _θ≤ C for some θ>0θ>0 and Y∼π0(⋅∣x)Y _0(· x). Then for any policy π(⋅∣x)π(· x), πr(x,Y)−π0r(x,Y)≤C(21/θ[α(π∥π0)]1/θ+21/θBα,θ+2),E_πr(x,Y)-E_ _0r(x,Y)\;≤\;C (2^1/θ[D_α(π\| _0)]^1/θ+2^1/θB_α,θ+2 ), where Bα,θB_α,θ depends only on (α,θ)(α,θ) (see Appendix C.2). In particular, for the optimizer π∗π^* of (5.3), x∼ρXY∼π∗(⋅∣x)r(x,Y)≤x∼ρXY∼π0(⋅∣x)r(x,Y)+C(21/θϵ1/θ+21/θBα,θ+2).E_x _XE_Y π^*(· x)r(x,Y)\;≤\;E_x _XE_Y _0(· x)r(x,Y)+C (2^1/θε^1/θ+2^1/θB_α,θ+2 ). Theorem 5.2 shows that, Rényi-constrained RLHF rules out unbounded reward inflation at any fixed (divergence) budget under sub-Weibull reward tails, thereby preventing catastrophic Goodhart in this model. 5.3 Best-of-n policies under heavy-tailed rewards We now analyze whether catastrophic Goodhart arises for best-of-n policies. We adopt the following structural assumption (Beirami et al., 2025; Mroueh and Nitsure, 2025). Assumption 1 (Reward structure) For each context x, define r(x)=r(x,Y),Y∼π0(⋅∣x),rn(x)=maxi∈[n]r(x,Yi),Yi∼i.i.d.π0(⋅∣x).r(x)=r(x,Y), Y _0(· x), r_n(x)= _i∈[n]r(x,Y_i), Y_i i.i.d. _0(· x). There exists a stochastic map HxH_x such that Hx(r(x))=π0(⋅∣x)H_x(r(x)) d= _0(· x) and Hx(rn(x))=πn(⋅∣x)H_x(r_n(x)) d= _n(· x). Under Assumption 5.3 and the data processing inequality for Rényi divergence (cf. Polyanskiy and Wu, 2025, p. 120), α(πn(⋅∣x)∥π0(⋅∣x))≤α(rn(x)∥r(x)).D_α( _n(· x)\| _0(· x))\;≤\;D_α(r_n(x)\|r(x)). Theorem 5.3 (Best-of-n under heavy-tailed rewards) Assume ‖r(x,Y)‖ψθ≤C\|r(x,Y)\|_ _θ≤ C for some θ>0θ>0, α>1α>1 and Y∼π0(⋅∣x)Y _0(· x), and assume Assumption 5.3. If the trust-region budget n≤eϵn≤ e^ε for ϵ>0ε>0, then α(πn(⋅∣x)∥π0(⋅∣x))≤1α−1log(nα(n−1)+1)≤ϵ,D_α( _n(· x)\| _0(· x))≤ 1α-1 \! ( n^α(n-1)+1 )≤ε, and πnr−π0r≤C(21/θ[α(πn∥π0)+Cα,θ]1/θ+2)≤C(21/θ[ε+Cα,θ]1/θ+2),E_ _nr-E_ _0r≤ C (2^1/θ [D_α( _n\| _0)+C_α,θ ]^1/θ+2 )≤ C (2^1/θ [ +C_α,θ ]^1/θ+2 ), where Cα,θC_α,θ depends only on (α,θ)(α,θ) in Lemma 3.2.1. Remark 2 For large n, α(πn∥π0)≍lognD_α( _n\| _0) n, yielding a reward bound of order log1/θn ^1/θn. This matches the scaling suggested by maximal inequalities and shows that, unlike KL-regularized RLHF, best-of-n policies do not exhibit severe catastrophic Goodhart behavior under sub-Weibull rewards. 6 Numerical Studies In this section, we first examine the tightness of generalization bounds provided by our theorem, and then present numerical experiments to illustrate the benefits of Rényi -regularized RLHF under heavy-tailed rewards. We implement an end-to-end alignment pipeline based on Group Relative Policy Optimization (GRPO; Shao et al. 2024) and evaluate the resulting policies using state-of-the-art reward models. 6.1 Illustrating Tighter Generalization Bounds We revisit the two-dimensional process example of Asadi et al. (2018) to illustrate a key phenomenon in the heavy-tailed, data-adaptive setting: a single-scale mutual-information bound can be vacuous even when a multiscale chained information bound remains finite and informative. Table 2 summarizes the comparison. Table 2: −[XW]-E[X_W] and upper bounds for θ=0.5θ=0.5. MI: Theorem 4.1.2; CM: Theorem 2.2; Rényi CMI: Theorem 4.1.3. ε 1/201/20 1/301/30 1/401/40 1/501/50 1/1001/100 1/2001/200 1/4001/400 MI ∞ ∞ ∞ ∞ ∞ ∞ ∞ CM 832.01 832.01 832.01 832.01 832.01 832.01 832.01 Rényi CMI 71.93 71.46 71.30 71.22 71.12 71.10 71.09 −[XW]-E[X_W] 0.180 0.120 0.090 0.072 0.036 0.018 0.009 Let S=(Z1,Z2)S=(Z_1,Z_2) with i.i.d. Weibull(θ)(θ) coordinates, i.e., ℙ(Zi≥t)=exp(−tθ)P(Z_i≥ t)= (-t^θ) for t≥0t≥ 0. Consider the canonical Weibull process on the unit circle, Xϕ:=Z1cosϕ+Z2sinϕ,ϕ∈[0,2π),X_φ:=Z_1 φ+Z_2 φ, φ∈[0,2π), with loss l(ϕ,S):=−Xϕl(φ,S):=-X_φ. One can verify that −Xϕ∈[0,2π)\-X_φ\_φ∈[0,2π) is a (θ,C)(θ,C)-sub-Weibull process (Definition 2.2) with respect to the arc-length metric d(ϕ1,ϕ2)=|ϕ1−ϕ2|d( _1, _2)=| _1- _2|; see Appendix G. We define a randomized data-dependent selector by taking a measurable minimizer ϕ⋆(S)∈argminϕl(ϕ,S)φ (S)∈ _φl(φ,S) and adding a small perturbation, W=ϕ⋆(S)⊕ξ(mod2π),ℙ(ξ=0)=ε,ξ∣(ξ≠0)∼Unif(−π,π),W=φ (S) ξ 2π, (ξ=0)= , ξ (ξ≠ 0) (-π,π), with ξ⟂Sξ \!\!\! S. We compare four ways to upper bound [XW]E[X_W]: (i) the single-scale mutual-information (MI) bound (Theorem 4.1.2); (i) the classical chaining/Dudley entropy bound (CM, Theorem 2.2); (i) the chained mutual-information bound (Rényi CMI, Theorem 4.1.3); (iv) the exact value of [XW]E[X_W] for this example. As shown in Table 2, the single-scale MI bound is infinite. The chained information bound remains finite and is substantially tighter than the classical entropy-based chaining bound. For any ε>0 >0, the conditional law PW∣S=sP_W S=s has an atom at ϕ⋆(s)φ (s), whereas the marginal law PWP_W is non-atomic. Hence PW∣S=s≪̸PWP_W S=s P_W for PSP_S-a.e. s, implying I(W;S)=Iα(W;S)=∞I(W;S)=I_α(W;S)=∞ and rendering the single-scale MI bound vacuous. In contrast, the quantized variables [W]k[W]_k used in the chaining construction take values in a finite partition whose cells all have strictly positive marginal probability, thanks to the uniform component of ξ. Therefore each Iα([W]k;S)I_α([W]_k;S) is finite, and the chained bound remains informative. Full derivations and calculations are given in Appendix G. 6.2 RLHF under Heavy-Tailed Rewards To illustrate—and to stress-test—the mechanism by which Rényi -regularized RLHF mitigates catastrophic Goodhart effects, we empirically study Rényi -regularized RLHF under controlled heavy-tailed reward perturbations. Since commonly used open-source reward models often appear approximately light-tailed on in-distribution prompts, we emphasize that the goal of these experiments is not to claim that the underlying reward model is intrinsically heavy-tailed; rather, we construct heavy-tailed training signals in a principled way to isolate the interaction between tail behavior and the choice of divergence regularizer. Starting from the constrained formulation (5.3), we adopt the Lagrangian optimization: πβ∗=argmaxπx∼[y∼π(⋅∣x)[r(x,y)]−βDα(π(⋅∣x)∥π0(⋅∣x))],β≥0, _β^*= _π\;E_x [E_y π(· x) [r(x,y) ]\;-\;β\,D_α (π(· x)\,\|\, _0(· x) ) ], β≥ 0, (6.1) where π0(⋅∣x) _0(· x) is the reference policy, α≥1α≥ 1 is the Rényi order (with α=1α=1 reducing to KL), and β controls the trade-off between reward maximization and conservatism. Pipeline. We implement an end-to-end alignment pipeline based on Group Relative Policy Optimization (GRPO; Shao et al. 2024) with three stages: (i) Supervised fine-tuning (SFT). We start from Qwen2.5-1.5B (Team, 2024) and perform supervised fine-tuning to obtain an initial policy that reliably follows the dialogue format and instructions. All runs are initialized from the same SFT checkpoint. (i) Reward modeling. We train a lightweight proxy reward model (Qwen2.5-0.5B) on the h-rlhf training split to provide scalable training-time feedback. The proxy model takes concatenated prompt+completion pairs as input and is used only to produce online rewards during GRPO. For evaluation, we additionally use a stronger reward model, Skywork-Reward-V2-Qwen3-1.7B (Liu et al., 2025), as a surrogate evaluator for the (unobserved) gold reward; its output is never used during training. This surrogate evaluator is trained on a much larger dataset and achieves higher correlation with human judgments, but it is too computationally expensive to run routinely during RL optimization. For simplicity and without loss of generality, we refer to its scores as the gold reward. Throughout this section, we refer to the lightweight training-time model’s scores as the proxy reward. (i) RL optimization and evaluation. We optimize the SFT policy via GRPO using the proxy reward model as the training-time critic. We use a frozen reference model initialized from the same checkpoint as the policy to compute divergence terms and to recalibrate reward statistics. This two-reward-model protocol is standard in the RLHF literature (e.g., Kwa et al. 2024) and provides a practical balance between computational efficiency and evaluation fidelity. Experimental settings. We fix β=1β=1, sweep α∈1,2,…,10α∈\1,2,…,10\, train on the h-rlhf training split for up to 15001500 GRPO steps, and evaluate every 1010 steps on 128 held-out prompts. Full training and evaluation hyperparameters (generation settings, batch sizes, optimizer details, truncation lengths, and reward recalibration) are provided in Appendix I.1. Inducing heavier tails as controlled stress tests. Most empirical RLHF analyses implicitly treat reward-model scores as approximately Gaussian, or more generally light-tailed (Yan et al., 2024; Yang et al., 2024a). Our theory predicts that the choice of divergence regularizer matters most when rare, high-magnitude reward events are plausible, possibly due to distribution shift, reward-model miscalibration, or occasional outlier completions. Since widely used open-source reward models often appear approximately light-tailed on in-distribution prompts, we do not claim that the base proxy reward is intrinsically heavy-tailed; instead, we stress-test this regime by constructing heavy-tailed training signals in controlled ways while keeping the rest of the pipeline fixed. Our construction follows Bakhshizadeh et al. (2023) and applies an order-preserving power transform to the recalibrated proxy reward before optimization: r~(x,y)=sign(r(x,y))|r(x,y)|κ,κ∈1,6,8,10. r(x,y)=sign\! (r(x,y) )\, |r(x,y) |^κ, κ∈\1,6,8,10\. Here, κ=1κ=1 corresponds to the original reward. The t↦sign(t)|t|κt (t)|t|^κ is strictly increasing on ℝR for κ>0κ>0 and therefore preserves the preference ordering induced by the original proxy score. Moreover, if the original proxy score is sub-Gaussian, then the transformed reward r~ r is sub-Weibull with parameter 2/κ2/κ. To confirm that the power transform does amplify the heavy-tailedness in the training signal, Figure 1 compares the empirical distributions of the original and transformed proxy rewards for the representative choice κ=8κ=8. Panels 1 and 3 show the distribution of the original reward r(x,y)r(x,y) together with fitted normal density curves. In both cases, the untransformed reward is relatively concentrated and visually close to a light-tailed profile. Panels 2 and 4 show the corresponding transformed reward r~(x,y) r(x,y), overlaid with kernel density estimates.The transformed distribution becomes much more dispersed, with visibly heavier tails and more mass in the extremes. This supports that the power transform makes rare, large-magnitude reward realizations substantially more influential during training. Figure 1: Distribution of proxy reward model scores before and after the order-preserving power transformation for the representative choice κ=8κ=8. Panels 1 and 3 show the original reward r(x,y)r(x,y) for β=1β=1 with α=1α=1 (KL) and α=2α=2 (Rényi), overlaid with fitted normal density curves. Panels 2 and 4 show the transformed reward r~(x,y)=sign(r(x,y))|r(x,y)|8 r(x,y)=sign(r(x,y))\,|r(x,y)|^8 for the same configurations, overlaid with kernel density estimates. The transformation preserves reward ordering while substantially amplifying the heavy-tailedness of the training signal. Robustness across heavy-tail constructions. The order-preserving power transform above provides a convenient knob (via κ) to dial tail-heaviness without changing preference rankings, but it is only one way to generate rare, high-impact reward outliers. To verify that our conclusions are not an artifact of this particular transformation, we also study an alternative heavy-tailed construction based on adding centered Weibull noise to the reward signal prior to optimization; see Appendix I. Across both constructions (and across sweeps of κ and noise parameters), we observe the same qualitative pattern: KL-style control exhibits unstable reward–divergence behavior and a non-monotone proxy–proxy-gold relationship once rewards become heavy-tailed, whereas higher-order Rényi regularization yields smoother reward–divergence curves and a more monotone proxy–proxy-gold coupling. Reward–divergence behavior. Figures 2–3 show the empirical relationship between reward and divergence under β=1β=1. Under KL regularization (α=1α=1), Figure 2 shows a clear separation between the proxy reward (training-time signal) and the gold reward (evaluation signal) once the proxy reward is heavy-tailed (κ>1κ>1). As the policy moves farther from the reference model, the proxy reward generally continues to increase, whereas the gold reward exhibits a pronounced rise-then-collapse pattern: moderate divergence is initially beneficial, but additional divergence can eventually substantially degrade proxy-gold performance. This is a Goodhart-style signature of proxy over-optimization, in which continued improvement on the training-time reward no longer translates into improvement under the stronger evaluator. This pattern is consistent with the mechanism in Section 4.1.1. Occasional extreme proxy rewards can dominate the policy-gradient estimate and induce abrupt, localized changes in the policy. Because the KL penalty averages discrepancies over the full action distribution, such tail-driven deviations need not incur a proportionate KL cost, even when they materially alter behavior. The optimization can therefore drift toward policies that exploit proxy-specific artifacts while remaining relatively close to the reference policy in KL, which explains the collapse in gold reward seen in Figure 2. Figure 3 shows that this behavior changes under Rényi regularization. For α>1α>1, higher-order Rényi divergences penalize large likelihood ratios π(⋅∣x)/π0(⋅∣x)π(· x)/ _0(· x) more strongly, even when they arise on small subsets of actions. This makes concentrated, outlier-driven departures from the reference policy more expensive and thereby dampens the instability caused by heavy-tailed proxy rewards. Empirically, across α∈2,…,10α∈\2,…,10\, the gold reward is substantially more stable and typically increases before leveling off, rather than exhibiting the sharp collapse seen under KL. Taken together, Figures 2 and 3 suggest that Rényi regularization provides a more reliable trust-region signal in the heavy-tailed regime. Figure 2: Reward–divergence relationship for α=1α=1 (KL) with β=1β=1 under different power exponents κ. The four subplots correspond to κ=1,6,8,10κ=1,6,8,10, ordered from left to right and top to bottom. As κ increases, a clearer separation emerges between proxy and gold rewards: the proxy reward tends to keep increasing with divergence, whereas the gold reward exhibits a rise-then-collapse pattern, indicating Goodhart-style over-optimization under heavy-tailed proxy rewards. Figure 3: Reward–divergence relationship under Rényi regularization with β=1β=1, for orders α∈2,…,10α∈\2,…,10\ and different power exponents κ. The four subplots correspond to κ=1,6,8,10κ=1,6,8,10, ordered from left to right and top to bottom. Across α∈2,…,10α∈\2,…,10\, the gold reward is substantially more stable and typically increases before leveling off, rather than exhibiting the sharp rise-then-collapse pattern observed under KL, suggesting that Rényi regularization provides a more reliable trust-region signal in the heavy-tailed regime. Proxy–proxy-gold coupling. Figure 4 examines how improvements in the proxy reward translate into improvements in the gold reward. Under KL regularization (α=1α=1), this relationship becomes clearly non-monotone once the proxy reward is heavy-tailed (κ>1κ>1): the gold reward initially increases with the proxy reward, but beyond a certain point it begins to decline. Thus, continued optimization of the proxy reward can coincide with worse performance under the stronger evaluator, which is another manifestation of Goodhart-style over-optimization. By contrast, under Rényi regularization (α≥2α≥ 2), the proxy–proxy-gold curves remain monotone increasing and noticeably smoother across the observed range, indicating that gains in the proxy reward are more consistently aligned with gains in the gold reward. Overall, these results suggest that Rényi regularization yields a more reliable coupling between proxy and proxy-gold objectives, and therefore a more reliable trust-region signal than KL in the heavy-tailed regime. Figure 4: Proxy–proxy-gold reward relationship under β=1β=1, for Rényi orders α∈1,…,10α∈\1,…,10\ and power exponents κ∈1,6,8,10κ∈\1,6,8,10\. The four subplots correspond to κ=1,6,8,10κ=1,6,8,10, ordered from left to right and top to bottom. As κ increases, the KL case (α=1α=1) becomes clearly non-monotone, with the gold reward eventually declining as the proxy reward continues to improve, whereas the curves for α≥2α≥ 2 remain smoother and largely monotone increasing, indicating a more reliable coupling between proxy and gold objectives under Rényi regularization. More experiments and summary. Appendix I provides additional diagnostics and robustness checks, including tail plots for the power transformation and the full set of results for the additive Weibull-noise construction. 7 Conclusions and Discussions This paper develops an information–theoretic framework for generalization under sub-Weibullity. Our starting point is the observation that classical KL-based mutual information bounds, while powerful in light-tailed settings, can be ineffective when MGFs do not exist and rare extreme events dominate selection effects. To address this, we introduce a new decorrelation lemma tailored to sub-Weibull tails: it controls expectations under a changed measure via a shifted-log fθf_θ-divergence and relates this divergence to Rényi divergence. This route avoids MGF arguments entirely and works directly with Orlicz norms, yielding tail-adaptive information-theoretic bounds. Starting from empirical process perspective, we extend classical chaining tools to genuinely heavy-tailed regimes. We establish a maximal inequality for heavy-tailed sub-Weibull random variables and derive a Dudley-type entropy bound for sub-Weibull processes. The resulting bounds reveal an explicit and interpretable dependence on the tail index: metric entropy enters with exponent 1/θ1/θ, quantifying how heavier tails inflate the effective complexity of suprema. These results complement existing concentration inequalities for sums of sub-Weibull variables by providing controls for maxima and suprema, which are the natural objects in empirical process and learning-theoretic arguments. Building on these technical ingredients, we derive a suite of generalization guarantees under sub-Weibull assumptions. We obtain expectation bounds in terms of the sub-Weibull scale of the centered loss and an information measure based on fθf_θ-mutual information, along with Rényi -based refinements that more transparently capture tail dependence. We also establish PAC-Bayes–type high-probability bounds for sub-Weibull losses and develop an information-theoretic chaining inequality. Together, these results clarify how tail behavior and information usage jointly govern generalization beyond the classical sub-Gaussian regime. We apply the framework to two algorithmic settings where heavy tails are particularly relevant. First, for RLHF with potentially heavy-tailed rewards, we establish tail-adaptive reward guarantees for Rényi -regularized RLHF that remain meaningful even when MGFs fail to exist. In contrast, KL-regularized objectives may suffer from catastrophic Goodhart effects under heavy-tailed proxy rewards. We also analyze best-of-n policy and show that its reward behavior can be controlled via Rényi divergence, indicating that catastrophic Goodhart effects do not manifest severely for this strategy under heavy-tailed sub-Weibull rewards. Second, for stochastic gradient Langevin dynamics, we extend the analysis-by-perturbation viewpoint to sub-Weibull losses and obtain pathwise generalization bounds that separate statistical scale (through a sub-Weibull norm of the loss) from algorithmic quantities (step sizes, injected noise levels, and gradient-noise moments). The resulting bounds recover the sub-Gaussian scale when θ=2θ=2. Several limitations and directions remain for future work. First, the optimality of the resulting Rényi -based bounds, in terms of both exponents and constants, remains to be characterized, especially in structured or high-dimensional settings where sharper localization may be possible. Second, our analysis assumes i.i.d.data and focuses on algorithmic randomness modeled through mini-batch sampling and additive noise; extending the framework to dependent data (e.g., time series, reinforcement learning trajectories) and to more complex training dynamics (e.g., adaptive gradient methods, multi-epoch training, and deep network optimization) is a natural next step. Finally, while this work focuses on Rényi divergences and shifted-log f-divergences, other information measures (e.g., Rényi divergence with α∈(0,1)α∈(0,1), Wasserstein distances, or hybrid integral probability metrics) may provide complementary guarantees. From a practical standpoint, our results suggest principled design guidelines for tail-aware learning algorithms. For RLHF, the theory motivates moving beyond KL penalties toward divergence regularizers that better control extreme events without overconstraining policy updates. It is worthwhile to investigate the use of Rényi regularization algorithms that offer quantifiable differential privacy guarantees in LLM training by RLHF. For stochastic optimization, our bounds highlight how heavy tails tighten the permissible tradeoff between step sizes and noise levels, and suggest that adapting optimization schedules to estimated tail indices could improve stability and generalization. We hope that the tools developed here provide a step toward a broader, tail-adaptive information–theoretic theory of generalization that is better aligned with the heavy-tailed phenomena observed in modern machine learning. Acknowledgements H.Z. is supported in part by by Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing and the Beihang University under Youth Talent Start up Funding Project (No. KG16384201). W.T. is supported in part by the Funds of the Natural science Foundation of Hangzhou (No. 2025SZRJJ1388) and the Beijing Outstanding Young Scientist Program (No. JWZQ20240101027). Q.S. is supported in part by MBZUAI, the Natural Sciences and Engineering Research Council of Canada (Grant RGPIN-2018-06484), computing resources provided by the Digital Research Alliance of Canada, and MBZUAI. References P. Alquier and B. Guedj (2018) Simpler pac-bayesian bounds for hostile data. Machine Learning 107 (5), p. 887–902. Cited by: §4.2.4. P. Alquier, J. Ridgway, and N. Chopin (2016) On the properties of variational approximations of gibbs posteriors. Journal of Machine Learning Research 17 (236), p. 1–41. Cited by: §4.2.4. A. Asadi, E. Abbe, and S. Verdú (2018) Chaining mutual information and tightening generalization bounds. In Advances in Neural Information Processing Systems, Cited by: §A.3, §A.3, §G.2, §1, §4.1.3, §4.1.3, §4.2.5, §4.2.5, §6.1. M. Bakhshizadeh, A. Maleki, and V. H. De La Pena (2023) Sharp concentration results for heavy-tailed distributions. Information and Inference: A Journal of the IMA 12 (3), p. 1655–1685. Cited by: §6.2. A. Beirami, A. Agarwal, J. Berant, A. D’Amour, J. Eisenstein, C. Nagpal, and A. T. Suresh (2025) Theoretical guarantees on the best-of-n alignment policy. In International Conference on Machine Learning, p. 3580–3602. Cited by: §5.3. Y. Bu, S. Zou, and V. V. Veeravalli (2020) Tightening mutual information based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory 1 (1), p. 121–130. Cited by: §1, §1. O. Catoni (2004) Statistical learning theory and stochastic optimization: ecole d’eté de probabilités de saint-flour xxxi-2001. Springer. Cited by: §4.2.4. K. P. Choi (1994) On the medians of gamma distributions and an equation of ramanujan. Proceedings of the American Mathematical Society 121 (1), p. 245–251. Cited by: Appendix H. Y. Chu and M. Raginsky (2023) A unified framework for information-theoretic generalization bounds. In Thirty-seventh Conference on Neural Information Processing Systems, Cited by: §A.1, §C.1, Appendix H, §4.2.4. I. Fatkhullin, F. Hübler, and G. Lan (2025) Can sgd handle heavy-tailed noise?. In OPT 2025: Optimization for Machine Learning, Cited by: Appendix F. P. Germain, F. Bach, A. Lacoste, and S. Lacoste-Julien (2016) PAC-bayesian theory meets bayesian inference. Advances in Neural Information Processing Systems 29. Cited by: §4.2.4. F. Götze, H. Sambale, and A. Sinulis (2021) Concentration inequalities for polynomials in α-sub-exponential random variables. Electronic Journal of Probability 26 (none), p. 1 – 22. Cited by: §A.1. F. Hellström, G. Durisi, B. Guedj, M. Raginsky, et al. (2025) Generalization bounds: perspectives from information theory and pac-bayes. Foundations and Trends® in Machine Learning 18 (1), p. 1–223. Cited by: Appendix F, §1, §1, §4.1.3. A. Huang, W. Zhan, T. Xie, J. D. Lee, W. Sun, A. Krishnamurthy, and D. J. Foster (2025) Correcting the mythos of KL-regularization: direct alignment without overoptimization via chi-squared preference optimization. In The Thirteenth International Conference on Learning Representations, Cited by: §5.2. J. Jiao, Y. Han, and T. Weissman (2017) Dependence measures bounding the exploration bias for general measurements. In 2017 IEEE International Symposium on Information Theory (ISIT), p. 1475–1479. Cited by: §1. V. Koltchinskii (2011) Oracle inequalities in empirical risk minimization and sparse recovery problems: École d’Été de probabilités de saint-flour xxxviii-2008. Vol. 2033, Springer Science & Business Media. Cited by: §1. A. K. Kuchibhotla and A. Chakrabortty (2022) Moving beyond sub-gaussianity in high-dimensional statistics: applications in covariance estimation and linear regression. Information & Inference: A Journal of the IMA 11 (4). Cited by: §D.4, §1. T. Kwa, D. Thomas, and A. Garriga-Alonso (2024) Catastrophic goodhart: regularizing rlhf with kl divergence does not mitigate heavy-tailed reward misspecification. Advances in Neural Information Processing Systems 37, p. 14608–14633. Cited by: §1, §5.2, item (i). M. Lerasle (2019) Lecture notes: selected topics on robust statistical learning theory. arXiv preprint arXiv:1908.10761. Cited by: §1. C. Y. Liu, L. Zeng, Y. Xiao, J. He, J. Liu, C. Wang, R. Yan, W. Shen, F. Zhang, J. Xu, Y. Liu, and Y. Zhou (2025) Skywork-reward-v2: scaling preference data curation via human-ai synergy. arXiv preprint arXiv:2507.01352. Cited by: item (i). L. Madden, E. Dall’Anese, and S. Becker (2024) High probability convergence bounds for non-convex stochastic gradient descent with sub-weibull noise. Journal of Machine Learning Research 25 (241), p. 1–36. Cited by: Appendix F. E. F. Mendes and F. Lopes (2023) Concentration inequalities for high-dimensional linear processes with dependent innovations. arXiv preprint arXiv:2307.12395. Cited by: §B.3, §1, §2.1. Y. Mroueh and A. Nitsure (2025) Information theoretic guarantees for policy alignment in large language models. Transactions on Machine Learning Research. External Links: ISSN 2835-8856 Cited by: §E.3, §5.1, §5.2, §5.3. R. Nakano, J. Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, et al. (2021) Webgpt: browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332. Cited by: §5.1. G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy (2021) Information-theoretic generalization bounds for stochastic gradient descent. In Proceedings of Thirty Fourth Conference on Learning Theory, M. Belkin and S. Kpotufe (Eds.), Proceedings of Machine Learning Research, Vol. 134, p. 3526–3545. Cited by: Appendix F, Appendix F, Appendix F, Appendix F. L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. (2022) Training language models to follow instructions with human feedback. Advances in neural information processing systems 35, p. 27730–27744. Cited by: §5.1. Y. Polyanskiy and Y. Wu (2025) Information theory: from coding to learning. Cambridge University Press. Cited by: §E.4, §E.5, §5.3. A. Raj, L. Zhu, M. Gurbuzbalaban, and U. Simsekli (2023) Algorithmic stability of heavy-tailed SGD with general loss functions. In Proceedings of the 40th International Conference on Machine Learning, Vol. 202, p. 28578–28597. Cited by: Appendix F, §1. D. Russo and J. Zou (2020) How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory 66 (1), p. 302–323. External Links: Document Cited by: §A.1, §A.2, §A.3, §1, §1, §4.1.1, §4. S. Shalev-Shwartz and S. Ben-David (2014) Understanding machine learning: from theory to algorithms. Cambridge university press. Cited by: §1. Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. Li, Y. Wu, et al. (2024) Deepseekmath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: §6.2, §6. N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano (2020) Learning to summarize with human feedback. In Advances in Neural Information Processing Systems, Vol. 33, p. 3008–3021. Cited by: §5.1. C. Sun, H. Zhang, B. Chen, and L. Yu (2025) Distributed stochastic optimization under heavy-tailed noises. IEEE Transactions on Automatic Control. Cited by: Appendix F. M. Talagrand (2005) The generic chaining: upper and lower bounds of stochastic processes. Springer. External Links: Document Cited by: §1. Q. Team (2024) Qwen2.5: a party of foundation models. External Links: Link Cited by: item (i). A. W. van der Vaart and J. A. Wellner (2023) Weak convergence and empirical processes with applications to statistics, second edition. Springer. Cited by: §A.1, §A.1, §A.2, §B.3. R. van Handel (2016) Probability in high dimension. Princeton University, Princeton University, APC 550 Lecture Notes. Cited by: §A.2, §1, §2.2. M. J. Wainwright (2019) High-dimensional statistics: a non-asymptotic viewpoint. Vol. 48, Cambridge University Press. Cited by: §1. M. Welling and Y. W. Teh (2011) Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), p. 681–688. Cited by: Appendix F. A. Xu and M. Raginsky (2017) Information-theoretic analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, Cited by: §1, §1, §4.2.2, §4.2.2. L. Xu, F. Yao, Q. Yao, and H. Zhang (2023) Non-asymptotic guarantees for robust statistical learning under infinite variance assumption. Journal of Machine Learning Research 24 (92), p. 1–46. Cited by: §1. Y. Yan, X. Lou, J. Li, Y. Zhang, J. Xie, C. Yu, Y. Wang, D. Yan, and Y. Shen (2024) Reward-robust rlhf in llms. arXiv preprint arXiv:2409.15360. Cited by: §6.2. A. X. Yang, M. Robeyns, T. Coste, Z. Shi, J. Wang, H. B. Ammar, and L. Aitchison (2024a) Bayesian reward models for llm alignment. In ICML 2024 Workshop on Structured Probabilistic Inference \\ &\ Generative Modeling, Cited by: §6.2. J. Q. Yang, S. Salamatian, Z. Sun, A. T. Suresh, and A. Beirami (2024b) Asymptotics of language model alignment. In 2024 IEEE International Symposium on Information Theory (ISIT), p. 2027–2032. Cited by: §5.1, §5.1. H. Zhang and S. X. Chen (2021) Concentration inequalities for statistical inference. Communications in Mathematical Research 37 (1), p. 1–85. Cited by: §4.2.4. H. Zhang and H. Wei (2022) Sharper sub-weibull concentrations. Mathematics 10 (13), p. 2252. Cited by: §A.1, §B.3, §I.4, §1, §2.1. L. Zhou, F. Koehler, D. J. Sutherland, and N. Srebro (2021) Optimistic rates: a unifying theory for interpolation learning and regularization in linear regression. arXiv preprint arXiv:2112.04470. Cited by: §1. R. Zhou, C. Tian, and T. Liu (2023) Stochastic chaining and strengthened information-theoretic generalization bounds. Journal of the Franklin Institute 360 (6), p. 4114–4134. Cited by: §4.2.5. Appendix Appendix A Preliminaries A.1 Preliminaries on sub-Weibull random variables We review the definition of Orlicz norm and an equivalent definition for sub-Weibull random variables. Definition A.1 (Orlicz norm, van der Vaart and Wellner (2023)) For a random variable X, the Orlicz norm associated with a Young function ψ is defined as ‖X‖ψ:=infK>0:ψ(|X|K)≤1,\|X\|_ψ:= \K>0:E\,ψ\! ( |X|K )≤ 1 \, where ψ:[0,∞)→[0,∞)ψ:[0,∞)→[0,∞) is a Young function, i.e., a convex function satisfying ψ(0)=0ψ(0)=0 and limx→∞ψ(x)=∞ _x→∞ψ(x)=∞. For example, the sub-Weibull Orlicz norm is defined as ‖X‖ψθ:=infK>0:exp(|XK|θ)≤2.\|X\|_ _θ:= \K>0:\ E \! ( | XK |^θ )≤ 2 \. The ∥⋅∥ψθ\|·\|_ _θ is a norm when θ≥1θ≥ 1. For 0<θ<10<θ<1, it is only a quasi-norm: the triangle inequality fails, but a weak triangle inequality holds (Götze et al., 2021, Lemma A.3), ‖X+Y‖ψθ≤Dθ(‖X‖ψθ+‖Y‖ψθ),\|X+Y\|_ _θ≤ D_θ (\|X\|_ _θ+\|Y\|_ _θ ), (A.1) where Dθ=21/θ0<θ<1+θ≥1D_θ=2^1/θ1\0<θ<1\+1\θ≥ 1\. As θ→0θ→ 0, the constant 21/θ→∞2^1/θ→∞, which makes direct summation-based concentration arguments ineffective. By the first-moment bound for the sub-Weibull norm (Zhang and Wei, 2022, Corollary 3), |X|≤2Γ(θ−1+1)‖X‖ψθ.E|X|≤ 2 (θ^-1+1)\|X\|_ _θ. Consequently, the centered Orlicz quasi-norm is controlled by the non-centered one: ∥X−X∥ψθ≤Dθ(∥X∥ψθ+∥X∥ψθ)≤Dθ(1+2Γ(θ−1+1))∥X∥ψθ=:C2(θ)∥X∥ψθ,\|X-EX\|_ _θ≤ D_θ (\|X\|_ _θ+\|EX\|_ _θ )≤ D_θ(1+2 \!(θ^-1+1))\|X\|_ _θ=:C_2(θ)\|X\|_ _θ, (A.2) for a constant C2(θ):=Dθ(1+2Γ(θ−1+1))C_2(θ):=D_θ(1+2 \!(θ^-1+1)). As mentioned in the introduction, sub-Weibull random variables can also be equivalently characterized via their tail probabilities. Below we give a definition equivalent to the one based on the Orlicz norm. Definition A.2 (Sub-Weibull random variables) A random variable X is called sub-Weibull with tail parameter θ>0θ>0, denoted X∼subW(θ)X (θ), if there exist positive constants a,b>0a,\,b>0 such that ℙ(|X|≥x)≤aexp−(x/b)θ,x>0.P(|X|≥ x)≤ a \-(x/b)^θ \, x>0. In other words, sub-Weibull distributions have tails no heavier than those of a Weibull random variable with the same parameter θ. When θ<1θ<1, X is heavy-tailed, whereas θ≥1θ≥ 1 corresponds to light-tailed distributions, including sub-Gaussian (θ=2θ=2) and sub-exponential (θ=1θ=1) cases. The next section reviews key prior results on maximal inequalities for light-tailed sub-Weibull random variables (sub-Weibull with θ≥1θ≥ 1, van der Vaart and Wellner (2023)), and information-theoretic generalization bounds for sub-Gaussian random variables (Russo and Zou, 2020; Chu and Raginsky, 2023). A.2 Maximum inequalities for light-tailed sub-Weibull random variables The following maximal inequality for light-tailed sub-Weibull random variables with θ≥1θ≥ 1 is due to van der Vaart and Wellner (2023). Proposition A.3 (Maximal inequality for light-tailed sub-Weibull random variables) For θ≥1θ≥ 1, let Xii=1n\X_i\_i=1^n be random variables with max1≤i≤n‖Xi‖ψθ<∞ _1≤ i≤ n\|X_i\|_ _θ<∞ and ψθ(x)=exθ−1 _θ(x)=e^x^θ-1, (max1≤i≤n|Xi|)≤ψθ−1(n)max1≤i≤n‖Xi‖ψθ=(log(1+n))1/θmax1≤i≤n‖Xi‖ψθ. ( _1≤ i≤ n|X_i| )\;≤\;ψ^-1_θ(n) _1≤ i≤ n\|X_i\|_ _θ=( (1+n))^1/θ\, _1≤ i≤ n\|X_i\|_ _θ. (A.3) The proof of Proposition A.2 relies on Jensen’s inequality, which requires the convexity of ψθ _θ. This property holds only when θ≥1θ≥ 1 and fails for θ<1θ<1. Note that the sub-Gaussian case corresponds to θ=2θ=2. More generally, Russo and Zou (2020) extended maximal inequalities in the sub-Gaussian setting by relating them to mutual information. Under the assumption that Xii=1n\X_i\_i=1^n are i.i.d. σ2σ^2-sub-Gaussian, they established: [XW]≤2σ2I(W;X1,…,Xn),E [X_W ]≤ 2σ^2\,I(W;X_1,…,X_n), (A.4) where the algorithm output is a random index W=W(X1,…,Xn)W=W(X_1,…,X_n). When W is taken to be the maximum selector in [n][n], the mutual information bound yields the classical sub-Gaussian maximal inequality [maxi∈[n]Xi]≤2logn,E [ _i∈[n]X_i ]≤ 2 n, (A.5) by using the fact that I(W;X1,…,Xn)≤lognI(W;X_1,…,X_n)≤ n. Hence, (A.4) implies (A.5) as a special case, so (A.4) is more general than (A.5). When the index set is infinite or even uncountable, it is natural to generalize maximal inequalities to upper bounds on the supremum of empirical or stochastic processes. Dudley’s inequality (Theorem 5.24 in van Handel (2016)) states that [supt∈TXt]≤ 6∑k∈ℤ2−klogN(T,d,2−k)E [ _t∈ TX_t ]\;≤\;6 _k 2^-k N (T,d,2^-k ) if Xtt∈T \X_t \_t∈ T is a separable 1-sub-Gaussian process of zero mean on the bounded metric space (T,d)(T,d), i.e., exp(λ(Xt−Xs))≤exp(λ2d(t,s)2/2)for allt,s∈T,λ≥0.E (λ(X_t-X_s) )≤ (λ^2d(t,s)^2/2 ) all~t,s∈ T,\;λ≥ 0. A.3 Information-theoretic generalization bounds Building upon Russo and Zou (2020), Asadi et al. (2018) introduced a chaining method to derive information-theoretic generalization bounds, which can be viewed as a refinement of Dudley’s inequality through mutual information. Proposition A.4 (Asadi et al. (2018)) Assume that Xtt∈T\X_t\_t∈ T is a separable sub-Gaussian process of zero mean on a bounded metric space (T,d)(T,d), and let k1(T)k_1(T) be an integer such that 2−(k1(T)−1)≥diam(T)2^- (k_1(T)-1 ) (T). Let kk=k1(T)∞\P_k\_k=k_1(T)^∞ be an increasing sequence of partitions of T, where for each k≥k1(T)k≥ k_1(T), kP_k is a 2−k2^-k-partition111Recall the definition of partition in Definition 4.1.3. of (T,d)(T,d). Then: (a) XW≤32∑k=k1(T)∞2−kI([W]k;XT).EX_W≤ 3 2 _k=k_1(T)^∞2^-k I([W]_k;X_T). (b) For any arbitrary t0∈Tt_0∈ T, |XW−Xt0|≤32∑k=k1(T)∞2−kI([W]k;XT)+log2.E X_W-X_t_0 ≤ 3 2 _k=k_1(T)^∞2^-k I([W]_k;X_T)+ 2. When W is taken to be the maximum selector, Proposition A.3 yields an infinite-series bound that refines Dudley’s inequality, since [XW]≤[supt∈TXt]E[X_W] [ _t∈ TX_t ]. However, standard MGF-based techniques for deriving maximal inequalities and mutual information bounds are ineffective for heavy-tailed sub-Weibull distributions. This motivates the development of new tools to obtain sharp information-theoretic generalization bounds in the heavy-tailed regime. Appendix B Proofs for Section 2 B.1 Proof of Lemma 2.1 Proof. The function ψθ _θ is increasing on [0,∞)[0,∞) and convex on [xθ,∞)[x_θ,∞). Indeed, ψθ′(x)=θxθ−1exθ,ψθ′(x)=θxθ−2exθ(θxθ−(1−θ)), _θ (x)=θ x^θ-1e^x^θ, _θ (x)=θ x^θ-2e^x^θ (θ x^θ-(1-θ) ), so ψθ′(x)≥0 _θ (x)≥ 0 for all x≥xθ=:(1−θ)1/θx≥ x_θ=: ( 1-θ )^1/θ. Let 0<θ<10<θ<1 and define gθ(x):=(ψθ(x)−ψθ(xθ))+g_θ(x):= ( _θ(x)- _θ(x_θ) )_+. Then gθg_θ is convex and nondecreasing on [0,∞)[0,∞). Let K:=max1≤i≤n‖Xi‖ψθK:= _1≤ i≤ n\|X_i\|_ _θ and M:=max1≤i≤n|Xi|KM:= _1≤ i≤ n |X_i |K. Then, the elementary bound max1≤i≤nai≤∑i=1nai(ai≥0) _1≤ i≤ na_i≤ _i=1^na_i~(a_i≥ 0) gives ψθ(M)≤∑i=1nψθ(|Xi|K)≤n.E _θ(M)≤ _i=1^nE _θ\! ( |X_i |K )≤ n. By Jensen’s inequality, (ψθ(M)−ψθ(xθ))+=gθ(M)≤gθ(M)≤ψθ(M)≤n. ( _θ(EM)- _θ(x_θ) )_+=g_θ(EM) _θ(M) _θ(M)≤ n. Hence, ψθ(M)≤ψθ(xθ)+n _θ(EM)≤ _θ(x_θ)+n. Since ψθ _θ is increasing, M=(max1≤i≤n|Xi|K)≤ψθ−1(ψθ(xθ)+n),EM=E ( _1≤ i≤ n |X_i |K )≤ _θ^-1\! ( _θ(x_θ)+n ), and multiplying by K:=max1≤i≤n‖Xi‖ψθK:= _1≤ i≤ n\|X_i\|_ _θ yields (2.1). The big-O rate is from ψθ−1 _θ^-1. ∎ B.2 Optimality and comparison with classical bounds The following result shows that the bound in Lemma 2.1 is optimal in order: the rate log1/θn ^1/θn cannot be improved in general. Proposition B.1 Let X1,…,XnX_1,…,X_n be i.i.d. Weibull random variables ℙ(X≥x)=exp(−(x/b)θ)P(X≥ x)= (-(x/b)^θ). Then, we have (maxi∈[n]Xi)≳log1/θ(n).E( _i∈[n]X_i) ^1/θ(n). Proof. The upper bound follows from the proof of Lemma 2.1. For the lower bound: (maxi∈[n]Xi) ( _i∈[n]X_i) =∫0∞ℙ(maxi∈[n]Xi>x)x=∫0∞[1−(1−exp(−(x/b)θ))n]x = _0^∞P( _i∈[n]X_i>x)\,dx= _0^∞ [1-(1- (-(x/b)^θ))^n ]dx ≥∫0blog(n)1/θ1−(1−exp(−(x/b)θ))nx ≥ _0^b (n)^1/θ \1-(1- (-(x/b)^θ))^n \dx ≥∫0blog(n)1/θ1−(1−1n)nx≥blog1/θ(n)(1−1e), ≥ _0^b (n)^1/θ \1-(1- 1n)^n \dx≥ b ^1/θ(n) (1- 1e ), where the third line uses monotonicity of function t↦tnt t^n and the last line uses (1−1n)n≤1e(1- 1n)^n≤ 1e. ∎ B.3 Comparison with norm-to-moment bounds A standard alternative to bounding maxi∈[n]|Xi|E _i∈[n]|X_i| is to first control the Orlicz norm of the maximum and then convert that norm bound into a moment bound. For instance, Mendes and Lopes (2023, (S2.2)) showed that ‖maxi∈[n]|Xi|‖ψθ≤c1ψθ−1(2n)maxi∈[n]‖Xi‖ψθ,wherec1=2log(1.5). \| _i∈[n]|X_i| \|_ _θ≤ c_1 _θ^-1(2n)\, _i∈[n]\|X_i\|_ _θ, ~~c_1= 2 (1.5). using (van der Vaart and Wellner, 2023, Lemma 2.2.2). Combining this with the first-moment bound for the sub-Weibull norm (Zhang and Wei, 2022, Corollary 3), |X|≤2‖X‖ψθΓ(1θ+1),E|X|≤ 2\|X\|_ _θ \! ( 1θ+1 ), yields the bound [maxi∈[n]|Xi|]≤2c1ψθ−1(2n)Γ(1θ+1)maxi∈[n]‖Xi‖ψθ.E [ _i∈[n]|X_i| ]≤ 2c_1\, _θ^-1(2n)\, \! ( 1θ+1 ) _i∈[n]\|X_i\|_ _θ. In contrast, Lemma 2.1 controls the expectation directly and avoids the additional multiplicative factor Γ(1/θ+1) (1/θ+1) introduced by the norm-to-moment conversion. The ratio between the two prefactors is Rn,θ=4/log(1.5)ψθ−1(2n)Γ(1θ+1)ψθ−1(ψθ(xθ)+n)≥4log(1.5)Γ(1θ+1)≈9.865Γ(1θ+1).R_n,θ= 4/ (1.5) _θ^-1(2n) \! ( 1θ+1 ) _θ^-1 ( _θ(x_θ)+n )≥ 4 (1.5) ( 1θ+1 )≈ 9.865\, ( 1θ+1 ). (B.1) Since Γ(1/θ+1) (1/θ+1) grows rapidly as θ↓0θ 0, the norm-to-moment route can be substantially looser in the heavy-tailed regime, whereas Lemma 2.1 retains the sharp logarithmic scaling. To verify (B.1), note that ψθ(x)=exθ−1 _θ(x)=e^x^θ-1 has inverse ψθ−1(y)=[log(y+1)]1/θ _θ^-1(y)= [ (y+1) ]^1/θ. Thus, Rn,θ=4log(1.5)ψθ−1(2n)Γ(1θ+1)ψθ−1(ψθ(xθ)+n).R_n,θ= 4 (1.5) _θ^-1(2n) ( 1θ+1 ) _θ^-1 ( _θ(x_θ)+n ). We substitute ψθ(xθ)=exθ−1=e1−θ−1 _θ(x_θ)=e^x_θ^θ-1=e 1-θ-1, where xθ=1−θx_θ^θ= 1-θ. Substituting the inverse functions gives Rn,θ=4log(1.5)Γ(1θ+1)[log(2n+1)log(n+e1−θ)]1/θ.R_n,θ= 4 (1.5) ( 1θ+1 ) [ (2n+1) (n+e 1-θ) ]^1/θ. As n→∞n→∞, limn→∞log(2n+1)log(n+e1−θ)=limn→∞logn+log(2+1/n)logn+log(1+e1−θ/n)=1. _n→∞ (2n+1) (n+e 1-θ)= _n→∞ n+ (2+1/n) n+ (1+e 1-θ/n)=1. Therefore, the ratio converges to the constant 4log(1.5)Γ(1θ+1) 4 (1.5) ( 1θ+1 ). Moreover, for any n≥e1−θn≥ e 1-θ, we have log(2n+1)log(n+e1−θ)≥1 (2n+1) (n+e 1-θ)≥ 1. Hence, Rn,θ≥4log(1.5)Γ(1θ+1).R_n,θ≥ 4 (1.5) ( 1θ+1 ). The next example shows that taking W=argmaxi∈[n]|Xi|W= _i∈[n]|X_i| in Theorem 4.1.2 recovers the maximal growth rate [maxi|Xi|]≲(logn)1/θE[ _i|X_i|] ( n)^1/θ. Example 1 Let S=X1,…,XnS=\X_1,…,X_n\ be a vector of n i.i.d. continuous random variables with a common density. Let W=argmaxi∈[n]|Xi|W= argmax_i∈[n]|X_i| denote the index of the largest absolute value. Then I(W;S)=limα→1Iα(W;S)=logn,I(W;S)= _α→ 1I_α(W;S)= n, and for every α∈(0,∞)∖1α∈(0,∞) \1\, the Rényi-α mutual information is Iα(W;S)=logn.I_α(W;S)= n. Furthermore, for any p>0p>0, the p-th moment of the density ratio satisfies ∫[(dPW,SdPW⊗PS)p−1]PW⊗PS=np−1−1. [ ( dP_W,SdP_W P_S )^p-1 ]dP_W P_S=n^p-1-1. Proof. By continuity, ties in |X1|,…,|Xn||X_1|,…,|X_n| occur with probability 0. Hence the maximizer W=argmaxi∈[n]|Xi|W= _i∈[n]|X_i| is almost surely unique and takes values in 1,…,n\1,…,n\. By the exchangeability of X1,…,Xn\X_1,…,X_n\, we have for every i, ℙ(W=i)=1n.P(W=i)= 1n. Moreover, conditional on S=s=(x1,…,xn)S=s=(x_1,…,x_n), the value of W is deterministic: ℙ(W=i∣S=s)=i=argmaxj∈[n]|xj|P(W=i S=s)=1\i= _j∈[n]|x_j|\, which is 0,1\0,1\-valued and ∑i=1nℙ(W=i∣S)=1 _i=1^nP(W=i S)=1. Kullback–Leibler mutual information: Write PW∣SP_W S for the conditional law of W given S and PWP_W for the marginal law. Then I(W;S) I(W;S) =[KL(PW∣S∥PW)]=[∑i=1nℙ(W=i∣S)logℙ(W=i∣S)ℙ(W=i)] =E [D_KL (P_W S\,\|\,P_W ) ]=E [ _i=1^nP(W=i S) P(W=i S)P(W=i) ] =[∑i=1nℙ(W=i∣S)log11/n]=logn. =E [ _i=1^nP(W=i S) 11/n ]= n. Rényi mutual information. For α≠1α≠ 1, Iα(W;S)=α(PW,S∥PW⊗PS)=1α−1log∫(dPW,Sd(PW⊗PS))αd(PW⊗PS).I_α(W;S)=D_α(P_W,S\,\|\,P_W P_S)= 1α-1 ( dP_W,Sd(P_W P_S) )^α\,d(P_W P_S). Because W is discrete and S has density, the Radon–Nikodym derivative exists and equals dPW,Sd(PW⊗PS)(i,s)=ℙ(W=i∣S=s)ℙ(W=i)=nℙ(W=i∣S=s). dP_W,Sd(P_W P_S)(i,s)= P(W=i S=s)P(W=i)=n\,P(W=i S=s). Hence, using ℙ(W=i∣S=s)∈0,1P(W=i S=s)∈\0,1\ and ∑i=1nℙ(W=i∣S=s)=1 _i=1^nP(W=i S=s)=1, ∫(dPW,Sd(PW⊗PS))αd(PW⊗PS) ( dP_W,Sd(P_W P_S) )^αd(P_W P_S) =[∑i=1nℙ(W=i)(nℙ(W=i∣S))α] =E [ _i=1^nP(W=i) (nP(W=i S) )^α ] =[1n∑i=1nαℙ(W=i∣S)]=[nα−1]=nα−1. =E [ 1n _i=1^nn^αP(W=i S) ]=E [n^α-1 ]=n^α-1. (B.2) Therefore, Iα(W;S)=1α−1log(nα−1)=logn,α≠1.I_α(W;S)= 1α-1 (n^α-1 )= n, α≠ 1. Taking α→1α→ 1 yields I(W;S)=limα→1Iα(W;S)=lognI(W;S)= _α→ 1I_α(W;S)= n. Equation (B.3) also gives ∫[(dPW,SdPW⊗PS)p−1]PW⊗PS=np−1−1. [ ( dP_W,SdP_W P_S )^p-1 ]dP_W P_S=n^p-1-1. ∎ B.4 Proof of Theorem 2.2 Proof. The proof proceeds in four steps. Step 1: Decretization via ε -nets. If |T|=1 |T |=1, the result is trivial. Assume |T|≥2 |T |≥ 2. For k≥0k≥ 0, set εk:=2−ke(T) _k:=2^-ke(T). Since T is finite, there exists Δ:=mind(s,t):s,t∈T,s≠t>0. := \d(s,t):s,t∈ T,\ s≠ t\>0. Choose K so large that εK<Δ/2 _K< /2. Then every εK _K-ball contains at most one point of T, so every εK _K-net is all of T and TK=T_K=T. Fix k∈1,…,Kk∈\1,…,K\ and u∈Tku∈ T_k. Since Tk−1T_k-1 is an εk−1 _k-1-net of T and u∈Tk⊆Tu∈ T_k T, there exists pk(u)∈Tk−1p_k(u)∈ T_k-1 such that d(u,pk(u))≤εk−1.d (u,p_k(u) )≤ _k-1. This proves the existence of the parent map pkp_k. Step 2: Apply the maximal inequality. Next, for each k, the set of possible kkth increments is contained in Xu−Xpk(u):u∈Tk. \X_u-X_p_k(u):u∈ T_k \. For each k≥1k≥ 1 and u∈Tku∈ T_k, set Yk,u:=Xu−Xpk(u)Y_k,u:=X_u-X_p_k(u). Then ‖Yk,u‖ψθ≤Cd(u,pk(u))≤2Cεk.\|Y_k,u\|_ _θ≤ C\,d (u,p_k(u) )≤ 2C _k. Moreover, supt∈T|Xπk(t)−Xπk−1(t)|≤maxu∈Tk|Yk,u|. _t∈ T |X_ _k(t)-X_ _k-1(t) |≤ _u∈ T_k |Y_k,u |. Applying Lemma 2.1 at scale k gives supt∈T|Xπk(t)−Xπk−1(t)|≤2Cεkψθ−1(ψθ(xθ)+N(T,d,εk)).E _t∈ T |X_ _k(t)-X_ _k-1(t) |≤ 2C _k\, _θ^-1\! ( _θ(x_θ)+N(T,d, _k) ). For k≥1k≥ 1 we have N(T,d,εk)≥2N(T,d, _k)≥ 2, so by the definition of KθK_θ, ψθ−1(ψθ(xθ)+N(T,d,εk))≤Kθ[logN(T,d,εk)]1/θ. _θ^-1\! ( _θ(x_θ)+N(T,d, _k) )≤ K_θ [ N(T,d, _k) ]^1/θ. Hence supt∈TXt≤2CKθ∑k=1Kεk[logN(T,d,εk)]1/θ.E _t∈ TX_t≤ 2CK_θ _k=1^K _k [ N(T,d, _k) ]^1/θ. Step 3: Converting to an integral. Note that εk=2(εk−εk+1) _k=2( _k- _k+1) and that ε↦N(T,d,ε) N(T,d, ) is nonincreasing. Therefore εk[logN(T,d,εk)]1/θ≤2∫εk+1εk[logN(T,d,ε)]1/θε. _k [ N(T,d, _k) ]^1/θ≤ 2 _ _k+1 _k [ N(T,d, ) ]^1/θ\,d . Summing over k yields supt∈TXt≤4CKθ∫0e(T)[logN(T,d,ε)]1/θε≤4CKθ∫0∞[logN(T,d,ε)]1/θε.E _t∈ TX_t≤ 4CK_θ _0^e(T) [ N(T,d, ) ]^1/θ\,d ≤ 4CK_θ _0^∞ [ N(T,d, ) ]^1/θ\,d . This is the desired bound. ∎ B.5 Proof of Corollary 2.2 Proof. By separability, there exists a countable dense set T0=t1,t2,…⊆T_0=\t_1,t_2,…\ T such that supt∈TXt=supt∈T0Xta.s. _t∈ TX_t= _t∈ T_0X_t .s. For m≥1m≥ 1, let T(m):=t1,…,tm,Mm:=supt∈T(m)XtT^(m):=\t_1,…,t_m\,~M_m:= _t∈ T^(m)X_t. Then Mm↑supt∈T0XtM_m _t∈ T_0X_t a.s. Since T(m)⊆T^(m) T, N(T(m),d,ε)≤N(T,d,ε),ε>0.N(T^(m),d, )≤ N(T,d, ), >0. Applying Theorem 2.2 to the finite set T(m)T^(m), Mm≤4CKθ∫0∞[logN(T(m),d,ε)]1/θε≤4CKθ∫0∞[logN(T,d,ε)]1/θε.EM_m≤ 4CK_θ _0^∞ [ N (T^(m),d, ) ]^1/θ\,d ≤ 4CK_θ _0^∞ [ N(T,d, ) ]^1/θ\,d . By monotone convergence, supt∈TXt=supt∈T0Xt=limm→∞Mm≤4CKθ∫0∞[logN(T,d,ε)]1/θε.E _t∈ TX_t=E _t∈ T_0X_t= _m→∞EM_m≤ 4CK_θ _0^∞ [ N(T,d, ) ]^1/θ\,d . ∎ Appendix C Proofs for Section 3 This section collects proofs for the main results in Section 3. C.1 Proof of Lemma 3.2.1 Proof. Write L:=dP/dQ>0L:=dP/dQ>0 (defined Q-a.s.). We have fθ(P∥Q)=P[log(L+A)]1/θD_f_θ(P\|Q)=E_P [ (L+A) ]^1/θ. Case 1: θ≥1θ≥ 1 and A=1A=1. The claim follows directly by combining (Chu and Raginsky, 2023, Proposition 1) with the monotonicity of Rényi divergence stated in Lemma 3.1. Since θ≥1θ≥ 1, the map x↦log1/θ(x+1)x ^1/θ(x+1) is concave on [0,∞)[0,∞). Hence, by Jensen, fθ(P∥Q)=Plog1/θ(L+1)≤log1/θ(PL+1).D_f_θ(P\|Q)=E_P ^1/θ(L+1)≤ ^1/θ (E_PL+1 ). Now PL=∫LP=∫L2Q=e2(P∥Q).E_PL= L\,dP= L^2\,dQ=e^D_2(P\|Q). Therefore, by log(ex+1)≤x+log2 (e^x+1)≤ x+ 2 for x≥0x≥ 0, one has fθ(P∥Q)≤log1/θ(eD2(P∥Q)+1)≤(2(P∥Q)+log2)1/θ≤(α(P∥Q)+log2)1/θ,D_f_θ(P\|Q)≤ ^1/θ (e^D_2(P\|Q)+1 )≤ (D_2(P\|Q)+ 2 )^1/θ≤ (D_α(P\|Q)+ 2 )^1/θ, (C.1) where the last step uses monotonicity of Rényi divergence. Case 2: 0<θ<10<θ<1 and 1<α≤21<α≤ 2. Using the elementary inequality (x+y)k≤xk+yk(x+y)^k≤ x^k+y^k for x,y≥0x,y≥ 0 and 0<k≤10<k≤ 1, we obtain fθ(P∥Q) _f_θ(P\|Q) =P[log(L+A)]1/θ=P[1α−1log(L+A)α−1]1/θ =E_P [ (L+A) ]^1/θ=E_P\! [ 1α-1 \! (L+A )^α-1 ]^1/θ ≤P[1α−1log(Lα−1+Aα−1)]1/θ. _P\! [ 1α-1 \! (L^α-1+A^α-1 ) ]^1/θ. By Lemma H in Appendix H, the log1/θ(x+Aα−1) ^1/θ(x+A^α-1) is concave on [0,∞)[0,∞) provided that Aα−1≥exp(1θ−1).A^α-1\;≥\; \! ( 1θ-1 ). Applying Jensen’s inequality then yields fθ(P∥Q)≤[1α−1log(PLα−1+Aα−1)]1/θ.D_f_θ(P\|Q)≤ [ 1α-1 \! (E_PL^α-1+A^α-1 ) ]^1/θ. To separate the logarithmic terms, for x≥1x≥ 1 and y≥0y≥ 0, x+y≤x(1+y)x+y≤ x(1+y), log(x+y)≤logx+log(1+y). (x+y)≤ x+ (1+y). Thus it suffices to verify that PLα−1≥1.E_PL^α-1≥ 1. Indeed, Jensen’s inequality gives P[Lα−1]=Q[Lα]≥(QL)α=1E_P[L^α-1]=E_Q[L^α]\;≥\; (E_QL )^α=1. Consequently, fθ(P∥Q)≤[α(P∥Q)+1α−1log(1+Aα−1)]1/θ,D_f_θ(P\|Q)≤ [D_α(P\|Q)+ 1α-1 (1+A^α-1) ]^1/θ, which establishes the desired bound for 1<α≤21<α≤ 2. Case 3: 0<θ<10<θ<1 and α>2α>2. For α>2α>2, we invoke the monotonicity of Rényi divergence, 2(P∥Q)≤α(P∥Q)D_2(P\|Q) _α(P\|Q), to obtain fθ(P∥Q)≤infα>2(α(P∥Q)+Cα,θ)1/θ=(2(P∥Q)+C2,θ)1/θ.D_f_θ(P\|Q)\;≤\; _α>2 \ (D_α(P\|Q)+C_α,θ )^1/θ \= (D_2(P\|Q)+C_2,θ )^1/θ. This completes the proof. ∎ C.2 Proof of Lemma 3.2.1 Proof. The θ≥1θ≥ 1 case follows from (C.1) in the proof of Lemma 3.2.1 and the inequality (x+y)k≤xk+yk(x+y)^k≤ x^k+y^k for x,y≥0x,y≥ 0 and 0<k≤10<k≤ 1: f(P∥Q)≤(α(P∥Q)+log2)1/θ≤α(P∥Q)1/θ+(log2)1/θ.D_f(P\|Q)≤ (D_α(P\|Q)+ 2 )^1/θ _α(P\|Q)^1/θ+( 2)^1/θ. So we take Bα,θ=Cα,θB_α,θ=C_α,θ. Now we consider θ<1θ<1. We prove the lemma for the 2 cases: 1<α≤21<α≤ 2 and α>2α>2. The 1<α≤21<α≤ 2 case. Using the proof of Lemma 3.2.1 above, we already showed fθ(P∥Q)≤[1α−1log(PLα−1+Aα−1)]1θ.D_f_θ(P\|Q)≤ [ 1α-1 \! (E_PL^α-1+A^α-1 ) ] 1θ. Then we can upper bound fθ(P∥Q)−[α(P∥Q)]1θD_f_θ(P\|Q)-[D_α(P\|Q)] 1θ as fθ(P∥Q)−[α(P∥Q)]1θ≤[1α−1log(PLα−1+Aα−1)]1θ−[1α−1log(PLα−1)]1θ,D_f_θ(P\|Q)-[D_α(P\|Q)] 1θ≤ [ 1α-1 \! (E_PL^α-1+A^α-1 ) ] 1θ- [ 1α-1 \! (E_PL^α-1 ) ] 1θ, where PLα−1≥1E_PL^α-1≥ 1 from Jensen’s inequality in the proof of Lemma 3.2.1 above. Let r(x):=(log(x+d))1θ−(logx)1θr(x):=( (x+d)) 1θ-( x) 1θ, where x=L≥1x=L≥ 1 and d=Aα−1d=A^α-1. Then fθ(P∥Q)−[α(P∥Q)]1θ≤(1α−1)1θsupx≥1r(x).D_f_θ(P\|Q)-[D_α(P\|Q)] 1θ≤( 1α-1) 1θ _x≥ 1r(x). Applying the mean value theorem to the function t↦t1θt t 1θ yields r(x) r(x) =1θt01θ−1log(1+dx) = 1θt_0 1θ-1 (1+ dx ) ≤1θ(logx+log(1+dx))1θ−1log(1+dx) ≤ 1θ ( x+ (1+ dx ) ) 1θ-1 (1+ dx ) ≤1θ(logx+dx)1θ−1dx, ≤ 1θ ( x+ dx ) 1θ-1 dx, (log(1+y)≤y,∀y≥0 (1+y)≤ y,~~∀~y≥ 0) for some t0∈[logx,logx+log(1+d/x)]t_0∈[ x, x+ (1+d/x)]. The elementary inequality (a+b)k≤(2a)k+(2b)k(a+b)^k≤(2a)^k+(2b)^k for a,b,k>0a,b,k>0 yields r(x)≤1θ[(2logx)1θ−1dx+(2dx)1θ−1dx]≤21θ−1⋅dθ(1x(logx)1θ−1+d1θ−1),r(x)≤ 1θ [ (2 x ) 1θ-1 dx+ ( 2dx ) 1θ-1 dx ]≤ 2 1θ-1· dθ ( 1x ( x ) 1θ-1+d 1θ-1 ), where the last inequality is by x≥1x≥ 1. Thus one can take Bα,θ:=(1α−1)1θsupx≥1r(x)=21θ−1(1α−1)1θAα−1θ[e−(1θ−1)(1θ−1)1θ−1+A(α−1)(1θ−1)].B_α,θ:= ( 1α-1 ) 1θ _x≥ 1r(x)=2 1θ-1 ( 1α-1 ) 1θ A^α-1θ [e^- ( 1θ-1 ) ( 1θ-1 ) 1θ-1+A (α-1 ) ( 1θ-1 ) ]. The α>2α>2 case. For α>2α>2, we use the monotonicity of Rényi divergence, 2(P∥Q)≤α(P∥Q)D_2(P\|Q) _α(P\|Q), to obtain fθ(P∥Q)≤infα>2[α(P∥Q)]1θ+Bα,θ=[2(P∥Q)]1θ+B2,θ.D_f_θ(P\|Q)≤ _α>2 \[D_α(P\|Q)] 1θ+B_α,θ \=[D_2(P\|Q)] 1θ+B_2,θ. This completes the proof. ∎ C.3 Proof of Lemma 3.3 Proof. Let μr=νdμdνrE_μr=E_ν dμdνr. Now set x=dμdνx= dμdν, y=ry=r in Lemma H, taking expectation gives μr=νdμdνr≤21θνdμdν[log(dμdν+A)]1θ+νexp(yθ),E_μr=E_ν dμdνr≤ 2 1θE_ν\ dμdν[ ( dμdν+A)] 1θ\+E_ν (y^θ), and the definition of fθ(μ∥ν)D_f_θ(μ\|ν) shows μr≤21θfθ(μ∥ν)+νexp(rθ).E_μr≤ 2 1θD_f_θ(μ\|ν)+E_ν (r^θ). Finally, we use Lemmas 3.2.1 and 3.2.1 to obtain the upper bound of fθ(μ∥ν)D_f_θ(μ\|ν): μr≤21θfθ(μ∥ν)+νexp(rθ)≤21θ[(α(μ∥ν))1θ+Bα,θ]+νexp(rθ),E_μr≤ 2 1θD_f_θ(μ\|ν)+E_ν (r^θ)≤ 2 1θ[(D_α(μ\|ν)) 1θ+B_α,θ]+E_ν (r^θ), and equivalently, μr≤21θ[α(μ∥ν)+Cα,θ]1θ+νexp(rθ).E_μr≤ 2 1θ[D_α(μ\|ν)+C_α,θ] 1θ+E_ν (r^θ). ∎ Next, we prove the truncated version of the above lemma. C.4 Proof of Lemma 3.3 Proof. Suppose that μ and ν are probability measures on (Ω,ℱ)( ,F) such that μ≪νμ ν. Let r:Ω→[0,∞)r: →[0,∞) be a non-negative ℱF-measurable function such that r∈L1(μ)r∈ L^1(μ) and h(r)∈L1(ν)h(r)∈ L^1(ν). Let μr=νdμdνr.E_μr=E_ν dμdνr. Now we set x=dμdνx= dμdν, y=ry=r in Lemma H, giving μr≤21θfθ(μ∥ν)+2νh(r).E_μr≤ 2 1θD_f_θ(μ\|ν)+2E_νh(r). Finally, applying Lemmas 3.2.1 and 3.2.1, we upper bound fθ(μ∥ν)D_f_θ(μ\|ν). Let A and B satisfy the restriction in Lemma 3.2.1. If we further assume A≥max(1,2⌈2/θ⌉−2(⌈2/θ⌉)!,2e⌊2θ⌋)A≥ (1,2 2/θ -2( 2/θ )!,2e 2θ ), μr≤21θfθ(μ∥ν)+2νh(r)≤21θ[(α(μ∥ν))1θ+Bα,θ]+2νh(r),E_μr≤ 2 1θD_f_θ(μ\|ν)+2E_νh(r)≤ 2 1θ[(D_α(μ\|ν)) 1θ+B_α,θ]+2E_νh(r), and equivalently, μr≤21θ[α(μ∥ν)+Cα,θ]1θ+2νh(r).E_μr≤ 2 1θ[D_α(μ\|ν)+C_α,θ] 1θ+2E_νh(r). where h(y)=exp(yθ)−∑k=0⌊2θ⌋ykθ/k!h(y)= (y^θ)- _k=0 2θ y^kθ/k! is a truncated version of exp(yθ) (y^θ). ∎ Appendix D Proofs for Section 4 D.1 Mutual information for randomized maximum selector Let S=X1,…,XnS=\X_1,…,X_n\ with i.i.d. Weibull(θ)(θ) coordinates (θ<1θ<1), so ℙ(X>x)=e−xθP(X>x)=e^-x^θ. The selector W∈[n]W∈[n] is defined by ℙ(W=y∣S=x)=:p(y∣x)=ϵ+1−ϵn,if y=argmaxi∈[n]xi,1−ϵn,otherwise,P(W=y S=x)=:p(y x)= casesε+ 1-εn,&if y= _i∈[n]x_i,\\[6.0pt] 1-εn,&otherwise, cases where the argmax is a.s. unique by the continuity of Xi\X_i\. By symmetry, the marginal of W is uniform: p(y)=ℙ(W=y)=1n,y∈[n].p(y)=P(W=y)= 1n, y∈[n]. Write pm:=ϵ+1−ϵn=1+ϵ(n−1)n,po:=1−ϵn.p_m:=ε+ 1-εn= 1+ε(n-1)n, p_o:= 1-εn. Then, for any realization x, exactly one index is the maximizer and ∑y=1np(y∣x)logp(y∣x)p(y)=∑y=1np(y∣x)log(np(y∣x))=pmlog(npm)+(n−1)polog(npo), _y=1^np(y x) p(y x)p(y)= _y=1^np(y x) (n\,p(y x) )=p_m (np_m)+(n-1)\,p_o (np_o), which is constant in x. Therefore, I(W;S) I(W;S) =∫p(x)∑y=1np(y∣x)logp(y∣x)p(y)dx=pmlog(npm)+(n−1)polog(npo) = p(x) _y=1^np(y x) p(y x)p(y)dx=p_m (np_m)+(n-1)\,p_o (np_o) =1n[(1+ϵ(n−1))log(1+ϵ(n−1))+(n−1)(1−ϵ)log(1−ϵ)]. = 1n [(1+ε(n-1))\, (1+ε(n-1) )+(n-1)\,(1-ε)\, (1-ε) ]. D.2 Proof of Theorem 4.1.2 Proof. Without loss of generality, we assume maxi∈[n]‖Xi‖ψθ=1 _i∈[n]\|X_i\|_ _θ=1. By changing measure, PW,S(|XW|)=PW⊗PS(|XW|dPW,SdPW⊗PS).E_P_W,S(|X_W|)=E_P_W P_S (|X_W| dP_W,SdP_W P_S ). Let μ=PW,Sμ=P_W,S, ν=PW⊗PSν=P_W P_S and r=|XW|r=|X_W|. Use Lemma 3.3 (decorrelation lemma) PW,S(|XW|)≤21θIfθ(W,S)+PW⊗PSexp(|XW|θ)≤21θIα(W,S)+21θBα,θ+PW⊗PSexp(|XW|θ).E_P_W,S(|X_W|)≤ 2 1θI_f_θ(W,S)+E_P_W P_S (|X_W|^θ)≤ 2 1θI_α(W,S)+2 1θB_α,θ+E_P_W P_S (|X_W|^θ). Or using Lemma 3.3 (truncated decorrelation lemma), PW,S(|XW|)≤21θIfθ(W,S)+PW⊗PSexp(|XW|θ)≤21θ[Iα(W,S)+Cα,θ]1θ+PW⊗PSexp(|XW|θ).E_P_W,S(|X_W|)≤ 2 1θI_f_θ(W,S)+E_P_W P_S (|X_W|^θ)≤ 2 1θ[I_α(W,S)+C_α,θ] 1θ+E_P_W P_S (|X_W|^θ). By sub-Weibullity, PW⊗PSexp|XW|=w∼PWPSexp|Xw|≤2E_P_W P_S |X_W|=E_w P_WE_P_S |X_w|≤ 2. Then, if A satisfies the conditions of Lemma 3.2.1, then |XW|≤maxi∈[n]‖Xi‖ψθ(21/θ(Iα(W;S)+Cα,θ)1/θ+2).E|X_W|\;≤\; _i∈[n]\|X_i\|_ _θ\, (2^1/θ (I_α(W;S)+C_α,θ )^1/θ+2 ). And if A satisfies the conditions of Lemma 3.2.1, then |XW|≤maxi∈[n]‖Xi‖ψθ(21/θ(Iα(W;S))1/θ+21/θBα,θ+2).E|X_W|\;≤\; _i∈[n]\|X_i\|_ _θ\, (2^1/θ(I_α(W;S))^1/θ+2^1/θB_α,θ+2 ). ∎ D.3 Proof of Theorem 4.1.3 Proof. Without loss of generality, assume C=1C=1. Step 1: The partitions get finer. Assume that we are given increasing sequence partitions kk≥0\P_k\_k≥ 0 such that 0=TP_0=\T\, and kP_k is a ϵk _k-partition for k≥1k≥ 1 with ϵk:=e(T)2−k _k:=e(T)2^-k. Let [W]k∈k[W]_k _k be the cell-valued random variable that contains W with T=[W]0⊃[W]1⊃[W]2⊃[W]3⊃⋯.T=[W]_0⊃[W]_1⊃[W]_2⊃[W]_3⊃·s. For each k≥0k≥ 0, let Wk:=t[W]kW_k:=t_[W]_k is a designated representative point of [W]k∈k[W]_k _k. For each cell A∈kA _k, choose a representative tA∈Tt_A∈ T such that A⊂ℬd(tA,εk).A _d (t_A, _k ). Moreover, choose these representatives hierarchically so that whenever A∈kA _k is contained in its parent cell B∈k−1B _k-1, one has tA∈Bt_A∈ B. Hence, for every such parent-child pair, it gives a parent-child distance d(tA,tB)≤εk−1.d (t_A,t_B )≤ _k-1. (D.1) Figure 5: Partition-cell chaining argument. Step 2: Telescope along the representatives for finite |T||T|. For finite |T||T|, there exists a large m such that each cell in mP_m contains at most one point of T. Hence Wm=W_m=W. Pick an arbitrary anchor point t0∈[W]0=Tt_0∈[W]_0=T. Then XW=Xt0+∑k=1m(XWk−XWk−1).X_W=X_t_0+ _k=1^m(X_W_k-X_W_k-1). For k≥1k≥ 1, by the hierarchical choice of representatives and [W]k⊂[W]k−1[W]_k⊂[W]_k-1, (D.1) implies d(Wk,Wk−1)≤ϵk−1=e(T)2−k+1.d(W_k,W_k-1)≤ _k-1=e(T)2^-k+1. Let δk=e(T)2−(k−1) _k=e(T)2^-(k-1). Because [Xt0]=0E[X_t_0]=0, the linearity of expectation shows, [XW]=∑k=1mδk[XWk−XWk−1δk]≤∑k=1mδk|XWk−XWk−1δk|.E[X_W]= _k=1^m _k\,E [ X_W_k-X_W_k-1 _k ]≤ _k=1^m _k\,E | X_W_k-X_W_k-1 _k |. To bound the expectation of the k-th term, we apply the decorrelation lemma (Lemma 3.3) with μ=P[W]k,Sμ=P_[W]_k,S and ν=P[W]k⊗PSν=P_[W]_k P_S. Let Zk=|XWk−XWk−1|/δkZ_k=|X_W_k-X_W_k-1|/ _k. We obtain P[W]k,S[Zk]≤21/θIfθ([W]k;S)+P[W]k⊗PS[exp(Zkθ)].E_P_[W]_k,S[Z_k]≤ 2^1/θI_f_θ([W]_k;S)+E_P_[W]_k P_S [ (Z_k^θ) ]. Under the product measure P[W]k⊗PSP_[W]_k P_S, the [W]k[W]_k is independent of the data S, and Wk−1W_k-1 is determined by [W]k[W]_k. Conditioning on [W]k[W]_k, the variable ZkZ_k is a normalized increment of the process. By the (θ,1)(θ,1)-sub-Weibull assumption and the fact that d(Wk,Wk−1)≤δkd(W_k,W_k-1)≤ _k, we have PS[exp(|XWk−XWk−1|θδkθ)∣[W]k]≤PS[exp(|XWk−XWk−1|θdθ(Wk,Wk−1))∣[W]k]≤2.E_P_S [ ( |X_W_k-X_W_k-1|^θ _k^θ ) [W]_k ] _P_S [ ( |X_W_k-X_W_k-1|^θd^θ(W_k,W_k-1) ) [W]_k ]≤ 2. Integrating over P[W]kP_[W]_k yields ν[exp(|Zk|θ)]≤2E_ν[ (|Z_k|^θ)]≤ 2. Substituting this back into the sum gives [XW]≤∑k=1me(T)2−(k−1)(21/θIfθ([W]k;S)+2),E[X_W]≤ _k=1^me(T)2^-(k-1) (2^1/θI_f_θ([W]_k;S)+2 ), which proves the theorem for finite T. Step 3: Extension to separable processes. For m≥1m≥ 1, define the m-th hierarchical approximation of W by Wm:=t[W]m.W_m:=t_[W]_m. Since W∈[W]m⊂Bd(Wm,e(T)2−m)W∈[W]_m⊂ B_d(W_m,e(T)2^-m), we have d(Wm,W)≤e(T)2−m→m→∞0a.s.d(W_m,W)≤ e(T)2^-m [m→∞]0 .s. Therefore, the separability of the process implies that there exists Wm\W_m\ such that XW=limm→∞XWmX_W= _m→∞X_W_m almost surely. To justify dominated convergence [XW]=limm→∞[XWm]E[X_W]= _m→∞E[X_W_m], fix any u0∈Tu_0∈ T. Then |XWm|≤|Xu0|+supt∈T|Xt−Xu0|. |X_W_m |≤ |X_u_0 |+ _t∈ T |X_t-X_u_0 |. The first term is integrable because a sub-Weibull random variable has finite first moment. For the second term, supt∈T|Xt−Xu0|≤supt∈T(Xt−Xu0)+supt∈T(Xu0−Xt). _t∈ T |X_t-X_u_0 |≤ _t∈ T (X_t-X_u_0 )+ _t∈ T (X_u_0-X_t ). Both processes Xt−Xu0t∈T and Xu0−Xtt∈T \X_t-X_u_0 \_t∈ T and \X_u_0-X_t \_t∈ T are again separable (θ,C)(θ,C)-sub-Weibull processes, so Corollary 2.2 implies that each supremum has finite expectation. The dominated convergence theorem justifies the passage to the limit: [XW]=limm→∞[XWm]≤∑k=1∞e(T)2−(k−1)(21/θIfθ([W]k;S)+2).E[X_W]= _m→∞E[X_W_m]≤ _k=1^∞e(T)2^-(k-1) (2^1/θI_f_θ([W]_k;S)+2 ). The refinements (i) and (i) follow immediately by applying Lemmas 3.2.1 and 3.2.1, respectively, to bound the IfθI_f_θ term via Rényi mutual information. ∎ D.4 Proof of Theorem 4.2.3 The proof is based on the following lemma, adapted from the proof of Theorem 3.1 in Kuchibhotla and Chakrabortty (2022). Lemma D.1 Let Xii=1n\X_i\_i=1^n be a sequence of independent zero-mean r.v.s with ‖Xi‖ψθ≤1\|X_i\|_ _θ≤ 1. Then, for p≥2p≥ 2 and 0<θ≤10<θ≤ 1, we have ‖∑i=1naiXi‖p≤Lθ[p‖a‖2+p1/θ‖a‖∞]. \| _i=1^na_iX_i \|_p≤ L_θ [ p\|a\|_2+p^1/θ\|a\|_∞ ]. (D.2) where Lθ=:8e3(2π)1/4e1/24(e2/e/θ)1/θL_θ=: 8e^3(2π)^1/4e^1/24(e^2/e/θ)^1/θ. And if θ≥1θ≥ 1, ‖∑i=1naiXi‖p≤(4e+2(log2)1/θ)p‖a‖2+4ep1/θ‖a‖θ−1. \| _i=1^na_iX_i \|_p≤(4e+2( 2)^1/θ) p\|a\|_2+4ep^1/θ\|a\|_ θ-1. (D.3) Note that the moment inequality above only holds for p≥2p≥ 2, we need to introduce a truncated function of exp(yθ) (y^θ): h(y)=exp(yθ)−∑k=0⌊2θ⌋ykθk!h(y)= (y^θ)- _k=0 2θ y^kθk!. Lemma D.2 (A truncated exponential moment bound) Let Xii=1n\X_i\_i=1^n be a sequence of independent zero-mean sub-Weibull r.v.s with ‖Xi‖ψθ≤1\|X_i\|_ _θ≤ 1. Then, for a positive constant Mθ=21θ(θ+θ1θ)e1θLθ,0<θ<1[(4e+2(log2)1/θ)θ+4eθ1θ](2e)1θ,θ≥1 M_θ= cases2 1θ( θ+θ 1θ)e 1θL_θ,&0<θ<1\\[10.0pt] [(4e+2( 2)^1/θ) θ+4eθ 1θ ](2e) 1θ,&θ≥ 1 cases (D.4) and Lθ=:8e3(2π)1/4e1/24(e2/e/θ)1/θL_θ=: 8e^3(2π)^1/4e^1/24(e^2/e/θ)^1/θ, which depend only on θ. For 0<θ≤20<θ≤ 2, we have [h(∑k=1nXktkMθ‖t‖2)]≤2.E [h ( _k=1^nX_kt_kM_θ\|t\|_2 ) ]≤ 2. And for θ>2θ>2, [h(∑k=1nXktkMθ‖t‖θ−1)]≤2.E [h ( _k=1^nX_kt_kM_θ\|t\|_ θ-1 ) ]≤ 2. (D.5) Proof. We prove the result by cases. Case 1 (θ<1θ<1). Note that h(y)=exp(yθ)−∑k=0⌊2θ⌋ykθk!h(y)= (y^θ)- _k=0 2θ y^kθk!. We have by Lemma D.4, [h(∑kXktkMθ‖t‖2)] [h ( _kX_kt_kM_θ\|t\|_2 ) ] =∑k≥⌈2θ⌉1k![(∑kXktkMθ‖t‖2)kθ]≤∑k≥⌈2θ⌉1k!(LθMθ‖t‖2)kθ(‖t‖2kθ+(kθ)1θ‖t‖∞)kθ = _k≥ 2θ 1k!E [ ( _kX_kt_kM_θ\|t\|_2 )^kθ ]≤ _k≥ 2θ 1k! ( L_θM_θ\|t\|_2 )^kθ(\|t\|_2 kθ+(kθ) 1θ\|t\|_∞)^kθ ≤∑k≥⌈2θ⌉(θk12−1θ+θ1θ‖t‖∞‖t‖2)kθ(e1θLθMθ)kθ(k!≥(k/e)k) ≤ _k≥ 2θ ( θk 12- 1θ+θ 1θ \|t\|_∞\|t\|_2)^kθ ( e 1θL_θM_θ )^kθ (k!≥(k/e)^k) ≤∑k=1∞((θ+θ1θ)e1θLθMθ)kθ=∑k=1∞2−k=2, ≤ _k=1^∞ ( ( θ+θ 1θ)e 1θL_θM_θ )^kθ= _k=1^∞2^-k=2, where we choose Mθ=21θ(θ+θ1θ)e1θLθM_θ=2 1θ( θ+θ 1θ)e 1θL_θ for θ<1θ<1. Case 2 (1≤θ≤21≤θ≤ 2). Let β=θ−1≥2β= θ-1≥ 2. By monotonicity of the ℓp _p norm, we have ‖t‖β≤‖t‖2.\|t\|_β≤\|t\|_2. (D.6) Then, [h(∑kXktkMθ‖t‖2)] [h ( _kX_kt_kM_θ\|t\|_2 ) ] =∑k≥⌈2θ⌉1k![(∑kXktkMθ‖t‖2)kθ] = _k≥ 2θ 1k!E [ ( _kX_kt_kM_θ\|t\|_2 )^kθ ] ≤∑k≥⌈2θ⌉1k!(1Mθ‖t‖2)kθ[(4e+2(log2)1/θ)‖t‖2kθ+(4e)(kθ)1θ‖t‖β]kθ ≤ _k≥ 2θ 1k! ( 1M_θ\|t\|_2 )^kθ[(4e+2( 2)^1/θ)\|t\|_2 kθ+(4e)(kθ) 1θ\|t\|_β]^kθ (Byk!≥(k/e)kand(D.6)) (By~k!≥(k/e)^k~and~ Norm) ≤∑k≥⌈2θ⌉((4e+2(log2)1/θ)θk12−1θ+(4e)θ1θ)kθ(e1θMθ)kθ ≤ _k≥ 2θ ((4e+2( 2)^1/θ) θk 12- 1θ+(4e)θ 1θ )^kθ ( e 1θM_θ )^kθ ≤∑k(((4e+2(log2)1/θ)θ+4eθ1θ)e1θMθ)kθ. ≤ _k ( ((4e+2( 2)^1/θ) θ+4eθ 1θ )e 1θM_θ )^kθ. So we choose Mθ=[(4e+2(log2)1/θ)θ+4eθ1θ](2e)1θM_θ=[(4e+2( 2)^1/θ) θ+4eθ 1θ](2e) 1θ for 1≤θ≤21≤θ≤ 2. Case 3 (θ>2θ>2). Let β=θ−1∈(1,2)β= θ-1∈(1,2), we have ‖t‖2≤‖t‖β\|t\|_2≤\|t\|_β (D.7) Using the same derivation as Case 2, it gives [h(∑kXktkMθ‖t‖β)] [h ( _kX_kt_kM_θ\|t\|_β ) ] =∑k≥⌈2θ⌉1k![(∑kXktkMθ‖t‖β)kθ] = _k≥ 2θ 1k!E [ ( _kX_kt_kM_θ\|t\|_β )^kθ ] ≤∑k≥⌈2θ⌉1k!(1Mθ‖t‖β)kθ((4e+2(log2)1/θ)‖t‖2kθ+(4e)(kθ)1θ‖t‖β)kθ ≤ _k≥ 2θ 1k! ( 1M_θ\|t\|_β )^kθ((4e+2( 2)^1/θ)\|t\|_2 kθ+(4e)(kθ) 1θ\|t\|_β)^kθ (k!≥(k/e)kand(D.7)) (k!≥(k/e)^kand~ Norm1)~ ≤∑k≥⌈2θ⌉((4e+2(log2)1/θ)θk12−1θ+(4e)θ1θ)kθ(e1θMθ)kθ ≤ _k≥ 2θ ((4e+2( 2)^1/θ) θk 12- 1θ+(4e)θ 1θ )^kθ ( e 1θM_θ )^kθ ≤∑k(((4e+2(log2)1/θ)θ+4eθ1θ)e1θMθ)kθ. ≤ _k ( ((4e+2( 2)^1/θ) θ+4eθ 1θ )e 1θM_θ )^kθ. So we choose Mθ=[(4e+2(log2)1/θ)θ+4eθ1θ](2e)1θM_θ=[(4e+2( 2)^1/θ) θ+4eθ 1θ](2e) 1θ for θ>2θ>2. ∎ Proof. of Theorem 4.2.3. Write S=Z1,…,ZnS=\Z_1,…,Z_n\ and ℓ¯(w,Z):=μ[ℓ(w,Z)]−ℓ(w,Z) (w,Z):=E_μ[ (w,Z)]- (w,Z), gen(W,S)=1n∑i=1nℓ¯(W,Zi).gen(W,S)= 1n _i=1^n (W,Z_i). Let C:=supw∈‖ℓ¯(w,Z)‖ψθ∈(0,∞)C:= _w \| (w,Z)\|_ _θ∈(0,∞), and define the normalized variables Xi:=ℓ¯(W,Zi)C,i=1,…,n.X_i:= (W,Z_i)C, i=1,…,n. Under the product measure PW⊗PSP_W P_S (i.e. W independent of S), the random variables X1,…,XnX_1,…,X_n are independent, centered, and satisfy ‖Xi‖ψθ≤1\|X_i\|_ _θ≤ 1. Step 1: a truncated exponential moment bound under PW⊗PSP_W P_S. Fix t=(t1,…,tn)t=(t_1,…,t_n) with ti≡1/nt_i≡ 1/n. Then ‖t‖2=n−1/2\|t\|_2=n^-1/2. Applying Lemma D.4 to Xii=1n\X_i\_i=1^n with this choice of t, we obtain (for some constant Mθ>0M_θ>0) PW⊗PS[h(∑i=1nXitiMθ‖t‖2)]≤2.E_P_W P_S [h ( _i=1^nX_it_iM_θ\|t\|_2 ) ]≤ 2. Since ∑i=1nXiti=1n∑i=1nXi=gen(W,S)/C _i=1^nX_it_i= 1n _i=1^nX_i=gen(W,S)/C and Mθ‖t‖2=Mθ/nM_θ\|t\|_2=M_θ/ n, the last display is PW⊗PS[h(n|gen(W,S)|MθC)]≤2.E_P_W P_S [h ( n\,|gen(W,S)|M_θ\,C ) ]≤ 2. Step 2: change of measure via the truncated decorrelation lemma. Let μ:=PW,Sμ:=P_W,S and ν:=PW⊗PSν:=P_W P_S. Define the nonnegative random variable r:=n|gen(W,S)|MθC.r:= n\,|gen(W,S)|M_θ\,C. Then Step 1 gives ν[h(r)]≤2E_ν[h(r)]≤ 2, hence h(r)∈L1(ν)h(r)∈ L^1(ν). Applying Lemma 3.3 with this (μ,ν,r)(μ,ν,r) yields μ[r]≤21/θDfθ(μ∥ν)+2ν[h(r)].E_μ[r]≤ 2^1/θD_f_θ(μ\|ν)+2\,E_ν[h(r)]. Using ν[h(r)]≤2E_ν[h(r)]≤ 2 from Step 1, we obtain the upper bound PW,S[r]≤21/θDfθ(PW,S∥PW⊗PS)+4.E_P_W,S[r]≤ 2^1/θD_f_θ(P_W,S\|P_W P_S)+4. Step 3: conclude and identify the information term. Multiplying the last inequality by MθC/nM_θC/ n gives |gen(W,S)|≤MθCn(21/θDfθ(PW,S∥PW⊗PS)+4).E |gen(W,S) |≤ M_θC n (2^1/θD_f_θ(P_W,S\|P_W P_S)+4 ). The definition of the fθf_θ-mutual information Ifθ(S;W)=Dfθ(PW,S∥PW⊗PS)I_f_θ(S;W)=D_f_θ(P_W,S\|P_W P_S) gives |gen(W,S)|≤MθCn(21/θIfθ(S;W)+4).E |gen(W,S) |≤ M_θC n\, (2^1/θI_f_θ(S;W)+4 ). Finally, the refinement using Rényi mutual information Iα(S;W)I_α(S;W) follows immediately by applying Lemmas 3.2.1 and 3.2.1 to upper bound Ifθ(S;W)I_f_θ(S;W). ∎ D.5 Proof of Theorem 4.2.4 First, we need the following lemma. Lemma D.3 (A change-of-measure inequality with truncated sub-Weibull tail) Let (Ω,ℱ)( ,F) be a measurable space and let μ,νμ,ν be probability measures on (Ω,ℱ)( ,F) such that μ≪νμ ν. Fix 0<θ≤20<θ≤ 2, and let h(x)=exp(xθ)−∑k=0⌊2/θ⌋xkθk!h(x)= (x^θ)- _k=0 2/θ x^kθk! with x≥0x≥ 0. Let g:Ω→[0,∞)g: →[0,∞) be measurable such that h(g)∈L1(ν)h(g)∈ L^1(ν) and (logdμdν)1/θ∈L1(μ) ( dμdν )^1/θ∈ L^1(μ). Then μ[g]≤41/θ(log(ν[h(g)]+1))1/θ+μ[logdμdν]1/θ+Eθ, _μ[g]≤ 4^1/θ \ ( (E_ν[h(g)]+1) )^1/θ+E_μ [ dμdν ]^1/θ+E_θ \, (D.8) where the constant Eθ>0E_θ>0 satisfying 41/θEθ:=supx≥1xexp(xθ/2)h(x)+1+1.4^1/θE_θ:= _x≥ 1 x\, (x^θ/2)h(x)+1+1. Proof. Set ϕ:=dμdνφ:= dμdν and denote G:=ν[h(g)]+1∈(1,∞)G:=E_ν[h(g)]+1∈(1,∞). Define the measurable set T:=ω∈Ω:ϕ(ω)≥exp(g(ω)θ/2)G.T:= \ω∈ :\;φ(ω)≥ (g(ω)^θ/2)G \. We decompose Eμ[g]=∫gμ=∫Tgμ+∫TcgμE_μ[g]= g\,dμ= _Tg\,dμ+ _T^cg\,dμ, and bound the two terms separately. Step 1: bound over TcT^c. Write Tc=(Tc∩g<1)∪(Tc∩g≥1)T^c=(T^c∩\g<1\)∪(T^c∩\g≥ 1\). Since g≥0g≥ 0, ∫Tc∩g<1gμ≤1. _T^c∩\g<1\g\,dμ≤ 1. On TcT^c we have ϕ<exp(gθ/2)/Gφ< (g^θ/2)/G, hence on Tc∩g≥1T^c∩\g≥ 1\, gdμ=gϕdν≤gexp(gθ/2)Gdν.g\,dμ=gφ\,dν≤ g (g^θ/2)G\,dν. Therefore, ∫Tcgμ≤1+∫g≥1gexp(gθ/2)Gν≤1+1Gsupx≥1xexp(xθ/2)h(x)+1∫(h(g)+1)ν. _T^cg\,dμ≤ 1+ _\g≥ 1\ g (g^θ/2)G\,dν≤ 1+ 1G _x≥ 1 x (x^θ/2)h(x)+1 (h(g)+1)\,dν. (D.9) Since ∫(h(g)+1)ν=G (h(g)+1)\,dν=G, the right-hand side of (D.9) becomes ∫Tcgμ≤supx≥1xexp(xθ/2)h(x)+1+1=41/θEθ. _T^cg\,dμ≤ _x≥ 1 x (x^θ/2)h(x)+1+1=4^1/θE_θ. Step 2: bound over T. On T we have ϕ≥exp(gθ/2)/Gφ≥ (g^θ/2)/G, hence gθ≤2log(Gϕ)=2(logG+logϕ)≤2(logG+(logϕ)+)g^θ≤ 2 (Gφ)=2 ( G+ φ )≤ 2 ( G+( φ)_+ ), so that g≤21/θ(logG+(logϕ)+)1/θ≤41/θ((logG)1/θ+(logϕ)+1/θ),g≤ 2^1/θ ( G+( φ)_+ )^1/θ≤ 4^1/θ (( G)^1/θ+( φ)_+^1/θ ), (D.10) where the last inequality uses (a+b)1/θ≤21/θ(a1/θ+b1/θ)(a+b)^1/θ≤ 2^1/θ(a^1/θ+b^1/θ) for 0<θ≤20<θ≤ 2 by CrC_r-inequality. Integrating (D.10) w.r.t. μ over T gives ∫Tgμ≤41/θ(logG)1/θ+41/θμ(logϕ)+1/θ. _Tg\,dμ≤ 4^1/θ( G)^1/θ+4^1/θE_μ( φ)_+^1/θ. Combining the bounds for ∫Tgμ _Tg\,dμ and ∫Tcgμ _T^cg\,dμ, we obtain (D.8). ∎ of Theorem 4.2.4. Let C:=supw∈‖ℓ¯(w,Z)‖ψθ<∞C:= _w \| (w,Z)\|_ _θ<∞ for 0<θ≤20<θ≤ 2, and write the generalization error as gen(w,S)=[ℓ(w,Z)]−1n∑i=1nℓ(w,Zi)=−1n∑i=1nℓ¯(w,Zi).gen(w,S)=E[ (w,Z)]- 1n _i=1^n (w,Z_i)=- 1n _i=1^n (w,Z_i). Fix w∈w , ℓ¯(w,Z1),…,ℓ¯(w,Zn) (w,Z_1),…, (w,Z_n) are independent, mean-zero with ‖ℓ¯(w,Zi)‖ψθ≤C\| (w,Z_i)\|_ _θ≤ C. Step 1: truncated MGF bound and a change-of-measure inequality. Let h(y)=exp(yθ)−∑k=0⌊2/θ⌋ykθ/k!h(y)= (y^θ)- _k=0 2/θ y^kθ/k!. Apply Lemma D.4 to Xi:=ℓ¯(w,Zi)/CX_i:= (w,Z_i)/C and ti:=1/nt_i:=1/ n. Since ‖Xi‖ψθ≤1\|X_i\|_ _θ≤ 1 and ‖t‖2=1\|t\|_2=1, there exists a constant Kθ>0K_θ>0 (depending only on θ) such that PSh(n|gen(w,S)|KθC)≤2.E_P_S\,h\! ( n\,|gen(w,S)|K_θC )≤ 2. (D.11) Integrating (D.11) w.r.t. w∼PWw P_W yields PS⊗PWh(n|gen(W,S)|KθC)≤2.E_P_S P_W\,h\! ( n\,|gen(W,S)|K_θC )≤ 2. (D.12) Define the random variable g(w):=n|gen(w,S)|KθCg(w):= n\,|gen(w,S)|K_θC, viewed as a function of w for the realized sample S. For each fixed S, apply Lemma D.5 with μ=PW∣Sμ=P_W S and ν=PWν=P_W to obtain PW∣Sg≤41/θ((log(PWh(g)+1))1/θ+PW∣S[log(dPW∣SdPW)+]1/θ+Eθ),E_P_W Sg≤ 4^1/θ ( ( (E_P_Wh(g)+1) )^1/θ+E_P_W S [ ( dP_W SdP_W )_+ ]^1/θ+E_θ ), (D.13) where Eθ>0E_θ>0 depends only on θ. Multiplying (D.13) by KθC/nK_θC/ n gives PW∣S|gen(W,S)|≤41/θKθCn(PW∣S[log(dPW∣SdPW)+]1/θ+Eθ+(log(PWh(g)+1))1/θ).E_P_W S|gen(W,S)|≤ 4^1/θK_θC n (E_P_W S [ ( dP_W SdP_W )_+ ]^1/θ+E_θ+ ( (E_P_Wh(g)+1) )^1/θ ). (D.14) Step 2: high-probability control of PWh(g)E_P_Wh(g). By (D.12), PSPW[h(g)+1]=PS⊗PW[h(g)+1]≤3.E_P_S\,E_P_W\,[h(g)+1]=E_P_S P_W[h(g)+1]≤ 3. Hence, by Markov’s inequality, for any δ∈(0,1)δ∈(0,1), PS(PW[h(g)+1]>3δ)≤δ3PSPW[h(g)+1]≤δ.P_S\! (E_P_W[h(g)+1]> 3δ )≤ δ3\,E_P_SE_P_W[h(g)+1]≤δ. Therefore, on an event ℰ:=PW[h(g)+1]≤3/δE:=\E_P_W[h(g)+1]≤ 3/δ\ with PS(ℰ)≥1−δP_S(E)≥ 1-δ, we have PW[h(g)+1]≤3/δE_P_W[h(g)+1]≤ 3/δ and thus log(PWh(g)+1)≤log(PW[h(g)+1])≤log(3/δ). (E_P_Wh(g)+1)≤ (E_P_W[h(g)+1])≤ (3/δ). Substituting this into (D.14) proves that on ℰE, PW∣S|gen(W,S)|≤41/θKθCn(PW∣S[log(dPW∣SdPW)+]1/θ+Eθ+(log(3/δ))1/θ)E_P_W S|gen(W,S)|≤ 4^1/θK_θC n (E_P_W S [ ( dP_W SdP_W )_+ ]^1/θ+E_θ+( (3/δ))^1/θ ) with probability at least 1−δ1-δ. ∎ D.6 Proof of Theorem 4.2.5 Proof. Similar to the proof of Theorem 4.1.3, for each k≥1k≥ 1, let ϵk=e()2−k _k=e(W)2^-k. Let Wk:=t[W]kW_k:=t_[W]_kbe a representative element of the cell [W]k∈k[W]_k _k. First, consider the case where ||<∞|W|<∞. The sequence of partitions is increasing and finite; hence, there exists an integer m sufficiently large such that Wm=W_m=W almost surely. We decompose gen(W,S)gen(W,S) as a telescoping sum. Choose a deterministic point w0∈w_0 and set W0:=w0W_0:=w_0. Since ℓ¯(w0,Z) (w_0,Z) is centered, [gen(w0,S)]=[1n∑i=1nℓ¯(w0,Zi)]=0.E[gen(w_0,S)]=E\! [ 1n _i=1^n (w_0,Z_i) ]=0. Therefore, gen(W,S)−gen(w0,S)=∑k=1m(gen(Wk,S)−gen(Wk−1,S)),gen(W,S)-gen(w_0,S)= _k=1^m (gen(W_k,S)-gen(W_k-1,S) ), and hence [gen(W,S)]≤∑k=1m|gen(Wk,S)−gen(Wk−1,S)|.E[gen(W,S)]≤ _k=1^mE |gen(W_k,S)-gen(W_k-1,S) |. (D.15) Therefore, the linearity implies [gen(Wm,S)]=∑k=1m[gen(Wk,S)−gen(Wk−1,S)]=∑k=1m[1n∑i=1n(ℓ¯(Wk,Zi)−ℓ¯(Wk−1,Zi))].E[gen(W_m,S)]= _k=1^mE [gen(W_k,S)-gen(W_k-1,S) ]= _k=1^mE [ 1n _i=1^n ( (W_k,Z_i)- (W_k-1,Z_i) ) ]. By the sub-Weibull process assumption, ‖ℓ¯(Wk,Z)−ℓ¯(Wk−1,Z)‖ψθ≤d(Wk,Wk−1)\| (W_k,Z)- (W_k-1,Z)\|_ _θ≤ d(W_k,W_k-1). By construction of the partitions, d(Wk,Wk−1)≤ϵk−1=e(T)2−(k−1)d(W_k,W_k-1)≤ _k-1=e(T)2^-(k-1). Let δk=e(T)2−(k−1) _k=e(T)2^-(k-1). We normalize the increments by δk _k: [gen(Wm,S)]=∑k=1mδkn[n∑i=1n(ℓ¯(Wk,Zi)−ℓ¯(Wk−1,Zi))nδk].E[gen(W_m,S)]= _k=1^m _k n\,E [ n _i=1^n( (W_k,Z_i)- (W_k-1,Z_i))n _k ]. Let Yk=n∑i=1n(ℓ¯(Wk,Zi)−ℓ¯(Wk−1,Zi))nδkY_k= n _i=1^n( (W_k,Z_i)- (W_k-1,Z_i))n _k. We apply the truncated decorrelation lemma (Lemma 3.3) for rk=|Yk|/Mθr_k=|Y_k|/M_θ with μ=P[W]k,Sμ=P_[W]_k,S and ν=P[W]k⊗PSν=P_[W]_k P_S, then P[W]k,S[rk]≤21/θIfθ([W]k;S)+2P[W]k⊗PS[h(rk)],E_P_[W]_k,S[r_k]≤ 2^1/θI_f_θ([W]_k;S)+2\,E_P_[W]_k P_S[h(r_k)], (D.16) where h(y)h(y) is the truncated exponential. Under the product measure P[W]k⊗PSP_[W]_k P_S: [W]k[W]_k is independent of S. Conditioning on [Wk][W_k], Wk−1W_k-1 is fixed, and the term YkY_k is a normalized sum of independent, mean-zero sub-Weibull random variables. Thus the truncated moment bound (Lemma D.4) with appropriate scaling MθM_θ for 0<θ≤20<θ≤ 2 applies conditionally on [W]k[W]_k with the choice ti≡1/nt_i≡ 1/n, whose Euclidean norm is ‖t‖2=n−1/2\|t\|_2=n^-1/2. Let h(y)=eyθ−∑j=0⌊2/θ⌋yjθ/j!h(y)=e^y^θ- _j=0 2/θ y^jθ/j!. We have PS[h(|Yk|Mθ)∣[W]k]≤2.E_P_S [h ( |Y_k|M_θ ) [W]_k ]≤ 2. Integrating over P[W]kP_[W]_k gives PWk⊗PS[h(rk)]≤2E_P_W_k P_S[h(r_k)]≤ 2 and substituting it into (D.16), we have [|gen(Wk,S)−gen(Wk−1,S)|]≤Mθδkn(21/θIfθ([W]k;S)+4).E[|gen(W_k,S)-gen(W_k-1,S)|]≤ M_θ _k n (2^1/θI_f_θ([W]_k;S)+4 ). Summing over k: [gen(Wm,S)]≤Mθe()n∑k=1m2−(k−1)(21/θIfθ([W]k;S)+4).E[gen(W_m,S)]≤ M_θe(W) n _k=1^m2^-(k-1) (2^1/θI_f_θ([W]_k;S)+4 ). This proves the result for finite W. For a general separable metric space W, the separability of the loss process implies that there exists a sequence Wm\W_m\ such that Wm→W_m→ W a.s.. To see this, for m≥1m≥ 1, define Wm:=t[W]mW_m:=t_[W]_m. Since W∈[W]m⊂Bd(Wm,e()2−m)W∈[W]_m⊂ B_d(W_m,e(W)2^-m), we have d(Wm,W)→0d(W_m,W)→ 0 a.s., hence gen(Wm,S)→m→∞gen(W,S)a.s.gen(W_m,S) [m→∞]gen(W,S) .s. The condition that the Dudley integral of the process is finite implies that the supremum of the process is integrable: |gen(Wm,S)|≤supw∈|gen(w,S)|∈L1.|gen(W_m,S)|≤ _w |gen(w,S)|∈ L^1. By the dominated convergence theorem, we can pass to the limit m→∞m→∞ in the expectation, [gen(W,S)]=limm→∞[gen(Wm,S)]≤e()Mθn∑k=1∞2−(k−1)(21/θIfθ([W]k;S)+4)E [gen(W,S) ]= _m→∞E [gen(W_m,S) ]≤ e(W)M_θ n _k=1^∞2^-(k-1) (2^1/θI_f_θ([W]_k;S)+4 ) This yields the infinite-series bound (4.4). ∎ Appendix E Proofs in Section 5 E.1 Proof of Lemma 5.2 Let (,ℬ)(Y,B) be a general measurable space. For a fixed x, we aim to solve: maxπ(⋅|x)∫r(x,y)π(dy|x) _π(·|x) _Yr(x,y)π(dy|x) subject to ∫π(dy|x)=1 _Yπ(dy|x)=1 and for α>1α>1 1α−1log∫(π(dy|x)π0(dy|x))απ0(dy|x)≤ϵ. 1α-1 _Y ( π(dy|x) _0(dy|x) )^α _0(dy|x)≤ε. Let P0=π0(⋅|x)P_0= _0(·|x) and q(y)=dπ(⋅|x)dP0(y)q(y)= dπ(·|x)dP_0(y) be the Radon-Nikodym derivative. Step 1: Functional Setup.The problem can be rewritten as maximizing J[q]J[q]: J[q]=∫r(x,y)q(y)P0(dy)J[q]= _Yr(x,y)q(y)P_0(dy) subject to G1[q]=∫qP0−1=0G_1[q]= qdP_0-1=0 and G2[q]=∫qαP0−e(α−1)ϵ≤0G_2[q]= q^αdP_0-e^(α-1)ε≤ 0. We define the Lagrangian functional ℒ[q]L[q] with multipliers t∈ℝt and λ≥0λ≥ 0: ℒ[q]=∫[r(x,y)q(y)−tq(y)−λq(y)α]P0(dy)+t+λe(α−1)ϵL[q]= _Y [r(x,y)q(y)-tq(y)-λ q(y)^α ]P_0(dy)+t+λ e^(α-1)ε (E.1) Let L(y,q)=(r(x,y)−t)q−λαqαL(y,q)=(r(x,y)-t)q-λα q^α be the Lagrangian density. In the calculus of variations, for a functional ∫L(y,q,q′)P0 L(y,q,q )dP_0, the Euler-Lagrange equation is ∂L∂q−dy∂L∂q′=0 ∂ L∂ q- ddy ∂ L∂ q =0. Since L does not depend on the derivative q′q , the condition for q to be an extremum is the pointwise stationary condition: ∂L∂q=r(x,y)−t−λαq(y)α−1=0P0-a.s. ∂ L∂ q=r(x,y)-t-λα q(y)^α-1=0 P_0-a.s. (E.2) Step 2: Non-negativity and Truncation Solution To handle the constraint q(y)≥0q(y)≥ 0, we apply the Karush-Kuhn-Tucker condition to the Euler-Lagrange equation. • Case 1: r(x,y)>tr(x,y)>t. In this region, r(x,y)−tr(x,y)-t is positive. To satisfy Eq. (E.2), q(y)q(y) must be positive: q(y)=(r(x,y)−tλα)1α−1>0q(y)= ( r(x,y)-tλα ) 1α-1>0 • Case 2: r(x,y)≤tr(x,y)≤ t. If we assume q(y)>0q(y)>0, then q(y)α−1=(r−t)/λα≤0q(y)^α-1=(r-t)/λα≤ 0, which contradicts α>1α>1 and q>0q>0. Thus, we must have q(y)=0q(y)=0. Combining these, the optimal density takes the truncated power-law form: q∗(y)=((r(x,y)−t)+λα)1α−1.q^*(y)= ( (r(x,y)-t)_+λα ) 1α-1. The optimal policy is given by π∗(dy|x)=q∗(y)π0(dy|x)π^*(dy|x)=q^*(y) _0(dy|x). By substituting q∗q^* into the normalization constraint ∫q∗P0=1 q^*dP_0=1, we obtain: π∗(y|x)=π0(y|x)(r(x,y)−t)+1α−1∫(r(x,y′)−t)+1α−1π0(dy′|x)=π0(y|x)(r(x,y)−t)+1α−1Y∼π0[(r(x,Y)−t)+1α−1].π^*(y|x)= _0(y|x)(r(x,y)-t)_+ 1α-1 _Y(r(x,y )-t)_+ 1α-1 _0(dy |x)= _0(y|x)(r(x,y)-t)_+ 1α-1E_Y _0 [(r(x,Y)-t)_+ 1α-1 ]. (E.3) The parameter t is the value such that the Rényi divergence constraint is met with equality. E.2 Proof of Theorem 5.2 Proof. Fix x∈x and abbreviate π(⋅∣x)π(· x) and π0(⋅∣x) _0(· x) by π and π0 _0, respectively. Let r¯(x,y):=r(x,y)−Y∼π0r(x,Y),y∈. r(x,y):=r(x,y)-E_Y _0r(x,Y), y . Define the nonnegative random variable Z:=|r¯(Y,x)|CZ:= | r(Y,x)|C with Y∼π0(⋅∣x)Y _0(· x). By the assumption ‖r¯(x,Y)‖ψθ≤C\| r(x,Y)\|_ _θ≤ C, under Y∼π0(⋅∣x)Y _0(· x), we have π0exp(Zθ)=π0exp(|r¯(Y)|θCθ)≤2.E_ _0 (Z^θ)=E_ _0 \! ( | r(Y)|^θC^θ )≤ 2. We now apply the decorrelation lemma (Lemma 3.3) with μ=πμ=π, ν=π0ν= _0, and the measurable function r(⋅):=|r¯(⋅,x)|/Cr(·):=| r(·,x)|/C. This yields π[|r¯(Y)|C]≤ 21/θfθ(π∥π0)+π0exp(|r¯(Y)|θCθ)≤ 21/θfθ(π∥π0)+2.E_π\! [ | r(Y)|C ]\;≤\;2^1/θ\,D_f_θ(π\| _0)\;+\;E_ _0 \! ( | r(Y)|^θC^θ )\;≤\;2^1/θ\,D_f_θ(π\| _0)+2. Multiplying both sides by C gives π|r¯(Y)|≤C(21/θfθ(π∥π0)+2).E_π| r(Y)|\;≤\;C (2^1/θ\,D_f_θ(π\| _0)+2 ). Since πr¯(Y)=πr(x,Y)−π0r(x,Y)E_π r(Y)=E_πr(x,Y)-E_ _0r(x,Y), we conclude by |πr¯|≤π|r¯||E_π r| _π| r| that |πr(x,Y)−π0r(x,Y)|≤C(21/θfθ(π∥π0)+2). |E_πr(x,Y)-E_ _0r(x,Y) |\;≤\;C (2^1/θ\,D_f_θ(π\| _0)+2 ). Finally, invoking Lemma 3.2.1 and Lemma 3.2.1 to upper bound fθ(π∥π0)D_f_θ(π\| _0) in terms of α(π∥π0)D_α(π\| _0) yields the two displayed Rényi-based bounds in the theorem. For π∗π^* solving (5.3), we have α(π∗∥π0)≤ϵD_α(π^*\| _0)≤ε for each x. Substituting this into the preceding bounds (and averaging over x if desired) gives the stated guarantee for π∗π^*. ∎ E.3 Proof of Theorem 5.3 Proof. By Assumption 5.3, we need to bound α(rn(x)∥r(x)).D_α(r_n(x)\|r(x)). This reduces to the following lemma by setting rn(x)∼πn=:νr_n(x) _n=:ν and r(x)∼π0=:μr(x) _0=:μ. Lemma E.1 (Rényi divergence of the maximum of i.i.d. draws) Let μ and ν be any one univarate probability distributions. Assume α>1α>1. Let X and Xii=1n∼i.i.d.μ\X_i\_i=1^n i.i.d. μ be random variables, and put Rn=maxi∈[n]Xi∼νR_n= _i∈[n]X_i ν. Then Dα(ν∥μ)≤1α−1log(nα(n−1)+1)D_α(ν\|μ)≤ 1α-1 ( n^α(n-1)+1 ) and DKL(ν∥μ)≤logn−n−1nD_KL(ν\|μ)≤ n- n-1n. Proof. The KL case is given by Theorem 1 in Mroueh and Nitsure (2025) and can also be proved by taking the limit α→1α→ 1, so here we prove the Rényi case: α>1α>1. Let Q be the left-continuous quantile function of X. For U and Uii=1n∼i.i.d.U[0,1]\U_i\_i=1^n i.i.d. U[0,1], R=dQ(U),Rn=dQ(U(n)),R d=Q(U), R_n d=Q(U_(n)), where U(n):=max1≤i≤nUiU_(n):= _1≤ i≤ nU_i. By data processing inequality for Rényi divergence, Dα(Rn∥R)≤Dα(U(n)∥U).D_α(R_n\|R)≤ D_α(U_(n)\|U). Now U(n)U_(n) has density nun−1nu^n-1 on [0,1][0,1], so Dα(Rn∥R)≤Dα(U(n)∥U)=1α−1log∫01(nun−1)αu=1α−1lognα(n−1)+1.D_α(R_n\|R)≤ D_α(U_(n)\|U)= 1α-1 _0^1 (nu^n-1 )^α\,du= 1α-1 n^α(n-1)+1. By L’Hôpital’s Rule, limα→11α−1lognα(n−1)+1=logn−n−1n _α→ 1 1α-1 n^α(n-1)+1= n- n-1n and we have DKL(ν∥μ)≤logn−n−1nD_KL(ν\|μ)≤ n- n-1n. ∎ Follows from Assumption 5.3 and another application of data processing: Dα(πn∥π0)≤Dα(Rn∥R).D_α( _n\| _0)≤ D_α(R_n\|R). Now, in this setting, since 1α−1log(nα(n−1)+1)≤logn 1α-1 ( n^α(n-1)+1 )≤ n for α>1α>1 and n≥1n≥ 1, we have α(πn∥π0)≤1α−1log(nα(n−1)+1)≤lognD_α( _n\| _0)≤ 1α-1 ( n^α(n-1)+1 )≤ n So if n≤exp(ε)n≤ ( ), then α(πn∥π0)≤εD_α( _n\| _0)≤ . Applying the decorrelation lemma (Lemma 3.3) to r¯(x,Y):=|r(x,Y)−Y∼π0r(x,Y)|/C,y∈ r(x,Y):=|r(x,Y)-E_Y _0r(x,Y)|/C,~~y , similar to the proof of Theorem 5.2, we have πn(⋅|x)r−π0(⋅|x)r≤|πn(⋅|x)r−π0(⋅|x)r|≤C(21/θ[α(πn∥π0)+Cα,θ]1/θ+2).E_ _n(·|x)r-E_ _0(·|x)r≤|E_ _n(·|x)r-E_ _0(·|x)r|≤ C (2^1/θ [D_α( _n\| _0)+C_α,θ ]^1/θ+2 ). from α(πn∥π0)≤εD_α( _n\| _0)≤ . This completes the proof. ∎ E.4 Proof of Lemma F We first state a lemma for the α-Rényi divergence between two d-dimensional Gaussian distributions. Lemma E.2 Let p=(μ1,σ2Id)p=N( _1,σ^2I_d) and q=(μ2,σ2Id)q=N( _2,σ^2I_d) be d-dimensional Gaussian distributions with identical isotropic covariance σ2Idσ^2I_d. Then for any α>0α>0, α≠1α≠ 1, the α Rényi divergence is α(p∥q)=α2σ2‖μ1−μ2‖2.D_α(p\|q)= α2σ^2\,\| _1- _2\|^2. Proof. Recall the definition of the Rényi divergence, α(p∥q)=1α−1log∫p(x)αq(x)1−αx.D_α(p\|q)= 1α-1 \! p(x)^αq(x)^1-α\,dx. The densities of p and q are p(x)=1(2πσ2)d/2exp(−‖x−μ1‖22σ2)p(x)= 1(2πσ^2)^d/2 \! (- \|x- _1\|^22σ^2 ) and q(x)=1(2πσ2)d/2exp(−‖x−μ2‖22σ2)q(x)= 1(2πσ^2)^d/2 \! (- \|x- _2\|^22σ^2 ). Therefore, p(x)αq(x)1−α=(2πσ2)−d/2exp(−12σ2(α‖x−μ1‖2+(1−α)‖x−μ2‖2)).p(x)^αq(x)^1-α=(2πσ^2)^-d/2 \! (- 12σ^2 (α\|x- _1\|^2+(1-α)\|x- _2\|^2 ) ). We now complete the square in the exponent. Let m=αμ1+(1−α)μ2m=α _1+(1-α) _2. A direct expansion shows that α‖x−μ1‖2+(1−α)‖x−μ2‖2=‖x−m‖2+α(1−α)‖μ1−μ2‖2.α\|x- _1\|^2+(1-α)\|x- _2\|^2=\|x-m\|^2+α(1-α)\| _1- _2\|^2. Thus, p(x)αq(x)1−α=(2πσ2)−d/2exp(−‖x−m‖22σ2)exp(−α(1−α)‖μ1−μ2‖22σ2).p(x)^αq(x)^1-α=(2πσ^2)^-d/2 \! (- \|x-m\|^22σ^2 ) \! (- α(1-α)\| _1- _2\|^22σ^2 ). Integrating over ℝdR^d, the first exponential integrates to (2πσ2)d/2(2πσ^2)^d/2, since it is the normalization constant of a Gaussian distribution with mean m and covariance σ2Idσ^2I_d. Hence, ∫p(x)αq(x)1−αx=exp(−α(1−α)‖μ1−μ2‖22σ2). p(x)^αq(x)^1-α\,dx= \! (- α(1-α)\| _1- _2\|^22σ^2 ). Taking the logarithm and dividing by α−1α-1 yields α(p∥q)=1α−1(−α(1−α)‖μ1−μ2‖22σ2)=α2σ2‖μ1−μ2‖2.D_α(p\|q)= 1α-1 (- α(1-α)\| _1- _2\|^22σ^2 )= α2σ^2\| _1- _2\|^2. ∎ Denote the joint distribution of (X,Y)(X,Y) by PX,YP_X,Y. By independence, the distributions of X+εX+ and Y+εY+ can be written as PX+ε=∫x,y(x,σ2I)dPX,Y(x,y)andPY+ε=∫x,y(y,σ2I)dPX,Y(x,y),P_X+ = _x,yN(x,σ^2I)\,dP_X,Y(x,y) P_Y+ = _x,yN(y,σ^2I)\,dP_X,Y(x,y), respectively, where (x,σ2I)N(x,σ^2I) is the Gaussian distribution with mean x and covariance σ2Iσ^2I. Since 0<θ≤10<θ≤ 1, the function fθ(x)=xlog1θ(x+A)f_θ(x)=x 1θ(x+A) is convex for A>1A>1, so fθ(P∥Q)D_f_θ(P\|Q) is jointly convex. Using this observation, we can write fθ(PX+ε∥PY+ε)=fθ(∫x,y(x,σ2I)dPX,Y(x,y)∥∫x,y(y,σ2I)dPX,Y(x,y)) ~~~~D_f_θ (P_X+ \|P_Y+ )=D_f_θ ( _x,yN(x,σ^2I)\,dP_X,Y(x,y) \| _x,yN(y,σ^2I)\,dP_X,Y(x,y) ) ≤∫x,yfθ((x,σ2I)∥(y,σ2I))dPX,Y(x,y)=X,Y[fθ((X,σ2I)∥(Y,σ2I))] ≤ _x,yD_f_θ (N(x,σ^2I)\|N(y,σ^2I) )\,dP_X,Y(x,y)=E_X,Y [D_f_θ (N(X,σ^2I)\|N(Y,σ^2I) ) ] ≤X,Y[α((X,σ2I)∥(Y,σ2I))1θ]+Bα,θ=(α2σ2)1θ‖X−Y‖2θ+Bα,θ, _X,Y [D_α (N(X,σ^2I)\|N(Y,σ^2I) ) 1θ ]+B_α,θ= ( α2σ^2 ) 1θE\|X-Y\| 2θ+B_α,θ, where the second line uses Jensen’s inequality and the joint convexity of fθ(⋅∥⋅)D_f_θ(·\|·) (Page 120 of Polyanskiy and Wu (2025), Theorem 7.5(b)) in its arguments, and the last inequality follows from Lemma 3.2.1. E.5 Proof of Theorem F Proof. Write W1:T:=W1,…,WTW_1:T:=\W_1,…,W_T\ and let W^=F(W1:T) W=F(W_1:T) be any measurable output (e.g. W^=WT W=W_T or W^=T−1∑t=1TWt W=T^-1 _t=1^TW_t). Recall the shifted-log divergence fθ(x)=xlog1/θ(x+A)f_θ(x)=x ^1/θ(x+A) and the corresponding fθf_θ–mutual information: Ifθ(F(W1:T),S)=PSfθ(PF(W1:T)∣S∥PF(W1:T)).I_f_θ(F(W_1:T),S)=E_P_S\,D_f_θ\! (P_F(W_1:T) S\, \|\,P_F(W_1:T) ). By the data processing inequality for f–divergence (c.f. Polyanskiy and Wu, 2025, p. 120), Ifθ(F(W1:T),S)≤PSfθ(PW1:T∣S∥PW1:T).I_f_θ(F(W_1:T),S)\;≤\;E_P_S\,D_f_θ\! (P_W_1:T S\, \|\,P_W_1:T ). Using the chain rule for the Radon–Nikodym derivative, logdPW1:T∣SdPW1:T=∑t=1TlogdPWt∣W1:t−1,SdPWt∣W1:t−1. dP_W_1:T SdP_W_1:T= _t=1^T dP_W_t W_1:t-1,SdP_W_t W_1:t-1. If 1/θ≥11/θ≥ 1 and x↦x1/θx x^1/θ is convex, Jensen’s inequality yields (∑t=1Tat)1/θ≤T1/θ−1∑t=1Tat1/θ( _t=1^Ta_t)^1/θ\;≤\;T^1/θ-1 _t=1^Ta_t^1/θ for nonnegative att=1T\a_t\_t=1^T. If 0<1/θ≤10<1/θ≤ 1, the map x↦x1/θx x^1/θ is subadditive, so (∑t=1Taj)1/θ≤∑t=1Taj1/θ( _t=1^Ta_j)^1/θ≤ _t=1^Ta_j^1/θ. These two cases give (∑t=1Taj)1/θ≤T(1θ−1)+∑t=1Taj1/θ. ( _t=1^Ta_j )^1/θ≤ T^( 1θ-1)_+ _t=1^Ta_j^1/θ. (E.4) Applying this to at=logdPWt∣W1:t−1,SdPWt∣W1:t−1a_t= dP_W_t W_1:t-1,SdP_W_t W_1:t-1, we obtain Ifθ(S;W1:T)=PS[dPW1:T|SdPW1:T(∑t=1TlogdPWt|W1:t−1,SdPWt|W1:t−1+A)1θ] I_f_θ(S;W_1:T)=E_P_S [ dP_W_1:T|SdP_W_1:T ( _t=1^T dP_W_t|W_1:t-1,SdP_W_t|W_1:t-1+A ) 1θ ] ≤T(1θ−1)+∑t=1TPS[dPW1:T|SdPW1:T(logdPWt|W1:t−1,SdPWt|W1:t−1+A)1θ]=T(1θ−1)+∑t=1TS,W1:t−1fθ(PWt|W1:t−1,S∥PWt|W1:t−1). ≤ T^( 1θ-1)_+ _t=1^TE_P_S [ dP_W_1:T|SdP_W_1:T ( dP_W_t|W_1:t-1,SdP_W_t|W_1:t-1+A ) 1θ ]=T^( 1θ-1)_+ _t=1^TE_S,W_1:t-1D_f_θ(P_W_t|W_1:t-1,S\|P_W_t|W_1:t-1). (E.5) Next, we characterize conditional distributions of WtW_t under SGLD. The update rule is Wt+1=Wt−ηtg(Wt,Bt)+ϵt,ϵt∼(0,σt2Id).W_t+1=W_t- _tg(W_t,B_t)+ _t, _t (0, _t^2I_d). Conditioned on ℱt−1=σ(W1:t−1,S)F_t-1=σ(W_1:t-1,S), the distribution PWt|ℱt−1P_W_t|F_t-1 is Gaussian with mean μS=Wt−1−ηt−1g(Wt−1,Bt−1) _S=W_t-1- _t-1g(W_t-1,B_t-1) and covariance σt−12Id _t-1^2I_d. We may write Wt=Xt+ϵt−1withXt:=Wt−1−ηt−1g(Wt−1,Bt−1),W_t=X_t+ _t-1~with~X_t:=W_t-1- _t-1g(W_t-1,B_t-1), with XtX_t measurable with respect to σ(W1:t−1,S)σ(W_1:t-1,S) and ϵt−1 _t-1 independent of XtX_t. Conditioned only on W1:t−1W_1:t-1, the marginal distribution PWt|W1:t−1P_W_t|W_1:t-1 is a mixture of Gaussians induced by the randomness of the mini-batch Bt−1B_t-1. To bound the divergence, we construct a coupling. Let Bt−1′B _t-1 be an independent copy of the mini-batch index variable, independent of S. We approximate PWt∣W1:t−1P_W_t W_1:t-1 by the conditional distribution PWt∣W1:t−1,SP_W_t W_1:t-1,S with Yt:=Wt−1−ηt−1g(Wt−1,Bt−1′),so thatWt=Yt+ϵt−1.Y_t:=W_t-1- _t-1g(W_t-1,B _t-1), that W_t=Y_t+ _t-1. Applying Lemma F to the pair (Xt,Yt)(X_t,Y_t) (with ϵt−1 _t-1 as the perturbation, and (W1:(t−1),S)(W_1:(t-1),S) fixed) yields Dfθ(PWt∣W1:t−1,S∥PWt∣W1:t−1)≤(α2σt−12)1/θ[‖Xt−Yt‖2/θ|W1:t−1,S]+Bα,θ D_f_θ\! (P_W_t W_1:t-1,S\, \|\,P_W_t W_1:t-1 )≤ ( α2 _t-1^2 )^1/θE [\|X_t-Y_t\|^2/θ\, |\,W_1:t-1,S ]+B_α,θ =(αηt−122σt−12)1/θ[‖g(Wt−1,Bt−1)−g(Wt−1,Bt−1′)‖2/θ|W1:t−1,S]+Bα,θ. = ( α _t-1^22 _t-1^2 )^1/θE [\|g(W_t-1,B_t-1)-g(W_t-1,B _t-1)\|^2/θ\, |\,W_1:t-1,S ]+B_α,θ. For t=1t=1, W1W_1 is independent of S, so fθ(PW1|S∥PW1)=0D_f_θ(P_W_1|S\|P_W_1)=0. Then the sum starts at t=2t=2. Thus by (E.5), Ifθ(F(W1:T),S)≤T(1θ−1)+∑t=2TS,W1:t−1fθ(PWt|W1:t−1,S∥PWt|W1:t−1). ~~~~I_f_θ(F(W_1:T),S)≤ T^( 1θ-1)_+ _t=2^TE_S,W_1:t-1D_f_θ(P_W_t|W_1:t-1,S\|P_W_t|W_1:t-1). ≤T1θ−1[log(1+A)1θ+∑t=2T((αηt−122σt−12)1θ∥g(Wt−1,Bt−1)−g(Wt−1,Bt−1′)∥2θ+Bα,θ)]. ≤ T 1θ-1 [ (1+A) 1θ+ _t=2^T ( ( α _t-1^22 _t-1^2 ) 1θE\|g(W_t-1,B_t-1)-g(W_t-1,B _t-1)\| 2θ+B_α,θ ) ]. We now bound the stochastic gradient difference with g¯(w)=Zg(w,Z) g(w)=E_Zg(w,Z). By the triangle inequality, ‖g(Wt,Bt)−g(Wt,Bt′)‖≤‖g(Wt,Bt)−g¯(Wt)‖+‖g(Wt,Bt′)−g¯(Wt)‖.\|g(W_t,B_t)-g(W_t,B _t)\|≤\|g(W_t,B_t)- g(W_t)\|+\|g(W_t,B _t)- g(W_t)\|. Using CrC_r-inequality: (x+y)k≤2k−1(xk+yk)(x+y)^k≤ 2^k-1(x^k+y^k) for k=2θ≥1k= 2θ≥ 1, we obtain ‖g(Wt,Bt)−g(Wt,Bt′)‖2θ≤22θGtwithGt:=‖g(Wt,Bt)−g¯(Wt)‖2θ.E\|g(W_t,B_t)-g(W_t,B _t)\| 2θ≤ 2 2θG_t~with~G_t:=E\|g(W_t,B_t)- g(W_t)\| 2θ. Substituting this bound into the previous display and invoking Theorem 4.2.3 to convert Ifθ(F(W1:T),S)I_f_θ(F(W_1:T),S) into a bound on the expected generalization error, we conclude that |gen(W^,S)|≤Mθvθn4+21/θT(1θ−1)+[log1/θ(1+A)+∑t=1T−1(Bα,θ+(2αηt2σt2)1/θGt)],E\,|gen( W,S)|≤ M_θv_θ n \4+2^1/θ\,T^( 1θ-1)_+ [ ^1/θ(1+A)+ _t=1^T-1 (B_α,θ+ ( 2α _t^2 _t^2 )^1/θG_t ) ] \, which completes the proof. ∎ Appendix F Stochastic Optimization with Heavy-tailed Losses Beyond empirical risk minimization, most information-theoretic generalization bounds for stochastic optimization rely on light-tailed assumptions on the loss and its gradients; see, e.g., Hellström et al. (2025, Section 8) for a survey. In noisy iterative methods such as stochastic gradient algorithms, however, both losses and stochastic gradients may exhibit heavy tails (Raj et al., 2023; Madden et al., 2024; Fatkhullin et al., 2025; Sun et al., 2025). In this section, we apply our information-theoretic framework to stochastic gradient descent, with a particular focus on stochastic gradient Langevin dynamics (SGLD; Welling and Teh, 2011). Our starting point is the analysis-by-perturbation viewpoint of Neu et al. (2021), which controls generalization via information accumulated along the optimization trajectory. Under sub-Gaussian assumptions, this approach yields sub-Gaussian generalization bounds. We extend this analysis to sub-Weibull losses and heavy-tailed gradient noise, obtaining analogous bounds whose constants depend explicitly on the tail parameter θ and on pathwise gradient variability. A perturbation bound for fθf_θ-divergence. We begin with a perturbation lemma that extends Lemma 4 of Neu et al. (2021) to the Heavy-tailed setting. Lemma F.1 Let X,YX,Y be ℝdR^d-valued random variables with ‖X−Y‖2/θ<∞E\|X-Y\|^2/θ<∞ for θ>0θ>0. Let σ>0σ>0, suppose ε∼(0,σ2Id) (0,σ^2I_d) is independent of (X,Y)(X,Y). Then, for the shifted-log divergence fθ(x)=xlog1/θ(x+A)f_θ(x)=x ^1/θ(x+A), fθ(PX+ε∥PY+ε)≤(α2σ2)1/θ‖X−Y‖2/θ+Bα,θ,D_f_θ(P_X+ \|P_Y+ )\;≤\; ( α2σ^2 )^1/θ\,E\|X-Y\|^2/θ\;+\;B_α,θ, where A and Bα,θB_α,θ are as in Lemma 3.2.1. SGLD dynamics. Consider SGLD in ℝdR^d with (possibly randomized) mini-batches Bt⊂[n]B_t⊂[n], step sizes ηtt≥1\ _t\_t≥ 1, and Gaussian noises εt∼(0,σt2Id) _t (0, _t^2I_d), independent across t and independent of S and W1W_1: Wt+1=Wt−ηtg(Wt,Bt)+εt,g(w,Bt):=1|Bt|∑k∈Btg(w,Zk).W_t+1=W_t- _t\,g(W_t,B_t)+ _t, g(w,B_t):= 1|B_t| _k∈ B_tg(w,Z_k). (F.1) Let the algorithm output be any measurable function W^=F(W1:T) W=F(W_1:T) (e.g., the last iterate WTW_T or the Polyak average T−1∑t=1TWtT^-1 _t=1^TW_t), and assume W1W_1 is independent of S. Theorem F.2 (SGLD generalization under sub-Weibull losses) Fix 0<θ≤20<θ≤ 2 and let S=:Zii=1nS=:\Z_i\_i=1^n be i.i.d. with law Z∼μZ μ. Assume the loss ℓ:×→ℝ :W×Z satisfies vθ:=supw∈‖ℓ(w,Z)−ℓ(w,Z)‖ψθ<∞.v_θ:= _w \| (w,Z)-E (w,Z) \|_ _θ<∞. Assume the stochastic gradient estimator is conditionally unbiased, [g(Wt,Bt)∣Wt]=g¯(Wt)E[g(W_t,B_t) W_t]= g(W_t) with g¯(w)=Zg(w,Z) g(w)=E_Zg(w,Z), and that the centered mini-batch noise satisfies Gt:=‖g(Wt,Bt)−g¯(Wt)‖2/θ<∞,t=1,…,T−1.G_t:=E \|g(W_t,B_t)- g(W_t) \|^2/θ<∞, t=1,…,T-1. Let A satisfy the conditions of Lemma 3.2.1 with constant Bα,θ>0B_α,θ>0. Then, |gen(W^,S)|≤Mθvθn[4+21/θT(1θ−1)+(log1/θ(1+A)+∑t=1T−1(Bα,θ+(2αηt2σt2)1/θGt))],E |gen( W,S) |≤ M_θ\,v_θ n [4+2^1/θT^( 1θ-1)_+ ( ^1/θ(1+A)+ _t=1^T-1 (B_α,θ+ ( 2α _t^2 _t^2 )^1/θG_t ) ) ], where MθM_θ is given in (D.4) in Appendix. Theorem F decomposes the expected generalization gap into a distributional component and an algorithmic/path component. The distributional component is the sub-Weibull scale vθv_θ, which uniformly quantifies the tail-heaviness of the centered loss. The path component aggregates stability contributions along the SGLD trajectory through the step sizes ηt _t, injected noise levels σt _t, and the stochastic-gradient noise: ∑t=1T−1(ηt2σt2)1/θGt,Gt≔‖g(Wt,Bt)−g¯(Wt)‖2/θ. _t=1^T-1 ( _t^2 _t^2 )^1/θG_t, G_t \|g(W_t,B_t)- g(W_t) \|^2/θ. This term makes the roles of the two sources of randomness explicit. Heavy tails arise from the minibatch (stochastic-gradient) noise g(Wt,Bt)−g¯(Wt)g(W_t,B_t)- g(W_t), whose burstiness is captured by the moment GtG_t and the tail index θ: smaller θ corresponds to heavier tails and increases the influence of rare but large gradient fluctuations. By contrast, the injected Gaussian noise is algorithmic and plays the role of a smoothing mechanism: adding (0,σt2I)N(0, _t^2I) at each step blurs the iterate distribution, reducing the distinguishability between neighboring trajectories (e.g., under neighboring datasets) and thereby limiting how much data-dependence can accumulate along the path. The resulting tradeoff is governed by the noise-normalized drift budget above: larger σt _t suppresses each per-step contribution, while larger ηt _t amplifies it. Relative to the sub-Gaussian baseline θ=2θ=2, where the dependence is (ηt2/σt2)1/2( _t^2/ _t^2)^1/2, heavier tails (smaller θ) increase the exponent 1/θ1/θ and make the bound more sensitive to the effective ratio ηt2/σt2 _t^2/ _t^2; in particular, for θ<1θ<1 this dependence becomes super-linear. Thus, Gaussian injection need not make the stochastic gradients light-tailed; rather, it provides stabilizing smoothing whose strength must be calibrated against tail-heaviness through θ and GtG_t. This interpretation is consistent with the sub-Gaussian specialization. When θ=2θ=2, the sub-Weibull norm reduces to the usual sub-Gaussian scale and Gt=‖g(Wt,Bt)−g¯(Wt)‖G_t=E\|g(W_t,B_t)- g(W_t)\|. Specializing Theorem F to θ=2θ=2 yields, up to constants, |gen(W^,S)|≲v2n[1+1T∑t=1T−1(Bα,2+|ηt|σt‖g(Wt,Bt)−g¯(Wt)‖)],E |gen( W,S) |\; \; v_2 n [1+ 1 T _t=1^T-1 (B_α,2+ | _t| _t\,E \|g(W_t,B_t)- g(W_t) \| ) ], where ηt/σt _t/ _t is exactly the θ=2θ=2 instance of (ηt2/σt2)1/θ( _t^2/ _t^2)^1/θ. By contrast, Neu et al. (2021, Proposition 3) obtain (for θ=2θ=2) a KL-based path bound of as the form O(1n∑t=1T−1ηt2σt2‖g(Wt,Bt)−g¯(Wt)‖2).O\! ( 1n _t=1^T-1 _t^2 _t^2\,E \|g(W_t,B_t)- g(W_t) \|^2 ). Both bounds reflect the same stability mechanism: generalization improves with larger injected noise σt _t and degrades with larger step sizes ηt _t and more variable stochastic gradients. They differ in form for two main reasons. First, our result applies to an arbitrary post-processed output W^=F(W1:T) W=F(W_1:T), whereas Neu et al. (2021) focus on the final iterate. Second, our heavy-tail analysis controls stepwise fθf_θ-divergence increments and then upper bounds them using Rényi divergence; unlike KL, Rényi divergences do not admit the same additive chain rule along the optimization path, which naturally leads to an additive per-step accumulation before applying outer norm inequalities. In the sub-Gaussian regime, the two forms can be related by standard inequalities. Let Xt≔g(Wt,Bt)−g¯(Wt)X_t g(W_t,B_t)- g(W_t). Then Cauchy–Schwarz and Jensen yield 1T∑t=1T−1|ηt|σt‖Xt‖≤∑t=1T−1ηt2σt2(‖Xt‖)2≤∑t=1T−1ηt2σt2‖Xt‖2. 1 T _t=1^T-1 | _t| _t\,E\|X_t\|\;≤\; _t=1^T-1 _t^2 _t^2\,(E\|X_t\|)^2\;≤\; _t=1^T-1 _t^2 _t^2\,E\|X_t\|^2. Thus, when θ=2θ=2 our bound is comparable to the KL path bound up to constants, while our formulation continues to apply in genuinely heavy-tailed settings where MGF-based KL techniques can become ineffective or inapplicable. Simulation studies for linear regression are given in Appendix I.4. Appendix G Calculation Details for Examples and Simulations G.1 Example of quadratic mean estimation Let the hypothesis class be =[−1,1]W=[-1,1], and consider the squared loss ℓ(w,Y)=(w−Y)2, (w,Y)=(w-Y)^2, where Y is a symmetric Weibull with ℙ(|Y|≥t)=12e−tθP(|Y|≥ t)= 12e^-t^θ for θ∈(0,1)θ∈(0,1). In this example, f(w,x)=wf(w,x)=w and there is no X. Let S=Yii=1nS=\Y_i\_i=1^n and take the empirical risk minimizer W(S):=argminw∈[−1,1]LS(w)=clip(1n∑i=1nYi,[−1,1]),W(S):= _w∈[-1,1]L_S(w)\;=\;clip\! ( 1n _i=1^nY_i,\;[-1,1] ), which is a deterministic and continuous function of S. Consequently, PW∣SP_W S is a point mass and is singular with respect to the marginal PWP_W, so Iα(W;S)=∞I_α(W;S)=∞ for every α>1α>1. Therefore, Theorem 4.2.3 does not produce a meaningful bound. To apply the chaining bound (Theorem 4.2.5), fix the dyadic partitions k=[m2−(k−1),(m+1)2−(k−1))∩[−1,1]:m∈ℤ,k≥1,P_k= \\,[m2^-(k-1),(m+1)2^-(k-1))∩[-1,1]\;:\;m \, k≥ 1, which form an increasing partition sequence of T. Denote k=∪i∈ℤk,iP_k= _i P_k,i denote the i-th cell in k-partition. With the metric from the square-loss example (see Example I.4), we have M=1M=1 and L=1L=1 with e()=d(0,1)=C2(θ)Dθ(2+2‖Y‖ψθ),e(W)=d(0,1)=C_2(θ)D_θ (2+2\|Y\|_ _θ ), and the corresponding Dudley integral γ<∞γ<∞ can be verified directly. Let Wk=[W]kW_k=[W]_k denote the cell in kP_k that contains W. Below are the rigorous, step-by-step derivation for the three claims to obtain our desired result. Claim 1: Iα(Wk;S)=1α−1log∫p(s)(1ℙ(Wk∈k,i(s)))α−1s.I_α(W_k;S)= 1α-1 p(s) ( 1P(W_k _k,i(s)) )^α-1ds. Proof. By definition, Iα(Wk;S)=Dα(PWk,S∥PWk⊗PS)=1α−1log∫∑i(pWk,S(i,s))α(PWk(i)p(s))α−1dsI_α(W_k;S)=D_α(P_W_k,S\|P_W_k P_S)= 1α-1 _S _i (p_W_k,S(i,s) )^α (P_W_k(i)p(s) )^α-1\,ds where pWk,S(i,s)p_W_k,S(i,s) is the joint density-mass function, p(s)p(s) is the marginal density of S, and PWk(i)=ℙ(Wk∈k,i)P_W_k(i)=P(W_k _k,i) is the marginal probability mass of WkW_k. The joint distribution is pWk,S(i,s)=ℙ(Wk∈k,i∣S=s)p(s).p_W_k,S(i,s)=P(W_k _k,i S=s)p(s). Because W is a deterministic function of S, WkW_k (the cell containing W) is also a deterministic function of S. Let i(s)i(s) be the unique index of the cell containing W(s)W(s). Then, ℙ(Wk∈k,i∣S=s)=Ii=i(s)=1if i=i(s)0otherwiseP(W_k _k,i S=s)=I\i=i(s)\= cases1&if i=i(s)\\ 0&otherwise cases Substitute this back into the Rényi mutual information formula: Iα(Wk;S) I_α(W_k;S) =1α−1log∫∑i(Ii=i(s)p(s))α(PWk(i)p(s))α−1ds=1α−1log∫p(s)α(PWk(i(s))p(s))α−1s = 1α-1 _S _i (I\i=i(s)\p(s) )^α (P_W_k(i)p(s) )^α-1ds= 1α-1 _S p(s)^α (P_W_k(i(s))p(s) )^α-1ds ≤1α−1log∫p(s)(1ℙ(Wk∈k,i(s)))α−1s. ≤ 1α-1 _Sp(s) ( 1P(W_k _k,i(s)) )^α-1ds. Since Ii=i(s)α=Ii=i(s)I\i=i(s)\^α=I\i=i(s)\ for α>1α>1, all terms in the sum over i evaluate to 0 except the single term where i=i(s)i=i(s). ∎ Claim 2: ℙ(Wk∈k,i)≥Cn,θ 2−(k−1)P(W_k _k,i)\;≥\;C_n,θ\,2^-(k-1). Proof. Recall the deterministic mapping: W=clip(Y¯,[−1,1])W=clip( Y,[-1,1]), where Y¯=1n∑j=1nYj Y= 1n _j=1^nY_j. The event Wk∈k,i\W_k _k,i\ means that the clipped mean W falls into the i-th cell k,i⊂[−1,1]P_k,i⊂[-1,1]. Based on the definition k,i=[i2−(k−1),(i+1)2−(k−1))∩[−1,1]P_k,i=[i2^-(k-1),(i+1)2^-(k-1))∩[-1,1], for any internal cell strictly within (−1,1)(-1,1), we have |k,i|=2−(k−1)|P_k,i|=2^-(k-1). • For an internal cell k,i⊂(−1,1)P_k,i⊂(-1,1), W∈k,iW _k,i if and only if Y¯∈k,i Y _k,i (no clipping). • For a boundary cell containing −1-1 or 11, W∈k,iW _k,i if Y¯∈k,i Y _k,i or Y¯>1 Y>1. Therefore, for any cell k,iP_k,i, ℙ(Wk∈k,i)=ℙ(W∈k,i)≥ℙ(Y¯∈k,i)P(W_k _k,i)=P(W _k,i) ( Y _k,i). If fY¯f_ Y denotes the density of Y¯=n−1∑i=1nYi Y=n^-1 _i=1^nY_i and Cn,θ:=inf|y|≤1fY¯(y)>0C_n,θ:= _|y|≤ 1f_ Y(y)>0. Thus, evaluating the probability by integrating the density over the cell gives ℙ(Wk∈k,i)≥ℙ(Y¯∈k,i)=∫k,ipY¯(y)y≥∫k,iCn,θy=Cn,θ|k,i|=Cn,θ2−(k−1).P(W_k _k,i) ( Y _k,i)= _P_k,ip_ Y(y)\,dy≥ _P_k,iC_n,θ\,dy=C_n,θ|P_k,i|=C_n,θ2^-(k-1). ∎ From Claims 1 and 2, we established that: Iα(Wk;S) I_α(W_k;S) =1α−1log∫p(s)(1ℙ(Wk∈k,i(s)))α−1s≤1α−1log∫p(s)(1Cn,θ2−(k−1))α−1s = 1α-1 p(s) ( 1P(W_k _k,i(s)) )^α-1ds≤ 1α-1 p(s) ( 1C_n,θ2^-(k-1) )^α-1ds =1α−1log[(1Cn,θ2−(k−1))α−1∫p(s)s]=1α−1log[(1Cn,θ2−(k−1))α−1] = 1α-1 [ ( 1C_n,θ2^-(k-1) )^α-1 _Sp(s)\,ds ]= 1α-1 [ ( 1C_n,θ2^-(k-1) )^α-1 ] =(k−1)log2−logCn,θ. =(k-1) 2- C_n,θ. since ℙ(Wk∈k,i(s))≥Cn,θ2−(k−1)P(W_k _k,i(s))≥ C_n,θ2^-(k-1). Substituting the upper bound into Theorem 4.2.5 yields a finite multiscale complexity term, [gen(W,S)]≤MθC2(θ)Dθ(2+2‖Y‖ψθ)n∑k=1∞2−(k−1)(21/θ[(k−1)log2−logCn,θ]+4).E [gen(W,S) ]≤ M_θC_2(θ)D_θ (2+2\|Y\|_ _θ ) n _k=1^∞2^-(k-1) (2^1/θ[(k-1) 2- C_n,θ]+4 ). G.2 Four approaches to upper-bound [XW]E[X_W] We build on the example of Asadi et al. (2018) to illustrate that, in heavy-tailed regimes, chaining mutual information can yield substantially tighter bounds than single-scale information or classical chaining (Dudley’s entropy bound). Let S=Z1,Z2S=\Z_1,Z_2\ be i.i.d. Weibull random variables with ℙ(Zi≥t)=exp(−tθ),t≥0,θ>0.P(Z_i≥ t)= (-t^θ),~t≥ 0,\ θ>0. Given an index set T⊂ℝ2T ^2, define the canonical Weibull process indexed by T⊂w∈ℝ2:‖w‖2=1T⊂\w ^2:\|w\|_2=1\: Xw:=∑i=12wiZi,w∈Tand‖w‖2=1.X_w:= _i=1^2w_iZ_i, w∈ T~~and~~\|w\|_2=1. Reparameterizing w by its phase ϕ∈[0,2π)φ∈[0,2π), we have w(ϕ)=(cosϕ,sinϕ)w(φ)=( φ, φ), and thus Xϕ:=Xw(ϕ)=Z1cosϕ+Z2sinϕX_φ:=X_w(φ)=Z_1 φ+Z_2 φ. Let l(ϕ,S):=−Xϕ.l(φ,S):=-X_φ. Verifying that −Xϕ∈[0,2π)\-X_φ\_φ∈[0,2π) is a sub-Weibull process (Definition 2.2). For any ϕ1,ϕ2∈[0,2π) _1, _2∈[0,2π), Xϕ1−Xϕ2=(w(ϕ1)−w(ϕ2))⊤Z=(cosϕ1−cosϕ2)Z1+(sinϕ1−sinϕ2)Z2.X_ _1-X_ _2=(w( _1)-w( _2)) Z=( _1- _2)Z_1+( _1- _2)Z_2. By the weak triangle inequality for ψθ _θ-Orlicz norms (see (A.1) in Appendix), ‖Xϕ1−Xϕ2‖ψθ \|X_ _1-X_ _2\|_ _θ ≤Dθ(|cosϕ1−cosϕ2|‖Z1‖ψθ+|sinϕ1−sinϕ2|‖Z2‖ψθ). ≤ D_θ (| _1- _2|\,\|Z_1\|_ _θ+| _1- _2|\,\|Z_2\|_ _θ ). Since ‖Z1‖ψθ=‖Z2‖ψθ\|Z_1\|_ _θ=\|Z_2\|_ _θ (i.i.d. coordinates), we get ‖Xϕ1−Xϕ2‖ψθ \|X_ _1-X_ _2\|_ _θ ≤Dθ‖Z1‖ψθ(|cosϕ1−cosϕ2|+|sinϕ1−sinϕ2|) ≤ D_θ\|Z_1\|_ _θ (| _1- _2|+| _1- _2| ) ≤2Dθ‖Z1‖ψθ‖w(ϕ1)−w(ϕ2)‖2, ≤ 2\,D_θ\,\|Z_1\|_ _θ\, \|w( _1)-w( _2) \|_2, where we used |a|+|b|≤2‖(a,b)‖2|a|+|b|≤ 2\|(a,b)\|_2. Moreover, on the unit circle we have the chord-length bound ‖w(ϕ1)−w(ϕ2)‖2≤|ϕ1−ϕ2|(chord length≤arc length)\|w( _1)-w( _2)\|_2≤| _1- _2|~(chord length length). Therefore, ‖Xϕ1−Xϕ2‖ψθ≤2Dθ‖Z1‖ψθ|ϕ1−ϕ2|.\|X_ _1-X_ _2\|_ _θ≤ 2\,D_θ\,\|Z_1\|_ _θ\,| _1- _2|. Let d(ϕ1,ϕ2):=|ϕ1−ϕ2|d( _1, _2):=| _1- _2|, −Xϕ\-X_φ\ is a (θ,C)(θ,C)-sub-Weibull process with C:=2Dθ‖Z1‖ψθC:= 2D_θ\|Z_1\|_ _θ. In Subsection 6.1, we consider four approaches to upper-bound [XW]E[X_W]. We begin with the MI method. By Theorem 4.1.2, controlling [XW]E[X_W] requires bounding the α-information Iα(W;S)I_α(W;S). In the present example, the random perturbation ξ contains a singular (degenerate) component, which implies that Iα(W;S)=∞I_α(W;S)=∞. Consequently, the MI-based bound is vacuous: it yields [XW]≤∞E[X_W]≤∞. The second approach is the classical chaining method. A crude bound is [XW]≤[supϕ∈[0,2π)Xϕ].E[X_W] [ _φ∈[0,2π)X_φ ]. (G.1) For ε∈(0,2π] ∈(0,2π], the circle can be covered by at most ⌈2π/ε⌉ 2π/ arcs of length 2ε2 with radius ε , and each such arc has chordal diameter at most its arc length. Hence, N(T,d,ε)=⌈2π2ε⌉=⌈πε⌉,ε∈(0,π].N(T,d, )= 2π2 = π , ∈(0,π]. (G.2) For ε≥π ≥π, clearly logN(T,d,ε)=0 N(T,d, )=0. Then Theorem 2.2 and (G.2) yield [supϕ∈[0,2π)Xϕ] [ _φ∈[0,2π)X_φ ] ≤4CKθ∫0∞[logN(T,d,ε)]1/θε=4CKθ∫02π[log⌈πε⌉]1/θε. ≤ 4CK_θ _0^∞ [ N(T,d, ) ]^1/θd =4CK_θ _0^2π [ π ]^1/θd . (G.3) Let Iθ=∫0π[log⌈πε⌉]1/θεI_θ= _0^π [ π ]^1/θd . On each interval where ⌈πε⌉ π is constant, we can compute the integral exactly. For k≥2k≥ 2, ⌈πε⌉=k⟺ε∈[πk,πk−1). π =k ∈ [ πk, πk-1 ). Therefore, Iθ=∑k=2∞∫π/kπ/(k−1)(logk)1/θ,dε=∑k=2∞(logk)1/θ(πk−1−πk)=π∑k=2∞(logk)1/θk(k−1).I_θ= _k=2^∞ _π/k^π/(k-1)( k)^1/θ,d = _k=2^∞( k)^1/θ ( πk-1- πk )=π _k=2^∞ ( k)^1/θk(k-1). The sum converges for every θ>0θ>0, since (logk)1/θ/(k(k−1))≍(logk)1/θ/k2( k)^1/θ/(k(k-1)) ( k)^1/θ/k^2. Hence, [XW]≤[supϕXϕ]≤4πCKθ∑k=2∞(logk)1/θk(k−1).E[X_W] [ _φX_φ ]≤ 4π CK_θ _k=2^∞ ( k)^1/θk(k-1). (G.4) This is a purely geometric bound via covering numbers, and it does not exploit any algorithmic dependence between W and S. The third approach is the Rényi chained mutual-information bound. Since continuous mutual information can be ill-behaved, we quantize W and apply a chaining argument. In the present example, e(T)=πe(T)=π. For each integer k≥1k≥ 1, let k:=[0,2π2k−1),[2π2k−1,2×2π2k−1),…,[(2k−1−1)2π2k−1,2π)=∪m=02k−1−1k,mP_k:= \ [0, 2π2^k-1 ), [ 2π2^k-1,2× 2π2^k-1 ),…, [ (2^k-1-1 ) 2π2^k-1,2π ) \= _m=0^2^k-1-1P_k,m be the equal-length partition of =[0,2π)W=[0,2π) into 2k−12^k-1 cells. Here: k,m:=[2π2k−1m,2π2k−1(m+1))P_k,m:= [ 2π2^k-1m, 2π2^k-1(m+1) ). For any w∈[0,2π)w∈[0,2π) and any level k, one can find the cell index m using the floor function: mk=⌊w2π⋅2k−1⌋m_k= w2π· 2^k-1 . The set [w]k[w]_k is given by [w]k=[mk2π2k−1,(mk+1)2π2k−1)[w]_k= [m_k 2π2^k-1,(m_k+1) 2π2^k-1 ). Then, [W]k=[⌊W2π⋅2k−1⌋2π2k−1,(⌊W2π⋅2k−1⌋+1)2π2k−1)[W]_k= [ W2π· 2^k-1 2π2^k-1, ( W2π· 2^k-1 +1 ) 2π2^k-1 ) is a discrete random variable taking values in the partition set kP_k. Given S, the minimizer ϕ⋆(S)φ (S) is deterministic. With probability ε , we have ξ=0ξ=0 and thus W=ϕ⋆(S)W=φ (S), so [W]k[W]_k falls into the “optimal” cell. With probability 1−ε1- , ξ is uniform on (−π,π)(-π,π). Let k,m⋆=[ϕ⋆(S)]kP_k,m =[φ (S)]_k be the cell containing the minimizer. The random variable [W]k∈k[W]_k _k has the following conditional probability mass function: 1. For the “optimal” cell containing ϕ⋆(S)φ (S): ℙ([W]k=k,m⋆|S)=ε+1−ε2k−1.P ([W]_k=P_k,m \; |\;S )= + 1- 2^k-1. 2. For any of the other 2k−1−12^k-1-1 cells (m≠m⋆m≠ m ): ℙ([W]k=k,m|S)=1−ε2k−1.P ([W]_k=P_k,m\; |\;S )= 1- 2^k-1. Using standard trigonometry, the objective can be written as Xϕ=Z1cosϕ+Z2sinϕ=‖Z‖2cos(ϕ−θZ).X_φ=Z_1 φ+Z_2 φ=\|Z\|_2 (φ- _Z). where Z=(Z1,Z2)Z=(Z_1,Z_2) and θZ _Z is the angle of the vector Z in polar coordinates. To minimize XϕX_φ, the cosine term must equal −1-1. This happens when the angle ϕφ points in the exact opposite direction of θZ _Z. Therefore, the deterministic minimizer is: ϕ⋆(S)=θZ⊕π(mod2π).φ (S)= _Z π 2π. Note that Z1,Z2Z_1,Z_2 are i.i.d. standard strictly positive Weibull variables, and θZ∈[0,π/2] _Z∈[0,π/2]. The probability density function for θZ _Z is fθZ(α)=θ(cosαsinα)θ−1(cosθα+sinθα)2,for α∈[0,π2].f_ _Z(α)= θ( α α)^θ-1( ^θα+ ^θα)^2, α∈ [0, π2 ]. See the corresponding Lemma H for the proof. Using the order-22 Rényi mutual information I2I_2 (chosen for algebraic simplicity), we obtain the following. I2([W]k;S)=logS[∑C∈kℙ([W]k=C∣S)2ℙ([W]k=C)]=log(∑m=02k−1−1u2+qm(ε2+2εu)εqm+u),u=1−ε2k−1.I_2([W]_k;S)= _S [ _C _k P([W]_k=C S)^2P([W]_k=C) ]= ( _m=0^2^k-1-1 u^2+q_m ( ^2+2 u ) q_m+u ),~u= 1- 2^k-1. where qm=ℙ(θZ∈([2π2k−1m−π,2π2k−1(m+1)−π)∩[0,π/2]))q_m=P ( _Z∈([ 2π2^k-1m-π, 2π2^k-1(m+1)-π)∩[0,π/2]) ) (the true probability that the minimizer lies in cell m). In particular, for every fixed k, we have I2([W]k;S)→0I_2([W]_k;S)→ 0 as ε→0 → 0. Applying Theorem 4.1.3 with e(T)=πe(T)=π yields the following. [XW]≤Cπ∑k=1∞2−(k−2)(21/θ(I2([W]k;S)+Cα,θ)1θ+2).E[X_W]≤ C\,π _k=1^∞2^-(k-2) (2^1/θ (I_2([W]_k;S)+C_α,θ ) 1θ+2 ). with C:=2Dθ‖Z1‖ψθ=21θ+12‖Z1‖ψθC:= 2D_θ\|Z_1\|_ _θ=2 1θ+ 12\|Z_1\|_ _θ for θ∈(0,1)θ∈(0,1). The fourth approach is a direct calculation of [XW]E[X_W]. Given S, minϕ∈[0,2π)l(ϕ,S)=−‖Z‖2. _φ∈[0,2π)l(φ,S)=-\|Z\|_2. Moreover, conditional on S, the algorithm output W is a mixture distribution: • With probability ε : ξ=0⟹W=ϕ⋆(S) ξ=0 W=φ (S) and XW=−‖Z‖2X_W=-\|Z\|_2; • With probability 1−ε1- : ξ∼Unif(−π,π)⟹W∼Unif(0,2π) ξ (-π,π) W (0,2π). Hence, [XW∣S,ξ≠0]=12π∫02π(Z1cosϕ+Z2sinϕ)ϕ=0.E[X_W S,ξ≠ 0]= 12π _0^2π (Z_1 φ+Z_2 φ )dφ=0. Then, by the law of total expectations, [XW∣S]=ε(−‖Z‖2)+(1−ε)⋅0=−ε‖Z‖2,⇒[XW]=−ε‖Z‖2.E[X_W S]= (-\|Z\|_2)+(1- )· 0=- \|Z\|_2, [X_W]=- \|Z\|_2. Each ZiZ_i has density f(z)=θzθ−1e−zθf(z)=θ z^θ-1e^-z^θ on [0,∞)[0,∞). Thus ‖Z‖2=∫0∞∫0∞x2+y2θ2xθ−1yθ−1e−xθ−yθxy.E\|Z\|_2= _0^∞\!\! _0^∞ x^2+y^2\,θ^2x^θ-1y^θ-1e^-x^θ-y^θ\,dx\,dy. Using polar coordinates on the first quadrant x=rcostx=r t, y=rsinty=r t, t∈[0,π/2]t∈[0,π/2], r∈[0,∞)r∈[0,∞), and dxdy=rdrdtdx\,dy=r\,dr\,dt, one obtains ‖Z‖2=θΓ(2+1θ)∫0π/2(costsint)θ−1(cosθt+sinθt)2+1/θt.E\|Z\|_2=θ\, \! (2+ 1θ ) _0^π/2 ( t\, t)^θ-1( ^θt+ ^θt)^2+1/θ\,dt. Equivalently, after the substitutions x=tanθtx= ^θt and then x=t/(1−t)x=t/(1-t), [XW]=−ε‖Z‖2=−εΓ(2+1θ)∫01(t2/θ+(1−t)2/θ)1/2t.E[X_W]=- \|Z\|_2=- \! (2+ 1θ ) _0^1 (t^2/θ+(1-t)^2/θ )^1/2\,dt. If θ=0.5θ=0.5, then [XW]=−εΓ(4)∫01(t4+(1−t)4)1/2t=−6ε∫01t4+(1−t)4t≈−3.6ε.E[X_W]=- \, (4) _0^1 (t^4+(1-t)^4 )^1/2\,dt=-6 _0^1 t^4+(1-t)^4\,dt≈-3.6 . Since ∫01t4+(1−t)4t≈0.60 _0^1 t^4+(1-t)^4\,dt≈ 0.60. Appendix H Proofs of Useful Lemmas and Formulas This section presents several lemmas used in the proofs of the main results. We begin by showing that the shifted-log function is convex. Lemma H.1 For θ>0θ>0, the function x↦xlogθ(x+A),A≥1x x ^θ(x+A),~A≥ 1 is convex over x>0x>0. Proof. Let L=log(x+A)L= (x+A), and define f(x):=xLθf(x):=x\,L^θ. The first derivative is f′(x)=Lθ+xθLθ−11x+A=Lθ−1(L+θx+A)=Lθ−1(L+θ[1−Ax+A]), f (x)=L^θ+xθ L^θ-1 1x+A=L^θ-1 (L+ θ xx+A )=L^θ-1 (L+θ [1- Ax+A ] ), while the second derivative is f′(x) f (x) =(θ−1)Lθ−21x+A(L+θx+A)+Lθ−1(1x+A+θA(x+A)2) =(θ-1)L^θ-2 1x+A (L+ θ xx+A )+L^θ-1 ( 1x+A+ θ A(x+A)^2 ) =θ(log(x+A))θ−2(x+A)2[(x+2A)log(x+A)+(θ−1)x]. =θ ( (x+A))^θ-2(x+A)^2 [(x+2A) (x+A)+(θ-1)x ]. Since θ>0θ>0, (x+A)2>0(x+A)^2>0, and for x>0,A≥1x>0,A≥ 1, we have log(x+A)≥0 (x+A)≥ 0, so log(x+A)θ−2>0 (x+A)^θ-2>0 whenever it is defined. It remains to prove that the bracketed term is positive. Define B(x)=(x+2A)log(x+A)+(θ−1)x.B(x)=(x+2A) (x+A)+(θ-1)x. The worst case occurs as θ→0+θ→ 0^+, so it suffices to show (x+2A)log(x+A)−x>0for allx>0.(x+2A) (x+A)-x>0 all~x>0. Define h(x)=(x+2A)log(x+A)−xh(x)=(x+2A) (x+A)-x. Then h(0)=2AlogA≥0h(0)=2A A≥ 0 (since A≥1A≥ 1), and h′(x)=log(x+A)+x+2Ax+A−1=log(x+A)+Ax+A>0forx>0.h (x)= (x+A)+ x+2Ax+A-1= (x+A)+ Ax+A>0 ~x>0. Thus, h(x)h(x) is strictly increasing and positive for all x>0x>0. Hence, B(x)>0B(x)>0 for all x>0x>0, A≥1A≥ 1, and θ>0θ>0. Therefore, f′(x)>0f (x)>0 on (0,∞)(0,∞), proving convexity. ∎ Lemma H.2 Let θ≥1θ≥ 1 and c>0c>0. The function x↦logθ(x+c)x ^θ(x+c) is concave on [0,∞)[0,∞) whenever c≥exp(θ−1)c≥ (θ-1). Proof. Define f(x):=logθ(x+c)f(x):= ^θ(x+c) for x≥0x≥ 0. Then f′(x)=θ(log(x+c))θ−11x+c.f (x)=θ ( (x+c) )^θ-1 1x+c. Differentiating it again yields f′(x) f (x) =θ[(θ−1)(log(x+c))θ−21(x+c)2−(log(x+c))θ−11(x+c)2] =θ [(θ-1) ( (x+c) )^θ-2 1(x+c)^2- ( (x+c) )^θ-1 1(x+c)^2 ] =θ(x+c)2(log(x+c))θ−2[(θ−1)−log(x+c)]. = θ(x+c)^2 ( (x+c) )^θ-2 [(θ-1)- (x+c) ]. Since θ≥1θ≥ 1 and x+c>0x+c>0, the prefactor θ(x+c)2(log(x+c))θ−2 θ(x+c)^2 ( (x+c) )^θ-2 is nonnegative whenever log(x+c)≥0 (x+c)≥ 0, and thus f′(x)≤0f (x)≤ 0 holds provided log(x+c)≥θ−1for all x≥0. (x+c)\;≥\;θ-1 all x≥ 0. The left-hand side is minimized at x=0x=0, so it suffices that logc≥θ−1 c≥θ-1, i.e., c≥eθ−1c≥ e^θ-1. ∎ To construct generalization bounds for heavy-tailed sub-Weibull, the following lemmas are needed, similar to the decorrelation lemma of Chu and Raginsky (2023). Lemma H.3 (A new Young-type inequality of non-convex function) For x,y≥0x,y≥ 0, we have xy≤21θx[log(x+A)]1θ+exp(yθ),xy≤ 2 1θx[ (x+A)] 1θ+ (y^θ), where A≥(2⌈2θ⌉−2⌈2θ⌉!)2∨1A≥(2 2θ -2 2θ !)^2 1 is a positive constant depending on θ>0θ>0. Proof. We discuss two cases below. Case 1. If y≤21θlog(x+A)1θy≤ 2 1θ (x+A) 1θ, the inequality is immediate for A≥1A≥ 1 since exp(yθ)>0 (y^θ)>0. Case 2. If y>21θlog(x+A)1θy>2 1θ (x+A) 1θ, we have xy<(exp(yθ2)−A)y≤(exp(yθ2)−A)(exp(yθ2)+A)≤exp(yθ).xy< ( ( y^θ2)-A )y≤ ( ( y^θ2)- A ) ( ( y^θ2)+ A )≤ (y^θ). The first inequality is because in this case x<exp(yθ2)−Ax< ( y^θ2)-A and we can properly choose A satisfying y≤exp(yθ2)+Ay≤ ( y^θ2)+ A to make the second inequality hold. Let m=⌈2/θ⌉m= 2/θ . What does hold for all y≥0y≥ 0 and θ>0θ>0 is exp(yθ2)≥y22mm!. ( y^θ2 )\ ≥\ y^22^mm!. The claim is trivial for y=0y=0, so assume y>0y>0 and set x:=yθ/2≥0x:=y^θ/2≥ 0. By the Taylor expansion of exe^x with nonnegative terms, for any integer m≥0m≥ 0, ex=∑k=0∞xkk!≥xmm!.e^x= _k=0^∞ x^kk!\ ≥\ x^mm!. Hence exp(yθ2)=ex≥1m!(yθ2)m=yθm2mm!. \! ( y^θ2 )=e^x\ ≥\ 1m! ( y^θ2 )^m\ =\ y^θ m2^m\,m!. We now compare yθmy^θ m and y2y^2. Case 1: 0≤y≤10≤ y≤ 1. We have exp(yθ/2)≥1 (y^θ/2)≥ 1. Also y2≤1y^2≤ 1, so y22mm!≤12mm!≤1≤exp(yθ2). y^22^mm!≤ 12^mm!≤ 1≤ \! ( y^θ2 ). Case 2: y≥1y≥ 1. Since m=⌈2θ⌉m= 2θ , we have θm≥2θ m≥ 2. Therefore yθm≥y2y^θ m≥ y^2 for all y≥1y≥ 1, thus exp(yθ2)≥yθm2mm!≥y22mm!. \! ( y^θ2 )\ ≥\ y^θ m2^mm!\ ≥\ y^22^mm!. So we have y−exp(yθ2)≤y−y22mm!≤2m−2m!,y≥0.y- ( y^θ2 )≤ y- y^22^mm!≤ 2^m-2m!,~y≥ 0. A≥2m−2m!∨1=(2⌈2θ⌉−2⌈2θ⌉!)∨1A≥ 2^m-2m! 1=(2 2θ -2 2θ !) 1 is enough. ∎ To derive generalization bounds, we need to handle sums of random variables. However, the moment inequality (Lemma D.4) does not hold for small moment order p, so the truncated version of the above lemma is useful. Lemma H.4 Let h(y)=exp(yθ)−∑k=0mykθk!h(y)= (y^θ)- _k=0^m y^kθk!. For x≥0x≥ 0 and y≥0y≥ 0, we have xy≤21θ⋅xlog(x+A)1θ+2h(y),xy≤ 2 1θ· x (x+A) 1θ+2h(y), where m=⌊2θ⌋m= 2θ and A≥max(1,2m∗−2(m∗)!, 2em)A≥ (1,2^m^*-2(m^*)!,\,2e^m ) with m∗=⌈2/θ⌉m^*= 2/θ . Proof. We prove by discussing two cases. Case 1. If y≤21θlog(x+A)1θy≤ 2 1θ (x+A) 1θ, the inequality is immediate since h(y)≥0h(y)≥ 0. Case 2. If y>21θlog(x+A)1θy>2 1θ (x+A) 1θ, we have xy<(exp(yθ2)−A)y≤(exp(yθ2)−A)(exp(yθ2)+A)=exp(yθ)−A≤2h(y).xy< ( ( y^θ2)-A )y≤ ( ( y^θ2)- A ) ( ( y^θ2)+ A )= (y^θ)-A≤ 2h(y). (H.1) The first inequality is because in this case x<exp(yθ2)−Ax< ( y^θ2)-A and we can properly choose A satisfying y≤exp(yθ2)+Ay≤ ( y^θ2)+ A to make the second inequality hold in Lemma H. The last inequality hold if we take A≥supy≥02∑k=0⌊2θ⌋yθk!−exp(yθ).A≥ _y≥ 0 \2 _k=0 2θ y^θ kk!- (y^θ) \. Let t:=yθ≥0t:=y^θ≥ 0 and define for m∈ℕm , Fm(t):=2∑k=0mtkk!−etF_m(t):=2 _k=0^m t^kk!-e^t. If X∼Poisson(t)X (t), then e−t∑k=0mtk/k!=P(X≤m)e^-t _k=0^mt^k/k!=P(X≤ m); hence Fm(t)=et(2P(X≤m)−1).F_m(t)=e^t (2P(X≤ m)-1 ). A bound for the median Med(t)Med(t) of a Poisson(t)Poisson(t) variable states that (see, e.g., Choi (1994)) Med(t)≥t−log2.Med(t)\;≥\;t- 2. Therefore, if t≥m+log2t≥ m+ 2 then Med(t)≥t−ln2≥mMed(t)≥ t- 2≥ m and P(X≤m)≤12P(X≤ m)≤ 12. It follows that t≥m+ln2⟹Fm(t)≤0.t≥ m+ 2\; \;F_m(t)≤ 0. For t∈[0,m+log2]t∈[0,m+ 2], Fm(t)≤et≤em+log2=2em,F_m(t)\;≤\;e^t\;≤\;e^\,m+ 2=2e^m, hence, supy≥02∑k=0⌊2θ⌋yθk!−exp(yθ)≤2em. _y≥ 0 \2 _k=0 2θ y^θ kk!- (y^θ) \≤ 2e^m. So, letting m=⌊2θ⌋m= 2θ , inequality (H.1) holds when A≥2exp(⌊2θ⌋)A≥ 2 ( 2θ ). ∎ Lemma H.5 Let S=Z1,Z2S=\Z_1,Z_2\ be i.i.d. Weibull random variables with ℙ(Zi>t)=exp(−tθ),t≥0,θ>0P(Z_i>t)= (-t^θ),~t≥ 0,\ θ>0. Put Z=(Z1,Z2)∈ℝ+×ℝ+Z=(Z_1,Z_2) ^+×R^+ with its length ‖Z‖2\|Z\|_2. Let θZ _Z be the angle of the vector Z in polar coordinates. Then, the density function for θZ _Z is fθZ(α)=θ(cosαsinα)θ−1(cosθα+sinθα)2,for α∈[0,π2].f_ _Z(α)= θ( α α)^θ-1( ^θα+ ^θα)^2, α∈ [0, π2 ]. Proof. We are given S=Z1,Z2S=\Z_1,Z_2\ i.i.d. Weibull random variables with survival function ℙ(Zi≥t)=e−tθ,t≥0,θ>0.P(Z_i≥ t)=e^-t^θ,~t≥ 0,\ θ>0. with probability density function fZi(z)=θzθ−1e−zθ,z≥0f_Z_i(z)=θ z^θ-1e^-z^θ, z≥ 0. The joint density of (Z1,Z2)(Z_1,Z_2) is fZ1,Z2(z1,z2)=θ2(z1z2)θ−1e−(z1θ+z2θ),z1,z2≥0.f_Z_1,Z_2(z_1,z_2)=θ^2(z_1z_2)^θ-1e^-(z_1^θ+z_2^θ), z_1,z_2≥ 0. Let R=‖Z‖2=Z12+Z22R=\|Z\|_2= Z_1^2+Z_2^2 and Θ=θZ = _Z be the polar angle, i.e. Z1=RcosΘ,Z2=RsinΘ,R>0,Θ∈[0,π2].Z_1=R , Z_2=R , R>0,\; ∈[0, π2]. The Jacobian of the transformation (z1,z2)↦(r,φ)(z_1,z_2) (r, ) is r, so the joint density (R,Θ)(R, ) fR,Θ(r,φ)=fZ1,Z2(rcosφ,rsinφ)r=θ2(r2cosφsinφ)θ−1e−rθ(cosθφ+sinθφ)r.f_R, (r, )=f_Z_1,Z_2(r ,r )r=θ^2(r^2 )^θ-1e^-r^θ( ^θ + ^θ )r. Simplifying, fR,Θ(r,φ)=θ2r2θ−1(cosφsinφ)θ−1e−rθ(cosθφ+sinθφ),r>0,φ∈[0,π2].f_R, (r, )=θ^2r^2θ-1( )^θ-1e^-r^θ( ^θ + ^θ ), r>0,\; ∈[0, π2]. Then, the marginal density of Θ is obtained by integrating out r: fΘ(φ)=∫0∞θ2r2θ−1(cosφsinφ)θ−1e−rθ(cosθφ+sinθφ)r.f_ ( )= _0^∞θ^2r^2θ-1( )^θ-1e^-r^θ( ^θ + ^θ )\,dr. Make the substitution u=rθ(cosθφ+sinθφ),r=(ucosθφ+sinθφ)1/θ,dr=1θu1/θ−1(cosθφ+sinθφ)−1/θdu.u=r^θ ( ^θ + ^θ ), r= ( u ^θ + ^θ )^1/θ, dr= 1θ\,u^1/θ-1 ( ^θ + ^θ )^-1/θ\,du. Then r2θ−1=(ucosθφ+sinθφ)(2θ−1)/θ=u(2θ−1)/θ(cosθφ+sinθφ)−(2θ−1)/θ.r^2θ-1= ( u ^θ + ^θ )^(2θ-1)/θ=u^(2θ-1)/θ ( ^θ + ^θ )^-(2θ-1)/θ. Multiplying drdr and r2θ−1r^2θ-1 gives drr2θ−1=1θu(1/θ−1)+(2θ−1)/θ(cosθφ+sinθφ)−1/θ−(2θ−1)/θdu=1θu(cosθφ+sinθφ)−2du.dr\;r^2θ-1= 1θ\,u^(1/θ-1)+(2θ-1)/θ\, ( ^θ + ^θ )^-1/θ-(2θ-1)/θ\,du= 1θ\,u\, ( ^θ + ^θ )^-2\,du. Substituting into the integral, for φ∈[0,π2] ∈[0, π2]. fΘ(φ) f_ ( ) =θ2(cosφsinφ)θ−1∫0∞1θue−u(cosθφ+sinθφ)−2u =θ^2( )^θ-1 _0^∞ 1θ\,u\,e^-u\, ( ^θ + ^θ )^-2\,du =θ(cosφsinφ)θ−1(cosθφ+sinθφ)−2∫0∞ue−uu=θ(cosφsinφ)θ−1(cosθφ+sinθφ)2. =θ( )^θ-1 ( ^θ + ^θ )^-2 _0^∞ue^-udu= θ( )^θ-1( ^θ + ^θ )^2. ∎ Appendix I Additional Numerical Experiments This section provides empirical evidence for the main experimental claims. We first verify that the order-preserving power transformation used in Section 6.2 indeed produces a heavier-tailed reward. We then study a distinct heavy-tailed reward construction based on injecting centered Weibull noise and show that the qualitative behavior observed under Rényi regularization persists. Finally, we report an SGLD experiment for heavy-tailed linear regressions, illustrating how the generalization gap depends on both sample size and tail heaviness. I.1 RLHF experimental details We study the effect of Rényi order α in (6.1) while fixing β=1β=1 throughout. We sweep α∈1,2,…,10α∈\1,2,…,10\, where α→1α→ 1 corresponds to the KL regularization. We train in the h-rlhf training split (50,000 prompts) for up to 15001500 optimization steps and evaluate every 1010 steps on 128 prompts that are not used for training. For text generation, we cap the prompt length at 256 tokens and the completion length at 128 tokens. We sample with temperature 1.0 and top-p 0.95, that is, at each decoding step we sample from the smallest set of tokens whose cumulative probability under the model is at least 0.95 (nucleus sampling). During training, we sample 4 completions for each prompt so that GRPO can compare multiple responses to the same prompt and form a group-relative reward signal for the policy update. We use a per-device batch size of 1 and accumulate gradients over 8 steps, which gives an effective batch size of 8, together with a learning rate of 10−510^-5 and BF16 precision.222“BF16” precision refers to the 16-bit bfloat16 floating-point format, which reduces memory usage and can improve training/inference throughput while typically maintaining numerical stability comparable to 32-bit floats. During evaluation, we generate with batch size 16 and estimate Rényi divergence on a 16-prompt subset to reduce computation. For reward scoring, both reward models use a maximum input length of 512 tokens, with longer inputs truncated. We also recalibrate the proxy reward using mean- and scale statistics estimated from 256 prompts sampled from the reference policy so that reward values are on a comparable scale across runs. I.2 Tail behavior under the order-preserving power transformation As discussed in Section 6.2, the RLHF experiments in the main text are deliberately conducted in a heavy-tailed reward regime induced by an order-preserving power transform. In Figure 1, we complement that visual evidence with a quantitative diagnostic based on the empirical MGF. For the original and transformed reward samples ri\r_i\, we compute M(t)=1n∑i=1netri,t∈ℝ.M(t)= 1n _i=1^ne^tr_i,~t . Its growth for moderate values of |t||t| provides a useful finite-sample summary of tail amplification. M(t)M(t) changes much more rapidly and explore as t moves away from zero. Figure 6 shows that the transformed rewards exhibit orders-of-magnitude larger empirical MGFs than the original rewards. For β=1β=1 and α=1α=1, at t=−0.4t=-0.4, the empirical MGF of the transformed reward is approximately 5.77×1065.77× 10^6, about 3.2×1063.2× 10^6 times larger than that of the original reward (1.801.80). For α=2α=2, the contrast is even stronger: at t=−0.4t=-0.4, the ratio between the transformed and original MGFs is approximately 8.34×10138.34× 10^13. The logarithmic growth rate dlogM(t)/dtd M(t)/dt shows the same pattern. At t=−0.4t=-0.4, this quantity is approximately −47.5-47.5 for α=1α=1 and −91.3-91.3 for α=2α=2 after transformation, compared with only −1.47-1.47 and −1.57-1.57 for the corresponding original rewards. Taken together, these diagnostics reinforce the main-text claim in Section 6.2: the order-preserving power transformation substantially amplifies tail behavior and thereby produces the heavy-tailed reward regime used to study the robustness of Rényi-regularized RLHF. Figure 6: Empirical MGFs comparison for the original and transformed reward. Left: β=1β=1 with α=1α=1 (KL). Right: β=1β=1 with α=2α=2 (Rényi). Blue curves correspond to the original reward r(x,y)r(x,y), and red curves correspond to the transformed reward r~(x,y)=sign(r(x,y))|r(x,y)|8 r(x,y)=sign(r(x,y))\,|r(x,y)|^8. The much faster growth of the empirical MGF for the transformed rewards is consistent with stronger tail amplification. I.3 Alternative heavy-tailed reward construction by injecting Weibull noise In addition to the power transform used in Section 6.2, we consider a second heavy-tailed reward construction obtained by adding centered Weibull noise to the reward. Let r0(x,y)=⟨θ∗,ψ(x,y)⟩r_0(x,y)= θ^*,ψ(x,y) denote the clean reward, where ψ(x,y)ψ(x,y) is the penultimate-layer representation of the same proxy reward model used in Section 6.2, namely Qwen2.5-0.5B, and θ∗θ^* is the parameter vector of its trained final linear layer. We define the observed reward by r(x,y)=r0(x,y)+ε(x,y),ε(x,y)=Z−[Z],Z∼Weibull(k,η(x,y)).r(x,y)=r_0(x,y)+ (x,y), (x,y)=Z-E[Z], Z (k,η(x,y)). Since [Z]=η(x,y)Γ(1+1/k)E[Z]=η(x,y) (1+1/k), the perturbation is centered and therefore preserves the conditional mean reward. We set k∈0.2,0.3,0.4,0.5,k∈\0.2,0.3,0.4,0.5\, with smaller k corresponding to heavier-tailed noise, and take η(x,y)η(x,y) to be the estimated standard error of the reward. We use the same penalized objective (6.1), fix β=1β=1, and vary the Rényi order over α∈2,4,6,8,10.α∈\2,4,6,8,10\. All other implementation details are the same as those in Section 6.2. Figure 7: Reward–divergence relationship under the centered Weibull-noise reward with shape parameters 0.2, 0.3, 0.4, and 0.5, ordered from left to right and top to bottom. Across all tested Weibull shape parameters, the reward–divergence curves remain stable: the gold reward typically increases and then levels off, rather than exhibiting a sharp collapse, indicating that higher-order Rényi regularization continues to provide a reliable trust-region with β=1β=1. Figure 8: Proxy–proxy-gold reward relationship under the centered Weibull-noise reward construction with β=1β=1 and Weibull shape parameters 0.2, 0.3, 0.4, and 0.5, ordered from left to right and top to bottom. Across all tested noise levels, the proxy–proxy-gold curves remain monotone increasing over the observed range, showing that improvements in the proxy reward continue to translate consistently into improvements in the gold reward even under heavier-tailed Weibull. Figures 7 and 8 show that the qualitative behavior observed in the main text persists under this alternative perturbation model. Across all tested noise levels, the reward–divergence curves remain stable and the proxy–proxy-gold relationship remains monotone over the observed range. Although smaller k produces heavier-tailed reward noise, it has the stabilizing effect under higher-order Rényi regularization. These results reinforce the main conclusion of Section 6.2: the favorable empirical behavior of Rényi regularization is not an artifact of the power transformation, but persists under a distinct heavy-tailed reward construction. I.4 Application of SGLD to heavy-tailed linear regressions To connect the SGLD experiment with the theory developed above, we first recall a square-loss setting in which the sub-Weibull increment condition can be verified explicitly. Example 1 (Squared Loss) Let Z=(X,Y)Z=(X,Y) with X∈ℝpX ^p and Y∈ℝY , and assume Y∼subW(θ)Y (θ) for some θ<2θ<2. Consider the squared loss ℓ(w,Z)=(f(w,X)−Y)2. (w,Z)=(f(w,X)-Y)^2. For fixed X, the loss ℓ(w,Z)=(f(w,X)−Y)2 (w,Z)=(f(w,X)-Y)^2 is sub-Weibull with tail parameter θ/2θ/2, so in particular it is heavy-tailed when θ/2<1θ/2<1; see Corollary 4 in (Zhang and Wei, 2022). If f(⋅,x)f(·,x) is L-Lipschitz in w and uniformly bounded: |f(w,x)|≤M|f(w,x)|≤ M and |f(u,x)−f(v,x)|≤L‖u−v‖|f(u,x)-f(v,x)|≤ L\|u-v\| for all u,vu,v and x∈ℝx . Then, for any u,v∈ℝu,v , ℓ(u,Z)−ℓ(v,Z)=(f(u,X)−f(v,X))(f(u,X)+f(v,X)−2Y). (u,Z)- (v,Z)= (f(u,X)-f(v,X) ) (f(u,X)+f(v,X)-2Y ). Therefore, by (A.1) in Appendix A.1, we have ‖ℓ(u,Z)−ℓ(v,Z)‖ψθ \| (u,Z)- (v,Z)\|_ _θ ≤‖f(u,X)−f(v,X)‖∞‖f(u,X)+f(v,X)−2Y‖ψθ ≤\|f(u,X)-f(v,X)\|_∞\,\|f(u,X)+f(v,X)-2Y\|_ _θ ≤L‖u−v‖Dθ(2M+2‖Y‖ψθ), ≤ L\|u-v\|D_θ (2M+2\|Y\|_ _θ ), where Dθ=21/θ0<θ<1+θ≥1D_θ=2^1/θ1\0<θ<1\+1\θ≥ 1\. Moreover, using (A.2) in Appendix A.1, the same type of bound holds for the centered increments ‖ℓ¯(u,Z)−ℓ¯(v,Z)‖ψθ\| (u,Z)- (v,Z)\|_ _θ. Therefore, with d(u,v)=C2(θ)DθL‖u−v‖(2M+2‖Y‖ψθ),d(u,v)=C_2(θ)D_θL\|u-v\| (2M+2\|Y\|_ _θ ), the centered loss process has sub-Weibull increments with respect to the metric d. We now specialize Example I.4 to heavy-tailed linear regressions and run SGLD on it. We take d=2d=2 and f(w,x)=x⊤wf(w,x)=x w, with true parameter β0=(1,−1)⊤∈ℝ2 _0=(1,-1) ^2. For each i=1,…,ni=1,…,n, the covariate Xi=(Xi1,Xi2)⊤X_i=(X_i1,X_i2) is sampled independently from Unif([0,1]2)Unif([0,1]^2), and the latent response is generated as Y~i∣Xi∼(Xi⊤β0,1) Y_i X_i (X_i _0,1). Consider the power transformation Yi=sign(Y~i)|Y~i|λ,λ∈1,…,10.Y_i=sign( Y_i)| Y_i|^λ, λ∈\1,…,10\. Here λ=1λ=1 corresponds to the Gaussian baseline, while larger λ induce increasingly heavy-tailed responses. The learner observes only the transformed samples Zi=(Xi,Yi)Z_i=(X_i,Y_i). We estimate the regression parameter by minimizing the squared loss ℓ(w,Zi)=(Xi⊤w−Yi)2, (w,Z_i)=(X_i w-Y_i)^2, which falls into the sub-Weibull index θ:=1/λθ:=1/λ in Theorem F. In this case, the single-sample stochastic gradient is g(w,Zi)=2(Xi⊤w−Yi)Xig(w,Z_i)=2(X_i w-Y_i)X_i, the mini-batch gradient is g(w,Bt)=|Bt|−1∑k∈Btg(w,Zk)g(w,B_t)=|B_t|^-1 _k∈ B_tg(w,Z_k), and the SGLD iterate is updated according to Wt+1=Wt−ηtg(Wt,Bt)+εt,εt∼(0,I2).W_t+1=W_t- _tg(W_t,B_t)+ _t, _t (0,I_2). We run the algorithm for K=100K=100 epochs. Using online updates with |Bt|=1|B_t|=1, this gives a total of T=100nT=100n iterations. We use a polynomial decay schedule satisfying ηt2/θ=t−θ _t^2/θ=t^-θ. This design allows us to study how the transformed heavy-tailed responses interact with the SGLD dynamics in (F.1) under the squared-loss model of Example I.4. Figure 9: Generalization gap versus iteration number for different sample sizes n. For any fixed λ, larger sample sizes generally lead to smaller generalization gaps throughout training, while for fixed n, increasing λ tends to enlarge the gap, indicating that heavier-tailed responses degrade generalization performance. Figures 9 and 10 reveal two clear trends. First, for any fixed λ, increasing the sample size n lowers the generalization gap throughout training: in Figure 9, the trajectories for larger n are generally below those for smaller n, and the left panel of Figure 10 is broadly consistent with the expected n−1/2n^-1/2 scaling. Second, for any fixed sample size n, increasing λ raises the generalization gap substantially. Because larger λ corresponds to a smaller tail index θ=1/λθ=1/λ, this shows that heavier tails systematically degrade generalization performance. Taken together, the two figures indicate that larger sample sizes improve generalization, but this benefit becomes less pronounced as the response distribution becomes heavier-tailed. This behavior is consistent with the sub-Weibull theory underlying Theorem F: heavier tails weaken concentration and thereby enlarge the gap between empirical and population risks. The SGLD experiment supports the same conclusion as the theory: the generalization gap decreases with n but increases with λ, and the adverse effect of heavy tails becomes progressively stronger as the response distribution departs from the Gaussian baseline. Figure 10: Left: generalization gap versus 1/n1/ n for different λ. Right: generalization gap versus λ for different sample sizes n. The left panel is broadly consistent with the expected n−1/2n^-1/2 scaling, while the right panel shows that the generalization gap increases markedly with λ, confirming that heavier-tailed response distributions lead to worse generalization.