Many times, working with data starts with writing code to build a model from the features x to the response y. Answering questions about the data can require understanding what parts of the features x influence the response y. We show that using the KL-divergence within a randomization test discovers important features, while allowing for the reuse of model code. We call this method AMI-CRT. AMI-CRT requires running models for each randomization. We develop a faster variant called FAST-AMI-CRT, and show it is robust to errors in the randomization. Questions of feature importance can also be asked at the level of an individual sample. We provide an example to show that optimal predictive models are insufficient for instance-wise feature selection. We show that the estimators from FAST-AMI-CRT can also be reused to find important features in a particular instance. We evaluate our method on several simulation experiments, on a genomic dataset, a clinical dataset for hospital readmission, and on a subset of classes in ImageNet. Our methods outperform several baselines in various simulated datasets, identifies biologically significant genes, selects the most important predictors of a hospital readmission event, and identifies distinguishing image regions in an image-classification task.
# Paper summary
This paper addresses supervised feature selection: given a D-dimensional input variable x = (x_1, ..., x_D), and a response variable y, the goal is to find a subset of "useful" features in x. Here, a feature x_j is useful if it is dependent on y even when conditioning on all other input variables (denoted by x_{-j}, which is a set). A generic procedure that can produce a p-value for each feature (allowing on to test each feature whether it is useful) is the conditional randomization test (CRT) proposed in Candes et al., 2018.  For the CRT to produce a valid p-value for each feature (input dimension) x_j, one needs to specify a test statistic that measures conditional dependence between x_j and y given the rest of the features.
This paper contributes the following results:
1. Propose using an estimate of the f-divergence for the conditional dependence measure and use it with the CRT (section 2.2).  
2. Measuring the conditional dependence with an f-divergence requires estimating a few conditional density functions. The paper considers the KL divergence as a special of f-divergence. This particular choice turns out the reduce the number of conditional density functions that have to be estimated (section 2.3). The paper also shows that the resulting conditional measure coincides with what is known as the Additional Mutual Information (AMI) studied in Ranganath & Perotte, 2018.  
3. The paper also studies instance-wise feature selection i.e., selecting a subset of input features which can explain the response specifically for one instance (example) x.  Yoon et al., 2019 proposed a criterion to decide the importance of a feature for instance-wise feature selection (definition 2). Briefly, a feature x_j is deemed important if q(y | full x) > q(y | x without the jth feature), where q is the conditional density function of y given x. _Contribution_: The paper notes that this criterion may fail and derive sufficient conditions (Definition 3) under which this approach will always work.  
In simulation on toy problems, the paper shows that the proposed method (KL divergence + CRT) has the highest mean under the ROC curve (Table 2), compared to competing methods. In real problems on images, the paper shows that the proposed instance-wise feature selection can be used to select relevant image patches (features) that explain the class of the input images. The paper also conducts experiments on hospital readmission data (Section 4.3), and genomics data (Section 4.2).
# Review
The paper is overall well written with some parts that can be improved (details below). Introduction and related work in section 1 are easy to follow. The paper is also mostly self-contained and friendly to non-specialists who may not work on feature selection primarily. My concerns are
1. I find that the amount of contribution is not sufficient. CRT is known from Candes et al., 2018. The present paper proposes using KL-divergence with it. This can be interesting if the combination gives some clear advantages.  Unfortunately I do not find that this is the case. It turns out that one still needs to learn two conditional density functions (see lines 3-4 in Algorithm 1). Further and even more concerning, one has to refit another conditional density function *for each draw from the null distribution* (see "Fit regression" in the loop in Algorithm 1). As an intermediate step for solving the original feature selection problem, I find that learning conditional density functions is a much more difficult problem. All these limit the novelty of the idea. While the title of the paper contains "model-agnostic", the idea of fitting conditional density functions seems to contradict it. The paper could have considered some nonparametric conditional dependence measures but did not. For instance, see 
Kernel-based Conditional Independence Test and Application in Causal Discovery
Kun Zhang, Jonas Peters, Dominik Janzing, Bernhard Schoelkopf
2012
and other papers that extend this paper.
Why was the approach of fitting conditional density functions chosen?
2. Related to the previous point, refitting a conditional density model for each draw from the null distribution must be very costly computationally. This point is never addressed in the paper.
3. Lemma 1 states that the expected f-divergence is a "proper statistic" (in the sense of Definition 1) i.e., p-value is uniformly distributed if the feature is not useful, and vanishes (asymptotically) if the feature is useful. This result unfortunately relies on a strong assumption that there is a consistent estimator for the f-divergence. In fact, the proof does not even rely on the fact that it is an f-divergence. It can be any divergence D(p,q) such that D(p,q) > 0 if  p!=q and D(p,p) = 0. In the proof in section C.2 in the appendix, existence of the quantile function $(F^{-1}_N)$ is never discussed. I can see the first part of the proof (under the alternative H1). But I do not see the second part (under H0). Since $\hat{f}$ is a consistent estimator by assumption, as N goes to infinity, the two quantities in the indicator function (in expectation) should both go to the same constant. Isn't this the case? 
4. As a contribution, the paper states a sufficient condition in Definition 3 under which instance-wise feature selection with the approach in Definition 2 is *always* possible. When does the condition hold in practice? How do we know if it holds or not? If it does not, what can go wrong?
5. Toy experiments: What is D in Xor and Orange? Where is the "selector" problem in Table 2? In table 2, "lime" and "shap" also seem to perform well. The paper never explains why the proposed approach is better than other methods (only reporting higher mean are under the ROC curve). This should be possible for toy problems.
# Minor but does affect the evaluation
* Paragraph after Lemma 1: it is unclear why those conditional distributions are required instead of conditional distributions in Eq. 3.
* Section E.1 (appendix), page 16: I think you should have $N( 0.5x_1 + 0.5x_2, \sigma^2_\epsilon)$ instead of 
$0.5N(x_1, \sigma^2_\epsilon) + 0.5N(x_2, \sigma^2_\epsilon)$.
# Things that can be improved. Did not affect the score.
* Section 1.1: the sentence about permutation tests is vague.
* Page 2, our contributions: "necessary" should be "sufficient"?
* Section 2, conditional randomization tests: This paragraph is unfortunately not well written even though it is a very important prerequisite of this work. For instance, at " ... replaced by samples of $\tilde{x}_j^{(i)}$ that is conditionally independent of the outcome...", at that point, it is unclear "conditioning on what". Following this sentence, one approach might be to replace $\tilde{x}_j^{(i)}$ with a constant (which is independent of everything else). It is not until definition 1 that this becomes clearer. Also, the "null hypothesis" (which is in the first line of equation 2) is never stated throughout the paper.
* Eq 1: that (i) is unclear. Should state that for i=1,...,N.
* Eq 2: rewrite the second line. The left hand side states that the p-value "converges in distribution to". The second line should be just 0.
* After eq.6, how to choose T (the number of bins) in practice?
* Definition 3 is actually a proposition? It is unclear what is being defined there.
* The word "complete conditional knockoffs (CCKs)" appears for the first time in Section 3.2 without any explanation.
* Orange skin on page 8: what is "~ exp(...)"? An exponential distribution, or just exponential function?