Is this the Right Neighborhood? Accurate and Query Efficient Model Agnostic Explanations

There have been multiple works that try to ascertain explanations for decisions of black box models on particular inputs by perturbing the input or by sampling around it, creating a neighborhood and then fitting a sparse (linear) model (e.g.