\section{Introduction}

Disclosure avoidance (DA) systems are methods used to protect confidentiality while still enabling data analyses and dissemination. These techniques are used in various fields, such as economics, public health, social science, and data science, and have a long history in censuses and other data collection efforts. For example, the US Census Bureau has leveraged various traditional DA techniques from the 1930 decennial release on. These include suppressing certain tables based on the number of people or households in a given area and swapping data in records with similar characteristics. 

While traditional confidentiality measures, such as suppression \citep{kelly1992cell}, swapping \citep{dalenius1982data}, and k-anonymity \citep{sweeney2002k} are important for protecting against accidental or intentional disclosure, they lack formal guarantees that quantify the privacy risks that individuals incur upon data releases. This is important as it restricts the ability of participants to assess the impact of these protections on published data. 


In contrast, differential privacy (DP) \citep{Dwork:06} is a \emph{relatively newer} DA that provides a rigorous definition of privacy and allows for quantifiable privacy guarantees. In differential privacy, the privacy of an individual is preserved by adding noise to their data in a controlled way. Such a process ensures that the participation of an individual in a dataset does not significantly affect the results of subsequent queries. 
Marking a significant shift towards more rigorous privacy protections, the US Census has recently adopted differential privacy for the 2020 Census release. However, it is worth noting that many other data agencies and organizations still rely on traditional disclosure avoidance systems to protect the confidentiality of their data. 

While these approaches can be effective at protecting against accidental or intentional disclosures, it is unclear what privacy guarantees they provide when compared to differential privacy. On the other hand, while differential privacy can provide stronger privacy guarantees than traditional disclosure avoidance systems, it may come with a cost in terms of accuracy and fairness \citep{kuppam2019fair,Fioretto:IJCAIa,Fioretto:IJCAI22a}, a topic of considerable debate recently.

Given that these DA are used to release data products that inform decisions with significant societal and economic consequences, it is essential to conduct a rigorous comparison of traditional DA and differential privacy in terms of privacy, bias, and fairness.
However, one of the challenges faced in this comparison is the absence of a standardized framework for evaluating privacy protections. Differential privacy offers a rigorous definition of privacy and enables quantifiable privacy guarantees. On the other hand, traditional disclosure avoidance techniques may not have a distinct set of privacy metrics, making it challenging to directly compare the level of privacy protection they offer.

\begin{figure*}[!t]
\includegraphics[width=\linewidth]{scheme3.pdf}
\caption{\label{fig:scheme} Illustration of the various traditional DA mechanisms.}
\end{figure*}

\paragraph{Contributions} This paper aims at addressing this challenge: it proposes a framework for comparing traditional DA to differential privacy and makes four distinct contributions. (1) It first proposes {\em carefully randomized} versions of three widely adopted {\em traditional} DA: suppression, swapping, and k-anonymity. The resulting randomized mechanisms can then be analyzed rigorously. In particular, the paper  derives $(\epsilon,\delta)$-differential privacy bounds for these new mechanisms and demonstrates that they are close to their traditional counterparts in terms of accuracy. (2) The paper then derives bounds for the bias 

of the new DA mechanisms, allowing for a direct comparison with classical differential privacy techniques for which such bounds exist. 
(3) Next, the paper analyzes the fairness impact induced by the considered DA systems and shows that the fairness violations incurred by the randomized DA algorithms are close to those of their traditional counterparts. (4) Finally, it provides an extensive empirical analysis of the performance of the new DA mechanisms and a comparison with two classical differentially private algorithms on data release and classification tasks. 

{\em From a broader perspective, the paper demonstrates that, contrary to  popular belief, classical differential privacy mechanisms may be superior to traditional disclosure avoidance systems in important data release and learning tasks in terms of accuracy and fairness for the same privacy levels}. As a consequence, the results of this study have the potential to impact the way in which data agencies and organizations approach disclosure avoidance: indeed, it provides the first framework for comparing the relative strengths and limitations of traditional DA and differential privacy.

\section{Problem Setting}

The paper considers datasets of $m$ records with $d$ attributes, $A_1,\dots,A_d$. Each record is a $d$-dimensional tuple of attributes associated with a unique individual from a data universe $\mathcal{X}\coloneqq \prod_{i=1}^d \dom{A_i}$,
where $\dom{A}$ represents the collection of all the possible values for the attribute $A$.
For convenience, assume that $\mathcal{X} = \{\bm{a}_1, \ldots, \bm{a}_n\}$, with $n$ being the size of the data universe $\mathcal{X}$, and consider the \emph{histogram} $\bm{x}(D) \in \mathbb{N}^n_+$ of dataset $D$, whose $i^{th}$ entry $x_i(D)$ represents the count of the individual records with the combination of attributes $\bm{a}_i$.
When there is no ambiguity, the dataset $D$ is omitted in the expression $\bm{x}(D)$ for simplicity.
Additionally, and without loss of generality, the histogram $\bm{x}$ is assumed to be sorted in some increasing order, i.e., $x_i\leq x_j$, for any $i<j$. Finally, each entry of the histogram $\bm{x}$ is assumed to be bounded by a value $B > 0$, i.e., $\bm{x}\in [B]^n$. 

Consider, for example, the illustration in Figure \ref{fig:scheme}(a);
The dataset $D$ contains records with three attributes: (geographic)
``Block'', ``Gender'', and ``Voting Age''. The associated histogram is
illustrated in Figure \ref{fig:scheme}(b).  In this instance, the
attribute ``Gender'', when combined with external information like
``Zip code'', can become personally identifying information and
thus is known as a \emph{quasi-identifier} (QI) while the remaining
attributes are referred to as \emph{non-quasi-identifiers}. Throughout
the paper, the sets of quasi-identifiers and non-quasi-identifiers are
denoted by $Q$ and $N$, respectively. Given a record $\bm{a}$ and
a set $S$ of attributes, $\bm{a}[S]$ is the vector of values for
attributes $S$ in $\bm{a}$.

The goal of the paper is to analyze the privacy, utility, and fairness properties of traditional disclosure avoidance systems (reviewed in the next section) on the task of releasing a privacy-preserving version $\tilde{\bm{x}}(D)$ of the histogram $\bm{x}(D)$. 
The notion of privacy considered in this paper is that of differential privacy, which is reviewed in the next section. The notions of utility and fairness central to the analysis rely on the concept of (statistical) \emph{bias}. For any entry $i\in [n]$, the bias associated with a mechanism $\mathcal{M}$ is 
\[
    \mathcal{B}(\mathcal{M})_{i}=\EE{}{\mathcal{M}(D)_i}-x_i(D)\,,
\]
where the expectation is taken over the randomness of the mechanism, and
\(
    \bias{\mathcal{M}}=\left[
    \begin{matrix}
        \biasi{\mathcal{M}}{1}&\dots&\biasi{\mathcal{M}}{n}
    \end{matrix}
    \right].
\)
Fairness is defined as the maximal difference in biases across the histogram entries.
\begin{definition}[$\alpha$-fairness \citep{ijcai2022p559}]\label{def:a-fair}
    A  mechanism $\mathcal{M}$ is said to be $\alpha$-fair if the maximum difference among 
    the biases is bounded by $\alpha$, i.e.,
    \begin{equation*}
        \lVert\bias{\mathcal{M}}\rVert_{\rightleftharpoons} = \max_{i\in[n]}~\biasi{\mathcal{M}}{i}-\min_{i\in[n]}~\biasi{\mathcal{M}}{i}\leq \alpha.
    \end{equation*}
\end{definition} 

\section{DA for Private Data Release}
\label{sec:das}

This section provides an overview of the prevalent DA methods utilized by data agencies to safeguard sensitive information within datasets. 
To comply with space limitations, the paper reports the proofs of all theorems in the appendix. 

\paragraph{Differential Privacy.}
Differential privacy (DP) \citep{Dwork:06} is a strong privacy notion used to quantify and bound the privacy loss of an individual participation to a computation. 
 Informally, it  states that the probability of any output does not change much when a record is changed from a dataset, limiting the amount of information that the output reveals about any individual.  
The action of changing a record from a dataset $D$, resulting in a new dataset $D'$, defines the notion of \emph{adjacency}, denoted $D \sim D'$.
\begin{definition}
  \label{dp-def}
  A mechanism $\mathcal{M} \!:\! \mathcal{D} \!\to\! \mathcal{R}$ with domain $\mathcal{D}$ and range $\mathcal{R}$ is $(\epsilon, \delta)$-differentially private, if, for any two inputs $D \sim D' \!\in\! \mathcal{D}$, and any subset of output responses $R \subseteq \mathcal{R}$:
  \[
      \Pr[\mathcal{M}(D) \in R ] \leq  e^{\epsilon} 
      \Pr[\mathcal{M}(D') \in R ] + \delta.
  \]
\end{definition}
\noindent 
Parameter $\epsilon > 0$ describes the \emph{privacy loss} of the algorithm, with values close to $0$ denoting strong privacy, while parameter $\delta \in [0,1)$ captures the probability of failure of the algorithm to satisfy $\epsilon$-DP. 
In particular, the \emph{Laplace mechanism} for histogram data release, defined by
\(
    \mathcal{M}_{\text{Lap}}(\bm{x}) = \bm{x} + \text{Lap}(\nicefrac{2}{\epsilon}), 
\)
\noindent where $\text{Lap}(\eta)$ is the Laplace distribution centered at 0 and with scaling factor $\eta$, satisfies $(\epsilon, 0)$-DP. 
Additionally, the \emph{discrete Gaussian mechanism} \citep{canonne2020discrete}, defined by
\(
    \mathcal{M}_{\text{Gaus}}(\bm{x}) = \bm{x} + \mathcal{N}_{\mathbb{Z}}(0, \nicefrac{4}{\epsilon^2}), 
\)
where $\mathcal{N}_\mathbb{Z}(0, \sigma)$ is the discrete Gaussian distribution with $0$ mean and standard deviation $\sigma$, satisfies $(\frac{1}{2}\epsilon^2 + \epsilon \sqrt{2 \log(\nicefrac{1}{\delta})}, \delta)$-DP. 

We next discuss three predominant traditional DA systems which, in contrast to differential privacy, do not provide formal bounds on privacy leakage. 

\paragraph{Cell suppression.}
The cell suppression technique \citep{kelly1992cell}, frequently employed by statistical agencies (e.g., \citep{mog}), aims at concealing the low-frequency counts in histograms before data dissemination. 
\begin{definition}
Given a histogram $\bm{x}$ and a threshold value $k$, cell suppression returns a private histogram $\tilde{\bm{x}}$ with entries
\begin{equation}\label{eq:cell_suppression}
\tilde{\bm{x}}_i = \max\left\{\bm{x}_i, \nicefrac{k}{2}\right\}.
\end{equation}
\end{definition}
\noindent
Figure~\ref{fig:scheme}(c) illustrates the application of cell suppression with threshold value $k=2$ to the histogram of Figure~\ref{fig:scheme}(b). The affected row counts are highlighted in red. 
A significant limitation of this approach is that it only protects sensitive attributes with a low number of records while neglecting others.

\paragraph{Swapping.}
Swapping \citep{dalenius1982data} is a mechanism that swaps the values of a set of sensitive attributes (the quasi-identifiers) in a record with those of another record. Informally speaking, the basic steps of the algorithms can be summarized as follows:
\begin{enumerate}[leftmargin=*, parsep=0pt, itemsep=0pt, topsep=2pt]
    \item Select multiple pairs of records in the histogram with probability proportional to their discrepancies;
    \item Swap the values of the quasi-identifiers attributes for each selected pair of records.  
\end{enumerate}

\noindent
Like cell suppression, swapping produces a privacy-preserving histogram $\tilde{\bm{x}}$. However, contrary to cell suppression (and differential privacy mechanisms), swapping requires a piece of additional information: the quasi-identifier attributes of the dataset. Figure~\ref{fig:scheme}(d) illustrates the application of swapping where two rows are swapped, using ``Gender'' as the quasi-identifier attribute (see figure (a)). The affected row counts are highlighted in red. While swapping has been commonly used, for example by the US Census Bureau, to swap similar individuals within close geographies, it is not immune to reconstruction attacks \citep{garfinkel2019understanding}.


\paragraph{$k$-anonymity.\!\!\!\!}
Next, $k$-anonymity protects sensitive data in a dataset by ensuring that each record in the dataset is indistinguishable from at least $k-1$ other records.

\begin{definition}[$k$-Anonymity \citep{sweeney2002k}]\label{def:k-anonymity}
    A dataset satisfies $k$-anonymity, relative to a set of the quasi-identifiers, if and only if when the dataset is projected to include only quasi-identifiers, every record appears at least $k$ times.
\end{definition}

The basic idea behind $k$-anonymity is to generalize
certain identifying attributes of individuals in the dataset such 
that each group of individuals with similar characteristics contains 
at least $k$ individuals. An outline of the algorithm is 
provided below (a formal description is given in Appendix~\ref{app:sec:DA_alg}):

\begin{enumerate}[leftmargin=*, parsep=0pt, itemsep=0pt, topsep=2pt]
    \item define a \emph{hierarchy} $H$ for each quasi-identifier;
    \item constructs a histogram that lists the number of records for each combination of quasi-identifiers;
   
   
    \item suppress the combinations in the generalization histogram that have fewer than $k$ instances.
    \item release the resulting histogram $\tilde{\bm{x}}(D, H)$.
\end{enumerate}
An important observation is that, contrary to the previous methods reviewed, $k$-anonymity produces a privacy-preserving histogram $\tilde{\bm{x}}(D,H)$ in a different space than $\mathcal{X}$. 
This important observation will be relevant in the error analysis. 
It additionally requires access to quasi-identifier attributes as well as a generalization histogram. 

Figure~\ref{fig:scheme}(e) illustrates the application of $k$-anonymity with $k\!=\!2$ to the histogram of Figure~\ref{fig:scheme}(b), using a
generalization hierarchy grouping Males and Females into a single attribute. 
Despite being widely adopted to publish statistics and medical data, k-anonymity does not prevent re-identification attacks that exploit external public data \citep{li2011provably}. 




\section{DA Analysis Roadmap}
\label{sec:roadmap}

This section outlines the methodology followed in the rest of the
paper.
Section~\ref{sec:privacy_analysis} presents DP counterparts to traditional DA systems, including cell suppression, swapping, and k-anonymity. It aims to show that these DP counterparts preserve the main characteristics of the original mechanisms and provide an analysis of their privacy and errors under a unified privacy setting of histogram data release $\tilde{\bm{x}}(D)$. 
It is important to note that classical DP
algorithms (e.g., Laplace mechanism) and cell suppression, 
make no assumptions about data attributes. In contrast,
swapping relies on the use of quasi-identifiers, 
and $k$-anonymity further requires a generalization hierarchy 
This hierarchy forces k-anonymity to
produce a histogram $\tilde{\bm{x}}(D,H)$ in a different space than
that of $\tilde{\bm{x}}(D)$. While this does not affect the privacy analysis, which
allows for a meaningful comparison across all mechanisms, it
challenges the evaluation of the performance of these techniques.  The
paper addresses this challenge by also presenting a unified empirical
framework for comparing the errors and biases of the various
techniques in terms of the original data space $\mathcal{X}$. This
necessitates a reconstruction step for k-anonymity, which is outlined
in Appendix~\ref{app:dp_kanonimity}. It is important to recognize that,
while the DP DA mechanisms share many characteristics with their
traditional DA counterparts, {\em they should not be considered as
``noisy'' versions of them}. As a result, the analytical and
experimental results presented may not necessarily show a decrease in
error as the privacy budget increases. In fact, they may even be more
precise than the traditional mechanisms for some privacy budgets.

Next, we present the DP versions of the traditional DA systems and 
their privacy analyses. These analyses specify the value of the $\delta$ parameter for a given value of $\epsilon$. Section~\ref{sec:fairness} analyzes the fairness
 results. Finally, Section~\ref{sec:experiments} presents an
 experimental evaluation on an extract of the American Community Survey (ACS) data \citep{SDNist}.




\section{Privacy and Errors Analysis}
\label{sec:privacy_analysis}

This section presents the first main contribution of the paper. It
introduces differentially private counterparts to the DA presented
earlier and analyzes their privacy guarantees and errors.  The
section starts with a technical lemma that specifies a sufficient
condition for $(\epsilon,\delta)$-DP. The lemma is a critical tool to
derive the privacy guarantees of the randomized versions of the DA
discussed next.

\begin{lemma}\label{lem:dp_cond}
Let $D$, $D'$ be datasets such that $D\sim D'$, let $S$ be defined as 
\begin{equation*}
        S\coloneqq\left\{\bm{o}~\middle\vert~ \frac{\pr{\mathcal{M}(D)=\bm{o}}}{\pr{\mathcal{M}(D')=\bm{o}}}\leq\exp(\epsilon) \right\}\,
\end{equation*}
and let $S^\complement$ denote the complement set of $S$. If   
\begin{equation*}
\pr{\mathcal{M}(D)\in S^\complement}\leq \delta\,,
\end{equation*}
then mechanism $\mathcal{M}$ is $(\epsilon,\delta)$-differentially private.
\end{lemma}


\subsection{Differentially Private Cell Suppression}
\label{sec:cell_suppression}



While cell suppression protects the privacy of the minorities of the
dataset, it neglects the privacy protection of the majorities and thus
does not satisfy the requirements of differential privacy.  Indeed,
the deterministic nature of this mechanism prevents it from generating
different outputs for two neighboring datasets. An extended discussion
is deferred to Appendix~\ref{app:sec:DA_alg}. To address this issue, the
paper introduces a randomized version of cell suppression, referred
to as \emph{DP cell suppression}. This mechanism, denoted by $\cM_{\text{CS}}$,
releases a private count for every $i \in [n]$ as follows:
\begin{equation}
\label{eq:DPsuppression}
\cM_{\text{CS}}(D)_i = \hat{x}_i =
\begin{cases}
x_i & \text{if } x_i+\eta_i \geq k, \\
\nicefrac{k}{2} & \text{otherwise}
\end{cases},
\end{equation}
where $\eta_i \sim \lap{2/\epsilon}$ is an additive noise variable drawn from a 0-centered Laplace distribution with factor $\nicefrac{2}{\epsilon}$ and $k$ is the cell suppression threshold.

Mechanism $\cM_{\text{CS}}$ has similarities with the \textsl{Sparse Vector
Technique} (SVT) \citep{dwork2014algorithmic} which, given a sequence
of queries and a real-valued threshold, outputs a vector indicating
whether each (noisy) query answer is above or below the corresponding
(noisy) threshold.  However, there are three fundamental differences:
(1) $\cM_{\text{CS}}$, does not perturb the threshold value $k$; (2) it
generates numeric outputs in contrast to binary outputs
of \textsl{SVT}; and (3) it reports true counts rather than noisy
counts, as long as the noisy counts are above the threshold (first
condition of Equation~\eqref{eq:DPsuppression}).

Figure~\ref{fig:error}(left) reports the empirical errors of $\cM_{\text{CS}}$
for several threshold values $k$ ($x$-axis) and $\epsilon$ parameters.
The errors are given for the ACS Massachusetts dataset \citep{SDNist} (described in
details in Appendix~\ref{app:datasets}): they report the $\ell_1$
distances $\| \tilde{\bm{x}} - \bm{x}\|_1$ between the
histograms of the cell suppression and its DP counterpart. Notice
how close the errors incurred by $\cM_{\text{CS}}$ are with respect to the
original mechanism.
This is important as it enables a meaningful comparison of $\cM_{\text{CS}}$ and other DP mechanisms, since
$\cM_{\text{CS}}$ has a similar bias as the traditional cell suppression that is
currently widely adopted by statistical agencies and organizations.


\paragraph{Privacy Analysis.}
The next theorem reports the privacy guarantee provided by $\cM_{\text{CS}}$.
\begin{figure*}[!t]
\centering
\includegraphics[width=0.3\textwidth]{MA_DP_Suppression_Utility_Errors_Decimal.pdf} 
\includegraphics[width=0.37 \textwidth]{swap_comparison.pdf}
\includegraphics[width=0.3\textwidth]{MA_kAnonymity_Utility_Errors_Decimal.pdf}
\caption{MA ACS dataset: Errors $\Vert \tilde{\bm{x}}- \bm{x}\Vert_1$ for cell suppression (left), 
swapping (center) and $k$-anonymity (right) and their differentially 
private counterparts (average of 200 repetitions).}
\label{fig:error}
\end{figure*}

\begin{theorem}\label{thm:sup_dp_param}
Given a value $\epsilon > 0$ and a threshold $k<B$, mechanism $\cM_{\text{CS}}$ is $(\epsilon,\delta)$-differentially private with
\[
        \delta= 1-\frac{1}{4}\exp\left(-\epsilon(B-k)\right)\,,
\]
    where $B$ is a bound on the histogram entries.
\end{theorem}

\paragraph{Error Analysis.}
Having examined privacy, the paper shows how close the histograms $\tilde{\bm{x}}$ returned by $\cM_{\text{CS}}$
are to the original histogram $\bm{x}$. The
error analysis focuses on the statistical bias which, for each entry $i\in[n]$, 
can be expressed as
\begin{equation*}
    \resizebox{.99\linewidth}{!}{$
            \displaystyle
            \biasi{\cM_{\text{CS}}}{i} =\EE{}{\cM_{\text{CS}}(D)_i}-x_i
    =\left(\frac{k}{2}-x_i\right)\cdot \pr{x_i+\eta_i<k}.
        $}
\end{equation*}%


\noindent
Observe that the error merely takes place when the noisy count is
below the threshold $k$ and is quantified as the difference between
half of the threshold and the true count. Therefore, the following
theorem relates the errors associated with $\cM_{\text{CS}}$ with the 
probabilities of noisy counts being below the
threshold, and the differences between half of the threshold and the
counts of the original histogram.

\begin{theorem}\label{prop:sup_bias_bound}
The statistical bias of the DP cell suppression mechanism $\cM_{\text{CS}}$ can be bounded as follows,
    \begin{equation*}
        \lVert \bias{\cM_{\text{CS}}}\rVert_1\leq \left\lVert \nicefrac{k}{2}\cdot \bm{1}_n - \bm{x}\right\rVert_2 \cdot 
           \left\Vert \bm{p}\right\rVert_2\,,
    \end{equation*}
    where $\bm{p}$ is a shorthand for the vector 
    \begin{equation}\label{eq:p_vector}
        \bm{p}\coloneqq\left[
        \begin{matrix}
         \pr{x_1+\eta_1<k}&\dots&\pr{x_n+\eta_n<k}
        \end{matrix}
        \right].
    \end{equation}
\end{theorem}

\noindent

\subsection{Differentially Private Swapping}\label{subsec:dpswap}
Despite its randomized nature, the swapping mechanism fails to meet
the requirements of differential privacy. To illustrate its failure,
let us take a look at an instance of two neighboring datasets $D$
and $D'$. Suppose that $D'$ has a record, say $\bm{a}_1$, which
does not match any record in $D$ for any attribute $A\in Q$. No
matter how swapping is performed, it cannot generate a record
$\bm{a}_1$ from the input dataset $D$.

To obtain a DP counterpart to swapping, {\em it is thus critical to
reason about the universe of quasi-identifiers, not simply the set of
quasi-identifiers present in the database.} Let $\cX_{\qi}
= \{\bm{q}_1,\dots,\bm{q}_{\qiattrs}\}$ denote the data universe of
quasi-identifiers. Instead of swapping quasi-identifiers, the
mechanism will randomly choose some quasi-identifiers from
$\cX_{\qi}$.  
The mechanism, referred to as DP swapping and denoted
by $\mathcal{M}_{\text{SW}}$, works as follows: for every $\bm{a}_i \in \mathcal{X}$,
consider the pair $(\bm{a}_i, x_i)$ denoting the tuple and its
associated count in the histogram $\bm{x}$. $\mathcal{M}_{\text{SW}}$ defines
$\tilde{\bm{a}}_i[N] = \bm{a}_i[N]$ and
\begin{equation}
\label{eq:dp_swap_def}
\tilde{\bm{a}}_i[Q] =
\begin{cases}
  \bm{a}_i[Q] & \text{w.p. } \gamma = \frac{\exp(\epsilon)}{\exp(\epsilon)+n_Q-1}, \\
\text{Uniform}(\cX_{\qi}\setminus \bm{a}_i[Q]) & \text{w.p. } 1 - \gamma
\end{cases}
\end{equation}
where $\text{Uniform}(C)$ denotes the uniform probability over the
event space $C$.  The result of the step above may create multiple
entries $(\tilde{\bm{a}}_i, x_i)$ and $(\tilde{\bm{a}}_j, x_j)$ with
$\tilde{\bm{a}}_i = \tilde{\bm{a}}_j$. The procedure collapses all
such tuples by summing the various $x_i$ and $x_j$. The induced
sub-histogram is then extended to a histogram $\tilde{\bm{x}}$.  
Notice that $\mathcal{M}_{\text{SW}}$ only modifies quasi-identifiers and produces
a private histogram $\tilde{\bm{x}}(\tilde{D})$, similarly to what 
done by the original swapping algorithm.

Figure~\ref{fig:error} (center) compares the $\ell_1$ distances
$\| \tilde{\bm{x}} - \bm{x}\|_1$ between the histograms generated by
$\cM_{\text{SW}}$ and its traditional counterpart for various amounts of
rows swapped (in \%) and parameters $\epsilon$. Once again, observe how close the
errors of the two mechanisms are.

\paragraph{Privacy analysis.}
Recall that differential privacy protects the disclosure of any individual user participating in the dataset. On the other hand, DP swapping operates at the level of a histogram count and it does so in way which impedes an analysis relying on pure $(\epsilon, 0)$-DP. The privacy analysis of $\mathcal{M}_{\text{SW}}$ is reported in the following theorem.
\begin{theorem}\label{thm:new_pram_dp_param}
    For a given $\epsilon > 0$, the $\mathcal{M}_{\text{SW}}$ algorithm is $\left(\epsilon,\delta\right)$-DP 
    with $\delta$ given by
    \begin{equation*}
        1-\frac{1-\gamma^2}{\qiattrs-1}-\left(\frac{1-\gamma}{\qiattrs-1}\right)^2,
    \end{equation*}
    with $\gamma$ defined in Equation \eqref{eq:dp_swap_def} and $\qiattrs=\vert\cX_{\qi}\vert$, 
\end{theorem}

\paragraph{Error analysis.\!\!}
Next we discuss how close the errors of the histograms 
returned by swapping and its DP counterparts are.

\begin{proposition}\label{prop:pram_bias_exp}
The bias associated with each element $i\in[n]$ of the DP swapping 
histogram can be expressed as
\begin{equation*}
    \biasi{\cM_{\text{SW}}}{i}=\frac{\sum_{j\in \mathcal{I}_i} x_{j} - \qiattrs\cdot x_{i}}{\exp(\epsilon)+\qiattrs-1},
\end{equation*} 
with the index set $\mathcal{I}_i$ collecting all the elements of the data universe $\mathcal{X}=\left\{\bm{a}_j\mid j\in [n]\right\}$, which share the same non-quasi-identifiers
$N$ with $\bm{a}_i$, i.e.,
\begin{equation}\label{eq:index_set}
    \mathcal{I}_i \coloneqq\left\{j\in[n]~\middle\vert~ \bm{a}_j[N]=\bm{a}_i[N]\right\}.
\end{equation}
\end{proposition}

\begin{theorem}
The statistical bias of the DP swapping mechanism $\cM_{\text{SW}}$ can be expressed as follows,
    \begin{equation*}
        \norm{\bias{\cM_{\text{SW}}}}_1=\frac{\qiattrs}{\exp(\epsilon)+\qiattrs-1}\sum_{i=1}^{n}\mad{\bm{x}_{\mathcal{I}_i}},
    \end{equation*}
    where $\mathcal{I}_i$ is an index set defined in Equation \eqref{eq:index_set} and
    $\bm{x}_{\mathcal{I}_i}$ is the reduced histogram consisting of the count $x_j$ for any $j\in\mathcal{I}_i$.
   Additionally,
    $\mad{\bm{x}_{\mathcal{I}_i}}$ is the mean absolute deviation of the histogram $\bm{x}_{\mathcal{I}_i}$, i.e.,
    \begin{equation*}
        \mad{\bm{x}_{\mathcal{I}_i}}\coloneqq\frac{1}{\qiattrs}\sum_{j\in \mathcal{I}_i} \left\vert x_{j} - \frac{\sum_{l\in\mathcal{I}_i} x_{l}}{\qiattrs}\right\vert.
    \end{equation*}
\end{theorem}


\subsection{Differentially Private $k$-anonymity}

Like cell suppression, $k$-anonymity is a deterministic algorithm,
which cannot produce outputs satisfying DP.  In recent years, however, there
were several attempts to integrate $k$-anonymity and differential
privacy. In particular, \citet{li2011provably} proposed a mechanism
that applies the generalization histogram and cell suppression with
parameter $k$ to a subsampled version of the original dataset. This
paper proposes a generalization of this mechanism.

\begin{figure*}[!t]
\centering
\includegraphics[width=0.3\textwidth]{MA_DP_Suppression_Fairness_Errors_Decimal.pdf}
\includegraphics[width=0.343\textwidth]{MA_Swapping_Fairness_Errors_Decimal.pdf}
\includegraphics[width=0.3\textwidth]{MA_kAnonymity_Fairness_Errors_Decimal.pdf}
\caption{MA ACS dataset: Fairness values $\alpha$ for cell suppression (left), 
swapping (center) and $k$-anonymity (right) and their differentially 
private counterparts (average of 200 repetitions).}
\label{fig:fairness}
\end{figure*}


\paragraph{DP $k$-anonymity algorithm.}
The paper proposes a simple modification to the $k$-anonymity 
algorithm presented in the previous section. The mechanism, 
called DP-$k$-anonymity and denoted by $\mathcal{M}_{\text{KA}}$, operates in two steps:
\begin{enumerate}[leftmargin=*, parsep=2pt, itemsep=0pt, topsep=2pt]
    \item Produce a subsampled version $D_\beta$ of the  dataset $D$ in which each row is retained with probability $\beta \!\in\! (0,1)$.
    \item Apply the classical $k$-anonymity algorithm on $D_\beta$.
\end{enumerate}

\noindent
Contrary to \citep{li2011provably}, $\mathcal{M}_{\text{KA}}$ makes it possible
to use a generalization hierarchy for merging cells, like in its
deterministic counterpart.  Figure~\ref{fig:error} (right) reports the
empirical errors of $\mathcal{M}_{\text{KA}}$ for several values $k$ (x-axis);
The values of $\beta$ are implied by the choice of the privacy
parameter $\epsilon$ (see Theorem~\ref{thm:beta_dp_param}).  The
figure reports the $\ell_1$ distances between the histograms (in the
original space $\mathcal{X}$) reconstructed from the generalized DP
k-anonymized and the original histogram $\bm{x}(D)$ as well as those
derived via its deterministic counterpart. A description of
the reconstruction step adopted is provided in Appendix~\ref{app:sec:DA_alg}.
Once again, notice that the errors incurred by the DP and
deterministic $k$-anonymity counterparts are very close to each other:
in fact, the DP versions improve upon the deterministic mechanism for
small values of $\epsilon$ as an artifact of the sampling procedure 
which considers fewer records.

\paragraph{Privacy Analysis.}
The next result generalizes \citep{li2011provably} and reports the
privacy guarantees provided by $\mathcal{M}_{\text{KA}}$.
\begin{theorem}\label{thm:beta_dp_param}
For a given $k\!>\!0$ and sampling probability $\beta \!\in\! (0,1)$, $\mathcal{M}_{\text{KA}}$ satisfies
$(\epsilon,\delta)$-DP for $\delta \!=\! d(k, \beta, \epsilon)$, where the
function $d$ is defined as
\begin{equation}\label{eq:beta_mech_delta_def}
    d(k, \beta, \epsilon)= 1-\min_{w\in [B]}~
       \left(\sum_{j=0}^{\nu}f(j;w,\beta)\right)^2\,,
      
\end{equation}
$\nu$ is a shorthand for $\lfloor(1-\exp(-\epsilon))w\rfloor$
and $f$ represents the probability mass function of the binomial
random variable,
\begin{equation}\label{eq:binom_pmf}
f(j;w,\beta)=\binom{w}{j}\beta^w(1-\beta)^{w-j}\,,\quad \forall~j\in
[w], \end{equation}
\end{theorem}


\paragraph{Error Analysis.\!\!}
The goal of the analysis is again to show that the DP version of
$k$-anonymity is close, in errors, to its deterministic counterpart.
Recall that, contrary to cell suppression and swapping, $k$-anonymity
does not return a histogram in the same space of the
attribute universe, due to its application of the generalization
hierarchy.  As a consequence, the output of $k$-anonymity consists of
the counts of individual records with respect to the data universe
$\mathcal{X}_H$ of the generalization hierarchy. Because of this critical
difference, the rest of this section analyzes the mechanism errors by
bounding whether a count of the histogram $\bm{x}(D_\beta)$
(produced in step 1) is merged by the $k$-anonymization step (step~2).

\noindent
Let $\cM_{\text{KA}}^{\beta}$ denote the binary vector
\begin{equation*}
    \cM_{\text{KA}}^{\beta}\left(D_\beta\right)\coloneqq
    \left[
    \begin{matrix}
         \bm{1}\left\{x_1\left(D_\beta\right)<k\right\}&\dots&\bm{1}\left\{x_n\left(D_\beta\right)<k\right\}
    \end{matrix}
   \right].
\end{equation*}
The error analysis focuses on statistical bias regarding whether a
count would be merged by the generalization hierarchy, i.e., the
difference between $\cM_{\text{KA}}^{\beta}\left(D_\beta\right)$ and $\cM_{\text{KA}}^{\beta}(D)$:
\begin{align*}
     \bias{\cM_{\text{KA}}^{\beta}}
    &=\EE{}{\cM_{\text{KA}}^{\beta}\left(D_\beta\right)}-\cM_{\text{KA}}^{\beta}(D)\\
    &=\left[
    \begin{matrix}
        \mathbb{E}\left[\bm{1}\left\{x_1\left(D_\beta\right)<k\right\}\right]
        -\bm{1}\left\{x_1<k\right\}\\
        \vdots\\
         \mathbb{E}\left[\bm{1}\left\{x_n\left(D_\beta\right)<k\right\}\right]-\bm{1}\left\{x_n<k\right\}
    \end{matrix}
    \right]^\top.
\end{align*}

\noindent
Next, we establish the equivalence between the count
$x_i(D_\beta)$ and a binomial random variable $B(x_i, \beta)$ and
presents the mathematical expressions characterizing the bias.
\begin{theorem}
The statistical bias associated of the DP $k$-anonymity mechanism $\cM_{\text{KA}}^{\beta}$ 
ca be expressed as, each $i\in[n]$,
    \begin{align*}
        &\biasi{\cM_{\text{KA}}^{\beta}}{i}=\EE{}{\bm{1}\left\{x_i\left(D_{\beta}\right)<k\right\}}-\bm{1}\left\{x_i <k\right\}\\
        =~&\begin{cases}
            \sum_{j=x_i-k+1}^{x_i} \binom{x_i}{j} \beta^{x_i-j}(1-\beta)^j\,, &x_i\geq k,\\
            0, &\mathrm{otherwise.}
        \end{cases}
    \end{align*}
\end{theorem}

\section{Fairness analysis }
\label{sec:fairness}

The second main contribution of this paper is an analysis of the
fairness of various differentially private DA algorithms, compared to
traditional differential privacy. The definition of fairness used in
this paper (Definition~\ref{def:a-fair}) is the maximum difference in
biases in the privacy-preserving histograms.  It should be noted that
the bias of the DP $k$-anonymity algorithm, which utilizes a
generalization histogram, is examined in a different context than the
one of the other mechanisms. Thus, the paper specifically focuses on
an analytical comparison of the fairness of the DP $k$-anonymity
algorithm.

The next result quantifies the unfairness of the DP cell suppression and swapping, along with the Laplace mechanism.

\begin{theorem}[$\alpha$-fairness for $\mathcal{M}_{\text{CS}}$]\label{prop:sup_fair_bound}
  The DP cell suppression algorithm is $\alpha_{\text{CS}}$-fair with $\alpha_{\text{CS}}$ given by
    \begin{equation*}
        \left(x_n-x_1\right)p_1+\max\left\{\left\vert\frac{k}{2}-x_1\right\vert,\left\vert\frac{k}{2}-x_n\right\vert\right\}(p_1-p_n),
    \end{equation*}
    where $p_1$ and $p_n$ are the first and last entries of $\bm{p}$ defined in Equation \eqref{eq:p_vector} respectively.
\end{theorem}



\begin{theorem}[$\alpha$-fairness for $\mathcal{M}_{\text{SW}}$]
\label{prop:pram_fair_bound}
    The DP swapping algorithm $\mathcal{M}_{\text{SW}}$ is
     $\alpha_{\text{SW}}$-fair with $\alpha_{\text{SW}}$ given by
    \begin{equation*}
       \frac{2\qiattrs\norm{\bm{x}}_{\rightleftharpoons}}{\exp(\epsilon)+\qiattrs-1}=
       \frac{2\qiattrs}{\exp(\epsilon)+\qiattrs-1}(x_n-x_1).
    \end{equation*}
\end{theorem}

\begin{theorem}[$\alpha$-fairness for $\mathcal{M}_{\text{Lap}}$]
\label{prop:lap_fair_bound}
The Laplace mechanism $\mathcal{M}_{\text{Lap}}$ is $\alpha_{\text{Lap}}$-fair with $\alpha_{\text{Lap}}$ given by
    \begin{equation*}
        \frac{\exp\left(-\epsilon x_1/2\right)}{2}\norm{\bm{x}}_{\rightleftharpoons}=
       \frac{\exp\left(-\epsilon x_1/2\right)}{2}\left(x_n-x_1\right).
    \end{equation*}
\end{theorem}

Figure~\ref{fig:fairness} illustrates the fairness violations values,
represented by the value of $\alpha$, for cell suppression, swapping,
and $k$-anonymity, as well as their differentially private
counterparts, for various privacy parameters $\epsilon$ and values of
$k$ (for cell suppression and $k$-anonymity) or percentage of rows
swapped (for swapping). It can be observed that the fairness
violations of the differentially private mechanisms are comparable (or
better) to those of their traditional counterparts. This is
particularly noteworthy as the privacy parameter $\epsilon$
increases. As previously mentioned, it is important to remember that
the differentially private mechanisms are not ``noisy'' versions of
their traditional counterparts; rather they are conceptually similar
mechanisms. Consequently, they may exhibit lower fairness violations
compared to their traditional counterparts, as seen for DP $k$-anonymity.

The following theorem is the third key result of this paper. {\em It
proves the superiority of the Laplace mechanism over DP cell suppression and swapping in terms of fairness errors.} 

\begin{theorem}\label{thm:fair-comp}
    Suppose that the minimum count of the original histogram $\bm{x}(D)$
    is between $2$ and the threshold $k$, i.e., $2\leq x_1\leq k$. Then,
    the fairness error associated with the Laplace mechanism is not
    greater than that of the DP cell suppression or DP swapping mechanism, namely,
    \begin{equation*}
        \alpha_{\text{Lap}}\leq \alpha_{\text{CS}}\quad\text{and}\quad\alpha_{\text{Lap}}\leq \alpha_{\text{SW}}.
    \end{equation*}
\end{theorem}

It is worth noting that $k$-anonymity operates in a different space
from the original histogram space, thus a theoretical comparison
between the Laplace mechanism and DP $k$-anonymity is not feasible. However, the paper next presents empirical evidence that the Laplace mechanism has 
a significant advantage over DP $k$-anonymity as well.


\section{Experimental Evaluation}
\label{sec:experiments}

This study assesses the performance of the DP variants of 
traditional DA mechanisms and compares them with two key DP
mechanisms, the Laplace and the Discrete Gaussian Mechanisms, reviewed
in Section~\ref{sec:das}. The experiments use the ACS 2019 IPUMS
datasets for Massachusetts, Texas, and Outlier \citep{SDNist}. All the experiments report the average of 200 repetitions. Results for the latter two datasets are included in the appendix as their trends are similar 
to the former. The appendix also includes a more extensive description of the
dataset and experimental settings. This section focuses on evaluating
the mechanisms in two settings: data release and classification.

\begin{table}[t]
\small
\centering
\resizebox{0.95\linewidth}{!}
{
    \begin{tabular}{c|l|r|r|r}
    \toprule
    $\epsilon$ & Mechanism & \multicolumn{1}{c|}{$\delta$} & Bias ($\ell_1$ norm) & $\alpha$-fairness \\
    \midrule
    \multirow{5}[2]{*}{0.5} & Laplace & \textbf{0} & \textbf{763.775} & \textbf{3.655} \\
          & Discrete Gaussian & 0.363  & 980.81  & 4.945  \\
          & DP Suppression & 0.999  & 935.525  & 4.345  \\
          & DP Swapping & 0.868 & 10906.79  & 469.015  \\
          & DP $k$-anonymity & 0.878  & 2337.8  & 22.65  \\
    \midrule
    \multirow{5}[2]{*}{1} & Laplace & \textbf{0} & \textbf{342.885} & \textbf{1.845} \\
          & Discrete Gaussian & 0.132  & 659.215  & 3.065  \\
          & DP Suppression & 0.999  & 1003.035  & 4.5  \\
          & DP Swapping & 0.874 & 9859.26  & 425.335  \\
          & DP $k$-anonymity & 0.906  & 3297.4  & 32.1\\
    \midrule
    \multirow{5}[2]{*}{2} & Laplace & \textbf{0} & \textbf{154.78} & \textbf{0.905} \\
          & Discrete Gaussian & 0.017  & 436.925  & 2.2  \\
          & DP Suppression & 0.999  & 1018.335  & 4.72  \\
          & DP Swapping & 0.899 & 6841.19  & 282.73  \\
          & DP $k$-anonymity & 0.981  & 4175.5  & 37.65  \\
    \midrule
    \multirow{5}[2]{*}{4} & Laplace & \textbf{0} & \textbf{67.34} & \textbf{0.465} \\
          & Discrete Gaussian & 3E-4  & 290.715  & 1.495  \\
          & DP Suppression & 0.999  & 1014.63  & 4.92  \\
          & DP Swapping & 0.969 & 1664.63  & 101.645  \\
          & DP $k$-anonymity & 0.999  & 4590.7  & 40.75 \\
    \bottomrule
    \end{tabular}%
}
  \caption{MA dataset data release: Comparison of DP mechanisms in terms of $\delta$, $\ell_1$ norm of the empirical bias and $\alpha$-fairness.  \label{tab:compareDPmethods}}
\end{table}%

\paragraph{Data Release.}

The first task compares datasets reconstructed from histograms
generated by the various DP mechanisms studied. Readers are referred
to Appendix~\ref{app:sec:DA_alg} for details on the reconstruction
algorithms.  Table~\ref{tab:compareDPmethods} assesses the performance
of the DP variants of the traditional DA mechanisms and the Laplace
and the discrete Gaussian mechanisms in terms of errors and fairness
violations. In mechanisms that may produce negative counts, a
simple post-processing projection into the non-negative orthant is applied.

These results are particularly significant: contrary to commonly held
beliefs, they demonstrate that classical DP algorithms not only
provide strong privacy guarantees (see the $\delta$ values), but also
produce histograms that improve over traditional DA mechanisms in
terms of both accuracy (see the bias column) and fairness metrics (see
$\alpha$-fairness column). {\em As a consequence, when agencies desire
to release data sets, it is advisable they consider traditional DP
mechanisms.}


\begin{figure}[!t]
\centering
        \includegraphics[width=0.8\linewidth]{lr_accu.pdf}
    \caption{MA dataset: Results for Logistic Regression.}
    \label{fig:Log_errors}
\end{figure}
\paragraph{Classification.} 

It is also important to compare the performance of all the DP
mechanisms in a classification task. The setting employs the private
datasets obtained through a data-release query in order to train a
logistic regression classifier. The task is to predict whether an
individual earns more than \$50,000 per year, and the results in Figure~\ref{fig:Log_errors} are presented in terms of accuracy on the original,
non-private dataset. Observe how the Laplace and discrete Gaussian mechanisms
lead to classifiers with much higher accuracies than classifiers
trained over data produced by other traditional DA
mechanisms. Notably, the classification accuracy of Laplace and discrete 
Gaussian is much closer to that of the baseline method (trained on
non-private datasets) than any other method.  Again, this is
significant: {\em despite their simplicity, these tasks are the
basis for numerous statistical analyses performed routinely by data
agencies and organizations.}


\section{Conclusion}

This paper presented a framework for comparing traditional disclosure
avoidance systems (DA) to differential privacy. It proposed carefully 
randomized versions of three widely adopted traditional DA methods, i.e., 
suppression, swapping, and k-anonymity, and derived $(\epsilon,\delta)$-DP bounds 
for these mechanisms. The paper
also analyzed these DP algorithms empirically and showed
that they are close to their traditional counterparts both in terms of
accuracy and fairness. The DP DA mechanisms were then compared experimentally
with traditional DP mechanisms (i.e., the Laplace or the discrete Gaussian
mechanisms)  on data release and classification tasks. Contrary to popular belief, 
the experimental evaluation showed that classical DP mechanisms may be superior to traditional DA in terms of accuracy and fairness for the same privacy levels. This study has the
potential to impact the way in which data agencies and organizations
approach disclosure avoidance in the future as it provides a framework that enables 
a comparison of the strengths and limitations of traditional DA and differential privacy.

\newpage
\section*{Ethical Statement}
From an ethical standpoint, the study's purpose is not to condone the release of data by agencies that have not fully considered the privacy implications of their actions. The study should not be taken as a means to discredit traditional DA methods. Furthermore, the empirical analysis presented should be understood as specific to the mechanisms and datasets discussed in the study.

It is also important to consider the potential benefits of the study, such as improved accuracy and fairness in data release which may be gained with the adoption of traditional differentially private tools. Additionally, the study has the potential to advance the development of more effective privacy-preserving technologies.

\section*{Acknowledgments}

This research is partially supported by NSF grant 2133169, AI institute 2112533, 
and NSF CAREER Award 2143706. 
Fioretto is also supported by a Google Research Scholar Award and an Amazon Research Award. 
Its views and conclusions are those of the authors only. 
The authors would also like to thank Matt Williams for the helpful discussions 
on swapping and other traditional DA techniques.


\bibliographystyle{named}
