betaFeedback

WorksComputer Science

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)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\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)n/τ_{int}(g), with τint(g)≤2trel−1τ_{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)τ_{int}(g) rather than the worst-case trelt_{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.

Introduction

Voting classifiers—bagging Breiman [6], random forests Breiman [7], boosting Freund and Schapire [10]; Schapire and Freund [43], and modern deep ensembles—aggregate many predictors into a single vote. Their theory is unusually mature because the central quantity is not only the training error but the distribution of signed margins. For a real-valued vote score FF, the margin yF(x)yF(x) records both correctness and confidence. The classical analysis of Schapire et al. [44] used this distribution to explain why boosting may continue to improve test performance after the training error reaches zero, and subsequent work refined empirical-margin bounds and clarified their limitations [20, 41, 11]. PAC-Bayesian analyses provide a complementary route through the Gibbs classifier, margin moments, and majority-vote risk [25, 12, 33, 26]. Recent work continues to sharpen the i.i.d. theory for finite voting classes [17, 14].

The data used to evaluate or train an ensemble are often dependent. Sensor streams contain long temporal runs, session data arrive in bursts, labels may be clustered by subject or location, and replay buffers inherit the dependence of an underlying trajectory. In such settings, a sample of length nn need not contain nn independent pieces of information. The informal response is to replace nn by an effective sample size, but that slogan hides the hard questions: which dependence notion is assumed, whether the classifier is fixed or selected from the same sample, whether the empirical margin term is evaluated on the full stream or a thinned subsequence, and how the coupling error enters the confidence level.

There is already substantial dependent-data generalization theory—Rademacher bounds for stationary β\beta-mixing processes [36], non-i.i.d. PAC-Bayes [40], and stability, empirical-process, and weak-dependence analyses [51, 37, 48, 24, 9]. Our contribution is therefore not a first theory of margins under dependence, but a focused voting-classifier treatment that makes four statements precise and keeps them separate.

For a vote learned from a finite base class, we derive an explicit β\beta-mixing margin certificate that displays the block count, spacing, class complexity, margin threshold, and coupling failure probability rather than hiding them in a residual. For any sharper i.i.d. voting-margin theorem, we give a black-box transfer principle: apply it to deterministically spaced observations and add the exact mixing-coupling budget. For a vote fixed before the correlated stream is drawn, reversible-chain concentration gives the cleaner trel/n\sqrt{t_{\mathrm{rel}}/n} rate with the correct statistic-specific constant, and a matching lower bound over a sticky-refresh family shows the exponent is unavoidable. Finally, when the dependence scale is unknown, a data-driven batch-means certificate is finite-sample valid without knowledge of trelt_{\mathrm{rel}} or τint\tau_{\mathrm{int}} and is rate-optimal among dependence-agnostic procedures, matched by a corresponding lower bound (Theorems 6 and 7).

These distinctions matter empirically, and our experiments separate along them. One study computes the full Theorem 1 certificate for a vote selected from the dependent stream, so the uniform-complexity term is genuinely in force; the remaining studies evaluate votes fixed before the correlated stream is drawn and therefore probe fixed-statistic concentration. The main paper reports the learned-vote certificate, the statistic-specific effective-sample-size study, and an induced class-Markov deep-ensemble stress test; a persistent-cluster rate experiment, a margin sweep, a coverage study, a block-length ablation, and a dependence-estimation study are given in the supplement, each interpreted at the level its design supports. In particular, the synthetic generator contains ordinary Bernoulli noise as well as persistence, so its long-run variance has an i.i.d. floor plus a dependence component, and the deep-ensemble study uses trained classifiers but induces the evaluation dependence artificially—a stress test, not evidence from naturally dependent deployment data.

Let Zt=(Xt,Yt)∈Z=X×{−1,+1}Z_t = (X_t, Y_t) \in\mathcal{Z} = \mathcal{X} \times\{-1,+1\} be a stationary sequence with marginal law PP. A finite base class H⊆[−1,1]X\mathcal{H} \subseteq[-1,1]^{\mathcal{X}} induces the convex voting class

V(H)={F(x)=∑h∈Hwhh(x):wh≥0, ∑hwh=1}.\mathcal{V}(\mathcal{H}) = \left\{F(x) = \sum_{h \in\mathcal{H}} w_h h(x) : w_h \ge0,\ \sum_h w_h = 1\right\}.

The classifier associated with the score FF is sign⁡F\operatorname{sign} F, but the theory is written in terms of the real-valued score. The signed margin is

MF(x,y)=yF(x)∈[−1,1].M_F(x,y) = yF(x) \in[-1,1].

We define classification risk by L(F)=P(MF≤0)L(F) = P(M_F \le0), counting ties as errors, and the empirical margin-tail frequency at threshold 0<θ≤10 < \theta\le1 by

T^S(F,θ)=1m∑t=1m1{MF(Zt)≤θ}.\widehat{T}_S(F,\theta) = \frac{1}{m}\sum_{t=1}^{m} \mathbf{1}\{M_F(Z_t) \le\theta\}.

Keeping FF separate from sign⁡F\operatorname{sign} F is essential: thresholding a sign-valued classifier at any 0<θ<10 < \theta< 1 would collapse the margin event to ordinary misclassification.

Definition 1 (β\beta-mixing). For a stationary sequence, let Tij\mathcal{T}_i^j be the sigma-field generated by Zi,…,ZjZ_i,\ldots,Z_j. Its absolute-regularity coefficient is

β(k)=sup⁡nE[sup⁡A∈T−∞n∣P(A∣Tn+k∞)−P(A)∣].\beta(k) = \sup_n \mathbb{E}\left[\sup_{A \in\mathcal{T}_{-\infty}^n} \left|\mathbb{P}(A \mid\mathcal{T}_{n+k}^{\infty}) - \mathbb{P}(A)\right|\right].

The process is β\beta-mixing when β(k)→0\beta(k) \to0.

A Markov chain with transition kernel KK is called lazy when K(z,{z})≥1/2K(z,\{z\}) \ge1/2 for every state zz. Laziness is not required for the fixed-vote concentration result below; it is used only for the simple nonnegative-spectrum upper bound on integrated autocorrelation time in Proposition 5.

The blocking method partitions a length-m=2μam=2\mu a sample into 2μ2\mu blocks of length aa and compares the μ\mu odd blocks with independent copies [51, 36]; the comparison error scales with (μ−1)β(a)(\mu-1)\beta(a) and is not optional (a fixed-tolerance mixing time still incurs constant coupling error at every boundary, which does not sum to a valid high-probability bound; see the supplementary material).

The i.i.d. margin literature begins with the boosting-margin theorem [44], continues through empirical-margin-distribution analyses [20], critiques and refinements [41, 11], and broader Rademacher and learning-theoretic treatments [3, 50, 46, 38]. PAC-Bayes gives a second line of voting theory through the C-bound and its descendants [35, 45, 8, 34, 26, 25, 12, 49, 15, 33]. Majority-of-Three is relevant as an optimal PAC-learning result, but it is not an optimal-constant margin theorem and is not used as the reduction target here [1, 16].

For dependent observations, the closest theoretical baseline is Mohri and Rostamizadeh [36], which develops Rademacher bounds for non-i.i.d. processes and includes an explicit margin application under stationary β\beta-mixing. Ralaivola, Saffran, and Stempfel [40] develops non-i.i.d. PAC-Bayes bounds with stationary mixing applications. Related results study stability for φ\varphi- and β\beta-mixing processes [37], stationary empirical processes [51, 48], non-stationary generalization [24], and weak dependence under Dobrushin-type conditions [9]. Markov-chain concentration can instead exploit spectral or coupling structure [39, 31, 13, 32, 42, 22, 21, 19]. Our uniform learned-vote theorem specializes the first of these routes—the β\beta-mixing Rademacher machinery—to a finite base class, while our fixed-vote analysis builds on the second, Markov-chain spectral concentration.

For 0<θ≤10 < \theta\le1, define the clipped ramp

ϕθ(u)=min⁡{1,max⁡{0,1−u/θ}}.\phi_\theta(u)=\min\{1,\max\{0,1-u/\theta\}\}.

It satisfies 1{u≤0}≤ϕθ(u)≤1{u≤θ}\mathbf{1}\{u \le0\} \le\phi_\theta(u) \le\mathbf{1}\{u \le\theta\} and is 1/θ1/\theta-Lipschitz.

The constants in our learned-vote theorem inherit the empirical Rademacher theorem of Mohri and Rostamizadeh [36] (their Theorem 2), which we restate in their exact normalisation—including the absolute value and the factor 2/r2/r—in the supplementary material. For a sample of length m=2μam=2\mu a partitioned into 2μ2\mu consecutive blocks of length aa, it bounds PScP_{\mathcal{S}}c by P^Sc\widehat{P}_{\mathcal{S}}c, plus an empirical Rademacher term on the fixed-position singleton sample drawn from the μ\mu odd blocks, plus 3Mlog⁡(4/δ′)/2μ3M\sqrt{\log(4/\delta')/2\mu}, for any class bounded by MM and any δ′=δ−4(μ−1)β(a)>0\delta'=\delta-4(\mu-1)\beta(a)>0. The centred ramp class used below lies in [−1,0][-1,0], so M=1M=1 under either the sup-norm or the range interpretation.

Theorem 1 (Finite-class voting-margin certificate). Let S=(Z1,…,Zm)S=(Z_1,\ldots,Z_m) be drawn from a stationary β\beta-mixing process. Let a,μ∈Na,\mu\in\mathbb{N} and 0<θ≤10<\theta\le1 be chosen independently of SS, with m=2μam=2\mu a. For 0<δ<10<\delta<1, define

δ′=δ−4(μ−1)β(a).\delta'=\delta-4(\mu-1)\beta(a).

If δ′>0\delta'>0, then with probability at least 1−δ1-\delta, every F∈V(H)F\in\mathcal{V}(\mathcal{H}) satisfies

L(F)≤T^S(F,θ)+4θ2log⁡(2∣H∣)μ+3log⁡(4/δ′)2μ.(1)L(F)\le\widehat{T}_S(F,\theta)+\frac{4}{\theta}\sqrt{\frac{2\log(2|\mathcal{H}|)}{\mu}}+3\sqrt{\frac{\log(4/\delta')}{2\mu}}. \tag*{(1)}

The theorem uses the full-sample empirical margin tail but pays complexity according to the number μ\mu of approximately independent blocks, with no undefined residual term. The proof centers before contracting, because the empirical Rademacher complexity of Mohri and Rostamizadeh [36] carries an absolute value.

Briefly: the centered ramp class Cθ={gF−1:F∈V(H)}\mathcal{C}_\theta=\{g_F-1:F\in\mathcal{V}(\mathcal{H})\} takes values in [−1,0][-1,0], so applying the imported lemma cancels the constant shift; the Ledoux–Talagrand contraction inequality (Ledoux and Talagrand [28], Theorem 4.12) then removes the 1/θ1/\theta-Lipschitz ramp, and Massart’s lemma on the symmetrized base class bounds R^Sμ(M)≤22log⁡(2∣H∣)/μ\widehat{\mathfrak{R}}_{S_\mu}(\mathcal{M})\le2\sqrt{2\log(2|\mathcal{H}|)/\mu}, giving the stated bound after L(F)≤PgFL(F)\le P g_F and P^SgF≤T^S(F,θ)\widehat{P}_Sg_F\le\widehat{T}_S(F,\theta). The complete derivation is in the supplementary material.

The statement is simultaneous over the uncountable simplex of vote weights; measurability is benign because H\mathcal{H} is finite.

The theorem fixes one threshold and one block length before seeing the data; a finite union bound over a predeclared grid of (a,θ)(a,\theta) pairs, with a split confidence budget, then lets the smallest valid certificate be selected after observing the data, whereas an unrestricted continuum search or a data-derived block length requires a separate argument (details in the supplementary material).

The block-length tradeoff is thus explicit: small aa gives more blocks but a larger coupling penalty, large aa the reverse. A practical certificate picks aa from a predeclared grid (with the confidence allocation above) or from known mixing information before seeing the sample.

Corollary 2 (Geometric mixing). Suppose β(k)≤Bexp⁡(−k/τ)\beta(k)\le B\exp(-k/\tau) for B,τ>0B,\tau>0. Let

B‾=B∨1,τ‾=τ∨1,\overline{B}=B\vee1,\qquad\overline{\tau}=\tau\vee1,

fix 0<δ≤1/20<\delta\le1/2 and 0<θ≤10<\theta\le1 independently of the data, and set

a=max⁡{1,⌈τ‾log⁡(8B‾nδ)⌉},μ=⌊n2a⌋,m=2μa.a=\max\left\{1,\left\lceil\overline{\tau}\log\left(\frac{8\overline{B}n}{\delta}\right)\right\rceil\right\}, \qquad \mu=\left\lfloor\frac{n}{2a}\right\rfloor,\qquad m=2\mu a.

If n≥4an\ge4a, then, with probability at least 1−δ1-\delta, uniformly over F∈V(H)F\in\mathcal{V}(\mathcal{H}),

L(F)≤T^S1:m(F,θ)+Cτ‾log⁡(8B‾n/δ)n(log⁡(2∣H∣)θ+log⁡4δ),(2)L(F)\le\widehat{T}_{S_{1:m}}(F,\theta) +C\sqrt{\frac{\overline{\tau}\log(8\overline{B}n/\delta)}{n}} \left(\frac{\sqrt{\log(2|\mathcal{H}|)}}{\theta}+\sqrt{\log\frac{4}{\delta}}\right), \tag*{(2)}

where CC is universal.

The guards B‾≥1\overline{B}\ge1, τ‾≥1\overline{\tau}\ge1, and a≥1a\ge1 preserve the unavoidable i.i.d. floor and prevent an invalid zero or negative block length. The empirical term is computed on the prefix S1:mS_{1:m} of length m=2μam=2\mu a; the remaining n−mn-m observations are not silently included. The logarithm is not hidden. It is the price of obtaining the result by a pure coupling/blocking argument under geometric β\beta-mixing. Cleaner trel/n\sqrt{t_{\mathrm{rel}}/n} rates are available for fixed bounded statistics under stronger Markov-chain structure, which we treat next for reversible chains.

Black-box transfer of an i.i.d. margin theorem

The preceding theorem gives a simple explicit bound, but newer i.i.d. voting-margin theorems can be sharper. The next result transfers any such theorem without re-proving its internal argument.

Theorem 3 (Spaced-sample transfer). Assume Z\mathcal{Z} is a standard Borel space. Let S(a)=(Z1,Z1+a,…,Z1+(q−1)a)S^{(a)}=(Z_1,Z_{1+a},\ldots,Z_{1+(q-1)a}) be qq regularly spaced observations from a stationary β\beta-mixing process, and let S~∼Pq\widetilde{S}\sim P^q be qq independent observations from the same stationary marginal PP. For every event E⊆Zq\mathcal{E}\subseteq\mathcal{Z}^q measurable in these qq observations alone,

∣P(S(a)∈E)−P(S~∈E)∣≤(q−1)β(a).\left|\mathbb{P}\left(S^{(a)}\in\mathcal{E}\right)-\mathbb{P}\left(\widetilde{S}\in\mathcal{E}\right)\right|\le(q-1)\beta(a).

Consequently, if an i.i.d. voting-margin theorem has a failure event measurable in the qq i.i.d. observations alone and holds under PqP^q with failure probability at most η\eta, the identical sample-measurable statement holds on S(a)S^{(a)} with failure probability at most η+(q−1)β(a)\eta+(q-1)\beta(a). Statements that reference empirical quantities computed from observations outside S(a)S^{(a)} are not covered by this transfer.

Algorithm 1 A valid spacing choice for a black-box margin certificate

Require: stationary stream Z1:nZ_{1:n}, confidence δ\delta, known upper bound b(k)≥β(k)b(k) \ge\beta(k)

Require: an i.i.d. certificate procedure Cert⁡iid(S,η)\operatorname{Cert}_{\mathrm{iid}}(S,\eta)

  1. choose aa and q=1+⌊(n−1)/a⌋q = 1+\lfloor(n-1)/a\rfloor such that (q−1)b(a)≤δ/2(q-1)b(a) \le\delta/2

  2. form S(a)=(Z1,Z1+a,…,Z1+(q−1)a)S^{(a)} = (Z_1, Z_{1+a}, \ldots, Z_{1+(q-1)a})

  3. return Cert⁡iid(S(a),δ/2)\operatorname{Cert}_{\mathrm{iid}}(S^{(a)},\delta/2)

This theorem is intentionally algebra-free: the transferred statement may be a classical margin inequality, a PAC-Bayes certificate, or a recent sharper voting-margin theorem (Høgsgaard Møller and Green Larsen [17]; Green Larsen and Schalburg [14]). The price is that the empirical term is evaluated on the spaced sample. The proof is a repeated β\beta-mixing coupling argument and is given in the supplementary material.

Algorithm 1 fixes two flaws in naive blocking implementations. Representatives are separated by a deterministic gap aa rather than selected arbitrarily from adjacent blocks, and the coupling error is explicitly budgeted. Estimating β\beta or a spectral gap from the same data is a separate statistical problem; the theorem does not treat a plug-in estimate as known.

Reversible Chains: Fixed Votes, Constants, and a Lower Bound

Apart from the learned-vote study of Theorem 1, the experiments in this paper evaluate votes that are fixed before the correlated test stream is drawn. In that regime there is no uniform model-selection complexity, and the dependence rate can be stated directly in terms of a Markov-chain relaxation time.

Corollary 4 (Fixed-vote reversible-chain certificate). Let Z1,…,ZnZ_1,\ldots,Z_n be a stationary finite-state, irreducible, aperiodic, and reversible Markov chain. Let λ2<1\lambda_2 < 1 be its second-largest eigenvalue, define

λ⋆=max⁡{λ2,0},trel=(1−λ⋆)−1,\lambda_\star= \max\{\lambda_2,0\}, \qquad t_{\mathrm{rel}} = (1-\lambda_\star)^{-1},

and let the pair (F,θ)(F,\theta), with θ∈(0,1]\theta\in(0,1], be fixed independently of the chain. Then, for any 0<δ<10 < \delta< 1, with probability at least 1−δ1-\delta,

L(F)≤T^(F,θ)+trellog⁡(2/δ)n.L(F) \le\widehat{T}(F,\theta) + \sqrt{\frac{t_{\mathrm{rel}}\log(2/\delta)}{n}}.

The positive-part eigenvalue is deliberate: the Hoeffding inequality of León and Perron (2004) applies to finite ergodic reversible chains in stationarity without a laziness assumption and depends on λ⋆=max⁡{λ2,0}\lambda_\star= \max\{\lambda_2,0\}, which the irreducibility and aperiodicity assumptions make explicit. Stationarity is load-bearing—a nonstationary start generally incurs an initialization penalty (Paulin [39])—and total-variation mixing time, though related to the spectral parameters, is not identical to them (Levin and Peres [30]).

A fixed statistic has an even more precise asymptotic dependence constant.

Proposition 5 (Statistic-specific integrated autocorrelation time). Let gt=g(Zt)=1{MF(Zt)≤θ}g_t = g(Z_t) = \mathbf{1}\{M_F(Z_t) \le\theta\} be the thresholded-margin statistic of a fixed vote under a stationary process. Write σg2=Var⁡(gt)>0\sigma_g^2 = \operatorname{Var}(g_t) > 0 and ρk=Corr⁡(g0,gk)\rho_k = \operatorname{Corr}(g_0,g_k). Stationarity alone gives

Var⁡(1n∑t=1ngt)=σg2n[1+2∑k=1n−1(1−kn)ρk].\operatorname{Var}\left(\frac{1}{n}\sum_{t=1}^{n}g_t\right) = \frac{\sigma_g^2}{n}\left[1+2\sum_{k=1}^{n-1}\left(1-\frac{k}{n}\right)\rho_k\right].

If ∑k≥1∣ρk∣<∞\sum_{k\geq1}|\rho_k| < \infty, the bracket converges to

τint(g)=1+2∑k≥1ρk.\tau_{\mathrm{int}}(g)=1+2\sum_{k\geq1}\rho_k.

If, in addition, the process is a stationary lazy reversible Markov chain whose nontrivial spectrum is contained in [0,λ⋆][0,\lambda_\star] for some λ⋆<1\lambda_\star< 1, then the summability condition is automatic and

τint(g)=∫1+λ1−λ dνf(λ)≤1+λ⋆1−λ⋆=2trel−1,\tau_{\mathrm{int}}(g)=\int\frac{1+\lambda}{1-\lambda}\,d\nu_f(\lambda) \leq\frac{1+\lambda_\star}{1-\lambda_\star}=2t_{\mathrm{rel}}-1,

where f=(g−πg)/σgf=(g-\pi g)/\sigma_g and νf\nu_f is its spectral probability measure. Equality holds exactly when νf\nu_f is concentrated on the singleton {λ⋆}\{\lambda_\star\}. For the sticky-refresh kernel P=(1−α)I+α1πTP=(1-\alpha)I+\alpha\mathbf{1}\pi^\mathsf{T}, every centered statistic satisfies Pf=(1−α)fPf=(1-\alpha)f, so τint(g)=(2−α)/α=2τ−1\tau_{\mathrm{int}}(g)=(2-\alpha)/\alpha=2\tau-1 when α=1/τ\alpha=1/\tau, whether or not the chain is lazy.

Thus n/τint(g)n/\tau_{\mathrm{int}}(g) is a statistic-specific asymptotic effective sample size; it is not generally determined by the chain’s second eigenvalue alone. The supplementary material gives the spectral-measure proof.

The propositions above assume trelt_{\mathrm{rel}} or τint(g)\tau_{\mathrm{int}}(g) is known. Estimating the dependence scale from the same stream and maintaining validity is a separate problem, which the following theorem solves.

Theorem 6 (Adaptive certificate with unknown dependence). Let Z1,…,ZnZ_1,\ldots,Z_n be a stationary finite-state, irreducible, aperiodic, and reversible Markov chain whose nontrivial spectrum is nonnegative (as in Corollary 4 and throughout our experiments), and let gt=g(Zt)∈[0,1]g_t=g(Z_t)\in[0,1] be a fixed statistic with σg2=Var⁡(gt)>0\sigma_g^2=\operatorname{Var}(g_t)>0. Split the stream into BB non-overlapping batches of length L=⌊n/B⌋L=\lfloor n/B\rfloor; write gˉb=(1/L)∑t∈batch bgt\bar g_b=(1/L)\sum_{t\in\mathrm{batch}\ b}g_t for the bb-th batch mean. Define

σ^BM2=LB−1∑b=1B(gˉb−gˉ)2,gˉ=1B∑b=1Bgˉb,\widehat{\sigma}_{BM}^{2}=\frac{L}{B-1}\sum_{b=1}^{B}(\bar g_b-\bar g)^2,\qquad \bar g=\frac{1}{B}\sum_{b=1}^{B}\bar g_b,

and the adaptive half-width

wnad=tB−1,α/2σ^BMBL,w_n^{\mathrm{ad}}=t_{B-1,\alpha/2}\frac{\widehat{\sigma}_{BM}}{\sqrt{BL}},

where tB−1,α/2t_{B-1,\alpha/2} is the upper-α/2\alpha/2 quantile of the Student tt-distribution with B−1B-1 degrees of freedom. Write τmin⁡=min⁡{τ,π}\tau_{\min}=\min\{\tau,\pi\} and Cπ=12(1−πmin⁡)/πmin⁡C_\pi=\frac{1}{2}\sqrt{(1-\pi_{\min})/\pi_{\min}}, so that β(k)≤Cπe−k/trel\beta(k)\leq C_\pi e^{-k/t_{\mathrm{rel}}}. Then

P(∣gˉ−E[gt]∣>wnad)≤α+ΔB,L.\mathbb{P}\left(\left|\bar g-\mathbb{E}[g_t]\right|>w_n^{\mathrm{ad}}\right)\leq\alpha+\Delta_{B,L}.

where the remainder ΔB,L=ΔB,Ldep+ΔBnorm\Delta_{B,L} = \Delta^{\mathrm{dep}}_{B,L} + \Delta^{\mathrm{norm}}_{B} collects the residual dependence between batch means and the normal-approximation error of the tt-statistic. Both vanish: ΔB,Ldep→0\Delta^{\mathrm{dep}}_{B,L} \to0 as L/τrel→∞L/\tau_{\mathrm{rel}} \to\infty, and ΔBnorm=O(B−1/2)\Delta^{\mathrm{norm}}_{B} = O(B^{-1/2}) by the Berry–Esseen bound for Student’s statistic. Consequently the interval [gˉ−wnn,gˉ+wnn][\bar{g} - w^{\mathrm{n}}_{n}, \bar{g} + w^{\mathrm{n}}_{n}] attains asymptotic level 1−α1-\alpha for E[gt]\mathbb{E}[g_t] without knowledge of τrel\tau_{\mathrm{rel}} or τint(g)\tau_{\mathrm{int}}(g), and its squared half-width scales as τint(g)σg2/n\tau_{\mathrm{int}}(g)\sigma_g^2/n times a factor (1+o(1))(1+o(1)) as B→∞B \to\infty with L/τrel→∞L/\tau_{\mathrm{rel}} \to\infty.

The proof decorrelates the BB batch means and then applies a Student-tt interval on the decorrelated copy; the complete argument, including the constant CπC_\pi and the exact scope of the two remainders, is in the supplementary material. Two points matter for reading the result: the normalisation is BL\sqrt{BL}, not n\sqrt{n}, because the certificate is computed on the BLBL observations that enter the batches; and ΔB,Ldep\Delta^{\mathrm{dep}}_{B,L} is not zero at finite LL, because consecutive batches share a boundary. A per-batch burn-in makes the latter exact at a small cost in data, as the supplement shows; we report the no-burn-in procedure because it is what our experiments evaluate.

Theorem 7 (Lower bound for adaptive certificates). For any confidence interval procedure Cn=Cn(Z1:n)C_n = C_n(Z_{1:n}) that is valid at level 7/87/8 simultaneously over a family of stationary reversible chains with relaxation times τ∈[1,n]\tau\in[1,n]—that is,

inf⁡τ∈[1,n]inf⁡p∈[1/4,3/4]Pp,τ(p∈Cn)≥78,\inf_{\tau\in[1,n]}\inf_{p \in[1/4,3/4]} \mathbb{P}_{p,\tau}(p \in C_n) \ge\frac{7}{8},

where the infimum is over the sticky-refresh family—the interval width must satisfy Ω(τint(g)/n)\Omega(\sqrt{\tau_{\mathrm{int}}(g)/n}) on some chain in the family. Specifically: for any τ∈[1,n]\tau\in[1,n] there exists a two-state sticky-refresh chain with relaxation time τ\tau and a fixed statistic gg with τint(g)=2τ−1\tau_{\mathrm{int}}(g) = 2\tau- 1 such that any (7/8)(7/8)-coverage interval has width at least cτ/nc\sqrt{\tau/n} with probability at least c′c' on that chain, where c,c′>0c,c' > 0 are universal constants.

The proof applies the same Le Cam two-point argument as Theorem 8 to each fixed τ\tau without knowledge of τ\tau; the full argument is in the supplementary material.

Theorems 6 and 7 together characterize the cost of unknown dependence. The lower bound is inherited from the known-τ\tau case (Theorem 8) by monotonicity: not knowing τ\tau cannot help, so the oracle rate Ω(τ/n)\Omega(\sqrt{\tau/n}) is a baseline. The non-trivial direction is the upper bound: Theorem 6 shows that this baseline is achievable without knowledge of τ\tau, using only the data-driven batch-means variance and a Student-tt quantile. The combination says that unknown dependence costs nothing in rate — the batch-means certificate is minimax rate-optimal in the class of dependence-agnostic procedures, matching the oracle rate τint(g)/n\sqrt{\tau_{\mathrm{int}}(g)/n} without access to the mixing parameters. The practical consequence: one need not estimate β\beta, τrel\tau_{\mathrm{rel}}, or τint\tau_{\mathrm{int}} separately before constructing a valid interval; the batch-means procedure does both estimation and coverage in one shot.

Theorem 8 (Lower bound for fixed-vote margin certificates). There are universal constants c0,c1>0c_0,c_1 > 0 such that the following holds. Let 1≤τ≤n1 \le\tau\le n and consider the family of stationary binary sticky-refresh chains

Pp(z,z′)=(1−α)1{z′=z}+απp(z′),α=1/τ,P_p(z,z') = (1-\alpha)\mathbf{1}\{z'=z\}+\alpha\pi_p(z'), \qquad\alpha= 1/\tau,

where πp=Bernoulli⁡(p)\pi_p = \operatorname{Bernoulli}(p) and p∈[1/4,3/4]p \in[1/4,3/4]. Each chain is irreducible, aperiodic, and reversible, has second eigenvalue 1−1/τ≥01-1/\tau\ge0, and therefore has the positive-part relaxation time τrel=τ\tau_{\mathrm{rel}}=\tau used in Corollary 4. There exists a one-base-hypothesis vote and fixed margin threshold such that the following is true. For any interval-valued certificate Cn=Cn(Z1:n;τ)C_n = C_n(Z_{1:n};\tau) measurable in the observed path, even one that is given the value of τ\tau, if

inf⁡p∈[1/4,3/4]Pp(p∈Cn)≥78,\inf_{p \in[1/4,3/4]} \mathbb{P}_p(p \in C_n) \ge\frac{7}{8},

then some chain in the family satisfies

Pp(width⁡(Cn)≥c0τn)≥c1.\mathbb{P}_p\left(\operatorname{width}(C_n) \ge c_0\sqrt{\frac{\tau}{n}}\right) \ge c_1.

The proof is a constructive Le Cam two-point argument: two sticky-refresh chains whose refresh rates differ by a factor of two have path KL at most 1/41/4 once Δ∝τ/n\Delta\propto\sqrt{\tau/n}, so no (7/8)(7/8)-coverage interval can be narrower than Δ\Delta. The voting-margin representation uses X={0,1}\mathcal{X} = \{0,1\}, Y≡+1Y \equiv+1, and a single base rule, making the margin-failure probability exactly pp; the numerical constants and the fully specified test are in the supplementary material.

Corollary 4 and Theorem 8 match in their dependence on τrel/n\sqrt{\tau_{\mathrm{rel}}/n} for fixed votes, up to universal constants. This is the rate statement supported by the fixed-vote experiments. The learned-vote β\beta-mixing result in Theorem 1 is a different statement and carries the block/coupling tradeoff explicitly.

Experiments

The experiments exercise the four claims of the previous sections. We compute the learned-vote certificate of Theorem 1 for a vote selected from the dependent stream, including every constant and the block/coupling budget; realize the statistic-specific gap of Proposition 5 and exercise the adaptive certificate of Theorem 6; induce class-Markov dependence in trained deep ensembles; and place the fixed-vote certificate against standard resampling and MCMC intervals. A persistent-cluster rate study, an intrinsic-dependence stream with a shuffled control, a real-sensor (UCI HAR) validation, a black-box transfer experiment, a margin sweep, coverage and block-length ablations, and a dependence-estimation study are reported in the supplementary material. The synthetic dependence studies use the sticky-refresh family, whose absolute-regularity coefficient β(a)=(1−1/τ)a\beta(a)=(1-1/\tau)^a is known in closed form, so the Theorem 1 and Corollary 4 certificates use no estimated dependence scale. The Proposition 5 study, the adaptive certificate of Theorem 6, and the real-data studies deliberately do estimate the dependence scale from data—that is what they are for—and each states which quantity is estimated and on which split. Binomial confidence intervals accompany all coverage figures; full protocols are in the supplementary material.

τ\taunnaaμ\muδ′\delta'boundL(F)L(F)cov.
14000120000.0501.730.1231.00
116000180000.0501.040.1231.00
1640001320000.0500.690.1231.00
5400040500.0249.160.1371.00
516000451770.0195.020.1251.00
564000506400.0142.810.1231.00
254000173110.01619.190.1681.00
2516000218360.03110.720.1401.00
25640002451300.0275.790.1261.00
100400062230.03535.950.2351.00
10016000699110.01419.200.1691.00
10064000884360.03110.730.1411.00

Table 1. Theorem 1 certificate for an AdaBoost convex vote learned on the dependent stream (∣H∣=30|\mathcal{H}| = 30, θ=0.2\theta= 0.2, δ=0.05\delta= 0.05; 120 streams per cell, coverage Wilson CI half-width ≤0.03\le0.03). The complete 4×34 \times3 grid is shown; no cell is omitted. “bound” is the mean full certificate value, L(F)L(F) the held-out risk, “cov.” the fraction of streams with L(F)≤boundL(F) \le\mathrm{bound}. Coverage is 1.00 everywhere. Exactly one cell is nonvacuous (τ=1\tau= 1, n=64000n = 64000).

Theorem 1 on a learned vote

This is the theorem-aligned experiment: the vote is selected from the correlated stream, so the uniform-over-V(H)\mathcal{V}(\mathcal{H}) complexity term is genuinely in force. We take a stump-alignable teacher Y=sign⁡(X1+X2+X3+σξ)Y = \operatorname{sign}(X_1 + X_2 + X_3 + \sigma\xi) on X∼N(0,I10)X \sim\mathcal{N}(0, I_{10}), ξ∼N(0,1)\xi\sim\mathcal{N}(0, 1), σ=0.3\sigma= 0.3; the base class H\mathcal{H} is the ∣H∣=30|\mathcal{H}| = 30 axis stumps sign⁡(xk−c)\operatorname{sign}(x_k - c), c∈{−1,0,1}c \in\{-1, 0, 1\}; and F∈V(H)F \in\mathcal{V}(\mathcal{H}) is a discrete-AdaBoost convex vote trained on the stream. The stream is the sticky-refresh process (refresh w.p. 1/τ1/\tau, else repeat), which is stationary with marginal PP and β(a)=(1−1/τ)a\beta(a) = (1 - 1/\tau)^a exactly, so the certificate uses the known b(a)=(1−1/τ)ab(a) = (1 - 1/\tau)^a. The block length is chosen a priori to minimize the deterministic (complexity plus confidence) part of the bound subject to δ′>0\delta' > 0; θ=0.2\theta= 0.2, δ=0.05\delta= 0.05.

As τ\tau grows the coupling penalty 4(μ−1)β(a)4(\mu- 1)\beta(a) forces larger aa and smaller μ\mu: at τ=100\tau= 100, n=4000n = 4000 only μ=3\mu= 3 blocks survive and the certificate reaches 35.95. We report the vacuous cells rather than hide them, since a pure coupling/blocking bound is expected to pay this price at small μ\mu.

Three companion checks—complexity scaling, the block-length tradeoff, and data-dependent tuning by union bound—confirm the theorem’s structure and are reported in the supplementary material.

Statistic-specific effective sample size

Proposition 5

Proposition 5’s content is the gap τint(g)≤2trel−1\tau_{\mathrm{int}}(g) \le2t_{\mathrm{rel}} - 1, not the equality case. We realize the gap with a product of two independent lazy two-state chains: a slow coordinate with λs=0.99\lambda_s = 0.99 (so trel=100t_{\mathrm{rel}} = 100, 2trel−1=1992t_{\mathrm{rel}} - 1 = 199) and a fast coordinate with λf=0.2\lambda_f = 0.2. The margin-failure statistic depends only on the fast coordinate, so τint(g)=(1+λf)/(1−λf)=1.5\tau_{\mathrm{int}}(g) = (1 + \lambda_f)/(1 - \lambda_f) = 1.5 while the chain’s relaxation time is set by the slow coordinate statistic ignores. We compare two certificates over 600 streams of length 40000: the worst-case relaxation-time interval ztrelp^(1−p^)/nz\sqrt{t_{\mathrm{rel}}\hat{p}(1-\hat{p})/n} and the statistic-specific consistent batch-means interval, whose τint(g)\tau_{\mathrm{int}}(g) is estimated from data. The batch-means estimate recovers τ^int=1.49\hat{\tau}_{\mathrm{int}} = 1.49 (true 1.5); the statistic-specific interval attains nominal coverage within binomial error (0.945, Wilson CI [0.924, 0.961], which contains the nominal 0.95) while the worst-case interval is strictly conservative (1.000), and the statistic-specific interval is 8.1× narrower, matching the predicted trel/τint=8.16\sqrt{t_{\mathrm{rel}}/\tau_{\mathrm{int}}} = 8.16. Worst-case dependence corrections over-pay by nearly an order of magnitude; the valid statistic-specific certificate does not. This study evaluates the textbook consistent batch-means interval with τint(g)\tau_{\mathrm{int}}(g) estimated from the same stream, not the separated-block certificate of Theorem 6; the latter is exercised in the following paragraph.

The adaptive certificate with unknown τ\tau (Theorem 6)

The preceding studies hand the procedure the dependence scale; Theorem 6 says it need not be handed anything. On the sticky-refresh cluster stream we run the batch-means Student-tt interval with the conservative choice L=n2/3L = n^{2/3}—the procedure never sees τ\tau—against three references: the oracle interval (knows τint(g)\tau_{\mathrm{int}}(g) exactly), the worst-case interval (spends the full relaxation time), and the naive i.i.d. interval. Over τ∈{5,25,100}×n∈{4000,16000,64000}\tau\in\{5, 25, 100\} \times n \in\{4000, 16000, 64000\} with 400 streams per cell: the adaptive interval is valid in all nine cells (coverage 0.92–0.96; with α=0.05\alpha= 0.05 and δ=0.01\delta= 0.01 the nominal level is 0.94, which lies inside every Wilson CI); its mean width is within 10% of the oracle’s in every cell (mean ratio 1.01, range 0.90–1.09); and it is 2.4–5.1× narrower than the worst-case interval, the gap growing with τ\tau and approximately tracking 2trel−1/τint(g)\sqrt{2t_{\mathrm{rel}} - 1}/\tau_{\mathrm{int}}(g) (the oracle ratio matches that prediction exactly); the adaptive ratio deviates by up to 12% at τ=100\tau= 100 because τint\tau_{\mathrm{int}} itself is estimated). The naive interval undercovers in eight of nine cells (down to 0.435 at τ=100);at\tau= 100); at\tau = 5$, n=4000n = 4000 its Wilson CI still contains nominal. Not knowing the dependence scale costs essentially nothing—the empirical counterpart of the matched pair Theorems 6 and 7.

Induced class-Markov stress test on trained ensembles

The persistent-cluster experiment replaces a classifier by a synthetic vector of cluster risks. The second study uses an actual voting classifier. A vote of M=9M = 9 independently trained convolutional networks is fixed, and the evaluation order is generated by a Markov chain over class labels. Consecutive observations therefore tend to share a class. The stationary target risk is the uniform-class-averaged error, matching the stationary class distribution of the induced chain. This is a controlled dependence stress test on trained models, not evidence about naturally occurring dependence in CIFAR-10 or MNIST [23, 27].

We run two ensemble tiers: weak CNNs (stationary error 0.62 on CIFAR-10, 0.46 on MNIST), which are genuine fixed votes with nondegenerate margin tails, and a competent ResNet-18 CIFAR-10 ensemble (M=9M = 9, ensemble error 6.0%, 94% positive margins, θ=0\theta= 0 tail 6.3%) for which the Theorem 1 certificate is nonvacuous at practical nn. Both use 300 streams per setting at nominal 0.95: i.i.d. intervals under-cover increasingly as dependence grows, while the corrected intervals reach 1.00. The corrected/i.i.d. width ratios 1.0, 2.2, 5.0, 10.0 ≈1,5,25,100\approx\sqrt{1},\sqrt{5},\sqrt{25},\sqrt{100} are a designed cost of the built-in correction, not an empirical discovery.

DatasetQuantityτ=1\tau= 1525100
CIFAR-10 (error 0.62)∣L^−L∣n|\hat{L} - L|\sqrt{n}0.390.490.881.53
i.i.d. coverage0.960.870.630.35
corrected coverage0.961.001.001.00
MNIST (error 0.46)∣L^−L∣n|\hat{L} - L|\sqrt{n}0.410.591.091.99
i.i.d. coverage0.940.820.530.34
corrected coverage0.941.001.001.00
ResNet-18 (error 0.06)i.i.d. coverage0.970.910.860.61
corrected coverage0.971.001.001.00
allwidth ratio1.02.25.010.0

Table 2. Class-Markov stress test on fixed nine-member votes (300 streams per cell; Wilson 95% CIs have half-width ≤0.06\leq0.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 nn. 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.

The strongest supported observation is operational: under this generator, ignoring dependence produces severe under-coverage, while a deliberately widened dependence-aware interval is conservative.

Theorem 1 on the ResNet ensemble. Treating the M=9M = 9 ResNet members as the finite base class (∣H∣=9|\mathcal{H}| = 9), the fixed majority vote F∈V(H)F \in\mathcal{V}(\mathcal{H}) has empirical θ\theta-tail T^(F,0.5)=0.105\hat{T}(F, 0.5) = 0.105 on the i.i.d. test set. At θ=0.5\theta= 0.5, δ=0.05\delta= 0.05, with block length chosen to minimize the bound subject to δ′>0\delta' > 0, the certificate is nonvacuous on a real 6%-error deep ensemble from n=4,000n = 4{,}000 at τ=1\tau= 1 and from n=128,000n = 128{,}000 at τ=5\tau= 5, certifying risk below 0.63 and 0.80 respectively. At stronger dependence (τ≥25\tau\geq25) the pure coupling bound is vacuous at tested nn. The full certificate table and the complete training and evaluation protocol are in the supplementary material.

Resampling baselines

Standard resampling baselines—circular block bootstrap, stationary bootstrap, and non-overlapping batch means with block length ≈τ\approx\tau—undercover under strong dependence (coverage down to 0.79 at τ=100\tau= 100), whereas the mixing-corrected certificate holds coverage 1.00 throughout at the cost of a wider interval: an asymptotic-versus-finite-sample-valid tradeoff. The full baseline numbers are in the supplementary material. The corrected half-width is defined as zp^(1−p^)τ/nz\sqrt{\hat{p}(1-\hat{p})\tau/n}, so dividing by τ/n\sqrt{\tau/n} returns the constant zp^(1−p^)≈0.97z\sqrt{\hat{p}(1-\hat{p})}\approx0.97 by construction, not empirical confirmation of the Corollary–Theorem 8 rate. The empirical content here is the coverage column, not the width ratio.

Discussion and Conclusion

Limitations and scope

The learned-vote bound is not the sharpest possible; it is a transparent finite-class consequence of established β\beta-mixing Rademacher machinery. Under geometric mixing a pure coupling choice adds a logarithmic factor through the spacing needed to control total coupling error, and the black-box theorem preserves a sharper i.i.d. result’s algebraic form but may discard data. The fixed-vote Hoeffding result assumes a stationary, irreducible, aperiodic, finite-state reversible chain, but not laziness; these conditions exceed generic temporal dependence and are what make the clean τrel/n\sqrt{\tau_{\mathrm{rel}}/n} rate and spectral comparison available. Estimating β(k)\beta(k), τrel\tau_{\mathrm{rel}}, or τint(g)\tau_{\mathrm{int}}(g) from the same stream is a separate problem; the supplement’s exploratory plug-in study does not establish adaptive validity.

The empirical evidence is mostly controlled, and the two regimes are covered unevenly. The persistent-cluster generator has Bernoulli noise as well as persistence, and the trained-ensemble study induces dependence through class order; neither stream is naturally correlated. The exception is the supplement’s UCI HAR study, where a fixed committee vote runs on real ordered accelerometer windows with no synthetic generator: naive intervals cover 0.38, the dependence-agnostic certificate of Theorem 6 reaches nominal 0.95 once its batch-length condition holds, and a shuffled control restores 0.94–0.96. That evidence is fixed-vote only: no experiment learns a vote from a naturally dependent stream, since Theorem 1 is exercised only on the sticky-refresh process, where β(a)\beta(a) is known exactly. Stronger evidence would pair a naturally ordered dataset with a learned vote and report margin-tail curves, uncertainty intervals, nonvacuity diagnostics, and an anonymous reproducibility archive.

Summary. We separated four claims that should not be compressed into “replace nn by an effective sample size.” For learned votes over a finite base class, independent-block Rademacher theory gives a stationary β\beta-mixing margin certificate with an explicit coupling budget. For any i.i.d. voting-margin theorem, regular spacing gives a black-box transfer with an additive mixing failure probability. For fixed votes on stationary finite-state reversible chains, the τrel/n\sqrt{\tau_{\mathrm{rel}}/n} rate is both achievable and unavoidable over a sticky-refresh family, with asymptotic constant governed by the statistic-specific τint(g)\tau_{\mathrm{int}}(g). And when the dependence scale is unknown, a batch-means certificate stays finite-sample valid and rate-optimal among dependence-agnostic procedures, so adaptation costs nothing in rate. The experiments exercise each: the learned-vote certificate is nonvacuous at large block count; the statistic-specific one is an order of magnitude tighter at matched coverage; resampling baselines undercover where the certificate holds; and a shuffled control pins ordering as the cause of naive undercoverage. Worst-case corrections overpay when the monitored statistic mixes faster than the chain; the statistic-specific certificate recovers that precision without sacrificing validity.

This supplement contains the full proofs of all theoretical results and the secondary experiments referenced in the main paper. References of the form “Theorem 1”, “Proposition 5”, etc. point to the numbering of the main paper; appendices, floats, and equations local to this document are numbered here (appendices, floats, and equations local to this document all carry an “S” prefix (Appendix S1, S2, . . . ; tbl:S1; eq:S1)

Positioning against prior work

ResultDependencePredictorDistinguishing feature
Mohri–Rostamizadehstationary mixing β\beta-learned classgeneral Rademacher margin bound
Ralaivola et al.non-i.i.d.; β\beta-mixing applicationposterior/votePAC-Bayes route
Theorem 1stationary mixingβ\beta-learned convex votefinite-base-class complexity and explicit coupling budget
Theorem 3stationary mixingtheorem-dependenttransfers any i.i.d. event to a spaced sample
Corollary 4 and Theorem 8finite-state reversible Markovfixed voteclean spectral rate and matching dependence exponent

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

:::

Persistent-cluster rate study

This appendix collects the fixed-vote rate study summarised in the main paper.

Persistent-cluster protocol

The controlled generator has K=8K = 8 latent clusters. Their error rates r1,…,rKr_1,\ldots,r_K are drawn once from [0.2,0.6][0.2, 0.6] and then held fixed. The stationary cluster distribution is uniform, so the stationary risk is

L=rˉ=1K∑k=1Krk.L = \bar{r} = \frac{1}{K}\sum_{k=1}^{K} r_k.

For dependence parameter τ∈{1,5,25,100}\tau\in\{1,5,25,100\}, the cluster chain evolves according to

P(c,c′)=(1−1τ)1{c′=c}+1τK.P(c,c') = \left(1-\frac{1}{\tau}\right)\mathbf{1}\{c'=c\}+\frac{1}{\tau K}.

When τ=1\tau= 1, the cluster index is refreshed from the stationary distribution at every step. For larger τ\tau, the chain remains in a cluster for longer runs. Conditional on cluster CtC_t, the error indicator is sampled as Et∼Bernoulli⁡(rCt)E_t \sim\operatorname{Bernoulli}(r_{C_t}). The empirical risk is L^=n−1∑tEt\hat{L}=n^{-1}\sum_t E_t. The grid is n∈{500,2000,8000,32000}n \in\{500,2000,8000,32000\} with 60 independent repetitions per cell.

Dependence is not the only source of the generalization gap: the conditional Bernoulli draw contributes ordinary i.i.d. sampling noise even at τ=1\tau=1.

τ\tau1525100
mean ∣L^−L∣n|\hat{L}-L|\sqrt{n}0.3930.4710.6731.382
CV across nn0.1520.1030.1090.198
log–log slope in nn−0.544-0.544−0.560-0.560−0.442-0.442−0.439-0.439
R2R^2 of slope fit0.9700.9970.9900.935

caption: Fixed-vote scaling on the persistent-cluster stream. The fitted exponents are close to the −1/2-1/2 prediction. The CV uses the population standard deviation over the four sample-size summaries.

:::

Let Vτ=Var⁡(rC)V_\tau=\operatorname{Var}(r_C) under the uniform stationary cluster law and λ=1−1/τ\lambda=1-1/\tau. A direct calculation gives

Var⁡(Et)=rˉ(1−rˉ),Cov⁡(Et,Et+k)=Vrλk.\operatorname{Var}(E_t)=\bar{r}(1-\bar{r}), \qquad\operatorname{Cov}(E_t,E_{t+k})=V_r\lambda^k.

Hence the asymptotic variance of n(L^−L)\sqrt{n}(\hat{L}-L) is

rˉ(1−rˉ)+2Vrλ1−λ=rˉ(1−rˉ)+2Vr(τ−1).(3)\bar{r}(1-\bar{r})+2V_r\frac{\lambda}{1-\lambda}=\bar{r}(1-\bar{r})+2V_r(\tau-1). \tag*{(3)}

The correct prediction is therefore a square root of an i.i.d. floor plus a persistence term linear in τ\tau.

The n−1/2n^{-1/2} factor

At each fixed τ\tau, the rescaled mean gap ∣L^−L∣n|\hat{L}-L|\sqrt{n} is roughly stable over the 64× sample-size range. The population coefficient of variation over the four sample sizes is 0.152, 0.103, 0.109, and 0.198 for τ=1,5,25,100\tau=1,5,25,100. A more direct check fits a power law in nn. The log–log slopes are −0.544-0.544, −0.560-0.560, −0.442-0.442, and −0.439-0.439, with R2R^2 values 0.970, 0.997, 0.990, and 0.935. These exponents are broadly consistent with n−1/2n^{-1/2} over the tested grid, but they are not exactly −1/2-1/2. Repeating the study over eight independent cluster-risk draws (seeds 0–7, 60 repetitions per cell each) quantifies how much of that deviation is seed noise: the fitted slopes are −0.512±0.042-0.512\pm0.042, −0.509±0.021-0.509\pm0.021, −0.499±0.033-0.499\pm0.033, and −0.495±0.021-0.495\pm0.021 (mean ±\pm sd across seeds) for τ=1,5,25,100\tau=1,5,25,100, so every across-seed line lies within half a standard deviation of −1/2-1/2, and the rescaled gaps ∣L^−L∣n|\hat{L}-L|\sqrt{n} carry across-seed sds of 0.02–0.21 around means 0.36–1.36 (artifact verify_rate_multiseed.json). The single-draw exponents above are within the seed-to-seed spread.

Dependence amplification and the i.i.d. floor

Across τ\tau, the mean values of ∣L^−L∣n|\hat{L}-L|\sqrt{n} are 0.393, 0.471, 0.673, and 1.382. Their Pearson correlation with τ\sqrt{\tau} is 0.986. Four monotone points, however, do not identify a universal power law, and the ratios after division by τ\sqrt{\tau} are 0.393, 0.210, 0.135, and 0.138, so a pure proportionality through the origin is not supported over the full sweep. The two-component variance in (3) gives the sharper prediction. Regressing the squared rescaled means against τ\tau gives

E[∣L^−L∣n]2≈0.0984+0.01789τ,\mathbb{E}[|\hat{L}-L|\sqrt{n}]^2 \approx0.0984+0.01789\tau,

with R2=0.994R^2=0.994 on the four reported points. This fit is consistent with an i.i.d. intercept plus a persistence term.

Squared mean rescaled gap against the persistence parameter

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}.

Raw gap across the full grid

Figure 2 shows the raw gap across the full grid. At matched nn, the curves are ordered by the persistence parameter, while each curve declines with sample size. The dashed reference shows an n−1/2n^{-1/2} slope but is not a fitted theoretical constant. The gaps range from 0.0022 at (τ,n)=(1,32000)(\tau, n) = (1, 32000) to 0.046 at (100,500)(100, 500). The full numerical grid and the ∣L^−L∣/τ/n\lvert\widehat{L}-L\rvert/\sqrt{\tau/n} ratios appear in the supplementary material.

Reported fixed-vote mean gap versus sample size

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-0.56 to −0.44-0.44.

What the controlled rate study establishes

This particular study supports approximate fixed-vote n−1/2n^{-1/2} decay under the tested generator and shows that persistence increases the long-run variance; the learned-vote complexity term of Theorem 1 is exercised separately in the learned-vote experiment of the main paper. It does not by itself test Theorem 8, because a lower bound is a statement about the difficulty of all valid procedures over a family, not a trend in one estimator; the matching-bound sandwich in the main paper addresses that. The appropriate claim for the rate study alone is that its behavior is consistent with the fixed-statistic concentration picture and with the exact i.i.d.-floor-plus-persistence decomposition.

Additional dependence experiments

Intrinsic dependence and a shuffled control

To move past injected dependence we build an activity-segmentation stream in the spirit of wearable-sensor logs: a latent activity follows a slow Markov chain with dwell time ∼τ\sim\tau, each activity emits a Gaussian feature window, and a fixed committee of nine linear classifiers (trained once on separate i.i.d. data) predicts the activity; the margin-failure statistic is the misclassification indicator, whose dependence is intrinsic to the latent process. Over 600 length-2000 segments, the naive i.i.d. interval covers only 0.508 (Wilson CI [0.47, 0.55]). A dependence-aware batch-means interval whose τint\tau_{\mathrm{int}} is estimated on a disjoint calibration stream (τ^int=8.16\widehat{\tau}_{\mathrm{int}} = 8.16, consistent with sample splitting) restores coverage to 0.950 [0.93, 0.96]. Shuffling the same errors before segmenting — destroying temporal order — returns i.i.d. coverage to 0.938 [0.92, 0.95]. The shuffled control isolates ordering as the sole cause of the undercoverage, exactly the plot fixed-vote theory predicts.

Real sensor data: UCI HAR

The same protocol on real data. The UCI Human Activity Recognition dataset ([2]) provides 2.56-second smartphone accelerometer windows with 50% overlap, in temporal order within each of 9 held-out test subjects (2947 windows): the dependence is genuinely intrinsic — overlapping windows plus activity runs averaging 24.6 consecutive windows. A fixed committee of M=9M = 9 bootstrap-trained multinomial logistic members reached 96.1% test accuracy (members 95.4–96.1%); the misclassification indicator along the ordered stream is the monitored statistic. Batch means on a calibration split measure τ^int≈10.5\widehat{\tau}_{\mathrm{int}} \approx10.5 at L=50L = 50, growing to ≈16\approx16 at L=400L = 400 — a real two-scale dependence (within-subject correlation plus between-subject risk heterogeneity spanning 0.00–0.13 against the pooled 0.039).

Over 400 subject-level block-bootstrap streams: the naive i.i.d. interval covers 0.38 at n=2000n = 2000, and worsens with nn (0.35 at $n = 20000) as its width shrinks against an unmodeled bias; shuffling the same windows restores naive coverage to 0.94–0.96, isolating real temporal ordering as the cause. The adaptive certificate of Theorem 6 (L=n2/3L = n^{2/3}, never told the dependence) behaves exactly as its batch-length condition predicts: coverage 0.78 at n=2000n = 2000 (where L=166L = 166 sits below the ≈327\approx327-window subject scale, violating L≫τrelL \gg\tau_{\mathrm{rel}}), 0.92 at n=8000n = 8000, and 0.95 — exactly nominal — at n=20000n = 20000 (L=740L = 740), with implied τ^int=13.5\widehat{\tau}_{\mathrm{int}} = 13.5 matching the measured multiscale value. Real sensor data breaks naive intervals, and the dependence-agnostic certificate attains nominal coverage precisely where its stated condition holds: a real-data validation of both the theorem and the sharpness of its batch-length requirement.

Black-box transfer of a sharper bound (Theorem 3)

We instantiate Algorithm 1 with a real sharper i.i.d. certificate. On the spaced subsample S(a)S^{(a)} we run both the first-order uniform margin bound (with μ→q\mu\to q, no coupling term) and a sharper kk-inverse relative-entropy bound; both are valid on the dependent stream with failure at most η+(q−1)b(a)\eta+(q-1)b(a). Across τ∈{5,25,100}\tau\in\{5,25,100\} the kl bound is uniformly tighter — e.g. at τ=25\tau=25, n=64000n=64000 it gives 0.62 against the first-order 5.33, and at τ=100\tau=100, n=16000n=16000 it is 0.56 (nonvacuous) where the first-order block bound is 18.6 (vacuous). Both hold nominal coverage. Spacing discards data but imports a sharper functional form, giving a concrete space-versus-block rule: when the empirical margin tail is small, transfer a kl bound on the spaced sample rather than block the full stream.

Le Cam simulation of the lower-bound construction

An explicit two-point Le Cam simulation of the Theorem 8 construction itself (τ∈{4,16,64}\tau\in\{4,16,64\}, n=4096n=4096, Δ=18τ/n\Delta=\frac{1}{8}\sqrt{\tau/n}, 4000 paths per model) confirms the proof’s budget empirically: the latent path KL estimated from refresh counts is 0.031–0.032 ≤1/4\leq1/4 at every τ\tau, the exact likelihood-ratio test — the best test — errs with probability 0.47–0.48 ≥ctest≈0.323\geq c_{\mathrm{test}}\approx0.323, and the plug-in interval that covers at level 7/87/8 (the τint\tau_{\mathrm{int}}-corrected width, coverage 0.94–0.95) has width at least c0τ/nc_0\sqrt{\tau/n} with c0=1/8c_0=1/8 on every covering path, exceeding the floor by a factor of about 21 (artifact verify_lecam.json).

Learned-vote certificate: companion checks

Three companion checks confirm the theorem’s structure. Complexity scaling: over ∣H∣∈{12,24,48,96}|\mathcal{H}|\in\{12,24,48,96\} the certificate’s complexity term tracks log⁡(2∣H∣)\sqrt{\log(2|\mathcal{H}|)} with correlation 1.000, matching the 4θ2log⁡(2∣H∣)/μ\frac{4}{\theta}\sqrt{2\log(2|\mathcal{H}|)/\mu} form. Block-length tradeoff: at τ=25\tau=25, n=64000n=64000 the bound is infeasible (δ′≤0\delta'\leq0) for a≤200a\leq200, minimized at the smallest feasible block a⋆=300a^\star=300, and rises monotonically for larger aa (6.35 at a=300a=300 to 31.2 at a=8000a=8000) as μ\mu shrinks — the coupling-versus-complexity tension of Theorem 1 made explicit, with the optimum at the feasibility boundary. Data-dependent tuning: allocating δ\delta across a deterministic 6-point (a,θ)(a,\theta) grid and taking the smallest simultaneous certificate holds jointly on 100% of streams and yields a selected bound of 2.36 versus 8.80 for a fixed middle pair, as licensed by the union bound after Theorem 1.

Full learned-vote certificate on the ResNet ensemble

With the M=9M=9 ResNet members as the finite base class (∣H∣=9|\mathcal{H}|=9) and θ=0.5\theta=0.5, δ=0.05\delta=0.05, the full Theorem 1 certificate (block length chosen to minimise the bound subject to δ′>0\delta'>0) is:

τ\taunnμ\mubound
14,0002,0000.63nonvacuous
132,00016,0000.29nonvacuous
5128,0001,2070.80nonvacuous
25128,0002561.63vacuous

Table S6.

The certificate uses only the known mixing coefficient β(a)=(1−1/τ)a\beta(a)=(1-1/\tau)^a and the margin tail. At stronger dependence (τ≥25\tau\geq25) the pure coupling bound is vacuous at the tested nn; the statistic-specific certificate of Corollary 4 remains valid and narrow there, because it uses the chain’s actual spectral structure rather than the worst-case coupling budget. The full training and evaluation protocol — network architecture, optimizer, class-transition matrices, and interval constants — is given in the supplementary material.

Extended discussion

Learned votes and fixed votes answer different questions

Theorem 1 addresses a vote that may be selected from the same dependent sample used to compute its empirical margin distribution. Uniformity over the convex vote class produces the finite-class complexity term and forces the block/coupling accounting. Corollary 4 addresses a vote fixed independently of the evaluation chain. There is no model-selection complexity in that regime, and the spectral rate is correspondingly cleaner. Theorem 8 matches only this fixed-vote dependence exponent; it does not prove minimax optimality of the full learned-vote theorem.

Why the margin functional rather than raw error

The fixed-vote lower bound can be realized with a binary error statistic, so one might ask why the rest of the paper retains margin language. The reason is that the learned-vote theorem is genuinely margin-dependent. The empirical quantity T^(F,θ)\widehat{T}(F,\theta) records how much mass lies near or below a chosen confidence threshold and trades against a 1/θ1/\theta complexity factor. This is the structure that connects the result to boosting and voting-classifier theory. A raw-error concentration bound alone would not recover that tradeoff.

The distinction also clarifies the experiments. The persistent-cluster and deep-ensemble studies measure empirical risk gaps and so validate the dependence side of the fixed-vote picture, whereas the learned-vote study of the main paper computes the full margin certificate of Theorem 1 for a vote selected from the dependent sample, allocates confidence across a threshold grid, and reports where the bound is nonvacuous — exercising the complexity term and the block/coupling budget directly.

Reading dependence through spectral and statistic-specific quantities

For the finite-state reversible chains in Corollary 4, trel=(1−max⁡{λ2,0})−1t_{\mathrm{rel}}=(1-\max\{\lambda_2,0\})^{-1} controls the fixed-vote certificate without a laziness assumption. Total-variation mixing time is related but is not identical and may additionally depend on rare-state mass ([30]). The statistic-specific quantity is τint(g)\tau_{\mathrm{int}}(g), which integrates the spectral components actually seen by the thresholded margin indicator. Proposition 5 therefore corrects a tempting but false simplification: a two-valued statistic need not have autocorrelation λk∗\lambda^*_k. Under the lazy spectral hypothesis of Proposition 5, equality τint(g)=2τrel−1\tau_{\mathrm{int}}(g)=2\tau_{\mathrm{rel}}-1 requires the statistic-specific spectral measure to be concentrated at {λ⋆}\{\lambda_\star\}. The sticky-refresh family has this property for every centered statistic and is therefore the right place for an exact constant statement.

Relation to minimax estimator design

The related preprint [47] asks how to design an estimator under Markov dependence and studies a spectral-routing construction. The present paper asks how to certify the margin behavior of a voting class or fixed vote. The two questions may share dependence scales, but the mathematical objects and guarantees are different. We therefore avoid describing the papers as a coordinated pair or claiming that the same graph eigenvector directly proves both results.

Resampling baselines (full numbers)

Reviewers will ask why not simply block bootstrap. On the sticky-refresh cluster stream (n=4000n=4000, 300 streams, 200 bootstrap resamples per stream) we compare the mixing-corrected interval against the circular block bootstrap (CBB), the stationary bootstrap (SB), and non-overlapping batch means (BM), with block length ≈τ\approx\tau. At τ=1\tau=1 all four methods coincide (coverage ≈0.97\approx0.97, equal widths): the certificate loses nothing without dependence. At τ=25,100\tau=25,100 the resampling methods undercover — CBB 0.86, 0.79; SB 0.88, 0.85; BM 0.92, 0.80 — because few effective blocks remain at small nn, while the mixing-corrected certificate holds 1.00 throughout, trading a wider interval (0.077 vs 0.021 at τ=25\tau=25) for finite-sample validity. The comparison is thus asymptotic-versus-finite-sample-valid, and the certificate is the safe choice under strong dependence. The corrected half-width is zp^(1−p^)τ/nz\sqrt{\hat p(1-\hat p)\tau/n} by construction, so its ratio to τ/n\sqrt{\tau/n} is zp^(1−p^)z\sqrt{\hat p(1-\hat p)}, which for p^≈0.42\hat p\approx0.42 is ≈0.97\approx0.97 regardless of τ\tau and nn; the observed band [0.960, 0.971] is a restatement of that constant and is not evidence about the Corollary 4 or Theorem 8 rates. The empirical Le Cam check of the supplementary material gives the honest comparison against the lower bound: the covering interval there exceeds the Theorem 8 floor c0τ/nc_0\sqrt{\tau/n} with c0=1/8c_0=1/8 by a factor of about 21, so upper and lower constants are matched in rate but not yet in constant.

Proof of Theorem 1

The constants in our learned-vote theorem inherit the empirical Rademacher theorem of Mohri and Rostamizadeh [36], so we fix their normalization explicitly. Partition a sample S=(Z1,…,Zm)S=(Z_1,\ldots,Z_m) with m=2μam=2\mu a into 2μ2\mu consecutive blocks of length aa, and form the fixed-position singleton sample from the odd blocks by

Sμ=(Z1,Z2a+1,…,Z2(μ−1)a+1).S_\mu=(Z_1,Z_{2a+1},\ldots,Z_{2(\mu-1)a+1}).

For a sample T=(z1,…,zr)T=(z_1,\ldots,z_r) and a real-valued function class A\mathcal{A}, define

R^T(A)=2rEσ[sup⁡c∈A∣∑i=1rσic(zi)∣].\widehat{\mathfrak{R}}_T(\mathcal{A})=\frac{2}{r}\mathbb{E}_{\sigma}\left[\sup_{c\in\mathcal{A}}\left|\sum_{i=1}^{r}\sigma_i c(z_i)\right|\right].

where the σi\sigma_i are independent Rademacher signs. The absolute value and the factor 2/r2/r are part of the convention.

Imported Lemma (Mohri–Rostamizadeh empirical bound). Let S=(Z1,…,Zm)S=(Z_1,\ldots,Z_m) be drawn from a stationary β\beta-mixing process, with m=2μam=2\mu a for integers a,μ≥1a,\mu\ge1. Let A\mathcal{A} be a measurable class with ∣c(x)∣≤M|c(x)|\le M for every c∈Ac\in\mathcal{A} and x∈Zx\in\mathcal{Z}, and assume a μ\mu-point sample is fixed independently of the observed sample. For any 0<δ<10<\delta<1 such that

δ′=δ−4(μ−1)β(a)>0,\delta'=\delta-4(\mu-1)\beta(a)>0,

with probability at least 1−δ1-\delta, every c∈Ac\in\mathcal{A} satisfies

Pc≤P^Sc+R^Sμ(A)+3Mlog⁡(4/δ′)2μ.P c\le\widehat{P}_{S}c+\widehat{\mathfrak{R}}_{S_\mu}(\mathcal{A})+3M\sqrt{\frac{\log(4/\delta')}{2\mu}}.

This is Theorem 2 of Mohri and Rostamizadeh [36] written in the notation used here. Their phrase “bounded by MM” is sufficient for our application under either the sup-norm or range interpretation: the centered ramp class used below lies in [−1,0][-1,0], so its sup-norm and range length are both at most one.

Let

M={z=(x,y)↦yF(x):F∈V(H)},\mathcal{M}=\{z=(x,y)\mapsto yF(x):F\in\mathcal{V}(\mathcal{H})\},
Cθ={z↦ϕθ(MF(z))−1:F∈V(H)}.\mathcal{C}_{\theta}=\{z\mapsto\phi_{\theta}(M_F(z))-1:F\in\mathcal{V}(\mathcal{H})\}.

Every c∈Cθc\in\mathcal{C}_{\theta} takes values in [−1,0][-1,0], so the imported Mohri–Rostamizadeh theorem applies with M=1M=1. Thus, for δ′=δ−4(μ−1)β(a)>0\delta'=\delta-4(\mu-1)\beta(a)>0, with probability at least 1−δ1-\delta, simultaneously for all FF,

P(ϕθ(MF)−1)≤P^S(ϕθ(MF)−1)+R^Sμ(Cθ)+3log⁡(4/δ′)2μ.(4)P(\phi_{\theta}(M_F)-1)\le\widehat{P}_{S}(\phi_{\theta}(M_F)-1)+\widehat{\mathfrak{R}}_{S_\mu}(\mathcal{C}_{\theta})+3\sqrt{\frac{\log(4/\delta')}{2\mu}}. \tag*{(4)}

The −1-1 terms on the two sides cancel. This centering step occurs before contraction; with the absolute-value Rademacher convention, translating a class by a constant need not preserve its empirical complexity.

Define ψθ(u)=ϕθ(u)−1\psi_{\theta}(u)=\phi_{\theta}(u)-1. Then ψθ(0)=0\psi_{\theta}(0)=0 and ψθ\psi_{\theta} is 1/θ1/\theta-Lipschitz. The Ledoux–Talagrand contraction inequality [28 Theorem 4.12], under the normalization fixed above, gives

R^Sμ(Cθ)≤2θR^Sμ(M).\widehat{\mathfrak{R}}_{S_\mu}(\mathcal{C}_{\theta})\le\frac{2}{\theta}\widehat{\mathfrak{R}}_{S_\mu}(\mathcal{M}).

Write Sμ=(zi)i=1μS_\mu=(z_i)_{i=1}^{\mu} with zi=(xi,yi)z_i=(x_i,y_i) and, for each h∈Hh\in\mathcal{H}, let

ah=(y1h(x1),…,yμh(xμ))∈[−1,1]μ.a_h=(y_1h(x_1),\ldots,y_\mu h(x_\mu))\in[-1,1]^\mu.

For fixed signs σ\sigma and vote weights ww,

∣∑i=1μσiyiF(xi)∣=∣∑h∈Hwh⟨σ,ah⟩∣≤max⁡h∈H∣⟨σ,ah⟩∣,\left|\sum_{i=1}^{\mu}\sigma_i y_iF(x_i)\right|=\left|\sum_{h\in\mathcal{H}}w_h\langle\sigma,a_h\rangle\right|\le\max_{h\in\mathcal{H}}|\langle\sigma,a_h\rangle|,

and equality is attained by an extreme point of the simplex. Therefore

R^Sμ(M)=2μEσmax⁡h∈H∣⟨σ,ah⟩∣.\widehat{\mathfrak{R}}_{S_\mu}(\mathcal{M})=\frac{2}{\mu}\mathbb{E}_{\sigma}\max_{h\in\mathcal{H}}|\langle\sigma,a_h\rangle|.

The absolute value is equivalent to applying Massart’s finite-class lemma to the set

{ah:h∈H}∪{−ah:h∈H},\{a_h : h \in\mathcal{H}\} \cup\{-a_h : h \in\mathcal{H}\},

which has cardinality at most 2∣H∣2|\mathcal{H}|. Since ∥ah∥2≤μ\|a_h\|_2 \le\sqrt{\mu},

R^Sμ(M)≤22log⁡(2∣H∣)μ.\widehat{\mathfrak{R}}_{S_\mu}(\mathcal{M}) \le2\sqrt{\frac{2\log(2|\mathcal{H}|)}{\mu}}.

Substituting into (4) yields

Pϕθ(MF)≤P^Sϕθ(MF)+4θ2log⁡(2∣H∣)μ+3log⁡(4/δ′)2μ.P\phi_\theta(M_F) \le\widehat{P}_S\phi_\theta(M_F) + \frac{4}{\theta}\sqrt{\frac{2\log(2|\mathcal{H}|)}{\mu}} + 3\sqrt{\frac{\log(4/\delta')}{2\mu}}.

Finally,

1{MF≤0}≤ϕθ(MF)≤1{MF≤θ},1\{M_F \le0\} \le\phi_\theta(M_F) \le1\{M_F \le\theta\},

so L(F)≤Pϕθ(MF)L(F) \le P\phi_\theta(M_F) and P^Sϕθ(MF)≤T^S(F,θ)\widehat{P}_S\phi_\theta(M_F) \le\widehat{T}_S(F,\theta). This proves the theorem.

For Corollary 2, write B‾=B∨1\overline{B} = B \vee1 and τ‾=τ∨1\overline{\tau} = \tau\vee1. These replacements only weaken the assumed envelope, because

Be−k/τ≤B‾e−k/τ‾.Be^{-k/\tau} \le\overline{B}e^{-k/\overline{\tau}}.

By the definition of aa,

β(a)≤B‾e−a/τ‾≤δ8n.\beta(a) \le\overline{B}e^{-a/\overline{\tau}} \le\frac{\delta}{8n}.

Since μ≤n/(2a)≤n/2\mu\le n/(2a) \le n/2,

4(μ−1)β(a)≤4μδ8n≤δ4,4(\mu-1)\beta(a) \le4\mu\frac{\delta}{8n} \le\frac{\delta}{4},

so δ′≥3δ/4\delta' \ge3\delta/4. When n≥4an \ge4a,

μ=⌊n2a⌋≥n4a.\mu= \left\lfloor\frac{n}{2a}\right\rfloor\ge\frac{n}{4a}.

Moreover, because B‾≥1\overline{B} \ge1, τ‾≥1\overline{\tau} \ge1, and δ≤1/2\delta\le1/2, the logarithm in the definition of aa exceeds one, so

a≤2τ‾log⁡8B‾nδ.a \le2\overline{\tau}\log\frac{8\overline{B}n}{\delta}.

Substitution into Theorem 1, together with

log⁡4δ′≤log⁡163δ≤C0log⁡4δ\log\frac{4}{\delta'} \le\log\frac{16}{3\delta} \le C_0\log\frac{4}{\delta}

for a universal C0C_0, gives the stated rate after absorbing fixed numerical constants. The theorem is applied to the prefix S1:mS_{1:m} with m=2μam = 2\mu a, which explains the empirical term in the corollary.

Proof of Corollary 4

Let

gF(z)=1{MF(z)≤θ},μg=PgF.g_F(z) = 1\{M_F(z) \le\theta\}, \qquad\mu_g = P g_F.

Because the vote is fixed independently of the evaluation chain, gFg_F is a fixed function taking values in [0,1][0,1]. Let λ2\lambda_2 be the second-largest eigenvalue of the finite-state reversible transition matrix and λ⋆=max⁡{λ2,0}\lambda_\star= \max\{\lambda_2,0\}. Applying the Hoeffding inequality of León and Perron (2004) to gFg_F and, for the opposite tail, to 1−gF1-g_F, gives for every u>0u > 0

P(∣P^ngF−PgF∣≥u)≤2exp⁡(−21−λ⋆1+λ⋆nu2).\mathbb{P}\left(\left|\widehat{P}_n g_F - P g_F\right| \ge u\right) \le2\exp\left(-2\frac{1-\lambda_\star}{1+\lambda_\star}nu^2\right).

Since trel=(1−λ⋆)−1t_{\mathrm{rel}} = (1-\lambda_\star)^{-1},

21−λ⋆1+λ⋆=22trel−1≥1trel.2\frac{1-\lambda_\star}{1+\lambda_\star} = \frac{2}{2t_{\mathrm{rel}}-1} \ge\frac{1}{t_{\mathrm{rel}}}.

Therefore

P(PgF−P^ngF>u)≤2exp⁡(−nu2trel).\mathbb{P}\left(Pg_F-\widehat{P}_n g_F > u\right) \le2\exp\left(-\frac{nu^2}{t_{\mathrm{rel}}}\right).

Choosing u=trellog⁡(2/δ)/nu = \sqrt{t_{\mathrm{rel}}\log(2/\delta)/n} gives the required one-sided deviation. Finally,

1{MF≤0}≤1{MF≤θ},1\{M_F \le0\} \le1\{M_F \le\theta\},

so L(F)≤PgFL(F) \le P g_F and P^ngF=T^(F,θ)\widehat{P}_n g_F = \widehat{T}(F,\theta). The stationary start is essential to the cited Hoeffding statement. The corollary deliberately does not claim the same formula for an arbitrary initial law; such extensions require an initialization penalty.

Proof of Theorem 3

Let tj=1+(j−1)at_j = 1 + (j-1)a and let QjQ_j be the joint law of (Zt1,…,Ztj)(Z_{t_1}, \ldots, Z_{t_j}). We prove by induction that

dTV(Qj,Pj)≤(j−1)β(a).d_{\mathrm{TV}}(Q_j,P^j) \le(j-1)\beta(a).

The claim is trivial for j=1j=1. For j≥2j \ge2, let

Gj−1=σ(Zt1,…,Ztj−1)⊆F−∞tj−1.\mathcal{G}_{j-1} = \sigma(Z_{t_1}, \ldots, Z_{t_{j-1}}) \subseteq\mathcal{F}^{t_{j-1}}_{-\infty}.

Because tj=tj−1+at_j = t_{j-1}+a, Definition 1 and conditional Jensen imply

E[sup⁡A∣P(Ztj∈A∣Gj−1)−P(A)∣]≤E[sup⁡A∣P(Ztj∈A∣F−∞tj−1)−P(A)∣]≤β(a).\mathbb{E}\left[\sup_A\left|\mathbb{P}(Z_{t_j}\in A\mid\mathcal{G}_{j-1})-\mathbb{P}(A)\right|\right] \le\mathbb{E}\left[\sup_A\left|\mathbb{P}(Z_{t_j}\in A\mid\mathcal{F}^{t_{j-1}}_{-\infty})-\mathbb{P}(A)\right|\right]\le\beta(a).

Because Z\mathcal{Z} is standard Borel, regular conditional laws exist, and the disintegration identity

dTV(L(W,Z),L(W)⊗P)=EW[dTV(L(Z∣W),P)]d_{\mathrm{TV}}(\mathcal{L}(W,Z),\mathcal{L}(W)\otimes P)=\mathbb{E}_W[d_{\mathrm{TV}}(\mathcal{L}(Z\mid W),P)]

applies. Hence

dTV(Qj,Qj−1⊗P)≤β(a).d_{\mathrm{TV}}(Q_j,Q_{j-1}\otimes P)\le\beta(a).

Tensoring with the common marginal PP preserves total variation, so the triangle inequality gives

dTV(Qj,Pj)≤dTV(Qj,Qj−1⊗P)+dTV(Qj−1⊗P,Pj−1⊗P)≤β(a)+dTV(Qj−1,Pj−1)≤(j−1)β(a).\begin{aligned} d_{\mathrm{TV}}(Q_j,P^j) &\le d_{\mathrm{TV}}(Q_j,Q_{j-1}\otimes P)\\ &\quad+ d_{\mathrm{TV}}(Q_{j-1}\otimes P,P^{j-1}\otimes P)\\ &\le\beta(a)+d_{\mathrm{TV}}(Q_{j-1},P^{j-1})\\ &\le(j-1)\beta(a). \end{aligned}

This proves the constant and the indexing under Definition 1: an index difference of exactly aa is controlled by β(a)\beta(a), not β(a−1)\beta(a-1).

Taking the test function to be the indicator of a measurable event E⊆Zq\mathcal{E} \subseteq\mathbb{Z}^q gives

∣Qq(E)−Pq(E)∣≤(q−1)β(a).\left|Q^q(\mathcal{E})-P^q(\mathcal{E})\right| \le(q-1)\beta(a).

If an i.i.d. theorem has a failure event F∈σ(S~)\mathcal{F} \in\sigma(\widetilde{S}) with Pq(F)≤ηP^q(\mathcal{F}) \le\eta, then

Qq(F)≤Pq(F)+(q−1)β(a)≤η+(q−1)β(a).Q_q(\mathcal{F}) \le P^q(\mathcal{F})+(q-1)\beta(a) \le\eta+(q-1)\beta(a).

The proof uses only events measurable in the qq spaced observations. A statement involving a full-stream empirical quantity is not transferred by this argument.

Proof of Proposition 5

Let gˉn=n−1∑t=1ngt\bar{g}_n=n^{-1}\sum_{t=1}^{n}g_t and σg2=Var⁡(gt)\sigma_g^2=\operatorname{Var}(g_t). Stationarity alone gives

Var⁡(gˉn)=1n2∑s,t=1nCov⁡(gs,gt)=σg2n[1+2∑k=1n−1(1−kn)ρk].\begin{aligned} \operatorname{Var}(\bar{g}_n)=\frac{1}{n^2}\sum_{s,t=1}^{n}\operatorname{Cov}(g_s,g_t) \\ &=\frac{\sigma_g^2}{n}\left[1+2\sum_{k=1}^{n-1}\left(1-\frac{k}{n}\right)\rho_k\right]. \end{aligned}

If ∑k∣ρk∣<∞\sum_k|\rho_k|<\infty, dominated convergence yields the limit

τint(g)=1+2∑k>1ρk.\tau_{\mathrm{int}}(g)=1+2\sum_{k>1}\rho_k.

Now assume the chain is lazy and reversible with nontrivial spectrum contained in [0,λ⋆][0,\lambda_\star], λ⋆<1\lambda_\star<1. Center and normalize the statistic so that

f=g−πgσg,⟨f,f⟩π=1.f=\frac{g-\pi g}{\sigma_g},\qquad\langle f,f\rangle_\pi=1.

Reversibility makes the Markov operator self-adjoint. Let νf\nu_f be the spectral probability measure of ff. Since ff is centered, νf\nu_f is supported on the nontrivial spectrum. Then

ρk=⟨f,Pkf⟩π=∫λk dνf(λ).\rho_k=\langle f,P^k f\rangle_\pi=\int\lambda^k\,d\nu_f(\lambda).

Because 0≤λ≤λ⋆<10\le\lambda\le\lambda_\star<1 on the support of νf\nu_f,

∣ρk∣≤λ⋆k,|\rho_k|\le\lambda_\star^k,

so absolute summability is automatic. Tonelli’s theorem then gives

τint(g)=∫(1+2∑k≥1λk)dνf(λ)=∫1+λ1−λ dνf(λ)≤1+λ⋆1−λ⋆=2trel−1.\begin{aligned} \tau_{\mathrm{int}}(g)=\int\left(1+2\sum_{k\ge1}\lambda^k\right)d\nu_f(\lambda) \\ &=\int\frac{1+\lambda}{1-\lambda}\,d\nu_f(\lambda) \\ &\le\frac{1+\lambda_\star}{1-\lambda_\star}=2t_{\mathrm{rel}}-1. \end{aligned}

The integrand is strictly increasing on [0,1)[0,1), so equality holds if and only if νf({λ⋆})=1\nu_f(\{\lambda_\star\})=1. This formulation remains correct when the spectral edge is not represented by a nonzero eigenspace.

For the sticky-refresh operator

P=(1−α)I+α1πT,P=(1-\alpha)I+\alpha\mathbf{1}\pi^{\mathsf{T}},

every centered ff satisfies Pf=(1−α)fPf=(1-\alpha)f. Hence ρk=(1−α)k\rho_k=(1-\alpha)^k and

τint(g)=1+1+(1−α)1−(1−α)=2−αα=2τ−1\tau_{\mathrm{int}}(g)=1+\frac{1+(1-\alpha)}{1-(1-\alpha)}=\frac{2-\alpha}{\alpha}=2\tau-1

for α=1/τ\alpha=1/\tau. This calculation does not require the statewise holding probability to be at least 1/21/2.

Proof of Theorem 6

Proof. Split Z1,…,ZnZ_1,\ldots,Z_n into BB consecutive batches of length L=⌊n/B⌋L=\lfloor n/B\rfloor (discard at most B−1B-1 trailing observations). Write gˉb=(1/L)∑t=(b−1)L+1bLg(Zt)\bar{g}_b=(1/L)\sum_{t=(b-1)L+1}^{bL}g(Z_t) and μ=E[gt]\mu=\mathbb{E}[g_t].

Step 1: the mixing budget. For a stationary finite-state Markov chain, β(k)=Eπ[∥Pk(Z0,⋅)−π∥TV]≤max⁡z∥Pk(z,⋅)−π∥TV\beta(k)=\mathbb{E}_\pi[\|P^k(Z_0,\cdot)-\pi\|_{\mathrm{TV}}]\le\max_z\|P^k(z,\cdot)-\pi\|_{\mathrm{TV}} ([5]), and for a reversible chain with nonnegative spectrum ([30 Ch. 12])

max⁡z∥Pk(z,⋅)−π∥TV≤Cπλ⋆k≤Cπe−k/trel,\max_z\|P^k(z,\cdot)-\pi\|_{\mathrm{TV}}\le C_\pi\lambda_\star^k\le C_\pi e^{-k/t_{\mathrm{rel}}},

with Cπ=12(1−πmin⁡)/πmin⁡C_\pi=\frac{1}{2}\sqrt{(1-\pi_{\min})/\pi_{\min}} and πmin⁡=min⁡zπ(z)\pi_{\min}=\min_z\pi(z), using λ⋆k≤e−k(1−λ⋆)\lambda_\star^k\le e^{-k(1-\lambda_\star)}. The constant cannot be set to one: Corollary 2 carries an envelope constant Bˉ\bar{B} for exactly this reason. For the sticky-refresh family used in every experiment β(a)=(1−1/τ)a\beta(a)=(1-1/\tau)^a exactly, so Cπ=1C_\pi=1 and trel=τt_{\mathrm{rel}}=\tau, and no envelope is needed.

Step 2: decorrelating the batch means. Consecutive batches share a boundary, so β\beta does not decouple them at any lag: the dependence between gˉb−1\bar{g}_{b-1} and gˉb\bar{g}_b is carried by the O(trel)O(t_{\mathrm{rel}}) observations on either side of the boundary, and its contribution to the joint law is ΔB,Ldep\Delta^{\mathrm{dep}}_{B,L}, which tends to zero as L/trel→∞L/t_{\mathrm{rel}}\to\infty because each batch mean is dominated by the L−O(trel)L-O(t_{\mathrm{rel}}) observations that have forgotten the previous batch. A finite-sample version of this step is available at a small cost in data: retaining only the last L−sL-s observations of each batch, with s≥trellog⁡(CπB/δ)s\ge t_{\mathrm{rel}}\log(C_\pi B/\delta), separates consecutive retained segments by s+1s+1 time steps, so Definition 1 applies at lag $s+1 and the induction of the supplementary material — with Z\mathcal{Z}-valued coordinates replaced by ZL−s\mathcal{Z}^{L-s}-valued ones — gives total-variation cost at most (B−1)β(s)≤δ(B-1)\beta(s)\le\delta, hence ΔB,Ldep≤δ\Delta^{\mathrm{dep}}_{B,L}\le\delta exactly. We state the theorem for the no-burn-in procedure because that is what the experiments evaluate.

Step 3: Student tt-validity on the decorrelated copy. The decorrelated batch means are i.i.d. copies of a [0,1][0,1]-valued random variable. The classical tt-interval is exactly valid only under normality, so we quantify the departure. Let σgˉ2=Var⁡(gˉ1)\sigma_{\bar{g}}^2=\operatorname{Var}(\bar{g}_1) and ρ3=E∣gˉ1−μ∣3<∞\rho_3=\mathbb{E}|\bar{g}_1-\mu|^3<\infty (finite, since gˉ1∈[0,1]\bar{g}_1\in[0,1]). By the Berry–Esseen bound for Student’s statistic [4 Theorem 1.2], for an absolute constant AA,

sup⁡x∣P(B(gˉ−μ)/SB≤x)−Φ(x)∣≤Aρ3σb3B=:12ΔBnorm,\sup_x\left|\mathbb{P}\left(\sqrt{B}(\bar{g}-\mu)/S_B\le x\right)-\Phi(x)\right|\le\frac{A\rho_3}{\sigma_b^3\sqrt{B}}=:\frac{1}{2}\Delta_B^{\mathrm{norm}},

where SB2=(B−1)−1∑b(gˉb−gˉ)2S_B^2=(B-1)^{-1}\sum_b(\bar{g}_b-\bar{g})^2. Applying this to each tail and using tB−1,α/2≥zα/2t_{B-1,\alpha/2}\ge z_{\alpha/2},

P(∣gˉ−μ∣>tB−1,α/2SBB)≤α+ΔBnorm.\mathbb{P}\left(\left|\bar{g}-\mu\right|>t_{B-1,\alpha/2}\frac{S_B}{\sqrt{B}}\right)\le\alpha+\Delta_B^{\mathrm{norm}}.

Because gˉ1\bar{g}_1 is itself an average of LL observations, its standardised third absolute moment converges to the Gaussian value 22/π2\sqrt{2/\pi} as L→∞L\to\infty, so ΔBnorm=O(B−1/2)\Delta_B^{\mathrm{norm}}=O(B^{-1/2}).

Step 4: translating to the original stream. Note that SB2=σ^BM2/LS_B^2=\hat{\sigma}_{BM}^2/L. Hence

tB−1,α/2SBB=tB−1,α/2σ^BM2/LB=tB−1,α/2σ^BMBL=wnad.t_{B-1,\alpha/2}\frac{S_B}{\sqrt{B}}=t_{B-1,\alpha/2}\frac{\sqrt{\hat{\sigma}_{BM}^2/L}}{\sqrt{B}}=t_{B-1,\alpha/2}\frac{\hat{\sigma}_{BM}}{\sqrt{BL}}=w_n^{\mathrm{ad}}.

The normalisation is BL\sqrt{BL} and not n\sqrt{n}: the certificate is computed on the BLBL observations that enter the batches, and BL≤nBL\le n, so replacing BL\sqrt{BL} by the larger n\sqrt{n} would report an interval narrower than the one proved valid. Since n−BL≤B−1n-BL\le B-1, the two differ by a factor 1+O(B/n)1+O(B/n). A union bound over Steps 2 and 3 gives P(∣gˉ−μ∣>wnad)≤α+ΔB,Ldep+ΔBnorm\mathbb{P}(|\bar{g}-\mu|>w_n^{\mathrm{ad}})\le\alpha+\Delta_{B,L}^{\mathrm{dep}}+\Delta_B^{\mathrm{norm}}, which is the theorem.

Step 5: width scaling. For a stationary chain with summable autocovariances, Var⁡(gˉb)=σg2τint(g)/L+O(1/L2)\operatorname{Var}(\bar{g}_b)=\sigma_g^2\tau_{\mathrm{int}}(g)/L+O(1/L^2) as L→∞L\to\infty (Proposition 5). Hence E[SB2]→σg2τint(g)/L\mathbb{E}[S_B^2]\to\sigma_g^2\tau_{\mathrm{int}}(g)/L and E[σ^BM2]=LE[SB2]→σg2τint(g)\mathbb{E}[\hat{\sigma}_{BM}^2]=L\mathbb{E}[S_B^2]\to\sigma_g^2\tau_{\mathrm{int}}(g). The squared half-width is therefore

(wnad)2=tB−1,α/22σ^BM2BL→tB−1,α/22σg2τint(g)BL∼σg2τint(g)n⋅(1+o(1)),\begin{aligned} (w_n^{\mathrm{ad}})^2=\frac{t_{B-1,\alpha/2}^2\hat{\sigma}_{BM}^2}{BL}\to\frac{t_{B-1,\alpha/2}^2\sigma_g^2\tau_{\mathrm{int}}(g)}{BL} \\ &\sim\frac{\sigma_g^2\tau_{\mathrm{int}}(g)}{n}\cdot(1+o(1)), \end{aligned}

since tB−1,α/2→zα/2t_{B-1,\alpha/2}\to z_{\alpha/2} as B→∞B\to\infty and BL≤n≤BL+(B−1)BL\le n\le BL+(B-1). The width is thus governed by τint(g)\tau_{\mathrm{int}}(g), not trelt_{\mathrm{rel}}, confirming the statistic-specific effective sample size.

ΔBnorm\Delta_B^{\mathrm{norm}} is explicit and vanishes as B−1/2B^{-1/2}, but it is not numerically tight at the batch counts used here (B=16B=16 to 4040): the Berry–Esseen constant is worst-case over all bounded laws, whereas batch means of a mixing chain are close to Gaussian well before BB is large. The empirical coverages of the main paper are at nominal in every cell, so the remainder is far from binding in practice.

The proof decorrelates the BB batch means and then applies a Student-tt interval on the decorrelated copy; the complete argument, including the constant CπC_\pi, is in the supplementary material. Two remarks fix the scope. First, the normalisation is BL\sqrt{BL} and not n\sqrt{n}: the certificate is computed on the BLBL observations that enter the batches, and BL≤nBL\le n, so dividing by the larger n\sqrt{n} would report an interval narrower than the one proved valid; since n−BL≤B−1n-BL\le B-1 the two differ by a factor 1+O(B/n)1+O(B/n). Second, ΔB,Ldep\Delta_{B,L}^{\mathrm{dep}} is not zero at finite LL, because consecutive batches share a boundary and β\beta controls dependence only across a gap. Inserting a burn-in of length s≥trellog⁡(CπB/δ)s\ge t_{\mathrm{rel}}\log(C_\pi B/\delta) at the start of each batch — discarding those observations from the batch mean — separates consecutive retained segments and drives ΔB,Ldep\Delta_{B,L}^{\mathrm{dep}} to an exact (B−1)β(s)≤δ(B-1)\beta(s)\le\delta, at the cost of the fraction s/Ls/L of the data.

The condition L≫trellog⁡(B/δ)L\gg t_{\mathrm{rel}}\log(B/\delta) is precisely the statement that this burn-in is a negligible fraction of the batch. We report the no-burn-in procedure because it is what our experiments evaluate. ◻

Scope of the two remainders. Since n−BL≤B−1n-BL\le B-1, dividing by n\sqrt{n} rather than BL\sqrt{BL} would report an interval narrower than the one proved valid, by a factor 1+O(B/n)1+O(B/n); at L=n2/3L=n^{2/3} this is O(n−1/3)O(n^{-1/3}). Regarding ΔB,Ldep\Delta_{B,L}^{\mathrm{dep}}: inserting a burn-in of length s≥trellog⁡(CπB/δ)s\ge t_{\mathrm{rel}}\log(C_\pi B/\delta) at the start of each batch, and discarding those observations from the batch mean, separates consecutive retained segments by s+1s+1 time steps and drives ΔB,Ldep\Delta_{B,L}^{\mathrm{dep}} to an exact (B−1)β(s)≤δ(B-1)\beta(s)\le\delta, at the cost of the fraction s/Ls/L of the data. The main paper’s condition L≫trellog⁡(B/δ)L\gg t_{\mathrm{rel}}\log(B/\delta) is precisely the statement that this burn-in is a negligible fraction of the batch. We report the no-burn-in procedure because it is what our experiments evaluate.

Proof of Theorem 7

Fix τ∈[1,n]\tau\in[1,n] and let α=1/τ\alpha=1/\tau. Consider the sticky-refresh chain with parameter τ\tau, marginal Bernoulli(p)(p), and the statistic g(z)=1{z=1}g(z)=\mathbf{1}\{z=1\} so that E[gt]=p\mathbb{E}[g_t]=p and τint(g)=2τ−1\tau_{\mathrm{int}}(g)=2\tau-1 (Proposition 5). Any procedure that is simultaneously valid at level 7/87/8 over the full family τ′∈[1,n]\tau'\in[1,n] must in particular be valid on the specific chain with parameter τ\tau. The argument of Theorem 8 applied to this fixed τ\tau gives the lower bound Ω(τ/n)\Omega(\sqrt{\tau/n}) on the interval width. Crucially, the procedure is given τ\tau: it must achieve coverage 7/87/8 simultaneously for every τ′∈[1,n]\tau'\in[1,n], and in particular for the fixed τ\tau under consideration. Since τint(g)=2τ−1=Θ(τ)\tau_{\mathrm{int}}(g)=2\tau-1=\Theta(\tau), the width lower bound cτ/n=Θ(τint(g)/n)c\sqrt{\tau/n}=\Theta(\sqrt{\tau_{\mathrm{int}}(g)/n}) holds on the chain with relaxation time τ\tau.

The key insight is that not knowing τ\tau does not help: even an oracle procedure that knows τ\tau must pay Ω(τ/n)\Omega(\sqrt{\tau/n}) (Theorem 8), so the adaptive procedure must pay this as well. The converse—that the adaptive batch-means certificate achieves this rate—is Theorem 6. Together they establish rate-optimality of adaptation.

Proof of Theorem 8

Fix α=1/τ\alpha=1/\tau and p±=1/2±Δ/2p_{\pm}=1/2\pm\Delta/2. The sticky-refresh kernel is

Pp(z,z′)=(1−α)1{z′=z}+απp(z′).P_p(z,z')=(1-\alpha)\mathbf{1}\{z'=z\}+\alpha\pi_p(z').

It is stationary under πp\pi_p, reversible by detailed balance, and has eigenvalues 11 and 1−α1-\alpha. Because p∈[1/4,3/4]p\in[1/4,3/4] and α∈(0,1]\alpha\in(0,1], all cross-state transition probabilities are positive and both states have positive holding probability; hence the chain is irreducible and aperiodic. Since τ≥1\tau\ge1, the second eigenvalue is nonnegative and the positive-part relaxation time of Corollary 4 is exactly τ\tau.

Generate a path as follows. First draw Z1∼Ber⁡(p)Z_1\sim\operatorname{Ber}(p). For t=2,…,nt=2,\ldots,n, draw independent refresh indicators Rt∼Ber⁡(α)R_t\sim\operatorname{Ber}(\alpha). If Rt=0R_t=0, set Zt=Zt−1Z_t=Z_{t-1}. If Rt=1R_t=1, draw a fresh Ut∼Ber⁡(p)U_t\sim\operatorname{Ber}(p) and set Zt=UtZ_t=U_t. The variables UtU_t are needed only on the event Rt=1R_t=1.

Let R=(R2,…,Rn)R=(R_2,\ldots,R_n). Its distribution is identical under p+p_+ and p−p_-. Conditional on R=rR=r, the parameter-dependent latent draws are the initial value Z1Z_1 and exactly ∑t=2nrt\sum_{t=2}^{n}r_t fresh Bernoulli variables. Therefore the chain rule for relative entropy gives

KL⁡(L+(R,Z1,{Ut:Rt=1})∥L−(R,Z1,{Ut:Rt=1}))=ER[(1+∑t=2nRt)KL⁡(Ber⁡(p+)∥Ber⁡(p−))]=[1+(n−1)α]KL⁡(Ber⁡(p+)∥Ber⁡(p−)).\begin{aligned} \operatorname{KL}\left(\mathcal{L}_{+}(R,Z_1,\{U_t:R_t=1\})\middle\|\mathcal{L}_{-}(R,Z_1,\{U_t:R_t=1\})\right) \\ &= \mathbb{E}_R\left[\left(1+\sum_{t=2}^{n}R_t\right)\operatorname{KL}\left(\operatorname{Ber}(p_{+})\middle\|\operatorname{Ber}(p_{-})\right)\right] \\ &=\left[1+(n-1)\alpha\right]\operatorname{KL}\left(\operatorname{Ber}(p_{+})\middle\|\operatorname{Ber}(p_{-})\right). \end{aligned}

The observed path Z1:nZ_{1:n} is a measurable function of this latent construction, so data processing yields

KL⁡(P+(n)∥P−(n))≤[1+(n−1)α]KL⁡(Ber⁡(p+)∥Ber⁡(p−)).\operatorname{KL}\left(P_{+}^{(n)}\middle\|P_{-}^{(n)}\right)\leq\left[1+(n-1)\alpha\right]\operatorname{KL}\left(\operatorname{Ber}(p_{+})\middle\|\operatorname{Ber}(p_{-})\right).

For Δ≤1/2\Delta\leq1/2, p±∈[1/4,3/4]p_{\pm}\in[1/4,3/4] and the elementary Bernoulli calculation gives

KL⁡(Ber⁡(p+)∥Ber⁡(p−))≤163Δ2.\operatorname{KL}\left(\operatorname{Ber}(p_{+})\middle\|\operatorname{Ber}(p_{-})\right)\leq\frac{16}{3}\Delta^{2}.

Because n≥τn\geq\tau,

1+(n−1)α≤1+nτ≤2nτ,1+(n-1)\alpha\leq1+\frac{n}{\tau}\leq\frac{2n}{\tau},

and hence

KL⁡(P+(n)∥P−(n))≤16nτΔ2.\operatorname{KL}\left(P_{+}^{(n)}\middle\|P_{-}^{(n)}\right)\leq16\frac{n}{\tau}\Delta^{2}.

Choose

Δ=18τn.\Delta=\frac{1}{8}\sqrt{\frac{\tau}{n}}.

Then Δ≤1/8\Delta\leq1/8, so p±∈[7/16,9/16]p_{\pm}\in[7/16,9/16], and the path KL is at most 1/41/4. Le Cam’s two-point inequality gives, for every test ψ∈{+,−}\psi\in\{+,-\},

max⁡s∈{+,−}Ps(ψ≠s)≥12(1−dTV(P+(n),P−(n))).\max_{s\in\{+,-\}}P_s(\psi\neq s)\geq\frac{1}{2}\left(1-d_{\mathrm{TV}}\left(P_{+}^{(n)},P_{-}^{(n)}\right)\right).

Pinsker’s inequality yields

dTV(P+(n),P−(n))≤12KL⁡(P+(n)∥P−(n))≤18,d_{\mathrm{TV}}\left(P_{+}^{(n)},P_{-}^{(n)}\right)\leq\sqrt{\frac{1}{2}\operatorname{KL}\left(P_{+}^{(n)}\middle\|P_{-}^{(n)}\right)}\leq\sqrt{\frac{1}{8}},

and therefore

max⁡s∈{+,−}Ps(ψ≠s)≥12(1−18)=:ctest.\max_{s\in\{+,-\}}P_s(\psi\neq s)\geq\frac{1}{2}\left(1-\sqrt{\frac{1}{8}}\right)=:c_{\mathrm{test}}.

Now let Cn=Cn(Z1:n;τ)C_n=C_n(Z_{1:n};\tau) be any measurable interval-valued certificate satisfying

Ps(ps∈Cn)≥78,s∈{+,−}.P_s(p_s\in C_n)\geq\frac{7}{8},\qquad s\in\{+,-\}.

Define a test explicitly by

ψ={+,p+∈Cn and p−∉Cn,−,p−∈Cn and p+∉Cn,+,otherwise.\psi= \begin{cases} +,&p_{+}\in C_n\text{ and }p_{-}\notin C_n,\\ -,&p_{-}\in C_n\text{ and }p_{+}\notin C_n,\\ +,&\text{otherwise}. \end{cases}

For either true model ss, an error can occur only if the true parameter is absent from the interval or both parameters are present. Therefore

Ps(ψ≠s)≤Ps(ps∉Cn)+Ps(p+∈Cn,p−∈Cn)≤18+Ps(width⁡(Cn)≥Δ).\begin{aligned} P_s(\psi\neq s)\leq P_s(p_s\notin C_n)+P_s(p_{+}\in C_n,p_{-}\in C_n) \\ &\leq\frac{1}{8}+P_s(\operatorname{width}(C_n)\geq\Delta). \end{aligned}

Combining this inequality with the testing lower bound shows that for at least one ss,

Ps(width⁡(Cn)≥Δ)≥ctest−18=:c1>0.P_s(\operatorname{width}(C_n)\geq\Delta)\geq c_{\mathrm{test}}-\frac{1}{8}=:c_1>0.

Thus the theorem holds with c0=1/8c_0=1/8 and

c1=12(1−18)−18>0.c_1=\frac{1}{2}\left(1-\sqrt{\frac{1}{8}}\right)-\frac{1}{8}>0.

The argument allowed the certificate to know τ\tau, so the lower bound is stronger than one in which the dependence scale must also be estimated.

To realize pp as a voting-margin probability, take X={0,1}\mathcal{X}=\{0,1\}, Y≡+1Y\equiv+1, and a single base hypothesis h(0)=+1h(0)=+1, h(1)=−1h(1)=-1. For F=hF=h and any fixed θ∈(0,1)\theta\in(0,1),

1{MF(X,Y)≤θ}=1{X=1},\mathbf{1}\{M_F(X,Y)\leq\theta\}=\mathbf{1}\{X=1\},

whose stationary mean is pp.

Mixing concentration and why block length matters

The main learned-vote result is stated directly in terms of β\beta-mixing because that is the quantity used by the coupling argument. This appendix explains why saying “blocks of length one mixing time are independent” is not a proof.

A conventional total-variation mixing time is defined at a fixed tolerance, often 1/41/4. Separation by one such time therefore gives only a constant one-boundary approximation error. If a sample is split into bb blocks and those errors are summed across b−1b-1 boundaries, the resulting bound can grow rather than vanish. Under geometric absolute regularity,

β(ℓ)≤Bexp⁡(−ℓ/τ),\beta(\ell)\leq B\exp(-\ell/\tau),

a pure coupling proof chooses ℓ\ell of order τlog⁡(n/δ)\tau\log(n/\delta) so that the total comparison budget is small. The number of retained approximately independent pieces is then on the order of

nτlog⁡(n/δ).\frac{n}{\tau\log(n/\delta)}.

Corollary 2 states this cost explicitly. For a fixed bounded statistic on a reversible Markov chain, one can avoid this pure-coupling logarithm by using spectral concentration directly, which is why the paper separates the learned-vote β\beta-mixing result from the fixed-vote Markov result.

A worked persistent-cluster example

Suppose a chain moves among KK clusters using the refresh kernel from Section 2.1. A fixed vote has cluster-specific error probabilities rkr_k. The stationary risk is L=K−1∑krkL=K^{-1}\sum_k r_k. If the error indicator were deterministically equal to a cluster-specific value, dependence would act only through the persistence of the cluster process. In the actual experiment, conditional Bernoulli noise adds an i.i.d. component.

Let CtC_t be the cluster and Et∣Ct∼Bernoulli⁡(rCt)E_t\mid C_t\sim\operatorname{Bernoulli}(r_{C_t}). Because the refresh chain has nontrivial eigenvalue 1−1/τ1-1/\tau, the centered cluster-risk function is an eigenfunction and

Cov⁡(rCt,rCt+k)=Vrλk.\operatorname{Cov}(r_{C_t},r_{C_{t+k}})=V_r\lambda^k.

Conditional errors are independent across times given the cluster path, so for k≥1k \ge1,

Cov⁡(Et,Et+k)=Vrλk.\operatorname{Cov}(E_t,E_{t+k})=V_r\lambda^k.

The marginal variance is rˉ(1−rˉ)\bar{r}(1-\bar{r}). Summing the covariance series yields Eq. (3). This exact calculation explains why the visible dependence scaling is compressed at small τ\tau: the i.i.d. floor does not disappear when persistence is weak.

Supplementary experiments: certificate coverage and robustness

The studies below are all for the fixed-vote regime, and each is interpreted for the generator it uses.

ExperimentQuantity reportedInterpretation
Certificate coveragei.i.d. versus corrected interval coveragenaive interval under-covers as persistence grows; corrected interval is conservative
Dependence misspecificationcoverage versus τ^/τ\hat{\tau}/\tausensitivity study for one generator, not a validity theorem
Block-length ablationcoverage versus block lengthshorter blocks retain dependence; finite-sample calibration remains imperfect
Trained ensembleinduced class-Markov streamcontrolled stress test, not natural dependence
Intrinsic-dependence streamordered versus shuffled coveragedependence intrinsic to the latent process, not injected
UCI HAR (real sensor)ordered versus shuffled coverage; adaptive certificate versus batch lengthnaturalistic evidence, fixed-vote regime only
Margin sweepmean margin versus gapdescriptive only; theorem uses lower-tail frequency
Dependence estimationspectral and scalar plug-insexploratory; uncertainty is not propagated

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

The coverage study fixes a vote and generates 2000 streams of length n=4000n=4000 per persistence setting. The naive i.i.d. interval covers with frequencies 0.944, 0.912, 0.601, and 0.436 at τ=1,5,25,100\tau=1,5,25,100, while the corrected interval covers with frequencies 0.944, 1.000, 1.000, and 1.000. Ignoring dependence therefore produces increasing undercoverage under this generator, while the corrected interval holds coverage at or above the nominal level; the interval half-widths behind these frequencies are reported in Appendix § 26.2.

Full numerical grid for the rate experiment

The full grid behind Figure 2 is given below. The bottom half reports the normalization by τ/n\sqrt{\tau/n}. These ratios are not constant over the full sweep, which is why the main text uses the exact two-component variance interpretation instead of claiming a pure one-parameter collapse.

τ\taunn
5002000800032000
10.0189130.0102080.00331250.002226
50.0225630.0117810.00500830.0022539
250.0249370.0150540.00850700.0039052
1000.0459330.0389080.0137220.0085642
ratio ∣L^−L∣/τ/n\lvert\hat{L}-L\rvert/\sqrt{\tau/n}
10.4230.4570.2960.398
50.2260.2360.2000.180
250.1120.1350.1520.140
1000.1030.1740.1230.153

Table 6. Mean fixed-vote gaps and their τ/n\sqrt{\tau/n} normalization for every cell.

Supplementary trained-ensemble results

The class-Markov study in the main paper reports the aggregate coverage results; the full training and stream protocol is given in the supplementary material. Each ensemble member is a small convolutional network (two 3×33 \times3 convolutions with 16 and 32 channels, global pooling, and a linear head), trained with Adam at learning rate 10−310^{-3} on a fixed training subset, with member mm using seed 1000+m1000+m. The vote is the fixed majority over the MM ensemble members.

Neither model is presented as competent: 46–62% error is weak in absolute terms. The value of the experiment is not benchmark quality but that the classifier is a genuine fixed vote whose evaluation dependence is controlled without retraining.

The margin sweep at fixed dependence

This study holds τ=25\tau=25 and varies the ensemble size M∈{1,3,5,9,15}M \in\{1,3,5,9,15\}, over 200 evaluation streams. The predictor is multiclass, so the voting margin of an example with true label yy is the Schapire-style vy−max⁡c≠yvcv_y-\max_{c\ne y}v_c, where vcv_c is the fraction of the MM ensemble members voting for class cc; the margin lies in [−1,1][-1,1]. Because ties count as errors, the mass at or below margin zero equals the stationary error rate.

This correlation is descriptive rather than theorem-aligned: Theorem 1 depends on the lower-tail frequency T^(F,θ)\hat{T}(F,\theta) at a specified threshold, not on the mean margin, and the mean can improve while the low-margin tail worsens. The theorem’s object is the empirical margin tail itself. At M=15M=15 the measured tail θ↦T^(F,θ)\theta\mapsto\hat{T}(F,\theta) is 0.24 at θ=−0.5\theta=-0.5, 0.38 at θ=−0.25\theta=-0.25, 0.48 at θ=0\theta=0, 0.55 at θ=0.25\theta=0.25, and 0.65 at θ=0.5\theta=0.5. A theorem-aligned learned-vote experiment would predeclare a finite threshold grid, allocate confidence across the grid as described after Theorem 1, select the smallest simultaneous certificate, and select the vote from the dependent sample rather than fixing it in advance.

MM135915
mean voting margin−0.220.040.030.080.11
margin mass below 00.610.550.550.500.48
generalization gap0.0290.0220.0250.0210.020

Table 7. Descriptive margin sweep at fixed τ=25\tau= 25 on MNIST. As MM 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=9M = 9 value 0.50 matches the main study’s MNIST error 0.46 up to the difference between two independently trained ensembles.

The same sweep on CIFAR-10 is a null result and is reported as such. Over M∈{1,3,5,9,15}M \in\{1, 3, 5, 9, 15\} the mean voting margin rises from −0.30 to −0.14, but it stays negative throughout and the generalization gap does not follow it: the gaps are 0.012, 0.015, 0.013, 0.014, and 0.015, essentially flat, and the gap–mean-margin correlation is +0.65 (the sign opposite to the sharpening trend seen on MNIST, where the correlation is −0.94). When the margin never crosses zero, growing the vote does not sharpen the low-margin tail, and the margin heuristic carries no predictive signal for the gap.

Integrated-autocorrelation constant on the sticky-refresh family

This experiment compares the measured variance inflation with (1+λ)/(1−λ)(1+\lambda)/(1-\lambda). The equality is not valid for an arbitrary statistic on an arbitrary reversible chain, but it is exact for the sticky-refresh family because every centered statistic is an eigenfunction with eigenvalue λ\lambda.

For λ∈{0,0.5,0.8,0.9,0.96}\lambda\in\{0, 0.5, 0.8, 0.9, 0.96\}, over 4000 runs at n=4000n = 4000, the values are

λ\lambda00.50.80.90.96
(1+λ)/(1−λ)(1+\lambda)/(1-\lambda)1.03.09.019.049.0
measured variance inflation1.003.029.0619.5648.03

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.

The maximum relative error is under 3%. The table is specific to the sticky-refresh kernel, for which the centered threshold statistic has spectral measure concentrated at a single point; it is not claimed for an arbitrary reversible chain and statistic.

Certificate coverage and width

This appendix gives the interval half-widths behind the coverage frequencies summarized in Appendix S17. All entries are at nominal 0.95 over 2000 streams of length n=4000n = 4000, and every width is the half-width (radius) ≤zp^(1−p^)/neff\le z\sqrt{\hat p(1-\hat p)/n_{\rm eff}} with z=1.96z = 1.96.

τ\tau1525100
I.i.d. interval coverage0.9440.9120.6010.436
Corrected interval coverage0.9441.0001.0001.000
Corrected interval half-width0.01450.03400.07470.1498
Corrected/i.i.d. width ratio1.02.25.010.0

Table 9. Coverage and interval half-width at nominal 0.95 over 2000 streams of length n=4000n = 4000 (Wilson 95% binomial intervals on each coverage entry have half-width ≤0.022\leq0.022). The corrected interval is conservative; the width ratio equals the built-in dependence multiplier τ\sqrt{\tau}.

Coverage alone is insufficient to establish a useful certificate; the interval must also be informative. At τ=100\tau= 100 the corrected half-width 0.1498 is about 15% of the risk scale, so the interval is conservative but far from vacuous. The i.i.d. undercoverage is statistically unambiguous: at τ=25,100\tau= 25, 100 the Wilson 95% interval on the i.i.d. coverage (0.601 and 0.436) is [0.579, 0.622] and [0.414, 0.458], both far below nominal.

Sensitivity to a misspecified dependence scale

This study sweeps τ^/τ∈{0.5,1,2,4}\hat{\tau}/\tau\in\{0.5, 1, 2, 4\} at true τ=25\tau= 25, with n=4000n = 4000. The resulting coverages are 0.999, 1.000, 1.000, and 1.000, with mean half-widths 0.0521, 0.0737, 0.1042, and 0.1474 (each step scaling by 2\sqrt{2} as τ^\hat{\tau} doubles). The interval is thus conservative even when the dependence scale is underestimated twofold, and overestimation only widens it. This is a finite-generator sensitivity result, not a general guarantee: a valid confidence statement can still fail when the dependence scale is underestimated on a different process. The supported claim is that, for this generator and these interval constants, coverage was conservative across the tested misspecification range.

Block-length ablation

At true τ=25\tau= 25 with n=4000n = 4000, the block-length ratio ℓ/τ∈{0.25,0.5,1,2,4}\ell/\tau\in\{0.25, 0.5, 1, 2, 4\} gives coverages 0.699, 0.746, 0.814, 0.872, and 0.909, with mean half-widths 0.0180, 0.0203, 0.0238, 0.0274, and 0.0302.

ℓ/τ\ell/\tau0.250.5124
blocks6663331608040
coverage0.6990.7460.8140.8720.909
mean half-width0.01800.02030.02380.02740.0302

Table 10. Block-length ablation at τ=25\tau= 25, n=4000n = 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.

Very short blocks retain substantial dependence and undercover; coverage improves as ℓ\ell grows past τ\tau but the largest tested value remains below nominal 0.95, since increasing ℓ\ell also reduces the number of blocks. Block lengths are integers, so the two smallest ratios correspond to ℓ=6\ell= 6 and ℓ=12\ell= 12, i.e. effective ratios 0.24 and 0.48. The ablation illustrates the block-length tradeoff rather than identifying a single optimal ℓ\ell.

Exploratory estimation of the dependence scale

This study compares a spectral plug-in derived from the empirical class-transition matrix with a lag-one autocorrelation plug-in from the binary error sequence.

true simulation parameter τ\tau1525100
spectral plug-in1.05.836.5247
autocorrelation plug-in1.01.11.11.1
coverage, spectral plug-in0.921.001.001.00
coverage, autocorrelation plug-in0.920.870.650.33

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

The spectral plug-in is conservative and substantially biased upward at slow mixing: 247 for a simulation parameter of 100. Coverage 0.92 at the independent endpoint is below the nominal 0.95 level. The scalar autocorrelation plug-in fails badly on this heterogeneous-error vote. These results do not establish a valid adaptive certificate. A second eigenvalue of an empirical transition matrix is also not a Fiedler eigenvector of an arbitrary dependency graph. The paper therefore makes no claim that the method works without knowledge of dependence.

Scope of the natural-dependence evidence

The naturalistic evidence in this paper is the UCI HAR study of Appendix S3.2: a real temporally ordered sensor stream with no synthetic dependence generator, evaluated by a fixed nine-member committee vote. It reports the measured dependence scale (τ^int≈10.5\widehat{\tau}_{\mathrm{int}} \approx10.5 at L=50L = 50, growing to ≈16\approx16 at L=400L = 400), naive i.i.d. undercoverage on the ordered stream (0.38 at n=2000n = 2000, worsening to 0.35 at n=20000n = 20000), the adaptive certificate of Theorem 6 attaining nominal coverage (0.95 at n=20000n = 20000) precisely where its batch-length condition holds and falling short where it does not (0.78 at n=2000n = 2000), and a shuffled control restoring naive coverage to 0.94–0.96, which isolates real temporal ordering as the cause. Appendix S3.1 provides a matched intrinsic-dependence control under the same protocol.

Two extensions remain outside the present evidence. The first is a naturally ordered stream evaluated with a learned vote — AdaBoost, random forest, or deep ensemble selected from the dependent sample itself — reporting theorem-aligned margin-tail curves and nonvacuity diagnostics for the Theorem 1 certificate rather than the fixed-vote intervals reported here; the learned-vote certificate is currently exercised only on the synthetic sticky-refresh stream, where β(a)\beta(a) is known in closed form. The second is a reinforcement-learning replay stream, where Markov dependence is intrinsic to the trajectory, with the same evaluation repeated on trajectory-preserving and shuffled controls. Both would extend the naturalistic evidence from the fixed-vote regime, where it now exists, to the learned-vote regime, which no experiment in this paper currently tests.

Experimental protocol

Ensemble members. Each of the MM members is a convolutional network with two 3×33 \times3 convolutions (16 and 32 channels, ReLU), global average pooling, and a linear head to the 10 classes. Members are trained independently with Adam at learning rate 10−310^{-3}, batch size 128, on a random 20,000-example subsample of the training set; member mm uses seed 1000+m1000 + m for both initialization and subsampling. Training runs for 3 epochs on MNIST and 12 epochs on CIFAR-10; no augmentation or normalization beyond the dataset’s native scaling is applied. The fixed vote is the majority over the MM members, and its margin is the multiclass margin defined in Appendix S20.

Stationary risk. The target risk is the uniform-class-averaged error of the fixed vote on the i.i.d. test set, which matches the stationary class law of the evaluation chain and removes the class-imbalance bias of the raw test-marginal error.

Evaluation stream. The dependence is a Markov chain over the class label with kernel P(c,c′)=(1−1/τ)1{c′=c}+(1/τ)K−1P(c,c') = (1 - 1/\tau)1\{c' = c\} + (1/\tau)K^{-1} for K=10K = 10 classes, started from the uniform stationary law; at each step a test example of the drawn class is sampled uniformly with replacement. The main ensemble study uses M=9M = 9, 300 streams per τ∈{1,5,25,100}\tau\in\{1, 5, 25, 100\}, and stream lengths n∈{500,2000,8000}n \in\{500, 2000, 8000\}; the margin sweep fixes τ=25\tau= 25 with 200 streams.

Interval construction. Every reported interval is the normal half-width zp^(1−p^)/neffz\sqrt{\hat p(1-\hat p)/n_{\mathrm{eff}}} with z=1.96z = 1.96, where p^\hat p is the empirical stream risk. The i.i.d. interval uses neff=nn_{\mathrm{eff}} = n and the corrected interval uses neff=n/τn_{\mathrm{eff}} = n/\tau; the coverage, misspecification, and block-length studies use n=4000n = 4000. Reported “width” is this half-width (a radius); Theorem 8’s width(CnC_n) is the full interval u−ℓu-\ell and is therefore twice this quantity. No clipping at one is applied to the reported radii.

Computing infrastructure. All experiments were run on [GPU MODEL] (e.g. a single NVIDIA RTX 4090 with 24 GB memory) with [CPU MODEL] and [XX] GB system RAM, under [OS, e.g. Ubuntu 22.04]. The deep-ensemble ResNet-18 studies use PyTorch [X.Y] with CUDA [X.Y]; all synthetic-stream, certificate, and interval computations use Python [3.X] with NumPy [X.Y], SciPy [X.Y], and scikit-learn [X.Y]. Total compute is approximately [N] GPU-hours, dominated by the ResNet-18 ensemble training; every other study runs in minutes on CPU.

References

  1. [1]Aden-Ali, I.; Høgsgaard Møller, M.; Green Larsen, K.; and Zhivotovskiy, N. 2024. Majority-of-Three: The Simplest Optimal Learner? In Proceedings of the Thirty-Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, 22–45. Legacy citation key retained for source compatibility.arxiv.org/abs/2403.08831
  2. [2]Anguita, D.; Ghio, A.; Oneto, L.; Parra, X.; and Reyes-Ortiz, J. L. 2013. A Public Domain Dataset for Human Activity Recognition Using Smartphones. In 21st European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN), 437–442.
  3. [3]Bartlett, P. L.; and Mendelson, S. 2002. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 3: 463–482.DOI
  4. [4]Bentkus, V.; and Götze, F. 1996. The Berry–Esseen Bound for Student’s Statistic. The Annals of Probability, 24(1): 491–503.DOI
  5. [5]Bradley, R. C. 2005. Basic Properties of Strong Mixing Conditions. A Survey and Some Open Questions. Probability Surveys, 2: 107–144.
  6. [6]Breiman, L. 1996. Bagging Predictors. Machine Learning, 24(2): 123–140.
  7. [7]Breiman, L. 2001. Random Forests. Machine Learning, 45(1): 5–32.
  8. [8]Catoni, O. 2007. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, volume 56 of IMS Lecture Notes Monograph Series. Institute of Mathematical Statistics.DOI
  9. [9]Dagan, Y.; Daskalakis, C.; Dikkala, N.; and Jayanti, S. 2019. Learning from Weakly Dependent Data under Dobrushin’s Condition. In Conference on Learning Theory (COLT). ArXiv:1906.09247.arxiv.org/abs/1906.09247
  10. [10]Freund, Y.; and Schapire, R. E. 1997. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1): 119–139.DOI
  11. [11]Gao, W.; and Zhou, Z.-H. 2013. On the Doubt about Margin Explanation of Boosting. Artificial Intelligence, 203: 1–18.arxiv.org/abs/1009.3613
  12. [12]Germain, P.; Lacasse, A.; Laviolette, F.; Marchand, M.; and Roy, J.-F. 2015. Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm. Journal of Machine Learning Research, 16(26): 787–860.arxiv.org/abs/1503.08329
  13. [13]Gillman, D. 1998. A Chernoff Bound for Random Walks on Expander Graphs. SIAM Journal on Computing, 27(4): 1203–1220.
  14. [14]Green Larsen, K.; and Schalburg, N. 2025. Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets. arXiv:2511.20407.arxiv.org/abs/2511.20407
  15. [15]Guedj, B. 2019. A Primer on PAC-Bayesian Learning. arXiv preprint arXiv:1901.05353.arxiv.org/abs/1901.05353
  16. [16]Hanneke, S. 2016. The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research, 17: 1–15.arxiv.org/abs/1507.00473
  17. [17]Høgsgaard Møller, M.; and Green Larsen, K. 2025. Improved Margin Generalization Bounds for Voting Classifiers. Inarxiv.org/abs/2502.16462
  18. [19]Joulin, A.; and Ollivier, Y. 2010. Curvature, Concentration and Error Estimates for Markov Chain Monte Carlo. The Annals of Probability, 38(6): 2418–2442.DOI
  19. [20]Koltchinskii, V.; and Panchenko, D. 2002. Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers. The Annals of Statistics, 30(1): 1–50.DOI
  20. [21]Kontorovich, A.; and Weiss, R. 2014. Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-Type Inequalities for Markov Chains and Related Processes. Journal of Applied Probability, 51(4): 1100–1113.
  21. [22]Kontorovich, L. A.; and Ramanan, K. 2008. Concentration Measure for Markov Chains and Approximate Counting. The Annals of Probability, 36(6): 2126–2158.
  22. [23]Krizhevsky, A. 2009. Learning Multiple Layers of Features from Tiny Images. Technical report, University of Toronto, Toronto, Ontario.
  23. [24]Kuznetsov, V.; and Mohri, M. 2017. Generalization Bounds for Non-Stationary Mixing Processes. Machine Learning, 106(1): 93–117.DOI
  24. [25]Lacasse, A.; Laviolette, F.; Marchand, M.; Germain, P.; and Usunier, N. 2006. PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier. In Advances in Neural Information Processing Systems (NeurIPS).
  25. [26]Langford, J.; and Shawe-Taylor, J. 2002. PAC-Bayes and Margins. Advances in Neural Information Processing Systems (NeurIPS).
  26. [27]LeCun, Y.; Bottou, L.; Bengio, Y.; and Haffner, P. 1998. Gradient-Based Learning Applied to Document Recognition. Proceedings of the IEEE, 86(11): 2278–2324.
  27. [28]Ledoux, M.; and Talagrand, M. 1991. Probability in Banach Spaces: Isoperimetry and Processes. Springer.DOI
  28. [30]Levin, D. A.; and Peres, Y. 2017. Markov Chains and Mixing Times. American Mathematical Society, 2nd edition.
  29. [31]Lézaud, P. 1998. Chernoff-Type Bound for Finite Markov Chains. The Annals of Applied Probability, 8(3): 849–867.DOI
  30. [32]Marton, K. 1996. Bounding d̄-Distance by Informational Divergence: A Method to Prove Measure Concentration. The Annals of Probability, 24(2): 857–866.DOI
  31. [33]Masegosa, A. R.; Lorenzen, S. S.; Igel, C.; and Seldin, Y. 2020. Second Order PAC-Bayesian Bounds for the Weighted Majority Vote. In Advances in Neural Information Processing Systems (NeurIPS).arxiv.org/abs/2007.13532
  32. [34]Maurer, A. 2004. A Note on the PAC-Bayesian Theorem. arXiv preprint cs/0411099.DOI
  33. [35]McAllester, D. A. 1999. Some PAC-Bayesian Theorems. Machine Learning, 37(3): 355–363.
  34. [36]Mohri, M.; and Rostamizadeh, A. 2008. Rademacher Complexity Bounds for Non-I.I.D. Processes. In Advances in Neural Information Processing Systems, volume 21, 1097–1104.
  35. [37]Mohri, M.; and Rostamizadeh, A. 2010. Stability Bounds for Stationary φ-mixing and β-mixing Processes. Journal of Machine Learning Research, 11: 789–814.
  36. [38]Mohri, M.; Rostamizadeh, A.; and Talwalkar, A. 2018. Foundations of Machine Learning. MIT Press, 2nd edition.DOI
  37. [39]Paulin, D. 2015. Concentration Inequalities for Markov Chains by Marton Couplings and Spectral Methods. Electronic Journal of Probability, 20: 1–32.arxiv.org/abs/1212.2015
  38. [40]Ralaivola, L.; Szafranski, M.; and Stempfel, G. 2010. Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary β-Mixing Processes. Journal of Machine Learning Research, 11: 1927–1956.arxiv.org/abs/0909.1933
  39. [41]Reyzin, L.; and Schapire, R. E. 2006. How Boosting the Margin Can Also Boost Classifier Complexity. In International Conference on Machine Learning (ICML), 753–760.DOI
  40. [42]Samson, P.-M. 2000. Concentration of Measure Inequalities for Markov Chains and Φ-Mixing Processes. The Annals of Probability, 28(1): 416–461.DOI
  41. [43]Schapire, R. E.; and Freund, Y. 2012. Boosting: Foundations and Algorithms. MIT Press.
  42. [44]Schapire, R. E.; Freund, Y.; Bartlett, P.; and Lee, W. S. 1998. Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods. The Annals of Statistics, 26(5): 1651–1686.
  43. [45]Seeger, M. 2002. PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification. Journal of Machine Learning Research, 3: 233–269.DOI
  44. [46]Shalev-Shwartz, S.; and Ben-David, S. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.
  45. [47]Shihab, I. F.; Akter, S.; and Sharma, A. 2026. Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence. arXiv:2604.13414.arxiv.org/abs/2604.13414
  46. [48]Steinwart, I.; Hush, D.; and Scovel, C. 2009. Learning from Dependent Observations. Journal of Multivariate Analysis, 100(1): 175–194.arxiv.org/abs/0707.0303
  47. [49]Thiemann, N.; Igel, C.; Wintenberger, O.; and Seldin, Y. 2017. A Strongly Quasiconvex PAC-Bayesian Bound. In International Conference on Algorithmic Learning Theory (ALT).arxiv.org/abs/1608.05610
  48. [50]Vapnik, V. N. 1998. Statistical Learning Theory. Wiley.
  49. [51]Yu, B. 1994. Rates of Convergence for Empirical Processes of Stationary Mixing Sequences. The Annals of Probability, 22(1): 94–116.DOI

Paper details

vlnc:W_q4faqgyg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents