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