Title: Learning a Code: Machine Learning for Approximate Non-Linear Coded Computation,
Abstract: Machine learning algorithms are typically run on large scale, distributed
compute infrastructure that routinely face a number of unavailabilities such as
failures and temporary slowdowns. Adding redundant computations using
coding-theoretic tools called "codes" is an emerging technique to alleviate the
adverse effects of such unavailabilities. A code consists of an encoding
function that proactively introduces redundant computation and a decoding
function that reconstructs unavailable outputs using the available ones. Past
work focuses on using codes to provide resilience for linear computations and
specific iterative optimization algorithms. However, computations performed for
a variety of applications including inference on state-of-the-art machine
learning algorithms, such as neural networks, typically fall outside this
realm. In this paper, we propose taking a learning-based approach to designing
codes that can handle non-linear computations. We present carefully designed
neural network architectures and a training methodology for learning encoding
and decoding functions that produce approximate reconstructions of unavailable
computation results. We present extensive experimental results demonstrating
the effectiveness of the proposed approach: we show that the our learned codes
can accurately reconstruct $64 - 98\%$ of the unavailable predictions from
neural-network based image classifiers on the MNIST, Fashion-MNIST, and
CIFAR-10 datasets. To the best of our knowledge, this work proposes the first
learning-based approach for designing codes, and also presents the first
coding-theoretic solution that can provide resilience for any non-linear
(differentiable) computation. Our results show that learning can be an
effective technique for designing codes, and that learned codes are a highly
promising approach for bringing the benefits of coding to non-linear
computations.