Theorem 2.5 — two-level gap amplification
OpenZOGlobalLB.Supplement.theorem_2_5lower-boundsoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1zeroth-order-optimization
There are universal constants such that
imply that every randomized adaptive reusable-label algorithm succeeding with probability at least on every admissible instance has expected query cost at least
on some finite family.
Differences from the source:
- encoding: finite labels and expected query cost under the standing oracle convention →
Fin nand an extended-nonnegative lintegral of the published stopping cost; reason: preserves arbitrary reuse and nontermination without changing any instance
Preamble
import Mathlib import Definitions.Def_ZOGlobalLB_Admissible import Definitions.Def_ZOGlobalLB_ZOAlg open MeasureTheory open scoped ENNReal universe u
Formal statement
namespace ZOGlobalLB
namespace Supplement
/-- **Theorem 2.5 (Two-level).** Xia, Yuan,
*On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization*, arXiv:2610.19652,
Theorem 2.5, p.5, (9)--(10).
There are universal positive `c, cε, Cstar, C` such that the three displayed conditions imply
the full two-level expected query lower bound
`c d L₀² / ε⁴ * min {ΔH, L₀⁴/ε²}` for every successful randomized adaptive reusable-label
algorithm.
**Formalization Note.** The quantifier order is universal constants, problem data, algorithm,
then its hard family. The minimum is retained with both branches; no large-gap branch is dropped. -/
theorem theorem_2_5 :
∃ c cε Cstar C : ℝ,
0 < c ∧ 0 < cε ∧ 0 < Cstar ∧ 0 < C ∧
∀ (d : ℕ) (L₀ Δ H ε : ℝ), 0 < L₀ → 0 < Δ → 0 < H → 0 < ε →
ε ≤ cε * L₀ → Cstar * L₀ ^ 2 ≤ Δ * H →
C * (L₀ ^ 2 / ε ^ 2) * Real.log (2 + L₀ ^ 2 / ε ^ 2) ≤ (d : ℝ) →
∀ (Ω : Type u) [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(A : ∀ n : ℕ, ZOAlg d n Ω),
(∀ (n : ℕ) (F : Fin n → E d → ℝ), Admissible Δ H L₀ F →
(2 / 3 : ℝ≥0∞) ≤ μ {ω | (A n).Succeeds ε F ω}) →
∃ (n : ℕ) (F : Fin n → E d → ℝ), Admissible Δ H L₀ F ∧
ENNReal.ofReal
(c * d * L₀ ^ 2 / ε ^ 4 * min (Δ * H) (L₀ ^ 4 / ε ^ 2)) ≤
∫⁻ ω, ((A n).cost F ω : ℝ≥0∞) ∂μ := by sorry
end Supplement
end ZOGlobalLB
Source
Xia, Yuan, On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization, arXiv:2610.19652, Theorem 2.5, p.5, Eqs. (9)-(10)