1比特就能精准估均值？非自适应方案竟追平自适应极限，还破解了样本区间权衡！
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
📖 AI 总结
该研究探讨了分布式一维均值估计在1比特通信约束下的非自适应协议性能。作者证明，对于任意k>1，非自适应协议能够达到与自适应协议相同的极小极大最优速率，推翻了此前认为需要两阶段交互的假设。研究进一步分析了当查询集合被限制为最多s个区间并集时的样本复杂度，发现相比无限制的非自适应查询，该约束额外增加了约(λσ/(sε²))log(1/δ)的样本量，从而完整刻画了样本复杂度与区间复杂度之间的权衡关系。这一结果对分布式统计估计中通信效率与估计精度间的平衡设计具有理论指导意义。
🔑 关键词速览
| 1-bit communication constraint | 每个智能体只能向中心学习器发送一个比特的信息，用于分布式估计。 |
| minimax rate | 在最坏情况分布下，估计器能达到的最优误差收敛速率。 |
| non-adaptive protocol | 所有查询在观测任何数据之前就固定，不根据先前响应调整的协议。 |
| sample complexity | 达到给定精度和置信度所需的样本数量。 |
| interval complexity | 查询函数的一集（即返回1的输入集合）所允许的区间数量，衡量查询的复杂度。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅