Stochastic Smooth Banach Fixed Point — Stochastic Banach Fixed Points
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Banach Fixed Points · Lean proof
Stochastic
Banach Fixed Points
We consider finding a fixed point of a nonexpansive map on a finite-dimensional real
Banach space with a smooth
squared norm controlled by .
A given point is within
distance of a fixed point.
At , the oracle returns an
unbiased estimate of using a
fresh independent sample, with expected squared error at most , where . For , the goal is a
measurable output with
,
where is the joint law of
sampling and independent algorithm randomness.
The fixed-point problem is to find such that Write
for the norm on and for its continuous real dual.
Operator norms are the induced operator norms. The algorithm receives
, the measurable sample space
, , , , , and ; it accesses through the stochastic oracle.
Our assumptions:
Assumption 1 (Smooth squared norm). There exists a
continuous map such
that, for every ,
Assumption 2 (Nonexpansiveness and initial
distance). The map satisfies
There exists such that
Assumption 3 (Stochastic 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 random
variables are
mutually independent with common law , and the entire 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 squared fixed-point residual must be integrable under , and it must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.StochasticSmoothBanachFixedPoint.spec
LongTails.Theorems.StochasticSmoothBanachFixedPoint.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.