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
The fixed-point problem is
Our assumptions:
Assumption 1 (Nonexpansiveness). For every
Assumption 2 (Additive noise). At query
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
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AdditiveCubeFixedPoint (Ours) (review) | |||
| (2) Dual Halpern (Lee 2026, Thm. 3), derived bound | (1) formalizes the rate
of (2) for a different anchored batch-mean method.
Apply (2) to |
(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), |
(1) avoids the accuracy logarithms for expected residual. (3) controls a residual quantile, so the costs are incomparable. | (3) guarantees residual
|
|
| (4) Minibatch Halpern (Bravo and Contreras 2026, arXiv v4, Cor. 3.5), derived bound | (1) reduces the accuracy
dependence from |
Abbr: