# Differential Privacy with Multiple Selections††thanks: Authors are listed in
alphabetical order.

Ashish Goel
Stanford University
<EMAIL_ADDRESS>Zhihao Jiang
Stanford University
<EMAIL_ADDRESS>Aleksandra Korolova
Princeton University
<EMAIL_ADDRESS>
Kamesh Munagala
Duke University
<EMAIL_ADDRESS>Sahasrajit Sarmasarkar
Stanford University
<EMAIL_ADDRESS>
###### Abstract

We consider the setting where a user with sensitive features wishes to obtain
a recommendation from a server in a differentially private fashion. We propose
a “multi-selection” architecture where the server can send back multiple
recommendations and the user chooses one from these that matches best with
their private features. When the user feature is one-dimensional – on an
infinite line – and the accuracy measure is defined w.r.t some increasing
function $\mathfrak{h}(.)$ of the distance on the line, we precisely
characterize the optimal mechanism that satisfies differential privacy. The
specification of the optimal mechanism includes both the distribution of the
noise that the user adds to its private value, and the algorithm used by the
server to determine the set of results to send back as a response and further
show that Laplace is an optimal noise distribution. We further show that this
optimal mechanism results in an error that is inversely proportional to the
number of results returned when the function $\mathfrak{h}(.)$ is the identity
function.

##  1 Introduction

Consider a user who wants to issue a query to an online server (e.g. to
retrieve a search result or an advertisement), but the query itself reveals
private information about the use. One commonly studied approach to protect
user privacy from the server in this context is for the user to send a
perturbed query, satisfying differential privacy under the local trust model
[14]. However, since the query itself is changed from the original, the server
may not be able to return a result that is very accurate for the original
query. Our key observation is that in many situations such as search or
content recommendations, the server is free to return many results, and the
user can choose the one that is the most appropriate, without revealing the
choice to the server. In fact, if the server also returns a model for
evaluating the quality of these results for the user, then this choice can be
made by a software intermediary such as a client running on the user’s device.
This software intermediary can also be the one that acts as the user’s privacy
delegate and is the one ensuring the local differential privacy protection.

We call this, new for the differential privacy (DP) literature system
architecture, the “Multi-Selection” approach to privacy, and the key question
we ask is: What is the precise trade-off that can be achieved between the
number of returned results and quality under a fixed privacy goal? Of course,
had the server simply returned all possible results, there would have been no
loss in quality since the client could choose the optimal result. However,
this approach is infeasible due to computation and communication costs, as
well as due to potential server interest in not revealing proprietary
information. We therefore restrict the server to return $k$ results for small
$k$, and study the trade-off between $k$ and the quality when the client sends
privacy-preserving queries. Our algorithmic design space consists of choosing
the client’s algorithm and the server’s algorithm, as well as the space of
signals they will be sending.

At a high level, in addition to the novel multi-selection framework for
differential privacy, our main contributions are two-fold. First, under
natural assumptions on the privacy model and the latent space of results and
users, we show a tight trade-off between utility and number of returned
results via a natural (yet a priori non-obvious) algorithm, with the error
perceived by a user decreasing as $\Theta(1/k)$ for $k$ results. Secondly, at
a technical level, our proof of optimality is via a dual fitting argument and
is quite subtle, requiring us to develop a novel duality framework for linear
programs over infinite dimensional function spaces, with constraints on both
derivatives and integrals of the variables. This framework may be of
independent interest for other applications where such linear programs arise.

###  1.1 System Architecture and Definitions

We denote the set of users by $\mathbb{R}$ and when we refer to a user
$u\in\mathbb{R}$, we mean a user with a query value $u\in\mathbb{R}$. Let $M$
denote the set of results and $\text{OPT}:\mathbb{R}\rightarrow M$ denotes the
function which maps user queries to optimal results. This function OPT is
available (known) to the server but is unknown to the users.

####  1.1.1 Privacy

We adopt a well-studied notion of differential privacy under the local trust
model [14]:

######  Definition 1.1 (adapted from [25, 43]).

Let $\epsilon>0$ be a desired level of privacy and let $\mathcal{U}$ be a set
of input data and $\mathcal{Y}$ be the set of all possible responses and
$\Delta(\mathcal{Y})$ be the set of all probability distributions (over a
sufficiently rich $\sigma$-algebra of $\mathcal{Y}$ given by
$\sigma(\mathcal{Y})$). A mechanism
$Q:\mathcal{U}\rightarrow\Delta(\mathcal{Y})$ is $\epsilon$-differentially
private if for all $S\in\sigma(\mathcal{Y})$ and $u_{1},u_{2}\in\mathcal{U}$:

$\mathbb{P}(Qu_{1}\in S)\leq e^{\epsilon}\mathbb{P}(Qu_{2}\in S).$

A popular relaxation of differential privacy is geographic differential
privacy [4] (GDP), which allows the privacy guarantee to decay with the
distance between user values. It reflects the intuition that the user is more
interested in protecting the specifics of a medical query they are posing
rather than protecting whether they are posing a medical query or an
entertainment query, and is thus, appropriate in scenarios such as search. We
restate the formal definition from [43] and use it in the rest of the work.

######  Definition 1.2 (adapted from [43]).

Let $\epsilon>0$ be a desired level of privacy and let $\mathcal{U}$ be a set
of input data and $\mathcal{Y}$ be the set of all possible responses and
$\Delta(\mathcal{Y})$ be the set of all probability distributions (over a
sufficiently rich $\sigma$-algebra of $\mathcal{Y}$ given by
$\sigma(\mathcal{Y})$). A mechanism
$Q:\mathcal{U}\rightarrow\Delta(\mathcal{Y})$ is $\epsilon$-geographic
differentially private if for all $S\in\sigma(\mathcal{Y})$ and
$u_{1},u_{2}\in\mathcal{U}$:

$\mathbb{P}(Qu_{1}\in S)\leq e^{\epsilon|u_{1}-u_{2}|}\mathbb{P}(Qu_{2}\in
S).$

####  1.1.2 “Multi-Selection” Architecture

Our “multi-selection” system architecture (shown in Figure 1) relies on the
server returning a small set of results in response to the privatized user
input, with the on-device software intermediary deciding, unbeknownst to the
server, which of these server responses to use.

User SideUserAgent e.g. browserServer SideResult Computation$u\in$best in
a$s(\in Z)\sim P_{u}$$\textbf{a}(\in M^{k})\sim Q_{s}$ Figure 1: Overall
architecture for multi-selection.

The space of mechanisms we consider in this new architecture consists of a
triplet $(Z,\mathbf{P},\mathbf{Q})$:

  1. 1.

A set of signals $Z$ that can be sent by users.

  2. 2.

The actions of users, $\mathbf{P}$, which involves a user sampling a signal
from a distribution over signals. We use $P_{u}$ for $u\in\mathbb{R}$ to
denote the distribution of the signals sent by user $u$ which is supported on
$Z$. The set of actions over all users is given by
$\mathbf{P}=\\{P_{u}\\}_{u\in\real}$.

  3. 3.

The distribution over actions of the server, $\mathbf{Q}$. When the server
receives a signal $s\in Z$, it responds with $Q_{s}$, which characterizes the
distribution of the $k$ results that the server sends (it is supported in
$M^{k}$). We denote the set of all such server actions by
$\mathbf{Q}=\\{Q_{s}\\}_{s\in Z}$. 111We treat this distribution to supported
on $U^{k}$ instead of $k$-sized subset of $U$ for ease of mathematical
typesetting.

Our central question is to find the triplet over $(Z,\mathbf{P},\mathbf{Q})$
that satisfies $\epsilon$-geographic differential privacy constraints on
$\mathbf{P}$ while ensuring the best-possible utility or the smallest-possible
disutility.

####  1.1.3 The disutility model: Measuring the cost of privacy

We now define the disutility of a user $u\in\mathbb{R}$ from a result $m\in
M$. One natural definition would be to look at the difference between (or the
ratio) of the cost of the optimum result for $u$ and the cost of the result
$m$ returned by a privacy-preserving algorithm. However, we are looking for a
general framework, and do not want to presume that this cost measure is known
to the algorithm designer, or indeed, that it even exists. Hence, we will
instead define the disutility of $u$ as the amount by which $u$ would have to
be perturbed for the returned result $m$ to become optimum; this only requires
a distance measure in the space in which $u$ resides, which is needed for the
definition of the privacy guarantees anyway. For additional generality, we
will also allow the disutility to be any increasing function of this
perturbation, as defined below.

######  Definition 1.3.

The dis-utility of a user $u\in\mathbb{R}$ from a result $m\in M$ w.r.t some
continuously increasing function $\mathfrak{h}(.)$ is given by 222If no such
$u^{\prime}$ exists then the dis-utility is $\infty$ as infimum of a null set
is $\infty$.

${}\text{Dis-
util}^{\mathfrak{h}(.)}(u,m):=\inf\limits_{u^{\prime}\in\mathbb{R}:OPT(u^{\prime})=m}\mathfrak{h}(|u-u^{\prime}|)$
(1)

We allow any function $\mathfrak{h}(.)$ that satisfies the following
conditions:

$\mathfrak{h}(.)$ is a continuously increasing function satisfying
$\mathfrak{h}(0)=0$. (2) There exists $\mathcal{B}\in{}^{+}$ s.t.
$\log\mathfrak{h}(.)$ is Lipschitz continuous in $[\mathcal{B},\infty)$ (3)

The first condition (2) captures the intuition that dis-utility for the
optimal result is zero. The second condition (3) which bounds the growth of
$\mathfrak{h}(.)$ by an exponential function is (a not very restrictive
condition) required for our mathematical analysis.

Quite surprisingly, to show that our multi-selection framework provides a good
trade-off in the above model for every $\mathfrak{h}$ as defined above, we
only need to consider the case where the $\mathfrak{h}$ is the identity
function. The following example further motivates our choice of the disutility
measure:

######  Example 1.

Suppose, one assumes that the result set $M$ and the user set are embedded in
the same metric space $(d,M\cup\real)$. This setup is similar to the framework
studied in the examination of metric distortion of ordinal rankings in social
choice [5, 20, 38, 42]. Using triangle inequality, one may argue that
$d(u,m^{\prime})-d(u,m)\leq 2d(u,u^{\prime})$ where $m$ is the optimal result
for user $u$ (i.e. $m=\operatorname*{arg\,min}\limits_{m\in M}d(u,m)$) and
$m^{\prime}$ is the optimal result for user $u^{\prime}$. 333This follows
since $d(u,m^{\prime})-d(u,u^{\prime})\leq d(u^{\prime},m^{\prime})\leq
d(u^{\prime},m)\leq d(u,u^{\prime})+d(u,m)$ Thus, $2d(u,u^{\prime})$ gives an
upper bound on the disutility of user $u$ from result
$\text{OPT}(u^{\prime})$.

####  1.1.4 Restricting users and results to the same set

For ease of exposition, we study a simplified setup restricting the users and
results to the same set . Specifically, since $\text{Dis-
util}^{\mathfrak{h}(.)}(u,\text{OPT}(u^{\prime}))\leq\mathfrak{h}(|u-u^{\prime}|)$,
our simplified setup restricts the users and results to the same set where the
dis-utility of user $u\in\real$ from a result $a\in\real$ is given by
$\mathfrak{h}(|u-a|)$. Our results will extend to the model where the users
and results lie in different sets, and we refer the reader to Appendix A.5 for
the treatment. We note that even in the simplified setup, while we use
$a\in\real$ to denote the result, what we mean is that the server sends back
$\text{OPT}(a)\in M$.

####  1.1.5 Definition of the cost function in the simplified setup

We use $\texttt{Set}(\textbf{a})$ to convert a vector
$\textbf{a}=(a_{1},a_{2},\ldots,a_{k})^{T}\in{}^{k}$ to a set of at most $k$
elements, formally $\texttt{Set}(\textbf{a})=\\{a_{i}:i\in[k]\\}$.

Recall from Section 1.1.4, the dis-utility of user $u\in\real$ from a result
$a\in\real$ in the simplified setup may be written as

${}\text{Dis-util}^{\mathfrak{h}(.)}_{sim}(u,a)=\mathfrak{h}(|u-a|)$ (4)

Since we restrict the users and results to the same set, $Q_{s}$ is supported
on k for every $s\in Z$. Thus, the cost for a user $u$ from the mechanism
$(Z,\mathbf{P},\mathbf{Q})$ is given by

$\displaystyle{}\text{cost}^{\mathfrak{h}(.)}(u,(Z,\mathbf{P},\mathbf{Q}))$
$\displaystyle=\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\text{Dis-
util}^{\mathfrak{h}(.)}_{sim}(u,a)\right]\right]$ (5)
$\displaystyle=\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right],$
(6)

where the expectation is taken over the randomness in the action of user and
the server.

We now define the cost of a mechanism by supremizing444We write supremum
instead of maximum as the maximum over an infinite set may not always be
defined. over all users $u\in\real$. Since, we refrain from making any
distributional assumptions over the users, supremization rather than mean over
the users is the logical choice.

${}\text{cost}^{\mathfrak{h}(.)}(Z,\mathbf{P},\mathbf{Q}):=\sup_{u\in\mathbb{R}}\text{cost}^{\mathfrak{h}(.)}(u,(Z,\mathbf{P},\mathbf{Q}))=\sup_{u\in\mathbb{R}}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right]$
(7)

We use $\mathds{1}(.)$ to denote the identity function, i.e. $\mathds{1}(x)=x$
for every $x\in\real$ and thus define the cost function when $\mathfrak{h}(.)$
is an identity function as follows:

${}\text{cost}^{\mathds{1}(.)}(Z,\mathbf{P},\mathbf{Q}):=\sup_{u\in\mathbb{R}}\text{cost}^{\mathds{1}(.)}(u,(Z,\mathbf{P},\mathbf{Q}))=\sup_{u\in\mathbb{R}}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}|u-a|\right]\right]$ (8)

Recall our central question is to find the triplet over
$(Z,\mathbf{P},\mathbf{Q})$ that ensures the smallest possible disutility /
cost while ensuring that $\mathbf{P}$ satisfies $\epsilon$-geographic
differential privacy. We denote the value of this cost by
$f^{\mathfrak{h}(.)}(\epsilon,k)$ and it is formally defined as

$\displaystyle{}f^{\mathfrak{h}(.)}(\epsilon,k):=$
$\displaystyle\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\end{subarray}}\inf_{\mathbf{Q}\in\mathcal{Q}_{Z}}\left(\text{cost}^{\mathfrak{h}(.)}(Z,\mathbf{P},\mathbf{Q})\right)$
$\displaystyle=$
$\displaystyle\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\end{subarray}}\inf_{\mathbf{Q}\in\mathcal{Q}_{Z}}\left(\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right]\right)\text{where}$
(9)

$\mathcal{P}^{(\epsilon)}_{Z}:=\\{\mathbf{P}|\forall
u\in\real,P_{u}\text{~{}is a distribution on $Z$,}\text{~{}and $\mathbf{P}$
satisfies $\epsilon$-geographic differential privacy.}\\}$.

$\mathcal{Q}_{Z}:=\\{\mathbf{Q}|\forall s\in Z,Q_{s}\text{~{}is a distribution
on ${}^{k}$}\\}$.

###  1.2 Our results and key technical contributions

For any $\mathfrak{h}(.)$ satisfying equations (2) and (3) when the privacy
goal is $\epsilon$-geographic DP our main results are:

  * •

The optimal action $P_{u}$ for a user $u$, is to add Laplace noise555We use
$\mathcal{L}_{\epsilon}(u)$ to denote a Laplace distribution of scale
$\frac{1}{\epsilon}$ centred at $u$. Formally, a distribution
$X\sim\mathcal{L}_{\epsilon}(u)$ has its probability density function given by
$f_{X}(x)=\frac{\epsilon}{2}e^{-\epsilon|x-u|}$. of scale $\frac{1}{\epsilon}$
to its value $u$ (result stated in Theorem 2.13 and proof sketch described in
Sections 2.1, 2.2 and 2.3). Further, we emphasize that the optimality of
adding Laplace noise is far from obvious666In fact, only a few optimal DP
mechanisms are known [37, 40, 41, 24], and it is known that for certain
scenarios, universally optimal mechanisms do not exist [18].. For instance,
when users and results are located on a ring, Laplace noise is not optimal
(see Appendix A.4 for an analysis when $k=2$).

  * •

The optimal server response $\mathbf{Q}$ could be different based on different
$\mathfrak{h}$. We give a recursive construction of $\mathbf{Q}$ for a general
$\mathfrak{h}$ (Section 2.4). Furthermore, when $\mathfrak{h}(t)=t$, we give
an exact construction of $\mathbf{Q}$ (sketched in Fig. 2 for $k=5$) and show
that $f^{\mathds{1}(.)}(\epsilon,k)=O(\frac{1}{\epsilon k})$ in Section 2.4
and Appendix B.5.

Formally, our main results can be stated as:

######  Theorem 1.4 (corresponds to Theorem 2.13 and Theorem B.3).

For $\epsilon$-geographic differential privacy, adding Laplace noise, that is,
user $u$ sends a signal drawn from distribution $\mathcal{L}_{\epsilon}(u)$,
is one of the optimal choices of $\mathcal{P}^{(\epsilon)}_{Z}$ for users.
Further, when $\mathfrak{h}(t)=t$, we have
$f^{\mathds{1}(.)}(\epsilon,k)=O(\frac{1}{\epsilon k})$ and the optimal
mechanism $(Z,\mathbf{P},\mathbf{Q})$ (choice of actions of users and server)
itself can be computed in closed form. For a generic $\mathfrak{h}(.)$, the
optimal server action $\mathbf{Q}$ may be computed recursively.

In addition to our overall framework and the tightness of the above theorem, a
key contribution of our work is in the techniques developed. At a high level,
our proof proceeds via constructing an infinite dimensional linear program to
encode the optimal algorithm under differential privacy constraints. We then
use dual fitting to show the optimality of Laplace noise. Finally, the optimal
set of results being computable by a simple dynamic program given such noise.

The technical hurdles arise because the linear program for encoding the
optimal mechanism is over infinite-dimensional function spaces with linear
constraints on both derivatives and integrals, since the privacy constraint
translates to constraints on the derivative of the density encoding the
optimal mechanism, while capturing the density itself requires an integral. We
call it Differential Integral Linear Program (DILP); see Section 2.2. However,
there is no weak duality theory for such linear programs in infinite
dimensional function spaces, such results only existing for linear programs
with integral constraints [3].

We therefore develop a weak duality theory for DILPs (see Section 2.2 with a
detailed proof in Appendix B.6), which to the best of our knowledge is novel.
The proof of this result is quite technical and involves a careful application
of Fatou’s lemma [49] and the monotone convergence theorem to interchange
integrals with limits, and integration by parts to translate the derivative
constraints on the primal variables to derivatives constraint on the dual
variables.

We believe our weak duality framework is of independent interest and has
broader implications beyond differential privacy; see Appendix A.8 for two
such applications.

Figure 2: Optimal mechanisms in geographic differential privacy setting when
$k=5$ and $\epsilon\in\\{0.3,0.5,1.0\\}$. Suppose the user has a private value
$u$. Then the user sends a signal $s$ drawn from distribution
$\mathcal{L}_{\epsilon}(u)$ to the server, meaning the user sends $s=v+x$
where $x$ is drawn from the density function $\rho(t)$ in this figure. Suppose
the server receives $s$. Then the server responds $\\{s+a_{1},...,s+a_{5}\\}$,
where the values of $a_{1},a_{2},...,a_{5}$ are the $t$-axis values of dots on
the density functions.

###  1.3 Related Work

####  1.3.1 Differential Privacy

The notion of differential privacy in the trusted curator model is introduced
in [26]; see [28] for a survey of foundational results in this model. The idea
of local differential privacy dates back to [53], and the algorithms for
satisfying it have been studied extensively following the deployment of DP in
this model by Google [30] and Apple [6]; see, e.g. [19, 21, 52, 12] and
Bebensee [14] for a survey. Geographic differential privacy was introduced by
Andrés  _et al._ [4] and has gained widespread adoption for anonymizing
location data. Our use of geographic DP utilizes the definition of [4] with
the trust assumptions of the local model, and is thus, only a slight
relaxation of the traditional local model of differential privacy.

####  1.3.2 Multi-Selection

An architecture for multi-selection, particularly with the goal of privacy-
preserving advertising, was already introduced in Adnostic by [50]. Their
proposal was to have a browser extension that would run the targeting and ad
selection on the user’s behalf, reporting to the server only click information
using cryptographic techniques. Similarly, Privad by [39] propose to use an
anonymizing proxy that operates between the client that sends broad interest
categories to the proxy and the advertising broker, that transmits all ads
matching the broad categories, with the client making appropriate selections
from those ads locally. Although both Adnostic and Privad reason about the
privacy properties of their proposed systems, unlike our work, neither
provides DP guarantees.

Two lines of work in the DP literature can be seen as somewhat related to the
multi-selection paradigm – the exponential mechanism (see e.g. [46, 17, 45])
and amplification by shuffling (see e.g. [29, 22, 32]). The exponential
mechanism focuses on high-utility private selection from multiple alternatives
and is usually deployed in the TCM model. Amplification by shuffling analyzes
the improvement in the DP guarantees that can be achieved if the locally
privatized data is shuffled by an entity before being shared with the server.
As far as we are aware, neither of the results from these lines of work can be
directly applied to our version of multi-selection, although combining them is
an interesting avenue for future work.

More broadly, several additional directions within DP research can be viewed
as exploring novel system architectures in order to improve privacy-utility
trade-offs, e.g., using public data to augment private training [47, 11],
combining data from TCM and LM models [8, 7, 15], and others. Our proposed
architecture is distinct from all of these. Finally, our work is different
from how privacy is applied in federated learning [36] – there, the goal is
for a centralized entity to be able to build a machine learning model based on
distributed data; whereas our goal is to enable personalized, privacy-
preserving retrieval from a global ML model.

####  1.3.3 Optimal DP mechanisms

To some extent, much of the work in DP can be viewed as searching for the
optimal DP mechanism, i.e. one that would achieve the best possible utility
given a fixed desired DP level. Only a few optimal mechanisms are known [37,
40, 41, 24], and it is known that for certain scenarios, universally optimal
mechanisms do not exist [18].

Most closely related to our work is the foundational work of [37] that derives
the optimal mechanism for counting queries via a linear programming
formulation; the optimal mechanism turns out to be the discrete version of the
Laplace mechanism. Its continuous version was studied in [33], where the
Laplace mechanism was shown to be optimal. These works focused on the trusted
curator model of differential privacy unlike the local trust model which we
study.

In the local model, [43] show Laplace noise to be optimal for
$\epsilon$-geographic DP. Their proof relies on formulating an infinite
dimensional linear program over noise distributions and looking at its dual.
Although their proof technique bears a slight resemblance to ours, our proof
is different and intricate since it involves the minimisation over the set of
returned results in the cost function.

A variation of local DP is considered in [35], in which DP constraints are
imposed only when the distance between two users is smaller than a threshold.
For that setting, the optimal noise is piece-wise constant, which is a similar
outcome to our optimal Laplace noise distribution. However, our setting of
choosing from multiple options makes the problems very different.

####  1.3.4 Related work on duality theory for infinite dimensional LPs

Strong duality is known to hold for finite dimensional linear programs [1].
However, for infinite dimensional linear programs, strong duality may not
always hold (see [3] for a survey). Sufficient conditions for strong duality
are presented and discussed in [51, 13] for generalized vector spaces. A class
of linear programs (called SCLPs) over bounded measurable function spaces have
been studied in [48, 16] with integral constraints on the functions. However,
these works do not consider the case with derivative constraints on the
functional variables. In [43, Equation 7] a linear program with derivative and
integral constraints (DILPs) is formulated to show the optimality of Laplace
noise for geographic differential privacy. However, their duality result does
not directly generalize to our case since our objective function and
constraints are far more complex as it involves minimisation over a set of
results.

We thus need to reprove the weak-duality theorem for our DILPs, the proof of
which is technical and involves a careful application of integration by parts
to translate the derivative constraint on the primal variable to a derivative
constraint on the dual variable. Further, we require a careful application of
Fatou’s lemma [49] and monotone convergence theorem to exchange limits and
integrals. Our weak duality result generalizes beyond our specific example and
is applicable to a broader class of DILPs. Furthermore, we discuss two
problems (one from job scheduling [2] and one from control theory [31]) in
Appendix A.8 which may be formulated as a DILP.

##  2 Characterizing the Optimal Mechanism: Proof Sketch of Theorem 1.4

We now present a sketch of the proof of Theorem 1.4; the full proof involving
the many technical details is presented in the Appendix. We first show that
for the sake of analysis, the server can be removed by making the signal set
coincide with result sets (Section 2.1) assuming that the function OPT is
publicly known both to the user and server.777One should note that this
removal is just for analysis and the server is needed since the OPT function
is unknown to the user. Then in Section 2.2 we construct a primal linear
program $\mathcal{O}$ for encoding the optimal mechanism, and show that it
falls in a class of infinite dimensional linear programs that we call DILPs,
as defined below.

######  Definition 2.1.

Differential-integral linear program (DILP) is a linear program over Riemann
integrable function spaces involving constraints on both derivatives and
integrals.

A simple example is given in Equation (10). Observe that in equation (10), we
define $\mathcal{C}_{1}$ to be a continuously differentiable function.

${}\text{\Large{$\tilde{\mathcal{O}}=$} }\left\\{\begin{aligned}
\inf_{g(.):\mathcal{C}^{1}(\mathbb{R}\rightarrow\mathbb{R}^{+})}&\int_{\mathbb{R}}|v|g(v)dv\\\
\textrm{s.t.}\quad&\int_{\mathbb{R}}g(v)dv=1\\\ &-\epsilon g(v)\leq
g^{\prime}(v)\leq\epsilon g(v)\text{ }\forall
v\in\mathbb{R}\end{aligned}\right.$ (10)

We next construct a dual DILP formulation $\mathcal{E}$ in Section 2.2, and
show that the formulation satisfies weak duality. As mentioned before, this is
the most technically intricate result since we need to develop a duality
theory for DILPs. We relegate the details of the proof here to the Appendix.

Next, in Section 2.3, we show the optimality of the Laplace noise mechanism
via dual-fitting, i.e., by constructing a feasible solution to DILP
$\mathcal{E}$ with objective identical to that of the Laplace noise mechanism.
Finally, in Section 2.4, we show how to find the optimal set of $k$ results
given Laplace noise. We give a construction for general functions
$\mathfrak{h}(.)$ as well as a closed form for the canonical case of
$\mathfrak{h}(t)=t$. This establishes the error bound and concludes the proof
of Theorem 1.4.

###  2.1 Restricting the signal set $Z$ to $\mathbb{R}^{k}$

We first show that it is sufficient to consider a more simplified setup where
the user sends a signal set in k and the server sends back the results
corresponding to the signal set. Since we assumed users and ads lie in the
same set, for the purpose of analysis, this removes the server from the
picture. To see this, note that for the setting discussed in Section 1.1.4,
the optimal result for user $u$ is the result $u$ itself, where when we refer
to “result $u$”, we refer to the result $\text{OPT}(u)\in M$.

Thus, this approach is used only for a simplified analysis as the OPT function
is not known to the user and our final mechanism will actually split the
computation between the user and the server.

Therefore a user can draw a result set directly from the distribution over the
server’s action and send the set as the signal. The server returns the
received signal, hence removing it from the picture. In other words, it is
sufficient to consider mechanisms in $\mathcal{P}^{(\epsilon)}_{{}^{k}}$,
which are in the following form (corresponding to Theorem 2.2).

  1. 1.

User $v\in\real$ reports $s$ that is drawn from a distribution $P_{v}$ over k.

  2. 2.

The server receives $s$ and returns $s$.

We give an example to illustrate this statement below.

######  Example 2.

Fix a user $u$ and let $Z=\\{s_{1},s_{2}\\}$ and
$\\{\textbf{a}^{(1)},\textbf{a}^{(2)}\\}\subseteq\mathbb{R}^{k}$ and consider
a mechanism $\mathcal{M}_{1}$ where user $u$ sends $s_{1}$ and $s_{2}$ with
equal probability. The server returns $\textbf{a}\in{}^{k}$ on receiving
signal $s$, with the following probability.

$\displaystyle\operatorname{\mathbb{P}}\left(\textbf{a}=\textbf{a}^{(1)}|s=s_{1}\right)=0.2,\quad\operatorname{\mathbb{P}}\left(\textbf{a}=\textbf{a}^{(2)}|s=s_{1}\right)=0.8,$
$\displaystyle\operatorname{\mathbb{P}}\left(\textbf{a}=\textbf{a}^{(1)}|s=s_{2}\right)=0.4,\quad\operatorname{\mathbb{P}}\left(\textbf{a}=\textbf{a}^{(2)}|s=s_{2}\right)=0.6.$

Then the probability that $u$ receives $\textbf{a}^{(1)}$ is 0.3 and it
receives $\textbf{a}^{(2)}$ is 0.7. Now consider another mechanism
$\mathcal{M}_{2}$ with the same cost satisfying differential privacy
constraints, where $Z=\\{\textbf{a}^{(1)},\textbf{a}^{(2)}\\}$, with user $u$
sending signal $\textbf{a}^{(1)}$ and $\textbf{a}^{(2)}$ with probabilities
0.3 and 0.7. When the server receives $\textbf{a}\in{}^{k}$, it returns a.

We show the new mechanism $\mathcal{M}_{2}$ satisfies differential privacy
assuming the original mechanism $\mathcal{M}_{1}$ satisfies it. As a result,
we can assume $Z={}^{k}$ when finding the optimal mechanism.

The following theorem states that it is sufficient to study a setup removing
the server from the picture and consider mechanisms in set of probability
distributions supported on k satisfying $\epsilon$-geographic differential
privacy ($\mathcal{P}^{(\epsilon)}_{{}^{k}}$ as defined in Section 1.1.5).

######  Theorem 2.2 (detailed proof in Appendix B.1).

It is sufficient to remove the server $(\mathbf{Q})$ from the cost function
$f^{\mathfrak{h}(.)}(\epsilon,k)$ and pretend the user has full-information.
Mathematically, it maybe stated as follows.

${}f^{\mathfrak{h}(.)}(\epsilon,k)=\inf_{\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{{}^{k}}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
P_{u}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right].$
(11)

###### Proof Sketch.

Fix
$Z,\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z},\mathbf{Q}\in\mathcal{Q}_{Z}$.
For $u\in\real$ and $S\subseteq{}^{k}$, let $\tilde{P}_{u}\left(S\right)$ be
the probability that the server returns a set in $S$ to user $u$. Then for any
$u_{1},u_{2}\in\real,S\subseteq{}^{k}$, we can show that
$\tilde{P}_{u_{1}}\left(S\right)\leq
e^{\epsilon\cdot|u_{1}-u_{2}|}\tilde{P}_{u_{2}}\left(S\right)$ using post-
processing theorem, and thus
$\tilde{\mathbf{P}}=\\{\tilde{P}_{u}\\}_{u\in\real}\in\mathcal{P}^{(\epsilon)}_{{}^{k}}$
because $\tilde{P}_{u}$ is a distribution on k for any $u\in\real$. At the
same time,

$\displaystyle\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim\mathbf{P}_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim\mathbf{Q}_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right]=\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim\tilde{P}_{u}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|))\right],\text{
so we have}$ $\displaystyle
f^{\mathfrak{h}(.)}(\epsilon,k)=\inf_{\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{{}^{k}}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
P_{u}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right],$

∎

###  2.2 Differential integral linear programs to represent $f(\epsilon,k)$
and a weak duality result

Recall the definition of DILP from Definition 2.1. In this section, we
construct an infimizing DILP $\mathcal{O}$ to represent the constraints and
the objective in the cost function $f(\epsilon,k)$. We then construct a dual
DILP $\mathcal{E}$, and provide some intuition for this formulation. The proof
of weak duality is our main technical result, and its proof is defered to the
Appendix.

####  2.2.1 Construction of DILP $\mathcal{O}$ to represent cost function
$f(\epsilon,k)$

We now define the cost of a mechanism $\mathbf{P}$ which overloads the cost
definition in Equation 7

######  Definition 2.3.

Cost of mechanism $\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$: We
define the cost of mechanism P as

${}\textit{cost}(\textbf{P}):=\sup_{u\in\mathbb{R}}\underset{\textbf{a}\sim
P_{u}}{\mathbb{E}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]$
(12)

Observe that in Definition 2.3 we just use $\mathbf{P}$ instead of the tuple
$(Z,\mathbf{P},\mathbf{Q})$ as in Equation (7). Observe that it is sufficient
to consider $\mathbf{P}$ in the cost since $\mathbf{P}$ simulates the entire
combined action of the user and the server as shown in Theorem 11 in Section
2.1. We now define the notion of approximation using cost of mechanism by a
sequence of mechanisms which is used in the construction of DILP
$\mathcal{O}$.

######  Definition 2.4.

Arbitrary cost approximation: We call mechanisms
$\textbf{P}^{(\eta)}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$ an arbitrary
cost approximation of mechanisms
$\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$ if
$\lim\limits_{\eta\to
0}\textit{cost}(\textbf{P}^{(\eta)})=\textit{cost}(\textbf{P})$

Now we define the DILP $\mathcal{O}$ to characterise ${f}(\epsilon,k)$ in
Equation (11). In this formulation, the variables are
$g(.,.):\mathcal{I}^{B}(\mathbb{R}\times\mathbb{R}^{k}\rightarrow\mathbb{R}^{+})$,
which we assume are non-negative Riemann integrable bounded functions. These
variables capture the density function $P_{u}$.

${}\text{ \Large{$\mathcal{O}=$}}\left\\{\begin{aligned}
\inf_{g(.,.):\mathcal{I}^{B}(\mathbb{R}\times\mathbb{R}^{k}\rightarrow\mathbb{R}^{+}),\kappa\in\mathbb{R}}\quad&\kappa\\\
\textrm{s.t.}\quad&\kappa-\int\limits_{\textbf{x}\in\mathbb{R}^{k}}\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\geq
0\text{ }\forall u\in\mathbb{R}\\\
&\int\limits_{\textbf{x}\in\mathbb{R}^{k}}g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)=1\text{
}\forall u\in\mathbb{R}\\\ &\epsilon
g(u,\textbf{x})+\underline{g}_{u}(u,\textbf{x})\geq 0;\text{ }\forall
u\in\mathbb{R};\textbf{x}\in\mathbb{R}^{k}\\\ &\epsilon
g(u,\textbf{x})-\overline{g}_{u}(u,\textbf{x})\geq 0;\text{ }\forall
u\in\mathbb{R};\textbf{x}\in\mathbb{R}^{k}\end{aligned}\right.$ (13)

In DILP $\mathcal{O}$, we define $\underline{g}_{u}(u,\textbf{x})$ and
$\overline{g}_{u}(u,\textbf{x})$ to be the lower and upper partial derivative
of $g(u,\textbf{x})$ at $u$. Now observe that, we use lower and upper
derivatives instead of directly using derivatives as the derivatives of a
probability density function may not always be defined (for example, the left
and right derivatives are unequal in the Laplace distribution at origin).

Note that the DILP $\mathcal{O}$ involves integrals and thus requires
mechanisms to have a valid probability density function, however not every
distribution is continuous, and, as a result, may not have a density function
(e.g. point mass distributions like $\hat{P}^{\mathcal{L}_{\epsilon}}_{u}$
defined in Definition 2.9). Using ideas from mollifier theory [34] we
construct mechanisms $\textbf{P}^{(\eta)}$ with a valid probability density
function that are an arbitrary good approximation of mechanism P in Lemma 2.7,
hence showing that it suffices to define $\mathcal{O}$ over bounded, non-
negative Reimann integrable functions $g$.

We now prove that the DILP constructed above captures the optimal mechanism,
in other words, $\text{opt}(\mathcal{O})=f(\epsilon,k)$.

######  Lemma 2.5.

Let $\text{opt}(\mathcal{O})$ denote the optimal value of DILP (13), then
$f(\epsilon,k)=\text{opt}(\mathcal{O})$.

To prove this lemma, we show Lemma 2.6, which relates the last two constraints
of the DILP $\mathcal{O}$ to $\epsilon$-geographic differential privacy, and
Lemma 2.7, which shows that an arbitrary cost approximation of mechanism P can
be constructed with valid probability density functions.

######  Lemma 2.6.

Let $P_{u}$ have a probability density function given by
$g(u,.):\mathbb{R}^{k}\rightarrow\mathbb{R}$ for every $u\in\mathbb{R}$. Then,
$\mathbf{P}$ satisfies $\epsilon$-geographic differential privacy iff
$\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)\leq\epsilon
g(u,\textbf{x})\text{ }\forall
u\in\mathbb{R};\forall\textbf{x}\in\mathbb{R}^{k}$
888$\underline{g}_{u}(u,\textbf{x})$, $\overline{g}_{u}(u,\textbf{x})$ denote
the lower and upper partial derivative w.r.t. $u$

The proof of this lemma (Appendix B.2.1) proceeds by showing that
$\epsilon$-geographic differential privacy is equivalent to Lipschitz
continuity of $\log g(u,\textbf{x})$ in $u$.999We handle the case when the
$\log$ is not defined as the density is zero at some point separately in the
proof.

######  Lemma 2.7.

(Proven in Appendix B.2.3) Given any mechanism
$\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\textbf{R}^{k}}$ (satisfying
$\epsilon$-geographic differential privacy), we can construct a sequence of
mechanisms $\textbf{P}^{(\eta)}$ with bounded probability density functions
such that $\textbf{P}^{(\eta)}$ is an arbitrary cost approximation of
mechanism $\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\textbf{R}^{k}}$.

Using Lemmas 2.7 and 2.6, we give the proof of Lemma 2.5.

###### Proof of Lemma 2.5.

Consider any $\zeta>0$. As established in Lemma 2.7, it follows for every
mechanism $\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\textbf{R}^{k}}$, we can
construct another mechanism $\textbf{P}^{(\eta)}$ with bounded probability
density functions whose cost is a $\zeta$ approximation of the cost of
mechanism P. Thus, we can use Lemma 2.6 to conclude that the optimum value of
DILP $\mathcal{O}$ is precisely $f(\epsilon,k)$. ∎

####  2.2.2 Dual DILP $\mathcal{E}$ and statement of weak duality theorem

Now, we write the dual of the DILP $\mathcal{O}$ as the DILP $\mathcal{E}$ in
Equation (14). Observe that, we have the constraint that $\delta(.)$ and
$\lambda(.)$ is non-negative, $\mathcal{C}^{0}$ (continuous) and $\nu(.,.)$ is
a $\mathcal{C}^{1}$ function i.e. $\nu(r,\textbf{v})$ is continuously
differentiable in $r$ and continuous in v. Thus, we may rewrite the equations
as

${}\text{\Large{$\mathcal{E}=$} }\left\\{\begin{aligned}
\sup_{\begin{subarray}{c}\delta(.),\lambda(.):\mathcal{C}^{0}(\mathbb{R}\rightarrow\mathbb{R}^{+});\\\
\nu(.,.):\mathcal{C}^{1}(\mathbb{R}\times(\mathbb{R})^{k}\rightarrow\mathbb{R})\end{subarray}}&\int_{r\in\mathbb{R}}\lambda(r)dr\\\
\textrm{s.t. }\quad&\int_{r\in\mathbb{R}}\delta(r)dr\leq 1\\\
&-\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]\delta(r)+\lambda(r)+\nu_{r}(r,\textbf{v})+\epsilon|\nu(r,\textbf{v})|\leq
0\text{ }\forall r\in\mathbb{R};\textbf{v}\in(\mathbb{R})^{k}\\\ &\exists
U:\mathcal{C}^{0}(\mathbb{R}^{k}\rightarrow\mathbb{R})\textrm{ s.t.
}\nu(r,\textbf{v})\geq 0\text{ }\forall r\geq U(\textbf{v})\text{
}\forall\textbf{v}\in(\mathbb{R})^{k}\\\ &\exists
L:\mathcal{C}^{0}(\mathbb{R}^{k}\rightarrow\mathbb{R})\textrm{ s.t.
}\nu(r,\textbf{v})\leq 0\text{ }\forall r\leq L(\textbf{v})\text{
}\forall\textbf{v}\in(\mathbb{R})^{k}\end{aligned}\right.$ (14)

To get intuition behind the construction of our dual DILP $\mathcal{E}$,
relate the equations in DILP $\mathcal{O}$ to the dual variables of DILP
$\mathcal{E}$ as follows. The first equation denoted by
$\\{\delta(r)\\}_{r\in\mathbb{R}}$, second equation denoted by
$\\{\lambda(r)\\}_{r\in\mathbb{R}}$ and the last two equations are jointly
denoted by
$\\{\nu(r,\textbf{v})\\}_{r\in\mathbb{R};\textbf{v}\in(\mathbb{R})^{k}}$
101010Note that the variable $\nu(r,\textbf{v})$ is constructed from the
difference of two non-negative variables corresponding to third and fourth
equations, respectively. The detailed proof is in Appendix B.6,.
The last two terms in the second constraint of DILP $\mathcal{E}$ are a
consequence of the last two equations on DILP $\mathcal{O}$ and observe that
it involves a derivative of the dual variable $\nu(u,\textbf{v})$. The linear
constraint on the derivative of the primal variable translates to a derivative
constraint on the dual variable by a careful application of integration by
parts, discussed in detail in Appendix B.6.

Observe that in our framework we have to prove the weak-duality result as, to
the best of our knowledge, existing duality of linear programs in infinite
dimensional spaces work for cases involving just integrals. The proof of this
Theorem 2.8 is technical and we defer the details to Appendix B.6.

######  Theorem 2.8.

$\text{opt}(\mathcal{O})\geq\text{opt}(\mathcal{E})$.

###  2.3 Dual fitting to show the optimality of Laplace noise addition

Before starting this section, we first define a function $\hat{f}(\epsilon,k)$
which characterises the optimal placement of $k$ points in to minimise the
expected minimum dis-utility among these $k$ points measured with respect to
some user $u$ sampled from a Laplace distribution. As we shall prove in
Theorem 2.10 that it bounds the cost of the Laplace noise addition mechanism.

${}\hat{f}(\epsilon,k)=\min_{\textbf{a}\in\mathbb{R}^{k}}\mathop{\operatorname{\mathbb{E}}}\limits_{y\sim\mathcal{L}_{\epsilon}(0)}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]$
(15)

In this section, we first define a mechanism in Definition 2.9 which simulates
the action of the server corresponding to the Laplace noise addition mechanism
in Section 2.3.1 and show that the cost of Laplace noise addition mechanism is
$\hat{f}(\epsilon,k)$. We finally show the optimality of Laplace noise
addition mechanism via dual fitting i.e. constructing a feasible solution to
the dual DILP $\mathcal{E}$ with an objective function $\hat{f}(\epsilon,k)$
in Section 2.3.2.

####  2.3.1 Bounding cost function $f(\epsilon,k)$ by the cost of Laplace
noise adding mechanism

We now define the mechanism
$\hat{\textbf{P}}^{\mathcal{L}_{\epsilon}}=\\{\hat{P}_{u}^{\mathcal{L}_{\epsilon}}\\}_{u\in\real}$
which corresponds to simulating the action of the server on receiving signal
$S_{u}\sim\mathcal{L}_{\epsilon}(u)$ from user $u$. We often call this in
short as the Laplace noise addition mechanism.

######  Definition 2.9.

The distribution $\hat{P}^{\mathcal{L}_{\epsilon}}_{u}$ is defined as follows
for every $u\in\real$.

$\displaystyle{}\hat{\textbf{a}}\sim\hat{P}^{\mathcal{L}_{\epsilon}}_{u}\iff\hat{\textbf{a}}=$
$\displaystyle\operatorname*{arg\,min}_{\textbf{a}\in\mathbb{R}^{k}}\mathop{\operatorname{\mathbb{E}}}\limits_{y\sim\mathcal{L}_{\epsilon}(S_{u})}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]\text{
where }S_{u}\sim\mathcal{L}_{\epsilon}(u)$ (16)
$\displaystyle\overset{(a)}{=}$
$\displaystyle\operatorname*{arg\,min}_{\textbf{a}\in\mathbb{R}^{k}}\mathop{\operatorname{\mathbb{E}}}\limits_{y\sim\mathcal{L}_{\epsilon}(0)}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]+S_{u}\text{where
}S_{u}\sim\mathcal{L}_{\epsilon}(u)$ (17)

Equality $(a)$ follows from the fact that
$y\sim\mathcal{L}_{\epsilon}(z)\implies y-z\sim\mathcal{L}_{\epsilon}(0)$ for
every $z\in\mathbb{R}$.

Observe that the server responds with set of points $\texttt{Set}(\textbf{a})$
for some $\textbf{a}\in\mathbb{R}^{k}$ so as to minimise the expected cost
with respect to some user sampled from a Laplace distribution centred at
$S_{u}$.

We show that the following lemma which states that
$\hat{P}^{\mathcal{L}_{\epsilon}}$ satisfies $\epsilon$-geographic
differential privacy constraints and bound $f(\epsilon,k)$ by
$\hat{f}(\epsilon,k)$.

######  Lemma 2.10 (detailed proof in Appendix B.3).

$\hat{\textbf{P}}^{\mathcal{L}_{\epsilon}}$ satisfies $\epsilon$-geographic
differential-privacy constraints i.e.
$\hat{\textbf{P}}^{\mathcal{L}_{\epsilon}}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$
and thus, we have
$f(\epsilon,k)\leq\textit{cost}(\hat{{P}}^{\mathcal{L}_{\epsilon}})=\hat{f}(\epsilon,k)$

###### Proof Sketch.

Observe that
$\hat{P}^{\mathcal{L}_{\epsilon}}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$
from the post processing theorem, refer to [27] since
$S_{u}\sim\mathcal{L}_{\epsilon}(u)$ satisfies $\epsilon$-geographic
differential privacy constraints.121212Post processing theorem can be proven
even for $\epsilon$-geographic differential privacy similarly. Thus, we prove
$f(\epsilon,k)\leq\text{cost}(\hat{{P}}^{\mathcal{L}_{\epsilon}})$. The
equality is fully proven in Appendix B.3.

∎

####  2.3.2 Obtaining a feasible solution to DILP $\mathcal{E}$

We now construct feasible solutions to DILP $\mathcal{E}$. For some $\zeta>0$
and $\hat{\lambda}>0$, we define

${}\delta^{(c)}(r)=(\zeta/2)e^{-\zeta|r|}\text{ and
}\lambda^{(c)}(r)=\hat{\lambda}\cdot(\zeta/2)e^{-\zeta|r|}\text{ }\forall
r\in\mathbb{R}$ (18)

Now define $v_{med}=\text{Median}(\texttt{Set}(\textbf{v}))$ and for every
$\textbf{v}\in\mathbbm{R}^{k}$, we consider the following Differential
Equation (19) in $\hat{\nu}(.)$.

${}-\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]\delta^{(c)}(r)+\lambda^{(c)}(r)+\frac{d\hat{\nu}(r)}{dr}+\epsilon|\hat{\nu}(r)|=0;\text{
with $\hat{\nu}(v_{med})=0$}$ (19)

Observe that this equation precisely corresponds to the second constraint of
DILP $\mathcal{E}$ (inequality replaced by equality) with an initial value. We
now show that a solution $\hat{\nu}(.)$ to differential equation (19) exists
such that $\hat{\nu}(r)$ is non-negative for sufficiently large $r$ and non-
positive for sufficiently small $r$ to satisfy the last two constraints of
DILP $\mathcal{E}$ in Lemma 2.11.

Observe that the structure of our differential equation is similar to that in
[43, Equation 19]. However, our differential equation has significantly more
complexity since we are minimising over a set of points
$\textbf{v}\in\mathbb{R}^{k}$ and also our equation has to be solved for every
$\textbf{v}\in\mathbb{R}^{k}$ making it more complex.

######  Lemma 2.11 (Proof in Appendix B.4.2).

Choose $\zeta<\epsilon$ and
$0<\hat{\lambda}\leq\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon+\zeta,k)$,
then equation $\eqref{eqn:diff_eqn_nu}$ has a unique $\mathcal{C}^{1}$
solution $\nu^{(c)}(.)$ and there exists $U,L\in\mathbb{R}$ satisfying
$\nu^{(c)}(r)\geq 0\text{ }\forall r\geq U$ and $\nu^{(c)}(r)\leq 0\text{
}\forall r\leq L$.

###### Intuitive explanation.

We just give an intuition for this proof for the case where $\hat{\lambda}$
exceeds $\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon,k)$ by showing
two plots in Figure 3(a) and 3(b) for the two cases where
$\hat{\lambda}<\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon,k)$ and
$\hat{\lambda}>\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon,k)$
respectively. In the first case, $\nu^{(c)}(r)$ is positive for sufficiently
large $r$ and in second case, it goes negative for large $r$ demonstrating the
requirement of the bound
$\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon,k)$ on $\hat{\lambda}$.

The two plots are for the case when $\epsilon=1$, $\zeta=0.1$,
$\mathfrak{h}(z)=z$ and thus
$\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon,k)$ may be
approximately by $\frac{9}{11}\times\frac{1}{2}=0.44$ as shown in Section 2.4.
For the purpose of the plots, we choose $\textbf{v}=[-\log 4;\text{ }0;\text{
}\log 4]^{T}$131313We choose this vector since it minimises equation (15) and
a detailed calculation is given in Section 2.4.  and demonstrate the point in
the Lemma.

(a) Solution for $\hat{\lambda}=0.40$

(b) Solution for $\hat{\lambda}=0.46$

Figure 3: Solutions for Differential Equation (19) for $\textbf{v}=[-\log
4;\text{ }0;\text{ }\log 4]^{T}$

These spikes in the solution may be observed due to the selection of
$\textbf{v}\in\mathbb{R}^{3}$ due to the term
$\left[\min\limits_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]$
in the differential equation. ∎

######  Lemma 2.12 (detailed proof in Appendix B.4.2).

$\text{opt}(\mathcal{E})\geq\hat{f}(\epsilon,k)$.

We present a proof sketch where we do not explicitly show the continuity of
the bounds $U(.)$ and $L(.)$. In Appendix B.7, we prove a claim showing the
existence of such continuous bounds.

###### Proof Sketch.

Recall the functions $\lambda^{(c)}(.),\delta^{(c)}(.)$ defined in (18). Also
for every $\textbf{v}\in\mathbb{R}^{k}$, we obtain a function
$\nu^{(c)}(.,\textbf{v})$ [solution of Equation (19)] with bounds
$U(\textbf{v})$ and $L(\textbf{v})$ satisfying $\nu^{(c)}(r,\textbf{v})\geq
0\text{ }\forall u\geq U(\textbf{v})$ and $\nu^{(c)}(r,\textbf{v})\leq 0\text{
}\forall u\leq L(\textbf{v})$ and this solution is feasible.

The objective value of this feasible solution is $\hat{\lambda}$ and the
constructed solution is feasible for any
$\hat{\lambda}\leq\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon+\zeta,k)$
and $\zeta>0$. Now, since $\hat{f}(\epsilon,k)$ is continuous in $\epsilon$,
choosing $\zeta$ to be arbitrarily small enables us to obtain the objective
value of the solution arbitrarily close to $\hat{f}(\epsilon,k)$ and thus,
$\text{opt}(\mathcal{E})\geq\hat{f}(\epsilon,k)$. ∎

Observe that although we defined the Laplace noise addition mechanism
$(\hat{\textbf{P}}^{\mathcal{L}_{\epsilon}})$ (see Definition 2.9) entirely in
terms of the user’s action, we can consider an alternate mechanism splitting
$(\hat{\textbf{P}}^{\mathcal{L}_{\epsilon}})$ into user’s action and server’s
response attaining the same cost:

  * •

User $u$ sends $S_{u}\sim\mathcal{L}_{\epsilon}(u)$ to the server.

  * •

The server on receiving $S_{u}$ responds with a vector
$\textbf{a}=\operatorname*{arg\,min}\limits_{\textbf{a}\in{}^{k}}\mathop{\operatorname{\mathbb{E}}}\limits_{y\sim\mathcal{L}_{\epsilon}(S_{u})}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]$.

######  Theorem 2.13.

For $\epsilon$-geographic differential privacy, sending Laplace noise, that
is, user $u$ sends a signal drawn from distribution
$\mathcal{L}_{\epsilon}(u)$ is one of the optimal choices of
$\mathcal{P}^{(\epsilon)}_{Z}$ for users, and in this case
$f^{\mathfrak{h}(.)}(\epsilon,k)=\hat{f}(\epsilon,k)$.

###### Proof.

Combining the results in Lemmas 2.10, 2.5, 2.12 and Theorems 2.8 and Theorem
2.2, we obtain
$\hat{f}(\epsilon,k)\leq\text{opt}(\mathcal{E})\leq\text{opt}(\mathcal{O})\leq\hat{f}(\epsilon,k)$
where $\hat{f}(\epsilon,k)$ denotes the cost of Laplace noise addition
mechanism $\hat{P}^{\mathcal{L}_{\epsilon}}$ i.e.
$\textit{cost}(\hat{P}^{\mathcal{L}_{\epsilon}})=\hat{f}(\epsilon,k)$.

∎

###  2.4 Server response given the user sends Laplace Noise

Recall that we proved in Theorem 2.13 that the Laplace noise addition
mechanism is an optimal action for the users. We now focus on the construction
of an optimal server action on receiving the signal $s$ from an user.

  1. 1.

User with value $v\in\real$ reports $s$ after adding Laplace noise of scale
$\frac{1}{\epsilon}$. More formally, $s$ is drawn from Laplace distribution
$\mathcal{L}_{\epsilon}(v)$.

  2. 2.

The server receives $s$ and respond $(s+a_{1},\dots,s+a_{k})$, where
$a_{1},\dots,a_{k}$ are fixed real values.

For the case of $\mathfrak{h}(t)=t$, the optimal mechanism is simple enough
that the values $a_{1},a_{2},\ldots,a_{k}$ can be computed by dynamic
programming, as we sketch in the following subsection, and this concludes the
proof of Theorem 1.4. For other general increasing functions, the optimal
solution for $\\{a_{i}\\}_{i=1}^{k}$ may not always be written in closed form,
however we can always write a recursive expression to compute the points.

####  2.4.1 Sketch of server response for odd $k$

We now show the optimal choice of $A$ to optimize cost function
$\hat{f}(\epsilon,k)$ [in Equation (15)]. Specifically, we assume odd $k$ in
this section. The solution for even $k$ (refer Theorem B.3) can be constructed
using a similar induction where the base case for $k=2$ can be directly
optimized.

Assuming the symmetry of $A$, let $A=\\{-y_{b-1},\ldots-
y_{1},0,y_{1},\ldots,y_{b-1}\\}$, where $y_{1},\ldots,y_{b-1}$ are positive
numbers in increasing order. We will construct the set $y_{1},\ldots,y_{b-1}$
inductively.Let $x$ be a random variable drawn from Laplace distribution
$\mathcal{L}_{\epsilon}(0)$ with parameter $\epsilon$, and the goal is to
minimize
$D_{b}=\operatorname{\mathbb{E}}_{x\sim\mathcal{L}_{\epsilon}(0)}\left[\min\limits_{a\in
A}|x-a|\right]$. Since the density function of $\mathcal{L}_{\epsilon}(0)$
satisfies
$\rho_{\mathcal{L}_{\epsilon}(0)}(x)=\rho_{\mathcal{L}_{\epsilon}(0)}(-x)$, we
have

$D_{b}=\operatorname{\mathbb{E}}_{x\sim\mathcal{L}_{\epsilon}(0)}\left[\min_{a\in
A}\mathfrak{h}(|x-a|)\bigg{|}x\right]>0,$

i.e. the user has a positive private value. Under this conditioning, the
variable $x$ is an exponential random variable of mean 1. In this case, the
search result being used by the server will be one of $y_{0},y_{1}$, …,
$y_{b-1}$. Clearly, $D_{1}=1$. To compute $D_{b+1}$, let $s=y_{1}$.

Then using the memorylessness property of exponential random variables, we get
the recurrence

$\displaystyle D_{b+1}$
$\displaystyle=\int_{t=0}^{s}\min\\{\mathfrak{h}(t),\mathfrak{h}(s-t)\\}e^{-t}dt+e^{-s}D_{b}$
$\displaystyle=\int_{t=0}^{s/2}\mathfrak{h}(t)e^{-t}dt+s\int_{t=s/2}^{s}e^{-t}dt-\int_{t=s/2}^{s}\mathfrak{h}(t)e^{-t}dt+e^{-s}D_{b}.$

The optimal $D_{b+1}$ given $D_{b}$ can be computed by minimising over all
$s\in\mathbb{R}$. However, for the case where $\mathfrak{h}(.)$ is an identity
function, we may give a closed form expression below.

$\displaystyle D_{b+1}=$
$\displaystyle\int_{t=0}^{s/2}te^{-t}dt+s\int_{t=s/2}^{s}e^{-t}dt-\int_{t=s/2}^{s}te^{-t}dt+e^{-s}D_{b}$
$\displaystyle=$
$\displaystyle\left(1-(s/2)e^{-s/2}-e^{-s/2}\right)+s\left(e^{-s/2}-e^{-s}\right)-\left((s/2)e^{-s/2}+e^{-s/2}-se^{-s}-e^{-s}\right)+e^{-s}D_{b}$
$\displaystyle=$ $\displaystyle 1-2e^{-s/2}+e^{-s}+e^{-s}D_{b}$
$\displaystyle=$
$\displaystyle\left(1-e^{-s/2}\right)^{2}+\left(e^{-s/2}\right)^{2}D_{b}$

Setting $\gamma=e^{-s/2}$, and minimizing by taking derivatives, we get
$-2(1-\gamma)+2\gamma D_{b}=0$ which in turn gives

$\gamma=\frac{1}{D_{b}+1}\qquad\mbox{and}\qquad
D_{b+1}=\frac{D_{b}}{D_{b}+1}.$

Plugging in the inductive hypothesis of $D_{b}=1/b$, we get $D_{b+1}=1/(b+1)$.
Further, we get $s=2\ln(1+1/b)$. Thus, by returning $k=2b-1$ results, the
expected “cost of privacy” can be reduced by a factor of $b$. To obtain the
actual positions $y_{1},..,y_{b-1}$ we have to unroll the induction. For
$i=1,\ldots,b-1$, the position $y_{i}$ is given by:

$y_{i}=y_{i-1}+2\ln(1+1/(b-i)).$

Based on the above arguments in the four sections, we have the main theorem
1.4.

##  3 Further extensions

We describe some additional results below.

  * •

When the user is not able to perform the optimal action, we show in Appendix
A.6 that $\text{cost}^{\mathds{1}(.)}(Z,\mathbf{P},\mathbf{Q})=O(\frac{\log
k}{k\epsilon})$ for an appropriate server response $\mathbf{Q}$141414The
server’s action $\mathbf{Q}$ involves sampling from the posterior of the noise
distribution. if the user’s action $\mathbf{P}$ consists of adding symmetric
noise whose distribution satisfies log-concave property151515If the random
noise with log-concave distribution $g$ is given by $Y$, then we have
$\mathbb{E}[Y^{+}\cup\\{0\\}]=\frac{1}{\epsilon}$ and $g(y)=g(-y)$.. Observe
that this property is satisfied by most natural distributions like Exponential
and Gaussian.

  * •

In practice, the set of users may not belong to but in many cases may have a
feature vector embedding in d. In this scenario, a server could employ
dimensionality reduction techniques such as Principal Component Analysis (PCA)
to create a small number $d^{\prime}$ of dimensions which have the strongest
correlation to the dis-utility of a hypothetical user with features identical
to the received signal. The server may project the received signal only along
these dimensions to select the set of $k$ results. In this case, we show that
$\text{cost}^{\mathds{1}(.)}(Z,\mathbf{P},\mathbf{Q})=O\left(\frac{1}{\epsilon
k^{1/d^{\prime}}}\right)$ under some assumptions as discussed Appendix A.7
when the user’s action $\mathbf{P}$ consists of adding independent Gaussian
noise to every feature.

  * •

We further show that Laplace noise continues to be an optimal noise
distribution for the user even under a relaxed definition of geographic
differential privacy (defined in Definition 3.2) in Section 3.1. This
definition captures cases when privacy guarantees are imposed only when the
distance between users is below some threshold (recall from Section 1.3.3 that
such a setup was studied in [35]).

###  3.1 A generalization of Geographic differential privacy

Here we consider a generalization of $\epsilon$-geographic differential
privacy and define $\mathfrak{g}(.)$-geographic differential privacy for an
increasing convex function $\mathfrak{g}(.)$ satisfying Assumption 3.1.

######  Assumption 3.1.

$\mathfrak{g}(.)$ is a increasing convex function satisfying
$\mathfrak{g}(0)=0$ and $\mathfrak{g}(.)$ is differentiable at 0 with
$\mathfrak{g}^{\prime}(0)\neq 0$.

######  Definition 3.2 (alternate definition of geo-DP).

Let $\epsilon>0$ be a desired level of privacy and let $\mathcal{U}$ be a set
of input data and $\mathcal{Y}$ be the set of all possible responses and
$\Delta(\mathcal{Y})$ be the set of all probability distributions (over a
sufficiently rich $\sigma$-algebra of $\mathcal{Y}$ given by
$\sigma(\mathcal{Y})$). For any $\mathfrak{g}(.)$ satisfying Assumption 3.1 a
mechanism $Q:u\rightarrow\Delta(\mathcal{Y})$ is $\mathfrak{g}(.)$-geographic
differentially private if for all $S\in\sigma(\mathcal{Y})$ and
$u_{1},u_{2}\in\mathcal{U}$:

$\mathbb{P}(Qu_{1}\in S)\leq
e^{\mathfrak{g}(|u_{1}-u_{2}|)}\mathbb{P}(Qu_{2}\in S).$

Since this definition allows the privacy guarantee to decay non-linearly with
the distance between the user values, it is a relaxation of
$\epsilon$-geographic DP as defined in Definition 1.2. Observe that this
definition captures cases where the privacy guarantees exist only when the
distance between users is below some threshold by defining $\mathfrak{g}(t)$
to be $\infty$ if $t>T_{0}$ for some threshold $T_{0}$.

Under this notion of differential privacy, we may redefine cost function
$f^{\text{alt},\mathfrak{h}(.)}(\epsilon,k)$ as follows.

$f^{\text{alt},\mathfrak{h}(.)}(\mathfrak{g}(.),k):=\inf_{Z}\inf_{\mathbf{P}\in\mathcal{P}^{\mathfrak{g}(.)}_{Z}}\inf_{\mathbf{Q}\in\mathcal{Q}_{Z}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim\mathbf{P}_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim\mathbf{Q}_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|\right)\right]\right],$

where $\mathcal{P}^{\mathfrak{g}(.)}_{Z}:=\\{\mathbf{P}|\forall
u\in\real,P_{u}\text{~{}is a distribution on $Z$,}\text{~{}and
$\mathfrak{g}(.)$-geographic differential privacy is satisfied}\\}$. The
definition of $\mathcal{Q}_{Z}$ are similar to that in Section 1.1.2.

We now show that adding Laplace noise continues to remain an optimal action
for the users even under this relaxed model of geographic differential
privacy.

######  Theorem 3.3.

For $\mathfrak{g}(.)$-geographic differential privacy, adding Laplace noise,
whose density function is $\rho(x)=\frac{\mathfrak{g}^{\prime}(0)}{2}\cdot
e^{-\mathfrak{g}^{\prime}(0)\left|x\right|}$, is one of the optimal choices of
$\mathcal{P}^{\mathfrak{g}(.)}_{Z}$ for users. Further, when
$\mathfrak{h}(z)=z$, we have
$f^{\text{alt},\mathfrak{h}(.)}(\mathfrak{g}(.),k)=O\left(\frac{1}{\mathfrak{g}^{\prime}(0)k}\right)$
and the optimal mechanism (choice of actions of users and server) itself can
be computed in closed form.

###### Proof.

The proof of this theorem follows identically to that of Theorem 1.4. However,
we require a slight modification of Lemma 2.6 to prove it as stated and proven
in Lemma 3.4. ∎

######  Lemma 3.4.

Suppose, $P_{u}$ has a probability density function given by
$g(u,.):\mathbb{R}^{k}\rightarrow\mathbb{R}$ for every $u\in\mathbb{R}$. Then,
$P$ satisfies $\mathfrak{g}(.)$-geographic differential privacy iff
$\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)\leq\mathfrak{g}^{\prime}(0)g(u,\textbf{x})\text{
}\forall u\in\mathbb{R};\forall x\in\mathbb{R}^{k}$ whenever $\mathfrak{g}(.)$
satisfies Assumption 3.1.

The proof of this Lemma is very similar to that of Lemma 2.6 and proven in
Section B.2.2.

##  4 Conclusion

We have defined a new architecture for differential privacy with a small
number of multiple selections, and shown in a stylized model that significant
improvements in the privacy-accuracy tradeoffs are indeed possible. Our model
ignores some practical considerations, namely, the client’s request lives in a
high dimensional feature space (and not in one-dimension), and the server has
a machine learning model to evaluate the quality of a result that it needs to
convey to the client in some compressed form. Addressing these issues while
preserving the privacy-accuracy trade-off either theoretically or empirically,
will be the focus of future work.

## References

  * [1] Duality in linear programming.  https://sites.math.washington.edu//~burke/crs/407/notes/section4.pdf.  Accessed: 2010-09-30.
  * [2] EJ Anderson.  A new continuous model for job-shop scheduling.  International journal of systems science, 12(12):1469–1475, 1981\.
  * [3] E.J. Anderson and P. Nash.  Linear Programming in Infinite-dimensional Spaces: Theory and Applications.  A Wiley-Interscience publication. Wiley, 1987.  URL: https://books.google.com/books?id=O2VRAAAAMAAJ.
  * [4] Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi.  Geo-indistinguishability: Differential privacy for location-based systems.  In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 901–914, 2013.
  * [5] Elliot Anshelevich and John Postl.  Randomized social choice functions under metric preferences, 2016.  arXiv:1512.07590.
  * [6] Apple.  Learning with privacy at scale.  Apple Machine Learning Journal, 1, 2017.  https://machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html.
  * [7] Brendan Avent, Yatharth Dubey, and Aleksandra Korolova.  The power of the hybrid model for mean estimation.  The 20th Privacy Enhancing Technologies Symposium (PETS), 2020.
  * [8] Brendan Avent, Aleksandra Korolova, David Zeber, Torgeir Hovden, and Benjamin Livshits.  BLENDER: Enabling local search with a hybrid differential privacy model.  In 26th USENIX Security Symposium (USENIX Security 17); Journal of Privacy and Confidentiality, 2019.
  * [9] M. Bagnoli and T. Bergstrom.  Log-Concave Probability And Its Applications.  Papers 89-23, Michigan - Center for Research on Economic & Social Theory, 1989.  URL: https://ideas.repec.org/p/fth/michet/89-23.html.
  * [10] Kenneth R Baker.  Introduction to sequencing and scheduling.  (No Title), 1974.
  * [11] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu.  Private query release assisted by public data.  In International Conference on Machine Learning, pages 695–703. PMLR, 2020.
  * [12] Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Guha Thakurta.  Practical locally private heavy hitters.  Advances in Neural Information Processing Systems, 30, 2017.
  * [13] Amitabh Basu, Kipp Martin, and Christopher Thomas Ryan.  Strong duality and sensitivity analysis in semi-infinite linear programming, 2015.  arXiv:1510.07531.
  * [14] Björn Bebensee.  Local differential privacy: a tutorial.  arXiv preprint arXiv:1907.11908, 2019.
  * [15] Amos Beimel, Aleksandra Korolova, Kobbi Nissim, Or Sheffet, and Uri Stemmer.  The power of synergy in differential privacy: Combining a small curator with local randomizers.  In Information-Theoretic Cryptography (ITC), 2020.
  * [16] R. Bellman.  Dynamic Programming.  Princeton Landmarks in Mathematics and Physics. Princeton University Press, 2010.  URL: https://books.google.co.in/books?id=92aYDwAAQBAJ.
  * [17] Avrim Blum, Katrina Ligett, and Aaron Roth.  A learning theory approach to noninteractive database privacy.  Journal of the ACM (JACM), 60(2):1–25, 2013.
  * [18] Hai Brenner and Kobbi Nissim.  Impossibility of differentially private universally optimal mechanisms.  SIAM Journal on Computing, 43(5):1513–1540, 2014.
  * [19] Mark Bun, Jelani Nelson, and Uri Stemmer.  Heavy hitters and the structure of local privacy.  ACM Transactions on Algorithms (TALG), 15(4):1–40, 2019.
  * [20] Ioannis Caragiannis, Nisarg Shah, and Alexandros A. Voudouris.  The metric distortion of multiwinner voting.  Artificial Intelligence, 313:103802, 2022.  URL: https://www.sciencedirect.com/science/article/pii/S0004370222001424, doi:https://doi.org/10.1016/j.artint.2022.103802.
  * [21] Rui Chen, Haoran Li, A Kai Qin, Shiva Prasad Kasiviswanathan, and Hongxia Jin.  Private spatial data aggregation in the local setting.  In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 289–300. IEEE, 2016.
  * [22] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev.  Distributed differential privacy via shuffling.  In Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part I 38, pages 375–403. Springer, 2019.
  * [23] Richard Walter Conway.  ” theory of scheduling,”.  Addison Wesley, 1967.
  * [24] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin.  Collecting telemetry data privately.  Advances in Neural Information Processing Systems, 30, 2017.
  * [25] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright.  Local privacy and statistical minimax rates.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438, 2013.  doi:10.1109/FOCS.2013.53.
  * [26] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006.
  * [27] Cynthia Dwork and Aaron Roth.  2014\.  doi:10.1561/0400000042.
  * [28] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [29] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta.  Amplification by shuffling: From local to central differential privacy via anonymity.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468–2479. SIAM, 2019.
  * [30] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  RAPPOR: Randomized aggregatable privacy-preserving ordinal response.  In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS ’14, pages 1054–1067, New York, NY, USA, 2014. ACM.  URL: http://doi.acm.org/10.1145/2660267.2660348.
  * [31] Lawrence C Evans.  An introduction to mathematical optimal control theory version 0.2.  Lecture notes available at http://math. berkeley. edu/~ evans/control. course. pdf, 1983.
  * [32] Vitaly Feldman, Audra McMillan, and Kunal Talwar.  Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954–964. IEEE, 2022.
  * [33] Natasha Fernandes, Annabelle McIver, and Carroll Morgan.  The laplace mechanism has optimal utility for differential privacy over continuous queries.  In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12. IEEE, 2021.
  * [34] K. O. Friedrichs.  The identity of weak and strong extensions of differential operators.  Transactions of the American Mathematical Society, 55(1):132–151, 1944.  URL: http://www.jstor.org/stable/1990143.
  * [35] Quan Geng and Pramod Viswanath.  The optimal noise-adding mechanism in differential privacy.  IEEE Transactions on Information Theory, 62(2):925–951, 2015.
  * [36] Robin C. Geyer, Tassilo J. Klein, and Moin Nabi.  Differentially private federated learning: A client level perspective.  arXiv preprint arXiv:1712.07557, 2017.
  * [37] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan.  Universally utility-maximizing privacy mechanisms.  SIAM Journal on Computing, 41(6):1673–1693, 2012.
  * [38] Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah.  Resolving the optimal metric distortion conjecture.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1427–1438. IEEE, 2020.
  * [39] Saikat Guha, Bin Cheng, and Paul Francis.  Privad: Practical privacy in online advertising.  In USENIX conference on Networked systems design and implementation, pages 169–182, 2011.
  * [40] Mangesh Gupte and Mukund Sundararajan.  Universally optimal privacy mechanisms for minimax agents.  In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 135–146, 2010.
  * [41] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  Extremal mechanisms for local differential privacy.  Advances in neural information processing systems, 27, 2014.
  * [42] Fatih Erdem Kizilkaya and David Kempe.  Plurality veto: A simple voting rule achieving optimal metric distortion.  arXiv preprint arXiv:2206.07098, 2022.
  * [43] Fragkiskos Koufogiannis, Shuo Han, and George J Pappas.  Optimality of the laplace mechanism in differential privacy.  arXiv preprint arXiv:1504.00065, 2015.
  * [44] Camillo De Lellis.  Cauchy-Lipschitz theorem.  https://encyclopediaofmath.org/wiki/Cauchy-Lipschitz_theorem.
  * [45] Jingcheng Liu and Kunal Talwar.  Private selection from private candidates.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 298–309, 2019.
  * [46] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007.
  * [47] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson.  Scalable private learning with pate, 2018.  arXiv:1802.08908.
  * [48] Malcolm C. Pullan.  An algorithm for a class of continuous linear programs.  SIAM Journal on Control and Optimization, 31(6):1558–1577, 1993\.  arXiv:https://doi.org/10.1137/0331073, doi:10.1137/0331073.
  * [49] W. Rudin.  Principles of Mathematical Analysis.  International series in pure and applied mathematics. McGraw-Hill, 1976\.  URL: https://books.google.com/books?id=kwqzPAAACAAJ.
  * [50] Vincent Toubiana, Arvind Narayanan, Dan Boneh, Helen Nissenbaum, and Solon Barocas.  Adnostic: Privacy preserving targeted advertising.  NDSS, 2010.
  * [51] N.T. Vinh, D.S. Kim, N.N. Tam, and N.D. Yen.  Duality gap function in infinite dimensional linear programming.  Journal of Mathematical Analysis and Applications, 437(1):1–15, 2016.  URL: https://www.sciencedirect.com/science/article/pii/S0022247X15011762, doi:https://doi.org/10.1016/j.jmaa.2015.12.043.
  * [52] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha.  Locally differentially private protocols for frequency estimation.  In 26th USENIX Security Symposium (USENIX Security 17), pages 729–745, 2017.
  * [53] Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  Journal of the American Statistical Association, 60(309):63–69, 1965.
  * [54] Mariusz Wodzicki.  Notes on Reinmann Integral.  https://math.berkeley.edu/~wodzicki/H104.F10/Integral.pdf.

##  Appendix A Extensions to the models and more detailed model description

###  A.1 Model and Overview (With More Details)

####  A.1.1 Notations

We use $[m]$ to denote the set $\\{1,2,\dots,m\\}$, for any non-negative
integer $m$. $\mathbb{N}$ is the set of positive integers, $\mathbb{Q}$ is the
set of rational real numbers, and is the set of real numbers. We denote
$\mathcal{A}={}^{k}$

$\operatorname{\mathbb{E}}\left[V\right]$ denotes the expectation of real
random variable $V$. $\operatorname{\mathbb{P}}\left(E\right)$ denotes the
probability of an event $E$. $\mathbbm{I}\left\\{E\right\\}$ is the indicator,
which has value 1 when the event $E$ happens and has value 0 when $E$ does not
happen, and thus we have
$\operatorname{\mathbb{P}}\left(E\right)=\operatorname{\mathbb{E}}\left[\mathbbm{I}\left\\{E\right\\}\right]$.

For any set $S$, $\mathbb{D}\left(S\right)$ is defined as the set of
probability measures on $S$.

We sometimes have integral operations. Since we are optimizing the objective
over all possible mechanisms, some functions may not be continuous, and some
distributions may not have density functions, so we use the Lebesgue integral.

We use $\operatorname{\mathbb{E}}_{X\sim\mu}\left[V(X)\right]$ to denote the
expectation of $V(X)$ when the probability measure of $X$ is $\mu$, so

$\displaystyle\operatorname{\mathbb{E}}_{X\sim\mu}\left[V(X)\right]:=\int_{x}V(x)\mu(dx).$

Similarly, we use $\operatorname{\mathbb{P}}_{X\sim\mu}\left(E(X)\right)$ to
denote the probability that event $E(X)$ happens when the probability measure
of $X$ is $\mu$, so

$\displaystyle\operatorname{\mathbb{P}}_{X\sim\mu}\left(E(X)\right):=\operatorname{\mathbb{E}}_{X\sim\mu}\left[\mathbbm{I}\left\\{E(X)\right\\}\right]=\int_{x}\mathbbm{I}\left\\{E(x)\right\\}\mu(dx).$

When a probability measure $\mu$ has a probability density (or in other words
is continuous), we use $\rho_{\mu}(x)$ to denote its probability density at
$x$ and the Lebesgue integral may be replaced by a Reimann integral.

Similarly, we use Set to convert a vector in k to a set. More formally, for
any $\textbf{a}\in{}^{k}$, $\texttt{Set}(\textbf{a})$ is denoted by
$\\{a_{i}:i\in[k]\\}$.

###  A.2 Problem setting for the restricted setup (results and users lie in
the same space)

Users send a signal to the server, and the server sends back $k$ results $A$
which we denote as a vector in k. In this subsection, we give a measure-
theoretic view of the mechanism $(Z,\mathbf{P},\mathbf{Q})$.

We aim to determine a mechanism with the following ingredients.

  1. 1.

A set of signals $Z$.

  2. 2.

Action of users $P_{u}(\mathcal{H})$, denoting the probability that user $u$
sends signal $s\in\mathcal{H}$, for $u\in U$ and
$\mathcal{H}\in\mathcal{F}_{Z}$, where $\mathcal{F}_{Z}$ is the set of all the
measurable subsets of $Z$.

  3. 3.

Action of server $Q_{s}(\mathcal{H})$, denoting the probability that server
sends back results $A\in\mathcal{H}$ when receiving signal $s$, for $s\in Z$
and $\mathcal{H}\in\mathcal{F}_{\mathcal{A}}$, where $\mathcal{F}_{Z}$ is all
the measurable subset of $Z$.

The system should have geographic differential privacy. For any
$\mathcal{H}\in\mathcal{F}_{Z}$, for any $u_{1},u_{2}\in U$,
$P_{u_{1}}(\mathcal{H})\leq
e^{\epsilon\cdot|u_{1}-u_{2}|}P_{u_{2}}(\mathcal{H})$,

We want to minimize the distance between the user and the closest ad that the
user receives, in the worst case with respect to the distribution of users.
Formally, we want to compute

$f^{\mathfrak{h}(.)}(\epsilon,k):=\inf_{Z}\inf_{\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z},\mathbf{Q}\in\mathcal{Q}_{Z}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u}}\left[\mathop{\operatorname{\mathbb{E}}}\limits_{\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right],$

where

  1. 1.

$Z$ can be any set.

  2. 2.

When we are interested in geographic differential privacy on . We call
$\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim P_{u},\textbf{a}\sim
Q_{s}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]$
the cost of user $u$ from mechanism $(Z,\mathbf{P},\mathbf{Q})$

  3. 3.

$\mathcal{P}^{(\epsilon)}_{Z}$ is the set of mechanism satisfying geographic
differential privacy.

  4. 4.

$\mathcal{Q}_{Z}:=\\{\mathbf{Q}|\forall s\in
Z,Q_{s}({\cdot})\in\mathbb{D}\left(\mathcal{A}\right)\\}$, which is the set of
available actions of the server.

###  A.3 Summary of Results

In either model, one of the optimal mechanisms satisfies $H=\mathcal{A}$,
which means the signals sent by users and servers can be drawn from the same
set. In fact, the server will directly return the signal it receives.
Furthermore, we do not need to consider all the distribution over users, we
only care about the user that has the largest error.

######  Theorem A.1.

For $\epsilon$-geographic differential privacy adding Laplace noise i.e. user
$u$ draws a signal from $\mathcal{L}_{\epsilon}(u)$ is one of the optimal
choices for users, and in this case $f^{\mathfrak{h}(.)}(\epsilon,k)$ is
$O(1/(\epsilon k))$ when $\mathfrak{h}(t)=t$. Furthermore, when
$\mathfrak{h}(t)=t$, the optimal mechanism can be computed in closed form
(Theorem B.3).

###  A.4 Calculation of optimal mechanism on a ring for the case of $k=2$

We calculate the optimal mechanism in geographic differential privacy setting,
on a unit ring, when $\epsilon=3/8$, and the number of results is $k=2$. In
this section, we define $d(u,a)=\left<u,a\right>$

We use real numbers in $[-\pi,\pi)$ to denote users and results on a unit
ring, and $\left<x,a\right>$ denotes $|x-a|$. Figure 4 illustrates the optimal
mechanism under geographic DP for $k=2$. This mechanism uses noise that is a
piece-wise composition of Laplace noises; we obtain a cost of 0.72 whereas
Laplace noise gives a cost of 0.75.

Figure 4: Geographic differential privacy setting when users and results are
located on a unit ring, for $k=2$ and $\epsilon\in\\{3/8,1\\}$, showing the
stark difference between Laplace noise and the optimal noise. Suppose the user
has a private value $u$. Then the user sends $u+x$ to the server, where $x$ is
drawn from a noise distribution with density $\rho(t)$, depicted here for both
Laplace noise and the optimal noise. Suppose the server receives $s$. Then the
server’s optimal response is $s+a_{1}$ and $s+a_{2}$, where the values of
$a_{1},a_{2}$ are the $t$-axis values of dots on the density functions, again
assuming both Laplace noise and the optimal noise. Laplace is not optimal when
$\epsilon=3/8$, while Laplace is optimal when $\epsilon=1$.

To find the optimal mechanism for the case of the ring, we solve the DILP
$\mathcal{O}$ using a linear program solver and obtain the plot shown in
Figure 4 with cost of 0.72. However, when the user sends Laplace noise, the
server on receiving signal $z$ responds with two points $z+a_{1}$ and
$z+a_{2}$ which maybe calculated by the following problem.

$\displaystyle\min_{a_{1}\in[-\pi,\pi),a_{2}\in[-\pi,\pi)}\int_{-\pi}^{\pi}\min\\{\left<x,a_{1}\right>,\left<x,a_{2}\right>\\}\rho(x)dx,$

where $\rho(x)$ is a density function for the Laplace distribution,

###  A.5 Restricted and Unrestricted Setup of the Multi-Selection model

Recall the setup in Section 1 where the users and results belonged to
different sets and $M$ with the definition of dis-utility in Definition 1.3.
In section 1.1.4, we considered an alternate setup where the users and results
belonged to the same set and the optimal result for an user $u$ was the result
$u$ itself. In this section, we call these setups unrestricted and restricted
respectively and define our “multi-selection” model separately for both these
setups. Finally, we bound the cost function in the unrestricted setup by the
cost function in the restricted setup in Theorem A.2 thus, showing that it is
sufficient to consider the cost function in the restricted setup.

####  A.5.1 Unrestricted setup

Recall that results and users are located in sets ${M}$ and respectively and
function $\text{OPT}:\real\rightarrow M$ maps every user to its optimal
result(ad). Recall that the dis-utility of an user $u$ from a result $m$ is
defined in Definition 1.3.

####  A.5.2 Restricted setup

This setup is very similar to the setup described except the fact that users
and results(ads) lie on the same set . Recall from the description in Section
1.1.4, the dis-utility of an user $u\in\real$ from a result $a\in\real$ is
given by $\mathfrak{h}(|u-a|)$ for some function $\mathfrak{h}(.)$ satisfying
equations (2) and (3).

####  A.5.3 The space of server/user actions

Recall that the goal is to determine a mechanism that has the following
ingredients:

  1. 1.

A set of signals $Z$.

  2. 2.

The action of users, which involves choosing a signal from a distribution over
signals. We use $P_{u}$ for $u\in\real$ to denote the distribution of the
signals sent by user $u$. This distribution is supported on $Z$.

  3. 3.

The distribution over actions of the server, $Q_{s}$ when it receives $s\in
Z$. This distribution denoting the distribution of the result set returned by
the server given signal $s$ may be supported on either k or $M^{k}$, for the
restricted setup and unrestricted setup respectively.

The optimal mechanism is computed by jointly optimizing over the tuple
$(Z,\mathbf{P},\mathbf{Q})$.

And thus, we define the set of server responses by
$\mathcal{Q}_{\text{unrestricted},Z}$ and $\mathcal{Q}_{\text{restricted},Z}$
for unrestricted and restricted setup respectively.

  * •

$\mathcal{Q}_{\text{unrestricted},Z}:=\\{\mathbf{Q}|\forall s\in
Z,Q_{s}\text{~{}is a distribution on $M^{k}$}\\}$.

  * •

$\mathcal{Q}_{\text{restricted},Z}:=\\{\mathbf{Q}|\forall s\in
Z,Q_{s}\text{~{}is a distribution on ${}^{k}$}\\}$.

In any feasible geographic DP mechanism, the user behavior should satisfy
$\epsilon$-geographic differential privacy: for any $u_{1},u_{2}\in\real$, it
should hold that $P_{u_{1}}(S)\leq P_{u_{2}}(S)e^{\epsilon|u_{1}-u_{2}|}$
where $S$ is any measurable subset of $Z$. For any fixed response size $k$, in
order to maximize utility while ensuring the specified level of privacy, the
goal is to minimize the disutility of the user from the result that the gives
the user minimum dis-utility where the minimisation is the worst case user $u$
in .

####  A.5.4 Cost functions in both the setups

For the unrestricted and restricted setups, we define the cost functions
${f}_{\text{unrestricted}}^{\mathfrak{h}(.)}(\epsilon,k)$ and
${f}_{\text{unrestricted}}^{\mathfrak{h}(.)}(\epsilon,k)$ respectively below.
Recall that $Z$ may denote any set.

${f}_{\text{unrestricted}}^{\mathfrak{h}(.)}(\epsilon,k):=\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\\\
\mathbf{Q}\in\mathcal{Q}_{\text{unrestricted},Z}\end{subarray}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\left(\text{Dis-
util}^{\mathfrak{h}(.)}(u,a)\right)\right],$

${f}_{\text{restricted}}^{\mathfrak{h}(.)}(\epsilon,k):=\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\\\
\mathbf{Q}\in\mathcal{Q}_{\text{restricted},Z}\end{subarray}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|\right)\right],\text{
where }$

$\mathcal{P}^{(\epsilon)}_{Z}:=\\{\mathbf{P}|\forall
u\in\real,P_{u}\text{~{}is a distribution on $Z$,}\text{~{}and
$\epsilon$-geographic differential privacy is satisfied}\\}$.

We state a theorem upper bounding
${f}_{\text{unrestricted}}^{\mathfrak{h}(.)}(\epsilon,k)$ by
${f}_{\text{restricted}}^{\mathfrak{h}(.)}(\epsilon,k)$.

######  Theorem A.2.

For any $\mathfrak{h}(.)$ satisfying equation (2), we have
${f}_{\text{unrestricted}}^{\mathfrak{h}(.)}(\epsilon,k)\leq{f}_{\text{restricted}}^{\mathfrak{h}(.)}(\epsilon,k)$.

###### Proof.

Recall that

${f}_{\text{unrestricted}}^{\mathfrak{h}(.)}(\epsilon,k):=\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\\\
\mathbf{Q}\in\mathcal{Q}_{\text{unrestricted},Z}\end{subarray}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\left(\text{Dis-
util}^{\mathfrak{h}(.)}(u,a)\right)\right],$
$f^{\mathfrak{h}(.)}(\epsilon,k):=\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\\\
\mathbf{Q}\in\mathcal{Q}_{\text{restricted},Z}\end{subarray}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|\right)\right],$

and

$\text{Dis-
util}^{\mathfrak{h}(.)}(u,m):=\inf\limits_{u^{\prime}:OPT(u^{\prime})=m}\mathfrak{h}(|u-u^{\prime}|).$

So we need to prove

$\displaystyle\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\\\
\mathbf{Q}\in\mathcal{Q}_{\text{unrestricted},Z}\end{subarray}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\left(\inf\limits_{u^{\prime}:OPT(u^{\prime})=a}\mathfrak{h}(|u-u^{\prime}|)\right)\right]$
$\displaystyle\leq$
$\displaystyle\inf_{Z}\inf_{\begin{subarray}{c}\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}\\\
\mathbf{Q}\in\mathcal{Q}_{\text{restricted},Z}\end{subarray}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|\right)\right]$

It is sufficient to show, for any $Z$ and
$\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z}$,

$\displaystyle\inf_{\mathbf{Q}\in\mathcal{Q}_{\text{unrestricted},Z}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\left(\inf\limits_{u^{\prime}:OPT(u^{\prime})=a}\mathfrak{h}(|u-u^{\prime}|)\right)\right]$
$\displaystyle\leq$
$\displaystyle\inf_{\mathbf{Q}\in\mathcal{Q}_{\text{restricted},Z}}\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|\right)\right]$
(20)

For $\mathbf{Q}\in\mathcal{Q}_{\text{restricted},Z}$, since $\text{Dis-
util}^{\mathfrak{h}(.)}(u,m):=\inf\limits_{u^{\prime}:OPT(u^{\prime})=m}\mathfrak{h}(|u-u^{\prime}|)$,
we have

$\displaystyle\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|\right)\right]\geq\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\text{Dis-
util}^{\mathfrak{h}(.)}(u,\text{OPT}(a))\right].$
$\displaystyle\implies\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|\right)\right]\geq\sup_{u\in\real}\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\text{Dis-
util}^{\mathfrak{h}(.)}(u,\text{OPT}(a))\right].$ (21)

Given $\mathbf{Q}\in\mathcal{Q}_{\text{restricted},Z}$, we draw a from
$\mathbf{Q}$, and let
$\textbf{b}=[\text{OPT}(a_{1}),\text{OPT}(a_{2}),\ldots,\text{OPT}(a_{k})]^{T}$.
Suppose the distribution of b is $\mathbf{Q}^{\prime}$, and we have

$\displaystyle\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{a}\sim Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\text{Dis-
util}^{\mathfrak{h}(.)}(u,\text{OPT}(a))\right]=\mathop{\operatorname{\mathbb{E}}}\limits_{s\sim
P_{u},\textbf{b}\sim
Q^{\prime}_{s}}\left[\min_{\textbf{b}\in\texttt{Set}(\textbf{b})}\text{Dis-
util}^{\mathfrak{h}(.)}(u,b)\right].$ (22)

Note that $\mathbf{Q}^{\prime}\in\mathcal{Q}_{\text{unrestricted},Z}$, so
combining Inequality A.5.4 and Equality 22, we have Equation 20, which
finishes the proof.

∎

And thus, it is sufficient to study
${f}_{\text{restricted}}^{\mathfrak{h}(.)}(\epsilon,k)$ (defined as
$f^{\mathfrak{h}(.)}(\epsilon,k)$ in Section 1.1.2).

###  A.6 Noise satisfying Monotone Hazard Rate property

Let $Y$ denote the random noise with density $g$. We assume $Y$ is symmetric
about the origin, and let $X=Y^{+}\cup\\{0\\}$. Let $f$ denote the density
function of $X$ (so that $f(x)=2g(x)$ for $x\geq 0$), and let
$F(x)=\operatorname{\mathbb{P}}\left(X\geq x\right)$. We assume that
$\operatorname{\mathbb{E}}\left[X\right]=\frac{1}{\epsilon}$.161616This
implies that a large $\epsilon$ is equivalent to the magnitude of noise being
smaller and vice-versa. Although this distribution does not satisfy $\epsilon$
geographic differential privacy, this follows a similar trend w.r.t
$\epsilon$.  We assume $f$ is continuously differentiable and log-concave. By
[9], we have $F$ is also log-concave. Note that several natural distributions
such as Exponential (Laplace noise) and Gaussian are log-concave.

We are interested in choosing $2K-1$ values
$S=\\{-a_{K-1},-a_{K-2},\ldots,-a_{1},0,a_{1},\ldots,a_{K-1}\\}$ such that for
a random draw $y\sim Y$, the expected error in approximating $y$ by its
closest point in $S$ is small. For $i=0,1,2,\ldots,K-1$, we will choose
$a_{i}=F^{-1}\left(1-\frac{i}{K}\right)$. Let
$\phi=\operatorname{\mathbb{E}}_{x\sim X}\left[\min\limits_{v\in
S}|v-x|\right]$. Note that the error of $Y$ with respect to $S$ is exactly
$\phi$.

Our main result is the following theorem:

######  Theorem A.3.

$\phi=O\left(\frac{\log K}{K\epsilon}\right)$.

###### Proof.

Let $G(z)=F^{-1}(z)$ for $z\in[0,1]$. For upper bounding $\phi$, we map each
$x\sim X$ to the immediately smaller value in $S$. If we draw $z\in[0,1]$
uniformly at random, the error is upper bounded as:

$\phi\leq\int_{0}^{1}G(z)dz-\sum_{i=1}^{K}\frac{1}{K}G\left(\frac{i}{K}\right)\leq\int_{0}^{1/K}\left(G(z)-G(1/K)\right)dz+\frac{1}{K}G(1/K).$

Let $q=G(1/K).$ Then the above can be rewritten as:

$\phi\leq\frac{q}{K}+\int_{q}^{\infty}F(x)dx.$

Next, it follows from [9] that if $F$ is log-concave, then so is
$\int_{r}^{\infty}F(x)dx$. This means the function

$\ell(r)=\frac{\int_{r}^{\infty}F(x)dx}{F(r)}$

is non-increasing in $r$. Therefore,

$\int_{q}^{\infty}F(x)dx\leq
F(q)\int_{0}^{\infty}F(x)dx=\frac{1}{K}\operatorname{\mathbb{E}}\left[X\right]=\frac{1}{\epsilon
K}.$

Let $h(x)=-\log F(x)$. Then, $h$ is convex and increasing. Further, $h(q)=\log
K$. Let $s=F^{-1}(1/e)$ so that $h(s)=1$. Since

$h(q)-h(s)\geq(q-s)h^{\prime}(s),$

we have

$q-s\leq\frac{\log K}{h^{\prime}(s)}.$

Further, $h(s)\leq sh^{\prime}(s)$ so that

$\frac{1}{h^{\prime}(s)}\leq s.$

Since $F(s)=1/e$ and
$\operatorname{\mathbb{E}}\left[X\right]=\frac{1}{\epsilon}\geq\int_{0}^{s}F(x)dx$,
we have $s\leq\frac{e}{\epsilon}$. Therefore, $h^{\prime}(s)\geq
1/{e\epsilon}$. Putting this together,

$q\leq\frac{s}{\epsilon}+\frac{\log
K}{h^{\prime}(s)}\leq\frac{e}{\epsilon}(1+\log K)=O(\frac{\log K}{\epsilon}).$

Therefore,

$\phi\leq\frac{q}{K}+\int_{q}^{\infty}F(x)dx=O\left(\frac{\log
K}{K\epsilon}\right)+\frac{1}{K\epsilon}$

completing the proof. ∎

###  A.7 User Features lying on some high dimensional space

In this subsection, we relax the assumption that users lying on an infinite
dimensional line, rather for every user $u$ belongs to some set $U$ and every
movie $m$ belongs to some set $M$ and consider some function
$\kappa:U\rightarrow\mathbb{R}^{d}$ mapping every user to some user feature
vector and denote the dis-utility of an user $u$ from a movie $m$ by
$d(\kappa(u),m)$. Observe that this could be any complex function in high
dimensions which could be captured by some machine learning model. We now make
the following assumption for movies lying in some vicinity of user $u$.
Informally, this means that the the user does not get dis-utility from every
possible feature but only gets a dis-utility only from some $d^{\prime}$
directions.

######  Assumption A.4.

Fix any user $u\in U$. There exists a subset of movies $M_{u}\subseteq M$
(call it movies in neighbourhood of user $u$), a matrix
$P_{u}\in\mathbb{R}^{d^{\prime}\times d}$ function
$\lambda_{u}:M_{u}\rightarrow\mathbb{R}^{d^{\prime}}$ satisfying the following
properties

  * •

The disutility of users $u^{\prime}\in U$ lying in a neighbourhood of $u$ i.e.
$|\kappa(u^{\prime})-\kappa(u)|_{1}<\delta$ from movies $m\in M_{u}$ may be
approximated by
$d(u^{\prime},m)\approx||P_{u}\cdot\kappa(u^{\prime})-\lambda_{u}(m)||_{1}$.

  * •

The function $\lambda_{u}$ is invertible i.e. the set of movies $M_{u}$ is
densely populated and movies exist along most directions.

These assumptions imply that the functions described above hold not just for
user $u$ but is also true for users $u^{\prime}$ with $\kappa(u^{\prime})$
lying in a neighbourhood of $\kappa(u)$. The function $\lambda_{u}$ denotes a
map from the movie space to the feature space for an user $u\in U$. $P_{u}$
effectively captures the linear combination of the features that play a role
in the dis-utility of user $u$.

Note that some of these assumptions a bit tight and may not be true in reality
but in this section we analyse the server response and user action under this
mechanism under the Gaussian noise addition mechanism. We analyse the Gaussian
mechanism as it is easier to analyse since additions of Gaussian is also a
Gaussian. Also we make an assumption that noise parameter
$1/\epsilon<<\delta$.

Notations: For some $Y\sim\mathcal{N}(0,\sigma^{2})$ and suppose $X=|Y|$. Now
denote $F_{\sigma}(x)=\text{Pr}(X\geq x)$ for some $x>0$ and observe that
$F_{\sigma}$ is invertible from $(0,1]\rightarrow[0,\infty)$. We also extend
its definition to $(0,2)$ by defining
$F^{-1}_{\sigma}(2-x)=-F^{-1}_{\sigma}(x)$ for $x>0$

Let us denote the sum of all squares of all entries in row $i$ of matrix $P$
is given by $P^{(2)}[i,:]$ and denote all integers from $a$ to $b$ by
$[a\ldots b]$ and $[a\ldots b]^{k}$ denotes the set of all $k$ dimensional
vectors in with each component taking an integral value from $a$ to $b$.

User’s Action:

An user $u\in U$ adds Gaussian noise with parameter $\epsilon$ i.e.
$\mathcal{N}(0,\frac{1}{\epsilon^{2}}{I})$ to its feature $\kappa(u)$ and
sends it to the server, let us call it distribution $\mathcal{F}_{u}$.

Server’s Action:

Suppose the server receives a signal $\hat{f}$. The signal sends back
$k=(2k^{\prime}+1)^{d^{\prime}}$ along each of the the $d^{\prime}$ dimensions
which we describe below. Further consider some user $u^{\prime}$ whose feature
vector $\kappa(u^{\prime})$ lies in $1/\epsilon$ vicinity of signal $\hat{f}$.
Let us index the movies by
$\mathcal{M}_{\hat{f}}=[\mathfrak{m}_{\textbf{i}}]_{\textbf{i}\in{[-k^{\prime}\ldots
k^{\prime}]}^{d^{\prime}}}$.

For every $\textbf{i}\in{[-k^{\prime}\ldots k^{\prime}]}^{d^{\prime}}$, define
$\mathfrak{m}_{\textbf{i}}$ as follows:

$\displaystyle
m_{\textbf{i}}:=\lambda_{u^{\prime}}^{-1}(P_{u^{\prime}}\hat{f}+\textbf{v})\text{
for }$ $\displaystyle\textbf{v}\in\mathbbm{R}^{d^{\prime}}$ (23)
$\displaystyle\text{ where
}v_{j}:=F^{-1}_{\frac{P^{(2)}_{u^{\prime}}[j,:]}{\epsilon^{2}}}(1-i_{j}/k^{\prime})\text{
}\forall j\in[1,\ldots,d^{\prime}]$ (24)

######  Lemma A.5.

$\mathbbm{E}_{\hat{f}\sim\mathcal{F}_{u}}\left[\min\limits_{m\in\mathcal{M}_{\hat{f}}}d(u,m)\right]\overset{(a)}{\approx}O\left(d^{\prime}\frac{\log
k^{\prime}}{\epsilon k^{\prime}}\right)=O\left(\frac{\log k}{\epsilon
k^{1/d^{\prime}}}\right)$

###### Proof.

This follows since $f^{\prime}$ is a Gaussian Random vector and thus $j^{th}$
component of $P_{u^{\prime}}\hat{f}$ is given by Gaussian random variable with
variance $\frac{P^{(2)}_{u^{\prime}}[j,:]}{\epsilon^{2}}$. The first point in
Assumption A.4 implies the disutility may be approximated by
$||P_{u^{\prime}}\cdot\kappa(u)-\lambda_{u^{\prime}}(m)||_{1}$ since the

Now apply Theorem A.3 and since the placement of points is identical to that
in Section A.6, we get the desired equality in $(a)$. ∎

###  A.8 Additional problems that may be be formulated as a DILP

We now discuss two scenarios where a problem maybe solved by formulation as an
optimization problem over function spaces involving constraints on both
derivatives and integrals.

####  A.8.1 A problem from job scheduling

Job scheduling has been a well-studied problem and has attracted a lot of
attention in theory of operations research starting from [23, 10]. In [2], a
new continuous time model was proposed for the same described formally in [2,
Section 2] and the optimization variable functions are given by
$\\{x_{i}(.)\\}_{i=1}^{N}:\mathbb{R}\rightarrow\mathbb{R}^{+},\\{y_{i,j}(.),u_{i,j}(.)\\}_{j=1,i=1}^{N_{i},N}:\mathbb{R}\rightarrow\mathbb{R}^{+}$.
In this model, we need to produce multiple items with each item goes through
multiple job shops for an operation to be performed. and there is a continuous
demand for each item. We aim to minimise the cumulative backlog for items in
continuous time.

We now introduce some notations for the same by restating the problem in [2].

  * •

$N$ : number of parts

  * •

$n_{i}$: number of operations required by part $i$

  * •

$M$: number of machines

  * •

$m_{i,j}$: machine on which the $j^{th}$ operation is performed for part $i$

  * •

$r_{i,j}$: Maximum rate of procession on $m_{i,j}$ of the $j^{th}$ operation
on part $i$

  * •

$s_{i,j}$ Initial stock of part $i$ between the $j^{th}$ and $(j+1)^{th}$
operation.

  * •

$b_{i}$: Initial backlog of part $i$

  * •

$d_{i}(t)$: Rate of demand of part $i$ at time $t$

  * •

$k_{i}$: cost per unit time of unit backlog of part $i$

  * •

$T$ time horizon

Observe that the optimization variables in this problem are
$x_{i}(t):[0,1]\rightarrow\mathbb{R}^{+}$ for $i\in[n]$ and
$y_{i,j}(t):[0,1]\rightarrow\mathbb{R}^{+}$ for $j\in[n_{i}],i\in[n]$

As discussed in [2], we now formulate our optimization problem below.

${}\left\\{\begin{aligned} \min&\int_{t\in
0}^{T}\sum_{i=1}^{n}k_{i}(t)x_{i}(t)du\\\ \textrm{s.t.
}\quad&x^{\prime}_{i}(t)=d_{i}(t)-r_{i,n_{i}}u_{i,n_{i}}(t)\text{ }\forall
j\in[n_{i}];i\in[n];\\\
&y^{\prime}_{i,j}(t)=r_{i,j}u_{i,j}(t)-r_{i,j+1}u_{i,j+1}(t)\text{ }\forall
j\in[n_{i}];i\in[n];\\\ &x_{i}(t)\geq 0;y_{i,j}(t)\geq 0;u_{i,j}(t)\geq
0\text{ }\forall j\in[n_{i}];i\in[n];t\in[0,T]\\\
&\sum_{i,j:m_{i,j}=k}u_{i,j}(t)\leq 1\text{ }\forall k\in[M]\\\
&x_{i}(0)=b_{i};y_{i,j}(0)=s_{i,j};\forall
j\in[n_{i}];i\in[n];\end{aligned}\right.$ (25)

Observe that since it involves constraints on both the derivatives and
integrals, this maybe modelled as a differential integral linear program
(DILP) and our weak duality framework may be a useful tool in analysing the
same.

####  A.8.2 A problem from control theory

In control theory [31], we often have a state $\textbf{x}(t)$ whose evolution
is given by a differential equation. We redefine the following equation from
[31, Chapter 4] below to characterise its evolution.

${}\left\\{\begin{aligned}
&\textbf{x}(t)=\textbf{f}(\textbf{x}(t),{\alpha}(t))\\\
&\textbf{x}(0)=x^{0}\end{aligned}\right.$ (26)

Here $x^{0}\in\mathbb{R}^{n}$, $A\in\mathbb{R}^{m}$,
$\textbf{f}:\mathbb{R}^{n}\times
A\rightarrow\mathbb{R},\alpha:[0,\infty)\rightarrow A$ is the control, and
$\textbf{x}:[0,\infty)\rightarrow\mathbb{R}^{n}$ is the response of the
system. Denote the set of admissible controls by
$\mathcal{A}=\\{\alpha(.):[0,\infty)\rightarrow A|\alpha(.)\text{ is
measurable}\\}$

We also introduce the payoff functional $(P)$

$P[\alpha(.)]=\int_{t=0}^{T}r(x(t),\alpha(t))dt+g(x(T))$

,

where the terminal time $T>0$, running payoff $r:\mathbb{R}^{n}\times
A\rightarrow\mathbb{R}$ and terminal payoff
$g:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are given. Observe that if the
function $f(.)$ is linear and the running payoff is linear, we may represent
it as a differential integral linear program.

It may also be typical to have constraints on the the control input $\alpha$,
for example there could be some constraints on its rate of growth or some
constraints on its Lipschitz continuity.

##  Appendix B Proofs of skipped lemmas and theorems

###  B.1 Simulating the server: Detailed proof of Theorem 2.2

We first show it is sufficient to consider mechanisms in which servers
directly return the received signal from the user, thus removing the server
from the picture.

Recall that $\mathcal{P}^{(\epsilon)}_{Z}$ is the set of differential private
mechanisms that adopt signal set $Z$. Then
$\mathcal{P}^{(\epsilon)}_{\mathcal{A}}$ is the set of differential private
mechanisms in which users pick signals from $\mathcal{A}={}^{k}$.

######  Theorem (Restatement of Theorem 2.2).

We have

$\displaystyle
f^{\mathfrak{h}(.)}(\epsilon,k)=\inf_{\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{{}^{k}}}\sup_{u\in\real}\operatorname{\mathbb{E}}_{\textbf{a}\sim
P_{u}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right].$

###### Proof.

Fix $Z,\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{Z},\mathbf{Q}\in\mathcal{Q}_{Z}$
and recall that that $\mathcal{A}={}^{k}$ from Appendix A.1.1. For any
$\mathcal{H}\in\mathcal{F}_{\mathcal{A}}$, let

$\displaystyle\tilde{P}_{u}\left(\mathcal{H}\right)=\operatorname{\mathbb{P}}_{s\sim
P_{u},\textbf{a}\sim Q_{s}}\left(\textbf{a}\in\mathcal{H}\right),$

which is the probability that user $u$ receives a result set in $\mathcal{H}$.

Then for any $u_{1},u_{2}\in\real,\mathcal{H}\in\mathcal{F}_{\mathcal{A}}$, we
have

$\displaystyle\tilde{P}_{u_{1}}\left(\mathcal{H}\right)=\operatorname{\mathbb{P}}_{s\sim
P_{u_{1}},\textbf{a}\sim Q_{s}}\left(\textbf{a}\in\mathcal{H}\right)=$
$\displaystyle\operatorname{\mathbb{E}}_{s\sim
P_{u_{1}}}\left[\operatorname{\mathbb{P}}_{\textbf{a}\sim
Q_{s}}\left(\textbf{a}\in\mathcal{H}\right)\right]$ $\displaystyle=$
$\displaystyle\int_{s\in Z}{\left(\operatorname{\mathbb{P}}_{\textbf{a}\sim
Q_{s}}\left(\textbf{a}\in\mathcal{H}\right)\cdot P_{u_{1}}(ds)\right)}$
$\displaystyle\leq$ $\displaystyle e^{\epsilon\cdot|u_{1}-u_{2}|}\int_{s\in
Z}{\left(\operatorname{\mathbb{P}}_{\textbf{a}\sim
Q_{s}}\left(\textbf{a}\in\mathcal{H}\right)\cdot P_{u_{2}}(ds)\right)}$
$\displaystyle=$ $\displaystyle
e^{\epsilon\cdot|u_{1}-u_{2}|}\operatorname{\mathbb{E}}_{s\sim
P_{u_{2}}}\left[\operatorname{\mathbb{P}}_{\textbf{a}\sim
Q_{s}}\left(\textbf{a}\in\mathcal{H}\right)\right]$ $\displaystyle=$
$\displaystyle e^{\epsilon\cdot|u_{1}-u_{2}|}\operatorname{\mathbb{E}}_{s\sim
P_{u_{2}},\textbf{a}\sim
Q_{s}}\left[\mathbbm{I}\left\\{\textbf{a}\in\mathcal{H}\right\\}\right]$
$\displaystyle=$ $\displaystyle
e^{\epsilon\cdot|u_{1}-u_{2}|}\tilde{P}_{u_{2}}\left(\mathcal{H}\right),$

so $\tilde{\mathbf{P}}\in\mathcal{P}^{(\epsilon)}_{\mathcal{A}}$ because
$\tilde{P}_{u}\left(\cdot\right)\in\mathbb{D}\left(\mathcal{A}\right)$ for any
$u\in\real$.

At the same time,

$\displaystyle\operatorname{\mathbb{E}}_{s\sim P_{u},\textbf{a}\sim
Q_{s}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]=\operatorname{\mathbb{E}}_{\textbf{a}\sim\tilde{P}_{u}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\text{
so we have},$ $\displaystyle
f^{\mathfrak{h}(.)}(\epsilon,k)=\inf_{\mathbf{P}\in\mathcal{P}^{(\epsilon)}_{\mathcal{A}}}\sup_{u\in{\real}}\operatorname{\mathbb{E}}_{\textbf{a}\sim
P_{u}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right].$

∎

It is sufficient to assume the server directly sends back the received signal,
and we care about the user with largest cost

###  B.2 Dual and primal DILPs: Proof of Lemmas 2.6, Lemma 3.4 and 2.7

####  B.2.1 Proof of Lemma 2.6

######  Lemma.

Suppose, $P_{u}$ has a probability density function given by
$g(u,.):\mathbb{R}^{k}\rightarrow\mathbb{R}$ for every $u\in\mathbb{R}$. Then,
$P$ satisfies $\epsilon$-geographic differential privacy iff
$\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)\leq\epsilon
g(u,\textbf{x})\text{ }\forall u\in\mathbb{R};\forall x\in\mathbb{R}^{k}$
171717$\underline{g}_{u}(u,\textbf{x})$, $\overline{g}_{u}(u,\textbf{x})$
denote the lower and upper partial derivative w.r.t. $u$

###### Proof.

We first prove the only if statement.

Here assuming $\epsilon$\- geographic differential privacy, we prove the
desired constraint on $g(u,.)$.

Observe that since, $\\{P_{u}\\}_{u\in\mathbb{R}}$ satisfies $\epsilon$ \-
geographic-differential privacy, we must have $g(u_{1},\textbf{x})\leq
e^{\epsilon|u_{1}-u_{2}|}g(u_{2},\textbf{x})$.

Thus, applying $\log$ on both sides we get [assuming $g(u,x)\neq 0$],

$\displaystyle\log g(u+\delta u,\textbf{x})-\log
g(u,\textbf{x})\leq\epsilon|\delta u|$ $\displaystyle\implies$
$\displaystyle\frac{\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)}{g(u,\textbf{x})}\leq\epsilon$

The last implication follows on limiting $\delta u$ towards zero and applying
the lower and upper limits respectively and thus we prove the only if
statement.

However, if $g(u,x)=0$, we get the following

$\displaystyle g(u+\delta u,\textbf{x})-g(u,x)\leq 0$ $\displaystyle\implies$
$\displaystyle{\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)}\leq
0$

The last inequality follows on applying $\delta u$ tending to 0 and applying
upper and lower limits respectively.

We now prove the if statement.

Here assuming,
$\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)\leq\epsilon
g(u,\textbf{x})$ we prove $\epsilon$-geographic differential privacy.

We first show that $g(u,\textbf{x})$ is continuous in $u$. Observe that
$\liminf\limits_{\delta u\to 0}g(u+\delta u)-g(u)=\lim\limits_{\delta u\to
0}\delta u\times\liminf\limits_{\delta u\to 0}\frac{g(u+\delta u)-g(u)}{\delta
u}=0$ as $|\underline{g}_{u}(u,\textbf{x})|=|\liminf\limits_{\delta u\to
0}\frac{g(u+\delta u)-g(u)}{\delta u}|\leq\epsilon g(u,\textbf{x})$.
Similarly, using the bound on upper derivative, we show that
$\limsup\limits_{\delta u\to 0}g(u+\delta u)-g(u)=0$ and thus, we have
continuity of $g(u,\textbf{x})$ at $u$ for every $u\in\mathbb{R}^{k}$.

We first prove assuming $g(u,x)\neq 0\forall u\in\mathbbm{R}$. Now consider
$u_{1}>u_{2}$ for some $u_{1},u_{2}\in\mathbb{R}$.

$\displaystyle\log g(u_{1},\textbf{x})-\log
g(u_{2},\textbf{x})\leq\int_{u=u_{2}}^{u_{1}}\frac{\overline{g}_{u}(u,\textbf{x})}{g(u,\textbf{x})}\leq\epsilon(u_{1}-u_{2})$

The first inequality follows since we use an upper derivative.

$\displaystyle\log g(u_{1},\textbf{x})-\log
g(u_{2},\textbf{x})\geq\int_{u=u_{2}}^{u_{1}}\frac{\underline{g}_{u}(u,\textbf{x})}{g(u,\textbf{x})}\geq-\epsilon(u_{1}-u_{2})$

Thus, we get $g(u_{1},\textbf{x})\leq
e^{\epsilon|u_{1}-u_{2}|}g(u_{2},\textbf{x})$ on taking exponent on both sides

We now consider the other case that $g(u,\textbf{x})=0$ for some
$u\in\mathbbm{R}$. We now show that this implies $g(u,\textbf{x})=0\text{
}\forall u\in\mathbbm{R}$. Suppose not and there exists some $u_{1}$ s.t.
$g(u_{1},\textbf{x})>0$ and consider the largest $u<u_{1}$ s.t.
$g(u,\textbf{x})=0$ (call it $u_{0}$)

Now, observe the following observe that we define the limits over extended
reals i.e. $\mathbbm{R}\cup\\{-\infty,\infty\\}$. Observe that

$\displaystyle\lim\limits_{u\to u_{1}}g(u,\textbf{x})$
$\displaystyle=\lim\limits_{u\to
u_{0}}g(u,\textbf{x})+\lim\limits_{\begin{subarray}{c}d^{l}\to u_{0}\\\
d^{u}\to u_{1}\end{subarray}}(\log g(d^{u},\textbf{x})-\log
g(d^{l},\textbf{x}))$ $\displaystyle\leq\lim\limits_{u\to
u_{0}}g(u,\textbf{x})+\int_{u=u_{0}}^{u_{1}}\frac{\overline{g}_{u}(u,\textbf{x})}{g(u,\textbf{x})}$
$\displaystyle{\leq}\lim\limits_{u\to
u_{0}}g(u,\textbf{x})+\epsilon(u_{1}-u_{0})$
$\displaystyle\overset{(a)}{=}-\infty+\epsilon(u_{1}-u_{0})=-\infty$

$(a)$ follows from the fact that $g(u,\textbf{x})$ is continuous in $u$ and
$g(u_{0},\textbf{x})=0$.

Since, $g(u,\textbf{x})$ is a continuous function, this implies that
$g(u_{1},\textbf{x})=0$. Since we can make this argument for every
$u_{1}\in\mathbbm{R}$, we argue that $g(u,\textbf{x})=0\text{ }\forall
u\in\mathbbm{R}$ and thus satisfy the condition of $\epsilon$-geographic DP.

∎

####  B.2.2 Proof of Lemma 3.4

######  Lemma.

Suppose, $P_{u}$ has a probability density function given by
$g(u,.):\mathbb{R}^{k}\rightarrow\mathbb{R}$ for every $u\in\mathbb{R}$. Then,
$P$ satisfies $\mathfrak{g}(.)$-geographic differential privacy iff
$\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)\leq\mathfrak{g}^{\prime}(0)g(u,\textbf{x})\text{
}\forall u\in\mathbb{R};\forall x\in\mathbb{R}^{k}$
181818$\underline{g}_{u}(u,\textbf{x})$, $\overline{g}_{u}(u,\textbf{x})$
denote the lower and upper partial derivative w.r.t. $u$ whenever
$\mathfrak{g}(.)$ satisfies Assumption 3.1.

###### Proof.

We first prove the only if statement.

Assuming $\mathfrak{g}(.)$ geographic differential privacy we prove the
desired constraint on $g(u,.)$.

Observe that since, $\\{P_{u}\\}_{u\in\mathbb{R}}$ satisfies $\mathfrak{g}(.)$
geographic-differential privacy, we must have $g(u_{1},\textbf{x})\leq
e^{\mathfrak{g}(|u_{1}-u_{2}|)}g(u_{2},\textbf{x})$.

Thus, applying $\log$ on both sides we get,

$\displaystyle\log g(u+\delta u,\textbf{x})-\log
g(u,\textbf{x})\leq\mathfrak{g}(|\delta u|)$ $\displaystyle\implies$
$\displaystyle\frac{\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)}{g(u,\textbf{x})}\leq\mathfrak{g}^{\prime}(0)$

The last implication follows on limiting $\delta u$ towards zero and
$\mathfrak{g}(0)=0$ thus, applying the lower and upper limits respectively and
thus we prove the only if statement.

However, if $g(u,x)=0$, we get the following

$\displaystyle g(u+\delta u,\textbf{x})-g(u,x)\leq 0$ $\displaystyle\implies$
$\displaystyle{\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)}\leq
0$

The last inequality follows on applying $\delta u$ tending to 0 and applying
upper and lower limits respectively.

We now prove the if statement.

Here assuming
$\max(|\overline{g}_{u}(u,\textbf{x})|,|\underline{g}_{u}(u,\textbf{x})|)\leq\mathfrak{g}^{\prime}(0)g(u,\textbf{x})$,
we prove $\mathfrak{g}(.)$-geographic differential privacy.

We first show that $g(u,\textbf{x})$ is continuous in $u$. Observe that
$\liminf\limits_{\delta u\to 0}g(u+\delta u)-g(u)=\lim\limits_{\delta u\to
0}\delta u\times\liminf\limits_{\delta u\to 0}\frac{g(u+\delta u)-g(u)}{\delta
u}=0$ as $|\underline{g}_{u}(u,\textbf{x})|=|\liminf\limits_{\delta u\to
0}\frac{g(u+\delta u)-g(u)}{\delta u}|\leq\epsilon g(u,\textbf{x})$.
Similarly, using the bound on upper derivative, we show that
$\limsup\limits_{\delta u\to 0}g(u+\delta u)-g(u)=0$ and thus, we have
continuity of $g(u,\textbf{x})$ at $u$ for every $u\in\mathbb{R}^{k}$.

We first prove assuming $g(u,x)\neq 0\forall u\in\mathbbm{R}$. Now consider
$u_{1}>u_{2}$ for some $u_{1},u_{2}\in\mathbb{R}$.

$\displaystyle\log g(u_{1},\textbf{x})-\log
g(u_{2},\textbf{x})\overset{(a)}{\leq}\int_{u=u_{2}}^{u_{1}}\frac{\overline{g}_{u}(u,\textbf{x})}{g(u,\textbf{x})}\leq$
$\displaystyle\mathfrak{g}^{\prime}(0)(u_{1}-u_{2})$
$\displaystyle\overset{(b)}{\leq}\mathfrak{g}(u_{1}-u_{2})$

The first inequality $(a)$ follows since we use an upper derivative and the
inequality $(b)$ follows from the fact that $\mathfrak{g}(.)$ is a convex
function and $\mathfrak{g}(0)=0$ as defined in Section 3.1.

$\displaystyle\log g(u_{1},\textbf{x})-\log
g(u_{2},\textbf{x})\geq\int_{u=u_{2}}^{u_{1}}\frac{\underline{g}_{u}(u,\textbf{x})}{g(u,\textbf{x})}\geq$
$\displaystyle-\mathfrak{g}^{\prime}(0)(u_{1}-u_{2})$
$\displaystyle\overset{(c)}{\geq}-\mathfrak{g}(u_{1}-u_{2})$

Inequality $(c)$ follows from the fact that $\mathfrak{g}(.)$ is a convex
function. Thus, we get $g(u_{1},\textbf{x})\leq
e^{-\mathfrak{g}(|u_{1}-u_{2}|)}g(u_{2},\textbf{x})$ on taking exponent on
both sides.

We now consider the other case that $g(u,\textbf{x})=0$ for some
$u\in\mathbbm{R}$. We now show that this implies $g(u,\textbf{x})=0\text{
}\forall u\in\mathbbm{R}$. Suppose not and there exists some $u_{1}$ s.t.
$g(u_{1},\textbf{x})>0$ and consider the largest $u<u_{1}$ s.t.
$g(u,\textbf{x})=0$ (call it $u_{0}$)

Now, observe the following observe that we define the limits over extended
reals i.e. $\mathbbm{R}\cup\\{-\infty,\infty\\}$. Observe that

$\displaystyle\lim\limits_{u\to u_{1}}g(u,\textbf{x})$
$\displaystyle=\lim\limits_{u\to
u_{0}}g(u,\textbf{x})+\lim\limits_{\begin{subarray}{c}d^{l}\to u_{0}\\\
d^{u}\to u_{1}\end{subarray}}(\log g(d^{u},\textbf{x})-\log
g(d^{l},\textbf{x}))$ $\displaystyle\leq\lim\limits_{u\to
u_{0}}g(u,\textbf{x})+\int_{u=u_{0}}^{u_{1}}\frac{\overline{g}_{u}(u,\textbf{x})}{g(u,\textbf{x})}$
$\displaystyle{\leq}\lim\limits_{u\to
u_{0}}g(u,\textbf{x})+\epsilon(u_{1}-u_{0})$
$\displaystyle\overset{(a)}{=}-\infty+\epsilon(u_{1}-u_{0})=-\infty$

$(a)$ follows from the fact that $g(u,\textbf{x})$ is continuous in $u$ and
$g(u_{0},\textbf{x})=0$.

Since, $g(u,\textbf{x})$ is a continuous function, this implies that
$g(u_{1},\textbf{x})=0$. Since we can make this argument for every
$u_{1}\in\mathbbm{R}$, we argue that $g(u,\textbf{x})=0\text{ }\forall
u\in\mathbbm{R}$ and thus satisfy the condition of
$\mathfrak{g}(.)$-geographic DP.

∎

####  B.2.3 Proof of Lemma 2.7

To prove this lemma, we first show another lemma showing a necessary and
sufficient condition for $\epsilon$-geographic differential privacy of
distributions $\\{P_{u}\\}_{u\in\mathbb{R}}$ assuming that it has a
probability density function.

We now restate and prove Lemma 2.5

######  Lemma.

Given any mechanism $\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\textbf{R}^{k}}$
(satisfying $\epsilon$-geographic differential privacy), we can construct a
sequence of mechanisms
$\textbf{P}^{(\eta)}\in\mathcal{P}^{(\epsilon)}_{\textbf{R}^{k}}$ with a
bounded probability distribution function for every $u\in\mathbbm{R}$ such
that $\textbf{P}^{(\eta)}$ is an arbitrary cost approximation of mechanism
$\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\textbf{R}^{k}}$.

###### Proof.

For any mechanism P belonging to the set
$\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$, we can construct alternative
mechanisms $\textbf{P}^{(\eta)}$ within the same set, aiming to provide an
arbitrary cost approximation of the original mechanism.

For this, we borrow ideas from theory of mollifier in [34]. We now give a
construction ${P}^{(\eta)}_{u}$ with a probability density function
$\rho_{V}(u,.):\mathbb{R}^{k}\rightarrow\mathbb{R}$ for every
$u\in\mathbb{R}$.

For $\eta>0$ and $\textbf{a}\in R^{k}$, define the $\eta$-ball of a, denoted
by $\mathcal{B}_{\textbf{a},\eta}$, to be

$\displaystyle\mathcal{B}_{A,\eta}:=\left\\{\textbf{a}^{\prime}\in
R^{k}:|\textbf{a}-\textbf{a}^{\prime}\|_{\infty}<\eta\right\\},$

and use $\left|\mathcal{B}_{\textbf{a},\eta}\right|$ to denote the Lebesgue
measure (corresponding to the volume) of $\mathcal{B}_{A,\eta}$. Note that
there exists a real number, denoted by
$\left|\mathcal{B}_{\eta}\right|\in\mathbb{R}$, satisfying
$\left|\mathcal{B}_{\textbf{a},\eta}\right|=\left|\mathcal{B}_{\eta}\right|$
for any $\textbf{a}\in\mathbb{R}^{k}$ as this volume is independent of a.

Fix $\eta>0$, we define another probability measure ${P}^{(\eta)}_{u}$ which
has density $\rho_{V}(u,\textbf{a})$ for all $\textbf{a}\in\mathbb{R}^{k}$.

$\displaystyle\rho_{V}\left(u,\textbf{a}\right):=\frac{{P}_{u}({\mathcal{B}_{\textbf{a},\eta}})}{\left|\mathcal{B}_{\eta}\right|}.$

$\rho_{V}(u,.)$ defines a valid probability measure because

$\displaystyle\int_{\mathbb{R}^{k}}\rho_{V}(u,\textbf{a})d\textbf{a}=$
$\displaystyle\int_{\mathbb{R}^{k}}\frac{P_{u}{(\mathcal{B}_{\textbf{a},\eta}})}{\left|\mathcal{B}_{\eta}\right|}d\textbf{a}$
$\displaystyle=$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int_{\textbf{a}\in\mathbb{R}^{k}}\int_{\textbf{b}\in\mathcal{B}_{\textbf{a},\eta}}P_{u}({d\textbf{b}})d\textbf{a}$
$\displaystyle=$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int_{\textbf{b}\in\mathbb{R}^{k}}P_{u}({d\textbf{b}})\int_{\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}}d\textbf{a}$
$\displaystyle=$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int_{\textbf{b}\in\mathbb{R}^{k}}P_{u}({d\textbf{b}})\left|\mathcal{B}_{\eta}\right|=1.$

To show $\textbf{P}^{(\eta)}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$, we
now show

$\rho_{V}(u_{1},\textbf{a})=\frac{{P}_{u_{1}}(\mathcal{B}_{\textbf{a},\eta})}{\left|\mathcal{B}_{\eta}\right|}\leq\frac{{P}_{u_{2}}(\mathcal{B}_{\textbf{a},\eta})e^{\epsilon|u_{1}-u_{2}|}}{\left|\mathcal{B}_{\eta}\right|}=e^{\epsilon|u_{1}-u_{2}|}\rho_{V}(u_{2},\textbf{a})$

This implies for any measurable set $S$ in $\mathbb{R}^{k}$, we have
${P}^{(\eta)}_{u_{1}}(S)\leq e^{\epsilon|u_{1}-u_{2}|}{P}^{(\eta)}_{u_{2}}(S)$
and thus satisfies $\epsilon$-geographic differential privacy and also implies
that that $\rho_{V}(u,\textbf{a})$ is continuous in $u$ for every
$\textbf{a}\in\mathbb{R}^{k}$.

Also observe that $\rho_{V}(u,\textbf{a})$ is always bounded above by
$\frac{1}{|B_{\eta}|}$ as ${P}_{u}(.)$ is a probability measure. Observe that
since, we showed that $\rho_{V}(.,\textbf{a})$ is Riemann integrable and is
non-negative for every $\textbf{a}\in\mathbb{R}^{k}$ and
$\rho_{V}(u,\textbf{a})$ is continuous in $u$, we showed that $\rho_{V}(.,.)$
is Riemann integrable over $\mathbbm{R}\times\mathbbm{R}^{k}$. 191919Observe
that this integral may go to $\infty$ but is always defined.

In the next set of equations (34) and (42), we upper and lower bound
$\mathbb{E}_{\textbf{a}\sim{P}^{(\eta)}_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]$
and then apply limit $\eta\to 0$ on both the upper and lower bounds in
Equations (B.2.3) and (49) to show that $\textbf{P}^{(\eta)}$ arbitrarily
approximates P in Equation (50).

$\displaystyle\mathbb{E}_{\textbf{a}\sim{P}^{(\eta)}_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]=$
$\displaystyle\int_{\textbf{a}\in\mathbb{R}^{k}}\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\rho_{V}(u,\textbf{a})d\textbf{a}$
(27) $\displaystyle=$
$\displaystyle\int_{\textbf{a}\in\mathbb{R}^{k}}\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\frac{P_{u}(\mathcal{B}_{\textbf{a},\eta})}{\left|\mathcal{B}_{\eta}\right|}d\textbf{a}$
(28) $\displaystyle=$
$\displaystyle\int_{\textbf{a}\in\mathbb{R}^{k}}\int_{\textbf{b}\in\mathcal{B}_{\textbf{a},\eta}}\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\frac{P_{u}(d\textbf{b})}{\left|\mathcal{B}_{\eta}\right|}d\textbf{a}$
(29) $\displaystyle=$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int_{\textbf{b}\in\mathbb{R}^{k}}\int_{\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}}P_{u}(d\textbf{b})\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)d\textbf{a}$
(30) $\displaystyle\leq$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int_{\textbf{b}\in\mathbb{R}^{k}}\int_{\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}}\left(\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}(|u-a|+\eta)\right)d\textbf{a}P_{u}(d\textbf{b})$
(31) $\displaystyle=$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int_{\textbf{b}\in\mathbb{R}^{k}}\int_{\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}}\left(\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}(|u-a|+\eta)\right)d\textbf{a}P_{u}(d\textbf{b})$
(32) $\displaystyle=$
$\displaystyle\int_{\textbf{b}\in\mathbb{R}^{k}}\left(\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}(|u-a|+\eta)\right)P_{u}(d\textbf{b})$
(33) $\displaystyle=$ $\displaystyle\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)\right]$
(34)

where Inequality 31 holds because for any $\textbf{b}\in\mathbb{R}^{k}$ and
$\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}$, we have

$\displaystyle\min_{a\in\texttt{Set}(\textbf{a})}(|u-a|)\overset{(a)}{\leq}\min_{a\in\texttt{Set}(\textbf{b})}(|u-a|)+\eta.$
$\displaystyle\overset{(b)}{\implies}$
$\displaystyle\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\leq\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}(|u-a|+\eta)$

$(a)$ follows from triangle inequality and the fact that
$|a_{i}-b_{i}|\leq\eta\text{ }\forall i\in[k]$. $(b)$ follows since
$\mathfrak{h}$ is monotonic.

Equality $\eqref{eq:mct}$ follows from monotone convergence theorem since
$\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}(|u-a|+\eta)$ is monotonic in
$\eta$ as $\mathfrak{h}(.)$ is monotonic.

We now show that
$\mathbb{E}_{\textbf{a}\sim{P}^{(\eta)}_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\geq\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(\left[|u-a|-\eta\right]_{+})\right]$.
Note that in the following expression $[x]_{+}$ denotes $\max(x,0)$.

$\displaystyle\mathbb{E}_{\textbf{a}\sim{P}^{(\eta)}_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]=$
$\displaystyle\int_{\textbf{a}\in\mathbb{R}^{k}}\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\rho_{V}(u,\textbf{a})d\textbf{a}$
(35) $\displaystyle=$
$\displaystyle\int_{\textbf{a}\in\mathbb{R}^{k}}\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\frac{P_{u}(\mathcal{B}_{\textbf{a},\eta})}{\left|\mathcal{B}_{\eta}\right|}d\textbf{a}$
(36) $\displaystyle=$
$\displaystyle\int_{\textbf{a}\in\mathbb{R}^{k}}\int_{\textbf{b}\in\mathcal{B}_{\textbf{a},\eta}}\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\frac{P_{u}(d\textbf{b})}{\left|\mathcal{B}_{\eta}\right|}d\textbf{a}$
(37) $\displaystyle=$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int_{\textbf{b}\in\mathbb{R}^{k}}\int_{\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}}P_{u}(d\textbf{b})\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)d\textbf{a}$
(38) $\displaystyle\geq$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int\limits_{\textbf{b}\in\mathbb{R}^{k}}\int\limits_{\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}}\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}\left(\left[|u-a|-\eta\right]_{+}\right)d\textbf{a}P_{u}(d\textbf{b})$
(39) $\displaystyle=$
$\displaystyle\frac{1}{\left|\mathcal{B}_{\eta}\right|}\int\limits_{\textbf{b}\in\mathbb{R}^{k}}\int\limits_{\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}}\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}\left(\left[|u-a|-\eta\right]_{+}\right)d\textbf{a}P_{u}(d\textbf{b})$
(40) $\displaystyle=$
$\displaystyle\int_{\textbf{b}\in\mathbb{R}^{k}}\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}\left(\left[|u-a|-\eta\right]_{+}\right)P_{u}(d\textbf{b})$
(41) $\displaystyle=$ $\displaystyle\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(\left[|u-a|-\eta\right]_{+}\right)\right]$
(42)

where Inequality 39 holds because for any $\textbf{b}\in\mathbb{R}^{k}$ and
$\textbf{a}\in\mathcal{B}_{\textbf{b},\eta}$, we have

$\displaystyle\min_{a\in\texttt{Set}(\textbf{a})}(|u-a|)\overset{(a)}{\geq}\min_{a\in\texttt{Set}(\textbf{b})}\left[(|u-a|)-\eta\right]_{+}.$
$\displaystyle\overset{(b)}{\implies}$
$\displaystyle\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\geq\min_{a\in\texttt{Set}(\textbf{b})}\mathfrak{h}\left(\left[|u-a|-\eta\right]_{+}\right)$

$(a)$ follows from triangle inequality and the fact that
$|a_{i}-b_{i}|\leq\eta\text{ }\forall i\in[k]$ and the fact $(b)$ follows
since $\mathfrak{h}$ is monotonic and $\mathfrak{h}(0)=0$

Now observe that $\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(\left[|u-a|-\eta\right]_{+}\right)\right]$
and $\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)\right]$
is continuous in $\eta$ for every $u$. Observe that each of these functions is
monotonic in $\eta$.

Now we bound $\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)\right]$
below by some linear function on
$\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]$
for every $u\in\mathbb{R}$ and use it to show the convergence of the supremum
in (B.2.3) and a similar approach for $\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)\right]$.
Let us denote the Lipschitz constant of $\log\mathfrak{h}(.)$ in
$[\mathcal{B},\infty)$ by $M$. We now split $\mathbb{R}^{k}$ into two sets
$\textbf{a}_{1}(u)=\\{\textbf{a}:\min\limits_{a\in\texttt{Set}(\textbf{a})}|u-a|>\mathcal{B}\\}$
[recall from definition of $\mathcal{B}$ from Property 3] and
$\textbf{a}_{2}(u)=\\{\textbf{a}:\min\limits_{a\in\texttt{Set}(\textbf{a})}|u-a|\leq\mathcal{B}\\}$.
With this, we now define

${}\kappa(\eta):=\sup_{\mathfrak{v}\in[0,\mathcal{B}]}\mathfrak{h}(\mathfrak{v}+\eta)-\mathfrak{h}(\mathfrak{v})$
(43)

Observe that this supremum is finite for every $\eta$ since, the interval is
closed and bounded and the function is continuous. We can now apply Dini’s
theorem [49, Theorem 7.13] to conclude $\kappa(\eta)$ goes to 0 as $\eta$
tends to 0. This argument goes as follows.

  * •

Observe that $\mathfrak{h}(\mathfrak{v}+\eta)$ converges point-wise in
$\mathfrak{v}$ monotonically to $\mathfrak{h}(\mathfrak{v})$

  * •

Since, $[0,\mathcal{B}]$ is a compact set(closed and bounded), we can argue
that $\mathfrak{h}(\mathfrak{v}+\eta)$ uniformly converges to
$\mathfrak{h}(\mathfrak{v})$ for $\mathfrak{v}\in[0,\mathcal{B}]$ implying
convergence of $\kappa(\eta)$ to 0 as $\eta\to 0$.

Now observe for every $\textbf{a}\in\textbf{a}_{1}(u)$, we get the following

$\displaystyle{}\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}\left(|u-a|+\eta\right)=\mathfrak{h}\left(\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta\right)$
$\displaystyle\overset{(a)}{\leq}\mathfrak{h}\left(\min\limits_{a\in\texttt{Set}(\textbf{a})}|u-a|\right)+\kappa(\eta)$
$\displaystyle=\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)+\kappa(\eta)$
(44)

Observe that $(a)$ follows from Definition 43 since
$\min\limits_{a\in\texttt{Set}(\textbf{a})}|u-a|\leq\mathcal{B}$ and the
equality follows since $\mathfrak{h}(.)$ is monotonic thus,
$\mathfrak{h}(\min(a,b))=\min\left(\mathfrak{h}(a),\mathfrak{h}(b)\right)$