Multi-Criteria Dimensionality Reduction with Applications to Fairness
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 our novel Fair-PCA problem and the Nash Social Welfare (NSW) problem. In Fair-PCA, 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 minimum variance of any one group is maximized. In NSW, the goal is to maximize the product of the individual variances of the groups achieved by the common low-dimensional space. Our main result is an exact polynomial-time algorithm for the two-criterion 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 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 experiments indicating the effectiveness of algorithms based on extreme point solutions of semi-definite programs on several real-world data sets.
Code (2)
Tasks
Dimensionality ReductionFairnessSimilar Papers 제목 키워드 기반
Dimensionality reduction: theoretical perspective on practical measures
Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular, metric dimensionality reduction where data from a general metric is mapped into low dimens…
BIG-bench Machine LearningDimensionality ReductionMathAn Item-Based Collaborative Filtering using Dimensionality Reduction Techniques on Mahout Framework
Collaborative Filtering is the most widely used prediction technique in Recommendation System. Most of the current CF recommender systems maintains single criteria user rating in user item matrix. However, recent studies…
Collaborative FilteringDimensionality ReductionPredictionRecommendation SystemsConvex Formulations for Fair Principal Component Analysis
Though there is a growing body of literature on fairness for supervised learning, the problem of incorporating fairness into unsupervised learning has been less well-studied. This paper studies fairness in the context of…
ClusteringDimensionality ReductionFairnessDistributionally Robust Fair Principal Components via Geodesic Descents
Principal component analysis is a simple yet useful dimensionality reduction technique in modern machine learning pipelines. In consequential domains such as college admission, healthcare and credit approval, it is imper…
Dimensionality ReductionFairnessPushing the limits of fairness impossibility: Who's the fairest of them all?
The impossibility theorem of fairness is a foundational result in the algorithmic fairness literature. It states that outside of special cases, one cannot exactly and simultaneously satisfy all three common and intuitive…
AllFairnessModel Selection