Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence

1 Introduction

• Existing Bernstein bounds for dependent data often rely on unknown mixing or spectral-gap quantities, whereas the paper uses observed regeneration times; empirical Bernstein methods for i.i.d. data replace population variance with an observable estimate [31].The motivation is to make bounds evaluable from a single trajectory and usable in learning criteria.Source: §1 · pp. 1–2
• Truncating centered cycle rewards and stopping an exponential supermartingale at the first cycle beyond the horizon yields a self-normalized Bernstein bound with observed cycle-length terms and an explicit tail remainder.A finite deterministic tuning-parameter collection gives an empirical version; its quadratic term uses observed squared cycle lengths below the truncation level, with corrections for longer cycles and the horizon-crossing cycle.Source: §1 · p. 2
• PAC-Bayes bounds for classifiers on non-i.i.d. regenerative data yield Gibbs-posterior oracle inequalities in probability and in expectation.The paper also proposes agnostic learning objectives that minimize only the first-order term while retaining oracle inequalities.Source: §1 · p. 2
• Under a normalized cycle-length moment condition above two and initialization at regeneration, fixed-confidence estimation error is of order p m/n; for integer m, a matching lower bound establishes minimax optimality.The comparison identifies n/m as the effective number of independent observations.Source: §1 · p. 2
• Combining Bernstein control of empirical centering with the regenerative strong approximation of Bashtova and Shashkin [10] yields a self-normalized Gaussian approximation and studentized asymptotic normality.The result assumes the moment and initialization conditions used in the minimax analysis, a fixed loss, and positive asymptotic variance.Source: §1 · p. 2

1.1 Background and Related Literature

• Prior work covers regenerative Markov-chain concentration [16], empirical-process and block-complexity bounds [2], and trajectory-dependent inequalities [24].Earlier dependent-data PAC-Bayes bounds share the need for prior knowledge of temporal dependence [1, 20, 28–30, 33, 34, 36, 37, 43, 44, 44, 50]; this work covers general regenerative, including non-Markovian, processes without estimating a mixing coefficient or spectral gap [21] [47] [49] [26] [25]. The paper notes that non-asymptotic coverage is lost, while agnostic learning rules remain possible [26].Source: §1.1 · pp. 3–4

2 Statement of the problem and notations

• The process is regenerative when each post-regeneration shifted trajectory is independent of the preceding filtration and has a common law; the marked cycles are assumed i.i.d., positive-integer length, finite-mean, and independent of the initial delay.The process may start from an arbitrary initial distribution, and regeneration boundaries are observed.Source: §2 · p. 4
• The framework includes regenerative Markov chains and non-Markovian processes, and can preserve the regeneration times under a measurable transformation of a process.Harris recurrent Markov chains can acquire regeneration through Nummelin splitting.Source: §2 · p. 4
• The objective is an empirical confidence bound for a bounded function’s deviation from its equilibrium expectation, based only on the single observed trajectory rather than unknown distribution parameters.For machine learning, the bounded functions are parameterized losses and the target is the risk.Source: §2 · pp. 4–5
• The regenerative formulation uses block losses and centered discrepancies; Kac’s lemma gives a risk identity that centers the discrepancies and supports the exponential-supermartingale argument.The cycle discrepancy has zero post-regeneration expectation and is bounded in absolute value by the cycle length.Source: §2 · p. 5
• The number of completed cycles is random, and the sample may include a final cycle that crosses the observation horizon; the remaining portion outside completed cycles is tracked separately.The text identifies the first cycle ending after n and defines the completed-block empirical risk when completed-cycle duration is positive.Source: §2 · p. 5
• Because bounded losses can have unbounded block sums, the analysis compares centered cycle discrepancies with versions truncated according to cycle length.The truncation level is finite and deterministic.Source: §2 · p. 5

• Theorem 3.1 gives a self-normalized Bernstein inequality for fixed deterministic truncation and tuning parameters, with the bound defined as infinite when D_n=0.Source: §3 · p. 6
• A finite deterministic tuning collection yields an empirical Bernstein bound, with the regeneration-tail term as the sole nonempirical term.The paper notes that this term can be ignored in learning objectives under exponential tails, but need not be second-order under some polynomial tails.Source: §3 · pp. 6–7
• Integrating the deviation inequality separates the truncated second moment, tail contribution, and expected length outside completed cycles.Source: §3 · p. 7
• For cycles bounded by k, the paper specializes the bound using D_n ≤ 2k and v(u_n) ≤ k^2, with β(k)=0.The example includes i.i.d. data when k=1.Source: §3 · p. 7
• With sufficiently light tails, the paper expects the tail, truncation, and cycle-count terms to be second-order relative to the leading n^-1/2 rate.Source: §3 · pp. 6–7

4.1 Regeneration for Markov chains

• Returns to an accessible atom yield i.i.d. regenerative blocks when the return times are almost surely finite and the cycle lengths have finite mean.Source: §4.1 · p. 8
• For a Markov chain without an accessible atom, Nummelin splitting constructs one from a small-set minorization, but practical use requires knowing the set and minorization probability.For an r-step construction, applying bounds to all intermediate observations requires separately verifying an i.i.d. cycle construction.Source: §4.1 · p. 8

4.2 Expected deviations under regeneration-length assumptions

• Under exponential regeneration tails, the tail contribution is O((log n)/n), while under polynomial tails its order and whether it is second-order depend on the exponent and cycle moments.For α>2 the tail term is o(n^-1/2); at α=2 it is O(n^-1/2), and for 1<α<2 it can match the optimized quadratic and truncation terms.Source: §4.2 · pp. 10–11
• For polynomial tails with 1<α<2, the tail contribution can be leading order, and under a precise power-law tail it has the stated asymptotic equivalent.The polynomial upper-tail assumption alone does not force this behavior because it also permits faster-decaying tails.Source: §4.2 · p. 11
• At α=2, the tail assumption does not ensure a finite second cycle-length moment; if that moment is finite, the rate improves to O(n^-1/2).In that case the actual tail term is o(n^-1/2), although the truncation correction remains order n^-1/2.Source: §4.2 · p. 11

4.3 A non-Markovian example

• The non-Markovian Geo/D/1 queue has i.i.d. marked cycles and an expected deviation bound of order n^-1/2, with an O((log n)/n) tail contribution.Its finite-sample bound can use only p and n by replacing r_n with (n+1)/n.Source: §4.3 · p. 12

5.1 PAC-Bayes bounds

• Minimizing the PAC-Bayes bound over posteriors yields randomized classifiers that satisfy oracle inequalities in probability and expectation.The classification risk is the generalization risk, and the posterior is a sample-dependent distribution over classifiers.Source: §5.1 · p. 13, §5 · p. 13
• The PAC-Bayes learning objective uses observable empirical quantities and excludes terms depending on the tails of the cycle lengths.Unlike earlier empirical PAC-Bayes attempts, its minimization does not require estimating non-empirical terms [25].Source: §5.1 · p. 13

5.2 Oracle risk bound in expectation

• A finite deterministic tuning grid yields a selected posterior whose oracle risk bound requires no information about regeneration tails.The grid penalty comes from a union bound; the selection criterion omits a common upper-bounded remainder independent of the tuning parameter.Source: §5.2 · pp. 14–15
• With exponential regeneration tails, the omitted explicit terms are second order for fixed prior-mass parameters, so omitting the tail term does not affect the leading rate.The stated grid and selection criterion also do not depend on the unknown tail parameters.Source: §5.2 · p. 15

6 Minimax upper and lower bounds

• The upper-bound argument chooses a truncation level and tuning parameter under which completed cycles cover at least half the observation horizon with high probability.The moment condition controls both the quadratic term and the discarded tail.Source: §6 · p. 16
• The lower-bound comparison uses a scalar model with observations in [0, 1] and i.i.d. regenerative blocks of positive integer lengths with mean m.The observations start at a regeneration time, and estimators may use observed regeneration boundaries.Source: §6 · p. 16
• The minimax estimation error has the same order of dependence on mean cycle length m and sample size n as the upper bound, under the stated moment condition.For integer m, Theorem 6.1 gives a matching lower bound; the analysis starts at a regeneration time.Source: §6 · p. 16

• The Bernstein inequality controls empirical centering of the completed-block variance estimator, which is combined with a regenerative strong approximation.The approximation uses an observable block variance estimator.Source: §7 · p. 17
• The result assumes i.i.d. regenerative blocks with positive integer lengths and the moment condition (6.1), with the regenerative law and θ fixed as n grows.Source: §7 · p. 17
• A realization of the losses, regeneration boundaries, and a standard Brownian motion satisfies the stated almost-sure approximation.Source: §7 · p. 17
• The normalized processes converge in distribution to standard Brownian motion in D[0, 1] with the usual Skorokhod topology.Source: §7 · p. 17

8.1 Proof of Theorem 3.1

• Theorem 3.1’s proof applies a stopped exponential bound to both signs, then accounts for the cycle crossing time n and restores truncated rewards.The completed-cycle empirical risk is used on {Dn > 0}; a convention handles Dn = 0.Source: §8.1 · p. 19

8.2 Proof of Corollary 3.1

• Corollary 3.1’s proof makes the inequality simultaneous over a finite deterministic tuning-parameter grid, allowing selection using observed block lengths.A union bound gives a common event for the grid’s inequalities.Source: §8.2 · p. 20

8.3 Proof of Theorem 3.2

• Theorem 3.2’s proof integrates the Bernstein tail bound to control deviation weighted by Dn, then accounts for the length outside completed cycles.It uses an expectation identity for sums through the first cycle ending after n.Source: §8.3 · pp. 21–22

• As un = O(log n), the tuning constraint is eventually inactive, λn is asymptotic to (1 + log 2)mn/v2, and the other terms are O((log n)/n).The square-root term has the leading constant stated in (4.6).Source: §8.4 · p. 24
• For α > 2 the deviation rate is O(n^-1/2); at α = 2 it is O(√((log n)/n)); for 1 < α < 2, the square-root, tail, and truncation terms are O(n^-(α-1)/α).At α = 2 the tail and truncation terms are O(n^-1/2), while the age term is O((log n)/n).Source: §8.4 · p. 25
• For polynomial tails, β(u) ∼ αc/(α − 1)u^(1−α).Source: §8.4 · p. 25
• When cycle tails satisfy P_A(∆1 > t) ∼ c t^-α, the tail contribution can be leading for 1 < α < 2; at α = 2 with finite v2, all remaining terms are O(n^-1/2).Source: §8.4 · p. 25

8.5 Proof of Corollary 4.3

• The queue-length process is not Markov in its natural filtration, yet its marked cycles are i.i.d. and have finite moments of every order.The proof establishes almost-surely finite regeneration times and an exponential cycle-length tail.Source: §8.5 · p. 26

8.6 Proof of Theorem 5.1

• Theorem 5.1’s proof applies a stopped PAC–Bayes inequality, restricts the sum to completed cycles, and restores losses excluded by truncation.It derives (5.1) on a common event simultaneously for all posteriors ρ ≪ µ.Source: §8.6 · pp. 28–29

8.7 Proof of Theorem 5.2

• Theorem 5.2’s proof controls deviations on a finite grid, enabling data-based selection of λ before comparison with a fixed posterior and grid point.The resulting bound holds simultaneously for every grid point and posterior.Source: §8.7 · pp. 29–31

8.8 Proof of Corollary 5.1

• The 6u_n/n correction comprises 4u_n/n from the two crossing-cycle corrections and 2u_n/n from the grid expectation remainder.Source: §8.8 · p. 31
• The square-root term is of order d log n/n, truncation and grid corrections are of order d(log n)^3/n, and the renewal-age term is O(n^-1).For a fixed regenerative law, β(u_n) = o(n^-a) for every fixed a > 0.Source: §8.8 · p. 32

8.9 Proof of Proposition 6.1

• In the proof of Proposition 6.1, controlling the number and lengths of regeneration cycles yields an event where D_n ≥ n/2, on which each term of Theorem 3.1 is estimated.Source: §8.9 · p. 32
• The proposition’s estimates include corrections for the cycle extending beyond time n and losses removed by truncation.Source: §8.9 · p. 33

• The upper-bound event has probability at least 1 − δ and satisfies D_n ≥ n/2.Source: §8.10 · pp. 34, 36
• With deterministic cycle lengths and Bernoulli labels constant within each cycle, estimating long-run risk reduces to estimating p from k_n independent Bernoulli observations.The lower-bound argument turns a two-value testing problem into an estimation bound that applies to any estimator.Source: §8.10 · pp. 35–36
• The proof establishes the upper and lower inequalities in (6.3), yielding minimax bounds over P(m, C, ε).Source: §8.10 · pp. 34, 36

• The maximum cycle length and the unfinished-cycle age are both o(n^(1/p)), controlling the change from the full path to completed cycles.Source: §8.11 · p. 37
• The full-path sum admits a Brownian coupling, and removing the incomplete cycle preserves the approximation using the same Brownian motion.The cycle paths and lengths are i.i.d., and the cycle reward has mean zero.Source: §8.11 · p. 37
• The block variance estimator centers each block at empirical risk; the proof uses the Bernstein inequality to control the centering error before establishing its convergence rate.The variance-estimation error is divided by D_n ∼ n, and the extra error is negligible for 2 < p < 4.Source: §8.11 · pp. 37, 40
• The final approximation converges in D[0, 1] after Brownian scaling makes the comparison process standard Brownian motion in distribution for each n.Source: §8.11 · p. 41