Optimal Inexact Jacobian Monotone — Monotone Equations with Inexact Jacobians
Descriptions may be stale. Consult the linked Lean sources.
Monotone Equations with Inexact Jacobians · Lean proof
Monotone Equations with
Inexact Jacobians
We consider finding a zero of a differentiable monotone map on a finite-dimensional real
inner product space . Its Jacobian
is -Lipschitz in operator norm,
with , and a given point
lies within distance of a zero. At a query , the oracle returns and a linear approximation to its
Jacobian with operator-norm error at most . For , the goal is an output
satisfying almost
surely under , the joint law of
algorithm and oracle randomness.
The equation to solve is 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 , , , , , and .
Our assumptions:
Assumption 1 (Monotonicity and Jacobian regularity).
The map is Fréchet differentiable
everywhere, and for every ,
Assumption 2 (Nearby zero). There exists such that
Assumption 3 (Inexact Jacobian oracle). Queries may
be made at any . Each oracle
call returns a pair , where
and is linear, satisfying These conditions hold for
every query history and every realization of the oracle randomness. The
approximate Jacobian may depend on both. Algorithm randomness is
independent of oracle randomness.
After the allotted oracle calls, the output must satisfy the residual
criterion
Proved result
OracleTemplate.Convergence LongTails.Setups.InexactJacobianMonotone.spec
LongTails.Theorems.OptimalInexactJacobianMonotone.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.