How Patterns Dictate Learnability in Sequential Data

AI summary

Authors: Mario Morawski, Anaïs Després, Rémi Rehm · arXiv: 2510.10744v1 [stat.ML], 12 Oct 2025 · License: CC BY 4.0

(Note: the supplied paper text is truncated mid-sentence in Section 6, so the Conclusion is only partially available. Every figure below comes from the content that was provided.)

Overview

Research area: Statistical machine learning and information theory applied to sequential data — time series forecasting, autoregressive modeling, and the theory of learnability under temporal dependence.

Technical level: Advanced. The paper leans on information theory (mutual information, entropy rates, excess entropy), statistical learning theory (Rademacher complexity, stationary-process bounds), and Bayesian asymptotics (Fisher information, parameter-dimension estimation).

Scope in one sentence: The paper builds a framework around predictive information — the mutual information between a sequence's past and future — to define an information-theoretic lower bound on the risk any sequential predictor can achieve, and validates that bound on synthetic Gaussian, autoregressive, and Ising-spin data.

What This Paper Is About

Autoregressive models depend on there being exploitable temporal patterns in the data, but practitioners usually have no principled way to tell whether poor performance is caused by a weak model or by the data simply not containing enough structure to predict. This paper proposes an information-theoretic answer: measure the mutual information between the past and future of a sequence, use how that quantity grows with context length (the "universal learning curve") to read off the strength of the temporal patterns, and convert it into an estimated floor on the best achievable prediction risk. That floor can then be compared directly against an actual model's loss to judge whether the model is leaving predictive structure on the table.

Key Contributions

1. A theoretical link between temporal patterns and minimal achievable risk. The authors formalize the idea that the presence or absence of structure in sequential data fundamentally constrains what any predictor can do, connecting the universal learning curve to a lower bound on forecasting risk.

2. Information-theoretic bounds on that minimal risk. They derive bounds expressed through structural properties of the data — predictive information and pattern complexity — including a Markov-process result, a parametric log-growth law, and a Rademacher-complexity bound for stationary sequences.

3. A practical estimator of the intrinsic risk limit. Corollary 4.7 gives a model-dependent procedure for estimating the oracle risk from a collection of trained models of orders 1 through M, allowing quantitative comparison against a model's empirical risk.

4. Empirical validation on synthetic data. Experiments on Gaussian processes, vector autoregressive processes, and blockwise-random Ising spin sequences show the framework assessing model adequacy, quantifying a dataset's inherent complexity, and revealing interpretable structure. Code is available at https://github.com/EkMeasurable/Learnability_Ipred.

Main Findings

• Predictive information generalizes EvoRate. EvoRate (Zeng et al., 2025) is the mutual information between the past k observations and the next observation. The authors generalize it to I_pred(k, k'), the mutual information between X_{t-k+1}^{t} and X_{t+1}^{t+k'}. In the limit of growing windows this converges to a quantity known in the literature as excess entropy or the effective measure of complexity.

• Pattern presence imposes a hard floor on risk. Proposition 4.5 states that for any order k and any model Q in the hypothesis class, the optimal risk is bounded as R^∞(Q*) ≤ R^k(Q) − Λ(k). Even an optimal predictor cannot beat the intrinsic information limit — no finite-memory model reaches the optimum unless Λ(k) is negligible.

• The learning curve is the discrete derivative of predictive information. Proposition 4.1 (from Bialek and Tishby, 1999) shows I_pred(k+1, k') − I_pred(k, k') → Λ(k) as k' → ∞, where Λ(k) = ℓ(k) − ℓ0 is the difference between the order-k entropy rate and its asymptotic value — also called the entropy gain.

• Markov order is recoverable from the curve. For a Markov process of order m, Proposition 4.2 shows Λ(k) = 0 for all k ≥ m. For first-order Markov processes, I_pred(k, k') = EvoRate(1) for all k ≥ 1, so the curve identifies the true Markov order.

• Parametric processes follow a logarithmic law. Theorem 4.3 gives I_pred(k, k') = (p/2)·ln(k) + (1/2)·ln det(F) + O(1), where p is the parameter-space dimension and F the Fisher information matrix. Corollary 4.4 then gives Λ(k) ~ p/(2k), implying dim Θ ≈ 2k·Λ(k). This contrasts with EvoRate, whose asymptotic behavior the authors describe as unclear.

• A finite-sample bound with a measurable penalty. Proposition 4.6 gives, with probability at least 1 − δ, R^∞(Q*) ≤ R̂^k(Q) − Λ(k) + 2ℜ̂_n(F_k) + 3·ln(1/δ)/n, where ℜ̂_n(F_k) is the empirical Rademacher complexity of the derived loss class.

• Oracle risk can be estimated from a collection of trained models. Corollary 4.7: R̂^∞(Q*) = min_{1≤k≤M} { R̂^k(Q_k) − Λ(k) }, and the true optimal order k* is at most the argmin of that expression. If loss plateaus while Λ(k) stays positive, residual structure remains uncaptured.

• Gaussian predictive information has a closed form. For a d-dimensional Gaussian process with i.i.d. components, I_pred(k, k') = (d/2)·ln( |Σ1^(1)|·|Σ2^(1)| / |Σ^(1)| ), where the Σ terms are the covariances of the past block, the future block, and the joint sequence.

• Estimators are accurate in low dimension and degrade in high dimension. In the Gaussian experiment with k = 5 and k' = 10, all methods were reasonably accurate for dimensionality d ≤ 20. The I_pred-SMILE and I_pred-NWJ estimators consistently under-estimated in structured, high-dimensional regimes (Periodic and RQ kernels). The authors explicitly state that refining the estimator is out of scope for this work.

• Learning curves identify autoregressive order. On stationary vector autoregressive processes in R³ with orders p ∈ {5, 10}, the estimated curve Λ̂(k) closely tracked the theoretical curve computed from the known generating distribution and produced a sharp transition at the correct order k = p. A "critical zone" threshold of 0.02 was used to mark where the curve is effectively zero, since estimation never yields exact zeros.

• The oracle estimate quantifies the data-versus-model gap on Ising sequences. Using blockwise-random Ising data (sequence length 10,000,000), as block size M increased — making the process effectively a first-order Markov chain — EvoRate rose and losses fell.

  M	EvoRate(10)	R̂^∞_lstm(Q*)	R̂^∞_mlp(Q*)	min R̂^k_lstm(Q)	min R̂^k_mlp(Q)
  10,000	0.2758	0.3724	0.3719	0.4853	0.4872
  100,000	0.2861	0.3684	0.3720	0.4679	0.4668
  1,000,000	0.3269	0.3569	0.3390	0.3798	0.3660
  10,000,000	0.4760	0.0697	0.0867	0.0733	0.0903

  For M = 10,000, the ratio R̂^k(Q)/R̂^∞(Q*) ≈ 1.3 signals suboptimal prediction, likely due to high non-stationarity; the ratio approaches 1 as M grows.

• Parameter-dimension recovery is consistent. Estimated dim(Θ) (true value 1) gave p̂ = 2 × k × Λ̂(k) = 0.9580 at k = 10 for M = 10,000, with comparable values for other sample sizes. At M = 10,000,000, where the process becomes Markovian and departs from the parametric setting, the estimator approached zero (p̂ = 0.0720 at k = 10), as theory predicts.

• Optimal regression orders track complexity. Estimated k* values were 1/1 (LSTM/MLP) at M = 10,000 and 100,000; 18/16 at 1,000,000; and 10/9 at 10,000,000.

• Estimator instability is a known limitation. Negative Λ(k) estimates at M = 10,000,000 are attributed to instability in Λ̂(k) when k ≫ p for a true order-p Markov process; the authors state refinement is needed to avoid misinterpretation in low-complexity settings.

Methodology in Plain English

The framework rests on three quantities. First, predictive information: how many bits about the future are shared with the past. Second, the universal learning curve, Λ(k) = ℓ(k) − ℓ0, which measures how much each additional past observation reduces uncertainty about the next one — essentially the marginal value of more context. Third, the forecasting risk of a model, measured by expected negative log-likelihood.

The authors assume the process is stationary with finite entropy H(X_t) < ∞, but they deliberately do not require finite second moments, which permits heavy-tailed distributions. Working under this assumption, they derive how Λ(k) behaves for two structured families — Markov processes (where it vanishes past order m) and finite-dimensional parametric families (where it decays as p/2k) — and then connect Λ(k) to the minimal achievable risk via a bound. Since the true risk is unobservable, they substitute an empirical estimate and add a Rademacher-complexity correction derived for stationary sequences.

Practically, the recipe is: train models of several regression orders on the same data; use mutual-information estimators to estimate I_pred and hence Λ(k); then compute R̂^k(Q_k) − Λ(k) for each order. The minimum is the estimated oracle risk, and the argmin upper-bounds the optimal regression order. Comparing a model's own loss to the oracle estimate reveals whether the model or the data is the binding constraint. Because the estimate depends on the hypothesis class, it is model-dependent — but that same property makes it directly comparable to real model performance, unlike EvoRate or ForeCA, which the authors describe as focusing on intrinsic signal properties without a principled connection to model performance.

The experiments test the components separately: a Gaussian process checks the mutual-information estimator against the closed-form value, the autoregressive process checks whether Λ̂(k) finds the true order, and the Ising spin sequence checks whether the oracle risk estimate behaves sensibly as data complexity changes.

Why This Matters

Impact on research. A large body of sequential-data theory bounds the gap between empirical and true risk (Rademacher complexity, PAC-Bayes, Bayesian bounds). This paper targets a different question: what is the minimal achievable risk at all. The authors argue that empirical evidence — such as the plateau in model performance on the Exchange dataset from GluonTs despite recent innovations — suggests data limitations rather than model inadequacy may be the binding constraint. The framework also connects to work on learning under general stochastic processes, including Prospective Learning (Silva et al., 2025) and consistency results for non-i.i.d. settings, by offering an intrinsic, data-side notion of learnability rather than an external risk or regret measure. Unlike the Bayes error rate in classification, the paper states that no prior approach explicitly connects minimal achievable risk to the presence of patterns in sequential data.

Real-world applications (domains the paper identifies as sequential):

• Finance: the paper opens with financial time series as a driver of autoregressive model adoption and cites the Exchange benchmark plateau as motivating evidence.
• Healthcare: clinical time series are named among the inherently sequential data that machine learning systems ingest.
• Natural language processing: text streams are cited as a second major sequential domain.
• Model auditing and selection more broadly: the oracle estimator is presented as a target for distinguishing a model that has captured all available structure from one that has not.

Industry relevance. The framework gives teams a diagnostic for the question "should we keep scaling the model, or is the data simply not predictable?" Because dim Θ ≈ 2k·Λ(k) connects the decay rate of the learning curve to the effective number of degrees of freedom, it also offers a practical handle on estimating model complexity requirements, and the estimated optimal regression order k* can guide context-length selection. The authors also note that pre-trained models on benchmark datasets are widely available, and argue such models can be leveraged to estimate both the optimal regression order and the best achievable risk on the dataset they were trained on. A practical caveat: for MSE loss with a multivariate Gaussian predictive distribution, L_mle = L_mse + const, so the framework carries over to standard Gaussian regression settings.

Future Directions

• Improving the mutual-information estimator. The authors state directly that refining the estimation of I_pred lies beyond the scope of this work and would warrant a dedicated investigation. High-dimensional structured regimes (Periodic and RQ kernels) produced consistent underestimation with SMILE and NWJ, and negative Λ(k) estimates appeared for k ≫ p.

• Stabilizing the learning curve at long context. The instability of Λ̂(k) when k ≫ p for a true order-p Markov process needs to be resolved to avoid misinterpretation in low-complexity settings.

• Making the critical-zone threshold principled. The 0.02 cutoff used to declare Λ(k) effectively zero is acknowledged as somewhat arbitrary — chosen small relative to typical Λ(k) magnitudes but large enough to survive estimation noise. A more rigorous criterion is left open.

• Extending the theory beyond finite parametric models. The paper notes that when the generating process depends on an infinite or unbounded set of latent parameters, predictive information may vanish or grow sub-logarithmically, indicating either insufficient structure for reliable forecasting or a mismatch between model and data complexity — cases where structural assumptions or inductive biases may be needed to enable generalization.

Target Audience

Researchers working on time series analysis, autoregressive modeling, or the theory of learning under temporal dependence, particularly those familiar with information theory and statistical learning theory. It will also be useful to practitioners who need a principled way to diagnose whether forecasting performance is limited by their model or by the data — though those readers should be prepared for a substantial theoretical component, since the framework's core results are propositions, corollaries, and asymptotic expansions. Readers looking for applied benchmarks on real datasets should note that the validation here is entirely on synthetic data, and that the mutual-information estimation step brings its own variance, which the authors flag as unresolved.

Authors’ abstract

Sequential data - ranging from financial time series to natural language - has driven the growing adoption of autoregressive models. However, these algorithms rely on the presence of underlying patterns in the data, and their identification often depends heavily on human expertise. Misinterpreting these patterns can lead to model misspecification, resulting in increased generalization error and degraded performance. The recently proposed evolving pattern (EvoRate) metric addresses this by using the mutual information between the next data point and its past to guide regression order estimation and feature selection. Building on this idea, we introduce a general framework based on predictive information, defined as the mutual information between the past and the future, $I(X_{past}; X_{future})$. This quantity naturally defines an information-theoretic learning curve, which quantifies the amount of predictive information available as the observation window grows. Using this formalism, we show that the presence or absence of temporal patterns fundamentally constrains the learnability of sequential models: even an optimal predictor cannot outperform the intrinsic information limit imposed by the data. We validate our framework through experiments on synthetic data, demonstrating its ability to assess model adequacy, quantify the inherent complexity of a dataset, and reveal interpretable structure in sequential data.