{"id":"0ff76bda-2eb7-4d82-8d17-d1e5e4248f77","arxiv_id":"2506.23758","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":5,"one_line_summary":"VR-SZD, a variance-reduced zeroth-order method using orthogonal structured directions, achieves O(d n^{2/3} ε^{-1}) function evaluations for non-convex composite finite-sum problems and linear convergence under the Polyak-Łojasiewicz condition, matching state-of-the-art rates at lower…","lead":"This paper introduces VR-SZD, a new black-box optimization algorithm for minimizing sums of many functions when gradients are unavailable. It combines variance reduction with structured random search directions and proves convergence rates that match the best known methods while using fewer function evaluations per step.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the advertised O(d n^{2/3}/ε) rate is internally consistent, with the caveat that ℓ must be proportional to d and Assumption 1 restricts 'non-smooth' to h, not the f_i.","rationale":"The reader's ACCEPT verdict is well supported. I traced the main proof chain and checked the dimension bookkeeping. Lemma 4 correctly shows unbiasedness with respect to the smoothed function f_β; Lemma 7's bounds have the right d-dependence; Lemma 8's coefficient 6d/(ℓb)L² plus the β² term produces the stated stepsize constraint; and the Lyapunov argument in Theorem 1 telescopes correctly with c_k chosen so that the inner-loop drift term is absorbed. Corollary 1(iii) uses b=n^{2/3}, m=√b, ℓ=d/c, and the resulting total query count n(d+1)T + 2mb(ℓ+1)T with T=O(√d/(√ℓb ε)) simplifies to O(d n^{2/3}/ε). The PL analysis in Theorem 2 also appears internally consistent: the condition γ<2/(μ(2m+1)) guarantees the key bracket is nonnegative, and the recurrence yields linear convergence with the stated complexity. The only reservations are interpretive rather than correctness-threatening. First, the paper's 'non-smooth' language refers to the proximal term h; the component functions f_i must be smooth. This is explicitly stated in Assumption 1 and is common in the literature. Second, the optimal rate demands ℓ proportional to d; using a constant number of directions would introduce an extra √d factor in the function-evaluation complexity. This does not contradict any theorem, but it means the 'ℓ≤d' advantage over coordinate-direction methods is a constant-factor saving in the asymptotic regime, not a reduction in the d-scaling of the per-iteration cost. Given these caveats, I see no reason to change the reader's ACCEPT verdict.","tokens_in":30562,"tokens_out":27087,"duration_ms":284519,"concrete_test":"Independently re-derive the constant in Lemma 8 and then re-run the Corollary 1(iii) query-count accounting for a concrete instance (e.g., d=100, n=1000, c=2, ℓ=50, b=ceil(n^{2/3}), m=ceil(sqrt(b))), verifying that the chosen γ lies below the Theorem 1 threshold and that the total query count matches O(d n^{2/3}/ε). If the constant or threshold is off, the complexity claim would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I could not find a load-bearing flaw in the central claim. The unbiasedness of the structured estimator (Lemma 4), the bias/variance controls (Lemma 7), the direction bound (Lemma 8), and the Lyapunov telescoping in Theorem 1 are internally consistent, and the parameter arithmetic in Corollary 1(iii) yields O(d n^{2/3}/ε) as stated. The weakest assumption is indeed Assumption 1: each f_i must be differentiable with L-Lipschitz gradient; only h may be nonsmooth. This is explicit, standard in the variance-reduced zeroth-order literature, and is not a hidden inconsistency, though it narrows the meaning of 'non-smooth finite-sum minimization' in the abstract. A second caveat is that the advertised rate requires ℓ=ceil(d/c), i.e., ℓ=Θ(d); with bounded ℓ (e.g., ℓ=1) the complexity would degrade by a √d factor. This tempers the 'lower per-iteration costs' framing but does not invalidate the theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes VR-SZD, a variance-reduced zeroth-order proximal algorithm for composite finite-sum minimization of the form min_x f(x)+h(x), where f is an average of differentiable but potentially nonconvex components and h is convex, nonsmooth, and proximable. The algorithm uses forward finite differences along the full coordinate basis to estimate the full gradient at each outer iteration and along a set of ℓ random orthogonal directions to estimate stochastic gradients in inner iterations. The main theoretical results are a nonconvex convergence rate in terms of the gradient mapping with function-evaluation complexity O(d n^{2/3} ε^{-1}) for a specific parameter choice, and a linear convergence rate under a revised Polyak-Łojasiewicz condition. Numerical experiments on LASSO and binary classification compare VR-SZD favorably with existing zeroth-order variance-reduced methods.","tokens_in":30746,"tokens_out":27205,"duration_ms":272321,"significance":"If the advertised rates hold, this is a useful contribution: it extends structured (orthogonal-direction) zeroth-order estimators to variance-reduced proximal finite-sum methods, uses cheaper forward differences than the central-difference estimators in several prior works, and matches the best known finite-sum complexity O(d n^{2/3} ε^{-1}) while handling a nonsmooth proximable term h. The proofs are unusually detailed, with explicit constants and parameter choices rather than asymptotic hand-waving, and the algorithm is clearly positioned against the prior work of Ji et al., Kazemi and Wang, Huang et al., and the authors' own structured zeroth-order papers. The numerical study is reasonable and the plots are informative. The main caveat is that the headline complexity requires ℓ=Θ(d), so the 'lower per-iteration cost' framing is weaker than the abstract suggests for bounded ℓ.","major_comments":[{"comment":"The step-size condition printed in Theorem 1 and the step-size chosen in Corollary 1 are not compatible as written. If the second term in the theorem's min is read as sqrt(ℓb)/(sqrt(32(e−1)) d L m), then for d≥2 the corollary's choice γ=sqrt(ℓb)/(10 L m sqrt(d)) exceeds it (for d=2 the ratio is about 1.05), so Corollary 1 cannot be deduced from Theorem 1. If, instead, the denominator is meant to be sqrt(32(e−1)d) L m, the display should say so, because the current rendering is ambiguous. The proof in Appendix D actually uses the condition γ1/2; for α=1 the sum tends to ζ(2)=π²/6≈1.645, which is larger than 4/3. The asymptotic O(1/T) conclusion is still correct, since the partial sums are bounded by ζ(2α), but the explicit constant should be replaced (e.g., by ζ(2α)) or the inequality justified.","section":"Section 3.1, Corollary 1(i)"}],"minor_comments":[{"comment":"The abstract says 'non-smooth finite-sum minimization,' but Assumption 1 requires every component f_i to be differentiable with L-Lipschitz gradient; only h may be nonsmooth. This is explicit in Section 2 and matches the literature, but the terminology should be adjusted to avoid overstating the scope.","section":"Abstract and Section 2"},{"comment":"The claim of 'lower per-iteration costs' should be qualified: matching the O(d n^{2/3} ε^{-1}) complexity requires ℓ=ceil(d/c), i.e., ℓ=Θ(d). With ℓ=1 the displayed complexity becomes O(d^{3/2} n^{2/3} ε^{-1}), which is worse than the coordinate-direction baselines, so the advantage is specifically for the structured ℓ=Θ(d) regime.","section":"Section 3.1, Discussion"},{"comment":"In the proof of Lemma 8, the notation EG^τ_k is used inconsistently with the conditional expectation notation defined at the start of Appendix C; this is cosmetic but makes the proof harder to follow.","section":"Appendix C, Lemma 8 proof"},{"comment":"The displayed equality between the expression with sum η_i² and the closed form with (1−α^{m(τ+1)})/(1−α^m) is not an equality; it should be an inequality. The final bound is still correct, but the line should be fixed.","section":"Appendix D, proof of Corollary 2(i)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is squarely within the journal's scope. The related-work discussion is thorough, and the overlap with the authors' prior structured zeroth-order papers and with Kazemi-Wang is disclosed and discussed in a balanced way. No citation-practice concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid theory paper. The core contribution is real: VR-SZD combines structured orthogonal random directions with proximal SVRG-style variance reduction and forward differences, where prior work used either unstructured directions or all coordinate directions. The proof architecture is standard but complete: smoothing lemma, unbiasedness, approximation-error bounds, Lyapunov argument. I checked the parameter arithmetic in Corollary 1(iii) and it yields O(d n^{2/3} ε^{-1}) as stated. That matches the state of the art while using ℓ ≤ d structured directions per stochastic estimate, and the ℓ=1 special case recovers ZO-PSVRG+. The RPL analysis is a useful add-on, and unlike [24] the paper doesn't need a bounded-gradient-variance assumption.\n\nSoft spots, in order of importance. First, the term 'non-smooth finite-sum minimization' in the abstract is generous: Assumption 1 requires each f_i to be L-smooth, and only h is allowed to be non-smooth. That's standard in this line of work and it's stated explicitly, so it's not a hidden flaw, but readers should know the title/abstract oversells slightly. Second, the advertised rate requires ℓ = Θ(d). If you take ℓ = 1, the complexity picks up a √d factor. So the 'lower per-iteration cost' versus coordinate-direction methods is a constant-factor gain, not an asymptotic one. The paper does not hide this—the complexity formula is explicit—but the discussion leans on it a bit hard. Third, no code is provided, and the experiments, while favorable, are on small-scale problems. That's a minor practical shortcoming.\n\nCitation pattern looks okay; the self-citations to the same group's structured zeroth-order work are appropriate because that is the relevant prior work. No circularity burden. The limitations appendix is honest and matches what I found.\n\nBottom line: the central claims hold up under scrutiny as far as I can tell. I would send this to a serious referee—preferably someone who knows the zeroth-order complexity literature—and expect it to come back with minor revisions. It is not a breakthrough, but it closes a genuine gap and does so cleanly.","headline":"A clean, competent paper that closes a real gap in variance-reduced zeroth-order optimization; the advertised O(d n^{2/3}/ε) rate is internally consistent, with two caveats worth noting.","tokens_in":31298,"tokens_out":2147,"would_cite":true,"duration_ms":23844,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","90C15","90C25","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces VR-SZD, a variance-reduced zeroth-order proximal algorithm that estimates gradients with forward finite differences along $\\ell \\le d$ random orthogonal directions, and proves it matches the best known $O(d n^{2/3}…","keywords":["zeroth-order optimization","finite-difference methods","variance reduction","structured directions","non-convex composite optimization","proximal gradient mapping","Polyak-Łojasiewicz condition","black-box optimization"],"falsifier":"Take a family of non-convex finite sums whose components are $L$-smooth but with gradients that vary rapidly at scale $\\beta$, run VR-SZD with $b=\\lceil n^{2/3}\\rceil$, $m=\\lceil \\sqrt{b}\\rceil$, $\\ell=\\lceil d/c\\rceil$, and record the number of function evaluations needed to drive $\\mathbb{E}\\|G_\\gamma(x)\\|^2$ below a fixed $\\varepsilon$; if the scaling in $n$ is worse than $n^{2/3}$, or an extra $\\varepsilon^{-2}$ factor appears, the central complexity claim is wrong.","tokens_in":30337,"feed_emoji":"📉","tokens_out":10901,"duration_ms":109464,"temperature":0.7,"pith_summary":"The paper sets out to show that a gradient-free, variance-reduced proximal method can solve black-box composite finite-sum problems at the same function-evaluation complexity as the best known zeroth-order methods while spending less per iteration. Its algorithm, VR-SZD, combines a full-gradient surrogate built from forward differences along all $d$ coordinate directions with stochastic surrogates built from forward differences along $\\ell \\le d$ random orthogonal directions, and couples them in an SVRG-style outer/inner loop. The main theorems prove that, for non-convex objectives whose components are $L$-smooth and whose nonsmooth part is convex and proximable, the expected squared norm of the proximal gradient mapping decays like $O(1/T)$, and the total function-evaluation complexity reaches $O(d n^{2/3}\\varepsilon^{-1})$ with the parameter choice $b=\\lceil n^{2/3}\\rceil$, $m=\\lceil \\sqrt{b}\\rceil$, $\\ell=\\lceil d/c\\rceil$. The same analysis gives linear convergence under a revised Polyak-Łojasiewicz condition. If correct, this means black-box finite-sum optimization does not pay an extra per-iteration price for using structured directions.","feed_headline":"Gradient-free method hits O(d n^(2/3)/ε) finite-sum complexity","feed_subtitle":"It combines orthogonal directions with SVRG-style variance reduction and costs less per iteration than coordinate baselines.","key_machinery":"The engine is the structured stochastic gradient estimator $\\hat{g}_i(x,G,\\beta) = \\frac{d}{\\ell}\\sum_{j=1}^\\ell \\frac{f_i(x+\\beta G e_j)-f_i(x)}{\\beta} G e_j$, with $G$ uniform on the orthogonal group $O(d)$ and $\\ell \\le d$ directions. Lemma 4 shows that this estimator is unbiased for the gradient of the smoothed function $f_\\beta(x)=\\mathbb{E}_{u\\sim U(\\mathbb{B}^d)}[f(x+\\beta u)]$, which turns a finite-difference direction into a controllable surrogate; Lemma 8 then bounds the variance of the SVRG direction $v^\\tau_k$ by a drift term plus a term proportional to $\\beta_\\tau^2$. The proof is carried by a Lyapunov function $R^\\tau_k = F(x^\\tau_k) + c_k\\|x^\\tau_k - x^\\tau_0\\|^2$ that absorbs the inner-loop drift, and stationarity is measured through the proximal gradient mapping $G_\\gamma(x)=\\gamma^{-1}(x - \\mathrm{prox}_{\\gamma h}(x-\\gamma\\nabla f(x)))$.","core_discovery":"The paper's central claim is that orthogonal structure in the stochastic finite-difference estimator is free: VR-SZD attains a function-evaluation complexity of $O(d n^{2/3}\\varepsilon^{-1})$ for non-convex composite finite-sum minimization, matching the best known zeroth-order finite-sum rates, while using only $\\ell \\le d$ directions per stochastic gradient estimate and forward rather than central differences. Under the revised Polyak-Łojasiewicz condition, Theorem 2 gives $\\mathbb{E}[F(x_0^{\\tau+1})-\\min F] \\le \\alpha^{m(\\tau+1)}[\\mathbb{E}[F(x_0^\\tau)-\\min F] + \\text{(error term)}$, with an overall complexity $O((nd/(\\gamma\\mu m) + b\\ell/(\\gamma\\mu))\\log(1/\\varepsilon))$. These results hold in the composite setting where $h$ is convex and proximable, and they avoid the bounded stochastic-gradient variance assumption used by earlier composite zeroth-order analyses.","pith_inferences":["The paper fixes $\\ell$ and tunes it by grid search, but its own experiments show a budget-dependent optimal number of directions; an adaptive schedule that grows $\\ell$ as outer iterates stabilize is a natural, testable extension.","Because the outer full-gradient surrogate costs $d$ evaluations regardless of $\\ell$, VR-SZD is most attractive when $d$ is moderate enough for the outer pass but too large to pay $d$ directions on every inner step; black-box adversarial perturbation and LLM fine-tuning budgets are the settings to check, which the paper does not run.","Replacing the forward-difference full gradient by a central-difference version would trade $d$ extra outer evaluations for smaller bias constants, and the same Lyapunov machinery should carry through, so a direct comparison of the two discretization choices is a close-by experiment."],"forward_implications":["With $b=\\lceil n^{2/3}\\rceil$, $m=\\lceil \\sqrt{b}\\rceil$, and $\\ell=\\lceil d/c\\rceil$, VR-SZD reaches $\\mathbb{E}\\|G_\\gamma(x)\\|^2 \\le \\varepsilon$ in $O(d n^{2/3}\\varepsilon^{-1})$ function evaluations for non-convex composite finite sums.","Each outer iteration costs $n(d+1)+2mb(\\ell+1)$ function evaluations, so for $\\ell < d$ the per-iteration cost is lower than coordinate-direction variants such as ZO-PSVRG+ with CoordSGE and ZO-PSpider+ with CoordSGE.","Under the revised Polyak-Łojasiewicz condition, choosing a square-summable discretization sequence makes VR-SZD converge exponentially fast to a global minimizer, while a constant discretization gives linear convergence to a neighborhood of size proportional to $\\beta^2$.","The convergence metric is the proximal gradient mapping, so the rates apply to composite problems with a nonsmooth convex and proximable part $h$, not only to smooth objectives.","Choosing $\\ell=1$ recovers the inner iteration of a prior hybrid zeroth-order method as a special case, while using cheaper forward differences in the outer full-gradient surrogate."],"supporting_citations":[{"why":"Supplies the SVRG variance-reduction template that Algorithm 1's outer/inner loop follows.","marker":"[30]"},{"why":"Closest baseline; proves $O(n^{2/3}d/\\varepsilon)$ complexity for composite zeroth-order proximal methods and the hybrid direction idea VR-SZD generalizes and compares against.","marker":"[31]"},{"why":"Establishes the $O(n^{2/3}d/\\varepsilon)$ variance-reduced zeroth-order complexity that VR-SZD matches with structured directions.","marker":"[29]"},{"why":"Proximal variance-reduced zeroth-order methods for composite problems; achieves a similar rate under a bounded stochastic-gradient variance assumption VR-SZD avoids.","marker":"[24]"},{"why":"Structured orthogonal direction estimators and the smoothing analysis used in the unbiasedness lemmas of the paper.","marker":"[54]"},{"why":"Foundational finite-difference smoothing lemma connecting spherical directions to gradients of the smoothed function, used in Proposition 1 and Lemma 4.","marker":"[47]"},{"why":"First-order proximal SVRG non-convex rates that VR-SZD's $O(1/T)$ and Polyak-Łojasiewicz results match in zeroth-order form.","marker":"[57]"}],"fun_headline_variants":["Structured finite-difference directions cut per-iteration cost in zeroth-order method","Variance-reduced zeroth-order meets best finite-sum complexity with orthogonal directions","Proximal gradient-free algorithm for non-smooth sums: orthogonal structure lowers cost","Orthogonal directions in variance-reduced zeroth-order: optimal rates, lower cost","Non-smooth finite-sum without gradients: structured variance reduction achieves best rates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The rates depend on every one of the $n$ component functions being smooth, meaning each has a derivative whose length changes at most proportionally to distance, and on the nonsmooth part $h$ being convex and easy to project onto; if a component is nonsmooth or has unbounded gradient variation, the finite-difference bias and variance bounds in the proof no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Structured finite-difference directions cut per-iteration cost in zeroth-order method","Variance-reduced zeroth-order meets best finite-sum complexity with orthogonal directions","Proximal gradient-free algorithm for non-smooth sums: orthogonal structure lowers cost","Orthogonal directions in variance-reduced zeroth-order: optimal rates, lower cost","Non-smooth finite-sum without gradients: structured variance reduction achieves best rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001148,"raw_usage":{"total_tokens":4762,"prompt_tokens":951,"completion_tokens":3811,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":3708}},"tokens_in":567,"tokens_out":3811,"duration_ms":33553,"temperature":1.0,"reasoning_tokens":3708,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:33:24.488288+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a family of non-convex finite sums whose components are $L$-smooth but with gradients that vary rapidly at scale $\\beta$, run VR-SZD with $b=\\lceil n^{2/3}\\rceil$, $m=\\lceil \\sqrt{b}\\rceil$, $\\ell=\\lceil d/c\\rceil$, and record the number of function evaluations needed to drive $\\mathbb{E}\\|G_\\gamma(x)\\|^2$ below a fixed $\\varepsilon$; if the scaling in $n$ is worse than $n^{2/3}$, or an extra $\\varepsilon^{-2}$ factor appears, the central complexity claim is wrong.","supporting_citations":[{"cited_title":"Johnson and T","cited_arxiv_id":null,"evidence_quote":"Supplies the SVRG variance-reduction template that Algorithm 1's outer/inner loop follows."},{"cited_title":"Kazemi and L","cited_arxiv_id":null,"evidence_quote":"Closest baseline; proves $O(n^{2/3}d/\\varepsilon)$ complexity for composite zeroth-order proximal methods and the hybrid direction idea VR-SZD generalizes and compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the $O(n^{2/3}d/\\varepsilon)$ variance-reduced zeroth-order complexity that VR-SZD matches with structured directions."},{"cited_title":"Huang, B","cited_arxiv_id":null,"evidence_quote":"Proximal variance-reduced zeroth-order methods for composite problems; achieves a similar rate under a bounded stochastic-gradient variance assumption VR-SZD avoids."},{"cited_title":"Rando, C","cited_arxiv_id":null,"evidence_quote":"Structured orthogonal direction estimators and the smoothing analysis used in the unbiasedness lemmas of the paper."},{"cited_title":"Nesterov and V","cited_arxiv_id":null,"evidence_quote":"Foundational finite-difference smoothing lemma connecting spherical directions to gradients of the smoothed function, used in Proposition 1 and Lemma 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"First-order proximal SVRG non-convex rates that VR-SZD's $O(1/T)$ and Polyak-Łojasiewicz results match in zeroth-order form."}],"review_version":1}