mlsanityData to 14 Oct 2026

On Socially Fair Low-Rank Approximation and Column Subset Selection

arXiv 2412.06063 ↗First posted 8 Dec 2024cs.LG cs.DS stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

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 2poly(k) time rather than the na"ive npoly(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 run in polynomial time.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 48 of its 77 references that are in the map. First posted on arXiv 8 Dec 2024.

Builds on

48 of 77 references.

References · 48

  1. 2016Equality of Opportunity in Supervised Learningcited by 2,007
  2. 2016Fair prediction with disparate impact: A study of bias in recidivism prediction instrumentscited by 672
  3. 2016Inherent Trade-Offs in the Fair Determination of Risk Scorescited by 586
  4. 2017Algorithmic decision making and the cost of fairnesscited by 403
  5. 2017Fairness in Criminal Justice Risk Assessments: The State of the Artcited by 315
  6. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  7. 2018Fair Clustering Through Fairletscited by 176
  8. 2019Fair Regression: Quantitative Definitions and Reduction-based Algorithmscited by 168
  9. 2017A Convex Framework for Fair Regressioncited by 148
  10. 2019Fair Algorithms for Clusteringcited by 98
  11. 2019Scalable Fair Clusteringcited by 78
  12. 2018The Price of Fair PCA: One Extra Dimensioncited by 67
36 more
  1. 2019Fair k-Center Clustering for Data Summarizationcited by 65
  2. 2020Individual Fairness for k-Clusteringcited by 56
  3. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  4. 2015Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Samplingcited by 46
  5. 2018On the cost of essentially fair clusteringscited by 44
  6. 2020Fair clustering via equitable group representationscited by 43
  7. 2017Active Regression via Linear-Sample Sparsificationcited by 36
  8. 2020Active Sampling for Min-Max Fairnesscited by 33
  9. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  10. 2020Probabilistic Fair Clusteringcited by 28
  11. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  12. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  13. 2020Fair Hierarchical Clusteringcited by 25
  14. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  15. 2023Efficient fair PCA for fair representation learningcited by 23
  16. 2018Convex Formulations for Fair Principal Component Analysiscited by 20
  17. 2018Near Optimal Linear Algebra in the Online and Sliding Window Modelscited by 19
  18. 2021Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifoldcited by 18
  19. 2021L1 Regression with Lewis Weights Subsamplingcited by 14
  20. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  21. 2022Fast Regression for Structured Inputscited by 11
  22. 2023New Subset Selection Algorithms for Low Rank Approximation: Offline and Onlinecited by 11
  23. 2019Regularized Weighted Low Rank Approximationcited by 10
  24. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
  25. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  26. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  27. 2021Streaming and Distributed Algorithms for Robust Column Subset Selectioncited by 6
  28. 2021Clustering with fair-center representation: parameterized approximation algorithms and heuristicscited by 6
  29. 2024Fair Submodular Covercited by 6
  30. 2018Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Normscited by 4
  31. 2022Fair Representation Clustering with Several Protected Classescited by 4
  32. 2022Fair Range k-centercited by 4
  33. 2022Near-Linear Sample Complexity for Lp Polynomial Regressioncited by 4
  34. 2023Fair Column Subset Selectioncited by 4
  35. 2021Active Linear Regression for ℓp Norms and Beyondcited by 3
  36. 2023Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorizationcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Fair PCA, One Component at a Timecited by 0
  2. 2026Active Learning with Low-Rank Structure for Data Selectioncited by 0