Multi-Criteria Dimensionality Reduction with Applications to Fairness
Uthaipon Tantipongpipat · Samira Samadi · Mohit Singh · Jamie Morgenstern · Santosh Vempala

Thu Dec 12th 10:40 -- 10:45 AM @ West Ballroom C

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.

Author Information

Tao (Uthaipon) Tantipongpipat (Georgia Tech)

My research interests include machine learning algorithms, combinatorial optimization, and differential privacy. I am grateful to be advised by Mohit Singh. Our current research has been finding better (randomized and deterministic) polynomial-time approximation algorithms for optimal design problems in statistics. In addition, I am working on differentially privacy on growing databases with Rachel Cummings and Sara Krehbiel. I also work on Fair PCA with Santosh Vempala and Jamie Morgenstern.

Samira Samadi (Georgia Tech)
Mohit Singh (Georgia Tech)
Jamie Morgenstern (University of Washington)
Santosh Vempala (Georgia Tech)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors