The Price of Fair PCA: One Extra Dimension
We investigate whether the standard dimensionality reduction technique of PCA inadvertently produces data representations with different fidelity for two different populations. We show on several real-world data sets, PCA has higher reconstruction error on population A than on B (for example, women versus men or lower-versus higher-educated individuals). This can happen even when the data set has a similar number of samples from A and B. This motivates our study of dimensionality reduction techniques which maintain similar fidelity for A and B. We define the notion of Fair PCA and give a polynomial-time algorithm for finding a low dimensional representation of the data which is nearly-optimal with respect to this measure. Finally, we show on real-world data sets that our algorithm can be used to efficiently generate a fair low dimensional representation of the data.
The manuscript proposes a dimensionality reduction method called “fair PCA”. The proposed study is based on the observation that, in a data model containing more than one data category (“population” as called by authors), the projection learnt by PCA may yield different reconstruction errors for different populations. This may impair the performance of machine learning algorithms that have access to dimensionality-reduced data obtained via PCA.   To address this problem, the authors propose a variant of the PCA algorithm that minimizes the total deviation between the error of the learnt projection and the error of the optimal projection for each population.  Quality: The paper is based on an interesting idea with an interesting motivation. The technical content of the paper is of satisfactory depth. The proposed work can find usage in many applications.  A few comments and questions:  - A setting with only two populations is considered in the theoretical results and the proposed algorithm. Is it possible to extend these results to a setting with multiple populations? In particular, is it easy to suggest a multiple-population version of Theorem 4.5?  - The experimental evaluation of the proposed algorithm is somewhat limited. It would be very interesting to see whether the proposed dimensionality reduction method improves the performance of machine learning algorithms when used for preprocessing the data containing two/multiple populations.  - Please have a complete pass over the paper to check the language. There are several sentences with typos and mistakes.     Clarity: The presentation of the study is of satisfactory clarity in general. However, please address the following issues:  - The discussion in page 2, lines 62-69 is hard to follow. It would be good to paraphrase with more clear wording.  - Please define the notation [A/B] in line 5 of Algorithm 1.  - In the first plot in Figure 2, the loss seems to increase with the number of dimensions. This contradicts the expectation that the loss should decay to 0 in the long term as the number of dimensions increases, since the approximation error of both PCA and fair PCA would approach 0. How do the authors explain this behavior?   Originality: As far as I know, the work is based on an original idea and problem formulation.  Significance: The proposed study has solid content and may find useful application in many machine learning problems.