On Differentially Private Subspace Estimation in a Distribution-Free Setting

Summary

The paper tackles the challenge of high costs in private data analysis due to the curse of dimensionality, despite many datasets having an underlying low-dimensional structure. It builds on prior work by introducing measures based on multiplicative singular-value gaps to quantify how "easy" a dataset is for private subspace estimation. The authors provide new bounds and a practical algorithm that can estimate subspaces with a number of points independent of the dimension, showing improved performance in high-dimensional settings compared to previous approaches.

Strengths

1.The problem of the paper is well-motivated and the authors give both upper bounds and lower bounds. 2.They also provide experimental results. 3. The writing is clear. 4. The literature review is relatively comprehensive.

Weaknesses

There are some gaps between their upper bounds and lower bounds.

Questions

1. Can your approaches work on real-world datasets? 2. Can you further improve the gap between upper bounds and lower bounds?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

There are some gaps between their upper bounds and lower bounds.

Summary

This paper addresses the challenge of private subspace learning without assuming that the dataset follows a Gaussian distribution. They propose new measure on the hardness of subspace learning problem based on the ratio between the $k^{th}$ and the remaining eigenvalues, or between the $k^{th}$ and the $(k+1)^{th}$ eigenvalues. They derive upper and lower bounds on the utility guarantees for private subspace estimation for datasets that meet these criteria, showing that the bounds can be dimension-independent under suitable conditions. However, these conditions depend on some additional parameters, e.g. $\lambda$, that might need to be carefully selected. Also, the paper presents an implementable algorithm that achieves the derived upper bounds.

Strengths

- The paper contributed to remove a restrictive assumption in previous works. Previous research on private subspace estimation has derived dimension-independent sample complexity for Gaussian-distributed data with large multiplicative eigen-gaps. This paper removes the Gaussianity assumption, and proves that dimension-independent sample complexity can still be achieved for easier datasets. - The proposed measure of "easiness" of the datasets for subspace estimation, based on multiplicative eigen-gap, is simple and intuitive. Their derived bounds on sample complexity require prior knowledge of this measure, however, they show that the bounds are hardly affected when this measure is agnostic. - The paper has practical relevance due to its realistic assumptions and the inclusion of an implementable algorithm for private subspace estimation.

Weaknesses

The description of some parameters is vague, which hinders the understanding of the significance of the sample complexity bounds. For example, while $\lambda$ is an important parameter that appears in the sample complexity bounds, it is not defined in Definition 1.3 or in the text above it.

Questions

Can you explain the parameter $\lambda$? Is it a parameter that can be freely selected, or is it intrinsically determined by the property of the dataset or the algorithm?

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

I don't see any significant limitations.

Summary

This work studies the problem of differentially private dimension reduction without dependence on the ambient dimension d. While this is known to be impossible generally, this work gives (distinct) necessary and sufficient conditions on gaps between the kth singular value of the data matrix and its subsequent singular values for privately identifying a k-dimensional subspace that captures the data with minimal distortion. The theoretical results are empirically verified, demonstrating that for datasets that are very close to a k-dimensional subspace, for small k, that the algorithms demonstrating sample upper-bounds do outperform existing, general DP subspace estimation techniques.

Strengths

This work makes significant progress on an interesting problem, and the contributions could potentially have applications to notably improving efficiency of the broadly useful DP-SGD algorithm (in cases where gradients approximately lie in low-dimensional subspaces).

Weaknesses

The presentation of this work could be improved. The reader's first introduction to what gamma-easiness means and how it eliminates dimension dependence comes in a footnote in page 2. I think that given the centrality of easy instances to this work, it would be good to dedicate a few sentences early on to give the reader a more precise understanding of what gamma-easiness means generally and how we should think of how gamma will relate to other parameters of a problem. I also found the lower-bounds overview exceptionally hard to follow. These results are very technical and make use of prior work on fingerprinting codes and DP, so it does seem challenging to give an overview that is both sufficiently high level for the page limits and also illuminating, but I think it should be possible to make the overview more modular, and in that way easier to follow. Typos/Suggested edits: Section 1.5.2 “combination between generating” -> “combination of generating” “However, their result strongly rely” -> “However, their results strongly rely” “top-singular vector” -> “top-singular vectors” 1.5.3 “which have the property that we seek for” -> “which have the property we seek” 1.7 “Additional related work appear at Appendix A. Notations, …” -> “Additional related work appears in Appendix A. Notation, …” 2 “that arbitrary partition” -> “that arbitrary partitions” “expected Forbenius” “The first one simply treat each matrix” -> “treats” “who privately estimate” -> “which privately estimates” “asymptotical” -> “asymptotic” Footnote 4 on page 6 defines the Frobenius norm, but it’s already been referred to in Definition 1.2, so could be good to move it earlier, also Frobenius is mispelled in the footnote. 3 Paragraph 4 of Section 3, second line, I think sigma_i should be sigma_i^2 4 “that are approximately lie” -> “that approximately lie” 5 “Yet, it still left open to close the gap” -> “Yet, closing the gap is still left open” “Forbenius” “via a private subspace estimation” -> “via private subspace estimation” Appendix B Proof of proposition B.12 “$Pi_1, Pi_2$ is holds” -> “it holds” Appendix C.1 “that uses an oracle access” -> “that uses oracle access” “we obtain that the projection matrices” -> “the projection matrices” “simply treat the matrices … and compute” -> “simply treats … and computes” Algorithm C.1 “Randomly split X intro t” -> “Randomly split X into t”

Questions

The experiments all involve very small choices of k. Does this reflect an appropriate choice of constant dimension for the intended applications, computational limits, or performance limitations?

Rating

7

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

Yes, the authors have addressed the limitations of their work.

Summary

The paper studies private PCA under the assumption that the singular values of the data matrix shows multiplicative decay. It is a problem that was initiated by Steinke-Singhal and has not seen much improvement since that work. This works provides a more thorough study of this problem.

Strengths

PCA is one of the most important problem in modern data analysis and ML. Unfortunately, with privacy constraints, it requires a lot of data samples to perform PCA with any reasonable accuracy. This has led researchers to look at instances where PCA can be easy. Most of these works rely on the assumption that the singular values of the data matrix has a particular behavior. This work extends on those line of work. It provides nice upper bound on various assumptions regarding the multiplicative decay of the singular values. The upper bound result follows the framework presented in Steinke-Singhal. The lower bound to me are the more interesting one, which is based on recent ideas of Peter et al.

Weaknesses

The lower and upper bound do not match. There is a large gap between the two. One major focus in the area of PCA is to get a bound under these assumptions such that when $k \to d$, we recover the optimal rate. For example, this was the motivation behind Mangroubi-Vishnoi. Unfortunately, under that assumption, the upper bound is way worse due to its dependence on $k^2 \sqrt{d}$ and $k^3d$, respectively. Due to that reason, I believe that the lower bound is tight.

Questions

Do the authors perceive a way to improve their upper bound to get better dependence on $k$?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The quadratic and cubic dependence on $k$.