SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud
Inference using deep neural networks is often outsourced to the cloud since it is a computationally demanding task. However, this raises a fundamental issue of trust. How can a client be sure that the cloud has performed inference correctly? A lazy cloud provider might use a simpler but less accurate model to reduce its own computational load, or worse, maliciously modify the inference results sent to the client. We propose SafetyNets, a framework that enables an untrusted server (the cloud) to provide a client with a short mathematical proof of the correctness of inference tasks that they perform on behalf of the client. Specifically, SafetyNets develops and implements a specialized interactive proof (IP) protocol for verifiable execution of a class of deep neural networks, i.e., those that can be represented as arithmetic circuits. Our empirical results on three-and four-layer deep neural networks demonstrate the run-time costs of SafetyNets for both the client and server are low. SafetyNets detects any incorrect computations of the neural network by the untrusted server with high probability, while achieving state-of-the-art accuracy on the MNIST digit recognition (99.4%) and TIMIT speech recognition tasks (75.22%).
The submission is interested in allowing an entity ("the verifier") to outsource the training of neural networks to a powerful but untrusted service provider ("the prover"), while obtaining a guarantee that that the prover correctly trained the neural network. Interactive proofs (IPs) are a kind of cryptographic protocol that provide such a guarantee.
The dominant cost in neural network training lies in evaluating the network on many different inputs (at least, this was my understanding -- the submission could be a bit clearer about this point for the benefit of readers who are not experts on how neural networks are trained in practice). Hence, the submission is focused on giving a very efficient IP for evaluating a neural network on many different inputs. 
The IP given in the submission applies to a rather restricted class C of neural networks: those that exclusively use quadratic activation functions and sum-pooling gates. It does not support popular activation functions like ReLU, sigmoid, or softmax, or max-pooling or stochastic pooling. The reason for this restriction is technical: existing IP techniques are well-suited mainly to "low-degree" operations, and quadratic activation functions and sum-pooling operations are low-degree.
Despite the fact that the IP applies to a rather restricted class of neural networks, the submission's experimental section states that this class of networks nonetheless achieves  state-of-the-art performance on a few benchmark learning tasks.
The submission represents a quite direct application of existing IP techniques (most notably, a highly efficient IP for matrix multiplication due to Thaler). The main technical contribution of the IP protocol lies in the observation that evaluating a neural network from the class C on many different inputs can be directly implemented via matrix multiplication (this observation exploits the linear nature of neurons), and squaring operations. This allows the authors to make use of the highly efficient IP for matrix multiplication due to Thaler. 
Without this observation, the resulting IP would be much more costly, especially for the prover, as Thaler's IP for matrix multiplication is far more efficient than general IPs for circuit-checking that have appeared in the literature.
In summary, I view the main contributions of the submission as two-fold. First, the authors observe that evaluating any neural network from a certain class (described above) on many different inputs can be reduced to operations for which highly efficient IPs are already known. Second, the submission shows experimentally that although this class is restrictive, it is still powerful enough to achieve state of the art performance on some learning tasks. 
Evaluation: Although the submission contains a careful and thorough application of interactive proof techniques, it has a few weaknesses that I think leave it below the bar for NIPS. First, as a rather direct application of known IP methods, the technical novelty is a bit low. Second, the class of networks supported is restrictive (though, again, the experiments demonstrate that the class performs quite well on some learning tasks).
Third, and perhaps most importantly, is an issue of motivation. The interactive proof in the submission allows the verifier to ensure that the neural network was correctly trained on a specific training set using a specific training algorithm. But people shouldn't care *how* the network was trained -- they should only care that the trained network makes accurate predictions (i.e., has low generalization error). Hence, there is an obvious alternative solution to the real problem that the submission does not mention or compare against: the prover can simply send the final trained-up network to the verifier. The verifier can check that this final network makes accurate predictions simply by evaluating it on a relatively small randomly chosen selection of labeled examples, and confirming that its error on these labeled examples is low. 
Based on the reported numbers for the verifier (i.e., an 8x-80x speedup for the verifier compared to doing the full training itself with no prover) this naive solution is in many cases likely to be more efficient for the verifier than the actual solution described in the paper.