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
The equation to solve is
Our assumptions:
Assumption 1 (Monotonicity and Jacobian regularity).
The map
Assumption 2 (Nearby zero). There exists
Assumption 3 (Inexact Jacobian oracle). Queries may
be made at any
After the allotted oracle calls, the output must satisfy the residual
criterion
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) OptimalInexactJacobianMonotone
(Ours) |
|||
| (2) (Jiang and Yoon 2026), Thms. 4.4, 4.6 | (1): removes a
logarithmic factor for |
(1) covers equations only; (2) also covers composite inclusions with tangent residual. | |
| (3) (Zhang et al.
2026), Thm. 3.1 ( |
(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 | (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: