Global Convergence and Acceleration for Single Observation Gradient Free Optimization

Caio Kalil Lauand; Sean Meyn

REVIEW 4 major objections 7 minor 25 references

Global Convergence and Acceleration for Single Observation Gradient Free Optimization

T0 review · 4 major / 7 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A state-dependent probing step makes 1SPSA globally convergent, and zig-zag exploration reduces its target-bias variance from $1/\epsilon_\bullet^2$ to $\epsilon_\bullet^2$.

desk verdict A credible convergence theorem for 1SPSA with state-dependent gain, but the headline variance acceleration claim rests on an unproved covariance dominance step. read the letter →

arxiv 2509.04424 v1 pith:AAAWAQLH submitted 2025-09-04 math.OC

Caio Kalil Lauand , Sean Meyn This is my paper · ORCID

classification math.OC MSC 90C5662L20

keywords simultaneousperturbationstochasticapproximation1SPSAzeroth-orderoptimizationstate-dependentexplorationgainzig-zagglobalconvergencevariancereduction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Simultaneous perturbation stochastic approximation (SPSA) estimates a gradient from function values alone, and its single-observation version (1SPSA) is especially attractive when evaluations are expensive or noisy. The paper shows that the standard 1SPSA recursion can fail even on a quadratic objective: under i.i.d. symmetric perturbations and a shrinking or constant probing gain, the iterates can escape to infinity. Its central claim is that replacing the constant probing step by a state-dependent gain $\epsilon(\theta)$ makes the algorithm globally stable and convergent: for sufficiently small $\epsilon_\bullet$, the iterates converge almost surely and in mean square to a point $\theta^*$ whose bias from the true minimizer is $O(\epsilon_\bullet^2)$. Its second claim is that replacing i.i.d. perturbations by negatively correlated zig-zag perturbations changes the asymptotic variance of the target-bias estimate from at least $b_0/\epsilon_\bullet^2$ to at most $b_1\epsilon_\bullet^2$, so small probing steps no longer blow up the variance. A reader should care because this removes the prior boundedness assumption that was hard to verify for 1SPSA, and because the variance collapse makes the method usable with the very small probing steps that keep bias low.

What carries the argument

The central object is the single-observation random update written as a stochastic-approximation recursion $f(\theta,\Phi)=-\xi\Gamma(\theta+\epsilon_\theta\xi)/\epsilon_\theta$, whose conditional expectation defines the mean field $\mathrm{sf}(\theta)$. The argument runs on two mechanisms. First, the state-dependent gain $\epsilon_\theta$ from (4) makes $f$ uniformly Lipschitz in $\theta$ and gives the expansion $\mathrm{sf}(\theta)=-\Sigma_\xi\nabla\Gamma(\theta)+\bar\gamma_f(\theta)$ with $\|\bar\gamma_f(\theta)\n\le b\min\{\epsilon_\theta,\epsilon_\theta^2\}$, so for small $\epsilon_\bullet$ the mean flow is a small perturbation of the gradient flow and inherits its exponential stability. Second, the zig-zag sequence $\xi_n=\varsigma(W_n-W_{n-1})$ is telescoping, so the dominant variance term $\nu_{n+1}=-\xi_{n+1}\Gamma(\theta^*)/\epsilon_\bullet$ has zero asymptotic covariance; what remains is bounded by terms of order $\epsilon_\bullet^2$. This telescoping identity is what converts an unbounded $1/\epsilon_\bullet^2$ variance into a vanishing $\epsilon_\bullet^2$ variance.

What would settle it

Run the paper's own experiment: minimize $\Gamma(\theta)=\theta^2-\cos\theta-\sin(5\theta)/5+4$ with $\alpha_n=n^{-0.6}$, the state-dependent gain (4a) with $\epsilon_\bullet\in[0.05,0.1]$, and $N=5\times10^5$ steps, and measure the scaled covariance of the averaged gradients across 100 runs. If the zig-zag curve does not fall like $\epsilon_\bullet^2$ while the i.i.d. curve rises like $1/\epsilon_\bullet^2$, the variance claims in Proposition 2.2 are wrong. A second decisive experiment adds small i.i.d. observation noise: if the state-dependent-gain iterates diverge or fail to converge as Proposition 2.1 predicts, the noiseless assumption is the load-bearing gap.

Watch

Extended reading notes

Core claim

Under smoothness and coercivity assumptions on $\Gamma$, with step size $\alpha_n=\min\{\alpha_0,n^{-\rho}\}$ and the exploration gain $\epsilon(\theta_n)=\epsilon_\bullet\sqrt{1+\|\theta_n-\theta_{\mathrm{ctr}}\|^2/\sigma_p^2}$ (or the objective-based form $\epsilon_\bullet\sqrt{1+\Gamma(\theta_n)-\Gamma_-}$), the paper establishes that the random update $f(\theta,\Phi)=-\xi\Gamma(\theta+\epsilon_\theta\xi)/\epsilon_\theta$ defines a mean field $\mathrm{sf}(\theta)=-\Sigma_\xi\nabla\Gamma(\theta)+\bar\gamma_f(\theta)$ that is an exponentially stable perturbation of the gradient flow for small $\epsilon_\bullet$. Consequently the 1SPSA iterates are ultimately bounded for every initial condition and converge to a unique root $\theta^*$ of $\mathrm{sf}$, with $\|\theta^*-\theta_{\mathrm{opt}}\|=O(\epsilon_\bullet^2)$ when the Hessian at the optimum is positive definite. If the perturbation sequence is i.i.d., the empirical target bias $\widehat{\beta}^f_N$ has asymptotic covariance at least $b_0/\epsilon_\bullet^2$; if the perturbations are the telescoping zig-zag sequence $\xi_n=\varsigma(W_n-W_{n-1})$, the same covariance is at most $b_1\epsilon_\bullet^2$. The paper's numerical experiments with the objective $\Gamma(\theta)=\theta^2-\cos\theta-\sin(5\theta)/5+4$ reproduce both scalings.

Load-bearing premise

The proofs assume every function evaluation is noise-free; with additive observation noise the central martingale and mean-field decomposition no longer holds as written.

Editorial extensions

If this is right

With the state-dependent gain, 1SPSA no longer needs the prior almost-sure boundedness assumption; convergence is guaranteed from any initial condition under the paper's smoothness and coercivity hypotheses.
Because $\|\theta^*-\theta_{\mathrm{opt}}\|=O(\epsilon_\bullet^2)$, users can reduce bias simply by choosing a smaller probing step.
With i.i.d. exploration, the target-bias variance is bounded below by $b_0/\epsilon_\bullet^2$, so shrinking the probing step to reduce bias forces variance to grow without bound.
With zig-zag exploration, the same variance is bounded above by $b_1\epsilon_\bullet^2$, so bias and variance can be made small simultaneously.
Averaging the iterates, via the classical averaging technique for stochastic approximation, can accelerate the mean-square convergence rate to $O(1/n)$ when the exploration gain is held fixed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: The telescoping-exploration principle is not limited to first differences; a sequence such as $\xi_n=\varsigma(W_n-2W_{n-1}+W_{n-2})$ should push the dominant variance term to $O(\epsilon_\bullet^{2k})$, although the paper only analyzes the first-difference case and higher-order differences would require re-checking the drift condition.
Editorial inference: The variance collapse is proved for the empirical target bias and for small $\epsilon_\bullet$; transferring the same mechanism to the averaged gradient estimate or to a noisy-observation setting are natural next tests that the paper leaves open.
Editorial inference: Because the state-dependent gain takes larger probing steps where $\Gamma(\theta)$ is large, it may help escape poor regions in non-convex problems, but the paper's theorems assume a globally stable gradient flow, so that behavior remains untested.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know up front. The convergence story is solid: the state-dependent gain (4) plus the uniform Lipschitz property in Prop. A.1 make it credible that 1SPSA is ultimately bounded and converges to a point within O(ε²) of the optimum. The variance story is not: Prop. 2.2, which is the paper's most eye-catching claim, is missing the crucial bound on cross-covariance terms. I wouldn't take the 1/ε² vs ε² separation as a theorem yet.

What's genuinely new: the adaptation of the state-dependent exploration gain from [15] to 1SPSA, and the use of zig-zag exploration to drive the asymptotic covariance to zero. The paper is honest that the gain idea came from the authors' earlier ESC work; that self-citation is appropriate. The application of the ODE method from [5] is plausible and Prop. A.1 does real work in making the recursion Lipschitz. Prop. 2.1 I'd accept as likely correct under the stated assumptions.

Where it's soft, in increasing order of seriousness. First, Lemma A.4's drift condition verification is left to the reader; if it's straightforward, it should be written down or the reader sent to a specific result, since the main theorems import it. Second, the paper motivates 1SPSA as attractive precisely when observations are noisy, then assumes noise-free throughout. That's a real scope gap; the martingale-noise decomposition uses exactness, so the extension is not immediate. Third, the abstract says unmodified 1SPSA may diverge, but the body only shows numerical divergence for a quadratic; there is no divergence theorem. That overstates the evidence.

The main problem is Prop. 2.2. Part (i) says Σν_CLT dominates by inspection without checking that the cross-covariances between ν and ω+ψ don't cancel the ε^{-2} contribution. Part (ii) drops ν because telescoping sequences have zero asymptotic covariance, but the proof would need to show the summed cross-covariances with the O(ε) and O(ε²) terms are negligible at the right order. The stress-test note is right that this is exactly where the advertised rate comparison lives. Maybe it all works out, but the proof as written is a sketch at the critical point.

The numerics are simple but consistent; no code or data, which is fine for a theory paper.

Who it's for: people working on derivative-free stochastic approximation, simulation optimization, and ESC who want global convergence theory. A serious referee should engage with it, and I'd expect a major revision to supply the missing variance estimates. I would not desk reject.

Referee Report

4 major / 7 minor

Summary. The paper studies 1SPSA, the single-observation variant of simultaneous perturbation stochastic approximation, for minimizing a smooth coercive objective. Its two advertised contributions are a state-dependent exploration gain that is claimed to ensure global convergence from arbitrary initial conditions, and a new 'zig-zag' exploration scheme that is claimed to accelerate the asymptotic variance of the empirical target bias. The main theoretical results are Proposition 2.1 (almost-sure and mean-square convergence to a biased equilibrium with O(epsilon_bullet^2) bias) and Proposition 2.2 (a 1/epsilon_bullet^2 lower bound on the variance for i.i.d. exploration and an epsilon_bullet^2 upper bound for zig-zag exploration). The proofs are based on the ODE method and associated CLT results from Borkar, Chen, Devraj, Kontoyiannis, and Meyn. The paper also contains numerical experiments illustrating both the instability of unmodified 1SPSA and the variance reduction obtained by zig-zag exploration.

Significance. If the advertised results are fully established, the paper makes a substantial contribution to gradient-free optimization. It addresses a known instability of single-measurement SPSA by introducing a state-dependent gain, and it provides a concrete mechanism---negatively correlated exploration---that changes the variance scaling of the averaged target bias from divergent in epsilon_bullet to vanishing in epsilon_bullet. The paper also gives a useful numerical counterexample showing divergence of standard 1SPSA on a quadratic objective, and it places the analysis within a modern stochastic-approximation framework. The promised bias and variance rates are falsifiable and quantitatively sharp. However, several load-bearing proof obligations are currently left to the reader or dismissed as 'obvious', and the variance-rate argument in Proposition 2.2 has a genuine gap concerning cross-covariance terms. The paper is interesting and likely correct in its main conclusions, but the advertised rates have not yet been rigorously established in the submitted form.

major comments (4)

[A.5, proof of Prop. 2.2(ii)] The claim that 'telescoping sequences have zero asymptotic covariance' is insufficient to justify dropping the sequence nu_n and all its cross-terms from the asymptotic covariance of Delta*. It is true that Sigma_nu_CLT = 0 for the telescoping sequence nu_n, but this does not imply that the cross-covariance Sigma_{nu,omega+psi}_CLT vanishes. From Lemma A.6, nu_n is of order 1/epsilon_bullet while psi_n is of order epsilon_bullet, so terms such as E[nu_n psi_{n+1}^T] are of order 1, which is not negligible compared with the claimed O(epsilon_bullet^2) upper bound in (5b). The proof must show either that these summed cross-covariances are exactly zero for this particular construction or that they are O(epsilon_bullet^2). Without this, the advertised zig-zag acceleration bound is not established.
[A.5, proof of Prop. 2.2(i)] Part (i) of Proposition 2.2 asserts that the term Sigma_nu_CLT 'dominates' the asymptotic variance without providing a quantitative bound on the cross terms Sigma_{nu,omega+psi}+Sigma_{omega+psi,nu}. Although the orders of these terms suggest they are lower order than epsilon_bullet^{-2}, a lower-bound statement such as (5a) requires an explicit estimate showing that the sum of cross-covariances is o(epsilon_bullet^{-2}). Please supply this estimate rather than relying on inspection.
[A.3, Lemma A.4] Lemma A.4 verifies condition (DV3), a key hypothesis of [5, Thm. 4/5] that underpins both Proposition 2.1 and Proposition 2.2, but its proof is 'left to the reader'. A drift condition of the form (14) does not follow automatically from uniform ergodicity, and verification of the small-set and drift-growth conditions is a nontrivial part of the ODE method. This proof should be included in the appendix or replaced with a precise reference where this exact condition is verified for the two exploration chains.
[Section 1, noise-free assumption] The paper motivates 1SPSA by its suitability for noisy observations, yet it states that 'observations are noise-free' throughout. This is an explicit limitation, but its implications are not discussed. With additive observation noise, the 1SPSA update becomes f(θ_n, Phi_{n+1}) plus a noise term, so the martingale-noise decomposition in (8) and the mean-field representation in Proposition A.1 no longer hold as stated. The restriction should be stated in the introduction and abstract, and the paper should indicate what changes would be needed to treat noisy observations.

minor comments (7)

[Proposition 2.1] The text reads 'there is ϵ0• > 0' where 'there exists ϵ0• > 0' would be more natural; the same grammatical issue appears near the statement of Proposition 2.2(ii), which contains a duplicated 'such that such that'.
[Lemma A.5] The notation θ_PR_N is used without definition; please define the Polyak-Ruppert averaged iterate before invoking it.
[Section 3] The experiments report the scaled variance of the averaged gradient ∇Γ(θ_k), whereas Proposition 2.2 concerns the averaged mean-field value sf(θ_k). The text should explicitly state that the comparison uses the approximation sf ≈ −Σξ∇Γ from Proposition A.1, or should report the quantity appearing in the propositions.
[Section 1 and Figure 1] The text first describes the oblivious exploration case as ε_n = n^{-0.3}, then says Figure 1(a) corresponds to a constant exploration gain ε_n ≡ ε_bullet; this inconsistency should be corrected.
[Literature Review] The name 'Keifer and Wolfowitz' should be spelled 'Kiefer and Wolfowitz'.
[Appendix A.2] There is a typo: 'Lipshcitz' should be 'Lipschitz'.
[References] Reference [5] is cited as a preprint; the version published in Annals of Applied Probability 35(2) should be used.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main theorems are applications of an external general ODE-method theorem, not equivalents of the paper's inputs.

full rationale

Walking the derivation chain, I find no step in which a prediction is equivalent to its inputs by construction. Propositions 2.1 and 2.2 are proved by verifying the hypotheses of the general ODE-method theorems in [5] (uniform Lipschitz continuity of f in Prop. A.1, exponential stability of the mean flow in Prop. A.2, geometric ergodicity in Lemmas A.3-A.4, and the asymptotic covariance relation in Lemma A.5). Reference [5] is a published general theorem with Meyn as one coauthor; it is not tailored to 1SPSA, its stated assumptions do not include the target results, and it functions as external mathematical support. The state-dependent gain (4) originates in the authors' prior work [15], but that citation supplies a construction rather than an assumption containing convergence or the variance bounds. Prop. A.1's Taylor decomposition, the bound on the error term gamma_f, and the variance decomposition in Lemmas A.6-A.7 are derived in the appendix from the assumptions. I also note genuine completeness gaps that are not circularity: Lemma A.4 leaves the verification of the drift condition (14) to the reader, Prop. 2.2(i) asserts that Sigma_nu_CLT dominates without explicitly bounding all cross-covariance terms, and the paper assumes noise-free observations despite motivating 1SPSA through noisy settings. These are proof gaps or limitations, not reductions of the conclusions to the model inputs. The self-citations are present, but under the stated rules they do not by themselves make the derivation circular, so the score stays low.

Assumptions & free parameters 4 free parameters · 8 assumptions · 0 invented entities

The central claim rests on standard SA assumptions, the published ODE theorem from [5], and the assumption of noise-free observations. The algorithm modifications are design choices, not new physical or mathematical entities, so no independent falsifiable handles are required. The main unverified load is the omitted drift verification in Lemma A.4 and the reliance on an existential small-gain condition.

free parameters (4)

epsilon_bullet (exploration gain) = not fitted; assumed sufficiently small
The theorems require epsilon_bullet in (0, epsilon0], but epsilon0 is existential and not quantified. This is an algorithm design parameter, not fitted to data.
theta_ctr and sigma_p in state-dependent gain (4a) = user specified (0 and 1 in experiments)
The center and scale of the active exploration gain are chosen by the user; the theory allows any smooth positive gain.
zig-zag scale ς = 1/sqrt(2) in experiments
Positive scale for zig-zag exploration; set to match variance of i.i.d. in experiments. The theory allows any ς > 0.
kappa1, kappa2 in Figure 2 = chosen to align with simulated curves
The comparison functions r1 and r2 are fitted to the data to illustrate the predicted exponents; they are not predictions.

assumptions (8)

domain assumption (A1): step size alpha_n = min{alpha0, n^{-rho}} with rho in (1/2, 1)
Standard SA step-size decay; used in all theorems.
domain assumption (A2): Gamma is C^2 with globally Lipschitz first and second derivatives, and grad Gamma is coercive
Needed for Prop. A.1 Lipschitz and mean-field approximation.
domain assumption (A3): exploration W zero-mean i.i.d. on compact set with zero mixed third moments and positive covariance; xi_iid = W or xi_zigzag = ς(W_n - W_{n-1})
Defines the exploration statistics; zero third moment makes variance decompositions work.
domain assumption (A4): gradient flow d/dt x_t = -grad Gamma(x_t) is globally exponentially asymptotically stable with unique minimizer and positive definite Hessian at theta_opt
This is the convexity-like condition that makes the mean flow stable; it is restrictive for non-convex problems.
domain assumption Noise-free function evaluations (Section 1)
The recursion f(theta, Phi) has no observation noise; the theory does not cover the noisy case that motivates single-sample SPSA.
standard math The ODE method theorem [5, Thm. 4 and Thm. 5] applies
The main convergence and covariance limits are quoted from this published paper; the authors verify conditions, though one verification (Lemma A.4) is left to the reader.
standard math Khalil's Lemma 5.1 on perturbed exponentially stable systems
Used in Prop. A.2 to transfer exponential stability from gradient flow to mean flow.
ad hoc to paper Drift condition (DV3) holds for the exploration chains; proof sketched and part left to reader (Lemma A.4)
This is a key hypothesis of [5, Thm. 4] and is asserted but not fully proved.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Global Convergence and Acceleration for Single Observation Gradient Free Optimization." pith.science (2026). https://pith.science/paper/AAAWAQLH

@misc{pith2026250904424,
  author       = {Pith},
  title        = {Pith review of: Global Convergence and Acceleration for Single Observation Gradient Free Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AAAWAQLH}},
  note         = {Machine review of arXiv:2509.04424}
}

read the original abstract

Simultaneous perturbation stochastic approximation (SPSA) is an approach to gradient-free optimization introduced by Spall as a simplification of the approach of Kiefer and Wolfowitz. In many cases the most attractive option is the single-sample version known as 1SPSA, which is the focus of the present paper, containing two major contributions: a modification of the algorithm designed to ensure convergence from arbitrary initial condition, and a new approach to exploration to dramatically accelerate the rate of convergence. Examples are provided to illustrate the theory, and to demonstrate that estimates from unmodified 1SPSA may diverge even for a quadratic objective function.

Figures

Figures reproduced from arXiv: 2509.04424 by the authors.

**Figure 2.** Impact of exploration correlation when the exploration gain is small: (a) Using i.i.d. exploration the scaled variance grows as 1/ϵ 2 • . (b) Using zig-zag exploration the scaled variance vanishes as ϵ 2 • . There is substantial research in the vanishing probing gain setting: the best possible convergence rate for the mean square error is O(n −β ) with β = (p − 1)/p, provided the objective function is p-fold differe… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 23 canonical work pages

[15]

C. K. Lauand and S. Meyn. Quasi-stochastic approximation: Design principles with applications to extremum seeking control. IEEE Control Systems Magazine , 43(5):111–136, Oct 2023

work page 2023
[5]

Borkar, S

V. Borkar, S. Chen, A. Devraj, I. Kontoyiannis, and S. Meyn. The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. Annals of Applied Probability (preprint at arXiv e-prints:2110.14427), 35(2):936–982, April 2021

arXiv
[1]

Asmussen and P

S. Asmussen and P. W. Glynn. Stochastic Simulation: Algorithms and Analysis , volume 57 of Stochastic Modelling and Applied Probability . Springer-Verlag, New York, 2007

work page 2007
[2]

Bhatnagar and V

S. Bhatnagar and V. S. Borkar. Multiscale chaotic SPSA and smoothed functional algorithms for simulation optimization. Simulation, 79(10):568–580, 2003

work page 2003
[3]

Bhatnagar, M

S. Bhatnagar, M. C. Fu, S. I. Marcus, and I.-J. Wang. Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences. ACM Transactions on Modeling and Computer Simulation (TOMACS) , 13(2):180–209, 2003

work page 2003
[4]

Bhatnagar, H

S. Bhatnagar, H. Prasad, and L. Prashanth. Stochastic Recursive Algorithms for Optimization: Simul- taneous Perturbation Methods. Lecture Notes in Control and Information Sciences. Springer, London, 2013

work page 2013
[6]

V. S. Borkar and S. P. Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM J. Control Optim. , 38(2):447–469, 2000

work page 2000
[7]

J. Dippon. Accelerated randomized stochastic optimization. The Annals of Statistics , 31(4):1260–1281, 2003

work page 2003

Show all 25 references

[8]

Dippon and J

J. Dippon and J. Renz. Weighted means in stochastic approximation of minima. SIAM Journal on Control and Optimization , 35(5):1811–1827, 1997

1997
[9]

V. Fabian. On the choice of design in stochastic approximation methods. The Annals of Mathematical Statistics, pages 457–465, 1968

1968
[10]

A. Gosavi. Simulation-based optimization. Springer, Berlin, 2015

2015
[11]

H. K. Khalil. Nonlinear systems. Prentice-Hall, Upper Saddle River, NJ, 3rd edition, 2002

2002
[12]

Kiefer and J

J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of a regression function. Ann. Math. Statist., 23(3):462–466, September 1952

1952
[13]

Larson, M

J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287–404, 2019

2019
[14]

C. K. Lauand and S. Meyn. Approaching quartic convergence rates for quasi-stochastic approximation with application to gradient-free optimization. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems ,...

2022
[16]

C. K. Lauand and S. Meyn. Markovian foundations for quasi-stochastic approximation. SIAM Journal on Control and Optimization (pre-publication version arXiv 2207.06371) , 63(1):402–430, 2025

2025 arXiv
[17]

S. Meyn. Control Systems and Reinforcement Learning. Cambridge University Press, Cambridge, 2022

2022
[18]

S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability . Cambridge University Press, Cambridge, second edition, 2009. Published in the Cambridge Mathematical Library. 1993 edition online

2009
[19]

Pasupathy and S

R. Pasupathy and S. Ghosh. Simulation optimization: A concise overview and implementation guide. Theory Driven by Influential Applications , pages 122–150, 2013

2013
[20]

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. 11

1990
[21]

J. C. Spall. A stochastic approximation technique for generating maximum likelihood parameter estimates. In Proc. of the American Control Conf. , pages 1161–1167. IEEE, 1987

1987
[22]

J. C. Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approxi- mation. IEEE transactions on automatic control , 37(3):332–341, 1992

1992
[23]

J. C. Spall. A one-measurement form of simultaneous perturbation stochastic approximation. Automatica, 33(1):109–112, 1997

1997
[24]

J. C. Spall. Introduction to stochastic search and optimization: estimation, simulation, and control . John Wiley & Sons, 2003

2003
[25]

J. C. Spall. Stochastic optimization. In Handbook of computational statistics , pages 173–201. Springer, 2012. 12

2012

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [15]

C. K. Lauand and S. Meyn. Quasi-stochastic approximation: Design principles with applications to extremum seeking control. IEEE Control Systems Magazine , 43(5):111–136, Oct 2023

work page 2023

[2] [5]

Borkar, S

V. Borkar, S. Chen, A. Devraj, I. Kontoyiannis, and S. Meyn. The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. Annals of Applied Probability (preprint at arXiv e-prints:2110.14427), 35(2):936–982, April 2021

arXiv

[3] [1]

Asmussen and P

S. Asmussen and P. W. Glynn. Stochastic Simulation: Algorithms and Analysis , volume 57 of Stochastic Modelling and Applied Probability . Springer-Verlag, New York, 2007

work page 2007

[4] [2]

Bhatnagar and V

S. Bhatnagar and V. S. Borkar. Multiscale chaotic SPSA and smoothed functional algorithms for simulation optimization. Simulation, 79(10):568–580, 2003

work page 2003

[5] [3]

Bhatnagar, M

S. Bhatnagar, M. C. Fu, S. I. Marcus, and I.-J. Wang. Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences. ACM Transactions on Modeling and Computer Simulation (TOMACS) , 13(2):180–209, 2003

work page 2003

[6] [4]

Bhatnagar, H

S. Bhatnagar, H. Prasad, and L. Prashanth. Stochastic Recursive Algorithms for Optimization: Simul- taneous Perturbation Methods. Lecture Notes in Control and Information Sciences. Springer, London, 2013

work page 2013

[7] [6]

V. S. Borkar and S. P. Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM J. Control Optim. , 38(2):447–469, 2000

work page 2000

[8] [7]

J. Dippon. Accelerated randomized stochastic optimization. The Annals of Statistics , 31(4):1260–1281, 2003

work page 2003