arXiv:2507.16953stat.MLcs.IT2025-07

研究分布式协方差估计的通信极限,提出新不等式工具突破理论瓶颈。

Fundamental limits of distributed covariance matrix estimation via a conditional strong data processing inequality

  • 引入条件强数据处理不等式(C-SDPI)量化状态相关信道收缩
  • 在高维、有限样本下给出紧致的最小最大误差下界
  • 适用于非高斯分布,且揭示交互通信可显著降本

高维协方差矩阵估计是众多领域中的关键任务。本文研究特征分裂设置下分布式协方差估计的理论极限,即多个代理观测来自子高斯随机向量的独立同分布样本的不同分量,中心服务器需通过每代理有限比特通信来估计完整协方差矩阵。我们获得了在算子范数与Frobenius范数下的近乎紧致的最小最大下界。核心工具是本文提出的强数据处理不等式(SDPI)的新推广——条件强数据处理不等式(C-SDPI)系数,该系数具备张量化等关键性质,能刻画状态依赖信道的平均压缩程度,且常远低于最坏情况下的传统SDPI系数。结合Geng-Nair的倍增技巧与算子Jensen不等式,我们计算了高斯混合信道下的该系数,并据此建立估计误差的最小最大下界,揭示了样本量、通信成本与数据维度间的权衡关系。基于此,我们设计出近乎最优的估计协议,其样本与通信需求仅相差对数因子。不同于多数现有文献,本框架无需无限样本或高斯假设,具有广泛适用性。最后,我们将分析拓展至交互式协议,表明交互相比非交互方案可显著降低通信开销。

原文摘要 · Abstract (English)

Estimating high-dimensional covariance matrices is a key task across many fields. This paper explores the theoretical limits of distributed covariance estimation in a feature-split setting, where communication between agents is constrained. Specifically, we study a scenario in which multiple agents each observe different components of i.i.d. samples drawn from a sub-Gaussian random vector. A central server seeks to estimate the complete covariance matrix using a limited number of bits communicated by each agent. We obtain a nearly tight minimax lower bound for covariance matrix estimation under operator norm and Frobenius norm. Our main technical tool is a novel generalization of the strong data processing inequality (SDPI), termed the Conditional Strong Data Processing Inequality (C-SDPI) coefficient, introduced in this work. The C-SDPI coefficient shares key properties such as tensorization with the conventional SDPI. Crucially, it quantifies the average contraction in a state-dependent channel and can be significantly lower than the worst-case SDPI coefficient over the state input. Utilizing the doubling trick of Geng-Nair and an operator Jensen inequality, we compute this coefficient for Gaussian mixture channels. We then employ it to establish minimax lower bounds on estimation error, capturing the trade-offs among sample size, communication cost, and data dimensionality. Building on this, we present a nearly optimal estimation protocol whose sample and communication requirements match the lower bounds up to logarithmic factors. Unlike much of the existing literature, our framework does not assume infinite samples or Gaussian distributions, making it broadly applicable. Finally, we extend our analysis to interactive protocols, showing interaction can significantly reduce communication requirements compared to non-interactive schemes.

协方差估计分布式学习信息不等式通信约束

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。