← All setups

Cube Fixed Points with Gaussian Noise

Descriptions may be stale. Consult the linked Lean sources.

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¯∥∞]≤ε.

Results

Let C=[−R,R]d, R≥128ε>0, d≥⌈R/ε⌉, and σ≥0. The map T:C→C is nonexpansive in ℓ∞. Each query returns T(x)+Z with independent draws Z∼N(0,vId) and E∥Z∥∞2≤σ2. A measurable adaptive randomized algorithm must return x^∈C with E∥T(x^)−x^∥∞≤ε, averaging over oracle and algorithm randomness.

Necessary oracle calls for fixed points on a cube with additive Gaussian noise
Result Oracle complexity Novelty Limitations
(1) AdditiveCubeFixedPointLowerBound (Ours) (⋆⋆⋆) (review) Lower bound: Ω(RεL(1+σ2ε2log⁡d))
(2) (Diakonikolas et al. 2026, Thm. 11), exact oracle (v=0) Lower bound: Ω(R/ε). Failure probability ≥1/4 gives the expected-residual bound after constant rescaling. (1) strengthens the Gaussian-class lower bound by a factor of order σ2/(ε2Llog⁡d) when σ2≫ε2Llog⁡d. (1) loses a factor L when σ2≲ε2log⁡d. It needs d≥⌈R/ε⌉; (2) needs d≥⌊R/(8ε)⌋ at residual threshold ε.
(3) (Diakonikolas et al. 2026, Thm. 13, Rem. 14), query-dependent Bernoulli oracle Lower bound: Ω(R/ε+Rσ2/ε3) on the Bernoulli family. Failure probability ≥1/8. (1) proves hardness even for fixed additive Gaussian noise, v=σ2/[4(2+log⁡d)]. A Gaussian change of measure replaces the information masking in (3). On their respective noise families, the noise term in (1) is smaller by Llog⁡d. The Bernoulli bound in (3) does not apply to Gaussian noise.

Abbr: L=min{R/ε,log⁡((R+σ)/ε)}; log is natural.

Diakonikolas, Jelena, Cristóbal Guzmán, and David Martínez-Rubio. 2026. Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps. https://doi.org/10.48550/arXiv.2609.09524.

Lean setup