← All setups

Euclidean Weak Minty Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Euclidean Weak Minty Root Finding

We consider finding a zero of an L-Lipschitz map F:Rd→Rd, where d≥257 and L>0. A given point x0 lies within Euclidean distance R>0 of a zero x⋆ satisfying the weak Minty condition ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2 for every x, with 0≤ρ≤1/(20L). The oracle returns F(x) at x. For ε>0 with 28ε≤LR, the goal is an output x¯ with integrable residual norm and EP∥F(x¯)∥≤ε, where P is the law of the algorithm’s randomness.

The root-finding problem is to find x∈Rd such that F(x)=0. Throughout, ⟨⋅,⋅⟩ and ∥⋅∥ denote the standard Euclidean inner product and norm. The algorithm receives d,L,ρ,x0,R, and ε, with parameter ranges d∈N,d≥257,L>0,0≤ρ≤120L,R>0,ε>0,28ε≤LR.

Our assumptions:

Assumption 1 (Lipschitz continuity). For every x,y∈Rd, ∥F(x)−F(y)∥≤L∥x−y∥.

Assumption 2 (Weak Minty condition and initial distance). There exists x⋆∈Rd such that F(x⋆)=0,∥x⋆−x0∥≤R,⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2for every x∈Rd.

Queries may be made at any point of Rd. After the allotted oracle calls, the output x¯∈Rd must have integrable residual norm under P and satisfy EP[∥F(x¯)∥]≤ε.

Results

F:Rd→Rd is L-Lipschitz, with F(x⋆)=0, ∥x⋆−x0∥≤R, and ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2 for every x. Parameters satisfy L,ε>0, 0≤ρL≤1/20, 28ε≤LR, and d≥257. Each query returns exact F(x); the setup imposes no algorithm restriction. The target is an integrable residual with ∫∥F(x^(ω))∥dP(ω)≤ε, where P is the execution probability law.

Exact-operator residual complexity for EuclideanWeakMinty.
Result Oracle complexity Novelty Limitations
(1) EuclideanWeakMintyLowerBound (Ours) (⋆⋆⋆) (review) Ω(min{L2R2/ε2,d1/3}) necessary calls, for arbitrary randomized algorithms and outputs; hard instances already satisfy ρ=0.
(2) EuclideanWeakMintyExtragradient (Ours) (review) O(L2R2/ε2) sufficient calls. Matches (1) up to universal factors if d≥257(LR/(28ε))6; otherwise a dimension-dependent gap remains.
(3) (Yoon and Ryu 2021), Theorem 3 Ω(LR/ε) necessary calls. Monotone biaffine saddle operators; deterministic separate-span methods. For N queries: d=2n, n≥N+2. (1): (LR/ε)2 instead of LR/ε when d≥257(LR/(28ε))6; stronger order whenever d1/3≫LR/ε. Scope: arbitrary randomized methods/outputs; nonmonotone Minty hard instances. (1) needs d≫(LR/ε)3 for an order improvement; (3) needs dimension only linear in its necessary budget.
(4) EG+ (Diakonikolas et al. 2021), Theorem 3.2 O(1+L2R2(1−8ρL)ε2) exact F calls; 0≤ρL<1/8. (2): matches known rate on the shared parameter range; formalization of the EG+ guarantee. (2) has a worse leading constant; requires ρL≤1/20, d≥257, and 28ε≤LR.
(5) CEG+ (Pethick et al. 2023), Corollary 3.2 O(L2R2/ε2) exact F calls on the shared setup, with the unconstrained resolvent equal to the identity. (2): matches known rate on the shared setup. (2) covers only ρL≤1/20; (5) permits ρL<1/2 and constrained inclusions.
(6) (Pethick et al. 2025), Theorem 6.1(i), Corollary 6.3 O(L2R2/ε2) exact F calls on the shared setup, including inner evaluations; the unconstrained resolvent is the identity. (2): matches known rate on the shared setup. (2) covers only ρL≤1/20; (6) permits ρL<1 and constrained inclusions; displayed cost is restricted to the shared range.

Abbr: L: operator Lipschitz constant; R: initial root-distance bound; ρ: weak-Minty parameter; ε: residual tolerance; d: dimension; N: exact operator-query count. Ω denotes necessary complexity, O sufficient complexity. All ρ ranges use the setup’s sign and normalization; the squared-residual tolerances in the cited upper bounds are set to ε2.

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, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevher. 2023. Escaping Limit Cycles: Global Convergence for Constrained Nonconvex-Nonconcave Minimax Problems. https://doi.org/10.48550/arXiv.2302.09831.
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.
Yoon, Taeho, and Ernest K. Ryu. 2021. “Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm.” Proceedings of the 38th International Conference on Machine Learning, Proceedings of machine learning research, vol. 139: 12098–109. https://proceedings.mlr.press/v139/yoon21d.html.

Lean setup