← All setups

Second-Order Weak Minty Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Second-Order Weak Minty Root Finding

We seek a zero of a differentiable map F:E→E on a finite-dimensional real inner product space E. The map and its derivative are Lipschitz. A root x⋆ satisfies the weak Minty inequality ⟨F(x),x−x⋆⟩≥−(ρ/2)∥F(x)∥2 for every x∈E, where ρ≥0, and a given starting point x0 lies within distance R≥0 of this root. The oracle returns either F(x) or its derivative at the queried point x. For ε>0, the goal is an output x¯∈E with ∥F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The root-finding problem is to find x∈E such that F(x)=0. Write J(x):E→E for the Fréchet derivative of F at x. The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The parameters satisfy L1>0,L2>0,ρL1<2. The algorithm receives E, L1, L2, ρ, ε, and x0; the radius R may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Lipschitz map and derivative). The map F is Fréchet differentiable everywhere on E, and, for all x,y∈E, ∥F(x)−F(y)∥≤L1∥x−y∥,∥J(x)−J(y)∥op≤L2∥x−y∥.

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

At any point x∈E, the algorithm may request either the exact value F(x) or the exact linear operator J(x). Each request counts as one call toward a shared oracle-call budget; obtaining both at a point requires two calls. After the allotted calls, the output must satisfy ∥F(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, F is differentiable, L1-Lipschitz, and has an L2-Lipschitz Jacobian, with L1,L2>0. A root x⋆ satisfies ∥x0−x⋆∥≤R and ⟨F(x),x−x⋆⟩≥−ρ2∥F(x)∥2 for every x, where R,ρ≥0 and ρL1<2. Exact value and full-Jacobian queries are available. The target is ∥F(xout)∥≤ε, ε>0, almost surely.

Second-order weak Minty root finding: WeakMintySecondOrder.
Result Oracle complexity Novelty Limitations
(1) FullRangeSecondOrderWeakMinty (Ours) (⋆⋆⋆) (review) O((1+L2R2/ε)δ−5ℓ) total value and full-Jacobian calls. Updates need no R.
(2) (Pethick et al. 2025), Thm. 6.1 / Cor. 6.3; A=0 Derived bound: O((1+L12R2/ε2)δ−3ℓ) value calls, including inner iterations. Full range ρL1<2; no Jacobian needed. (1): ε−1 instead of ε−2 when ε≪δ2L12/L2 and ε≲L2R2. Fixed δ, L1=L2=R=1: O(ε−1) versus O(ε−2). (1) needs Lipschitz full Jacobians and exact cubic-model roots; arithmetic uncounted. Worse δ dependence; loses at large ε. No constrained extension.
(3) (Vyas and Bullins 2023), Thm. B.1, p=q=2; restricted standard weak Minty Value and full-Jacobian calls. At ρ=0: O(1+L2R2/ε). (1): Scope extends trajectory-dependent smallness of ρ to every ρL1<2, independently of initial distance. Matches known rate at ρ=0.
(4) (Vyas and Bullins 2023), Thm. 3.5, p=2; 3/2-power defect At ρ′=0: O(1+L2R2/ε) value and full-Jacobian calls. General condition: ⟨F(x),x−x⋆⟩≥−ρ′2∥F(x)∥3/2, with sufficiently small ρ′. (1) matches known rate at ρ=ρ′=0. Away from Minty, defect classes are incomparable; rates are not comparable without additional restrictions. (1) additionally requires global L1-Lipschitz continuity of F.
(5) (Vyas and Bullins 2026), Thm. B.3; bounded-operator special case Value and full-Jacobian calls; requires supx∥F(x)∥≤D and a D-dependent smallness condition on ρ. (1): Scope extends to unbounded operators throughout ρL1<2. No established rate improvement on the overlap.

Abbr: δ=1−ρL1/2∈(0,1]; ℓ=1+log⁡(1/δ); R bounds initial root distance. Each full-Jacobian query counts as one call. A=0 denotes the unconstrained specialization (its resolvent is the identity). ρ′ is the 3/2-power defect coefficient; D bounds operator norms. Minty means zero defect.

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.
Vyas, Abhijeet, and Brian Bullins. 2023. Beyond First-Order Methods for Non-Convex Non-Concave Min-Max Optimization. https://doi.org/10.48550/arXiv.2304.08389.
Vyas, Abhijeet, and Brian Bullins. 2026. Beyond First-Order Methods for ℓp-Structured Non-Monotone Variational Inequalities. https://doi.org/10.48550/arXiv.2603.13491.

Lean setup