On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithm

• URL: http://arxiv.org/abs/2609.16803v1
• Date: Tue, 15 Sep 2026 08:08:42 GMT
• Title: On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithm
• Abstract summary: PAC-Bayesian theory provides generalization guarantees for weighted majority votes.<n>We propose a derandomization framework for majority votes, transforming guarantees into certificates for a single deterministic majority vote.
• Score: 8.44966073503768
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 papers

• Beyond Majority Voting: Efficient Best-Of-N with Radial Consensus Score [13.41454380481593]
  Radial Consensus Score (RCS) is a simple, efficient, and training-free method for best-of-N selection.<n>RCS models semantic consensus by computing a weighted Fréchet mean (semantic center) of answer embeddings and ranking candidates by their radial distance to this center.
  arXiv  Detail & Related papers  (2026-04-14T02:02:20Z)
• A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes [4.664367264604233]
  PAC-Bayes is a popular framework for obtaining generalization guarantees in uncountable hypothesis spaces.<n>We propose a unified framework to extract guarantees holding for a single hypothesis from PAC-Bayesian guarantees.
  arXiv  Detail & Related papers  (2025-10-29T14:38:35Z)
• Generating Fair Consensus Statements with Social Choice on Token-Level MDPs [7.5036512760759715]
  We model the task as a multi-objective, token-level Markov Decision Process (MDP)<n> Token-level rewards for each agent are derived from their policy (e.g., a personalized language model)<n>This approach utilizes the finding that such policies implicitly define optimal Q-functions, providing a principled way to quantify rewards at each generation step without a value function.
  arXiv  Detail & Related papers  (2025-10-15T21:23:18Z)
• Beyond Majority Voting: LLM Aggregation by Leveraging Higher-Order Information [57.397381631496906]
  We develop two new aggregation algorithms called Optimal Weight (OW) and Inverse Surprising Popularity (ISP)<n>Our theoretical analysis shows these methods provably mitigate inherent limitations of majority voting under mild assumptions.<n>We empirically validate our algorithms on synthetic datasets, popular LLM fine-tuning benchmarks such as UltraFeedback and MMLU, and a real-world healthcare setting ARMMAN.
  arXiv  Detail & Related papers  (2025-10-01T22:21:50Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Bounded Rationality for LLMs: Satisficing Alignment at Inference-Time [52.230936493691985]
  We propose SITAlign, an inference framework that addresses the multifaceted nature of alignment by maximizing a primary objective while satisfying threshold-based constraints on secondary criteria.<n>We provide theoretical insights by deriving sub-optimality bounds of our satisficing based inference alignment approach.
  arXiv  Detail & Related papers  (2025-05-29T17:56:05Z)
• Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound [15.557653926558638]
  We investigate a counterpart of majority votes over finite ensembles of classifiers, and study its generalization properties. We instantiate it with Dirichlet distributions: this allows for a closed-form and differentiable expression for the expected risk. The resulting majority vote learning algorithm achieves state-of-the-art accuracy and benefits from (non-vacuous) tight bounds.
  arXiv  Detail & Related papers  (2021-06-23T16:57:23Z)
• Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Bound [0.0]
  We derive self-bounding majority vote learning algorithms based on PAC-Bayesian guarantees on the C-Bound. Our algorithms are scalable and lead to accurate predictors paired with non-vacuous guarantees.
  arXiv  Detail & Related papers  (2021-04-28T08:23:18Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  We investigate multi-armed bandit with semi-bandit feedback (CMAB) We analyze variants of the Combinatorial Thompson Sampling policy (CTS) This last result gives us an alternative to the Efficient Sampling for Combinatorial Bandit policy (ESCB)
  arXiv  Detail & Related papers  (2020-06-11T17:12:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.