Tail Oblivious Root Finding — Tail-Oblivious Monotone Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Tail-Oblivious Monotone Root Finding · Lean proof
Tail-Oblivious Monotone Root
Finding
We seek a zero of a monotone, -Lipschitz operator on a finite-dimensional real
inner product space , where . A given point lies within distance of a zero . The oracle returns an unbiased
random vector estimating at
each query , using independent,
identically distributed samples, with centered -moment at most , where and . The algorithm knows only
, , and . For , the goal is a
measurable output
satisfying ,
where is the joint law of
independent algorithm and oracle randomness.
The root-finding problem is Write for the inner
product and for its
induced norm. The parameters , , , and may enter the oracle-call
budget, but are not algorithm inputs.
Our assumptions:
Assumption 1 (Monotonicity and Lipschitz
continuity). For all ,
Assumption 2 (Nearby zero). There exists such that
Assumption 3 (Heavy-tailed stochastic oracle). Let
be a measurable sample space
and a probability measure on
. There is a jointly
measurable map . For every , the
map is Bochner
integrable and is integrable
under , with At call , a query receives , where the measurable sample
variables 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 . After the allotted oracle calls, the
output must be measurable,
its residual moment must be integrable
under , and it must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.TailObliviousMonotoneRootFinding.spec
LongTails.Theorems.TailObliviousRootFinding.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.