PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes

• URL: http://arxiv.org/abs/2106.09683v1
• Date: Thu, 17 Jun 2021 17:35:29 GMT
• Title: PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
• Authors: Peter Gr\"unwald, Thomas Steinke, Lydia Zakynthinou
• Abstract summary: We give a novel, unified derivation of conditional PAC-Bayesian and mutual information (MI) generalization bounds. We get nontrivial PAC-Bayes and MI-style bounds for general VC classes, something recently shown to be impossible with standard PAC-Bayesian/MI bounds.
• Score: 17.544630217945333
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a novel, unified derivation of conditional PAC-Bayesian and mutual information (MI) generalization bounds. We derive conditional MI bounds as an instance, with special choice of prior, of conditional MAC-Bayesian (Mean Approximately Correct) bounds, itself derived from conditional PAC-Bayesian bounds, where `conditional' means that one can use priors conditioned on a joint training and ghost sample. This allows us to get nontrivial PAC-Bayes and MI-style bounds for general VC classes, something recently shown to be impossible with standard PAC-Bayesian/MI bounds. Second, it allows us to get faster rates of order $O \left(({\text{KL}}/n)^{\gamma}\right)$ for $\gamma > 1/2$ if a Bernstein condition holds and for exp-concave losses (with $\gamma=1$), which is impossible with both standard PAC-Bayes generalization and MI bounds. Our work extends the recent work by Steinke and Zakynthinou [2020] who handle MI with VC but neither PAC-Bayes nor fast rates, the recent work of Hellstr\"om and Durisi [2020] who extend the latter to the PAC-Bayes setting via a unifying exponential inequality, and Mhammedi et al. [2019] who initiated fast rate PAC-Bayes generalization error bounds but handle neither MI nor general VC classes.

Related papers

• Block-Sample MAC-Bayes Generalization Bounds [12.628001897418509]
  We present a family of novel block-sample MAC-Bayes bounds (mean approximately correct)<n>While PAC-Bayes bounds typically give bounds for the generalization error that hold with high probability, MAC-Bayes bounds have a similar form but bound the expected generalization error instead.
  arXiv  Detail & Related papers  (2026-02-13T04:23:12Z)
• Learning Conditional Averages [52.361762722359366]
  We introduce the problem of learning conditional averages in the PAC framework.<n>Instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood.<n>More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains.
  arXiv  Detail & Related papers  (2026-02-12T13:20:29Z)
• Misclassification excess risk bounds for PAC-Bayesian classification via convexified loss [0.0]
  PAC-Bayesian bounds are a valuable tool for designing new learning algorithms in machine learning. In this paper we show how to leverage relative bounds in expectation rather than relying on PAC-Bayesian bounds in terms of generalization.
  arXiv  Detail & Related papers  (2024-08-16T11:41:06Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• A unified recipe for deriving (time-uniform) PAC-Bayes bounds [31.921092049934654]
  We present a unified framework for deriving PAC-Bayesian generalization bounds. Our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times.
  arXiv  Detail & Related papers  (2023-02-07T12:11:59Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  This paper contributes to the study of CPAC learnability by solving three open questions from recent papers. Firstly, we prove that every CPAC learnable class is contained in a class which is properly CPAC learnable with a sample complexity. Secondly, we show that there exists a decidable class of hypothesis which is properly learnable, but only with uncomputably fast growing sample complexity.
  arXiv  Detail & Related papers  (2023-02-06T02:52:36Z)
• PAC Verification of Statistical Algorithms [0.10878040851637999]
  We develop the setting of PAC verification, where a hypothesis (machine learning model) that purportedly satisfies the agnostic PAC learning objective is verified using an interactive proof. We present a protocol for PAC verification of unions of intervals over $mathbbR$ that improves upon their proposed protocol for that task, and matches our lower bound's dependence on $d$. Our final result is a protocol for the verification of statistical algorithms that satisfy a constraint on their queries.
  arXiv  Detail & Related papers  (2022-11-28T23:57:27Z)
• 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)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  We investigate the problem dependent regime in the Thresholding Bandit problem (TBP) The objective of the learner is to output, at the end of a sequential game, the set of arms whose means are above a given threshold. We provide upper and lower bounds for the probability of error in both the concave and monotone settings.
  arXiv  Detail & Related papers  (2021-06-18T15:01:01Z)
• How Tight Can PAC-Bayes be in the Small Data Regime? [39.15172162668061]
  PAC-Bayes and test set bounds can be made for small datasets. We show that PAC-Bayes bounds are surprisingly competitive with comparable, commonly used Chernoff test set bounds. The sharpest test set bounds still lead to better guarantees on the generalisation error than the PAC-Bayes bounds we consider.
  arXiv  Detail & Related papers  (2021-06-07T12:11:32Z)
• A Limitation of the PAC-Bayes Framework [32.24251308425503]
  We present a limitation for the PAC-Bayes framework. We demonstrate an easy learning task that is not amenable to a PAC-Bayes analysis.
  arXiv  Detail & Related papers  (2020-06-24T06:36:00Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning. We show that exploration is possible using only emphbatch assumptions with an algorithm that achieves the optimal statistical rate for the setting we consider.
  arXiv  Detail & Related papers  (2020-02-29T02:02:40Z)

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.