← All setups

Generalized Lipschitz Monotone Root Finding

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

A continuous monotone map F:E→E on a real inner-product space satisfies ∥F(x)−F(y)∥≤(L0+L1max0≤t≤1∥F(x+t(y−x))∥)∥x−y∥. Here L0>0, L1,G,R≥0, ε>0, ∥F(x0)∥≤G, and some root x⋆ satisfies ∥x0−x⋆∥≤R. The oracle returns exact F(x); the target is ∥F(x)∥≤ε deterministically. The setup imposes no algorithm restriction.

Exact monotone root finding under GeneralizedLipschitzMonotone.
Result Oracle complexity Novelty Limitations
(1) AnchoredGeneralizedMonotone (Ours) (⋆⋆⋆) (review) O(1+L0Rε+(1+L1R)⋅log(1+(L0+L1G)Rε)). Also O(1+L0R/ε+L12R2) using the intrinsic initial-residual bound.
(2) EG (Choudhury and Loizou 2025, Thm. 3.6) O(1+L02R2/ε2+L12R2). E=Rd. (1): L0R/ε instead of (L0R/ε)2; speedup Θ(L0R/ε) if ε≤min{L0R,L0/(L12R)}. Scope: arbitrary real inner-product spaces. For L0=L1=1, R=10, ε=10−3: O(104) versus O(108).
(3) PolyakEG (Yoon et al. 2026, Thm. 3.4, Eq. (19)) O(1+L02R2/ε2+L12R2). Known L0,L1; E=Rd. (1): same leading-term gain as against (2). If L1>0 and L0/(L12R)≤ε≤L0/L1, speedup Ω((L0/(L1ε))2). For ε≥L0/L1, moderate G gives L1Rlog⁡(2+L1R+L0R/ε) instead of L12R2; otherwise no strict gain is assured.
(4) PolyakEG-LS (Yoon et al. 2026, Thm. 3.4, Prop. 3.5(a)) Derived bound: O(1+B+(λ¯0)2R2ε2+(λ¯1)2R2), including all trials. E=Rd; fixed A∈(0,1), β>2, positive initial estimates λ0,λ1. (1): ε−1 instead of ε−2 for fixed remaining parameters; no backtracking calls. Last iterate instead of minimum residual among observed iterates. (1) needs L0,L1 in its updates; (4) does not.
(5) FEG / EAG (Lee and Kim 2021, Thm. 4.1, ρ=0)(Yoon and Ryu 2021, Thms. 1–2, Sec. 2.3) O(1+L0R/ε). Special case: L1=0, E=Rd. (1) matches the known rate on this overlap; scope extends to generalized Lipschitz continuity with L1>0. (1) has a roughly fivefold larger leading cost constant than FEG when L1=0.

Abbr: Costs count individual F-evaluations. R: initial root-distance bound; G: initial residual bound; ε: residual tolerance. The intrinsic bound is ∥F(x0)∥≤L0ReL1R, so G may be replaced by min{G,L0ReL1R}. Moderate G means log⁡(1+L1G/L0)=O(log⁡(2+L1R)). For (4), A is the fixed acceptance tolerance, β the backtracking factor, λi the initial estimates, B=2max{0,⌈log⁡(L0/λ0)/log⁡(β−1)⌉,⌈log⁡(L1/λ1)/log⁡(β−1)⌉}, and λ¯i=βB/2λi; omit the L1 logarithm when L1=0. In (2), interpret L0/(L12R)=+∞ if L1R=0.

Choudhury, Sayantan, and Nicolas Loizou. 2025. Extragradient Method for (L0,L1)-Lipschitz Root-Finding Problems. https://doi.org/10.48550/arXiv.2510.22421.
Lee, Sucheol, and Donghwan Kim. 2021. Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems. https://doi.org/10.48550/arXiv.2106.02326.
Yoon, TaeHo, Sayantan Choudhury, Ezra Greenberg, and Nicolas Loizou. 2026. Polyak-Type Extragradient Methods for Monotone Root-Finding Problems. https://doi.org/10.48550/arXiv.2609.26581.
Yoon, TaeHo, and Ernest K. Ryu. 2021. Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm. https://doi.org/10.48550/arXiv.2102.07922.

Lean setup