技术摘要：未知方差下的单比特分布式均值估计

1. 问题陈述

本研究解决了在极端通信约束下的分布式均值估计 (Distributed Mean Estimation, DME) 问题，其中每个用户仅限于向中央服务器传输一位（1-bit）信息。与以往通常假设方差已知或均值是唯一未知参数的研究不同，本文考虑了尺度-位置族 (scale-location family) 分布，其中均值 ($\mu$) 和方差 ($\sigma^2$) 均为未知。方差被视为一个扰动参数（nuisance parameter）。

该设定涉及 $n$ 个用户，每个用户持有独立同分布 (i.i.d.) 的样本 $X_i$，该样本来自分布 $f_{X,\mu,\sigma}(x) = \frac{1}{\sigma}f_X(\frac{x-\mu}{\sigma})$，其中 $f_X$ 是已知的具有零均值和单位方差的基准密度。目标是设计一个通信协议 $\Pi$（由 $n$ 个编码器和一个解码器组成），使服务器能够以最小的渐近均方误差 (MSE) 来估计 $\mu$。本文区分了以下两种情况：

• 非自适应协议 (Non-adaptive protocols)： 每个用户的比特 $Y_i$ 仅取决于其本地样本 $X_i$。
• 自适应协议 (Adaptive protocols)： 用户的比特 $Y_i$ 可能取决于 $X_i$ 以及先前传输的比特 $Y_1, \dots, Y_{i-1}$（或来自服务器的广播消息）。

2. 方法论与协议

非自适应协议

作者提出了一个简单的两阈值非自适应协议，用于联合估计 $\mu$ 和 $\sigma$。

• 机制： 用户被分为两组，规模分别为 $n_1$ 和 $n_2$。第一组使用阈值 $\theta_1$，第二组使用 $\theta_2$。每个用户传输一个比特，指示其样本是否低于各自的阈值。
• 估计： 服务器计算这些阈值处的经验累积分布函数 (CDF) 值，反转已知的基准 CDF $F_X$，并通过求解方程组来获得粗略估计值 $\hat{\mu}_c$ 和 $\hat{\sigma}_c$。
• 性能： 定理 3.1 证明该协议是强一致且渐近正态的。然而，其渐近 MSE 取决于真实的 $\mu$，并且对于固定的阈值，当 $|\mu| \to \infty$ 时会趋于无界。

论文还引入了一种用于非参数均值估计的多阈值非自适应协议（第 3.4 节），该协议通过黎曼和来近似期望值。然而，作者指出，除非分布的支持集是有界的，否则该方法产生的 MSE 阶数通常比 $O(1/n)$ 更差。

自适应协议

为了克服非自适应方案的局限性，作者设计了一个简单的两轮自适应协议：

1. 第一轮（粗略估计）： 一部分用户（$n_1 + n_2$）执行上述非自适应两阈值协议，以生成粗略估计值 $\hat{\mu}_c$ 和 $\hat{\sigma}_c$。
2. 广播： 服务器将 $\hat{\mu}_c$ 广播给剩余的用户（$n_3$）。
3. 第二轮（精细化）： 剩余的用户使用 $\hat{\mu}_c$ 作为其量化阈值，传输 $Y_i = \mathbb{1}\{X_i < \hat{\mu}_c\}$。
4. 最终估计： 服务器利用新的经验 CDF 值和粗略方差估计值 $\hat{\sigma}_c$ 来精细化最终估计值 $\hat{\mu}_f$。

理论分析（定理 4.1）表明，该方案实现的渐近 MSE 为 $\frac{\sigma^2}{4f_X(0)^2}$，该值与真实的 $\mu$ 无关。

3. 核心贡献与理论结果

非自适应协议的下界

一个主要的贡献是推导了针对对称、严格对数凹分布的任何 1-bit 非自适应协议的通用极小极大 MSE 下界。

• 使用 Le Cam 两点法 和经过改进的平方 Hellinger 距离分析，作者证明了对于任何此类分布，其渐近极小极大 MSE 的下界为：
  $$\lim_{n \to \infty} \sup_{\mu} n \cdot \text{MSE}(\hat{\mu}) \geq \frac{\alpha^* \sigma^2}{T(f_X)}$$
  其中 $\alpha^* \approx 0.1034$，且 $T(f_X)$ 是由密度 $f_X$ 导出的依赖于分布的常数。
• 该界限适用于包括广义高斯族在内的广泛分布类。

自适应协议的最优性

作者证明了其简单的自适应协议对于一大类对称、严格对数凹分布（其中密度满足特定的形状条件）具有信息论最优性。

• 通过使用 Van Trees 不等式 推导出一个匹配的下界，作者证明了任何 1-s bit 自适应协议所能实现的渐近 MSE 都不可能低于 $\frac{\sigma^2}{4f_X(0)^2}$。
• 由于作者的自适应协议达到了这一界限，因此对于这些分布而言，它是最优的。

自适应与非自适应之间的差距

论文展示了对于许多常见分布，自适应协议与非自适应协议之间存在显著的性能差距。

• 对于形状参数 $1 < \beta < 1.85$ 的广义高斯分布 (GGD) 和双曲正割分布，非自适应协议的下界严格大于自适应协议所达到的上界。
• 具体而言，对于 $\beta < 1.85$ 的 GGD，非自适应下界与自适应上界的比值大于 1，这证明了在这些情形下非自适应协议是严格次优的。
• 对于 $\beta > 1.85$，自适应常数变得比非自适应下界更小，尽管作者推测对于这类重尾形状，非自适应下界可能不够紧凑。

与无量化极限的比较

作者将他们的自适应一比特界限与费舍尔信息量界限（即无通信约束时的极限）进行了比较。

• 对于许多分布（例如高斯分布、逻辑分布、双曲正割分布），自适应一比特协议所达到的常数非常接近中心化的费舍尔信息量极限。
• 这表明，对于这些分布，将每用户比特预算增加到 1 比特以上，对渐近 MSE 的提升非常有限。

4. 意义与主张

论文声称其工作为存在扰动参数（方差）时，通信约束对分布式估计的影响提供了基础性的见解。

• 自适应性的最优性： 本研究严谨地证明了，对于一大类分布，当方差未知时，自适应协议严格优于非自适应协议。这与以往的一些文献形成对比，在那些文献中，非自适应方案在不同的假设下（例如方差已知或均值有界）被证明是阶数最优的。
• 实际效率： 所提出的自适应协议非常简单（仅需两轮通信）且达到了理论下界，使其成为所述问题的理论信息论最优解。
• 更多比特的边际收益： 自适应一比特性能与中心化费舍尔信息量界限的接近性意味着，在涉及对称对数凹分布的许多实际场景中，一比特量化的“代价”极小，主要的瓶颈在于缺乏自适应性而非比特预算本身。
• 局限性： 作者谦虚地指出，其非自适应下界对于所有分布（特别是 $\beta > 1.85$ 的 GGD）可能并不紧凑，且目前关于方差估计的结果仅限于非自适应设置，未进行最优性声明。他们还指出，将这些技术扩展到高维向量和多比特预算是未来的研究方向。

论文中的仿真结果证实了其理论预测，显示出在各种分布下，自适应与非自适应协议之间的经验 MSE 存在持续的正向差距，这与推导出的渐近界限相吻合。