← All setups

Monotone Roots with Lipschitz Second Derivatives

Descriptions may be stale. Consult the linked Lean sources.

Monotone Roots with Lipschitz Second Derivatives

We consider finding a zero of a twice continuously differentiable monotone map F:E→E on a finite-dimensional real inner product space E. Its second derivative is L-Lipschitz, where L>0. A given point x0∈E satisfies ∥F′(x0)∥op≤H0, where H0≥0, and lies within distance D>0 of a zero x⋆. Here primes denote Fréchet derivatives and ∥⋅∥op denotes the induced operator norm. Two oracles return F(x) and F′(x), respectively. For ε>0, the goal is an output x¯∈E with ∥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. The derivative F′(x) is a linear map from E to E, and F″(x) is a bilinear map from E×E to E; their norms are the induced operator norms. The algorithm receives E, x0, L, D, H0, and ε.

Our assumptions:

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

Assumption 2 (Lipschitz second derivative). The map F is twice continuously Fréchet differentiable on E, and ∥F″(x)−F″(y)∥op≤L∥x−y∥,x,y∈E.

Assumption 3 (Initial bounds). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤D,∥F′(x0)∥op≤H0.

Both oracles are exact and may be queried at any point of E. Calls to the value oracle and the derivative oracle are counted separately. After the allotted calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, F:E→E is C2 and monotone, D2F is globally L-Lipschitz, ∥DF(x0)∥≤H0, and some zero x⋆ satisfies ∥x0−x⋆∥≤D. Here L,D,ε>0 and H0≥0. Exact F,DF queries are available; the target is ∥F(x)∥≤ε, almost surely. Result (1) is deterministic and uses known L,D,H0,ε.

Monotone equations with Lipschitz second derivative: UnconstrainedLipschitzSecondDerivativeMonotone.
Result Oracle complexity Novelty Limitations
(1) HomotopyNewtonMonotone (Ours) (⋆⋆⋆) (review) O((1+(LD3/ε)1/4)ℓ2) total F,DF calls.
(2) AEP tensor (Jiang and Yoon 2026), Thms. 5.2–5.3, p=3 O((1+(LD3/ε)1/4)
⋅[1+log⁡(1+LD3/ε)]) total F,DF,D2F calls, including trials.
(1): Removes D2F queries with dimension-free cost; matches the polynomial residual rate. (1): Extra logarithmic overhead and H0 knowledge; larger proved constant. Unconstrained only; (2) also covers composite inclusions.
(3) AEP Newton (Jiang and Yoon 2026), Thms. 4.4, 4.6 O((1+(L2D2/ε)2/5)
⋅[1+log⁡(1+L2D2/ε)]) total F,DF calls, including trials; requires globally L2-Lipschitz DF.
(1): On the overlap, fixed positive L,L2,D,H0 and ε→0: O(ε−1/4log2⁡(1/ε)) versus O(ε−2/5log⁡(1/ε)). Scope: allows non-Lipschitz DF. (1): Needs Lipschitz D2F and known L,H0; classes incomparable. Can lose when L2 is small. Unconstrained only.

Abbr: DF,D2F: Jacobian and second derivative; ℓ=1+log⁡(1+H0D/ε+LD3/ε). L2: global Jacobian Lipschitz constant. AEP: anchored extra-proximal. Costs count primitive derivative/value calls; linear algebra and model-subproblem solves are uncharged.

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.

Lean setup