On Socially Fair Low-Rank Approximation and Column Subset Selection
Authors: Zhao Song
Ali Vakilian
David Woodruff
Samson Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: fairness
low-rank approximation
column subset selection
Primary area: fairness

Abstract: Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. In this paper, we study the question of socially fair low-rank approximation and socially fair column subset selection, where the goal is to minimize the loss over all sub-populations of the data. We show that surprisingly, even constant-factor approximation to fair low-rank approximation requires exponential time under certain standard complexity hypotheses. On the positive side, we give an algorithm for fair low-rank approximation that, for a constant number of groups and constant-factor accuracy, runs in $2^{\text{poly}(k)}$ rather than the naive $n^{\text{poly}(k)}$, which is a substantial improvement when the dataset has a large number $n$ of observations. We then show that there exist bicriteria approximation algorithms for fair low-rank approximation and fair column subset selection that runs in polynomial time.

On Socially Fair Low-Rank Approximation and Column Subset Selection
Zhao Song
Ali Vakilian
The Simons Institute for the Theory of Computing
Toyota Technological Institute at Chicago vakilian@tiic.en
UC Berkeley
magic. limuxkde@gmail. com
David P. Woodruff
Samson Zhou
Department of Computer Science Careggi Mellon University Aaroodruf@andren cmu. cmu.edu
Department Computer Science
Texas A&M University
sansonzhou@gmail.com com
Abstract
Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. In this paper, we study the question of socially fair low-rank approximation and socially fair column subset selection, where the goal is minimize the loss over all sub pobpppppultions of the data. We show that surprisingly. even constant-facto approximation fair low-rank approximation requires exponential time under certain standard complexity hypotheses. On the positive side, we give an algorithm for fair low-rank approximation that, for constant number of groups and constant- factor accuracy, runs in (Pk time rather than the naïve poly(()), which is a substantial improvement when the dataset has a large number of observations. We then show that there exist bicriteria approximation algorithms for fair low-rank approximation and fair column subset selection that run in polynomial time.
Introduction
Machine learning algorithms are increasingly used in technologies and decision-making processes that affect our daily lives, from high volume interactions such as online advertising, e-mail filtering, smart devices, large language models, more critical processes such as autonomous vehicles, healthcare diagnostics, credit scoring, and sentencing recommendations in courts of law [Cho17, 18, BHJ 21]. Machine learning algorithms frequently require statistical analysis, utilizing fundamental problems from numerical linear algebra, especially low-rank approximation and column subset selection.
In the classical low-rank approximation problem, the input is data matrix Raxd and integral rank parameter & >> 0, and the goal is to find the best rank & approximation to A, i.e., find set of vectors in R that span a matrix B, which minimizes C(A - B) across all rank-k matrices B, for some loss function L. The rank parameter & should be chosen to accurately represent the complexity of the underlying model chosen to fit the data, and thus the low-rank approximation problem is often used for mathematical modeling and data compression.
Similarly, in the classic column subset selection problem, the goal is to choose & columns U of A so to minimize C(A UV) across all choices of V & Although low-rank approximation can reveal important latent structure among the dataset, the resulting linear combinations may not be as interpretable as simply selecting & features. The column subset selection problem is therefore
g
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

version of low-rank approximation with the restriction that the left factor must be k columns of the data matrix. Column subset selection also tends to result in sparse models. For example, if the columns of A are sparse, then the columns in the left factor U are also sparse. Thus in some cases, column subset selection, often also called feature selection, can be more useful than general low-rank approximation.
Algorithmic fairness. Unfortunately, real-world machine learning algorithms across a wide variety of domains have recently produced a number of undesirable outcomes from the lens of generalization. For example, [BS16] noted that decision-makiin processes using data collected from smartphone devices reporting poor road quality could potentially underserve poorer communities with less smartphone ownership. [KMM15] observed that search queries for CEOs overwhelmingly returned images of white men, while [BG18] observed that facial recognition software exhibited different accuracy rates for white men compared with dark-skinned women.
Initial attempts to explain these issues can largely he categorized into either "biased data" or "biased algorithms", where the former might include training data that is significantly misrepresenting the true statistics of some sub-population, while the latter might sacrifice accuracy on a specific sub-population in order achieve better global accuracy, As a result, increasingly relevant line of active work has focused on designing, fair algorithms. An immediate challenge is to formally define the desiderata demanded from fair algorithmic design and indeed multiple natural quantitative measures of fairess have been proposed [6PS16, Chol7, KMRIT 17, BHJ 21J. However, [KMR17, CPF* 17] showed that many of these conditions for fairness cannot be simultaneously achieved.
In this paper, we focus on socially fair algorithms, which seek to optimize the performance of the algorithm across all sub-populations. That is, for the purposes of low-rank approximation and column subset selection, the goal is to minimize the maximum cost across all sub-populations. For
socially fair low-rank approximation, the input is a set of data matrices A (1) E Ra1xd xd ...... A E Reex xd corresponding to groups and rank parameter k. and the goal is to determine set of l factors UI,..., U E RRd that span matrices BI)).... ..... ((),, which minimize max ||
B Due to the Eckart- Eckart-Young Mirsky theorem stating that the Frobenius loss is minimized when each A (0) projected onto the span of U U1 .... UR, the problem is equivalent to minuegexa max | (6) UTU A [ where denotes the Moore-Penrooe pseudoinverse. We remark that as we can scale the columns in each group (even each individual column), our formulation captures min-max normalized cost relative the total Frobenius norm of each group and the optimal rank-k reconstruction loss for each group.
1.1 Our Contributions and Technical Overview
In this paper, we study socially fair low-rank approximation and socially fair column subset selection.
Fair low-rank approximation. We first describe our results for socially fair low-rank approximation. We first show that under the assumption that P A NP, fair low-rank approximation cannot be approximated within any constant factor in polynomial time.
Theorem 1.1. Fair low-rank approximation is NP-hard to approximate within any constant factor.
We show Theorem 1.1 by reducing to the problem of minimizing the distance of a set of points in d-dimensional Euclidean space to all sets of dimensional lincar subspaces, which was shown by [BGK00, DTV11] ] to be NP-hard to approximate within any constant factor. In fact, [BGK00, DTVII [I] showed that a constant-facte approximation to this problem requires runtime exponential in k under a stronger assumption, the exponential time hypothesis [IPO1]. We show similar results for the fair low-rank approximation problem.
Theorem 1.2. Under the exponential time hypothesis, the fair low-rank approximation requires 2 20)) time approximate within any constant factor.
Together, Theorem 1.1 and Theorem 1.2 show that under standard complexity assumptions, cannot achieve a constant-factor approximation to fair low-rank approximation using time polynomial in n and exponential in k. We thus consider additional relaxations, such as bicriteria approximation (Theorem 1.4) or (k)ly(k) runtime (Theorem 1.3). On the positive side, we first show that for constant number of groups and constant-factor accuracy, it suffices to use runtime 20oly(k) rather

---

than the naive (2 which is a substantial improvement when the dataset has a large number of observations, i.e., n large.
Theorem 1.3. Given an accuracy parameter E E (0. 1), there exists algorithm which outputs
V E k such that with probability at least 3. max ||A (V) | S (1 E) veRAaa max || (0) ViV - [r...
r. The algorithm uses runlime _ poly(n) (20) for
Ei= ny and N poly (e, k, :)-
Next, we show that there exists bicriteria approximation algorithm for fair low-rank approximation that uses polynomial runtime.
Theorem 1.4. Given a trade-off parameter E (0,1), there exists an algorithm that outputs V TRed for L = O (k<log log (log d)) such that with probability least? 2 3'
|A A A - 10. 2// (A(log log k)ol d))- iE[0
min VERoxd iE[!]
The algorithm uses runtime polynomial in n and d.
The algorithm for Theorem 1.4 substantially differs from that of Theorem 1.3. For one, we can no longer use polynomial system solver, because it would be infeasible to achieve polynomial runtime. Instead, we observe that for sufficiently large p. we have max ||x||<< = (1 = |>||>||
1/p
and thus focus on optimizing minver--x (Eieqa (V
However, the terms
|| Vvvv - A IE are difficult to handle, so we apply Dvoretzky's Theorem, i.e., Theorem 3.2, to generate matrices G and H that (1 <)|lHHH|| s ||]] S (1 GMHH| Ip. for all matrices M Rnxd so that it suffices approximately solve minxeR*xa |GAHSX GAH for A ( o A (1),
Although low-rank approximation with Lp loss cannot be well-approximated in polynomial time, we recall that there exists matrix S that samples a "small" number of columns of A to provide coarse bicriteria approximation to Lp low-rank approximation [WY23]. However, we require a solution with dimension d and thus seek to solve the regression problem minx |AASSX GAH Thus, we consider a Lewis weight sampling matrix T such that
1I TGAHSX TGAH p S |GAHSX - GAHI,, P S TGATSS - TGAH p-
and again note that (TGAHS) is the closed-form solution to the minimization problem minx |TGASSX - -GAHH|
which only provides a small distortion to the T,p regression problem, since TGAH has small number of rows due to the dimensionality reduction. We then observe that by Dvoretzky's 's Theorem, (TGAHS)'TC. is a "good" approximate solution to the original fair low-rank approximation problem. Given (0, 1). the success probabilities for both Theorem 1.3 and Theorem 1.4 can be boosted arbitrary 1 8 by taking the minimum of O (log !) independent instances of the algorithm, at the cost of increasing the runtime by the same factor.
Fair column subset selection. We next describe our results for fair column subset selection. We give a bicriteria approximation algorithm for fair column subset selection that uses polynomial runtime.
Theorem 1.5. Given input matrices A (6) E Rn:xd with n = En there exists an algorithm that selects a set S of k' O (k log k) columns such that with probability least &. S is O (Molog log (1og d) -approximattion to the fair column subset selection problem. The algorithm uses runtime polynomial in n and d.
The immediate challenge in adapting the previous approach for fair low-rank approximation to fair column subset selection is that we required the Gaussian matrices G, to embed the awkward maximum of Frobenius losses min max;ete] ||. || into the more manageable Lp loss min || Ipp through GAH. However, selecting columns of GAH does not correspond to selecting columns of the input matrices A (1),... (1),...,(())
Instead, we view the bicriteria solution V from fair low-rank approximation as a good starting point for the right factor for fair low-rank approximation. Thus we consider the multi-response regression problem max ming ( V - A (0) We then argue through Dvoretzky's 's theorem
3

---

that a leverage score sampling matrix S that samples O (k log k) columns of V will provide good approximation to the column subset selection problem. We defer the formal exposition to Section 4.
Empirical evaluations. Finally, in Section 5, we perform a number of experimental results on socially fair low-rank approximation, comparing the performance of the socially fair low-rank objective values associated with the outputs of the bicriteria fair low-rank approximation algorithm and the standard (non-fair) low-rank approximation that outputs the top k right singular vectors of the singular value decomposition.
Our experiments are on the Default of Credit Card Clients dataset [YL09], which is common human- centric data used for benchmarks on fairness, e.g., see [STM* + 18]. We perform empirical evaluations comparing the objective value and the runtime of our bicriteria algorithm with the aforementioned baseline, across various subsample sizes and rank parameters. Our results demonstrate that our bicriteria algorithm can perform better than the standard low-rank approximation algorithm across various parameter settings, even when the bicriteria algorithm is not allowed a larger rank than the baseline. Moreover, we show that our algorithm is quite efficient and in fact, the final step of extracting the low-rank factors is faster than the singular value decomposition baseline due to a smaller input matrix. All in all, our empirical evaluations indicate that our bicriteria algorithm can perform well in practice, thereby reinforcing the theoretical guarantees of the algorithm. Finally, we give a number of additional experiments on synthetic datasets, in Appendix D.
Paper organization. We first described a number of related works in Section 2. We detail our socially fair low-rank approximation algorithms in Section 3 and our socially fair column subset selection algorithms in Section 4. We defer all proofs to the supplementary material. We present our experiments in Section 5 and Appendix D. The reader may also find it helpful to consult Appendix A for standard notation used in our paper and additional preliminaries.
2 Related Work
Initial insight into socially fair data summarization methods were presented by [STM*18] where the concept of fair PCA was explored. This study introduced the faimess metric of average reconstruction loss, expressed by the loss function loss( A, B) == =IAA- - B k-dimensional subspace that minimizes the loss across the groups, with A a representing the best rank-k approximation of A. Their proposed approach, in a two-group scenario, identifies a fair PCA of up to k + dimensions that is not worse than the optimal fair PCA with & dimensions. When extended to l groups, this method requires an additional k + 8 - 1 dimensions. Subsequently, [TSS+ + 19] explored fair PCA from distinct objective perspective, seeking projection matrix P optimizing min || (0) Pl A pivotal difference between these works and ours our focus on the reconstruction error objective, a widely accepted objective for regression and low-rank approximation tasks. Alternatively, 10A19, LKO KDRZ23] explored different formulation of fair PCA. The main objective is to ensure that data representations are not influenced by demographic attributes. In particular, when a classifier is exposed only to the projection of points onto the k-dimensional subspace, it should be unable to predict the demographic attributes.
| - Ax ll?.. aiming to identify
Recently, [MOT24] studied fair column subset selection objective similar to ours, focusing on the setting with two groups (i.e.,& f= 2). They established the problem's 's hardness and introduced a polynomial-tine time solution that offers relative-error guarantees while selecting column subset of size O (k)).
For fair regression, initial research focused on designing models that offer similar treatment to in- stances with comparable observed results by incorporating fairness regularizers [BHJ+17] However, in [ADW19], 19]. the authors studied fairness notion closer to our optimization problem, termed as "bounded group loss". In their work, the aim is to cap each group's loss within a specific limit while also optimizing the cumulative loss. Notably, their approach diverged from ours, with focus on the sample complexity and the problem's 's generalization error bounds.
[AAK 22] studied similar socially fair regression problem under the name min-mac max regression. In their setting, the goal is to minimize the maximum loss over a mixture distribution, given samples from the mixture; our fair regression setting can be reduced to theirs. [AAK+22] observed that a maximum of norms is convex function and can therefore be solved using projected stochastic gradient descent.

---

The term "socially fair" was first introduced in the context of clustering, aiming to optimize clustering costs across predefined group sets ABB21], In subsequent studies, tight upproximation algo- rithms [MV21, CMV22J, FPT approaches [GJ23], and bicriteria approximation algorithms [GSV22] for socially fair clustering have been presented.
3 Socially Fair Low-Rank Approximation
In this section, we consider algorithms and hardness for socially fair low-rank approximation. Let Mi....,, ny positive integers and for each E [e]. let A (a) E II Then for norm || I we define the fair low-rank approximation problem to be minyeeted maxie( || (OViV - (+).
3.1 (1 + AAprrxxmmmnn Algorithm for Fair Low-Rank Approximation
We first give (1 (1+ aapprooximati algorithm for fair low-rank approximation that uses runtime poly(n) (20)0()) for = Ei= n2 and N = poly (e, k, 2
The algorithm first finds a value that is an 6-approximation to the optimal solution, i.c., minverexd maxi[[]] | Avviv - (01 is at most a S é. minveaexd maX || (Avivv A 1l1.. We then repeatedly decrease by (1 +) while checking if the resulting quantity is still achievable. To efficiently check a is achievable, we first apply dimensionality reduction to each of the matrices by right-multpllyngg by affine embedding matrix S, so that
(1 (I= A 1 V - AIS (1+ ++++)IIAA VVV AE.
for all rank & matrices V and all E [e].
Now if we knew V, then for each E [4]. we can find x(1) minimizing |X ( - A S and the resulting quantity will approximate || viv - A 11 In fact, we know that the minimizer is (A (A() () (VS) through the closed form solution to the regression problem. Let ( be defined so
that (A (1) (V has orthonormal columns, so that
[I(A (1) () ()(S)) R A
A
S
min XX VS - A X
and so we require that if is feasible, then 2 [I(A (V)) (V
A S Unfortunately, we do not know V. so instead we use a polynomial solver to check whether there exists such a V. We remark that similar guessing strategies were employed by [RSW16, KPRW19, BWZ19, VVWZ23] and in particular, [RSW16] also uses polynomial system in conjunction with the guessing strategy. Thus we write Y VS and its pseudoinverse W (VS)t and check whether there exists satisfying assignment to the above inequality, given the constraints (1) YWY Y. (2) WYW W, and (3) A ( (WR())
(6) has orthonormal columns. Note that since V E exd then implementing the polynomial solver naïvely could require kd variables and thus use 20(a)) runtime. Instead, we note that we only work with VS, which has dimension le x m for m ( log so that the polynomial solver only uses (moly(mk) time.
We now show a crucial structural property that allows us to distinguish between the case where a guess for the optimal value OPT exceeds + OPT is smaller than (1 OPT by simply looking at a polynomial system solver on an affine embedding.
Lemma 3.1. Let E xgd the optimal solution to the fair low-rank approximation problem for inputs A ())..... ())...,,A(* (t), where A Rrexd and suppose OPT max ( A ( II.
..... Let S be an affine embedding for V and let W (VS)t E kxm_ For E [1, let 9
A A (SSW< e B and ( E R be defined so that A (WSRR (6) has orthonormal columns. If SWRR
2 (P+ then for each i E [6]. 2 [|(A SWRR
(1 A (6) A 1) Ifa <
(1 (1PT),OPT,
OPT, then there exists i E [6]. such that [I ( SWR (A SWR (1) TA A 11)
5

---

Algorithm Input to polynomial solver
( (1++))approxiimatin for fair low- rank approximation
Algorithm
Input: A J....y (4,, S.
Output: Feasibility of polynomial system
Input:
A E [R=; for all i E [4] rank pa-
I: Polynomial variables
2: Let Y = (VS) R be mk variables
rameter k accuracy parameter
(0,
3: Let W = (VS)1 E mR be mk variables
Output: (1+ aaprroxiiimiaino for fair LRA
1: Let a be an E-approximation for the fair LRA problem
4: Let R E &xk for each [e] be th?
variables
2: Let S be generated from a random affine embedding distribution
5: System constraints
6: YWY =Y, WYW W
3: while Algorithm I on input A A ...., A()
7: A SWR! (i) has orthonormal columns
8: a 2 (I (1) SWR SWRR O)) (
S. and a does not return 1 do
4: Let V be the output of Algorithm on input A ( ( (1) S, and
A I?
9: Run polynomial system solver
5: a 1+2
a
If feasible, output V
(A ASSW"W A Otherwise, output
6: end while
7: Return V
3.2 Bicriteria Algorithm
To achieve polynomial time for our bicriteria algorithm, we can no longer use polynomial system solver. Instead, we observe that for sufficiently large p. we have max ||x||>> (1 =)|[>||>>
Thus, in place of optimizing minverexa max
V A we instead optimize
1/p
ee (Eietg | A
However, the terms ||A V A ( Il are un-
wieldy to work with. Thus instead use Dvoretzky's Theorem, i.e., Theorem 3.2, to embed L2 into
Lp. by generating matrices and H so that (1 E) [MGHH] I |M| S (1 + |GMH|| for
all matrices M E Rexd
Now, writing A - o o... ( it suffices to approximately solve minxeR=xd | |GAHSX GAH Unfortunately, low-rank approximation with I,, loss still cannot be approximated to (1 (1+ s)-fctor in polynomial time, and in fact GAH has dimension n' d' with n'' 2 and d' > d. Hence, we first apply dimensionality reduction by appealing to a result [WY23] showing that there exists matrix S that samples "small" number of columns of A to provide coarse bicriteria approximation to Lp low-rank approximation. Now to lift the solution back to dimension d, we would like to solve regression problem minx GAHSSX - GAH pp- To that end, we consider Lewis weight sampling matrix such that
TGAHSXX TGAH S |GAHSX - GAHI, S TGAHSS - TGAH
We then note that (TGAHS)'TGA is the minimizer of the problem min TGAHSX TGAH|| |F. which only provides small distortion the Lp regression problem, since TGAH has small number of rows due to the dimensionality reduction. By Dvoretzky's 's Theorem, we have that (TGAHS) TTA is "good" approximate solution to the original fair low-rank approximation problem. The algorithm appears in full in Algorithm 3.
Algorithm 3 Bicriteria approximation for fair low-rank approximation
Input: ( E Rn: xd for all i [6], rank parameter > 0, trade-off parameter e E (0, 1)
Output: Bicriteria approximation for fair LRA
1: Generate Gaussian matrices G 1g" xn H. E jaddd' through Theorem 3.2
2: Let S E IR" Z Rx be the output of Theorem 3.3 on input GAH
3: Let T sx be a Lewis weight sampling matrix for GAHSX GAH
4: Let V (TGAHH))(TC)) (TGA)
5: Return V

---

We use the following notion of Dvoretzky's 's theorem to embed the problem into entrywise Lp loss. Theorem 3.2 (Dvoretzky's Theorem, e.g., Theorem 1.2 in [PVZ17], Fact 15 [SW18]). Ler p 2 be a parameter and let
nnn g (up)a/2
8 8 (Cp) 2n 26--1)
m m(n.p.E)
8 (Cp) n 200-1)
neta pai2ga7z
log
2/2
p <
Then there exists family G of random scaled Gaussian matrices with dimension m such that for
G G, with probability at least simultaneously for all y IR", (1 (1-+) 1lyy z ||yy|p S
(1 +)llll2,
We use the following algorithm from [WY23] to perform dimensionality reduction so that switching between L2 and Lp loss will incur smaller error. See also [CGK 17].
Theorem 3.3 (Theorem 1.5 in [WY23]). Let A E Raxd and let k: 2 1. Let O log log k). Then there exists a polynomial-Mne hime algorithm that outputs a matrix E Bdxx that samples l = O (k(log log (logg d)) columns of A and a matrix E RRxd such that ||A - ASZI] S 2F. O (VB) minuexex+ Ve xd ||A - UV
We recall the following construction to use Lewis weights to achieve an I, subspace embedding.
Theorem 3.4 ([CP15)). Ler (0,1) and p Let A Raxd and O (dv/2 log d). Then there exists polynomial-time algorithm that outputs matrix S E Rax that samples and reweights s rows of A, such that with probability at least 0.99, simultaneously for all x E R Ax
1| S SAx 1B S + Ax|
We then show that Algorithm provides a bicriteria approximation.
Lemma 3.5. Let V be the output of Algorithm 3. Then with probability at least TO max
(f is most (.. (e..2//.C (k(log log (log d)) max4ete || 10 (
A ||r where c the trade-off parameter input.
Since the generation of Gaussian matrices and the Lewis weight sampling matrix both only require polynomial time, follows that our algorithm uses polynomial time overall. Hence, we have Theorem 1.4.
4 Socially Fair Column Subset Selection
In this section, we consider socially fair column subset selection, where the goal identify a matrix C Baxk that selects &o columns minimize millgeRá**, /|CC o B()) maxield] |A (6) CB A |
Algorithm 4 Bicriteria approximation for fair column subset selection
Input: ( E R.= for all i [4]. rank parameter 1: > 0, trade-off parameter e E (0, 1) Output:
Bicriteria approximation for fair column subset selection 1: Acquire V from Algorithm
2: Generate Gaussian E R=''x xm through Theorem 3.2
3: Let S E pdxk' be a leverage score sampling matrix that samples k' = =O (k log k) columns of V
4: ( = St (V) for all i E [e]
5: Return A S (MO)
We first provide preliminaries on leverage score sampling.
Definition 4.1. Given matrix M E Raadd define the leverage score os of each row m; with
i [n] by (MMMM) Equivalently, for the singular value decomposition M UEV, the leverage score of row m, is also the squared row norm of u,
7

---

We recall in Appendix C that it can be shown the sum of the leverage scores for an input matrix M Raxd is upper bounded by and moreover, given the leverage scores of M. it suffices to sample only O (d log n) rows of M to achieve a constant factor subspace embedding of M. Because the leverage scores of M can be computed directly from the singular value decomposition of M, which can be computed in O (nd + dn²)) time where w is the exponent of matrix multiplication, then the leverage scores of M can be computed in polynomial time.
Finally, we recall that to provide a constant factor approximation to Lp regression, it suffices to compute a constant factor subspace embedding. e-g.. through leverage score sampling. The proof is through the triangle inequality and is well-known among the active sampling literature [CP19, PPP21, MMWY22, MMM 22. MMM e.g., a generalization of Lemma 2.1 in [MMM 22]. For completeness, we provide the proof in Appendix C.
Lemma 4.2. Given a matrix M E Ruxd let S be a matrix such that for all x E I& and v E RR"
11 |
13 - SMM - 12
Mx
E [[[SV]]] = 1|112
12
For fixed B E Raxm where B = bj o... bm with bj E IR" for i E [m], let x, = (SM)(((b)) Let X Xi Xm. Then with probability at least 0.97, ||MX BlI2 S 99 minx ||XX Bl2a.
We now give the correctness guarantees of Algorithm 4. Lemma 4.3. Let S,M ,..,,, (M.,(( be the output of Algorithm 4. Then with probubility at least 0.8, max4e (M(() A is at most C 2// O (k(log log klooog d)) minveRexd ( VIA A 6
We also have the following runtime guarantees on Algorithm 4. Lemma 4.4. The runtime of Algoritim is poly(n, d).
By combining Lemma 4.3 and Lemma 4.4, we have Theorem 1.5.
5 Empirical Evaluations
In this section, we describe our empirical evaluations for socially fair low-rank approximation on real-world datasets.
Credit card dataset. We used the Default of Credit Card Clients dataset [YL09], which has 30,000 observations across 23 features, including 17 numeric features. The dataset is a common human- centric data for experiments on fairness and was previously used as a benchmark by [STM+18 18] for studies on fair PCA. The study collected information from various customers including multiple previous payment statements, previous payment delays, and upcoming bill statements, well as if the customer was able to pay the upcoming bill statement or not, i.e., defaulted on the bill statement. The dataset was accessed through the UCI repository [Yeh16].
Experimental setup. For the purposes of reproducibility, our empirical evaluations were conducted using Python 3.10 using 64- operating system on an AMD Ryzen 5700U CPU, with 8GB RAM and 8 cores with base clock 1.80 GHz. We compare our bicriteria algorithm from Algorithm against the standard non-fair low-rank approximation algorithm that outputs the top A right singular vectors from the singular value decomposition. Gender was used as the sensitive attribute, so that all observations with one gender formed the matrix A (1) and the other observations formed the matrix A (2). As in Algorithm 3, we generate normalized Gaussian matrices G and H and then use L, Lewis weight sampling to generate a matrix T. We generate matrices T, G. and H with a small number of dimensions and thus do not compute the sampling matrix S but instead use the full matrix. We first sampled a small number s of rows from A (1) and A (2) and compared our bicriteria algorithm to the standard non-fair low-rank approximation algorithm baseline. We plot the minimum ratio for s E (2. 21}. A 1, and p over 10, 000 iterations for each setup Figure la. Similarly, we plot both the minimum and average ratios for s 1000, k E {1, 2, 7, 8) and p = 1 over 200 iterations in Figure 1b, where we permit the bicriteria solution to have rank 2k. Finally, we compare the runtimes of the algorithms in Figure Ic, separating runtimes for our bicriteria into the total nuntime bicritt t1 that includes the process of generating the Gaussian matrices and performing the Lewis weight sampling, as well as the runtime bicrit2 for the step for extracting the factors
8

---

similar to SVD, which measures the runtime for extracting the factors. Across all experiments in Figure I, we used Gaussian matrices G with 30 rows and H with 30 columns.
3
VAI
(a) Costs over subsampled data
(b) Costs over different ranks k
(c) Runtime evaluations
Fig. 1: Empirical evaluations on the Default Credit dataset.
Results and discussion. Our empirical evaluations that our bicriteria algorithm can perform significantly better for socially fair low-rank approximation, without allowing for more than & factors. In particular, all ratios in Figure la and most ratios in are less than 1, indicating that the cost of our algorithm is less than the cost of the baseline, so that smaller ratios represent better performance. In fact, in some cases the ratio was less than 0.6, demonstrating the superiority of our algorithm. Finally, we show in Figure I that due to the small number of rows acquired by Lewis weight sampling, the final extraction of the factors is significantly faster by our algorithm. However, the main runtime bottleneck is the process of generating the Gaussian matrices and performing the subsequent Lewis weight sampling. As we use an iterative procedure to approximate the I.p Lewis weights with 10 iterations, this translates to computing 10 matrix inversions. Hence it is likely this gap can be improved with further optimizations to Lewis weight approximation algorithms. We provide details on a number of additional empirical evaluations Appendix D. In particular, we describe additional experiments on socially fair low- rank approximation synthetic datasets and perform a quick investigation into socially fair linear regression, as additional motivation for studying fairness for randomized numerical linear algebra.
simple proof-of-concepp demonstrating
Conclusion
In this paper, study algorithms for socially fair low-rank approximation and column subset selection. Although we show that even a constant-factor approximation to fair low-rank approximation requires exponential time under certain standard complexity hypotheses, we give an algorithm that is a substantial improvement over the naïve approach for any constant number of groups. We also give bicriteria approximation algorithms for fair low-rank approximation and fair column subset selection that runs in polynomial time. Finally, we perform a number of empirical evaluations serving as simple proof-of ooof-of-concept demonstrating the practical nature of our theoretical findings. is our hope that our work is an important step toward better understanding of fairnsss in numerical linear algebra.
Our work also leads number of interesting future directions. For example, there are various notions of fairness, including (1) disparate impact, which requires that the output of an algorithm respects a desired distribution that protects various subpopulations in the decision-making pro- cess [CKLV17, RS18, BIO+19, BCFN19, BGK 18, AEK 20, EBTD20, DMV22, CXZC24], (2) individual fairness, where each element should incur cost that is within reasonable amount with respect to the overall dataset [JKL20, MV20, NC21, VY22]. or (3) representative fairness, where the number of representative elements of each subpopulation should be relatively bal- anced [KAM19, JNN20, AKSZ22, NNJ22, TGOO22, HMV23]. A natural direction is the capa- bilities and limitations of randomized linear algebra for other notions of fairesss Another question the efficient construction of e-coresets with minimal size for socially fair subset selection. Finally, one can ask whether similar guarantees are possible in settings whether the input matrix is not centralized, but rather for example, distributed or arrives over a data stream. Indeed, there are known analogs [CDW18 18, BDM+ +L1, WY23] for a number of the central tools used the main algorithms of this paper.

---

Acknowledgements
David P. Woodruff was supported in part by Simons Investigator Award and NSF CCF-2335412. Samson Zhou is supported in part by NSF CCF-2335411. The work was conducted in part while Ali Vakilian, David Woodruff and Samson Zhou were visiting the Simons Institute for the Theory of Computing as part of the Sublinear Algorithms program.
References
[AAK*22] Jacob D. Abernethy, Pranjal Awasthi, Matthäus Kleindessner, Jamie Morgenstern, Chris Russell, and Jie Zhang. Active sampling for min-max faimess. In International Conference on Machine Learning. ICML, pages 53-65, 2022.
[ABV21] Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasuubramanian. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM conference fairness, accountability, and transparency, pages 504-514, 2021.
[9DW19] Alckh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and reduction-basse algorithms. In International Conference Machine Learning, pages 120-129. PMLR, 2019.
[AEK*20] Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mah- dian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang. Fair hierarchical clustering. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS, 2020.
[AKSZ22] Haris Angelidakis, Adam Kurpisz, Leon Sering, and Rico Zenklusen. Fair and fast k-center clustering for data summarization. In International Conference on Machine Learning, ICML, pages 669-702, 2022.
[BCFN19] Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32, 2019.
20) Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium Foundations of Computer Science, FOCS, pages 517-528, 2020.
[BG18] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference Fairness, Accountability and Transparency, FAT, volume 81 of Proceedings of Machine Learning Research, pages 77-91, 2018.
[BGK00] Andreas Brieden, Peter Gritzmann, and Victor Klee. Inapproximability of some geometric and quadratic optimization problems. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, pages 96-115, 2000.
[BGK 18] Ioana O Bercea, Martin GroB, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R Schmidt, and Melanie Schmidt. On the cost essentially fair clusterings. arXiv preprint
2018.
[BH++1] 17] Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. A convex framework for fair regression. arXiv preprint arXiv:1706. (tf::1766.02099, 2017.
[BH]+21] Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3 2021.
[BI0+19] Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. International Conference on Machine Learning, pages 405-413. PMLR, 2019.
10

---

[BPR96] Saugata Basu, Richard Pollack, and Marie-Françoise Roy. On the combinatorial and algebraic complexity of quantifier elimination. J. ACM, 43(6):1002-1045, 1996.
[BS16] Solon Barocas and Andrew D Selbst. Big data's disparate impact. California law review, pages 671-732, 2016.
[BWZ19] Frank Ban, David P. Woodruff, and Qiuyi (Richard) Zhang. Regularized weighted low rank approximation. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems, NeurlPS, pages 4061-4071. 2019.
[CDW18) [8] Graham Cormode, Charlie Dickens, and David P. Woodruff. Leveraging well- conditioned bases: Streaming and distributed summaries in minkowski p-norms. In Proceedings of the 35th International Conference on Machine Learning, ICML, Pro- ceedings of Machine Learning Research, pages 1048-1056, 2018
[CHM+15) Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means elustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 163-172, 2015.
[CGK+17] Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David Woodruff. Algorithms for lp low-rank approximation. In Proceedings of the 34th International Conference on Machine Learning, ICML, pages 806-814, 2017.
[Cho17] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):133-163 2017.
[CKLV17] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair cluster- ing through fairlets. In Advances in Neural Information Processing Systems 30; Annual Conference Neural Information Processing Systems, pages 5029-5033 2017.
[CMM17] Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Tiehty-Figtth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1758- 1777, 2017.
[CMV22] Eden Chlamtáē, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Proceedings of the 2022 annual ACM-SIAM symposium on discrete algorithms (SODA), pages 2664-2683. SIAM, 2022.
[CP15] Michael B. Cohen and Richard Peng. Lp row sampling by lewis weights. In Proceed- ings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 192- 2015.
[CP19] Xue Chen and Eric Price. Active regression via linear-sample sparsification. In Conference Learning Theory, COLT, pages 663-695, 2019.
[CPF+17] Sam rithmic decision making and the cost of fairness. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 797-806, 2017.
Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algo-
[CXZC24] Wenjing Chen, Shuo Xing, Samson Zhou, and Victoria G. Crawford. Fair submodular cover. CoRR, 24022407704444 2024.
[DMM06a] Petros Drineas, Michael W. Mahoney, and Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column based methods. In Approximation, Randomizution, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimiza- tion Problems, APPROX and 10th International Workshop on Randomization and Computation, RANDOM, Proceedings, pages 316-326, 2006.
11

---

[DMM06b] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-row couuum--oww-ueed based methods. In Algorithms ESA 2006, 14th Annual European Symposium, Proceedings, pages 304-314, 2006.
[DMV22] Zhen Dai, Yury Makarychev, and Ali Vakilian. Fair representation clustering with several protected classes. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 814823, 2022.
[DTV11] Amit Deshpande, Madhur Tulsiani, and Nisheeth K. Vishnoi. Algorithms and hardness for subspace approximation. In Proceedings of the Aventy-Secome Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pages 482-496 2011.
[EBTD20] Seyed A. Esmacili, Brian Brubach, Leonidas Tsepenckas. and John Dickerson. Prob- abilistic fair clustering. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS, 2020.
[EY36] Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211-218, 1936.
[Fos53] Frederic G Foster. On the stochastic matrices associated with certain queuing processes. The Annals of Mathematical Statistics, 24(3):355-360 1953.
[GJ23] Dishant Goyal and Ragesh Jaiswal. Tight FPT approximation for socially fair clustering. Information Processing Letters, 182: I 06383, 2023.
[GSV21] Mchrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 438 448, 2021.
[GSV22] Mehrdad Ghadiri, Mohit Singh, and Santosh S Vempala. Constant-factor approximation algorithms for socially fair k-clustering. arXiv preprint 2rXiv:2206./12100 2022.
[HMV23] Sedjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian. Approximation algo- rithms for fair range clustering. In International Conference on Machine Learning. pages 13270-13284, PMLR, 2023.
[HPS16] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learn ing. In Advances in Neural Information Processing Systems 29: Anmual Conference on Neural Information Processing Systems, pages 3315-3323, 2016
[IPO1] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001.
[JKL20] Christopher Jung, Sampath Kannan, and Neil Lutz. Service in your neighborhood: Fairness in center location. In Aaron Roth, editor, 1st Symposiun on Foundations of Responsible Computing, FORC 2020, pages 5:1-5:15, 2020.
[JL++21] Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, and David P. Woodruff. Streaming and distributed algorithms for robust column subset selection. In Proceedings of the 38th International Conference on Machine Learning. ICML, volume 139 of Proceedings of Machine Learning Research, pages 4971-4981, 2021.
[JN220] Matthew Jones, Huy Nguyen, and Thy Nguyen. Fair k-centers via maximum matching. In International conference on machine learning, pages 4940-4949, PMLR, 2020.
[JTT13] Gabriela Jeronimo, Daniel Perrucci, and Elias Tsigaridas. On the minimum of a polynomial function on basic closed semialgebraic set and applications. SIAM J. Optim., 23(1):241 2013.
[KAM19] Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstemn Fair k-center cluster- ing for data summarization. In Proceedings of the 36th International Conference on Machine Learning, ICML, pages 3448-3457, 2019.
12

---

[KDRZ23] Matthäus Kleindessner, Michele Donini, Chris Russell, and Muhammad Bilal Zafar. Efficient fair pea for fair representation learning. In International Conference on Artificial Intelligence and Statistics, pages 5270- PMLR, 2023.
[KLL*18] Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mul- lainathan. Human decisions and machine predictions. The quarterly journal of eco- nomics, 133(1):237-22) 2018.
[KMM15] Matthew Kay, Cynthia Matuszek, and Sean A. Munson. Unequal representation and gender stereotypes in image search results for occupations. In Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, Cill, pages 3819-3828, 2015.
[KMR17] Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In 8th Innovations in Theoretical Computer Science Conference, ITCS, pages 43:1-43:23, 2017.
[9] Ravi Kumar, Rina Panigrahy, Ali Rahimi, and David P. Woodruff. Faster algorithms for binary matrix factorization. In Proceedings of the 36th International Conference Machine Learning, ICML, pages 3551-3559, 2019.
[LKO*22] Junghyun Lee, Gwangsu Kim, Mahbod Olfat, Mark BaasegawaJJohnson and Chang D Yoo. Fast and efficient mmd-based fair pea via optimization over stiefel manifold. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7363-7377 2022.
[Mag10] 10] Malik Ismail. Row sampling for matrix algorithms via non-commutative bernstein bound. CoRR, abs/1008.00$$ 2010.
[MMM 22]
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou. Fast regression for structured inputs. In The Tenth International Conference on Learning Representutions, ICLR, 2022.
[MMM+23 23] Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou. Near-linear sample complexity for Lp polynomial regression. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 3959-4025, 2023.
[MMWY22] Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda. Active linear regression for Lp norms and beyond. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 744-753, 2022.
[MOT24] Antonis Matakos, Bruno Ordozgoiti, and Suhas Thejaswi. Fair column subset selection. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2189-2199, 2024.
[MV20] Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering, In Proceedings of the 37th International Conference on Machine Learning, ICML, pages 6596-6596. 2020.
[MV21] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair cluster- ing. In Conference on Learning Theory, pages 2246-3264, PMLR, 2021.
[NC21] Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k-clustering. Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS, pages 13340- 13351, 2021.
[NN]22] Huy Nguyen. Thy Nguyen, and Matthew Jones. Fair range k-center. arXiv preprint arXiv:2207. 1337, 2022.
[OA19] 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, 2019.
13

---

[PPP21] Aditya Parulekar, Advait Parulekar, and Eric Price. L1 regression with lewis weights subsampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 49:1-49:21, 2021.
[PVZ17] Grigoris Paouris, Petros Valettas, and Joel Zinn. Random version of dvoretzky's theorem in Pg. Stochastic Processes and their Applications, 127(10)31177-3227, 2017.
[Ren92a] James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-alse semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of symbolic computation, 13(3):555-999 1992.
[Ren92b] James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part ii: The general decision problem. preliminaries for quantifier climination. Journal of Symbolic Computation, 13(3):301-322 1992.
[RS18] Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pages 96:1-96: 4, 2018
[RSW16] Ilya P. Razenshteyn, Zhao Song, and David P. Woodruff. Weighted low rank approxi- mations with provable guarantees. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 250-263, 2016.
[STM+18] Samira Samadi, Uthaipon Tantipongpipar, Jamie H Morgenstern, Mohit Singh, and Santosh Vempala. The price of fair pea: One extra dimension. Advances in neural information processing systems, 31, 2018.
[SW18] Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 59th IEEE Annual Symposium Foundations of Computer Science, FOCS, pages 802-813, 2018.
[TGO022] Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Michal Osadnik. Clustering with fair-center representation: Parameterized approximation algorithms and heuristics. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1749-1759, 2022.
[TSS+19] Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh, Jamie H Morgenstern, and Santosh Vempala. Multi-criteria dimensionality reduction with applications to fairness. Advances in neural information processing systems, 32, 2019.
[VVWZ23] Ameya Velingker, Maximilian Vötsch, David Woodruff, and Samson Zhou. Fast (1 + e)-approximation algorithms for binary matrix factorization. In International Conference on Machine Learning, ICML, pages 11952-34977, 2023.
[VY22] Ali Vakilian and Mustafa Yalciner. Improved approximation algorithms for individually fair clustering. In International conference on artificial intelligence and statistics, pages 8758-8779. PMLR, 2022.
[Woo14] David P. Woodruff. Sketching tool for numerical linear algebra. Found. Trends Theor. Comput. Sci., 10(1-2):1-177, 2014.
[WY23] David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pages 1802-1813, 2023.
[Ych16] I-Cheng Yeh. Default of Credit Card Clients. UCI Machine Learning Repository, 2016. DOI:
[YL09]] I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2):2473-2480, 2009.
14

---

A Preliminaries
We use the notation [ni] represent the {I,..., ni for an integer 2 We use the notation poly(n) to represent a fixed polynomial in and we use the notation polylog(n) to represent poly(log n)). We use poly(n) denote a fixed polynomial in and polylog(n) to denote poly(log n). We say an event holds with high probability if it holds with probability 1 poly(n)
We generally use bold-font variables to represent vectors and matrices, whereas we use default-font variables to represent scalars. For matrix A E Raxd we use A; represent the i-th row of and
A represent the j-th column of A. We A represent the entry in the i-th row and j-th column of A. For p 2 1, we use
1/P
ΣΣ
||||,
A
to represent the entrywise Lp norm of A and we use
ΣΣ jEId
A F =
represent the Frobenius of A, which is simply the entrywise L2 norm of A. We define the l.p.q of as the hp norm the vector consisting of the bg norms of each row of A, so that
1/D
|| =
Σ iE(n]
Σ (Arr)² jE[d]
Similarly, we use [All(p.)) denote the Lp norm of the vector consisting of the L, norms of each column of A. Equivalently, we have ||
(lp.) = | lln.q so that
p/u
1/p
(p
(A
jE(d]
(E(m)
We use to represent vertical stacking of matrices, so that
A (1)
(1) o A (m)
A (m)
For a matrix A E Rexd of rank k. its singular decomposition A UEV, where E Raxk Σ E Rexk V Rexd, that the columns of U orthonormal and the rows of V are orthonormal. The columns of are called the left singular vectors of A and the rows of V are called the right singular vectors of A.
A.1 Regression and Low-Rank Approximation
In this section, we briefly describe some common techniques used to handle both regression and low- rank approximation, thus presenting multiple unified approaches for both problems. Thus in light of the abundance of techniques that can be used to handle both problems, it somewhat surprising that socially fair regression and socially fair low-rank approximation exhibit vastly different complexities.
Closed form solutions. Given the regression problem minxer |Ax - bll2 for an input matrix A E Roxd and label vector E R", the closed form solution for the minimizer is ib argminxeRd ||Ax bll2, where At is the Moore-Penrose pseudoinverse of A. Specifically, for matrix A paxd written in its singular value decomposition A UΣv. have At
15

---

VTE-'UT, In particular, for if A has linearly independent rows, then At = A A (AAT)-! On the other hand, has linearly independent columns, then A = (ATA)-IAT.
Similarly, given an imput matrix A and rank parameter & > O, there exists closed form solu- tion for the minimizer argmin ||A - AV AVi VIl. Specifically, by the Eckart- Eckart-Young-Minn Young-Mirsky theorem [EY36], the minimizer is the top k right singular vectors of A.
Dimensionality reduction. We next recall a unified set of dimensionality reduction techniques for both linear regression and low-rank approximation. We consider the "sketch-and-solve" paradigm, so that for both problems, we first acquire a low-dimension representation of the problem, and find the optimal solution in the low dimension using the above closed-form solutions. For "good" designs of the low-dimension representations, the low-dimension solution will also be near-optimal for the original problem.
We first observe that oblivious linear sketches serve as a common dimensionality reduction for both linear regression and low-rank approximation. For example, it is known [Woo 14] that there exists family of Gaussian random matrices 91 from which S ~ 91 satisfies with high probability,
- [)]A - Sb|l2 & ||Ax bll2 z (1 + +) S SSbl2,
simultaneously for all x E IRd. Similarly, there exists [Woo14] family of Gaussian random matrices G2 from which S 91 satisfies with high probability, that the row space of SA contains (1+ =))-apprxxiimaiinn of the optimal low-rank approximation to A.
Alternatively, can achieve dimensionality reduction for both linear regression and low-rank approximation by sampling a small subset of the input related ways for both problems. For linear regression, can generate random matrix by sampling rows of [A bj by their leverage scores [DMM06a, DMM06b, Mag10, Woo14]. this manner, we again achieve a matrix such that with high probability,
SAx Sbll2 < ||A blI2 S (1++) SSb/xx
simultaneously for all Rdd For low-rank approximation, sampling rows of with the related ridge-leverage scores [CMM17]. Then with high probability, we have for all V ig
generate random matrix S by
(1 =) SA SAVIVI = ||A AVVV < (1++)
SAV
B
Missing Proofs from Section 3
B.1
Lower Bound
We first show in Section B.1 that it is NP-hard approximate fair low-rank approximation within any constant factor in polynomial time and moreover, under the exponential time hypothesis, it requires exponential time to achieve a constant factor approximation. We then give missing details from Section 3.1 and in Section 3.2.
Given points (11) ...., (x)) E Rdd their outer (d -r)-rdd defined the minimum, over all k-dimensional linear subspaces, of the maximum Euclidean distance of these points to the subspace. We define this problem Subspace(k, oo). is known that it is NP-hard approximate the Subspace(n (n - 1, oc) problem within any constant factor:
Theorem B.1 ([BGK00, DTV11J). The Subspace(n - 1, oo) problem is NP-hard to approximate within any constant factor.
Utilizing the Na-hards of approximation of the Subspace(n 1, o0) problem, we show the hardnrss of approximation of fair low-rank approximation.
Theorem 1.1. Fair low-rank approximation NP-hard approximate within any constant factor.
Proof. Given an instance ,..,,
Rd of Subspace(n 1, oo) with n < d, we set L k 1 and A (6) = (() for all i E [r]] Then for k-dimensional linear subspace V E Rexd we have that |A ( VT VV- 2 is the distance from (+) to the subspace. Hence, max | [A (T
16

---

11 &. is the maximum Euclidean distance of these points to the subspace and so the fair low-rank approximation problem is exactly Subspace(n 1, 0.). By Theorem B.I, the Subspace(n oo) problem is NP-hard to approximate within any constant factor. Thus, fair low-rank approximation is NP-hard to approximate within any constant factor.
We next introduce standard complexity assumption beyond NP-hardness. Recall that in the 3-SAT problem, the input is a Boolean satisfiability problem written in conjunctive normal form, consisting of n clauses, each with literals, either variable or the negation of variable. The goal is to determine whether there exists Boolean assignment to the variables to satisfy the formula.
Hypothesis B.2 (Exponential time hypothesis [IPO1]. The 3-SAT problem requires 20(m) runtime.
Observe that while NP-hardness simply conjectures that the 3-SAT problem cannot be solved in polynomial time, the exponential time hypothesis conjectures that the 3-SAT problem requires exponential time.
We remark that in the context of Theorem B.1, [BGK00] showed the hardness of approximation of Subspace(1r nn - 1, oc) through a reduction from the Max-Not-All Not-All-Equal-3-SAT problem, whose NP- hardness itself is shown through reduction from 3-SAT. Thus under the exponential time hypothesis, Max-Noo-All--aqual--SAA problem requires 20(n)) solve. Then it follows that:
Theorem B.3 ((BGK00, DTV11I). Assuming the exponential time hypothesis, then the Subspace(n- 1, oo) problem requires 2n 20)) time to approximate within any constant factor.
follows that under the exponential time hypothesis, any constant- canstant-factor approximation to socially fair low-rank approximation requires exponential time.
Theorem 1.2. Under the exponential time hypothesis, the fair low-rank approximation requires 2 2t00) time approximate within any constant factor.
v(!)...,, v(k) E Rdd of Subspace(k: 1, oc) with k < d, set & = Proof. Given instance v(1), ,....,
k and (t) v(t) for all (k-ixxd, we have that ||A VVV
[b). Then for (k- dimieeensona linear subspace V 1 is the distance from v(() to the subspace. Hence, A | is the maximum Euclidean distance of these points to the subspace and so the fair low-rank approximation problem is exactly Subspace(k - 1, x)). By Theorem B.3, the Subspace(k: - 1, oc) problem requires 2k time to approximate within any constant factor. Thus, fair low-rank approximation requires 24000) time to approximate within any constant factor.
max4ete] || | V A
B.2 Missing Proofs from Section 3.1
We first recall the following result for polynomial system satisfiability solvers.
Theorem B.4 ([Ren92a, Ren92b, BPR96]). Given a polynomial system P(z In) over real numbers and m polynomial constraints fi(TI,.... Inn) 8 0, where @ E 1,,2,=,7,5 S, <) for all i E [m]. let d denote the maximum degree of all the polynomial constraints and let B denote the maximum size of the bit representation of the coefficients of all the polynomial constraints. Then there exists an algorithm that determines whether there exists solution the polynomial system P in time (md))(n) (oly(B).
To apply Theorem B.4, we utilize the following statement upper bounding the sizes of the bit representation of the coefficients of the polynomial constraints in our system.
2 0} be defined by m polynomials fe(x1,... Inn) for i E [m] with degrees bounded by an even integer and coefficients of magnitude at most M. Let C be compact connected component T. Let g(I be a polynomial of degree at most d with integer coefficients of magnitude at most M. Then the minimum nonzero magnitude that lakes over C is at least (22-n/2 M Md - max (M, 2n + 2m).
Theorem B.5 (UPT13]). Let T = {x E R" (1 2
where M =
To perform dimensionality reduction, recall the following definition of affine embedding.
17

---

Definition B.6 (Affine embedding). We say matrix S E R is an affine embedding for matrix A E _2 and a vector b E R we have
(1- - - blli I |AAS - bSll S (1 + - ---A-b -bll
for all vectors x E Rd
We then apply the following affine embedding construction.
Lemma B.7 (Lemma 11 in (CEM*15)) Given 6,5 E (0,1) and a rank parameter k > 0, let m = O
- log 3). For any matrix A RRdx,, there exists a family S of random matrices in Buxmm such that for ~ S. we have that with probability at least 1 5, S is one-sided affine embedding for a matrix A E Rdxn and a vector E IR..
We now show crucial structural property that allows us distinguish between the case where guess a for the optimal value OPT exceeds (1 + e)OPT or is smaller than (1 ePT by simply looking a polynomial system solver on an affine embedding.
Lemma 3.1. Let V E &R x be the optimal solution the fair low-rank approximation problem for inputs A A
where ()) E R Rru xd, and suppose OPT = max;e]1] | A 11
Let S be an affine embedding for V and let W (VS)1 E k For i E [e], let Z A SW E Bg and R()) E B be defined so that SWR! has orthonormal columns. If 2 (1+e).OPT, then each i E [f]. a 2 [I(A (WR))) (A (0 (W))())) -A 11. Ifa <
(1-s) OPT, then there exists E [6]. such that a < (
18
Proof. By the Pythagorean theorem, have that
(A ()(S))
argmin X
X
VS A S1
Thus, Z argminx**. |X VS
S for Z A A E R and W (VS)
Rmxk
Let ( R bxk be defined so that A (1) SWR. ( has orthonormal columns. Thus, we have
Z R
(Z())
Us A S| (I (1) - SIS
=|Z A (1) S
min X
X (1) VS A S
by the definition of (+).
Suppose a 2 (1 + 2) ОPT. Since S is an affine embedding for V, then we have that for all x xk
1 vs - A S < (1 [[++)]]100 XV - P
In particular, we have
min x - A S S (1 1
min V
- A 1 S (1+c)
Then from the above argument, we have
(Z AS A =
X VS SSS
X
(1 + OP S
Since ( = A E x then for a 2 (1+ OPT, we have that for each i [Q]
2 [I SWR (A (1) SWR (1) A (
A 2
On the other hand, suppose a < (1 s) OPT. Let E [ be fixed so that
OPT = min
X V - A 12
X(
18

---

Since S is an affine embedding for V, we have that for all ( E R
' - A A x
- x
XX
S
-
Therefore,
(1 é) min
X - A 1 <
min X - A S|
X
From the above, we have
S
min X(e)
X VS - S
Hence, putting these relations together,
(1 - =]1== (1 min X (0)
A 1
s min X(1)
( $|
S A S
as desired.
We can thus utilize the structural property of Lemma 3.1 by using the polynomial system solver in Algorithm affine embedding.
Corollary B.8. Ifa (1 +1) OPT, then Algorithm 1 outputs vector B such that
a | - 1 a
a < (1 s1 - OPT, then Algorithm outputs 1
Correctness of Algorithm 2 then follows from Corollary B.8 and binary search on We now analyze the runtime of Algorithm
Lemma B.9. The runtime of Allorittmm 2 is at most poly(n) (20)0(N), for Ei=r n4 and
N poly (e, 2).
Proof. Suppose the coefficients of A (1) are bounded in magnitude by 20oly(n), where n = Ei=1 n4. The number of variables in the polynomial system is at most
= 2mn + 022 = poly e (,t.,-1))
Fach of the (E) polynomial constraints has degree at most 20. Thus by Theorem B.5, the minimum nonzero magnitude that any polynomial constraint takes over C is at least " --N=" 2 " Hence, the maximum bit representation required B poly(n)
20(N), By Theorem B.4, the runtime of the polynomial system solver is at most (O (f) 20) poly(B) = poly(n) (26)O(N), We require most O (Hlog) log iterations of the polynomial system solver. Thus, the total runtime is at most poly(n) (2)))(M)
Putting things together, we have:
Theorem 1.3. Given an accuracy parameter E E (0, 1), there exists an algorithm which outputs
V E kxd such that with probability at least 3, maxserq ||A (V) - A S (1 E). minveRtxa max,e[d] ||A00 Vi Al.... The algorithm uses runtime poly(n) (20) for
E._ ii and N- =ooyy (E, k, 1).
19

---

B.3
Missing Proofs from Section 3.2
Lemma B.10. Ler E (0, and x E R and let p ( logg t). Then ||x|o S | I
(L+E)] x||oo.
Proof. Since clear that ||x||>> S ||x||p_ then it remains to prove ||x 1p S (1+ Note that we have | < ||x|| L. To achieve f//p - (1 + E), it suffices to have 1 log I log( 1 + E). Since p.
log(1+ +)) (E) for E (0, 1), then for p O ( log E), have 61/1 - (1 + +), and the desired claim follows.
Lemma 3.5. Let V be the output of Algorithm 3. Then with probability least 10 max4e(e) (V) (6) is at most g 2//e (ki[log log (log d)) max4ete | (0) (V)iV-
A A where is the trade-off parameter input.
Proof. We have
1/P
|
V
Σ ( iE(4
A (0
[
Let A A ....o ( and let
Ú == AHS.
For i [e]. let U()) be the matrix of U whose rows correspond with the rows of A in A, i.., let U be the i-th block of rows of U.
By the optimality of A (6) (V)t with respect the Frobenius norm, have
1/r
I/P
Σ A ( (V) AE(
A
Σ
A
iE(
By Dvoretzky's Theorem, Theorem 3.2, with distortion e = 0(1), we have that with probability at least 0.99,
1/p
1/p
Σ kE
J A
2 Σ
FE
where use || I|p to denote the entry-wise p-norm. Writing Ú = U U then have
1/P
Σ
GU GA GA O HHB
HI
JJGÚÜHH-GARD
By the choice of the Lewis weight sampling matrix T, we have that with probability 0.99,
HGÜVH-GAN s TTÜVH - TGAH
2 TGÜVH - TGAH (n.2)
2/TGAAS//GAAHS) (TGA)H TGAH (p.2);
where |M (p.2) denotes the L, norm of the vector consisting of the L2 norms of the columns of M. and the last equality follows due to our setting of Ü AHS and V (TGAHS) (TGA), the latter in Algorithm By optimality of (TGAHS) (TGA)) for the choice of X in the
minimization problem
min X
TGAHSX TGAH (p.2);
20

---

we have
TGAHS (TGA)H TGAH (p.2)
min XERtXd
TGGHHX TGAH (p.2)-
Since S E Re'xt and T is Lewis weight sampling matrix for GAHSX GAH, then T has t rows, where & = O (k(log log (log' d)) by Theorem 3.3. Thus, each column of TGAH has t
entries, so that
min X
|TGAHSX TGAH (2.2) S VL min |TGAHSX - TGAH p XERIXa
By the choice of the Lewis weight sampling matrix T, we have that with probability 0.99,
min XeRoxa
[TGASXX - TGAH|| 2 min ||GAHSX GAH
XEROXA
By Theorem 3.3, we have that with probability 0.99,
min XERexa
||AASSX
GAH $ (vVs)
min UER" VER
JV GAH
for = O log loglogght k). Let V = argmin VeRaxa m |A - A A Then since UV has rank with 2 k, we have
min VER
|UV GAH (GA(V")'V'-GGA
1/p
Σ
(V) GA
iE|d
By Dvoretzky's ' Theorem, Theorem 3.2, with distortion e = ((1), we have that with probability at least 0.99,
1/p
1/P
Σ IGA (V* - PE
2
| (i) (V*)lV* - A 1
(c(e)
For clog l with 1, have
1/P
Σ
JA 10 (V')
-
S 2// max [E(
A 6 (V)
Al
EEL
Putting together these inequalities successively, ultimately have
max AA (8) (V) - [1 S 2 2//c. O (Vst) max |A A (V) - (0
[E|e]
SEld
for p clog O (k log log k), and O (k:log log (log d)). Therefore, we have
max A (V) A | t <E(?)
E .F.22// 2/c O (k:log log k) (log d)) max J (0) (V)'V - A A
(E(!)
C Missing Proofs from Section
It is known that the of the leverage scores of the rows of matrix can be bounded by the rank of the matrix.
Theorem C.1 (Generalization of Foster's Theorem, [Fos53]). Given a matrix M Raxd the sum of its leverage scores is rank(M)
By sampling rows proportional to their leverage scores, we can obtain subspace embedding as follows:
21

---

Theorem C.2 (Leverage score sampling). [DMM06a, DMM06b, Mag10, Wool4] Given a matrix M E Raxd let o, be the leverage score of the i-th row of M. Suppose p; == min (1, 0, log n) for each i E [n] and let S be a random diagonal matrix that the i-th diagonal entry of S is vP: probability Pt and with probability 1 Pt- Then for all vectors RR"
with
E | |v]2
and with probability least 0.99, for all vectors Rd
99
101
Mx l2 S |SMx S
|Mx
100
100
Moreover, S has most O (d log nonzero entries with high probability.
Lemma 4.2. Given matrix M E Rgad let S be a matrix such that for all T&d and IR"
11
13 M E [[[vv]]
M & |SMx S
1/v12
12
12
For fixed Raxm where B b .... bm with D, E R for i [m]. ler ler (Sb)) Let = X1 o.... o Xm. Then with probability at least 0.97, |MX B 99 minx ||XX B
Proof. Let X = argminx |MX BlI2 and OPT = MX -Bl By triangle inequality,
|SMX SB
|SM(X - X2)12 |SMX -SB 12-
We have
99
101
|X 2 S |SMX|
|MX |2
100
100
for E max Thus,
99
SMX SBIl2
M(X X')
|SMX* TMMX*-BBI -SBI12.
100
By triangle inequality,
SMX SBI|2 2 100 (| - Bl|2 - | Bll2) - S|SMX -SB|22
Since [[[v]]]] = |v] for all x E RRd, then by concavity and Markov's inequality, we have that
1
Pr |||| SBI|2 M Bl121 <
49
Thus with probability at least 0.97,
99
SMX
SBI|2 2
(| B/I2 - |XX - BBI2) MX - -BI|2-
100
Now since we have |SMXX then
-SB|22
| < 49
MX B/l2 and ||SM - SSB S |SMX - -SB|22
4
B 2
99
(IMX BlI2 ||MX - Bl12) - 49 - -B
100
so that
|MX BlIa s MX Bl12,
as desired.
Lemma 4.3. Let S,M M be the output of Algorithm 4. Then with probability at least 0.8, maxie (MM)) A [61 at most c 2/
O (k[log log (log d)) minver maxigg AA A A
22

---

Proof. Let V E Rexd be the output of Algorithm 3, where t = O (kelog log (log² d)). Then with
probability least 2. we have
max | (9) - E ...22"2 2/c
(logd)
min VeRlxd (E(d
max
A ( VVV - A (9)
sE]e]
Therefore, we have
max min B g - 1 sE[d]
A S e 2//c. O (k(log log k) (log d))
min max A (0 V - AA VERaxd KE[0
Let be sufficiently large parameter to be fixed. By Dvoretzky's theorem, i.e,, Theorem 3.2, with O (1), we have
max min B A p,.2 I (0(1) max min [ B aE|d (
A [F.
iE B
For sufficiently large = O (log f), we have by Lemma B.10,
min B A A < (1) min | GO 1p..- xE(4]
B
B
By change of variables, we have
min X
|XV
GA min |BV B
GA 1..
G,A over all i [n']. However, arbitrary choice of X, may not correspond selecting columns of A. Thus we apply leverage score sampling matrix S to sample columns of V which will correspondingly sample columns of GA. Then by Lemma 4.2, we have
Note that minimizing |XV GAI over all X corresponds to minimizing |X, V
min XVS GAS n. S (1) min |X GA
Putting these together, we have
min - p2 S e 2/e2 (k(log log (log d)) min max ||A ( (VvtV- I (I) VER=xa iE[
Let be the selected columns from Algorithm 4 by and note that A SS (V) V is in the column span of A { for each i [e]. By Dvoretzky's s theorem, i.e. Theorem 3.2, with E (1) and fixed parameter we have
| SSt (V) A =E(E]
G A A SSI (V) G A 1b.2
max EE
For sufficiently large p. we have
max | Astt (Vy-V- - G( A (0) 11 S (0()) | (V) GA
sE[{]
By the correctness of the leverage score sampling matrix, we have
||GASS (V) GA < O (1) (V) -
Observe that minimizing [XVS GAS p.22 over all X corresponds to minimizing |X, VS G,AS||2 over all i [n']. Moreover, the fosed-form solution of the L2 minization problem is
G argmin VS G,AS|12. X.
Therefore, we have
GASS (V)'VS GAS
p.2 min X
XVS - GAS
Putting things together, we have
max | sst (V) A ( min XVS
GAS p.
(2)
RE|
By Equation and Equation and rescaling of the constant hidden inside the big Oh notation, we have
max *E[]]
|A | sS) (V) VV
A < //2 (k<log log k) (log (l)
min max A V -
A [=
VeRtxd iE(!]
The desired claim then follows from the setting of M st tV for i [C] by Algorithm 4. 0
23

---

D Additional Empirical Evaluations
In this section, we present number of additional results from empirical evaluations on socially fair low-rank approximation.
We first remark on a number of additional empirical evaluations for socially fair low-rank approxi- mation. We first compare our bicriteria algorithm to the standard low-rank approximation baseline over simple synthetic example. We then describe simple fixed input matrix for socially fair low-rank approximation that serves as a proof-of-concept similarly demonstrating the improvement of fair low-rank approximation optimal solutions over the optimal solutions for standard low-rank approximation.
Synthetic dataset. Next, we show that for simple dataset with two groups. each with two observations across four features, the performance of the fair low-rank approximation algorithm can be much better than standard low-rank approximation algorithm on the socially fair low-rank objective, even without allowing for bicriteria rank. For our synthetic dataset, we generate simple
(1) =
2 0
0
and A (2)
0
0 1.99
An optimal fair low-rank solution for 1.99]
0
0
2
0
k = is
0
0
which gives cost 4. However, due to the weight of the items in A (1), the
standard low-rank algorithm will output low-rank factors with cost 2- 1.992 x 7.92, such as the factors
Thus the ratio between the objectives is roughly 1, i... the improvement roughly a factor of two. We show in Figure 2 that our bicriteria algorithm achieves similar improvement.
0 1 0
Experimental setup. Again, we compare our bicriteria algorithm from Algorithm against the standard non-fair low-rank approximation algorithm that outputs the top l right singular vectors from the singular value decomposition. Per Dvoretzky's 's Theorem, c.f., Theorem 3.2, we generate normalized Gaussian matrices G and H of varying size and then use Lp Lewis weight sampling to generate a matrix T with varying values of We generate matrices T, G. and H with a small number of dimensions and thus do not compute the sampling matrix S but instead use the full matrix. We first fix 1 and iterate over the number of rows/columns in the Gaussian sketch in the range 21, 19, 20) in Figure 2a. We then fix the Gaussian sketch have three rows/columns and iterate over E {1, 9, 10} in Figure 2b. For each of the variables, we compare the outputs of the two algorithms across 100 iterations and plot the ratio of their fair costs. In particular. we set the same rank parameter of k = 2 for both algorithms; we remark that the theoretical guarantees for our bicriteria algorithm are even stronger when we permit the solution to have rank ke for ke > kt
082
0.85
0.0
088
0.9
nér milu avg rato
Raaloo of
ni: méo 2vg reo
0.82
075
673
075
075
10
Mumber rows Cosssian
of Lewis sample
(a) Ratio costs over different number of (b) Ratio of costs over different values of p in the Lewis rows/columns in the Gaussian sketch matrix.
sampling process.
Fig. 2: Ratio of the cost of our bicriteria algorithm to the cost of the standard low-rank approximation solution for k = 2, across 100 iterations.
24

---

Results and discussion. Our empirical evaluations in Figure 2 show that our algorithms can perform significantly better for socially fair low-rank approximation. We note that in both across all values of the number of rows/columns in the Gaussian sketch in Figure 2a and across all values p p the Lewis weight sampling parameter in Figure 2b, the average ratio between our bicriteria solution and the standard low-rank approximation is less than 0.9. We remark that any ratio less than 1 demonstrates the superiority of our algorithm, with smaller ratios indicating better performance. In fact, the minimum ratio is as low as 0.76.
Proof-of-coneept. Finally, we give a toy example using synthetic dataset showing the impor- tance of considering fairnsss in low-rank approximation. Namely, show that even for simple dataset with four groups, each with a single observation across two features, the performance of the fair low-rank approximation algorithm can be much better than standard low-rank approximation algorithm on the socially fair low-rank objective. In this setup, we repeatedly generate matrices A ( A (2), ( (4) E {0, 132. with (2) = (1,0) and A (2)
(3) A (4) (0, 1). The but due the extra instances of (0, 1). the standard 2
optimal fair low-rank solution
22
low-rank algorithm will output the factor (0, 1). Thus the optimal fair solution achieves value on the socially fair low-rank approximation objective while the standard low-rank approximation solution achieves value 2. so that the ratio a 50% improvement.
Potential Broader Impact
This paper presents research aimed reducing biases in key data summarization tasks. Our work is driven by the societal implications machine learning techniques, representing series of results towards developing equitable methods in this field.
25

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Indeed, our abstract and introduction clearly state the claims made, including the contributions made in the paper, as well as important assumptions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
(2) Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, our theorem statements formally describe the limitations of our theoretical results.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiiatinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
(3) Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
26

---

Answer:
[Yes]
Justification:
Yes, the paper provides the complete proofs in the full version.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
(4) Experimental Result Reproducibility
Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, the paper fully discloses the information needed to reproduce the main experimental results of the paper, including the accessed datasets, as well as the code the full version.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
(5) Open access to data and code
27

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Yes, open access to the data and code are provided in the full version.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//niss httppsccccpbccccccceececcccccccc /tt.gde////ooeeammaiieee /Cooeeeooiissseeeeeee wwsssonollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
(6) Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Yes, all the testing parameters are described in the paper, and also provided in the code in the full version.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, the paper provides the central statistics of our experiments when relevant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
28

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
(8) Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, the computing resources are described in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
(9) Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https //te:r/is....eeeeee cwteriissccppuuuu htlpppi//ttiisasaiiiiteeee ines?
Answer: [Yes]
Justification: Yes, the research conducted in the paper conforms every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
(10) Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, we address the potential broader impacts in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
29

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
(11) Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our dataset acquired from publicly available repository and thus do not introduce new data this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
(12) Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All original assets used in this paper have been referenced appropriately.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
30

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
(13) New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Yes, the provided is well-documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
(14) Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
(15) Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
31

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "ocFgM9z2OR", "reviewer": "Reviewer_icAD", "summary": "The paper studies the socially-fair variants of low-rank approximation and column subset selection. The authors prove hardness results similar to those in the literature for the non-fair versions of the problems. They then propose exponential time close-to-optimal solution for socially-fair low rank approximation and polynomial time bi-criteria approximation algorithms for both the problems.", "questions": "Are there any open problems related to socially-fair low rank approximation and subset selection not addressed in the paper? If yes, I request the authors to mention some.", "limitations": "Limitations adequately addressed by the authors.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies two important and relevant problems. \n2. The socially-fair variants are established notions of fairness in clustering, dimension reduction etc., and applies very well to both low rank approximation and column subset selection, neither of which are solved in the literature.\n3. The theoretical analysis is well done.\n4. The experimental results show that the algorithms are practical enough to use in the real-world applications.", "weaknesses": "The paper is not easy to read. The introduction may be shortened.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper is not easy to read. The introduction may be shortened.\n\nThe nature of our result is theoretical and, in principle, builds on technical results in the area of randomized numerical linear algebra. However, we will provide more background and preliminaries in the next version of our paper.\n\n> Are there any open problems related to socially-fair low rank approximation and subset selection not addressed in the paper? If yes, I request the authors to mention some.\n\nThank you for your suggestions. We will add related open problems in the next version of our paper, including both technical questions and more general fairness-aware optimization of data summarization methods. For example, a natural future direction is the efficient construction of $(1+\\epsilon)$-coresets with minimal size for socially fair subset selection.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KdZQ5ifIEH", "reviewer": "Reviewer_YsQa", "summary": "The authors investigate socially-fair low-rank approximation and column subset selection problems. The concept of socially-fair (in the context of clustering problems this fairness notion is well studied) is introduced when the input matrix rows can be partitioned resulting in sub-matrices, the goal is to find a low-rank matrix of rank $k$ that minimizes the maximum reconstruction error or loss. In the socially-fair column subset selection problem, the task is to select $k$ columns from the input matrix that minimize the maximum reconstruction error. The quality of the solution (error) is measured by the residual norm when the input matrix is projected onto the subspace spanned by the selected columns.\n\nFirst they show that fair low-rank approximation is NP-hard to approximate to any constant factor, further they strengthen their inapproximability claim by showing that it is not possible to find an algorithm with running time $2^{\\Omega(k)}$ that gives a constant factor approximation. Note that these results only apply for low-rank approximation and not column-subset selection (correct me if I am wrong)---these proofs/construction was easier to follow and I have verified in sufficient detail, they appear to be correct. They proceed to present approximation algorithms, asserting that these algorithms run in time $2^{\\text{poly}(k)}$. I have not been able to verify these proofs myself.", "questions": "Line 58: $U = U_1 \\circ \\dots \\circ U_k$, what operations does $\\circ$ symbol denote?\n\nLine 82: Why does the naive algorithm require $ n^{\\text{poly}(k)} $ and not $ n^k \\text{poly}(n, k) $? Can you clarify this precisely? Which specific naive algorithm are you referring to here?\n\nLine 88-92: I'm having trouble understanding this. Could you explain what this value of $ \\alpha $ is and how it relates to Theorem 1.3 in simpler terms? Once this is clear, the subsequent statements will be easier to follow. The theorem statement does not mention the term $ \\alpha $; how does it connect to $ \\alpha $? What do you mean when you say $ \\alpha $ is feasible?\n\nLine 131: Could you please provide a precise definition of the fair column subset selection problem, or indicate where it is defined in the paper, before discussing algorithmic results for the problem?\n\nLine 183: Is the problem studied by Matakos et al. 2023 the same or \"similar\" to the problem addressed in this paper? What are the specific differences between them? Specifically, does this paper generalize the problem defined on two groups by Matakos et al. to more than two groups, or is it a different notion of fairness altogether?\n\nLine 206 - 228: It is redundant to repeat the exact same text as outlined in our contributions and technical overview. I am not sure if this is the most efficient way to utilize the space by reiterating these statements multiple times, there is nothing new, the explanation is again in high-level without any details.\n\nLine 286: What is the relationship between matrix $ B^{(i)} $ and $ A^{(i)} $? Where is $ B^{(i)} $ defined in the paper? Without clarifying this, I cannot proceed to verify the subsequent details. Are you selecting $ C $ as a column matrix of $ A $ or $ A^{(i)} $? I am concerned that the dimensions of matrices may not match with the current problem formulation.", "limitations": "No discussion on potential negative social impact.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper presents approximation algorithms for the socially-fair low-rank approximation and column subset selection problem, which are both important from the context of dimensionality reduction and algorithmic fairness perspective.", "weaknesses": "The paper seems to be written for a specialized audience deeply embedded in the field, rather than for a general audience. The authors frequently cite lemmas and theorems from previous papers without providing sufficient explanations or context, assuming readers already have extensive background knowledge. This approach can alienate those who are not experts in the niche area of matrix approximations. The writing style is convoluted, making it challenging to follow the arguments and understand the implicit assumptions. The authors should consider that not everyone working on these topics is an expert with a long history in the field, and make an effort to present the material more clearly and accessibly.\n\nI was not able to understand the paper in sufficient detail to provide the best possible review. I cannot confirm that the proofs are correct, as I could not verify them without clarifying several unclear aspects of the paper. However, if the authors can address my questions in sufficient detail, I am willing to review the paper again and update my assessment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper seems to be written for a specialized audience deeply embedded in the field, rather than for a general audience. The authors frequently cite lemmas and theorems from previous papers without providing sufficient explanations or context, assuming readers already have extensive background knowledge. This approach can alienate those who are not experts in the niche area of matrix approximations. The writing style is convoluted, making it challenging to follow the arguments and understand the implicit assumptions. The authors should consider that not everyone working on these topics is an expert with a long history in the field, and make an effort to present the material more clearly and accessibly.\n\nWe emphasize that to provide context, the previous version already includes simple intuitive explanations prior to each lemma and theorem statement, even those from previous papers. Moreover, the nature of our result is theoretical and, in principle, builds on technical results in the area of randomized numerical linear algebra. However, we will provide more background and preliminaries in the next version of our paper.\n\n> Line 58: $U=U_1\\circ\\cdots\\circ U_k$, what operations does $\\circ$ symbol denote?\n\n$\\circ$ denotes vertical concatenation of the rows, c.f., line 542 in the preliminaries. \n\n> Line 82: Why does the naive algorithm require $n^{\\mathrm{poly}(k)}$ and not $n^k\\mathrm{poly}(n,k)$? Can you clarify this precisely? Which specific naive algorithm are you referring to here?\n\nThe algorithm we were referring to is a brute force search over a net on all subsets of $k$ factors, which for constant dimension would require $n^{\\mathrm{poly}(k)}$ time (and even worse for super-constant dimension). Moreover, it should be noted that a runtime of $n^k\\mathrm{poly}(n,k)$ would still fall under $n^{\\mathrm{poly}(k)}$ runtime, i.e., the polynomial would be linear. \n\n> Line 88-92: I'm having trouble understanding this. Could you explain what this value of $\\alpha$ is and how it relates to Theorem 1.3 in simpler terms? Once this is clear, the subsequent statements will be easier to follow. The theorem statement does not mention the term $\\alpha$; how does it connect to $\\alpha$? What do you mean when you say $\\alpha$ is feasible?\n\n$\\alpha$ is simply a guess for a $(1+\\epsilon)$-approximation to the optimal solution. The theorem does not need to mention the term $\\alpha$ because the algorithm makes a small number of guesses, one of which must be feasible, i.e., a $(1+\\epsilon)$-approximation to the optimal solution for which there exists $k$ factors that realize the fair low-rank approximation cost. \n\n> Line 183: Is the problem studied by Matakos et al. 2023 the same or ``similar'' to the problem addressed in this paper? ... What are the specific differences between them? Specifically, does this paper generalize the problem defined on two groups by Matakos et al. to more than two groups, or is it a different notion of fairness altogether?\n\nMatakos et al. (2023) study fair column subset selection, which is a specific type of low-rank approximation. Thus, their focus is more narrow than ours. They present an algorithm that can only achieve fairness for two groups, which may be inapplicable for many applications. Therefore, it is accurate to say that our setting for the specific problem of socially fair column subset selection generalizes the problem they study, although the techniques in the corresponding algorithms are quite different. To emphasize, we both study the same notion of fairness.\n\n> Line 206 - 228: It is redundant to repeat the exact same text as outlined in our contributions and technical overview...I am not sure if this is the most efficient way to utilize the space by reiterating these statements multiple times, there is nothing new, the explanation is again in high-level without any details.\n\nThis section expands on the algorithmic outline given in the technical overview to provide more intuition. While we understand that some details may appear repetitive, this is necessary to maintain coherence and clarity for the reader, especially when transitioning between different sections of the paper. That said, we will use the extra page in the introduction to address your comments. Additionally, we provide the full details in Algorithms 1 and 2 on Line 238.\n\n> Line 286: What is the relationship between matrix $B^{(i)}$ and $A^{(i)}$?...Where is $B^{(i)}$ defined in the paper? Without clarifying this, I cannot proceed to verify the subsequent details. Are you selecting $C$ as a column matrix of $A$ or $A^{(i)}$? I am concerned that the dimensions of matrices may not match with the current problem formulation.\n\nAh thanks, there is a slight typo --  the expression in Line 286 should be $\\|A^{(i)}CB^{(i)}-A^{(i)}\\|_F$ and hence the dimensions of the matrices match the current problem formulation. We are selecting $k$ columns of the overall matrix $A$, which also corresponds to the same $k$ columns for each group $A^{(i)}$. Note that $B^{(i)}$ is defined in this optimization problem as the minimizing factor. Given the selection of the $k$ columns induced by $C$, then $B^{(i)}$ is the matrix that minimizes the low-rank cost for $A^{(i)}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aObsCpxC8D", "reviewer": "Reviewer_CrGT", "summary": "The paper considers low-rank approximation and column selection in a specific setting to which authors refer as socially fair setting. Basically, given $\\ell$ matrices $A^{(1)},\\dots,A^{(\\ell)}$, they consider the problem of approximating solution of $\\\\min_{U \\\\in \\\\mathbb{R}^{k\\\\times d}} \\\\max_{i\\\\in [\\ell]} \\\\Vert A^{(i)}U^{\\\\dagger}U - A^{(i)}\\\\Vert_F$. They first show that this problem is in general NP-hard, and then propose two algorithms that achieve time complexity polynomial in $n=\\sum_{i=1}^{\\ell} n_i$ and either exponential in $k$ (rank) for $(1+\\epsilon)$ approximation, or polynomial in $k$ for an approximation with multiplicative constant polynomial in $k,\\ell,\\log d$. Lastly, proposed algorithm for low rank approximation is then used for column subset selection, where similar guarantees are obtained.", "questions": "1) According to Theorem 1.3 the runtime is given by $\\\\frac{1}{\\epsilon} \\mathrm{poly}(n) (2\\ell)^{O(N)}$ where $N=\\mathrm{poly}(\\ell,k,\\frac{1}{\\epsilon})$. You present this result for fixed number of groups $\\ell$ and as a function of $n$ and $k$. But in the case when all matrices are (approximately) low rank (say of rank $r$) then it does not make sense to have $k\\geq r\\ell$? So, in this case we are equally interested in dependence on $\\ell$, right?\n\n2)  Notation in line (286) is confusing - I am not sure if $B^{(i)}$ is defined at that point, and how $B^{(i)} C$ becomes $A^{(i)}SM^{(i)}$ in Lemma 4.3. In addition, it seems like $M^{(1)}=\\cdots=M^{(\\ell)} = M$, so why are there these superscripts?   \n\n3) In the setting when $\\ell = 1$, your column selection algorithm has the same (or higher) time complexity as SVD, but has multiplicative factor $\\widetilde{O}(k)$ in front of the approximation error. Thus, in this setting your algorithm is as complex as the optimal algorithm, but achieves worse performance. But, in any setting $\\ell > 1$, it is not clear how to combine subspaces obtained from SVD to achieve small fair low-rank approximation error. Is this correct?\n\n4) Could you please explain how you choose rank for bicriteria approximation in Section 5? Namely, at the end of Section 1.1 you say that bicriteria algorithm performs better \"even when the bicriteria algorithm is not allowed a larger rank than the baseline\". Later in Section 5 you choose bicriteria solution to have rank $2k$. I find this a bit confusing, especially since I thought $k$ was the rank...\n\n\nOther comments\n- missing definition of $k$ in the abstract\n- there is a typo in Lemma 3.5, on the right hand side of the last inequality it should be $\\\\min_V$ and not $\\tilde{V}$. \n- in Section 5 I did not find definition of the costs ratio you have plotted (I believe it is given in Appendix), so please add it there.", "limitations": "The authors have addressed limitations adequately.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) This paper has a few interesting and nontrivial contributions. The way these are presented is also very good - starting from computationally infeasible (in polynomial time) results, to less time demanding algorithms.  \n\n2) I believe the authors made a nice connection with fairness, and this clearly increases significance of the paper. Nonetheless, I believe this is a fundamental problem of multi-matrix approximation and I appreciate derived results even from pure theoretical perspective.\n\n3) It seems to be the first paper considering socially fair low-rank matrix approximation and related topics.\n\n4) Although the main results and their analysis are not simple, I believe the authors made great efforts to make it as accessible as possible.", "weaknesses": "1) There are a lot of things to understand in Introduction i.e. section 1.1. Although it gets easier once you are done with it, I would prefer keeping some of the details of section 1.1 until section 3. Furthermore, there is a significant overlap between the two sections, so merging them might give you more space for explanations in the main.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There are a lot of things to understand in Introduction i.e. section 1.1. Although it gets easier once you are done with it, I would prefer keeping some of the details of section 1.1 until section 3. Furthermore, there is a significant overlap between the two sections, so merging them might give you more space for explanations in the main.\n\nWe will apply your suggestion in the next version of our paper, thank you.\n\n> According to Theorem 1.3 the runtime is given by $\\frac{1}{\\epsilon}\\text{poly}(n)(2\\ell)^{O(N)}$ where $N=\\text{poly}\\left(\\ell,k,\\frac{1}{\\epsilon}\\right)$. You present this result for fixed number of groups $\\ell$ and as a function of $n$ and $k$. But...in the case when all matrices are (approximately) low rank (say of rank $r$) then it does not make sense to have $k\\ge r\\ell$?...So, in this case we are equally interested in dependence on $\\ell$, right?\n\nEven in this case, we believe that the focus can be on the input parameter $k$. In particular, in the case where all matrices have rank at most $r$, the input value of $k$ should not be set larger than $r\\ell$. Indeed, given a more reasonable input parameter of $k<r\\ell$ that does not trivialize the problem, the algorithmic runtime dependency on $k$ is still quite important. \n\n> Notation in line (286) is confusing - I am not sure if $B^{(i)}$ is defined at that point, and how $B^{(i)}C$ becomes $A^{(i)}SM^{(i)}$ in Lemma 4.3. In addition, it seems like $M^{(1)}=\\cdots=M^{(\\ell)}=M$, so why are there these superscripts? \n\nThanks for the question, there is a slight typo -- the expression in Line 286 should be $||A^{(i)}CB^{(i)}-A^{(i)}||_F$. We are selecting $k$ columns of the overall matrix $A$, which also corresponds to the same $k$ columns for each group $A^{(i)}$. Note that $B^{(i)}$ is defined in this optimization problem as the minimizing factor. Given the selection of the $k$ columns induced by $C$, then $B^{(i)}$ is the matrix that minimizes the low-rank cost for $A^{(i)}$. We then use a change of notation, the column selection matrix $C$ becomes the column sampling matrix $S$ and $B^{(i)}$ becomes $M^{(i)}$, so that the matrices $M^{(1)},\\ldots,M^{(\\ell)}$ differ across the groups. We will fix the typo and unify the notation in the next version of the paper. \n\n> In the setting when $\\ell=1$, your column selection algorithm has the same (or higher) time complexity as SVD, but has multiplicative factor $\\tilde{O}(k)$ in front of the approximation error...Thus, in this setting your algorithm is as complex as the optimal algorithm, but achieves worse performance. But, in any setting $\\ell>1$, it is not clear how to combine subspaces obtained from SVD to achieve small fair low-rank approximation error. Is this correct?\n\nNote that even for $\\ell=1$, SVD does not translate to column subset selection since the top $k$ singular values generally do not correspond to elementary vectors (i.e., columns of the matrix), though SVD does give the optimal solution for low-rank approximation. More generally, it is not even clear how to combine subspaces acquired from SVD for the socially fair low-rank approximation with $\\ell>1$. \n\n> Could you please explain how you choose rank for bicriteria approximation in Section 5?...Namely, at the end of Section 1.1 you say that bicriteria algorithm performs better ``even when the bicriteria algorithm is not allowed a larger rank than the baseline''. Later in Section 5 you choose bicriteria solution to have rank $2k$. I find this a bit confusing, especially since I thought $k$ was the rank...\n\nWe perform multiple experiments in Section 5. In Figure 1a, the bicriteria algorithm is not allowed a larger rank than the baseline. In Figure 1b, the bicriteria algorithm is permitted rank $2k$, where $k$ is the rank of the baseline.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UTmMyztjft", "reviewer": "Reviewer_aAWQ", "summary": "This paper considers the fair low-rank approximation and fair column subset selection problem. These two problems are similar; they aim to select a subset of vectors that optimize the algorithm's performance across all sub-populations. Formally, given $\\ell$ matrices A and $\\ell$ matrices B, the goal is to choose k vectors that span these $\\ell$ B matrices such that the maximum distance between A and B is minimized. The distance is defined as some norm function between these $2\\ell$ matrices. Such a problem has applications in feature selection, which is one of the most important topics in machine learning.\n\nThe main contributions of this work are (1) a $(1+\\epsilon)$-approximation algorithm running in O(2^n); (2) using the similar key idea, one can obtain an $\\tilde{O}(k)$-approximation running in polynomial time for column selection. The authors also show a lower bound that achieving constant approximation requires exponential running time under the ETH conjecture. Besides these theoretical results, the authors also provide a set of experimental results.", "questions": "Is it possible to make the proposed algorithms run in parallel?", "limitations": "This is a theoretical paper, there are no potential negative societal impacts.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is well-motivated and it has wide application in machine learning. I believe that it should be interesting in the ML community.\n\n2. This is a technical solid paper. I like the high-level idea of the algorithm. Namely, it starts from some \"bad\" solution, and then repeatedly decreases the approximation until the ratio becomes $(1+\\epsilon)$. Checking feasibility requires some new ideas.\n\n3. The paper is well-written. I appreciate that the authors provide sufficient intuition and high-level descriptions for algorithms in Section 1.1. They are very helpful.", "weaknesses": "The main weakness is that the $(1+\\epsilon)$-approximation runs in exponential time, while for the column selection algorithm, its running time is polynomial but the approximation ratio is linear in k. I understand that there is a lower bound under ETH conjecture, but this running time strictly restricts the applications to the algorithm. Maybe it is more suitable to study the parallel algorithms for these problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The main weakness is that the $(1+\\epsilon)$-approximation runs in exponential time while for the column selection algorithm, its running time is polynomial but the approximation ratio is linear in $k$. I understand that there is a lower bound under ETH conjecture, but this running time strictly restricts the applications to the algorithm. Maybe it is more suitable to study the parallel algorithms for these problems... Is it possible to make the proposed algorithms run in parallel?\n\nThanks for the suggestion. It could be possible to make the proposed algorithms run in parallel, but due to our hardness results, the total runtime for a $(1+\\epsilon)$-approximation algorithm must still be exponential, across all servers. That said, this is a very interesting future direction.\n\nAdditionally, in most practical instances, $k$ is usually a small constant. Therefore, for these instances our algorithm provides a polynomial time constant factor approximations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thoughtful comments and valuable feedback. We also appreciate the positive remarks, such as:
- The paper studies two important and relevant problems. (Reviewer icAD)
- The theoretical analysis is well done. (Reviewer icAD)
- The experimental results show that the algorithms are practical enough to use in the real-world applications. (Reviewer icAD)
- The paper presents approximation algorithms for the socially-fair low-rank approximation and column subset selection problem, which are both important from the context of dimensionality reduction and algorithmic fairness perspective. (Reviewer YsQa)
- This paper has a few interesting and nontrivial contributions. The way these are presented is also very good - starting from computationally infeasible (in polynomial time) results, to less time demanding algorithms. (Reviewer CrGT)
- I believe the authors made a nice connection with fairness, and this clearly increases significance of the paper. Nonetheless, I believe this is a fundamental problem of multi-matrix approximation and I appreciate derived results even from pure theoretical perspective. (Reviewer CrGT)
- It seems to be the first paper considering socially fair low-rank matrix approximation and related topics. (Reviewer CrGT)
- Although the main results and their analysis are not simple, I believe the authors made great efforts to make it as accessible as possible. (Reviewer CrGT)
- The studied problem is well-motivated and it has wide application in machine learning. I believe that it should be interesting in the ML community. (Reviewer aAWQ)
- This is a technical solid paper. I like the high-level idea of the algorithm. Namely, it starts from some "bad" solution, and then repeatedly decreases the approximation until the ratio becomes $(1+\epsilon)$. Checking feasibility requires some new ideas. (Reviewer aAWQ)
- The paper is well-written. I appreciate that the authors provide sufficient intuition and high-level descriptions for algorithms in Section 1.1. They are very helpful. (Reviewer aAWQ)

We provide our responses to the initial comments of each reviewer separately below. We hope our answers addresses all points raised by the reviewers and we will be most happy to answer any remaining or additional questions during the discussion phase!

Meta-review: The reviewers agree that this paper studies important problems that lie in the intersection of algorithmic fairness and low-rank approximation. They acknowledged that the paper is technically solid and novel, and also considered the exposition of the techniques to be reasonably good. Experimental results serve as a good addition to the theory. Although one reviewer still has concerns on writing consistencies in the discussion stage, overall the pros significantly outweigh the cons.
Decision: Accept (poster)