AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness

We appreciate the reviewer's thoughtful comments and questions. We'll address each point in turn:

1. Practical settings and adversarial examples

We acknowledge that certified radii, including those in our work, may not always encompass all practical attacks. However, our approach significantly expands the certified region compared to previous methods, particularly for longer sequences. This improvement is crucial as it narrows the gap between theoretical guarantees and practical attack scenarios.

It's important to note that the edit distance threat model, while not perfect, represents a significant advancement over previous work that only accommodates substitutions (Hamming distance). This allows us to certify robustness against a broader range of perturbations, including insertions and deletions, which are particularly relevant for text data [GR20, LZP+21].

We also emphasize that certification isn't solely about defending against adversarial attacks. It's equally important for ensuring model stability under benign noise, which is common in real-world applications. Our method provides strong guarantees for this broader notion of robustness.

Missing explanation for robustness-accuracy trade-off

We appreciate the opportunity to clarify this point. Looking at Table 4, we'd argue that the clean accuracy of AdaptDel and AdaptDel+ is generally on par with CERT-ED, with only slight drops (less than 1-2 percentage points) which may not be statistically significant.

The slight variations in clean accuracy could be attributed to several factors:

• Convergence of training/calibration under variable-rate deletion

• The base model's ability to handle variable-rate deletion

• More aggressive deletion for medium to long sequences potentially affecting their accuracy

We believe these small trade-offs in clean accuracy are well justified by the significant improvements in certified robustness, particularly for longer sequences. That said, we agree that further improving clean accuracy is desirable. This could potentially be achieved by manually adjusting the deletion rate curve for AdaptDel, or adjusting the certified accuracy threshold $\tau$ for AdaptDel+.

References

• Garg, S., and G. Ramakrishnan. “BAE: BERT-based adversarial examples for text classification.” In: EMNLP 2020.

• Li, D., Y. Zhang, H. Peng, L. Chen, C. Brockett, M. Sun, and B. Dolan. “Contextualized perturbation for textual adversarial attack.” In: NACL 2021.

Thank you for your thoughtful review and insightful questions. We appreciate your recognition of our work's motivation and theoretical soundness.

The operations o contains three elements del, ins, sub, but section directly jump to del only, can you briefly explain why the other two operations are dropped?

Thank you for highlighting this point. We originally included a more explicit explanation of this distinction, but it was cut due to space constraints. To clarify: the edit operations in Section 2 define the edit distance we certify, which in our experiments includes all three operations (Levenshtein distance). Our smoothing mechanism, however, uses only deletion. This decoupling of certification and smoothing operations is a key feature of our approach, allowing us to certify robustness against a broader set of edit operations while using a simpler smoothing mechanism. We will reinstate a more explicit discussion of this in the final version to prevent any misunderstanding.

For line 143, how can you make $\mathrm{apply}(\bar{x}, \bar{\epsilon}) = \mathrm{apply} (\bar{x}, \epsilon^\star)$? Is there a typo? Do you mean $\mathrm{apply}(\bar{x}, \bar{\epsilon}) = \mathrm{apply} (x, \epsilon^\star)$?

Thank you for catching this typo. The correct equation should be $\mathrm{apply}(\bar{\mathbf{x}}, \bar{\epsilon}) = \mathrm{apply} (\mathbf{x}, \epsilon)$.

Can you explain how you define $\rho$ intuitively? Also it is not trivial to see the equivalence of lemma 3.1 from lemma4 from [1], can you elaborate a bit?

We define $\rho(\psi, \bar{\psi})$ purely to make the math more concise. It's a product of ratios of deletion and retention probabilities (line 145), simplifying to 1 when the deletion probability is constant ($\psi = \bar{\psi}$).

Regarding Lemma 3.1, the key differences from Lemma 4 in [1] are:

• We represent deletion edits as Boolean vectors aligned with $\mathbf{x}$, whereas [1] uses sets of indices into $\mathbf{x}$ that are retained (i.e., not deleted).

• We use $\mathcal{E}(\mathbf{x}, \mathbf{\epsilon}^\star)$ to denote the edits building on $\mathbf{\epsilon}^\star$ (by flipping zeros to ones), whereas [1] uses $2^{\epsilon^\star}$ to denote the edits building on $\epsilon^\star$ (by removing indices from the set).

• This representation difference explains why the direction of the inequality flips: we consider $\bar{\mathbf{\epsilon}} \sqsupseteq \bar{\mathbf{\epsilon}}^\star$, whereas [1] considers $\bar{\epsilon} \subseteq \bar{\epsilon}^\star$.

• The equality relating $s(\bar{\mathbf{\epsilon}}, \bar{\mathbf{x}})$ and $s(\mathbf{\epsilon}, \mathbf{x})$ follows from (2), where an input-dependent deletion probability is used in place of the constant deletion probability from [1].

If I understand correctly, the bound is derived from greedy algorithm of knapsack problem relaxation. Can you explain your bound tightness? It might be helpful to discuss it a bit for future better schedule $\psi$.

You're correct that we use a knapsack problem relaxation. The bound is sound but not tight due to constraint relaxations in the proof of Lemma 3.2 (following eq. 10). Regarding the design of $\psi$, we believe it should be tailored based on the specific dataset and base model characteristics. For instance, some datasets may not tolerate as much noise, necessitating a more conservative $\psi$.

Notation-wise (minor), $m$ is used to define bijection in lemma 3.1 and also define the num of trails in lemma 3.2.

Thanks for spotting this. We’ll use a different symbol in Lemma 3.2 to avoid confusion.

In the LUN setup, AdapDel is not better than CERT-ED at small radius. And when radius is small, the improvement is also marginal in IMDB and SpamAssassin. Can you explain why?

This behavior is expected. AdaptDel is configured to match CERT-ED's deletion rate (90%) for short sequences (Fig 3a), which primarily determines the certified radius. We expect (and observe) larger certified radii for longer sequences where AdaptDel's deletion rate increases. We will incorporate this explanation in the final version of the paper.

How does AdaptDel behave for extremely short inputs where deletion can harm semantics much?

For short inputs, AdaptDel uses the same deletion rate as CERT-ED, resulting in comparable semantic impact. Our input-dependent approach is motivated by the hypothesis that longer sequences can often tolerate higher deletion rates without significant semantic loss. Our experiments on multiple datasets support this hypothesis, demonstrating the effectiveness of our approach. This empirical validation, alongside our theoretical contributions in deriving certificates for input-dependent deletion, is a core contribution of our work.

Additionally, AdaptDel's increasing deletion rate with sequence length leads to more uniform post-deletion sequences. This characteristic could benefit the model across all sequence lengths by promoting more stable training and potentially easier learning of robust features, as the model encounters more consistent input lengths.

Thank you for the positive evaluation of our work. We're pleased you found our research direction interesting and our findings well-summarized. We appreciate your recognition of the sound intuition behind our approach and the comprehensive experimental evaluation.

Regarding your question about empirical robustness against text attacks:

We are familiar with the methodology used in [B] for testing empirical robustness. While we acknowledge the value of such empirical validation, our focus in this work is on provable robustness guarantees through certification. The certified radii we provide ensure that, with high probability, no attack within that radius can change the classifier's prediction. This means that:

• Any attack operating within the certified region would be provably ineffective with high probability.

• For potential attacks outside the certified region, a practical deployment of our method could employ abstention for inputs where robustness cannot be guaranteed.

Given these strong theoretical guarantees, we believe our current results demonstrate the effectiveness of our approach. This focus on certification without empirical attack testing is the norm for work on certified robustness, although we appreciate the value of empirical research in adversarial ML more broadly.

We thank the reviewer for their thoughtful feedback and constructive criticism. We appreciate the recognition of our work's technical merits and the improvements in certified robustness demonstrated by our methods.

Overall, the novelty and clarity are limited, and the scope is narrow.

We appreciate the reviewer's perspective. However, we respectfully disagree with this assessment. Our work introduces a novel approach to input-dependent randomized smoothing for discrete sequences, which has not been explored in previous literature. We extend the theoretical framework for randomized smoothing to variable-rate deletion, ensuring sound certification with respect to edit distance. This contribution is both novel and significant in the field of certified robustness.

Regarding clarity, we would appreciate specific feedback on which aspects of the paper were unclear, so we can improve the presentation in the final version. As for the scope, our work addresses a fundamental challenge in NLP robustness, applicable to a wide range of sequence classification tasks. We believe this scope is sufficiently broad and impactful.

AdaptDel+ introduces additional complexity through its calibration process, yet the paper provides limited discussion on its computational cost or reproducibility.

How computationally intensive is the AdaptDel+ calibration process, especially in scenarios with many bins or limited training data?

We thank the reviewer for highlighting this aspect.

Regarding computational cost: We acknowledge that our submission did not include information about the computational cost of the AdaptDel+ calibration process. Here are the calibration times for each dataset:

We note that the calibration process (Algorithm 5) has an asymptotic running time that is linear in the number of bins $n$ and sample size per bin $m$. It is done offline (following training) and does not contribute to online certification time. We will include these details in the final version of the paper.

Concerning reproducibility: The process is fully detailed in pseudocode in Appendix C, including Algorithm 5. We report the parameter settings used in Appendix D.3 and provide code in the supplementary material. If there are specific aspects of reproducibility that the reviewer finds lacking, we would appreciate more detailed feedback to address these concerns.

the method is a relatively straightforward extension of CERT-ED and remains limited to perturbations that only involve deletion.

Could the proposed approach be extended to certify robustness under general edit operations, including insertions and substitutions?

We appreciate the opportunity to clarify a potential misunderstanding. Our method is not limited to certifying deletion-only perturbations. Instead, it provides robustness guarantees against the generalized edit distance, where the set of edit operations $\mathsf{o}$ can be any subset of insertions, substitutions, and deletions. This is stated in Section 2, though we removed a more explicit paragraph to fit within the page limit – we will reinstate this in the final version.

By contrast, our smoothing mechanism does employ deletion operations only. This decoupling of the smoothing mechanism from the certified threat model is a key feature of our approach, though it's not a new concept [LJG21, LF21]. The critical requirement is that the smoothing distribution produces statistically similar outputs for inputs that are close in edit distance, which we achieve using deletion-based smoothing.

In our experiments, we focus on certification of (Levenshtein) edit distance, which is supported by our method and CERT-ED (line 243). RanMASK only supports Hamming distance certification (line 246).

Given the difficulty of interpreting the derived bounds, can the authors provide more intuition or visualization for how the adaptive deletion affects robustness?

The key intuition behind our approach is that while higher deletion rates generally improve robustness, they also tend to reduce clean accuracy. However, prior work has observed that longer sequences can tolerate more aggressive deletion without as significant a drop in accuracy. Lemma 3.2 can be used to bound the stability of a smoothed classifier with input-dependent deletion rates. While the bound is complex to express mathematically, it is computationally tractable. This is not uncommon in the certification literature, where bounds often cannot be expressed analytically but must be computed numerically [LYC+19, SKG22].

Our experiments demonstrate how adaptive deletion impacts robustness. In essence, we can achieve a similar robustness/accuracy trade-off for short sequences while improving performance for longer sequences. This is most clearly illustrated in Fig 2, where we plot certified accuracy grouped by quartile of input size.

References

• Liu, H., J. Jia, and N. Z. Gong. "PointGuard: Provably robust 3D point cloud classification." In: CVPR 2021.

• Levine, A. and S. Feizi. "Improved, deterministic smoothing for L1 certified robustness." In: ICML 2021.

• Súkenı́k, P., A. Kuvshinov, and S. Günnemann. "Intriguing Properties of Input-Dependent Randomized Smoothing." In: ICML 2022.

• Lee, G. H., Y. Yuan, S. Chang, and T. Jaakkola. "Tight certificates of adversarial robustness for randomly smoothed classifiers." In: NeurIPS 2019.