Approaching Quartic Convergence Rates for Quasi-Stochastic Approximation with Application to Gradient-Free Optimization
Authors: Caio Kalil Lauand
Sean P. Meyn
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic Approximation
Gradient-Free Optimization
Optimization

Abstract: Stochastic approximation is a foundation for many algorithms found in machine learning and optimization. It is in general slow to converge: the mean square error vanishes as $O(n^{-1})$. A deterministic counterpart known as quasi-stochastic approximation is a viable alternative in many applications, including gradient-free optimization and reinforcement learning. It was assumed in prior research that the optimal achievable convergence rate is $O(n^{-2})$. It is shown in this paper that through design it is possible to obtain far faster convergence, of order $O(n^{-4+\delta})$, with $\delta>0$ arbitrary. Two techniques are introduced for the first time to achieve this rate of convergence. The theory is also specialized within the context of gradient-free optimization, and tested on standard benchmarks. The main results are based on a combination of novel application of results from number theory and techniques adapted from stochastic approximation theory.


Approaching Quartic Convergence Rates for Quasi-Stochastic Approximation with Application to Gradient-Free Optimization
Caio Kalil Lauand University of Florida caio. htb..kaliillluandffllcccmom
Sean Meyn University of Florida meyn ufl. ufl.edu edu
Abstract
Stochastic approximation is a foundation for many algorithms found in machine learning and optimization. It is in general slow to converge: the mean square error vanishes as O(n-1). A deterministic counterpart known as quasi-stochastic approximation a viable alternative many applications, including gradient-free optimization and reinforcement learning. It was assumed in prior research that the optimal achievable convergence rate is ((n-)) It is shown in this paper that through design it is possible obtain far faster convergence, of order O(n 4-A), with >> arbitrary. Two techniques are introduced for the first time to achieve this rate of convergence. The theory is also specialized within the context gradient-fiee frree optimization, and tested on standard benchmarks. The main results are based on combination of novel application of results from number theory and techniques adapted from stochastic approximation theory.
1 Introduction
Stochastic approximation (SA) was introduced in the seminal work of Robbins and Monro [38]. The goal is to solve the root finding problem f(0*) = 0, in which f: Id + Rd of the form
f(0) = E( ()
(1)
where is random vector taking values in R!... The basic algorithm is expressed as the d-dimensional recursion,
0 8,, + an Sn+1),
0,
which {a,} } step-size sequence, and (n+1 _ Ç as n - oc (convergence in distribution). SA theory has attracted great deal of attention over the past twenty years, motivated in large part by applications to reinforcement learning and optimization [49, 18, 32, 16, 7].
Convergence theory is couched in the ODE Method in which trajectories of (2) are compared to solutions of the ODE å f(0) (the mean flow). The major assumption required to ensure convergence to 0*, for each initial condition Og E Rd, is that the mean flow is globally asymptotically stable-see see [7] for minimal assumptions on the "noise sequence" Ç. Establishing sharp rates of convergence is far greater challenge. There is however rich theory available to achieve the optimal rate of convergence for the mean-square error (MSE). which is general E[]l 0* [|2 O O(n ').
There are many applications for which the designer the algorithm also designs the noise. Notable examples include the introduction of exploration in reinforcement learning gradient- optimiza- tion. This motivates the use of quasi-stochastic approximation (QSA) in which the sequence Ç is deterministic (e.g. mixtures of sinusoids pseudo- random numbers). The idea was introduced in
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

[20, 22], but has much longer history in the context of gradient-fre free optimization see [48, 26] for a survey of extremum seeking control (ESC).
Theory supporting rates of convergence of nonlinear QSA appeared only recently [9, 30). Analysis and algorithms are posed in continuous time simplify analysis. This setting is also motivated by recent success stories justifying algorithm design in continuous time, followed by a careful translation obtain discrete time algorithm. See for example theory surrounding acceleration methods of Polyak and Nesterov [2, 46, 19].
The notation adopted in [30, Chap. 4] will be used here: the QSA ODE is defined as
áe e = az f(O,, Ex)
(3)
The deterministic continuous time process & will be called the probing signal, and plays the role of Ç in SA; called the gain process. The motivation for QSA two-fold:
(i) It will be seen that the rate of convergence is far faster than SA, subject to careful choice of algorithm architecture.
(ii) In on-line applications the introduction of independent noise may not be realizable, or may impose unnecessary stress equipment. In QSA design the components of the probing signal might be chosen to be sinusoidal signals of appropriate frequency and magnitude to ensure learning takes place without stress on physical devices.
What is the optimal rale of convergence for QSA? Consider the most basic one-dimensional problem which f(),; E = - + Ege with & a vero-mean signal. The special case a = 1/((1 + 1) results in an approximate average:
1 1+T
O , = 1+T
& dt
(4)
If for example & = sin(wt) then the right hand side converges at rate O(T which translates to 2) for the "MSE"; this is far faster than the rate O(T-1) expected for SA.
The special case of pure averaging is illustrated at the top Fig. 1. The bold question mark in the figure refers to a question regarding a natural extension of the linear example in (4): can we obtain the same rute of conver- gence for general non-linear QSA? This question is posed and answered in the affirmative in [30, $ 4.9], achieved through the averaging technique of Polyak and Ruppert, but only under conditions on the QSA ODE that could not be verified a priori. The current paper not only provides ways to ensure such conditions are always met, but also answers this question in much more optimistic manner:
wT cos(wi)))
sin(wt)
AVG
0" +01/T)
sin(wi)
QSA
0r + O(L/T) ?
Figure 1: What is the optimal convergence rate for QSA?
the presumption that MSE rates of order O are optimal for general QSA is fallacy since for any 0, rates of order ||Or - 112 = (T 146) can be achieved through design.
The astonishingly fast MSE rates obtained for general QSA are a result of the perturbative mean flow (p-mean flow) representation for the QSA ODE. This representation expresses (3) terms of the average vector field f.
2-1 d' ai
O a.l a. Y, Wi),
W. Σ (=0
W
dt
where (W) : = 0, 1, are smooth functions of larger state process, and Y, = r(,,) with Y also smooth (see Thm. 2.1).
This representation is valuable only after boundedness of (Qt) is established, for which sufficient conditions are provided in [30, Prop. 4.33 and 4.34) (these conditions form part of Assumption (QSA3) in the supplementary material). A linearization of (5) around 6* gives
e a (0,- 0*) T + W; + o(I@, - - 13)
(6)

---

Polyak- Ruppert
Forward-Backin Backward
0.8
Figure 2: Rates of convergence for PR averaging and forward-hackwand algorithms.
where A" - af(()) and Y 7(0*). The upper bound ||O; - 00 (aa)) (previously obtained in
[9, 30]) follows easily from (5).
Given estimates {O, 2 0}, Polyak-Ruppert (PR) averaging defines the new estimates follows,
T T To [" O dt,
1
Of
T> To:
where the interval [0, To] is known as the burn-in period. The time-average of (W/ is of order Oaa)), implying the rate | 0- 2|2 = O(T if and only if Y O.
This brings us the main contributions:
The p-mean flow representation (5) is introduced for the first time in Thm. 2.1.
(ii) Convergence rates arbitrarily close (T-)
2) can be obtained (so that the MSE arbitrarily close to O(T-*)), which is far faster than the bound O(T assumed in prior research.
(iii) The near quartic rates for MSE are established for PR averaging in Thm. 2.2, subject to the assumption that Y 0. Sufficient conditions the probing signal & are provided in Thm. 2.1 to ensure that Y = 0.
(iv) An alternative rates without the special conditions imposed in Thm. 2.2 (see Thm. 2.3).
averaging introduced: forward-backware filtering achieves near quartic
The theory is refined in the context of gradient free-optimization, and the general theory is illustrated through numerical examples in this setting.
While theory is developed in continuous time, simulation studies using Euler approximations are consistent with theory. The plots shown in Fig. are based on two-dimensional example, whose details can be found in Section 2. The change of notation is also explained there: (2p)²
O
8.
where is a design parameter subject to < 1. The forward- backward algorithm is a new algorithm introduced in this paper, that achieves the O convergence rate; we find in these experiments that the same rates hold for the Euler approximation. Polyak-Ruppent Ruppert averaging (7) cannot obtain this fast rate of convergence, because the frequencies used in this experiment violate critical assumption in Thm. 2.2.
1.4
3 1=16 1.6
n
10
10a
xx10
10x102
Figure 3: Quasi Monte Carlo using QSA with Polyak-Ruppert averaging. Histograms for 10 x 7 10a.
Fig. 3 illustrates how the techniques introduced in this paper specialize to quasi-Monte Carlo (QMC), based on two in- stances of the algorithm: one designed using = / 8 = 1.4, and the other with 3 = 1.6. Details found in the supplementary material.
1.1 Preliminaries
short literature survey and notation glossary are provided here.
Literature review: RuppertRuppert (PR) averaging was introduced in [39, 35, 36), and now a standard workhorse in machine learning [14, 32, 31, 30).
Quasi-Monte Carlo (QMC) remains an active area research for applications to estimation and optimization [33]. One aspect of the theory concerns techniques to construct sequence {G:

---

i E 2+} C [0, 1| so that sample path averages are convergent, n as n + oo for functions g: Rx + R, with j uniform; theory predicts a convergence rate of O(log(n)K //n) (see e.g. [1, Section 9.3]).
"i== - S g(x) p(dx)
is shown in Thm. 1.1 of the present paper that the convergence rate O(1/n) holds for QMC, subject to smoothness condition the function, and careful design of the probing signal. The main results of this paper hinge on these new bounds for QMC, and further refinements. These bounds are based in part on refinements of Baker's Theorem [28. 8).
QSA was first applied to finance in [20, 22]. Stability and convergence theory for QSA is recent 19, 301, following preliminary results in [3]; this work was motivated by applications to extremum seeking control, and successful application of QSA to Q-learning in [29].
The linear QSA ODE is treated in [40], where the first bounds on the rate of convergence of order O(at) were obtained. This bound was extended general nonlinear QSA in [9, 30), and it was also shown that the use of PR averaging results in convergence rate of O(T-1) subject to (up to now) unverifiable conditions.
QSA with fixed step-size is the topic of the contemporaneous work [24, 25J. An analog of the p-mean flow representation (5) obtained, along with both steady-state and transient error bounds
Gradient-fin optimization (GFO) concerns minimization of an objective function I' R + R based solely measurements of ((0) for selected values of & E Rdd The algorithms of Keifer and Wolfowitz are early examples [17, 6, 4, 15, 1]. The QSA ODEs for GFO considered in this paper inspired by the simultaneous perturbation stochastic approximation (SPSA) algorithms of Spall [41, 42, 43]. Two examples are of the form (2), with
1SPSA:
IISPSA (Ons Su+1)
1 -a+ [(0 EGn+1)
(8a)
8
1
2SPSA:
FaSPSA Sn+1)
(Sa+1 [T(,,, + E5n41) - r(On - =Gn+
(8b)
2e
where 0 and {Sn} } is zero-mean i.i.d. sequence.
These algorithms are biased in general unless the probing gain E is vanishing function of There is substantial research in this setting: the best possible convergence rate for the mean square error is O(n (0) with 3 = (p- - (2p) provided the objective function p-fold differentiable at 8* [37]. Upper bounds appeared earlier in [13]. See [12, 11, 45, 34, 21] for more recent history.
Deterministic versions of SPSA were analyzed [5] without sharp rates of convergence. The present paper follows the approach of [30, $ 4.9], in which the applications to gradient-free optimization result in algorithms that resemble simple versions of the ESC algorithms surveyed in [48, 26] (see [25] for more on the relationship between ESC and QSA).
Notation: We restrict to probing signals that nonlinear functions of sinusoids, of the form
E, = GGG(E) with E, (cos(2 + d1)), cos(2 + Φx|)]T
for which Go RKK + RM is analytic on CK {or} are arbitrary, and assumptions the distinct frequencies {wi} will be imposed the main results. When Go is linear we obtain the mixture of sinusoids
of cos(27(wrt + del), for vectors {ut) C I
(10)
Denote i exp(2iTjwut + osl) for each and t, which defines the K K-dimensional vector-valued ④, function of time evolving on Q (2 E ok |2/- = 1 isis K}. Writing G(z) == Go((2
2- 2/2) for non-zero CKK we obtain & G(D.).
For two real-valued functions of time {4 t 0, i 1,2) denote
( dtd dt,
/'
( (5:
lim T T=x0 T
(z") = lim T T- T 2 dt,
2= 2 (22) (11)
The notation is extended to vector or matrix valued functions. In particular, (E) = E R" and E (EET) is m m matrix.

---

The functions of time used in (11) are frequently obtained as functions of (0;, Ex) [or more generally,
(o,, }.)]- If h: IRd x Im - R we often write h4 = h(O & and h = h(0", E.) to save space, and use the alternative notation h (h); identical notation is used for functions of (@,, Φ,).
Let h denote a solution of Poisson's 's equation (12) with forcing function h: I - IR, which satisfies the defining equations,
((Tr== h(E,) di ((oo), T20, to Q
(12)
It is assumed throughout that the solution is normalized so that its mean is zero. Thm. B.1 in the supplementary material provides conditions ensuring smooth solution.
For continuously differentiable (C") function g: Rd Q R. the directional derivative in the
direction of the QSA vector field f is denoted
[D' g) =) deg (0,z)- f(0, G(z)), (0, E R X Q
(13)
For vealur-valued function 6, O, indicates that there a constant B such that [[0())) I Bö, for all t. That is, we are only asserting
the notation O();) to denote a function of t; the notation
an upper bound. For example, if o, 1/(1 1) we not claiming that [[0(6)]] s B83 is not possible.
Organization: Section 2 summarizes the main contributions of the paper, and Section provides illustrations of the theory in application to GFO; in particular, convergence rate bounds are validated for GFO algorithms based on QSA. Conclusions and directions for future research are summarized in Section 4. Technical proofs and additional numerical results can be found in the supplemental material.
Towards Quartic Rates
2.1 Quasi-Stochastic Approximation
We begin with foundations regarding the QSA ODE (3) from [30, Ch. 4.5, 4.9]. The mean vector field is defined by the sample path average,
/'" [00, Ex) dt, 0 d Rdd
f(0) = lim
(14)
T T
Theory is based on comparison with the ODE,
d o = a. [ for t 2 to and θ = Otg
(15)
at
The time to is fixed, but chosen suitably large in analysis of convergence rates.
The full list of assumptions (QSA)))(QSA5) may be found in the supplementary material. We settle for brief summary here: (QSA0) specifies conditions on the frequencies in (9). The assumptions allow the following special case: fix W1 > 0 and an increasing sequence of positive integers {n;}. and choose the probing signal of the form (9) with
Wi n,W1 and di = 1101, S<isK.
(16)
See Prop. A.1 for explanation.
(QSAI) concerns the gain process; in the body of the paper we take a, an - for pe e (1/2, 1] and constant an O. (QSA2) imposes global Lipschitz bounds on f and f. (QSA3) imposes global asymptotic stability of the mean flow de 0, f(,) and minor additional assumptions. (QSA4): C², A(0)= f (0) bounded and Lipschitz continuous, and A A(0*) is Hurwitz. (QSA5): existence of functions f, and Y that are Lipschitz continuous in 0 solving for each 0 S to $ t1,
(0,
F(B, E.) dt Pt.),
F(0. E.) = ((0,E)) f(()
f(0, (1o))
f(0, Ex) dt + f(0, ).,)
(17)
to
(0, 11o))
T(0, ②.) dt + 900 tT,),
7(0, r(0, ((0)
to
5

---

where for 2(0,E)==08) = -o (0,
Y(0) = lim 1 o T-200 T / Y(0, (.) dt
Y(0, (x) -A (0) Ex),
(18)
A E) = A(0) for all and & then T(0)) = This is a very restrictive special case, though does hold for QMC for which A(0, L) I. In broad generality, we can always ensure Y(0") = by designing algorithm with & satisfying (QSA0) as shown in part (ii) of Thm. 2.1.
The solutions to Poisson's 's equation in (17) used to define the terms in (5):
Theorem 2.1. Suppose that (QSAI) holds and a; = (1 + P) with p E (0, 1).
ii Under (QSA5), the p-mean flow representation (5) holds with
( +.) - -D 4..)
T2
[D A(,,, (.)
(19a)
at
(O, P,) -ID -ID/ 2,) r(,,, D,)
(19b)
(O, 2x) -(0,,, 21) where Tt p/ + 1)
(19c)
(ii) (QSAO) and (QSA5) hold, then Y(0) for each 0 E Rd.
(iii) If (QSA2) and (QSA3) hold, then {Or} is ultimately bounded: there exists b < 3o such that for any Og lim sup,->oo ||O||| < b.
Proof: The proof of part (i) is given at the end of Section B.3, while part (iii) follows from [30, Prop. 4.33 and 4.34).
Part (ii) is based on the geometry illustrated in Fig. 4: S denotes the set of functions I + IR that are analytic functions of the probing signal, and S the set of functions h: Q + that have zero mean and solve Poisson's 's equation for some these two function classes in L2: (g, f)) = for each g E S
8 - ho amalytic)
S. Corollary 8.6 establishes orthogonality of
and h E S (in the notation (11)), which indicates
Figure 4: Hidden geometry: orthogonality
lim T'+00
g( ((E,) (. (.) di = 0, for each to
of the function classes S and S.
The definition (18) gives
d
Y:(0, ②) - Σ
(0, (0,,(0E))
for each & E R. and each & E Q.
j=1
Since (0, .) 3 and f0, .) E for each j.j and 6, it follows that Y(0) = 0.
2.2 Acceleration
Two approaches to obtain the convergence rate bounds ||0, - 0- = (aaz)) are described here.
Polyak-Rupper averaging Fast convergence can be obtained using standard averaging, but only under restrictive conditions. In Thm. 2.2 we adopt the notation,
Y -[A*]-' where F. -==-(00) -00",,
f==-(0" 11), 12 0
(20)
The proof of Thm. 2.2 is postponed to the supplementary material.
Theorem 2.2. Suppose that (QSA)) hold, and the following additional assumptions are
imposed: (Q.} obtained using a; (1+1)-P with p E 1/2, 1), and estimates using PR averaging (7) are obtained using To = (1 1/x)T with α. > 1 fixed. Then,
O 0" a. Y f. o(a:)
(21a)
OR 0r ar|c(k, p) + o(1)]²* + 20T
(21b)
with c(x, p) x(1 - (1 1/1))- -

---

Thm. 2.1 and the definition (20) imply that Y = 0 under (QSA0). Eq. (21b) of Thm. 2.2 then implies that PR averaging leads to a convergence rate bounded by O(T 3p), subject (OSA))(QSAS))
It was discovered recently that the vector Y also appears in representations of the SA recursion (2) when {Sn) is a smooth function of a Markov chain. This introduces bias and potentially large variance for fixed step-size algorithms (an+1
> 0), even when using averaging [24, $2.5.3),[23].
forward-backward filtering We present technique achieve near quartic MSE convergence rate without imposing additional structure on the probing signal. Motivation is two-fold: first, it is hoped that this technique can be extended SA for which there no known analog (QSA0); second, in some applications of QSA it may not be possible to ensure that (QSA0) is satisfied.
Forward-backwant (FB) filtering is defined by pair of QSA ODEs:
er a ( E,
O 2 1 + e
(22)
where &T = E_ R is defined in (7), and @ is defined analogously using (0, Theorem 2.3. If the assumptions of Thm. 2.2 hold, then, 0 H OpT)))). 20).
Overview of proof: The analogous vector Y for the QSA ODE (22) denoted Y The identity Y = --y" is established through consideration of (20), and the desired bound is then obtained by combining (21b) with the definition (22).
Assumption (QSA0) implies that the frequencies {wi) are irrationally related. This might appear far stronger than needed: for one, the full rank condition for Σg can be achieved under far weaker assump- tions. In two dimensions, Σg / for each of the following special cases: & = (cos(t), (2)() and & (tos(t), si However, in each case we can construct second order polynomial h: R²² + R such that h(E,) 0 for all f, so that the excitation implied by the full rank condition is lost through simple nonlinearity. This is only the first sign of trouble.
We consider next a numerical example designed with four positive frequencies that are linearly independent over the rationals, denoted (wi, w2 wa wa]. Consider the linear QSA ODE,
dt θ = a.f((0) &x) (1 "(AA" + 02 + 106;]
[siin(unt) sin(w
sin(w)) 4 siinwal()
2 cos( cos(wal)
with Ag =
and A" Hurwitz.
We have f(0) A 8 and hence lr O. To fit the notation (9) we must take & E R. which can be chosen so that Σg I. The expression Y 20/22/w1, 1/wa] follows from (20).
The conclusions of Thm. 2.3 are illustrated in Fig. 2. The model was simulated with A = 0 and frequencies ir v3, 4, v5)/5. The QSA ODEs were constructed using three values of the parameter in the gain process, p 0..,,..7,0.8),
The plots shown on the left in Fig. were obtained using PR averaging with To (1 - 1/x)T and x = 4. The convergence rate O(T-P) because Y * 0 (recall (21b)). FB filtering achieves the convergence rate of (27-))), for each value of tested, predicted by Thm. 2.2.
3 Gradient-Free Optimization
We now turn to applications to gradient-free optimization (GFO). It is assumed that the objective C2 and that it has unique minimizer denoted gept, and that De := (EET) is full rank.
I: Rdd
3.1 Gradient-Free Optimization and QSA
Two approaches are considered in the following: For >> 0 and each O, Rd.
fl),O,, & = = - +100:+=t,, +
1gSGD:
(23)
2gSGD:
(0))),))) = (, + +tE,) - ((0) - =E,)
(24)
20
7

---

The mean vector fields f 10 9 are identical, provided the probing signal is symmetric:
Proposition 3.1. Suppose (QSAI)(QSAS) hold, that I is C2 with unique minimizer (0pt, Assume moreover that the probing signal is of the form (10) with m = d and distinct frequencies {ws). Then, the average vector fields for 1gSGD and 2gSGD are equal:
f(0) = (0, E)) = (f2) = 2 + +
(25)
For the special case of strongly convex objective bounds on bias of 2qSGD are well known [44]. An application of Prop. 3.1 implies that the bias for LqSGD is identical:
Corollary 3.2. Suppose the assumptions of Prop. 3.1 hold, and I' is strongly corvex.
Then, |00 (000) S ) for either 1qSGD or 2qSGD.
Dimension
Dimension 2
(
1SPSA
02
x10
1qSGD
78h VurEs)
PR Forward Barkward
1qSGD
T
<10
x19
Figure 5: Rastrigin objective (top left), scaled trace of empirical covariance (bottom left), histograms of estimation error for ISPSA with PR averaging (top middle and top right), histograms of estimation error for 1gSGD with PR averaging (bottom middle and hottom right).
3.2 Numerical Examples
The numerical results surveyed here and in the supplementary material used crude approximation of the QSA ODE: an Euler scheme with sampling interval of 1 sec. is found that the results remain consistent with theory for moderate dimension. metric for testing this theory was via the empirical covariance, obtained using M 2 50 independent runs to obtain 0
s M). and then
M
ET
0 0,
Ö
1 M 1=1
Σ
(26)
M
Thm. 2.2 and Thm. 2.3 predict that the root mean square error Top (i((E)) is bounded in T, subject conditions.
Rastrigin: The algorithms were tested in this standard benchmark [47], for which plot of the objective can be found on the upper left in Fig. 5. In each qSGD ODE the values 0.25 and p 0.85 were used, with PR averaging. In the SPSA stochastic counterparts the ex- ploration sequence (S..) was chosen i.i.d. and zero-mean, with values in (+v2) (these values
Finelo04
02
5 in
0,5
chosen that the covariance matrices for both SPSA and qSGD would equal). Further details on the experiment are postponed to the supplementary material.
As predicted by theory, the root-MSE T (Σr) is bounded in T when using FB filtering or PR averaging: see the plot on the lower left Fig. 5. Histograms are shown only for 1gDGD and 1SPSA using PR averaging. The results
1.5
0
4.5
-2
40.5
0.5
1.0
Figure 6: [Or) for final 66% of the run, and (@PR) for the final 33%.

---

obtained for 1gSGD with FB filtering were similar. Results obtained using 2qSGD and 2SPSA were similar qualitatively. Outliers, identified with Matlab's 's isoutlirr function, are excluded in these plots. Outliers were found in 20% of the independent runs for ISPSA, and none for 1gSGD. Outliers for deterministic algorithms were observed in other experiments, but fewer than their stochastic counterparts.
Fig. shows part of the trajectory of {Or} for a short run. We see that {0r} oscillates between saddle points and local extrema before settling around the minimizer ( = 0 near the end of the run. The corresponding PR estimates very closely approximate 2ee for the final 33% of the run.
T ((E))
Averaging
Forward Backward
(
d 30
10'
107
10f
104
10
Tinge
Figure Ackley objective d (right). Scaled root-MSE for (left) and 30 (middle).
Ackley: This is another standard benchmark [47]. Its objective function is shown on the right in Fig. 7 in the special case d 2.
Fig. shows the scaled root-MSE for dimensions d 2 and = 30 with = 0.85. Both PR averaging and FB filtering successful in achieving OTT)2p) convergence rates. We observe much
larger values of tr (Er)a ) at the end of the run for d 30. It is possible that better results will be improved by with a different choice of probing signal
P
10
Cr
((0)
11
1//
10
13/2
104
Figure Average of ((e)) over S i S independent rums for three-hump camel.
Three- Three-Hump Hump Camel: This is another standard benchmark [47], whose objective function is plotted on the right Fig. Results from experiments using PR averaging, surveyed in Section C.2, show that the root-MSE is similar to what is obtained for the Ackley objective with d = 2. In this example the value (()))) converges rapidly towards its optimal value of zero.
Conclusions
While it is convenient design exploration around i.i.d. signals, and this approach opens the doors to many powerful tools from probability theory, we have shown that deterministic "noise" has significant benefits. Convergence rates can be accelerated dramatically provided the algorithm and deterministic probing signals are chosen with care.
There many avenues for future research:
A The impact of dimension on convergence rate appears to understood for QMC [1]. We currently do not know how to extend this theory to QSA because our analysis is rooted in properties of the K -d-imensional clock process 4, which is far removed from the QMC setting.
The optimal convergence rate for QSA is unknown for the approaches described in this paper, and currently lack universal bounds that are not restricted to particular algorithm.

---

(i) Can we improve the upper bounds for PR averaging and the FB algorithm? It may be possible achieve the bound O rather than O 30) in current theory.
(ii) Can find fundamental bounds for any algorithm? We haven's 't ruled out the creation of algorithm with rate of convergence of order O This question is motivated by long history of success in the stochastic approximation literature [10, 39, 35, 36, 37).
A It is not clear that the constraint p 2 is required in this deterministic setting, and may be removed if we can improve the bounds in our analysis. We have found in some experiments that the use of PR averaging results in very fast convergence even when this constraint is violated.
A Under what conditions is V (t(ET) strictly smaller using the FB algorithm as compared to PR averaging? We find in experiments that the FB algorithm usually outperforms averaging, but we have yet to find tools to obtain bounds that are rich enough to compare the two approaches.
Acknowledgements Many thanks to Profs. Yann Bugeaud (U. Strasbourg) and Gisbert Wüstholz (ETH) for guidance on the literature surrounding Baker's Theorem.
Financial support from ARO award W911NF2010055 and National Science Foundation award EPCN 1935389 is gratefully acknowledged
10

---

References
[1] S. Asmussen and W. Glynn. Stochastic Simulation: Algorithms and Analysis, volume 57 of Stochastic Modelling and Applied Probability. Springer-Veriae New York, 2007.
[2] H. Attouch, X. Goudou, and Redont. The heavy ball with friction method, the contin- uous dynamical system: global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system. Communications in Contemporary Mathematics, 2(01):1-34 2000.
[3] A. Bernstein, Y. Chen, M. Colombino. E. Dall' Anese, P. Mchta, and S. Meyn. Quasi-stochastic approximation and off-policy reinforcement learning. In Proc. of the Conf. on Dec. and Control, pages 1251, Mar 2019.
[4] S. Bhatnagar and V. S. Borkar. Multiscale chaotic SPSA and smoothed functional algorithms for simulation optimization. Simulation, 79(10):5685580 2003.
[5] S. Bhatnagar, M. C. Fu, S. I. Marcus, and I.JJ. Wang. Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences. ACM Transactions on Modeling and Computer Simulation (TOMACS), 13(2):180-20,, 2003.
[6] S. Bhatnagar, H. Prasad, and L. Prashanth. Stochastic Recursive Algorithms for Optimization: Simultanouss Perturbation Methods. Lecture Notes in Control and Information Sciences. Springer, London, 2013.
[7] V. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint, Hindustan Book Delhi, India and Cambridge, UK, 2nd
Agency and online edition, 2021.
[8] Y. Bugeaud. Linear forms in logarithms and applications, volume 28 of IRMA Lectures in Mathematics and Theoretical Physics. EMS Press, 2018
[9] S. Chen, A. Devraj, A. Bernstein, and S. Meyn. Revisiting the ODE method for recursive algorithms: Fast convergence using quasi stochastic approximation. Journal of Systems Science and Complexity, 34(5)_1681-1702, 2021.
[10] K. I.. Chung. On stochastic approximation method. The Annals of Mathematical Statistics, 25(3):463-433 1954.
[11] J. Dippon. Accelerated randomized stochastic optimization. The Annals of Statistics, 3164):1260- 1281, 2003.
[12] J. Dippon and J. Renz. Weighted means stochastic approximation of minima. SIAM Journal on Control and Optimization,
1997.
[13] V. Fabian. On the choice of design in stochastic approximation methods. The Annals of Mathematical Statistics, pages 457-465, 1968.
[14] A. Fradkov and B. T. Polyak. Adaptive and robust control in the USSR. IFAC- IFAC-PaperSOnLine, 53(2):13731137,, 2020. 21th IFAC World Congress.
[15] A. Gosavi. Simulation-burl based optimization. Springer, Berlin, 2015.
[16] P. Karmakar and S. Bhatnagar. Two time-scale stochastic approximation with controlled Markov noise and off- policy cemporal-differentt learning. Math. Oper. Res., 43(1):130-155 2018.
[17] Kiefer and Wolfowitz. Stochastic estimation of the maximum of regression function, Ann. Math. Statist., 23(3):462-466, September 1952.
[18] V. R. Konda and J. N. Tsitsiklis. Convergence rate of linear two-time-scale stochastic approxi- mation. Ann. Appl. Probab., 14(2):796-811 2004.
[19] N. B. Kovachki and A. M. Stuart. Continuous time analysis momentum methods. of Machine Learning Research, 22(17):1-40) 2021.

---

[20] B. Lapeybe, G. Pages, and K. Sab. Sequences with low discrepancy generalisation and applica- tion Robbins-Monro algorithm. Statistics, 21(2):251-27,, 1990.
[21] J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287-404, 2019.
[22] S. Laruelle and G. Pagès. Stochastic approxmaaton with averaging innovation applied to finance. Monte Carlo Methods and Applications, 18(1):1-51, 2012.
[23] C. K. Lauand and S. Meyn. Bias in stochastic approximation cannot be eliminated with averaging the outlook is far better for quasi stochastic approximation. In preparation (extended abstract in the Proc. of the Allerton Conference on Communication. Control, and Computing), 2022.
[24] C. K. Lauand and S. Meyn. Markovian foundations for quasi stochastic approximation with applications to extremum seeking control. arXiv 2207.06371, 2022.
[25] C. Lauand and S. Meyn. Quasi-stochastic approximation: Design principles with applications to extremum seeking control. IEEE Control Systems Magazine (to appear), 2022.
[26] Liu and M. Krstic. Introduction extremum seeking. In Stochastic Averaging and Stochastic Extremum Seeking, Communications and Control Engineering. Springer, London, 2012.
[27] E. M. Matveev. An explicit lower bound for homogeneous rational linear form in logarithms of algebraic numbers. lavestiya: Mathematics, (2(4):733-772, aug 1998.
[28] E. M. Matveev. An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers. ii Izvestiya: Mathematics, 6416): 2000.
[29] G. Mehta and S. Meyn. Q-learning and Pontryagin's minimum principle. In Proc. of the Conf. on Dec. and Control, pages 3598-3605, Dec. 2009.
[30] S. Meyn. Control Systems and Reinforcement Learning. Cambridge University Press, Cam- bridge, 2021.
[31] W. Mou, C. Junchi Li. J. Wainwright, P. L. Bartlett, and M. I. Jordan. On linear stochastic approximation: Fine-grained Solyyak-Rupeer and non-asymptotic concentration. Conference on Learning Theory and arXiv:2004.04719, pages 2947-2997, 2020.
[32] E. Moulines and F. R. Bach. Non-asymptotic analysis stochastic approximation algorithms for machine learning, In Advances in Neural Information Processing Systems 24, pages 451-459, 2011.
[33] A. B. Owen and P. W. Glynn. Monte Carlo and Quasi-Monte Carlo Methods. Springer, 2016.
[34] R. Pasupathy and Ghosh. Simulation optimization: A concise overview and implementation guide. Theory Driven by Influenial Applications, pages 122-150 2013.
[35] B. T. Polyak. new method of stochastic approximation type. Avtomatika telemekhanika (in Russian), translated in Automat. Remote Control, 51 (1991), pages 98-107, 1990.
[36] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM
J. Control Optim., 30(4):838-855 1992.
[37] B. T. Polyak and A. B. Tsybakov. Optimal order of accuracy of search algorithms in stochastic optimization. Problemy Peredachi Informatsii (Prob. Inform. Trans.), 26(2):45-53, 1990.
[38] H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407, 1951.
[39] D. Ruppert. Efficient estimators from a slowly convergent Robbins- processes. Technical Report Tech. Rept. No. 781, Cornell University, School of Operations Research and Industrial Engineering, Ithaca, NY, 1988.
12

---

[40] S. Shirodkar and S. Meyn. Quasi stochastic approximation. In Proc. of the American Control Conf., pages 2429-2435, July 2011.
[41] Spall. A stochastic approximation technique for generating maximum likelihood parameter estimates. In Proc. of the American Control Conf. pages 1161-1167. IEEE, 1987.
[42] J. C. Spall. Multivariate stochastic approximation using simultancous perturbation gradient approximation. IEEE transactions on automatic control, 37(3):332-3411 1992.
[43] J. C. Spall. A one-measurement form of simultaneous perturbation stochastic approximation. Automatica, 33(1):109-112, 1997.
[44] C. Spall. Introduction to stochastic search and optimization: estimation, simulation, and control. John Wiley & Sons, 2003.
[45] J. C. Spall. Stochastic optimization. In Handbook of computational statistics, pages 173-201. Springer, 2012.
[46] W. Su, S. Boyd, and E. Candes, A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. In Proc. Advances in Neural Information Processing Systems, pages 2510-2518, 2014.
[47] S. Surjanovic and D. Bingham. Virtual library of simulation experiments: Test functions and datasets. Retrieved May 16, 2022, from http:://wxt sfu caa" jssuraano.
[48] Y. Tan, W. Moase, C. Manzie, D. Nešić, and I. Mareels. Extremum seeking from 1922 to 2010. In Proc. of the 29th Chinese control conference, pages 14-26. IEEE, 2010.
[49] J. Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning, 16:185-202, 1994.
[50] G. Wüstholz, editor. A Panorama of Number Theory Or-The View from Baker's Garden. Cambridge University Press, 2002.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 4
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.1 for overview of the assumptions. A complete list is found in the supplementary material
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are in the supplementary material, with overviews of all significant results in the main body.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] Code and data are not provided, but all details required for reproduceability are provided
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Details on experiments are specified in the supplementary material
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] It is mentioned in the supplementary material
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "lw3TYGTQ7A", "reviewer": "Reviewer_DYiM", "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.", "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?\n\n2. How to translate the Quasi-Stochastic Approximation ODE to a stochastic algorithm?\n\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n(i) The paper is well-written. The main message of the paper is very clear.\n(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).\n\nWeaknesses:\n(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.\n\n(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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b3xB4J-tZDo", "reviewer": "Reviewer_dkZC", "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.\n\n\n", "questions": "  ", "limitations": "This is a theoretical work with no foreseeable negative societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\n- 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.\n\n- Quality: Technically strong, highly general results, advanced techniques.\n\n- 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:\n\n     * \\[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)\n     * \\[B] \"Accelerating optimization and reinforcement learning with quasi stochastic approximation\". (Chen, Shuhang and Devraj, Adithya and Bernstein, Andrey and Meyn, Sean)\n\n- Significance: The results are quite important as they extend and relax several assumptions made so far in the quasi-stochastic approximation litterature.\n\n**References**\n\n- \\[A]: @article{bernstein2019optimal,\n  title={Optimal rate of convergence for quasi-stochastic approximation},\n  author={Bernstein, Andrey and Chen, Yue and Colombino, Marcello and Dall'Anese, Emiliano and Mehta, Prashant and Meyn, Sean},\n  journal={arXiv preprint arXiv:1903.07228},\n  year={2019}}\n\n- \\[B]: @inproceedings{chen2021accelerating,\n  title={Accelerating optimization and reinforcement learning with quasi stochastic approximation},\n  author={Chen, Shuhang and Devraj, Adithya and Bernstein, Andrey and Meyn, Sean},\n  booktitle={2021 American Control Conference (ACC)},\n  pages={1965--1972},\n  year={2021},\n  organization={IEEE}}", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "C0nROcIqnU", "reviewer": "Reviewer_JEVp", "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.", "questions": "One question:\n\nIn 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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper has the following strengths in terms of the originality, quality, clarity and significance:\n\nOriginality 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.\n\nQuality: 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.\n\nClarity: 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.\n\nFrom 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-SCDLbEIQJK", "reviewer": "Reviewer_SkSg", "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.", "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$.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nI 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. \n\nAlthough 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. \n\nOverall, 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept