← All setups

Hessian Stable Skew Newton — Hessian-Stable Skew Monotone Equations

Descriptions may be stale. Consult the linked Lean sources.

Hessian-Stable Skew Monotone Equations · Lean proof

Hessian-Stable Skew Monotone Equations

We seek a zero of a differentiable map F:E→E on a finite-dimensional real inner product space E. Its Jacobian has a constant skew-adjoint part and a positive semidefinite symmetric part with exponential stability parameter M>0. A given point x0∈E lies within distance D>0 of a zero x⋆, around which the Jacobian satisfies a local bound with hidden constant Λ≥0. Two exact oracles return F(x) and its Jacobian J(x)=DF(x). For ε>0, the goal is an output x¯∈E with ∥F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The underlying equation is F(x)=0,x∈E. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm; ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, M, D, and ε; Λ may enter the oracle-call budgets but is not an algorithm input.

Our assumptions:

Assumption 1 (Skew decomposition and multiplicative stability). The map F is Fréchet differentiable everywhere on E. There exists a fixed linear operator S:E→E such that, with H(x)=J(x)−S, for every x,y,u,v∈E, ⟨Sv,v⟩=0,⟨H(x)u,v⟩=⟨u,H(x)v⟩,⟨H(x)v,v⟩≥0,⟨H(y)v,v⟩≤eM∥y−x∥⟨H(x)v,v⟩.

Assumption 2 (Nearby zero and local Jacobian bound). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤D. Around this same zero, the full Jacobian satisfies ∥J(x)∥op≤Λwhenever∥x−x⋆∥≤3D+14M.

Queries to either oracle may be made at any point of E. A value-oracle call returns F(x), and a Jacobian-oracle call returns the full linear operator J(x):E→E; the two types of calls are counted separately. After the allotted calls, the required residual accuracy is ∥F(x¯)∥≤εP-a.s.

Proved result

Oracle 0:⌈217⋅(1+(M⋅D)23)⋅(log⁡(3+M⋅D+M⋅Λ⋅(D+1M)2ε))3⌉+ Oracle 1:⌈217⋅(1+(M⋅D)23)⋅(log⁡(3+M⋅D+M⋅Λ⋅(D+1M)2ε))3⌉+

OracleTemplate.Convergence LongTails.Setups.HessianStableSkewMonotone.spec
  LongTails.Theorems.HessianStableSkewNewton.budget

Relevant previous results

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