A Sequential Approximation Framework for Coded Distributed Optimization
Building on the previous work of Lee et al. and Ferdinand et al. on coded computation, we propose a sequential approximation framework for solving optimization problems in a distributed manner. In a distributed computation system, latency caused by individual processors ("stragglers") usually causes a significant delay in the overall process. The proposed method is powered by a sequential computation scheme, which is designed specifically for systems with stragglers. This scheme has the desirable property that the user is guaranteed to receive useful (approximate) computation results whenever a processor finishes its subtask, even in the presence of uncertain latency. In this paper, we give a coding theorem for sequentially computing matrix-vector multiplications, and the optimality of this coding scheme is also established. As an application of the results, we demonstrate solving optimization problems using a sequential approximation approach, which accelerates the algorithm in a distributed system with stragglers.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationSimilar Papers 제목 키워드 기반
Optimal Algorithms for Submodular Maximization with Distributed Constraints
We consider a class of discrete optimization problems that aim to maximize a submodular objective function subject to a distributed partition matroid constraint. More precisely, we consider a networked scenario in which …
A New Framework for Distributed Submodular Maximization
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been de…
BIG-bench Machine LearningClusteringDocument SummarizationFast Distributed k-Center Clustering with Outliers on Massive Data
Clustering large data is a fundamental problem with a vast number of applications. Due to the increasing size of data, practitioners interested in clustering have turned to distributed computation methods. In this work…
ClusteringDistributed ComputingTask-Oriented Communication for Multi-Device Cooperative Edge Inference
This paper investigates task-oriented communication for multi-device cooperative edge inference, where a group of distributed low-end edge devices transmit the extracted features of local samples to a powerful edge serve…
Fundamental Resource Trade-offs for Encoded Distributed Optimization
Dealing with the shear size and complexity of today's massive data sets requires computational platforms that can analyze data in a parallelized and distributed fashion. A major bottleneck that arises in such modern dist…
Distributed ComputingDistributed Optimization