Generalization bounds for models trained on time series all carry a hidden dial: how quickly the data forget their past. For a linear system whose next state is a fixed matrix times the current state plus noise, that dial is set by the spectral radius $\rho$, the largest eigenvalue magnitude of the matrix. As $\rho$ approaches 1, shocks linger for a long time and the effective number of independent samples shrinks. Recent PAC-Bayes bounds for dependent data, which are guarantees on the average error of a randomized predictor drawn from a learned "posterior" distribution, make this explicit through an effective sample size. They work only if someone supplies the forgetting rate in advance. In practice nobody knows it, and near instability it is hardest to estimate. This proposal asks a concrete question: what does it cost to estimate the forgetting rate from the same trajectory and still have a valid bound, and how does that cost change when the noise is heavy-tailed?
Our claim is that this cost has a sharp, measurable form. When the noise has light (sub-Gaussian) tails, certifying the stability margin $1-\rho$ from data should add only a logarithmic penalty, and only in the regime where the oracle bound is already vacuous. When the noise has only a few finite moments, the "no free lunch" price of PAC-Bayes, which is a polynomial rather than logarithmic dependence on the confidence level, is paid twice: once for the loss and once for the margin estimate. Margin certification then becomes the bottleneck. We would prove a fully empirical bound for continuous-state linear systems, prove a matching lower bound on the price of not knowing $\rho$, and test the predicted two-regime picture on synthetic systems swept toward $\rho=1$ and on real near-unit-root series.
What exists and where the gap is
Two literatures meet here without quite touching. On the dynamical-systems side, finite-sample analyses show that difficulty explodes at the stability boundary. Transition Matrix Estimation in High Dimensional Time Series shows that estimation stays hard near spectral norm one even when the matrix is low-dimensional. Finite Sample Deviation and Variance Bounds for First Order Autoregressive Processes shows that deviation probabilities rise sharply near the unit root. On the Approximation of Toeplitz Operators for Nonparametric H∞-norm Estimation gets sample complexity scaling as $1/(1-\rho)^2$. Finite-sample-based Spectral Radius Estimation and Stabilizability Test for Networked Control Systems gives finite-sample spectral radius estimates and a stabilizability test whose cost scales as the inverse square of the margin. These papers motivate the proposal: they establish that margin estimation is expensive. They also supply a method, since we reuse their least-squares spectral radius estimators and confidence bands. None of them bounds the generalization error of a learned predictor.
On the PAC-Bayes side, four papers come closest. Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds builds the effective sample size $\tilde n = n\gamma_{ps}$ into a Gibbs-posterior bound, where $\gamma_{ps}$ is the pseudo-spectral gap, a measure of how fast a Markov chain mixes. Its temperature must be tuned with a known lower bound on that gap. Empirical PAC-Bayes Bounds for Markov Chains removes the oracle by estimating the gap, but only for finite state spaces, and it uses light-tailed concentration. PAC-Bayes Generalisation Bounds for Dynamical Systems including Stable RNNs requires strict contraction and bounded or truncated noise, and does not track how its constants behave as the contraction factor approaches 1. Simpler PAC-Bayesian bounds for hostile data handles heavy-tailed autoregressive data. It replaces the KL divergence with power divergences and uses Hölder and Markov inequalities in place of exponential moments, but it assumes the mixing coefficients are given and pays $\delta^{-1/p}$ in the confidence level.
That polynomial dependence is not an accident. Still No Free Lunches: The Price to Pay for Tighter PAC-Bayes Bounds proves that no PAC-Bayes bound can be sub-Gaussian-tight, valid at every confidence level, and valid under finite variance all at once. This result constrains the proposal: we do not try to beat the trilemma. We ask how it composes with margin estimation.
The obvious idea at this intersection is to compute how the constants of an existing bound blow up as $\rho\to 1$. That calculation is largely mechanical once the mixing rate is written as roughly $\rho^\tau$, and it does not change what a practitioner can certify. Our proposal differs from all four PAC-Bayes papers in a specific way. The margin is unknown, it is estimated from the training trajectory, its uncertainty is charged inside the bound, and the state space is continuous. The headline result is a pair of matching upper and lower bounds on that charge, separately for light and heavy tails.
Core Claim
Take an autoregressive or linear-state-space predictor learned from one trajectory of length $N$. The oracle bounds above behave, up to constants and logarithms, like
$$R(\hat\rho) - R_N(\hat\rho) \lesssim \sqrt{\frac{\mathrm{KL}(\hat\rho\|\pi) + \log(1/\delta)}{N(1-\rho)}}.$$
Here $\hat\rho$ is the posterior over predictors, $\pi$ is a data-free prior, $R$ and $R_N$ are true and empirical risk, $\delta$ is the failure probability, and $N(1-\rho)$ plays the role of $n\gamma_{ps}$ in Alquier and Kengne. A fully empirical bound must replace $1-\rho$ with a high-confidence lower bound on the margin computed from the same data.
We build that bound in three steps. We place a prior on a geometric grid of candidate margins. We spend part of the confidence budget on a margin certificate obtained from least-squares spectral radius estimation, following Xu et al. We then apply a PAC-Bayes change of measure jointly over predictors and margins.
The conjecture has two parts. Under sub-Gaussian noise, the empirical bound is within a $\log\log$ and constant factor of the oracle whenever $N(1-\rho)$ exceeds a threshold. Below that threshold even the oracle bound is vacuous, so oracle-freeness is nearly free. Under noise with only $q$ finite moments, the margin certificate itself inherits a polynomial confidence cost. The empirical bound then scales as $\delta^{-1/p}$ compounded with the margin-certificate error. The lower bound we aim for says this compounding cannot be removed by any oracle-free bound that is valid uniformly over $\rho<1$.
Whether the relevant certificate cost scales as $1/(1-\rho)$ or $1/(1-\rho)^2$ is genuinely open. Relative-accuracy estimation of an AR(1) coefficient suggests the former. The $H_\infty$ and stabilizability results suggest the latter. Settling which one governs PAC-Bayes is part of the contribution.
Research Program
The theory has three pieces. The first is an upper bound for continuous-state linear autoregressions with Gaussian and with finite-moment innovations. For light tails it uses a Bernstein-type concentration in the style of Alquier and Kengne. For heavy tails it uses the Hölder–Markov power-divergence route of Alquier and Guedj, with the margin certificate entering through a union over the margin grid that is absorbed into the prior. The second is a two-point lower-bound construction: AR(1) processes with $\rho$ and $\rho'$ close to 1 that are hard to distinguish from $N$ samples. It shows that any bound valid over both must pay the certificate cost. The third is an extension of the upper bound from scalar AR(1) to vector autoregressions, where the relevant margin is that of the spectral radius rather than the spectral norm. This distinction matters because non-normal matrices can have $\|A\|_2>1$ with $\rho(A)<1$, which is exactly where the contraction assumption of Eringis et al. fails.
On the computational side, we sample from the optimal power-divergence aggregator, whose closed form Alquier and Guedj give but call intractable in high dimension. We use Langevin-type sampling for low-dimensional linear predictors and small recurrent networks. This keeps the empirical study honest about the bounds a practitioner could actually compute.
Baselines
The naive reference point is the trivial bound: the loss range, or for unbounded losses the risk of predicting zero. It is accompanied by a held-out-suffix test error treated as if the samples were independent. That estimate has no valid guarantee under dependence, and we expect it to under-cover near $\rho=1$. We report it only as a reference for tightness.
The strongest existing competitor is the oracle effective-sample-size bound of Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds, given the true pseudo-spectral gap of the simulated chain. For heavy-tailed noise, the corresponding competitor is the bound of Simpler PAC-Bayesian bounds for hostile data with true mixing coefficients. These are the bounds our method tries to match without the oracle, so they define the ceiling. All methods share the same trajectories, prior family, posterior sampler, sampler budget, and $\delta$. Temperature and divergence order are selected on the bound itself through a pre-registered grid paid for in the union bound.
On the stable-RNN benchmark of PAC-Bayes Generalisation Bounds for Dynamical Systems including Stable RNNs, the reported result is that the bound becomes non-vacuous at $N = 9$. We rerun their system as given and then sweep the contraction factor toward 1. Beating them means remaining non-vacuous at contraction factors where their constants make the bound vacuous. On the original system, a fully empirical bound should come within a small factor of $N=9$.
For the finite-state comparison with Empirical PAC-Bayes Bounds for Markov Chains, no reported numerical result was found on Lacuna; that paper reports qualitatively that the empirical bound is essentially as tight as the oracle one. We reimplement it on discretized AR(1) chains as a sanity check that our construction reduces to theirs.
The key ablation is the plug-in bound. It inserts the point estimate of $\rho$ into the oracle formula with no certificate charge, and it isolates whether charging for margin uncertainty is necessary. Beating it means equal or better coverage at a modest width cost. We expect it to be tighter but to under-cover as $\rho\to 1$. A second ablation swaps power divergences for KL under heavy tails, to show where the trilemma bites.
Why not just…?
Why not just plug in the estimated spectral radius? This is the ablation above, and it is the most tempting shortcut. The finite-sample results of Finite Sample Deviation and Variance Bounds for First Order Autoregressive Processes and Transition Matrix Estimation in High Dimensional Time Series indicate that the estimate is most unreliable exactly where it matters. Least-squares estimates near a unit root are biased toward stability, so plug-in should overstate the margin and the bound should under-cover. If our coverage experiments show plug-in covering at the nominal level for all $\rho$ we test, that is a real threat. We would then report that the certificate is unnecessary in practice and shift the contribution to the heavy-tailed lower bound.
Why not just assume a conservative worst-case margin? Fixing a prior upper bound $\rho_{\max}$ gives a valid bound with no estimation. It is tight only when the true $\rho$ is near $\rho_{\max}$. It also requires a number the user cannot check, which is exactly the oracle problem raised against Alquier and Kengne. Our sweep will show the width ratio between the worst-case bound and ours across $\rho$. If the ratio stays near 1 over realistic ranges, the adaptive bound is not worth its complexity, and we will say so.
Why not just use frequentist confidence regions for the least-squares estimator? The structured-VAR results of Estimating Structured Vector Autoregressive Models and Sampling Requirements for Stable Autoregressive Estimation give sharp rates, but only for a single point estimate and only under Gaussian or sub-Gaussian innovations. They say nothing about randomized predictors or recurrent networks, and they do not apply under Student-t noise. We include the least-squares prediction risk with its confidence band as a comparison on the light-tailed linear benchmarks, where it is a fair competitor. We drop it in the heavy-tailed and nonlinear settings, where it has no guarantee.
Why not just split the trajectory into blocks? Blocking with buffers, or median-of-means over blocks, converts dependence into near-independence. As the research file notes, near $\rho=1$ the buffers must exceed the mixing time, so few blocks survive. Median-of-means also cannot reach small $\delta$, by the structural limit Guedj and Pujol identify. We run a buffered-block bound with buffer length set from the same margin certificate and measure how many samples it needs to become non-vacuous.
Proposed Experiments
The central experiment uses synthetic AR(1) and sparse VAR systems of the kind studied by Melnyk and Banerjee. We use $\rho \in \{0.5, 0.9, 0.97, 0.99, 0.997, 0.999\}$, include both normal and non-normal transition matrices, and draw innovations that are Gaussian or Student-t with 2.5, 3, and 5 degrees of freedom. Trajectory lengths range from $10^2$ to $10^5$. We use the Eringis et al. stable-RNN system as the nonlinear case.
For each cell we record four quantities: the bound value, the true risk computed by long independent rollouts, coverage over 500 repeated trajectories at $\delta \in \{0.05, 0.01, 0.001\}$, and the smallest $N$ at which each bound becomes non-vacuous. The decisive check is the slope of $\log N_{\text{non-vacuous}}$ against $\log(1-\rho)$ for the empirical bound versus the oracle. Under light tails we predict equal slopes, which would show oracle-freeness is free. Under heavy tails we predict a steeper slope for the empirical bound that grows as $\delta$ shrinks. A slope near $-2$ rather than $-1$ would side with the $H_\infty$ and stabilizability literature on which margin power governs PAC-Bayes. Matching slopes under heavy tails would falsify the compounding conjecture.
For real data we use the WTI crude oil spot price and freeway traffic speed series from Kazemipour et al. and the NASA DASHlink landing telemetry from Melnyk and Banerjee. For these, no reported quantitative results were found on Lacuna. Crude oil prices are a natural near-unit-root test case, and traffic speeds have strong daily and weekly cycles, so spectral radii sit close to 1. Since true risk is unavailable, we evaluate coverage against a long held-out future segment and report bound width. The question is whether the fully empirical bound is ever non-vacuous on these series, and whether its estimated margin agrees with the cycle structure the earlier papers recovered.
References
- Transition Matrix Estimation in High Dimensional Time Series
- Finite Sample Deviation and Variance Bounds for First Order Autoregressive Processes
- On the Approximation of Toeplitz Operators for Nonparametric H∞-norm Estimation
- Finite-sample-based Spectral Radius Estimation and Stabilizability Test for Networked Control Systems
- Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds
- Empirical PAC-Bayes Bounds for Markov Chains
- PAC-Bayes Generalisation Bounds for Dynamical Systems including Stable RNNs
- Simpler PAC-Bayesian bounds for hostile data
- Still No Free Lunches: The Price to Pay for Tighter PAC-Bayes Bounds
- Estimating Structured Vector Autoregressive Models
- Sampling Requirements for Stable Autoregressive Estimation