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.

References in corpus (4)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Coded Sparse Matrix Multiplication
• Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning

Cited by in corpus (12)

• Communication-Efficient Edge AI: Algorithms and Systems
• A Survey of Coded Distributed Computing
• Parity Models: A General Framework for Coding-Based Resilience in ML Inference
• A locality-based approach for coded computation
• Serverless Straggler Mitigation using Local Error-Correcting Codes
• CodeNet: Training Large Scale Neural Networks in Presence of Soft-Errors
• Collage Inference: Using Coded Redundancy for Low Variance Distributed Image Classification
• Transition Waste Optimization for Coded Elastic Computing
• Optimal Load Allocation for Coded Distributed Computation in Heterogeneous Clusters
• Coded Elastic Computing
• Utility-based Resource Allocation and Pricing for Serverless Computing
• Coded-InvNet for Resilient Prediction Serving Systems