# Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem

arXiv: https://arxiv.org/abs/2102.09704 · HTML: https://mlsanity.com/paper/2102.09704/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 54 references that are in the map.
- First posted on arXiv 19 Feb 2021.

## Builds on (most cited first, 20 of 20)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Algorithmic decision making and the cost of fairness](https://mlsanity.com/paper/1701.08230/) (2017)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [A Convex Framework for Fair Regression](https://mlsanity.com/paper/1706.02409/) (2017)
- [Inherent Tradeoffs in Learning Fair Representations](https://mlsanity.com/paper/1906.08386/) (2019)
- [Fair Regression with Wasserstein Barycenters](https://mlsanity.com/paper/2006.07286/) (2020)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [On the relation between accuracy and fairness in binary classification](https://mlsanity.com/paper/1505.05723/) (2015)
- [Stable and Fair Classification](https://mlsanity.com/paper/1902.07823/) (2019)
- [Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm](https://mlsanity.com/paper/1405.2936/) (2014)
- [A General Framework for Fair Regression](https://mlsanity.com/paper/1810.05041/) (2018)

## Built on by (most cited first, 5 of 5)

- [Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation](https://mlsanity.com/paper/2206.01167/) (2022)
- [The price of unfairness in linear bandits with biased feedback](https://mlsanity.com/paper/2203.09784/) (2022)
- [Outlier-robust Estimation of a Sparse Linear Model Using Invexity](https://mlsanity.com/paper/2306.12678/) (2023)
- [Invex Programs: First Order Algorithms and Their Convergence](https://mlsanity.com/paper/2307.04456/) (2023)
- [Deep Learning Evidence for Global Optimality of Gerver's Sofa](https://mlsanity.com/paper/2407.11106/) (2024)

## Abstract (arXiv)

In this paper, we study the problem of fair sparse regression on a biased dataset where bias depends upon a hidden binary attribute. The presence of a hidden attribute adds an extra layer of complexity to the problem by combining sparse regression and clustering with unknown binary labels. The corresponding optimization problem is combinatorial, but we propose a novel relaxation of it as an invex optimization problem. To the best of our knowledge, this is the first invex relaxation for a combinatorial problem. We show that the inclusion of the debiasing/fairness constraint in our model has no adverse effect on the performance. Rather, it enables the recovery of the hidden attribute. The support of our recovered regression parameter vector matches exactly with the true parameter vector. Moreover, we simultaneously solve the clustering problem by recovering the exact value of the hidden attribute for each sample. Our method uses carefully constructed primal dual witnesses to provide theoretical guarantees for the combinatorial problem. To that end, we show that the sample complexity of our method is logarithmic in terms of the dimension of the regression parameter vector.