Distributed Primal-Dual Optimization for Non-uniformly Distributed Data
Distributed Primal-Dual Optimization for Non-uniformly Distributed Data
复制标题
DOI：
10.24963/ijcai.2018/280
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Minhao Cheng;Cho-Jui Hsieh
中科院分区：
文献类型：
--
作者：
Minhao Cheng;Cho-Jui Hsieh
分布式原对偶优化在过去几年中受到了许多关注。在这个框架中，训练样本存储在多台机器中。在每一轮中，所有机器都基于其本地数据进行一系列更新，然后同步和合并本地更新以获得对全局模型的更新。所有前面的方法都是通过用统一的权值对所有更新进行平均来合并本地更新。然而，在许多实际应用程序中，数据并不是均匀地分布在每台机器上，因此统一的权重不足以捕获本地更新的异质性。为了解决这个问题，我们提出了一种更好的方法来合并原始对偶优化框架中的本地更新。我们开发了一种计算效率高的算法来自动为每台机器选择最优权重，而不是对所有本地更新使用单个权重。在此基础上，提出了一种利用目标函数的结构来估计合并更新的对偶间隙的有效方法，从而得到了一种基于对偶间隙减小的高效线搜索算法。结合这两个想法，我们的算法比现实世界问题上现有的方法更快，更具可扩展性。
Distributed primal-dual optimization has received many focuses in the past few years. In this framework, training samples are stored in multiple machines. At each round, all the machines conduct a sequence of updates based on their local data, and then the local updates are synchronized and merged to obtain the update to the global model. All the previous approaches merge the local updates by averaging all of them with a uniform weight. However, in many real world applications data are not uniformly distributed on each machine, so the uniform weight is inadequate to capture the heterogeneity of local updates. To resolve this issue, we propose a better way to merge local updates in the primal-dual optimization framework. Instead of using a single weight for all the local updates, we develop a computational efficient algorithm to automatically choose the optimal weights for each machine. Furthermore, we propose an efficient way to estimate the duality gap of the merged update by exploiting the structure of the objective function, and this leads to an efficient line search algorithm based on the reduction of duality gap. Combining these two ideas, our algorithm is much faster and more scalable than existing methods on real world problems.