NIPS 2018
Sun Dec 2nd through Sat the 8th, 2018 at Palais des Congrès de Montréal
Paper ID: 2059 The Price of Privacy for Low-rank Factorization

### Reviewer 1

Low rank matrix factorization under privacy constraint is a well-studied problem in Differentially private Machine Learning. This problem has been studied in various models and tight bounds are known for various settings. The current work looks at this problem in distribute d, streaming, and continual release settings. It studies two natural notions of neighborhood from the point of view of defining privacy. The main contribution is a sketching based approach that gets tight bounds for differentially private PCA under these privacy models, whi le getting fast and simple sketching based algorithms. In a little more detail, the privacy models both consider two matrices to be neighboring if their differnce has Frobenious norm 1. In the first model priv_1, this difference is also rank 1, where priv_2 can handle arbitrary Frobenius norm 1 differences. There has been recen t work on these problems using sketching algorithms that gets good bounds in terms of space complexity, runtime, and communication. The c urrent paper shows that these algorithms based on sketching can be made differentially private, to yield near-optimal algorithm for vario us settings, without incurring a significant overhead in terms of space or time complexity. The authors show that this approach gives a streaming DP algorithm inthe turnstile model, where one can continually output an estimate of he best rank-k approximation to the matrix. The overhead in terms of error in Frobenius norm is $O(\sqrt{kd})$ for a $d \times d$ matrix , wiht a constant multiplicative error. Overall, I find that the paper makes progress on an interesting and important problem in DP Machine learning. I would therefore support a ccepting it.