Pith. sign in

REVIEW 2 major objections 5 minor 41 references

Fully Adaptive Zeroth-Order Method for Minimizing Functions with Compressible Gradients

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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)…

desk verdict 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. read the letter →

arxiv 2501.11616 v3 pith:K2OGHJIV submitted 2025-01-20 math.OC

Geovani Nunes Grapiglia , Daniel McKenzie This is my paper · ORCID
classification math.OC MSC 90C5690C30
keywords zeroth-orderoptimizationderivative-freecompressiblegradientscompressedsensingCoSaMPadaptivelinesearchworst-casecomplexitysparsegradientestimation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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)$.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Abstract, Introduction, Conclusion, Corollaries 3–4, Eq. (36), Remark 4] 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.
  2. [Corollary 4 and text after Eq. (45)] 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.
minor comments (5)
  1. [Lemma 4, display after Eq. (4)] There is a typo in the indexing: 'j = i, ..., m' should be 'i = 1, ..., m'.
  2. [Proof of Corollary 2] 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.
  3. [Proof of Corollary 3] 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.
  4. [Corollary 4] 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*})).
  5. [Introduction] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity bounds are derived from external recovery and RIP results plus in-paper descent and counting arguments.

full rationale

The paper's derivation chain is self-contained in the relevant sense. Algorithm 1's guarantees are built from Lemma 4 (Taylor expansion under A1), Lemma 5 (CoSaMP recovery bound citing Foucart's external theorem and Needell-Tropp), Corollary 1, which defines the effective sparsity s(θ,p) directly from those recovery bounds, the descent Lemma 6, the safeguard Lemma 7, and the iteration-counting arguments in Theorems 1-2 and Corollaries 2-4. No parameter is fitted to data and then renamed as a prediction, and no target bound is assumed as an input. The conditional nature of the improved result is explicit: Corollary 4 requires Assumptions A1-A4 plus a RIP event, and Remark 4 states that A4 requires p sufficiently close to zero, i.e., it is not implied by compressibility alone. That is a scope limitation of the advertised O(s log n / eps^2) claim, not a circular step. Self-citations to [8] and [16] situate the algorithm relative to prior ZORO and DFQRM work, but the load-bearing recovery and restricted-isometry statements are external results, and the adaptive line-search analysis is proven in the paper itself. The abstract's compressibility-only phrasing may overstate the scope of the improved complexity bound, but overstatement is not circularity. No equation in the paper reduces by construction to an assumed conclusion.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The method introduces no new physical or mathematical entities. Its parameter count is modest: four user hyperparameters (s0, sigma0, theta, b) plus the accuracy eps. The biggest hidden cost is A4, which bundles several constants into a favorable-regime assumption that is not stated in the abstract.

free parameters (5)
  • s0
    Initial sparsity estimate chosen by user. Appears in Theorems 1 and 2 and in assumption A4. Experiments set s0 = 20 or 0.1n.
  • sigma0
    Initial inverse step size. Doubling via line search approximates 1/L; appears in all complexity bounds and in A4.
  • theta
    Relative gradient approximation error parameter in (0,1/2). Controls s(theta,p), the line-search threshold, and Lemma 6 constants; user chooses 0.25 in experiments.
  • b
    Oversampling factor in m_j = ceil(b s_j log n). Must be at least c1(0.22664) for the high-probability RIP result (Corollary 4); experiments use b = 1, far below that threshold.
  • epsilon
    Target accuracy for approximate stationarity; user-specified as 1e-5 in Section 4.1 and 1e-2 in Section 4.2.
assumptions (6)
  • domain assumption A1: gradient of f is L-Lipschitz continuous
    Used throughout for finite-difference error bounds and the descent lemma (Sections 2.1 and 2.2). Violated by fms in the experiments.
  • domain assumption A2: f is bounded below
    Needed to sum function decreases and bound the iteration count (Theorem 1). Standard.
  • domain assumption A3: gradient of f is p-compressible at every x
    Controls sparse approximation error in Lemma 1 and defines s(theta,p), the target of the improved bound.
  • ad hoc to paper A4: j* defined in (36) lies in [1, J-1)
    Restricts the effective sparsity and initial step so that the compressed-sensing branch is active before the safeguard. Not implied by A3 alone and omitted from the abstract.
  • domain assumption A5: Z^(j*) satisfies 4s-RIP with delta < 0.22665
    Needed for CoSaMP recovery (Lemma 5). Guaranteed with high probability by Lemma 3 if b is large enough, as in Corollary 4.
  • standard math Rademacher matrices satisfy RIP with high probability (Lemma 3)
    Imported from Baraniuk et al.; used to convert A5 into the probabilistic statement of Corollary 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully Adaptive Zeroth-Order Method for Minimizing Functions with Compressible Gradients." pith.science (2026). https://pith.science/paper/K2OGHJIV

@misc{pith2026250111616,
  author       = {Pith},
  title        = {Pith review of: Fully Adaptive Zeroth-Order Method for Minimizing Functions with Compressible Gradients},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K2OGHJIV}},
  note         = {Machine review of arXiv:2501.11616}
}
abstract

We propose an adaptive zeroth-order method for minimizing differentiable functions with $L$-Lipschitz continuous gradients. The method is designed to take advantage of the eventual compressibility of the gradient of the objective function, but it does not require knowledge of the approximate sparsity level $s$ or the Lipschitz constant $L$ of the gradient. We show that the new method performs no more than $O\left(n^{2}\epsilon^{-2}\right)$ function evaluations to find an $\epsilon$-approximate stationary point of an objective function with $n$ variables. Assuming additionally that the gradients of the objective function are compressible, we obtain an improved complexity bound of $O\left(s\log\left(n\right)\epsilon^{-2}\right)$ function evaluations, which holds with high probability. Preliminary numerical results illustrate the efficiency of the proposed method and demonstrate that it can significantly outperform its non-adaptive counterpart.

Figures

Figures reproduced from arXiv: 2501.11616 by the authors.

Figure 1
Figure 1. Left: Typical trajectories on fms. adaZORO fails when it is unable to find a gradient approximation satisfying its acceptance criterion. DS-RS fails when αk fall below 10−6 . Right: Typical trajectories on fN,λ,s. Note the x-axis displays the cumulative number of queries divided by n + 1. number of functions to 36 by toggling the initial point x0 = 10sx˜0, for s ∈ {0, 1} and ˜x0 the default initial point associated … view at source ↗
Figure 2
Figure 2. Data profiles for various tolerances (τ ) and problem dimensions (n). Top Row: n = 100. Middle Row: n = 500. Bottom Row: n = 1000. Left Column: τ = 10−1 . Middle Column: τ = 10−2 . Right Column: τ = 10−3 . In the top row, plots for ZORO and adaZORO are absent as they did not solve any problems to the required tolerance. 4.3 Discussion On functions exhibiting gradient sparsity ZORO-FA outperforms existing bench￾marks… view at source ↗
Figure 3
Figure 3. Top row: Gradient magnitude profiles for two MGH functions: rosex (Left), and trig (Right). The solid line represents the mean (over 20 trials), while the shading represents the minimum and maximum values of gradient component magnitudes observed. Bottom row: The successful sparsity level for ZORO-FA (left axes) as well as the objective function values (right axes) for rosex (Left), and trig (Right). exploit the pre… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 35 canonical work pages

  1. [1]

    Advances in Neural Information Processing Systems 31 (2018)

    Balasubramanian, K., Ghadimi, S.: Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates. Advances in Neural Information Processing Systems 31 (2018)

    work page 2018

  2. [2]

    Mathematical Programming 134, 223–257 (2012)

    Bandeira, A.S., Scheinberg, K., Vicente, L.N.: Computation of sparse low degree inter- polating polynomials and their application to derivative-free optimization. Mathematical Programming 134, 223–257 (2012)

    work page 2012

  3. [3]

    Constructive approximation 28, 253–263 (2008) ZORO-F A 21

    Baraniuk, R., Davenport, M., DeVore, R., Wakin, M.: A simple proof of the restricted isometry property for random matrices. Constructive approximation 28, 253–263 (2008) ZORO-F A 21

    work page 2008

  4. [4]

    SIAM Journal on Optimization 30 (2020)

    Bergou, E.H., Gorbunov, E., Richt´ arik, P.: Stochastic three points method for uncon- strained smooth optimization. SIAM Journal on Optimization 30 (2020)

    work page 2020

  5. [5]

    Journal of Machine Learning Research 1, 281–305 (2012)

    Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. Journal of Machine Learning Research 1, 281–305 (2012)

    work page 2012

  6. [6]

    PMLR, 1193–1203 (2021)

    Cai, H., Lou, Y., McKenzie, D., Yin, W.: A zeroth-order block coordinate descent algo- rithm for huge-scale black-box optimization. PMLR, 1193–1203 (2021)

    work page 2021

  7. [7]

    Applied and Computational Harmonic Analysis 60, 242–266 (2022)

    Cai, H., McKenzie, D., Yin, W., Zhang, Z.: A one-bit, comparison-based gradient estima- tor. Applied and Computational Harmonic Analysis 60, 242–266 (2022)

    work page 2022

  8. [8]

    SIAM Journal on Optimization 32, 687–714 (2022)

    Cai, H., Mckenzie, D., Yin, W., Zhang, Z.: Zeroth-order regularized optimization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Optimization 32, 687–714 (2022)

    work page 2022

Show all 41 references
  1. [9]

    Mathematical Programming 199, 461–524 (2023)

    Cartis, C., Roberts, L.: Scalable subspace methods for derivative-free nonlinear least- squares optimization. Mathematical Programming 199, 461–524 (2023)

    2023

  2. [10]

    Information and Inference: A Journal of the IMA, 11(1), 167-201

    Cartis, C., Otemissov, A.: A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality. Information and Inference: A Journal of the IMA, 11(1), 167-201

  3. [11]

    Mathematical Programming, 198(1), 997-1058

    Cartis, C., Massart, E., Otemissov, A.: Bound-constrained global optimization of func- tions with low effective dimensionality using multiple random embeddings. Mathematical Programming, 198(1), 997-1058

  4. [12]

    arXiv preprint arXiv:2310.02025 (2023)

    Chen, A., Zhang, Y., Jia, J., Diffenderfer, J., Liu, J., Parasyris, K., Zhang, Y., Zhang, Z., Kailkhura, B., Liu, S.: Deepzero: Scaling up zeroth-order optimization for deep model training. arXiv preprint arXiv:2310.02025 (2023)

    2023 arXiv

  5. [13]

    Conference on Robot Learning, 683–696 (2020)

    Choramanski, K, Pacchiano, A., Parker-Harbor, J., Tang, Y., Jain, D., Yang, Y., Iscen, A., Hsu, J., Sindhwani, V.: Provably robust blackbox optimization for reinforcement learning. Conference on Robot Learning, 683–696 (2020)

    2020

  6. [14]

    Approximation Theory XIII: San Antonio 2010

    Foucart, S.: Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants. Approximation Theory XIII: San Antonio 2010. Springer, 2012

    2010

  7. [15]

    Computational Optimization and Applications 85, 683–703 (2023)

    Grapiglia, G.N.: Quadratic regularization methods with finite-difference gradient approx- imations. Computational Optimization and Applications 85, 683–703 (2023)

    2023

  8. [16]

    Optimization Letters 18, 195–213 (2024)

    Grapiglia, G.N.: Worst-case evaluation complexity of a derivative-free quadratic regular- ization method. Optimization Letters 18, 195–213 (2024)

    2024

  9. [17]

    arXiv preprint arXiv:2109.13391 (2021)

    Kim, B., Cai, H., McKenzie, D., Yin, W.: Curvature-aware derivative-free optimization. arXiv preprint arXiv:2109.13391 (2021)

    2021 arXiv

  10. [18]

    Computational Optimization and Appli- cations 79, 339–368 (2021)

    Kozak, D., Becker, S., Doostan, A., Tenorio, L.: A stochastic subspace approach to gradient-free optimization in high dimensions. Computational Optimization and Appli- cations 79, 339–368 (2021)

    2021

  11. [19]

    Mathematical Programming, 199(1), 1179-1219 (2023)

    Kozak, D., Molinari, C., Rosasco, L., Tenorio, L., Villa, S.: Zeroth-order optimization with orthogonal random directions. Mathematical Programming, 199(1), 1179-1219 (2023)

    2023

  12. [20]

    arXiv preprint arXiv:2402.15751 (2024)

    Liu, Y., Zhu, Z., Gong, C., Cheng, M., Hsieh, C-J., You, Y.: Sparse MeZO: Less Pa- rameters for Better Performance in Zeroth-Order LLM Fine-Tuning. arXiv preprint arXiv:2402.15751 (2024)

    2024

  13. [21]

    Advances in Neural Information Processing Systems 36 (2024)

    Malladi, S., Gao, T., Nichani, E., Damian, A., Lee, J.D., Chen, D., Arora, S.: Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems 36 (2024)

    2024

  14. [22]

    Proceedings of the 32nd International Conference on Neural Information Processing Systems, 1805–1814 (2018)

    Mania, H., Guy, A., Recht, B.: Simple random search of static linear policies is competitive for reinforcement learning. Proceedings of the 32nd International Conference on Neural Information Processing Systems, 1805–1814 (2018)

    2018

  15. [23]

    ACM Transactions on Mathematical Software 7, 17–41 (1981)

    Mor´ e, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Transactions on Mathematical Software 7, 17–41 (1981)

    1981

  16. [24]

    SIAM Jour- nal on Optimization 20, 172–191 (2009)

    Mor´ e, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM Jour- nal on Optimization 20, 172–191 (2009)

    2009

  17. [25]

    Applied Stochastic Models in Business and Industry 33, 314–321 (2017)

    Nakamura, N., Seepaul, J., Kadane, J.B., Reeja-Jayan, B.: Design for low-temperature microwave-assisted crystallization of ceramic thin films. Applied Stochastic Models in Business and Industry 33, 314–321 (2017)

    2017

  18. [26]

    Applied and computational harmonic analysis 26, 301–321 (2009)

    Needell, D., Tropp, J.A.: CoSaMP: Iterative signal recovery from incomplete and inaccu- rate samples. Applied and computational harmonic analysis 26, 301–321 (2009)

    2009

  19. [27]

    The Computer Journal 7, 308-313 (1965)

    Nelder, J.A., Mead, R.: A simplex method for function minimization. The Computer Journal 7, 308-313 (1965)

    1965

  20. [28]

    Foundations of Computational Mathematics 17, 527–566 (2017) 22 Geovani N

    Nesterov, Yu., Spokoiny, V.: Random Gradient-Free Minimization of Convex Functions. Foundations of Computational Mathematics 17, 527–566 (2017) 22 Geovani N. Grapiglia, Daniel McKenzie

    2017

  21. [29]

    Nesterov, Yu.: Introductory Lectures on Convex Optimization: A Basic Course. Vol 87. Spring, Berlin (2013)

    2013

  22. [30]

    Large-scale nonlinear optimization, 255–297 (2006)

    Powell, M.J.D.: The NEWUOA software for unconstrained optimization without deriva- tives. Large-scale nonlinear optimization, 255–297 (2006)

    2006

  23. [31]

    SIAM Journal on Optimization 33 (2023)

    Roberts, L., Royer, C.W.: Direct search based on probabilistic descent in reduced spaces. SIAM Journal on Optimization 33 (2023)

    2023

  24. [32]

    arXiv preprint arXiv:1703.03864 (2017)

    Salimans, T., Ho, J., Chen, X., Sidor, S., Sutskever, I.: Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864 (2017)

    2017 arXiv

  25. [33]

    arXiv preprint arXiv:2210.05824 (2022)

    Slavin, I., McKenzie, D.: Adapting zeroth order algorithms for comparison-based opti- mization. arXiv preprint arXiv:2210.05824 (2022)

    2022 arXiv

  26. [34]

    Optimization Methods and Soft- ware 38, 289–311 (2023)

    Shi, H.M., Xuan, M.Q., Oztoprak, F., Nocedal, J.: On the numerical performance of finite- difference-based methods for derivative-free optimization. Optimization Methods and Soft- ware 38, 289–311 (2023)

    2023

  27. [35]

    Tett, S., Gregory, J., Freychet, N., Cartis, C., Mineter, M., Roberts, L.: Calibrating Climate Models-what observations matter? EGU General Assembly Conference Abstracts (2022)

    2022

  28. [36]

    Journal of Artificial Intelligence Research, 55, 361-387

    Wang, Z., Hutter, F., Zoghi, M., Matheson, D., De Feitas, N.: Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55, 361-387

  29. [37]

    PMLR, 1356–1365 (2018)

    Wang, Y., Du, S., Balakrishnan, S., Singh, A.: Stochastic zeroth-order optimization in high dimensions. PMLR, 1356–1365 (2018)

    2018

  30. [38]

    In The Thirty Sixth Annual Conference on Learning Theory

    Yue, P., Yang, L., Fang, C., Lin, Z.: Zeroth-order optimization with weak dimension de- pendency. In The Thirty Sixth Annual Conference on Learning Theory. PMLR, 4429–4472 (2023)

    2023

  31. [39]

    Available at http://www.libprima.net,DOI:10.5281/zenodo.8052654 (2023)

    Zhang, Z.: PRIMA: Reference Implementation for Powell’s Methods with Modernization and Amelioration. Available at http://www.libprima.net,DOI:10.5281/zenodo.8052654 (2023)

    2023 doi

  32. [40]

    arXiv preprint arXiv:2402.11592 (2024)

    Zhang, Y., Li, P., Hong, J., Li, J., Zhang, Y., Zheng, W., Chen, P-Y., Lee, J.D., Yin, W., Hong, M., Wang, Z., Liu, S., Chen, T.: Revisiting Zeroth-Order Optimization for Memory- Efficient LLM Fine-Tuning: A Benchmark. arXiv preprint arXiv:2402.11592 (2024)

    2024 arXiv

  33. [41]

    R. Qiu, H. Tong: Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization. Proceedings of the Forty-first International Conference on Machine Learning (2024) Declarations – Conflict of interest: The authors have no confli...

    2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.