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
The fixed-point problem is to find
Our assumptions:
Assumption 1 (Nonexpansiveness). For all
Assumption 2 (Additive Gaussian noise). At call
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
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AdditiveCubeFixedPointLowerBound
(Ours) |
Lower bound: |
||
| (2) (Diakonikolas et al. 2026,
Thm. 11), exact oracle ( |
Lower bound: |
(1) strengthens the
Gaussian-class lower bound by a factor of order |
(1) loses a factor |
| (3) (Diakonikolas et al. 2026, Thm. 13, Rem. 14), query-dependent Bernoulli oracle | Lower bound: |
(1) proves hardness even
for fixed additive Gaussian noise, |
On their respective noise families, the
noise term in (1) is smaller by |
Abbr: