← All setups

Universal Holder Monotone — Zeros of Hölder Monotone Operators

Descriptions may be stale. Consult the linked Lean sources.

Zeros of Hölder Monotone Operators · Lean proof

Zeros of Hölder Monotone Operators

We seek a zero of a monotone operator F:E→E on a finite-dimensional real inner product space E. The operator satisfies a mixed Lipschitz–Hölder bound with constants L,H≥0 and exponent α∈(0,1]. A given point x0∈E lies within distance R>0 of a zero x⋆ of F. These regularity parameters and R are hidden from the algorithm. The oracle returns F(x) at x. For ε>0, the goal is an output x¯∈E satisfying ∥F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The problem is to find x⋆∈Esuch thatF(x⋆)=0. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The algorithm receives only E, x0, a radius parameter r0, and ε, where 0<r0≤R; the parameters L,H,α,R may enter only the oracle-call budget.

Our assumptions:

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

Assumption 2 (Mixed Lipschitz–Hölder continuity). For every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥+H∥x−y∥α.

Assumption 3 (Initial distance to a zero). There exists a zero x⋆ of F satisfying ∥x0−x⋆∥≤R.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Proved result

⌈40⋅(16⋅L⋅Rε+2⋅(8⋅H⋅Rαε)1α+log2⁡(Rr0)+2)⋅log⁡((32⋅L⋅Rε+4⋅(8⋅H⋅Rαε)1α+4)⋅Rr0)⌉+

OracleTemplate.Convergence LongTails.Setups.HolderMonotone.spec OracleTemplate.HolderMonotone.budget

Relevant previous results

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