← All setups

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 T:C→C on the cube C=[−R,R]d⊂Rd, where d is a positive integer and R>0. The map is nonexpansive in the maximum norm ∥⋅∥∞. At each query x∈C, the oracle returns T(x) plus an independent draw of centered additive noise with bounded second moment in this norm. For a tolerance ε>0, the goal is an output x¯∈C satisfying E[∥T(x¯)−x¯∥∞]≤ε, averaging over oracle and algorithm randomness.

The fixed-point problem is find x∈C such that T(x)=x. The algorithm receives d, R, ε, and the noise bound σ≥0 specified below.

Our assumptions:

Assumption 1 (Nonexpansiveness). For every x,y∈C, ∥T(x)−T(y)∥∞≤∥x−y∥∞.

Assumption 2 (Additive noise). At query xk∈C, the oracle returns T(xk)+Zk∈Rd. The noise vectors (Zk)k≥0 are independent random variables with common law μ on Rd, and the sequence is independent of the algorithm’s randomness. For Z∼μ, the vector Z is Bochner integrable, ∥Z∥∞2 is integrable, and E[Z]=0,E[∥Z∥∞2]≤σ2.

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 x¯ must be a measurable C-valued random vector with integrable residual satisfying E[∥T(x¯)−x¯∥∞]≤ε.

Proved result

{0R≤ε⌈4096⋅Rε⋅(1+2097152⋅log⁡(2⋅d)⋅(σε)2)⌉+otherwise

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.