Additive Cube Fixed Point — Noisy Fixed Points on a Cube
Descriptions may be stale. Consult the linked Lean sources.
Noisy Fixed Points on a Cube · Lean proof
Noisy Fixed
Points on a Cube
We seek an approximate fixed point of a map on the cube , where
is a positive integer and . The map is nonexpansive in the
maximum norm . At
each query , the oracle
returns plus an independent
draw of centered additive noise with bounded second moment in this norm.
For a tolerance ,
the goal is an output
satisfying ,
averaging over oracle and algorithm randomness.
The fixed-point problem is The algorithm receives , , , and the noise bound specified below.
Our assumptions:
Assumption 1 (Nonexpansiveness). For every ,
Assumption 2 (Additive noise). At query , the oracle returns . The noise
vectors are
independent random variables with common law on , and the sequence is
independent of the algorithm’s randomness. For , the vector is Bochner integrable, is integrable, and
The algorithm uses a measurable initialization, query rule, and
output rule, with an update jointly measurable in its current state and
the oracle reply. After the allotted calls, its output must be a measurable -valued random vector with integrable
residual satisfying
Proved result
OracleTemplate.Convergence LongTails.Setups.AdditiveCubeFixedPoint.spec LongTails.Theorems.AdditiveCubeFixedPoint.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.