Generalization Bounds via Vector-Valued $L_p$ Correlation $V_α$

Mohammad Hossein Momeni Hamaneh; Mohammad Mahdi Mojahedian; Mohammad Hossein Yassaee

cs.LGOct 21, 2026

Generalization Bounds via Vector-Valued $L_p$ Correlation $V_α$

Authors: Mohammad Hossein Momeni Hamaneh, Mohammad Mahdi Mojahedian, Mohammad Hossein Yassaee

Organizations: Information Systems and Security Laboratory (ISSL), Sharif University of Technology, Tehran, Iran

Abstract

Understanding generalization of randomized learning algorithms remains a central challenge. Mutual-information and total-variation bounds provide complementary ways to quantify data--hypothesis dependence, but they can behave quite differently in high-dimensional regimes. We study a one-parameter family of dependence measures, the vector-valued $L_p$ -norm correlation $V_α$ , and derive generalization bounds whose dependence terms interpolate between total variation (TV) at $α=1$ and variance and $χ^2$ related behavior at $α=2$ . For $α>2$ , the Hölder-conjugate loss moment is below two, yielding heavy-tailed specializations that can remain finite even when the loss variance is infinite. A particularly interpretable specialization occurs at $α=2$ , where the bound can be expressed in terms of the variability of the algorithm's output density across datasets, $\int \sqrt{\mathrm{Var}_S[p(w\mid S)]}~ dw$ . We show that the entire $V_α$ family is invariant under smooth bijective reparameterizations of the hypothesis space. We also introduce an adaptive density stability (ADS) condition that implies explicit control of $V_2$ , and we verify it for Gibbs-type posteriors under bounded losses (yielding rates that depend on the inverse temperature and sample size). To address scaling, we extend the framework to a conditional formulation using supersamples, analogous in spirit to conditional mutual information (CMI), and discuss evaluations in the output space as a practical surrogate for estimating dependence. Simulations on Bayesian linear regression illustrate how tuning $α$ can change the tightness of the resulting bounds across regimes. Additional supersample experiments on noisy MNIST and on a pretrained ResNet-50 for CIFAR-10 show similar behavior of the projected loss-space bounds beyond the original clean-MNIST setting.

Figures & tables

Figure 1: Ratio between estimated bound increments and the empirical selected-versus-ghost gap on MNIST

4

vs.

9

. Left:

0

1

loss. Right: clipped cross-entropy. The dashed line denotes ratio

1

. Error bars show the standard error of the mean (SEM) over five supersample seeds.

Figure 2: CIFAR-10 results with a pretrained ResNet-50. The panels show the ratio between the estimated bound increment and the empirical selected-versus-ghost gap for

0

–

1

loss (left) and clipped cross-entropy (right). The dashed line denotes ratio

1

. Error bars show SEM over two supersample seeds.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Result	Statistic	Certified bound on $\|\overline{\mathrm{gen}}\|$
Thm. 6	Output vector $T_{\tilde{S}}$	$\displaystyle\mathbb{E}_{\tilde{S}}\!\left[\operatorname{ess\,sup}_{t}\\|\hat{\Delta}_{\tilde{S}}(t,U)\\|_{\alpha^{\prime},U}\,V_{\alpha}(U;T_{\tilde{S}}\mid\tilde{S})\right]$
Thm. 7	Loss-difference vector $D_{\tilde{S}}$	$\displaystyle\mathbb{E}_{\tilde{S}}\!\left[\operatorname{ess\,sup}_{d}\left\\|\frac{1}{n}\sum_{i}(1-2U_{i})d_{i}\right\\|_{\alpha^{\prime},U}V_{\alpha}(U;D_{\tilde{S}}\mid\tilde{S})\right]$

Appendix

Table 1: Full-vector conditional

V_{\alpha}

bounds. These are direct instantiations of the centered

V_{\alpha}

–Hölder decoupling principle.

Result	Statistic	Certified bound on $\|\overline{\mathrm{gen}}\|$
Thm. 8	$D_{i}=L_{i}^{1}-L_{i}^{0}$	$\displaystyle\frac{1}{n}\sum_{i}\mathbb{E}_{\tilde{S}}\mathbb{E}_{D_{i}\mid\tilde{S}}[\|D_{i}\|\lambda_{\alpha}(D_{i};U_{i}\mid\tilde{S})]$ ; if $0\leq\ell\leq M$ , at most $\displaystyle\frac{M}{n}\sum_{i}\mathbb{E}_{\tilde{S}}V_{\alpha}(U_{i};D_{i}\mid\tilde{S})$
Thm. 9	Single loss $L_{i}^{0}$	$\displaystyle\frac{2}{n}\sum_{i}\mathbb{E}_{L_{i}^{0}}[\|L_{i}^{0}-c_{i}\|\lambda_{\alpha}(L_{i}^{0};U_{i})]$ ; if $0\leq\ell\leq M$ and $c_{i}=M/2$ , at most $\displaystyle\frac{M}{n}\sum_{i}V_{\alpha}(U_{i};L_{i}^{0})$
Thm. 10	$P_{i}=(L_{i}^{0},L_{i}^{1})$	$\displaystyle\frac{1}{n}\sum_{i}\mathbb{E}_{\tilde{S}}\mathbb{E}_{P_{i}\mid\tilde{S}}[\|L_{i}^{1}-L_{i}^{0}\|\lambda_{\alpha}(P_{i};U_{i}\mid\tilde{S})]$ ; if $0\leq\ell\leq M$ , at most $\displaystyle\frac{M}{n}\sum_{i}\mathbb{E}_{\tilde{S}}V_{\alpha}(U_{i};P_{i}\mid\tilde{S})$

Appendix

Table 2: Continuous sample-wise loss-space

V_{\alpha}

generalization bounds. For each result, the table gives the projected statistic and the corresponding certified bound on

\left|\overline{\mathrm{gen}}\right|

. The weighted expressions retain the local loss magnitude, while the simplified expressions apply when the loss is bounded as

0\leq\ell\leq M

Result	Statistic	Certified bound on $\|\overline{\mathrm{gen}}\|$ for $0\leq\ell\leq 1$
Thm. 11	$\bar{L}_{i}^{0}\in\{0,1\}$	$\displaystyle\frac{1}{n}\sum_{i}V_{\alpha}(U_{i};\bar{L}_{i}^{0})$
Thm. 12	$\bar{D}_{i}\in\{-1,0,1\}$	$\displaystyle\frac{1}{n}\sum_{i}\mathbb{E}_{\bar{D}_{i}}[\|\bar{D}_{i}\|\lambda_{\alpha}(\bar{D}_{i};U_{i})]\leq\frac{1}{n}\sum_{i}V_{\alpha}(U_{i};\bar{D}_{i})$
Thm. 13	$\bar{P}_{i}\in\{0,1\}^{2}$	$\displaystyle\frac{1}{n}\sum_{i}\mathbb{E}_{\bar{P}_{i}}[\|\bar{L}_{i}^{1}-\bar{L}_{i}^{0}\|\lambda_{\alpha}(\bar{P}_{i};U_{i})]\leq\frac{1}{n}\sum_{i}V_{\alpha}(U_{i};\bar{P}_{i})$

Appendix

Table 3: Binarized sample-wise

V_{\alpha}

bounds. For losses in

[0,M]

, multiply the displayed right-hand sides by

M

Figure 3: Additional MNIST

4

-vs.-

9

results under random label noise. Each panel reports the bound-to-empirical-gap ratio for

0

–

1

loss (left) and clipped cross-entropy (right). Rows correspond to

\delta=0.05,0.10,0.15

from top to bottom. Error bars show SEM over five supersample seeds.

Figure 4: BLR bound comparison for the reported experiment. The figure includes Conditional theorem-valid

V_{\alpha}

(Theorem 5 ), Conditional finite-candidate approx.

V_{\alpha}

(Theorem 5 ), Parameter Cor. 2

V_{\alpha}

(Corollary 2 ), Parameter finite-candidate approx.

V_{\alpha}

(Theorem 1 ), and Parameter fixed

V_{2}

(

\alpha=2

) (Theorem 2 ), together with the MI and CMI baselines.

Figure 5: Selected

\alpha^{\star}

values for the reported BLR experiment. Conditional theorem-valid

\alpha^{\star}

stays at

2

for

d=1,2,5

and shifts slightly below

2

only at

d=10

, whereas Conditional finite-candidate

\alpha^{\star}

, Parameter Cor. 2

\alpha^{\star}

, and Parameter finite-candidate

\alpha^{\star}

move below

2

earlier.

Parameter	Description	Value
$\sigma_{\mathrm{noise}}^{2}$	Observation noise variance	$0.16$
$\lambda$	Gaussian prior precision	$2.0$
$c$	Clipping level in the squared loss	$4.0$
$\sigma_{\mathrm{loss}}^{2}$	Subgaussian scaling constant	$4.0$
$\mathbf{w}_{\mathrm{true}}$	Ground-truth coefficient in each coordinate	$0.8$
$d$	Dimensions evaluated	$[1,2,5,10]$

Appendix

Table 4: Configuration used to generate Figures 4 and 5 .

Figure 6: Normalized proposed (blue solid) and mutual-information (red dashed) generalization bounds at

\alpha=2

for (a) the BSC, (b) the BEC, and (c) the Z-channel. The common factor

\sqrt{\sigma^{2}/n}=1/2

is omitted.

Figure 7: Illustration of the trade-off in Remark 3 . As

\alpha

increases, the information term

V_{\alpha}(S;W)

grows while the loss sensitivity term

\|\cdot\|_{\alpha^{\prime}}

shrinks. Their product (our bound) is minimized at an intermediate value, providing a tighter guarantee than the classical mutual information bound.

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 162 papers

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
Jun 5, 2026Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1Algorithmic Stability Generalization Bounds
Department of Statistics, The University of Chicago, Chicago, IL 60637, USA. · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, USA.
A Survey on Data-Dependent Worst-Case Generalization Bounds
May 13, 2026Hubert Leroux, Jean Marcus, Julien RogerNeural Network Generalization PAC-Bayesian Generalization Bounds
´Ecole polytechnique Palaiseau, France
The Sharp Tail of Uniform Stability
Aug 25, 2026Pahan DewasurendraAlgorithmic Stability Generalization Bounds
Johns Hopkins University

Jun 5, 2026J/K move · Enter open · S save

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments

Qianqian Lei, Soham Bonnerjee, Yuefeng Han, Wei Biao Wu

Department of Statistics, The University of Chicago, Chicago, IL 60637, USA. · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, USA.

Algorithmic Stability Generalization Bounds

Open paper AskPDF arXiv

While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptions, which can be overly restrictive for modern settings with heavy-tailed or unbounded losses. We develop a stability-based framework that requires only a finite

L_p

moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under

L_p

constraints, extending McDiarmid's bounded-differences techniques beyond the classical regime. Leveraging these results, we derive sharp high-probability generalization bounds across a range of learning paradigms, including empirical risk minimization, transductive regression, and meta-learning. These guarantees show that

L_p

stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.

Abstract

Generalization Bounds

Explore similar work

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite LpL_pLp​ Moments

A Survey on Data-Dependent Worst-Case Generalization Bounds

The Sharp Tail of Uniform Stability

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments