• Starts: 1:30 pm on Thursday, November 21, 2024
  • Ends: 3:30 pm on Thursday, November 21, 2024

ECE PhD Prospectus Defense: Nicholas Sacco

Title: Straggler Mitigation in Distributed Iterative Methods

Presenter: Nicholas Sacco

Advisor: Professor Bobak Nazer

Chair: Professor Ashok Cutkosky

Committee: Professor Bobak Nazer, Professor Alex Olshevsky, Professor Ashok Cutkosky.

Google Scholar Profile: https://scholar.google.com/citations?user=SNn5y0gAAAAJ&hl=en&oi=ao

Abstract: Modern scientific, statistical, and engineering applications require the storage and processing of very large matrices. In these high-dimensional regimes, it is natural to distribute storage and computation across many servers. However, participating servers often experience delays or errors with completing their assigned tasks.

While it is possible to wait for these “stragglers” to complete their assigned jobs, various coded computing techniques have been developed for several basic operations, such as matrix multiplication. These methods preemptively introduce erasure coding to the distributed workload, enabling the reconstruction of delayed computations from sufficiently many completed ones. While coded computing techniques can efficiently achieve the information-theoretic limits to recover from straggler-induced erasures, the computational overhead associated with such constructions may be prohibitively expensive. For example, iterative methods that refine an estimate over time or repeatedly perform the same matrix operation may not require exact recovery at every step of the algorithm.

In this work, we consider the problem of estimating the principal eigenvector of a positive semi-definite matrix using the distributed power method, subject to random row erasures. We propose a simple recovery strategy that updates non-erased coordinates and reuses missing values from the previous iteration. We prove that, given a good initialization, the power method with row erasures converges exponentially fast to the principal eigenvector. The rate of convergence is governed by a modified spectral gap, depending only on the original spectral gap and row erasure ratio. Numerical results validate the theoretical bounds, and we find that in certain settings, our proposed strategy out-performs coded computing methods and other stochastic algorithms, such as Oja’s algorithm.

Future work will consider the application of this reuse-strategy to other classes of iterative methods, such as the Jacobi and Kaczmarz methods for solving systems of linear equations. Preliminary numerical results demonstrate these methods still converge to the unique solution, even in the presence of row erasures.

Location:
PHO 339