← All setups

Monotone Equations with Inexact Jacobians

Descriptions may be stale. Consult the linked Lean sources.

Monotone Equations with Inexact 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 is M-Lipschitz in operator norm, with M>0, and a given point x0∈E lies within distance R>0 of a zero. At a query x∈E, the oracle returns F(x) and a linear approximation to its Jacobian with operator-norm error at most δ≥0. For ε>0, the goal is an output x¯∈E satisfying ∥F(x¯)∥≤ε almost surely under P, the joint law of algorithm and oracle randomness.

The equation to solve is F(x)=0,x∈E. Write JF(x):E→E for the Fréchet derivative of F at x. The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, M, δ, R, and ε.

Our assumptions:

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

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

Assumption 3 (Inexact Jacobian oracle). Queries may be made at any x∈E. Each oracle call returns a pair (v,A), where v∈E and A:E→E is linear, satisfying v=F(x),∥A−JF(x)∥op≤δ. These conditions hold for every query history and every realization of the oracle randomness. The approximate Jacobian may depend on both. Algorithm randomness is independent of oracle randomness.

After the allotted oracle calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Results

F:E→E is differentiable and monotone on a finite-dimensional real inner-product space, with ∥DF(x)−DF(y)∥≤M∥x−y∥ and a root x⋆ satisfying ∥x0−x⋆∥≤R. Each call returns exact F(x) and J satisfying ∥J−DF(x)∥≤δ, allowing history-dependent adversarial errors. Here M,R,ε>0, δ≥0. The target is ∥F(output)∥≤ε almost surely; (1) guarantees it pathwise and uses known M,δ,R,ε.

Comparison for InexactJacobianMonotone.
Result Oracle complexity Novelty Limitations
(1) OptimalInexactJacobianMonotone (Ours) (⋆⋆) (review) O(1+(MR2/ε)2/5+δR/ε) combined calls.
(2) (Jiang and Yoon 2026), Thms. 4.4, 4.6 O((1+(MR2/ε)2/5)
⋅(1+log⁡(1+MR2/ε))) exact second-order calls, including trials; δ=0.
(1): removes a logarithmic factor for δ=0, MR2/ε≫1. Scope: permits δ>0, adding δR/ε. (1) covers equations only; (2) also covers composite inclusions with tangent residual.
(3) (Zhang et al. 2026), Thm. 3.1 (p=2) O(1+(MR2/ε)2/5) exact second-order calls; compact convex X, tangent residual ≤ε, δ=0. (1): full-space residual with inexact Jacobians. Rates not comparable: compact-domain tangent residual does not establish the full-space target. (1) does not cover constrained VIs.
(4) VIJI (Agafonov et al. 2024), Thm. 3.2 O(1+(MD3/ε)2/3+δD2/ε) combined calls; bounded closed convex X, Minty gap ≤ε. Model subproblems require additional computation. (1): unbounded-domain, last-iterate norm residual instead of averaged Minty gap. Rates not comparable: different criteria and diameter versus root distance. (1) does not cover constrained VIs or provide quasi-Newton instantiations.

Abbr: DF: Jacobian; M: Jacobian Lipschitz constant; δ: Jacobian error bound; R: initial distance bound (to a VI solution in (3)); D=diam(X); VI: variational inequality. Tangent residual: dist(0,F(x)+NX(x)), with NX the normal cone. Minty gap: supz∈X⟨F(z),x−z⟩. Combined call: one F-value and one Jacobian approximation; arithmetic and model solves are not oracle calls.

Agafonov, Artem, Petr Ostroukhov, Roman Mozhaev, et al. 2024. Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations. https://arxiv.org/abs/2405.15990v2.
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