- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes a method for real-time certification of neural network robustness by computing global robustness bounds offline and using them for efficient online certification. While the basic framework of dividing certification into offline and online stages has already been proposed in prior work, such as VHAGaR, the authors introduce two techniques to improve its practicality. The first is Diff MILP, which directly represents differences in neuron activations to compute tighter upper bounds. The authors also develop two computationally efficient abstractions, 2b+1 and 1b, of Diff MILP. The second is the incorporation of a PCA-based Linear AutoEncoder (LAE) into neural networks to reduce global robustness bounds. The effectiveness of these methods is supported by numerical experiments.
Critical strengths
- Diff MILP achieves tighter upper bounds than conventional MILP encodings. The proposed 2b+1 and 1b models also provide useful trade-offs between computational efficiency and bound tightness.
- LAE substantially reduces the global robustness bounds.
Critical weaknesses
- Table 3 shows that introducing LAE can substantially increase the relative gap between the upper and lower bounds, as the lower bounds decrease much more dramatically than the upper bounds. In particular, for LAE-CIFAR10-Conv, the lower bound is 0.0015, whereas the upper bound remains 0.99 even after 60 hours of computation. The reason for this extremely large gap is not adequately explained.
- The paper does not sufficiently explain why PCA-based dimensionality reduction improves the robustness bounds. In particular, it remains unclear whether the improvement is specific to the subspace selected by PCA or simply results from dimensionality reduction itself.
- Although Table 4 reports certification rates, it does not provide certified accuracy or classification accuracy on certified inputs. Thus, it is difficult to evaluate the relationship between classification correctness and robustness certification.
Questions for authors
- What causes the extremely large gap between the lower and upper bounds for LAE-CIFAR10-Conv in Table 3? Is this due to a genuinely small worst-case sensitivity, or to difficulty finding good feasible solutions or obtaining tight relaxations in the MILP solver?
- Is the reduction in robustness bounds due to properties of the subspace selected by PCA, rather than dimensionality reduction alone? Could the authors investigate this by comparing PCA with random projections at comparable classification accuracy?
- Could the authors report certified accuracy in Table 4, as well as classification accuracy separately for certified and uncertified inputs, to better evaluate the practical significance of robustness certification?
4 comments
Thank you for the clarifications. In particular, I find the results that PCA plays a role beyond simple dimensional reduction quite valuable. While I will reserve my judgment on the additional experiments discussed with the 2nd Reviewer, I am generally satisfied with the authors' responses and think I will keep my original score for now.
Thanks a lot for your answers.
Concerning Reviewer MLsQ, we understand he had a lots of doubts concerning:
-application to perturbations: we did additional experiments showing that our results extends to perturbations.
-is LEA-DNN really necessary, which he is no more claiming. We also provided additional experiments there to provide hard numbers.
-different verifiers based on DiffPoly could be more efficient, and we did additional expriments showing that it was not the case on the networks we considered.
-computational overhead of LEA-DNN. We explained there is none, using the result already in the paper. The reviewer is not claiming that anymore.
new PDF has been uploaded
Notice that we did update the pdf. We added a full new page with 3 tables on page 9/10:
-Table 4 is the table with the different accuracy and attack success rate of the different DNNs.
-Table 6 is a comparison with SaBRe/ DiffPoly of our global bound on .
-Table 7 is the real time certification with perturbations.
This confirms the results in the original version, and answers the doubts by 2sd reviewer MLsQ
We would like to thank the reviewer for the constructive review. We are providing answers now, and we will edit the pdf within the next day.
Q1
From our experiments, finding feasible solutions for LAE-CIFAR10-Conv seems very hard. This makes lower bound particularly pessimistic. This explains the large gap between lower- and upper-bound. However, lower bounds are only indicative, and what is crucial for real-time certification is upper bound, which looks reasonable and sufficient for our aim.
Q2
Theoretically, dimensionality itself does not explain why the bounds are better. Any space allowing the 2 images of a feasible solution reaching the lower bound (e.g. figure 1 left) would result in the high lower bound reported. Low dimension (=2) suffices for that.
In practice, we tried to run random projections at same dimension number as asked by the reviewer. However, the accuracy becomes unsurprisingly very bad (less than 10%), because no reasonable in-distribution image can be built, so the resulting LAE-DNN is useless (a random guess on the class provides 10% accuracy). The bounds computed were actually small, which we believe makes sense as the network is probably not sensitive to the particular directions that were randomly drawn. We believe there are 3 kinds of dimensions:
-In-distribution dimensions (crucial for accuracy, which are recovered by learning directions from the in-distribution dataset as we do), on which the network is normally sensitive.
-Out of distribution directions on which the network is not sensitive (the ones that were randomly drawn in our tests, likely most common).
-Out of distribution directions on which the network is overly sensitive and create very high (lower) bound. This set is likely very sparse. This is in line with what we know on adversarial robustness which cannot be solved by random sampling, because only very particular directions are sensitive. These directions are the ones which are crucial to project away for the bound to be reasonable. However, it is not easy to discover all such directions.
The way we build LAE-DNNs (computing directions from the in-distribution samples) allows to keep the meaningful in-distribution directions which ensures accuracy, and all other directions are projected way, including the important overly sensitive directions. We do not see how to select all the overly sensitive out of distribution direction to only remove them directly in another way.
Q3
We report a new table here. We will edit the pdf in the forthcoming days to add the table to the pdf.