← All setups

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 F:Rd→Rd, where d is a nonnegative integer and the space has its Euclidean inner product and norm. Its Jacobian JF is globally L-Lipschitz, with L>0, and a given point x0 lies within distance R>0 of a zero x⋆. The oracle returns (F(x),JF(x)) at x. For a tolerance ε>0, the goal is an output x¯ satisfying EP[∥F(x¯)∥]≤ε, where P is the law of the algorithm’s randomness.

The root-finding problem is find x∈Rd such that F(x)=0. The algorithm receives d, x0, L, R, and ε. Write JF(x) for the Fréchet derivative of F at x, a linear operator from Rd to itself; ∥⋅∥op denotes its induced operator norm.

Our assumptions:

Assumption 1 (Parameter regime). The positive parameters L, R, and ε, and the dimension d, satisfy 4096ε≤LR2,d≥4096(⌊(LR24096ε)2/5⌋+2)5.

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

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

Queries may be made at any point of Rd, 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 EP[∥F(x¯)∥]≤ε.

Proved result

⌊(L⋅R24096⋅ε)25⌋+

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.