Optimal Data Splitting in Distributed Optimization for Machine Learning
The distributed optimization problem has become increasingly relevant recently. It has a lot of advantages such as processing a large amount of data in less time compared to non-distributed methods. However, most distributed approaches suffer from a significant bottleneck - the cost of communications. Therefore, a large amount of research has recently been directed at solving this problem. One such approach uses local data similarity. In particular, there exists an algorithm provably optimally exploiting the similarity property. But this result, as well as results from other works solve the communication bottleneck by focusing only on the fact that communication is significantly more expensive than local computing and does not take into account the various capacities of network devices and the different relationship between communication time and local computing expenses. We consider this setup and the objective of this study is to achieve an optimal ratio of distributed data between the server and local machines for any costs of communications and local computations. The running times of the network are compared between uniform and optimal distributions. The superior theoretical performance of our solutions is experimentally validated.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationSimilar Papers 제목 키워드 기반
Distributed Proximal Splitting Algorithms with Rates and Acceleration
We analyze several generic proximal splitting algorithms well suited for large-scale convex nonsmooth optimization. We derive sublinear and linear convergence results with new rates on the function value suboptimality or…
Distributed Pose Graph Optimization using the Splitting Method based on the Alternating Direction Method of Multipliers
Distributed optimization aims to leverage the local computation and communication capabilities of each agent to achieve a desired global objective. This paper addresses the distributed pose graph optimization (PGO) probl…
Distributed OptimizationDynamic Parallel and Distributed Graph Cuts
Graph-cuts are widely used in computer vision. In order to speed up the optimization process and improve the scalability for large graphs, Strandmark and Kahl introduced a splitting method to split a graph into multiple …
Federated K-Means Clustering via Dual Decomposition-based Distributed Optimization
The use of distributed optimization in machine learning can be motivated either by the resulting preservation of privacy or the increase in computational efficiency. On the one hand, training data might be stored across …
ClusteringComputational EfficiencyDistributed OptimizationAccelerated consensus via Min-Sum Splitting
We apply the Min-Sum message-passing protocol to solve the consensus problem in distributed optimization. We show that while the ordinary Min-Sum algorithm does not converge, a modified version of it known as Splitting y…
Distributed Optimization