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 \to \{0,1\}\) and instance \(x^\star\), our algorithm makes \[ {S(f)^{O(\Delta_f(x^\star))}\cdot \log d}\] queries to \(f\) and returns {an {\sl optimal}} counte...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-07
Main Authors: Blanc, Guy, Koch, Caleb, Lange, Jane, Li-Yang, Tan
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Lower bounds
Queries
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model \(f : X^d \to \{0,1\}\) and instance \(x^\star\), our algorithm makes \[ {S(f)^{O(\Delta_f(x^\star))}\cdot \log d}\] queries to \(f\) and returns {an {\sl optimal}} counterfactual for \(x^\star\): a nearest instance \(x'\) to \(x^\star\) for which \(f(x')\ne f(x^\star)\). Here \(S(f)\) is the sensitivity of \(f\), a discrete analogue of the Lipschitz constant, and \(\Delta_f(x^\star)\) is the distance from \(x^\star\) to its nearest counterfactuals. The previous best known query complexity was \(d^{\,O(\Delta_f(x^\star))}\), achievable by brute-force local search. We further prove a lower bound of \(S(f)^{\Omega(\Delta_f(x^\star))} + \Omega(\log d)\) on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.
ISSN:2331-8422