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
The underlying variational inequality is to find
Our assumptions:
Assumption 1 (Feasible set and starting point). The
set
Assumption 2 (Monotonicity). For every
Assumption 3 (Lipschitz Jacobian). The map
Queries to either oracle may be made at any point of
Define the normal cone at
Results
In a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CachedJacobian
(Ours) |
|||
| (2) Fresh jets (Zhang et al.
2026), Thm. 3.1 ( |
(1): lower cost for |
(1): worse accuracy
dependence when Jacobians are cheap; at |
|
| (3) Halpern-NPE (Chen et al. 2026), Thm. 4.1 | (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 |
(1): lower cost for the
shared gap target when |
(1): logarithmic cost
overhead when |
|
| (5) LEN (Chen et al. 2025), Thm. 4.1; unconstrained convex–concave saddles only | (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: