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
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.
Figures & tables
τ
n
a
μ
δ′
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
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 ( ∣H∣=30 , θ=0.2 , δ=0.05 ; 120 streams per cell, coverage Wilson CI half-width ≤0.03 ). The complete 4×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)≤ bound. Coverage is 1.00 everywhere. Exactly one cell is nonvacuous ( τ=1 , n=64000 ).
Dataset
Quantity
τ=1
5
25
100
CIFAR-10
∣L−L∣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
∣L−L∣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 ≤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 β -mixing
learned class
general Rademacher margin bound
Ralaivola et al.
non-i.i.d.; β -mixing application
posterior/vote
PAC-Bayes route
Theorem 1
stationary β -mixing
learned convex vote
finite-base-class complexity and explicit coupling budget
Theorem 3
stationary β -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.
τ
1
5
25
100
mean ∣L−L∣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
R2 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.
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 τ .
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 τ^/τ
sensitivity study for one generator, not a validity theorem
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.
n
τ
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
ratio ∣L−L∣/τ/n
Appendix
Table 6: Mean fixed-vote gaps and their τ/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 τ=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 to 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.
λ
0
0.5
0.8
0.9
0.96
(1+λ)/(1−λ)
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.
τ
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 ≤0.022 ). The corrected interval is conservative; the width ratio equals the built-in dependence multiplier τ .
ℓ/τ
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 τ=25 , n=4000 . Blocks shorter than τ retain dependence and undercover; coverage rises toward nominal as ℓ exceeds τ , at the cost of fewer blocks and wider intervals.
true simulation parameter τ
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 studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.