  Counterfactual explanations have substantially increased in popularity in the
past few years as a useful human-centric way of understanding individual
black-box model predictions. While several properties desired of high-quality
counterfactuals have been identified in the literature, three crucial concerns:
the speed of explanation generation, robustness/sensitivity and succinctness of
explanations (sparsity) have been relatively unexplored. In this paper, we
present FASTER-CE: a novel set of algorithms to generate fast, sparse, and
robust counterfactual explanations. The key idea is to efficiently find
promising search directions for counterfactuals in a latent space that is
specified via an autoencoder. These directions are determined based on
gradients with respect to each of the original input features as well as of the
target, as estimated in the latent space. The ability to quickly examine
combinations of the most promising gradient directions as well as to
incorporate additional user-defined constraints allows us to generate multiple
counterfactual explanations that are sparse, realistic, and robust to input
manipulations. Through experiments on three datasets of varied complexities, we
show that FASTER-CE is not only much faster than other state of the art methods
for generating multiple explanations but also is significantly superior when
considering a larger set of desirable (and often conflicting) properties.
Specifically we present results across multiple performance metrics: sparsity,
proximity, validity, speed of generation, and the robustness of explanations,
to highlight the capabilities of the FASTER-CE family.
