PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization Bounds via Vector-Valued $L_p$ Correlation $V_\alpha$

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

arXiv:2610.29425v1cs.LGcs.ITmath.IT

TL;DR

Generalization bounds for randomized learning algorithms use data–output dependence, but mutual-information and total-variation measures can behave differently in high-dimensional regimes. This paper derives bounds based on the tunable Vα family and extends them with density stability and supersample formulations. The paper establishes reparameterization invariance and evaluates how α and projection choices affect empirical tightness and estimability.

  • Problem

    Mutual-information and total-variation bounds quantify dependence between training data and randomized outputs, but can behave differently in high-dimensional regimes.

    Source: §1 · p. 1

  • Method

    The paper derives Vα-based bounds and extends them with adaptive density stability and supersample conditional formulations.

    Source: §1 · p. 2

  • Results

    Vα is invariant under smooth bijective reparameterizations, and experiments illustrate how α, projection statistics, and binarization affect empirical tightness and estimability.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bounds offer TV-type, variance-based, and lower-order-moment specializations, with their dependence terms and loss sensitivity varying across α.

    Source: §1 · p. 2

    The base parameter-space bound can be large in high-dimensional models, full-vector conditional estimates can be difficult with few selector draws, and deep-learning experiments cover only a small set of datasets and architectures.

    Source: §8 · p. 12

Abstract

from arXiv · show

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_\alpha$, and derive generalization bounds whose dependence terms interpolate between total variation (TV) at $\alpha=1$ and variance and $\chi^2$ related behavior at $\alpha=2$. For $\alpha>2$, the H\"older-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 $\alpha=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_\alpha$ 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 $\alpha$ 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.

1 Introduction

The paper develops Vα-based generalization bounds to address how dependence between training data and randomized outputs relates to generalization, especially in high-dimensional regimes. It extends the framework through density stability, supersample conditioning, and projected bounds, and evaluates how α and projection choices affect the resulting quantities.

1 Introduction

  • Vα bounds interpolate between a TV-type endpoint at α = 1 and variance- and χ2-related behavior at α = 2, with heavy-tailed specializations for α > 2.For α > 2, the conjugate loss moment q = α/(α −1) lies below two, so the bound can use lower-order moments even when variance is infinite.Source: §1 · p. 2
  • At α = 2, the dependence term is expressed through output-density variability across datasets, and Vα is invariant under smooth bijective reparameterizations.The invariance holds for every α ≥ 1.Source: §1 · p. 2
  • Adaptive Density Stability (ADS) gives explicit control of V2, and fixed-temperature Gibbs posteriors satisfy ADS under bounded losses with γn = O(1/n) when β and the loss bound are fixed.The Gibbs-posterior result concerns the stated bounded-loss, fixed-temperature setting.Source: §1 · p. 2
  • Supersample bounds measure dependence between the selector and learned object conditional on the supersample, while projected variants can reduce effective dimension when the statistic preserves the selected-versus-ghost gap.The variants include output-space, loss-difference, loss-pair, and binarized forms.Source: §1 · p. 2
  • Experiments on supersample MNIST, pretrained ResNet-50 for CIFAR-10, and Bayesian linear regression illustrate how α, projection statistics, and binarization affect empirical tightness and estimability.The paper evaluates the proposed bounds and plug-in estimators in these settings.Source: §1 · p. 2

2 Preliminaries and Related Work

The preliminaries establish the learning setup and situate the paper’s Vα dependence measure among information-theoretic approaches to generalization. They connect its TV endpoint, convexity, and supersample extensions to the paper’s analysis of stability and scaling.

2.1 Statistical Learning Setup

  • A learning algorithm maps an i.i.d. training sample to a possibly randomized hypothesis, whose population and empirical risks define the generalization gap.The algorithm is represented by a conditional distribution given the sample.Source: §2.1 · p. 3

2.2 Information-Theoretic Bounds and Algorithmic Stability

  • Information-theoretic bounds quantify stability through data–hypothesis dependence; PAC-Bayes instead uses a prior-relative KL term and typically targets high-probability risk bounds.The paper characterizes these frameworks as complementary rather than exact specializations.Source: §2.2 · p. 3
  • Classical MI dependence can scale linearly with parameter count, while supersample CMI shifts dependence to sample size; the paper adapts this machinery to Vα.The Vα adaptation is presented as equipping the framework for high-dimensional regimes.Source: §2.2 · p. 3

2.3 The Vα Correlation Measure

  • Vα is a convex dependence measure that equals twice total variation at α = 1 and is related to Rényi mutual information for α > 1.Its convexity with respect to conditional distributions supports the decoupling analysis used for generalization bounds.Source: §2.3 · p. 4

3 The Vα Information Framework

The Vα framework bounds expected generalization error by combining loss sensitivity with data–output dependence, trading between the two as α changes. Its rate and moment requirements depend on α and on control of the dependence term.

3.1 A general bound on the generalization error

  • The master Vα bound applies for every α ≥ 1 to learning algorithms and measurable losses when its displayed quantities are well-defined.The α = 1 and α = 2 cases are interpretable reference regimes; intermediate values trade off loss sensitivity and dependence.Source: §3.1 · pp. 4–5

3.2 Subgaussian specialization (rate form)

  • As α increases, Vα is non-decreasing while the loss-sensitivity factor decreases, so the two factors move in opposite directions.No α is universally best; the choice can depend on the algorithm, loss, and data distribution.Source: §3.2 · p. 5
  • Under subgaussian losses, α > 1 gives an explicit n^-1/2 loss-sensitivity factor, and the full bound has that rate when Vα stays O(1) in n.If Vα itself decreases with n, the resulting rate can be faster.Source: §3 · p. 4, §3.2 · p. 5

3.3 Recovering n−1/2 rates and the α = 1 regime

  • At α = 1, the worst-case L∞ loss deviation need not decay with n; α > 1 restores an n^-1/2 loss-sensitivity factor under subgaussianity.The full bound’s rate still depends on how Vα varies with n.Source: §3.3 · p. 5

3.4 Heavy-tailed example: finite lower-order moments

  • For α > 2, the bound can use a finite centered q-th loss moment with q = α/(α − 1) ∈ (1, 2), even when loss variance is infinite.The generic rate is n^-1/α rather than n^-1/2; the specialization is vacuous if Mq or Vα is infinite.Source: §3.4 · p. 6
  • At α = ∞, dependence is measured by the essential-supremum deviation of the conditional output law over datasets, while the loss factor is a mean absolute deviation.A first-moment assumption alone gives no universal polynomial decay in n without additional tail or regularity assumptions.Source: §3.4 · p. 6

4 The Variance Perspective: α = 2

At α = 2, the dependence term can be expressed through variability in the algorithm’s output density across training samples, linking the bound to algorithmic stability. The Vα dependence terms are also invariant under smooth bijective coordinate changes independent of the training sample.

4 The Variance Perspective: α = 2

  • At α = 2, the dependence term is represented by output-density variability across samples; higher variability penalizes the bound, while lower variability yields a tighter guarantee.This is an average-case sensitivity measure of the output distribution, distinct from uniform stability’s worst-case loss change after altering one data point.Source: §4 · p. 7

4.1 A Geometric Advantage: Reparameterization Invariance

  • For every α ≥ 1, Vα is invariant under smooth bijective coordinate changes independent of the training sample, so the dependence term is not a coordinate artifact.The α = 2 case additionally has the density-variance interpretation.Source: §4.1 · p. 7

5 Adaptive Density Stability (ADS) & Practical Rates

The section introduces Adaptive Density Stability (ADS) to control the V2 measure and obtain generalization guarantees. It verifies ADS for fixed-temperature Gibbs posteriors under bounded losses, while the resulting rate depends on keeping βM fixed.

5 Adaptive Density Stability (ADS) & Practical Rates

  • ADS restricts pointwise changes in output density relative to the marginal density, imposing stronger stability constraints on low-probability tails.The condition is defined for every pair of datasets differing in one example and every hypothesis; p(w) is the marginal output density.Source: §5 · p. 8
  • ADS gives explicit control of V2, which yields a generalization bound under the stated loss condition.For σ2-subgaussian loss, Theorem 4 converts the V2 control into a bound on generalization error.Source: §5 · p. 8
  • For bounded losses, fixed-temperature Gibbs posteriors satisfy ADS with γn = O(1/n), yielding an O(1/n) generalization rate when βM is fixed.The Gibbs-posterior calculation concerns the posterior itself, not finite-step or finite-time SGLD iterates.Source: §5 · pp. 8–9
  • The rate is not uniformly non-vacuous across inverse temperatures: when β = Θ(n) with fixed M, the certificate becomes exponentially conservative.The fast-rate statement applies when βM is fixed.Source: §5 · p. 9
  • ADS is a strong condition, and extending the Gibbs example to other stochastic algorithms requires algorithm-specific ADS arguments.Source: §5 · pp. 8–9

6 Scaling to High Dimensions via Conditional and Projected Vα Bounds

The section moves dependence analysis to a supersample selector, then uses projections to make the resulting quantities lower-dimensional and more estimable. These changes can mitigate parameter-space scaling issues but do not guarantee small dependence or easy estimation.

6 Scaling to High Dimensions via Conditional and Projected Vα Bounds

  • The supersample formulation measures how much the learned object reveals about the selector choosing training examples, rather than directly measuring dependence on the full sample.The selector-dependent term can still be large when the learned object reveals substantial information about the selector.Source: §6 · p. 9, §6.1 · p. 10

6.1 Conditional Vα bound

  • The conditional Vα bound replaces dependence on the full sample with dependence on the discrete selector U, which can mitigate dimension-scaling issues.The term may remain large if the learned object nearly determines U.Source: §6.1 · p. 10

6.2 Projected and estimable variants (overview)

  • Projecting W to a lower-dimensional statistic that preserves the supersample gap cannot increase the Vα dependence term, and can make it more estimable.Examples include supersample predictions, loss differences, and evaluated losses; the section also gives sample-wise and binarized variants.Source: §6.2 · p. 10

7 Experiments

The experiments compare estimated bound increments with empirical selected-versus-ghost gaps across MNIST and CIFAR-10, and examine α tuning and dimension effects in Bayesian linear regression. Loss-pair and binarized estimates are close to the empirical gap in the reported image settings, while BLR exposes trade-offs between parameter-space and conditional bounds.

7 Experiments

  • On MNIST and CIFAR-10, T10–T13 stay close to ratio 1 for clipped cross-entropy; for 0–1 loss, T9–T13 are close on MNIST and CIFAR-10, while T8 is more conservative.On MNIST 0–1 loss, T8 ratios are about 1.9–2.0; on CIFAR-10 they are about 1.8–1.9.Source: Figure 1 · p. 11, §7 · p. 11
  • Under MNIST label-noise probabilities 0.05, 0.10, and 0.15, clipped cross-entropy retains the separation between the more conservative T8/T9 estimates and T10–T13.Source: §7 · p. 11
  • In Bayesian linear regression, fixed α = 2 parameter-space bounds degrade with dimension, tuning α can improve tightness, and conditional bounds are dimension-free but numerically conservative.Source: §7 · p. 11

8 Conclusion and Limitations

The conclusion presents Vα bounds as a tunable bridge between TV-like and variance-like regimes, with an interpretable α = 2 stability view. The authors qualify the empirical findings as descriptive and identify limits in estimation, assumptions, and experimental scope.

8 Conclusion and Limitations

  • At α = 2, the bound has a variance-stability interpretation through VarS[p(w|S)], and this quantity is invariant under smooth reparameterizations of the hypothesis space.The conclusion also extends the framework to conditional, projected, sample-wise, and binarized supersample bounds.Source: §8 · pp. 11–12
  • The empirical comparisons are descriptive rather than finite-sample certificates, and the deep-learning experiments cover only a small set of classification datasets and architectures.The authors call for sharper finite-sample estimators and validation across larger architectures and datasets.Source: §8 · p. 12
  • The base Vα bound can remain large in high-dimensional models, while full-vector conditional and projected bounds can be difficult to estimate from few selector draws.The authors caution that ADS is a strong pointwise condition and is not a generic guarantee for deterministic deep networks without additional smoothing or randomization.Source: §8 · p. 12

A Extended Related Work and Modern Baselines

A.1 Advancements in Conditional and Sample-Wise Measures

The appendix situates Vα among conditional and stability-based approaches, then develops its bounds and ADS connections. It emphasizes the framework’s tunable dependence measure and the α = 2 density-variance interpretation.

A.1 Advancements in Conditional and Sample-Wise Measures

  • Supersample conditioning shifts Vα dependence analysis toward the selector and learned object, while projected variants can lower effective dimension when the statistic preserves the selected-versus-ghost gap.The appendix frames this extension as addressing dimensionality challenges that also affect the base Vα framework.Source: §A.1 · p. 15

A.2 Divergences, f-Information, and Binary Comparators

  • The framework favors an explicit tunable Vα family over more abstract f-information or Orlicz unifications, with α = 2 yielding an interpretable VarS[p(w|S)] expression.Source: §A.2 · p. 15

A.3 Variance, Learnability, and Bayesian Stability

  • V2 measures hypothesis-space output-density variance, complementing outcome-space variance in population loss; its stability term is loss-agnostic and invariant under reparameterization.The loss scales the bound through the subgaussian constant.Source: §A.3 · p. 16

B.2 Symmetric form of Theorem 1

  • The general bound also has a symmetric form in Vα(W; S), allowing the tighter of the two valid forms to be used.Source: §B.2 · p. 17

B.3 Explicit subgaussian constant

  • As α increases, Vα is non-decreasing while the Hölder-conjugate loss-sensitivity prefactor shrinks, so the best α is problem-dependent.Source: §B.3 · p. 18

C.1 Proof of Theorem 2 (The Variance-Based Bound)

  • At α = 2, V2 can be expressed as an integral of the standard deviation of the output density across datasets, and the full Vα family is invariant under smooth bijective reparameterization.Source: §C.1 · p. 20, §C.2 · p. 20

D.1 Connection to Total Variation (TV) Stability

  • The ADS pointwise density condition implies integrated TV stability and, for bounded nonnegative losses, expected uniform stability with parameter Mγn/2; the converse need not hold.Source: §D.1 · p. 21, §D.2 · p. 21

D.4 Comparison with Bayesian Stability

  • ADS controls absolute pointwise density changes, unlike integrated KL-stability, and this structure matches the density-difference term used in the Efron-Stein analysis.Source: §D.4 · p. 22

E.1 Proof of Theorem 4 (Generalization via ADS)

The appendix derives V2 control from ADS and verifies ADS for bounded-loss Gibbs posteriors. It also gives a master decoupling lemma underpinning conditional and projected bounds.

E.1 Proof of Theorem 4 (Generalization via ADS)

  • When ADS has γn = O(1/n), the framework yields a generalization bound of order O(1/n).The derivation bounds output-density variance using Efron-Stein and substitutes that control into the V2 identity and variance-based generalization bound.Source: §E.1 · pp. 22–23

E.2 Rigorous Proof of Example 5.1 (Gibbs Posteriors satisfy ADS)

  • For bounded losses, Gibbs posteriors satisfy ADS with O(1/n) decay when β and the loss bound are fixed.The proof obtains a neighboring-dataset density bound and extends it across datasets by composition.Source: §E.2 · pp. 23–25

F.1 A master Vα–Hölder decoupling lemma

  • A centered Vα–Hölder decoupling lemma is the shared analytic step behind conditional, output-space, loss-space, sample-wise, and binarized bounds.Source: §F.1 · p. 25
  • Conditional data processing ensures that post-processing the learned object cannot increase Vα dependence on the selector, conditional on the supersample.Source: §F.1 · p. 26

G Formal projected and sample-wise Vα bounds

The appendix derives projected, sample-wise, and binarized conditional Vα bounds as applications of one centered Vα–Hölder decoupling argument. The variants differ in the statistic used to represent the supersample gap and in how that statistic is reduced.

G Formal projected and sample-wise Vα bounds

  • All projected, sample-wise, and binarized bounds instantiate the same centered Vα–Hölder decoupling argument, with reductions changing the statistic rather than the bounding principle.Density ratios use the relevant marginal law; when absolute continuity or integrability fails, the associated Vα is +∞.Source: G Formal projected and sample-wise Vα… · pp. 26–27

G.1 Conditional output-space bound

  • When loss factors through predictions, Theorem 6 bounds the supersample gap using the prediction vector as a lower-dimensional statistic.The conditional data-processing inequality also permits further measurable post-processing without increasing Vα.Source: G Formal projected and sample-wise Vα… · p. 27, §G.1 · p. 28

G.2 Conditional loss-difference vector bound

  • Theorem 7 applies the conditional bound to the vector of selected-versus-ghost loss differences, with a prediction-space version when losses factor through predictions.The loss-difference vector is a measurable post-processing of the prediction statistic in that setting.Source: §G.2 · p. 29

G.3 Sample-wise loss-difference bound

  • Theorem 8 decomposes the supersample gap into coordinatewise loss-difference contributions and bounds them sample-wise, including a bounded-loss specialization.For losses in [0, M], each coordinate difference has magnitude at most M.Source: §G.3 · pp. 29–30

G.4–G.5 Sample-wise single-loss and loss-pair bounds

  • Theorem 9 bounds centered single-loss contributions, while Theorem 10 instead uses each coordinate’s evaluated loss pair.For losses in [0, M], Theorem 9’s stated specialization uses center ci = M/2.Source: §G.4 · p. 30, §G.5 · p. 31

G.6–G.8 Binarized bounds

  • Theorems 11–13 give binarized sample-wise bounds for single losses, loss differences, and loss pairs, respectively.For losses in [0, M], the displayed binarized bounds are scaled by M.Source: §G.6 · p. 32, §G.7 · p. 33, §G.8 · p. 34

G.9 Conditional coordinatewise versions used in the experiments

  • With a fair binary selector, the local Vα likelihood-ratio factor—and its statistic-weighted expectation—is independent of α.The appendix uses this invariance for the conditional coordinatewise single-loss and binarized bounds in the experiments.Source: §G.9 · p. 35

H Experimental Details and Methodology

The experiments estimate conditional, coordinatewise Vα bounds from supersample runs and compare them with observed generalization gaps and other bounds. The appendix also specifies the MNIST, noisy-MNIST, CIFAR-10, and Bayesian linear regression settings and estimator choices.

H Experimental Details and Methodology

  • The clean MNIST experiment classifies digits 4 versus 9, using five supersample seeds and 30 selector runs per supersample to evaluate 0–1 and clipped cross-entropy losses.The clipped cross-entropy is capped at 1, matching the stated bound M = 1 for both evaluated losses.Source: H Experimental Details and Methodology · p. 36
  • T10–T13 remain close to the observed gap across displayed settings; T8 is more conservative for 0–1 loss, while T8 and T9 are more conservative for clipped cross-entropy.T8 uses the worst-case loss range instead of the local loss-difference magnitude; T9 can lose cancellation between paired losses.Source: H Experimental Details and Methodology · p. 38

H.1 Additional deep-learning experiments

  • With random label-flip rates δ = 0.05, 0.10, and 0.15, T10–T13 stay near the gap for clipped cross-entropy; T9 is not uniformly tighter than T8.Figure 3 reports the noisy-MNIST bound-to-gap ratios for 0–1 loss and clipped cross-entropy.Source: §H.1 · p. 38, Figure 3 · p. 39

I Additional Results on Bayesian Linear Regression

  • The BLR appendix compares parameter-space and supersample-conditional bounds at n = 100 across dimensions d = 1, 2, 5, and 10 using a conjugate Gaussian posterior.The reported experiment is a moderate-dimensional run with those fixed dimensions and sample size.Source: I Additional Results on Bayesian… · p. 38, §I.1 · p. 39

I.2 Monte Carlo Estimators

  • The BLR estimators use posterior-mixture Monte Carlo for parameter-space Vα and Gaussian-mixture approximations for conditional marginals; finite-candidate curves are diagnostics, not certified bounds absent an external supremum certificate.The experiment selects α on an independent pool and evaluates it on a disjoint pool.Source: §I.2 · pp. 40–41

I.3 Reported Figures and Interpretation

In the BLR experiment, the fixed α = 2 parameter-space bound loosens as dimension grows, while optimizing α reduces that growth. The selected α values also shift below 2 in several formulations as dimension increases.

I.3 Reported Figures and Interpretation

  • The fixed V2 parameter-space curve is competitive at the lowest dimension but loosens as dimension grows; optimizing the Corollary 2 bound reduces that growth, while conditional theorem-valid bounds are dimension-free but conservative.Estimated CMI is smaller than estimated MI, although the bounded-loss CMI bound is numerically larger because its prefactor is twice the Hoeffding-based MI prefactor.Source: §I.3 · p. 41
  • The conditional finite-candidate approximation rises from about 0.020 at d = 1 to about 0.132 at d = 10, and finite-candidate diagnostics are substantially smaller than theorem-based estimates.The authors interpret this gap mainly as evidence of conservative theorem-valid prefactor control in this BLR regime.Source: §I.3 · p. 41
  • The theorem-valid conditional α⋆ values are 2.0, 2.0, 2.0, and 1.85 as d grows, while the parameter-space formulations select smaller α values at higher dimensions.Figure 5 shows the selected α⋆ trajectories for the reported BLR experiment.Source: §I.3 · p. 42, Figure 5 · p. 42

J Additional Results on Canonical Channel Models

Exact evaluations on three binary channel models compare the V2 and classical MI bounds, with V2 no larger across the plotted parameter ranges. A separate Z-channel example illustrates that an intermediate α can minimize the bound.

J Additional Results on Canonical Channel Models

  • The channel experiments use n = 1, binary data and hypotheses, and squared loss; the BEC adds an erasure output mapped to prediction 0.5.Exact analytical evaluation removes Monte Carlo variance and approximation error for the reported true error and bounds.Source: J Additional Results on Canonical… · p. 42
  • For the BSC, BEC, and Z-channel, the proposed V2 bound is no larger than the MI bound and is strictly smaller away from equality cases.Figure 6 compares the bounds across the full parameter range of each channel.Source: J Additional Results on Canonical… · p. 43, Figure 6 · p. 43

J.1 Illustration of the α Trade-off

  • In the considered Z-channel setting, balancing loss sensitivity and dependence yields the smallest bound at an intermediate α.The illustration varies α to examine the two competing terms in Theorem 1.Source: §J.1 · p. 44, Figure 7 · p. 44

Related papers

Loading 2610.29425v1…