通信的任意分区模型中的 $l_p$ 回归

Jul, 2023

通信的任意分区模型中的 $l_p$ 回归

$\ell_p$-Regression in the Arbitrary Partition Model of Communication

Yi Li, Honghao Lin, David P. Woodruff

TL;DR本研究探讨了分布式 l_p 回归问题的随机通信复杂度，得到了比以前更好的上下界，并在最小二乘回归和其他一些情况中给出了优化算法。

Abstract

We consider the randomized communication complexity of the distributed $\ell_p$-regression problem in the coordinator model, for $p\in (0,2]$. In this problem, there is a coordinator and $s$ servers. The $i$-th server receives $A^i\in\{-M, -M+1, \ldots, M\}^{n\times d}$ and $b^i\in\{-M

distributed regression randomized communication complexity arbitrary partition model least squares regression communication lower bounds

发现论文，激发创造

优化问题的通讯复杂度

研究了分布式优化中线性系统问题和优化任务的通信复杂度，并对线性规划问题的通信复杂度进行了分析。

Jun, 2019

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

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

Jun, 2015

指数随机变量的子空间嵌入和 Lp 回归

本文从子空间嵌入的角度出发，提出了一种构造常数扭曲率子空间嵌入的新方法，并将其应用于线性回归问题以及分布式计算中。

May, 2013

异常值鲁棒的多元多项式回归

鲍里斯全程鉴定弦扫，变身全员该事宜同异常低精度是样本。

Mar, 2024

统计优化的通信高效算法

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

Sep, 2012

关于鲁棒线性回归的高效算法及下界

研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

May, 2018

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

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

Feb, 2019

通信约束下的分布式非参数回归

本文研究了分布在多个机器上的数据的非参数平滑函数估计问题，其中每个机器上收集了来自白噪声模型的独立样本，并需要在中央机器上构建潜在真实函数的估计值以及在每台机器上限制了传输信息所需的比特数。我们给出了各种设置下统计风险的渐近下限和匹配上限，并且确定了三个不同的区别（通信预算 / 机器数 / 每台机器上可用数据大小），在这些区别中当通信预算很小时，统计风险仅取决于通信瓶颈，而与样本量无关；在通信预算很大的区域内，与非分布式估计的经典极小风险的情况相同；在一种中间机制中，统计风险取决于样本大小和通信预算。

Mar, 2018

分布式功能监测的严格界限

通过新的直接求和定理，我们解决了数据流模型中估计频率矩阵和其它问题时的基础问题，并通过改进算法显著提高了界限。

Dec, 2011

基于通信约束的分布式参数估计的几何下界

在分布式网络中进行参数估计，考虑每个传感器从基础分布中观察独立样本并具有 $k$ 位通信其样本到集中式处理器，该处理器计算所需参数的估计值。我们为一类广泛的损失和分布模型开发极小化风险的下界，并表明在温和的正则条件下，当 $k$ 较小时，通信约束将使有效样本量减少 $d$ 倍，其中 $d$ 是被估计参数的维数。此惩罚随着 $k$ 的增加而以最多指数级别降低，这对某些模型如高维分布估计成立。对于其他模型，我们表明样本量的减少是与 $k$ 线性递减的，例如，当一些次高斯结构可用时。我们将结果应用于具有乘积 Bernoulli 模型、多项式模型、高斯位置模型和逻辑回归的分布式设置中，从而恢复或加强现有结果。

Feb, 2018