{"id":"62cd83c6-af56-4bd1-98a2-f631dffc57c0","arxiv_id":"2411.15866","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Averaging the iterates of the stochastic order oracle algorithm yields asymptotically normal errors with covariance d/((d-1)^2 α^2) ∇²f(x*)^{-2}, tighter than the non-averaged version.","lead":"By adding Polyak-Ruppert averaging to an algorithm that learns from noisy comparisons of function values, the authors derive a new asymptotic covariance formula that is tighter than the previous one. The result could sharpen convergence predictions for comparison-based and preference-based optimization, such as RLHF.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's proof uses Lemma 1's adaptive probing radius γ_k to equate the oracle output with sign⟨∇f,e⟩, but Algorithm (2) is stated with a constant γ and no rule for setting it; for fixed γ the identity in Eq. (11) fails, so the proven covariance describes a different recursion.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing issue: the proof of Theorem 2 substitutes the order oracle by the normalized stochastic gradient through Lemma 1, whose adaptive γ_k is absent from the algorithm statement. I read the paper in good faith and see no way around this mismatch in the current text; the empirical section is silent on γ and uses a quadratic where the problem disappears. Secondary concerns (the Lemma 3 claim about all unitarily invariant norms, the heuristic passages around c, and sparse experiment details) are real but less central. Because the paper could plausibly be repaired by specifying γ_k or by proving a rigorous bias bound for fixed γ, a conditional verdict remains the right call; my stress-test does not move the reader's verdict.","tokens_in":12274,"tokens_out":10615,"duration_ms":105026,"concrete_test":"Derive E_e[sign(f(x + γe) − f(x − γe))e] for f(x) = 0.5 x^T A x + 0.1 x_1^3 in d = 2 with fixed γ and compare it with c/√d ∇f(x)/∥∇f(x)∥; show the difference is nonzero for γ > 0 (it is of order 0.1γ when ⟨∇f, e⟩ ≈ O(γ)). Then recompute the asymptotic covariance of the resulting biased update and verify whether Eq. (5) changes by more than the Monte-Carlo error in a 10^4-run simulation. If it changes, Algorithm (2) as stated does not satisfy the premise of Theorem 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The asymptotic covariance in Theorem 2 rests on Eq. (11), where the order-oracle output is replaced by sign⟨∇f(x_k, ξ_k), e_k⟩e_k. This replacement is exact only under Lemma 1, which requires γ_k = ∥∇f(x_k, ξ_k)∥/(√d L). Algorithm (2), however, is written with a constant smoothing parameter γ > 0, and Section 2.1 gives no mechanism for choosing γ_k from order-oracle information. With a constant γ, the sign of f(x + γe, ξ) − f(x − γe, ξ) is not exactly sign⟨∇f(x, ξ), e⟩ for a general L-smooth f: the O(γ²) finite-difference error can flip the sign when the directional derivative is of order γ. Consequently R(x) in Eq. (11) is not ψ(∇f(x)), the recursion analyzed in Section A.2 is not the recursion actually run, and the covariance formula (5) may carry an uncontrolled bias or misspecification. The experiments use a quadratic objective, for which the finite-difference sign is exact for any γ, so they cannot expose this gap. This is the weakest load-bearing point: if the algorithm were repaired by prescribing γ_k adaptively, the theorem might hold, but as stated the theorem and the algorithm are mismatched.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12544,"tokens_out":9224,"duration_ms":86397,"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":[{"comment":"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":"Section 2.2.3 / Appendix A.2, Eq. (11)"},{"comment":"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.","section":"Section 2.2.2 / Appendix A.3, Lemma 3"},{"comment":"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.","section":"Lemma 4, Statement 2 / Appendix A.1.2"}],"minor_comments":[{"comment":"The notation S_d(r) := {x∈R^d : ∥x| = r} contains a typo; it should be ∥x∥=r.","section":"Section 2.2.1"},{"comment":"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.","section":"Section 3"},{"comment":"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.","section":"Appendix A.1.2"},{"comment":"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":"Theorem 2"},{"comment":"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.","section":"Section 3 / Eq. (4)"}],"recommendation":"major_revision","confidential_remarks":"The central idea is worth publishing after a substantive revision: the claimed covariance is attractive and the Polyak-Juditsky route is appropriate. The main blocker is the mismatch between the fixed γ in the algorithm and the adaptive γ_k required by Lemma 1, together with the unproven claim for all unitarily invariant norms in Lemma 3 and the false positivity step in Lemma 4 for d=1. These are fixable within the scope of the manuscript, but they are load-bearing and should be addressed before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: the paper derives a genuinely nicer asymptotic covariance for the averaged stochastic order oracle — Hessian^{-2} instead of Hessian^{-1}, and free of the unknown constant c — and the PSD comparison in Lemma 5 is a real improvement, not a restatement. The application of Ruppert-Polyak averaging is a standard template, but the specific computation is new and appears algebraically correct.\n\nThe trouble is load-bearing: the analysis assumes Lemma 1's adaptive probing radius γ_k = ∥∇f(x_k,ξ_k)∥/(√d L), while Algorithm (2) is stated with a constant γ > 0 and no rule for choosing it. The proof of Theorem 2 in Appendix A.2 silently replaces the order-oracle output by sign⟨∇f,e⟩ e, which only holds for that adaptive γ. With constant γ, the finite-difference sign can flip when the directional derivative is O(γ), so the recursion analyzed is not the recursion run. The experiments use quadratics, where the finite-difference identity is exact for any γ, so they cannot expose the gap. This is fixable in principle — state the theorem for the adaptive γ recursion, or give a mechanism to implement γ_k from order-oracle comparisons — but as written the algorithm and the theorem are mismatched.\n\nSmaller issues: Lemma 3 claims an optimal η for any unitarily invariant norm, but the proof only handles the spectral norm. That is an overclaim; either prove it for the general class or narrow the statement. The experiments also estimate c·α from Setting 1 and reuse it to set η0 in Setting 2, which is a mild circularity, and the histograms are qualitative only. The paper leans heavily on lemmas imported from [7] and [9]; that's fine, but a referee should verify Lemma 1's exactness and the martingale conditions from Polyak–Juditsky.\n\nWho this is for: people working on comparison-based / dueling optimization and RLHF-style feedback, who will care about the tighter asymptotic covariance if the gap is closed. It deserves a serious referee, but the revision needs to fix the algorithm specification and the norm claim before the main theorem can be trusted.","headline":"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.","tokens_in":13114,"tokens_out":3174,"would_cite":false,"duration_ms":27564,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","90C15","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Stochastic Order Oracle","Stochastic Optimization","Asymptotic Convergence Analysis","Ruppert-Polyak averaging","Covariance matrix","Strong convexity","Normalized gradient descent","Spherically symmetric noise"],"falsifier":"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.","tokens_in":12068,"feed_emoji":"📉","tokens_out":8226,"duration_ms":66843,"temperature":0.7,"pith_summary":"The paper claims that applying Ruppert–Polyak averaging to a stochastic order oracle—an oracle that only compares noisy function values and returns the sign of the difference—produces an asymptotically normal optimization error with a covariance matrix that is smaller, in the positive-semidefinite sense, than the covariance of the base oracle algorithm even when the base step size is tuned optimally. This matters because order oracles arise in preference-based learning and black-box optimization where exact function values are unavailable; a smaller asymptotic covariance means the averaged iterate concentrates more tightly around the true minimizer for large step counts. The new covariance formula $V = d/((d-1)^2 \\alpha^2) (\\nabla^2 f(x^*))^{-2}$ also drops the unknown constant $c$ that appears in the earlier estimate, so the limiting distribution can be characterized from the Hessian and the noise's inverse moment alone. The claim is established for strongly convex, smooth, twice differentiable objectives with i.i.d. spherically symmetric bounded noise, and it is supported by finite-sample histograms on quadratic problems.","feed_headline":"Averaging shrinks the order-oracle error covariance","feed_subtitle":"The averaged stochastic order oracle provably beats the base algorithm's best covariance on strongly convex problems.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the stochastic order oracle and the base algorithm (2), supplies Lemma 1 linking the oracle output to the sign of the gradient inner product, and provides Theorem 1 whose covariance is the baseline being improved.","marker":"[7]"},{"why":"Supplies the asymptotic-normality theorem for averaged stochastic recursions that Theorem 2 applies to obtain the covariance formula.","marker":"[8]"},{"why":"Provides Lemma 2: the expectation of the sign of the inner product with a uniform sphere vector equals the normalized gradient scaled by $c/\\sqrt{d}$.","marker":"[9]"},{"why":"Establishes the normalized-gradient-descent structure that connects the order oracle algorithm to the asymptotic stochastic approximation theory.","marker":"[10]"},{"why":"Introduces the Ruppert–Polyak averaging procedure as a means to improve the convergence properties of the recursion, the central technique whose effect is analyzed.","marker":"[15]"}],"fun_headline_variants":["Averaging tightens order-oracle covariance to d/(d-1)^2 scaling","Ruppert-Polyak averaging beats base order-oracle covariance","Averaged stochastic order oracle has provably smaller covariance","Order-oracle covariance shrinks via Ruppert-Polyak averaging","Averaging provably improves stochastic order oracle asymptotics"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Averaging tightens order-oracle covariance to d/(d-1)^2 scaling","Ruppert-Polyak averaging beats base order-oracle covariance","Averaged stochastic order oracle has provably smaller covariance","Order-oracle covariance shrinks via Ruppert-Polyak averaging","Averaging provably improves stochastic order oracle asymptotics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000642,"raw_usage":{"total_tokens":2924,"prompt_tokens":889,"completion_tokens":2035,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":505,"completion_tokens_details":{"reasoning_tokens":1942}},"tokens_in":505,"tokens_out":2035,"duration_ms":13286,"temperature":1.0,"reasoning_tokens":1942,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:49:20.930175+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Dueling convex optimization","cited_arxiv_id":null,"evidence_quote":"Provides Lemma 2: the expectation of the sign of the inner product with a uniform sphere vector equals the normalized gradient scaled by $c/\\sqrt{d}$."},{"cited_title":"Optimal pseudogradient adaptation algorithms","cited_arxiv_id":null,"evidence_quote":"Establishes the normalized-gradient-descent structure that connects the order oracle algorithm to the asymptotic stochastic approximation theory."},{"cited_title":"Optimal non-asymptotic analysis of the ruppert–polyak averaging stochastic algorithm","cited_arxiv_id":null,"evidence_quote":"Introduces the Ruppert–Polyak averaging procedure as a means to improve the convergence properties of the recursion, the central technique whose effect is analyzed."}],"review_version":1}