Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint
Authors: Junghyun Lee
Hanseul Cho
Se-Young Yun
Chulhee Yun
Venue: NeurIPS 2023 poster (2023)
Keywords: streaming
PCA
memory-limited
fair representation
online learning
TL;DR: We propose a new problem setting, called fair streaming PCA, and propose a simple yet efficient algorithm that is both theoretically and empirically verified.

Abstract: 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 statistical guarantee in terms of PAFO-learnability, which is the first of its kind in fair PCA literature. We verify our algorithm in the CelebA dataset without any pre-processing; while the existing approaches are inapplicable due to memory limitations, by turning it into a streaming setting, we show that our algorithm performs fair PCA efficiently and effectively.

Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint
Junghyun Lee" Hanseul Cho" Se-Young Yun Chulhee Yun
Kim Jaechul Graduate School of AI, KAIST {jh_lee00, jhs4015, yunseyoung, chulhee, yun) ac.kr
Abstract
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 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) lcarnability. 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 memory-efficiet algorithm, fair noisy power method (FNPM). We then provide its statistical guarantee in terms which is the first of its kind in fair PCA literature. Lastly, verify the efficacy and memory efficiency of our algorithm on real-world datasets.
Introduction
Algorithmic fairness ensures that machine learning algorithms not propagate nor exacerbate bias, which may lead to discriminatory decision-making (Barocas and Selbst, 2016) and thus has been a very active area of research. This has direct implications our everyday life, including but not limited criminal justice (Kirchner et al., 2016), education (Kiziloec and Lee, 2021), and more. See Mchrabi et al. (2021) for a comprehensive survey of bias and fairness in machine learning.
Often, one needs to consider faimess for large number of high- digeediiensional data points. One of the standard tools for dealing with such high-dimensional data is PCA (Hotelling, 1933; Pearson, 1901), a classical yet still one of the most popular algorithms for performing interpretable dimensionality reduction. has been adapted as a baseline and/or standard tool exploratory data analysis, whose application ranges from natural sciences, engineering (Abdi and Williams, 2010; Jolliffe and Cadima, 2016), and even explainable AI (Li al., 2023; Tjoa and Guan, 2021). ). Due to its ubiquity and wide applicability, several works study defining fairness in PCA and developing a fair variant of it. A recent line of research (Kleindessner et al., 2023; Lee et al., 2022: Olfat and Aswani, 2019) defines PCA fairness in the context of fair representation (Zemel et al., 2013) in that the projected group conditional distributions should match.
However, existing fair PCA approaches suffer from two problems. Theoretically, they provide no statistical foundation of fair PCA or guarantees for their algorithms. By statistical foundation, we mean the usual PAC-learabilitty (Shalev-Schwanl and Ben- David, 2014) guarantees, e.g., sample complexity for ensuring optimality explained variance and fairness constraint with high probability.
"Equal contributions
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

On top of that, the second problem arises from a practical viewpoint: memory limitation. All the aforementioned fair PCA algorithms assume that the learner can store the entire data points and incurs memory complexity of order at least (d max (N, d)), where d is the dimensionality of the data and N is the number of data points. As memory limitation is often critical bottleneck in deploying machine learning algorithms (Mirliagkas et al., 2013), as much as faimess is important, it is also paramount that imposing fairness to PCA does not incur too much memory overhead. A popular approach to mitigate such memory limitation for PCA is to consider the one-pass, streaming setting. In this setting, each data point is revealed to the learner sequentially, each point is irretrievably gone unless she explicitly stores it, and she use only (dk) memory, with i being the target dimension of projection. Indeed, without the fairness constraint, streaming PCA has been studied extensively; see Balzano et al. (2018) and references therein.
In this work, we address both problems in a principled manner. Our contributions are as follows:
We provide an alternative formulation of fair PCA based on the "Null It Out" approach (Section 3). Based on the new formulation, we introduce the concept of probably approximately fair and optimal (PAFO)-learnabll)
to formalize the problem of fair PCA (Section 4).
To address the memory limitation, we propose a new problem setting called fair streaming PCA, as well as fair noisy power method (FNPM), a simple yet memory-efficiee algorithm based on the noisy power method. (Section 5). We note that our algorithm incurs a much lower memory complexity even compared to the most efficient variant of fair PCA proposed by Kleindessner al. (2023).
We then prove that our algorithm achieves the PAFO-leamabilinn for fair streaming PCA (Sec- tion 6). Such statistical guarantee is the first of its kind in fair PCA literature.
Lastly, we empirically validate our algorithm on CelebA and UCI datasets. Notably, we run FNPM on the original full-resolution CelebA dataset on which existing fair PCA algorithms fail due to high memory requirements. It shows turning such non-streaming setting into streaming setting and applying our algorithm allows one to bypass the memory limitation (Section 7).
2 Preliminaries
Notation. For E 2 1, let I be the identity matrix of size E x f. For k < d, we bring the Stiefel manifold St,d, k) {A Rddk ATA Is}, which is the collection of all rank-k semi-orthogonal matrices. We denote an orthonormal column basis of a (full column rank) matrix M R obtained by QR decomposition as QR(M) E St k)) and denote its column space by (M) Also, for A E St(d, k),, we denote the orthogonal projection matrix to col( A) mull( (AT) as II A = I,- AAT = La A Moreover, we denote the collection of all possible d- d-dimensional probability distributions as Pa. For zero-mean random matrix Z, its (scalar-valued) variance is defined as Var(Z) ()) = max E [Z 2T]]ll2 ||E ZT 21112) In general, Var Z) Var( Z - B(Z)).
Lastly, we use the usual O, 2t and O notations for asymptotic analyses, where tildes (Ö, á. and é, resp.) are used for hiding logarithmic factors.
Setup. Assume that the sensitive attribute variable, which we will be imposing fairness, is binary, denoted by a E (0. 1}. For each group a, let D, be a d-dimensional distribution of mean μa, and covariance E,, both of which are assumed to be well-defined. We often call them group-conditional mean and covariance, respectively. With a fixed, unknown mixture parameter p E (0, 1), let us denote the total data distribution as D := pDo + (1 - D). Equivalently, the sensitive attribute follows a ~ Bernoulli(p). and the conditional random variable æ|a is sampled from D.. In that case, t.. E[æ[||] and Σ, E[ææTTaa [a] M. We often write po 1 p and pl p for brevity. We also define the mean difference f == μ1 pn and the second moment difference S : E [xxx la = 1] ExxxT la 0] ΣS Eg + mn Mola. Accordingly, denote the true mean and covariance of D as μ and Σ, respectively. For simplicity, let us assume that D is centered, i... | 0: note that this does not mean that the group conditional distributions D. 's are centered.
PCA. In the offline setting, the full covariance matrix Σ is given which is often a sample covariance matrix 1 - a for n data points ,,,..., Tr, The goal of vanilla (offline) PCA (Hotelling, 1933; Pearson, 1901) is to compute the loading matrix V E Rd that preserves as much variance as possible after projecting E via V, i.e., maximize tr II Σ) tr (VV). Here, k < d is the

---

target dimension to which the data's dimensionality d is to be reduced and is chosen by the learner. We additionally consider the constraint E St(d, k) to ensure that the resulting coordinate after the transformation is orthogonal and thus amenable to various statistical interpretations (Johnson and Wichern, 2008). Without any fairness constraint, Eckart- Young theorem (Eckart and Young, 1936) implies that the solution is characterized as a matrix whose columns are the top-k eigenvectors of Σ.
Fair PCA. Recently, it has been suggested that performing vanilla PCA on real-world datasets may exhibit bias, making the final outputted projection "unfair". As is often the case, there can be multiple definitions of fairness in PCA, but the following two are the most popular: equalizing reconstruction losses (Kamani et al., 2022; Samadi et al., 2018; Tantipongpipat et al., 2019; Vu et al., 2022), or equalizing the projected distributions (Kleindessner et al., 2023; Lee al., 2022; Olfat and Aswani, 2019) from the perspective of fair representation (Zemel et al., 2013); we focus on the latter one.
3 An Alternative Approach to Fair PCA
3.1 "Null It Out" Formulation of Fair PCA
In this work, we consider fair PCA as learning fair representation (Zemel et al., 2013). The goal is to preserve as much variance as possible while obfuscating any information regarding the sensitive attribute. To this end, we take the "Null It Out" approach as proposed in Ravfogel et al. (2020). Intuitively, we want to nullify the directions which the sensitive attribute a can be inferred, and in this work, we consider two such unfair directions: mean difference f and eigenvectors of second moment difference S. To give the learner flexibility in choosing the trade-off between fairness and performance (measured in explained variance), let 2 1 be the number of top eigenvectors of S to nullify. Thus, the learner is nullifying at most (m + 1)-dimensional subspace that is unfair with respect to a, which refer to the unfair subspace. Precisely, we formulate our fair PCA as follows:
max tr( tr(VTEV), subject to col(V) co.((P.l1f)+
(1)
()))( where d the data dimensionality, & is the target dimension, and the columns of Pm E St(d, m) is top-m orthonormal eigenvectors of S.
3.2 An Explicit Characterization for Solution of Fair PCA
To first construct the unfair subspace that is spanned by f as well as Pm, let us define U E St(d, mm) be the orthogonal matrix whose columns form a basis of as follows: m vn if f E col(P., and m m + otherwise, and
Then, U has a closed form
Pm.
if f E col(P otherwise,
U
Q = Pm 1
where = 11 f E col( +t Note that g is a vector in a direction that f is projected onto col(P,.. (Pll((PT.... For this U, our constraint in (1) can be interpreted as equivalent nullity constraint Il
max tr(VEEV), subject to Iy V = 0. (ESe(d,))
(3)
The above is equivalent to the following problem without any constraint other than semi-orthgonality:
max tr VV)
VeSt(d,k)
which is basically the vanilla k-PCA problem of a matrix H. EM Therefore, top-k orthonormal column basis this matrix is indeed a solution of our problem (4).
3.3 Comparison to the Existing Covariance Matching Constraint
Previous works on fair PCA (Kleindessner et al., 2023; Olfat and Aswani, 2019) consider an exact
covariance-matching constraint (namely, VT - E = 0). fact, this equivalent to the condition VT VVSV 0 under the mean-matching constraint fTV 0, which can be derived
3

---

VT(E, - Eo]V= - VT (E|a
E 0)) V V (Mu (oMt V VTSV - VT (fu) + Hof
VTSV=0
One immediate problem with this is that the constraint may be infeasible depending on the choice of Eg. Σ, or S: e.g. when - is positive definite. For this reason, Kleindessner al. (2023): Olfat and Aswani (2019) propose relaxations of the faimess constraints but provide no further discussions on its impact on statistical guarantees. On the contrary, our formulation always feasible without any need for relaxation, allowing us to consider rigorous definition of fair PCA (Definition 2) for the first time in fair PCA literature.
4 Statistical Viewpoint: PAFO-Learnabiliy of PCA
As all the distribution statistics (E.p....) are unknown, the learner, given some finite number of samples, must learn all of them and solve fair PCA. In supervised learning, such problem is often formalized in a PAC-learnability framework (Shalev-Schward and Ben-David, 2014). In the context of PAC-learnability for unsupervised learning settings, TV-learning, which is the task of learning distribution, has been mainly considered so far (Ananthakrishnan et al., 2021; Hopkins al., 2023). However, unlike TV-learning PCA; moreover, fair PCA has the fairness constraint Hy V = O to be satisfied. Inspired by the unsupervised PAC-learnability propose a new notion of learnability for fair PCA, called PAFO (Probably Approximately Fair and Optimal) learnability, as follows:
unnecessary learn the whole distribution in fair
well constrained PAC-learnability (Chamon and Ribeiro, 2020),
Definition (Projection Learner). A projection learner is a function that takes k 1 and d- dimensional samples as input and outputs a loading matrix V E St(d,
Definition (PAFO-Learraaiiiity of PCA). Let d, ki be integers such that 1 < k < and m d. We say that Fa C Pa x Pa (0, 1) is PAFO-learnable for PCA if there exists a function NF. (0, 1)3 + N and projection learner A satisfying the following:
For every Eo, Et, (0, 1) and (Do. D1, E Fa. when running A on N 2 NN, EF, 8) i.i.d. samples from D = pD1 + (1 Do of the form (a, w)), A returns V s.l., with probability at least - 8 (over the draws of the N samples),
tr (VTEV) 2 tr (v, - So.
[UVV S Et,
(5)
where U is as defined in Eqn. (2) and V. is any solution to Eqn. (4) (with prescribed k and m.).
Like in the usual PAC-learnability. Nr, is referred to as the sample complexity of fair PCA. Observe how the optimality is measured w.r.t the optimal solution of fair PCA, not the vanilla PCA. Also, the two conditions are not overlapping: vanilla PCA (overly) satisfies -o-otiiallity in explained variance but does not satisfy e--optimality in fairness, and vice versa for poorly chosen V St k) with col(V) C co
Algorithmic Viewpoint: Fair Streaming PCA
We now introduce new problem setting. streaming PCA. In this setting, the learner receives a stream of pairs (a,, x.) E {0, 1} x IR sequentially. Note that the sensitive attribute information aj is also available at each step; this is commonly assumed when considering fairness streaming setting (Bera et al., 2022; El Halabi et al., 2020). Precisely, we assume the following model of the data generation process: at each time-step& f, sensitive attribute chosen as a, ~ Bernoullipp), then the data is sampled from the corresponding sensitive group's 's conditional distribution Importantly, as done in previous streaming PCA literature (Mitliagkas et al., 2013), we assume that the learner has only ((dk) memory, where d is the data dimension and & is the target dimension. We can formally define the PAFO-Icaraailiiyy in this streaming setting:
Da,-
Definition say that Fa Pa x Pa x (0. PAFO-learnable for streaming PCA if the projection learner A for which Definition 2 holds uses only O(dk) memory for streaming data.

---

5.1 Our Algorithm: Fair Noisy Power Method (FNPM)
One only needs to estimate U to use the off-the-shelf streaming PCA algorithm. As U of size d x m, storing its estimate is no problem for the memory constraint as long as m Okk). Naturally, we proceed via a two-stage approach; first, estimate U sufficiently well, then with the fixed estimate of U, apply the noisy power method (Hardt and Price, 2014; Mitliagkas et al., 2013) for V.
For estimating U, one needs to estimate f and Pm. Estimating f can be done using the usual cumulative averaging. As for Pm. we can consider the two main approaches for streaming PCA: Oja's method (Huang et al., 2021; Oja, 1982; Oja and Karhunen, 1985) and noisy power method (NPM) (Hardt and Price, 2014; Mitliagkas et al., 2013). We first show that Oja's method is inap- plicable for our purpose, as may ignore some eigenvectors corresponding to negative (but large in magnitude) eigenvalues of S. For instance, if S -2e, -2eee + e2e] + 4eze] with e; being the standard basis vectors, then Oja's method with m = would yield [ea [ea] when we actually want (ei le]e For the same reason, simply shifting the eigenvalue spectrum by considering S + S| does not work. Thus we apply NPM for estimating Pm, in our case. which is known to converge as long the singular value gap of Pm. is large enough and norms of the noise matrices at each iterate are properly bounded (Balcan et al., 2016; Hardt and Price, 2014).
Algorithm 1: UnfairSubspace
Input: m. Block size b, Number of iterations T:
2 Output: A matrix Ò with orthonormal columns;
3 Wo QR, 1)dxm);
(m m, B(O), B() (0., Oz, 0,0);
Algorithm 2: Fair NPM
5 for E [T) do
1 Input: k. Block sizes B, b. Numbers of iterations T, T:
Receive {(a; x..) 33)) (t-
2 Output: Vy E St(d,, k));
7 foreach a E {0, 1} do
Compute (/2), m (a)
c(e) as Eqn. (6);
Ô < UnfairSubspace((, T);
// Algorithm 1
m (a)
Bio) M.0 m (a)
Blus
(
(o).
4 Vo + QR(NNO, 1)dxk);
B(a)+ - B(a)+ + +b² (();
for T E [T] do
10
V, + V,-1 -,0T-
W QR (0 -c(²)
11
Receive {(*,,,)) (-
1)8+1
12 f + ml (1) m :)
V, t B - 2. Vr:
13 x- f W.W.F.
V, + QR V. - UÚTV.):
14 1 2 = 0 then
10 return VT
15
U- = Wr
16 else
Ü WT
a T
17
18 return Ú
Description of the algorithms. The pseudocode of our algorithm is shown in Algorithms and 2.
The goal of Algorithm is to estimate U- = P... T in Eqn. (2) as accurately as possible. Lines
5-13 do the estimation of P., and g = =mp f: line 11 is the NPM find P... lines 12 and 13 the estimation of ff and respectively, and line 17 is the concatenation of the estimates of P... and g/l|ø/11 Especially at line 17, the algorithm determines whether to incorporate mean difference by checking g. which can be proved to be correct, i.e., With the estimated U from Algorithm 1, Algorithm 2 performs the usual NPM on Ht EII as in Eqn. (4). The memory complexity of Algorithm 2 is O (d max(m, k)), since we do not have to store all b or B data points at each time, and all the operations used can be implemented in manner that conforms to the memory limitation; the full pseudocodes are provided in Appendix B.
0 if and only if 9 = O with high probability.
At time step of Algorithm 1, for each E {0, 6:0) is the number of data points a 's such that a; = a: m, (a) is the term used for estimation of the group-wise sample mean of a "s C(a) is used for the group-wise sample second moment. Their forms are as follows and can be computed
5

---

incrementally in the streaming setup:
bt
m (a) bt
bt
((0)==
aa
(a)
oi
clao=
Σ
1a,=al
(a)
C,C;
W, 1-
bmb(t-1)+ 1)+1
smb(t- 1)+1 D2
(6)
where we the last two quantities to 0 when 6l() 0.
Note that as b(a) itself is random, this presents some technical challenges in the proofs of the theoretical guarantees. For instance, the above estimators for the mean and covariance are biased. Still, by properly using peeling argument and matrix concentration inequalities as well as perturbation theories (Golub and Loan, 2013; Tropp, 2015), could sufficiently bound their errors. Informally speaking, we show that line 11 corresponds to the noisy power method for the matrix S, which incurs the memory complexity ((d)).
5.2 Previous Approaches are not Suitable for Streaming Setup
All the existing approaches to fair PCA require the full knowledge of μ* po and Σ -g. or even the full data matrix X. Olfat and Aswani (2019) need f and S to formulate the convex matrix constraints for their semi-positive definite programming (SDP), which is then solved with commercial SDP solver; Lee et al. (2022) need X to compute the derivative of their maximum mean discrepancy (MMD) penalty term, which requires (dd) memory to compute kernel Gram matrices. One may hope that the PCA-type approach taken by Kleindessner et al. (2023) may be easily extendable to our streaming setting by just using the standard techniques (e.g.. using matrix-vector products) from streaming PCA (Mitliagkas et al., 2013). Indeed, they also propose similar relaxation of the covariance constraint, leading to a closed-form solution. However, their formulation is not memory- and, more importantly, is not applicable to streaming settings our formulation; see Appendix D for more discussions.
5.3 Extension Multiple Sensitive Groups/Attributes
So far, we have considered a single and binary-sensitive attribute for simplicity. Here, we briefly discuss extending our framework to multiple non-binary sensitive attributes. Suppose that there are é different attributes (e.g.. gender and race), and for each r E [4]. the r-th sensitive attribute has Ir groups (e.g., male, female, and non- con-binary: Igender 3 in this case). We first describe the new data generation process: at each time t, we obtain ((a1,). ... aa,)), zz). where for each Then, our formulation of fair PCA easily extends via one- one-versus-all all comparison approach. That is to say, for each r E [[], define
a,,t (pt.
Pr.g.) ) with Σ Pr.e
fr.a = E[x| a, = a] - E[x a, + a], Sra = E[xxT ar = a] - E E[xx=T a, + a). Denote the top-m, column basis of eigenspace of Sr,a by Pm..(6 (Sya). ). Then our notion of fair PCA
can be extended as follows: where d, k. m1, m, are given as d > k + 1 E my,
max tr( (v(VVVV) subject to col(V) c n n col ((mm, (Sra)) fr,a))+ (E(s))).s.)
(7)
VESt(d,))
Our algorithm can also be naturally adapted to this scenario via one-versus-all manner. In Appendix C, we provide the full pseudocode for the general case of multiple and non-binary sensitive attributes.
FNPM is a PAFO-Learning Algorithm
We now show that proposed eeemory-efficiiee algorithm, FNPM. is actually PAFO-lcarning algorithm in that with a certain sample complexity, it satisfies the definition of PAFO-learnability. The proof's of all the theoretical results stated here are deferred to Appendix E.
To use proper matrix concentration inequalities for our error term analysis, various streaming PCA literature adopt some assumption on the underlying data distribution, e.g., sub-Gaussianity (Bienstock et al., 2022; Jain et al., 2016; Yang et al., 2018). Throughout the paper and for our theoretical discussions, we consider a collection of distributions F, C Pa x Pa x (0. 1) satisfying the following assumptions to our data generation process in terms of the data point conditioned on the sensitive attribute and its cigenspectrum:

---

Assumption 1. Consider our data generation process a ~ Bernoullipp) and x | a ~ Da- There exists 0, V. MM, V. 9min 0, fmax E (gmin 00), and Pmii E (0, 0.5) such that the followings hold for any (Do: P1,)) E Fd: for {0, 1, Da E nSG(o),
P P|| ( + HaHt) - M =, EEa + HaHlll2 S V, Var (xx
a S VV
and
||9|12 = [Ppp Pm f fl12 E {0} U Imiu: fmax], llfll2 S fmax. and p E [pmin 1 - Pmiul-
Assumption 2. Fix m, E N. There exist Ampy AKye Km Kg E (0,00) such that for any (Do, 11. E Fa the followings hold:
Vm v Dn Kik
kk+1 AR,K Vm Km,vs and Kik KK
where V1 2 ... 2 Uu 2 0 and 11 2 2 Kd 2 0 are the singular values of S and y E respectively.
We start by establishing the sample complexity bounds of Algorithms and based on the conver- gence bound for NPM by Hardt and Price (2014). Recall that NPM is an algorithm for finding top-r eigenspace (in magnitude) of a symmetric (but not necessarily PSD) matrix A under random noise Z E ddd by update V2 f QR(AV, + Z.). We start by recalling their meta-sample complexity result for NPM, which we have slightly reformulated for our convenience:
E (0,1/2) and ô E (0,2e 2e 2d)a) where e is absolute constant." Let L, be the d X matrix, whose columns correspond to the top-r eigenvectors (in magnitude) of the symmetric (not necessarily PSD) matrix E Raxd, and let & 2 ... Ex 2 0 be the singular values of A. Assume that the noise matrices Zi
Lemma (Corollary 1.1 of Hardt and Price (2014)), Let 1 S
Rdxr satisfy
8(Er - Srt1)
Z 12 S c(Er Er+1)
and 51 S
111
(8)
2v
Then, after T = O Sorm log (1) steps of NPM, IV Ly 1l S e with probability at least Ex-Er+1
1 8.
First, we prove that the WT resulting from Algorithm 1 (NPM for the second moment gap) converges to the true value. We can view Algorithm I's updates as W, <- QR(SW,-1 Z,,),, where the noise matrix in this case is Z (C(2) c( SW,- t-1 and c(a) is as defined in Eqn. (6). The following lemma asserts that with large enough block size b, the error matrices are sufficiently bounded such that the NPM iterates converge:
Lemma 2. Let e, 5,6c E (0, 1). It is sufficient to choose the block size b in Algorithm I as
b= Ω V
dm log
1 log 1og a
log d Vpmin
M²
+
(9)
8
to make the following hold with probability at least 1 - 8:
8Am.y
5 Zr,1l22 I eDm.r and 5 P1 m P1.ll, S
Vt 2 1,
(10)
2v dm
where we recall that the columns of Pm are the top-m (in magnitude) orthonormal eigenvectors of S.
Let Ô be the final estimate of the true U outputted by Algorithm 1. For Algorithm 2, the noise matrix is Z,, == (mŞ IHEIH, V--1, where Σ, == B Σ, 2, is the sample covariance at time step of Algorithm 2. Similarly, with large enough block size B, we have the following lemma:
2 is norm-sub- norm-sub-Gaussian denoted as u if P EyI S 2c 202, We refer interested readers Jin al. (2019, Section 2) more discussions on norm-sub waa-ssuu--suuss Gaussianity. 'I depends polynomially only in the sub-Gaussian moment of the data distribution D; see Theorem 1.1 of Rudelson and Vershynin (2009).
7

---

Lemma Let e, E (0,1). Suppose that 1 sufficient to choose the block size B in Algorithm 2 as
Ille 1l2
S
Abe min 201
(12va))) 2v
c,
Then, it is
1 V2
dk
k
1
d
M2
log d
B -
A
82
log
5
log
+
V V2
8) 8
(11)
R.N
to make the following hold with probability at least 1 - 8:
ÖDR.
5 EDR,N and 5 Q
-
VT 2 1,
(12)
2v
where the columns of Qs is the top-k (in magnitude) orthonormal eigenvectors of nl E (We note that Qs is solution for Eqn. (4).)
Remark We emphasize that, regardless of the block size requirement in the above lemmas, all the operations can be implemented within o(d?) space requirement.
Combining the convergence results, we can prove the following PAFO-learaability guarantee in the memory-limiter streaming setting:
Theorem 1. Let d, m, k E N be fixed. Consider collection Fa Pa Pa (0,1) satisfying Assumptions I and 2. Then, Fa is PAFO-learnable for streaming PCA with FNPM, where the sufficient number of samples is given as NF, St, et, Ni + N2, with
Km,
V
dm
a
M2
}
N1 =
+
(Algorithm 1)
Pmin
A
82
Th
VAm,y
Punin Th
N₂ á KR,N (V V2)
dk:
k2V2
+ KR
(Algorithm 2)
E
(v,(V++V3)
where = - min Es:
ARin RV2 Cor
Aei vv
6 and a =
1
Pnin
Let us take a moment to digest the sample complexity in Theorem 1. The second term N2 is deter- mined by the E. -ottimaalyyy requirement in our PAFO-lcaraability Note that N₂ has no dependencies on fairness-related quantities such as εt, Pmin. and Am,e- On the other hand, the first term N₁ not only determined by the e:-fairness requirement, but also the co-otimallity of pursuing fairness; U, which encodes the unfair subspace needed to be nullified, is required to be accurately estimated optimality. This is clear in our formulation of fair PCA; in Eqn. (4), note how the optimal solution depends heavily Mr..
well. This is the "price"
impacts only the level of fairness but also the resulting solution's
We further elaborate on the dependencies of N1 on fairness-related quantities, namely Pmin and g. First, if Pmiin + 0, i.c., if one of the two groups is to infinity, and the lcarnability does not hold: this aligns with our intuition, as we need samples from both of the sensitive groups. Its dependency is also quite natural, as the minimum expected number of samples from either group depends linearly on Paii Also, when * 0, Nı has an additional additive term scaling linearly with ي This is because when g * must explicitly account for the approximation error of Tlll
sampled, then the sample complexity tends
9mm due to the QR decomposition at the end of Algorithm 1.
7
Experiments on World Datasets
The code for all experiments is available at a wtthhtt.cm//tnmeello/aaaa-----ee -pca.
7.1 CelebA Dataset
evaluate the efficacy of our proposed FNPM on the CelebA dataset (Liu et al., 2015b). It has been considered by Kleindessner et al. (2023) to show the superior efficiency of their fair PCA algorithm compared to previous approaches (Lee al., 2022; Olfat and Aswani, 2019; Ravfogel al., 2022a). However, even in Kleindessner al. (2023), the images were resized and gcey-saaled,

---

Original
Fair NPM
Figure 1: Experimental results on full-resolution CelebA dataset. Original image v.s. FNPM output. (Sensitive attribute: "Eyeglasses")
reducing the dimension from the original 218 178==118888,04 to 80x80=6,400, Indeed, for a modest- sized computer, it is impossible to load all 162,770 original images in training set the memory at once, while they require full dataset to run each step of their algorithm. Here, we use the original resolution, full-color CelebA dataset. We implement our FNPM using Python JAX NumPy Module (Bradbury et al., 2023; Harris et al., 2020) and Pytorch (Paszke et al., 2017). All experiments performed on Apple 2020 Mac mini MI with 16GB RAM.
Although CelebA is not streaming in nature, we intend to show that transforming to one and using memory-efficient approach allow us to scale up fair PCA. Since there are three channels of color, we run FNPM channel-wise but in parallel as usual in vision tasks (Priorov et al., 2013). For each channel of colors, project the data onto k 1000-dimensional subspace while nullifying leading eigenvectors of covariance difference.
The resulting images are displayed in Figure 1. Here, we consider 'Eyeglasses' as a sensitive attribute to divide groups. We adopt the predefined valn-validation split and run our algorithm only on the training set for 5 iterations with block sizes of b = B 32, 000. Then, using the output V of FNPM, we project images selected from the validation set. We observe that have images of faces wearing colorful glasses by nullifying some of the leading eigenvectors of covariance difference. For the images originally with sunglas aunglasses, their glasses get blurred, and "virtual"" eyes are added to them. provide more results on the other attributes and ablation studies varying m and b in Appendix F.2.
7.2 UCI Datasets
For the sake of completeness, we conduct a quantitative evaluation of our algorithm on UCI datasets (Adult Income, COMPAS, German Credit) and compare it with six previous works (Kleindessner et al., 2023; Lee et al., 2022: Olfat and Aswani, 2019; Ravfogel et al., 2020, 2022a; Samadi et al., 2018). The results for the Adult Income dataset are shown in Table 1. We assess several variants of our methods: in Table "mean" when we match the means and not second moments, "FNPM" is when solve our "Null It Out" formulation of fair PCA (Eqn. (4)) via offline ggen-decompooition. In the table, we report the explained variance (% Var), representation fairness measured by maximum mean discrepancy (MMD*), downstream task accuracy (%Acc), and downstream task fairness in demographic parity (% App). The result showcases that method yields competitive quantitative performance even for the common tabular datasets while being much more memory efficient. We defer the full results for other UCI datasets Appendix F.3.
Algorithm 2 with block size of full-batch, and "offline" is when directly
8 Other Related Works
Fairness in ML. There are largely two directions in the literature of algorithmic fairness. One direction to propose suitable and meaningful fairness definition (Dwork et al., 2012: Feldman et al., 2015; Hardt et al., 2016). The other direction is to develop efficien/ fair algorithms, although often the fairness constraint forces the algorithm be much more inefficient than its unfair counterpart, or it calls for need for completely new algorithmic approach. There are also different ways of

---

Table 1: Dataset Adult Income [feature dim=102, #(train data)=311655), k
%eAc((t)
ApP(l)
Method
% Var((1)
MMD*(L)
kernel SVM
PCA
(.88
0.374:0.00m
82.4(0.2)
0.19/o.01)
Olfat and Aswani (2019) (0.1)
Memory Out
Olfat and Aswani (2019) (0.0)
Memory Out
Lee ct al. (2022) (1c-3)
(.68(o.11)
(.0go.a)
80.34(0.24)
0.05(o.01)
Lee et al. (2022) (1e-6)
(..2(
0.0
79.41
0.02(o.01)
Kleindessner al. (2023) (mean)
1.74(0.11)
0.002(o.0)
80.6(0.2)
(o.01)
Kleindessner et al. (2023) (0.85)
(o.17)
0.001 (0.001)
75.52
0.0
Kleindessner ct al. (2023) (0.5)
(o.3
(.0
(0.38
0.0
Kleindessner ct al. (2023) (kernel)
Takes too long time
Ravfogel al. (2020)
1.91
0.001 (0.001)
75.67
0.0
Ravfogel et al. (2022a)
1991
(o.03)
75.59(u.34)
0.0
Samadi al. (2018)
N/A
N/A
82.63
0.15(u.01)
Ours (offline, mean)
(.74(..11)
0.002(0.0)
80.6(0.2)
0.07
Ours (FNPM, mean)
1.74
0.002(0.0)
80.6(0.2)
0.07
Ours (offline. m=15)
4.04(0.14)
0.001 (0.001)
(0.5))
0.0
Ours (FNPM, m=15)
4.07 (o.13)
0.001
(5.54().26)
(.0
Ours (offline, m=50)
(o.3)
0.0
75.38
0.0
Ours (PNPM, m=50)
2.64(0.08)
0.0
75.44(0.21)
0.0
imposing fairness in an ML pipeline, such learning fair pre-processing (Biswas and Rajan, 2021), fair in in-processing (Roh et al., 2021; Wan et al., 2023; Zafar et al., 2019), and more. The reader is encouraged to check Barocas et al. (2019) for more comprehensive treatment of this subject.
Fair online/streaming Learning. Bechavod et al. (2020); Gillen et al. (2018) study individual fairness in online learning in a learning theoretic framework, even when the underlying metric is unavailable. Stemming from the concept of fair clustering as proposed in Chierichetti et al. (2017), Bera et al. (2022); Schmidt et al. (2020) study imposing demographic parity on clustering in the streaming setting. Such fairness has been considered in various other streaming problems such as online selection (Correa et al., 2021), streaming submodular optimization (El Halabi al., 2020), and diversity maximization (Wang et al., 2022). Quite surprisingly, demographic parity (or any other concept of fairness) has never been considered in the setting of streaming PCA.
Streaming PCA. Without the fairness constraint, streaming PCA has been studied much from statistics and the machine learning community. Two prominent algorithms have been studied; the noisy power method (Mitliagkas et al., 2013) and Oja's method (Oja, 1982). Much work has been done in improving the theoretical guarantees of streaming PCA (Balcan et al., 2016; Hardt and Price, 2014; Jain al., 2016; Liang, 2023), improving the algorithm itself (Xu, 2023; Yun, 2018), or extending the guarantees to various different settings (Balzano et al., 2018; Bienstock et al., 2022: Kumar and Sarkar, 2023). Memory-limited, streaming versions of somewhat related problems, such as community detection (Yun et al., 2014) and low-rank matrix completion (Yun et al., 2015). have been tackled as well using similar spectral techniques as PCA (e.g.. power method). However, to the best of our knowledge, fairness (regardless of the definition) has never been considered in this context of streaming PCA, which we tackle this work and which we believe of great importance.
Conclusion
In this work, we tackled the outstanding problems of the existing fair PCA literature. From the theoretical side, we illustrated a new formulation of fair PCA based on the "Null It Out" approach and then provided a novel statistical framework called PAFO-learabbility of fair PCA. From the practical side, we addressed the memory -imited scenarios by proposing a new problem setting called fair streaming PCA and a memory-efficiae
two-stage algorithm called FNPM. Based on these, we established a statistical guarantee that our algorithm achieves the PAFO-learaaiility for fair streaming PCA. Lastly, we ran experiments on the CelebA and UCI datasets to certify the scalability of our method.
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments and suggestions. We also thank Gwangsu Kim (Jeonbuk National University) for the helpful discussions in the initial phase of the research. This work was supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grants funded by the Korean governmen((MSIT) NN.220190-00077 Artificial Intelligence Graduate School Program(KAIST), No. 2022-0-00188 144, Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy on Ethics).
References
Hervé Abdi and Lynne Williams. Principal component analysis. WIREs Computational Statistics, 2(4):433 459, 2010.
Nivasini Anamthakrishnan. Shai Ben-David, Tosca Lechner, and Ruth Umnrr. Identifying regions of trusted predictions. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 27-30 Jul 2021.
PMLR,
Maria-Florine Balcan, Simon Shaolci Du, Yining Wang, and Adams Wei Yu. An Improved Gap- Dependency Analysis of the Noisy Power Method. In 29th Annual Conference Learning Theory, volume 49 Proceedings of Machine Learning Research, pages 284-309, Columbia University, New York, New York, USA, 23-26 26 Jun 2016. PMLR.
Laura Balzano, Yuejic Chi, and Yue M. Lu. Streaming PCA and Subspace Tracking: The Missing Data Case. Proceedings of the IEEE, 106(8): 2018.
Solon Barocas and Andrew Selbst. Big Data's Disparate Impact. 104 California Law Review 671, 2016.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limitations and Opportunities. fairmlbook.org org, 2019.
Yahav Bechavod, Christopher Jung, and Steven 7. Wu. Metric-Free Individual Fairness in Online Learning- In Advances in Neural Information Processing Systems, volume 33, pages 1 11214-12225. Curran Associates, Inc., 2020.
Suman K. Bera, Syamantak Das, Sainyam Galhotra, and Sagar Sudhir Kale. Fair K-Center Clustering in MapReduce and Streaming Settings. In Proceedingy of the ACM Web Conference 2022, WWW '22, page 1414-1422, New York, NY, USA, 2022. Association for Computing Machinery.
Daniel Bienstock, Minchan Jeong, Apurv Shukla, and Se- Young Yun. Robust Streaming PCA. In Advances in Neural Information Processing Systems, volume 35, pages 4231-4243 Curran Associates, Inc., 2022.
Sumon Biswas and Hridesh Rajan. Fair Preprocessing: Towards Understanding Compositional Fairness of Data Transformers in Machine Learning Pipeline. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/SE 2021, page 981-993, New York, NY, USA, 2021. Association for Computing Machinery.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPP programs, 2023. URL
bttp:///ithnnn com/ google/jax.
Luiz Chamon and Alejandro Ribeiro. Probably Approximately Correct Constrained Learning. In Advances in Neural Information Processing Systems, volume 33, pages 16722-16735. Curran Associates, Inc., 2020.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair Clustering Through Fairlets. In Advances Neural Information Processing Systems, volume 30, pages 5036-5044. Curran Associates, Inc., 2017.

---

Jose Correa, Andres Cristi, Paul Duetting, and Ashkan Norouzi-Fasd Fairnsss and Bias in Online Selection. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2112-2121. PMLR, 18-24 Jul 2021.
Chandler Davis and W. M. Kahan. Some new bounds on perturbation of subspaces. Bulletin of the American Mathematical Sociery, 75(4):863 868, 1969.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through Awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 12, page 214-226, New York, NY, USA, 2012. Association for Computing Machinery.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, 1:211-218, 1936.
Marwa EI Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub M Tarnawski. Fairness in Streaming Submodular Maximization: Algorithms and Hardness. In Advances in Neural Information Processing Systems, volume 33, pages 13609-13622. Curran Associates, Inc., 2020.
Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger. and Suresh Venkatasubra- manian. Certifying and Removing Disparate Impact. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, page 259-268, New York, NY, USA, 2015. Association for Computing Machinery.
Mina Ghashami, Daniel J. Perry, and Jeff Phillips. Streaming Kernel Principal Component Analysis. In Proceedings of the 19th International Conference on Artificial Intelligence and Statisties, volume 51 of Proceedings of Machine Learning Research, pages 1365-1374, Cadiz, Spain, 09-11 May 2016. PMLR.
Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. Online Learning with an Unknown Fairness Metric. In Advances in Neural Information Processing Systems, volume 31, pages 2605-2614. Curran Associates, Inc., 2018
Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, 4 edition, 2013.
Moritz Hardt and Eric Price. The Noisy Power Method: Meta Algorithm with Applications. In Advances in Neural Information Processing Systems, volume 27, pages 2861-2869. Curran Associates, Inc., 2014.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of Opportunity in Supervised Learning, In Ad- vances in Neural Information Processing Systems, volume 29, pages 3323-3331. Curran Associates, Inc., 2016.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Marchat, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357 362, September 2020.
Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Do PAC-Leamers Learn the Marginal Distribution? arXiv preprint arXiv:2332.00228, 2023.
Harold Hotelling. Analysis of complex of statistical variables into principal components. Journal of Educational Psychology, 24(6):417-411 1933.
De Huang, Jonathan Niles Weed, and Rachel Ward. Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2463-2498. PMLR, 15-19 Aug 2021.
12

---

Prateek Jain, Chi Jin, Sham M. Kakade. Praneeth Netrapalli, and Aaron Sidford. Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 114--1164 Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm arXiv preprint arXiv:1902.03736. 2019.
Richard A. Johnson and Dean W. Wichern. Applied Multivariate Statistical Analysis. Pearson, edition, 2008
Ian I. Jolliffe and Jorge Cadima. Principal component analysis: a review and recent developments. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 374(2065), 2016.
Mohammad Mahdi Kamani, Farzin Haddadpour, Rana Forsati, and Mehrdad Mahdavi. Efficient fair principal component analysis. Machine Learning, 111(10):371-3302, 2022.
Kirchner, J. Larson, S. Mattu, and J. Angwin. Machine bias. ProPublica, 2016.
René F. Kizileec and Hansol Lee. Algorithmic Fairness in Education. arXiv preprint arXiv:2007.05444, 2021.
Matthaus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. Guarantees for Spectral Clustering with Faimess Constraints. In Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 3458-3467.
PMLR, 09-15 Jun 2019.
Matthäus Kleindessner, Michele Donini, Chris Russell, and Muhammad Bilal Zafar. Efficient fair PCA for fair representation learning. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 5250-5270. PMLR, 25-27 Apr 2023.
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled Cubic Regularization for Non-convex Opti- mization. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1895-1904. PMLR, 06-11 Aug 2017.
Syamantak Kumar and Purnamrita Sarkar. Streaming PCA for Markovian Data. arXiv preprint
arXiv:2305.02456, 2023.
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without Demographics through Adversarially Reweighted Learning. In Advances in Neural Information Processing Systems, volume 33, pages 728-740 Curran Associates, Inc., 2020.
Junghyun Lee, Gwangsu Kim, Mahbod Olfat, Mark Hasegawa-Johnson and Chang D. Yoo. Fast and Efficient MMD-Based Fair PCA via Optimization over Stiefel Manifold. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 7363-7371. 1, Jun. 2022.
Xun Li, Dongsheng Chen, Weipan Xu, Haohui Chen, Junjun Li, and Fan Mo. Explainable dimension- ality reduction (XDR) to unbox AI 'black box' models: study of AI perspectives on the ethnic styles of village dwellings. Humanities and Social Sciences Communications, 10(1):35, Jan 2023,
Xin Liang. On the optimality of the Oja's 's algorithm for online PCA. Statistics and Computing, 33(3): 62, Mar 2023.
Edo Liberty. Simple and Deterministic Matrix Sketching. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '13, page 581-588, New York, NY, USA, 2013. Association for Computing Machinery.
Ziqi Liu, Yu-Xiang Wang, and Alexander Smola. Fast Differentially Private Matrix Factorization. In Proceedings of the 9th ACM Conference on Recommender Systems, RecSys '15, page 171-178, New York, NY, USA, 2015a. Association for Computing Machinery.
13

---

Ziwei Liu, Ping Luo, Xiaogang Wang. and Xiaoou Tang. Deep Learning Face Attributes in the Wild.
In 2015 IEEE International Conference on Computer Vision (ICCV), pages 3730-3738, 2015b.
Albert W. Marshall, Ingram Olkin, and Barry C. Amold. Inequalities: Theory of Majorization and Its Applications. Springer Series in Statistics. Springer New York, edition, 2011.
Ninarch Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A Survey on Bias and Fairness Machine Learning. ACM Computing Surveys, 54(6), jul 2021.
L. Mirsky, A trace inequality of John von Neumann. Monatshefte für Mathematik, 79(4):003-366 Dec 1975.
Ioannis Mitliagkas, Constantine Caramanis, and Prateek Jain, Memory Limited, Streaming PCA. In Advances in Neural Information Processing Systems, volume 26, pages 2886-2894. Curran Associates, Inc., 2013.
Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of Mathematical Biology, 15(3):267-273, Nov 1982.
Erkki Oja and Juha Karhunen. On Stochastic Approximation of the Eigenvectors and Eigenvalues of the Expectation of Random Matrix. Journal of Mathematical Analysis and Applications, 106: 69-84, 1985.
Matt Olfat and Anil Aswani. Convex Formulations for Fair Principal Component Analysis. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 663-670, Jul. 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS 2017 Workshop Autodiff, 2017.
Karl Pearson. Liii lines and planes of closest fit systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(1 2(11):559-572, 1901.
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global Vectors for Word Representation. In Proceedings of the 2014 Conference on Empirical Methods Natural Lan- guage Processing (EMNLP), pages 1532 1543, Doha, Qatar, October 2014. Association for Computational Linguistics.
Andrey Priorov, Kirill Tumanov, Vladimir Volokhov, Evgeny Sergeev, and Ivan Mochalov. Applica- tions of image filtration based on principal component analysis and nonlocal image processing. IAENG International Journal of Computer Science, 40(2):62-80, 2013.
Shauli Ravfogel, Yanai Elazar, Hila Gonen, Michael Twiton, and Yoav Goldberg. Null It Out: Guarding Protected Attributes by Iterative Nullspace Projection. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7237-7256, Online, July 2020. Association for Computational Linguistics.
Shauli Ravfogel, Michael Twiton, Yoav Goldberg, and Ryan D Cotterell. Linear Adversarial Concept Erasure. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 18400-18421. PMLR, 17-23 Jul 2022a.
Shauli Ravfogel, Francisco Vargas. Yoav Goldberg, and Ryan Cotterell. Adversarial Concept Erasure in Kernel Space. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 6034-6055. Abu Dhabi, United Arab Emirates, December 2022b. Association for Computational Linguistics.
Yuji Roh, Kangwook Lee, Steven Fuijong Whang, and Changho Suh. FairBatch: Batch Selection for Model Fairness. In International Conference on Learning Representations, 2021.
Mark Rudelson and Roman Vershynin. Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics, 62(12):1707-173)) 2009.
14

---

Samira Samadi, Uthaipon Tantipongpipat, Jamie H Morgenstern Mohit Singh, and Santosh Vempala. The Price of Fair PCA: One Extra dimension. In Advances in Neural Information Processing Systems, volume 31, pages 10999-110100 Curran Associates, Inc., 2018.
Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means. In Approximation and Online Algorithms, pages 232-251, Cham, 2020. Springer International Publishing.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear Component Analysis as Kernel Eigenvalue Problem. Neural Computation, 10(5):1299-1319 07 1998.
and S. Ben-David, Understanding Machine Learning: From Theory Algorithms. S. Cambridge University Press, 2014.
Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh, Jamie H Morgenstern, and Santosh Vempala. Multi-Criteria Dimensionality Reduction with Applications to Fairness. In Advances in Neural Information Processing Systems, volume 32, pages 15161-15171. Curran Associates, Inc., 2019.
Erico Tjoa and Cuntai Guan. A Survey on Explainable Artificial Intelligence (XAI): Toward Medical
XAL IEEE Transactions on Neural Networks and Learning Systems, 32(11))4793-481 2021.
Joel A. Tropp. An Introduction to Matrix Concentration Inequalities. Foundations and Trends@) in
Machine Learning, 8(1-2):1-230, 2015.
Enayat Ullah, Poorya Mianjy, Teodor Vanislavov Marinov, and Raman Arora. Streaming Kernel PCA with (vv)) Random Features. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
John von Neumann. Some Matrix-Inequalities and Metrization of Matrix-Space. Tomsk University Review, 1:286-300 1937.
Hieu Vu, Toan Tran, Man-Chung Yue, and Viet Anh Nguyen. Distributionally Robust Fair Principal Components via Geodesie Descents, In International Conference on Learning Representations. 2022.
Mingyang Wan, Daochen Zha, Ninghao Liu, and Na Zou. In-Processing Modeling Techniques for Machine Learning Fairness: A Survey. ACM Transactions on Knowledge Discovery from Data, 17 (3), mar 2023.
Chuang Wang and Yue M. Lu. Online learning for sparse PCA in high dimensions: Exact dynamics and phase transitions. In 2016 IEEE Information Theory Workshop (ITW), pages 186-190, 2016.
Ji Wang, Ding Lu, Ian Davidson, and Zhaojun Bai. Scalable Spectral Clustering with Group Fairness Constraints. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 6613 6629. PMLR, 25 Apr 2023.
Yanhao Wang, Francesco Fabbri, and Michael Mathioudakis. Streaming Algorithms for Diversity Maximization with Fairness Constraints. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 41-53, Los Alamitos, CA, USA, 2022. IEEE Computer Society.
Zhiqiang Xu. On the Accelerated Noise-Tolerant Power Method. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 7147-7175. PMLR, 25-27 Apr 2023.
Zhiqiang Xu and Ping Li. Faster Noisy Power Method. In Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 1 1138-18 1164. PMLR, 29 Mar-01 Apr 2022.
Puyudi Yang, Cho-Jui Hsich, and Jane-Ling Wang. History PCA: A new algorithm for streaming PCA. arXiv preprint 1=Xiv:8802.054477 2018
Wenzhuo Yang and Huan Xu. Streaming Sparse Principal Component Analysis. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 494-503, Lille, France, 07-09 Jul 2015. PMLR.
15

---

Se- Young Yun. Noisy Power Method with Grassmann Average. In 2018 IEEE International Conference on Big Data and Smart Computing (BigComp), pages 709-712, 2018.
Se-You Se-Young Yun, Mare Lelarge, and Alexandre Proutière. Streaming, Memory Limited Algorithms for Community Detection. In Advances in Neural Information Processing Systems, volume 27, pages 3167-3175. Curran Associates, Inc., 2014.
Se- Young Yun, Marc Lelarge, and Alexandre Proutière. Fast and Memory Optimal Low-Rank Matrix Approximation. In Advances in Neural Information Processing Systems, volume 28, pages 3166-3185, Curran Associates, Inc., 2015.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. Faireess Constraints: A Flexible Approach for Fair Classification Journal of Machine Learning Research, 20(75):1-42, 2019.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning Fair Representa- tions. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 325-333, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Tianxiang Zhao, Enyan Dai, Kai Shu, and Suhang Wang. Towards Fair Classifiers Without Sensitive Attributes: Exploring Biases in Related Features. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM '22, page 4433-144, New York, NY, USA, 2022. Association for Computing Machinery.
16

---

Contents
Introduction
2
Preliminaries
3
An Alternative Approach to Fair PCA
3.1 "Null It Out" Formulation of Fair PCA
3.2 An Explicit Characterization for Solution of Fair PCA
................................
3.3
Comparison to the Existing Covariance Matching Constraint
4
Statistical Viewpoint: PAFO-I.carabbility of PCA
5
Algorithmic Viewpoint: Fair Streaming PCA
5.1
Our Algorithm: Fair Noisy Power Method (FNPM)
5.2
Previous Approaches are not Suitable for Streaming
................................
5.3
Extension to Multiple Sensitive Groups/Attributes..
6
6
FNPM a PAFO-L.carning Algorithm
7
Experiments on RorldWorld Datasets
7.1
CelebA Dataset
7.2
UCI Datasets
Other Related Works
9
Conclusion
10
A Broader Impacts, Limitations, and Future Directions
19
A.1 Broader Impacts
19
A.2 Limitations and Future Directions
19
B Full Pseudocodes of Algorithms and 2 for Fair "Streaming" PCA
21
C Extension of Algorithms 3 to Multiple and Non-binary Attributes
22
More Detailed Comparison to Kleindessner et al. (2023)
23
D.1 Their Approach
23
D.2 Unsuitability for the Streaming Setting
23
Proof's of Lemma 2, 3, and Theorem
25
E.I Notations and Assumptions
25
E,2 Matrix/Vector Concentration Inequalities
26
E,3 Proof of Lemma Bounding Error in Second Moment Gap
26
E.4 Proof of Lemma 3 Bounding the Final Error
28

---

E.5
Bounding the Estimation Error of Mean Difference
30
E,6
Proof of Theorem
Sample Complexity for PAFO-learability
................................
31
More Experiments
36
F.1
Synthetic Example
36
F2 Additional Results on CelebA Dataset
36
E3 Full Results on UCI Dataset
36
18

---

Appendix
A Broader Impacts, Limitations, and Future Directions
A.1 Broader Impacts
This work proposes dimensionality reduction method that addresses memory efficiency and fairness while providing a statistical guarantee. By identifying and nullifying the "unfair direction" inherent in the data distribution, we offer alternative approach to fair PCA. We anticipate that our approach will motivate researchers to explore other dimensionality reduction techniques (e.g,, auto-encoder) with faimeess constraints. Significantly, our contribution includes a rigorous theoretical framework, PAFO learnability, which enables sample complexity analysis of fair PCA. We envision the potential for theory to be further generalized to broader contexts, including alternative definitions of fairness and optimality of different algorithms for fair machine learning.
On the application side, the memory efficiency of our method can facilitate the scalability of fair PCA, making it viable for processing high-dimensional datasets, even in scenarios where data points arrive in streaming fashion. One possible application of our approach is data pre-/post- processing to alleviate unfairness, such as generating fair word embeddings by eliminating sensitive attribute information through orthogonal projection. For more detailed discussions potential future directions, please refer to below.
A.2 Limitations and Future Directions
Here, we list some of our work's limitations and possible extensions/future directions.
Individual Fairness for PCA. Our definition of fairness in PCA only covers group faireess via fair presentation learning, which was also the case for the prior works (Kleindessner et al., 2023; Lee et al., 2022; Olfat and Aswani, 2019). None of the works, including ours, have yet to consider the notion of individual fairness (Dwork et al., 2012) in the context of PCA, for which we do not have a definitive answer.
Knowledge sensitive attribute. Our framework requires the full knowledge of the sensitive attribute for all data points æ's, which was also the case for all the previous works (Kleindessner et al., 2023; Lee et al., 2022; Olfat and Aswani, 2019). But, the assumption of such knowledge may not be feasible in the real world due privacy or legal reasons (Lahoti et al., 2020; Zhao et al., 2022), or even just due to some extrinsic noises. Considering the case where the dataset may lack sensitive attributes for some all of the data points is important future direction.
Making the algorithm anytime. In our formulation of fair PCA, our algorithm is two-phase, with the first phase as a "burn-in" period for estimating the unfair subspace. Thus, it is not anytime algorithm in that if the algorithm stops whilst in the first phase, then the resulting V is random and completely uninformative. Designing an anytime variant of our algorithm is an important future direction. One possible way to achieve that is to consider other streaming PCA algorithms such as Oja's method (Oja and Karhunen, 1985) accelerated NPM (Xu, 2023; Xu and Li, 2022).
Improving gap dependence. Our algorithm's 's current sample complexity analysis relies on the analysis of NPM by Hardt and Price (2014), which relies on the immediate singular value gap. σ 0 Balcan et al. (2016) showed that considering greater iteration rank 2 k, i.e. by considering optimization variable of greater size, leads better gap dependency: from o oK+1 to a gt11. However, this is incompatible with our current definition of MAFO-learnabiliy (Definition 2) because with greater iteration rank, the solution V which the explained variance should be compared against is not clear. The problem is that the sample complexity guarantee of Balcan et al. (2016); Hardt and Price (2014) derived terms of the sine angle between the top k-eigenspace of the true covariance and the estimated g-dimensional subspace. Clearing this up would allow for a better theoretical guarantee in sample complexity and thus an important future direction.
19

---

Kernelizing our framework Kernel PCA (Schölkopf et al., 1998) is cornerstone in modern machine learning that has lent itself to be an inspiration many applications, both theory and practice-wise. Unlike previous fair PCA works (Kleindessner et al., 2023; Olfat and Aswani, 2019), in which the authors provided kernelized version of their fair PCA algorithm, both our statistical framework and memory-efficien algorithm for streaming setting do not readily extend to the kernelized version. Algorithmically, to tackle the streaming setting, one may take inspiration from streaming kernel PCA (Ghashami et al., 2016; Ullah al., 2018), which was in turn inspired by matrix sketching (Liberty, 2013).
Extending to other settings. In similar spirit, extending formulation of fair PCA other streaming settings such as sparse (Wang and Lu, 2016; Yang and Xu, 2015), nonstationary (Bienstock et al., 2022), or even distributionally robust settings (Vu et al., 2022) would also be interesting.
More experiments Last but not least, we' ve only performed experiments on synthetic, CelebA, and UCI datasets. It would be interesting to try framework (either the statistical formulation, the streaming setting, or both) on datasets from other domains, such as NLP and graphs. GloVe vectors (Pennington et al., 2014) has been used benchmark in a similar task called "concept erasure" (Ravfogel et al., 2020, 2022b); group fairness in spectral clustering of graphs has been studied as well (Kleindessner al., 2019; Wang al., 2023).
20

---

B Full Pseudocodes of Algorithms 1 and 2 for Fair "Streaming" PCA
Throughout the appendices, from hereon, we will refer our algorithms by Algorithms 3 and instead of Algorithms 1 and 2.
Algorithm 3: UnfairSubspace (= Algorithm 1)
Input: m, Block size b, Number of iterations
Output: A matrix Ü with orthonormal columns;
Wo t QR, 1)dxm);
(m("), ml) B(O), B()) + (0,, Oa, 0)0);
for f [T) do
(b(0) ((") - (0.0);
(m.)) (0) m, (1) (0) (
(1) (0a, Ou Odxms Odxm);
for E b do
Receive (a, x) (a(1-1)6+2: (0
bl() (a) +1;
10
m, (a) - mi
(a)
11
+ x;
cl + c(a) + x 1i
12
foreach E {0, 1 do
14
if 1 > 0 then
m, (a)
(0)
m
0
(a)
16
m (n)
Blos
m (a)
(a)
17
B(o) +1
Biat
46
m
B B(a) ((),
18
W. QR (C C(U));
f
m 1) m
g 4 WT W.F.
22 if
= 0 then
U WT
24 else
Ú
WT
1
return
Algorithm 4: Fair NPM (= Algorithm 2)
Input: d, k. Block sizes B, b, Numbers of iterations T, T; 2 Output: Vy E St(d, k);;
3 Ò + UnfairSubspacce(,17
Vo 10)
for 7 E do do
V. + V,-1 ÚŪIV,-I:
C 0axki
8
j [B] do
Receive (+, a)
(+, (1r-1)8++)
10
C- C B .. V+:
V - QR Cc C -Ú0-)
11
return VT
21

---

C Extension of Algorithms 3 to Multiple and Non-binary Attributes
We remark that Algorithm 3 special case of the pseudocode below. By applying Algorithm after applying this algorithm, we can handle the multiple non-binary attribute case and approximately and memory-efficientl solve the extended notion of fair PCA elaborated in Section 5.3.
Algorithm 5: Taraiiruubapacc_xxeeeeeee
Input: d, m me, Block size 6, Number of iterations T';
2 Output: A matrix Ü with orthonormal columns;
for r E [e] do
for a E [gr] do
W W (r.0) (0, 1)uxmr);
(r...i)) m (na,outt) B(na)) (0d, Oz, 0)
for f [T) do Receive (((a),)
ae.s), (;)] 160
for r E [4] do
for E [ do
((re)) Eie b [ar.
11
(r.a) + B(r.a) + bl (ma))
12
((a)) > then
13
m, (nj,,n)
1
2 bt bi- 1)+1 10
14
((a)
C (na.in)
Σne 2i= 1)+1 =a W (na). 6-1
16
else
m (na.in) c(riaii)) + (0d, Odxm..)
17
18
if by
(a) b then (r,a,out)
b b-b(n) Ene 2i=b(t-1)- 1)-1 f0
19
c (na,oout)
b-b(n) E 2i=b((-1)-1 [nne a w (na)) (na), 6-1
20
21
else
mmg (r,a,out)
((ra.out) - (0,s, Oáxm,)
22
(,a,in)
Blou) m(aa)
17)) m (ra
(5a)
(raa.in)
23
m
Boy m,
m (na,out)
[t-1)b +p
m (na,out)
86 Blay m (r,,,ut))
b ((a)
24
Bia)
w (naa)
QR (Clraaju) cf c(rraoou)):
25
26
for r E [$] do
27
for a E [gr] do
f(nna m
(na.in)
m. (na,
28
29 Ú QR (W
w ((o))))
f(1.1) ... p(eeod))
return Ū
22

---

D More Detailed Comparison to Kleindessner et al. (2023)
D.I Their Approach
Kleindessner et al. (2023) considered the following formulation of fair PCA: max tr(vTXIXV), subject to fTV = A (T Σn) V 0,
(13)
VESud,A)
and proposed a reasonable approximation of the covariance constraint, which we briefly describe here. Let us write S' = Σ Ey for brevity. As implicitly assumed in Kleindessner al. (2023), let us assume that f * 0. The mean constraint is dealt with first. Denoting U, E St(d, d - 1) to be the matrix whose columns form basis (d - 1) dimennniional nullspace of f. the mean constraint is satisfied if and only if V is of the form U with U & (t(d - 1, k) as the intermediate optimization variable. With this first reparametrization, the optimization now becomes
max (E
((UTU]XIXU;U) subject to UTUSSUJU = =0
(14)
which now has only the covariance constraint.
To deal with the possible infeasibility of the covariance constraint, Kleindessner (2023) proposed the following approach: letting M E St(d - 1,() be the matrix whose columns are the I smallest eigenvectors of U (in magnitude), U only needs nullify the eigenspace spanned by the
remaining d 1-1 eigenvectors. To see which terms are ignored with the relaxation, let > o/''v'" be the eigenvalue decomposition of U S with 141 2 14 2 ... l.all 2 0. This approach essentially ignores the constraint U E,U = O, where
d-1 Eyooo! Yo'e i=d-1
E = S. UJSU
(15)
The number (k..... 1} controls how much the group-conditional covariances will be equalized; smaller means that the covariance constraint is enforced more stringently and vice versa. Ultimately, the learner can control I as hyperparameter fairness and the explained variance. Moreover, if lg 's are negligible for all i 2 d - - L, then MJ.s: A As 0, and the relaxation becomes tighter.
create a trade-off between
As any U of the form M A satisfies the relaxed covariance constraint, a second reparameterizatioo
in terms of the new optimization variable E St(1, k) gives us
max (ESt(LA)
(16)
which can be solved via the standard SVD-based approach for vanilla PCA. Then, the final solution is obtained as V M U,A".
D.2 Unsuitability for the Streaming Setting
In Section 5.2, we provided a rough overview of why existing approaches fair PCA (Kleindessner et al., 2023; Lee et al., 2022; Olfat and Aswani, 2019) are not amenable to our streaming setting. Especially as the approach of Kleindessner al. (2023) (described above) is almost like PCA, one may wonder if standard techniques used in streaming PCA (Mitliagkas et al., 2013) can be used. Here, we argue in detail why that is not the case, which in sharp contrast to our approach and our reformulation of fair PCA that led to memory-efficient fair streaming PCA algorithm.
Memory constraint. For streaming PCA without fairness constraints, the main objective could be written as tr(VTXTXVV) = Σn 1 tr x V), which is easily amenable to memory-limited algorithm such as noisy power method (Mitliagkas et al., 2013) or stochastic optimization (Oja, 1982). Both approaches utilize the fact that instead of storing d x d matrices, one only needs to store matrix- vector product of size d x 1, e.g., V This is not the case for the approach of Kleindessner et al. (2023). To see this, consider Eqn. (14) without the covariance constraint, i.c., fair PCA with only the mean constraint, Even here, although the objective can written as ΣN Lr (TUUJa.AUUU1)
23

---

we must know Uy in order to proceed further. Moreover, y is of size O(d²), it cannot be stored nor estimated explicitly. When the covariance constraint also taken into account, although the matrix in question M is of dimension (d 1) x I, which is within the memory constraint if = (1), the computation of M requires the knowledge of Ug. This because Kleindessner et al. (2023) dealt with the two constraints sequentially (mean first, then covariance), which forced the reparametrization to be done twice and, more importantly, coupling the memory requirement for the computation of U and Ms
Statistical consideration. The statistical guarantee (global convergence, sample complexity) of streaming PCA algorithms is often obtained by appropriatcly bounding the error term and using proper matrix concentration inequalities (Tropp. 2015). For example, for the sample complexity guarantee of noisy power method (Balcan et al., 2016; Hardt and Price, 2014), as the learner performs power method on the empirical covariance Σ, x.Φ. instead of the true covariance Σ, the proof proceeds by first showing that the empirical covariance is close enough to the true covariance (i.e., the norm of their error term is sufficiently bounded), which then implies that the variance of the estimation isn't t too high. Thus analyze the error bound of the final iterates V when the approach of Kleindessner et al. (2023) is extended to a streaming setting, one would have to bound the estimation error of M,.s UUJEU M. There three sources of estimation error: M Uj E. Recalling that M consists of the eigenvectors UJSU one can see that the estimation error of M f.s is actually nontrivially dependent on the estimation quality of both U and S'. Here, we say nontrivially because the eπror isn't 't simply bounded in linear sense via the usual triangle inequality; it requires rather intricate techniques involving eigenvector perturbation theory (Davis and Kahan, 1969; Golub and Loan, 2013), which may require additional assumptions eigenvalue gaps. As can later in the proof, our approach considers both constraints simultaneously and thus allows for quite simple theoretical analysis.
24

---

E Proofs of Lemma 2, 3, and Theorem 1
E.1 Notations and Assumptions
We first recall the data generation process of our interest. At every time step, pair sensitive attribute and data point sampled has mean aa and covariance En. This can be written more compactly as x ~ = PoDo + pr D1. where we denote Po 1 p and p1 : p.
Bernoullipp) and æ/aa Da. respectively, where Da
We recall set of notation needed for the proof. The mean difference denoted by p1 while the second moment difference is S Ea 1] DlæxT|a 0J Σ; En + Mi Hop Let Pm E RR be the matrix whose columns are top eigenvectors of S in magnitude of eigenvalues. Note that & E [T] is the time variable for Algorithm 3, which we often omit if the context is clear. Moreover, b (without any sub-/superscript) is the block size of Algorithm 3. The remaining notation is listed below; most them came from the pseudocode our algorithms.
Counts of data points for each sensitive attribute a:
1b
T
Tb
(()
B(a)
la.=a]+
[a==a]
(
1=1
1=1
Estimates of group-conditional means:
[a.=0| F3
if B(()) > 0,
m
TBaaa
0
if B(a)
Estimate the group-conditional mean gap: f = (1 m
Estimate of the group-conditional second moments:
if ((b(a) 0,
[a [,
A
(0)
bi [a]
(1-1))6+1
0
if b/ =
Estimate of the group-conditional second moment gap: S. A (1)
A (0)
We E St(d, n) (decision variable of Algorithm and 3)
cla) A W,-1
. F, -( c((0
S.W.
W. (R.):) (i.e., F. OR W.R, R. E Rmxm is a lower triangular matrix)
Recall the assumptions on the data distribution, which we will assume throughout the proof: Assumption 1. Consider
data generation process a Bernoulli(p) and
D,.- There
exists a, V,M, V, 9min > 0, fmax E (gmin, oo), and Pmin E (0, 0.5) such that the followings hold for any (Do. (1.p) Fa: for {0, 1}, D. iSG(o)))
PP [||
(E MoHl))l2 S M a] =1 E MoHTl12 S V, Var (aea: aa) S V,
and
|لgو|2 = 1 1l2 E {0] U00iim [max]; |15 S fmaxi and p E [[min, - Pmii]-
Assumption 2. Fix m. E N. There exist Am,ys Dises Km KE E (0, such that for any Fa. the followings hold:
(Do, :), E
Un Um+1 2 Am,r, Kk+1 2 Ak Vm S Km and lok S KR.K.
where V1 respectively.
va 0 and K1
Kd the singular values of S and II ΣN
is norm-sub norm-sub-Gauusian, denoted as (.), if F Eyl 2 2e 202 We refer interested readers
Jin al. (2019, Section for more discussions norm-sub-Gaussiannn Gaussianity.
25

---

We provide some intuition on the assumptions that we impose here. Assumption 1 consists of three parts. The first part, which involves a, V,M and V, ensures that the maximum deviation in mean and covariance of each Dr are well bounded; this is critical in allowing for us to use proper matrix concentration inequalities (to be described the next subsection) and has been used in various streaming PCA literature (Bienstock et al., 2022; Huang et al., 2021; Jain et al., 2016). The second part, which involves Imin and fmax. imposes a bound on the maximum mean separation, f f= M41 /4. l2 wise and angle-wise, respectively. If the mean difference can be arbitrarily large, then the Eg-estimation error that one has to achieve becomes arbitrarily small; precisely speaking, I|fll acts a Lipschitz constant. On the other hand, if the mean difference can be arbitrarily small, then the angle-wise estimation error becomes arbitrarily large. The last part, which involves Pusin ensures that both groups selected with some positive. nonvanishing probability. Assumption 2 is standard in streaming PCA literature to ensure convergence; indeed, if the singular value gap is zero, definitive convergence result never be obtained, as the ground-truth solution becomes vague.
E.2 Matrix/Vector Concentration Inequalities
Before moving on to our proof, we review some useful concentration inequalities for our theoretical analysis.
Definition (Variance of random matrix). For zero-mean random matrix Z, its variance defined as
Var ( max (I [ZZ ||E [ 21112)
In general, Var(Z) Var(2 Z - E(Z]).
Proposition (Matrix Bernstein inequality (Theorem 6.6.1 of Tropp (2015))). Consider a finite collection {Y,} of independent matrices with the same size (d1 x d2). Suppose they are zero mean and they have uniformly bounded singular values, i.e.,
E|y 0 and P P |l S M) = for each j E [b].
Let V be an upper bound of matrix variance, V Z Var (Y₁) for all j E [b]. Then, for all 0.
bx²
P
Y
2 x
I (d1 + d2) exp
2(V + Mx/3)
j=1
In particular, if0 S x S M
3V
bx
P
Y
2 x
I (d1 + d2) exp
4V
Proposition (Vector Hoeffding incquality (Corollary 7 of Jin et al. (2019))). There exists an absolute constant such that y, Yo be independent random vectors with common dimension d, and assume the following:
Ely 0, Y: E enSG(o).
Then, for any x 2
6 y
(-
bxx
IP
2 < 2d edp
(-e202)
Remark 2. With an additional assumption that the random variables are bounded, we can also consider using vector Bernstein inequality (Lemma 18 of Kohler and Lucchi (2017)), which removes the factor of dimension d from the RHS of the concentration inequality.
E.3 Proof of Lemma 2- -Bounding Error in Second Moment Gap
Recall that Algorithm performs NPM on the second moment difference matrix that an iteration can be written as
W, QR( .-1) = QR (S,, + Z,,1),
where Zr = (S, (SS-S)W..... is the noise matrix.
The lemma below provides a general statement on sufficient size b of blocks to bound the second moment difference error S, S multiplied by some fixed matrices.
26

---

Lemma 4. Let any 8 > 0 and matrices M E R and N E R be given. If we choose
b
max
11,
S.M2
log 2(m+m), then with probability at least 5,
Puii
M(S. (MSS
(() -
32V
log
2 + +n)
bpmin
6
We now proceed the proof of Lemma 2. To this end, recall that Z,, = (S. - S- Firstly,
applying Lemma 4 with M = La and N = W E Rdxm, a sufficient condition for having 5 1212 I Edm,p with probability at least 1 5 is that
400V uPmia
2(d + m)
4
8M2 9V log 6 max (I,
2 + m)
log
5
Pmin
Secondly, applying Lemma 4 with M PT Rd and N Wt- E Rd sufficient
condition for having 5 PT 11, I
6Amm with probability at least 1 - 5 is that
2vdm
3200dmV
4m
4
8.M²
4m
b 2
log
max 1, 9V
log 8
8 2 Pmin
8
Pmin
Combining all bounds for b, we conclude that sufficient block size is
V
dm
1 log
d) 8)
M
d log
b= 9
log
+
A2
Pmmin
82
Vpmin
8)
Proof of Lemma 4. Note that (a,, Dss's are i..d samples (i E {(t 1)6 + tb). Consider independent random matrices
M ( + (all)) N. For each set A S [b]. define an event Fx:=
== (a,;11 11 Vi E [b]] Note that P[EA] = Po Pi pl.
1-141 |4|
To exploit this, we first apply peeling argument as follows: for any co, Ci (0, with co CI
(M(()-S)AN S) 2 xx)
b
Σ
( - 5)
EA) P (EA)
P
Σ (1)
b-r Σx,
(:(0)
2
Ea
P ((E)
AE (
SEA
BEA
2
(1
+P
Y (0)
2 Eg
P (Ex) +P
((())
2 E1j
PP (Ep1)
2
2
b-1
Ea ) pb po
Σ (0
2 Cu
EA
+P
(1))
2 c1
EA
b - r
AE
(t)
iEA
iEA
h
(1
F
Y, (0)
2 coar
Lig
1/ + P
(1)
2 c
Eip
pi.
1=1
where the last inequality holds for the following fact: if ||a (1 \)x for any X E (0, 1).
bll 2 then ||a|| > Ax
||b|| >
Now, make the crucial observation that conditioned the event EA, both {r and
iEA are sets of i.i.d. random zero-mean m x n matrices. In addition, with Assumption 1, we have that for each i E A,
(x: As
Y (1| S SM i A) =1, Var (x,")) ( ie A) SV.
27

---

(and analogously for each i E A4). Thus, applying the matrix Bernstein inequality (Proposition 1), we obtain the following: when S M
3V."
|1 -
S)W --
_z)
b-1
(b - r)cga²
ref2
$ (m + n)
Σ
Po
b-r
pi
exp
+ exp
+exp
4V
4V
AE(
befa²
boqx²
+ + + n)pp exp
+ (m + n)ppp exp
4V
4V
(b - r)
refx²
(m + (m
2
Po
b-r pi
exp
+ exp
4V
4V
cf
(m (m+n))
Po + pı exp
+
p1 Pu exp
5.
4V
4V
For this to occur, it suffices for both terms to be bounded by I. Let us consider only the first term, as the second term follows from symmetry. Taking the log, we have
log (1 (1- P1) p1 exp
5
log
4V
2 + n)
Using log(1 + v) S y. suffices to have
2mm + +n)
(1 (1- exp
log
S pi
4V
Using y e 29 for y E [0, 1/2). it now suffices to have
8V
2mm +
2V 9V²
log
min
b
8
द M2
Combining this with the other term and, for simplicity choosing cp = C1 = 1/2, we have our desired statement.
E.4 Proof of Lemma 3 Bounding the Final Error
Recall that the iterates are V,+1 QR Σ. II V7), where Ô is the output of Algorithm 3, I Ia Úûτ, and Σ, Σー 1)=(r-1)8+1 @. is the sample covariance at time step of Algorithm 4. This can be rewritten
V = QR + Z7.2),
where Z,2 = (II J - HI E V, is the noise matrix and Σ = Eae Pa(E, MaHl). have that |E|| V.
By Assumption
The lemma below provides a general statement on sufficient block size B to bound the covariance error Σ --- Σ multiplied by some fixed matrices.
Lemma Lel any > and matrices M RRmx and N Rdxx be given. If we choose B > 1 M²2
9 V+V= log 1mm+n), then the the following holds with probability at least 1 1-8:
|
Σ>>|, < _
(2)
4(V
+
log
4(m + n))
B
5
Precisely, we use its conditional version where the means and the variances are replaced with their conditional counterparts.
'One could try to optimize for co, Ci to obtain an "optimal" sample complexities. However, from some preliminary computations. this seems to be not worth pursuing, and we conjecture that it would yield the same asymptotic dependency when co 1/2.
28

---

We now proceed the proof of Lemma 3. Fix some V E St(d, and from the design of our
Algorithm 4, Ù is also fixed. By our given assumption upper bound of [ IT ll and the fact that || [ 2 1, we have
V
+ + 2
Hul2
<Ak.
1 E > v
+
10
and, with a similar logic,
6DR. 20 dk
I 212 < Q - 2
Applying Lemma with M y E Radd and N n V Rd sufficient condition for
having [ - E)
r
- rAt. with probability at least 1 - d is that
0
B 400( + V2)
4(d+k) k)
4
M V2 log
4(d (dd+h)
log
2
Furthermore, applying Lemma 5 with M = I
E
RR
&xd and N = g V E Rdxk a sufficient
condition for having Q I V
6āk.. with probability at least ó is that
20v
B 1600dk(V + V22
8h
M
8k 8
log
log
82
8
9V + 12
Combining all bounds for B, we conclude that sufficient block size B to have our desired statement
V V2
dki
k +
1
d z
M
d 3
B
A K,K
82
log
5
2
loy
+
V + 12
log
Proof of Lemma 5. Note that ă, are i... samples from D (j E {(T 1)B + , TB}). Let
Y, M (ājæ] Σ) N.
Then, Y, are i.i.d. random zero-mean d x k matrices across j. In addition, with Assumption 1,
[|@ E11 s M)
Σ
P P[ E12 S M/a a d'] = a'I 1,
d'E,0,3)
and
Var Var(@æT)
= E [ > //|a|]] [ [a]
E E (क:
|/a )
- B[ä [a]
|E [ [a|2] - E[Blăä [a]]
Σ Pa [ ||a] B| [a]2]
E [ pa E EE + Halu
2
aE[0.1]
Var( (a)
< V PoP1
|| | Dhroo E1 m1 12
< 1/ + 4po(1 V2
3 VV+V2 V2.
Applying the matrix Bernstein inequality (Proposition 1), we obtain the following: when 0 S x 3(V4y2)
M
8
Ba.
P
Y
2
S (m + n)
B
4(V + V2)
Solving for v, we have
4(V V2
4(m n))
(V (V+V2' 2
log
< 2 5
5
M
from which the statement naturally follows.
29

---

E.5
Bounding the Estimation Error of Mean Difference
Lemma 6. For any 6 > O, choose b Tumin least 1 8:
log
Then, the following holds with probability at
f f
5010 2
8c20² Tbpmin
4d log 5"
where c
Proof. Again, note that (a;, x.)'s are i..d. samples (i [1'6]. Consider independent random vectors
yi 2: Pa-
For each A S [Tb], EA = {a; = 1|i AJ Vi E b)} is an event satisfying P(EA) = Po 11
T6-1A1 |A| To
exploit this, we now apply the peeling argument as follows: for any co. C1 E (0, 1) with co + =
f f 111 2x)
Tb
Σ
Σ
P
p[]
111=
2 x
EA) PEA))
(
Tb-1
(1
Σ
Σ
P
Σ
yi
(1)
1
EV. (0)
Y;
N x
EA
((EA)
Tb r
AE( (TM))
iEA
iEAr
26
Tb
1
Σ
y
2 x
Eg
P (EE) + +
y
(1)
Bira
P (Eirro)
Tb
Tb
2
Tb-1
EA )
Σ
P
1
Σ
y;
(0)
cOz
EA
+P
ト y
2 c1
Po
Tb pp
Tb
AE( (TT)
(TM)
iEA
2
EEA
2
P
yi (0)
2 x
Fe
Po
Tb
+
P
Th Vi
(1)
2
Observe that conditioned on the event A. both {91"
(1) (1)
and { J JE are sets of i.i.d. random
(0)
iEA
zero-mean d-dimensional vectors. In addition, with Assumption 1, we have that for each E A,
y (1) E no)( (and analogously for each E A9). Thus, applying the vector Bernstein inequality (Proposition 2), we obtain the following: for x > 0,
Tb-1
(Tb r)ce2² 220
ref2² 20?
(( f f
2 x
2d
Tb Po
pi
Σ
exp
+ exp
r=1
AE (TTU))
Thx
Thx
+ 2dpb
exp
220
+ 2dp
exp
c207
T8
Tb
(Th r)cfue
refaa2
< 2d
Po
Tb
exp
2o0
+ exp
Gof
==0
(-
(-
c/ 2
Tb
Tb
= 2d pn + pı exp
+ 2d
+ po exp
<.
suffices for each of both terms to be bounded by g. Let us consider only the first term, as the second term follows from symmetry. Taking the log, we have
log (1- pL) + Pi exp (-cie²
cja²)
6 log
<
Tb
4d
30

---

Using log(1+ +1))++ S it suffices to have
1 4d Tb
(-
cq2²
log
8 S 1 (1-exp) exp
2:07
Using 11 2-2x for y - 1/2, it now suffices to have
of
4d
log
S x²
Cbp 8
ct
Combining this with the other term and, for simplicity (see the footnote on pg. 25), choosing Co C1 1/2, we have our desired statement.
E.6 Proof of Theorem 1 ISample Complexity for PAFO-Icarnability
Let fix Et, Eo, 8 (0, 1). From the definition of PAFO-leamability (Definition 2), with large enough sample size, we must guarantee the following with probability at least 1 - ó:
tr (VIEV) 2 tr (V E1,
|[U Vil2 S
Let Ú be the final estimate of the unfair subspace from Algorithm and let V be the final estimate of Q V*, whose columns are top k eigenvectors of n ENT.
We first recall the Neumann trace inequality (Mirsky, 1975; von Neumann, 1937):
Proposition (Theorem H.l.g of Marshall et al. (2011)). If A, B are two n x Hermitian malrices, then
trAB)) (AA))(BB.
where Xa(-) is the i-th smallest eigenvalue.
Also, the following lemma implies that the sine angle between subspaces (with the same dimension) and the corresponding Grassmannian (projection) distance the same.
Lemma 7. Let A E RRdxk and B E dx be semi-orthogonal matrices: ATAi I and
B Bi Ig. Define
( col 2 |IIA; I. l1a sin (col(A1), col( (B:)) A IT B 11112-
Then, (i) if = = dist(col(A1), coll() sin (col(A1), col( (B1))
sin (col(Br). coo((o))))) = 1
O (imi((A (1)
where min (M)) is the minimum singular value of M. On the other hand, (ii) if < E,
dist(col(A1), col( = =sin (col(cco))))))) col (o)( =
sin (col B1). vol(Ar)) V m (A)B,)²
Now we can write the optimality (the first inequality) as follows:
Ir [QEQ)) - (VTEV) = ir (E(Q - VVT))
X: (EE VVT)
(6)
3 24 Σ 22 QT VV
(o)
2kV
II II Q 5
31

---

Here, (a) follows from the von Neumann trace inequality, (6) follows from the fact that Q& VVT a symmetric matrix of rank at most 2k, and (c) follows from Lemma 7. Thus, for the optimality, suffices ensure that I Qu S ZEV
S Eo or Similarly, for the fairness (the second inequality), it suffices ensure that [ |1 [ - I Eo, as
ny Vll ( I ||
|
Hull2 So.
where (+) follows from V n V (due to the design of Algorithm 4) and (*) follows from Lemma 7.
From Lemma (letting T = O DE,m
KE. log $ ) and (substituting 28V given that
AKNer
k
11 HT S Tus- = me(et, cor 6) - min Eo:
40V2
v
(17)
total of N₂ TB samples sufficient in Algorithm 4 for ensuring Er-optimality with probability at least 1 -. where
K (V + V2)
dk
k
v² d) Ef
K2 + DR (V V2)
log d log
dkV
N₂
log
log
(18)
A3
82
6
8))
E,d
We now focus on obtaining the sample complexity for Algorithm to satisfy Eqn. (17) with probability least 1 6
Then combining those with union bound gives us the desired statement.
2-
From hereon and forth, we write
1
A II P
f,
|gg12 h
A
9.
g
è f.
A
9
10l1
Also, we introduce the following lemma that provides general bound of sine angle between a pair of vectors with small fz-distance. Lemma 8. Consider two vectors a, b E Rd. If we denote the (acute) angle between a and b as ((a,b)
1
1
sin Oaa b) sin(span(a), span(b))
aa
bbt
||a||
b
2
Consider any c (0. ||ل|| and suppose l|a - fabl, Then,
2
V2e
sin din0 b) <
[all2
Case 1. Assume g * 0. In this case, U = Pm hl,
||g1|2
2 Imin and || S fmax by
Assumption 1. We want upper-bound the following probability to be < 8/2:
PP I
-P [ā +
and
Il H ms) or
و = 0 and
> Th
< P m] wr
> mh g
+ P g 0].
Let us obtain sample complexity bound the first probability term to be 1. Note that
1wr + Ihh 1 -hh
1 [... [n]
II Wr
2
< p
32

---

Firstly, to yield
P
Hw, 112
Ww Pmll2 -
7
2
with probability at least
6 12.
it is sufficient that
Km.
nz )
T=
log
(19)
Am,
dm
m
d
M
d g
b= = Ω
A2
Pmiin
82
log
8
7
log
8
+
Vpmin
log
(20)
due to application of Lemma and
Secondly, aim to make the second term
hht - hhT
2
small with high probability. We first
claim that, if lgg Oll2 I Amin min
1 then
|hhT
-hh"
n4 2
Here is the proof of the
2
claim: Since ||g g g|1 S
|ااوا
we have
2
hht hh
S
V2
1 gl12 5
V2
19
9l12 S
7
|gl2
Imin
2
Thus, since
llg - 9l12 = = -Iw,) f + Iw (f - f)
< | -I l12 fmax + ||5 - 511.
(21)
we have
hht hh
1
g
+
2 2
$
11g Øl12 >
Imin
min
7k
9 +
2
V22
9min
Tk 12
||s
51/
Jmin
7/
<
P
P - II 11
min
1
9 +
0
+ IP
min
9 +
0
4 4mmx
4
To have
Amin 4fuax
1)k 1
III P... -I ll2 <
min
122'
with probability at least
12 is sufficient that
Km log
d fmax
)):
T T=
(22)
Dm,
n Imin
dm
log m
faax
d
M Vpmin
log 1og g
log z
(23)
2 Pminn
Moreover, have
- 5|
Jmin
7k 1 V22"
<
min
with probability at least
4 12 it is sufficient that
2
48d
Tb
max
2 17K
1
log
(24)
Pming
Next, we obtain sample complexity to bound the second probability term P [ of Eqn. (21),
0
Because
P p 0j P Øl > |
33

---

P
P
H, 112
Jmun
+P |||
f
Imiu
2fmax
2
To have [IPp Hw 12 <
Jmin
with probability at least 1 6 8
it suffices to have sample
2faax
complexity in Eqn. (22) and (23). Also, to have f f f/|_ Quin with probability at least
suffices to have sample complexity in Eqn. (24).
Combining the bounds the Case with union bound, we obtain a full sample complexity for Algorithm 3 as follows: a total of N1 Tb samples are sufficient for ensuring Eo)PFOO learnabliity with probability least 1 5, where
N 1 (Km.
V
dm
m
fmax log d
M² VAn.
f M
Pmin
A3
m,
log
5
2 Iiiin
8
log log
Imni
o²
+
log
Pminnfiin UJ
K
V
dm
f2 mh.
M
=Ω
+
(25)
Pmin
A m.p
82
VAm,
Pmii
Case 2.
Assume g O. In this case, U Pm.
We want to upper-bound the follow probability to
be < 5/2:
IP H mh
PP (ā and [ Ho ma)
(g + and
T II 0 m7
< P [I Iw 112 > na Ā = 0] + 1p II Wr|h
> 7/x g + 0
The first probability term is bounded by given that a sufficient number of samples just like Eqn. (19) and (20). To bound the second one, note that is orthogonal to every column of WT (i.e.
Iw, h = 0). Thus,
II
II II
[[w, -hhi)
Wn
Ip Iw (IIp.. Iw hht
2 I Iw, l
which can be bounded by < Th with probability at least 1 - f given that a sufficient number of samples just like Eqn. (19) and (20) again. Therefore, a total of N2(2 = Tb samples are sufficient for ensuring (ct, PAFO-lerabblyl with probability at least 5, where
N(1) Ω
Km,v
V
dm
log d 1
1
M²
log d log
d
log
+ VAm,
Pain
3
m,y
52
8
Km,v
V
dm
M²
}).
+
(26)
Punin
A3
82
T
VA 7/m.v/
Combining Case 1 (Eqn. (25)) and Case (Eqn. (26)) as N₂ 1[g + O)N + - N) have our desired statement.
Lastly, we provide the missing proof for our lemmas:
Proof of Lemma 7. Let
A
A
A2
and
B =
B
B
d-k
34

---

be d x d orthogonal matrices. proven as
We first show that sin (col( A1), (B))) || It can be
IT -| 2 || - |A] - <
|2AA/BBl
Thus, from now on, we will work with || instead of sin (col( A (.)).
The rest of the proof borrows the idea from the proof of Golub and Loan (2013, Theorem 2.5.1). Observe that
dist(col(A)). (B))) A (AT(AAAAA A
B A 22
B|)
A
0
2
max (IIB) A1l12 [|]
Note that A, and AI are submatrices of a d x d orthogonal matrix Q defined as
A B
B.
Q ATB =
A,B,
Readers might notice that A Bi E kx For any unit vector (in 2-norm) R
A B æ A B x
1
Q
= ||]
|| l|
Thus.
|A B
m18 @ER* ==
AA] B 12
min ØERt
|| B x
, 1==1
miin (1).
if 2 f if < l.
Likewise, working with QT, one can deduce that
| A 1/
|B. A A
yER 11y1l1== =1
min VERi .1vll1=11
||BT A.y
Omin (I],))?
if
if
Therefore, our desired statement naturally follows.
Proof of Lemma 8. To prove the first claim, let and be unit (&g norm) vectors in direction of and b, respectively. Then, by Lemma 7,
luaJ vo 112 1 min (uTv)² =
cos" 0(u, v) =sin² sin²0(a,)) b).
Now, observe that |bbl| 2 ||all2 - c 2 ||a||2 /2 and
2(1a |bbl| (a, b)) |al| -11b112 (a, b) 1| ila-bli, b112 < ?
Thus,
sin² (a, b) = (1 + cos 0 (a, b))(1 - cos ((a b)) < 2(1 - cos 0(a, b))
= 2 ||||| |||||
(a, b)
2c
2
a b
1
|a]
35

---

F More Experiments
E1
Synthetic Example
Vanilla NPM
Mean-matched NPM
Fair NPM
7.5
7.5
7.5
Group
Group
Group
5.0
Group
5.0
Group
5.0-
Group
2.5
2.5
2.5
0.0
-25
-2.5
-2.5
5.0
5.0
5.0
-7.5
-7.5
-7.5
-5
-5
-5
5
Figure Synthetic Example: Vanilla NPM v.s. Mean-matched NPM v.s. FNPM (ours).
We randomly generated two different group-conditional distributions as 10-dimensional multivariate Gaussians with different mean vectors pi and μ1. satisfying μ = = covariance matrices Eo and Σj. We choose the sampling probability parameter p as 0.2, which induces asymmetric sampling between two sensitive attributes. The covariance matrices are designed so that both of their eigenvalue spectra, foi,.... oa), have power-law decay many practical datasets do (Liu et al., 2015a), i.e., oj = ((j for some decay parameter a 2 1.
- p) - - = 0, and different
We first run and compare three different algorithms: vanilla NPM (without any fairness constraint), mean-matched NPM (with only constraint V 0), and FNPM with m 3. To ease the visualization, we project the sampled distributions onto 2-dimensional subspace (i.e., running 2-PCA). After running three algorithms for ten iterations and with block size of b B 1000, we randomly sample 1000 data points and visualize the results of projecting the data points in Figure 2. In particular, for FNPM, we run 50 iterations for unfair subspace estimation (Algorithm 3) and run the other 50 iterations for PCA (Algorithm 4). We observe that FNPM does indeed enforce both mean-matching and (partial) cecariinne-mmtcchnn despite the setting being streaming and having asymmetric sampling probability.
F.2 Additional Results on CelebA Dataset
In Figures 3-5, we provide additional experimental results on the CelebA dataset (L.iu et al., 2015b). We consider three sensitive attributes in the CelebA dataset: "Fyeglasses", "Mouth Slightly Open", and "Goattee", In all the figures, False is when the sensitive attribute is absent; True is otherwise.
Figure 3 presents the main results for the new attributes. The first row shows the original images, the second row shows the images after projecting them to col (V*), and the third row shows the images after projecting them to the estimated unfair subspace, col(ū). Here, both Ū and V* are obtained from our FNPM; specifically speaking, they are obtained from Algorithm 3 and Algorithm respectively. While we' ve used m 2 for Figure in the main text, we use m 5 here.
We then perform the two ablation studies as described in the main text, one on the dimension m of unfair subspace and another on the block size b of Algorithm 3, for the additional sensitive attributes considered. In Figure 4, we vary E {1, 2, 5, 10]: m increases, more features of images are "erased"" making the images from the two sensitive groups less distinguishable. At the same time, more semantically meaningful features are erased as well, resulting in rather "alien-like" images. In Figure 5, we vary 6 {32000, 8000, 3200, 1600]: as b increases, we have a more accurate estimation of unfair subspace col(U') resulting in more indistinguishable images (in sensitive attributes). As soon as the batch size exceeds a certain threshold (e.g., 8000 for "Goattee"), "), col (U) is estimated very well, and the unfair features are cleanly recovered, as it can be in the bottom rows.
E3 Full Results UCI Dataset
The full experiment results of fair PCA and downstream tasks on UCI datasets are provided. Again, method is competitive to the existing fair PCA algorithms across the considered UCI datasets.
36

---

Original
(Unfair subsp.)
(a) Atribute: "Eyeglasses" (Left four: False, Right four: True)
Original
Fair NPM
(Unfair subsp.)
(b) Attribute: "Mouth Slightly Open" (Left four: False, Right four: True)
Original
NPM
(Unfair subsp.)
(c) Attribute: "Goatee" (Left four: False, Right four: True)
Figure 3: CelebA, Additional results (m 5).
37

---

THE Lovil
CO
THE COui
Co 17
Covir
6.
Co
THe COrE
(a) Attribute:
"Eyeglasses"
(Left: False, Right: True)
Yor Oorch
Gon Do
CLVISS
PAN'S 18
Yer CEviS
new Goc D0
ver 021121
Pein's Con
wwrk COVIS
(b) Attribute: "Mouth Slightly Open" (Left: False, Right: True)
Wel
Cevil
Cevits
Cevit
Whlt
Coniza
Corts
Cow
Cenrs
Conoa
(c) Attribute: "Goatee" (Left: False, Right: True)
Figure 4: CelebA, Additional ablation on m E {1, 5, 10)
38

---

1-100
HOZI
1-
HOME
1-16M
-OKE
MAD
HOME
(a) Attribute:
"Eyeglasses"
(Left: False, Right: True)
3- XMXK
-2209
t-100
E-4
9-2269
8-2601
(b) Attribute: "Mouth Slightly Open" (Left: False, Right: True)
Vin
XXXX
3-0000
Shala
Wrlt
3209
2-10K
(c) Attribute: "Goatee" (Left: False, Right: True)
Figure 5: CelebA, Additional ablation on b E (32000, 082000,8000, 3200, 1600}
39

---

%ecco(() Apr(()
0.19
(.06().01)
0.02;0.01)
0.07
0.0ro.0)
0.0
0.0
0.0
0.06
(.07
0.07
0.0
0.01
0.0
0.0
0.2
(.17
(o.4
(0.0().02))
0.1
0.1 0.11
(.19)).01)
0.17
(0.01)
0.13
0.12 02)
0.07
0.06
MLP
(o.18)
80. (o..2
(0.2)))
79 (9.48)
80 (0.442(o.1)
75.37
75.33 10)
75.5 (5.54(u.39)
75. (5.48(u.30)
77 77.62 (6)
80.3 (0.31
80.33 (0.33
75. (0.24)
75.5 (5.58
75. 15.39(0.25)
75.37
83. 83.88
83.8 83.83(0.32)
81 (1.92(0.56)
79. (3.73
80. (8
80.72.0.99
84.52 29)
83 (3.228))
81 31.84(0.54)
80. 80.96.0 se)
78 78.94(0.7)
78. (n.63)
83.7
App(()
0.2
0.01 (0.0)
(o.0)
0.01 (0.0)
0.0
0.0
0.0
0.0
0.17
0.01 (o.0)
0.01 (0.0)
0.0
0.0
0.0
0.0
(.19
0.03
0.0kn.0)
0.0
0.0
0.0
0.17.0.01)
0.03
0.03 01)
0.0ro.0)
0.0
0.0
0.0
linear SVM
Table 2: Dataset = Adult Income [feature dim= diim=102... 102, #(train data (lata)=31,655)
1,655]
%)cco(
81.23 (0.36)
0.05 (0.0)) 78. (0.36)
(0.36)
(0.52(0.60)
78.57
75.33
75.33 (m.33 10)
75. (o.3))
75.33
82.21 (0.2)
78.57 (0.26)
78.57
75.3 (0.19))
75. (0.19)
75.33
75.33
0.18 83. (3.14)).1)
Takes too long time Takes too long time 0.18 81.71
75.33(0.10)
75. (0.39)
75.33 75.33
75.37
(0.18)
81.71
81.7 29)
75.33 (o.19)
75.33 75.33
75.33
(5.33 (0.10)
Takes too long time
75.33
Takes too long time
Memory Out
Memory OuL
Memory Oul
Memory Out
75.
0.19(..11)
ADP(U)
(.02(..01)
0.07
0.0
0.0
0.0
0.0
0.15
0.07
0.07
0.0
0.0
0.0
0.0 0)
0. 0.16
0. 0.12
0. 0.14
0. 0.16
(.18
(0.00))01)
(0.00)
0.16
0. 0.166,0 0)
0.12
0.11
kernel SVM
%eAce(())
82.4(o.2)
80. (0. 24).
(9.41 23)
80 (0.6
75.52
(0.38)
(o.a1)
75.55 75.59 34)
82.63 18)
80.6
80. 80.6
75.51 23)
73.54
75. 75.38
75,4 75.44(o.21) 21)
88. (0.21)
88. 88.43 18)
86. (6.99 82).
83.0 83.01 28)
85.71 78)
87.61 87)
85, (5.69(0.20) 24)
88. (0.18)
88. 38.53 22)
86. (6.86.0.3)
86. 86,64 29)
83.0
82.85 (0. 22)
75.67
MMD"()
(a300))
(.0().0)
0.0:0-0)
0.002.a.0)
0.001
(.0
0.001 0.001 (0.001)
0.006
N/A
0.002
0.002 0)
0.001 001)
0.001
0.0
0.0
0. 195 (0.002)
0.0022a.0)
0.0
(o.0)
0.001 0)
NA
0.01 (0.0)
(o.0) 0)
0.002
0.001
0.0
0.0
0.01
96 Var(1)
(.88
(0.11)
5.42(..11)
5.74
4.09 17)
(...3)
1.91 (0.0e)
1.91 09)
N/A
5.74
5.74
(.04(
2.63 (o.1)
2.64(0.00) 06)
20. (o.08)
18. (0.35)
14.54
11.34
9.36
9. 9.6 28) N/A
18. (0.a5)
83 35)
14.48 (4.48
14. 14.38
11.34 2)
11.34
Olfat and Aswani (2019) (0.1)
Olfat and Aswani (2019) (0.0)
Kleindessner et al (2023) (mean)
Kleindessner et al. (2023) (0.85)
Kleindessner al. (2023) (0.5)
(0.5)
Kleindessner et al. (2023) (kernel) Ravfogel et al. (2020)
Olfat and Aswani (2019) (0.1)
Olfat and Aswani (2019) (0.0)
Kleindessner al. (2023) (mean)
Kleindessner et al. (2023) (0.85)
Kleindessner et al. (2023) (0.5)
Kleindessner et al. (2023) (kernel)
Lee et (2022) (le-3)
Lee et al (1e-))
Ravfogel al. (2022a)
Samadi et al. (2018)
Ours (offline, mean)
Ours (FNPM. mean)
Ours (offline, m= 15)
Ours (FNPM, m==15)
Ours (offline, m==00
Ours (FNPM, m=50)
Lee et al. (Ie-3)
Lee et al. (2022)
10 Ravfogel al. (2020)
Ravfogel et al. (2022a)
Samadi et (2018)
Ours (offline. mean)
Ours (FNPM, mean)
Ours (offinne m==
Ours (FNPM. m=155)
Ours (offiin, m=50)
Ours (FNPM, m=50)
Method
PCA
PCA
40

---

ApP(()
(.3
0.03 (.03(0.03) (0.01)
(0.00)
0.07 (0.04)
0.07 (0.04)
0.08 (0.05)
0.02 (0.n4)
0.01 (0.01)
0.15
0.06
0.07 (0.03)
0.12 .0)
0.12 on
0.14 (0000))
0.13
0.2
0.03 (0.02) 02)
0.04
0.04
0.05 (0.04)
0.07 (0.04)
0.04 (0)
0.04
0.06,0.00
0.16 (30..3)
0.04
0.04 (0.00)) 03)
0.04 04)
0.04 02)
0.03 02)
0.04 83
0.03
0.07
MLP
(ecce())
64.16 64.16(1.01)
60. (1.59) (959)
(1.59)
(0.79
58.8
57.11
55.9 (1.27)
55. (Q.38
36.42 (2.29)
64.4 64.4(1.3)) 1.33)
60.61
60.5
59. (1.35)
59.5 59.56 48)
59.74(2.0)
59.63
70.01
68 (1.97(1.10) 10)
67 67.23
69.83 69.83 83)
68 (1.28) (1.28)
68 (3.63 (2)
64 (1.43
62.56
66 66.66(1.08)
(0.87) 81)
69. (0.5))
68. (8.86 (0.88)
69 69.25
68.97 68.97
68.92 68.92(1.05)
69 (1.00)
56.42
APP())
(.2
0.04 03)
0.04 0s)
0.05
0.01
p.0
(.02
0.0
0.0
0.13
0.05
0.05
0.04 .4)
0.03
0.03
0.03
0.16(0.05)
0.04 03)
0.04
0.02
(.02
(.02
0.05
0.0
0.0
0.14 03)
0.02
0.02
0.02
0.02
0.02
0.02 02)
linear SVM
Table 3: Datasel COMPAS [feature dim= 11. #(train data)=4,33 1,3
(eAco(1)
58.91 (0.52)
57.57 18)
57.56 06)
56.03 00)
56. 36.16,1.23 21)
54.81
54.74(1.21)
(1.44
54.81
59. (0.15) 39)
56.03 .00)
56.03 ..00)
55 (0.9)
55.51
55.49
55.55
65.39(1.15)
63 (1.85)1.15) 15)
61. 61.68
64.76/1.00
63.63 19)
61.62(0.63) (36
64.35
54.85
55.26 25)
65.54 72)
64.78
64. (4.84(..01) .1)
64.72 93)
(1.65(1.1)
64.47
64.54 23)
Memory Out
Memory OuL
Memory Oul
Memory Out
0.28 (0.03) (.28
(DP(()
0.03 (0.00))) 02)
0.03 (0.00 08)
0.07
0.08
0. (n.0))
0.08 06)
0.01 (u.0)
0.03 02)
0.15 03)
0.07
0.07 (0.00) 02)
(0.04) 04)
0.09
0.1 0.1
0.11(0.05)
(.15
(.1
0.09
0.09
0.09 (0.04)
(.1
0.26
0.04
0.07 04)
0.17 02)
0.09
0.09 02)
0.09 (0.00) 03)
0.09 08)
0.09 03)
0.09 03)
kernel SVM
(cAco(()
(4.84(0.79)
62.41 09)
62.65
61.94
60.64
59.67
57.8
56.35
57.54
(4.19 0n)
61.94
61. (0.9)
61.22 85)
61.08
61.71
61.67
82.78
78.93
80.87
80.64 82)
79.22 44)
655 65.9661.12)
64.17
71.75 69)
69.75(1.0)
80.87
(0.87 49)
80.93 63)
80.82 48)
81.03 (0.6))
80. (0.4).
80.76go.
61.9%
MMD*(L)
(0.06))
0.003 (0. 002)
0.003 (0.002)
0.008 (0.08(0.003) (0.003)
(o.05()
0.005 (0.002)
0.004 (D.0n1)
(p.04)))
N/A
0.0
0.002
N/A
0.008 0.008(p.omz) (D.ons)
0.008 (0.00))
0.006 0.006 (0.002)
0.006 0.006 (0.002)
(0.0000000)
0.006
(.089(0.002)
0.089 (0.002)
0.002 (0.001)
0.002 (0.001)
0.004 (0.001
0.004 0.004(0.00) (0.001)
0.003 (0.001)
N/A
0.001
0.001 (0.0) ()
N/A
0.004 0.004(0.001) (0.001)
0.004(00.00) 00.011)
(..00(c.000)) (0.001)
0.004
0.004 (0.400
0.004 (0.001)
0.004
%6 Var(1)
(.11)
1.8 1)
o.78
1.78 (.97
13)
(p.on)
N/A
0.62
0.49 0.49 00)
N/A
1.97
1.97
(.92().11)
(.92
1. (o.1)
(o81)
5.85
(.36(0.31)
4.83
5.67
5.41
(0.31)
N/A
2.64
2.45 08)
N/A
5.67 (0.37)
(0.3))
(o.55)
5.55
(.55 (0.34)
5.58
Olfat and Aswani (2019) (0.1) I)
Olfat and Aswani (2019) (0.0)
Kleindessner et (2023) (mean)
K Kleindessner et al. (2023) (0.85)
Kleindessner al. (2023) (0.5)
Kleindessner et al. (2023) (keme))
Olfat and Aswani (2019) (0.1)
Olfat and Aswani (2019) (0.0)
Kleindessner al. (2023) (mean)
Kleindessner et (2023) 85)
Kleindcssner et al. (2023) (0.5)
Kleindessner et al. (2023) (kernel)
Lee et al. (2022) (Ie-3)
Lee et al (2022)
Ravfogel et al. (2020)
Raviogel et al. (2022a)
Samadi et al. (2018)
Ours (offline, mean)
Ours (FNPM, mean)
Ours (offline, m=2)
Ours (FNPM, m)=2
Ours (offline, m==5
Ours (FNPM, m==5)
Lee et (
Lee et (2022)
Ravfogel al. (2020)
Raviogel et al. (2022a)
Samadi (2018)
Ours (offline, mean)
Ours (FNPM. mean)
Ours (offline, m==2)
Ours (FNPM, m=2)
Ours (offline, m=5)
Ours (FNPM, m==)
Method
PCA
PCA
41

---

Apr(()
0.15
0.0
0.0
0.05(0.04)
0.03
0.05
0.02
0.01 (n.a1)
0.0
(.01
0.02 03)
0.08 (0.06)
0.06
0.08
(..0().03))
0.02(0.02)
0.03
0.02 02)
0.11
0.0
0.0
0.0910.07)
0.06
0.09
0.09 (o.06)
0.08 (0.06)
(.08
0.07 06)
0.09
0.09 (0.06)
(a.07)
0.1 (0.07)
0.1 on)
0.08 06)
0.08 (.08(o.04)
0.08 (0.05))
MLP
%Acco())
(1.43))
0.0
0.0
(1.6(1.58)
70.73
72.13
70.7
71.17
(3.98)
70. 70.13
70. 70.47
76.57
71.8
72.63
(1.2
70.83/2.25)
71.27
70.9
95.7
0.0
(.0
(1.9
83.1
96.77 96.77
(7.8
94.67(2.11)
81.7((449)
93.27
95.9(2.3)
98. (0.8(0.622 62)
97.5
35.53(1.40)
96.73/1.21)
96.4
93.5 (4.54)
(2.56)
95.53
72.6
App(()
0..33
0.0
0.0
0.0(0.0)
0.0(0.0)
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0(o.0)
0.0
0.0
0.0 0)
0. 0.14
0.03
0.02 .1)
0.09(..02)
0.0ko.0)
0.09
0.05
(..0
0.0
0.01
0.03
0.11
0.09 (0.05)
0.09 06)
O.04(
0.02
0.02
0.03 (8.04)
linear SVM
Table 4: Datasel = German Credit [feature dim=59, #(train data)= 700]
%cccc(()
70.3
69 (1.97(1.0) .90)
69.97 (1.97 (90)
69 (9.97((1.0)) (98)
69 (9.97(1.99) (..9)
69 (9.97(1-00) (1-9))
69 (1.97().99) 1.00)
(1.97 19))
(9.8(1.25)
69 (1.97
69.97 (9.97(1.00) 99)
69 (9.93(1.90) .9)
69.97 69.97 (0)
69 (9.97( 190))
69 (9.97(1.90)
69 19.97(1.900 (1.90)
69 (1.97 .8)
69 (9.97 18)
74.43
71.43
71.3
74.3 00)
69 69.97(1.00) (1)08)
74.1
(3.06)
(2.87)
69.8 (1.8(1.11)
70.7
71.8 (8.08)
75.8 (5.87(0.92) (2)
74.1 (2.00)
(4.07(2.12)
72.83
71.37
71.77
(1.77
ADP(U)
0.15
0.02
0.02
(.05
(.03(0.03)
0.04.0.03)
0.03
0.02
0.0
(.02
71.37 0.03
0.06
0.04
0.04
0.03 02)
0.02
0.04
0.03
0.09
0. 0.1 06)
0. 0.1 (0.00)
0.1 00)
0.07
0. 0.1
0. 0.1 (0.0))
0.1
0.0
0. 0.1
0. 0.1 06)
0. 0.1 (0.00)
0. (.. (0.06)
0. 1
0.1
0. 0.1 00)
0. 0.1 06)
0. 1. 06)
kerell SVM
%eAce(())
75.47
71.53 85)
72.03 99)
74. (1.78)
73.23 27)
76, 76.77 47)
73. 73.17(2.03) 03)
71.6g2.84)
69.8 (9.8(1.2))
71.33
74.2
76,77
76.7
72.6(2.37)
73.0
72.77 57)
72.53 37)
99. (o.93().13)
99.97(0.1)
99, (0.17
100.0.o.0)
94.4 p4.43 55)
99. 99.97.0.1)
100.0
(9.9(o.15)
(1.1
99.1 (0.47)
99. 9 (0.15)
99. (9.07(0.55)) 57)
99. (0.97
(0.1)
99.9 (0.3
99 19.9
99 19.87 22)
99. (n.1)
76,
MMD
0.293 0.293 (0.054)
0.024(0.01)
0.022 (0.009) 0000))
0.027 (0.0188
(o.05))
0.031ç0.018
0.021 (0.008)
0.017 (0.n1s)
0.007 0.007 (0.004)
0.04 (0.044))
0.031 0.031 (0.018)
0.031 (0.018)
0.017 008)
(0009)
0.032
0.028
0. 1.137 (0.012)
0.022 (000))
0.021 (o 005)
0.022 000)
0.014 008)
0.024
(0.004) (0.004)
(000600004))
0.0l
0.022 (0.01))
0.024 (o.04)) (0.004)
0.024 004)
0.008
0.018 001)
0.027 006)
0.026 n06)) o08)
N/
N/A
0.02
N/A
N/
% Var(1)
(1.13
7.28 (0.52)
9.82(0.45) 45)
8 (.8%
4.66 6.97
22)
3.25
3.19 36)
10.39 62)
(0.39 (0.62)
6.55 (o.5))
(.89
4.91
38. (9
29. (0.98) (8)
29 (0.98)
33. (1.04
16.6
35. (0.88)
27. 79.99 (0)82)
19.87 19.87 (0.61)
15.0 8e)
16.4 (6.41
35. (0.88)
35. (0.84)
26. (0.94)
26.23
21.1
21.06
10.39
N/A
N/A
N/A
N/A
7.25
Olfat and Aswani (2019) (0.1)
Olfat and Aswani (2019) (0.0)
Kleindessner et al. (2023) (mean)
Kleindessner et al. (2023) (0.85)
Kleindessner al. (2023) (0.5)
(0.5)
Kleindessner et al. (2023) (kernel)
Olfat and Aswani (2019) (0.1)
Olfat and Aswani (2019) (0.0)
Kleindessner al. (2023) (mean)
Kleindessner et al. (2023) (0.85)
Kleindessner et al. (2023) (0.5)
Kleindessner et al. (2023) (kernel)
Lee et al. (2022) (le-3)
Lee et al (1e-6)
Ravfogel et al. (2020)
Ravfogel al. (2022a)
Samadi et al. (2018)
Ours (offline, mean)
Ours (FNPM. mean)
Ours (offline, m= 10)
Ours (FNPM, m==00)
Ours (offline, m=25)
Ours (FNPM, m=25)
Lee et al. (Ie-))
Lee et al. (2022)
10 Ravfogel al. (2020)
Ravfogel et al. (2022a)
Samadi (2018)
Ours (offline. mean)
Ours (FNPM. mean)
Ours (offinne m/ 10)
Ours (FNPM, m=10)
Ours (offiin,, m=25)
Ours (FNPM, m=25)
Method
PCA
PCA
42


Reviews:
[{"review_id": "HMIhrovKPw", "reviewer": "Reviewer_SSmx", "summary": "The paper defines a new notion for fair pca. It is assumed that the data comes from  mixture of (two) distributions and the goal is to find a subspace for it such that the solution subspace is perpendicular to \n\n1) the difference in the difference vector of the mean\n2) the top m eigen vectors of the difference of the variance\n\nThis problem can simply be computed by computing PCA on a projected space. This paper looks for an algorithm that is \n\n1) with probability 1-delta, reports an approximate solution.\n2) Works in the streaming setting where once gets samples from the mixture of the distributions and uses space which depends on O(kd).\n\nThe algorithm is to use the samples to estimate the parameters of the two distributions and thus approximating the orthogonal constraint and then run the standard SVD algorithms.", "questions": "NA", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper defines a new notion for fair PCA.", "weaknesses": "- The paper does not discuss why this particular notion captures fairness.\n- The amount of technical novelty in the paper is limited.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and comments. We assure the reviewer in advance that all the answers and discussions provided here will be incorporated into our revised manuscript. Below, we respond to each point raised in your review:\n \n> **W1. Why does this particular notion capture fairness?**  \n\nTo the best of our understanding, your question can be divided into two parts: 1) ‘Why does our “Null it out” formulation of fair PCA capture fairness?’ 2) ‘Why is our PAFO learnability an appropriate statistical framework for fair PCA?’\n \nFirst, we emphasize that our intuitive notion of fairness in PCA, where the projected distributions are approximately matched, has already been well studied [1,2,3]. Including our paper, this line of work builds upon the foundation of fair representation learning [4], a seminal work in fairness that recently received the test-of-the-time award at ICML 2023. The main idea is to learn a low-dimensional representation that retains as much information as possible about the high-dimensional data while ensuring fairness, such that any vanilla downstream task learner can achieve fairness without explicit regularization. This matches the intuition that if the appropriate (conditional) distributions match, any vanilla supervised learners would be fair.\n \nSecond, we elaborate on why our proposed PAFO learnability aligns well with fair PCA. We emphasize that no existing literature on fair PCA for fair representation learning has provided statistical frameworks to analyze the problem setting. Our new formulation defines optimality and fairness criteria. Optimality refers to how suboptimal our solution's explained variance is compared to the optimal fair solution, which is always well-defined, a key characteristic of our new formulation. Fairness is defined based on how much component is left in the \"unfair\" directions.\n\n> **W2-1. Amount of technical novelty**  \n\nWe believe that our paper contributes significant technical novelty in making and analyzing scalable (memory-efficient) fair algorithms. While these points are summarized in our contributions (pg. 2) and throughout the paper, we reiterate them for clarity:\n \n> **W2-2. The novelty of our proposed new streaming setting.**  \n\nThe problem of fair PCA for fair representation learning has been well-studied [1,2,3]. However, previous approaches cannot handle memory limitations, where the algorithm is restricted to using only $o(d^2)$ (or $O(dk)$) space. To handle this, we introduce the new fair streaming PCA setting, where data points arrive sequentially from an \"unfair\" distribution, and the algorithm must learn under memory constraints. Even without fairness, such a streaming setting has received considerable interest from the stat/ML community due to its potential in processing data streams and dealing with memory limitation, especially in streaming PCA [5,6,7,8,9,10]. **We thoroughly discussed in Section 5.2 and Appendix C why existing approaches/formulations of fair PCA [1,2,3] can*not* be trivially extended to this streaming setting.**\n \n> **W2-3. The novelty of our statistical framework.**  \n\nNone of the previous works on fair PCA [1,2,3] had a statistical framework in which the performance of their algorithms could be rigorously shown. By statistical framework, we mean a learnability framework (similar to PAC-learning) in which the number of samples sufficient to solve the problem of fair PCA can be formalized. Indeed, due to several approximations that [1,2,3] had done to make their algorithm and/or optimization problem feasible, it is hard to see exactly which part of the approximation causes the bottleneck in the sample complexity. **As discussed in Section 3**, by considering a new “Null It Out” formulation of fair PCA, we could overcome the infeasibility issues and allow us to develop the PAFO-learnability framework.\n \n> **W2-4. Technical difficulties in the analysis.**  \n\nNone of the previous works on fair PCA [1,2,3] provide statistical guarantees for their algorithms. While our algorithm is based on the well-known noisy power method [8,9], **the analysis is significantly more challenging because there are two sources of randomness: group membership described by Bernoulli random variables and sampling from a group-wise distribution.** We had to modify the given random variables to apply the existing Bernstein concentration results during Phase 1's convergence proof.\n \n> **W2-5. Relevance of our setting to real-life: Experimental results.**  \n\nIn Section 7, we experimentally demonstrate the significance of memory limitations when performing a fair PCA on real-world datasets (full resolution, full colored CelebA dataset) using previously proposed algorithms; none of them could run on this dataset with our local machine. By transforming the problem into a streaming setting and applying our algorithm, we show that such memory limitation can be circumvented, making fair PCA *scalable*. Additional quantitative results on UCI datasets, parts of which we report in Table 1 of our attached supplementary pdf, demonstrated that our new formulation achieves similar performance as previous algorithms, showing that our formulation and algorithm are a strict improvement over the previous ones. Furthermore, the simplicity of our algorithm enhances its applicability to real-world datasets; this is in contrast to some of the previous fair PCA algorithms [1,2] as they require external libraries such as SDP solver [1] or manifold optimization package [2].\n\nIn conclusion, we believe that our paper offers substantial technical novelty in both algorithm design and theoretical analysis, as well as a new problem setting of fair streaming PCA. We are open to addressing any further questions or concerns the reviewer may have. We hope that our response has properly addressed the reviewer’s concerns and that the reviewer would reconsider the score. Thank you again for your helpful reviews and comments."}, {"review_id": "6WmJbdLcDe", "reviewer": "Reviewer_VcC6", "summary": "This research paper focuses on the fair principal component analysis (PCA) problem using streaming data while requiring low memory. The authors introduce a new formulation for fair PCA, which involves optimizing the vanilla PCA objective with a linear \"fair\" constraint. In the oracle setting, where the true parameter is known, the problem has a closed-form solution. The authors define the concept of \"PAFO-learnable\" to quantify the sample complexity of learning a semi-orthogonal matrix V, which is an approximately optimal solution to the oracle problem. They present streaming algorithms and prove that such an algorithm scheme has finite sample complexity according to the proposed PAFO-learnable notion. The main idea is to utilize the noisy power method framework to estimate the unfair subspace (the linear constraint) and subsequently employ this estimation in the NPM (Noisy Power Method) to estimate fair PCA. The effectiveness of the proposed method is evaluated using real-world data.", "questions": "See above.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the contribution of the paper is well-motivated and aligns with the ongoing development of methods for problems involving fair constraints. The paper is well-written, and the investigation is quite extensive. However, I must admit that I am not familiar with recent developments in fairness in machine learning and cannot provide an assessment of the significance of the new formulation Equation (1) and the concept of learnability (Definition 4.2), although they appear reasonable and interesting.\n", "weaknesses": "I have a few minor comments:\n\n* L68: It might be more appropriate to use the term \"semi-orthogonal matrix\" instead of \"orthogonal\" to distinguish between O(d) and St(d,k).\n* L69, L116, L171: QR decomposition typically yields two outputs, namely the (semi-)orthogonal part and the upper triangular part.\n* L164: Regarding F_d, it differs from the one defined in Definition 4.2, where learnability is defined for a different quantity denoted as F_d.\n* L262: Once again, F_{d,m,k} is inconsistent with the definition provided in Definition 4.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing a detailed and insightful review of our paper. We are glad that the reviewer recognized the significance of our work and appreciated our contributions. We provide our answers below.\n \n> **S1. Recent developments in fairness in ML**\n  \nThe field of fairness has seen considerable progress in recent years in proposing sensible and new definitions of fairness and new algorithms with the fairness constraint. However, scalability remains a crucial challenge in the latter part (so-called algorithmic fairness), particularly for fair PCA. Indeed only recently has the issue of scalability begun to be studied, focusing on fair clustering [14,15,16]. One of our primary focuses was addressing the memory limitation associated with fair PCA by proposing its streaming variant. Especially as PCA is one of the standard tools used for high dimensional data analysis (see our Introduction section) and previous approaches to fair PCA [1,2,3] are still not so scalable (see our Experiments section), we believe that making fair PCA further scalable is timely and important.\n\n> **S2. Regarding the significance of our new formulation Equation (1) and the concept of learnability (Definition 4.2)**   \n\nAgain, we appreciate the reviewer's keen interest in our paper. We would like to take a moment to delve deeper into the significance of our work. Our alternative formulation of fair PCA offers two crucial advantages: **feasibility** and **scalability**. To begin, our formulation of fair PCA as a constrained optimization problem is always feasible so that there is no need for further relaxation, which is sometimes not the case for the previous formulations under certain group-wise distributions [1,2,3]. This, in turn, has paved the way for the rigorous establishment of the novel concept of statistical sample complexity in terms of PAFO-learnability. Indeed, this achievement stands as a first in the field of fair PCA literature. Moreover, our formulation is scalable, particularly in the context of streaming scenarios, allowing us to develop the FNPM algorithm for fair streaming PCA. For a more detailed elaboration on this, we kindly direct the reviewer to our general response.\n \n> **W1. Minor comments on the writing**  \n\nWe genuinely appreciate the reviewer's comments on the writing and assure you that we will incorporate all the suggested fixes in our revised manuscript. To be more specific, we will reflect the following points:\n* L68: We will clarify by using the term ‘semi-orthogonal’ rectangular matrices, as per the reviewer’s suggestion.\n* QR decomposition (L69, L116, L171): We would like to remark that the symbol “$QR(\\cdot)$” itself is quite widely used in (streaming) PCA literature, which is generally used as an orthogonal projection operator onto the Stiefel manifold (for the case of vectors (i.e., $k=1$), $QR(v)$ is defined to be the same as the normalization $v/\\|v\\|$, an orthogonal projection onto the unit sphere). Nevertheless, we will elaborate more clearly on this in our revised manuscript.\n* L164 & L262: We greatly appreciate the reviewer’s comment on our notation. We correct the notation such that for fixed integers $d, k, m$, we define PAFO-learnability for a collection $\\mathcal{F}_d \\subset \\mathcal{P}_d \\times \\mathcal{P}_d \\times (0,1)$. We will make this clear in our upcoming manuscript. \n"}, {"review_id": "NSvL8DWuqb", "reviewer": "Reviewer_6AMc", "summary": "This paper proposes a new approach for Fair PCA algorithms that is scalable and fair at the same time. The main contributions of the paper are as follows:\n\n- A new formulation of fair PCA based on the \"Null It Out\" approach. The goal is to maximize explained variance while nullifying the subspace spanned by the mean difference and leading eigenvectors of the covariance difference between groups. This formulation leads to a closed-form solution and avoids infeasibility issues in previous covariance matching approaches. Their approach removes the unfair subspaces using a noisy power method.\n\n- A new notion of learnability for fair PCA called Probably Approximately Fair and Optimal (PAFO)-learnability. This provides a statistical framework to analyze some of the fair PCA algorithms.\n\n- A new setting called fair streaming PCA, which addresses practical memory limitations. The authors propose an algorithm called Fair Noisy Power Method (FNPM) which only requires O(dk) memory, where d is data dimension and k is the target PCA dimension.\n\n- The empirical study of this method using a vision task is intuitive.", "questions": "See the previous part", "limitations": "Some of the limitations I discussed in the weakness section are not clearly discussed in the paper. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe the strengths of this paper can be summarized in three main key points:\n\n- Theoretical rigor. The paper provides the first statistical framework for analyzing fair PCA in terms of PAFO-learnability. This gives theoretical guarantees on the solution quality of algorithms like FNPM. Previous works mainly lacked such a framework.\n\n- They propose  FNPM for this problem, which is quite simple to implement, building on standard tools like cumulative averaging and the noisy power method. This makes it easy to apply in practice.\n\n- Their approach is scalable and intuitive. They have validated that with a vision task to demonstrate the scalability. Also, the formulation based on nullifying the \"unfair\" subspace gives flexibility in how much fairness to impose by choosing m. This can be tuned based on the use case. The analysis provides insights into how properties like the singular value gaps and mean difference norm affect the sample complexity and solution quality.", "weaknesses": "There are some main concerns I have regarding this paper:\n\n- The results are limited to binary sensitive attributes and two groups. Extending the approach to handle more complex, multi-group scenarios with sensitive feature interactions would strengthen the paper. Some of the main previous approaches can easily handle this problem as well [A,B].\n\n- Certain assumptions made, like those in Assumptions 6.1 and 6.2, are quite strong and restrictive. Relaxing these assumptions, or testing how sensitive the approach is to their violation would improve the robustness.\n\n- The experiments focus on how much FNPM removes features visually related to sensitive attributes. Evaluating the fairness of solutions in a more quantitative, metric-based fashion would provide a more objective assessment. This quantity is defined differently in various approaches.\n\n- Lack of comparison with the other branch of fair PCA methods. Although the goal of equalizing losses is different than what presented here, it would be more beneficial to better understand how different methods would compare.\n\n- Comparing the effects of this fair PCA on downstream tasks like classification can be beneficial to better understand the effects of a fair PCA approach.\n\n\n\n[A] Morgenstern, Jamie, et al. \"Fair dimensionality reduction and iterative rounding for sdps.\" arXiv 2019 (2019).\n\n[B] Kamani, Mohammad Mahdi, et al. \"Efficient fair principal component analysis.\" Machine Learning (2022): 1-32.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review, for recognizing the significance of our contributions, and for providing valuable feedback. Let us address the raised points below:\n \n> **W1. Dealing with multiple sensitive groups**  \n\nWe appreciate the reviewer for bringing up the issue of focusing on two sensitive groups in our paper. While we agree that the simplicity of the discussions led us to consider two groups initially, we acknowledge the importance of extending our work to handle multiple sensitive groups. We agree with the reviewer that this direction would significantly enhance the strength and impact of our paper.\n\nWe first emphasize that the definition of fair PCA considered in references [A, B] mentioned by the reviewer is entirely different from ours as their definition is such that the reconstruction losses across groups are equalized, while ours is in terms of fair representation learning. Thus, their approaches are not readily applicable to our definition of fair PCA as a straightforward extension to multiple groups. Among the ones that tackle fair PCA from the fair representation learning perspective, [1,3] explicitly consider dealing with multiple groups in the fair PCA (fair representation). However, the approach of [1] is not scalable to higher dimensions (as also discussed in [2,3]), and [3]’s approach only deals with mean-matching, is not memory-efficient, and has no theoretical guarantees.\n \nFor completeness, we outline how our formulation can be extended to handle multiple sensitive groups. In the streaming setting, we propose to sample the sensitive attribute from a multinomial distribution over the $G$ sensitive groups, where each group corresponds to a separate data distribution. The fair PCA formulation would then involve nullifying the projected mean differences and the top-m eigenvectors of the projected covariance differences for all possible pairwise group comparisons.\n \nTo address theoretical analyses, we assume that $G = O(1)$ (or even up to $G = o(\\sqrt{d/m})$, as further explained later). For the mean difference, we construct a $d \\times (G-1)$ matrix whose $j$-th column is the (estimated) mean difference between group $j$ and $j+1$. For the covariance difference, we construct $\\binom{G}{2}$ number of $d \\times m$ matrices, each corresponding to top-m eigenvectors of the (estimated) covariance difference between two groups for all possible pairwise comparisons. These matrices are to be nullified, forming a $d \\times O(mG^2)$ matrix $\\boldsymbol{N}$ used in Phase 2. Estimating $\\boldsymbol{N}$ in Phase 1 can be achieved in $o(d^2)$ space, even when $G= o(\\sqrt{d/m})$ as mentioned at the beginning. With minor adjustments, we believe our algorithm can effectively satisfy PAFO-learnability for multiple groups with similar assumptions.\n \n\n> **W2. Strong Assumptions**  \n\nPlease refer to the general response 2. \n\n> **W3-5. Lack of quantitative evaluation, downstream tasks, and comparison with the other branch of fair PCA**  \n\nWe appreciate the reviewer's suggestion and acknowledge the importance of quantitative evaluation in providing an objective assessment. As showcased in **Table 1** of our supplementary attachment, we have already conducted experiments on UCI datasets (German Credit, Adult Income, COMPAS) to compare the performance of our algorithm against previous approaches. We evaluated our approach based on metrics such as explained variance, PCA fairness (measured by MMD distance), downstream task accuracy, and downstream task fairness (measured by demographic parity). The experimental protocols were adopted from prior fair PCA literature [2,3] to ensure a fair comparison.\n \nAdditionally, we performed additional experiments comparing our approach with the algorithm presented in reference [11], which focuses on equalizing reconstruction loss across groups. The results (shown in Table 1) demonstrate that our alternative formulation of fair PCA and its streaming variant exhibit comparable performance. Moreover, as already reported in [2,3], in general, the fair PCA algorithms that focus on fair representation learning, including ours, outperform [11] in both PCA fairness (in the context of fair representation) and downstream task fairness. For further information, we refer the reviewer to Appendix A of [2], where the conceptual difference between the two different fair PCA formulations is well explained."}, {"review_id": "sA3YZm9yHi", "reviewer": "Reviewer_GuCQ", "summary": "This paper studies fair PCA problem. The authors provide a novel formulation of fair PCA based on the \"Null it Out\" approach and propose the corresponding criterion called PAFO-learnability. The authors also present a streaming algorithm for fair PCA, which has low memory complexity. Experimental results verify the scalability of the proposed method.", "questions": "1. Why this paper proposes a new formulation of fair PCA rather than use a existing one? What's the advantage of \"Null it out\" formulation?\n2. Do existing fair PCA algorithms satisfy PAFO-Learnability?", "limitations": "The paper has no potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and mostly clear.\n2. The studied problem is interesting and important. Streaming algorithms are very useful in the limited-memory setting.", "weaknesses": "1. Assumption 6.1 is a bit strong to me. The paper may show that when D_s is a common distribution such as sub-Gaussian distribution, the generated data satisfies assumption 6.1.\n2. I'm worried about the tightness of theorems in section 6. The theoretical results show that Alg 1 and Alg 2 may require very large block sizes, which reduces the contirbution of saving memory.\n3. The experiments part may present some quantitative results rather than just show the images. The expriments should verify that proposed FNPM algorithm is PAFO-learnability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer’s valuable review and questions. Here, we respond to each point raised by the reviewer:\n\n> **W1. Strong assumption**  \n\nPlease refer to our general response.\n \n\n> **W2. Tightness of the theorems & large block size**  \n\nWe understand your concern about the tightness of the theorems, particularly as they assert that one needs a large block size. However, we want to emphasize that **the memory complexity is independent of the size of the blocks.** Indeed, our algorithm only requires O(d max(m, k)) *storage* as all other computations are handled in a running-average-type manner, with the primary computational cost being matrix-vector multiplications.\n \nIt is important to note that the dependencies on epsilon, delta, and the singular value gap in our results align with those found in previous works on the (vanilla, non-fair) noisy power method [8,9], which also relied on Bernstein concentrations. In practice, using large block sizes helps mitigate large variances and is a common theoretical and empirical approach for the noisy power method.\n \n\n> **W3. Experiments verifying that the FNPM algorithm is PAFO-learnable**  \n\nThank you for suggesting experiments to verify the PAFO-learnability of our algorithm. We have done two sets of additional experiments that would address this point. **Due to space constraints, we report only partial results, but we emphasize that we will report the full results in our revised manuscript.**\n\nFirst, we conducted experiments on UCI datasets (COMPAS, German Credit, & Adult Income) to compare our algorithm's *quantitative* performance against previous approaches. We evaluated our approach based on metrics such as explained variance, distributional fairness (measured by MMD distance), downstream task accuracy, and downstream task fairness (measured by demographic parity, or DP). The experimental protocols were adopted from prior fair PCA literature [2,3] to ensure a fair comparison. The results demonstrate that our alternative formulation of fair PCA and its streaming variant exhibit comparable performance in both runtime and overall performance.\n\nSecond, we conducted synthetic experiments varying the block sizes (and thus the overall sample complexity). With a fixed confidence level ($1-\\delta = 0.9$), we reported the maximum possible resulting $\\varepsilon_1$ (for optimality) and $\\varepsilon_2$ (for fairness constraint). To disentangle the effect of these two error terms, we fix one of either $\\boldsymbol{V}$ or $\\boldsymbol{N}$ and train the other one with our NPM-based algorithm. As confirmed by Figure 1 in the additional supplementary pdf file, the blocks of sizes $\\approx O(\\epsilon_1^{-2} + \\epsilon_2^{-2})$ are sufficient to achieve PAFO-learnability with errors $\\varepsilon_1$ and $\\varepsilon_2$ with probability $0.9$. Our obtained sample complexity dependencies seem to match the experiments.\n\n> **Q1. Regarding the significance of our new formulation**  \n\nPlease refer to our global response.  \n\n\n> **Q2. Do existing fair PCA algorithms satisfy PAFO-Learnability?**  \n\nWe appreciate your comment and bringing up this interesting and important point. We agree that investigating whether existing algorithms satisfy PAFO-learnability is an interesting future topic, but it is a nontrivial task. However, we want to reiterate that none of the existing fair PCA algorithms satisfy PAFO-learnability for *streaming* PCA (Definition 5.1), where the crucial part is whether the memory limitation can be satisfied; this is discussed in Section 5.2.\n \nBased on our understanding, we suspect that the fair PCA algorithms proposed in [2,3] may be PAFO-learnable in the *non-streaming* setting (with $\\Omega(d^2)$ memory). The reason for excluding [1] (SDP-based approach) is because, empirically, the algorithm proposed by [1] consistently yielded significantly sub-optimal performance regarding explained variance and downstream task accuracy compared to other fair PCA algorithms [2,3]. For further details and discussions, please refer to the experimental sections of [2,3].\n\nIn conclusion, we believe that our current approach does indeed address the memory limitation, even with a large block size (which is unavoidable for noisy power method-type algorithms), and that our theoretical guarantees will hold even with a relaxed assumption. We are open to addressing any further questions or concerns the reviewer may have. We hope that our response, including the additional experiments verifying PAFO-learnability, has properly addressed the reviewer’s concerns, and we hope that the reviewer would reconsider the score. Thank you again for your insightful reviews and comments."}]

Author rebuttal:
We sincerely thank all the reviewers for providing detailed and insightful reviews/comments/questions about our paper. We assure the reviewers in advance that all the answers and discussions provided here will be incorporated into our revised manuscript.
We are encouraged to see that the reviewers recognize the relevance of our newly proposed problem setting in fairness (SSmx, VcC6, 6AMc, GuCQ), *scalable yet simple* algorithm for our setting (6AMc), theoretical rigor (6AMc), clarity of our exposition (VcC6, 6AMc, GuCQ), and extensive investigation into the effectiveness of our algorithm (VcC6, 6AMc).

From now on, let us first provide our responses to three commonly raised questions:

### **Regarding the significance of our new formulation (VcC6, GuCQ)**

We start by elaborating on the justification of our new formulation of fair PCA (Eqn. (1)). Intuitively, the PCA projection that nullifies the mean difference and top eigenvectors of the covariance difference would result in an orthogonal representation from which any linear (or stronger) adversaries have difficulty in distinguishing between the sensitive groups. We acknowledge that this notion of fair PCA has been previously discussed in [1, 3], as well as recent advances in guarding protected attributes of word embeddings via the “Null It Out” approach [12,13]. Despite the existence of similar prior formulations, we clarify why we needed to propose another new formulation.

Our new formulation, compared to the prior ones, yields two main benefits. One is that our formulation is always feasible, unlike previous formulations [1,2,3], it allows us to define the notion of learnability for fair PCA rigorously. Another is that this makes the problem amenable to a memory-efficient streaming algorithm for fair PCA. On a more technical side, our formulation is quite similar to that of [3], but the key difference lies in the order in which the nullification is applied. [3] applies mean difference nullification first, then it applies the covariance nullification on the subspace resulting after the mean difference nullification. On the other hand, we apply both simultaneously. In Section 5.2 and Appendix C.2, we provide extensive discussions on why previous approaches to fair PCA [1,2,3] CANNOT be easily adapted to our memory-limited & streaming setting.

Especially for the rigorous definition of *learnability* in the context of fair PCA, we start by remarking that *no prior work has approached fair PCA from this perspective*, emphasizing the importance of establishing a solid statistical foundation. We firmly believe that defining learnability in this context will shed light on the number of samples required to achieve a desired output, providing valuable insights for researchers and practitioners in the field, as the PAC-learning framework has done since its introduction.

### **Strong assumptions (6AMc, GuCQ)**

While our assumptions may seem stringent, they are essential to highlight that no previous works on fair PCA (for fair representation learning) [1,2,3] have provided statistical guarantees. Consequently, these assumptions were indispensable in achieving rigorous results for our streaming fair PCA formulation. 
 
Assumption 6.1 enables us to utilize the simpler version of vector/matrix Bernstein concentrations, which require bounded random variables. This was also the case in various streaming PCA literature [5,6,7] for similar reasons, where using Bernstein concentrations was necessary. Indeed, we are sure that our sample complexity results will be retained with relaxed (but similar) assumptions by using appropriate variants of the concentration inequalities (e.g., [10]).
 
Regarding Assumption 6.2, it is crucial to assume a singular value gap for the convergence of the noisy power method. Without this assumption, the eigenvectors lose uniqueness, hindering the overall convergence.

### **Experiments (6AMc, GuCQ)**

We have also attached a supplementary pdf containing additional experimental results that support our rebuttal. Figure 1 shows synthetic results that verify our sample complexity result w.r.t. block sizes. Also, Table 2 showcases the quantitative results of comparing several fair PCA methods on the UCI Adult Income dataset, showing the efficacy of our proposed FNPM.
Due to space constraints, we report only partial results, but we will report the full results in the upcoming revised manuscript.

Lastly, we put all the relevant references for our rebuttal below.

---
[1] Olfat & Aswani, “Convex Formulations for Fair Principal Component Analysis.” AAAI 2019.  
[2] Lee et al., “Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifold.” AAAI 2022.  
[3] Kleindessner et al., “Efficient fair PCA for fair representation learning.” AISTATS 2023.  
[4] Zemel et al., “Learning Fair Representations.” ICML 2013.  
[5] Bienstock et al., “Robust Streaming PCA.” NeurIPS 2022.  
[6] Jain et al., “Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm.” COLT 2016.  
[7] Huang et al., “Streaming k-PCA: Efficient guarantees for Oja’s algorithm, beyond rank-one updates.” COLT 2021.  
[8] Hardt & Price, “The Noisy Power Method: A Meta Algorithm with Applications.” NIPS 2014.  
[9] ​​Balcan et al., “An Improved Gap-Dependency Analysis of the Noisy Power Method.” COLT 2016.  
[10] C. Jin et al., “A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm.” arXiv 2019.  
[11] Samadi et al., “The Price of Fair PCA: One Extra Dimension.” NeurIPS 2018.  
[12] Ravfogel et al., “Null It Out: Guarding Protected Attributes by Iterative Nullspace Projection.” ACL 2020.  
[13] Ravfogel et al., “Linear Adversarial Concept Erasure.” ICML 2022.  
[14] Backurs​​ et al., “Scalable Fair Clustering.” ICML 2019.  
[15] Ziko et al., “Variational Fair Clustering.” AAAI 2021.  
[16] ​​Wang et al., “Scalable Spectral Clustering with Group Fairness Constraints.” AISTATS 2023.  

Meta-review: The paper concerns fair PCA in the streaming setup. It received mostly positive evaluation from the reviewers, except for one borderline reject score.

Summary of the strengths:
- The paper introduces a new formulation of fair PCA based on the _Null It Out_ approach
- It provides a statistical framework for analyzing fair PCA in terms of PAFO-learnability
- It presents a streaming algorithm for fair PCA that addresses memory limitations. This algorithm, called Fair Noisy Power Method (FNPM), is thoroughly analyzed and shown to be PAFO-learnable. 
- Reviewers generally found the paper well-written and clear in its presentation.

Summary of the weaknesses:
- The paper lacks a clear explanation of why the new formulation of fair PCA, based on _Null It Out_, is significant or how it captures fairness compared to existing formulations. 
- Some reviewers expressed concerns about the limited technical novelty of the paper - mainly due to the fact that `offline' fair PCA turns out to be a straightforward application of the SVD. Still, developing a streaming version of fair PCA requires non trivial modifications of the original noisy power method.
- Some of the assumptions, such as Assumption 6.1, were found to be restrictive by one of the reviewers. 
- Reviewers note that the experiments primarily focus on visual aspects related to sensitive attributes, while a more quantitative evaluation of fairness would provide a more objective assessment. Also, they pointed out the lack of comparison with other fair PCA methods
- Theoretical results suggesting very large block sizes.

I believe some of the weakness were resolved in the author-reviewer discussion phase, but some of the remained - in particular, the lack of motivation for the new problem formulation.

It is clear to me that there are some concerns and limitations with the paper's contribution. Still, I think overall the paper is above the acceptance bar. I hope the authors will address all the reviewers' concerns in the final version of the manuscript.
Decision: Accept (poster)