A DPI-PAC-Bayesian Framework for Generalization Bounds

• URL: http://arxiv.org/abs/2507.14795v3
• Date: Tue, 29 Jul 2025 01:17:07 GMT
• Title: A DPI-PAC-Bayesian Framework for Generalization Bounds
• Authors: Muhan Guan, Farhad Farokhi, Jingge Zhu,
• Abstract summary: We develop a unified Data Processing Inequality PAC-Bayesian framework -- abbreviated DPI-PAC-Bayesian.<n>We obtain explicit bounds on the binary Kullback-Leibler generalization gap for both R'enyi divergence and any $f$-divergence measured between a data-independent prior distribution and an algorithm-dependent posterior distribution.
• Score: 11.922046341518278
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a unified Data Processing Inequality PAC-Bayesian framework -- abbreviated DPI-PAC-Bayesian -- for deriving generalization error bounds in the supervised learning setting. By embedding the Data Processing Inequality (DPI) into the change-of-measure technique, we obtain explicit bounds on the binary Kullback-Leibler generalization gap for both R\'enyi divergence and any $f$-divergence measured between a data-independent prior distribution and an algorithm-dependent posterior distribution. We present three bounds derived under our framework using R\'enyi, Hellinger \(p\) and Chi-Squared divergences. Additionally, our framework also demonstrates a close connection with other well-known bounds. When the prior distribution is chosen to be uniform, our bounds recover the classical Occam's Razor bound and, crucially, eliminate the extraneous \(\log(2\sqrt{n})/n\) slack present in the PAC-Bayes bound, thereby achieving tighter results. The framework thus bridges data-processing and PAC-Bayesian perspectives, providing a flexible, information-theoretic tool to construct generalization guarantees.

Related papers

• Distributional Vision-Language Alignment by Cauchy-Schwarz Divergence [83.15764564701706]
  We propose a novel framework that performs vision-language alignment by integrating Cauchy-Schwarz divergence with mutual information.<n>We find that the CS divergence seamlessly addresses the InfoNCE's alignment-uniformity conflict and serves complementary roles with InfoNCE.<n> Experiments on text-to-image generation and cross-modality retrieval tasks demonstrate the effectiveness of our method on vision-language alignment.
  arXiv  Detail & Related papers  (2025-02-24T10:29:15Z)
• Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets [25.250314934981233]
  We first apply the PAC-Bayesian framework on "random sets" in a rigorous way, where the training algorithm is assumed to output a data-dependent hypothesis set.<n>This approach allows us to prove data-dependent bounds, which can be applicable in numerous contexts.
  arXiv  Detail & Related papers  (2024-04-26T14:28:18Z)
• Tighter Generalisation Bounds via Interpolation [16.74864438507713]
  We present a recipe for deriving new PAC-Bayes generalisation bounds based on the $(f, Gamma)$-divergence. We also present PAC-Bayes generalisation bounds where we interpolate between a series of probability divergences.
  arXiv  Detail & Related papers  (2024-02-07T18:55:22Z)
• PAC-Bayes-Chernoff bounds for unbounded losses [9.987130158432755]
  We introduce a new PAC-Bayes oracle bound for unbounded losses that extends Cram'er-Chernoff bounds to the PAC-Bayesian setting. Our approach naturally leverages properties of Cram'er-Chernoff bounds, such as exact optimization of the free parameter in many PAC-Bayes bounds.
  arXiv  Detail & Related papers  (2024-01-02T10:58:54Z)
• Data-dependent Generalization Bounds via Variable-Size Compressibility [16.2444595840653]
  We establish novel data-dependent upper bounds on the generalization error through the lens of a "variable-size compressibility" framework. In this framework, the generalization error of an algorithm is linked to a variable-size 'compression rate' of its input data. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds.
  arXiv  Detail & Related papers  (2023-03-09T16:17:45Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  Thompson sampling and other sequential decision-making algorithms are popular approaches to tackle explore/exploit trade-offs in contextual bandits. We show that performance degrades gracefully with misspecified priors.
  arXiv  Detail & Related papers  (2021-07-03T23:17:26Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  We study reinforcement learning with linear function approximation. Existing algorithms only have high-probability regret and/or Probably Approximately Correct (PAC) sample complexity guarantees. We propose a new algorithm called FLUTE, which enjoys uniform-PAC convergence to the optimal policy with high probability.
  arXiv  Detail & Related papers  (2021-06-22T08:48:56Z)
• Information Complexity and Generalization Bounds [0.0]
  We show a unifying picture of PAC-Bayesian and mutual information-based upper bounds on randomized learning algorithms. We discuss two practical examples for learning with neural networks, namely, Entropy- and PAC-Bayes- SGD.
  arXiv  Detail & Related papers  (2021-05-04T20:37:57Z)
• Implicit Distributional Reinforcement Learning [61.166030238490634]
  implicit distributional actor-critic (IDAC) built on two deep generator networks (DGNs) Semi-implicit actor (SIA) powered by a flexible policy distribution. We observe IDAC outperforms state-of-the-art algorithms on representative OpenAI Gym environments.
  arXiv  Detail & Related papers  (2020-07-13T02:52:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.