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,
The root-finding problem is
Our assumptions:
Assumption 1 (Monotonicity and Lipschitz
continuity). For all
Assumption 2 (Nearby zero). There exists
Assumption 3 (Heavy-tailed stochastic oracle). Let
Queries may be made at any point of
Results
A finite-dimensional real inner-product space; a monotone, globally
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) TailObliviousRootFinding
(Ours) |
|||
| (2) RAIN (Chen and Luo 2025),
Thm. 4.2; finite-variance restriction |
(1): Scope extends to
infinite variance ( |
(1) at |
|
| (3) Clipped-SEG (Sadiev et al. 2023), Thm. G.2 | (1): No clipping or |
(1): Expectation only;
needs global assumptions instead of assumptions on |
Abbr: Costs count individual stochastic operator
calls, including all stages and batches.