← All setups

Cohypomonotone Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Cohypomonotone Root Finding

We consider finding a zero of a differentiable map F:E→E on a finite-dimensional real inner product space E. The map is ρ-cohypomonotone, where ρ≥0, and its derivative J(x)=DF(x) is H-Lipschitz in operator norm, where H>0. A given starting point x0∈E lies within distance R>0 of a zero x⋆ of F. The oracle returns (F(x),J(x)) at x. For a tolerance ε>0, the goal is an output x¯∈E satisfying ∥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 and ∥⋅∥ for its induced norm; ∥⋅∥op denotes the induced operator norm for linear maps from E to E. The algorithm receives E, H, ρ, R, ε, and x0.

Our assumptions:

Assumption 1 (Lipschitz derivative). The map F is Fréchet differentiable everywhere on E, with derivative J(x):E→E, and ∥J(x)−J(y)∥op≤H∥x−y∥,x,y∈E.

Assumption 2 (Cohypomonotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥−ρ∥F(x)−F(y)∥2.

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, and both components of the oracle reply are exact. After the allotted oracle calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, F is differentiable, ∥DF(x)−DF(y)∥≤H∥x−y∥, and ⟨F(x)−F(y),x−y⟩≥−ρ∥F(x)−F(y)∥2. A root x⋆ satisfies ∥x0−x⋆∥≤R, with H,R,ε>0 and ρ≥0. Exact paired (F,DF) queries are available. The target is ∥F(xout)∥≤ε almost surely; (1) holds for every seed.

Cohypomonotone equations with a Lipschitz Jacobian (CohypomonotoneNewton).
Result Oracle complexity Novelty Limitations
(1) CohypomonotoneNewtonAcceleration (Ours) (⋆⋆⋆) (review) O([(1+ρHR)2+(1+Q)2/5]ℓ2) paired value–Jacobian calls, including initialization and rejected trials.
(2) (Jiang and Yoon 2026), Theorems 4.4, 4.6 O((1+Q2/5)[1+log⁡(1+Q)]) value–Jacobian calls; monotone restriction ρ=0. (1): Scope extends to arbitrary ρ≥0, with additive (1+ρHR)2 overhead. At ρ=0, matches the optimal polynomial exponent up to logarithms. (1): One extra logarithm at ρ=0; does not cover composite inclusions supported by (2).
(3) FEG (Lee and Kim 2021), Theorem 4.1 O(1+LR(1−2ρL)ε) value calls; F globally L-Lipschitz, ρL<1/2. (1): Removes global Lipschitzness and the ρL restriction. For L=H=R=1, ρ=1/4, calls become O(ε−2/5log2⁡(1/ε)) versus O(ε−1) as ε→0. (1): Needs an H-Lipschitz Jacobian and full-Jacobian queries; (3) uses only values. Call counts are different cost units.
(4) Adjoint acceleration (LongTails, n.d.) O((1+ρL+LR/ε)log⁡(2+ρL)+(1+ρL)5log⁡(2+ρL)⋅(HR/L)log2⁡(2+LR/ε)) total value and vector–Jacobian-product calls; F globally L-Lipschitz. (1): Removes global Lipschitzness. At L=H=R=ρ=1, calls become O(ε−2/5log2⁡(1/ε)) versus O(ε−1) as ε→0. (1): Full Jacobians instead of products. At L=R=ρ=1, H=M, ε=M−1, costs O(M2log2⁡M) versus O(Mlog2⁡M).

Abbr: Q=HR2/ε; ℓ=1+log⁡(1+ρHR+Q); L>0 is an operator-Lipschitz constant where required; DF is the Jacobian. All costs count primitive oracle calls, including search trials.

Jiang, Ruichen, and TaeHo Yoon. 2026. Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems. https://doi.org/10.48550/arXiv.2609.30212.
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.
LongTails: AdjointAcceleratedCohypomonotone. n.d. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AdjointAcceleratedCohypomonotone.lean.

Lean setup