← All setups

Hessian-Stable Skew Monotone Equations

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a finite-dimensional real inner-product space, F is differentiable with DF(x)=S+H(x), constant skew-adjoint S, and symmetric positive-semidefinite H(x) satisfying H(y)⪯eM∥y−x∥H(x). A root x⋆ satisfies ∥x0−x⋆∥≤D; ∥DF(x)∥≤Λ on B(x⋆,3D+1/(4M)). Here M,D,ε>0 and Λ≥0. Exact F and DF oracles are available. The constructed deterministic output satisfies ∥F(x^)∥≤ε; Λ is needed only for the budget.

Comparison for HessianStableSkewMonotone.
Result Oracle complexity Novelty Limitations
(1) HessianStableSkewNewton (Ours) (⋆⋆⋆) (review) O((1+(MD)2/3)ℓ3) total F,DF calls.
(2) AEP (Jiang and Yoon 2026), Thms. 4.4, 4.6 O((1+(L2D2/ε)2/5)(1+log⁡(1+L2D2/ε))) total F,DF calls, including trials. Globally L2-Lipschitz DF. (1): Polynomial-to-polylogarithmic accuracy gain on the overlap as ε→0 with fixed instance. Scope: permits non-globally-Lipschitz Jacobians. (1) requires constant skew and Hessian stability; can cost more at moderate accuracy and large MD. Ball-affine VI solves uncharged.
(3) EAG (Yoon and Ryu 2021), Thm. 1, §2.3 O(1+LD/ε) F calls; globally L-Lipschitz monotone F. (1): Lower cost on the overlap when LD/ε≫(1+(MD)2/3)ℓ3. Scope: no global Lipschitz requirement. (1) needs DF queries, constant skew and Hessian stability; ball-affine VI solves uncharged.
(4) MS-BACON (Carmon et al. 2020), Cor. 12 O((1+(MD)2/3)[1+log⁡(1+Δ/δ)][1+log⁡(1+LD2(1+MD)/δ)]3) linear solves; gradient/Hessian calls bounded by this cost. S=0, globally L-smooth, M-QSC objective; gap ≤δ. (1): Scope extends gradient fields to constant skew coupling. Matches the (MD)2/3 power up to logarithms; residual conversion on this overlap uses δ=ε2/(2L).
(5) Regularized Newton (Doikov 2023), Thm. 3.3 O(1+MB[1+log⁡(1+Δ/δ)]+log⁡(1+g0B/δ)) gradient/Hessian calls and linear solves. S=0, M-QSC objective, bounded initial sublevel diameter B; gap ≤δ. (1): Scope extends minimization to constant skew coupling. Rates are not directly comparable using B versus D and objective gap versus residual.

Abbr: ℓ=log⁡(2+MD+MΛ(D+1/M)2/ε); L,L2 are global Lipschitz constants of F,DF, respectively. For minimization, F=∇f, Δ=f(x0)−f(x⋆), g0=∥∇f(x0)∥, δ is objective-gap tolerance, and B=diam{x:f(x)≤f(x0)}. QSC means |D3f(x)[u,u,v]|≤M⟨∇2f(x)u,u⟩∥v∥. VI means variational inequality.

Carmon, Yair, Arun Jambulapati, Qijia Jiang, et al. 2020. Acceleration with a Ball Optimization Oracle. https://doi.org/10.48550/arXiv.2003.08078.
Doikov, Nikita. 2023. Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method. https://doi.org/10.48550/arXiv.2308.14742.
Jiang, Ruichen, and TaeHo Yoon. 2026. Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems. https://doi.org/10.48550/arXiv.2609.30212.
Yoon, TaeHo, and Ernest K. Ryu. 2021. Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm. https://doi.org/10.48550/arXiv.2102.07922.

Lean setup