Efficient Public Verification of Private ML via Regularization

Training with differential privacy (DP) guarantees dataset members that they cannot be identified by users of the released model. However, those data providers, and, in general, the public, lack methods to efficiently verify that models trained on their data satisfy DP guarantees. The amount of compute needed to verify DP guarantees for current algorithms scales with the amount of computation required to train the model. In this paper we design the first DP algorithm with near optimal privacy-utility trade-offs but whose DP guarantees can be verified cheaper than training. We focus on DP stochastic convex optimization (DP-SCO), where optimal privacy-utility trade-offs are known. Here we show we can obtain tight privacy-utility trade-offs by privately minimizing a series of regularized objectives and only using the standard DP composition bound. Crucially, this method can be verified with much less compute than training. This leads to the first known DP-SCO algorithm with near optimal privacy-utility whose DP verification scales better than training cost, significantly reducing verification costs on large datasets.

Machine learning models can reveal sensitive information about the individuals whose data the model was trained on. The standard approach to ensuring a model does not reveal information about these individuals is to use specially designed training algorithms, but the public lacks tools to verify a model was trained using such an algorithm. In this paper we explore how we might design these private training algorithms so that it is also easy for the public to verify they were used. This led us to an algorithm which kept the optimal utility guarantees of past algorithms, but drastically decreased the time it takes for verification. In doing so, we made progress towards enabling the public to verify how their information is being used by entities training models.