Learning Ergodic Dynamical Systems from a Finite Trajectory

Lorenzo Rosasco; Oleksii Kachaiev; Silvia Villa

A single finite trajectory of an ergodic stochastic dynamical system is enough to learn the optimal one-step predictor with high-probability guarantees that match i.i.d. rates, up to explicit mixing constants.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 04:50 UTC pith:DG5IBPBE

load-bearing objection A genuine, self-aware contribution to single-trajectory ergodic learning; the headline rate is real but explicitly rides on the well-specified assumption, and the paper says so.

arxiv 2607.22399 v1 pith:DG5IBPBE submitted 2026-07-24 stat.ML cs.LG

Learning Ergodic Dynamical Systems from a Finite Trajectory

Oleksii Kachaiev , Silvia Villa , Lorenzo Rosasco This is my paper

classification stat.ML cs.LG MSC 62M0562G0860J0537A30

keywords ergodic dynamical systemsMarkov chainsone-step predictionKoopman operatorregularized least squaresuniform geometric ergodicityconcentration inequalitiessingle-trajectory learning

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks what can be guaranteed when a learner sees only one finite trajectory of a stochastic dynamical system, where successive states are neither independent nor identically distributed. Its central answer is that, under uniform geometric ergodicity, regularized least squares over feature models estimates the optimal one-step predictor with excess-risk bounds of order sqrt(log(1/delta)/T), the same rate as independent data, with an extra multiplicative factor (C/(1-rho))^2 that encodes how slowly the system forgets its past. The proof supplies the missing tool: a concentration inequality for Hilbert-space-valued sums along Markov chains, built from the Poisson equation and a martingale decomposition. The same machinery yields operator-norm guarantees for learning Koopman operators and extends to vector-valued, higher-order, and finite-state systems. If correct, the result says that a trajectory's nonstationary transient phase is not an obstacle to statistical rates, only to the constants.

Core claim

Under a well-specified model (the true predictor f_star lies in the feature class) and uniform geometric ergodicity, the paper proves a high-probability finite-sample bound: regularized least squares from a single trajectory of length T satisfies excess risk O((C^2 D/(1-rho)^2)(log(1/delta)/sqrt(T) + 1/T^{3/2}) + ||w_star||^2/sqrt(T)) when lambda is chosen around T^{-1/2}. The T^{-1/2} leading term matches i.i.d. supervised learning; what is new is the explicit mixing factor (C/(1-rho))^2 and a boundary term 1/(lambda T^2) that comes from truncating a martingale over a finite orbit. The same template, with the state lifted to feature space, gives operator-norm learning guarantees for Koopman

What carries the argument

Uniform geometric ergodicity means the distribution at time t approaches the invariant measure at rate C rho^t in total variation. This guarantees that a Poisson equation (I-P)g = f has a bounded solution g = sum_{k>=0} P^k f for centered, bounded Hilbert-valued observables. That solution decomposes a trajectory sum into a martingale plus two boundary terms, and a Pinelis inequality for Banach-space-valued martingales controls the martingale. The resulting concentration inequality for empirical means, and its covariance-operator version, is what converts a single nonstationary trajectory's empirical averages into invariant-measure expectations with explicit dependence on the mixing constants

Load-bearing premise

The fast T^{-1/2} guarantee assumes the true one-step predictor is exactly representable in the chosen feature class; without that well-specified assumption, the paper proves only a slower consistency result.

What would settle it

Simulate a simple AR(1) chain X_{t+1} = rho X_t + noise with identity features, estimate the excess risk from single trajectories of increasing length across many replicates, and check whether the empirical rate is T^{-1/2} with constants growing like (1-rho)^{-2}; a slower rate or a linear growth in (1-rho)^{-1} would show the central bound is not tight.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

For any system satisfying uniform geometric ergodicity, a single orbit of length T certifies one-step prediction at the same T^{-1/2} rate as i.i.d. data, without requiring a burn-in period.
The multiplicative factor (C/(1-rho))^2 quantifies how slow mixing inflates sample needs, acting as an explicit effective-sample-size penalty.
The same estimator and analysis give learning guarantees for Koopman operators in operator norm from one nonstationary trajectory.
Higher-order and finite-state next-token prediction inherit the same T^{-1/2} rate, with the sample count adjusted to T-p+1 for order-p systems.
Universal consistency holds even without the well-specified assumption, so asymptotic learnability does not depend on exact model specification.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the paper's mixing factor (C/(1-rho))^2 is likely conservative; deviations of ergodic averages typically scale with integrated correlation time, suggesting a linear (1-rho)^{-1} dependence, and the paper's own slow-mixing experiments show trajectory learning lagging in a way that may overstate true difficulty.
Editorial inference: because the T^{-1/2} rate rests on exact representability of f_star, an experiment with a drift outside the feature space should show a slower empirical rate; universal kernels close the approximation gap only asymptotically.
Editorial inference: the Poisson-equation and martingale machinery is natural scaffolding for faster rates under source conditions and for spectral regularizers, since the trajectory-specific difficulty is concentrated in covariance concentration.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

A genuine, self-aware contribution to single-trajectory ergodic learning; the headline rate is real but explicitly rides on the well-specified assumption, and the paper says so.

read the letter

Quick take: this is a genuine step for learning from one nonstationary trajectory. The Hilbert-space-valued Hoeffding bound for uniformly geometrically ergodic Markov chains (Appendix C) is the real technical engine, and the paper uses it honestly: covariance concentration, martingale decomposition, approximation-estimation split. Theorem 3.6's T^{-1/2} rate for well-specified models is derived, not fitted, and the extensions to vector states, higher-order lags, finite-state prediction, and Koopman learning are mostly direct but add real coverage. I side with the reader's accept verdict, though I would temper the headline slightly.

What the paper does well: assumptions are explicit, proofs are detailed, and the text repeatedly tells you where things are weaker. It says the fast rate needs Assumption 3.5 (exact representability), that without it Proposition 3.8 only gives consistency, and that the (1-rho)^{-2} factor is probably loose. That self-awareness is not just rhetorical; they actually leave the improved mixing dependence open.

Soft spots, in order. (1) Assumption 3.5 is load-bearing. For universal kernels, f* approximable is not the same as exactly representable, so the "matching i.i.d. rates" claim should be read as a well-specified guarantee. The stress-test note is right, and the paper itself says this in Sections 3.3 and 3.4. Not an internal contradiction. (2) The constants D, D1-D4 are often defined in proofs rather than stated in the theorems, which makes the bounds less transparent than they could be. (3) The numerical section is illustrative only, with no code or data; fine for a theory paper, but not evidence for the rates. (4) Minor typos, e.g. Section 5's title says "higher-order systems dynamical systems". Citation pattern is fine: self-citations are to relevant prior work like Kostic et al., and the comparison with Zou et al. is honest about different assumptions.

Bottom line: for anyone doing statistical learning with dependent data, this is worth engaging with and citing. It deserves a serious referee; the well-specified limitation should stay transparent in the final version, perhaps with a misspecified-rate theorem under source conditions, but the current version is already a solid contribution.

Referee Report

0 major / 6 minor

Summary. The paper studies the statistical learning problem of estimating the one-step transition (and later the Koopman operator) of a time-homogeneous Markov process from a single finite trajectory, without assuming stationarity. The population risk is defined with respect to the invariant measure, and the estimator is regularized least squares over a feature space, possibly an RKHS. Under bounded features, a Bernstein-type residual moment condition, and uniform geometric ergodicity, the authors prove strong universal consistency and, under exact representability of the regression function, a high-probability excess-risk bound of order O( (C^2/(1-ρ)^2)(log(6/δ)/√T + 1/T^{3/2}) + ||w*||^2/√T ) when λ ≍ T^{-1/2}. The analysis is extended to vector-valued states, higher-order Markov processes, finite-state next-token prediction via a least-squares surrogate with margin/comparison inequalities, and Koopman operator learning in operator norm. The main technical tool is a concentration inequality for Hilbert-space-valued additive functionals of uniformly geometrically ergodic Markov chains, developed in Appendix C via a Poisson-equation/martingale decomposition and Pinelis-type tail bounds.

Significance. If the results hold up, this is a valuable contribution: it provides non-asymptotic learning guarantees for a nonstationary single-trajectory setting, with the ergodicity constants entering explicitly, and it connects statistical learning theory with quantitative ergodic theory. The paper is unusually careful: assumptions are stated explicitly, the proofs are detailed, and the central Theorem 3.6 follows from clean approximation/estimation decompositions supported by the Appendix C concentration result. The Hilbert-space-valued Hoeffding inequality for geometrically ergodic chains is itself a useful technical contribution. The stress-test concern about Assumption 3.5 is real: the T^{-1/2} rate in Theorem 3.6 is a well-specified-model guarantee; without exact representability, Proposition 3.8 gives only a slower bound and Theorem 3.4 gives consistency but not the rate. This limitation is stated explicitly in the theorem and surrounding text, so it is an important scope condition rather than an internal inconsistency. The numerical experiments are illustrative rather than a benchmark.

minor comments (6)

[§Abstract / §3.3, Theorem 3.6] The T^{-1/2} rate in Theorem 3.6 is explicitly conditional on Assumption 3.5 (exact representability of f* in the feature class), while Proposition 3.8 and Theorem 3.4 show that without this assumption only slower bounds or asymptotic consistency are obtained. This is stated in the text, but because the abstract promises only 'high-probability guarantees', I recommend adding the qualifier 'for well-specified models' when referring to the finite-sample rate, to prevent over-reading of the headline claim.
[§2.4 / Eq. (4) and Appendix A.7] In Example 2.5 and Appendix A.7, the d=1 approximation for 1/(1−ρ) appears to be off by a factor of 2. Since 1−ρ = 2(1−Φ(a)), the usual Mills-ratio approximation gives 1/(1−ρ) ≈ √(π/2) a e^{a^2/2}, not √(2π) a e^{a^2/2}. Please correct or clarify the convention.
[§C.4, proof of Theorem C.1] In the bound for the remainder, the text writes ||R_T|| ≤ ||g(X_1)|| + ||g(X_T)||. From Lemma C.5, R_T = g(X_0) − g(X_T), so the first argument should be g(X_0).
[§3.1] The text says 'Assumption 5' when referring to the moment bound displayed as Equation (5). Please refer to 'Condition (5)' or renumber to avoid confusion with the numbered assumptions.
[§8, Fig. 1] The caption reads 'Dependency of the mean squared error'; it should be 'Dependence'. Also, the legend label 'KRR (train: i.i.d)' is slightly ambiguous; since the text describes an i.i.d. training set drawn from the invariant measure, the label could read 'train: i.i.d. from π'.
[Theorems 3.6, 4.4, 5.5, 6.4, 7.5] Several theorems state the leading constant D only as 'can be derived from the proof'. Because these bounds are the main quantitative deliverables, I recommend giving D explicitly (for example, referencing D4 in Proposition 3.8 or displaying the final assembled constant) so that readers can verify and compare constants without reconstructing the proof.

Circularity Check

0 steps flagged

No significant circularity: the finite-sample rates are derived from explicit assumptions and self-contained proofs, with the well-specified assumption being an acknowledged scope limitation rather than a circular input.

full rationale

The derivation chain is self-contained. Theorem 3.6 is a conditional finite-sample bound proved from the regularized least-squares estimator (Eq. 14), the approximation/estimation decomposition in Propositions 3.7 and 3.8, and the Hilbert-space concentration inequality Theorem C.1, which is proved in Appendix C from Assumption 2.4 via the Poisson equation and Pinelis' martingale inequality. The excess risk E(f_hat_lambda, f_star) is defined with respect to the invariant measure pi independently of the estimator. The only load-bearing positivity is Assumption 3.5, which requires f_star = <w_star, Phi(.)>; this is stated explicitly as an assumption, and the paper itself notes it can be weakened: Proposition 3.8 says the first bound 'does not require the model to be well specified, but has a worse dependence on lambda, of order 1/(lambda^2 T), in the leading term. This bound is sufficient to establish the asymptotic consistency result in Theorem 3.4. Under Assumption 3.5, the second bound improves this dependence to 1/(lambda T), which is needed to obtain the finite-sample rate in Theorem 3.6.' That is a scope limitation, not a circular reduction. Self-citations (e.g., Kostic et al. 2022, Ciliberto et al. 2020, De Vito et al. 2005a) provide related work, context, or standard facts whose proofs are included; no central theorem is imported from a self-citation. The Koopman and finite-state guarantees are explicit reductions to the vector-valued one-step analysis, not renamings. No fitted parameter is presented as a prediction, and no prediction is equivalent to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The central claims rest on standard Markov-chain ergodicity, sub-Gaussian noise and bounded-feature assumptions, and a well-specified model condition. No parameters are fitted to data; the constants C, rho, M, sigma, kappa are assumed inputs. The finite-state chapter introduces a minor ad hoc restriction that the identity feature map is bounded on the encoded state space.

axioms (5)

domain assumption Uniform geometric ergodicity (Assumption 2.4): sup_x ||P^t(x,.)-pi||_TV <= C rho^t.
Central mixing assumption that enables the concentration inequality Theorem C.1; all bounds inherit the factor (C/(1-rho))^2.
domain assumption Moment condition and bounded feature map (Assumption 3.2): E[|X'-f_star(X)|^m | X=x] <= m!/2 sigma^2 M^{m-2} and ||Phi(x)|| <= kappa.
Standard sub-Gaussian-style conditions from supervised learning; needed for Bernstein-type concentration of the martingale terms.
domain assumption Well-specified model (Assumption 3.5): f_star(x)=<w_star,Phi(x)>.
Required for the T^{-1/2} rate in Theorem 3.6; without it, only universal consistency (Theorem 3.4) is proved.
ad hoc to paper Boundedness of identity feature map on the effective state space (Remark E.1).
In the finite-state setting, Phi(z)=z is unbounded on R^N, but the proof only needs boundedness on E(X) subset R^N; this restriction is flagged by the authors.
standard math Standard operator-theoretic and martingale results: spectral theorem, Neumann series, Pinelis inequality, Poisson equation theory.
Used extensively in Appendices B and C; these are not the paper's contribution but are cited or proved for completeness.

pith-pipeline@v1.3.0-alltime-deepseek · 59596 in / 10855 out tokens · 126892 ms · 2026-08-01T04:50:57.699785+00:00 · methodology

0 comments

read the original abstract

We consider the problem of learning from a single finite trajectory of an ergodic stochastic dynamical system. More precisely, we study discrete-time autonomous stochastic systems defining time-homogeneous Markov processes. We first focus on estimating the optimal one-step prediction function by nonlinear least squares, and derive high-probability guarantees measured with respect to the invariant measure of the process. These results make explicit how the non-independent and non-identically distributed nature of trajectory data modifies the classical statistical learning analysis. We then extend the framework to higher-order systems and finite-state spaces. Finally, we show that the same least squares and concentration arguments naturally extend to learning Koopman operators. Our approach combines tools from statistical learning theory and quantitative ergodic theory for Markov chains. It relies, in particular, on a concentration inequality for Hilbert-space-valued additive functionals of uniformly geometrically ergodic Markov chains.

Figures

Figures reproduced from arXiv: 2607.22399 by Lorenzo Rosasco, Oleksii Kachaiev, Silvia Villa.

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 5 linked inside Pith

[1]

A. León, C. and Perron, F. (2004). Optimal hoeffding bounds for discrete reversible markov chains. Adamczak, R. (2008). A tail inequality for suprema of unbounded empirical processes with applications to markov chains. Agarwal, A. and Duchi, J. C. (2012). The generalization ability of online algorithms for dependent data. IEEE Transactions on Information ...

2004
[2]

Fischer, S

John Wiley & Sons. Fischer, S. and Steinwart, I. (2020). Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 21(205):1–38. Gallegos-Herrada, M. A., Ledvinka, D., and Rosenthal, J. S. (2024). Equivalences of geometric ergodicity of markov chains.Journal of Theoretical Probability, 37(2):1230–1256. Gia...

2020
[6]

Grunewalder, S., Lever, G., Baldassarre, L., Pontil, M., and Gretton, A. (2012). Modelling transition dynamics in mdps with rkhs embeddings.arXiv preprint arXiv:1206.4655. Györfi, L., Kohler, M., Krzyżak, A., and Walk, H. (2002).A Distribution-Free Theory of Nonparametric Regression. Springer Series in Statistics. Springer, New York. Han, Y., Jana, S., an...

Pith/arXiv arXiv 2012
[11]

If the conditional probabilities in(85) do not depend ont, the process is calledtime-homogeneous

= P(Xt∈A|F t−1). If the conditional probabilities in(85) do not depend ont, the process is calledtime-homogeneous. Markov processes are tightly connected to the notion of transition kernel. Atransition kernelon(X,B(X))is a map P:X×B(X)→[0,1] such that, for everyx∈X , the mapA↦→P(x,A )is a probability measure on(X,B (X )), and, for every A∈B(X), the mapx↦→...

2018
[13]

are mutually independent, then P-almost everyω∈Ωdetermines a sequence xt =X t(ω), η t =N t(ω), satisfying (87)

IfX0,N 0,N 1,... are mutually independent, then P-almost everyω∈Ωdetermines a sequence xt =X t(ω), η t =N t(ω), satisfying (87). Thus, (87) is the sample-path notation, while(86) is the corresponding random-variable formulation. As shown next, the latter yields an immediate connection to Markov processes. We first add a remark regarding the existence of p...

1995
[14]

are mutually independent,X0 has law(ξ0)#PX, and eachNt has lawξη #PN

Then X0,N 0,N 1,... are mutually independent,X0 has law(ξ0)#PX, and eachNt has lawξη #PN. Hence the probability space used to describe the stochastic dynamical system(86) above can always be realized as a product space carrying the initial condition together with countably many independent copies of the noise. A.5 Stochastic dynamical systems and Markov p...

1999
[15]

(90) Let Gt = { σ(X0), t= 0, σ(X0,N 0,...,N t−1), t≥1

We claim that P(Xt+1∈B|F t) =h B(Xt)P-a.s. (90) Let Gt = { σ(X0), t= 0, σ(X0,N 0,...,N t−1), t≥1. By Equation (86),Xs isG t-measurable for everys≤t. Hence Ft =σ(X 0,...,X t)⊆G t. By mutual independence of X0,N 0,N 1,... , Nt is independent ofGt, and therefore ofFt. Since Xt is Ft-measurable andNt is independent ofFt, for everyA∈F t, ∫ A 1B(f(Xt(ω),Nt(ω)))...

2012
[16]

SinceT is a measurable isomorphism onto its image˜Y, equality holds

By the definition ofQand˜π, Qt(x,·)−˜π  TV = T#Pt(x,·)−T #π  TV = Pt(x,·)−π  TV, by the data-processing inequality for the total variation distance under measurable transformations; see, e.g., Polyanskiy and Wu (2025, Section 7.2). SinceT is a measurable isomorphism onto its image˜Y, equality holds. Taking the supremum overx∈Xand applying (92)...

2025
[17]

P(x,A) = ∫ A 1 (2πσ 2)d/2 exp ( −∥x′−b(x)∥ 2 X 2σ2 )    p(x,x′) dx′, x∈X,A∈B(X)

Moreover, 1 1−ρ ≈    √ 2πaexp ( a2/2 ) , d= 1 exp ( a √ d+a 2/2 ) , d≫1 Proof.We begin by constructing transition kernel defined by the process(Xt)t≥0. P(x,A) = ∫ A 1 (2πσ 2)d/2 exp ( −∥x′−b(x)∥ 2 X 2σ2 )    p(x,x′) dx′, x∈X,A∈B(X). Note that suppP (x,· ) =X for everyx∈X . Therefore, Markov chain(Xt)t∈N0 is ψ-irreducible with respect to Lebesgue me...

2012
[18]

It is positive since for allf∈H ⟨Σρf,f⟩H = ∫ |⟨f,Φ(x)⟩H|2ρ(dx)≥0

It is easy to see thatΣρ is self-adjoint, since for allf,g∈H ⟨Σρf,g⟩H = ∫ ⟨f,Φ(x)⟩H⟨Φ(x),g⟩H ρ(dx) =⟨f,Σ ρg⟩H. It is positive since for allf∈H ⟨Σρf,f⟩H = ∫ |⟨f,Φ(x)⟩H|2ρ(dx)≥0. Moreover,Σ ρ is trace class sinceTr [Σ]= ∫ ∥Φ(x)∥2ρ(dx)≤κ 2, because of Condition(18). LetL2(ρ)be the Hilbert space of square-integrable functions with respect toρ with inner produ...

1969
[19]

See, e.g., Douc et al

ThePoisson equation associated withfandPis the operator equation: (I−P)g=f,(102) whereIdenotes the identity operator onM b(X,H). See, e.g., Douc et al. (2018, Definition 21.2.1). A natural question is under which conditions onf and on the process(Xt)t∈N the Poisson equation has a solution. In the next proposition we give an answer. Proposition C.4(Poisson...

2018
[20]

Consequently,MT is a martingale inHwith respect toF

Thus, the process(dt)t≥1 is adapted to the filtrationF = (Ft)t≥1 and satisfies the martingale difference property. Consequently,MT is a martingale inHwith respect toF. Remark C.6.This decomposition originates from Gordin (1969) in the study of stationary Markov chains. C.4 Proof of Theorem C.1. Provided with the martingale decomposition in Lemma C.5 we ca...

1969
[22]

Steinwart, I., Hush, D., and Scovel, C. (2009). Learning from dependent observations.Journal of Multivariate Analysis, 100(1):175–194. Tsigler, A. and Bartlett, P. L. (2023). Benign overfitting in ridge regression.Journal of Machine Learning Research, 24(123):1–76. Tsybakov, A. B. (2004). Optimal aggregation of classifiers in statistical learning.The Anna...

Pith/arXiv arXiv 2009
[25]

Musavi, N., Guo, Z., Dullerud, G., and Li, Y. (2024). Identification of analytic nonlinear dynamical systems with non-asymptotic guarantees.Advances in Neural Information Processing Systems, 37:85500–85522. Nowak, A., Bach, F., and Rudi, A. (2019). Sharp analysis of learning with discrete losses. InProceedings of the Twenty-Second International Conference...

2024
[31]

Brockwell, P

Springer Science & Business Media. Brockwell, P. J. and Davis, R. A. (2016a).Introduction to Time Series and Forecasting. Springer, 3 edition. Brockwell, P. J. and Davis, R. A. (2016b).Introduction to time series and forecasting. Springer Texts in Statistics. Springer International Publishing, Cham, Switzerland, 3 edition. Brunton, S. L., Budišić, M., Kai...

Pith/arXiv arXiv 2021
[107]

Li, Y., Zhang, T., Das, S., Shamma, J., and Li, N

American Mathematical Soc. Li, Y., Zhang, T., Das, S., Shamma, J., and Li, N. (2023). Non-asymptotic system identification for linear systems with nonlinear policies.IFAC-PapersOnLine, 56(2):1672–1679. 43 Li, Z., Meunier, D., Mollenhauer, M., and Gretton, A. (2024). Towards optimal sobolev norm rates for the vector-valued regularized least-squares algorit...

Pith/arXiv arXiv 2023
[156]

Kloeckner, B

Springer Science & Business Media. Kloeckner, B. R. (2020). Empirical measures: regularity is a counter-curse to dimensionality.ESAIM: Probability and Statistics, 24:408–434. Kontorovich, A. and Weiss, R. (2014). Uniform chernoff and dvoretzky-kiefer-wolfowitz-type inequalities for markov chains and related processes.Journal of Applied Probability, 51(4):...

Pith/arXiv arXiv 2020
[204]

Mollenhauer, M., Klus, S., Schütte, C., and Koltai, P. (2022). Kernel autocovariance operators of stationary processes: Estimation and convergence.Journal of Machine Learning Research, 23(327):1–34. Montenegro, R. and Tetali, P. (2006). Mathematical aspects of mixing times in markov chains.Foundations and Trends®in Theoretical Computer Science, 1(3):237–3...

2022
[423]

I., and Recht, B

45 Simchowitz, M., Mania, H., Tu, S., Jordan, M. I., and Recht, B. (2018). Learning without mixing: Towards a sharp analysis of linear system identification. InConference On Learning Theory, pages 439–473. PMLR. Smale, S. and Zhou, D.-X. (2005). Shannon sampling ii: Connections to learning theory.Applied and Computational Harmonic Analysis, 19(3):285–302....

2018
[2002]

Thus the pair(µ0,P )determines the law of the processuniquely, although the process may admit many realizations on different probability spaces

48 yields a unique probability measure on the canonical path spaceX N0, equipped with its productσ-algebra, under which the coordinate process is a time-homogeneous Markov process(Xt)t∈N0 with initial distribution µ0 and transition kernelP, i.e., P(X0∈A) =µ 0(A),P(X t∈A|X t−1) =P(X t−1,A), for allt∈N and A∈B (X ). Thus the pair(µ0,P )determines the law of...

2009

[1] [1]

A. León, C. and Perron, F. (2004). Optimal hoeffding bounds for discrete reversible markov chains. Adamczak, R. (2008). A tail inequality for suprema of unbounded empirical processes with applications to markov chains. Agarwal, A. and Duchi, J. C. (2012). The generalization ability of online algorithms for dependent data. IEEE Transactions on Information ...

2004

[2] [2]

Fischer, S

John Wiley & Sons. Fischer, S. and Steinwart, I. (2020). Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 21(205):1–38. Gallegos-Herrada, M. A., Ledvinka, D., and Rosenthal, J. S. (2024). Equivalences of geometric ergodicity of markov chains.Journal of Theoretical Probability, 37(2):1230–1256. Gia...

2020

[3] [6]

Grunewalder, S., Lever, G., Baldassarre, L., Pontil, M., and Gretton, A. (2012). Modelling transition dynamics in mdps with rkhs embeddings.arXiv preprint arXiv:1206.4655. Györfi, L., Kohler, M., Krzyżak, A., and Walk, H. (2002).A Distribution-Free Theory of Nonparametric Regression. Springer Series in Statistics. Springer, New York. Han, Y., Jana, S., an...

Pith/arXiv arXiv 2012

[4] [11]

If the conditional probabilities in(85) do not depend ont, the process is calledtime-homogeneous

= P(Xt∈A|F t−1). If the conditional probabilities in(85) do not depend ont, the process is calledtime-homogeneous. Markov processes are tightly connected to the notion of transition kernel. Atransition kernelon(X,B(X))is a map P:X×B(X)→[0,1] such that, for everyx∈X , the mapA↦→P(x,A )is a probability measure on(X,B (X )), and, for every A∈B(X), the mapx↦→...

2018

[5] [13]

are mutually independent, then P-almost everyω∈Ωdetermines a sequence xt =X t(ω), η t =N t(ω), satisfying (87)

IfX0,N 0,N 1,... are mutually independent, then P-almost everyω∈Ωdetermines a sequence xt =X t(ω), η t =N t(ω), satisfying (87). Thus, (87) is the sample-path notation, while(86) is the corresponding random-variable formulation. As shown next, the latter yields an immediate connection to Markov processes. We first add a remark regarding the existence of p...

1995

[6] [14]

are mutually independent,X0 has law(ξ0)#PX, and eachNt has lawξη #PN

Then X0,N 0,N 1,... are mutually independent,X0 has law(ξ0)#PX, and eachNt has lawξη #PN. Hence the probability space used to describe the stochastic dynamical system(86) above can always be realized as a product space carrying the initial condition together with countably many independent copies of the noise. A.5 Stochastic dynamical systems and Markov p...

1999

[7] [15]

(90) Let Gt = { σ(X0), t= 0, σ(X0,N 0,...,N t−1), t≥1

We claim that P(Xt+1∈B|F t) =h B(Xt)P-a.s. (90) Let Gt = { σ(X0), t= 0, σ(X0,N 0,...,N t−1), t≥1. By Equation (86),Xs isG t-measurable for everys≤t. Hence Ft =σ(X 0,...,X t)⊆G t. By mutual independence of X0,N 0,N 1,... , Nt is independent ofGt, and therefore ofFt. Since Xt is Ft-measurable andNt is independent ofFt, for everyA∈F t, ∫ A 1B(f(Xt(ω),Nt(ω)))...

2012

[8] [16]

SinceT is a measurable isomorphism onto its image˜Y, equality holds

By the definition ofQand˜π, Qt(x,·)−˜π  TV = T#Pt(x,·)−T #π  TV = Pt(x,·)−π  TV, by the data-processing inequality for the total variation distance under measurable transformations; see, e.g., Polyanskiy and Wu (2025, Section 7.2). SinceT is a measurable isomorphism onto its image˜Y, equality holds. Taking the supremum overx∈Xand applying (92)...

2025

[9] [17]

P(x,A) = ∫ A 1 (2πσ 2)d/2 exp ( −∥x′−b(x)∥ 2 X 2σ2 )    p(x,x′) dx′, x∈X,A∈B(X)

Moreover, 1 1−ρ ≈    √ 2πaexp ( a2/2 ) , d= 1 exp ( a √ d+a 2/2 ) , d≫1 Proof.We begin by constructing transition kernel defined by the process(Xt)t≥0. P(x,A) = ∫ A 1 (2πσ 2)d/2 exp ( −∥x′−b(x)∥ 2 X 2σ2 )    p(x,x′) dx′, x∈X,A∈B(X). Note that suppP (x,· ) =X for everyx∈X . Therefore, Markov chain(Xt)t∈N0 is ψ-irreducible with respect to Lebesgue me...

2012

[10] [18]

It is positive since for allf∈H ⟨Σρf,f⟩H = ∫ |⟨f,Φ(x)⟩H|2ρ(dx)≥0

It is easy to see thatΣρ is self-adjoint, since for allf,g∈H ⟨Σρf,g⟩H = ∫ ⟨f,Φ(x)⟩H⟨Φ(x),g⟩H ρ(dx) =⟨f,Σ ρg⟩H. It is positive since for allf∈H ⟨Σρf,f⟩H = ∫ |⟨f,Φ(x)⟩H|2ρ(dx)≥0. Moreover,Σ ρ is trace class sinceTr [Σ]= ∫ ∥Φ(x)∥2ρ(dx)≤κ 2, because of Condition(18). LetL2(ρ)be the Hilbert space of square-integrable functions with respect toρ with inner produ...

1969

[11] [19]

See, e.g., Douc et al

ThePoisson equation associated withfandPis the operator equation: (I−P)g=f,(102) whereIdenotes the identity operator onM b(X,H). See, e.g., Douc et al. (2018, Definition 21.2.1). A natural question is under which conditions onf and on the process(Xt)t∈N the Poisson equation has a solution. In the next proposition we give an answer. Proposition C.4(Poisson...

2018

[12] [20]

Consequently,MT is a martingale inHwith respect toF

Thus, the process(dt)t≥1 is adapted to the filtrationF = (Ft)t≥1 and satisfies the martingale difference property. Consequently,MT is a martingale inHwith respect toF. Remark C.6.This decomposition originates from Gordin (1969) in the study of stationary Markov chains. C.4 Proof of Theorem C.1. Provided with the martingale decomposition in Lemma C.5 we ca...

1969

[13] [22]

Steinwart, I., Hush, D., and Scovel, C. (2009). Learning from dependent observations.Journal of Multivariate Analysis, 100(1):175–194. Tsigler, A. and Bartlett, P. L. (2023). Benign overfitting in ridge regression.Journal of Machine Learning Research, 24(123):1–76. Tsybakov, A. B. (2004). Optimal aggregation of classifiers in statistical learning.The Anna...

Pith/arXiv arXiv 2009

[14] [25]

Musavi, N., Guo, Z., Dullerud, G., and Li, Y. (2024). Identification of analytic nonlinear dynamical systems with non-asymptotic guarantees.Advances in Neural Information Processing Systems, 37:85500–85522. Nowak, A., Bach, F., and Rudi, A. (2019). Sharp analysis of learning with discrete losses. InProceedings of the Twenty-Second International Conference...

2024

[15] [31]

Brockwell, P

Springer Science & Business Media. Brockwell, P. J. and Davis, R. A. (2016a).Introduction to Time Series and Forecasting. Springer, 3 edition. Brockwell, P. J. and Davis, R. A. (2016b).Introduction to time series and forecasting. Springer Texts in Statistics. Springer International Publishing, Cham, Switzerland, 3 edition. Brunton, S. L., Budišić, M., Kai...

Pith/arXiv arXiv 2021

[16] [107]

Li, Y., Zhang, T., Das, S., Shamma, J., and Li, N

American Mathematical Soc. Li, Y., Zhang, T., Das, S., Shamma, J., and Li, N. (2023). Non-asymptotic system identification for linear systems with nonlinear policies.IFAC-PapersOnLine, 56(2):1672–1679. 43 Li, Z., Meunier, D., Mollenhauer, M., and Gretton, A. (2024). Towards optimal sobolev norm rates for the vector-valued regularized least-squares algorit...

Pith/arXiv arXiv 2023

[17] [156]

Kloeckner, B

Springer Science & Business Media. Kloeckner, B. R. (2020). Empirical measures: regularity is a counter-curse to dimensionality.ESAIM: Probability and Statistics, 24:408–434. Kontorovich, A. and Weiss, R. (2014). Uniform chernoff and dvoretzky-kiefer-wolfowitz-type inequalities for markov chains and related processes.Journal of Applied Probability, 51(4):...

Pith/arXiv arXiv 2020

[18] [204]

Mollenhauer, M., Klus, S., Schütte, C., and Koltai, P. (2022). Kernel autocovariance operators of stationary processes: Estimation and convergence.Journal of Machine Learning Research, 23(327):1–34. Montenegro, R. and Tetali, P. (2006). Mathematical aspects of mixing times in markov chains.Foundations and Trends®in Theoretical Computer Science, 1(3):237–3...

2022

[19] [423]

I., and Recht, B

45 Simchowitz, M., Mania, H., Tu, S., Jordan, M. I., and Recht, B. (2018). Learning without mixing: Towards a sharp analysis of linear system identification. InConference On Learning Theory, pages 439–473. PMLR. Smale, S. and Zhou, D.-X. (2005). Shannon sampling ii: Connections to learning theory.Applied and Computational Harmonic Analysis, 19(3):285–302....

2018

[20] [2002]

Thus the pair(µ0,P )determines the law of the processuniquely, although the process may admit many realizations on different probability spaces

48 yields a unique probability measure on the canonical path spaceX N0, equipped with its productσ-algebra, under which the coordinate process is a time-homogeneous Markov process(Xt)t∈N0 with initial distribution µ0 and transition kernelP, i.e., P(X0∈A) =µ 0(A),P(X t∈A|X t−1) =P(X t−1,A), for allt∈N and A∈B (X ). Thus the pair(µ0,P )determines the law of...

2009