针对分布式分布估计的通信约束问题，提出自适应精炼方法提升精度。
Adaptive Refinement Protocols for Distributed Distribution Estimation under $\ell^p$-Losses
- 采用分步精炼策略：先粗估再基于粗估结果细化。
- 在多数参数下达到最优率，且在p=2时出现明显拐点。
- 适合关注通信受限下分布估计的算法研究者。
考虑在ℓ^p损失下，各分布式节点持有多个独立样本并受通信比特数限制时的离散分布估计问题。本文在多数参数区间内确定了该问题的极小极大最优率，并清晰识别出p=2处的拐点效应。为实现最优率，设计了包含自适应精炼机制的估计协议：先利用部分信息生成粗略估计，再通过后续步骤依据粗略估计进行精细化修正。协议结合逐次精炼、样本压缩、阈值处理和随机哈希等技术，在不同参数条件下实现最优性能。通过构造相容的极小极大下界，证明了协议的最优性。
原文摘要 · Abstract (English)
Consider the communication-constrained estimation of discrete distributions under $\ell^p$ losses, where each distributed terminal holds multiple independent samples and uses limited number of bits to describe the samples. We obtain the minimax optimal rates of the problem in most parameter regimes. An elbow effect of the optimal rates at $p=2$ is clearly identified. To show the optimal rates, we first design estimation protocols to achieve them. The key ingredient of these protocols is to introduce adaptive refinement mechanisms, which first generate rough estimate by partial information and then establish refined estimate in subsequent steps guided by the rough estimate. The protocols leverage successive refinement, sample compression, thresholding and random hashing methods to achieve the optimal rates in different parameter regimes. The optimality of the protocols is shown by deriving compatible minimax lower bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。