The Price of Privacy for Low-rank Factorization
In this paper, we study what price one has to pay to release differentially private low-rank factorization of a matrix. We consider various settings that are close to the real world applications of low-rank factorization: (i) the manner in which matrices are updated (row by row or in an arbitrary manner), (ii) whether matrices are distributed or not, and (iii) how the output is produced (once at the end of all updates, also known as one-shot algorithms or continually). Even though these settings are well studied without privacy, surprisingly, there are no private algorithm for these settings (except when a matrix is updated row by row). We present the first set of differentially private algorithms for all these settings. Our algorithms when private matrix is updated in an arbitrary manner promise differential privacy with respect to two stronger privacy guarantees than previously studied, use space and time comparable to the non-private algorithm, and achieve optimal accuracy. To complement our positive results, we also prove that the space required by our algorithms is optimal up to logarithmic factors. When data matrices are distributed over multiple servers, we give a non-interactive differentially private algorithm with communication cost independent of dimension. In concise, we give algorithms that incur optimal cost across all parameters of interest. We also perform experiments to verify that all our algorithms perform well in practice and outperform the best known algorithm until now for large range of parameters.
SUMMARY: This is mostly a theory paper proposing new algorithms for low-rank matrix factorisation (LRF) that satisfy approximate (delta > 0) differential privacy (DP) and are also suitable for settings where the input matrix is distributed, or streamed, or the output is produced continually. The paper analyses the runtime, space requirements and the multiplicative and additive errors of the proposed algorithms.  There is an attempt in the paper to provide the reader with sufficient background to understand how the proposed algorithms compare to prior work and what are the key new ideas. Unfortunately, the paper is at times difficult to read due to unclear writing.   MAIN COMMENTS: 0/ [suitability] The main paper (8 pages) is essentially an advertisement for the actual, substantial journal paper appearing in the Appendix. Although I realize this appears to be common practice nowadays due to the page limitation, submitting to a journal instead would provide the benefit of the actual technical content of this work (currently in the appendices) being peer-reviewed.  1/ [significance] This could appear as another paper that takes an existing task X and simply looks at what happens when one wants to solve it under DP, proposing a new DP-X algorithm. However, I think X=LRF can be a particularly interesting problem to look at under the DP constraint, for the following reason. In DP we are constantly looking for ways to reduce the amount of noise required in order to reach a given privacy guarantee, and one folk wisdom general advice seems to be to avoid privatising high-dimensional objects (especially when some dimensions can carry little useful statistical information, but still need to be privacy-protected as we don't know a priori which dimensions these are). In studying DP-LRF one is forced to look at this question whether interest in a lower-dimensional description of the data allows one to get away with less noise being added, and this paper answers this question in the positive for the settings studied. I wonder if there might be some substance in this view and if it could help differentiate this paper from other DP-X papers.  2/ [significance] Is the proposed algorithm practical, or is it theoretical at this stage? Specifically, could you compute exact values of epsilon and delta when the algorithm is run? I couldn't spot the values of epsilon or delta in either the main text or in Appendix K.  3/ [originality] To my knowledge the paper is novel, and it is well discussed against existing work, describing the differences in assumptions, theoretical results and algorithmic ideas used. However, there is a bit of confusion especially in the Abstract about whether the proposed algorithms are the first ones to consider a given setting under the privacy constraint (lines 7-9), or whether they are improvements on top of existing ones (line 19).  4/ [clarity] The clarity of writing could be substantially improved at places (for example, in all of the important Section 2). The submission would also really benefit from just careful proof-reading for grammar (although I'm not penalising in my review for bad grammar, fixing even singular vs plural in many places would have made reading the submission easier). The submission has probably not even gone through a spell-checker. Please see also minor comments below for some concrete suggestions.  5/ [significance] Motivation for the newly introduced neighbouring relation definitions Priv1 and Priv2 currently only appears in Appendix B, but I think a summary would deserve to appear in the main paper (space can definitely be gained e.g. in the final Empirical evaluation section), so that the significance of targeting these new privacy settings can be better assessed.  6/ [quality] Is the code for reproducing experiments (available in the supplementary material upload) planned to be released to the public?   STRENGTHS: [+] LRF seems to be an interesting problem to study under DP, and it appears the particular settings considered here had either not been studied before, or the algorithms proposed here perform better.  WEAKNESSES: [-] The quality of the writing (and grammar) unfortunately leaves a lot to be desired. I don't think the paper could be published in the exact same form as it has been submitted for review. [-] Being a theory paper first and foremost, a more suitable venue than NIPS could be a journal where the reviewing process scope would be such that the proofs (currenty in the Appendix) are also carefully peer-reviewed.   MINOR COMMENTS: (Problem 1) Missing range for the variable gamma. (Definition 1) If the output of M is not discrete, a rigorous definition would only consider measurable sets S, rather than all subsets of the range. (36) The sentence is false as written. (73-74) Please provide context about the problem considered by Dwork et al. and Blum et al. (90) Does Big-O with tilde only hide poly log factors in the variable n, or also in other variables (e.g. poly log k)? (170) What is "Question 3"? (205) Do you mean "Algorithm 1" instead of "Figure 1"? (Figure 1) Using different marker shapes would help plot readability when printed in black and white.  ===== Update after author response and reviewer discussion =====  Thank you for the responses to our reviews. I'm happy with the answers to our technical comments, and where appropriate I would like to suggest perhaps incorporating some of these clarifications into the next revision. I don't think the quality of writing was good enough for NIPS in the submitted version of the paper, but I believe this can be fixed in the next revision. Please do have your paper proof-read for style and grammar issues. Assuming these changes are made, I've increased my score from 5 to 7.