Timezone: »

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

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #80
in Applications -- Fairness, Accountability, and Transparency »

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.

Keywords: Components Analysis (e.g., CCA, ICA, LDA, PCA) · Algorithms · Applications -> Fairness, Accountability, and Transparency; Optimization -> Convex Optimization; Theory · Computational Comple

Author Information

Uthaipon Tantipongpipat (Georgia Tech)

Graduating PhD student in machine learning theory and optimization. Strong background in mathematics and algorithmic foundations of data science with hands-on implementations on real-world datasets. Strive for impact and efficiency while attentive to details. Enjoy public speaking and experienced in leading research projects. Published many theoretical results in academic conferences and developed several optimized algorithms for public use. My research includes • Approximation algorithms in optimal design in statistics, as known as design of experiments (DoE) using combinatorial optimization. Diversity or representative sampling. • Differential privacy – theory of privacy in growing database; its deployment in deep learning models such as RNNs, LSTMs, autoencoders, and GANs; and its application in private synthetic data generation. • Fairness in machine learning – fair principle component analysis (fair PCA) using convex optimization and randomized rounding to obtain low-rank solution to semi-definite programming Other Interests: model compressions; privacy and security in machine learning; fair and explainable/interpretable machine learning

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