Fairness for Image Generation with Uncertain Sensitive Attributes

Introduction

Fairness, accountability, and transparency have taken a front-row seat in the machine learning community. Numerous recent controversies have erupted over how current machine learning systems already in use can be racist (Simonite, 2018), sexist (Kay et al., 2015), homophobic (Morse, 2017), or all of the above (Moore, 2016). In a recent controversy, a low-resolution image of Barack Obama was put into PULSE, a super-resolution generative model (Menon et al., 2020b), but the resulting image was of a distinctly White man. While we generally have to be careful when identifying the race of a person that does not exist, such as the one represented by the generated image, multiple other reconstructions by PULSE strongly suggest that this algorithm contributes to the systemic bias against people of color.

Accuracy of representation as a fairness notion is a significant leap from the more traditional classification setting, in which we require some form of independence (or conditional independence) between the sensitive attributes and the algorithm prediction. In the context of image reconstruction, the output itself can be considered as having sensitive attributes, and we want the sensitive attributes of the input to match the sensitive attributes of the output – which is fundamentally different from an independence condition. This leads us to introduce and discuss new fairness definitions, specific to the field of image generation, reconstruction, denoising and super-resolution.

In light of the “White Obama” controversy (Menon et al., 2020b), it has been suggested that reconstruction algorithms are biased because the datasets are not representative of the true population distribution. While it is true that the datasets are biased (Buolamwini & Gebru, 2018; Khosla et al., 2012), current algorithms also play their part in widening this gap (Wang et al., 2019; Terhörst et al., 2020), such that majority classes get overrepresented, and minorities get further underrepresented. Indeed, when applying PULSE (Menon et al., 2020b) to an unbalanced dataset with 80% dogs (majority class) and 20% cats, we observe that 80% of cats are mistakenly reconstructed as dogs, while only 2% of dogs are reconstructed as cats (see Figure 4(a)). When cats are the 80% majority, the situation reverses to 1% and 98% mistakes, respectively (see Figure 5(a)).

There is a simple intuitive reason why reconstruction algorithms designed to maximize accuracy will increase bias. Assume we observe a noisy version $y$ of an image $x^{*}$ that is either a dog or a cat. Assume cats are the minority, with the prior $\Pr(x^{*}\in\text{Dog})=0.8$. Further, assume that the measurements are always noisy and cannot definitively identify the species, so cat-like measurements are such that $p(y\mid x^{*}\in\text{Cat})/p(y\mid x^{*}\in\text{Dog})\leq 2$. Using Bayes, the posterior is

Therefore, regardless of the measurement, an algorithm that maximizes accuracy will always produce images of dogs.

This issue relates to a rich area of work on fairness in machine learning, including for classification or generation without measurements (see Section 1.1 for an overview). However, to the best of our knowledge, previous approaches always assume that the sensitive attributes are well-defined and unambiguous. While this assumption might hold for cats and dogs, as (Benthall & Haynes, 2019; Hanna et al., 2020) emphasize, race cannot be treated in the same way. First, it is unclear when to include subgroups within the larger group or when to treat them separately (for instance, when to consider South Asians as their own subgroup, or as Asians). This has major implications, as choosing which groups exist and what sensitive attributes are valid can already widen existing discrimination, as the long line of research on intersectionality shows. Second, even if we could decide on which groups are relevant, races are multidimensional and cannot be reduced to a simple categorical value: studies show that we can arrive at inconsistent conclusions about the same data depending on how race is measured (e.g. self-reported or observed) (Howell & Emerson, 2017). Our work therefore focuses on moving away from classifying people into partitions.

Suppose that we have a distribution of users $x^{*}$; each user $x^{*}$ is observed through some lossy observation process to produce $y$ (e.g., a low-resolution image); and our reconstruction algorithm produces $\widehat{x}$ from $y$. We are concerned about fairness with respect to a collection of protected groups $C=\{c_{1},\dotsc,c_{k}\}$. Our setting therefore includes, but is not limited to, the special case in which $C$ is a partitionFor simplicity of notation, each group $c_{i}$ contains both people $x^{*}$ and images $\widehat{x}$..

The fairness concern we consider is that of representation: when users in each protected group use the algorithm, does the result adequately represent them and their group? When the observation process $y$ is significantly lossy, there inevitably will be “representation errors” where a member of one group is reconstructed as being in a different group. How should we determine if the errors are equitable?

Our Contributions: Fairness Definitions.

We introduce definitions for some natural notions of fairness in reconstruction. One is that the average representation rate should be independent of the group:

is the same value for all $i\in[k]$. We call this Representation Demographic Parity (RDP), by analogy to the binary classification setting, where Demographic Parity means that $\Pr(L=1\mid x^{*}\in c_{i})$ is fixed. The difference here is that the “good” outcome $(\widehat{x}\in c_{i})$ is different for each group, while typically in classification the “good” outcome (where, e.g., $L=1$ means “offer a loan”) is the same across groups. RDP is simply requesting that the reconstructions have the same error rates across groups.

An alternative definition is that the demographics of the output should match those of the input:

We call this Proportional Representation (PR). It simply says that the reconstruction process should not introduce bias in the distribution for or against any group.

Unfortunately, these two definitions are often incompatible. We show in Proposition 2.8 that, whenever a majority group exists and the measurements can confuse it with other groups, no algorithm can achieve both RDP and PR.

One weakness of both PR and RDP is that they only consider the global behavior of the reconstruction. But individual users want to be represented well when they use the system, and may not be mollified by the knowledge that many other members of their group are being represented. On the other hand, some images are genuinely harder to reconstruct accurately, so expecting equal representation accuracy/RDP for every user would strongly limit overall accuracy. Our solution is to extend PR by incorporating the measurement process:

We call this Conditional Proportional Representation (CPR). The idea is that the population of users with each given $y$ should have fair treatment (in the sense of PR). Of course, CPR implies PR by averaging over $y$.

Note that CPR implies that the reconstruction process must be randomized, not deterministic. This has other benefits: if the user is not satisfied with the result, they can rerun the algorithm until they get a result that represents them. Users can also get a collection of $\widehat{x}_{i}$ to observe the diversity of possible reconstructions.

Our Contributions: Algorithms.

We show that CPR (and hence PR) are achievable with a simple-to-describe algorithm: posterior sampling, where we output $\widehat{x}\sim p(x^{*}\mid y)$. This can be approximated well in practice using Langevin dynamics for state-of-the-art generative models representing $p(x^{*})$, as we discuss in Section 4.1.

Posterior Sampling also satisfies one more fairness condition: the confusion matrix is symmetric, meaning that (for example) an equal number of Black users will be reconstructed as White as White users will be reconstructed as Black. We call this condition Symmetric Pairwise Error (SPE).

for all $i,j\in[k]$. CPR implies SPE, and SPE implies PR (see Figure 2).

Since SPE implies PR, in general SPE is incompatible with RDP (per Proposition 2.8). But in the special case of two groups $c_{1},c_{2}$ of equal size, then SPE actually implies RDP. This gives an algorithm to achieve RDP for the two-group setting: we reweight our input distribution such that each group has equal probability, then perform Posterior Sampling with respect to the reweighted distribution. With more than two groups, there still exists a reweighting of the groups such that Posterior Sampling on the reweighted distribution satisfies RDP (see Theorem 3.5). This reweighted-resampling algorithm can be performed in practice by learning a GAN for the reweighted distribution and using Langevin dynamics on the reweighted GAN.

Our Contributions: Obliviousness.

Posterior Sampling satisfies the CPR, PR, and SPE fairness criteria while retaining an invaluable property: the algorithm doesn’t depend on the set of protected groups $C$. It satisfies the fairness properties for every set of protected groups, which is an algorithmically achievable way of addressing the issues raised in (Hanna et al., 2020) about race being ambiguous and ill-defined. We say such an algorithm is obliviously fair. By contrast, our reweighted-resampling algorithm achieving RDP needs to know the protected groups, and would not satisfy RDP for a different collection of groups. Which fairness properties can be achieved obliviously, and under what circumstances?

Our main results here are twofold: first, Posterior Sampling is the only algorithm that satisfies CPR obliviously. Second, RDP cannot be satisfied obliviously. This impossibility applies even to obliviousness with respect to one of two plausible, socially meaningful partitions. Theorem 2.4 shows, for example, that you cannot satisfy RDP with respect to both {White, Asian} and {White, South Asian, East Asian} if your observations are lossy. This means that every algorithm can reasonably be viewed as unfair with respect to RDP.

Our Contributions: Experiments.

We implement Posterior Sampling via Langevin dynamics, study its empirical performance and compare it to PULSE with respect to our defined metrics. We do this on the MNIST (LeCun, 1998), FlickrFaces-HQ (Karras et al., 2019) and AFHQ cat & dog (Choi et al., 2020b) datasets. We evaluate obliviousness and SPE of Posterior Sampling on the first two datasets. Using the AFHQ cat & dog dataset, we demonstrate empirically that Posterior Sampling satisfies SPE and PR over various imbalances between cats and dogs.

1 Related Work

Numerous works have attempted to tackle the issue of bias in the machine learning of images, either for data generation/reconstruction tasks or for downstream tasks such as face recognition and image quality assessment. One popular approach for dealing with bias consists of adversarially generating data or embeddings with a discriminator for different values of the sensitive attributes, yielding similar distributions for different values of the sensitive attribute (Madras et al., 2018; Xu et al., 2018, 2019; Gong et al., 2020a; Khajehnejad et al., ; Sattigeri et al., 2018; Yu et al., 2020). Another approach focuses on learning explicitly the bias of the dataset, so as to remove it (Khosla et al., 2012; Grover et al., 2019; Choi et al., 2020a). The special case of fair dimensionality reduction through principal component analysis is solved by (Samadi et al., 2018). Another research direction formulates the fairness constraints as an additional term in the loss (Serna et al., 2020). Another approach focuses on minorities and learns their specific features (Amini et al., 2019; Gong et al., 2020b). A related line of work improves the fairness of generative models without retraining (Tan et al., 2020), however we do not know how to use these for inverse problems.

Another relevant line of research studies fairness in the presence of uncertainty, either in the labels (Kleinberg & Raghavan, 2018; Blum & Stangl, 2019; Wang et al., 2020a; Rolf et al., 2020) or in the sensitive attributes (Awasthi et al., 2020; Lamy et al., 2019; Celis et al., 2020; Wang et al., 2020b). In particular, one work studies overlapping groups (Yang et al., 2020).

Super resolution using deep learning has had remarkable success at producing accurate images. In (Ledig et al., 2017), the authors provide an algorithm which performs photo-realistic super resolution using GANs. However, this model requires retraining of the GAN when the measurement operator changes. Subsequent work has overcome this hurdle. Some models independent of the forward operator include CSGM (Bora et al., 2017), OneNet (Chang et al., 2017), PULSE (Menon et al., 2020a), Deep Image Prior (Ulyanov et al., 2018) and Deep Decoder (Heckel et al., 2019). Another line of work has shown that Posterior Sampling using approximate deep generative priors is instance-optimal for compressed sensing (Jalal et al., 2021).

Fairness definitions for image generation

While multiple group fairness definitions (demographic parity, equalized odds or opportunity, calibration etc.(Barocas et al., 2017; Hardt et al., 2016)) have been studied and widely accepted in the context of classification, their extension to the setting of image generation is not immediate. Here, we extend demographic parity.

If $k=2$, $c_{1}$ being all women, $c_{2}$ being all non-women, Representation Demographic Parity with respect to these two groups implies that women are as likely to be reconstructed as women as non-women are to be reconstructed as non-women.

2 Limitations of traditional group fairness definitions

Inspired by (Hanna et al., 2020), we note several reasons for having fairness definitions that are more flexible with respect to the groups in the collection or partition.

Minorities are ill-defined: What constitutes a minority? Are South Asians their own subgroup, or are they assigned as Asians? The list of accepted minorities is not only inconsistent across location and purpose, but multiple levels of granularity could be equally valid. Similar concerns can be raised from the point of view of intersectionality: we might both be interested in the discrimination faced by all women, and all people of color, without wanting to erase the singular discrimination faced by women of color (Buolamwini & Gebru, 2018).

Races are multi-dimensional: As (Roth, 2016) argues, races are multi-dimensional, and these dimensions are all relevant, albeit in different settings. For instance, voting patterns are more accurately predicted based on self-identified race, while observed race is more informative when dealing with discrimination. These differences are not minor: as (Howell & Emerson, 2017) shows, measuring races in five different ways led to widely different interpretations of the same data.

Partitions reify the status quo: According to (Hanna et al., 2020), widespread adoption of race categories participates in erasing their historical and social context (Duster, 2005; Smart et al., 2008), as well as perpetuating the current system and creating new harm (Kaufman, 1999; Sewell, 2016).

Who chooses the partition: (Barabas et al., 2020) raises concerns on who has the power to choose the partitions and what their intentions were. Historically, such partitions have done significant harm to the minorities they were supposed to protect (Mills, 2014; Hanna et al., 2020).

In response to these critiques, we study a novel property of fairness definitions.

We say an algorithm satisfies a group fairness definition obliviously if the algorithm satisfies the fairness definition for any collection of sets and does not require knowledge of the collection of sets to perform reconstruction.

Satisfying a fairness definition obliviously is one way of addressing the issues above, as it is now satisfied for all groups at the same time. This requirement may nevertheless be too strong, since most such groupings are not socially meaningful. This leads to more restricted versions of obliviousness, ones that only hold for specific sets of collections. Unfortunately, RDP cannot be satisfied even with only two socially meaningful partitions.

Let $A$ and $B$ be disjoint groups (e.g., Asian and White people), and let $A_{1},A_{2}\subset A$ be disjoint groups that cannot be perfectly distinguished from measurements only (e.g., South Asians and East Asians). Then Representation Demographic Parity cannot be satisfied $\{\{A,B\},\,\{A_{1},A_{2},B\}\}$-obliviously.

In the example stated in Theorem 2.4, it is impossible to be fair as defined by Representation Demographic Parity with respect to White people, South Asians, East Asians, and Asians as a whole. This holds even if we know exactly what the measurement process is, the demographics, and what the relevant groups are.

The only way for an algorithm to satisfy Representation Demographic Parity obliviously is to achieve perfect reconstruction.

3 Conditional Proportional Representation

An alternative fairness measure is that the distribution of the output of the algorithm should match the demographics of the input to the algorithm:

In the setting of Definition 2.1, an algorithm satisfies Proportional Representation (PR) if:

One could also demand a much stricter fairness property, where the algorithm should satisfy PR among the population that maps to the same observation, for every possible observation:

In the setting of Definition 2.1, an algorithm satisfies Conditional Proportional Representation (CPR) if, almost surely over $y$:

Intuitively, many images could yield the same lossy measurement. Because we have no way of knowing exactly from which image the measurement came, we reconstruct one at random based on how likely images in the same group are to have yielded this measurement in the first place. As such, it is “fair”: every image that could have led to the measurement gets a chance at being represented, not just the most likely. This also implies that the reconstruction cannot be deterministic. Unfortunately, while CPR can be achieved via Posterior Sampling (Theorem 3.1), the fact that the definition involves the posterior distribution makes it difficult to verify without full knowledge of the measurement process and the probability distribution.

It turns out that one cannot achieve RDP and PR simultaneously if you have a majority which has mass larger than $1/2$.

Whenever there exists a majority class that the measurements cannot 100% distinguish from the non-majority classes, PR and RDP are not simultaneously achievable.

Posterior Sampling

The Posterior Sampling algorithm outputs a reconstruction $\widehat{x}$ drawn from the posterior $P(\cdot\mid y)$. It is known to be instance-optimal for compressed sensing (Jalal et al., 2021) and to give fairly accurate results in practice when implemented via annealed Langevin dynamics (Song & Ermon, 2019b). In this section, we show that it also has good fairness properties.

It is easy to see that if one has access to the distribution $P$ over images and the likelihood function associated with the measurement process, then Posterior Sampling will satisfy the CPR. The following Theorem shows that this is the only algorithm that can satisfy CPR.

Posterior Sampling is the only algorithm that achieves oblivious Conditional Proportional Representation.

In the setting of Definition 2.1, an algorithm satisfies Symmetric Pairwise Error (SPE) if

Using the fact that the ground truth and reconstruction are conditionally independent given the measurements, we can show that any algorithm that satisfies CPR will also satisfy SPE.

In the setting of Definition 2.1, Conditional Proportional Representation implies Symmetric Pairwise Error.

Theorem 3.1 and Theorem 3.3 give the following Corollary.

Finally, for any partition $C$, there exists a reweighting of the underlying distribution such that Posterior Sampling achieves RDP with respect to the partition $C$.

Let $C=\{c_{1},\dots,c_{k}\}$ be a partition. There exists a choice of weights $\lambda_{i}>0$ with $\sum\lambda_{i}=1$ such that Posterior Sampling with respect to the reweighted distribution

In the special case of 2 classes, the reweighting is very simple: $\lambda_{1}=\lambda_{2}=\frac{1}{2}$.

For the special case when the collection $C$ is a partition, we can show that Posterior Sampling obliviously minimizes a loss we call Representation Cross-Entropy (RCE). Intuitively, one can think of this as the generative analogue of the cross-entropy loss popular in classification settings. Following the notation in Definition 2.1, we define RCE as:

We show that if we want to minimize RCE over a partition, then we must have CPR on this partition:

From Theorem 3.1, we know that Posterior Sampling is the only algorithm that can achieve CPR over all measurable sets. The same result holds if we restrict to measurable partitions, so Posterior Sampling is the only algorithm that minimizes RCE obliviously to the partition.

Experiments

So far we have discussed and analyzed properties of several different fairness metrics. In this section, we briefly describe how one can implement Posterior Sampling, and study the empirical performance of Posterior Sampling and PULSE with respect to our defined metrics, on the MNIST (LeCun, 1998), FlickrFaces-HQ (Karras et al., 2019) and AFHQ cat&dog dataset (Choi et al., 2020b).

We implement Posterior Sampling via Langevin dynamics, which states that if $x_{0}\sim\mathcal{N}(0,cI_{n}),$ (for $c$ appropriately small), then we can sample from $p(x|y)$ by running noisy gradient ascent:

where $\xi_{t}\sim\mathcal{N}(0,I_{n})$ is an i.i.d. standard Gaussian drawn at each iteration. It is well known (Welling & Teh, 2011; Song & Ermon, 2019b) that as $\gamma_{t}\to 0,t\to\infty,$ we have $p(x_{t}|y)\to p(x|y).$ In practice, we need some form of annealing of the noise in order to mix efficiently. Since our algorithm is randomized, we always output the first obtained reconstruction. Please see Appendix D for architecture-specific details.

2 MNIST dataset

We trained a VAE (Kingma & Welling, 2013) on MNIST digits, and consider the groups {0, 1, 2, 3, 4, $\geq 5$}. As seen in the confusion matrix in Table 1, Posterior Sampling does satisfy SPE obliviously over the groups (recall that SPE also implies PR).

3 FlickrFaces dataset

We use a StyleGAN2 (Karras et al., 2020b) model for PULSE, while Posterior Sampling uses the NCSNv2 generative model (Song & Ermon, 2019a, 2020). We choose this model as it has been designed to produce images via Langevin dynamics, which is the practical implementation of Posterior Sampling.

Results

In Figure 1, we show the results of super-resolution on Barack Obama and four faces from FFHQ, using PULSE and Posterior Sampling. As shown, Posterior Sampling preserves the image features better than PULSE. We use the CLIP classifier (Radford et al., 2021) to assign labels of {child with / without glasses, adult with / without glasses}, and report the confusion matrix in Table 2. This shows that Posterior Sampling satisfies SPE over multiple groups obliviously.

Please see Appendix A for more representative samples. These correspond to images 69000-69020 in the FFHQ validation set (these were the first 20 images as we downloaded them in reverse-chronological order from the Google Drive folder).

4 AFHQ Cats and Dogs dataset

We trained StyleGAN2 (Karras et al., 2020a) on the AFHQ cat & dog (Choi et al., 2020b) training set. In order to study the effect of population bias on PULSE and Posterior Sampling, we trained three models on datasets with varying bias: (1) 20% cats and 80% dogs, (2) 80% cats and 20% dogs, and (3) 50% cats and 50% dogs.

In order to label the images generated by the GAN, we take a pre-trained Resnet108 and retrain the last layer using labelled images from the AFHQ training set. We find that the classifier’s predictions does match the human perception of dogs and cats in general.

Posterior Sampling satisfies SPE and PR when the cats and dogs are unbalanced.

For this experiment, we draw $x^{*}$ from the AFHQ validation dataset, which contains 500 images of cats and 500 images of dogs. Since we want to study whether Posterior Sampling and PULSE satisfy SPE and PR, we construct the test set to match the training population of the generator. That is, for the 20% cat generator, we use 125 images of cats and all 500 images of dogs from the AFHQ dataset. Similarly, for the 80% cat generator, we use 500 images of cats and 125 images of dogs in the test set.

We then downscale the images, and vary the downscaling factor such that the observed measurements have resolution $1\times 1,2\times 2,4\times 4,8\times 8.$ We ran PULSE and Posterior Sampling to super-resolve the blurry measurements, and used a classifier to count how many cats and dogs were reconstructed in the wrong class. The results for the 20% cat generator are in Table 3(a) and Figure 4(a), and the results for the 80% cat generator are in Table 4(a) and Figure 5(a). In Figure 3 we show example reconstructions.

We find that PULSE consistently makes very few mistakes on the majority, and an overwhelming number of mistakes on the minority. Posterior Sampling, however, makes an approximately equal number of mistakes on each class (i.e., satisfies SPE). Equivalently for this 2-class setting, it generates cats and dogs in proportion to their population (i.e., satisfies PR).

Posterior Sampling satisfies RDP, SPE, and PR when the cats and dogs are balanced.

We use a generator trained on 50% cats and 50% dogs, and study whether Posterior Sampling and PULSE satisfy RDP, SPE, and PR in practice. In this case, we use all images of cats and dogs from the AFHQ validation set. These results are in Appendix B, Figure 10. Please see Appendix B for more results as we vary the training bias of the generator and test SPE for images drawn from the range of the generator.

Limitations

The fact that CPR can be satisfied obliviously is its main strength, as the subgroups one would like to protect are often not well defined or labeled in datasets. This is especially beneficial for overlooked groups that lack the power to convince an algorithm designer to cater to them. However, obliviousness can also be seen as a weakness, as it leads to symmetry in the number of errors in each group rather than the fraction of errors. For two groups, this means that the minority group will always have higher error rate than the majority.

Furthermore, the goal of CPR is to treat the members of each group equally. The philosophical stance behind this property implicitly views being “fair” as treating individuals equally, and hence representing groups in proportion to their size. However, alternative philosophical stances exist. In particular, it is at odds with the idea that historically oppressed minorities should get particular attention (Hanna et al., 2020). One could adapt such an approach into our framework by reweighting the classes, analogous to Theorem 3.5, but doing so requires explicit group information.

Finally, all of the definitions we consider focus on representation but do not consider the quality of the reconstruction. If all reconstructions on minorities were of poor quality (for instance because the training set did not have enough images of this specific minority, and/or they were of poorer quality, as we know can happen (Buolamwini & Gebru, 2018)), the algorithm could still satisfy any of the definitions and be deemed “fair” according to it. Representation fairness is just one piece of the larger question of fairness in reconstruction.

Conclusion

In the image generation setting, fairness is related to the concept of representation: we assign a protected group to the output, which should match the protected group of the input. This is a stark contrast with the classification setting, in which we usually require some form of independence between the output and the sensitive attributes. We therefore introduce two notions of fairness, an extension of demographic parity called Representation Demographic Parity (RDP), and a conceptually new notion, Conditional Proportional Representation (CPR). We show that these notions are in general incompatible. Furthermore, we prove that RDP is strongly dependent on the choice of the protected groups. This is especially problematic for generating images of people, as races are usually ill-defined and/or ambiguous. CPR, however, does not suffer from these downsides, and can even be satisfied obliviously (i.e., simultaneously for any choice of protected groups).

We prove that Posterior Sampling can achieve CPR, and is actually the only algorithm that can achieve CPR fully obliviously. We show how to experimentally implement our findings through Langevin dynamics, and our experiments exhibit the expected desirable properties.

We see our work as a first step towards better understanding ideas of fairness in the context of generating structured data – our paper deals with image generation, but the problem of generating structured data could be extended to other settings. What happens when the data is of a different type? For instance, one might want to predict pronouns in the context of text completion or generation, or provide the option to use a certain dialect.

The definitions introduced in this paper are specific to generative procedures. However, the underlying issues – having definitions that do not strongly rely on the choice of the protected groups – can be found in the classification setting as well. It would be interesting to see if any analogs of CPR exist in this more traditional setting, and if there exist algorithms that can achieve it obliviously.

Acknowledgements

Ajil Jalal and Alex Dimakis were supported by NSF Grants CCF 1934932, AF 1901292, 2008710, 2019844 the NSF IFML 2019844 award and research gifts by Western Digital, WNCG and MLL, computing resources from TACC and the Archie Straiton Fellowship. Sushrut Karmalkar was supported by a University Graduate Fellowship from the University of Texas at Austin. Jessica Hoffmann was supported by NSF TRIPODS grant 1934932. Eric Price was supported by NSF Award CCF-1751040 (CAREER) and NSF IFML 2019844.

References

Appendix A FFHQ Experiments

Appendix B AFHQ Experiments

For this experiment, we draw $x^{*}$ from the validation set of the AFHQ dataset which contains 500 images of cats + 500 images of dogs. We use a generator trained on 50% cats and 50% dogs, and use it to study whether posterior sampling and PULSE satisfy RDP, SPE, and PR in practice. These results are in Figure 10.

In Figure 11, we show results when 200 images drawn from the 20% cat generator are reconstructed.

In Figure 12, we show results when 200 images drawn from the 80% cat generator are reconstructed.

B.3 Varying training bias

We train StyleGAN2 models with 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 90% cats, and report the fraction of errors on cats when tested on the AFHQ validation set. The results are in Figure 13.

Appendix C Proofs

Let $A$ and $B$ be disjoint groups (e.g., Asian and White people), and let $A_{1},A_{2}\subset A$ be disjoint groups that cannot be perfectly distinguished from measurements only (e.g., South Asians and East Asians). Then Representation Demographic Parity cannot be satisfied $\{\{A,B\},\,\{A_{1},A_{2},B\}\}$-obliviously.

Let $A=A_{1}\cup A_{2}$. We write $p_{a}=\Pr(x^{*}\in a)$, $q_{ab}=\Pr(\hat{x}\in b|x^{*}\in a)$. Using Representation Demographic Parity, with respect first to $\{A,B\}$, then to $\{A_{1},A_{2},B\}$, we have:

Writing $0<\frac{p_{A_{1}}}{p_{A_{1}}+p_{A_{2}}}=\alpha<1$, and replacing $q_{AA},q_{A_{1}A_{1}}$ and $q_{A_{2}A_{2}}$ by $q_{BB}$, we have:

Therefore, an algorithm can satisfy Representation Demographic Parity $\{\{A_{1}\cup A_{2},B\},\,\{A_{1},A_{2},B\}\}$-obliviously if and only if there exists no confusion between $A_{1}$ and $A_{2}$, i.e. $q_{A_{1}A_{2}}=0=q_{A_{2}A_{1}}$. ∎

The only way for an algorithm to satisfy Representation Demographic Parity obliviously is to achieve perfect reconstruction.

Suppose there exists $x$ such that $\Pr(x)>0$, and $x_{1}\neq x$ such that $\Pr(\hat{x}=x_{1})>0$. Let us split the space into two groups $A$ and $B$, such that both $x$ and $x_{1}$ belong in $A$. We now further split $A$ into $A_{1}$ and $A_{2}$, such that $x_{1}$ belongs in $A_{1}$, and $x$ belongs in $A_{2}$. $A_{1}$ and $A_{2}$ now are not perfectly distinguishable, so using the claim above, Representation Demographic Parity is not satisfiable $\{\{A_{1}\cup A_{2},B\},\,\{A_{1},A_{2},B\}\}$-obliviously, so it cannot be satisfiable obliviously. ∎

Whenever there exists a majority class that the measurements cannot 100% distinguish from the non-majority classes, PR and RDP are not simultaneously achievable.

Suppose towards a contradiction that both PR and RDP hold, and the distribution is such that

Since PR holds, $\Pr(\hat{x}\in c_{1})=\Pr(x^{*}\in c_{1})$. However, since RDP holds and the algorithm does not reconstruct each class perfectly we have $\alpha=\Pr(\hat{x}\in c_{i}\mid x^{*}\in c_{i})<1$ for all the $i$. We now observe the following contradiction.

Let $\mathcal{A}$ denote a reconstruction algorithm. Given measurements $y$, let $Q(U|y)$ denote the probability that the reconstruction from algorithm $\mathcal{A}$ lies in the measurable set $U$.

By the definition of the total variation distance, we have

This shows that the output distribution of $\mathcal{A}$ must exactly match the posterior distribution $P(\cdot|y)$, and hence posterior sampling is the only algorithm that can satisfy obliviousness and CPR. ∎

In the setting of Definition 2.1, Conditional Proportional Representation implies Symmetric Pairwise Error.

Consider the term $\Pr(\widehat{x}\in c_{i},x^{*}\in c_{j})$. We can write this as an average over $y$, to get:

Note that $\widehat{x}\&x^{*}$ are conditionally independent given $y$. This is because $\widehat{x}$ is purely a function of $y$. This gives

If we have CPR with respect to $c_{i}$ and $c_{j}$, then we can rewrite the above equation as

Using the conditional independence of $x^{*},\widehat{x}$ given $y$, we now have

The proof follows directly from Theorem 3.1 and Theorem 3.3 ∎

In the special case of 2 classes, the reweighting is very simple: $\lambda_{1}=\lambda_{2}=\frac{1}{2}$.

We will prove this theorem by contradiction. Before we start, observe that if we scale the mass of $c_{i}$ by $\lambda_{i}\geq 0$, we have,

WLOG, assume $\sum_{i}\lambda_{i}=1$, this can be done by rescaling the $\lambda_{i}$’s by their sum. RDP is achieved if all the $\alpha_{i}$ are equal. Let the smallest $\alpha_{i}$ when all the $\lambda_{i}$’s are equal be $\epsilon$. Consider the set $T:=\{\vec{\lambda}\mid\sum_{i}\lambda_{i}=1,\forall i~{}\alpha_{i}\geq\epsilon\}$.

Towards a contradiction, suppose no assignment of $\vec{\lambda}\in T$ achieves $f(\vec{\lambda}):=\frac{\max_{i}\alpha_{i}}{\min_{j}\alpha_{j}}=1$. Let $r:=\min_{\lambda_{1},\dots,\lambda_{k}}f(\vec{\lambda})>1$, and let $\vec{\lambda}^{*}$ be a point which achieves this. $\vec{\lambda}^{*}$ exists since $f(\vec{\lambda})$ is continuous over $T$, which is compact.

We will show that there exists $\vec{\lambda}^{\prime}\in T$ such that $f(\lambda^{\prime})<r$, which contradicts our hypothesis. Let $S:=\{i\in[k]\mid\alpha_{i}\leq\sqrt{r}\min_{i}\alpha_{i}\}$ and,

Let $\alpha^{\prime}_{i}$ be $\Pr(\hat{x}\in C_{i}\mid x^{*}\in C_{i})$ where the probability is with respect to the modified distribution. For $i\in S$,

Where the last line follows from the fact that $\lambda^{\prime}_{i}\geq\lambda_{i}$ for all $i$, since $r>1$, which means the denominator only increases. A similar calculation shows that if $i\notin S$, then each $\alpha_{i}$ is multiplied by a factor between $r^{-1/4}$ and $1$.

We notice that, by definition of $S$, all the $j$ such that $\alpha_{j}=\min_{i}\alpha_{i}$ are in $S$, and all the $k$ such that $\alpha_{k}=\max_{i}\alpha_{i}$ are not in $S$. This ensures that $\max_{i}\alpha_{i}^{\prime}<\max_{i}\alpha_{i}$ and $\min_{i}\alpha^{\prime}_{i}>\min_{i}\alpha_{i}\geq\epsilon$. Which, in turn, contradicts the hypothesis that $r$ was the smallest achievable ratio with the original constraints, since we can always renormalize $\lambda^{\prime}_{i}$ without affecting the $\alpha_{i}$.

The proof follows from Lemma C.1. Note that $H(U|Y)$ is a function of $x^{*}\&y$ and hence has no dependence on the reconstruction algorithm. By the non-negativity of $KL$ divergence, the representation cross-entropy is minimized when $Q(U_{i}|y)=P(U_{i}|y)$ for each $i\in[N],$ almost surely over $y$. ∎

For a reconstruction algorithm $\mathcal{A},$ let $Q(c_{i}|Y)$ denote the probability that the reconstruction lies in the set $c_{i}$ given measurements $y$. Let $P(c_{i}|y)$ denote the probability that $x^{*}$ lies in $U_{i}$ conditioned on $y$.

There is a slight abuse of notation in the lemma. Since $U$ is a function of $x^{*},$ when treating $x^{*}$ as a random variable, we also treat $U$ as a random variable.

By the definition of $RCE$ and the tower property of expectations, we have

where the second line follows because the $U_{i}$s form a partition, the third line follows since $\widehat{x}\in U(x^{*})$ is equivalent to $\widehat{x}\in U_{i}$ if we know that $x^{*}\in U_{i}$, the fourth line follows from the definition of $Q(U_{i}|y)$ and the last line follows from linearity of expectation.

Now we can multiply and divide $P(U_{i}|y)$ within the $\log$ term above. This gives

Appendix D Langevin Dynamics

The prior of the latent and noise variables is a standard Gaussian distribution. Since we know the prior distribution of these variables, if we know the distribution of the meaurement process, we can write out the posterior distribution.

For the measurement process we consider, we have $y=Ax^{*}$, where $A$ is a blurring matrix of appropriate dimension. Note that in the absence of noise, posterior sampling must sample solutions that exactly satisfy the measurements. However, this is difficult to enforce in practice, and hence we assume that there is some small amount of Gaussian noise in the measurements. In this case, the posterior distribution becomes:

where $c(y)$ is an additive constant which depends only on $y$.

Now, Langevin dynamics tells us that if we run gradient ascent on the above log-likelihood, and add noise at each step, then we will sample from the conditional distribution asymptotically. Please note that we sample $z$ and all noise variables $n_{1},\cdots,n_{18}.$

In our experiments, we do 1500 gradient steps. In practice, we replace the $\sigma$ in the equation above with $\sigma_{t}$, where $t$ is the iteration number. When the measurements have resolution $8\times 8$ or $4\times 4$, we find that $\sigma_{1}=1.0,\sigma_{1500}=0.1$ works best. When the resolution of the measurements is $2\times 2$ or $1\times 1$, we find that $\sigma_{1}=1.0,\sigma_{1500}=0.01$ works best. We change the value of $\sigma_{t}$ after every 3 gradient steps, such that $\sigma_{1},\sigma_{4},\sigma_{7},\cdots,\sigma_{1497}$ form a geometrically decreasing sequence. The learning rate $\gamma_{1500}$ is also tuned to be a decreasing geometric sequence, such that $\gamma_{t}=5\cdot 10^{-6}.$ Please see (Song & Ermon, 2019a) for the equations specifying the learning rate tuning, and the logic behind it.

We also find that adding a small amount of noise corresponding to $\sigma_{1500}$ in the measurements helps Langevin mix better.

We note that our approach is different from prior work (Karras et al., 2020b; Menon et al., 2020a), which optimizes a function of our variable $z$, and a subset of the noise variables.

The NCSNv2 model (Song & Ermon, 2020) has been designed such that sampling from the marginal distribution requires Langevin dynamics. This model is given by a function $s(x;\sigma)$, which outputs $\nabla\log p_{\sigma}(x),$ where $p_{\sigma}(x)$ is the distribution obtained by convolving the distribution $p(x)$ with Gaussian noise of variance $\sigma^{2}$. That is, $p_{\sigma}(x)=(p*\mathcal{N}(0,\sigma^{2}))(x)$.

It is easy to adapt the NCSNv2 model to sample from posterior distributions, see (Song & Ermon, 2020) for inpainting examples. In our super-resolution experiments, one can compute the gradient of $p(y|x)$, to get the following update rule for Langevin dynamics:

where $A$ is the blurring matrix, and $\xi_{t}\sim\mathcal{N}(0,I_{n})$ is i.i.d. Gaussian noise sampled at each step. We use the default values of noise and learning rate specified in https://github.com/ermongroup/ncsnv2/blob/master/configs/ffhq.yml. That is, $\sigma_{1}=348,\sigma_{6933}=0.01$, and $\gamma_{6933}=9\cdot 10^{-7}.$ Note that the value of $\sigma,\gamma$ changes every 3 iterations, and both $\gamma_{t}$ and $\sigma_{t}$ decay geometrically. See (Song & Ermon, 2020) for specific details on how these are tuned.

Appendix E Code

All code and generative models, along with hyperparameters and README are available at https://github.com/ajiljalal/code-cs-fairness.