Theorem 6.5 — randomized lower bounds without gradient Lipschitzness
OpenHOTrap.Supplement.theorem_6_5lower-boundsnonconvex-optimizationoptimizationoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms
For every integer , there are constants such that, whenever
the following hold.
- If and , then
- If and , then
In both branches the hard functions may be chosen and coercive.
Differences from the source:
- encoding: real lower bounds on integer query complexity → their natural-number ceilings are below the -valued complexities; reason: equivalent and avoids fractional query counts
- encoding: “the hard functions may be chosen and coercive” → each lower bound is also stated for the smooth coercive subclass; reason: complexity of that subclass is the exact minimax content of the sentence
- encoding: in the hard class → for every ; reason: equivalent under the class's nonnegativity condition and avoids a default-valued real infimum
- encoding: probability of the stationarity event → a measurable inner event of successful seeds with probability at least ; reason: equivalent for the continuous hard class and makes measurability explicit
- encoding: functions on → functions on
EuclideanSpace ℝ (Fin d); reason: zero-based finite coordinates carry the same Euclidean norm and derivative structure
Preamble
import Mathlib import Definitions.Def_HOTrap_Supplement_RandomFOAlg import Definitions.Def_HOTrap_Supplement_effectiveCurvature
Formal statement
namespace HOTrap.Supplement
/-- **Theorem 6.5 (lower bounds without gradient Lipschitzness).**
Zhou--Sugiyama--Suzuki, *Finding Stationary Points under Higher-Order Smoothness: Trapping
Algorithms and First-Order Lower Bounds*, arXiv:2610.02791, Theorem 6.5, p.38 (PDF p.41).
Both printed branches are stated, including their dimension thresholds. The parallel bounds for
`SmoothCoercivePart` formalize the theorem's final sentence that the hard functions may be chosen
`C^∞` and coercive.
**Formalization Note.** `c,C` are before every problem parameter and depend only on `p`. Natural
ceilings express real lower bounds for the integer query complexity without weakening them. -/
theorem theorem_6_5 (p : ℕ) (hp : 2 ≤ p) :
∃ c C : ℝ, 0 < c ∧ 0 < C ∧
∀ Δ Lp ε : ℝ, 0 < Δ → 0 < Lp → 0 < ε →
ε ≤ c * Real.rpow Δ ((p : ℝ) / ((p : ℝ) + 1)) *
Real.rpow Lp (1 / ((p : ℝ) + 1)) →
(p = 2 → ∀ d : ℕ,
C * Real.rpow
((Real.rpow Δ (2 / 3 : ℝ) * Real.rpow Lp (1 / 3 : ℝ)) / ε) 5 ≤ (d : ℝ) →
((⌈c * Real.rpow
((Real.rpow Δ (2 / 3 : ℝ) * Real.rpow Lp (1 / 3 : ℝ)) / ε)
(7 / 4 : ℝ)⌉₊ : ℕ) : WithTop ℕ) ≤
randFOComplexity d (HardClassP d 2 Δ Lp) ε ∧
((⌈c * Real.rpow
((Real.rpow Δ (2 / 3 : ℝ) * Real.rpow Lp (1 / 3 : ℝ)) / ε)
(7 / 4 : ℝ)⌉₊ : ℕ) : WithTop ℕ) ≤
randFOComplexity d (SmoothCoercivePart (HardClassP d 2 Δ Lp)) ε) ∧
(3 ≤ p → ∀ d : ℕ,
C * Real.rpow
((Real.rpow Δ ((p : ℝ) / ((p : ℝ) + 1)) *
Real.rpow Lp (1 / ((p : ℝ) + 1))) / ε)
(13 / 3 + 1 / (p : ℝ)) ≤ (d : ℝ) →
((⌈c * Real.rpow
((Real.rpow Δ ((p : ℝ) / ((p : ℝ) + 1)) *
Real.rpow Lp (1 / ((p : ℝ) + 1))) / ε) (5 / 3 : ℝ)⌉₊ : ℕ) :
WithTop ℕ) ≤ randFOComplexity d (HardClassP d p Δ Lp) ε ∧
((⌈c * Real.rpow
((Real.rpow Δ ((p : ℝ) / ((p : ℝ) + 1)) *
Real.rpow Lp (1 / ((p : ℝ) + 1))) / ε) (5 / 3 : ℝ)⌉₊ : ℕ) :
WithTop ℕ) ≤
randFOComplexity d (SmoothCoercivePart (HardClassP d p Δ Lp)) ε) := by sorry
end HOTrap.Supplement
Source
Zhou–Sugiyama–Suzuki, Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds, arXiv:2610.02791, Theorem 6.5, p.38