Stochastic Weak Minty Extragradient — Stochastic Weak Minty Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Weak Minty Root Finding · Lean proof
Stochastic Weak Minty Root Finding
We seek a zero of a Lipschitz operator
The root-finding problem is
Our assumptions:
Assumption 1 (Lipschitz continuity). For every
Assumption 2 (Weak Minty condition). There exists
Assumption 3 (Stochastic operator oracle). On call
After the allotted oracle calls, the output
Proved result
OracleTemplate.Convergence LongTails.Setups.StochasticWeakMinty.spec
LongTails.Theorems.StochasticWeakMintyExtragradient.budgetRelevant previous results
- Jelena Diakonikolas, Constantinos Daskalakis, Michael I. Jordan. Efficient
Methods for Structured Nonconvex-Nonconcave Min-Max Optimization.
2021. Complexity:
stochastic operator calls for mini-batched Extragradient+ to return a uniformly sampled iterate with in , where . - Sayantan Choudhury, Eduard Gorbunov, Nicolas Loizou. Single-Call
Stochastic Extragradient Methods for Structured Non-monotone Variational
Inequalities: Improved Analysis under Weaker Conditions. 2023.
Complexity:
sampled operator calls for mini-batched stochastic past extragradient to achieve in under uniform variance and .