Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote

Yi-Shan Wu*, Andres Masegosa, Stephan Sloth Lorenzen, Christian Igel, Yevgeny Seldin

*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

Abstract

We present a new second-order oracle bound for the expected risk of a weighted majority vote. The bound is based on a novel parametric form of the Chebyshev-Cantelli inequality (a.k.a. one-sided Chebyshev’s), which is amenable to efficient minimization. The new form resolves the optimization challenge faced by prior oracle bounds based on the Chebyshev-Cantelli inequality, the C-bounds [Germain et al., 2015], and, at the same time, it improves on the oracle bound based on second order Markov’s inequality introduced by Masegosa et al. [2020]. We also derive a new concentration of measure inequality, which we name PAC-Bayes-Bennett, since it combines PAC-Bayesian bounding with Bennett’s inequality. We use it for empirical estimation of the oracle bound. The PAC-Bayes-Bennett inequality improves on the PAC-Bayes-Bernstein inequality of Seldin et al. [2012]. We provide an empirical evaluation demonstrating that the new bounds can improve on the work of Masegosa et al. [2020]. Both the parametric form of the Chebyshev-Cantelli inequality and the PAC-Bayes-Bennett inequality may be of independent interest for the study of concentration of measure in other domains.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems (NeurIPS 2021)
Number of pages12
Volume34
Publication date2021
Publication statusPublished - 2021
EventThirty-fifth Conference on Neural Information Processing Systems -NeurIPS 2021 - Virtual-only Conference
Duration: 6 Dec 202114 Dec 2021

Conference

ConferenceThirty-fifth Conference on Neural Information Processing Systems -NeurIPS 2021
LocationVirtual-only Conference
Period06/12/202114/12/2021

Bibliographical note

BFI Level 2

Keywords

  • Machine Learning
  • Ensemble Methods
  • Majority Vote
  • PAC-Bayesian

Fingerprint

Dive into the research topics of 'Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote'. Together they form a unique fingerprint.

Cite this