Communication-Efficient Distributed Computing via Matrix Factorization

This paper presents a novel distributed computing framework, DCbMF (Distributed Computing by Matrix Factorization), for the efficient computation of linearly separable functions. Our framework operates within a multicast network of interconnected computing nodes to compute a set of output functions from input data through an efficient three-step process - Map, Shuffle, and Reduce. We cast the computation procedure as a sparse matrix factorization problem to achieve efficient communication and computation. To this end, we formulate an ℓ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> optimization problem that seeks to minimize the number of nonzero elements in each matrix factor. Due to the intractability of ℓ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> minimization, we turn to a relaxed ℓ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> formulation of the problem. We devise a modified alternating direction method of multipliers to solve the biconvex optimization problem and prove the convergence of our algorithm to a stationary solution. The numerical experiments show that DCbMF outperforms similar computing frameworks for linearly separable function computation, achieving a substantial reduction in communication overhead by 98% while maintaining the same computation cost. Notably, leveraging sparse matrix factorization and alternating optimization highlights a fundamental tradeoff between compu-tation and communication costs and paves the way for scalable and efficient distributed computing applications.