Non Euclidean Weak Minty Extragradient — Non-Euclidean Weak Minty Problems
Descriptions may be stale. Consult the linked Lean sources.
Non-Euclidean Weak Minty Problems · Lean proof
Non-Euclidean Weak Minty
Problems
We seek a zero of an operator on a finite-dimensional real normed space , where is its continuous dual with induced
operator norm . The operator is
-Lipschitz, with , and satisfies a weak Minty
condition with parameter at a zero .
A differentiable, -strongly
convex function ,
with , bounds the Bregman
distance from a given to
by . The oracle returns at . For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The problem is to find
such that Write for and . The norm on is denoted by , and define the Bregman
divergence by where is the Fréchet
derivative. The algorithm receives , , , , , and ; the bound and tolerance may enter only the
oracle-call budget.
Our assumptions:
Assumption 1 (Bregman geometry). The function is Fréchet differentiable everywhere on
, and
Assumption 2 (Lipschitz continuity). The operator
satisfies
Assumption 3 (Weak Minty condition and initial
bound). There exists
such that
Queries may be made at any point of . After the allotted oracle calls, the
output must satisfy the residual criterion
Proved result
OracleTemplate.Convergence LongTails.Setups.NonEuclideanWeakMinty.spec
LongTails.Theorems.NonEuclideanWeakMintyExtragradient.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.