← All setups

Monotone Equations with Lipschitz Jacobians

Descriptions may be stale. Consult the linked Lean sources.

Monotone Equations with Lipschitz Jacobians

We consider finding a zero of a differentiable monotone map F:E→E on a finite-dimensional real inner product space E. Its Jacobian F′ is L-Lipschitz in operator norm, where L≥0, and a given point x0∈E lies within distance D>0 of a zero x⋆. Two exact oracles return F(x) and F′(x), respectively, at x∈E. 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 equation to be solved is F(x)=0,x∈E. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The Jacobian F′(x):E→E is the Fréchet derivative, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, L, D, ε, and an integer parameter m≥1.

Our assumptions:

Assumption 1 (Monotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥0.

Assumption 2 (Lipschitz Jacobian). The map F is Fréchet differentiable everywhere on E, and ∥F′(x)−F′(y)∥op≤L∥x−y∥,x,y∈E.

Assumption 3 (Initial distance to a zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤D.

Both oracles accept queries at any point of E. Calls to the map oracle and the Jacobian oracle are counted separately. After the allotted 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 and monotone, with globally L-Lipschitz Jacobian and a zero x⋆ satisfying ∥x0−x⋆∥≤D. Exact value and Jacobian oracles are available; L≥0, D,ε>0, and integer m≥1. The target is ∥F(z)∥≤ε (deterministically for our construction).

Comparison for UnconstrainedLipschitzJacobianMonotone.
Result Oracle complexity Novelty Limitations
(1) LazyAnchoredExtraProximal (Ours) (⋆⋆⋆) (review) O((m+m3/5T2/5)ℓ2)
(2) AEP Newton (Jiang and Yoon 2026), Thms. 4.4, 4.6; H=0, L>0 O(m(1+T2/5)[1+log⁡(1+T)]) (1): polynomial cost factor min(m,T)2/5 before logarithms; for T≥m, gain m2/5/ℓ. (1): more value calls; extra logarithm at m=O(1); needs D,m additionally; lacks composite-inclusion scope.
(3) Derived bound (Zhang et al. 2026), Thm. 3.1 (p=2); ball reduction O(m(1+T2/5)); tangent tolerance ε/4 on B(x0,2D) gives residual tolerance ε. (1): cost gain m2/5/ℓ2 when T≥m, if this factor exceeds one. (1): logarithmic overhead; does not cover constrained VIs.
(4) LEN (Chen et al. 2025), Thm. 4.1; convex–concave minimax only O(m+m2/3(LD3/εg)2/3) for averaged restricted gap εg. (1): general monotone scope; last-iterate residual. If ∥zN−x⋆∥=O(D), setting ε=εg/O(D) gives gap cost O((m+m3/5(LD3/εg)2/5)ℓ2). (1): gap conversion requires an output-distance bound absent from its statement; conversion is one-way.

Abbr: T=LD2/ε, ℓ=1+log⁡(m+m3/5T2/5); costs are #F+m#DF, including trials. DF denotes the Jacobian; m is its price and our tuning input. εg denotes restricted saddle-gap accuracy; in (4), evaluate ℓ at the stated residual tolerance. H denotes the composite set-valued operator; B(x,r) is the closed ball.

Chen, Lesi, Chengchang Liu, and Jingzhao Zhang. 2025. Second-Order Min-Max Optimization with Lazy Hessians. https://arxiv.org/abs/2410.09568v2.
Jiang, Ruichen, and TaeHo Yoon. 2026. Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems. https://arxiv.org/abs/2609.30212v1.
Zhang, Xinliang, Lesi Chen, Linxuan Pan, Chengchang Liu, Junchi Yang, and Jingzhao Zhang. 2026. Optimal High-Order Methods for Solving Monotone Variational Inequalities. https://arxiv.org/abs/2609.23557v1.

Lean setup