Provably efficient, succinct, and precise explanations

We consider the problem of explaining the predictions of an arbitrary blackbox model f : given query access to f and an instance x, output a small set of x's features that in conjunction essentially determines f (x). We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient. We obtain our algorithm via a connection to the problem of implicitly learning decision trees. The implicit nature of this learning task allows for efficient algorithms even when the complexity of f necessitates an intractably large surrogate decision tree. We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory. Our approach of "explaining by implicit learning" shares elements of two previously disparate methods for post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both. * Alphabetical order. 35th Conference on Neural Information Processing Systems (NeurIPS 2021).