← All setups

High-Dimensional Stochastic Weak Minty Problems

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Stochastic Weak Minty Problems

We seek a zero of a Lipschitz operator F:Rd→Rd in high dimension d. A zero x⋆ lies within a prescribed radius of the given starting point x0 and satisfies the weak Minty inequality ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2 for every x∈Rd, with ρ≥0. At each query x, the oracle uses a fresh independent sample to return an unbiased estimate of F(x) with uniformly bounded variance. For tolerance ε>0, the goal is an output x¯∈Rd with E∥F(x¯)∥≤ε, averaging over algorithm and oracle randomness.

In terms of the Euclidean residual, the problem is minx∈Rd∥F(x)∥. The algorithm receives d∈N, the Lipschitz constant L>0, the weak Minty parameter ρ∈[0,1/(20L)], the noise bound σ≥0, the radius R≥0, the tolerance ε>0, and x0∈Rd. We consider the parameter regime 210ε≤LR,L6R6(ε2+σ2)≤ε8d.

Our assumptions:

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

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

Assumption 3 (Stochastic operator oracle). The oracle samples (ξk)k≥0 are independent real-valued random variables with common law μ, and the sequence is independent of the algorithm’s randomness. On call k, a query at any x∈Rd receives g(x,ξk), where g:Rd×R→Rd is jointly measurable. For each x 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 residual norm of the output x¯ must be integrable under the joint law P of the algorithm’s randomness and the oracle samples, and satisfy EP[∥F(x¯)∥]≤ε.

Results

Let F:Rd→Rd be L-Lipschitz, with F(x⋆)=0, ∥x0−x⋆∥≤R, and ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2 for every x. Each call returns g(x,ξ) using a fresh IID real sample, with g jointly measurable, Eg(x,ξ)=F(x) and E∥g(x,ξ)−F(x)∥2≤σ2. For L,ε>0, R,σ≥0, 0≤ρ≤1/(20L), a≥210 and d≥a6(1+s2), the target is E∥F(x^)∥≤ε over oracle and algorithm randomness.

Necessary oracle calls for high-dimensional stochastic weak-Minty problems
Result Oracle complexity Novelty Limitations
(1) StochasticWeakMintyLowerBound (Ours) (⋆⋆⋆) (review) Lower bound: Ω(a2(1+s2)) calls
(2) Derived bound: exact Minty oracle (auto-math-bot 2026) plus mean estimation Lower bound: Ω(a2+s2) calls (1): Even at ρ=0, the noise term grows from s2 to a2s2. The total bound gains a factor Θ(min{a2,1+s2}), reaching Θ(a2) for σ≥LR. (1) needs d≥a6(1+s2) and a≥210. For (2), d≥max{257,a6} and a≥28 suffice. The hard stochastic oracle in (1) lacks mean-square Lipschitz continuity.
(3) Derived bound: biaffine saddle problems (Yoon and Ryu 2021, Thm. 3) plus mean estimation Lower bound: Ω(a+s2) calls for deterministic span methods on monotone instances (1) covers arbitrary randomized adaptive methods and outputs. Allowing nonmonotone Minty instances strengthens the class lower bound by Ω(a), or Ω(a2) when σ2≥εLR. (3) needs only d≥2(N+2) for the exact-oracle span bound at N calls. The stronger rate in (1) requires higher dimension and allows nonmonotone instances.

Abbr: a=LR/ε, s=σ/ε. One call counts one operator sample.

auto-math-bot. 2026. LongTails: EuclideanWeakMintyLowerBound. Unpublished Lean theorem, commit 98684e93, 17 November 2026. https://github.com/k3nfalt/longtails/blob/98684e93f90740c6e22f46041ffb3d08aebe18d1/LongTails/Theorems/EuclideanWeakMintyLowerBound.lean.
Yoon, Taeho, and Ernest K. Ryu. 2021. “Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm.” Proceedings of the 38th International Conference on Machine Learning, Proceedings of machine learning research, vol. 139: 12098–109. https://proceedings.mlr.press/v139/yoon21d.html.

Lean setup