← All setups

Hidden Potential Oracle Complexity — Strongly Monotone Hidden-Potential Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Strongly Monotone Hidden-Potential Root Finding · Lean proof

Strongly Monotone Hidden-Potential Root Finding

We seek a zero of a map F:E→E on a real Hilbert space E. The map is μ-strongly monotone, where μ>0, and admits a hidden differentiable potential φ:E→R whose gradient is L-Lipschitz, with L≥0, while F−∇φ is s-Lipschitz, with s≥0. A given point x0∈E lies within distance R≥0 of a zero x⋆. The oracle returns F(x) at x. For ε>0, the goal is an output x¯∈E satisfying ∥x¯−x⋆∥≤ε almost surely under P, the law of the algorithm’s randomness.

The root-finding problem is find x⋆∈E such that F(x⋆)=0. Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, x0, μ, L, s, R, and ε; the potential φ is not supplied.

Our assumptions:

Assumption 1 (Strong monotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥μ∥x−y∥2.

Assumption 2 (Hidden potential). There exists an everywhere Fréchet differentiable function φ:E→R such that, for every x,y∈E, ∥∇φ(x)−∇φ(y)∥≤L∥x−y∥,∥(F−∇φ)(x)−(F−∇φ)(y)∥≤s∥x−y∥.

Assumption 3 (Initial distance). There exists x⋆∈E satisfying F(x⋆)=0,∥x0−x⋆∥≤R.

Queries may be made at any point of E. Strong monotonicity makes the zero x⋆ unique. After the allotted oracle calls, the output must satisfy ∥x¯−x⋆∥≤εP-a.s.

Proved result

⌈2097152⋅(μ+s)⋅(L+μ+s)μ⋅log⁡(2+sμ)⋅log⁡(2+Rε)⌉+

OracleTemplate.Convergence LongTails.Setups.HiddenPotentialStronglyMonotone.spec OracleTemplate.HiddenPotential.budget

Relevant previous results

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