Margin Certificates for Voting Classifiers under Mixing Dependence

Adria Binte Habib; Ibne Farabi Shihab

cs.LGOct 16, 2026

Margin Certificates for Voting Classifiers under Mixing Dependence

Authors: Adria Binte Habib, Ibne Farabi Shihab

Organizations: Department of Computer Science and Engineering, BRAC University, Bangladesh · Department of Computer Science, Iowa State University, USA

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.

Figures & tables

$\tau$	$n$	$a$	$\mu$	$\delta^{\prime}$	bound	$L(F)$	cov.
$1$	$4000$	$1$	$2000$	$0.050$	$1.73$	$0.123$	$1.00$
$1$	$16000$	$1$	$8000$	$0.050$	$1.04$	$0.123$	$1.00$
$1$	$64000$	$1$	$32000$	$0.050$	$\mathbf{0.69}$	$0.123$	$1.00$
$5$	$4000$	$40$	$50$	$0.024$	$9.16$	$0.137$	$1.00$
$5$	$16000$	$45$	$177$	$0.019$	$5.02$	$0.125$	$1.00$
$5$	$64000$	$50$	$640$	$0.014$	$2.81$	$0.123$	$1.00$

Table 1: Theorem 1 certificate for an AdaBoost convex vote learned on the dependent stream (

|\mathcal{H}|=30

\theta=0.2

\delta=0.05

;

120

streams per cell, coverage Wilson CI half-width

\leq 0.03

). The complete

4\times 3

grid is shown; no cell is omitted. “bound” is the mean full certificate value,

L(F)

the held-out risk, “cov.” the fraction of streams with

L(F)\leq

bound. Coverage is

1.00

everywhere. Exactly one cell is nonvacuous (

\tau=1

n=64000

Dataset	Quantity	$\tau=1$	$5$	$25$	$100$
CIFAR-10	$\|\widehat{L}-L\|\sqrt{n}$	$0.39$	$0.49$	$0.88$	$1.53$
(error $0.62$ )	i.i.d. coverage	$0.96$	$0.87$	$0.63$	$0.35$
	corrected coverage	$0.96$	$1.00$	$1.00$	$1.00$
MNIST	$\|\widehat{L}-L\|\sqrt{n}$	$0.41$	$0.59$	$1.09$	$1.99$
(error $0.46$ )	i.i.d. coverage	$0.94$	$0.82$	$0.53$	$0.34$
	corrected coverage	$0.94$	$1.00$	$1.00$	$1.00$

Table 2: Class-Markov stress test on fixed nine-member votes (

300

streams per cell; Wilson

95\%

CIs have half-width

\leq 0.06

). Top two blocks: weak CNNs (

62\%

46\%

error). Bottom: competent ResNet-18 CIFAR-10 ensemble (

6\%

error), whose rich margin distribution (

94\%

positive, mean

0.85

) makes the Theorem 1 certificate nonvacuous at practical

n

. The corrected intervals use the known simulation dependence parameter; coverage is a calibration diagnostic and the width ratio is the designed cost of the correction.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Result	Dependence	Predictor	Distinguishing feature
Mohri–Rostamizadeh	stationary $\beta$ -mixing	learned class	general Rademacher margin bound
Ralaivola et al.	non-i.i.d.; $\beta$ -mixing application	posterior/vote	PAC-Bayes route
Theorem 1	stationary $\beta$ -mixing	learned convex vote	finite-base-class complexity and explicit coupling budget
Theorem 3	stationary $\beta$ -mixing	theorem-dependent	transfers any i.i.d. event to a spaced sample
Corollary 4 and Theorem 8	finite-state reversible Markov	fixed vote	clean spectral rate and matching dependence exponent

Appendix

Table 3: Positioning the paper’s results (main-paper Theorem 1, Theorem 3, Corollary 4, and Theorem 8) against the closest dependent-data routes.

$\tau$	$1$	$5$	$25$	$100$
mean $\|\widehat{L}-L\|\sqrt{n}$	$0.393$	$0.471$	$0.673$	$1.382$
CV across $n$	$0.152$	$0.103$	$0.109$	$0.198$
log–log slope in $n$	$-0.544$	$-0.560$	$-0.442$	$-0.439$
$R^{2}$ of slope fit	$0.970$	$0.997$	$0.990$	$0.935$

Appendix

Table 4: Fixed-vote scaling on the persistent-cluster stream. The fitted exponents are close to the

-1/2

prediction. The CV uses the population standard deviation over the four sample-size summaries.

Panel of Figure 1 — Figure 1: Squared mean rescaled gap against the persistence parameter. An affine fit is more faithful to the exact variance decomposition than a pure line through the origin in $\sqrt{\tau}$ .

Panel of Figure 2 — Figure 2: Reported fixed-vote mean gap versus sample size. The dashed line is a slope reference, not a fitted constant. Fitted slopes range from $-0.56$ to $-0.44$ .

Experiment	Quantity reported	Interpretation
Certificate coverage	i.i.d. versus corrected interval coverage	naive interval under-covers as persistence grows; corrected interval is conservative
Dependence misspecification	coverage versus $\hat{\tau}/\tau$	sensitivity study for one generator, not a validity theorem
Block-length ablation	coverage versus block length	shorter blocks retain dependence; finite-sample calibration remains imperfect
Trained ensemble	induced class-Markov stream	controlled stress test, not natural dependence
Intrinsic-dependence stream	ordered versus shuffled coverage	dependence intrinsic to the latent process, not injected
UCI HAR (real sensor)	ordered versus shuffled coverage; adaptive certificate versus batch length	naturalistic evidence, fixed-vote regime only

Appendix

Table 5: Supplementary studies and the strongest interpretation supported by each design.

ratio $\|\widehat{L}-L\|/\sqrt{\tau/n}$
	$n$
$\tau$	$500$	$2000$	$8000$	$32000$
$1$	$0.018913$	$0.010208$	$0.0033125$	$0.002226$
$5$	$0.022563$	$0.011781$	$0.0050083$	$0.0022539$
$25$	$0.024937$	$0.015054$	$0.0085070$	$0.0039052$
$100$	$0.045933$	$0.038908$	$0.013722$	$0.0085642$

Appendix

Table 6: Mean fixed-vote gaps and their

\sqrt{\tau/n}

normalization for every cell.

$M$	$1$	$3$	$5$	$9$	$15$
mean voting margin	$-0.22$	$0.04$	$0.03$	$0.08$	$0.11$
margin mass below $0$	$0.61$	$0.55$	$0.55$	$0.50$	$0.48$
generalization gap	$0.029$	$0.022$	$0.025$	$0.021$	$0.020$

Appendix

Table 7: Descriptive margin sweep at fixed

\tau=25

on MNIST. As

M

grows the voting margin sharpens (its mean rises from

-0.22

toward

+0.11

, and the below-zero mass falls from

0.61

0.48

) and the realized gap shrinks; the correlation between the gap and the mean margin is

-0.94

. The below-zero mass equals the stationary error, so the

M=9

value

0.50

matches the main study’s MNIST error

0.46

up to the difference between two independently trained ensembles.

$\lambda$	$0$	$0.5$	$0.8$	$0.9$	$0.96$
$(1+\lambda)/(1-\lambda)$	$1.0$	$3.0$	$9.0$	$19.0$	$49.0$
measured variance inflation	$1.00$	$3.02$	$9.06$	$19.56$	$48.03$

Appendix

Table 8: Variance-inflation experiment on the sticky-refresh family. The exact formula is justified for this family, not for an arbitrary reversible chain and arbitrary statistic.

$\tau$	$1$	$5$	$25$	$100$
I.i.d. interval coverage	$0.944$	$0.912$	$0.601$	$0.436$
Corrected interval coverage	$0.944$	$1.000$	$1.000$	$1.000$
Corrected interval half-width	$0.0145$	$0.0340$	$0.0747$	$0.1498$
Corrected/i.i.d. width ratio	$1.0$	$2.2$	$5.0$	$10.0$

Appendix

Table 9: Coverage and interval half-width at nominal

0.95

over

2000

streams of length

n=4000

(Wilson

95\%

binomial intervals on each coverage entry have half-width

\leq 0.022

). The corrected interval is conservative; the width ratio equals the built-in dependence multiplier

\sqrt{\tau}

$\ell/\tau$	$0.25$	$0.5$	$1$	$2$	$4$
blocks	$666$	$333$	$160$	$80$	$40$
coverage	$0.699$	$0.746$	$0.814$	$0.872$	$0.909$
mean half-width	$0.0180$	$0.0203$	$0.0238$	$0.0274$	$0.0302$

Appendix

Table 10: Block-length ablation at

\tau=25

n=4000

. Blocks shorter than

\tau

retain dependence and undercover; coverage rises toward nominal as

\ell

exceeds

\tau

, at the cost of fewer blocks and wider intervals.

true simulation parameter $\tau$	$1$	$5$	$25$	$100$
spectral plug-in	$1.0$	$5.8$	$36.5$	$247$
autocorrelation plug-in	$1.0$	$1.1$	$1.1$	$1.1$
coverage, spectral plug-in	$0.92$	$1.00$	$1.00$	$1.00$
coverage, autocorrelation plug-in	$0.92$	$0.87$	$0.65$	$0.33$

Appendix

Table 11: Exploratory plug-in study on the induced CIFAR-10 class-Markov stream.

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 561 papers

May 7, 2026

When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation

Majority voting is one of the few black-box interventions that can improve a fixed stochastic predictor: repeated access can be cheaper than changing a high-capability model. Classical fixed-competence theory makes this intervention look monotone -- more votes help above the majority threshold and hurt below it. We show that this picture is fundamentally incomplete. Under the de Finetti representation for exchangeable repeated correctness, voting is governed by a latent distribution of per-example correctness probabilities. Even simple latent mixtures can generate sharply different voting curves, including nonmonotone behavior and, in an explicit construction, infinitely many trend changes. The full latent law determines the curve, but the curve does not determine the law. The exact object recovered by voting is a signed voting signature: at each binomial variance scale, it records excess latent mass above rather than below the majority threshold. Our main theorem proves that the complete odd-budget curve and this signature are equivalent: the curve increments are signed Hausdorff moments, and the full curve recovers the signature uniquely. This viewpoint explains shape phenomena, branch-symmetric nonidentifiability, realizability, variation, and endpoint rates. It also separates estimation regimes: direct per-example success-probability information targets the full signature, whereas fixed-depth grouped labels reveal only a finite prefix.

Yi Liu

York University

Statistical Learning Theory Majority Voting

Ask PDF

Apr 15, 2026

Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence

Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners. When training data exhibits Markov dependence, as in time-series forecasting, reinforcement learning (RL) replay buffers, and spatial grids, this classical guarantee degrades in ways that existing theory does not fully quantify. We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting, together with an adaptive algorithm that matches the rate on a graph-regular subclass. We first establish an information-theoretic lower bound for stationary, reversible, geometrically ergodic chains in fixed ambient dimension, showing that no measurable estimator can achieve excess classification risk better than

Ω(\sqrt{\Tmix/n})

. We then prove that, on the AR(1) witness subclass underlying the lower-bound construction, dependence-agnostic uniform bagging is provably suboptimal with excess risk bounded below by

Ω(\Tmix/\sqrt{n})

, exhibiting a

\sqrt{\Tmix}

algorithmic gap. Finally, we propose adaptive spectral routing, which partitions the training data via the empirical Fiedler eigenvector of a dependency graph and achieves the minimax rate

\mathcal{O}(\sqrt{\Tmix/n})

up to a lower-order geometric cut term on a graph-regular subclass, without knowledge of

\Tmix

. Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions. Consequences for deep RL target variance, scalability via Nyström approximation, and bounded non-stationarity are developed as supporting material in the appendix.

Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma

Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University

Ensemble Learning Majority Voting Classification Minimax Estimation

Ask PDF

Oct 7, 2026

Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets

Signals that predict whether a chain-of-thought (CoT) trace is correct are compared by AUC, but deploying one requires a threshold with a guarantee. We ask what distribution-free selective guarantees deliver for CoT verifiers at realistic calibration budgets of tens to a few hundred labelled problems, using seven open models, five verifier signals and 37,000 graded traces. The central observation is validity by abstention: an

(α,δ)

-valid procedure that issues a certificate with probability

P_{\rm fire}

bounds the failure probability of an issued certificate only by

δ/P_{\rm fire}

, so a certificate that rarely fires can be valid and wrong every time it is used. In a simulation with known risk the standard certificate fails in at most 0.3% of calibration draws but in up to 69% of those in which it fires. A certification floor and a lattice condition for Benjamini-Hochberg conformal selection explain why certificates abstain at these budgets, and the data bear them out: the standard certificate returns nothing or a large accepted set, and an unreadable residual-stream probe buys two to three times the coverage of the readable signals, an edge a cross-fitted reconstruction cannot recover linearly from the readable features. We then give a floor-started fixed-sequence certificate, valid without monotonicity assumptions, that covers more than the Bonferroni certificate on every model-signal pair and raises coverage at the non-vacuous target

0.75π_0

from 0.05 to 0.16, although the floor keeps absolute coverage small. Finally, a certificate cannot see what matters after deployment: under benchmark shift the error among accepted traces tracks the new task's base error, and under best-of-

n

selection against the verifier it rises past the target while the empirical failure frequency stays below

δ

, because abstention absorbs the failures.

Arjun Balaji

Columbia University

Selective Prediction Conformal Prediction LLM Abstention CoT Evaluation FDR Control

Ask PDF

Abstract

Statistical Learning Theory

Explore similar work

When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation

Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence

Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets