Fair Principal Component Analysis (PCA) is a problem setting where we aim to
perform PCA while making the resulting representation fair in that the
projected distributions, conditional on the sensitive attributes, match one
another. However, existing approaches to fair PCA have two main problems:
theoretically, there has been no statistical foundation of fair PCA in terms of
learnability; practically, limited memory prevents us from using existing
approaches, as they explicitly rely on full access to the entire data. On the
theoretical side, we rigorously formulate fair PCA using a new notion called
\emph{probably approximately fair and optimal} (PAFO) learnability. On the
practical side, motivated by recent advances in streaming algorithms for
addressing memory limitation, we propose a new setting called \emph{fair
streaming PCA} along with a memory-efficient algorithm, fair noisy power method
(FNPM). We then provide its {\it statistical} guarantee in terms of
PAFO-learnability, which is the first of its kind in fair PCA literature.
Lastly, we verify the efficacy and memory efficiency of our algorithm on
real-world datasets.

公平主成分分析（Fair Principal Component Analysis，fair PCA）是一个问题设置，旨在在执行主成分分析的同时，使得所得到的表示在条件敏感属性的情况下相互匹配的分布公平。然而，现有的公平主成分分析方法存在两个主要问题：从理论上讲，公平主成分分析在可学习性方面没有统计学基础；从实际上讲，有限的内存限制了现有方法的使用，因为它们明确要求对所有数据进行完全访问。在理论上，我们使用一个称为 “可能近似公平和最优学习”（PAFO-learnability）的新概念，严格地制定了公平主成分分析。在实际上，受近期应对内存限制的流数据算法的最新进展的启发，我们提出了一种称为 “公平流式主成分分析（fair streaming PCA）” 的新设置，以及一种内存高效的算法，公平噪声幂法（fair noisy power method，FNPM）。然后，在公平主成分分析文献中，我们提供了该算法的统计保证，这是其首次存在。最后，我们验证了我们算法在现实世界数据集上的效果和内存效率。

公平的流式主成分分析：统计和算法视角

Fair Streaming Principal Component Analysis: Statistical and Algorithmic  Viewpoint

This paper defines fair principal component analysis (PCA) as minimizing the
maximum mean discrepancy (MMD) between dimensionality-reduced conditional
distributions of different protected classes. The incorporation of MMD
naturally leads to an exact and tractable mathematical formulation of fairness
with good statistical properties. We formulate the problem of fair PCA subject
to MMD constraints as a non-convex optimization over the Stiefel manifold and
solve it using the Riemannian Exact Penalty Method with Smoothing (REPMS; Liu
and Boumal, 2019). Importantly, we provide local optimality guarantees and
explicitly show the theoretical effect of each hyperparameter in practical
settings, extending previous results. Experimental comparisons based on
synthetic and UCI datasets show that our approach outperforms prior work in
explained variance, fairness, and runtime.

本文提出了一种公平的主成分分析方法，该方法使用最大均值差异法对不同保护类别的条件分布进行降维，并将多目标策略与数据降维技术相结合，通过在 Stiefel 流形上的非凸优化过程，优化约束条件下的主成分分析，得到较高的计算效率和分类精确性。使用合成数据和 UCI 数据集进行的实验结果表明该方法在自变量解释度，公平性和运行时间方面均优于现有工作。

基于 MMD 的 Stiefel 流形优化的快速高效公平 PCA 算法

Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel  Manifold

We consider Fair Principal Component Analysis (FPCA) and search for a low
dimensional subspace that spans multiple target vectors in a fair manner. FPCA
is defined as a non-concave maximization of the worst projected target norm
within a given set. The problem arises in filter design in signal processing,
and when incorporating fairness into dimensionality reduction schemes. The
state of the art approach to FPCA is via semidefinite relaxation and involves a
polynomial yet computationally expensive optimization. To allow scalability, we
propose to address FPCA using naive sub-gradient descent. We analyze the
landscape of the underlying optimization in the case of orthogonal targets. We
prove that the landscape is benign and that all local minima are globally
optimal. Interestingly, the SDR approach leads to sub-optimal solutions in this
simple case. Finally, we discuss the equivalence between orthogonal FPCA and
the design of normalized tight frames.

本文探讨了公平主成分分析 (FPCA) 的问题，并且提出了使用次梯度下降来解决此问题的方法，该方案可以使优化结果更易于计算且结果更精确。