# Efficiently Computing Similarities to Private Datasets

Arturs Backurs
Microsoft Research
<EMAIL_ADDRESS>
&Zinan Lin
Microsoft Research
<EMAIL_ADDRESS>
&Sepideh Mahabadi
Microsoft Research
<EMAIL_ADDRESS>
Sandeep Silwal
MIT
<EMAIL_ADDRESS>
&Jakub Tarnawski
Microsoft Research
<EMAIL_ADDRESS>

###### 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.

##  1 Introduction

It is 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 as 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 et al., 2022; Carlini et 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 a trained ML model to compute the similarity
between public and private data, and Lin et al. (2023) use a voting scheme
based on the $\ell_{2}$ 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 et
al., 2023; Lin et al., 2023), it is also implicit in 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\subset\mathbb{R}^{d}$ and a similarity function
$f(x,y):\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$, such as a
kernel or distance function, output a _private_ data structure
$\mathcal{D}_{X}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ which approximates the
map $y\rightarrow\sum_{x\in X}f(x,y)$. We additionally require that
$\mathcal{D}_{X}$ 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 et
al., 2023). It is a meaningful abstraction 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 a query as the class which it 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,y)=e^{-\|x-y\|_{2}/\sigma^{2}}$, this is known as
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 et al., 2004; Hofmann et al., 2008) for a
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 similarities 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 a wide range of kernels and
distance functions. We also study utility lower bounds in order to understand
the inherent algorithmic 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.

In this work, we consider the natural and standard notion of differential
privacy introduced in the seminal work of Dwork et al. (2006). Two datasets
$X,X^{\prime}$ are called neighboring if they differ on a single data point.

######  Definition 1.1 (Dwork et al. (2006)).

Let M be a randomized algorithm that maps an input dataset to a range of
outputs $\mathcal{O}$. For $\varepsilon,\delta>0$, $M$ is defined to be
$(\varepsilon,\delta)$-DP if for every neighboring datasets $X,X^{\prime}$ and
every $O\subseteq\mathcal{O}$,

$\Pr[M(X)\in O]\leq e^{\varepsilon}\cdot\Pr[M(X^{\prime})\in O]+\delta.$

If $\delta=0$, we say that $M$ is $\varepsilon$-DP, which is referred to as
pure differential privacy.

We also work under the function release model; the data structure we output
must handle arbitrarily many queries without privacy loss.

#### Function release.

Given a private dataset $X$ and a public function $f$, we wish to release a
differentially private (DP) data structure capable of answering either kernel
density estimation (KDE) or distance queries. We focus on the function release
model as in Wagner et al. (2023) and employ their definition: the algorithm
designer releases a description of a data structure $\mathcal{D}$ which itself
is private (i.e. $\mathcal{D}$ is the output of a private mechanism as per
Definition 1.1). A client can later use $\mathcal{D}$ to compute
$\mathcal{D}(y)$ for any query $y$. Since $\mathcal{D}$ itself satisfies
$\varepsilon$-DP, it can support an _arbitrary number_ of queries without
privacy loss. This is motivated by scenarios such as synthetic data
generation, or when we do not have a 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 $\mathcal{D}$ itself is private), some query outputs
can be inaccurate.

Our private dataset is denoted as $X\subset\mathbb{R}^{d}$, with $|X|=n$. The
similarities are computed with respect to a public function
$f:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$. We define
distance queries (for distance functions such as $\|x-y\|_{2}$) and KDE
queries (for kernel functions such as $f(x,y)=e^{-\|x-y\|_{2}^{2}}$) as
follows:

######  Definition 1.2 (Distance Query).

Let $f$ be a distance function. Given a query $y\in\mathbb{R}^{d}$, a distance
query computes an approximation to $\sum_{x\in X}f(x,y)$.

######  Definition 1.3 (KDE Query).

Let $f$ be a kernel function. Given a query $y\in\mathbb{R}^{d}$, a KDE query
computes an approximation to $\frac{1}{|X|}\sum_{x\in X}f(x,y)$.

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.

Type | $f$ | Thm. | Our Error | Prior Error | Our Query Time | Prior Query Time
---|---|---|---|---|---|---
Distance Queries | $\|x-y\|_{1}$ | 4.4 | $\left(1+\alpha,\frac{d^{1.5}}{\varepsilon\sqrt{\alpha}}\right)$ | $\left(1,\left(\frac{nd^{7}}{\varepsilon^{2}}\right)^{1/3}\right)$ | $d$ |  $d$ (Huang & Roth, 2014)
$\|x-y\|_{2}$ | 6.2 | $\left(1+\alpha,\frac{1}{\varepsilon\alpha^{1.5}}\right)$ | $\left(1,\left(\frac{n^{15}d^{7}}{\varepsilon^{2}}\right)^{1/17}\right)$ | $d$ |  $\geq d$ (Huang & Roth, 2014)
$\|x-y\|_{2}^{2}$ | 6.5 | $(1,\frac{d}{\varepsilon})$ | - | $d$ | -
$\|x-y\|_{p}^{p}$ | 6.4 | $\left(1+\alpha,\frac{d}{\varepsilon\sqrt{\alpha}}\right)$ | - | $d$ |
KDE Queries | $e^{-\|x-y\|_{2}}$ | 7.1 | $(1,\alpha)$ | $(1,\alpha)$ | $d+\frac{1}{\alpha^{4}}$ |  $\frac{d}{\alpha^{2}}$ (Wagner et al., 2023)
$e^{-\|x-y\|_{2}^{2}}$ | 7.1 | $(1,\alpha)$ | $(1,\alpha)$ | $d+\frac{1}{\alpha^{4}}$ |  $\frac{d}{\alpha^{2}}$ (Wagner et al., 2023)
$\frac{1}{1+\|x-y\|_{2}}$ | 9.1 | $(1,\alpha)$ | - | $d+\frac{1}{\alpha^{4}}$ | -
$\frac{1}{1+\|x-y\|_{2}^{2}}$ | 9.1 | $(1,\alpha)$ | $(1,\alpha)$ | $d+\frac{1}{\alpha^{4}}$ |  $\frac{d}{\alpha^{2}}$ (Wagner et al., 2023)
$\frac{1}{1+\|x-y\|_{1}}$ | 9.1 | $(1,\alpha)$ | - | $\frac{d}{\alpha^{2}}$ | -
Table 1: Summary of the $\varepsilon$-DP upper bounds. See Definition 1.4 for
the error notation. For clarity, we suppress all logarithmic factors. The KDE
bounds assume that
$n\geq\tilde{\Omega}\left({\frac{1}{\alpha\varepsilon^{2}}}\right)$. The
distance query bounds are stated for points in a bounded radius.

#### Discussion of Theoretical Results.

The main trade-off that we are interested in is between privacy, as measured
with respect to the standard DP definition (Definition 1.1), and accuracy of
our answers, also called utility. For example, a data structure which always
returns a fixed answer, such as 42, is 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.4 (Error Notation).

For a fixed query, if $Z$ represents the value output by our private data
structure and $Z^{\prime}$ represents the true value, we say that $Z$ has
error $(M,A)$ for $M\geq 1$ and $A\geq 0$ if
$\operatorname*{\mathbb{E}}[|Z-Z^{\prime}|]\leq(M-1)Z^{\prime}+A$. That is, we
have relative error $M-1$ and additive error $A$. The expectation is over the
randomness used by our data structure.

We want $M$ to be close to $1$ and the additive error $A$ to be as small as
possible. Table 1 shows our errors and query times, as well as those of the
most relevant prior works. See Section 2 for a technical overview of how we
obtain these results.

For distance queries, the most relevant work is Huang & Roth (2014). They
considered the $\ell_{1}$ and $\ell_{2}$ functions and obtained additive
errors with large dependence on $n$ (dataset size) and $d$ (dimension); see
Table 1. In contrast, we show that if we allow for a small multiplicative
error (e.g. $\alpha=0.001$ in Table 1), we can obtain additive error with
improved dependence on $d$ and _no dependence on_ $n$.

######  Theorem 1.1 (Informal; see Theorem 4.4 and Corollary 6.2).

Suppose the data points have bounded diameter in $\ell_{1}$. For any
$\alpha\in(0,1)$ and $\varepsilon>0$, there exists an algorithm which outputs
an $\varepsilon$-DP data structure $\mathcal{D}$ capable of answering any
$\ell_{1}$ distance query with
$\left(1+\alpha,\tilde{O}\left(\frac{d^{1.5}}{\varepsilon\sqrt{\alpha}}\right)\right)$
error. For the $\ell_{2}$ case, where the points have bounded $\ell_{2}$
diameter, we obtain error
$\left(1+\alpha,\tilde{O}\left(\frac{1}{\varepsilon\alpha^{1.5}}\right)\right)$.

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 of distances. Furthermore, given that we think of $n$ as
the largest parameter, we incur much smaller additive error. Our simpler
approach also demonstrates superior empirical performance as discussed
shortly. Our $\ell_{1}$ upper bounds are complemented with a lower bound
stating that any $\varepsilon$-DP algorithm supporting $\ell_{1}$ distance
queries for private datasets in the box $[0,R]^{d}$ must incur
$\tilde{\Omega}(Rd/\varepsilon)$ error.

######  Theorem 1.2 (Informal; see Theorem 5.2).

Any $\varepsilon$-DP data structure which answers $\ell_{1}$ distance queries
with additive error at most $T$ for any query must satisfy
$T=\tilde{\Omega}(Rd/\varepsilon)$.

Note that our lower bound only pertains to additive error and does not say
anything about multiplicative 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 $\ell_{p}^{p}$; see Section
6.

We now discuss our kernel results. For the Gaussian ($e^{-\|x-y\|_{2}^{2}}$),
exponential ($e^{-\|x-y\|_{2}}$), and Cauchy ($\frac{1}{1+\|x-y\|_{2}^{2}}$)
kernels, we parameterize our runtimes in terms of additive error $\alpha$.
Here, we obtain query times of $\tilde{O}(d+1/\alpha^{4})$ whereas prior work
(Wagner et al., 2023) requires $\tilde{O}(d/\alpha^{2})$ query time. Thus our
results are faster in high-dimensional regimes where $d\gg 1/\alpha^{2}$.

######  Theorem 1.3 (Informal; see Theorems 7.1 and 9.1).

Consider the Gaussian, exponential, and Cauchy kernels. In each case, for any
$\varepsilon>0$ and $\alpha\in(0,1)$, there exists an algorithm which outputs
an $\varepsilon$-DP data structure that answers KDE queries with error
$(1,\alpha)$ and query times $\tilde{O}(d+1/\alpha^{4})$.

For kernels $\frac{1}{1+\|x-y\|_{2}}$ and $\frac{1}{1+\|x-y\|_{1}}$, we obtain
the first private data structures; see Table 1. We do this via a 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 $\alpha$ and $\varepsilon$.
These two kernels and the Cauchy kernel fall under the family of _smooth_
kernels (Backurs et al., 2018).

We also give faster query times for the _non-private_ 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 10.1).

For the Gaussian kernel, we improve prior running time for computing a non-
private KDE query with additive error $\alpha$ from
$\tilde{O}\left(\frac{d}{\varepsilon^{2}\alpha^{0.173+o(1)}}\right)$ to
$\tilde{O}\left(d+\frac{1}{\varepsilon^{2}\alpha^{2.173+o(1)}}\right)$.
Similarly for the exponential kernel, the improvement in the query time is
from $\tilde{O}\left(\frac{d}{\varepsilon^{2}\alpha^{0.1+o(1)}}\right)$ to
$\tilde{O}\left(d+\frac{1}{\varepsilon^{2}\alpha^{2.1+o(1)}}\right)$. The
preprocessing time of both algorithms is asymptotically the same as in prior
works.

#### Discussion of Empirical Results.

Our experimental results are given in Section 11. We consider three
experiments which are representative of our main results. The first setting
demonstrates that our $\ell_{1}$ 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 $\varepsilon$ increases, but
their algorithms always return the trivial estimate of $0$. 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 dimensionality 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 negligible additional error.

Lastly, we explore an application to DP classification on the CIFAR-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 $f$ is a
distance). We set $f$ to be $\ell_{2}^{2}$ 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 et al., 2022).

##  2 Technical Overview

At a high level, all of our upper bounds crucially exploit fundamental ‘low-
dimensionality structures’ 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 algorithmic work. We provide the following insights into
the low-dimensional properties used in our upper bounds.

#### Distance Queries via One-dimensional Decompositions.

For the $\ell_{1}$ distance function, our improvements are obtained by
reducing to the one-dimensional case. To be more precise, we use the well-
known property that $\sum_{x\in X}\|x-y\|_{1}=\sum_{j=1}^{d}\sum_{x\in
X}|x_{j}-y_{j}|$. In other words, the sum of $\ell_{1}$ distances decomposes
into $d$ one-dimensional sums (this is also true for other related functions
such as $\ell_{p}^{p}$). This explicit low-dimensional representation offers a
concrete avenue for algorithm design: 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 6.1), we can also embed
$\ell_{2}$ into $\ell_{1}$ using an oblivious map, meaning that any
algorithmic result for $\ell_{1}$ implies similar results for $\ell_{2}$ 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 Johnson-
Lindenstrauss (JL) matrices for preserving sums of kernel values. The main
challenge is that kernel functions are _non-linear_ functions of distances,
and preserving distances (as JL guarantees) does not necessarily imply that
non-linear functions 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 $O(\log n)$ dimensions
(Johnson & Lindenstrauss, 1984), but this is not possible for the kernel
values: if $\|x-y\|_{2}$ is extremely large, then after applying a JL
projection $G$, $\|Gx-Gy\|_{2}$ can differ from $\|x-y\|_{2}$ by a large
_additive_ factor $\Delta$ (even if the relative error is small) with constant
probability, and thus $e^{-\|Gx-Gy\|_{2}}=e^{-\Delta}\cdot e^{-\|x-y\|_{2}}$
_does not_ approximate $e^{-\|x-y\|_{2}}$ up to relative error.

We overcome these issues in our analysis by noting that we do not require a
relative error approximation! 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 it is possible to
project onto a _constant_ dimension, depending on the additive error, which is
independent of the original dataset size $n$ or original dimensionality $d$.

######  Theorem 2.1 (Informal; see Theorems 7.2 and 9.2).

Consider the Gaussian and exponential kernels. For any $\alpha\in(0,1)$,
projecting the dataset and query to $\tilde{O}(1/\alpha^{2})$ dimensions using
an oblivious JL map preserves the KDE value up to additive error $\alpha$. For
the Cauchy kernel, projecting to $O(1/\alpha^{2})$ dimensions preserves the
KDE value up to multiplicative $1+\alpha$ 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 dimension 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, complementing a
long line of recent works (Boutsidis et al., 2010; Cohen et al., 2015;
Becchetti et 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 $\frac{1}{1+\|x-y\|_{2}}$ in
terms of exponential functions. To be more precise, for
$h(x,y)=\|x-y\|_{2},\|x-y\|_{2}^{2},$ and $\|x-y\|_{1}$, Corollary 8.2 allows
us to express $\frac{1}{1+h(x,y)}\approx\sum_{j\in J}w_{j}e^{-t_{j}h(x,y)}$
for explicit parameters $t_{j},w_{j}$. The corollary follows from a
modification of results in approximation theory, see Section 8. This can be
viewed as projecting the kernel onto a low-dimensional span of exponential
functions, since only $|J|=\tilde{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 kernel! Hence, we
obtain new private KDE queries for a host of new functions in a black-box
manner. The fact that $|J|$ (the number of terms in the sum) is small is
crucial, as instantiating a differentially private KDE data structure for each
$j\in[J]$ does not substantially degrade the privacy guarantees or
construction and query times. This reduction is detailed in Section 8.

###  2.1 Outline of the Paper

Our $\ell_{1}$ algorithm in one dimension is in Section 4. It contains the
main ideas for the high-dimensional $\ell_{1}$ algorithm, given in Section
4.1. Section 5 states our lower bounds for the $\ell_{1}$ distance function.
Applications of our $\ell_{1}$ upper bound, such as for $\ell_{2}$ and
$\ell_{p}^{p}$, are given in Section 6. Our improved DP bounds for the
exponential and Gaussian kernels are given in Section 7. Section 9 contains
improved DP results for smooth kernels (such as Cauchy kernels). Our function
approximation theory reduction is presented in Section 8. Section 10 contains
our improved KDE query bounds in the non-private setting. Finally, in Section
11, we empirically verify our upper bound algorithms and give applications to
private classification.

##  3 Related Work

We use the standard definition of differential privacy (Dwork et al., 2006),
given in Definition 1.1. We survey the most relevant prior works. 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 $\|x-y\|_{1}$. It
is stated for the case where all the dataset points and queries are in the box
$[0,1]^{d}$, but easily extend to a larger domain by scaling.

######  Theorem 3.1 (Huang & Roth (2014)).

Assume the dataset and query points are contained in $[0,1]^{d}$. There exists
an algorithm which outputs an $\varepsilon$-DP data structure for the function
$\|x-y\|_{1}$ with the following properties: (1) the expected additive error
is
$\tilde{O}\left(\frac{n^{1/3}d^{7/3}}{\varepsilon^{2/3}}\right)$111Throughout
the paper, $\tilde{O}$ hides logarithmic factors in $n$ and $d$., (2) the
construction time is $O\left(n^{8/3}\varepsilon^{2/3}d^{2/3}\right)$, (3) the
space usage is $O\left(\frac{n^{2/3}\varepsilon^{2/3}}{d^{1/3}}\right)$, (4)
and the query time is $O(d)$.

(Huang & Roth, 2014) also obtained results for $\ell_{2}$ with additive errors
containing factors of $n$ and $d$ as shown in Table 1. The construction times
and query times in the result below are not explicitly stated in Huang & Roth
(2014), but they are likely to be similar to that of Theorem 3.1.

######  Theorem 3.2 (Huang & Roth (2014)).

Assume the dataset and query points are contained in the $\ell_{2}$ ball of
diameter $1$. There exists an algorithm which outputs an $\varepsilon$-DP data
structure for the distance function $f(x,y)=\|x-y\|_{2}$ such that the
expected additive error is
$\tilde{O}\left(\frac{n^{15/17}d^{7/17}}{\varepsilon^{2/17}}\right)$.

The result of Wagner et al. (2023) concerns private KDE constructions for the
exponential ($e^{-\|x-y\|_{2}}$), Gaussian ($e^{-\|x-y\|_{2}^{2}})$, and
Laplace ($e^{-\|x-y\|_{1}}$) kernels.

######  Theorem 3.3 (Wagner et al. (2023)).

Let $\alpha\in(0,1)$ and suppose
$n\geq\Omega\left(\frac{1}{\alpha\varepsilon^{2}}\right)$. For
$h(x,y)=\|x-y\|_{2},\|x-y\|_{2}^{2}$, or $\|x-y\|_{1}$, there exists an
algorithm which outputs an $\varepsilon$-DP data structure for
$f(x,y)=e^{-h(x,y)}$ with the following properties: (1) the expected additive
error is at most $\alpha$, (2) the query time is
$O\left(\frac{d}{\alpha^{2}}\right)$, the construction time is
$O\left(\frac{nd}{\alpha^{2}}\right)$, and the space usage is
$O\left(\frac{d}{\alpha^{2}}\right)$.

Earlier works such as 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 on $d$ for
running time. The results of Wagner et al. (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 art DP KDE results from Wagner et al. (2023).

#### Other Works on Distance Estimation

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 $\ell_{1}$ distance query. However, their lower bound only applies to
coresets specifically, whereas our lower bounds hold for any private
mechanism. 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.

#### 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 private datasets. Lastly, we note that dimensionality reduction
has been studied in differential privacy in non-KDE contexts in (Blocki et
al., 2012; Singhal & Steinke, 2021); see the references therein for further
related works.

##  4 $\ell_{1}$ Distance Query

We construct a private data structure for answering $\ell_{1}$ distance
queries in one dimension. As an overview, the general high-dimensional case,
given in Section 4.1, can be handled as follows: create a collection of $d$
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 we are given an interval
$I\subset\mathbb{R}$ as the query, rather than a point $y$, and our data
structure outputs $|I\cap X|$. We can approximate a distance query at any $y$
by asking appropriate interval queries $I$, for example geometrically
increasing intervals around the query point $y$.

To motivate the algorithm design, let us additionally ignore privacy
constraints for a moment. We use the classic binary tree in one dimension: its
leaves correspond to the integer multiples of $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. It is well-known that any interval query $I$
can be answered by adding up the values of only $O(\log n)$ tree nodes. To
handle privacy, we release a noisy version of the tree. We note that changing
any data point can only change $O(\log 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 4.1 (Simplifications).

(1) We scale all dataset points from $[0,R]$ to $[0,1]$ by dividing by $R$. We
also scale $y$. We can undo this by multiplying our final estimate by $R$. (2)
After scaling, we assume $y\in[0,1]$. If $y$ is outside $[0,1]$, for example
if $y\geq 1$, we can just instead query $1$ and add $n(y-1)$ to the final
answer, since all dataset points are in $[0,1]$. This does not affect the
approximation. (3) Lastly, we round all points to integer multiples of $1/n$,
introducing only $O(R)$ additive error.

Algorithm 1 Pre-processing data structure

1:Input: A set $X$ of $n$ numbers in the interval $[0,1]$, privacy parameter
$\varepsilon$

2:Output: An $\varepsilon$-DP data structure

3:procedure Preprocess

4: Round every dataset point to an integer multiple of $1/n$

5: Compute the counts of the number of dataset points rounded to every
multiple of $1/n$

6: Build a balanced binary tree $T$ 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($\eta$) where
$\eta=O(\log(n)/\varepsilon)$ to every count

8: Return tree $T$

9:end procedure

Algorithm 2 Interval Query

1:Input: Tree $T$, interval $Q\subseteq[0,1]$

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 node in $T$ representing each piece $\triangleright$ _At
most $O(\log n)$ pieces are required_

5: Return the sum of the counts in each of the nodes in $T$ computed above

6:end procedure

Algorithm 3 One dimensional Distance Query

1:Input: data structure $T$ from Algorithm 1, query $y\in[0,1]$, accuracy
parameter $\alpha\in(0,1)$.

2:procedure DistanceQuery

3: Round $y$ to the closest integer multiple of $1/n$

4: Value $\leftarrow 0$

5: for $j=0,1,...,O(\log(n)/\alpha)$ do

6:
$Q_{j}\leftarrow\left[y+\frac{1}{(1+\alpha)^{j+1}},y+\frac{1}{(1+\alpha)^{j}}\right)$
$\triangleright$ This will consider the points to the right of $y$

7: Value $\leftarrow$ Value + NoisyCount($Q_{j}$)
$\cdot\frac{1}{(1+\alpha)^{j}}$

8: end for

9: Repeat the previous loop for intervals to the left of $y$

10: Return Value

11:end procedure

######  Lemma 4.1.

The tree $T$ returned by Algorithm 1 is $\varepsilon$-DP.

###### Proof.

We can encode the tree $T$ as a vector in dimension $O(n)$. Changing one input
data point only changes $O(\log n)$ entries of this vector, each by $1$, thus
the sensitivity of $T$ is $O(\log n)$. Adding coordinate-wise Laplace noise of
magnitude $\eta=O(\log(n)/\varepsilon)$ suffices to ensure $\varepsilon$-DP
using the standard Laplace mechanism. ∎

We now analyze the utility of the algorithm.

######  Theorem 4.2.

Suppose $X\subseteq[0,R]$ is a dataset of $n$ numbers in one dimension. Let
$\alpha\in(0,1)$ be the accuracy parameter used in Algorithm 3. Let $A$ be the
output of Algorithm 3 and let $A^{\prime}=\sum_{x\in X}|y-x|$ be the true
distance query value. Then we have
$\operatorname*{\mathbb{E}}|A-A^{\prime}|\leq\alpha
A^{\prime}+\tilde{O}\left(\frac{R}{\varepsilon\sqrt{\alpha}}\right)$.

###### 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 4.1. They only affect the
additive error by at most $O(R)$. For an interval $Q$, define
$\text{TrueCount}(Q)$ to be the true value $|Q\cap X|$. Let

$\displaystyle\text{Estimate}_{1}$ $\displaystyle=\sum_{j\geq
0}\frac{1}{(1+\alpha)^{j}}\cdot\text{TrueCount}(Q_{j})\qquad\text{and}\qquad
A^{\prime}=\sum_{j\geq 0}\sum_{x\in X\cap Q_{j}}|y-x|.$

First, we know that $|\text{Estimate}_{1}-A^{\prime}|\leq\alpha\cdot
A^{\prime}$, as for all $j$, the distanced between $y$ and different points
$x\in X\cap Q_{j}$ only differ by a multiplicative $(1+\alpha)$ factor. Thus,
it suffices to show the output as returned by Algorithm 3, i.e. $A$, differs
from Estimate1 by $\tilde{O}\left(\frac{1}{\varepsilon\sqrt{\alpha}}\right)$.
Let $\text{NoisyCount}(Q)$ denote the interval query answer returned by our
noised-tree via Algorithm 2. Algorithm 3 outputs $A=\sum_{j\geq
0}\frac{1}{(1+\alpha)^{j}}\cdot\text{NoisyCount}(Q_{j})$. We wish to bound

$\displaystyle|\text{Estimate}_{1}-A|$ $\displaystyle\leq\left|\sum_{j\geq
0}\frac{1}{(1+\alpha)^{j}}\cdot\left(\text{TrueCount}(Q_{j})-\text{NoisyCount}(Q_{j})\right)\right|.$

Note that $Z_{j}:=\text{TrueCount}(Q_{j})-\text{NoisyCount}(Q_{j})$ is equal
to the sum of at most $O(\log n)$ Laplace random variables, each with
parameter $O((\log n)/\varepsilon)$. This is because we compute all noisy
counts by accumulating the counts stored in the individual nodes in $T$
corresponding to $Q_{j}$. We only query $O(\log n)$ nodes for any $Q_{j}$ and
each node has independent noise added. Thus,
$\operatorname*{\mathbb{E}}Z_{j}=0$ and
$\text{Var}\left[Z_{j}\cdot\frac{1}{(1+\alpha)^{j}}\right]\leq\frac{\tilde{O}(1)}{\varepsilon^{2}}\cdot\frac{1}{(1+\alpha)^{2j}}$.
In addition, the $Z_{j}$’s are also independent of each other since the
intervals $Q_{j}$’s are disjoint, meaning we query disjoint sets of nodes in
the tree for different $Q_{j}$’s. Hence,

$\text{Var}\left[\sum_{j\geq 0}\frac{1}{(1+\alpha)^{j}}\cdot
Z_{j}\right]\leq\frac{\tilde{O}(1)}{\varepsilon^{2}}\cdot\sum_{j\geq
0}\frac{1}{(1+\alpha)^{2j}}\leq\frac{\tilde{O}(1)}{\alpha\varepsilon^{2}},$
(1)

meaning with large constant probability, say at least $0.999$, the quantity
$|\text{Estimate}_{1}-A|$ is at most $\tilde{O}(1)/(\varepsilon\sqrt{\alpha})$
by Chebyshev’s inequality. A similar conclusion also holds in expectation
since for any centered random variable $W$,
$\operatorname*{\mathbb{E}}|W|\leq\sqrt{\text{Var}(W)}$. We recover our
desired statement by multiplying through by $R$ to undo the scaling. ∎

###  4.1 High-Dimensional $\ell_{1}$ Query

Algorithm 3 automatically extends to the high dimensional case due to the
decomposability of the $\ell_{1}$ 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 is stated
below. For simplicity, we state both the preprocessing and query algorithms
together.

Algorithm 4 High-dimensional $\ell_{1}$ distance query

1:Input: Set $X$ of $n$ $d$-dimensional points in the box $[0,R]^{d}$, privacy
parameter $\varepsilon$, mulitplicative accuracy parameter $\alpha$, query $y$

2:procedure $\ell_{1}^{d}$ Query

3: Instantiate $d$ different one-d data structures
$\mathcal{D}_{1},\ldots,\mathcal{D}_{d}$. $\mathcal{D}_{i}$ is the output of
Algorithm 1 on the $i$th coordinate projections of $X$. Each data structure is
$\varepsilon/d$-DP $\triangleright$ Preprocessing Stage

4: Return The sum of outputs when $\mathcal{D}_{i}$ is queried on $y_{i}$ for
every $i$ $\triangleright$ Query Stage

5:end procedure

Our result is stated in Theorem 4.4, which is a corollary of Lemma 4.1,
Theorem 4.2, and the following advanced composition theorem of Dwork et al.
(2010).

######  Theorem 4.3 (Advanced Composition Starting from Pure DP (Dwork et al.,
2010)).

Let $M_{1},\ldots,M_{k}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ be randomized
algorithms, each of which is $\varepsilon$-DP. Define
$M:\mathcal{X}^{n}\rightarrow\mathcal{Y}^{k}$ by
$M(x)=(M_{1}(x),\ldots,M_{k}(x))$ where each algorithm is run independently.
Then $M$ is $(\varepsilon^{\prime},\delta)$-DP for any $\varepsilon,\delta>0$
and

$\varepsilon^{\prime}=\frac{k\varepsilon^{2}}{2}+\varepsilon\sqrt{2k\log(1/\delta)}.$

For $\delta=0$, $M$ is $k\varepsilon$-DP.

######  Theorem 4.4.

Let $A$ be the output of Algorithm 4. Let $A^{\prime}=\sum_{x\in
X}\|y-x\|_{1}$ be the true answer. We have
$\operatorname*{\mathbb{E}}|A-A^{\prime}|\leq\alpha
A^{\prime}+\tilde{O}\left(\frac{Rd^{1.5}}{\varepsilon\sqrt{\alpha}}\right)$.
Furthermore, Algorithm 4 is $\varepsilon$-DP.

###### Proof.

The $\varepsilon$-DP guarantee follows from standard DP composition results
(Theorem 4.3), so it remains to argue about the approximation guarantee. Let
$A_{i}$ be the estimate returned by $\mathcal{D}_{i}$ and let $A^{\prime}_{i}$
be the true answer in the $i$th dimension. Note that
$A^{\prime}=\sum_{i}A^{\prime}_{i}$ and $A=\sum_{i}A_{i}$. Naively applying
Theorem 4.2 gives us additive error
$\tilde{O}(Rd^{2}/(\varepsilon\sqrt{\alpha}))$. 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 4.2. Let $Z_{j}^{i}$ be the variables
$Z_{j}$ used in the proof of Theorem 4.2 for coordinate $i$. Similar to the
proof of Theorem 4.2, we can note that the error incurred by our estimate
among _all_ coordinates, can be upper bounded by the absolute value of
$\sum_{j}\frac{1}{(1+\alpha)^{j}}\left(\sum_{i}Z_{j}^{i}\right)$, where each
$Z_{j}^{i}$ are independent across $i$ and $j$ and are each the sum of at most
$O(\log n)$ different Laplace $O((\log n)/\varepsilon)$ random variables. The
variance of each individual dimension is given by Equation 1 (with
$\varepsilon$ scaled down by $\varepsilon/d$), i.e., it is of the order
$\tilde{O}(d^{2})/(\alpha\varepsilon^{2})$. The total variance across $d$
copies is then $\tilde{O}(d^{3})/(\alpha\varepsilon^{2})$. Finally, the same
calculations as the proof of Theorem 4.2 imply an additive error of the square
root of this quantity, namely $\tilde{O}(d^{1.5})/(\sqrt{\alpha}\varepsilon)$.
∎

If we relax the privacy guarantees to approximate DP, we can get a better
additive error, matching the additive error term in the lower bound of Theorem
5.2 (note however that Theorem 5.2 is a lower bound on pure DP algorithms, not
approximate DP).

######  Theorem 4.5.

Let $\delta>0$ and $A$ be the output of Algorithm 4 where every one
dimensional algorithm is instantiated to be
$(c\varepsilon/\sqrt{d\log(1/\delta)})$-DP for a sufficiently small constant
$c$ independent of all parameters. Let $A^{\prime}=\sum_{x\in X}\|y-x\|_{1}$
be the true answer. We have
$\operatorname*{\mathbb{E}}|A-A^{\prime}|\leq\alpha
A^{\prime}+\tilde{O}\left(\frac{Rd\sqrt{\log(1/\delta)}}{\varepsilon\sqrt{\alpha}}\right)$.
Furthermore, Algorithm 4 is $(\varepsilon,\delta)$-DP assuming
$\varepsilon\leq O(\log(1/\delta))$. $\tilde{O}$ hides logarithmic factors in
$n$.

###### Proof.

The same proof as Theorem 4.4 applies, but instead we use the approximate DP
advanced composition result 4.3, and an appropriately smaller noise parameter
in Algorithm 1. ∎

##  5 Lower Bounds for $\ell_{1}$ 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\in\mathbb{R}$, computes the value $\sum_{x\in X}|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
$\ell_{1}$ distance queries on these datasets must be similar, since they are
all ‘nearby’ datasets. However, our construction will ensure that these
different datasets result in vastly different _true_ $\ell_{1}$ distance
queries for a fixed set of queries. This implies a lower bound on the additive
error incurred from the privacy requirements.

######  Theorem 5.1.

For sufficiently large $n$ and any $\varepsilon<0.2$ , any $\varepsilon$-DP
algorithm which outputs a data structure such that with probability at least
$2/3$, the distance query problem is correctly answered on any query $y$ with
additive error at most $T$, must satisfy $T=\Omega(R/\varepsilon)$.

###### Proof.

Let $T$ be the additive error of an algorithm $\mathcal{A}$ as described in
the theorem statement. Our goal is to show that we must have
$T\geq\Omega(R/\varepsilon)$. Note that crucially we know the value of $T$.
Since the purported algorithm outputs an $\varepsilon$-DP data structure, we
use the value of $T$ to design a ‘hard’ instance for the algorithm.

Let $\alpha\in[0,1]$ be a parameter. Define $2^{R^{1-\alpha}}$ different
datasets as follows: we first put markers in the interval $[0,R]$ at locations
$kR^{\alpha}$ for all $0\leq k\leq R^{1-\alpha}$. At every marker besides $0$,
we either put $0$ or $\gamma:=\lceil\frac{3T}{R^{\alpha}}\rceil$ data points,
and consider all such possible choices. The rest of the data points are put at
location $0$. For sufficiently large $n$, this results in the claimed number
of datasets.

Now for every such dataset $D$, define the function
$f_{D}:\mathbb{R}\rightarrow\mathbb{R}$ defined as

$f_{D}(y)=\sum_{x\in D}|x-y|.$

We claim that the (exact) vector of evaluations

$[f_{D}(0),f_{D}(R^{\alpha}),f_{D}(2R^{\alpha}),\ldots,f_{D}(R),f_{D}(R+R^{\alpha})]$

uniquely determines $D$. Indeed, $f_{D}$ is a piece wise linear function
consisting of at most $R^{1-\alpha}+2$ pieces. Its slopes can only change
precisely at the locations $kR^{\alpha}$. Thus, exactly calculating
$f_{D}((k+1)R^{\alpha})-f_{D}(kR^{\alpha})$ gives us the exact values of the
slopes, and thus allows us to reconstruct the piece wise linear functions that
comprise $f_{D}$. Correspondingly, this allows us to determine which markers
contain a non zero (i.e. $\gamma$) 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 $\gamma R^{\alpha}$ and the additive error is small enough to
determine the correct multiple. Formally, we have that $T<\frac{1}{2}\gamma
R^{\alpha}$ and since each $f_{D}(kR^{\alpha})$ is a multiple of $\gamma
R^{\alpha}$, any entry of a noisy evaluation vector with additive error at
most $T$ can be easily rounded to the correct value, as it lies closest to a
_unique_ multiple of $\gamma R^{\alpha}$.

Now the rest of the proof proceeds via the ‘packing’ argument for proving
lower bounds in differential privacy. Let $Q$ be the queries defined above and
let $P_{D}$ be the set of allowable vectors of evaluations (i.e. those that
achieve entry wise error of at most $T$) for dataset $D$ on $Q$. As argued
above, the probability that $\mathcal{A}$ on dataset $D$ outputs a vector in
$P_{D}$ is at least $2/3$, and all these sets $P_{D}$ are disjoint as argued
above. Furthermore, all datasets differ in at most

$\gamma R^{1-\alpha}\leq 3TR^{1-2\alpha}+R^{1-\alpha}$

data points. Let $D^{\prime}$ be the dataset with all points at $0$. Group
privacy gives us

$\displaystyle 1$ $\displaystyle\geq\sum_{D}\Pr(\mathcal{A}(D^{\prime},Q)\in
P_{D})$
$\displaystyle\geq\sum_{D}e^{-(3TR^{1-2\alpha}+R^{1-\alpha})\varepsilon}\cdot\Pr(\mathcal{A}(D,Q)\in
P_{D})$
$\displaystyle\geq\sum_{D}\frac{2}{3}e^{-(3TR^{1-2\alpha}+R^{1-\alpha})\varepsilon}$
$\displaystyle\geq
2^{R^{1-\alpha}}\cdot\frac{2}{3}e^{-(3TR^{1-2\alpha}+R^{1-\alpha})\varepsilon}.$

It follows that

$3TR^{1-2\alpha}+R^{1-\alpha}\geq\frac{\log(2)R^{1-\alpha}}{\varepsilon}+\frac{\log(2/3)}{\varepsilon}\implies
T\geq\frac{\log(2)R^{\alpha}}{3\varepsilon}+\frac{\log(2/3)}{3\varepsilon
R^{1-2\alpha}}-\frac{R^{\alpha}}{3}.$

Taking $\alpha\rightarrow 1$, we can check that for $\varepsilon\leq 0.2$,
$T\geq 0.02R/\varepsilon=\Omega(R/\varepsilon)$, as desired. ∎

Let us 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
$\mathbb{R}^{d}$ with every coordinate in the interval $[0,R]$, give an
algorithm which outputs a data structure, which given a query
$y\in\mathbb{R}^{d}$, computes the value $\sum_{x\in X}\|x-y\|_{1}$. The goal
is to prove that $\approx Rd/\varepsilon$ additive error is required for
answering queries of this form. For a vector $v$, let $v(j)$ denote its $j$th
coordinate.

######  Theorem 5.2.

For sufficiently large $n$ and $R$ as a function of $d$ and sufficiently small
constant $\varepsilon$, any $\varepsilon$-DP 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=\tilde{\Omega}(Rd/\varepsilon)$.

###### Proof.

We reduce the $1$ dimensional version of the problem to the $d$ dimensional
version which allows us to use the lower bound of Theorem 5.1. Pick $\alpha$
such that $(Rd)^{\alpha}=Rd/\log(Rd)$ and suppose $R$ satisfies $R\geq 2^{Cd}$
for a sufficiently large constant $C$. Furthermore, assume that $R$ is an
integer multiple of $R^{\alpha}$. Now consider the lower bound construction
from Theorem 5.1 where the parameter ‘$R$’ there is replaced by $Rd$ and
$\alpha$ is as stated. Theorem 5.1 implies that an $\varepsilon$-DP data
structure which with probability at least $2/3$ correctly answers any distance
query for a _one dimensional_ input $y$ must have additive error at least
$\Omega((Rd)^{\alpha}/\varepsilon)=\tilde{\Omega}(Rd/\varepsilon)$. We will
now show how to simulate any one dimensional query $y$ on this lower bound
instance with _one_ $d$ dimensional query on a related $d$ dimensional
instance.

To construct the $d$ dimensional instance, consider the interval $[0,Rd]$ as
$d$ different blocks, separated by integer multiples of $R$ as
$[0,R),[R,2R),\ldots$ etc. Note that in the one dimensional hard instance we
are considering from Theorem 5.1, 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 in the marker
construction from 5.1. Due to our choice of $R$ and $\alpha$, it is easy to
see that the number of such balanced allocations is at least
$2^{\Theta((Rd)^{1-\alpha})})$. Let $X_{1}$ be this one dimensional dataset
and let $n^{\prime}$ be the number of (one dimensional) points that are
contained within each block. Consider the $d$ dimensional dataset on
$n^{\prime}$ 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 $i$th block are the $i$th coordinate projections of the dataset. Since
every block has the same number of points, we can construct such a dataset
which is consistent with respect to these coordinate projections222Note there
are many ways to assign the coordinate projections to the points in
$\mathbb{R}^{d}$. We can just consider one fixed assignment.. Denote this
dataset by $X_{d}$. For a one dimensional query $y$, make a vector
$\hat{y}\in\mathbb{R}^{d}$ which just has $y$ copied in all its coordinates.

We have

$\displaystyle\sum_{x\in X_{1}}|y-x|$ $\displaystyle=\sum_{\text{blocks
}b}\sum_{x\in b}|y-x|$ $\displaystyle=\sum_{j=1}^{d}\sum_{x\in
X_{d}}|x(j)-\hat{y}(j)|$ $\displaystyle=\sum_{x\in X_{d}}\|x-\hat{y}\|_{1}.$

Thus, the exact value of the single $d$ dimensional query we have constructed
is equal to the exact value of the one dimensional query we are interested in.
This reduction immediately implies that any $\varepsilon$-DP data structure
which with probability at least $2/3$ answers all $d$ dimensional queries with
additive error at most $T$ must satisfy $T=\tilde{\Omega}(Rd/\varepsilon)$, as
desired. ∎

######  Remark 5.1.

The lower bound is slightly stronger than stated since we only assume the
query vectors have their one dimensional coordinates bounded by
$\tilde{O}(R)$.

######  Remark 5.2.

There is a gap between our upper and lower bounds. Our $\varepsilon$-DP data
structure has a $O(d^{1.5})$ dependency whereas the lower bound we prove only
states $\Omega(d)$ dependency is required. Note that our approx-DP result of
Theorem 4.5 has only $O(d)$ 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.

##  6 Corollaries of Our $\ell_{1}$ data structure

Our high dimensional $\ell_{1}$ distance query result implies a multitude of
downstream results for other distances and functions. For example, it
automatically implies a similar result for the $\ell_{2}$ case via a standard
oblivious mapping from $\ell_{2}$ to $\ell_{1}$. A similar procedure was
applied in Huang & Roth (2014), but using our version of the $\ell_{1}$
distance query obtains superior results for the $\ell_{2}$ case. The
guarantees of the mapping is stated below.

######  Theorem 6.1 (Matousek (2002)).

Let $\gamma\in(0,1)$ and define $T:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ by

$T(x)_{i}=\frac{1}{\beta k}\sum_{j=1}^{d}Z_{ij}x_{j},\quad i=1,\ldots,k$

where $\beta=\sqrt{2/\pi}$ and $Z_{ij}$ are standard Gaussians. Then for every
vector $x\in\mathbb{R}^{d}$, we have

$\Pr[(1-\gamma)\|x\|_{2}\leq\|T(x)\|_{1}\leq(1+\gamma)\|x\|_{2}]\geq
1-e^{-c\gamma^{2}k},$

where $c>0$ is a constant.

The mapping $T$ given by Theorem 6.1 is _oblivious_ to the private dataset and
can be released for free without any loss in privacy, and the distances are
preserved up to a $1+\alpha$ multiplicative error if we take
$k=O(\log(n)\log(1/\alpha)/\alpha^{2})$ for a dataset of size $n$.

######  Corollary 6.2.

Let $X$ be a private dataset of size $n$ with a bounded diameter of $R$ in
$\ell_{2}$. There exists an $\varepsilon$-DP data structure such that for any
fixed query $y$, with probability $99\%$, it outputs $Z$ satisfying
$\left|Z-\sum_{x\in X}\|x-y\|_{2}\right|\leq\alpha\sum_{x\in
X}\|x-y\|_{2}+\tilde{O}\left(\frac{R}{\alpha^{1.5}\varepsilon}\right)$.

###### Proof.

We sketch the argument since it is follows from a combination of the prior
listed results. We just apply the embedding result of Theorem 6.1 as well as
the guarantees of our $\ell_{1}$ distance query data structure from Theorem
4.4. 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
$\tilde{O}(R\alpha^{2})$.333We need to clip the the coordinates of the
embedding output so that every coordinate lies in the correct range. But this
event happens with high probability, so it does not affect the distance-
preserving guarantees. The bound follows by just plugging into the statement
of Theorem 4.4. ∎

Note that minor modifications to the one dimensional $\ell_{1}$ algorithm also
implies the following:

######  Corollary 6.3.

Let $p\geq 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 $\alpha$
scaled down by a factor of $p$ and all counts weighted instead by
$(R/(1+\alpha/p)^{j})^{p}$ in Lines $8$ and $13$ of Algorithm 3. Let
$Z^{\prime}=\sum_{x\in X}|y-x|^{p}$ be the true answer. We have
$\operatorname*{\mathbb{E}}|Z-Z^{\prime}|\leq\alpha
Z^{\prime}+\tilde{O}\left(\frac{R^{p}\log(1/p)}{\varepsilon\sqrt{\alpha}}\right)$.

The higher dimensional version also follows in a similar manner to Theorem 4.4
due to the decomposibility of $\ell_{p}^{p}:\sum_{x\in
X}\|x-y\|_{p}^{p}=\sum_{j=1}^{d}\sum_{x\in X}|x(j)-y(j)|^{p}$.

######  Corollary 6.4.

Let $Z$ be the output of Algorithm 4 but with modifications made as in
Corollary 6.3. Let $Z^{\prime}=\sum_{x\in X}\|y-x\|_{p}^{p}$ be the true
answer. We have, $\operatorname*{\mathbb{E}}|Z-Z^{\prime}|\leq\alpha
Z^{\prime}+\tilde{O}\left(\frac{R^{p}d^{1.5}\log(1/p)}{\varepsilon\sqrt{\alpha}}\right)$.
Furthermore, Algorithm 4 is $\varepsilon$-DP. Similarly to Theorem 4.5, we can
get an $(\varepsilon,\delta)$-DP algorithm satisfying
$\operatorname*{\mathbb{E}}|Z-Z^{\prime}|\leq\alpha
Z^{\prime}+\tilde{O}\left(\frac{R^{p}d\sqrt{\log(p/\delta)}}{\varepsilon\sqrt{\alpha}}\right)$.

###  6.1 An alternate algorithm for $\ell_{2}^{2}$

We give an alternate, simpler algorithm, with slightly better guarantees than
our general $\ell_{p}^{p}$ result.

######  Corollary 6.5.

There exists an $\varepsilon$-DP algorithm which answers the $\ell_{2}^{2}$
distance query with additive error $O\left(\frac{R^{2}d}{\varepsilon}\right)$
in expectation and requires $O(d)$ query time.

###### Proof.

The following identity holds:

$\sum_{x\in X}\|x-y\|_{2}^{2}=\sum_{x\in
X}\|x-\operatorname*{\mathbb{E}}X\|_{2}^{2}+n\|y-\operatorname*{\mathbb{E}}X\|_{2}^{2}$

where $\operatorname*{\mathbb{E}}X=\frac{1}{n}\sum_{x\in X}x$. Note that the
first quantity $\sum_{x\in X}\|x-\operatorname*{\mathbb{E}}X\|_{2}^{2}$ is a
scalar which does not depend on the query $y$. Thus, an alternate
$\varepsilon$-DP algorithm in the $\ell_{2}^{2}$ case is to first release a
(noisy) version of $\sum_{x\in X}\|x-\operatorname*{\mathbb{E}}X\|_{2}^{2}$ as
well as a noisy $\operatorname*{\mathbb{E}}X$.

If all coordinates are in $[0,R]$, then changing one data point can change
every coordinate of $\operatorname*{\mathbb{E}}X$ by a $R/n$ factor. Analyzing
$\sum_{x\in X}\|x-\operatorname*{\mathbb{E}}X\|_{2}^{2}$ is a bit trickier
since changing one data point changes a term in the sum as well as
$\operatorname*{\mathbb{E}}X$. Let $z$ denote the new mean after changing one
data point in $X$ and let $\operatorname*{\mathbb{E}}X$ denote the old mean.
We have

$\displaystyle\sum_{x\in X}\|x-z\|_{2}^{2}$ $\displaystyle=\sum_{x\in
X}\|x-\operatorname*{\mathbb{E}}X+\operatorname*{\mathbb{E}}X-z\|_{2}^{2}$
$\displaystyle=\sum_{x\in
X}\left(\|x-\operatorname*{\mathbb{E}}X\|_{2}^{2}+2\langle
x-\operatorname*{\mathbb{E}}X,\operatorname*{\mathbb{E}}X-z\rangle+\|\operatorname*{\mathbb{E}}X-z\|_{2}^{2}\right).$

Now $n\|\operatorname*{\mathbb{E}}X-z\|_{2}^{2}\leq O(R^{2}d/n)$ and

$\sum_{x\in X}2|\langle
x-\operatorname*{\mathbb{E}}X,\operatorname*{\mathbb{E}}X-z\rangle|\leq
2\sum_{x\in
X}\|x-\operatorname*{\mathbb{E}}X\|_{2}\cdot\|z-\operatorname*{\mathbb{E}}X\|_{2}\leq
O(R^{2}d).$

Thus, the simple Laplacian mechanism of adding
Laplace$(O(R^{2}d/\varepsilon))$ and releasing the value of $\sum_{x\in
X}\|x-\operatorname*{\mathbb{E}}X\|_{2}^{2}$ ensures $\varepsilon/2$-DP. Then
we can release the vector $\operatorname*{\mathbb{E}}X$ by adding
Laplace$(O(Rd/(n\varepsilon)))$ noise to every coordinate, to also ensure
$\varepsilon/2$-DP. Overall, the algorithm is $\varepsilon$-DP. To analyze the
error, note that we get additive error $O(R^{2}d/\varepsilon)$ from the noisy
value $\sum_{x\in X}\|x-\operatorname*{\mathbb{E}}X\|_{2}^{2}$. Assuming $n$
is sufficiently large, we can easily repeat a calculation similar to above
which shows that the overall additive error is at most $O(R^{2}d/\varepsilon)$
in expectation. Indeed, letting $z$ denote the noisy mean we output, we have

$\left|\|y-z\|_{2}^{2}-\|y-\operatorname*{\mathbb{E}}X\|_{2}^{2}\right|\leq
2\|y-z\|_{2}\cdot\|z-\operatorname*{\mathbb{E}}X\|_{2}+\|z-\operatorname*{\mathbb{E}}X\|_{2}^{2},$

from which the conclusion follows. ∎

##  7 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 et al. (2023) stated
in Theorem 3.3.

######  Theorem 7.1.

Let $\alpha\in(0,1)$ and suppose $n\geq
O\left(\frac{1}{\alpha\varepsilon^{2}}\right)$. For $h(x,y)=\|x-y\|_{2}$ and
$\|x-y\|_{2}^{2}$, there exists an algorithm which outputs an $\varepsilon$-DP
data structure for the kernel $f(x,y)=e^{-h(x,y)}$ with the following
properties:

  1. 1.

The expected additive error is $\alpha$,

  2. 2.

The query time is $\tilde{O}\left(d+\frac{1}{\alpha^{4}}\right)$,

  3. 3.

The construction time is $\tilde{O}\left(nd+\frac{n}{\alpha^{4}}\right)$,

  4. 4.

and the space usage is $\tilde{O}\left(d+\frac{1}{\alpha^{4}}\right)$.

Note that our bound improves upon Wagner et al. (2023) in the large dimension
regime $d\gg 1/\alpha^{2}$, by disentangling the factors of $d$ and
$1/\alpha$. We prove this via a 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, as
elaborated in Section 10.

###  7.1 Dimensionality Reduction for Gaussian KDE

We obtain general dimensionality reduction results for the Gaussian and
exponential KDE, using variants of the Johnson-Lindenstrauss (JL) transforms.
See 2 for an overview and motivations.

######  Theorem 7.2 (Dim. Reduction for Gaussian and exponential kernels).

Let $G:\mathbb{R}^{d}\rightarrow\mathbb{R}^{O(\log(1/\alpha)/\alpha^{2})}$ be
the standard Gaussian JL projection where $\alpha<1$ is a sufficiently small
constant. Fix a query $y\in\mathbb{R}^{d}$. Let

$\displaystyle z$ $\displaystyle=\frac{1}{|X|}\sum_{x\in X}f(x,y),$
$\displaystyle\hat{z}$ $\displaystyle=\frac{1}{|X|}\sum_{x\in X}f(Gx,Gy)$

for $f(x,y)=e^{-\|x-y\|_{2}}$ or $f(x,y)=e^{-\|x-y\|_{2}^{2}}$. Then,
$\operatorname*{\mathbb{E}}|z-\hat{z}|\leq\alpha$.

As stated, Theorem 7.2 requires a projection matrix of dense Gaussian random
variables, making the projection time $\tilde{O}(d/\alpha^{2})$. We can speed
this up by using the _fast_ JL transform of Ailon & Chazelle (2009), which
only requires $\tilde{O}(d+1/\alpha^{2})$ time, a significant speedup in the
case where the original dimension $d$ is large.

######  Corollary 7.3.

The same guarantees as in Theorem 7.2 holds if we use the fast JL transform
and project to $O(\log(1/\alpha)^{2}/\alpha^{2})$ dimensions.

In the proof of Theorem 7.2, we use the following facts about a standard
Johnson-Lindenstrauss (JL) projection using Gaussians:

######  Lemma 7.4 (Indyk & Naor (2007); Narayanan et al. (2021)).

Let $x$ be a unit vector in $\mathbb{R}^{d}$ and let $G$ be an (appropriately
scaled) Gaussian random projection to $k$ dimensions. Then for $t>0$:

$\Pr(|\|Gx\|-1|\geq t)\leq e^{-t^{2}k/8},$

and

$\Pr(\|Gx\|\leq 1/t)\leq\left(\frac{3}{t}\right)^{k}.$

###### Proof of Theorem 7.2 .

We give the full proof for $f(x,y)=e^{-\|x-y\|_{2}}$. Carrying out the
identical steps with very minor modifications also implies the same statement
for $f(x,y)=e^{-\|x-y\|_{2}^{2}}$, whose details are omitted. Fix a $x\in X$.
We calculate $\operatorname*{\mathbb{E}}|f(x,y)-f(Gx,Gy)|$ (note the
randomness is over $G$). We consider some cases, depending on the value of
$f(x,y)$.

Case 1: $f(x,y)\leq\alpha$. In this case, if $\|Gx-Gy\|_{2}\geq\|x-y\|_{2}$,
then $f(Gx,Gy)\leq\alpha$, so the additive error
$|f(x,y)-f(Gx,Gy)|\leq\alpha$. Thus, the only relevant event is if the
distance shrinks, i.e., $\|Gx-Gy\|_{2}\leq\|x-y\|_{2}$. If $f(Gx,Gy)\leq
3\alpha$ after the projection, then the additive error $|f(x,y)-f(Gx,Gy)|\leq
O(\alpha)$. Thus, we just have to consider the event $f(Gx,Gy)>3\alpha$.

For this to happen, we note that $\|x-y\|_{2}\geq\log(1/\alpha)$, but $\|Gx-
Gy\|_{2}\leq\log(\alpha^{-1}/3)$. Thus, the distance has shrunk by a factor of

$\frac{\|x-y\|_{2}}{\|Gx-
Gy\|_{2}}\geq\frac{\log\alpha^{-1}}{\log(\alpha^{-1}/3)}=\frac{\log(3)+\log(\alpha^{-1}/3)}{\log(\alpha^{-1}/3)}=1+\frac{\log(3)}{\log(\alpha^{-1}/3)}.$

By setting $k=O(\log(1/\alpha)^{3})$ and $t=O(1/\log(1/\alpha))$ in Lemma 7.4,
the probability of this event is at most $\alpha$, meaning the expected
additive error $\operatorname*{\mathbb{E}}|f(x,y)-f(Gx,Gy)|$ can also be
bounded by $\alpha$.

Case 2: $f(x,y)>\alpha$. This is a more involved case, as we need to handle
both the sub-cases where the distance increases and decreases. Let
$f(x,y)=r>\alpha$.

Sub-case 1: In this sub-case, we bound the probability that $f(Gx,Gy)\leq
r-\alpha/2$. The original distance is equal to $\log(1/r)$ and the new
distance is at least $\log((r-\alpha/2)^{-1})$. The ratio of the new and old
distances is $g(r)=\log(r-\alpha/2)/\log(r)$. Writing $r=w\alpha/2$ for $w\geq
2$, we have

$g(r)=\frac{\log((w-1)\alpha/2)}{\log(w\alpha/2)}=\frac{\log((w-1)/w\cdot
w\alpha/2)}{\log(w\alpha/2)}=1+\frac{\log(1-1/w)}{\log(w\alpha/2)}.$

As $|\log(1-1/w)|=\Theta(1/w)$ for $w\geq 2$, it suffices to upper bound
$|w\log(w\alpha/2)|$ in the interval $2\leq w\leq 2/\alpha$. One can check
that the upper bound occurs for $w=2/(e\alpha)$, resulting in
$\log(1-1/w)/\log(w\alpha/2)=\Omega(\alpha)$. Thus by taking
$k=O(\log(1/\alpha)/\alpha^{2})$ in Lemma 7.4, the probability that
$f(Gx,Gy)\leq r-\alpha/2$ is at most $\alpha$.

Sub-case 2: In this sub-case, we bound the probability that $f(Gx,Gy)\geq
r+\alpha/2$. Again the ratio of the old and new distances is at least
$\log(r)/\log(r+\alpha/2)$. Writing $r=w\alpha/2$ for $w\geq 2$, we have

$\frac{\log(r)}{\log(r+\alpha/2)}=\frac{\log(w\alpha/2)}{\log((w+1)\alpha/2)}=1+\frac{\log(1-1/(w+1))}{\log((w+1)\alpha/2)}.$

Thus a similar calculation as above implies that the probability of
$f(Gx,Gy)\geq r+\alpha/2$ is at most $\alpha$ by setting
$k=O(\log(1/\alpha)/\alpha^{2})$ in Lemma 7.4.

Altogether, we have bounded the probability of $|f(Gx,Gy)-f(x,y)|\geq\alpha/2$
by at most $\alpha$, meaning
$\operatorname*{\mathbb{E}}|f(Gx,Gy)-G(x,y)|\leq\alpha$, as desired.

Then by linearity and the triangle inequality, it follows that

$\operatorname*{\mathbb{E}}|z-\hat{z}|\leq\frac{1}{|X|}\sum_{x}\operatorname*{\mathbb{E}}|f(x,y)-f(Gx,Gy)|\leq\frac{1}{|X|}\sum_{x}O(\alpha)\leq
O(\alpha),$

as desired. ∎

We now prove Corollary 7.3 where we use the fast JL transform of Ailon &
Chazelle (2009). However, the fast JL transform, denoted as $\Pi$, does not
exactly satisfy the concentration bounds of Lemma 7.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 9.2 can be adapted.

######  Theorem 7.5 (Makarychev et al. (2019)).

Let $\Pi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ be the fast JL map of Ailon
& Chazelle (2009). Then for every unit vector $x\in\mathbb{R}^{d}$, we have:

  1. 1.

If $t\leq\frac{\log m}{\sqrt{m}}$, then

$\Pr(|\|\Pi x\|_{2}^{2}-1|\geq t)\leq e^{-\Omega(\frac{t^{2}m}{\log m})}.$

  2. 2.

If $\frac{\log m}{\sqrt{m}}\leq t\leq 1$, then

$\Pr(|\|\Pi x\|_{2}^{2}-1|\geq t)\leq e^{-\Omega(t\sqrt{m})}.$

  3. 3.

If $t\geq 1$, then

$\Pr(|\|\Pi x\|_{2}^{2}-1|\geq t)\leq e^{-\Omega(\sqrt{tm})}.$

###### Proof of Corollary 7.3.

We sketch the modification needed and everything else is identical to the
proof of Theorem 7.2. Going through the proof, we can check that Case $2$ is
the only bottleneck that potentially requires a higher projection dimension
than Theorem 7.2. Here, we need to set $t=\alpha$ in Theorem 7.5 and the first
inequality there is relevant. However, due to the $\log m$ factor in the
denominator, we require an additional $\log(1/\alpha)$ factor in the
projection dimension to achieve the same probaiblity of failure as in the
proof of Theorem 7.2. ∎

###### Proof of Theorem 7.1.

We simply apply our dimensionality reduction result of Corollary 7.3 in a
black-box manner in conjunction with the data structure of Theorem 3.3 from
Wagner et al. (2023): First we project the datapoints to dimension
$\tilde{O}(1/\alpha^{2})$ 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 guarantees of the fast JL transform
Ailon & Chazelle (2009) and Theorem 3.3 from Wagner et al. (2023). ∎

##  8 Sparse Function Approximation

We provide details on the function approximation theory, which are later used
to obtain our final results on smooth kernels, which are stated in Section 9.
We use the fact that a small number of exponential sums can approximate smooth
kernels, enabling us to reduce this case to prior kernels of Section 7. First
we recall a classic result.

######  Theorem 8.1 (Sachdeva & Vishnoi (2014)).

Given $\varepsilon,\delta\in(0,1]$, there exist
$O(\log(1/(\varepsilon\cdot\delta)))$ positive numbers $w_{j},t_{j}>0$, all
bounded by $O\left(\frac{1}{\varepsilon\log(1/\delta)}\right)$, such that for
all $x\in[\varepsilon,1]$ we have
$(1-\delta)x^{-1}\leq\sum_{j}w_{j}e^{-t_{j}x}\leq(1+\delta)x^{-1}$.
Furthermore, $|w_{j}e^{-t_{j}}|\leq O(1)$ for all $j$.

The theorem implies the following useful corollary.

######  Corollary 8.2.

Given $\alpha\in(0,1]$, there exist $O(\log(1/\alpha))$ positive numbers
$w_{j},t_{j}>0$, all bounded by
$O\left(\frac{1}{\alpha\log(1/\alpha)}\right)$, such that for all $x\geq 1$ we
have $\left|\sum_{j}w_{j}e^{-t_{j}x}-x^{-1}\right|\leq\alpha$.

###### Proof.

Let $f(x)$ be the approximation to $x^{-1}$ in the interval $[\alpha,1]$ given
by Theorem 8.1 for $\delta=O(\alpha)$. Now consider $g(x)=\alpha\cdot f(\alpha
x)$. For any $x\in[1,1/\alpha]$, we have

$\displaystyle|g(x)-x^{-1}|$ $\displaystyle=|\alpha\cdot f(\alpha
x)-x^{-1}|\leq|\delta/x|\leq O(\alpha)$

where the first equality follows from the fact that $\alpha\cdot x$ is in the
interval $[\alpha,1]$ for $x\in[1,1/\alpha]$. Thus, $g(x)$ is an additive
$O(\alpha)$ approximation to $x^{-1}$ in the interval $[1,1/\alpha]$. Now
since $g$ and $x^{-1}$ are both decreasing functions of $x$, and
$x^{-1}\leq\alpha$ for $x\geq 1/\alpha$, it immediately follows that $g(x)$ is
an $O(\alpha)$ additive error approximation for $x^{-1}$ for _all_ $x\geq 1$
(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 8.1. ∎

Using Corollary 8.2, we can obtain private KDE data structures for the kernels
$f(x,y)=\frac{1}{1+\|x-y\|_{2}},\frac{1}{1+\|x-y\|_{1}},\frac{1}{1+\|x-y\|_{2}^{2}}$
via a black-box reduction to the corresponding private KDE data structures for
the kernels $e^{-\|x-y\|_{2}},e^{-\|x-y\|_{2}^{2}},$ and $e^{-\|x-y\|_{1}}$.

######  Theorem 8.3.

Let $h(x,y)=\|x-y\|_{2},\|x-y\|_{2}^{2},$ or $\|x-y\|_{1}$ and
$\alpha\in(0,1)$. Suppose there exists an algorithm for constructing an
$\varepsilon$-DP KDE data structure for the kernel $e^{-h(x,y)}$ on a given
dataset of size $n$ which answers any query with expected additive error
$\alpha$, takes $C(n,\alpha)$ construction time, $Q(n,\alpha)$ query time, and
$S(n,\alpha)$ space, assuming $n\geq L(\varepsilon,\alpha)$.

Then, there exists an $\varepsilon$-DP data structure for answering KDE
queries for $f(x,y)=\frac{1}{1+h(x,y)}$ which answers any query with expected
additive error $\alpha$ and the same construction, query, and space as the
exponential case, but with $n$ replaced by $O(n\log(1/\alpha))$ and $\alpha$
replaced by $\alpha/\log(1/\alpha)$ 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(x,y)}$ can be used to answer KDE queries for
$f(x,y)=\frac{1}{1+h(x,y)}$. Let $g(z)$ be the function guaranteed by
Corollary 8.2 which approximates $1/z$ by an additive factor for all $z\geq
1$:

$|\underbrace{\sum_{j}w_{j}e^{-t_{j}z}}_{g(z)}-z^{-1}|\leq
O(\alpha)\quad\forall z\geq 1.$

We have

$\displaystyle\frac{1}{|X|}\sum_{x\in X}f(x,y)=\frac{1}{|X|}\sum_{x\in
X}\frac{1}{1+h(x,y)}=\left(\frac{1}{|X|}\sum_{x\in
X}\sum_{j}w_{j}e^{-t_{j}(1+h(x,y))}\right)+O(\alpha)$
$\displaystyle=\left[\sum_{j}w_{j}e^{-t_{j}}\left(\frac{1}{|X|}\sum_{x\in
X}e^{-t_{j}h(x,y)}\right)\right]+O(\alpha)=\left[\sum_{j}w_{j}e^{-t_{j}}\left(\frac{1}{|X_{j}|}\sum_{x\in
X_{j}}e^{-h(x,y_{j})}\right)\right]+O(\alpha)$

where $X_{j}$ is the dataset $X_{j}=\\{t_{j}\cdot x\mid x\in X\\}$ and $y_{j}$
is the query $t_{j}\cdot y$ in the cases that $h(x,y)=\|x-y\|_{1}$ or
$\|x-y\|_{2}$. In the case where $h(x,y)=\|x-y\|_{2}^{2}$ we have
$X_{j}=\\{\sqrt{t_{j}}\cdot x\mid x\in X\\}$ and $y_{j}$ is the query
$\sqrt{t_{j}}\cdot y$.

Note that the function $g$ is public so the parameters $w_{j}$ and $t_{j}$ are
publicly known (and do not depend on the dataset). Now we simply instantiate
private KDE data structures which approximate each of the sums
$\frac{1}{|X_{j}|}\sum_{x\in X_{j}}e^{-h(x,y)}$. More specifically, we release
$O(\log(1/\alpha))$ kernel KDE data structures, one for each $X_{j}$, and each
of which is $O(\varepsilon/\log(1/\alpha))$-DP. Then the overall data
structures we release are $\varepsilon$-DP by composition. Furthermore, since
each $w_{j}e^{-t_{j}}=O(1)$ and there are only $O(\log(1/\alpha))$ of these
terms, if each data structure has expected additive error
$O(\alpha/\log(1/\alpha))$, then the overall error is $O(\alpha)$ as well. To
summarize, the logarithmic blowup happens in the query/space, as well as any
lower-bound assumption on the size of the dataset. ∎

##  9 New Bounds for Smooth Kernels

In this section, we give new bounds for privately computing KDE queries for
the kernels $f(x,y)=\frac{1}{1+\|x-y\|_{2}},\frac{1}{1+\|x-y\|_{2}^{2}}$, and
$\frac{1}{1+\|x-y\|_{1}}$. Our main result is the following.

######  Theorem 9.1.

Let $\alpha\in(0,1)$ and suppose
$n\geq\tilde{O}\left(\frac{1}{\alpha\varepsilon^{2}}\right)$. For the kernels
$f(x,y)=\frac{1}{1+\|x-y\|_{2}}$ and $f(x,y)=\frac{1}{1+\|x-y\|_{2}^{2}}$,
there exists an algorithm which outputs an $\varepsilon$-DP data structure
with the following properties:

  1. 1.

The expected additive error is $\alpha$,

  2. 2.

The query time is $\tilde{O}\left(d+\frac{1}{\alpha^{4}}\right)$,

  3. 3.

The construction time is $\tilde{O}\left(nd+\frac{n}{\alpha^{4}}\right)$,

  4. 4.

and the space usage is $\tilde{O}\left(d+\frac{1}{\alpha^{4}}\right)$.

For the kernel $f(x,y)=\frac{1}{1+\|x-y\|_{1}}$, we can obtain the following:

  1. 1.

The expected additive error is $\alpha$,

  2. 2.

The query time is $\tilde{O}\left(\frac{d}{\alpha^{2}}\right)$,

  3. 3.

The construction time is $\tilde{O}\left(\frac{nd}{\alpha^{2}}\right)$,

  4. 4.

and the space usage is $\tilde{O}\left(\frac{d}{\alpha^{2}}\right)$.

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. Then we show how to combine our
dimensionality reduction result with classical function approximation theory
to reduce the smooth kernel case to our prior Gaussian and exponential kernel
result of Theorem 7.1. These results assume a similar condition on $n$ as in
our Theorem 7.1 and prior works Wagner et al. (2023):
$n\geq\tilde{O}\left(\frac{1}{\alpha\varepsilon^{2}}\right)$. We present our
novel dimensionality reduction for the kernels
$f(x,y)=\frac{1}{1+\|x-y\|_{2}}$ and $\frac{1}{1+\|x-y\|_{2}^{2}}$.

###  9.1 Dimensionality Reduction

Our main result is the following. As before, we assume the projection is
chosen independently of the dataset and query.

######  Theorem 9.2 (Dim. Reduction for Smooth Kernels).

Let $G:\mathbb{R}^{d}\rightarrow\mathbb{R}^{1/\alpha^{2}}$ be a Gaussian JL
projection where $\alpha<1$ is a sufficiently small constant. Fix a query
$y\in\mathbb{R}^{d}$. Let

$\displaystyle z$ $\displaystyle=\frac{1}{|X|}\sum_{x\in X}f(x,y),$
$\displaystyle\hat{z}$ $\displaystyle=\frac{1}{|X|}\sum_{x\in X}f(Gx,Gy).$

for $f(x,y)=\frac{1}{1+\|x-y\|_{2}}$ or $f(x,y)=\frac{1}{1+\|x-y\|_{2}^{2}}$.
Then, $\operatorname*{\mathbb{E}}|z-\hat{z}|\leq O(\alpha z)$.

A similar corollary as Corollary 9.3 also applies to the exponential and
Gaussian KDE case.

######  Corollary 9.3.

The same dimensionality reduction bound, up to constant factors, holds as in
Theorem 9.2, if we use the fast JL transform.

###### Proof of Theorem 9.2.

We give the full proof for $f(x,y)=\frac{1}{1+\|x-y\|_{2}}$. Carrying out the
identical steps with small modifications also implies the same statement for
$f(x,y)=\frac{1}{1+\|x-y\|_{2}^{2}}$, whose details are omitted. Fix a $x\in
X$. We calculate $\operatorname*{\mathbb{E}}|f(x,y)-f(Gx,Gy)|$ (note the
randomness is over $G$). First we consider the case where the distance $\|Gx-
Gy\|_{2}$ expands. Let $\mathcal{A}_{i}$ be the event that

$\frac{\|Gx-Gy\|_{2}-\|x-y\|_{2}}{\|x-y\|_{2}}\in[\alpha i,\alpha(i+1))$

for $i\geq 0$. We have

$\displaystyle\sum_{i\geq
0}\Pr[\mathcal{A}_{i}]\operatorname*{\mathbb{E}}[|f(x,y)-f(Gx,Gy)|\mid\mathcal{A}_{i}]$
$\displaystyle\leq\sum_{i\geq
0}e^{-i^{2}/8}\left(\frac{1}{1+\|x-y\|_{2}}-\frac{1}{1+\|x-y\|_{2}(1+\alpha(i+1))}\right)$
$\displaystyle=\sum_{i\geq
0}e^{-i^{2}/8}\frac{\|x-y\|_{2}}{1+\|x-y\|_{2}}\cdot\frac{\alpha(i+1)}{1+\|x-y\|_{2}(1+\alpha(i+1))}$
$\displaystyle\leq\sum_{i\geq 0}e^{-i^{2}/8}\frac{\alpha(i+1)}{1+\|x-y\|_{2}}$
$\displaystyle=\frac{\alpha}{1+\|x-y\|_{2}}\sum_{i\geq 0}(i+1)e^{-i^{2}/8}$
$\displaystyle<\frac{7\alpha}{1+\|x-y\|_{2}}.$

We now handle the cases where the distance shrinks. We further subdivide this
case into sub-cases where the distance shrinks by a factor $t$ satisfying
$1\leq t\leq 6$ and the sub-case where $t\geq 6$. To handle the first sub-
case, let $\mathcal{B}_{i}$ be the event that

$\frac{\|x-y\|_{2}}{\|Gx-Gy\|_{2}}\in[1+\alpha i,1+\alpha(i+1))$

for $0\leq i\leq 5/\alpha$. Note that

$\displaystyle\operatorname*{\mathbb{E}}[|f(x,y)-f(Gx,Gy)|\mid\mathcal{B}_{i}]$
$\displaystyle\leq\frac{1}{1+\frac{\|x-y\|_{2}}{(1+\alpha(i+1))}}-\frac{1}{1+\|x-y\|_{2}}$
$\displaystyle=\frac{\|x-y\|_{2}}{\|x-y\|_{2}+1}\cdot\frac{\alpha(i+1)}{1+\|x-y\|_{2}+\alpha(i+1)}$
$\displaystyle\leq\frac{\alpha(i+1)}{1+\|x-y\|_{2}}.$

Furthermore, under the event $\mathcal{B}_{i}$, we have that

$\|x-y\|_{2}-\|Gx-Gy\|_{2}\geq\left(1-\frac{1}{1+\alpha
i}\right)\|x-y\|_{2}\geq\frac{\alpha i}{6}\,\|x-y\|_{2}.$

Thus,

$\displaystyle\sum_{0\leq i\leq
5/\alpha}\Pr[\mathcal{B}_{i}]\operatorname*{\mathbb{E}}[|f(x,y)-f(Gx,Gy)|\mid\mathcal{B}_{i}]$
$\displaystyle\leq\sum_{0\leq i\leq
5/\alpha}e^{-i^{2}/288}\cdot\frac{\alpha(i+1)}{1+\|x-y\|_{2}}$
$\displaystyle\leq\frac{\alpha}{1+\|x-y\|_{2}}\sum_{i\geq
0}(i+1)e^{-i^{2}/288}$ $\displaystyle<\frac{160\alpha}{1+\|x-y\|_{2}}.$

For the other sub-case, write it as the union $\cup_{i=1}^{\infty}D_{i}$ where
$D_{i}$ is the event that

$3\cdot 2^{i+1}\geq\frac{\|x-y\|_{2}}{\|Gx-Gy\|_{2}}\geq 3\cdot 2^{i},$

i.e., $\|Gx-Gy\|_{2}$ shrinks by a factor between $3\cdot 2^{i}$ and $3\cdot
2^{i+1}$. Lemma 7.4 gives us

$\displaystyle\sum_{i\geq
1}\Pr[\mathcal{D}_{i}]\cdot\mathbb{E}[|f(x,y)-f(Gx,Gy)|\mid\mathcal{D}_{i}]$
$\displaystyle\leq\sum_{i\geq
1}\left(\frac{1}{2^{i}}\right)^{k}\cdot\left(\frac{1}{1+\|x-y\|_{2}/2^{i+1}}-\frac{1}{1+\|x-y\|_{2}}\right)$
$\displaystyle\leq\sum_{i\geq
1}\left(\frac{1}{2^{i}}\right)^{1/\alpha^{2}}\cdot\frac{2^{i+1}}{1+\|x-y\|_{2}}$
$\displaystyle\leq\frac{2}{1+\|x-y\|_{2}}\cdot\sum_{i\geq
1}\left(\frac{1}{2^{i}}\right)^{1/\alpha^{2}-1}$
$\displaystyle\leq\frac{2\alpha}{1+\|x-y\|_{2}}.$

Together, the above cases imply that

$\operatorname*{\mathbb{E}}|f(x,y)-f(Gx,Gy)|\leq
O(\alpha)\cdot\frac{1}{1+\|x-y\|_{2}}.$

Then by linearity and the triangle inequality, it follows that

$\operatorname*{\mathbb{E}}|z-\hat{z}|\leq\frac{1}{|X|}\sum_{x}\operatorname*{\mathbb{E}}|f(x,y)-f(Gx,Gy)|\leq
O(\alpha)\cdot\frac{1}{|X|}\sum_{x}\frac{1}{1+\|x-y\|_{2}}\leq O(\alpha z),$

as desired. ∎

###### Proof of 9.3.

We outline the steps in the proof of Theorem 9.2 which required concentration
bounds for the standard JL transform stated in Lemma 7.4, and show how they
can be appropriately replaced by the guarantees of Theorem 7.5. The first step
is the sum bounding the contribution of the events $\mathcal{A}_{i}$, defined
as the event where

$\frac{\|Gx-Gy\|_{2}-\|x-y\|_{2}}{\|x-y\|_{2}}\in[\alpha i,\alpha(i+1))$

for $i\geq 0$. Here, for some smaller values of $i$, the second condition of
Theorem 7.5 is appropriate and for the rest, the third event is appropriate.
Since the sum $\sum_{i\geq 0}ie^{-\sqrt{i}}$ converges to a constant, this
portion of the proof carries through. The same comment applies where we bound
the contribution of the events $\mathcal{B}_{i}$. The last place we need to
check is when we bound the contribution of the events $\mathcal{D}_{i}$. Here,
the third statement of Theorem 7.5 is relevant, and the calculation boils down
to showing the sum $\sum_{i\geq 1}e^{-\Omega(\sqrt{3\cdot 2^{i}-1})}\cdot
2^{i}$ converges to a constant, which is clearly true. ∎

We are now able to prove Theorem 9.1.

###### Proof of Theorem 9.1.

The claimed guarantees follow from a simple combination of the tools we have
developed so far, and a black-box appeal to the result of Theorem 3.3. For the
kernel $f(x,y)=\frac{1}{1+\|x-y\|_{2}}$, we can first perform dimensionality
reduction to $O(1/\alpha^{2})$ dimensions via an oblivious fast JL projection
as stated in Corollary 9.3. We then use the reduction given by Theorem 8.3 to
instantiate $O(\log(1/\alpha))$ copies of private exponential KDE data
structure of Theorem 3.3. The same procedure works for the kernel
$f(x,y)=\frac{1}{1+\|x-y\|_{2}^{2}}$. We don’t have a dimensionality reduction
result for the kernel $f(x,y)=\frac{1}{1+\|x-y\|_{1}}$, so we just repeat the
same steps as above, except we do not perform any dimensionality reduction.
The guarantees follow from the guarantees of Theorem 3.3 along with the black
box reduction given in Theorem 8.3. ∎

##  10 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 as well in the high-dimensional
regime where $d\gg 1/\alpha^{2}$ where $d$ is the original dimension and
$\alpha$ is our desired additive error. Indeed, we can combine our
dimensionality reduction bounds of Theorems 7.2 and 9.2 with any KDE data
structure by first projecting to a 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 our dimensionality reduction
results (the _fast_ JL versions of corollaries 7.3 and 9.3) with prior KDE
data structures whose preprocessing and query times are listed in Table 2, the
following new results easily follow for KDE queries. They give improved query
times for the Gaussian, exponential, and the Cauchy kernels. For the Gaussian
and exponential kernels, we project to dimension $\tilde{O}(1/\alpha^{2})$
where $\alpha$ is the additive error that prior data structures incur and for
the Cauchy kernel, we project to dimension $\tilde{O}(1/\varepsilon^{2})$,
where $1+\varepsilon$ is the multiplicative factors that prior data structures
incur.

######  Theorem 10.1.

By combining with Charikar et al. (2020), for the Gaussian and exponential
kernels, we obtain a data structure which gives a $(1+\varepsilon)$
multiplicative and $\alpha$ additive error guarantee for any fixed query with
$90\%$ probability with the following preprocessing and query time:

  * •

Gaussian kernel: the preprocessing time is
$\tilde{O}\left(\frac{nd}{\varepsilon^{2}\alpha^{0.173+o(1)}}\right)$ and
query time
$\tilde{O}\left(d+\frac{1}{\varepsilon^{2}\alpha^{2.173+o(1)}}\right)$.

  * •

Exponential kernel: the preprocessing time is
$\tilde{O}\left(\frac{nd}{\varepsilon^{2}\alpha^{0.1+o(1)}}\right)$ and query
time $\tilde{O}\left(d+\frac{1}{\varepsilon^{2}\alpha^{2.1+o(1)}}\right)$.

For the kernel $\frac{1}{1+\|x-y\|_{2}^{2}}$, by combining with Backurs et al.
(2018), we obtain a data structure which gives a $(1+\varepsilon)$
multiplicative error with $90\%$ probability for any fixed query with
preprocessing time $\tilde{O}(nd/\varepsilon^{2})$ and query time
$\tilde{O}(d+\frac{1}{\varepsilon^{4}})$.

Table 2:  Prior non-private KDE queries. The query times depend on the dimension $d$, accuracy $\varepsilon$, and additive error $\alpha$. The parameter $\beta$ is assumed to be a constant and log factors are not shown. Kernel | $f(x,y)$ | Preprocessing Time | KDE Query Time | Reference
---|---|---|---|---
Gaussian | $e^{-\|x-y\|_{2}^{2}}$ | $\frac{nd}{\varepsilon^{2}\alpha^{0.173+o(1)}}$ | $\frac{d}{\varepsilon^{2}\alpha^{0.173+o(1)}}$ | Charikar et al. (2020)
Exponential | $e^{-\|x-y\|_{2}}$ | $\frac{nd}{\varepsilon^{2}\alpha^{0.1+o(1)}}$ | $\frac{d}{\varepsilon^{2}\alpha^{0.1+o(1)}}$ | Charikar et al. (2020)
Exponential | $e^{-\|x-y\|_{2}}$ | $\frac{nd}{\varepsilon^{2}\alpha^{0.5}}$ | $\frac{d}{\varepsilon^{2}\alpha^{0.5}}$ | Backurs et al. (2019)
Laplacian | $e^{-\|x-y\|_{1}}$ | $\frac{nd}{\varepsilon^{2}\alpha^{0.5}}$ | $\frac{d}{\varepsilon^{2}\alpha^{0.5}}$ | Backurs et al. (2019)
Rational Quadratic | $\frac{1}{(1+\|x-y\|_{2}^{2})^{\beta}}$ | $\frac{nd}{\varepsilon^{2}}$ | $\frac{d}{\varepsilon^{2}}$ | Backurs et al. (2018)

##  11 Empirical Evaluation

We evaluate our algorithms on 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 $\pm 1$ standard
deviation is shaded where appropriate. All experiments unless stated otherwise
are implemented in Python 3.9 on an M1 MacbookPro with 32GB of RAM.

###  11.1 $\ell_{1}$ Experiments.

The task here is to approximate the (normalized) map
$y\rightarrow\frac{1}{n}\sum_{x\in X}|x-y|$ for a one dimensional dataset $X$
of size $n=10^{3}$, with points randomly picked in $[0,1]$. The query points
are $O(n)$ evenly spaced points in $[0,1]$. We implement our one-dimensional
$\ell_{1}$ 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-
dimensional 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
$\int_{0}^{1}|x-y|\,dx=y^{2}-y+1/2$ for $y\in[0,1]$, allowing us to easily
compare to the ground truth. In Figure 1(a), we plot the average relative
error across all queries as a function of $\varepsilon$. 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 $0$ function, which gives relative error equal to $1$ (the
distance query was always estimated to be $0$) for the values of $\varepsilon$
tested, as shown in Figure 1(a). On the other hand, our algorithm gives non-
trivial empirical performance and its error decreases smoothly as
$\varepsilon$ increases. Indeed, Figure 1(b) shows our output values (scaled
by $1/n$) for various $\varepsilon$’s. We can observe that our estimates
converge to the true function as $\varepsilon$ increases. We observed
qualitatively similar results for both algorithms for the larger $n=10^{6}$
case as well.

(a) Our relative error decreases as $\varepsilon$ increases.

(b) Our performance for various fixed $\varepsilon$.

Figure 1: Our algorithm for $\ell_{1}$ queries has smaller error than prior
SOTA of (Huang & Roth, 2014).

###  11.2 Dimensionality Reduction Experiments.

We empirically demonstrate that dimensionality reduction provides
computational savings for DP-KDE without significantly degrading accuracy. Our
task is to approximate KDE values for the Gaussian kernel
$e^{-\|x-y\|_{2}^{2}}$. We compare against the prior SOTA (Wagner et al.,
2023). Our provable dimensionality reduction result of Theorem 7.2 gives a
general framework: apply an oblivious dimensionality reduction to the data and
use any DP-KDE algorithm in the projected space. Indeed, Theorem 7.1 follows
by applying the framework to the prior SOTA algorithm of Wagner et al. (2023).
Thus in our experiment, we use the randomized dimension reduction of Theorem
7.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 of 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 is 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 2(a) 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 computed by
comparing to the ground truth. Figure 2(b) shows the construction time of the
private data structure and Figure 2(c) shows the total query time on the test
points. We see that the relative error smoothly decreases as we project to
more dimensions, while construction and query time smoothly increase. Note the
construction time includes the time to compute the projection. For example,
projecting to $d=1000$ increases the relative error by $0.015$ in absolute
terms, while reducing the construction time by $\approx 2$x and reducing the
construction time by a factor of $>4$x.

(a) Proj. dimension vs relative error

(b) Construction time

(c) Total query time

Figure 2: Results for our dimensionality reduction experiments.

###  11.3 Differentially Private Classification.

We consider the DP classification task on Cifar-10. The train and test splits
are the private data and query respectively, and the task is to train a
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 an $(\varepsilon,\delta)$-DP distance query data
structure on each class. The classes disjointly partition the data so the
output, which is an $(\varepsilon,\delta)$-DP data structure for each class,
is overall $(\varepsilon,\delta)$-DP (Ponomareva et al., 2023). We use
$f(x,y)=\|x-y\|_{2}^{2}$ since it has the simplest algorithm (see Section
6.1). It essentially reduces to releasing a noisy mean for every class. To
classify a query, we 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 first
give a high-level methodology of prior works: they start with a pre-trained
model on ImageNet444The works consider other alternate datasets, but we only
compare to the Imagenet case. We expect qualitatively similar results when
pre-training with other datasets. and fine tune using DP-gradient descent/SGD.
Note that the vectors we build our private data structures on are the
penultimate layer embeddings of the ResNet pre-trained model used in Yu et al.
(2020). Thus, all methods have the access to the same ‘pre-training’
information.

Note a simple but important point: $\varepsilon,\delta$ are input parameters,
so we 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 vs privacy vs runtime are non-trivial trade-offs.
The full details are given below.

#### Methodology of Yu et al. (2020).

We use the “GP” baseline from Yu et al. (2020), which trains a linear
classifier with DP-SGD (Abadi et al., 2016) on top of features from SimCLR
(Chen et al., 2020b). Deviating from the vanilla DP-SGD, GP uses all samples
to compute gradients at every iteration (i.e., no subsampling) as it was found
to perform better. In our implementation, we use the “r152_2x_sk1” SimCLR
network released from Chen et al. (2020b) to extract the features of the
images. When training the linear classifier, we do a grid search of the hyper-
parameters (learning rate $\in[0.1,0.05,0.1]$, gradient clipping threshold
$\in[1.0,0.1,0.01]$, noise multiplier $\in[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 of De et al. (2022).

De et al. (2022) pretrains the WRN-28-10 network (Zagoruyko & Komodakis, 2016)
on ImageNet and fine-tunes it on CIFAR10 with DP-SGD (Abadi et al., 2016). We
use their official code for the experiments. We do a grid search of the noise
multiplier ($\in[9.4,12.0,15.8,21.1,25.0]$) where the first four values are
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.

#### Our hyper-parameters.

For our method, we take the embeddings from the pre-trained “r152_3x_sk1”
SimCLR network released from Chen et al. (2020b). Our embeddings were in
dimensions $6144$. Since we are computing the $\ell_{2}$ distance squared, we
can apply Johnson-Lindenstrauss to reduce the dimensionality, without any
privacy loss. Furthermore, we can clip the embeddings as well, which reduces
the overall sensitivity of our algorithm (to reduce the $R$ dependency in
Section 6.1) Thus, our hyper-parameters were the projection dimensions, which
we looped from $100$ to $2000$ and the clipping threshold, which we picked
from $10$ choices in $[0.001,1]$.

Figure 3: Runtime vs Accuracy.

Let us temporarily ignore $\delta$ for simplicity of discussion. If they use
$T$ steps of training, every model update step approximately satisfies
$\varepsilon/\sqrt{T}$ privacy (exact bounds depend on the DP composition
formulas), ensuring the overall final model is $(\varepsilon,\delta)$-DP.
Thus, every step for them incurs some privacy budget, with the benefit of
increased accuracy. Therefore, these works can stop training at intermediate
times to obtain a model with stronger privacy guarantees (lower
$\varepsilon$), but worse accuracy. However, the same procedure also gives an
accuracy vs model training time trade-off for these prior works. This is shown
in Figure 3. The right most endpoints of both baselines (the largest times),
correspond to models with $\varepsilon=1$. In other words, their models with
the worst privacy guarantees has the highest accuracy, while also requiring
the longest training time.

In contrast, our algorithm of Section 6.1 simply releases a noisy collection
of fixed vectors. Our data structure construction _time_ , which corresponds
to their model training time, is independent of $(\varepsilon,\delta)$ (but
_accuracy_ depends on them). In Figure 3, we plot the accuracy of our data
structure for $\varepsilon=1$ (we use the best hyper-parameter choices for all
methods). For other values of $\varepsilon$, we would simply incur the same
construction time, but observe differing accuracy since the construction time
is independent of $\varepsilon$ (but again accuracy improves for higher
$\varepsilon$). 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
$\varepsilon=1$ takes $>8.5$ hours on a single NVIDIA RTX A6000 GPU. The
runtimes of De et al. (2022) are even longer since they use larger models.
Thus, as shown in Figure 3, creating our private data structure is $>$ 3
orders of magnitude faster than the time to create models of corresponding
accuracy via the two baselines. Note that we are also using arguably inferior
hardware. The best accuracy of all methods as a function of $\varepsilon$,
ignoring run-time considerations, is shown in Figure 4.

#### Additional Results.

In Figure 4, we also show the $\varepsilon$ vs accuracy trade-off, ignoring
runtime. We plot accuracy as a function of the privacy $\varepsilon$. $\delta$
is always $10^{-5}$. We also plot the best performance of every tested method:
we iterate over the hyper-parameters of all methods including both De et al.
(2022) and Yu et al. (2020) using their code, and we display the best accuracy
for every value of $\varepsilon$. Hyper-parameters are described above. Note
the trivial accuracy is $.1$ via random labels. We see that for small values
of $\varepsilon$, we obtain the second best results, but lag behind both prior
SOTA for large $\varepsilon$ regime. The accuracy in the large
$\varepsilon\geq 1$ regime are $0.87,0.93,0.95$ respectively for ours, Yu et
al. (2020), and De et al. (2022). However, our approach has a major run-time
benefit compared to these prior works, as argued in Section 11. Such a boost
in runtime may justify the drop in accuracy in some applications.

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 our
$\varepsilon=1$ 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.

Figure 4: Accuracy of all methods as a function of $\varepsilon$, ignoring all
run-time constraints. The best hyper-parameter choices are used for all
methods.

##  12 Conclusion

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 to 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 an interesting
direction to derive algorithms for more complicated ‘similarity’ measures,
such as Optimal Transport (OT), although it is not clear what notion of
privacy we should use for such measures. Lastly, generalizing our proof-of-
concept experiment on DP image classification to text or other domains, using
embeddings computed from models such as LLMs, is also an interesting empirical
direction.

## References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pp. 308–318, 2016.
  * Ailon & Chazelle (2009) Nir Ailon and Bernard Chazelle.  The fast johnson–lindenstrauss transform and approximate nearest neighbors.  _SIAM J. Comput._ , 39(1):302–322, 2009.  doi: 10.1137/060673096.  URL https://doi.org/10.1137/060673096.
  * Aldà & Rubinstein (2017) 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.1609/aaai.v31i1.10884.  URL https://doi.org/10.1609/aaai.v31i1.10884.
  * Backurs et al. (2018) 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–626, 2018.
  * Backurs et al. (2019) Arturs Backurs, Piotr Indyk, and Tal Wagner.  Space and time efficient kernel density estimation in high dimensions.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS_ , pp. 15773–15782, 2019.
  * Bakshi et al. (2022) Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, and Samson Zhou.  Subquadratic algorithms for kernel matrices via kernel density estimation.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Becchetti et al. (2019) Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn.  Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma.  In _Proceedings of the 51st annual ACM SIGACT symposium on theory of computing_ , pp. 1039–1050, 2019.
  * Beimel et al. (2014) 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.
  * Blocki et al. (2012) Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet.  The johnson-lindenstrauss transform itself preserves differential privacy.  In _53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012_ , pp. 410–419. IEEE Computer Society, 2012.  doi: 10.1109/FOCS.2012.67.  URL https://doi.org/10.1109/FOCS.2012.67.
  * Blum et al. (2013) Avrim Blum, Katrina Ligett, and Aaron Roth.  A learning theory approach to noninteractive database privacy.  _J. ACM_ , 60(2):12:1–12:25, 2013.  doi: 10.1145/2450142.2450148.  URL https://doi.org/10.1145/2450142.2450148.
  * Boutsidis et al. (2010) Christos Boutsidis, Anastasios Zouzias, and Petros Drineas.  Random projections for $k$-means clustering.  _Advances in neural information processing systems_ , 23, 2010.
  * Carlini et al. (2019) 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.
  * Carlini et al. (2021) 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.
  * Carlini et al. (2022) Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer.  Membership inference attacks from first principles.  In _2022 IEEE Symposium on Security and Privacy (SP)_ , pp. 1897–1914. IEEE, 2022.
  * Carlini et al. (2023a) 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.
  * Carlini et al. (2023b) 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.
  * Charikar & Waingarten (2022) Moses Charikar and Erik Waingarten.  The johnson-lindenstrauss lemma for clustering and subspace approximation: From coresets to dimension reduction.  _CoRR_ , abs/2205.00371, 2022.  doi: 10.48550/arXiv.2205.00371.  URL https://doi.org/10.48550/arXiv.2205.00371.
  * Charikar et al. (2020) Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis.  Kernel density estimation through density constrained near neighbor search.  _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , pp. 172–183, 2020.
  * Chen et al. (2020a) 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 on computer and communications security_ , pp. 343–362, 2020a.
  * Chen et al. (2020b) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pp. 1597–1607. PMLR, 2020b.
  * Cohen et al. (2015) Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality 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.
  * Coleman & Shrivastava (2021) 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 on Computer and Communications Security_ , pp. 3252–3265, 2021.
  * De et al. (2022) Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle.  Unlocking high-accuracy differentially private image classification through scale.  _arXiv preprint arXiv:2204.13650_ , 2022.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pp. 248–255. Ieee, 2009.
  * Dwork et al. (2006) 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.
  * Dwork et al. (2010) 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. IEEE Computer Society, 2010.  doi: 10.1109/FOCS.2010.12.  URL https://doi.org/10.1109/FOCS.2010.12.
  * Feldman et al. (2009) 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.
  * Fredrikson et al. (2015) Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , pp. 1322–1333, 2015.
  * Gupta et al. (2012) Anupam Gupta, Aaron Roth, and Jonathan R. Ullman.  Iterative constructions and private data release.  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/978-3-642-28914-9“˙19.  URL https://doi.org/10.1007/978-3-642-28914-9_19.
  * Haim et al. (2022) 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.
  * Hall et al. (2013) Rob Hall, Alessandro Rinaldo, and Larry Wasserman.  Differential privacy for functions and functional data.  _The Journal of Machine Learning Research_ , 14(1):703–727, 2013.
  * Hardt & Talwar (2010) 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.
  * Hofmann et al. (2008) Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola.  Kernel methods in machine learning.  _The annals of statistics_ , 36(3):1171–1220, 2008.
  * Hou et al. (2023) 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.
  * Huang & Roth (2014) Zhiyi Huang and Aaron Roth.  Exploiting metric structure for efficient private query release.  In Chandra Chekuri (ed.), _Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014_ , pp. 523–534. SIAM, 2014.  doi: 10.1137/1.9781611973402.39.  URL https://doi.org/10.1137/1.9781611973402.39.
  * Indyk & Naor (2007) Piotr Indyk and Assaf Naor.  Nearest-neighbor-preserving embeddings.  _ACM Transactions on Algorithms (TALG)_ , 3(3):31–es, 2007.
  * Indyk & Silwal (2022) 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 Neural Information Processing Systems_ , volume 35, pp. 35576–35589. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/e7599c4b309e39e444a7dcf92572fae1-Paper-Conference.pdf.
  * Izzo et al. (2021) Zachary Izzo, Sandeep Silwal, and Samson Zhou.  Dimensionality reduction for wasserstein barycenter.  _Advances in neural information processing systems_ , 34:15582–15594, 2021.
  * Johnson & Lindenstrauss (1984) W. Johnson and J. Lindenstrauss.  Extensions of lipschitz maps into a hilbert space.  _Contemporary Mathematics_ , 26:189–206, 01 1984.  doi: 10.1090/conm/026/737400.
  * Li et al. (2021) Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto.  Large language models can be strong differentially private learners.  In _International Conference on Learning Representations_ , 2021.
  * Lin et al. (2020) Zinan Lin, Alankar Jain, Chen Wang, Giulia Fanti, and Vyas Sekar.  Using gans for sharing networked time series data: Challenges, initial promise, and open questions.  In _Proceedings of the ACM Internet Measurement Conference_ , pp. 464–483, 2020.
  * Lin et al. (2023) Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin.  Differentially private synthetic data via foundation model apis 1: Images.  _arXiv preprint arXiv:2305.15560_ , 2023.
  * Luo et al. (2023) Xinyu Luo, Christopher Musco, and Cas Widdershoven.  Dimensionality reduction for general kde mode finding.  In _International Conference on Machine Learning_. PMLR, 2023.
  * Makarychev et al. (2019) Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Performance of johnson-lindenstrauss transform for _k_ -means and _k_ -medians clustering.  In Moses Charikar and Edith Cohen (eds.), _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019_ , pp. 1027–1038. ACM, 2019.  doi: 10.1145/3313276.3316350.  URL https://doi.org/10.1145/3313276.3316350.
  * Matousek (2002) Jirí Matousek.  _Lectures on discrete geometry_ , volume 212 of _Graduate texts in mathematics_.  Springer, 2002.  ISBN 978-0-387-95373-1.
  * Narayanan et al. (2021) Shyam Narayanan, Sandeep Silwal, Piotr Indyk, and Or Zamir.  Randomized dimensionality reduction for facility location and single-linkage clustering.  In _International Conference on Machine Learning_ , pp. 7948–7957. PMLR, 2021.
  * Phillips & Tai (2020) Jeff M. Phillips and Wai Ming Tai.  Near-optimal coresets of kernel density estimates.  _Discret. Comput. Geom._ , 63(4):867–887, 2020\.  doi: 10.1007/s00454-019-00134-6.  URL https://doi.org/10.1007/s00454-019-00134-6.
  * Ponomareva et al. (2023) 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_ , 77:1113–1201, 2023.
  * Radford et al. (2021) 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 on machine learning_ , pp. 8748–8763. PMLR, 2021.
  * Sachdeva & Vishnoi (2014) Sushant Sachdeva and Nisheeth K. Vishnoi.  Faster algorithms via approximation theory.  _Found. Trends Theor. Comput. Sci._ , 9(2):125–210, 2014.  doi: 10.1561/0400000065.  URL https://doi.org/10.1561/0400000065.
  * Schölkopf et al. (2002) Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press, 2002.
  * Shawe-Taylor et al. (2004) John Shawe-Taylor, Nello Cristianini, et al.  _Kernel methods for pattern analysis_.  Cambridge university press, 2004.
  * Singhal & Steinke (2021) Vikrant Singhal and Thomas Steinke.  Privately learning subspaces.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pp. 1312–1324, 2021.  URL https://proceedings.neurips.cc/paper/2021/hash/09b69adcd7cbae914c6204984097d2da-Abstract.html.
  * Szegedy et al. (2016) Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 2818–2826, 2016.
  * Tramèr et al. (2022) Florian Tramèr, Reza Shokri, Ayrton San Joaquin, Hoang Le, Matthew Jagielski, Sanghyun Hong, and Nicholas Carlini.  Truth serum: Poisoning machine learning models to reveal their secrets.  In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_ , pp. 2779–2792, 2022.
  * Vadhan (2017a) Salil Vadhan.  _The Complexity of Differential Privacy_ , pp. 347–450.  Springer, Yehuda Lindell, ed., 2017a.  URL https://link.springer.com/chapter/10.1007/978-3-319-57048-8_7.
  * Vadhan (2017b) Salil Vadhan.  _The Complexity of Differential Privacy_ , pp. 347–450.  Springer, Yehuda Lindell, ed., 2017b.  URL https://link.springer.com/chapter/10.1007/978-3-319-57048-8_7.
  * Wagner et al. (2023) Tal Wagner, Yonatan Naamad, and Nina Misrha.  Fast private kernel density estimation via locality sensitive quantization.  In _International Conference on Machine Learning_. PMLR, 2023.
  * Wang et al. (2016) Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang.  Differentially private data releasing for smooth queries.  _The Journal of Machine Learning Research_ , 17(1):1779–1820, 2016.
  * Yin et al. (2022) Yucheng Yin, Zinan Lin, Minhao Jin, Giulia Fanti, and Vyas Sekar.  Practical gan-based synthetic ip header trace generation using netshare.  In _Proceedings of the ACM SIGCOMM 2022 Conference_ , pp. 458–472, 2022.
  * Yu et al. (2020) 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 Representations_ , 2020.
  * Yu et al. (2021) 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.
  * Yu et al. (2023) 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.13865_ , 2023.
  * Yue et al. (2022) 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.14348_ , 2022.
  * Zagoruyko & Komodakis (2016) Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  _arXiv preprint arXiv:1605.07146_ , 2016.