Tessellated Distributed Computing

The work considers the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>-server distributed computing scenario with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> users requesting functions that are linearly-decomposable over an arbitrary basis of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</i> real (potentially non-linear) subfunctions. In our problem, the aim is for each user to receive their function outputs, allowing for reduced reconstruction error (distortion) <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>, reduced computing cost (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>; the fraction of subfunctions each server must compute), and reduced communication cost (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula>; the fraction of users each server must connect to). For any given set of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> requested functions — which is here represented by a coefficient matrix <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {F} \in \mathbb {R}^{K \times L}$ </tex-math></inline-formula> — our problem is made equivalent to the open problem of sparse matrix factorization that seeks — for a given parameter <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i>, representing the number of shots for each server — to minimize the reconstruction distortion <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\frac {1}{KL}\|\mathbf {F} - \mathbf {D}\mathbf {E}\|^{2}_{F}$ </tex-math></inline-formula> over all <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula>-sparse and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>-sparse matrices <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {D}\in \mathbb {R}^{K \times NT}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {E} \in \mathbb {R}^{NT \times L}$ </tex-math></inline-formula>. With these matrices respectively defining which servers compute each subfunction, and which users connect to each server, we here design our <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {D},\mathbf {E}$ </tex-math></inline-formula> by designing tessellated-based and SVD-based fixed support matrix factorization methods that first split F into properly sized and carefully positioned submatrices, which we then approximate and then decompose into properly designed submatrices of D and E. For the zero-error case and under basic dimensionality assumptions, the work reveals achievable computation-vs-communication corner points <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(\gamma ,\delta)$ </tex-math></inline-formula> which, for various cases, are proven optimal over a large class of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {D},\mathbf {E}$ </tex-math></inline-formula> by means of a novel tessellations-based converse. Subsequently, for large <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>, and under basic statistical assumptions on F, the average achievable error <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> is concisely expressed using the incomplete first moment of the standard Marchenko-Pastur distribution, where this performance is shown to be optimal over a large class of D and E. In the end, the work also reveals that the overall achieved gains over baseline methods are unbounded.