← All setups

Cohypomonotone Newton Acceleration — Cohypomonotone Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Cohypomonotone Root Finding · Lean proof

Cohypomonotone Root Finding

We consider finding a zero of a differentiable map F:E→E on a finite-dimensional real inner product space E. The map is ρ-cohypomonotone, where ρ≥0, and its derivative J(x)=DF(x) is H-Lipschitz in operator norm, where H>0. A given starting point x0∈E lies within distance R>0 of a zero x⋆ of F. The oracle returns (F(x),J(x)) at x. 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 root-finding problem is to find x∈E such that F(x)=0. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm; ∥⋅∥op denotes the induced operator norm for linear maps from E to E. The algorithm receives E, H, ρ, R, ε, and x0.

Our assumptions:

Assumption 1 (Lipschitz derivative). The map F is Fréchet differentiable everywhere on E, with derivative J(x):E→E, and ∥J(x)−J(y)∥op≤H∥x−y∥,x,y∈E.

Assumption 2 (Cohypomonotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥−ρ∥F(x)−F(y)∥2.

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

Queries may be made at any point of E, and both components of the oracle reply are exact. After the allotted oracle calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Proved result

⌈100000000000000⋅((1+ρ⋅H⋅R)2+(1+H⋅R2ε)25)⋅(1+log⁡(2+ρ⋅H⋅R+H⋅R2ε))2⌉+

OracleTemplate.Convergence LongTails.Setups.CohypomonotoneNewton.spec
  LongTails.Theorems.CohypomonotoneNewtonAcceleration.budget

Relevant previous results

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