Euclidean Weak Minty Extragradient — Euclidean Weak Minty Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Euclidean Weak Minty Root Finding · Lean proof
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
Proved result
OracleTemplate.Convergence LongTails.Setups.EuclideanWeakMinty.spec
LongTails.Theorems.EuclideanWeakMintyExtragradient.budgetRelevant previous results
- Jelena Diakonikolas, Constantinos Daskalakis, Michael I. Jordan. Efficient
Methods for Structured Nonconvex-Nonconcave Min-Max Optimization.
2021 (preprint 2020). Complexity:
exact operator evaluations using EG+, with a fixed budget ensuring , for .