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

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

*Kontaktforfatter

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer 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.
OriginalsprogEngelsk
TitelAdvances in Neural Information Processing Systems (NeurIPS 2021)
Antal sider12
Vol/bind34
Publikationsdato2021
StatusUdgivet - 2021
BegivenhedThirty-fifth Conference on Neural Information Processing Systems -NeurIPS 2021 - Virtual-only Conference
Varighed: 6 dec. 202114 dec. 2021

Konference

KonferenceThirty-fifth Conference on Neural Information Processing Systems -NeurIPS 2021
LokationVirtual-only Conference
Periode06/12/202114/12/2021

Fingeraftryk

Dyk ned i forskningsemnerne om 'Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote'. Sammen danner de et unikt fingeraftryk.

Citationsformater