CS Paper Radar

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

Julien Bastian, Benjamin Leblanc, Pascal Germain, Amaury Habrard, Guillaume Metzler, Emilie Morvant, Paul Viallard

cs.LG stat.ML ·submitted 2026-09-15 08:08 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Calibration of Crowdsourcing Aggregators

cs.LG stat.ML ·2026-10-12 ·Gabriel Singer, Reda Arab, Maïssa Frikha, Samuel Gruffaz, Olivier Vo Van +2 more
theory similarity 0.62
Abstract

Calibration has been extensively studied for classifiers, but remains largely unexplored for crowdsourcing aggregation methods, which are increasingly used for making probabilistic decisions. To the best of our knowledge, we provide the first theoretical and empirical study of calibration in label aggregation. To our great surprise, we find that widely used aggregation methods can be severely miscalibrated, and in opposite directions: Majority Vote is underconfident while model-based aggregators are overconfident. We prove that the Bayesian aggregator is perfectly calibrated under its data-generating model. We also show that exact calibration of weighted majority votes requires highly restrictive conditions, which helps explain why Majority Vote is generally miscalibrated in realistic crowds. Empirically, we study calibration across $39$ human crowdsourcing datasets and LLM-based crowds. In both cases, we observe systematic miscalibration for aggregation models such as Majority Vote, Dawid--Skene, GLAD, and CrowdFM. Finally, we propose a post-hoc calibration procedure that \emph{aggregates the aggregators}: for any aggregation function $φ$, we introduce a transformation that first combines its predictive distribution with those of complementary aggregators, before applying temperature scaling. This simple and interpretable transformation makes temperature scaling more effective than when applied directly to $φ$. It improves calibration, especially in the high-redundancy regime where there are many annotations per item, while generally preserving or even improving accuracy.

0.31

Margin Certificates for Voting Classifiers under Mixing Dependence

cs.LG math.STstat.ML ·2026-10-16 ·Adria Binte Habib, Ibne Farabi Shihab
theory similarity 0.61
Abstract

Margin bounds explain why weighted votes generalize after training error vanishes, but dependent observations require concentration arguments that keep the dependence model and failure budget explicit. We study stationary mixing streams without treating dependence as a formal substitution of an "effective sample size." For a finite base class, we combine independent-block Rademacher theory for stationary $β$-mixing processes with a clipped margin loss to obtain an explicit uniform voting-margin certificate, whose dependence penalty is set by the number of approximately independent blocks and the coupling budget $4(μ-1)β(a)$. A black-box transfer theorem shows that any i.i.d. voting-margin guarantee remains valid on a regularly spaced subsequence, with only an additive $β$-mixing failure probability. For votes fixed independently of a stationary finite-state reversible Markov stream, spectral concentration gives the cleaner $\sqrt{t_{rel}/n}$ rate, and a sticky-refresh construction shows this exponent is unavoidable. The constant is statistic-specific: the effective sample size is $n/τ_{int}(g)$, with $τ_{int}(g) \le 2t_{rel}-1$. When the dependence scale is unknown, a batch-means Student-t interval is valid up to an explicit remainder vanishing in the number of batches, with width governed by $τ_{int}(g)$ rather than the worst-case $t_{rel}$. Experiments show: the learned-vote certificate is nonvacuous once the block count is large; a two-timescale construction gives a batch-means interval 8.1x narrower than the worst-case interval at nominal coverage (0.945); block-bootstrap and batch-means intervals undercover under strong dependence while the certificate stays valid; and on real, ordered UCI HAR sensor data the dependence-agnostic certificate reaches 0.95 coverage where naive intervals reach only 0.38.

0.23

Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules

cs.GT ·2026-08-15 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.59
Abstract

In metric social choice, voters and candidates lie in a common but unknown metric space, voters rank candidates by distance, and a voting rule seeks to minimize total distance to the voters. Its distortion is the worst-case approximation ratio relative to the minimum possible total distance. We study weighted-tournament rules (also known as C2 rules), which observe only the fraction of voters who prefer $a$ to $b$ for each pair of candidates $a,b$. These frequencies form a weighted tournament on candidates, a compressed representation that omits voter identities and the association of comparisons with individual voters. Prior work placed the optimal distortion of deterministic C2 rules between $3.1128$ and $3.9312$ [Charikar et al., EC 2025]. We introduce the Path-Unblanketed Set rule, a polynomial-time deterministic C2 rule with distortion at most $1+2\sqrt{2}\approx3.8284$ for every finite number of candidates. For elections with no more than six candidates, we prove with computer assistance that the distortion is at most $3.3346$. Furthermore, using an exact computer-assisted certificate, we provide a lower bound of $3.1828$ for deterministic C2 rules as a byproduct.

0.32

Decisive Margins in Differentially Private Voting

cs.DS cs.CR ·2026-08-19 ·Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn, Phanu Vajanopath
theory similarity 0.58
Abstract

Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close. We study how precise central differential privacy and local differential privacy can be for common voting rules, including Plurality, Condorcet, Maximin, Plurality with Runoff, and Single Transferable Vote (STV). Our measure of precision is the margin of victory needed for a private mechanism to return the same winner as the non-private rule with high probability. We give private algorithms for publishing the winner and prove upper bounds on the required margin for these algorithms. We also prove lower bounds showing that nontrivial margins are necessary; many of these bounds match the corresponding upper bounds up to logarithmic factors. For STV, an information-theoretic upper bound matches the lower bound, but we prove that this guarantee cannot be achieved in polynomial time unless NP $\subseteq$ BPP. This gives a rare example of a computationally tractable task that becomes intractable when one simultaneously requires differential privacy and utility.

0.41

Exact power indices for plurality-voting ensembles

cs.LG cs.DScs.GT ·2026-10-13 ·Ilie Sarpe, Theofanis Georgakopoulos, Aristides Gionis
top venue similarity 0.58
Abstract · Extended version of a work accepted at NeurIPS 2026. 59 pages, 9 figures, 11 tables

Plurality-voting ensembles aggregate the predictions of multiple base classifiers and output the most voted class, with ties typically broken at random. Despite the simple aggregation rule, attributing the impact of each base classifier to the ensemble's predictions is far from straightforward. That is, a single base classifier's impact depends on how it interacts with the votes of all other classifiers in the ensemble, for example, in resolving ties, and not only on its own predictions. We address the attribution problem using established tools from cooperative game theory, studying the Banzhaf and Shapley power indices for new games modeling plurality voting and random tie-breaking, for binary and multiclass classification settings. Computing power indices is, in general, intractable. Surprisingly, our methods, collectively named ENPOWER, enable the exact computation of Banzhaf and Shapley values in linear time for the binary classification setting and in low-degree polynomial time for the multiclass setting. The algorithms in ENPOWER rely on new combinatorial formulations of the Banzhaf and Shapley indices, yielding closed-form solutions for the binary case and ordinary generating function representations for the multiclass case. We validate empirically the methods in ENPOWER demonstrating their high applicability, providing attribution values not captured by existing methods. We apply the attribution of ENPOWER to: ensemble pruning and prompt-based ensembling of vision-language models.

0.40

Stable Voting Rules on the Edge of Optimal Metric Distortion

cs.GT ·2026-09-08 ·Ziyi Cai, Fabian Frank, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang +1 more
theory similarity 0.57
Abstract

We prove the existence of a randomized voting rule with metric distortion at most $2.1248$, within $0.013$ of the lower bound of $2.11264$. Our rule comes from a generalization of \emph{stable $k$-lotteries} developed in the context of committee selection. In contrast to prior work, our rule samples from a single distribution derived from a zero-sum game, without mixing between voting rules. Our result also gives sharp distortion bounds for stable $k$-lotteries. In particular we show that stable $2$-lotteries have distortion $7/3$, despite only relying on aggregate preferences over triples of candidates, and that stable $2$-lotteries are optimal in this class of voting rules.

0.37

The Distortion of Threshold Approval Multiwinner Voting

cs.GT ·2026-10-09 ·Mohamad Latifian, Marzieh Nilipour, Alexandros A. Voudouris
similarity 0.57
Abstract

We study multiwinner voting with $n$ voters and $m$ candidates, where the goal is to select a committee of size $k$. Voters have unit-sum cardinal utilities but report only coarse information induced by $t$ utility thresholds. In particular, each voter partitions the candidates into approval sets, with the utilities of all candidates in the same set lying between the same pair of consecutive thresholds. We model the utility of each voter for a committee as a normalized monotone symmetric norm, capturing, among others, additive welfare, best-representative utility, top-$r$ welfare, $\ell_p$ welfare, and normalized non-increasing ordered weighted averages. We design a deterministic rule with distortion at most $2(2m)^{1/t}$ and a randomized rule with distortion at most $2\min\{m^{1/(t+1)},m/k\}$. These guarantees hold for every committee size $k$ and every norm in our framework. Consequently, a single threshold yields distortion $O(m)$ for deterministic rules and $O(\sqrt{m})$ for randomized rules, while $O(\log m)$ thresholds suffice for constant distortion. We complement these results with norm-dependent lower bounds that asymptotically match our upper bounds for constant committee sizes, including the single-winner case.

0.18

A Generalized McDiarmid Inequality: Sample Reuse and Non-Uniform Unbounded Differences

cs.LG stat.ML ·2026-10-12 ·Jeremiah Birrell
similarity 0.57
Abstract · 20 pages

We develop a novel generalization of McDiarmid's concentration inequality and use it to obtain a uniform law of large numbers result and error bounds on stochastic optimization problems which simultaneously incorporate two key features: 1) They capture the benefit of training sample reuse in algorithms that also employ easily-sampled auxiliary random variables. 2) They allow for one-component mean-difference bounding functions which are both unbounded in the component of interest and have non-uniform dependence on another component. We demonstrate the utility of our method by deriving concentration inequalities for score-based generative modeling. This application naturally leverages both key features of our new tools: 1) It utilizes auxiliary Gaussian random variables in conjunction with the training samples; accounting for training sample reuse results in tighter error bounds by effectively integrating out the dependence on the auxiliary random variables. 2) The ability to handle non-uniform mean-difference bounding functions allows us to treat unbounded score models and data distributions with unbounded support.

0.28