Theorem 6.1 — randomized exact first-order lower bound
OpenHOTrap.Supplement.theorem_6_1lower-boundsnonconvex-optimizationoptimizationoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms
For every integer , there is such that for all there is a finite constant with the following property. If
and , then
The oracle returns exact values and gradients, its budget holds for every input and seed, terminal outputs may be arbitrary transcript-measurable points, and success means probability at least .
Differences from the source:
- encoding: a real lower bound on integer query complexity → its natural-number ceiling is below the -valued complexity; reason: this is equivalent and avoids fractional query counts and empty-infimum junk values
- 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: in the hard class → for every ; reason: equivalent under the class's nonnegativity condition and avoids a default-valued real infimum
- 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.1 (randomized first-order lower bound).** Zhou--Sugiyama--Suzuki,
*Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order
Lower Bounds*, arXiv:2610.02791, Theorem 6.1, p.37 (PDF p.40), Eq. (28).
**Formalization Note.** `c` depends only on `p`; `C` is quantified after `Δ,L₁,L_p` but before
`ε,d`, so it has exactly the printed dependencies. Since oracle complexity is integer-valued, the
real lower bound is converted with the natural ceiling. `randFOComplexity` includes exact values
and gradients, Borel transcript rules, an arbitrary transcript-measurable output, an every-seed
budget, and the inner success probability `2/3`. -/
theorem theorem_6_1 (p : ℕ) (hp : 2 ≤ p) :
∃ c : ℝ, 0 < c ∧ ∀ Δ L₁ Lp : ℝ, 0 < Δ → 0 < L₁ → 0 < Lp →
∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ,
0 < ε →
ε ≤ c * min (Real.sqrt (Δ * L₁))
(Real.rpow Δ ((p : ℝ) / ((p : ℝ) + 1)) *
Real.rpow Lp (1 / ((p : ℝ) + 1))) →
∀ d : ℕ,
C * Real.rpow ε (-(4 + 2 / (p : ℝ))) ≤ (d : ℝ) →
((⌈c * Δ * Real.sqrt (L₁ * effectiveCurvature p L₁ Lp ε) *
Real.rpow ε (-2)⌉₊ : ℕ) : WithTop ℕ) ≤
randFOComplexity d (HardClass1p d p Δ L₁ 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.1, p.37, Eq. (28)