{"id":"0949d0c5-8592-4637-a08a-9db36ce48be7","arxiv_id":"2501.11616","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"ZORO-FA is a fully adaptive zeroth-order method that provably finds eps-stationary points in O(s(log n)/eps^2) function evaluations when gradients are sufficiently compressible, and O(n^2/eps^2) otherwise.","lead":"This paper introduces ZORO-FA, a derivative-free optimization method that adaptively selects step size, sampling radius, and sparsity to exploit compressible gradients without knowing the Lipschitz constant or sparsity. It proves worst-case complexity of O(n^2 / eps^2) function evaluations in general, and O(s log n / eps^2) with high probability under additional compressibility conditions, with strong preliminary gains over ZORO.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised O(s log n / eps^2) bound depends on A4, a joint smallness condition on s(theta,p), s0, and L/sigma0 relative to n/(b log n), not implied by p-compressibility alone.","rationale":"The reader's weakest assumption pinpoints A4, and my review independently arrives at the same load-bearing concern: the improved O(s log n / eps^2) guarantee is not a consequence of compressibility (A3) alone. The proof of Lemma 10 and Corollary 3 explicitly uses j* in [1, J-1) to ensure the sensing matrix is still in the low-query regime (m_j < n) when s_j reaches the effective sparsity level. If A4 fails, the algorithm's own safeguard (Step 2.4) takes over, and the theorem provides only the O(n^2/eps^2) bound. This is a genuine limitation on the scope of the headline claim, not an internal inconsistency: the mathematical core is sound under A1-A5. The abstract and conclusion should state the additional smallness condition, or define 'compressible' to include A4. Because the issue is presentational and addressable, the CONDITIONAL verdict is appropriate; I do not recommend changing the reader's verdict. Credit is due for the explicit statement of A4 and Remark 4, which make the limitation visible in the paper itself.","tokens_in":16769,"tokens_out":15570,"duration_ms":156783,"concrete_test":"Fix n=10^4, theta=0.25, b=1, s0=1, sigma0=1, L=1, p=0.9. Compute s(theta,p) from (12), about 8.5e3, while n/(4b ln n) is about 2.7e2; j* = ceil(log2(s/s0)) is about 14 while J-1 is about 10, so A4 fails. Run ZORO-FA on f(x) = (1/2) sum_{j=1}^n j^{-2/p} x_j^2, whose gradient satisfies A3 with L=1, to eps=1e-3, and record function evaluations; check whether they scale as n/eps^2 instead of as s(theta,p) ln n / eps^2. Equivalently, verify analytically that for all j with m_j < n, s_j < s(theta,p), so Corollary 1's sparsity condition is never met on the compressed-sensing path.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 4 and the abstract's 'assuming gradients are compressible' claim require Assumption A4 (Eq. 36), which forces j* = ceil(max{1, log2(s(theta,p)/s0), log2((theta+1)^2/(1-2theta)L/sigma0)}) to lie in [1, J-1), where J = ceil(log2(n/(b s0 ln n))). This is not a consequence of A3. For p close to 1, s(theta,p) from (12) can exceed n/(4b ln n); then the sparsity level at which CoSaMP's guarantee (14) holds is only reached after m_j >= n, so Step 2.1 diverts to forward differences and the compressed bound never applies. Corollary 3's conclusion is genuinely conditional on this smallness; when A4 fails, only the O(n^2/eps^2) safeguard bound of Corollary 2 remains. The abstract's compressibility-only phrasing overstates the scope of the improved complexity result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ZORO-FA, a zeroth-order method for minimizing smooth, possibly nonconvex functions. At each inner iteration the algorithm first attempts a CoSaMP-based gradient estimate from O(s log n) random directional derivatives, and only if the trial step fails to produce a sufficient decrease does it fall back to forward finite differences. The sparsity level, sampling radius, and step size are all adapted. The paper proves a deterministic O(n^2 ε^{-2}) evaluation bound under only Lipschitz-gradient and boundedness assumptions, and a high-probability O(s(θ,p) log n ε^{-2}) bound under additional compressibility and RIP assumptions. Numerical experiments on sparse-gradient test functions and the Moré-Garbow-Hillstrom suite illustrate strong practical performance.","tokens_in":17010,"tokens_out":25759,"duration_ms":265543,"significance":"The main contribution is a genuinely adaptive scheme that does not need to know the Lipschitz constant L or the sparsity level s, together with a clean safeguard argument: if compressed sensing fails, the method switches to forward differences, so the deterministic O(n^2 ε^{-2}) bound always holds. The proofs build on standard, well-cited compressed-sensing results (CoSaMP, RIP) and provide explicit constants. The numerical section is preliminary but suggestive, and the comparisons are reasonably configured. The principal weakness is that the advertised improved complexity is conditional on an additional, easily-violated smallness assumption (A4) that is not indicated in the abstract; the technical results themselves are internally coherent.","major_comments":[{"comment":"The abstract and introduction state that 'assuming the gradients are compressible' the method achieves O(s log n ε^{-2}) evaluations, and the conclusion repeats this claim. This is stronger than what is proved. Theorem 2 and Corollary 3 require Assumption A4, which fixes j* = ceil(max{1, log2(s(θ,p)/s0), log2(((θ+1)^2/(1-2θ)) L/σ0)}) to lie in [1, J-1). A4 is not a consequence of the p-compressibility assumption A3: for fixed θ, L/σ0, and p close to 1, the value s(θ,p) from (12) can exceed n/(2b ln n), in which case j* can reach or exceed J, and Step 2.1 of Algorithm 1 diverts to forward differences at Step 2.4, so only the O(n^2 ε^{-2}) safeguard bound of Corollary 2 remains. Remark 4 acknowledges that A4 is restrictive, but the abstract and main text do not. The improved complexity result should be stated as holding under A4 (with A5 holding with the high probability described in Lemma 3), not under A3 alone.","section":"Abstract, Introduction, Conclusion, Corollaries 3–4, Eq. (36), Remark 4"},{"comment":"Corollary 4 claims that, under A1–A4 and b ≥ c1(0.22664), Algorithm 1 requires O(s(θ,p) ln n ε^{-2}) evaluations with high probability. Its proof says this follows from Corollary 3, but Corollary 3's explicit bound contains factors involving s0 and σ0; it only reduces to (46) under the additional conditions s0 = O(s(θ,p)) and, implicitly, σ0 = O(L) (or if s0 and σ0 are treated as fixed constants hidden in the big-O). If s0 ≫ s(θ,p) or σ0 ≪ L, the per-iteration evaluation count or the step-size bound in Corollary 3 can be much larger than s(θ,p) ln n, and the claimed reduction is not justified. Since the paper emphasizes that the method does not require knowledge of s or L, this qualification should be stated in Corollary 4 and in the abstract.","section":"Corollary 4 and text after Eq. (45)"}],"minor_comments":[{"comment":"There is a typo in the indexing: 'j = i, ..., m' should be 'i = 1, ..., m'.","section":"Lemma 4, display after Eq. (4)"},{"comment":"The displayed inequality Σ_k (j_k+1) ≤ 2 Σ_k j_k is not valid when j_k = 0; the intended bound can be repaired by writing j_k+1 ≤ 2 max{1, j_k} before applying Lemma 8.","section":"Proof of Corollary 2"},{"comment":"The displayed inequality Σ_{j=0}^{j_k} (m_j+2) ≤ 2 Σ b s_j ln n appears to be missing a factor when m_j is small; the final O(·) statement is unaffected, but the proof should be corrected.","section":"Proof of Corollary 3"},{"comment":"The condition 'b ≥ c1(0.22664)' is notationally incomplete because c1(δ) in (2) depends on n/(4s); with s = s_{j*} this ratio should be displayed explicitly, for example b ≥ c1(0.22664; n/(4s_{j*})).","section":"Corollary 4"},{"comment":"The text contains a duplicated sentence: 'For problems of this scale, classical zeroth-order algorithms can struggle...' is immediately followed by 'For problems of moderate to large scale, deterministic zeroth-order algorithms often struggle...', which says essentially the same thing.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the core proof is sound, but the advertised scope of the improved complexity bound is broader than the theorems support. The main fix is to revise the abstract, introduction, and Corollary 4 to make clear that the O(s log n / ε^2) bound requires the additional smallness condition A4 and suitable initial scales s0 and σ0; I do not think the technical approach needs to be reworked."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — read Grapiglia-McKenzie (arXiv:2501.11616). The main deliverable: ZORO-FA, a fully adaptive zeroth-order method that selects sparsity, sampling radius, and step size on the fly, with a forward-difference safeguard. It contributes the first worst-case complexity bounds for fully adaptive ZORO: O(n^2/eps^2) under just smoothness and boundedness, and an improved O(s(theta,p) log n/eps^2) bound under compressibility plus a few extra conditions. The proof structure is coherent, builds on CoSaMP/RIP recovery, and the numerical experiments show meaningful gains over ZORO/adaZORO on sparse-gradient problems. That is a genuine step forward for derivative-free optimization.\n\nThe soft spots are in the framing and one theorem statement. The abstract and conclusion say 'assuming gradients are compressible' gives the improved bound. In fact the improved bound requires Assumption A4, a joint smallness condition on s(theta,p), s0, L/sigma0 relative to n/(b log n). That is not implied by p-compressibility; the authors do state it in Remark 4, but the abstract's compressibility-only wording overstates the scope. There is a second issue with Corollary 4. Even under A4, the clean O(s(theta,p) log n) bound follows only when s0 = O(s(theta,p)) and L/sigma0 = O(s(theta,p)/s0) (up to constants). Otherwise Corollary 3's bound contains factors like (L/sigma0)s0 and s(theta,p)^2/s0. Corollary 4 drops that caveat. Minor: no code is posted for the experiments; and one benchmark, fms, violates A1 (they acknowledge non-differentiability but use it as a stress test). Those are not fatal, but they should be fixed.\n\nOverall my take: the core algorithm and the unconditional O(n^2/eps^2) bound hold up. The improved bound is genuinely conditional, and the paper should be revised to say so in the abstract and to state Corollary 4 correctly. I'd send it to review, and I'd expect a revise-and-resubmit. A reader in derivative-free optimization or high-dimensional black-box methods will find the method and the parameter-adaptation line-search useful.","headline":"Solid adaptive zeroth-order method with real worst-case bounds, but the headline O(s log n / eps^2) guarantee needs Assumption A4 and a sharper Corollary 4.","tokens_in":17507,"tokens_out":9290,"would_cite":false,"duration_ms":88587,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"ZORO-FA is a derivative-free method that selects its own sparsity, sampling radius, and step size, and proves an epsilon-stationary point in O(s log(n)/epsilon^2) evaluations when gradients are compressible, with an O(n^2/epsilon^2)…","keywords":["zeroth-order optimization","derivative-free optimization","compressible gradients","compressed sensing","CoSaMP","adaptive line search","worst-case complexity","sparse gradient estimation"],"falsifier":"Take a smooth function of $n$ variables whose gradient has entries of comparable size (for example, rotate the quadratic $f(x)=\\frac12\\|x\\|^2$ so that no coordinate dominates), so $s(\\theta,p)$ is comparable to $n$ and Assumption A4 fails. Run ZORO-FA and count function evaluations until $\\|\\nabla f(x_k)\\|\\le\\epsilon$; if the count scales like $n^2/\\epsilon^2$ rather than $s\\log(n)/\\epsilon^2$, the compressibility-only reading of the abstract is refuted, and the safeguard is doing the work.","tokens_in":16565,"feed_emoji":"📉","tokens_out":10552,"duration_ms":102951,"temperature":0.7,"pith_summary":"Zeroth-order optimization—minimizing a function using only function values—normally costs $O(n)$ queries per iteration, which is prohibitive when the dimension is large. This paper claims that when the gradient is compressible, meaning most of its mass sits in a few coordinates, a fully adaptive method can reduce that cost to $O(s\\log(n)/\\epsilon^2)$ function evaluations with high probability, without being told the sparsity level $s$ or the Lipschitz constant $L$. The method, ZORO-FA, tries cheap compressed-sensing gradient estimates at increasing sparsity and step-size levels and accepts one only when it delivers a guaranteed function decrease. When the cheap estimate fails, a forward-difference safeguard guarantees progress at $O(n)$ cost per successful step, giving a worst-case $O(n^2/\\epsilon^2)$ bound. A sympathetic reading of the paper is that adaptivity itself is the contribution: all hyperparameters are chosen on the fly, and the complexity guarantees survive that choice.","feed_headline":"Adaptive zero-order method hits O(s log n / ε²) queries","feed_subtitle":"It tunes its own sparsity, radius, and step size; worst-case stays O(n²/ε²).","key_machinery":"The load-bearing object is the acceptance test (25) together with the adaptive gradient estimator. For each inner level $j$ the algorithm forms a Rademacher sensing matrix $Z^{(j)}\\in\\mathbb{R}^{m_j\\times n}$ with $m_j=\\lceil b s_j\\ln n\\rceil$, computes the $m_j$ directional finite differences $y^{(j)}_k$, and solves the sparse linear inverse problem $\\min_{\\|g\\|_0\\le s_j}\\|Z^{(j)}g-y^{(j)}_k\\|_2$ with a fixed number of CoSaMP iterations; the candidate is accepted only if $f(x_k)-f(x_k-g/\\sigma_j)\\ge \\epsilon^2/(2\\sigma_j)$. Two lemmas make this work: the descent lemma (Lemma 6) shows that any gradient estimate satisfying a relative-error bound (15) yields the required decrease once $\\sigma_j$ is large enough, and Corollary 1 shows that compressibility plus the 4s-RIP property supplies exactly that bound. The forward-difference step (Step 2.4) is the safeguard that forces the same decrease with probability one when the compressed estimate fails.","core_discovery":"The paper's central claim is that a single derivative-free algorithm, ZORO-FA, simultaneously achieves the compressed-sensing query rate and a worst-case fallback, with no user-supplied knowledge of $L$ or $s$. Under Assumptions A1–A5, in particular the effective-sparsity condition A4 and the RIP condition A5, Algorithm 1 uses at most $O(s(\\theta,p)\\log(n)/\\epsilon^2)$ function evaluations with high probability to reach an $\\epsilon$-approximate stationary point, where $s(\\theta,p)$ is an effective sparsity level independent of $n$; under only Lipschitz smoothness and boundedness below, it uses at most $O(n^2/\\epsilon^2)$ evaluations. The mechanism is an inner loop over dyadic levels $(s_j,\\sigma_j)$: it measures $m_j=\\lceil b s_j\\ln n\\rceil$ random directional derivatives, runs a fixed number of CoSaMP iterations to obtain an $s_j$-sparse gradient estimate, and accepts the trial point only when the observed decrease is at least $\\epsilon^2/(2\\sigma_j)$; otherwise it doubles $j$ and, once $m_j\\ge n$, switches to forward differences, which certify the decrease. The high-probability part comes from the restricted isometry property of Rademacher sensing matrices, while the fallback part is deterministic.","pith_inferences":["The accept-decrease template is general: any gradient estimator with a similar relative-error guarantee could replace compressed sensing and inherit the same adaptive complexity argument, so the paper is effectively a recipe for certifying adaptive structured zeroth-order methods.","For high-dimensional applications, the operative question is whether gradients are p-compressible with p small enough that $s(\\theta,p)$ is a small fraction of $n$; one could test this directly by sorting the magnitudes of gradient estimates collected by ZORO-FA itself during a run.","The paper notes that on the trig function ZORO-FA accepts smaller sparsity levels despite apparently less compressible gradients; that coupling between the sparsity search and the step-size search suggests a decoupled variant—fix $\\sigma$ while searching $s$, then tighten $\\sigma$—worth testing.","Warm-starting CoSaMP from the previous accepted gradient, rather than from zero at every inner trial, is a natural practical extension that would not change the worst-case bound but could reduce the constant in the query count."],"forward_implications":["On compressible-gradient problems satisfying A4 and A5, ZORO-FA reaches an $\\epsilon$-stationary point in $O(s(\\theta,p)\\log(n)/\\epsilon^2)$ evaluations with probability at least $1-2e^{-\\gamma m_{j^*}}$, with no knowledge of $L$ or $s$.","Without compressibility, the same algorithm still converges at $O(n^2/\\epsilon^2)$ worst-case evaluations, so the adaptivity does not remove the safety net.","Choosing $s_0$ so that $m_0\\approx n/4$ makes the worst-case bound $O(n/\\epsilon^2)$, the same order as a derivative-free quadratic regularization method (Remark 3).","In the reported experiments ZORO-FA beats ZORO and adaZORO on sparse-gradient test problems even when given an underestimate of the true sparsity, because it can shrink its step size and sampling radius while they cannot."],"supporting_citations":[{"why":"introduces the ZORO compressed-sensing gradient estimator and the adaZORO variant that ZORO-FA makes fully adaptive","marker":"[8]"},{"why":"supplies CoSaMP and the RIP-based sparse recovery bounds used to build the gradient approximation","marker":"[26]"},{"why":"provides the CoSaMP iteration error bound (Theorem 5 and Remark 3) used in Lemma 5","marker":"[14]"},{"why":"gives the restricted isometry property for Rademacher matrices, which yields the high-probability guarantee in Corollary 4","marker":"[3]"},{"why":"supplies the line-search acceptance procedure that ZORO-FA adapts and gives the baseline complexity it matches in the non-compressible case","marker":"[16]"}],"fun_headline_variants":["Adaptive zeroth-order method: O(s log n) queries without knowing s","Adaptive derivative-free method: O(s log n) queries when gradients are compressible","Adaptive zero-order method: worst-case O(n²), compressible O(s log n)","Gradient-sparsity-aware zeroth-order method without user-set parameters","Zeroth-order optimizer adapts to gradient sparsity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The advertised fast rate applies only when the gradient has most of its mass in very few coordinates, so that the compressed-sensing estimate succeeds while still using fewer than $n$ queries; if not, the fallback still makes progress but the query count becomes $O(n^2/\\epsilon^2)$.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive zeroth-order method: O(s log n) queries without knowing s","Adaptive derivative-free method: O(s log n) queries when gradients are compressible","Adaptive zero-order method: worst-case O(n²), compressible O(s log n)","Gradient-sparsity-aware zeroth-order method without user-set parameters","Zeroth-order optimizer adapts to gradient sparsity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001133,"raw_usage":{"total_tokens":4734,"prompt_tokens":997,"completion_tokens":3737,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":3636}},"tokens_in":613,"tokens_out":3737,"duration_ms":26357,"temperature":1.0,"reasoning_tokens":3636,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:03:08.591392+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a smooth function of $n$ variables whose gradient has entries of comparable size (for example, rotate the quadratic $f(x)=\\frac12\\|x\\|^2$ so that no coordinate dominates), so $s(\\theta,p)$ is comparable to $n$ and Assumption A4 fails. Run ZORO-FA and count function evaluations until $\\|\\nabla f(x_k)\\|\\le\\epsilon$; if the count scales like $n^2/\\epsilon^2$ rather than $s\\log(n)/\\epsilon^2$, the compressibility-only reading of the abstract is refuted, and the safeguard is doing the work.","supporting_citations":[{"cited_title":"SIAM Journal on Optimization 32, 687–714 (2022)","cited_arxiv_id":null,"evidence_quote":"introduces the ZORO compressed-sensing gradient estimator and the adaZORO variant that ZORO-FA makes fully adaptive"},{"cited_title":"Applied and computational harmonic analysis 26, 301–321 (2009)","cited_arxiv_id":null,"evidence_quote":"supplies CoSaMP and the RIP-based sparse recovery bounds used to build the gradient approximation"},{"cited_title":"Approximation Theory XIII: San Antonio 2010","cited_arxiv_id":null,"evidence_quote":"provides the CoSaMP iteration error bound (Theorem 5 and Remark 3) used in Lemma 5"},{"cited_title":"Constructive approximation 28, 253–263 (2008) ZORO-F A 21","cited_arxiv_id":null,"evidence_quote":"gives the restricted isometry property for Rademacher matrices, which yields the high-probability guarantee in Corollary 4"},{"cited_title":"Optimization Letters 18, 195–213 (2024)","cited_arxiv_id":null,"evidence_quote":"supplies the line-search acceptance procedure that ZORO-FA adapts and gives the baseline complexity it matches in the non-compressible case"}],"review_version":1}