PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales

• URL: http://arxiv.org/abs/2210.00928v2
• Date: Mon, 24 Apr 2023 16:00:01 GMT
• Title: PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
• Authors: Maxime Haddouche and Benjamin Guedj
• Abstract summary: We contribute PAC-Bayes generalisation bounds for heavy-tailed losses. Our key technical contribution is exploiting an extention of Markov's inequality for supermartingales. Our proof technique unifies and extends different PAC-Bayesian frameworks.
• Score: 5.799808780731661
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: While PAC-Bayes is now an established learning framework for light-tailed losses (\emph{e.g.}, subgaussian or subexponential), its extension to the case of heavy-tailed losses remains largely uncharted and has attracted a growing interest in recent years. We contribute PAC-Bayes generalisation bounds for heavy-tailed losses under the sole assumption of bounded variance of the loss function. Under that assumption, we extend previous results from \citet{kuzborskij2019efron}. Our key technical contribution is exploiting an extention of Markov's inequality for supermartingales. Our proof technique unifies and extends different PAC-Bayesian frameworks by providing bounds for unbounded martingales as well as bounds for batch and online learning with heavy-tailed losses.

Related papers

• 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)
• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner. We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
  arXiv  Detail & Related papers  (2024-08-12T17:08:31Z)
• A note on generalization bounds for losses with finite moments [28.102352176005514]
  The paper derives a high-probability PAC-Bayes bound for losses with a bounded variance. It extends results to guarantees in expectation and single-draw PAC-Bayes.
  arXiv  Detail & Related papers  (2024-03-25T12:15:55Z)
• 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)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59: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)
• PAC$^m$-Bayes: Narrowing the Empirical Risk Gap in the Misspecified Bayesian Regime [75.19403612525811]
  This work develops a multi-sample loss which can close the gap by spanning a trade-off between the two risks. Empirical study demonstrates improvement to the predictive distribution.
  arXiv  Detail & Related papers  (2020-10-19T16:08:34Z)
• Distribution-Balanced Loss for Multi-Label Classification in Long-Tailed Datasets [98.74153364118898]
  We present a new loss function called Distribution-Balanced Loss for the multi-label recognition problems that exhibit long-tailed class distributions. The Distribution-Balanced Loss tackles these issues through two key modifications to the standard binary cross-entropy loss. Experiments on both Pascal VOC and COCO show that the models trained with this new loss function achieve significant performance gains.
  arXiv  Detail & Related papers  (2020-07-19T11:50:10Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
  arXiv  Detail & Related papers  (2020-06-26T12:37:17Z)
• 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)

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.