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
The root-finding problem is
Our assumptions:
Assumption 1 (Parameter regime). The positive
parameters
Assumption 2 (Monotonicity and Jacobian regularity).
The map
Assumption 3 (Nearby zero). There exists
Queries may be made at any point of
Results
Monotone differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RandomizedGlobalJacobianMonotoneLowerBound
(Ours) |
Necessary: |
||
| (2) (Jiang and Yoon
2026), Thm. 6.1, |
Necessary: |
(1): Scope: randomized adaptive algorithms instead of deterministic algorithms, with unrestricted queries. Matches the lower-bound exponent. | (1): Dimension scales as
|
| (3) (Zhang et al.
2026), Thm. 11.3, |
Necessary: |
(1): Scope: unrestricted
queries and global residual. Same exponent; |
(1): Dimension scales as
|
| (4) (Garg et al.
2021), Thm. 1, |
Necessary: |
(1): Exponent |
(1): residual-to-value conversion requires bounded outputs, absent from the target setup. |
Abbr: