  Given the black box nature of machine learning models, a plethora of
explainability methods have been developed to decipher the factors behind
individual decisions. In this paper, we introduce a novel problem of black box
(probabilistic) explanation certification. We ask the question: Given a black
box model with only query access, an explanation for an example and a quality
metric (viz. fidelity, stability), can we find the largest hypercube (i.e.,
$\ell_{\infty}$ ball) centered at the example such that when the explanation is
applied to all examples within the hypercube, (with high probability) a quality
criterion is met (viz. fidelity greater than some value)? Being able to
efficiently find such a \emph{trust region} has multiple benefits: i) insight
into model behavior in a \emph{region}, with a \emph{guarantee}; ii)
ascertained \emph{stability} of the explanation; iii) \emph{explanation reuse},
which can save time, energy and money by not having to find explanations for
every example; and iv) a possible \emph{meta-metric} to compare explanation
methods. Our contributions include formalizing this problem, proposing
solutions, providing theoretical guarantees for these solutions that are
computable, and experimentally showing their efficacy on synthetic and real
data.
