← All setups

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 F:E→E on a finite-dimensional real inner product space E. Its Jacobian is M-Lipschitz in operator norm, with M>0, and a given point x0∈E lies within distance R>0 of a zero. At a query x∈E, the oracle returns F(x) and a linear approximation to its Jacobian with operator-norm error at most δ≥0. For ε>0, the goal is an output x¯∈E satisfying ∥F(x¯)∥≤ε almost surely under P, the joint law of algorithm and oracle randomness.

The equation to solve is F(x)=0,x∈E. 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, x0, M, δ, R, and ε.

Our assumptions:

Assumption 1 (Monotonicity and Jacobian regularity). The map F is Fréchet differentiable everywhere, and for every x,y∈E, ⟨F(x)−F(y),x−y⟩≥0,∥JF(x)−JF(y)∥op≤M∥x−y∥.

Assumption 2 (Nearby zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R.

Assumption 3 (Inexact Jacobian oracle). Queries may be made at any x∈E. Each oracle call returns a pair (v,A), where v∈E and A:E→E is linear, satisfying v=F(x),∥A−JF(x)∥op≤δ. 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 ∥F(x¯)∥≤εP-a.s.

Proved result

⌈4194304⋅(1+(M⋅R2ε)25+δ⋅Rε)⌉+

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.