A Gaussian smoothing-based zeroth-order method for Goldstein second-order stationarity

Hao Zhang; Liaoyuan Zeng; Man-Chung Yue; Ming Lei; Ting Kei Pong

REVIEW 2 major objections 4 minor 51 references

A Gaussian smoothing-based zeroth-order method for Goldstein second-order stationarity

T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read This paper introduces a Goldstein-style second-order stationarity criterion for functions that are only once differentiable with locally Lipschitz gradients, and proves that a zeroth-order algorithm using Gaussian smoothing and cubic regula

desk verdict Genuinely new C^{1,1} second-order stationarity framework with a sound core analysis, but Theorem 4.3 has a false constant identity and a load-bearing moment bound that controls the rate. read the letter →

arxiv 2607.21258 v1 pith:J5JP2U65 submitted 2026-07-23 math.OC

Ming Lei , Ting Kei Pong , Man-Chung Yue , Liaoyuan Zeng , Hao Zhang This is my paper · ORCID

classification math.OC MSC 90C5690C2649J5265K05

keywords zeroth-orderoptimizationGoldsteinsecond-orderδ-subdifferentialGaussiansmoothingcubicregularizationhomotopymethodLipschitzdifferentiablefunctionsstationarityiterationcomplexity

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 asks whether second-order stationarity can be meaningfully defined and algorithmically reached when the objective is not twice differentiable. It answers yes by defining the Goldstein second-order δ-subdifferential, the convex hull of all generalized Hessians on a δ-ball, and the associated notion of (ε1, ε2, δ)-second-order stationary points for C^{1,1} functions. The central bridge is a new connection between the Hessian of the Gaussian-smoothed function and this Goldstein subdifferential, which requires only Lipschitz differentiability, not Lipschitz Hessian. On that bridge, the paper builds a function-value-only algorithm with growing Monte Carlo sample sizes and a vanishing smoothing parameter, and proves iteration complexity for reaching such points under a coercivity-type moment bound. If correct, this gives the first complexity guarantee for approximate second-order stationarity in a derivative-free setting without assuming twice differentiability.

What carries the argument

The load-bearing object is the Goldstein second-order δ-subdifferential, a tractable surrogate for the pointwise generalized Hessian. Its algorithmic partner is the bridge theorem (Theorem 3.2), which shows that for σ at most an explicit threshold, −2ε + λ_min(∇²fσ(x)) lower-bounds inf_{||h||=1} s(h, ∂²_{G,δ} f(x) h). This transfers negative curvature from the smoothed Hessian, which can be estimated by function-value samples, to the original function's generalized Hessian. The cubic subproblem with the (1+||x_k||)³ scaling provides descent and Hessian-feasibility through its first- and second-order optimality conditions, while Lemma 2.2 converts bounds for the smoothed function into bounds

What would settle it

Take the one-dimensional C^{1,1} function f(x)=x²/2 for x≥0 and x²/4 for x<0, which has Lipschitz gradient but no second derivative at 0, and run Algorithm 1 with fixed γ, ρ, α, β. The theorem predicts E[|∇f(x_{k*})|^{1/(6⌈1/θ⌉)}] decays like T^{−ρ} (here θ=2) and the curvature measure like T^{−dρ} + T^{−(1−2ρ)/3}; fit the empirical rates over T = 10² to 10⁵. A rate much slower than predicted, or a failure to decrease, would show the complexity claim is false or not tight. Separately, evaluate Theorem 3.2(ii) at x=0 for this f, where fσ''(0)=3/4 for every σ, to check the bridge on a non-twice-

Watch

Extended reading notes

Core claim

For a continuously differentiable function with locally Lipschitz gradient and bounded-below values, the paper defines the Goldstein second-order δ-subdifferential ∂²_{G,δ}f(x) = conv(∪_{y∈B(x,δ)} ∂²_H f(y)) and calls x an (ε1, ε2, δ)-second-order stationary point when ||∇f(x)|| ≤ ε1 and inf_{||h||=1} s(h, ∂²_{G,δ} f(x) h) ≥ −ε2. The paper proves that the Hessian of the Gaussian smoothing fσ admits a derivative-free expectation formula and, for σ below an explicit threshold, its minimum eigenvalue lower-bounds the Goldstein second-order curvature. Algorithm 1 estimates ∇fσ and ∇²fσ from centered function-value differences, solves a cubic-regularized subproblem with a (1+||x_k||)³ scaling, le

Load-bearing premise

The proof needs the iterates to have a bounded θ-th moment: sup_T E[||x_{k*}||^θ] < ∞ for some θ > 0; the paper offers f(x) ≥ μ1||x||^θ − μ2 as a sufficient condition, but θ and the constants are not specified, and if the bound fails the convergence guarantees apply only to the smoothed function, not the original.

Editorial extensions

If this is right

Any bounded-below objective with Lipschitz continuous gradient can be optimized to approximate second-order stationarity using only function evaluations; no gradients or Hessians are ever queried.
The user does not need to pre-specify a target accuracy: the smoothing parameter decreases and sample sizes increase automatically, giving an a priori iteration bound in terms of T.
The Gaussian-smoothing Hessian is a valid computational proxy for the Goldstein second-order subdifferential under Lipschitz differentiability alone, widening the class of functions for which second-order guarantees are available.
When the coercivity condition f(x) ≥ μ1||x||^θ − μ2 holds, the complexity statement applies to the original objective, not merely to the smoothed one.
The framework extends derivative-free second-order stationarity guarantees from twice-differentiable functions with Lipschitz Hessian to the larger class C^{1,1}.

Reading between the lines

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

Editorial inference: the moment bound (4.30) is doing more work than the word 'mild' suggests. Theorems 4.1 and 4.2 control only the smoothed quantities, and it is Lemma 2.2 that promotes those to guarantees for the original f; if (4.30) fails, or holds only with very small θ, the stated complexity of Theorem 4.3 either says nothing or degrades severely because the final exponents are 1/(6⌈1/θ⌉).
Editorial inference: the rates contain a built-in trade-off. Since ρ ∈ (0,1/2), choosing ρ close to 1/2 improves the T^{−ρ} gradient term but pushes the T^{−(1−2ρ)/3} curvature term toward a constant rate; no single parameter choice makes both measures converge quickly.
Editorial inference: the stationarity notion averages generalized Hessians over a δ-ball, so a point can pass the criterion while having a negative-curvature direction of width smaller than δ. A natural testable extension is to let δ shrink adaptively with T, which would make the smoothed-Hessian proxy approximate the pointwise generalized Hessian as the iteration count grows.

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

Read this one. The Goldstein second-order δ-subdifferential and the associated (ε1, ε2, δ)-SOSP are a real framework: they extend second-order stationarity to C^{1,1} in a way that is checkable through Gaussian smoothing, and Theorem 3.2 is the core contribution. The proof machinery in Section 4 up through Theorems 4.1–4.2 is coherent; I did a line-by-line pass on Lemmas 4.4, 4.5, and the descent analysis and found no hidden fitting or circularity. The sample-growth and vanishing smoothing sequence are sensible, and the (1+‖x_k‖)^3 scaling in the subproblem is justified by Remark 4.1. Credit where due: the paper contains no fitted constants, and the imported tail bound from [31] is published and parameter-free.

Now the soft spots. First, the capstone Theorem 4.3 has a real constant bug. After (4.33), the proof uses (3dρ)^{1/d} = 3^ρ to convert the definition of ε_T into the threshold T. That identity is false in general—take d=3, ρ=0.3, where the left side is 2.7 and the right side is 3^0.9 ≈ 2.687. The inequality goes the wrong way, so the stated constants and the threshold are not proven as written. This is mechanical and fixable—redefine ε_T or multiply the threshold by the missing factor—but it has to be fixed.

Second, the moment bound (4.30) is load-bearing, not just a technical reach. It does not follow from C^{1,1} plus bounded-below: f(x) = −e^{−‖x‖²} is a smooth bounded-below function with Lipschitz gradient and violates the sufficient condition (4.39) for every θ > 0. Theorems 4.1–4.2 do not need it; Theorem 4.3 does, and the unknown θ and fMD enter the rate exponent 1/(6⌈1/θ⌉) and the prefactor. If θ is small, the stated rate is essentially empty. The abstract does say a coercivity-type assumption is used, so the authors are not hiding it, but “mild” understates that this assumption sets the rate.

Overall: the framework is a genuine subfield-level advance for zeroth-order non-twice-differentiable optimization, and the parts I checked support the conceptual claims. The capstone needs a corrected constant and a more honest statement of what the moment bound buys. Send it to serious peer review—a good referee will pin the authors to fix Theorem 4.3 and clarify the rate dependence on θ.

Referee Report

2 major / 4 minor

Summary. The paper introduces a Goldstein-type second-order δ-subdifferential ∂²_{G,δ}f for functions in C^{1,1}(R^d), together with the associated notion of (ε1,ε2,δ)-second-order stationary point. It then proposes a zeroth-order algorithm (Algorithm 1) that combines Gaussian smoothing, cubic regularization, a homotopy schedule σ_k = γk^{−ρ}, and increasing sample sizes N_k, J_k. The main results are Theorems 4.1–4.2, which give bounds on the smoothed gradient and smoothed Hessian eigenvalue, and Theorem 4.3, which converts these into guarantees on the original, unsmoothed stationarity measures under an additional moment/coercivity assumption (4.30). The paper claims to provide the first zeroth-order complexity guarantee for approximate second-order stationarity without twice differentiability.

Significance. If the results hold, this is a meaningful contribution: it provides a natural second-order analog of the Goldstein subdifferential and a zeroth-order method with explicit complexity rates for finding points satisfying the new stationarity criterion, under weaker smoothness than the existing Lipschitz-Hessian assumption. The proofs are largely self-contained and the constants are explicit, with no fitted parameters. The main caveats are that the headline guarantee is conditional on an extra moment bound, and that the proof of Theorem 4.3 contains a fixable but load-bearing technical error.

major comments (2)

[Theorem 4.3, proof after (4.33)] The proof asserts that σ_{k*} ≤ σ_{⌊T/2⌋} = γ(⌊T/2⌋)^{−ρ} ≤ γ3^ρ T^{−ρ} = (dπe)^{−1/2}δ(4L)^{−1/d}ϵ_T^{1/d}. Direct substitution of ϵ_T from (4.33) gives (dπe)^{−1/2}δ(4L)^{−1/d}ϵ_T^{1/d} = (3dρ)^{1/d}γT^{−ρ} (or 3ρ^{1/d}γT^{−ρ} if the intended factor was 3^dρ). This equals γ3^ρT^{−ρ} only for special (d,ρ); for example d=1, ρ=1/2 gives 1.5γT^{−ρ} versus 1.732γT^{−ρ}. Consequently the invocation of Remark 3.2 to obtain (4.32) is not justified as written. This is fixable by redefining ϵ_T (e.g., with factor 3^{ρd} in place of 3dρ or 3^dρ) and adjusting λ3 accordingly, but it is a genuine error in the proof of the main complexity bound.
[§4.2, (4.30)–(4.39)] The complexity guarantee in Theorem 4.3 is entirely mediated by the moment bound (4.30), which is not a consequence of the standing assumptions (Lipschitz-differentiable, bounded below). The sufficient condition (4.39) fails for natural bounded-below C^{1,1} functions such as f(x) = −e^{−||x||²}. Moreover, the rates in (4.31)–(4.32) contain the exponent 1/(6⌈1/θ⌉) and the prefactor (1+√fMD), and the user is not told θ or fMD in terms of problem data. The paper calls this assumption 'mild', but it controls the quality of the rate, not just the reach of the proof. This should be stated more prominently in the abstract/introduction, and the dependence on θ and fMD should be discussed, ideally with examples or a remark quantifying the degradation for small θ.

minor comments (4)

[Theorem 4.3 statement] The condition on T involves min{5L,1}^{1/d} in the denominator, while the proof refers to 0<ϵ_T<min{5L,1}. Please ensure consistency between the stated T-threshold and the condition used in the proof.
[Lemma 4.5, equations (4.25)–(4.26)] A few displays have missing norms, e.g., the left-hand sides should involve E_k[||x_{k+1}−x_k||^3] rather than E_k[||x_{k+1}−x_k||^3] without the norm in the text. Please proofread the equations.
[Notation] The exponent ⌈1/θ⌉ is used throughout Theorem 4.3; a short remark clarifying its behavior for θ>1 (where it equals 1) would improve readability.
[Algorithm 1] The sample sizes N_k and J_k are given as ⌈(k+1)^{4/3 β}⌉ and ⌈(k+1)^{2/3 α}⌉; stating that these are not tuned to a target tolerance (the algorithm is anytime) would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is a forward chain of explicit bounds; the only overlapping-author citation is independent support, and the moment bound is a stated assumption rather than a fitted input.

full rationale

Algorithm 1's analysis is a forward derivation. Lemma 4.4 bounds the sample-average estimators v_k and H_k by explicit constants D1, D2, D3 depending only on L, d, gamma, alpha, beta; Lemma 4.5 combines these with the cubic subproblem optimality conditions (4.6)-(4.7) via Young's inequality to obtain the descent bound (4.21). Theorems 4.1-4.2 then bound the weighted smoothed gradient and smoothed Hessian eigenvalue by explicit powers of T. Theorem 4.3 combines these with Theorem 3.2 and the explicit sigma bound (3.8), and then uses Lemma 2.2 to convert weighted bounds into unweighted bounds on the original Goldstein measures. The conversion is genuinely extra: it invokes the moment bound (4.30), which the paper states as an assumption and supports in Proposition 4.1 under the coercivity condition (4.39). No predicted quantity appears among the inputs; no parameter is fitted to data; no target conclusion is assumed in a hypothesis. The only overlapping-author citation, [31], supplies the Gaussian tail bound (3.12) and the simplified sigma bound in Remark 3.2, but these are published, parameter-free results whose stated assumptions (Lipschitz gradient) do not include the present second-order Goldstein target, so they count as independent support rather than circularity. The fact that (4.30) controls the rate via 1/theta and fMD is a legitimate caveat about the strength of the guarantee, not a circular reduction. I find no significant circularity.

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

The paper's central claim rests on standard analysis/probability machinery plus three domain assumptions stated in the text. The non-standard load-bearing item is the moment bound (4.30)/coercivity (4.39): it is flagged by the authors but controls the final rate through the unknown exponent θ. Algorithm parameters ρ, α, β, γ are user inputs satisfying Assumption 4.1; the theory holds for any valid choice, so they are not fitted. The Goldstein second-order δ-subdifferential is a new definition, not a hidden postulate; its worth is established by Theorems 3.2 and 4.3 via the smoothed-Hessian certificate.

free parameters (5)

coercivity exponent θ
Existential parameter in (4.30)/(4.39); the final complexity exponent 6⌈1/θ⌉ depends on it, so the guarantee is not an explicit (ε₁, ε₂) iterate count for the user.
coercivity constants μ₁, μ₂
Proposition 4.1, (4.39); needed to derive the moment bound f_MD; not constructively given.
initial smoothing scale γ (σ₀ = γ, σ_k = γk^{−ρ}) = γ ∈ (0,1) user-specified
Algorithm 1 Input; enters all constants λ₁–λ₄ and the T threshold.
smoothing decay exponent ρ = ρ ∈ (0,1/2) user-specified
Assumption 4.1; sets the rates T^{−ρ} and T^{−(1−2ρ)/3}.
sample-growth exponents α, β = α, β > 0 with 2ρ+α > 1, ρ/2+β > 1
Assumption 4.1; they make the estimation-error series converge.

assumptions (6)

domain assumption f ∈ C^{1,1}(R^d) with L-Lipschitz gradient; L known to the algorithm (used in h_k and σ̄ bounds)
Sections 3–4 throughout; Theorems 3.1–3.2 and Lemma 4.4 use L; Algorithm 1's subproblem requires L.
domain assumption f bounded below: f* := inf f > −∞
Problem (4.1), Section 4; used in the telescoping arguments of Lemma 4.5.
domain assumption Moment bound (4.30): sup_T E[||x_{k*}||^θ] ≤ f_MD for some θ > 0, with sufficient condition (4.39) f(x) ≥ μ₁||x||^θ − μ₂
Theorem 4.3 and Proposition 4.1; converts the smoothed-iterate bounds into guarantees on the original f; the rate exponent depends on θ.
ad hoc to paper Assumption 4.1: ρ∈(0,1/2), 2ρ+α>1, ρ/2+β>1
Makes the series in Lemma 4.5/Theorem 4.3 converge; benign but imposed for the analysis.
standard math Tail-probability bound (3.12), imported from [31, Theorem 3.6(ii)] plus the Remark 3.2 simplification
Theorem 3.2(ii) proof: 'following the proof of [31, Theorem 3.6(ii)]' — the critical Gaussian-tail control with Lambert W is not reproduced.
standard math Standard background: Rademacher a.e. differentiability, [37, Lemma 1] Gaussian moment bounds, Rosenthal inequality ([41])
Used in Theorem 3.2(i), Lemma 4.2, and Lemma 4.4.

invented entities (2)

Goldstein second-order δ-subdifferential ∂²_G,δ f independent evidence
purpose: Set-valued surrogate for the Hessian in C^{1,1}; enables a tractable relaxed second-order optimality condition (Defs 3.1–3.2).
Not an occult postulate: reduces to the Hessian over B(x,δ) when f is C²; contains ∇²f at all twice-differentiability points; any local minimizer is (0,0,δ)-SOSP; Theorem 3.2 gives it an independent computational handle via ∇²f_σ.
(ε₁, ε₂, δ)-second-order stationary point independent evidence
purpose: Algorithm output target; replaces the intractable exact second-order condition.
Definitional; the smoothed Hessian certificate approximately implies it (Theorem 3.2), so it is reachable by a zeroth-order method.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Gaussian smoothing-based zeroth-order method for Goldstein second-order stationarity." pith.science (2026). https://pith.science/paper/J5JP2U65

@misc{pith2026260721258,
  author       = {Pith},
  title        = {Pith review of: A Gaussian smoothing-based zeroth-order method for Goldstein second-order stationarity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J5JP2U65}},
  note         = {Machine review of arXiv:2607.21258}
}

abstract

We introduce a new generalized Hessian, called the Goldstein second-order $\delta$-subdifferential, and an associated notion of $(\epsilon_1,\epsilon_2,\delta)$-second-order stationary point for continuously differentiable functions with locally Lipschitz gradients. We propose a zeroth-order algorithm based on cubic regularization and Gaussian smoothing with homotopy to find such approximate second-order stationary points for Lipschitz differentiable functions, and derive the iteration complexity under a mild coercivity-type assumption on the objective function.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 6 linked inside Pith

[31]

M. Lei, T. K. Pong, S. Sun and M.-C. Yue. Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization.SIAM J. Optim.35, pp. 1393–1418 (2025)

2025
[1]

Amaran, N

S. Amaran, N. V. Sahinidis, B. Sharda and S. J. Bury. Simulation optimization: a review of algorithms and applications.Ann. Oper. Res.240, pp. 351–380 (2016)

2016
[2]

J. P. Aubin and H. Frankowska.Set-Valued Analysis. Birkh¨ auser (1990)

1990
[3]

Balasubramanian and S

K. Balasubramanian and S. Ghadimi. Zeroth-order nonconvex stochastic opti- mization: handling constraints, high dimensionality, and saddle points.Found. Comput. Math.22, pp. 35–76 (2022)

2022
[4]

Bhojanapalli, B

S. Bhojanapalli, B. Neyshabur and N. Srebro. Global optimality of local search for low rank matrix recovery. InAdv. Neural Inf. Process. Syst.29, pp. 3873–3881 (2016)

2016
[5]

Billingsley.Probability and Measure

P. Billingsley.Probability and Measure. John Wiley and Sons, (2008)

2008
[6]

Cartis, N

C. Cartis, N. I. M. Gould and P. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results.Math. Program.127, 245–295 (2011)

2011
[7]

Cartis, N

C. Cartis, N. I. M. Gould and P. L. Toint. Complexity bounds for second-order optimality in unconstrained optimization.J. Complexity28, pp. 93–108 (2012)

2012

Show all 51 references

[8]

P. Chen, H. Zhang, Y. Sharma, J. Yi and C.-J. Hsieh. ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. InProc. 10th ACM Workshop Artif. Intell. Secur, pp. 15–26 (2017)

2017
[9]

F. H. Clarke.Optimization and Nonsmooth Analysis. Wiley, New York, (1983). 26

1983
[10]

A. R. Conn, K. Scheinberg and L. N. Vicente.Introduction to Derivative-free Optimization. SIAM (2009)

2009
[11]

Cominetti and R

R. Cominetti and R. Correa. A generalized second-order derivative in nonsmooth optimization.SIAM J. Control Optim.28, pp. 789–809 (1990)

1990
[12]

Davis, M

D. Davis, M. D ´ ıaz and D. Drusvyatskiy. Escaping strict saddle points of the Moreau envelope in nonsmooth optimization.SIAM J. Optim.32, pp. 1958–1983 (2022)

1958
[13]

Davis, D

D. Davis, D. Drusvyatskiy and L. Jiang. Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization.Found. Comput. Math. 26, pp. 779–861 (2026)

2026
[14]

Dieudonne.Foundations of Modern Analysis

J. Dieudonne.Foundations of Modern Analysis. Academic Press (1969)

1969
[15]

R. Ge, J. D. Lee and T. Ma. Matrix completion has no spurious local minimum. InAdv. Neural Inf. Process. Syst.29, pp. 2973–2981 (2016)

2016
[16]

A. A. Goldstein. Optimization of Lipschitz continuous functions.Math. Program. 13, pp. 14–22 (1977)

1977
[17]

Grafakos.Classical Fourier Analysis

L. Grafakos.Classical Fourier Analysis. Springer, New York, (2008)

2008
[18]

Guan and A

J. Guan and A. M.-C. So. ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points. Preprint (2024). Available at https://arxiv.org/abs/2410.05025

2024 arXiv
[19]

X. Guo, D. Keivan, G. Dullerud, P. Seiler and B. Hu. Complexity of derivative- free policy optimization for structured H∞ control. InAdv. Neural Inf. Process. Syst.36, pp. 5050–5078 (2023)

2023
[20]

J. B. Hiriart-Urruty, J. J. Strodiot and V. H. Nguyen. Generalized Hessian matrix and second-order optimality conditions for problems with C 1,1 data.Appl. Math. Optim.11, pp. 43–56 (1984)

1984
[21]

Huang, B

F. Huang, B. Gu, Z. Huo, S. Chen and H. Huang. Faster gradient-free proximal stochastic methods for nonconvex nonsmooth optimization. InProc. AAAI Conf. Artif. Intell.33, pp. 1503–1510 (2019)

2019
[22]

Huang and W

M. Huang and W. Zhu. Escaping saddle points for nonsmooth weakly con- vex functions via perturbed proximal algorithms. Preprint (2023). Available at https://arxiv.org/abs/2102.02837

2023 arXiv
[23]

Ioffe and T

A. Ioffe and T. Mi losz. On a characterization of C 1,1 functions.Cybernet. Systems Anal.38, pp. 313–322 (2002). 27

2002
[24]

Iwakiri, Y

H. Iwakiri, Y. Wang, S. Ito and A. Takeda. Single loop Gaussian homotopy method for non-convex optimization. InAdv. Neural Inf. Process. Syst.35, pp. 7065–7076 (2022)

2022
[25]

C. Jin, R. Ge, P. Netrapalli, S. M. Kakade and M. I. Jordan. How to escape saddle points efficiently. InProc. 34th Int. Conf. Mach. Learn., pp. 1724–1732 (2017)

2017
[26]

Jongeneel, M.-C

W. Jongeneel, M.-C. Yue and D. Kuhn. Small errors in random zeroth-order optimization are imaginary.SIAM J. Optim.34, pp. 2638–2670 (2024)

2024
[27]

Larson, M

J. Larson, M. Menickelly and S. M. Wild. Derivative-free optimization methods. Acta Numer.28, pp. 287–404 (2019)

2019
[28]

Lei and U

J. Lei and U. V. Shanbhag. Variance-reduced accelerated first-order methods: central limit theorems and confidence statements.Math. Oper. Res.50, pp. 1364–1397 (2025)

2025
[29]

F. Lieder. Solving large scale cubic regularization by a generalized eigenvalue problem.SIAM J. Optim.30, 3345–3358 (2020)

2020
[30]

Liu, M.-C

H. Liu, M.-C. Yue and A. M.-C. So. On the estimation performance and convergence rate of the generalized power method for phase synchronization. SIAM J. Optim.27, pp. 2426–2446 (2017)

2017
[32]

T. Lin, Z. Zheng and M. I. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. InAdv. Neural Inf. Process. Syst. 35, pp. 26160–26175 (2022)

2022
[33]

Malladi, T

S. Malladi, T. Gao, E. Nguyen, D. Chen, P. Sridhar, S. Sukhbaatar, A. Letman and S. Arora. Fine-tuning language models with just forward passes. InAdv. Neural Inf. Process. Syst.36, pp. 53038–53075 (2023)

2023
[34]

A. D. McRae. Phase retrieval via overparametrized nonconvex optimiza- tion: nonsmooth amplitude loss landscapes. Preprint (2025). Available at https://arxiv.org/abs/2511.19045

2025 arXiv
[35]

K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming.Math. Program.39, pp. 117–129 (1987)

1987
[36]

Nesterov and B

Y. Nesterov and B. T. Polyak. Cubic regularization of Newton method and its global performance.Math. Program.108, pp. 177–205, (2006)

2006
[37]

Nesterov and V

Y. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions.Found. Comput. Math.17, pp. 527–566 (2017). 28

2017
[38]

Nouiehed, J

M. Nouiehed, J. D. Lee and M. Razaviyayn. Convergence to second-order stationarity for constrained non-convex optimization. Preprint (2018). Available at https://arxiv.org/abs/1810.02024

2018 arXiv
[39]

P´ ales and V

Z. P´ ales and V. Zeidan. Generalized Hessian for C 1,1 functions in infinite dimensional normed spaces.Math. Program.74, pp. 59–78 (1996)

1996
[40]

Z. Ren, Y. Tang and N. Li. Escaping saddle points in zeroth-order optimization: the power of two-point estimators. InProc. 40th Int. Conf. Mach. Learn., pp. 28914–28975 (2023)

2023
[41]

E. Rio. Moment inequalities for sums of dependent random variables under projective conditions.J. Theor. Probab.22, pp. 146–163 (2009)

2009
[42]

R. T. Rockafellar and R. J-B Wets.Variational Analysis. Springer-Verlag, Berlin, (1998)

1998
[43]

Rudin.Real and Complex Analysis

W. Rudin.Real and Complex Analysis. McGraw-Hill, New York, (1987)

1987
[44]

Salimans, J

T. Salimans, J. Ho, X. Chen, S. Sidor and I. Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. Preprint (2017). Available at https://arxiv.org/abs/1703.03864

2017 arXiv
[45]

Starnes, A

A. Starnes, A. Dereventsov and C. Webster. Gaussian smoothing gradi- ent descent for minimizing functions (GSmoothGD). To appear inOptim. https://doi.org/10.1080/02331934.2026.2669828

2026
[46]

E. M. Stein and R. Shakarchi.Functional Analysis: Introduction to Further Topics in Analysis. Princeton University Press, Princeton, (2011)

2011
[47]

J. Sun, Q. Qu and J. Wright. Complete dictionary recovery over the sphere I: Overview and the geometric picture.IEEE Trans. Inform. Theory63, pp. 853–884 (2017)

2017
[48]

J. Sun, Q. Qu and J. Wright. A geometric analysis of phase retrieval.Found. Comput. Math.18, pp. 1131–1198 (2018)

2018
[49]

Vlatakis-Gkaragkounis, L

E.-V. Vlatakis-Gkaragkounis, L. Flokas and G. Piliouras. Efficiently avoiding saddle points with zero order methods: No gradients required. InAdv. Neural Inf. Process. Syst.32, pp. 10066–10077 (2019)

2019
[50]

J. Xia, Z. Lin and Q. Deng. Revisiting randomized smoothing: nonsmooth nonconvex optimization beyond global Lipschitz continuity. Preprint (2025). Available at https://arxiv.org/abs/2508.13496

2025 arXiv
[51]

M.-C. Yue, Z. Zhou and A. M.-C. So. On the quadratic convergence of the cubic regularization method under a local error bound condition.SIAM J. Optim.29, pp. 904–932 (2019). 29

2019

Pith tools

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

[1] [31]

M. Lei, T. K. Pong, S. Sun and M.-C. Yue. Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization.SIAM J. Optim.35, pp. 1393–1418 (2025)

2025

[2] [1]

Amaran, N

S. Amaran, N. V. Sahinidis, B. Sharda and S. J. Bury. Simulation optimization: a review of algorithms and applications.Ann. Oper. Res.240, pp. 351–380 (2016)

2016

[3] [2]

J. P. Aubin and H. Frankowska.Set-Valued Analysis. Birkh¨ auser (1990)

1990

[4] [3]

Balasubramanian and S

K. Balasubramanian and S. Ghadimi. Zeroth-order nonconvex stochastic opti- mization: handling constraints, high dimensionality, and saddle points.Found. Comput. Math.22, pp. 35–76 (2022)

2022

[5] [4]

Bhojanapalli, B

S. Bhojanapalli, B. Neyshabur and N. Srebro. Global optimality of local search for low rank matrix recovery. InAdv. Neural Inf. Process. Syst.29, pp. 3873–3881 (2016)

2016

[6] [5]

Billingsley.Probability and Measure

P. Billingsley.Probability and Measure. John Wiley and Sons, (2008)

2008

[7] [6]

Cartis, N

C. Cartis, N. I. M. Gould and P. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results.Math. Program.127, 245–295 (2011)

2011

[8] [7]

Cartis, N

C. Cartis, N. I. M. Gould and P. L. Toint. Complexity bounds for second-order optimality in unconstrained optimization.J. Complexity28, pp. 93–108 (2012)

2012