- Rating
- 3(+2)
- Confidence
- 4
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes to use a neural architecture that is a *mixed-monotone function; specifically, the paper investigates the difference of two sign-constrained (think: monotonic) networks. The motivation is that interval output bounds (for given input bounds) can be computed by normal forward passes of only two normal inputs (namely the minimum and maximum bounds). The experiment investigates the performance of this architecture and how the bound propagation compares to other bound-propagation tools.
Critical strengths
- The observations made in this paper are interesting and worthy publishing.
Critical weaknesses
-
The difference of two monotonic networks does not sound convincing to me for any but the simplest tasks. As the authors argue, they obtain interval bounds, which are known to be too coarse in most practical cases.
-
I am not sure that the paper contains significant conceptual contributions. The theory of mixed-monotone functions has been developed before, and the authors went for the simplest possible choice (which was also known before): the difference of two monotonic networks.
-
The experiments are not sufficient to convince me. While the networks are quite deep (up to 8 layers), I could not find any mention of how many neurons were used, and from the very simple environments, I presume that the answer is "not many." I really think that the practicality of mixed-monotone networks must be demonstrated viable in challenging scenarios (beyond simple control tasks) to be competitive at a top ML conference.
-
The paper contains quite a few obvious errors. This lowers my confidence in the paper significantly. Examples:
- Definition 2 is not sufficient for a neural network to be monotonic. It misses the requirement that the activations are monotonic.
- Example 1 is completely broken. Eq. (3) should say
2 \max(1-x, 0)to match the figure. Two lines below, the interval computation is also wrong (0 - (-2) is not -2). Similarly, the second network is also broken.
Questions for authors
-
The significance of the contribution would be demonstrated if you can do something that other approaches cannot. So you need to take a network that is too large for other approaches and verify an interesting property. Can you do that?
-
If your approach computes IBP results, why do you improve over the zonotope approach in Fig. 3? I expect your bounds to be looser. Also, why do you not show the results for (\alpha-)CROWN?
7 comments
Thanks for the clarifications.
The new results indeed look promising. How did you select ? For MNIST, does this mean you analyze robustness up to 25 grayscale levels for each pixel ()?
Regarding the precision, I still do not understand why your approach is more precise than the zonotope baseline. As far as I understand, it should be expected that you get quite loose output bounds as shown in Figure 1. This is because IBP loses dependencies in the many multiplications in the layers. You only obtain these bounds faster than before. The zonotope baseline, while not perfect, should preserve at least some of these dependencies. Am I missing something?
Thank you for your follow-up and for your positive assessment of the new results. Your question showed us that the paper did not explain why IBP is precise on our architecture; we have added this explanation, and that all methods in Tab. 2 run on the same networks, to Sec. 5.2 (marked in blue).
Choice of . We use , one of the standard perturbation radii for MNIST in certified training (Gowal et al., 2019; Mao et al., 2024; Sec. 5.4). Yes: with pixel values in , every pixel can change by up to of gray levels simultaneously.
Precision. Fig. 1 is a schematic; its sets are not computed. You are right that IBP loses dependencies in the linear layers of general networks. This happens when the neurons of a layer attain their bounds at different inputs, which requires weights of mixed signs. In our subnetworks, all weights are non-negative and all activations are non-decreasing, so every neuron attains its lower bound at the lower corner and its upper bound at the upper corner of the input interval. IBP therefore computes exactly the ranges and : within the subnetworks, there is no dependency to lose. The only lost dependency is the one between and , whose extremes lie at opposite corners. This loss occurs once, at the output; our training minimizes it (Eq. (5)), and Prop. 3 bounds it from below. With the enclosure penalty, our enclosure is within 0.4% of the sampled image (Tab. 3). Hence, we do not compute loose bounds faster; we change the network so that its interval bounds are exact up to the decomposition, and we train the decomposition to be tight.
Zonotope propagation preserves dependencies through the linear layers, but it relaxes every activation whose input interval is not within a linear region, i.e., every unstable ReLU and every tanh neuron, and each relaxation adds an error term that all subsequent layers propagate. In Tab. 2 and Tab. 10, we propagate one zonotope through both subnetworks of the same networks (trained without the enclosure penalty, ), so it even keeps the dependency between and that our enclosure loses. Still, its tightness degrades from 1.08 at two layers to 1.44 at eight layers, while ours improves from 3.58 to 1.05: the zonotope is tighter for shallow networks, ours for deep ones. Tab. 5 shows the same crossover over the radius against the unconstrained baseline: the radius above which our enclosure is smaller shrinks from 1.0 at three layers to 0.025–0.04 at six and eight layers. On MNIST, zonotope propagation through our network certifies 92.30% of the test images and our enclosure 94.60% (Tab. 6).
Dear reviewer evjb,
we thank you for your detailed feedback and for finding our core observations interesting. We are particularly grateful for your precise list of technical corrections. We have fixed the omission in Def. 2 and clarified Fig. 2, which caused the confusion about Example 1. For your convenience, we mark the changes in our revised paper in blue.
We have rewritten the appendix for clarity and therefore marked it entirely in blue; the changes most relevant to your review are the revised proof of Prop. 3 (App. A.1), the architectures and parameter counts of all compared neural networks (App. A.4 and Tab. 7), and the details of the evaluation over multiple time steps in Fig. 3, including a corrected size of the zonotope enclosure (App. A.9).
W4 — Errors (Def. 2 and Example 1) Thank you for catching the omission in Def. 2. You are correct that it required a non-decreasing activation condition, which we have now added. Regarding Example 1, we apologize for the confusion about the figure. The math in Eq. (3) is correct as written, but Fig. 2 plots the negated subnetwork (−Φ−), causing Φ−(2)=2 to visually appear as −2. To prevent this confusion, we have updated the caption of Fig. 2. We hope this revision makes the example clearer and easier to follow.
W3 — Network size We thank you for pointing it out. Each subnetwork of our fully connected networks has 32 neurons per hidden layer, i.e., 194 to 26k parameters in total (Tab. 7); the new MNIST CNN has 1.7M parameters. We ensured the total parameter count of every compared baseline architecture agrees with ours to within 2%. We have added this detail to Sec. 5 and provided a comprehensive parameter count table and architecture details in App. A.4.
W1/Q2 — IBP, zonotopes, and α-CROWN On our architecture, the enclosure coincides with IBP. IBP is coarse on general networks because it adds an abstraction error at every layer; on our architecture it adds none, since each monotone subnetwork is evaluated exactly at the two corners of the input interval. The only overapproximation stems from the decomposition, which our training minimizes and Prop. 3 bounds from below. This relies on the sign constraints: for the monotone Lipschitz-constrained subnetworks (Kitouni et al., 2023), IBP is looser by factors of 1.15 to 1.49 (App. A.6). Our contribution is thus not a tighter bound computation for a given network, but an architecture on which computing bounds does not require a per-layer abstraction error, together with a training objective that minimizes the enclosure size. Regarding Fig. 3: the two enclosures are computed for different networks (App. A.9), ours for our trained mixed-monotone network and the zonotope for an unconstrained network trained on the same data. The zonotope accumulates abstraction errors over layers and time steps, whereas our enclosure has no per-layer abstraction error and, for the cooperative Tanks system, a nearly exact decomposition (Tab. 3). On the same networks (Tab. 2, Tab. 10), α-CROWN is tighter but up to 20,600$\times$ slower (at eight layers, our enclosure is 5.1% larger). We omitted it from Fig. 3 because of this runtime (4.3 s vs. 0.21 ms per input set at eight layers, Tab. 2).
W2 — Novelty We completely agree that the mathematical difference of two monotone networks is an established concept and we have updated the related work accordingly. We believe our core contribution lies in how this structure is utilized: explicitly training the decomposition to minimize enclosure size (Eq. 5), computing bounds without layerwise set propagation. Moreover, Prop. 3 characterizes the smallest enclosure that any difference of two monotone functions can achieve (the total variation along chains, which is attained), so we can measure how close a trained decomposition is to the optimum (within 0.5%, Tab. 3).
Q1 — Scaling to harder tasks We appreciate you pushing us to demonstrate practicality beyond simple control tasks. We have added a convolutional MNIST benchmark with 1.7M parameters (Tab. 6). At an equal parameter count, our enclosure certifies 94.60% of the test images at ϵ=0.1 in 0.59 ms per image from two forward passes. Zonotope propagation on the same network certifies 92.30% in 825 ms per image, and α-CROWN exceeds the budget of 100 s on every test image; without a budget, it requires at least 3,263 s per image on the first 23 test images (App. A.6). Our certified accuracy stays below that of state-of-the-art certified training (about 98% on MNIST at ϵ=0.1), which we state in our limitations; our contribution is the cost of the enclosure, not the certified accuracy.