Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing

Understand

One of the major challenges in using distributed learning to train complicated models with large data sets is to deal with stragglers effect.

• As a solution, coded computation has been recently proposed to efficiently add redundancy to the computation tasks.
• In this technique, coding is used across data sets, and computation is done over coded data, such that the results of an arbitrary subset of worker nodes with a certain size are enough to recover the final results.
• The major challenges with those approaches are (1) they are limited to polynomial function computations, (2) the size of the subset of servers that we need to wait for grows with the multiplication of the size of the data set and the model complexity (the degree of the polynomial), which can be prohibitively large, (3) they are not numerically stable for computation over real numbers.