Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, this paper studies the finite-time convergence of nonlinear SA with multiple coupled sequences. Different from existing multi-timescale analysis, the authors seek for scenarios where a fine-grained analysis can provide the tight performance guarantee for single-timescale multi-sequence SA (STSA). When all sequences have strongly monotone increments, they establish the iteration complexity of O(eps^{−1}) to achieve eps-accuracy, which improves the existing O(eps^{−1.5}) complexity for two coupled sequences. When the main sequence does not have strongly monotone increment, they establish the iteration complexity of O(eps^{−2}).
strengths_and_weaknesses: Strengths:
1. This paper provides an improved rate for the case where all sequences have strongly monotone increments in single-timescale multi-sequence SA.
2. This paper further provides an analysis for a single-timescale multi-sequence SA when the main sequence does not have strongly monotone increment. 
3. The theoretical analysis is novel, which makes significant contribution to the related area.

Weaknesses:

1. I think this paper lacks sufficient discussions and comparisons on the assumptions, which makes the technical part of this paper not sufficiently clear:

There is another work studying the single-timescale minimiax optimization [1], which is a special case of the single-timescale two-sequence SA when the main sequence does not have strongly monotone increment. In their Algorithm 1, they show that a momentum updating step is needed in order to obtain a single-timescale algorithm. However, this paper does not need the momentum updates. In my understanding, the main technique for the proof to get rid of momentum is in (57) and (59). And (57) and (59) depends on two important assumptions: 

a)  \xi and \psi are mutually independent. Otherwise, the second equation in (57) does not hold. This means we need to sample twice independently in the application of the algorithm. In [1], they do not have this assumption. I think this mutual independence should be highlighted as a formal assumption and a comparison with the existing work is needed as well.

b) Existing works e.g., [1] [2], only need a Lipchitz assumption for y*, while this work makes a relatively stronger assumption that the gradient of y* exists. Such a comparison is also necessary in the paper to clarify the major difference in the assumptions and the reason why we can obtain a single-timescale algorithm.

[1] Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
[2] On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

2. According to the submission instructions, the authors need to complete the check list after the reference section. In this paper, the authors did not provide limitations of this work.
questions: 1. Can we still get a single-timescale algorithm when \xi and \psi are not mutually independent?
limitations: According to the submission instructions, the authors need to complete the check list after the reference section. In this paper, the authors did not provide limitations of this work. I think the authors can further discuss the limitation of this theoretical analysis in their submission.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proves the convergence guarantees for SA with double-sequence and also extends to multi-sequence and the results seem tight. Besides, this paper also applies their general results to SBO and SCO problems and show the improvement of their results.
strengths_and_weaknesses: As I'm not an expert in optimization area, I'm only able to give some common issues in this paper. 

Questions:
1. I think Assumption 3 is a little bit weird because LHS is a random variable while the RHS is a non-random term and without a high probability guarantee. And I think it is not the generalized version of Assumption 2.1 in [30] because the second-order condition in Assumption 3 can induce moment assumption in [30].
2. I would be appreciated if the author could provide an example of a weak dependent sequence as Assumption 3 describes.
3. Is $y^n$ arbitrary in Assumption 4? If so, please use more precise language.
4. Line 169, it is not $\mathcal{O}(K^{-2})$ but $\mathcal{O}(\epsilon^{-2})$ or $\mathcal{O}(K^{-1/2})$

In conclusion, in my own opinion, I think this paper provides a solid result. But I will consider changing my score after reading other reviewers' comments and authors' responses.

questions: see Strengths And Weaknesses
limitations: see Strengths And Weaknesses
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the finite-time convergence of nonlinear stochastic approximation (SA) with multiple coupled sequences. While there are few work on analyzing the performance of SA in this setting, existing analysis all adopt a multi-timescale analysis in the sense that the stepsizes for all the sequences decay at the different rates, which leads to a convergence rate that is slower than that of the single-sequence SA. The focus of this paper is on finding settings where it suffices to using single-timescale updates for multi-sequence SA, leading to the same convergence rate as that of the classic single-sequence SA. The implications of the new results on applications to bilevel, compositional and reinforcement learning have been discussed. 
strengths_and_weaknesses: Strengths:
1.	This paper presents the ﬁrst $k^{-1}$ and $k^{-1/2}$ convergence rates for nonlinear SA under two settings: a) all sequences have strongly monotone increments; and b) all but the main sequence have strongly monotone increments. These results have been then extended to multiple coupled sequences with the same iteration complexity, which is also new.
2.	The paper presents a unified and new perspective of understanding the recent theoretical advances in stochastic bilevel, compositional optimization and reinforcement learning. Applying the new results of nonlinear SA with multiple coupled sequences to those special cases lead to either improved iteration/sample complexity or relaxed assumptions. 
3.	The nice thing about this framework is that the iteration/sample complexity of new SA algorithms developed in these applications can be established by just verifying the assumptions in this paper. If those assumptions are verified, they automatically enjoy the same convergence rate as single-sequence stochastic approximation or SGD. 
4.	The simulation, although very simple, gets the key point of this paper – there is a gap between the existing theory and the actual performance of nonlinear SA. 

Weaknesses:
1.	The new iteration complexity results for nonlinear SA hold under the smoothness assumption on the fixed point. While the paper has justified it in several applications, it does not improve the existing complexity of SA without this smoothness assumption. 
2.	The paper can do a better job on discussing and highlighting in the main paper how the new proof techniques improve the existing analysis.

questions: 1. If the smoothness assumption does not hold, can the existing complexity of SA be improved using the analysis in this paper?
2. In addition to stochastic bilevel and compositional optimization, what other new special class of stochastic optimization problems can benefit from this generic results? 
3. It would be interesting to discuss and highlight in the main paper how the new proof improves the existing analysis. Now they are hidden in the supplementary document. 

limitations: NA
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper fomulates the stochastic approximation of multiple coupled sequences and builds the non-asymptotic convergence rate for both strongly monotone and non-monotone case. Multiple applications are introduced after providing the theoretical convergence guarantee, including bilevel optimization and compositional optimization.    
strengths_and_weaknesses: ***Strengths***
* This work is sufficiently complete and well-written. It gives a clear definition of the multiple sequences stochastic approximation and builds the convergence rate for both of strongly monotone and non-monotone cases. Also, those derived bounds have matches the best known results. 

* It is nice to see there is a unifying framework that can include stochastic bilevel optimization and stochastic compositional optimization. I am not sure if this paper is the first work doing so, but this paper reveals the significance of studying the stochastic approximation with multiple coupled sequences.    

* The sngle-time-scale  learning rate scheduling can be better than the standard two-time-scale one. This result is really new.

***Weaknesses***
* I have not found any major weakness of this work.
questions: * I agree that the monotonicity assumption (Assumption 4 and Assumption 5) is standard in many existing work. But I am not clear how this assumption is connected to concave or strongly concave function. Are they just different name? 
limitations: Since this work is purely theoretical, there is no any negative impact.
review_title: null

Meta-review: metareview: This paper provides convergence analysis for nonlinear stochastic approximation with a "multi-sequence" update structure motivated by applications in reinforcement learning and bilevel learning. When all sequences have strongly monotone increments, the authors provide iteration complexity of O(\epsilon^{−1}) to achieve accuracy, which improves the existing O(\epsilon^{−1.5}) complexity for two coupled sequences. When the main sequence does not have strongly monotone increments, they establish iteration complexity O(\epsilon^{−2}).

The reviewers agreed that the techniques in this paper are novel, and that it is well-written. In addition, the paper improves upon existing results when applied to problems in reinforcement learning and bilevel optimization, and hence is likely to have broader impact. However, the reviewers felt that the for the final version, the discussion of the smoothness assumption needs to be expanded, and the comparison with prior work needs to be improved.
confidence: Certain
Decision: Accept