Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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.
questions: Can we testify the theory on simple regression problems, empirically?
limitations: There is no negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

The proof relies on using the hypercontractivity to control the lower tail of sums involving the dependent random variables.

The 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).
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. 

However, 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.

There are also some limitations to the theorem (see below).
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?
* 304: Why is a lower bound on the marginal probabilities needed? Is this necessary?
* 315: What are natural examples where a $L^{2+\epsilon},L^2$ norm equivalence holds?
* (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$.

Minor edits

* 211: hypercontracitity -> hypercontractivity
* 544: some constant factors as missing in the following inequalities.
* 549: missing log in following inequality
* 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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
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.
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
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strength: 1. This paper is technical. It is clearly written and well organized.
2. The result in this paper is significant.
Weakness: 1. This paper requires a more detailed discussion and comparison with the previous related work.
2. There are some confusing mistake in the proof of the main results.
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?
2. Can the authors elaborate more on the technical new insight of this work?
3. Can the authors conduct some numerical studies on this phenomenon?
4. 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.
2. This paper seemed not to give any new insight on this field.
review_title: null

Meta-review: metareview: This paper studies the problem of learning under dependent data. Existing bounds usually work by deflating the effective sample size by a factor that depends on the mixing time. Essentially when the samples are far enough away from each other, depending on the mixing time, they can be treated as independent. This paper introduces a new framework that they call the trajectory hypercontractivity condition, which stipulates that there is sublinear growth in the dependency matrix. This is a flexible perspective, and the paper derives both general results and applies them in interesting settings. There are some weaknesses, e.g. they cannot recover results in the marginally stable case or in settings with unbounded noise. For example, as the maximum eigenvalue approaches one, the burn-in blows up. I think reviewer SNkB's perfunctory review should be ignored. The paper is somewhat borderline, but in my opinion it is technical stronger and more interesting than some of the other borderline papers in my batch. I recommend acceptance. 
confidence: Less certain
Decision: Accept