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 on a compact convex set in a finite-dimensional real inner
product space . The map is
differentiable on with an -Lipschitz Jacobian, where . Two exact oracles return and its Jacobian, respectively. For
, the goal is a
feasible output
admitting an outward normal ,
meaning for every , such that almost
surely under , the law of the
algorithm’s randomness.
The underlying variational inequality is to find such that Write for the Fréchet derivative
of at . The norm is induced by the inner product
on , and denotes the
induced operator norm. The algorithm receives , , a given starting point , constants , and an integer
.
Our assumptions:
Assumption 1 (Feasible set and starting point). The
set is compact and
convex, and
Assumption 2 (Monotonicity). For every ,
Assumption 3 (Lipschitz Jacobian). The map is Fréchet differentiable at
every point of , and
Queries to either oracle may be made at any point of . The value oracle returns at , and the Jacobian oracle returns at ; outside , the latter is interpreted as the zero
operator wherever is not
differentiable. Calls to the two oracles are counted separately.
Define the normal cone at
by After the allotted oracle calls,
the required accuracy is
Proved result
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.