Euclidean Weak Minty Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Euclidean Weak Minty Root Finding
We consider finding a zero of an
The root-finding problem is to find
Our assumptions:
Assumption 1 (Lipschitz continuity). For every
Assumption 2 (Weak Minty condition and initial
distance). There exists
Queries may be made at any point of
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) EuclideanWeakMintyLowerBound
(Ours) |
|||
| (2) EuclideanWeakMintyExtragradient (Ours) (review) | |||
| (3) (Yoon and Ryu 2021), Theorem 3 | (1): |
(1) needs |
|
| (4) EG+ (Diakonikolas et al. 2021), Theorem 3.2 | (2): matches known rate on the shared parameter range; formalization of the EG+ guarantee. | (2) has a worse leading
constant; requires |
|
| (5) CEG+ (Pethick et al. 2023), Corollary 3.2 | (2): matches known rate on the shared setup. | (2) covers only |
|
| (6) (Pethick et al. 2025), Theorem 6.1(i), Corollary 6.3 | (2): matches known rate on the shared setup. | (2) covers only |
Abbr: