Success at Goldstein -stationarity
DefinitionZOGlobalLB_Supplement_SucceedsGoldsteinnonsmooth-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1stationarityzeroth-order-optimization
A randomized zeroth-order run succeeds at Goldstein -stationarity if it stops after finitely many exact scalar queries and outputs a point satisfying
A run that never stops does not succeed. The algorithm retains arbitrary adaptive queries, label reuse, randomized stopping, and arbitrary outputs.
Definition code
import Mathlib
import Definitions.Def_ZOGlobalLB_ZOAlg
import Definitions.Def_ZOGlobalLB_Supplement_goldsteinGauge
namespace ZOGlobalLB
namespace Supplement
/-- A run succeeds at Goldstein `(δ, ε)`-stationarity when it stops and outputs `x` with
`g_δ(x) ≤ ε`, as in Xia--Yuan, arXiv:2610.19652, display (6) and Theorem 2.2, pp.4--5.
A run that never stops does not succeed. -/
def SucceedsGoldstein {d n : ℕ} {Ω : Type*} [MeasurableSpace Ω] (δ ε : ℝ)
(A : ZOAlg d n Ω) (F : Fin n → E d → ℝ) (ω : Ω) : Prop :=
∃ t x, A.outputAt F ω t = some x ∧ goldsteinGauge (popMean F) δ x ≤ ε
end Supplement
end ZOGlobalLB
Source
Xia, Yuan, On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization, arXiv:2610.19652, Eq. (6) and Theorem 2.2, pp.4-5