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
In terms of the Euclidean residual, the problem is
Our assumptions:
Assumption 1 (Lipschitz continuity). For every
Assumption 2 (Weak Minty condition and initial
distance). There exists
Assumption 3 (Stochastic operator oracle). The
oracle samples
After the allotted oracle calls, the residual norm of the output
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticWeakMintyLowerBound
(Ours) |
Lower bound: |
||
| (2) Derived bound: exact Minty oracle (auto-math-bot 2026) plus mean estimation | Lower bound: |
(1): Even at |
(1) needs |
| (3) Derived bound: biaffine saddle problems (Yoon and Ryu 2021, Thm. 3) plus mean estimation | Lower bound: |
(1) covers arbitrary
randomized adaptive methods and outputs. Allowing nonmonotone Minty
instances strengthens the class lower bound by |
(3) needs only |
Abbr: