← Back to all news
arXiv Machine Learning

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

The paper introduces a derandomization framework for stochastic majority vote classifiers, converting PAC‑Bayesian guarantees into deterministic majority vote guarantees. By applying disintegrated PAC‑Bayesian theory to the space of vote weight vectors, the authors derive two families of high‑probability generalization bounds for both data‑independent and data‑dependent ensembles. These bounds naturally lead to a self‑bounding learning algorithm that optimizes deterministic majority vote performance.

Related stories

arXiv AI
Oct 2

Query-efficient winner prediction in district-based elections

The paper studies how to predict the winner of a district‑based election using as few queries to individual votes as possible. It introduces an adaptive randomized algorithm that, for any number of candidates and any error tolerance, correctly predicts the overall winner with probability at least 1‑δ using ≥O(1/ε² log m/δ log 1/δ) queries. This improves previous results for two candidates and balanced districts, and nearly matches a proven lower bound for constant‑size candidate sets.

By Koustav De, Debajyoti Kar, Swagato Sanyal
More like this →
Hugging Face Trending Papers
Jun 17

Smoothness-Based Derandomization of PAC-Bayes Bounds

We study PAC-Bayes derandomization for smooth loss functions. Our goal is to obtain generalization bounds that hold with high probability for deterministic predictors by exploiting smoothness properties of both the loss and the predictor class.

More like this →
arXiv Machine Learning
Jul 30

Tight Generalization Bound for AdaBoost

arXiv:2607. 26838v1 Announce Type: new Abstract: In this paper we show that the generalization error of AdaBoost is $\Theta\big(\tfrac{d\ln(n\gamma^{2}/d)}{n\gamma^2}+\tfrac{\ln(1/\delta)}{n}\big)$, where $\gamma$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample size, and $\delta$ is the confidence parameter.

By Mikael M{\o}ller H{\o}gsgaard
More like this →
arXiv AI
Aug 19

A decodability criterion predicts when hidden-state selection beats majority voting in large language models

The paper introduces CASE, a dynamic selection combiner that uses a linear gate trained on answer-token hidden states to choose the best candidate answer from a large language model’s samples. It proposes decodability, a leakage‑free metric that predicts when hidden‑state selection will outperform majority voting, achieving a strong correlation (r=0.75) with accuracy gains. CASE improves accuracy by up to 19 points on medium‑difficulty and 16.8 points on hard questions across general and medical LLMs, and its predictive power transfers to unseen scientific domains.

By Zhixiang wang, Ziliang Hong, Ulas Bagci
llms
More like this →