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 proposes to solve the root finding problem of the form $\bar f(\theta^* ) = 0$ where $\bar f$ is the expectation of some smooth but random function. Instead of the usual ODE method that converges at at rate of $O(1/t)$ in the MSE, the authors propose to use QSA ODE instead to obtain a convergence rate of $O(1/t^2)$, and *close to* $O(1/t^4)$ if combined with Polyak-Rupert (PR) Averaging. The QSA ODE method is similar to the ODE method but with sinusoidal perturbations rather than iid uniform perturbations. The theoretical results provide insights to new approaches in Quasi Monte Carlo sampling. Finally, simulation studies using Euler approximation corroborate with the theoretical results.
strengths_and_weaknesses: I find this submission to be very interesting, unfortunately, I would like to first acknowledge that after carefully reading the paper, I realized my expertise in certain technical aspects is lower than I had anticipated, especially when it comes to complex analysis, the invocation of Baker's Theorem, and assumptions on the probing signal. I only looked through the proofs at a high level and was unable to understand every detail. My evaluation is thus also at a very high level based on my knowledge in other aspects such as discrete time stochastic optimization and QMC. I look forward to learning more from the authors and the other reviewers. 

I particularly enjoy the new QMC results developed that give rise to Theorem 2.1 (continuous time) and B.9 (discrete time). One concern I have is that the authors claim (line 87-89) the latter result gives a $O(1/n)$ instead of the usual $O(log(n)^d/n)$ rate for QMC in the root MSE. To me, removing a dependence on the dimensionality $d$ is a huge improvement, as QMC is long known to work better than MC only in the low dimensional setting. However, as the authors pointed out, the $O(1/n)$   actually contains a multiplicative constant $K_f$ for which known bounds grow at least exponentially in $d$. It is thus unclear to me whether this is in fact a better rate than classical QMC rates. If yes, it would be great if the authors could elaborate more on precisely what settings this would be the case. 

Although PR Averaging has long been studied in stochastic optimization, I have not seen it being used in conjunction with Quasi-Monte Carlo perturbations. The near-quartic convergence obtained from this is therefore impressive, and it would be interesting to see if similar techniques (such as using sinusoidal noise) can be incorporated to, say, SGD, to obtain even faster rates. 

Overall, I think the submission is well polished and organized. The experiments setups are justified and plots are nicely presented, with details clearly stated in the appendix. 
questions: Please see section above.
limitations: I find the discussions on limitations to be fairly adequate. This is particularly reflected in Section 2.1, where the authors discuss bounds on the constant $K_f$.
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: This manuscript provides a fast convergence rate analysis for nonlinear quasi-stochastic approximation by the Polyak-Ruppert averaging technique. The main ingredient for achieving acceleration is to carefully design the sine type probing signals to break the $O(n^{-2})$ bound. The application of this idea to gradient-free optimization is also discussed. Some experiments are conducted on simple test functions and it seems to verify the theory.
strengths_and_weaknesses: Strengths:
(i) The paper is well-written. The main message of the paper is very clear.
(ii) The theoretical result looks sound and strong. The overview of the proof makes sense to me (although I did not read all the proofs in the appendix in great detail).

Weaknesses:
(i) The specific form of the probing signal is very important to achieve acceleration. However, the noise design is not realistic in machine learning applications. For example, in standard stochastic approximation or SGD for training machine learning models, we do not really have the knowledge of the noise. Some discussions/clarifications would be better.

(ii) The whole paper considered an ODE formulation, it is unclear whether there is a corresponding stochastic algorithm that has a fast convergence rate as well.
questions: 1. Is it possible to relax the requirement of the probing signal (e.g., to a broader class of signals) and still achieve acceleration?

2. How to translate the Quasi-Stochastic Approximation ODE to a stochastic algorithm?


limitations: N/A
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: This paper deals with quasi-stochastic approximation -  i.e. when the random noise of standard stochastic approximation schemes is replaced by exponential signals - and provides novel and faster convergence rates. The authors introduced acceleration techniques to derive such theoretical results and highlight them in the context of gradient-free optimization. Numerical experiments support the theoretical findings.



strengths_and_weaknesses: First, I would like to thank the authors for their work: It is a well written and clear paper with relevant motivations (clear introduction), well-explained related work and fine overall structure. Although I am not an expert in this area of research, I found the message of the article to be clear and the theoretical results to be well presented and discussed.

- Originality: The idea of forward-backward filtering is originial and there are solid contributions. This paper presents a new framework for quasi-stochastic approximation which extends several convergence results known so far in restricted settings. The related work is adequately cited and clearly describes how the current paper differs from it.

- Quality: Technically strong, highly general results, advanced techniques.

- Clarity: The paper is very well written with fine overall structure making it easy for the reader to grasp all the main ideas. The authors may consider to add and discuss the following works which are strongly related to the current contribution:

     * \[A] "Optimal rate of convergence for quasi-stochastic approximation". (Bernstein, Andrey and Chen, Yue and Colombino, Marcello and Dall'Anese, Emiliano and Mehta, Prashant and Meyn, Sean)
     * \[B] "Accelerating optimization and reinforcement learning with quasi stochastic approximation". (Chen, Shuhang and Devraj, Adithya and Bernstein, Andrey and Meyn, Sean)

- Significance: The results are quite important as they extend and relax several assumptions made so far in the quasi-stochastic approximation litterature.

**References**

- \[A]: @article{bernstein2019optimal,
  title={Optimal rate of convergence for quasi-stochastic approximation},
  author={Bernstein, Andrey and Chen, Yue and Colombino, Marcello and Dall'Anese, Emiliano and Mehta, Prashant and Meyn, Sean},
  journal={arXiv preprint arXiv:1903.07228},
  year={2019}}

- \[B]: @inproceedings{chen2021accelerating,
  title={Accelerating optimization and reinforcement learning with quasi stochastic approximation},
  author={Chen, Shuhang and Devraj, Adithya and Bernstein, Andrey and Meyn, Sean},
  booktitle={2021 American Control Conference (ACC)},
  pages={1965--1972},
  year={2021},
  organization={IEEE}}
questions:   
limitations: This is a theoretical work with no foreseeable negative societal impacts.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors focus on the theoretical analysis and the application of quasi-stochastic approximation to the gradient-free optimization. The authors utilized some acceleration techniques to achieve the faster rate of convergence of order $\mathcal{O}(n^{\delta - 4})$ where $\delta > 0$ is any arbitrary positive number. Then, the authors specialize this theoretical results to the setting of the gradient-free optimization problem. The authors also conduct several numerical experiments and these empirical results are consistent with the theoretical theorems. The authors applied the results from stochastic approximation theory and the most recent discovery from number theory to prove the theoretical theorems. All proof has been put in the supplementary material of the appendix.
strengths_and_weaknesses: This paper has the following strengths in terms of the originality, quality, clarity and significance:

Originality and Significance: this paper provides the first analysis and proof of quadratic convergence rates of quasi-stochastic approximation with application in the gradient-free optimization. This is the main and independent contribution of this paper.

Quality: the authors provides detailed and correct theoretical analysis in the proof section and reasonable explanations in the numerical experiments section. These theoretical and empirical results are consistent with each other.

Clarity: the paper is organized with clear and clean structure and the language is well-organized so that the readers can easily understand the content of this submission.

From my perspective, there is no major weakness for this submission. One minor weakness is that the authors should put the literature review, notation and organization of section Introduction into another section so that the structure of the submission could be more clear.
questions: One question:

In line 18, is that convergence notation the notation of convergence in distribution? If it is, the authors should explicitly explain this notation and give an introduction to the concept of convergence in distribution, so that the readers could easily understand this.
limitations: The authors have presented the limitations of this paper in the final conclusion section.
review_title: null

Meta-review: metareview: All reviewers are happy with the new ideas and strength of results in this paper.
confidence: Certain
Decision: Accept