The noise level in linear regression with dependent data
Authors: Ingvar Ziemann
Stephen Tu
George J. Pappas
Nikolai Matni
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning Theory
Learning with dependent data
Time-Series
TL;DR: We provide the first non-asymptotic instance-optimal analysis of misspecified random design linear regression with dependent data---our leading order term is not deflated by slow mixing

Abstract: We derive upper bounds for random design linear regression with dependent ($\beta$-mixing) data absent any realizability assumptions.  In contrast to the strictly realizable martingale noise regime, no sharp \emph{instance-optimal} non-asymptotics are available in the literature. Up to constant factors, our analysis correctly recovers the variance term predicted by the Central Limit Theorem---the noise level of the problem---and thus exhibits graceful degradation as we introduce misspecification. Past a burn-in, our result is sharp in the moderate deviations regime, and in particular does not inflate the leading order term by mixing time factors.

The noise level in linear regression with dependent data
Ingvar Ziemann University of Pennsylvania
Stephen Tu Google Research
George J. Pappas University of Pennsylvania
Nikolai Matni University of Pennsylvania
Abstract
We derive upper bounds for random design linear regression with dependent (3- mixing) data absent any realizability assumptions. In contrast to the strictly re- alizable martingale noise regime, sharp instance-optimal non-asymptotics available in the literature. Up to constant factors, our analysis correctly recovers the variance term predicted by the Central Limit Theorem-thh noise level of the problem-and thus exhibits graceful degradation as we introduce misspecifica- tion. Past burn-in, result is sharp in the moderate deviations regime, and in particular does not inflate the leading order term by mixing time factors.
Introduction
Ordinary least squares (OLS) regression from finite sample one of the most ubiquitous and widely used technique in machine learning. When faced with independent data, there are now sharp tools available to analyze its success optimally under relatively general assumptions. Indeed, non-asymptotic theory matching the classical asymptotically optimal understanding from statistics [van der Vaart, 2000] has been developed over the last decade [Hsu et al., 2012, Oliveira, 2016, 6, Mourtada, 2022]. However, once we relax the independence assumption and move toward data that exhibits correlations, the situation is much less well-understood even for problem as seemingly simple as linear regression. While sharp asymptotics are available through various limit theorems, there are no general results matching these the finite sample regime.
In this paper, we study the instance-specific performance of ordinary least squares in a setting with dependent data and in contrast to much contemporary work on the temme-wthoott imposing realizability. If in addition to a realizability assumption the noise forms martingale difference sequence, now well-known that martingale methods can used to demonstrate that dependent linear regression is no harder than its independent counterpart [Simchowitz et al., 2018) Furthermore, as long as one maintains such an assumption on the noise, a similar observation even holds true for generalized linear and bilinear models [Kowshik et al., 2021, Sattar et al., 2022], and regression with square loss more generally [Ziemann and Tu, 2022].
However, barring any such strong realizability assumption, martingale methods are no longer directly available, and neither are there any sharp non-asymptotics in the learning theory literature. Absent martingale techniques, a natural approach is to use the blocking technique [Bernstein, 1927, Yu, 1994] port concentration inequalities valid for independent data to the dependent setting. However, since blocking effectively reduces the sample size by a factor of the degree of dependence of the data, a judicious application is necessary order to recover the correct noise level of the problem- the level predicted by the Central Limit Theorem (CLT).
A distribution P Px, y is (lincarly) realizable if the regression function x + E|Y X = x] is lincar.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Contributions
This paper serves to explain how the combination of two simple yet powerful observations sidestep the aforementioned issues with blocking. To better appreciate these observations, we recall that the analysis of random design linear regression decomposes into: (1) controlling the lower tail of the empirical covariance matrix; and (2) controlling the interaction between the noise and the covariates.
First, as noted by Mendelson [2014], the dominant contribution to the error rate is due the interaction of the noise with the covariates via the hypothesis class. In linear regression this interaction term takes the form of random walk (see (2.6) and (2.8) below). While one must also analyze the lower tail of the empirical covariance matrix, its contribution to the final error tends to be lower order. This exactly the point: the empirical covariance matrix tends to dominate its population counterpart under very mild assumptions [see e.g. Koltchinskii and Mendelson, 2015, Oliveira, 2016, Simchowitz al., 2018]. Hence deflating the sample size for this purpose by using dependency is of relatively minor consequence and only amounts to an additional burn-in.
Second, turning the random walk-the noise-class interaction term-the above issue with blocking can be remedied if one restricts its use to control only the largest scale of deviation. This observation can be traced the moderate deviations literature, but does not seem have made its way into the learning theory literature [see e.g. Merlevède et al., 2011]. To explain this idea, let us recall Bernstein's 's inequality: for b > O, 8 E (0, and sequence of E N iid mean zero b-bounded scalar random variables VISR.
EV? In(1/5 E
4blog(1/8)
Σ T1
V12 2V
6.
(1.1)
n
3n
In the moderate deviations bandwidth (6 2 exp(-nEV? /b)), the leading term of (1.1) is exactly
of the expected order, seen from a central limit heuristic: / /B (m(1/8) Assume now for sake of
argument that A N divides and set m n/k. Applying (1.1) instead the bk-bounded variables Vim, V. - D = - Vi we find instead:
1
k E(V (
4bk log(1/)) 3n
P
Vi 2 2
S 6.
(1.2)
The (normalized) variance of iid random variables tensorizes nicely (k (k- E(V1)² =V}}), and so the only difference between (1.1) and (1.2) is that the large deviations term has been inflated by a factor k. More generally, however, (1.2) remains valid as long every & samples are blockwise independent. The leading term of (1.2) already captures the correct variance term in the blockwise independent, mne-iimenioonal and bounded setting.
The above two paragraphs illustrate the core of our argument: by combining the above two ob- servations we can entirely relegate any dependence on mixing to additive burn-in factors. In the sequel, we produce a more general version of this argument. To allow for arbitrary dimensions and handle unbounded processes, we first replace Bernstein's 's inequality with a corollary to Talagrand's inequality due to Einmahl and Li [2008]. To allow for 3-mixing processes, we replace the blockwise independence assumption with the blocking strategy of Yu [1994]. By combining with control of the lower tail, which as noted above holds under mild assumptions, this leads to our main result Theorem 3.1, captured informally below.
Informal version of Theorem 3.1. Pust a mild burn-in, polynomial in relevant problem quantities including the B-mixing coefficients of the data, and for a failure probability ö E (0, 1). OLS with -in-dimensional targets and dx-dimensional covariates enjoys the following excess risk guarantee:
0² (dx log((/6))
Excess Risk (OLS) S
(1.3)
n
Moreover, the term o² in (1.3) accurately captures the noise level of the problem solely via the relevant second order statistics; it is not inflated by any mixing times.
The crux of this result that past burn-in, the OLS excess risk does not directly depend on mixing times, but only on the relevant second order statisties. Put differently, the effect of slow mixing has

---

been relegated to small additive term with higher order dependence on 1/n. This stands in stark contrast the usual invocation of the blocking technique where the effect of mixing typically enters multiplicatively, thereby degrading the rate of convergence uniformly across all sample-sizes and past any burn-in times [see e.g. Steinwart and Christmann, 2009, Kuznetsov and Mohri, 2017, Wong et al., 2020, Roy et al., 2021].
Applicability. Before we proceed with the main development, we remark that the class of 3-mixing is quite broad; few examples where Theorem 3.1 can be instantiated are as follows:
all ø-mixing processes are 3-mixing [Doukhan, 2012],
stationary uniformly ergodic Markov chains are 3-mixing,
stationary Gaussian vector autoregressive moving average (ARMA) processes
B-
mixing [Mokkadem, 1988],
many other sub-classes of GARCH models, often studied in the economics and finance literature, are 3-mixing [Carrasco and Chen, 2002].
The list is far from exhaustive and further examples can for instance be found in Doukhan [2012]. The stationarity assumptions above also typically be dropped. We also point out that it is precisely because we can handle misspecification that our result is of interest for many of these examples.
Outline. The rest of this article is structured follows. Section 2 fixes notation and yields more formal problem formulation. We provide our main result, Theorem 3.1, in Section 3. After stating our main theorem, we highlight its features and then proceed to compare it to related work in Section 3.1. We outline the proof of Theorem 3.1 and provide supporting results in Section 4, including separate analyses of the noise-interaction and the lower tail of the empirical covariance matrix. Section 5 concludes and technical details are relegated to Appendix A.
2 Preliminaries
Expectation (resp. probability) with respect to all the randomness of the underlying probability space is denoted by E (resp. P). For two probability measures P and Q defined on the same probability space, their total variation denoted |P Q|[TV. Maxima (resp. minima) of two numbers b E IR. are denoted by a V b = max(a, (a,b) b) (resp. A b = min(a, b)). For an integer E N, we also define the shorthand [n]] nl.
Notation.
The Euclidean norm on Rd denoted || ||2. and the unit sphere in Rd is denoted gd-1, The standard inner product on Rdd is denoted (,.) We embed matrices M 1ddixda in Fuclidean space by vectorization: vec M E Reids, where vec is the operator that vertically stacks the columns of M (from left to right and from top to bottom). For matrix M, the Euclidean norm is the Frobenius norm, i.c., || || - ve ||2.. We similarly define the inner product of two matrices M, N by NM _ (vec M, vec N). The transpose of a matrix M is denoted by M and if M is square tr M denotes its trace. We also write || al for the induced (R4 [|2] + (Rd || l12) norm. For two symmetric matrices M, N, we write M N (M > N) if M N is positive (semi-)definite If M is positive semidefinite we write θM & {x Rd induced by M (note that gd-1 Ala).
and
x T Mx 1} for the boundary of the ellipsoid
Problem Formulation. We are given n input-output tuples: X ~ P.K. (taking values in Rdx) and Y1m ~ Pl (taking values in IRdy). Using these samples, the goal of the learner is to estimate the best linear hypothesis:
M. E argmin M ME xáx
E - MX
(2.1)
where the distributions of X and in (2.1) are specified via:
1
Y ~ 1
X ~
PX
and
PY
(2.2)
3

---

Note that (2.2) is equivalent to sampling from the uniform mixture over (X1s,, Yim) with the index i [n) sampled uniformly. The operator Σx E[XXT] is the averaged covariance operator (with X as in (2.2)). The excess risk of a linear hypothesis M can then be written as:
Excess Risk (M) e B|ly 1 E 2 II M.) Ex
(2.3)
We now define the noise variable W, P Y; M, but, as mentioned above, do not impose any (conditional) mean zero assumptions on the noise. To simplify the exposition, we will henceforth assume that Σx > O, but our results easily extend to the case Σx > 0 by restricting attention to the span of Σx. With these preliminaries in place, on the event that the design is nondegenerate, the OLS and its error equation can be specified as follows:
M A
Σ yX!
Σ xXXX]
- M-M,, M.
Σ WiX!
(=xxT)"
Exxx
(2.4)
Our task in the sequel is to establish that the choice M renders the excess risk (2.3) small. We note in passing that M is empirical risk minimizer:
72 Σ
M argmin MERly Xáy
|.
MX,
71
The Noise Term.
Let us also define the following prefiltered noise-class interaction variables:
V/ a WxX,'xx'2 i [n].
(2.5)
The square of the following (weighted and possibly biased) random walk effectively characterizes the noise level in our problem:
S 4
V,
(2.6)
We remark that by construction ESS, 0 using the optimality of M, in (2.1). To see this, simply in- voke the optimality equation for M, and note that d induces a convex class in the corresponding 7,2-space over the mixtures (2.2). Note however that the increments of (2.6) are not necessarily mean zero unless X1.. and Yi.. are stationary. However, since E.,, O, we also have with V. A V; EV;
S,
V.
(2.7)
In light of (2.4) and (2.6), we have that the empirical excess risk depends on the norm of:
1
M Ex S,
Sn
(2.8)
n
Hence, we need to control the random walk in (2.7) and the lower tail of
n Σ
x
(2.9)
the prefiltered empirical covariance matrix. mentioned previously, lower uniform laws for (2.9)
are valid under mild assumptions [Koltchinskii and Mendelson, 2015, Oliveira, 2016), and blocking such results does not incur more than worsening of the burn-in. Hence, the noise level of the problem is very much dictated by the random walk (2.6).
3-mixing and the Blocking Technique. the sequel we demonstrate that the standard blocking device combined with (functional) version of Bernstein's 's inequality allows us to pass the distribu- tional (or coarse) measure of dependency to a higher order additive term, yielding non-asymptotic rates consistent with the CLT described in Section 1. We will also use blocking to derive our lower uniform law, controlling the lower tail of (2.9). To make these ideas rigorous we require the following standard measure of dependence (take Zi. (X,Y)1., below).

---

Definition 2.1. Let Zim be stochastic process. The B-mixing coefficients of Z, (i), are: P P
(z(1)
sup
E||p 2. I
E [n].
(2.10)
Intuitively, the coefficients 3z in (2.10) measure the dependence at range of the process 7 This mcasurement is done in total variation distance by comparing the distribution of Zt+4 with the conditional distribution Zt++ Zia. More concretely, the notion of 3-mixing allows us to use the blocking technique Yu [1994]. This technique splits the process Zi: into blocks, such that every other block is approximately independent, leaving us with two separate processes, consisting of odd and even blocks, that are almost independent (see (4.1) below). One then proceeds to use B-mixing to construct a "parallel" probability space, approximating the original one, but in which the odd and even blocks are independent. The price we pay for this measured in terms of the coefficients (2.10). The essence of this idea-to use that data points sufficiently separated in time are often roughly independent- can be traced back to Bernstein [1927]-
3
Main Result
To give our main result for general target dimension we require one last preliminary notion. Given a d-dimensional square, symmetric positive semidefinite matrix M Raxd we say that its effective dimension is edim (M) & tr M/lpp Our main result is the following theorem.
Theorem 3.1. Fix 8 E (0, 1) and n, m E with 2m S n. Let a1:2m be a monotone partition of [n] such that if k E 04, 1 E 0gz, and i >> j. then k >> I holds. Set Omax E (e (qyl- Fix also B-mixing sequence Y) of which each element admits at least that there exists a positive number h E R such that for every v E xΣx and i E [n]] we have that E(c,X,) & (1² (1,,E[, Define also the noise interaction terms:
[4, 00) moments. Assume
2m Σ
E
Σ, E vec
Σ V2
vec
Σ V
0² 2
||llop
(3.1)
n
jEa,
JEa,
There exist universal positive constants C1, C22 C32 C4, C5 such that with probability at least
- 8:
II M.) Ex q (edim(2) + log(1/8))
(3.2)
as long as the following burn-in conditions hold:
2/a
n
2 C2(1x + h² 12
T2.
1-2/8
2
Cz8²
778
2m
E
Vlemax
Ejea,
Vj
Amax
Amax
edim 282//
(3.3)
Eie(2m)n22 [asl
Eee(e))((2N-)) laol < C4:
Σ
C5 Σ2 1
Σ
Σ
En;
se xe[2m]n(2N-1)
se de[2m]nau n2N
ie xe[2m]n(aN))
(3.4)
2m
Σ (lall S coo;
(3.5)
2
and where Bx,y are the 3-mixing coefficients of Y,,Y)
To interpret Theorem 3.1 we proceed with a sequence of remarks, discussing its features. These remarks also serve to parse the terminology above and lead to simplified statement for stationary data and 1-dimensional targets. We present this simplified version as Corollary 3.1 below.
The dimensional scaling in (3.2) is captured by the effective dimension term edim(2), which always lies in the interval [1, dydy]. For one-dimensional targets and benign noise interaction, and since the X; in the noise term V; have been whitened (see (2.5)), expect E to be roughly isotropic. Indeed, whenever dy = 1, the trivial bound edim( (Σ) S dx produces the familiar
behavior: ||M M.)vEx 2 < dddx/ dx/n with high probability.
5

---

The scaling with dx, dy, o² and n thus scales as expected in the iid regime, but also degrades gracefully with dependence. We reiterate that (3.2) does not depend directly on mixing in the leading order term. For comparison, under suitable regularity conditions, the noise term predicted by the CLT is:
ECLT A limsup E vec Σ Vj
vec Σ
V
(3.6)
n=000
and one can achieve Σ ECTT o(1) in most situations of practical interest by tuning the block-length; therefore, our analysis of OLS essentially matches the optimal asymptotics.
Moreover, the constant ej appearing in (3.2) is quite benign and can be made arbitrarily close to 2 by suitably inflating our burn-in constants c C3, Ca, C5 Gg. We have however not been able to approach the optimal leading constant 1 in front of adim(E). This can be traced to an application of the triangular inequality in Corollary 4.1.
The moment bound Eu, X,) < (u, Jux (v E 0Xx) is easily satisfied for e.g., Gaussian bounded processes but is of course much milder than either assumption. The assumption that 8 2 4 can be relaxed to 8 > 2 by replacing our result controlling the lower tail, Theorem 4.3. We have chosen present our result for s 2 4 to strike a balance between expositional clarity and generality.
The first burn-in condition of (3.3) is standard for control of the lower muil-beside the deflation factor |amax) it is necessary even for iid data to guarantee that the "denominator" (2.9) is nonsingu- lar. The second condition of (3.3)- in which a ratio of s:th and 2nd moment of the noise variable appears-is the price we pay in the moderate deviations bandwidth for only having moments: it controls the rate at which the random walk (2.6) approaches asymptotic normality and reduces to the condition of Oliveira [2016] in the iid regime. This latter condition can in principle be removed with slightly modified constants if sufficiently many moments of the data-generaate process satisfy a sub- Gaussaan type moment equivalence condition (in which case the above-mentioned ratio is constant). Without such an assumption, we note that some polynomial dependence on 1/6 is necessary under our tail assumptions and is not an artifact of our analysis; OLS is not deviation- optimal in the entire range of å E (0. du- to the presence of the random walk (2.6) in the numerator-unde unless the noise variables have Gaussian-like tails [cf. Mendelson, 2018, Section 6.4].
The conditions in (3.4) and (3.5) relate to dependence. The last condition (3.5) simply asks that our process mixes sufficiently fast. If the mixing coefficients Bx.y (Jaal) are exponential, this amounts still handle slow, polynomial mixing rates, at the
to a logarithmic burn-in in 1/8. However, cost a polynomial burn-in in 1/6. The conditions in (3.4) asks that the odd and even blocks are balanced in terms of their length and second order statisties. It is trivially satisfied for (weakly) stationary processes analyzed using a uniform blocking length (length of the 0z).
In light of the above remarks, we are now in position to simplify Theorem 3.1. If we impose stationarity, quite a few terms in the burn-in conditions (3.3).(..4) and (3.5) either simplify or vanish. Further restricting to the case where targets are 1-dimensional and letting the sample-size be divisible by the block-length yields the corollary below.
Corollary 3.1. Fix å E (0, 1) and n, E N and let 27 divide n. Fix also a joint distribution of 1 1-dimensional targets and dx dimeensiiin covariates P.XYY with at least E [4, oo) moments. Let )) i. be a stationary 3-mixing sequence with marginals equal to pX,. Assume further that there exists a positive number h E R such that for every v E 0.x we have that E(v, X) < h [E (V,,)) 27
where X ~ px_ Define also the noise interaction term: o² & suppessx
There exist universal positive constants C1 C22 C3, C4 such that with probability at least 1 8:
[I -M) c10² (dx + log(1/8))
n
as long as the following burn-in conditions hold:
v. 1/1l3) 2/s
2 c2 + h2 log log(1/)));
(5)
12 1-2/s
2
C35
E
Vrdx
n 3xxy S cj.
0282/8
(3.7)

---

Corollary 3.1 takes a very similar form to by now standard results in the iid regime [Hsu et al., 2012, Oliveira, 2016]. Indeed, if the data is stationary the price we pay for dependence is that:
variance and moment terms need to be computed in blocks;
the burn-in is deflated by factor of the block-length (the first two parts of (3.7)); and
we incur an additional burn-in penalizing slow mixing-the last part of (3.7) asks that the block-length is not "too small".
3.1 Comparison to Related Work
Having established our main result, Theorem 3.1, we now provide a more detailed comparison to the relevant literature. Most closely related to results is Nagaraj et al. [2020], who study bounded linear regression models in which the data comes from an exponentially ergodic Markov chain. They find that strictly realizable linear regression is harder than its iid counterpart in this setting, and show that a parallelized gradient algorithm achieves the optimal rate. More interestingly, in the absence of realizability, they also establish lower bound demonstrating that the worst-case (global minimax) excess risk across all Markov chains with a given mixing time is deflated by said mixing time, thereby establishing a gap between realizable and non-realizable learning from dependent data.
Of course, their lower bound is no longer valid if one drops the requirement that the predictor performs uniformly well across all distributions with a prescribed mixing time. It is exactly herein that our analyses differ. While Nagaraj et al. [2020] characterize the worst-case (or global) complexity of linear regression, compete against the worst distribution at a given level of mixing, whereas we compete against fixed distribution. To appreciate this distinction, let momentarily assume that dx dy 1. The noise term x² in Theorem 1 can be upper-bounded as:
focus on the instance-speciffe (or local) complexity. In other words, they
)1=
2m E
0²
ΣE
Vg
S
max lasl- max EV? #E[2m] /E|n]
(3.8)
jEa;
inequality. The right hand side of (3.8) precisely inflated by the (maximal) by the max4e[2m) |ay)- block-length
Seen in this light, our results being sharper in terms of the measure of dependency reduces to stating that our results are sharper by an application of the Cauchy-Schwarz Inequality. Moreover, the statement that the global complexity worse than its iid counterpart by factor of the mixing time amounts in our setting to stating that there exists a distribution achieving equality in (3.8). We remark that such a distribution is easily constructed by taking X i.n. and Yu. be constant within each block and stationary across the blocks; this is precisely when the application of the Cauchy- Sehaa-S inequality in (3.8) turns equality. To further appreciate the distinction between our results, note that our result measures dependence through correlation. By contrast, result scaling with the mixing time measures dependence in a stronger variational sense. That is, the former measures dependence at the level of orthogonality of the random variables themselves, whereas the latter measures it at the level of orthogonality of all measurable functions of these random variables.
Further Related Work. Another closely related line of work studies parameter identification in auto-regressive models [for recent survey, see Tsiamis et al., 2022]. When the noise model is strictly realizable- the variables Wi.. form a martingale difference sequence with respect to the filtration generated by $1m=iientification is possible at the iid rate even in the absence of mixing [Simchowitz et al., 2018, Faradonbeh et al., 2018, Sarkar and Rakhlin, 2019]. Naturally, our results do not cover the mixing-free regime as we consider: (1) the agnostic setting in which self-normalized martingale arguments [Peña al., 2009, Yadkori et al., 2011] are not available; and (2) excess risk bounds instead of parameter identification it seems unlikely that (3.2) holds without some notion of stochastic stability due to the presence of Σx on the left hand side.
More generally-moving beyond linear time-series models-severt authors have considered learning under various weak dependency notions. Kuznetsov and Mohri [2017] give generalization bounds in a more general setting using the same blocking technique- to Yu [1994] used here. Statements similar in spirit can also be found in e.g., Steinwart and Christmann [2009], Duchi et al. [2012] and
7

---

most recently Roy et al. [2021]. However, they all suffer the dependency deflation discussed above and in our introduction (Section 1). We also note that Ziemann and Tu [2022] obtain rates for strictly realizable square loss that sottssmilar to ours here-relegate mixing times into additive burn-in factors. While they treat more general hypothesis classes, they do not go beyond strict realizability, and their analysis rests on the assumption that the noise interaction term is a martingale difference sequence.
Proof Overview
Theorem 3.1 is the direct consequence of two separate results: Theorem 4.2, which controls the centered noise (2.7) term, and Theorem 4.3, which bounds the lower tail of the normalized empirical covariance matrix (2.9). We prove Theorem 4.2 by blocking the Fuk-Nagaev inequality of Einmahl and Li [2008], and Theorem 4.3 by truncation argument combined with blocking. These results are found in Section 4.2 and Section 4.3. Our proof idea is heavily inspired by that of Oliveira [2016] and the idea is very much to adjust his approach in such a way that blocking does not affect the leading term in the rate.? ? As either result relies on blocking, it is now pertinent to describe this technique in little more detail.
4.1 Blocking
Recall that we partition [n] into 2m consecutive intervals, denoted aj for j E [2m], so that
E layl = n. Denote further by O (resp. by E) the union of the oddly (resp. evenly) indexed subsets of [n]. We further abuse notation by writing (2(a,) B2((a,)) in the sequel.
We split the process Zum as:
Zojo & (Za
Zigm-1))
(Zozr-.. ... Zazm). )-
(4.1)
Let 20,0 and /a be blockwise decoupled versions of (4.1). That we posit that Z0
1:101 ~
P 2%
and Z
P Pže where:
Pz,,
& Pzng
P2 PZozm-1 and P P2jja
A Pzez 2 PZ.,
8 ... 2 PZozm
(4.2)
The process ZIn with the same marginals as Z and 2 is said to be the decoupled version of
Zi.. To be clear: P A Pz., Pzug 8 ... @ P Pzuzmm S0 that Zi:00 and Zi,E are alternatingly embedded Zı.. The following result is key-byy by skipping every other block, Z1. may be used in place of Zin for evaluating scalar functions at the cost of an additive mixing-related term.
Kuznetsov and Mohri [2017]). Fix 3-mixing process Zum and let Zum be its decoupled version. For any measurable function of Zio01 (resp. g of (i) with joint range [0, 1] we have that:
Proposition 4.1 (Lemma 2.6 Yu [1994]; Proposition
B(f(Zi)))) - E(f(Zi
Σ
Bz(as),
(EE((2m)
(4.3)
((g(Zi))) E(g(2i
Σ
(z(a,)
:EOV(1)
The following corollary to Proposition 1.1 convenient for controlling norms of random walks.
Corollary 4.1 (Lemma in Kuznetsov and Mohri [2017]). Let Zi.n be a B-mixing process taking values in a normed space (Z []), and let Zim be its decoupled version. For any
At high level, for iid data, this proof strategy first appeared in the journal version of Oliveira [2016].

---

11
iE
2.
E
EiEg
Z.1
we have that:
0
E
P
Σ 4
7
32(ai)
+P
Σ iEO
2
E
Z
+
+P
1
Σ iEE
74
E
1
Z4
+e
0
00|
E
E
iEO
SEB
(4.4)
where E, = E
Eieo 2,
and Ee = E T
EiE F
2,
In short, up mild failure additional failure probability term, we only need control the tensor product processes (4.2).
4.2 Dependent Random Walks
Once equipped with Corollary 4.1, we still require control of the independent blocks. The following Fuk-Nagaev inequality due to Einmahl and Li [2008] provides such control.
Theorem 4.1 (Theorem 4 in Einmahl and Li [2008]). Fix 2, a separable normed space (U II) and a U-valued sequence Umn of independent random variables. Assume that E||U;i|* < 00 for i [n]. Then for any & E (0, oc). n E (0, 1I. and 2 O, we have that:
P
max kEim
Σ U
(1 + E
Σ U
+ (1 + 9E)t (1+92)t
i=1
12
S exp
+ Ce...
(4.5)
(2 + n)A (2+m)A)
t
where A A supee g. Moreover, we may take Ce,n,- = (1 (2s/e)2=(2())) + (3 + 4/n))² + =))))
E (U,) and where 5 is unit disk in the dual space of (U,
II).
If our data were drawn independently. Theorem 4.1 would give us the required control of the random walk (2.7). The right hand side of (4.5) consists of a mixed tail: (1) nub-Gaussian term with a CLT-like weak variance term A; and (2) a polynomial term accounting for the fact that we only imposed the existence of s moments. With the preliminary results Corollary 4. and Theorem 4.1 in place, we are now in position to control dependent random walks of the form (2.7).
Theorem 4.2. Fix & > 2, a separable normed space (Z, |- II), constants E, > 0, and set Cen,, = (2s/e)))) + (3 + 4/n))² + Fix also a consecutive partition 01:2m of [n] and let Zim be mean zero, 9-mixing process taking values in Z with block decoupled version Zi Let O be the union of the odd a; and E be the union of the even üg Assume that E| 2.11" < for i [m]. For every E, 77 > 0 and ō E (0, 1), we have that:
Asgn sgn
P
Z
>
max OO
V
(11+2n) (1+22))F+(0 9c) (2+ log(1/5)
1=1
2m
Bz(a;) + Ce.no(1 9=) p2/27p
E
Σ Jea Zj
< 28
(4.6)
Isgn 1/2 Ag/2
sgnE EE (E(2m):a, Cagn
where Asgn A sup [sgn]
Σ Za.Con Caga
Ev²
Σ Ejea: Zi) for sgn E E3, gp is unit disk in the
E
Eier Z
dual space of (z.
|l (), and /r 2 max.ne((O.F)
Augii
'The constant Ca,p.a is not specified exactly in Einmahl and Li [2008]. This constant is easy to obtain by observing that their K2, which may be taken to be the best constant such that (logx)²* < K, for 2 1. is upper-bounder by (2s/e)2s.

---

In Theorem 4.2 we have combined the blocking technique with the Fuk-Nagaev inequality (4.5). The right hand side of (4.6) exactly as in (4.5) but instantiated our setting and with extra additive mixing-related term.
4.3 The Lower Tail of the Empirical Covariance Matrix
We now proceed to analyze the lower tail of the empirical covariance matrix (2.9).
Theorem 4.3. 6 and consecutive partition a 1:22m of (n). Let Xum be a sequence of 3-mixing random variables taking values in R with finite fourth moment. Assume that there exists a positive number h E E such that for every xEx and E [n], we have E(v,X.) 4 S (e, E(x, There exists a positive universal constant
such that as long as
2m-1
8 2¹
n 2 C
max layl(dx + h2 log(1/6)) and [2
Σ 1=2
8x (x(a:)
(4.7)
then
P
Vu E Rd
uu x
1 2n
Eu, x,)
2 1 - 5.
(4.8)
It is by now well-established fact that lower uniform laws of the form (4.8) hold under mild assump- tions for various function classes (linear functions on R this case). Since these assumptions are quite mild and only affect burn-in conditions, deflating the sample-size via blocking does not deflate the final convergence rate. The particular approach we have chosen here to establish Theorem 4.3 to combine blocking with the approach found in [Wainwright, 2019, Theorem 14.12]. We remark that similar statements hold if one instead blocks the arguments of say Oliveira [2016] or Koltchinskii and Mendelson [2015].
5 Summary
The leading order term of our main result, Theorem 3.1, does not directly depend on any mixing-tine time type quantities. It mimics the asymptotic rate and scales solely in terms the second order statistics of the process at hand. To arrive at this result, we rely on two facts:
The lower tail of the empirical covariance matrix (2.9) well-behaved under mild assump- tions. In excess risk bound, the contribution of the lower uniform law to the overall error is not of leading order. Hence, incurring a sample size deflation for this purpose not critical.
By combining blocking with version of Bernstein's inequality, we able to push the effect of blocking to only affect the large deviations regime. In the moderate and small deviations regimes, control of the leading order of the random walk in (2.7) is not directly impacted by slow mixing.
Acknowledgements
Ingvar Ziemann is supported by a Swedish Research Council international postdoc grant. Nikolai Matni is supported in part by NSF award CPS-2038873, NSF CAREER award ECCCS-044834, and Google Research Scholar award. The authors thank Bruce Lee for comments on an earlier draft of the manuscript.
References
Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Serge Bernstein. Sur l'extension du théorème limite du calcul des probabilités aux sommes de quantités dépendantes. Mathematische Annalen, 97:1-59, 1927.
10

---

Marine Carrasco and Xiaohong Chen. Mixing and moment properties of various garch and stochastic volatility models. Econometrie Theory, 18(1):17-3, 2002.
Paul Doukhan. Mixing: properties and examples, volume 85. Springer Science & Business Media, 2012.
John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-1578, 2012.
Uwe Einmahl and Deli Li. Characterization of lil behavior in banach space. Transactions of the American Mathematical Society, 360(12))6777-6699 2008.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time identifica- tion in unstable linear systems. Automatica, 96:342-353, 2018.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference learning theory, pages 9-1. JMLR Workshop and Conference Proceedings, 2012.
Thierry Klein and Emmanuel Rio. Concentration around the mean for maxima of empirical processes. The Annals of Probability, 1360))106-11077, 2005.
Vladimir Koltchinskii and Shahar Mendelson. Bounding the smallest singular value of a random matrix without concentration. International Mathematics Research Notices, 2015(23):12991- 13008, 2015.
Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. Near-optimal offline and streaming algorithms for learning lineli dynamical systems. In Advances in Neural Information Processing Systems, volume 34, pages 8518 2021.
Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for non- con-stationary mixing processes. Machine Learning, 106(1):93-117, 2017.
Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pages 3-17. Springer, 2016.
Shahar Mendelson. Learning without concentration. Conference on Learning Theory, pages 25-39. PMLR, 2014.
Shahar Mendelson. Learning without concentration for general loss functions. Probubility Theory and Related Fields, 171(1-2):459-5 502, 2018.
Florence Merlevède, Magda Peligrad, and Emmanuel Rio. A bernstein type inequality and moderate deviations for weakly dependent sequences. Probability Theory and Related Fields, 151:435-474 2011.
Abdelkader Mokkadem. Mixing properties of arma processes. Stochastic processes and their applications, 29(2):309-315, 1988.
Jaouad Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. The Annals of Statisties, 50(4)21157-2178, 2022.
Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli, Least squares regres- sion with markovian data: Fundamental limits and algorithms. Advances in Neural Information Processing Systems. 33, 2020.
Roberto Imbuzeiro Oliveira. The lower tail of random quadratic forms with applications to ordinary least squares. Probability Theory and Related Fields, 175 2016.
Victor H Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer, 2009.
Abhishek Roy, Krishnakumar Balasubramanian, and Murat A Erdogdu. On empirical risk minimiza- tion with dependent and heavy-tailed data. Advances in Neural Information Processing Systems, volume 34, 2021.
11

---

Tuhin Sarkar and Alexander Rakhlin. Near Optimal Finite Time Identification of Arbitrary Linear Dynamical Systems. International Conference on Machine Learning, pages 5610-5618, 2019.
Yahya Sattar, Samet Oymak, and Necmiye Ozay. Finite sample identification of bilinear dynamical systems, In 2022 IEEE 61st Conference Decision and Control (CDC), pages 6705-6711. IEEE, 2022.
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.
Ingo Steinwart and Andreas Christmann. Fast learning from non-i.id. observations. Advances in Neural Information Processing Systems, 22, 2009.
Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George Pappas. Statistical learning theory for control: A finite sample perspective. arXiv preprint arXiv:2209.05423; 2022.
Aad W van der Vaart. Asymptotic Statistics. Cambridge university press, 2000.
Martin J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam-
bridge University Press, 2019.
Kam Chung Wong, Zifan Li, and Ambuj Tewari. Lasso guarantees for β-mixing heavy-tailed time series. 2020.
Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, 22(1):94-116, 1994.
Ingvar Ziemann and Stephen Tu. Learning with little mixing. In Advances in Neural Information Processing Systems, volume 35, pages 4626-4637, 2022.
12

---

A Proofs
A.1 Proof of Theorem 4.2
Let Zum be the block-decoupled version of Zim Let sgn E E}. For i O we define U, Ejen 23 and similarly for E we define U; TET Σ jEa, 2z.
In light of Corollary 4.1 to control P (I E Z:
> u) it suffices to control
2
S
2
+ Usgn
sgn
sgn
1Esgn
sEsgn
for both sgn E F} and where Uegn
Σ
DiEsgn
Introduce now the change of
Isgm
2. 2.1)
variables (1 96) Msgn
Usgn
E
legni
Evesgn
We invoke Theorem 4.1 twice; we do so once for the even blocks and once for the odd blocks. This
yields for sgn E {0, } that for any (0, o0), E (0, 1] and fgn 2 we have that:
P
2.
< (1+
Zx
+ (1 + 95)
isgn
sgn
sEsgn
EEsgn
|sgn| sgn
E
Σ jEa, Zj
S
exp
Can
(A.1)
(2 + 1))
|sgn
$15
agn
B1 Csga
with Ago announced and where we used that Ejecs Z is equal to Ejeas Bg in distribution for every [n].
Consequently, with u = (1-95)(sgn) + +(1+n) together yield that:
Ign Eiegon 2.1 we find that (A.1) and Corollary 4.1
2m 11
P
2
u1
<
32(a:)
1=2
Σ jEa, Zj l
Isgn| sgn
E
Σ
exp
Cem.
(A.2)
(O
(2 + Aggn
ne Cagn
Iggn
sgn
where summation over a; C sgn is restricted to a1:2m- for some c >>>> we choose
cV (2 17) log(1/5)
tgn
max (O,E)
Agga
ssgn|
Erem
and VF 2 max.gn (0.E)
then (A.2) reads for either sgn E (0,
Aggn
P
Z
max (O,
(1+92) (L+
VCv 11)+n))og (og((/0))
71
sgn
2mm
Cen 0/121
Σjea, Z
Can c 1
E
Σ Σjer, Z
Σ Bz(as)
+8
Ag
A x/2
1=1
a:co
C.C E
E
The result follows if we choose TTT2/(L 92)
13

---

A.2 Proof of Theorem 4.3
We will argue by truncation. This rests on the observation that for any sequence Pim of measurable sets:
Exxx = EXITIRR iE@
(A.3)
iEa
where before we let C [n]. The idea is that once we truncate do not have to worry about the upper tail the empirical covariance matrix. We begin by showing below that well-chosen level of truncation still preserves most of the mass of the lower tail.
A.2.1 Truncation step
We will want to choose the events F; to be constant across each block. We require the following simple observation. It states that the moment condition E(u, X,) s (2, E(X,XTjo) extends
naturally to the situation where each block is our basic unit of randomness.
Lemma A.I. Under the hypotheses of Theorem 4.3 for every subset C [ri] we have that:
E
(0, x,)²
h²²
1 [a
E(c,
a
Proof. By direct calcuation:
2
E Σ (v, x7,3
Σ
Ev, X,)
(Cauchy- (chch-)Schhar))
iea
< h
E(u, X:)3
X,) ("o,
(A.4)
iEa
< h2 |a]
Evu X.)
(Cauchy-Schwarg
To finish the proof, divide both sides of (A.4) by la|2.
As announced above, let now the F, be constant each block [n]. In what follows, abuse notation in the obvious way and write F, F; for any E a. The next lemma shows that suitable truncation preserves most of the mass of the lower tail.
Lemma A.2. Impose the hypotheses of Theorem 4.3, fix
0 and let F.
A
L a Eical, x,)² < 72) } For every subset C [m]] we have that:
h2 1
1 E
vv
x
Σ 21)
2
14

---

Proof. As announced, fix T > 0 and let Fa -
{ 1 [a
Diealo Xi)
We have that:
E
00
X
Σ iEO
(u, X3) $F
EEa
E
xz)² 1 PX
IEa
(e, X;)²
P(Fa)
(Cauchy-Schwarzz)
EEa
(A.5)
E
(u, X2
VP(FF)
(Lemma A.1)
Eieo (v, x,)² ?
E
E
(u,
X,)²
(Markov's Inequality)
12
72
FEB
h
uu x,)
(Lemma A.1)
To finish the proof, multiply both sides of (A.5) above by |a| and re-arrange.
We now proceed with the truncation argument. Define the function
if S T 7 if >T.
u
(u)
The truncation is combined with an approximation. Namely, notice that we have
((u, x:))
71
71 i=1
E
or (1v, X,))
1
E
o (1u, X.))
n Σ ==1
o (1u,
71
n
1=1
(A.6)
E
pr((1, Xz))
sup
E
Φt ((),
E0- Xii)
eEDEx
i=1
iEO
iE0
sup
E E
(11 x,))
Σ (r((1,
v
n
,EB
iEE
where the last step uses the assumption that v E 0..x.
By invoking Lemma A.2 and noticing that o, can be lower-bounded via the indicators of the F, we have that:
Ed, (10, X²))
Σ
E(c, X >
11
(1-
h2
1 x,)
Σ B
(1
2
n
n
(A.7)
since E x.x. tion:
Consequently by combining (A.6) and (A.7) we obtain the deterministic decomposi-
11
h2 1
U. X,)
sup =E0EX
E Σ iEO
((u,
Cdr(uo x.))
72
72
n
150
sup
E
(r((,x
Σ
(r((1o,
(A.8)
7
i
15

---

for every 0Σx.
The decomposition (A.8) the stage for the last step of the proof: will apply the block decoupling result of Proposition 4.1 to replace the empirical processes appearing on the right of (A.8) and pay an additional failure probability of 2i 3x (a:).
Consequently, it only remains to control the supremum of the following truncated and decoupled empirical process (sgn E E))
sup REBXx
E M ((U,
Σ EEgga
((v, Xii)
(A.9)
sEsgg
A.2.2 Approximation step: bounding (A.9)
We now intend to invoke Talagrand's inequality for independent but not necessarily equally distributed variables [see Klein and Rio, 2005, Theorem 1.1]. To so, we first need to control the expectation and then the weak variance of the process (A.9). For future reference, we also point out that by construction:
Σ FEE
Eś, ((v, X.)) ((v, S 2,73/a/.
(A.10)
We now turn to controlling the expectation of (A.9). Using that the odd (resp. even) blocks of the decoupled process are independent, a straightforward symmetrization argument yields [see e.g. Wainwright, 2019, Proposition 4.11]:
E sup veBEx
E Σ zEsgn
(())
((v,
Σ ((u,
2 S
E
Σ
M ΣΦ
or (1r
vEOEx
iEsen
jE[2m], Cagn
iEes
(A.11)
for sequence Jj j [2m] of Rademacher random variables. Since the map (Rd, || 112) 3 x + Σ (-,,) E --.I-1) is dri-sisccizz the vector version of the Ledoux-Talageen contraction principle yields [see Maurer, 2016, Theorem 2]:
(1oxXa))
2E
sup vegEx
Σ
V Σ de
< 4T
max [2mm)]
lay E
sup Σ veaEx
sesgn nn Xx) (A.12)
je(2m]] ayy Cagn
KEa,
for another sequence T/6, [ri] of Rademacher random variables. Obviously,
sup x VEsgn
Σ ml
=E Σ 1
1/2 X
E
Σ 1 1/-1/ X
Vnxx (A.13)
iEsgn
lEsgn
Combining (A.11),(A.12) and (A.13) we find that:
sup eEaXx 7
E Σ 0r((v, Σ
0r((o,
$ 47 v
2ndx
max layl jE(2m)
(A.14)
iEsgn
Exxy
16

---

As announced, we also need an upper bound on the variance of the truncated empirical process (A.9):
sup vE05x
Var
E Σ
o
(1u,
Σ or (1o,
sgggn
zEggo
= sup ve0Ex
Σ je[2m],aycC
Var
E
(r((u,
(Blockwise Indep.)
iEaj
< sup vE02X
Σ
E
Σ
Φ ((r, Xii)
(Jensen's Ineq.)
je 2mm Cay
iEn;
sup v60Ex
Σ
Flal
Evu X.)
(1++(-) S 72)
jE[2m]]a, Cagn
iEa;
S 7² max |a] sup aggg
Evu, X,)
" jEsgn
I n' max azyl
jc[2m]
(A.
Combining Klein and Rio's version of Talagrand's inequality with estimates (A.10), (A.14) and (A.15), we find for any u [0, oo) that:
EΦ, ((v, ((), - or (tv, ((o,
P
sup vEaEx
2 4r 2ndx max |a| + u oCsen
FExgn
-
exx
laylu/ (A.16)
2v + 6T max
with v 7 max |ay| + 8 8 maXacssn la].
A.2.3 Finishing the proof of Theorem 4.3
Fix a positive constant E R to be determined later. We now set an. Let us further fix a positive constant and assume that n 2 (1/=")dx max layl. Under these additional hypotheses:
47 2ndx max layl 4rn/2=
(A.17)
JE(2m)
and
2v + 2 max
laylu
2r2n max |a,1 16, 2ndx 5E[2m]
max
layl + 67 max
lay/u
jE(2m]
5E(2m]
jE jE[2m]
(A.18)
max lay (2n + 6am) + 16rn jE[2m]
We now decouple using Proposition 4.1 and instantiate our upper bound (A.16) control (A.8). This step combined with the estimates (A.17) and (A.18) yields:
(1
h2
P Vu E 05x
Σ
X,)² 2
8T
-2a
72
a²n
2m
2 1 - 2exp
(x) (A.19)
maxxe[2ml | + 6a 16T
2
By choosing and sufficiently small and sufficiently large, we find that there exists a universal positive constant C such that if
2m -1
n 2 max (dy(dx + h² log(1/6)) and Σ 3E(2m]
(x(a;) S
17

---

then
P Yo E dxx
Σ
X1) 2 2
21 -
i=1
The result follows by rescaling to arbitrary v 18xx
A.3 Finishing the of Theorem 3.1
The proof of Theorem 3.1 now easily follows from Theorem 4.3 and Theorem 4.2. We translate the necessary conditions below.
First, we note that in light of Theorem 4.3 if (4.7) holds then we may estimate Σ 3 clax for some universal positive constant e > O. We remark that (4.7) holds by (3.3) and (3.5). Consequently, suffices to control the random walk (2.6).
Second, we turn the control the random walk (2.6), which is provided by Theorem 4.2, by instantiating it to the case of the Euclidean space ( || ||e). We identify this space by linear isometry (vec) with (Rdvdx, [|2) and hence in the notation Theorem 4.2 we have that the weak variances
Ao
1
Σ
E
vec
Σ
Z
vec
Σ Zn
10]
iE(2m],iE2N-1
jEal
jEau
lp
Ag
1 F
Σ
E
vec
Σ
Zz
vec
Zz
kE(2m],
jEa,
jEas
Using monotonicity of the operator norm symmetric positive semidefite matrices and the condition (3.4) we also have for either sgn E E):
do² S Asgn S 0
(A.20)
for some universal positive constant c' Condition (3.4) also implies that the constant r in Theorem 4.2 can be chosen c'edim (E) for some universal positive constant c". The final step is to note that the last two terms on the right hand side of (4.6) are less than e 8 for some third universal positive constant e if the respective second parts of (3.3) and (3.4) hold.
18


Reviews:
[{"review_id": "WqnwjpnKv6", "reviewer": "Reviewer_BbWm", "summary": "The paper gives finite-sample bounds on the excess risk of ordinary least squares regression in the non-realizable case with dependent ($\\beta$-mixing) data. The result asymptotically matches the predictions of the central limit theorem. The dependence on the mixing behaviour of the process is relegated to terms of smaller order in $1/{n}$, where $n$ is the length of the observed sample path, so that, apart from absolute constants, the bound asymptotically coincides with those for independent data.\n\nThe technical proof decomposes the excess risk as the norm of the product of a weighted random walk and the inverse covariance matrix (prefiltered with the true covariance). These two factors are bounded separately, in both cases using the blocking technique, which has become a standard method when dealing with $\\beta$-mixing processes. How it is avoided, that the mixing times enter the  asymptotically dominant term of the bound, is already explained in the introduction by the example of Bernstein's inequality. The technical details are a major achievement (I did not have time to verify all of it) and relegated to the appendix. ", "questions": "Suggestions:\n\nThm 3.1 first stated for stationary processes.\n\nDetailed discussion of the second condition in (3.3)", "limitations": "The limitations seem to be adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an important and obvious problem and offers a largely satisfactory solution.\n\nThe multiplicative dependence on the mixing times is a major problem which besets many bounds for dependent data. It is a major accomplishment to free the dominant term of the bound from this dependence. The illustrative explanation in section 1.1 (lines 44-57) is very nice.\n\nI did not find any faults, but because of time constraints I could not verify all the material in the appendix. Otherwise I would have rated the soundness with 4 rather than 3.\n", "weaknesses": "The statement of Theorem 3.1 is somewhat opaque because of the choice of the blocking partition. Presumably the cardinalities of the partition members have to be different to accommodate the non-stationarity of the process, as specified in eq (3.4). \nThe theorem would be more transparent if first stated for stationary processes using a homogeneous partition. The more general version could be stated in the supplement.\n\nThe most critical \"burn-in\" condition seems to be the second condition in 3.3, because of its dependence on $\\sigma^2$ and $\\delta$ and in particular if $s=4$. How shall we interpret the slow-down of the \"burn-in\" as $\\sigma^2$ becomes small? It seems to me that this condition would merit a more detailed discussion.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort spent on evaluating our manuscript. \n\n\n* While we agree that there is trade-off between generality, obtuseness and being concise, we prefer to leave the statement of Theorem 3.1 as is. Our motivation for this is that we already have an informal theorem statement which is relatively easy to parse.\n\n\n* (Relating to the appearance of $\\sigma^2$ in the denominator in the second burn-in condition). Note that it is in fact a ratio-squared of the $s$:th moment and the 2nd moment that appears in this condition. This ratio appears because we use higher moments than $2$ to control the deviation of a normalized random walk from its 2nd moment (in principle by Markov's inequality). We will clarify this point in the manuscript.\n"}, {"review_id": "C9oYhMazvK", "reviewer": "Reviewer_vLcM", "summary": "This paper studies the risk bounds of OLS for linear regression with dependent data. In particular, the label noise is allowed to be non-martingale. It shows that, after a burn-in phase, OLS with dependent data archives a bound of the same order as if the data is iid, provided that the failure probability is moderately small. The proved bound is particularly interesting because it suggests that the leading error does not explicitly depend on the mixing time. ", "questions": "1. My main question is regarding line 158, the \"hypercontractivity condition\". To my knowledge, in the iid case, the hypercontractility condition states that \n$$ E \\langle v, x \\rangle^4 \\le h^2 \\cdot \\langle v, E [xx^\\top] v  \\rangle^2. $$\nIn comparison, the \"hypercontractivity condition\" introduced in line 158 misses a square on the right-hand side. Could you please comment on this difference? I understand that the \"hypercontractivity condition\" introduced in line 158 only requires $v$ such that \n$$ \\langle v, \\Sigma v\\rangle = 1.$$\nWill the \"hypercontractivity condition\" in line 158 implies an additional condition on the data dependence? \n\n2. Line 182. ```The first burn-in condition of (3.3) is standard for control of the lower tail... it is optimal even in the iid regime.```\nI am not sure if this statement is accurate. For example, the work by [BLLT] (and its many follow-ups) allows $n$ to be smaller than $d_{X}$. Granted, they do need stronger assumptions such as data being iid and sub-Gaussian. \n\n3. One drawback of the bound is that the fail probability $\\delta$ cannot be made arbitrarily small. The condition (3.5) implies the mixing time has to be sufficiently fast. This is also acknowledged in lines 192-197.  \n\n4. Line 169. ```The scaling with ... thus scales as expected in the iid regime, but also degrades gracefully with dependence. We reiterate that (3.2) does not depend directly on mixing in the leading order term....```. \nI feel the discussion is a little confusing. Note that even if the bound has a multiplicative dependence on the mixing time, it still degrades \"gracefully\" with dependence. Because in the iid case, the mixing time is just $1$ so a multiplicative dependence does not harm either. \n\n\n## Typos\n1. Line 52. Are there some typos in the definitions of $\\bar V_i$? I guess the right definition be \n$$ \\bar V_i = \\sum_{j = (i-1)k + 1}^{ik} V_j$$\n\n2. Line 128. \"empirical excess risk\" -> \"excess risk\"\n\n3. Should mention that eq (3.2) holds with probability $> 1-\\delta$. \n\n\n\n[BLLT] Bartlett, Peter L., Philip M. Long, Gábor Lugosi, and Alexander Tsigler. \"Benign overfitting in linear regression.\" Proceedings of the National Academy of Sciences 117, no. 48 (2020): 30063-30070.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ Excellent presentation. \n\n+  Sharp risk bounds are well-developed for OLS for linear regression with iid data. However, when the data is dependent, the risk achieved by OLS is less clear. Surprisingly, this work proves that, even when the data is dependent, the risk of OLS still recovers that predicted by the central limit theorem and does not rely on the mixing time, given that the sample size exceeds a burn-in requirement and that the failure probability is moderately small. \n\n+ The proof is decomposed into two neat parts, the first part controls a dependent random walk with the blocking technique and the other part controls the lower tail of the empirical covariance. The proof demonstrates the new ingredients of this work that allows obtaining the improved bound. \n\n+ Prior works are well discussed. I especially appreciate the comparison with [23], which clarifies that, in the worst case, the bound will depend on the mixing time, but in average cases, the bound does not explicitly depend on the mixing time. \n\n\n\n", "weaknesses": "Please see the questions below. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort spent on reviewing our manuscript. We provide brief answers to their questions 1,2 and 4 below (with 3 being more of a statement).  \n\n* Answers to Questions.\n\n1. (hypercontractivity/moment equivalence). For sake of argument, let us assume that the process in question is stationary. The condition we use is then equivalent to $L^4/L^2$ equivalence on the $\\Sigma_X$-sphere. Namely for fixed $v\\in \\partial\\Sigma_X$, the requirement that $\\mathbb{E} \\langle v,X\\rangle^4 \\leq \\langle v, \\mathbb{E} XX^\\top v\\rangle^2$ is exactly the same as the requirement that  $\\mathbb{E} \\langle v,X\\rangle^4 \\leq \\langle v, \\mathbb{E} XX^\\top v\\rangle$, precisely because  $\\langle v, \\mathbb{E} XX^\\top v\\rangle=1$ since $\\partial\\Sigma_X = \\{ v : \\langle v, \\mathbb{E} XX^\\top v\\rangle=1 \\}$ by definition.  Put differently, these conditions only differ significantly if one requires them to hold outside the $L^2_{P_X}$-unit-sphere but since we are working with a linear class we only need to consider the unit ball (by a rescaling argument). In general (without stationarity) these conditions will not differ by more than a factor of a condition number between $\\Sigma_X$ and $\\Sigma_{X_i}$.\n\n2. This is a good point, thank you. We should have phrased this more carefully so that it refers to invertibility of the empirical covariance matrix---changes to reflect this have been made.\n\n3. This is correct---these burn-ins are obtained  by requiring that various additive terms are \"sufficiently small\". We could in principle present a bound valid without these mixing-related burn-ins but there is no guarantee that our results are sharper than existing bounds for $\\delta$ in this regime.\n\n4. We will clarify this point, thank you. \n\nTypos: We thank the reviewer for pointing these out to us. "}, {"review_id": "yG0QRqpxd9", "reviewer": "Reviewer_8guK", "summary": "The paper explores the impact of noise level in linear regression for dependent data by blocking technique, which can accommodate a broad type of dependent structures.  Theoretical justification of the non-asymptotic guarantee and excess risk bound  are provided, imposing any realizable assumptions on the noise.  The paper's insights and conclusions are likely to influence and inspire further research in the field.\n", "questions": "There are some issues need to be addressed.\n1. The martingale technique is commonly-used to address the dependence in random stochastic process. Could the authors highlight the differences between the proposed methods and martingale? Further, it would be valuable for the authors  to give some discussion about the realizable and non-realizable learning under dependent setting.\n\t\n2. In the problem formulation, does the last equality hold in the definition of excess risk in Equation (2.3)?\n\t\n3. The authors claimed that the sidestep of blocking can be decomposed as controlling the lower tail of the empirical covariance matrix and the interaction between the noise and covariates,  and thus adopt $\\beta$-mixing assumption to address the interaction term for non-asymptotic bound.  However, I wonder what is the main contribution of the proposed method except for the use of  $\\beta$-mixing and blocking, since the two instruments are very common to tackle dependent data or time series. Maybe the Summary section need to be rewritten.\n\n4.  In Theorem 3.1, it would be better if the detail of correcting the blocking inflation factor is exposed.\n\t\n5. The authors mentioned that the non-asymptotic result allows for arbitrary dimensions and unbounded process, but there is no further discussion or elaboration on this aspect.\n\n6. The authors have mentioned  that the proposed method outperform the some existing work. It would be beneficial if the authors could conduct some numerical experiments to support the proved theoretical results compared to some existing works, for example, Nagaraj et al. (2020).\n\n7. The manuscript is not well-organized and there are many typos in the manuscript and the writing  needs more polishing. For example, in Section 1 of Page 1 Paragraph 2, the last sentence appeared twice. \n", "limitations": "No other major concerns than the ones listed in the weaknesses and questions.\n ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The authors propose a novel perspective by combining  $\\beta$-mixing assumption and blocking technique, leading to a new approach for addressing the dependent data. This innovative combination offers unique insights and contributes to advancing the field in handling such data structures. This paper demonstrates a solid theoretical foundation, characterized by sound reasoning and logical coherence. The non-asymptotic results are precisely analyzed, and potential limitations are appropriately addressed.\n", "weaknesses": "1. Inadequate comparison with prior work: The paper could benefit from a more thorough comparison with existing literature. Providing a detailed analysis and critique of related works would help situate the proposed approach in the context of prior research. Identifying the limitations of previous methods and explicitly explaining how the proposed approach addresses those limitations would strengthen the argument for the paper's contribution.\n2. Lack of clarity in methodology: The paper could benefit from providing more detailed and explicit explanations of the research introduction and methodology. Some sections may be unclear or lack sufficient technical details, making it difficult for readers to understand the implementation nuances. Adding supplementary information, such as mathematical formulations, pseudo-code, or algorithmic details, would greatly improve the clarity of the work.\n3. Lack of experimental validation: There conducted no numerical results in the manuscript, which are limited in scope and fail to provide a comprehensive evaluation of the proposed approach. To strengthen the research, the authors should consider adding some numerical experiments  to demonstrate the effectiveness and generalization of their method compared to existing methods. Additionally, providing a comparative analysis with existing methods would further highlight the strengths and weaknesses of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We do not agree with the assessment provided by reviewer 8guK and believe it should be disregarded. There is no real criticism of our work in this review other than sweeping and unsubstantiated (and sometimes contradictory) claims. The main points of contention appear to be 1) related work, 2) clarity, and 3) experiments. We address these below.\n\n1. While we do not claim to be exhaustive, we believe we have provided a fair overview of closely related contributions. In particular, we have provided a detailed comparison to the work of Nagaraj et al. in Section 3.1, which to the best of our knowledge is most closely related.\nWe also note that the other reviewers appear to be in agreement with us on this point.\n\n2. The reviewer believes that our work \"lacks clarity in methodology\". We find this criticism to be rather sweeping and without proper justification. We also note that the other reviewers appear to find the paper rather clear. \n\n3. While experiments generally do not hurt we do not think they would do much to improve this particular paper, and in particular we do not agree with the way this criticism is written by the reviewer. Our result is a refined analysis of a very standard algorithm and in particular we do not provide any new algorithm and so providing a \"comparative analysis with existing methods\" does not make much sense. \n\nWe also note that the review is somewhat incoherent, examples including for instance that the paper is likely to \"inspire further research in the field\" while being awarded a contribution score of \"1\".\n\n\n\nWe respond below to the reviewer's questions below:\n\n1. As is stated in the introduction, the differences lie in the set of assumptions. This in turn necessitates a new proof approach as is provided here.\n2. Yes, this is a well-known identity for the population risk in the regression literature and is easily obtained invoking optimality of $M_\\star$ to the population risk criterion.\n3. As is clearly stated at several places throughout the paper, the main contribution is that we are first to provide a sharp non-asymptotic analysis of least squares for a wide range of processess ($\\beta$-mixing). Previous results operate either under  strict realizability assumptions or deflate the rate by a \"mixing time factor\". With regard to the use of blocking and mixing the novelty lies in the way these are combined.\n4. We could not follow the meaning of this question. Could the reviewer clarify the meaning of exposing the blocking inflation factor? We have clearly stated our burn-in conditions.\n5. As the reviewer notes we state in the introduction that the one dimensional \"Bernstein sketch\" can be extended to arbitrary dimensions and unbounded processes. This is precisely the statement of Theorem 3.1 which holds for covariates taking values in any finite dimensional space and does not impose boundedness assumptions on these covariates other than the existence of 4 moments. We are left wondering what the reviewer means?\n6. We believe the rather detailed comparison in Section 3.1 makes this point sufficiently clear.\n7. We thank the reviewer for point out the accidental doubling of this sentence. We do however strongly disagree with the suggestion that the manuscript is not well-organized and it appears strange to us in light of how highly the other reviewers rate our presentation."}, {"review_id": "ECN9Ercwqy", "reviewer": "Reviewer_2Nqt", "summary": "This paper deals with linear regression with dependent ($\\beta$-mixing) data. It provides an upper bound of the OLS error in terms of the sample size and the effective dimension of the covariate matrix. ", "questions": "I have no specific question, but one general comment. The result established in this paper has close affinity to nonparametric estimation (with possibly non i.i.d. noise, e.g. time series). This is a vast field, and the authors may want to add more discussions on this connection, see e.g. Wu's paper Nonlinear system theory: another look at dependence. PNAS, 2005.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper studies the linear regression with dependent data. The main idea is to decompose the data into blocks, and apply the concentration inequalities. The authors also provide bounds on the burn-in period. The overall results are new, though the idea does not seem to be novel. The presentation of the paper is clear, and I mostly enjoyed reading the paper.", "weaknesses": "The main weakness of this paper is that the approach of combining blocking with concentration is quite traditional. As pointed out by the authors themselves, this idea was carried out in [10] (almost 30 years ago), with subsequent development by Massart, Wu...etc. The main result (Theorem 3.1) is more or less expected in the high dimensional statistics. Moreover, there is no (empirical) experiment for illustration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort reviewing our submission. \n\nBy our estimation, the reviewer's main concern is a lack of novelty, in the sense that similar estimates on the  random walk component of our analysis (i.e. the \"numerator\" in the estimation error)  have appeared previously in the large/moderate deviations literature.  We do not argue this fact but would like to  some nuance to claim that the result is \"expected\" or lacks novelty and kindly ask the reviewer to reconsider their score in light of this if possible. \n\nFirst, one of the main points of our manuscript is precisely that this is expected (from the central limit theorem) but that, nevertheless, sharp estimates for learning with dependent data are conspicuously absent in the literature (beyond certain special cases as we note).  Indeed, a quick glance at our references (and more can probably be found) reveals that several top tier venues including NeurIPS, the Annals of Statistics, and COLT have published results on square loss  quite recently in which the noise term is deflated by such mixing time dependencies. Moreover, just as we do here, some of these papers focus entirely on linear classes (e.g. Wong et al. (Ann.Stat. 2020) and Nagaraj et al. (NeurIPS 2020)).  Hence, even if these papers combine blocking with concentration, they do not arrive at rates that match known asymptotics---again: remedying this is precisely the point of the present manuscript.\n\nArguably, we then have that 1) the problem is of interest to the intended audience; 2)  to the best of our knowledge, there are no previous works that manage to obtain sharp non-asymptotics for any convex class with general dependent data---even though they as we do combine blocking and concentration, they only manage to obtain multiplicative instead of additive dependency on mixing; and 3) miss-specified linear regression is a natural starting point for sharpening this dependency. \n\nWith this in mind then, it appears a little unfair to us to reject our solution based on the fact that it is \"simple\" and draws on existing ideas from probability theory. \n\n"}, {"review_id": "Kdldn2NDhH", "reviewer": "Reviewer_6Vi5", "summary": "The focal point of this paper is very precise, namely least-squares linear regression under data which need not be independent. Regardless of linearity, when the model is properly specified (realizability, i.e., the expected squared error minimizer is included in the model), martingale-based arguments are well-established in the literature. It is this realizability assumption that the authors remove. They conduct a blocking-based argument; this breaks up the data into blocks which are essentially independent, but takes a hit because the effective sample size is reduced. Their blocking-based argument is done in a careful way, such that the resulting \"noise level\" factor (a variance-like quantity) that appears in excess risk bounds is not excessively inflated by this reduction.", "questions": "I do not have any points to confirm that would change my opinion of the paper.", "limitations": "The technical assumptions are all given explicitly, with plentiful references to the existing literature, so I feel the limitations of this work are quite clear.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is extremely well-written, with notation and exposition all crystal-clear. The main content is all quite technical in nature, but the key ideas are explained in an intuitive fashion, with appropriate references to the relevant literature upon which this work stands. The paper is centered around the main technical result (Thm 3.1), and is organized to give relevant background to understand the technical context in which this result stands, and to describe the essential points of their proof. In my opinion, the balance between informal and formal content is excellent.\n\nThe main result of this work is Theorem 3.1. While there are several technical \"burn-in\" conditions (the sample cannot be too small, relative to the degree of dependence and noise level, etc.), the core result (3.2) is clear, appealing, and to the best of my knowledge fills a valid gap in the theoretical literature for linear least-squares with dependent data.", "weaknesses": "Obviously this is a technical paper with a very particular problem of interest, and thus the overall \"impact\" on the field of machine learning is limited, but the solution provided by the authors to this problem is presented clearly, and the main claims are to the best of my understanding solid.\n\nThe only point I had trouble with in terms of clarity was the notion of \"instance-specific\" and \"instance-optimal\" performance guarantees. I know the authors try to spell this out in the first paragraphs of 3.1, but if space allows, I think a more explicit explanation of the \"global\" complexity in previous works would make the \"local\" complexity here a lot more clear.\n\nA couple other small points:\n- Since there is some space left, I felt that it would be nice to give $\\\\widehat{M}$ a definition analogous to $M\\_{\\\\star}$ in (2.1), instead of just giving the form in (2.4) and saying it is the OLS solution. I know this is simple to verify, but if space allows it, such an explicit expression makes it more friendly to a crowd familiar with notions of ERM.\n- The last sentence of paragraph 2 in section 1 is repeated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort spent on evaluating our manuscript. \n\n* We have clarified the distinction between local and global complexities by adding the following sentence to Section 3.1: \"In other words, they compete against the worst distribution at a given level of mixing, whereas we compete against a fixed  distribution.\"\n\n* We have also added a short remark that $\\widehat M$ is an empirical risk minimizer at the end of the problem formulation as per your request."}]

Author rebuttal:

Meta-review: This is a surprising and nontrivial result, on a fundamental topic that has already attracted wide interest.  

I strongly encourage the authors to take BbWm's advice and write a more easily understood theorem, possibly in a special case as a corollary.
Decision: Accept (poster)