Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations

Authors: Stefan Balauca, Mark Niklas Mueller, Yuhao Mao, Maximilian Baader, Marc Fischer, Martin Vechev
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Certified Robustness, Adversarial Robustness, Certified Training, Convex Relaxation, Neural Network Verification

Abstract:
Training neural networks with high certified accuracy against adversarial examples remains an open challenge despite significant efforts. While certification methods can effectively leverage tight convex relaxations for bound computation, in training, these methods, perhaps surprisingly, can perform worse than looser relaxations. Prior work hypothesized that this phenomenon is caused by the discontinuity, non-smoothness and perturbation sensitivity of the loss surface induced by tighter relaxations. In this work, we theoretically show that Gaussian Loss Smoothing (GLS) can alleviate these issues. We confirm this empirically by instantiating GLS with two variants: a zeroth-order optimization algorithm called PGPE which allows training with non-differentiable relaxations, and a first-order optimization algorithm, called RGS, which requires gradients of the relaxation, but is much more efficient than PGPE. Extensive experiments show that when combined with tight relaxations, these methods surpass state-of-the-art methods when training on the same network architecture for many settings. Our results clearly demonstrate the promise of Gaussian Loss Smoothing for training certifiably robust neural networks and pave a path towards leveraging tighter relaxations for certified training.

Decision: reject
Reviewer scores: 6, 1, 3

Reviews and discussion:
<thread>
creation date:
1729973119650

thread_type:
official_review

<thread_object>
creator: reviewer_xmev

<content>
summary:
This paper proposes to use Gaussian Loss Smoothing (GLS) with certified training algorithm, such as IBP, CROWN, etc. The motivation is that a previous paper pointed out that methods other than IBP, though having tighter relaxation, suffer from discontinuity, non-smoothness, perturbation sensitivity. The authors argue that GLS can make the loss surface smoother using a theoretical result and some plots as evidence. The method is tested on MNIST, Cifar-10 and TinyImagenet.

strengths:
1. The writing is fine. There is little difficulty understanding the paper.

weaknesses:
1. Contribution: This paper proposes to apply GLS to existing certified training methods such as IBP and DeepPoly, and one can use PGPE or RGS to compute the GLS. Note that, however, all of IBP, DeepPoly, GLS, PGPE and RGS are existing methods. Theorem 3.1 is a direct application of an existing result. So if I understand correctly, the only novelty of this submission is combining these things together, and thus the contribution is incremental.
2. Performance: How does the proposed method perform? From Table 1, it seems that the proposed method (PGPE) is not significantly better than the standard method (GRAD), if not worse. It is true that PGPE makes DeepPoly better than IBP, but the way it does that is to make IBP worse, not making DeepPoly better. On MNIST (0.3) and CIFAR-10 (8/255), the best PGPE method is worse than the best GRAD method. On the other two settings, it is only slightly better. For all settings, IBP-PGPE is worse than IBP-GRAD (standard). Thus, this result suggests that one probably should not use PGPE. There is no evidence that the proposed method works in practice.
3. Experimental results: Tables 1 and 3 seem contracting with each other. In Table 1, standard IBP on CIFAR-10 (2/255) has natural accuracy 48.05% and certified accuracy 37.69%; in Table 3, the two reported numbers are 54.92% and 45.36%. Probably this is because CNN5 is better than CNN3, but then what is the point of Table 1? Why not always use a bigger model (CNN7 seems even better). And why not compare with RGS in Table 1? I don't think there is anything preventing you from comparing with RGS in Table 1. The authors report DP-RGS to be the best method in Table 3, but since there are so many problems with the tables I do not trust this result.

Overall, this submission proposes to combine a bunch of existing methods, but the experiments show that this is even worse than the original methods. Thus, I recommend rejecting this submission.

questions:
1. DeepPoly-GRAD achieves 90.04% certified accuracy on MNIST (0.1) in Table 1; in Table 2 this number is only 68.47%. Is this a typo? I don't believe that changing the model size can make such a big difference; plus, only DeepPoly-GRAD has such a huge drop in performance.
2. Is it correct that you are only changing the loss of training the model, but you are not changing the way of certifying the model?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730586006919

thread_type:
official_review

<thread_object>
creator: reviewer_v31k

<content>
summary:
The paper talks about the variation in certified training; though tighter relaxations sometimes reduce performance compared to looser bounds, it shows the authors introducing Gaussian Loss Smoothing as one of the methods for smoothing the loss landscape to reduce discontinuity and sensitivity—the major hurdles in certified training with tight relaxations.

They provide two ways of realizing the different realizations of GLS: first is PGPE, a gradient-free approach based on policy gradients with parameter-based exploration; second is RGS, which is described as a gradient-based approach using randomized gradient smoothing. Experimental results on several datasets illustrate that indeed the algorithm GLS outperforms current methods relying on tight relaxations; sometimes its performance is tested along with the DEEPPOLY relaxation.

strengths:
GLS introduces novelty in using Gaussian smoothing across the loss landscapes, strongly problematic in certified training.

weaknesses:
## Writing Style

- **Introduction**: In some respects, the introduction could be improved about adversarial certified robustness. It is abrupt and feels more work-related.
  
- **Transitions and Structure**: Transitions from one section to another are missing; hence, making the paper hard to follow. Statements such as, "While CROWN-IBP is not strictly more or less precise than either IBP or DEEPPOLY," necessarily need references or explanations.

- **Undefined Terms**: Terms such as "soundness" and "sensitivity" are undefined.

- **Results of experiments**: These are presented in a very untidy fashion.


## Related Work

- **Definitions**: Some more clear definitions can be provided, for instance, adversarial attack and adversarial robustness because the latter is different from certified robustness.
  
- **Redundant Subsections**: Sections 2.1 would seem to represent redundant subsections: "Training for Robustness" and "Adversarial Training."


## Theoretical Findings

- **Lack of Rigor**: Theoretical statements, like Theorem 3.1, are informal and not mathematically precise. References to results, including Stein's Lemma [2], could be good in the proof.
  
- **Flaw in Proofs in Lemmas**: 
In the proof of Lemma B.1 terminology and symbols that are important are not defined (for example, \(\delta \theta\), \(P_{\epsilon_1}\), \(P_{\epsilon_2}\), \(P_{\mathcal{N}(0, \sigma^2)}\)). The authors seem to take the limit $\delta \theta$ to $0$ but it is never stated anywhere in the proof and the integral of the derivative of the loss  $L^\prime$  should be a multi dimensional integral as the input space is multi dimensional.
In Lemma B.2's proof  the simplifications are excessive,  the structure of the proof is highly defective in many places and it needs a thorough revision. 



## Experimental Results

- **Lack of Detail**: Neither the dataset nor the architecture used in Figure 1 are specified.
  
- **Performance Gains**: Although the experimental results are somewhat improved, they are not very significant compared to previous methods; therefore, this added complexity is questionable in value. Presentation of the standard deviations over multiple runs would have given more robust conclusions since apparent gains are marginal.


# Major Concerns

1. **Theoretical Rigor**: The proofs are not rigorous; better structure and formalization are required. The use of Stein's Lemma might improve the underlying framework, giving credibility to the theoretical results.
  
2. **Marginal Gains and Complexity**: GLS brings in computational complexity especially with PGPE, while performance benefits are marginal.

3. **Readability and Clarity**: The writing style and the structure take away from clarity, making the paper difficult to follow.


[2] Stein, “Estimation of the Mean of a Multivariate Normal Distribution,” The Annals of Statistics, 1981.

questions:
GLS appears to be related to Sharpness-Aware Minimization (SAM) [1], as both approaches aim to smooth the loss landscape for a more regular surface. It would be beneficial to include a discussion or a related work section to clarify this connection in the paper.

[1] Foret et al., “Sharpness-Aware Minimization for Efficiently Improving Generalization,” ICLR, 2021.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730615273845

thread_type:
official_review

<thread_object>
creator: reviewer_9dhw

<content>
summary:
This paper proposes to use a method (Gaussian Loss Smoothing) to address the paradox of certified training which is caused by the discontinuity/non-smoothness/sensitivity issues of certifiable training with tighter convex relaxations. Moreover, the authors also use a gradient-based method called Randomized Gradient Smoothing (RGS) to scale GLS to larger models.

strengths:
I think the following strength itself is enough for accept.
- The paradox of certified training is an important subject to study.
- The proposed method (GLS) is well-motivated and backed up by theoretical results.
- The empirical results on small perturbation settings in Table 3 are quite impressive.

weaknesses:
This paper is well-motivated, but has a minor weakness in the performance (on large perturbation) detailed as follows:
- Table 3 (Table 5 in Appendix) shows the results for small (large) perturbation settings. The results for large perturbation is not significant. IBP performs well for large perturbations and other tighter methods does well for small perturbations. This is because of the continuity, smoothness and sensitivity of the loss landscape. Thus, to check the effectiveness of GLS, I think it is crucial to check the result of tighter methods on large perturbation settings. However, setups (i) MNIST $\epsilon=0.3$ and (ii) CIFAR-10 $\epsilon=8/255$ show that 
GLS (or RGS) (i) does not show a significant performance gain (DP-RGS (IBP) vs MTL-IBP; 88.69 vs 88.68) or (ii) shows a worse performance (29.25 vs 29.62). This should be discussed in the main text (not in Appendix). I don't think the performance itself is a reason for a rejection, but it needs more discussion.
- In Table 1, "the more precise DeepPoly bounds now yield the best certified accuracy across all settings, even outperforming accuracy at low perturbation radii'', but not for the large perturbation (IBP vs DeepPoly-PGPE; 77.23 vs 74.28, 25.72 vs 22.19).
- In GRAD Training, "IBP dominates the other methods, confirming the paradox of certified training", but in the original paper of CROWN-IBP, CROWN-IBP outperforms IBP for a larger network (see their Table 2 https://arxiv.org/pdf/1906.06316). 
- (For a larger model,) IBP outperforms the other methods (e.g, CROWN-IBP, CAP) for large perturbation, not for small perturbation (e.g., see Table 1 in Lee et al. (2021)). This implies that the paradox plays more important role for a larger perturbation.



Please check the Questions part together. I think unclear presentation is also a weakness.

questions:
- There is no comparison with CROWN-IBP in Table 3. Why?
- "We remark that scaling to CNN7 used by the SOTA methods is still infeasible due to the high computatinoal cost of evaluating DeepPoly" How about applying RGS to CROWN-IBP as it is cheaper than DeepPoly?
- What do the italic numbers mean in Table 3?
- DP-RGS appears first in L480, but never defined (seems like DP-RGS = DeepPoly-RGS).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732364613159

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We thank all reviewers for their insightful reviews, helpful feedback, and interesting questions.
$\newcommand{\Rd}{\textcolor{green}{9DHW}}$
$\newcommand{\Rv}{\textcolor{blue}{v31k}}$
$\newcommand{\Rx}{\textcolor{orange}{XmeV}}$
We are particularly encouraged that reviewers consider our work novel, well motivated and intriguing ($\Rd$, $\Rv$, $\Rx$), the experimental results and conclusions insightful for the community ($\Rd$, $\Rv$), and the paper well-written ($\Rd$, $\Rx$). We will incorporate the reviewer’s writing suggestions. 

As we did not identify any shared questions among reviewers, we will address each reviewer’s questions in individual responses. We look forward to the reviewers’ replies.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The main claim of the paper is that issues arising in certified training can be alleviated by smoothing the loss surface in parameter space of a neural network by convolving it with a Gaussian distribution. 

Combining ideas of loss smoothing and convex relaxation is an interesting direction, and some of the experiments in the small perturbation setting are encouraging. However, there are several concerns pointed out by the reviewers regarding theoretical rigor, marginal gains in the experiments and incremental contributions. 

I recommend to reject the paper and encourage the authors to take the detailed comments of the reviewers into account for a resubmission.