自协调经验损失的通信高效分布式优化
研究了分布式方法在凸学习与优化中所需要的通信效率的根本限制,在不同信息假设和函数类型条件下找到了现有算法已达到最坏复杂度的情况,同时也指出了仍有改进的余地,说明了当本地目标函数没有相似之处时(由于统计数据相似或其他原因),即使设备具有无限计算能力,也可能需要多次通信往返。
Jun, 2015
本文提出了一种新的分布式训练线性分类器的方法,旨在减少通信成本,在迭代期间每个节点最小化局部形成的近似目标函数,然后合并得到下降方向移动,该方法可以看作是迭代参数混合法。
Oct, 2013
本论文研究了用于最小化凸函数平均值的分布式优化算法,应用于统计机器学习的经验风险最小化问题。我们设计了一种分布式随机方差减少梯度算法,其在条件数方面同时增强了最佳并行运行时间、通信量和所有分布式一阶方法的通信轮数。此外,当条件数相对于每个机器中的数据大小不太大时,我们的方法及其加速扩展还可以优于现有的分布式算法,此外,还证明了广泛分布的课程的有关通信轮数的下限。我们证明了我们的加速分布式随机方差减少梯度算法实现了这一下限,从而它使用最少的通信轮数。
Jul, 2015
本文提出了基于近似镜像下降的一类在线分布式优化算法,以 Bregman 距离为测量函数,包括欧几里得距离作为特例,考虑两种标准信息反馈模型,并通过在线分布式正则化线性回归问题的仿真结果验证了算法的性能。
Apr, 2020
分析了两种用于大规模数据集的分布式统计优化的通信有效算法,一种是标准平均法,另一种是基于适当形式的自助子抽样的新算法,实验结果表明两种方法都有效地解决了中文 SoSo 搜索引擎的广告预测问题。
Sep, 2012
本文提出了一种基于去中心化网络的、通信效率高且线性收敛的近似牛顿方法,该方法可以用于复合优化,并且通过本地通信和计算,可以显著提高总体效率。
Sep, 2019
提出了一种使用二阶信息进行通信和计算效率高的分布式优化算法来解决具有非平滑正则化项的 ERM 问题。该算法使用逐步二次逼近法,并描述了如何在分布式方式下有效地维护 Hessian 的逼近并解决子问题。该方法适用于广泛的非强凸问题,具有全局线性收敛性,需要更低的通信复杂度。同时,该方法可以收敛于非凸问题,因此具有在深度学习等应用中使用的潜力。初步的计算结果表明,该方法在凸问题上显著提高了通信成本和运行时间,超越了现有技术的方法。
Mar, 2018
本研究提出了适用于分布式优化的一种新的 Newton 类方法,特别适用于随机优化和学习问题。对于二次目标,该方法的收敛速度呈现线性,可以按照数据规模得到改善,基于合理假设需要基本恒定次迭代。本文提供了理论和实证证据,表明我们的方法比其他方法,如单次参数平均和 ADMM,具有优势。
Dec, 2013
在分布式网络中进行参数估计,考虑每个传感器从基础分布中观察独立样本并具有 $k$ 位通信其样本到集中式处理器,该处理器计算所需参数的估计值。我们为一类广泛的损失和分布模型开发极小化风险的下界,并表明在温和的正则条件下,当 $k$ 较小时,通信约束将使有效样本量减少 $d$ 倍,其中 $d$ 是被估计参数的维数。此惩罚随着 $k$ 的增加而以最多指数级别降低,这对某些模型如高维分布估计成立。对于其他模型,我们表明样本量的减少是与 $k$ 线性递减的,例如,当一些次高斯结构可用时。我们将结果应用于具有乘积 Bernoulli 模型、多项式模型、高斯位置模型和逻辑回归的分布式设置中,从而恢复或加强现有结果。
Feb, 2018