在1比特通信约束下，实现各类分布尾部的最优均值估计。
Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
- 基于随机阈值查询的自适应估计方法，仅用1比特反馈。
- 样本复杂度在所有尾部条件下都达到理论最优，$k=2$时有额外对数惩罚。
- 适用于未知方差、预算或需降低通信量的场景，适合资源受限应用。
本文研究1比特通信约束下的均值估计问题。提出一种仅依赖随机阈值查询的新型自适应估计器，每个1比特输出表示样本是否超过逐次选择的阈值。该估计器对任意具有有界均值 $μ∈ [-λ, λ]$ 且 $k$ 阶中心矩 $\mathbb{E}[|X-μ|^k] \le σ^k$（$k>1$ 固定）的分布均满足 $(ε, δ)$-PAC。其样本复杂度在所有此类尾部类型中均为阶最优：当 $k≠2$ 时，复杂度与无量化极小极大下界一致，仅多出 $O(\log(λ/σ))$ 的定位成本；当 $k=2$（有限方差）时，多出 $O(\log(σ/ε))$ 的乘性惩罚，我们建立了新信息论下界证明此为1比特量化的根本限制。此外，揭示显著的自适应差距：无论阈值查询还是更一般的区间查询，任何非自适应估计器的样本复杂度必须随 $λ/σ$ 线性增长，远劣于本方法。最后提出多种算法变体，分别处理未知采样预算、未知尺度参数 $σ$（在可能松散的界内）、仅两阶段自适应即可达阶最优、以及每1比特查询使用多个局部样本以成比例降低通信开销。
原文摘要 · Abstract (English)
In this paper, we study the problem of mean estimation under 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is $(ε, δ)$-PAC for any distribution with a bounded mean $μ\in [-λ, λ]$ and a bounded $k$-th central moment $\mathbb{E}[|X-μ|^k] \le σ^k$ for any fixed $k > 1$. Moreover, our sample complexity is order-optimal in all such tail regimes, i.e., for every such $k$ value. For $k \neq 2$, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable $O(\log(λ/σ))$ localization cost. For the finite-variance case ($k=2$), our estimator's sample complexity has an extra multiplicative $O(\log(σ/ε))$ penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter $λ/σ$, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter $σ$ given (possibly loose) bounds, (iii) require only two stages of adaptivity to achieve order-optimal sample complexity at the expense of more general 1-bit queries, and (iv) leverage multiple local samples per 1-bit query to proportionally reduce communication costs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。