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

Jun 5, 2026

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

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.

Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1

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

Ask PDF

May 13, 2026

A Survey on Data-Dependent Worst-Case Generalization Bounds

Deep neural networks generalize well despite being heavily overparameterized, in apparent contradiction with classical learning theory based on uniform convergence over fixed hypothesis spaces. Uniform bounds over the entire parameter space are vacuous in this regime, and recent work has shown that non-vacuous guarantees can be recovered by restricting attention to the part of parameter space that the algorithm actually visits. This survey paper organizes this line of work around three steps: extending PAC-Bayesian theory to random, data-dependent hypothesis sets (arXiv:2404.17442); refining the complexity term with geometric and topological descriptors of the optimization trajectory, including fractal dimensions, alpha-weighted lifetime sums, and positive magnitude (arXiv:2006.09313, arXiv:2302.02766, arXiv:2407.08723); and replacing the resulting information-theoretic terms by stability assumptions (arXiv:2507.06775). We unify these contributions around a single template inequality and a head-to-head comparison of the resulting bounds.

Hubert Leroux, Jean Marcus, Julien Roger

´Ecole polytechnique Palaiseau, France

Neural Network Generalization PAC-Bayesian Generalization Bounds Generalization Bounds Algorithmic Generalization

Ask PDF

Aug 25, 2026

The Sharp Tail of Uniform Stability

Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a

γ

-uniformly stable algorithm with loss in

[0,L]

has generalization gap at most

O \left(γ\log(1/δ) +L\sqrt{\frac{\log(1/δ)}{n}}\right)

with probability

1-δ

. Whether an actual bounded-loss learning algorithm can realize the linear dependence on

\log(1/δ)

has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with

n

. The known learning lower bound holds only at constant probability. We close this gap. For every

n

, stability level

γ

, and loss bound

L

, we construct one deterministic

γ

-uniformly stable learning problem whose tail satisfies, simultaneously for

1\le p\le c n

\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,γp+L\sqrt{p/n}\right\} \right)\ge e^{-p}.

The construction is ordinary bounded absolute-loss regression with constant labels. Its key is a multiscale collection of rare Rademacher features. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of order

γp

without violating the loss bound. Geometrically spaced ramps put all confidence levels into the same problem. Together with the logarithmic-free upper bound, this determines the optimal high-probability and moment dependence of uniform stability up to universal constants.

Pahan Dewasurendra

Johns Hopkins University

Algorithmic Stability Generalization Bounds

Ask PDF

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