# Profile Reconstruction from Private Sketches

Hao WU  Rasmus Pagh

###### Abstract

Given a multiset of $n$ items from $\mathcal{D}$, the _profile reconstruction_
problem is to estimate, for $t=0,1,\dots,n$, the fraction $\vec{f}[t]$ of
items in $\mathcal{D}$ that appear exactly $t$ times. We consider
differentially private profile estimation in a distributed, space-constrained
setting where we wish to maintain an updatable, private sketch of the multiset
that allows us to compute an approximation of
$\vec{f}=(\vec{f}[0],\dots,\vec{f}[n])$. Using a histogram privatized using
discrete Laplace noise, we show how to “reverse” the noise, using an approach
of Dwork et al. (ITCS ’10). We show how to speed up their LP-based technique
from polynomial time to $O(d+n\log n)$, where $d=|\mathcal{D}|$, and analyze
the achievable error in the $\ell_{1}$, $\ell_{2}$ and $\ell_{\infty}$ norms.
In all cases the dependency of the error on $d$ is $O(1/\sqrt{d})$ — we give
an information-theoretic lower bound showing that this dependence on $d$ is
asymptotically optimal among all private, updatable sketches for the profile
reconstruction problem with a high-probability error guarantee.

Machine Learning, ICML

##  1 Introduction

The _profile_ is a fundamental statistic of a data set. Given a multiset of
$n$ items from a finite domain $\mathcal{D}$, the profile is a vector
$\vec{f}$ whose $t^{(th)}$ entry equals the fraction $\vec{f}[t]$ of items in
$\mathcal{D}$ that appear exactly $t$ times. The concept has arisen in many
contexts under various names, including _rarity_ , _incidence_ , _fingerprint_
, _prevalence_ , _collision statistics_ , _anonymous histogram_ ,
_unattributed histogram_ , and _histogram of histograms_. Besides succinctly
summarizing frequency information in a dataset, for example the degree
distribution in a graph, a profile is sufficient to compute any _symmetric_
function of the dataset histogram (Chen et al., 2024).

In settings where space, communication or privacy constraints prevents us from
computing the exact profile it is of interest to _approximate_ the profile
$\vec{f}$ by a vector $\vec{r}$ such that $\vec{r}-\vec{f}$ has small
$\ell_{p}$ norm for some parameter $p$.

Streaming algorithms. Datar & Muthukrishnan (2002) considered estimating the
profile in a streaming setting, showing that a small sample of the domain
$\mathcal{D}$ suffices to ensure small error (they focus on $\ell_{1}$ error,
but the technique applies to general $\ell_{p}$ norms). The sample can be
described by a compact hash function, making it suitable for use in
distributed settings. More recently, Chen, Indyk, and Woodruff (2024) improved
the error bound, and showed matching space lower bounds for streaming
algorithms. General estimators for symmetric functions based on samples were
presented and analyzed by Acharya, Das, Orlitsky, and Suresh (2017).

Differentially private algorithms. Differential privacy (Dwork et al., 2006)
is a leading approach to ensure that the output of an algorithm, from simple
statistics to machine learning models, does not reveal too much about the
inputs. It is one of the central techniques for enabling collection of
statistics, training of machine learning models, and other computations on
data that may hold sensitive information. We will focus on the privacy of
individual elements in the multiset, that is, our differential privacy
guarantee is defined in terms of pairs of neighboring datasets where the
number of occurrences of a particular element differs by 1, and that are
otherwise identical.

In the _central model_ of differential privacy (where a trusted curator holds
the input data), privately releasing a _profile_ with small $\ell_{2}$ error
was considered by Hay, Li, Miklau, and Jensen (2009, 2010), the latter
focusing on the application of graph degree distributions. Private synthetic
graphs with specific degree distribution were also studied by Karwa and
Slavkovic (2012).

Motivated by estimating repetitions in password datasets, Blocki, Datta, and
Bonneau (2016) studied differentially private protocols for profile
estimation, focusing on $\ell_{2}$ error.

Suresh (2019) considered an alternative (incomparable) error metric, where the
profile is represented in the “verbatim” form of a vector encoding all
frequencies in sorted order. They presented an algorithm to release verbatim
profiles with a small $\ell_{1}$ error. Recently Manurangsi (2022) showed
improved tight upper and lower bounds on the privacy/$\ell_{1}$ error trade-
off for verbatim profiles.

Differentially private distributed/streaming algorithms Dwork, Naor, Pitassi,
Rothblum, and Yekhanin (2010) studied profile estimation (referred to as _$t$
-incidence_) in the pan-private streaming setting, where the internal state of
the streaming algorithm must satisfy a differential privacy guarantee. Pan-
private algorithms protect against _intrusions_ , i.e., unintended release of
the internal state of the algorithm. Unlike the other works on private profile
estimation mentioned above, the neighboring relation considered by Dwork et
al. (2010) is defined on the profile itself, i.e., datasets are neighboring if
they differ _by any amount_ on the count of one item (so the profiles differ
in two entries). In a nutshell111Since there is no good bound on the
difference between histograms with their notion of neighboring datasets, Dwork
et al. (2010) actually work with histograms of counts modulo several small
random primes $p_{i}$, and use these to estimate profiles on the counts modulo
$p_{i}$, which are in turn used to estimate the original profile. In our
context this complication goes away., their algorithm works by maintaining a
_histogram_ that stores the number of occurrences of each item perturbed by
additive noise. Since the noisy histogram is a linear function of the
histogram it is _updatable_ when the count of an item changes. Dwork et al.
(2010) finally show how to derive an estimate of the profile from the noisy
histogram by solving a linear programming problem. The size of the sketch
required for achieving $\ell_{\infty}$ error $\alpha$ on the profile estimate
with high probability is stated as $\text{poly}(\log
n,1/\varepsilon,1/\alpha)$ with unspecified exponents. Unfortunately, the
paper does not analyze for what values of $\alpha$ it is possible to solve the
linear program (with high probability), meaning that the privacy-utility
trade-off obtained remains unclear.

###  1.1 Our contributions

In this paper we study how to approximate the profile from a noisy histogram
of the data. Specifically, we consider the setting where _discrete Laplace_
noise has been added to the counts in the histogram. (This is different from
the noise distribution used by Dwork et al. (2010), which is nearly uniform
modulo a small prime $p_{i}$.) Computing the empirical profile directly from
the noisy histogram can lead to large errors. For example, consider the
situation where $\mathcal{D}$ has $n$ items that each appear once in the
dataset and let $\varepsilon>0$ be a small constant. After adding noise to the
histogram to make it $\varepsilon$-differentially private (and possibly
rounding up negative values to 0), the fraction of items with a count of 1
will be $\approx\varepsilon$, far from the true fraction of $1$.

Instead we use an approach similar to that of Dwork et al. (2010) to
approximately invert the effect of the noise. Since we use a known noise
distribution, the _expected_ value of the profile computed from the noisy
histogram is a linear function of the true profile. Due to concentration we
can argue that the observed values in the profile based on the noisy histogram
are in fact close to the expected ones, and thus it makes sense to find a
histogram whose expected profile after noise would be close to the observed
noisy profile. Unlike Dwork et al. (2010) who formulate this as a feasibility
question of a linear program, we show that it can be reduced to solving a
linear $\ell_{p}$-regression problem with a circulant matrix, paving the way
for a near-linear time algorithm. We also give a careful analysis of the error
$\mathcal{E}\textit{rr}_{p}$ in $\ell_{p}$ norm, for $p\in\\{1,2,\infty\\}$,
showing the following upper bound:

######  Theorem 1.1.

Let $\eta\in(0,1)$, $\varepsilon>0$. Denote
$B\doteq\frac{1}{\varepsilon}\ln\big{(}\max\left\\{{\frac{2d}{\eta(e^{\varepsilon}+1)},\frac{8\,e^{\varepsilon}}{e^{2\varepsilon}-1}}\right\\}\big{)}$,
and assume that $n\geq B$. There is an algorithm that, given a private version
$\tilde{h}$ of a $d$-dimensional histogram $\vec{h}$ published by the
$\varepsilon$-DP discrete Laplace mechanism and a parameter $p=1,2$ or
$\infty$, returns an approximate $\vec{r}$ for the profile $\vec{f}$ of
$\vec{h}$ in $O(d+n\log n)$ time. Moreover, with probability at least
$1-\eta$, the estimation error
$\mathcal{E}\textit{rr}_{p}\doteq||\vec{r}-\vec{f}||_{p}$ satisfies

$\displaystyle\mathcal{E}\textit{rr}_{1}$ $\displaystyle\in
O{\left({\left(\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\right)}^{2}{\left(\frac{\sum_{t=-B}^{n+B}\sqrt{\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}}{\sqrt{d}}+\sqrt{\frac{2\ln\frac{1}{\eta}}{d}}\right)}\right)}$
(1) $\displaystyle\mathcal{E}\textit{rr}_{2}$ $\displaystyle\in
O{\left({\left(\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\right)}^{2}\sqrt{\frac{\ln\frac{1}{\eta}}{d}}\right)}$
(2) $\displaystyle\mathcal{E}\textit{rr}_{\infty}$
$\displaystyle\in{\left({\left(\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\right)}^{2}{\left(\sqrt{\frac{2\,{\left(e^{\varepsilon}-1\right)}}{d\,{\left(e^{\varepsilon}+1\right)}}\ln\frac{n}{\eta}}+\frac{\ln\frac{n}{\eta}}{3\,d}\right)}\right)}$
(3)

where $\tilde{f}[t]=\frac{1}{d}|\\{\ell\in\mathcal{D}:\tilde{h}[\ell]=t\\}|,$
$t=\text{-}B,\ldots,n+B.$

Notice that the error bounds in all three norms are proportional to
$O(1/\sqrt{d})$, where $d$ is the domain size. As we will discuss below, this
dependence is optimal under $\varepsilon$-differential privacy for updatable
sketches. On the other hand, when $\varepsilon\in O(1)$, the
$O(1/\varepsilon^{1.5})$ dependence for $\mathcal{E}\textit{rr}_{\infty}$ on
the privacy parameter does not match the $\Omega(1/\varepsilon)$ lower bound
on the error of releasing a single counter (Hardt & Talwar, 2010). We note
that the bound on $\mathcal{E}\textit{rr}_{1}$ is a refinement of the bound
implied by the bound on $\mathcal{E}\textit{rr}_{2}$ and the fact that
$\ell_{1}$ distances in $n$ dimensions are at most $\sqrt{n}$ times larger
than $\ell_{2}$ distances. Since errors are normalized by a $1/d$ factor one
might hope to achieve errors that decrease more rapidly with $d$ than those of
Theorem 1.1. However, we show the following lower bound:

######  Theorem 1.2.

For every $\varepsilon$-DP and updatable algorithm
$\mathcal{A}:[{0}\,.\,.\,{n}]^{d}\rightarrow\mathcal{Y}$, and every profile
estimation algorithm $\mathcal{R}:\mathcal{Y}\rightarrow[0,1]^{n+1}$, if the
sensitivity $\Delta_{\mathcal{R}\circ\mathcal{A}}\in
o\big{(}\frac{1}{\sqrt{d}}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}\big{)}$
(for some universal constant $c>0$), then there exists an input
$\vec{h}\in[{0}\,.\,.\,{n}]^{d}$ such that

$\begin{array}[]{c}\operatorname*{\mathbb{E}}\left[\left\|{\vec{f}-\mathcal{R}{\left(\mathcal{A}(\vec{h})\right)}}\right\|_{\infty}\right]\in\Omega\Big{(}\frac{1}{\sqrt{d}\cdot
e^{c\cdot\varepsilon}}\Big{)}.\end{array}$ (4)

This lower bound is not limited to algorithms reconstructing the profile from
a perturbed histogram published by the discrete Laplace mechanism. Instead, it
applies to a broader class of algorithms that attempt to reconstruct the
profile from outputs of _updatable_ $\varepsilon$-differentially private
algorithms. The formal definition of an “updatable” algorithm and the
sensitivity $\Delta_{\mathcal{R}\circ\mathcal{A}}$ will be given in Section 5.
Informally, the former denotes the property that when the input histogram
$\vec{h}$ is updated, we can directly modify $\mathcal{A}(\vec{h})$ to reflect
the change, and the latter represents the maximum distance between the
profiles reconstructed from the outputs of $\mathcal{A}$ for neighboring
histograms. The lower bound shows that an error of $\Omega(1/\sqrt{d})$ is
unavoidable for such sketches.

###  1.2 Technical overview

As noted by Datar & Muthukrishnan (2002) and Dwork et al. (2010) it suffices
to estimate the profile of a sample of elements from the domain, since the
profile of the sample will closely resemble the true profile. Thus we will
assume that this sampling step has already been done, and consider the full
histogram of (sampled) items. The final error bounds add the sampling error
and the error from privacy using the triangle inequality, but here we focus on
the latter.

Given a noisy histogram $\tilde{h}$, we can compute an empirical profile
$\tilde{f}$. As the noisy histogram is obtained by adding independent noise to
each coordinate of the full histogram $\vec{h}$, the empirical profile can be
viewed as a function of a set of independent random variables and should
concentrate around its expectation $\mathbb{E}[\tilde{f}]$. Hence, we regard
the empirical profile as a reliable representative of its expectation.

Although the expectation $\mathbb{E}[\tilde{f}]$ itself may not be a good
approximation of the original profile $\vec{f}$ of $\vec{h}$, there is a
subtle connection between them: $\mathbb{E}[\tilde{f}]$ can be computed via a
linear transform of the original profile $\vec{f}$. Due the symmetry of
discrete Laplace noise, we can write the linear transform as
$\boldsymbol{A}\vec{f}$ for a circulant matrix $\boldsymbol{A}$ with non-zero
eigenvalues.

Since the inversion for such linear transforms can be computed in $O(n\log n)$
time via Fast Fourier transform (FFT), it motivates us to compute
$\boldsymbol{A}^{-1}\tilde{f}$ as an approximation of the true profile.
However, such an approximation may not be a valid profile: it may contain
coordinates outside $[0,1]$, and its coordinates do not sum up to $1$. We will
design a systematic procedure for fixing these violations, which also relies
on FFT and runs in $O(n\log n)$ time.

The approximation error comes from three sources: the deviation of $\tilde{f}$
from its expectation, the inverse linear transform, and the violation fixing
procedure. Each part will be analyzed separately. The second part, in
particular, might be of independent interest as it involves examining various
matrix norms of $\boldsymbol{A}^{-1}$, which naturally arises from the
discrete Laplace mechanism.

To establish a lower bound, we employ a reduction from the $d$-dimensional
inner product estimation problem in the framework of two-party differential
privacy where an error of $\Omega(\sqrt{d})$ is inevitable (McGregor et al.,
2010; Haitner et al., 2022).

##  2 Problem Description

Let $\mathcal{D}\doteq\left\\{{1,\ldots,d}\right\\}$ be a set of $d$ items.
Given a multiset of $n$ items from $\mathcal{D}$, for each item
$\ell\in\mathcal{D}$, let $\vec{h}[\ell]$ be the number of times it appears in
the multiset. The _histogram_ is a vector
$\vec{h}\doteq{({\vec{h}[1],\ldots,\vec{h}[d]})}\in[{0}\,.\,.\,{n}]^{d}$. The
_profile_ of the histogram $\vec{h}$ is a frequency vector
$\vec{f}\doteq(\vec{f}[0],\ldots,\vec{f}[n])\in[0,1]^{n+1},$ where
$\vec{f}[t]={\left(1/d\right)}\cdot|\\{\ell\in\mathcal{D}:\vec{h}[\ell]=t\\}|$
is the fraction of elements in $\mathcal{D}$ which appears $t$ times in the
multiset, for each $t\in[{0}\,.\,.\,{n}]$.

Our goal is to design an efficient and accurate algorithm for estimating the
profile $\vec{f}$ from a private histogram $\tilde{h}$ output by the _discrete
Laplace mechanism_ (or geometric mechanism) due to Ghosh, Roughgarden, and
Sundararajan (2009).

#### Discrete Laplace Mechanism.

Given an input histogram $\vec{h}$, the mechanism aims at outputting a
perturbed version $\tilde{h}$ of $\vec{h}$ that is insensitive to the
addition/removal of an arbitrary item in the multiset. Specifically, the
mechanism creates $\tilde{h}$ by adding independent noises to each coordinate
of $\vec{h}$, such that

$\tilde{h}[\ell]=\vec{h}[\ell]+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right),\,\forall\ell\in\mathcal{D},$

where $\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)$ denotes a
random variable following discrete Laplace distribution:
$\Pr\left[\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)=t\right]=\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}\cdot
e^{-\varepsilon\cdot\left|{t}\right|},\,\forall t\in\mathbb{Z}.$ In practice,
a clipping step can be applied after coordinate perturbation:

$\tilde{h}[\ell]=\text{clip}{\left[{{\vec{h}[\ell]+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)},{0},{n}}\right]},\,\forall\ell\in\mathcal{D}.$

where
$\text{clip}[\vec{h}[\ell]+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right),0,n]\doteq\max\\{0,\min\\{\vec{h}[\ell]$
$+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right),n\\}\\}$ ensures
the returned value is in $[0\,.\,.\,n]$.

Privacy Guarantee. The privacy guarantee provided by the mechanism is measured
by the framework of _differential privacy_. Formally, we call two histograms
$\vec{h}$ and $\vec{h}^{\prime}$ _neighboring_ , written as
$\vec{h}\sim\vec{h}^{\prime}$, if $\exists\ell\in\mathcal{D}$, s.t.,
$|\vec{h}[\ell]-\vec{h}^{\prime}[\ell]|\leq 1$, and
$\forall\ell^{\prime}\in\mathcal{D}\setminus\left\\{{\ell}\right\\}$, it holds
that $\vec{h}[\ell^{\prime}]=\vec{h}^{\prime}[\ell^{\prime}]$. The discrete
Laplace mechanism ensures that the output histograms have similar
distributions for neighboring inputs.

######  Definition 2.1 (${\varepsilon}$-Differentially Privacy (Dwork & Roth,
2014)).

Given $\varepsilon>0$, a randomized algorithm
$\mathcal{A}:\mathbb{N}^{d}\rightarrow\mathcal{Z}$ is called
${\varepsilon}$-differentially private (DP), if for every
$\vec{h},\vec{h}^{\prime}\in\mathbb{N}^{d}$ such that
$\vec{h}\sim\vec{h}^{\prime}$, and all (measurable) $Z\subseteq\mathcal{Z}$,

$\begin{array}[]{c}\Pr\left[\mathcal{A}(\vec{h})\in Z\right]\leq
e^{\varepsilon}\cdot\Pr[\mathcal{A}(\vec{h}^{\prime})\in Z]\,.\end{array}$ (5)

Ghosh et al. (2009) showed that the discrete Laplace mechanism is
$\varepsilon$-DP (with or without the clipping step).

##  3 Preliminaries

######  Definition 3.1 (Circulant Matrix).

Let $p\in\mathbb{N}^{+}$ and
$\vec{c}=\begin{bmatrix}c_{0},c_{1},\cdots,c_{p-1}\end{bmatrix}\in\mathbb{C}^{p}$
be a row vector. Define the (right) circular shift operator
$\sigma:\mathbb{C}^{p}\rightarrow\mathbb{C}^{p}$ by
$\sigma{\left(\vec{c}\right)}=\begin{bmatrix}c_{p-1},c_{0},\cdots,c_{p-2}\end{bmatrix}.$
The circulant matrix $\boldsymbol{\text{circ}}{\left(\vec{c}\right)}$ is a
matrix whose rows
$\vec{c},\sigma{\left(\vec{c}\right)},\ldots,\sigma^{p-1}{\left(\vec{c}\right)}$
are generated by iteratively applying the operator $\sigma$ on $\vec{c}$.

######  Fact 3.2 (Eigenvectors and Eigenvalues (Gray, 2005)).

Let $w_{t}\doteq e^{-\frac{2\pi t\cdot i}{p}},$ for each
$t\in[{0}\,.\,.\,{p-1}]$. Then the eigenvalues
$\varphi_{0},\ldots,\varphi_{p-1}$ and the corresponding eigenvectors
$\vec{v}_{0},\ldots,\vec{v}_{p-1}$ of the matrix
$\boldsymbol{\text{circ}}{\left(\vec{c}\right)}$ are given by

$\displaystyle\varphi_{t}$ $\displaystyle\doteq
c_{0}+c_{1}(w_{t})^{1}+\cdots+c_{p-1}(w_{t})^{p-1},$ (6)
$\displaystyle\vec{v}_{t}$ $\displaystyle\doteq
1/{\sqrt{p}}\cdot\begin{bmatrix}1,(w_{t})^{1},\cdots,(w_{t})^{p-1}\end{bmatrix}^{\top}.$
(7)

######  Fact 3.3 (Fast Fourier Transform (FFT) (Cormen et al., 2009)).

Let
$\boldsymbol{V}\doteq{\left[{\vec{v}_{0}\cdots\vec{v}_{p-1}}\right]}\in\mathbb{C}^{p\times
p}$ be the matrix composed of column vectors $\vec{v}_{t}$ (defined in
Equation (7)) for $t=0,1,\ldots,p-1.$ Then for each
$\vec{x}\in\mathbb{C}^{p}$, $\boldsymbol{V}\vec{x}$,
$\boldsymbol{V}^{-1}\vec{x}$, $\vec{x}^{\top}\boldsymbol{V}$ and
$\vec{x}^{\top}\boldsymbol{V}^{-1}$ can be computed in $O(p\log p)$ time.

##  4 Near-linear Time Algorithm

In this section, we introduce an algorithm that achieves the properties stated
in Theorem 1.1. Our presentation is structured as follows. In Section 4.1, we
demonstrate that we can transform the histograms published by the discrete
Laplace mechanisms with the clipping step into ones without clipping steps,
ensuring they follow the same distribution. This allows us to address
perturbed histograms with and without clipping in a unified approach.
Subsequently, in Section 4.2, we formulate the task of searching for a good
estimate of the profile as an optimization problem. Section 4.3 presents a
near-linear algorithm for systematically finding an approximate solution to
the optimization problem. Sections 4.4 and 4.5 analyze the time complexity and
the approximation error of the proposed algorithms, respectively. Finally,
Section 4.6 provides a more detailed comparison of our algorithm with the
previous approach.

###  4.1 Unfolding Clipped Histograms

Assume that $\tilde{h}$ has been clipped, so that each entry has value between
$0$ and $n$. Based on the clipped histogram, we can construct a new histogram
that has the same distribution as the an unclipped one. Consider an entry
$\tilde{h}[\ell]=\text{clip}{\left[{{\vec{h}[\ell]+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)},{0},{n}}\right]}$
for some $\ell\in\mathcal{D}$, and the recovery procedure:

$\begin{array}[]{c}\tilde{h}^{\prime}[\ell]\doteq\begin{cases}\tilde{h}[\ell],&\text{
if }0<\tilde{h}[\ell]<n,\\\
\tilde{h}[\ell]-\operatorname{\mathbb{DE}xp}\left({e^{-\varepsilon}}\right),&\text{
if }\tilde{h}[\ell]=0,\\\
\tilde{h}[\ell]+\operatorname{\mathbb{DE}xp}\left({e^{-\varepsilon}}\right),&\text{
if }n=\tilde{h}[\ell],\end{cases}\end{array}$ (8)

where $\operatorname{\mathbb{DE}xp}\left({e^{-\varepsilon}}\right)$ denotes a
random variable following the geometric distribution:
$\Pr\left[\operatorname{\mathbb{DE}xp}\left({e^{-\varepsilon}}\right)=t\right]={\left(1-e^{-\varepsilon}\right)}\cdot
e^{-\varepsilon\cdot{t}},\,\forall t\in\mathbb{N}.$

######  Lemma 4.1.

$\tilde{h}^{\prime}[\ell]$ has the same distribution as $\vec{h}[\ell]+Z$,
where $Z$ is an independent copy of
$\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)$.

Appendix B contains the detailed proof of the theorem. Here, we present a
high-level overview of the proof’s intuition: when restricting the two-
directional discrete Laplace random variable
$\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)$ to a single
direction, it reduces to a random variable that follows the geometric
distribution. It is a well-known fact that for a geometric random variable,
truncating it at a certain value and adding an independent copy of the random
variable at the truncated value preserves its geometric distribution. This
property is commonly referred to as the ”memorylessness” property of the
geometric distribution.

###  4.2 Searching for Profiles

A natural attempt would be estimating the profile $\vec{f}$ with
$\tilde{f}[{0}\,.\,.\,{n}]\doteq{({\tilde{f}[0],\ldots,\tilde{f}[n]})}$, where
$\tilde{f}[t]={\left(1/d\right)}\cdot|\\{\ell\in\mathcal{D}:\tilde{h}[\ell]=t\\}|,\forall
t\in\mathbb{Z}.$ There are several issues with such an estimate. First,
$\tilde{f}[{0}\,.\,.\,{n}]$ is not an empirical profile, as its entries do not
sum up to $1$. An even more significant concern is that such an estimate can
incur an error of $\Omega(1)$.

#### Example.

Consider the example where $\vec{h}[\ell]=1,\forall\ell\in\mathcal{D}.$ Hence,
$\vec{f}[1]=1$ and $\vec{f}[t]=0$ for all $t\neq 1$. But, it can be shown that
$\mathbb{E}[\tilde{f}[1]]=\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}$ and
$\mathbb{V}ar[\tilde{f}[1]]\leq\frac{1}{d}\cdot\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}.$
By Chebyshev’s inequality, when $\varepsilon\in\Theta(1)$, with constant
probability,
$\|\tilde{f}[{0}\,.\,.\,{n}]-\vec{f}\|_{p}\geq|\tilde{f}[1]-\vec{f}[1]|\in\Omega(1),$
for $p=1,2,\infty.$

To deepen our understanding of the relationship between $\tilde{f}$ and
$\vec{f}$, let us consider a fixed $t\in[{0}\,.\,.\,{n}]$. There are
$\vec{f}[t]\cdot d$ items in $\mathcal{D}$ such that $\vec{h}[\ell]=t$. For
each of these items, the random variable
$\tilde{h}[\ell]=\vec{h}[\ell]+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)$
is independent and identically distributed. Our _analysis_ considers an
algorithm, outlined in Algorithm 1, for generating $\tilde{f}$ directly from
$\vec{f}$. We emphasize that our final algorithm is the combination of
Algorithms 2 and 3, and does not make use of Algorithm 1.

Algorithm 1 Private Profile Generator $\mathcal{A}{\left(\vec{r}\right)}$

Input: $\vec{r}$

1: Initialize an all zero profile $\vec{v}$

2: for $t\in[{0}\,.\,.\,{n}]$ do

3: for $j\leftarrow 1$ to $\vec{r}[t]\cdot d$ do

4: $I\leftarrow t+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)$

5: $\vec{v}[I]\leftarrow\vec{v}[I]+{1/d}$

6: return $\vec{v}$ $\triangleright$ the perturbed profile

To search for a good approximation $\vec{r}$ of $\vec{f}$, our strategy shifts
towards searching for a $\vec{r}$ such that $\mathcal{A}(\vec{r})$ (the vector
returned by Algorithm 1 given input $\vec{r}$) is close to $\tilde{f}$. The
search is framed as an optimization problem. Our goal is then to design
efficient algorithm for solving the optimization problem, and to prove that
the proximity between $\mathcal{A}(\vec{r})$ and $\tilde{f}$ indeed implies
the proximity between $\vec{r}$ and $\vec{f}$.

#### Optimization Problem.

Let $B\in\mathbb{R}^{+}$ be the parameter (as defined in Theorem 1.1), and
$\mathcal{E}_{B}$ be the event that the all noises introduced by Algorithm 1
are absolutely bounded by $B$, and ${\footnotesize\text{LB}}\doteq-B$,
${\footnotesize\text{UB}}\doteq n+B$,
$\tilde{f}\doteq{({\tilde{f}[{\footnotesize\text{LB}}],\ldots,\tilde{f}[{\footnotesize\text{UB}}]})}.$
Given $p=1,2$ of $\infty$, the optimization problem we rely on is given by

$\displaystyle\min_{\vec{r}\in\mathbb{R}^{n+1}}$
$\displaystyle\quad\left\|{\operatorname*{\mathbb{E}}_{\mathcal{A}}\left[\mathcal{A}{\left(\vec{r}\right)}\mid\mathcal{E}_{B}\right]-\tilde{f}}\right\|_{p}$
($\text{P}_{1}$) s.t. $\displaystyle\quad\sum_{t=0}^{n}\vec{r}[t]=1,$
$\displaystyle\quad 0\leq\vec{r}[t]\leq 1,$ $\displaystyle\quad\forall
t\in[{0}\,.\,.\,{n}].$

To simplify the notation, when it is clear from the context, we write
$\operatorname*{\mathbb{E}}_{\mathcal{A}}\left[\mathcal{A}{\left(\vec{r}\right)}\mid\mathcal{E}_{B}\right]$
as
$\operatorname*{\mathbb{E}}\left[\mathcal{A}{\left(\vec{r}\right)}\mid\mathcal{E}_{B}\right]$.
In what follows, we provide motivation for this formulation.

Conditioning on $\mathcal{E}_{B}.$ Without the event $\mathcal{E}_{B}$,
$\mathcal{A}{\left(\vec{r}\right)}$ can have unbounded support, as the noises
introduced by Algorithm 1 are unbounded. Conditioned on event
$\mathcal{E}_{B}$, only
$\mathcal{A}{\left(\vec{r}\right)}[{\footnotesize\text{LB}}],\ldots,\mathcal{A}{\left(\vec{r}\right)}[{\footnotesize\text{UB}}]$
process nonzero values. Therefore,
$\operatorname*{\mathbb{E}}\left[\mathcal{A}{\left(\vec{r}\right)}\mid\mathcal{E}_{B}\right]$
can be viewed as a vector indexed from LB to UB. Further, by proper choice of
$B$, the event $\overline{\mathcal{E}_{B}}$ only occurs with sufficiently
small probability. Therefore, the event $\mathcal{E}_{B}$ encompasses the
majority of cases.

Taking the Expectation. Without the expectation, the error
$\|{\mathcal{A}{\left(\vec{r}\right)}}-\tilde{f}\|_{p}$ is itself a random
variable (even conditioned on $\mathcal{E}_{B}$). The objective in
($\text{P}_{1}$) is a relaxation of the expected error, as it provides a lower
bound for the latter. To see this, note that $\left\|{\cdot}\right\|_{p}$ is
convex for $p\geq 1$, and according to Jensen’s inequality, we have

$\begin{array}[]{c}\left\|{\operatorname*{\mathbb{E}}_{\mathcal{A}}\left[\mathcal{A}{\left(\vec{r}\right)}\mid\mathcal{E}_{B}\right]-\tilde{f}}\right\|_{p}\leq\operatorname*{\mathbb{E}}_{\mathcal{A}}\left[\left\|{{\mathcal{A}{\left(\vec{r}\right)}}-\tilde{f}}\right\|_{p}\mid\mathcal{E}_{B}\right].\end{array}$

Matrix Form. We now reformulate the above in matrix form. The primary
advantage of this formulation lies in its potential for expressing the
objective in special matrix form, facilitating the development of efficient
optimization algorithms. Let $\vec{c}\in\mathbb{R}^{n+2B+1}$ be a vector
defined as follows:

  * •

The first $B$ entries are set to
$1,e^{\text{-}\varepsilon},\ldots,e^{\text{-}\varepsilon\cdot B}$.

  * •

The last $B$ entries are set to $e^{\text{-}\varepsilon\cdot
B},e^{\text{-}\varepsilon\cdot(B-1)},\ldots,e^{\text{-}\varepsilon}$.

  * •

All other entries are set to $0$.

Define
$P_{norm}\doteq\frac{1+e^{-\varepsilon}-2\,(e^{-\varepsilon})^{B+1}}{1-e^{-\varepsilon}},$
and

$\begin{array}[]{c}\boldsymbol{A}\doteq\frac{1}{P_{norm}}\,\boldsymbol{\text{circ}}{\left(\vec{c}\right)}.\end{array}$
(9)

To maintain consistency with $\tilde{f}$, we assume that both rows and columns
of $\boldsymbol{A}$ are indexed by
$[{{\footnotesize\text{LB}}}\,.\,.\,{{\footnotesize\text{UB}}}]$. The
following lemma states that, we can express the objective in ($\text{P}_{1}$)
in matrix form.

######  Lemma 4.2.

Let $\mathcal{A}(\cdot)$ be the Algorithm 1, $\boldsymbol{A}$ be matrix
defined as Equation (9), and
$\vec{r}={\left(\vec{r}[0],\ldots,\vec{r}[n]\right)}\in\mathbb{R}_{\geq
0}^{n+1}$ be a vector such that $\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]=1.$
Assume that we expand the vector $\vec{r}$ to one in $\mathbb{R}^{n+2B+1}$ by
padding $\vec{r}[-B]=\cdots=\vec{r}[-1]=0$ to the front and
$\vec{r}[n+1]=\cdots=\vec{r}[n+B]=0$ to the back of $\vec{r}$. The following
claim holds:
$\operatorname*{\mathbb{E}}\left[\mathcal{A}{\left(\vec{r}\right)}\mid\mathcal{E}_{B}\right]=\boldsymbol{A}\times\vec{r}.$

Based on the above lemma, the optimization problem ($\text{P}_{1}$) is
equivalent to the following one:

$\displaystyle\min_{\vec{r}\in\mathbb{R}^{n+2B+1}}$
$\displaystyle\left\|{\boldsymbol{A}\times\vec{r}-\tilde{f}}\right\|_{p}$
($\text{P}_{2}$) s.t. $\displaystyle\sum_{t=0}^{n}\vec{r}[t]=1,$
$\displaystyle 0\leq\vec{r}[t]\leq 1,$ $\displaystyle\,\,\forall
t\in[{0}\,.\,.\,{n}],$ $\displaystyle\vec{r}[t]=0,$ $\displaystyle\,\,\forall
t\in[{{\footnotesize\text{LB}}}\,.\,.\,{{\footnotesize\text{UB}}}]\setminus[{0}\,.\,.\,{n}].$

An important advantage lies in the potential efficiency gained from the
circulant matrix $\boldsymbol{A}$, as detailed in Section 4.4, enabling
$\boldsymbol{A}^{-1}\vec{x}$ to be computed in $O(n\log n)$ time for each
vector $\vec{x}$. This motivates the choice of computing
$\boldsymbol{A}^{-1}\tilde{f}$ as the approximate profile $\vec{r}$, resulting
in zero error in the objective function:

$\begin{array}[]{c}\left\|{\boldsymbol{A}\times\boldsymbol{A}^{-1}\times\tilde{f}-\tilde{f}}\right\|_{p}=0.\end{array}$

However, it’s crucial to note that such a solution may potentially violate
other constraints outlined in ($\text{P}_{2}$). This observation motivates the
development of an algorithm for systematically solving ($\text{P}_{2}$), which
will be discussed in the next section.

###  4.3 Optimization Algorithms

In this section, we present effective algorithms to address the optimization
problem defined by ($\text{P}_{2}$). Our approach consists of two steps:
initially, we concentrate on a relaxed version of ($\text{P}_{2}$) and
introduce an algorithm that optimally solves it. Subsequently, building upon
the solution obtained in the first step, we introduce a rounding procedure
designed to yield an approximate solution for ($\text{P}_{2}$), satisfying all
the specified constraints. The proofs of all lemmas in this section are
included in the _Appendix D._

#### Relaxation.

There are two categories of constraints on $\vec{r}$ in optimization problem
($\text{P}_{2}$): its coordinates should sum up to $1$; and each of its
coordinates should be within a given range. Optimizing ($\text{P}_{2}$)
simultaneously with two constraints is non-trivial, so we initially focus on
the first constraint, leading to optimization problem ($\text{P}_{3}$):

$\begin{array}[]{ccccc}&\min&\left\|{\boldsymbol{A}\times\vec{r}-\tilde{f}}\right\|_{p}&\text{s.t.}&\sum_{t=0}^{n}\vec{r}[t]=1.\end{array}$
($\text{P}_{3}$)

The optimization problem ($\text{P}_{3}$) has a simple geometric
interpretation. Since $\boldsymbol{A}$ is invertible (as will be shown in
Lemma 4.6), the function
$\|\cdot\|_{\boldsymbol{A},p}:\mathbb{R}^{[{0}\,.\,.\,{n}]}\rightarrow\mathbb{R}$,
defined by

$\begin{array}[]{c}\|\vec{v}\|_{\boldsymbol{A},p}\doteq\|\boldsymbol{A}\times\vec{v}\|_{p},\quad\forall\vec{v}\in\mathbb{R}^{[{0}\,.\,.\,{n}]}.\end{array}\vspace{-1mm}$

constitutes a norm. The objective of ($\text{P}_{3}$) is equivalent to

$\begin{array}[]{c}\|\boldsymbol{A}\times{({\vec{r}-\boldsymbol{A}^{-1}\times\tilde{f}})}\|_{p}\end{array}$

Hence, ($\text{P}_{3}$) seeks to find the point nearest to
$\boldsymbol{A}^{-1}\times\tilde{f}$ (measured by the distance induced by the
norm $\|\cdot\|_{\boldsymbol{A},p}$) within the hyperplane specified by
$\sum_{t=0}^{n}\vec{r}[t]=1$.

This inspires Algorithm 2 for solving ($\text{P}_{3}$). First, it computes a
vector $\vec{u}={\boldsymbol{A}}^{-1}\times{\tilde{f}}$. Let
$\vec{\mathbbm{1}}_{{0:n}}$ be a binary vector such that
$\vec{\mathbbm{1}}_{{0:n}}[t]=1$ only when $t\in[{0}\,.\,.\,{n}]$. If
$\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\rangle\neq 1$, the algorithm
rectifies this by adjusting $\vec{u}$ along the direction
$\boldsymbol{A}^{-1}\times\vec{a}$ (by an appropriate amount), where $\vec{a}$
is the unit vector (in terms of the norm $\left\|{\cdot}\right\|_{p}$) which
maximizes
$\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\rangle$. In
essence, adjusting $\vec{u}$ along $\boldsymbol{A}^{-1}\times\vec{a}$ is the
most cost-effective way to correct the violation
$\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\rangle\neq 1$. Formally, Lemma 4.3
holds.

Algorithm 2 Fast Inversion $\mathcal{A}_{\textit{fst-inv}}$

Input: $\tilde{h}$ and $p\in\\{1,2,\infty\\}$

1: Compute $\tilde{f}$ based on $\tilde{h}$

2: $\vec{u}\leftarrow{\boldsymbol{A}}^{-1}\times{\tilde{f}}$

3: Let $\vec{\mathbbm{1}}_{{0:n}}$ be a vector, s.t.,
$\vec{\mathbbm{1}}_{{0:n}}[t]=\begin{cases}1,&\forall t\in[{0}\,.\,.\,{n}]\\\
0,&\text{ otherwise }\end{cases}$

4: Let
$\vec{a}\leftarrow\arg\max_{\left\|{\vec{a}^{\prime}}\right\|_{p}=1}\langle{\vec{\mathbbm{1}}_{{0:n}}}{\boldsymbol{A}^{-1}\times\vec{a}^{\prime}}\rangle$

5:
$\vec{r}\leftarrow\vec{u}-\frac{{\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle-1}}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}\cdot\boldsymbol{A}^{-1}\times\vec{a}$

6: return $\vec{r}$ $\triangleright$ the estimated profile

######  Lemma 4.3.

Algorithm 2 returns an optimal solution for the optimization problem
($\text{P}_{3}$).

#### Rounding.

Given a solution $\vec{r}$ returned by Algorithm 2, Algorithm 3 post-processes
it to ensure satisfaction of all constraints in ($\text{P}_{2}$).

Algorithm 3 unfolds in three phases: Phase 1 (Line 1), wherein the algorithm
sets $\vec{r}[t]$ to $0$ for each
$t\in[{{\footnotesize\text{LB}}}\,.\,.\,{{\footnotesize\text{UB}}}]\setminus[{0}\,.\,.\,{n}]$;
Phase 2 (Line 2 to Line 7), where the algorithm clips $\vec{r}[t]$ to the
range of $[0,1]$; and Phase 3 (Line 8 to Line 12), during which the algorithm
adjusts $\vec{r}[t]$ to ensure their sum equals $1$. It is essential to
observe that Phase 3 will not generate any coordinate outside the range
$[0,1]$. Moreover, in Phase 3, it is adequate to solely consider decreasing
the coordinate values of $\vec{r}$, which will be formally explained in the
proof of Lemma 4.4.

Algorithm 3 Rounding $\mathcal{A}_{\textit{rnd}}$

Input: $\vec{r}$

1: $\vec{r}[t]\leftarrow 0,\forall
t\in[{{\footnotesize\text{LB}}}\,.\,.\,{{\footnotesize\text{UB}}}]\setminus[{0}\,.\,.\,{n}]$

2: $T_{>1}\leftarrow\left\\{{t\in[{0}\,.\,.\,{n}]:\vec{r}[t]>1}\right\\}$

3: $T_{<0}\leftarrow\left\\{{t\in[{0}\,.\,.\,{n}]:\vec{r}[t]<0}\right\\}$

4: $s_{>1}\leftarrow\sum_{t\in T_{>1}}{\left(1-\vec{r}[t]\right)}$

5: $s_{<0}\leftarrow\sum_{t\in T_{<0}}{\left(0-\vec{r}[t]\right)}$

6: $\vec{r}[t]\leftarrow 1$, $\forall t\in T_{>1}$

7: $\vec{r}[t]\leftarrow 0$, $\forall t\in T_{<0}$

8: $s\leftarrow s_{>1}+s_{<0}$. $\triangleright$ we must have $s\geq 0$

9: if $s>0$ then

10: Let $\tau\geq 0$ be the solution for
$\sum_{t=0}^{n}\min\left\\{{\tau,\vec{r}[t]}\right\\}=s$

11: $\vec{r}[t]\leftarrow\vec{r}[t]-\min\left\\{{\tau,\vec{r}[t]}\right\\}$,
$\forall t\in[{0}\,.\,.\,{n}]$

12: end if

13: return $\vec{r}$ $\triangleright$ the rounded profile

######  Lemma 4.4.

The vector returned by Algorithm 3 satisfies all constraints in the
optimization problem ($\text{P}_{2}$).

###  4.4 Time Analysis

In this section, we study the running time of both Algorithm 2 (Theorem 4.5)
and Algorithm 3 (Theorem 4.7).

######  Theorem 4.5.

Algorithm 2 runs in $O(d+n\log n)$ time.

The proof of Theorem 4.5 relies heavily on the properties of $\boldsymbol{A}$
as a circulant matrix.

######  Lemma 4.6.

The eigenvalues $\varphi_{t},t=-B,\ldots,n+B$ of $\boldsymbol{A}$ can be
computed in $O(n)$ time. Further, $\boldsymbol{A}$ is invertible and

$\begin{array}[]{c}\boldsymbol{A}^{-1}=\boldsymbol{V}\times\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}\times\boldsymbol{V}^{-1},\end{array}$

where $\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}$
is a diagonal matrix, and
$\boldsymbol{V}\doteq{\left[{\vec{v}_{-B}\cdots\vec{v}_{n+B}}\right]}$ is the
matrix comprising column vectors
$\vec{v}_{t}=\frac{1}{\sqrt{n+2B+1}}\cdot\begin{bmatrix}1,(w_{t})^{1},\cdots,(w_{t})^{n+2B}\end{bmatrix}^{\top},\,$
$w_{t}\doteq e^{-\frac{2\pi\cdot{\left(t+B\right)}\cdot i}{n+2B+1}},$ for
$t=-B,\ldots,n+B$.

The proof of Lemma 4.6 is included in the Appendix E. Now we are ready to
prove Theorem 4.5.

###### Proof of Theorem 4.5.

First, computing the empirical profile $\tilde{f}$ from $\tilde{h}$ takes
$O(d)$ time. Next, by fast Fourier transform (Fact 3.3), multiplying a vector
with both $\boldsymbol{V}$ and $\boldsymbol{V}^{-1}$ can be performed in
$O((n+2B+1)\log(n+2B+1))=O(n\log n)$ time. Based on the decomposition of
$\boldsymbol{A}^{-1}$ (Lemma 4.6), we see that multiplying
$\boldsymbol{A}^{-1}$ with a vector takes $O(n\log n)$ time. Therefore, it
suffices to show that $\vec{a}$ can also be found in $O(n\log n)$ time.

For consistency, assume that the coordinates of $\vec{a}$ are indexed from
$-B$ to $n+B$ and write $\vec{a}={\left[{a_{-B},\ldots,a_{n+B}}\right]}$. Then
$\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\rangle=\sum_{t=-B}^{n+B}\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}[\cdot,t]\rangle\cdot
a_{t},$ where $\boldsymbol{A}^{-1}[\cdot,t]$ is the $t^{(th)}$ column of
$\boldsymbol{A}^{-1}$. For convenience, let $c_{t}$ be a short hand for
$\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}[\cdot,t]\rangle$.
Observe that
$\vec{c}\doteq{\left[{c_{-B},\ldots,c_{n+B}}\right]}={\left(\vec{\mathbbm{1}}_{{0:n}}\right)}^{\top}\times\boldsymbol{A}^{-1}$
can be computed in $O(n\log n)$ time. Once the $c_{t}$ are known, finding
$\vec{a}$ is equivalent to solving the following optimization problem:
$\max_{\left\|{\vec{a}}\right\|_{p}=1}\left\langle\vec{c},\vec{a}\right\rangle.$

It is straightforward to see that: i)
$\vec{a}=\text{sign}(c_{t})\cdot\vec{e}_{t}$ where $\vec{e}_{t}$ is a standard
basis vector and $t=\arg\max_{t}\left|{c_{t}}\right|$ when $p=1$; ii)
$\vec{a}=\frac{\vec{c}}{\left\|{\vec{c}}\right\|_{2}}$ when $p=2$; iii)
$\vec{a}={\left[{\text{sign}{\left(c_{-B}\right)},\ldots,\text{sign}{\left(c_{n+B}\right)}}\right]}^{\top}$
when $p=\infty$.

∎

######  Theorem 4.7.

Algorithm 3 has an implementation which runs in $O(n\log n)$ time.

The detailed proof of the theorem is included in the Appendix E. At a high
level, we can initially sort the $\vec{r}[t]$ in non-decreasing order in
$O(n\log n)$ time. Subsequently, we identify the smallest integer $t^{*}$ for
which $\vec{r}[t^{*}]\geq\tau$. It can be demonstrated that
$\tau=\frac{s-\sum_{t=0}^{t^{*}-1}\vec{r}[t]}{n+1-t^{*}}$.

###  4.5 Error Analysis

In this section, we analyze the estimation error when we combined algorithms 2
and 3, and show that this results in the estimation error stated in Theorem
1.1.

The approximation errors arise from two sources: the difference between the
optimal solution of ($\text{P}_{3}$) and the actual profile; and the error
introduced during the rounding procedure. We will demonstrate that the errors
resulting from the former are of the same order of magnitudes as those
indicated in Theorem 1.1, while the latter introduces only additional
constants to the error of the former. Formally, the following two lemmas hold.

######  Lemma 4.8 (Error from Optimization ($\text{P}_{3}$)).

Given the profile $\tilde{f}$ of a private version $\tilde{h}$ of a histogram
$\vec{h}$ published by the $\varepsilon$-DP discrete Laplace mechanism and a
parameter $p=1,2$ or $\infty$, with probability at least $1-\eta$, Algorithm 2
returns a vector $\vec{r}$ with the estimation error
$\mathcal{E}\textit{rr}_{p}\doteq\|\vec{r}-\vec{f}\|_{p}$ satisfying
Inequalities (1,2,3).

######  Lemma 4.9 (Error from Rounding).

Given a vector $\vec{r}$ returned by Algorithm 2, let
$\mathcal{E}\textit{rr}_{p}$ denote the error before running Algorithm 3, and
$\mathcal{E}\textit{rr}_{p}^{\prime}$ denote the error afterwards. Then
$\mathcal{E}\textit{rr}_{p}^{\prime}\leq\mathcal{E}\textit{rr}_{p}\,$ for
$p=1,2,$ and $\mathcal{E}\textit{rr}_{\infty}^{\prime}\leq
2\,\mathcal{E}\textit{rr}_{\infty}.$

Combing Lemma 4.8 and 4.9 immediately proves the error bounds in Theorem 1.1.
In the rest of the section, we present the proofs for Lemma 4.8 and Lemma 4.9
separately.

#### Error from Optimization ($\text{P}_{3}$)

###### Proof of Lemma 4.8.

We need to prove that, the closeness between $\boldsymbol{A}\times\vec{r}$ and
$\tilde{f}$ implies the closeness between $\vec{r}$ and $\vec{f}$. To bound
$\|\vec{r}-\vec{f}\|_{p},$ we observe that

$\displaystyle\left\|{\vec{r}-\vec{f}}\right\|_{p}$
$\displaystyle=\left\|{\boldsymbol{A}^{-1}\times\boldsymbol{A}\times{\left(\vec{r}-\vec{f}\right)}}\right\|_{p}\leq\left\|{\boldsymbol{A}^{-1}}\right\|_{p}\cdot\left\|{\boldsymbol{A}\times{\left(\vec{r}-\vec{f}\right)}}\right\|_{p}$
$\displaystyle\leq\left\|{\boldsymbol{A}^{-1}}\right\|_{p}\cdot{\left(\left\|{\boldsymbol{A}\times\vec{r}-\tilde{f}}\right\|_{p}+\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{p}\right)}$
$\displaystyle\leq\left\|{\boldsymbol{A}^{-1}}\right\|_{p}\cdot{\left(2\cdot\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{p}\right)},$

where the first inequality comes from the definition of matrix norm
$\|\boldsymbol{A}^{-1}\|_{p}\doteq\max_{\vec{v}:\|\vec{v}\|_{p}=1}\|\boldsymbol{A}^{-1}\times\vec{v}\|_{p}$;
the last one from that $\vec{r}$ is the solution for optimization problem
($\text{P}_{3}$). It remains to bound $\|\boldsymbol{A}^{-1}\|_{p}$ and
$\|\tilde{f}-\boldsymbol{A}\times\vec{f}\|_{p}$ separately.

######  Lemma 4.10.

Let $\varphi_{t},t=-B,\ldots,n+B$ be the eigenvalues of $\boldsymbol{A}$. Then

$\displaystyle\left\|{\boldsymbol{A}^{-1}}\right\|_{1}$
$\displaystyle=\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}\leq\frac{2+e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}-4\cdot
e^{-\varepsilon\cdot B}}\cdot P_{norm},$
$\displaystyle\left\|{\boldsymbol{A}^{-1}}\right\|_{2}$
$\displaystyle\leq\max_{t}\frac{1}{|\varphi_{t}|}\leq\frac{P_{norm}\cdot{\left(1+e^{-\varepsilon}\right)}}{{\left(1-e^{-\varepsilon}-2\cdot
e^{-\varepsilon\cdot{\left(B+1\right)}}\right)}}.$

######  Lemma 4.11.

With probability at least $1-\eta$, it holds that

$\displaystyle\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}$
$\displaystyle\leq\frac{1}{\sqrt{d}}\cdot{\sum_{t=-B}^{n+B}\sqrt{\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}}+\sqrt{\frac{2\cdot\ln\frac{1}{\eta}}{d}}.$
$\displaystyle\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}$
$\displaystyle\leq\sqrt{\frac{1}{d}}+\sqrt{\frac{\ln\frac{1}{\eta}}{d}}.$
$\displaystyle\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{\infty}$
$\displaystyle\leq\frac{1}{\sqrt{d}}\cdot\sqrt{2\cdot\frac{1}{P_{norm}}\cdot\ln\frac{n}{\eta}}+\frac{1}{3d}\cdot\ln\frac{n}{\eta}.$

The proof of Lemma 4.10 and Lemma 4.11 are included in the Appendix F.
Finally, combining these lemmas, the assumption of $B$ in Theorem 1.1, and
that
$P_{norm}=\frac{1+e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}{1-e^{-\varepsilon}}$
finishes the proof. ∎

#### Error from Rounding.

The full proof for Lemma 4.9 is provided in the Appendix F. Here is a brief
outline of the proof for the case of $p=1$ to offer some insight. The proof
for the cases of $p=2,\infty$ are similar but much more technical. The
algorithm is divided into three phases:

  * •

Phrase 1 (Line 1): In this phase, the algorithm rounds $\vec{r}[t]$ to $0$ for
each $t\in[{-B}\,.\,.\,{n+B}]\setminus[{0}\,.\,.\,{n}]$.

  * •

Phase 2 (Line 2 to Line 7): In this phase, the algorithm clips the
$\vec{r}[t]$ to the range of $[0,1]$.

  * •

Phase 3 (Line 8 to Line 12): In this phase, the algorithm adjusts the
$\vec{r}[t]$ so that they sum up to $1$.

It is evident that the quantity $\left|{\vec{r}[t]-\vec{f}[t]}\right|$ only
decreases in Phases 1 and 2, as $\vec{f}[t]\in[0,1]$. Further it can be shown
that in Phase 2, $\|\vec{r}-\vec{f}\|_{1}$ decreases by an amount of
$-s_{>1}+s_{<0}$, and in Phase 3, $\|\vec{r}-\vec{f}\|_{1}$ can increase by at
most $s_{>1}+s_{<0}$. Hence overall, $\|\vec{r}-\vec{f}\|_{1}$ decreases.

###  4.6 Comparison with Previous Approach

Dwork, Naor, Pitassi, Rothblum, and Yekhanin (2010) also studied the profile
estimation (referred to as the _$t$ -incidence_) problem, with a key
difference from our work: their approach aimed for pan-privacy, which resulted
in significantly more noise added to the histogram $\vec{h}\in[0..n]^{d}$. To
simplify the comparison, we assume a sampling step involved in their method
has already been executed, and focus on the full histogram of sampled items.
Let $\tilde{h}$ denote the noisy histogram. For each $\ell\in[d]$, their
requirement was that

$\big{(}\max_{t\in[0..n]}\Pr[\tilde{h}[\ell]=t]\big{)}\big{/}\big{(}\min_{t\in[0..n]}\Pr[\tilde{h}[\ell]=t]\big{)}\leq
e^{\varepsilon}.$

Specifically, they used noise scaling with $n$:
$\tilde{h}[\ell]\leftarrow\vec{h}[\ell]+Z\pmod{n+1}$, where $Z$ is a noise
variable such that $\Pr[Z=t]\propto e^{-\varepsilon\cdot t/(n+1)}$.

In contrast, our paper considers adding symmetric discrete Laplace noise
$\mathbb{DL}ap(e^{-\varepsilon})$ to each entry, which is fundamental and
widely used for publishing privatized histograms. Our technique is applicable
even in the pan-private setting, with appropriately scaled noise.

Another minor difference lies in the optimization problem: their linear
program (LP) aims to achieve solutions with $\ell_{\infty}$ error, whereas our
algorithm supports $\ell_{1}/\ell_{2}/\ell_{\infty}$ errors. Moreover, they
did not provide an almost linear-time algorithm for solving their LP. However,
the almost linear-time algorithm developed in our paper can solve their LP as
well, as it also involves a circulant matrix.

##  5 Lower Bound

In this section, we discuss the lower bound in Theorem 1.2. We will begin by
providing the formal definition of _updatable_ histogram publishing algorithms
and the _sensitivity_ of the profile reconstruction algorithms when composed
with the private histogram publishing algorithm. To establish the lower bound,
we will then present a reduction from the inner product estimation problem in
the two-party setting.

Our lower bound applies to an algorithm $\mathcal{A}$ that is updatable,
meaning that there exists an update algorithm $\mathcal{U}$, s.t., given the
output $\mathcal{A}(\vec{h})$ and some other histogram $\vec{h}^{\prime}$,
$\mathcal{U}$ can adjust the output directly (by computing
$\mathcal{U}(\mathcal{A}(\vec{h}),\tilde{h})$), as if the input to
$\mathcal{A}$ is $\vec{h}+\vec{h}^{\prime}.$ Formally,

######  Definition 5.1 (Updatable Algorithm).

A (randomized) algorithm
$\mathcal{A}:[{0}\,.\,.\,{n}]^{d}\rightarrow\mathcal{Y}$ is called updatable,
if there exists another (randomized) algorithm
$\mathcal{U}:\mathcal{Y}\times[{0}\,.\,.\,{n}]^{d}\rightarrow\mathcal{Y}$, the
_update algorithm_ , such that for every
$\vec{h},\vec{h}^{\prime}\in[{0}\,.\,.\,{n}]^{d}$,
$\mathcal{U}(\mathcal{A}(\vec{h}),\vec{h}^{\prime})$ has the same distribution
as $\mathcal{A}(\vec{h}+\vec{h}^{\prime})$.

######  Example 5.2.

If $\mathcal{A}$ is the discrete Laplace mechanism, then it is updatable. Let
$\mathcal{U}$ be the vector addition operation:
$\mathcal{U}(\mathcal{A}(\vec{h}),\vec{h}^{\prime})=\vec{h}+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)^{d}+\vec{h}^{\prime}=\mathcal{A}(\vec{h}+\vec{h}^{\prime}),$
where
${\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)}^{d}\in\mathbb{Z}^{d}$
is a vector composed of independent discrete Laplace random variables.

When $\mathcal{A}$ represents a randomized algorithm, it can be conceptualized
as a function, denoted as $F_{A}$, acting on both the input of $\mathcal{A}$
and the randomness inherent in its execution (commonly referred to as ”coin
tosses” in the literature). This randomness is formally represented by the
random variable $C_{A}$. In what follows, denote
$\mathcal{R}:\mathcal{Y}\rightarrow[0,1]^{n+1}$ as an algorithm trying to
reconstruct the profile of $\vec{h}$ when given $\mathcal{A}(\vec{h}).$

######  Definition 5.3.

The sensitivity of $\mathcal{R}\circ\mathcal{A}$ is defined as the maximum
deviation of $\mathcal{R}\circ F_{A}$, over all possible realization $c_{A}$
of $C_{A}$ and all possible pair of neighboring inputs of $\mathcal{A}:$

$\Delta_{\mathcal{R}\circ\mathcal{A}}\doteq\max_{c_{A}}\max_{\vec{h}\sim\vec{h}^{\prime}}\left\|{\mathcal{R}{\left(F_{A}{\left(\vec{h},c_{A}\right)}\right)}-\mathcal{R}{\left(F_{A}{\left(\vec{h}^{\prime},c_{A}\right)}\right)}}\right\|_{\infty},$

where the second maximum is over all
$\vec{h},\vec{h}^{\prime}\in[{0}\,.\,.\,{n}]^{d}$ such that
$\|\vec{h}-\vec{h}^{\prime}\|_{1}\leq 1$

In Appendix G, we show that when $\mathcal{A}$ is the discrete Laplace
mechanism, $\mathcal{R}$ is the profile reconstruction algorithm stated in
Theorem 1.1, and $\frac{1}{\sqrt{d}}\in
o{\big{(}{\big{(}\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}\big{)}^{2}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}}\big{)}}$,
$\Delta_{\mathcal{R}\circ\mathcal{A}}$ satisfies
$\Delta_{\mathcal{R}\circ\mathcal{A}}\in
o\big{(}\frac{1}{\sqrt{d}}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}\big{)}$.
Hence, the lower bound in Theorem 1.2 applies to our algorithms.

#### Two Party Differential Privacy.

We will prove the lower bound by establishing a connection between the profile
estimation problem and the inner product estimation problem in the two party
differential privacy setting (McGregor et al., 2010).

Two players, Alice and Bob, equipped with unrestricted computational
capabilities, collaborate to compute the inner product
$\left\langle\vec{x},\vec{y}\right\rangle$, where
$\vec{x}\in\left\\{{-1,1}\right\\}^{d}$ is the binary string held by Alice,
and $\vec{y}\in\left\\{{-1,1}\right\\}^{d}$ is one held by Bob. The
collaboration follows a pre-agreed protocol, denoted as $\Pi$. In this
protocol, they alternate turns to communicate with each other. During each
player’s turn, the communicated information is determined by their own vector,
the cumulative communication up to that point, and possibly their randomness.
The sequences of messages, which collectively form the protocol’s transcript,
are denoted as $\Pi$. To protect the data of both parties, it is required that
each party’s view of $\Pi$, as a function of the other party’s data, should be
differentially private.

Formally, the view of Alice, denoted as
$\Pi_{\vec{x}}:\left\\{{-1,1}\right\\}^{d}\rightarrow\mathcal{Z}$ (where
$\mathcal{Z}$ is the set of all possible sequences of messages), is regarded
as a (randomized) algorithm with input string $\vec{y}$ when $\vec{x}$ is
fixed. The view $\Pi_{\vec{x}}$ is $\varepsilon$-DP, if for each measurable
$Z\subseteq\mathcal{Z}$ and every pair of neighboring vector $\vec{y}$ and
$\vec{y}^{\prime}$ s.t. $\left\|{\vec{y}-\vec{y}^{\prime}}\right\|=1$, it
holds that

$\begin{array}[]{c}\Pr\left[\Pi_{\vec{x}}(\vec{y})\in Z\right]\leq
e^{\varepsilon}\cdot\Pr\left[\Pi_{\vec{x}}(\vec{y}^{\prime})\in
Z\right].\end{array}$

We can define the view of Bob
$\Pi_{\vec{y}}:\left\\{{-1,1}\right\\}^{d}\rightarrow\mathcal{Z}$ and the
$\varepsilon$-DP property of $\Pi_{\vec{y}}$ in a similar manner. The protocol
$\Pi$ is called $\varepsilon$-DP, if $\Pi_{\vec{x}}$ is $\varepsilon$-DP for
all possible $\vec{x}$, and $\Pi_{\vec{y}}$ is $\varepsilon$-DP for all
possible $\vec{y}$. McGregor et al. (2010) established a lower bound on inner
product estimation, which was further refined by Haitner et al. (2022).

######  Fact 5.4 (The Two Party Lower Bound (Haitner et al., 2022)).

An $\varepsilon$-DP two-party protocol that, for some $\ell\geq\log d$,
estimate the inner product over
$\left\\{{\text{-1},1}\right\\}^{d}\times\left\\{{\text{-1},1}\right\\}^{d}$
up to an additive error $\ell$ with probability $c\cdot
e^{c\cdot\epsilon}\cdot\ell/\sqrt{d}$ (for some universal constant $c>0$), can
be used to construct a key-agreement protocol.

Since an information theoretically secure key agreement does not exist
(Haitner et al., 2022), Fact 5.4 implies that such protocols do not exist
either.

###### Sketch Proof of Theorem 1.2..

Based on Fact 5.4, we present a sketch proof for the theorem. The complete
proof is included in the Appendix G.

We will prove the theorem by contraction. Assume there exists an
$\varepsilon$-DP and updatable algorithm
$\mathcal{A}:[{0}\,.\,.\,{n}]^{d}\rightarrow\mathcal{Y}$, profile estimation
algorithm $\mathcal{R}:\mathcal{Y}\rightarrow[0,1]^{n+1}$, such that, for
every input $\vec{h}\in[{0}\,.\,.\,{n}]^{d}$,

$\begin{array}[]{c}\mathbb{E}[\|\vec{f}-\mathcal{R}{({\mathcal{A}(\vec{h})})}\|_{\infty}]\in
o{\big{(}{{1}/{({\sqrt{d}\cdot e^{c\cdot\varepsilon}})}}\big{)}}.\end{array}$

We will construct an $\varepsilon$-DP protocol $P$ such that for every
$\vec{x}$ and $\vec{y}$, Bob’s output (denoted by $m_{B}$) satisfies

$\begin{array}[]{c}\Pr\left[\left|{m_{B}-\left\langle\vec{x},\vec{y}\right\rangle}\right|\geq\mathcal{E}\textit{rr}\right]\in
o(1),\end{array}$ (10)

where $\mathcal{E}\textit{rr}=\sqrt{d}/{({2\cdot c\cdot
e^{c\cdot\varepsilon}})}$, contradicting Fact 5.4.

The protocol is outlined by Algorithm 4, where
$\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)$ denotes a random
variable following the Laplace distribution with probability density
$p(z)=\frac{\varepsilon}{2}\cdot\exp{\left(-\varepsilon\cdot\left|{z}\right|\right)},\forall
z\in\mathbb{R}.$

Algorithm 4 Protocol $P$

Alice: send $m_{A}\leftarrow\mathcal{A}(\vec{x}+\vec{\mathbbm{1}})$ to Bob.

Bob: $\circ$ on receiving $m_{A}$, compute
$\vec{r}\leftarrow\mathcal{R}{({\mathcal{U}{({m_{A},\vec{y}+\vec{\mathbbm{1}})})}})}$

$\circ$ publish
$d{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}$

Since $\vec{x},\vec{y}\in\left\\{{\text{-}1,1}\right\\}^{d}$ and
$\vec{x}+\vec{\mathbbm{1}},\vec{y}+\vec{\mathbbm{1}}\in\left\\{{0,2}\right\\}^{d}$,
it can be verified that

$\begin{array}[]{rl}\left\langle\vec{x},\vec{y}\right\rangle&=\left|{\left\\{{\ell\in[d]:\vec{x}[\ell]=\vec{y}[\ell]}\right\\}}\right|-\left|{\left\\{{\ell\in[d]:\vec{x}[\ell]\neq\vec{y}[\ell]}\right\\}}\right|\\\
&=\left|{\left\\{{\ell\in[d]:{({\vec{x}+\vec{\mathbbm{1}}})}[\ell]={({\vec{y}+\vec{\mathbbm{1}}})}[\ell]}\right\\}}\right|\\\
&\,-\left|{\left\\{{\ell\in[d]:{({\vec{x}+\vec{\mathbbm{1}}})}[\ell]\neq{({\vec{y}+\vec{\mathbbm{1}}})}[\ell]}\right\\}}\right|\\\
&=d\cdot{({\vec{f}[4]+\vec{f}[0]-\vec{f}[2]})}.\end{array}$

Via the accuracy assumption of $\mathcal{R}$ and the sensitivity assumption of
$\Delta_{\mathcal{R}\circ\mathcal{A}}$ (in Theorem 1.2), it holds that
$m_{B}\doteq
d\cdot{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}$
is an estimate of $d\cdot{({\vec{f}[4]+\vec{f}[0]-\vec{f}[2]})}$ with expected
error $o{({\sqrt{d}/{e^{c\cdot\varepsilon}}})}$:

$\begin{array}[]{c}\operatorname*{\mathbb{E}}\left[\left|{m_{B}-d\cdot{({\vec{f}[4]+\vec{f}[0]-\vec{f}[2]})}}\right|\right]\in
o{({\sqrt{d}/{e^{c\cdot\varepsilon}}})}.\end{array}$

Combing
$d\cdot{({\vec{f}[4]+\vec{f}[0]-\vec{f}[2]})}=\left\langle\vec{x},\vec{y}\right\rangle$
with Markov inequality proves Equation (10).

Finally, we verify that $P$ is $\varepsilon$-DP. Clearly
$\mathcal{A}(\vec{x}+\vec{\mathbbm{1}})$ is $\varepsilon$-DP. The output of
Bob,
$d\cdot{({\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)})}$
is also $\varepsilon$-DP. This is because, by the definition of
$\Delta_{\mathcal{R}\circ\mathcal{A}}$, it serves as an upper bound on the
sensitivity of $\vec{r}[4],\vec{r}[0]$ and $\vec{r}[2]$.

∎

We provide some further comments on the lower bound. First, it is also
possible to prove a lower bound of

$\begin{array}[]{c}\operatorname*{\mathbb{E}}\left[\left\|{\vec{f}-\mathcal{R}{({\mathcal{A}(\vec{h})})}}\right\|_{\infty}\right]\in
o{\left(\frac{1}{\sqrt{d}\cdot\log
d}\cdot\frac{1}{e^{\varepsilon}}\right)},\end{array}$ (11)

for Theorem 1.2, via a similar reduction to the two-party inner product lower
bound accuracy lower bound by McGregor et al. (2010). In particular, they
showed that with probability $1-\delta$, inner product estimation in a two-
party setting incurs an additive error of $\Omega{\left(\frac{\sqrt{d}}{\log
d}\cdot\frac{\delta}{e^{\varepsilon}}\right)}$. Compared to Equation (4),
Equation (11) avoids a constant $c$ blow up in the exponent, at the cost of an
addition factor of $\log d$ in the denominator.

Second, Theorem 1.2 assumes $\Delta_{\mathcal{R}\circ\mathcal{A}}\in
o\big{(}\frac{1}{\sqrt{d}}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}\big{)}$.
We considered removing this assumption because it appears that if
$\Delta_{\mathcal{R}\circ\mathcal{A}}\in\Omega\big{(}\frac{1}{\sqrt{d}}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}\big{)}$,
it would imply that
$\mathbb{E}[\|\vec{f}-\mathcal{R}{({\mathcal{A}(\vec{h})})}\|_{\infty}]\in\Omega\big{(}\frac{1}{\sqrt{d}\cdot
e^{c\cdot\varepsilon}}\big{)}$ for some $\vec{h}$. However, this is not the
case. Since $\mathcal{A}$ is a randomized algorithm,
$\Delta_{\mathcal{R}\circ\mathcal{A}}$ is defined over all randomness $c_{A}$
of $\mathcal{A}$ as per Definition 5.3. It is possible that
$\Delta_{\mathcal{R}\circ\mathcal{A}}\in\Omega\big{(}\frac{1}{\sqrt{d}}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}\big{)}$
for the $c_{A}$’s with very small probabilities. Therefore, we cannot derive a
lower bound for
$\mathbb{E}[\|\vec{f}-\mathcal{R}{({\mathcal{A}(\vec{h})})}\|_{\infty}].$

Finally, our current lower bound applies to an algorithm $\mathcal{A}$ that
protects the number of occurrences of a single element by 1. It extends
naturally to an algorithm $\mathcal{A}$ that protects the number of
occurrences of a single element by an arbitrary amount, as long as it
satisfies the other assumptions in Theorem 1.2.

## Impact Statement

The goal of this work is to advance privacy-preserving data analysis and
machine learning in distributed and large-scale settings. Generally speaking
this work adds to the toolbox of ways in which we can incorporate privacy into
system designs. There are many potential societal consequences of our work,
none of which we feel must be specifically highlighted here.

## Acknowledgements

We thank the anonymous reviewers for their feedback which helped improve the
paper. The authors are supported by Providentia, a Data Science Distinguished
Investigator grant from Novo Nordisk Fonden and affiliated with Basic
Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation
grant 16582.

## References

  * Acharya et al. (2017) Acharya, J., Das, H., Orlitsky, A., and Suresh, A. T.  A unified maximum likelihood approach for estimating symmetric properties of discrete distributions.  In _International Conference on Machine Learning (ICML)_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 11–21. PMLR, 2017.
  * Audibert et al. (2009) Audibert, J., Munos, R., and Szepesvári, C.  Exploration-exploitation tradeoff using variance estimates in multi-armed bandits.  _Theor. Comput. Sci._ , 410(19):1876–1902, 2009.
  * Blocki et al. (2016) Blocki, J., Datta, A., and Bonneau, J.  Differentially private password frequency lists.  In _Network and Distributed System Security Symposium (NDSS)_. The Internet Society, 2016.
  * Bun et al. (2019) Bun, M., Nelson, J., and Stemmer, U.  Heavy hitters and the structure of local privacy.  _ACM Trans. Algorithms_ , 15(4):51:1–51:40, 2019.
  * Chen et al. (2024) Chen, J. Y., Indyk, P., and Woodruff, D. P.  Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions.  In Guruswami, V. (ed.), _15th Innovations in Theoretical Computer Science Conference (ITCS 2024)_ , volume 287 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pp. 32:1–32:22, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-95977-309-6.
  * Chung & Lu (2006) Chung, F. and Lu, L.  Concentration inequalities and martingale inequalities: a survey.  _Internet Math._ , 3(1):79–127, 2006.
  * Cormen et al. (2009) Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C.  _Introduction to Algorithms, 3rd Edition_.  MIT Press, 2009.  ISBN 978-0-262-03384-8.
  * Datar & Muthukrishnan (2002) Datar, M. and Muthukrishnan, S.  Estimating rarity and similarity over data stream windows.  In _Proceedings of European Symposium on Algorithms (ESA)_ , pp. 323–335. Springer, 2002.
  * Dwork & Roth (2014) Dwork, C. and Roth, A.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Dwork et al. (2006) Dwork, C., McSherry, F., Nissim, K., and Smith, A. D.  Calibrating noise to sensitivity in private data analysis.  In Halevi, S. and Rabin, T. (eds.), _Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings_ , volume 3876 of _Lecture Notes in Computer Science_ , pp. 265–284. Springer, 2006.
  * Dwork et al. (2010) Dwork, C., Naor, M., Pitassi, T., Rothblum, G. N., and Yekhanin, S.  Pan-private streaming algorithms.  In _Proceedings of Innovations in Computer Science (ICS)_ , pp. 66–80, 2010.  Now known as ITCS.
  * Ghosh et al. (2009) Ghosh, A., Roughgarden, T., and Sundararajan, M.  Universally utility-maximizing privacy mechanisms.  In Mitzenmacher, M. (ed.), _Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009_ , pp. 351–360. ACM, 2009.
  * Gray (2005) Gray, R. M.  Toeplitz and circulant matrices: A review.  _Found. Trends Commun. Inf. Theory_ , 2(3), 2005.
  * Haitner et al. (2022) Haitner, I., Mazor, N., Silbak, J., and Tsfadia, E.  On the complexity of two-party differential privacy.  In Leonardi, S. and Gupta, A. (eds.), _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ , pp. 1392–1405. ACM, 2022.  doi: 10.1145/3519935.3519982.  URL https://doi.org/10.1145/3519935.3519982.
  * Hardt & Talwar (2010) Hardt, M. and Talwar, K.  On the geometry of differential privacy.  In Schulman, L. J. (ed.), _Proceedings of Symposium on Theory of Computing (STOC)_ , pp. 705–714. ACM, 2010.
  * Hay et al. (2009) Hay, M., Li, C., Miklau, G., and Jensen, D. D.  Accurate estimation of the degree distribution of private networks.  In _International Conference on Data Mining (ICDM)_ , pp. 169–178. IEEE Computer Society, 2009.
  * Hay et al. (2010) Hay, M., Rastogi, V., Miklau, G., and Suciu, D.  Boosting the accuracy of differentially private histograms through consistency.  _Proc. VLDB Endow._ , 3(1):1021–1032, 2010.
  * Karwa & Slavkovic (2012) Karwa, V. and Slavkovic, A. B.  Differentially private graphical degree sequences and synthetic graphs.  In _Privacy in Statistical Databases (PSD)_ , volume 7556 of _Lecture Notes in Computer Science_ , pp. 273–285. Springer, 2012.
  * Manurangsi (2022) Manurangsi, P.  Tight bounds for differentially private anonymized histograms.  In _5th Symposium on Simplicity in Algorithms_ , pp. 203–213. SIAM, 2022.
  * McGregor et al. (2010) McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., and Vadhan, S. P.  The limits of two-party differential privacy.  In _51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA_ , pp. 81–90. IEEE Computer Society, 2010.
  * Mitzenmacher & Upfal (2017) Mitzenmacher, M. and Upfal, E.  _Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis_.  Cambridge university press, 2017.
  * Suresh (2019) Suresh, A. T.  Differentially private anonymized histograms.  In _Advances in Neural Information Processing Systems 32_ , pp. 7969–7979, 2019.
  * Tolstikhin (2017) Tolstikhin, I. O.  Concentration inequalities for samples without replacement.  _Theory of Probability & Its Applications_, 61(3):462–481, 2017.

##  Appendix A Probability Inequalities

######  Definition A.1 (Lipschitz Condition).

Consider an arbitrary set $\mathcal{Z}$. A function
$\Delta:\mathcal{Z}^{d}\rightarrow\mathbb{R}$ satisfies the Lipschitz
condition with bound $c\in\mathbb{R}$ if, for every $i\in[d]$ and for every
sequence of values $x_{1},\ldots,x_{d}\in\mathcal{Z}$ and
$y_{i}\in\mathbb{R}$,

$|\Delta(x_{1},x_{2},\ldots,x_{i-1},x_{i},x_{i+1},\ldots,x_{d})-\Delta(x_{1},x_{2},\ldots,x_{i-1},y_{i},x_{i+1},\ldots,x_{d})|\leq
c.$

######  Fact A.2 (McDiarmid’s Inequality (Mitzenmacher & Upfal, 2017;
Tolstikhin, 2017)).

Let $\Delta:\mathcal{Z}^{d}\rightarrow\mathbb{R}$ be a function that satisfies
the Lipschitz condition with bound $c\in\mathbb{R}$. Let $X_{1},\ldots,X_{d}$
be independent random variables from the set $\mathcal{Z}$ Then for all
$\lambda\geq 0$,

$\Pr\left[\Delta(X_{1},\ldots,X_{d})-\operatorname*{\mathbb{E}}\left[\Delta(X_{1},\ldots,X_{d})\right]\geq\lambda\right]\leq\exp{\left(-\frac{2\lambda^{2}}{dc^{2}}\right)}\,.$

######  Fact A.3 (Bernstein’s Inequality (Chung & Lu, 2006; Audibert et al.,
2009)).

Let $X_{1},\ldots,X_{d}$ be independent real-valued random variables such that
$|X_{i}|\leq c$ with probability one. Let $S_{d}=\sum_{i\in[d]}X_{i}$ and
$\operatorname*{\mathbb{V}\mathrm{ar}}\left[S_{d}\right]=\sum_{i\in[d]}\operatorname*{\mathbb{V}\mathrm{ar}}\left[X_{i}\right]$.
Then for all $\eta\in(0,1)$,

$\left|S_{d}-\operatorname*{\mathbb{E}}\left[S_{d}\right]\right|\leq\sqrt{2\operatorname*{\mathbb{V}\mathrm{ar}}\left[S_{d}\right]\ln\frac{2}{\eta}}+\frac{2c\ln\frac{2}{\eta}}{3}\,,$

with probability at least $1-\eta$.

##  Appendix B Proofs for Section 4.1

###### Proof of Lemma 4.1.

Our goal is to prove for all $t\in\mathbb{Z},$

$\displaystyle\Pr\left[\tilde{h}^{\prime}[\ell]=t\right]=\Pr\left[\vec{h}[\ell]+Z=t\right].$
(12)

The equation holds trivially for each integer $t\in{\left(0,n\right)}$. By
symmetry, we prove that the equation holds for each integer $t\geq n.$ In this
case,

$\displaystyle\Pr\left[\tilde{h}^{\prime}[\ell]=t\right]$
$\displaystyle=\Pr\left[\operatorname{\mathbb{DE}xp}\left({e^{-\varepsilon}}\right)=t-n\right]\cdot\Pr\left[\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)\geq
n\right]$ $\displaystyle={\left({\left(1-e^{-\varepsilon}\right)}\cdot
e^{-\varepsilon\cdot{\left(t-n\right)}}\right)}\cdot{\left(\sum_{j\geq
n-\vec{h}[\ell]}\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}\cdot
e^{-\varepsilon\cdot j}\right)}$
$\displaystyle={\left(1-e^{-\varepsilon}\right)}\cdot
e^{-\varepsilon\cdot{\left(t-n\right)}}\cdot\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}\cdot\frac{e^{-\varepsilon\cdot{\left(n-\vec{h}[\ell]\right)}}}{1-e^{-\varepsilon}}$
$\displaystyle=\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}\cdot
e^{-\varepsilon\cdot{\left(t-\vec{h}[\ell]\right)}}$
$\displaystyle=\Pr\left[\vec{h}[\ell]+Z=t\right].$

∎

##  Appendix C Proofs for Section 4.2

###### Proof of Lemma 4.2.

Let $\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)$ denotes
a random variable following truncated Laplace distribution:

$\Pr\left[\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)=t\right]=\frac{1}{P_{norm}}\cdot
e^{-\varepsilon\cdot\left|{t}\right|},\,\forall t\in[{-B}\,.\,.\,{B}],$

where

$P_{norm}=1+2\cdot\sum_{j=1}^{B}e^{-\varepsilon\cdot
j}=1+2\cdot\frac{e^{-\varepsilon}-(e^{-\varepsilon})^{B+1}}{1-e^{-\varepsilon}}=\frac{1+e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}{1-e^{-\varepsilon}}.$
(13)

Conditioned on $\mathcal{E}_{B}$, all random noises introduced by Algorithm 1
follows truncated Laplace distribution. Therefore,

$\displaystyle\mathcal{A}{\left(\vec{r}\right)}[t]$
$\displaystyle=\frac{1}{d}\cdot\sum_{k=0}^{t+B}\sum_{j=1}^{\vec{r}[k]\cdot
d}\mathds{1}_{\left[k+\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)=t\right]},\,\quad\forall
t\in[{-B}\,.\,.\,{-1}].$ $\displaystyle\mathcal{A}{\left(\vec{r}\right)}[t]$
$\displaystyle=\frac{1}{d}\cdot\sum_{k=t-B}^{t+B}\sum_{j=1}^{\vec{r}[k]\cdot
d}\mathds{1}_{\left[k+\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)=t\right]},\,\quad\forall
t\in[{0}\,.\,.\,{n}].$ $\displaystyle\mathcal{A}{\left(\vec{r}\right)}[t]$
$\displaystyle=\frac{1}{d}\cdot\sum_{k=t-B}^{n}\sum_{j=1}^{\vec{r}[k]\cdot
d}\mathds{1}_{\left[k+\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)=t\right]},\,\quad\forall
t\in[{n+1}\,.\,.\,{n+B}],$

where $\mathds{1}_{\left[\cdot\right]}$ is the indicator for some event. Since
by assumption, we have $\vec{r}[t]=0$ for all
$t\in[{-B}\,.\,.\,{n+B}]\setminus[{0}\,.\,.\,{n}]$, the above equations can be
written in a unified manner:

$\displaystyle\mathcal{A}{\left(\vec{r}\right)}[t]=\frac{1}{d}\cdot\sum_{k=t-B}^{t+B}\sum_{j=1}^{\vec{r}[k]\cdot
d}\mathds{1}_{\left[k+\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)\equiv
t\right]},$ (14)

where for the ease of notations, we omit the modular operations on the indexes
and the events of the indicators. In particular, we assume
$\vec{r}[k]\doteq\vec{r}[\mathsf{mi}{\left({k}\right)}]$, and
$k+\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)\equiv t$
represents the event that
$\mathsf{mi}{\left({k+\operatorname{\mathbb{TDL}ap}\left({e^{-\varepsilon}},{B}\right)}\right)}=t$,
where

$\mathsf{mi}{\left({x}\right)}\doteq\begin{cases}x,&\text{ if
}x\in[{-B}\,.\,.\,{n+B}],\\\
{\left({\left(x+B\right)}\mod{\left(n+2B+1\right)}\right)}-B&\text{ otherwise
}.\end{cases}$

Combining the definition of $\boldsymbol{A}$, we can verify that

$\displaystyle\operatorname*{\mathbb{E}}\left[\mathcal{A}{\left(\vec{r}\right)}[t]\mid\mathcal{E}_{B}\right]$
$\displaystyle=\frac{1}{d}\cdot\frac{1}{P_{norm}}\cdot\sum_{k=-B}^{B}e^{-\varepsilon\cdot\left|{k}\right|}\cdot{\left(\vec{r}[t+k]\cdot
d\right)}$ $\displaystyle=\sum_{k=-B}^{B}\frac{1}{P_{norm}}\cdot
e^{-\varepsilon\cdot\left|{k}\right|}\cdot\vec{r}[t+k]$
$\displaystyle=\boldsymbol{A}[t,\cdot]\times\vec{r}.$

∎

##  Appendix D Proofs for Section 4.3

###### Proof of Lemma 4.3.

The proof consists of two parts. First, we show that the returned solution
$\vec{r}$ satisfies the constraint
$\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{r}\right\rangle=1$:

$\displaystyle\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{r}\right\rangle$
$\displaystyle=\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}-\frac{\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle-1}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}\cdot\boldsymbol{A}^{-1}\times\vec{a}^{\prime}\right\rangle$
$\displaystyle=\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle-\frac{\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle-1}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}\cdot\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle$
$\displaystyle=1.$

Next, we need to prove that $\vec{r}$ is an optimal solution. Consider an
arbitrary vector $\vec{v},$ s.t.,
$\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{v}\right\rangle=1.$ We want to
prove that
$\left\|{\boldsymbol{A}\times\vec{v}-\tilde{f}}\right\|_{p}\geq\left\|{\boldsymbol{A}\times\vec{r}-\tilde{f}}\right\|_{p}.$
The claim is trivial if
$\left\|{\boldsymbol{A}\times\vec{r}-\tilde{f}}\right\|_{p}=0$. Otherwise,
based on Algorithm 2, observe that

$\displaystyle\boldsymbol{A}\times\vec{r}-\tilde{f}=\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}=\boldsymbol{A}\times{\left(\frac{{\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle-1}}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}\cdot\boldsymbol{A}^{-1}\times\vec{a}.\right)}=\frac{{\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle-1}}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}\cdot\vec{a}.$

Since $\left\|{\vec{a}}\right\|_{p}=1$, it holds that
$\frac{\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}}{\left\|{\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}}\right\|_{p}}=\vec{a}.$
Therefore,

$\displaystyle 1-\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle$
$\displaystyle=\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{v}-\vec{u}\right\rangle$
$\displaystyle=\left\|{\boldsymbol{A}\times{\left(\vec{v}-\vec{u}\right)}}\right\|_{p}\cdot\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\frac{\boldsymbol{A}\times{\left(\vec{v}-\vec{u}\right)}}{\left\|{\boldsymbol{A}\times{\left(\vec{v}-\vec{u}\right)}}\right\|_{p}}\right\rangle,$
$\displaystyle 1-\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{u}\right\rangle$
$\displaystyle=\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{r}-\vec{u}\right\rangle$
$\displaystyle=\left\|{\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}}\right\|_{p}\cdot\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\frac{\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}}{\left\|{\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}}\right\|_{p}}\right\rangle$
$\displaystyle=\left\|{\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}}\right\|_{p}\cdot\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle.$

By the definition of $\vec{a},$ we have
$\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle\geq\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\frac{\boldsymbol{A}\times{\left(\vec{v}-\vec{u}\right)}}{\left\|{\boldsymbol{A}\times{\left(\vec{v}-\vec{u}\right)}}\right\|_{p}}\right\rangle,$
which proves that

$\displaystyle\left\|{\boldsymbol{A}\times{\left(\vec{r}-\vec{u}\right)}}\right\|_{p}$
$\displaystyle=\left\|{\boldsymbol{A}\times\vec{r}-\tilde{f}}\right\|_{p}$
$\displaystyle\leq\left\|{\boldsymbol{A}\times\vec{v}-\tilde{f}}\right\|_{p}=\left\|{\boldsymbol{A}\times{\left(\vec{v}-\vec{u}\right)}}\right\|_{p}.$

∎

###### Proof of Lemma 4.4.

When $\vec{r}$ is inputted to Algorithm 3, it satisfies
$\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]=1$. After line 1, it satisfies
$\vec{r}[t]=0$, for all $t\in[{-B}\,.\,.\,{n+B}]\setminus[{0}\,.\,.\,{n}].$
After line 7, it satisfies $\vec{r}[t]\in[0,1]$, for all
$t\in[{0}\,.\,.\,{n}]$. However, it may violate is that
$\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]$ should sum up to $1$.

Since the cumulative change to the sum $\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]$
is $s_{>1}+s_{<0}$, after line 7, we have
$\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]-1=s_{>1}+s_{<0}$. We claim that
$s_{>1}+s_{<0}\geq 0$.

Since $s_{<0}\geq 0$, the claim holds trivially if $s_{>1}=0.$ On the other
hand, if $s_{>1}<0$, then there exists some $t\in[{0}\,.\,.\,{n}]$, such that
$\vec{r}[t]=1$ after Line 6. However, after Line 6 and 7, we must have that
$\vec{r}[t]\in[0,1],\forall t\in[{0}\,.\,.\,{n}].$ Therefore,
$\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]\geq 1,$ and
$s_{>1}+s_{<0}=\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]-1\geq 0$.

In case that $s_{>1}+s_{<0}>0$, the algorithm needs to decreases the
$\vec{r}[t]$ to fix the constraint that
$\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]$ should sum up to $1$. Define the
function
$g(\tau)\doteq\sum_{t\in[{0}\,.\,.\,{n}]}\min\left\\{{\tau,\vec{r}[t]}\right\\}$.
The algorithm searches for the solution $\tau$ for which
$g(\tau)=s_{>1}+s_{<0}$. By intermediate value theorem, the solution always
exists, as

  * •

$g$ is a continuous function with respect to $\tau$;

  * •

$0=g(0)<s_{>1}+s_{<0}$;

  * •

$1+s_{>1}+s_{<0}=\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}[t]=g(1)>s_{>1}+s_{<0}.$

Finally the algorithm decreases each $\vec{r}[t]$ by
$\min\left\\{{\tau,\vec{r}[t]}\right\\}$ to fix the constraint so that they
sum up to $1$. ∎

##  Appendix E Proofs for Section 4.4

###### Proof of Lemma 4.6.

The proof relies on Fact 3.2. It’s worth emphasizing that $\boldsymbol{A}$ is
a matrix with row and column indices starting from $-B$ (up to $n+B)$, in
contrast to the matrix described in Fact 3.2, where indices commence from $0$.
With appropriate shifting, we observe that the eigenvalues of $\boldsymbol{A}$
are given by
$\displaystyle\varphi_{t}\doteq\left\langle\boldsymbol{A}[-B,:],\sqrt{n+2B+1}\cdot\vec{v}_{t}\right\rangle$
$\displaystyle=\frac{1}{P_{norm}}\cdot{\left(\sum_{j=-B}^{0}e^{-\varepsilon\cdot\left|{j+B}\right|}\cdot
w_{t}^{j+B}+\sum_{j=1}^{n}0\cdot
w_{t}^{j+B}+\sum_{j=n+1}^{n+B}e^{-\varepsilon\cdot\left|{j-{\left(n+B+1\right)}}\right|}\cdot
w_{t}^{j+B}\right)}$
$\displaystyle=\frac{w_{t}^{B}}{P_{norm}}\cdot{\left(1+\sum_{j=1}^{B}e^{-\varepsilon\cdot
j}\cdot w_{t}^{j}+\sum_{j=1}^{B}e^{-\varepsilon\cdot j}\cdot w_{t}^{-j}\cdot
w_{t}^{n+2B+1}\right)}$
$\displaystyle=\frac{w_{t}^{B}}{P_{norm}}\cdot{\left(1+\frac{(e^{-\varepsilon}\cdot
w_{t})^{1}-(e^{-\varepsilon}\cdot w_{t})^{B+1}}{1-e^{-\varepsilon}\cdot
w_{t}}+\frac{(e^{-\varepsilon}\cdot w_{t}^{-1})^{1}-(e^{-\varepsilon}\cdot
w_{t}^{-1})^{B+1}}{1-e^{-\varepsilon}\cdot w_{t}^{-1}}\right)}.$ Observe that

$\displaystyle 1+\frac{(e^{-\varepsilon}\cdot
w_{t})^{1}-(e^{-\varepsilon}\cdot
w_{t})^{{\left(B+1\right)}}}{1-e^{-\varepsilon}\cdot
w_{t}}+\frac{(e^{-\varepsilon}\cdot w_{t}^{-1})^{1}-(e^{-\varepsilon}\cdot
w_{t}^{-1})^{{\left(B+1\right)}}}{1-e^{-\varepsilon}\cdot w_{t}^{-1}}$
$\displaystyle=1+\frac{e^{-\varepsilon}\cdot
w_{t}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot w_{t}^{B}\cdot
w_{t}^{1}}{1-e^{-\varepsilon}\cdot w_{t}}+\frac{e^{-\varepsilon}\cdot
w_{t}^{-1}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot w_{t}^{-B}\cdot
w_{t}^{-1}}{1-e^{-\varepsilon}\cdot w_{t}^{-1}}$
$\displaystyle=1+\frac{e^{-\varepsilon}\cdot
w_{t}-e^{-2\varepsilon}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot
w_{t}^{B}\cdot{\left(w_{t}^{1}-e^{-\varepsilon}\right)}+e^{-\varepsilon}\cdot
w_{t}^{-1}-e^{-2\varepsilon}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot
w_{t}^{-B}\cdot{\left(w_{t}^{-1}-e^{-\varepsilon}\right)}}{1-e^{-\varepsilon}\cdot
w_{t}-e^{-\varepsilon}\cdot w_{t}^{-1}+e^{-2\varepsilon}}$
$\displaystyle=\frac{1-e^{-2\varepsilon}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot{\left(w_{t}^{B+1}+w_{t}^{-(B+1)}-e^{-\varepsilon}\cdot
w_{t}^{B}-e^{-\varepsilon}\cdot w_{t}^{-B}\right)}}{1-e^{-\varepsilon}\cdot
w_{t}-e^{-\varepsilon}\cdot w_{t}^{-1}+e^{-2\varepsilon}}.$

It is easy to see that each $\varphi_{t}$ can be computed in $O(1)$ time,
therefore all the eigenvalues can be computed in $O(n)$ time. This proves the
first part of the lemma. It follows that

$\displaystyle\boldsymbol{A}\times\boldsymbol{V}$
$\displaystyle=\boldsymbol{V}\operatorname{\bf
diag}{\left(\varphi_{-B},\varphi_{-B+1},\ldots,\varphi_{n+B}\right)},$
$\displaystyle\boldsymbol{A}$
$\displaystyle=\boldsymbol{V}\times\operatorname{\bf
diag}{\left(\varphi_{-B},\varphi_{-B+1},\ldots,\varphi_{n+B}\right)}\times{\left(\boldsymbol{V}\right)}^{-1}.$

Since $\varphi_{t}\neq 0$ for all $t\in[{-B}\,.\,.\,{n+B}],$ the inverse of
$\operatorname{\bf
diag}{\left(\varphi_{-B},\varphi_{-B+1},\ldots,\varphi_{n+B}\right)}$ is given
by

$\operatorname{\bf
diag}{\left(\varphi_{-B},\varphi_{-B+1},\ldots,\varphi_{n+B}\right)}^{-1}=\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}.$

Therefore, it can be verified that

$\displaystyle\boldsymbol{A}^{-1}$
$\displaystyle=\boldsymbol{V}\times\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}\times\boldsymbol{V}^{-1}.$

∎

###### Proof of Theorem 4.7.

All steps in Algorithm 3 clearly run in linear time, with the exception of the
search for the $\tau$ such that
$\sum_{t\in[{0}\,.\,.\,{n}]}\min\left\\{{\tau,\vec{r}[t]}\right\\}=s$.

We show that it can be found in $O(n\log n)$ time. First, sort the
$\vec{r}[t]$ in non-decreasing order in $O(n\log n)$ time. Now, assume that
$\vec{r}[0]\leq\cdots\leq\vec{r}[n]$. After this step, our goal is to find the
smallest $t^{*}\in[{0}\,.\,.\,{n}]$ such that $\vec{r}[t^{*}]\geq\tau$. Since

$\displaystyle\sum_{t=0}^{n}\min\left\\{{\tau,\vec{r}[t]}\right\\}$
$\displaystyle=\sum_{t=0}^{t^{*}-1}\vec{r}[t]+\sum_{t=t^{*}}^{n}\tau$
$\displaystyle=\sum_{t=0}^{t^{*}-1}\vec{r}[t]+{\left(n+1-t^{*}\right)}\tau=s,$

$t^{*}$ is the smallest number in $[{0}\,.\,.\,{n}]$ satisfying
$\sum_{t=0}^{t^{*}-1}\vec{r}[t]+{\left(n+1-t^{*}\right)}\vec{r}[t^{*}]\geq s$
and therefore can be identified in $O(n)$ time. Once $t^{*}$ is known, $\tau$
is determined by
$\tau={\left(s-\sum_{t=0}^{t^{*}-1}\vec{r}[t]\right)}/{\left(n+1-t^{*}\right)}.$

∎

##  Appendix F Proofs for Section 4.5

###### Proof of Lemma 4.9.

Since $\vec{f}$ is a vector in $\mathbb{R}^{n+1}$, we expand it into one in
$\mathbb{R}^{n+2B+1}$ by padding
$\vec{f}[-B]=\vec{f}[-B+1]=\cdots=\vec{f}[-1]=0$ to the front and
$\vec{f}[n+1]=\vec{f}[n+2]=\cdots=\vec{f}[n+B]=0$ to the back of the vector.
After this, $\vec{f}$ has the same dimension as $\vec{r}$, therefore
$\left\|{\vec{r}-\vec{f}}\right\|_{p}$ is well-defined.

We study how the error $\left\|{\vec{r}-\vec{f}}\right\|_{p}$ changes in
Algorithm 3, for $p=1,2,\infty.$ To begin with, we divide Algorithm 3 into 3
phrases:

  * •

Phrase 1 (Line 1): in which the algorithm rounds $\vec{r}[t]$ to $0$ for each
$t\in[{-B}\,.\,.\,{n+B}]\setminus[{0}\,.\,.\,{n}]$.

  * •

Phase 2 (Line 2 to Line 7), in which the algorithm clips the $\vec{r}[t]$ to
the range of $[0,1]$.

  * •

Phase 3 (Line 8 to Line 12), in which the algorithm adjusts the $\vec{r}[t]$
so that they sum up to $1$.

The error only decreases in Phase 2 and 3:

  * •

Since $\vec{f}[t]=0$ for each
$t\in[{-B}\,.\,.\,{n+B}]\setminus[{0}\,.\,.\,{n}],$ rounding $\vec{r}[t]$ to
$0$ for each $t\in[{-B}\,.\,.\,{n+B}]\setminus[{0}\,.\,.\,{n}]$ only decrease
$\left\|{\vec{r}-\vec{f}}\right\|_{p}$.

  * •

Since $\vec{f}[t]\in[0,1]$, for each $t\in[{0}\,.\,.\,{n}],$ clipping the
$\vec{r}[t],t\in[{0}\,.\,.\,{n}]$ to the range $[0,1]$ also decreases
$\left\|{\vec{r}-\vec{f}}\right\|_{p}$.

It remains to study the change of $\left\|{\vec{r}-\vec{f}}\right\|_{p}$ in
Phase 3. We discuss this for $p=1,2,\infty$ separately. To distinguish the
value of $\vec{r}$ at different phases of the algorithm, we denote it as
$\vec{r}_{0}$ before Phase 1, $\vec{r}_{1}$ right after Phase 1, $\vec{r}_{2}$
right after Phase 2, and $\vec{r}_{3}$ right after Phase 3.

$\left\|{\vec{r}_{3}-\vec{f}}\right\|_{1}\leq\left\|{\vec{r}_{1}-\vec{f}}\right\|_{1}:$
observe that in Phase 2 $\left\|{\vec{r}-\vec{f}}\right\|_{1}$ decreases by an
amount of $-s_{>1}+s_{<0}:$

$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{1}[t]-\vec{f}[t]}\right|$
$\displaystyle=\sum_{t\in
T_{>1}}\left|{\vec{r}_{1}[t]-\vec{f}[t]}\right|+\sum_{t\in
T_{<0}}\left|{\vec{r}_{1}[1]-\vec{f}[t]}\right|+\sum_{t\in[{0}\,.\,.\,{n}]\setminus{\left(T_{>1}\cup
T_{<0}\right)}}\left|{\vec{r}_{2}[t]-\vec{f}[t]}\right|$
$\displaystyle=\sum_{t\in
T_{>1}}{\left(\left|{1-\vec{f}[t]}\right|+{\vec{r}_{1}[t]-1}\right)}+\sum_{t\in
T_{<0}}{\left(\left|{0-\vec{f}[t]}\right|+{0-\vec{r}_{1}[t]}\right)}+\sum_{t\in[{0}\,.\,.\,{n}]\setminus{\left(T_{>1}\cup
T_{<0}\right)}}\left|{\vec{r}_{2}[t]-\vec{f}[t]}\right|$
$\displaystyle=\sum_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{2}[t]-\vec{f}[t]}\right|-s_{>1}+s_{<0}.$

In Phase 3, $\left\|{\vec{r}-\vec{f}}\right\|_{1}$ can increase by at most
$s_{>1}+s_{<0}$. To see that, observe that
$\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}_{2}[t]-1=\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}_{2}[t]-\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}_{1}[t]=s_{>1}+s_{<0}=s.$
After the adjustment, we have $\vec{r}_{3}[t]\leq\vec{r}_{2}[t]$ for each
$t\in[{0}\,.\,.\,{n}]$, and $\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}_{3}[t]=1$.
Therefore,

$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{3}[t]-\vec{f}[t]}\right|-\sum_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{2}[t]-\vec{f}[t]}\right|$
$\displaystyle\leq\sum_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{2}[t]-\vec{r}_{3}[t]}\right|$
$\displaystyle=\sum_{t\in[{0}\,.\,.\,{n}]}{\left(\vec{r}_{2}[t]-\vec{r}_{3}[t]\right)}=\sum_{t\in[{0}\,.\,.\,{n}]}\vec{r}_{2}[t]-1=s_{>1}+s_{<0}.$

It follows that

$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{3}[t]-\vec{f}[t]}\right|-\sum_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{1}[t]-\vec{f}[t]}\right|\leq
s_{>1}+s_{<0}-{\left(-s_{>1}+s_{<0}\right)}=2\cdot s_{>1}\leq 0.$

$\left\|{\vec{r}_{3}-\vec{f}}\right\|_{\infty}\leq
2\cdot\left\|{\vec{r}_{2}-\vec{f}}\right\|_{\infty}:$ Let
$b_{t}\doteq\left|{\vec{r}_{2}[t]-\vec{f}[t]}\right|$ for each
$t\in[{0}\,.\,.\,{n}]$, and $b_{\max}\doteq\max_{t\in[{0}\,.\,.\,{n}]}b_{t}.$
It is easy to see that

$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}{\left(\vec{r}_{2}[t]-\min\left\\{{b_{\max},\vec{r}_{2}[t]}\right\\}\right)}\leq\sum_{t\in[{0}\,.\,.\,{n}]}\vec{f}[t]=1.$

On the other hand, we have

$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}{\left(\vec{r}_{2}[t]-\min\left\\{{\tau,\vec{r}_{2}[t]}\right\\}\right)}=1.$

It follows that
$\sum_{t\in[{0}\,.\,.\,{n}]}\min\left\\{{\tau,\vec{r}_{2}[t]}\right\\}\leq\sum_{t\in[{0}\,.\,.\,{n}]}\min\left\\{{b_{\max},\vec{r}_{2}[t]}\right\\},$
and hence $\tau\leq b_{\max}.$

$\displaystyle\left\|{\vec{r}_{3}-\vec{f}}\right\|_{\infty}$
$\displaystyle=\max_{t\in[{0}\,.\,.\,{n}]}\left|{\vec{r}_{2}[t]-\min\left\\{{\tau,\vec{r}_{2}[t]}\right\\}-\vec{f}[t]}\right|$
$\displaystyle\leq\max_{t\in[{0}\,.\,.\,{n}]}{\left(\left|{\vec{r}_{2}[t]-\vec{f}[t]}\right|+\min\left\\{{\tau,\vec{r}_{2}[t]}\right\\}\right)}$
$\displaystyle\leq 2\cdot\left\|{\vec{r}_{2}-\vec{f}}\right\|_{\infty}.$

$\left\|{\vec{r}_{3}-\vec{f}}\right\|_{2}\leq\left\|{\vec{r}_{2}-\vec{f}}\right\|_{2}:$
without lose of generality, assume that
$\vec{r}_{2}[0]\leq\vec{r}_{2}[1]\leq\ldots\leq\vec{r}_{2}[n].$ The adjustment
step (line 11) can be replaced by Algorithm 5.

Algorithm 5 Iterated Adjustment

1: $t\leftarrow 0$

2: while $t\leq n$ and $s>0$ do

3: $\tau^{\prime}\leftarrow\min{\left(\vec{r}[t],\frac{s}{n-t+1}\right)}$

4: $\vec{r}[j]\leftarrow\vec{r}[j]-\tau^{\prime},\,\forall
j\in[{t}\,.\,.\,{n}]$

5: $s\leftarrow s-\tau^{\prime}\cdot{\left(n-t+1\right)}$

6: $t\leftarrow t+1$

7: end while

We claim that, $\left\|{\vec{r}-\vec{f}}\right\|_{2}$ does not increase at
each iteration. Fix some iteration $t$. Note that $\vec{r}[j]$ does not change
for $j\in[{0}\,.\,.\,{t-1}]$, whereas $\vec{r}[j]$ decreases by
$\tau^{\prime}$ for $j\in[{t}\,.\,.\,{n}]$. Therefore, the total change of
$\left\|{\vec{r}-\vec{f}}\right\|_{2}^{2}$ is given by

$\displaystyle\sum_{j\in[{t}\,.\,.\,{n}]}\left|{\vec{r}[t]-\tau^{\prime}-\vec{f}[t]}\right|^{2}-\sum_{j\in[{t}\,.\,.\,{n}]}\left|{\vec{r}[t]-\vec{f}[t]}\right|^{2}$
$\displaystyle=\sum_{j\in[{t}\,.\,.\,{n}]}-\tau^{\prime}\cdot{\left(2\cdot\vec{r}[t]-2\cdot\vec{f}[t]-\tau^{\prime}\right)}$
$\displaystyle=-\tau^{\prime}\cdot{\left(2\cdot\sum_{j\in[{t}\,.\,.\,{n}]}\vec{r}[t]-2\cdot\sum_{j\in[{t}\,.\,.\,{n}]}\vec{f}[t]-\sum_{j\in[{t}\,.\,.\,{n}]}\tau^{\prime}\right)}$
$\displaystyle=-\tau^{\prime}\cdot{\left(2\cdot{\left(\sum_{j\in[{t}\,.\,.\,{n}]}\vec{r}[t]-1\right)}-{\left(n-t+1\right)}\cdot\tau^{\prime}\right)}$
$\displaystyle\leq 0,$

where the last inequality follows since $0\leq\tau^{\prime}\leq\vec{r}[j]$ for
each $j\in[{t}\,.\,.\,{n}].$ ∎

We present the proof for Lemma 4.11 first, then the proof for Lemma 4.10.

###### Proof of Lemma 4.11.

Since $\vec{f}$ is a vector in $\mathbb{R}^{n+1}$, we expand it into one in
$\mathbb{R}^{n+2B+1}$ by padding
$\vec{f}[-B]=\vec{f}[-B+1]=\cdots=\vec{f}[-1]=0$ to the front and
$\vec{f}[n+1]=\vec{f}[n+2]=\cdots=\vec{f}[n+B]=0$ to the back of the vector,
so that $\boldsymbol{A}\times\vec{f}$ is well-defined.

Recall that
$\tilde{h}[\ell]=\vec{h}[\ell]+\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right),\,\forall\ell\in\mathcal{D}.$
Since $B\geq\frac{1}{\varepsilon}\cdot\ln\frac{2\cdot
d}{\eta\cdot{\left(e^{\varepsilon}+1\right)}}$. Then

$\displaystyle\Pr\left[\left|{\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)}\right|>B\right]$
$\displaystyle=2\cdot\sum_{t\geq
B}\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}\cdot
e^{-\varepsilon\cdot\left|{t}\right|}=2\cdot\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}}\cdot\frac{e^{-\varepsilon\cdot
B}}{1-e^{-\varepsilon}}=\frac{2\cdot e^{-\varepsilon\cdot
B}}{1+e^{-\varepsilon}}\leq\frac{\eta}{d}.$

By union bound,

$\displaystyle\Pr\left[\max_{\ell\in\mathcal{D}}\left|{\tilde{h}[\ell]-\vec{h}[\ell]}\right|>B\right]\leq\eta.$

Assuming that
$\max_{\ell\in\mathcal{D}}\left|{\tilde{h}[\ell]-\vec{h}[\ell]}\right|\leq B$,
$\tilde{f}=\mathcal{A}{({\vec{f}})}$ can be equivalent viewed as the outcome
of running Algorithm 1 with input $\vec{f}$, (conditioned on the event
$\mathcal{E}_{B}$ that all noises added by the algorithm are absolutely
bounded by $B$). It follows by Lemma 4.2 that

$\displaystyle\operatorname*{\mathbb{E}}\left[\tilde{f}\right]=\operatorname*{\mathbb{E}}\left[\mathcal{A}{\left(\vec{f}\right)}\mid\mathcal{E}_{B}\right]=\boldsymbol{A}\times\vec{f}.$

Bounding $\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}$. Under
these assumptions,

$\displaystyle\operatorname*{\mathbb{E}}\left[\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[\left\|{\tilde{f}-\operatorname*{\mathbb{E}}\left[\tilde{f}\right]}\right\|_{1}\right]=\operatorname*{\mathbb{E}}\left[\sum_{t=-B}^{n+B}\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|\right]$
$\displaystyle=\sum_{t=-B}^{n+B}\operatorname*{\mathbb{E}}\left[\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|\right]=\sum_{t=-B}^{n+B}\operatorname*{\mathbb{E}}\left[\sqrt{\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|^{2}}\right]$
$\displaystyle\leq\sum_{t=-B}^{n+B}\sqrt{\operatorname*{\mathbb{E}}\left[\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|^{2}\right]}.$

Consider a $t\in[{-B}\,.\,.\,{n+B}]$. Conditioned on the event that
$\max_{\ell\in\mathcal{D}}\left|{\tilde{h}[\ell]-\vec{h}[\ell]}\right|\leq B$,
the noises added to the $\tilde{h}[\ell]$ follows independent truncated
Laplace distribution. For each $\ell\in\mathcal{D}$, define the indicator
$\mathds{1}_{\left[\tilde{h}[\ell]=t\right]}$ for the event that
$\tilde{h}[\ell]=t$. We have

$\Pr\left[\mathds{1}_{\left[\tilde{h}[\ell]=t\right]}=1\right]=\frac{e^{-\varepsilon\cdot\left|{t-\vec{h}[\ell]}\right|}}{P_{norm}},$

where
$P_{norm}=\frac{1+e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}{1-e^{-\varepsilon}}.$
Since
$\tilde{f}[t]=\frac{1}{d}\cdot\sum_{\ell\in\mathcal{D}}\mathds{1}_{\left[\tilde{h}[\ell]=t\right]},$
we have

$\displaystyle\operatorname*{\mathbb{E}}\left[\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{V}\mathrm{ar}}\left[\frac{1}{d}\cdot\sum_{\ell\in\mathcal{D}}\mathds{1}_{\left[\tilde{h}[\ell]=t\right]}\right]$
$\displaystyle=\frac{1}{d^{2}}\cdot\sum_{\ell\in\mathcal{D}}\operatorname*{\mathbb{V}\mathrm{ar}}\left[\mathds{1}_{\left[\tilde{h}[\ell]=t\right]}\right]$
$\displaystyle=\frac{1}{d^{2}}\cdot\sum_{\ell\in\mathcal{D}}\frac{e^{-\varepsilon\cdot\left|{t-\vec{h}[\ell]}\right|}}{P_{norm}}\cdot{\left(1-\frac{e^{-\varepsilon\cdot\left|{t-\vec{h}[\ell]}\right|}}{P_{norm}}\right)}$
$\displaystyle\leq\frac{1}{d}\cdot\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right].$

Note that
$1-\frac{e^{-\varepsilon\cdot\left|{t-\vec{h}[\ell]}\right|}}{P_{norm}}\geq
1-\frac{1}{P_{norm}}=1-\frac{1-e^{-\varepsilon}}{1+e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}=\frac{2e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}{1+e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}$.
So the inequality is tight up to a factor of
$\frac{2e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}{1+e^{-\varepsilon}-2\cdot(e^{-\varepsilon})^{B+1}}$.
It concludes that

$\displaystyle\operatorname*{\mathbb{E}}\left[\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}\right]\leq\sum_{t=-B}^{n+B}\sqrt{\operatorname*{\mathbb{E}}\left[\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|^{2}\right]}=\sum_{t=-B}^{n+B}\sqrt{\frac{1}{d}\cdot\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}.$

Further, $\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}$ is a
function of the random variables $\tilde{h}[\ell]^{\prime}s:$

$\displaystyle\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}$
$\displaystyle=\sum_{t\in[{-B}\,.\,.\,{n+B}]}\left|{\frac{1}{d}\cdot\sum_{\ell\in\mathcal{D}}\mathds{1}_{\left[\tilde{h}[\ell]=t\right]}-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|.$

Changing the value of one $\tilde{h}[\ell]$ affects at most two terms on the
right hand side of the equation, each by $1/d$. By Definition A.1,
$\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}$ satisfies the
Lipschitz condition with bound $2/d$. Therefore, via Fact A.2,

$\displaystyle\Pr\left[\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}-\operatorname*{\mathbb{E}}\left[\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{1}\right]\geq\sqrt{\frac{2\ln\frac{1}{\eta}}{d}}\right]\leq\exp{\left(-\frac{2}{d\cdot{\left(2/d\right)}^{2}}\cdot\frac{2\ln\frac{1}{\eta}}{d}\right)}=\eta.$

Bounding $\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}$.
Similarly,

$\displaystyle\operatorname*{\mathbb{E}}\left[\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[\left\|{\tilde{f}-\operatorname*{\mathbb{E}}\left[\tilde{f}\right]}\right\|_{2}\right]=\operatorname*{\mathbb{E}}\left[\sqrt{\sum_{t=-B}^{n+B}\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|^{2}}\right]$
$\displaystyle\leq\sqrt{\sum_{t=-B}^{n+B}\operatorname*{\mathbb{E}}\left[\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|^{2}\right]}\leq\sqrt{\sum_{t=-B}^{n+B}\frac{1}{d}\cdot\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}=\sqrt{\frac{1}{d}}.$

Further, $\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}$ is a
function of the random variables $\tilde{h}[\ell]:$

$\displaystyle\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}$
$\displaystyle=\sqrt{\sum_{t\in[{-B}\,.\,.\,{n+B}]}\left|{\frac{1}{d}\cdot\sum_{\ell\in\mathcal{D}}\mathds{1}_{\left[\tilde{h}[\ell]=t\right]}-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|^{2}},$

We can view
$\tilde{f}={\left({\left(1/d\right)}\cdot\sum_{\ell\in\mathcal{D}}\mathds{1}_{\left[\tilde{h}[\ell]=-B\right]},\ldots,{\left(1/d\right)}\cdot\sum_{\ell\in\mathcal{D}}\mathds{1}_{\left[\tilde{h}[\ell]=n+B\right]}\right)}$.
Assume that we change the value of one $\tilde{h}[\ell]$, to obtain a vector
$\tilde{f}^{\prime},$ which differs from $\tilde{f}$ by two coordinates, each
by $1/d$. Therefore,
$\left\|{\tilde{f}^{\prime}-\tilde{f}}\right\|_{2}=\sqrt{2}/d$, and

$\displaystyle\left|{\left\|{\tilde{f}^{\prime}-\boldsymbol{A}\times\vec{f}}\right\|_{2}-\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}}\right|\leq\left\|{\tilde{f}^{\prime}-\tilde{f}}\right\|_{2}\leq\sqrt{2}/d.$

By Definition A.1,
$\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}$ satisfies the
Lipschitz condition with bound $\sqrt{2}/d$. Therefore, via Fact A.2,

$\displaystyle\Pr\left[\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}-\operatorname*{\mathbb{E}}\left[\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{2}\right]\geq\sqrt{\frac{\ln\frac{1}{\eta}}{d}}\right]\leq\exp{\left(-\frac{2}{d\cdot{\left(\sqrt{2}/d\right)}^{2}}\cdot\frac{\ln\frac{1}{\eta}}{d}\right)}=\eta.$

Bounding $\left\|{\tilde{f}-\boldsymbol{A}\times\vec{f}}\right\|_{\infty}$. To
prove the last part, by Bernstein’s inequality (Fact A.3), with probability at
least $1-1/(n\eta)$, we have

$\displaystyle\left|{\tilde{f}[t]-\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]}\right|$
$\displaystyle\leq\sqrt{2\cdot\operatorname*{\mathbb{V}\mathrm{ar}}\left[\tilde{f}[t]\right]\cdot\ln\frac{n}{\eta}}+\frac{2}{3}\cdot\ln\frac{n}{\eta}$
$\displaystyle\leq\sqrt{\frac{2}{d}\cdot{\left(\sum_{\ell\in\mathcal{D}}\frac{e^{-\varepsilon\cdot\left|{t-\vec{h}[\ell]}\right|}}{P_{norm}}\right)}\cdot\ln\frac{n}{\eta}}+\frac{2}{3d}\cdot\ln\frac{n}{\eta}$
$\displaystyle=\frac{1}{\sqrt{d}}\cdot\sqrt{2\cdot\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]\cdot\ln\frac{n}{\eta}}+\frac{2}{3d}\cdot\ln\frac{n}{\eta}.$

It is not easy to have a non-trivial bound for
$\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]$, which depends on the
histogram $\vec{h}$. On the other hand, a trivial bound can be given by

$\operatorname*{\mathbb{E}}\left[\tilde{f}[t]\right]\leq\frac{1}{d\cdot
P_{norm}}\cdot\sum_{\ell\in\mathcal{D}}e^{-\varepsilon\cdot
0}=\frac{1}{P_{norm}}.$

∎

###### Proof of Lemma 4.10.

We first bound $\left\|{\boldsymbol{A}^{-1}}\right\|_{2}$, since it is the
easier part of the proof. According to Lemma 4.6,

$\displaystyle\left\|{\boldsymbol{A}^{-1}}\right\|_{2}$
$\displaystyle=\left\|{\boldsymbol{V}\times\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}\times\boldsymbol{V}^{-1}}\right\|_{2}$
(15)
$\displaystyle\leq\left\|{\boldsymbol{V}}\right\|_{2}\cdot\left\|{\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}}\right\|_{2}\cdot\left\|{\boldsymbol{V}^{-1}}\right\|_{2}.$
(16)

Since $\boldsymbol{V}$ is the discrete Fourier transform matrix with
orthonormal column and row vectors, it holds that
$\left\|{\boldsymbol{V}}\right\|_{2}=\left\|{\boldsymbol{V}^{-1}}\right\|_{2}=1$.
Moreover, $\left\|{\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}}\right\|_{2}=\max_{t\in[{-B}\,.\,.\,{n+B}]}\frac{1}{|\varphi_{t}|}$.
We proceed to show that to bounds
$\max_{t\in[{-B}\,.\,.\,{n+B}]}\frac{1}{|\varphi_{t}|}=1/\min_{t\in[{-B}\,.\,.\,{n+B}]}|\varphi_{t}|$.
For each $t\in[{-B}\,.\,.\,{n+B}]$,

$\displaystyle\left|{\varphi_{t}}\right|=\left|{\frac{w_{t}^{B}}{P_{norm}}\cdot\frac{1-e^{-2\varepsilon}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot{\left(w_{t}^{B+1}+w_{t}^{-(B+1)}-e^{-\varepsilon}\cdot
w_{t}^{B}-e^{-\varepsilon}\cdot w_{t}^{-B}\right)}}{1-e^{-\varepsilon}\cdot
w_{t}-e^{-\varepsilon}\cdot w_{t}^{-1}+e^{-2\varepsilon}}}\right|$

We have

$\displaystyle\left|{w_{t}^{B}}\right|$ $\displaystyle=1.$
$\displaystyle\left|{1-e^{-\varepsilon}\cdot w_{t}-e^{-\varepsilon}\cdot
w_{t}^{-1}+e^{-2\varepsilon}}\right|$ $\displaystyle\leq\left|{1+2\cdot
e^{-\varepsilon}+e^{-2\varepsilon}}\right|={\left(1+e^{-\varepsilon}\right)}^{2}.$

and

$\displaystyle\left|{1-e^{-2\varepsilon}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot{\left(w_{t}^{B+1}+w_{t}^{-(B+1)}-e^{-\varepsilon}\cdot
w_{t}^{B}-e^{-\varepsilon}\cdot w_{t}^{-B}\right)}}\right|$
$\displaystyle\geq\left|{1-e^{-2\varepsilon}}\right|+e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot\left|{w_{t}^{B+1}+w_{t}^{-(B+1)}-e^{-\varepsilon}\cdot
w_{t}^{B}-e^{-\varepsilon}\cdot w_{t}^{-B}}\right|$ $\displaystyle\geq
1-e^{-2\varepsilon}-e^{-\varepsilon\cdot{\left(B+1\right)}}\cdot
2\cdot{\left(1+e^{-\varepsilon}\right)}$
$\displaystyle={\left(1-e^{-\varepsilon}-2\cdot
e^{-\varepsilon\cdot{\left(B+1\right)}}\right)}\cdot{\left(1+e^{-\varepsilon}\right)}.$

Therefore

$\left|{\varphi_{t}}\right|\geq\frac{1}{P_{norm}}\cdot\frac{{\left(1-e^{-\varepsilon}-2\cdot
e^{-\varepsilon\cdot{\left(B+1\right)}}\right)}}{{\left(1+e^{-\varepsilon}\right)}}.$

To bound $\left\|{\boldsymbol{A}^{-1}}\right\|_{1}$ and
$\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}$, we will first show that there
two values are equal; then we bound just
$\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}$.

$\left\|{\boldsymbol{A}^{-1}}\right\|_{1}=\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}.$
We will show that, $\boldsymbol{A}^{-1}$ is also a circulant matrix. Since
each column of a circulant matrix has the same $\ell_{1}$-norm as each row of
the matrix, and since

$\displaystyle\left\|{\boldsymbol{A}^{-1}}\right\|_{1}$
$\displaystyle=\max_{t\in[{-B}\,.\,.\,{n+B}]}\left\|{\boldsymbol{A}^{-1}[\cdot,t]}\right\|_{1},$
$\displaystyle\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}$
$\displaystyle=\max_{t\in[{-B}\,.\,.\,{n+B}]}\left\|{\boldsymbol{A}^{-1}[t,\cdot]}\right\|_{1},$

it follows that
$\left\|{\boldsymbol{A}^{-1}}\right\|_{1}=\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}.$
It remains to show that $\boldsymbol{A}^{-1}$ is also a circulant matrix.
According to Lemma 4.6, $\boldsymbol{V}$ is the discrete Fourier transform
matrix whose rows and columns are indexed from $-B$ to $n+B$. Therefore
$\forall k,\ell\in[{-B}\,.\,.\,{n+B}]$, it holds that

$\displaystyle\boldsymbol{V}[k,\ell]$
$\displaystyle=\frac{1}{\sqrt{n+2B+1}}\cdot\varphi_{\ell}^{k+B}$
$\displaystyle=\frac{1}{\sqrt{n+2B+1}}\cdot
e^{-\frac{2\pi{\left(k+B\right)}\cdot{\left(\ell+B\right)}\cdot
i}{n+2B+1}},\,$ $\displaystyle\boldsymbol{V}^{-1}[k,\ell]$
$\displaystyle=\frac{1}{\sqrt{n+2B+1}}\cdot\varphi_{k}^{-{\left(\ell+B\right)}}$
$\displaystyle=\frac{1}{\sqrt{n+2B+1}}\cdot
e^{\frac{2\pi{\left(k+B\right)}\cdot{\left(\ell+B\right)}\cdot i}{n+2B+1}}.$

Since $\boldsymbol{A}^{-1}=\boldsymbol{V}\times\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}\times\boldsymbol{V}^{-1},$
we can verify that

$\displaystyle\boldsymbol{A}^{-1}[k,\ell]$
$\displaystyle=\boldsymbol{V}[k,\cdot]\times\operatorname{\bf
diag}{\left(\varphi_{-B}^{-1},\varphi_{-B+1}^{-1},\ldots,\varphi_{n+B}^{-1}\right)}\times\boldsymbol{V}^{-1}[\cdot,\ell]$
$\displaystyle=\frac{1}{n+2B+1}\cdot\left\langle{\left(e^{-\frac{2\pi{\left(k+B\right)}\cdot
0\cdot
i}{n+2B+1}}\varphi_{-B}^{-1},\ldots,e^{-\frac{2\pi{\left(k+B\right)}\cdot{\left(n+2B\right)}\cdot
i}{n+2B+1}}\varphi_{n+B}^{-1}\right)},{\left(e^{\frac{2\pi{0\cdot{\left(\ell+B\right)}}\cdot
i}{n+2B+1}},\ldots,e^{\frac{2\pi{{\left(n+2B\right)}\cdot{\left(\ell+B\right)}}\cdot
i}{n+2B+1}}\right)}\right\rangle$
$\displaystyle=\frac{1}{n+2B+1}\cdot\sum_{t\in[{-B}\,.\,.\,{n+B}]}e^{-\frac{2\pi{\left(k-\ell\right)}\cdot{\left(t+B\right)}\cdot
i}{n+2B+1}}\varphi_{t}^{-1}.$

Now it is easy to see that $\boldsymbol{A}^{-1}$ is a circulant matrix, since
for each $-B\leq k<n+B$, we have

$\displaystyle\boldsymbol{A}^{-1}[k+1,\ell+1]$
$\displaystyle=\boldsymbol{A}^{-1}[k,\ell],\quad\forall\ell\in[{-B}\,.\,.\,{n+B-1}],$
$\displaystyle\boldsymbol{A}^{-1}[k+1,-B]$
$\displaystyle=\boldsymbol{A}^{-1}[k,n+B].$

Bounding $\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}.$ We will show that
for each $\vec{v}\in\mathbb{R}^{n+2B+1}$, it holds that

$\left\|{\boldsymbol{A}^{-1}\vec{v}}\right\|_{1}\leq\frac{2+e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}-4\cdot
e^{-\varepsilon\cdot B}}\cdot P_{norm}\cdot\left\|{\vec{v}}\right\|_{1}.$

Since $\boldsymbol{A}$ is invertible, let
$\vec{x}\doteq\boldsymbol{A}^{-1}\vec{v}$. It reduces to prove that

$\left\|{\vec{x}}\right\|_{1}\leq\frac{2+e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}-4\cdot
e^{-\varepsilon\cdot B}}\cdot
P_{norm}\cdot\left\|{\boldsymbol{A}\vec{x}}\right\|_{1}.$

To finish the proof, we need the following lemma.

######  Lemma F.1.

Let $\vec{x}\in\mathbb{R}^{n+2B+1}$ and assume that for each
$t\in[{-B}\,.\,.\,{n+B}]$, there exists $b_{t}\in\mathbb{R}_{\geq 0}$, s.t.
$\left|{{\boldsymbol{A}[t,\cdot]\times\vec{x}}}\right|\leq b_{t}$. The for
each $t\in[{-B}\,.\,.\,{n+B}]$, we have

$\left|{\vec{x}[t]}\right|\leq\frac{e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot{\left(P_{norm}\cdot{\left(b_{t}+\frac{b_{t-1}+b_{t+1}}{e^{-\varepsilon}+e^{\varepsilon}}\right)}+\frac{e^{-\varepsilon\cdot
B}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot{\left(\left|{\vec{x}{\left[{t-B-1}\right]}}\right|+\left|{\vec{x}{\left[{t+B+1}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t-B}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t+B}\right]}}\right|\right)}\right)},$

where for simplicity we omit the modular operations on the subscripts and
indexes. In particular, we define $b_{-B-1}\doteq b_{n+B}$,
$b_{n+B+1}=b_{-B}$, and for each $t\notin[{-B}\,.\,.\,{n+B}]$, we let
$\vec{x}[t]\doteq\vec{x}[{\left({\left(t+B\right)}\mod{({n+2B+1})}\right)}+{\left(-B\right)}]$.

Based on Lemma F.1, we have

$\displaystyle\sum_{t\in[{-B}\,.\,.\,{n+B}]}\left|{\vec{x}[t]}\right|$
$\displaystyle\leq\sum_{t\in[{-B}\,.\,.\,{n+B}]}\frac{e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot{\left(\begin{array}[]{c}P_{norm}\cdot{\left(b_{t}+\frac{b_{t-1}+b_{t+1}}{e^{-\varepsilon}+e^{\varepsilon}}\right)}+\\\
\frac{e^{-\varepsilon\cdot
B}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot{\left(\left|{\vec{x}{\left[{t-B-1}\right]}}\right|+\left|{\vec{x}{\left[{t+B+1}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t-B}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t+B}\right]}}\right|\right)}\end{array}\right)}$
$\displaystyle=\sum_{t\in[{-B}\,.\,.\,{n+B}]}\frac{e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot
P_{norm}\cdot
b_{t}\cdot{\left(1+\frac{2}{e^{-\varepsilon}+e^{\varepsilon}}\right)}+4\cdot\sum_{t\in[{-B}\,.\,.\,{n+B}]}\frac{e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot\frac{e^{-\varepsilon\cdot
B}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot\left|{\vec{x}[t]}\right|$
$\displaystyle=\sum_{t\in[{-B}\,.\,.\,{n+B}]}\frac{2+e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot
P_{norm}\cdot b_{t}+\sum_{t\in[{-B}\,.\,.\,{n+B}]}\frac{4\cdot
e^{-\varepsilon\cdot
B}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot\left|{\vec{x}[t]}\right|.$

This implies that

$\displaystyle\frac{e^{\varepsilon}-e^{-\varepsilon}-4\cdot
e^{-\varepsilon\cdot
B}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot\sum_{t\in[{-B}\,.\,.\,{n+B}]}\left|{\vec{x}[t]}\right|$
$\displaystyle\leq\sum_{t\in[{-B}\,.\,.\,{n+B}]}\frac{2+e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot
P_{norm}\cdot b_{t},$
$\displaystyle\Longleftrightarrow\sum_{t\in[{-B}\,.\,.\,{n+B}]}\left|{\vec{x}[t]}\right|$
$\displaystyle\leq\frac{2+e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}-4\cdot
e^{-\varepsilon\cdot B}}\cdot
P_{norm}\cdot\sum_{t\in[{-B}\,.\,.\,{n+B}]}b_{t},$

∎

###### Proof of Lemma F.1.

Fix a $t\in[{-B}\,.\,.\,{n+B}].$ By assumption, we have

$\displaystyle P_{norm}\cdot b_{t}$ $\displaystyle\geq
P_{norm}\cdot\left|{\boldsymbol{A}{\left[{t,\cdot}\right]}\times\vec{x}}\right|$
$\displaystyle=\left|{\sum_{j\in[B]}e^{-\varepsilon\cdot
j}\cdot\vec{x}{\left[{t-j}\right]}+e^{-\varepsilon\cdot
0}\cdot\vec{x}{\left[{t}\right]}+\sum_{j\in[B]}e^{-\varepsilon\cdot
j}\cdot\vec{x}{\left[{t+j}\right]}}\right|.$

On the other hand, since $\boldsymbol{A}$ is a circulant matrix,

$\displaystyle P_{norm}\cdot b_{t-1}$ $\displaystyle\geq
P_{norm}\cdot\left|{\boldsymbol{A}{\left[{{t-1},\cdot}\right]}\times\vec{x}}\right|$
$\displaystyle=\left|{\sum_{j\in[B+1]}e^{-\varepsilon\cdot(j-1)}\cdot\vec{x}{\left[{t-j}\right]}+e^{-\varepsilon}\cdot\vec{x}{\left[{t}\right]}+\sum_{j\in[B-1]}e^{-\varepsilon\cdot(j+1)}\cdot\vec{x}{\left[{t+j}\right]}}\right|,$
$\displaystyle P_{norm}\cdot b_{t+1}$ $\displaystyle\geq
P_{norm}\cdot\left|{\boldsymbol{A}{\left[{t+1,\cdot}\right]}\times\vec{x}}\right|$
$\displaystyle=\left|{\sum_{j\in[B-1]}e^{-\varepsilon\cdot(j+1)}\cdot\vec{x}{\left[{t-j}\right]}+e^{-\varepsilon}\cdot\vec{x}{\left[{t}\right]}+\sum_{j\in[B+1]}e^{-\varepsilon\cdot(j-1)}\cdot\vec{x}{\left[{t+j}\right]}}\right|.$

Therefore

$\displaystyle
P_{norm}\cdot{\left(b_{t}+\frac{b_{t-1}+b_{t+1}}{e^{-\varepsilon}+e^{\varepsilon}}\right)}$
$\displaystyle\geq
P_{norm}\cdot\left|{\boldsymbol{A}{\left[{t,\cdot}\right]}\times\vec{x}-\frac{1}{e^{-\varepsilon}+e^{\varepsilon}}\cdot{\left(\boldsymbol{A}{\left[{t-1,\cdot}\right]}\times\vec{x}+\boldsymbol{A}{\left[{t+1,\cdot}\right]}\times\vec{x}\right)}}\right|$
$\displaystyle=\left|{\begin{array}[]{c}-\frac{e^{-\varepsilon\cdot
B}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot\vec{x}{\left[{t-B-1}\right]}+{\left(1-\frac{e^{\varepsilon}}{e^{-\varepsilon}+e^{\varepsilon}}\right)}\cdot
e^{-\varepsilon\cdot
B}\cdot\vec{x}{\left[{t-B}\right]}+{\left(1-\frac{2e^{-\varepsilon}}{e^{-\varepsilon}+e^{\varepsilon}}\right)}\cdot\vec{x}{\left[{t}\right]}\\\
+{\left(1-\frac{e^{\varepsilon}}{e^{-\varepsilon}+e^{\varepsilon}}\right)}\cdot
e^{-\varepsilon\cdot
B}\cdot\vec{x}{\left[{t+B}\right]}-\frac{e^{-\varepsilon\cdot
B}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot\vec{x}{\left[{t+B+1}\right]}\end{array}}\right|$
$\displaystyle\geq\frac{e^{\varepsilon}-e^{-\varepsilon}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot\left|{\vec{x}{\left[{t}\right]}}\right|-\frac{e^{-\varepsilon\cdot
B}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot{\left(\left|{\vec{x}{\left[{t-B-1}\right]}}\right|+\left|{\vec{x}{\left[{t+B+1}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t-B}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t+B}\right]}}\right|\right)}.$

It concludes that

$\left|{\vec{x}{\left[{t}\right]}}\right|\leq\frac{e^{-\varepsilon}+e^{\varepsilon}}{e^{\varepsilon}-e^{-\varepsilon}}\cdot{\left(P_{norm}\cdot{\left(b_{t}+\frac{b_{t-1}+b_{t+1}}{e^{-\varepsilon}+e^{\varepsilon}}\right)}+\frac{e^{-\varepsilon\cdot
B}}{e^{-\varepsilon}+e^{\varepsilon}}\cdot{\left(\left|{\vec{x}{\left[{t-B-1}\right]}}\right|+\left|{\vec{x}{\left[{t+B+1}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t-B}\right]}}\right|+e^{-\varepsilon}\cdot\left|{\vec{x}{\left[{t+B}\right]}}\right|\right)}\right)}.$

∎

##  Appendix G Proof for Section 5

We show that, the lower bound in Theorem 1.2 applies to our algorithms, if
$\frac{1}{d}\,\big{(}\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\big{)}^{2}\in
o{\left(\frac{1}{\sqrt{d}}\cdot\frac{\varepsilon}{c\cdot
e^{c\cdot\varepsilon}}\right)}$, i.e., $\frac{1}{\sqrt{d}}\in
o{\left(\big{(}\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}\big{)}^{2}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}\right)}$.
We need the following lemma.

######  Lemma G.1.

Let $\mathcal{A}$ be the discrete Laplace mechanism,
$C_{A}={\left(\operatorname{\mathbb{DL}ap}\left({e^{-\varepsilon}}\right)\right)}^{d}$,
$F_{\mathcal{A}}(\vec{h},C_{A})=\vec{h}+C_{A}$ and $\mathcal{R}$ be the
profile reconstruction algorithm stated in Theorem 1.1. Then
$\Delta_{\mathcal{R}\circ\mathcal{A}}\in
O{\left(\frac{1}{d}\cdot\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}\right)}.$

Combined with Lemma 4.10 on the matrix norm, and the assumption of $B$ in
Theorem 1.1, we have $1/d\,\|\boldsymbol{A}^{-1}\|_{\infty}\in
O\big{(}\frac{1}{d}\,\big{(}\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\big{)}^{2}\big{)}$,
which proves our claim.

###### Proof of Lemma G.1.

Let $\vec{h},\vec{h}^{\prime}\in[{0}\,.\,.\,{n}]^{d}$ be two neighboring
histograms that differ in just one coordinate by at most $1$, i.e.,
$\left\|{\vec{h}-\vec{h}^{\prime}}\right\|_{1}\leq 1$. For every possible
realization $c_{A}$ of $C_{A}$, the histograms
$\tilde{h}=F_{A}{\left(\vec{h},c_{A}\right)},\tilde{h}^{\prime}=F_{A}{\left(\vec{h}^{\prime},c_{A}\right)}$
published by discrete Laplace mechanism also differ in just one coordinate by
at most $1$, i.e.,

$\left\|{F_{A}{\left(\vec{h},c_{A}\right)}-F_{A}{\left(\vec{h}^{\prime},c_{A}\right)}}\right\|_{1}=\left\|{\vec{h}-\vec{h}^{\prime}}\right\|_{1}\leq
1.$

Let $\tilde{f}$ and $\tilde{f}^{\prime}$ be the profiles that corresponds to
$\tilde{h}$ and $\tilde{h}^{\prime}$, respectively. Then $\tilde{f}$ and
$\tilde{f}^{\prime}$ differ in at most two coordinates, each by at most $1/d$.
Applying $\mathcal{A}_{\textit{fst-inv}}$ (Algorithm 2) to $\tilde{f}$ and
$\tilde{f}^{\prime}$ the amplify their distance by:

$\displaystyle\left\|{\mathcal{A}_{\textit{fst-
inv}}(\tilde{f})-\mathcal{A}_{\textit{fst-
inv}}(\tilde{f}^{\prime})}\right\|_{\infty}$
$\displaystyle=\left\|{\boldsymbol{A}^{-1}\times{\left(\tilde{f}-\tilde{f}^{\prime}\right)}-\frac{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times{\left(\tilde{f}-\tilde{f}^{\prime}\right)}\right\rangle}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}\cdot\boldsymbol{A}^{-1}\times\vec{a}}\right\|_{\infty}$
$\displaystyle\leq\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}\cdot{\left(\left\|{\tilde{f}-\tilde{f}^{\prime}}\right\|_{\infty}+\left|{\frac{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times{\left(\tilde{f}-\tilde{f}^{\prime}\right)}\right\rangle}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}}\right|\cdot\left\|{\vec{a}}\right\|_{\infty}\right)}$
$\displaystyle\leq\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}\cdot{\left(\left\|{\tilde{f}-\tilde{f}^{\prime}}\right\|_{\infty}+\left|{\frac{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times{\left(\tilde{f}-\tilde{f}^{\prime}\right)}\right\rangle}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}}\right|\right)},$

where the last inequality follows since
$\left\|{\vec{a}}\right\|_{\infty}\leq\left\|{\vec{a}}\right\|_{p}=1$ for
$p=1,2,\infty$. We claim that

$\displaystyle\left|{\frac{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times{\left(\tilde{f}-\tilde{f}^{\prime}\right)}\right\rangle}{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}}\right|\leq\frac{2}{d}.$

Since $\tilde{f}-\tilde{f}^{\prime}$ is a vector of at most two non-zero
coordinates, each bounded by $1/d$,

$\displaystyle\left|{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times{\left(\tilde{f}-\tilde{f}^{\prime}\right)}\right\rangle}\right|$
$\displaystyle=\frac{1}{d}\cdot\max_{t,t^{\prime}}\left|{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}[\cdot,t]\right\rangle+\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}[\cdot,t^{\prime}]\right\rangle}\right|$
$\displaystyle\leq\frac{2}{d}\cdot\max_{t}\left|{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}[\cdot,t]\right\rangle}\right|.$

On the other hand, since it holds for the standard basis vectors that
$\left\|{\vec{e}_{t}}\right\|_{p}=1$,

$\displaystyle\left|{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{a}\right\rangle}\right|$
$\displaystyle\geq\max_{t}\left|{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{e}_{t}\right\rangle}\right|=\max_{t}\left|{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}[\cdot,t]\right\rangle}\right|.$

It remains to verify that
$\max_{t}\left|{\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}[\cdot,t]\right\rangle}\right|\neq
0$. This is true, as

$\displaystyle\left\langle\vec{\mathbbm{1}}_{{0:n}},\sum_{t}\boldsymbol{A}^{-1}[\cdot,t]\right\rangle$
$\displaystyle=\left\langle\vec{\mathbbm{1}}_{{0:n}},\boldsymbol{A}^{-1}\times\vec{\mathbbm{1}}\right\rangle=\left\langle\vec{\mathbbm{1}}_{{0:n}},\vec{\mathbbm{1}}\right\rangle=n+1,$

where the equation
$\boldsymbol{A}^{-1}\times\vec{\mathbbm{1}}=\vec{\mathbbm{1}}$ holds since
$\boldsymbol{A}\times\vec{\mathbbm{1}}=\vec{\mathbbm{1}}$.

Combined, we have

$\displaystyle\left\|{\mathcal{A}_{\textit{fst-
inv}}(\tilde{f})-\mathcal{A}_{\textit{fst-
inv}}(\tilde{f}^{\prime})}\right\|_{\infty}$ $\displaystyle\in
O{\left(\frac{1}{d}\cdot\left\|{\boldsymbol{A}^{-1}}\right\|_{\infty}\right)}.$

To ease the notation, from now on, denote $\vec{r}=\mathcal{A}_{\textit{fst-
inv}}(\tilde{f})$ and $\vec{r}\,^{\prime}\doteq\mathcal{A}_{\textit{fst-
inv}}(\tilde{f}\,^{\prime})$. We will finally show that, Applying
$\mathcal{A}_{\textit{rnd}}$ (Algorithm 3) to $\vec{r}$ and
$\vec{r}\,^{\prime}$ the amplify their $\ell_{\infty}$ distance only by some
constant:

$\displaystyle\left\|{\mathcal{A}_{\textit{rnd}}{\left(\vec{r}\right)}-\mathcal{A}_{\textit{rnd}}{\left(\vec{r}\,^{\prime}\right)}}\right\|_{\infty}$
$\displaystyle\in
O{\left(\left\|{\vec{r}-\vec{r}\,^{\prime}}\right\|_{\infty}\right)}.$

We investigate the steps of Algorithm 3. First, rounding the coordinates of
$\vec{r}$ and $\vec{r}\,^{\prime}$ to the interval $[0,1]$ only decreases
their $\ell_{\infty}$ distance.

Next, the algorithm searches for some thresholds $\tau$ and $\tau^{\prime}$,
such that

$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}{\left(\vec{r}[t]-\min\left\\{{\tau,\vec{r}[t]}\right\\}\right)}$
$\displaystyle=1,$
$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}{\left(\vec{r}\,^{\prime}[t]-\min\left\\{{\tau^{\prime},\vec{r}\,^{\prime}[t]}\right\\}\right)}$
$\displaystyle=1.$

We claim that
$\tau\,^{\prime}\leq\tau+\left\|{\vec{r}-\vec{r}\,^{\prime}}\right\|_{\infty}$,
as

$\displaystyle\sum_{t\in[{0}\,.\,.\,{n}]}{\left(\vec{r}\,^{\prime}[t]-\min\left\\{{\tau+\left\|{\vec{r}-\vec{r}\,^{\prime}}\right\|_{\infty},\vec{r}\,^{\prime}[t]}\right\\}\right)}\leq\sum_{t\in[{0}\,.\,.\,{n}]}{\left(\vec{r}[t]-\min\left\\{{\tau,\vec{r}[t]}\right\\}\right)}=1.$

Via symmetry, we can prove that
$\tau\leq\tau^{\prime}+\left\|{\vec{r}-\vec{r}\,^{\prime}}\right\|_{\infty}$.
As Algorithm 3 eventually update each $\vec{r}[t]$ and $\vec{r}^{\prime}[t]$
by

$\displaystyle\vec{r}[t]\leftarrow\vec{r}[t]-\min\left\\{{\tau,\vec{r}[t]}\right\\},\quad\vec{r}\,^{\prime}[t]\leftarrow\vec{r}\,^{\prime}[t]-\min\left\\{{\tau^{\prime},\vec{r}\,^{\prime}[t]}\right\\},$

after the update, it still holds that
$\left|{\vec{r}[t]-\vec{r}\,^{\prime}[t]}\right|\in
O(\left\|{\vec{r}-\vec{r}\,^{\prime}}\right\|_{\infty})$, which finishes the
proof. ∎

###### Proof of Theorem 1.2.

We will prove the theorem by contraction. Assume there exists $\varepsilon$-DP
and updatable algorithm
$\mathcal{A}:[{0}\,.\,.\,{n}]^{d}\rightarrow\mathcal{Y}$, profile estimation
algorithm $\mathcal{R}:\mathcal{Y}\rightarrow[0,1]^{n+1}$, such that, for
every input $\vec{h}\in[{0}\,.\,.\,{n}]^{d}$, s.t.

$\mathbb{E}[\|\vec{f}-\mathcal{R}{({\mathcal{A}(\vec{h})})}\|_{\infty}]\in
o{\big{(}{{1}/{({\sqrt{d}\cdot e^{c\cdot\varepsilon}})}}\big{)}}.$

We will construct an $\varepsilon$-DP protocol $P$ such that such that for
every $\vec{x}$ and $\vec{y}$, Bob’s output (denoted by $m_{B}$) satisfies

$\Pr\left[\left|{m_{B}-\left\langle\vec{x},\vec{y}\right\rangle}\right|\geq\mathcal{E}\textit{rr}\right]\in
o(1),$ (17)

where $\mathcal{E}\textit{rr}=\sqrt{d}/{({2\cdot c\cdot
e^{c\cdot\varepsilon}})}$, contradicting Fact 5.4.

The protocol is given by Algorithm 4. Alice initializes the computation by
sending $\mathcal{A}{({\vec{x}+\vec{\mathbbm{1}}})}$ to Bob. On receiving
$\mathcal{A}{({\vec{x}+\vec{\mathbbm{1}}})}$, Bob updates it with their own
data $\vec{y}+\vec{\mathbbm{1}}$ by running algorithm $\mathcal{U}$, and the
result is then passed to the profile estimation algorithm $\mathcal{R}$.
Observe that by the property of updatable algorithm,
$\mathcal{U}{({\mathcal{A}(\vec{x}+\vec{\mathbbm{1}}),\vec{y}+\vec{\mathbbm{1}})})}=\mathcal{A}(\vec{x}+\vec{\mathbbm{1}}+\vec{y}+\vec{\mathbbm{1}})$.
Hence,
$\mathcal{R}{\left(\mathcal{U}{({\mathcal{A}(\vec{x}+\vec{\mathbbm{1}}),\vec{y}+\vec{\mathbbm{1}})})}\right)}$
is essentially an estimate of the profile $\vec{f}$ of
$\vec{h}\doteq\vec{x}+\vec{\mathbbm{1}}+\vec{y}+\vec{\mathbbm{1}}$. Finally,
Bob publishes
$d\cdot{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}$.
where $\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\in\mathbb{R}$
is a random variable following the Laplace distribution whose probability
density function is given by
$p(z)=\frac{\varepsilon}{2}\cdot\exp{\left(-\varepsilon\cdot\left|{z}\right|\right)},$
for all $z\in\mathbb{R}.$

It remains to analyze the privacy and utility guarantee of $P$ respectively.

Privacy Guarantee. The view of Bob is
$\mathcal{A}(\vec{x}+\vec{\mathbbm{1}})$, which is $\varepsilon$-DP by the
assumptions of $\mathcal{A}$. The view of Alice is
$d\cdot{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}$.
To prove this is $\varepsilon$-DP, it suffices to show that
$\vec{r}[4]+\vec{r}[0]-\vec{r}[2]$ has sensitivity
$\Delta_{\mathcal{R}\circ\mathcal{A}}$.

Assume the randomness $C_{A}$ of $\mathcal{A}$ has realization $c_{A}$. The
message $\mathcal{A}(\vec{x}+\vec{\mathbbm{1}})$ received by Bob therefore can
be written as $F_{A}(\vec{x}+\vec{\mathbbm{1}},c_{A}).$ After performing the
update
$\mathcal{U}{({\mathcal{A}(\vec{x}+\vec{\mathbbm{1}}),\vec{y}+\vec{\mathbbm{1}})})}=\mathcal{A}(\vec{x}+\vec{\mathbbm{1}}+\vec{y}+\vec{\mathbbm{1}})$,
the message becomes
$F_{A}(\vec{x}+\vec{\mathbbm{1}}+\vec{y}+\vec{\mathbbm{1}},c_{A})$. Suppose
that $\vec{y}$ is replaced by a neighbor binary vector $\vec{y}\,^{\prime}$
such that $\left\|{\vec{y}-\vec{y}\,^{\prime}}\right\|_{1}\leq 1$. Then
$\left\|{\vec{x}+\vec{\mathbbm{1}}+\vec{y}+\vec{\mathbbm{1}}-(\vec{x}+\vec{\mathbbm{1}}+\vec{y}+\vec{\mathbbm{1}}\,^{\prime})}\right\|_{1}\leq
1$, and via the definition of $\Delta_{\mathcal{R}\circ\mathcal{A}}$, we have
$\left\|{\mathcal{R}{\left(F_{A}(\vec{x}+\vec{\mathbbm{1}}+\vec{y}+\vec{\mathbbm{1}},c_{A})\right)}-\mathcal{R}{\left(F_{A}(\vec{x}+\vec{\mathbbm{1}}+\vec{y}^{\prime}+\vec{\mathbbm{1}},c_{A})\right)}}\right\|_{\infty}\leq\Delta_{\mathcal{R}\circ\mathcal{A}}$.

Accuracy Guarantee. Since $\vec{x}$ and $\vec{y}$ are binary vectors,
$\left\langle\vec{x},\vec{y}\right\rangle=\left|{\left\\{{\ell\in[d]:{({\vec{x}+\vec{y}})}[\ell]=2}\right\\}}\right|=d\cdot\vec{f}[2]$.
Therefore

$\displaystyle\left|{d\cdot{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}-d\cdot{\left(\vec{f}[2]+\vec{f}[0]-\vec{f}[2]\right)}}\right|$
(18) $\displaystyle\leq
d\cdot{\left(\left|{\vec{r}[4]-\vec{f}[4]}\right|+\left|{\vec{r}[2]-\vec{f}[2]}\right|+\left|{\vec{r}[0]-\vec{f}[0]}\right|+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\left|{\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)}\right|\right)}.$
(19)

Since
$\operatorname*{\mathbb{E}}\left[\left|{\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)}\right|\right]\in
O(1/\varepsilon)$, and by assumption,
$\operatorname*{\mathbb{E}}\left[\left\|{\vec{r}-\vec{f}}\right\|_{\infty}\right]\in
o{\left(\frac{1}{\sqrt{d}}\cdot\frac{1}{e^{c\cdot\varepsilon}}\right)},$ and
$\Delta_{\mathcal{R}\circ\mathcal{A}}\in
o{\left(\frac{1}{\sqrt{d}}\cdot\frac{\varepsilon}{e^{c\cdot\varepsilon}}\right)},$
it concludes that

$\operatorname*{\mathbb{E}}\left[\left|{d\cdot{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}-d\cdot{\left(\vec{f}[2]+\vec{f}[0]-\vec{f}[2]\right)}}\right|\right]\in
o{\left(\frac{\sqrt{d}}{e^{c\cdot\varepsilon}}\right)}.$

Combing
$d\cdot{({\vec{f}[4]+\vec{f}[0]-\vec{f}[2]})}=\left\langle\vec{x},\vec{y}\right\rangle$
with Markov inequality, we see

$\displaystyle\Pr\left[\left|{d\cdot{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}-\left\langle\vec{x},\vec{y}\right\rangle}\right|\geq\frac{2\cdot
c_{1}\cdot\sqrt{d}}{e^{c\cdot\varepsilon}}\right]$ (20)
$\displaystyle\leq{\operatorname*{\mathbb{E}}\left[\left|{d\cdot{\left(\vec{r}[4]+\vec{r}[0]-\vec{r}[2]+3\cdot\Delta_{\mathcal{R}\circ\mathcal{A}}\cdot\operatorname{\mathbb{L}ap}\left({1/\varepsilon}\right)\right)}-\left\langle\vec{x},\vec{y}\right\rangle}\right|\right]}\Bigg{/}{{\left(\frac{\sqrt{d}}{2\cdot
c\cdot e^{c\cdot\varepsilon}}\right)}}$ (21) $\displaystyle\in
o{\left(\frac{\sqrt{d}}{e^{c\cdot\varepsilon}}\middle/{\left(\frac{\sqrt{d}}{2\cdot
c\cdot e^{c\cdot\varepsilon}}\right)}\right)}$ (22) $\displaystyle=o(1).$ (23)

∎