Nonsmooth stochastic class for the Goldstein lower bound
DefinitionZOGlobalLB_Supplement_GoldsteinAdmissiblelower-boundsnonsmooth-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1zeroth-order-optimization
A nonempty finite family is admissible for the stochastic Goldstein theorem when its population mean is globally Lipschitz and bounded below, satisfies , and
The population objective may be nonsmooth; no differentiability or -smoothness is imposed.
Formalization Note The finite label set is Fin n. Extended nonnegative Lipschitz constants ensure that non-Lipschitz samples cannot pass through a default real supremum.
Definition code
import Mathlib
import Definitions.Def_ZOGlobalLB_Admissible
import Definitions.Def_ZOGlobalLB_lipConst
open scoped ENNReal
namespace ZOGlobalLB
namespace Supplement
/-- The nonsmooth stochastic class of Theorem 2.2 in Xia--Yuan,
*On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization*,
arXiv:2610.19652, p.5: a nonempty finite sample family whose population mean is globally
Lipschitz (but need not be differentiable), is bounded below with initial gap at most `Δ`, and
whose average squared sample Lipschitz constants is at most `L₀²`.
**Formalization Note.** This is deliberately not the published smooth class `Admissible`: no
differentiability or `H`-smoothness is imposed. The finite label set is `Fin n`, and `lipConst`
takes values in `ℝ≥0∞`, so non-Lipschitz functions cannot pass through a junk real supremum. -/
def GoldsteinAdmissible {d n : ℕ} (Δ L₀ : ℝ) (F : Fin n → E d → ℝ) : Prop :=
0 < n ∧
BddBelow (Set.range (popMean F)) ∧
popMean F 0 - ⨅ x, popMean F x ≤ Δ ∧
(n : ℝ≥0∞)⁻¹ * ∑ i, lipConst (F i) ^ 2 ≤ ENNReal.ofReal (L₀ ^ 2)
end Supplement
end ZOGlobalLB
Source
Xia, Yuan, On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization, arXiv:2610.19652, Theorem 2.2, p.5