Consistent Multigroup Low-rank Approximation

Thank you for your comprehensive review and for sharing new interesting ideas.

"The convexity analysis indicates that the primal problem is non-convex, which might raise concerns about convergence guarantees for more than two groups. Can the authors provide comment and a numerical test to mitigate this concern? A more detailed discussion about the limitations for a high number of groups would be beneficial for the paper. Non-convexity of the optimization problem raises concerns of convergence issues in practice."

Thank you for raising this excellent point. We will add to the current manuscript a discussion on the regime of a high number of groups in the data, focusing on the convergence of our algorithms and offering numerical tests.

A note on the convergence of our method. We clarify that, even though the primal problem is indeed non-convex, the dual problem is always convex. In our work, we introduce algorithms that either solve the dual problem or its dual (the bidual). Thus, from an optimization perspective, our algorithms solve convex problems so that they are always expected to converge, which is why we have not included an extensive discussion of convergence issues in the manuscript.

The effect of the number of groups on convergence. As we discuss in the manuscript, for more than two groups strong duality does not hold in general, meaning that our algorithms are not guaranteed to retrieve the optimal solution of the primal problem (but only the optimal solution of the dual problem). However, as we show in the experimental evaluation, the duality gap is consistently narrow. In practice, our algorithms quickly converge, regardless of the number of groups. If the reviewer is interested, we have added a simple numerical experiment to our repository showing that our method quickly converges also when the number of groups becomes large (https://anonymous.4open.science/r/multigroupSVs-F716/notebooks/ManyGroupsExample.ipynb).

"The experiments cover the case of more than 2 groups, where some theoretical guarantees (optimality) are not valid. The results look reasonable. Question: How does the method perform for a high number of groups, i.e. more than 20 groups?"

This is certainly an interesting question.

A note on the choice of datasets in our experiments. Consistent with related work, we primarily rely on benchmark datasets that can be naturally partitioned in two, three or four groups, which is a setting particularly widespread in the real world. At the same time, for the specific purposes of the experiments, considering too large datasets (with many large groups), provided that they can be found, would preclude the comparison with the main baseline (FAIR-PCA), which hinges upon an expensive SDP solver and thus quickly incurs scalability issues as the data size grows.

The setting with a large number of groups. We note that the Frank-Wolfe algorithm and the SDP we introduce can handle any number of groups, and their performance is not intrinsically connected to the number of groups. This is also suggested by the experimental results on the COMPAS and COMMUNITIES dataset (although the number of groups increases only up to three and four). Nevertheless, as thoughtfully observed by the reviewer, it is interesting to study the behavior of our method as the number of groups becomes very large. Should the reviewer already wish to explore this question further, we have added to our repository a simple numerical experiment to investigate the duality gap (and hence the performance) of our method as the number of groups increases from 3 to 25 (https://anonymous.4open.science/r/multigroupSVs-F716/notebooks/ManyGroupsExample.ipynb).

"Please fix the formatting of Figure 3 in the appendix, it seems to be out of bounds."

Thank you for noticing. We will fix the figure to constrain it within the page bounds.

"Could the framework be extended to nonlinear low-rank approximation methods (e.g., kernel PCA)?"

We thank the reviewer for this stimulating suggestion. Developing a nonlinear method for consistent multigroup low-rank approximation surely represents an exciting avenue for future research.
We believe that both our problem formulation and method are amenable to extension toward nonlinear settings.
Specifically, since our method is inspired from the SVD, future work could introduce a method inspired from Kernel SVD (or Kernel PCA). To accomplish this, we would compute a kernel matrix and then extract and study the multigroup singular vectors associated with the kernel matrix.

We sincerely thank you for your review and valuable comments, which will also be very useful in future work.

"The method proposed by the author may bring new inspiration in solving large-scale problems?"

Our method guarantees high scalability. We appreciate the suggestion of the reviewer. An important advantage of our method over existing approaches for closely related problems is the scalability it ensures. By imposing the consistency property on the output low-rank representation, we effectively decompose a larger problem into multiple smaller problems that can be efficiently solved. The Frank-Wolfe algorithm we introduce as well as the algorithm we design tailored to the two-group case (but not the SDP solver) scale to large problem instances.

Possibilities for future work addressing large-scale problems. For future work, it would be interesting to study even more scalable (stochastic) hardware-accelerated gradient-based solutions to extract multigroup singular vectors. It would also be interesting to study different applications of our method beyond fairness, since our method can provide high-quality data compression whenever a partitioning of the data in multiple groups is relevant.

"Although the paper is innovative as a whole, there is insufficient emphasis on the comparison and differentiation between the paper and the existing research when explaining the innovation points. The essential differences in principle, algorithm and performance from existing multi-group data dimensionality reduction methods should be pointed out more clearly. It is suggested that the author improve the content of related work and introduce the research content in detail to facilitate readers' understanding."

As pointed out when addressing the comments of Reviewer 2Q4n, we fully share this concern. We will give more details on related work, with particular emphasis on the work of Samadi et al (2018)., which represents the closest existing work to ours. We will highlight more the fundamental aspects that set our problem and method apart from related work, and we will separate more clearly our innovation points from the state of the art in multigroup-data dimensionality reduction.

"I have a question about whether the method studied by the author can be effectively transferred to other fields such as clustering and matrix completion "

We again thank the reviewer for their useful suggestions.

Clustering. Unlike clustering methods, our method considers a partitioning of the data into groups that is given as input.

However, our method, being a low-rank approximation method, could be used to address clustering tasks. For instance, one can take advantage of our method in preprocessing, to extract informative features that can be used by existing clustering algorithms.

Similarly, clustering algorithms can be used to address multigroup low-rank approximation. In particular, we can leverage clustering algorithms prior to our method to find a meaningful partitioning of the data into clusters (i.e., a clustering). Then, we can give the clustering in input to our method and obtain a balanced low-rank approximation that takes the clustering into consideration.

For future work, it would be valuable to design an iterative procedure that combines clustering and multigroup low-rank approximation, by iteratively optimizing the clustering structure and the corresponding multigroup low-rank approximation.

Matrix completion. Our method can also be regarded as an extension of the singular value decomposition (SVD) that incorporates a partitioning of the data into multiple groups. The SVD has been successfully leveraged to tackle matrix-completion tasks. Given a partially observed matrix, our method could be extended to address matrix-completion tasks by accounting for the missing values. In this direction, a straightforward approach would be to impute the missing values (e.g., by the mean), and then compute the multigroup singular vectors and the resulting multigroup low-rank approximation as usual. In future work, we will study more refined approaches for multigroup matrix-completion tasks.

Thank you for your thorough review. We understand your concerns, and we believe that your feedback gives excellent input for improving the manuscript.

We begin by carefully addressing the reviewer’s main concern, i.e., the novelty of our work in the context of previous work, notably that of Samadi et al. (2018). We acknowledge that the distinction between our work and that of Samadi et al. has not been sufficiently clarified.

Different problem. Our problem and the problem studied by Samadi et al. are fundamentally different. Intuitively, given an integer $d$, Samadi et al. seek a balanced rank-$d$ approximation of the data. The obtained solution is not related to the solutions of lower rank by any straightforward transformation. On the other hand, our problem asks for a rank-$d$ approximation where balance is also achieved in all dimensions lower than $d$. We call this the consistency property, inspired by the SVD: given a rank-$d$ SVD, for all $d’ < d$ the rank-$d’$ approximation is also optimal.

Different loss function. We note that our min-max loss is only equal to the Samadi et al. marginal loss in the rank-$1$ sub-problem. Our final solution of rank-$d$ (by Algorithm 1), optimizes the incremental loss not the marginal loss. There is a crucial difference: the incremental loss for a rank-$d$ solution is the sum of $d$ rank-$1$ min-max losses, whereas the marginal loss directly applies the min-max criterion to a rank-$d$ solution and cannot be decomposed into separate rank-$1$ losses.

Different methodology. Our approach for obtaining a rank-$d$ solution is based on an orthonormalization procedure similar to that of the SVD (Algorithm 1) based on solving iteratively a rank-$1$ problem, instead of directly solving a rank-$d$ SDP. We highlight important differences:

• The rank-$1$ sub-problem is solved by a novel primal-dual framework unlike Samadi et al. For this problem, we use a variety of methods such as Frank-Wolfe, root-finders, or SDP.

• Regarding the SDP: our SDP is tailored to the rank-$1$ dual-problem only, and is based on the bidual of the rank-$1$ problem, with different constraints.

• Our approach always returns a rank-$1$ solution, unlike Samadi et al., which requires one extra dimension.

Finally, we visually demonstrate that the method of Samadi et al., unlike our method, does not guarantee the consistency property through a simple example, which can be found in our repository (https://anonymous.4open.science/r/multigroupSVs-F716/notebooks/ConsistencyExample.ipynb).

Relevance of consistency in view of previous work. Consistency yields several practical advantages. Just like SVD or PCA, the user can run our method once, and then retain the desirable number of basis vectors. Instead, the method of Samadi et al. needs to be run separately for all possible values of $d$, possibly obtaining drastically different approximations, which can be cumbersome in many applications (e.g., in extracting and selecting features for a machine-learning model).

The consistency property furthermore means that the basis vectors output by our method are meaningful, and they can be interpreted as the principal components, that is, the orthogonal directions of maximum variance when considering all groups.

In addition, as remarked in Section 1, the consistency property breaks down a large problem into several smaller problems, offering significant benefits in terms of computational efficiency and scalability.

Empirical evaluation of consistency. As rightly noted by the reviewer, the metrics do not imply the consistency on their own. The consistency is achieved by the sequential orthonormalization process described in Algorithm 1. In the experimental evaluation, to ensure an unbiased comparison, we monitor the different loss functions that are optimized by our method and the baselines. The results of the experiments in Figure 2,3 and 4 empirically demonstrate the consistency property: the errors incurred by the method of Samadi et al. can deviate drastically across groups for $d' < d$, which is not the case for our method.

More discussion in Section 7. We agree with the reviewer; more details will be added to Section 7.

• Theorem 7.1 states that Problem 1 is computationally tractable, and can be solved efficiently by any of the algorithms we propose, as will be clarified.

• As for Lemma 7.2, a tight semidefinite-program relaxation is one where the optimal solution of the relaxed problem corresponds to the optimal solution of the original problem. We will expand the statement of the lemma.

• Finally, in Lemma 7.3, we will explain the exact meaning of equal error in this context.

Conclusion. Our work bridges the gap between the existing literature in multigroup (or fair) low-rank approximation and the standard SVD and PCA, and, as shown by our thorough experimental evaluation, provides an unprecedented trade-off between result quality and efficiency.