Efficiently Computing Similarities to Private Datasets
Authors: Arturs Backurs
Zinan Lin
Sepideh Mahabadi
Sandeep Silwal
Jakub Tarnawski
Venue: ICLR 2024 poster (2024)
Keywords: differential privacy
distance estimation
sublinear algorithms
high dimensional data analysis
kernels
Primary area: optimization
TL;DR: We give fast algorithms for computing similarities between a query point and private data, for a wide class of similarity functions such as kernels and distances.

Abstract: Many methods in differentially private model training rely on computing the similarity between a query point (such as public or synthetic data) and private data. We abstract out this common subroutine and study the following fundamental algorithmic problem: Given a similarity function $f$ and a large high-dimensional private dataset $X \subset \mathbb{R}^d$, output a differentially private (DP) data-structure which approximates $\sum_{x \in X} f(x,y)$ for any query $y$. We consider the cases where $f$ is a kernel function, such as $f(x,y) = e^{-\|x-y\|_2^2/\sigma^2}$ (also known as DP kernel density estimation), or a distance function such as $f(x,y) = \|x-y\|_2$, among others. 
    
Our theoretical results improve upon prior work and give better privacy-utility trade-offs as well as faster query times for a wide range of kernels and distance functions. The unifying approach behind our results is leveraging `low-dimensional structures' present in the specific functions $f$ that we study, using tools such as provable dimensionality reduction, approximation theory, and one-dimensional decomposition of the functions. Our algorithms empirically exhibit improved query times and accuracy over prior state of the art. We also present an application to DP classification. Our experiments demonstrate that the simple methodology of classifying based on average similarity is orders of magnitude faster than prior DP-SGD based approaches for comparable accuracy.

Published as a conference paper at ICLR 2024
EFFICIENTLY COMPUTING SIMILARITIES TO PRIVATE DATASETS
Arturs Backurs
Zinan Lin
Sepideh Mahabadi
Microsoft Research
Microsoft Research nan1 in@mi crosoft.com
Microsoft Research
arturs. backurs@gmai com
mahabadi @tti ededu
Sandeep Silwal
Jakub Tarnawski
MIT si silwal @mit edu
Microsoft Research jakub. wwwrawsskimmirrsseee.ooooo
ABSTRACT
Many methods in differentially private model training rely computing the sim- ilarity between a query point (such as public or synthetic data) and private data. We abstract out this common subroutine and study the following fundamental al- gorithmic problem: Given similarity function f and a large high-dimensional private dataset X C Rd, output differentially private (DP) data structure which approximates Exex x f(x,, y) for any query We consider the cases where ʃ is a kernel function, such as fx. y) = e- -==-v////0" (also known as DP kernel density estimation), or distance function such as f(z y) = || yl12. among others. Our theoretical results improve upon prior work and give better privacy-utilii trade-offs as well as faster query times for a wide range kernels and dis- tance functions. The unifying approach behind our results is leveraging 'low- dimensional structures' present in the specific functions f that we study, using tools such provable dimensionality reduction, approximation theory, and one- dimensional decomposition of the functions. Our algorithms empirically exhibit improved query times and accuracy over prior state of the art. We also present an application to DP classification. Our experiments demonstrate that the simple methodology of classifying based on average similarity is orders of magnitude faster than prior DP-SGD based approaches for comparable accuracy.
INTRODUCTION
evident that privacy is an important and often non-negotiable requirement in machine learning pipelines. In response, the rigorous framework of differential privacy (DP) has been adopted as the de-facto standard for understanding and alleviating privacy concerns (Dwork et al., 2006). This is increasingly relevant non-private ML models have been shown to profusely leak sensitive user information (Fredrikson et al., 2015: Carlini et al., 2019; Chen et al., 2020a; Carlini et al., 2021; 2022: 2023a; Haim et al., 2022: Tramèr al., 2022: Carlini al., 2023b). Many methodologies have been proposed in hopes of balancing DP requirements with retaining good downstream performance of ML models. Examples include generating public synthetic data closely resembling the private dataset at hand (and training on it) (Lin et al., 2020; Li et al., 2021; Yu et al., 2021; Yin et al., 2022: Yue et al., 2022: Lin et al., 2023). or selecting similar public examples for pre-training ML models (Hou et al., 2023; Yu et al., 2023). Furthermore, in the popular DP-SGD method, it is also widely understood that the use of public data bearing similarity to private datasets vastly improves downstream performance (Yu et al., 2020; 2021; Yin et al., 2022; Li et al., 2021; De et al., 2022). To list some concrete examples, Hou et al. (2023) use a variant of the Fréchet distance to compute similarities of private and public data, Yu et al. (2023) use trained ML model to compute the similarity between public and private data, and Lin et al. (2023) use a voting scheme based on the l2 distances between (embeddings of) private and synthetic data to select synthetic representatives.
Common among such works is the need to compute similarities to a private dataset. While this is explicit in examples such as (Hou et al., 2023; Yu al., 2023; Lin et al., 2023), it is also implicit in

---

Published as a conference paper at ICLR 2024
many other works which employ the inductive bias that pre-training on similar public data leads to better DP model performance (Yu et al., 2020; Li et al., 2021; De et al., 2022; Yin et al., 2022).
We study the abstraction of this key subroutine and consider the following fundamental algorithmic problem: given a private dataset X C R and a similarity function f(x, y) Rd x IF + R. such as kernel distance function, output a private data structure Dx .Rd - R which approximates the map y -> Evex x f(x, y). We additionally require that Dx be always private with respect to X, regardless of the number of times it is queried. This problem has garnered much recent interest due to its strong motivation (Hall et al., 2013; Huang & Roth, 2014; Wang et al., 2016; Aldà & Rubinstein, 2017: Coleman & Shrivastava, 2021: Wagner al., 2023). It is a meaningful abstrac- tion since similarities between (neural network based) embeddings can meaningfully represent rich relationships between objects such as images or text (Radford et al., 2021). Indeed, beyond training private models, there is additional motivation from performing downstream tasks such as private classification or clustering, where a natural methodology is to classify query as the class which has the highest similarity to.
In addition to the privacy angle, computing similarity to a dataset is a fundamental and well-studied problem in its own right. In the case where f is a kernel such as f(x, v) e-ll=-vila//", this is known kernel density estimation (KDE), whose non-private setting has been extensively studied (Backurs et al., 2018; 2019; Charikar et al., 2020; Bakshi et al.. 2022), with many applications in machine learning; see (Schölkopf et al., 2002: Shawe-Taylor al., 2004; Hofmann et al., 2008) for comprehensive overview. In the case where f is a distance function, the sum represents the objective of various clustering formulations, such as k-means and k-median.
1.1
OUR RESULTS
The aforementioned works have produced non-trivial utility-privacy trade-offs for computing sim- ilarities privately for a wide class of f. On the theoretical side, we improve upon these results by giving faster algorithms and improved utility-privacy trade-offs for wide range of kernels and distance functions. We also study utility lower bounds in order to understand the inherent algorith- mie limitations for such problems. Our algorithms are also validated practically; they demonstrate empirical improvements over baselines, both in terms of accuracy and query time.
Definitions. We wish design differentially private algorithms (see Definition A.I for a DP primer) under the following natural and standard notion: datasets X, X' are neighboring if they differ on single data point. We also work under the function release model; the data structure we output must handle arbitrarily many queries without privacy loss.
Function release. Given private dataset X and public function f. we wish to release a differ- entially private (DP) data structure capable of answering either kernel density estimation (KDE) or distance queries. We focus on the function release model as Wagner et al. (2023) and employ their definition: the algorithm designer releases description of a data structure D which itself is private (i.e. D the output of private mechanism as per Definition A. A client can later use D to compute D(y) for any query y. Since D itself satisfies e-DP, it can support arbitrary number of queries without privacy loss. This is motivated by scenarios such as synthetic data generation, or when do not have pre-specified number of queries known upfront. Our accuracy guarantees are also stated similarly as in Wagner et al. (2023): we bound the error for any fixed query y. Thus, while our outputs are always private (since D itself is private), some query outputs can be inaccurate.
Our private dataset is denoted as X C Rd, with |X| = n. The similarities are computed with respect public function ʃ Rdd Rd - R. We define distance queries (for distance functions such as ||æ - -Vll) and KDE queries (for kernel functions such as f(x. y) -1l-==))1 as follows:
Definition 1.1 (Distance Query). Let f be distance function. Given query y E Rd, a distance query computes an approximation to Enex f(x, y).
Definition 1.2 (KDE Query). Let f be a kernel function. Given a query y E Rd, a KDE query computes an approximation [x Enex (x,
The normalization by |X| = n is inconsequential; we follow prior convention for KDE queries. For distance queries, the un-normalized version seemed more natural to us.
2

---

Published as a conference paper at ICLR 2024
Type
f
Thm.
Our Error
Prior Error
Our Query Time
Prior Query Time
| 111
B.3
d 1 + O2 Eva
1.
nd 82
1/3
d
Distance
1/17
I| y11
D.2
a Eal.6)
d
2
Queries
| v
D.5
(1,
d
|
D.4
0 eva
d
1z-vlla
E.1
(1)
(1,
d
d
1
E.1
(1,
(1,a)
d
KDE
F.I
(1,
d
I+ 2 2
Queries
1 1+
F.1
(1,
(1,a)
d
|| v
F.1 (1,
1+ | 1-ll-ll 1
Table 1: Summary of the e-DP upper bounds. See Definition 1.3 for the enror notation. For clarity, suppress all logarithmic factors. The KDE bounds assume that 2 Q (2zz). The distance query bounds are stated for points bounded radius. The prior distance query results are due to Huang & Roth (2014), and the prior KDE results are due to Wagner al. (2023).
Discussion of Theoretical Results. The main trade-off that we are interested in is between privacy, measured with respect to the standard DP definition (Definition 1) and accuracy of our answers, also called utility. For example, a data structure which always returns a fixed answer, such as 42, clearly always private regardless of the number of queries performed, but is highly inaccurate. Thus, our goal is to obtain non-trivial accuracy guarantees while respecting privacy. Secondary, but important, concerns are query time and data structure construction time and space. Our main theoretical results are summarized in Table 1, where we use the following error notation.
Definition 1.3 (Error Notation). For a fixed query, if Z represents the value output by our private data structure and 7' represents the true value, we say that 7. has error (M, A) for M > and A Z 0 if - 2' < (M - 1) + A. That is, we have relative error M - and additive error A. The expectation is over the randomness used by our data structure.
We want M to be close to and the additive error A to be as small as possible. Table shows our errors and query times, as well as those of the most relevant prior works. See Section for technical overview of how we obtain these results.
For distance queries, the most relevant work Huang & Roth (2014). They considered the & and & functions and obtained additive errors with large dependence on (dataset size) and d (dimension); see Table In contrast, we show that we allow for a small multiplicative error (e.g. a = 0.001 in obtain additive
Table 1),
with improved dependence d and dependence
Theorem 1.1 (Informal; see Theorem B.3 and Corollary D.2). Suppose the data points have bounded diameter in l,. For any a E (0, and O, there exists an algorithm which outputs an E-DP data structure 'D capable of answering any e distance query with (1 a,
a
error.
EVVo
For the lg case, where the points have bounded &g diameter, we obtain error (1 (1+ a, (
Our approach is fundamentally different, and much simpler, than that of Huang & Roth (2014), who used powerful black-box online learning results to approximate the sum distances. Furthermore, given that think of the largest parameter, incur much smaller additive error. Our simpler approach also demonstrates superior empirical performance as discussed shortly. Our & upper bounds complemented with lower bound stating that any s-DP algorithm supporting e distance queries for private datasets in the box [0, Rijd must incur Ω ((Rd/s) error.
3

---

Published as a conference paper at ICLR 2024
Theorem 1.2 (Informal; Theorem C.2). Any c-DP data structure which answers & distance queries with additive error at most T for any query must satisfy T (2(Rd/s).
Note that our lower bound only pertains to additive error and does not say anything about multi- plicative error. It is an interesting direction to determine if multiplicative factors are also necessary. We also obtain results for other functions related to distances, such as f% see Appendix D.
We now discuss our kernel results. For the Gaussian (e (e-1l=-vllā), exponential (E (e=ll==vlla),, and Cauchy ( (1+1l=-111)) kernels, we parameterize our runtimes in terms of additive error Here, obtain query times of Ö(d + 1/a²) whereas prior work (Wagner et al., 2023) requires O(d/a²) query time. Thus our results are faster in high- -ighedimensio regimes where d > 1/a².
Theorem 1.3 (Informal: see Theorems E. and F.I), Consider the Gaussian, exponential, and Cauchy kernels. In each case, for any ε > 0 and a (0, 1), there exists an algorithm which oulputs an E-DP data structure that answers KDE queries with error (1, a) and query times O(d + 1/a²).
For kernels 1+|2--vlaa and 1+ 1 we obtain the first private data structures; see Table 1. We do this via black-box reduction to other kernels that already have private data structure constructions, using tools from function approximation theory; this is elaborated more in Section 2. All KDE results, including prior work, assume that n is lower- bounded by some function of a and e. These two kernels and the Cauchy kemee fall under the family of smooth kernels (Backurs et al., 2018).
We also give faster query times for the non-prite privariv setting for the Gaussian, exponential, and Cauchy KDEs. Interestingly, our improvements for the non-private setting use tools designed for our private data structures and are faster in the large d regime.
Theorem 1.4 (Informal; see Theorem G.1). For the Gaussian kernel, we improve prior run- & ning time for computing a non-private KDE query with additive error a from Ô (2 to Ô (d (721))00))) Similarly for the exponential kernel, the improvement in the query time is from Ô (22,0) to Ô (d 2.22--0)) The preprocessing time of both algorithms is asymptot- ically the same as in prior works.
Discussion of Empirical Results. Our experimental results are given in Section 4. We consider three experiments which are representative of our main results. The first setting demonstrates that our E query algorithm is superior to prior state of the art (Huang & Roth, 2014) for accurately answering distance queries. The error of our algorithm smoothly decreases as increases, but their algorithms always return the trivial estimate of O. This is due to the fact that the constants used in their theorem are too large to be practically useful. We also demonstrate that our novel dimension- ality reduction results can be applied black-box in conjunction with any prior DP-KDE algorithm, leading to savings in both data structure construction time and query time, while introducing negli- gible additional error.
Lastly, we explore an application to DP classification on the CIFAR-IO 10 dataset. The standard setup is to train a private classification model on the training split (viewed as the private dataset), with the goal of accurately classifying the test split (Yu et al., 2020; De et al., 2022). Our methodology is simple, fast, and does not require a GPU: we simply instantiate a private similarity data structure for each class and assign any query to the class which it has the highest similarity to (or smallest distance if is distance). We set be lg since it has arguably the simplest algorithm. In contrast to prior works, our methodology involves no DP-SGD training. For comparable accuracy, we use > 3 orders of magnitude less runtime compared to prior baselines (Yu et al., 2020; De al., 2022).
TECHNICAL OVERVIEW
At a high level, all of our upper bounds crucially exploit fundamental 'low-dimensionality struc- tures' present in the f's that we consider. For different f's, we exploit different 'low-dimensional" properties, elaborated below, which are tailored to the specific f at hand. However, we emphasize that the viewpoint of low-dimensionality" is the extremely versatile tool driving all of our algorith- mic work. We provide the following insights into the low-dimensional properties used in our upper bounds.
4

---

Published as a conference paper at ICLR 2024
Distance Queries via One-dimensional Decompositions. For the f distance function, our im- provements are obtained by reducing to the one dieeeinnsioona case. To be more precise, we use the well-known property that ΣzEx || vll = Σラ Ezex [x; Wjl- In other words, the sum of & distances decomposes into d one-dimensions sums (this is also true for other related functions such as fg) This explicit -ow-iimesioonal representation offers concrete avenue for algorithm de- sign: we create a differentially private data structure for each of the d one-dimensional projections of the dataset. In one dimension, we can employ many classic and efficient data structure tools. Furthermore, using metric embedding theory (Theorem 1)1),, we can also embed l2 into & using an oblivious map, meaning that any algorithmic result for & implies similar results for &g as well.
Kernels via New Dimensionality Reduction Results. For kernels such as Gaussian, exponential, and Cauchy, we obtain novel dimensionality reduction results. Our results show that KDE values are preserved if we project both the dataset and the queries to a suitably low dimension via an oblivious, data-independent linear map. Our dimensionality reduction schemes are automatically privacy-respecting: releasing an oblivious, data-independent matrix leaks no privacy. Our results also have implications for non-private KDE queries and give new state-of-the- art query times.
To obtain our new dimensionality reduction bounds, we analyze for preserving sums of kernel values. The main challenge is that kernel functions are non-linear functions of distances, and preserving distances (as JI. guarantees) does not necessarily imply that non-linear funetions of them are preserved. Furthermore, JL-style guarantees may not even be true. JL guarantees that distances are preserved up to relative error when projecting to approximately Olog v.) dimensions (Johnson & Lindenstrauss, 1984), but this is not possible for the kernel values: if | Ull2 is extremely large, then after applying a JL projection G, |Gz Gyllz can differ from || - y/1 by large additive factor A (even if the relative error is small) with constant probability, and thus e (Ga--yyla
(JL) matri-
A. ||æ-y la does not approximate -|l-~vlla up to relative error.
We overcome these issues in our analysis by noting that we do not require a relative error approx- imation! Even non-private KDE data structures (such as those in Table 2) already incur additive errors. This motivates proving additive error approximation results, where the additive error from dimensionality reduction is comparable to the additive error incurred by existing non-private KDE data structures. We accomplish this via a careful analysis of the non-linear kernel functions and show that is possible to project onto a constant dimension, depending on the additive error, which is independent of the original dataset size
original dimensionality d.
Theorem 2.1 (Informal; see Theorems E.2 and F.2). Consider the Gaussian and exponential ker- nels. For any E (0, 1), projecting the dataset and query Ó(1/a²) dimensions using obliv- ious JL map preserves the KDE value up to additive error a. For the Cauchy kernel, projecting to O(1/a²) dimensions preserves the KDE value up multiplicative 1 + factor.
We note that variants of 'dimensionality reduction" have been studied for Gaussian kernels, most notably via coresets which reduce the dataset size (one can then correspondingly reduce the dimen- sion by projecting onto the data span; see Luo et al. (2023); Phillips & Tai (2020)). However, these coresets are data-dependent and it is not clear if they respect DP guarantees. On the other hand, our results use random matrices that do not leak privacy. Lastly, our analysis also sheds additional light on the power of randomized dimensionality reduction beyond JL for structured problems, comple- menting long line of recent works (Boutsidis al., 2010; Cohen et al., 2015; Becchetti al., 2019; Makarychev et al., 2019; Narayanan et al., 2021; Izzo et al., 2021; Charikar & Waingarten, 2022).
Smooth Kernels via Function Approximation Theory. For DP-KDE, we also exploit low- dimensional structures via function approximation, by approximating kernels such as I+ in terms of exponential functions. To be more precise, for h( y) = ||x- - ylll, || - - and | v/I,, Corollary 3.2 allows us to express 1+h(r,y) ~ ΣSEJ (t(..v)) for explicit parameters ty, my.- The corollary follows from modification of results in approximation theory, see Section 3. This can be viewed as projecting the kernel onto a low-dimensional span of exponential functions, since only |J] = O(1) terms in the sum are required. We can then benefit from already existing KDE data structures for various kernels involving exponential functions, such as the exponential kemel!! Hence, we obtain new private KDE queries for host of new functions in a black-box manner. The fact that [J] (the number of terms in the sum) is small is crucial, instantiating a differentially
5

---

Published as a conference paper at ICLR 2024
private KDE data structure for each E [J] does not substantially degrade the privacy guarantees or construction and query times. This reduction is detailed in Section 3.
Outline of the Paper. Due space constraints, only the function approximation theory reduction is presented the main body in Section 3. The rest of our theoretical results is deferred to the appendix with full proofs. In Section 4, we empirically verify our upper bound algorithms and give applications to private classification. Our & algorithm in one dimension is in Section B. It contains the main ideas for the high-dimensional & algorithm, given in Appendix B.I. Appendix states our lower bounds for the & distance function. Applications of our & upper bound, such as for &g and fg. are given Appendix D, and improved DP bounds for the exponential and Gaussian kernels are given in Appendix E. Appendix F contains improved DP results for smooth kernels (such Cauchy kernels). Appendix G contains our improved KDE query bounds in the non- non-private setting.
Related Work. We use the standard definition of differential privacy (Dwork et al., 2006), given in Definition A.1. We survey the most relevant prior works. Additional related works are given in Section A.2. We write guarantees in terms of the expected error for any fixed query. These algorithms, and ours, can easily be converted to high-probability results by taking the median of multiple (logarithmically many) independent copies. The theorem statement below pertains to the distance functions ||æ vll1. It is stated for the case where all the dataset points and queries are in the box (0, 1]s, but easily extend to a larger domain by scaling.
Theorem 2.2 (Huang & Roth (2014)), Assume the dataset and query points are contained in [0, 1]d. There exists an algorithm which outputs an E-DP data structure for the function || - yll with the following properties: (1) the expected additive error is Ô
(2) the construction time is n7 23/33 ),
e273
O
(3) the space usage is O
2//322/3 d:/3
(4) and the query time is O(d).
(Huang Roth, 2014) also obtained results for & with additive errors containing factors of n and d shown in Table I; see Appendix A.2 for the formal statement of their results. The result of Wagner et al. (2023) concerns private KDE constructions for the exponential (e (e-1lz-vll llz-,,ll),, Gaussian (e- (e=1l==v1l)), and Laplace (e (e- -==-vlll kernels.
Theorem 2.3 (Wagner et al. (2023)). Let a E (0,1) and suppose n 2 (2)). For h(x, || - y/12. || v112. or | yll,. there exists an algorithm which outputs an E-DP data structure for f(x y) = e - k(ma)) with the following properties: (1) the expected additive error is at most a,
(2) the query time is (.)) ), the construction time is O ud and the space usage is O (1)).
Earlier works also study or imply DP KDE. The results of Wagner et al. (2023) were shown to be superior, thus we only explicitly compare to Wagner et al. (2023); see Appendix A.2.
SPARSE FUNCTION APPROXIMATION
We provide details on the function approximation theory used in Section F to obtain our results on smooth kernels. We use the fact that small number of exponential sums can approximate smooth kernels, enabling to reduce this case to prior kernels in Section E. First we recall a classic result.
Theorem 3.1 (Sachdeva & Vishnoi (2014)). Given e, 8 (0, 1). there exist ((log(1/(e-/))
positive
numbers Wjj > 0, all bounded by O =log(1/05 such that for all x E [s, 1] we have (1 6)x=11
Σ, wye 4 < (1 + 6)x Furthermore, |uye b/| - (1)) for all j.
The theorem implies the following useful corollary, proved in Appendix F.2. Corollary 3.2. Given E (0, 1). there exist ((log(1 1 /a)) positive numbers wj. tt > 0, all bounded by [oy() such that for all x 2 we have E, wye typ x
S a.
'Throughout the paper, Ô hides logarithmic factors in and d.

---

Published as a conference paper at ICLR 2024
obtain private KDE data structures for the kernels f(z, y) Using Corollary 3.2, 1 via a black-box reduction to the corresponding private KDE data 1+ I+la-vlla" 1+| 1+]l--wll structures for the kernels e vll-vlll,, e -elll- and e-1=~
Theorem 3.3. Let h(z, y) = -|-- - y || - yll2. or ||z y and a E (0, 1). Suppose there exists an algorithm.for for constructing an s-DP KDE data structure for the kernel e h(2.9) on a given dataset of size n which answers any query with expected additive evvor a, takes C(,, o:) construction time, Qn, a) query time, and S(n, a) space, assuming Z L(e,)).
Then, there exists an E-DP data structure for answering KDE queries for (xxy)) 1+h(a.s) which answers any query with expected additive error a and the same construction, query, and space as the exponential case, but with n replaced by On log(1/a)) and a replaced by a/ 1oo(1//) in the functions C, Q S. and L.
Proof. We give a reduction showing how (a small collection of) private KDE data structures for the kernel e -h((z)) can be used answer KDE queries for f(z, y) I T+h(a.0) Let g(z) be the
function guaranteed by Corollary 3.2 which approximates 1/2 by an additive factor for all x 2 1:
Σ Wje -, -1 S ((a) 2/2 2 1. We have
g(*)
1
Σ
f(x,8)=
1
Σ xE
Σ #EX
ΣΣ
Σ
wye ((--(()))))) +O(a)
X
=
[X]
+ k(x,))
[
REX
]
Σ wje to
+0(a)=
Σ
Wje
e ((xr))))
+ +
zEX;
where X, is the dataset X, U4 x E X) and yy is the query 1n y in the cases that h(r,y) || y/11 || yl12. In the case where h(x, y) | vll2 we have X, = (Vty x X and Vy is the query Vtz y.
Note that the function g is public the parameters wy and tú publicly known (and do not depend on the dataset). Now we simply instantiate private KDE data structures which approximate each of the sums μX ExEx, eh((z.)) More specifically, we release (log(L/aa) kernel KDE data struc- tures, one for each Xj. and each of which is O log(1 log(1/a)) --D) Then the overall data structures we release are E-DP by composition. Furthermore, since each w + = O(1) and there are only (loo([//a) of these terms, if each data structure has expected additive error ((a/ log(1/a)), then the overall error is (a)) as well. To summarize, the logarithmic blowup happens in the query/space, assumption the size of the dataset.
as well any
4 EMPIRICAL EVALUATION
We evaluate our algorithms synthetic and real datasets. We consider three experimental settings which together are representative of our main upper-bound results. We show the average of 20 trials and +1 standard deviation is shaded where appropriate. All experiments unless stated otherwise are implemented in Python 3.9 on an MI MacbookPro with 32GB of RAM.
yl for a one dimensional dataset X of size n = 103, with points randomly picked in 1]. The query points O(n) evenly spaced points in 1]. We implement our one-dimensional ε distance query algorithm and compare to the prior baseline of (Huang & Roth, 2014). Both our and (Huang & Roth, 2014)'s high-dimensional algorithms are constructed by instantiating d different copies of one-dimensiome data structures (on the standard coordinates ). Thus, the performance in one dimension is directly correlated with the high-dimensional case. In our case, the map we wish to approximate converges to for Jx - yl dx = y² y + 1/2 for y E [o, 1]. allowing us to easily compare to the ground truth. In Figure 1a, we plot the average relative error across all queries as
4 Experiments. The task here is to approximate the (normalized) map y - 1
x |x -
7

---

Published as a conference paper at ICLR 2024
function of The explicit parameter settings for the algorithm given in (Huang & Roth, 2014) are extremely large in practice, meaning the output of their algorithm was always the identically function, which gives relative error equal to (the distance query was always estimated to be 0) for the values of & tested, as shown in Figure la. On the other hand, our algorithm gives non-trivial empirical performance and its error decreases smoothly output values (scaled by 1 1/n) for various E's. We can observe that our estimates converge to the true function E increases. We observed qualitatively similar results for for 10 well.
increases. Indeed, Figure 1b shows
4 Distance Query
1.6
1.4
Ours [HR14]
Relative Error
1.2
1.0
0.8
6-7
0.6
0.50
Our Alp Trum
0.2
1.30
0.0
0
1
4
5
0.6
02
04
0.6
0.
10
20
02
24
16
0.5
16
(b) Our performance for various fixed E.
(a) Our relative error decreases increases.
Figure/ I: Our algorithm for & queries has smaller error than prior SOTA of (Huang & Roth, 2014).
Dimensionality Reduction Experiments. We empirically demonstrate that dimensionality reduc- tion provides computational savings for DP-KDE without significantly degrading accuracy. Our task approximate KDE values for the Gaussian kernel -12-- We compare against the prior SOTA (Wagner et al., 2023). Our provable dimensionality reduction result of Theorem F.2 gives a general framework: apply an oblivious dimensionality reduction the data and use any DP-KDE al- gorithm in the projected space. Indeed, Theorem E. follows by applying the framework to the prior SOTA algorithm of Wagner al. (2023). Thus in our experiment, we use the randomized dimension reduction of Theorem E.2 in conjunction with the implementation of Wagner et al. (2023). Note that while we fix the DP-KDE implementation used after dimensionality reduction, our framework is compatible with any other choice and we expect qualitatively similar results with other choices.
Our dataset consists of embeddings CIFAR-10 in dimension 2048, computed from an Inception- v3 model (Szegedy et al., 2016), pre-trained on ImageNet (Deng et al., 2009). Obtaining embeddings of private datasets from pre-trained ML models is standard in the applied DP literature (Yu et al., 2020; De et al., 2022). The intuition is that the embeddings from the network are powerful enough to faithfully represent the images in Euclidean space, so computing kernel values on these features meaningful. We project the embeddings to lower dimensions d ranging from 200 to 2000. We use the training points of a fixed label as the private dataset and the corresponding test set as the queries.
Figure 2a shows the relative error of our approach (in blue) and the baseline of Wagner et al. (2023) (in orange) which does not use any dimensionality reduction. The relative errors of both are com- puted by comparing the ground truth. Figure 2b shows the construction time of the private data structure and Figure 2c shows the total query time on the test points. We see that the relative error smoothly decreases as we project more dimensions, while construction and query time smoothly increase. Note the construction time includes the time to compute the projection. For example, projecting d 1000 increases the relative eттor by 0.015 in absolute terms, while reducing the construction time by x 2x and reducing the construction time by factor of > 4x.
Differentially Private Classification. We consider the DP classification task on Cif The train and test splits are the private data and query respectively, and the task is to train private classifier on the train set to classify the test set. Our methodology is extremely simple, fast, and does not require any specialized hardware like GPUs: we instantiate (z, 8D distance query data structure on each class. The classes disjointly partition the data so the output, which is an (e, DDP data structure for each class, is overall (c, 0)-P (Ponomareva et al., 2023). We use
8

---

Published as a conference paper at ICLR 2024
Gaussian KDE
Gaussian KDE
Gaussian KDE
0.14
Relative Errar
Projection
No Projection
Construction Time
1.50
Relative Error
(g)
0.4
1.25
0.10
time
Query
0.75
Projection
0.2
0.50
0.04
0.00
Projected 1258
250
sas 1928 186
Projected Dimension
Projected Dimension
(a) Proj. dimension relative error
(b) Construction time
(c) Total query time
Figure 2: Results for our dimensionality reduction experiments.
f(r,0) 1-1--vyl since has the simplest algorithm (see Section D.I). It essentially reduces to releasing noisy mean for every class. To classify query, assign it to the class whose (noisy) mean is closest to the query. For other potential choices of f like kernels, one would instead assign to the class with the highest KDE value. There are two competing SOTA works: one from Deepmind (De et al., 2022) and (Yu et al., 2020). We give a high-level methodology of prior works (see Appendix H for more details): they start with pre-trained model on ImageNet and fine tune using DP- DP-gradient descent/SGD. Their specific model details are given in Appendix H. Note that the vectors we build our private data structures ResNet pre-trained model used in Yu et al. (2020). Thus, all methods have the access to the same "pre-training' information.
the penultimate layer embeddings of the
Let us temporarily ignore ō for simplicity of discus- sion. If they use steps of training, every model up- date step approximately satisfies e/VT privacy (ex- act bounds depend on the DP composition formulas), ensuring the overall final model (e, dD. Thus, every step for them incurs some privacy budget, with
CIFARIO, 5 10-5
0.9
orders magnitade
0.8
Accuract
0.7
the benefit of increased accuracy. Therefore, these
0.6
works can stop training at intermediate times to ob- tain a model with stronger privacy guarantees (lower
0.5
0.4
E), but worse accuracy. However, the same proce- dure also gives an accuracy vs model training time trade-off for these prior works. This is shown in Fig- ure 3. The right most endpoints of both baselines (the largest times), correspond to models with ε In other words, their models with the worst privacy guarantees has the highest accuracy, while also re- quiring the longest training time.
0.3
Yo el al.
0.2
Deepmind
102
10
10
105
10
'10"
Time (ms)
Figure 3: Runtime Accuracy.
In contrast, our algorithm of Section D.1 simply re- leases a noisy collection of fixed vectors. Our data structure construction time, which corresponds their model training time, is independent of (c, 5) (but accuracy depends on them). Figure 3, 1 (we use the best hyper-parameter choices for
plot the accuracy of our data structure for all methods). For other values e, we would simply incur the same construction time, but observe differing accuracy since the construction time is independent of (but again accuracy improves for higher E). The time to initialize our data structure (for all classes) is 28.8 ms on a CPU, and the query time for all queries was 73.8 ms. On the other hand, fully training the model of Yu et al. (2020) up to & = takes > 8.5 hours on a single NVIDIA RTX A6000 GPU. The runtimes of De al. (2022) are private data structure is orders of magnitude faster than the time to create models of corre- sponding accuracy via the two baselines. Note that we are also using arguably inferior hardware. The best accuracy of all methods as a function of e, ignoring run-time considerations, is shown in Figure 4.
longer since they larger models. Thus, shown in Figure 3, creating
Thhe works consider other alternate datasets, but only compare to the Imagenet case. We expect quali- tatively similar results when pre-training with other datasets.

---

Published as a conference paper at ICLR 2024
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Nir Ailon and Bernard Chazelle. The fast -indnssnniiddestraasss transform and approximate nearest neighbors. SIAM J. Comput., 39(1):00--32,, 2009. doi: 10.1137/06067309. URL https:
//doi. orooorggooo.oo 10. 1137 113370006730955
Francesco Aldà and Benjamin I. P. Rubinstein. The bernstein mechanism: Function release under differential privacy. In Satinder Singh and Shaul Markovitch (eds.), Proceedings of the Thirty- First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pp. 1705-1711, AAAI Press, 2017. doi: 10. 10.1609/aaii.v33 100844 URL httht://dddi. org/10. 609 wwa.avaiiviv...................a v.1.1. 10884.
Arturs Backurs, Moses Charikar, Piotr Indyk, and Paris Siminelakis. Efficient density evaluation for smooth kernels. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 615 2018.
Arturs Backurs, Piotr Indyk, and Tal Wagner. Space and time efficient kernel density estimation in high dimensions. In Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurlPS, pp. 15773-15782, 2019.
Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, and Samson Zhou. Subquadratic algorithms for kernel matrices via kernel density estimation. In The Eleventh International Con- ference on Learning Representations, 2022.
Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the johnson lindenssrasssss lemma. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp- 1039-1050, 2019.
Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine learning. 94:401-437, 2014.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The johnson-lindenstrruss transform itself preserves differential privacy. In 53rd Annual IEEE Symposium on Foundations of Com- puter Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pp. 410 IEEE Computer Society, 2012. doi: 10. 101//FOCS.2012..77 URL httpt / doi. org 10. 10.19999//111/////// FOCS. 2012. 67.
Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. ACM, 6012):12:1-12:22 2013. doi: 10.1145/4550422255114.. URL https:// doi
Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. Random projections for k-means clus- tering. Advances in neural information processing systems, 23, 2010.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19), pp. 267-284, 2019.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pp- 2633-2650, 2021.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Mem- bership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1997-1914. IEEE, 2022.
10

---

Published as a conference paper at ICLR 2024
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. International Conference on Learning Representations, 2023a.
Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle. Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 5253-5270, 2023b.
Moses Charikar and Erik Waingarten. The oohnson-lindenstrauss lemma for clustering and subspace approximation: From coresets dimension reduction. CoRR, abs/2205 00031,, 2022. doi: 10. 48550MarXiv.2205.00 000771.1..........11011 URL https: / /doi. org /10. 48550 /1//550//Xiv arxiv. 2205. 00371.
Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estima- tion through density constrained near neighbor search. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 172-183, 2020.
Dingfan Chen, Ning Yu, Yang Zhang, and Mario Fritz. Gan-leaks: A taxonomy of membership inference attacks against generative models. In Proceedings of the 2020 ACM SIGSAC conference computer and communications security, pp. 343-362, 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning, pp. 1597-1607. PMLR, 2020b.
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimen- sionality reduction for k-means clustering and low rank approximation. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 163-172, 2015.
Benjamin Coleman and Anshumali Shrivastava. A one-pass distributed and private sketch for kernel sums with applications to machine learning at scale. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pp. 3252-32222 3265, 2021.
Soham De. Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. lece, 2009.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284. Springer, 2006.
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pp. 51-60. TEFE Computer Society, 2010. doi: 10.1109/FOCS. 2010.12. URL https:: /tte:://doi.oo org 10. 1 11119110000111 2010.12 12.
Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 361-370, 2009.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC confer- ence on computer and communications security, pp. 1322 1333, 2015.
Anupam Gupta, Aaron Roth, and Jonathan R. Ullman. Iterative constructions and private data lease. In Ronald Cramer (ed.), Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, volume 7194 of Lecture
Notes in Computer Science, pp. 339-356. Springer, 2012. doi: 10. 1007//088-3-649 21442222944-- 18914-9) 19.
URL https::////./.......t /doii .org 1000.000.0000 --------12----9999---

---

Published as a conference paper at ICLR 2024
Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. Advances in Neural Information Processing Systems, 35:22911- 22924, 2022.
Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and func- tional data. The Journal of Machine Learning Research, 14(1):703-727. 2013. 2013.
Moritz. Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 705-714, 2010.
Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. Kernel methods in machine learn- ing. The annals of statistics, 36(3):111--1200, 2008.
Charlie Hou, Hongyuan Zhan, Akshat Shrivastava, Sid Wang, Aleksandr Livshits, Giulia Fanti, and Daniel Lazar. Privately customizing prefinetuning to better match user data in federated learning. In ICLR 2023 Workshop on Pitfalls of limited data and computation for Trustworthy ML, 2023.
Zhiyi Huang and Aaron Roth. Exploiting metrie structure for efficient private query release. In Chandra Chekuri (ed.), Proceedings of the Twenty- Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 523-534. SIAM, 2014. doi: 00.1137/1.7781111 1973401293 URL https::t///// //oss://doo.eee 1011//0110001111111///111 1137/1. 9781611973402.1
Piotr Indyk and Assaf Naor. Nennsstneighhoo-prreevvnngg embeddings. ACM Transactions on Algo- rithms (TALGG), 3-3) 2007.
Piotr Indyk and Sandeep Silwal. Faster linear algebra for distance matrices. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neu- ral Information Processing Systems, volume 35, pp. 35576-35589, Curran Associates, Inc., http://ppooeednnnn.eeeeeeeeeeeee neurips. ec /ttccc///aaeee patpe__filespppper///a// 2022. URL HllcETT9Sc4000333444441172222223 orr.rr/e7eeeeaaaaaaee-----rrreer
Zachary Izzo, Sandeep Silwal, and Samson Zhou Dimensionality reduction for wasserstein barycenter. Advances in neural information processing systems, 34:15582-15594, 2021.
W. Johnson and J. Lindenstrauss. Extensions of lipschitz maps into hilbert space. Contemporary Mathematics, 26: 01 1984. doi: 10. 0011090/comm/00677774000.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference Learning Representations, 2021.
Zinan Lin, Alankar Jain, Chen Wang, Giulia Fanti, and Vyas Sekar. Using gans for sharing net- worked time series data: Challenges, initial promise, and open questions. In Proceedings of the ACM Internet Measurement Conference, pp. 464-483, 2020.
Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin. Differentially private synthetic data via foundation model apis Images. arXiv preprint arXiv:2305. 15560, 2023.
Xinyu Luo, Christopher Musco, and Cas Widdershoven. Dimensionality reduction for general kde mode finding. In International Conference Machine Learning. PMLR, 2023.
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. Moses Charikar and Edith Cohen (eds.), Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Com- puting, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 1027-1038. ACM, 2019, doi: 0t55/33333276.33133333
10.1145/3313276.3333333 URL ARL.htss. httptttts/// /oo..
Jirí Matousek. Lectures on discrete geometry, volume 212 of Graduate texts in mathematics. Springer, 2002. ISBN 978-0-387-95377--1.
12

---

Published as a conference paper at ICLR 2024
Shyam Narayanan, Sandeep Silwal, Piotr Indyk, and Or Zamir. Randomized dimensionality reduc- tion for facility location and angle-linkage clustering. In International Conference on Machine Learning. pp. 7948-7957. PMLR, 2021.
Jeff M. Phillips and Wai Ming Tai. Near-optimal coresets of kernel density estimates. Discret. Comput. Geom,, 6374)7867-887, 2020. doi: 10.10077/00044001-000000 doi. 100 1007//00054--000 011-0000045-10-011110000000-0--0 00119-0014--66
URL https://
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 13-2011, 2023.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning, pp. 8748-8766 8763. PMLR, 2021.
Sushant Sachdeva and Nisheeth K. Vishnoi. Faster algorithms via approximation theory. Found. Trends Theor Comput. Sci., 92):125-210, 2014. doi: 10. 10/1566/0400000055 URL https: ///dii.org/// 15511000000006655
Bernhard Schölkopf, Alexander Smola, Francis Bach, al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
John Shawe-Taylor, Nello Cristianini, al. Kernel methods for pattern analysis. Cambridge uni- versity press, 2004.
Vikrant Singhal and Thomas Steinke. Privately learning subspaces. In Marc' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp- 1312-1324, 2021. URL https: https::/proceeeeeee http://poceeeg.....e// 0 9bb69adcccccbbee1444200000 -btt
neuriingnnnnenun...eeee.eerr neurips. ccc/paper/222//has.. Abstract html.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Florian Tramèr, Reza Shokri, Ayrton San Joaquin, Hoang Le, Matthew Jagielski, Sanghyun Hong, and Nicholas Carlini. Truth serum: Poisoning machine learning models reveal their secrets. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 2779-2792, 2022.
Salil Vadhan. The Complexity of Differential Privacy. pp. 347-450. Springer, Yehuda Lindell, ed., 2017a. URL attps://link.. springer com/ Shapter/10.1000
778-3-319- 101-33319--7048-- 57048-8
Salil Vadhan. The Complexity of Disferential Privacy, pp. 347-450. Springer, Yehuda Lindell, ed., 2017b. URL https: //t::///inkk..... springerr com/ chapter/10.1007.
978- 778-3-319-1 3-0---1---788111
Tal Wagner, Yonatan Naamad, and Nina Misrha. Fast private kernel density estimation via locality sensitive quantization. In International Conference on Machine Learning. PMLR, 2023.
Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang. Dif- ferentially private data releasing for smooth queries. The Journal of Machine Learning Rexearch, 17(1):179--1200 2016.
Yucheng Yin, Zinan Lin, Minhao Jin, Giulia Fanti, and Vyas Sekar. Practical gan- aan-based synthetic ip header trace generation using netshare. In Proceedings of the ACM SIGCOMM 2022 Conference, pp. 458 452-472, 2022.
13

---

Published as a conference paper at ICLR 2024
Da Yu, Huishuai Zhang, Wei Chen, and Tie- Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference on Learning Represen- tations, 2020.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. arXiv preprint arXiv:2110.06500, 2021.
Da Yu, Sivakanth Gopi, Janardhan Kulkarni, Zinan Lin, Saurabh Naik, Tomasz Lukasz Religa, Jian Yin, and Huishuai Zhang. Selective pre-training for private fine-tuning. arXiv preprint arXiv:2305. I 13665, 2023.
Xiang Yue, Huseyin A Inan, Xuechen Li, Girish Kumar, Julia McAnallen, Huan Sun, David Levitan, and Robert Sim. Synthetic text generation with differential privacy: A simple and practical recipe. arXiv preprint arXiv:2210. 1122200.44440 14348, 2022.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016. 2016.
Wide residual networks.
arXiv
preprint
14

---

Published as a conference paper at ICLR 2024
A ADDITIONAL PRELIMINARIES
A.1 STANDARD DIFFERENTIAL PRIVACY RESULTS
Two datasets X, X' are neighboring if they differ on single data point.
Definition A.1 (Dwork et al. (2006)). Let M be a randomized algorithm that maps an input dataset range of outputs O. For 8 > O, M is defined to be (e, (c,5)-1 5-DP ifr every neighboring datasets
X, X' and every O S O, (X]M(() E O] S ef Pr(M((X)) E O] + If = O, we say that M is E-DP (this is called pure differential privacy).
Theorem A.1 (Advanced Composition Starting from Pure DP (Dwork al., 2010)). Let
My...., My X + y be randomized algorithms, each of which is s-DP. Define M : X + yk
by (x) (M1 (,)...., where each algorithm is run independently. Then M is (E', -DD
for any 5 > 0 and
kE² e' 2
+ log///ogg1/0))
For O, M is ks-DP.
A.2 ADDITIONAL RELATED WORKS
Distance Query Related Works. The construction times and query times in the result below are not explicitly stated in Huang & Roth (2014), but they are likely be similar to that of Theorem 2.2.
Theorem A.2 (Huang & Roth (2014)), Assume the datasel and query points are contained in the lg ball of diameter 1. There exists an algorithm which outputs an E-DP data structure for the distance function [(x, y) | y/l such that the expected additive error is Ô 15//17
g2/17
Feldman et al. (2009) give lower bounds for additive errors of private algorithms which approximate the k-median cost function, which is related to the & distance query. However, their lower bound lower bounds hold for any private mechanism.
only applies to coresets specifically, whereas There have also been recent works designing scalable algorithms for computing distance functions in the non-private setting; see Indyk & Silwal (2022) and references therein.
KDE Related Works. Earlier works such the mechanisms in (Gupta et al., 2012; Blum et al., 2013; Aldà Rubinstein, 2017) also study or imply results for DP-KDE. However, many suffer from drawbacks such as exponential dependency (2023) were shown to be superior to such prior methods (see therein for more discussions). so we only compare to the current state of the DP KDE results from Wagner al. (2023).
d for running time. The results of Wagner al.
Generic Private Queries. We refer the reader the the excellent survey of Vadhan (2017a) and references therein for an overview of algorithms and discussions for broad classes of queries for pri- vate datasets. Lastly, we note that dimensionality reduction has been studied in differential privacy in ODD contexts in (Blocki et al., 2012; Singhal & Steinke, 2021); see the references therein for further related works.
B 4 DISTANCE QUERY
We construct a private data structure for answering & distance queries in one dimension. The general high-dimensional case, given fully in Appendix B.1, can handled as follows: create collection of one-dimensional data structures, constructed on the standard coordinate projections of the dataset. We now describe our one-dimensional algorithm. For the sake of simplicity, let us assume for now that all dataset points are integer multiples of 1/n in [0, 1]. This holds without loss of generality as shown later. Furthermore, let us also instead consider the slightly different interval query problem. Here data structure outputs J ( X). We can approximate a distance query at any y by asking appropriate interval queries 7, for example geometrically increasing intervals around the query point y.
are given interval I C R the query, rather than point y, and our
15

---

Published as a conference paper at ICLR 2024
To motivate the algorithm design, let us additionally ignore privacy constraints for moment. We use the classic binary tree one dimension: its leaves correspond to the integer multiples of 1 1/n in [0, 1] and store the number of dataset points in that particular position, while internal nodes store the sum of their children. is well-known that any interval query can be answered by adding up the values of only Oloog n) tree nodes. To handle privacy, release a noisy version of the tree. We note that changing any data point can only change O n) counts in the tree, each by at most one (the leaf to root path). This bounds the sensitivity of the data structure. The formal algorithm and guarantees are stated below. Before presenting them, we make some simplifications which hold without loss of generality.
Remark B.1 (Simplifications). (1) We scale all dataset points from [0, Rj to [0, 1] by dividing by R. also scale y/. We can undo this by multiplying our final estimate by R. (2) After scaling, just instead query
assume E 1]. If is outside 00, 11, for example y Z 1, we and add n(y - 1) to the final answer, since all dataset points are [0, 1]. This does not affect the approximation. (3) Lastly, round all points to integer multiples of 1/n, introducing only O(R) additive error.
Algorithm Pre- processing data structure
1: Input: A set X of n numbers in the interval [0, 1], privacy parameter E
2: Output: An e-DP data structure
3: procedure PREPROCESS
4: Round every dataset point integer multiple of 1 1/n
5: Compute the counts of the number dataset points rounded to every multiple of 1/n
6: Build balanced binary tree where internal nodes store the sum of the counts of their
children and leaf nodes store the counts of the multiples of 1/n
7:
Independently add noise drawn from Laplace(1) where r (llog(n)/z) to every count
8: Return tree T
9: end procedure
Algorithm 2 Interval Query
1: Input: Tree T, interval Q [0,
2: procedure NOISYCOUNT
3: Round the endpoints of Q to the closest multiple of 1/n
4: Break Q up into the smallest number of contiguous and disjoint pieces such that there is a
>> Ar most Oloo pieces required 5: Return the sum of the counts in each of the nodes in T computed above
node in T representing each piece
6: end procedure
Algorithm One dimensional Distance Query
1: Input: data structure 7' from Algorithm 1, query E [0, 1], accuracy parameter a E (0, 1).
2: procedure DISTANCEQUERY
3: Round y to the closest integer multiple of 1/n
4: Value
5: for 0, 1, O(log(n)/a) do
6:
Q, - y + (T+O)t [+
> This will consider the points to the right of
7: Value f- Value NoisyCount((,) "[tay
8: end for
9: Repeat the previous loop for intervals to the left
Return Value
11:
end procedure
Lemma B.1. The tree T returned by Algorithm is e-DP.
Proof. We can encode the tree T as a vector dimension (n)) Changing one input data point only changes Ollog n) entries of this vector, each by 1, thus the sensitivity of T is O(log n). Adding
16

---

Published as a conference paper at ICLR 2024
coordinate-wil wise Laplace noise of magnitude (llo(n))ss) suffices to ensure E-DP using the standard Laplace mechanism.
We now analyze the utility of the algorithm.
Theorem B.2. Suppose X S [0, R) a dataset of n numbers in one dimension. Let a E (0, be the accuracy parameter used in Algorithm 3. Let A be the outpui of Algorithm and let A' Exex 1 - x be the true distance query value. Then we have A A S aA' + CRR
Proof. For simplicity, we only consider the distance query to the points in X to the right of y. The identical proof extends to the symmetric left case. We also work under the simplifications stated in Remark B.I. They only affect the additive error by at most O(H). For an interval Q, define TrueCount Q) to be the true value IQ nX. Let
Estimate; = Σ
TrueCount(Q.)
and A' A'=
1y x x/- 120
a)
120
First, we know that [Estimate; A S a A', as for all j. the distanced between y and different points z E X n Q2 only differ by multiplicative (1 + a) factor. Thus, it suffices to show the
output as returned by Algorithm 3, i.e. A, differs from Estimate, by EVA Let NoisyCount())
denote the interval query answer returned by our noised-tree via Algorithm Algorithm 3 outputs
A = E5 (1+a)² HoisyCount(Q)) We wish to bound
Estimate; A <
Σ J20
(1 (1+ (TrueCoun(Qj) - NoisyCount(Q))
Note that : TrueCount(2))> NoisyCount(2.) is equal to the sum of at most O n) Laplace random variables, each with parameter O(log n)/s). This is because we compute all noisy counts by accumulating the counts stored in the individual nodes in corresponding to Qj- We only query O(log n) nodes for any Qj and each node has independent noise added. Thus, E ZZ, 0 and Var Z [I+a|]
Ó(1) e (I+a)s In addition, the Zj" 's are also independent of each other since the intervals Qj 's are disjoint, meaning we query disjoint sets of nodes in the tree for different Q," 's. Hence,
Var Σ
E 2,
0(1)
Σ (1+a) 120
Õ(1)
(I)
(1+a)} 120
ag
meaning with large constant probability, say at least 0.999, the quantity Estimate; A is at most ((1)(ev/a) by Chebyshev's inequality. A similar conclusion also holds in expectation since for any centered random variable W, E. W| v /Var(W). We recover desired statement by multi- plying through by R to undo the scaling.
B. DIGEESINENS & QUERY
Algorithm automatically extends to the high dimensional case due the decomposability of the l distance function. Indeed, we simply instantiate d different one-dimensional distance query data structures, each on the coordinate projection of our private dataset. The algorithm stated below. For simplicity, we state both the preprocessing and query algorithms together.
Algorithm High- dineediimenioonal & distance query
1: Input: Set X of n d'-imensional points in the box [0, R] privacy parameter mulitplicative
accuracy parameter a, query
2: procedure e QUERY
3: Instantiate d different one-d data structures Di...., Da. D, is the output of Algorithm on Preprocessing Stage
the ith coordinate projections of X. Each data structure is e/d-DP
4: Return The sum of outputs when D, is queried on yi for every i
D Query Stage
5: end procedure
17

---

Published as a conference paper at ICLR 2024
The following theorem is corollary of Lemma B.1 and Theorem B.2.
Theorem B.3. Let A be the output of Algorithm 4. Let A' ExEx lly - æ1l1 be the true answer. We have E A - A S aA' + +Ö
Rdlli) EVO
Furthermore, Algorithm 4 is e-DP.
Proof. The E-DP guarantee follows from standard DP composition results (Theorem A.I), so it remains to argue about the approximation guarantee. Let A, be the estimate returned by DD and let A be the true answer in the ith dimension. Note that A' = Σ, A and A = Σ; A,. Naively applying Theorem B.2 gives us additive error Ö(Rd² ((Rdd/(e//r /(eva)). However, we can exploit the fact that the data structures in the individual dimensions are using independent randomness to get a better bound.
Let us inspect the proof of Theorem B.2. Let Zj be the variables Zj used in the proof of Theorem B.2 for coordinate Similar to the proof of Theorem B.2, we can note that the error incurred by our estimate among all coordinates, can be upper bounded by the absolute value of Σj [1+a]7 E;)), where each 23 are independent across i and j and are each the sum of at most O(log n) different Laplace n()))))/e) random variables. The variance of each individual dimension given by Equation| 1 (with scaled down by e/d), i.c., it is of the order (dd)) ((E"). The total variance across copies then O(d))/(a=) (ox²). Finally, the same calculations as the proof of Theorem B.2 imply an additive error of the square root of this quantity, namely ((d)-))((Vae).
we relax the privacy guarantees to approximate DP, we can get better additive error, matching the additive error term in the lower bound of Theorem C.2 (note however that Theorem C.2 is lower bound on pure DP algorithms, not approximate DP).
Theorem B.4. Let 5 > and A be the output of Algorithm 4 where every one dimensional al- gorithm is instantiated to be (CE/ (oloo((//))-DDP for sufficiently small constant e indepen-
dent of all parameters. Let A' = Exxx lyy ælI2 be the true answer. We have E AA - A'l s
aA' +
Rdd (lg(11))
Furthermore, Algorithm 4 is (e.8)-DP assuming OOoog (16)). Ô
EVO
hides logarithmic in n.
Proof. The same proof as Theorem B.3 applies, but instead we use the approximate DP advanced composition result A. and an appropriately smaller noise parameter in Algorithm 1.
C LOWER BOUNDS FOR & DISTANCE QUERIES
First we obtain lower bounds for the one-dimensional case, which is then extended to the arbitrary dimensional case. Recall the definition of the dimensional distance query problem: Given a dataset X of n points in the interval [0, R). an algorithm outputs a data structure which given query y E IR, computes the value >rex x- y/. Our lower bound idea is via the 'packing lower bound' technique used in DP (Hardt & Talwar, 2010; Beimel et al., 2014; Vadhan, 2017b). At a high level, we construct many datasets which differ on very few points. By the restrictions of DP, the & distance queries on these datasets must be similar, since they are all 'nearby' datasets. However, ensure that these different datasets result in vastly different true & distance queries for a fixed set of queries. This implies a lower bound on the additive error incurred from the privacy requirements.
construction will
Theorem C.1. For sufficiently large and any E < 0.2, any E-DP algorithu which outputs a data structure such that with probability at least 2/ the distance query problem is correctly answered on any query y with additive error at most T, must satisfy T = ((R/e).
Proof. Let T be the additive error of an algorithm A as described in the theorem statement. Our goal is to show that we must have T 2 (2RRe)). Note that crucially we know the value of T. Since the purported algorithm outputs an cDP data structure, we use the value of T to design a 'hard' instance for the algorithm.
Let a E [0, be a parameter. Define 2 different datasets as follows: we first put markers in the interval (0, R] at locations kR for all < k < Rl-a, At every marker besides O we either put
18

---

Published as a conference paper at ICLR 2024
1 data points, and consider all such possible choices. The rest of the data points put at location 0. For sufficiently large n, this results in the claimed number of datasets.
or y 7t=
Now for every such dataset D, define the function fD R + IR defined
Sn
Σ RED
a yl-
We claim that the (exact) vector of evaluations
R³)]
uniquely determines D. Indeed, fn is piece wise linear function consisting of at most Ra-a + pieces. Its slopes can only change precisely at the locations kRt Thus, exactly calculating [D((k+ + 1) - (D(kRR) gives us the exact values the slopes, and thus allows us to reconstruct the piece wise linear functions that comprise fD. Correspondingly. this allows us to determine which markers contain non zero (i.e. 7) number of points, reconstructing D.
The second claim is that the vector of evaluations with entry wise additive error at most T allows for the exact reconstruction of the vector of evaluations. This follows from the fact that the exact evaluation values are multiples of 7/ta and the additive error is small enough to determine the correct multiple. Formally, we have that T < R and since each In (kRR) a multiple yy y/8, any entry of noisy evaluation vector with additive enror at most T can be casily rounded to the correct value, as it lies closest to a unique multiple of RR.
Now the rest of the proof proceeds via the 'packing' argument for proving lower bounds in differ- ential privacy. Let Q be the queries defined above and let PD be the set allowable vectors of evaluations (i.e. those that achieve entry wise error of most T) for dataset D Q. As argued above, the probability that A on dataset D outputs a vector in Pp is at least 2/3, and all these sets Pn are disjoint as argued above. Furthermore, all datasets differ in most
yR' l- < R. 2a + Rl-a
data points. Let D' be the dataset with all points O. Group privacy gives us
Σ Pr(A(D', E PD)
R3T 20 2R -
"ett"))ee((A...O Pp)
Pr(A(D,.)
2
(3TR!-2a 1al-2244 22
3
D
n
2
follows that
3TR!-20 20 + R!-0 log 12) R2) log(2/3)
log(2)
log(2/3)
R
T>
&
35
3e R1-2a
3
Taking a + we can check that for S 0.2, 2 0.02R/E 22 (R)))). as desired.
Let now extend the lower bound to d dimensions. Recall the problem we are interested in is the following: Given a dataset X of n points in Id with every coordinate in the interval [0, R). give algorithm which outputs a data structure, which given query y Rd. computes the value Exex x | y|l The goal is to prove that ~ Rd/e additive error is required for answering queries of this form. For a vector v, let v(j) denote its jth coordinate.
Theorem C.2. For sufficiently large n and R as a function of d and sufficiently small constant e, any e- DD algorithm which outputs a data structure which with probability at least 2/3 answers the above query problem for any query with additive error at most T, must satisfy T = 52 Rd/s).
Proof. We reduce the 1 dimensional version of the problem to the d dimensional version which allows to the lower bound of Theorem C.I. Pick such that (Rd) Rd/ log( Rd) and
19

---

Published as a conference paper at ICLR 2024
suppose R satisfies R 2 20d for sufficiently large constant C. Furthermore, assume that R is an integer multiple of R Now consider the lower bound construction from Theorem C.I where the parameter 'R' there is replaced by Rd and is stated. Theorem C.1 implies that an E-DP data structure which with probability at least 2/3 correctly answers any distance query for a one dimensional input must have additive error at least (((Rd))) /e) = (Rd/E). We will now show how to simulate any one dimensional query y on this lower bound instance with one d dimensional query on related d dimensional instance.
To construct the dimensional instance. consider the interval [0, Rd as d different blocks, separated by integer multiples of R. as [0, R), [R, 2 etc. Note that in the one dimensional hard instance we are considering from Theorem C.I, we can always ensure that every one of these d blocks contains the same number of points (For example by only considering such 'balanced' allocations of dataset constructions the marker construction from C.I. Due to our choice of R and a, is easy to see that the number of such balanced allocations is least 20((Rd)*~)) Let X1 be this one dimensional dataset and let n' be the number of (one dimensional) points that are contained within each block. Consider the d dimensional dataset on n' points where the (one dimensional) points in the first block are the first coordinate projections of the dataset and in general, the points in the ith block are the ith coordinate projections of the dataset. Since every block has the same number of points, projections'. Denote this dataset by Xa. For a one dimensional query make vector ÿ E IR which just has y copied in all its coordinates.
can construct such dataset which is consistent with respect to these coordinate
We have
Σ EXI
y wー
x
E blocks wEb
|
x1
xx())
x
Σ xxXa
ø111
Thus, the exact value of the single d dimensional query have constructed is equal the exact value of the one dimensional query we are interested in. This reduction immediately implies that any e-DP data structure which with probability least 2/3 answers all d dimensional queries with additive error at most T must satisfy T (((d/=),, as desired.
Remark C.1. The lower bound is slightly stronger than stated since only assume the query vectors have their one dimensional coordinates bounded by Ö(R).
Remark C.2. There a gap between our upper and lower bounds. Our e-DP data structure has a ((d-5) dependency whereas the lower bound we prove only states (i(d) dependency is required. Note that our approx-DD result of Theorem B.4 has only (dd dependency, but the lower bound we proved only applies to pure DP algorithms. It is an interesting question to close this gap between the upper and lower bounds.
D COROLLARIES OF OUR l DATA STRUCTURE
Our high dimensional & distance query result implies multitude of downstream results for other distances and functions. For example, automatically implies a similar result for the l case via standard oblivious mapping from & to Li. A similar procedure was applied in Huang & Roth (2014), but using our version of the ε distance query obtains superior results for the lz case. The guarantees of the mapping is stated below.
Theorem D.1 (Matousek (2002)). Let E (0, 1) and define T Rd + R by
T(x);
Σ Zzjz
1= 1,.,...,
3h 1=1
Note there many ways assign the coordinate projections to the points in Rdd We can just consider fixed assignment.
20

---

Published as a conference paper at ICLR 2024
where B 2/ and Ziz standard Gaussians. Then for every vector x E R we have
Pr[(1 - >>]||= (1(()) s (1 + + -
where c is a constant.
The mapping 7 given by Theorem D.1 is oblivious the private dataset and can be released for free without any loss in privacy, and the distances are preserved up to a + a multiplicative error if we take k (n) log(1/a)//²²) for a dataset of size n.
Corollary D.2. Let X be private dataset of size n with bounded diameter of R. in l2. There exists an E-DP data structure such that for any fixed query with probability 99%, it outputs Z satisfying Z ExEx
frexlll || ylla| I E | ull + + (at.gg)
Proof. We sketch the argument since it is follows from combination of the prior listed results. We just apply the embedding result of Theorem D.1 as well as the guarantees of our & distance query data structure from Theorem B.3. The only thing left to check is the bounds of the individual coordinates after we apply the embedding. Note that with high probability, every coordinate after applying T will be bounded by (()o)). The bound follows by just plugging into the statement of Theorem B.3.
Note that minor modifications to the one dimensional & algorithm also implies the following:
Corollary D.3. Letp 2 1 and suppose all points in our one-dimensional datasets are in the interval [0, R). Let Z be the output of Algorithm 3 but with scaled down by factor of p and all counts weighted instead by (1 + a/p)">² in Lines 8 and 13 of Algorithm 3. Let Z ->oex x
be the true answer. We have E Z Z" < aZ' + (It log(1/p)
EVa
The higher dimensional version also follows in similar manner to Theorem B.3 due to the decom- posibility of P. Ezex || yll Σÿ= Exex
Corollary D.4. be the output of Algorithm but with modifications made as Corollary D.3.
Let Z' Exex 11y I1β be the true answer. We have. E Z Z'| S aZ + Ô R' log(1/p)
5va
Furthermore, Algorithm 4 is e-DP. Similarly to Theorem B.4, get (8, DDP algorithm R' RPdd/log(pff
satisfying E Z Z'| I 77' +
D. AN ALTERNATE ALGORITHM FOR &
We give an alternate, simpler algorithm, with slightly better guarantees than our general eg result. Corollary D.5. There exists an s-DP algorithu which answers the Eg distance query with additive error O dd'd in expectation and requires (d) query time.
Proof. The following identity holds:
Σ ZEX
1-
Σ 1| EXI -nly EXI XEX
E X l1 is scalar which does not where EX = - Note that the first quantity Exex |
depend the query y. Thus, alternate eDDP algorithm in the Eg case is to first release (noisy) x E xI2 as well as a noisy E.X.
version of Ezex
If all coordinates are in [0, R), then changing one data point can change every coordinate of E X by R/n factor. Analyzing Σzex || E 3 is a bit trickier since changing one data point changes
We need to clip the the coordinates of the embedding output that every coordinate lies in the correct range. But this event happens with high prohability, it does affect the distance- preservvn guarantees.
21

---

Published as a conference paper at ICLR 2024
term in the sum well as E X. Let denote the new mean after changing data point in X and let E X denote the old mean. We have
Σ mex
2 2112 =
Σ
| EX 2112
ZEX
Σ
(|L
- EX +2 -
-X -211)
2EX
Now n/| EX 2113 2 O(12 and
Σ - 2)1 2 ZEX
Σ xEX
1 EX|12 ||2 EX S O(R2)).
Thus, the simple Laplacian mechanism of adding Laplace(O((ed/e)) and releasing the value E E ensures E/2-DP. Then we can release the vector E by adding Laplace (Rd/(ne)) noise every coordinate, also ensure E/2-DP. Overall, the algorithm &-DP. To analyze the error, note that we get additive error O(I2d/s) from the noisy value ΣxEx | 1 - E Assuming n sufficiently large, we can easily repeat calculation similar to above which shows that the overall additive error at most O(IAd/s) in expectation. Indeed, letting& denote the noisy mean output, we have
of Ezex x ||
||ly =1 lyy E x s 2 z|12 1|2 EX + ||2 EX
from which the conclusion follows.
E IMPROVED BOUNDS FOR THE EXPONENTIAL AND GAUSSIAN KERNELS
In this section we provide our bounds for the exponential and Gaussian kernels, improving the query time of the result of Wagner al. (2023) stated in Theorem 2.3.
Theorem E.1. Let a E (0,1) and suppose n 2 O (23)). For h(x, y) = || - yll2 and | - 1 there exists algorithm which outputs e-DP data structure for the kernel f(x, v) = --(r..)) with the following properties:
1. The expected additive error is
2. The query time is Ô (d + 2.).
3. The construction time is Ô (nd + )).
4. and the space usage is Ô (d )
Note that our bound improves upon Wagner al. (2023) in the large dimension regime d >> 1/a². by disentangling the factors of d and 1/a. We prove this via general dimensionality reduction result, which maybe of general interest. Note that our dimensionality reduction result also implies improved bounds for KDE queries in the non-private setting as well, elaborated in Section G.
E. DIMENSIONALITY REDUCTION FOR GAUSSIAN KDE
We obtain general dimensionality reduction results for the Gaussian and exponential KDE, using variants of the Johnson- Lindeettnnnnddsssruusss (JL) transforms. See 2 for overview and motivations. Theorem E.2 (Dim. Reduction for Gaussian and exponential kernels), Let G Rd (a() be the standard Gaussian JL projection where a < 1 is sufficiently small con- stant. Fix a query y Rdd Let
Σ f(x,))
X
FEX
8 =
Σ
f(Gz, Gy)
X
DEX
for f(x, v) e- -lx--olaa [xx v) c ~1 Then, E -
22

---

Published as a conference paper at ICLR 2024
As stated, Theorem E.2 requires a projection matrix of dense Gaussian random variables, making the projection time O(d/a²). We can speed this up by using the fast JL transform of Ailon & Chazelle (2009), which only requires O(d 1/a?) time, significant speedup in the case where the original dimension is large.
Corollary E.3. The same guarantees as in Theorem E.2 holds if we use the fast JL transform and project ( /a)² /a²) dimensions.
In the proof of Theorem E.2, we use the following facts about a standard Johnson-Lindenstrauss (JL) projection using Gaussians:
Lemma E.4 (Indyk & Naor (2007); Narayanan et al. (2021)). Let be unit vector in Rd and let G be an (appropriately scaled) Gaussian random projection to k dimensions. Then for >> 0:
Pr(I|]==|| 1| 1) S PR/8
and
3 (
Pr([]Gr| $ 1/t) -
Proof of Theorem E.2. We give the full proof for f(z y) e 1z-- Carrying out the identical steps with very minor modifications also implies the same statement for far, y) = e --11==ll,, whose details are omitted. Fix X. We calculate E (f y) fGr, Gy)] (note the randomness is over G). We consider some cases, depending on the value of f(x y).
Case 1: f(x,,/ y) S a. In this case, if |Ga Gyllz 2 || yll2. then f(G,, Gy) S a, so the additive error f(x y) f(Gx, Gy)l I Thus, the only relevant event is if the distance shrinks, i.e., ||Gx Gyll2 < | ylle. If f(Gx, Gy) I 3a after the projection, then the additive error [f(x,)) - f(2,, Gy)l S O(a). Thus, we just have consider the event f(Gx, Gy) > 3a.
For this to happen, we note that || v/12 2 log(1/a)) but ||Gx - Gyll2 < log(a-1/3) Thus, the distance has shrunk by a factor of
| yl12 |Gr - Gylla lo33)
log a log(3) loggaa1///0 1/3)
log(3) (3)
1og(a-1/3)
By setting = (log((//a)) and t = (ot//oo////))) in Lemma E.4, the probability of this event at most a, meaning the expected additive error E fz, fGr, Gyyl can also be bounded by a.
Case 2: fzz a. This is more involved case, need to handle both the sub-cases where the distance increases and decreases. Let f(x, y) = a.
Sub-case 1:
In this sub-case, we bound the probability that f(r, Gy) S r - a/2. The original distance is equal log(1/r) and the new distance is at least log((r -1). The ratio of the new and old distances is g(r) = log(r - a/2)/ log(r). Writing r = wa/2 for w 2 2, we have
g(r) = log((w 1)a/2)
log((w - 1//w- wa/2) 1+ log(1 (1 - L/w) log(wa/22
log(wor/2)
log(wa/2)
As llog(1 1/w)l = 0(1ww) for w 2 2, it suffices to upper bound |w log(wa/222 in the
interval 2 < 2/a. One can check that the upper bound occurs for w 2/(ee) (ea)), resulting in log(1 - 1/w)/ (og(wa/2) = 2(x). Thus by taking k = Ollo((//a)/ea in Lemma E,4, the probability that / (Gr, Gy) S r-- a/2 is most
Sub-case 2: this sub-case, we bound the probability that f(G,, Gy) 2 r a/2. Again the ratio of the old and new distances is at least log(r)/ log(r+a/2), Writing r = wa / for w 2 2, we have
log(r + a/2) = log((w + 1)a/2) = log(1 - 1/(w 1))
log(r)
log(wa/2)
log((w: 1)a/2)
23

---

Published as a conference paper at ICLR 2024
Thus similar calculation as above implies that the probability of f(G,, Gy) 2 a/2 is at most a by setting & = (llog(//a)/a² in Lemma E.4.
Altogether, we have bounded the probability of If(Gz, f(x-f((z))) v) 2 a/2 by at most a, meaning E ff Gy) G(x, y)1 & a, as desired.
Then by linearity and the triangle inequality, it follows that
S
1 X
Elf v) [(Gx, Gy)l -
Io(0) < O(a):
X
as desired.
We now prove Corollary E.3 where we use the fast JL transform of Ailon & Chazelle (2009). How- ever, the fast JL transform, denoted as II, does not exactly satisfy the concentration bounds of Lemma E.4. In fact, only slightly weaker analogous concentration results are known. Nevertheless, they suffice for our purposes. We quickly review the concentration inequalities known for the fast JL transform and sketch how the proof of Theorem F.2 can be adapted.
Theorem E.5 (Makarychev et al. (2019)). Let II R mm be the fast JL map of Ailon & Chuzelle (2009). Then for every unit vector x E IRd, we have:
1. Ift S
log then vm
Pr( Pr[ 2t
Q(
log
2_m
2. If
log m Vm
< t 1, then
Pr Pr[ 11 2 1) S (((()/m))
3. lft 2 1, then
Pr( - 2) < 5e ((vmm
Proof of Corollary E.3. We sketch the modification needed and everything else is identical to the proof Theorem E.2. Going through the proof, we can check that Case 2 the only bottleneck that potentially requires higher projection dimension than Theorem E.2. Here, we need to set t = Theorem E.5 and the first inequality there relevant. However, due to the log m factor in the denominator, we require an additional log(1 (og(1/a) factor in the projection dimension to achieve the same probaiblity of failure as in the proof of Theorem E.2.
Proof of Theorem E. I. We simply apply our dimensionality reduction result of Corollary E.3 in a black-box manner in conjunction with the data structure of Theorem 2.3 from Wagner et al. (2023): First we project the datapoints to dimension ((1/a²) and build the data structure on the projected space. We also release the fast JL projection matrix used which is oblivious of the dataset so it leaks no privacy. Finally, to compute a KDE query, we also project the query vector y using the fast JL projection and query the data structure we built in the lower dimensional space. The construction time, query time, and space all follow from the guarantces of the fast JL transform Ailon & Chazelle (2009) and Theorem 2.3 from Wagner et al. (2023).
F NEW BOUNDS FOR SMOOTH KERNELS
In this section, we give new bounds for privately computing KDE queries for the kernels f(x, v) 1
1+1a-vlla 1+1=-= and 1 1+1i=-vli Our main result is the following.
Theorem F.I. Let a (0, 1) and suppose 2 ( For the kernels f(x, v)
and f(x y) = 1l there exists an algorithm which outputs c-DP data structure with the
following properties:
1. The expected additive error is a,
24

---

Published as a conference paper at ICLR 2024
2. The query time is Ô (d )
3. The construction time is Ô (nd + at)
4. and the space usage is Ô (d )
For the kernel fxx,y) 1+ v we can obtain the following:
1. The expected additive error is a,
2. The query time is Ô (.a)).
3. The construction time is Ô nd
4. and the space usage is (
The road-map for this section is described in two steps. First, we give new dimensionality reduction results for the first two kernels which obtain the stronger relative error guarantee. 'hen show how to combine our dimensionality reduction result with classical function approximation theory to reduce the smooth kernel case our prior Gaussian and exponential kernel result of Theorem E.I. These results assume a similar condition on as in our Theorem E. and prior works Wagner et al. (2023): 2
We present our novel dimensionality reduction for the kernels f(x, y)
2 and y
F.I DIMENSIONALITY REDUCTION
Our main result is the following. As before, we assume the projection chosen independently of the dataset and query.
Theorem F.2 (Dim. Reduction for Smooth Kernels), G .R. TR/1/a² be a Gaussian J.. projection where < 1 is sufficiently small constant. Fix a query Rd. Let
Σ ((x,)),
X
#EX
[(Gx, Gy).
sEX
for f(x,8) 1+la--vlaa or v1
1-11=-=113 Then, E E 2 < 0(zz).
1
similar corollary as Corollary F.3 also applies the exponential and Gaussian KDE case.
Corollary F.3. The same dimensionality reduction bound, up constant factors, holds in Theo- rem F22, if we use the fast JL transform.
Proof of Theorem F22. We give the full proof for f(x,)) = 1+||2-91a"" Carrying out the identical steps with small modifications also implies the same statement for f(z, v)
म- whose details are omitted. Fix a E X. We calculate E fxx v) - (Gr, Gyyl (note the randomness is over G). First we consider the case where the distance ||Gr Gylla expands. Let A, be the event that
Gr Gylle - || v12
Jaúi a(i + 1))
|
2|12
25

---

Published as a conference paper at ICLR 2024
for i 2 0. We have
Pr[A]]][[((,,,)) v) f(Gr, Gy)l A. -
Σ
-/88
1
1
1+ x
vl1
1+ 1
y112(1 + a(i + 1))
120
120
|
yll
a(i+1)
1+ |
vll
1 |
v22 + a(i 1))
120
a(i +
2/8
1 1+ |
yl12
12:
(i + 1)e 2/8
14
u112
$20
7a
1+ x 8112
We now handle the cases where the distance shrinks. We further subdivide this case into sub-cases
where the distance shrinks by a factor i satisfying 1 S < 6 and the sub-case where & 2 6. To handle the first sub-case, let B, be the event that
||
yl12
E [1 + oi, 1 a(i+ 1))
||r Gyll2
for 0 sis 5/a. Note that
1
Bllf(x, v) f(Gx, G()) [B.]
1
l--vlla
+ || 8112
(I+a(+11)
|
y1l2
a
- 1/2 +1
1+ 1 vll2 + ali +
ali
+ 1)
1 1 || ull
Furthermore, under the event B;, we have that
(1 (1-T+ar) arl )
1
|1 ||--zl12 2112 2 ai
|
u/12
|| Gyil22 2
| 5/12.
6
Thus,
ali 1)
Σ
Pr[B: - [(Gr, Gy)l
B
2 22/288
1 + | - y112
OS155/0
0Si55/a
(i + 1)e 1)e- 12288 /288
1 1
v/12
120
160a
1 | - -1l1
For the other sub-case, write it as the union Ug D, where D, is the event that
| v/12
3 2
> 3-,
Gr Gyll
i.e. |/Gz Gyllz shrinks by a factor between 3 2 and 3 24+1, Lemma E.4 gives us
k
1
Pr|D.] fz v) - fGrr Gy)l D. < Σ
2
1
| r- 2112/22t2
1 1 || - -1122/
221
1/a²
2++1
2
+ ||
2112
1/a
2
v/|2
2
2x
||
y y11
26

---

Published as a conference paper at ICLR 2024
Together, the above cases imply that
1
E (f) I(Ga, Gy)l S O(a).
1 11 y
Then by linearity and the triangle inequality, it follows that
2
S
X Σ (ff(..))-((Ca Gy)l O(a):
S {((az),
X
1 +
|| - yll
desired.
Proof of F.3. We outline the steps in the proof of Theorem F.2 which required concentration bounds for the standard JI. transform stated Lemma E.4, and show how they can appropriately replaced by the guarantees of Theorem E.5. The first step is the sum bounding the contribution of the events A, defined as the event where
Gr Gylla - || u12
[axi, a(i 1))
|
y||
for í 2 O. Here, for some smaller values of i, the second condition of Theorem E.5 is appropriate and for the rest, the third event is appropriate. Since the sum Σizg ie'v's converges to constant, this portion of the proof carries through. The same comment applies where we bound the contribution of the events B, The last place we need to check is when we bound the contribution of the events D, Here, the third statement of Theorem E.5 is relevant, and the calculation boils down to showing the sum Σize Q(v32-I) 2 converges constant, which is clearly true.
F.2 PROOF OF COROLLARY 3.2
Proof of Corollary 3.2. Let f(x be the approximation x= in the interval (a, given by Theo- rem 3.1 for = (a)). Now consider g(x) = f(az). For any E [1,1/a], we have
19(x) - -- 1- f(ax)) x 16/z| S O(a)
where the first equality follows from the fact that a is in the interval (ax, 1] for J E [1, 1/a]. Thus, g(z) is an additive (aa) approximation to x1 in the interval [1, 1/a]] Now since g and x are both decreasing functions of x, and x= S a for 2 1/a, it immediately follows that g(x) is an ((a)) additive eтror approximation for x- for all x 2 (note the constant in the O notation has increased). The bounds on the coefficients of g in its exponential sum representation follows from the guarantees of Theorem 3.1.
We are now able to prove Theorem F.1.
Proof of Theorem F.l. The claimed guarantees follow from a simple combination of the tools we have developed far, and black-box appeal to the result of Theorem 2.3. For the kernel f(x, y) I+ I+1a-vll2 we can first perform dimensionality reduction to O(1/a²) dimensions via an oblivious fast JL projection as stated in Corollary F.3. We then use the reduction given by Theorem 3.3 to instantiate Olog(1 (1/r)) copies of private exponential KDE data structure of Theorem 2.3. The same procedure works for the kernel (xx v) I+Il=vil
We don't 't have a dimensionality reduction
s0 we just repeat the same steps above, except we do not perform any dimensionality reduction. The guarantees follow from the guarantees of Theorem 2.3 along with the black box reduction given in Theorem 3.3.
result for the kernel f(x,y) --
G FASTER KERNEL DENSITY ESTIMATION IN THE NON-PRIVATE SETTING
Our novel dimensionality reduction results also obtain faster query algorithms for KDE queries in the non-private settings well in the high-dimensional regime where d > 1/a² where d is the original dimension and a is our desired additive error. Indeed, we can combine our dimensionality reduction bounds of Theorems E.2 and F.2 with any KDE data structure by first projecting
27

---

nd and query time Published as a conference paper at ICLR 2024
reduced dimension and then instantiating the KDE data structure in the projected space. Since the dimensionality reduction preserves kernel sums, we can guarantee accurate answers in the projected dimension. In particular, by combining of corollaries E.3 and F.3) with prior KDE data structures whose preprocessing and query times are listed in Table 2, the following times for the Gaussian, exponential, and the Cauchy kernels. For the Gaussian and exponential kernels, we project to dimension ((1/a²) where ar is the additive error that prior data structures incur and for the Cauchy kernel, we project to dimension ((1/E²), where + is the multiplicative factors that prior data structures incur.
dimensionality reduction results (the fast JL versions
results easily follow for KDE queries. They give improved query
Theorem G.1. By combining with Charikar el al. (2020), for the Gaussian and exponential kernels, we obtain a data structure which gives (1 + E) multiplicative and a additive error guarantee for any fixed query with 90% probability with the following preprocessing and query time:
Gaussian kernel: the preprocessing time is Ô (200:174001)) and query time
.
ò (d+ 2aa1sso0))
Exponential kernel: the preprocessing time Ô
(2
(d Pou.ioar
For the kernel 1+1|=-u11 by combining with Backurs al. (2018), we obtain data structure which gives (1++) multiplicative error with 90% probability for any fixed query with preprocessing time O(nd/E2) and query time (d + 2.)
Table 2: Prior non-private KDE queries. The query times depend the dimension d, accuracy c, and additive error a. The parameter / is assumed to be a constant and log factors are not shown.
Kernel
f (x. y)
Preprocessing Time
KDE Query Time
Reference
Gaussian
a vil
nd (2Q017744(17 nd c ++0(1)) nd 2" ni e P. nd
Charikar et al. (2020)
Exponential
vlla
Charikar et al. (2020)
Exponential
vlla
Backurs et al. (2019)
Laplacian
wil
Backurs et al. (2019)
Rational Quadratic
Backurs et al. (2018)
H ADDITIONAL EXPERIMENTAL DISCUSSION
Note simple but important point: E, are input parameters, cannot just output the data structure or ML model with the highest accuracy. The data structure or model we output must satisfy the given privacy guarantee. Thus, accuracy privacy runtime non-trivial trade-offs.
Methodology of Yu et al. (2020). We use the "GP" haseline from Yu et al. (2020), which trains linear classifier with DP-SGD (Abadi al., 2016) top of features from SimCLR (Chen al., 2020b). Deviating from the vanilla DP-SGD, GP uses all samples to compute gradients at every iteration (i.e., no subsampling) as was found perform better. In our implementation, we use the "r152.2x 2k""k""" SimCLR network released from Chen et al. (2020b) to extract the features of the images. When training the linear classifier, we do grid search of the hyper- syper-parammters (learning rate 1. 0.05, 0.1], gradient clipping threshold E [1.0, 0.1, 0.01], noise multiplier E [100, 500, 1000)) and take the best combination. Following the common practice (Yu et al., 2020), we ignore the privacy cost of this hyper-parameter tuning process.
Methodology De al. (2022). De et al. (2022) pretrains the WRN-28-10 network (Zagoruyko & Komodakis, 2016) ImageNet and fine-tunes it CIFARIO with DP-SGD (Abadi al., 2016). We use their official code for the experiments. We do a grid search the noise multiplier (E [9.4. 12.0, 15.8, 21.1, 25.0) where the first four values used in the paper and the last value is an additional one we test. We report the best results across these values and ignore the privacy cost of this hyper-parameter tuning process.
28

---

Published as a conference paper at ICLR 2024
Our hyper-parameters For method, take the embeddings from the pre-trained 1115_3x_sk1" SimCLR network released from Chen et al. (2020b). Our embeddings were in dimen- apply
sions 6144. Since to reduce the dimensionality, without any privacy loss. Furthermore, we can clip the embeddings well, which reduces the overall sensitivity of our algorithm (to reduce the R dependency in Sec- tion D.1) Thus, our haper-parameters were the projection dimensions, which we looped from 100 to 2000 and the clipping threshold, which picked from 10 choices in [0.001, 1].
computing the & distance squared,
Additional Results. In Figure 4, we also show the & vs accuracy trade-off, ignoring runtime. We plot accuracy as function of the privacy ö is always 10-5 We also plot the best performance of every tested method: we iterate over the hyper-parameters (2022) and Yu et al. (2020) using their code, and we display the best accuracy for every value of s. prper-paraetters are described above. Note the trivial accuracy is .1 via random labels. We see that for small values of e, we obtain the second best results, but lag behind both prior SOTA for large regime. The accuracy in the large 2 1 regime are 0.87, 0.93, 0.95 respectively for ours, Yu et al. (2020), and De al. (2022). However, our approach has a major run-time benefit compared to these prior works, as argued in Section 4. Such boost in runtime may justify the drop in accuracy in some applications.
all methods including both De et al.
Note that the main bottleneck in accuracy of our method is the quality of embeddings used. If we ignore all privacy constraints, then our average similarity based methodology obtains accuracy close to 0.87 without accounting for privacy. This is very close to the performance obtained by E private data structure of Figure 4. Thus, we cannot hope to do better in terms of accuracy. However, our method is extremely flexible in the sense that better initial embeddings, for example from other models or models pre-trained on additional or different data, can automatically lead to better downstream performance.
CIFAR10, 5 = 10-5
0.8
Accuracy
0.6
0.4
Ours
Yu et al. Deepmind
0.2
0.0
0.2
0.4
0.6
0.8
1.0
Figure 4: Accuracy of all methods function of e, ignoring all run-time constraints. The best hyper-parameter choices are used for all methods.
I FUTURE DIRECTIONS
We give improved theoretical algorithms for computing similarity to private datasets for a wide range of functions f. Our algorithms have the added benefit of being practical implement. We view our paper as the tip of the iceberg in understanding similarity computations on private datasets. Many exciting open directions remain such as obtaining improved upper bounds or showing lower bounds for the f's we considered. It is also interesting direction to derive algorithms for more compli- cated 'similarity' measures, such as Optimal Transport (OT), although it is not clear what notion of privacy should use for such measures. Lastly, generalizing our proof-of-concept experiment DP image classification to text or other domains, using embeddings computed from models such as L.MMs, is also interesting empirical direction.
29


Reviews:
[{"review_id": "zvZ16Li0F2", "reviewer": "Reviewer_8sJu", "summary": "In this paper, the authors consider the following question: Given a private dataset X in d-dimensional space and a similarity function f(a,b) (where a and b are d-dimensional points), output a private data structure that given any y approximates the $\\sum_{x\\in X} f(x,y)$. In particular, the authors consider f to be distance functions such as $\\ell_p$ for $p = 1, 2,\\ldots,$  and also Kernel density estimates such as gaussian, exponential and Cauchy kernels. The approximation obtained is $\\alpha$-relative and also has an additive factor.\n\nIn comparison to prior work, for the case where f is the $\\ell_p$ norm, the relative error produced in this paper seems higher (from a relative approximation standpoint) but lower in terms of the additive error. For the KDE queries, the errors are similar to before but the parameters d and \\alpha in the query time of this result are decoupled. Finally, at least some of the results in this paper seems relatively simple leading to an implementation.", "questions": "NA", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper provides a simpler algorithm with a slightly different (better in some settings) trade-off for privately approximating distances and KDEs. The problem is an important one with many usecases. For this reason, I think the result is interesting\n\nThe techniques used involve decomposing the distance calculation into approximating several one-dimensional approximations (at least for the $\\ell_1$). The idea is simple and leads to implementations.", "weaknesses": "The result is an improvement over existing work only under certain settings. In this sense, the result may be considered incremental. Writing is good for the first two sections, but technical insights (especially pertaining to privacy) in the main paper is somewhat limited.\n\nPost-rebuttal update: Thank you for addressing my concerns. I have raised my score accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3CKbtCe3oj", "reviewer": "Reviewer_8tNP", "summary": "This paper provides results for computing similarity-functions for queries and datasets under the constraint of differential privacy (DP). The approach they rely on mainly is leveraging the low-dimensional structures behind specific functions, whilst utilising tools, like dimensionality reduction, approximation theory, and one-dimensional decomposition of functions. They provide both theoretical and empirical results on their findings, and show that they improve on the state-of-the-art solutions for these problems.\n\nTheir algorithm for the $\\ell_1$ distance function involves reduction to a series of one-dimensional decompositions. They work with Kernel Density Estimation (KDE) queries (for kernels, such as Gaussian, Exponential, and Cauchy), they use their new dimensionality reduction results that adapt the well-known JL matrices for their use-case. For the case of smooth kernels, they use functional approximation theory.\n\nSome of their experiments are performed on the CIFAR-10 dataset.", "questions": "1. Is there any specific reason, why you considered pure DP only, but not zCDP or approximate DP?\n2. Might be worth citing this work https://arxiv.org/abs/2106.00001, since it is recent and is relevant to DP dimensionality reduction.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The clear improvement on the prior work by Huang and Roth (2014) in terms of runtime and accuracy, both theoretically and empirically, is something to note.\n2. Besides improving on prior work, this paper also has results for new kinds of queries, as well, for example $\\ell_p$ distance queries.\n3. The paper is easy to follow.", "weaknesses": "1. There is a $\\sqrt{d}$ gap in the additive error for $\\ell_1$ functions, and there isn't much intuition on why that may be happening or why it may be non-trivial to remove.\n2. For the $\\ell_1$ distance queries, the error for $\\varepsilon=1$ seems very large. It will always be the case that the error decreases with increasing $\\varepsilon$, but in any case, it seems like this work may not be as useful in the high-privacy regimes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yStSn43oAL", "reviewer": "Reviewer_3sGr", "summary": "The authors proposed improved theoretical algorithms to compute similarity to high-dimensional private dataset for a rich class of functions. The authors give theoretical results on different distance functions and kernel functions that are advantageous over the existing results in error or query time. Further, some empirical results on $l_1$ query, dimensionality reduction and DP classification also show the advantages of the algorithm over the state-of-art benchmarks with careful discussions.", "questions": "None", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors presents solid theoretical results that improve over the existing literature on the error terms and query time for commonly used distance queries functions and KDE queries.\n\n2. The authors presented a thorough comparisons of the proposed results with the state-of-art theoretical results in the literature.\n\n3. Although the paper is technical, the authors provided sufficient empirical results to support the theory.", "weaknesses": "The paper structure can be improved. I find it more helpful to include some important formal results and algorithms in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hOaB7dXQzv", "reviewer": "Reviewer_PamP", "summary": "This paper gives novel results on the problem of computing the similarity between a query point and private data, in the context of differential privacy.", "questions": "Page 2:\nBetter put the definition of differential privacy in the main body.\n\nPage 3:\nWhat other notions of distance would it make sense to study?\n\nPage 4:\nI do not understand the discussion before Theorem 1.4.\n\nPage 5:\nWhy is it the case that Corollary 3.2 allows you to express 1/(1 + h(x, y)) in such a way?\n\nPage 7:\nSecond math display:\nI do not see why the last equality holds.\n\nPage 8:\nCould you please edit the caption of Figure 1 to be more detailed?\n\nPage 9:\nI do not understand the comparison in Figure 3.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality:\nWork seems original.\n\nQuality:\nWriting and presentation are very good.\n\nClarity:\nWriting is very clear.\n\nSignificance:\nThe problem addressed is important for differential privacy.", "weaknesses": "None.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)