A Query-Optimal Algorithm for Finding Counterfactuals

Abstract

We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model f : X^d \0,1\ and instance x^, our algorithm makes \[ S(f)^O( _f(x^ )) d\] queries to f and returns an optimal counterfactual for x^: a nearest instance x' to x^ for which f(x') f(x^). Here S(f) is the sensitivity of f, a discrete analogue of the Lipschitz constant, and _f(x^) is the distance from x^ to its nearest counterfactuals. The previous best known query complexity was d^\,O(_f(x^)), achievable by brute-force local search. We further prove a lower bound of S(f)^(_f(x^)) + ( d) on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.

Tasks

Reproductions