TL;DR
This paper introduces FastSBS, a significantly faster method for creating "fake" fair benchmark datasets that mimic real data distributions. This addresses the critical issue that existing methods for generating these deceptive datasets are too slow for large datasets, potentially masking the risk of manipulated benchmarks in real-world applications.
What Problem Does This Paper Address?
Ensuring fairness in machine learning is crucial, but a concerning vulnerability has emerged: "Stealthily Biased Sampling" (SBS). SBS can be used to create benchmark datasets that appear fair, even if the underlying model is unfair. This is achieved by minimizing the Wasserstein distance between the original data and the generated benchmark, making them nearly indistinguishable. The catch? The original SBS method is computationally very expensive (superquadratic time complexity), limiting its practical use to small datasets. This paper highlights that this risk isn't confined to small datasets and introduces a solution that works for large-scale data.
Methods
The core innovation is FastSBS, which replaces the computationally intensive Wasserstein distance in the original SBS with the Sliced Wasserstein distance. This allows the optimization to be performed using a stochastic gradient-based method. This approach dramatically reduces the time complexity per update to nearly linear (O(N)), making it scalable to large datasets. The paper also introduces a heuristic for accelerating FastSBS by pre-sampling projection vectors, further reducing computational overhead without sacrificing performance.
Datasets
The paper evaluates FastSBS on:
- Synthetic datasets: A custom-generated dataset to control specific fairness properties.
- Real-world datasets:
- COMPAS: A dataset commonly used in fairness research, related to recidivism prediction.
- Adult: A dataset containing demographic and economic information, often used for predicting income.
Key Insights and Ideas
- The threat of manipulated benchmarks is real, even for large datasets: This is a crucial finding that expands the scope of concern beyond small-scale research.
- Sliced Wasserstein distance is a viable, faster alternative: It offers a computationally tractable way to approximate the Wasserstein distance for this specific optimization problem.
- Stochastic gradient descent is key to scalability: Moving from an exact optimization to a gradient-based approach unlocks the ability to handle large datasets.
- Heuristics can bridge the gap between theory and practice: The fixed slicing approach demonstrates how practical considerations can significantly improve efficiency without compromising results.
Key Results
- Speedup: FastSBS is shown to be an order of magnitude faster than the original SBS on large datasets. For instance, on a synthetic dataset of 10,000 instances, FastSBS achieved a runtime that was significantly lower than SBS, especially as dataset size increased.
- Performance Maintenance: Despite the speedup, FastSBS maintains the quality of the manipulated benchmark. Experiments showed that FastSBS-generated benchmarks achieved comparable fairness metrics (low Demographic Parity) and distribution similarity (low rejection ratios in statistical tests, small Wasserstein distances) to those generated by SBS.
- Parameter Sensitivity: The paper suggests that the choice of certain hyperparameters (like the stopping threshold $\epsilon$ and the number of fixed slices $S$) has a limited impact on the quality of the generated benchmark, making FastSBS robust in practice.
Limitations and Future Work
- Heuristic Nature of Fixed Slicing: While effective, the fixed slicing approach is a heuristic. The paper acknowledges that theoretically, independent random sampling of projections in each iteration is ideal for stochastic optimization. Future work could explore more theoretically grounded ways to achieve similar speedups.
- Further Exploration of Parameters: While the paper shows limited sensitivity to $\epsilon$ and $S$, further investigation into optimal parameter choices for various scenarios could be beneficial.
- Broader Applicability: The paper focuses on Demographic Parity as the fairness metric. Extending FastSBS to other fairness criteria and exploring its effectiveness in more complex real-world scenarios would be valuable.
Summary updated