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 -Lipschitz map , where
and . A given point lies within Euclidean distance of a zero satisfying the weak Minty
condition for every , with . The oracle returns
at . For with , the goal is an
output with integrable
residual norm and ,
where is the law of the
algorithm’s randomness.
The root-finding problem is to find such that Throughout, and denote the standard Euclidean
inner product and norm. The algorithm receives , and , with parameter ranges
Our assumptions:
Assumption 1 (Lipschitz continuity). For every ,
Assumption 2 (Weak Minty condition and initial
distance). There exists such that
Queries may be made at any point of . After the allotted oracle
calls, the output must have
integrable residual norm under
and satisfy
Proved result
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.