On Socially Fair Low-Rank Approximation and Column Subset Selection

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?

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

Additionally, in most practical instances, $k$ is usually a small constant. Therefore, for these instances our algorithm provides a polynomial time constant factor approximations.

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.

We will apply your suggestion in the next version of our paper, thank you.

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?

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

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?

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

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?

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

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

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

Thank you for your reply. I believe this is a strong paper and I will maintain my score.

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.

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

Line 58: $U=U_1\circ\cdots\circ U_k$, what operations does $\circ$ symbol denote?

$\circ$ denotes vertical concatenation of the rows, c.f., line 542 in the preliminaries.

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?

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

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?

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

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?

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

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.

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

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.

Ah 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)}$.

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

The paper is not easy to read. The introduction may be shortened.

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.

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.

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