DP-PCA: Statistically Optimal and
Differentially Private PCA

Principal Component Analysis (PCA) is a fundamental statistical tool with multiple applications including dimensionality reduction, data visualization, and noise reduction. Naturally, it is a key part of most standard data analysis and ML pipelines. However, when applied to data collected from numerous individuals, such as the U.S. Census data, outcome of PCA might reveal highly sensitive personal information. We investigate the design of privacy preserving PCA algorithms and the involved privacy/utility tradeoffs, for computing the first principal component, that should serve as the building block of more general rank-$k$ PCA.

Differential privacy (DP) is a widely accepted mathematical notion of privacy introduced in [22], which is a standard in releasing the U.S. Census data [2] and also deployed in commercial systems [64, 26, 28]. A query to a database is said to be $(\varepsilon,\delta)$-differentialy private if a strong adversary who knows all other entries but one cannot infer that one entry from the query output, with high confidence. The parameters $\varepsilon$ and $\delta$ restricts the confidence as measured by the Type-I and II errors [42]. Smaller values of $\varepsilon\in[0,\infty)$ and $\delta\in[0,1]$ imply stronger privacy and plausible deniability for the participants.

For non-private PCA with $n$ i.i.d. samples in $d$ dimensions, the popular Oja’s algorithm (provided in Algorithm 1) achieves the optimal error of $\sin(\hat{v},v_{1})=\tilde{\Theta}(\sqrt{d/n})$, where the error is measured by the sine function of the angle between the estimate, $\hat{v}$, and the principal component, $v_{1}$, [39]. For differentially private PCA, there is a natural fundamental question: what is the extra cost we pay in the error rate for ensuring $(\varepsilon,\delta)$-DP?

We introduce a novel approach we call DP-PCA (Algorithm 3) and show that it achieves an error bounded by $\sin(\hat{v},v)=\tilde{O}(\sqrt{d/n}+d/(\varepsilon n))$ for sub-Gaussian-like data defined in Assumption 1, which is a broad class of light-tailed distributions that includes Gaussian data as a special case. The second term characterizes the cost of privacy and this is tight; we prove a nearly matching information theoretic lower bound showing that no $(\varepsilon,\delta)$-DP algorithm can achieve a smaller error. This significantly improves upon a long line of existing private algorithms for PCA, e.g., [15, 10, 36, 34, 24]. These existing algorithms are analyzed for fixed and non-stochastic data and achieve sub-optimal error rates of $O(\sqrt{d/n}+d^{3/2}/(\varepsilon n))$ even in the stochastic setting we consider.

A remaining question is whether the sub-Gaussian-like assumption, namely Assumption A.4, is necessary or if it is an artifact of our analysis and our algorithm. It turns out that such an assumption on the lightness of the tail is critical; we prove an algorithmic independent and information theoretic lower bound (Theorem 5.4) to show that, without such an assumption, the cost of privacy is lower bounded by $\Omega(\sqrt{d/(\varepsilon n)})$. This proves a separation of the error depending on the lightness of the tail.

We start with the formal description of the stochastic setting in Section 2 and present Oja’s algorithm for non-private PCA. Our first attempt in making this algorithm private in Section 3 already achieves near-optimal error, if the data is strictly from a Gaussian distribution. However, there are two remaining challenges that we describe in detail in Section 4: $(i)$ the excessive number of iterations of Private Oja’s Algorithm (Algorithm 2) prevents using typical values of $\varepsilon$ used in practice, and $(ii)$ for general sub-Gaussian-like distributions, the error does not vanish even when the noise in the data (as measured by a certain fourth moment of a function of the data) vanishes. The first challenge is due to the analysis that requires amplification by shuffling [25] that is restrictive. The second is due to its reliance on gradient norm clipping [1] that does not adapt to the variance of the current gradients. This drives the design of DP-PCA in Section 5 that critically relies on two techniques to overcome each challenge, respectively. First, minibatch SGD (instead of single sample SGD) significantly reduces the number iterations, thus obviating the need for amplification by shuffling. Next, private mean estimation (instead of gradient norm clipping and noise adding) adapts to the stochasticity of the problem and adds the minimal noise necessary to achieve privacy. The main idea of this variance adaptive stochastic gradient update is explained in detail in Section 6, along with a sketch of a proof.

Typical PCA assumes i.i.d. data $\{x_{i}\in{\mathbb{R}}^{d}\}$ from a distribution and finds the first eigenvector of $\Sigma={\mathbb{E}}[(x_{i}-{\mathbb{E}}[x_{i}])(x_{i}-{\mathbb{E}}[x_{i}])^{\top}]\in{\mathbb{R}}^{d\times d}$. Our approach allows for a more general class of data $\{A_{i}\in{\mathbb{R}}^{d\times d}\}$ that recovers the standard case when $A_{i}=(x_{i}-{\mathbb{E}}[x_{i}])(x_{i}-{\mathbb{E}}[x_{i}])^{\top}$.

The first three assumptions are required for PCA even if privacy is not needed. The last assumption provides a Gaussian-like tail bound that determines how much noise we need to introduce in the algorithm for $(\varepsilon,\delta)$-DP. The following lemma is useful in the analyses.

Following the standard recipe in training with DP-SGD, e.g., [1], we introduce Private Oja’s Algorithm in Algorithm 2. At each gradient update, we first apply gradient norm clipping to limit the contribution of a single data point and next add an appropriately chosen Gaussian noise from Lemma 2.4 to achieve $(\varepsilon,\delta)$-DP, end-to-end. The choice of clipping threshold $\beta$ ensures that, with high probability under our assumption, we do not clip any gradients. The choice of noise multiplier $\alpha$ ensures $(\varepsilon,\delta)$-DP.

One caveat in streaming algorithms is that we access data $n$ times, each with a private mechanism, but accessing only a single data point at a time. To prevent excessive privacy loss due to such a large number of data accesses, we apply a random shuffling in line 2 Algorithm 2, in order to benefit from a standard amplification by shuffling [25, 30]. This gives an amplified privacy guarantee that allows us to add a small noise proportional to $\alpha=O(\log(n/\delta)/(\varepsilon\sqrt{n}))$. Without the shuffle amplification, we will instead need a larger noise scaling as $\alpha=O(\log(n/\delta)/\varepsilon)$, resulting in a suboptimal utility guarantee. However, this comes with a restriction that the amplification holds only for small values of $\varepsilon=O(\sqrt{\log(n/\delta)/n})$. Our first contribution in the proposed DP-PCA (Algorithm 3) is to expand this range to $\varepsilon=O(1)$, which includes the practical regime of interest $\varepsilon\in[1/2,5]$.

Under Assumption 1, we select gradient norm clipping threshold $\beta$ such that no gradient exceeds $\beta$.

We provide proofs of both lemmas and the next theorem in Appendix D. When no clipping is applied, we can use the standard analysis of Oja’s Algorithm from [39] to prove the following utility guarantee.

The first term in Eq. (5) matches the non-private error rate for Oja’s algorithm in Eq. (2) with $\alpha=O(\log n)$ and $T=n$, and the second term is the price we pay for ensuring $(\varepsilon,\delta)$-DP.

Comparing to a lower bound in Theorem 5.3, this is already near optimal. However, for general distributions satisfying Assumption 1, Algorithm 2 (in particular the second term in Eq. (5)) can be significantly sub-optimal. We explain this second weakness of Private Oja’s Algorithm in the following section (the first weakness is the restriction on $\varepsilon=O(\sqrt{\log(n/\delta)/n})$).

We explain the two remaining challenges in Private Oja’s Algorithm and propose techniques to overcomes these challenges that lead to the design of DP-PCA (Algorithm 3).

This is problematic since the second term, due to the DP noise, does not vanish as the randomness $\sigma^{2}$ in the data decreases. We do not observe this for Gaussian data where signal and noise scale proportionally as shown below. We reduce the noise we add for privacy, by switching from a simple norm clipping, that adds noise proportional to the norm of the gradients, to private estimation, that only requires the noise to scale as the range of the gradients, i.e. the maximum distance between two gradients in the minibatch. The toy example above showcases that the range can be arbitrarily smaller than the maximum norm (Fig. 1). We want to emphasize that although the idea of using private estimation within an optimization has been conceptually proposed in abstract settings, e.g., in [44], DP-PCA is the first setting where $(i)$ such separation between the norm and the range of the gradients holds under any statistical model, and hence $(ii)$ the long line of recent advances in private estimation provides significant gain over the simple DP-SGD [1].

Combining the two ideas of minibatch SGD and private mean estimation, we propose DP-SGD. We use minibatch SGD of minibatch size $B=O(n/\log^{2}n)$ to allow for larger range of $\varepsilon=O(1)$. We use Private Mean Estimation to add an appropriate level of noise chosen adaptively according to Private Eigenvalue Estimation. We describe details of both sub-routines in Section 6.

We show an upper bound on the error achieved by DP-PCA under an appropriate choice of the learning rate. We provide a complete proof in Appendix E.1 that includes the explicit choice of the learning rate $\eta_{t}$ in Eq. (60), and a proof sketch is provided in Section 6.1.

We further interpret this analysis and show that $(i)$ DP-PCA is nearly optimal when the data is from a Gaussian distribution by comparing against a lower bound (Theorem 5.3); and $(ii)$ DP-PCA significantly improves upon the private Oja’s algorithm under Example 4.1. We discuss the necessity of some of the assumptions at the end of this section, including how to agnostically find the appropriate learning rate scheduling.

We prove a nearly matching lower bound, up to factors of $\sqrt{\lambda_{1}/\lambda_{2}}$ and $\sqrt{\log(1/\delta)}$. One caveat is that the lower bound assumes pure-DP with $\delta=0$. We do not yet have a lower bound technique for approximate DP that is tight, and all known approximate DP lower bounds have gaps to achievable upper bounds in its dependence in $\log(1/\delta)$, e.g., [6, 56]. We provide a proof in Appendix C.1.

Currently, DP-PCA requires choices of the learning rates, $\eta_{t}$, that depend on possibly unknown quantities. Since we can privately evaluate the quality of our solution, one can instead run multiple instances of DP-PCA with varying $\eta_{t}=c_{1}/(c_{2}+t)$ and find the best choice of $c_{1}>0$ and $c_{2}>0$. Let $w_{T}(c_{1},c_{2})$ denote the resulting solution for one instance of $\{\eta_{t}=c_{1}/(c_{2}+t)\}_{t=1}^{T}$. We first set a target error $\zeta$. For each round $i=1,\ldots$, we will run algorithm for $(c_{1},c_{2})=[2^{i-1},2^{-i+1}]\times[2^{-i+1},2^{-i+2}\ldots,2^{i-1}]$ and $(c_{1},c_{2})=[2^{-i+1},2^{-i+2}\ldots,2^{i-1}]\times[2^{i-1},2^{-i+1}]$, and compute each $\sin(w_{T}(c_{1},c_{2}),v_{1})$ privately, each with privacy budget $\varepsilon_{i}=\frac{\varepsilon}{2^{i+1}(2i-1)},\delta_{i}=\frac{\delta}{2^{i+1}(2i-1)}$. We terminate the algorithm once there there is a $w_{T}(c_{1},c_{2})$ satisfies $\sin(w_{T}(c_{1},c_{2}),v_{1})\leq\zeta$. It is clear that this search meta-algorithm terminate in logarithmic round, and the total sample complexity only blows up by a poly-log factor.

DP-PCA critically relies on private mean estimation to reduce variance of the noise required to achieve $(\varepsilon,\delta)$-DP. We follow a common recipe from [49, 43, 47, 9, 16]. First, we privately find an approximate range of the gradients in the minibatch (Alg. 4). Next, we apply the Gaussian mechanism to the truncated gradients where the truncation is tailored to the estimated range (Alg. 5).

We provide a proof in Appendix E.2. There are other ways to privately estimate the range. Some approaches require known bounds such as $\sigma_{\rm min}^{2}\leq\lambda_{1}^{2}(H_{u})_{ii}\leq\sigma_{\rm max}^{2}$ for all $i\in[d]$ [49], and other agnostic approaches are more involved such as instance optimal universal estimators of [18].

The next lemma shows that the Private Mean Estimation is $(\varepsilon,\delta)$-DP, and with high probability clipping does not apply to any of the gradients. The returned private mean, therefore, is distributed as a spherical Gaussian centered at the empirical mean of the gradients. This result requires that we have a good estimate of the top eigenvalue from Alg. 4 such that $\hat{\Lambda}\simeq\lambda_{1}^{2}\|H_{u}\|_{2}$. This analysis implies that we get an unbiased estimate of the gradient mean (which is critical in the analysis) with noise scaling as $\tilde{O}(\lambda_{1}\gamma\sqrt{d\log(1/\delta)}/(\varepsilon B))$, where $\gamma^{2}=\max_{u:\|u\|=1}\|H_{u}\|_{2}$ (which is critical in getting the tight sample complexity in the second term of the final utility guarantee in Eq. (10)). We provide a proof in Appendix E.3.