提出公平低秩分解与列选择算法，兼顾不同群体数据的精度均衡。
On Socially Fair Low-Rank Approximation and Column Subset Selection
- 设计基于分组的公平性优化方法，确保各子群体误差均衡。
- 证明常数近似需指数时间，但常数组数下可实现亚多项式复杂度。
- 给出多项式时间双准则近似算法，适合大规模公平数据分析。
低秩近似和列子集选择是机器学习中两个基础且密切相关的问题。本文研究社会公平性低秩近似与列子集选择，目标是在所有数据子群体上最小化损失。我们发现，即使在常数因子近似下，公平低秩近似在某些标准复杂性假设下仍需指数时间。但在常数个群体和常数精度条件下，我们提出一个运行时间为 $2^{ ext{poly}(k)}$ 的算法，远优于朴素的 $n^{ ext{poly}(k)}$，当样本量 $n$ 很大时具有显著优势。此外，我们还构造了多项式时间的双准则近似算法，适用于公平低秩近似与公平列子集选择。
原文摘要 · Abstract (English)
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 $2^{\text{poly}(k)}$ time rather than the naïve $n^{\text{poly}(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。