Grid Search

Note

Learning tasks: Binary classification, regression.

Introduction

Grid search is a method used to select a deterministic classifier from a set of candidate classifiers obtained from the saddle point of a Lagrangian function. This method is particularly useful when the number of constraints is small, such as in demographic parity or equalized odds with a binary protected attribute. The goal is to find a classifier that balances the tradeoff between accuracy and fairness.

Description

Grid search involves the following steps:

1. Candidate Classifiers: A set of candidate classifiers is obtained from the saddle point \((Q^\dagger, \lambda^\dagger)\). Since \(Q^\dagger\) is a minimizer of \(L(Q, \lambda^\dagger)\) and \(L\) is linear in \(Q\) the distribution \(Q^\dagger\) puts non-zero mass only on classifiers that are the Q-player’s best responses to \(\lambda^\dagger\).

2. Best Response Calculation: If \(\lambda^\dagger\) is known, one can retrieve a best response via a reduction to cost-sensitive learning.

3. Grid Search: When the number of constraints is small, a grid of values for \(\lambda\) is considered. For each value, the best response is calculated, and the value with the desired tradeoff between accuracy and fairness is selected.

Basic Usage

You can find an example of using the Grid Search Reduction method in the following demo.

Read more about the class attributes and methods in the API reference: GridSearchReduction.

References

1. Agarwal, A., Beygelzimer, A., Dudik, M., Langford, J., & Wallach, H. (2018). A reductions approach to fair classification. In Advances in Neural Information Processing Systems (pp. 656-666).