Theorem 3.1 — th-order trapping from function values
OpenHOTrap.Supplement.theorem_3_1higher-order-smoothnessnonconvex-optimizationoptimizationoracle-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , , , and let . For every and every , there is a deterministic strict value-only trapping algorithm using adaptive rounds such that:
- In the unconstrained problem with the known lower bound , given and with , it returns with and uses value queries per round.
- On , for a fixed , it returns with and uses value queries per round.
The algorithm receives exact function values only; it has no gradient, mixed, or higher-derivative oracle.
Differences from the source:
- encoding: asymptotic and bounds for → explicit uniform constants with and ; reason: this extends the same small- asymptotics to all positive accuracies without a negative round bound
- encoding: → is fixed before the complexity constant and satisfies ; reason: quantifier order is the formal content of fixed dimension
- encoding: → for every ; reason: equivalent for lower-bounded and avoids the junk value of a real infimum
- encoding: with exact value-only adaptive rounds →
EuclideanSpace ℝ (Fin d)and a response-typed fixed-budget batched structure; reason: zero-based finite coordinates preserve Euclidean geometry, and shorter executions can be padded without changing oracle power
Preamble
import Mathlib import Definitions.Def_GeomDRSub_cube import Definitions.Def_HOTrap_HolderClass import Definitions.Def_HOTrap_projGrad import Definitions.Def_HOTrap_Supplement_StrictBatchAlg
Formal statement
namespace HOTrap.Supplement
/-- **Theorem 3.1 (p-th order trapping via function value oracle).**
Zhou--Sugiyama--Suzuki, *Finding Stationary Points under Higher-Order Smoothness: Trapping
Algorithms and First-Order Lower Bounds*, arXiv:2610.02791, Theorem 3.1, p.14.
For fixed `d ≥ 2`, a deterministic strict value-only algorithm uses logarithmically many adaptive
rounds and `O(ε^{-(d-1)})` queries per round in the lower-bounded unconstrained problem, or
`O(ε^{-(d-1)/(p+β)})` queries per round on the cube, and returns the stated stationary/KKT point.
**Formalization Note.** `C` may depend on the fixed `d,p,β,L,Δ,γ`, but not on `ε`, the objective,
or its answers. `max 1` and `1 + max 0 log(1/ε)` extend the asymptotic bounds harmlessly to all
`ε > 0`. The unconstrained lower-bound/gap convention is written shift-invariantly as
`∀ y, f x₀ - f y ≤ Δ`. The cube's `ε`-stationarity is the fixed-`γ` KKT convention of Section 2.
The response type `ℝ` prevents the algorithm from seeing gradients or higher derivatives. -/
theorem theorem_3_1 (d p : ℕ) (hd : 2 ≤ d) (hp : 1 ≤ p) (β L Δ γ ν : ℝ)
(hβ0 : 0 < β) (hβ1 : β ≤ 1) (hL : 0 ≤ L) (hΔ : 0 < Δ) (hγ : 0 < γ)
(hν : ν = (p : ℝ) + β) :
∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ, 0 < ε →
(∀ x₀ : EuclideanSpace ℝ (Fin d),
∃ A : StrictBatchAlg d ℝ Unit,
(∀ r < A.rounds,
(A.batch r : ℝ) ≤ C * max 1 (Real.rpow ε (-((d : ℝ) - 1)))) ∧
(A.rounds : ℝ) ≤ C * (1 + max 0 (Real.log (1 / ε))) ∧
∀ f : EuclideanSpace ℝ (Fin d) → ℝ, HOTrap.HolderClass p β L f →
(∀ x, 0 ≤ f x) → (∀ y, f x₀ - f y ≤ Δ) →
‖gradient f (A.run f ())‖ ≤ ε) ∧
(∃ A : StrictBatchAlg d ℝ Unit,
(∀ r < A.rounds,
(A.batch r : ℝ) ≤
C * max 1 (Real.rpow ε (-(((d : ℝ) - 1) / ν)))) ∧
(A.rounds : ℝ) ≤ C * (1 + max 0 (Real.log (1 / ε))) ∧
∀ f : EuclideanSpace ℝ (Fin d) → ℝ, HOTrap.HolderClass p β L f →
A.run f () ∈ GeomDRSub.cube d ∧ ‖HOTrap.projGrad f γ (A.run f ())‖ ≤ ε) := 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 3.1, p.14