On Differentially Private Subspace Estimation in a Distribution-Free Setting

Authors: eliad  tsfadia
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 17:14:05

Abstract: Private data analysis faces a significant challenge known as the curse of dimensionality, leading to increased costs. However, many datasets possess an inherent low-dimensional structure. For instance, during optimization via gradient descent, the gradients frequently reside near a low-dimensional subspace. If the low-dimensional structure could be privately identified using a small amount of points, we could avoid paying for the high ambient dimension.

On the negative side, Dwork, Talwar, Thakurta, and Zhang (STOC 2014) proved that privately estimating subspaces, in general, requires an amount of points that has a polynomial dependency on the dimension. However, their bounds do not rule out the possibility to reduce the number of points for "easy" instances. Yet, providing a measure that captures how much a given dataset is "easy" for this task turns out to be challenging, and was not properly addressed in prior works.

Inspired by the work of Singhal and Steinke (NeurIPS 2021), we provide the first measures that quantify "easiness" as a function of multiplicative singular-value gaps in the input dataset, and support them with new upper and lower bounds. In particular, our results determine the first types of gaps that are sufficient and necessary for estimating a subspace with an amount of points that is independent of the dimension. Furthermore, we realize our upper bounds using a practical algorithm and demonstrate its advantage in high-dimensional regimes compared to prior approaches.

Main paper: 
 introduction: 
 Differentially private (DP) Dwork et al. [2006b] algorithms typically exhibit a significant dependence on the dimensionality of their input, as their error or sample complexity tends to grow polynomially with the dimension. This cost of dimensionality is inherent in many problems, as Bun et al. [2014] , Steinke and Ullman [2017] , Dwork et al. [2015] showed that any method that achieves lower error rates is vulnerable to tracing attacks (also known as, membership inference attacks). However, these lower bounds consider algorithms that guarantee accuracy for worst-case inputs and do not rule out the possibility of achieving higher accuracy for "easy" instances.Example: DP averaging. As a simple prototypical example, consider the task of DP averaging. In this task, the input dataset consists of d-dimensional points x 1 , . . . , x n ∈ R d , and the goal is to estimate their average 1 n n i=1 x i using a DP algorithm while minimizing the ℓ 2 additive error. One natural way to capture input "easiness" for this task is via the maximal ℓ 2 distance between any two points (i.e., points that are closer to each other are considered "easier"). Indeed, Tsfadia et al. [2022] , Peter et al. [2024] showed that if the points are γ-close to each other, and we aim for an accuracy of λγ (i.e., an accuracy that is proportional to the "easiness" parameter γ), then it is sufficient and necessary to use n = Θ( √ d/λ) points. Equivalently, if we aim for an accuracy of α, then by applying these results with λ = α/γ, we obtain that the answer is n = Θ(γ √ d/α). This, in particular, implies that when γ ≤ α/ √ d (i.e., the points are very close to each other), then Õ(1) points are sufficient, but for γ = α/d 1/2-Ω(1) , a polynomial dependency on d is necessary in general.DP subspace estimation. In this work, we consider the more complex problem of DP subspace estimation: Given a dataset X = (x 1 , . . . , x n ) ∈ (R d ) n of unit norm points and a parameter k, estimate the top-k subspace of Span{x 1 , . . . , x n }. The main goal of this work is to answer the following meta question: Question 1.1. How should we quantify how "easy" a given dataset is for DP subspace estimation?Since the dimension d is very large in many settings, we aim at providing tight measures that smoothly eliminate the dependency on d as a function of input "easiness". In particular, we want to be able to identify when we can avoid paying on the ambient dimension d, and when a polynomial dependency on d is unavoidable.To motivate the problem, consider the task of privately training large neural networks. The most commonly used tool to perform such a private training is the differentially-private stochastic gradient descent (DP-SGD) Abadi et al. [2016b] , Bassily et al. [2014] , Song et al. [2013] -a private variant of SGD that perturbs each gradient update with random noise vector drawn from an isotropic Gaussian distribution. However, this approach does not differentiate between "easy" gradients and "hard" ones, which results with high error rates when the ambient dimension -the number of parameters in the model -is large. However, empirical evidence and theoretical analysis indicate that while training some deep learning models, the gradients tend to live near a low-dimensional subspace Abadi et al. [2016a] , Li et al. [2018b] , Gur-Ari et al. [2018] , Li et al. [2018a] , Demeniconi and Chawla [2020] , Zhou et al. [2021] , Feng and Tu [2020] , Li et al. [2022] , Golatkar et al. [2022] , Kairouz et al. [2020] . In particular, Gur-Ari et al. [2018] showed that in some cases, the low dimension is the number of classes in the dataset, and the gradients tend to be close and well-spread inside this subspace. If we could exploit such a low-dimensional structure into an (inexpensive) private and useful projection matrix, we could reduce the error of DP-SGD by making it dependent solely on the low dimension.We start by defining the setting of DP subspace estimation more formally.We consider the setting of Dwork et al. [2014] . That is, the input dataset consists of n points of unit norm x 1 , . . . , x n ∈ S d := {v ∈ R d : ∥v∥ 2 = 1} and a parameter k, and the goal is to output a k-dimensional projection matrix Π such that Π • X T is "close" to X T as possible, where X denotes the n × d matrix whose rows are x 1 , . . . , x n . We measure the accuracy of our estimation using the "usefulness" definition of Dwork et al. [2014] : Definition 1. 2 (α-useful) . We say that a rank-k projection matrix Π is α-useful for a matrix X ∈ (S d ) n if for any k-rank projection matrix Π ′ :Π • X T 2 F ≥ Π ′ • X T 2 F -α • n, where ∥•∥ F denotes the Frobenius norm. 1Observe that any projection matrix is 1-useful for any X (because∥X∥ 2 F = n i=1 ∥x i ∥ 2 2 = n).Therefore, we will be interested in smaller values of α (e.g., 0.001).Without privacy restrictions, we can find a 0-useful (i.e., optimal) solution using Singular-Value Decomposition (SVD). The SVD of X is X = U ΣV T , where U ∈ R n×n and V ∈ R d×d are unitary 1 The Frobenius norm of a matrix A = (a j i ) i∈ [n] ,j∈ [d] is defined by∥A∥ F = i∈[n],j∈[d] a j i 2 .matrices, and Σ is an n × d diagonal matrix which has values σ 1 ≥ . . . ≥ σ min{n,d} ≥ 0 along the diagonal. The top-k rows subspace of X is given by the span of the first k columns of V , and it can be computed, e.g., by applying Principal Component Analysis (PCA) on the covariance matrix A = X T X (the eigenvectors of A are the columns of V ).With differential privacy, however, the problem is much harder, and Dwork et al. [2014] showed a lower bound of n ≥ Ω(k √ d) for computing a 0.001-useful k-rank projection matrix under (1, Ω(1/n2 ))-DP. This bound, however, only holds for algorithms that provide accuracy for worstcase instances and does not rule out the possibility of achieving high accuracy with smaller values of n for input points that are very close to being in a k-dimensional subspace (i.e., "easy" instances).Perhaps the easiest instances are those that exactly lie in a k-dimensional subspace, and are wellspread within it (i.e., there is no (k -1)-dimensional subspace that contains many points). Indeed, Singhal and Steinke [2021] and Ashtiani and Liaw [2022] developed (ε, δ)-DP algorithms for such instances that precisely recover the subspace using only n = Θε,δ (k) points. However, while these algorithms are robust to changing a few points, they are very brittle if we change all the points by a little bit.One approach to smoothly quantify how much a dataset is "easy" is to consider the additive-gap σ 2 k -σ 2 k+1 . Indeed, Dwork et al. [2014] , Gonem and Gilad-Bachrach [2018] present (ε, δ)-DP algorithms that output 0.001-useful projection using n = Θε,δk √ d σ 2 k -σ 2 k+1points. Yet, the downside of such additive-gap based approaches is their inherent dependency on the dimension d. Even in the extreme case where the points exactly lie in a k-dimensional subspace and well-spread within it, the additive gap σ 2 k -σ 2 k+1 is at most n/k, which still results with a polynomial dependency on d. The only existing approach to eliminate the dependency on d in some non-exact cases is the one of Singhal and Steinke [2021] (their "approximate" case). Rather than quantifying easiness as a function of the input dataset, they consider a setting where the points are sampled i.i.d. from some distribution, and implicitly measure how "easy" a distribution is according to some stability notion. In particular, they show that a d-dimensional Gaussian N ( ⃗ 0, Σ) with a multiplicative-gap σ k+1 (Σ) σ k (Σ) ≤ Θε,δ,k1 d 2is "stable" enough for estimating the top-k subspace of Σ with sample complexity that is independent of d. While Singhal and Steinke [2021] do not provide an answer to Question 1.1, they inspired our work to consider multiplicative singular-value gaps in the input dataset as a measure for easiness.Towards answering Question 1.1, we consider mechanisms M that are parameterized by k, λ, and β, and satisfy the following utility guarantee: Given a dataset X = (x 1 , . . . , x n ) ∈ (S d ) n and a value γ as inputs, such that X is "γ-easy" for k-subspace estimation, then with probability at least β over a random execution of M(X, γ), the output Π is an λγ-useful rank-k projection matrix for X. 2 In Definition 1.3, the "γ-easy" property is abstracted by a predicate f . We also allow an additional parameter γ max to relax the utility for non-easy instances (i.e., we would not require a utility guarantee for instances that are not "γ max -easy"). Furthermore, we only focus on cases in which X has at least k significant directions, which is formalized by requiring that σ 2 k (X) ≥ 0.01 • n/k (we refer to Remark 2.3 for how our upper bounds, stated in Theorem 1.6, can handle smaller values of σ k using an additional parameter or different assumptions).Definition 1.3 ((k, λ, β, γ max , f )-Subspace Estimator). Let n, k, d ∈ N s.t. k ≤ min{n, d}, let β ∈ (0, 1], and let f : (S d ) n × [0, 1] → {0, 1} be a predicate. We say that M : (S d ) n × [0, 1] → R d×d is an (k, λ, β, γ max , f )-subspace estimator, if for every X ∈ (S d ) n and γ ≤ γ max with σ 2 k (X) ≥ 0.01 • n/k and f (X, γ) = 1, it holds that Pr Π∼M(X,γ) [Π is (λγ)-useful for X] ≥ β.In this work, we develop two types of smooth measures (captured by the predicate f in Definition 1.3) for input "easiness", which are translated to the following two types of subspace estimators:Definition 1.4 ((k, λ, β, γ max )-Weak Subspace Estimator). M : (S d ) n × [0, 1] → R d×d is called an (k, λ, β, γ max )-Weak Subspace Estimator, if it is (k, λ, β, γ max , f )-Subspace Estimator for the predicate f (X, γ) that outputs 1 iff n i=k+1 σ 2 i (X) ≤ γ 2 σ 2 k (X). Definition 1.5 ((k, λ, β, γ max )-Strong Subspace Estimator). M : (S d ) n × [0, 1] → R d×d is called an (k, λ, β, γ max )-Strong Subspace Estimator, if it is (k, λ, β, γ max , f )-Subspace Estimator for the predicate f (X, γ) that outputs 1 iff σ k+1 (X) ≤ γσ k (X).In both cases, we define f based on multiplicative singular-value gaps in the input dataset, but the difference is what type of gap the value γ bounds: Strong estimators depend solely on the gap σ k+1 /σ k without taking into account smaller singular values. Weak estimators, on the other, depend on the gap min{n,d} i=k+1 σ 2 i /σ k . Note that a strong estimator is, in particular, a weak one (with the same parameters). Also note that both measures smoothly converge to the exact k-subspace case: When each gap tends to zero, the points tend to be closer to a k-dimensional subspace.We provide new upper and lower bounds for both types of estimators.Theorem 1.6 (Weak estimator). There exists an (k, λ, β = 0.9,γ max = Θ(min{ 1 λ , 1}))-weak subspace estimator M : (S d ) n × [0, 1] → R d×d with n = Õε,δ k + min{k 2 √ d, kd} λ such that M(•, γ) is (ε, δ)-DP for every γ ∈ [0, 1].Theorem 1.7 (Strong estimator). There exists an (k, λ, β = 0.8,γ max = Θ(min{ 1 λ , λ 2 k 2 d }))-strong subspace estimator M : (S d ) n × [0, 1] → R d×d with n = O ε,δ k + k 3 d λ 2 such that M(•, γ) is (ε, δ)-DP for every γ ∈ [0, 1].Both of our estimators provide a useful projection by outputting a matrix that is close (in Frobenius norm) to the projection matrix of the top-k rows subspace. Their running time is n m • T (m, d, k) + Õ(dkn) for some m = Θ(k), where T (m, d, k) denotes the running time required to compute (non-privately) a projection matrix to the top-k rows subspace of an m × d matrix. We refer to Section 2 for a detailed overview.For simplifying the presentation and the formal utility guarantees, we assume that our algorithms know the values of γ (the bound on the multiplicative-gap) and of k beforehand. Yet, we show that both assumptions are not inherent, and we refer to Remark 2.4 for additional details.We also remark that in both theorems, it is possible to increase the confidence β to any constant smaller than 1 without changing the asymptotic cost.Theorem 1.8 (Lower bound for weak estimators).If M : (S d ) n × [0, 1] → R d×d is a (k, λ, β = 0.1, γ max = Θ( 1 λ ))-weak subspace estimator for 1 ≤ λ ≤ Θ( d k log k ) and M(•, γ) is 1, 1 50nk -DP for every γ ∈ [0, 1], then n ≥ Ω √ kd λ.Theorem 1.9 (Lower bound for strong estimators).If M : (S d ) n × [0, 1] → R d×d is a (k, λ, β = 0.1, γ max = Θ 1 λ )-strong subspace estimator for 1 ≤ λ ≤ Θ( d log k ) and M(•, γ) is 1, 1 50nk -DP for every γ, then n ≥ Ω k √ d λ .Our lower bounds are more technically involved, and use a novel combination of generating hardinstances using the tools from Peter et al. [2024] for proving smooth lower bounds, and extracting sensitive vectors from useful projection matrices using ideas from the lower bound of Dwork et al. [2014] . Both lower bounds are proven by generating hard-instances that are "γ-easy" for γ = 1 1000λ . We refer to Section 3 for a detailed overview.We remark that Peter et al. [2024] recently proved a similar lower bound for the special case of k = 1 (estimating the top-singular vector). However, their result strongly relies on the similarity between Weak EstimatorÕε,δ k+ k 2 √ d λ O ε,δ k + k 3 d λ 2 Lower Bound Ω √ kd λ Ω k √ d λTable 1 : Our bounds on n for subspace estimation (ignoring restrictions on γ max and λ).Strong EstimatorUpper Bound Õε,δ k + γ 1 k 2 √ d O ε,δ k + γ 2 2 k 3 d Lower Bound Ω γ 1 √ kd Ω γ 2 k √ dTable 2 : Our bounds on n for computing 0.001-useful projection, where γ 1 = min{n,d} i=k+1 σ 2 i /σ k and γ 2 = σ k+1 /σ k denote here the "easiness" parameters for weak and strong estimators, respectively. As mentioned in Footnote 3, our upper bound for strong estimators only hold forγ 2 ≤ Θ(k -2/3 d -1/3 ).averaging and estimating top-singular vector in their hard instances, which does not hold for the case k ≥ 2. Table 1 summarizes our bounds for k ≤ √ d.We offer two formulations which have the property we seek: If we aim for an error α, and the dataset is "γ-easy" for a very small γ, we take λ = α/γ to reduce the number of necessary and sufficient points.For strong estimators, the rate n = n(λ) in Theorem 1.7 does not match the corresponding lower bound Theorem 1.9, and Theorem 1.7 is limited to small values of γ. 3 Yet, for small values of k, the strong-estimator bounds do imply that in order to privately compute an 0.001-useful rank-k projection with number of points that is independent of d, it is sufficient and necessary to have a gap σ k+1 /σ k of at most ∝ 1/ √ d. Table 2 summarizes our bounds for the special case of outputing 0.001-useful projection matrix, using our two different types of input "easiness".We believe that private subspace estimation of easy instances could find practical applications. Therefore, we made an effort to realize our upper bounds using a practical algorithm. In Section 4 we empirically compared our method to the additive-gap based approach of Dwork et al. [2014] for the task of privately estimating the empirical mean of points that are close to a small dimensional subspace, demonstrating the advantage of our approach in high-dimensional regimes.In Sections 2 and 3 we present proof overviews for our results, and the empirical evaluation is provided in Section 4. A limitations section is given in Section 5. Additional related work appears at Appendix A. Notations, definitions and general statements are given in Appendix B. Our upper bounds are proven in Appendix C, and our lower bounds are proven in Appendix D. 
upper bounds -overview: 
 Both of our estimators (Theorems 1.6 and 1.7) follow the same structure, but with different parameters. Similarly to Singhal and Steinke [2021] , our algorithms follow the sample-and-aggregate approach of Nissim et al. [2007] . That is, given a dataset X = (x 1 , . . . , x n ) ∈ (S d ) n , we partition the rows into t subsets, compute (non-privately) a projection matrix to the top-k rows subspace of each subset, and then privately aggregate the projection matrices Π 1 , . . . , Π t . For doing that, we need to argue that Π 1 , . . . , Π t are expected to be close to each other. In the Gaussian setting of Singhal and Steinke [2021] , this holds by concentration properties of Gaussian distributions. In our setting, however, it is unreasonable to expect that arbitrary partitions will lead to similar subspaces. For instance, consider the matrix X whose first n/k rows are e 1 = (1, 0, . . . , 0), the next n/k rows are e 2 = (0, 1, . . . , 0), and so forth until e k . Even though X is rank-k and has σ 2 1 = . . . = σ 2 k = n/k, if we simply partition the rows according to their order, then most of those subsets will induce a rank-1 matrix which clearly does not represent the original matrix X. Therefore, we must consider a more clever partition that will guarantee a good representation of the top-k rows subspace of X in each subset.There is an extensive line of works who aim for methods to choose a small subset of rows that provides a good low-approximation for the original matrix (e.g., see Mahoney [2011] for a survey). Yet, most of these methods are data-dependent, and therefore seem less applicable for privacy.In this work we show that by simply using a uniformly random partition into subsets of size Θ(k), then w.h.p. each subset induces a projection matrix that is close to the projection matrix of the top-k rows subspace of X: Lemma 2.1. Let X = (x 1 , . . . , x n ) ∈ (S d ) n with singular values σ 1 ≥ . . . ≥ σ min{n,d} ≥ 0, andlet γ 1 = σ k+1 σ k and γ 2 = min{n,d} i=k+1 σ 2 i σ k . Let X ′ ∈ (S d) m be a uniformly random m-size subset of the rows of X (without replacement). Let Π and Π ′ be the projection matrices to the top-k rows subspace of X and X ′ , respectively. Assuming that σ 2 k ≥ 0.01n/k, then the following holds for m = Θ(k):1. If γ 1 ≤ m 2n , then Pr ∥Π -Π ′ ∥ ≤ O n m • γ 1 ≥ 0.9. (∥•∥ denotes the Spectral norm 4 ). 2. If γ 2 ≤ 0.1, then Pr[∥Π -Π ′ ∥ F ≤ O(γ 2 )] ≥ 0.9. 5 .Namely, Item 1 bounds the expected spectral norm distance of the projection matrices using the first type gap σ k+1 /σ k (which is used in the analysis of our strong estimator), and Item 2 bounds the expected Frobenius norm distance using the second type gap min{n,d} i=k+1 σ 2 i /σ k (which is used in the analysis of our weak estimator). We prove Lemma 2.1 in Appendix C.1.2. The next step is to aggregate the non-private projection matrices Π 1 , . . . , Π t into a private one Π. We consider two types of aggregations. The first one simply treats each matrix as a d 2 vector and privately estimate the average of Π 1 , . . . , Π t . The second type (which outperforms the first one in most cases) follows a similar high-level structure of Singhal and Steinke [2021] . That is, to sample i.i.d. reference points p 1 , . . . , p q ∼ N ( ⃗ 0, I d×d ) for q = Θ(k), privately average the qd-dimensional points {(Π j p 1 , . . . , Π j p q )} t j=1 for obtaining a private P ∈ R q×d (whose i th row estimates the projection of p i onto the top-k rows subspace of X), and then compute the projection matrix of the top-k rows subspace of P . But unlike Singhal and Steinke [2021] who perform this step using a histogram-based averaging that has the same flavor of Karwa and Vadhan [2018] , we perform this step using FriendlyCore Tsfadia et al. [2022] that simplifies the construction and makes it practical in high dimensional regimes. We remark that in both aggregation types, we need a DP averaging algorithm that is resilient to a constant fraction of outliers (say, 20%) since both items in Lemma 2.1 only guarantee that the expected number of outliers is no more than 10%. Fortunately, FriendlyCore can be utilized for such regimes of outliers (see Appendix B.8.3 for more details).A few remarks are in order. Remark 2.2. The first aggregation type (which privately estimate the average of Π 1 , . . . , Π t directly) outperforms the second type only for our weak estimator in the regime k ≥ √ d (as it inherently posses larger dependency in the dimension). Remark 2.3. We could avoid the requirement σ 2 k ≥ 0.01n/k by adding an additional parameter η such that σ 2 k ≥ η • n/k, and using subsets of size m = Θ(k/η) (which would increase n by the same factor of 1/η). For readability purposes, we chose to avoid this additional parameter. Because our algorithms provide useful projection by estimating the actual top-k projection, then such a requirement is unavoidable if we would like to provide utility guarantees only as a function of the singular values. 6 In fact, any assumption that would imply that two random subsets induce similar top-k projection matrices would suffice for the utility analysis.Remark 2.4. To eliminate the known-γ assumption, we can replace the FriendlyCore-averaging step Tsfadia et al. [2022] (that requires to know the diameter) with their unknown diameter variant that gets two very rough bounds ξ min and ξ max , and performs a private binary search for estimating a good diameter ξ ∈ [ξ min , ξ max ] in a preprocessing phase. This step only replaces the dependency on d with d + log log(ξ max /ξ min ) in the asymptotic sample complexity (section 5.1.2. in Tsfadia et al. [2022] ) and is very practical. In fact, we use this method in our empirical evaluation in Section 4.For handling unknown values of k, note that our algorithms provide useful utility guarantees (compared to the additive-gap based ones) only when σ 2 k+1 ≪ 1. So in cases where σ 2 k ≥ 2 • log(k/β)/ε ′ for some (fixed) privacy budget ε ′ < ε (say, ε ′ = ε/10), we can privately determine w.p. 1 -β the right value of k using a simple ε ′ -DP method. The main observation is that the ℓ 1 sensitivity of the vector (σ 2 1 , . . . , σ 2 n ) is at most 2 (Amin et al. [2019] ), yielding that we can privately compute(σ ′2 1 , . . . , σ ′2 n ) = (σ 2 1 +Lap(2/ε ′ ), . . . , σ 2 n +Lap(2/ε ′ )), and then perform analysis on (σ ′2 1 , . . . , σ ′2 n ) to set k as the first index i where σ 2 i ≥ log(i/β)/ε ′ and σ 2 i+1 < log(i/β)/ε ′ .3 Lower Bounds -OverviewOur lower bounds (Theorems 1.8 and 1.9) use the recent framework of Peter et al. [2024] for generating smooth lower bounds for DP algorithms using Fingerprinting Codes (FPC), but require technically involved analysis due to the complex structure of this problem for k ≥ 2.Roughly speaking, let D be a distribution over {-1, 1} n0×d0 that induces an optimal FPC codebook with d 0 = Õ(n 2 0 ) (e.g., Tardos [2008] , Peter et al. [2024] ). The connection between FPC and DP (first introduced by Bun et al. [2014] ) is that any DP algorithm, given a random codebook X = (x j i ) i∈[n0],j∈[d0] ∼ D as input, cannot output a vector q = (q 1 , . . . , q d0 ) ∈ {-1, 1} d0 that "agrees" with most of the "marked" columns of X (Formally, for b ∈ {-1, 1}, a columns x j = (x j 1 , . . . , x j n ) is called b-marked if x j 1 = . . . = x j n = b, and q agrees with it if q j = b). Now consider a DP mechanism M : X n → W that satisfies some non-trivial accuracy guarantee. Peter et al. [2024] reduces the task of lower bounding n to the following task: (1) Generate from an FPC codebook X ∈ {-1, 1} n0×d0 hard instances Y ∈ X n for M, and (2) Extract from the output w ∼ M(Y ) a vector q ∈ {-1, 1} d0 that agrees with most of the marked columns of X (n 0 and d 0 are some functions of n, X and the weak accuracy guarantee of M). Peter et al. [2024] proved that if there exists such generating algorithm G and extracting algorithm F (which even share a random secret that M does not see) such that G is neighboring-preserving (i.e., maps neighboring databases to neighboring databases), then it must hold that n 0 ≥ Ω( √ d 0 ) (Otherwise, M cannot be DP).Warm-up: DP averaging. We first sketch how Peter et al. [2024] applied their framework with n 0 = n and d 0 = Θ(d/λ 2 ) for proving a lower bound for the simpler problem of DP averaging. In this setting, we are given a mechanism that guarantees λγ-accuracy (ℓ 2 additive error) for γ-easy instances (i.e., points that are γ-close to each other in ℓ 2 norm). The generator G, given an FPC codebook X ∈ {-1, 1} n0×d0 , uses the padding-and-permuting technique: It pads ℓ ≈ 10 4 λ 2 d 0 1-marked columns and ℓ (-1)-marked columns, and then permutes all the d = d 0 + 2ℓ columns of the new codebook X ′ using a random permutation π :[d] → [d]that is shared with the extractor F. The input Y to the algorithm would be the normalized rows of X ′ which are 1 100λ -close to each other in ℓ 2 norm, so the mechanism has to output an 1 100 -accurate solution w. In particular, after rounding w to {-1, 1} d , the coordinates of w must agree with a vast majority of the marked columns, and also with a vast majority of the original marked columns that are located within π(1), . . . , π(d 0 ) as it cannot distinguish between them and the other marked columns (because π is hidden from it). The extractor F, given w and π, rounds w to {-1, 1} d and outputs q = (w π(1) , . . . , w π(d) ) which agrees with most of the marked columns of X. Hence, we obtain the lower bound of n ≥ Ω( DP Subspace Estimation In our case, we are given a (weak or strong) subspace estimator√ d 0 ) = Ω( √ d/λ).M : (S d ) n → R d×d that outputs an λγ-useful rank-k projection matrix if σ k+1 (X) ≤ γσ k (X) (or min{n,d} i=k+1 σ i (X) 2 ≤ γσ k (X)). We prove our lower bounds by applying the framework with n 0 = n/k and d 0 = Θ(αd), for some parameter α = α(λ) that will depend on the type of M we consider. In order to generate hard instancesY ∈ (S d ) n for M given an FPC codebook X ∼ D (X ∈ {-1, 1} (n/k)×d0), we use a variation of the approach to Dwork et al. [2014] . Namely, our generatorG samples k independent FPC codebooks A 1 , . . . , A k ∼ D where it plants A i = X for a random i ← [k]. Then for each j ∈ [k],it applies (independently) the padding-and-permuting technique of Peter et al. [2024] where it pads ℓ 1-marked columns and ℓ (-1)-marked columns for ℓ ≈ d0 2α , and permute all the columns. This induces k matrices B 1 , . . . , B k ∈ {-1, 1} (n/k)×d (for d = d 0 + 2ℓ) such that each B j is "almost" rank-1 and their vertical concatenationB ∈ {-1, 1} n×d is almost rank-k. It provides Y = 1 √ d Bas the input for M. See Figure 1 for graphical illustrations. We remark that at this step, the main difference from Dwork et al. [2014] (who implicitly follow a similar paradigm) is that they use a fixed padding length of ℓ = 15d 0 that suffices for the robustness properties that they need. On the other hand, we use Peter et al. [2024] 's observation that increasing the padding can handle low-accuracy regimes of many problems, and indeed we use the padding length ℓ to increase the k'th singular value gap, which will be a function of the quality parameter λ.The next step is to choose the right value of α = α(λ) such that M, on input Y , will have to output a useful projection matrix. We show that the input matrix Y has w.h.p.σ 1 (Y ) 2 ≥ . . . ≥ σ k (Y ) 2 ≥ (1 -O(α)) • n k , which yields that min{n,d} i=k+1 σ i (Y ) 2 ≤ O(α)n. If M is a weak estimator, then we simply use α = Θ 1 λ 2 k to guarantee that min{n,d} i=k+1 σ i (Y ) 2 ≤ γ 2 • σ k (Y ) 2 for γ = 1 1000λ, which yields that by the utility guarantee of M, we get an 0.001-useful projection matrix. If M is a strong estimator, then we use α = Θ 1 λ 2 (i.e., we decrease the padding length by a factor of k). Yet, in order to meet the requirements of M, we must argue that w.h.p., σ k+1 (Y ) 2 ≤ Õ(α) • n k , and this is more complex than the previous case. Here we use more internal properties of the fingerprinting distribution D. Namely, that in Peter et al. [2024] 's construction (which is also true for Tardos [2008] 's one), each entry of the codebook matrix has expectation 0 and the columns of the matrix are independent. Using known concentration bounds, this allows us to argue that if we pick a unit vector v that is orthogonal to the top-k rows subspace of Y , then with probability at least1 -exp(-Ω(d)) it holds that ∥Y v∥ 2 2 ≤ Õ(α) • n k . Since σ 2 k is bounded by the supremum of ∥Y v∥ 2 2under such unit vectors, we conclude the proof of this part using a net argument.Finally, the last step, which is not trivial for k ≥ 2, is to extract from an 0.001-useful projection matrix Π for Y , a vector q ∈ {-1, 1} d0 that with noticeable probability, strongly agrees with the marked columns of the original codebook X ∈ {-1, 1} n0×d0 . For that, our extractor F uses the random permutations and the random location i (which are part of the shared secret between the generator and the extractor) and follows the strategy of Dwork et al. [2014] . That is, it applies the i th invert permutation over the columns of Π (denote the resulting matrix by Π i ), chooses a vector u ∈ Span( Π i ) that has the maximal agreement with half of the padding bits, and then simply outputs its first d 0 coordinates after rounding to {-1, 1}. The intuition is that an 0.001-useful projection matrix must be also 0.001-useful for at least one of the parts Y j = 1 √ d B j . Since all the Y j 's have the same distribution and the location i (where the original X is planted) is hidden from M, then it must be 0.001-useful for Y i with probability at least β/k (where β denotes the success probability of M). Given that this event occurs, the usefulness of Π implies that there must exists a vector in Span( Π i ) that strongly agrees with half of the padding locations. But because all the marked columns (that includes the padding locations) are indistinguishable from the eyes of M who computed Π, then a similar agreement must hold for the marked columns of X.In this section, we prove Theorem 1.6, stated below.Theorem C.5 (Restatement of Theorem 1.6). Let n, k, d ∈ N, λ > 0, ε, δ ∈ (0, 1]where k ≤ min{n, d}. There exists an (k, λ, β = 0.9,γ max = Ω(min{ 1 λ , 1}))-weak subspace estima- tor M : (S d ) n × [0, 1] → R d×d with n = O k log k log(1/δ) ε + min{k √ d, d} log(1/δ) λε such that M(•, γ) is (ε, δ)-DP for every γ ∈ [0, 1].Theorem C.5 is an immediate corollary of the following Lemmas C.6 and C.7. 20) λεLemma C.6. Let t = c 1 • log(1/δ) ε + d √ log(1/δ) log((where c 1 is the hidden constant in Fact B.26). Then for any n ≥ 800k ln(25k) • t, the mechanism M : (S d ) n × [0, 1] → W d,k defined by M(X, γ) := EstSubspace Naive_Agg ε,δ,ξ=60γ k,t (X) is an (k, λ, β = 0.9, γ max = 1 20 )-weak-subspace- estimator. Proof. Let X ∈ (S d ) n with min{n,d} i=k+1 σi(X) 2 σ k (X) 2≤ γ ≤ γ max and let Π ∈ W d,k be the projection of the top-k rows subspace of X. Consider a random execution of M(X). Let {Π j } t j=1 , Π be (random variables of) the values of {Π j } t j=1 , Π in the execution, and let Π be the output. By Lemma C.4(2) (recall that γ max ≤ 1 20 ) and the union bound,EQUATIONLet a j = 1{∥Π -Π j ∥ ≤ 60γ} (indicator random variable) and let a = t j=1 a j . By Equation (3) it holds that E[a] ≥ 0.99t, and recall that a ≤ t. It follows thatEQUATIONIn the following we assume that the event a ≥ 0.8t occurs. Let J = {j ∈ [t] : a j = 1}. Note that our choice of t satisfies EQUATIONt = c •   log(1/δ) ε + √ k+ log dk log(1/δ) λε √ kd log(1/δ) λε   , η = c 1 • √ k + ln(qt) and q = c 2 • k. Then for any n ≥ 800k ln(25k) • t, the mechanism M : (S d ) n × [0, 1] → W d,k defined by M(X, γ) := EstSubspace SS_Agg ε,δ,k,q,ξ=120η √ kγ k,t (X) is an (k, λ, β = 0.9, γ max = Θ(min{ 1 λ , 1}))-weak-subspace-estimator. Proof. Let X ∈ (S d ) n with min{n,d} i=k+1 σi(X) 2 σ k (X) 2 ≤ γ ≤ γ max and let Π ∈ W d,kbe the projection of the top-k rows subspace of X.Consider a random execution of M(X). Let {Π j } t j=1 , {p i } q i=1 , {y j } t j=1 , z, P be (random variables of) the values of {Π j } t j=1 , {p i } q i=1 , {y j } t j=1 , z, P in the execution, and let Π be the output. As in the proof of Lemma C.6, let a = t j=1 a j where a j = 1{∥Π -Π j ∥ ≤ 60γ}. Then Equation ( 4) imples that Pr[a ≥ 0.8t] ≥ 0.95.In the following we assume that the event a ≥ 0.8t occurs. Let J = {j ∈ [t] : a j = 1}. By Fact B.14 and the definition of η we obtain thatPr ∀i ∈ [q], j ∈ J : ∥(Π -Π j )p i ∥ 2 ≤ 60ηγ ≥ 0.95,In the following we assume that the above event occurs. This yields that ∀i, j ∈ J :∥y i -y j ∥ 2 ≤ 120η √ kγ = ξ.Furthermore, by the definition of t and η (note that η depends on log(t)), it holds thatt ≥ c ′ •   log(1/δ) ε + dk log(1/δ) c3λ 1500η • ε   ,where c ′ denotes the constant from Fact B.26. Therefore we obtain by Fact B.26 (FriendlyCore averaging) thatPr    P -P F ≤ c 3 λ √ kγ 12 α    ≥ 0.99,where P is the q × d matrix whose rows are Πp 1 , . . . , Πp q . By Fact B.15 we have thatPr σ k (P) ≥ c 3 √ k ≥ 0.95,and in the following we assume that the above event occurs (which in particular implies that Span(P T ) = Span(Π)). Finally, since 2α ≤ σ k (P) by assumption (and assuming γ max ≤ 6 c3λ ), we conclude by Proposition B.13 thatΠ -Π F ≤ 2 √ 2 • α σ k (P ) -α ≤ λγ/2.We therefore conclude the proof of the lemma by Proposition B.16.In this section, we prove Theorem 1.7, stated below. Theorem C.8 (Restatement of Theorem 1.7). Let n, k, d ∈ N, λ > 0, such that k ≤ min{n, d}.There exists an (k, λ, β = 0.8, γ max )-weak subspace estimator M :(S d ) n × [0, 1] → R d×d with γ max = Ω   min{ 1 λ , λ 2 ε 2 λ 2 ε log(1/δ) + k + log dk log(1/δ) λε dk log(1/δ) }   and n = O   k log k   log(1/δ) ε + k + log dk log(1/δ) λε dk log(1/δ) λ 2 ε 2     such that M(•, γ) is (ε, δ)-DP for every γ ∈ [0, 1].Lemma C.9. Let c 1 , c 2 , c 3 be the constants from Facts B.14 to B.15 (respectively), and let c be a largeenough constant. Let t = c • log(1/δ) ε + (k+log( dk log(1/δ) λε ))dk log(1/δ) λ 2 ε 2 , η = c 1 • √ k + ln(qt) and q = c 2 • k. Then for any n ≥ 800k ln(25k) • t, the mechanism M : (S d ) n × [0, 1] → W d,k defined by M(X, γ) := EstSubspace SS_Agg ε,δ,k,q,ξ=8 √ 2tkηγ k,t (X) is an (k, λ, β = 0.8, γ max = min{ 1 2t , 6 c3λ })- strong-subspace-estimator. Proof. Fix X ∈ (S d ) n with σ k+1 (X)σ k (X) ≤ γ ≤ γ max and let Π ∈ W d,k be the projection of the top-k rows subspace of X. Consider a random execution of M(X). Let {Π j } t j=1 , {p i } q i=1 , {y j } t j=1 , z, P be (random variables of) the values of {Π j } t j=1 , {p i } q i=1 , {y j } t j=1 , z, P in the execution, and let Π be the output. By Lemma C.4(1) (recall that γ max ≤ 1 2t ) and the union bound,EQUATIONLet a j = 1{∥Π -Π j ∥ ≤ 4 √ 2tγ} (indicator random variable) and let a = t j=1 a j . As in Equation (4), the above yields thatEQUATIONIn the following we assume that the event a ≥ 0.8t occurs. Let J = {j ∈ [t] : a j = 1}. By Fact B.14 and the definition of η we obtain thatPr ∀i ∈ [q], j ∈ J : ∥(Π -Π j )p i ∥ 2 ≤ 4 √ 2tηγ ≥ 0.95,In the following we assume that the above event occurs. This yields that ∀i, j ∈ J :∥y i -y j ∥ 2 ≤ 8 √ 2tkηγ = ξ.Furthermore, by the definition of t and η, it holds thatt ≥ c ′ •   log(1/δ) ε + dk log(1/δ) c3λ 150η √ t • ε   ,where c ′ denotes the constant from Fact B.26. Therefore we obtain by Fact B.26 (FriendlyCore averaging) thatPr    P -P F ≤ c 3 λ √ kγ 12 α    ≥ 0.99,where P is the q × d matrix whose rows are Πp 1 , . . . , Πp q . By Fact B.15 we have thatPr σ k (P) ≥ c 3 √ k ≥ 0.95,and in the following we assume that the above event occurs (which in particular implies that Span(P T ) = Span(Π)). Finally, since 2α ≤ σ k (P) by assumption (and using γ max = 6 c3λ ), we conclude by Proposition B.13 thatΠ -Π F ≤ 2 √ 2 • α σ k (P ) -α ≤ λγ/2.We therefore conclude the proof of the lemma by Proposition B.16. □In this section, we prove our lower bounds. In Appendix D.1 we prove Theorem 1.8 (lower bound for weak estimators) and in Appendix D.2 we prove Theorem 1.9 (lower bound for strong estimators).Both lower bounds rely on the framework of Peter et al. [2024] , described in Appendix B.8.5. In the following, we define random variables X ∼ D(n 0 , d 0 ) (Definition B.30) and z = (s, (P 1 , . . . , P k )) ← Z, and consider a random execution ofλ 2 k , n 0 = n/k, ℓ = 2 • 1 4 (1 -α)d , d 0 = d -2ℓ, X = S d , Z = [k] × (P d ) k and W = W d,k . Let G : {-1, 1} n0×d0 × Z → X n be Algorithm D.EQUATIONThe following claim holds under our assumption that λ 2 ≤ d ck log k for large enough constant c. Claim D.5. Let γ = 1 1000λ . It holds thatEQUATIONwhere the last inequality holds since ℓ ≈ d/2 ≥ c • k/2 for large enough constant c > 0. Furthermore, note that for every s, t ∈ [k], 2ℓ • ⟨v s , v t ⟩ = j : sign(v j s )=1 sign(v j t )j : sign(v j s )=-1 sign(v j t ) where each sum has Hypergeometric distributions HG 2ℓ,0,ℓ (Definition B.5) . Therefore by Fact B.6 and the union bound, it holds thatEQUATION(i.e., v 1 , . . . , v k are almost orthogonal).In the following, we assume that the events in Equations ( 8) and ( 9) occur. {-1, 1} d0 × (1, . . . , 1 ℓ , -1, . . . , -1 ℓ ) • P t = {-1, 1} d0 × (0, . . . . . . , 0 2ℓ ) • P t + 2ℓ d • v tTherefore, we obtain that∥Y • u t ∥ 2 2 ≥ ∥Y t • u t ∥ 2 2(10)≥ ⟨ 2ℓ d v t , u t ⟩ 2 - d 0 d • n 0 ≥ (1 -α) • 1 -O log k d 2 -α • n 0 ≥ (1 -4α) • n 0 ,where the last inequality holds whenever α ≥ Θ(log k/d), which holds by the assumption on λ.We therefore obtain thatEQUATIONwhere the second inequality holds since α =1 5•10 6 λ 2 k . □The following claim holds under our assumption that d ≥ ck for large enough constant c > 0. Claim D.6. It holds that Pr sign(u) [d]\H strongly-agrees withB s P T s [d]\H ≥ 0.8β k .where "strongly-agrees" is according to Definition B.36.Proof. In the following we assume that the 0.9 probability event in Claim D.5 occurs. Since M is (k, λ, β, γ max = 1 1000λ )-subspace estimator, it follows from Equation (11) that w.p. β, the output Π of M(Y) satisfyEQUATIONwhere we denote by Π the projection matrix onto Span{v 1 , . . . , v k } (defined in Equation ( 7)). In the following, we assume that the event in ( 12) occurs. This yields that there must exists t ∈[k] such that Π • Y T t 2 F ≥ Π • Y T t 2 F - n 1000k ≥ 2ℓ d • ∥v t ∥ 2 2 • n k - n 1000k ≥ (0.999 -α) • n kSince s (part of z) is chosen at random and does not change the distribution of Y (the input of the mechanism), w.p. 1/k the above holds for t = s, i.e.,EQUATION)In the following we assume that the 1/k-probability event in Equation ( 13) occurs.EQUATIONIn the following, defineEQUATIONNote that each row i of B ′ s can be written as v + ξ i where ξ i ∈ {-1, 0, 1} d0 × (0, . . . , 0). This yields thatΠ s • v T 2 2 = k n • Π s • (B ′ s ) T 2 F - k n n/k i=1 Π s • ξ T i 2 2 ≥ (0.999 -α)d -d 0 ≥ (0.999 -2α)d Now, since ∥v∥ 2 2 = ⟨v, v⟩ = ⟨ Π t v T + (I -Π t )v T , Π t v T + (I -Π t )v T ⟩ = Π t v T 2 2 + (I -Π t )v T 2 2 ,we conclude that for ṽT = Π t v T ∈ Span( Π t ):EQUATION)We next define (I, η)-good vectors.Definition D.7. We say that a vector w ∈ {-1, 1} d is (I, η)-good iff for (1 -η) fraction of the indices j ∈ I it holds that sign(w j ) = sign(v j ) (for the v defined in Equation ( 15)).We use the following trivial fact:Observation D.8. If w is not (I, η)-good, then ∥w -v∥ Since for both b ∈ {-1, 1}, |H b | ≥ 1 4 (1 -α)d ≥ d/5and ∥v -ṽ∥ 2 2 ≤ d 500 , Observation D.8 implies that ṽ is (H 1 , η)-good and (H -1 , η)-good for η = 1 100 . Therefore, the vector u (computed in F) is also (H 1 , η)-good and (H -1 , η)-good.In the following, we use similar arguments to Dwork et al. [2014] for claiming that because u is good on half of the padding location, then it should also be good on the rest of the marked locations.From the point of view of the algorithm M (which does not know P s ), the locations in H b are indistinguishable from those in F b \ H b . Therefore, for any point that is not (F b , 3η)-good, the probability (taken over the random choice of P s ) that it is (H b , 2η)-good is at most exp(-Ω(η 2 d)). Now let N be an (η (k)) • exp(-Ω(η 2 d)) ≤ 0.01, any given vector in N that is (H b , 2η)-good is also (F b \ H b , 4η)-good. Since u is (H b , η)-good, then its nearest net point u ′ is (H b , 2η)-good. Thus u ′ is (F b \ H b , 4η)-good which implies that u is (F b \ H b , 5η)-We now ready to prove the final claim that concludes the proof of Lemma D.2.Claim D.9. It holds that Pr r,r ′ ←{0,1} m , X∼D A Mr,F,G r ′ (X) is strongly-correlated with X ≥ 0.8β k .Proof. In the following we assume that the event from the statement of Claim But note that B ′ = PAP n0,d0,ℓ/2 (X, P ′ ) and also note that q ′ is just a function of Π ′ and P ′ (i.e., independent of P ′ ) since it equals to sign(w) P ′ ([d]\H) where w is the vector in Span( Π) that maximizes min{ j∈P ′ (H1) sign(w j ), -j∈P ′ (H-1) sign(w j )}. Furthermore, note that (q ′ • (P ′ ) T ) 1,...,d0 = q, where q is the final output of A M,F,G (X) = F(z, M(G(X, z))). Thus by Lemma B.37 and Equation (17) we conclude thatPr r,r ′ ←{0,1} m , X∼D A Mr,F,G r ′ (X) is strongly-correlated with X ≥ 0.8β k . □ D.2 Strong Estimators Theorem D.10 (Restatement of Theorem 1.9). Let n, k, d ∈ N, λ ≥ 1, β ∈ (0, 1] such that d ≥ ck and λ 2 ≤ d c log k for large enough constant c > 0, and n is a multiple of k. If M : (S d ) n × [0, 1] → R d×d is an (k, λ, β, γ max = 1 10 6 λ 2 )-strong subspace estimator and M(•, γ) is 1, β 5nk -DP for every γ ∈ [0, 1], then n ≥ Ω k √ d/λ log 1.5 ( dk λβ ) √ log(dk) log(2n/k).We prove Theorem D.10 using a similar technical lemma to Lemma D.2, but now since M is a strong subspace estimator, we can use α = Θ 1 λ 2 (rather than Θ 1 λ 2 k as in Lemma D.2). Lemma D.11. There exists large enough constant c > 0 such that the following holds: Let n, k, d, λ, β and M as in Theorem D.10, let α = 1 c•log(dk) log(2n/k)•λ 2 , n 0 = n/k, ℓ = 2• 1 4 (1 -α)d , d 0 = d -2ℓ, X = S d , Z = [k] × (P d ) k and W = W d,k . Let G : {-1, 1} n0×d0 × Z → X n be Algorithm D.M,F,G (X) = F(z, M(G(X, z))). Let {A t }, {B t }, Y be the values of {A t }, {B t }, Y ∈ (S d n in the execution of G, and recall that Y is a vertical concatenation of Y 1 , . . . , Y k where Y t = 1 √ d B t .The only difference from proving Lemma D.2 is to prove a different version of Claim D.5 that only considers the gap between σ k and σ k+1 (which will meet the requirements of the strong estimator M). Namely, is suffices to prove the following claim: Claim D.12. It holds thatPr[σ k+1 (Y) ≤ γ • σ k (Y)] ≥ 0.9, for γ = 1 1000λ .Proof of Claim D.12. As in Equation ( 7), for t ∈ [k] we define EQUATIONThis yields (using similar steps as in the proof of Claim D.5) that w.p. 0.98, dim(E) = k and every unit vector u ∈ E has ∥Yu∥2 2 ≥ (1 -4α) n k . This in particular implies that σ 2 k (Y) ≥ (1 -4α) n k .Our goal is to prove that w.p. 0.99 it also holds that σ 2 k+1 (Y) ≤ Õ(α) n k . Let Ē be the orthogonal subspace to E. Our goal is reduced to showing that there exists a constant c such thatEQUATION)Given that the event in Equation ( 20) holds we conclude that σ2 k+1 (Y) ≤ α•c log(k/α) log(2n/k)• n k and hence σ 2 k+1 (Y) σ 2 k (Y) ≤ α • c log(k/α) log(2n/k) • n k (1 -4α) • n k ≤ 1 10 6 λ 2 = γ 2 ,where the last inequality holds by takingα = 1 2 • 10 6 • c log(k/α) • log(2n/k) • λ 2 . Note that for every u ∈ Ē ∩ S d is holds that ∥Yu∥ 2 2 = k t=1 ∥Y t u∥ 2 2 = 1 d k t=1 ∥A t u∥ 2 2 ,where the last equality holds since u is orthogonal to v 1 , . . . , v k . Therefore, we can prove Equation (20) by proving that there exists a constant c ′ such thatEQUATIONGiven that Equation ( 21) holds, we prove the claim using a net argument. By taking an exp(d ln(3k/α))-size α/k-net of S d (Fact B.10), Equation ( 20) follows by Equation ( 21) and the union bound over all the net points, which concludes the proof of the claim.In the we focus on proving Equation ( 21). i,t , u⟩ 2 ≥ ξ = E J Pr ⟨a i,t , u J ⟩ 2 ≥ ξ ≤ E J 2 exp - dξ 2∥u J ∥ 2 2 ≤ 2 exp   - dξ E 2∥u J ∥ 2 2   ≤ 2 exp - dξ 2α ,where the first inequality holds by Fact B.2, the second one holds by Jensen's inequality (and since the function f (x) = e -1/x is concave), and the last one hold since E ∥u J ∥ 2 2 = d0 d ≤ α. By the union bound over the n/k rows of A t we obtain that ∀ξ ≥ 0 : Pr ∥A t w∥EQUATIONIn the following, let b t = ∥Y t u∥ . First, note thatE[b t ] = ∞ 0 Pr[b t > ξ]dξ = µ + ∞ µ Pr[b t > ξ]dξ ≤ µ + ∞ µ 2n k • exp - dk 2αn • ξ dξ = µ + - 2n k • 2αn dk • exp - dk 2αn • ξ ∞ µ ≤ 2αn dk ≤ 2µ.In where the second inequality holds assuming that c is large enough. This concludes the proof of Equation ( 21) and therefore the proof of the lemma. □In this work we develop algorithms that maintain the differential privacy of the input points. When the points represent individuals, our work helps to maintain the privacy of those individuals.• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
empirical evaluation: 
 We implemented a zCDP (Definition B.24) variant of our subspace estimation algorithm in Python (denoted by EstSubspace), and in this section we present empirical results for the fundamental task of privately estimating the average of d dimensional points that approximately lie in a much smaller k-dimensional subspace. Namely, given a dataset X = (x 1 , . . . , x n ) ∈ S n d , a parameter k, and zCDP parameters ρ, δ, we perform the following steps: (a) Compute a (ρ/2, δ)-zCDP rank-k projection matrix Π using EstSubspace that estimates the projection onto the top-k rows subspace of X, (b) Compute a ρ/2-zCDP estimation of the average of X using the Gaussian Mechanism:x = 1 n n i=1 x i + N (0, σ 2 • I d×d ) for σ = 2 n √ ρ , and (c) Output x = Π • x.The accuracy is measured by the ℓ 2 error from the average:x -1 n n i=1 x i 2 .In all our experiments, we use ρ = 2 and δ = 10 -5 , t = 125 (the number of subsets in the sampleand-aggregate process), n = 2tk data points, q = 10 • k (the number of reference points in the aggregation), and use the zCDP implementation of the FriendlyCore-based averaging algorithm of Tsfadia et al. [2022] . 7 All experiments were tested on a MacBook Pro Laptop with 8-core Apple M1 CPU with 16GB RAM.Rather than using Tsfadia et al. [2022] 's algorithm for the known-diameter case, we use their unknown-diameter implementation with ξ min = 10 -6 and ξ max = 100 (see Remark 2.4 for details). Furthermore, we reduced the space complexity of our implementation from Θ(d 2 ) to Θ(kd).8 In order to generate a synthetic dataset that approximately lie in a k-dimensional subspace, we initially sample uniformly random b 1 , . . . , b k ← {-1, 1} d and perform the following process to generate each data point: (i) Sample a random unit vector u in Span{b 1 , . . . , b k }, (ii) Sample a random noise vector ν ← {1/τ, -1/τ } d , and (iii) Output u+ν ∥u+ν∥ (note that higher τ results with data points that are closer to a k-dimensional subspace).We compare our averaging method to two other approaches: The first one simply applies the Gaussian mechanism directly on X = (x 1 , . . . , x n ) using the entire privacy budget ρ (i.e., without computing a projection matrix). The second one replaces our Step (a) by computing the projection matrix Π using a (ρ/2, δ)-zCDP variant of the additive-gap based algorithm of Dwork et al. [2014] (see Appendix B.8.4 for more details). 9 The empirical results are presented in Figure 2 . In all experiments, we perform 30 repetitions for generating each graph point which represents the trimmed average of  
limitations and future directions: 
 From a theoretical perspective, our work is the first to provide proper measures for how "easy" a given dataset is which smoothly eliminates the dependency on the dimension d. Yet, closing the gap between our upper and lower bounds is still left open. Specifically, for weak estimator, there is still a gap of k 1.5 between Theorems 1.6 and 1.8. For strong estimators, the upper-bound rate n = n(λ) (Theorem 1.7) does not align with the one of the lower bound (Theorem 1.9), and it is left open to relax the restriction on γ max . One possible reason for some of these gaps (especially the dependency in k) is that our upper bounds follow the approach of Singhal and Steinke [2021] to estimate (under some matrix norm) the projection matrix to the top-k rows subspace (we do it in Frobenius norm). While estimating the projection matrix itself provides, in particular, a useful solution (Proposition B.16), the opposite direction is not true in general, and it could be possible to reduce the sample complexity by focusing on α-usefulness (Definition 1.2) directly, or alternatively, providing stronger lower bounds for estimating the projection matrix.From a more practical standpoint, we empirically demonstrate the advantage of our approach in high-dimension regimes when the data is very close to a low-dimensional structure, which is directly translated to an advantage in private mean estimation of such instances. The downside of our approach is that it requires the points to be very close to a k-dimensional structure in order to be effective, which might not be sufficient for typical training scenarios in deep learning. It would be intriguing to explore if there is a connection between training parameters (e.g., the network structure) to the phenomena of gradients that are close to a low-dimensional subspace (mentioned in Section 1.1). If we could boost this closeness to regimes where our method achieves high accuracy, we could generate drastically improved private models. On the other hand, if we cannot do it, then our lower bounds indicate that improving DP-SGD via private subspace estimation might not be the right approach, and we should focus on different approaches for this task. A closely related line of work is on Private PCA. Dwork et al. [2014] consider the simple algorithm that adds independent Gaussian noise to each entry of the covariance matrix A = n i=1 x T i x i ∈ R d×d , and then performs analysis on the noisy matrix. This method, predating the development of differential privacy Blum et al. [2005] , was later analyzed under differential privacy by McSherry and Mironov [2009] and Chaudhuri et al. [2013] . 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 is inherent for any instances (including "easy" ones). While this approach has a variant that improves the accuracy of estimating the top-k subspace as a function of the additive gap σ 2 k -σ 2 k+1 (Appendix B.8.4), it does not prevent the polynomial dependency on the dimension d even for very easy instances.Techniques from dimensionality reduction have been applied by Hardt and Roth [2012] and Arora et al. [2018] to privately compute a low-rank approximation to the input matrix X. Similarly, Hardt and Roth [2013] and Hardt and Price [2014] utilize the power iteration method with noise injected at each step to compute low-rank approximations to X. Despite their effectiveness, these methods, relying on noise addition, require sample complexity to grow polynomially with the ambient dimension to achieve meaningful guarantees.Another approach, employed by Blocki et al. [2012] and Sheffet [2019] , involves approximating the covariance matrix A using dimensionality reduction. 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). Chaudhuri et al. [2012] , Kapralov and Talwar [2013] , Wei et al. [2016] apply variants of the exponential mechanism McSherry and Talwar [2007] to privately select a 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.Gonem and Gilad-Bachrach [2018] exploit smooth sensitivity Nissim et al. [2007] to release a lowrank 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. A recent popular trend in DP learning is to utilize a few public examples to enhance accuracy. This has led to methods for private ML which project the sensitive gradients onto a subspace estimated from the public gradients. By using a small amount of i.i.d. public data, Zhou et al. [2021] demonstrate that this approach can improve the accuracy of differentially private stochastic gradient descent in high-privacy regimes and achieve a dimension-independent error rate. Similarly, Yu et al. [2021] proposed GEP, a method that utilizes public data to identify the most useful information carried by gradients, and then splits and clips them separately. These works underscore the importance of identifying the subspace of gradients in private ML.We use calligraphic letters to denote sets and distributions, uppercase for matrices and datasets, boldface for random variables, and lowercase for vectors, values and functions. For n ∈ N, let[n] = {1, 2, . . . , n}. Throughout this paper, we use i ∈ [n] as a row index, and j ∈ [d] as a column index (unless otherwise mentioned).For a matrix X = (x j i ) i∈[n],j∈[d] , we denote by x i the i th row of X and by x j the j th column of X. A column vector x ∈ R n is written as (x 1 , . . . , x n ) or x = x 1...n , and a row vector y ∈ R d is written as (y 1 , . . . , y d ) or y 1...d . In this work we consider mechanisms who receive an n × d matrix X as input, which is treated as the dataset X = (x 1 , . . . , x n ) where the rows of X are the elements (and therefore, we sometimes write X ∈ (R d ) n instead of X ∈ R n×d to emphasize it).For a vector x ∈ R d we define ∥x∥ 2 = n i=1 x 2 i (the ℓ 2 norm of x), and for a subset S ⊆ [d] we define x S = (x i ) i∈S , and in case x is a row vector we write x S . Given two vectors x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ), we define ⟨x, y⟩ = n i=1 x i y i (the inner-product of x and y). We denote by S d the set of d-dimensional unit vectors, that is,S d = {v ∈ R d : ∥v∥ 2 = 1}. For a matrix X = (x j i ) i∈[n],j∈ [d] we let ∥X∥ = max v∈S d ∥Xv∥ 2 (the spectral norm of X) and let For z ∈ R, we define sign(z∥X∥ F = i∈[n],j∈[d] (x j i ) 2 (the Forbenius norm of X). For a matrix X = (x j i ) i∈[n],j∈[d] ∈ {-1,) := 1 z ≥ 0 -1 z < 0 and for v = (v 1 , . . . , v d ) ∈ R d we define sign(v) := (sign v 1 , . . . , sign v d ) ∈ {-1, 1} d .Given a distribution D, we write x ∼ D to denote that x is sampled according to D. For a set S, we write x ← S to denote that x is sampled from the uniform distribution over S.For a matrix X ∈ R n×d , the singular value decomposition of X is defined by X = U ΣV T , where U ∈ R n×n and V ∈ R d×d are unitary matrices. The matrix Σ ∈ R n×d is a diagonal matrix with non-negative entries σ 1 ≥ . . . ≥ σ min{n,d} ≥ 0 along the diagonal, called the singular values of X.The SVD of X can also be written in the form X = min{n,d} i=1σ i u i v T i, where u i and v i are the i th columns of U and V (respectively). It holds that ∥X∥ 2 F = i σ 2i and ∥X∥ = σ 1 . We define the top-k rows subspace of X as the subspace spawned by the first k columns of V . Fact B.1 (Min-Max principle for singular values). For every matrix X ∈ R n×d and i ∈ [min{n, d}] it holds thatσ i (X) = max dim(E)=i min v∈S d ∩E ∥Xv∥ 2 = min dim(E)=i max v∈S d ∩E ∥Xv∥ 2 .Fact B.2 (Montgomery- Smith [1990] ). Let x = (x 1 , . . . , x n ) where the x i 's are i.i.d. random variables with Pr[x i = 1] = Pr[x i = -1] = 1/2, and let v ∈ R n . Then ∀t ≥ 0 : Pr[|⟨x, v⟩| > t • ∥v∥ 2 ] ≤ 2 exp(-t 2 /2).Fact B.3 (Bernstein's Inequality for sampling without replacement (Bardenet and Maillard [2015] , Proposition 1.4)). Let x 1 , . . . , x m be a random sample drawn without replacement from {w 1 , . . . ,w n } for n ≥ m. Let a = min i∈[n] w i , b = max i∈[n] w i , µ = 1 n n i=1 w i and σ 2 = 1 n n i=1 (w i -µ) 2 . Then for every t ≥ 0, Pr m i=1 x i -m • µ ≥ t ≤ 2 • exp - t 2 mσ 2 + (b -a)t/3 .The following proposition is used for proving Lemma , it holds thatPr ∥X ′ v∥ 2 2 - m n a 2 ≥ 2 m n a 2 ln(1/β) ≤ 2β.Proof. The random variable ∥X ′ v∥ 2 2 is distributed as the sum of a uniformly random m-size subset of (⟨x 1 , v⟩ 2 , . . . , ⟨x n , v⟩ 2 ) (each element is bounded in [0, 1]). In the notations of Fact B.3, it holds that µ = 1 n n i=1 ⟨x i , v⟩ 2 = a 2 /n, andσ 2 = 1 n n i=1 (⟨x i , v⟩ 2 -a 2 /n) 2 = 1 n n i=1 (⟨x i , v⟩ 4 -2⟨x i , v⟩ 2 a 2 /n + a 4 /n 2 ) = 1 n n i=1 ⟨x i , v⟩ 4 -a 4 /n 2 ≤ 1 n n i=1 ⟨x i , v⟩ 2 = a 2 /n,where the last inequality holds since ⟨x i , v⟩ 2 ≤ 1. Let t = 2 m n a 2 ln(1/β). By Fact B.3, Pr ∥X ′ v∥ 2 2 - m n a 2 ≥ t ≤ 2 • exp - t 2 m n a 2 + t/3 = 2 • exp - 2 m n a 2 ln(1/β) m n a 2 + 2 m n a 2 ln(1/β)/3 ≤ 2 • exp - 2 m n a 2 ln(1/β) 2 m n a 2 ≤ 2β,]). Let X, Y, Z ∈ R n×d such that X = Y + Z. Let [U U ⊥ ]Σ[V V ⊥ ] T be the SVD of Y , and let [ U U ⊥ ] Σ[ V V ⊥ ] T be the SVD of X, where U, V, U , V denote the first k columns of [U U ⊥ ], [V V ⊥ ], [ U U ⊥ ], [ V V ⊥ ] (respectively). Let Z 12 = Π U ZΠ V ⊥ and Z 21 = Π U ⊥ ZΠ V . In addition, let z ij = ∥Z ij ∥, let α = σ min (U T XV ) (i.e., the smallest singular value larger than 0), and Y ) , andβ = U T ⊥ XV ⊥ . If α 2 > β 2 + min{z 2 12 , z 2 21 }, then Π V -Π V ≤ 2 • αz 12 + βz 21 α 2 -β 2 -min{z 2 12 , z 2 21 } and Π V -Π V F ≤ √ 2 • α∥Z 12 ∥ F + β∥Z 21 ∥ F α 2 -β 2 -min{z 2 12 , z 2 21 } . Proposition B.12. Let X, Y, Z, V, V as in Fact B.11 such that Y has rank-k and Span(Y T ) is orthogonal to Span(Z T ). If σ k (Y ) 2 ≥ 2∥Z∥ 2 , then 1. Π V -Π V ≤ 4 • ∥Z∥ σ k (2. Π V -Π V F ≤ 2 √ 2 • ∥Z∥ F σ k (Y ) .Proof. Note that Span(V ) = Span(Y T ). Therefore ZV = 0, which implies thatZ 21 = Π U ⊥ ZΠ V = 0. Compute α = σ min (U T XV ) = σ min (U T Y V + U T ZV 0 ) = σ k (Y ). β = U T ⊥ XV ⊥ = U T ⊥ Y V ⊥ 0 +U T ⊥ ZV ⊥ ≤ ∥U ⊥ ∥ • ∥Z∥ • ∥V ⊥ ∥ ≤ ∥Z∥. ∥Z 12 ∥ = ∥Π U • Z • Π V ⊥ ∥ ≤ ∥Z∥, ∥Z 12 ∥ F ≤ ∥Π U • Z • Π V ⊥ ∥ F ≤ ∥Z∥ F ,where the last inequalities in the above two equations hold since for any matrix A and projection matrices Π 1 , Π 2 it holds that ∥Π 1 AΠ 2 ∥ ≤ ∥A∥ and ∥Π 1 AΠ 2 ∥ F ≤ ∥A∥ F . The proof now immediately follows by applying Fact B.11. □ Proposition B.13. Let P ∈ R n×d be a rank-k matrix and let P ′ ∈ R n×d such that ∥P -P ′ ∥ F ≤ α.Let Π be the projection matrix onto Span(P T ), and let Π ′ be the projection onto the top-k rows subspace of P ′ . If σ k (P ) ≥ 2α, then∥Π -Π ′ ∥ F ≤ 2 √ 2 • α σ k (P ) -α .Proof. Let E = P ′ -P , and divide E into E = E P + E P where the rows of E P belong to the rows subspace of P and the rows of E P are orthogonal to it. Let Y = P + E P , so we can write P ′ = Y + E P . Note that ∥E P ∥ F ≤ α,Pr ∀i ∈ [q], j ∈ [t], ∥(Π -Π j )p i ∥ 2 ≤ O α √ k + ln(qt) ≥ 0.95.Fact B.15 (Implied by the proof of Lemma 4.9 in Singhal and Steinke [2021] ). Let Π ∈ W d,k and let p 1 , . . . , p q be i.i.d. random vectors in R d from N ( ⃗ 0, I d×d ). Let P be the d × q matrix whose columns are Πp 1 , . . . , Πp q . If q ≥ c • k for some large enough constant c, then w.p. 0.95 it hold that σ k (P) ≥ Ω( √ k) (and in particular, Span(P) = Span(Π)).Proposition B.16. For any Π, Π ∈ W d,k and X ∈ (S d ) n , it holds thatΠ • X T 2 F -Π • X T 2 F ≤ 2n • Π -Π F . Proof. Compute ΠX T 2 F -ΠX T 2 F = ( ΠX T F -ΠX T F ) • ( ΠX T F + ΠX T F ) ≤ ( ΠX T F -ΠX T F ) • 2 √ n ≤ (Π -Π)X T F • 2 √ n ≤ Π -Π F • X T F • 2 √ n = 2n • Π -Π F . □ Proposition B.17. Let v 1 , . . . , v k ∈ S d with max i,j |⟨v i , v j ⟩| ≤ α ≤ 1 20 .Let u 1 , . . . , u k be the result of the Gram-Schmidt process applied on v 1 , . . . , v k . Then for every i ∈ [k], there existsλ i-1 ∈ R with |λ i-1 | ≤ α(1 + 4α) and w i ∈ R d with ∥w i ∥ 2 ≤ 2α 2 such that u i = v i + λ i-1 v i-1 + w i .Proof. We prove it by induction on i. The case i = 1 holds since u 1 = v 1 . Assume it holds for i, and we prove it for i + 1. Defineλ i = -⟨u i , v i+1 ⟩ and w i+1 = λ i (λ i-1 v i-1 + w i ). Note that |λ i | = |⟨v i + λ i-1 v i-1 + w, v i+1 ⟩| = |⟨v i , v i+1 ⟩ + λ i-1 ⟨v i-1 , v i+1 ⟩ + ⟨w, v i+1 ⟩| ≤ α + |λ i-1 |α + ∥w∥ 2 ≤ α + α 2 (1 + 4α) + 2α 2 ≤ α(1 + 4α),and that ∥w∥ 2 ≤ α 2 (1 + 4α) 2 + 2α 3 ≤ 2α 2 (recall that α ≤ 1 20 ). The proof now follows sinceu i+1 = v i+1 -⟨u i , v i+1 ⟩u i = v i+1 + λ i (v i + λ i-1 v i-1 + w i ) = v i+1 + λ i v i + w i+1 . □ B. 
algorithms: 
 Let M be a randomized algorithm that uses m random coins. For r ∈ {0, 1} m we denote by M r the (deterministic) algorithm M after fixing its random coins to r. Given an oracle-aided algorithm A and algorithm B, we denote by A B the algorithm A with oracle access to B.Definition B.18 (Differential privacy [Dwork et al., 2006b,a] ). A randomized mechanism M : X n → Y is (ε, δ)-differentially private (in short, (ε, δ)-DP) if for every neighboring databases X = (x 1 , . . . , x n ), X ′ = (x ′ 1 , . . . , x ′ n ) ∈ X n (i.e., differ by exactly one entry), and every set of outputs T ⊆ Y, it holds thatPr[M(X) ∈ T ] ≤ e ε • Pr[M(X ′ ) ∈ T ] + δ B.8.1 Basic Facts Fact B.19 (Post-Processing). If M : X n → Y is (ε, δ)-DP then for every randomized F : Y → Z, the mechanism F • M : X n → Z is (ε, δ)-DP.Post-processing holds when applying the function on the output of the DP mechanism. In this work we sometimes need to apply the mechanism on the output of a function. While this process does not preserve DP in general, it does so assuming the function is neighboring-preserving. Definition B.20 (Neighboring-Preserving Algorithm). We say that a randomized algorithm G :X n → Y m is neighboring-preserving if for every neighboring X, X ′ ∈ X n , the outputs G(X), G(X ′ ) ∈ Y m are neighboring w.p. 1. Fact B.21. If G : X n → Y m is neighboring-preserving and M : Y m → Z is (ε, δ)-DP, then M • G : X n → Z is (ε, δ)-DP.Our empirical evaluation (Section 4) is performed in the zCDP model of Bun and Steinke [2016] , defined below. Definition B.22 (Rényi Divergence (Rényi [1961] )). Let y and y ′ be random variables over Y. For α ∈ (1, ∞), the Rényi divergence of order α between y and y ′ is defined byD α (y||y ′ ) = 1 α -1 • ln E y←y P (y) P ′ (y) α-1, where P (•) and P ′ (•) are the probability mass/density functions of y and y ′ , respectively. Definition B.23 (zCDP Indistinguishability). We say that two random variable y, y ′ over a domain Y are ρ-indistinguishable (denote by y ≈ ρ y ′ ), iff for every α ∈ (1, ∞) it holds thatD α (y||y ′ ), D α (y ′ ||y) ≤ ρα.We say that y, y ′ are (ρ, δ)-indistinguishable (denote by y ≈ ρ,δ y ′ ), iff there exist events E, Bun and Steinke [2016] ). A mechanism M is δ-approximate ρ-zCDP (in short, (ρ, δ)-zCDP), if for any neighboring databases X, X ′ it holds that M(X) ≈ ρ,δ M(X ′ ).E ′ ⊆ X with Pr[y ∈ E], Pr[y ′ ∈ E ′ ] ≥ 1 -δ such that y| E ≈ ρ y| E ′ . Definition B.24 ((ρ, δ)-zCDPThe Gaussian Mechanism Fact B.25 (The Gaussian Mechanism Dwork et al. [2006a] , Bun and Steinke [2016] ). Let x, x ′ ∈ R d be vectors with ∥x -x ′ ∥ 2 ≤ λ. For ρ > 0, σ = λ √ 2ρ and Z ∼ N (0, σ 2 • I d×d ) it holds that x + Z ≈ ρ x ′ + Z.We use the following DP averaging algorithm that given the diameter ξ of a ball that contain most of the points, it can estimate their average. Fact B.26 (Tsfadia et al. [2022] ). Let λ ≥ 1 and δ ≤ ε, β ≤ 1. There exists an (ε, δ)-DP algorithm FC_Average that gets as input a dataset S = (x 1 , . . . , x n ) ∈ (R d ) n and a parameter ξ > 0 and satisfies the following utility guarantee:If n ≥ O log(1/δ) ε + √ d log(1/δ) log(1/β) λε and ∃S ′ ⊆ S with |S ′ | ≥ 0.8n s.t. ∀x i , x j ∈ S ′ : ∥x i -x j ∥ 2 ≤ ξ, then Pr y∼FC_Average(S,ξ) [∥y -µ∥ > λξ] ≤ β, where µ = 1 |S ′ | x∈S ′ x.Furthermore, the running time of FC_Average(S, •) is Õ(dn log(n/δ)) (See Appendix B in Tsfadia et al. [2022] ).Fact B.26 is not explicitly stated in Tsfadia et al. [2022] since they only analyzed the utility guarantee of their averaging in the zCDP model. Yet, it can be achieved using similar steps. First, we need to consider a "friendly" DP variant of their FriendlyAvg algorithm (Algorithm 3.3 in Tsfadia et al. [2022] ), and as Tsfadia et al. [2022] noted, we can do it such that the probability of failure is low whenever n ≥ O log(1/δ) ε , and the additive error (given success) decreases in a rate ofξ √ d log(1/δ) log(1/β) nε, where ξ is the diameter of the points. Fact B.26 immediately obtained by combining FriendlyAvg with their paradigm for DP (Theorem 4.11 in Tsfadia et al. [2022] applied with α = 0.2). Dwork et al. [2014] We next describe the subspace recovery algorithm of Dwork et al. [2014] that strongly takes advantage of a large additive gap σ 2 k -σ 2 k+1 for decreasing the noise that is required for privacy. This algorithm is only used in our empirical evaluation (Section 4). Note that when the additive gap σ 2 k -σ 2 k+1 is large, the algorithm will add smaller noise per coordinate in Step 3. Fact B.28 (Theorem 11 in Dwork et al. [2014] ). Algorithm B.27 is (2ε, 2δ)-DP.The privacy analysis is done by the following steps. First, by the Laplace mechanism, Step 2 is ε-DP. Second, by tail bound on the Laplace distribution, the probability that g-2 log(1/δ)/ε ≤ σ 2 k -σ 2 k+1is at least 1 -δ. Furthermore, they show that if σ 2 k -σ 2 k+1 ≥ α then the Forbenius-norm sensitivity of the matrix Π is at most 2 α-2 . So conditioned on the above 1 -δ probability event, the Forbenius-norm sensitivity of Π is at most 2 g-2 log(1/δ)/ε-2 , and therefore the Gaussian mechanism step (Item 3) guarantees (ε, δ)-DP, and by composition the entire process is (2ε, 2δ)-DP.In order to consider a zCDP version of Algorithm B.27, we replace the Laplace noise Lap(2/ε) with a Gaussian noise N (0, σ 2 ) for σ = 2/ρ. Given this change, now it holds that g -σ 2 ln(1/δ) ≤ σ 2 k -σ 2 k+1 w.p. at least 1 -δ (by tail bound on Gaussian distribution). Finally, in Step 3 we replace ∆ ε,δ (the required standard deviation for (ε, δ)-DP) to 1/ √ 2ρ (what is required for ρ-zCDP). This results with the following (2ρ, δ)-zCDP algorithm: Peter et al. [2024] showed that for d = Θ(n 2 ), the distribution D(n, d) below induces a fingerprinting codebook for n users, each codeword is of length d. Definition B.30 (FPC hard distribution D(n, d) Peter et al. [2024] ). Let ρ be the distribution that outputs p = (e t -1)/(e t + 1) ∈ [-1, 1] for t ← [-ln(5n), ln(5n)]. For n, d ∈ N, let D(n, d) be the distribution that chooses independently p 1 , . . . , p d ∼ ρ, and outputs a codebook(x 1 , . . . , x n ) ∈ ({-1, 1} d ) n where for each i ∈ [n] and j ∈ [d], x j i is drawn independently over {-1, 1} with expectation p j .Framework for Lower Bounds Consider a mechanism M : X n → W that satisfies some weak accuracy guarantee. Peter et al. [2024] showed that the task of proving a lower bound on n is reduced to the following task: Transform an FPC codebook X ∈ {-1, 1} n0×d0 into hard instances Y ∈ X n for M, and then extract from the output w ∈ W of M(Y ) a vector q ∈ {-1, 1} d0 that is strongly-correlated with X (n 0 and d 0 are some functions of n and d and the weak accuracy guarantee of M), where Definition B.31 (Strongly Correlated). We say that a random variable q = (q 1 , . . . ,q d ) ∈ {-1, 1} d is strongly-correlated with a matrix X ∈ {-1, 1} n×d , if ∀b ∈ {-1, 1}, ∀j ∈ J b X : Pr q j = b ≥ 0.9 (recall that J b X = {j ∈ [d] : x j i = b for all i ∈ [n]}).Denote by G : {-1, 1} n0×d0 × Z → X n the algorithm that generates the hard instances using a uniformly random secret z ← Z (i.e., z could be a random permutation, a sequence of random permutations, etc). Denote by F : Z × W → {-1, 1} d0 the algorithm that extracts a good q using the secret z and the output w. We denote by A M,F,G (X) the entire process:EQUATIONF : Z × W → [-1, 1] d0 , each uses m random coins. Define A M,F,G : {-1, 1} n0×d0 → [-1, 1] d0as the randomized algorithm that on inputs X ∈ {-1, 1} n0×d0 , samples z ← Z, Y ∼ G(X, z) and w ∼ M(Y ), and outputs q ∼ F(z, w).Definition B.33 (β-Leaking). Let M, F, G be randomized algorithms as in Definition B.32, each uses m random coins, and let D(n 0 , d 0 ) be the distribution from Definition B.30. We say that the triplet(M, F, G) is β-leaking if Pr r,r ′ ,r ′′ ←{0,1} m , X←D(n0,d0) A Mr,F r ′ ,G r ′′ (X) is strongly-correlated with X ≥ β,where recall that M r denotes the algorithm M when fixing its random coins to r (F r ′ , G r ′′ are similarly defined).subset of the rows of X (without replacement). Let Π and Π ′ be the projection matrices to the top-k rows subspace of X and X ′ , respectively. Then the following holds for γ 1 = σ k+1 σ k andγ 2 = min{n,d} i=k+1 σ 2 i σ k : 1. If m ≥ max{800k ln k 4β , 2γ 1 n}, then Pr ∥Π -Π ′ ∥ ≤ 4 2n m • γ 1 ≥ 1 -β/2. 2. If m ≥ 800k ln k 4β and β ≥ 4γ 2 2 , then Pr ∥Π -Π ′ ∥ F ≤ 4 2 β • γ 2 ≥ 1 -β.Proof. We will prove each part of the lemma by applying Proposition B.12. In the following, let X = n i=1 σ i u i v T i be the SVD of X, and note that we can write X ′ = (x i1 , . . . , x im ) where {i 1 , . . . ,i m } is a random subset of [n] (without replacement). Let Y = (y 1 , . . . , y n ) = k i=1 σ i u i v T i and let Z = (z 1 , . . . , z n ) = min{n,d} i=k+1 σ i u i v Ti , and note that Span{y 1 , . . . , y n } = Span{v 1 , . . . , v k } is orthogonal to Span{z 1 , . . . , z n } = Span{v k+1 , . . . , v min{n,d} }. Furthermore, define the random matrices Y ′ = (y i1 , . . . , y im ) and Z ′ = (z i1 , . . . , z im ) and note thatX ′ = Y ′ + Z ′ .First, by Proposition B.4 (applied on v 1 , . . . , v k ) and the assumptions on m, σ k , it holds by the union bound thatEQUATIONIn the following we assume that the event in Equation ( 1) occurs. We first prove Item 1. Note that∥Z ′ ∥ ≤ ∥Z∥ ≤ σ k+1 ≤ γ 1 σ k and that σ k (Y ′ ) 2 ≥ m 2n σ 2 k ≥ 2γ 2 1 σ 2 k ≥ 2∥Z ′ ∥ 2 (the second inequality holds since m ≥ 4γ 2 1 n). By applying Proposition B.12(1) on X ′ , Y ′ , Z ′ we conclude that ∥Π -Π ′ ∥ ≤ 4 • ∥Z ′ ∥ σ k (Y ′ ) ≤ 4 2n m • γ 1 .We next focus on proving Item 2. Note that ∥Z∥2 F = min{n,d} i=k+1 σ 2 i = γ 2 2 σ 2 k , and that E ∥Z ′ ∥ 2 F = m n ∥Z∥ 2 F = m n • γ 2 2 σ 2 k .Therefore by Markov's inequalityEQUATIONIn the following we assume that the event in Equation ( 2) occurs. Note thatσ k (Y ′ ) 2 ≥ m 2n σ 2 k ≥ 2m βn γ 2 2 σ 2 k ≥ 2∥Z ′ ∥ 2 (the second inequality holds since β ≥ 4γ 2 2 ). By applying Proposition B.12(2) on X ′ , Y ′ , Z ′ we conclude that ∥Π -Π ′ ∥ ≤ 2 √ 2 • ∥Z ′ ∥ F σ k (Y ′ ) ≤ 2 √ 2 • 2m βn γ 2 σ k m 2n σ k ≤ 4 2 β • γ 2 . □ C. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We mentioned in Section 4 that we use the Python implementation of Tsfadia et al. [2022] that is publicly available in https://media.icml.cc/Conferences/ ICML2022/supplementary/tsfadia22a-supp.zip and we cite them as required.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.Similarly to the DP averaging example, we consider algorithms which guarantee accuracy that is proportional to the "easiness" parameter γ, and we measure the "quality" of the estimations by the parameter λ.If we take λ = α/γ (i.e., aiming for an error α), the utility restriction on γmax in Theorem 1.7 implies that γ should be smaller than Θ α 2/3 k 2/3 d 1/3 .The spectral norm of a matrix A ∈ R n×d is defined by ∥A∥ = sup x∈S d ∥Ax∥ 2 and is equal to σ1(A).The Frobenius norm of a matrix A ∈ R n×d is equal to σ1(A) 2 + . . . + σ min{n,d} (A) 2 .To illustrate why σ1, . . . , σ k should be large, consider a matrix X whose first n -k + 1 rows are e1, and the next k -1 rows are e2, . . . , e k . This matrix has σ2 = . . . = σ k = 1, and even though it is a rank-k matrix, it is clearly impossible to output a projection matrix that reveals any of the directions e2, . . . , e k under DP.Their source code is publicly available in https://media.icml.cc/Conferences/ICML2022/ supplementary/tsfadia22a-supp.zip.We do not explicitly compute a d × d rank-k projection matrix in each subset, but rather only compute a good approximation of the top-k rows V = (v1, . . . , v k ) ∈ S k d using the Python function randomized_svd (provided in the sklearn library). We then compute the projection of any vector u ∈ R d onto Span{v1, . . . , v k }, given by V T V u, from right to left, which only involves O(kd) time and space computation cost. We do the same thing w.r.t. to the output projection Π (i.e., represent it using only k vectors).We remark that unlike EstSubspace,Dwork et al. [2014]'s algorithm requires O(d 2 ) time and space complexity as it requires an explicit access to the d × d projection matrix onto the top-k rows subspace, and therefore is limited to moderate values of d. Still, we were able to use it as baseline since we saw the advantage of our approach in terms of accuracy even when d is not extremely high.≥ η|I|. 
 
 Appendix:  


Decision: This paper studies the problem of differentially private subspace estimation. By assuming the multiplicative decay singular values, the author provide through studies of this problem.

All the reviewers agree that the paper provides interesting results and makes significant contributions to the field. In light of this, I recommend the paper for acceptance.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: Do the authors perceive a way to improve their upper bound to get better dependence on $k$?
limitations: limitations: The quadratic and cubic dependence on $k$.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Yes, the authors have addressed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: I don't see any significant limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: There are some gaps between their upper bounds and lower bounds.
questions: questions: 1. Can your approaches work on real-world datasets?
2. Can you further improve the gap between upper bounds and lower bounds?
limitations: limitations: There are some gaps between their upper bounds and lower bounds.

Comments: comment: Thank you for answering my questions regarding parameter choices and for committing to improve some presentation issues. I will keep my score.
Thanks for your clarification. It's very helpful for my understanding, and I increase my score accordingly.