Efficient Private Empirical Risk Minimization for High-dimensional Learning


Shiva Prasad Kasiviswanathan, Hongxia Jin ;
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:488-497, 2016.


Dimensionality reduction is a popular approach for dealing with high dimensional data that leads to substantial computational savings. Random projections are a simple and effective method for universal dimensionality reduction with rigorous theoretical guarantees. In this paper, we theoretically study the problem of differentially private empirical risk minimization in the projected subspace (compressed domain). We ask: is it possible to design differentially private algorithms with small excess risk given access to only projected data? In this paper, we answer this question in affirmative, by showing that for the class of generalized linear functions, given only the projected data and the projection matrix, we can obtain excess risk bounds of $O(w(Theta)^2/3/n^1/3) under eps-differential privacy, and O((w(Theta)/n)^1/2)$ under (eps,delta)-differential privacy, where n is the sample size and w(Theta) is the Gaussian width of the parameter space that we optimize over. A simple consequence of these results is that, for a large class of ERM problems, in the traditional setting (i.e., with access to the original data), under eps-differential privacy, we improve the worst-case risk bounds of Bassily et al. (FOCS 2014).

Related Material