Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote. / Wu, Yi Shan; Masegosa, Andrés R.; Lorenzen, Stephan Sloth; Igel, Christian; Seldin, Yevgeny.
Advances in Neural Information Processing Systems 34 (NeurIPS). NeurIPS Proceedings, 2021. s. 1-12.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
AU - Wu, Yi Shan
AU - Masegosa, Andrés R.
AU - Lorenzen, Stephan Sloth
AU - Igel, Christian
AU - Seldin, Yevgeny
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
M3 - Article in proceedings
SP - 1
EP - 12
BT - Advances in Neural Information Processing Systems 34 (NeurIPS)
PB - NeurIPS Proceedings
T2 - 35th Conference on Neural Information Processing Systems (NeurIPS 2021)
Y2 - 6 December 2021 through 14 December 2021
ER -
ID: 298390373