Privately Learning Subspaces
Authors: Vikrant Singhal
Thomas Steinke
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Learning
Machine Learning
Data Privacy
Subspaces

Abstract: Private data analysis suffers a costly curse of dimensionality. However, the data often has an underlying low-dimensional structure. For example, when optimizing via gradient descent, the gradients often lie in or near a low-dimensional subspace. If that low-dimensional structure can be identified, then we can avoid paying (in terms of privacy or accuracy) for the high ambient dimension. 

We present differentially private algorithms that take input data sampled from a low-dimensional linear subspace (possibly with a small amount of error) and output that subspace (or an approximation to it). These algorithms can serve as a pre-processing step for other procedures.

Privately Learning Subspaces
Vikrant Singhal
Thomas Steinke
Cheriton School of Computer Science
Google Research, Brain Team Mountain View, CA, United States of America
University of Waterloo Waterloo, ON N21. 3G1, Canada
subspace@thooms--teeiin net
vikrant. www.:ssiinnaawwwarnloomomm
Abstract
Private data analysis suffers a costly curse of dimensionality. However, the data often has an underlying low-dimensional structure. For example, when optimizing via gradient descent, the gradients often lie in or near low-dimensional subspace. If that now-dimensional structure can identified, then we can avoid paying (in terms of privacy or accuracy) for the high ambient dimension.
We present differentially private algorithms that take input data sampled from a low-dimensional linear subspace (possibly with a small amount of error) and output that subspace (or approximation to it). These algorithms can as a pre-processing step for other procedures.
Introduction
Differentially private algorithms generally have poor dependence on the dimensionality of their input. That is, their error or sample complexity grows polynomially with the dimension. For example, for the simple task of estimating the mean of a distribution supported on [0, 1J", we have per-coordinate error ((vd/n) attain differential privacy, where n is the number of samples. In contrast, the non-private error O ((Vlog(d)/m)
This cost of dimensionality is inherent [UV114 SU17 DSS 15
Any method with lower error is susceptible to tracing attacks (a.k.a. membership inference attacks). However, these lower bounds only apply when the data distribution is "high-entropy." This leaves open the posssibility that can circumvent the curse dimensionality when the data has an underlying low-dimensional structure.
Data often does possess an underlying low-dimensional structure. For example, the gradients that arise in deep learning tend be close low-dimensional subspace [ACG 16 LXT 17 GARDI8
LFLYI8 LGZ 20 ZWB20 FT20]. Low dimensionality can arise from meaningful relationships that are least locally linear, such as income versus tax paid. can also arise because we are looking at function of data with relatively few attributes.
A long line of work [BL088 HTTO HRTO 0in15 BBNST9 BCM+ ZWB20 KRRT20 etc.] has
shown how to exploit structure in the data to attain better privacy and accuracy. However, these approaches assume that this structure known a priori that be learned from non-private sources. This raises the question:
Can we learn low-dimensional structure from the data subject to differential pri- vacy?
We consider the simple setting where the data lies in Rdd but is in, or very close to linear subspace, of dimension A. We focus the setting where k & d and we develop algorithms whose sample
"The full version of this article is available online
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

complexity does not depend on the ambient dimension d; polynomial dependence on the true dimension is unavoidable.
Our algorithms identify the subspace in question or, if the data is perturbed slightly, an approximation to it. Identifying the subspace structure is interesting in its right, but it also can be used pre-processing step for further analysis by projecting to the low-dimensional subspace, we ensure subsequent data analysis steps do not need to deal with high-dimensional data.
1.1 Our Contributions: Privately Learning Subspaces Exact Case
We first consider the exact case, where the data X,, .,, E I' are assumed to lie in a k- dimensional subspace (rather than merely being near to it) i... rank (A) k, where A Σ X,X? E Iddd In this case, we can also recover the subspace exactly.
However, we must also make some non-degeneracy assumptions. We want to avoid pathological input dataset such as the following. Suppose ",, Xs are linearly independent, but X Xn. While can easily reveal the repeated data point, we cannot reveal anything about the other points due to the privacy constraint.
Xk-1 X
A natural non-degeneracy assumption would be to assume that the data points are in "general position" that is, that there are no non-trivial linear dependencies among the data points. This means that every set of & data points spans the subspace or, equivalently, no subspace of dimension k 1 contains more than 1 data points. This is a very natural assumption if the data consists of n samples from continuous distribution
the subspace, then this holds with probability 1. We relax this assumption slightly and assume that no subspace of dimension k contains more than & data points. We also assume that all points are non-zero. Note that we define subspaces to pass through the origin; our results can easily be extended to affine subspaces.
Theorem 1.1 (Main Result Exact Case). For all n, d, k. E and 5, satisfying n Z O ((+
log(1/6) there exists randomized algorithm M : pdxx - Sh satisfying the following. Here Sy denotes the set of all k-dimensional subspaces Rd.
5
.M is diifferrrreee private with respect to changing one column of its input.
Let X = (X1,... (xn) E dx Suppose there exists k-dimensional subspace S, E Sh that contains all but E of the points - -.e., i [n] X, E S.,] 2 n É. Further suppose that any (k- 1))dimmensiona subspace contains most points - for all S E S we have E [n] X, E SH < f. Then PP (M) = S.] = 1.
The parameter in Theorem I.I can be thought of as a robustness parameter. Ideally the data points
are in general position, in which case é f= k - 1. If a few points are corrupted, then we increase / accordingly; our algorithm can tolerate the corruption of small constant fraction of the data points.
Theorem 1.1 is optimal in the sense that > Ω log(1/5) samples are required.
1.2 Our Contributions: Privately Learning Subspaces Approximate Case
Next we turn to the substantially more challenging approximate case, where the data XT. .X,,,, Rd are assumed to be close to a k-dimensional subspace, but are not assumed to be contained within that subspace. Our algorithm for the exact case robust to changing a few points, but very brittle if we change all the points by little bit. Tiny perturbations of the data points (due to numerical errors or mcasurement imprecision) could push the point outside the subspace, which would cause the algorithm to fail. Thus it is important for to cover the approximate case and our algorithm for the approximate is entirely different from our algorithm for the exact case.
The approximate case requires us to precisely quantify how close the input data and our output are to the subspace and we also need make quantitative non-degeneracy assumptions. formulate this via distributional assumption. We will assume that the data comes from a Gaussian distribution where the covariance matrix has a certain eigenvalue gap. This a strong assumption and we emphasize that this is only for ease of presentation; our algorithm works under weaker assumptions. Furthermore, we stress that the differential privacy guarantee worst-case and does not depend on any distributional assumptions.
easiest to
2

---

We assume that the data is drawn from multivariate Gaussian (0, Σ). Let (1 2 A2()) > 2 Aa(E) be the eigenvalues of Σ E R We assume that there are l large eigenval- ues (2), ..... (x)))) these represent the "signal" we want and d small cigenvalues 1 Ax - these are the "noise". Our goal is to recover the subspace spanned by the eigenvectors corresponding the k largest eigenvalues (2))), (2)). Our assumption is that there is a large multiplicatiie gap between the large and small eigenvalues. Namely, we assume (=+1 (x(
poly(dj
Theorem 1.2 (Main Result - Approximate Case), For all n, m,d,k k E N and a, 2,,,,,8 > 0 satisfying
k <log(1/0)
In(1/6) In([(//0e(( and 5
=a2n
1
m20
min log(k (P
there exists an algorithm M Rdxn + Stz satisfying the following. Here S is the set of all k-dimensional subspaces of represented as projection matricies- - i.e., St = (II Raddd I12
II ITT,, rrank(T)= = =k]-
M is (E, 8) differrrnitlllllyy private with respect to changing one column of its input.
Let Xi...., Xn be independent samples from N), Let (E 2 >² 2... Xa(E) be the eigenvalues D E Bdddd Suppose Xx+1(E) > Ler II S be the projection matrix onto the subspace spanned by the eigenvectors corresponding to the largest eigenvalues of Σ. Then P (X) - 11|| S a] 2 0.7.
The sample complexity of our algorithm n O(k 1og(1/5)/s) is independent of the ambient dimension d; this is ideal. However, there is polynomial dependence on d in 7, which controls the multiplicative eigenvalue gap. This multiplicative eigenvalue gap a strong assumption, but also a necessary assumption if we want the sample complexity n to be independent of the dimension d. In fact, it is necessary even without the differential privacy constraint (CZI6). That is, if we did not assume an eigenvalue gap that depends polynomially on the ambient dimension d, then it would be impossible to estimate the subspace with sample complexity n that independent of the ambient dimension d even in the non- -on-private setting.
Our algorithm is based the subsample and aggregate framework [RS07] and differentially private histogram algorithm. These methods are generally quite robust and thus our algorithm is, too. For example, our algorithm can tolerate o(n/k) input points being corrupted arbitrarily. We also believe that our algorithm's 's utility guarantee is robust to relaxing the Gaussianity assumption. All that we require in the analysis is that the empirical covariance matrix of a few samples from the distribution is sufficiently close to its expectation 2 with high probability.
1.3 Related Work
To the best of our knowledge, the problem of privately learning subspaces, not been studied before. However, a closely-related line of work is on Private Principal Component Analysis (PCA) and low-rank approximations. We briefly discuss this extensive line of work below, but first we note that, in our setting, all of these techniques have a sample complexity n that grows polynomially with the ambient dimension d. Thus, they do not evade privacy's curse of dimensionality. However, we make a stronger assumption than these prior works namely, we assume a large multiplicative eigenvalue gap. (Many of the prior works consider additive eigenvalue gap, which is a weaker assumption.)
formulate it, has
There has been a lot of interest in Private PCA, matrix completion. and low-rank approximation. One motivation for this is the infamous Netflix prize, which can be interpreted as a matrix completion problem. The competition was cancelled after researchers showed that the public training data revealed the private movie viewing histories of many of Netflix's 's customers [NS06]. Thus privacy is real concern for matrix analysis tasks.
Many variants of these problems have been considered: Some provide approximations to the data matrix X = (X1,-- ... X,) E dx others approximate the covariance matrix A A= = X,X? e Rddd (as we do). There are also different forms of approximation we can either produce subspace or an approximation to the entire matrix, and the approximation can be measured by different norms (we consider the operator norm between projection matrices). Importantly, we define differential
3

---

privacy to allow one data point X; to be changed arbitrarily. whereas most of the prior work assumes a bound on the norm of the change or even assumes that only one coordinate of one vector can be changed. In the discussion below we focus on the techniques that have been considered for these problems, rather than the specific results and settings.
[TTTZ44] consider the simple algorithm which adds independent Gaussian noise to each of entries of the covariance matrix A, and then perform analysis the noisy matrix. (In fact, this algorithm predates the development of differential privacy [BMNN05] and was also analyzed under differential privacy by McSherry and Mironov [MM09] and Chaudhuri, Sarwate, and Sinha [CSST2)) This simple algorithm is versatile and several bounds are provided for the accuracy of the noisy PCA. The downside of this is that a polynomial dependence on the ambient dimension d inherent indeed, they prove a sample complexity lower bound of approximation to the top eigenvector of A. This lower bound does not contradict our results because the relevant inputs do not satisfy our near low-rank assumption.
(2) for any algorithm that identifies a useful
[HR12] and [ABUIS] apply techniques from dimensionality reduction to privately compute low- rank approximation to the input matrix X. (HR13) and (HP13] use the power iteration method with noise injected at each step to compute low-rank approximations to the input matrix X. In all of these, the underlying privacy mechanism still noise addition and the results still require the sample complexity to grow polynomially with the ambient dimension to obtain interesting guarantees. (However, the results can be rameessoo-independeee if we define differential privacy so that only one entry- as opposed to one column of the matrix X can be changed by 1. This is a significantly weaker privacy guarantee.)
BBDS12 and [Sh also use tools from dimensionality reduction; they approximate the covariance matrix A. However, they show that the dimensionality reduction step itself provides a privacy guarantee (whereas the aforementioned results did not exploit this and relied on noise added at a later stage). [9he19] analyzes two additional techniques the addition of Wishart noise (i.e., YyT where the columns of Y are independent multivariate Gaussians) and sampling from an inverse Wishart distribution (which has a Bayesian interpretation).
apply variants of the exponential mechanism [MT07 to privately select low-rank approximation to the covariance matrix A. This method is nontrivial to implement and analyse, but it ultimately requires the sample complexity to grow polynomially in the ambient dimension.
KTI3), (CSS2
16] and [ADK* 18]
[GBB88 exploit smooth sensitivity [NRS07] to release a low-rank approximation to the matrix A. This allows adding less noise than worst case sensitivity, under an eigenvalue gap assumption. However, the sample complexity n is polynomial in the dimension d.
Limitations of Prior Work Given the great variety of techniques and analyses that have been applied to differentially private matrix analysis problems, what is missing? We see that almost all of these techniques are ultimately based on some form of noise addition or the exponential mechanism. With the singular exception of the techniques of Sheffet [She19], all of these prior techniques satisfy pure[ or concentrated differential privacy [BS16). This is enough to conclude that these techniques cannot yield the dimension dimensiooninndepedden guarantees that we seek. No amount of postprocessing or careful analysis can avoid this limitation. This is because pure and concentrated differential privacy have strong group privacy properties, which means "packing" lower bounds (HTI0) apply.
We briefly sketch why concentrated differential privacy is incompatible with dimension cinnension-indepeddded independent guarantees. Let the input be X1 X2 = ................................ = Xn, ε V for a uniformly random & E 11,, +1)" That is, the input is one random point repeated n times. If A satisfies -(1)-concettrated differential privacy, then it satisfies the mutual information bound I (M(; s O(n²) [BS66]. But, if M provides meaningful approximation to X or approximation to & from its output, whenee I (X): X) 2 sidd), as the entropy of X is d bits. This gives lower bound of 2 ((vd), even though X and A have rank k =
XXT, then we must be able to recover an
The above example shows that, even under the strongest assumptions (i.c., the data lies exactly in a rank-1 1 subspace). any good approximation to the subspace, to the data matrix X, or to the covariance matrix A X must require the sample complexity n to grow polynomially in the ambient
Pure differential privacy (a.ka. pointwise differential privacy) is (c, (e, diffferrnti privacy with 5 = 0.

---

dimension d if we restrict to techniques that satisfy concentrated differential privacy. Almost all of the prior work in this general area is subject to this restriction.
To avoid a sample complexity n that grows polynomially with the ambient dimension d, we need fundamentally new techniques.
1.4
Our Techniques
For the exact case, we construct a score function for subspaces that has low sensitivity, assigns high score to the correct subspace, and assigns a low score to all other subspaces. Then we can simply apply GAP-MAX algorithm to privately select the correct subspace (BDRS18).
The GAP-MAX algorithm satisfies (e, 6) -differrentia privacy and outputs the correct subspace as long as the gap between its score and that of any other subspace is larger than (1log( (1/8)/). This works even though there are infinitely many subspaces to consider, which would not be possible under concentrated differential privacy.
The simplest score function would simply be the number of input points that the subspace contains. This assigns high score to the correct subspace, but it also assigns high score to any larger subspace that contains the correct subspace. To remedy this, we subtract from the score the number of points contained in strictly smaller subspace. That is, the score of subspace S is the number of points in S minus the maximum over all subspaces S Ç S of the number of points contained in S".
This GAP-MAX approach easily solves the exact case, but it does not readily extend to the approxi- mate case. If count points near to the subspace, rather than in it, then (infinitely) many subspaces will have high score, which violates the assumptions needed for GAP-MAX to work. Thus we use a completely different approach for the approximate case.
We apply the "subsample and aggregate" paradigm of [NRS07]. That is, we split the dataset X1, X,, into n/O(k sub-datasets each of size O(k). We use each sub-dataset to compute an approximation to the subspace by doing a inon-private projection matrix onto the correct subspace and 111.-.. /o(/ the projection matrices onto the approximations derived from the sub-datasets. With high probability [|TT [T| is small for most j. (Exactly how small depends on the eigengap.) Now we must privately aggregate the projection matrices II,, /Ok)) into a single projection matrix.
PCA on the sub-dataset. Let II be the
Rather than directly trying aggregate the projection matrices, we pick a set of reference points, project them onto the subspaces, and then aggregate the projected points. We draw Pl. PP(I))
independently from a standard spherical Gaussian. Then ||II;p: Ipp:I| S ||I, 1I|| O(vk) is also small for all i and most j. We wish to privately approximate Ipp, and to do this we have n// (k) points I most of which are close to Hp: This is now location or mean estimation problem. which we can solve privately. Thus we obtain points P. such that IIp, - Ipp || is small for all i. From a PCA of these points we can obtain projection Ii with ||i 11I| being small, required.
Finally, we discuss how to privately obtain (61, f..... )P(K) from (IIpP)..... Ilpoo))):""> (Un/ow)P1 II, (ow)))) It is better here to treat P2, (POK)) as single vector in Ro(kd), rather than as (kk vectors in Rd. We split (O(kd) into cells and then run a differen- tially private histogram algorithm. If we construct the cells carefully, for most j we have that (Typr,... II ()))) is in the same histogram cell as the desired point (Ipı. [))())) The histogram algorithm will thus identify this cell, and we take arbitrary point from this cell as estimate (p2, po. ... )o()).. ). The differentially private histogram algorithm is run over exponentially many cells, which is possible under (c, ddiffcrrentt privacy if n/O(k) 2 ([log(1/)//s) (Note that under concentrated differential privacy the histogram algorithm's 's sample complexity would need to depend on the number of cells and, hence, the ambient dimension d.)
The main technical ingredients in the analysis of our algorithm for the approximate case are matrix perturbation and concentration analysis and the location estimation procedure using differentially private histograms. Our matrix perturbation analysis uses a variant of the Davis-Kahan theorem to show that if the empirical covariance matrix is close to the true covariance matrix, then the subspaces corresponding to the top A eigenvalues of each are also close; this is applied to both the subsamples and the projection of the reference points. The matrix concentration results that we use show that the empirical covariance matrices in all the subsamples are close to the true covariance matrix. This is
5

---

the only place where the multivariate Gaussian assumption arises. Any distribution that concentrates well will work.
2 Exact case
Here, we discuss the case, where all n points lie exactly in a subspace 8. of dimension & of R Our goal is to privately output that subspace. We do it under the assumption that all strict subspaces of s. contain at most & points. If the points are in general position, then = k - 1, as any strictly smaller subspace has dimension < & and cannot contain more points than its dimension. Let S be the set of all k-dimensional subspaces of IRd. Let Sa be the set of all subspaces of Red We formally define that problem as follows.
Problem 2.1. Assume (i) all but most l. input points are in some s, Sh. and (ii) every subspace of dimension < k contains at most points. (If the points are in general position aside from being contained in 8. then & t= k - 1.) The goal is to output a representation of 8..
We call these S points that do not lie in S., "adversarial points". With the problem defined in Problem 2. we will state the main theorem of this section.
Theorem 2.2. For any e, 0, k- 1 > O, and
0 l log(1/0)
there exists an (e, 8)- algorithm M RRdx -> Sh such that if X is a dataset of points satisfying the conditions in Problem 2.1 then M (X) outputs representation ofs, s, with probability 1.
We prove Theorem 2.2 by proving the privacy and the accuracy guarantees of Algorithm [ The algorithm performs a GÁP-MAX. It assigns a score to all the relevant subspaces, that is, the subspaces spanned by the points of the dataset X. We show that the only subspace that has a high score is the true subspace s., and the rest of the subspaces have low scores. Then GAP-MAX outputs the true subspace successfully because of the gap between the scores of the best subspace and the second to the best one. For GAP-MAX to work all the time, we define a default option in the output space that has high score, which we call NULL. Thus, the output space is now = Sa U (NULL). Also, for GAP C.P-MAA MAX to run in finite time, we filter Sy to select finite number of subspaces that have least 0 scores on the basis of X. Note that this is a preprocessing step, and does not violate privacy as, we will show, all other subspaces already have 0 probability of getting output. We define the score function u : n x y + as follows.
u( 8) = |x nss sup (I= n E ( 8) if E Sa e 4log(1/6)
if NULL
Note that this score function can be computed in finite time because for any m points and >> 0, if the points are contained in an i-dimensional subspace, then the subspace that contains all m points must lie within the set of subspaces spanned by ((+1) subsets of points.
2.1 Privacy
Lemma 2.3. Algorithm 7 is (e, (eiff-liifrrl private.
The proof of Lemma 2.3 closely follows the privacy analysis of GAP-MAX by [DDRSIS. The only novelty is that Algorithm I may output NULL in the case that the input is malformed (i.e., doesn't 't. satisfy the assumptions
Problem 2.
The key is that the score u(X, 8) is low sensitivity. Thus max(0, u(X, 8) u(X,,x 82) - 1} also has low sensitivity. What we gain from subtracting the second-largest score and taking this maximum is that these values are also sparse - only one (s = s1) is nonzero. This means we can add noise to all the values without paying for composition. We prove the privacy guarantees in the full version.
2.2 Accuracy
We start by showing that the true subspace 8, has a high score, while the rest of the subspaces have low scores.

---

Algorithm 1: DP Exact Subspace Estimator DPESE,,,,
Input: Samples X IRdxn Parameters E, k, 0. Output: E S..
Set y - {NULL} and sample noise E(NULL) from TLap(2,e,0)
Set score u NULL) L log(1/6)
// Identify candidate outputs.
each subset S of X of size & do Let s be the subspace spanned by S.
Sample noise {(s) from TLap(2, 8). Set score u( s) = 2 N sup( Sa, s
end
// Apply GAP-MAX.
Let 81 arg m u(X, be the candidate with the largest score.
10 Let 82 = arg max sy)((s)) u(X, 9) be the candidate with the second-largest score.
11 Let 3 = arg m&x,ey ma u(X,s) s) u(X, 82) - -1 + E(s).
// Truncated Laplace noise TLap(2,e,
12 return S.
Lemma 2.4. Under the assumptions of Problem 2.1 u(I, 8.) 2 n 2l and u(x, S 28 for 8' # 8,.
Proof. We have u(x, s.) = nss/- Iz for some s' E Sa with s' S s.. The dimension of s' most 1 and, by the assumption (ii), |2 nss
Let s' E Sa) \ {s.). There are three cases to analyse:
1. Let 8' 8.. Then u(z, s') < the 2 n non-adversarial points may not together lie a subspace dimension k.
< L because the l adverserial points and
2. Let s' C 8.. Let K' be the dimension of s'. Clearly k' < k. By our assumption (ii, ss' nx] I l. Then u(x, s') x nss Jxr n S. É for some t because the S adversarial points already don't lie in s., so they will not lie in any subspace of s..
3. Let be incomparable to 8,. Let 8 O 8.. Then u(ar, 8') S |a |a 8 because the adversarial points may not lie in s., but could be in s' s
This completes the proof.
Now, we show that the algorithm is accurate.
Lemma 2.5. If n 2 38 + 8log(1/6) + 2, then Algorithm Noupputs s. for Problem 2.1
Proof. From Lemma 2.4 we know that s, has score of least n 2E, and the next best subspace can have a score of at most f. Also, the score of NULL is defined to be é 4log(1/8) + 1. This means that the gap satisfies max(0, (xX,ss)) u(X, 52) 1} 2 n 36 1lo((188) 1. Since the noise is bounded by 2log(1/6) our bound on implies that á
2.3 Extensions of our Algorithm
Determining the True Dimension k. Algorithm I actually does not need know the parameter which is the dimension of the "true" subspace. That is, we could modify the algorithm to run over all subspaces, not just those of dimension k. Or, if we have an upper bound kmax, then we could run the algorithm over all subspaces of dimension kmax. However, the analyst may want to know

---

what k is before spending the privacy budget necessary to run the algorithm. If the dimension k turns out be large, then may not be worth running the algorithm. In other words, it would be desirable to be able to compute the dimension & without paying for the privacy cost of computing the subspace itself by running Algorithm[ T
We now sketch an algorithm that would help determine the right choice of & when it is unkown, at a low cost in sample complexity. We essentially use the exponential mechanism [MT07] to find k.
Given i = I,..., d, let S; be the set of subspaces of dimension that could be found by taking all combinations of points from our dataset. Then define SCORE(t) max uXX, s). Since has
sES.
sensitivity 1, SCORE(i) does too, as taking the maximum does not increase sensitivity. We then run the exponential mechanism over all i, and output the best i. This is private by the guarantees of the exponential mechanism. The intuition for accuracy is that only one subspace will have high score (from the accuracy argument in the previous subsection), and all other subspaces will have low score. Therefore, the dimension of that subspace would be output with high probability by the mechanism, if the number of samples is at least n ((log()) since the sensitivity of SCORE is 1. If we know an upper bound on k, say kmax. we can evaluate over i = I...., kmax and only pay for kmax instead of d.
Alternatvely, if our goal is simply to determine whether S kmax or k > kmax. we could compute max;5kmsx (i) and add Laplace Gaussian noise. If this value is large, then probably k S kmax. if it is small then probably k >> kimax- This would have minimal cost and may suffice to determine whether not it is worth running the full algorithm.
Computational Efficiency. Algorithm I ennuerrtees all subsets of input points of size k; so its running time is On²*), which is not efficient unless l is very small. We now sketch a modification to the algorithm that would make it efficient. Rather than considering all subsets we consider a random collection of subsets. That is, we change the for loop in Algorithm [o that instead of considering each subset S of X of size we consider some number of randomly chosen sets of & points.
Intuitively, it suffices to consider such a random subset of the subspaces because any subspace s with large u(2; s) will be included in this subset with high probability. And any subspace s with small u(x, s) is not going to be output anyway. Formally, we must show that this new algorithm will with high probability output the same thing as the current algorithm. The failure probability is added to the 8 of the (e, d)-differentia privacy guarantee. This requires changing the analysis as well as some of the parameter settings in the algorithm.
Note that our algorithm for the approximate case is computationally efficient. Thus, computational efficiency is concern, we simply run that algorithm.
3 Approximate Case
In this section, we discuss the case, where the data "approximately" lies in a k-dimensional subspace of Rd. We make Gaussian distributional assumption, where the covariance is approximately k- dimensional, though the results could be extended to distributions with heavier tails using the right inequalities. We formally define the problem:
Problem 3.1. Let E daxd be a symmetric. PSD matrix of rank 2 k {l....,d}, and let 0 < 7 < 1, such that Ar. s2². Suppose II is the projection matrix corresponding to the subspace spanned by the eigenvectors of E corresponding to the eigenvalues >ı...., Ag. Given sample access to (0 Σ), and 0 < a < 1, output a projection matrix II, such that ||T -Îll S a.
Ax-1
We solve Problem 3.1 under the constraint of (c, -iffffrrrell privacy. Throughout this section, we would refer to the subspace spanned by the top l eigenvectors of Σ as the "true" or "actual" subspace.
Algorithm 2 solves Problem 3.1 and proves Theorem 1.2 Here || || is the operator norm.
Remark 3.2. We scale the eigenvalues of Σ. so that X = and AR+1 S 722 R. Also, for the purpose of the anulysis, we will be splitting Σ Σ₁ + Ea-k. where Ex. is the covariance matrix formed by the top io eigenvalues and the corresponding eigenvectors of E. and Eag-k is remainder. Also, we assume the knowledge of y and (an upper bound on) 7.
8

---

Our solution is presented in Algorithm 2 The following theorem is the main result of the section.
Theorem 3.3. Let E E IR be an arbitrary, symmetric, PSD matrix of rank 2 k E (l,....,) d)) and lei < 7 < Suppose II is the projection matrix corresponding to the subspace spanned by the vectors of Egg- Then given
1 I 72 A (2:), for every e, O, and 0 a < there exists and (e, 6DP
E20
=a'n
min k' In(k in(1/1995]))
1
such that A (2) algorithm that takes
(log(110)
log(oog10/////
n 0
samples from (O, E), and outputs a projection matrix II, such that |1- -il S a with probability at least 0.7.
Algorithm 2 is a type of "Subsamppe-ande" aaappll-annnggggree Aaggrggggee"""" algorithm NRS07 Here, we consider multiple subspaces formed by the points from the same Gaussian, and privately find subspace that is close to all those subspaces. Since the subspaces formed by the points would be close to the true subspace, the privately found subspace would be close to the true subspace.
little more formally, we first sample q public data points (called "reference points") from N(, T). Next, we divide the original dataset X into disjoint datasets of m samples each, and project all reference points on the subspaces spanned by every subset. Now, for every reference point, do the following. We have f = 2 projections of the reference point. Using DP histogram over R4, we aggregate those projections close to one another, so they would lie within one histogram cell. We output random point from the histogram cell corresponding the reference point. With a total of q points output in this way, finally output the projection matrix spanned by these points. In the algorithm Co, C1, and C2 are universal constants.
the histogram cells; with high probability all those projections will be
We divide the proof of Theorem 3.3 into two parts: privacy (Lemma 3.4) and accuracy.
3.1 Privacy
We analyse the privacy by understanding the sensitivities at the only sequence of steps invoking differentially private mechanism, that is, the sequence of steps involving DP-histograms.
Lemma 3.4. Algorithm 2 is (s, dddffferrent private.
Proof. Changing one point in X can change only one of the X This can only change one point in Q. which in turn can only change the counts in histogram cells by 1. Therefore, the sensitivity is 2. Because the sensitivity of the histogram step is bounded by 2, an application of DP-histogram (e, -)- Outputting a random point in the privately found histogram cell preserves privacy by post-processing. Hence, the claim.
3.2 Accuracy
The accuracy analysis of Algorithm is relatively complex and is deferred to the full version. The key ingredients come from the literature on matrix concentration bounds and matrix perturbation inequalities. We briefly outline the key steps: First, apply matrix concentration to show that the empirical covariance matrix X (²')²² of each subsample is, after rescaling, close to the true covariance matrix E with high probability. Second, we apply matrix perturbation inequalities to show that the top-k subspace II, corresponding to the data matrix X is close to the true top-k subspace
II. It follows that most of the the projected reference points pi are close to the desired value Пр,: Third, we show that the aggregated projections 9; are also close to the true projections II, Finally, we apply matrix perturbation inequalities again to show that the subspace derived from the aggregated projections Il is close to the true subspace II.

---

Algorithm 2: DP Approximate Subspace Estimator DPASE (
Input:
........ Xi...., Xn Rd. Parameters e, Y, 0. Output: Projection matrix II Rdxd rank k.
Samples
[n/t] Sample reference points Pi..... Pq from NO, independently.
Set parameters: f Co In(1/8)
q C1k
L Carvakivi++ (inkk()) vm
// Subsample from X, and form projection matrices. for j E I,...,t do
Let X (X Xim) E Rdxm
Let E Rdxd be the projection matrix onto the subspace spanned by the cigenvectors of (' E Bddd corresponding to the largest eigenvalues.
for pl - 1p
....., do
end
end
// Create histogram cells with random offset. 10 Let be a random number in [0, 1). Divide Rad into f2 {..., [Ae + if, (1++ 1)0)..... jod for all e Z.
Let each disjoint cell of length e be histogram bucket.
// Perform private aggregation of subspaces.
13 For each i [g]. let Q E Rdxt be the dataset, where column j is p!.
14 Let Q E RRadxr the vertical concatenation of all Q 's in order.
is Run (e, 6)-DP histogram over Ω using Q to get w E Q that contains at least z points.
16 no such w exists then return 18 end
// Return the subspace.
Let (Pi, (Pi,...,Pal Pdt..... P(g-1)d411 .qqa) be random point in for each
do
21 Let p. = (o-1))411-.... Pea).
22 end
Let IT be the projection matrix of the top-k subspace of (f1,....PA) Pp))
return fT.
24
3.3 Handling Unknown Dimension k
Our algorithm requires knowning the parameter k which determines the dimension of the subspace and which corresponds to the location of the eigenvalue gap. What if we only have upper bound < kmax? In this case, we can use generic techniques to select the parameter & [LT99 PS2I]. These methods repeat algorithm multiple times with different settings of the parameter and output the one with the highest self-reported score. The key is that these methods incur only a constant factor overhead in the parameter E despite repeating the algorithm super-constant number of times. (They do, however, incur poly(k) factor overhead in the parameter 6.) To apply these results we must modify our algorithm to also output quality score for the subspace it has computed, such that the right parameter k is chosen we have high score and if the wrong parameter is chosen we have low score. To compute this score we take auxiliary samples (i.e., add to the sample complexity and ensure that these samples are independent from the generated subspaces). Given the projection matrix Íi returned by our algorithm and an auxiliary sample æ, we compute the projection Hr and the orthogonal component x Nr. Our success metric simply counts how many auxiliary samples satisfy ||æ iir|| < ||| for some threshold 7.
10

---

Funding Disclosure
V.S. currently at the University of Waterloo supported by an NSERC Discovery Grant, and was at Northeastern University supported by NSF grants CCF-1750640,, CNS-1816022 and CCSS-19600 V.S. was an intern at IBM during part of this work. T.S. is currently employed by Google, but was employed by IBM during part of this work.
References
[ABU18] Raman Arora, Vladimir Braverman, and Jalaj Upadhyay. Differentially private robust low-rank approximation. Advances in neural information processing systems, 2018.
[ACG+16] 16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[ADK*18] 18] Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz Medina, and Sergei Vassil- vitskii. Private covariance estimation via iterative eigenvector sampling. In 2018 NIPS workshop in Privacy-Preserving Machine Learning, volume 250, 2018.
[BBDS12] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson- Lindenstrauss transform itself preserves differential privacy. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS '12, pages 410-419, Washington, DC, USA, 2012. IEEE Computer Society.
[BBNS19] Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. Towards instance-optimal private query release. In Proceedings of the Thirtieth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 2480-2497. SIAM, 2019.
[BCM+20] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu. Private query release assisted by public data. In International Conference on Machine Learning, pages 695-703, PMLR, 2020.
[BDMN05] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: The SuLQ framework. Proceedings of the 24th ACM SIGMOD-SIGA -SSSAAAT---IGRRTT Symposium on Principles of Database Systems, PODS '05, pages 128-138, New York, NY, USA, 2005. ACM.
[BDRS18] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated edp. In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, STOC '18, pages 74-86, New York, NY, USA, 2018.
ACM.
[BLR08] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non- interactive database privacy. In STOC, 2008.
[BNS16] Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts. In Proceedings of the 7th Conference on Innovations in Theoretical Computer Science, ITCS '16, pages 369-380, New York, NY, USA, 2016. ACM.
[BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proceedings of the 14th Conference on Theory of Cryptography, TCC 16-B, pages 635-658, Berlin, Heidelberg, 2016. Springer.
[BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings the 46th Annual ACM Symposium on the Theory of Computing, STOC 14, pages 1-10, New York, NY, USA, 2014. ACM.
(CSS12) Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. Advances in Neural Information Processing Systems, 25:989-997, 2012.
11

---

[CZ16] T. Cai and Anru Zhang. Rate-ope aate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. The Annals of Statistics, 46, 05 2016.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 265-284, Berlin, Heidelberg, 2006. Springer.
[DSS + 15]
Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust traceability from trace amounts. In Proceedings of the 56th Annual IEEE Sym- posium on Foundations of Computer Science, FOCS '15, pages 650-669, Washington, DC, USA, 2015. IEEE Computer Society.
[DTTZ14] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze Gauss: Optimal bounds for the 46th Annual ACM Symposium on the Theory of Computing, STOC '14, pages 11-20, New York, NY, USA, 2014. ACM
principal component analysis. In Proceedings of
[FT20] Yu Feng and Yuhai Tu. How neural networks find generalizable solutions: Self-tuned annealing deep learning. arXiv preprint arXiv:2001.01677 2020.
[GARDI8] Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace, arXiv preprint arXiv:1812.04755:5 2018.
[GDGK20] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Tiventy Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 89-99, PMLR, 26-28 Aug 2020.
[GGB18] Alon Gonem and Ram Baaad-Baccrach. Smooth sensitivity based approach for differen- tially private PCA. In Algorithmic Learning Theory, ALT '1, pages 438-450 JMLR, Inc., 2018.
[HP13] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applica- tions. arXiv preprint arXiv: 1311::311..2499 2013,
[HR10] Moritz Hardt and Guy N Rothblum. A multiplicative weights mechanism for privacy- preserving data analysis. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 61-70. IEEE, 2010.
[HR12] Moritz Hardt and Aaron Roth. Beating randomized response on incoherent matrices. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1255-1268, 2012.
[HR13] Moritz Hardt and Aaron Roth. Beyond worst-cass analysis in private singular vector computation. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 331-340, 2013.
[HT10] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the 42nd Annual ACM Symposium the Theory of Computing, STOC '10 pages 705-714, New York, NY, USA, 2010. ACM.
[KRRT20] Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. Fast dimension independent private adagrad on publicly estimated subspaces, 2020.
[KT13] Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, pages 1395-1414, Philadelphia, PA, USA, 2013. SIAM.
[FLYY8] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint arXiv: 1804.0880..83 2018.
[LG Xinyan Li, Qilong Gu, Yingxue Zhou, Tiancong Chen, and Arindam Banerjee. Hessian based analysis of sgd for deep nets: Dynamics and generalization. In Proceedings of the 2020 SIAM International Conference on Data Mining, pages 190-198. SIAM, 2020.
12

---

[LT19] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Pro- ceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. pages 298 298-309, 2019.
LXT 17] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. arXiv preprint arXiv:1712.09913. 2017.
[MM09] Frank McSherry and Ilya Mironov. Differentially private recommender systems: Build- ing privacy into the netflix prize contenders. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 627-636, 2009.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS '07, pages 103, Washington, DC, USA, 2007, IEEE Computer Society.
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, STOC '07, pages 75-84, New York, NY, USA, 2007, ACM.
[NS06] Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the netflix prize dataset. arXiv preprint cx/0610105, 2006.
[PS21] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy, 2021.
[She19] Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory, pages 789-827. PMLR, 2019.
[SU17] Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. The Journal of Privacy and Confidentiality, 7(2):3-22, 2017.
[U1I15] Jonathan Ullman. Private multiplicative weights beyond linear queries. In Proceedings of the 34th ACM SIGMOD-SIGACT-SICA Symposium on Principles of Database Systems, pages 303-312 2015.
[Vad17] Salil Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography; Dedicated to Oded Goldreich, chapter 7, pages 347-450. Springer International Publishing AG, Cham, Switzerland, 2017.
[Ver18] Roman Vershynin. DigeeDimnnso Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
[WSC+ 16] Lu Wei, Anand D Sarwate, Jukka Corander, Alfred Hero, and Vahid Tarokh. Analysis of privacy srivacy-preserving. pea algorithm using random matrix theory. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 1335-1339. IEEE, 2016.
[ZWB20] Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimen- sion: Private sgd with gradient subspace identification. arXiv preprint arXiv:2007.03813. 2020.
13


Reviews:
[{"review_id": "jnKUc_YHWc0", "reviewer": "Reviewer_P1nL", "summary": "The paper studies the problem of learning a low-dimensional subspace from high-dimensional data in a differentially private manner.  The emphasis is on getting sample complexity that only depends on the dimension of the subspace but not the dimension of the original space. Such a guarantee is not achieved by previous techniques such as private PCA.\n\nFormally, the paper studies two settings: the exact setting and the approximate setting.  In the exact setting, they assume that they are given $n$ points and almost all of them are contained in some $k$-dimensional subspace.  It is also necessary to make a non-degeneracy assumption that no $k-1$-dimensional subspace contains too many of the points.  In the approximate setting, they assume that all of the points are drawn from a Gaussian that is close to $k$-dimensional (i.e. its covariance matrix has $k$ large eigenvalues and $d-k$ much smaller eigenvalues).  In the first case, they obtain a sample complexity of $O(k + \\log (1/\\delta)/\\epsilon)$  and in the second setting they obtain a sample complexity of  $O(k \\log(1/\\delta)/\\epsilon)$ for achieving $(\\epsilon, \\delta)$ differential privacy.  Crucially, these are linear in $k$ and independent of $d$ and also their privacy guarantee is in the worst case, where any of the sample points may be altered arbitrarily.  It is also worth noting that for the approximate setting, they do not really use the Gaussian distribution assumption very strongly and only need that the sample covariances approximate the true covariances.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the contributions are solid and the concept of getting sample complexity depending only on the `````\"true\" dimensionality of the data rather than the full dimensionality of the space is nice.  The paper is reasonably well-written and understandable.  \n\n I do feel that the algorithms presented are somewhat unsatisfying because at their core they involve some type of brute-force search over all possible subspaces.  Thus, my main question to the authors is: do you think the algorithms presented in the paper can be made computationally efficient or would this require a significantly different approach?\n\n\nAfter Author Response: Thanks for the clarifications!  My opinion remains that this paper is a solid, but not quite spectacular contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "DmUO5dPNomf", "reviewer": "Reviewer_YUHG", "summary": "This paper studies the following problem: given d-dimensional data living in an (unknown) linear subspace of dimensionality k<d, learn the subspace under the constraint of differential privacy (DP). \n\nThe authors Provide the first DP method(s) for learning a low dimensional subspace that the data lives in, where the sample complexity of their algorithms can scale with k instead of d. Their algorithms can serve as an important private pre-processing step that can reduce the sample complexity of further estimation tasks.\n\nThe authors consider two different settings. In the first “exact case”, the authors assume the data lies in a subspace s* of dimensionality k < d. For technical reasons, the authors also make the assumption that any strict subspace of s* contains at most l points. Their final sample complexity bounds scale with l instead of d (this is good when l is small, aka ``nice’’) and they present an (eps,delta)-DP algorithm that outputs s* with probability 1. Finally they give a matching lower bound for this setting proving their result is sharp.  \n\nThe result in the exact setting can be quite restrictive if the dataset is slightly perturbed (e.g. from measurement noise). This motivates the second “approximate case” in which the authors assume the data is generated from some 0 mean d-dimensional Gaussian. They assume a multiplicative ``eigenvalue gap’’ between the top k and bottom d-k eigenvalues and present an algorithm that takes advantage of the celebrated sub-sample and aggregate algorithm and stability based histogram. Their algorithm outputs a projection matrix that (with high probability) is close in operator norm to the “true” projection matrix (corresponding to the subspace spanned by the top k eigenvectors of the covariance of the Gaussian). Here, $\\Pi$ is precisely what we want to recover since for further data analysis tasks, one could project to the low dimensional subspace and work in this subspace for future tasks. Finally, the sample complexity of this second algorithm grows polynomially with k instead of d.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is solid work that takes advantage of classic tools such as stability based histograms and the GAP-MAX algorithm in new and clever ways. The arguments (to prove the privacy and accuracy) are sound. The paper is well written and includes some high-level discussions.\n\nThe first algorithm presented in the “exact case” is very simple and also has the added benefit of being sample optimal and correct with probability 1. Unfortunately, the running time of this algorithm is exponential in the size of the dataset and the assumptions on the dataset don’t seem to be very realistic, making it unlikely to see practical application. Nevertheless this is an important result from a theoretical point of view.\n\nThe second algorithm handles the approximate case but makes a distributional assumption (Gaussian) and an eigengap (which is necessary even in the non DP case). It would have been nice if the authors have explicitly stated the running time of this algorithm.\n\nIt appears that the algorithm requires the knowledge of k, the underlying dimension of the low dimensional subspace. This seems to be unrealistic in practical applications. It would be nice if the authors comment on this.\n\nOverall, the paper addresses a fundamental problem and should be attractive to both theoreticians and practitioners. More generally, the paper betters our understanding of how to exploit the structure of data to circumvent lower bounds for private estimation/learning tasks in high-dimensions.\n\nSmall typo: In line 296, The inequality $ \\geq n -3l -4\\log(1/\\delta)/\\varepsilon -1$ should end with -2 instead of -1 I believe. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see direct societal impact of this paper (aside from the benefits of studying privacy)", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "An7ZhwqPrK", "reviewer": "Reviewer_Rxwy", "summary": "The paper looks at the problem of privately learning a subspace. They consider two different settings and give algorithms for each setting.\n\nIn the first setting, they assume that almost all the points lie in a fixed subspace of dimension $k$. They also make a non-degeneracy assumption which states that no subspace of dimension $k-1$ contains too many of the points. Under these assumptions, they give an algorithm which returns the subspace exactly and with probability 1. Their algorithm has the optimal sample complexity. However, it is not efficient except for constant $k$. One interesting aspect of the result is that it has no dependence on the ambient dimension.\n\nIn the second setting, they make a distributional assumption. They assume that the points come from a mean-zero Gaussian with some unknown covariance matrix. The covariance matrix is assumed to have a large gap between the $k$th largest and the $(k+1)$th largest eigenvalue. Under these assumptions, the authors given an algorithm which returns an approximation to the subspace. Here, approximation is measured as the operator norm in the difference between the respective projection matrices.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality.**\nThe paper considers the problem of privately learning a subspace. This is a basic and fundamental problem which has not been previously studied in the literature although there have been quite a bit of work in related areas such as privately PCA. In terms of techniques, the ideas used in the exact case are a somewhat simple application of the GAP-MAX strategy with a nice score function. The approximate setting makes use of many more sophisticated techniques in a nice way (in particular, to prove accuracy) such as matrix perturbation and matrix concentration results. Their idea of using reference points as a way to aggregate candidate projection matrices is quite clever and nice.\n\n**Quality.**\nThe submission appears to be technically sound as far as I can tell. All the claims either have proofs in the main part of the paper or the appendix. However, I have not verified or read over the proofs in the appendix.\n\n**Clarity.**\nOverall, the writing quality of the paper is quite good. The authors do a good job in explaining their contributions and the technical ideas. In the exact setting, I was able to easily follow the details and understand why the algorithm works. The approximate case is much more technical but the authors clearly explain provide some high-level intuition.\n\n**Significance.**\nI believe this is a good starting point for the problem of privately learning subspaces. The present work may be of interest to researchers designing algorithms for high-dimensional datasets which may possess some lower-dimensional structure. In these settings, the present work may be of value and may help reduce the dimensionality in a private manner.\n\n**Other comments.**\nOne minor downside I have of the paper is that in the exact case, the algorithm is not very efficient (except for constant $k$). I wonder if the authors have thought a bit about how to design faster algorithms.\nAnother minor downside is that the required gap for the approximate case seems to be quite large and works only if it happened to be the case where the gap between the kth and (k+1)th eigenvalue is large.\n\nI have one additional question for the authors: In the exact case, how is the subspace represented? For example, one can use any k linearly independent vectors to represent the vectors but this is obviously not private. So I am wondering if the authors could elaborate a bit more on this aspect.\n\nLemma 4.3: Should be $u(x,s') \\leq \\ell$. This is what is proved and is what is used in Lemma 4.4.\n\nIn the proof of Lemma 4.3, first paragraph, it might be good to mention $|x \\cap s_*| \\geq n-\\ell$ by assumption (i) as well, just to increase clarity.\n\n**Update** The authors were very clear in answering my questions and I like the paper. So have increased my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "-ksU4YqiTi", "reviewer": "Reviewer_YS3D", "summary": "This paper studies the problem of learning low-dimensional structure from the data subject to differential privacy. The paper considers the setting where the data lies in or very close to a linear subspace of dimension (k<<d). For the exact case where all the data lies in a linear subspace, the proposed algorithm DPESE, which applies the GAP-MAX, can recover the subspace exactly when there are enough samples. For the approximate case, they assume that the data comes from a Gaussian distribution where the covariance matrix has a certain eigenvalue gap. This paper proposes the DPASE algorithm that is based on the subsample-and-aggregate algorithm. In both cases, the sample complexity the dimension-independent. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, and I found the analysis and algorithm easy to follow. This paper studies learning a linear subspace in the setting that the data lies in or is very close to the subspace. This problem is useful for dimension reduction and thus prevents the curse of dimensionality in private data analysis. It has some nice ideas. However, the technical contribution is not strong enough. The two algorithms are largely based on existing tools. It's nontrivial, but it's far from challenging to develop. The theoretical analysis is also quite standard, especially given that the assumptions are very strong. One question I have is how efficient to compute the scores in Algorithm 1. It seems you have to enumerate all the subspaces of a particular space. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has a discussion on the limitations of the paper. I don't see the paper has any potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of differentially private subspace learning. Under an assumption on low-dimensional nature of data, the authors present algorithms that enjoy a sample complexity scaling with the dimension of the subspace and not with the ambient dimension, thereby improving on existing results. Overall, a good paper. 
Decision: Accept (Poster)