Anchored 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 seek a zero of a continuous monotone operator on a real inner product space
with induced norm . For constants and , the Lipschitz bound along each
segment is whenever bounds the norm of on that segment. A given point satisfies and lies within distance
of a zero, where . 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 . The algorithm
receives only , , , and ; the residual bound , radius , and tolerance may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Continuity and monotonicity). The
operator is continuous, and for
every ,
Assumption 2 (Generalized Lipschitz condition). For
every and satisfying the operator satisfies
Assumption 3 (Initial residual and distance). 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.GeneralizedLipschitzMonotone.spec OracleTemplate.GeneralizedMonotone.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.