Monotone Roots with Lipschitz Second Derivatives
Descriptions may be stale. Consult the linked Lean sources.
Monotone Roots with Lipschitz Second Derivatives
We consider finding a zero of a twice continuously differentiable
monotone map
The root-finding problem is to find
Our assumptions:
Assumption 1 (Monotonicity). For every
Assumption 2 (Lipschitz second derivative). The map
Assumption 3 (Initial bounds). There exists
Both oracles are exact and may be queried at any point of
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) HomotopyNewtonMonotone
(Ours) |
|||
| (2) AEP tensor (Jiang and Yoon
2026), Thms. 5.2–5.3, |
(1): Removes |
(1): Extra logarithmic
overhead and |
|
| (3) AEP Newton (Jiang and Yoon 2026), Thms. 4.4, 4.6 | (1): On the overlap,
fixed positive |
(1): Needs Lipschitz
|
Abbr: