← All setups

Zeros of Hölder Monotone Operators

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a finite-dimensional real inner-product space, F:E→E is monotone and satisfies ∥F(x)−F(y)∥≤L∥x−y∥+H∥x−y∥α, with L,H≥0 and 0<α≤1. A zero x⋆ satisfies ∥x0−x⋆∥≤R, and 0<r0≤R, ε>0. The exact oracle returns F(x); the target is ∥F(x^)∥≤ε. Result (1) uses only x0,r0,ε and returns a stopped iterate deterministically; the setup imposes no algorithm restriction.

Monotone root finding under mixed Lipschitz–Hölder continuity: HolderMonotone.
Result Oracle complexity Novelty Limitations
(1) UniversalHolderMonotone (Ours) (⋆⋆) (review) O((S+log⁡ρ)[1+log⁡(Sρ)])
(2) PolyakEG-LS (Yoon et al. 2026), Thm. 3.4(12), Prop. 3.5. O(1+R2(2M/ε)2/ν+(λR/ε)2+log+(2M)1/νλε(1−ν)/ν). Pure Hölder: L=0, (M,ν)=(H,α); pure Lipschitz: H=0, (M,ν)=(L,1). (1): For L=0, α=1/2, H=R=r0=1, fixed λ, ε↓0: O(ε−2log⁡(1/ε)) instead of O(ε−4). Scope: mixed continuity. Matches parameter-free updates. At H=0, fixed L,R,r0,λ, ε↓0: O(ε−1log⁡(1/ε)) instead of O(ε−2).
(3) Fast composite extragradient (Zhang 2026), Thm. 2. OH,R,α(1+[ε−2ℓα]1/(3α−1)). Comparison: L=0, G=0, one Hölder operator, α>1/3. Parameter dependence not explicit. (1): Fixed H,R,r0, 1/3<α<1, ε↓0: exponent 1/α instead of 2/(3α−1); no knowledge of H,α. Also covers α≤1/3. (1): Stopped rather than last iterate; extra logarithm at α=1. Equations in finite dimension rather than Hilbert-space inclusions with sums of operators.
(4) Tseng splitting (Zhang 2026), Thm. 1. OH,R,α(1+[ε−2ℓα]1/α). Comparison: L=0, G=0, one Hölder operator. Parameter dependence not explicit. (1): Fixed H,R,r0,α, ε↓0: exponent 1/α instead of 2/α, up to logarithms; no knowledge of H,α. (1): Equations in finite dimension rather than Hilbert-space inclusions with sums of operators.
(5) Anchored extragradient (Yoon and Ryu 2021), Cor. 2, Sec. 2.3. O(1+LR/ε). Special case H=0; known L. (1): No knowledge of L; scope extends to mixed Lipschitz–Hölder continuity. (1): Logarithmic overhead at H=0 (also radius-guess overhead); stopped rather than last iterate.

Abbr: S=1+LR/ε+(8HRα/ε)1/α; ρ=R/r0; ℓα=1+(1−α)log+⁡(1/ε); log+⁡t=max{0,log⁡t}, with log+⁡0=0. Costs count all evaluations of F, including rejected trials. In (2), λ>0 is the initial inverse-step estimate; line-search constants are fixed at A=1/2, β=3. In (3), (4), G is the set-valued inclusion term; OH,R,α holds these parameters fixed.

Yoon, TaeHo, Sayantan Choudhury, Ezra Greenberg, and Nicolas Loizou. 2026. Polyak-Type Extragradient Methods for Monotone Root-Finding Problems. https://doi.org/10.48550/arXiv.2609.26581.
Yoon, Taeho, and Ernest K. Ryu. 2021. “Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm.” In Proceedings of the 38th International Conference on Machine Learning, edited by Marina Meila and Tong Zhang, vol. 139. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v139/yoon21d.html.
Zhang, Yi. 2026. Convergence Rates of Tseng’s Splitting Method and Its Acceleration Schemes for Monotone Inclusion Problem with a Sum of Hölder Continuous Operators. https://doi.org/10.48550/arXiv.2606.22392.

Lean setup