← All setups

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 F:E→E on a separable real Hilbert space E. A zero within a prescribed distance of the given starting point satisfies the weak Minty condition. At each query x∈E, the oracle uses a fresh independent sample to return an unbiased estimate of F(x) with uniformly bounded variance. For a tolerance ε>0, the goal is an output x¯∈E with integrable residual norm satisfying E∥F(x¯)∥≤ε, where the expectation includes both oracle and algorithm randomness.

The root-finding problem is find x∈E such that F(x)=0. The algorithm receives E with its Borel σ-algebra, the measurable sample space Ω, the starting point x0∈E, and the parameters L,ρ,σ,R,ε, whose ranges are L>0,0≤ρ≤120L,σ≥0,R≥0,ε>0.

Our assumptions:

Assumption 1 (Lipschitz continuity). For every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥.

Assumption 2 (Weak Minty condition). There exists x⋆∈E with F(x⋆)=0 and ∥x0−x⋆∥≤R such that ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2for every x∈E.

Assumption 3 (Stochastic operator oracle). On call k, a query at any x∈E returns g(x,ξk), where g:E×Ω→E is jointly measurable. The samples (ξk)k≥0 are independent random variables with common law μ on Ω, and the sequence is independent of the algorithm’s randomness. For each x∈E and ξ∼μ, the vector g(x,ξ) is Bochner integrable, the squared error ∥g(x,ξ)−F(x)∥2 is integrable, and Eξ∼μ[g(x,ξ)]=F(x),Eξ∼μ[∥g(x,ξ)−F(x)∥2]≤σ2.

After the allotted oracle calls, the output x¯ must satisfy ∥F(x¯)∥∈L1(P),EP[∥F(x¯)∥]≤ε, where P is the joint law of the algorithm’s randomness and the oracle samples.

Results

On a separable real Hilbert space, F is L-Lipschitz (L>0) and has a zero x⋆ with ∥x0−x⋆∥≤R. For every x, ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2, where 0≤ρ≤1/(20L). The jointly measurable oracle uses IID samples ξ, with Eξg(x,ξ)=F(x) and Eξ∥g(x,ξ)−F(x)∥2≤σ2. The target is E∥F(x^)∥≤ε, for ε>0.

Sufficient oracle budgets for stochastic weak Minty root finding
Result Oracle complexity Novelty Limitations
(1) StochasticWeakMintyExtragradient (Ours) (review) O((1+L2R2ε2)(1+σ2ε2)) calls
(2) EG+ (Diakonikolas et al. 2021, Thm. 4.5(i)) O((1+L2R2sε2)(1+σ2sε2)) calls in Rd (1) formalizes the known rate for ordinary extragradient on separable Hilbert spaces. On the shared ρ range, s is bounded below by a universal constant. (1) requires ρL≤1/20. (2) allows ρL<1/(82) and certifies a mean-square residual bound for the random output.
(3) Past extragradient (Choudhury et al. 2023, Thm. 4.5) O(ε−4) component calls for mink<KE∥F(x^k)∥2≤ε2, with other parameters fixed. (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 x⋆, and allows ρL<1/2.
(4) Minibatching (Alacaoglu and Kim 2026, Thm. 2.1) O~(ε−4) calls with increasing batches (1) matches the polynomial accuracy dependence without logarithms, using a constant batch size on the unconstrained, bounded-variance overlap in Rd. (1) requires uniform variance and an unconstrained domain. (4) allows constraints, variance up to B2∥x−x0∥2+σ2, and ρL<72/(360+2056).
(5) Multilevel Monte Carlo (Alacaoglu and Kim 2026, Thm. 3.1) O~(ε−4) calls in expectation (1) gives a deterministic call budget with the same polynomial accuracy dependence and no logarithms on the unconstrained, bounded-variance overlap in Rd. (1) requires ρL≤1/20 and uniform variance. (5) allows ρL<1, constraints, and variance up to B2∥x−x0∥2+σ2.

Abbr: s=1−82Lρ. K counts iterations. B controls variance growth. O~ suppresses logarithmic factors in 1/ε with other parameters fixed as ε↓0.

Alacaoglu, Ahmet, and Jun-Hyun Kim. 2026. Solving Stochastic Variational Inequalities Without the Bounded Variance Assumption. https://doi.org/10.48550/arXiv.2602.05531.
Choudhury, Sayantan, Eduard Gorbunov, and Nicolas Loizou. 2023. “Single-Call Stochastic Extragradient Methods for Structured Non-Monotone Variational Inequalities: Improved Analysis Under Weaker Conditions.” Advances in Neural Information Processing Systems 36: 64918–56. https://doi.org/10.52202/075280-2833.
Diakonikolas, Jelena, Constantinos Daskalakis, and Michael I. Jordan. 2021. “Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization.” Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Proceedings of machine learning research, vol. 130: 2746–54. https://proceedings.mlr.press/v130/diakonikolas21a.html.

Lean setup