Margin Certificates for Voting Classifiers under Mixing Dependence
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 √(trel/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) ≤ 2trel−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 trel. 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.
Related
- Anchor-proofness in Voting with Ranked Ballots
- There can be equitable social welfare orders but no fair voting system
- When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation
- Large player classes and approximately weighted voting
- When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting
BibTeX
@misc{habib2026margin,
title = {{Margin Certificates for Voting Classifiers under Mixing Dependence}},
author = {Adria Binte Habib and Ibne Farabi Shihab},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24166},
eprint = {2610.24166},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24166},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Margin Certificates for Voting Classifiers under Mixing Dependence
AU - Adria Binte Habib
AU - Ibne Farabi Shihab
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.24166
UR - https://arxiv.org/abs/2610.24166
AB - 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 √(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) ≤ 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.
ER -