PaperlayerView exact revision on arXiv

Source-linked AI summary

Generative sequence modeling for infinite memory processes via predictive states

Michael Wieck-Sosa, Cosma Rohilla Shalizi

arXiv:2609.38524v1stat.MLcs.LGstat.ME

TL;DR

Estimating one-step-ahead conditional distributions is challenging when structural assumptions are unsuitable for processes with long-range nonlinear interactions. The paper models history through predictive states and develops an estimator with fast-rate guarantees when those states are low-dimensional. This provides a predictive-state approach to sequence modeling, with exogenous-covariate extensions left for future work.

  • Problem

    Estimating one-step-ahead conditional distributions is challenging without structural assumptions such as additivity or sparsity, which can be poorly suited to long-range nonlinear interactions.

    Source: §1 · p. 1

  • Method

    The method recursively represents history with predictive states and estimates the next-step distribution using conditional expectations of random features from a finite future block.

    Source: §2.1 · p. 2, §2.2 · p. 3

  • Results

    The analysis shows that fast convergence rates are achievable when the predictive state space is low-dimensional.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The one-step prediction task supports learning the predictive distribution of the whole future, relevant to forecasting, optimization, and control.

    Source: §1 · p. 1

    The model leaves extensions to include exogenous covariates for future work.

    Source: §2.1 · p. 2

Abstract

from arXiv · show

We consider estimating the one-step-ahead conditional distribution of a multivariate stochastic process. Many existing approaches rely on assumptions such as finite-range memory, sparsity, or additivity, which can be poorly suited to processes with long-range nonlinear interactions. However, without such structural assumptions, nonparametric estimation is challenging due to the curse of dimensionality. To address this challenge, we introduce a new estimation approach based on the predictive states of a process, possibly with infinite-range memory. We show that our estimator achieves fast convergence rates when the past history can be compressed into a low-dimensional statistic that is sufficient for predicting the future. Specifically, we show that the statistical complexity of the estimation problem is determined by the intrinsic dimension of the predictive state space. We establish guarantees for an instantiation of our method based on deep neural network estimators, and we support these theoretical results with experiments.

1 INTRODUCTION

The paper targets one-step-ahead conditional distribution estimation and proposes predictive states as a route to fast rates when history compresses to a low-dimensional sufficient statistic. Its contributions establish predictive sufficiency, identify states through finite future blocks, and analyze neural-network estimators.

1 INTRODUCTION

  • One-step-ahead conditional distribution estimation matters for multi-step forecasting, optimization, and control because success lets us learn the predictive distribution for the whole future.Source: §1 · p. 1
  • Fast convergence rates are achievable when the predictive state space is low-dimensional, offering an alternative to additivity, sparsity, low intrinsic dimensionality, and hierarchical compositionality assumptions.The estimator targets the one-step-ahead conditional distribution.Source: §1 · p. 1

1.1 OUR CONTRIBUTIONS

  • Predictive states are sufficient for the whole future, and any recursively updated one-step-ahead predictively sufficient predictor is also sufficient for the whole future.Source: §1.1 · p. 1
  • Conditional expectations of 2p + 1 random Fourier features of a finite future block identify p-dimensional predictive states and the one-step-ahead conditional distribution.Source: §1.1 · p. 2
  • The RNN and MDN estimator analyses establish fast-rate guarantees for low-dimensional predictive states, and synthetic experiments support the theoretical findings.The paper also extends MDN guarantees to possibly low-intrinsic-dimensional covariates in β-mixing processes.Source: §1.1 · p. 2

2 METHODS AND MAIN IDEAS

The method represents history by recursively updated predictive states, embeds those states through conditional expectations of random features, and estimates the next-step distribution from the resulting features. Under stated identification conditions, the one-step model can be iterated for multi-step sequence generation.

2.1 PROBABILISTIC SEQUENCE MODEL

  • The process model generates each observation from latent noise and a recursively updated state that summarizes the entire past; it includes nonlinear infinite-range-memory and finite-order Markov processes.The model leaves extensions to exogenous covariates for future work.Source: §2.1 · p. 2
  • Because the predictive state is recursively updated and sufficient, multi-step generation reduces to characterizing one-step conditional distributions given the state.The displayed factorization writes the horizon-L future law as iterated state-conditioned one-step kernels.Source: §2.1 · p. 2

2.2 DYNAMIC EMBEDDINGS OF PREDICTIVE STATES

  • The method embeds predictive states using conditional expectations of test functions applied to finite future blocks; distinct states must yield distinct block distributions.The block length m must be large enough for identification, and the sample size must satisfy n > 2m + 1.Source: §2.2 · p. 3
  • Identification assumes a compact semialgebraic state space, distinct future-block distributions for distinct states, and a jointly real-analytic extension of the feature map.Source: §2.2 · p. 3
  • With k ≥ 2p + 1 random Fourier features, the embedding is one-to-one almost surely, and Theorem 3 establishes that conditioning on the embedding yields the same conditional distribution as conditioning on the state.Source: §2.2 · p. 4

2.3 GENERATIVE SEQUENCE MODELING

  • Algorithm 1 estimates conditional expectations to obtain the embedded states, then fits a conditional distribution estimator using those estimates and the next observations.The feature count, block length, and estimator hyperparameters are selected jointly by optimizing a criterion.Source: §2.3 · p. 4
  • The framework also supports estimating arbitrary-horizon conditional quantiles, risk functionals, and utilities of action sequences.Source: §2.3 · p. 4

3 THEORY

The theory analyzes predictive-state conditional-distribution estimation through RNN and MDN estimators, deriving convergence guarantees under specified conditions.

3 THEORY

  • The theory uses an RNN and MDN as a concrete instantiation, while allowing other estimators to be used with the method.Source: §3 · p. 4

3.1 RECURRENT NEURAL NETWORK ESTIMATOR

  • The RNN estimator uses a recursive state update and a neural-network function class, with a smoothness condition on the target function.Source: §3.1 · pp. 4–5

3.2 MIXTURE DENSITY NETWORK ESTIMATOR

  • The MDN estimates the conditional density through coordinate-wise conditional factors using the learned predictive-state representation and preceding coordinates.Source: §3.2 · pp. 6–7

3.3 STATIONARITY AND TEMPORAL DEPENDENCE

  • Consistency of the RNN and MDN estimators is established under a stationary, exponentially β-mixing process assumption.Source: §3.3 · p. 8

3.4 MAIN THEORETICAL RESULT

  • Theorem 4 gives a convergence rate for the one-step conditional-density estimator under Assumptions 1–11 and specified RNN and MDN network choices.The theorem requires at least 2p + 1 random Fourier features and specifies network-width and depth conditions.Source: §3.4 · p. 8
  • Theorem 4 evaluates the estimator at the true predictive-state embedding, whereas practical use evaluates it at the learned representation.Source: §3.4 · p. 9
  • Theorem 5 considers fixed-horizon predictions formed by continuing the fitted RNN with observed inputs, under a high-level RNN error condition.The recurrence is continued through step n + L − 1 without refitting.Source: §3.4 · p. 9
  • When Λn is O(1), the estimation error converges to zero in probability.Source: §3.4 · p. 9

4 EXPERIMENTS

The experiments compare the proposed estimator with an MDN using a lag window that grows with sample size. Across 100 replications, the method performs comparably to that baseline.

4 EXPERIMENTS

  • The MDN baseline uses a lag window whose largest possible lag grows with sample size to accommodate infinite-range memory.The method is implemented in PyTorch.Source: §4 · p. 9
  • The experiments use three-dimensional processes and truncated-normal conditional distributions supported on [−2.5, 2.5]^d.The stated dimensions are r = p = d = 3.Source: §4 · p. 9
  • The method performs comparably to an MDN with a growing lag window across 100 replications.The comparison measures L2 distance by sample size.Source: Figure 1 · p. 9, §4 · p. 9

5 CONCLUSION AND FUTURE WORK

The paper presents predictive-state sequence modeling and its convergence-rate results, while outlining possible language-modeling applications. It also describes related work, conditional-functional estimation, and research transparency statements.

5 CONCLUSION AND FUTURE WORK

  • The paper introduces a predictive-state generative sequence framework and derives convergence rates, with fast rates achievable for low-dimensional predictive states.The authors identify language modeling as a possible direction for future work.Source: §5 · p. 9

AI USE STATEMENT

  • Generative AI assisted with literature search, brainstorming, editing, proof checking, software and experiment suggestions, and figure code; the authors reviewed the resulting content.The statement says AI did not draft paper sections or formulate the mathematical claims.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

  • The authors state that the work involves no human subjects or sensitive-data collection and declare no conflicts of interest.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

  • The authors say proofs and additional results are in the appendix and that code will be made available upon acceptance and to reviewers during review.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 RELATED WORK

  • Earlier predictive-state work includes computational mechanics and function-learning methods, while this paper adapts predictive states to generative sequence modeling.The authors distinguish their focus from causal states and replace user-chosen sufficient features with random-feature probes.Source: §A.1 · pp. 13–14

A.2 CONDITIONAL FUNCTIONAL ESTIMATION

  • Algorithm 2 estimates conditional functionals by simulating future observations from fitted estimators and aggregating the resulting functional estimates.The paper defers theory and experiments for this procedure to a separate manuscript.Source: §A.2 · p. 14

A.3 DISCUSSION OF RECURRENT NEURAL NETWORK ARCHITECTURE

The appendix explains how the RNN transforms inputs and hidden states into outputs, then collects mathematical preliminaries used elsewhere in the paper.

A.3 DISCUSSION OF RECURRENT NEURAL NETWORK ARCHITECTURE

  • At each step, a DNN transforms the input, combines it with a linear transformation of the current hidden state through shifted ReLU, and another DNN maps the next state to output.The input is (X_{t−m:t}, Y_{t−m}); the hidden-state transformation is W_h H_t.Source: §A.3 · p. 14

B PRELIMINARIES

  • The preliminaries define σ-subanalytic sets and functions and state closure properties under countable unions and linear projections.The appendix also points to a figure summarizing relationships among classes of sets and functions.Source: B PRELIMINARIES · pp. 14–15
  • A finite-witness result uses 2D + 1 parameter values to characterize the same equality set as requiring equality for every parameter in W.The stated setting assumes σ-subanalytic sets and functions.Source: B PRELIMINARIES · p. 16
  • The preliminaries state that characteristic functions uniquely determine distributions and that a continuous one-to-one map from a compact metric space has a continuous inverse.Source: B PRELIMINARIES · p. 16

C ADDITIONAL RESULTS

The additional results extend MDN guarantees to covariates with lower-dimensional support and establish strong predictive sufficiency for the paper’s predictive-state model.

C.1 MIXTURE DENSITY NETWORK

  • The MDN guarantee is extended to covariates with lower-dimensional support, as needed when predictive-state embeddings lie in Φ(S) ⊂ R^k while S has Hausdorff dimension p.The setting does not assume the embedded covariates are absolutely continuous with respect to Lebesgue measure.Source: §C.1 · p. 17
  • Theorem 6 supplies oracle conditional joint-density estimators under Assumptions 3, 7, 9, and 11, with function classes satisfying Assumption 8.Source: §C.1 · p. 17

C.2 PREDICTIVE STATES

  • The predictive-state result generalizes a result of Shalizi and Crutchfield from discrete measurable spaces to standard Borel spaces.Source: §C.2 · p. 18
  • In the stated model, the predictive states have strong predictive sufficiency: the next observation is conditionally independent of the entire past given the state.The model defines the state recursively from the previous state and current observation, and as a reduction of the history.Source: §C.2 · p. 18

D.1 PROOF OF THEOREM 6

The proof of Theorem 6 establishes a joint conditional-density bound by controlling the coordinate estimators and combining them through conditional-density factorization. It first develops oracle-loss, approximation, and concentration arguments for independent observations, then extends them to dependent observations using β-mixing and block coupling.

Proof structure

  • The proof is organized into three main steps; Step 1 temporarily treats observations as independent, with the dependent-observation extension deferred to Step 2.The proof structure follows Zhou et al. (2023).Source: §D.1 · pp. 18–19

Step 1.1

  • The proof first derives upper and lower oracle-loss bounds using a path between the true conditional density and a candidate density, with Taylor expansion and density normalization.The path interpolates between the two densities; the argument uses that both integrate to one.Source: §D.1 · pp. 19–20

Step 1.2.1

  • Under Assumption 7, the conditional density is approximated by a Gaussian mixture whose weights, means, and scales are smooth functions of a (k + j − 1)-dimensional input.The proof applies a DNN approximation result to those functions, clips mean and scale approximations to the Assumption 8 ranges, and constructs an approximating mixture density.Source: §D.1 · pp. 20–21

Step 1.2.2

  • The resulting MDN parameter count is bounded by a constant times n^((k+j−1)/(2γ+k+j−1)) log(nMj), as required by Assumption 8.The construction uses three networks per mixture component for its weight, mean, and scale functions.Source: §D.1 · p. 23

Step 1.3.3–1.3.4

  • The excerpts identify ReLU DNN metric entropy, upper-bound the function class’s pseudo-VC dimension, and justify population-to-empirical norm comparison under stated conditions with probability at least 1−2e^-r̃.Source: §D.1 · p. 26

Step 2.2–2.3

  • Berbee coupling partitions the β-mixing process into blocks of length order log n, producing independent even- and odd-block subsequences for concentration arguments.Each subsequence contains order n/log n complete blocks; fewer than 2 blocks of leftover observations contribute O(log n/n) to the average.Source: §D.1 · pp. 28–30

Step 2.4

  • For each j in [d], the conditional density estimator’s convergence bound follows by combining previous bounds and recursively improving r0,j, holding with probability at least 1−O(n^-1).Source: §D.1 · pp. 30–31

Step 3

  • The coordinatewise bounds combine into the joint conditional-density bound with probability at least 1−O(n^-1), using fixed dimension, bounded densities, and compact support.The proof uses the factorization of the true conditional density, a telescoping product identity, and a union bound across coordinates.Source: §D.1 · pp. 31–32

D.2 PROOF OF THEOREM 7

The proof establishes predictive sufficiency for every finite future horizon by induction, then extends it to the infinite future using a monotone-class argument. It concludes that conditioning on the predictive state gives the same future-event probabilities as conditioning on the full past.

Step 1

  • Induction extends one-step predictive sufficiency to every finite future horizon, using the recursive update of the state from the current state and intervening observations.The proof then obtains the finite-horizon equality for events involving the future block.Source: §D.2 · pp. 32–33

Step 2

  • The matching-event class is a λ-system, and finite-horizon events form a generating π-system, extending the equality to all events in the infinite-future σ-algebra.The proof uses the monotone class theorem for this extension.Source: §D.2 · pp. 33–34
  • The resulting equality gives the infinite future’s conditional law given the full past from the predictive state instead.The proof invokes Doob’s conditional independence property, since the state is measurable with respect to the past.Source: §D.2 · p. 34

D.3 PROOF OF LEMMA 1

The proof decomposes the next observation into its conditional mean and a residual with zero conditional mean. It also applies Theorem 7 to standard Borel state and observation spaces to obtain Theorem 1.

D.3 PROOF OF LEMMA 1

  • The next observation is decomposed into its conditional mean Z_t and residual ξ_{t+1}, defined as the observation minus that mean.The residual has conditional expectation zero given the past.Source: §D.3 · p. 34
  • The proof’s construction uses the inverse of Φ, which exists because Assumption 2 makes Φ injective, together with recursive state updates and g*.The construction is specified on the domain D defined in the proof.Source: §D.3 · p. 34

E.1 PROOF OF THEOREM 1

  • Theorem 1 follows directly from Theorem 7 because the state and observation spaces are Borel subsets of Euclidean spaces and hence standard Borel.The proof identifies this space property as the condition used for the implication.Source: §E.1 · p. 34

E.2 PROOF OF THEOREM 2

The proof uses random Fourier feature conditional expectations to embed predictive states injectively for generic choices of at least 2p + 1 features. This relies on feature expectations distinguishing conditional distributions and Assumption 1 making the state-to-distribution map one-to-one.

E.2 PROOF OF THEOREM 2

  • Unlike Wieck-Sosa & Shalizi (2026a) and Wieck-Sosa & Shalizi (2026b), this proof concerns conditional feature expectations given past observations to embed predictive states.Those works estimate unconditional random-feature expectations for parametric time-series models.Source: §E.2 · p. 35
  • The finite witness theorem’s analytic condition is met because the feature expectations admit a jointly real analytic extension over the predictive state space and feature parameters.The proof also uses the σ-subanalytic structure of the state space and parameter domain.Source: §E.2 · p. 35
  • Equal feature expectations imply equal conditional distributions because the features encode characteristic-function values; Assumption 1 then forces the predictive states to be equal.The proof uses the one-to-one map from predictive states to conditional distributions.Source: §E.2 · p. 36
  • For Π-almost every choice of k ≥ 2p + 1 random Fourier features, the conditional-expectation map Φ is injective on the predictive state space.The argument applies the finite witness theorem; k need not equal 2p + 1.Source: §E.2 · pp. 35–36

E.3 PROOF OF THEOREM 3

The proof establishes that the predictive state and its feature representation generate the same information, by showing each is a measurable function of the other.

E.3 PROOF OF THEOREM 3

  • Joint real analyticity makes the feature map measurable, so the feature representation is a measurable function of the predictive state.This gives σ(Zt) ⊆ σ(St).Source: §E.3 · p. 36
  • Injectivity, continuity, and compactness make the inverse feature map measurable, so the predictive state is a measurable function of its representation.This gives σ(St) ⊆ σ(Zt).Source: §E.3 · p. 36
  • Together, the two inclusions establish σ(St) = σ(Zt), yielding the stated almost-sure result.The proof identifies the first equality as definitional and the second as a consequence of this σ-field equality.Source: §E.3 · p. 36

E.4 PROOF OF THEOREM 4

The proof bounds the estimator’s error by controlling RNN prediction, MDN estimation, and their combination, under the stated boundedness and mixing conditions.

E.4 PROOF OF THEOREM 4

  • The average RNN error is decomposed around the predictive state, which minimizes squared prediction error over Ft-measurable random vectors.The cross term vanishes under the conditional orthogonality condition used in the concentration arguments.Source: §E.4 · p. 37
  • The concentration arguments require boundedness and mixing conditions, which the proof obtains from Assumptions 3 and 11, respectively.The proof applies the concentration inequality after checking those conditions.Source: §E.4 · p. 37
  • Truncated RNN predictions permit interlaced-subsequence concentration under β-mixing, with truncation chosen proportional to network width times log² n.The proof notes that β-mixing coefficients upper-bound α-mixing coefficients, allowing the cited concentration argument to apply.Source: §E.4 · p. 38
  • The RNN estimation bound depends on η, k, d, and m, with a logarithmic factor, and is used in the final convergence-rate argument.The proof derives the RNN rate before combining it with the MDN estimation error.Source: §E.4 · pp. 38–39
  • The proof combines the RNN rate with the MDN estimation error to obtain the estimator’s convergence rate.For the representation network, the fixed lag m changes constants through the recurrent-layer width.Source: §E.4 · pp. 38–39
  • Among the MDN components, j = d has the slowest convergence rate because it uses more covariates, making the upper bound largest.The proof therefore identifies this component as rate-limiting.Source: §E.4 · p. 39

E.5 PROOF OF THEOREM 5

The proof controls MDN error at the true predictive state, then accounts for substituting the estimated state. Combining these bounds yields the stated convergence rate under the theorem’s assumptions.

E.5 PROOF OF THEOREM 5

  • The final convergence bound is governed by the smaller of two exponents involving η, k, d, and m, together with a logarithmic factor.The proof combines bounds for density estimation, approximation, and predictive-state substitution to establish the stated rate.Source: §E.5 · p. 43
  • The proof bounds the MDN error at the true predictive state by partitioning the state space and controlling the probability of regions with large approximation error.With fixed k, the number of partition intervals is controlled by the approximation scale.Source: §E.5 · pp. 40–42
  • The predictive-state substitution error tends to zero under the theorem’s assumption because its rate is the square of the final rate term.This is the step that controls replacing the true state with the estimated state.Source: §E.5 · p. 42
  • The proof combines the true-state MDN error, approximation error, and state-substitution error to establish the estimator’s rate.The three terms are bounded by the rate in equation 31.Source: §E.5 · p. 43
Loading 2609.38524v1…