通过分布式数据处理不等式推导统计估计问题的通信下界
探索分布式学习中维度和沟通成本之间的关系,研究估计未知高维高斯分布均值的问题。同时,提出了一个基于阈值的协议,可在保证相同平方损失的前提下节省通信开销。
May, 2014
在分布式网络中进行参数估计,考虑每个传感器从基础分布中观察独立样本并具有 $k$ 位通信其样本到集中式处理器,该处理器计算所需参数的估计值。我们为一类广泛的损失和分布模型开发极小化风险的下界,并表明在温和的正则条件下,当 $k$ 较小时,通信约束将使有效样本量减少 $d$ 倍,其中 $d$ 是被估计参数的维数。此惩罚随着 $k$ 的增加而以最多指数级别降低,这对某些模型如高维分布估计成立。对于其他模型,我们表明样本量的减少是与 $k$ 线性递减的,例如,当一些次高斯结构可用时。我们将结果应用于具有乘积 Bernoulli 模型、多项式模型、高斯位置模型和逻辑回归的分布式设置中,从而恢复或加强现有结果。
Feb, 2018
本文研究了分布在多个机器上的数据的非参数平滑函数估计问题,其中每个机器上收集了来自白噪声模型的独立样本,并需要在中央机器上构建潜在真实函数的估计值以及在每台机器上限制了传输信息所需的比特数。我们给出了各种设置下统计风险的渐近下限和匹配上限,并且确定了三个不同的区别(通信预算 / 机器数 / 每台机器上可用数据大小),在这些区别中当通信预算很小时,统计风险仅取决于通信瓶颈,而与样本量无关;在通信预算很大的区域内,与非分布式估计的经典极小风险的情况相同;在一种中间机制中,统计风险取决于样本大小和通信预算。
Mar, 2018
研究了在分布式学习中,如何在总通信次数亚线性的情况下通过镜像下降与随机稀疏化 / 量化迭代相结合的算法来实现线性模型的最优误差学习,从而探讨了高维环境下分布式学习的可行性。
Feb, 2019
本文为研究局部隐私约束下的估计方案制定下限,推导出了私有估计和受通信限制的估计问题之间的等价性,适用于任意交互的隐私机制,并且得出了所有不同隐私保护级别的尖锐下限。作者作为对研究结果的一个重要推论,证明了有界或高斯随机向量的均值估计的最小最大均方误差按比例缩放的结论为 $d/n * d/min (ε,ε^2)$ 。
Feb, 2019
研究如何在分布式网络中学习高维、非参数和结构化(如高斯)分布,并考虑不同通信模型(包括独立、顺序和黑板模型)的交互限制对于最小化风险和 Fisher 信息的影响。
Feb, 2019
分析了两种用于大规模数据集的分布式统计优化的通信有效算法,一种是标准平均法,另一种是基于适当形式的自助子抽样的新算法,实验结果表明两种方法都有效地解决了中文 SoSo 搜索引擎的广告预测问题。
Sep, 2012
本论文研究了用于最小化凸函数平均值的分布式优化算法,应用于统计机器学习的经验风险最小化问题。我们设计了一种分布式随机方差减少梯度算法,其在条件数方面同时增强了最佳并行运行时间、通信量和所有分布式一阶方法的通信轮数。此外,当条件数相对于每个机器中的数据大小不太大时,我们的方法及其加速扩展还可以优于现有的分布式算法,此外,还证明了广泛分布的课程的有关通信轮数的下限。我们证明了我们的加速分布式随机方差减少梯度算法实现了这一下限,从而它使用最少的通信轮数。
Jul, 2015
该研究提出了一种基于 Kashin 表示和随机抽样的方案以及利用 Walsh-Hadamard 矩阵的递归结构来实现隐私和通信效率的联合优化编码和解码机制,对平均值估计和频率估计等问题进行了研究。
Jul, 2020