Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization

Summary

This paper proposes a new bound for margin maximization, as well as tighter estimation of Lipschitz constant, to improve the adversarial robustness of neural networks. Experiments on three benchmark datasets are presented to show the proposed method can improve the certified radius.

Strengths

- This paper is written well and clearly - New bound for input margin as regularization term - New estimation of Lipschitz constant for multi-layer networks - Experiments are conducted to show improved robust radius

Weaknesses

- Regarding the improved bound for input margin, I think the contribution is limited since the similar strategy has be used frequently in recently works. - The authors argued that the estimation of Lip. constant is scalable for multi-layer networks, but experimental results are not verified.

Questions

See above.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

The novelty of margin regularization is limited and the experimental results are not sufficient.

Summary

The authors explore how a model’s robustness to local pertubations in the input space can be enhanced through regularization at a low cost on the clean accuracy. The goal is to have large margins on the desicion boundaries in input space. Since adding a regularization directly on the size of these margins is very costly, the authors introduce an alternative and efficient proxy to regularize this. They use the Lipschitz constants of the logit difference function between pairwise classes to identify the most important directions to regularize. Since computing the constants is exactly is costly, but naive estiamtes are very conservative as they do not take into account the correlation between the trained layers, the authors introduce a new approximation that is efficient to compute. They show that the method is comparing well with SOTA adversarial robustness methods.

Strengths

1. The authors explore a new regularizer that is efficient to compute and can trade off the margin maximation in the input space via Lipschitz regularization which is still efficient to be used on classical toy datasets. They show that this regularizer is on par with existing approaches and may even outperform them. 2. They provide a new strategy to efficiently approximate Lipschitz constants which is of independent interest. 3. The paper overall is well written and structured; and can be followed comfortably.

Weaknesses

1. In the experimental evaluation, I would find it valuable to study your model also independently to see how the accuracy of the improved Lipschitz estimate affects the final accuracy outcome. The claim that the less conservative estimates lead to a better regularizer can be checked independently of other state-of-the-art methods. I think interesting experiments to support that claim could be: Comparing how the estimated (and naive) Lipschitz constant evolves throughout training for training with and without regularizer for the same architecture; replacing the improved estimate of the Lipschitz constant with the naive one; introducing a global hyperparameter that replaces L_{ij} and tunes it at the computational budget available to the Lipschitz constant estimation. These are just a few suggestions that would improve the understanding of the actual efficiency of the introduced loss regularizer. 2. The method relies on estimates for Lipschitz constants for every pair of classes, this scaling becomes unreasonable for datasets with many different classes.

Questions

1. In L.3 you mention Lipschitz-capped networks and argue on to say that these approaches are not good at increasing the input margin. Why is that exactly, does your own approach not follow a similar idea? 2. L.90, can you elaborate in a half-sentence on the problems of applying this to multilayer networks? 3. Can you comment at some point, on why you exclude wrongly classified examples from the regularizer and if this sequential inclusion is expected to have some effect? 4. I like the notation with the underline for the differentiable functions. However, since \underline{R}_t^soft is not computing the same version as the R_t^soft and is more closely related to \underline{R} I find the repetition of the names not optimal. Especially in L.249-252 the notation is confusing. First, in L. 251 there is a repetition (replace … with … with) and also it is not clear to me if h(x) in L.249 takes x=R_t^soft(x’,y,theta) so that the condition is a double application of R_t(R_t^soft(…)). I tried to understand it in different ways but I settled on the following to interpret the results: replace R(..) by x only in the case distinction in L.250 and the second ‘with' in L.51 to ‘and’. Could you please clarify if that is correct? 5. It would be nice if you could spend 2 more sentences explaining what you mean by loop transformation. To me the term was new and difficult to google, I checked the appendix to understand what was going on. 6. In (17) you use the function psi(.) which is not introduced in the main draft, only in the appendix - maybe you can explain that jointly with the loop transformation. 7. I did not find a definition of the Standard baseline, so I am just guessing that it is normal training without any regularization… 8. Can you give an intuition why you chose the specific values of l_2 perturbations in L.231/232? Is there a good reason why this was not tested for other values? 9. Can you give a clearer comparison how costly the computation of the approximate Lipschitz constants is in comparison to the backpropagation in terms of GPU time in your expeiments? O(L) is mentioned but it would be nice to understand what this means in practice. Minor comments: 1. In L.81 introduce the abbreviation SDP 2. L.88 constantS 3. L.95 To keep with convention, iterate over small i instead of small k in the CE 4. L.158 eqref missing 5. In (10) you just say ‘’compatible dimensions’ but then use dimensions in Thm.3.1 without introduction — it would be nice to make them clear from the start if you are going to use them anyways. 6. L.185 Abbreviation of LMI not introduced 7. L.189 blockS 8. The numbering of the equations in the Supplementary material is very confusing, as theorems and text have different numberings but are not distinguished (so the eq numbers are somehow in seemingly random order)

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors are clear about the limitations of their method in the paper. I would like to add that it is not immediately clear to me how more complex architectures would be amenable to similar estimates of the Lipschitz constants. Adversarial robust training which only relies on adapting the training data can achieve this for any architecture, so if this is not given, I would include it as a limitation.

Summary

This paper developed a robust training algorithm whose objective is to increase the margin while regularizing the Lipschitz constant of the model along vulnerable directions. The authors also developed an improved Lipschitz estimation for a multi-layer networks with residual connections. Experiments on MNIST and CIFAR-10 shows superior performance of the proposed method compared to the state-of-the-art.

Strengths

- A novel regularized loss function that directly promote larger margins in the input space is proposed. - A scalable Lipschitz bounding algorithm is proposed, which is tighter than the naive bound while being efficient. - Experiments on MNIST and CIFAR-10 showed the effectiveness of the proposed methods.

Weaknesses

- This paper proposed many interesting methods, but I sometimes find it hard to see the motivation of each proposed method and the connections between them. It may be good to spend some more space to set up the preliminaries: - The name is section 2 is a unified perspective on margin maximization, I'd hope to see what margin maximization algorithms it unified. For instance, the variant of (6) may result in different algorithms, replacing L_{yi} with \sqrt(2)L will results to Lipschitz margin training [Tsuzuku et al. 2018]. - It would be good to decouple the effectiveness of each component: the use of pairwise Lipschitz, the use of log-sum-exp to make max/min to be differentiable, the use of the new Lipschitz bounding algorithm. It would be interesting to see the contribution from each of these to the certified accuracy. - It would be good if the authors can discuss the sensitivity of the proposed method wrt the choice of hyper-parameters. An ablation study on CIFAR-10 with various hyper-parameters and the corresponding certified robustness performance would be helpful. The proposed method is not performing as well on Tiny-Imagenet, I understand that it may be because of the inferior choice of hyper-parameters, but it may be good to debug more into that, especially giving table 2, the improved pair-wise Lipchitz of Tiny Imagenet seems to be much better than other Lipschitz, it is surprising that it does not lead to better certified robustness. - It would be nice to provide the computational cost of the proposed method in terms of Flops or running time.

Questions

- In section 3, the proposed scalable Lipschitz estimation method seems to be work on neural networks with residual connections (Eq 16). But in the experiments, the model architectures seems to not have residual connections. How to apply the proposed bounds then? - What is loop transformation? I am not familiar with the term. - Line 221, Recurring structure can reduce the complexity by dynamic programing, but the operations are still sequential rather than parallel since we need m_j, j<=k to compute m_{k+1}. How does the parallelized implementation on GPU work?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes

Summary

This paper proposes a loss to induce robustness w.r.t. adversarial attacks. This loss is composed of a term for enlarging the logit difference (such as classical Cross-Entropy Loss), and a surrogate term to maximize the robust radius. The latter imply to compute an upper bound of the Lipschitz constant (called L_ij) of the difference of logits z_y-z_i (y is the true class and any other class i). Inspired by work in [39], the authors propose to take into consideration the motonicity of activation functions to compute a tigher lower bound of a residual-like layer than the classical one. They also propose an extension for computing an upper bound of the Lipschitz constant of a multilayer residual NN. Note that Batchnorm layers and dropout are not supported. They also claim to compute these L_ij with the same complexity as computing the Lipschitz constant of each layer (supplementary materials) Experiments are done on MNIST,CIFAR10 and TinyImagenet. Comparison is provided with several methods, reporting clean accuracy, adversarial accuracy (PGD attack) and certified accuracy, and report higher certified accuracy. They also compare the Lipschitz estimation to classical bounds (sqrt(2)Lz, Li+Lj and theirs Lij) and claims an improvement of up to 200.

Strengths

The algorithm described in section 3.1 seems new and results presented in table 1 indicate that it enhance the lipschitz estimation..

Weaknesses

-Clean performances are low and equivalent to 1LipchitzNN but author indicate in the related work that it should have a higher expressivity -No evaluation of computational complexity is provided. Scalability os the method is not clear

Questions

The paper is rather easy to read. Even if without the supplementary materials, Several errors or inexactitude can be found in Notation and equation and proof Computation of a tight upper bound of NN seems new and interesting. However enlarging the margin under lipschitz constraint or regularization is not new. And besides main loss and regularization may have contradictory objectives (see detail comments) Detailed remarks: L31: correlation between robustness and lipschitz constant of NN is an established property , cite[1] L33: “constraining the model (e.g. 1-Lipschitz models) can lead to excessive regularization in addition to potentially limiting expressivity.”: it has been shown that 1-Lipschitz NN have the the same expressivity has non constrained networks (see “pay attention to your loss”, Bethune et al. Neurips’22). Thus this sentence is false. L43: “hinges on the idea of loop transformation on the nonlinearities”: the notion of “loop transformation” is not clear. Please clarify or add a reference. L54: choice of tiny-imagenet is not justified. Authors claim for scalability (L84) but restrain the learning to tiny-Imagenet.This must be explained L92: notation for matrix norm is not described in this section, and ||.|| can be confusing: frobenius nor, spectral norm,… L100: “A unified perspective on margin maximization” : this section title is not justified. Please explain which unification is provided in this section? L111: “we note that maximizing the logit margin…..in the input space”: this is a well known property ([1]) L125: “many choices for h, we use the same function proposed in [17] (see supplementary materials) “ but no information is given in the supplementary matrials L132: eq 4 this equation is not use in the following, confusing in notation with eq (7), and not evaluated. Probably useless for paper understanding L134: .”Solving (4) still requires an iterative inner loop within the outer loop of training”: transformation from inf formulation to outer loop is unclear. Please precise if this loop is an adversarial search or any other method L146: “This lower bound is not differentiable”: min function is differentiable. A least subderivative. Justification l149 is a better one. Eq 9: it is known that CE loss aims to increase the Lipschitz constant of the NN during training (see paper Bethune et al cited earlier), and the regularization in (6) aims to reduce this Lipschitz constant. Please explain how these two antagonist objectives will be balanced. L169: inequality soes not represent the lispchitz constraint. A divide operator is missing Theorem 3.1: this theorem isbased on supposition of existence of \rho and T, but in the following justifications of this existence is not clear L185: “analytic solutions to the LMI of Theorem 3.1,”: acronym LMI is not defined L192: same remark as on line L33 L204: ||H|| isnot clear can be ether frobenius norm or spectral norm? L247: “,we calculate the certified radii using(6)” (6) is only applicable for ReLU like activation. Please justify how this certified robustness is computed for NN such as MaxMin (2) L249: “CRM hyperparameters”: first use of this acronym. Please detail L251: contradiction of justification given in eq (8). Please justify why the choice of h is not the same for each dataset. L255: “For Tiny-Imagenet, as the number of classes is far larger, bounding the pairwise Lipschitz would be computationally heavy.” Such a sentence and footnote 4 need justification. Please detail the computational complexity induced by your method Table 1: In related works, author indicate that 1-Lipschitz NN are harder to train and have a lower expressivity. However, clean performance of the proposed solution has performances equivalent to 1Lip solutions and far from classical performances. Please justify No software provided to verify the correctness of the paper Supplementary materials: L532: “However, the expressive power of 1-Lipschitz networks needs to be addressed and some works study their limitations [47]. ” this sentence is false. See remark on line 33 L580: \gamma is non differentiable. : Max operation is differentiable? L598: h function was supposed to be described in the supplementary materials L605 (equation) replace (1-t) by (1-t^hat) L615 (equation) i\neqy is replaced in this eq by i\in[1,K-1] pleae justify? L638: please justify te existenceof T and \rho? L660 m_k is not the lipschitz constant, but an upper bound of the Lipschitz constant L660 (eq) m_{k+1} should be lower than L673: eq 33 : lack || L719: “ Calculating the ℓ 2 norm of a general rectangular matrix can be performed by using the power iteration”: confusing notations: power iteration is for spectral norm and is often in general notes ||.||_2 and not l_2. Confusing with frobenius norm references: clean references for papers that are published and not preprint

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Limitations are addressed

Thank for the rebuttal

Thank you for the authors' rebuttal regarding more experimental results and explaination on the novelity.