Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss
Yuchen Zhang Department of Electrical Engineering and Computer Science, University of California, Berkekey, CA 94720, USA. Email: (This work was perfomed during an internship at Microsoft Research.) Lin Xiao Machine Learning Groups, Microsoft Research, Redmond, WA 98053, USA. Email:
Abstract
We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sampled from a common distribution. We propose a communication-efficient distributed algorithm to minimize the overall empirical loss, which is the average of the local empirical losses. The algorithm is based on an inexact damped Newton method, where the inexact Newton steps are computed by a distributed preconditioned conjugate gradient method. We analyze its iteration complexity and communication efficiency for minimizing self-concordant empirical loss functions, and discuss the results for distributed ridge regression, logistic regression and binary classification with a smoothed hinge loss. In a standard setting for supervised learning, the required number of communication rounds of the algorithm does not increase with the sample size, and only grows slowly with the number of machines.
中文速览
大规模机器学习中，数据分散在多台机器上，每次迭代都要在机器间通信，而通信往往是整个分布式系统的瓶颈——传统梯度类方法所需的通信轮数会随样本量增大而持续增长。为此，论文提出了一种名为 DiSCO 的分布式优化算法，核心思路是用不精确阻尼牛顿法（inexact damped Newton method）作为外层迭代，再用预条件共轭梯度法（preconditioned conjugate gradient, PCG）作为内层求解器来近似计算牛顿步；关键创新在于利用各机器数据同分布（i.i.d.）这一统计特性，直接拿某台机器的本地 Hessian 矩阵作预条件子，从而大幅压缩内层 PCG 的迭代次数。理论分析表明，对于自相容（self-concordant）损失函数（涵盖岭回归、逻辑回归、平滑 hinge 损失等常见模型），在标准监督学习设置下，DiSCO 所需的通信轮数不随样本量增大而增加，仅随机器数量缓慢增长。这一结果意味着在真实大数据场景中，DiSCO 能以极少的通信开销达到高精度解，为通信受限的分布式机器学习提供了有理论保障的高效方案。
原文 arXiv:1501.00263;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1501.00263v1