On Socially Fair Low-Rank Approximation and Column Subset Selection

Authors: zhao  song
ali  vakilian
david p woodruff
samson  zhou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:54:47

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.

Main paper: 
 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, or large language models, to more critical processes such as autonomous vehicles, healthcare diagnostics, credit scoring, and sentencing recommendations in courts of law [Cho17, KLL + 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 a data matrix A ∈ R n×d and an integral rank parameter k > 0, and the goal is to find the best rank k approximation to A, i.e., to find a set of k vectors in R d that span a matrix B, which minimizes L(A -B) across all rank-k matrices B, for some loss function L. The rank parameter k 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 k columns U of A so as to minimize L(A -UV) across all choices of V ∈ R k×d . Although low-rank approximation can reveal important latent structure among the dataset, the resulting linear combinations may not be as interpretable as simply selecting k features. The column subset selection problem is therefore a 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-making 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 be 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 to achieve better global accuracy. As a result, an 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 fairness have been proposed [HPS16, Cho17, KMR17, BHJ + 21]. 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) ∈ R n1×d , . . . , A (ℓ) ∈ R n ℓ ×d corresponding to ℓ groups and a rank parameter k, and the goal is to determine a set of k factors U 1 , . . . , U k ∈ R d that span matrices B (1) , . . . , B (ℓ) , which minimize max i∈[ℓ] ∥A (i) -B (i) ∥ F . Due to the Eckart-Young-Mirsky theorem stating that the Frobenius loss is minimized when each A (i) is projected onto the span of U = U 1 • . . . • U k , the problem is equivalent to min U∈R k×d max i∈[ℓ] ∥A (i) U † U -A (i) ∥ F , where † denotes the Moore-Penrose 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 to the total Frobenius norm of each group and the optimal rank-k reconstruction loss for each group.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 ̸ = 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 n points in d-dimensional Euclidean space to all sets of k dimensional linear subspaces, which was shown by [BGK00, DTV11] to be NP-hard to approximate within any constant factor. In fact, [BGK00, DTV11] showed that a constant-factor approximation to this problem requires runtime exponential in k under a stronger assumption, the exponential time hypothesis [IP01] . 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 k Ω(1) time to approximate within any constant factor.Together, Theorem 1.1 and Theorem 1.2 show that under standard complexity assumptions, we 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 2 poly(k) runtime (Theorem 1.3). On the positive side, we first show that for a constant number of groups and constant-factor accuracy, it suffices to use runtime 2 poly(k) rather F 1/p . However, the terms∥A (i) V † V -A (i) ∥ pF are difficult to handle, so we apply Dvoretzky's Theorem, i.e., Theorem 3.2, to generate matrices G and H so that (1 -ε)∥GMH∥ p ≤ ∥M∥ F ≤ (1 + ε)∥GMH∥ p , for all matrices M ∈ R n×d , so that it suffices to approximately solve min X∈R k×d ∥GAHSX -GAH∥ p , forA = A (1) • . . . • A (ℓ) .Although low-rank approximation with L p loss cannot be well-approximated in polynomial time, we recall that there exists a matrix S that samples a "small" number of columns of A to provide a coarse bicriteria approximation to L p low-rank approximation [WY23] . However, we require a solution with dimension d and thus we seek to solve the regression problem min X ∥GAHSX -GAH∥ p . Thus, we consider a Lewis weight sampling matrix T such that1 2 ∥TGAHSX -TGAH∥ p ≤ ∥GAHSX -GAH∥ p ≤ 2∥TGAHSX -TGAH∥ p .and again note that (TGAHS) † TGAH is the closed-form solution to the minimization problem min x ∥TGAHSX -TGAH∥ F , which only provides a small distortion to the L p regression problem, since TGAH has a small number of rows due to the dimensionality reduction. We then observe that by Dvoretzky's Theorem, (TGAHS) † TGA 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 to arbitrary 1 -δ by taking the minimum of O log 1 δ 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 (i) ∈ R ni×d with n = n i , there exists an algorithm that selects a set S of k ′ = O (k log k) columns such that with probability at least 2 3 , S is a O (k(log log k)(log d))-approximation 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, H to embed the awkward maximum of Frobenius losses min max i∈[ℓ] ∥ • ∥ F into the more manageable L p loss min ∥ • ∥ p through GAH. However, selecting columns of GAH does not correspond to selecting columns of the input matrices A (1) , . . . , A (ℓ) . 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 i∈[ℓ] min B (i) ∥B (i) V -A (i) ∥ F . We then argue through Dvoretzky's theorem that a leverage score sampling matrix S that samples O (k log k) columns of V will provide a 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 a common humancentric 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. 
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 fairness metric of average reconstruction loss, expressed by the loss function loss(A, B) := ∥A -B∥ 2 F -∥A -A k ∥ 2 F , aiming to identify a k-dimensional subspace that minimizes the loss across the groups, with A k representing the best rank-k approximation of A. Their proposed approach, in a two-group scenario, identifies a fair PCA of up to k + 1 dimensions that is not worse than the optimal fair PCA with k dimensions. When extended to ℓ groups, this method requires an additional k + ℓ -1 dimensions. Subsequently, [TSS + 19] explored fair PCA from a distinct objective perspective, seeking a projection matrix P optimizing min i∈[ℓ] ∥A (i) P∥ 2 F . A pivotal difference between these works and ours is our focus on the reconstruction error objective, a widely accepted objective for regression and low-rank approximation tasks. Alternatively, [OA19, LKO + 22, KDRZ23] explored a 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.Recently, [MOT24] studied a fair column subset selection objective similar to ours, focusing on the setting with two groups (i.e., ℓ = 2). They established the problem's NP-hardness and introduced a polynomial-time solution that offers relative-error guarantees while selecting a column subset of size O (k).For fair regression, initial research focused on designing models that offer similar treatment to instances with comparable observed results by incorporating fairness regularizers [BHJ + 17]. However, in [ADW19] , the authors studied a 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 a focus on the sample complexity and the problem's generalization error bounds.[AAK + 22] studied a similar socially fair regression problem under the name min-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 a 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 [GSV21, ABV21] . In subsequent studies, tight approximation algorithms [MV21, CMV22], FPT approaches [GJ23] , and bicriteria approximation algorithms [GSV22] for socially fair clustering have been presented. 
socially fair low-rank approximation: 
 In this section, we consider algorithms and hardness for socially fair low-rank approximation. Let n 1 , . . . , n ℓ be positive integers and for each i ∈ [ℓ], let A (i) ∈ R ni×d . Then for a norm ∥ • ∥, we define the fair low-rank approximation problem to be min V∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥.We first give a (1 + ε)-approximation algorithm for fair low-rank approximation that uses runtime1 ε poly(n) • (2ℓ) O(N ) , for n = ℓ i=1 n i and N = poly ℓ, k, 1ε . The algorithm first finds a value α that is an ℓ-approximation to the optimal solution, i.e., minV∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥ F is at most α ≤ ℓ • min V∈R k×d max i∈[ℓ] ∥A (i) V † V - A (i) ∥ F .We then repeatedly decrease α by (1 + ε) while checking if the resulting quantity is still achievable. To efficiently check if α is achievable, we first apply dimensionality reduction to each of the matrices by right-multiplying by an affine embedding matrix S, so that(1 -ε)∥A (i) V † V -A (i) ∥ 2 F ≤∥A (i) V † VS -A (i) S∥ 2 F ≤ (1 + ε)∥A (i) V † V -A (i) ∥ 2 F ,for all rank k matrices V and all i ∈ [ℓ].Now if we knew V, then for each i ∈ [ℓ], we can find X (i) minimizing ∥X (i) VS -A (i) S∥ 2 F and the resulting quantity will approximate∥A (i) V † V -A (i) ∥ 2 F .In fact, we know that the minimizer is (A (i) S)(VS) † through the closed form solution to the regression problem. Let R (i) be defined so that (A (i) S)(VS) † R (i) has orthonormal columns, so that∥(A (i) S)(VS) † R (i) )((A (i) S)(VS) † R (i) ) † A (i) S -A (i) S∥ 2 F = min X (i) ∥X (i) VS -A (i) S∥ 2 F ,and so we require that if α is feasible, then α ≥ ∥(A (i) S)(VS) † R (i) )((A (i) S)(VS) † R (i) ) † A (i) S - A (i) S∥ 2 F .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 a polynomial system in conjunction with the guessing strategy. Thus we write Y = VS and its pseudoinverse W = (VS) † and check whether there exists a satisfying assignment to the above inequality, given the constraints (1) YWY = Y, (2) WYW = W, and (3) A (i) SWR (i) has orthonormal columns. Note that since V ∈ R k×d , then implementing the polynomial solver naïvely could require kd variables and thus use 2 Ω(dk) runtime. Instead, we note that we only work with VS, which has dimension k × m for m = O k 2 ε 2 log ℓ , so that the polynomial solver only uses 2 poly(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 (1 + ε)OPT or is smaller than (1 -ε)OPT by simply looking at a polynomial system solver on an affine embedding.Lemma 3.1. Let V ∈ R k×d be the optimal solution to the fair low-rank approximation problem for inputs A (1) , . . . , A (ℓ) , where A (i) ∈ R ni×d , and supposeOPT = max i∈[ℓ] ∥A (i) V † V -A (i) ∥ 2F . Let S be an affine embedding for V and letW = (VS) † ∈ R k×m . For i ∈ [ℓ], let Z (i) = A (i) SW ∈ R ni×k and R (i) ∈ R k×k be defined so that A (i) SWR (i) has orthonormal columns. If α ≥ (1+ε)•OPT, then for each i ∈ [ℓ], α ≥ ∥(A (i) SWR (i) )(A (i) SWR (i) ) † A (i) -A (i) ∥ 2 F . If α < (1-ε)•OPT, then there exists i ∈ [ℓ], such that α < ∥(A (i) SWR (i) )(A (i) SWR (i) ) † A (i) -A (i) ∥ 2 F .Algorithm 1 Input to polynomial solver Input: A (1) , . . . , A (ℓ) , S, α Output: Feasibility of polynomial system 1: Polynomial variables 2: Let Y = (VS) ∈ R k×m be mk variables 3: Let W = (VS) † ∈ R m×k be mk variables4: Let R (i) ∈ R k×k for each i ∈ [ℓ] be ℓk 2 variables 5: System constraints 6: YWY = Y, WYW = W 7: A (i) SWR (i) has orthonormal columns 8: α ≥ ∥(A (i) SWR (i) )(A (i) SWR (i) ) † A (i) - A (i) ∥ 2 F 9: Run polynomial system solver 10: If feasible, output V = (A (1) SWR (1) ) † A (1) . Otherwise, output ⊥.Algorithm 2 (1+ε)-approximation for fair lowrank approximation Input: A (i) ∈ R ni×d for all i ∈ [ℓ], rank parameter k > 0, accuracy parameter ε ∈ (0, 1) Output: (1 + ε)-approximation for fair LRA 1: Let α be an ℓ-approximation for the fair LRA problem 2: Let S be generated from a random affine embedding distribution 3: while Algorithm 1 on input A (1) , . . . , A (ℓ) , S, and α does not return ⊥ do 4:Let V be the output of Algorithm 1 on input A (1) , . . . , A (ℓ) , S, and α 5:α ← α 1+ε 6: end while 7: Return VTo achieve polynomial time for our bicriteria algorithm, we can no longer use a polynomial system solver. Instead, we observe that for sufficiently large p, we have max ∥x∥ ∞ = (1 ± ε)∥x∥ p . Thus, in place of optimizing minV∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥ F , we instead optimize min V∈R k×d i∈[ℓ] ∥A (i) V † V -A (i) ∥ p F 1/p. However, the terms ∥A (i) V † V -A (i) ∥ p F are unwieldy to work with. Thus we instead use Dvoretzky's Theorem, i.e., Theorem 3.2, to embed L 2 into L p , by generating matrices G and H so that (1 -ε)∥GMH∥ p ≤ ∥M∥ F ≤ (1 + ε)∥GMH∥ p , for all matrices M ∈ R n×d . Now, writing A = A (1) • . . . • A (ℓ) , it suffices to approximately solve min X∈R k×d ∥GAHSX -GAH∥ p . Unfortunately, low-rank approximation with L p loss still cannot be approximated to (1 + ε)-factor in polynomial time, and in fact GAH has dimension n ′ × d ′ with n ′ ≥ n and d ′ ≥ d. Hence, we first apply dimensionality reduction by appealing to a result of [WY23] showing that there exists a matrix S that samples a "small" number of columns of A to provide a coarse bicriteria approximation to L p low-rank approximation. Now to lift the solution back to dimension d, we would like to solve regression problem min X ∥GAHSX -GAH∥ p . To that end, we consider a Lewis weight sampling matrix T such that1 2 ∥TGAHSX -TGAH∥ p ≤ ∥GAHSX -GAH∥ p ≤ 2∥TGAHSX -TGAH∥ p .We then note that (TGAHS) † TGAH is the minimizer of the problem min x ∥TGAHSX -TGAH∥ F , which only provides a small distortion to the L p regression problem, since TGAH has a small number of rows due to the dimensionality reduction. By Dvoretzky's Theorem, we have that (TGAHS) † TGA is a "good" approximate solution to the original fair low-rank approximation problem. The algorithm appears in full in Algorithm 3.Input: A (i) ∈ R ni×d for all i ∈ [ℓ], rank parameter k > 0, trade-off parameter c ∈ (0, 1) Output: Bicriteria approximation for fair LRA 1: Generate Gaussian matrices G ∈ R n ′ ×n , H ∈ R d×d ′ through Theorem 3.2 2: Let S ∈ R n ′ ×t , Z ∈ R t×d ′be the output of Theorem 3.3 on input GAH 3: Let T ∈ R s×n ′ be a Lewis weight sampling matrix for GAHSX -GAH 4: Let V ← (TGAHS) † (TGA) 5: Return V We use the following notion of Dvoretzky's theorem to embed the problem into entrywise L p loss. Theorem 3.2 (Dvoretzky's Theorem, e.g., Theorem 1.2 in [PVZ17] , Fact 15 in [SW18] ). Let p ≥ 1 be a parameter and letm ≳ m(n, p, ε) =        p p n ε 2 , ε ≤ (Cp) p 2 n -p-2 2(p-1) (np) p/2 ε , ε ∈ (Cp) p 2 n -p-2 2(p-1) , 1 p n p/2 p p/2 ε p/2 log p/2 1 ε , 1 p < ε < 1.Then there exists a family G of random scaled Gaussian matrices with dimension R m×n such that for G ∼ G, with probability at least 1 -δ, simultaneously for ally ∈ R n , (1 -ε)∥y∥ 2 ≤ ∥Gy∥ p ≤ (1 + ε)∥y∥ 2 .We use the following algorithm from [WY23] to perform dimensionality reduction so that switching between L 2 and L p loss will incur smaller error. See also [CGK + 17].Theorem 3.3 (Theorem 1.5 in [WY23]). Let A ∈ R n×d and let k ≥ 1. Let s = O (k log log k).Then there exists a polynomial-time algorithm that outputs a matrixS ∈ R d×t that samples t = O k(log log k)(log 2 d) columns of A and a matrix Z ∈ R t×d such that ∥A -ASZ∥ p ≤ 2 p • O ( √ s) • min U∈R n×k ,V∈R k×d ∥A -UV∥ p .We recall the following construction to use Lewis weights to achieve an L p subspace embedding.Theorem 3.4 ([CP15]). Let ε ∈ (0, 1) and p ≥ 2. Let A ∈ R n×d and s = O d p/2 log d .Then there exists a polynomial-time algorithm that outputs a matrix S ∈ R s×n that samples and reweights s rows of A, such that with probability at least 0.99, simultaneously for allx ∈ R d , (1 -ε)∥Ax∥ p p ≤ ∥SAx∥ p p ≤ (1 + ε)∥Ax∥ p p .We then show that Algorithm 3 provides a bicriteria approximation.Lemma 3.5. Let V be the output of Algorithm 3. Then with probability at least 9 10 ,max i∈[ℓ] ∥A (i) ( V) † V-A (i) ∥ F is at most ℓ c •2 1/c •O (k(log log k)(log d)) max i∈[ℓ] ∥A (i) ( V) † V- A (i) ∥ F ,where c is the trade-off parameter input.Since the generation of Gaussian matrices and the Lewis weight sampling matrix both only require polynomial time, it follows that our algorithm uses polynomial time overall. Hence, we have Theorem 1.4. 
socially fair column subset selection: 
 In this section, we consider socially fair column subset selection, where the goal is to identify a matrixC ∈ R d×k that selects k columns to minimize min C∈R d×k ,∥C∥0≤k,B (i) max i∈[ℓ] ∥A (i) CB (i) - A (i) ∥ F .Input: A (i) ∈ R ni×d for all i ∈ [ℓ], rank parameter k > 0, trade-off parameter c ∈ (0, 1) Output: Bicriteria approximation for fair column subset selection 1: Acquire V from Algorithm 3 2: Generate Gaussian G ∈ R n ′ ×n through Theorem 3.2 3: Let S ∈ R d×k ′ be a leverage score sampling matrix that samples k ′ = O (k log k) columns of V 4: M (i) = S † ( V) † V for all i ∈ [ℓ] 5: Return A (i) S, {M (i) }We first provide preliminaries on leverage score sampling. Definition 4.1. Given a matrix M ∈ R n×d , we define the leverage scoreσ i of each row m i with i ∈ [n] by m i (M † M) -1 m ⊤ i .Equivalently, for the singular value decomposition M = UΣV, the leverage score of row m i is also the squared row norm of u i .We recall in Appendix C that it can be shown the sum of the leverage scores for an input matrix M ∈ R n×d is upper bounded by d 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 ω 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 L p 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 + 23], 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 ∈ R n×d , let S be a matrix such that for all x ∈ R d and v ∈ R n ,11 12 ∥Mx∥ 2 ≤ ∥SMx∥ 2 ≤ 13 12 ∥Mx∥ 2 , E ∥Sv∥ 2 2 = ∥v∥ 2 2 . For a fixed B ∈ R n×m where B = b 1 • . . . • b m with b i ∈ R n for i ∈ [m], let x i = (SM) † (Sb i ). Let X = x 1 • . . . • x m .Then with probability at least 0.97, ∥M X -B∥ 2 ≤ 99 min X ∥MX -B∥ 2 .We now give the correctness guarantees of Algorithm 4.Lemma 4.3. Let S, M (1) , . . . , M (ℓ) be the output of Algorithm 4.Then with probability at least 0.8, max i∈[ℓ] ∥A (i) SM (i) -A (i) ∥ F is at most ℓ c • 2 1/c • O (k(log log k)(log d)) min V∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥ F .We also have the following runtime guarantees on Algorithm 4. Lemma 4.4. The runtime of Algorithm 4 is poly(n, d).By combining Lemma 4.3 and Lemma 4.4, we have Theorem 1.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 humancentric data for experiments on fairness and was previously used as a benchmark by [STM + 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, as 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 a 64-bit operating system on an AMD Ryzen 7 5700U CPU, with 8GB RAM and 8 cores with base clock 1.80 GHz. We compare our bicriteria algorithm from Algorithm 3 against the standard non-fair low-rank approximation algorithm that outputs the top k 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 p 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 ∈ {2, 3, . . . , 21}, k = 1, and p = 1 over 10, 000 iterations for each setup in Figure 1a . Similarly, we plot both the minimum and average ratios for s = 1000, k ∈ {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 1c , separating runtimes for our bicriteria into the total runtime bicrit1 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 similar to SVD, which measures the runtime for extracting the factors. Across all experiments in Figure 1 , we used Gaussian matrices G with 30 rows and H with 30 columns. Results and discussion. Our empirical evaluations serve as a simple proof-of-concept demonstrating that our bicriteria algorithm can perform significantly better for socially fair low-rank approximation, even without allowing for more than k factors. In particular, all ratios in Figure 1a 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 1c 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 L 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 in Appendix D. In particular, we describe additional experiments on socially fair lowrank approximation on synthetic datasets and perform a quick investigation into socially fair linear regression, as additional motivation for studying fairness for randomized numerical linear algebra. 
conclusion: 
 In this paper, we 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 a 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 a simple proof-of-concept demonstrating the practical nature of our theoretical findings. It is our hope that our work is an important step toward better understanding of fairness in numerical linear algebra.Our work also leads to a 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 process [CKLV17, RS18  
 
 Appendix: We use the notation [n] to represent the set {1, . . . , n} for an integer n ≥ 1. We use the notation poly(n) to represent a fixed polynomial in n and we use the notation polylog(n) to represent poly(log n). We use poly(n) to denote a fixed polynomial in n and polylog(n) to denote poly(log n).We say an event holds with high probability if it holds with probability 1 -1 poly(n) . We generally use bold-font variables to represent vectors and matrices, whereas we use default-font variables to represent scalars. For a matrix A ∈ R n×d , we use A i to represent the i-th row of A and A (j) to represent the j-th column of A. We use A i,j to represent the entry in the i-th row and j-th column of A. For p ≥ 1, we use∥A∥ p =   i∈[n] j∈[d] A p i,j   1/pto represent the entrywise L p norm of A and we use∥A∥ F =   i∈[n] j∈[d] A 2 i,j   1/2to represent the Frobenius norm of A, which is simply the entrywise L 2 norm of A. We use define the L p,q of A as the L p norm of the vector consisting of the L q norms of each row of A, so that∥A∥ p,q =    i∈[n]   j∈[d] (A i,j ) q   p/q    1/p .Similarly, we use ∥A∥ (p,q) to denote the L p norm of the vector consisting of the L q norms of each column of A. Equivalently, we have ∥A∥ (p,q) = ∥A ⊤ ∥ p,q , so that∥A∥ (p,q) =    j∈[d]   i∈[n] (A i,j ) q   p/q    1/p .We use • to represent vertical stacking of matrices, so thatA (1) • . . . • A (m) =    A (1). . .A (m)    . For a matrix A ∈ R n×d of rank k, its singular decomposition is A = UΣV, where U ∈ R n×k , Σ ∈ R k×k , V ∈ R k×d ,so that the columns of U are orthonormal and the rows of V are orthonormal.The columns of U are called the left singular vectors of A and the rows of V are called the right singular vectors of A.In this section, we briefly describe some common techniques used to handle both regression and lowrank 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 is somewhat surprising that socially fair regression and socially fair low-rank approximation exhibit vastly different complexities.Closed form solutions. Given the regression problem min x∈R d ∥Ax -b∥ 2 for an input matrix A ∈ R n×d and a label vector b ∈ R n , the closed form solution for the minimizer isA † b = argmin x∈R d ∥Ax -b∥ 2, where A † is the Moore-Penrose pseudoinverse of A. Specifically, for a matrix A ∈ R n×d written in its singular value decomposition A = UΣv, we haveA † = V ⊤ Σ -1 U ⊤ .In particular, for if A has linearly independent rows, then A † = A ⊤ (AA ⊤ ) -1 . On the other hand, if A has linearly independent columns, thenA † = (A ⊤ A) -1 A ⊤ .Similarly, given an input matrix A and a rank parameter k > 0, there exists a closed form solution for the minimizer argmin V∈R k×d ∥A -AV † V∥ 2 F . Specifically, by the Eckart-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 [Woo14] that there exists a family of Gaussian random matrices G 1 from which S ∼ G 1 satisfies with high probability,(1 -ε)∥SAx -Sb∥ 2 ≤ ∥Ax -b∥ 2 ≤ (1 + ε)∥SAx -Sb∥ 2 ,simultaneously for all x ∈ R d . Similarly, there exists [Woo14] a family of Gaussian random matrices G 2 from which S ∼ G 1 satisfies with high probability, that the row space of SA contains a (1 + ε)-approximation of the optimal low-rank approximation to A.Alternatively, we can achieve dimensionality reduction for both linear regression and low-rank approximation by sampling a small subset of the input in related ways for both problems. For linear regression, we can generate a random matrix S by sampling rows of [A b] by their leverage scores [DMM06a, DMM06b, Mag10, Woo14] . In this manner, we again achieve a matrix S such that with high probability,(1 -ε)∥SAx -Sb∥ 2 ≤ ∥Ax -b∥ 2 ≤ (1 + ε)∥SAx -Sb∥ 2 ,simultaneously for all x ∈ R d . For low-rank approximation, we can generate a random matrix S by sampling rows of A with the related ridge-leverage scores [CMM17] . Then with high probability, we have for all V ∈ R k×d ,(1 -ε)∥SA -SAV † V∥ 2 F ≤ ∥A -AV † V∥ 2 F ≤ (1 + ε)∥SA -SAV † V∥ 2 F .B Missing Proofs from Section 3We first show in Section B.1 that it is NP-hard to 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 v (1) , . . . , v (n) ∈ R d , their outer (d -k)-radius is defined as the minimum, over all k-dimensional linear subspaces, of the maximum Euclidean distance of these points to the subspace. We define this problem as Subspace(k, ∞). It is known that it is NP-hard to approximate the Subspace(n -1, ∞) problem within any constant factor: ] ). The Subspace(n -1, ∞) problem is NP-hard to approximate within any constant factor.EQUATIONUtilizing the NP-hardness of approximation of the Subspace(n -1, ∞) problem, we show the NP-hardness of approximation of fair low-rank approximation. Theorem 1.1. Fair low-rank approximation is NP-hard to approximate within any constant factor.Proof. Given an instance v (1) , . . . ,v (n) ∈ R d of Subspace(n -1, ∞) with n < d, we set ℓ = k = n -1 and A (i) = v (i) for all i ∈ [n].Then for a k-dimensional linear subspace V ∈ R k×d , we have that∥A (i) V ⊤ V -A (i) ∥ 2 F is the distance from v (i) to the subspace. Hence, max i∈[ℓ] ∥A (i) V ⊤ V - A (i) ∥ 2F is the maximum Euclidean distance of these points to the subspace and so the fair low-rank approximation problem is exactly Subspace(n -1, ∞). By Theorem B.1, the Subspace(n -1, ∞) 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 a 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 3 literals, either a variable or the negation of a variable. The goal is to determine whether there exists a Boolean assignment to the variables to satisfy the formula.). The 3-SAT problem requires 2 Ω(n) 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(n -1, ∞) through a reduction from the Max-Not-All-Equal-3-SAT problem, whose NPhardness itself is shown through a reduction from 3-SAT. Thus under the exponential time hypothesis, Max-Not-All-Equal-3-SAT problem requires 2 Ω(n) to solve. Then it follows that:Theorem B.3 ([BGK00, DTV11]).Assuming the exponential time hypothesis, then the Subspace(n-1, ∞) problem requires 2 n Ω(1) time to approximate within any constant factor.It follows that under the exponential time hypothesis, any constant-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 k Ω(1) time to approximate within any constant factor.v (1) , . . . , v (k) ∈ R d of Subspace(k -1, ∞) with k < d, we set ℓ = k -1 and A (i) = v (i) for all i ∈ [k].Then for a (k -1)-dimensional linear subspace V ∈ R (k-1)×d , we have that∥A (i) V ⊤ V -A (i) ∥ 2F is the distance from v (i) to the subspace. Hence,max i∈[ℓ] ∥A (i) V ⊤ V -A (i) ∥ 2F is the maximum Euclidean distance of these points to the subspace and so the fair low-rank approximation problem is exactly Subspace(k -1, ∞). By Theorem B.3, the Subspace(k -1, ∞) problem requires 2 k Ω(1) time to approximate within any constant factor. Thus, fair low-rank approximation requires 2 k Ω(1) time to approximate within any constant factor.We first recall the following result for polynomial system satisfiability solvers.). Given a polynomial system P (x 1 , . . . , x n ) over real numbers and m polynomial constraints f i (x 1 , . . . , x n ) ⊗ i 0, where ⊗ ∈ {>, ≥, =, ̸ =, ≤, <} for all i ∈ [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 a solution to the polynomial system P in time (md) O(n) • poly(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.).Let T = {x ∈ R n | f 1 (x) ≥ 0, . . . , f m (x) ≥ 0} be defined by m polynomials f i (x 1 , . . . , x n ) for i ∈ [m]with degrees bounded by an even integer d and coefficients of magnitude at most M . Let C be a compact connected component of T . Let g(x 1 , . . . , x n ) be a polynomial of degree at most d with integer coefficients of magnitude at most M . Then the minimum nonzero magnitude that g takes over C is at least (2 4-n/2 M d n ) -n2 n d n , where M = max(M, 2n + 2m).To perform dimensionality reduction, recall the following definition of affine embedding.Definition B.6 (Affine embedding). We say a matrix S ∈ R n×m is an affine embedding for a matrix A ∈ R d×n and a vector b ∈ R n if we have(1 -ε)∥xA -b∥ 2 F ≤ ∥xAS -bS∥ 2 F ≤ (1 + ε)∥xA -b∥ 2 F , for all vectors x ∈ R d .We then apply the following affine embedding construction. Lemma B.7 (Lemma 11 in [CEM + 15]). Given δ, ε ∈ (0, 1) and a rank parameter k > 0, let m = O k 2 ε 2 log 1 δ . For any matrix A ∈ R d×n , there exists a family S of random matrices in R n×m , such that for S ∼ S, we have that with probability at least 1 -δ, S is a one-sided affine embedding for a matrix A ∈ R d×n and a vector b ∈ R n .We now show a crucial structural property that allows us to distinguish between the case where a guess α for the optimal value OPT exceeds (1 + ε)OPT or is smaller than (1 -ε)OPT by simply looking at a polynomial system solver on an affine embedding. Lemma 3.1. Let V ∈ R k×d be the optimal solution to the fair low-rank approximation problem for inputs A (1) , . . . , A (ℓ) , where A (i) ∈ R ni×d , and supposeOPT = max i∈[ℓ] ∥A (i) V † V -A (i) ∥ 2F . Let S be an affine embedding for V and letW = (VS) † ∈ R k×m . For i ∈ [ℓ], let Z (i) = A (i) SW ∈ R ni×k and R (i) ∈ R k×k be defined so that A (i) SWR (i) has orthonormal columns. If α ≥ (1+ε)•OPT, then for each i ∈ [ℓ], α ≥ ∥(A (i) SWR (i) )(A (i) SWR (i) ) † A (i) -A (i) ∥ 2 F . If α < (1-ε)•OPT, then there exists i ∈ [ℓ], such that α < ∥(A (i) SWR (i) )(A (i) SWR (i) ) † A (i) -A (i) ∥ 2 F .Proof. By the Pythagorean theorem, we have that(A (i) S)(VS) † = argmin X (i) ∥X (i) VS -A (i) S∥ 2 F .Thus,Z (i) = argmin X (i) ∥X (i) VS -A (i) S∥ 2 F for Z (i) = A (i) SW ∈ R ni×k and W = (VS) † ∈ R m×k .Let R (i) ∈ R k×k be defined so that A (i) SWR (i) has orthonormal columns. Thus, we have∥(Z (i) R (i) )(Z (i) R (i) ) † A (i) S -A (i) S∥ 2 F = ∥(Z (i) )(Z (i) ) † A (i) S -A (i) S∥ 2 F = ∥Z (i) VS -A (i) S∥ 2 F = min X (i) ∥X (i) VS -A (i) S∥ 2 F ,by the definition of Z (i) .Suppose α ≥ (1 + ε) • OPT. Since S is an affine embedding for V, then we have that for allX (i) ∈ R ni×k , ∥X (i) VS -A (i) S∥ 2 F ≤ (1 + ε)∥X (i) V -A (i) ∥ 2 F .In particular, we have minX (i) ∥X (i) VS -A (i) S∥ 2 F ≤ (1 + ε) min X (i) ∥X (i) V -A (i) ∥ 2 F ≤ (1 + ε)OPT.Then from the above argument, we have∥(Z (i) R (i) )(Z (i) R (i) ) † A (i) S -A (i) S∥ 2 F = min X (i) ∥X (i) VS -A (i) S∥ 2 F ≤ (1 + ε)OPT ≤ α. Since Z (i) = A (i) SW ∈ R ni×k , then for α ≥ (1 + ε) • OPT, we have that for each i ∈ [ℓ], α ≥ ∥(A (i) SWR (i) )(A (i) SWR (i) ) † A (i) -A (i) ∥ 2 F .On the other hand, suppose α < (1 -ε) • OPT. Let i ∈ [ℓ] be fixed so that OPT = minX (i) ∥X (i) V -A (i) ∥ 2 F .Since S is an affine embedding for V, we have that for allX (i) ∈ R ni×k , (1 -ε)∥X (i) V -A (i) ∥ 2 F ≤ ∥X (i) VS -A (i) S∥ 2 F ,Therefore,(1 -ε) minX (i) ∥X (i) V -A (i) ∥ 2 F ≤ min X (i) ∥X (i) VS -A (i) S∥ 2 FFrom the above, we have∥(Z (i) R (i) )(Z (i) R (i) ) † A (i) S -A (i) S∥ 2 F = min X (i) ∥X (i) VS -A (i) S∥ 2 F .Hence, putting these relations together,α < (1 -ε)OPT = (1 -ε) min X (i) ∥X (i) V -A (i) ∥ 2 F ≤ min X (i) ∥X (i) VS -A (i) S∥ 2 F = ∥(Z (i) R (i) )(Z (i) R (i) ) † A (i) S -A (i) S∥ 2 F ,as desired.We can thus utilize the structural property of Lemma 3.1 by using the polynomial system solver in Algorithm 1 on an affine embedding.Corollary B.8. If α ≥ (1 + ε) • OPT, then Algorithm 1 outputs a vector U ∈ R n×k such that α ≥ ∥UU † A (i) -A (i) ∥ 2 F . If α < (1 -ε) • OPT, then Algorithm 1 outputs ⊥Correctness of Algorithm 2 then follows from Corollary B.8 and binary search on α.We now analyze the runtime of Algorithm 2.Lemma B.9. The runtime of Algorithm 2 is at most1 ε poly(n) • (2ℓ) O(N ) , for n = ℓ i=1 n i and N = poly ℓ, k, 1 ε .Proof. Suppose the coefficients of A (i) are bounded in magnitude by 2 poly(n) , where n = ℓ i=1 n i . The number of variables in the polynomial system is at mostN := 2mk + ℓk 2 = poly ℓ, k, 1 ε .Each of the O (ℓ) 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 ) . By Theorem B.4, the runtime of the polynomial system solver is at most N ) . We require at most O 1 ε log ℓ iterations of the polynomial system solver. Thus, the total runtime is at most(2 4-N/2 2 poly(n) 20 N ) -N 2 N 20 N . Hence, the maximum bit representation required is B = poly(n) • 2 O(N(O (ℓ) • 20) O(N ) • poly(B) = poly(n) • (2ℓ) O(1 ε poly(n) • (2ℓ) O(N ) .Putting things together, we have:Theorem 1.3. Given an accuracy parameter ε ∈ (0, 1), there exists an algorithm which outputs V ∈ R k×d such that with probability at least 2 3 ,max i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F ≤ (1 + ε) • min V∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥ F . The algorithm uses runtime 1 ε poly(n) • (2ℓ) O(N ) , for n = ℓ i=1 n i and N = poly ℓ, k, 1 ε . B.3 Missing Proofs from Section 3.2 Lemma B.10. Let ε ∈ (0, 1) and x ∈ R ℓ and let p = O 1 ε log ℓ . Then ∥x∥ ∞ ≤ ∥x∥ p ≤ (1 + ε)∥x∥ ∞ .Proof. Since it is clear that ∥x∥ ∞ ≤ ∥x∥ p , then it remains to prove ∥x∥ p ≤ (1 + ε)∥x∥ ∞ . Note that we have ∥x∥ p p ≤ ∥x∥ p ∞ • ℓ. To achieve ℓ 1/p ≤ (1 + ε), it suffices to have 1 p log ℓ ≤ log(1 + ε). Since log(1 + ε) = O (ε) for ε ∈ (0, 1), then for p = O 1 ε log ℓ , we have ℓ 1/p ≤ (1 + ε), and the desired claim follows.Lemma 3.5. Let V be the output of Algorithm 3. Then with probability at least 9 10 ,max i∈[ℓ] ∥A (i) ( V) † V-A (i) ∥ F is at most ℓ c •2 1/c •O (k(log log k)(log d)) max i∈[ℓ] ∥A (i) ( V) † V- A (i) ∥ F ,where c is the trade-off parameter input.Proof. We havemax i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F ≤   i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ p F   1/p . Let A = A (1) • . . . • A (ℓ) and let U := AHS.For i ∈ [ℓ], let U (i) be the matrix of U whose rows correspond with the rows of A (i) in A, i.e., let U (i) be the i-th block of rows of U.By the optimality of A (i) ( V) † with respect to the Frobenius norm, we have  i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ p F   1/p ≤   i∈[ℓ] ∥ U (i) V -A (i) ∥ p F   1/pBy Dvoretzky's Theorem, Theorem 3.2, with distortion ε = Θ(1), we have that with probability at least 0.99,  i∈[ℓ] ∥ U (i) V -A (i) ∥ p F   1/p ≤ 2   i∈[ℓ] ∥G U (i) VH -GA (i) H∥ p p   1/p, where we use ∥ • ∥ p to denote the entry-wise p-norm. Writing U = U (1) • . . . • U (ℓ) , then we have  i∈[ℓ] ∥G U (i) VH -GA (i) H∥ p p   1/p = ∥G U VH -GAH∥ p .By the choice of the Lewis weight sampling matrix T, we have that with probability 0.99,∥G U VH -GAH∥ p ≤ 2∥TG U VH -TGAH∥ p ≤ 2∥TG U VH -TGAH∥ (p,2) = 2∥TGAHS(TGAHS) † (TGA)H -TGAH∥ (p,2) ,where ∥M∥ (p,2) denotes the L p norm of the vector consisting of the L 2 norms of the columns of M, and the last equality follows due to our setting of U = AHS and V ← (TGAHS) † (TGA), the latter in Algorithm 3. By optimality of (TGAHS) min X∈R t×d ′ ∥GAHSX -GAH∥ p ≤ 2 p • O √ s • min U∈R n ′ ×t ,V∈R t×d ′ ∥UV -GAH∥ p , for s = O (k log log k). Let V * = argmin V∈R k×d max i∈[ℓ] ∥A (i) -A (i) V † V∥ p . Then since UV has rank t with t ≥ k, we have min U∈R n ′ ×t ,V∈R t×d ′ ∥UV -GAH∥ p ≤ ∥GA(V * ) † V * H -GAH∥ p =   i∈[ℓ] ∥GA (i) (V * ) † V * H -GA (i) H∥ p p   1/p. By Dvoretzky's Theorem, Theorem 3.2, with distortion ε = Θ(1), we have that with probability at least 0.99,  i∈[ℓ] ∥GA (i) (V * ) † V * H -GA (i) H∥ p p   1/p ≤ 2   i∈[ℓ] ∥A (i) (V * ) † V * -A (i) ∥ p F   1/p . For p = c log ℓ with c < 1, we have   i∈[ℓ] ∥A (i) (V * ) † V * -A (i) ∥ p F   1/p ≤ 2 1/c max i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F .Putting together these inequalities successively, we ultimately havemax i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F ≤ 2 p • 2 1/c • O √ st max i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F , for p = c log ℓ, s = O (k log log k), and t = O k(log log k)(log 2 d) . Therefore, we have max i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F ≤ ℓ c • 2 1/c • O (k(log log k)(log d)) max i∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F .It is known that the sum of the leverage scores of the rows of a matrix can be bounded by the rank of the matrix. Theorem C.1 (Generalization of Foster's Theorem, [Fos53] ). Given a matrix M ∈ R n×d , the sum of its leverage scores is rank(M).By sampling rows proportional to their leverage scores, we can obtain a subspace embedding as follows:Theorem C.2 (Leverage score sampling). [DMM06a, DMM06b, Mag10, Woo14] Given a matrix M ∈ R n×d , let σ i be the leverage score of the i-th row of M. Suppose p i = min (1, σ i log n) for each i ∈ [n] and let S be a random diagonal matrix so that the i-th diagonal entry of S is 1 √ pi with probability p i and 0 with probability 1 -p i . Then for all vectors v ∈ R n ,E ∥Sv∥ 2 2 = ∥v∥ 2 2and with probability at least 0.99, for all vectors x ∈ R d 99 100 ∥Mx∥ 2 ≤ ∥SMx∥ 2 ≤ 101 100 ∥Mx∥ 2 .Moreover, S has at most O (d log n) nonzero entries with high probability.Lemma 4.2. Given a matrix M ∈ R n×d , let S be a matrix such that for all x ∈ R d and v ∈ R n ,11 12 ∥Mx∥ 2 ≤ ∥SMx∥ 2 ≤ 13 12 ∥Mx∥ 2 , E ∥Sv∥ 2 2 = ∥v∥ 2 2 . For a fixed B ∈ R n×m where B = b 1 • . . . • b m with b i ∈ R n for i ∈ [m], let x i = (SM) † (Sb i ). Let X = x 1 • . . . • x m .Then with probability at least 0.97, ∥M X -B∥ 2 ≤ 99 min X ∥MX -B∥ 2 .Proof. Let X * = argmin X ∥MX -B∥ 2 and OPT = ∥MX * -B∥ 2 . By triangle inequality,∥SMX -SB∥ 2 ≥ ∥SM(X -X * )∥ 2 -∥SMX * -SB∥ 2 .We have 99 100∥MX∥ 2 ≤ ∥SMX∥ 2 ≤ 101 100 ∥MX∥ 2 for all X ∈ R n×m . Thus, ∥SMX -SB∥ 2 ≥ 99 100 ∥M(X -X * )∥ 2 -∥SMX * -SB∥ 2 .By triangle inequality,∥SMX -SB∥ 2 ≥ 99 100 (∥MX -B∥ 2 -∥MX * -B∥ 2 ) -∥SMX * -SB∥ 2 .Since E ∥Sv∥ 2 2 = ∥v∥ 2 2 for all x ∈ R d , then by concavity and Markov's inequality, we have thatPr [∥SMX * -SB∥ 2 ≥ 49∥MX * -B∥ 2 ] ≤ 1 49 .Thus with probability at least 0.97,∥SMX -SB∥ 2 ≥ 99 100 (∥MX -B∥ 2 -∥MX * -B∥ 2 ) -49∥MX * -B∥ 2 . Now since we have ∥SMX * -SB∥ 2 ≤ 49∥MX * -B∥ 2 and ∥SM X -SB∥ 2 ≤ ∥SMX * -SB∥ 2 , then 49∥MX * -B∥ 2 ≥ 99 100 ∥M X -B∥ 2 -∥MX * -B∥ 2 -49∥MX * -B∥ 2 , so that ∥M X -B∥ 2 ≤ 99∥MX * -B∥ 2 ,as desired.Lemma 4.3. Let S, M (1) , . . . , M (ℓ) be the output of Algorithm 4.Then with probability at least 0.8, max i∈[ℓ] ∥A (i) SM (i) -A (i) ∥ F is at most ℓ c • 2 1/c • O (k(log log k)(log d)) min V∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥ F .Proof. Let V ∈ R t×d be the output of Algorithm 3, where t = O k(log log k)(log 2 d) . Then with probability at least 2 3 , we have maxi∈[ℓ] ∥A (i) ( V) † V -A (i) ∥ F ≤ ℓ c • 2 1/c • O (k(log log k)(log d)) min V∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥ F .Therefore, we havemax i∈[ℓ] min B (i) ∥B (i) V -A (i) ∥ F ≤ ℓ c • 2 1/c • O (k(log log k)(log d)) min V∈R k×d max i∈[ℓ] ∥A (i) V † V -A (i) ∥ F .Let p be a sufficiently large parameter to be fixed. By Dvoretzky's theorem, i.e., Theorem 3.2, with ε = O (1), we havemax i∈[ℓ] min B (i) ∥G (i) B (i) V -G (i) A (i) ∥ p,2 ≤ O (1) • max i∈[ℓ] min B (i) ∥B (i) V -A (i) ∥ F .For sufficiently large p = O (log ℓ), we have by Lemma B.10,max i∈[ℓ] min B (i) ∥B (i) V -A (i) ∥ F . ≤ O (1) • min B (i) ∥G (i) B (i) V -G (i) A (i) ∥ p,2 .By a change of variables, we havemin X ∥X V -GA∥ p,2 ≤ min B ∥GB V -GA∥ p,2 .Note that minimizing ∥X V -GA∥ p,2 over all X corresponds to minimizing∥X i V -G i A∥ 2 over all i ∈ [n ′ ].However, an arbitrary choice of X i may not correspond to selecting columns of A. Thus we apply a leverage score sampling matrix S to sample columns of V which will correspondingly sample columns of GA. Then by Lemma 4.2, we havemin X ∥X VS -GAS∥ p,2 ≤ O (1) • min X ∥X V -GA∥ p,2 .Putting these together, we havemin X ∥X VS-GAS∥ p,2 ≤ ℓ c •2 1/c •O (k(log log k)(log d)) min V∈R k×d max i∈[ℓ] ∥A (i) V † V-A (i) ∥ F . (1)Let S be the selected columns from Algorithm 4 by S and note that A (i) SS † ( V) † V is in the column span of A (i) S for each i ∈ [ℓ]. By Dvoretzky's theorem, i.e., Theorem 3.2, with ε = O (1) and a fixed parameter p, we havemax i∈[ℓ] ∥A (i) SS † ( V) † V -A (i) ∥ F ≤ O (1) • max i∈[ℓ] ∥G (i) A (i) SS † ( V) † V -G (i) A (i) ∥ p,2 .For sufficiently large p, we havemax i∈[ℓ] ∥G (i) A (i) SS † ( V) † V -G (i) A (i) ∥ p,2 ≤ O (1) • ∥GASS † ( V) † V -GA∥ p,2 .By the correctness of the leverage score sampling matrix, we have∥GASS † ( V) † V -GA∥ p,2 ≤ O (1) • ∥GASS † ( V) † VS -GAS∥ p,2 .Observe that minimizing ∥X VS -GAS∥ p,2 over all X corresponds to minimizing∥X i VS - G i AS∥ 2 over all i ∈ [n ′ ]. Moreover, the closed-form solution of the L 2 minization problem is G i ASS † ( V) † = argmin Xi ∥X i VS -G i AS∥ 2 .Therefore, we have∥GASS † ( V) † VS -GAS∥ p,2 ≤ min X ∥X VS -GAS∥ p,2 .Putting things together, we havemax i∈[ℓ] ∥A (i) SS † ( V) † V -A (i) ∥ F ≤ O (1) • min X ∥X VS -GAS∥ p,2 .(By Equation 1and Equation 2 and a rescaling of the constant hidden inside the big Oh notation, we have maxi∈[ℓ] ∥A (i) SS † ( V) † V-A (i) ∥ F ≤ ℓ c •2 1/c •O (k(log log k)(log d)) min V∈R k×d max i∈[ℓ] ∥A (i) V † V-A (i) ∥ F .The desired claim then follows from the setting ofM (i) = S † ( V) † V for i ∈ [ℓ] by Algorithm 4.In this section, we present a number of additional results from our empirical evaluations on socially fair low-rank approximation.We first remark on a number of additional empirical evaluations for socially fair low-rank approximation. We first compare our bicriteria algorithm to the standard low-rank approximation baseline over a simple synthetic example. We then describe a 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 a 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 simpleA (1)= 2 0 0 0 0 2 0 0 and A (2) = 0 0 1.99 0 0 0 0 1.99 . An optimal fair low-rank solution for k = 2 is 1 0 0 0 0 0 1 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.99 2 ≈ 7.92, such as the factors 1 0 0 0 0 1 0 0 . Thus the ratio between the objectives is roughly 1 2 , i.e., the improvement is roughly a factor of two. We show in Figure 2 that our bicriteria algorithm achieves similar improvement.Experimental setup. Again, we compare our bicriteria algorithm from Algorithm 3 against the standard non-fair low-rank approximation algorithm that outputs the top k right singular vectors from the singular value decomposition. Per Dvoretzky's Theorem, c.f., Theorem 3.2, we generate normalized Gaussian matrices G and H of varying size and then use L p Lewis weight sampling to generate a matrix T with varying values of p. 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 p = 1 and iterate over the number of rows/columns in the Gaussian sketch in the range {1, 2, . . . , 19, 20} in Figure 2a . We then fix the Gaussian sketch to have three rows/columns and iterate over p ∈ {1, 2, . . . , 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 k ′ for k ′ > k. 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 of p in 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-concept. Finally, we give a toy example using a synthetic dataset showing the importance of considering fairness in low-rank approximation. Namely, we show that even for a 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 (1) , A (2) , A (3) , A (4) ∈ {0, 1} 2 , with A (1) = (1, 0) and A (2) = A (3) = A (4) = (0, 1). The optimal fair low-rank solution is√ 2 2 , √ 2 2but due to the extra instances of (0, 1), the standard low-rank algorithm will output the factor (0, 1). Thus the optimal fair solution achieves value 1 4 on the socially fair low-rank approximation objective while the standard low-rank approximation solution achieves value 1 2 , so that the ratio is a 50% improvement.This paper presents research aimed at reducing biases in key data summarization tasks. Our work is driven by the societal implications of machine learning techniques, representing a series of results towards developing more equitable methods in this field.(1) 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 in 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 as long as it 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 no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important 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 a complete (and correct) proof? 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 a 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, or as supplemental material.( 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to 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 or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).(10) Broader Impacts Question: Does the paper discuss both potential positive societal 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML).(11) Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our dataset was acquired from a publicly available repository and thus we do not introduce new data in this paper.Guidelines:• The answer NA means that the paper poses no 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.(12) Licenses for existing assets Question: 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?Answer: [Yes]Justification: All original assets used in this paper have been referenced appropriately.Guidelines:• The answer NA means that the paper does not 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 a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 is not available online, the authors are encouraged to reach out to the asset'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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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 an equivalent approval/review based on the requirements of your country or 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 nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The paper is not easy to read. The introduction may be shortened.
questions: 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: Limitations adequately addressed by the authors.
paper_summary: paper_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.

First 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.
strength_weakness: strength_weakness: 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.

I 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.
questions: questions: Line 58: $U = U_1 \circ \dots \circ U_k$, what operations does $\circ$ symbol denote?

Line 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?

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?

Line 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?

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?

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.

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.
limitations: limitations: No discussion on potential negative social impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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?

2)  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?   

3) 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?

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


Other comments
- missing definition of $k$ in the abstract
- 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}$. 
- 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: limitations: The authors have addressed limitations adequately.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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.
questions: questions: Is it possible to make the proposed algorithms run in parallel?
limitations: limitations: This is a theoretical paper, there are no potential negative societal impacts.

Comments: title: Re: Official comment
Re: followup for official comment(s)
Response to rebuttal
comment: **[Lower bound on number of columns: Actually, while Matakos et al. (2023) considers $\dots$ ]** I agree with the authors on this point, and they are correct.
Thank you for both the continued correspondence and the time for taking an additional pass over our paper. We really appreciate the extra effort by the referee toward the overall review process -- our paper will certainly benefit from the thorough feedback. 

>...For example, the matrix $A$ is sometimes referred to as $M$, with corresponding changes from $A^{(i)}$ to $M^{(i)}$ and the column matrix is inconsistently labeled as $C$, $V$, or $S$ across different sections. $B^{(i)}$ is used before it is defined. In Lemma 3.5, $c$ is not defined; one has to go to the proof of the Lemma in Line 725 to even known what is $c$ or refer back to the statement in Theorem 1.4.

For what it's worth, our intention is to use $A$ as the input matrix to the problem and $M$ as an input matrix for leverage score sampling, the matrices $\{A^{(i)}\}$ as the input groups, and the matrices $\{M^{(i)}\}$ as outputs to Algorithm 4. We will unify $C$ and $S$ as the column selection matrix, and our intention is to use $V$ as a set of rank-$k$ factors that need not be restricted to a subset of columns. We will make the implicit definition of $B^{(i)}$ in Line 286 more explicit. Finally, we agree that the trade-off parameter $c<1$ is not clearly stated prior to Lemma 3.5. We apologize for the confusion -- we will clarify the purpose of $c$ in the statement of Lemma 3.5, as well as the surrounding context. 

> Also, Matakos et al. (2023) have established a lower bound on the number of columns, $k\ell$, and choosing fewer columns than this would make it unbounded. Therefore, the results for column subset selection are only meaningful if $\ell\gg\log k$ (a similar comment also noted by reviewer CrGT in the context of Theorem~1.3).

Actually, while Matakos et al. (2023) considers the same intuitive goal of choosing $k$ columns to minimize the maximum cost, their cost function is normalized by $\frac{1}{||A^{(i)}-A^{(i)}_k||_F}$, where $A^{(i)}_k$ is the best rank-$k$ approximation to $A^{(i)}$. Therefore, the lower bound of Matakos et al. (2023) does not apply to our objective. 

For example, it can be shown that returning the best $k$ columns for our column subset selection objective on the entire matrix $A=A^{(1)}\circ\ldots\circ A^{(\ell)}$ is an $\ell$-approximation to the fair column subset selection problem. Thus, it is not necessary to choose $k\ell$ columns and more generally, our results for column subset selection do actually hold across all settings of $\ell$.

> I acknowledge that the paper may have strong theoretical contributions, and if all the claimed results are correct, they are significant. However, despite my experience with similar topics, I struggled to follow the proof arguments due to unclear writing and constant change in notation. The authors should recognize that this level of writing is not ideal and likely falls short of the standard while reviewing. Sections 3, 4, and 5 are particularly problematic. Even after multiple clarifications, these sections remain difficult to read and understand. While the statements and approaches appear correct at a high level, verifying the proofs becomes tedious due to the way the it is presented, making it difficult to check the details precisely.

Thank you for your positive assessment of the theoretical contributions. We emphasize that we are fully committed to improving the overall presentation of the paper, so that it is accessible to the general research community.
I thank authors for their responses. 

After carefully checking the rebuttal and considering the comments from other reviewers, I went through the paper again. Unfortunately, I still find it challenging to follow the arguments and writing due to inconsistent and confusing notation. For example, the matrix $A$ is sometimes referred to as $M$, with corresponding changes from $A^{(i)}$ to $M^{(i)}$, and the column matrix is inconsistently labeled as $C$, $V$, or $S$ across different sections. $B^{(i)}$ is used before it is defined. In Lemma 3.5, $c$ is not defined; one has to go to the proof of the Lemma in Line 725 to even known what is $c$ or refer back to the statement in Theorem 1.4. Such inconsistency makes the paper difficult to read and understand. Also, the equations are poorly organized and spread across multiple lines. I often had to rewrite these equations on a paper to make sense of them.

I acknowledge that the paper may have strong theoretical contributions, and if all the claimed results are correct, they are significant. However, despite my experience with similar topics, I struggled to follow the proof arguments due to unclear writing and constant change in notation. The authors should recognize that this level of writing is not ideal and likely falls short of the standard while reviewing. Sections 3, 4, and 5 are particularly problematic. Even after multiple clarifications, these sections remain difficult to read and understand. While the statements and approaches appear correct at a high level, verifying the proofs becomes tedious due to the way the it is presented, making it difficult to check the details precisely.

Being said that, I am not fully confident about the correctness of the proofs, so I will retain my original evaluation. To be clear, my evaluation is based on the difficulty in validating the claims due to the imprecise writing. If the theoretical contributions are correct, this work is a valuable addition in the study of fair variants of matrix approximation problems. I hope other reviewers have been able to thoroughly check the proofs in ways I could not.

Regarding the proof arguments in Section 5, they seem to hold at a high level. Also, Matakos et al. (2023) have established a lower bound on the number of columns, $k \ell$, and choosing fewer columns than this would make it unbounded. Therefore, the results for column subset selection are only meaningful if $\ell \gg \log k$ (a similar comment also noted by reviewer CrGT in the context of Theorem~1.3).
Thank you for your reply. I believe this is a strong paper and I will maintain my score.
I'd like to thank the authors for replying to my concerns. I will keep my score unchanged. Please add some descriptions for the scenarios where k is a small constant.
Thank you for the follow-up questions! We hope the following clarifications address your points; if not, we would also be happy to continue discussing any possible concerns. 

> ["slight typo" in Line 286] In the current formulation of the submitted paper, the dimensions of the matrices do not match, which the authors have casually dismissed this as a "slight typo." This, however, is a significant error, raising concerns about whether the proofs in Section 4 were thoroughly read and verified. Given that the objective being minimized was not accurately stated, it is unclear how one could have validated the claimed approximation ratios and algorithmic results in that section. 

We would like to emphasize that the objective function precisely matches both the informal description of the problem, i.e., "to select $k$ columns", and the subsequent analysis. In particular, the cost $||A^{(i)}CB^{(i)}-A^{(i)}||_F$ precisely matches the cost in Lemma 4.3 $||A^{(i)}SM^{(i)}-A^{(i)}||_F$ up to a change of notation (where $C$ is $S$ and $B^{(i)}$ is $M^{(i)}$). Note that $C\in\mathbb{R}^{d\times k}$ and $B^{(i)}\in\mathbb{R}^{k\times d}$ for all $i\in[\ell]$, so that $A^{(i)}CB^{(i)}$ has dimension $n_i\times d$, which is the same as the dimension of $A^{(i)}$. Therefore, the dimensions match. 

For the sake of consistency, we further remark that Reviewer CrGT raised a similar question about the objective and we provided a response that exactly matches these details, i.e., see the response to Reviewer CrGT (https://openreview.net/forum?id=EO1Qev952p&noteId=A1p5yN7fG0)

> [improving writing] The authors do not seem fully committed to revising the writing to enhance the accessibility of their research, as the descriptions currently lack clarity. In my view, the paper requires significant revision to be accessible to a wider audience. Unless the authors address these concerns and demonstrate a strong commitment to improving the writing, I would maintain my current evaluation.

We apologize that our initial response conveys this sentiment. We are fully committed to producing a manuscript that is accessible to the general research community and in fact, we have already incorporated the explicit suggestions from the initial reviews. We are also taking additional more thorough passes to improve the overall exposition of the paper, as well as preparing a "full version" with the complete details and additional intuition in the main body. We hope these updates will address the remaining concerns.
**["slight typo" in Line 286]** In the current formulation of the submitted paper, the dimensions of the matrices do not match, which the authors have casually dismissed this as a "slight typo." This, however, is a significant error, raising concerns about whether the proofs in Section 4 were thoroughly read and verified. Given that the objective being minimized was not accurately stated, it is unclear how one could have validated the claimed approximation ratios and algorithmic results in that section. 

**[improving writing]** The authors do not seem fully committed to revising the writing to enhance the accessibility of their research, as the descriptions currently lack clarity. In my view, the paper requires significant revision to be accessible to a wider audience. Unless the authors address these concerns and demonstrate a strong commitment to improving the writing, I would maintain my current evaluation.