← All setups

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 F:E→E on a real inner product space E with induced norm ∥⋅∥. For constants L0>0 and L1≥0, the Lipschitz bound along each segment is L0+L1M whenever M bounds the norm of F on that segment. A given point x0∈E satisfies ∥F(x0)∥≤G and lies within distance R of a zero, where G,R≥0. 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. The algorithm receives only E, L0, L1, and x0; the residual bound G, radius R, and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

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

Assumption 2 (Generalized Lipschitz condition). For every x,y∈E and M∈R satisfying ∥F(x+θ(y−x))∥≤Mfor every θ∈[0,1], the operator satisfies ∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

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

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⋅(⌈11⋅L0⋅Rε+(27⋅L1⋅R+4)⋅log⁡(1+8⋅(L0+L1⋅G)⋅Rε)⌉++1)

OracleTemplate.Convergence LongTails.Setups.GeneralizedLipschitzMonotone.spec OracleTemplate.GeneralizedMonotone.budget

Relevant previous results

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