# Knowledge Gain as Privacy Loss in Local Privacy Accounting

Mingen Pan  Independent Researcher
Email<EMAIL_ADDRESS>
###### Abstract

This paper establishes the equivalence between Local Differential Privacy
(LDP) and a global limit on learning any knowledge about an object. However,
an output from an LDP query is not necessarily required to provide exact
amount of knowledge equal to the upper bound of the learning limit. Since the
amount of knowledge gain should be proportional to the incurred privacy loss,
the traditional approach of using DP guarantee to measure privacy loss can
occasionally overestimate the actual privacy loss. This is especially
problematic in privacy accounting in LDP, where privacy loss is computed by
accumulating the DP guarantees. To address this issue, this paper introduces
the concept of realized privacy loss, which measures the actual knowledge
gained by the analyst after a query, as a more accurate measure of privacy
loss.

The realized privacy loss is then integrated into the privacy accounting of
fully adaptive composition, where an adversary adaptively selects queries
based on previous results. The Bayesian Privacy Filter is implemented to
continually accept queries until the realized privacy loss of the composed
queries equals the DP guarantee of the composition, allowing the full
utilization of the privacy budget of an object. Tracking the realized privacy
loss during the composition is achieved through a Bayesian Privacy Odometer,
and the gap between the privacy budget and the realized privacy loss measures
the leeway of the DP guarantee for future queries. Additionally, a branch-and-
bound method is devised to enable the Bayesian Privacy Filter to safeguard
objects with continuous values. The Bayesian Privacy Filter is proven to be at
least as efficient as the basic composition, and more efficient if the queries
are privacy-loss compactible. Experimental results indicate that Bayesian
Privacy Filter outperforms the basic composition by a factor of one to four
when composing linear and logistic regressions.

##  1 Introduction

Artificial intelligence has experienced a recent surge in development, largely
driven by training models using vast amounts of data collected everywhere,
including from individuals. Naturally, this raises concerns about privacy when
personal data are utilized in AI models [1]. To address these concerns,
Differential Privacy (DP), firstly proposed by [2], is proved to be able to
protect individual privacy during model training [1, 3]. DP ensures that, when
a database is queried, the participation of an entry in the database point
does not significantly alter the probability of any output. The original form
of DP, also known as Centralized Differential Privacy (CDP), operates under
the assumption that a trusted curator is responsible for aggregating data and
ensuring that the output adheres to the DP guarantee. However, centralized
data processing presents two significant problems: (1) users have to trust a
curator, and (2) there are various potential vulnerabilities that may
compromise user data, from eavesdropping on data transmission to hacking the
curator’s database [4].

To address these concerns, Local Differential Privacy (LDP) has been
introduced by [5], whereby any data inputted into a query yields a similar
output distribution. LDP is often achieved by directly perturbing the input.
LDP offers the advantage of conducting queries locally on an individual’s
device, with only the perturbed result being transmitted. Theoretically, no
third parties are able to acquire the original value of a user’s data. As a
result, tech giants, including Google [6], Apple [7], and Microsoft [8], have
embraced LDP as an integral part of their data processing protocols.

###  1.1 Motivation

Although it is unlikely for an adversary to derive the true value of queried
objects from the result of an LDP query using Bayesian inference, the
definition of LDP does not explicitly guarantee the extent to which an
adversary could learn or infer about an object. For instance, an LDP query may
inquire about a person’s age, and while it is improbable for an adversary to
deduce the age from the query, can we also ensure that the adversary is
unlikely to learn anything about whether the person has a certain disease? To
address this gap, this paper introduces learning limits for gaining knowledge
about statements. Informally, a learning limit prevents the posterior belief
of an adversary about a statement from changing too much compared to the prior
belief after a query. Subsequently, this paper demonstrates that LDP is
equivalent to providing a global learning limit for all statements, and vice
versa.

However, while LDP provides a learning limit, it does not necessarily mean
that an adversary can always gain knowledge exactly as the limit from every
output of an LDP query. Consider the following example:

######  Example 1.

Suppose we have a binary object $X$ with value $x\in\\{0,1\\}$, and a
randomized response $q$, with the following likelihood function.

$Pr(y|x)=\begin{cases}p,\text{ if }y=x,\\\ 1-p,\text{ otherwise}.\end{cases}$
(1)

$q$ is run $k$ times against $X$. The results of the queries are a sequence of
ones followed by a sequence of zeros, with equal frequencies, i.e.,
$[1,1,1,...,1,0,0,0,...,0]$.

The randomized response $q$ is $\log\frac{p}{1-p}$-LDP [9]. This paper mainly
focuses on pure DP (i.e., $\epsilon$-DP, formally defined in Section 2.3).
Notably, $(\epsilon,\delta)$-DP is equivalent to maintaining $\epsilon$-DP
with a probability of $1-\delta$ [10], so the artifact in this paper can be
extended to $(\epsilon,\delta)$-DP (see Section 4.3). In the tech industry, it
is common to adopt $\epsilon$-DP to measure the privacy budget for data
queried by LDP mechanisms. For example, Apple sets $\epsilon\in\\{4,8\\}$
[11], Microsoft sets $\epsilon=1.672$ [8], and Apple and Google set
$\epsilon=8$ for the local mechanism of a shuffle model [12]. As for pure DP,
existing research [13, 14, 15] has only explored using the basic composition
[16] for privacy accounting, which computes the DP guarantee of a sequence of
queries by summing the DP guarantee of each individual query. Therefore, the
process described above corresponds to $k\log\frac{p}{1-p}$-LDP. Researchers
often equate the DP guarantee and privacy loss, implying that the object is
expected to lose some privacy due to the process above. Intuitively, if an
object loses privacy, an adversary should be able to learn something about the
object. However, if the adversary is a Bayesian believer, they actually learn
nothing, as their posterior belief about the object remains the same as their
prior belief. In this case, even though the object is queried, the adversary
gains no knowledge. This raises the question: can we still say that the object
has lost privacy if the adversary does not learn anything? Simply using the DP
guarantee to represent privacy loss could overestimate the actual privacy
loss.

This paper proposes a different perspective, considering knowledge gain as
privacy loss. Informally, knowledge gain is the difference between the
posterior and prior beliefs of an adversary regarding a statement about an
object. The amount of knowledge gain is used in this paper to measure privacy
loss. Prior research (e.g., [17, 18]) has explored a similar methodology to
define privacy loss as gaining knowledge about the identity of an object.
However, this paper stands as the first to consider any knowledge gained as
privacy loss. In addition, to distinguish from the traditional representation
of privacy loss, the privacy loss measured by knowledge gain is also called
realized privacy loss, while the DP guarantee is considered as the worst-case
privacy loss. With this new metric for quantifying privacy loss, the author
further defines privacy-budget utilization as the ability of a query to
realize the privacy loss of an object. A query fully utilizes its privacy
budget if and only if every output of the query could realize the privacy loss
exactly as the DP guarantee. The composition of queries is equivalent to a
complex DP query, so the privacy-budget utilization is also applicable to the
composition. In Example 1, the basic composition does not fully utilize its
privacy budget, prompting this paper to seek an efficient privacy-accounting
algorithm for composition that maximizes privacy-budget utilization.

###  1.2 Result

This paper focuses on the most flexible form of interaction between an analyst
(adversary) and an object, where an analyst adaptively determines the next
query based on the results of previous queries. This type of interaction was
initially discussed by [14] within the context of CDP, referred to as pay-as-
you-go or fully adaptive composition. Due to its flexibility, the fully
adaptive composition has found application in various scenarios [3, 19, 20].
[14] proposed a privacy accounting framework for fully adaptive composition,
consisting of two components: (1) a privacy filter that ensures the
composition satisfies the DP guarantee, and (2) a privacy odometer that
monitors the privacy loss of the executed queries. Subsequent works [21, 22,
23] have aimed at enhancing the performance of the privacy filter and
odometer. In this paper, these concepts are extended to the framework of LDP.
For the privacy filter, the DP guarantee of the composition is translated into
the requirement that the realized privacy loss does not exceed the DP
guarantee. Moreover, a privacy filter is also expected to accept as many
queries as possible for higher efficiency and better privacy-budget
utilization. Therefore, this paper introduces the Bayesian Privacy Filter,
which accepts a new query as long as every potential output from the query
still guarantees that the realized privacy loss will not exceed the DP
guarantee. A simplified version of the Bayesian Privacy Filter is also
introduced, sharing a similar methodology but with reduced computational
complexity. Furthermore, an $(\epsilon,\delta)$-DP version of Bayesian Privacy
Filter is also extended from its $\epsilon$-DP version. Additionally, this
paper proposes a corresponding privacy odometer - Bayesian Privacy Odometer -
equating the realized privacy loss to the usage of the privacy budget.
Importantly, the gap between the realized privacy loss and the privacy budget
gauges the leeway of the DP guarantee for future queries. For instance, if the
gap is one, then the Bayesian Privacy Filter can always accept an LDP query
with $\epsilon\leq 1$, or potentially even a higher $\epsilon$.

The Bayesian Privacy Filter and Odometer require the realized privacy loss of
the executed queries, whose computation can be challenging for an object with
a domain of continuous values. This paper suggests a novel approach by
translating the computation of realized privacy loss into a form of Difference
of Convex (DC) Programming [24]. It further outlines the translating process
for linear regression, truncated linear regression, and logistic regression.
Additionally, a dedicated branch-and-bound method is introduced specifically
for computing the realized privacy loss associated with the aforementioned
regressions.

Subsequently, this paper proceeds to evaluate the efficiency of adaptive
compositions managed by a Bayesian Privacy Filter, referred to as Bayesian
composition. First, the paper proves that if the Bayesian composition accepts
at least a pair of privacy-loss compactible queries (Definition 6.2), then the
efficiency of the composition is expected to be better than the basic
composition. Also, the paper proves that if all the queries in the composition
are privacy-loss independent (Definition 6.4), the Bayesian composition is as
efficient as the basic composition. Next, a sequence of experiments are
conducted to measure the efficiency of the Bayesian composition. This involves
sending a stream of queries to the privacy filter until it initiates
rejection. The first experiment involves composing identical randomized
responses, revealing that if the basic composition can accept $k$ randomized
responses, Bayesian composition can accept $k^{2}$ queries under the same
conditions. Similar experiments are conducted for linear and logistic
regressions with random parameters, demonstrating that Bayesian composition is
four times more efficient for linear regressions and one time more efficient
for logistic regressions. Real-world query compositions are also evaluated,
with four regressions against healthcare data sent to a Bayesian Privacy
Filter. With a 50% chance, these queries consume less than 61% of the total
privacy budget.

Finally, this paper discusses the use case of Bayesian composition.
Acknowledging that Bayesian composition might incur computational expenses,
the paper advises its application only when deemed essential. An instance
where it proves beneficial is when composing queries against an object with
continuous value(s).

##  2 Background

###  2.1 Belief and Bayesian Inference

For an unknown object $X$, a person may have multiple candidates in mind
regarding its true identity. The confidence that $X$ turns out to be a
candidate $x$ is denoted as $Q(X=x|\theta)$, where $\theta$ represents
auxiliary information held by the person about $X$. $Q(X=x|\theta)$ falls with
the range of $[0,1]$, and the sum of confidence values for all candidates
equals unity, i.e. $\sum_{x\in\mathcal{X}}Q(X=x|\theta)=1$, where
$\mathcal{X}$ is the universe containing all the candidates. In this article,
we will use the notation $Q(x|\theta)$ instead of $Q(X=x|\theta)$ when there
is no ambiguity regarding the object we are referring to.

If the auxiliary information $\theta$ is empty, i.e., the person possesses no
knowledge about the unknown object $X$, then $Q(x|\emptyset)$ can assume
arbitrary values as long as they satisfy the aforementioned requirements.
However, a rational person would likely prefer an uninformative prior
distribution, e.g., a uniform distribution among all candidates

A Bayesian believer also updates their belief regarding an unknown object
after making an observation. This update follows Bayes’ theorem, which states:

$Pr(A|B)=\frac{Pr(B|A)Pr(A)}{Pr(B)},$ (2)

where $A$ and $B$ represent two events. The new belief (referred to as the
posterior belief) of a Bayesian believer after observing an event $y$ is
defined as:

$Q(x|\theta,y)=\frac{Pr(y|x)Q(x|\theta)}{\sum\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})Q(x^{\prime}|\theta)}.$
(3)

Eq. (3) bears the same form as Eq. (2) because
$\sum\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})Q(x^{\prime}|\theta)=Q(y|\theta)$,
which represents the person’s belief regarding the marginal probability of the
event $y$. In the subsequent article, we may omit $\theta$ in $Q(x|\theta,y)$
and $Q(x|\theta)$, thereby denoting them as $Q(x|y)$ and $Q(x)$, respectively,
when the auxiliary information before an observation is not the main focus of
interest. Furthermore, we will use $Q$ to represent the distribution of $Q(x)$
among all the candidates, reflecting a person’s prior belief regarding an
unknown object prior to making an observation.

###  2.2 Probabilistic Knowledge

Probabilistic knowledge, initially proposed by [25], has gained widespread
acceptance as a means of representing uncertainty and confidence regarding
statements (e.g., [26]). It has been found to have extensive application in
fields such as machine learning ([27, 28]). When the value of an object is
known, the correctness of a statement can be quantified using a probability
measure. For instance, when assessing the statement that a person has
diabetes, the probability of its correctness may be $\alpha\%$ given a person
with hyperglycemia, while it could be $\beta\%$ for a healthy person. A
certain event about an object has a probability of 1, while an impossible
event has a probability of 0. A correctness function $f$ is associated with
each statement to evaluate the probability of its correctness given an object,
i.e., $f:\mathcal{X}\rightarrow[0,1]$. The confidence (or belief) of a person
regarding the truth of a statement is defined to be

$Q(f)=\sum\limits_{x\in\mathcal{X}}f(x)Q(x),$ (4)

We will use a correctness function $f$ to denote the corresponding statement.
Analogous to the aforementioned posterior belief (Eq. (3)), the confidence
about a statement $f$ after an observation $y$ is given by

$Q(f|y)=\sum\limits_{x\in\mathcal{X}}f(x)Q(x|y)=\frac{\sum\limits_{x\in\mathcal{X}}Pr(y|x)f(x)Q(x)}{\sum\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})Q(x^{\prime})}.$
(5)

When a person observes an event, the person may be more confident or more
uncertain about a statement. Nevertheless, the person learns something new
about the statement, so we call the change of confidence as knowledge gain
about the statement, which is measured by $\frac{Q(f|y)}{Q(f)}$.

###  2.3 Local Differential Privacy (LDP)

To protect the true value of an object from being inferred by an adversary,
[5] has proposed Local Differential Privacy to ensure a query against an
object does not significantly disclose its actual value.

######  Definiton 2.1.

A query $M$ is $\epsilon$-LDP, if and only if, for any
$x,x^{\prime}\in\mathcal{X}$ and any $y$ generated by $M$,

$Pr(M(x)=y|x)\leq e^{\epsilon}Pr(M(x^{\prime})=y|x^{\prime}).$ (6)

This condition is equivalent to, for any $y$ generated by $M$,

$\max\limits_{x\in\mathcal{X}}Pr(M(x)=y|x)\leq
e^{\epsilon}\min\limits_{x\in\mathcal{X}}Pr(M(x)=y|x).$ (7)

While there are other variations of LDP, this paper focuses only on the most
common form mentioned above.

###  2.4 LDP of Continuous Value

Consider a query against an object $x$ yielding an output $y\in[a,b]$.
Depending on the purpose, various methods can be employed to enforce LDP for
$y$.

This paper specifically focuses on LDP enforcement for estimating the mean of
$y$ from a group of objects. The chosen approach is a well-established
perturbation algorithm, initially proposed by [29] and later refined by [30].
This algorithm discretizes and perturbs $y$, producing either $a$ or $b$ with
the following probabilities:

$Pr(b|y)=\frac{1}{b-a}\frac{e^{\epsilon}-1}{e^{\epsilon}+1}(y-a)+\frac{1}{e^{\epsilon}+1},$
(8)

and $Pr(a|y)=1-Pr(b|y)$. Intuitively, if $y=a$, the probability to output $b$
is $\frac{1}{e^{\epsilon}+1}$. As $y$ approaches $b$, its probability to
output $b$ increases linearly and eventually reaches
$\frac{e^{\epsilon}}{e^{\epsilon}+1}$. Clearly, this algorithm adheres to
$\epsilon$-LDP.

To estimate the mean of $y$ from a group of objects, the first step involves
computing the frequency of $b$ outputted by the perturbation algorithm,
denoted as $\pi_{b}$. Subsequently, the mean of $y$ can be approximated as:

$\bar{y}\approx a+b\frac{(e^{\epsilon}+1)\pi_{b}-1}{e^{\epsilon}-1}.$ (9)

##  3 Learning From LDP queries

LDP ensures that all objects have indistinguishable outputs. However, the
definition of LDP does not explicitly restrict how much an adversary can learn
from an object. In this section, we will introduce a metric to quantify the
amount of knowledge an adversary can acquire from a query and then demonstrate
how LDP effectively prevents significant knowledge gain by the adversary.

###  3.1 Learning Limit

Here, we will use $\frac{Q(f|y)}{Q(f)}$, the knowledge gain about a statement
$f$ after an event $y$, to define a learning limit that imposes a constraint
on the maximum amount of knowledge an adversary can acquire about an object.

######  Definiton 3.1.

A mechanism $M$ provides an $\epsilon$-learning limit for a statement $f$, if
and only if, for any output $y$ from $M$ and any prior belief $Q$, the
following inequality

$e^{-\epsilon}\leq\frac{Q(f|y)}{Q(f)}\leq e^{\epsilon}$ (10)

always holds true.

When querying against an individual object, all statements regarding the
object should be considered as privacy. For instance, in a survey, a
participant may provide only basic biometric information such as age, height,
and weight, without disclosing any medical history. However, a medical expert
may still be able to infer with high confidence whether a person has a certain
disease based on their biometric information. To prevent adversaries from
gaining too much new knowledge about an object, it is crucial for privacy-
preserving queries to maintain a reasonable learning limit for all statements.

###  3.2 Equivalence between LDP and Learning Limit

In this section, we will establish the equivalence between LDP and a global
learning limit for all statements.

######  Theorem 3.1.

If a query $M$ is $\epsilon$-LDP, then $M$ also provides an
$\epsilon$-learning limit for all statements.

Before proving this theorem, we need to establish the following lemma:

######  Lemma 3.1.

For any statement $f$, after a query $M$ returns a result $y$, the inequality

$\frac{\min\limits_{x\in\mathcal{X}}Pr(M(x)=y|x)}{\max\limits_{x^{\prime}\in\mathcal{X}}Pr(M(x^{\prime})=y|x^{\prime})}\leq\frac{Q(f|y)}{Q(f)}\\\
\leq\frac{\max\limits_{x\in\mathcal{X}}Pr(M(x)=y|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}Pr(M(x^{\prime})=y|x^{\prime})}$
(11)

holds true.

Proof: we will begin with the first inequality. Here, $Pr(M(x)=y|x)$ is
abbreviated as $Pr(y|x)$. For any statement $f$, after a query $M$ yielding a
result $y$, we have

$\frac{Q(f|y)}{Q(f)}=\frac{\sum\limits_{x\in\mathcal{X}}Pr(y|x)f(x)Q(x)}{\sum\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})Q(x^{\prime})\sum\limits_{x\in\mathcal{X}}f(x)Q(x)}.$
(12)

Given $\sum\limits_{x^{\prime}\in\mathcal{X}}Q(x^{\prime})=1$, we have
$\sum\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})Q(x^{\prime})\leq\max\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})$.
Additionally, we have $\sum\limits_{x\in\mathcal{X}}Pr(y|x)f(x)\allowbreak
Q(x)\geq\min\limits_{x\in\mathcal{X}}Pr(y|x)\sum\limits_{x\in\mathcal{X}}f(x)Q(x)$.
Thus,

$\eqref{eq:knowledge_bound_step_1}\geq\frac{\min\limits_{x\in\mathcal{X}}Pr(y|x)\sum\limits_{x\in\mathcal{X}}f(x)Q(x)}{\max\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})\sum\limits_{x\in\mathcal{X}}f(x)Q(x)}\geq\frac{\min\limits_{x\in\mathcal{X}}Pr(y|x)}{\max\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})}.$
(13)

The proof of the first inequality is complete. The second inequality can be
proven in a similar manner by scaling in the opposite direction, and the
details are omitted here. ∎.

Now we can prove Theorem 3.1. If $M$ is $\epsilon$-LDP, from Eq. 13, we obtain

$\eqref{eq:knowledge_bound_step_1}\geq\frac{\min\limits_{x\in\mathcal{X}}Pr(y|x)}{\max\limits_{x^{\prime}\in\mathcal{X}}Pr(y|x^{\prime})}\geq
e^{-\epsilon}.$ (14)

The above inequality is equivalent to the first inequality in the definition
of an $\epsilon$-learning limit (Definition 10). Similarly, we have Eq.
$\eqref{eq:knowledge_bound_step_1}\leq e^{\epsilon}$, which is equivalent to
the second inequality in the definition of $\epsilon$-learning limit. Thus,
$M$ provides an $\epsilon$-learning limit for all statements. ∎.

Now, we will prove the converse of Theorem 3.1:

######  Theorem 3.2.

If a query $M$ provides an $\epsilon$-learning limit for all statements, then
$M$ is $\epsilon$-LDP.

We will instead prove the following contrapositive of the theorem:

######  Proposition 3.1.

If a query $M$ is not $\epsilon$-LDP, there exists a statement $f$ for which
$M$ cannot provide an $\epsilon$-learning limit.

We also need the contrapositive of the definition of $\epsilon$-learning limit
(Definition 10):

######  Proposition 3.2.

A query $M$ cannot provide an $\epsilon$-learning bound for a statement $f$,
if and only if there exists an output $y$ from $M$ and a prior belief $Q$ such
that

$Q(f|M(\mathbf{x})=y)<e^{-\epsilon}Q(f)$ (15)

or

$Q(f|M(\mathbf{x})=y)>e^{\epsilon}Q(f).$ (16)

Before proving Theorem 3.2, we need another lemma as an intermediate step.
Recall the upper bound in Lemma 3.1. We will prove:

######  Lemma 3.2.

For any $\delta>0$, there exists a statement $f$, an output $y$ from a query
$M$, and a prior belief $Q$, the equation

$\frac{Q(f|y)}{Q(f)}\geq\frac{\max\limits_{x\in\mathcal{X}}Pr(M(x)=y|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}Pr(M(x^{\prime})=y|x^{\prime})}-\delta$
(17)

holds.

Proof: we only focus on
$\delta<\frac{\max\limits_{x\in\mathcal{X}}Pr(M(x)=y|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}Pr(M(x^{\prime})=y|x^{\prime})}$.
Otherwise, the proof is trivial. Define a statement $f$ satisfying $f(x)=1$
only if $x=\operatorname*{argmax}_{x\in\mathcal{X}}Pr(y|x)$; otherwise
$f(x)=0$. Also define a prior distribution $Q$ as follows:

$Q(x)=\begin{cases}p,\text{if
}x=\operatorname*{argmax}_{x\in\mathcal{X}}Pr(y|x)\\\ 1-p,\text{if
}x=\text{argmin}_{x\in\mathcal{X}}Pr(y|x)\\\ 0,\text{ otherwise.}\\\
\end{cases},$ (18)

where $p\leq\frac{\delta p_{min}^{2}}{(p_{max}-p_{min})(p_{max}-\delta
p_{min})}$, $p_{max}=\max_{x\in\mathcal{X}}Pr(y|x)$, and
$p_{min}=\min_{x\in\mathcal{X}}Pr(y|x)$. Substituting $Q$ and $f$ into Eq.
(17), we can see the inequality is satisfied. ∎

Now, we can continue to prove the contrapositive of Theorem 3.2. Suppose $M$
is not $\epsilon$-LDP, and we have

$\max\limits_{x\in\mathcal{X}}Pr(y|x)>e^{\epsilon}\min\limits_{x\in\mathcal{X}}Pr(y|x).$
(19)

Rewrite the above equation as
$\max\limits_{x\in\mathcal{X}}Pr(y|x)=e^{\epsilon}\min\limits_{x\in\mathcal{X}}Pr(y|x)+\theta$.
Set $\delta$ in Lemma 3.2 to be $\theta$, and we have

$\frac{Q(f|y)}{Q(f)}\geq
e^{\epsilon}+\frac{\theta}{\min\limits_{x\in\mathcal{X}}Pr(y|x)}-\theta.$ (20)

Notice that $\min\limits_{x\in\mathcal{X}}Pr(y|x)<1$. Otherwise,
$\max\limits_{x\in\mathcal{X}}Pr(y|x)$ will be larger than one. Therefore,
$\frac{\theta}{\min\limits_{x\in\mathcal{X}}Pr(y|x)}>\theta$, and we have

$\frac{Q(f|y)}{Q(f)}>e^{\epsilon}+\theta-\theta=e^{\epsilon}.$ (21)

which is equivalent to Eq. (16). The satisfaction of Eq. (16) concludes that
the query $M$ cannot provide an $\epsilon$-learning limit for a statement $f$.
Therefore, the contrapositive of Theorem 3.2 is proved, as is the theorem. ∎

###  3.3 What is Privacy Loss?

Theorem 3.1 states that every output of an $\epsilon$-DP query is allowed to
change the confidence of an adversary about any statement up to an
$\epsilon$-learning limit. However, being allowed does not necessarily imply
being able, and an LDP process sometimes may not even reveal privacy at all.
Recall Example 1 above; we compute the likelihood function for both values:

$Pr(q(1)=y|X=1)\\\ =Pr(q(0)=y|X=0)=p^{\frac{k}{2}}(1-P)^{\frac{k}{2}}.$ (22)

Based on Lemma 3.1, for any statement $f$, $\frac{Q(f|y)}{Q(f)}=1$. This
implies that an adversary does not gain any knowledge about the object, and we
must acknowledge that no privacy is compromised from the object. Therefore,
instead of simply using the DP guarantee of a query to represent privacy loss,
it is more appropriate to consider the measure of knowledge gain. Let us once
again recall Lemma 3.1. It states that for all statements, their knowledge
gain can be bounded by a pair of symmetric bounds. Furthermore, Lemma 3.2
demonstrates that these bounds are tight and can be approached by the
knowledge gain of at least one statement. Thus, the tight upper bound of
knowledge gain can be utilized to quantify the privacy loss:

######  Definiton 3.2.

Privacy loss $L(X|y)$ of an object $X$ after a query $M$ returns $y$ is
defined to be

$L(X|y)=\frac{\max\limits_{x\in\mathcal{X}}Pr(M(x)=y|X=x)}{\min\limits_{x^{\prime}\in\mathcal{X}}Pr(M(x^{\prime})=y|X=x^{\prime})}.$
(23)

In the subsequent article, $L(X|y)$ may be abbreviated as $L(y)$ if there is
no ambiguity about the queried object. $L(y)$ is also referred to as realized
privacy loss since it depends on the result of a query. Let’s recall the
definition of LDP, which implies that $\forall y,L(y)\leq\epsilon$. If
$\epsilon$ is a tight bound for the query, it indicates $\exists
y,L(y)=\epsilon$, representing the worst case of potential privacy loss from a
query. Thus, the DP guarantee provided by a query can be seen as the worst-
case privacy loss. If we aim to limit the privacy loss for a future query,
then the worst-case privacy loss is the metric to consider. However, when
examining the privacy loss of a composition, we must consider both the
realized privacy loss of the executed queries and the worst-case privacy loss
of future queries.

Previous research [17, 18] has explored a similar method to define privacy
within the context of Bayesian belief. However, these studies focused
exclusively on CDP and only considered the identity and existence of an object
as privacy concerns. However, ISO has published a standard for information
security, which defines personally identifiable information (i.e., privacy of
a person) as “any information that is directly or indirectly linked to a
person” [31]. Therefore, considering only the identity of an object as privacy
is insufficient. As discussed in Section 3.1, querying against an object is
more stringent, as any knowledge gained about any statements can be considered
as privacy loss. Our definition of privacy loss represents an upper bound on
learning any knowledge about an object, encompassing the personally
identifiable information defined by ISO. Additionally, though previous
research (e.g., [32, 14, 33]) has introduced the concept of privacy loss
random variable similar to Eq. (23), they only focused on expected or worst-
case privacy loss, which characterizes the privacy loss of future queries.
However, the realized privacy loss defined in this paper characterizes the
privacy loss of executed queries. Therefore, this paper represents the first
research to concentrate on the realized privacy loss.

With the notion of realized and worst-case privacy loss, we can define the
utilization of privacy budget as follows:

######  Definiton 3.3.

An $\epsilon$-DP query $M$ fully utilizes its privacy budget if and only if
$L(X|y)=\epsilon$ holds for every output $y$ from $M$.

That is, if a query fully utilizes its privacy budget, each of its outputs
will realize the same privacy loss as the worst-case privacy loss. It is
evident to see that Randomized Response [9], the fundamental algorithm in LDP,
fully utilizes its privacy budget, though the proof is omitted here. In
Example 1, it is apparent that the basic composition does not fully utilize
its privacy budget. Another example involves the LDP estimators of mean and
variance [34] of a group of continuous values (see Appendix A). Given the
above examples, this paper aims to find a more efficient privacy-accounting
algorithm for composition that guarantees that the realized privacy loss could
approach the DP guarantee as close as possible.

##  4 Privacy Accounting in Fully Adaptive Composition

Privacy accounting encompasses two main functions: (1) ensuring the DP
guarantee of a composition and (2) monitoring the privacy loss during the
composition. In this section, we will focus on fully adaptive composition,
where an adversary adaptively determines which query to execute based on the
previous queries and their results. Fully adaptive composition is regarded as
the most flexible form of adaptive composition, as it can represent any type
of interaction between an adversary and an object, as long as the queries are
executed sequentially. [14] introduced the concepts of privacy filter and
odometer to implement these two functions in the context of CDP. The privacy
filter ensures the DP guarantee of the composition, while the odometer
monitors the privacy loss of the executed queries. This paper extends these
concepts to the framework of LDP.

###  4.1 Privacy Filter

A privacy filter for LDP is a state machine that either accepts and rejects a
query against an entry, while ensuring the composition of all accepted queries
does not exceed its DP guarantee. The interaction between an adversary and an
object protected by a privacy filter appears as follows: the adversary
collects all previous queries and their results, and is allowed to dry run the
privacy filter to know if a query will be accepted. Considering all the
information above, the adversary will either choose a valid query against the
object or terminate the interaction. If a query is chosen, it will be verified
by the privacy filter, executed against the object, and return a result. The
adversary then repeats the aforementioned steps. Further details are presented
in Algorithm 1.

Algorithm 1 Interaction between an adversary and an entry (Fully Adaptive
Composition)

1:Adversary $\mathcal{A}$, Privacy Filter $F$, and object $X$

2:$i=1$

3:loop

4: $\mathcal{A}=\mathcal{A}(F,X,M_{1},y_{1},M_{2},y_{2},...,M_{i-1},y_{i-1})$
// $\mathcal{A}$ collects existing information

5: $\mathcal{A}$ gives either $M_{i}$ or HALT. // $M_{i}$ will always be
accepted by $F$ if given.

6: if $\mathcal{A}$ gives HALT then

7: break.

8: end if

9: Assert $F$ accepts $M_{i}$. Otherwise, continue.

10: $\mathcal{A}$ receives $y_{i}=M_{i}(x)$.

11: $i=i+1$

12:end loop

13:$(M_{1},y_{1},M_{2},y_{2},...,M_{i-1},y_{i-1})$

Now, we will formally define the DP guarantee of a privacy filter. The
interaction $q(F,\mathcal{A},X)$ between the adversary $\mathcal{A}$ and an
object $X$ protected by a privacy filter $F$ can be regarded as a mechanism
against an object (i.e., $M(\cdot)=q(F,\mathcal{A},\cdot)$). Therefore, we can
directly apply the definition of LDP to the interaction:

######  Definiton 4.1.

An interaction $q(F,\mathcal{A},\cdot)$ is $\epsilon$-LDP if and only if, for
any pair of object values $x$ and $x^{\prime}$, and any output
$V=(M_{1},y_{1},...,M_{n},y_{n})$ from the $q(F,\mathcal{A},\cdot)$, the
inequality

$Pr(q(F,\mathcal{A},x)=V|x)\leq
e^{\epsilon}Pr(q(F,\mathcal{A},x^{\prime})=V|x^{\prime})$ (24)

holds.

Consequently, the DP guarantee of a privacy filter can be defined as:

######  Definiton 4.2.

A privacy filter $F$ is $\epsilon_{g}$-DP if and only if $\forall\mathcal{A}$,
$q(F,\mathcal{A},\cdot)$ is $\epsilon_{g}$-DP.

Based on Algorithm 1, the choice of mechanism $M_{i}$ only depends on the
adversary $\mathcal{A}$, the privacy filter $F$, and previous mechanisms
$M_{<i}=\\{M_{j}|1\leq j<i\\}$ and their results $y_{<i}=\\{y_{j}|1\leq
j<i\\}$. Therefore, its conditional probability is represented as
$Pr(M_{i}|\mathcal{A},F,M_{<i},y_{<i})$. The result $y_{i}$ of mechanism
$M_{i}$ only depends on the queried object $X$. Suppose $X$ has a value of
$x$. The conditional probability of $y_{i}$ is represented as
$Pr(M_{i}(x)=y_{i}|x)$. Therefore,

$Pr(q(F,\mathcal{A},x)=V|x)=\\\ =\prod\limits_{1\leq i\leq
n}Pr(M_{i}|\mathcal{A},F,M_{<i},y_{<i})Pr(M_{i}(x)=y_{i}|x)\\\ \times
Pr(\text{HALT}|\mathcal{A},F,M_{\leq n},y_{\leq n}),$ (25)

where $V=(M_{\leq n},y_{\leq n})$ represents a valid output from
$q(F,\mathcal{A},x)$ and $n$ is the number of accepted queries in this output.
Since $Pr(M_{i}|\mathcal{A},F,M_{<i},y_{<i})$ and
$Pr(\text{HALT}|\mathcal{A},F,M_{\leq n},y_{\leq n})$ are independent of $x$,
substituting Eq. (25) into Eq. (24) yields

$\prod\limits_{1\leq i\leq n}Pr(M_{i}(x)=y_{i}|x)\\\ \leq
e^{\epsilon_{g}}\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x^{\prime})=y_{i}|x^{\prime}),$ (26)

which is equivalent to

$\frac{\max\limits_{x\in\mathcal{X}}\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x)=y_{i}|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}\prod\limits_{1\leq
i\leq n}Pr(M_{i}(x^{\prime})=y_{i}|x^{\prime})}\leq e^{\epsilon_{g}}.$ (27)

As a result, we just proved the following theorem:

######  Theorem 4.1.

A privacy filter $F$ is $\epsilon_{g}$-DP if and only if, for any adversary
$\mathcal{A}$ and any result $V=(M_{1},y_{1},...,M_{n},y_{n})$ from the
interaction $q(F,\mathcal{A},\cdot)$, Eq. (27) is satisfied.

It is observed that the left-hand side of the above inequality is actually the
realized privacy loss $L(y_{\leq n})$, indicating that the realized privacy
loss must not exceed the DP guarantee. A sufficient condition for a privacy
filter to maintain $\epsilon_{g}$-DP after accepting a query $M$ is that every
output of $M$ still satisfies Eq. (27). Thus, we have the following corollary:

######  Corollary 4.1.

If, for any $y$ from a query $M$,

$\frac{\max\limits_{x\in\mathcal{X}}\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x)=y_{i}|x)\times
Pr(M(x)=y|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x^{\prime})=y_{i}|x^{\prime})\times
Pr(M(x^{\prime})=y|x^{\prime})}\\\ \leq e^{\epsilon_{g}}$ (28)

holds true, where $M_{\leq n}$ are the accepted queries, then a privacy filter
accepting $M$ is still $\epsilon_{g}$-DP.

Therefore, we can design a privacy filter that continuously accepts queries as
long as Corollary 4.1 holds true for every query it receives. Such privacy
filter is called Bayesian Privacy Filter:

######  Definiton 4.3.

A Bayesian Privacy Filter is a privacy filter using Eq. (28) to accept or
reject a query (Algorithm 2).

Algorithm 2 Bayesian Privacy Filter

1:GLOBAL STATE: privacy budget $\epsilon_{g}$, Data Universe $\mathcal{X}$

2:GLOBAL STATE: map $P:\mathcal{X}\rightarrow\mathbb{R}$, where $\forall
x\in\mathcal{X}$, $P(x)=1$ when initialized.

3:query $M$

4:for $y\in Range(M)$ do

5: Set $P^{\prime}=P$.

6: $\forall x\in\mathcal{X},$ Set $P^{\prime}(x)=P^{\prime}(x)\times
Pr(M(x)=y|x)$.

7: $L=\max P^{\prime}(x)/\min P^{\prime}(x)$ // realized privacy loss

8: if $L>e^{\epsilon_{g}}$ then

9: return REJECT

10: end if

11:end for

12:Execute $M$, and receive the result $y$.

13:$\forall x\in\mathcal{X}$, Set $P(x)=P(x)\times Pr(M(x)=y|x)$.

14:return ACCEPT

The LDP guarantee has been proved in Corollary 4.1. This algorithm maintains a
map $P$, which records $\prod\limits_{1\leq i\leq n}Pr(M_{i}(x)=y_{i}|x)$ for
every $x$, accepted queries $M_{i}$, and their results $y_{i}$. For
convenience, $M_{i}$ and $y_{i}$ are ignored, and $\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x)=y_{i}|x)$ is denoted as $P(x)$, which will also be referred to
as a likelihood function. The purpose of the algorithm is to ensure
$\frac{\max_{x}P(x)}{\min_{x}P(x)}\leq e^{\epsilon_{g}}$.

The Bayesian Privacy Filter requires iteration over every potential output.
However, if the iteration becomes too complex, there exists a simplified
version:

######  Definiton 4.4.

A Simplified Bayesian Privacy Filter is a privacy filter that accepts a query
if and only if

$\log L(y_{\leq n})+\epsilon\leq\epsilon_{g},$ (29)

where $y_{\leq n}$ represents the accepted queries, and $\epsilon$ is the DP
guarantee of a pending query.

Further details are presented in Algorithm 3.

Algorithm 3 Simplified Bayesian Privacy Filter

1:GLOBAL STATE: privacy budget $\epsilon_{g}$, Data Universe $\mathcal{X}$

2:GLOBAL STATE: map $P:\mathcal{X}\rightarrow\mathbb{R}$, where $\forall
x\in\mathcal{X}$, $P(x)=1$ when initialized.

3:query $M$

4:Read the DP parameter $\epsilon$ of $M$.

5:$L=\max P(x)/\min P(x)$ // realized privacy loss

6:if $L\>e^{\epsilon}>e^{\epsilon_{g}}$ then

7: return REJECT

8:end if

9:Execute $M$, and receive the result $y$.

10:$\forall x\in\mathcal{X}$, Set $P(x)=P(x)\times Pr(M(x)=y|x)$.

11:return ACCEPT

######  Theorem 4.2.

A Simplified Bayesian Privacy Filter is $\epsilon_{g}$-DP.

Proof: since the examined query $M$ is $\epsilon$-DP, the inequality

$\frac{\max\limits_{x\in\mathcal{X}}\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x)=y_{i}|x)\times
Pr(M(x)=y|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x^{\prime})=y_{i}|x^{\prime})\times
Pr(M(x^{\prime})=y|x^{\prime})}\\\
\leq\frac{\max\limits_{x\in\mathcal{X}}\prod\limits_{1\leq i\leq
n}Pr(M_{i}(x)=y_{i}|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}\prod\limits_{1\leq
i\leq n}Pr(M_{i}(x^{\prime})=y_{i}|x^{\prime})}e^{\epsilon}$ (30)

holds true. The right-hand side of Eq. (30) corresponds to
$P_{max}e^{\epsilon}$ in Step 6 of Algorithm 3. Thus, the condition of Step 6
ensures

$\eqref{eq:simplified_filter_proof_step_1}\leq e^{\epsilon_{g}},$ (31)

which is equivalent to Corollary 4.1. ∎

###  4.2 Privacy Odometer

Bayesian Privacy Filter ensures the DP guarantee and limits how much an
adversary can learn from an object, but it does not monitor the privacy loss
during the interaction between an adversary and an object. However, as pointed
out by [14], the privacy loss of an object is undefined when a query (i.e.,
the interaction in this case) is executed halfway. This is because the
definition of LDP only depends on the final outputs of a mechanism. If we
consider “running an adaptive composition and stopping halfway” as a completed
mechanism, then we need to consider all possible outcomes of the mechanism
being stopped. If the composition is allowed to be stopped arbitrarily, there
will be a scenario (i.e., output) where the composition stops right before the
last accepted query. In this case, the output from this process is no
different from the original composition, so its DP guarantee will also be very
similar to that of the original composition. Therefore, we cannot rely on the
definition of LDP to quantify the privacy loss during the execution of a
mechanism. In addition, as discussed in Section 3.3, using the DP guarantee as
privacy loss may overestimate the knowledge an adversary can gain from an
object, and it is more reasonable to measure privacy loss with knowledge gain,
i.e., realized privacy loss. In this section, a privacy odometer is defined
based on the privacy loss $L(y)$:

######  Definiton 4.5.

Bayesian Privacy Odometer is a function mapping from the accepted queries
$(M_{1},y_{1},...,M_{j},y_{j})$ after step 10 of the interaction between an
adversary and an object (Algorithm 1) to

$\epsilon(y_{\leq j})=\log L(y_{\leq
j})=\log\frac{\max\limits_{x\in\mathcal{X}}\prod\limits_{1\leq i\leq
j}Pr(M_{i}(x)=y_{i}|x)}{\min\limits_{x^{\prime}\in\mathcal{X}}\prod\limits_{1\leq
i\leq j}Pr(M_{i}(x^{\prime})=y_{i}|x^{\prime})}.$ (32)

It is interesting to note that Eq. (32) corresponds to the left-hand side of
Eq. (27). Thus, $\epsilon(y_{\leq j})$ will never exceed $\epsilon_{g}$ if the
interaction is managed by a Bayesian Privacy Filter. When $\epsilon(y_{\leq
j})$ equals $\epsilon_{g}$, no new queries with privacy loss can be accepted
based on Eq. (28). Furthermore, if a Simplified Bayesian Privacy Filter is
used, only queries with a DP guarantee $\epsilon$ that does not exceed
$\epsilon_{g}-\epsilon(y_{\leq j})$ will be accepted. Therefore, the
$\epsilon(y_{\leq j})$ of the Bayesian Privacy Odometer measures how close the
interaction is to depleting the privacy budget and indicates the maximum DP
guarantee of the queries guaranteed for acceptance. Importantly, a Bayesian
Privacy Filter might accept a query with a DP guarantee above
$\epsilon_{g}-\epsilon(y_{\leq j})$ if the realized privacy loss consistently
increases by an amount less than $\epsilon_{g}-\epsilon(y_{\leq j})$ for all
outputs. An illustration of this scenario is provided in Appendix A, where the
realized privacy loss consistently remains smaller than the DP guarantee.

Another observation is that $\epsilon(y_{\leq j})$ could decrease. Recall
Example 1 mentioned above, where $\epsilon$-DP randomized responses are run
$k$ times against a binary-value entry. The first $\frac{k}{2}$ responses
return one, and the last $\frac{k}{2}$ responses return zero. In this case,
$\epsilon(y_{\leq j})$ will initially increase to $\frac{k}{2}\epsilon$ and
later decrease to zero.

###  4.3 Extend to Approximate Differential Privacy

Local Approximate Differential Privacy, denoted as $(\epsilon,\delta)$-LDP, is
defined as follows:

######  Definiton 4.6.

A query $M$ is $(\epsilon,\delta)$-LDP, if and only if, for any
$x,x^{\prime}\in\mathcal{X}$ and any subset $S$ of the outputs generated by
$M$,

$Pr(M(x)\in S|x)\leq e^{\epsilon}Pr(M(x^{\prime})\in S|x^{\prime})+\delta.$
(33)

This definition is equivalent to:

######  Definiton 4.7.

For any $x\in\mathcal{X}$ and with the probability of $1-\delta$, an output
$y$ generated by $M(x)$ satisfies the realized privacy loss
$L(y)<e^{\epsilon}$ [10].

Previous research has introduced a category of privacy filters designed to
enforce $(\epsilon,\delta)$-DP for fully adaptive composition [14, 23]. These
privacy filters either accept a query or halt the composition. When the
composition is halted, these filters guarantee, with the probability of
$1-\delta$, that the composition will have $L(\mathbf{y})\leq e^{\epsilon}$,
irrespective of the outputs $\mathbf{y}$ of the accepted queries.
Distinguished from Bayesian Privacy Filters, these privacy filters are termed
output-independent filters. Although derived for CDP, they are applicable to
LDP due to the equivalence of fully adaptive composition in both LDP and CDP.
An $(\epsilon_{g},\delta_{g})$-LDP output-independent filter can be enhanced
to an $(\epsilon_{g},\delta_{g})$-Bayesian Privacy Filter in the following
manner: consider the situation where an output-independent filter decides to
halt the composition. With the probability of $\delta_{g}$, $L(\mathbf{y})$
will exceed $e^{\epsilon_{g}}$. In this case, as the $\epsilon_{g}$-DP
guarantee has already been violated, and there is no further constraint for
$L(\mathbf{y})$, $L(\mathbf{y})$ can be infinitely large. Consequently, the
Bayesian Privacy Filter is permitted to continue accepting an infinite number
of arbitrary queries, even directly outputting the true value $x$, as allowed
under Definition 4.7. However, in good faith, the Bayesian Privacy Filter
chooses to terminate the composition to prevent further privacy leaks.
Conversely, with the probability of $1-\delta_{g}$, $L(\mathbf{y})$ remains
below $e^{\epsilon_{g}}$, and the Bayesian Privacy Filter is obligated to
sustain this. Thus, the filter can accept queries as long as the
$L(\mathbf{y})$ after acceptance does not surpass $\epsilon_{g}$. Detailed
implementation is provided in Algorithm 4.

Algorithm 4 Bayesian Privacy Filter for $(\epsilon_{g},\delta_{g})$-LDP

1:GLOBAL STATE: privacy budget $(\epsilon_{g},\delta_{g})$

2:GLOBAL STATE: output-independent $(\epsilon_{g},\delta_{g})$-DP Privacy
Filter $F_{0}$

3:GLOBAL STATE: $\epsilon_{g}$-DP Bayesian Privacy Filter $F_{B}$

4:GLOBAL STATE: the outputs of the currently accepted queries $\mathbf{y}$.

5:query $M$

6:if $F_{0}$ is not halted then

7: $F_{0}$ receives $M$ and outputs ACCEPT or HALT

8: if $F_{0}$ outputs ACCEPT then

9: Execute $M$ and add the output into $\mathbf{y}$

10: return ACCEPT

11: else

12: $F_{0}$ becomes halted.

13: end if

14:end if

15:if $L(\mathbf{y})>\epsilon_{g}$ then

16: return REJECT

17:end if

18:// $F_{B}$ can accept $M$ only if $L(\mathbf{y})\leq\epsilon_{g}$ given any
output from $M$.

19:if $F_{B}$ can accept $M$ then

20: $F_{B}$ accepts, executes $M$, and add the output into $\mathbf{y}$

21: return ACCEPT

22:end if

23:return REJECT

The above introduction of Algorithm 4 is self-explanatory; therefore, no
formal proof is provided here. Despite the derivation of the
$(\epsilon_{g},\delta_{g})$-Bayesian Privacy Filter, the subsequent sections
of the article will concentrate exclusively on the $\epsilon_{g}$-Bayesian
Privacy Filter.

##  5 Algorithms to Compute Realized Privacy Loss

The Bayesian Privacy Filter and Odometer calculate a realized privacy loss
(left hand side of Eq. (27)) after receiving a query. The initial
implementation (see Algorithm 2 and 3) relies on maintaining the likelihood
function $P(x)$ for every $x\in\mathcal{X}$ to compute the realized privacy
loss. However, updating $P(x)$ involves iterating over every $x$. In cases
where $|\mathcal{X}|$ is excessively large, such as when $\mathcal{X}$ is a
continuous value, computing $P(x)$ becomes impractical. In this section, we
will introduce a method to numerically compute the realized privacy loss for
an object with multi-dimensional continuous values without the need to
maintain $P(x)$ for every $x$.

###  5.1 Upper Bound of Realized Privacy Loss

Computing a realized privacy loss requires both maximum and minimum of the
likelihood function $P(x)$. While determining the exact extrema can be
computationally expensive, it’s often more feasible to calculate the lower
bound $\min_{x}P(x)$ and upper bound $\max_{x}P(x)$. Let $LB\leq\min_{x}P(x)$
and $\max_{x}P(x)\leq UB$. The realized privacy loss can then be expressed as:

$L(y)=\frac{\max\limits_{x}P(x)}{\max\limits_{x^{\prime}}P(x^{\prime})}\leq\frac{UB}{LB}.$
(34)

Bayesian Privacy Filter and Odometer may instead utilize the upper bound of
$L(y)$ for privacy accounting, and their privacy guarantee remains valid. The
subsequent section will introduce a method to determine $LB$ and $UB$ for
$P(x)$ using the technique of Difference of Convex Programming.

###  5.2 Difference of Convex Programming

Difference of Convex (DC) Programming [24] with box constraints addresses the
following problem:

$\begin{gathered}\min f(x)-g(x)\\\ \text{subject to }x_{i,lb}\leq x_{i}\leq
x_{i,ub},\;\;1\leq i\leq m\end{gathered}$ (35)

where $x\in\mathbb{R}^{m}$; $f(x)$ and $g(x)$ are convex functions. Despite
the objective being the minimization of $f(x)-g(x)$, the corresponding
maximization can be obtained by interchanging $f(x)$ and $g(x)$. The lower
bound of the global solution can be determined by relaxing $g(x)$ into an
affine (linear) function $h(x)$ under the conditions that (1) $g(x)\leq h(x)$
within a compact (closed and bounded) set of $x$, and (2) $h(x)\rightarrow
g(x)$ as the compact set of $x$ approaches infinitesimally small. This results
in a convex optimization problem, with $\min f(x)-h(x)$ serving as the lower
bound for $\min f(x)-g(x)$. The function $h(x)$ is referred to as the concave
envelope of $g(x)$. Utilizing the branch-and-bound method [35], the lower
bound of will converge gradually to the actual value of $\min f(x)-g(x)$,
i,e., $LB$ in Eq. (34). $UB$ can be acquired similarly with $\min g(x)-f(x)$.

Notably, $\log P(x)$ can be expressed as

$\log P(x)=\sum\limits_{1\leq i\leq n}\log P_{i}(x),$ (36)

where $P_{i}(x)=Pr(M_{i}(x)=y_{i}|x)$. If $\log P_{i}(x)$ can be expressed as
the difference of two convex functions, given that the sum of convex functions
is still convex, minimizing/maximizing $\log P(x)$ transforms into a DC
programming.

###  5.3 Translate Queries into Difference of Convex Functions

This section will introduce three types of LDP queries with likelihood
functions $P(x)$ that can be represented in the form of DC programming. This
assumes that their LDP is enforced using the perturbation algorithm outlined
in Section 2.4.

####  5.3.1 Linear Regression

Consider a vector $x$, and let $y$ be the result of a linear regression
against it, with the form $y=\theta x+c$, and $y\in[a,b]$ under the
constraints of $x$. By replacing $y$ in Eq. (8) with $\theta x+c$, the
conditional probability of an output given $x$ is:

$Pr(b|x)=\frac{1}{b-a}\frac{e^{\epsilon}-1}{e^{\epsilon}+1}(\theta
x+c-a)+\frac{1}{e^{\epsilon}+1},$ (37)

and $Pr(a|x)=1-Pr(b|x)$. It is evident that both $Pr(b|x)$ and $Pr(a|x)$ are
linear functions of $x$. For simplicity, we express the conditional
probability as:

$Pr(o|x)=\alpha x+\beta$ (38)

where $o$ is either $a$ or $b$, and $\alpha$ and $\beta$ represent the slope
and intercept of the linear relationship. The logarithmic form $\log Pr(o|x)$
is concave, allowing it to be incorporated into DC programming, where $\log
Pr(o|x)$ serves as a component of $-g(x)$.

####  5.3.2 Truncated Linear Regression

Similar to the linear regression, the value $y$ in truncated linear regression
is represented as:

$y=\min\\{b,\max\\{a,\theta x+c\\}\\}.$ (39)

After enforcing LDP, the conditional probability of an output is given by

$Pr(b|x)=\min\\{\frac{e^{\epsilon}}{e^{\epsilon}+1},\max\\{\frac{1}{e^{\epsilon}+1},\\\
\frac{1}{b-a}\frac{e^{\epsilon}-1}{e^{\epsilon}+1}(\theta
x+c-a)+\frac{1}{e^{\epsilon}+1}\\}\\},$ (40)

and $Pr(a|x)=1-Pr(b|x)$. For simplicity, the conditional probability is
rewritten as:

$Pr(o|x)=\min\\{\frac{e^{\epsilon}}{e^{\epsilon}+1},\max\\{\frac{1}{e^{\epsilon}+1},\alpha
x+\beta\\}\\}.$ (41)

$\log Pr(o|x)$ can be expressed as $f(x)-g(x)$, where:

$f(x)=\log(\frac{1}{e^{\epsilon}+1})-\log(\min\\{\frac{1}{e^{\epsilon}+1},\>\alpha
x+\beta\\}),$ (42)

and

$g(x)=-\log(\min\\{\frac{e^{\epsilon}}{e^{\epsilon}+1},\>\alpha x+\beta\\}).$
(43)

Both $f(x)$ and $g(x)$ are convex (proof is omitted), demonstrating that $\log
Pr(o|x)$ can be accommodated within DC programming.

####  5.3.3 Logistic Regression

Let $x$ be a vector, and denote $y$ as the result of logistic regression:

$y=\frac{e^{\theta x+c}}{e^{\theta x+c}+1}.$ (44)

If LDP is enforced for $y$ using the perturbation algorithm in Section 2.4,
then the algorithm will output either 0 or 1. Substituting the $y$ into Eq.
(8), the conditional probability of an output given $x$ becomes:

$Pr(1|x)=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}\frac{e^{\theta x+c}}{e^{\theta
x+c}+1}+\frac{1}{e^{\epsilon}+1}$ (45)

and $Pr(0|x)=1-Pr(1|x)$. For simplicity, the formula can be rewritten as:

$Pr(o|x)=\frac{\alpha e^{\theta x+c}+\beta}{e^{\theta x+c}+1},$ (46)

where $o$ is either 0 or 1, and $\alpha$ and $\beta$ are the parameters after
the refactor. Defining

$f(x)=\log(\alpha e^{\theta x+c}+\beta)$ (47)

and

$g(x)=\log(e^{\theta x+c}+1),$ (48)

we have $\log Pr(o|x)=f(x)-g(x)$. Given $f(x)$ and $g(x)$ are both convex
(because $\log(e^{x}+1)$ is convex and $\theta x+c$ is a linear
transformation), $\log Pr(o|x)$ can be incorporated into DC programming
accordingly.

###  5.4 Branch-and-bound for Realized Privacy Loss

This section will adapt the branch-and-bound method [35] to compute the
realized privacy loss given the executed results of the queries introduced in
Section 5.3. Assume a Bayesian Privacy Filter has accepted a sequence of the
aforementioned queries, each of which is denoted as $M_{i}$, and the
corresponding output is denoted as $y_{i}$. The likelihood function of each
query can be expressed as the difference of two convex functions: $\log
Pr(M_{i}(x)=y_{i}|x)=f_{i}(x)-g_{i}(x)$.

As outlined in Section 5.3, both $f_{i}(x)$ and $g_{i}(x)$ share the same form
as $F(h(x))$, where $F(y)$ is a convex function, $y$ is a scalar, and $h(x)$
is a linear transformation (i.e., $\theta x+c$). Given any range $[a,b]$ such
that $a\leq h(x)\leq b$, we have

$F(h(x))\leq\frac{F(b)-F(a)}{b-a}(h(x)-a)+F(a)$ (49)

because of the convexity of $F(y)$. The right hand side is denoted as $H(x)$.
Since $H(x)$ is a linear transformation of $h(x)$, it is also a linear
function of $x$. Notably, as $a\rightarrow b$, $F(h(x))\rightarrow H(x)$.
Consequently, $H(x)$ can act as a concave envelope of $F(h(x))$.

The log-likelihood function $\log P(x)$ of all accepted queries can be
represented as $\sum_{i}f_{i}(x)-g_{i}(x)$. Let $g(x)=\sum_{i}g_{i}(x)$, and
$H_{i}(x)$ to be the aforementioned concave envelope of $g_{i}(x)$. A concave
envelope of $g(x)$ can then be represented as $\sum_{i}H_{i}(x)$. When solving
$\min_{x}\log P(x)$, $f(x)-\sum_{i}H_{i}(x)$ remains convex and serves as the
lower bound of $\log P(x)$. This process is also applicable to maximizing
$\log P(x)$ because it is equivalent to minimizing $g(x)-f(x)$.

With the concave envelope $\sum_{i}H_{i}(x)$ in hand, the branch-and-bound
method [35] can be used to optimize the lower bound of $\log P(x)$. However,
searching in the space of $x$ may be slow in practice, prompting an upgrade to
the method. Recall that each $f_{i}(x)$ and $g_{i}(x)$ can be represented as
$F(h(x))$, and if we denote $y=h(x)$, an insightful heuristic emerges — the
change of $f_{i}(x)$ and $g_{i}(x)$ is more sensitive to $y$ than $x$.
Consequently, in the design of the branch-and-bound method, branching
(splitting) on the $y$ values of individual queries is favored over branching
on $x$. Let $\mathbf{Y}=\\{Y_{1},Y_{2},...,Y_{n}\\}$, where $Y_{i}$ is a
variable representing the output of $h_{i}(x)$. Given that $x$ is bounded,
each $Y_{i}$ possesses its own lower and upper bounds, forming a box
constraint denoted as $B_{0}^{\mathbf{Y}}$, where the constraint of one
dimension does not depend on another dimension. The algorithmic details are
presented in Algorithm 5.

Notably, the complexity of Algorithm 5 increases exponentially with the size
of $\mathbf{Y}$. Appendix B introduces a strategy to partition the accepted
queries into groups of constant size, potentially reducing the overall
complexity to linearity.

Algorithm 5 Branch and Bound for $\log P(x)=f(x)-g(x)$

1:$B^{x}$: box constraint of $x$

2:$B_{0}^{\mathbf{Y}}$: box constraint of $\mathbf{Y}$ (see Section 5.4).

3:function Branch And Bound($f,g,B^{x},B_{0}^{\mathbf{Y}},\delta=0.01$)

4: $\mathcal{Q}$: a priority queue storing $\\{LB,B^{\mathbf{Y}}\\}$ in
ascending order

5: $UB_{g}=0$ // global upper bound of $f(x)-g(x)$

6: Bound($B_{0}^{\mathbf{Y}}$)

7: while $\text{peek}(\mathcal{Q}).LB\geq UB_{g}-\delta$ do

8: $B^{\mathbf{Y}}$ = pop$(\mathcal{Q})$

9: $B_{L}^{\mathbf{Y}}$, $B_{R}^{\mathbf{Y}}$ =
Branch($B^{\mathbf{Y}},B_{0}^{\mathbf{Y}}$)

10: Bound($f,g,B^{x},B_{L}^{\mathbf{Y}},UB_{g},\mathcal{Q}$)

11: Bound($f,g,B^{x},B_{R}^{\mathbf{Y}},UB_{g},\mathcal{Q}$)

12: end while

13: return peek$(\mathcal{Q}).LB$

14:end function

15:

16:function Branch($B^{\mathbf{Y}}$, $B_{0}^{\mathbf{Y}}$)

17: $B_{max}$: longest_edge = None

18: $l_{max}$: longest_length = 0

19: // iterate each edge

20: for $B^{Y},B_{0}^{Y}$ in zip($B^{\mathbf{Y}},B_{0}^{\mathbf{Y}}$) do

21: $l$ = $B^{Y}$.length / $B_{0}^{Y}$.length

22: if $l_{max}<l$ then

23: $l_{max}=l$

24: $B_{max}=B^{Y}$

25: end if

26: end for

27: $B_{L}^{\mathbf{Y}},B_{R}^{\mathbf{Y}}$ = Split $B^{\mathbf{Y}}$ in half
by $B_{max}$

28: return $B_{L}^{\mathbf{Y}}$, $B_{R}^{\mathbf{Y}}$

29:end function

30:

31:function Bound($f,g,B^{x},B^{\mathbf{Y}},UB_{g},\mathcal{Q}$)

32: $UB$ = $\min_{x}f(x)-g(x)$ s.t. $B^{x},B^{\mathbf{Y}}$, using any LDC
algorithm.

33: $UB_{g}=\max\\{UB_{g},UB\\}$

34: Find $H(x)$ as the concave envelope of $g(x)$

35: $LB$ = $\min_{x}f(x)-H(x)$ s.t. $B^{x},B^{\mathbf{Y}}$.

36: Insert $\\{LB,B^{\mathbf{Y}}\\}$ into $\mathcal{Q}$

37:end function

##  6 Evaluation of Bayesian Privacy Filter

In this section, we will use the term Bayesian composition to represent the
interaction between an adversary and an object managed by a Bayesian Privacy
Filter, as compared to the basic composition. It is important to note that the
adversary is assumed to be rational and greedy. This implies that the
adversary in the Bayesian composition will not halt the composition if the
Bayesian Privacy Filter can still accept any queries the adversary likes to
send.

To begin, we define the efficiency of Bayesian composition and prove the
condition that leads to better efficiency than the basic composition. Next, we
delve into an efficiency experiment for Bayesian composition, wherein a
Bayesian Privacy Filter receives a stream of LDP queries until the filter
begins rejecting queries. The pseudocode is presented in Algorithm 6. Finally,
we will briefly discuss the use case of Bayesian composition.

Algorithm 6 Bayesian Composition Experiment

1:a stream of queries $\mathbf{q}$

2:an object $x$ protected by Bayesian Privacy Filter $F$

3:$O=[]$ // outputs

4:loop

5: next query $q$ from $\mathbf{q}$

6: $F$ receives $q$ and returns RESULT

7: if RESULT is REJECT then

8: return $O$

9: end if

10: $F$ executes $q$ with output $o$.

11: Append $(q,o)$ to $O$

12:end loop

###  6.1 Efficiency of Bayesian Composition

Let’s define the efficiency of a composition. Suppose a composition is halted
after accepting $n$ queries, where the $i$-th query $M_{i}$ is
$\epsilon_{i}$-DP. The composed queries $M_{\leq n}=\\{M_{i}|1\leq i\leq n\\}$
and their results $y_{\leq n}=\\{y_{i}\in Range(M_{i})|1\leq i\leq n\\}$ are
considered as the result of the composition. Meanwhile, the composition
guarantees $\epsilon_{g}$-DP. We have:

######  Definiton 6.1.

The efficiency of the result of a composition is defined to be

$K=\sum\limits_{i=1}^{n}\epsilon_{i}/\epsilon_{g}.$ (50)

The basic composition has $K=1$, while the Bayesian composition could achieve
a higher $K$, which will be proved below.

######  Lemma 6.1.

A Bayesian composition always has $K\geq 1$.

Proof: Reuse the notation $y_{\leq n}$ above. We have

$\exp(\sum\limits_{i=1}^{n}\epsilon_{i})=\prod\limits_{i=1}^{n}\frac{\max\limits_{x}Pr(y_{i}|x)}{\min\limits_{x}Pr(y_{i}|x)}\geq\frac{\max\limits_{x}\prod\limits_{i=1}^{n}Pr(y_{i}|x)}{\min\limits_{x}\prod\limits_{i=1}^{n}Pr(y_{i}|x)}\\\
=L(y_{\leq n}).$ (51)

Given the assumption of a greedy adversary, we will have $L(y_{\leq
n})=e^{\epsilon_{g}}$, so
$K=\sum\limits_{i=1}^{n}\epsilon_{i}/\epsilon_{g}\geq 1$. ∎

Now we will show the condition for a Bayesian composition to achieve $K>1$
with at least one potential result. Let $Y$ denote a random variable
representing the result of an $\epsilon_{Y}$-DP mechanism $M_{Y}$, and $Z$
represent the result of an $\epsilon_{Z}$-DP mechanism $M_{Z}$.

######  Definiton 6.2.

$M_{Y}$ and $M_{Z}$ are privacy-loss compactible if and only if $\exists y\in
Y,\exists z\in Z:L(y,z)<e^{\epsilon_{Y}+\epsilon_{Z}}$.

######  Theorem 6.1.

At least one result of a Bayesian composition can achieve $K>1$, if at least
two queries accepted by the Bayesian composition are privacy-loss compactible.

The proof is provided in Appendix C.1.

######  Corollary 6.1.

A Bayesian composition has $E[K]>1$, if at least two queries accepted by the
Bayesian composition are privacy-loss compactible.

Proof: This is easily inferred from the fact that all results have $K\geq 1$,
and at least one result has $K>1$. ∎

Now, we will show that a common use case of composition - running identical DP
queries against an object - is privacy-loss compactible:

######  Lemma 6.2.

Two identical queries are privacy-loss compactible if they have a non-zero DP
guarantee.

The proof is provided in Appendix C.2.

On the other hand, the Bayesian composition of some queries is always
equivalent to the basic composition. Let $M_{\leq n}$ be a set of $n$ queries,
where the $i$-th query is $M_{i}$.

######  Definiton 6.3.

$M_{\leq n}$ are privacy-loss independent if and only if, $\forall y_{\leq
n}\in Range(M_{\leq n})$,

$L(y_{\leq n})=\prod\limits_{i=1}^{n}L(y_{i})$ (52)

######  Corollary 6.2.

If $M_{\leq n}$ are privacy-loss independent and all $M_{i}$ fully utilize
their privacy budget (i.e., $\forall y\in
Range(M_{i}):L(y)=e^{\epsilon_{i}}$), then $\forall y_{\leq n}\in
Range(M_{\leq n})$:

$L(y_{\leq n})=\exp(\sum\limits_{i}^{n}\epsilon_{i})$ (53)

The corollary above indicates that the composition of privacy-loss independent
queries, each with full privacy-budget utilization, is equivalent to the basic
composition. Now, we will present a common case of composition whose queries
are privacy-loss independent:

######  Definiton 6.4.

A data space $\mathcal{X}$ can be decomposed into $n$ spaces
$\\{\mathcal{V}_{1},\mathcal{V}_{2},...,\mathcal{V}_{n}\\}$, denoted as
$\mathcal{X}=\prod_{i}\mathcal{V}_{i}$, if and only if, for any
$x\in\mathcal{X}$, there exists one and only one tuple of
$(v_{1},v_{2},...,v_{n})\in\\{\mathcal{V}_{1},\mathcal{V}_{2},...,\mathcal{V}_{n}\\}$,
and vice versa.

######  Theorem 6.2.

$M_{\leq n}$ are privacy-loss independent if there exists data spaces
$\\{\mathcal{V}_{1},\mathcal{V}_{2},...,\mathcal{V}_{n}\\}$ such that
$\mathcal{X}=\prod_{i}\mathcal{V}_{i}$ and $\forall
i\in[1,n]\cap\mathbb{N},\forall x\in\mathcal{X},\forall y_{i}\in
Y_{i}:Pr(y_{i}|x)=Pr(y_{i}|v_{i})$, where $v_{i}\in\mathcal{V}_{i}$ is the
$i$-th decomposed value from $x$.

The proof is provided in Appendix C.3.

Consider an object with multiple properties, and the possible values of the
object are the Cartesian product of the possible values of each property. If
all the queries against the object only depend on different properties of the
object, then all the queries are privacy-loss independent. If all the queries
fully utilize their privacy budget, the corresponding Bayesian composition
degenerates to the basic composition, and the efficiency in this case is
always one. Another example is that if an object changes its value over time
(e.g., Markov chain), then the queries against its value over time are also
privacy-loss independent.

###  6.2 Composing Identical Queries

The initial benchmark in the efficiency experiment for Bayesian composition
involves continually composing a sequence of identical binary randomized
responses, yielding either 0 or 1. The evaluation focuses on determining how
many more queries Bayesian composition can accept compared to basic
composition. The results are presented below:

######  Theorem 6.3.

If the total privacy budget is $\epsilon_{g}$, and each binary randomized
response has LDP guarantee of $\frac{\epsilon_{g}}{k}$, then the expected
number of queries accepted by a Bayesian Privacy Filter is

$\frac{-ke^{-2\epsilon_{g}}+2ke^{-\epsilon_{g}}-k}{\frac{e^{\frac{\epsilon_{g}}{k}}-1}{e^{\frac{\epsilon_{g}}{k}}+1}(e^{-2\epsilon_{g}}-1)}.$
(54)

In comparison, the basic composition can only accept $k$ queries with the same
setting. Additionally, we have:

######  Corollary 6.3.

When $\epsilon_{g}\rightarrow 0$, expected number of allowed queries will
converge to $k^{2}$.

The comprehensive proof and discussion have been moved to Appendix D, because
the composition of identical randomized responses is proved to have lower
precision in frequency estimation than using a single query (see Appendix E).

###  6.3 Composing Linear Regressions

(a)

(b)

(c)

(d)

Figure 1: Results for Composition Experiments. (a) realized privacy loss vs.
number of accepted queries for 10 sampled linear regressions; (b) confidential
interval (10th to 90th percentile, same for (d)) of number of accepted queries
vs. privacy budget for linear regressions; (c) realized privacy loss vs.
number of accepted queries for 10 sampled logistic regressions; and (d)
confidential interval of number of accepted queries vs. privacy budget for
logistic regressions.

An experiment is designed to continually send linear regressions to query an
object protected by a Bayesian Privacy Filter until the filter starts
rejecting. This section will compare the number of the queries allowed by the
privacy filter with that by the basic composition. The object has a
9-dimensional domain and each dimension ranges from $[-1,1]$, denoted as
$x\in[-1,1]^{9}$. For convenience, the true value $x$ is set to be
$\mathbf{0}$ for all dimensions, unknown to the analyst querying the object.
The object is assigned a privacy budget $\epsilon=1.0$. Each linear
regression, with 10 parameters denoted as
$\mathbf{\theta}=\\{\theta_{0},\theta_{1},...,\theta_{9}\\}$, has $\theta_{i}$
uniformly sampled between [-1, 1]. The $\mathbf{\theta}$ of each query is
normalized to be $||\mathbf{\theta}||_{1}=1$ ($L_{1}$ Norm). Before enforcing
LDP, the output of the linear regression against $x$ is
$y=\theta_{0}+\sum_{1\leq i\leq 9}\theta_{i}x_{i}$, and $y\in[-1,1]$. LDP is
enforced against $y$, following Section 2.4, with a guarantee of
$\epsilon=0.1$ per query. The privacy filter groups every 10 regressions to
reduce computation (see Section B), and the realized privacy loss is computed
using the branch-and-bound method (Section 5.4).

The experiment follows Algorithm 6 and has been executed 50 times. Fig. 1(a)
randomly samples 10 runs, illustrating that the realized privacy loss
increases with the number of queries accepted by the privacy filter. In all
sampled experiments, the realized privacy loss grows slower than that of basic
composition.

Additionally, the confidence interval of the number of accepted queries given
a privacy budget $\epsilon$ is of interest. The number of accepted queries
given a privacy budget is equivalent to the smallest number accepted given a
realized privacy loss. Thus, the number of accepted queries is interpolated
for each experiment across different privacy budgets ($\epsilon$ from 0.1 to
1.0), and the 10th percentile (lower bound), median, and 90th percentile
(upper bound) are computed. The results in Fig 1(b) indicate that the number
of accepted queries increases approximately linearly with $\epsilon$. The
median of accepted queries at $\epsilon=1.0$ is 47, while basic composition
only accepts 10 queries.

###  6.4 Composing Logistic Regressions

An experiment akin to Section 6.3 is conducted for logistic regressions. All
the setups remain identical except for the parameter $\mathbf{\theta}$ of each
logistic regression. Like linear regression, $\mathbf{\theta}$ has 10
dimensions, but each dimension is uniformly sampled between $[-10,10]$ without
normalization. Before enforcing LDP, the output $y$ is
$\frac{1}{1+e^{-(\theta_{0}+\sum\theta_{i}x_{i})}}$, ranging from 0 to 1. LDP
is enforced against $y$ following Section 2.4.

The experiment is run for 50 times. Fig. 1(c) randomly samples 10 runs,
illustrating that the realized privacy loss increases with the number of
queries accepted by the Bayesian Privacy Filter. Similar to the linear
regression experiment, all sampled experiments exhibit a realized privacy loss
growing slower than that of basic composition.

Also, akin to Section 2.4, the confidence interval of the number of accepted
logistic regressions given a privacy budget $\epsilon$ is plotted in Fig.
1(d), with upper and lower bounds as the 90th and 10th percentiles,
respectively. Similar to linear regression, the number of accepted logistic
regressions increases approximately linearly with $\epsilon$. The median of
accepted queries at $\epsilon=1.0$ is 21, while for linear regression, it is
47. Nevertheless, it still outperforms basic composition.

###  6.5 Read-world Example: Compose Regressions of Healthcare data

An analyst, such as an insurance company, may be interested in extracting
average health conditions and disease incidence rates from a group’s health
checkup data. The analyst might train linear or logistic regression models
using public datasets or existing literature and apply them to the group. This
section explores how a Bayesian Privacy Filter could assist the analyst in
optimizing the usage of the privacy budget when the health checkup data is
protected by $\epsilon$-LDP. The dataset includes information on age, sex,
blood pressure, and BMI. Three logistic regressions are trained from public
datasets [36, 37, 38] to predict the likelihood of individuals having heart
disease, stroke, and diabetes. The mean of these probabilities represents the
disease incidence rates for the group. Additionally, a linear regression is
trained from a public dataset [39] to predict individuals’ sleep duration, and
the mean of the predicted values yields the group’s average sleep duration,
which is also interested by the analyst. The regression parameters can be
found in Appendix F. To enforce LDP, these regressions are discretized and
perturbed following Section 2.4. Each individual in the group is assigned a
privacy budget of $\epsilon=4$, with each regression having an DP guarantee of
$\epsilon=1$. Their realized privacy loss is computed using the branch-and-
bound method (Section 5.4). As each regression randomly returns two discrete
values, there are 16 possible outcomes. The realized privacy losses are
detailed in Appendix F. In the worst case, 3.7 out of 4 of the privacy budget
$\epsilon$ is consumed, while the median privacy loss is only 2.46 out of 4,
indicating that at least half of the group can receive additional queries with
an DP guarantee $\epsilon$ of at least 1.54.

###  6.6 Use Case of Bayesian Composition

Lemma 6.1 establishes that the worst-case scenario for Bayesian composition is
equivalent to that of basic composition. In contrast, Theorem 6.1 demonstrates
that Bayesian composition outperforms basic composition when the composed
queries are privacy-loss compactible. Thus, the Bayesian composition can
seamlessly replace the basic composition wherever it is employed. A common
application of basic composition involves privacy accounting for LDP queries.
When transitioning to Bayesian composition for accounting, a Bayesian Privacy
Filter is assigned to an object and the corresponding Bayesian Privacy
Odometer is used to track the usage of the privacy budget. The adversary in
Algorithm 2 represents anyone (and not even the same person all the time)
querying against the object. The interaction is halted when the object expires
or the realized privacy loss reaches the assigned privacy budget.

Though the basic composition can always be replaced by Bayesian composition,
the necessity is worth considering, because Bayesian composition requires
computing realized privacy loss, which might be expensive in some cases. For
instance, when querying an object with continuous values, the branch-and-bound
method (Section 5.4) is required, which is generally computation-intensive.
Furthermore, if the object being queried has multiple fields with independent
domains, and the composed queries read different fields, Theorem 6.2 asserts
that Bayesian composition yields the same effect as basic composition.
Additionally, Appendix E illustrates that when estimating the histogram of a
group of objects, using Bayesian composition of randomized responses against
an individual object results in a less precise estimation than applying a
single randomized response. Therefore, one should be careful when deciding to
switch from a single query to the corresponding Bayesian composition. However,
the evaluation in Section 6 highlights that Bayesian composition of linear and
logistic regressions against objects with continuous values can be 2-5 times
as efficient as basic composition. In scenarios where privacy budgets are
scarce, deploying Bayesian composition becomes a viable and worthwhile option.

##  7 Future Work

Some future work is presented here for further exploration. The first work is
the investigation of $(\epsilon,\delta)$-Bayesian Privacy Filters. While
introduced in this article, the optimal implementation remains unproven.
Different privacy filters can serve as Filter $F_{0}$ in Algorithm 4, and an
evaluation of which filter yields the best results is yet to be conducted.
Moreover, the question arises: Is it possible to develop a
$(\epsilon,\delta)$-Bayesian Privacy Filter without depending on another
privacy filter?

Another future work involves extending the computation of realized privacy
loss to more query types, some of which are not trivial to be converted as DC
programming. For instance, the input of a polynomial regression introduces
terms like $x_{i}x_{j}$, where $x_{i}$ and $x_{j}$ are two fields of $x$, and
the likelihood function of a polynomial regression may not be concave, unlike
that of linear regression. Addressing this challenge requires additional
exploration to render it DC. Similarly, multi-class logistic regression can be
rewritten to DC, following the same methodology in Section 5.3.3, but finding
the concave envelope of its $g(x)$ is a non-trivial task. More complex query
types, such as neural networks, pose additional challenges in their conversion
to DC programming.

##  8 Conclusion

This paper has introduced several key contributions:

  1. 1.

The concept of “Knowledge gain as Privacy loss” is proposed to measure the
realized privacy loss of an object, which captures the difference between the
posterior and prior belief of a person regarding an object.

  2. 2.

Bayesian Privacy Filter was introduced to enable a fully adaptive composition
to fully utilize privacy budget while preserving the DP guarantee of the
composition; Bayesian Odometer was introduced to monitor the realized privacy
loss during a fully adaptive composition.

  3. 3.

A branch-and-bound method is devised to compute the realized privacy loss of
linear and logistic regressions against objects with continuous values,
allowing the deployment of Bayesian Privacy Filter.

  4. 4.

The Bayesian composition of linear and logistic regressions is observed to
accept 2-5 times as many queries as basic composition.

## References

  * [1] R. Shokri and V. Shmatikov, “Privacy-preserving deep learning,” in _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 2015, pp. 1310–1321.
  * [2] C. Dwork, “Differential privacy,” in _International colloquium on automata, languages, and programming_. Springer, 2006, pp. 1–12.
  * [3] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016, pp. 308–318.
  * [4] M. U. Hassan, M. H. Rehmani, and J. Chen, “Differential privacy techniques for cyber physical systems: a survey,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 1, pp. 746–789, 2019.
  * [5] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” _SIAM Journal on Computing_ , vol. 40, no. 3, pp. 793–826, 2011.
  * [6] Ú. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in _Proceedings of the 2014 ACM SIGSAC conference on computer and communications security_ , 2014, pp. 1054–1067.
  * [7] A. Team _et al._ , “Learning with privacy at scale,” _Apple Mach. Learn. J_ , vol. 1, no. 8, pp. 1–25, 2017.
  * [8] B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [9] Y. Wang, X. Wu, and D. Hu, “Using randomized response for differential privacy preserving data collection.” in _EDBT/ICDT Workshops_ , vol. 1558, 2016, pp. 0090–6778.
  * [10] S. P. Kasiviswanathan and A. Smith, “On the’semantics’ of differential privacy: A bayesian formulation,” _Journal of Privacy and Confidentiality_ , vol. 6, no. 1, 2014.
  * [11] Apple, “Differential privacy.” [Online]. Available: https://www.apple.com/privacy/docs/Differential_Privacy_Overview.pdf
  * [12] Apple and Google, “Exposure notification privacy-preserving analytics (enpa) white paper,” _ENPA White Paper_ , 2021.
  * [13] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [14] R. M. Rogers, A. Roth, J. Ullman, and S. Vadhan, “Privacy odometers and filters: Pay-as-you-go composition,” _Advances in Neural Information Processing Systems_ , vol. 29, 2016.
  * [15] M. Yang, L. Lyu, J. Zhao, T. Zhu, and K.-Y. Lam, “Local differential privacy and its applications: A comprehensive survey,” _arXiv preprint arXiv:2008.03686_ , 2020.
  * [16] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3_. Springer, 2006, pp. 265–284.
  * [17] J. Lee and C. Clifton, “Differential identifiability,” in _Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2012, pp. 1041–1049.
  * [18] N. Li, W. Qardaji, D. Su, Y. Wu, and W. Yang, “Membership privacy: A unifying framework for privacy definitions,” in _Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security_, 2013, pp. 889–900.
  * [19] D. Durfee and R. M. Rogers, “Practical differentially private top-k selection with pay-what-you-get composition,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [20] M. Lécuyer, R. Spahn, K. Vodrahalli, R. Geambasu, and D. Hsu, “Privacy accounting and quality control in the sage differentially private ml platform,” in _Proceedings of the 27th ACM Symposium on Operating Systems Principles_ , 2019, pp. 181–195.
  * [21] V. Feldman and T. Zrnic, “Individual privacy accounting via a renyi filter,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 28 080–28 091, 2021.
  * [22] M. Lécuyer, “Practical privacy filters and odometers with r$\backslash$’enyi differential privacy and applications to differentially private deep learning,” _arXiv preprint arXiv:2103.01379_ , 2021.
  * [23] J. Whitehouse, A. Ramdas, R. Rogers, and Z. S. Wu, “Fully adaptive composition in differential privacy,” _arXiv preprint arXiv:2203.05481_ , 2022.
  * [24] P. D. Tao and L. H. An, “Convex analysis approach to dc programming: theory, algorithms and applications,” _Acta mathematica vietnamica_ , vol. 22, no. 1, pp. 289–355, 1997.
  * [25] F. I. Bacchus, “Representing and reasoning with probabilistic knowledge.” Ph.D. dissertation, University of Alberta, 1989.
  * [26] J. Y. Halpern, _Reasoning about uncertainty_. MIT press, 2017.
  * [27] M. Richardson and P. Domingos, “Markov logic networks,” _Machine learning_ , vol. 62, pp. 107–136, 2006.
  * [28] S. Russell, “Unifying logic and probability,” _Communications of the ACM_ , vol. 58, no. 7, pp. 88–97, 2015.
  * [29] T. T. Nguyên, X. Xiao, Y. Yang, S. C. Hui, H. Shin, and J. Shin, “Collecting and analyzing data from smart device users with local differential privacy,” _arXiv preprint arXiv:1606.05053_ , 2016.
  * [30] Q. Ye, H. Hu, X. Meng, and H. Zheng, “Privkv: Key-value data collection with local differential privacy,” in _2019 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2019, pp. 317–331.
  * [31] I. 27001, “Information security management systems,” International Organization for Standardization, Geneva, CH, Standard, Oct. 2022.
  * [32] C. Dwork and G. N. Rothblum, “Concentrated differential privacy,” _arXiv preprint arXiv:1603.01887_ , 2016.
  * [33] A. Triastcyn and B. Faltings, “Bayesian differential privacy for machine learning,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 9583–9592.
  * [34] B. Ding, H. Nori, P. Li, and J. Allen, “Comparing population means under local differential privacy: with significance and power,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 32, no. 1, 2018.
  * [35] H. P. Benson and R. Horst, “A branch and bound-outer approximation algorithm for concave minimization over a convex set,” _Computers & Mathematics with Applications_, vol. 21, no. 6-7, pp. 67–76, 1991.
  * [36] A. Janosi, W. Steinbrunn, M. Pfisterer, and R. Detrano, “Heart Disease,” UCI Machine Learning Repository, 1988, DOI: https://doi.org/10.24432/C52P4X.
  * [37] “Mckinsey analytics online hackathon - healthcare analytics.” 2018. [Online]. Available: https://datahack.analyticsvidhya.com/contest/mckinsey-analytics-online-hackathon/
  * [38] “National institutes of diabetes and digestive and kidney diseases,” 1998. [Online]. Available: https://www.kaggle.com/datasets/mathchi/diabetes-data-set/data
  * [39] “Sleep health and lifestyle dataset,” 2023. [Online]. Available: https://www.kaggle.com/datasets/uom190346a/sleep-health-and-lifestyle-dataset/data

##  Appendix A Example: Realized Privacy Loss of Mean and Variance Estimators

In this section, a practical example is presented to illustrate that basic
composition fails to fully utilize its privacy budget and highlights the
necessity of considering realized privacy loss. Consider a group of objects
$\mathbf{x}$, each a scalar within the range of $[-1,1]$. Their mean and
variance estimations are $\mathbb{E}_{x\in\mathbf{x}}[x]$ and
$\mathbb{E}_{x\in\mathbf{x}}[x^{2}]-\mathbb{E}_{x\in\mathbf{x}}[x]^{2}$,
respectively. To enforce LDP for these estimators, we replace $y$ in Eq. (8)
with $x$ and $x^{2}$, respectively. This LDP processing is commonly employed
in prior literature (e.g., [34]). Given the linear relationship between
$Pr(o|y)$ and $y$ in Eq. (8), we have

$Pr(o_{1}|x)=\alpha_{1}x+\beta_{1},$ (55)

and

$Pr(o_{2}|x)=\alpha_{2}x^{2}+\beta_{2},$ (56)

where $o_{1}$ and $o_{2}$ can be any outputs from LDP-enforced mean and
variance estimators, respectively; $\alpha_{1},\beta_{1},\alpha_{2},\beta_{2}$
are the abbreviation of the query parameters after replacing $y$ with $x$ and
$x^{2}$.

Assume both LDP-enforced estimators are $\epsilon$-LDP, and they are applied
against the same object. The log of the conditional probability is

$\log
Pr(o_{1},o_{2}|x)=\log(\alpha_{1}x+\beta_{1})+\log(\alpha_{2}x^{2}+\beta_{2}).$
(57)

Since $x\in[-1,1]$, its maximum and minimum can either be located at the
bounds or a critical point (if within the bound). First, the critical points
are derived analytically for all possible outputs:

$o_{1}$ | $o_{2}$ | $\frac{d}{dx}\log Pr(o_{1},o_{2}|x)$
---|---|---
1 | 1 | $\frac{\sqrt{e^{2\epsilon}-e^{\epsilon}+4}-e^{\epsilon}-1}{3e^{\epsilon}-3}$
1 | 0 | $\frac{\sqrt{4e^{2\epsilon}-e^{\epsilon}+1}-e^{\epsilon}-1}{3e^{\epsilon}-3}$
-1 | 1 | $\frac{-\sqrt{e^{2\epsilon}-e^{\epsilon}+4}+e^{\epsilon}+1}{3e^{\epsilon}-3}$
-1 | 0 | $\frac{-\sqrt{4e^{2\epsilon}-e^{\epsilon}+1}+e^{\epsilon}+1}{3e^{\epsilon}-3}$

Then, we set $\epsilon=1$ and compute $\max_{x}\log Pr(o_{1},o_{2}|x)$,
$\min_{x}\log Pr(o_{1},o_{2}|x)$, and realized privacy loss

$\log L(o_{1},o_{2})=\max\limits_{x}\log Pr(o_{1},o_{2}|x)\\\
-\min\limits_{x}\log Pr(o_{1},o_{2}|x)$ (58)

for all possible $o_{1}$ and $o_{2}$:

$o_{1}$ | $o_{2}$ | $\max\log Pr$ | $\min\log Pr$ | $\log L$
---|---|---|---|---
1 | 1 | -0.63 | -2.04 | 1.41
1 | 0 | -0.94 | -2.63 | 1.69
-1 | 1 | -0.63 | -2.04 | 1.41
-1 | 0 | -0.94 | -2.63 | 1.69

All outputs exhibit a realized privacy loss less than $e^{2}$. However, the
basic composition will consider these two queries being $2$-LDP, thus failing
to fully utilize its privacy budget for any outputs. Using $o_{1}=1$ and
$o_{2}=1$ as an example, an intuitive explanation is that $x=-1$ is the least
likely to output $o_{1}=1$, but it is not the least likely to output
$o_{2}=1$. Consequently,
$\min_{x}Pr(o_{1}=1,o_{2}=1|x)>\min_{x}Pr(o_{1}=1|x)\min_{x}Pr(o_{2}=1|x)$.
This discrepancy results in the realized privacy loss less than that from the
basic composition.

##  Appendix B Grouping Queries

This section introduces a method to break down the computation of the extrema
of $P(x)$ into smaller problems, each of which computes the extrema of $P(x)$
for a subset of the accepted queries. It is particularly helpful when
complexity of computing the extrema of $P(x)$ grows superlinearly (e.g.
exponentially) with the number of composed queries. Given a sequence of
queries, each denoted as $M_{i}$ with $y_{i}$ as the corresponding output, the
upper bound of their likelihood function $P(x)$ can be computed as

$\max\limits_{x\in\mathcal{X}}P(x)\leq\prod\limits_{i=mk+1,k\in\mathbb{N},i\leq
n}\max\limits_{x\in\mathcal{X}}\prod\limits_{1\leq j\leq m}P_{i+j}(x),$ (59)

where $P_{i}(x)=Pr(M_{i}(x)=y_{i}|x)$. The right hand side of Eq. (59)
organizes the queries into groups of size $m$, calculates the $\max P(x)$
within each group, and utilizes the product of these maxima across all groups
as the upper bound for the $P(x)$ of all queries. If the complexity of
computing $\max_{x}P(x)$ is $O(c^{N})$, where $c$ is a constant and $N$ is the
number of queries, then computing the $\max P(x)$ within each group will be
$O(c^{m})$, and finding the upper bound of $P(x)$ will be
$O(c^{m}\frac{N}{m})\sim O(N)$.

##  Appendix C Proofs in Section 6.1

###  C.1 Proof of Theorem 6.1

Proof: Define $y_{\leq n}$ to be the result of an arbitrary set of queries
accepted by a Bayesian composition, where $n$ is the number of the queries.
Based on Eq. (23), $L(y_{\leq n})\leq L(y_{\leq i})L(y_{[i+1,n]})$, where
$y_{[i+1,n]}$ represents the set from the $(i+1)$-th query to the $n$-th
query. Since the order of queries does not impact the realized privacy loss,
without loss of generality, we assume the $(n-1)$-th and $n$-th queries are
privacy-loss compactible. Thus, $\exists y_{n-1},y_{n}\in
Range(M_{n-1},M_{n})$:

$L(y_{\leq n})\leq L(y_{\leq n-2})L(y_{n-1},y_{n})<L(y_{\leq
n-2})e^{\epsilon_{n-1}+\epsilon_{n}}.$ (60)

Given the assumption of an greedy adversary, $L(y_{\leq n})=e^{\epsilon_{g}}$,
so

$L(y_{\leq n-2})>e^{\epsilon_{g}-\epsilon_{n-1}-\epsilon_{n}}.$ (61)

Furthermore,

$L(y_{\leq
n-2})\leq\prod\limits_{i=1}^{n-2}\frac{\max\limits_{x}Pr(y_{i}|x)}{\min\limits_{x}Pr(y_{i}|x)}=\exp(\sum\limits_{i=1}^{n-2}\epsilon_{i}).$
(62)

Combining Eq. (61) and (62) and we have
$\epsilon_{g}<\sum\limits_{i=1}^{n}\epsilon_{i}$, i.e., $K>1$. ∎

###  C.2 Proof of Theorem 6.2

Proof: Assume the DP guarantee is tight. Otherwise, replace $\epsilon$ with
the corresponding tight value. Denote $M$ to be the mechanism of the identical
queries. Given the definition of $\epsilon$-DP, there exists $y$ and two
object values $x_{1}$ and $x_{2}$ such that
$Pr(y|x_{1})=e^{\epsilon}Pr(y|x_{2})$. It is easy to see that
$x_{1}=\operatorname*{argmax}_{x}Pr(y|x)$ and
$x_{2}=\operatorname*{argmin}_{x}Pr(y|x)$.

Also, $\forall x\in\mathcal{X}:\sum_{y}Pr(y|x)=1$. Given
$Pr(y|x_{1})>Pr(y|x_{2})$, there must exist another $y^{\prime}$ such that
$Pr(y^{\prime}|x_{1})<Pr(y^{\prime}|x_{2})\leq\max_{x}Pr(y^{\prime}|x)$.

Define $u=\operatorname*{argmax}_{x}Pr(y|x)Pr(y^{\prime}|x)$. If $u=x_{1}$,
given $Pr(y^{\prime}|x_{1})<\max_{x}Pr(y^{\prime}|x)$, we have
$Pr(y|u)Pr(y^{\prime}|u)<Pr(y|x_{1})\max_{x}Pr(y^{\prime}|x)$. If $u\neq
x_{1}$, we have $Pr(y|u)<Pr(y|x_{1})$, so we also get
$Pr(y|u)Pr(y^{\prime}|u)<Pr(y|x_{1})\max_{x}Pr(y^{\prime}|x)$. Therefore,

$L(y,y^{\prime})=\frac{Pr(y|u)Pr(y^{\prime}|u)}{\min\limits_{x\in\mathcal{X}}Pr(y|x)Pr(y^{\prime}|x)}<\\\
\frac{Pr(y|x_{1})\max\limits_{x\in\mathcal{X}}Pr(y^{\prime}|x)}{Pr(y|x_{2})\min\limits_{x\in\mathcal{X}}Pr(y^{\prime}|x)}=e^{2\epsilon}.\qed$
(63)

###  C.3 Proof of Theorem 6.2

Proof:

$L(y_{\leq
n})=\frac{\max\limits_{x\in\mathcal{X}}\prod\limits_{i}^{n}Pr(y_{i}|x)}{\min\limits_{x\in\mathcal{X}}\prod\limits_{i}^{n}Pr(y_{i}|x)}\\\
=\frac{\max\limits_{(v_{1},v_{2},...,v_{n})\in\\{\mathcal{V}_{1},\mathcal{V}_{2},...,\mathcal{V}_{n}\\}}\prod\limits_{i}^{n}Pr(y_{i}|v_{i})}{\min\limits_{(v_{1},v_{2},...,v_{n})\in\\{\mathcal{V}_{1},\mathcal{V}_{2},...,\mathcal{V}_{n}\\}}\prod\limits_{i}^{n}Pr(y_{i}|v_{i})}\\\
=\frac{\prod\limits_{i}^{n}\max\limits_{v_{i}\in\mathcal{V}_{i}}Pr(y_{i}|v_{i})}{\prod\limits_{i}^{n}\min\limits_{v_{i}\in\mathcal{V}_{i}}Pr(y_{i}|v_{i})}=\prod\limits_{i}^{n}L(y_{i}).\qed$
(64)

##  Appendix D Details of Composing Identical Randomized Responses

While Lemma 6.1 proves that the Bayesian composition is at least as efficient
as the basic composition, we would like to explore the exact value of its
efficiency. In this section, we will conduct an experiment to ask a Bayesian
Privacy Filter to accept as many identical queries as possible. Since all
queries are identical, the efficiency $K$ is proportional to the number of
accepted queries. Lemma 6.2 shows that identical queries are privacy-loss
compactible, so we expect the Bayesian composition to accept more queries than
the basic composition.

The queries used in the experiment are $\epsilon$-DP randomized responses. The
randomized responses have an output distribution given by

$Pr(y|x)=\begin{cases}\frac{e^{\epsilon}}{|\mathcal{X}|-1+e^{\epsilon}},&\text{if
}x=y\\\ \frac{1}{|\mathcal{X}|-1+e^{\epsilon}},&\text{if }x\neq y\\\
\end{cases},$ (65)

where $y\in\mathcal{X}$. The queried object has a privacy budget of
$k\epsilon$, which is protected by a Simplified Bayesian Privacy Filter111Both
the Bayesian Privacy Filter and Simplified Bayesian Privacy Filter behave the
same when it comes to accepting or rejecting a randomized response. The data
universe $\mathcal{X}$ consists of $m$ elements (i.e., $[x_{i}]_{1\leq i\leq
m}$), and the queried object has a value of $x_{1}$. The randomized responses
will be continually run against the object until a randomized response is
rejected by the privacy filter. This is equivalent to the experiment in
Algorithm 6, where the sequence of queries are identical randomized responses

The experiment described above can be viewed as a random walk among $P(x)$
(see Algorithm 3). The initial state is defined as $P(x)=1$ for every
candidate $x$. When the privacy filter accepts a randomized response, the
response can yield any value $y$ from $\mathcal{X}$. From the perspective of a
random walker, this corresponds to transitioning from state $P$ to a new state
$P^{\prime}$, where $P^{\prime}(y)=P(y)e^{\epsilon}$ and $P^{\prime}(x)=P(x)$
if $x\neq y$, with a probability of $Pr(y|x)$. It is important to note that
every element of $P^{\prime}$ is then normalized to $\min P^{\prime}$. The
random walk is terminated when a state is reached where one and only one
$P(x)=e^{k\epsilon}$. Figure 2 illustrates an example of the transition graph
when $m=2$ and $k=2$. The number of steps taken from the initial state to a
terminated state corresponds to the number of allowed queries by the privacy
filter

Figure 2: An example of the transition graph of map $P$, where $m=2$ and
$k=2$. $[a,b]$ in the graph represents
$\\{P(x_{1})=e^{a\epsilon},P(x_{2})=e^{b\epsilon}\\}$. The value of the edges
$w$ represents a weight $e^{w}$ to reach a neighboring state.

Let’s first consider the simplest case where $m=2$. We will use a tuple to
represent a possible state of $P(x)$, and define $[a,b]$ to represent
$\\{P(x_{1})=e^{a\epsilon},P(x_{2})=e^{b\epsilon}\\}$. The possible states of
$P(x)$ when $m=2$ are $[0,k],[0,k-1],\ldots,[0,0],[1,0],\ldots,[k-1,0],[k,0]$.
Without loss of generality, we index the values in the same order as mentioned
above and denote $P_{i}$ as the $i$-th state of $P(x)$. For any transient
state $P_{i}$, i.e., neither $[0,k]$ nor $[k,0]$, the probability of
transitioning from $P_{i}$ to $P_{i+1}$ is
$\frac{e^{\epsilon}}{e^{\epsilon}+1}$, while the probability of transitioning
from $P_{i}$ to $P_{i-1}$ is $\frac{1}{e^{\epsilon}-1}$. Thus, the problem is
simplified to a one-dimensional random walk starting at $[0,0]$ and
terminating at either $[0,k]$ or $[k,0]$. Let $E(x)$ denote the expected
number of steps required to reach a terminated state from the state
corresponding to $P(x)$, i.e., $[x,0]$ if $x\geq 0$, or $[0,-x]$ if $x<0$.
$E(x)$ satisfies the following recurrence relation:

$E(x)=1+\frac{e^{\epsilon}}{e^{\epsilon}+1}E(x+1)+\frac{1}{e^{\epsilon}+1}E(x-1),$
(66)

subject to $E(-k)=0$ and $E(k)=0$. The solution of $E(x)$ is

$E(x)=\frac{-(x+k)e^{-2k\epsilon}+2ke^{-(x+k)\epsilon}+x-k}{\frac{e^{\epsilon}-1}{e^{\epsilon}+1}(e^{-2k\epsilon}-1)}.$
(67)

Substituting $x=0$, i.e., the initial state $[0,0]$, into the above equation
yields

######  Theorem D.1.

When $m=2$, the expected number of queries, denoted as $E(0)$, in a Bayesian
composition is

$E(0)=\frac{-ke^{-2k\epsilon}+2ke^{-k\epsilon}-k}{\frac{e^{\epsilon}-1}{e^{\epsilon}+1}(e^{-2k\epsilon}-1)}.$
(68)

(a) $m=2$, different $\epsilon$

(b) $\epsilon=1$, different $m$

Figure 3: Expected Number of Accepted Queries vs $k$

Figure 3(a) depicts the expected number of accepted queries for different
values of $\epsilon$. Considering Eq. (68) as a function of $k$, we can derive
the following corollary:

######  Corollary D.1.

When $m=2$ and $k\rightarrow\infty$, the expected number of allowed queries
$E(0)\rightarrow\frac{k(e^{\epsilon}+1)}{e^{\epsilon}-1}$.

We observe that $E(0)$ increases linearly with $k$ eventually. By using the
ratio $E(0)/k$, we can measure the efficiency of a Bayesian composition
compared to a $k\epsilon$-basic composition. It is evident that
$E(0)/k\rightarrow\frac{e^{\epsilon}+1}{e^{\epsilon}-1}$ when $k$ is large
enough. As $\epsilon$ decreases, the efficiency of the Bayesian composition
increases. Interestingly, $E(0)/k\rightarrow\infty$ as $\epsilon\rightarrow
0$, implying that privacy becomes almost costless when the DP parameter
$\epsilon$ is small enough.

Furthermore, if the total budget $k\epsilon$ is fixed for a Bayesian
composition, denoted as $\epsilon_{g}$, we have

$E(0)=\frac{-ke^{-2\epsilon_{g}}+2ke^{-\epsilon_{g}}-k}{\frac{e^{\epsilon_{g}/k}-1}{e^{\epsilon_{g}/k}+1}(e^{-2\epsilon_{g}}-1)}.$
(69)

Considering $E[0]$ as a function of $\epsilon_{g}$, we obtain the following
corollary:

######  Corollary D.2.

When $m=2$ and $\epsilon_{g}\rightarrow 0$, expected number of allowed queries
$E[0]\rightarrow k^{2}$.

This result is obtained by applying L’Hôpital’s Rule to $E(0)$.

Now, let’s explore more general cases where $m>2$. We will assume that all
possible states of the map $P$ are indexed. The probability of a random walker
transitioning from state $j$ to state $i$ can be represented by a transition
matrix:

$\mathcal{T}_{ij}=\begin{cases}P(y|x_{1}),\text{ if state $i$ + output $y$
$\rightarrow$ state $j$,}\\\ 1,\text{ if $i=j$ and state $i$ is a termination
state,}\\\ 0,\text{otherwise.}\end{cases}.$ (70)

Assuming that the first state is the initial state, the probabilities of the
random walker being in each state after $n$ steps can be represented by a
vector $\mathbf{s}_{n}$. Here, $\mathbf{s}_{n}[i]$ represents the probability
of being in state $i$ after $n$ steps. Initially, the walker is at the initial
state, so $\mathbf{s}_{0}=[1,0,0,...,0]^{T}$. The vector $\mathbf{s}_{n}$ can
then be computed as:

$\mathbf{s}_{n}=\mathcal{T}^{n}[1,0,0,...,0]^{T}.$ (71)

Suppose state $z$ is a termination state. The value
$\mathbf{s}_{n}[z]-\mathbf{s}_{n-1}[z]$ represents the probability of the
random walker reaching state $z$ at step $n$. Therefore, the expected number
of steps to reach any termination state can be calculated as

$\sum\limits_{z\in\mathbf{z}}\sum\limits_{n=1}^{\infty}n(\mathbf{s}_{n}[z]-\mathbf{s}_{n-1}[z]),$
(72)

where $\mathbf{z}$ is the collection of all termination states. Since it is
not feasible to iterate $n$ until infinity, we will stop the iteration when
$\mathbf{s}_{n}$ is approximately equal to $\mathbf{s}_{n-1}$, which is
defined as $\forall i:|\mathbf{s}_{n}[i]-\mathbf{s}_{n-1}[i]|\leq\theta$.
Here, $\theta$ is a small threshold and is set to $10^{-9}$ for our experiment
in order to compute Eq. (72) numerically.

We computed Eq. (72) for different values of $k$ and $m$. The computational
complexity of this process increases rapidly. The intermediate states have a
size of $k^{m}-(k-1)^{m}$, which means that each $P(x_{i})$ can range from 0
to $k-1$, with at least one $P(x_{i})=0$. The terminated states have a size of
$m[k^{m-1}-(k-1)^{m-1}]$, where one $P(x_{i})$ must be $k$, and at least one
$P(x_{j})=0$. The size of the possible states grows polynomially with $k$ and
exponentially with $m$. Therefore, we can only numerically compute a small
range of $k$ and $m$. In our experiment, we set $k$ to range from 2 to 15, and
$m$ to range from 2 to 4. The DP guarantee $\epsilon$ of a randomized response
is set to one. The results are shown in Figure 3(b). Based on the results, we
make the following conjectures:

######  Conjecture D.1.

Regardless of $m$, the expected number of allowed queries increases linearly
with $k$.

######  Conjecture D.2.

The expected number of allowed queries increases as $m$ increases.

##  Appendix E Single Randomized Response vs. Bayesian Composition of
Randomized Responses

The randomized response technique is used to estimate the histogram of a group
of objects $\mathbf{X}$ while preserving their privacy. When a group of
objects are surveyed, each object randomly responds with an output from
$\mathcal{X}$. An analyst counts the responses of each object and obtains a
histogram of responses $\mathbf{v}$, where the $i$-th element represents the
count of $x_{i}$. The true histogram of the queried objects can be estimated
using the formula:

$\hat{\mathbf{u}}=P^{-1}\mathbf{v},$ (73)

where $\hat{\mathbf{u}}$ is the estimator and $P^{-1}$ is the inverse of a
probability matrix where $P_{ij}=Pr(x_{j}|x_{i})$ in Eq. (65). The element at
location $(i,j)$ of $P^{-1}$ is given by:

$P^{-1}[i,j]=\begin{cases}\frac{e^{\epsilon}+m-1}{e^{\epsilon}-1},&\text{if
}i=j\\\ \frac{-1}{e^{\epsilon}-1},&\text{if }i\neq j\\\ \end{cases},$ (74)

where $m=|\mathcal{X}|$. The histogram of responses $\mathbf{v}$ can be
considered as the sum of individual unit vectors, each representing a
response. Suppose an object responds with $x_{i}$. The response can be
represented as a unit vector $\mathbf{v}_{i}$, where the $i$-th element is one
and the other elements are zero. Let $\mathbf{v}_{X}$ be the vector
representation of the response from an object $X\in\mathbf{X}$, and define
$\hat{\mathbf{u}}(X)=P^{-1}\mathbf{v}_{X}$ as an estimator of the value of
$X$. Now, we can rewrite $\hat{\mathbf{u}}$ as:

$\hat{\mathbf{u}}=\sum_{X\in\mathbf{X}}\hat{\mathbf{u}}(X)=\sum_{X\in\mathbf{X}}P^{-1}\mathbf{v}_{X}.$
(75)

The response $\mathbf{v}_{X}$ is a random variable, and we are interested in
the covariance of $\hat{\mathbf{u}}$:

$Cov(\hat{\mathbf{u}})=\sum_{X\in\mathbf{X}}Cov(P^{-1}\mathbf{v}_{X})=\sum_{X\in\mathbf{X}}P^{-1}Cov(\mathbf{v}_{X})P^{-1,T}$
(76)

######  Theorem E.1.

$Cov(\hat{\mathbf{u}})\propto\frac{1}{\epsilon^{2}}$ when $\epsilon\rightarrow
0$ .

Without loss of generality, define the object $X$ to have a value $x_{1}$.
Then $Cov(\mathbf{v}_{X})$ is computed as:

$Cov(\mathbf{v}_{X})=\begin{bmatrix}\frac{e^{\epsilon}}{M}-\frac{e^{2\epsilon}}{M^{2}}&-\frac{e^{\epsilon}}{M^{2}}&-\frac{e^{\epsilon}}{M^{2}}&...\\\
-\frac{e^{\epsilon}}{M^{2}}&\frac{1}{M}-\frac{1}{M^{2}}&-\frac{1}{M^{2}}&...\\\
-\frac{e^{\epsilon}}{M^{2}}&-\frac{1}{M^{2}}&\frac{1}{M}-\frac{1}{M^{2}}&...\\\
...&...&...&...\\\ \end{bmatrix},$ (77)

where $Cov(\mathbf{v}_{X})$ is an $m\times m$ matrix and $M=m-1+e^{\epsilon}$.
Assuming $\epsilon$ is small enough, we can approximate $e^{\epsilon}$ as
$1+\epsilon$. Therefore, the covariance matrix can be also approximated as:

$Cov(\mathbf{v}_{X})\approx\begin{bmatrix}\frac{1}{M}-\frac{1}{M^{2}}&-\frac{1}{M^{2}}&-\frac{1}{M^{2}}&...\\\
-\frac{1}{M^{2}}&\frac{1}{M}-\frac{1}{M^{2}}&-\frac{1}{M^{2}}&...\\\
-\frac{1}{M^{2}}&-\frac{1}{M^{2}}&\frac{1}{M}-\frac{1}{M^{2}}&...\\\
...&...&...&...\par\end{bmatrix}.$ (78)

Furthermore, the matrix $P^{-1}$ can be approximated as:

$P^{-1}\approx\frac{1}{\epsilon}\begin{bmatrix}m-1&-1&-1&...\\\
-1&m-1&-1&...\\\ -1&-1&m-1&...\\\ ...&...&...&...\par\end{bmatrix}.$ (79)

Thus, the covariance of $\hat{\mathbf{u}}(X)$ can be approximated as:

$Cov(\hat{\mathbf{u}}(X))\propto\frac{1}{\epsilon^{2}}.$ (80)

Consequently, $Cov(\hat{\mathbf{u}})\propto\frac{1}{\epsilon^{2}}$ when
$\epsilon$ is small enough.

The purpose of deriving the covariance of $\hat{\mathbf{u}}$ is to compare it
with a new estimation method based on the Bayesian composition of randomized
responses. In this paper, we refer to the estimator $\hat{\mathbf{u}}$ as the
”single-response” method, and the new method as the ”composition” method. In
the composition method, instead of querying an object with a single randomized
response, we perform a Bayesian composition by querying the object multiple
times. Each randomized response in the composition has a DP guarantee of
$\frac{\epsilon}{k}$. Similar to Eq. (75), the estimator of the original input
given a single response from $X$ is
$P^{-1}_{\frac{\epsilon}{k}}\mathbf{v}_{X}$, where
$P^{-1}{\frac{\epsilon}{k}}$ is the probability matrix of the
$\frac{\epsilon}{k}$-randomized response.

Suppose a Bayesian composition against the object $X$ yields $n$ responses,
denoted as $\mathbf{v}_{X,1},\mathbf{v}_{X,2},...,\mathbf{v}_{X,n}$. The
estimator $\hat{\mathbf{u}}_{c}(X)$ of the original value of $X$ based on the
composition is then given by:

$\hat{\mathbf{u}}_{c}(X)=\frac{1}{n}\sum\limits_{1\leq i\leq
n}P^{-1}_{\frac{\epsilon}{k}}\mathbf{v}_{X,i}.$ (81)

Consequently, the estimator $\hat{\mathbf{u}}_{c}$ for the queried objects is
obtained as $\hat{\mathbf{u}}_{c}=\sum_{X}\hat{\mathbf{u}}_{c}(X)$.

Now, let’s compare the covariance of the single-response and composition
methods. For both methods, the covariance of the estimator is the sum of the
covariance of the estimators for individual objects. Therefore, we just need
to compare the covariance of $\hat{\mathbf{u}}(X)$ with
$\hat{\mathbf{u}}_{c}(X)$. Let’s derive the covariance of
$\hat{\mathbf{u}}_{c}(X)$. Assuming $n$ is a constant, we have:

$Cov(\hat{\mathbf{u}}_{c}(X))=\frac{1}{n^{2}}\sum\limits_{1\leq i\leq
n}Cov(P^{-1}_{\frac{\epsilon}{k}}\mathbf{v}_{X,i}).$ (82)

Eq. (80) shows that
$Cov(P^{-1}_{\frac{\epsilon}{k}}\mathbf{v}_{X,i})\propto\frac{k^{2}}{\epsilon^{2}}$,
so we have:

$Cov(\hat{\mathbf{u}}_{c}(X))\propto\frac{1}{n^{2}}\sum\limits_{1\leq i\leq
n}\frac{k^{2}}{\epsilon^{2}}=\frac{k^{2}}{\epsilon^{2}n}.$ (83)

The number of queries $n$ returned by a Bayesian composition is also a random
variable. Thus, we can write:

$Cov(\hat{\mathbf{u}}_{c}(X))\propto\sum\limits_{n}Pr(n)\frac{k^{2}}{n\epsilon^{2}}=\frac{k^{2}}{\epsilon^{2}}E[\frac{1}{n}]$
(84)

Given $n\in\mathbb{N}^{+}$ and applying Jensen’s inequality, we have
$E[\frac{1}{n}]\geq\frac{1}{E[n]}$. Additionally, Corollary D.2 shows that
$E[n]\rightarrow k^{2}$, when the total budget $\epsilon$ is small enough.
Hence, we obtain

$\lfloor
Cov(\hat{\mathbf{u}}_{c}(X))\rfloor\propto\frac{k^{2}}{\epsilon^{2}}\frac{1}{E[n]}=\frac{1}{\epsilon^{2}},$
(85)

where $\lfloor Cov(\hat{\mathbf{u}}_{c}(X))\rfloor$ denotes the lower bound of
$Cov(\hat{\mathbf{u}}_{c}(X))$. Notice that
$Cov(\hat{\mathbf{u}}(X))\propto\frac{1}{\epsilon^{2}}$. Therefore, we have:

######  Theorem E.2.

When $m=2$ and total privacy budget $\epsilon$ is small enough, using a single
randomized response has smaller variance than using a Bayesian composition
when estimating the histogram of queried objects.

Now, we will discuss the case where $m>2$. Substituting
$Cov(\hat{\mathbf{u}}(X))\propto\frac{1}{\epsilon^{2}}$ into Eq. (85) and
reorganizing, we have:

$\frac{\lfloor
Cov(\hat{\mathbf{u}}_{c}(X))\rfloor}{Cov(\hat{\mathbf{u}}(X))}=\frac{k^{2}}{E[n]}.$
(86)

If $\frac{k^{2}}{E[n]}\geq 1$, then the single-response method is still
preferred. Similar to Section D, we computed $\frac{k^{2}}{E[n]}$ for
different parameter $k$ and the size of data universe $m$, where $k$ ranges
from 1 to 10 and $m$ ranges from 3 to 5. The total privacy budget $\epsilon$
is fixed as one. The results are shown in Fig. 4.

Figure 4: $\frac{k^{2}}{E[n]}$ vs $k$ and $m$. The total privacy budget
$\epsilon$ is set to one.

All the data points in the graph demonstrate that $\frac{k^{2}}{E[n]}\geq 1$
is always true. Therefore, we have the following conjecture:

######  Conjecture E.1.

When estimating the histogram of queried objects, using a single randomized
response against an object is always preferred than using a Bayesian
composition.

regression | $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | intercept
---|---|---|---|---|---
heart disease | -0.059 | -1.456 | -0.0134 | 0 | 6.177
stroke | 0.0761 | 0.0952 | 0 | 0.0163 | -7.989
sleep | 0.0855 | 0.4617 | -0.07 | 0 | 12.323
diabetes | 0.0491 | 0 | -0.0091 | 0.1039 | -5.07
TABLE I: The parameters of the health-checkup-data regressions

##  Appendix F Realized Privacy Loss of Regressions against Health Checkup
Data

A group of individuals possesses health checkup data, including age ($x_{1}$),
sex ($x_{2}$), blood pressure ($x_{3}$), and BMI ($x_{4}$). Logistic
regressions are trained from [36, 37, 38] to predict the probability of
individuals having heart disease, stroke, and diabetes, while a linear
regression is trained from [39] to predict sleep duration. Table I outlines
the parameters of these regressions.

To ensure privacy, the regressions adhere to LDP guarantee, as outlined in
Sections 2.4 and 5. Logistic regressions are discretized to output 0 or 1, and
the linear regression for sleep duration is truncated to output 0 or 12. Input
data ranges are derived from public datasets: age assumed to range from 10 to
100; sex categorized as 0 (female) or 1 (male); blood pressure varying between
50 and 200; and BMI spanning from 10 to 50. Employing the branch-and-bound
method (Section 5.4), the realized privacy loss of these four regressions is
computed for all possible outputs as follows:

$o_{1}$ | $o_{2}$ | $o_{3}$ | $o_{4}$ | realized privacy loss
---|---|---|---|---
0 | 0 | 0 | 0 | 2.4639
0 | 0 | 0 | 1 | 2.4084
0 | 0 | 12 | 0 | 1.8036
0 | 0 | 12 | 1 | 2.7253
0 | 1 | 0 | 0 | 2.6865
0 | 1 | 0 | 1 | 3.1550
0 | 1 | 12 | 0 | 2.4642
0 | 1 | 12 | 1 | 3.7449
1 | 0 | 0 | 0 | 3.4761
1 | 0 | 0 | 1 | 2.2610
1 | 0 | 12 | 0 | 2.7511
1 | 0 | 12 | 1 | 2.1975
1 | 1 | 0 | 0 | 2.3362
1 | 1 | 0 | 1 | 1.6863
1 | 1 | 12 | 0 | 1.9062
1 | 1 | 12 | 1 | 2.4959

where $o_{1},o_{2},o_{3},o_{4}$ denote the outputs of the regressions of heart
disease, stroke, sleep duration, and diabetes, respectively.