NIPS 2018
Sun Dec 2nd through Sat the 8th, 2018 at Palais des Congrès de Montréal
Paper ID: 2051 Differentially Private Robust Low-Rank Approximation

### Reviewer 1

This paper studies the problem of low-rank approximation in the l_p norm, while guaranteeing differntial privacy. The verion of the probl em when we care about the usual frobenious norm (or any rotationally invariant norm) approximation is the usual PCA and DP PCA has been t he subject of intense study, with tight upper and lower bounds known for various reasonable privacy models. In the non-private setting, t here has been some recent work on provable bounds on the best low-rank approximation in terms of entry-wise l_p norm of the residual. The current submissio takes those algorithms, and find appropriate differentially private variations of those. This is a mathematically challenging task, as it is not usually clear what the best way is of making an algorithm differentially private. The current paper shows that under their definition of privacy, an appropriate choice is to use random sketchs as in the non-DP algorith ms for this problem, and once the problem has been reduced down to that of finding a low-rank approximation of a polylogarithmic sized ma trix, one can use the usual PCA since for small matrices, all norms are related by factors polynomial in the dimension. The main tool is to use a differentially private PCA at this step, and to make this all work, the authors show how to analyze the sensitivity of the matri x one is doing this PCA when moving between neighboring datasets in the privacy definition. I find the utility guarantee of the main algorithm somewhat weak wrt the privacy definition. Specifically, the privacy definition only protects changes to the matrix by an l_1 norm of 1. A priori, this is a reasonable privacy definition. E.g. if the matrix of interest is a covariance matrix over features and each user has a sparse small-norm feature vector then one can imagine that each user has limited influence in terms of the l_1 norm. However, the approach incurs an additive overhead of $O(k(n+d))$ in this setting, which seems rather larg e. It would be useful if the authors compared this to what is obtainable, and e.g., what one pays in the usual PCA setting. Further, the authors would do well to explain better where this privacy neighborhood relation makes sense. It seems to me that in most se ttings where I would be ok with edge-level privacy, the true goal is to get a handle on the right (or left) singular values, rather than getting a low-rank representation of the matrix itself that is private. I have now read the rebuttal and am convinced that the privacy definition is a reasonable one. I would encourage the authors to improve the writeup and justify the privacy definition better.