Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper offers a non-asymptotic analysis of the linear stochastic approximation algorithm with fixed step-size, where the solution to the linear system $\bar{A} \theta = \bar{b}$ is approximated iteratively. While prior literature has considered asymptotic and non-asymptotic bounds, the main contribution of this work is the improved quality of non-asymptotic bound for LSA performance, yielding more meaningful finite-time confidence sets. The authors consider a set of mild assumptions on the coefficients, under which they prove high probability bounds on the approximation error. The analysis is based on a new analysis of product of random matrices, with further extension to random matrices with Hurwitz mean but not necessarily symmetric a.s. The authors further discuss the tightness of the resulted polynomial bound with respect to error probability $\delta$ through a clean (counter-)example (Example 1), and the sharpness with respect to the step-size through derivation of a central limit theorem.
main_review: The paper is well-written and organized, with clear and consistent notations. The structure of having a standalone section (Sec 3) on product bound of matrices followed by its application to LSA (Sec 4) and discussion of tightness (Sec 4-5) seems natural and easy to follow. A minor suggestion is to be more explicit when discussing tightness (e.g. L60-61: “Section 5 shows the tightness of the bounds”) since more than one variables are considered.

The concentration results proven in the paper are nontrivial and clearly improve upon previously known analysis (asymptotic or non-asymptotic) in the sense that the assumptions are weak and that the bound itself is tight. Though, I would hope for a more substantial discussion of the statements (L32-34) “non-asymptotic studies are in general too coarse and lose significant statistical information in their derivation”, especially when claiming “their upper bounds are generally loose when used in predicting the actual performance of LSA.”

While the proof technique isn’t a most novel one mathematically in my opinion, the details are sound and well-presented and I believe the main claims are all correct. The main technical tool relates Huang et al’s recent paper on matrix concentration for products. The idea of handling the error term by splitting it into bias and variance terms is nice albeit standard and the actual proofs are clearly nontrivial to carry out.

### Other comments/suggestions:

I like the recurrent use of Example 1 to demonstrate tightness of the polynomial bound, a very clean example. This could be a trivial point, but I would appreciate some intuition for Assumption A2 as the additional condition for exponential high probability bounds. In particular, as is illustrated by the few examples in Section 2, A2 holds in many natural cases but not others, and I would love to have a conceptual understanding of which cases may admit an exponential bound vs polynomial. 

In the discussion of tightness in Section 5, I didn’t completely get how the paragraph L271-275 discussing Eqn (36) on the limit $\theta_\infty^\alpha$ implies the optimality of the finite-time bound (or does it not and is simply a standalone result?). I could be missing something obvious, but perhaps some additional interpretations around Theorem 5 and (36) can be helpful.

I would also love to see a discussion of implications and take-away message of the results, advancing it further from a mostly mathematical result. E.g., what are some insights behind the necessity of Assumption 2? How can the results improve current practice/knowledge when applied to reinforcement learning for example?

### Note:
I may not be familiar enough with some pieces of related work. I have checked some of the proofs carefully but not all.

### Typos spotted:
L69-70: probabilities measure -> probability measures

L113: definite positive -> positive definite

L120: \mathcal{X} -> \mathsf{X}

L268: in $\mathsf{D}_1$ definition, $e^{2/3}$ -> $e^{4/3}$ I believe, in consistency with other occurrences

L286: functions -> function

L490: are an independent -> are independent

L498: remains take -> remains to take

L520: first term RHS in the equation below: missing an $\alpha$ subscript

L556: first “=” in equation below should be \le
limitations_and_societal_impact: The theoretical limitations are discussed. N/A for negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper performs a non-asymptotic analysis for the linear stochastic approximation (LSA) algorithm, with bounds given in the form of Eq. (2). This paper shows the tightness of their bounds by examples. 
main_review: The LSA algorithm is significant in machine learning. I am generally unfamiliar with the related work, but I think this paper makes a good technical contribution to the study of LSA. 

The proof is written formally, but the intuition is unclear to me. 
limitations_and_societal_impact: ### Limitations

1. The paper claims tightness by showing a CLT-like statement. However, this seems only justifying the variance term in the main result (see, e.g., the $\sqrt{u^\top \Sigma u}$ term in Eq. 2), but not the constant term (e.g., $\delta^{-\frac{1}{p_0}}$ in Eq. 2), while the latter term is of more interest. 


### Societal Impact

The paper is mainly theoretical, and I don't see any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provides a non-asymptotic analysis for linear stochastic approximation algorithms. Polynomial concentration bounds with order depending on the stepsize are derived under weaker conditions than previous works. The paper also shows that logarithmic dependence on probability $\delta$ is not possible.
main_review: The main contribution of the paper is:

1. Under mild conditions on the sequence of $A_n, b_n$, the paper provides non-asymptotic bound for the approximation error with polynomial dependence on $1/\delta$ and near optimal dependence on the step size. 

2. Counterexamples are provided illustrating that the logarithmic dependence in $1/\delta$ cannot hold. 

3. The optimality of the term $\sqrt{\alpha}$ is shown via a central limit theorem for the family of stationary distribution for $\{\theta_n\}.

Overall, I believe this paper is a nice complement to the literature of linear stochastic approximation. My questions are summarized as below:

1. Example 1 is concluded with the impossibility to obtain exponential high probability bounds for $||\theta_n-\theta^*||$. Does this naturally suggest the impossibility to obtain exponential high probability bounds for $u^\top(\theta_n-\theta^*)$ for some fixed $u$? This seems correct to me. But it would be great to make it explicit in the paper.

2. Following-up the first point, is it possible to derive reasonable upper bounds for the term $||\theta_n-\theta^*||$ instead of $u^\top(\theta_n-\theta^*)$? Simple union bound seems to introduce exponential dimension dependence. I'm curious whether this is the best one can do or not.  

3. Is the asymptotic covariance matrix $\Sigma$ in Equation (2) guaranteed to be full rank and well-conditioned? If not, in the degenerate case when $u^\top \Sigma u$ is approximately 0, is the dependence w.r.t $\alpha$ still tight?

**Update based on the author response:

Thanks for the detailed reply. I'm satisfied with the responses to the comments and remain my score.

limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the problem of analyzing linear stochastic approximation (LSA) algorithms which are used to obtain an approximate solution of a linear system $ A \theta = b$, where $A$ and $b$ are observed through random variables $\{ (A_1,b_``1), (A_2,b_2),\cdots \}$. The analysis relies on new results regarding moments and high probability bounds for matrix products under weak conditions with polynomial concentration with the order depending on the step-size $\alpha$, which diverges from results in prior work. At this level of generality, the authors show that polynomial tails cannot be improved in the worst case. The concentration bounds are in terms of covariance matrices appearing in central limit theorems of the matrix products under appropriate scaling limits.
main_review: The paper considers the classical problem of analyzing LSA algorithms which have gained renewed interest in modern applications such as least squares (and ridge) regression, reinforcement learning (such as TD(0) learning) among other areas. Convergence results are established for these algorithms with a fixed stepsize under a set of assumptions more general than those considered in prior work. Indeed to the best of my knowledge, this is the first paper to establish convergence properties with non-subgaussian tails under a wide family of assumptions. I think this paper is a fine contribution to the theory of analysis of LSA algorithms. However, I think it would help the interpretability of the results if more instantiations of these results are provided for relevant applications (ridge regression / TD(0) learning, etc.).

- Under assumption A.1, it would help to include a remark as to how concretely show how this assumption compares with that in prior works.

- Line 120: $\mathcal{X}$ notation is incorrect. Line 134: The terminology suggesting that the matrix $G^{(\alpha)}_{1:n}$ decays with $n$ is mathematically imprecise. 

- Concerning the discussion on TD(0) learning under linear function approximation: is there any intuition how the current results can be extended to the case when $x_n$ is not sampled from the stationary distribution but equals $x_{n-1}'$. More generally, when the i.i.d.ness assumptions fail, but a martingale structure is retained, is there any intuition as to whether such bounds still hold true? For the purpose of the exposition (and comparison), it may help to instantiate the proved results in the context of TD(0) learning to compare with known results here.
limitations_and_societal_impact: Yes, I believe the authors have adequately addressed the limitations of their work, and future work to be done.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides high probability concentration bounds for linear stochastic approximation algorithms using constant stepsize under weaker assumptions. The key novelty is to derive tight moment bounds for the product of random matrices. The polynomial concentration bounds were shown to be tight. Since linear SA was widely used in application, the results are of broader interest to the NeurIPS community.
main_review: Although this paper is theoretical and highly technical, it is well-organized to convey the main idea.

(line 25): $Q$-learning cannot be modeled by a linear stochastic approximation algorithm since it involves a max operator.

Often in applications such as reinforcement learning, the samples $\{(A_n,b_n)\}$ are not i.i.d.. For example, in TD-learning with synchronous update, the corresponding samples form a martingale difference sequence. In TD-learning with asynchronous update,  the corresponding samples form a Markov chain. It may be an interesting future direction to extend the high probability bounds in this paper to these more general settings.


limitations_and_societal_impact: No Societal Impact
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the finite-time analysis of linear stochastic approximation algorithms driven by IID noise and fixed stepsize. New analysis based on new results on moments and high probability bounds for products of random matrices. High probability bounds on the LSA iterates are derived under weaker assumptions on the random samples than existing works. The bounds have also been shown tight with the assumptions made and some additional results on the concentration error bounds are also discussed. 
main_review: Finite-sample analysis of stochastic approximation algorithms has been studied in a number of works, recently motivated by e.g., analysis of reinforcement learning algorithms dealing with Markov decision processes. This paper revisits the linear stochastic approximation algorithms and analyzes its finite-time performance using recent results in concentration equalities and moments bounds. Although the analysis is new, and the high probability bound improves upon the existing one, the submission falls in several aspects. First, there are a number of related works analyzing the finite-time error bounds of different stochastic approximation algorithms and, yet they were not discussed in the submission, so it is difficult to judge the novelty and significance of the results. For example,  [a] Gugan Thoppe, Vivek Borkar (2019) A Concentration Bound for Stochastic Approximation via Alekseev’s Formula. Stochastic Systems 9(1):1-26. [b] Borkar, V. S. . "A concentration bound for contractive stochastic approximation." Systems & Control Letters 153.1(2021):104947.
Second, how important is the improvement? Does the analysis carry over to other stochastic approximation algorithms driven by e.g., Markovian noise in reinforcement learning applications? And how about nonlinear stochastic approximation algorithms? Third, it would be great if the authors also provide numerical tests validating the improvement as well as the practical usefulness of the results. 

The paper is mostly clear and easy to follow, althoug with a bit heavy notation. Some were used before they were defined. 
limitations_and_societal_impact: More recent works on (non)linear stochastic approximation analysis shall be discussed; and provide also numerical simulations validating the improved error bounds.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors analyze the convergence of the linear stochastic approximation (LSA) algorithms with fixed stepsize. They establish a high probability convergence result on how the algorithms estimate compares to the true value of the linear system. They also analyze the stationary distribution of the algorithms iterates. They show that their results are theoretically tight. Their key lemma is a result on bounding the expected value of the norm of products of random matrices, which may be of independent interest.
main_review: The paper seems very interesting mathematically but is difficult to understand in its current form. I believe that the paper needs to be rewritten for clarity.

Pros:

The paper presents tight results on the convergence of the LSA algorithm with minimal assumptions. The techniques used seem interesting and deep, such as the technical lemma used to bound the norm of the mean of a product of random matrices.

Cons:

I believe the clarity of the paper needs to be improve before it is accepted for publication.

The first clarity issue is that the authors do not go into detail on how their results compare and complement previous results on LSA convergence. The authors mention a long list of related papers but simply mention that they are weak. For example, how do the results compare to Theorem 1 of [23]? Can this work provide a high probability version Theorem 1?

The second clarity issue is that to understand the main theorems, the reader needs to understand a large number of symbols defined throughout the text (which are themselves defined with a large number of symbols). The authors should improve the discussion around the main theorems including intuition on the important terms or present simplified theorems to help the reader understand the main claim of the theorems.

Further questions:

Often the mean $\bar{\theta} = \frac{1}{n}\sum_{i=1}^n\theta_i$ is used as the estimate of the true parameters $\theta^*$ due to the natural variation of the iterates. Does this work say anything about the estimate $\bar{\theta}$? Since there is a natural variation of the iterates $\theta_i$ around the true parameters $\theta^*$ the mean should be a better estimate of the true parameters.



limitations_and_societal_impact: This was not discussed but I believe it is not needed.
review_title: null

Meta-review: The paper provides a non-asymptotic analysis of linear stochastic approximation algorithms. It shows interesting concentration bounds and certain bounds are not achievable. The majority of the reviewers agree that the analysis is interesting, and provides new results to the literature. I have read the paper carefully and also the discussions between the authors and the reviewers, and agree with the majority of the reviewers. One reviewer pointed out that its connections to other papers are not made clear and pointed out some future directions to work on, and the authors have responded to these particular points. I do agree that the current form of the paper has not addressed fully these interesting new directions, but it has crossed the threshold. 
Decision: Accept (Poster)