{"id":"4e73a736-1895-4fb7-8149-51645611dade","arxiv_id":"2505.19720","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A benchmark plus a variance bound showing structured orthogonal direction matrices improve gradient estimation and convergence in finite-difference optimization with little extra generation cost.","lead":"Structured, orthogonal search directions for finite-difference optimization can be generated at roughly the same cost as random independent directions, and they often give more accurate gradients and faster convergence. The paper's benchmark of these methods, across synthetic tasks, CUTEst problems, and image attacks, matters because gradient-free optimization is used wherever gradients are unavailable, such as LLM fine-tuning and black-box adversarial attacks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Empirical advantage of structured directions is only demonstrated at the single fixed discretization h=1e-7; the theoretical bound in Lemma 1 is actually more robust than the reader's regularity concern suggests.","rationale":"The reader correctly identified the unstated regularity conditions, but those are not the weakest link: Lemma 1's inequality can be proven by a two-line argument that only needs finite first moments of the finite difference, because the spherical cross-term is a squared norm. The real vulnerability is the empirical comparison's dependence on a single, unusually small h that maximizes the variance term where orthogonality helps. This is addressable by a sensitivity sweep, and it determines whether the abstract's claim about 'significantly improving' holds beyond the tested setting. The incorrect Eq. (9) in Appendix D is a real defect but does not invalidate the inequality, so I would keep the verdict CONDITIONAL rather than reject. The empirical evidence at the default h is extensive and consistent across many benchmarks, so there is no reason to reject; the condition is to verify h-robustness and release code and error bars.","tokens_in":22166,"tokens_out":18331,"duration_ms":192351,"concrete_test":"Rerun the gradient approximation error experiments (Figure 2) and the synthetic convergence experiments (Figure 4) with h in {1e-3, 1e-5, 1e-7, 1e-9}, d=500, ell=d/2, keeping all other parameters fixed. If structured methods no longer consistently outperform unstructured ones for h >= 1e-5, the reported advantage is an artifact of the chosen discretization and the central claim should be qualified as regime-dependent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest_claim is the empirical one: structured directions give comparable generation cost and significantly better gradient accuracy and optimization. The load-bearing theoretical support, Lemma 1, does not depend on the regularity of F as the reader feared: for any F for which E[Z]=E[(F(x+hp)-F(x))p/h] is finite, the i.i.d. spherical cross-terms equal ||E[Z]||^2 >= 0, while the orthogonal cross-terms vanish, so the variance inequality holds without invoking [15, Lemma 1] or the smoothed gradient. What is not load-bearing is the proof's Eq. (9), which is dimensionally inconsistent and overstates the reduction. The genuinely load-bearing assumption is experimental: every gradient-accuracy and convergence result (Figures 2, 4, Appendix C) is computed with h fixed at 1e-7. At such a small h, forward-difference estimates are variance-dominated, and orthogonality's variance reduction gives structured methods a maximal advantage. If h were larger, bias O(h) would dominate and the gap could shrink or reverse. The paper contains no h-sensitivity analysis and no error bars on the aggregated rho curves, so the abstract's 'significantly improving' is conditional on an untested, possibly favorable regime.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a comparative study of structured versus unstructured direction matrices for forward finite-difference gradient estimators in zeroth-order optimization. It reviews known constructions (QR, coordinate, butterfly, Householder) and proposes two extensions: a padded butterfly construction and a permuted Householder variant. The comparison is carried out under a fixed line-search algorithm with identical hyperparameters across methods, measuring direction-generation cost, relative gradient approximation error, and function-value progress on synthetic functions, a subset of CUTEst problems, and an MNIST adversarial-perturbation task. The central claims are that several structured direction schemes can be generated at computational cost comparable to unstructured ones, and that they yield significantly better gradient accuracy and optimization performance, especially when the number of directions is at least d/2. The only theoretical result is Lemma 1 in Appendix D, which asserts that an orthogonal-direction estimator has no larger expected squared error than an i.i.d. spherical-direction estimator.","tokens_in":22384,"tokens_out":9916,"duration_ms":101238,"significance":"If the claims hold, this is a useful benchmark-style contribution to a practically important question: whether orthogonality can be imposed on finite-difference directions without a prohibitive cost. The experimental protocol is fair in several respects that deserve credit: hyperparameters are fixed across methods, the function-evaluation budget is identical, relative error and performance profiles are used, and the paper honestly reports that the plain Householder method underperforms. The proof of Lemma 1 is not circular; it is derived from stated unbiasedness identities and external lemmas. However, the proof contains an algebra error that must be fixed, and the empirical conclusions rest on a single value of the discretization parameter h. Neither defect appears fatal, but both are load-bearing for the paper's main message. With a corrected Appendix D and an h-sensitivity analysis, this would be a solid and useful paper; in its current form the central theoretical and empirical claims are not fully established.","major_comments":[{"comment":"The proof of Lemma 1 contains an algebra error that makes the displayed equations dimensionally inconsistent. For i.i.d. spherical directions, [15, Lemma 1] gives E[(F(x+hp)-F(x))p] = (h/d)∇F_h(x), so the cross-term in Eq. (8) should be ℓ(ℓ−1)(h^2/d^2)||∇F_h||^2, which after the prefactor d^2/(ℓ^2 h^2) contributes (ℓ−1)/ℓ ||∇F_h(x)||^2, not d^2(ℓ−1)/(ℓ h^2)||∇F_h||^2. Eq. (9) must accordingly subtract (ℓ−1)/ℓ ||∇F_h||^2, and the norm in Eq. (9) must be squared. The inequality stated in Lemma 1 is recoverable after this correction because the cross-term is nonnegative, but the proof as printed does not establish the lemma.","section":"Appendix D, Eqs. (8) and (9)"},{"comment":"All experimental claims, including Figures 2, 3, 4, 5, 6 and Appendix C, are computed with a single fixed discretization h_k = 10^{-7}. For smooth objectives the forward-difference bias is O(h), while the relative size of the fluctuation terms changes with h, so the observed gap between structured and unstructured estimators could shrink or reverse at larger h. Since the abstract asserts a general 'significantly improving' effect, the paper needs either an h-sensitivity study on a representative subset of problems or an explicit restriction of the conclusion to the small-h regime. This is the main load-bearing experimental gap.","section":"Section 4 and Appendix A.1 (h_k = 10^{-7})"},{"comment":"The proof invokes the unbiasedness identities [15, Lemma 1] and [36, Lemma 1] without stating the regularity conditions on F under which the identity E[g(x,h,P)] = ∇F_h(x) holds. If F is not sufficiently regular, the cross-term reduction in Eq. (8) is not formally justified. A direct argument using m = E[(F(x+hp)-F(x))p] (when finite) would avoid this issue, or the paper should state the required assumptions explicitly.","section":"Appendix D, Lemma 1"}],"minor_comments":[{"comment":"The aggregated performance profiles ρ_grad(τ) and ρ_val(τ) are shown without error bars or confidence bands, even though the underlying expectations are approximated with a finite number of samples; adding shading or standard errors would make the comparisons easier to assess.","section":"Figures 3 and 5"},{"comment":"The definition O(d) := {G : det G ≠ 0 ∧ G^{-1} = G^T} contains a redundant determinant condition, and the notation 'U(O(d))' for the Haar-uniform distribution is nonstandard; this is a minor notational issue.","section":"Appendix D"},{"comment":"The claim that 'no comprehensive comparison of structured and unstructured strategies has been conducted' should be qualified relative to [1], which already compares several structured and interpolation-based schemes in the regime ℓ ≥ d; otherwise the novelty statement is somewhat overstated.","section":"Section 1"},{"comment":"No code or data repository is referenced. For a benchmark-style empirical paper, releasing the experimental scripts and the list of CUTEst problem instances would substantially improve reproducibility.","section":"Entire manuscript"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope well, but the main theoretical lemma has a fixable algebraic error and the empirical claim is supported only at one value of h. I recommend requesting a revision rather than rejection: the experimental protocol is fair, the claims are mostly appropriately qualified, and the corrections appear straightforward. The heavy reliance on the authors' own prior work is normal for this research line, but the editors may want to check the novelty of the 'tour' contribution against [1]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThis is a genuinely useful benchmark paper, but the headline empirical claim is narrower than the abstract suggests. Every gradient-accuracy and convergence experiment uses h=1e-7; there is no sensitivity analysis, so \"significantly improving\" is demonstrated only in the variance-dominated regime where orthogonality helps most.\n\nWhat is actually new: a unified head-to-head comparison of unstructured and structured direction methods in the ℓ<d regime, which I agree was missing; two small algorithmic extensions (permuted Householder and padded Butterfly) that work as advertised; and a clean Lemma 1 showing orthogonal directions have no larger expected squared error than i.i.d. spherical ones. The variance lemma is correct in substance—Eq. (9) has a typo (missing square on the norm) but the inequality itself does not depend on the regularity of F the way the reader worried; for any F with finite expectations, the i.i.d. cross terms are ||E[Z]||^2 ≥ 0, so the bound goes through without invoking the smoothed gradient. The experimental protocol is fair: same budget, fixed hyperparameters, careful qualification that plain Householder is poor, and an honest limitations appendix.\n\nThe soft spots are real but addressable. First, h=1e-7 is the only discretization tested for all results in Figures 2, 4, and Appendix C. At that scale forward differences are variance-dominated, which is precisely where orthogonality's variance reduction is maximal. A sweep over h (or at least one larger h) would show whether the advantage persists when bias starts to matter. Second, the aggregated ρ curves in Figures 3, 5, and 6 have no error bars; with only 50 trials on synthetic and 100 images on MNIST, some of the gaps could be noise. Third, no code is released, which is a real disincentive for independent replication of a benchmark paper. The heavy self-citation is more defensible: the cited structured methods are the direct competitors and the authors' own prior work is on point.\n\nBottom line: this is a solid, honest, useful paper that deserves a serious referee. I would send it out and ask for an h-sensitivity experiment, error bars on the summary curves, and a code release before acceptance. The core message—structured directions can match unstructured cost and often beat them in the ℓ<d regime—is plausible and well-supported at the tested setting; it just needs to be shown not to be an artifact of one small h.","headline":"Useful benchmark, but the empirical edge of structured directions is only shown at one fixed h; theory holds, experiments need a sensitivity sweep and error bars.","tokens_in":22952,"tokens_out":2002,"would_cite":true,"duration_ms":20822,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that structured, orthogonal random directions dominate independently sampled ones in finite-difference gradient estimation, and that cheap constructions make the advantage practical in high dimensions.","keywords":["zeroth-order optimization","finite-difference methods","structured directions","orthogonal random directions","gradient approximation error","variance reduction","line-search methods","adversarial perturbation"],"falsifier":"Run the comparison of Lemma 1 on a non-smooth objective such as $F(x)=\\sum_i |x_i|^{1/2}$ at a fixed point near zero with small $h$ and $\\ell<d$, and compute the empirical mean squared error over many structured and i.i.d. spherical direction matrices. If the spherical estimator's error is lower than the orthogonal estimator's at any $h$, or if the gap reverses sign as $h$ shrinks, the unbiasedness premise behind Lemma 1 has failed.","tokens_in":21905,"feed_emoji":"🎯","tokens_out":10046,"duration_ms":82705,"temperature":0.7,"pith_summary":"This paper examines whether imposing structure—chiefly orthogonality—on the random directions used by finite-difference gradient estimators is worth the extra effort. It argues that in the practically important regime where the number of directions $\\ell$ is no larger than the dimension $d$, several families of structured direction matrices can be generated about as cheaply as unstructured ones while producing more accurate gradient estimates and faster progress under a fixed budget of function evaluations. The theoretical anchor is a lemma showing that the expected squared gradient approximation error of an orthogonal-direction estimator never exceeds that of the i.i.d. spherical estimator. Experiments on synthetic problems, the CUTEst suite, and adversarial perturbation of an MNIST classifier support the view that orthogonality is a practical upgrade rather than a theoretical nicety.","feed_headline":"Orthogonal search directions beat random ones at same cost","feed_subtitle":"Structured finite-difference matrices cut gradient error and speed up zeroth-order optimization for no extra generation cost.","key_machinery":"The load-bearing object is the finite-difference gradient surrogate $g(x,h,P) = \\frac{d}{\\ell}\\sum_{i=1}^\\ell \\frac{F(x+h p^{(i)})-F(x)}{h} p^{(i)}$, used inside a line-search descent loop in place of $\\nabla F(x)$. The comparison is between direction matrices $P$ whose columns are sampled i.i.d. from the unit sphere and matrices whose columns inherit structure from a random orthogonal matrix, a butterfly transform, a Householder reflector, or a coordinate/permutation draw. The identity that carries the proof is that orthogonal columns make the expansion of $\\|g(x,h,P)\\|^2$ a sum of $\\ell$ diagonal terms: $\\langle G e_i, G e_j\\rangle=0$ for $i\\ne j$, whereas for independent spherical directions the expectation of every cross term is nonnegative and equals, up to constants, $\\|\\nabla F_h(x)\\|^2$, with $\\nabla F_h$ the gradient of the ball-smoothed surrogate $F_h(x)=\\frac{1}{\\mathrm{vol}(B_d)}\\int_{B_d} F(x+h u)\\,du$. Since both estimators are unbiased for $\\nabla F_h(x)$, Lemma 1 reduces the structured-versus-unstructured gap to the removal of those cross terms, and the experiments translate that variance reduction into better line-search behavior and faster convergence.","core_discovery":"The paper's central claim is that structured random directions should be the default choice for finite-difference zeroth-order optimization whenever $\\ell$ is a non-trivial fraction of $d$. Lemma 1 establishes the theoretical core: for every $x$ and $h$, the estimator built from the first $\\ell$ columns of a Haar-distributed random orthogonal matrix has expected squared error no larger than the estimator built from $\\ell$ independent uniform spherical directions, because orthogonality eliminates the $\\ell(\\ell-1)$ positive cross terms that survive in the i.i.d. case. Empirically, at $\\ell \\ge d/3$ the structured methods (QR, butterfly, coordinate, and the proposed permuted Householder variant) consistently give lower relative gradient error than Gaussian, spherical, or Rademacher directions, and at $\\ell \\ge d/2$ they solve more CUTEst problems and more adversarial-perturbation instances within a fixed evaluation budget. Cost measurements show that butterfly, Householder, permuted Householder, and coordinate matrix generation takes time comparable to the unstructured samplers, including at dimension $d=10000$; only QR carries a visibly higher cost. The plain, un-permuted Householder reflector is the structured method that fails for $\\ell<d$, and the paper's fix is to apply it to a random subset of coordinates.","pith_inferences":["The cross-term-removal mechanism suggests that orthogonality is not the only structure that pays: any ensemble of directions with near-zero pairwise inner products, such as tight frames or low-coherence partial orthogonal systems, should reproduce part of the variance reduction; this is a direct extension of Lemma 1's computation rather than a claim in the paper.","The same argument should apply to central-difference estimators, where analogous cross terms involve pairs of evaluations at $x\\pm hp_i$; testing Lemma 1 for that estimator is a natural next step the paper does not take.","The paper's observation that $\\ell=d$ can converge slower than $\\ell=d/2$ under a fixed evaluation budget implies a budget-aware optimal number of directions, a selection rule that could be derived from the variance-versus-iteration trade-off.","The timing and gradient-accuracy results make structured directions a candidate drop-in replacement for Gaussian directions in memory-efficient large-language-model fine-tuning, a setting the paper names as future work but does not test."],"forward_implications":["At $\\ell=d$, structured directions (coordinate, QR, butterfly, Householder, permuted Householder) match or beat unstructured ones on gradient accuracy, so full-rank structure is the safer choice.","For $\\ell\\ge d/2$, replacing i.i.d. random directions by structured ones reaches a fixed target value in fewer function evaluations on the CUTEst problems and solves more adversarial-perturbation instances within 30000 evaluations.","Coordinate directions with $\\ell=d$ need only be generated once and reused, so the cheapest structured option also has the smallest per-iteration overhead.","The permuted Householder construction keeps memory at $O(d\\ell)$ and generation cost at $O(d\\ell)$ while repairing the poor $\\ell<d$ behavior of a single Householder reflector.","Structured methods remain competitive in high dimensions: generation times for butterfly, Householder, permuted Householder, and coordinate matrices are comparable to unstructured sampling up to $d=10000$."],"supporting_citations":[{"why":"Supplies the unbiasedness identity used to identify the i.i.d. cross terms as $\\|\\nabla F_h(x)\\|^2$; the proof of Lemma 1 depends on it for the spherical estimator.","marker":"[15]"},{"why":"Supplies the smoothing/unbiasedness lemma for Haar-orthogonal directions and introduces the butterfly direction construction that the paper extends.","marker":"[36]"},{"why":"Supplies the theorem equating the marginal law of $Ge_i$ with the uniform spherical law, which links the structured and unstructured diagonal terms in Lemma 1.","marker":"[28]"},{"why":"Introduces QR and truncated-permutation structured directions and the rate analysis showing structure does not affect dominant convergence terms.","marker":"[23]"},{"why":"Provides the structured-direction convergence theory and the stepsize dependence on $\\ell$ that explains the multi-direction benefit.","marker":"[37]"},{"why":"Provides the high-probability accuracy condition for line-search convergence and the $\\ell=d$ coordinate/interpolation baseline that the paper extends to $\\ell<d$.","marker":"[1]"},{"why":"Justifies why variance reduction matters: line-search convergence requires the surrogate to be a sufficiently accurate gradient with high probability.","marker":"[4]"},{"why":"Defines random butterfly matrices used as the basis of the butterfly direction generation.","marker":"[43]"}],"fun_headline_variants":["Structured directions cut gradient error at no extra cost","Orthogonal probes beat random ones for zero-order optimization","Structured finite-difference directions: less error, same speed","Orthogonality slashes gradient error in derivative-free optimization","Structured random directions: cheaper and more accurate than i.i.d."],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the objective is regular enough for a random-direction finite difference to be an unbiased estimate of the gradient of a smoothed version of the objective; the paper never states exactly what smoothness or integrability that requires.","fun_headline_variants_meta":{"raw":{"variants":["Structured directions cut gradient error at no extra cost","Orthogonal probes beat random ones for zero-order optimization","Structured finite-difference directions: less error, same speed","Orthogonality slashes gradient error in derivative-free optimization","Structured random directions: cheaper and more accurate than i.i.d."]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000882,"raw_usage":{"total_tokens":3838,"prompt_tokens":998,"completion_tokens":2840,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":2758}},"tokens_in":614,"tokens_out":2840,"duration_ms":20463,"temperature":1.0,"reasoning_tokens":2758,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:07:50.577115+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the comparison of Lemma 1 on a non-smooth objective such as $F(x)=\\sum_i |x_i|^{1/2}$ at a fixed point near zero with small $h$ and $\\ell<d$, and compute the empirical mean squared error over many structured and i.i.d. spherical direction matrices. If the spherical estimator's error is lower than the orthogonal estimator's at any $h$, or if the gap reverses sign as $h$ shrinks, the unbiasedness premise behind Lemma 1 has failed.","supporting_citations":[{"cited_title":"Flaxman, A","cited_arxiv_id":null,"evidence_quote":"Supplies the unbiasedness identity used to identify the i.i.d. cross terms as $\\|\\nabla F_h(x)\\|^2$; the proof of Lemma 1 depends on it for the spherical estimator."},{"cited_title":"Rando, C","cited_arxiv_id":null,"evidence_quote":"Supplies the smoothing/unbiasedness lemma for Haar-orthogonal directions and introduces the butterfly direction construction that the paper extends."},{"cited_title":"Mattila.Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem equating the marginal law of $Ge_i$ with the uniform spherical law, which links the structured and unstructured diagonal terms in Lemma 1."},{"cited_title":"Kozak, C","cited_arxiv_id":null,"evidence_quote":"Introduces QR and truncated-permutation structured directions and the rate analysis showing structure does not affect dominant convergence terms."},{"cited_title":"Rando, C","cited_arxiv_id":null,"evidence_quote":"Provides the structured-direction convergence theory and the stepsize dependence on $\\ell$ that explains the multi-direction benefit."},{"cited_title":"Cartis and K","cited_arxiv_id":null,"evidence_quote":"Justifies why variance reduction matters: line-search convergence requires the surrogate to be a sufficiently accurate gradient with high probability."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines random butterfly matrices used as the basis of the butterfly direction generation."}],"review_version":1}