Strongly Monotone Hidden-Potential Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Strongly Monotone Hidden-Potential Root Finding
We seek a zero of a map
The root-finding problem is
Our assumptions:
Assumption 1 (Strong monotonicity). For every
Assumption 2 (Hidden potential). There exists an
everywhere Fréchet differentiable function
Assumption 3 (Initial distance). There exists
Queries may be made at any point of
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) HiddenPotentialOracleComplexity
(Ours) |
|||
| (2) Past extragradient (Gidel et al. 2020, Thm. 1) | (1): gain |
(1): loses factor |
|
| (3) (Wang and Li 2020, Thm. 3) | (1): on bilinear overlap
with |
(1) does not cover the general nonlinear-coupling saddle class of (3); outside the bilinear overlap, rates are not comparable. | |
| (4) APDG (Kovalev et al. 2022, Thm. 4.2, Sec. 5.1) | (1): scope extends to hidden partitions and nonlinear residuals. On the stated restriction, component gradients and matrix products require only constantly many combined calls. | (1) has worse polynomial
dependence for |
|
| (5) Restarted AG-EG (Yuan et al. 2023, Cor. 2.8) | (1): only combined |
(1) has larger polynomial
cost when |
Abbr: