Subspace-based Approximate Hessian Method for Zeroth-Order Optimization

Dongyoon Kim; Kwang In Kim; Sungjae Lee; Wonjin Lee

REVIEW 5 major objections 4 minor 55 references

Subspace-based Approximate Hessian Method for Zeroth-Order Optimization

T0 review · 5 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Fitting a quadratic in random two-dimensional subspaces and reusing function evaluations makes curvature-aware zeroth-order optimization converge faster while keeping query costs low.

desk verdict Useful empirical paper on query-efficient zeroth-order optimization, but the convergence proof covers a different algorithm than the one implemented, and the closest prior work is never compared. read the letter →

arxiv 2507.06125 v1 pith:J4I466QO submitted 2025-07-08 cs.LG cs.AI

Dongyoon Kim , Sungjae Lee , Wonjin Lee , Kwang In Kim This is my paper · ORCID

classification cs.LGcs.AI MSC 90C5390C5665K05

keywords zeroth-orderoptimizationHessianestimationsubspacemethodsquadraticmodelfittingfunction-queryefficiencyblack-boxderivative-freedeepneuralnetworktraining

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

The paper presents ZO-SAH, a zeroth-order (gradient-free) optimization algorithm that tries to obtain the acceleration of second-order methods without paying their function-query cost. Its strategy is to restrict attention to random two-dimensional subspaces, fit a quadratic polynomial to the objective inside each subspace, and use the fitted curvature to scale the search direction like Newton's method would. A periodic subspace-switching rule recycles the function evaluations from the two previous steps, so most iterations add no extra queries beyond gradient estimation. The paper claims this yields linear convergence under strong convexity and, on eight datasets ranging from logistic regression to ResNet training, reaches given loss levels with substantially fewer function evaluations than existing zeroth-order baselines. The contribution matters because in black-box settings each function call can be the bottleneck, so a curvature-aware method with near-constant per-step query cost could make second-order behavior practical.

What carries the argument

The load-bearing mechanism is a random two-dimensional subspace quadratic fit combined with a caching schedule. The algorithm partitions an m-dimensional intermediate subspace into m/2 disjoint coordinate pairs; in each pair it estimates the gradient by finite differences and the Hessian by least-squares fitting a quadratic to four points Θk={θk−2,1,θk−2,2,θk−1,1,θk−1,2}, which are the evaluation points from the two previous updates. The fitted Hessian is symmetrized into a positive definite matrix by taking absolute values of its eigenvalues and clipping them at κ=0.1, guaranteeing that the accumulated update vk=∑jPj−1((H^jk)−1g^jk) is a descent direction. The convergence proof hangs on the bound ‖H^−H‖2≤6s/γ(C1εkl3/2+C2l5/6), which requires the recycled points to stay within distance l of the current iterate so the quadratic is a local model.

What would settle it

Take a strongly convex quadratic such as f(x)=‖x‖2 in dimension d=10, run ZO-SAH from a starting point far from the origin, and at every iteration record the distance from the current point to the four reused evaluation points and the spectral error ‖H^−∇2f‖; if after a large Armijo step the distance exceeds the l assumed in the appendix and the error violates the bound in Eq. (33), then the locality assumption that carries Proposition 1 is false.

Watch

Extended reading notes

Core claim

The central claim is that a useful Hessian approximation can be built in a two-dimensional coordinate subspace by least-squares fitting a quadratic model to four function evaluations, and that the resulting estimate is accurate enough to accelerate zeroth-order optimization when the same subspace is kept for T steps and evaluations are reused. Concretely, the paper estimates the subspace gradient by coordinate-wise finite differences and the subspace Hessian as the coefficient matrix A of p(θ)=12θ⊤Aθ+b⊤θ+c, obtained by solving the 3×3 normal equations Φ⊤Φh∗=Φ⊤q with φ(θ)=[12θ12,θ1θ2,12θ22]⊤; it then makes A positive definite by taking absolute eigenvalues with a lower clip κ=0.1. The proof of Proposition 1 states that for a μ-strongly convex function with Lipschitz gradient and Hessian, the expected optimality gap contracts as (1−ν)k with ν=c1ρminμm/(d2(C1+E+κ)2), where E collects the curvature-estimation error. The empirical claim is that this scheme converges faster in cumulative function evaluations than first-order zeroth-order methods, the diagonal-Hessian HiZOO, and the subspace method DeepZero, including roughly 29–50% fewer queries to match DeepZero's final loss on ResNet tasks.

Load-bearing premise

The proof assumes that the four recycled evaluation points are all within distance l of the current iterate, so the fitted quadratic is a local model; the algorithm neither enforces nor checks this after a large step.

Editorial extensions

If this is right

If the central claim is correct, curvature-aware zeroth-order optimization no longer needs a full Hessian or O(d2) finite differences; a two-dimensional quadratic fit at constant query cost can deliver speedups on anisotropic objectives.
For deep-network training, the results imply a black-box optimizer can match DeepZero's final loss with roughly half (CIFAR10/ResNet8) to about a third (CIFAR100/ResNet20) of the function evaluations, making derivative-free training of small residual networks more practical.
The linear rate in Proposition 1 predicts that the iteration complexity scales as d2/(μm) times a curvature-error factor, so raising the subspace dimension m or reducing the recycled-point distance l directly accelerates convergence.
The comparison with diagonal-only Hessian estimates implies that capturing off-diagonal curvature in a small subspace is what buys the speedup; a fully diagonal method will lag on rotated anisotropic problems even if it sees all coordinates.

Reading between the lines

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

The paper does not enforce its own locality assumption; a natural extension is to track the distance to the four recycled evaluation points and refresh them when the current iterate has moved far, which would make the proven rate actually apply without changing the query budget much.
Because the model fit uses only four points constrained to a coordinate pair, the method should excel when the objective's Hessian is dominated by pairwise interactions, and the paper's own condition-number analysis (3.93 on GISETTE vs 15.23 on Olivetti) suggests a testable prediction: the gain over first-order baselines grows with anisotropy.
The quadratic-fit idea could be extended to estimate the gradient from the same model rather than by finite differences; the paper's ablation finds the hybrid design better, but a fully model-based version might win in settings where evaluations are noisy and differencing amplifies noise.
The period T controls a trade-off between evaluation reuse and adapting to a changing landscape; the sensitivity table suggests an adaptive schedule that shortens T when the estimated curvature changes rapidly could outperform the fixed T=20 used in the paper.

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.

Desk Editor's Note

read the letter

Brief: I read the ZO-SAH paper. The algorithmic idea is genuinely interesting: estimate a 2-D subspace Hessian by quadratic least-squares fitting and reuse function evaluations across a fixed subspace block. That reuse mechanism is the main query saver, and the experiments support it. The paper reports faster convergence than several strong baselines on six logistic regression datasets and two ResNet/CIFAR tasks, with ablations on the switching period and on diagonal vs. full Hessian. The comparisons look fair, and the baseline settings are taken from the original papers. This is a solid empirical contribution.

The soft spot is the theory. Proposition 1 gives a linear rate under strong convexity and Armijo line search, but the proof (Appendix A.2) takes expectation over a fresh random projection matrix P at every step. Algorithm 1 fixes V (and the pairings) for T steps, T=20 in the experiments, precisely to enable reuse. Once V is fixed, the update only moves in V; the gradient components orthogonal to V are untouched, so ||v_k|| can be tiny while the full gradient norm is large. The inequality (22) that lower-bounds ||v_k|| in terms of ||∇f(x_k)|| has no reason to hold under fixed V. The telescoping argument therefore proves convergence for the T=1 version, not for the implemented reuse mechanism. That is a structural gap, not a cosmetic one.

There are two smaller issues. First, the rate constant ν differs by a factor of two between the main text (Eq. 18) and the appendix statement (Eq. 27); the proof (Eq. 77) matches the main text, so the appendix is wrong. Second, Assumption 4 requires reused evaluation points to lie within distance l of the current iterate, but the algorithm never enforces or checks this; after a large step, the reused points can be far away, and the Hessian estimate becomes biased. This is secondary, but it should be addressed.

Also, the closest prior work, Berglund et al. 2022, is cited only inside a proof and never compared or discussed. That is a citation-practices problem, not a technical one.

My verdict: the paper deserves peer review, because the empirical mechanism is useful and the experiments are careful. But the theory as written does not cover the main algorithm. A referee should require the authors to either analyze the fixed-subspace reuse directly (e.g., blockwise analysis) or clearly present the rate as applying to the per-step random-subspace variant and give a heuristic argument for reuse. The ν inconsistency and the [5] comparison also need fixing.

Referee Report

5 major / 4 minor

Summary. The paper proposes ZO-SAH, a zeroth-order optimizer that at each block fixes a random coordinate subspace V, decomposes it into two-dimensional subspaces, fits a quadratic model in each 2D subspace to estimate a projected Hessian, and reuses function evaluations from the previous two steps within the block. It reports faster convergence in terms of function evaluations than RSPG, ZO-signSGD, ZO-AdaMM, ReLIZO, GraCe, HiZOO, and DeepZero on six logistic-regression datasets and on CIFAR-10/CIFAR-100 with ResNet8/ResNet20, and it provides a convergence theorem (Proposition 1) claiming a linear rate for strongly convex functions under Armijo line search.

Significance. If the theorem and experiments are correct, ZO-SAH would be a useful query-efficient curvature-aware zeroth-order method with a simple per-step O(1) query cost and an effective evaluation-reuse mechanism. The empirical evaluation is broad (eight datasets, seven baselines), the ablations isolate the role of off-diagonal Hessian terms and the switching period T, and the experimental settings are described in reasonable detail. However, the convergence theorem as written does not cover the implemented algorithm: the proof assumes fresh random subspaces at every step while Algorithm 1 fixes V for T steps to enable reuse, and the key lower bound in the proof is derived from an invalid pathwise use of an expectation inequality. These issues are load-bearing for the paper's theoretical claim, though they do not by themselves undermine the empirical comparison.

major comments (5)

[Sec. 4.3 and Appendix A.2 (Eqs. 22, 66-72)] The convergence proof does not cover the algorithm as implemented. Algorithm 1 fixes the subspace V for T steps (lines 5-12; T=20 in Sec. 5.3) precisely to reuse the evaluation points of Eq. (15), but the proof of Proposition 1 takes an expectation over freshly drawn projection matrices P at every step (Appendix A.2, 'we take the expectation with respect to the projection matrices P'). Once V is fixed, the update v_k touches only coordinates in V, so ||v_k|| can be arbitrarily small relative to ||grad f(x_k)|| even when the full gradient is large; the pathwise lower bound in Eq. (22) and the telescoping inequality in Eq. (72) therefore do not hold for the implemented ZO-SAH. The theorem as stated is for a different algorithm, namely one with fresh random subspaces per step and no evaluation reuse, and the central query-saving mechanism is left without theoretical support.
[Appendix A.2, Eqs. (66)-(68)] The derivation of the key lower bound is invalid. Eq. (66) is an expectation bound on ||P^T bg - grad f(x_k)||; from it one cannot conclude the pathwise inequality ||P^T bg|| >= (1-tau_k) ||grad f(x_k)|| that Eq. (67) and hence Eq. (68) require. The notation switches between g and P^T bg in Eqs. (66)-(68), and the displayed 'triangular inequality' does not follow from the preceding expectation bound. Since Eq. (72) is the basis for the linear rate, this step needs to be repaired or replaced with a valid per-step lower bound.
[Eqs. (18), (27), (77)] The rate constant nu is stated inconsistently: Eq. (18) gives nu = c1 rho_min mu m / (d^2 (C1 + E + kappa)^2), Eq. (27) in the appendix gives nu = c1 rho_min 2 mu m / (d^2 (C1 + E + kappa)^2), and the proof at Eq. (77) yields nu = c1 rho_min m mu / (d^2 (C1 + E + kappa)^2). These three expressions cannot all be correct; the appendix's Proposition 2 should be reconciled with the main-text Proposition 1 before the theorem can be evaluated.
[Sec. 4.3 / Appendix A, Assumption 4 and Eq. (15)] The locality assumption on the reused evaluation points is not enforced. Assumption 4 bounds the distance between theta_k and every element of Theta_k by l, but Algorithm 1 reuses Theta_k = {theta_{k-2}, theta_{k-1}} (Eq. (15)) without checking whether those points are within l of the current iterate. After a large accepted Armijo step the previous iterates can be far away, so the quadratic fit is not a local model and Corollary A.2 (Eq. (33)) does not apply; alternatively, if l is taken to be the actual distance, the constant E in Eq. (19) may grow without bound and the rate becomes vacuous. The proof needs an explicit mechanism or assumption that keeps reused points local.
[Sec. 4.2 and Appendix A.2 (eigenvalue clipping)] The description of eigenvalue clipping is contradictory: Sec. 4.2 replaces lambda_i with max(lambda_i, kappa), while Appendix A.2 states min(lambda_i, kappa). Positive definiteness of the estimated Hessian and the inverse bound in Eq. (61) depend on which operation is actually used. In addition, Eq. (51) of Corollary A.2 displays an equality that is not valid for varying Delta q_i; the bound can be obtained correctly via Cauchy-Schwarz, but the displayed step should be fixed.

minor comments (4)

[Appendix A.1, Eqs. (37) and (40)] The linear term in the definition of q(theta_i) is written as bg^T theta in the display after Eq. (40), but it should be bg^T theta_i to match Eq. (37) and the subsequent derivation.
[Appendix A.1, Eq. (41)] The term 'P Hf(theta) g^T theta_i' appears to contain a typo; it should be the gradient term grad f(x_k)^T P^T theta_i, matching the simplification in Eq. (42).
[Sec. 5.3] The text reports that ZO-SAH reaches DeepZero's final loss with approximately 50% and 29% fewer function queries, but the total query counts are not stated; please add the query counts or mark the crossing points on the convergence curves.
[References] Reference [26] is missing the title 'A primer on zeroth-order optimization in signal processing and machine learning: Principles, recent advances, and applications', and several other bibliography entries have minor formatting inconsistencies.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence theorem is derived from stated assumptions and problem constants, not from the benchmark results or from the authors' own prior work.

full rationale

Walking the derivation chain, Proposition 1 (Eqs. 17-18) states a linear rate whose contraction factor depends only on problem constants (strong convexity mu, Lipschitz constants C1 and C2, dimension d, subspace dimension m), line-search constants, and the local-model quantities l, gamma, and s = |Theta_k| = 4. None of these are fitted to the empirical losses reported in the experiments. The evaluation-reuse mechanism enters the analysis only through the fixed number of reused points s and the assumed local radius l; the proof does not take the measured convergence curves as input. The paper contains no load-bearing self-citations by the present authors: citations such as [17], [43], and [50] are external and are used for standard ingredients (random subspace Newton, Armijo backtracking setup, and eigenvalue clipping). The choice T = 20 in Appendix C.2 is a hyperparameter selected from an ablation on the same benchmark tasks, but that is empirical model selection rather than a circular derivation, and the theorem does not depend on T. The most serious weakness, correctly identified by the skeptic, is that the proof takes expectations over fresh projection matrices P in Eqs. (62)-(66), while Algorithm 1 fixes V for T steps to reuse evaluations; this means the theorem may prove convergence for a different algorithm. That is a proof-algorithm mismatch and a correctness risk, not circularity, because the theorem is not equivalent to its conclusions or to the experimental numbers. The appendix also explicitly flags the gamma assumption as non-restrictive; even if that assumption is debatable, it is an ordinary modeling assumption rather than a reduction of the claimed result to its own input. Overall, no step in the paper's derivation chain is circular, so the appropriate finding is no significant circularity with score 0.

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

The central claim rests on a strong-convexity and smoothness setup, a line-search assumption, and several method-specific conditions (bounded γ, local reused points, bounded perturbation) that are not verified in the experiments. The method itself introduces no new physical or ontological entities.

free parameters (5)

subspace switching period T = 20 for neural networks; not stated for logistic regression
Chosen by hand based on ablation (Appendix C.2, Fig. 7, Tab. 3); directly controls evaluation reuse and query efficiency.
eigenvalue clipping threshold κ = 0.1
Fixed positive parameter used to ensure the estimated Hessian is positive definite (Sec. 4.2); appears in the convergence rate denominator.
finite difference step size ϵ = 10^{-3}
Used for gradient estimation in Eq. (7) in all experiments; the proof (Assumption 4) requires an upper bound that is not verified in practice.
subspace dimension m = unspecified in experiments
The dimensionality of the intermediate subspace V; the convergence rate (Eq. 18) scales with m, but the reported value is not given.
line search step parameters = initial 1.0, Armijo c1=10^{-4}, shrinkage 0.5
Applied to all algorithms (Appendix B.4); the proof assumes a minimum step size ρ_min, which is not estimated or reported.

assumptions (5)

domain assumption f is µ-strongly convex, twice continuously differentiable, with C1-Lipschitz gradient and C2-Lipschitz Hessian (Assumptions 1 and 3).
Invoked in Proposition 1 and throughout the proof; strong convexity gives the Polyak-Lojasiewicz inequality used for linear convergence.
domain assumption Armijo backtracking line search with a minimum step size is applied (Assumption 2).
Used to guarantee sufficient decrease f(x_{k+1}) ≤ f(x_k) − c1 ρ_k ||v_k||²; experiments report using line search.
ad hoc to paper The smallest eigenvalue of the design matrix Φ^T Φ is bounded below by γ (Assumption 4).
Specific to the least-squares Hessian fit; the paper argues it is not restrictive because the sampling radius l need not shrink, but no value or validation of γ is given.
ad hoc to paper The function-evaluation points Θ_k reused from previous steps stay within distance l of the current iterate θ_k (Assumption 4, Eq. 15).
The quadratic fit is local only if the reused points are near the current point; the algorithm does not enforce or verify this after large optimization steps.
ad hoc to paper The gradient perturbation bound ϵ_k ≤ sqrt(2)/(d C1) ||∇f(x_k)|| holds (Assumption 4).
The algorithm fixes ϵ = 10^{-3}, which may violate this bound near the optimum where the gradient norm is small; the proof uses this bound for the gradient estimation error.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Subspace-based Approximate Hessian Method for Zeroth-Order Optimization." pith.science (2026). https://pith.science/paper/J4I466QO

@misc{pith2026250706125,
  author       = {Pith},
  title        = {Pith review of: Subspace-based Approximate Hessian Method for Zeroth-Order Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J4I466QO}},
  note         = {Machine review of arXiv:2507.06125}
}

read the original abstract

Zeroth-order optimization addresses problems where gradient information is inaccessible or impractical to compute. While most existing methods rely on first-order approximations, incorporating second-order (curvature) information can, in principle, significantly accelerate convergence. However, the high cost of function evaluations required to estimate Hessian matrices often limits practical applicability. We present the subspace-based approximate Hessian (ZO-SAH) method, a zeroth-order optimization algorithm that mitigates these costs by focusing on randomly selected two-dimensional subspaces. Within each subspace, ZO-SAH estimates the Hessian by fitting a quadratic polynomial to the objective function and extracting its second-order coefficients. To further reduce function-query costs, ZO-SAH employs a periodic subspace-switching strategy that reuses function evaluations across optimization steps. Experiments on eight benchmark datasets, including logistic regression and deep neural network training tasks, demonstrate that ZO-SAH achieves significantly faster convergence than existing zeroth-order methods.

Figures

Figures reproduced from arXiv: 2507.06125 by the authors.

**Figure 1.** Visualization of quadratic models p in Eq. (8) for different matrices A in (a)–(d). (e) a top-down view of (b), illustrating level curves and search directions: steepest descent (orange arrow, orthogonal to the level curves; Eq. (1)) and Newton’s method (green arrow; Eq. (2)) at a hypothetical search point (red circle). The minimizer h∗ ∈ R 3 of Eq. (11) is obtained as the solution of a 3 × 3 linear system: Φ⊤Φh∗ =… view at source ↗

**Figure 2.** Optimization trajectories of ZO-SAH and RSPG on the toy example in Eq. (23). Exploiting second-order information, ZO-SAH achieves significantly faster convergence (201 function calls) than RSPG (7,921 function evaluations). Applying Eq. (20) and Eq. (21) to x k and combining these bounds, we obtain the following lower bound for the update: m 2d 2(C1 + E + κ) 2 ∥∇f(x k )∥ 2 ≤ ∥v k ∥ 2 . (22) Our Hessian estimate Hb i… view at source ↗

**Figure 3.** Progression of average objective function values (y-axis) across eight benchmark datasets. Since each algorithm step requires a [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: Performance of our algorithm and finite-difference Hes [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 5.** Figure 5: Progression of average objective function values (y-axis) across six logistic regression benchmark datasets. Since each algorithm [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]

**Figure 6.** Figure 6: Impact of incorporating off-diagonal Hessian elements: (left) logistic regression and (right) neural network training. [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]

**Figure 7.** Figure 7: Performance of our algorithm with varying subspace switching period [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]

**Figure 8.** Figure 8: Performance of the proposed ZO-SAH algorithm (Ours (Final)) and its variant using polynomial model-based estimation for both the gradient and Hessian (Ours (Pure model-based)). For reference, the convergence curves of other algorithms are also visualized. 20 [PITH_FUL…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 52 canonical work pages

[5]

Zeroth-order randomized subspace Newton methods

Erik Berglund, Sarit Khirirat, and Xiaoyu Wang. Zeroth-order randomized subspace Newton methods. In ICASSP, 2022. 12

work page 2022
[1]

Backpropagation and stochastic gradient descent method

Shunichi Amari. Backpropagation and stochastic gradient descent method. Neurocomputing, 1993. 1

work page 1993
[2]

Tsybakov

Jean-Yves Audibert and Alexandre B. Tsybakov. Fast learn- ing rates for plug-in classifiers. The Annals of Statistics, 2007. 14

work page 2007
[4]

Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg

Albert S. Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. FoCM, 2022. 2

work page 2022
[6]

Stochastic gradient descent tricks

L´eon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade. Springer, 2012. 1

work page 2012
[7]

Picking winning tickets before training by preserving gradient flow

Wang Chaoqi, Zhang Guodong, and Grosse Roger. Picking winning tickets before training by preserving gradient flow. In ICLR, 2020. 17

work page 2020
[8]

DeepZero: Scaling up zeroth-order optimization for deep model training

Aochuan Chen, Yimeng Zhang, Jinghan Jia, James Diffend- erfer, Jiancheng Liu, Konstantinos Parasyris, Yihua Zhang, Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. DeepZero: Scaling up zeroth-order optimization for deep model training. In ICLR, 2024. 2, 7, 8, 17

work page 2024
[9]

ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models

Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho- Jui Hsieh. ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In AISec, 2017. 1

work page 2017

Show all 55 references

[10]

ZO-AdaMM: Zeroth-order adaptive momentum method for black-box optimization

Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. ZO-AdaMM: Zeroth-order adaptive momentum method for black-box optimization. In NeurIPS, 2019. 2, 7, 16, 17

2019
[11]

Improve single-point zeroth- order optimization using high-pass and low-pass filters

Xin Chen, Yujie Tang, and Na Li. Improve single-point zeroth- order optimization using high-pass and low-pass filters. In ICML, 2022. 17

2022
[12]

Adaptive subgra- dient methods for online learning and stochastic optimization

John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgra- dient methods for online learning and stochastic optimization. JMLR, 2011. 1

2011
[13]

Duchi, Michael I

John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex opti- mization: The power of two function evaluations.IEEE Trans. Information Theory, 2015. 1, 3, 16

2015
[14]

Jeffrey A. Fessler. Optimization Algorithms for Data Science. University of Michigan, 2023. 14

2023
[15]

William A. Gardner. Learning characteristics of stochastic- gradient-descent algorithms: A general study, analysis, and critique. Signal Processing, 1984. 1

1984
[16]

Mini- batch stochastic approximation methods for nonconvex stochastic composite optimization

Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini- batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Program- ming, 2016. 2, 6, 16

2016
[17]

Gower, Dmitry Kovalev, Felix Lieder, and Peter Richt´arik

Robert M. Gower, Dmitry Kovalev, Felix Lieder, and Peter Richt´arik. RSN: Randomized subspace Newton. In NeurIPS,
[18]

Isabelle Guyon, Steve Gunn, Asa Ben-Hur, and Gideon Dror. GISETTE. UCI Machine Learning Repository, 2004. 7

2004
[19]

Deep residual learning for image recognition

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sum. Deep residual learning for image recognition. In CVPR, 2015. 8

2015
[20]

Black-box adversarial attacks with limited queries and information

Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In ICML, 2018. 1

2018
[21]

Linear con- vergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition

Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear con- vergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition. In ECML–PKDD, 2016. 6, 15

2016
[22]

Kingma and Jimmy Lei Ba

Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In ICLR, 2015. 1

2015
[23]

Zeroth-order optimization with orthogo- nal random directions

David Kozak, Cesare Molinari, Lorenzo Rosasco, Luis Teno- rio, and Silvia Villa. Zeroth-order optimization with orthogo- nal random directions. Mathematical Programming, 2023. 2, 3, 6, 11

2023
[24]

Learning multiple layers of features from tiny images

Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. 8

2009
[25]

signSGD via zeroth-order oracle

Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In ICLR, 2019. 2, 7, 16, 17

2019
[26]

Hero III, and Pramod K

Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O. Hero III, and Pramod K. A primer on zeroth- order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 2020. 1

2020
[27]

General stability analysis for zeroth-order optimization algorithms

Xinyue Liu, Hualin Zhang, Bin Gu, and Hong Chen. General stability analysis for zeroth-order optimization algorithms. In ICLR, 2024. 17

2024
[28]

Adversarial variational optimization of non-differentiable simulators

Gilles Louppe, Joeri Hermans, and Kyle Cranmer. Adversarial variational optimization of non-differentiable simulators. In AISTATS, 2019. 1

2019
[29]

Efficient second order online learning by sketching

Haipeng Luo, Alekh Agarwal, Nicolo Cesa-Bianchi, and John Langford. Efficient second order online learning by sketching. In NeurIPS, 2016. 2

2016
[30]

Phishing Websites

Rami Mohammad and Lee McCluskey. Phishing Websites. UCI Machine Learning Repository, 2012. 7

2012
[31]

Efficiency of coordinate descent methods on huge-scale optimization problems

Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Opti- mization, 2012. 2

2012
[32]

Random gradient-free minimization of convex functions

Yurii Nestrov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. FoCM, 2015. 1, 3, 16

2015
[33]

Jorge Nocedal and Stephen J. Wright. Numerical Optimiza- tion. Springer, 2nd edition, 2006. 1, 3, 4, 6, 11, 13, 14

2006
[34]

Zeroth-order random subspace algorithm for non-smooth con- vex optimization

Ryota Nozawa, Pierre-Louis Poirion, and Akiko Takeda. Zeroth-order random subspace algorithm for non-smooth con- vex optimization. Journal of Optimization Theory and Appli- cations, 2025. 14

2025
[35]

John C. Platt. Fast Training of Support Vector Machines Using Sequential Minimal Optimization . MIT Press, Cambridge, MA, 1999. 7

1999
[36]

Gradient compressed sensing: A query-efficient gradient estimator for high- dimensional zeroth-order optimization

Ruizhong Qiu and Hanghang Tong. Gradient compressed sensing: A query-efficient gradient estimator for high- dimensional zeroth-order optimization. In ICML, 2024. 7, 16, 17 9

2024
[37]

SDNA: Stochastic dual Newton ascent for empirical risk minimization

Zheng Qu, Peter Richt ´arik, Martin Tak´aˇc, and Olivier Fer- coq. SDNA: Stochastic dual Newton ascent for empirical risk minimization. In ICML, 2016. 2

2016
[38]

Samaria and A

F. Samaria and A. Harter. Parameterisation of a stochastic model for human face identification. In WACV, 1994. 7

1994
[39]

Youn, Michael D

Adam Thelen, Xiaoge Zhang, Olga Fink, Yan Lu, Sayan Ghosh, Byeng D. Youn, Michael D. Todd, Sankaran Mahade- van, Chao Hu, and Zhen Hu. A comprehensive review of dig- ital twin—part 1: modeling and twinning enabling technolo- gies. Structural and Multidisciplinary Optimization ...

1991
[40]

Zeroth-order SciML: Non-intrusive integration of sci- entific software with deep learning

Ioannis Tsaknakis, Bhavya Kailkhura, Sijia Liu, Donald Love- land, James Diffenderfer, Anna Maria Hiszpanski, and Mingyi Hong. Zeroth-order SciML: Non-intrusive integration of sci- entific software with deep learning. arXiv:2206.02785, 2022. 1

2022 arXiv
[41]

Wadia, Daniel Duckworth, Samuel S

Neha S. Wadia, Daniel Duckworth, Samuel S. Schoenholz, Ethan Dyer, and Jascha Sohl-Dickstein. Whitening and sec- ond order optimization both make information in the dataset unusable during training, and can reduce or prevent general- ization. In ICML, 2021. 8

2021
[42]

Picking winning tickets before training by preserving gradient flow

Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In ICLR, 2020. 2

2020
[43]

ReLIZO: Sample reusable linear interpolation-based zeroth-order optimization

Xiaoxing Wang, Xiaohan Qin, Xiaokang Yang, and Junchi Yan. ReLIZO: Sample reusable linear interpolation-based zeroth-order optimization. In NeurIPS, 2024. 2, 6, 7, 11, 14, 16, 17

2024
[44]

Hessian recovery based finite element methods for the Cahn-Hilliard equation

Minqiang Xu, Hailong Guo, and Qingsong Zou. Hessian recovery based finite element methods for the Cahn-Hilliard equation. Journal of Computational Physics, 2019. 4

2019
[45]

Mirror natural evolution strategies

Haishan Ye. Mirror natural evolution strategies. arXiv:2308.00469, 2023. 1, 2, 16, 17

2023 arXiv
[46]

Hessian-aware zeroth-order optimization for black-box adversarial attack

Haishan Ye, Zhichao Huang, Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian-aware zeroth-order optimization for black-box adversarial attack. arXiv:1812.11377, 2018. 1, 2, 3

2018 arXiv
[47]

Matthew D. Zeiler. ADADELTA: An adaptive learning rate method. arXiv:1212.5701, 2015. 1

2015 arXiv
[48]

How to robustify black- box ML models? A zeroth-order optimization perspective

Yimeng Zhang, Yuguang Yao, Jinghan Jia, Jinfeng Yi, Mingyi Hong, Shiyu Chang, and Sijia Liu. How to robustify black- box ML models? A zeroth-order optimization perspective. In ICLR, 2022. 1

2022
[49]

Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tian- long Chen

Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin-Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tian- long Chen. Revisiting zeroth-order optimization for memory- efficient LLM fine-tuning: A benchmark. In ICML, 2024. 1

2024
[50]

HE- LENE: Hessian layer-wise clipping and gradient annealing for accelerating fine-tuning LLM with zeroth-order optimization

Huaqin Zhao, Jiaxi Li, Yi Pan, Shizhe Liang, Xiaofeng Yang, Wei Liu, Xiang Li, Fei Dou, Tianming Liu, and Jin Lu. HE- LENE: Hessian layer-wise clipping and gradient annealing for accelerating fine-tuning LLM with zeroth-order optimization. arXiv:2411.10696, 2024. 5

2024 arXiv
[51]

Yanjun Zhao, Sizhe Dang, Haishan Ye, and Ivor W. Tsang. Second-order fine-tuning without pain for LLMs: A Hessian informed zeroth-order optimizer. arXiv:2402.15174v3, 2025. 1, 2, 5, 7, 17 10 Appendix In this appendix, we provide

2025 arXiv
[52]

the full proof of our main convergence result (Proposition 1; Appendix A)
[53]

additional information, including preliminary details on zeroth-order (ZO) optimization and a detailed description of our experimental settings (Appendix B); and
[54]

For completeness, some content from Sec

extended experimental results (Appendix C). For completeness, some content from Sec. 4.3 is reproduced here. A. Convergence analysis This section presents a complete proof of Proposition 1. We begin by introducing assumptions commonly used in zeroth-order optimization [23, 43]...
[55]

(80) to Eq

(80) Finally, substituting Eq. (80) to Eq. (78), we obtain Eg∼D[f (xk) − f (x∗)] ≤ (1 − ν)k C1 2 ∆0
[56]

Additional information B.1

(81) 15 B. Additional information B.1. Preliminaries for zeroth-order optimization First- and second-order optimization. Consider the problem of minimizing a twice-continuously differentiable function f : Rd 7→ R. Two well-established strategies for this task are first-order a...

Pith tools

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

[1] [5]

Zeroth-order randomized subspace Newton methods

Erik Berglund, Sarit Khirirat, and Xiaoyu Wang. Zeroth-order randomized subspace Newton methods. In ICASSP, 2022. 12

work page 2022

[2] [1]

Backpropagation and stochastic gradient descent method

Shunichi Amari. Backpropagation and stochastic gradient descent method. Neurocomputing, 1993. 1

work page 1993

[3] [2]

Tsybakov

Jean-Yves Audibert and Alexandre B. Tsybakov. Fast learn- ing rates for plug-in classifiers. The Annals of Statistics, 2007. 14

work page 2007

[4] [4]

Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg

Albert S. Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. FoCM, 2022. 2

work page 2022

[5] [6]

Stochastic gradient descent tricks

L´eon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade. Springer, 2012. 1

work page 2012

[6] [7]

Picking winning tickets before training by preserving gradient flow

Wang Chaoqi, Zhang Guodong, and Grosse Roger. Picking winning tickets before training by preserving gradient flow. In ICLR, 2020. 17

work page 2020

[7] [8]

DeepZero: Scaling up zeroth-order optimization for deep model training

Aochuan Chen, Yimeng Zhang, Jinghan Jia, James Diffend- erfer, Jiancheng Liu, Konstantinos Parasyris, Yihua Zhang, Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. DeepZero: Scaling up zeroth-order optimization for deep model training. In ICLR, 2024. 2, 7, 8, 17

work page 2024

[8] [9]

ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models

Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho- Jui Hsieh. ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In AISec, 2017. 1

work page 2017