论文标题
分布式优化的统计预处理加速方法
Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
论文作者
论文摘要
我们考虑分布式经验风险最小化的设置，其中多台机器并行计算梯度和集中式服务器更新模型参数。为了减少达到给定准确性所需的通信数量，我们提出了一个\ emph {预处理}加速梯度方法，其中通过在服务器上的子采样数据集上解决局部优化问题来完成预处理。该方法的收敛速率取决于全局和局部损耗函数之间相对条件数的平方根。我们通过研究Hessians在有限域上的\ Emph {均匀}浓度来估计线性预测模型的相对条件数，这使我们能够为现有的预处理梯度方法和我们的加速方法得出改善的收敛速率。对现实世界数据集的实验说明了不良条件制度中加速的好处。
We consider the setting of distributed empirical risk minimization where multiple machines compute the gradients in parallel and a centralized server updates the model parameters. In order to reduce the number of communications required to reach a given accuracy, we propose a \emph{preconditioned} accelerated gradient method where the preconditioning is done by solving a local optimization problem over a subsampled dataset at the server. The convergence rate of the method depends on the square root of the relative condition number between the global and local loss functions. We estimate the relative condition number for linear prediction models by studying \emph{uniform} concentration of the Hessians over a bounded domain, which allows us to derive improved convergence rates for existing preconditioned gradient methods and our accelerated method. Experiments on real-world datasets illustrate the benefits of acceleration in the ill-conditioned regime.
