← All setups

Additive Cube Fixed Point Lower Bound — Cube Fixed Points with Gaussian Noise

Descriptions may be stale. Consult the linked Lean sources.

Cube Fixed Points with Gaussian Noise · Lean proof

Cube Fixed Points with Gaussian Noise

We seek an approximate fixed point of a map T:C→C on the cube C=[−R,R]d⊂Rd of radius R>0 and dimension d≥1. The map is nonexpansive in the supremum norm ∥⋅∥∞. At each query x∈C, the oracle returns T(x) plus fresh centered Gaussian noise with independent coordinates of equal variance and bounded expected squared supremum norm. For a tolerance ε>0, the goal is a measurable output x¯∈C satisfying E∥T(x¯)−x¯∥∞≤ε, with expectation over the algorithm and oracle randomness.

The fixed-point problem is to find x∈Csuch thatT(x)=x. The algorithm receives d, R, the noise bound σ≥0, and ε. We consider the parameter range 128ε≤R,⌈R/ε⌉≤d.

Our assumptions:

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

Assumption 2 (Additive Gaussian noise). At call k=0,1,…, a query xk∈C yields the reply T(xk)+Zk∈Rd. For some fixed variance v≥0, the coordinates (Zk,i)k≥0,1≤i≤d are mutually independent with common law N(0,v). The noise sequence is independent of the algorithm’s randomness. Each Zk is Bochner integrable, its squared supremum norm is integrable, and E[Zk]=0,E[∥Zk∥∞2]≤σ2.

The algorithm uses measurable initialization, query, and output rules, and its update is jointly measurable in the current state and reply. After the allotted calls, its cube-valued output must have an integrable fixed-point residual satisfying E[∥T(x¯)−x¯∥∞]≤ε.

Proved result

⌊(1+(σε)22+log⁡(d))⋅max{1,Rε1+log⁡(2+R+σε)}67108864⌋+

OracleTemplate.NonConvergence LongTails.Setups.GaussianAdditiveCubeFixedPoint.spec
  LongTails.Theorems.AdditiveCubeFixedPointLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.