Non-Euclidean Weak Minty Problems
Descriptions may be stale. Consult the linked Lean sources.
Non-Euclidean Weak Minty Problems
We seek a zero of an operator
The problem is to find
Our assumptions:
Assumption 1 (Bregman geometry). The function
Assumption 2 (Lipschitz continuity). The operator
satisfies
Assumption 3 (Weak Minty condition and initial
bound). There exists
Queries may be made at any point of
Results
In a finite-dimensional real normed space
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) NonEuclideanWeakMintyExtragradient
(Ours) |
|||
| (2) Mirror extragradient (Zhang and Dai 2022), Thm. 2, Lemma 3 | (1): Accuracy term
smaller by |
(1): Larger leading
constant. For the Euclidean quadratic mirror, narrower range: |
|
| (3) EG+ (Diakonikolas et al. 2021), Thm. 3.2; Euclidean special case | On |
(1): Matches known rate on this restriction; extends scope to arbitrary norms. | (1): Narrower admissible
range: |
| (4) EG |
(1): |
||
| (5) (Pethick et al. 2025), Thm. 6.1, Cor. 6.3; Euclidean unconstrained restriction | On |
(1): Extends scope to arbitrary norms; no established rate improvement on the Euclidean restriction. | (1): Narrower admissible
range: |
Abbr: