How Patterns Dictate Learnability in Sequential Data
Authors: Mario Morawski
Anaïs Després
Remi Rehm
Venue: NeurIPS 2025 poster ()
Keywords: Time Series
Sequential Data
Autoregressive Models
Mutual Information
Generalization Error
Primary area: theory

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 $\texttt{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—the mutual information between the past and the future, $\mathbf{I}(X_{\text{past}}; X_{\text{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.

How Patterns Dictate Learnability in Sequential Data
Mario Morawski
Anais Després'
Rémi Rehm
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 underlying patterns in the data, and their identification often depends heavily on human expertise. Misinterpreting these patterns 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 guide regression order estimation and feature selection. Building on this idea, we introduce general framework based on predictive information the mutual information between the past and the future, [_Xpasti X This quantity naturally defines an infornation-theorrtie learning curve, which quantifies the amount of predictive information available 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 sequential data.
Introduction
From time series in finance and healthcare 3 45 34 to text streams in natural language processing 38]. much the real-world data ingested by machine learning systems inherently sequential. Autoregressive models are commonly trained to predict such data, with their performance relying heavily on capturing evolving patterns. However, identifying these patterns still depends largely on human expertise [55]. Misinterpretation
result in models that overfit to training data, leading to poor calibration, generalization errors, and heightened vulnerability to adversarial examples 22]; for instance, classifiers memorize random label assignments in the training set [56]. A substantial body of work is devoted to bounding generalization error, primarily through Bayesian theory 22. For sequential data, these bounds have been formulated using Rademacher complexity 36). leveraging concentration inequalities and Bayyesian-isspiee
methods. We identify a critical open question the study of sequential data: (i) What is the minimal achievable risk for predictor attempting to model sequential data? This question differs subtly but importantly from bounding the gap between empirical and true risk. Empirical evidence, such as the plateau in model performance on the Exchange dataset from GluonTs I despite recent innovations [46), suggests that data limitations-ratan than model inadequacy- -ma be the binding constraint. This leads to a critical second question: (ii) Can we distinguish whether poor performance stems from the model's limitations or from the inherent unpredictability of the data? This distinction hinges on the nature and strength of temporal patterns: fewer patterns imply that even an optimal predictor will perform poorly, while richer structure offers more room for effective forecasting. Thus, good
Equal Contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

prediction requires both (1) that the data contain exploitable patterns, and (2) that the model can identify and leverage them. To illustrate this, consider the following stylized scenarios in which colleague attempts to predict what meal researcher will bring to lunch each day:
Meals are sampled uniformly at random from a cookbook.
Meals are chosen weekly based on preferences, weather, and prior meals.
Meals follow fixed rotation established years ago.
In the first case, even the optimal predictor cannot outperform random guessing due to the absence of structure. contrast, the second and third cases involve latent patterns-periodien
preference dependencies, contextual triggers that that a well-designed model could exploit. Crucially, identifying whether such structure exists-ane how much of it is learnable- iss a prerequisite for developing effective models. Concurrently, recent work has pointed out the lack of effective metrics for quanti- fying evolving patterns in sequential data, proposing the evolving rate (EvoRate) metric as a preliminary solution [55]. Building on this idea, we generalize the notion of EvoRate through the concept of predictive information- the mutual information between the past and the future 7 [4]. This leads the formulation of the universal learning curve (7], which measures the rate which predictive information increases with observation length. This curve serves as fundamental tool to quantify the minimal achievable risk. Our framework thus provides an inffrmationn-hhoreee perspective that addresses both questions (i) and (ii), while also offering insights into the nature and strength of the patterns embedded in the data. Our main contributions are:
Establishing theoretical link between the presence of temporal patterns in sequential data and the minimal achievable prediction risk.
Deriving -theoretiontthhoretti bounds on this minimal risk, expressed in terms of structural properties of the data such as predictive information and pattern complexity.
Proposing practical estimator of the intrinsic risk limit, enabling quantitative comparison with model performance assess whether learning is limited by data or by the model.
Validating the framework synthetic data, showing how it supports model selection and reveals when further improvements are constrained by the data itself. The codes are available GitHub: /ttps::/ggiian com www..//e//eeeuaaeeeeeeeeeeeeeeee wtw.:rrrrbb..eaaaaaaa.a......... Ipred
2
Related work
Patterns Estimation for Sequential Data Early work on measuring predictability in time series includes ForeCA [23], which introduced the concept of forecastability, based on the entropy of the spectral density. This metric quantifies how predictable a time series is from frequency-domat perspective. More recently, EvoRate (55) proposed a mutual information-basee approach to capture evolving patterns in sequential data, and demonstrated its for guiding regression order and feature selection. While promising, both ForeCA and EvoRate focus primarily on intrinsic signal properties and lack principled connection to model performance. In particular, EvoRate emphasizes temporal changes in its value rather than its absolute magnitude, which remains under-exploited. Moreover, these methods do not assess whether predictive model has effectively captured the patterns present in the data. In contrast, we introduce an cntommtiion-theoree estimator of the minimal achievable risk dataset, which serves two key purposes: (i) indicating the presence and strength of temporal patterns-lowed risk suggests stronger patterns-and (ii) enabling direct comparison with a model's empirical risk.
Learning under General Stochastic Processes. Recent advances in statistical learning theory have increasingly focused on relaxing the classical assumption of independent and identically distributed (i..d.) data. In particular, extending learning frameworks to handle stochastic processes with temporal dependencies or evolving distributions has become a central research direction. The Prospective Learning framework (49 formalizes this setting by requiring a learner to produce a sequence hypotheses that achieve low risk on future observations, given the data observed up to the present-an approach particularly relevant in non-stationary or dynamic environments where the optimal predictor may change over time. Complementary efforts have characterized learnability
under general stochastic processes [18] 25 providing general conditions for when consistent learning

---

is possible, often framed in terms of regret minimization or universal consistency. These perspectives share the common goal of determining whether, and under what conditions, learning remains feasible in complex non-i.i.d. settings. Our work complements these approaches by introducing an intrinsic, cnrrmation-thhoreee notion of learnability. Rather than relying solely on external performance measures such as risk or regret, we quantify learnability through the predictive structure of the data captured by predictive information and the universal learning curve. This allows us to bridge theoretical learnability guarantees with the structural properties of the data-generating process, offering a complementary perspective on when and why generalization is possible in sequential environments.
Mutual Information Estimation (MT) Traditional methods, such as the k-nearest neighbor es- timator (30), perform well in low-dimensional settings but struggle when applied to long or high- dimensional time series. MINE [6] addresses these challenges by leveraging the Donsker-Varadhan representation and deep neural networks to learn flexible estimators of mutual information. However, MINE cxhibits high variance and instability, particularly in sequential data settings. Alternative approaches, such InfoNCE [40], originally developed for contrastive predictive coding (CPC), are better suited to time series tasks; they learn representations that maximize mutual information between past and future segments. Further advancements include CLUB [I], which provides tractable upper bound on mutual information, and SMILE [1 which improves estimator stability through Sansen-Shannon-basse objectives.
Predictive Information and Learning Curve. Originally introduced by 7 8, predictive infor- mation can be viewed generalization of EvoRate. The core idea is measure the mutual information between a context, X Xpss, and a target, X Xfutur- It has been applied in machine learning to learn meaningful data representations (33), and several methods for estimating it have been proposed [22]. Building on this line of work. (7] and [15] also introduced the notion of the universal learning curve, which describes how predictive information grows with the length of the observed context. This curve captures the fundamental limits of learnability by quantifying how much additional in- formation about the future can be extracted from longer histories. In this paper, we extend these theoretical ideas by establishing novel link between the universal learning curve and the minimal achievable risk. Specifically, we show that the learning curve can be used to derive an empirical estimator of the optimal prediction performance attainable by any model. This connection provides an operational interpretation of predictive information as a diagnostic tool to distinguish between model limitations and the intrinsic unpredictability of the data.
Lowest Possible Error Rate In classification tasks, the Bayes error rate represents the lowest achievable error rate for any classifier T0, (4). This concept was developed alongside the PAC- In the context of sequential
Bayes framework, which provides upper bounds on the risk 47 32 data, prior work has focused primarily on bounding the gap between empirical and true risk, notably through Rademacher complexity (37 36 31. However, to the best our knowledge, none of these approaches explicitly connects the minimal achievable risk to the presence of patterns in sequential data.
3 Preliminary
3.1 Notations and hypothesis
We consider a stochastic process X = (XulT= E TT innexxdd over [t, T). with t E [].
We assume:
(Ho)=
The process is stationary and H(X)) < <0,
where (-)) denotes entropy. We do not require IE(x}) co, allowing for heavy-tailed distributions, and typically set X' = Rdd
Given a predictor g : x X and loss function é: X x X R, we define the forecasting risk of order as:
(h) (g) = Exi+1 -+1 [((Xe11. g(X x+1)) x --l.
(1)
3

---

3.2 Entropy and Entropy Rate
Understanding the nature of sequential data is closely linked studying the memory properties of the underlying process. For stationary process X fundamental quantity for measuring the information content is its entropy [48]. defined as
(X, ( (np()))
H(x²)=
(2)
where S denotes the support of the distribution. Under Assumption (Ho). the joint density p(a...... .TT (rr) is invariant under time translation. so the entropy depends only on the length of
the block [t, T]. The entropy is concave and subadditive with respect to the block size, and satisfies (0) 0. Let l(k) (X, x
-(x,,. k:1) In P(X; xx be the entropy rate of order 13. It measures how well X, can be predicted by observing & past values. Naturally, the more past observations are available, the lower the uncertainty, the mapping k - [(k) is non-increasing and non-negative. Under Assumption (Ho). ((k) converges to a constant lo as k - oc, and the fundamental theorem of entropy [48] states that
[1(( lo:
k+000
that is H(k) klo when k is large.
3.3 Iped as a generalization of EvoRate
In Zeng et al. (55), EvoRate is proposed as a measure for capturing predictive patterns in sequential data. It is defined as the mutual information between the past & observations, - and the next observation, Xe+1, that note IX X(+1). fundamental quantity.
We naturally extend EvoRate by introducing
p p(X
I Ipred (ki, k') I(X 141i x x
p0 p(X p(X
dX.
P(X; k+ )o
Predictive information, denoted Ipedd quantifies how much information from the past can be used to predict the future. Under assumption (Ho), it converges in the limit as both context lengths grow:
lim Iprea (k: k') Ipred past; Xfuture):
the effective measure of complexity [24]. Our focus remains on finite l and values to ensure practical relevance. Under (Ho) and suitable regularity conditions, predictive information corresponds to the sub-extensive component of the entropy.
quantity also known in the literature excess entropy [66]
14 21
The asymptotic behavior of predictive information provides principled lens through which to assess the complexity and predictability of stochastic processes [5]. In machine learning, recent works have leveraged this quantity to improve learned representations 33 22], taking advantage of its ability to capture shared temporal structure across sequences.
Theoretical analysis of Ipred
Consider the set Fú = { (X), X2+1) - In (X..1 X; Q E Hd }. which defines a class of real-valued functions on X. This class encompasses all possible loss functions that can be derived from making predictions using model Q E Hr = (Qo 0 E {}. where Hs represents a family of models of order k parameterized by 0-the vector of model parameters that governs the behavior and structure of the prediction model.
4.1 From a learning perspective
The th order forecasting risk R²x defined as
ck
-BEp(Xit x X and In Q(X+++ ((
(6)

---

has been widely used to assess autoregressive model performance 44 [5]] In similar spirit, we draw connection between the predictive information nead and central concept information theory: the universal learning curve ((k) = {(k) to 7 15 also known as the entmpy gain. This quantity measures the reduction in uncertainty about the future obtained by conditioning on past observations, and thus captures the presence of temporal patterns in sequential data. A key theoretical connection between the predictive information and the learning curve established by the following result from Bialek and Tishby 77:
Proposition 4.1 (Bialek and Tishby (1999) (7.. Under hypothesis (Ho), we have:
[kred + 1,K) Ipred (k, k.) A(k) as k' 00.
Proof in Appendix A.6
The notion of learning curve is central our analysis. In EvoRate [55], the authors primarily focused on how the metric evolves with the size of the past window, as its absolute values were difficult to interpret. it can be seen as a discrete derivative of the predictive information [7]. capturing the marginal contribution of each additional past observation. This perspective not only enhances interpretability but also plays key role in our theoretical developments and empirical evaluations.
contrast, the universal learning curve offers more principled alternative:
4.2 Interpreting the Asymptotic Behavior of A(k)
The asymptotic behavior of A(k) offers insight into the nature of the temporal patterns present in the data. helps characterize the structure the underlying distribution and supports the theoretical link between AAk) and the presence of predictive patterns. We now present examples that illustrate the relevance of this perspective.
The special case of Markov processes. When X is generated by Markov process of order m. dependencies are limited to the past m observations. This structure naturally reflected in the predictive information Iredd Previous approaches have addressed Markov order estimation using conditional mutual information 42]. with EvoRate showing promising empirical results (55), though without formal guarantees. Classical criteria like AIC [29] and BIC [17] also remain standard tools.
Building on Crutchfield and Feldman [15], we derive a closed-form expression for Iped under the Markov assumption and show that the universal learming curve A(k) vanishes for all & 2 m, providing a theoretical link between pattern complexity and memory length.
Proposition 4.2 (Predictive information in Markov processes). Let XX be a Markov process of order m. If k 2 t 2 m, then:
P(X(T X(-mta)
(i) Ipri (ki, k') x In
P(X
(ii) VkΣ m, A()=
In particular, for first-order Markov processes, we recover that (pre(k,, k') EvoRate(L) for all k Z allowing A(k) identify the true Markov order.
Proof in Appendices A.7 and A.8
(0). with unknown parameter 0 drawn from prior P(0) and dim θ p. Classical results in the i.i.d. case 722 show that predictive information grows logarithmically with We extend this to dependent settings under mild regularity conditions.
Parametric Processes. Let the process X be generated by a parametric family Qx; x+1
Theorem 4.3 (Predictive information in parametric models). Assuming standard hypotheses on stationarity, weak dependence, and regularity of the parametric 4 2 and 3. let the past and future windows grow with le 00 and k' 2 (the ratio ke /lc may vary). Then
ppra(kk, k0 2
2 In(k) + Indel(F) O(1),
where F is the Fisher information (
matrix
associated with the divergence
D ( k11 Proof in Appendix A.9
[0) 4+1 (0)).
5

---

This result provides an interpretable asymptotic expansion: the first term captures the uncertainty due to parameter estimation, while the second reflects model confidence via the concentration of likelihood around 0. In contrast to EvoRate, whose asymptotic behavior remains unclear, pred exhibits a principled structure grounded in classical learning theory.
Corollary 4.4 (Universal Learning Curve Decay). Under the same assumptions, the universal learning curve satisfies:
A(k)
2k
In particular, the dimensionality of the parameter space can be estimated as dim θ 2k A(k). Proof in Appendix A.9
This relation reveals precise connection between the decay of the universal learning curve A(k) and the intrinsic dimensionality of the parameter space O The behavior is consistent with classical Bayesian learning theory in the i..dd case, now extended to structured and dependent sequences. This correspondence indicates that predictive information faithfully reflects the effective degrees of freedom of the generative process.
Beyond Finite Parametric Models. When the data-generating process depends on an infinite or un- bounded set of latent parameters 47. predictive information may vanish grow sub-logarithmically, indicating insufficient structure for reliable forecasting or mismatch between model and data com- plexity. In such cases, structural assumptions or inductive biases may be necessary enable generalization and avoid overfitting.
4.3 Link Between Learning Curve and Minimal Achievable Risk
We now show how the universal learning curve A(k) provides upper bound on how close model of order can get to the optimal regression risk.
Proposition 4.5. For any l E N and any Q E Hy.
R²0)) S (²) A(k).
where Rx (Q") is the minimal risk achievable by the optimal predictor Q = P(Xe+1 Xpan). Proof in Appendix A.17
In practice, the optimal achievable risk is given by R (Q") limg- H(x++1 X/-+1)) This notion parallels the Bayesian risk in classification tasks [50], where the focus lies the gap between
the current and optimal losses, particularly in online learning contexts 26 27 35
Here, we aim to estimate (Q") directly. The previous proposition shows that model with finite memory can attain the optimal risk unless A(k) is negligible. The term ((k) quantifies the irreducible uncertainty due to limited context and serves as data-dependent upper bound on the possible reduction in risk achievable by optimizing over H4-
Since the true risk R* (+) is not directly observable, we use its empirical estimate,
(Q) = Σ In Q (Xi,411 X
To control the deviation between the true and estimated risks, we leverage Rademacher complexity for stationary sequences (36), together with standard concentration inequalities.
Proposition 4.6. Assume (Xt)tzz is stationary process satisfying the conditions of [36]. Then, for any E (0, 1), with probability at least 1 å over r--ample drawn from the process, every Q E H satisfies
S =** A(K) + 2R. (Fx) + +
In(1/8)
R
where
RR.FF = E, sup 1 Σ oi (x X(sta) JEFe i=1
is the empiricul Rademacher complexity of the class Fx computed on the sample, with . i...d. Rademacher variables.
Proof in Appendix A.1l

---

This proposition provides a formal bound on the best achievable risk. For simplicity, we assume RAt (Q) R. R*(() throughout the rest of the paper to reduce notational complexity. Pre-trained models on various benchmark datasets are widely available the literature. We argue that such models can be leveraged estimate both the optimal regression order and the best achievable risk on the dataset they were trained on.
Corollary 4.7. Suppose we have access to trained model Qk E Hy for each regression order k I..... M. Then:
(1) (²))))) min ( (Qx) - A(k)).
ISkS
(ii) h' S arg min (Qx) ((k))-
ISKSM
(i) provides way to estimate the minimal achievable risk. (ii) allows one infer the optimal regression order from this same model collection. Proof Appendix 1.
model performance plateaus beyond a certain context length k-that is, the loss ceases to improve while (Ak) remains strictly positive-ther the oracle reveals lower achievable loss than what the model currently attains. This discrepancy indicates the presence of residual predictive structure that the model fails to capture, thereby offering principled target for improvement. Oracle-based analysis thus provides framework for assessing whether a model fully exploits the predictive information present in the data. Unlike EvoRate [55] or the forccastability measure [2]]. estimator is model- dependent, as relies on the hypothesis class H4. While this introduces sensitivity to the model architecture, it also enables direct comparisons between the estimated oracle risk and the empirical performance of candidate models, offering a more actionable diagnostic.
Finally, under Mean Squared Error (MSE) loss and assuming the predictive distribution is multivari- ate Gaussian, holds that Liie = Lmse + const [53]. This equivalence ensures that our framework remains applicable in standard Gaussian regression settings, thereby enhancing its practical utility,
5 Experiment
Throughout this section, we use empirical estimators of the predictive information Iped, following the procedure outlined in Appendix B For clarity, we will refer to our estimate simply as Iped in the remainder this section. In the first part, we explain the estimation procedure for Ipedd and then use it to derive the estimated learning curve À and the optimal risk Re (Q*).
5.1 Estimation of Iped on a Gaussian process
We consider the process (X a d-dimensional Gaussian process with independent and identi- cally distributed (i.i.d.) components. In this setting, it can be shown that
[ 1 y
Ikea k)) I(X; k41 x x(t))
In
(8)
where Σj denotes the covariance matrix of X k+
Eg the covariance of X and Σ the joint
covariance matrix of the full sequence {X,)++k 14+1
k+1
Figure Iillsttrates the estimation results of Iprea k') across various input dimensions and kernel
types detailed in Appendix B.2 For this experiment, we fixed & = 5 and & 10. Ipeed-Tee True denotes the theoretical value computed from Equation Additional combinations of (ks, k') and their corresponding estimation results are provided in Appendix B.3
"The superscript (1) indicates that, due to the i.i.d. nature of the dimensions, the computation can be performed on the first dimension only and scaled by d.
7

---

Tpeot DV 0.5
23
0.14
1.3
0.16
3.9
0.59
2.5
4.1
0.97
5.7
4.5
3.2
5.5
4.8
0.5
2.
3.5
0.14
12
1.8
0.49
3.4
3.9
4.1
0.59
2.6
3.7
0.93
3.5
4.1
3.9
3.5
1.5
4.2
4.1
2.6
Apw- InfoNCE
0.48
2.2
3.6
0.14
1.2
1.3
0.44
4.3
4.4
4.5
0.58
2.6
4.4
0.93
3.9
5.9
1.7
2.7
1.4
7.8
5.4
Terd-TUBA 0.5
2.
0.14
1.2
0.5
2.7
3.5
2.6
3.5
0.96
2.9
2.9
3.4
3.1
1.4
2.9
True
0.51
3.1
6.3
AR (d-1)
AR (d=s)
AR (d-10)
Gausiaa (p- 0.5. d-1)
Gaussian 0.5. d 10)
Gaussian (p= D.. d=20))
Gaussian (p 0.8. d::))
Caussian -08 100
Gaussian (p= 0.8. d-20)-
LocalP (d-1)
Matöm 3/2 (d-1)
Marden 3/2 (d-5)
Matém 3/2 (d=10))
Matór 5/2 (d-1)
Matém 5,2 (d=s)
Matém (d-10).
Periodic (d-1).
RBF (d-1)
(d=5))
RQ (d- 10)
RQ (Exra)
Figure 1: Estimation of (k, k)) using various neural- based methods. Color encodes the
estimation bias: blue regions indicate negative bias (underestimation), while the intensity reflects the
magnitude of this bias.
While all methods provide relatively accurate estimates in fow-dimensional settings (dimensionality < 20), their performance deteriorates the input space becomes more complex. Notably, methods like SMILE and IWWa exhibited consistent underestimation, structured, high-dimensional regimes (e.g.. Periodic and RQ kernels). Although these estimators inherently introduce variance and may lead some instability the results, refining the estimation Iped lies beyond the scope of this work and would warrant dedicated investigation.
5.2 Autoregressive Process
We demonstrate the relevance of using predictive information Iprd to approximate the universal learning curve A A(k), as stated in Proposition 4.1 This experiment also serves to validate the effectiveness of A(k) in identifying the true memory length of Markovian process, in accordance N-1 with Proposition 4.2 To this end, simulate stationary vector autoregressive process {X₂ ft=o C R order p E 55, 10). The initial states Xo. Xo...., .p-1 are drawn independently from a standard multivariate normal distribution (0, [z). For t 2 p, the process evolves according to:
X,
P P ド==ーpp
Σ
Xj + V PEn
(9)
where e, N/0 I3) and the parameter / (0, 1) controls the strength of temporal dependence.
Figure compares the estimated learning curve Â(k) obtained via the estimator of predictive information from Proposition 4.1 -with with reference curve Á(k) computed from known data- generating distribution. Although this theoretical curve is not available in real-world scenarios, it serves here as a useful benchmark. Since the full distribution is known, we can accurately approximate the entropy and thereby the true learning curve (see Appendix C for derivation details).
The results confirm that ((k) closely tracks the theoretical curve and successfully identifies the correct model order p. This supports both the statistical consistency the estimator and practical usefulness of the learning curve for model selection. Despite minor fluctuations due to estimation variance, the method exhibits sharp transition at the correct order l = p. underscoring its robustness and precision in capturing the underlying temporal structure.

---

0.5
Curves
0.4
Ap=5
10
Ap=10
0.3
Ap=5
1(k)
Ap-10
0.2
A(k)
0.1
Crted 201
2
3
4
5
6
10
11
12
13
k
Figure 2: Learning curves A(k) for AR processes with orders p and p 10.
Remark 5.1. The "Critical zone" designates the range where the universal learning curve A(k) falls below small threshold (here 0.02). Because estimation does not yield exact zeros due to inherent variance, it is difficult to pinpoint the exact context length at which the curve vanishes. Introducing such cutoff therefore provides practical criterion: values of A(k) below this level are considered effectively zero. While the threshold is somewhat arbitrary, it is chosen small relative to the typical magnitude of Alk), yet large enough to remain robust to estimation noise.
5.3 Estimating R (Q*) for Ising Spin Sequences
Let X = [XuJeze E -+++++ denote sequence of binary variables where X = {11 We generate sequence of length 10. 00,,000000 starting with X₂ U +11. The sequence is divided into blocks of size M. For each block, we sample J ~ ~N(00, and evolve the sequence according
exp(JX,-1)
P( +1 Xx-1,)) exp(JX;-1) + exp(-JX:-1)
(10)
This yields a piecewise-stational Markov chain resembling bockwiss-rrndon Ising process. We train both MLP and an LSTM to predict X,+1 from the l past observations. Since an efficient predictor only requires single parameter (logistic regression suffices), we fix dim O = 1, and use cross-entropy as the loss. For each block size M E (10,000, 100,000, 1,000,000, 10,000,000, we 19), EvoRate(k). along with our modee--dependett estimates of
evaluate, for 1 < k < n (with the minimal achievable risk and the minimal loss empirically attained by LSTM and MLP models.
M
EvoRate(10)
R (Q*)
R (Q")
min R (Q)
min R (Q) 15kSR
1SkSn
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
Table 1: Estimated minimal achievable risk and estimated minimal reached risk versus EvoRate.
As M increases, the data becomes less complex: for M 10. 100000,000, the coupling J remains fixed, and the process reduces to first-order Markov chain. Consequently, EvoRate increases, reflecting stronger underlying structure, and models achieve lower prediction losses. However, while EvoRate signals learnability, it does not provide quantitative target, unlike our estimator oe (Q"). Despite being model-dependent, the oracle estimates R. (Q") remain consistent across

---

LSTM and MLP, with only minor differences relative to their scale. It also aligns qualitatively with EvoRate: lower estimated risk corresponds to more predictable sequences. Importantly, enables direct comparison with actual model performance. For example, when M = 10,000, the ratio R*)((() (Q) (Q*) R 1.3 indicates suboptimal predictions. likely due to high non-stationarity. As grows, this ratio approaches I, confirming improved model adequacy. Lastly, negative A(k) estimates for M = 10,000,000 stem from instability (see Table 8 in (k) when k >>> for a true order-p Markov process (see Figure 2 Refining this estimator is necessary avoid misinterpretation in low-complexity settings.
Additional Remarks on Result Interpretability
We estimate the parameter dimension dim(@) using Corollary 4.4 with the true value being 1. For k 10. the estimator yields 2 x k x A(k) 0.9580 when M 10,000. Comparable values are obtained for other sample sizes M, indicating the consistency of the procedure in the parametric regime. In contrast, when M 10,000,000, which corresponds to the chain length, the process effectively becomes Markovian and thus departs from the parametric setting. As theoretically expected, the estimator then approaches zero; for example, at k 10 we obtain P 0.0720.
We can also evaluate the optimal regression orders ke for each model, which remain consistent across both, evolving together and staying within the same order of magnitude M increases.
M
kLST
KMPP
10,000
100,000
1,000,000
18
16
10,000,000
10
Table 2: Estimated optimal regression orders.
6
Conclusion
This work addresses two fundamental questions in sequential modeling: (i) what is the minimal achievable risk when modeling sequential data, and (ii) is poor predictive performance due to model limitations or to the intrinsic unpredictability of the data?
To answer these questions, we introduced unified information-theoreei framework centered around the learning curve A(k), which quantifies the gain in predictive accuracy when extending the context This quantity provides principled way connect statistical dependencies in the data to achievable predictive performance. Building on this foundation, we proposed a practical estimator of the minimal achievable risk, Rxx (Q") which bounds from below the performance of any predictor operating on the same data. This estimator enables direct diagnostic test for model adequacy: if the empirical risk R² (Q) approaches R²x))) (Q*), then the observed performance is close to the intrinsic unpredictability of the process-suggestin that increasing model capacity or context length unlikely to yield further improvements. Conversely, a significant gap between these two quantities reveals that the model underfits the data, pointing unexploited temporal dependencies.
from
Through theoretical analysis, we demonstrated that A(k) admits explicit asymptotic forms in both parametric and Markov regimes, linking the decay of the learning curve to intrinsic properties such as the parameter dimensionality or the Markov order. Empirical validation on controlled synthetic datasets confirmed these predictions: our estimator consistently recovered the true minimal risk, accurately distinguished between parametric and non-paramen parameertiiic regimes, and correctly identified whether performance limitations arose from model capacity or from the intrinsic randomness of the process.
10

---

References
[1] Alexander Alexandrov, Konstantinos Benidis, Michael Bchhke-Schneider, Valentin Flunkert, Jan Gasthaus, Tim Januschowski, Danielle C Maddix, Syama Rangapuram, David Salinas, Jasper Schulz, et al. Gluonts: Probabilistic and neural time series modeling python. Journal of Machine Learning Research, 21(116): 2020.
[2] Pierre Alquier al. User-friendly introduction to pac-bayes bounds. Foundations and Trends in Machine Learning, 17(2):174-303, 2024.
[3] Arjun Ashok, Étienne Marcotte, Valentina Zantedeschi, Nicolas Chapados, and Alexandre Drouin. Tactis-2: Better, faster, simpler attentional copulas for multivariate time series. arXiv preprint wrXiv:2310.01322) 2023.
[4] Andrew R Barron and Thomas M Cover. Minimum complexity density estimation. IEEE transactions on information theory, 37(4):1034-1055 1991.
[5] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mine: mutual information neural estimation. arXiv preprint arXiv: 1100111.00000 1,00624 2018.
[6] Mohamed Ishmael Belghazi, Arnaud Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. Mutual information neural estimation. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
[7] William Bialek and Naftali Tishby. Predictive information. arXiv preprint cond-mat9902341,
1999.
[8] William Bialek, Ilya Nemenman, and Naftali Tishby, Predictability, complexity, and learning. Neural computation, 13(11):2409-2463 2001.
[9] Norman Bleistein and Richard Handelsman. Asymptotic Expansions of Integrals. Dover, 2012.
[10] Qingqiang Chen, Fuyuan Cao, Ying Xing, and Jiye Liang. Evaluating classification model against bayes error rate. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45 (8):9639-963) 2023.
[11] Minmin Cheng. Lu Zhang, Jiaming Song, and Stefano Ermon. Club: A contrastive log-ratio upper bound mutual information. In International Conference on Machine Learning (ICML), 2020.
[12] Bertrand S Clarke and Andrew R Barron. information- asymptotics of bayes methods. IEEE Transactions on Information Theory, 36(3):453-477 -711,,4-11111 1990.
[13] Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
[14] James P Crutchfield and David Feldman. Statistical complexity of simple one-dimensional spin systems. Physical Review E, 55(2))R1239, 1997.
[15] James P Crutchfield and David P Feldman. Regularities unseen, randomness observed: Levels of entropy convergence. Chaos: An Interdisciplinary Journal of Nonlinear Science, 13(1): 25-54. 2003.
[16] James P Crutchfield and NH719053 Packard. Symbolic dynamics of noisy chaos. Physica D: Nonlinear Phenomena, 7(1- 7(1-3):201-223 1983.
[17] Imre Csiszár and Paul C Shields. The consistency of the bic markov order estimator. The Annals of Statistics, 1806):661111111 2000.
[18] A. Philip Dawid and Ambuj Tewari. On learnability under general stochastic processes, 2022. URL hhttpp:://arxiv.org//baaa 07605
[19] Jérôme Dedecker and Florence Merlevède. The conditional central limit theorem in hilbert spaces. Stochastic Processes and their Applications, 108(2):229-263 2003. doi: 10. 1016/.//..ppa. 2003.07.004.

---

[20] Jérôme Dedecker, Paul Doukhan, Gabriel Lang. José Rafaél León, Sana Louhichi, and Clémen- tine Prieur. Weak dependence: With examples and applications. Springer, 2007.
[21] David Feldman and James Patrick Crutchfield. Discovering noncritical organization: Statistical mechanical, information theoretic, and computational views of patterns in one dimensional spin systems. Santa Fe Institute, 1998.
[22] Ian Fischer. The conditional entropy bottleneck. Entropy, 22(9):999, 2020.
[23] Georg Goerg- Forecastable component analysis. In International conference machine learning, pages 64-72. PMLR, 2013.
[24] Peter Grassberger. Toward quantitative theory of self- self-generated complexity. International Journal of Theoretiial Physics, 25:907-938, 1986.
[25] Steve Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes, 2020. / wwwpiii.wrg/bb.a...eee 1t/11776000111 00418
[26] Jason Hartline, Vasilis Syrgkanis, and Eva Tardos. No-regret learning in bayesian games. Advances in Neural Information Processing Systems, 28, 2015.
[27] Chih-War Wei Hsu, Branislav Kveton, Ofer Meshi, Martin Mladenov, and Csaba Szepesvari. Empir- ical bayes regret minimization. arXiv preprint 10X,vv1904.02000 2019.
[28] Olav Kallenberg. Foundations of Modern Probability. Springer, 2002.
[29] Richard W Katz. On some criteria for estimating the order of markov chain. Technometrics, 23(3):243-249 1981.
[30] Alexander Kraskov, Harald Stöghauer, and Peter Grassherger. Estimating mutual information. Physical Review E, 69(6):06613) 38, 2004.
[31] Vitaly Kuznetsov and Mehryar Mohri. Learning theory and algorithms for forecasting non- stationary time series. Advances in neural information processing systems, 28, 2015.
[32] John Langford and Matthias Seeger. Bounds for averaging classifiers. School of Computer Science, Carnegie Mellon University, 2001.
[33] Kuang-Huei Lee, Ian Fischer, Anthony Liu, Yijie Guo, Honglak Lee, John Canny, and Sergio Guadarrama. Predictive information accelerates learning in rl. Advances in Neural Information Processing Systems, 33:1 1890-11901, 2020.
[34] Bryan Lim and Stefan Zohren. Time-series forecasting with deep learning: a survey, Philosoph- ical Transactions of the Royal Society A, 379(3 379022214))22220229, 2021.
[35] Congwen Lu and Joel Paulson. No-regret bayesian optimization with unknown equality and inequality constraints using exact penalty functions. Paper-nppe,, 55(7):895-99)) 902, 2022.
[36] Daniel J McDonald and Cosma Rohilla Shalizi. Rademacher complexity of stationary sequences. arXiv preprint arXiv: I 106.0730, 2011.
[37] Mehryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for non-iid processes. Advances in neural information processing systems, 21, 2008
[38] Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saeed Anwar, Muhammad Usman, Naveed Akhtar, Nick Barnes, and Ajmal Mian. A comprehensive overview of large language models. arXiv preprint 2rXiv:2307.06433 2023.
[39] Xuanl Long Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence func- tionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(1 5886777586, 2010.
[40] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, In arXiv preprint arXiv: 180.::1807 2018.
12

---

[41] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint FrXivv1807.037444 2018.
[42] Maria Papapetrou and Dimitris Kugiumtzis. Markov chain order estimation with conditional mutual information. Physica A: Statistical Mechanics and its Applications, 192(7):1533-16) 2013.
[43] Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In International conference on machine learning, pages 5171- 5180. PMLR, 2019.
[44] Syama Sundar Rangapuram, Matthias W Seeger, Jan Gasthaus, Lorenzo Stella, Yuyang Wang, and Tim Januschowski. Deep state space models for time series forecasting, Advances in neural information processing systems, 31, 2018.
[45] Kashif Rasul, Abdul-Saboor Sheikh, Ingmar Schuster, Urs Bergmann, and Roland Vollgraf. Multivariate probabilistic time series forecasting via conditioned normalizing flows. arXiv preprint 2rX1vv2002.006103, 2020.
[46] Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denois- ing diffusion models for multivariate probabilistic time series forecasting. In International conference on machine learning, pages 8857-8868. PMLR, 2021.
[47] Omar Rivasplata, Vikram M Tankasali, and Csaba Szepesvari. Pac-bayes with backprop. arXiv preprint arXiv: 1908.07380, 2019.
[48] Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379 423, 1948.
[49] Ashwin De Silva, Rahul Ramesh, Rubing Yang. Siyu Yu, Joshua T Vogelstein, and Pratik Chaudhari. Prospective learning: Learning for a dynamic future, 2025. URL https://arxiv org/abss/411.00100
[50] Robert Snapp and Tong Xu. Estimating the bayes risk from sample data. Advances in Neural Information Processing Systems, 8, 1995.
[51] Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual informa- tion estimators. In International Conference on Learning Representations (ICLR), 2019.
[52] Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual informa- tion estimators. arXiv preprint arXiv: 2019.
[53] Kagan Tumer and Joydeep Ghosh. Estimating the bayes error rate through classifier combining. In Proceedings of 13th international conference on pattern recognition, volume 2, pages 695-699, IEEE, 1996.
[54] Kagan Tumer and Joydeep Ghosh. Bayes error rate estimation using classifier ensembles. International Journal of Smart Engineering System Design, 109, 2003.
[55] QIUHAO Zeng, Long-Kai Huang, Qi Chen, Charles X Ling, and Boyu Wang. Towards understanding evolving patterns in sequential data. Advances in Neural Information Processing Systems, 37:132747-13277,, 2025.
[56] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 16 1et11666110000 2016
13

---

Appendix
Proofs
15
A.1
On the main properties of pred
15
A.2
Learning theory
16
A.3
Asymptotic behavior pred
17
Minimal achievable risk
20
Estimation of pred
21
Estimating -ped with Variational Neural Estimators
B
Synthetic data: kernel-based methods
22
B.3
Additional Combinations of (k, k') for Predictive Information Estimation
23
4
Other simple process
24
B.5
Estimator comparison for past 30, future 40
24
Experiment
25
Ising Spin Sequences
26
D Computational Cost
28
Algorithms training procedures
28
Limitations
28
14

---

A Proofs
A.1 On the main properties of pred
Proposition A.1 (Elementary properties of the predictive mutual information). For integers kz 1 and let
Ipred (k, k') = [ x
denote the mutual information between past block of length io and a future block of length k. Assuming that the process (Xt)xez is stationary (and therefore time-translation invariant), Iredd satisfies:
1. Non-negativity.
Ipred 2
2. Symmetry. Ipre K') Ix X x
3. Monotonicity.
(a) (Increasing past) For fixed W,, Iprea + 1,k') 2 pred (k:, k)).
(b) (Increasing future) For fixed k; Iprea (ki, R/ + 1) 2 I Iredd (k; k²).
4. Chain-rule decomposition. For any split kn + ki = k',
Ipred(k, k1 12) = Ikrea k1) I(X -+1 ; X itith
tke
x1#11),
and analogous identity holds when the past block is partitioned.
5. Data-processing inequality. For any measurable maps f and g.
{(f(X)++1); 9(x(+1)) S IIpred K').
6. Convergence excess entropy. Let denote the excess (or predictive) entropy of the process: E := [Xx' I x.+1). Then lim Ipred (k, E.
Proof. All items follow directly from classical properties of Shannon's 's mutual information (see, e.g.. Chs. 2-3]).
(2) are immediate from non-negativity and symmetry of ((X;Y).
(3) Extending the conditioning set can only reduce conditional entropy, hence cannot decrease T(X;Y); apply this with X = X (resp. X x and Y x x!+k'+1)
x+1 (resp.
(4) is the chain rule I(X; (ZX +(X:)) Y) applied to suitably chosen blocks.
(5) is the data-procsssing inequality: applying measurable maps cannot increase mutual information.
(6) For fixed k. (k; k)) is non-decreasing and bounded above by E; likewise in k. Monotone convergence plus stationarity gives the limit E.
Proposition A.2 (Convergence of Iped when the future window grows). Let (Xt)sez z be a stationary process with finite entropy rate ho ;= lim H(X))/n. Write the block entropy as
H(n) n ho Hi(n),
n n
where the sub-extensive term satisfies H1 (n) o(n). Then, for every fixed 1,
lim Iproa (k, k') (k)..
# 000
15

---

Proof. For any k 2 1 the predictive mutual information can be written as
Ipred (k, k') = (() + H[K)) - H(k + k").
Insert the decomposition H(n) = nho + H2(m):
to I pprea(k, (k, k)) (f (K/)
-[(k++k))oo H1 (k+ (())) Now let + Do while keeping & fixed. Because H1 = (n),, the difference (((K)- vanishes:
(I(K') - (k + K'I - o(k) + olk + K') = o(k'),
hence tends to 0. Therefore lim pree (k: k²) Hı (A:).
k-000
Proposition A.3 (Asymptotic equivalence between (k) and Ipred). Assume Hypothesis (Ho) (stationarity with finite entropy rate lo and sub-extensive remainder H1). Fix a non-decreasing sequence k' o'= k (k) such that k' 2 k and k' (k) when l + co. Then
H(X;-u+1) = kl + Inraa (k. k') + o(k), ++000
hence in particular Iredd (k: k)Kk
0.
Proof. Write the block entropy as H(n) = n nl + (n) with (i = o(n). Using the identity
Ireea (k, K) (A) + H(K) - H(k + K') and the decomposition above gives
I prea (k. k²) = Hi (k) H, (K) H1 (k + k))
Because 1 2/2 k and K' = Ol:), sub-extensiveness yields H, (k') - Hi (k + k') o(k). Therefore
Iprea (k) H1 (k) + o(k:).
Insert this into (Kk) kl H, to obtain (k) k + p (k, k²) + o(k). Finally,
Iprec K)/K H1 (k))///)b)))))))/))/)))/) o(1) 1000, 0 because H1 (k) o(k)).
Proposition A.4 (Exact link between EvoRate and prred). Assume the process is stationary and transtrannlaiion invariant. For any integers k 1 and k 1,
Iprea (k. k') EvoRate(k) + (H'(k)) H1 (1)] + [H] +1) (1 k'),
where the block entropy is decomposed as H(n) = n 1g + H (n) with a sub-extensive part H3 =
of.). In particular, for a single-step future window (k' 1) we recover
Iproa (k: 1) EvoRate(k).
Proof. By stationarity, proe = (k)) + (k) - Hk + K"). The evolutionary rate is
defined as EvoRate(k) H1 + (k) H, 11. Solving the last equation for H, (k) gives (k) = EvoRate(k) - (1) + Hi(k (k + 1). Substituting this into the expression of Ired yields
Ipred (k, K' EvoRate + [H [1)] + [H, (k 1) H1 (k: + k)];
which is the desired identity. Setting k cancels both bracketed terms, proving the special case I Iprea (k, 1) EvoRate(k).
A.2 Learning theory
Proposition A.5 (Predictive information versus the cumulative learning curve). Assume (Hg) (strict stationarity and a finite entropy rate). For 2 1 write the block entropy as H (n) = n to + Hi(n), where the sub-extensive term satisfies (n) o(n). Define the order-k entropy rate E(k)
(lk + - (k) and the universal learning curve A(k) = E(k) - to Hı (k + 1) (k).
Then, for all integers l 2 1 and k' 2 k.
k
Σ
A(i) (k)) S (kr S
Σ A(I..
(11)
1=1
Moreover
A(k)) O,
(12)
so the width of the sandwich in
11 is (k) o(k)-
16

---

Proof. From the decomposition (n) = nlo + H1(n) we have A(k) = Hi (k) and Sk -E-- A(d) (k -1))
For any k.
Iprad (ki, H(k) + H(K) - H(k + +K) = H.(k) + H.(K)
Hi (k)
Hence
Ipedd (k, k²) Sk- [11 (k: + H1 (K)).
(13)
Because H1 is non-decreasing, (1 + k)) 2 H1 (k'); the bracket in
13 is therefore non non-negative
and we obtain the upper bound pred (k, k') S Sk-
Sub-additivity of H1 gives (k + k) & (k') + H1 (k), hence H1 (k + K)
Hi(K) v (k)..
Inserting this into (13) yields the lower bound Ired (ke k') S H1 (k). Together these inequalities establish (TT).
Finally, & (kk) = k (1 Hi)]
Hi + 1) = ({k), which proves 12
Proposition A.6 under hypothesis (Ho).
increment vs. universal learning curve). Fix k 2 Then,
(1ra(k++1,k)) (prea(k,)) k-000
A(k);
where ((k) E(k) to is the universal learning curve and E(k) H(k + 1) (k) denotes the order-k entropy rate.
Proof. Write the block entropy in its extensiveeplls--rmainner form H(n) 12 fo + Hi (n) with
(n) = o(n). Consequently
{(k: = H(k+1] H[k) H1 (k+11) (k)),,
A(k) = ((k) - to Hi H1 (k)) (1)
Proposition A.2 (convergence to the sub-extensive part) gives, for every fixed m,
k' (mre K)) H1(m).
lim
(2)
Applying 2 with m and m + we obtain
lim Ipred 1, k')
Iprea k)) Hi H,,)(()))
k
Combined with 11. this equals A(k), establishing the claimed convergence.
A.3
Asymptotic behavior of Ipred
A.3.1
Markovian case
believe that the main limitations EvoRate stem from the fact that its limiting values are unclear. It is difficult to conclude about its limits. In contrast, the study of pped and its limiting values can provide meaningful insights and may help to uncover underlying patterns sequential data. This is particularly true in the case of Markovian processes:
Proposition A.7. Assume that X is Markov process of order and that k' 2 k 2 so that the relevant past information is contained X then
P
(xttm X x H+
Ipred (ke, k2) (
X x(4E LE Ex!! I'
In
P(X+*))
In particular for order-1 Markov process, Ipred (ks,') R') EvoRate(1).
Proof. We start from the definition
P P + X
Ipred (k, = I ( :
x(+k')
=E Extte
In
x
P P(x++
17

---

Assume that X is Markov process of order m and that k 2 m so that the relevant past information
contained in X; m- We start by decomposing the unconditionnal probability (the denominator)
kt'
P
( 1+1
= II (Xeex -=1
Xets x
Since the process is Markov of order m, the simplification by the Markov property holds only when there at least m prior observations in the sequence X For ....., m, the conditional probability P (x4+ xx+1-1) remains because x X-+J-1 contains fewer than m observations (with the understanding that, by convention, for
have P (Xt-1 () P (X++1) For j 2 + 1, the Markov property yields P (Xets) (x(111
P (xts x
Thus, the full decomposition is
k' II P (X+ts j=++1
P
P(x##1)
x
II p
(xes x+1
(tj--m
x
(14)
non-simplified terms
Markov terms
Now, consider the numerator P [141 X2+++1- Since & m, the available past Xi-k+1 contains at least the last values, i.e., X; X We directly have by similar arguments,
P
P(xt#l
x x++
II P (Xets x(-
(15)
Using 14 and 15 the factors for j 2 m + in the numerator and the denominator match and cancel each other in the ratio. other words, the difference between the conditional probability P [x+t x and the unconditional probability P [x++)* is confined to the first factors. We therefore write
P (x(t1 x
I1 P Xets X
P ((x++)
I P
(Xits) x(ti-1)
We obtain, after simplification:
P (xxt 141 (X
P Px x P p(x(tr)
P ((x(())
leading to
P (xt+m X
Ipred (k, 1 x =xx
In
[+1
P P(X
Proposition A.8. Let's suppose X. is a Markovian process of order m. Then
Vk.
k m + A(k) = 0,
Proof. From the definition of the universal learning curve, and noting that Iprea is constant for greater than
18

---

A.3.2 Predictive information for a parametrised stationary process
Our goal is to derive the asymptotic expansion of the predictive mutual information when the cata-generating process belongs to a finiteddimensional parametric family. The argument extends Bialek and Tishby 771. who treated the i..dd case, to the setting of dependent sequences.
Setup and notation. Let (et be a strictly stationary stochastic process taking values in Polish space X' C IR.. For integers &o 2 1 and k' 2 & denote
X past
X -+1 (Xe-kt1....,X,)
Xi),
k (X.+1...... X(+t). Xiut X
Write p(x+)) for the joint density of the block Xy = (X1,.... X,) with respect to a reference
measure A dd on Xm
Parametric model.
Assume that there exists
open parameter set θ I (p oo),
prior density P: θ + (0, oo) of class C' on θ
a Kolmogonov-consisten family densities {QE J0e0,221 such that, for each n 2 1,
p(a7) / 2 (x2)
Consistency means that (Q/ )221 are the marginals of single probability law Qo 2
28
Chap. 8]. The true parameter 8 E θ is the (unknown) value generating the observations.
Main regularity hypotheses.
1. Stationarity and geometric a-mixing. Under the true parameter 0, the process is strictly stationary and ergodic, with Rosenblatt mixing coefficients satisfying ag(n) s Ce Ce for some constants C, < O.
2. C3 identifiability of the KL map. The function + continuously differentiable on neighbourhood of 0, attains its unique minimum 0, and has positive-definite Hessian F that point.
DRu(Qo || Qa) is three-times
3. Finite entropy rate. The block entropy H(n) = Ho, (XT) satisfies the Shan- non non-Mohi Mon-MMMillan property (n)) & onn) with 6o < oo.
Theorem A.9 (Asymptotics of the predictive mutual information). Under assumptions 73 as + 20 with k 2 k,
Ipred (k, k-==)=== = 1(Xpasti Xfut)
P In k + Ind F F- P In In((x) + In (12m)+IPPpp) Ok-
1
(16)
2
Consequently the universal learning curve A(k) = f(k) lo obeys
A(k)
p
p
+ Okk 3).
(17)
2k
4
All o(-) and O(-) symbols are uniform 0 N0)).
Proof. Letn: = k+ kK For E θ set (0) = In( (n)
X (xT)). Exponential a-mixing
p
together with a Bernstein-type blocking argument 20 numbers:
19
yields uniform strong law of large
- (.) sup #EN())
Qsass. 0.
(18)
Assumption 2 gives the quadratic expansion DKL (Q (2)) (0 FTF(O 0) + O 013))
Plugging this into (18) and integrating, we split the marginal likelihood as
p(x)) = (n) (X
exp Ln (0)) P(0) do = Qf (X Zn
19

---

Laplace expansion. Because (Kl(O) 2 c - in (()), decompose e = B(0,n-1/20 (complement). On the small ball, (0) is dominated by the quadratic form 20 F 0) with cubic remainder uniformly o(1). Classical Laplace-Watson lemma Chap. 6] yields
P(O)
2n (2T) p/2
{1+0(n=)).
(19)
Vdet
The contribution of the complement dn p/2) because the integrand decays like expl cnn)..
Block entropy decomposition. Taking the In and the Qg-expectation of Q (XT) 2n and invoking
3 give
1 P Inn Int. P (n(2 + In P(0) +0
H(m) Eo
(20)
Predictive information. By definition Iprea (ki, k) = H(k) H(W) H(k + k²). Substituting (20
with n k, le 1 cancels the extensive nlo parts; the remaining sub-extensive contributions
yield 16
Finally
A(k) [(k) - Eu 1) (H) + H(
p
p
2k
4k
where the last equality follows from Taylor expansion In(k+1) - In k = カ- Uniformity of the remainders ensured by the uniform Laplace estimate 19p. This completes the proof.
_ + 0
Remark A.10. The leading term 2 In coincides with the model penalty in Bayesian minimum description length [12] 4y. The constant In P(O) E In(2m) depends on the local prior mass; it vanishes the derivative A(k) but is essential for the absolute scale of Ipred-
A.4 Minimal achievable risk
Proposition A.11 (Learning-cure, surplus bound). Let (Xt)tez be stationary and geometrically a-mixing, ie. ((n) & Ce en for constants C, c >> O. For every regression order h E N, every predictor Q Hr, every sample size n 2 1 and every confidence 5 (), with probability least 1-8
R (Q") & (²) - A(k) + (Fx) + In(1/6)
(21)
where (Fk) is the empirical Rademacher complexity of the loss class F { (x -In 1n1 x) Q Hx).
Proof. For any Q E Hi.
R* =R²(Q") + ( A(k),
because A(k) R* R00 Since the loss function E(s:) is non-negative, R*(Q)
Rd (Q"),, hence
R² (Q) 2 Rd R (Q") + A(k).
Rearranging gives the excess-risk identity
xd R²)Q") < (() A(k).
(22)
Because sequence is geometrically mixing, Theorem 2 McDonald and Shalizi [36 (their
bounded-loss Rademacher bound for a-mixing processes) applies to Fr: with probability 2 1 - 8
+3 In(1/5)
R*) <
for every Q E H4.
(23)
Insert 23 into the right-hand side of 22 to obtain 2T
20

---

Corollary A.12 (Oracle estimator and minimal order). Assume the high-probability event of Proposi-
tion A.11
For a collection of pre-trained models {Qx H 1M
define
R (²)) = min IskSM (Qx) -(K))
Then
R²)2)) & (Q)) and k E arg min (Qx)
- A(H)) - k²
ISRSM
where h- : inf A(k) = 0} is the minimal order for which the universal learning curve vanishes.
Proof. Under the bigb-brobability event, inequality (1 is valid for each k = 1,...,
..... M when
evaluated Qs- Discarding the non-negative complexity terms yields
R²') < (Qx)) A(k),
Wk S M.
Taking the minimum over k proves the claimed upper bound on R Rº00" (Q*). Af realises that minimum
while ht < k., then A A(+t) > A(k*) = and monotonicity of would contradict optimality of let
Hence k k.t
B Estimation of pred
B.1 Estimating I pped with Variational Neural Estimators
We estimate the predictive mutual information Ipred using variational techniques based on recent advances in neural MI estimation. Given d-dimensional time series (Xt), our goal is to estimate
Ipre
X
which quantifies the mutual information between past window of ls time steps and future window of 1 steps.
Variational Estimators. Our approach builds on contrastive lower bounds of mutual information,
including SMILE (52) NWJ [39], InfoNCE 40). TUBA [43,, and DV [5). These methods rely on parameterized critic function fo v), which scores pairs of past and future segments. The critic is
trained to distinguish between positive pairs (sampled from the joint distribution p(z, y)) and negative pairs (from the product of marginals p(z)p(y))
Training Objective. objective of the form:
The mutual information estimate is obtained by maximizing variational
B fo vi) In
B
Aprea(k: K.) Iaxx
Σ
exp(fo(#;,
(24)
B
B(B 1)
where B is the batch size and the second term acts as a contrastive regularizer, penalizing high scores on mismatched pairs.
Critic Architectures and Optimization. To capture the structure temporal data, we experiment with multiple critic architectures: Separable (independent encodings for past and future), Concate- nated (joint embeddings), and Sequential (L.STM-base) encoders). The critic parameters are optimized using the Adam optimizer with stochastic gradient updates.
Data Sampling. Training batches are constructed either by sampling synthetic data from known generators, or by extracting context-future pairs from long, continuous sequences. The full training procedure is detailed in Algorithm
21

---

B.2 Synthetic data: kernel-based methods
For this part, we don't tt't assume the invariance temporal translation and stationarity of the process, as our concern is to verify that the estimators are working correctly.
Proposition B.1. (Theoretical value of prea) In the particular case where we consider {X+]t-k+1 Gaussian process of dimension d with all dimensions independent and of the same distribution, we can compute explicitly pred.
prii (k) I(Xi-K+ x d In
2
Where Σ1 represents the covariance matrix of X 1-++1 Σg the covariance matrix of X and E the joint covariance matrix. The index (1) means that we can just look at the first dimension of the Gaussian process.
Proof. For a Gaussian process with dimension d and independent dimensions, the predictive infor- mation formula is:
d
Σ
(
I [ Xtuture)
In
(25)
2
Using the differential entropy property of a Gaussian vector X of dimension n with covariance matrix Σ:
1(X) In In((2T))*[E)
(26)
Due to the independence of dimensions, the mutual information decomposes as:
T(X pasts X Xfuture )
T(X(i) x-1 pasts future
(27)
For each dimension j. with >:(1)) representing the covariance matrix of x(1) x-(0) of x future and 2 the joint covariance matrix:
pasts
I 1(x(1 pasti x f
h(x past + h(xxxxxx (((x() - h 1(x (1)
x(0) past: xluture)
(28)
1 In In((Te))"
1
1
In (2
In (2(TT)m)
(29)
2
2
2
|
(2Te) 11 (2Te)*²
In
(30)
2
2
(2 t
1 In
2/2
(31)
Summing over all dimensions yields the result.
In practice, to ensure that the covariance matrix was invertible, we stayed with a low temporal resolution, from 5, k' 10 30, k' 40. If the covariance matrix was invertible, we were just removing it from our results. To perform the experiences, we have chosen different Gaussian kernels,
AR Kernel (Auto-Regressive): K KAR(ti, (2) = 0² p1
Matérn 3/2 Kernel: KM3z t2) 0² [ ا exp - ا
Matérn 5/2 Kernel: KM52(11, 12) = o² (1+ volcutaal علعيوو
exp vb 11
3r
22

---

Squared Exponential Kernel: KsE(t1,t2) 0² eexp(
-
21
Periodic Kernel: (er, 12) = o² expp (- 2innn( 14 12
12
Rational Quadratic Kernel: KRQ(lI, (2)(()11))=0) = (1 (1+
14 1
-8
2012
sluu(( 112 exp
Locally Periodic Kernel: Kip(t1. 12) = 0² exp
Ita-tal" 2d22
12
For our experiment, we evaluated several variational lower bounds for mutual information estimation fyed-SMILE [52], NWo [39], Iped Ipe.-InfoNCE [4Л) Ipedd-DV [5]. and TTee [43]. We took as parameters the followings, where ın practice, t and t2 takes values between 0 and k + kr 1. As
14.4 choose = k 1 the date of observation of (X, [-41- The table describe the parameters
we took for each of the kernels in the experiments.
Method AR
Period
Decay
0
0.8
0.5
Matérn 3/2
2.0
1.0
Matérn 5/2
2.0
1.0
Squared Exponential
2.0
1.0
Periodic
3.0
0.5
Rational Quadratic
2.0
1.0
1.0
Locally Periodic
4.0
10.0
Table 3: Parameters choose for each of the kernels.
B.3 Additional Combinations of (k, K) for Predictive Information Estimation
This section presents complementary estimation results for the predictive information Iprdd (k: k) obtained with various combinations of past and future context lengths (k, k'). These results extend the main analysis shown in Figure where A: 5 and k 10 were fixed.
Case 1: = 2, k 5:
DV 0.51 23
3.5
0.14
13
0.48
5
2.7
4.1
0.95
3.5
4.9
4.2
3.4
14
5.6
4.8
0.48
L SHILE:
0.5
2.4
2.5
0.14
13
17
0.48
3.3
2.7
4.7
0.6
2.7
2.6
0.94
3.3
1.9
4
3
1.5
3.4
4.3
Ioo- InfoNCE 0.5
2.3
0.13
1.3
0.49
5.7
6.2
0.56
2.6
4.4
0.94
3.9
6.6
1.6
2.9
8.2
TyNe-UUBA 0.5
2.2
0.14
1.3
0.51
2.6
4.6
2.4
2.2
0.95
3.3
3.9
2.9
3
Iped-True 0.51
2.5
5.1
0.14
1.4
2.9
0.51
5.1
10
8.6
0.62
3.1
6.2
5
10
12
6.3
1.6
16
AR (d-1)
AR ()=5)
AR (d-10)-
Gussian (o- 0.5, d-1)-
Couzsoon 05, d-10)
Goussian (o 06. d=20)-
Goustan (o 0.8, d=1)-
Coussion d-10)
Cousion (o 0.8, d=20)-
Local-P (d-1)
Matém 3/2 (d=1)
Matérn 3/2 (d-5)
Motérn 3/2 (d=10)-
Matôi 5/2 (d-1)
Matém 5/2 (d=5)-
Modémn 5:2 (d-10)
Periodic (d=1)-
RBF (d-1)
RQ (d=5)
no (d=10)
RQ (Extra)
Figure 3: Estimation of (2, () using various neural-based methods.
Case k 10, k' =0:
23

---

Tpeot DV 0.19
23
0.14
111
0.51
3.4
2.5
4.2
0.93
3.7
4.3
3.3
6.3
4.9
0.5
2.
3.5
0.13
12
1.2
0.48
3.4
3.7
4.1
0.6
2.6
3.8
0.94
3.5
4.1
4.2
3.6
1.5
4.2
4.1
Apw-- InfoNCE 0.51
2.2
3.5
0.14
0.87
0.96
0.49
3.8
3.6
4.9
0.58
2.7
4.5
0.96
3.8
6.3
4.2
3
1.2
9.5
5
Terd-TUBA 0.5
2.3
3.3
0.14
1.1
0.49
4.7
2.5
0.96
3.5
3.3
3.5
3.1
1.5
3
3.7
True
0.51
6.3
AR (d-1)
AR (d=s)
AR (d-10)
Gausiaa (p- 0.5. d-1)
Gaussaa 0.5. 10)
Geussian (p= D.. d=20))
Gaussian (p= 0.8. d::])
Gaussian 088 10)
Gaussian (p= 0.8. d-20)-
LocalP (d-1)
Matöm (d-1)
Marden 3/2 (d-5)
Matém 3/2 (d=10)-
5/2 (d-1)
Motém 5,2 (d=s)
Matém 5,2 (d- (d-10))
Periodic (d=1)-
RBF (d-1)
(d=5).
RQ (d 10)
RQ (Exrr))
Figure 4: Estimation of (10, 20) using various neural- buseel methods.
B.4 Other simple process
Consider the process {z (2) C Rd defined as follows:
N-1
2g ~ NO0, Ia),
(32)
= 1 v1 p Eto 12 1,
(33)
where p E (-1,17 1) is the correlation coefficient, La is the d x d identity matrix, and N0, Ia) are i.i.d. random vectors.
This defines a Markov (AR(1)) Gaussian process in which each state depends solely on the immediate predecessor. the total time length is given by N pass Tius we partition the sequence into:
X past
{:0,- 31, ......... 2Tm
Xiu
{ (2Tpmt
1
Then we compute the theorical value of I pread thanks to 4.2
B.5 Estimator comparison for Tpast 30, T fature-
Below are the estimated values of pred across different kernel types, critic architectures, and values.
The training parameters are follows: a batch size of 70, 10,000 iterations, and a learning rate of
5 x 10-4
24

---

dim
theoretical mi
rho
SeparableCritic
ConcatCritic
SequentialCritte
EvoRate
kernel_type
0.14
0,50
0.14
0.14
0.01
0.14
0,51
0.80
0.48
0.51
0.28
0.48
0.83
0.90
0.77
0.82
0,44
0.79
5
0.72
0.50
0.63
0.67
-0.07
0.65
5
2.55
0.80
2.16
2.41
1.37
2.13
4.15
0.90
3.17
3.75
2.15
3.34
2.88
0.60
1.45
-1.99
0,60
10.22
0.80
3.21
6.07
5.86
3.16
20
16.61
0.90
4.97
9.28
8.87
4,95
100
14.38
0.50
0,41
0.78
5.14
0,51
100
51.08
0.80
2.13
3.76
45.64
2.46
100
83.04
0.90
4,40
5.46
63.96
4.58
0.51
0.48
0.50
0.28
0.47
AR
0.62
0,58
0.59
0.23
0.57
matern32
7.09
0.58
1,39
periodic
2.55
1.83
2.39
1.10
2.22
AR
5
3.09
2.52
2.75
0.97
2.62
matern32
5
7.12
28.55
2.83
3,93
periodic
20
10.22
2.12
4,92
4.08
2.11
AR
20
12.35
2.33
5.40
5.45
3.23
matern32
13.34
31.06
11.61
4.96
periodic
51.08
2.40
3.63
20.77
1.87
AR
100
61.74
2.07
3.06
44.52
2.37
matern32
100
9.47
26.18
81.52
7.40
periodic
Table 4: Comparison of predictive information estimators across different kernel types and process dimensions. Values rounded two decimals.
C
Experiment
Note the Use of Nats
Units in nats. Throughout experiments, all information-theorrtie results and measures (e.g.. mutual information and differential entropy) are reported nats rather than in bits. In information theory, the choice of base for the logarithm determines the unit: base-e (the natural logarithm) yields nats, while base-2 yields bits. We prefer natural logarithms because they often simplify analytical expressions in both theory and implementation (e.g.. when computing the log-likelihood in many machine learning frameworks). However, is straightforward to convert from nats to bits by noting
nat
In(2) bits.
Due to this simple relationship, one can easily switch to bits by scaling the values by 1/ In(2) desired.
Estimation of Ä(k)
To estimate the learning curve Â(k) 1(k) - lo. we evaluate the conditional entropy rate ((k) from the data and analytically compute the theoretical baseline lg. From the probabilistic formulation in Equation ( we can directly access the data distribution, which allows us to compute the entropy as follows:
Estimation of ((k). We estimate the conditional entropy ((k) = H (X, Xr-k...., X 1) of multivariate time series using ridge regression. After fitting a linear model to predict X, from its past, we compute the residuals and estimate their empirical covariance matrix Σ. Assuming the residuals are approximately Gaussian, the conditional entropy is estimated using:
((k) In ((2me)* -E)),
where d the dimension of the observed vectors.
Estimation of lo-
25

---

According to Proposition 4.2 from Equation
we have lu = I(p) for an autoregressive process of order p. Furthermore, X Xt-p follows a normal distribution with
P P
X and o² 0²
ド=レーp
Since l(p) (X, x we can compute directly using the above formula for the conditional entropy of multivariate normal distribution.
X(p)),
C.1 Ising Spin Sequences
Training of the MLP and LSTM models. We train both multilayer perceptron (MLP) and long short-term memory (LSTM) model on spin chain data generated using the procedure described in Section 5.3 Each model receives context window of length & and is trained predict the next binary symbol in the sequence.
The MLP model consists of two hidden layers with ReLU activations, mapping the input vector of length to a softmax output over two classes. The LSTM model, on the other hand, processes input sequence series of scalar values through an LSTM layer followed by fully connected output layer.
Training is performed using the Adam optimizer with a learning rate of 10-3 and a batch size of 128. For each value of k, training proceeds for up to 1000 epochs, using early stopping with a patience of 10 epochs based on validation loss. To standardize comparisons across models, we fix the number of batches per epoch and apply the same evaluation procedure to all architectures. The dataset split into 80% training and 20% validation sets, and results are averaged across runs account for variance.
Model architectures:
2 hidden layers (64, then 32 neurons), ReLU activations, output layer with units (softmax).
MLP:
LSTM:
Single-layer LSTM (32 hidden units), fully connected layer mapping to output classes.
Training setup: Adam optimizer (Ir=10-3), batch size=128, max epochs=1000, early stopping (patience=10), 50 batches per epoch, 80/20 wrain-validation splít.
Below are the results obtained for different block sizes M: (1) 10,000, (2) 100,000, (3) 1, 1,000,000, and (4) 10,000,000.
R/ (Q)
(et.,(())
Å(k)
R(/sm(( A(k)
* Atk)
EvoRate(k)
0.6932
0.6927
0.1208
0.0043
0.3724 0.0043
0.3719 # 0.0043
0.0005 + 0.0012
0.6220
0.0023
0.5955
0.5571
0,1503 0.0031
0.4452 1 0.0051
0.106% = 0.0031
0.1731 + 0.0015
0.5611
0.5560
0.1
0,4434
0..034
0.2059 0.0115
0.5394
0.5429
0.0962 0.0035
0,4432 + 0.0035
0.4467 + 0.0035
0.2274 + 0.0120
0.5347
0.5343
0,0810 0.0036
0.4537 0.0036
0.4533 0036
0.2427 0.0122
0.5167
0.5199
0.0696 + 0.0035
0,4471 + 0.0035
0.4503 + 0.0035
0.2541 + 0.0124
0.5105
0.5088
0.0607 0.0035
0,4498 0.0035
0.4481 0.0035
0.2629 0.0125
0.5036
0.5092
0.0537 0.0034
0,4499 0.0834
0,4555 A 0.0034
0.2700 & 0.0126
10 0.5079
0.5064
0,0479 0.0034
0,4600 0.0034
0-4585 0.0034
0,2758 0.0126
0.5077
0,5232
0.0430
0.0034
0,4802 =
0.2807 0.0127
12
0.5181
0.4997
0.0389
0.0034
0,4792 + 0.0034
014608 0.0034
0.2850 + 0.0127
0.0128
14
0.4989
0.4992
0.0324
0.0033
0.4665 1 0.0033
0.4668 = 0.0033
0.2924 + 0.0128
0.4864
0.5000
0.0297
0,4567 0.0032
0,4703 0.0032
0.2962 0.0128
16
0.4949
0,5062
0.0273 + 0.0032
0.4676 1 0.0032
0.4789 : 0.0032
0.3010 + 0.0128
0.4972
0.4968
0.0252
0.4720 0.0032
0.4716 0.0032
0.3080 0.0128
18
0.4885
0.4872
0.0232 0.0033
0.4653 0.0033
0.4640 + 0.0033
0.3202 + 0.0128
0.4853
0.5041
0,0213 0.0034
0.4640 0.0034
0.4828 0.0034
0.3452 0.0129
Minima
0.4853
0.4872
1²*(())) 0.3724 0.001 x²*(")) 0.3799 0.0043
Table 5: Estimated risks and A(k) values for different history lengths & (M = 10,000).
26

---

Order k
R/ (Q)
(Q)
A(k)
R/smu (Q) A(k)
Rin=(Q) A(k)
EvoRate (k)
0.6897
0.6933
0.3213
0.3684 0.0153
0.3720 = 0.0153
0.0056 0.0030
0,5789
0.6070
0.2061 0,0058
0.3728 + 0.0058
0,4009 = +000558
0.1261 + 0.0208
0.6036
0.5745
0.1506
0.4530
0.0071
0.1832 0.0262
0.5497
0.5615
0,1179 = 0,0081
0.4318 1 0,0081
0.4436 = 0.0081
0.2163 + 0.0282
0.5146
0,9964
0,4182
=: 0.0085
0.23379 0.0290
0.5226
0.5537
0.0811 0.0087
0,4415 0.0087
0.4726 = 0.0087
0.2531 + 0.0294
0.5311
0,5409
0.0697 0.0088
0,4614 0. 0,0088
0,4712 0.0088
0.2645 0 0.92
0.5124
0.5831
0.0608 0.0088
0.4516 + 0.0088
0.4923 + 0.0088
0.2733 + 0.0296
0.5236
0.5331
0,0537 0.0088
0,4699 0,0088
0,4794 0.0088
0,2803 0.0297
10 0,4901
0,5186
0,0479 0.0088
0,4422 1 0.0088
0,4707 1 0.0088
0.2861 4: 0.0297
11
0,4679
0,5119
0.0430 0,0088
0,4249 0,0088
0,4689 = 0. 0,088
0.29 10 0.0296
0.4975
0.5273
0.0389
0.0088
0. 0.0088
0.2952 0.0296
13
0.4692
0.4736
0,0353 0,0088
0.4339 0 0,0088
0.4383 = 0.0088
0.2990 + 0.0296
0.5152
0,5259
0.0323
0,4829
0,4936 0.DUS8
0.30126
15 0.4971
0.4733
0.0296 0,0087
0.4675 0.0087
0.4437 = 0.0087
0.3064 + 0.0296
0.4714
0,5184
0.0272
0,0087
0,4912 2: 0.00877
0.3112
17 0.4996
0.5278
0.0250
0. 0.0087
0.4746 0.0562000000 0.0087
0,5028 = 0.0087
0,3182 + 0.0295
0.5037
0.4748
0.0230 0.0069
0,4807 0.0089
0,4518 0009
0.3305 0.0297
19
0.5189
0.4668
0 0.0092
0.4978 0.0092
0.4457 = 0.0092
0.3556 + 0.0299
Minima
0.4679
0.4668
(Q') = 0.3684 = 0.0153
(Q') 0.3720 = 0.0153
Table 6: Estimated risks and A(k) values for different history lengths l: (M 100,000).
Order
(Q)
(Qa)(Q)
Á(X)
R(sTM(() A(R)
( - A(k)
Evoßate(A)
0.6910
0.6808
0.3235
0.3675 0.0718
0,0718
0,0009 0.0320
0.5641
0.6290
0,2069
0,0188
0.3572 a: 0.0188
0.4221 = 0.0188
0,1450 + 0.0465
0.6157
0.5502
0.1510
0.4647
0,3992 0.0314
0.20990 0.0554
0.5913
0,5847
0.1181 = 0.0376
0.4732 : 0.0376
0,4666 = 0.0376
0,2460 +: 0.0588
0.5621
0.5145
0.0965 0.0395
0,4656 0.0395
0,4180 0.0395
0.2706 0.0603
0.5087
0.6114
0 # 0.0402
0,4276 + 0.0402
0,5303 # 0.0402
0,2883 + 0.0609
0.4705
0.4423
0,0697 0,0401
0,4008 0.0401
0.3726 0.0401
0,3016 0.0613
0.5378
0.5469
0.9607 0.0398
0,4771 + 0.0398
0,4862 = 0.0398
0.3120 + 0.0614
0.5195
0,5008
0.0536 0,0394
0,4659 0.0394
0,4472 # 0.0394
0,3202 + 0.0615
0.4480
0,4690
0.0478
0.0390
0,4212 + 0.0390
0.3269 0.0615
11 0.5612
0,5034
0.0429 0,0386
0,5183 & 0.0386
0,4605 = 0.0386
0,3326 +: 0.0615
0.5172
0,4650
0.0388
0.0383
+ 0.0383
0.3373 0.0615
13
0.5039
0,5169
0.0352 0.0379
0.4687 1 0.0379
0.4817 = 0.0379
0,3416 + 0.0615
0,5588
0.4728
0.0321
: 0.0376
0,3456 0.0615
15
0.4760
0.4402
0.0294 # 0.0374
0,4466 + 0.0374
0,4108 = 0.0374
0,3498 + 0.0614
16
0.5425
0.3660
0.0270 0.0373
0,5155 0.0373
0.3390 0.0373
0.3548 0.0614
17
0.4003
0.4738
0.0249 # 0.0370
0.3754 0.0370
0,4489 + 0.0370
0.3619 +: 0.0616
18
0.3798
0.4653
0,0229 0.0359
0,3569 0.0359
0.4424 0.0359
0,3741 0.0618
19
0,5082
0,5629
0.0210 = 0.0315
0,4872 0.0315
0,5419 = 0.0315
0.3989 + 0.0618
Minima
0.3798
0.3660
(Q') = 0.3569 = 0.0359
(Q*) = D.33300 0.1373
Table 7: Estimated risks and A(k) values for different history lengths 1 (M 1, 1,000,,000).
Order
Ris
(Q)
Á(k)
NisT (Q) A(k)
(Qa - A(k))
EvoRate(k)
0.6709
0.3551
0.0037 0.0929
0.6672 + 0.0929
0.3514 = 0.0929
0.4760 0.2277
0.5209
0.2713
0.0037 0.0067
0.5172 + 0.0067
0.2676 = 0.0067
0.4760 #: 0.2277
0,1961
0.6698
0.0037 0.0086
0.1924 1 0.0086
0.6661 = 0.0086
0.4760 0.2277
0.5440
0.6037
0.0057 = 0.0075
0.5403 + 0.0075
0.6000 = 0.0075
0,4760 + 0.2277
0.2271
D. 1029
0.00337 + 0.0108
0.2234 + 0.0108
0.0992 = 0.0108
0.4760 + 0.2277
0.2312
D.4188
0.2275 + 0.0101
0.4661 0.0101
0.4760
0.6919
0.6896
0.0037 2 0.0139
0.6882 a 0.0139
0.6859 = 0.0139
0.4760 1: 0.2277
0.6824
0.5694
0. 0.0077 0.0143
0.6787 : 0.0143
0.5657 0.0143
0.4760 0.2277
0.6913
0.0903
0. 0.0066 + 0.0061
O 0.7777 + 0.0061
0.0867 = 0.0061
0.4760 + 0.2277
10
0.0733
0.1276
0. 0.0036 0.0206
0.0697 0.02066
0,1240 0.0206
0.4760 0.2277
0.5529
0.6932
0.0035 0.0067
0.5494 a: 0.9067
0.6897 = 0.0067
0.4761 4 0.2277
12 0,5981
0.6909
0.003400.000 0.0098
0.5947 2 0.0098
0.6875 = 0.0098
0.4762 0.2277
0.5111
0.6873
0.0031 0.0079
0.5080 + 0.0079
0.6842 = 0. 0,0079
0.4744 0.2276
14
0.4116
D.5636
0.0025 + 0.0063
0.4091 + 0.0063
0,561 = 010063
0.4767 + 0.2275
0.6620
0.5387
0.0013
0.6607 + 0.2535 4 0.0099
0.5374 = 0.0054
0.4772
16
0.2525
0.6352
-0.0010 0.0099
0.6362 = 0.0099
0.4779 # 0.2263
0.3450
0.5577
-0.0099
38
0.3509 0.0138
0.5636 = 0.01 38
0.4788 0.2246
18
0.6929
0.6884
-0.0156 = 0.0142
0.7085 + 0.0142
0.7040 = 0.01
0.4801 + 0.2209
0.2151
0.2619
0.0355 0.0050
0.2506 + 0.0050
0.2974 0.0050
0.4819 0.2128
Minima
0.0733
0.0903
Re (Q') 0.0697 0.0206 (²') 0.0867 + 0.0061
Table 8: Estimated risks and A(k) values for different history lengths & (M = 10,000,000).
27

---

D Computational Cost
All experiments conducted system equipped with 14-core CPU, 20-core integrated GPU, 24 GB of unified memory, and TBB of SSD storage.
Estimating Iprdd The computational complexity of the proposed algorithm is primarily driven by the estimation of mutual information between learned representations. This process incurs a cost of O(B²d) per iteration, where B is the batch size and d is the dimensionality of the representations. The O(B²d) complexity reflects the need to compute pairwise interactions between samples within each batch in high-dimensional space. The total computational cost per iteration is therefore d)),),, excluding the contribution of the encoder and decoder h, whose complexity depends on their specific architectures.
Estimating ((k) Using Corollary 4.4 when k ranges from I to the computational complexity of estimating the learning curve is (n
Estimating R0 (Q") The total cost corresponds to training the model Q times over However, this cost generally unknown or difficult to quantify directly. Moreover, it must be added to the computational cost required estimate the learning curve A(k)).
E Algorithms training procedures
Algorithm Ipred: Data is sampled in sequential manner with temporal alignment
for each training iteration do
2:
Sample {[T, 1.)) from a long sequence {z, { such that:
22 = -k......... 21, Y: = [ 2t,+
3: Compute critic scores Sij = ((xx))9)
4: Compute pred using Eq. (3):
1 B
B
Ikrod, k') =
Σ
fol vi) In
Σ
exp(fo (z,, v,))
B
B(B 1)
5: Update critic parameters 0 by maximizing Ipod
6: end for
F Limitations
Estimating Iped remains a challenging task in practice. Since the learning curve is derived directly from this quantity, any noise or bias in the estimation can lead to significant errors the assessment of the optimal achievable risk. In particular, the tendency of current estimators to systematically underestimate Iped can misrepresent the true predictive structure of the data. Moreover, estimation can suffer from variance and occasional instability, especially in high-dimensional settings when the underlying process has weak temporal dependencies. While developing a definitive and robust estimator of pree is not the main objective of this work, we view it as important and promising direction for future research its own right.
Another limitation lies in the fact that our estimator of the minimal achievable risk is model-dependent, in contrast to model-free approaches such as EvoRate (55). We acknowledge that this dependency introduces potential confounds related to model capacity and training variability. However, our framework designed with different purpose: while EvoRate aims to detect the mere presence of temporal structure, our objective is to quantify how much of this structure is captured by a given model class. The core quantity of interest- tte learning curve A reminns model-indeependnt and reflects the intrinsic predictability of the data across context lengths. The model-specific risk can then be seen as an added diagnostic, enabling one to assess whether predictive limitations stem from insufficient model capacity from intrinsic data constraints.
28

---

Importandl, in our experiments, the estimated minimal achievable risk was generally stable across different architectures, which suggests that the diagnostic remains robust despite being evaluated within specific model classes. Nonetheless, we emphasize that mutual information estimation in sequential settings is still young and evolving research area. We hope that our contribution helps lay the theoretical foundation for more robust mutual information estimation to the more stable and interpretable learning curve A(k).
by shifting focus from direct
Finally, an important future direction will be to evaluate the framework on large-scale real-world sequential tasks sasks-such as those in natural language processing where validating its usefulness beyond synthetic benchmarks would provide strong evidence of its practical relevance.
29

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
Justification:
The claims clearly stated in the abstract and introduction. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification See Appendix section
Guidelines:
30

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The full of assumptions is described before each proposition and theorem and each corresponding proof can be found in the Appendix section A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
See Appendix sections and
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
31

---

If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification
The GitHub link is provided in the introduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ peplllc/guides.. (oodeSumiissiiooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips.cc cc/ http://lll/ggg..dee/eeeeeeueeeee http:///otttuubmsssooooooooo.ooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
32

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
See Appendix sections
and
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Confidence intervals are reported whenever computationally feasible. See Section 5 for details and Appendix C.1 for additional results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma eтror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See Appendix section
D
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
33

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpinttttss///oor......coo///tt
Answer: [Yes]
Justification: Anonymity preserved.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [No]
This work constitutes foundational research in machine learning rather than applied study, and as such, it does not pose any foreseeable negative societal impact.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks are associated with this paper.
Guidelines:
The answer NA means that the paper poses such risks.
34

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Relevant references are appropriately acknowledged in the Related Work section.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsswiteeetteeeeeeeeeeeep thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Documentation of the new assets can be found Appendix sections and Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
35

---

This paper does not involve crowdsourcing or research involving human subjects.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: LLM are only used for editing and formatting purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy htttp:://eerrissccc/oofeeeeeeeee for what should or should not be described.
36


Reviews:
[{"review_id": "xWpAtBrmvg", "reviewer": "Reviewer_MaER", "summary": "Building on the classical works of Bialek and Tishby [1], and Crutchfield and Feldman [2], this paper addresses the following questions related to sequential modeling: \n\n1)\tWhat is the minimum achievable risk for a predictor modeling sequential data?\n2)\tIf a model performs poorly, is it due limitations of the model, or due to the inherent unpredictability of the data? \n\nEffective sequence modeling requires (1) predictable patterns in the data, and (2) a model capable of exploiting those patterns. Determining whether a sequence contains predictable patterns is a crucial first step. Predictive information $I_{\\text{pred}}(k, k')$ (mutual information between the past $k$ observations and the future $k'$ observations) and universal learning curve $\\Lambda(k)$ (the discrete derivative of predictive information as $k' \\to \\infty$) are classical quantities that measure the learnability and complexity of a sequence.\n\nThe paper begins by revisiting basic concepts from information theory and defining predictive information and the universal learning curve under the assumptions of stationarity and finite entropy. The authors then compute these quantities for a $m$-order Markov chain and a parametric process where the dimensionality of the parameter space is $p$. Similar calculations can also be found in [1, 2]. \n\nNext, the authors bound the minimal achievable risk by the true $k$-th order forecasting risk minus $\\Lambda(k)$. They also present an empirical version of this bound involving the empirical $k$-th order forecasting risk. Based on this bound, if the model's loss fails to improve beyond a certain context length $k$ while $\\Lambda(k) > 0$, it indicates that the current model complexity is insufficient to capture the learnable patterns in the sequence. This, I believe, is the key contribution of the paper, as it addresses questions (1) and (2) above.\n\nFinally, the authors provide some experimental results demonstrating the estimation of $I_{\\text{pred}}(k, k')$ on a Gaussian process, the ability of the estimated $\\Lambda(k)$ to identify the correct order of an autoregressive process, and the estimation of the minimum achievable forecasting risk of an Ising spin sequence. \n\n**References**\n\n[1] William Bialek and Naftali Tishby. Predictive information. arXiv preprint cond-mat/9902341, 352 1999.\n\n[2] James P Crutchfield and David P Feldman. Regularities unseen, randomness observed: Levels of entropy convergence. Chaos: An Interdisciplinary Journal of Nonlinear Science, 13(1): 25–54, 2003.", "questions": "I'm listing some minor questions and suggestions below. \n\n1. In line 32, you cite an example about the performance discrepancy related to GluonTs despite recent innovations. Can you elaborate this example by proving more context?\n\n2. In line 139, you use $\\ln$ and later in Eq. 6, you use $\\log$. Also, in line 139, $\\mathcal{F}_k$ is a set of functions, and in line 186, $\\mathcal{F}$ is the Fisher information matrix. Better to be consistent with the notation. \n\n3. In Figure 1, you have not indicated what the strength of the color means. \n\n4. Prospective Learning [1] introduces a framework in which data is generated by a stochastic process, and the learner is expected to produce a sequence of hypotheses that achieves low risk on future observations, given the data observed up to the present. I believe some of the results from your paper could be used to extend or enrich this framework. Related ideas have also been explored in [2, 3]. It would be valuable to position your work in the context of these studies in the related work section.\n\n**References**\n\n[1] De Silva, A., Ramesh, R., Yang, R., Yu, S., Vogelstein, J. T., & Chaudhari, P. (2024). Prospective Learning: Learning for a Dynamic Future. arXiv preprint arXiv:2411.00109.\n\n[2] Dawid, A. P., & Tewari, A. (2020). On learnability under general stochastic processes. arXiv preprint arXiv:2005.07605.\n\n[3] Hanneke, S. (2021). Learning whenever learning is possible: Universal learning under general stochastic processes. Journal of Machine Learning Research, 22(130), 1-116.", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I enjoyed reading this paper. The ideas are communicated clearly and effectively. However, I believe it lacks a bit of originality, as tools such as predictive information (or excess entropy) and the universal learning curve (or entropy gain) are well-established concepts in the field. That said, the paper makes a novel and interesting contribution by connecting these quantities to the minimum achievable risk, which adds valuable insight to sequential learning and modeling.", "was_revised": true, "final_justification": "The authors have successfully addressed the concerns I had. This paper employs predictive information and universal learning curve initially introduced by Bialek and Tishby, and Crutchfield and Feldman, to quantify the limits of sequential learning. I will maintain my score in favor of accepting the paper.", "rebuttal": "We would like to thank the reviewer for the careful reading and constructive feedback. Below we address each question in turn.\n\n---\n\n**Q1 – GluonTS**\n\nThe example mentioned in line 32 refers to the Exchange Rate dataset from GluonTS [1], which contains daily exchange rates (1990–2016) for eight major currencies (AUD, GBP, CAD, CHF, CNY, JPY, NZD, SGD).\n\nIn this dataset, we observe that even state-of-the-art models — including Transformer-based and probabilistic architectures — offer only marginal improvements over simpler baselines such as DeepAR. This suggests a plateau in forecasting performance despite increasing model complexity.\n\nTo support this observation, we computed Exchange dataset MSE for four models: a naive baseline (which predicts the next value as the previous one), a simple feedforward neural network, DeepAR, and the Temporal Fusion Transformer (TFT) and applied our framework to this dataset. As shown in the table below, the differences in MSE across models are relatively minor. Even the naive model performs comparably to more sophisticated ones, reinforcing the idea that additional architectural complexity does not necessarily translate into meaningful performance gains.\n\nTo obtain the  minimal achievable risk $\\hat{\\mathcal{R}}^{\\infty}(Q^{*}) = \\min_{1 \\leq k \\leq M} \\hat{\\mathcal{R}}^{k}(Q_k) - \\hat{\\Lambda}(k)$, we estimated the learning curve $\\Lambda(k)$.  While our estimator is admittedly noisy and unstable, the results (shown below) suggest that there is little left to learn in this dataset. Indeed, the actual MSE values lie close to this estimated minimal risk, suggesting that the performance ceiling is due less to model limitations than to the intrinsic unpredictability of the data.\n\nThis aligns with the characteristics of the dataset. Unlike many other financial assets, FX rates are driven by the relative economic conditions, monetary policies, and geopolitical factors of two countries, adding significant complexity to their dynamics. This market is also extremely liquid and highly competitive, so any patterns or inefficiencies are quickly detected and eliminated by market participants. These factors contribute to the inherent unpredictability of the dataset.\n\n**Table: Comparison between actual MSE and estimated minimal achievable risk for each model**\n\n| Model| MSE |$\\hat{R}^{\\infty}(Q^*) $|\n|---------------------|------------------------|----------------------------------------------|\n| Naive  | 0.000030 | 0.000021 ± 0.000007 |\n| DeepAR | 0.000018 ± 0.000004| 0.000013 ± 0.000009|\n| Simple FeedForward  | 0.000021 ± 0.000002    | 0.000015 ± 0.000008|\n| TFT | 0.000016 ± 0.000002| 0.000013 ± 0.000011|\n\n---\n**Q2 – Notations**\n\nThank you for pointing this out. We will revise the final version to avoid overloading notation (e.g., $\\mathcal{F}_k$ vs. $F$) and clarify the use of logarithms throughout.\n\n---\n\n**Q3 – Figure 1 legend**\n\nIn the final version, we will clarify that blue regions indicate negative bias (underestimation), and that color intensity reflects the magnitude of this bias.\n\n---\n\n**Q4 – Related work section**\n\nWe are grateful to the reviewer for bringing up the notion of prospective learning, which was not initially part of our analysis, and for pointing us to relevant references. We will incorporate the following discussion into the \"Related Work\" section:\n\nRecent developments in statistical learning theory increasingly emphasize learning in contexts where classical assumptions, such as independent and identically distributed (i.i.d.) samples, no longer hold. In particular, extending traditional frameworks to accommodate stochastic processes with temporal dependencies or evolving distributions has become a critical direction for research. \n[2] directly addresses this by proposing learners that output sequences of hypotheses aimed at minimizing future risk—an approach well-suited for non-stationary settings where the optimal predictor may itself change over time. Complementary to this, [3, 4] offer general characterizations of learnability under arbitrary stochastic processes, framing it in terms of regret minimization or universal consistency, and showing its deep connections with online learning.\nThese frameworks share a common goal: to define when learning is possible in complex, non-i.i.d. environments. However, they primarily rely on external performance criteria—such as risk or regret—without explicitly analyzing the structural properties of the data itself. Our work complements these approaches by introducing an intrinsic, information-theoretic perspective: we characterize learnability in terms of the presence of stable and identifiable patterns within the data-generating process. This allows us to bridge high-level learnability guarantees with the underlying structure of the data, providing new insights into how and why generalization is achievable beyond traditional settings.\n\n---\nWe hope the clarifications above resolve the reviewer’s concerns and further illustrate how our framework complements existing work on sequential learning.  We appreciate the insightful feedback and look forward to refining the final manuscript accordingly.\n\n\n**References**\n\n[1] Alexandrov, A., et al. (2019). *GluonTS: Probabilistic Time Series Modeling in Python*. arXiv preprint arXiv:1906.05264.\n\n[2] De Silva, A., Ramesh, R., Yang, R., Yu, S., Vogelstein, J. T., & Chaudhari, P. (2024). *Prospective Learning: Learning for a Dynamic Future*. arXiv preprint arXiv:2411.00109.\n\n[3] Dawid, A. P., & Tewari, A. (2020). *On learnability under general stochastic processes*. arXiv preprint arXiv:2005.07605.\n\n[4] Hanneke, S. (2021). *Learning whenever learning is possible: Universal learning under general stochastic processes.* Journal of Machine Learning Research, 22(130), 1-116."}, {"review_id": "eBko8FWG5a", "reviewer": "Reviewer_PCUk", "summary": "The paper introduces predictive information \\( I_{\\text{pred}} \\), which measures the mutual information between a length-\\(k\\) past and a length-\\(k'\\) future in sequential data. It generalizes the EvoRate metric from \\(k'=1\\) to arbitrary future block lengths. The authors connect \\( I_{\\text{pred}} \\),  with the concept of a universal learning curve \\( \\Lambda(k) \\), which quantifies the incremental benefit of extending the past window by one step. Theoretically, this allows identifying the optimal context length and estimating the parameter dimension \\(p\\) of the underlying generative process. The method is evaluated on synthetic data, including Gaussian, autoregressive, and Ising processes, to validate its theoretical and empirical utility.", "questions": "Questions:\n\n1. The Gaussian-process study reports results only for the fixed pair \\((k = 5,\\; k' = 10)\\).  How was this setting chosen, and do your conclusions hold for other \\((k,k')\\) combinations?\n\n2. What does the critical zone stand for in the learning-curve plot (Figure 2)?\n\n3. Could you provide the correct reference for the definition of consistency in line 569?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper is very well written and presents a clear theoretical contribution. It offers exhaustive derivations and proofs, and it generalizes EvoRate while drawing a formal connection to information theory through the universal learning curve.\n\nWeaknesses:\n- Limited empirical scope: currently all experiments are performed on synthetic data. No real-world sequential datasets are used to show practical benefit. This makes it hard for me to assess the impact of this work apart from the theoretical work and the mapping of predictive information and information theory. However, it is to note that the authors mention the lack of real-world data experiments as a limitation in the corresponding section.\n\n- Expressiveness of the experiments: Although the chosen synthetic experiments are well designed, it is unclear whether the reported benefits would persist under a wider set of settings, for example, more \\((k,k')\\) combinations in the first experiment, additional \\(p\\) values in the second, or cross-validation splits in the third.\n\n- Reproducibility: for the last experiment using MLP and LSTM the exact model parameter counts are not provided. Including these numbers would make the results easier to reproduce and interpret.", "was_revised": true, "final_justification": "After reading the authors’ detailed rebuttal, I believe they have sufficiently addressed all of my concerns. In particular they extended their experiments by showing results on a real world dataset, adding experimental details and explaining unclear parts of the work. If the commitee sees this work as a sufficiently large increment, I would definitely recommend accepting the paper.", "rebuttal": "We thank the reviewer for their overall positive evaluation and for highlighting both the strengths and limitations of our work. We appreciate the comments regarding empirical scope, experimental coverage, and reproducibility, and we address each of these points below.\n\n**W1 – Limited empirical scope**\n\nIt is true that our paper does not include any experiments on real-world datasets and we understand that it might be challenging to fully assess the impact of our work without those. The primary focus of our work is indeed theoretical, and as you may have seen, the theoretical contributions—particularly the proofs—are already substantial and technically demanding.\n\nWe intentionally chose not to simultaneously tackle the separate and equally challenging problem of experimentally estimating the learning curve and the minimal achievable risk. Indeed, estimating the learning curve is itself a complex theoretical question that warrants dedicated treatment. Addressing it rigorously would require an entirely separate line of work, and we felt that attempting to incorporate this into the current paper would dilute the clarity and focus of our main contributions. For instance, [1] is a full research article dedicated solely to estimating mutual information in sequential settings. Hence, we chose to first address the problem from a theoretical perspective, and plan to tackle the estimation of the learning curve and thus minimal risk in a follow-up article.\n\nThat said, we did include experiments on synthetic data, where the estimation of $\\mathbf{I}_{\\text{pred}}$ is not an issue, since closed-form expressions are available. These experiments serve an illustrative purpose, allowing us to demonstrate the theoretical framework in controlled settings.\n\nNevertheless, we fully acknowledge the reviewers' concern regarding the lack of real-world evaluations. In response, we applied our framework to the Exchange Rate dataset from GluonTS [2], and show how it can be used on a real world dataset. This dataset contains daily exchange rates (1990–2016) for eight major currencies (AUD, GBP, CAD, CHF, CNY, JPY, NZD, SGD). In this case, we show that this dataset is more limited by data itself rather than by model complexity.\n\nWe first computed the MSE for four models: a naive baseline (which predicts the next value as the previous one), a simple feedforward neural network, DeepAR, and the Temporal Fusion Transformer (TFT). The differences in MSE across models are relatively minor. Even the naive model performs comparably to more sophisticated ones, reinforcing the idea that additional architectural complexity does not necessarily translate into meaningful performance gains.\n\nTo obtain the  minimal achievable risk $\\hat{\\mathcal{R}}^{\\infty}(Q^{*}) = \\min_{1 \\leq k \\leq M} \\hat{\\mathcal{R}}^{k}(Q_k) - \\hat{\\Lambda}(k)$, we estimated the learning curve $\\Lambda(k)$.  While our estimator is admittedly noisy and unstable, the results (shown below) suggest that there is little left to learn in this dataset. Indeed, the actual MSE values lie close to this estimated minimal risk, suggesting that the performance ceiling is due less to model limitations than to the intrinsic unpredictability of the data.\n\nThis aligns with the characteristics of the dataset. Unlike many other financial assets, FX rates are driven by the relative economic conditions, monetary policies, and geopolitical factors of two countries, adding significant complexity to their dynamics. This market is also extremely liquid and highly competitive, so any patterns or inefficiencies are quickly detected and eliminated by market participants. These factors contribute to the inherent unpredictability of the dataset.\n\n**Table: Comparison between actual MSE and estimated minimal achievable risk for each model**\n\n| Model| MSE |$\\hat{R}^{\\infty}(Q^*) $|\n|---------------------|------------------------|----------------------------------------------|\n| Naive  | 0.000030 | 0.000021 ± 0.000007 |\n| DeepAR | 0.000018 ± 0.000004| 0.000013 ± 0.000009|\n| Simple FeedForward  | 0.000021 ± 0.000002    | 0.000015 ± 0.000008|\n| TFT | 0.000016 ± 0.000002| 0.000013 ± 0.000011|\n\n---\n\n**W2 – Expressiveness of the experiments**\n\nFor the $(k, k')$ combinations, please refer to our response to **Question 1**.  \nRegarding the second experiment, the results hold consistently across all values of $p$. We chose to report only $p = 5$ and $p = 10$ in the article to maintain clarity and avoid cluttering the figure. \nFor the third experiment, we already included several cross-validation block sizes ( $\\(M = 10^4, 10^5, 10^6, 10^7\\)$ ) to illustrate the robustness of the results across different magnitudes.  That said, our conclusions remain valid for other values of $M$ as well.  We do observe, however, that the estimation of the learning curve $\\Lambda(k)$ becomes less stable when $M \\ll 10^4$, due to higher variance in the empirical estimator of $\\mathbf{I}_{\\text{pred}}$\n\n---\n\n**W3 – Reproducibility (for the last experiment)**\n\nHere are the exact model and training details:\n\n**Model architectures**\n- **MLP**: 2 hidden layers (64, then 32 neurons), ReLU activations, output layer with 2 units (softmax).\n- **LSTM**: Single-layer LSTM (32 hidden units), fully connected layer mapping to 2 output classes.\n\n**Training setup**\n- Adam optimizer (lr = $10^{-3}$)  \n- Batch size = 128  \n- Max epochs = 1000  \n- Early stopping with patience = 10  \n- 50 batches per epoch  \n- 80/20 train-validation split  \n\nWe will explicitly add these details in the final manuscript.\n\n---\n**Q1 – On the fixed pair $(k, k')$**\n\nWe selected the fixed pair $(k, k')$ = $(5, 10)$ based on two main considerations.  \n\nFirst, we needed to satisfy the constraint $k'$ > $k$, and since the rest of the paper focuses on estimating the learning curve $\\Lambda(k)$  we aimed for $k'$ to be sufficiently large to approximate the limit $k' \\to \\infty$.\nSecond, for autoregressive Gaussian processes with order $1$ < d < $20$, we wanted $k$ and $k'$ to be of the same order of magnitude as $d$, which motivated our choice of $k$ = $5$ and $k'$ = $10$. While this choice is somewhat arbitrary, other settings such as $(k, k')$ = $(10, 20)$ would also be valid.\n\nImportantly, our conclusions hold for other combinations. We repeated the first experiment with other $(k, k')$ pairs and observed consistent results. Due to character limits, we report only the results for $(k, k') = (10, 20)$ here, but we can provide additional tables upon request. We had to remove some columns from the original experiment due to space and formatting constraints.\n\n---\n\n**Table: Estimated predictive information $ \\hat{I}_{\\text{pred}}$ across models and GP kernels for $(k, k') = (10,20)$**\n| |AR (d=1)|AR (d=10)|Gaussian (ρ=0.5, d=1)|Gaussian (ρ=0.5, d=10)|Gaussian (ρ=0.8, d=1)|Gaussian (ρ=0.8, d=10)|Local-P (d=1)|Matérn 3/2 (d=1)|Matérn 3/2 (d=10)|Matérn 5/2 (d=1)|Matérn 5/2 (d=10)|Periodic (d=1)|RBF (d=1)|RQ (d=10)|RQ (Extra)|\n|--|--------|---------|----------------------|-----------------------|----------------------|-----------------------|--------------|------------------|-------------------|------------------|-------------------|---------------|---------|----------|-----------|\n|$\\hat{\\mathbf{I}}_{\\text{pred}}\\text{-}\\mathtt{DV}$|0.49|3.08|0.14|1.11|0.51|3.51|4.95|0.60|4.20|0.93|4.94|4.32|3.28|6.29|4.89|\n|$\\hat{\\mathbf{I}}_{\\text{pred}}\\text{-}\\mathtt{NWJ}$|0.50|3.49|0.13|1.24|0.48|3.43|4.13|0.60|3.76|0.94|4.13|4.17|3.59|4.21|4.09|\n|$\\hat{\\mathbf{I}}_{\\text{pred}}\\text{-}\\mathtt{SMILE}$|0.49|3.00|0.14|1.01|0.49|2.85|4.57|0.60|3.07|0.95|2.21|3.66|2.98|1.95|3.76|\n|$\\hat{\\mathbf{I}}_{\\text{pred}}\\text{-}\\mathtt{InfoNCE}$|0.51|3.48|0.14|0.87|0.49|3.78|4.87|0.58|4.48|0.95|6.34|4.24|3.00|9.54|5.01|\n|$\\hat{\\mathbf{I}}_{\\text{pred}}\\text{-}\\mathtt{TUBA}$|0.50|3.27|0.14|1.11|0.49|2.74|4.68|0.60|2.96|0.96|3.34|3.52|3.10|2.97|3.66|\n|$\\hat{\\mathbf{I}}_{\\text{pred}}\\text{-}\\mathtt{TRUE}$|0.51|5.11|0.14|1.44|0.51|5.11|8.57|0.62|6.17|1.00|10.00|12.00|6.34|15.91|7.9|\n\n---\n\n**Q2 – Meaning of the \"critical zone\" in Figure 2**\n\nThe \"critical zone\" represents values of the universal learning curve $\\Lambda(k)$ below a small threshold (here set at $0.02$).\n\nIn practice, estimating $\\Lambda(k)$ doesn't yield exact zeros due to inherent variance. Therefore, choosing precisely the context length $k$ at which the learning curve becomes negligible is challenging.\n\nTo address this, we introduce a practical cutoff—this \"critical zone\"—below which we consider the learning curve effectively zero. In our example, the threshold ($0.02$) was chosen to be small relative to the typical magnitude of $\\Lambda(k)$, yet large enough to account for estimation noise.\n\nWhile somewhat arbitrary, this choice helps clearly identify the region where additional context no longer meaningfully improves predictions.\n\n---\n\n**Q3 – Reference correction (line 569)**\n\nThank you for catching this error. The missing reference is [3].\nWe will correct this citation in the final version.\n\n--- \n\nWe thank the reviewer again for their constructive feedback. We believe the clarifications above, as well as the new real-world experiment on the Exchange Rate dataset, help to address the concerns raised regarding empirical scope and reproducibility.\n\n**References**\n\n[1] Zeng, Q., Huang, L.-K., Chen, Q., Ling, C. X., & Wang, B. (2025). *Towards Understanding Evolving Patterns in Sequential Data*. Advances in Neural Information Processing Systems.\n\n[2] Alexandrov, A., et al. (2019). *GluonTS: Probabilistic Time Series Modeling in Python*. arXiv preprint arXiv:1906.05264.\n\n[3] Kallenberg, O. (2002). *Foundations of Modern Probability*. Springer."}, {"review_id": "thyblJkHRt", "reviewer": "Reviewer_sHAW", "summary": "The paper addresses two questions:\n1. What are the minimum achievable risks for any predictor intending to model sequential data?\n2. Can the error be attributed to predictor limitation or unpredictability of the sequential data?\n\nIn the context of stationary processes, the authors consider the mutual information between the past and the future with increasing window size to derive lower bounds for the minimal achievable risks and highlight patterns' impact on learnability. Theoretical results have been highlighted with empirical experiments on synthetic", "questions": "- Regarding the additional remarks on Result Interpretability, would it be possible to illustrate corollary 4.4 with a plot showing the asymptotic consistency of the dimension estimator?\n- Link to the first question: The window size is closely linked to the parameter space dimension for the autoregressive model. Assuming a large window size, would it be possible to estimate the window size from smaller windows?", "limitations": "Limitations are raised in my questions and weaknesses.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is well-motivated and written. The theoretical framework is well described, and several intuitions are provided, giving a good understanding of the framework's usability.\n- Applying the framework to the case of Markovian and parametric processes seems promising, as the estimation of the proper window length or parameter space remains challenging in practice.\n- Appendices are well-detailed, complementing both the theoretical section with proofs and the experimental section with detailed results and implementation, easing reproducibility.\n\nWeaknesses:\n- While not central to this paper, an illustration of the framework on real-world data would benefit the overall comprehension and paper motivation.\n- The paper could also benefit from a summary answering the two introductory questions with the framework as partially done in the theoretical and experimental parts.", "was_revised": true, "final_justification": "I thank the authors for their thorough and clear responses. They have addressed my concerns and provided additional experiments. The paper is easy to follow, and the inclusion of an additional real-world experiment further clarifies the practical usability of the proposed framework. I maintain my score in support of this paper.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. We appreciate the positive assessment of our contributions, as well as the valuable questions and concerns raised. We address them point by point below.\n\n**W1 – Illustration on real-world dataset**\n\nWe acknowledge that our work could benefit from an application on a real world dataset.  But the primary focus of our work is theoretical, and as you may have seen, the theoretical contributions—particularly the proofs—are already substantial and technically demanding.\n\nWe intentionally chose not to simultaneously tackle the separate and equally challenging problem of experimentally estimating the learning curve and the minimal achievable risk. Indeed, estimating the learning curve is itself a complex theoretical question that warrants dedicated treatment. Addressing it rigorously would require an entirely separate line of work, and we felt that attempting to incorporate this into the current paper would dilute the clarity and focus of our main contributions. \n\nNevertheless, we agree with the reviewer that a real world application could benefit the overall comprehension of this article. Thus, we applied our estimator of $\\mathbf{I}_{\\text{pred}}$ to the Exchange Rate dataset from GluonTS [1], in order to assess how much predictive information remains in that data. This dataset contains daily exchange rates (1990–2016) for eight major currencies (AUD, GBP, CAD, CHF, CNY, JPY, NZD, SGD).\n\nWe first computed the Mean Squared Error (MSE) for four models: a naive baseline (which predicts the next value as the previous one), a simple feedforward neural network, DeepAR, and the Temporal Fusion Transformer (TFT). The differences in MSE across models are relatively minor. Even the naive model performs comparably to more sophisticated ones, reinforcing the idea that additional architectural complexity does not necessarily translate into meaningful performance gains.\n\nTo better understand this plateau, we estimated the learning curve $\\Lambda(k)$. This curve is approximately flat and close to zero (see table). While our estimator is admittedly noisy and unstable, the results (shown below) suggest that there is little left to learn in this dataset.\n\nWe then computed the minimal achievable risk using:\n$\\hat{\\mathcal{R}}^{\\infty}(Q^{\\*}) = \\min_{1 \\leq k \\leq M} \\hat{\\mathcal{R}}^{k}(Q_k) - \\hat{\\Lambda}(k) $.\n\nInterestingly, the actual MSE values lie close to this estimated bound, suggesting that the performance ceiling is due less to model limitations than to the intrinsic unpredictability of the data.This aligns with the characteristics of the dataset. Unlike many other financial assets, FX rates are driven by the relative economic conditions, monetary policies, and geopolitical factors of two countries, adding significant complexity to their dynamics. \n\n**Table: Comparison between actual MSE and estimated minimal achievable risk for each model**\n\n| Model| MSE |$\\hat{R}^{\\infty}(Q^*) $|\n|---------------------|------------------------|----------------------------------------------|\n| Naive  | 0.000030 | 0.000021 ± 0.000007 |\n| DeepAR | 0.000018 ± 0.000004| 0.000013 ± 0.000009|\n| Simple FeedForward  | 0.000021 ± 0.000002    | 0.000015 ± 0.000008|\n| TFT | 0.000016 ± 0.000002| 0.000013 ± 0.000011|\n---\n\n**W2 – Summary of Contributions**\n\nThis work addresses two fundamental questions in sequential modeling:\n\n1. **What is the minimal achievable risk when modeling sequential data?**  \n2. **Is poor predictive performance due to model limitations or to the intrinsic unpredictability of the data?**\n\nTo address these questions, we introduce a practical framework grounded in information theory. A central element of this framework is the learning curve $\\Lambda(k)$, which captures the improvement in predictive accuracy when the context length increases from $k$ to $k+1$. This measure is derived from the predictive information $I_{\\text{pred}}(k, k')$ (defined as the mutual information between a block of $k$ past observations and a block of $k'$ future observations ) through this formula :\n\n$\\Lambda(k) = \\lim_{k' \\to \\infty} \\left[ I_{\\text{pred}}(k+1, k') - I_{\\text{pred}}(k, k') \\right]$\n\nUsing this quantity, we introduce an estimator of  the *minimal achievable risk* — the lowest possible prediction error attainable by any model — through a bound involving the $k$-order forecasting risk. This estimator is defined as follows:\n\n$\\hat{\\mathcal{R}}^{\\infty}(Q^{*}) = \\min_{1 \\leq k \\leq M} \\hat{\\mathcal{R}}^{k}(Q_k) - \\hat{\\Lambda}(k)$, \n\nwhere $\\hat{\\mathcal{R}}^k(Q)$ is the empirical risk of a model $Q$ using a context of length $k$.\n\nThis leads to a simple yet effective diagnostic tool to address the second question: is poor performance due to model limitations or to the data itself? If the actual model risk $\\hat{\\mathcal{R}}^k(Q)$ is close to the estimated minimal risk $\\hat{\\mathcal{R}}^\\infty(Q^*)$, it indicates that either the data contains little predictive structure or that this structure has already been captured—suggesting that increasing model complexity is unlikely to yield better results. Conversely, a substantial gap between these two quantities signals that the model could be missing exploitable patterns in the data, pointing to potential model improvements.\n\n---\n**Q1 - Corollary 4.4 Illustration**\n\nDue to recent NeurIPS policies, we are unfortunately unable to include new plots during the rebuttal period. However, we performed additional experiments to validate Corollary 4.4 using a concrete example that illustrates the asymptotic consistency of our dimension estimator.\n\nFor this additional illustration, we follow the same setup as the experiment in **Section 5.3**, which is based on the Ising spin sequence example from [2]. We generated a sequence of $10^9$ samples with block size $M = 400{,}000$, and computed the learning curve up to $k = 20$. We restricted the analysis to $k \\leq 20$ since $2^{20} \\approx 10^6$ corresponds to the number of distinct words of length 20; beyond this point, entropy estimation $S(20)$ - via empirical frequencies - becomes unreliable due to insufficient sampling.\n\nThe table below reports the values of our dimension estimator defined as $\\hat{p}(k) = 2k \\cdot \\hat{\\Lambda}(k)$ :\n\n| $k$|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|\n|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|\n| $\\hat{p}(k)$|0.647|0.840|0.894|0.907|0.992|1.048|1.061|1.063|1.073|1.083|1.084|1.084|1.082|1.079|1.075|1.069|1.062|1.053|1.039|1.016|\n\nThis clearly shows that our estimator converges to the real dimension p = 1.\n\n[1] provides both theoretical and empirical support for this behavior. In particular, they show that $\\hat{p}(n) = 2n \\cdot \\Lambda(n) = p - \\frac{1}{2n} + o\\left(\\frac{1}{n}\\right)$, confirming that our estimator is consistent and can be used to estimate dimension of parameters, with convergence rate $(1/n)$.\n\n---\n\n**Q2 - Estimating the true window size (model order) from small windows**\n\nLet us first restate the question to ensure we have understood it correctly.  \n\nGiven an autoregressive (AR) process of order $p$, **Proposition 4.2** in our paper shows that the learning curve $\\Lambda(k)$ becomes exactly zero for all $k \\geq p$. The reviewer asks whether it is possible to estimate this value of $p$ without having to compute $\\Lambda(k)$ for all values up to $p$—in particular, using only small window sizes $k \\ll p$.\n\nWe propose a simple extrapolation-based method to approximate $p$ from a small number of evaluations. The learning curve $\\Lambda(k)$ is decreasing and converges to zero, and under mild conditions—such as for Gaussian AR processes—it is also convex. We exploit this structure by computing $\\Lambda(k)$ for $k = 1, \\dots, M$, where $M$ is a user-defined limit, and fitting a simple parametric function such as a rational function $f(k) = a / (k + b)$ or an exponential decay. These function classes are chosen to reflect the smooth and typically convex decay of $\\Lambda(k)$ as stated in [2]. Once the function is fitted, we define an estimator $\\hat{p}$ as the first $k$for which $f(k) < \\Lambda(1)/N$, with $N$ another tunable parameter controlling tolerance.\n\nTo demonstrate this approach, we extended the experiment from **Section 5.2** of our paper. We generate a 5-dimensional Gaussian AR process with autoregressive coefficient $\\rho = 0.9 $, and vary the true order $p $. We evaluate $\\Lambda(k)$ for $k = 1$ to $10 $, fit the rational function $f(k)$, and estimate $\\hat{p}$ as above with $M=10$ and $N = 10$. Results are summarized below:\n\n|$p$|10|50|100|500|1000|\n|---|---|---|---|---|---|\n|$\\hat{p}$|10±0|51±3|98±5|459±18|811±49|\n\nThis method achieves surprisingly accurate estimates, even for large values of $p$, despite using only the first 10 points of the learning curve. Of course, extrapolation becomes harder as $p$ grows, but the approach remains effective and tunable: one can adjust the number of observed points $M$, the threshold $N$, or the fitting function class to balance cost and precision.\n\nAs an alternative, one could also apply a root-finding method (e.g., Newton’s method) to estimate where $\\Lambda(k) \\approx 0$. While such techniques may reduce the number of required evaluations, they still require accessing large $k$-values close to $p$, limiting their practical gain in high-order regimes.\n\nWe thank the reviewer for this insightful question. These techniques may also prove useful in real-world applications where the learning curve is currently estimated via predictive information. Leveraging extrapolation strategies like the one discussed here could help refine learning curve estimation directly, beyond mutual information bounds.\n\n ---\n\n**References**\n\n[1] Alexandrov, A., et al. (2019). *GluonTS: Probabilistic Time Series Modeling in Python*. arXiv preprint arXiv:1906.05264.\n\n[2] Bialek, W., Nemenman, I., & Tishby, N. (2001). *Predictability, complexity, and learning*."}, {"review_id": "vbtib5FZwJ", "reviewer": "Reviewer_BK66", "summary": "This paper proposes a theoretically grounded and general framework for understanding the learnability of sequential data using predictive information—the mutual information between the past and the future. It formalizes the concept of an information-theoretic learning curve (via the universal learning curve, Λ(k)) and connects it to fundamental limits on forecasting performance. Building on prior work like EvoRate, the authors extend the analysis by defining a minimal achievable risk, offering new diagnostic tools for model adequacy. Theoretical contributions are complemented by experiments on synthetic datasets, including autoregressive and Ising processes, validating the proposed framework’s ability to detect learnability bounds and optimal regression orders.", "questions": "See above.", "limitations": "See above.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\t1.\tStrong Theoretical Foundations:\nThe authors rigorously establish the link between predictive information and learnability, grounding their framework in information theory and learning theory. This includes closed-form results for Markov processes, asymptotic expansions for parametric families, and connections to Bayesian learning theory (e.g., Corollary 4.4 on dimensionality estimation).\n\t2.\tConceptual Clarity:\nThe paper provides intuitive examples (e.g., lunch meal prediction) to motivate its central question—whether poor forecasting performance arises from data limitations or model inadequacies.\n\t3.\tSound Use of Information-Theoretic Tools:\nThe authors successfully extend EvoRate into a more general predictive information metric that connects to the universal learning curve. This supports robust interpretations of structure in data and connects theory with empirical forecasting tasks.\n\t4.\tSynthetic Experiments:\nThe experiments validate the theory by showing that the proposed estimator Λ(k) tracks ground-truth model orders and minimum risk accurately in controlled settings.\n\n⸻\n\nWeaknesses:\n\t1.\tEmpirical Evaluation Scope:\nThe experiments are performed entirely on synthetic datasets—autoregressive Gaussian processes and Ising spin chains. While these are useful for validation, they fall short of demonstrating the framework’s practical utility on real-world data (e.g., NLP or financial sequences), which the paper itself acknowledges as a limitation.\n\t2.\tEstimation Stability:\nThe authors note estimation variance and occasional instability of the Ipred estimators in high dimensions or near low-complexity regimes. This potentially limits the utility of the learning curve in real settings unless estimation is improved.\n\t3.\tModel Dependency of the Estimator:\nThe proposed estimator of minimal achievable risk is model-dependent, which contrasts with EvoRate’s model-free nature. While this allows diagnostic comparisons, it introduces potential confounds related to model capacity and training variability.\n\t4.\tInterpretability vs. Accessibility:\nWhile the theoretical depth is commendable, some derivations and notations—though well-supported in the appendix—could be inaccessible to readers not well-versed in information theory or statistical learning, potentially limiting broader appeal.\n\nOverall Evaluation:\n\nThe paper is clearly written, well-structured, and theoretically sound. It presents a significant conceptual advance over EvoRate by offering a quantitative and theoretically justified estimator of the fundamental limits of learnability. While the theory is solid, I cannot fully assess its novelty in the context of the most recent literature on predictive information estimation and sequential risk bounds. As someone less familiar with the deep technical nuances of the information-theoretic theory presented, I found the framework persuasive, but dense.\n\nThe empirical component appears somewhat underwhelming compared to the strength of the theoretical contribution. It may be that synthetic validation is standard in this line of work, but the lack of any real-world application or benchmark comparison makes it hard to assess its broader utility.", "was_revised": true, "final_justification": "While the authors' rebuttal was good, I don't feel confident increasing my original score.", "rebuttal": "We are grateful to the reviewer for the valuable feedback and recommendations.\nWe provide here a detailed answer to the weaknesses and questions.\n\n**W1 – Real world dataset**\n \nWe understand that the empirical part of the paper may appear modest relative to the theoretical contribution, which can make evaluating its practical relevance more challenging.\nHowever, the primary focus of our work is indeed theoretical, and as you may have seen, the theoretical contributions—particularly the proofs—are already substantial and technically demanding.\n\nWe intentionally chose not to simultaneously tackle the separate and equally challenging problem of experimentally estimating the learning curve and the minimal achievable risk. Indeed, estimating the learning curve is itself a complex theoretical question that warrants dedicated treatment. Addressing it rigorously would require an entirely separate line of work, and we felt that attempting to incorporate this into the current paper would dilute the clarity and focus of our main contributions. For instance, [1] is a full research article dedicated solely to estimating mutual information in sequential settings. Hence, we chose to first address the problem from a theoretical perspective, and plan to tackle the estimation of the learning curve and thus minimal risk in a follow-up article.\n\nThat said, we did include experiments on synthetic data, where the estimation of $\\mathbf{I}_{\\text{pred}}$ is not an issue, since closed-form expressions are available. These experiments serve an illustrative purpose, allowing us to demonstrate the theoretical framework in controlled settings.\n\nNevertheless, we fully acknowledge the reviewers' concern regarding the lack of real-world evaluations. In response, we applied our framework to the Exchange Rate dataset from GluonTS [2], and show how it can be used on a real world dataset. This dataset contains daily exchange rates (1990–2016) for eight major currencies (AUD, GBP, CAD, CHF, CNY, JPY, NZD, SGD). In this case, we show that this dataset is more limited by data itself rather than by model complexity.\n\nWe first computed the MSE for four models: a naive baseline (which predicts the next value as the previous one), a simple feedforward neural network, DeepAR, and the Temporal Fusion Transformer (TFT). The differences in MSE across models are relatively minor. Even the naive model performs comparably to more sophisticated ones, reinforcing the idea that additional architectural complexity does not necessarily translate into meaningful performance gains.\n\nTo obtain the  minimal achievable risk $\\hat{\\mathcal{R}}^{\\infty}(Q^{*}) = \\min_{1 \\leq k \\leq M} \\hat{\\mathcal{R}}^{k}(Q_k) - \\hat{\\Lambda}(k)$, we estimated the learning curve $\\Lambda(k)$.  While our estimator is admittedly noisy and unstable, the results (shown below) suggest that there is little left to learn in this dataset. Indeed, the actual MSE values lie close to this estimated minimal risk, suggesting that the performance ceiling is due less to model limitations than to the intrinsic unpredictability of the data.\n\nThis aligns with the characteristics of the dataset. Unlike many other financial assets, FX rates are driven by the relative economic conditions, monetary policies, and geopolitical factors of two countries, adding significant complexity to their dynamics. This market is also extremely liquid and highly competitive, so any patterns or inefficiencies are quickly detected and eliminated by market participants. These factors contribute to the inherent unpredictability of the dataset.\n\n**Table: Comparison between actual MSE and estimated minimal achievable risk for each model**\n\n| Model| MSE |$\\hat{R}^{\\infty}(Q^*) $|\n|---------------------|------------------------|----------------------------------------------|\n| Naive  | 0.000030 | 0.000021 ± 0.000007 |\n| DeepAR | 0.000018 ± 0.000004| 0.000013 ± 0.000009|\n| Simple FeedForward  | 0.000021 ± 0.000002    | 0.000015 ± 0.000008|\n| TFT | 0.000016 ± 0.000002| 0.000013 ± 0.000011|\n\n---\n**W2 – Estimation Stability**\n\nIndeed, as noted above, estimating predictive information in practice is a difficult task—particularly in high-dimensional settings or when the underlying data has weak temporal structure. Our main objective in this work, however, is not to develop a definitive estimator of $\\mathbf{I}_{\\text{pred}}$, but to provide a theoretical characterization of the limits of learnability from an information-theoretic perspective. We believe that a rigorous and robust estimation procedure for the predictive information is an important and challenging problem in its own right, and we see it as a promising direction for future work.\n\nIt is also worth emphasizing that estimating mutual information in sequential settings is a relatively recent and evolving research area—[1] , for instance, was one of the first works to directly address this. While our current estimator is admittedly imperfect, it already yields valuable insights in real-world scenarios, as demonstrated in our experiments on both synthetic and real world datasets.\nMoreover, our theoretical results suggest new avenues for improving estimation techniques. For example, instead of estimating $\\mathbf{I}_{\\text{pred}}$ directly, one might focus on estimating the learning curve $\\Lambda(k)$, which could offer a more stable and interpretable alternative. We view our contribution as laying the groundwork for such future developments.\n\n---\n\n**W3 – Model Dependency of the Estimator**\n\nWe thank the reviewer for this important point. It is true that our estimator of the minimal achievable risk is model-dependent, in contrast to $\\texttt{EvoRate}$ 's model-free approach in [1]. However, we believe that this dependency is not necessarily a limitation, but rather reflects the different purpose of our framework. While EvoRate focuses on detecting the presence of temporal structure, our aim is to quantify how much of that structure is actually being captured by a given model class.\n\nThe core quantity of interest in our framework—the learning curve $ \\Lambda(k) $—is itself model-independent and provides richer information than EvoRate, as it reflects the data’s intrinsic predictability across context lengths. The connection we draw to model-specific risk should be seen as an added benefit: it enables one to assess the current state of modeling capabilities on a given dataset, and to determine whether improvements are more likely to come from better models or whether the data has already been exhaustively exploited.\n\nImportantly, in our experiments, we observed that the estimated minimal achievable risk is generally stable across different architectures. This suggests that our diagnostic remains robust despite being evaluated within specific model classes.\n\n---\n\n**W4 – Interpretability vs. Accessibility**\n\nWe appreciate the reviewer’s concern regarding the accessibility of the theoretical content and recognize that the paper is conceptually dense. To address this, we deliberately included intuitive illustrations—such as the lunch meal prediction scenario in the introduction—to ground the theoretical framework in concrete terms. We also designed empirical experiments, including one on a real-world dataset, to directly support and illustrate our theoretical claims. We began with synthetic data precisely because it offers controlled settings where expected behaviors are known, making the theory more digestible for the reader. Additionally, we will revise and clarify some derivations and reinforce the connection between theory and experiments in the final version of the article to further improve interpretability.\n\n---\n\nWe hope we have adequately addressed the reviewer’s questions and concerns regarding this paper.\n\n\n**References**\n\n[1] Zeng, Q., Huang, L.-K., Chen, Q., Ling, C. X., & Wang, B. (2025). *Towards Understanding Evolving Patterns in Sequential Data*. Advances in Neural Information Processing Systems.\n\n[2] Alexandrov, A., et al. (2019). *GluonTS: Probabilistic Time Series Modeling in Python*. arXiv preprint arXiv:1906.05264."}]

Author rebuttal:

Meta-review: This paper proposes an interesting predictive information framework for quantifying the learnability in sequential data. Specifically,  the authors  formalize this by using the predictive mutual information between the past $k$ and the future $k'$ observations, as well as the   connection with the universal learning curve Λ(k). The theoretical contributions based on the empirical risk are interesting,  while synthetic datasets, e.g. in Gaussian processes, show the ability to detect optimal autoregressive orders.

All reviewers agree that this is a strong submission that provides an rigorous information theoretic method to quantity
learnability in sequential data settings and do Markov order selection.
Decision: Accept (poster)