← All setups

Tail-Oblivious Monotone Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Tail-Oblivious Monotone Root Finding

We seek a zero of a monotone, L-Lipschitz operator F:E→E on a finite-dimensional real inner product space E, where L>0. A given point x0∈E lies within distance R≥0 of a zero x⋆. The oracle returns an unbiased random vector estimating F(x) at each query x, using independent, identically distributed samples, with centered α-moment at most σα, where 1<α≤2 and σ≥0. The algorithm knows only E, x0, and L. For ε>0, the goal is a measurable output x¯∈E satisfying EP∥F(x¯)∥α≤εα, where P is the joint law of independent algorithm and oracle randomness.

The root-finding problem is find x∈E such that F(x)=0. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The parameters α, σ, R, and ε may enter the oracle-call budget, but are not algorithm inputs.

Our assumptions:

Assumption 1 (Monotonicity and Lipschitz continuity). For all x,y∈E, ⟨F(x)−F(y),x−y⟩≥0,∥F(x)−F(y)∥≤L∥x−y∥.

Assumption 2 (Nearby zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R.

Assumption 3 (Heavy-tailed stochastic oracle). Let Ω be a measurable sample space and ν a probability measure on Ω. There is a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−F(x)∥α is integrable under ν, with Eξ∼ν[g(x,ξ)]=F(x),Eξ∼ν[∥g(x,ξ)−F(x)∥α]≤σα. At call k≥0, a query xk∈E receives g(xk,ξk), where the measurable sample variables (ξk)k≥0 are mutually independent and each has law ν. The sample sequence is independent of the algorithm’s randomness.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable, its residual moment ∥F(x¯)∥α must be integrable under P, and it must satisfy EP[∥F(x¯)∥α]≤εα.

Results

A finite-dimensional real inner-product space; a monotone, globally L-Lipschitz operator F, L>0, with F(x⋆)=0 and ∥x0−x⋆∥≤R. IID samples have law p and joint law P. The jointly measurable oracle g is integrable, ∫g(x,ω)dp=F(x), and its integrable central moment satisfies ∫∥g(x,ω)−F(x)∥αdp≤σα, 1<α≤2, R,σ≥0. Target: ∫∥F(Z)∥αdP≤εα, ε>0, for the constructed method’s last completed epoch Z. Only x0,L are public inputs; the stopping budget depends on α,σ,R,ε.

Monotone root finding with tail-oblivious updates: TailObliviousMonotoneRootFinding.
Result Oracle complexity Novelty Limitations
(1) TailObliviousRootFinding (Ours) (⋆⋆⋆) (review) O((1+LR/ε)b4ℓ2+220/(α−1)(σ/ε)b(64b2ℓ)2b)
(2) RAIN (Chen and Luo 2025), Thm. 4.2; finite-variance restriction α=2 O((1+LR/ε)(1+log⁡h)+(σ/ε)2h3) for ∫∥F(Z)∥dP≤ε. (1): Scope extends to infinite variance (α<2). Updates need no α,σ,R,ε; stopping still does. At α=2, matches polynomial rate and strengthens residual to second moment. (1) at α=2: deterministic factor ℓ2 instead of 1+log⁡h; noise factor ℓ4 instead of h3.
(3) Clipped-SEG (Sadiev et al. 2023), Thm. G.2 O(1+LR2δlog(e+LR2δβ)+(σRδ)blog(e+σRδβ)) for P{GapR(x¯)≤δ}≥1−β. (1): No clipping or α,σ,R,ε in updates. Certifies residual instead of restricted gap; rates are not comparable. (1): Expectation only; needs global assumptions instead of assumptions on B4R(x⋆). No proved bound on ∥Z−x⋆∥ converts its residual guarantee to this gap.

Abbr: Costs count individual stochastic operator calls, including all stages and batches. b=α/(α−1); ℓ=1+log⁡(1+LR/ε+σ/ε); h=1+log⁡(1+LR/ε). δ>0 is gap accuracy, 0<β<1 is failure probability, x¯ is the averaged extragradient point, and GapR(x)=sup∥y−x⋆∥≤R⟨F(y),x−y⟩.

Chen, Lesi, and Luo Luo. 2025. Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization. https://doi.org/10.48550/arXiv.2208.05925.
Sadiev, Abdurakhmon, Marina Danilova, Eduard Gorbunov, et al. 2023. High-Probability Bounds for Stochastic Optimization and Variational Inequalities: The Case of Unbounded Variance. https://doi.org/10.48550/arXiv.2302.00999.

Lean setup