Radius Generalized Monotone — Generalized Lipschitz Monotone Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Generalized Lipschitz Monotone Root Finding · Lean proof
Generalized Lipschitz
Monotone Root Finding
We consider finding a zero of a continuous monotone operator on a real inner product space
. For constants and , its Lipschitz bound along any
segment is whenever bounds on that segment. A given point
is within distance of a zero of . The oracle returns at . For , the goal is an output
with almost
surely under , the law of the
algorithm’s randomness.
The root-finding problem is to find such that Write
for the
inner product on and for its induced norm. The
algorithm receives , , , , and ; the tolerance may enter the oracle-call
budget but is not an algorithm input.
Our assumptions:
Assumption 1 (Continuity and monotonicity). The
operator is continuous on and satisfies
Assumption 2 (Generalized Lipschitz bound). For
every and satisfying we have
Assumption 3 (Initial distance to a zero). There
exists such that
Queries may be made at any point of . After the allotted oracle calls, the
output must satisfy the residual criterion
Proved result
OracleTemplate.Convergence LongTails.Setups.RadiusGeneralizedLipschitzMonotone.spec
OracleTemplate.WarmAnchoredMonotone.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.