A query-optimal algorithm for finding counterfactuals

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 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. Theorem 2. Given queries to a monotone model f : X d → 0, 1 with sensitivity S(f ) and an instance x ⋆ , our algorithm makes queries to f and w.h.p. returns the collection C f (x ⋆ ) = ∆(x ⋆ , x ′ ) : x ′ is an optimal counterfactual for x ⋆ . Theorems 1 and 2 give the first algorithms with query complexity that evades the curse of dimensionality, and indeed, strongly so. We contrast our query complexity to that of ball search, a simple and natural algorithm for finding counterfactuals: first query f on x ⋆ and all instances that differ from x ⋆ by a single feature. (By the monotonicity of f , for any feature, it suffices to query f on the instance that differs maximally from x ⋆ on that feature.) Next, query f on the instances that differ by two features, and so on, until a counterfactual is found. This algorithm has query complexity d O(∆ f (x ⋆ )) , an exponentially worse dependence on d than ours. Prior to our work, this was the best known query complexity even just to return a single optimal counterfactual.