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 in high
dimension . A zero lies within a prescribed radius
of the given starting point and
satisfies the weak Minty inequality for every , with . At each query , the oracle uses a fresh independent
sample to return an unbiased estimate of with uniformly bounded variance. For
tolerance , the
goal is an output with ,
averaging over algorithm and oracle randomness.
In terms of the Euclidean residual, the problem is The
algorithm receives ,
the Lipschitz constant , the
weak Minty parameter , the noise bound , the radius , the tolerance , and . We consider the
parameter regime
Our assumptions:
Assumption 1 (Lipschitz continuity). For every ,
Assumption 2 (Weak Minty condition and initial
distance). There exists with and such that
Assumption 3 (Stochastic operator oracle). The
oracle samples
are independent real-valued random variables with common law , and the sequence is independent of
the algorithm’s randomness. On call , a query at any receives , where
is jointly measurable. For each
and , the vector is Bochner integrable, the
squared error
is integrable, and
After the allotted oracle calls, the residual norm of the output
must be integrable under
the joint law of the algorithm’s
randomness and the oracle samples, and satisfy
Proved result
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.