On Socially Fair Low-Rank Approximation and Column Subset Selection
Authors: Zhao Song, Ali Vakilian, David Woodruff, Samson Zhou
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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 human-centric data used for benchmarks on fairness, e.g., see [STM+18]. We perform empirical evaluations comparing the objective value and the runtime of our bicriteria algorithm with the aforementioned baseline, across various subsample sizes and rank parameters. Our results demonstrate that our bicriteria algorithm can perform better than the standard low-rank approximation algorithm across various parameter settings, even when the bicriteria algorithm is not allowed a larger rank than the baseline. |
| Researcher Affiliation | Academia | Zhao Song The Simons Institute for the Theory of Computing UC Berkeley magic.linuxkde@gmail.com, Ali Vakilian Toyota Technological Institute at Chicago vakilian@ttic.edu, David P. Woodruff Department of Computer Science Carnegie Mellon University dwoodruf@andrew.cmu.edu, Samson Zhou Department of Computer Science Texas A&M University samsonzhou@gmail.com |
| Pseudocode | Yes | Algorithm 1 Input to polynomial solver, Algorithm 2 (1+ε)-approximation for fair low-rank approximation, Algorithm 3 Bicriteria approximation for fair low-rank approximation, Algorithm 4 Bicriteria approximation for fair column subset selection |
| Open Source Code | Yes | Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Yes, open access to the data and code are provided in the full version. |
| Open Datasets | Yes | Our experiments are on the Default of Credit Card Clients dataset [YL09], which is a common human-centric data used for benchmarks on fairness, e.g., see [STM+18]. The dataset was accessed through the UCI repository [Yeh16]. DOI: https://doi.org/10.24432/C55S3H. |
| Dataset Splits | No | The paper mentions using a 'Default of Credit Card Clients dataset' and 'sampled a small number s of rows from A(1) and A(2)', but does not specify explicit train/validation/test splits, percentages, or methodology for partitioning the data into these sets. |
| Hardware Specification | Yes | 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. |
| Software Dependencies | No | The paper mentions 'Python 3.10' as the programming language used but does not provide specific version numbers for any libraries, frameworks, or other ancillary software dependencies. |
| Experiment Setup | Yes | 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 Lp 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. |