Saliency methods help to make deep neural network predictions more interpretable by identifying particular features, such as pixels in an image, that contribute most strongly to the network's prediction. Unfortunately, recent evidence suggests that many saliency methods perform poorly when gradients are saturated or in the presence of strong inter-feature dependence or noise injected by an adversarial attack. In this work, we propose a data-driven technique that uses the distributionpreserving decoys to infer robust saliency scores in conjunction with a pre-trained convolutional neural network classifier and any off-the-shelf saliency method. We formulate the generation of decoys as an optimization problem, potentially applicable to any convolutional network architecture. We also propose a novel decoy-enhanced saliency score, which provably compensates for gradient saturation and considers joint activation patterns of pixels in a single-layer convolutional neural network. Empirical results on the ImageNet data set using three different deep neural network architectures-VGGNet, AlexNet and ResNet-show both qualitatively and quantitatively that decoy-enhanced saliency scores outperform raw scores produced by three existing saliency methods.
Given a model and an image, the proposed method generates perturbations of the image, such that the model output in intermediate layers of the network does not change. Their method first generates such perturbed images, and then uses those to generate a saliency map in order to interpret the classification.  The idea is overall interesting, but its relationship with many other methods is not adequately examined. Significant portion of recent literature is ignored, especially studies on counterfactuals and decision boundaries in the context of image classification.  For numerical results, they compare their results with raw scores generated by three other methods, but the results are quite thin and disorganized with respect to adversarial robustness and interpretability.
Your proposed computational method possibly needs to be changed, too.   Details are explained below:  
Authors have cited the paper on "Sanity Checks for Saliency Maps", but have not used it to verify their own results, not with respect to saliency map, and not with respect to computational cost.  Several recent methods on saliency maps have not been considered, for example: 
1. Certifiably robust interpretation in deep learning 
2. Interpreting Neural Networks Using Flip Points 
3. Explaining Image Classifiers by Counterfactual Generation
 4. Counterfactual Visual Explanations 
It's not clear how your proposed saliency scores relate to methods that consider counterfactuals and the decision boundaries. For any image, there is a counterfactual image closest to it. One can also compute the closest image on the decision boundary of the model. Such image can reveal which pixels should be changed in order to change or to keep the classification. The relationship between the current method and those methods needs to be established.
 Assume that for an image, you compute the closest image to it on the decision boundary and let’s call the distance between them r (distance measured in l1 or l2 norm). Then, consider a ball centered at that image with radius r. All images inside that ball would have the same label as the original image and you can obtain all of them only by solving one optimization problem for finding closest point on the decision boundary. Would this be a less expensive computation compared to solving your proposed decoy optimization many times?
There are many hyper parameters in your optimization problem, and it seems that for each image, hyper-parameters should be tuned separately. However, if you seek the closest image on the decision boundary, your results would be independent of hyper-parameters. 
As you have mentioned, your optimization problem seems quite hard to solve, but no details are given on how long it takes to solve it for a single image. You have mentioned sometimes you cannot solve it if c is not chosen well. This information needs to be reported. Is it solvable at all with a large mask? How many trials did it take to obtain your saliency maps?
Your optimization is nonlinear, non-convex, non-differentiable, …. . How did you deal with non-convexity? Do you arrive at the same solution each time you solve it? These are vital information to about an optimization method.
Proposition 1 is quite obvious. Its discussion seems obvious, too, given how you have defined the Z. In your proof, you have considered a single layer network, i.e. a simple linear transformation. It might be better to explain your proof for Proposition 1 as an observation and use it as the motivation on how you have defined Z.
 Overall, you are taking a data-driven approach to interpret the classification of an image. The additional computational cost of your proposed method needs to be compared to other methods that are not data-driven. For example, how does your computational cost compare with the references above?
On page 12, one equation is referenced with ??.
At the beginning of section 3.4, you are using a standard optimization technique to augment a constraint as a penalty in the objective function. You can explain it as such, instead of saying we solve an alternative formulation. See Numerical Optimization by Nocedal and Wright.
The necessity to transform the variable via tanh, instead of performing projection is not explained. Does it make the process faster?
Strategy for choosing a good initial value for c (in the penalty term) and how to increase it is not explained well. How many iterations does it take to find the solution?
Any classification model is defined by its decision boundaries, so interpreting the classification without considering the decision boundaries seems inconclusive.
In summary, it would be best to compare your results with other methods, some of which are mentioned above. It would also be necessary to justify the additional data-driven cost that you are prescribing and to explain why your goals cannot be achieved otherwise with less expensive computation.