Title: Fair Dimensionality Reduction and Low Rank Semi-definite Programs
Presented By: Mohit Singh, Georgia Institute of Technology

Abstract:
Dimensionality reduction is a standard task in classic as well as modern data analysis. A standard method for dimensionreduction deployed widely is Principal Component Analysis (PCA), which minimizes the average reconstruction error. Unfortunately, when data belongs to different groups, say images of men and women, the average error on the two groups can be significantly different. To alleviate this unfairness, we formulate the fair dimensionality reduction problem that aims to reduce the dimensionality of the data while maintaining fairness across different groups. We give polynomial time algorithm for 2 groups and approximation algorithm for multiple groups. These results rely on low rank properties of extreme points of semi-definite programs extending the classic results of Pataki and Barvinok. We also show the effectiveness of our algorithms on several real-world datasets as well as its computational efficiency.

This is joint work with Jamie Morgernstern, Samira Samadi, Santosh Vempala and Tao Tantipongpipat.