← All setups

Cached Jacobian — Monotone Variational Inequalities with Lipschitz Jacobians

Descriptions may be stale. Consult the linked Lean sources.

Monotone Variational Inequalities with Lipschitz Jacobians · Lean proof

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.

Proved result

Oracle 0:⌈100000⋅(1+m⋅L⋅D2ε)⋅(1+log⁡(2+m⋅L⋅D2ε))⌉+ Oracle 1:⌈20000⋅(1+L⋅D2m⋅ε)⋅(1+log⁡(2+m⋅L⋅D2ε))⌉+

OracleTemplate.Convergence LongTails.Setups.LipschitzJacobianMonotone.spec LongTails.Theorems.CachedJacobian.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.