# Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint

arXiv: https://arxiv.org/abs/2310.18593 · HTML: https://mlsanity.com/paper/2310.18593/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 86 references that are in the map.
- First posted on arXiv 28 Oct 2023.

## Builds on (most cited first, 30 of 45)

- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Null It Out: Guarding Protected Attributes by Iterative Nullspace Projection](https://mlsanity.com/paper/2004.07667/) (2020)
- [A Survey on Explainable Artificial Intelligence (XAI): Towards Medical XAI](https://mlsanity.com/paper/1907.07374/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Fairness without Demographics through Adversarially Reweighted Learning](https://mlsanity.com/paper/2006.13114/) (2020)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Linear Adversarial Concept Erasure](https://mlsanity.com/paper/2201.12091/) (2022)
- [FairBatch: Batch Selection for Model Fairness](https://mlsanity.com/paper/2012.01696/) (2020)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Fair Preprocessing: Towards Understanding Compositional Fairness of Data Transformers in Machine Learning Pipeline](https://mlsanity.com/paper/2106.06054/) (2021)
- [Kernelized Concept Erasure](https://mlsanity.com/paper/2201.12191/) (2022)
- [Probably Approximately Correct Constrained Learning](https://mlsanity.com/paper/2006.05487/) (2020)
- [Towards Fair Classifiers Without Sensitive Attributes: Exploring Biases in Related Features](https://mlsanity.com/paper/2104.14537/) (2021)
- [Algorithmic Fairness in Education](https://mlsanity.com/paper/2007.05443/) (2020)
- [Metric-Free Individual Fairness in Online Learning](https://mlsanity.com/paper/2002.05474/) (2020)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Fairness in Streaming Submodular Maximization: Algorithms and Hardness](https://mlsanity.com/paper/2010.07431/) (2020)
- [Efficient fair PCA for fair representation learning](https://mlsanity.com/paper/2302.13319/) (2023)
- [Memory Limited, Streaming PCA](https://mlsanity.com/paper/1307.0032/) (2013)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Fast Differentially Private Matrix Factorization](https://mlsanity.com/paper/1505.01419/) (2015)

## Built on by (most cited first, 5 of 5)

- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Hidden Convexity of Fair PCA and Fast Solver via Eigenvalue Optimization](https://mlsanity.com/paper/2503.00299/) (2025)
- [Detecting Domain Shifts in Myoelectric Activations: Challenges and Opportunities in Stream Learning](https://mlsanity.com/paper/2508.21278/) (2025)
- [Implicitly Normalized Online PCA: A Regularized Algorithm with Exact High-Dimensional Dynamics](https://mlsanity.com/paper/2512.01231/) (2025)
- [Achieving Fair PCA Using Joint Eigenvalue Decomposition](https://mlsanity.com/paper/2502.16933/) (2025)

## Abstract (arXiv)

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 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 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.