Introduction
In the realm of fair machine learning, most algorithms rely on the availability of sensitive attributes—such as race, gender, or age—to mitigate bias. However, real-world datasets often lack these labels due to privacy concerns, legal restrictions, or simple omission. When a hidden binary attribute $z$ influences the outcome, the standard linear model becomes $y = Xw^* + \gamma z^* + e$. Ignoring this hidden bias leads to inaccurate predictions and models that perpetuate systemic discrimination.
The Combinatorial Challenge
Addressing hidden bias requires solving two problems simultaneously: sparse regression to find the feature weights $w$, and clustering to assign each sample to a biased group $z \in \{-1, 1\}$. This joint optimization is a combinatorial problem that is NP-hard. Traditional methods like LASSO fail because they treat the bias term as noise, leading to biased coefficients that do not reflect the true underlying relationships in the data.
Methods: The Invex Fair LASSO
To overcome this, Barik and Honorio (2021) propose the Invex Fair LASSO. Their methodology involves a three-step relaxation process to turn a discrete, impossible problem into a tractable one:
- Combinatorial Formulation: Defining the ideal objective function that minimizes prediction error while accounting for group-based bias.
- Continuous Relaxation: Mapping discrete group labels into a continuous matrix space ($Z$).
- Invex Relaxation: The critical innovation. While the resulting problem is non-convex, the authors prove it is invex.
Why Invexity Matters
Invexity is a powerful generalization of convexity. In an invex function, every stationary point (where the gradient is zero) is guaranteed to be a global minimum. This property allows the use of efficient optimization algorithms, such as alternating minimization, to reach the global optimum despite a non-convex landscape. This ensures that the model reliably finds the best possible weights and group assignments without getting stuck in local optima.
Theoretical Guarantees
The authors utilize a Primal-Dual Witness construction to provide rigorous theoretical support for their method. They demonstrate that the Invex Fair LASSO achieves exact recovery of both the hidden attributes and the regression support (the set of non-zero features) given a sufficient sample size.
Specifically, the sample complexity is $O(s^3 \log d)$, where $s$ is the number of active features and $d$ is the total dimensionality. The logarithmic dependence on $d$ makes the approach highly scalable for high-dimensional "big data" applications where the number of potential features far exceeds the number of samples.
Empirical Results
The Invex Fair LASSO was evaluated across synthetic and real-world benchmarks:
- Synthetic Data: The model achieved 100% accuracy in recovering hidden group labels once the sample size crossed the theoretical threshold.
- Communities and Crime: Predicting violent crime rates, the model identified hidden subgroups related to housing and education, achieving an MSE of 0.0265—comparable to state-of-the-art methods that require known labels.
- Student Performance: The algorithm successfully isolated performance biases linked to school environment and past academic failures in a Portuguese language course.
Key Insights
A major takeaway of this research is that fairness acts as an enabler. Rather than a constraint that degrades performance (the typical fairness-accuracy trade-off), the fairness objective helps the model uncover the true underlying structure of the data. By discovering biased groups during the learning process, the regression weights are corrected for hidden shifts, leading to more robust and accurate predictions.
Limitations and Future Directions
While powerful, the current framework is limited to binary hidden attributes. Future work could extend this to multi-group or intersectional bias. Additionally, while the model is robust to estimates of the bias parameter $\gamma$, automating the learning of $\gamma$ remains an open challenge. Finally, memory efficiency for the matrix-based relaxation is a consideration for extremely large datasets as the sample size $n$ grows.
Reference: Barik, A., & Honorio, J. (2021). Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem. arXiv:2102.09704v2.
Summary updated