Santosh Vempala, Georgia Institute of Technology

Abstract

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. We study 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 and the Nash Social Welfare (NSW) problem. In the Fair PCA problem, 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-dimensional 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 polynomial-time algorithms for Fair PCA and NSW for k=2 groups. We also give approximation algorithms for k>2 (and show the problem is NP-hard for general k, even for d=1). These results are based on new low-rank properties of extreme point solutions to semi-definite programs, and a generalization of iterative rounding for semidefinite programs, which appear to be of independent interest. 

This is joint work with Samira Samadi, Uthaipon Tantipongpipat, Jamie Morgenstern and Mohit Singh.

Video