acceptodds
Under review as a conference paper at ICLR 2027

REAL-TIME Certification of robustness for AE-DNNs with the Diff MILP Model

Abstract

Deep neural networks (DNNs) are often brittle to small perturbations, which has led to extensive research to certify their robustness. Most existing methods focus on _local_ robustness, i.e., in the neighborhood of fixed specific inputs. However, these techniques are often impractical for guaranteeing robustness to _real-time_ inputs on embedded systems, due to excessive latency and computational cost. To tackle real-time certification, we proceed in two steps. First, offline, we solve _global_ robustness problems, which are significantly more complex than local robustness. Namely, we compute _bounds_ on the difference of output values across different DNN decision classes under both - _and_ -perturbations. We then use the results online to perform real-time certification. On vanilla DNNs, however, global bounds are deemed overly pessimistic, because of inputs that are not In Distribution (ID). We propose alternative "AE-DNNs" to vanilla DNNs to use in exploitation, projecting inputs on an AutoEncoder (AE) latent space learnt from ID samples. With a sufficiently large latent space, ID inputs are only changed slightly and (Linear) AE-DNNs accuracy is close to Vanilla DNNs, with much smaller (3-15x) global bounds than Vanilla DNNs. To compute these bounds accurately, we develop novel _Diff_ MILP models, explicitly representing the small differential variables between the input and its perturbation, instead of implicitly representing them as differences between 2 larger values (standard MILP encoding). Online, our method certifies in real-time over 70% of incoming images for AE-DNNs used _in exploitation_, across standard benchmarks (MNIST, Fashion MNIST and CIFAR-10), with -perturbations of , respectively, requiring only 0.5 ms of latency on a single CPU core.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Certification in real-time, robustness, global robustness, milp

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_SpAJOpenReview ↗
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
  1. 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.
  2. LAE substantially reduces the global robustness bounds.
Critical weaknesses
  1. 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.
  2. 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.
  3. 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
  1. 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?
  2. 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?
  3. 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

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.

ModelMetricDNNLAE-DNNswitch between DNN and LAE-DNN
MNIST-FCAccuracy98%98%2%
PGD-attackable1%4%5%
FMNIST-ConvAccuracy82%81%5%
PGD-attackable2%1%3%
CIFAR10-ConvAccuracy51%50%1%
PGD-attackable10%1%10%

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 L∞L_{\infty} perturbations: we did additional experiments showing that our results extends to L∞L_{\infty} 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.

AuthorsOpenReview ↗

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 β\beta on L∞L_\infty.

-Table 7 is the real time certification with L∞L_\infty perturbations.

This confirms the results in the original version, and answers the doubts by 2sd reviewer MLsQ

Reviewer_MLsQOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes real-time DNN robustness certification using global robustness bounds computed offline via a Diff MILP formulation. During inference, these bounds are used to certify robustness through simple output comparisons. To obtain tighter bounds, the authors prepend a linear autoencoder (LAE) to the original DNN. Experiments on MNIST, Fashion-MNIST, and CIFAR-10 show improved global bounds and high certification rates for the modified networks.

Critical strengths
  • Leveraging precomputed global robustness bounds for efficient robustness certification during inference is interesting and potentially useful.
Critical weaknesses
  • The main certification improvements rely on prepending an LAE, effectively changing the network being verified. The improved certification guarantees apply only to the modified networks, not the original DNNs. Similar classification accuracy does not imply equivalent predictions or robustness properties. Furthermore, projecting inputs onto a low-dimensional subspace does not necessarily eliminate out-of-distribution behavior, weakening the motivation for LAE-DNNs.

  • MILP scales poorly to large DNNs due to the combinatorial complexity of unstable ReLUs, and the Diff formulation inherits this limitation. LP relaxation avoids the combinatorial search but may yield overly loose bounds, while large LPs remain computationally expensive. Consequently, the global bounds may be too loose for effective online certification, regardless of its low overhead. Scalable abstract interpretation techniques for computing global differential bounds, such as DiffPoly (PLDI 2024), might be a more promising direction.

  • The real-time certification experiments (Table 4) only consider L_1 perturbations, while the L_inf experiments (Table 1) report global bounds. The chosen L_1 budgets exclude many dense perturbations permitted under standard L_inf settings, which raises concerns about the generalizability of the reported results.

Questions for authors
  • Q1: What practical scenarios justify replacing existing DNNs with LAE-DNNs, given that the robustness guarantees do not transfer to the original networks?

  • Q2: How is the global input domain defined and encoded in MILP to ensure sound certification?

12 comments

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:

We are not proposing to use DNN in deployment/exploitation and LAE-DNN when computing the bound. This would not be sound. Instead, we propose that LAE-DNN should also be used in exploitation / deployment (see. e.g. the abstract l.021-030, introduction l.080-086, 110, Section 4 l.236-237, 260), and not only when computing the bounds. We thus do not transfer robustness guarantees from LAE-DNN to the DNN, and we do not need to do it as the DNN is not used, only the LAE-DNN is used.

The reasons to use LAE-DNN (in both bounds and exploitation) are the following:

The original (vanilla) DNNs are not amenable to real-time verification, which we show in our paper (see lower bound in Table 3, and also the Reviewer BZVB comment). So the original DNN cannot be used.

By comparison, LAE-DNNs have similar behavior as the original DNN (accuracy), see table below (which we will add to the pdf in the following day). Crucially, the global upper bounds we obtained are much lower (3x-15x), even lower than the unachievable lower bounds for DNNs, meaning that no algorithm could ever achieve better bounds for the original DNN.

ModelMetricDNNLAE-DNNswitch between DNN and LAE-DNN
MNIST-FCAccuracy98%98%2%
PGD-attackable1%4%5%
FMNIST-ConvAccuracy82%81%5%
PGD-attackable2%1%3%
CIFAR10-ConvAccuracy51%50%1%
PGD-attackable10%1%10%

Q2:

For example, for MNIST: 784 continuous variables (one for each pixel), where each pixel can take any value in [0,1]. This is the "full" (global) input domain, for both LAE-DNN and original DNN. That is, every input is possible for both LAE-DNN and original DNN, and the certification is sound.

Answer to weaknesses not answered above

Projecting inputs onto a low-dimensional subspace does not necessarily eliminate out-of-distribution behavior, weakening the motivation for LAE-DNNs.

Eliminating out-of-distribution behavior is not our motivation. Our motivation is to obtain tighter bounds while maintaining high accuracy. We achieved this consistently across all DNNs considered: as shown in Table 3, the bounds are 3-15x smaller, and accuracy is within 1% of the vanilla DNN (Table 2). Eliminating most out-of-distribution behaviors is the (very successful) means to reach this goal. To do so, LAE-encode projects the input onto an LAE-basis learnt from in-distribution samples, projecting away most out-of-distribution behavior (in particular the ones on which the DNN is very sensitive and create an artificially large bound). Some out-of-distribution behavior can remain possible, which is not a problem per se (as long as the DNN is not overly sensitive over them).

MILP scales poorly ... Scalable abstract interpretation techniques might be a more promising direction.

We agree that for larger DNNs, other (faster but not as accurate) techniques might be useful. This is out of scope of the current paper.

The real-time certification experiments (Table 4) only consider L_1 perturbations, while the L_inf experiments (Table 1) report global bounds. The chosen L_1 budgets exclude many dense perturbations permitted under standard L_inf settings, which raises concerns about the generalizability of the reported results.

L_1 and L_inf are orthogonal perturbations. We believe a L_1 perturbation of 1 is meaningful (it means one pixel can be fully changed freely, with proven attacks adding patch anywhere on the image). We obtained real-time certification up to L_1 perturbation of 4 (4 full pixels can be changed fully, or 8 pixels can be altered considerably (+/- .5), etc). Such alterations cannot be modeled by L_inf perturbations.

Concerning L_inf perturbations, they are computationally easier to handle than L_1 (corrected from L_infty) perturbation (upper and lower bounds are much tighter in Table 1 (L_inf) than in Table 3 (L_1)), so generalizability of our results to L_inf is very likely.

To demonstrate it, we experimented on certifying robustness for L_inf perturbations for LAE-FMNIST-Conv. We obtained the following real-time certification rates for different epsilon:

Epsilon0.010.020.030.040.05
Real-Time Certification Rate88%78%62%52%34%

Hence, we can certify in real-time 78% of images for LAE-FMNIST-Conv for a L_inf perturbation of 0.02 (that is a perturbation of up to 5 levels of grey scale on each pixel).

Reviewer_MLsQOpenReview ↗

Result on abstract interpretation-based global verifier invalidate LAE-DNN contribution

  1. Deploying AE-DNN raises practical concerns. Prepending an autoencoder adds computational overhead in inference time, especially on low-power embedded devices.

  2. I ran a small experiment using the public implementation of VHAGaR and compared it with abstract interpretation-based global robustness verifiers (RaVeN and SaBRe).

Benchmarkε\varepsilonVHAGaRRaVeNSaBRe
MNIST FNN 784×20×10784 \times 20 \times 105×10−45\times10^{-4}42.940.5450.427
1×10−31\times10^{-3}42.431.090.855
5×10−35\times10^{-3}43.775.454.28
1×10−21\times10^{-2}44.6310.908.53
  • In the paper, the proposed MILP models give bounds about 1.5x - 1.9x tighter than VHAGaR (Table 1), and AE-DNN reduces the bound by a further 3x - 15x compared to just DNN (Tab. 3) so totally less than 30x tigher than VHAGaR.
  • My results show that unmentioned abstract interpretation verifiers achieve bounds that are 5x to 100x tighter than VHAGaR
  • Thus, AE-DNN is not better than abstract interpretation verifiers in terms of precision.
  • Abstract interpretation verifiers can verify DNN as is. No additional overhead in inference time.
  1. The proposed real-time local robustness certification is trivial because it is a simple look up from a precomputed global bound.

After completing my due diligence to fully understand this paper and to get additional results to validate my initial hypothesis, I believe this paper provides no meaningful contribution. I respectfully disagree with the other reviewers, and I believe this paper must be rejected.

References:

  • RaVeN: Banerjee et al., "Input-Relational Verification of Deep Neural Networks", PLDI 2024.
  • SaBRe: Fukuda et al., "Branch and Bound for Relational Verification of Neural Networks", EMSOFT 2026 (contemporary work, published Aug. 2026).

Thank you for your answer.

1.

As we explain in the appendix C page 14, the LAE part (which is linear) can be fully fused (offline) into the weights of the first layer of the DNN. There is no architecture change to the original DNN (only weights are changed), and thus 0 online computational overhead for LAE-DNN vs DNN.

2.

As we report in Table 1 in the (gap) column, for L_inf = 5x$10^{-2}$, we reach in the worst case 6% difference between the computed upper bound and a lower bound we found.

For instance, for MNIST-Conv with epsilon=5x 10−210^{-2}, a lower bound is 9.51, our computed upper bound is 10.07, and Vhagar computes an upper bound of17.54. No algorithm can reach 9.51, so no algortihm on this benchmark can get better than 17.54/9.51 = 1.844x improvement over Vhagar. We reached 1.74x improvement.

An improvement of even 2x of Vhagar is simply impossible here, let alone an improvement of 5x, 30x, or 100x as reported by the reviewer. We do not deny other DNNs and other epsilon could display such improvements: As we explained, we chose a best case scenario for Vhagar:

l.355-l360: To be able to compare with VHAGaR, we use their benchmarks: VHAGaR bounds, perturbation L∞ = 5x$10^{-2}$, VHAGaR convolutional DNNs, for which the VHAGaR reduction rules of binary variables are implemented

Thus, AE-DNN is not better than abstract interpretation verifiers in terms of precision.

Transfering improvement factors between 2 different networks and 2 different epsilons is not sound.

We invite this reviewer to use this particular setting if they want to compare directly (same DNN MNIST-Conv1 available from Vhagar, same epsilon= 5x$10^{-2}$ instead of the very small perturbations 10$^{-3}$ (which cannot even change 1 level of grey scale in an image) the reviewer was trying. In the results from the reviewer, Vhagar does not see much improvement when epsilon is reduced. On the other hand, the near linear scaling of Sabre and Raven with epsilon (which is not surprising) would mean a much smaller improvement (<2x) at our tested epsilon = 5x$10^{-2}$.

Abstract interpretation verifiers can verify DNN as is.

It is impossible, see e.g. reviewer BZVB comment:

The tightness gain is architectural, not algorithmic—no verification method could achieve it on the unmodified network.

To spell it out, in Table 3, we found a lower bound for FMNIST-Conv of 4.16. That is, we have 2 inputs within a L_1 perturbation of 1 which display a difference of 4.16 in the difference of the values of 2 outputs neurons. It is thus absolutely impossible, with any tool, existing or not yet invented, even using infinite runtime, to obtain an upper bound < 4.16 on FMNIST-Conv.

On the other hand, using LAE-FMNIST-Conv, we find an upper bound of 1.95, >2x better. This is simply absolutetly impossible to obtain using the original FMNIST-Conv.

The same is true for CIFAR10-Conv: here we get a >>3x improvement by using our algorithm on LAE-CIFAR10-Conv over using any algorithm running infinite runtime over CIFAR10-Conv.

No additional overhead in inference time.

neither do we need it (see 1. above)

3.

That is indeed the whole point to have an extremely trivial online check to be able to reach the real-time constraint of ~1ms overhead in certifying. No non-trivial method would reach it. On the other hand, this puts much more pressure on the offline computation to bring very accurate bounds, which we do thanks both to the LAE-architecture and the Diff MILP model on the considered DNNs and perturbations.

Reviewer_BZVBOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a two-step method for real-time certification of global DNN robustness. First, global bounds on output differences between class pairs are computed offline with an MILP model. Second, each incoming image is certified online by comparing class output gaps against these precomputed bounds. The check needs about 27 CPU instructions, roughly 0.5 ms. The key obstacle is that global bounds on vanilla DNNs are overly pessimistic, because non-distribution inputs cause erratic behavior. The authors show no verification method can fix this problem on unmodified DNNs.

The paper makes two contributions. First, the AE-DNN architecture. A linear autoencoder, trained on in-distribution data, projects inputs onto a small latent subspace before the DNN. This removes non-ID directions that inflate global bounds. Bounds shrink 3–15x with at most 1% accuracy loss. Appendix C proves the projection can be absorbed into the first DNN layer, so no architecture change is needed. Second, the Diff MILP model. It represents input-perturbation differences as explicit variables, giving tighter global bounds than classical encodings.

Experiments cover MNIST, Fashion-MNIST, and CIFAR-10 with four pretrained DNNs and their LAE variants. Bounds are computed with Gurobi on a 32-core Threadripper, with timeouts up to 216000 seconds. LAE-DNNs reach bounds 15x, 3x, and 7x smaller than their vanilla counterparts. Notably, the LAE-CIFAR10 bound (0.99) is below the vanilla CIFAR10 lower bound (3.38), so no method can match LAE bounds on the original network. Real-time certification exceeds 70% of images for L1 perturbations of 1, 4, and 2, at 0.5 ms latency.

Critical strengths

1. A well-posed, provably reframed problem. The paper shows global bounds on vanilla DNNs are irreducibly pessimistic due to non-ID inputs, then proves (Appendix C) a rank-n input projection can be absorbed into the first layer. The tightness gain is architectural, not algorithmic—no verification method could achieve it on the unmodified network.

2. A decisive empirical argument. LAE-CIFAR10's upper bound (0.99) falls below vanilla CIFAR10's lower bound (3.38). This converts a method comparison into an impossibility argument for competing tools on the original network, which is rare and convincing.

3. Real-time practicality with good scoping. The expensive work is fully offline; the online check costs ~27 CPU instructions (0.5 ms, one core), certifying 70%+ of images at up to 4x larger radii, for ≤1% accuracy loss. Authors self-declare concept-and-feasibility scope, keeping claims properly bounded.

Critical weaknesses

1. The certified guarantee is about a different model than the deployed task requires. Bounds are computed on the projected network. Perturbation components orthogonal to the latent subspace are invisible to the network—filtered out, not resisted. The certified perturbation set is silently redefined. The paper never states this trade explicitly.

2. No adaptive attacks against the projected model. Robustness claims on non-ID regions rest only on indirect evidence (bounds, visualizations). No attack success rate is reported for LAE-DNNs. For a paper whose central contribution is an architecture filtering non-ID inputs, adversarial validation of exactly that boundary is the minimum expected evidence.

3. Offline cost is unbounded and unreported. The tightest LAE-CIFAR10 bound required a 60-hour Gurobi timeout; total cost over all 45 class pairs, and re-computation after retraining, are never quantified. Combined with small networks and linear-AE-only experiments, feasibility beyond toy scale remains an assumption, not a finding.

Questions for authors

The bound β̄ is computed on the projected network, so perturbations orthogonal to the rank-n latent subspace leave the output unchanged. In what precise sense is the resulting guarantee a robustness certificate "for the model in deployment"? Please state the certified perturbation set explicitly, and clarify whether a component-wise adversary exploiting exactly these filtered directions is considered in-scope, out-of-scope, or excluded by assumption.

The paper's central claim concerns behavior on non-ID inputs, yet no attack success rate against LAE-DNNs is reported. Did you run any adaptive attack (e.g., PGD or a targeted attack through the projection P, or an attack searching in latent space) on the deployed LAE-DNNs?

Accuracy loss reaches ≤1% only at latent dimension 60 for CIFAR-10, after a plateau of 5–16% at smaller dimensions. Do you have any evidence (even preliminary) on whether the ≤1% budget remains attainable at ImageNet-scale inputs, or does the required latent dimension grow superlinearly with data complexity?

3 comments

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.

In what precise sense is the resulting guarantee a robustness certificate "for the model in deployment"?

The model in deployment is the LAE-DNN itself, not the original DNN. We explicitly state this throughout the paper (see. e.g. the abstract l.021-030, introduction l.080-086, 110, Section 4 l.236-237, 260). As you rightly note, "The paper shows global bounds on vanilla DNNs are irreducibly pessimistic." Thus, to achieve real-time certification, the vanilla DNN cannot be used during deployment. It is the reason why maintaining accuracy for LAE-DNN is crucial, because it is the one being deployed. We provide hereafter a table with the different accuracies and PGD attack rates for L1-perturbation of 1. We will add the table to the pdf in the following days.

ModelMetricDNNLAE-DNNswitch between DNN and LAE-DNN
MNIST-FCAccuracy98%98%2%
PGD-attackable1%4%5%
FMNIST-ConvAccuracy82%81%5%
PGD-attackable2%1%3%
CIFAR10-ConvAccuracy51%50%1%
PGD-attackable10%1%10%

Please state the certified perturbation set explicitly,

The certified perturbation set is any continuous image (with each pixel value continuous in [0,1]), e.g. of size 24*24 for MNIST and FMNIST, that is within epsilon-distance from the real-time input image, for a given norm (in the paper: L_\inf, L_1, or a conjunction of both). This holds for both DNN and LAE-DNN (they consider the exact same input and perturbation).

whether a component-wise adversary exploiting exactly these filtered directions is considered in-scope, out-of-scope, or excluded by assumption.

An adversary can exploit any direction in the input space, so in particular it can use filtered directions. Notice that as the first 2 layers (encode + decode) of AE-DNN project away these components, an adversary would not benefit from doing so, but it is allowed to do it.

The paper's central claim concerns behavior on non-ID inputs, yet no attack success rate against LAE-DNNs is reported. Did you run any adaptive attack (e.g., PGD or a targeted attack through the projection P, or an attack searching in latent space) on the deployed LAE-DNNs?

Our focus is on real-time certification: the global bounds we need cannot restrict to in-distribution inputs. By contrast, (local) robustness considers perturbation to in-distribution inputs only, which are largely unaffected by the LAE-DNN construction. We did report in the table above robustness to PGD attacks: the largest change is on CIFAR10, where most attacks for CIFAR10-Conv are no more allowed in LEA-CIFAR10-Conv, probably because the attack directions are largely projected away by the LAE projection so they have lower impact.

Accuracy loss reaches ≤1% only at latent dimension 60 for CIFAR-10, after a plateau of 5–16% at smaller dimensions. Do you have any evidence (even preliminary) on whether the ≤1% budget remains attainable at ImageNet-scale inputs, or does the required latent dimension grow superlinearly with data complexity?

We have not experimented on DNNs for ImageNet. Notice that dimensionality reduction is not necessarily the main source for lowering the bound, it is removing some non-ID directions, on which the DNN is very sensitive, so even if dimension scales super linearly, it might not be a big issue.

**Critical Weaknesses not addresses above. **

W2:

Our central claim is not that AE-DNNs are inherently more robust on in-distribution data (this seems to be the case only for CIFAR10-Conv), but that they enable smaller global bounds (which it does: 3-15x smaller). Still, we agree with you that the robustness numbers are interesting, and we provided them.

W3:

Constructing the AE-DNN offline takes negligible computation time (<1 second). In addition, as per Table 3, for the longest 60h time out, precomputing the bounds across all 45 (=9x10/2 unordered) pairs of classes requires 120 hours using 23 parallel threads (120h = 2x60h = 2 runs of 60h) on our 32-core CPU. This holds for both Diff MILP and ITNE. Using a 64 cores CPUs or 2 machines would directly halve this runtime. Importantly, this is a one-time cost, since the network is fixed for deployment.

Also, note that using timeout of 4hours instead of 60hours does not significantly lower the bounds. The impact on the real-time certification rate is only a few percentage points: the computational cost can be reduced without much affecting the result. What we suggest is thus using a feasible runtime for the LAE-DNN under consideration and proceeding with the bounds produced.

Thanks for the quick and detailed reply, and for adding the accuracy/PGD table and the cost numbers.

The deployed model is the LAE-DNN, the perturbation set is the same for both, and filtered directions give an adversary nothing. That's the clarification I wanted.

On ImageNet: fair answer, out of scope. Worth a sentence in limitations.

The responses partially addressed my concerns. I will maintain my rating as weak acceptance.

Thanks for your answer.

Worth a sentence in limitations.

We agree, but we believe that it is already taken into account by:

"This is a Concept and Feasibility paper. Our techniques are tested on several DNNs and datasets, but the DNN size is limited (though concrete examples are tackled)."

If you do not agree, we will mention it explicitly.

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 β\beta on L∞L_\infty.

-Table 7 is the real time certification with L∞L_\infty perturbations.

This confirms the results in the original version.

Comments on the paper

1 comment
AuthorsOpenReview ↗

New PDF has been uploaded

Dear AC,

We reviewed and answered carefully the reviewers comments.

In line with that, we did update a new 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 as asked by all 3 reviewers. It shows that LAE-DNNs and DNNs have close caracteristic, except for LAE-CIFAR10-DNN which is sensibly more robust than CIFAR10-DNN (10% less attacks), which is obviously a positive thing.

-Table 6 is a comparison of our methods with SaBRe/ DiffPoly of our global bound β\beta on L∞L_\infty.

It shows that our methods are twice as accurate as SaBRe on the tested DNN, even at 100s runtime.

Also, it shows that our methods is extremely close to the lower bound (4.94 vs 4.85) in 1000s on the tested DNN, so it is impossible to do sensibly better (<2% better), even in the future.

Last, we obtain better bounds (3.19) on LAE-DNN, unachievable on the original DNN (lower bound 4.85).

While this is not as good as for L1L_1 perturbations we obtained in the original submition, this is still a very decisive improvement, both on our models Diff and on our LEA-DNN architecture.

-Table 7 is the real time certification with L∞L_\infty perturbations.

We can certify 78% of images for perturbation of 5 level of grey on LAE-DNN while we can only certify perturbation of 2 levels of grey for the original DNN for a similar percentage of images (84%).

This confirms the results in the original version, and answers the doubts by 2sd reviewer MLsQ

In conclusion: We showed in this paper that we can certify in real-time for meaningful L1L_1 and L∞L_\infty perturbations, and this is the major contribution of our paper.

A last word on reviewer MLsQ: he had many doubts:

  1. SaBRe is more efficient on the DNN considered.

We showed it is not the case.

  1. SaBRe is more accurate on DNN than our method on LAE-DNN

It was already shown in the paper through lower bounds that no algorithm can do that (existing or not yet invented). We did additional experiments to provide hard numbers.

  1. We cannot handle L∞L_\infty:

We showed that we can provide real time certification for meaningful L∞L_\infty perturbations.

  1. computational overhead of LEA-DNN.

We explained there is none, using the result already in the paper.

  1. On much larger DNNs, Diff is likely not going to be the most accurate in practice anymore.

We perfectly agree with that. Our reservation is that on such large DNNs, there is currently no solution that fulfills real time certification with meaningful perturbations. Further, very large DNNs are unlikely to be deployed on embedded hardware, which we target. Last, our LAE-DNN architecture helps, regardless of the algorithm to compute the bound (we showed that it also improves SaBRe results by 2x on L∞L_\infty perturbations).

Scaling the problem to larger DNNs and understanding the feasible limit is certainly worth researching, which is out of scope of this paper. We only bring a seed to this problem, and we do not claim to have solved everything.

We are excited to contribute to show that real-time certification is possible and to push other researchers to consider studying the topic.

We notice that despite answering every single doubt in lenght, this reviewer is stuck on his first impression. We cannot find scientific justification for this behavior. We hope that the AC can take this into consideration to take the final decision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.