A Limitation of the PAC-Bayes Framework

• URL: http://arxiv.org/abs/2006.13508v3
• Date: Fri, 3 Sep 2021 08:07:45 GMT
• Title: A Limitation of the PAC-Bayes Framework
• Authors: Roi Livni and Shay Moran
• Abstract summary: We present a limitation for the PAC-Bayes framework. We demonstrate an easy learning task that is not amenable to a PAC-Bayes analysis.
• Score: 32.24251308425503
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: PAC-Bayes is a useful framework for deriving generalization bounds which was introduced by McAllester ('98). This framework has the flexibility of deriving distribution- and algorithm-dependent bounds, which are often tighter than VC-related uniform convergence bounds. In this manuscript we present a limitation for the PAC-Bayes framework. We demonstrate an easy learning task that is not amenable to a PAC-Bayes analysis. Specifically, we consider the task of linear classification in 1D; it is well-known that this task is learnable using just $O(\log(1/\delta)/\epsilon)$ examples. On the other hand, we show that this fact can not be proved using a PAC-Bayes analysis: for any algorithm that learns 1-dimensional linear classifiers there exists a (realizable) distribution for which the PAC-Bayes bound is arbitrarily large.

Related papers

• 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)
• Better-than-KL PAC-Bayes Bounds [23.87003743389573]
  We show that it is possible to achieve a strictly tighter bound with a novel and better-than-KL divergence. Our result is first-of-its-kind in that existing PAC-Bayes bounds with non-KL divergences are not known to be strictly better than KL.
  arXiv  Detail & Related papers  (2024-02-14T14:33:39Z)
• 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)
• 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)
• 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)
• 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)
• A General Framework for the Practical Disintegration of PAC-Bayesian Bounds [2.516393111664279]
  We introduce new PAC-Bayesian generalization bounds that have the originality to provide disintegrated bounds. Our bounds are easily optimizable and can be used to design learning algorithms.
  arXiv  Detail & Related papers  (2021-02-17T09:36:46Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)

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.