Randomized Global Jacobian Monotone Lower Bound — Monotone Root Finding with Jacobians
Descriptions may be stale. Consult the linked Lean sources.
Monotone Root Finding with Jacobians · Lean proof
Monotone Root Finding with
Jacobians
We consider finding a zero of a differentiable monotone map , where
is a nonnegative integer and the
space has its Euclidean inner product and norm. Its Jacobian is globally -Lipschitz, with , and a given point lies within distance of a zero . The oracle returns at . For a tolerance , the goal is an output
satisfying ,
where is the law of the
algorithm’s randomness.
The root-finding problem is The algorithm
receives , , , , and . Write for the Fréchet derivative of
at , a linear operator from to itself; denotes its
induced operator norm.
Our assumptions:
Assumption 1 (Parameter regime). The positive
parameters , , and , and the dimension , satisfy
Assumption 2 (Monotonicity and Jacobian regularity).
The map is Fréchet differentiable
everywhere, and for every ,
Assumption 3 (Nearby zero). There exists such that
Queries may be made at any point of , and each oracle call
returns both the exact map value and the exact Jacobian. After the
allotted calls, the output must have an integrable residual norm and
satisfy
Proved result
OracleTemplate.NonConvergence LongTails.Setups.GlobalJacobianMonotoneExpected.spec
LongTails.Theorems.RandomizedGlobalJacobianMonotoneLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.