theoremTheorem lemmaLemma corollaryCorollary propositionProposition

# Privately Answering Queries on Skewed Data via Per Record Differential
Privacy

Jeremy Seeman⋆, William Sexton⋆, David Pujol⋆, Ashwin Machanavajjhala⋆ ⋆
Tumult Labs, Durham, NC jeremy.seeman, william.sexton, david.pujol,
<EMAIL_ADDRESS>
###### Abstract.

We consider the problem of the private release of statistics (like aggregate
payrolls) where it is critical to preserve the contribution made by a small
number of outlying large entities. We propose a privacy formalism, per-record
zero concentrated differential privacy (PzCDP), where the privacy loss
associated with each record is a public function of that record’s value.
Unlike other formalisms which provide different privacy losses to different
records (ebadi_differential_2015; jorgensen_2015_conservative), PzCDP’s
privacy loss depends explicitly on the confidential data. We define our
formalism, derive its properties, and propose mechanisms which satisfy PzCDP
that are uniquely suited to publishing skewed or heavy-tailed statistics,
where a small number of records contribute substantially to query answers.
This targeted relaxation helps overcome the difficulties of applying standard
DP to these data products.

##  1\. Introduction

We consider the problem of releasing private aggregate statistics on data with
highly skewed attributes. These kinds of data occur frequently in practice,
for example the Census Bureau’s County Business Patterns (CBP) dataset (cbp),
USDA’s Census of Agriculture (agcensus), and many IRS data products like the
Corporation Sourcebook (irstaxstats). Moreover, the aggregate statistics are
highly sensitive to contributions by a single (or small set of) units. For
example, CBP takes business establishments as its unit of analysis, where it
is common that one establishment (like a large retailer or hospital)
contributes to the majority of the jobs in a rural area. Regardless of their
large contributions, the privacy of these units is often protected under
federal law (title13; title26). Current disclosure avoidance methods, both
traditional and modern, either fail to provide strong privacy guarantees or
high utility. Classical statistical disclosure limitation techniques like
complementary cell suppression using the p% rule and EZS noise
(OMalley2007PracticalCI; evans1996using) offer no formal privacy guarantee and
can deterministically reveal information about large contributions.
Differentially private (DP) techniques (dwork_calibrating_2006;
dwork_algorithmic_2013) that globally bound the contribution of any one unit
to published statistics require that highly skewed data are either truncated
or suppressed, resulting in unreasonably large bias or unreasonably large
noise injected into published statistics.

Table 1 gives one such data example. Suppose we wanted to execute the
following SQL query using DP:

SELECT SUM(Employees) FROM table1 WHERE Industry = ’Retail’

DP requires bounding the contribution of any one record to the summation,
enforced by truncating large values to a clamping bound. Setting this bound
too high will require unreasonably large additional noise for DP, whereas
setting this bound too low will add unreasonably large bias by truncating
record 4. In Section 6.2, we further demonstrate how this problem makes global
DP methods ill-suited for summations on skewed data.

ID | Industry | Employees
---|---|---
1 | Retail | 5
2 | Retail | 5
3 | Retail | 10
4 | Retail | 1000
5 | Technology | 10000
6 | Services | 5
7 | Hospitality | 5
Table 1. Sample of skewed data containing a subset of a much larger collection
of rows.

Problems like these affect many high-sensitivity queries, where mitigating the
effect of one record can have exorbitant effects on utility. For example, DP
partition selection algorithms (desfontaines_differentially_2022) used in
keyset selection for group-by queries can neglect the impact of individual
records with important, outlying attributes. In Table 1, if we were to execute
the query “SELECT Count(*) FROM Table1 GROUP BY Industry” using DP, the
probability of including ”Services” and ”Technology” would be the same,
despite the fact that the majority of employees in the dataset work in
Technology. Issues like these stem from inherent connections between DP and
robustness (dworkPrivRobust; liu2021differential; asi2023robustness), where DP
techniques cannot successfully answer inherently non-robust queries.

###  1.1. Contributions

In these settings where standard DP tools do not work, we might consider a
relaxation of DP that applies different privacy loss bounds to different
units. For example, in Table 1, we might allow additional privacy loss for
record 5 (Technology establishment with 10000 employees) than record 1 (Retail
establishment with 5 employees), especially because record 5 is an influential
record which describes more individuals than record 1. However, existing
techniques restrict how this mapping between records and privacy losses can
occur. Personalized DP (jorgensen_2015_conservative) requires that the mapping
between units and their privacy losses is public knowledge, but we might
require this mapping to non-trivially depend on confidential data.
Alternatively, individual DP (ebadi_differential_2015) requires that this
mapping is confidential, but this limits our ability to be methodologically
transparent or describe how privacy losses differ across units.

We propose per-record zero-concentrated DP (PzCDP), which aims to address
these problems. We publicly release what we call a ”policy function” $P$ that
maps each possible (hypothetical) record to a maximum privacy loss that said
record could incur. The form of $P$ can depend on the record’s value, allowing
different privacy losses for outlying units when necessary to maintain
reasonable data utility. We next propose an algorithm methodology, called unit
splitting, which indirectly sets $P$ by executing traditional zCDP
(bun_concentrated_2016) algorithms on a preprocessed version of the data where
influential records are split into sub-records. Our formalism and mechanisms
are ideal for non-interactive query workloads involving highly skewed data; as
a result, our approach is a candidate methodology for data products like CBP
(cbp-demo). Our contributions are as follows:

  * •

In Sections 3 and 4, we formally define PzCDP and demonstrate its formal
properties, such as sequential and parallel composition.

  * •

In Section 5, we propose unit splitting, a pre-processing step which allows us
to compute DP mechanisms on the output so that the final results satisfy
$P$-PzCDP.

  * •

In Section 6, we apply these techniques to three datasets: one simulated
heavy-tailed dataset, one USDA dataset, and CBP synthetic data provided to us
by the U.S. Census Bureau. We empirically demonstrate how small changes in
privacy loss significantly improve utility for these skewed datasets.

###  1.2. Related work

Among the hundreds of existing formal privacy definitions
(desfontaines_sok_2020), many formalisms aim to provide privacy guarantees
which differ across units (alaggan_2016_heterogeneous;
jorgensen_2015_conservative; ebadi_differential_2015; ghosh_selling_2015) or
realized datasets (papernot2018scalable; wang_per-instance_2019). These are
often used in service of broader global DP goals, such as publishing data-
dependent privacy guarantees (redberg2021privately) or establishing privacy
filters for adaptive composition (feldman_individual_2021;
whitehouse2022fully). Our work differs in a few key areas. First, we consider
explicit dependencies between individual privacy loss parameters and
confidential record values, relaxing strong assumptions made about this
relationship in previous work (alaggan_2016_heterogeneous;
jorgensen_2015_conservative; ebadi_differential_2015; ghosh_selling_2015;
papernot2018scalable; wang_per-instance_2019; redberg2021privately). Second,
we consider data-dependent privacy guarantees without global bounds on privacy
loss; we consider cases where the policy loss can become arbitrarily large for
certain records. Such relaxations are necessary to address problems that arise
with skewed data, for which global DP guarantees cannot provide reasonable
privacy loss and utility simultaneously. We provide a detailed comparison
between PzCDP and closely related definitions in Section 4.1.

##  2\. Preliminaries

###  2.1. Data Model

We assume a single table schema $R(a_{1},a_{2}\dots a_{d})$ where
$\mathcal{A}=\\{a_{1},a_{2}\dots a_{d}\\}$ denotes the set of attributes $R$.
Each attribute in $a_{i}$ has domain, $\operatorname{Dom}(a_{i})$, which need
not be finite or bounded. The full domain of $R$ is
$\operatorname{Dom}(R)=\operatorname{Dom}(a_{1})\times\operatorname{Dom}(a_{2})\times\dots\operatorname{Dom}(A_{d})$.

A database $D$ is an instance of relation $R$. $D$ is a multi-set whose
elements are tuples in $\operatorname{Dom}(R)$, i.e. a tuple can be written as
$r=(x_{1},\ldots,x_{d})$ where $x_{i}\in\operatorname{Dom}(a_{i})$. The number
of tuples in $D$ is denoted as $|D|=n$.

###  2.2. Zero-Concentrated Differential Privacy

Informally, a randomized mechanism $M$ satisfies DP if the output distribution
of the mechanism does not change too much with the addition or removal of a
single unit’s record. We focus on a variant of DP called $\rho$-Zero-
Concentrated Differential Privacy (zCDP)(bun_concentrated_2016), but all the
following results could similarly be adapted for $\epsilon$-DP
(dwork_calibrating_2006). This DP formulation bounds the Rényi Divergence of
output distributions induced by changes in a single record. We first begin by
defining neighboring databases.

###### Definition 0 (Neighboring Databases).

Two databases $D$ and $D^{\prime}$ are considered neighboring databases if $D$
and $D^{\prime}$ differ by adding or removing at most one row. We denote this
relationship by $D^{\prime}\approx D$.

We call the maximum change to a function due to the removal or addition of a
single row the sensitivity of the function. We will often refer to a single
row in a database as a “unit” and use the terms interchangeably.

###### Definition 0 ($\ell_{2}$-Sensitivity).

Given a vector function $f$, the sensitivity of $f$ is $sup_{D^{\prime}\approx
D}{|f(D)-f(D^{\prime})|_{2}}$, where $|\cdot|_{2}$ is the $\ell_{2}$-norm, and
is denoted by $\Delta$.

From here, we can define the formal notion of privacy under zCDP.

###### Definition 0 (Zero-Concentrated Differential Privacy).

A randomized mechanism $M$ satisfies $\rho$-zCDP for $\rho\geq 0$ if, for any
two neighboring databases $D$ and $D^{\prime}$ and for all values of
$\alpha\in(1,\infty)$:

$D_{\alpha}(M(D)\|M(D^{\prime}))\leq\rho\alpha$

where $D_{\alpha}(\cdot\|\cdot)$ is the Rényi divergence of order $\alpha$
between two probability distributions.

zCDP ensures that no unit contributes too much to the final output of the
mechanism by bounding the difference with or without their particular record.
The parameter $\rho$ is often called the privacy loss and refers to the amount
of information that can be learned about any particular individual. A high
value of $\rho$ means weaker privacy protection, while a lower value of $\rho$
denotes a stronger privacy protection.

zCDP has a number of properties that are often used to construct more complex
mechanisms. These are composability, post-processing invariance, and group
privacy. Composition allows for multiple private mechanisms to compose
together to create a large mechanism which still satisfies zCDP.

###### Theorem 2.4 (zCDP Sequential Composition (bun_concentrated_2016)).

Let $M_{1},M_{2}$ be randomized mechanisms which satisfy $\rho_{1}-$zCDP and
$\rho_{2}-$zCDP respectively. Then the mechanism
$M^{\prime}(D)=(M_{1}(D),M_{2}(D))$ satisfies $(\rho_{1}+\rho_{2})-$zCDP.

Additionally, if a mechanism is run on multiple disjoint sections of the
database, private mechanisms compose with no additional privacy loss.

###### Theorem 2.5 (zCDP Parallel Composition (bun_concentrated_2016)).

Let $M_{1},M_{2}$ be randomized mechanisms which satisfy $\rho_{1}-$zCDP and
$\rho_{2}-$zCDP respectively. Let $D_{1},D_{2}$ be two disjoint subsets of a
database, $D$. The mechanism $M^{\prime}(D)=(M_{1}(D_{1}),M_{2}(D_{2}))$
satisfies $\max(\rho_{1},\rho_{2})-$zCDP.

zCDP also allows for arbitrary post-processing without additional privacy
loss.

###### Theorem 2.6 (zCDP Post-processing (bun_concentrated_2016)).

Let $M$ be a randomized mechanism which satisfies $\rho-$ zCDP. Let
$M^{\prime}(D)=f(M(D))$ for some arbitrary function $f$. Then $M^{\prime}$
satisfies $\rho-$zCDP.

Due to the composition and post-processing theorems, most zCDP mechanisms are
built out of simple primitive mechanisms such as the Gaussian mechanism
(bun_concentrated_2016) which are then post-processed and combined to create
more complex mechanisms.

###### Definition 0 (Gaussian Mechanism (bun_concentrated_2016)).

Let $q$ be a sensitivity $\Delta$ query. Consider the mechanism $M$ that on
input $D$ releases a sample from $\mathcal{N}(q(D),\sigma^{2})$. Then $M$
satisfies$\frac{\Delta^{2}}{2\sigma^{2}}$-zCDP.

Another property of formally private mechanisms is the notion of group
privacy. That is, that the mechanism not only protects the unit but also
protects arbitrary groups of units with a privacy loss that scales in the size
of the group.

###### Theorem 2.8 (zCDP Group Privacy).

Let $M$ be a randomized mechanism which satisfies $\rho-$zCDP. Then $M$
guarantees $(k^{2}\rho)-$zCDP for groups of size $k$. That is, for every set
of neighboring databases $D,D^{\prime}$ differing in up to $k$ entries, and
$\alpha\in(1,\infty)$ we have the following.

$D_{\alpha}(M(D)\|M(D^{\prime}))\leq(k^{2}\rho)\cdot\alpha$

While all the results that follow will use zCDP, they still hold in the
context of pure $\epsilon$-DP.

##  3\. Per-Record Differential Privacy

Here, we introduce Per-Record Zero-Concentrated Differential Privacy (PzCDP),
a relaxation of DP designed for skewed data tasks. This takes the form of a
privacy guarantee that varies as a function of the record’s confidential
value; for example, when records are real-valued positive numbers, we can
consider privacy loss bounds that grow monotonically as a function of these
record values. The key feature of PzCDP is a record dependent policy function
which can be publicly released and analytically captures the privacy loss of a
hypothetical record.

###### Definition 0 (Record-dependent policy function).

A record-dependent policy function $P:\mathcal{T}\rightarrow\mathbb{R}_{\geq
0}$ denotes a maximum allowable privacy loss associated with a particular
record value $r\in\mathcal{T}$, where $\mathcal{T}$ is the universe of
possible records.

This record-dependent policy function differs from other individual privacy
frameworks in that the parameter value $P(r)$ itself depends on the
confidential record values $r$. We allow the functional form of the policy
function $P(\cdot)$ to be made public, but the value of the policy function
$P(r)$ for any record $r$ in the confidential database cannot be made public.
Record-dependent policy functions are inspired by and generalize binary policy
functions of (doudalis_one-sided_2017). Given a policy function, Per-Record
Zero-Concentrated Differential Privacy is defined as follows.

###### Definition 0 ($P$-per-record zero-Concentrated DP ($P$-PzCDP)).

Let $M$ be a randomized algorithm which outputs a random variable $Y$ over a
range $(\mathcal{Y},\mathcal{F}_{Y})$, where $\mathcal{F}_{Y}$ is an
appropriately chosen $\sigma$-algebra. $M$ satisfies $P$-per-record zero-
concentrated differential privacy ($P$-PzCDP) iff $\forall
D,D^{\prime}\in\mathcal{D}$:

$D\ominus D^{\prime}=\\{r\\}\implies d_{\alpha}(M(D)||M(D^{\prime}))\leq\alpha
P(r)\quad\forall\alpha\in(1,\infty)$

where $\mathcal{D}$ is the input database space and $\ominus$ denotes
symmetric difference.

In this definition, the privacy loss associated with each record scales
according to the policy function, as opposed to having equal privacy loss for
all records. Traditional zCDP can be stated as a special case of $P$-PzCDP
where the policy function is a constant.

###### Example 0.

Consider Table 2(a) and a policy function
$P(r)=\rho\left\lceil\frac{r[Employees]}{50}\right\rceil$, where $\rho$ is a
privacy parameter. Under this policy function, Establishment $1$ would receive
$3\rho$ privacy loss since they have $150$ employees, while Establishment 2
would receive $\rho$ privacy loss since it only has $50$ employees.
Establishment $5$ would still receive $\rho$ privacy loss even though it has
less than $50$ employees.

##  4\. Properties of Per-record differential privacy

We demonstrate here that PzCDP satisfies the traditional properties often
associated with Differential Privacy, as well as its variants. First, PzCDP is
closed under post-processing, in that any data independent function computed
on the output of a mechanism which satisfies PzCDP also satisfies PzCDP.

###### Lemma 4.1 (Closure under post-processing).

Given $M:\mathcal{T}^{*}\to\mathcal{Y}$, a $P$-PzCDP mechanism $M$, and any
function $f$, it is the case that $f\circ M$ is also $P$-PzCDP.

PzCDP satisfies basic adaptive sequential composition in that two PzCDP
mechanisms with arbitrary policy functions (chosen prior to running any
mechanism) compose together to satisfy PzCDP in combination.

###### Lemma 4.2 (basic adaptive sequential composition for $P$-PzCDP).

Let $M_{1}$ satisfy $P_{1}$-PzCDP and let $M_{2}$ satisfy $P_{2}$-PzCDP. Then
$M_{3}(D)=M_{2}\left(M_{1}(D),D\right)$ satisfies
$\left(P_{1}(r)+P_{2}(r)\right)$-PzCDP.

Like in DP, the privacy losses sum when mechanisms are composed together. In
PzCDP, since the privacy loss is encoded into the policy function, this takes
the form of the sum of the two policy functions.

PzCDP also satisfies a form of parallel composition. When multiple mechanisms
which satisfy $P$-PzCDP are run on disjoint subsets of the database, the joint
result also satisfies $P$-PzCDP:

###### Lemma 4.3 (Parallel composition for $P$-PzCDP).

Define the partition of size $J\in\mathbb{N}\cup\\{\infty\\}$: Let
$\mathcal{T}$ define a partition over the universe of possible records. That
is,

$\mathcal{T}\triangleq\bigcup_{j=1}^{J}C_{j},\qquad C_{i}\cap
C_{j}=\emptyset,i\neq j$

Let $\mathcal{D}_{j}$ be the space of all databases containing only records in
$C_{j}$ for $j\in[J]$. Let $\\{M_{j}\\}_{j=1}^{J}$ be mechanisms satisfying
$P$-PzCDP for databases $D_{j}\in\mathcal{D}_{j}$ for $j\in[J]$, respectively.
Then:

$M(D)\triangleq\left\\{M_{j}(D\cap C_{j})\mid j\in[J]\right\\}$

satisfies $P$-PzCDP. Note that the $M_{j}$s can depend on their respective
$C_{j}$s, allowing for adaptivity.

Note that Lemma 4.3 does not require the individual mechanisms
$\\{M_{j}\\}^{J}_{j=1}$ to be the same for all $j\in[J]$, allowing for
adaptive parallel composition.

PzCDP satisfies the group privacy notion as well. A mechanism that satisfies
$P$-PzCDP also protects groups.

###### Lemma 4.4 (Simple group privacy for $P$-PzCDP).

Consider a sequence of databases $D_{0},\dots,D_{J}$ where $D_{0}=D$ and
$D_{j}\ominus D_{j-1}=\\{r_{j}\\}$ for $j\in[J]$. Let $M$ be a randomized
mechanism satisfying $P$-PzCDP. Then we have:

(1) $d_{\alpha}(M(D_{0})||M(D_{J}))\leq\alpha J\sum_{j=1}^{J}P(r_{j})$

###### Lemma 4.5 (Advanced group privacy for $P$-PzCDP).

Consider a sequence of databases $D_{0},\dots,D_{J}$ where $D_{0}=D$ and
$D_{j}\ominus D_{j-1}=\\{r_{j}\\}$ for $j\in[J]$. Let $M$ be a randomized
mechanism satisfying $P$-PzCDP. Define $r_{(1)},\dots,r_{(J)}$ such that:

$P(r_{(1)})\geq P(r_{(2)})\geq\cdots\geq P(r_{(J)})$

Then we have:

(2)
$d_{\alpha}(M(D_{0})||M(D_{J}))\leq\alpha\inf_{k\in(1,\infty)}\sum_{j=1}^{J}\frac{k^{j}}{k-1}P(r_{(j)})$

###  4.1. Relation to Other Privacy Formulations

Prior work has studied the idea of giving different privacy guarantees to
different records, and the idea of accounting privacy loss as a function of
the data. The flexibility of PzCDP, by comparison, lies in the fact that each
unit’s privacy loss is a _function_ of their private record, and only that
function is published instead of particular values. Units with knowledge of
their private record use this public function to ‘look up’ their privacy loss.

PzCDP most closely resembles the definition for Personalized Differential
Privacy (PDP) (jorgensen_2015_conservative). Like PzCDP, PDP gives different
guarantees to different records:

###### Definition 0 (Personalized zCDP (PDP)(jorgensen_2015_conservative)).

Let $\mathcal{T}$ be a universe of participating records and
$\Phi:\mathcal{T}\mapsto\mathbb{R}^{+}$ be a function which maps each unit to
a privacy loss. A randomized algorithm $M$ satisfies $\Phi$-PDP if, for any
two databases $D,D^{\prime}$ which differ on the contributions of one unit
$r\in\mathcal{T}$, we have

$d_{\alpha}(M(D)||M(D^{\prime}))\leq\alpha\Phi(r)$

This definition contrasts with PzCDP by assuming that $\Phi(r)$ is public
knowledge for all $r\in\mathcal{T}$ _i.e._ each unit’s privacy guarantee is
publicly publishable. Fundamentally, this requires that the guarantee,
$\Phi(r)$, of each unit, $r$, is independent of their private record. By
comparison, $P$-PzCDP does not make any assumptions about independence of a
unit’s privacy guarantee and their sensitive record. Thus, each unit’s
guarantee, $P(r)$ for the unit’s record $r$, remains confidential. Only the
policy function, $P(\cdot)$, is published and individual unit with knowledge
of their private record can compute their own guarantee.

Other works have also studied computing privacy loss as a function of the data
but only in an effort to give tighter accounting of the global privacy loss,
which is constant across all participants and is made public. For instance,
pate give tight privacy loss accounting by deriving a global loss from the
data itself. This global loss is then passed through a novel mechanism to
publish a noisy private version. PzCDP instead gives per-record guarantees
that are not published. Similarly, the individualized accounting method of
(feldman_individual_2021) computes each record’s loss as a function of its
data. However, this is only to ensure that no single record exceeds the public
global privacy budget, constant across all records. Alternatively,
(redberg2021privately) uses an existing global DP guarantee to provide an ex-
post characterization for the gap between the global privacy loss and the
confidential data-dependent realized privacy loss. The foundational
distinguishing factor of PzCDP from both these approaches is that only the
policy is published, as opposed to any global or individual privacy losses.

DP encompasses a wide variety of formalisms (desfontaines_sok_2020) which rely
on alternative characterizations of scenarios under comparison, measures of
privacy loss between those scenarios, and the generality of bounds on these
measures. Here, we show how PzCDP is interoperable with these definitions.
Connections can be made to one-sided DP (doudalis_one-sided_2017), also
adapted to the semantics of zCDP:

###### Definition 0 (One-sided zCDP (OSzCDP)(doudalis_one-sided_2017)).

Let $P:\mathcal{R}\mapsto\\{0,1\\}$ be a function that labels records as
privacy-sensitive ($P(r)=0$) or not ($P(r)=1$). A randomized algorithm $M$
satisfied $(P,\rho)$-one-sided zero-concentrated DP if, for any two databases
$D,D^{\prime}$ where

(3) $D^{\prime}=D\setminus\\{r\\}\cup\\{r^{\prime}\\},P(r)=0,r\neq r^{\prime}$

we have

(4) $d_{\alpha}(M(D)||M(D^{\prime}))\leq\alpha\rho$

###### Lemma 4.8.

Suppose there exists $\rho\geq 0$ and a subset of records
$R\subseteq\mathcal{T}$ such that:

(5) $\sup_{r\in R}P(r)\leq\rho$

Then for the policy $P^{*}:\mathcal{T}\mapsto\\{0,1\\}$ where
$P(r)=\mathbbm{1}\\{r\notin R\\}$, any mechanism $M$ that is $P$-PzCDP is also
$(P^{*},2\rho)$-OSzCDP.

##  5\. Mechanisms for PzCDP

In this section, we present a novel class of privacy mechanisms for ensuring
PzCDP. This class of mechanisms is called Unit Splitting. As the name
suggests, the mechanisms follow this general pattern:

  * •

Preprocess the input dataframe by “splitting” each row or record into many
smaller rows or sub-records. The number of splits depends on a measure of how
large the row is.

  * •

Next, we run a mechanism that satisfies standard $\rho$-zCDP.

  * •

By group composition, the privacy loss of a row or record in the original
dataframe will be $k^{2}\rho$, where $k$ is the number of times an original
row is split in the preprocessing step.

This allows a PzCDP mechanism to be built by doing a pre-processing step
followed by any arbitrary zCDP mechanism. We introduce the basics of unit
splitting in Section 5.1, and describe how to use them to answer SQL
aggregation queries and group-by aggregation queries in Sections 5.2 and 5.4,
respectively.

###  5.1. Unit Splitting

Unit splitting is a preprocessing step that uses a mapping function $A(r)$ to
map each record into one or more other records. Answering queries on the split
records using a mechanism that satisfies zCDP results in an overall mechanism
that satisfies PzCDP. We state this more formally as follows.

###### Lemma 5.1 ($\rho$-zCDP with pre-processing implies $P$-PzCDP).

Consider a pre-processing function $A:\mathcal{T}\mapsto\mathcal{T}^{*}$ where
$A$ maps each record $r\in\mathcal{T}$ to a multiset of records in
$\mathcal{T}^{*}$. Let $|A(r)|$ be the cardinality of the multiset $A(r)$,
i.e., the number of subsequent records generated by $A(r)$. If $M$ is a
$\rho$-zCDP algorithm operating on $\mathcal{D}^{*}$, then $M(A(D))$ satisfies
$P$-PzCDP where $P(r)=\left(\rho|A(r)|^{2}\right)$.

###### Proof.

Let $D$ and $D^{\prime}$ be neighboring datasets and, without loss of
generality, let $A(D^{\prime})\setminus A(D)=\\{s_{1},\dots
s_{|A(r)|}\\}\subseteq\mathcal{T}^{*}$. By the group-privacy properties of
$\rho$-zCDP:

(6) $\displaystyle
D_{\alpha}(M(A(D))||M(A(D^{\prime})))\leq\alpha\left(|A(r)|^{2}\rho\right)$

∎

This allows a practitioner to create mechanisms which satisfy $P$-PzCDP by
using the unit-splitting preprocessing step followed by an off-the-shelf zCDP
mechanism. This applies to all zCDP mechanisms from existing private
frameworks such as Tumult Analytics(berghel2022tumult), to complex mechanisms
such as stochastic gradient descent(AbadiCGMMT016) and the matrix
mechanism(li_matrix_2015). The policy function in this case is implied by the
choice of unit splitting. The number of splits per record directly impacts the
privacy loss of that record, with those that require a higher number of splits
receiving a larger privacy loss than those with a smaller number of splits.

Since each record’s privacy loss is now a function of the contents of the
record, the privacy loss is considered a private value, and cannot be
published. Instead, for transparency, the splitting function itself can be
released, which would allow an observer to reason about the privacy loss of
hypothetical records without releasing information about the records.

Unit splitting is a powerful tool that can be applied to a wide variety of
tasks. In the following sections, we’ll demonstrate how to use the unit
splitting paradigm for one such task. Specifically, PzCDP algorithms for
answering SQL group-by aggregation queries for highly skewed data.

ID | Industry | Employees | Payroll
---|---|---|---
1 | Agriculture | 150 | $ 10,000,000
2 | Agriculture | 50 | $ 15,000,000
3 | Mining | 100 | $ 10,000,000
4 | Mining | 50 | $ 10,000,000
5 | Retail | 20 | $ 1,000,000
(a) Pre-Split Table

ID | Industry | Employees | Payroll
---|---|---|---
1 | Agriculture | 50 | $ 5,000,000
1 | Agriculture | 50 | $ 5,000,000
1 | Agriculture | 50 | $ 0
2 | Agriculture | 50 | $ 5,000,000
2 | Agriculture | 0 | $ 5,000,000
2 | Agriculture | 0 | $ 5,000,000
3 | Mining | 50 | $ 5,000,000
3 | Mining | 50 | $ 5,000,000
4 | Mining | 50 | $ 5,000,000
4 | Mining | 0 | $ 5,000,000
5 | Retail | 20 | $ 1,000,000
(b) Post-Split Table

Table 2. Sample table before and after unit splitting. The splitting
thresholds used were as follows. Employees: 50, Payroll: $ 5,000,000

###  5.2. Answering Aggregation Queries Using Unit Splitting

We can privately compute aggregates such as sums on skewed data by applying
unit splitting in the form of a splitting threshold. Doing so splits the few
large contributors with possibly unbounded values into several smaller bounded
values. This method both bounds and reduces the overall sensitivity of many
queries, therefore allowing lower-error private answers. It, however, comes at
the cost of higher privacy loss for larger records which were split into
multiple smaller records. The choice of splitting procedure results in an
implicit policy function for PzCDP.

We make a distinction between conditional attributes and measure attributes.
Conditional attributes are those which will be used in conditional statements,
such as the WHERE clause in an SQL query. These get duplicated across all
splits of the data. Measure attributes are those which are computed in
aggregations and thus get split across all the split records. For numerical
measure attributes, we individually evaluate the minimum number of times each
of the magnitude attributes $a$ need to be split (i.e., the smallest integer
$m$ such that $mT(a)\geq r(a)$). For example, if a row has $r(a)=12$, and the
splitting threshold is $T(a)=5$, then the row would need to be split into at
least 3 sub-records, corresponding to values of $\\{5,5,2\\}$. This minimum
number of splits may be different for each attribute in any particular row; to
resolve this difference, we select the magnitude attribute with the _largest_
number of required splits. The remaining split elements are zero-padded.
Ideally, each magnitude attribute will be split the same number of times, to
prevent too many zero-padded elements. As a complete example, Table 2 lists
how several records would be split according to these rules.

Algorithm 1 Unit Splitting Pre-Processing

1:$D$: Private dataframe.

2:$T:\mathcal{A}\mapsto\mathbb{Z}$: splitting threshold function.

3:$\\{r_{i}\\}$: multiset of unit splitting rows.

4:procedure UnitSplit($D$, $T$)

5: for $r\in\operatorname{Rows}(D)$ do

6: Find the smallest integer $m$ such that $mT(a)\geq r(a)$ for all
$a\in\mathcal{A}$

7: Split $r$ into $m$ rows such that for each split and each attribute
$r_{i}(a)\leq T(a)$ and $\sum_{i}r_{i}(a)=r(a)$

8: end for

9:end procedure

Once each record has been split, the split records are used to answer each
query in the workload. For each query on the original unsplit records, we
define an equivalent rewritten query on the split records. Table 3 describes
how each query is rewritten. For example, in order to ensure the non-private
results agree between the split and unsplit records, we count the number of
distinct IDs for the COUNTs when using the split records.

###### Lemma 5.2.

As $\rho$ tends to $\infty$, the difference between rewritten queries of Table
3 and their unsplit counterparts tends to $0$.

###### Proof.

By construction, non-private sum queries will be equivalent using either the
split or unsplit data. Since the values of the aggregation columns are
distributed without loss or additions to each of the split rows, the sum of
the split rows is equivalent to the sum of the unsplit rows. Likewise, since
the row IDs are copied over to all the split rows, the COUNT_DISTINCT query
will only increment by one for each unsplit row. Since an average of the
unsplit rows is the sum divided by count, the equivalent on the split rows is
the sum divided by the distinct count. ∎

Since these aggregations are simply a zCDP mechanism after a mapping, by Lemma
5.1, the entire process satisfies $P$-PzCDP where the policy function is
dependent on the number of times each record is split.

###### Lemma 5.3.

Computing Algorithm 1 followed by an aggregation from Table 3 satisfies
$P$-PzCDP.

Conditionals such as group-by and filters can be applied to split data without
any adaptation, since the conditional attributes are duplicated across all
splits. We give an example of answering a private sum below.

###### Example 0.

Consider taking a sum over the Employees column of Table 2(a). We use the
following splitting threshold (Employees: 50, Payroll: $5,000,000). The table
after splitting can be found in Table 2(b). After splitting, the maximum value
of the Employees column is 50 and each record is split into multiple rows with
at most $50$ employees. The same holds for Payroll and its associated
threshold. Once the table is split, the sum is taken over all the split rows.

The PzCDP policy function is implied by the splitting threshold. Each record
incurs a privacy loss according to the number of times it is split.
Establishments $1$ and $2$ are split $3$ times and incurs a privacy loss of
$9\rho$. Establishments $3$ and $4$ are only split twice and each incurs a
privacy loss of $4\rho$. Establishment $5$ is never split and incurs a privacy
loss of $\rho$.

In this example, we used a sum, but this could include other aggregations such
as averages or other more complex zCDP mechanisms such as partition selection
(desfontaines_differentially_2022), matrix mechanism (li_matrix_2015) among
others. One benefit of unit splitting is bounding the sensitivity of
previously unbounded queries.

###### Example 0.

Consider taking a sum over the Employees column of Table 2(a). Prior to unit
splitting, the maximum possible number of employees for any arbitrary
establishment is unbounded. There is no limit to the number of employees an
establishment can have. After the splitting, the maximum value of the
Employees column is set to 50, introducing a bound. Since the maximum number
of employees in any record is 50, the sensitivity of the sum over employees is
also 50.

In this case, the previously unbounded sensitivity is now bounded by the unit
splitting algorithm. Traditionally, one would set a clamping bound on the sum,
which would truncate all the values outside the bound to one of the boundary
values. For heavily skewed data, this can either introduce bias (if the bound
is too small) or a large amount of noise (if the bound is too large). When
using unit splitting, this is no longer a concern, as the splitting threshold
can be set low enough to avoid incurring too much noise. The tradeoff in this
case is that the larger records incur a larger privacy loss overall. This
makes PzCDP particularly powerful in the case of highly skewed data, where a
small amount of large records makes it impractical to introduce clamping
bounds. Instead, these records are split into many smaller records and incur a
larger privacy loss as a result.

Original query | Rewritten Exact Query | PzCDP $P(r)$
---|---|---
COUNT(ROW_ID) | COUNT_DISTINCT(ROW_ID) | $\rho$
SUM($\cdot$) | SUM($\cdot$) | $\rho|A(r)|^{2}$
AVG($\cdot$) | SUM($\cdot$) / COUNT_DISTINCT(ROW_ID) | $\rho|A(r)|^{2}$
Table 3. Common exact queries and their reconstruction strategies

###  5.3. Multiple Aggregations

While unit splitting is a versatile technique in its own right, much of its
power comes from its ability to compose neatly with much of the existing DP
literature as well as other instances of unit splitting. While any two PzCDP
mechanisms compose together due to Lemma 4.2, this also holds for mechanisms
run prior to the unit splitting. This is because $\rho$-zCDP can be seen as a
special case of PzCDP where the policy function is equal to the privacy
parameter $\rho$.

###### Lemma 5.6.

Let $M$ be a randomized mechanism which satisfies $\rho$-zCDP. Then $M$ also
satisfies $P$-PzCDP where $P(r)=\rho$.

This allows mechanisms run prior to unit splitting to compose with those run
after unit splitting by using Lemma 4.2.

PzCDP excels in reducing the sensitivity of high or unbounded sensitivity
queries, such as sums or means. However, when computing queries with low
sensitivities such as counts or medians, it is easier to use zCDP to compute
these counts prior to unit splitting. In these cases, each record only incurs
a constant privacy loss (the $\rho$ parameter given to the zCDP mechanism) as
opposed to the variable privacy loss given by PzCDP and unit splitting. We
demonstrate this in the following example where zCDP is used to compute a
median followed by a sum computed on unit split data.

###### Example 0.

Consider the sum from Example 5.4 with the addition of a median query on the
Payroll column prior to the unit splitting process. If we first compute the
median with a privacy budget of $\rho_{1}$, then compute the sum with privacy-
loss budget $\rho_{2}$, then by Lemma 4.2 the combination of the two
mechanisms satisfies PzCDP with a policy function of
$\rho_{1}+\rho_{2}|A(r)|^{2}$, where $|A(r)|$ is the maximum number of times
record $r$ is split. In this case, Establishments $1$ and $2$ incur
$\rho_{1}+9\rho_{2}$ privacy loss, Establishments $3$ and $4$ incur
$\rho_{1}+4\rho_{2}$ privacy loss, and Establishment $5$ incurs
$\rho_{1}+\rho_{2}$ privacy loss.

By using traditional zCDP to compute the median, each record only incurs a
constant ($\rho_{1}$) privacy loss. Had that median been computed after the
unit splitting, the larger records would have incurred $9\rho_{1}$ privacy
loss instead, a significant increase. In these cases, zCDP mechanisms can be
used for tasks that are not subject to high sensitivity, such as medians, or
complex tasks for which no unit split equivalent is available, such as
stochastic gradient descent (AbadiCGMMT016). This allows for tighter analysis
when using low sensitivity queries and opens up the vast literature of
differentially private techniques for use alongside unit splitting.

###  5.4. Answer GroupBy Aggregation Queries Using Unit Splitting.

In addition to aggregations such as sums and counts, unit splitting also
supports conditional analysis such as filters and group-by. Filters and group-
by can be applied directly on the conditional attributes after unit splitting,
since those attributes are duplicated across all splits. This allows for
individual analysis for each group.

Lemma 4.3 allows a practitioner to apply different splitting thresholds for
each group in order to better serve the needs of each group. For example,
consider if we added Technology as an additional industry in Table 2.
Technology firms have significantly higher average pay than agricultural
establishments and as such have a significantly higher payroll. In such cases,
a different set of splitting thresholds may be necessary for technology firms
to avoid extremely high privacy loss.

In cases where the group-by keyset is unknown, or is sparse in the domain of
the attribute one can use a private partition selection algorithm, after the
unit splitting process. Since the data has been split prior to partition
selection, large records are instead split into many small records and are as
such more likely to be discovered. We demonstrate an example of using all
three techniques; group-by, multiple splitting thresholds, and split partition
selection.

###### Example 0.

Consider taking two sums over the Employee column and Payroll column of Table
2(a), grouped by the values of the Industry column. In addition, consider the
following splitting thresholds for each industry. For agriculture and retail,
use the previous splitting threshold of (Employees: 50, Payroll: $5,000,000).
For mining, apply the splitting threshold of (Employees: 50, Payroll:
$10,000,000).

To compute the sum, we need to complete three steps. First apply unit
splitting to each industry with their own splitting threshold. This bounds the
sensitivity of both the Employees and Payroll column, however this bound is
now different for each industry. Then use some privacy budget $\rho_{1}$ to
use a partition selection technique (desfontaines_differentially_2022) to find
the keyset for the group-by. Since each industry is split prior to the
partition selection, those with few but large records still have a high
probability to be in the resulting keyset. Then for each category in the
Industry column, we take the sum over employees using the Gaussian mechanism
with sensitivity $50$ and privacy budget $\rho_{2}$. This sensitivity remains
the same since the employee splitting threshold is the same for all
industries. For sum over payroll, use the Gaussian mechanism with sensitivity
$5,000,000$ for agriculture and retail and use sensitivity $10,000,000$ for
mining. For both, we will use the same privacy budget $\rho_{3}$.

Since the partitions over the industry column form disjoint subsets of the
dataset by Lemma 4.3, the sum over Employees and Payroll satisfy
$\rho_{2}|A(r)|^{2}$ and $\rho_{3}|A(r)|^{2}$-PzCDP respectively where
$|A(r)|$ denotes the number of splits for each record for their respective
splitting thresholds. We can combine all of these policy functions together
using Lemma 4.2 to get that the overall mechanism satisfies $P$-PzCDP with a
policy function $P(r)=(\rho_{1}+\rho_{2}+\rho_{3})|A(r)|^{2}$. For records 1
and 2, the final privacy loss is $9(\rho_{1}+\rho_{2}+\rho_{3})$ since they
are each split into 3 rows. Record 3 incurs $4(\rho_{1}+\rho_{2}+\rho_{3})$
privacy loss since it is split into 2 rows under the new splitting threshold,
and record 4 only incurs $\rho_{1}+\rho_{2}+\rho_{3}$ privacy loss since it is
not split under the new splitting thresholds.

Since these were disjoint sections of the database, we could apply different
splitting thresholds to each disjoint section and still satisfy $P$-PzCDP. In
this case, the new policy function would be a piece-wise function, giving a
different functional form for each industry.

Due to the initial unit splitting, the partition selection step has a high
probability of selecting each of the populated industries, even if those
industries are populated by few but large establishments. This allows
practitioners to properly analyze heavily skewed data where much of the data
is compressed into relatively few records, a phenomenon which often happens in
economic or population statistics.

##  6\. Experiments

In this section, we empirically demonstrate the effectiveness of PzCDP when
applied to skewed data. In Section 6.2 we demonstrate how the high bias and
error from global zCDP results in an unacceptable trade-off between privacy
and utility. Then, in Section 6.3, we focus on univariate queries to show how
PzCDP can be an effective alternative to zCDP with modest reductions in
privacy. Finally, in Section 6.4, we demonstrate the methodology on our
motivating use case, CBP.

###  6.1. Setup and Datasets

For each experiment, we answer queries using either zCDP or PzCDP according to
the Gaussian mechanism (Def. 2.7) with clamping-enforced sensitivity $\Delta$,
noise variance $\sigma^{2}$, and privacy loss
$\rho=\frac{\Delta^{2}}{2\sigma^{2}}$, or unit splitting pre-processing
(Algorithm 1) with additive Gaussian noise with variance $\sigma^{2}$
according to different splitting functions $T$. We use the following metrics
throughout. Where contextually appropriate, we abuse notation and only include
the relevant arguments.

Policy loss: for $r\in D$, we have

(7) $\mathrm{PolicyLoss}(P,r)\triangleq P(r)$

Note that in practice, we cannot release $\mathrm{PolicyLoss}(P,r)$, only the
functional form $P(\cdot)$.

Realized loss: for a record $r$, the realized dataset $D$, and mechanism $M$,

(8) $\displaystyle\mathrm{RealizedLoss}(M,D,r)$ (9)
$\displaystyle\triangleq\sup_{\alpha\in(1,\infty)}\frac{d_{\alpha}(M(D)||M(D\setminus\\{r\\}))}{\alpha}$

By construction, when $M$ satisfies $P$-PzCDP,

(10) $\mathrm{PolicyLoss}(P,r)\geq\mathrm{RealizedLoss}(M,D,r)$

for all $r\in D$. Again, in practice, we cannot release
$\mathrm{RealizedLoss}(M,D,r)$ nor its functional form, as it depends on the
realized dataset $D$.

Query relative error: for a dataset $D$, query $M(D)$, and non-private answer
$S(D)$, define

(11) $\displaystyle\mathrm{QueryRelErr}(M,S,D,\gamma)$ (12)
$\displaystyle\triangleq\min\left\\{v\in\mathbb{R}^{+}\mid\operatorname{\mathbb{P}}\left(\frac{|M(D)-S(D)|}{S(D)}\geq
v\right)\leq 1-\gamma\right\\}$

Absolute relative error (ARE): for a given output $M(D)$ and non-private
answer $S(D)$, define

(13)
$\displaystyle\mathrm{ARE}(M(D),S(D))\triangleq\frac{|M(D)-S(D)|}{|S(D)|}$

Policy minimum: for a policy function $P$, we will use
$\mathrm{PolicyMin}(P)=\min_{r\in\mathcal{T}}P(r)$ to denote the smallest
policy loss associated with one record. For unit splitting algorithms, this
can be interpreted as the policy loss for records unaffected by unit
splitting.

Our experiments are run on three different datasets: a simulated dataset
(SIM), the National Agricultural Statistical Service Cattle Inventory Survey
(CIS), and a County Business Patterns (CBP) synthetic dataset.

The first dataset is simulated data for which we know the precise data
generating distribution. This allows us to illustrate the kinds of heavy-
tailed behavior that our methodology can better accommodate, as opposed to
global DP.

We simulate two heavy-tailed variables in $[1,\infty)$ with tail index
parameters $\alpha$, where smaller values of $\alpha$ correspond to heavier
tails. The simulated variables are listed in Table 4; note that both variables
HT1 and HT2 have infinite variance. Our goal is to answer sum queries of HT1
and HT2 grouped by CatIX.

Name | Domain | Distribution
---|---|---
$\mathrm{CatIX}$ | $\\{1,\dots,1000\\}$ | $\mathrm{Categorical}(\phi)$
$\mathrm{HT1}$ | $[1,\infty)$ | $\mathrm{Pareto}(1,1.2)$
$\mathrm{HT2}$ | $[1,\infty)$ | $\mathrm{Pareto}(1,1.5)$
Table 4. Simulated heavy-tailed variables

The second dataset is from the U.S. Department of Agriculture (USDA)’s Cattle
Inventory survey (CIS), managed by the National Agricultural Statistical
Service (NASS) (agcensus). Our records consist of county-level survey records
of total cattle inventory and average pastureland rent cost (in dollars per
acre). Each county geography is contained hierarchically within an
agricultural district (AD), itself contained within a particular state. We
will treat these records as our privacy units, since the individual farm-level
records are not publicly available. Still, a small number of records
contribute to the majority of the total cattle inventory in any particular
state or AD, making the methodology applicable. We consider the queries in
Table 5 under different privacy loss allocations and splitting thresholds
shown in the figures. The $P$-PzCDP queries are answered using Algorithm 1 and
the $\rho$-zCDP queries are answered using the Gaussian mechanism from
Definition 2.7.

Geographies | Query | Formalism
---|---|---
State | SUM(CattleInventory) |  $P$-PzCDP
State | AVG(PastureRent) |  $\rho$-zCDP
State x AD | SUM(CattleInventory) |  $P$-PzCDP
State x AD | AVG(PastureRent) |  $\rho$-zCDP
Table 5. CIS Queries

The final dataset is a proposed use case involving summations over skewed
data: the County Business Patterns (CBP) dataset, published by the U.S. Census
Bureau. We use synthetic data provided by the U.S. Census Bureau to
demonstrate PzCDP methodology on these synthetic records. Each row in our
tabular data represents an “establishment”, or one separate unit of a
business; “firms” represent one or more establishments that operate as a
single business venture. Our goal is to release the following information
about groups of establishments:

  * •

ESTAB: A count of the number of establishments.

  * •

PAYANN: A sum of annual payrolls of establishments.

  * •

PAYQTR1: A sum of first quarter payrolls of establishments.

  * •

EMP: A sum over employee size of establishments.

The groups of establishments correspond to different geographic areas (such as
counties, ZIP codes, or congressional distributions) and different industry
classifications using the North American Industry Classification System
(NAICS) codes (such as finance, real estate, agriculture, etc.). For the
purposes of this experiment, we consider the subset of all county-level
queries at every possible NAICS classification level with no cross-
tabulations; moreover, we limit our evaluations to only those queries with 100
or more establishments.

Geographies | Query | Formalism
---|---|---
County x NAICS* | COUNT(ESTAB) |  $\rho$-zCDP
County x NAICS* | SUM(EMP) |  $P$-PzCDP
County x NAICS* | SUM(PAYANN) |  $P$-PzCDP
County x NAICS* | SUM(PAYQTR1) |  $P$-PzCDP
Table 6. CBP Queries

###  6.2. Global zCDP on Skewed data

First, we show how a theoretical analysis of the $\rho$-zCDP Gaussian
mechanism for sums on heavy-tailed random variables fails to yield reasonable
trade-offs between privacy and utility. Specific to our simulation study, we
consider the theoretical mean-square error (MSE) of estimators truncated with
high probability from heavy tails. In Figure 1, we fix $n=1000$ and plot the
theoretical mean-square error (MSE) over the sum’s expected value as a measure
of ”noise-to-signal” on the y-axis. We show how this ratio varies with
different sensitivities $\Delta$ on the x-axis, privacy losses $\rho$, and
tail weights $\alpha$. Note that in every case, privacy-preserving noise
exceeds the sum’s expected value by orders of magnitude. For each
configuration, we additionally calculate the optimal $\Delta$ for given
$\alpha$ and $\rho$ values which minimize the ratio (shown as the vertical red
lines in the subplots). As expected, the optimal $\Delta$ value to minimize
MSE increases as $\alpha$ decreases and as $\rho$ increases; however, even at
these optimal $\Delta$ values, the errors are prohibitively large. Recall from
(bun_concentrated_2016) that Gaussian noise is tight for zCDP summation
queries, meaning any $\rho$-zCDP mechanism requires noise with variance at
least $\Omega(\Delta/\rho^{2})$, i.e. as a function of the volume of the sum
query space. So even for modest tail weights, the cost of ensuring each record
lies in a bounded domain makes it near-impossible to simultaneously maintain
modest global privacy losses and MSE guarantees.

Figure 1. Theoretical MSE over the expected query value for global $\rho$-zCDP
mechanisms with different global sensitivities $\Delta$, privacy loss budgets
$\rho$, and different tail parameters $\alpha$ for $n=1000$. Optimal $\Delta$
for minimizing MSE given $\rho$ and $\alpha$ shown in red. Blue dashed line at
1, for reference.

###  6.3. PzCDP privacy-utility trade-offs with univariate splitting

Next, we show how using Algorithm 1 in conjunction with the Gaussian mechanism
offers significant improvements to utility with a cost to privacy loss that
only affects a small number of units. In Figure 2, we use our proposed method
to answer queries on the workloads with different univariate unit splitting
thresholds (STs) for one variable of interest (HT1 for SIM, CattleInventory
for CIS). The left set of subplots show the workload AREs (y-axis) at
different STs; as ST decreases, the proportion of records that are split (for
which policy loss is greater than $\rho$) increases, shown on the x-axis. To
simplify, utility increases (y-axis distributions shift downward) as privacy
loss increases (x-axis boxplots shift to the right). The plots show that ARE
improves significantly, while policy loss for most records remains the same as
the global zCDP counterpart. For example, at $\rho=1$ for the simulated data,
we can achieve a median 10% ARE across queries while ensuring less than 1% of
records have policy loss greater than $\rho=1$.

On the right-hand side of Figure 2, we show a more detailed view of the policy
loss functions by visualizing their empirical CDFs: namely, for any one unit
splitting configuration, what proportion of records (y-axis) have policy
losses less than a particular value (x-axis)? We show this for different STs
and $\rho$. As $\rho$ increases, the CDFs shift to the right, as expected
since less noise injection increases policy loss uniformly across records.
Larger STs correspond to more conservative unit splitting schemes, ensuring
that a greater proportion of records have the smallest possible policy loss.
As ST decreases, the policy loss grows more rapidly for larger units, which
are split more frequently. These plots demonstrate how $\rho$ toggles the
privacy-utility trade-off for all records, whereas ST toggles how fast the
policy loss grows as records become more skewed.

a) Simulated Pareto data
b) USDA Cattle Inventory Study

Figure 2. (Left) distribution of ARE over workload queries (y-axis) by
proportion of records with policy loss greater than $\rho$ (x-axis). (Right)
Empirical CDFs of policy loss, i.e. proportion of observed records (y-axis)
with policy loss bounded by $P(r)$ (x-axis). Columnar subplots show different
levels of minimum policy loss $\rho$. Red line represents 100% ARE and green
line represents 10% ARE.

###  6.4. End-to-end example: County Business Patterns dataset

We now turn towards a more complex, realistic application of our methodology
to CBP. The query workload is described in Table 6; answering these queries
requires leveraging more features of our proposed framework. First, we
consider multivariate unit splitting as a function of multiple attributes per
record. Second, we combine zCDP with PzCDP queries. Third, we use both
sequential and parallel composition simultaneously to answer queries about the
full workload.

Figure 3. AREs for the CBP query workload using topcoding and zCDP (left)
versus using unit splitting (right) for different NAICS levels (rows) and
splitting schemes (columns). Red line represents 20% ARE and green line
represents 5% ARE.

We consider two different algorithmic approaches for answering the CBP query
workload. First, we consider zCDP mechanisms using sensitivities defined by
three possible sets of “top-codes” in Table 7, which we name “Conservative”,
“Moderate”, and “Aggressive”, in decreasing order. Second, we consider PzCDP
based on splitting schemes listed in Table 8, which we name “Conservative”,
“Moderate”, and “Median”. The three schemes are listed in increasing split
cardinality order.

Top-code scheme name | Attribute | Value
---|---|---
Conservative | EMP | $10^{3}$
PAYANN | $10^{5}$
PAYQTR1 | $2.5*10^{4}$
Moderate | EMP | $3*10^{2}$
PAYANN | $10^{4}$
PAYQTR1 | $2.5*10^{3}$
Aggressive | EMP | $10^{2}$
PAYANN | $10^{3}$
PAYQTR1 | $2.5*10^{2}$
Table 7. Top-code scheme description. SchemeName | SplitAttribute | SplitThreshold | PctScore
---|---|---|---
Conservative | PAYANN | 10000 | 99%
PAYQTR1 | 2500 | 99%
EMP | 100 | 97%
Moderate | PAYANN | 500 | 79%
PAYQTR1 | 125 | 80%
EMP | 5 | 66%
Median | PAYANN | 104 | 50%
PAYQTR1 | 24 | 50%
EMP | 2 | 47%
Table 8. Establishment splitting thresholds for three different splitting
schemes and their associated percentiles of score in the CBP synthetic data.

In Figure 3 we plot the ARE of each query for the top-coding algorithm and the
establishment splitting algorithm, respectively. The results are aggregated by
attribute, total privacy loss budget, NAICS level, and algorithmic
configuration. The green and red dashed lines mark the 5% and 20% ARE
thresholds, respectively, representing example fitness-for-use goals. First,
we expect the relative errors for counting attributes (i.e. ESTAB and FIRM) to
have the same distribution for either algorithm, as they are unaffected by
establishment splitting. However, when we look at the magnitude attributes
(EMP, PAYANN, and PAYQTR1), none of the top-coding schemes on the left come
close to providing reasonable AREs, since the majority of the box plot masses
for these queries are above the dashed green line. Alternatively, on the
right, we see that establishment splitting provides far smaller relative
errors, even for more granular queries at finer NAICS levels (although the
relative errors increase as the NAICS level increases, as expected).

Figure 4. Theoretical minimum policy function CDFs to achieve different
fitness-for-use goals on 95% of the COUNTY by NAICS code query workload. The
green dashed line represents the total unsplit privacy loss budget of 1.
Figure 5. CBP policy losses grouped by establishment (left) and firm (right)

Similarly, in Figure 5, we plot the policy loss CDFs for each splitting
scheme, which can be interpreted similarly to the policy loss CDFs in Figure 2
with a few differences worth highlighting. First, by PzCDP’s group composition
properties, we can extend the results from the left column of establishment
subplots to the right column of firm subplots. Since the majority of
establishments in the synthetic data have a unique ID, the plots look very
similar; however, the firm-level CDFs sit slightly below the establishment
level CDFs. This demonstrates how establishment-level guarantees are conferred
to firms. Second, we additionally calculate the _realized_ privacy losses for
each establishment and firm. Specifically, this calculates the log-max
divergence between the establishment splitting outputs using the specific CBP
synthetic dataset with and without the establishment (or firm) of interest. By
construction, the realized loss is always less than the policy loss, so the
blue CDF line will always be to the left of the orange policy loss line.
First, we observe that for the majority of establishments, the realized
privacy loss is significantly lower than the policy upper bound. Moreover,
because this gap depends on the number of queries answered in the workload, we
can reasonably expect this gap to be larger when considering the entire CBP
workload, not just county-level queries. Next, we observe that, as the
splitting thresholds decrease, the gap between the realized privacy loss and
the policy upper bound decreases.

Finally, instead of considering the realized relative errors, we ask: what is
the _smallest_ possible policy function which ensures we reach a particular
fitness-for-use goal? Specifically, we calculate the smallest policy loss
function for each entity where we assume that for each query in the county
workload, we have at theoretical query relative error of less than $\delta$
with probability at least 95%. We plot the implied policy loss CDFs in Figure
4. As expected, we require smaller policy losses for the majority of
establishments as the splitting thresholds get smaller and smaller, since we
are incurring larger privacy losses for larger establishments. Additionally,
as expected, when $\delta$ increases, the distribution of the minimum policy
loss subsequently decreases (i.e., the CDFs are shifted to the left). All this
demonstrates that with these splitting schemes, fitness-for-use goals are more
feasible than under the traditional top-coding assessment.

##  7\. Conclusion

To summarize, we introduced PzCDP to transparently encode dependencies between
per-record privacy loss and confidential records. This relaxation of
traditional DP notions helps answer SQL-style queries over skewed data where
approaches like zCDP may fail to offer reasonable privacy-utility trade-offs.
By making the policy function public, we offer a new way of describing privacy
loss in cases where a small minority of records pose exorbitant privacy risks
that aren’t representative of the entire dataset. Such policy functions are
particularly useful when the unit of privacy analysis is not an individual
person, but a group of people in a business establishment or other
organization where there may be different social privacy expectations for
large versus small groups. We additionally offer a way of indirectly setting
the policy function through unit splitting, a pre-processing step that
composes with DP algorithms to provide PzCDP guarantees by construction. Our
experiments applying this technique to simulated data, cattle inventory data,
and business pattern data demonstrate how PzCDP can better answer realistic
SQL-style query workloads on skewed data without relying on zCDP’s worst-case
analysis. Future work beyond the scope of the article could more formally
characterize the semantic guarantees offered by PzCDP. Techniques like unit
splitting intrinsically leak more information about confidential records when
records are split with finer granularity. Understanding the kinds of queries
that could be leveraged to learn confidential information via the policy
function require further investigation. While this paper focuses on static
data dissemination settings, such extensions would be helpful for using PzCDP
in more general (possibly interactive) query systems. Similarly, future work
could explore different techniques for choosing how privacy loss scales with
record values. While we considered quadratic dependence between record values
and policy loss, using $\epsilon$-DP style semantics could yield linear
dependence instead. Alternatively, additional pre-processing and post-
processing steps could enable new ways of scaling this dependence.

###### Acknowledgements.

We would like to thank Margaret Beckom, Anthony Caruso, William Davie Jr, Ian
Schmutte, and Brian Finley from the U.S. Census Bureau and Zach Terner from
MITRE for their valuable insight and feedback.

## References

  * (1)
  * 83rd United States Congress (1954) 83rd United States Congress. 1954.  Title 13.
  * 99th United States Congress (1986) 99th United States Congress. 1986.  Title 26 / Internal Revenue Code of 1986.
  * Abadi et al. (2016) Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep Learning with Differential Privacy. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016_ , Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM, 308–318.  https://doi.org/10.1145/2976749.2978318
  * Alaggan et al. (2016) Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec. 2016.  Heterogeneous Differential Privacy.  _Journal of Privacy and Confidentiality_ 7, 2 (2016), 127–158.
  * Asi et al. (2023) Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. 2023.  From Robustness to Privacy and Back.  arXiv:2302.01855 [cs.LG]
  * Berghel et al. (2022) Skye Berghel, Philip Bohannon, Damien Desfontaines, Charles Estes, Sam Haney, Luke Hartman, Michael Hay, Ashwin Machanavajjhala, Tom Magerlein, Gerome Miklau, Amritha Pai, William Sexton, and Ruchit Shrestha. 2022.  Tumult Analytics: a robust, easy-to-use, scalable, and expressive framework for differential privacy.  arXiv:2212.04133 [cs.CR]
  * Bun and Steinke (2016) Mark Bun and Thomas Steinke. 2016.  Concentrated differential privacy: Simplifications, extensions, and lower bounds. In _Theory of Cryptography Conference_. Springer, 635–658.
  * Bureau (2023a) U.S. Census Bureau. 2023a.  County Business Patterns.  https://www.census.gov/programs-surveys/cbp.html
  * Bureau (2023b) U. S. Census Bureau. 2023b.  US Census Bureau, County Business Patterns: Demonstration Tables for New Differential Privacy Methodology for Disclosure Avoidance.  https://www.census.gov/topics/business-economy/disclosure/data/tables/cbp-privacy-demonstration-tables.html
  * Desfontaines and Pejó (2020) Damien Desfontaines and Balázs Pejó. 2020.  Sok: differential privacies.  _Proceedings on privacy enhancing technologies_ 2020, 2 (2020), 288–313.
  * Desfontaines et al. (2022) Damien Desfontaines, James Voss, Bryant Gipson, and Chinmoy Mandayam. 2022.  Differentially private partition selection.  _Proceedings on Privacy Enhancing Technologies_ 1 (2022), 339–352.
  * Dwork and Lei (2009) Cynthia Dwork and Jing Lei. 2009.  Differential Privacy and Robust Statistics. In _Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing_ (Bethesda, MD, USA) _(STOC ’09)_. Association for Computing Machinery, New York, NY, USA, 371–380.  https://doi.org/10.1145/1536414.1536466
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006.  Calibrating noise to sensitivity in private data analysis. In _Theory of cryptography conference_. Springer, 265–284.
  * Dwork and Roth (2013) Cynthia Dwork and Aaron Roth. 2013.  The Algorithmic Foundations of Differential Privacy.  _Foundations and Trends® in Theoretical Computer Science_ 9, 3-4 (2013), 211–407.  https://doi.org/10.1561/0400000042
  * Ebadi et al. (2015) Hamid Ebadi, David Sands, and Gerardo Schneider. 2015.  Differential privacy: Now it’s getting personal.  _Acm Sigplan Notices_ 50, 1 (2015), 69–81.  Publisher: ACM New York, NY, USA.
  * Evans et al. (1996) Timothy Evans, Laura Zayatz, and John Slanta. 1996.  Using noise for disclosure limitation of establishment tabular data. In _Proceedings of the Annual Research Conference, US Bureau of the Census, Washington, DC_ , Vol. 20233. 65–86.
  * Feldman and Zrnic (2021) Vitaly Feldman and Tijana Zrnic. 2021.  Individual privacy accounting via a renyi filter.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Ghosh and Roth (2015) Arpita Ghosh and Aaron Roth. 2015.  Selling privacy at auction.  _Games and Economic Behavior_ 91 (2015), 334–346.  Publisher: Elsevier.
  * Internal Revenue Service (2023) Statistics of Income (SOI) Division Internal Revenue Service. 2023.  SOI Tax Stats - Products, Publications, and Papers.  https://www.irs.gov/statistics/soi-tax-stats-products-publications-and-papers
  * Jorgensen et al. (2015) Zach Jorgensen, Ting Yu, and Graham Cormode. 2015.  Conservative or liberal? Personalized differential privacy. In _2015 IEEE 31St international conference on data engineering_. IEEE, 1023–1034.
  * Kotsogiannis et al. (2020) Ios Kotsogiannis, Stelios Doudalis, Sam Haney, Ashwin Machanavajjhala, and Sharad Mehrotra. 2020.  One-sided Differential Privacy. In _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. 493–504.  https://doi.org/10.1109/ICDE48307.2020.00049
  * Li et al. (2015) Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. 2015.  The matrix mechanism: optimizing linear counting queries under differential privacy.  _The VLDB journal_ 24, 6 (2015), 757–781.  Publisher: Springer.
  * Liu et al. (2021) Xiyang Liu, Weihao Kong, and Sewoong Oh. 2021.  Differential privacy and robust statistics in high dimensions.  arXiv:2111.06578 [math.ST]
  * O’Malley and Ernst (2007) Meghan O’Malley and Lawrence R. Ernst. 2007.  Practical Considerations in Applying the pq-Rule for Primary Disclosure Suppressions December.
  * Papernot et al. (2018a) Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. 2018a.  Scalable private learning with pate.  _arXiv preprint arXiv:1802.08908_ (2018).
  * Papernot et al. (2018b) Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. 2018b.  Scalable Private Learning with PATE.  _arXiv:1802.08908 [cs, stat]_ (Feb. 2018).  http://arxiv.org/abs/1802.08908 arXiv: 1802.08908.
  * Redberg and Wang (2021) Rachel Redberg and Yu-Xiang Wang. 2021.  Privately publishable per-instance privacy.  _Advances in Neural Information Processing Systems_ 34 (2021), 17335–17346.
  * Service (2023) National Agricultural Statistics Service. 2023.  Census of Agriculture.  https://www.nass.usda.gov/AgCensus/
  * Wang (2019) Yu-Xiang Wang. 2019.  Per-instance differential privacy.  _Journal of Privacy and Confidentiality_ 9, 1 (2019).
  * Whitehouse et al. (2022) Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Zhiwei Steven Wu. 2022.  Fully adaptive composition in differential privacy.  _arXiv preprint arXiv:2203.05481_ (2022).

##  Appendix A Omitted Proofs

###  A.1. Proof of Lemma 4.2

Fix $D\in\mathcal{D}$ and let $D^{\prime}\in\mathcal{D}$ such that $D\ominus
D^{\prime}=\\{r^{\prime}\\}$. Let $Y_{1},Y_{2}$ be the outputs from $M_{1}(D)$
and $M_{2}(D)$, respectively, and let $B_{1}\in\mathcal{F}_{Y_{1}}$ and
$B_{2}\in\mathcal{F}_{Y_{2}}$. Then:

$\displaystyle
d_{\alpha}\left(\left(M_{1}(D),M_{2}(D)\right)\mid\left(M_{1}(D^{\prime}),M_{2}(D^{\prime})\right)\right)$
$\displaystyle=d_{\alpha}(M_{1}(D)\mid
M_{1}(D^{\prime}))+d_{\alpha}(M_{2}(D)\mid M_{2}(D^{\prime}))$
$\displaystyle\leq\alpha P_{1}(r)+\alpha P_{2}(r)$
$\displaystyle=\alpha\left(P_{1}(r)+P_{2}(r)\right)$

###  A.2. Proof of Lemma 4.3

Without loss of generality, let $D,D^{\prime}\in\mathcal{D}$ such that
$D\ominus D^{\prime}\triangleq\\{r^{\prime}\\}\subseteq C_{1}$. Then:

$\displaystyle
D_{\alpha}(M(D)||M(D^{\prime}))=\sum_{j=1}^{J}D_{\alpha}(M_{j}(D\cap
C_{j})||M_{j}(D^{\prime}\cap C_{j}))$ $\displaystyle\leq\alpha
P(r^{\prime})+\left[\sum_{j=2}^{J}D_{\alpha}(M_{j}(D\cap
C_{j})||M_{j}(D^{\prime}\cap C_{j}))\right]$ $\displaystyle=\alpha
P(r^{\prime})$

###  A.3. Proof of Lemma 4.4

We will prove the result by strong induction. Define the induction hypothesis
for $m\in[J]$:

$d_{\alpha}(M(D_{0})\mid
M(D_{m}))\leq\alpha\left(m\sum_{j=1}^{m}P(r_{j})\right)$

The hypothesis holds by definition for $m=1$. Next, suppose it holds for
$m=J-1$. From Lemma 5.2 in (bun_concentrated_2016), we have, for any
$k,\alpha\in(1,\infty)$:

(14)
$d_{\alpha}(P||Q)\leq\frac{k\alpha}{k\alpha-1}d_{\frac{k\alpha-1}{k-1}}(P||R)+d_{k\alpha}(R||Q)$

Then using the lemma where $k=J$:

$\displaystyle d_{\alpha}(M(D_{0})||M(D_{J}))$
$\displaystyle\leq\frac{J\alpha}{J\alpha-1}d_{\frac{J\alpha-1}{J-1}}(M(D_{0})||M(D_{J-1}))+d_{J\alpha}(M(D_{J-1})||M(D_{J}))$
$\displaystyle\leq\frac{J\alpha}{J\alpha-1}\left(\frac{J\alpha-1}{J-1}\right)\left((J-1)\sum_{j=1}^{J-1}P(r_{j})\right)+J\alpha
P(r_{J})$ $\displaystyle\leq\alpha\left(J\sum_{j=1}^{J}P(r_{j})\right)$

By induction, the result holds for $m=J$. Note that the expression holds
without loss of generality for any permutation of $\\{r_{1},\dots,r_{J}\\}$.

###  A.4. Proof of Lemma 4.5

From Lemma 5.2 in (bun_concentrated_2016), we have, for
$k,\alpha\in(1,\infty)$

(15)
$d_{\alpha}(P||Q)\leq\frac{k\alpha}{k\alpha-1}d_{\frac{k\alpha-1}{k-1}}(P||R)+d_{k\alpha}(R||Q)$

In iterated form, we have:

(16)
$d_{k^{m}\alpha}(P||Q)\leq\frac{k^{m+1}\alpha}{k^{m+1}\alpha-1}d_{\frac{k^{m+1}\alpha-1}{k-1}}(P||R)+d_{k^{m+1}\alpha}(R||Q)$

Using the iterated form, we have:

$\displaystyle d_{\alpha}(M(D_{0})||M(D_{J}))$
$\displaystyle\leq\frac{k\alpha}{k\alpha-1}d_{\frac{k\alpha-1}{k-1}}(M(D_{0})||M(D_{1}))+d_{k\alpha}(M(D_{1})||M(D_{J}))$
$\displaystyle\leq\frac{k\alpha}{k\alpha-1}d_{\frac{k\alpha-1}{k-1}}(M(D_{0})||M(D_{1}))+$
$\displaystyle\frac{k^{2}\alpha}{k^{2}\alpha-1}d_{\frac{k^{2}\alpha-1}{k-1}}(M(D_{1})||M(D_{2}))+d_{k^{2}\alpha}(M(D_{2})||M(D_{J}))$
$\displaystyle\leq\cdots$
$\displaystyle\leq\sum_{j=1}^{J}\frac{k^{j}\alpha}{k^{j}\alpha-1}d_{\frac{k^{j}\alpha-1}{k-1}}(M(D_{j-1})||M(D_{j})))$
$\displaystyle\leq\sum_{j=1}^{J}\frac{k^{j}\alpha}{k^{j}\alpha-1}\left(\frac{k^{j}\alpha-1}{k-1}\right)P(r_{j})$
$\displaystyle\leq\alpha\sum_{j=1}^{J}\frac{k^{j}}{k-1}P(r_{j})$

Since $\frac{k^{j}}{k-1}$ is an increasing function in $j$ for $j\in[J]$ and
$k\in(1,\infty)$, this expression is minimized by the sequence of order
statistics defined above by finding the minima over all $k\in(1,\infty)$:

$\displaystyle
d_{\alpha}(M(D_{0})||M(D_{J}))\leq\alpha\sum_{j=1}^{J}\frac{k^{j}}{k-1}P(r_{(j)})\quad\forall
k\in(1,\infty)$ $\displaystyle\implies
d_{\alpha}(M(D_{0})||M(D_{J}))\leq\alpha\inf_{k\in(1,\infty)}\sum_{j=1}^{J}\frac{k^{j}}{k-1}P(r_{(j)})$

As an example where the bound improves upon the result from Lemma 4.4, let
$J=2$. Then:

$\displaystyle d_{\alpha}(M(D_{0})||M(D_{2}))$
$\displaystyle\leq\frac{k\alpha}{k\alpha-1}d_{\frac{k\alpha-1}{k-1}}(M(D_{0})||M(D_{1}))+d_{k\alpha}(M(D_{1})||M(D_{2}))$
$\displaystyle\leq\frac{k\alpha}{k-1}P(r_{(1)})+k\alpha P(r_{(2)})$

Finding the minimum solution within $k\in(1,\infty)$ yields:

$\frac{d}{dk}\left[\frac{k}{k-1}P(r_{(1)})+kP(r_{(2)})\right]=-\frac{P(r_{(1)})}{(k-1)^{2}}+P(r_{(2)})=0\implies$
$k^{*}=\sqrt{\frac{P(r_{(1)})}{P(r_{(2)})}}+1$

This implies:

$\displaystyle
d_{\alpha}(M(D_{0})||M(D_{2}))\leq\alpha\left[\frac{k^{*}}{k^{*}-1}P(r_{(1)})+k^{*}\alpha
P(r_{(2)})\right]$
$\displaystyle=\alpha\left[\frac{\sqrt{\frac{P(r_{(1)})}{P(r_{(2)})}}+1}{\sqrt{\frac{P(r_{(1)})}{P(r_{(2)})}}}P(r_{(1)})+\left(\sqrt{\frac{P(r_{(1)})}{P(r_{(2)})}}+1\right)P(r_{(2)})\right]$
$\displaystyle=\alpha\left[P(r_{(1)})+P(r_{(2)})+2\sqrt{P(r_{(1)})P(r_{(2)})}\right]$

Therefore, the result will demonstrate an improvement over Lemma 4.4 whenever:

$\displaystyle 2\sqrt{P(r_{(1)})P(r_{(2)})}<P(r_{(1)})+P(r_{(2)})$
$\displaystyle\iff(P(r_{(1)})-P(r_{(2)}))^{2}>0$ $\displaystyle\iff
P(r_{(1)})>P(r_{(2)})$

Therefore, such improvement occurs only when the policy yields non-constant
privacy loss across records, which agrees with the global zCDP result.
Moreover, this result only holds when the records are considered to be added
or removed in the most favorable order. In the least favorable order, in which
the order statistics are reversed, the composition is weaker, i.e.:

$\frac{}{}\alpha\sum_{j=1}^{J}\frac{k^{j}}{k-1}P(r_{(J+1-j)})>\alpha
J\sum_{j=1}^{J}P(r_{j})$

In other words, the simple composition offered by the previous theorem is
tighter among order-agnostic group privacy guarantees.

Similar to previous definitions, PzCDP is also robust to post-processing. That
is, if a mechanism $M$ satisfies PzCDP, then any function applied directly to
the output of $M$ also satisfies PzCDP.

###  A.5. Proof of Lemma 5.1

Let $D$ and $D^{\prime}$ be neighboring datasets and, without loss of
generality, let $A(D^{\prime})\setminus A(D)=\\{s_{1},\dots
s_{|A(r)|}\\}\subseteq\mathcal{T}^{*}$. By the group-privacy properties of
$\rho$-zCDP:

(17) $\displaystyle
D_{\alpha}(M(A(D))||M(A(D^{\prime})))\leq\alpha\left(|A(r)|^{2}\rho\right)$


them can be investigated using similar ideas. One has

$\displaystyle\int_{-\infty}^{-1}(u(t,x)-u_{-\infty}(t))^{2}dx$
$\displaystyle=\int_{-\infty}^{-1}\left(\int_{-\infty}^{x}u_{x}(t,z)dz\right)^{2}dx$
$\displaystyle=\int_{-\infty}^{-1}\left(\int_{-\infty}^{x}\frac{1}{(-z)^{\gamma/2}}(-z)^{\gamma/2}u_{x}(t,z)dz\right)^{2}dx$
$\displaystyle\leq\int_{-\infty}^{-1}\left(\int_{-\infty}^{x}\frac{1}{(-z)^{\gamma}}dz\right)\left(\int_{-\infty}^{x}(-z)^{\gamma}u_{x}^{2}(t,z)dz\right)dx$
$\displaystyle\leq\frac{1}{\gamma-1}\int_{-\infty}^{-1}\frac{1}{(-x)^{\gamma-1}}dx\left(\int_{\mathbb{R}}|z|^{\gamma}u_{x}^{2}(t,z)dz\right)$
$\displaystyle\leq\frac{1}{(\gamma-1)(\gamma-2)}\left(\int_{\mathbb{R}}|z|^{\gamma}d\nu(t,z)\right),$

which is finite if $\gamma>2$ and (5.2) is satisfied.

For the second condition, recall that

$\lim_{x\to-\infty} F(t,x)=0\quad\text{ and }\quad\lim_{x\to\infty} F(t,x)=C.$

Thus $F(t,\,\cdot\,)\in E_{1}^{0}$ if and only if

$\int_{-\infty}^{-1}F^{2}(t,x)dx+\int_{-1}^{1}F^{2}(t,x)dx+\int_{1}^{\infty}(F(t,x)-C)^{2}dx<\infty,$

by the definition of $E_{0}^{1}$. Again we only consider one integral, since
all of them can be considered using similar ideas. One has

$\displaystyle\int_{-\infty}^{-1}$ $\displaystyle F^{2}(t,x)dx$
$\displaystyle=\int_{-\infty}^{-1}\left(\int_{-\infty}^{x}\frac{1}{(-z)^{\gamma/2}}(-z)^{\gamma/2}d\mu(t,z)\right)^{2}dx$
$\displaystyle\leq\int_{-\infty}^{-1}\left(\int_{-\infty}^{x}\frac{1}{(-z)^{\gamma}}d\mu(t,z)dz\right)dx\left(\int_{\mathbb{R}}|z|^{\gamma}d\nu(t,z)\right)$
$\displaystyle=\int_{-\infty}^{-1}\left(\frac{1}{(-x)^{\gamma}}F(t,x)-\gamma\int_{-\infty}^{x}\frac{1}{(-z)^{\gamma+1}}F(t,z)dz\right)dx\left(\int_{\mathbb{R}}|z|^{\gamma}d\nu(t,z)\right)$
$\displaystyle\leq
C\int_{-\infty}^{-1}\left(\frac{1}{(-x)^{\gamma}}+\gamma\int_{-\infty}^{x}\frac{1}{(-z)^{\gamma+1}}dz\right)dx\left(\int_{\mathbb{R}}|z|^{\gamma}d\nu(t,z)\right)$
$\displaystyle\leq\frac{2C}{\gamma-1}\left(\int_{\mathbb{R}}|z|^{\gamma}d\nu(t,z)\right),$

which is finite if $\gamma>2$ and (5.2) is satisfied.

We have proved the following theorem.

######  Theorem 5.10.

Let $\gamma>2$, then for any initial data $(u_{0},\mu_{0})\in\mathcal{D}$ such
that

$\int_{\mathbb{R}}(1+|x|^{\gamma})d\mu_{0}<\infty$

the Hunter–Saxton equation has a unique global conservative weak solution
$(u,\mu)\in\mathcal{D}$ in the sense of Definition 2.3, which satisfies

$\int_{\mathbb{R}}(1+|x|^{\gamma})d\mu(t)<\infty\quad\text{ for all
}t\in\mathbb{R}.$

##  Appendix A Proof of Lemma 5.2 and Lemma 5.6

######  Lemma A.1 (Lemma 5.2).

(i): Let $g(t,\xi)$ be given by (4.13). Then there exists a positive constant
$\bar{M}$ such that

(A.1) $\displaystyle-\bar{M}$
$\displaystyle|t-s|^{3/2}-p\big{(}t,y(t,\xi+u(t,y(t,\xi))(t-s))\big{)}u(t,y(t,\xi))(t-s)$
$\displaystyle\quad-\int_{\mathbb{R}}u(t,y(t,\eta))K\big{(}y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta)\big{)}\tilde{H}_{\xi}(t,\eta)d\eta\,(s-t)$
$\displaystyle\leq g(s,\xi)-g\big{(}t,\xi+u(t,y(t,\xi))(t-s)\big{)}$
$\displaystyle\leq\bar{M}|t-s|^{3/2}-p\big{(}t,y(t,\xi+u(t,y(t,\xi))(t-s))\big{)}u(t,y(t,\xi))(t-s)$
$\displaystyle\quad-\int_{\mathbb{R}}u(t,y(t,\eta))K\big{(}y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta)\big{)}\tilde{H}_{\xi}(t,\eta)d\eta\,(s-t).$

(ii): Let $H(t,\xi)$ be defined by (5.9). Then

$\displaystyle-($
$\displaystyle\tilde{M}+\bar{M})|t-s|^{3/2}-p\big{(}t,y(t,\xi+u(t,y(t,\xi))(t-s))\big{)}u(t,y(t,\xi))(t-s)$
$\displaystyle\quad-\int_{\mathbb{R}}u(t,y(t,\eta))K\big{(}y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta)\big{)}\tilde{H}_{\xi}(t,\eta)d\eta\,(s-t)$
$\displaystyle\leq H(s,\xi)-H\big{(}t,\xi+u(t,y(t,\xi))(t-s)\big{)}$
$\displaystyle\leq(\tilde{M}+\bar{M})|t-s|^{3/2}-p\big{(}t,y(t,\xi+u(t,y(t,\xi))(t-s))\big{)}u(t,y(t,\xi))(t-s)$
$\displaystyle\quad-\int_{\mathbb{R}}u(t,y(t,\eta))K\big{(}y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta)\big{)}\tilde{H}_{\xi}(t,\eta)d\eta\,(s-t).$

###### Proof.

(i): We want to estimate

$g(s,\xi)-g(t,\xi+u(t,y(t,\xi))(t-s)).$

Recalling (4.13), we split the above difference into two terms as follows

$\displaystyle g(s,\xi)-g(t,\xi+u(t,y(t,\xi))(t-s))$
$\displaystyle=\int_{y(t,\xi+u(t,y(t,\xi))(t-s))}^{y(s,\xi)}p(s,z)dz$
$\displaystyle\qquad+\int_{-\infty}^{y(t,\xi+u(t,y(t,\xi))(t-s))}\big{(}p(s,z)-p(t,z)\big{)}dz$
$\displaystyle=\textup{I}_{1}+\textup{I}_{2}.$

$\textup{I}_{1}$: Since $p(t,x)$ is continuously differentiable on
$[0,T]\times\mathbb{R}$, we have by the mean value theorem that

$\displaystyle\textup{I}_{1}$
$\displaystyle=\int_{y(t,\xi+u(t,y(t,\xi))(t-s))}^{y(s,\xi)}p(s,z)dz$
$\displaystyle=p(s,m)(y(s,\xi)-y(t,\xi+u(t,y(t,\xi))(t-s)))$
$\displaystyle=\big{(}p(s,m)-p(t,y(t,\xi+u(t,y(t,\xi))(t-s)))\big{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\times(y(s,\xi)-y(t,\xi+u(t,y(t,\xi))(t-s)))$
$\displaystyle\quad+p(t,y(t,\xi+u(t,y(t,\xi))(t-s)))(y(s,\xi)-y(t,\xi+u(t,y(t,\xi))(t-s)))$

for some $m$ between $y(s,\xi)$ and $y(t,\xi+u(t,y(t,\xi))(t-s))$.
Furthermore, we find

$\displaystyle\left|p(s,m)-p(t,y(t,\xi+u(t,y(t,\xi))(t-s)))\right|\left|y(s,\xi)-y(t,\xi+u(t,y(t,\xi))(t-s))\right|$
$\displaystyle\quad\leq
M\big{(}\left|s-t\right|+\left|m-y(t,\xi+u(t,y(t,\xi))(t-s))\right|\big{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\times\big{(}\left|u(t,y(t,\xi))(t-s)\right|+\tilde{M}\left|t-s\right|^{3/2}\big{)}$
$\displaystyle\quad\leq
M\big{(}\left|s-t\right|+\left|y(s,\xi)-y(t,\xi+u(t,y(t,\xi))(t-s))\right|\big{)}\left|t-s\right|$
$\displaystyle\quad\leq
M\big{(}\left|s-t\right|+\left|u(t,y(t,\xi))(t-s)\right|\big{)}\left|t-s\right|$
$\displaystyle\quad\leq M\left|s-t\right|^{2},$

for some constant $M$ (that is increased during the calculation), using (4.8),
(4.11), (5.29), and (3.6). In addition, we estimate

$\displaystyle p(t,$ $\displaystyle
y(t,\xi+u(t,y(t,\xi))(t-s)))(y(s,\xi)-y(t,\xi+u(t,y(t,\xi))(t-s)))$
$\displaystyle=p(t,y(t,\xi+u(t,y(t,\xi))(t-s)))\Big{(}u(t,y(t,\xi))(t-s)$
$\displaystyle\qquad+(y(s,\xi)-y(t,\xi+u(t,y(t,\xi))(t-s)))-u(t,y(t,\xi))(t-s)\Big{)}.$

Finally, using (5.29) once more, there exists a positive constant $\hat{M}$
such that

$\left|\textup{I}_{1}+p(t,y(t,\xi+u(t,y(t,\xi))(t-s)))u(t,y(t,\xi))(t-s)\right|\leq\hat{M}|t-s|^{3/2}.$

$\textup{I}_{2}$: Using (3.1), (3.2), and (4.5), we can write

$\displaystyle\textup{I}_{2}$
$\displaystyle=\int_{-\infty}^{y(t,\xi+u(t,y(t,\xi))(t-s))}\big{(}p(s,z)-p(t,z)\big{)}dz$
$\displaystyle=\int_{-\infty}^{y(t,\xi+u(t,y(t,\xi))(t-s))}\int_{t}^{s}p_{t}(\tau,z)d\tau
dz$
$\displaystyle=-\int_{-\infty}^{y(t,\xi+u(t,y(t,\xi))(t-s))}\int_{t}^{s}\int_{\mathbb{R}}u(\tau,x)K^{\prime}(z-x)d\mu(\tau,x)d\tau
dz$
$\displaystyle=-\int_{t}^{s}\int_{\mathbb{R}}u(\tau,x)K(y(t,\xi+u(t,y(t,\xi))(t-s))-x)d\mu(\tau,x)d\tau$
$\displaystyle=-\int_{t}^{s}\int_{\mathbb{R}}u(\tau,y(\tau,\eta))K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(\tau,\eta))\tilde{H}_{\xi}(\tau,\eta)d\eta
d\tau$
$\displaystyle=-\int_{t}^{s}\int_{\mathbb{R}}(u(\tau,y(\tau,\eta))-u(t,y(t,\eta)))$
$\displaystyle\qquad\qquad\qquad\qquad\times
K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(\tau,\eta))\tilde{H}_{\xi}(\tau,\eta)d\eta
d\tau$
$\displaystyle\quad-\int_{t}^{s}\int_{\mathbb{R}}u(t,y(t,\eta))(K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(\tau,\eta))$
$\displaystyle\qquad\qquad\qquad\qquad\qquad-K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta)))\tilde{H}_{\xi}(\tau,\eta)d\eta
d\tau$ $\displaystyle\quad-\int_{t}^{s}\int_{\mathbb{R}}u(t,y(t,\eta))$
$\displaystyle\qquad\qquad\qquad\times
K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))(\tilde{H}_{\xi}(\tau,\eta)-\tilde{H}_{\xi}(t,\eta))d\eta
d\tau$
$\displaystyle\quad-\int_{t}^{s}\int_{\mathbb{R}}u(t,y(t,\eta))K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))\tilde{H}_{\xi}(t,\eta)d\eta
d\tau$ $\displaystyle=\textup{II}_{1}+\textup{II}_{2}+\textup{II}_{3}$
$\displaystyle\quad-\int_{t}^{s}\int_{\mathbb{R}}u(t,y(t,\eta))K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))\tilde{H}_{\xi}(t,\eta)d\eta
d\tau.$

Next we will show that each of the terms $\textup{II}_{1}$, $\textup{II}_{2}$,
and $\textup{II}_{3}$ is of order $|t-s|^{3/2}$. Therefore it is important to
keep in mind that $0\leq y_{\xi}$, $\tilde{H}_{\xi}\leq 1$.

$\textup{II}_{1}$: Since $u(t,x)$ is Hölder continuous with Hölder exponent
$\frac{1}{2}$ on $[0,T]\times\mathbb{R}$, we have, by (3.8) and (3.9), for all
$\tau$ between $s$ and $t$ that

$\displaystyle|u(\tau,y(\tau,\eta))-u(t,y(t,\eta))|$ $\displaystyle\leq
D\big{(}|t-\tau|+|y(\tau,\eta)-y(t,\eta)|\big{)}^{1/2}$ $\displaystyle\leq
D\big{(}1+\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}^{1/2}|t-\tau|^{1/2}$
$\displaystyle\leq
D\big{(}1+\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}^{1/2}|t-s|^{1/2},$

and

$|\textup{II}_{1}|\leq
DC\big{(}1+\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}^{1/2}|t-s|^{3/2}.$

$\textup{II}_{2}$: Since $K(\,\cdot\,)$, given by (4.3), is smooth one has for
all $\tau$ between $s$ and $t$ that

$\displaystyle|K(y(t,\xi+u(t,y(t,\xi))(t-s))$
$\displaystyle-y(\tau,\eta))-K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))|$
$\displaystyle=|\int_{y(t,\eta)}^{y(\tau,\eta)}K^{\prime}(y(t,\xi+u(t,y(t,\xi))(t-s))-x)dx|$
$\displaystyle\leq n|y(\tau,\eta)-y(t,\eta)|$ $\displaystyle\leq
n\Big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\Big{)}|t-\tau|$
$\displaystyle\leq
n\Big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\Big{)}|t-s|$

and

$|\textup{II}_{2}|\leq
nC\Big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\Big{)}^{2}|t-s|^{2}.$

$\textup{II}_{3}$: Here integration by parts will be the key. Indeed, one has

$\displaystyle\int_{\mathbb{R}}u(t,y(t,\eta))K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))(\tilde{H}_{\xi}(\tau,\eta)-\tilde{H}_{\xi}(t,\eta))d\eta$
$\displaystyle\quad=-\int_{\mathbb{R}}u_{x}(t,y(t,\eta))$
$\displaystyle\qquad\qquad\times
K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))(\tilde{H}(\tau,\eta)-\tilde{H}(t,\eta))y_{\xi}(t,\eta)d\eta$
$\displaystyle\qquad+\int_{\mathbb{R}}u(t,y(t,\eta))$
$\displaystyle\qquad\qquad\times
K^{\prime}(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))(\tilde{H}(\tau,\eta)-\tilde{H}(t,\eta))y_{\xi}(t,\eta)d\eta.$

Recalling (3.24) and that $0\leq\tilde{H}_{\xi}\leq 1$, we have for all $\tau$
between $s$ and $t$ that

$|\tilde{H}(t,\eta)-\tilde{H}(\tau,\eta)|\leq\Big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\Big{)}|t-s|$

and

$\displaystyle|$
$\displaystyle\int_{\mathbb{R}}u(t,y(t,\eta))K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))(\tilde{H}_{\xi}(\tau,\eta)-\tilde{H}_{\xi}(t,\eta))d\eta|$
$\displaystyle\leq\Big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\Big{)}\int_{\mathbb{R}}|u_{x}(t,x)|K(y(t,\xi+u(t,y(t,\xi))(t-s))-x)dx\,|t-s|$
$\displaystyle\quad+\Big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\Big{)}\int_{\mathbb{R}}|u(t,x)|K^{\prime}(y(t,\xi+u(t,y(t,\xi))(t-s))-x)dx\,|t-s|$
$\displaystyle\leq\Big{(}\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}C^{1/2}\pi^{1/2}+n\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}^{2}\pi\Big{)}|t-s|.$

Thus, we have

$|\textup{II}_{3}|\leq\Big{(}\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}C^{1/2}\pi^{1/2}+n\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}^{2}\pi\Big{)}|t-s|^{2}.$

Combining now all these estimates, we have that there exists a positive
constant $\check{M}$ such that

$\displaystyle\left|\textup{I}_{2}+\int_{\mathbb{R}}u(t,y(t,\eta))K(y(t,\xi+u(t,y(t,\xi))(t-s))-y(t,\eta))\tilde{H}_{\xi}(t,\eta)d\eta\,(s-t)\right|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq\check{M}|t-s|^{3/2}$

(ii): Combine (5.9), (5.30), and (A.1). ∎

######  Lemma A.2 (Lemma 5.6).

Consider the function $h$ defined by (5.45). Then
(i) $t\mapsto h(t,\eta)$ is continuous;
(ii) $\eta\mapsto h(t,\eta)$ is Lipschitz and satisfies

(A.2)
$|h(t,\eta_{2})-h(t,\eta_{1})|\leq(1+2n\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+C+\frac{n}{2}Ct)|\eta_{2}-\eta_{1}|.$

###### Proof.

(i) First, we establish the continuity with respect to time. Recalling (3.6),
(3.9), (4.4), (4.9), and (5.27), we have

$\displaystyle|\mathcal{U}\mathcal{P}(t,\eta)-\mathcal{U}\mathcal{P}(s,\eta)|$
$\displaystyle\leq|\mathcal{U}(t,\eta)||\mathcal{P}(t,\eta)-\mathcal{P}(s,\eta)|+|\mathcal{P}(s,\eta)||\mathcal{U}(t,\eta)-\mathcal{U}(s,\eta)|$
$\displaystyle\leq\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}|p(t,\chi(t,\eta))-p(s,\chi(s,\eta))|$
$\displaystyle\quad+C|u(t,\chi(t,\eta))-u(s,\chi(s,\eta))|$
$\displaystyle\leq\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT+2A\big{)}nC|t-s|$
$\displaystyle\quad+CD\big{(}1+2A\big{)}^{1/2}|t-s|^{1/2}.$

For the second term of $h(t,\eta)$, note that one can write

$\displaystyle\int_{0}^{B+C}$
$\displaystyle\mathcal{U}(t,\tilde{\eta})K(\chi(t,\eta)-\chi(t,\tilde{\eta}))(1-\mathcal{P}\chi_{\eta}(t,\tilde{\eta}))d\tilde{\eta}$
$\displaystyle=\int_{0}^{B+C}\mathcal{U}(t,\tilde{\eta})K(\chi(t,\eta)-\chi(t,\tilde{\eta}))d\tilde{\eta}-\int_{\mathbb{R}}K(\chi(t,\eta)-y)up(t,y)dy.$

Using (3.9), (5.27), and Lemma 4.1, one has

$\displaystyle\Big{|}\int_{0}^{B+C}$
$\displaystyle\Big{(}\mathcal{U}(t,\tilde{\eta})K(\chi(t,\eta)-\chi(t,\tilde{\eta}))-\mathcal{U}(s,\tilde{\eta})K(\chi(s,\eta)-\chi(s,\tilde{\eta}))\Big{)}d\tilde{\eta}\Big{|}$
$\displaystyle\leq\Big{|}\int_{0}^{B+C}(\mathcal{U}(t,\tilde{\eta})-\mathcal{U}(s,\tilde{\eta}))K(\chi(t,\eta)-\chi(t,\tilde{\eta}))d\tilde{\eta}\Big{|}$
$\displaystyle\quad+\Big{|}\int_{0}^{B+C}\mathcal{U}(s,\tilde{\eta})\big{(}K(\chi(t,\eta)-\chi(t,\tilde{\eta}))-K(\chi(s,\eta)-\chi(s,\tilde{\eta}))\big{)}d\tilde{\eta}\Big{|}$
$\displaystyle\leq(B+C)\left\|\mathcal{U}(t,\,\cdot\,)-\mathcal{U}(s,\,\cdot\,)\right\|_{L^{\infty}}$
$\displaystyle\quad+2n\big{(}\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT\big{)}(B+C)\left\|\chi(t,\,\cdot\,)-\chi(s,\,\cdot\,)\right\|_{L^{\infty}}$
$\displaystyle\leq(B+C)D\big{(}1+2A\big{)}^{1/2}|t-s|^{1/2}$
$\displaystyle\quad+2n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT)(B+C)2A|t-s|.$

Last but not least, recalling (3.9), Lemma 4.1, (4.4), (4.10), and (5.27), we
have

$\displaystyle\Big{|}\int_{\mathbb{R}}\big{(}K(\chi(t,\eta)-y)up(t,y)$
$\displaystyle-K(\chi(s,\eta)-y)up(s,y)\big{)}dy\Big{|}$
$\displaystyle\leq\Big{|}\int_{\mathbb{R}}(K(\chi(t,\eta)-y)-K(\chi(s,\eta)-y))up(t,y)dy\Big{|}$
$\displaystyle\quad+\Big{|}\int_{\mathbb{R}}K(\chi(s,\eta)-y)(up(t,y)-up(s,y))dy\Big{|}$
$\displaystyle\leq
n\left\|\chi(t,\,\cdot\,)-\chi(s,\,\cdot\,)\right\|_{L^{\infty}}\int_{\mathbb{R}}|u|p(t,y)dy$
$\displaystyle\quad+\pi\left\|up(t,\,\cdot\,)-up(s,\,\cdot\,)\right\|_{L^{\infty}}$
$\displaystyle\leq
2nA(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT)B|t-s|$
$\displaystyle\quad+\pi
n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}CT)^{2}C|t-s|+\pi
CD(t-s)^{1/2}.$

Thus we have that $h(t,\eta)$ is Hölder continuous with exponent $\frac{1}{2}$
with respect to time.

(ii) To establish the Lipschitz continuity with respect to space is a bit more
involved, but follows pretty much the same lines. As a closer look at (5.12)
reveals, one has

$\sigma G(t,\chi(t,\eta)-)+(1-\sigma)G(t,\chi(t,\eta)+)=\eta\quad\text{ for
some }\sigma\in[0,1].$

This means especially given $\eta\in[0,B+C]$, there exist
$\eta^{-}\leq\eta\leq\eta^{+}$ such that

$\chi(t,\eta^{-})=\chi(t,\eta)=\chi(t,\eta^{+})$

and

$\eta^{-}=G(t,\chi(t,\eta)-)\quad\text{ and
}\quad\eta^{+}=G(t,\chi(t,\eta)+).$

In view of Definition 2.3 (v), (5.3), (4.11), and (5.5), we then have for
$\eta_{1}<\eta_{2}$ such that $\chi(t,\eta_{1})\not=\chi(t,\eta_{2})$ that

$\displaystyle|\mathcal{U}\mathcal{P}(t,\eta_{2})-$
$\displaystyle\mathcal{U}\mathcal{P}(t,\eta_{1})|$
$\displaystyle=|\mathcal{U}\mathcal{P}(t,\eta_{2}^{-})-\mathcal{U}\mathcal{P}(t,\eta_{1}^{+})|$
$\displaystyle=|up(t,\chi(t,\eta_{2}^{-}))-up(t,\chi(t,\eta_{1}^{+}))|$
$\displaystyle\leq\int_{\chi(t,\eta_{1}^{+})}^{\chi(t,\eta_{2}^{-})}|u_{x}p+up_{x}|(t,y)dy$
$\displaystyle\leq\int_{\chi(t,\eta_{1}^{+})}^{\chi(t,\eta_{2}^{-})}(u_{x}^{2}+p^{2}+n|u|p)(t,y)dy$
$\displaystyle\leq(1+\left\|p(t,\,\cdot\,)\right\|_{L^{\infty}}+n\left\|u(t,\,\cdot\,)\right\|_{L^{\infty}})\int_{\chi(t,\eta_{1}^{+})}^{\chi(t,\eta_{2}^{-})}(u_{x}^{2}+p)(t,y)dy$
$\displaystyle\leq(1+C+n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}Ct))(G(t,\chi(t,\eta_{2}^{-}))-G(t,\chi(t,\eta_{1}^{+})))$
$\displaystyle=(1+C+n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}Ct))|\eta_{2}^{-}-\eta_{1}^{+}|$
$\displaystyle\leq(1+C+n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}Ct))|\eta_{2}-\eta_{1}|.$

As far as the second part is concerned, observe that (cf. (5.63))

$\int_{0}^{B+C}\mathcal{U}(t,\tilde{\eta})K(\chi(t,\eta)-\chi(t,\tilde{\eta}))(1-\mathcal{P}\chi_{\eta}(t,\tilde{\eta}))d\tilde{\eta}=\int_{\mathbb{R}}u(t,y)K(\chi(t,\eta)-y)d\mu(t,y),$

and we have

$\displaystyle|\int_{0}^{B+C}\mathcal{U}(t,\tilde{\eta})$
$\displaystyle(K(\chi(t,\eta_{2})-\chi(t,\tilde{\eta}))-K(\chi(t,\eta_{1})-\chi(t,\tilde{\eta})))(1-\mathcal{P}\chi_{\eta}(t,\tilde{\eta}))d\tilde{\eta}|$
$\displaystyle=|\int_{\mathbb{R}}u(t,y)(K(\chi(t,\eta_{2})-y)-K(\chi(t,\eta_{1})-y))d\mu(t,y)|$
$\displaystyle=|\int_{\mathbb{R}}u(t,y)\int_{\chi(t,\eta_{1})}^{\chi(t,\eta_{2})}K^{\prime}(z-y)dzd\mu(t,y)|$
$\displaystyle=|\int_{\chi(t,\eta_{1}^{+})}^{\chi(t,\eta_{2}^{-})}\int_{\mathbb{R}}u(t,y)K^{\prime}(z-y)d\mu(t,y)dz|$
$\displaystyle\leq(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}Ct)\int_{\chi(t,\eta_{1}^{+})}^{\chi(t,\eta_{2}^{-})}\int_{\mathbb{R}}nK(z-y)d\mu(t,y)dz$
$\displaystyle=n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}Ct)\int_{\chi(t,\eta_{1}^{+})}^{\chi(t,\eta_{2}^{-})}p(t,z)dz$
$\displaystyle=n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}Ct)\big{(}G(t,\chi(t,\eta_{2}^{-}))-G(t,\chi(t,\eta_{1}^{+}))\big{)}$
$\displaystyle\leq
n(\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+\frac{1}{4}Ct)|\eta_{2}-\eta_{1}|.$

Thus we have that $h(t,\eta)$ is Lipschitz continuous with respect to space
with

$|h(t,\eta_{2})-h(t,\eta_{1})|\leq\big{(}1+2n\left\|u(0,\,\cdot\,)\right\|_{L^{\infty}}+C+\frac{n}{2}Ct\big{)}|\eta_{2}-\eta_{1}|.$

∎

######  Lemma A.3.

Given $\gamma>2$ and a weak conservative solution $(u,\mu)$ in the sense of
Definition 2.3, which satisfies

$\int_{\mathbb{R}}(1+|x|^{\gamma})d\mu(t)<\infty\quad\text{ for all
}t\in\mathbb{R}.$

Then for any $n\in\mathbb{N}$ such that $n\geq\gamma$

$\int_{\mathbb{R}}(1+|x|^{\gamma})p(t,x)dx<\infty\quad\text{ for all
}t\in\mathbb{R}.$

###### Proof.

Due to (4.10) it suffices to show

$\int_{-\infty}^{-1}|x|^{\gamma}p(t,x)dx+\int_{1}^{\infty}|x|^{\gamma}p(t,x)dx<\infty.$

Since $p(t,\,\cdot\,)$ is non-negative and both integrals can be estimated
using the same ideas, we only present the details for the first one. Direct
computations yield

$\displaystyle\int_{-\infty}^{-1}|x|^{\gamma}p(t,x)dx$
$\displaystyle=\int_{-\infty}^{-1}(x^{2})^{\gamma/2}\int_{\mathbb{R}}\frac{1}{(1+(x-y)^{2})^{n}}d\mu(t,y)dx$
$\displaystyle=\int_{-\infty}^{-1}(((x-y)+y)^{2})^{\gamma/2}\int_{\mathbb{R}}\frac{1}{(1+(x-y)^{2})^{n}}d\mu(t,y)dx$
$\displaystyle\leq
2^{\gamma/2}\int_{-\infty}^{-1}\int_{\mathbb{R}}\left(\frac{(x-y)^{2}+y^{2}}{1+(x-y)^{2}}\right)^{\gamma/2}\frac{1}{(1+(x-y)^{2})^{n-\gamma/2}}d\mu(t,y)dx$
$\displaystyle\leq
2^{\gamma/2}\int_{-\infty}^{-1}\int_{\mathbb{R}}(1+y^{2})^{\gamma/2}\frac{1}{(1+(x-y)^{2})^{n-\gamma/2}}d\mu(t,y)dx$
$\displaystyle\leq
2^{\gamma/2}\int_{\mathbb{R}}\left(\int_{\mathbb{R}}\frac{1}{(1+(x-y)^{2})^{n-\gamma/2}}dx\right)(1+y^{2})^{\gamma/2}d\mu(t,y)$
$\displaystyle\leq
2^{\gamma/2}\int_{\mathbb{R}}\left(\int_{\mathbb{R}}\frac{1}{1+z^{2}}dz\right)(1+y^{2})^{\gamma/2}d\mu(t,y)$
$\displaystyle\leq
2^{\gamma/2}\pi\int_{\mathbb{R}}(1+y^{2})^{\gamma/2}d\mu(t,y)$
$\displaystyle\leq 2^{\gamma}\pi\int_{\mathbb{R}}(1+|y|^{\gamma})d\mu(t,y).$

In the above calculations we used that $(a+b)^{2}\leq 2(a^{2}+b^{2})$ and that
$(a+b)^{2}\leq 2\max(a^{2},b^{2})$. ∎

## References

  * [1] V. I. Bogachev, Measure Theory. Vol. I, II. Springer-Verlag, Berlin, 2007.
  * [2] A. Bressan, G. Chen, and Q. Zhang. Uniqueness of conservative solutions to the Camassa–Holm equation via characteristics. Discrete Contin. Dyn. Syst. 35 (2015) 25–42.
  * [3] A. Bressan and A. Constantin. Global solutions of the Hunter–Saxton equation. SIAM J. Math. Anal. 37 (2005) 996–1026.
  * [4] A. Bressan, H. Holden, and X. Raynaud. Lipschitz metric for the Hunter–Saxton equation. J. Math. Pures Appl. 94 (2010) 68–92.
  * [5] A. Bressan, P. Zhang, and Y. Zheng. Asymptotic variational wave equations. Arch. Ration. Mech. Anal. 183 (2007), 163–185.
  * [6] J. A. Carrillo, K. Grunert, and H. Holden. A Lipschitz metric for the Hunter–Saxton equation. Comm. Partial Differential Equations 44 (2019) 309–334.
  * [7] C. M. Dafermos. Generalized characteristics and the Hunter–Saxton equation. J. Hyperbolic Differ. Equ. 8 (2011) 159–168.
  * [8] K. Grunert and A. Nordli. Existence and Lipschitz stability for $\alpha$-dissipative solutions of the two-component Hunter–Saxton system. J. Hyperbolic Differ. Equ.  15 (2018) 559–597.
  * [9] K. Grunert, A. Nordli, and S. Solem. Numerical conservative solutions of the Hunter–Saxton equation. BIT Numerical Mathematics 61 (2021) 441–471.
  * [10] K. Grunert and M. Tandy. Lipschitz stability for the Hunter–Saxton equation. arXiv:2103.10227.
  * [11] H. Holden, K. H. Karlsen, and P.H.C. Pang. The Hunter–Saxton equation with noise. J. Differential Equations 270 (2021) 725–786.
  * [12] H. Holden, K. H. Karlsen, and N. H. Risebro. Convergent difference schemes for the Hunter–Saxton equation. Math. Comp. 76 (2007) 699–744.
  * [13] H. Holden and X. Raynaud. Global conservative solutions of the Camassa–Holm equation — a Lagrangian point of view. Comm. Partial Differential Equations 32 (2007) 1511–1549.
  * [14] J. K. Hunter and R. Saxton. Dynamics of director fields. SIAM J. Appl. Math. 51 (6) (1991) 1498–1521.
  * [15] J. K. Hunter and Y. X. Zheng. On a nonlinear hyperbolic variational equation. I. Global existence of weak solutions Arch. Rational Mech. Anal. 129 (4) (1995) 305–353.
  * [16] J. K. Hunter and Y. X. Zheng. On a nonlinear hyperbolic variational equation. II. The zero-viscosity and dispersion limits. Arch. Rational Mech. Anal. 129 (4) (1995) 355–383.
  * [17] B. Khesin and G. Misiołek. Euler equations on homogeneous spaces and Virasoro orbits. Adv. Math. 176 (2003) 116–144.
  * [18] J. M. Lee. Geometric approach on the global conservative solutions of the Camassa–Holm equation. J. Geom. Phys. 142 (2019) 137–150.
  * [19] J. Lenells. The Hunter–Saxton equation: a geometric approach. SIAM J. Math. Anal. 40 (2008) 266–277.
  * [20] J. Lenells. Weak geodesic flow and global solutions of the Hunter–Saxton equation. Discrete Contin. Dyn. Syst. 18 (2007) 643–656.
  * [21] J. Lenells. The Hunter–Saxton equation describes the geodesic flow on a sphere. J. Geom. Phys. 57 (2007) 2049–2064.
  * [22] H. Li and G. Toscani. Long–time asymptotics of kinetic models of granular flows. Arch. Ration. Mech. Anal. 172 (3) (2004) 407–428.
  * [23] A. Nordli. A Lipschitz metric for conservative solutions of the two-component Hunter–Saxton system. Methods Appl. Anal. 23 (2016) 215–232.
  * [24] M. Wunsch. The generalized Hunter–Saxton system. SIAM J. Math. Anal. 42 (2010) 1286–1304.
  * [25] M. Wunsch. On the Hunter–Saxton system. Discrete Contin. Dyn. Syst. Ser. B 12 (2009) 647–656.
  * [26] P. Zhang and Y. Zheng. On oscillations of an asymptotic equation of a nonlinear variational wave equation. Asymptot. Anal. 18 (3-4) (1998) 307–327.
  * [27] P. Zhang and Y. Zheng. On the existence and uniqueness of solutions to an asymptotic equation of a variational wave equation. Acta Math. Sin. (Engl. Ser.) 15 (1) (1999) 115–130.
  * [28] P. Zhang and Y. Zheng. Existence and uniqueness of solutions of an asymptotic equation arising from a variational wave equation with general data. Arch. Ration. Mech. Anal. 155 (1) (2000) 49–83.