← All setups

Generalized Lipschitz Monotone Root Finding

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Let F:E→E be continuous and monotone on a real inner-product space, with L0>0, L1≥0, R≥0. For every x,y,M, if ∥F(x+θ(y−x))∥≤M for all θ∈[0,1], then ∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥. A root x⋆ satisfies ∥x0−x⋆∥≤R. Access is to exact evaluations of F; the target is ∥F(x)∥≤ε, ε>0. No initial-residual bound is supplied.

Residual complexity for RadiusGeneralizedLipschitzMonotone.
Result Oracle complexity Novelty Limitations
(1) RadiusGeneralizedMonotone (Ours) (⋆⋆⋆) (review) O(1+L0Rε+(L1R)4/3)
(2) EG (Choudhury and Loizou 2025, Theorem 3.6); past-EG (Greenberg and Loizou 2026, Corollary 3.3). Unconstrained Rd. O(1+(L0Rε)2+(L1R)2) (1): A2→A, C2→C4/3; speedup Θ((1+A2+C2)/(1+A+C4/3)). Last iterate instead of minimum residual. Scope: arbitrary real inner-product spaces. (1) needs R in updates in addition to L0,L1.

Abbr: A=L0R/ε, C=L1R; costs count all exact F evaluations, including two per EG step and one new evaluation per past-EG step. O suppresses universal constants. The guarantee in (1) is deterministic.

Choudhury, Sayantan, and Nicolas Loizou. 2025. Extragradient Method for (L0,L1)-Lipschitz Root-Finding Problems. https://doi.org/10.48550/arXiv.2510.22421.
Greenberg, Ezra, and Nicolas Loizou. 2026. Extragradient and Past Extragradient Methods for (L0,L1)-Lipschitz Variational Inequalities. https://doi.org/10.48550/arXiv.2610.16886.

Lean setup