随机分布式均值估计：准确性与通信

Nov, 2016

随机分布式均值估计：准确性与通信

Randomized Distributed Mean Estimation: Accuracy vs Communication

Jakub Konečný, Peter Richtárik

TL;DR本文研究如何在分布式计算环境中在通信成本约束下，适应一系列随机化算法以在预期的通信成本和估计误差之间进行权衡，实现对一组向量的平均值估计，为分布式优化和学习算法中的 reduce-all 操作提供了一种解决方案。

Abstract

We consider the problem of estimating the arithmetic average of a finite collection of real vectors stored in a distributed fashion across several compute nodes subject to a communication budget constraint. Our analysis does not rely on any statistical assumptions about the source of the vectors. This problem arises as a subproblem in many applications, incl

distributed computing communication constraint randomized algorithms federated optimization estimation error

发现论文，激发创造

有限通信下的分布式均值估计

研究低通信成本的分布式平均估计的通信高效算法，实现数据的结构化随机旋转和编码策略，并在 k-means 和 PCA 的分布式算法中应用。

Nov, 2016

DRIVE：一位分布式均值估计算法

研究压缩问题在分布式和联邦学习中的应用，并提供数学模型和算法来比现有方法更加有效率和准确。

May, 2021

统计优化的通信高效算法

分析了两种用于大规模数据集的分布式统计优化的通信有效算法，一种是标准平均法，另一种是基于适当形式的自助子抽样的新算法，实验结果表明两种方法都有效地解决了中文 SoSo 搜索引擎的广告预测问题。

Sep, 2012

分布式统计估计和维度的通信成本

探索分布式学习中维度和沟通成本之间的关系，研究估计未知高维高斯分布均值的问题。同时，提出了一个基于阈值的协议，可在保证相同平方损失的前提下节省通信开销。

May, 2014

通过分布式数据处理不等式推导统计估计问题的通信下界

本文研究了高维分布统计估计问题的统计误差和通信成本之间的权衡，并提供了分布式稀疏高斯均值估计问题的紧密的权衡分析结果，这直接导致了分布式稀疏线性回归问题的下界，并给出了在稠密情况下均值估计的第一个最优同时协议。

Jun, 2015

高效分布式在线预测和随机优化：近似分布式平均方法

研究分布式方法用于在线预测和随机优化，并提出了基于 gossip 的优化方法以实现最优的后悔界限。

Mar, 2014

基于通信复杂度的局部隐私估计的下限

本文为研究局部隐私约束下的估计方案制定下限，推导出了私有估计和受通信限制的估计问题之间的等价性，适用于任意交互的隐私机制，并且得出了所有不同隐私保护级别的尖锐下限。作者作为对研究结果的一个重要推论，证明了有界或高斯随机向量的均值估计的最小最大均方误差按比例缩放的结论为 $d/n * d/min (ε,ε^2)$ 。

Feb, 2019

联邦学习中的混合模型：隐私、通讯和准确性权衡

为了解决联邦学习框架下传统 ERM 问题所面临的隐私保障、低带宽、动态客户端等挑战，我们开发了最优通信 - efficient 私密方案，可以使客户端参与到 ERM 的优化中，同时保证通信和隐私效果，并利用数据和客户端抽样实现隐私扩大，验证了我们的解决方案既能够获得相同的隐私、优化 - 性能操作点，又能大幅降低通信成本。

Aug, 2020

打破通信 - 隐私 - 准确性三难题

该研究提出了一种基于 Kashin 表示和随机抽样的方案以及利用 Walsh-Hadamard 矩阵的递归结构来实现隐私和通信效率的联合优化编码和解码机制，对平均值估计和频率估计等问题进行了研究。

Jul, 2020

可扩展的去中心化在线个性化均值估计算法

该研究关注于代理人合作的均值估计问题，提出了两种协作均值估计算法，并建立了性能的理论描述和渐近最优估计条件。

Feb, 2024