← All setups

Monotone Variational Inequalities with Lipschitz Jacobians

Descriptions may be stale. Consult the linked Lean sources.

Monotone Variational Inequalities with Lipschitz Jacobians

We consider a monotone map F:E→E on a compact convex set X in a finite-dimensional real inner product space E. The map is differentiable on X with an L-Lipschitz Jacobian, where L>0. Two exact oracles return F(x) and its Jacobian, respectively. For ε>0, the goal is a feasible output x¯∈X admitting an outward normal n∈E, meaning ⟨n,z−x¯⟩≤0 for every z∈X, such that ∥F(x¯)+n∥≤ε almost surely under P, the law of the algorithm’s randomness.

The underlying variational inequality is to find x∈X such that ⟨F(x),z−x⟩≥0for every z∈X. Write JF(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 algorithm receives E, X, a given starting point x0, constants L,D,ε>0, and an integer m≥1.

Our assumptions:

Assumption 1 (Feasible set and starting point). The set X⊆E is compact and convex, and x0∈X,∥x−y∥≤Dfor every x,y∈X.

Assumption 2 (Monotonicity). For every x,y∈X, ⟨F(x)−F(y),x−y⟩≥0.

Assumption 3 (Lipschitz Jacobian). The map F:E→E is Fréchet differentiable at every point of X, and ∥JF(x)−JF(y)∥op≤L∥x−y∥for every x,y∈X.

Queries to either oracle may be made at any point of E. The value oracle returns F(x) at x, and the Jacobian oracle returns JF(x) at x; outside X, the latter is interpreted as the zero operator wherever F is not differentiable. Calls to the two oracles are counted separately.

Define the normal cone at x∈X by NX(x)={n∈E:⟨n,z−x⟩≤0 for every z∈X}. After the allotted oracle calls, the required accuracy is x¯∈X,∃n∈NX(x¯): ∥F(x¯)+n∥≤εP-a.s.

Results

In a finite-dimensional real inner-product space, X is compact and convex, x0∈X, and diam(X)≤D. The operator F is differentiable at every point of X, monotone on X, and its Jacobian J is L-Lipschitz on X. Given L,D,ε>0 and integer m≥1, exact values and Jacobians are available separately. The target is u∈X and n∈NX(u) with ∥F(u)+n∥≤ε; (1) guarantees this deterministically. Costs count oracle calls, with known affine-VI solves uncharged.

Comparison for LipschitzJacobianMonotone.
Result Oracle complexity Novelty Limitations
(1) CachedJacobian (Ours) (⋆⋆⋆) (review) W=O((m+mQ)ℓ);
G=O((1+mQ)ℓ),
H=O((1+Q/m)ℓ).
(2) Fresh jets (Zhang et al. 2026), Thm. 3.1 (p=2) W=O(m(1+Q2/5)) for tangent residual ≤ε. (1): lower cost for Q1/5ℓ2≪m≤Q. At m=Q, O(Q3/4log⁡Q) instead of O(Q9/10) as Q→∞. (1): worse accuracy dependence when Jacobians are cheap; at m=1, O(Q1/2log⁡Q) versus O(Q2/5) as Q→∞.
(3) Halpern-NPE (Chen et al. 2026), Thm. 4.1 W=O(m(1+Q)
⋅[1+log⁡log⁡(e+Q)]) for ∥x−Pηx∥/η≤ε.
(1): tangent residual at the output instead of normalized proximal residual. Without a conversion cost, rates are not directly comparable.
(4) VIJI, derived bound (Agafonov et al. 2024), Thm. 3.2; reuse J(x0) W=O(m+Q) for gap ≤εD; G=O(1+Q2/3+Q), H=1, Jacobian error δ=LD. (1): lower cost for the shared gap target when 1≤m≪Q/ℓ2, by order Q/m/ℓ; additionally certifies last-inner-iterate tangent residual instead of averaged gap. (1): logarithmic cost overhead when m≥Q.
(5) LEN (Chen et al. 2025), Thm. 4.1; unconstrained convex–concave saddles only W=O(m+(mLR3εD)2/3) for restricted saddle gap ≤εD; lazy period m, globally L-Lipschitz ∇2f. (1): scope extends to general monotone VIs on compact convex sets; tangent residual replaces ergodic restricted gap. Setups are not nested; rates are not comparable. (1) needs a compact feasible set; (5) permits unconstrained domains.

Abbr: Q=LD2/ε, ℓ=log⁡(2+mQ); G,H count value and Jacobian calls, W=G+mH charges a Jacobian at m value calls, and a full jet at m+1. NX(u)={n:⟨n,z−u⟩≤0 ∀z∈X}. Gap means supz∈X⟨F(z),u−z⟩. Pη=(I+η(F+NX))−1, with η=Θ(1/Lε) in (3). In (5), R=∥z0−z∗∥ for a saddle point z∗; the restricted gap uses radius 3R. The symbol ≪ denotes an asymptotically vanishing ratio.

Agafonov, Artem, Petr Ostroukhov, Roman Mozhaev, et al. 2024. “Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations.” Advances in Neural Information Processing Systems 37. https://doi.org/10.52202/079017-3678.
Chen, Lesi, Chengchang Liu, and Jingzhao Zhang. 2025. Second-Order Min-Max Optimization with Lazy Hessians. https://doi.org/10.48550/arXiv.2410.09568.
Chen, Lesi, Xinliang Zhang, Hengyu Wang, Chengchang Liu, Yongchao Chen, and Jingzhao Zhang. 2026. Halpern Iteration Achieves O~(ϵ−1/p) pTh-Order Oracle Complexity for Monotone Variational Inequalities. https://doi.org/10.48550/arXiv.2608.08463.
Zhang, Xinliang, Lesi Chen, Linxuan Pan, Chengchang Liu, Junchi Yang, and Jingzhao Zhang. 2026. Optimal High-Order Methods for Solving Monotone Variational Inequalities. https://doi.org/10.48550/arXiv.2609.23557.

Lean setup