On the disintegration of the stochastic majority vote: from pac-bayesian bounds to a self-bounding algorithm
Abstract
Weighted majority votes are central to many successful ensemble methods. PAC-Bayesian theory provides tight generalization guarantees for such models by analyzing the expected risk of stochastic classifiers, while analyzing the risk of deterministic majority votes relies on surrogate bounds. To avoid these surrogates, Zantedeschi et al. ( 2021) introduced guarantees for stochastic majority votes, but the resulting models remain randomized. In this paper, we propose a derandomization framework for stochastic majority votes. To do so, we apply recent advances in disintegrated PAC-Bayesian theory directly to the space of majority vote weight vectors, transforming stochastic guarantees into certificates for a single deterministic majority vote. We derive two families of high-probability generalization bounds, covering both data-independent and data-dependent constructions of the ensemble, which naturally lead to a self-bounding learning algorithm optimizing deterministic majority vote guarantees.
Related
- Pre-training of Bayesian Optimization Algorithm through Bayesian Optimization
- Bagel: A Fast Bayesian Online Changepoint Detection Algorithm for Linear Models via Posterior Merging
- An Adaptive Projected-Gradient Algorithm for Sample-Average Approximations of Stochastic Multi-Objective Optimization
- A Stochastic Nested Fixed Point Algorithm for Large-Scale BLP Estimation
- A Link-Based Algorithm for Stochastic User Equilibrium with Bounded Choice and Local Detour Threshold
BibTeX
@misc{bastian2026disintegration,
title = {{On the disintegration of the stochastic majority vote: from pac-bayesian bounds to a self-bounding algorithm}},
author = {Julien Bastian and Benjamin Leblanc and Pascal Germain and Amaury Habrard and Guillaume Metzler and Emilie Morvant and Paul Viallard},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16803},
eprint = {2609.16803},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05734573v1},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - On the disintegration of the stochastic majority vote: from pac-bayesian bounds to a self-bounding algorithm
AU - Julien Bastian
AU - Benjamin Leblanc
AU - Pascal Germain
AU - Amaury Habrard
AU - Guillaume Metzler
AU - Emilie Morvant
AU - Paul Viallard
PY - 2026
DA - 2026/09/01
PB - HAL
DO - 10.48550/arxiv.2609.16803
UR - https://hal.science/hal-05734573v1
AB - Weighted majority votes are central to many successful ensemble methods. PAC-Bayesian theory provides tight generalization guarantees for such models by analyzing the expected risk of stochastic classifiers, while analyzing the risk of deterministic majority votes relies on surrogate bounds. To avoid these surrogates, Zantedeschi et al. ( 2021) introduced guarantees for stochastic majority votes, but the resulting models remain randomized. In this paper, we propose a derandomization framework for stochastic majority votes. To do so, we apply recent advances in disintegrated PAC-Bayesian theory directly to the space of majority vote weight vectors, transforming stochastic guarantees into certificates for a single deterministic majority vote. We derive two families of high-probability generalization bounds, covering both data-independent and data-dependent constructions of the ensemble, which naturally lead to a self-bounding learning algorithm optimizing deterministic majority vote guarantees.
ER -