← All setups

Non-Euclidean Weak Minty Problems

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

In a finite-dimensional real normed space E, F:E→E∗ is L-Lipschitz from the primal to the dual norm, L>0. A root x⋆ satisfies ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥∗2 for all x, with 0≤ρL≤1/20. The differentiable mirror h satisfies Dh(u,x)≥(μ/2)∥u−x∥2, μ>0, and Dh(x⋆,x0)≤D, D≥0. Exact F evaluations are counted; the target is ∥F(xout)∥∗≤ε, ε>0, almost surely.

Exact-operator residual complexity for NonEuclideanWeakMinty.
Result Oracle complexity Novelty Limitations
(1) NonEuclideanWeakMintyExtragradient (Ours) (⋆⋆⋆) (review) O(1+L2Dμε2)
(2) Mirror extragradient (Zhang and Dai 2022), Thm. 2, Lemma 3

O(1+L0L2Dμ3ε2)

h additionally L0-smooth; ρL≤μ2/(16L0).

(1): Accuracy term smaller by L0/μ on the overlap; no mirror-gradient smoothness. Range ρL≤1/20 independent of geometry. Spectral/Frobenius example: O(1+L2RF2/ε2) instead of O(1+rL2RF2/ε2). (1): Larger leading constant. For the Euclidean quadratic mirror, narrower range: 1/20 versus ρL<1/8.
(3) EG+ (Diakonikolas et al. 2021), Thm. 3.2; Euclidean special case

O(1+L2R22ε2)

On ρL≤1/20; Euclidean quadratic mirror.

(1): Matches known rate on this restriction; extends scope to arbitrary norms. (1): Narrower admissible range: ρL≤1/20 versus ρL<1/8.
(4) EGp+ (Diakonikolas et al. 2021), Thm. 4.2(i); ℓp special case

O(1+L2Rp2(p−1)2ε2)

1<p≤2, ρ=0; h=12∥⋅−x0∥p2.

(1): O(1+L2Rp2/((p−1)ε2)) at ρ=0: accuracy term smaller by 1/(p−1). Extends this geometry to 0<ρL≤1/20.
(5) (Pethick et al. 2025), Thm. 6.1, Cor. 6.3; Euclidean unconstrained restriction

O(1+L2R22ε2)

On ρL≤1/20, including inner evaluations; the extra resolvent is the identity.

(1): Extends scope to arbitrary norms; no established rate improvement on the Euclidean restriction. (1): Narrower admissible range: ρL≤1/20 versus ρL<1.

Abbr: Dh(u,x)=h(u)−h(x)−Dh(x)[u−x]; ∥⋅∥∗ is the dual norm; L0 is the Lipschitz constant of Dh. Rp=∥x⋆−x0∥p; in row (4), μ=p−1, D=Rp2/2. Euclidean comparisons use h=12∥⋅−x0∥22, μ=1, D=R22/2. In the spectral-norm example, r=min(m,n), RF=∥X⋆−X0∥F, and the Frobenius mirror has μ=1, L0=r, D=RF2/2. All ranges use the displayed setup’s convention for ρ.

Diakonikolas, Jelena, Constantinos Daskalakis, and Michael I. Jordan. 2021. “Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization.” Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Proceedings of machine learning research, vol. 130: 2746–54. https://proceedings.mlr.press/v130/diakonikolas21a.html.
Pethick, Thomas, Ioannis Mavrothalassitis, and Volkan Cevher. 2025. “Efficient Interpolation Between Extragradient and Proximal Methods for Weak MVIs.” The Thirteenth International Conference on Learning Representations. https://proceedings.iclr.cc/paper_files/paper/2025/file/7f44f98e5e70dea605d0c5baca231c58-Paper-Conference.pdf.
Zhang, Hui, and Yu-Hong Dai. 2022. Mirror Frameworks for Relatively Lipschitz and Monotone-Like Variational Inequalities. https://doi.org/10.48550/arXiv.2108.12070.

Lean setup