Generalized Lipschitz Monotone Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Generalized Lipschitz Monotone Root Finding
We seek a zero of a continuous monotone operator
The root-finding problem is to find
Our assumptions:
Assumption 1 (Continuity and monotonicity). The
operator
Assumption 2 (Generalized Lipschitz condition). For
every
Assumption 3 (Initial residual and distance). There
exists
Queries may be made at any point of
Results
A continuous monotone map
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AnchoredGeneralizedMonotone
(Ours) |
|||
| (2) EG (Choudhury and Loizou 2025, Thm. 3.6) | (1): |
||
| (3) PolyakEG (Yoon et al. 2026, Thm. 3.4, Eq. (19)) | (1): same leading-term
gain as against (2). If |
||
| (4) PolyakEG-LS (Yoon et al. 2026, Thm. 3.4, Prop. 3.5(a)) | Derived bound: |
(1): |
(1) needs |
| (5) FEG / EAG (Lee and Kim 2021,
Thm. 4.1, |
(1) matches the known
rate on this overlap; scope extends to generalized Lipschitz continuity
with |
(1) has a roughly
fivefold larger leading cost constant than FEG when |
Abbr: Costs count individual