← All setups

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 F:E→E∗ on a finite-dimensional real normed space E, where E∗ is its continuous dual with induced operator norm ∥⋅∥op. The operator is L-Lipschitz, with L>0, and satisfies a weak Minty condition with parameter 0≤ρ≤1/(20L) at a zero x⋆. A differentiable, μ-strongly convex function h:E→R, with μ>0, bounds the Bregman distance from a given x0∈E to x⋆ by D≥0. The oracle returns F(x) at x. For ε>0, the goal is an output x¯∈E satisfying ∥F(x¯)∥op≤ε almost surely under P, the law of the algorithm’s randomness.

The problem is to find x∈E such that F(x)=0. Write ⟨v,u⟩=v(u) for v∈E∗ and u∈E. The norm on E is denoted by ∥⋅∥, and define the Bregman divergence by Bh(u,x)=h(u)−h(x)−⟨h′(x),u−x⟩, where h′(x)∈E∗ is the Fréchet derivative. The algorithm receives E, L, ρ, μ, h, and x0; the bound D and tolerance ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Bregman geometry). The function h is Fréchet differentiable everywhere on E, and Bh(u,x)≥μ2∥u−x∥2,x,u∈E.

Assumption 2 (Lipschitz continuity). The operator satisfies ∥F(x)−F(y)∥op≤L∥x−y∥,x,y∈E.

Assumption 3 (Weak Minty condition and initial bound). There exists x⋆∈E such that F(x⋆)=0,Bh(x⋆,x0)≤D,⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥op2,x∈E.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy the residual criterion ∥F(x¯)∥op≤εP-a.s.

Proved result

2+2⋅⌈400⋅L2⋅Dμ⋅ε2⌉+

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.