PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.16803v1stat.MLcs.LG

TL;DR

Classical PAC-Bayesian analyses generally certify stochastic classifiers, while deterministic majority votes require surrogate bounds and stochastic majority vote methods remain randomized. The paper applies disintegrated PAC-Bayes directly to majority-vote weight vectors, producing deterministic certificates and a self-bounding optimization procedure. Empirically, it yields tighter certificates than classical surrogate approaches while remaining competitive with stochastic majority votes.

  • Problem

    Classical PAC-Bayesian bounds certify posterior-average risk, deterministic majority-vote analyses use imprecise surrogates, and stochastic majority votes still require randomized prediction.

  • Method

    The paper applies disintegrated PAC-Bayesian theory to the hyper-posterior over majority-vote weight vectors and directly optimizes the resulting deterministic guarantees.

  • Results

    The approach produces deterministic majority votes with competitive accuracy and certificate tightness, requires less training time than stochastic majority votes, and substantially improves classical surrogate-based bounds.

  • Takeaways & Limitations

    Disintegrated PAC-Bayes can transform stochastic guarantees into certificates for a single deterministic majority vote while retaining self-bounding learning.

  • Takeaways & Limitations

    The stochastic-majority-vote comparison still certifies a randomized predictor, whereas the paper’s framework is designed to derandomize this setting.

Abstract

from arXiv · show

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.

1 Introduction

Weighted majority votes are established ensemble methods whose PAC-Bayesian analysis primarily controls stochastic classifiers. This paper extends stochastic majority vote guarantees through disintegrated PAC-Bayes to obtain optimizable deterministic certificates and a self-bounding algorithm.

  • Weighted majority votes exploit voter diversity and underpin ensemble methods including Bagging, random forests, and boosting.
  • Classical PAC-Bayesian bounds control weighted-average voter risk, equivalent to the expected risk of the associated stochastic Gibbs classifier.These bounds can also directly induce learning algorithms that minimize generalization guarantees.
  • Zantedeschi et al. shift randomization from individual voters to weight vectors, producing stochastic majority votes defined over the vote-weight space.A Dirichlet distribution models weights on the simplex while preserving tractability.
  • The paper applies disintegrated PAC-Bayesian theory to majority-vote weights, yielding deterministic majority votes, self-bounding optimization, and competitive certificates.The framework is presented as a contribution developed into a self-bounding algorithm and empirical evaluation.

2 Basics on PAC-Bayesian Theory

PAC-Bayesian theory relates empirical and true risks through posterior-weighted guarantees, while disintegrated bounds provide guarantees for a single sampled model. These results motivate learning a posterior, deploying one model, and certifying its generalization with high probability.

  • 2.1 Classical PAC-Bayesian Bounds: PAC learning bounds relate empirical risk to true risk through a high-probability generalization gap.The desired deviation should be as small as possible.
  • 2.1 Classical PAC-Bayesian Bounds: PAC-Bayes analyzes a stochastic Gibbs classifier by sampling hypotheses from a learned posterior over voters, alongside a prior encoding knowledge before observing data.Classical bounds can recover different forms through suitable choices of the deviation function and include a KL penalty between posterior and prior.
  • 2.1 Classical PAC-Bayesian Bounds: The general PAC-Bayesian theorem applies to any posterior and measurable function, with guarantees penalized by the KL divergence between posterior and prior.The framework supports bounds controlling empirical-to-true risk gaps through an appropriate function choice.
  • 2.2 Disintegrated PAC-Bayesian Bounds: Disintegrated PAC-Bayes moves the posterior expectation outside the probability statement, giving high-probability guarantees for one model sampled from the learned posterior.Its penalty uses a density-ratio form, while an alternative theorem uses Rényi divergence.
  • 2.2 Disintegrated PAC-Bayesian Bounds: The resulting procedure learns a posterior from data, samples one model for deployment, and obtains a high-probability guarantee for that deterministic model.This provides a derandomization route relative to expectation-based posterior guarantees.

3 PAC-Bayes for Majority Vote

PAC-Bayesian analyses of deterministic majority votes traditionally use surrogates because direct risk analysis is difficult, while stochastic majority votes provide direct guarantees but remain randomized. The weight-space formulation shifts randomization to majority-vote weights, enabling direct PAC-Bayesian analysis and motivating derandomization.

  • Deterministic weighted majority vote: Deterministic majority-vote guarantees commonly rely on surrogates because the vote’s non-differentiable aggregation makes its risk difficult to analyze directly.The factor-two, binomial, second-order, and C-bound approaches relate majority-vote risk to voter-risk, sampling, joint-error, or disagreement quantities.
  • Deterministic weighted majority vote: The factor-two surrogate becomes uninformative above voter risk 1/2 and does not exploit voter diversity or error correlations.It is close to zero only when the stochastic classifier’s risk is also close to zero.
  • Deterministic weighted majority vote: The joint-error surrogate becomes uninformative when E_D(ρ) exceeds 1/4, despite reflecting the value of diverse and complementary voter errors.The C-bound additionally incorporates disagreement to account for voter diversity explicitly.
  • PAC-Bayesian stochastic majority vote: Zantedeschi et al. shift PAC-Bayesian randomization from individual voters to weight vectors, so sampling a weight vector samples an entire deterministic majority vote.A hyper-posterior Q over the weight space yields a stochastic predictor with true risk E_ρ∼Q R_D(MV_ρ).
  • PAC-Bayesian stochastic majority vote: Dirichlet distributions make the stochastic majority-vote objective tractable in binary classification, but the certified predictor remains stochastic at prediction time.The expected 0-1 loss has a closed form, enabling direct optimization of a PAC-Bayesian bound; prediction still requires sampling ρ∼Q for each data point.

4 Disintegrated stochastic majority vote

The paper applies disintegrated PAC-Bayesian theory to majority-vote weight vectors, yielding high-probability guarantees for a single deterministic majority vote. It develops bounds for both data-independent and sample-split data-dependent voters and priors.

  • 4 Disintegrated stochastic majority vote: Disintegration over majority-vote weights converts stochastic guarantees into a high-probability risk certificate for one sampled deterministic majority vote.Each weight vector directly defines a deterministic classifier MV_ρ, so the bound controls RD(MV_ρ) rather than an expectation over majority votes.
  • 4.1 Data-Independent Base Voters and Priors: The data-independent setting fixes the voter set, weight space, and hyper-prior independently of the learning data, producing two disintegrated bounds.Theorem 6 uses a pointwise density-ratio penalty, while Theorem 7 uses a Rényi divergence between the full hyper-posterior and hyper-prior.
  • 4.1 Data-Independent Base Voters and Priors: Theorem 6 can yield a tighter certificate through a sampled-vector density ratio, whereas Theorem 7 offers a more stable and tractable distribution-level optimization penalty.The pointwise penalty depends only on the sampled ρ; the Rényi penalty does not depend on a particular sampled weight vector.
  • 4.2 Data-Dependent Base Voters and Priors: Theorems 8 and 9 extend disintegrated guarantees to data-dependent constructions, with Theorem 9 using a Rényi-based penalty.The resulting guarantee applies to a convex combination of risks of two sampled majority votes drawn from independent data splits.
  • 4.2 Data-Dependent Base Voters and Priors: Sample splitting enables data-dependent voters and hyper-priors while preserving PAC-Bayesian validity through cross-evaluation on independent complementary subsets.Each split learns voters, weight space, and hyper-prior from the other split, then evaluates the resulting majority vote on the held-out subset.

5 Optimization Algorithm

The bounds become trainable objectives for a self-bounding procedure that learns a Dirichlet hyper-posterior and outputs a deterministic majority vote. Training evaluates sampled-vote empirical risk rather than the expected risk over all majority votes.

  • 5 Optimization Algorithm: The disintegrated bounds serve as optimization objectives, making the generalization guarantee itself the target of a self-bounding learning procedure.Each theorem induces a specific objective B(α; S, P, δ) parameterized by the Dirichlet hyper-posterior.
  • 5 Optimization Algorithm: The practical instantiation uses Dirichlet hyper-priors and hyper-posteriors over simplex-constrained majority-vote weight vectors.The simplex contains nonnegative weight vectors summing to one, and α parameterizes the learned Dirichlet hyper-posterior.
  • 5 Optimization Algorithm: Algorithm 1 samples weights, builds a deterministic majority vote, computes minibatch empirical risk and the self-bounding objective, then updates α by gradient descent.After training, a final sampled ρ defines the deterministic classifier used at prediction time.
  • 5 Optimization Algorithm: The procedure is computationally cheaper than stochastic-majority-vote training because it evaluates one drawn vote instead of approximating an expected empirical risk.The stochastic expected risk involves an indefinite integral requiring integration estimation or Monte Carlo, whereas a drawn vote’s empirical risk is straightforward.

6 Experiments

The experiments compare disintegrated and stochastic majority-vote methods with classical surrogate-based PAC-Bayesian approaches across binary and multiclass datasets. Direct-risk methods achieve comparable test errors but substantially tighter bounds, while disintegrated objectives generally reduce training time.

  • Experimental setup: The evaluation averages results over 10 independent runs and reports standard deviations for bounds, test errors, and training times.Binary and multiclass classification datasets are drawn from UCI, LIBSVM, and Fashion-MNIST, with Adam optimization and early stopping.
  • Results—Test error and bound tightness: DIS-R, DIS-V, SMV-EXACT, and SMV-MC achieve comparable test errors while producing substantially tighter bounds than FO, SO, and BIN across datasets.Classical surrogate-based bounds become vacuous on PROTEIN.
  • Results—Test error and bound tightness: SMV-EXACT and SMV-MC yield the tightest bounds overall, while DIS-R outperforms them on SPLICE and DIS-R is consistently tighter than DIS-V.The stochastic methods certify expected risk, whereas DIS-R and DIS-V certify a single deterministic majority vote.
  • Results—Training times: DIS-V trains faster than SMV-EXACT and SMV-MC on every dataset, while DIS-R is faster on most datasets but slowest on MUSHROOMS, PHISHING, and SPLICE.The disintegrated objectives optimize one sampled majority vote per mini-batch rather than approximating an expectation with Monte Carlo samples.

7 Conclusion

The paper introduces the first disintegrated PAC-Bayesian framework for stochastic majority votes, converting stochastic guarantees into certificates for a single deterministic weighted vote. It also shows that this perspective extends to higher-level parameter randomness and suggests broader self-bounding applications.

  • 7 Conclusion: The framework directly certifies the true risk of deterministic majority votes instead of relying on classical surrogate quantities.It applies disintegrated PAC-Bayesian theorems to majority-vote weight vectors and supplies a self-bounding algorithm.
  • 7 Conclusion: The method transforms stochastic majority-vote guarantees into guarantees for a single sampled deterministic weighted majority vote.The empirical results are significantly tighter than classical surrogate-based approaches, competitive with stochastic majority votes, and generally require less training time.
  • 7 Conclusion: Disintegrated PAC-Bayesian bounds can extend to higher stochasticity levels where randomness acts on an entire final-predictor parameterization rather than an individual voter.The paper identifies latent representations, architectures, and other high-level model parameters as possible future targets.

A Proofs of the main results

The proofs use a cross-bounding construction that creates each voter and hyper-prior system from the opposite data subset. This independence permits separate bounds on each subset before combining them.

  • A Proofs of the main results: The cross-bounding argument constructs H1, W1, and P1 from S2, and H2, W2, and P2 from S1, making each construction independent of the subset it bounds.The corresponding data-independent bound is applied conditionally to the other subset with confidence parameter δ/2.
  • A Proofs of the main results: The two conditional guarantees are combined through a union bound and the joint distribution of the data subsets.

A.1 Proof of Theorem 8

The data-dependent results split the sample into two subsets, construct each ensemble from the opposite subset, and apply disintegrated bounds conditionally. Dirichlet specializations then provide computable objectives for self-bounding optimization.

  • A.1 Proof of Theorem 8: Theorem 8 gives a data-dependent disintegrated bound for stochastic majority votes using two finite hypothesis sets, weight spaces, hyper-priors, learning algorithms, and a sample split.The learned hyper-posteriors are QS=A1(S1,P1) and QS=A2(S2,P2).
  • A.1 Proof of Theorem 8: The proof applies Theorem 6 separately to S1 and S2 with confidence parameter δ/2 because each subset is independent of the constructions based on the other subset.A union bound combines the two guarantees with probability at least 1−δ, followed by convexity of the KL divergence.
  • A.1 Proof of Theorem 8: Theorem 9 provides the corresponding data-dependent Rényi-based disintegrated bound under the same assumptions with λ>1.Its proof repeats the split-sample, conditional-application, union-bound, and convexity steps using Theorem 7.
  • A.1 Proof of Theorem 8: The bounds are specialized to Dirichlet hyper-priors and hyper-posteriors, yielding self-bounding optimization objectives for data-independent and data-dependent settings.The Dirichlet Rényi expression is finite only when λα_j+(1−λ)β_j>0 for every coordinate j.

B.2 Data-Independent Setting

The section specializes the paper’s disintegrated PAC-Bayesian bounds with Dirichlet hyper-priors and hyper-posteriors, yielding explicit corollaries and self-bounding objectives for deterministic majority votes.

  • Dirichlet instantiation: Dirichlet distributions instantiate the hyper-prior and hyper-posterior over majority-vote weight spaces for the paper’s disintegrated bounds.The corollaries cover both pointwise density-ratio and Rényi-divergence formulations, including data-independent and cross-bounded constructions.
  • Scope of the bounds: The resulting corollaries apply to finite hypothesis sets, simplex-constrained majority-vote weights, bounded losses, and PAC-Bayesian learning algorithms.For the two-split constructions, each subset has its own hypothesis set, prior, posterior, and learning algorithm.
  • Optimization: Substituting the Dirichlet density or Rényi divergence into the general theorems produces explicit bounds and corresponding self-bounding optimization objectives.The proof passages identify these substitutions as the route to the stated corollaries and objectives.
  • Data-dependent construction: The data-dependent construction uses two equally sized data splits, with separate Dirichlet priors and posteriors for each split and τ = 1/2.The setup assumes n is even and sets n1 = n2 = n/2.

C.1 Datasets

The experiments use binary and multiclass classification datasets drawn from UCI, LIBSVM, and Zalando’s Fashion-MNIST data.

  • Dataset collection: The dataset collection covers binary and multiclass classification tasks from UCI, LIBSVM, and Zalando’s Fashion-MNIST.The binary and multiclass dataset tables report instances, preprocessed input features, classes, and prediction tasks.
  • Binary datasets: Table 1 organizes the binary classification datasets used in the experiments.The accompanying dataset description specifies that dataset tables report instances, features, classes, and prediction tasks.
  • Multiclass datasets: Table 2 organizes the multiclass classification datasets used in the experiments.The same dataset metadata categories are reported for the multiclass tasks.

C.2 Complete Numerical Results

The complete numerical results report bounds, test errors, and training times for binary and multiclass datasets, averaged over repeated independent runs with standard deviations.

  • Results organization: Tables 3–8 report bound values, test errors, and training times separately for binary and multiclass datasets.Tables 3, 4, and 7 cover binary results, while Tables 5, 6, and 8 cover multiclass results.
  • Reporting protocol: All reported results are averaged over 10 independent runs and include standard deviations.Bound values and test errors are expressed as percentages, while training times are expressed in seconds.
  • Binary results: The binary numerical results include mean bounds, mean test errors, and mean training times across the listed binary datasets.The binary dataset-method layout is represented in the numerical-results tables, with dataset names including MUSHROOMS, TICTACTOE, SVMGUIDE, and others.
  • Multiclass results: The multiclass numerical results include mean bounds, mean test errors, and mean training times across the multiclass datasets.The multiclass results are reported in Tables 5, 6, and 8 using the same repeated-run reporting convention.
Loading 2609.16803v1…