Stochastic Weak Minty Root Finding
Descriptions may be stale. Consult the linked Lean sources.
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
Results
On a separable real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticWeakMintyExtragradient (Ours) (review) | |||
| (2) EG+ (Diakonikolas et al. 2021, Thm. 4.5(i)) | (1) formalizes the known
rate for ordinary extragradient on separable Hilbert spaces. On the
shared |
(1) requires |
|
| (3) Past extragradient (Choudhury et al. 2023, Thm. 4.5) | (1) returns a random iterate. (3) bounds the best index without identifying it and assumes finite-sum sampling with the expected residual condition. Rates across these noise models are incomparable. | (1) needs uniform
variance control and two fresh batches per full step.
(3) uses one batch per step, measures noise at |
|
| (4) Minibatching (Alacaoglu and Kim 2026, Thm. 2.1) | (1) matches the
polynomial accuracy dependence without logarithms, using a constant
batch size on the unconstrained, bounded-variance overlap in |
(1) requires uniform
variance and an unconstrained domain. (4) allows
constraints, variance up to |
|
| (5) Multilevel Monte Carlo (Alacaoglu and Kim 2026, Thm. 3.1) | (1) gives a deterministic
call budget with the same polynomial accuracy dependence and no
logarithms on the unconstrained, bounded-variance overlap in |
(1) requires |
Abbr: