Learning with little mixing
Authors: Ingvar Ziemann
Stephen Tu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Learning Theory
Nonlinear Dynamical Systems
Learning with dependent data

Abstract: We study square loss in a realizable time-series framework with martingale difference noise. Our main result is a fast rate excess risk bound which shows that whenever a trajectory hypercontractivity condition holds, the risk of the least-squares estimator on dependent data matches the iid rate order-wise after a burn-in time. In comparison, many existing results in learning from dependent data have rates where the effective sample size is deflated by a factor of the mixing-time of the underlying process, even after the burn-in time. Furthermore, our results allow the covariate process to exhibit long range correlations which are substantially weaker than geometric ergodicity. We call this phenomenon learning with little mixing, and present several examples for when it occurs: bounded function classes for which the $L^2$ and $L^{2+\epsilon}$ norms are equivalent, finite state irreducible and aperiodic Markov chains, various parametric models, and a broad family of infinite dimensional $\ell^2(\mathbb{N})$ ellipsoids. By instantiating our main result to system identification of nonlinear dynamics with generalized linear model  transitions, we obtain a nearly minimax optimal  excess risk bound after only a polynomial burn-in time.


Learning with little mixing
Ingvar Ziemann KTH Royal Institute of Technology z ziemann@kth.ss se
Stephen Tu Robotics at Google stephentu@google... com
Abstract
We study square loss in a realizable time-series framework with martingale dif- ference noise. Our main result is fast rate excess risk bound which shows that whenever trajectory hypercontractivity condition holds, the risk of the least- squares estimator dependent data matches the iid rate order-wise after a burn-in time. In comparison, many existing results in learning from dependent data have rates where the effective sample size is deflated by factor of the mixing-time time of the underlying process, even after the burn-in in time. Furthermore, our results allow the covariate process to exhibit long range correlations which are substantially weaker than geometric ergodicity. We call this phenomenon learning with little mixing, and present several examples for when occurs: bounded function classes for which the T.2 and 2 norms are equivalent, ergodic finite state Markov chains, various parametric models, and a broad family of infinite dimensional (N ellipsoids. By instantiating main result to system identification of nonlinear dynamics with generalized linear model transitions, we obtain nearly minimax optimal excess risk bound after only polynomial burn-in time.
Introduction
Consider regression in the context of the time-series model:
Y; = fx(,) + Wt
0,1,
(1)
Such models are ubiquitous in applications of machine learning, signal processing, econometrics, and control theory. In our setup, the learner is given access to E N4 pairs ((X,, YD) drawn from the model (1), and is asked to output hypothesis I from hypothesis class F which best approximates the (realizable) regression function f+ I terms of square loss.
In this work, we study the least-squares estimator (LSE). This procedure minimizes the empirical risk associated to the square loss over the class F. When each pair observations (X2, Y:) drawn iid from some fixed distribution, this procedure is minimax optimal over broad set of hypothesis classes [1-4]. However, much less known about the optimal rate of convergence for the general time-series model (1), as correlations across time in the covariates { {X+} complicate the analysis.
With this in mind, we seek extend our understanding of the minimax optimality of the LSE for the time-series model (1). We show that for a broad class of function spaces and covariate processes, the effects of data dependency across time enter the LSE excess risk only as higher order term, whereas the leading term in the excess risk remains order-wise identical to that in the iid setting. Hence, after a sufficiently long, but finite burn-in time, the LSE's excess risk scales as if all T' samples are independent. This behavior applies to processes that exhibit correlations which decay slower than geometrically. We refer to this double phenomenon, where the mixing-tine time only enters burn-in time, and where the mixing requirement is mild, as learning with little mixing.
Our result stands in contrast a long line of work on learning from dependent data (see e.g., [5-14] and the references within), where the blocking technique [5] is used to create independence amongst
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the dependent covariates, so that tools to analyze independent learning can be applied. While these affrrmmenionedd works differ in their specific setups, the main commonality that the resulting dependent data rates mimic the corresponding independent rates, but with the caveat that the sample size is replaced by an "effective" sample size that is decreased in some way by the mixing-time even after any necessary burn-in time. Interestingly, the results of Ziemann et al. [15] studying the LSE on the model (1) also suffer from such sample degradation, but do not rely on the blocking technique.
The model (1) captures learning dynamical systems by setting Y, = X so that the regression function f. describes the dynamics of the state variable Xt. Recent progress in system identification shows that the lack of ergodicity does not necessarily degrade learning rates. Indeed, when the states evolve as a linear dynamical system (i.e., the function f. is linear), learning rates are not deflated by any mixing times, and match existing rates for iid linear regression [16-19]. Kowshik et al. [20], Gao and Raskutti [21] extend results of this flavor to parameter recovery of dynamics driven by generalized linear model. The extent to which this phenomenon less ergodicity not impeding tearning-generalllnn generalizes beyond linear and generalized linear models is key motivation for our work.
Contributions We consider the realizable setting, where f. is assumed to be contained in a known function space F. Our results rest on two assumptions regarding both the covariate process {X,} and the function space P. The first assumption posits that the process (Xe) exhibits some mild form of ergodicity (that is significantly weaker than the typical geometric ergodicity assumption). The second assumption is hypercontractivityy condition that holds uniformly in f along the trajectory (X,), extending contractivity assumptions for iid learning [3] to dependent processes.
Informally, our main result (Theorem 4.1, presented in Section 4), shows that under these two assumptions, letting comp( denote some (inverse) measure of complexity of F, the LSE f satisfies:
dimensional factors of
comp(
EII 111l x
higher order o(1 (1/7 ccmpp/ x)) terms. (2)
The first term in (2) matches existing LSE risk bounds for iid learning order-wise, and most impor- tantly, does not include any dependence on the mixing-time of the process. Indeed, all mixing-time dependencies enter only in the higher order term. Since this term scales as o(1 [T/Tm))mpp())) it becomes negligible after finite burn-in time. This captures the crux of our results: on a broad class of problems, given enough data, the LSE applied to time-series model (1) behaves as if all samples are independent.
Section 5 provides several examples for which the trajectory hypercontractivity assumption holds. When the covariate process {X,} is generated by finite-state irreducible and aperiodic Markoy chain, then any function class F satisfies the requisite condition. More broadly, the condition is satisfied for any bounded function classes for which the 2 and 2 norms (along trajectories) are equivalent. Next, we show that many infinite dimensional function spaces based on (²(NN) ellipsoids satisfy our hyperoontractivity condition, demonstrating that our results are not inherently limited to fnite-dimensional hypothesis classes.
To demonstrate the broad applicability of our framework, Section 6 instantiates our main result on two system identification problems that have received recent attention in the literature: linear dynamical systems (LDS), and systems with generalized linear model (GLM) transitions. For stable LDS, after a polynomial burn-in time, we recover an excess risk bound that matches the iid rate. A more general form of this result was recently established by Tu et al. [19]. For stable GLMs, also after polynomial burn-in time, we obtain the first excess risk bound for this problem which matches the iid rate, up to logarithmic factors in various problem constants including the mixing-time. In both of these settings, our excess risk bounds also yield nearly optimal rates for parameter recovery, matching known results for LDS [16] and GL.Ms [20] in the stable case. In Appendix A, we show experimentally, using the stable GL.M model, that the trends predicted by our theory are indeed realized in practice.
2 Related work
While regression is a fundamental problem studied across many disciplines, our work draws its main inspiration from Mendelson [3] and Simchowitz et al. [16]. Mendelson [3] shows that for nonparametric iid regression, only minimal assumptions are required for one-sided isometry, and
2

---

thus learning. Simchowitz et al. [16] build on this intuition and provide mixing- mixing-ffree rates for linear regression over trajectories generated by a linear dynamical system. We continue this trend, by leveraging one-sided isometry to show that mixing only enters as a higher order term in the rates of the nonparametric LSE. More broadly, the technical developments we follow synthesize techniques from two lines of work: nonparametric regression with iid data, and learning from dependent data.
Nonparametric regression with iid data. Beyond the seminal work of Mendelson [3], the works [2. 22, 23] all study iid regression with square loss under various moment equivalence conditions. In addition to moment equivalence, we build on the notion of off'et Rademacher complexity defined by [24] in the context of iid regression. Indeed, we show that a martingale analogue of the offset complexity (described in [15]) characterizes the LSE rate in (I).
Learning from dependent data. As discussed previously, many existing results for learning from dependent data reduce the problem to independent learning via the blocking technique [5], the expense of sample complexity deflation by the mixing-time. Nagaraj et al. [25] prove a lower bound for linear regression stating that in a worst case agnostic model, this deflation is unavoidable. Moreover, if the linear regression problem is realizable, Nagaraj et al. [25] provide upper and lower bounds showing that the mixing-time only affects the burn-in time, but not the final risk. We note that their upper bound is an algorithmic result that holds only for a specific modification of SGD, Our work can be interpreted as an upper bound in the more general nonparametric setting, where we put forth sufficient conditions to recover the iid rate after a burn-in time. Our result is algorithm agnostic and directly applies to the empirical risk minimizer. Ziemann et al. [15] also study the model (1), and provide an cepormmtion-thhoreee approach fundamentally reduces to showing two-sided concentration something our work evades- and therefore their bounds incur worst case dependency on the mixing-time. Roy et al. [13] extend the results from Mendelson [3] to the dependent data setting. While following Mendelson's 's argument allows their results to handle non-realizability and heavy-tailed noise, their proof ultimately still relies on two-sided concentration for both the "version space" and the "noise interaction". Hence, their rates end up degrading for slower mixing processes. We note that this is actually expected in the non-realizable setting in light of the lower bounds in Nagaraj et al. [25].
analysis of the nonparametrie LSE. However, their
The measure of dependencies we use for the process {X,} is due to Samson [26]. Recently, Dagan et al. [27] use a similar measure to study learning when the covariates have no obvious sequential ordering (e.g., graph structure or Ising model). However, our results are not directly comparable, other than noting that their risk bounds degrade as the measure of correlation increases.
Results in linear system identification show that lack of ergodicity does not degrade parameter recovery rates [16-19, 28, 29]. Beyond linear system identification, Kowshik et al. [20], Gao and Raskutti [21]. Sattar and Oymak [30], Foster et al. [31] prove parameter recovery bounds for dynamical systems driven by a generalized linear model (GLM) transition. Most relevant are Kowshik et al. [20] and Gao and Raskutti [21]. who again show that the lack of ergodicity does not hamper rates. Indeed, Gao and Raskutti [21] even manage do so semiparametric setting with an unknown link function. As mentioned previously, our main result instantiated to these problems in the stable case matches existing excess risk and parameter recovery bounds for linear system identification, and actually provides the sharpest known excess risk bound for the GLM setting (when the link function is known). A more detailed comparison to existing LDS results is given in Appendix 1.4, and to existing GLM results in Appendix J.I.
3 Problem formulation
The time-series (1) evolves on two subsets of Fuclidean space, X C dRxx and Y c Rdy, with X, E X and Y,, W Y. Expectation (resp. probability) with respect to all the randomness of the underlying probability space is denoted by E (resp. P). The Euclidean norm on Rd is denoted || -1l2, and the unit sphere in Rd is denoted 1d-1 For a matrix M E Rd xd2, ||M op denotes the largest singular value, mmin (M) the smallest non-zero singular value, and (M number. When the matrix M is symmetric, Amin Xmin(M) will be used to denote its minimum eigenvalue.
|| minn (M) the condition
We assume there exists filtration {Fi} such that (a) (W:) is a square integrable martingale difference sequence (MDS) with respect to this filtration, and (b) {X.} is adapted to (F-1))- Further tail conditions on this MDS will be imposed as necessary later on.
3

---

Let & be a hypothesis space of functions mapping R to Rdy. We assume that the true regression function is an element of & (i.e.. f. E )), ) and that # known to the learner. Given two compatible function spaces F2 let $1 $2 {fi
f2 fi E $1.f2 E F2). A key quantity in our analysis the shifted function class F. _ & {f.). Our results will be stated under the assumption that P. is star-shuped, although we will see that this is not too restrictive. For any function f X + Bdy, we define || _ sup=ex xup>exll/fll> ex|l/ll2- A function f is B-bounded if || < B. Similarly, a hypothesis class is B-bounded if each of elements is B-bounded. For bounded class &e and resolution > 0, the quantity No (F, denotes the size of the minimal E-cover of # (contained in }) ) in the nnomm.
We fix a T E N+, indicating the number of labeled observations {(X,, = from the time-series (I) that are available to the learner. The joint distribution of Xo:T - (Xo.... x1-1) is denoted
Px- For p 2 1, we endow - with L xP(Px) norms: ||~-g - 7 Ei [ g( 1 where expectation is taken with respect to Px. We will mostly be interested in L2xPxx, hereafter often just referred to as L This is the L space associated the law of the uniform mixture over Xo-r-1 and thus, for iid data, coincides with the standard L space often considered in iid regression. For radius O, we let (r)) denote the closed ball of F. with radius r in L and we let ( denote its boundary: B(r) { E &. ||.f S r²) and (B(r) & {s E $- 1;: = r²)
The learning task is to produce an estimate f of f.. which renders the excess risk f small as possible. We emphasize that Ilf f-11,, = + Σi= E _ [lf((X)) (Xx) where X a fresh, statistically independent, sample with the same law Px as Xo.T Namely, f f= is a random quantity, still depending on the internal randomness of the learner and that of the sample Xo-r- used to generate f. We study the performance of the least-squares estimator (LSE) defined as f E argmin T El || f(x))1 and measure the excess risk Elis - f-1li22
4 Results
This section presents our main result. We first detail the definitions behind our main assumptions in Section 4.1. The main result and two corollaries are then presented in Section 4.2.
4.1 Hypercontractivity and the dependency matrix
Hy Hypervontractivity. We first state our main trajectory hypercontractivity condition, which we will use to establish lower isometry. The following definition is heavily inspired by recent work on learning without concentration [3, 23].
Definition 4.1 (Trajectory (C, at) -ty-ereoontaactiiity)... Fix constants C > 0 and a E [1, We say that the tuple (IF Px) satisfies the trajectory (C, hypercoottraatt condition if
T-1
1) for all f E
E
T M
C
E
Σ
13(x))13
(3)
T
Here, the expectation is with respect to Px, the joint law of Xo.T-1.
Condition (3) interpolates between boundedness and small-ball behavior. Indeed, if the class I is B-bounded, then it satisfies trajectory (B², -n-ypeeccontractivityy trivially. On the other hand, for
= 2, (3) asks that [| S C1/41]fllz> for trajectory-wise LP-norms; by the Paley-Zygmund inequality, this implies that a small-ball condition holds. Moreover, if for some E (0, 2), the trajectory-wise 2 and 2 norms are equivalent F,, then Proposition 5.2 (Section 5) shows that the condition holds for nontrivial a = 1 + e/2 E 21, More examples are given in Section 5.
Our main results assume that (F., Px) (or particular subset of F.)) satisfies the trajectory (C, a)) hypercontractivity condition with a > 1, which we refer to as the hypercontracttive regime. The condition > is required in analysis for the lower order excess risk term not depend on
A function class 3 is shaped if for any a [0, 1]. f implies af E F.

---

the mixing- time. Our results instantiated for the a = 1 case directly correspond to existing work by Ziemann et al. [15], and exhibit lower order term that depends on the mixing time.
Ergodicity via the dependency matrix. We now state the main definition we use to measure the stochastic dependency of a process. Recall that for two measures μ4, P the same measurable space with o-algebra- A, the rotal-variation norm is defined as || 2/|TV - sup AEAA Ie(A) v(A)]-
Definition 4.2 (Dependency matrix, Samson [26, Section 2)). The dependency matrix of a process {Zi with distribution Pz is the supper-triangule matrix I d'dep (Pp( = {T 1T-1 E R
defined as follows. Let Zozi denote the a-algebra generated by (Z))i= For indices < j. let
Túj
sup [|Pzy.T-1 (A) - AE2..
(4)
V-
For the remaining indices i let Fú = and Taj when i >> (below the diagonal).
Given the dependency matrix from Definition 4.2, we measure the dependency of the process Px by the quantity |[ (Pxx olopp Notice that this quantity always satisfies < ||T (Px X T. The lower bound indicates that the process Px is independent across time. The upper bound indicates that the process is fully dependent, e.g., Xt+1 X, for all e N.
Our results apply to cases where de 1lp) grows sub-linearly in T- the exact require- ment depends on the specific function class P If the process {X₂} is geometrically o-mixing, then ||T (P p>)lepp is upper bounded by constant that depends the mixing-time of the pro- cess, and is independent of [26, Section 2]. Other examples, such as processes satisfying Doeblin's condition [32], given in Samson [26, Section 2]. When {X.} is stationary time-homogenous Markov chain with invariant distribution म, the coefficients Tiş simplify to 17 2sup.Axx.. [ A) <||TV for indices j > i, where X is the o-algebra gener- ated by X (cf. Proposition F.1). Hence, the requirement || dep 1x) Z T for 3 E (0, 1) then corresponds to AE ||xx,( A) TT| & 1/tl-9 for t N4. Jarner and Roberts [33] give various examples and conditions to check polynomial convergence rates for Markov chains. We also provide further means to verify ||T dep (Px))lop = O(1) in Appendix F and Appendix G.
4.2 Learning with little mixing
key quantity appearing in our bounds is martingale variant of the notion Gaussian complexity.
Definition 4.3 (Martingale offset complexity, ef. Liang al. [24], Ziemann al. [15]). For the regression problem (I), the martingale offset complexity of a function space F is given by:
Mr(
sup JEZ
(W.. -15(x))13
(5)
T
Recall that F. = {f.}
= is is the centered function class and ²B(r) = {f F. |Iffl the boundary of the 2 ball Br)). The following theorem is the main result of this paper.
Theorem 4.1. Fix B O, C (0, B) + R4, star-shaped and B-bounded. Let Fr, C F. be r 8-/ee of ²B(r) in the supremum norm II-lloo, and suppose that (F,, Px) satisfies the trajectory (C(r), (1))),aa-hypercomm hee---pperooorrctiviiy condition (cf. Definition 4.1). Then:
[1,2], and
(0, B). Suppose that F.
-T,
BlJ -1F--412 S112, S SEMT (F.) B²
[P| exp
(6)
8C(r)
[ dep (Px) 1
The assumption that F. is star-shaped in Theorem 4.1 is not particularly restrictive. Indeed, The- orem 4.1 still holds if replace F, by its star-hull star (FF) & (</ E [0, E (.F.). and (B(r) with the boundary of the r-sphere of star (F)). In this case, we note that (a) the metric entropy of star(E )) is well controlled by the metric entropy of F and (b) the trajectory hypercontractivity conditions over class F, and its star-hull star F.) are equivalent. Hence, at least whenever we are
PSpecifically, log. No.. (star( (F.). & log(2B/ /E) + No (F., e/2) [34, Lemma 4.5J.
5

---

able to verify hypercontractivity over the entire class F. little generality is lost. While most of our examples are star-shaped, we will need the observations above when we work with generalized linear model dynamics in Section 6.2.
To understand Theorem 4.1, will proceed in series of steps. We first need to understand the martingale complexity term (M.()... Since F. is B-bounded, if one further imposes the tail conditions that the noise process {W;] is a o ---sub-Gaussaan MDS,' chaining argument detailed in Ziemann et al. [15, Lemma 4] shows that:
oi log log + ow How d dyd+ + owr ( Noo s)ds t VT
EMr( inf 720,6E
T
In particular, this bound only depends on P. and is independent of || dep (Px) 1l Furthermore, coincides with the corresponding risk bound for the LSE with iid covariates [24].
Given that EMr( corresponds to the rate of learning from T iid covariates, the form of (6) suggests that we choose ,2 z EMr(3 scale, Given that r has been set, the only remaining degree of freedom in (6) is to set T large enough (the burn-in time) so that the third term is dominated by r². Thus, is this third term (6) that captures the interplay between the function class I. and the dependency measure [[Tdep(P (Pep(PX) llop. We will now consider specific examples to illustrate how the burn-in time can be set.
that the dominant term in (6) is equal to EMr (#F.) in
Our first example supposes that (a) F. satisfies the trajectory (C, 2)-mhypercootractivity condition, and that (b) F, is nonparametric, but not too large:
3p > O, E (0, s.t. N Sp (t) for all E E (0, 1).
(8)
Covering numbers of the form (8) are typical for sufficiently smooth function classes, e.g. the space of k-times continuously differentiable functions mapping X + Y for any k: 2 [dx/2] [35]. If condition (8) holds and the noise process (Wa} is a sub-Gaussian MDS, inequality (7) yields (MM((F.) S T T-rrn and hence we want to set 2 o(T zfo). ). Carrying out this program yields the following corollary.
Corollary 4.1. Fix B
0, E (0. 2), and y E (0, Z0g). Suppose that F. is star-shaped, B-bounded, satisfies (8), and (I.,, Px) satisfies the trajectory (C, 2)-erppercoottruttiiity condition. Suppose that T satisfies:
T 2 max
[8(32p 1)C dep (Px)) 1- (1
4 4log
B
8
log
16
8
+7)
9
(9)
Then, we have that:
Ell fAll22 S SEMT( 27 (22
(10)
The rate (10) of Corollary 4.1 highlights the fact that the first order term of the excess risk is bounded by the martingale offset complexity EMr(F..). This behavior arises since the dependency matrix I' (Pp x) only appears as the burn-in requirement (9). Here, the value of q constrains how
fast || (Px 11pp is allowed to grow. In particular, condition (9) requires that ||T (Pep(P (Px I1lp
o(T 2+2) otherwise the burn-in condition cannot be satisfied for any 7 E (0, 24g))
In our next example, we consider both a variable hypercontractivity parameter C(r) that varies with the covering radius r. and also allow E (1,2) to vary. Since our focus is on the interaction of the parameters in the hypercontractivity definition, we will consider smaller function classes with logarithmic metric entropy. This includes parametric classes but also bounded subsets of certain reproducing kernel Hilbert spaces. For such function spaces, one expects EMT(F.) S Ô(T-1), and hence we set 2 = o1.
That is, for any u gdy-1, A E IR, and E N. we have E(exp(X(W..u)) Fe.1] S 2

---

(1,2), by E 10. by E 20, ? E (0,1), 1), and P.q 2 Suppose that F, is star-shaped and B-bounded, and that for every r (0. there exists a r-net F, of (r) in the -nor such that (a) log Fr plogg (t) and (b) (x) satisfies the trajectory (C(r), a) -npeercccntratttvit condition. Next, suppose the growth conditions hold:
Corollary 4.2. B2BLIC :
(Pxe S TT C(r) S (1/r) Vr E (0,1).
As long as the constants a, by b2, and y satisfy sb == - bj (1+7)14-2a-t) > 0, thenfor any T 2 poly $ (p, log B, $) we have:
2
14+ T
1
Elif f.1L, S SEMT (F.) +2
Here poly./v denotes polynomial of degree O(//v) () in its arguments- the exact expression is given in the proof. Proposition 5.4 in Section gives an example of an (N) ellipsoid which satisfies the assumptions in Corollary 4.2. Corollary 4.2 illustrates the interplay between the function class P.. the data dependence of the covariate process {X+), and the hypercontractivity constant a. Let us consider few cases. First, let suppose that the process {Xe+} is geometrically ergodic and that C(r) is a constant, so that we can set 6y and by arbitrarily close to zero (at the expense of longer burn-in time). Then, the v/ > 0 condition simplifies to > 2 T45' This illustrates that in the hypercontractivity regime (a > 1), there exists a valid setting of (61, b2, 7) that satisfies vp O. Next, let us consider the case where (r) is again a constant, but {X+} is not geometrically ergodic. Setting b2 and y arbitrarily close to zero, we have v > simplifies bj a-1. Compared to Corollary 4.1, we see that in the case when
2, the parametric nature of F. allows the dependency requirement to be less strict: (T)) in the parametric case versus oTT 2²4) in the nonparametric case.
We conclude with noting that when a 1, not possible to remove the dependence on dep (Px) Olop in the lowest order term. In this situation, our results recover existing risk bounds from Ziemann et al. [15]- see Appendix H for discussion.
5 Examples of trajectory hypercontractivity
In this section, we detail a few examples of trajectory hypercontractivity. Let us begin by considering the simplest possible example: a finite hypothesis class. Let |.$1 < co. Define for any fixed f E F,
the constant Cf
+ E [[(())) (E E (1(())I)) where the ratio 0/0 is F. is trajectory (maxfes, Cj, 2)-hhypercontractiive.
2
taken to be 1. Then the class Similarly, processes evolving
finite state space can also be verified to be hypercontractive.
Proposition 5.1. Fix a > O. Let {pe)T denote the marginal distributions of Px. Suppose that the p4's 's all share common support of finite set of atoms (1h,-.., vxx C Rdx, and that minogesT-1 mini SkgK ne ((bx)) 2 p. For any class of functions F mapping { [bkk BRd we have that F satisfies the trajectory (1/p,, (1,,,2)-hppercci 2--hypercomtruuccvity condition.
We remark that when Px is an aperiodic and irreducible Markov chain over a finite state space, the condition μ > 0 is always valid even as T + xo [36]. In this case, our findings are related to Wolfer and Kontorovich [37. Theorem 3.1], who show that in the high accuracy regime (i.e., after burn-in time), the minimax rate of estimating the transition probabilities of such a chain is not affected by the mixing time (in their case the pseudo-spectral gap).
The examples considered thus far rely on the fact that under a certain degree of finiteness, the fourth and second moment can be made uniformly equivalent. The next proposition relaxes this assumption. Namely, if for some E (0, 2] the L" and L norms are equivalent on bounded class 3, this class then satisfies nontrivial hypercontractivity constant, a > 1 (ef. Mendelson [23]).
Proposition 5.2. Fix & E (0,2) and c >>> O. Suppose that F is B-bounded and that || S f|l for all f F. Then F is trajectory (B2-c 1 + e e/2) -nypercontractive.
Next, we show that for processes {Xt} which converge fast enough to a stationary distribution, suffices to verify the hypercontractivity condition only over the stationary distribution. This mimics
7

---

existing results in iid learning, where hypercontractivity is assumed over the covariate distribution [3, 24]. We first recall the definition of the x2 divergence between two measures. Let μ and be two measures over the same probability space, and suppose that μ is absolutely continuous w.r.t. V. The
@ -
(", v) divergence is defined as x²(,, v) - Ey
Proposition 5.3. Fix positive r, Cx2, CTV, and C8-12- Suppose that the process (X+) has a stationary distribution x. Let {uet denote the marginal distributions of (Xe), and suppose that the marginals {ue} are absolutely continuous w.r.t. n. Assume the process is ergodic in the sense that:
sup x2 (4,, T) C2. T = cEN
liee x
1|VV S CTVr..
(11)
Suppose also that for all f E F. (x) S C. 22 (E=1) Then the set 0B(r) satisfies Cr.
(C, 2)-trajectory hypercontracctivity with C = (1+
We further discuss the ergodicity condition (11) in Appendix E.3.1.
Ellipsoids in e (NN. Given that equivalence of norms is typically dinte-ddmeesio phenomenon, one may wonder whether examples of hypercontractivity exist in an infinie-diimensoona setting. Here we show that such examples are actually rather abundant. The key is that hypercontractivity need only be satisfied on an E-cover of F.. As discussed above, every finite hypothesis class (and thus every finite cover) is automatically (C,2))-yperconte ---percoottrattiee for some > The issue is to ensure that this constant does not grow too fast as one refines the cover. The next result shows that the growth can be controlled for e (N) ellipsoids of orthogonal expansions. By Mercer's theorem, these ellipsoids correspond to unit balls in reproducing kernel Hilbert spaces [4, Corollary 12.26).
Proposition 5.4. Fix positive constants 3, B, K, and y. Fix base measure À on X and suppose that JONN is an orthonormal system in (2) satisfying 1 I Bnn, Vn N. Suppose
[ij S -33 and define the ellipsoid: -
Fix e > 0, and 0500 E5=1 Ms S1
let me denote the smallest positive integer solution to m log
subject to log z
B=
Let P C I be an arbitrary subset. There exists an E-Cover P. of in the I-lloc-nom satisfying
log PPll I m. log (1 8Bm? ) Further, let {14 [T] be the marginal distributions of Px and
suppose that maxoş15T-1 max { trajectory (Ce, hyperrcccnttiii with C. (1+7K* B
duc dd S K. Then, as long as E S inffeelllfllee.. Px), 2x dpe
Proposition 5.4 states that when F. C P. then (OB(r), is (C(r), 2)-hypprcontracttiv where C(r) C, only grows poryillgarilmmically in 1/r and thus verifies the assumptions of Corollary 4.2.
6 System identification in parametric classes
To demonstrate the sharpness of our main result, we instantiate Theorem 4.1 on two parametric system identification problems which have received recent attention in the literature: linear dynamical systems (LDS) and generalized linear model (GLM) dynamics.
6.1 Linear dynamical systems
Consider the setting where the process (X, Jizu is described by a linear dynamical system:
X A.X, + HV,, X, = HV. V, E Rdy, Vn ~ (0, V, 1 V/2 tt
(12)
this setting, the system identification problem is to recover the dynamics matrix A, from (X.)7-) evolving according to (12). We derive rates for recovering A, by first deriving excess risk bound on the least-squares estimator via Theorem 4.1, and then converting the risk bound to a parameter error bound. Since Theorem 4. relies on the process being ergodic, we consider the case when A, is stable. We start by stating a few standard definitions.
T-1
Definition 6.1. Fix k E (1...., .t....,dx, dx). rank ([H AH A²H ... A=-1 dx.
The pair (A, H) is k-step controllable if
8

---

For t E N. let the t-step controllability gramian be defined as r, E (HHH(AA) Since the noise in (12) serves as the "control" in this setting, the controllability gramian also coincides with the covariance at time t, i... ] = -r
Definition 6.2. Fix a 2 and p E (0. 1). A matrix A is called (Ttble if for all N we have llop TTp².
With these definitions place, we now state our result for linear dynamical system.
Theorem 6.1. Suppose that the matrix A. in (12) is (T, -)stbblee (cf. Definition 6.2), and that the pair (A., H) is k-step controllable (ef. Definition 6.1). Suppose also that ||A,|| S B for some B 2 1. Consider the linear hypothesis class and true regression function:
runcctooon
g a {f(x) Ar A E Rdxxdx, || S BB), fx(1) A,T.
(13)
Suppose that model (1) follows the process described in (12) with Y; X1+1. There exists To such that the LSE with hypothesis class & achieves for all T 2 To:
Elif f. f.122 S SEM, 41 op
(14)
T
Furthermore, To satisfies for a universal positive constant co:
H 11p op dx
1 (1 (1- polylog B, T,
To Cu (1-p) (1- Nmin 12
122
H|lop: Amin (T' x-1 1 p (15)
Appendix I.4 contains a more detailed discussion about the results in Theorem 6.1. There, we argue that the term EMr( )) in (14) is proportional dl..// implying that the final rate is proportional to the minimax rate, ie., E f.lli= 2 || 11g
6.2 Generalized linear models
We next consider the following non-linear dynamical system:
X = (A)X,) + HV,, Xo = HVo, Ve E Rdx, Vi ~ V. Vt (16)
Here, A, Rdxx is the dynamics matrix and Rddx - Rd is coordinate wise link function. The notation a will also be overloaded to refer to the individual coordinate function mapping IR - R. We study the system identification problem where the link function is assumed to be known, but the dynamics matrix A, is unknown and to be recovered from {X, ) We will apply Theorem 4.1 to derive a nearly optimal excess risk bound for the LSE on this problem in the stable case.
We start by stating few assumptions that are again standard in the literature [20, 31]. Assumption 6.1. Suppose that A., H, and a from the GLM process (16) satisfy:
1. (One-step controllability. The matrix H E xdxxxxx is full rank.
2. (Link function regularity). The link function o R + R is L-pisschitz, satisfies ((0) = 0, and there exists a Ç E (0, 1] such that (a(x)) - a 2 Ç| y) for all x, y E R.
3. (Lyapunov stability). There exists positive definite diagonal matrix P. E BRdx xdx satisfying P. > I and a E (0, 1) such that P.A. % pP..
With our assumptions in place, we ready to instantiate our main result the process (16). Theorem 6.2. Suppose the model (1) follows the process described in (16) with Y, = Xt+11 Assume that the process (16) satisfies Assumption 6.1. Fix a B > 1, and suppose that ||A. S B. Consider the hypothesis class and true regression function:
g A (s(x) = (Ax) A E ddxxds | S BB, fx(x) (A.a).
(17)
There exists To and universal positive constant co such that the LSE with hypothesis class F achieves for all T 2 To:
|1 d
1 1-
Blf f. a < co
log max T, B, dx. |P || 111)))p11p)))
(18)
T

---

Furthermore, for universal constant C1 > 0, we may choose To that satisfies:
[IP. cond( (H)*
To C1 max
polylog
[, Bx,x, P. cond(H))
<<(1 p)
|| op
Ç"
(19)
Further discussion regarding Assumption 6.1 and Theorem 6.2, including more detailed comparison with existing results, can be found in Appendix J.3.
7 Conclusion
We developed a framework for showing when the mixing-time of the covariates plays a relatively small role in the rate of convergence of the least-squares estimator. In many situations, after finite burn-in time, this learning procedure exhibits an excess risk that scales as all the samples were independent (Theorem 4.1). As a byproduct of our framework, by instantiating our results system identification for dynamics with generalized linear model transitions (Section 6.2), we derived the sharpest known excess risk rate for this problem; our rates are nearly minimax optimal after only polynomial burn-in time.
To arrive at Theorem 4.1, we leveraged insights from Mendelson [3] via one-sided concentration
inequality (Theorem B.2). As mentioned Section 4.1, hypercontractivity closely related to the small-ball condition [3]. Such conditions can be understood as quantitative identifiability conditions by providing control of the "version space" (cf. Mendelson [3]). Given that identifiability conditions also play key role in linear system identification setting in which similar phenomenon as studied here had already been reported-this suggests an interesting direction for future work: are such conditions actually necessary for learning with little mixing?
Acknowledgements
We thank Dheeraj Nagaraj for helpful discussions regarding the results in Nagaraj al. [25], and Abhishek Roy for clarifying the results in Roy et al. [13]. We also thank Mahdi Soltanolkotabi for an informative discussion about the computational aspects of empirical risk minimization for generalized linear models under the square loss.
References
[1] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009.
[2] Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes: Upper and minimax bounds. arXiv preprint arXiv: 4825, 2013.
[3] Shahar Mendelson. Learning without concentration. In Conference on Learning Theory, pages 25-39. PMLR, 2014.
[4] Martin J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[5] Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, 22(1):94-116, 1994.
[6] Dharmendra S. Modha and Elias Masry. Minimum complexity regression estimation with weakly dependent observations. IEEE Transactions on Information Theory, 42(6):2133-2155; 1996.
[7] Mehryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for non-i.i.d. processes. Advances in Neural Information Processing Systems, 21, 2008
[8] Ingo Steinwart and Andreas Christmann. Fast learning from non-i.i.d. observations. Advances in Neural Information Processing Systems, 22, 2009.
10

---

[9] Bin Zou, Luoqing Li, and Zongben Xu. The generalization performance of erm algorithm with strongly mixing observations. Machine Learning. 75:275-295, 2009.
[10] Alekh Agarwal and John C. Duchi. The generalization ability of online algorithms for dependent data. IEEE Transactions Information Theory, (9)):333-587, 2012.
[11] John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. Ergodic mirror descent. SIAM Journal Optimization, 22(4):1599-1578 2012.
[12] Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for non-stationary mixing pro- cesses. Machine Learning, 106(1):93-117, 2017
[13] Abhishek Roy, Krishnakumar Balasubramanian, and Murat A. Erdogdu. On empirical risk minimization with dependent and heavy-tailed data. In Advances in Neural Information Processing Systems, volume 34, 2021.
[14] Alessio Sancetta. Estimation in reproducing kernel hilbert spaces with dependent data. IEEE Transactions on Information Theory, 67(3): 1795, 2021.
[15] Ingvar Ziemann, Henrik Sandberg, and Nikolai Matni. Single trajectory nonparametric learning of nonlinear dynamics. arXiv preprint arXiv:220.008311, 2022.
[16] Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
[17] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time identification unstable linear systems. Automatica, 96:342-353, 2018.
[18] Tuhin Sarkar and Alexander Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In International Conference on Machine Learning, pages 5610-5618. PMLR, 2019.
[19] Stephen Tu, Roy Frostig, and Mahdi Soltanolkotabi. Learning from many trajectories, arXiv preprint Stt::2200.179933 2022.
[20] Suhas Kowshik, Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Near-optimal offline and streaming algorithms for learning non-linear dynamical systems. Advances in Neural Information Processing Systems, 34, 2021.
[21] Yue Gao and Garvesh Raskutti. Improved prediction and network estimation using the monotone single index multi-variate autoregressive model. arXiv preprint arXiv:2106. 14630, 2021.
[22] dean-Yves Audibert and Olivier Catoni. Robust linear least squares regression. The Annals of Statistics, 39(5):2766-2794, 2011.
[23] Shahar Mendelson. On aggregation for heavy-tailed classes. Probability Theory and Related Fields, 168(3):641-674, 2017.
[24] Tengyuan Liang, Alexander Rakhlin, and Karthik Sridharan. Learning with square loss: Lo- calization through offset rademacher complexity. In Conference on Learning Theory, pages 1260-1285. PMLR, 2015.
[25] Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithms. Advances in Neural Information Processing Systems, 33, 2020.
[26] Paul-Marie Samson. Concentration of measure inequalities for markov chains and o-mixing processes. The Annals of Probability, 28(1 11:41164461, 2000.
[27] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti. Learning from weakly dependent data under dobrushin's 's condition. Conference on Learning Theory, pages 914-928, PMLR, 2019.

---

[28] Anders Rantzer. Concentration bounds for single parameter adaptive control. In 2018 Anmual American Control Conference (ACC), pages 1862-1866, 2018.
[29] Yassir Jedra and Alexandre Proutiere. Finite-time identification of stable linear systems opti- mality of the least-squares estimator. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 996-1001. IEEE, 2020.
[30] Yahya Sattar and Samet Oymak. aon-asymptotic and accurate learning of nonlinear dynamical systems. arXiv preprint arXiv:2002.088336 2020.
[31] Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Learning nonlinear dynamical systems from a single trajectory. In Learning for Dynamics and Control, pages 851-861. PMLR, 2020.
[32] Sean P. Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, Verlag, 1993.
[33] Søren F. Jarner and Gareth O. Roberts. Polynomial convergence rates of markov chains. The Annals of Applied Probability, 12(1))224-243) 2477, 2002.
[34] Shahar Mendelson. Improving the sample complexity using global data. IEEE Transactions on Information Theory, 48(7)11977-1991, 2002.
[35] Vladimir M. Tikhomirov. e-Entropy and e-Capucity of Sets In Functional Spaces, pages 86-170. Springer Netherlands, 1993.
[36] David A. Levin and Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society, 2008
[37] Geoffrey Wolfer and Arych Kontorovich. Statistical estimation of ergodic markov chain kernel over discrete state space. Bernoulli, 27(1):532 553, 2021.
[38] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL attp://githut com/ hoaa//gooll/////
[39] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018.
[40] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffussion Operators. Springer, 2014.
[41] Jan R. Magnus. The moments of products of quadratic forms in normal variables. Statistica Neerlandica, 32(4):201-210, 1978.
[42] Minwoo Chae and Stephen G. Walker. Wasserstein upper bounds of the total variation for smooth densities. Statistics & Probability Letters, 163:108771, 2020.
[43] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In Proceedings of the 38th International Conference on Machine Learning, pages 2826-2836. PMLR, 2021.
[44] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Online least squares estimation with self- nelf-normalized processes: An application to bandit problems. arXiv preprint arXiv: 2011.
[45] Anastasios Tsiamis and George J. Pappas. Linear systems can be hard to learn. arXiv preprint arXiv:2104.01 /20, 2021.
[46] Randal Douc, Eric Moulines, and Jeffrey S. Rosenthal. Quantitative bounds on convergence of time-inhomogeneous markov chains. The Annals of Applied Probability, 1444) 2004.
[47] Martin Hairer and Jonathan C. Mattingly, Yet another look at harris' ergodic theorem for markoy chains. In Seminar Stochastic Analysis, Random Fields and Applications VI, 2011.
12


Reviews:
[{"review_id": "mYnFGydOieV", "reviewer": "Reviewer_nYrc", "summary": "This paper studies square loss in a realizable time-series framework, the main result shows that whenever a trajectory hypercontractivity condition holds, the risk of least squares estimator on dependent data matches the iid rate order-wise after a burn-in time. The paper formulates a phenomenon called learning with little mixing and presents several examples where such phenomenon occurs. ", "questions": "Can we testify the theory on simple regression problems, empirically?", "limitations": "There is no negative societal impact.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper gives solid theoretical results on learning with dependent data. It shows on a broad class of examples, the LSE applied to time-series model behaves as if all samples are independent given enough data. Although I am not familiar with the background of this problem, the results look insightful. On the other hand, I'd also be curious to see if the theory can be testified empirically on simple regression problems.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "LINI2ZYDscI", "reviewer": "Reviewer_U6WV", "summary": "The authors investigate the square loss in a realizable time-series framework with martingale difference noise, which is an interesting topic in machine learning with non-i.i.d. data. Their main result is a fast rate excess risk bound which shows that whenever a trajectory hypercontractivity condition holds, the risk of the least-square estimator on dependent data matches the iid rate order-wise after a burn-in time. Moreover, the authors give some examples of when the condition holds. I find the main context easy to follow.", "questions": "1. Can the authors provide a more detailed discussion and comparison with the previous related work so that I can make a fair judgement about the contribution of this work?\n2. Can the authors elaborate more on the technical new insight of this work?\n3. Can the authors conduct some numerical studies on this phenomenon?\n4. Line 524: Both sides of this inequality seem to be random variables while the distance, to which the covering number is respect, is expected value, is this a mistake? Or is there any guarantee that this inequality holds with probability?", "limitations": "1. This paper lacks a detailed discussion and comparison with the previous work.\n2. This paper seemed not to give any new insight on this field.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: 1. This paper is technical. It is clearly written and well organized.\n2. The result in this paper is significant.\nWeakness: 1. This paper requires a more detailed discussion and comparison with the previous related work.\n2. There are some confusing mistake in the proof of the main results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "DYjTc0s5JLV", "reviewer": "Reviewer_SNkB", "summary": "The paper shows that for mixing systems under an easiness condition, the rate of convergence of the LSE for rather general hypothesis classes has i.i.d. data like performance.", "questions": "Is it possible to show that, under regularity conditions, for most loss functions, \"learning with little mixing\" isn't too much worse compared to i.i.d. data?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proves excess risk bounds of LSE with dependent data, however the results aren't very surprising, and contributions are a bit too incremental for me.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7OX8I0N8XVo", "reviewer": "Reviewer_AYjz", "summary": "The authors study the problem of learning from dependent data over time, with the aim of obtaining empirical risk minimization bounds that do not depend on the mixing time of the process. They consider a time-series framework with martingale difference noise, and prove a general result: under an assumption they introduce called *trajectory hypercontractivity* (and sublinear growth in the dependency matrix), the risk of the least-squares estimator matches the iid rate after a burn-in time (note the burn-in time can depend on the mixing). This is in contrast to naive bounds where the effective sample size is deflated by a factor of the mixing time. \n\nThe proof relies on using the hypercontractivity to control the lower tail of sums involving the dependent random variables.\n\nThe authors specialize the result both to non-parametric function classes and those with logarithmic metric entropy. They give several examples where their conditions are satisfied (and which recover or generalize previous results): finite-state Markov chains, bounded function classes for which $L^2,L^{2+\\epsilon}$ norms are equivalent, and infinite-dimensional function classes based on subsets of $\\ell^2(\\mathbb N)$ ellipsoids (e.g., functions of bounded norm in a RKHS).", "questions": "* 233: When $\\alpha = 1$, it is not possible to remove the dependence on $\\|\\Gamma_{\\text{dep}}(P_X)\\|_{\\text{op}}^2$ in the lowest order term - Why? Is there a lower bound?\n* 304: Why is a lower bound on the marginal probabilities needed? Is this necessary?\n* 315: What are natural examples where a $L^{2+\\epsilon},L^2$ norm equivalence holds?\n* (23): How is this inequality obtained? The assumption is that $\\|\\phi_j\\|_\\infty\\le Bm^q$ for $j\\le m$, but the terms in the sum are $j>m$.\n\nMinor edits\n\n* 211: hypercontracitity -> hypercontractivity\n* 544: some constant factors as missing in the following inequalities.\n* 549: missing log in following inequality\n* 559: missing inequality $T\\ge T_1,T_2,...$", "limitations": "Certain known results are not covered by the framework, in particular, learning linear dynamical systems that are marginally stable or which have unbounded noise. Additionally, as the max eigenvalue approaches 1, the necessary burn-in time given by the theorem blows up, whereas known results do not have this dependence. (This stems from reliance on rate of growth of the dependency matrix--while the asymptotic rates do not depend on the mixing, the burn-in time does.) The authors discuss this in Section 4.3.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper lies in the fact that it gives a very general result that unites previous results under a general framework, e.g., results on learning linear dynamical systems and finite Markov chains. There is a large degree of quantitative flexibility in the assumption that the authors introduce (trajectory hypercontractivity, which interpolates between boundedness and small-ball behavior). The proofs in the appendix are easy to follow. \n\nHowever, the main body of the paper is technically dense and not easy to digest; the examples are fairly abstract. It would help the exposition significantly to expand on concrete instantiations of the theorem (moving more techical commentary to the appendix as necessary), for example, writing out the theorem for linear dynamical systems obtained from the general theorem.\n\nThere are also some limitations to the theorem (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept