Cheap Checking for Cloud Computing: Statistical Analysis via Annotated Data Streams


Chris Hickey, Graham Cormode ;
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1318-1326, 2018.


As the popularity of outsourced computation increases, questions of accuracy and trust between the client and the cloud computing services become ever more relevant. Our work aims to provide fast and practical methods to verify analysis of large data sets, where the client’s computation and memory costs are kept to a minimum. Our verification protocols are based on defining ’proofs’ which are easy to create and check. These add only a small overhead to reporting the result of the computation itself. We build up a series of protocols for elementary statistical methods, to create more complex protocols for Ordinary Least Squares, Principal Component Analysis and Linear Discriminant Analysis, and show them to be very efficient in practice.

Related Material