← All setups

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 F:E→E on a real inner product space E. For constants L0>0 and L1≥0, its Lipschitz bound along any segment is L0+L1M whenever M bounds ∥F∥ on that segment. A given point x0∈E is within distance R≥0 of a zero x⋆ of F. The oracle returns F(x) at x. For ε>0, the goal is an output x¯∈E with ∥F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The root-finding problem is to find x∈E such that F(x)=0. Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, L0, L1, R, and x0; the tolerance ε may enter the oracle-call budget but is not an algorithm input.

Our assumptions:

Assumption 1 (Continuity and monotonicity). The operator F is continuous on E and satisfies ⟨F(x)−F(y),x−y⟩≥0,x,y∈E.

Assumption 2 (Generalized Lipschitz bound). For every x,y∈E and M∈R satisfying ∥F(x+θ(y−x))∥≤M,θ∈[0,1], we have ∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Initial distance to a zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Proved result

2⋅⌈215⋅(1+L0⋅Rε+(L1⋅R)43)⌉+

OracleTemplate.Convergence LongTails.Setups.RadiusGeneralizedLipschitzMonotone.spec
  OracleTemplate.WarmAnchoredMonotone.budget

Relevant previous results

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