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
stat.ML · cs.LG
Quick verdict
Derandomizes stochastic majority votes via disintegrated PAC-Bayes: sound but incremental theory; multiclass bound covers a mixture, not one model.
Summary
The paper derandomizes the stochastic majority vote framework of Zantedeschi et al. (2021). Instead of certifying the average risk of majority votes sampled from a hyper-posterior over weight vectors, the authors apply disintegrated PAC-Bayesian theorems (Rivasplata et al. 2020; Viallard et al. 2024) directly to the weight space, obtaining high-probability certificates for a single deterministic weighted majority vote drawn from the learned hyper-posterior. Two penalty forms are derived: a pointwise log-density ratio (Theorem 6) and a Renyi divergence (Theorem 7), first for data-independent voters and priors, then, via cross-bounding sample splitting following Mhammedi et al. (2019), for data-dependent voters and priors (Theorems 8-9), whose guarantee covers a tau-weighted combination of two risks. Specializing to Dirichlet distributions yields closed-form penalties and a self-bounding algorithm (Algorithm 1) that directly minimizes the bound. On 9 binary and 6 multiclass datasets, DIS-R/DIS-V yield far tighter certificates than first-order, second-order and binomial surrogate bounds (which become vacuous on PROTEIN) and stay close to stochastic majority vote bounds while certifying one deterministic model; DIS-V is the fastest method overall, though DIS-R is slowest on three binary datasets. Limitations: the proofs are direct plug-ins of existing theorems, the multiclass certificate concerns a mixture of two risks rather than the deployed predictor, training optimizes a sigmoid surrogate of the 0-1 loss, and no code release is mentioned.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 2
● low 3
4 strengths · 5 weaknesses · 5 author questions
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Applying disintegrated PAC-Bayesian theorems directly to the majority-vote weight space yields high-probability generalization certificates for a single deterministic weighted majority vote drawn from the learned hyper-posterior (Theorems 6-7), extendable to data-dependent voters and priors via cross-bounding sample splitting (Theorems 8-9).
- These bounds admit closed-form Dirichlet instantiations and a self-bounding learning algorithm (Algorithm 1, Eqs. 14-17) that directly minimizes the certificate.
- Empirically the disintegrated certificates are substantially tighter than first-order, second-order and binomial surrogate bounds and remain close to stochastic majority vote bounds while certifying a deterministic model (Tables 3 and 5).
- The disintegrated approach trains faster than the stochastic majority vote, especially DIS-V, which is the fastest method on all 15 datasets (Tables 7-8).
Strengths
Clean, verifiable reduction
The idea of disintegrating one level higher, over weight vectors rather than voters, is well-motivated; I verified the Renyi-Dirichlet expression Eq. 12 against the definition (including the condition alpha_j > (lambda-1)/lambda * beta_j), the joint-convexity step in Appendix A, and the constants in Corollaries 3-4 (ln 8n/delta^2, ln 2n) - all correct.
Two complementary penalties with honest trade-off analysis
Section 4.1 contrasts the pointwise density-ratio penalty (Theorem 6, tighter but harder to optimize) with the Renyi penalty (Theorem 7, tractable); the experiments confirm DIS-R yields tighter bounds than DIS-V on essentially all datasets (Tables 3, 5), as theory predicts.
Thorough, transparent experiments
Practical speed and non-vacuity where surrogates fail
Weaknesses
Incremental theoretical novelty
Multiclass certificate covers a mixture, not a single model
Optimization-certificate mismatch
Bound-to-risk gap remains large on hard datasets
Runtime claim not uniform and no code release
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a disintegrated PAC-Bayesian bound?
Classical PAC-Bayes bounds control the average risk of a stochastic (Gibbs) classifier that samples a model from a learned posterior. Disintegrated bounds move the randomness outside the probability statement: they certify the risk of one specific model drawn from that posterior, replacing the KL divergence penalty with a pointwise density ratio or a Renyi divergence. This paper applies that idea to distributions over majority-vote weight vectors, so a single deterministic weighted majority vote gets its own generalization certificate.
How does this paper improve on the stochastic majority vote of Zantedeschi et al. 2021?
Zantedeschi et al. certify the expected risk of majority votes sampled from a Dirichlet hyper-posterior, so the deployed predictor stays randomized (a new weight vector per prediction). This paper derives high-probability certificates for one sampled deterministic majority vote instead. Empirically the certificates are slightly looser than the stochastic ones (e.g., 5.95 vs 4.68 bound value on MUSHROOMS) but apply to a fixed model, and training is faster (DIS-V is the fastest method on all 15 datasets).
Are the generalization certificates in this paper non-vacuous?
Partly. On easy datasets the gap to the test error is moderate (MUSHROOMS: bound 5.95% vs test error 1.93% for DIS-R). On harder ones the bounds are weak: on TICTACTOE the best disintegrated bound is about 45.6% against a 29.9% test error, and on PROTEIN every method's bound is near 59% against roughly 55% test error, while the classical first-order, second-order and binomial surrogate bounds all exceed 100% (vacuous).
Is code available for this paper?
The paper does not mention a code or data release. The experimental protocol is documented in unusual detail (hyperparameters, voter constructions, splits), and the datasets are public (UCI, LIBSVM, Fashion-MNIST), so independent reimplementation is feasible, but exact-number replication currently depends on it.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1-2 are bar plots; visual tightness/runtime patterns were judged from the numerical Tables 3-8 rather than the figures
- The embedded text appears complete (Sections 1-7 plus Appendices A-C and all tables); no evident truncation
- The deployed predictor for the multiclass data-dependent setting is never stated in the text, so the interpretation of Table 6 test errors is inferred
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.