Second Order PAC-Bayesian Bounds for the Weighted Majority Vote

• Unknown error rates and dependent classifier errors make practical weight assignment unresolved under assumptions used by earlier analyses.Source: §1 · pp. 1–2
• Unlike prior C-bounds, the new analysis is designed to avoid difficult estimation and optimization limitations while handling multiclass classification.Source: §1 · p. 2
• The first-order bound ignores error correlation, and its minimization typically concentrates weights on a few classifiers and deteriorates test error.Source: §1 · pp. 1–2
• The proposed multiclass analysis uses a second-order Markov inequality and PAC-Bayesian tandem-loss estimation to produce a bound that can optimize majority-vote weights.Source: §1 · p. 2
• The binary specialization rewrites tandem loss using expected loss and disagreement, allowing disagreement estimation from unlabeled data when unlabeled data substantially exceeds labeled data.Source: §1 · p. 2

• A multiclass hypothesis maps inputs to a finite label set, with quality measured by expected and empirical 0-1 loss.Source: §2 · p. 2
• A randomized classifier samples one hypothesis from distribution ρ for each prediction, and its expected loss is averaged over hypotheses.Source: §2 · pp. 2–3
• The ρ-weighted majority vote predicts the label receiving the greatest ρ-weighted average of hypothesis votes.Source: §2 · p. 3
• If the majority vote errs, at least half the classifier weight errs, yielding a Markov-based first-order bound through randomized-classifier loss.Source: §2 · p. 3
• PAC-Bayesian analysis converts the randomized classifier’s expected loss into an empirical bound, but this first-order quantity ignores prediction correlations.Source: §2 · p. 3

3 New second order oracle bounds for the majority vote

• The second-order analysis bounds majority-vote risk through expected tandem loss, capturing the probability that two independently drawn hypotheses err simultaneously.The bound follows by applying second-order Markov’s inequality to the randomized classifier’s error and relating the resulting second moment to tandem loss.Source: §3 · p. 3

3.1 A specialized bound for binary classification

• In binary classification, tandem loss can be rewritten using expected randomized-classifier loss and pairwise disagreement, enabling disagreement estimation from unlabeled data.The resulting specialized bound is advantageous when the expected disagreement exceeds the expected loss, but disagreement estimation has a slow convergence rate.Source: §3.1 · pp. 3–4, §3.2 · p. 4

3.2 Comparison with the first order oracle bound

• With identical predictions, the second-order bound can be twice as loose as the first-order bound, while under independent equal errors it is tighter when L(h) < 1/2.The independent-case comparison assumes a large number of hypotheses and ignores the second term in the second-order expression.Source: §3.2 · p. 4
• 4/M^2 versus 2/M: with disjoint error regions and uniform weights, the second-order bound is an order of magnitude tighter than the first-order bound.In this best-case construction, the majority-vote risk is 0 while the second-order bound is 4/M^2.Source: §3.2 · p. 4

3.3 Comparison with the oracle C-bound

• The oracle C-bound is always at least as tight as the new second-order oracle bound, but its denominator terms make estimation and minimization substantially harder.Under independent errors with equal rates below 1/2, the C-bound converges to zero with more classifiers, whereas the new bound converges to 4L(h)^2.Source: §3.3 · pp. 4–5

4.1 A general bound for multiclass classification

• Theorem 9 bounds multiclass weighted-majority-vote loss using empirical tandem losses with a PAC-Bayesian guarantee valid simultaneously over distributions and λ.PAC-Bayes-kl can be tighter, but the λ-form bound is chosen because it is more convenient for minimization.Source: §4.1 · p. 5

4.2 A specialized bound for binary classification

• Theorem 10 bounds binary weighted-majority-vote loss using empirical disagreements estimated from labeled and additional unlabeled inputs.The bound has potential to be tighter when considerable unlabeled data are available and is designed for convenient minimization.Source: §4.2 · p. 6

4.3 Ensemble construction

• Cross-validation or random-forest bagging produces data-dependent ensembles whose validation losses support PAC-Bayesian weighting, with the sample size replaced by the smallest validation-set size.For pairwise tandem losses, overlapping validation sets provide unbiased estimates and determine the corresponding minimum sample size.Source: §4.3 · p. 6

4.4 Comparison of the empirical bounds

• FO has larger validation denominators and lower KL complexity, whereas TND benefits from typically faster tandem-loss convergence; which is preferable depends on the data and hypothesis space.TND’s estimation disadvantage comes from smaller validation-set overlaps, while its advantage comes from Eρ2[L(h,h′)] ≤ Eρ[L(h)].Source: §4.4 · p. 7
• DIS is favored by abundant unlabeled data but is expected to outperform TND only when m > n^2, because disagreement estimation has a slow convergence rate.DIS also estimates both first-order loss and disagreement, requiring a union-bound adjustment.Source: §4.4 · p. 7

Experimental setup

• The evaluation used 100-tree random forests on UCI and LibSVM datasets, with 20% held out for testing and 50 repetitions per experiment.Dataset sizes ranged from 3000 to 70000 points with dimensions below 1000; the reported results use means and standard deviations.Source: §5 · p. 7

Uniform weighting

• TND produced the tightest bound on 5 of 16 datasets and outperformed C-bounds on 4 of 7 binary datasets, although FO was tightest in most cases.The comparison used uniformly weighted random forests; C1 and C2 were unavailable for multiclass datasets.Source: §5 · p. 8, Figure 1 · p. 8

Optimization of the weighting

• Optimizing FO weakened test-set performance on all datasets, whereas optimizing TND avoided this effect and sometimes improved the outcome.Both bounds became tighter after optimization, but their effects on majority-vote loss differed substantially.Source: §5 · pp. 8–9
• FO concentrated optimized weight on a few top trees, while TND distributed weight across multiple trees, reflecting its treatment of voter interactions.The optimized distributions were illustrated for two sample datasets, and the authors interpret the contrast as handling interactions between voters.Source: Figure 2 · p. 8, §5 · p. 9

6 Discussion

• The new bound guides weight optimization without causing the test-error deterioration observed when minimizing the commonly used first-order bound.The authors attribute this to capturing cancellation of errors, the core mechanism of majority voting.Source: §6 · p. 9
• Out-of-bag samples let random forests compute the bound without a dedicated hold-out validation set, making efficient use of the data.Source: §6 · p. 9

Broader impact

• The study provides generalization guarantees for random forests and a method for tuning individual tree weights, which can lead to higher accuracies.The authors describe the result as having high practical relevance because random forests and other ensemble classifiers are frequently used.Source: Broader impact · p. 9
• Rigorous generalization bounds are presented as important because machine-learning models increasingly support decisions affecting society, industry, and individuals.Source: Broader impact · p. 9

A Proof of Lemmas 2 and 4

• The proof of Lemma 2 rewrites the squared expected randomized classification error as a product of two identical expectations.Source: A Proof of Lemmas 2 and 4 · p. 12
• The proof of Lemma 4 selects the relevant expression from the preceding identity and rewrites one factor using the complement of the error indicator.Source: A Proof of Lemmas 2 and 4 · p. 12
• Taking expectation over the data distribution and applying Lemma 2 to the left-hand side yields the next proof relation.Source: A Proof of Lemmas 2 and 4 · p. 12

B An alternative derivation of Theorems 1 and 3 using relaxations of the indicator function

• The first-order relaxation uses 1(w ≥ 0.5) ≤ 2w, while the second-order relaxation uses 1(w ≥ 0.5) ≤ 4w^2.Both relaxations apply to w ∈ [0, 1] and yield the corresponding majority-vote bounds.Source: B An alternative derivation of… · p. 13

C Relation between second order Markov’s and Chebyshev-Cantelli inequalities

• The second-order Markov inequality is shown to be a relaxation of the Chebyshev-Cantelli inequality, so Chebyshev-Cantelli provides the tighter inequality.The comparison is stated for the non-trivial regime where E[X] < ε.Source: C Relation between second order… · p. 14

D A proof of Theorem 6

• The appendix supplies a direct proof of Theorem 6 using the Chebyshev-Cantelli inequality.Source: D A proof of Theorem 6 · p. 14

E Equivalence of Theorem 6 to prior forms of the oracle C-bound

• The C-tandem oracle bound in Theorem 6 is shown to be equivalent to prior oracle C-bound forms, including Laviolette et al.’s formulation [2017].Source: E Equivalence of Theorem 6 to prior… · p. 14, §E.1 · p. 14

E.1 Equivalence to Corollary 1 of Laviolette et al. [2017]

• The equivalence to Laviolette et al.’s oracle C-bound follows through their ω-margin representation and algebraic identities.Source: §E.1 · p. 14

E.2 Equivalence to Theorem 11 of Germain et al. [2015] in binary classification

• Theorem 6 is equivalent in binary classification to Germain et al.’s C1 and C2 oracle bounds [2015].The second line gives the C1 form, and the last line gives the C2 form.Source: §E.2 · p. 15
• Equivalent oracle forms can yield different empirical tightness because expected loss, tandem loss, and disagreement differ in estimation difficulty.Source: §E.2 · p. 15

G Positive semi-definiteness of the matrix of empirical tandem losses

• A common-sample empirical tandem-loss matrix is positive semidefinite, making the Theorem 9 bound convex in ρ for fixed λ.The quadratic tandem term and KL(ρ∥π) are both convex in ρ under this condition.Source: G Positive semi-definiteness of the… · p. 16

G.1 Non positive semi-definite example

• Out-of-bag tandem estimates from different data subsets are not necessarily positive semidefinite; one example has eigenvalues −0.5, 0.5, and 1.5.Consequently, optimization in that setting is expected to converge only to a local minimum.Source: §G.1 · p. 16, G Positive semi-definiteness of the… · p. 16

H Gradient-based minimization of the bounds

• The optimization appendix derives closed-form updates for λ and γ, gradients with respect to ρ, and an alternating minimization procedure for the bounds.Source: H Gradient-based minimization of the… · p. 16, §H.1 · p. 17, §H.2 · p. 17

H.3 Alternating optimization procedure

• The alternating procedure parameterizes ρ with a softmax, optimizes ρ until the bound stabilizes, then recomputes λ and γ when applicable.It starts from uniform ρ and stops when the bound change is below 10^-9.Source: §H.3 · pp. 17–18
• Uniform priors and KL regularization exclude weights exactly equal to 0 or 1 without limiting the optimization procedure.Source: §H.3 · p. 18

I.1 Data sets

• The experiments use UCI, LibSVM, and FASHION-MNIST data sets with 3000 ≤ N ≤ 70000 and d ≤ 1000, evaluating 100-tree forests over repeated train/test splits.Most experiments report means and standard deviations over 50 runs, while the unlabeled-data experiment uses 20 runs per split.Source: I Experiments · p. 18, §I.1 · p. 19

I Experiments

• The appendix supplies bound values, loss statistics, optimization risks, and figures for binary, multiclass, reduced-bagging, and unlabeled-data experiments.Tables I.2–I.7 cover computed bounds, auxiliary statistics, and test risks under alternative weighting procedures.Source: §I.2 · p. 19, §I.4 · p. 23, Table I.2 · p. 28

I.2 Standard uniformly weighted random forests

• TND is tightest on 2 of 7 binary and 3 of 10 multiclass data sets, while FO is tightest on the remainder.TND tends to outperform FO when disagreement is large relative to randomized loss, but tandem-loss estimation uses smaller overlaps than first-order estimation.Source: §I.2 · p. 19, Table I.2 · p. 28

I.3 Standard random forests with optimized weights

• FO minimization reduces its bound more strongly but considerably increases test loss, whereas TND minimization improves the bound more modestly without degrading the classifier.FO concentrates posterior mass on a few top classifiers, diminishing ensemble power; the TND result is supported by the binary and multiclass optimization figures.Source: §I.3 · p. 21, Figure I.7 · p. 21, Figure I.8 · p. 22

I.4 Random forests with reduced bagging vs. full bagging with uniform and optimized weights

• Reduced bagging increases out-of-bag overlap from roughly n/9 to n/3 and improves bounds while causing only a limited change in test risk.Sampling n/2 rather than n points raises out-of-bag sample sizes from roughly n/3 to roughly (2/3)n, with relatively minor impact on uniformly weighted ensemble quality.Source: §I.4 · p. 22, Figure I.13 · p. 26, Figure I.14 · p. 26

I.5 DIS bound vs. TND bound in presence of unlabeled data

• DIS has its greatest advantage over TND when the unlabeled-to-labeled data ratio is largest, after which the gap narrows and TND overtakes DIS in most cases.The experiment varies the labeled fraction r and reports means and standard deviations over 20 runs.Source: §I.5 · p. 23, Figure I.15 · p. 27