← All setups

Stochastic Weak Minty Lower Bound — High-Dimensional Stochastic Weak Minty Problems

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Stochastic Weak Minty Problems · Lean proof

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¯)∥]≤ε.

Proved result

⌊L2⋅R2⋅(ε2+σ2)219⋅ε4⌋+

OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalStochasticWeakMinty.spec
  LongTails.Theorems.StochasticWeakMintyLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.