A Query-Optimal Algorithm for Finding Counterfactuals

07/14/2022
by   Guy Blanc, et al.
0

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^⋆))·log 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^⋆)) + Ω(log d) on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset