Fast Stealthily Biased Sampling Using Sliced Wasserstein Distance

Yudai Yamamoto, Satoshi HaraACML Conference Track 2024 · OpenReview

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

Abstract

Ensuring fairness is essential when implementing machine learning models in practical applications. However, recent research has revealed that benchmark datasets can be crafted as fake evidence of fairness from unfair models using a method called Stealthily Biased Sampling (SBS). SBS minimizes the Wasserstein distance to manipulate a fake benchmark so that the distribution of the benchmark closely resembles the true data distribution. This optimization requires superquadratic time relative to the dataset size, making SBS applicable only to small-sized datasets. In this study, we reveal for the first time that the risk of manipulated benchmark datasets exists even for large-sized datasets. This finding indicates the necessity of considering the potential for manipulated benchmarks regardless of their size. To demonstrate this risk, we developed FastSBS, a computationally efficient variant of SBS using the Sliced Wasserstein distance. FastSBS is optimized by a stochastic gradient-based method, which requires only nearly linear time for each update. In experiments with both synthetic and real-world datasets, we show that FastSBS is an order of magnitude faster than the original SBS for large datasets while maintaining the quality of the manipulated benchmark.
BibTeX
@inproceedings{yamamoto2024fast,
  author = {Yudai Yamamoto and Satoshi Hara},
  title = {{Fast Stealthily Biased Sampling Using Sliced Wasserstein Distance}},
  booktitle = {ACML Conference Track},
  year = {2024},
  url = {https://openreview.net/forum?id=0ymcR0F1wP},
}
Figure