Multi-Criteria Dimensionality Reduction with Applications to Fairness
Multi-Criteria Dimensionality Reduction with Applications to Fairness
复制标题
DOI：
--
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
U. Tantipongpipat;S. Samadi;Mohit Singh;Jamie Morgenstern;S. Vempala
中科院分区：
文献类型：
--
作者：
U. Tantipongpipat;S. Samadi;Mohit Singh;Jamie Morgenstern;S. Vempala
近似性约简是一种广泛应用于数据分析的经典技术。一个基本的实例是主成分分析（PCA），它使平均重建误差最小化。在本文中，我们介绍了多准则降维问题，我们被赋予多个目标，需要同时优化。作为一个应用，我们的模型捕获了几个降维的公平标准，例如Samadi等人引入的Fair-PCA问题[NeurIPS 18]和Nash社会福利（NSW）问题。在Fair-PCA问题中，输入数据被分成k组，目标是为所有组找到一个单一的d维表示，使任何一组的最大重建误差最小化。在新南威尔士州的目标是最大限度地提高产品的个人方差的群体所取得的共同的低维空间。我们的主要结果是一个精确的多项式时间算法的双准则降维问题的两个标准时，这两个标准是增凹函数。作为这一结果的应用，我们得到了一个多项式时间算法的公平PCA为k=2组，解决了一个公开的问题Samadi等人。[NeurIPS 18]，以及针对k=2组的NSW目标的多项式时间算法。我们还给出了k>2的近似算法。我们在上述结果中的技术贡献是证明了半定规划极值点解的新的低秩性质。我们得出结论，几个实验的结果表明，我们的算法在现实世界的数据集上的性能提高和推广应用。
Dimensionality reduction is a classical technique widely used for data analysis. One foundational instantiation is Principal Component Analysis (PCA), which minimizes the average reconstruction error. In this paper, we introduce the multi-criteria dimensionality reduction problem where we are given multiple objectives that need to be optimized simultaneously. As an application, our model captures several fairness criteria for dimensionality reduction such as the Fair-PCA problem introduced by Samadi et al. [NeurIPS18] and the Nash Social Welfare (NSW) problem. In the Fair-PCA problem, the input data is divided into k groups, and the goal is to find a single d-dimensional representation for all groups for which the maximum reconstruction error of any one group is minimized. In NSW the goal is to maximize the product of the individual variances of the groups achieved by the common low-dimensinal space. Our main result is an exact polynomial-time algorithm for the two-criteria dimensionality reduction problem when the two criteria are increasing concave functions. As an application of this result, we obtain a polynomial time algorithm for Fair-PCA for k=2 groups, resolving an open problem of Samadi et al.[NeurIPS18], and a polynomial time algorithm for NSW objective for k=2 groups. We also give approximation algorithms for k>2. Our technical contribution in the above results is to prove new low-rank properties of extreme point solutions to semi-definite programs. We conclude with the results of several experiments indicating improved performance and generalized application of our algorithm on real-world datasets.