{"id":"68a6319b-c4ce-40eb-8830-e66bfe8bca8d","arxiv_id":"2509.04424","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A state-dependent exploration gain makes single-sample SPSA globally convergent, and zig-zag exploration reduces its asymptotic variance from order 1/epsilon^2 to order epsilon^2.","lead":"This paper proposes a modified single-sample gradient-free optimization algorithm (1SPSA) with a state-dependent exploration step, and proves it converges from any starting point when the objective is smooth and convex enough. It also introduces zig-zag exploration, which sharply reduces the variance of the estimate compared with standard random exploration.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 2.2's variance claims rest on unproved covariance-dominance and cross-covariance cancellations; until those are supplied, the advertised rate comparison is not fully established.","rationale":"The reader's verdict is CONDITIONAL, and my read supports keeping it there. The noise-free assumption is a real scope limitation but is explicitly stated in Section 1, so it does not invalidate the theorems as written. The omitted Lemma A.4 is straightforward to verify and is not the main risk. The greater risk is in Prop. 2.2, the paper's headline acceleration claim: the proof's covariance dominance and telescoping steps are asserted rather than demonstrated. I did not find a concrete counterexample, and the claims may well be true after supplying the missing cross-covariance estimates: the bias relation grad Gamma(theta*) = O(epsilon^2), the third-moment assumptions in (A3), and the MA(1) structure of zig-zag exploration all point in the right direction. But because the asymptotic variance rate comparison is the central novelty, the proof gap is load-bearing. The proposed exact/simulation check would settle whether the concern actually lands; if it passes, the paper should be acceptable subject to the noise-free caveat and the supplied details.","tokens_in":10381,"tokens_out":33757,"duration_ms":343428,"concrete_test":"Test Prop. 2.2 on the scalar family Gamma(theta) = a theta^2/2 + c sin(k theta) + d, with parameters chosen so (A2)-(A4) hold, using zig-zag xi_n = W_n - W_{n-1}. Either derive the exact asymptotic covariance Sigma_Delta*_CLT at theta*, or simulate M = 10^4 independent runs of length N = 10^6 for epsilon in {0.01, 0.02, 0.05}. Verify: (a) for zig-zag, N trace(Cov(beta_N^f)) = O(epsilon^2), including the cross-covariance of nu with psi and omega; (b) for i.i.d. exploration, the epsilon^{-2} lower bound holds with a constant independent of epsilon. If the summed cross-covariance involving nu is O(1), part (ii) fails; if negative cross terms cancel the Delta* variance at order epsilon^{-2}, part (i) fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in the proof of Prop. 2.2 (Appendix A.5). For part (i), after decomposing Delta*_n = nu_n + omega_n + psi_n (Lemma A.6), the proof states that 'the term Sigma_nu_CLT dominates' and then stops; it does not show that the cross-covariance terms Sigma_{nu, omega+psi} + Sigma_{omega+psi, nu} cannot cancel the epsilon^{-2} contribution of Sigma_nu_CLT at order epsilon^{-2}. For part (ii), the proof uses only 'telescoping sequences have zero asymptotic covariance' to drop nu and its cross terms. This is not sufficient by itself: with xi_n = W_n - W_{n-1}, nu_n is of order epsilon^{-1} while psi_n contains epsilon xi_n^3 plus O(epsilon^2), so E[nu_n psi_n^T] is O(1); cross terms at lags +/-1 with omega are only O(epsilon) because grad Gamma(theta*) = O(epsilon^2) by (10b)-(11), but the proof never verifies that the summed cross-covariances vanish or are O(epsilon^2). No counterexample is presented here, but this is exactly where the advertised i.i.d. 1/epsilon^2 lower bound and zig-zag epsilon^2 upper bound live. The companion omission of Lemma A.4's DV3 verification, explicitly left to the reader, is less serious but belongs to the same chain of imported assumptions from [5, Thm. 4/5].","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10761,"tokens_out":9190,"duration_ms":79271,"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":[{"comment":"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.","section":"A.5, proof of Prop. 2.2(ii)"},{"comment":"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.","section":"A.5, proof of Prop. 2.2(i)"},{"comment":"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":"A.3, Lemma A.4"},{"comment":"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.","section":"Section 1, noise-free assumption"}],"minor_comments":[{"comment":"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'.","section":"Proposition 2.1"},{"comment":"The notation θ_PR_N is used without definition; please define the Polyak-Ruppert averaged iterate before invoking it.","section":"Lemma A.5"},{"comment":"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":"Section 3"},{"comment":"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.","section":"Section 1 and Figure 1"},{"comment":"The name 'Keifer and Wolfowitz' should be spelled 'Kiefer and Wolfowitz'.","section":"Literature Review"},{"comment":"There is a typo: 'Lipshcitz' should be 'Lipschitz'.","section":"Appendix A.2"},{"comment":"Reference [5] is cited as a preprint; the version published in Annals of Applied Probability 35(2) should be used.","section":"References"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nWhere 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.\n\nThe 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.\n\nThe numerics are simple but consistent; no code or data, which is fine for a theory paper.\n\nWho 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.","headline":"A credible convergence theorem for 1SPSA with state-dependent gain, but the headline variance acceleration claim rests on an unproved covariance dominance step.","tokens_in":11279,"tokens_out":2932,"would_cite":true,"duration_ms":25712,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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$.","keywords":["simultaneous perturbation stochastic approximation","1SPSA","zeroth-order optimization","state-dependent exploration gain","zig-zag exploration","global convergence","variance reduction","stochastic approximation"],"falsifier":"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.","tokens_in":10169,"feed_emoji":"📉","tokens_out":10953,"duration_ms":91020,"temperature":0.7,"pith_summary":"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.","feed_headline":"Zig-zag sampling cuts single-shot SPSA variance from 1/ε² to ε²","feed_subtitle":"A state-dependent probing step also gives the algorithm convergence from any starting point, with bias only O(ε²).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduces the 1SPSA recursion and the i.i.d. symmetric-exploration framework whose boundedness assumption the paper relaxes.","marker":"[24]"},{"why":"supplies the ODE-method theorem that converts mean-flow stability plus geometric ergodicity into convergence and asymptotic covariance limits.","marker":"[5]"},{"why":"provides the perturbation result used to show exponential stability of the mean flow for small epsilon-bullet.","marker":"[11]"},{"why":"gives the Markov-chain small-set and uniform ergodicity definitions used in verifying the drift condition for exploration.","marker":"[18]"},{"why":"introduces state-dependent exploration gain in a related continuous-time setting, the stabilization idea adapted here.","marker":"[15]"},{"why":"supplies the stochastic-approximation stability theory used for boundedness and for transient removal in the experiments.","marker":"[17]"}],"fun_headline_variants":["Zig-zag probes make one-sample SPSA converge globally","State-dependent exploration fixes 1SPSA divergence and cuts variance","From 1/ε² to ε²: telescoping sampling accelerates SPSA","Single-observation SPSA: global convergence via zig-zag step sizes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Zig-zag probes make one-sample SPSA converge globally","State-dependent exploration fixes 1SPSA divergence and cuts variance","From 1/ε² to ε²: telescoping sampling accelerates SPSA","Single-observation SPSA: global convergence via zig-zag step sizes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000256,"raw_usage":{"total_tokens":1598,"prompt_tokens":989,"completion_tokens":609,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":528}},"tokens_in":605,"tokens_out":609,"duration_ms":5844,"temperature":1.0,"reasoning_tokens":528,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:29:40.191553+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the 1SPSA recursion and the i.i.d. symmetric-exploration framework whose boundedness assumption the paper relaxes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the perturbation result used to show exponential stability of the mean flow for small epsilon-bullet."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the Markov-chain small-set and uniform ergodicity definitions used in verifying the drift condition for exploration."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces state-dependent exploration gain in a related continuous-time setting, the stabilization idea adapted here."}],"review_version":2}