- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This work studies one particular method for neural network certification, namely SDP. It studies various theoretical properties of the diagonal multiplier of SDP. It then demonstrates its theoretical results with empirical studies.
Critical strengths
SDP is one of the major methods in verifying robustness, therefore, understanding and improving it is an important problem.
Critical weaknesses
-
The paper is extremely badly written. I tried hard to read it and still find it confusing. It rarely has intuitions well-explained, and the proof sketch is also weak and abstract. Explaining the intuition and sketch via minimal examples or plots would have been better. I do not think any reader can reasonably understand the current manuscript without significant difficulty.
-
The empirical result is very weak. The main result uses networks with up to hundreds of neurons, while SDP-CROWN which also uses SDP for robustness, has scaled to millions of parameters. At radius 0.3, this work achieves up to 56.6% on MNIST, while SDP-CROWN reports more than 80%. This might be due to the model scale, but if the method proposed is not scalable at all, what will be the credit?
Questions for authors
See weakness
6 comments
Dear authors,
Thanks for the effort, especially the improved writing. However, I am still unconvinced about the novelty of this work. In particular, the authors try to say it is unnecessary to compare against SDP-CROWN, which I believe to be super weak, as all theoretical results ultimately want to guide the practice. Especially when this work also presents a new algorithm, even though it does not claim sota.
Part 1. Thank you for the follow-up and for noting the improved writing
It does present a new, provably valid certificate family, the block-multiplier hierarchy, but we do not propose it as a verifier (§1, "Scope"): used as one, it gives a modest gain at a higher cost, so we do not claim state of the art. The paper is a measurement study. Its credit is twofold: methods that make the cost of diagonal multipliers measurable with certified bounds, and the certified findings they produce.
Terms, as used in the paper.
- Multiplier: the weights an SDP certificate puts on the conditions that each activation's slope stays in a known range (for ReLU, between 0 and 1). A diagonal multiplier gives each neuron its own weight; a block multiplier also couples the neurons within a group; the full block is one group with all neurons of a layer.
- Storage function: an energy-like quadratic function that some certificates use to track how the difference between two inputs changes over time steps (for a feedforward network, a time step is a layer).
- Static: a static multiplier acts at a single time step. A static fixed-point certificate for deep equilibrium models (DEQs) works directly on the fixed-point equation, with no storage function.
- Reference value: the smallest bound that a quadratic storage function can prove from the slope ranges alone, with each neuron's slope free to vary over time (one storage per layer for feedforward networks). No certificate that combines such a storage with a static multiplier, diagonal or not, can prove less.
- Price: the diagonal bound divided by the reference value; 1.05 means the diagonal bound is 5% above it. For DEQs, certificates without storage are never worse (Proposition 6(v)), so there both bounds are static fixed-point certificates: the diagonal one divided by the best one with the full block.
Thank you. The general comment lists the changes. As you suggested, Figure 1 is now a minimal example with three neurons and a plot (exact values in App. E). §4–§6 start with intuition, and the proof ideas after Theorem 2, Theorem 5 and Proposition 6 go step by step.
Scale and SDP-CROWN. The paper is a measurement study, not a new verifier (§1, "Scope"). It asks how much tightness diagonal multipliers cost in SDP Lipschitz certificates. Measuring this from both sides needs the reference value, the best bound this certificate type can prove. Computing it takes 2m LMIs for a layer of m neurons and is NP-hard already for one hidden layer, so two-sided results are limited to small models. One-sided bounds scale further: new App. K certifies that the price is at most 19.3% on 27 feedforward networks (up to six hidden layers and 768 neurons) and at most 11.0% on 9 convolutional networks; for 18 residual networks the bounds are inconclusive.
The 56.6% is the mean certified accuracy at radius 0.3 of three width-40 monotone DEQs on MNIST (Table 2). It comes from Lipschitz bounds that hold for all inputs, with four-neuron block multipliers. SDP-CROWN computes bounds for each input separately, on different and larger models, so the two numbers are not comparable. §2 now cites SDP-CROWN and says this.
What the measurement offers. We measured how much looser diagonal multipliers make the bound than the best bound of the same certificate type: on the networks with certified two-sided bounds, at most 4.94% for feedforward networks and 12.29% for DEQs (against the static full-block certificate). A much larger gap comes from using only slope ranges: in one ReLU network, every bound that uses only slope ranges, including ours, exceeds the true Lipschitz constant by over 72%. So, on these networks, richer static multipliers can tighten the bounds only slightly, and designers of SDP certificates are likely to gain more from information that slope ranges discard.
If any point that affects your assessment remains open, please tell us and we will address it.