← All setups

Noisy Fixed Points on a Cube

Descriptions may be stale. Consult the linked Lean sources.

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

Results

Let T:C→C be nonexpansive in the sup norm on C=[−R,R]d. A measurable policy knows d≥1, R,ε>0 and σ≥0. Each query at x∈C returns T(x)+Z, with fresh IID noise satisfying EZ=0 and E∥Z∥∞2≤σ2. The target is a measurable X∈C with E∥T(X)−X∥∞≤ε.

Sufficient oracle-call budgets for fixed-point residuals on a cube with additive noise.
Result Oracle complexity Novelty Limitations
(1) AdditiveCubeFixedPoint (Ours) (review) O(1{R>ε}Rε(1+σ2log⁡(2d)ε2))
(2) Dual Halpern (Lee 2026, Thm. 3), derived bound O(Rε(1+σ2log⁡(2d)ε2)) for ε≤R (1) formalizes the rate of (2) for a different anchored batch-mean method. Apply (2) to T∘clipC from 0, bound initial distance by R, and clip the output. (1) requires additive noise on a cube. (2) allows query-dependent unbiased noise with bounded variance.
(3) Recursive anchoring (Diakonikolas et al. 2026, Cor. 6), p=∞ O(Rε(1+log⁡s)(s+log⁡(1/δ))⋅(1+s2σ2log⁡(2d)ε2)) for ε≤R (1) avoids the accuracy logarithms for expected residual. (3) controls a residual quantile, so the costs are incomparable. (3) guarantees residual ≤ε with probability 1−δ or higher and allows unbiased, query-dependent noise on compact convex domains with a Lipschitz retraction.
(4) Minibatch Halpern (Bravo and Contreras 2026, arXiv v4, Cor. 3.5), derived bound O([u(1+log⁡u)]5) for ε<R (1) reduces the accuracy dependence from O(ε−5log5⁡(1/ε)) to O(ε−3) for fixed d,R,σ>0 as ε→0. (2) already attains this rate.

Abbr: clipC denotes coordinatewise clipping to C. s=1+log⁡(R/ε), δ∈(0,1) is the failure probability, and u=max{R,dσ}/ε uses E∥Z∥22≤dσ2.

Bravo, Mario, and Juan Pablo Contreras. 2026. “Stochastic Halpern Iteration in Normed Spaces and Applications to Reinforcement Learning.” Mathematical Programming, ahead of print. https://doi.org/10.1007/s10107-026-02345-1.
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.
Lee, Jongmin. 2026. Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces. https://doi.org/10.48550/arXiv.2610.26484.

Lean setup