Timezone: »
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.
Author Information
Yi-Shan Wu (University of Copenhagen)
Andres Masegosa (Aalborg University)
Stephan Lorenzen (University of Copenhagen)
Christian Igel (University of Copenhagen)
Yevgeny Seldin (University of Copenhagen)
More from the Same Authors
-
2022 Poster: A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs »
Chloé Rouyer · Dirk van der Hoeven · Nicolò Cesa-Bianchi · Yevgeny Seldin -
2022 Poster: Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables »
Yi-Shan Wu · Yevgeny Seldin -
2022 Poster: A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback »
Saeed Masoudian · Julian Zimmert · Yevgeny Seldin -
2020 Poster: Learning under Model Misspecification: Applications to Variational and Ensemble methods »
Andres Masegosa -
2020 Poster: A Loss Function for Generative Neural Networks Based on Watson’s Perceptual Model »
Steffen Czolbe · Oswin Krause · Ingemar Cox · Christian Igel -
2020 Poster: Second Order PAC-Bayesian Bounds for the Weighted Majority Vote »
Andres Masegosa · Stephan Lorenzen · Christian Igel · Yevgeny Seldin -
2020 Spotlight: Second Order PAC-Bayesian Bounds for the Weighted Majority Vote »
Andres Masegosa · Stephan Lorenzen · Christian Igel · Yevgeny Seldin -
2019 Poster: U-Time: A Fully Convolutional Network for Time Series Segmentation Applied to Sleep Staging »
Mathias Perslev · Michael Jensen · Sune Darkner · Poul Jørgen Jennum · Christian Igel -
2019 Poster: Nonstochastic Multiarmed Bandits with Unrestricted Delays »
Tobias Sommer Thune · Nicolò Cesa-Bianchi · Yevgeny Seldin -
2016 Poster: CMA-ES with Optimal Covariance Update and Storage Complexity »
Oswin Krause · Dídac Rodríguez Arbonès · Christian Igel