On Differentially Private Subspace Estimation in a Distribution-Free Setting
Authors: Eliad Tsfadia
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Private Subspace Estimation
Private PCA
Fingerprinting Codes
Primary area: privacy

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.

On Differentially Private Subspace Estimation in a Distribution-Free Setting
Eliad Tsfadia
Department of Computer Science
Georgetown University el eliadtsfadia@ggaall com
Abstract
Private data analysis faces significant challenge known the curse of dimen- sionality, leading to increased costs. However, many datasets possess an inherent low-dimensional structure. For instance, during optimization via gradient de- scent, the gradients frequently reside near a low-dimensional subspace. the low-dimensional structure could be privately identified using small amount of points, we could avoid paying for the high ambient dimension.
On the negative bwork et al. (2014) proved that privately estimating subspaces, in general, requires an amount of points that has 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 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 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 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.
Introduction
Differentially private (DP) Dwork al. (2006b) algorithms typically exhibit 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 al. (0014), Steinke and Ullman [2017), Dwork et al. (2033) showed that any method that achieves lower error rates is vulnerable 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 "casy" instances.
Example: DP averaging. As simple prototypical example, consider the task of DP averaging. In this task, the input dataset consists d-dimensional points T1, Tx E Rdd, and the goal is to estimate their average Σ I, using DP algorithm while minimizing the &g additive error. One natural way to capture input "casiness" for this task via the maximal & distance between any two points (i.c.. points that closer to each other Peter et al. (0244) showed that the points are y-close to each other, and we aim for an accuracy of Xry (i.e., accuracy that is proportional to the "easiness" parameter 7), then it is sufficient and
considered "casier"). Indeed, Tsfadia et al. 2022).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

necessary to use = ((vd/A) points. Equivalently, if we aim for an accuracy of a, then by applying these results with À az/n, we obtain that the answer is n @(rvd/a). This, in particular, implies that when 7 - a/ V (i.e., the points very close to each other), then O(1) points are sufficient, but for y a/ (2d/22211)) 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 dataset X (CII,..,,In) (Rd)) of unit norm points and parameter estimate the top-k subspace of Span(xi,..... Tnn.. 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 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 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 polynomial dependency on is unavoidable.
1.1 Motivation: DP-SGD
To motivate the problem, consider the task of privately training large neural networks. The most commonly used tool to perform such a private training the sifferentially-privatt stochastic gradient descent (DP-SGD) (DP-SGD)[Abadi [Abadi et al.] (2016b), Bassily et al. [2014), [onng et al. [2013] 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 nww-dimensional subspace caappacee/badiii Abadi et al.
[2016a] Li et al.
[b1 Gur-Grrrrr Ari al. (2118] Li al. [2018]] Demeniioni and Chawla [2020].
Zhou et al. [021 Feng and Tu [2020). Li et al. 2022]. Golatkar et al. 20222. Kairouz et al. 2020
In particular, Gur-Ari al. [2018] showed that in
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 fow-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.
1.2 Subspace Estimation
That is, the input dataset consists of n points of 1) and parameter k, and the goal is output k-dimensional projection matrix II such that II x is "close" to X as possible, where X denotes the n x d matrix whose rows are #1.... Tn. We measure the accuracy of our estimation using the "usefulness" definition of Dwork al. (0144:
We consider the setting of Dwork et al.
2014
unit norm . Fn Sa = (v R"
Definition 1.2 (a-useful). We say that rank-k projection matrix II is a-useful for matrix X (Sa)a if for any k-rank projection matrix II':
x
2 IT'
XTI - a n.
where || denotes the Frobenius norm!
Observe that any projection matrix is 1-useful for any X (because |X = -E 1= n2). Therefore, we will be interested in smaller values of (e.g., 0.001).
1.3 Prior Works
Without privacy restrictions, we can find 0-useful (i.e., optimal) solution using Singular- Value Decomposition (SVD). The SVD of X X UEVT, where U E Roxa and V E Rdxd are unitary
'The Frobenius norm of matrix A =aa{) (af)xew)lseja is defined by ||A|| V Eietnooe (a!)²

---

matrices, and Σ is an x d diagonal matrix which has values T1 2 ...2 2..2 o minn( 2 0 along the diagonal. The top-k rows subspace of X is given by the span of the first & columns of V, and can be computed, e.g., by applying Principal Component Analysis (PCA) on the covariance matrix A X 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 2 (((v2)) for computing a 0.001-useful k-rank projection matrix under (1, ((DD This bound, however, only holds for algorithms that provide accuracy for worst- case 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 k-dimensional subspace (i.e.. "easy" instances).
Perhaps the easiest instances are those that exactly lie in a k-dimensional subspace, and are well- spread within it (i.e., there is no (k: (k=11 didmennsio subspace that contains many points). Indeed, Singhal and Steinke [2021] and Ashtiani and Liaw| [022] developed (c, 5)-DP algorithms for such instances that precisely recover the subspace using only = e.. (k:) points. However, while these algorithms are robust to changing few points, they are very brittle if we change all the points by a little bit.
One approach to smoothly quantify how much dataset is "casy" is to consider the additive-gap gap of --1- Indeed, Dwork et al. (2014), /oonem and
(2018) present 6D
algorithms that output 0.001-useful projection using n = O..6
kvd
points. 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 k-dimensional subspace and well-spread within it, the additive gap o 2e 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 [202T] (their "approximate" case). Rather than quantifying easiness as function of the input dataset, they consider setting where the points
sampled i..dd from some distribution,
and implicitly measure how "easy" a distribution is according to some stability notion. In particular,
(++1(E) < 0 they show that d-dimensional Gaussian NO, Σ) with multiplicative gap (x.
is "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-valle value gaps in the input dataset as a measure for easiness.
1.4 Defining Subspace Estimators
Towards answering Question I.I, we consider mechanisms M that are parameterized by k, X, and B, and satisfy the following utility guarantee: Given a dataset X (#1,.... 2n) E (Sa)" and value ? as inputs, such that X is "ry-easy" for k-subspace estimation, then with probability at least B over random execution of M(X, 7), the output 1I is an Xr-uueful rank-k projection matrix for X In 1.3] the "*yeasy" property is abstracted by a predicate f. We also allow an additional parameter Ymux to relax the utility for non-easy instances (i.e., would not require utility guarantee for instances that are not "Ymux-easy"". Furthermore, we only focus on cases in which X has at least & significant directions, which is formalized by requiring that (X) 2 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 o using an additional parameter or different assumptions).
Definition
Definition 1.3 ((k, X, B, "maxx f)- -ubbspae Estimator). Let n,k, d E N s.t. k S min d}. let B E (0. 1), and let f: (Sa)" x [0, 1] + (0. }} be predicate. We say that M: (S.)" x [0. - Rdxd an (k, 3, Tmaxx f) Jusubsppcee estimator, if for every X E (Sa)" and y S Tmax with of xx) z
0.01 n/k and f(X,7) = 1, it holds that
Prn-M(x;>) [I is (Ar)-usefiul for X| 2 B.
1.5 Quantifying Easiness - Our Approach
In this work, we develop two types of smooth measures (captured by the predicate f in Definition L.3 for input "easiness", which are translated to the following two types of subspace estimators:
Similarly to the DP averaging example, we consider algorithms which guarantee accuracy that is proportional to the "easiness" parameter 7, and measure the "quality" of the estimations by the parameter A.
3

---

fxd is called an (k,, X. B. (mmax) -Weak Subspace Estimator, if is (ki X, 8, Tmax: f) -Subspace Estimator for the predicate f(X,7) that ouiputs iff Ei=k+1 (x) S 2-0 7 (X).
Definition 1.4 ((k,), X, 3, Tmmax) -eeak Subspace Estimator). M: (Sa)" x [0.1] + Rd
Definition 1.5 ((k, X, 3, Yuma)) "Stoo)St Subspace Estimator). M: (Sa)" x [0, 1] + Rddd is called an (k, A, B, Ymmxx) )-Srong Subspace Estimator, if it is 1,, Vmmxx f)Subspace Estimator for the predicate f(X,7) that outputs iff 0x+1(X) S (X).
In both cases, we define f based on multiplicatiie singular- value gaps in the input dataset, but the difference is what type of gap the value y bounds: Strong estimators depend solely on the gap 0k+1/ok without taking into account smaller singular values. Weak estimators, on the other, depend
on the gap V min((,,) of /ok- 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 closer to k-dimensional subspace.
We provide new upper and lower bounds for both types of estimators.
1.5.1 Our Upper Bounds
Theorem 1.6 (Weak estimator). There exists an (ks X, = 0.9, Tmax Ommin 3t. (..1)))weakk
subspace estimator M: (Sa)" x [0, + Raxd with n = Õz.6 (k: (k+ min (a2,)aa, ya, ()-P) for every y E [0,1].
kdl ( such that M(-,7) 7)
A
X, 3 0.8, Imax =m(minf3, 3 X² (ad))) subspace estimator M: (Sa)a x [0,1] + Rdxd with n = δ..8 +
Theorem 1.7 (Strong estimator). There exists an (k,
k&d
such that M(: is x
(E, (E every [0, 1].
Both of our estimators provide useful projection by outputting matrix that is close (in Frobenius norm) to the projection matrix of the top-k rows subspace. Their running time 2 T(m, d, k) Ö(dnn) for some (non-pun (non-privane poiv-aiaattll) a projection matrix to the top-k rows subspace of an m matrix. We refer to Section 2 for detailed overview.
Ō(k), where T(m, d, k) denotes the running time required to compute
For simplifying the presentation and the formal utility guarantees, we assume that our algorithms know the values of (the bound on the multiplicative-aan and of k beforehand. Yet, we show that both assumptions are not inherent, and we refer Remark 2.4 additional details.
We also remark that in both theorems, it is possible to increase the confidence 3 to any constant smaller than 1 without changing the asymptotic cost.
1.5.2 Our Lower Bounds
Theorem 1.8 (Lower bound for weak estimators). M: (Sa)" x 0, + Rdxd is a (k, A, =
0.1, Tmax = 0 =)+))-weal -wekk subspace estimator for 1 < X S O Flog
and M(:,)) is (1, sonk -DP
for every y [0, 1), then n 2 Ω
Add
Theorem 1.9 (Lower bound for strong estimators). If M: (Sa)" [0. + Rdxd is a (k, X, B
0.1, Tmax + ( ) subspace estimator for 1 < X < O log and M(: is (1, 50nk -DP
for every 7, then n 2 á lvva)
Our lower bounds are more technically involved, and use a novel combination of generating hard- instances 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 Dwork et al.
[2014). Both lower bounds are proven by generating hard-ine iardd-intances that are "y-easy" for 1000A
We refer Section 3 for detailed overview.
We remark that Peter et al. 2024 recently proved a similar lower bound for the special case of k = (estimating the top-singular vector). However, their result strongly relies on the similarity between

---

Weak Estimator
Strong Estimator
Upper Bound
Og.5 h
Og, k
K'd X
Lower Bound
Ω Vild
Ω
Avd
Table 1: Our bounds on n for subspace estimation (ignoring restrictions on Ymax and X).
Weak Estimator
Strong Estimator
Upper Bound
Ōz,8 k2k2v
Oz,8 (k + 72 kkdd)
Lower Bound
Ω 71 11vkd
52 722vV
Table 2: Our bounds on n for computing 0.001-useful projection, where V/1 - Ei=k+1 / and 72 02+1/Ox denote here the "easiness" parameters for weak and strong estimators, re- spectively. As mentioned in Footnote 3 our upper bound for strong estimators only hold for 72 I O 11/3-22/d--1// 1/33.
Eminfa,d)
averaging and estimating top-singular vector in their hard instances, which does hold for the case Table summarizes our bounds for ls S vd.
1.5.3 Implications
We offer two formulations which have the property we seek: If we aim for an eroor and the dataset "7-easy" for very small 7, we take À a/7 to reduce the number of necessary and sufficient points.
For strong estimators, the rate = =n( A) in Theorem 1.7 does not match the corresponding lower bound Theorem 1.9 and Theorem 1.7 limited to small values of 7f Yet, for small values of k, the -us0fulllf rank-k projection with number of points that is independent of d, it is sufficient and necessary to have gap c o of at most 1/vā. Table summarizes our bounds for the special case of outputing 0.001-useful projection matrix, using our two different types of input "easiness".
strong-estimator bounds do imply that in order privately compute
1.6 Empirical Evaluation
We believe that private subspace estimation of easy instances could find practical applications. Therefore, we made an effort realize our upper bounds using a practical algorithm. In Section we empirically compared our method to the additive-gap based approach of Dwork et al. (0114) 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.
1.7 Paper Organization
In Sections 3 we present proof overviews for our results, and the empirical evaluation is provided in Section A limitations section is given in Section Additional related work appears 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
2 Upper Bounds Overview
Both of our estimators (Theorems 1.6 and follow the same structure, but with different parameters. Similarly to Singhal and Steinke 2021 algorithms follow the sample-and-agee agggegate approach of Nissim et al. 2007]. That is, given a dataset
( E (Sa)", " we partition the rows
into i subsets, compute (non- privateia) projection matrix the top-k rows subspace of each subset,
'If we take a/y (i.e., aiming for an error a),, the utility restriction on Tmax Theorem implies that should be smaller than @ 2/3
62/9.173
5

---

and then privately aggregate the projection matrices II,,..... ........IIII II. For doing that, we need to argue that I...... II, are expected to be close each other. In the Gaussian setting of [innhal and Steinke (202T] 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/ rows are 61 = (1,0..... 0), the next n/ / rows are e2 = (0, 1, 0), and so forth until eg. Even though X is rank-k and has of = 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 good representation of the top-k rows subspace of X in each subset.
of = n n/k, if we simply partition
There is an extensive line of works who aim for methods to choose a small subset of rows that provides a good oowapppoximation for the original matrix (e.g., see Mahoney (201T) 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 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 = (21,..., Lnd ) E (Sa)" with singular values 01 .... min (n,)) 2 0, and
n? Let X' E (Sa)a be a uniformly random m-size subset of oe X (withoul replacement). Let IT and IT' be the projection matrices to the top-k rows
(n.d)
let 711 = Jht1 and 722 = ok the rows of subspace of X and X', respectively. Assuming that of 2 0.01n/k, then the following holds for m (le)::
1. 1f S 2n then Pr [r[ II'| 1 (V(V m
m)] 2 0.9. (|-|] denotes the Spectral norm 4
2. 1/ S 0.1, then Pr[ II'Il S (12)) 2 0.9. S
Namely, Item | bounds the expected spectral norm distance of the projection matrices using the first type gap 0k+1/ox ox (which is used in the analysis of our strong estimator), and Item 2 bounds the
expected Frobenius norm distance using the second type gap the analysis of our weak estimator). We prove Lemma 2.1 in Appendix C.1.2
Li=k-1 Emiu(ndd of /oy (which is used in
The next step is aggregate the non-private projection matrices II .1.... II into private one II. We consider two types of aggregations. The first one simply treats each matrix as a d2 vector and privately estimate the average of IT, II,.... IT.- The second type (which outperforms the first one in most cases) follows a similar high-level structure of Singhal and Steinke (202T). That is, to sample i..d. reference points Pl..... Pl.....Py Py ~ (ū, for g = (k)), privately average the gd-dimensional points [(T,p),.... II p) ) for obtaining private P RRaxd (whose 7th row estimates the projection of p; 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 [202]] 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 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, Friendly 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 II,.... II directly) outperforms the second type only for our weak estimator in the regime k 2 Vd (as it inherently posses larger dependency in the dimension).
Remark 2.3. We could avoid the requirement of 2 0.01n/k by adding an additional parameter n such that of 2 17 n/ki and using subsets of size m. @(k/n) (which would increase by the same factor of 1/n). 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
"The spectral norm of matrix A E Raxd is defined by ||A|| = sup , Axrl/ and is equal to 0 d1(A).
'The Frobenius norm of matrix A gaxd is equal to voi(A) + .... Omin (A)².
6

---

requirement is unavoidable we would like to provide utility guarantees only as a function of the singular values 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-Ty assumption, we can replace the SeeedtyCore-averagien step Tsfadia et al.) (2022) (that requires to know the diameter) with their unknown diameter variant that gets two very rough bounds Emin and Emax. and performs a private binary search for estimating good diameter E [gmin: [mass] in a preprocessing phase. This step only replaces the dependency on d with d + log log(Smax/ (ossmmx//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 (com- pared to the additive- daaitive-gap gap based ones) only when kk+1 < 1. So in cases where of 2 2- 2log((k/ /B)/ for some (fixed) privacy budget e' < E (say, e' = e/10), we can privately determine w.p.
the right value of k using a simple e'PD method. The main observation is that the & semsitivity of the vector (oi....,0 (.) is most 2 (Amin et al. (2019)) yielding that we can privately compute
(of² .......0 ,,,)) ==)== + + Lap(2/E")) "aa LLap(2/) and then perform analysis on (o] ,...,,"?' "
to set l as the first index where of 2 log(i/3)/e and o. < log(t//)/e*.
3 Lower Bounds - Overrvew
Our 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 & 2 2.
Roughly speaking, let D be a distribution over { 1, 1i "dg
xdo that induces an optimal FPC codebook
with do (m²) (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²) (e()) ~ 'D as input, cannot output a vector q = (g', .e......4 E 1- that "agrees" with most of the "marked" columns of X (Formally, for b E {-1, 1). columns x² = (af..... an) is called b-marked if m] = _...
... = . = b, and q agrees with it if q² = b).
Now consider a DP mechanism M: X - 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 E (-1, 1 1 hard instances Y E X for M. and (2) Extract from the output w ~ M(Y) a vector o E {[1,1 that agrees with most of the marked columns of X (ng and do are some functions of n. X' and the weak accuracy guarantee of M). Peter et al. (0024) proved that 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 nrighboring-preserviie (i.e., maps neighboring databases to neighboring databases), then it must hold that no 2 (((Vdo) (Otherwise, M cannot be DP).
Warm-up: DP averaging. We first sketch how Peter et al. [2024] applied their framework with no = n and do = Odd/x²) for proving lower bound for the simpler problem of DP averaging. In this setting, we are given a mechanism that guarantees Xy-accuracy (&2 additive error) for 7-easy instances (i.e., points that are 7-close to each other in E norm). The generator G. given an FPC codebook X E 1] xdo, uses the padding madding-and-ae -nd--aade permuting technique: It pads é = 10 1-marked columns and (-1)-markce columns, and then permutes all the d = dg + 28 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 TOOX 1 -close to each other in &
1 aaccurate solution w. In particular, after rounding w to norm, so the mechanism has to output an 100
{)1, 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), ...),,.,. I (do) as it cannot distinguish between them and the other marked columns (because N is hidden from it). The extractor F, given w and म. rounds w to 1_ and outputs g = (1) ...., (d) which agrees with most of the marked columns of X. Hence, we obtain the lower bound of n 2 5(V = ((Vd/A).
TTo illustrate why di...., dx should be large, consider a matrix X whose first n - k + 1 rows are es, and the next & - 1 rows are ..,..., en. This matrix has d2 = da 1, and even though it is a rank matrix, it is clearly impossible output a projection matrix that reveals any of the directions e2. .... es under DP.
7

---

B1
do
vd
PAP
vd
B3
Ba
Vd
Figure 1: From Left to Right: (1) The normalized rows of the fingerprinting codebook X well-spread on the do do-dimensional unit sphere. (2) Applying the padding-and andd-ntttn-- (PAP) technique makes the normalized points very close to each other the d-dimensional unit sphere (d >> do). (3) We create hard instances for DP subspace estimation using k-independent (normalized) PAP-FPC codebooks ......, BR, where PAP(X) is planted in one of the B; 's (in this example, in B2). Reducing a (i.e., increasing the padding length) makes the points in each group B, closer to each other, which in particular, increases the closeness k-dimensional subspace.
DP Subspace Estimation In our case, we are given (weak strong) subspace estimator M: (Sa)" + Rdxd that outputs an Xy--useful rank-k projection matrix if xx+1(X) - 7ork
(or v Li=k+1 (x)2 S (xx(X)). We prove our lower bounds by applying the framework with no n/k and dg = ((ad), for some parameter a a()) that will depend on the type of M we consider. In order to generate hard instances Y E (Su)" for M given an FPC codebook X ~ D (X e (-.
we use a variation of the approach to Dwork et al. [2014). Namely, our DD where plants A, X for random < [k] Then for each j E [k], it applies (independently) the padding-and and--addde-ea permuting technique of Peter et (2024) where it pads 1-marked columns and (-1k-marked columns for the columns. This induces matrices B,...., , Bg E (-1,1) (n/k)xd (for = dg + 26) such that each By is "almost" rank-1 and their vertical concatenation B E (-1,1) is almost rank-k. &.. It provides Y 1 B as the input for M. See Figure for graphical illustrations.
generator G samples & independent FPC codebooks AI...., A
Rd do and permute
2
va
We remark that at this step, the main difference from Dwork et al. 2014 (who implicitly follow a similar paradigm) is that they use fixed padding length of ? 15dg 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 lcc-acyy regimes of many problems, and indeed use the padding length& É to increase the k'th singular value gap, which will be a function of the quality parameter X.
The next step is to choose the right value of a aa)) such that M, input Y, will have to output useful projection matrix. We show that the input matrix Y has w.h.p. a1 (Y)² 2 ... 2 (x)
(1 ((a) +. which yields that Emin(nd)) (Y)) < O(x)). If M is a weak estimator, then we y to guarantee that Li=k+] (Y)) 2² -x (Y)) for Togox which yields that by the utility guarantee of M, we get an 0.001-useful projection matrix. M is a strong estimator, then we use = O(X) x²) (i.e., we decrease the padding length by a factor of k). Yet, in
simply use O
order to meet the requirements of M, we must argue that w.h.p., o (Y)² < Ō(a) 7. and this is more complex than the previous case. Here we use more internal properties of the fingerprinting distribution DD Namely, that in Peter et al. [2024)'s 's construction (which is also true for Tardos 22088's 's one), each entry of the codebook matrix has expectation O and the columns of the matrix are independent. Using known concentration bounds, this allows us to argue that if we pick a unit vector that orthogonal the top-k rows subspace of Y, then with probability at least cxp(-$i(d)) it holds that |Yu| < Ō(a) z. Since of is bounded by the supremum of YYul" under such unit vectors, we conclude the proof of this part using a net argument.
Finally, the last step, which is not trivial for 2 2, is to extract from an 0.001 projection matrix Îî for Y, a vector E 1- that with noticeable probability, strongly agrees with the marked columns of the original codebook E (-1,1) no xoxd, 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 tth invert permutation over the columns of 11 (denote the resulting matrix by 11,), chooses a vector Span(TI,) that has the maximal agreement with half of the padding bits, and then simply outputs its first do coordinates after rounding to {-1,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/a B3- Since all the Y; 's have the same distribution and the location i (where the original X is planted) is hidden from M. then must be 0.001-useful for Y, with probability at least B/k (where 3 denotes the success probability of M). Given that this event occurs, the usefulness of II implies that there must exists a vector in Span(ll,) 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 II, then similar agreement must hold for the marked columns of X.
4 Empirical Evaluation
We implemented a zCDP (Definition B.24 variant of our subspace estimation algorithm in Python (denoted by EstSubspacc), 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 much smaller k-dimensional subspace. Namely, given a dataset X = (Zi,...,, In) ) E S a parameter k. and zCDP parameters p, 6, we perform the following steps: (a) Compute a (p/2, 6)-ZCDP rank-k projection matrix II using EstSubspace that estimates the projection onto the top-k rows subspace of X, (b) Compute a p/2-7CDP estimation of the average of X using the Gaussian Mechanism: T == E T; + (O, o². laaxa) for a nyp
2 and (c) Output a = II T.
The accuracy measured by the lg error from the average: || 1 EE=1111
24
In all our experiments, we use - = and 10-5, tt= = 125 (the number of subsets in the sample- and-aggregate process), n 2tk data points, q = 10 h (the number of reference points in the aggregation), and use the zCDP implementation of the FriendlyCore-
averaging algorithm of Tsfadia et al. [2022] 7 All experiments were tested on MacBook Pro Laptop with 8-core Apple M1 CPU with 16GB RAM.
Rather than using Tsfadia et al. [022]'s 's algorithm for the known-diameter case, we use their unknown-diameter implementation with Emin = 10 6 and Emax 100 (see Remark 2.4 for details). Furthermore, we reduced the space complexity of our implementation from ((d O (kd))
In order to generate a synthetic dataset that approximately lie in a k-dimensional subspace, we initially sample uniformly random bi...., by 1) and perform the following process to generate each data point: (i) Sample a random unit vector u in Span(b,, (b....., ,b J. (ii) Sample a random noise vector v < {1/T, - and (iii) Output a+v (note that higher results with data points that ||++a||
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 = (#1...., In) using the entire privacy budget p (i.c., without computing projection matrix). The second one replaces our Step (a) by computing the projection matrix Il using (p/2, 8) DDDP variant of the additive-gap based algorithm of Dwork et al. [2014) (see Appendix 8..48.4 for more details). 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
Their source code is publicly available in https://media.. icml htt.://aaaaeeeennee////...00./0 httpp//etttattttaaae222222 aalaaa2222sspp2222 supp.zip)
We do not explicitly compute a d x d rank-k projection matrix in cach subset, but rather only compute a good approximation of the top-k rows V = (v)...., uk) E Si using the Python function randomized svd (provided in the sklearn library). We then compute the projection of any vector u E Rd onto Span(21-- 1// ) given by VTVu, u, from right to left, which only involves (ked) time and space computation cost. We do the same thing w.r.t. to the output projection Il (i.e.. represent it using only A vectors).
"We remark that unlike EstSubspace, Dwork al. [2014]'s algorithm requires ((d)) time and space complexity as it requires an explicit access to the d x 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 ad advantage of our approach in terms of accuracy when d is not extremely high.

---

Avsroglig Effect incressing
Aucragi (Effuct
Awcraging (Effect
lambbss)
Grunsion burtir Davck al (2801))
Geass in Machommm
rlack et (21-0)
Dwail 4t (2604))
0.00
0.00
0.05
0.25
0003
0022
0020
612
0.22
0000
4.00
0000
120 200
140
280
200
Figure 2: From Left to Right: (1) The case k = 4 and 10d, varying d (the X-axis is vd). (2) The case d = 10 and r = 10d, varying k. (3) The case d = 10 and 4, varying T (the X-axis is r/d). In all the experiments, we use 250 k data points.
values between the 0.1 and 0.9 quantiles. We show the lg error of our estimate on the Y-xxis. The first graph illustrates the inherent dependency on d that Dwork et al. [2014]'s 's algorithm has, while our algorithm EstSubspace takes advantage of the closeness of the points to dimension k in order to eliminate this dependency. The second graph illustrates that when is fixed, increasing k and n in the same rate a has similar affect on both EstSubspace and Dwork et al. (2014) 's algorithm. In the last graph we compare the accuracy of EstSubspace and Dwork al.] 2014 ss algorithm as a function of the closeness to subspace &o (measured in our experiments by the parameter t), and show in what regimes EstSubspace outperforms Dwork et al. (0114] 's algorithm.
Limitations and Future Directions
From theoretical perspective, work is the first to provide proper measures for how "easy" 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 1.1 between Theorems 1.6 and 1.8 For strong estimators, the upper-bound rate n(A) (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 these gaps (especially the dependency in k) is that our upper bounds follow the approach of [Singhal and Steinke (001) 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, useful solution (Proposition 16). the opposite direction is not true in general, and it could be possible to reduce the sample complexity by focusing on a-usefulness (Definition 1.2) directly, or alternatively, providing stronger lower bounds for estimating the projection matrix.
practical standpoint, 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 now-dimensional subspace (mentioned in Section I.Ip. 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.
From
empirically demonstrate the advantage of our approach in
10

---

Acknowledgments and Disclosure of Funding
Work supported by gift Georgetown University.
The author would like to thank Edith Cohen and Jonathan Ullman for very useful discussions.
References
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS 16, page 308-318, 2016a.
M. Abadi, Chu, Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, CCS '1,, page 308-318, 2016b.
K. Amin, T. Dick, A. Kulesza, A. Munoz, and S. Vassilvitskii. Differentially private covariance estimation. Advances in Neural Information Processing Systems, volume 32, 2019.
R. Arora, V. braverman, and J. Upadhyay. Differentially private robust low-rank approximation. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
H. Ashtiani and C. Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory, volume 178 Proceedings of Machine Learning Research, pages 1075-1076. PMLR, 2022.
R. Bardenet and O.-A. Maillard, Concentration inequalities for sampling without replacement. Bernoulli, 21(3):1361 1385, 2015.
R. Bassily, Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 2014 IEEE 55th Annual Symposium Foundations of Computer Science, FOCS 14, page 464-4744 663,473, USA, 2014.
J. Blocki, A. Blum, A. Datta, and O. Sheffet. The johnson-lindenstrause transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410-419, 2012.
A. Blum, Dwork, McSherry, and Nissim. Practical privacy: The Sul.Q framework. In C. Li, editor, PODS, pages 138-138. ACM, 2005.
M. Bun and Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography 14th International Conference, TCC 2016, volume 9985, pages 635-658, 2016.
M. Bun, J. Ullman, and S. P. Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Symposium on Theory of Computing, STOC 2014, pages 1-10, 2014.
T. T. Cai and A. Zhang. Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. The Annals of Statistics, 46(1):60 89, 2018.
K. Chaudhuri, A. Sarwate, and K. Sinha. Near-optimal differentially private principal components.
In Advances Neural Information Processing Systems, volume 25, 2012.
K. Chaudhuri, A. D. Sarwate, and K. Sinha. A near-optimal algorithm for differentially-privac principal components. Journal of Machine Learning Research, 14, 2013.
C. Demeniconi and N. Chawla. Hessian based analysis of sgd for deep nets: Dynamics and general- ization. In Demeniconi and N. Chawla, editors, Proceedings of the 2020 SIAM International Conference Data Mining (SDM), 2020.
C. Dwork, Kenthapadi, McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, volume 4004, pages 486-503, 2006a.

---

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, volume 3876, pages 265-284, 2006b.
C. Dwork, K. Talwar, A. Thakurta, and L. Zhang. Analyze gauss: Optimal bounds for privacy- preserving principal component analysis. In Proceedings of the 46th Anmual ACM Symposium Theory of Computing, STOC 14. pages 11-20. ACM, 2014. URL http://kunaltaaliat org/ papers/ Prtirss/rivaeee....mm pdf
C. Dwork, A. D. Smith, T. Steinke, J. Ullman, and S. Vadhan. Robust traceability from trace amounts. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 150-669, 2015.
Y. Feng and Y. Tu. How neural networks find generalizable solutions: Self-tuned annealing in deep learning, 2020.
A. Golatkar, A. Achille, Y. Wang. A. Roth, M. Kearns, and S. Soatto. Mixed differential privacy in computer vision. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8366-8376. IEEE Computer Society, 2022.
A. Gonem and R. GilladBBachracl Smooth sensitivity based approach for differentially private pea.
In Proceedings of Algorithmic Learning Theorr, volume 83, pages 438-450. PMLR, 2018.
G. Gur-Ari,J D. A. Roberts, and E. Dyer. Gradient descent happens in tiny subspace, 2018.
M. Hardt and E. Price. The noisy power method: A meta algorithm with applications. In Advances in Neural Information Processing Systems, volume 27, 2014.
M. Hardt and A. Roth. Beating randomized response on incoherent matrices. In Proceedings of the Forty-Fourt Annual ACM Symposium on Theory of Computing, STOC '22 page 1255-1268, 2012.
M. Hardt and A. Roth. Beyond worst-case analysis in private singular vector computation. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '1, page 331-340, 2013.
Kairouz, M. Ribero, Rush, and A. Thakurta. Dimension independence in unconstrained private ERM via adaptive preconditioning. CoRR, abs/2008. 065700, 2020.
G. Kamath, A. Mouzakis, V. Singhal, T. Steinke, and J. Ullman. A private and computationally- efficient estimator for unbounded gaussians. In Proceedings of Thirty Fifth Conference on Learning Theoor, volume 178, pages 572. PMLR, 02-05 Jul 2022.
M. Kapralov and K. Talwar. On differentially private low rank approximation. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1395-1414, 2013.
V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 2018
Kothari, P. Manurangsi, and A. Velingker. Private robust estimation by stabilizing convex relax- ations. In Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 723-777. PMLR, 2022.
C. Li, H. Farkhoor, R. Liu, and J. Yosinski. Measuring the intrinsic dimension of objective landscapes. CoRR, abs/1804.088333 2018a.
H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018b.
X. Li, D. Liu, I. Hashimoto, H. A. Inan, J. Kulkarni, Y. Lee, and A. G. Thakurta. When does differeenially private learning not suffer in high dimensions? In Advances in Neural Information Processing Systems, 2022.
M. W. Mahoney. Randomized algorithms for matrices and data. Found. Trends Mach. Learn., 3(2): 123-224 2011.
12

---

F. McSherry and I. Mironov. Differentially private recommender systems: building privacy into the net. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '09, pages 627-636, New York, NY, USA, 2009. ACM.
F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94-103. IEEE Computer Society, 2007.
S. J. Montgomery-Smith The distribution of rademacher sums. Proceedings of the American
Mathematical Sociery, 109(2):517-522, 1990.
K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In STOC, pages 75-84. ACM, 2007.
N. Peter, E. Tsfadia, and J. R. Ullman. Smooth lower bounds for differentially private algorithms via
fingerprinting codes. The Thirty Seventh Annual Conference on Learning Theory, COLT 2024, volume 247, pages 4207-4223 2024.
A. Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, page 547-561, 1961.
M. Scala. Hypergeometric tail inequalities: ending the insanity, arXiv preprint arXiv:1311.5939 2009.
O. Sheffet. Old techniques in differentially private linear regression. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume of Proceedings of Machine Learning Research, pages 789-88 827. PMLR, 2019.
V. Singhal and T. Steinke. Privately learning subspaces. Advances in Neural Information Processing Systems, 34, 2021. URL httpt:///xxxii..oot www.aaawwwiiiiooaaaaaaaaaaaeaaee wttpab//////....oo///////// 00001
S. Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248, 2013.
T. Steinke Jnd J. R. Ullman. Subgaussian tail bounds via stability arguments. CoRR, abs/1 701403993, 2017.
G. Tardos. Optimal probabilistic fingerprint codes. J. ACM, 55(2), 2008
E. Tsfadia, Cohen, H. Kaplan, Mansour, and U. Stemmer. Friendlycore: Practical differentially private aggregation. In International Conference on Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages 21828-21863. PMLR, 2022.
R. Vershynin. Hiigh-Dimensione Probability: An Introduction with Applications Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
L. Wei, A. D. Sarwate, J. Corander, A. Hero, and V. Tarokh. Analysis of privacy-preservee pea algorithm using random matrix theory. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 1335-1339. 2016.
D. Yu, H. Zhang, W. Chen, and T.-Y. Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference on Learning Representations, 2021.
Y. Zhou, S. Wu, and A. Banerjee. Bypassing the ambient dimension: Private {sgd] with gradient subspace identification. International Conference on Learning Representations, 2021.
13

---

A Additional Related Work
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 = Ei= x5 xz E [Rddd and then performs analysis on the noisy matrix. This method, predating the development of differential privacy Bllm et al. [2005), was later analyzed under differential privacy by [McSherry and Mironov 2209) 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 dl 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 of x (Appendix B.8.4). 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 imput 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 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 [013]. Wei et al. [016]] apply variants of the expo- nential mechanism McSherry and Talwar [2007] to privately select low-rank approximation 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-Bachraad Bachrach (2018) exploit smooth sensitivity Nissim et al. 2007 to release a lowrank approximation the matrix A. This allows adding less noise than worst case sensitivity, under an cigenvalue gap assumption. However, the sample complexity n is polynomial in the dimension d.
Another related area involves estimating the parameters of unbounded Gaussians Kamath et al. 2022 Ashtiani and Liaw [2022). Kothari et al. [2022], Tsfadia et al. [2022). Notably, Kamath et al. 2022
used the subspace learning algorithm of Singhal and Steinke [202] to efficiently learn the covariance
matrix.
A recent popular trend in DP learning is to utilize few public examples to enhance accuracy. This has led to methods for private MI which project the sensitive gradients onto a subspace estimated from the public gradients. By using 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 proposed GEP, a method that utilizes public data to identify the most useful information earried by gradients, and then splits and clips them separately. These works underscore the importance of identifying the subspace of gradients in private ML.
error rate. Similarly, Yu et al. [222T]
B Preliminaries
B.1
Notations
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 E N, let [n] {1, ... n). Throughout this paper, we use i E [n] row index, and j [d] as a column index (unless otherwise mentioned).
For a matrix X = (=?)se(n)jjE(4)) we denote by 2; the ith row of X and by x the jth column of X. A column vector I E IR" is written as (Ii,..., 2.)) ) or x II.... and row vector E R2 is written as (y' "y......'" 3² or I.... input, which is treated the dataset X (#1, Ix) where the rows of X are the elements (and therefore, sometimes write X e (Rd)) instead of X e gaxd to emphasize it).
_ In this work we consider mechanisms who receive an n x d matrix X as
14

---

For vector R we define ||ا||| VEE= oं (the l norm of r), and for a subset S C we define = (a:)ies. and in case is row vector we write r². Given two vectors (21,...,, In Fn , y = (y1....,, Vn), we define (r. Ei= ziys (the inner-product of x and y). We
[d]
denote by S2 the set of d-dimensional unit vectors, that is, Sa = {o E R || 1}. For
a matrix X (I)))E( we let |||||| = max |Xull2 (the spectral norm of X) and let
|X EiEin,sEEj (x/ (the Forbenius norm of X). For matrix X (=:))a(t)
(-1,1) and b (-1,1}, define the b-marked columns of X as the subset Jx [d] defined by T [j [d] x! for all i E [m])-
For d E N we denote by Pa the set of all d x d permutation matrices. For a permutation matrix P E Pa and i [d] we denote by P(i) the index j [d] for which e, E; (where e, and ej are the corresponding one-hot row vectors), and for I S [d] we denote P(Z) = {P(i): E
For d, k E N denote by Wa,k the set of all d x d projection matrices of rank k. For matrix A Rnxd we denote by Span(A) the columns subspace of A (and therefore the rows subspace of A is Span(A")).
For E R, we define sign(=) = 1 220 and for v = (v',..., v4) E Rd we define sign(e) =
-1 <<0
(sign( (1 ................... sig......inn(((1)) {-1,11]
B.2 Distributions and Random Variables
Given distribution we write x D denote that sampled according D. For a set S, we write r + S to denote that x is sampled from the uniform distribution over S.
B.3 Singular Value Decomposition (SVD)
For matrix X E gaxd the singular value decomposition of X is defined by x UEVT, where U E TRax and V E Rdxd are unitary matrices. The matrix E E TRaxd a diagonal matrix with non-negative entries d1 2 ... 2 min(n.d) 2 0 along the diagonal, called the singular values of X. The SVD of X can also be written in the form X = -mmia (m,df a;u;v] where u, and i; are the zth columns of U and V (respectively). It holds that | E of and ||X|| = 01. We define the top-k rows subspace of X as the subspace spawned by the first & columns of V.
Fact B.1 (Min-Max principle for singular values). For every matrix X E gaxdd and E [min(n, d]] it holds that
(x)
max min dim(E)=d VESINE
[| min max dim(E)=t vESaNE
[Xvllg-
B.4 Concentration Bounds
Fact B.2 (Montgomery-Smint 1990 Let = (XI,..., .x)) where the x; 's are i.i.d. random variables with Pr[x; = = Pr(x; = -11 1/2, and let v E R", Then
Vt 1200 0: Pr]l(x, w\1 >|>+ t ||l||a] < 2 exxp(-t2
Fact B.3 (Bernstein's 's Inequality for sampling without replacement (Bardenet and Maillard
2015). Proposition 1.4)). Let X1 XI...., Xm a random sample drawn without replacement from
[W1, ........ ] for n 2 m. Let a = minse(n) ws b = maX Wi = >m= Wy and
0² = ---2 12 (w: 22).. Then for every t 2
t
Pr X;
1 2t 22 exp
exxpp
mo² + a)t/3
The following proposition is used for proving Lemma
Proposition B.4. Let X (I1,..., (Sa)" with singular values 01 2... minn(n.d) 2 0. Let X' (x)....,Xy, be the random matrix that is generated by taking uniformly random
15

---

m-size subset of the rows of X. Let u E Sy and a² = | EE= u)?. Assuming that
m 2n (n holds that
90
Pr X u112
m
2 m a (n(1B))
2B.
Proof. The random variable ||X'e' v122 122 distributed the sum of uniformly random m-size subset of (1x1,00 v)2 3..., (I u)2) (each element is bounded in [o, 1)). In the notations of Fact B.3 it holds
that μ nn (0s, 27² = a² n,, and
a²
Σ
(111, - -d²/n)²
n
1
Σ (1ess 1)* -2(x0,, 0)² /ooonn/nnnn /n2))
"
1
(2i, e)* - a² =d2
n
(ait w)²² = n²/nn,
where the last inequality holds since (zz, 11²² < 1.
Let / = n In( 1/3). By Fact B.3
t
Pr X'vl u| a
< exp
1n + 1/3
2 2 In (1/3)
2 exp
na² + 2 In 11/33//3
2 a (1(33)
$ exp
n
2 2 a²
$ 23,
where the penultimate inequality holds by the assumption on m.
B.4.1 Hypergeometric Distributions
Definition B.S. For T E N, m E [n]] and w E (-T....., define the Hypergeometric probability
distribution Hgmmmmm the output of the following process: Take vector E {-1,1)" with Di U/ w, choose a uniformly random subset I C [ni] of size m, and output EieI Ui.
Fact B.6 (Scala 2009) Equations 10 and 14). Ifx H9 nm then
Vt 02
Pr[xx p 2 t 5ee 3/
where 1 Fx[]
B.4.2 Sub-Exponential Distributions
Definition B.7 (Sub-Exponential Random Variable and Norm). We say that a random variable IR: 2. The sub-exponential norm of
sub-exponential if there exists t 0 such that E. E/c denoted ||x|| is
| = inf 0: E |x//
23
Fact B.8 (Bernstein's inequality (Theorem 2.8.1 in Vershynin dent, mean zero, sub-exponential random variables. Then
2018 ) Let Xi...., Xn. be indepen-
t2
2 0:
Pr Σ x
>1
< 2exp
-Ω
min
max; X sell
x;
16

---

B.5 Nets
Definition B.9 (y-Net), Let be subspace of R Consider subset K. T and let y > subset N S K. is called an ny-net of K. if every point in K. is within distance Y of some point of N, i...
Vx E K. By E N 2 yll 5
Fact B.10 (Extension of Corollary 4.2.13 in Vershynin (0188). D. If E is subspace with dim (b) = k.
then there exists n-net of size (3/7)* &
to the unit sphere in E (i.e., to ENS.).
B.6 Projections
Recall that Wa.k denotes the set of all d rank-k projection matrices. For a matrix A E Rd, we denote that I the projection matrix onto the subspace spawned by the columns of A (in case A is unitary matrix, II A.
Fact B.11 (Theorem I and Lemma I in Cai and Zhang [2088] D. Let X, Y, Z Rgnd such that
X- Y Z. Let IU Un JE[V V. be the SVD ofY, and let [U U [ V la be the SVD of X,
where U, V, Ü, V denote the first is columns of [U U1]. [V V1],
11], [V V (respectively), Let
212 = Hy ZIy, and Z21 Hr Zlly. In addition, let Zig
Ziy]
let
T 0 XV) (i.e.,
the smallest singular value larger than 0), and B = |TTVV ||. If > 8 + min| 2 2 ). then
0212 + 3221
Ml 1pll < 2 a² B2 min 22 221
and
112 F + :11 1F
TT 1p F S V2.
a² 3² min ( 22 2221
Proposition B.12. Let X,Y, X,Y,Z,V, as in Fact B. such that Y has rank-k and Span(YT) is orthogonal to Span 2²) f 2 Z| 2 then
1. TT 11 || S 4 ||
and
ox(Y)
2. [T Hp < 222
|| xxlY)'
Proof. Note that Span(V) = Span(Y Therefore ZV = 0, which implies that Zz1 = Nu ZTly 0. Compute
Tmial (U" (U
Omiul omia(U YU + T ZV
oY(Y).
||UXXII|
UI YVL +UTZV1
|I1|l ||]| ||V1|
< ||
|| 71 ||T Z ITy, || $ ||
|| 11 < ||0 lI || - ||
where the last inequalities in the above two equations hold since for any matrix A and projection ma- trices IT, Hl it holds that [[T, ATT S ||||| and ||TT, ATT2l] S || The proof now immediately
follows by applying Fact B.1l
17

---

Proposition B.13. Let P Raxd be rank-k matrix and let P E Ruxd such that ||P P' S a. Let IT be the projection matrix onto Span (P"), and let IT' be the projection onto the top-k rows subspace of P'. If (P) Z 2a, then
Il 22V2
ox(P) -a
Proof. Let E = P P, and divide E into E = Ep + Ep where the rows of Ep belong to the rows subspace of and the rows of Ep are orthogonal to it. Let + Ep, so we can write The proof now Ep. Note that |ppl g S or and (Y{)) 2 ox(P) |E (x(
P' = Y
follows by applying Proposition B.12 on P', Ep.
Fact B.14 (Implied by Corollary 4.6 Singhal and Steinke (222I). Let 11, 11,..................... 11, Wa,k S.f. for all j [4. ||TT n2ll a. Lef PI, ................................ Pyy i.i.d random vectors in IRd from NO, Taxa). Then Pr Vi [gl. E [t], I - II 11:1, I o vm((t)) ] 2 0.95.
Fact B.15 (Implied by the proof of Lemma 4.9 Singhal and Steinke 202T]). Let E Wa.k and let pi....: Py be i.i.d. random vectors in IR from N(0, laxa). Let P be the d x q matrix whose columns are IIpi,..., -pp Ifq 2 for some large enough constant c, then w.p. 0.95 hold that (P) 2 (2(K) (and in particular, Span(P) = Spon(11)).
Proposition B.16. For any II, E Wa,k and E (Sa)", it holds that
x
[ x
S
2n
11
F
Proof. Compute
|XX
2 ii
(|
T
+
||xx||
TIXT
.2V7
(TT
ñ)
-2
||*1||
-2
2n
Proposition B.17. Let 01..... Uk E Sa with max,, ( of the Gram Sram-Schmidt process applied on ......, Then for every i E [k], there exists A e R with A;-1l S al1 + 4a) and w, E Rd with ||wl]| I 2a² such that
20' Let u1.... uy be the result
= + 1 + w/-
Proof. We prove it by induction i. The case i = 1 holds since in Assume it holds for i, and we prove it for + 1. Define X; = (u; 1)+1) and wi41 Ae(Ai-18;-1 + w.). Note that
|Ai
(0; A + w. v++ill
(e,, W2+1) + 1 meta) + (w, v--1)
< + |A--1 + ||w|||2
Sa+ a2+ 4a) ) + 2
$ <a(1 + 4a),
and that ||0| I a²²(1 4 2 < 2 (recall that I 1.. The proof now follows since
U4 U++1 (u, 0/41/4
Ui+ + de(1; + Ai-10i-1 + ww)
U++1 + Aet + wi+1-
18

---

B.7
Algorithms
Let M be randomized algorithm that uses m random coins. For E {0, 13 we denote by M, the (deterministicc) algorithm M after fixing its random coins to r. Given an oracle-aided algorithm A and algorithm B, denote by A the algorithm A with oracle access B.
B.8 Differential Privacy
Definition B.18 (Differential privacy (Dwork et al. 2006b a)). ) A randomized mechanism M: X y is dedfffrrrrre private (in short, (e. DD- if for every neighboring databases X ( Tnn, X' ( Inn E x (i.e., differ by exactly one entry), and every set of outputs
T S it holds that
Pr(M(X) ST) Pr(M(X')EN) +
B.8.1 Basic Facts
-D then for every randomized F: y + Z, the Fact B.19 (Post- Post-Proccssiigg. M: X" +Yi is (e, 6DDP mechanism Fo M: AT + 2 is (s, D)-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, does so assuming the function neighhoring weighhorrng--reseevingg
Definition B.20 (Neighboring- Preseivingg Algorithm). We say that randomized algorithm G: X )" is wraighboring-preseevee are neighboring w.p. 1.
for every neighboring X, X E X", the outputs G(X), G(X)) E ym
Fact B.21. If G: X + )m is neighboring- and M: ym - Z is (c, 0)-DP, then M O G: X + is (e.
B.8.2 Zero-Concentrated Differential Privacy (zCDP)
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 (961])). Let y and y' be random variables over Y. For E (1, oo), the Rényi divergence of order a between y and y' is defined by
[
P P'())
Da(ylly) a
In
Eyey
where PO.) and P'(-) are the probability mass/density functions of y and y', respectively. Definition B.23 (zCDP indistinguishabilitt).. We say that random variable y y,y' over a domain y are p-indistinguishable (denote by y Ri Y'), iff for every a E (1,00) it holds that
(alylly'), Da Ily) pac.
We say that y'y' are (0,5) jisindistinguishaall (denote by Pp.8 y'), iff there exist events E, E' CX with Prly E E), Pr(y' E ET 2 1 - 8 such that y| Rep y/E.-
Definition B.24 ((p, -)P2DDP Bun and Steinke (2016)) ). mechanism M 5-approximate p-zCDP (in short, (p, DDDP),, for any neighboring databases X,X' it holds that M(X) =p.5 M(X').
The Gaussian Mechanism
Fact B.25 (The Gaussian Mechanism Dwork et al. 2006a Bun and Steinke 2016 ) Let x' Rd be vectors with || x' x'll2 S X. For o V2p
and ~ NOO,, o² Laxa) it holds that
7 R x + Z.
B.8.3 FriendlyCore Core Averaging
We use the following DP averaging algorithm that given the diameter E of a ball that contain most of the points, it can estimate their average.
19

---

Fact B.26 (Tsadiaa et al. 20222). ) Let X and 6 _ E, E, S 1. There exists an (E, (E,8)-DP algorithm
FC_ FC_Averege that gets as input a dataset = (#1,...., ,......,,.,)). E (Rd))n and a parameter & >> and
satisfies the following utility guarantee: If n2 2 log(1/6) + /log(1/6) log(1/3) with [S 2 0.8n s.t. Vo,, E S": 114--z1l S E, then
and 38' C
Az
Syy-FFC_AveraeeS5.0 f1ly all X5] 3, where 1S") Enesi Furthermore, the running time of FC Averagee))) is O(dnlog(n/)) (See Appendix in sfadda al.) (2022)).
Fact B.26 explicitly stated in Tsfadia 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 consider "friendly" DP variant of their FriendlyAvg algorithm (Algorithm 3.3 in [sfadia et al. 2022 ) and as Tsfadia et al. [2022) noted, we can do it such that the probability of failure
low whenever n O 1/8) and the additive error (given success) decreases in a rate of
(1/l log(1/8) where & is the diameter of the points. Fact B.26 immediately obtained by combining FriendlyAvg with their paradigm for DP (Theorem 4.11 in Sfadia et al. [2022) applied with a 0.2).
ne
B.8.4 Subspace Recovery Algorithm Dwork et al. 2014
We next describe the subspace recovery algorithm of Dwork et al. (2014) that strongly takes advantage of large additive gap of k for decreasing the noise that is required for privacy. This algorithm only used in our empirical evaluation (Section 4
Algorithm B.27 (Algorithm in Dwork al. (2014)
Input: A dataset (#1...., xn) E (Sa)".
DP parameters: E,
Rank parameter:
Operation:
1. Compute a projection matrix IT to the top-k rows subspace of X, and compute the singular values dk, 0k+1-
2. Compute g of oh o.41 Lap(2/E).
3. Compute W = 11 + E, where E is a x d symmetric matrix where the upper triangle
i..dd. samples from N((, G-2log(1/b//-2)
Drs
where De, 1+g/2lo((18)
4. Output projection matrix Il to the top k eigenvectors of W.
Note that when the additive gap of - large, the algorithm will add smaller noise per coordinate in Step Fact B.28 (Theorem 11 in Dwork et al. 20144] Algorithm B.27 (2e, 28)
The privacy analysis is done by the following steps. First, by the Laplace mechanism. Step 2 s-DP. Second, by tail bound on the Laplace distribution, the probability that - log log(L/0)/= of - is least - 8. Furthermore, they show that if of t then the Forbenius-norm sensitivity of the matrix II is at most
a-2 So conditioned the above 5 probability event, the Forbenius-norm
2 sensitivity of II is at most g-2 /// and therefore the Gaussian mechanism step (Item
guarantees (s, 6DP,, and by composition the entire process is (2s, 2DP
In order consider a zCDP version of Algorithm B.27 we replace the Laplace noise Lap(2/e) with a Gaussian noise (0, o²) for = p2/p. Given this change, now holds that و a / (1/8)) s (by tail bound on Gaussian distribution). Finally, Step 3 we replace
of o w.p. least A (the required standard deviation for (e, 6DPD) 1/ /2p (what is required for p>ZCDP). This results with the following (2p, 8)-CDPP algorithm:
20

---

Algorithm B.29 (zCDP version of Algorithm 2 in Dwork et al. (2014). Input: A dataset X (#1..... Fn) E (Sa)".
zCDP parameters: p. Ó.
Rank parameter:
Operation:
Compute a projection matrix to the top-k rows subspace of X, and compute the singular values dk 0++1-
2. Compute 9 o o + (, 2/p).
3. Compute W = 11 E, where E is a d symmetric matrix where the upper triangle
/1/(20)
Li.d. samples ((0,
9 2--2 (nt1//8
4. Output projection matrix to the top eigenvectors of W.
B.8.5 Lower Bounding Tools from Peter et al. 2024
Peter et al. 20224 showed that for (n²)) the distribution ((n, d) below induces a fingerprinting codebook for users, each codeword is of length d.
Definition B.30 (FPC hard distribution D(n,d) d) Peter al. 2024 D. Let be the distribution that outputs = (e' - 1)/(c' + 1) E [-1,1] for + (5(5). In (5n)]. For n,d E N. let D(n, d) be the distribution that chooses independently p² ,......"""" ~ ps and outputs a codebook (x (Z1,..., Tn) E (f-1, 1)d)= where for each [n]] and j E [d]. xf is drawn independently over {-1,1} with expectation p².
Framework for Lower Bounds Consider mechanism M: 2 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 13 into hard instances Y E X for M, and then extract from the output E W of M(Y) vector q {-1,1] that is strongly-correlated with X (no and dn are some functions of n and and the weak accuracy guarantee of M), where
Definition B.31 (Strongly Correlated). We say that random variable q = =q''....., strongly-correlate with matrix X 1-1,11nxe if
q²) 1-1,1
Vb E { [- 13. Vje Jh: Pr(q' = 2 0.9
(recall that J& = (j E [d]: 2 for all [n]})
x do x + x the algorithm that generates the hard instances using a uniformly random secret +- Z (i.e., could be random permutation, sequence of random permutations, etc). Denote by F: Z x W - (-1, 1 the algorithm that extracts a good using the secret and the output w. We denote by A AM.F.G(X the entire process:
Denote by G:
Definition B.32 (Algorithm AM.F,G). Let Z. W be domains, and let no, do, n, d E N. Let (M,F.G. be a triplet of randomized algorithms of types G: 11,,1]mo da x Z - X=, M: X - W, and
F: Z x W + [-1, 1]do, each uses m random coins. Define A A.F..G; {-1,1) mo + [-1, as the randomized algorithm that on inputs X E [-1,1]]% 111oooxd, samples <- 2, Y G(X,)) and ~ M(Y), and outputs ~ F(2, w).
Definition B.33 (8-Leaking). Let M, F, G be randomized algorithms as in Definition B.32 each uses
m random coins, and let D(no, do) be the distribution from Definition B.30 We say that the triplet (M. G) is B-leaking if
Prype (0011m d=D [AM..F,r.G." (X) is strongly-corvelated with X) 2 3,
where recall that M, denotes the algorithm M when fixing random coins to r (F,r, , G are similarly defined).
21

---

Lemma B.34 (Framework for Lower Bounds Peter et al. (2024), D. Let 3 E (0,1), no, n. do, d E N. Let
M: x + W be an algorithm such that there exists two algorithms G: {-1, jng do x + x
and F: 2 x W - [-1, such that the triplet (M,F,G G) B-leaking (Definition B.33 If M
1, ina
-DP and G(,,2) 2) weighboring-presenvee (Definition B.20 for every 2 2, then
720 2 Ω
Vdg log (da/8)
Madding-AnddPerrmutin (PAP) FPC The main technical tool of Peter al. (2024) for generating hard instance is to sample a random fingerprinting codebook from D(n, do), append many 1 1-marked and (-rk-marked columns, and randomly permute all the columns.
Definition B.35 (PAPn,do.e) Let l, n, do doxdd Pa - (-1,1jnxe as the function that given X E {-1,11]jnxc and permutation matrix P E Pa as inpuls, outputs X' = =" P (i.e., permutes the columns of X" according to P), where X" is the {-1, 11,, matrix after appending 1-marked and E (-1)-marked columns to X (where recall that b-marked is column with all entries equal to b).
N. and let d do + 28. We define
{-1, n:
Note that for every n, do, & and Pd, the function PAP PAPn,do,e:: P) is neighboring pressrving (Definition B.20
Definition B.36 (Strongly Agrees). We say that vector q = .q......'' g²)) strongly-agrees with matrix X E { (- if
Ab (-1,11 e e = bb} 2 0.9
The following lemma capture the main technical property of the PAP technique.
Lemma B.37 (Peter et al. 20244). Let f, n, do E N such that d do + 28. Let M: (-1, 1]nxd [-1, 1] be an mechanism that uses m random coins, P + Pa (a random variable) and for X (11,11 let Y PAP(X. P). Then for any distribution D over o [-1,1]mxdo;
(r XND (Y,() . pT do is strongly-correlated with X] > Ex-DIPr|M(Yy) strongly-agrees with Yx]]-
C Upper Bounds
In this section we prove our upper bounds for subspace estimation. In Appendix C.2
we prove
Theorem 1.66, and in Appendix C.3 we prove Theorem 1.7 Both algorithm share similar structure that is defined next in Appendix
C.1 Base Algorithms
Similarly to Singhal and Steinke 202T], algorithms will follow the sample and aggregate approach of Nissim et al. [2007] That is, we partition the rows into /. subsets, compute (non-privately) the top-k projection matrix of each subset, and then privately aggregate the projections. This is Algorithm C that uses oracle access to an aggregation algorithm. Unlike Singhal and Steinke [2021] who assumed that the rows are i.i.d. Gaussian samples, here we take random partition and show that with large enough probability over the randomness of the partition, the projection matrices are indeed close to each other. We consider two types of aggregations: The first type, called Algorithm C.2 simply treats the matrices as vectors of dimension d' and computes DP-average of them using FriendlyCors averaging (Fact) 13.. The second type, called Algorithm C.3 is more similar to the aggregation done by (Snngaal and Steinke (2021). That is, sample reference points Pl..... Py and then aggregate the kd dimensional points [(1,,)1,... II,,,) ) The difference from Singhal and Steinke 2021
is that we use FriendlyCore averaging (Fact B.26 which simplifies the construction.
22

---

Algorithm C.1 (Algorithm EstSubspace).
Input:
A dataset X (Z), ( E (Sa)".
Parameters: k,t. t.
Oracle:
A DP algorithm for aggregating projection matrices.
Operation:
Randomly split X into subsets, each contains (at least) m [n/t] rows.
Let Xiy..., Xx be the resulting subsets.
2. For each [8]: Compute the projection matrix I1 of the top-k rows subset of X--
3. Oulput II Agg([I,,.....)
Algorithm C.2 (Algorithm Naive_Agg).
Input: A dataset II (II,,..,,ll 1I) E (Wa,,)). Privacy parameters: e, 1.
Utility parameter: { [].
Operation:
Compute î FC_ FC_Average,, (TI, 5) (i.e,, each I1 treated like a vector in RRod
2. Output πI argminnewa. I1 f1
Algorithm C.3 (Algorithm SS (S_Agg).
Input: A dataset (II,,..., I1,) E (Wax)) Utility Parameters: k; q, S.
Privacy parameters: 5, < 1. Operation:
1. Sample P1....aPo (Ō, llaxa) (i.idd samples from standard spherical Gaussian).
2. For j E [t], compute yd = (I,pp,...,,II, (lpp)) Redd, and let Y = (y ,y"),
3. Compute z (Z1,..., Zqdd) FC_ A (z 1R
4. Let P be the x d matrix whose ith row (for [q)) is Ea(--1)+1.... ,ds) (which estimates the projection of ps onto the top-k rows subspace of X).
5. Output the projection matrix II of the top-k subspace P.
C.1.1 Running Time
We analyze the running time EstSubspace S5.Aes Denote by T(n, d, k) the running time of computing projection matrix to the top-k row subspace of an n matrix. The running time
of Step 2 in EstSubspace is t (n//t, k). The running time of SS_ SS_Agg is O(dqtk) on Step 2
Odqt log t) on Step (.FactB..26 and T(g. d, k) on Step[5 Overall is t. (.m dt)/t/,dd.))) +T)+T(qq.0 (lgg + k)). For both our weak and strong estimators (described next) we use n/t = ²(k) and = (k), and therefore we obtain that the total running time is a T(m, d, k) + (dknn) for n//l (k).
C.1.2 Key Property
In order to claim that the (non-private) projection matrices are close to each other, we use the following lemma which states that with high enough probability projection matrix in the subset close to the top-k projection matrix of the entire matrix.
random subset, the top-k
.e.,...,T.)) (Sa)" with singular values 0i 2 ... 2 mmin[n.d] 0 and of 2 0.01n/k. Let X' (Sa) m be uniformly random m-size
Lemma C.4 (Restatement of Lemma 2.1b. Let
23

---

subset of the rows of X (without replacement). Let II and IT' be the projection matrices to the top-k rows subspace of and X', respectively. Then the following holds for 7n /
de+1 and ax
72
1. m max
2nn),, then Pr & 13
|
2n AV II
71
2 1 - B/2
m
2. mf 2 800 In
4, and 3 2 4n2. then Pr ||||| Il
S
2 1 - B.
Proof. We will prove each part of the lemma by applying Proposition B.12 In the following, let Ei= "anie be the SVD of X, and note that we can write X (Zi, ................................ Li where {i1.... .im a random subset of [n] (without replacement). Let Y = (y1,.... Un) = Σ o,u;y and let minnf..d)
Z (21 ,.l...,,,,,,, 2n) 2i=k+1 o;u;o," and note that Span Bn Span vn is orthogonal to Span (21,.... Fn Span (u++1 (n J. Furthermore, define the random matrices Y (y). ..... yt... and Z' 1. 2mm) and note that X' Y Z'.
First, by Proposition B.4 (applied on U1,.... 02) and the assumptions on m, ds. holds by the union bound that
Pr OK (Y)
V
m
ok
2 1 3/2.
2n
In the following assume that the event in Equation |Z < [||l S ok+1 S "1 and that (Y))² o
occurs. We first prove Item Note that
2
2 Z'|l (the second inequality
holds since m 47in). By applying Proposition B.12 on X', Y', Z' we conclude that
|Z'|l σ YY)
'2
|||I
4
S 4V
71
We next focus on proving Item
2 Note that |
Di=bt1 of oz and that E [1
m
2 m
120
Therefore by Markov's inequality
Pr
z
2
2m
220
> 3/2.
Bn
In the following we assume that the event in Equation occurs. Note that o% (Y') 2m
>
2n o
in 12 of
f 2 2| 2'12 (the second inequality holds since
B 472). By applying Proposition 1.12 2
on X', Y', Z' conclude that
V
2m Bn
ZZ' 1 ok (Y')
72
2 $ 1/ 3 72.
||| IT
2
22
2n o
C.2 Weak Estimator
In this section, we prove Theorem [.6] stated below.
Theorem C.5 (Restatement of Theorem 1.6). Let n, k, d N, X > O. 8,0 E (0, where
k < min(n,,) d). There exists an (ki, X, 0.9, 7max = M(min 1 subspace estima- for M: ( x [0. 1] + Rdxd with
m k logg
log(1/5)
minskydd d} Mlog(1//)) 110) A8
such that M(-,7) is ()- for every [0. 1].

---

Theorem C.5 is an immediate corollary of the following Lemmas C.6 and C.7
Lemma C.6. Let 1 = c1 log(1/6)
dy Aooo 1 loR(20)
(where ei is the hidden constant in Fact B.2 Then for any n 2 800 (25k)) t, the mechanism M: (Sa)" x [0, - Wa, defined
As
by M(X,7) == EstSubspace Naive Agg 6.con (X) is an (k, X, 0.9, 7max 20 --eak-subbppcee
estimator:
Sminin.d (x)) (xY2
Proof. Let X E (Sa)" with
2 S Tmax and let E Wa, be the projection of top-k rows subspace of X. Consider a random execution M(X). ). Let {m)))=1: II be (random
variables of) the values of {Iı))]=ı II in the execution, and let II be the output. By Lemma C
(recall that 7max I 2 and the union bound,
V E [
Pr[[[II I1 s 60q] 2 0.99,
Let a, I[ HI - 60y) (indicator random variable) and let a Ej=1 aj. By Equation holds that E[a] 2 0.991, and recall that a S L. It follows that
E[a] 0.8t Pr(a 0.8f]
Pr(a 2 0.8t]
0.99 - 0.8(1 - Priaa 0.8t))
Pr(a 2 0.8t) 2 0.95.
(4)
In the following we assume that the event 2 0.8t occurs. Let J E [t] a, 1}. Note that our choice of / satisfies
1og(1/0) d (log(1/8) log(())))))))))) (100)
t t c'
where c' denotes the constant from Fact B.26 averaging) that
Therefore we conclude by Fact B.26 (FriendlyCore
Xy
Pr
II
0.99.
F
The proof of the lemma follows by Proposition B. since
II
2
II πI
Lemma C.7. Let C1 C2 Cs be the constants from Facts
B.14
B.15 (respectively), and let
VT++ /log
ak log(1/6)
(1d))
c be a large enough constant.
Let f. = c. log(1/6)
Xe
Ae
= ai (Vi+ /I(qqt] and k. Then for any n 2 800k ln(25k) t, the mechanism
S5_AgE, A. (X) is an
M: (Sa)a x [0.1] Wa, defined by M(X, = EstSubspace
(ks, A, B 0.9, 7max Omin 1)))k http:/wwaaaasssaeeeeeeeeeeeeeeee subspace-estimator
> mint ox(X)²
S 7 7max and let 11 Wa. subspace of X. Consider random execution of M(X). Let (II (p:1g -- be (random variables of) the values of {II,); fp ( 1/-1, P in the execution, and let II be the output. As in the proof of Lemma C.6 let Ej aj where a, = 1[ I1,1 || < 607). Then Equation (4 imples that
Proof. Let X (Sa)" with
be the projection of the top-k (x
Pr(a 2 0.81) 2 0.95.
In the following assume that the event 0.8t occurs. Let J (j E [t] a, 1}. By Fact B.14 and the definition of 7) we obtain that
Pr E ag JJ: |III - 11)) S 60ml 2 0.95,
25

---

In the following we assume that the above event occurs. This yields that
vi.j E
lly; Yyll2 I 120n by = &.
Furthermore, by the definition t and r) (note that depends on log(t)), it holds that
Log(1/0)
v dk (og
8 2 d'
ca
1500n)
where denotes the constant from Fact averaging) that
B.26 Therefore we obtain by Fact B.26 (FriendlyCore
Pr
P
P
0.99,
12
where P the q x matrix whose rows are III...... Hpp By Fact B.15 we have that
Pr(ox(P)2csV) c3Vk 0.95,
and in the following assume that the above event occurs (which in particular implies that Span(P") (I)) Finally, since 2a < (P) by assumption (and assuming Tmax I ex )
we conclude by Proposition B.13 that
II íí
22
ox(P) S \7/2.
We therefore conclude the proof of the lemma by Proposition B.16
C.3 Strong Estimator
In this section, we prove Theorem
1.7 stated below.
Theorem C.8 (Restatement of Theorem 1.7p. Let n, k. d E N. À > 0, such that k S min (n, d}.
There exists an (ki, X, = 0.8, (max))weak subspace estimator M: (Sa)" x [0, 1] + Rdxd with
1 Tmax Ω minl X
X3g²
>eelog(1/8) (k: + log
dk log( log(111) dk log(1/5)
Ae
and
log(1/8) +
k: + log (olo((1/))
dk log(1/0)
0 k log &
X2g2
such that M(- 7) is (E, for every 7 [0, 1].
Lemma C.9. Let C1, C22 C3 the constants from Facts B. to B.15 respecttively). and let be large Log(1/5)
enough constant. Let 1. = log(1/8) (k+Jog( x²g=
.1 (VT + v VI(qq)) and C2 k. for any > 800k In (25k) tt the mechanism M: (Sa)" x 10, Wa, defined by M(X.7) == EstSubspace As_, & 9. (X) is an (k, = 0.8, Tmax min + agx ))
6.
strong-swuspacc--ssiimttoo
Proof. Fix X E (Sa)" with (x)
(x(X) 5 S Tmax and let II E Wa.k be the projection of the top-k
subspace of X. Consider random execution of M(X). Let M {pr) (y*
26

---

be (random variables of) the values of ( fy be the output. By Lemma
ور= 1j=1, P in the execution, and let II C.4 (recall that Ymmax 20 and the union bound,
Vj [4]
Pr
1Ill S 4V217 0.99.
(5)
Let a, = 1 HI, < 4v 2ty) (indicator random variable) and let a Ej=1 aj. As in Equa-
tion 44. the above yields that
Pr(a 2 0.81] 2 0.95.
(6)
In the following we assume that the event 0.81 occurs. Let = (i E [4] : = 1]. By Fact B.14 and the definition of y we obtain that
Pr Vi [g).j EJ: - (II-H1))Pl S 4v2(m]] 2 0.95,
In the following assume that the above event occurs. This yields that
vi.j J lly; Ysll2 s &v &. Furthermore, by the definition t and 1), it holds that
t t2 d log((/5) v dk (1/( ca 150nyt
where o' denotes the constant from Fact B.26 averaging) that
Therefore obtain by Fact B.26 (FriendlyCore
CsAvkr
Pr
P
P F
0.99,
where P is the q matrix whose rows are 1lp 1lp...... 1lp By Fact B.15 have that
Pr(ox(P) 2 csV
0.95,
and in the following we assume that the above event occurs (which in particular implies that Span(P") (pan((I)). Finally, since 2a s (P) by assumption (and using 7max _
conclude by Proposition B.13 that
I 22
ox(P) S \y/2.
a
We therefore conclude the proof of the lemma by Proposition B.16
D Lower Bounds
In this section, we prove our lower bounds. In Appendix D.I we prove Theorem 1.8 (lower bound for weak estimators) and in Appendix D.2 we prove Theorem .9 (lower bound for strong estimators).
Both lower bounds rely on the framework of Peter et al. [024] described in Appendix B.8.5
Throughout this section, recall that for d, k N we denote by Wa,k the set of all d projection matrices rank kt and denote by Pa the set all x d permutation matrices.
D.I Weak Estimators
Theorem D.1 (Restatement of Theorem 1.8
(0. 1,,
Letn,
such that d 2 ck and
X² < cogg for large enough constant >
d
0, and n is multiple of k. IfM: (S.)" x 10, 1] + Wa, is
a (ki, X,B, 7max = I0xx" --weak subspace estimator and M(:77) is (1, 5nk -DP for every 7 E [0. 1).
then n 2 Q
Vkd/A Ing 2
27

---

Theorem
1.8 is an immediate corollary of Lemma B.34 Framework for lower bounds) and the following Lemma D.2
5-10 no = =n/k, 2. (1-1d)d do = 20, X Sa. = [k] (Pa)* and W Wa.kk Let G: (-1,1]moxae x
Lemma D.2. Let n, ki d, B and as Theorem D.
2 + x" be Algorithu D.3 and let F: Z x W + 1-111 be Algoritim D.4 Then the triplet
(M, G) is 0.80 -leaking (Definition B.33
Note that by Lemmas D.2 and B.34 we obtain that no 2 M
vdn but since no n/k and
Tog (do/
do ((dd) = @ X the proof of Theorem D.1 follows. We next prove Lemma D.2
Algorithm D.3 (Algorithm G).
Parameters: no, n, do, d, l N.
Inputs: z == (s, (P,,..., ;h)....,P))))..)......).. for [k] and Pl,..., ......,P Pa Pd. and a matrix X (-1,1]mmp Operation:
Sample = (AI,.... As) Dino, da)*. and set A₃ = X. do 2. For t E [k], compute B, PAP PAPno,do (Ar, P.) {-1, 11,,1oood (Definition B.35 and let
B E (-1,1]nxd be the vertical concatenation of Bi...., Bg.
3. Output Y BE (S
Va
Algorithm D.4 (Algorithm F).
Parameters: Tho, n, do, d, & N.
Inputs: 2 == (s, (P1, Pk)) for E [k] and Pı,..., Ps Pa, and rank-k projection matrix πI E W (which is the output of M(Y, 1000x) )
Operation:
1. Compute a vector u (u'....,u?) ua) Span(1i P!)) that maximizes d// min 2j=do+1 sign(w'). Σ E -+=1++ sign(w)))
d3
2. Output sign do E 11,11)d0
D.1.1 Proving Lemma D.2
In the following, we define random variables X D(no, do) (Definition
B.30 and
(s, (P1.... .P)) + Z, and consider random execution of A G.F.GG(X (X) F(z, MGG(M z))). Let B Bi...., B,. B, be the values of Bı,..., .....,,, Bg E (-1, noxd
(-1,1]nxc and B E
Y E (8.)" in the execution of G, and let Y, / B Y2
BB, (note that Y is YI...., Yε). Let u be the value of u Sa the execution of F. For b E 1-1.1) }) let Fù be the set of b-marked columns of B, pf (note that F, includes
/a
a vertical concatenation
do + +,,.... do and F_, includes do + l I,....,i d). Let H, {do + 1,.... do + 2/23 F1
and H-1 {do + ++ 1, do + 32/2] C F-1. and let H Hi U H-1. Fort E [k], define
Vt /28
(0
P Sa
do
The following claim holds under our assumption that 2 < oklog for large enough constant
Claim D.5. Let = - It holds that
Pr
Σ
2 0.9.
1=
28

---

Proof. Recall that d = do - 20 and f (1 addd for 5-104X2R' First, note that
Pr[vi,...., Vi are linearly independent] 2 1 (2 2 + 2- +...+ +2 2++(k-2) 2 0.99,
(8)
where the last inequality holds since Ri d/2 2 c k/22 2 for large enough constant 0. Furthermore, note that for every s, E [k), 26- (v,, vi) E f: signtv/)=1 sign(v)) (v/)
Σg
y: sign(v))=-1 sign vi
where each sum has Hypergeometric distributions 24 (Definition B.5p. Therefore by Fact B.6
and the union bound, it holds that
so (V
log k idd
Pr Vs,t t E l(v. (v..
> 0.99.
(i.e., VI...., Vi are almost orthogonal).
In the following, we assume that the events in Equations (8) and occur. Using the Gram-Schmidt
process Viy..-a Vk, obtain orthogonal basis -1.---. U1 to Span (vi...r, V& such that for
every / E [k].
+ -V- + Wt. where A S O log k
and
|/wll2 0
log
(holds by Proposition B.17 Recall that Y is vertical concatenation of vd
B
Va
B and for
every t E [k], the rows B, are all in
2 +
P. = 1-1, x (O....... 0 P. {-1,1]db x (h...ry - -....,
d
2
Therefore, we obtain that
IY un uel12 2 Y uel2
(10)
28
dg
Vt, uz)
n1
d
a) (1 11-0
log k ))
2
-00
2 4a) nn,
where the last inequality holds whenever a 2 Oloog k/d), which holds by the assumption on
We therefore obtain that of(Y)...., ({Y 2 (1 4a) no which yields that Σi (Y) s
k(1 4a. ni 4an. Hence
E Y
4am 4a)
4ock
72
(11)
4a
10
where the second inequality holds since 5-10"X#E
The following claim holds under our assumption that d 2 ck for large enough constant > 0. Claim D.6. It holds that
Pr (u) dMH strongly-agrees with (B.P"))
[d]H
2
0.8,3
k
where "strongly-agress" 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, X, B, Tmax ) estimator, it follows from Equation 11 that w.p. 8, the output II of M(Y) satisfy
i 1 > II Y
7
(12)
1000*
29

---

where we denote by II the projection matrix onto Span(vi..... v&} (defined in Equation 7). In the following, we assume that the event occurs. This yields that there must exists [X] such that
II
Y
F
1000k
2
l|vell
K
1000k
(0.999 a)) k
Since s (part of x) 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 = 8, i.e.,
n Y
(0.999 a)
(13)
In the following we assume that the //k-probability event in Equation
13 occurs.
Recall that BN = Vd. Y,, and let IT, = -II PT_ and B' = BB P It follows that
II (B) (B]TT| d. II Y 2
dn
(0.999 a. k
(14)
In the following, define
jED Fi
v= (v',..., vo) 13
where
v
-1 jEB F
(15)
O.W.
Note that each row of B', can be written + & where & 1-1,0,1) x (0, that
This yields
2
k n/R
I1g T k II (B2)7 2
T' 2
II
n i=1
> (0.999 add do 2 (0.999 20ddd
Now, since
2 |M (v. = (i,v + (1 -i. fi +(1 - -i.v = Viv T
+ (1 [1,
we conclude that for -a' -I. E Span
||v - 1 livl2
M T
2 S d - (0.999 2add <
d
(16)
500
We next define (I, -nn-goood vectors.
Definition D.7. We say that vector w 1-1,1] is (I,n)-good iff for (1 fraction of the indices j E I it holds that sign(w") = sign(v') (for the v defined in Equation 15
We use the following trivial fact:
Observation D.8. If w is not (I, good,, then ||w -v1 2 n/Z
30

---

Since for both 6 E (-1,1), [4 2 (1--add d/5 and v
d Observation D.8 implies 500
that V is rigoood and (H-1;7))go00 for 100 Therefore, the vector (computed in F) is also miggood and (H-1.
In the following, we use similar arguments to Dwork et al. [2014] for claiming that because is good on half of the padding location, then it should also good on the rest of the marked locations.
From the point of view of the algorithm M (which does not know Ps), the locations in Hi, are indistinguishable from those in F, Ho- Therefore, for any point that is not (Fb,31))go00) the probability (taken over the random choice of Ps) that it is (%,,2o))good
at most exp(-S(
Now let N be (nvv))-net of the vd-sphere in Span(IL (II,) (Definition B.9. Taking union bound over a exp(O(k (og(1/n)) = ex)(O(k) points in NN (Fact 1. and recall that dl 2 ck for large enough constant c, we conclude that except with probability exp(O(k)) exp(-9(rdd) I 0.01, any given vector N that is (HN. 2n)og is also (F& Hs. 4n)-good. Since u is (Ha. -goodd, then its nearest net point u' is (Ha. 2g)ogood. Thus u' is (Fù H.s 4n))- which implies that (F& Hg. 5r)) -nodd except w.p. exp( (x((= & 0.01. But by defimition of v, it perfectly agrees with the marked columns of B, P Since by < 0.1 the above implies that sign(u)Fu Fo strongly-agrees (Definition B.36) with the matrix (B, [B.) P
which implies that sign(u) [4)
strongly-ape aagnee agrees with the matrix (Bg .P)) [d]) as required.
We now ready to prove the final claim that concludes the proof of Lemma D.2
Claim D.9. It holds that
0.83
Prar'e(0.1)7 XwD A.M.F..G, (X) is strongly-correlated with X] 2 k
Proof. In the following we assume that the event from the statement of Claim occurs, and let H = Hi U UH-1 Define the permutation matrix P' E Poo++ that is obtained by removing the rows
H and the columns P*(H) from Ps (i.e., P' is the permutation induced by P. between [d] H and
[d] (P().. Similarly, define the permutation matrix P E Pe that obtained by removing the rows H. [d] H and the columns P. (H) from Ps (i.e.. P' is the permutation induced by Ps between H and P. PPH)). Note that P' distributed uniformly over Pdo+e for any choice of P In the following,
let II' 14W q' sign(u) P', and B' B ( By Claim D.6 holds that
0.8,3
Príq' strongly-agreet with B"
(17)
k
But note that B' PAP no no.do.t/2 (2/4//2(X,, (X, P') and also note that q' is just a function of II' and p (i.e., independent of P\) since it equals to sign(w) ( P' ([d)))) where w is the vector in Span EjEp'(H (H 1) (ign(w")). Furthermore, note that (q' (P')T) L....d q. where q the final output of A (M...G(X)
that maximizes min min (H₂) sign(w"),
F(z,M(G(XX z))). Thus
by Lemma B.37 and Equation (17) we conclude that
0.83
Pr Ptr.''-0011" X-D X-D (000:000.../(AMM.F...... A.M.F.G.'(X) (X) is
with x] 2
k
D.2 Strong Estimators
Theorem D.10 (Restatement of Theorem 1.9
Let 2,
(0. 1] such that d 2 ck
and X2 < clogk for large enough constant 0, and is a multiple of k. If M: (Sa)" x 10, 1]
Rdxd an (k, X, B, Tmax x0 >trrong subspace estimator and M(: 7) is (1, 5nk -DP for every
kvd/A
7 E [0, 1], then n 2 Ω log /log (og(d)) log (2n/k)
31

---

We prove Theorem D.10 using similar technical lemma to Lemma D.2 but now since M is a strong subspace estimator, we can use = = (rather than O x as in Lemma D.2
Lemma D.11. There exists large enough constant > O such that the following holds: Let
k d. 2, and M as in Theorem D. 10 lel leta- log((d))
nh = =n/k, E. 2 {1 a)d
do = d 28, X
Sá. 2 =
k x (Pa)* and W = Wa Let G: (-1,1)moxda x 2 - X
be Algorithm
D.3 and let F: x
W + [-1,1] 1] be Algorithm D.4 Then the tripler (M, F, is
0.83 -lekinn DDefiitton B.33
By Lemmas D.11 and B. B.34 it holds that no 2 0 log (do/ ). The proof of Theorem D.10 now follows since no n/h and do x ad for the a defined in the lemma.
do
D.2.1 Proving Lemma D.11
As in the proof of Lemma D.2. we define random variables X ~ D(ng, da) (Definition B.30 and z (s. (PI. (P...... P&)) < Z, and consider a random execution of (M.. = F(z, G z) z))). Let (A.), (B,), Y be the values of {Ar), [Be),
Y E (Sx)* the execution of and recall that Y is a vertical concatenation of Y Y,...., Yx where Y, Va B,.
The only difference from proving Lemma D.2 is to prove different version of Claim D.5 that only considers the gap between σ and 0x++ (which will meet the requirements of the strong estimator M). Namely, is suffices to prove the following claim:
Claim D.12. holds that
Pr|ow+i (Y) oR)) 0.9,
for
T000A
Proof of Claim D.12
As in Equation
7 for [k] we define
(O....0.1 0.
P. E Sa
(18)
228
do
Let E = Span (Vi,....
V Note that by construction, {vr), E are independent of { {At).
Similarly to Equation
99 it holds that
( I(v. vo)l 50 ( log k
Pr e E [k]
> 0.99.
(19)
d
This yields (using similar steps in the proof of Claim D.5 that w.p. 0.98, dim(E) l: and every unit vector u E E has Yull2 2 - 2.
(1-4a) This particular implies that (Y 2 (1 - 4a) D
Our goal is to prove that w.p. 0.99 it also holds that o2.1 (Y) S Ō Let be the orthogonal subspace to E. Our goal is reduced to showing that there exists constant e such that
Pr Vu E EnSa:
|Yull < a clog(k/ log(2m//g
" 2 0.99.
(20)
T
Given that the event in Equation and hence
20
holds we conclude that 02 (Y) & a co-clogk///n (k/))))) (2n/k)
of k
(log(k//))lo((2n/k
1
72
YY)
(1-4a)
12
where the last inequality holds by taking
1
2 106 clog(k//o) log((n/k).
32

---

Note that for every E Sa is holds that
A Yu Y
A 2:
where the last equality holds since u is orthogonal to Vi,..., Vv. Therefore, we can prove Equa- tion (20) by proving that there exists a constant c' such that
1 d
k Σ 2m1
Vu E Saz
Pr
> a- log((t/a))og(2n) k
< exp(-dln(33koo) - 10).
(21)
Given that Equation 21 holds, prove the claim using net argument. By taking exp(d (3kk/k)))ssii / a/ feek-net of S₂ (Fact B.10 Equation (0) follows by Equation 21 and the union bound over all the net points, which concludes the proof of the claim.
In the following we focus on proving Equation (2I). Fix columns vector E Sy. Recall that A, D(no, do) (Definition B.30). and A, located dg random columns out of d, which are the columns coordinates of a,,; are i.i.d. Bernoulli distribution over {-1,1}, each takes w.p. 1/2 and w.p. 1/2. Therefore by Fact B.2 it holds that
P.((o)). Let ar, (+ do be the 7th row of Ar. By Definition B.30 the
de 21| 112
3A 2 0: Pr[ u)² 2 = Ey [Pr[[aa, uz)² 2 E]] S Eg
2cxp
dg
dE
$ exp
$ 2 cxp
E 2
2a
where the first inequality holds by Fact B.2 the second one holds by Jensen's inequality (and since the function f(x) e e-1 is concave), and the last one hold since union bound over the n/k rows of A, we obtain that
dg
S a.
By the
En AA 2 0: Pr Ir
2n
dp
<
exp
k
2a
or equivalently
3A 0: Pr Pr| 3 2 E = =Pr[1A,,0]]
2n
exp
dk 2an
$
(22)
In the following, let b. YYul2 and define by: b. E[b,]. and μ that
2am In (2n/k) dk
First, note
/
Ebb
Pr[b, > EldE
Pr(b. E)dE
2n
dk
S p +
exp
{ }dl
2am
2n.
2an
dk
$)
00
p +
exp
k
dk
2am
2nn
< 2pp
33

---

In addition, it holds that
b
[b]]
exp
Pr
exp
> { de
8/1
8pu
0
3/2
Pr[[b/ 8pln(E))dE
3/2
= 3/2
(Pr[b; Sp (n() E|b.l] + Pr[b, < (8p + bib,,l)dg
3/2
$ 3/2
Pr(b/ > (1)n(()) + Pr(b. 18u1n(3/22) 24 de
3/2
33/2
2n
exp
dk 2an
8pln(E) )d
3/2
= 3/22-
E
5d
de
3/2
2.
Namely, by is a Sub-Exponential random variable (Definition B.7 with ||b/ll,, S 8j,. Since (b²) are independent, each has zero mean, we obtain by Fact B.8 that
E
AA
Pr
bi
2kμ
S Pr
b 2
E
exxp
-0 min
k64p
8p
We now take f = c. (nk/a( 2 ca . log(k/a) log(2n/k)
k for large enough constant c. Recall
that by our assumption on it holds that & 2 4kp. Hence
Pr
Y
u
12
26
< Pr
b, 2 2kμ + E/2
S exp( 15d ln(k/a)),
S exp( In3k//a) - 10).
where the second inequality holds assuming that c is large enough. This concludes the proof of Equation (1 and therefore the proof of the lemma.
E Broader Impact
In this work we develop algorithms that maintain the differential privacy of the input points. When the points represent individuals, our work helps maintain the privacy of those individuals.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Upper bounds, lower bounds, and experiments are provided in Appendices C and D and Section (respectively).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
35

---

Justification:
Full proofs are provided in Appendices C and D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
This information is disclosed in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
36

---

Answer: [Yes]
Justification: The Python code provided in the supplementary material along with a README file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
aubl:c//guddee/Ddeeeliniiss///// iollo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https /pips.ccc/pulic/guuu guwde//ddee/ee/ Coc//ooodeeesiseeeeeee hwtpibbmsssiioooooooiooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All the details are given in Section
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
that we perform 30 repetitions for generating each graph point which represents the trimmed average of values between the 0. and 0.9 quantiles.
Justification: We mentioned in Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
37

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We mentioned in Section 4 that all experiments were tested on MacBook Pro Laptop with 8-core Apple M1 CPU with 16GB RAM.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://////errppp.ccccc/c///////
Answer: [Yes]
Justification: We only perform experiments on synthetic datasets that do not cause any harm.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Appendix E
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact 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.
38

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: We mentioned in Section 4 that we use the Python implementation of T'sa dia al. [2022] that is publicly available in pattps://med:: icml. wt..c///ooo wwt.cc///eeeeeeeeeeeeeeeeeeeeeee (Conferences/ ICML2022/
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 dataset.
The authors should state which version the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
39

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "AtaBmk39D6", "reviewer": "Reviewer_T3Ub", "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.", "questions": "Do the authors perceive a way to improve their upper bound to get better dependence on $k$?", "limitations": "The quadratic and cubic dependence on $k$.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "PCA is one of the most important problem in modern data analysis and ML. Unfortunately, with privacy constraints, it requires a lot of data samples to perform PCA with any reasonable accuracy. This has led researchers to look at instances where PCA can be easy. Most of these works rely on the assumption that the singular values of the data matrix has a particular behavior. This work extends on those line of work. \n\nIt provides nice upper bound on various assumptions regarding the multiplicative decay of the singular values. The upper bound result follows the framework presented in Steinke-Singhal. The lower bound to me are the more interesting one, which is based on recent ideas of Peter et al.", "weaknesses": "The lower and upper bound do not match. There is a large gap between the two. One major focus in the area of PCA is to get a bound under these assumptions such that when $k \\to d$, we recover the optimal rate. For example, this was the motivation behind Mangroubi-Vishnoi. Unfortunately, under that assumption, the upper bound is way worse due to its dependence on $k^2 \\sqrt{d}$ and $k^3d$, respectively. Due to that reason, I believe that the lower bound is tight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive review. \n\nRegarding your question. We currently don’t know how to improve the upper bounds, and we agree with your intuition that the lower bounds seem closer to the truth. One supporting evidence for this intuition is that our lower bound for strong estimators generalizes the tight lower bound of Dwork et al. 2014 that only holds for instances that have a multiplicative singular-value gap above some specific constant. Yet, it is important to note that prior to our work, the gap between the lower bound of Dwork et al. 2014 and the upper bound of Singhal and Steinke 2021 was far beyond quantitative because the settings were very different. So we believe that our work, although it left quantitative gaps, makes a significant qualitative step towards understanding this problem better.", "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": "", "extra_scores": {}}, {"review_id": "tqH6NYjQOQ", "reviewer": "Reviewer_UdSk", "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.", "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": "Yes, the authors have addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This work makes significant progress on an interesting problem, and the contributions could potentially have applications to notably improving efficiency of the broadly useful DP-SGD algorithm (in cases where gradients approximately lie in low-dimensional subspaces).", "weaknesses": "The presentation of this work could be improved. The reader's first introduction to what gamma-easiness means and how it eliminates dimension dependence comes in a footnote in page 2. I think that given the centrality of easy instances to this work, it would be good to dedicate a few sentences early on to give the reader a more precise understanding of what gamma-easiness means generally and how we should think of how gamma will relate to other parameters of a problem.\n\nI 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. \n\nTypos/Suggested edits:\n\nSection 1.5.2\n\n“combination between generating” -> “combination of generating”\n\n“However, their result strongly rely” -> “However, their results strongly rely”\n\n“top-singular vector” -> “top-singular vectors”\n\n1.5.3\n\n“which have the property that we seek for” -> “which have the property we seek”\n\n1.7\n\n“Additional related work appear at Appendix A. Notations, …” -> “Additional related work appears in Appendix A. Notation, …”\n\n2\n\n“that arbitrary partition” -> “that arbitrary partitions”\n\n“expected Forbenius”\n\n“The first one simply treat each matrix” -> “treats”\n\n“who privately estimate” -> “which privately estimates”\n\n“asymptotical” -> “asymptotic”\n\nFootnote 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.\n\n3\n\nParagraph 4 of Section 3, second line, I think sigma_i should be sigma_i^2\n\n4\n\n“that are approximately lie” -> “that approximately lie”\n\n5\n\n“Yet, it still left open to close the gap” -> “Yet, closing the gap is still left open”\n\n“Forbenius”\n\n“via a private subspace estimation” -> “via private subspace estimation”\n\nAppendix B\n\nProof of proposition B.12 “$Pi_1, Pi_2$ is holds” -> “it holds”\n\nAppendix C.1\n\n“that uses an oracle access” -> “that uses oracle access”\n\n“we obtain that the projection matrices” -> “the projection matrices”\n\n“simply treat the matrices … and compute” -> “simply treats … and computes”\n\nAlgorithm C.1\n\n“Randomly split X intro t” -> “Randomly split X into t”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive and thorough review. Your editorial comments are very helpful and we will address them in the next version. In the following, we would like to respond to specific points you make.\n\nRegarding the weaknesses:\nIn the next version, we will dedicate a few more sentences to clarify the connection between gamma and the other parameters (usefulness, and lambda), and we will try to improve the overview of our lower bounds. \n\nRegarding the question:\nOur implementation has time and space complexities of $\\tilde{O}(dn+dk)$. \nIn our experiments, we use $n = 250\\cdot k$ points, so up to the hidden constant factors, the complexities are $\\tilde{O}(dk)$. Since we focused on large values of $d$, we decided to use small values of $k$ to reduce the total running time (which involved 30 repetitions for each graph point), but there is no problem with using larger values of $k$.\nWe remark that we did not try to optimize the running time. In particular, we did not use the fact that the heavy parts of our algorithm can be parallelized.", "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": "", "extra_scores": {}}, {"review_id": "cOkkvwxNk2", "reviewer": "Reviewer_ivMD", "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.", "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": "I don't see any significant limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper contributed to remove a restrictive assumption in previous works. Previous research on private subspace estimation has derived dimension-independent sample complexity for Gaussian-distributed data with large multiplicative eigen-gaps. This paper removes the Gaussianity assumption, and proves that dimension-independent sample complexity can still be achieved for easier datasets.\n- The proposed measure of \"easiness\" of the datasets for subspace estimation, based on multiplicative eigen-gap, is simple and intuitive. Their derived bounds on sample complexity require prior knowledge of this measure, however, they show that the bounds are hardly affected when this measure is agnostic. \n- The paper has practical relevance due to its realistic assumptions and the inclusion of an implementable algorithm for private subspace estimation.", "weaknesses": "The description of some parameters is vague, which hinders the understanding of the significance of the sample complexity bounds. For example, while $\\lambda$ is an important parameter that appears in the sample complexity bounds, it is not defined in Definition 1.3 or in the text above it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive review. \n\nRegarding your question:\nWe are interested in DP algorithms that have the property that if they get \"easier\" inputs, they achieve \"better\" accuracy. The parameter $\\lambda$ captures the connection between \"easiness\" and \"accuracy\" (i.e., it is a property of the algorithm).  In the setting of subspace estimation, if we aim for an $\\alpha$-useful projection and we have an $\\gamma$-easy dataset, then we would need to use an $\\lambda$-estimator for $\\lambda \\leq \\alpha/\\gamma$.\n\nWe decided to use this parameter since it captures (out of these three parameters) what mostly affects the sample complexities and our upper bounds' design (the number of subsets in the sample and aggregate), and is similar to the recent formulations of Peter et al. 2023. But this is just a matter of taste, and alternatively, we could avoid this parameter and formulate our results with $\\alpha$ and $\\gamma$.", "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": "", "extra_scores": {}}, {"review_id": "4SRV9qjmRM", "reviewer": "Reviewer_RoTv", "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.", "questions": "1. Can your approaches work on real-world datasets?\n2. Can you further improve the gap between upper bounds and lower bounds?", "limitations": "There are some gaps between their upper bounds and lower bounds.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The problem of the paper is well-motivated and the authors give both upper bounds and lower bounds. \n2.They also provide experimental results.\n3. The writing is clear.\n4. The literature review is relatively comprehensive.", "weaknesses": "There are some gaps between their upper bounds and lower bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive review. \n\nRegarding your questions:\n\n1. We made an effort to reduce the constants so that our algorithm can achieve high accuracy using a reasonable amount of points. But as we mentioned in Section 5, our method is only effective for instances that are very close to a low-dimensional subspace, which seems unavoidable in the high dimensional regimes due to our lower bounds. We currently don’t know if interesting real-world datasets, like the gradients during training of large neural networks, have such a strong property that can be exploited for DP. We believe that it is an interesting research direction to understand the connection between the network and input structures to the phenomena of gradients near a low-dimensional subspace (Section 1.1). The work of Gur-Ari et al. [2018] (CoRR abs/1812.04754) makes us optimistic that in some cases it is possible to see this strong property, but we leave this direction for future work. \n\n2. We currently don’t know how to improve the gap between the bounds. We conjecture that our lower bound for strong estimators is tight because it generalizes the tight lower bound of Dwork et al. 2014 which only holds for instances with a multiplicative singular-value gap above some specific constant. Yet, it is important to note that prior to our work, the gap between the lower bound of Dwork et al. 2014 and the upper bound of Singhal and Steinke 2021 was far beyond quantitative because the settings were very different. So we believe that our work, although it left quantitative gaps, makes a significant qualitative step towards understanding this problem better.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)