Research map / Learning theory and algorithms / Matrix and tensor methods
On Socially Fair Low-Rank Approximation and Column Subset Selection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies socially fair (min-max group) low-rank approximation and column subset selection, proving hardness, giving a (1+eps) algorithm running in 2^poly(k) time for constant groups, and polynomial-time bicriteria algorithms for both problems.
Problem
Low-rank approximation and column subset selection that minimize the maximum reconstruction loss across sub-populations (groups) of the data, i.e., socially fair versions of these problems.
Approach
Formulates fair LRA/CSS as a min-max objective over groups; shows constant-factor hardness (NP-hard, ETH lower bound), gives a polynomial-system-based (1+eps) algorithm exploiting affine embeddings and a small number of groups, and polynomial-time bicriteria algorithms via Dvoretzky-type embeddings of Frobenius max into entrywise L_p with Lewis weight sampling.
Key results
- Fair low-rank approximation is NP-hard to approximate within any constant factor, and under ETH requires 2^{k^{Omega(1)}} time for constant-factor approximation.
- A (1+eps)-approximation runs in (1/eps) poly(n) (2l)^{O(N)} time, improving on naive n^{poly(k)} for constant number of groups l.
- On the Default Credit dataset, the bicriteria algorithm achieves cost ratios below 1 versus SVD in many settings, with some ratios below 0.6.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the optimal fair low-rank solution instead of standard low-rank approximation | Synthetic two-group, two-observation example · Synthetic two-group, two-observation example | socially fair objective value: 4 vs. 2·1.99^2≈7.92; ratio roughly 1/2 | Helped |
| use the optimal fair low-rank solution instead of standard low-rank approximation | Synthetic four-group, one-observation example · Synthetic four-group, one-observation example | socially fair objective value: 1/4 vs. 1/2; 50% improvement | Helped |
| use the bicriteria fair low-rank approximation instead of standard low-rank approximation | Synthetic dataset, rank k=2 · Synthetic dataset, Gaussian sketch and Lewis sampling sweeps | fair-cost ratio to standard low-rank approximation: average ratio ... less than 0.9; minimum ratio ... 0.76 | Helped |
| use the bicriteria fair low-rank approximation instead of standard low-rank approximation | Default of Credit Card Clients · Default of Credit Card Clients | fair-cost ratio to standard low-rank approximation: less than 0.6 | Helped |
Surprising findings
- Even constant-factor approximation to fair low-rank approximation is NP-hard and requires exponential time under ETH, unlike fair regression which is polynomial-time solvable.
Limitations
- The (1+eps) algorithm is exponential in the number of groups and poly(k) in the exponent, so it is only practical for a constant number of groups.
- The bicriteria algorithms return solutions of larger rank t = O(k log log k log^2 d) and approximation factors that depend on ell^c and polylog d.
- Experiments are small-scale proof-of-concept on one real dataset with gender as the sensitive attribute.
Experimental setup
Datasets: Default of Credit Card Clients
Benchmarks: Default of Credit Card Clients
Metrics: ratio of fair min-max Frobenius cost to standard SVD cost runtime
Baselines: standard SVD low-rank approximation
Builds on: Dvoretzky's theorem Lewis weight sampling exponential time hypothesis Eckart-Young-Mirsky theorem
Closest papers by meaning
- Optimal Analysis of Subset-Selection Based L_p Low-Rank Approximation (NeurIPS 2019 · similarity 0.89)
- Towards a Zero-One Law for Column Subset Selection (NeurIPS 2019 · similarity 0.89)
- Fair Submodular Cover (ICLR 2025 · similarity 0.86)
- Improved Algorithms for Fair Matroid Submodular Maximization (NeurIPS 2025 · similarity 0.85)
- Linear Time Approximation Algorithm for Column Subset Selection with Local Search (NeurIPS 2024 · similarity 0.85)
- Multi-View Unsupervised Column Subset Selection via Combinatorial Search (Student Abstract) (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.