← All setups

Euclidean Weak Minty Lower Bound — Euclidean Weak Minty Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Euclidean Weak Minty Root Finding · Lean proof

Euclidean Weak Minty Root Finding

We consider finding a zero of an L-Lipschitz map F:Rd→Rd, where d≥257 and L>0. A given point x0 lies within Euclidean distance R>0 of a zero x⋆ satisfying the weak Minty condition ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2 for every x, with 0≤ρ≤1/(20L). The oracle returns F(x) at x. For ε>0 with 28ε≤LR, the goal is an output x¯ with integrable residual norm and EP∥F(x¯)∥≤ε, where P is the law of the algorithm’s randomness.

The root-finding problem is to find x∈Rd such that F(x)=0. Throughout, ⟨⋅,⋅⟩ and ∥⋅∥ denote the standard Euclidean inner product and norm. The algorithm receives d,L,ρ,x0,R, and ε, with parameter ranges d∈N,d≥257,L>0,0≤ρ≤120L,R>0,ε>0,28ε≤LR.

Our assumptions:

Assumption 1 (Lipschitz continuity). For every x,y∈Rd, ∥F(x)−F(y)∥≤L∥x−y∥.

Assumption 2 (Weak Minty condition and initial distance). There exists x⋆∈Rd such that F(x⋆)=0,∥x⋆−x0∥≤R,⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2for every x∈Rd.

Queries may be made at any point of Rd. After the allotted oracle calls, the output x¯∈Rd must have integrable residual norm under P and satisfy EP[∥F(x¯)∥]≤ε.

Proved result

⌊min{(L⋅R28⋅ε)2,(d257)13}⌋+−1

OracleTemplate.NonConvergence LongTails.Setups.EuclideanWeakMinty.spec
  LongTails.Theorems.EuclideanWeakMintyLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.