PaperlayerView exact revision on arXiv

Source-linked AI summary

Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm

Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, Jean-Francis Roy

arXiv:1503.08329v2stat.MLcs.LG

TL;DR

Majority votes can outperform individual voters through error compensation, but existing risk analyses do not fully capture this behavior. The paper introduces the C-bound and PAC-Bayesian analyses, then derives MinCq, which minimizes the bound and performs very well empirically against AdaBoost and SVM.

  • Problem

    Existing majority-vote analyses need bounds that capture when voters’ errors compensate and the vote outperforms its average voter.

    Source: §2 · p. 2

  • Method

    The paper studies majority-vote margins, derives the C-bound from their first two moments, develops PAC-Bayesian bounds, and uses them to formulate MinCq.

    Source: §2 · pp. 3–4, §5 · p. 19

  • Results

    The C-bound accurately predicts majority-vote risk and can approach zero even when Gibbs-classifier risk is near 1/2, while MinCq is expressed as a quadratic program.

    Source: §2 · p. 3, §9 · pp. 62–63

  • Takeaways & Limitations

    The analysis provides a theoretical foundation for constructing voter communities that account for both voter quality and disagreement.

    Source: §2 · p. 4, §9 · p. 63

    The KL-term removal argument does not straightforwardly extend to paired voters because products of aligned posteriors need not remain aligned.

    Source: Lemma 30 (Change of measure inequality… · p. 42

Abstract

from arXiv · show

We propose an extensive analysis of the behavior of majority votes in binary classification. In particular, we introduce a risk bound for majority votes, called the C-bound, that takes into account the average quality of the voters and their average disagreement. We also propose an extensive PAC-Bayesian analysis that shows how the C-bound can be estimated from various observations contained in the training data. The analysis intends to be self-contained and can be used as introductory material to PAC-Bayesian statistical learning theory. It starts from a general PAC-Bayesian perspective and ends with uncommon PAC-Bayesian bounds. Some of these bounds contain no Kullback-Leibler divergence and others allow kernel functions to be used as voters (via the sample compression setting). Finally, out of the analysis, we propose the MinCq learning algorithm that basically minimizes the C-bound. MinCq reduces to a simple quadratic program. Aside from being theoretically grounded, MinCq achieves state-of-the-art performance, as shown in our extensive empirical comparison with both AdaBoost and the Support Vector Machine.

1. Previous Work and Implementation

The paper unifies and revises several earlier PAC-Bayesian contributions, adding new theoretical results and extending the empirical experiments. Source code is provided for computing the bounds and implementing MinCq.

Previous Work

  • The work extends Lacasse et al. (2006) and Laviolette et al. (2011), incorporates ideas from Laviolette and Marchand (2005, 2007) and Germain et al. (2009, 2011), and revises and unifies this previous work.It also adds new results and extends the empirical experiments.Source: §1 · p. 1

Implementation

  • Source code is available for computing the paper’s PAC-Bayesian bounds and implementing the MinCq learning algorithm.Source: §1 · p. 1

2. Introduction

The paper develops the C-bound, a PAC-Bayesian risk bound for majority votes that uses voter quality and disagreement to capture error compensation. It derives PAC-Bayesian guarantees and introduces MinCq, a quadratic-programming algorithm that minimizes the C-bound and performs competitively against AdaBoost and SVM.

Motivation

  • Majority votes encompass ensembles, Bayesian classifiers, kernel methods, and neural-network output units, and can outperform individual voters when their errors compensate.The neural-network discussion assumes fixed voters; learning their incoming weights remains outside the paper’s analysis.Source: §2 · p. 2

C-bound

  • The C-bound uses the first two moments of the majority-vote margin, linking them to Gibbs risk and expected disagreement to obtain a tighter bound than the factor-of-two Gibbs-risk guarantee.The factor-of-two bound follows from Markov’s inequality on the first moment, whereas the C-bound uses Chebyshev’s inequality.Source: §2 · p. 3
  • Theoretical and empirical studies show that the C-bound accurately indicates majority-vote risk and can approach zero even when Gibbs risk is near 1/2, capturing compensation among voter errors.It can therefore be smaller than the Gibbs risk rather than merely twice that risk.Source: §2 · p. 3

PAC-Bayesian analysis

  • The PAC-Bayesian analysis separately bounds Gibbs risk and disagreement or directly bounds the C-bound, with the former suited to semi-supervised learning and the latter improving supervised-learning bounds.The analysis also recovers commonly used McAllester and Langford–Seeger PAC-Bayesian bounds.Source: §2 · p. 3
  • The paper extends PAC-Bayesian guarantees beyond KL-based bounds and handles voters defined from training data, such as kernel voters, through sample compression theory.This addresses the apparent conflict between data-dependent voters and priors that must be defined before observing data.Source: §2 · p. 4

Learning algorithm

  • MinCq minimizes the C-bound over classifier or kernel-function voters, accounts for voter quality and disagreement, reduces to a simple quadratic program, and performs competitively against AdaBoost and SVM.The resulting vote is designed to form a community whose individual errors compensate.Source: §2 · p. 4

3. Basic Definitions

The section defines weighted majority votes, their risks, and related Gibbs and disagreement quantities in binary and real-valued classification. It motivates disagreement-aware analysis because Gibbs-risk bounds can miss cases where voter communities compensate for individual errors.

Voters and losses

  • The framework uses i.i.d. PAC data and defines zero-one and linear losses for binary and real-valued voters, with the losses coinciding for binary outputs.Expected loss is evaluated under either the true distribution or its empirical training-set counterpart.Source: §3 · pp. 4–5

Majority votes

  • A Q-weighted majority vote predicts the sign of the Q-average voter output, with ties defined as abstentions.The convention sgn(0)=0 simplifies the analysis, and ties incur zero-one loss 1.Source: §3 · pp. 4–6

Risk definitions

  • The Bayes risk is the expected zero-one loss of the majority vote, while the Gibbs classifier samples a voter from Q and its risk uses expected linear loss.The deterministic majority vote and stochastic Gibbs classifier provide linked but distinct risk notions.Source: §3 · p. 6

Gibbs-risk limitation

  • The standard inequality RD′(BQ) ≤ 2RD′(GQ) can be loose because an inaccurate Gibbs classifier may coexist with a perfect majority vote.When each example’s expected voter margin is just below one half, RD′(GQ)=1/2−ϵ while RD′(BQ)=0, so individual weakness does not capture community compensation.Source: §3 · p. 7

Disagreement

  • Expected disagreement measures how voters differ and is label-independent, allowing it to be estimated from unlabeled data.This quantity is introduced to compare voters with one another rather than only assessing their average individual quality.Source: §3 · pp. 7–8

4. Bounds on the Risk of the Majority Vote

This section introduces and derives the C-bound, an upper bound on majority-vote risk based on Gibbs risk and expected disagreement, using the first two moments of the margin. It also examines the bound’s behavior and empirically evaluates its characterization of majority-vote risk and use as an AdaBoost stopping criterion.

4.1 The Margin of the Majority Vote and its Moments

  • The margin’s first moment recovers the classical bound RD′(BQ) ≤2 · RD′(GQ), while its second moment links expected disagreement to the margin variance.The C-bound extends the first-moment Markov analysis by using Chebyshev’s inequality and the variance of the margin.Source: §4.1 · p. 10, §4.2 · pp. 10–11

4.3 The C-bound: a Bound on RD′(BQ) That Can Be Much Smaller Than RD′(GQ)

  • The C-bound upper-bounds majority-vote risk from the margin’s mean and variance, assuming positive mean margin, and decreases as Gibbs risk decreases or disagreement increases.This yields a trade-off between voter quality and disagreement that is more informative than minimizing Gibbs risk alone.Source: §4.3 · pp. 11–12

4.4 Statistical Analysis of the C-bound’s Behavior

  • Even when Gibbs risk is large, the C-bound can approach zero as the number of voters grows, provided their pairwise covariances are non-positive and the relevant margins remain bounded away from zero.This behavior is especially associated with non-correlated voters and follows from the shrinking variance of the aggregate margin.Source: §4.4 · p. 13, §4.4.2 · p. 15

4.4.1 Conditions of Optimality

  • The C-bound is optimal exactly when its value is below twice the Gibbs risk, meaning a margin distribution with the same first two moments can attain the bound as the majority-vote risk.The optimality conditions are stated under positive mean margin, equivalently RD′(GQ) < 1/2.Source: §4.4.1 · pp. 13–14

4.4.2 The C-bound Can Be Arbitrarily Small, Even for Large Gibbs Risks

  • With many voters of vanishing individual weight, non-positive average pairwise covariance drives the margin variance toward zero, including for pairwise-independent voters.For uniformly weighted voters, the variance is O(1/n) under the stated covariance condition.Source: §4.4.2 · p. 15
  • The derivation of the C-bound’s third inequality concludes by applying Equation (11).The supplied passage provides only this final derivation step.Source: §4.4.2 · p. 16

4.5.1 Comparison with Other Indicators

  • The C-bound shows a strong, nearly linear correlation with majority-vote risk, whereas its individual component quantities show no clear correlation and are insufficient to characterize Bayes risk.The comparison uses AdaBoost with decision stumps on several UCI binary classification datasets, evaluating 20 majority votes per dataset.Source: §4.5.1 · p. 16

4.5.2 The C-bound as a Stopping Criterion for Boosting

  • The stopping-criterion experiment runs AdaBoost for 1000 rounds, selects the lowest training-set empirical C-bound, and compares it with empirical-risk, cross-validation, and validation-set selection.The validation-set method trains on 10% fewer examples, while the empirical-risk method is vulnerable to overfitting.Source: §4.5.2 · pp. 17–18
  • The empirical C-bound is a surprisingly good AdaBoost stopping criterion, outperforming empirical Bayes risk and validation-set selection while matching cross-validation accuracy with lower runtime.Statistical tests support its advantage over empirical Bayes risk and validation selection; cross-validation achieves similar accuracy but requires more running time.Source: Table 1 · p. 18, §4.5.2 · p. 18

5. A PAC-Bayesian Story: From Zero to a PAC-Bayesian C-bound · 5.1 General PAC-Bayesian Theory for Real-Valued Losses

The paper develops a self-contained PAC-Bayesian route from empirical C-bound estimates to majority-vote risk bounds. It introduces a general real-valued-loss theorem, specializes it to Gibbs and majority-vote analyses, and explains the computational procedures for each bound.

5. A PAC-Bayesian Story: From Zero to a PAC-Bayesian C-bound

  • The analysis estimates the true C-bound from its empirical estimate and derives majority-vote risk bounds from training-data observations.It presents PAC-Bound 0 for Gibbs risk, PAC-Bounds 1 and 2 for majority votes, and reserves PAC-Bound 3 for Section 6.Source: §5 · p. 19
  • PAC-Bayesian bounds for Gibbs classifiers use empirical Gibbs risk and the Kullback-Leibler divergence between posterior Q and prior P, with validity uniform over all posteriors Q.The prior is chosen before observing training data, whereas the posterior is typically selected after training.Source: §5 · p. 19
  • The section first bounds Gibbs risk, converts it to majority-vote risk using Proposition 10, then introduces pairwise losses to bound the majority vote directly through the C-bound.The paper also describes the algorithmic procedure required to compute each proposed bound.Source: §5 · p. 19

5.1 General PAC-Bayesian Theory for Real-Valued Losses

  • The subsection’s key technical device is a change-of-measure inequality for arbitrary distributions P and Q and measurable real-valued functions.Its proof uses the definition of KL-divergence and Jensen’s inequality; equality holds when P and Q share the same support.Source: §5.1 · pp. 19–20
  • Theorem 18 bounds expectations of any loss L:Y×Y→[0,1] for every posterior Q using a convex function D, prior P, confidence δ, and sample parameter m′.Unlike a theorem specialized to expected linear loss, this result supports generalized Gibbs risks and later loss-function choices.Source: §5.1 · p. 20
  • Choosing m′ different from the training-set size m changes the relative weighting of KL(Q∥P) and the logarithmic term, potentially tightening the bound.The theorem applies simultaneously to all posteriors Q, and the choice is especially relevant when the two terms differ substantially.Source: §5.1 · p. 20
  • Specializing Theorem 18 with Bernoulli KL yields a real-valued-loss theorem reused for Gibbs-risk bounds and later PAC-Bayesian bounds for other losses.The resulting intermediate Theorem 20 connects the general theorem to Corollary 21 and to the developments in Section 5.3.Source: §5.1 · pp. 21–22
  • Maurer’s auxiliary quantity satisfies ξ(m)≤2√m for m≥8 and ξ(m)≥√m for m≥2, with smaller cases verified computationally.These bounds quantify the finite-sample term used in the specialized PAC-Bayesian result.Source: §5.1 · p. 22

5.2 PAC-Bayesian Theory for the Gibbs Classifier

The section derives PAC-Bayesian risk bounds for Gibbs classifiers, uses one to bound majority-vote risk, and computes the resulting bound by root finding. The Gibbs bounds slightly improve related results by Langford, Seeger, and McAllester.

5.2 PAC-Bayesian Theory for the Gibbs Classifier

  • The analysis begins with two PAC-Bayesian Gibbs-risk results, then uses one to construct a first PAC-Bayesian bound for the majority-vote classifier.The section also explains how the bound’s empirical value can be computed from training observations.Source: §5.2 · p. 23, §5.2.2 · p. 24

5.2.1 PAC-Bayesian Theorems for the Gibbs Risk

  • Corollaries 21 and 22 provide classical PAC-Bayesian Gibbs-risk bounds, slightly improving bounds associated with Langford and Seeger (2001); Seeger (2002); Langford (2005) and McAllester (1999, 2003a).Corollary 22 is obtained from Corollary 21 using Pinsker’s inequality.Source: §5.2.1 · p. 23

5.2.2 A First Bound for the Risk of the Majority Vote

  • PAC-Bound 0 upper-bounds majority-vote risk by maximizing a confidence-valid Gibbs-risk set and multiplying the result by 2.The bound follows from Proposition 10 and Corollary 21; it is trivial when the resulting value reaches 1.Source: §5.2.2 · p. 24

5.2.3 Computation of PAC-Bound 0

  • PAC-Bound 0 has no closed-form expression, so its empirical value is obtained by solving an equation with a root-finding method.The equation is easy to solve because its left-hand side is convex in r while its right-hand side is constant.Source: §5.2.2 · p. 24, §5.2.3 · p. 24

5.3 Joint Error, Joint Success, and Paired-voters

The section introduces joint-error and joint-success notions and paired-voters to support new PAC-Bayesian C-bound theorems, including separate disagreement bounds.

5.3 Joint Error, Joint Success, and Paired-voters

  • The section develops notions needed for new PAC-Bayesian C-bound theorems and illustrates PAC-Bound 0 by deriving RD(BQ) ≲ 0.746 from an empirical Gibbs risk of 0.30.With KL(Q∥P)=5, m=1000, and δ=0.05, the estimated interval is approximately [0.233, 0.373] at 95% confidence.Source: §5.3 · pp. 24–25

5.3.1 The Joint Error and the Joint Success

  • Expected joint success and joint error extend the binary-voter analysis to real-valued voters and rewrite margin moments, Gibbs risk, and the C-bound.The definitions relate joint success, joint error, and disagreement, whose probabilities sum to one in the binary case.Source: §5.3.1 · pp. 25–26

5.3.2 Paired-Voters and Their Losses

  • Paired-voters combine two voters into a tuple-valued voter, with product weighting Q2(fij)=Q(fi)·Q(fj), enabling separate bounds on disagreement and the C-bound.For fij(x)=⟨fi(x),fj(x)⟩, the paired-voter class contains all ordered voter pairs, and their expected losses recover joint-error quantities.Source: §5.3.2 · p. 26

5.4 PAC-Bayesian Theory For Losses of Paired-voters

The section develops PAC-Bayesian bounds for majority-vote risk by controlling Gibbs risk and paired-voter disagreement through the C-bound. It derives supervised and semi-supervised bounds and explains their computation.

5.4 PAC-Bayesian Theory For Losses of Paired-voters

  • Paired-voter analysis yields two PAC-Bayesian majority-vote risk bounds, covering supervised and semi-supervised settings through the C-bound.The approach combines a Gibbs-risk bound with a disagreement bound and exploits paired-voters to control the C-bound.Source: §5.4 · p. 27

5.4.1 A PAC-Bayesian Theorem for eD

  • Theorem 25 provides a PAC-Bayesian bound for the expected disagreement, expected joint success, or expected joint error of a majority vote.The theorem applies for arbitrary data distributions, voter sets, priors, confidence parameters, and posteriors.Source: §5.4.1 · p. 27

5.4.2 A New Bound for the Risk of the Majority Vote

  • PAC-Bound 1 bounds majority-vote risk through the C-bound, while PAC-Bound 1’ is tighter when abundant unlabeled data enables more accurate disagreement estimation.PAC-Bound 1 can degrade when numerator and denominator bounds are loose; PAC-Bound 1’ uses unlabeled data for disagreement and labeled data for Gibbs risk.Source: §5.4.2 · pp. 28–29

5.4.3 Computation of PAC-Bounds 1 and 1’

  • PAC-Bounds 1 and 1’ are computed by solving equations for the Gibbs-risk quantity r and disagreement quantity d, using unlabeled data for d in the semi-supervised case.After computing r and d, the majority-vote bound is obtained from the corresponding C-bound expression.Source: §5.4.3 · p. 29

5.5 PAC-Bayesian Theory to Directly Bound the C-bound

The section extends PAC-Bayesian analysis from bivalent to trivalent variables, enabling direct bounds on the C-bound. It derives PAC-Bounds 2 and 2′ and gives a one-dimensional optimization procedure for computing them.

5.5.1 A General PAC-Bayesian Theorem for Two Losses of Paired-Voters

  • Theorem 26 simultaneously bounds two losses of paired-voters using a convex divergence function, extending the PAC-Bayesian framework for real-valued losses.The theorem applies to any two losses among the error, success, and disagreement losses.Source: §5.5.1 · p. 30

5.5.2 A PAC-Bayesian Theorem for Any Pair Among e_D

  • Theorem 28 replaces Bernoulli KL divergence with KL divergence between trivalent random variables, supported by a trivalent generalization of Maurer’s lemma.The theorem is described as tighter than the first version proposed by Lacasse et al. (2006).Source: §5.5.2 · pp. 31, 33
  • Theorem 28 directly bounds any pair among the expectations e_D, s_D, and d_D, making it suitable for bounding the C-bound.Its trivalent-variable formulation yields tighter bounds for k = 3 than the cited general k-valent PAC-Bayesian results.Source: §5.5 · p. 30, §5.5.2 · p. 33

5.5.3 Another Bound for the Risk of the Majority Vote

  • PAC-Bound 2 directly bounds the C-bound by optimizing over achievable disagreement–joint-error pairs constrained by d ≤ 2(√e − e) and 2e + d < 1.PAC-Bound 2′ slightly improves this by additionally bounding the joint error with confidence parameter δ/2.Source: §5.5.3 · pp. 34–35

5.5.4 Computation of PAC-Bounds 2 and 2′

  • PAC-Bounds 2 and 2′ maximize the concave function F_C(d, e) over bounded convex domains using two nested one-dimensional optimization procedures.In the supplied examples, PAC-Bound 2 gives R_D(B_Q) ≤ 0.679, while PAC-Bound 2′ gives R_D(B_Q) ≤ 0.660.Source: §5.5.4 · p. 36, §5.5.3 · p. 36, Figure 6 · p. 37

5.6 Empirical Comparison Between PAC-Bounds on the Bayes Risk RD(BQ)

On Mushroom UCI data, the PAC-Bounds are empirically compared during AdaBoost training, with PAC-Bound 1′ generally tightest and all bounds degrading after eight boosting rounds. The degradation is attributed to margin-moment behavior that amplifies slack in estimating the first margin moment.

5.6 Empirical Comparison Between PAC-Bounds on the Bayes Risk RD(BQ)

  • The experiment uses AdaBoost with decision stumps on 8124 Mushroom UCI examples split randomly into training and testing halves, evaluating PAC-Bound 0 and the proposed variants each round.PAC-Bound 1′ simulates abundant unlabeled data by computing d_Q empirically on the testing set.Source: §5.6 · p. 37
  • PAC-Bound 1 is generally tighter than PAC-Bound 0, PAC-Bound 2 improves substantially, and PAC-Bound 1′ is tightest when unlabeled data estimate d_Q.PAC-Bound 2′ yields almost no improvement in this setting.Source: §5.6 · p. 37, Figure 7 · p. 38
  • After eight boosting rounds, all bounds degrade even though the empirical C_Q continues to decrease.The comparison covers 60 boosting rounds.Source: §5.6 · p. 37, Figure 7 · p. 38
  • The degradation occurs because C_Q’s denominator tends to zero, forcing the second margin moment near zero and making slack in the first-margin-moment bound multiply across all three PAC-bounds.Boosting constructs votes whose empirical first margin moment is only slightly above zero, so the required condition is difficult to satisfy tightly.Source: §5.6 · p. 37

6. PAC-Bayesian Bounds without KL

The section develops PAC-Bayesian bounds without KL divergence by restricting posteriors to aligned distributions on self-complemented voter sets. These results extend from Gibbs risk and paired-voter disagreement to a majority-vote risk bound that motivates MinCq and supports sample-compressed kernel voters.

6.1 Self-Complemented Sets of Voters and Aligned Distributions

  • Aligned-posterior bounds eliminate KL divergence by restricting posteriors on self-complemented voter sets, whose complementary-weight constraints provide built-in regularization.For uniform priors, aligned distributions are quasi-uniform; in finite settings, complementary voter pairs induce bounded weights and L∞-norm regularization.Source: §6 · pp. 38–39, §6.1 · p. 39

Lemma 30 (Change of measure inequality for aligned posteriors)

  • The change-of-measure lemma works by exchanging expectations under an aligned posterior and prior for functions invariant under voter complementation, then applying Jensen’s inequality.The construction relies on self-complemented voter sets and aligned posteriors.Source: Lemma 30 (Change of measure inequality… · p. 40

6.2 PAC-Bayesian Theorems without KL for the Gibbs Risk

  • The aligned-posterior change-of-measure inequality replaces the usual KL-based step and yields PAC-Bayesian theorems for Gibbs risk without a KL term.Specializing the theorem recovers classical PAC-Bayesian forms for aligned posteriors, including a bound analogous to McAllester (2003a) without KL divergence.Source: Lemma 30 (Change of measure inequality… · pp. 40–41, §6.2 · p. 40

6.3 PAC-Bayesian Theorems without KL for the Expected Disagreement dD

  • Paired-voter extensions apply the same KL-free strategy to expected disagreement by using product distributions over voter pairs and complementation-invariant pair functions.The paired-voter theorem uses the disagreement loss Ld and produces corresponding corollaries for aligned posteriors.Source: §6.3 · p. 42, Theorem 35 (PAC-Bayesian theorem for… · p. 43

Theorem 35 (PAC-Bayesian theorem for paired-voters and aligned posteriors)

  • The paired-voter theorem derives disagreement bounds by replacing the single-voter change-of-measure inequality with its aligned-posterior counterpart for voter pairs.The construction uses the product prior P^2 and posterior Q^2 over paired voters.Source: Theorem 35 (PAC-Bayesian theorem for… · pp. 43–44

6.4 A Bound for the Risk of the Majority Vote without KL Term

  • PAC-Bound 3 controls the majority-vote risk through separate bounds on Gibbs risk and expected disagreement for aligned posteriors, without a KL term.The bound provides the theoretical starting point for the MinCq learning algorithm.Source: §6.4 · p. 44
  • The KL-free framework also yields PAC-Bound 3′ for kernel-function voters defined from part of the training set through sample compression.This addresses the difficulty that the prior must ordinarily be defined before observing the training set.Source: §6.4 · p. 44

7. PAC-Bayesian Theory for Sample-Compressed Voters

The section extends PAC-Bayesian analysis to voters constructed from training examples through sample compression, addressing data-dependent priors and biased empirical risks. It culminates in KL-free bounds for majority votes using kernel or similarity-based voters, motivating MinCq.

7. PAC-Bayesian Theory for Sample-Compressed Voters

  • Sample compression resolves the data-dependent-voter problem by defining priors over compression indices and messages before observing the training data, without requiring RKHS or representer-theorem machinery.Unlike the surrogate-RKHS approach, this framework handles arbitrary similarity measures and voters constructed from examples.Source: §7 · p. 44, §7.2 · p. 46

7.1 The General Sample Compression Setting

  • Each sc-voter is reconstructed from a compression sequence of training examples and an a priori specified message through a reconstruction function R.The framework allows repeated indices and strictly generalizes the non-sample-compressed setting when |i| = 0.Source: §7.1 · p. 45

7.2 A Simplified Sample Compression Setting

  • The simplified setting restricts compression sequences to at most λ examples and messages to λ bits, placing the posterior Q on Iλ × Σλ.This representation makes the prior independent of the observed training sequence.Source: §7.2 · pp. 45–46

7.3 A First Sample-Compressed PAC-Bayesian Theorem

  • Because compression examples bias empirical Gibbs risk, sample-compressed bounds replace the usual 1/m factor with 1/(m−λ) under the maximum-size simplification.The proof treats the examples outside the compression sequence as an independent sample of size m−λ.Source: §7.3 · pp. 46–47

7.4 Sample-Compressed PAC-Bayesian Bounds without KL

  • The section generalizes preceding PAC-Bayesian results to sample-compressed voters, especially the KL-free bounds used to derive MinCq.These extensions include the sample-compressed analogues of the Gibbs-risk and disagreement results.Source: §7.3 · p. 48, §7.4 · p. 48

7.4.1 A PAC-Bayesian Theorem for the Gibbs Risk of Sc-Voters

  • For self-complemented reconstruction functions, Theorem 41 provides a PAC-Bayesian bound on the Gibbs risk of sc-voters for posteriors aligned with the prior.The theorem applies when reconstructed voters have compression size at most λ and λ < m.Source: §7.4.1 · p. 48

7.4.2 A PAC-Bayesian Theorem for the Disagreement of Sc-Voters

  • Theorem 42 extends the self-complemented analysis to expected disagreement by constructing paired sc-voters, with the effective sample size reduced according to two compression sequences.The theorem assumes compression size λ < ⌊m/2⌋.Source: §7.4.2 · p. 49

7.4.3 A Sample Compression Bound for the Risk of the Majority Vote

  • PAC-Bound 3’ bounds the risk of majority votes using kernel or similarity-based sc-voters with compression size at most one, in Gibbs/disagreement or margin-moment forms.The margin-moment form supports the learning algorithm introduced in Section 8.Source: §7.4.3 · pp. 50–51

8. MinCq: Learning by Minimizing the C-bound

This section presents MinCq, a quadratic-programming approach that learns weighted majority votes by minimizing the C-bound under constraints designed to control overfitting and instability. It evaluates the method across three learning contexts against AdaBoost and SVM, examining both predictive performance and the behavior of the resulting PAC-Bayesian bounds.

8. MinCq: Learning by Minimizing the C-bound

  • MinCq constructs weighted majority votes by minimizing the C-bound, with supervised and transductive versions expressible as quadratic programs on positive semi-definite matrices.The algorithm targets weak learners and exploits the possibility that decorrelated voters yield a small C-bound even when Gibbs risk is near 1/2.Source: §8 · p. 51

8.1 From the C-bound to the MinCq Learning Algorithm

  • MinCq constrains Q to quasi-uniform distributions with empirical margin at least µ, where µ>0 is selected by cross-validation; this addresses overfitting while preserving majority votes and C-bound values.Any Q with empirical margin at least µ can be replaced by a quasi-uniform Q′ with margin exactly µ, preserving its majority vote and empirical and true C-bound values.Source: §8 · pp. 51–52, §8.1 · pp. 53–54
  • Under the fixed-margin constraint, MinCq minimizes the second margin moment, thereby reducing margin variance while maintaining its first moment above the threshold.This strategy supplies a theoretical justification for variance-control approaches used in random forests, transfer learning, and Boosting.Source: §8 · p. 52

8.2 MinCq as a Quadratic Program

  • For a self-complemented voter set, MinCq is implemented as a quadratic program with n variables rather than 2n, using a positive semi-definite matrix and recovering complementary weights from the first n variables.The program minimizes the empirical second margin moment subject to the empirical margin constraint and quasi-uniformity constraints.Source: §8.1 · p. 54, §8.2 · p. 56

8.3 Experiments

  • The experiments compare MinCq with AdaBoost and SVM across handwritten-digit recognition, classical binary classification, and Amazon-review sentiment contexts.Decision-stump, RBF-kernel, and linear-kernel variants are evaluated, with hyperparameters selected by 5-fold cross-validation on each training set.Source: §8.3 · p. 57

8.3.1 Handwritten Digits Recognition Context

  • On 45 MNIST binary tasks, both statistical tests find RbfMinCq outperforms RbfSVM and StumpsMinCq outperforms StumpsAdaBoost.Each task uses 500 training examples, with the remaining examples held out for testing.Source: Figure 8 · p. 58, §8.3.1 · p. 59

8.3.2 Classical Binary Classification Tasks Context

  • Across unrelated UCI binary tasks, RbfMinCq and RbfSVM, and StumpsMinCq and StumpsAdaBoost, show no significant performance differences.The benchmark uses half of each data set, up to 500 examples, for training and the remainder for testing.Source: §8.3.2 · p. 59, Table 3 · p. 60

8.3.3 Amazon Reviews Sentiment Analysis

  • On Amazon sentiment data, LinearMinCq wins or draws on every data set against LinearSVM, although statistical tests find no significant difference.Reviews are represented with filtered unigram and bigram tf-idf features, using 1,000 positive and 1,000 negative training reviews per product category.Source: §8.3.3 · pp. 59–60, Table 4 · p. 61

8.3 Experiments

  • MinCq achieves state-of-the-art performance, significantly outperforming its SVM and AdaBoost counterparts on handwritten digits while remaining competitive on other benchmarks.The paper attributes this to minimizing the C-bound and favoring majority votes with maximally uncorrelated voters.Source: Table 2 · p. 58, §8.3.1 · p. 59, §8.3.3 · p. 60

8.3.4 Experiments with Stronger Voters

  • With stronger decision-tree voters, PAC-Bayesian bounds tighten as µ increases, with PAC-Bounds 2 and 2’ below 0.2, but cross-validation is still needed to choose µ.On Mushroom, the empirical C-bound rises from 0.001 to 0.016, while test risk remains below 0.001; PAC-Bound 3 is looser but has similar behavior.Source: §8.3.4 · pp. 61–62, Figure 9 · p. 62

9. Conclusion

The paper develops the C-bound and PAC-Bayesian estimates that support MinCq, a quadratic-programming learner with strong performance on natural data compared with SVM.

Contributions

  • The paper revisits and extends earlier results while updating their discussion in light of the continuing development of PAC-Bayesian theory.The cited prior work includes Lacasse et al. (2006) and Laviolette et al. (2011).Source: §9 · p. 62
  • The C-bound uses the first two moments of the margin distribution, is based on one-sided Chebyshev, and strongly predicts majority-vote risk.Under Proposition 14’s mild condition, one-sided Chebyshev is tight among inequalities using only the first two moments; Figure 3 supports the bound’s predictive power.Source: §9 · p. 62
  • PAC-Bayesian theorems provide uniform high-confidence estimates of the C-bound for all posterior distributions.The analysis also extends to sample compression, including training-data-constructed voters such as kernel functions yik(x_i, ·), and introduces bounds without a Kullback-Leibler divergence term.Source: §9 · pp. 62–63
  • The C-bound and divergence-free PAC-Bounds 3 and 3’ provide the theoretical foundation for MinCq, which reduces to a quadratic program.MinCq is designed from these guarantees and performs very well on natural data compared with the state-of-the-art SVM.Source: §9 · p. 63

Future scope

  • The conclusion identifies broader PAC-Bayesian applications across transductive learning, domain adaptation, density estimation, structured prediction, co-clustering, martingales, higher-order U-statistics, non-i.i.d. settings, bandits, and reinforcement learning.These applications are presented as evidence that PAC-Bayesian theory can address more sophisticated learning frameworks.Source: §9 · p. 63

Appendix A. Auxiliary mathematical results

This appendix collects auxiliary inequalities and convexity results used in the paper’s PAC-Bayesian analysis. It also generalizes Maurer’s lemma to trivalent random variables and establishes concavity of F_C(d, e).

Basic inequalities

  • Markov’s and one-sided Chebyshev’s inequalities provide probability bounds from expectations, variances, and positive thresholds.The appendix applies Markov’s inequality to derive the one-sided Chebyshev bound.Source: Appendix A · pp. 63–64

KL convexity

  • The Kullback-Leibler divergence is convex in pairs of distributions, implying convexity for the Bernoulli and trivalent divergence functions used in the analysis.The cited theorem is stated for discrete distributions, with the argument noted as straightforwardly generalizable to continuous distributions.Source: Appendix A · p. 64

Generalized Maurer lemma

  • Maurer’s lemma is generalized from [0, 1]-valued variables to pairs (X, Y) in [0, 1]^2 satisfying X + Y ≤ 1, represented by three outcomes.The proof uses convex combinations of extreme points in H = {(1, 0), (0, 1), (0, 0)} and independence of n realizations.Source: Appendix A · pp. 65–66

Convex-combination proof

  • The convex-combination representation underlying the generalized lemma is proved by induction over vector size n.For n = 1, the representation uses weights x_1, y_1, and 1 − x_1 − y_1 on the three extreme points; the induction extends it to larger vectors.Source: Appendix A · p. 66

Concavity result

  • The function F_C(d, e) is concave, established by showing that its Hessian matrix is negative semi-definite.This proposition supplies the curvature property needed for subsequent optimization arguments.Source: Appendix A · p. 67

Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors

Appendix B develops a tuple-level change-of-measure inequality and a general PAC-Bayesian theorem for aligned posteriors. These results extend the corresponding simpler lemmas and theorems from the main paper.

Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors

  • The appendix defines tuples of voters under Cartesian-product posteriors and establishes a change-of-measure inequality for self-complemented voter sets and aligned distributions.The construction uses complement-transformed tuples and applies Jensen’s inequality after changing expectations from Q^k to P^k.Source: Appendix B · pp. 68–69

Theorem 56 (General PAC-Bayesian theorem for tuples of voters and aligned

  • Theorem 56 generalizes the PAC-Bayesian guarantee to tuples of voters, aligned posteriors, convex functions, and loss functions under arbitrary data distributions.Its proof combines Markov’s inequality, Theorem 55’s tuple-level change of measure, and Jensen’s inequality using convexity.Source: Theorem 56 (General PAC-Bayesian… · p. 70

Related papers

Loading 1503.08329v2…