The Cost of Working Memory in Streaming Mean Estimation
Abstract
A streaming estimator must compute from the evidence that fits in memory. We determine when storing an accurate mean is easier than computing it. For Gaussian mean estimation over the Euclidean unit ball in ℝd, we establish the minimax rate under squared error with K persistent states, a known horizon, and a public time index: min{1, K−2/d+d/n (1+log(ed)/(1+(log K)/d))}. Unrestricted computation followed by K-level encoding has rate min{1,d/n+K−2/d}. At a fixed sufficiently small error, statistically optimal sample size therefore requires order dlog d working bits, while order d bits suffice to store the answer. The lower bound tracks repeated state compression through an entropy potential obtained by Gaussian smoothing. A matching construction combines a multiscale modular counter with workspace reused across coordinate groups. In one dimension, it attains the terminal rate n−1+K−2. Any fixed confidence requirement that the realized loss not exceed the zero baseline preserves these rates. Increasing confidence creates a further memory requirement: at fixed nontrivial risk in every fixed dimension, failure probability e−γn requires and permits order log n working states for sufficiently small fixed γ>0. In the scalar problem, a fixed terminal alphabet suffices under the same protection. These bounds separate the memory needed to represent an answer from the memory needed to accumulate evidence and validate a decision.
Related
- Estimation and Inference for One-pass Streaming Function-on-Function Regression
- A Memory-Magic Exchange Law in Streaming Clifford+T Compilation
- Working memory, mathematics motivation, and problem solving in English learners with and without risk for mathematics learning difficulties: evidence from a high-poverty urban district
- Optimal guaranteed sequential estimation for mean-reverting CEV diffusions
- Mean-variance portfolio selection: connections between mean-field systems and forward-backward stochastic systems under initial-terminal cost coupling
BibTeX
@misc{wu2026cost,
title = {{The Cost of Working Memory in Streaming Mean Estimation}},
author = {Zeyu Wu and Zihao Wang and Minghua Deng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39540},
eprint = {2610.39540},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39540},
}
RIS
TY - UNPB
TI - The Cost of Working Memory in Streaming Mean Estimation
AU - Zeyu Wu
AU - Zihao Wang
AU - Minghua Deng
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39540
UR - https://arxiv.org/abs/2610.39540
AB - A streaming estimator must compute from the evidence that fits in memory. We determine when storing an accurate mean is easier than computing it. For Gaussian mean estimation over the Euclidean unit ball in ℝ^d, we establish the minimax rate under squared error with K persistent states, a known horizon, and a public time index: min{1, K^−2/d+d/n (1+log(ed)/(1+(log K)/d))}. Unrestricted computation followed by K-level encoding has rate min{1,d/n+K^−2/d}. At a fixed sufficiently small error, statistically optimal sample size therefore requires order dlog d working bits, while order d bits suffice to store the answer. The lower bound tracks repeated state compression through an entropy potential obtained by Gaussian smoothing. A matching construction combines a multiscale modular counter with workspace reused across coordinate groups. In one dimension, it attains the terminal rate n^−1+K^−2. Any fixed confidence requirement that the realized loss not exceed the zero baseline preserves these rates. Increasing confidence creates a further memory requirement: at fixed nontrivial risk in every fixed dimension, failure probability e^−γn requires and permits order log n working states for sufficiently small fixed γ>0. In the scalar problem, a fixed terminal alphabet suffices under the same protection. These bounds separate the memory needed to represent an answer from the memory needed to accumulate evidence and validate a decision.
ER -