Inertial Monotone Residual — Stochastic Lipschitz Monotone Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Lipschitz Monotone Root Finding · Lean proof
Stochastic Lipschitz
Monotone Root Finding
We seek a zero of a monotone, -Lipschitz operator on a finite-dimensional real
Hilbert space , where . A given point lies within distance of a zero . At each query, the oracle
returns an unbiased estimate of with mean squared error at most
, where , using independent,
identically distributed samples. For , the goal is a
measurable output with
integrable squared residual satisfying ,
where expectation includes oracle and independent algorithm
randomness.
The root-finding problem is Write for the inner
product on and for its induced norm. Let be the measurable sample space.
The algorithm receives , , , , , , and ; it accesses through the oracle.
Our assumptions:
Assumption 1 (Monotonicity and Lipschitz
continuity). For every ,
Assumption 2 (Nearby zero). There exists such that
Assumption 3 (Stochastic operator oracle). There
exist a probability measure on
and a jointly measurable map
. For every
, the map is Bochner integrable under
, the squared error is integrable, and
At call , a query receives the reply . The measurable sample
variables are
mutually independent with common law under a joint probability law on
. Algorithm
randomness is independent of this sample sequence.
Queries may be made at any point of . Let denote the joint law of the algorithm
randomness and oracle samples. After the allotted oracle calls, the
output must be measurable,
its squared residual must be integrable under , and
Proved result
OracleTemplate.Convergence LongTails.Setups.StochasticLipschitzMonotone.spec
LongTails.Theorems.InertialMonotoneResidual.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.