← All setups

Adjoint Anchored Cohypomonotone — Cohypomonotone Root Finding with Adjoints

Descriptions may be stale. Consult the linked Lean sources.

Cohypomonotone Root Finding with Adjoints · Lean proof

Cohypomonotone Root Finding with Adjoints

We seek a zero of a differentiable map F:E→E on a finite-dimensional real inner product space E. The map is L-Lipschitz and ρ-cohypomonotone, and its derivative J(x):E→E is L2-Lipschitz, where L>0, L2≥0, and ρ≥0. A given point x0∈E lies within distance R≥0 of a zero. The oracle returns F(x) or the adjoint product J(x)∗w for x,w∈E. For ε>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. The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives only E, L, L2, ρ, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Differentiability and Lipschitz bounds). The map F is Fréchet differentiable at every x∈E, with derivative J(x). For every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥,∥J(x)−J(y)∥op≤L2∥x−y∥.

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.

Oracle queries may use any x,w∈E. Both reply types are exact, with the adjoint characterized by ⟨J(x)∗w,h⟩=⟨w,J(x)h⟩,h∈E. Each evaluation of F(x) or J(x)∗w counts as one call toward a shared oracle-call budget. After the allotted calls, the output must satisfy ∥F(x¯)∥≤εP-a.s.

Proved result

⌈(4⋅L⋅R(1+ρ⋅L)⋅ε+2)⋅(5+8⋅(2+2⋅ρ⋅L)2⋅log⁡(11+10⋅ρ⋅L))+128⋅(1+2⋅ρ⋅L)2⋅(2+2⋅ρ⋅L)2⋅L2⋅R⋅(4+log⁡(1+4⋅L⋅Rε))2L⌉+

OracleTemplate.Convergence LongTails.Setups.CohypomonotoneAdjoint.spec
  OracleTemplate.CohypomonotoneAdjoint.AdjointAnchoredCohypomonotone.budget

Relevant previous results

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