Source-linked AI summary
The Price of Fair PCA: One Extra Dimension
Samira Samadi, Uthaipon Tantipongpipat, Jamie Morgenstern, Mohit Singh, Santosh Vempala
TL;DR
PCA can represent two populations with different reconstruction fidelity, motivating a fairness objective for dimensionality reduction. The paper defines Fair PCA and gives a polynomial-time algorithm that achieves the optimal fair objective using at most one additional dimension, while experiments show improved balance between populations.
Problem
PCA can impose higher reconstruction error on one population than another, even when the populations are similarly sized, raising fairness concerns for dimensionality reduction.
Method
The paper defines Fair PCA by minimizing the maximum additional reconstruction loss relative to each population’s individually optimal projection, then solves it through an SDP followed by an LP rank-reduction step.
Results
The algorithm achieves the optimal fair PCA objective with a representation of rank at most d+1 and equal losses for the two populations.
Takeaways & Limitations
Fair PCA can improve fidelity for the worse-served population by accepting a corresponding loss for the better-served population, producing more balanced representations.
Takeaways & Limitations
The algorithm’s SDP component dominates runtime and is too slow for practical use on moderate-sized data sets.
Abstract
from arXiv · showhide
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.
1 Introduction
PCA can produce substantially different reconstruction fidelity for equally sized populations, motivating dimensionality reduction that equalizes populations’ additional error. The paper proposes Fair PCA and a polynomial-time near-optimal algorithm, while noting practical runtime and broader fairness implications.
- PCA can incur much higher average reconstruction error for one population than another, even when populations are similarly represented.
- Fairness in dimensionality reduction matters because PCA representations can contribute to representational harms in high-stakes scientific and economic applications.
- Fair PCA minimizes the maximum additional reconstruction error each population incurs relative to its population-specific optimal d-dimensional projection.
- A polynomial-time algorithm finds an n into (d + 1)-dimensional embedding whose objective value is better than any d-dimensional embedding.
- The algorithm uses a semidefinite program, though the paper notes that this can be prohibitively slow for practical applications.
2 Related work
Related fairness work often seeks balanced decisions or representations that hide sensitive attributes. This paper instead focuses on preserving comparable information about each population after dimensionality reduction.
- Representation-learning approaches commonly reduce dependence between a representation and a protected attribute while retaining information or task-relevant information.
- The paper’s distinct goal is to maintain as much information as possible about each population after projection.
- Sensitive-attribute obfuscation methods aim to hide the attribute, whereas this work aims for high fidelity regardless of the attribute.
- Much fairness research targets classification, scoring, statistical parity, or equal false-positive and false-negative rates.
3 Notation and vanilla PCA
The paper models data as an n-dimensional matrix containing two subpopulations and recalls vanilla PCA as a rank-constrained reconstruction-error minimization problem. Its optimal projection uses the top d eigenvectors of the data covariance-style matrix M^T M.
- Data points are represented as rows of M ∈ R^{m×n}, with two subpopulations corresponding to different values of a binary sensitive attribute.
- The Frobenius norm and inner product provide the matrix notation used for reconstruction-error calculations.
- Vanilla PCA seeks a rank-at-most-d approximation that minimizes the Frobenius reconstruction error.
- An optimal rank-d PCA approximation has the form MWW^T, where W’s orthonormal columns are eigenvectors for the top d eigenvalues of M^T M.
4 Fair PCA
Fair PCA measures how much each population loses when represented together rather than by its own optimal d-dimensional projection. The objective minimizes the worse population loss and yields equal normalized losses at an optimum.
- Motivation: The motivating examples show that a single projection can favor one population or impose substantial error on both, despite each population separately admitting a high-fidelity projection.A second example shows why minimizing maximum reconstruction error alone can penalize a well-represented population without improving the other.
- Fair PCA formulation: The formulation targets similar additional error for populations A and B when they share one d-dimensional representation.Reconstruction error is normalized by population size, while reconstruction loss compares against each population’s optimal rank-d approximation.
- Fair PCA formulation: Fair PCA minimizes the maximum loss each population suffers relative to its individually optimal rank-d representation.This loss-based objective avoids worsening one population without improving the other, unlike minimizing raw maximum reconstruction error.
- Optimality condition: At a Fair PCA solution, the normalized losses of populations A and B are equal.The theorem states that 1/|A| loss(A, UA) equals 1/|B| loss(B, UB).
5 Algorithm and analysis
The algorithm relaxes Fair PCA to a semidefinite program and then uses a linear program and extreme-point structure to reduce rank. For two populations, it achieves the optimal d-dimensional fairness objective using at most d+1 dimensions, while the SDP can be computationally impractical for moderate n.
- Algorithm: The algorithm solves an SDP relaxation followed by an LP-based rank reduction procedure.Extreme-point constraints imply that the resulting solution lies in at most d+1 dimensions.
- Two-population guarantee: A polynomial-time algorithm outputs either an optimal rank-d solution or a rank-(d+1) solution with equal population losses and the optimal d-dimensional fairness objective.This is the two-population guarantee stated in Theorem 5.1.
- Projection construction: The resulting affine projection embeds each point using at most d+1 coordinates while preserving the optimal fairness objective.The projection is constructed from the SDP/LP solution and has rank at most d+1.
- Multiple populations: With k populations, the method uses at most d+k−1 dimensions while achieving the optimal fairness objective for dimension d.For more than two groups, equal losses need not hold for every optimal d-dimensional solution, but the added dimensions keep each loss within the optimal objective.
- Runtime: The SDP dominates runtime at O(n^6.5 log(1/ϵ)) and is too slow for practical use on moderately sized n.A multiplicative-weight variant is reported to reach ϵ < 10^-5 within tens of iterations and handle dimensions up to a thousand in under a minute.
6 Experiments
Experiments on LFW and Default Credit compare vanilla PCA with Fair PCA across population reconstruction error and loss. PCA shows population disparities, while Fair PCA equalizes loss by improving the less well represented population at a cost to the better represented one.
- Datasets and preprocessing: The experiments use LFW face data and Default Credit data, with preprocessing that centers all data and normalizes pixel values or attribute variances.LFW pixels are normalized by 1/255, while each Credit attribute is scaled to variance 1.
- Reconstruction error: At 20 dimensions, PCA’s male–female average reconstruction-error gap on LFW reaches up to 10% of total reconstruction error, even with equally sampled populations.Equal sampling gives men and women equal magnitude in PCA’s objective function.
- Reconstruction error: As dimensionality increases, average reconstruction error decreases for every population; Credit error reaches 0 at 21 dimensions because the original data has 21 dimensions.LFW has 1764 original dimensions, so 20 dimensions still leave considerable reconstruction error.
- Average loss: PCA produces much higher average loss for female than male faces, while Fair PCA places both populations’ loss at the same intermediate level.The Credit data shows the same qualitative pattern: improving the less represented population costs the better represented population.
7 Future work
The paper identifies unresolved theoretical and empirical questions about fair dimensionality reduction, including the complexity of its objective and the necessity of extra dimensions. It also frames the work as an incomplete study of how dimensionality reduction affects population fairness.
- Scope and open questions: The study remains incomplete regarding when and how dimensionality reduction helps or harms fair treatment of different populations.The authors describe several concrete theoretical questions as open.
- Scope and open questions: The complexity of optimizing the fairness objective, including whether it is NP-hard for d = 1, remains unresolved.This is posed explicitly as a future theoretical question.
- Scope and open questions: For k predefined subgroups, the algorithm naturally extends using k −1 additional dimensions, but whether these dimensions are necessary for computational efficiency remains open.The paper does not establish that the extra dimensions are unavoidable.
- Broader implication: The broader goal is to highlight another way standard machine-learning techniques may introduce unfair treatment of subpopulations.The authors identify further work on this issue as needed.
A Improved runtime of semi-definite relaxation by multiplicative weight update method
This appendix develops a multiplicative-weight framework for solving the fair PCA semidefinite relaxation and analyzes its runtime. The method repeatedly solves weighted standard PCA subproblems, with complexity depending on the number of groups, accuracy, and input width.
- Algorithmic framework: The multiplicative-weight algorithm solves the fair PCA relaxation for an n × n matrix to ϵ additive error using repeated standard PCA computations.The framework is later specialized to the fair PCA SDP.
- Runtime: For two groups, the method requires O(1/ϵ^2) iterations of standard PCA, such as SVD, and therefore has O(n^3/ϵ^2) runtime.The runtime uses SVD’s O(n^3) cost per iteration.
- Runtime: For k groups, the iteration bound is O(W^2 log k/ϵ^2), where W is the problem width and is at most the total input variance L.Under the normalization assumption L ≤1, this yields an O(log k/ϵ^2) iteration bound.
- Algorithmic framework: The framework replaces a feasibility-oriented multiplicative-weight procedure with an optimization counterpart tailored to the fair PCA SDP.The authors state that this formulation fits the fair PCA setting and simplifies implementation.
- Oracle implementation: A weighted single-constraint oracle can be solved by applying standard PCA to the union of groups after weighting each group according to p.The weighted solution optimizes the corresponding weighted objective.
A.1.2 New setting: multiplicative weight on optimization problem
This section extends multiplicative weights from feasibility to optimization, seeking the best feasible solution without guessing the unknown optimum. In fair PCA, the resulting weighted optimization oracle can be solved through standard PCA on appropriately weighted groups.
- Optimization formulation: The new framework asks for the best x ∈P rather than merely determining whether a feasible x exists.It formalizes the optimization problem by minimizing a slack variable z subject to Ax −b + z·1 ≥0.
- Optimization formulation: The optimization formulation avoids guessing the unknown optimum z∗ and removes the binary-search log(n/ϵ) factor from the previous approach.The modification also simplifies the algorithm.
- Optimization oracle: The framework assumes an oracle that, for a probability vector p over constraints, returns a maximizer of the weighted optimization objective.This replaces feasibility checking with direct optimization under weighted constraints.
- Optimization oracle: In the fair PCA setting, the optimization oracle can be implemented by standard PCA on the union of the two groups after appropriate weighting.This makes the one-constraint optimization subproblem tractable through an existing PCA routine.
A.2 Algorithm and Analysis
The section develops a multiplicative-update framework that solves the optimization problem through a bounded oracle, achieving additive-error guarantees with controlled oracle complexity.
- Oracle refinement: The oracle framework avoids guessing the unknown optimum z∗ while slightly improving runtime and simplifying the algorithm.Known bounds on the range of Aix − bi can still provide useful oracle parameters ℓ and ρ.
- Optimization guarantee: The proof uses a bounded oracle and multiplicative updates to solve the optimization problem up to additive error ϵ.The oracle-based algorithm outputs x satisfying Ax − b + z∗·1 ≥ −ϵ.
- Multiplicative-update procedure: The algorithm initializes uniform constraint weights, repeatedly queries the oracle, updates weights using losses, and averages the oracle outputs.The update process is multiplicative in nature and uses a learning rate η over T iterations.
A.3 Application of multiplicative update method to the fair PCA problem
This section applies multiplicative updates to the SDP relaxation of Fair PCA, using a weighted PCA oracle to obtain near-optimal solutions with polynomial runtime.
- Fair PCA formulation: The Fair PCA SDP relaxation is expressed as an LP with two group-specific constraints over positive semidefinite projection matrices.The feasible matrices satisfy 0 ⪯ M ⪯ I and Tr(M) ≤ d.
- Oracle construction: The oracle combines the two group constraints using weights p and solves the resulting problem by taking top principal components of a weighted covariance matrix.The weighted constraint is linear in P because both group terms are dot products with fixed covariance matrices.
- Approximation guarantee: The multiplicative-weight algorithm finds a solution within additive error ϵ after O(1/ϵ²) oracle calls.The oracle is shown to be (1, 1)-bounded after normalizing the group variances.
- Runtime: O(n³/ϵ²) is the resulting running time because each oracle call solves standard PCA in O(n³) time.Weight updates add negligible processing time relative to the PCA computation.
- Extension to multiple groups: For k groups, the method requires O(log k/ϵ²) oracle calls, while SVD remains the dominant cost when k is much smaller than n.Each call additionally computes a weighted sum of k matrices in O(kn²) arithmetic operations.
B Proofs
The proofs establish that projecting onto a suitable d-dimensional subspace improves reconstruction loss relative to arbitrary rank-d representations, using eigenvector-based subspace transformations.
- Projection comparison: The proof first shows that replacing an arbitrary rank-d representation with projection onto a d-dimensional subspace cannot increase reconstruction loss.For every row, choosing coefficients equal to AiV minimizes the row-wise approximation error.
- Two-population conclusion: Applying the same reasoning to both populations yields loss(A, AVVᵀ) ≤ loss(A, UA) and the analogous inequality for B.Thus the principal-subspace projection is no worse than the corresponding arbitrary rank-d representations for either group.
- Eigenvector-based improvement: The argument iteratively moves a subspace toward the top eigenvectors of AᵀA while strictly decreasing the objective whenever the subspace is not optimal.The construction replaces a vector with a combination involving a missing top eigenvector and proves the objective decreases.
- Eigenvalue argument: The decrease follows because the top eigenvector has greater squared image norm than the vector it replaces.The proof uses ∥Aw∥² − ∥Au1∥² = ϵ²(λ1 − ∥Au1∥²) > 0.