← All setups

Monotone Root Finding with Jacobians

Descriptions may be stale. Consult the linked Lean sources.

Monotone Root Finding with Jacobians

We consider finding a zero of a differentiable monotone map F:Rd→Rd, where d is a nonnegative integer and the space has its Euclidean inner product and norm. Its Jacobian JF is globally L-Lipschitz, with L>0, and a given point x0 lies within distance R>0 of a zero x⋆. The oracle returns (F(x),JF(x)) at x. For a tolerance ε>0, the goal is an output x¯ satisfying EP[∥F(x¯)∥]≤ε, where P is the law of the algorithm’s randomness.

The root-finding problem is find x∈Rd such that F(x)=0. The algorithm receives d, x0, L, R, and ε. Write JF(x) for the Fréchet derivative of F at x, a linear operator from Rd to itself; ∥⋅∥op denotes its induced operator norm.

Our assumptions:

Assumption 1 (Parameter regime). The positive parameters L, R, and ε, and the dimension d, satisfy 4096ε≤LR2,d≥4096(⌊(LR24096ε)2/5⌋+2)5.

Assumption 2 (Monotonicity and Jacobian regularity). The map F is Fréchet differentiable everywhere, and for every x,y∈Rd, ⟨F(x)−F(y),x−y⟩≥0,∥JF(x)−JF(y)∥op≤L∥x−y∥.

Assumption 3 (Nearby zero). There exists x⋆∈Rd such that F(x⋆)=0,∥x0−x⋆∥≤R.

Queries may be made at any point of Rd, and each oracle call returns both the exact map value and the exact Jacobian. After the allotted calls, the output must have an integrable residual norm and satisfy EP[∥F(x¯)∥]≤ε.

Results

Monotone differentiable F:Rd→Rd with L-Lipschitz Jacobian and a zero x⋆ satisfying ∥x0−x⋆∥≤R. Exact joint queries return (F(x),DF(x)) anywhere in Rd; randomized adaptive algorithms and arbitrary output rules are allowed. The target is integrable residual with ∫∥F(x^(ω))∥dP(ω)≤ε, where P is the algorithm’s seed law. Parameters satisfy L,R,ε>0, LR2≥4096ε, and d≥4096(⌊(LR2/(4096ε))2/5⌋+2)5.

Necessary oracle budgets for randomized monotone root finding: GlobalJacobianMonotoneExpected.
Result Oracle complexity Novelty Limitations
(1) RandomizedGlobalJacobianMonotoneLowerBound (Ours) (⋆⋆) (review) Necessary: Ω((LR2/ε)2/5) joint calls. Hard instance fixed before the seed.
(2) (Jiang and Yoon 2026), Thm. 6.1, p=2 Necessary: Ω((LR2/ε)2/5) joint calls; deterministic algorithms, global residual; d≥2N+1. (1): Scope: randomized adaptive algorithms instead of deterministic algorithms, with unrestricted queries. Matches the lower-bound exponent. (1): Dimension scales as N5 instead of N.
(3) (Zhang et al. 2026), Thm. 11.3, p=2 Necessary: Ω((LD2/ε)2/5) joint calls. Queries and output confined to a ball of diameter D; tangent-residual failure probability ≥3/4; dimension O(N3log⁡(N+2)). (1): Scope: unrestricted queries and global residual. Same exponent; D=2R in the ball construction. No direct transfer to unrestricted queries. (1): Dimension scales as N5 instead of N3log⁡(N+2); expectation failure is weaker than constant-probability failure.
(4) (Garg et al. 2021), Thm. 1, p=2 Necessary: Ω(Qf2/7/(1+log⁡Qf)2/3), Qf=LR3/εf≥2. Convex minimization on a radius-R ball; queries return (f,∇f,∇2f); function-value error εf. (1): Exponent 2/5 for general monotone equations, versus 2/7 for convex minimization. No stronger convex-subclass bound; different criteria make rates incomparable. (1): residual-to-value conversion requires bounded outputs, absent from the target setup.

Abbr: N: tested query budget; L: Jacobian Lipschitz constant (Hessian Lipschitz constant in (4)); R: initial distance bound (optimization-ball radius in (4)); D: feasible-ball diameter; εf: function-value tolerance; Qf=LR3/εf. Ω: necessary budget up to universal factors; dimension scalings describe sufficient dimensions for the hard constructions.

Garg, Ankit, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. 2021. Near-Optimal Lower Bounds for Convex Optimization for All Orders of Smoothness. https://doi.org/10.48550/arXiv.2112.01118.
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.
Zhang, Haihan, Wendao Wu, Chenheng Zhang, Cong Fang, Haoxuan Li, and Zhouchen Lin. 2026. Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities. https://doi.org/10.48550/arXiv.2609.13462.

Lean setup