PaperlayerView exact revision on arXiv

Source-linked AI summary

Empirical concentration for chains with infinite memory

Pierre Alquier, Paul Doukhan

arXiv:2610.32265v1stat.MLcs.LG

TL;DR

Concentration bounds for dependent time series often rely on unknown dependence quantities, limiting their direct use as empirical confidence bounds. This paper derives a dependence-sensitive inequality for stationary infinite-memory chains and estimates its dependence margin from data; the resulting confidence radius is asymptotically close to the oracle radius.

  • Problem

    Dependent-data concentration inequalities can involve unknown dependence quantities, preventing their direct evaluation as confidence bounds or model-selection criteria.

    Source: §1 · p. 1

  • Method

    The paper establishes a McDiarmid-type inequality under a summable Wasserstein contraction condition and estimates the dependence margin for finite and continuous state spaces.

    Source: §1 · p. 2

  • Results

    1 + κ times the oracle radius asymptotically, when the estimated margin is substituted using a fixed κ > 0 safety factor.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results provide a proof of concept that empirical concentration bounds are possible for a large class of time series, with confidence intervals asymptotically in 1/√n.

    Source: §6 · p. 11

    The empirical inequality is only eventually valid: before an unknown threshold N(P, κ, q), the theorem does not certify a finite radius.

    Source: §3 · p. 5

Abstract

from arXiv · show

Concentration inequalities for time series usually involve unknown quantities measuring dependence. This prevents their direct use as confidence bounds, or as criteria for learning algorithms. Recent works proved empirical concentration inequalities for stationary Markov chains, where the unknown quantities are estimated. We extend this approach beyond the Markov case, by considering stationary chains with infinite memory. We first establish a bounded-differences inequality on bounded Polish metric spaces under a summable Wasserstein contraction condition. We then estimate its dependence coefficients from a single trajectory, using either transition counts when the state space is finite, or derivatives of kernel conditional-density estimates for a continuous state space. We give general error bounds and illustrate their dependence on the memory tail. Finally, a fixed multiplicative safety factor turns these estimators into empirical concentration bounds. While some regularity assumptions are required to make the bounds empirical, our procedure remains fully adaptive in the sense that it does not require the knowledge of the constants involved in these assumptions. The empirical confidence bounds derived from our results are asymptotically as tight as the theoretical ones.

1 Introduction

The paper extends empirical concentration bounds from Markov chains to stationary processes whose next observation may depend on the entire past. It develops a dependence-sensitive concentration inequality and estimates its dependence margin from data.

1 Introduction

  • Dependent-data concentration bounds often require unknown dependence quantities, so they cannot be directly evaluated on a sample for confidence bounds or model-selection criteria.The introduction also identifies generalization bounds and UCB algorithms as applications of concentration inequalities.Source: §1 · p. 1
  • Prior empirical concentration work estimates dependence quantities for Markov chains, while this paper targets processes with dependence on the entire past.The paper cites pseudo-spectral-gap estimation for finite state spaces and compact continuous state spaces, and related empirical bounds for learning and bandit applications.Source: §1 · p. 2
  • The paper extends empirical concentration to infinite-memory processes using a McDiarmid-type inequality with dependence penalty 1/∆(P).The approach assumes lag-wise effects are bounded by coefficients δ_j(P) and estimates the margin for finite and compact continuous state spaces.Source: §1 · p. 2
  • A fixed κ > 0 safety factor yields an eventually valid lower confidence bound on ∆(P), making the substituted concentration radius asymptotically 1 + κ times the oracle radius.The procedure does not require unknown constants in its definition, although the sample size at which the guarantee becomes valid may be unknown.Source: §1 · p. 2

1.1 Related works

  • The related-work discussion distinguishes this approach by using a kernel-level Wasserstein condition and explicitly treating the stationary remote past.Its concentration theorem has an explicit dependence penalty that the paper subsequently estimates; the cited alternative regeneration approach does not estimate a dependence coefficient but leaves second-order terms nonempirical.Source: §1.1 · p. 3
  • Here, “empirical” means the bound requires no numerical knowledge of the process beyond the known state space and the statistic’s regularity.For continuous observations, the estimator differentiates a kernel estimate of a conditional density.Source: §1.1 · p. 3

2 Setting and notation

The setting observes a segment of a stationary process on a Polish metric space with a bounded state space. A Wasserstein contraction condition controls how changes in the past affect the next-observation kernel.

2 Setting and notation

  • The data are a segment of a stationary process taking values in a Polish metric space, with the past indexed by negative times.The process is described through a measurable probability kernel conditional on the past.Source: §2 · p. 3
  • The state space is assumed bounded, and the Wasserstein contraction assumption bounds the effect of changing past observations through coefficients δ_j(P).These assumptions suffice for the deviation inequality; estimating ∆(P) requires additional regularity and positivity conditions that differ by state-space type.Source: §2 · pp. 3–4
  • The concentration theorem holds for any admissible coefficient sequence, but estimation targets differ by setting: minimal total-variation oscillations in the discrete case and density-Lipschitz coefficients converted to Wasserstein distance in the continuous case.The notation also defines clipping to [0,1] and interprets upper-bound fractions with zero denominator as +∞.Source: §2 · p. 4

3 Concentration inequality and objective

The paper establishes a bounded-differences concentration inequality for dependent observations, then addresses its unknown dependence margin by using an observable lower bound. The resulting empirical radius is eventually valid and asymptotically approaches the theoretical radius up to a fixed safety factor.

3 Concentration inequality and objective

  • Under Assumptions 2.1 and 2.2, Theorem 3.1 bounds deviations of separately Lipschitz functions using their coordinatewise constants and a dependence penalty.On a discrete alphabet, the dependence penalty recovers the oscillation-based result of Chazottes et al. (2023).Source: §3 · p. 4
  • For bounded losses in [0, 1], the theorem applies to empirical risk with coordinate constants c_j = 1/n.The paper uses this learning example to motivate replacing the unknown dependence margin in the bound with an observable lower bound.Source: §3 · pp. 4–5
  • The empirical radius uses an observable estimate of the margin, with an infinite radius when that estimate is zero.The stated guarantee holds eventually, after a process-dependent threshold; it is not uniform over processes at every sample size.Source: §3 · p. 5
  • When the estimated margin converges almost surely to the true margin, the empirical-to-theoretical radius ratio converges almost surely to 1 + κ.The paper notes that this asymptotic tightness is sufficient for regret bounds in UCB methods or classification generalization bounds in prior work.Source: §3 · p. 5

4 The discrete case

The discrete case estimates dependence from transition counts on a finite alphabet. Under positivity and memory-tail conditions, the estimate is consistent and yields empirical concentration without requiring the unknown regularity constants.

4.1 Assumptions and examples

  • Continuity and summable coordinate influences support the discrete contraction setup, with examples including uniformly ergodic Markov chains and chains with finite, geometric, or polynomial memory tails.For higher-order Markov chains, positivity alone need not make the sum of the first q influences less than one.Source: §4.1 · p. 6
  • A positive lower bound on transition probabilities makes finite words observable and the transition kernel and its oscillation coefficients identifiable.The lower bound π* is unknown and appears in the analysis, not in the estimator.Source: §4.1 · p. 6

4.2 Estimator and a general error bound

  • The estimator replaces transition probabilities with empirical context counts, but it is defined only for contexts observed at least once.When a context count is zero, no guarantee on estimating the dependence margin is available.Source: §4.2 · pp. 6–7
  • Its error has a variance component from context sampling and a bias component from truncating the infinite past to K lags and summing estimated influences.The choice of K is calibrated in the next subsection.Source: §4.2 · p. 7

4.3 Consistency, rates, and empirical concentration

  • If K tends to infinity while K T_K tends to zero, the estimated margin converges almost surely and meets the condition for empirical concentration.The estimator does not require π* or a bound on the memory tail; for δ_j(P) ≤ Cj^-r, any r > 2 suffices without knowing C or r.Source: §4.3 · p. 7
  • The parameter-free choices yield nearly n^-1/2 rates for super-exponential memory tails with γ > 2, beyond a process-dependent threshold.The paper does not claim these parameter-free rates are optimal.Source: §4.3 · pp. 7–8

5 The continuous case

The continuous-state method estimates dependence through conditional-density derivatives under positivity, smoothness, and contraction conditions. Its kernel-based estimates yield parameter-free empirical concentration bounds, with error behavior that depends on the memory tail.

5.1 Assumptions and examples

  • The coefficients L_j bound how conditional-density derivatives depend on past coordinates and provide usable upper bounds δ_j(P)=L_j/π for the dependence coefficients.The procedure estimates L_j rather than requiring the tightest possible δ_j(P).Source: §5.1 · p. 8
  • Examples include Gaussian location, nonlinear-mean, heteroscedastic, and context-dependent mixture kernels, with summable coefficient tails ensuring the stated conditions.For the mixture example, the density is uniformly positive without knowing the minimum of either component density.Source: §5.1 · p. 9

5.2 Estimator

  • The continuous estimator uses kernel estimates of conditional densities and their derivatives, with deterministic trimming and optimization restricted to an interior cube.The trimming level n^-1 avoids using the unknown density lower bound; the resulting statistics are explicit finite-dimensional optimizations.Source: §5.2 · p. 10

5.3 General bound and parameter-free choices

  • Theorem 5.2 gives a general error bound, while the continuous-case empirical inequality can be formed without numerical knowledge of α, H, L, or a memory-tail constant.The bound separates smoothing bias from statistical error; for fixed K, balancing them gives rate (log n/n)^(1/(2d(K+1)+6)), which the authors do not claim is optimal.Source: §5.3 · pp. 10–11
  • For any fixed q>0, the smoothing and statistical error at η=n^-q is eventually bounded by exp{-c_d(log n)^(2/3)}; the displayed examples specialize the bound when Ω_K≤C T_LK.The bound’s quantitative behavior therefore depends on control of the memory-tail quantity.Source: §5.3 · p. 11

6 Conclusion

The paper extends empirical concentration bounds from Markov chains to chains with infinite memory. The resulting confidence intervals are asymptotically of order 1/√n, while the authors identify the unbounded-state case as an unresolved boundary for their approach.

6 Conclusion

  • The approach extends empirical concentration bounds to chains with infinite memory, and the resulting confidence intervals remain asymptotically in 1/√n.The authors describe this as a proof of concept for a large class of time series.Source: §6 · p. 11
  • The method is limited to the bounded setting: uniform conditional-density estimation fails for unbounded observations, and sub-Gaussian norms would also need estimation without general convergence rates.The authors say the unbounded case may require a different approach.Source: §6 · p. 11

7 Proofs

The proofs establish concentration and empirical estimation guarantees for discrete and continuous dependence-coefficient estimators, using coupling and martingale arguments and controls on estimator error. They also prove convergence results under stated depth, memory-tail, and tuning-parameter conditions.

7.1 Proofs of Section 3

  • Successive optimal Wasserstein couplings control the effect of changing observations and initial pasts, enabling a martingale-difference and Hoeffding argument for bounded-differences concentration.The proof also derives an empirical bound and shows that ∆/∆n converges almost surely to 1 + κ.Source: §7.1 · pp. 12–13

7.2 Proofs of Section 4 (the discrete case)

  • For the discrete case, the proof bounds dependence-coefficient estimation error using context transition counts, then obtains almost-sure convergence when KnTKn tends to zero.The stochastic error term tends to zero under the stated growth conditions on Kn, while the deterministic bias vanishes by KnTKn → 0.Source: §7.2 · pp. 16–17

7.3 Proofs of Section 5 (the continuous case)

  • A Neumann–Poincaré inequality on the unit cube, combined with Kantorovich–Rubinstein duality, supplies a Wasserstein bound used in the continuous-case proof.The inequality constant is 1/π for [0, 1]^d.Source: §7.3 · p. 17
  • For the continuous case, the proof uses density regularity and kernel-estimator sensitivity bounds to establish concentration uniformly over estimators and evaluation points.Changing one observation affects at most K + 1 summands in the empirical average; the proof then discretizes the evaluation domain to apply a finite union bound.Source: §7.3 · pp. 18, 20, 21
  • The proof bounds first and second scalar derivatives of f_K and g_K, then combines statistical and boundary errors to control the gradient estimator over the full cube.The statistical error is controlled on the interior cube; the boundary contribution is handled by comparing each point with its nearest point in that cube.Source: §7.3 · pp. 23, 25, 26
  • Theorem 5.2’s continuous-case probability guarantee follows by combining Lemma 7.6 with Lemma 7.4 when e_n,K,h(P, η) < 1.For e_n,K,h(P, η) ≥ 1, the proof says the assertion is trivial because ΔL(P) and its estimator lie in [0, 1].Source: §7.3 · pp. 23, 26
  • With K_n = ⌊(log(n + e))^(1/3)⌋ and h_n = exp{−log(n + e)/[4(D_n + 3)]}, the failure sum is eventually at most exp{−c_d(log n)^(2/3)}, where c_d = 1/[32(d + 3)].Taking η = n^−(q+2), the proof uses K_T L_K → 0 to obtain B_K → 0; a summable failure level and Borel–Cantelli yield almost-sure convergence.Source: §7.3 · p. 27
Loading 2610.32265v1…