Non-linearly separable distributed computing: A sparse tensor factorization approach

The work considers the N-server distributed computing setting with K users requesting functions that are arbitrary multi-variable polynomial evaluations of L real (potentially non-linear) basis subfunctions. Our aim is to seek efficient task-allocation and data-communication techniques that reduce computation and communication costs. Towards this, we take a tensor-theoretic approach, in which we represent the requested non-linearly decomposable functions using a properly designed tensor ¯F, whose sparse decomposition into a tensor ¯E and matrix D directly defines the task assignment, connectivity, and communication patterns. We here design an achievable scheme, employing novel fixed-support SVD-based tensor factorization methods and careful multi-dimensional tiling of subtensors, yielding computation and communication protocols whose costs are derived here, and which are shown to perform substantially better than the state of art.