← All setups

Lazy Anchored Extra Proximal — Monotone Equations with Lipschitz Jacobians

Descriptions may be stale. Consult the linked Lean sources.

Monotone Equations with Lipschitz Jacobians · Lean proof

Monotone Equations with Lipschitz 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 F′ is L-Lipschitz in operator norm, where L≥0, and a given point x0∈E lies within distance D>0 of a zero x⋆. Two exact oracles return F(x) and F′(x), respectively, at x∈E. For a tolerance ε>0, the goal is an output x¯∈E satisfying ∥F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The equation to be solved is F(x)=0,x∈E. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The Jacobian F′(x):E→E is the Fréchet derivative, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, L, D, ε, and an integer parameter m≥1.

Our assumptions:

Assumption 1 (Monotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥0.

Assumption 2 (Lipschitz Jacobian). The map F is Fréchet differentiable everywhere on E, and ∥F′(x)−F′(y)∥op≤L∥x−y∥,x,y∈E.

Assumption 3 (Initial distance to a zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤D.

Both oracles accept queries at any point of E. Calls to the map oracle and the Jacobian oracle are counted separately. After the allotted calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Proved result

Oracle 0:32768⋅(m+1)⋅(⌈(L⋅D2m⋅ε)25⌉++1)⋅(log2(m⋅(⌈(L⋅D2m⋅ε)25⌉++1))+1)2 Oracle 1:⌈(L⋅D2m⋅ε)25⌉++1

OracleTemplate.Convergence LongTails.Setups.UnconstrainedLipschitzJacobianMonotone.spec
  LongTails.Theorems.LazyAnchoredExtraProximal.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.