Post-processing of Differentially Private Data: A Fairness Perspective

1 Introduction

Differential privacy (DP) [Dwork et al., 2006] has become a fundamental technology for private data release. Private companies and federal agencies are rapidly developing their own implementations of DP. It is particularly significant to note that the U.S. Census Bureau adopted DP for its 2020 release [Abowd, 2018]. It is also of primary importance to observe that the released data by corporation or federal agencies are often used to make policy decisions with significant societal and economic impacts for the involved individuals. For example, U.S. census data users rely on the decennial census data to apportion the 435 congressional seats, allocate the $1.5 trillion budget, and distribute critical resources to U.S. states and jurisdictions.

Although DP provides strong privacy guarantees on the released data and is widely celebrated among privacy researchers, its wide adoption among more federal agencies and public policy makers presents a key challenge: without careful considerations, DP methods may disproportionately impact minorities in decision processes based on the private data. Specifically, to protect individuals in a dataset, typical DP data-release methods operate by adding calibrated noise onto the data and then post-process the resulting noisy data to restore some important data invariants. Since such a process perturbs the original data, it necessarily introduces some errors which propagate onto downstream decision tasks. In fact, this paper will show that these errors may affect various individuals differently. Although understanding the outcome of these effects is extremely important, these disproportionate impacts are poorly understood and have not received the attention they deserve given their broad impact on various population segments.

This paper addresses this gap in understanding the effect of DP, and analyzes the disproportionate effects of a family of post-processing methods commonly adopted in data release tasks. The analysis focuses on two critical settings: the release of differentially private datasets and the use of such private datasets in critical allocation tasks, as those using U.S. Census data to allocate funds and benefits. The paper makes two fundamental contributions:

1. In the release setting, the paper derives tight bounds on the unfairness introduced by commonly adopted postprocessing mechanisms, providing a valuable tool for policy makers and information officers to understand the disproportionate impact of their DP releases. These results are complemented by numerical simulations on the census data.
2. In the downstream decision setting, the paper proposes a novel post-processing mechanism that integrates the data invariant into the downstream decision processes. The resulting mechanism achieves near-optimal results and reduces unfairness and the cost of privacy up to an order of magnitude on practical case studies.

To the best of the authors' knowledge, this is the first study that analyzes the fairness impacts of DP post-processing steps. The rest of this paper presents the related work, the preliminaries, the settings considered, and the motivation. The core of the paper is in Sections 6 and 7 that present the two main contributions. The last section concludes the paper. All the proofs are in the Appendices that also contain a nomenclature summary.

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

g

/

q

E

X

z

+

7

L

J

D

O

c

G

A

p

r

P

8

>

B

H

V

N

S

w

M

3

W

Y

k

R

9

F

2

o

5

n

v

m

y

Z

U

Q

K

I

C

f

T

j

d

u

0

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

T

M

C

2

K

X

3

R

7

+

Q

k

5

y

m

I

>

A

B

9

c

V

D

L

S

g

F

j

Z

W

Y

J

d

N

E

v

0

w

G

O

U

o

/

p

H

z

n

8

P

q

r

f

u

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

r

P

B

n

y

A

w

/

H

I

M

8

>

C

O

3

c

V

7

T

F

E

9

U

S

o

k

q

0

g

Q

m

5

z

W

J

d

L

D

X

Z

R

f

p

+

K

Y

G

N

v

j

2

u

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Z

8

G

9

o

Q

7

N

g

R

+

q

j

d

V

w

p

J

>

A

C

U

H

c

B

P

T

M

m

2

/

0

D

k

E

W

z

S

n

O

5

K

3

u

I

y

L

f

v

X

r

Y

F

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

n

J

B

M

G

z

q

p

3

H

8

r

Q

j

N

c

>

A

C

X

V

F

d

9

w

u

y

Z

Y

E

P

R

+

S

K

O

0

f

m

I

T

k

U

/

D

2

5

7

g

L

W

o

v

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

p

E

o

G

f

w

J

W

Z

K

z

L

8

v

n

N

Y

>

A

C

O

3

c

V

D

S

g

M

F

r

P

0

B

m

T

/

Q

U

k

7

I

5

d

X

u

9

2

y

R

H

+

q

j

2 RelatedWork

Privacy and fairness have been studied mostly in isolation with a few exceptions. [Cummings et al., 2019] considered the tradeoffs arising between differential privacy and equal opportunity. [Ekstrand et al., 2018] raised questions about the tradeoffs involved between privacy and fairness, and [Jagielski et al., 2018] showed two algorithms that satisfy pϵ, δq-differential privacy and equalized odds. In the context of data release and resource allocation, [Pujol et al., 2020] were seemingly first to show, empirically, that there might be privacy-fairness tradeoffs involved in resource allocation settings. In particular, for census data, they show that the noise added to achieve differential privacy could disproportionately affect some groups over others. [Tran et al., 2021] formalized the ideas developed in [Pujol et al., 2020] and characterized the conditions for which fairness violations can be bounded for a class of allocation problems. Finally, [Abowd and Schmutte, 2019] considered statistical accuracy and privacy protection as competing public goods, and designed an economic framework to balance the tradeoff. This paper departs from these results significantly: it provides tight lower and upper bounds on the unfairness introduced by post-processing steps that are critical for practical applications, and proposes new mechanisms that merge postprocessing and the downstream resource allocation for mitigating these fairness issues.

3 Preliminaries: Differential Privacy

Differential Privacy [Dwork et al., 2006] (DP) characterizes the amount of individual data disclosed in a computation.

Definition 1. A randomized algorithm M : X Ñ R with domain X and range R satisfies pϵ, δq-differential privacy if for any output O Ď R and datasets x, x1 P X differing by at most one entry (written as x " x1 )

Parameter ϵą0 is the privacy loss: values close to 0 denote strong privacy and δ ě 0 represents a probability of failure. Intuitively, DP states that every event has a similar probability regardless of the participation of any individual data to the dataset. DP satisfies several properties including immunity to post-processing, which states that the privacy loss of DP outputs is not affected by arbitrary data-independent postprocessing [Dwork and Roth, 2013].

A function f from a dataset x P X to a result set R Ď Rn can be made differentially private by injecting random noise onto its output. The amount of noise relies on the notion of global sensitivity ∆f " maxx"x1 }fpxq ´ fpx1 q}p with p P

t1, 2u. The Laplace mechanism [Dwork et al., 2006] that outputs fpxq`η, where η P Rn is drawn from the i.i.d. Laplace distribution with 0 mean and scale ∆f {ϵ over n dimensions, achieves ϵ-DP. The Gaussian mechanism [Dwork and Roth, 2013] that outputs fpDq ` η, where η P Rn is drawn from the multivariate normal distribution Np0, σ2Inq with parameter σ ě c∆f {ϵ, achieves pϵ, δq-differential privacy, for c2 ą 2 lnp1.25{δq.

4 Settings and Goals

The paper considers datasets x P R of n entities, whose elements xi describe some measurable quantities of entity i P rns, such as the number of individuals living in a geographical region i. A data-release mechanismM is applied to the dataset x (called true data in this paper) to produce a privacy-preserving counterpart ˜x " Mpxq (referred to as noisy data). Given the released data, the paper considers allocation problems P : Rn Ñ Rn that distribute a finite set of resources to the problem entities. For example, P may be used to allocate funds to school districts.

The focus of the paper is to study the error disparities of a DP data-release mechanismM in two contexts: (1) data release and (2) downstream decisions. The first context refers to the case in which the noisy data must be post-processed before being released to satisfy desired invariants. The second context refers to the case in which the noisy data is released for use in an allocation problem. Again, the release data must be post-processed to satisfy the problem-specific feasibility constraints. The paper studies the disparate impacts of the error introduced by post-processing among entities in both scenarios.

Quantitatively, this error is represented by the bias associated with a post-processing mechanism π, i.e.,

The paper will often omit the last two arguments of the bias term when there is no ambiguity. The disparate impact of the error is then characterized by the following definition.

Definition 2 (α-fairness). A post-processing mechanism π is said α-fair with respect to problem P if the maximum difference among the biases is bounded by α, i.e.,

with α referred to as a fairness bound that captures the fairness violation.

5 Motivating Applications

This section reviews two settings highlighting the disparate impacts of DP post-processing in census releases.

Data Release. Consider a simplified version of the census data release problem. The task is to release counts, such as demographic information of individuals, which are required to be non-negative and summed up to a public quantity. The latter is usually used to preserve known statistics at a state or national level. To preserve these invariants, commonly adopted post-processing mechanisms (e.g., the one

-4

Misallocation Funds (×105 $)

used by the Top-Down algorithm in the release of several 2020 U.S. census data products) constrain the noisy DP outcomes with an ℓ2 projection step. Such post-processing step will be described in detail and studied in the next section. Figure 2 (left) shows the (sorted) values of some synthetically generated true counts (bars) and the (empirical) biases (red dots), obtained by comparing the post-processed DP counts with the true counterparts. Notice how the resulting biases vary among entities. This is significant as sub-communities may be substantially under- or over-counted affecting some important data analysis tasks.

Downstream Decisions. These disparities may also have negative socio-economic impacts. For instance, when agencies allocate funds and benefits according to differentially private data, an ill-chosen post-processing mechanism can result in huge disparities and, as a consequence, lead to significant inefficiencies of allocation. Consider the Title I of the Elementary and Secondary Education Act of 1965 [Sonnenberg, 2016]: It uses the US Census data to distribute about $6.5 billion in basic grants to qualified school districts in proportion to the count xi of children aged 5 to 17 who live in necessitous families in district i. The allocation is formalized by

where x " rx1 . . . xnsJ is the vector of the districts' true counts and ai is a positive weight factor reflecting students expenditures in district i. When a projection mechanism (described in more details in Section 7) is used to guarantee nonnegativity of the private data ˜x, the resulting errors on the proposal of funds allocation can be consequential. Figure 2 (right) visualizes the misallocation (blue dots) for over 16,000 school districts (due to this post-processing mechanism) in terms of proportions (left y-axis) and funds (right y-axis). In this numerical simulation, which uses data based on the 2010 US census release, large school districts may be strongly penalized. For example the largest school district in Los Angeles can receive up to 99,000 dollars fewer than warranted.

The next sections analyze these effects and propose mitigating solutions. Due to space limitations, complete proofs are deferred to the Appendix.

6 Unfairness in Data Release

This section studies the effects of post-processing in a common data-release setting, where the goal is to release population counts that must also sum up to a public constant C. The section first introduces the projection mechanisms used to restore non-negativity and other aggregate data invariants and then studies its fairness effects.

Projections are common post-processing methods central to many data-release applications, including energy [Fioretto et al., 2019], transportation [Fioretto et al., 2018], and census data [Abowd et al., 2019]. They are defined as:

with feasible region defined as

Notice that PS` is a convex program, and its unique optimal solution πS`p˜xq guarantees the desired data invariants by definition. For the analysis, it is also useful to consider a modified version PS of PS`, which differs from the latter only in that it ignores the non-negativity constraint v ě 0. Its feasible region and optimal solution are denoted, respectively, KS and πSp˜xq.

This section provides tight upper and lower bounds of the unfairness arising from projection operators. Lemma 3 and 4 are critical components to derive the α-fairness bounds developed in Theorem 1. The tightness of the proposed bounds is demonstrated in Example 1 and the existence of inherent unfairness in Example 2. Proposition 2 then presents an efficient method to evaluate the α-fairness bounds under the Gaussian mechanism, giving a uniquely valuable tool to decision makers to evaluate the impact of post-processing the data in their applications. To ease notation, the section omits the second argument P of the bias term B (as the P is an identity function for data-release settings). Additionally, unless otherwise specified, it assumes that the noisy data ˜x is an output of the Laplace mechanism with parameter λ or the Gaussian mechanism with parameter σ.

Lemma 1. [Zhu et al., 2021] For any noisy data ˜x P Rn , the closed-form solution πSp˜xq to program (PS) is,

for any i P rns, with injected noise η " ˜x ´ x.

Unlike πSp˜xq, the post-processed count πS`p˜xq does not have a close-form expression. However, the following lemma introduces an implicit expression of πS`p˜xq on the basis of πSp˜xq, establishing the foundation for the fairness analysis of the post-processing mechanism πS`.

Lemma 2. For any noisy data ˜x P Rn , the solution πS`p˜xq to program (PS`) can be expressed as

where p¨qě0 "maxt¨, 0u, and TpπSp˜xqq is the non-negative scalar that is the unique solution to the following equation

Figure 3 provides an illustrative example relating the two post-processing mechanisms and the role of TpπSp˜xqq. Given the noisy data ˜x (top of the figure) πS first projects it onto the solid line, which is the feasible region KS. Then, T needs to be deducted from both entries of πSp˜xq such that the positive part of πSp˜xq ´ T ¨ 1 equals πS`p˜xq.

The following lemma provides lower and upper bounds for the bias difference of post-processing πS` and plays a critical role in establishing the main results.

Lemma 3. For any pair pi, jq such that xi ď xj, the following relations hold,

with T defined as in Lemma 2 and B `pπS qě0 ˘ used as shorthand for E˜x "pπS p ˜xqqě0 ‰ ´ x.

While important, the upper bound (2b) is dependent on function T, which does not have a close-form expression; this makes it difficult to evaluate it. The following proposition provides an upper bound of T using πSp˜xq.

Proposition 1. For any noisy data ˜x P Rn , TpπSp˜xqq is upper bounded by the sum of negative parts in πSp˜xq:

where p¨q´ "´mint¨, 0u takes the negative part of the input.

The following lemma presents an upper bound of the difference between biases: unlike the bound developed in Lemma 3, this new bound is independent of the injected noise.

Lemma 4. For any pair pi, jq such that xi ď xj, the following relation holds.

The next theorem is the main result of this section: it bounds the unfairness resulting from the projection mechanism πS`. Without loss of generality, the true data x is assumed to be sorted in an increasing order, i.e., xi ď xj, for any i ă j.

Theorem 1. The fairness bound α associated with the postprocessed mechanism πS` is bounded from the below by

and bounded from the above by

Proof Sketch. By Equation (2a) in Lemma 3, notice that B pπS`q1 is the largest entry while B pπS`qn is the smallest one among all the biases. The lower bound of the fairness bound α can then be derived in the following way.

Likewise, Lemma 3 and 4, along with Proposition 1, make the joint effort to generate the upper bound.

The tightness of the derived bounds follows from the following instance.

Example 1 (Centroid). The lower and upper bounds proposed in Theorem 1 hold with equality when the true data x is exactly the centroid of the feasible region KS` of program (PS`), i.e., x " rC{n . . . C{ns P Rn , and the noisy data ˜x is an output of either Laplace or Gaussian mechanism. In this case, the fairness bound α and its bounds in Theorem 1 happen to be 0, which also means that there is no fairness violation.

The next example shows that post-processing definitely introduces unfairness when the true is not at the centroid.

Example 2 (Non-centroid). Suppose that the true data x is not the centroid of the feasible region KS`, i.e., xn ą x1. The fairness bound α associated with the post-processing mechanism πS` is strictly positive, i.e.,

This negative result motivates the development of novel postprocessing mechanisms in downstream decision processes, which are topics of the next section. The last result of this section provides an efficient evaluation of the proposed bounds via numerical integration methods.

Table 1: Case study of Hawaii.

MechanismM	α-fairness	Lower	Upper
Laplace	0.0245	0.0242	0.0288
Gaussian	0.0910	0.0897	0.1085

Proposition 2. Let ˜x be the output of the Gaussian mechanism with parameter σ. The key component of both lower and upper bounds in Theorem 1 can be written as

where a " 1σ b n n´1 , and Φp¨q is the standard Gaussian cumulative distribution function.

It is interesting to demonstrate the tightness of these bounds using the US Census households counts at the county level for the state of Hawaii.

Example 3 (Hawaii). The state of Hawaii has a total number of C " 453, 558 households distributed in n " 5 counties. The experiments use the Laplace mechanism with parameter λ " 10 and the Gaussian mechanism with parameter σ " 25. The empirical studies of α-fairness and its bounds in Theorem 1 associated with the post-processing mechanism πS` over 1, 000, 000 independent runs are reported in Table 1. The bounds of Gaussian mechanism use Proposition 2; those of Laplace mechanism are generated by the empirical means.

The derived lower and upper bounds are really tight and provide decision makers a uniquely valuable tool to assess the unfairness introduced by post-processing.

7 Mechanisms for DownstreamDecisions

Having shown that unfairness is unavoidable in common data-release settings, this section aims at designing postprocessing mechanisms for decision processes that minimize their fairness impact on the resulting decisions. The mechanisms studied are tailored for the allocation problem P F described in Section 5, which captures a wide class of resource allocation problems.

A natural baseline, currently adopted in census data-release tasks, is to first post-process the noisy data to meet the feasibility requirement (i.e., non-negativity) and then apply the allocation formula P F to the post-processed counts. To restore feasibility, it suffices to take the positive part of ˜x to obtain p˜xqě0 , or equivalently, project ˜x onto the non-negative orthant Rn`.

Definition 3 (Baseline Mechanism (BL)). The baseline mechanism outputs, for each i P rns,

It is possible to derive results similar to Example 2 for p¨qě0 when the baseline mechanism is used to produce feasible released data. Additionally, as shown in [Tran et al., 2021], the disparate errors resulting from p¨qě0 can be further exacerbated when they are used as inputs to downstream decision problems. It suggests that the baseline mechanismmight not be a good candidate for mitigating unfairness in this allocation problem. To address this limitation, consider the optimal post-processing mechanism in this context, i.e.,

where Π∆n " tπ | π : Rn ÞÑ ∆nu represents a class of postprocessing mechanisms whose images belong to the probability simplex ∆n. The optimization problem in Equation (4) is intractable in its direct form, since P F pxq is not available to the mechanism, motivating the need to approximate the objective function. Consider the following proxy E˜x "∥∥πp˜xq ´P F p˜xq∥∥é‰, which first exchanges the order of expectation and ∥¨∥é and then replaces the true allocation P F pxq with its noisy variant P F p˜xq. Then, the optimal post-processing mechanism π˚ α associated with this new proxy function becomes:

A mechanism, which is closely related to program (Pα), is presented as follows.

Definition 4 (Projection onto Simplex Mechanism (PoS)). The projection onto simplex mechanism outputs the allocation as follows.

Program (PPoS) projects P F p˜xq, which is not necessarily an allocation since it may violate non-negativity constraints, onto the closest feasible allocation. The next theorem establishes the equivalence between program (Pα) and program (PPoS): It leads to a near-optimal post-processing mechanism. (The missing proofs of the rest of this paper can be found in the Appendix).

Theorem 2. For any noisy data ˜x, the mechanism πPoS p˜xq generates the unique optimal solution to program (Pα).

Figure 4 visualizes the resulting biases of the Title I allocation associated with these two mechanisms, πPoS and πBL. It is noteworthy that these two mechanisms achieve roughly same performance for the school districts that are allocated small amounts. However, under the baseline mechanism, the school districts that account for a significant portion of total budget receive much less funding than what they are supposed to receive when no differential privacy is applied. This is not the case for mechanism πPoS, which reduces unfairness significantly. Recall that the notion of α-fairness measures the maximum difference among biases associated with different entities. Pictorially, the biases associated with πPoS do not vary as drastically as the baseline mechanism. Table 2 quantifies the benefits of πPoS over πBL.

8 Generalizations

The results in Section 7 can be generalized to other fairness metrics. This section discusses an important metric that quantifies the extra budget needed to ensure that all of the problem entities receive the resources (e.g., amounts of funds) they are warranted by law.

Table 2: Comparison between the two post-processing mechanisms in terms of two fairness metrics for different privacy budgets. This work takes Laplace mechanism and 200, 000 independent runs for numerical evaluation.

Privacy Budgets	ϵ " 0.1		ϵ " 0.01		ϵ " 0.001
Mechanisms	πBL	πPoS	πBL	πPoS	πBL	πPoS
α-fairness	3.00E-07	1.50E-07	1.70E-05	1.75E-06	8.06E-04	2.23E-05
Cost of Privacy	1.62E-05	1.41E-05	1.33E-03	1.04E-03	5.90E-02	3.49E-02

Definition 5 (Cost of privacy [Tran et al., 2021]). Given the mechanism π, the total budget B to distribute and the true data x, the cost of privacy is defined as

ÿ

The next proposition establishes the equivalence between the cost of privacy and the ℓ1 norm of the bias when the image of the mechanism π is restricted to be the probability simplex.

Proposition 3 (Cost of privacy as a ℓ1-norm). Suppose that π is a post-processing mechanism, which belongs to the class Π∆n . The cost of privacy is a multiplier of the ℓ1-norm of its bias, i.e.,

Since the optimal post-processing is again intractable in its direct form, i.e., it cannot be solved as an optimization problem, its objective can be replaced by the proxy B{2 ¨ E˜x "∥∥πp˜xq ´ P F p˜xq∥∥1 ‰. Then, the optimal post-processing mechanism π˚CoP associated with this proxy function is given

The next theorem depicts the connection between PCoP and the two post-processing mechanisms proposed in Section 7.

Theorem 3. For any noisy data ˜x, the mechanism πPoS p˜xq generates an optimal solution to program (PCoP). For any noisy data ˜x such that řnj"1 aj ¨ ˜xj ą 0, mechanism πBL p˜xq generates an optimal solution to program (PCoP) as well.

This theorem demonstrates that mechanism πPoS always produces an optimal solution to program (PCoP) while the baseline mechanism achieves optimality with high probability. Table 2 shows that πPoS may significantly outperform the baseline mechanism, providing substantial reductions in the cost of privacy.

9 Discussion and Conclusion

This paper was motivated by the recognition that the disparate error impacts of post-processing of differentially private outputs are poorly understood. Motivated by Census applications, it took a first step toward understanding how and why post-processing may produce disparate errors in data release and downstream allocation tasks. The paper showed that a popular class of post-processing mechanisms commonly adopted to restore invariants during the release of population statistics are inherently unfair. It proposed a tight bound on the unfairness and discussed an efficient method to evaluate the disparate impacts. Motivated by these negative results, the paper studied how post-processed data affects downstream decisions under a fairness lens and how to contrast such effects. In this context, the paper proposed to release the noisy, non-post-processed data, and post-processing the output of the downstream decisions instead. It focused on an important class of resource allocation problems used to allot funds or benefits and proposed a novel (approximately) optimal post-processing mechanism that is effective in mitigating unfairness under different fairness metrics. The analysis was complemented with numerical simulation on funds allocation based on private Census data showing up to an order magnitude improvements on different accuracy disparity metrics.

These results may have strong implications with respect to fairness in downstream decisions and should inform statistical agencies about the advantage of releasing private nonpost-processed data, in favor of designing post-processing methods directly applicable in the downstream decision tasks of interest.

Acknowledgements

This research is partially supported by the National Science Foundation (NSF 2133169 and NSF 2133284) and by a Google Research Scholar Program award. The opinions expressed are solely those of the authors.