REVIEW 3 major objections 5 minor 20 references
Ruppert-Polyak averaging for Stochastic Order Oracle
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Averaging the stochastic order oracle iterates yields an asymptotically normal error whose covariance is d/((d−1)²α²)(∇²f(x*))⁻², provably smaller than the base algorithm's at optimal step size.
desk verdict Genuinely nicer covariance for averaged order oracle, but the theorem analyzes an adaptive-γ recursion while the algorithm states a constant γ; conditional until that mismatch is fixed. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the Ruppert–Polyak averaged sequence $\bar{x}_k = \frac{1}{k}\sum_{i=0}^{k-1} x_i$ of the stochastic-order-oracle recursion (2), together with the reduction of that recursion to a normalized stochastic gradient method: by Lemmas 1 and 2, the oracle step $E[\text{sign}\langle\nabla f(x,\xi), e\rangle e]$ equals $\frac{c}{\sqrt{d}}\frac{\nabla f(x,\xi)}{\|\nabla f(x,\xi)\|}$. The proof machinery is the asymptotic-normality theorem for averaged recursions, applied through Lemma 4, which establishes that the expected direction $\psi(x) = E_\xi \varphi(x+\xi)$ is Lipschitz-like near zero with $\psi'(0) = \frac{c}{\sqrt{d}}\alpha(1-\frac{1}{d})I$, and that the noise covariance at zero is $\chi(0) = \frac{c^2}{d^2}I$; plugging these into $V = G^{-1}\chi(0)(G^{-1})^T$ with $G = -\psi'(0)\nabla^2 f(x^*)$ gives the covariance in Theorem 2.
What would settle it
Estimate the empirical covariance of $\sqrt{k}(\bar{x}_k - x^*)$ from many long runs of algorithm (2) on a quadratic objective with known Hessian and truncated isotropic Gaussian noise, first with $\gamma$ set to the adaptive value of Lemma 1 and then with a fixed $\gamma$. If the adaptive version does not approach $d/((d-1)^2\alpha^2)(\nabla^2 f(x^*))^{-2}$, or if the fixed-$\gamma$ version coincidentally matches the formula, the theorem's assumptions and conclusions are not properly aligned. Also compute the smallest eigenvalue of $V(\eta_0) - V$ over a range of condition numbers to test the positive-semidefiniteness claim numerically.
Extended reading notes
Core claim
Under Assumptions 3–4 (µ-strong convexity, L-smoothness, twice differentiability, and spherically symmetric i.i.d. noise), the averaged iterate $\bar{x}_k = \frac{1}{k}\sum_{i=0}^{k-1} x_i$ of algorithm (2) satisfies $\sqrt{k}(\bar{x}_k - x^*) \sim N(0, V)$ with $V = \frac{d}{(d-1)^2 \alpha^2} (\nabla^2 f(x^*))^{-2}$, where $\alpha = E\|\xi\|^{-1}$. This covariance is positive-semidefinite smaller than the base algorithm's covariance $V(\eta_0)$ at the optimal step size (Lemma 5), so averaging both sharpens the asymptotic distribution and removes the unknown constant $c$ from its description. The derivation represents the oracle's expected direction as $\psi(\nabla f(x)) = E_\xi \frac{c}{\sqrt{d}} \frac{\nabla f(x)+\xi}{\|\nabla f(x)+\xi\|}$, applies the asymptotic-normality theorem for averaged stochastic recursions to the resulting normalized stochastic gradient recursion, and verifies the required Lyapunov and noise conditions through Lemma 4.
Load-bearing premise
The covariance formula holds only if the probing radius $\gamma_k$ is chosen adaptively as the length of the noisy gradient divided by $\sqrt{d}L$ (Lemma 1) and the noise is bounded and spherically symmetric; if $\gamma$ is fixed or the noise breaks symmetry, the oracle's expected direction is no longer the normalized stochastic gradient that the derivation relies on.
Editorial extensions
If this is right
- The theorem gives a fully specified asymptotic covariance for the averaged stochastic order oracle, with no dependence on the unknown constant $c$; only $\nabla^2 f(x^*)$ and $\alpha = E\|\xi\|^{-1}$ are needed.
- With the optimal base step $\eta_0 = \frac{d\sqrt{d}}{(d-1)c\alpha\mu}$, the base algorithm's covariance $V(\eta_0)$ is PSD-greater than the averaged covariance, so averaging provides a tighter concentration around $x^*$ in any unitarily invariant norm sense.
- The optimal step-size formula for the base algorithm is explicit and can be estimated in practice from the strong-convexity constant, the noise's inverse moment, and the product $c\alpha$.
- The result indicates that averaging is beneficial not only in the matrix sense but also for practical accuracy: the averaged iterate's distribution narrows as the Hessian grows, compared to the base algorithm's dependence on the Hessian inverse.
- Because the covariance formula is independent of the oracle's constant $c$, the asymptotic behavior of the averaged method is more robust to unknown noise comparisons than the non-averaged version.
Reading between the lines
- If the adaptive probing radius $\gamma_k = \|\nabla f(x_k,\xi_k)\|/(\sqrt{d}L)$ of Lemma 1 is replaced by a fixed $\gamma$, as written in algorithm (2) and used in the experiments, the identity $R(x) = \psi(\nabla f(x))$ in Eq. (11) is not exact; the covariance formula of Theorem 2 may require a correction that depends on $\gamma$—an empirical check would be to sweep $\gamma$ and see how the empir
- The PSD comparison in Lemma 5 says the averaged covariance is smaller at the optimal base step, but the size of the advantage grows with the condition number of $\nabla^2 f(x^*)$; averaging is likely most valuable for poorly conditioned objectives where the base method's error ellipsoid is widest.
- The spherical-symmetry assumption on the noise is used twice: to make the cross terms vanish in $\psi'(0)$ and to force the pure-noise covariance $\chi(0)$ to be a multiple of the identity. Generalizing to non-spherically-symmetric bounded noise would likely replace the scalar $\alpha$ by a matrix, changing the covariance formula.
- The derivation suggests a concrete testable extension to accelerated or momentum variants of the order oracle: if the same averaging machinery applies, the covariance should still be independent of $c$ and depend on the Hessian inverse squared, provided the recursion can be cast in the same normalized-gradient form.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies a stochastic order oracle that returns the sign of a noisy function-value difference, sign[f(x+γe,ξ)-f(x-γe,ξ)] along a random direction e, and applies Ruppert-Polyak averaging to the resulting recursion (2). Its main theoretical claim, Theorem 2, is that under strong convexity, L-smoothness, twice differentiability, and spherically symmetric i.i.d. noise, the averaged iterate satisfies sqrt(k)(x̄_k-x*) → N(0,V) with V = d/((d-1)^2 α^2) ∇²f(x*)^{-2}, which improves on the previously known covariance by replacing the inverse Hessian power and removing the constant c. The paper also claims an optimal step-size formula minimizing any unitarily invariant norm of the earlier covariance matrix, compares the two covariance matrices, and presents histogram-based experiments on a quadratic objective.
Significance. If Theorem 2 were established as stated, the contribution would be meaningful: the covariance depends on the Hessian through the inverse square, the dependence on the unknown constant c disappears, and the comparison in Lemma 5 is a clear quantitative improvement over the earlier order-oracle analysis. The high-level strategy of importing Polyak-Juditsky averaging through Lemmas 1 and 2 is natural and worth pursuing. The paper also has the merit of making a concrete falsifiable prediction about the asymptotic covariance that future experiments can check. However, the central theorem is not proven for the algorithm as stated: the proof relies on an adaptive probing radius that the algorithm does not specify, and Lemma 4 contains a positivity claim that is false under the stated assumptions in some cases. The experimental section is a useful sanity check but cannot validate the main claim because it uses a quadratic objective, for which the finite-difference sign is exact for any γ, and because it calibrates c·α on one setting and reuses it in another.
major comments (3)
- [Section 2.2.3 / Appendix A.2, Eq. (11)] The proof's central reduction R(x_k)=ψ(∇f(x_k)) uses Lemma 1 to replace the oracle output φ(x_k+γe_k,x_k-γe_k,ξ_k)e_k with sign⟨∇f(x_k,ξ_k),e_k⟩e_k. Lemma 1 requires the probing radius to be γ_k=∥∇f(x_k,ξ_k)∥/(√d L), which is an adaptive quantity, whereas Algorithm (2) and Eq. (11) use a fixed γ>0. For fixed γ, the sign of f(x+γe)-f(x-γe) need not equal sign⟨∇f(x),e⟩ when the directional derivative is of order γ, so the recursion analyzed in Appendix A.2 is not the recursion actually run, and the covariance formula (5) may carry an uncontrolled bias. The experiments on a quadratic objective cannot expose this gap because the finite-difference identity is exact for quadratics for every γ. The paper must either specify an adaptive γ_k rule and analyze it, or add conditions on |⟨∇f(x_k),e_k⟩| that make the fixed-γ sign exact up to a controlled error.
- [Section 2.2.2 / Appendix A.3, Lemma 3] Lemma 3 claims the existence of a unique η0 minimizing ∥V(η)∥ for an arbitrary unitarily invariant norm, but the proof in A.3 minimizes only the spectral norm. The displayed function g(η)=η²/(d(ηλ_d-1)) is specific to the spectral norm, and a minimizer of the spectral norm is not in general a minimizer of the Frobenius or nuclear norm. This overstatement is load-bearing because the resulting η0 is used in Setting 2 of the experiments and in the comparison of Lemma 5. The lemma should either be proved for all unitarily invariant norms or explicitly restricted to the spectral norm.
- [Lemma 4, Statement 2 / Appendix A.1.2] The proof of the inequality x^Tψ(x)>0 relies on the assertion that P_β(-1<β<0)>0 for every spherically symmetric distribution. This is false in general: in dimension d=1, if ξ is uniform on {−R,R} and R>∥x∥, then φ(x+ξ)=c sign(x+ξ) has expectation zero for |x|<R, so x^Tψ(x)=0. The Lyapunov condition used in the proof of Theorem 2 is therefore not established under Assumptions 3-4 alone, and the covariance formula (5) is singular for d=1 in any case. The proof needs either a dimension restriction d≥2, an additional condition on the noise distribution (such as absolute continuity or non-vanishing mass near zero), or a direct proof of the positivity inequality under the stated assumptions.
minor comments (5)
- [Section 2.2.1] The notation S_d(r) := {x∈R^d : ∥x| = r} contains a typo; it should be ∥x∥=r.
- [Section 3] The estimate of the product c·α obtained from Setting 1 is used to compute η0 for Setting 2; this is an in-sample calibration, so the comparison between Setting 2 and Setting 3 should be described as a calibration-based experiment rather than as independent validation.
- [Appendix A.1.2] The domination argument for differentiating under the integral uses lower bounds such as ∥z∥³−3ε∥z∥²−ε³, which are not positive for small ∥z∥, so the claimed integrable majorant is not established; the local integrability of the integrand near zero should be handled separately.
- [Theorem 2] The condition α=∫∥z∥^{-1}dP(z)<∞ appears only in the theorem statement and not in Assumptions 3-4; it should be listed as an explicit assumption since it is needed for ψ to be differentiable at zero.
- [Section 3 / Eq. (4)] The averaged iterate is written as x_k in Eq. (4) and as x̄_k in Setting 3 and the conclusion; the notation should be unified throughout.
Circularity Check
Minor in-sample tuning of η0 from Setting 1; central averaging covariance derivation is an independent application of Polyak–Juditsky.
-
fitted input called prediction
[Section 3, Numerical Experiments (paragraph after Setting 3)]
"Note that from the first setting we calculated an estimation of the product c · α, which is used to compute an optimal η0 (see appendix for details)."
Lemma 3 defines η0 = d√d / ((d−1)cαµ), so η0 is a function of the unknown product c·α. The paper estimates c·α from the Setting 1 run of the same algorithm, then plugs this estimate into the formula to set η0 for Setting 2, and presents Setting 2's tighter distribution as empirical support for the optimal-η theory. Thus the optimized parameter is fitted on the same type of data that is then claimed to be improved, so Setting 2 is not an independent confirmation of Lemma 3. The main averaged-sequence claim (Setting 3) does not depend on this fit, so the circularity is limited and non-load-bearing.
full rationale
The central theoretical result (Theorem 2) is not circular: it is derived by verifying the assumptions of the Polyak–Juditsky theorem for the recursion in Eqs. (10)–(14), with Lemma 4 proved in the appendix from the stated smoothness, strong-convexity, and spherical-noise assumptions. The reduction of the order oracle to a normalized stochastic gradient uses Lemma 1 cited from [7] (and ultimately [9]); this lemma is a parameter-free deterministic statement whose assumptions do not include the target covariance, so under the review rules it counts as independent evidence even though [7] shares authors. The only genuine circularity is minor and experimental: c·α is estimated from Setting 1 and then used to choose η0 for Setting 2, making the optimal-η demonstration partly in-sample. Separately, the proof applies Lemma 1 at Eq. (11) with a constant γ, whereas Lemma 1 requires the adaptive probing radius γ_k = ∥∇f(x_k, ξ_k)∥/(√d L); this is a correctness gap between the stated algorithm and the analyzed recursion, not a case of the output being equivalent to the input, so it is not scored as circularity. Overall score 1.
Assumptions & free parameters
free parameters (2)
- c·α product (estimated from Setting 1) =
not reported
- smoothing parameter γ =
not reported
assumptions (7)
- domain assumption f is L-smooth and µ-strongly convex (Assumptions 1-2)
- domain assumption f is twice continuously differentiable with µI ≤ ∇²f ≤ LI and ∇²f(x*) > 0 (Assumption 3)
- domain assumption Noise ξ_k is i.i.d. with spherical symmetry (Assumption 4)
- domain assumption Additive gradient noise ∇f(x,ξ) = ∇f(x) + ξ with bounded ξ (∥ξ∥ ≤ Δ, Δ small)
- domain assumption Lemma 1 from [7]: with γ_k = ∥∇f(x_k,ξ_k)∥/(√d L), the oracle equals sign⟨∇f,e⟩e
- domain assumption Lemma 2 from [9]: E_e[sign⟨∇f,e⟩e] = (c/√d)∇f/∥∇f∥
- standard math Polyak-Juditsky Theorem 2 [8] conditions are satisfied
Cite this review
Pith. "Pith review of Ruppert-Polyak averaging for Stochastic Order Oracle." pith.science (2026). https://pith.science/paper/I4T673OF
@misc{pith2026241115866,
author = {Pith},
title = {Pith review of: Ruppert-Polyak averaging for Stochastic Order Oracle},
year = {2026},
howpublished = {\url{https://pith.science/paper/I4T673OF}},
note = {Machine review of arXiv:2411.15866}
}
read the original abstract
Black-box optimization, a rapidly growing field, faces challenges due to limited knowledge of the objective function's internal mechanisms. One promising approach to address this is the Stochastic Order Oracle Concept. This concept, similar to other Order Oracle Concepts, relies solely on relative comparisons of function values without requiring access to the exact values. This paper presents a novel, improved estimation of the covariance matrix for the asymptotic convergence of the Stochastic Order Oracle Concept. Our work surpasses existing research in this domain by offering a more accurate estimation of asymptotic convergence rate. Finally, numerical experiments validate our theoretical findings, providing strong empirical support for our proposed approach.
Figures
Reference graph
Works this paper leans on
-
[7]
Acceleration exists! optimization problems when oracle can only compare objective function values
Aleksandr Lobanov, Alexander Gasnikov, and Andrei Krasnov. Acceleration exists! optimization problems when oracle can only compare objective function values. arXiv preprint arXiv:2402.09014, 2024
arXiv 2024
-
[9]
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization. In International Conference on Machine Learning, pages 9245–9254. PMLR, 2021
work page 2021
-
[1]
Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15–26, 2017
2017
-
[2]
Practical black-box attacks against machine learning
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pages 506–519, 2017
2017
-
[3]
Introduction to derivative-free optimization
Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization. SIAM, 2009
2009
-
[4]
Derivative-free optimization methods
Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Derivative-free optimization methods. Acta Numerica, 28:287–404, 2019
2019
-
[5]
Zeroth-order optimization meets human feedback: Provable learning via ranking oracles
Zhiwei Tang, Dmitry Rybin, and Tsung-Hui Chang. Zeroth-order optimization meets human feedback: Provable learning via ranking oracles. arXiv preprint arXiv:2303.03751, 2023
arXiv 2023
-
[6]
Training language models to follow instructions with human feedback
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730–27744, 2022
2022
Show all 20 references
-
[8]
Acceleration of stochastic approximation by averaging
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838–855, 1992
1992
-
[10]
Optimal pseudogradient adaptation algorithms
Boris Teodorovich Polyak and Yakov Zalmanovich Tsypkin. Optimal pseudogradient adaptation algorithms. Avtomatika i Telemekhanika, (8):74–84, 1980
1980
-
[11]
Random gradient-free minimization of convex functions
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017
2017
-
[12]
Convex optimization
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004
2004
-
[13]
Lectures on convex optimization, volume 137
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018
2018
-
[14]
Revisiting normalized gradient descent: Fast evasion of saddle points
Ryan Murray, Brian Swenson, and Soummya Kar. Revisiting normalized gradient descent: Fast evasion of saddle points. IEEE Transactions on Automatic Control, 64(11):4818–4824, 2019
2019
-
[15]
Optimal non-asymptotic analysis of the ruppert–polyak averaging stochastic algorithm
Sébastien Gadat and Fabien Panloup. Optimal non-asymptotic analysis of the ruppert–polyak averaging stochastic algorithm. Stochastic Processes and their Applications, 156:312–348, 2023. 7 A Appendix A.1 Proof of Lemma 4 Lemma 4 allows to apply the results from the work of B.T....
2023
-
[16]
ψ(x) = Eξ c√ d x+ξ ∥x+ξ∥ = R c√ d x+z ∥x+z∥ dP (z) is defined
-
[17]
(a) φ(x + z) = c√ d x+z ∥x+z∥ is a Lebesgue-integrable function of z for each x ∈ X
Let’s check that ψ′(x) = R ∇xφ(x + z)dP (z) for all x ∈ X, where X = {x : ∥x∥ < ε}, ε >0, z∈ Ω. (a) φ(x + z) = c√ d x+z ∥x+z∥ is a Lebesgue-integrable function of z for each x ∈ X. (b) For almost all z ∈ Ω the partial derivative ∇xφ(x + z) exists for all x ∈ X as ∂φ(xi + zi) ∂...
-
[18]
From Assumption 4 we get that ψ(0) = Eξ c√ d ξ ∥ξ∥ = 0
-
[19]
Let’s estimate ψ(x) = Eξ x+ξ ∥x+ξ∥: Vector x is a constant here, thus we will consider two components of a random vector ξ = ξ∥ + ξ⊥: ξ∥ ∥ x and ξ⊥ ⊥ x. Having that and from properties of mathematical expectation we can split the mathematical expectation we are looking for: Eξ...
-
[20]
(a) ∇xφ(x + z) = c√ d [ 1 ∥x+z∥ I − (x+z)(x+z)T ∥x+z∥3 ] is a Lebesgue-integrable function of z for each x ∈ X (proved in 2a)
Let’s check that ψ′′(x) = R ∇2 xφ(x + z)dP (z) for all x ∈ X, where X = {x : ∥x∥ < ε}, ε >0, z∈ Ω. (a) ∇xφ(x + z) = c√ d [ 1 ∥x+z∥ I − (x+z)(x+z)T ∥x+z∥3 ] is a Lebesgue-integrable function of z for each x ∈ X (proved in 2a). (b) For almost all z ∈ Ω the partial derivative ∇2 ...
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.