Theorem 2.7 — logarithmic dependence on the global gap
OpenZOGlobalLB.Supplement.theorem_2_7lower-boundsoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1zeroth-order-optimization
There are universal positive constants and such that, if , , and
then every successful randomized adaptive reusable-label algorithm has expected cost at least
on some admissible finite family.
Differences from the source:
- encoding: the floor-defined positive nesting depth → one plus Lean's natural floor of the same nonnegative real ratio; reason: and make the two floors identical
- encoding: finite labels and expected query cost →
Fin nand an extended-nonnegative lintegral of the published stopping cost; reason: preserves label reuse and nontermination
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.7 (Logarithmic gap).** Xia, Yuan,
*On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization*, arXiv:2610.19652,
Theorem 2.7, p.6, (12)--(13).
There are universal positive `c, cε, C₀, C` and `C₁ > 1` such that, for the exact nesting
depth `K = 1 + floor(log(ΔH/(C₀L₀²))/log C₁)`, the printed conditions imply the expected query
lower bound `c d L₀⁴ ε⁻⁴ [1 + log(ΔH/(C₀L₀²))]`.
**Formalization Note.** `⌊·⌋₊` is the natural floor; the large-gap and `C₁ > 1` hypotheses make
its argument nonnegative. The `log(2K)` term and the complete logarithmic factor in the conclusion
are both retained. -/
theorem theorem_2_7 :
∃ c cε C₀ C C₁ : ℝ,
0 < c ∧ 0 < cε ∧ 0 < C₀ ∧ 0 < C ∧ 1 < C₁ ∧
∀ (d : ℕ) (L₀ Δ H ε : ℝ), 0 < L₀ → 0 < Δ → 0 < H → 0 < ε →
ε ≤ cε * L₀ → C₀ * L₀ ^ 2 ≤ Δ * H →
let K : ℕ := 1 + ⌊Real.log (Δ * H / (C₀ * L₀ ^ 2)) / Real.log C₁⌋₊
C * ((L₀ ^ 2 / ε ^ 2) * Real.log (2 + L₀ ^ 2 / ε ^ 2) +
Real.log (2 * K)) ≤ (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₀ ^ 4 / ε ^ 4 *
(1 + Real.log (Δ * H / (C₀ * L₀ ^ 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.7, p.6, Eqs. (12)-(13)