Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies principle component analysis (PCA) under differential privacy (DP) constraints. The authors improve the sample complexity from prior SOTA to a near-optimal rate by proposing a new single-pass algorithm. This algorithm is novel, and it is based on a minibatch SGD algorithm where each step contains a private top eigenvalue estimation and a private mean estimation. Although the authors have not shown any simulation or experiment for their algorithm, they provide both upper bounds and lower bounds under various assumptions with solid theoretical analysis.
strengths_and_weaknesses: Major strengths:

1. The authors point out current issues for the existing results performing PCA with privacy constraint and use a totally different approach to tackle this problem. They identify the two challenges of the intuitive Private Oja’s Algorithm and solve them by two subalgorithms which perfectly match the need.
2.  The authors provide both the upper bound and lower bound which vastly improves the understanding of the PCA problem under DP constraint. The analysis of the DP-PCA under Gaussian distributions shows that their algorithm is near-optimal.

Minor strengths:

1. This paper is well-written and greatly organized to help readers get familiar with the problem they are solving and the reason behind their solution. Section 6 is very helpful for understanding what is happening during the proof.
2. The assumptions and the corresponding reasons are clearly provided.

Major weakness:

1. I have checked most of the theorems with the proof in the appendix, and found all of them are solid and accurate, except for the lower bound, Theorem 5.3, which may invalidate the near-optimality: 
    1. In Section C.1, Line 635, the very last term in the equation is incorrect where from [3] Corollary 4, $\frac{\log(|V|)}{n\phi\varepsilon}$ should be $\frac{|V|}{\exp(10n\phi\varepsilon)}$; 
    2. In Line 640 Lemma C.3, the final part $c_1 d$ should contains $\alpha$. 
    3. In Line 644, the usage of Lemma F.4 seems to have wrong constants. 
    4. In Line 647, the choice of $\alpha$ depends on $d$ which is not permissible if we want to use Lemma C.3.  

Minor weakness: 

1. This paper only considers PCA as computing the first principal component. The paper [23], which is the tightest result they have compared with in Line 115, can be used to compute the top $k$ principal components under DP constraint. Therefore, the description that the rate of DP-PCA is better than existing results is correct but may not be very fair. It would be better if the authors provide a discussion on how to use DP-PCA to find top $k$ principal components.
2. Theorem 2.2 typo: $\beta$ should be $\xi$
3. Line 178 typo, $x_i$ should be $s_i$
questions: 1. In Theorem 6.1, the rate on $B$ contains $d\log(1/\delta)$, but in Theorem 5.1, the rate on $n$, which I think should be almost the same as $B$ since $B=O(n/log^2 n)$ in Line 196, does not contain $d\log(1/\delta)$ as a whole term. Is there any typo?
limitations: The authors has discussed the limitation of their analysis and algorithm, e.g., Line 121-123, Line 235-244.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Principal Component Analysis (PCA) is a fundamental statistical tool with multiple applications and differential privacy (DP) is a widely accepted mathematical notion of privacy. This paper presents a algorithm called DP-PCA and shows that it achieves an error bounded for sub-Gaussian-like data. 
strengths_and_weaknesses: The authors make the Oja’s algorithm private and show that it achieves near-optimal error if the data is strictly from a Gaussian distribution. Then they overcame the two remaining challenges: (i) restricted range of \epsilon=O(\sqrt{log(n/\delta)/n}); (ii) excessive noise for privacy. To overcome each challenge, it critically relies on two techniques: minibatch SGD and private mean estimation. The authors proposed DP-SGD based on the two ideas above. They use minibatch SGD of minibatch size B=O(n/log^{2}n) to allow for larger range of \epsilon=O(1) and use Private Mean Estimation to add an appropriate level of noise chosen adaptively according to Private Eigenvalue Estimation.
This paper considers using private estimation within an optimization in DP-PCA setting while the idea has already been proposed in abstract settings. 

questions: See below for the weakness
limitations: DP-PCA requires choices of the learning rates. I think authors should better explain their choice of learning rate.

There are no experiments to validate the effectiveness of the proposed methods in the current paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the PAC task under differential privacy guarantee and propose private algorithms which achieves the optimal sample complexity. 
strengths_and_weaknesses: Strengths:
1. This paper is well written and I enjoy the reading. The motivations for each proposed techniques and improvements, though simple, are clear.
2. This paper shows DP PCA algorithm of an asymptotically optimal sample complexity. Concrete examples for the lower bound are presented, especially for the effect on concentration assumptions. 

Weakness:
There is some unclarity in the algorithm and proof. Please see below. 
questions: 1. In Algorithm 3, why not apply subsampling in the input A_i but instead only implement on split data? Is is because it only concerns the asymptotic  properties and there does not matter if the mini-batch is n/log n for log n iterations? 


2. Can you further drop the Gaussian tail assumption (A4) but instead apply heavy-tailed mean estimation as Algorithm 5 to implement Algorithm 3? It seems that changes in A4 only produce a worse dependence on the variance of the data but some bound can still be derived though not necessarily optimal. 

3. Can the techniques to construct the lower bound be generalized to the case when only the second or fourth moment of  tail is assumed? I am curious for heavy-tailed data, can the author claim anything interesting on the utility bound? 
limitations: Please see above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose a Differentially Private PCA (DP-PCA) based on a minibatch GD method to overcome the limitations of existing approaches. Nearly optimal statistical error rates are provided. A lower bound shows that sub-Gaussian style assumption is necessary
to obtain the optimal error rate.

strengths_and_weaknesses: Strengths:
1) The paper is well organized.
2)  The proposed Private Oja’s Algorithm and DP-PCA are well explained and reproducible.

Weaknesses:
1) There are missing key references:
H. Imtiaz, A. Sarwate, "Differentially Private Distributed Principal Component Analysis", IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2018, pages 2206-2210, 2018.
H. Imtiaz, A. Sarwate, “Distributed Differentially-Private Algorithms for Matrix and Tensor Factorization” , IEEE Journal of Selected Topics in Signal Processing, December 2018.
S. Wang, J. Chang, "Differentially Private Principal Component Analysis Over Horizontally Partitioned Data", IEEE Conference on Dependable and Secure Computing, DSC 2018, 2018.
A. Gang, B. Xiang, W. Bajwa, “Distributed principal subspace analysis for partitioned big data: Algorithms, analysis, and implementation", IEEE Transactions on Signal and Information Processing over Networks, Volume 7, pages 699–715, 2021.

questions: Can the authors locate their work in comparison of the works of . Imtiaz and. Sarwate published in 2018?
limitations: The authors have addressed adequately  the limitations of the proposed method.
review_title: null

Meta-review: metareview: The paper studies PCA under the constraint of differential privacy, and presents an improved algorithm which is based on a minibatch SGD where each step contains a private top eigenvalue estimation and a private mean estimation. The reviewers agree that the new algorithm is interesting and that the new results are important.
confidence: Certain
Decision: Accept