PAC-Bayes-Chernoff bounds for unbounded losses
- URL: http://arxiv.org/abs/2401.01148v3
- Date: Tue, 6 Feb 2024 10:06:22 GMT
- Title: PAC-Bayes-Chernoff bounds for unbounded losses
- Authors: Ioar Casado, Luis A. Ortega, Andr\'es R. Masegosa and Aritz P\'erez
- Abstract summary: We introduce a new PAC-Bayes oracle bound for unbounded losses.
This result can be understood as a PAC-Bayesian version of the Cram'er-Chernoff bound.
We show that our result naturally allows exact optimization of the free parameter on many PAC-Bayes bounds.
- Score: 1.9799527196428246
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We introduce a new PAC-Bayes oracle bound for unbounded losses. This result
can be understood as a PAC-Bayesian version of the Cram\'er-Chernoff bound. The
proof technique relies on controlling the tails of certain random variables
involving the Cram\'er transform of the loss. We highlight several applications
of the main theorem. First, we show that our result naturally allows exact
optimization of the free parameter on many PAC-Bayes bounds. Second, we recover
and generalize previous results. Finally, we show that our approach allows
working with richer assumptions that result in more informative and potentially
tighter bounds. In this direction, we provide a general bound under a new
``model-dependent bounded CGF" assumption from which we obtain bounds based on
parameter norms and log-Sobolev inequalities. All these bounds can be minimized
to obtain novel posteriors.
Related papers
- Closing the Gap Between the Upper Bound and the Lower Bound of Adam's
Iteration Complexity [51.96093077151991]
We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption.
Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
arXiv Detail & Related papers (2023-10-27T09:16:58Z) - More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity [27.87324770020133]
We present new high-probability PAC-Bayes bounds for different types of losses.
For losses with a bounded range, we recover a strengthened version of Catoni's bound that holds uniformly for all parameter values.
For losses with more general tail behaviors, we introduce two new parameter-free bounds.
arXiv Detail & Related papers (2023-06-21T12:13:46Z) - 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) - 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) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
We derive a novel problem-dependent lower-bound for regret in finite-horizon Markov Decision Processes (MDPs)
We show that our lower-bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all.
We show that this last result is attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.
arXiv Detail & Related papers (2021-06-24T13:46:09Z) - 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) - Tighter expected generalization error bounds via Wasserstein distance [23.52237892358981]
We introduce several expected generalization error bounds based on the Wasserstein distance.
We present full-dataset, single-letter, and random-subset bounds on both the standard setting and the randomized-subsample setting.
We show how various new bounds based on different information measures can be derived from the presented bounds.
arXiv Detail & Related papers (2021-01-22T20:13:59Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm.
We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
arXiv Detail & Related papers (2020-08-20T03:48:14Z) - Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime.
We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem.
We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
arXiv Detail & Related papers (2020-06-18T17:18:02Z) - PAC-Bayes unleashed: generalisation bounds with unbounded losses [12.078257783674923]
We present new PAC-Bayesian generalisation bounds for learning problems with unbounded loss functions.
This extends the relevance and applicability of the PAC-Bayes learning framework.
arXiv Detail & Related papers (2020-06-12T15:55:46Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
We consider the fundamental problem of ReLU regression.
The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
arXiv Detail & Related papers (2020-05-26T16:26:17Z)
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.