acceptodds
Under review as a conference paper at ICLR 2027

Semidefinite Bound Propagation for Neural Network Verification with General Activations

Abstract

Linear bound propagation enables scalable neural network verification by propagating linear bounds through activation functions, but these bounds can lose tightness for general activations. The semidefinite bound propagation method SDP-CROWN strengthens these bounds while retaining efficient linear bound propagation, but its construction relies on a quadratic outer approximation derived from ReLU's piecewise linear structure. We extend semidefinite bound propagation to general activations using quadratic outer approximations derived from sector bounds and quadratic bounds. Our construction converts these constraints into optimizable linear bounds over ellipsoidal domains, which we refine recursively using the same semidefinite bound-propagation framework. The resulting linear bounds integrate directly into the standard bound-propagation recursion, enabling scalable verification against both and adversaries. Our experiments demonstrate substantial improvements in verification performance across all benchmarks with general activations. On representative benchmarks, our method improves verified accuracy over GenBaB from 12% to 57% on MNIST under perturbations and from 23% to 87% on CIFAR-10 under perturbations.

Primary area:
optimization
Keywords:
Neural network verification, Machine learning, Optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_oYPeOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper extends the approach of SDP-CROWN from ReLU to general activation functions. The method integrates sector bounds, quadratic bounds, and ellipsoidal domains; it derives an optimizable linear bounding oracle via semidefinite programming (SDP) relaxation and its dual, which is then embedded into a standard backward bound propagation framework. Furthermore, the authors employ this same framework to recursively refine the ellipsoidal domains at each layer. Experiments are conducted on feedforward networks—utilizing sigmoid, tanh, sine, and GeLU activations—trained on the MNIST and CIFAR-10 datasets, with considerations for both ℓ2\ell_2 and ℓ∞\ell_\infty perturbations. Under a unified time constraint, the complete method achieves higher verified accuracy than α-CROWN and GenBaB across the reported benchmarks.

Critical strengths
  1. The method makes a clear technical contribution. This paper unifies sector bounds and quadratic bounds into an optimizable linear bounding oracle. This allows information derived from semidefinite programming (SDP) to be applied to general activation functions, while maintaining the efficiency of layer-wise linear backward propagation. This extends the applicability of existing methods and avoids the need to solve dense SDPs during the propagation process, offering significant practical algorithmic value.

  2. Consistent experimental gains support the effectiveness of the method. Under a uniform 300-second timeout, the full method achieves higher verified accuracy across a variety of activation functions, network architectures, and two types of perturbations. Even the version that excludes Branch-and-Bound (BaB) demonstrates notable performance gains, indicating that the improvements do not rely solely on branching. These results provide compelling evidence for the practical utility of the proposed bound construction.

Critical weaknesses

The paper provides an insufficient explanation of the background of SDP and its connection to the actual algorithms employed. For readers familiar with linear bound propagation but less acquainted with SDP, the transition in §2.2 and §4.1—from quadratic constraints to a linear bounding oracle—feels somewhat abrupt. Although the paper includes the relevant formulas and proofs, it lacks a comprehensive example illustrating how the relaxation is constructed, the source of its soundness, and how it ultimately yields the linear bounds that can be propagated. It is recommended to include brief background context in these sections, along with a running example that follows the entire computational process, to enhance the clarity of the paper’s core contributions.

Questions for authors
  1. Could you provide a simple example illustrating how quadratic constraints are transformed into propagatable linear bounds via SDP relaxation and dual formulation? Specifically, I would appreciate an explanation of where the reliability of these bounds originates, and how this theoretical derivation maps to the actual parameter optimization process.

  2. Does the improvement in precision primarily stem from a more accurate characterization of the activation function's shape, or from the joint constraints across multiple neurons—facilitated by the use of ellipsoids? Could you also discuss the reasons for the observed performance variations across different activation functions, in light of your current results?

  3. The current framework does not support general computational graphs. Is this limitation inherent to the theoretical approach, or is it a constraint of the current implementation? For networks involving multivariate operations, which components of the existing framework can be directly reused, and which parts would require the development of new methods?

  4. Appendix B.3 presents a method for decomposing dot products and softmax operations into scalar operations. Could the authors discuss whether this expansion is expected to yield sufficiently tight bounds? Given the inherent quadratic structure of the dot product, is it appropriate to construct a joint relaxation directly? Furthermore, in the case of softmax, can ellipsoidal constraints help capture the joint variation of the exponential terms, as well as the dependency between the numerator and the shared denominator? It would be beneficial for the authors to discuss the potential advantages and primary challenges, rather than focusing solely on the formal decomposition of these operators.

4 comments
AuthorsOpenReview ↗

Author Rebuttal (Part 1)

Could you provide a simple example illustrating how quadratic constraints are transformed into propagatable linear bounds via SDP relaxation and dual formulation? Specifically, I would appreciate an explanation of where the reliability of these bounds originates, and how this theoretical derivation maps to the actual parameter optimization process.

Thank you for this suggestion. Section 4 briefly explains how quadratic constraints are transformed into propagatable linear bounds. We will expand the derivation and provide additional background in the final version.

Here, we illustrate the construction using sector bounds for the one-dimensional verification problem $$\min_{z^2/d^2\leq 1}c\sigma(z).$$ After constructing sector bounds for $\sigma(z)$, our key insight is that its dual SDP relaxation provides a family of valid quadratic lower bounds$$g(\lambda)z+h(\lambda)-\frac {m(\lambda)}{2}z^2 \leq c\sigma(z) \text{ for all }\frac{z^2}{d^2}\leq 1$$ for any $\lambda\in\mathcal L$. Here, $m(\lambda)\geq 0$ and the precise definition of $g(\lambda),h(\lambda),m(\lambda)$ and $\mathcal L$ are in Lemma 1. For each $\lambda\in\mathcal L$, minimizing $z$ gives a valid lower bound on the verification problem, which is exactly the process of bound propagation $$\max_{\lambda\in\mathcal L}\min_{z^2/d^2\leq 1} g(\lambda)z+h(\lambda)-\frac {m(\lambda)}{2}z^2 \leq \min_{z^2/d^2\leq 1}c\sigma(z).$$ To see how the quadratic bound becomes linear, observe that $\min_{z^2/d^2\leq 1} g(\lambda)z+h(\lambda)-\frac{m(\lambda)}{2}z^2$ attains its minimum at $z=d$ or $z=-d$. Therefore, $$\min_{z^2/d^2\leq 1} g(\lambda)z+h(\lambda)-\frac{m(\lambda)}{2}d^2=\min_{z^2/d^2\leq 1} g(\lambda)z+h(\lambda)-\frac{m(\lambda)}{2}z^2.$$ Thus, setting $z^2=d^2$ preserves the inner minimization of bound propagation. Finally, since $z^2\leq d^2$, we can equivalently propagate a family of valid linear bounds $$g(\lambda)z+h(\lambda)-\frac{m(\lambda)}{2}d^2\leq c\sigma(z)\text{ for all }\frac{z^2}{d^2}\leq 1$$ for any $\lambda\in\mathcal L$.

Does the improvement in precision primarily stem from a more accurate characterization of the activation function's shape, or from the joint constraints across multiple neurons—facilitated by the use of ellipsoids? Could you also discuss the reasons for the observed performance variations across different activation functions, in light of your current results?

Thank you for the interesting questions. The improvement of our method stems from both a more accurate quadratic outer approximation for the activations and the ellipsoid domain. From an optimization point of view, each quadratic outer approximation, either a sector bound or a quadratic bound, provides second moments that capture the second-order information of an activation function. On the other hand, ellipsoids provide restrictions on those second moments. Importantly, the second moments generated from sector or quadratic bounds cannot provide any benefit alone without being restricted by ellipsoids. Similarly, the second-order restriction from an ellipsoid cannot provide any benefit alone without the individual second moments generated from sector bounds or quadratic bounds.

We are not certain of the cause of performance variations across different activation functions. One plausible explanation is how accurately the linear and quadratic outer approximations characterize each activation over the actual preactivation intervals. For example, tanh⁡\tanh is approximately linear on the interval [−0.5,0.5][-0.5,0.5]. A linear relaxation can therefore already be accurate in this interval, leaving less room for additional quadratic constraints to improve the bound. On the other hand, GeLU is highly nonlinear on [−0.5,0.5][-0.5,0.5], leaving more room for additional quadratic constraints to improve the bound.

AuthorsOpenReview ↗

Author Rebuttal (Part 2)

The current framework does not support general computational graphs. Is this limitation inherent to the theoretical approach, or is it a constraint of the current implementation?

Our proposed method is compatible with general computational graphs as long as all the nonlinearities inside could be supported. The previous lack of support was due to limitations of our current implementation. During the rebuttal period, we implemented the subroutine necessary for our method to support general computational graphs. We provide some results for the LSTM models used in the GenBaB paper. We can see that our methods beat GenBaB already before any branch-and-bound. We will continue to work on supporting general computation graphs and add more results.

ModelUpper Bound (%)OursOurs w/o BaBα-CROWNGenBaB
LSTM-4-3210090(64.4s)90(45.9s)64(33.4s)78(86.4s)
LSTM-4-6410071(121.1s)71(73.4s)48(44.2s)62(147.7s)

For networks involving multivariate operations, which components of the existing framework can be directly reused, and which parts would require the development of new methods? Appendix B.3 presents a method for decomposing dot products and softmax operations into scalar operations. Could the authors discuss whether this expansion is expected to yield sufficiently tight bounds?

We thank the reviewer for this interesting question. Our proposed linear bounding oracle is formulated for univariate activation functions σ:R→R\sigma:R\to R, for which sector and quadratic bounds can be constructed.

Our proposed method cannot be extended directly to multivariate activation functions σ:Rn→R\sigma:R^n\to R such as inner products and softmax. One simple way to apply our method to multivariate functions is to decompose them into univariate functions. For example, the inner product admits the exact decomposition xTy=14∑i=1n[(xi+yi)2−(xi−yi)2]x^Ty=\frac{1}{4}\sum_{i=1}^n[(x_i+y_i)^2-(x_i-y_i)^2]. During the rebuttal period, we extended our method to handle general computational graphs, enabling it to handle inner products through this decomposition. Using this decomposition, we verified the LSTM benchmarks used in GenBaB, which involve inner product operations. We observed improvements over GenBaB on these benchmarks, demonstrating the practical usefulness of this approach.

Given the inherent quadratic structure of the dot product, is it appropriate to construct a joint relaxation directly?

Thank you for providing this valuable insight. The quadratic structure of the inner product allows us to derive a linear bounding oracle using a paradigm similar to that in our paper. We derived the corresponding oracle during the rebuttal period.

We described a simple case of this result, the complete linear bounding oracle and proofs are included in Appendix E of the revised paper. In particular, let $\mathcal E_2(\hat x,d)=\{\hat x + \mathrm{diag}(d)u\mid \|u\|_2\leq 1\}$ denote an ellipsoid in $R^n$, then the following linear bound holds $$\hat y^Tx+\hat x^Ty-\hat x^T\hat y-\frac{\eta_x+\eta_y}{2}\leq x^Ty\text{ for all } x\in \mathcal E_2(\hat x,d_x), y\in \mathcal E_2(\hat y,d_y)$$ for any $\eta_x\geq 0$, $\eta_y\geq 0$ that satisfy $\eta_x\eta_y\geq d_{x,i}^2d_{y,i}^2$ for all $i=1,\ldots,n$.

Our linear bounding oracle for the inner product can yield bounds that are a factor of $n$ tighter than those of GenBaB. To illustrate this, consider a simple case $(x,y)\in D$ where $D = \{(x,y)\mid \|x\|_2\leq 1,\|y\|_2\leq 1\}$. This corresponds to $\hat x=\hat y = 0$ and $d_x = d_y = 1$. Since GenBaB uses a linear relaxation, the variables $x_i$ and $y_i$ are treated independently. Hence, $$\min_{(x,y)\in D} x^Ty\geq \sum_{i=1}^n\min_{|x_i|\leq 1, |y_i|\leq 1} x_iy_i=-n.$$ Our method account for the domain $D$, which gives a significantly tighter lower bound $$\min_{(x,y)\in D}x^Ty\geq\max_{\eta_x\geq 0,\eta_y\geq 0,\eta_x\eta_y\geq 1}-\frac{\eta_x+\eta_y}{2}= -1.$$

Furthermore, in the case of softmax, can ellipsoidal constraints help capture the joint variation of the exponential terms, as well as the dependency between the numerator and the shared denominator?

Yes, the ellipsoidal domain can capture the joint variation introduced by softmax. The challenge is that our proposed method cannot be extended directly to softmax. Specifically, unlike inner product, softmax does not have a simple quadratic form. Therefore, we cannot derive a multivariate oracle in the same way as we did for the inner product. One viable extension is to decompose softmax into univariate operations. We leave the direct construction of linear bounding oracles for general multivariate activations to future work.

I’m not entirely satisfied with your response to Question 1. I’m not looking for a derivation of abstract symbols in a formula, but rather a concrete example, such as a small, clean matrix, to illustrate how your method would handle the ReLU under the perturbations you’re considering. What upper and lower bounds can be obtained? How does this compare to other methods? Additionally, I’d like the author to describe the underlying idea of the method from a high-level perspective, as well as explain why this method has advantages over others.

Methods such as CROWN construct their local linear relaxations of the activations over the entire preactivation box, in which it discards joint constraints/correlations between neurons. Our method provide a systematic way of combining quadratic relaxations of individual activations with ellipsoid constraints that couple the neurons, allowing us to construct tighter linear relaxations over the smaller feasible region. Below, we provide a simple illustrating example showing how quadratic activation bounds combine with a joint ellipsoid constraint could produce a tighter linear bound.

Example. Consider a two-neuron ReLU network

z=Wx,W=[111−1],f(x)=−ReLU(z1)−ReLU(z2),z=Wx,\qquad W=\begin{bmatrix} 1&1\\\\ 1&-1 \end{bmatrix},\qquad f(x)=-\text{ReLU}(z_1)-\text{ReLU}(z_2),

under the ℓ2\ell_2 input ball x12+x22≤1x_1^2+x_2^2\le1. We compare the linear lower bounds on f(x)f(x) obtained by CROWN and our method.

Since W⊤W=2IW^\top W=2I, the preactivations satisfy

z12+z22=2(x12+x22)≤2.z_1^2+z_2^2=2(x_1^2+x_2^2)\le2.

CROWN constructs its local activation relaxation over the preactivation ℓ∞\ell_\infty box [−2,2]2[-\sqrt2,\sqrt2]^2.

CROWN. CROWN relaxes the ReLU by using the upper chord on each preactivation interval,

ReLU(zi)≤12zi+22.\text{ReLU}(z_i)\le\frac12z_i+\frac{\sqrt2}{2}.

Negating and adding these bounds gives the affine lower bound

f(x)≥−12(z1+z2)−2=−x1−2.f(x)\ge-\frac12(z_1+z_2)-\sqrt2=-x_1-\sqrt2.

Our method. We consider a quadratic upper bound per neuron instead. We know

ReLU(t)≤(t+1)24,\text{ReLU}(t)\le\frac{(t+1)^2}{4},

which is valid for all real tt. Negating and adding the two quadratic bounds gives

f(x)≥−(z1+1)24−(z2+1)24=−12(z1+z2)−12−14(z12+z22).f(x) \ge-\frac{(z_1+1)^2}{4}-\frac{(z_2+1)^2}{4} =-\frac12(z_1+z_2)-\frac12-\frac14(z_1^2+z_2^2).

We now use the joint constraint z12+z22≤2z_1^2+z_2^2\le2 to bound the squared terms together. This produces the affine lower bound

f(x)≥−12(z1+z2)−1=−x1−1.f(x)\ge-\frac12(z_1+z_2)-1=-x_1-1.

This affine lower bound is strictly tighter than CROWN's because it has the same slope and a larger intercept. A visual illustration of this example is also included in the paper's Appendix F. This example uses one simple quadratic constraint. Our SDP formulation allows us to consider more general cases, combining multiple pairs of quadratic bounds, sector bounds, and ellipsoid constraints to further tighten the resulting linear bounds, while the underlying idea remains the same as in this example.

Reviewer_5NxCOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work extends semidefinite bound propagation (SDP-CROWN [1]), previously limited to ReLU networks, to general activations. Authors observe that the quadratic outer approximation of ReLU used in [1] combines sector bounds and quadratic bounds. For general activations, authors derive linear bounding oracles over ellipsoidal domains from each of these two families of quadratic constraints and combine them, recovering SDP-CROWN as a special case. The resulting linear bounds are integrated into the standard bound propagation recursion, and the ellipsoidal domains are refined recursively with the same framework. On the sigmoid, tanh, sine and GeLU feedforward networks from GenBaB [2] on MNIST and CIFAR-10, the proposed method obtains the highest verified accuracy in all benchmarks under both ℓ2\ell_2 and ℓ∞\ell_\infty perturbations, e.g., improving over GenBaB from 23% to 87% on CIFAR-10 under ℓ∞\ell_\infty perturbations.

[1] Chiu et al., SDP-CROWN: Efficient bound propagation for neural network verification with tightness of semidefinite programming, ICML 2025

[2] Shi et al., Neural network verification with branch-and-bound for general nonlinearities, TACAS 2025

Critical strengths
  • Principled generalization of SDP-CROWN: Authors identify that the quadratic outer approximation of ReLU used in [1] combines sector and quadratic bounds, and use this to extend semidefinite bound propagation to general activations, recovering SDP-CROWN as a special case. The resulting linear bounds integrate into the standard bound propagation recursion and bring benefits for both ℓ2\ell_2 and ℓ∞\ell_\infty perturbations, while [1] only showed benefits for ℓ2\ell_2.

  • Large improvements in verified accuracy: The proposed method obtains the highest verified accuracy in all 32 benchmarks, with the largest gains where linear relaxations are loose. For example, on the 4×200 and 4×500 sine networks under ℓ2\ell_2 perturbations, neither α-CROWN nor GenBaB [2] verify any instance, while the proposed method verifies 61 and 82, close to the PGD upper bounds of 78 and 85.

[1] Chiu et al., SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming, ICML 2025

[2] Shi et al., Neural Network Verification with Branch-and-Bound for General Nonlinearities, TACAS 2025

Critical weaknesses
  • Missing runtime and implementation details: The paper only reports verified accuracy under a 300-second timeout, without runtime or memory for any method. Since the main motivation of semidefinite bound propagation [1] is retaining the scalability of bound propagation, the cost of the method compared with α-CROWN and GenBaB [2] should be reported. Additionally, important details are missing: the number of sector and quadratic bounds per neuron and their anchors, the number of ellipsoids KK, the optimizer and number of iterations, and the branch-and-bound procedure used in "Ours". No code is provided, which makes the results hard to reproduce.

  • Missing comparison with SDP-CROWN and limited evaluation: The proposed method generalizes SDP-CROWN [1], which is recovered as a special case (Appendix D), while adding per-neuron multipliers, intersections of multiple ellipsoids and recursive ellipsoid refinement. However, the method is never evaluated on ReLU networks, so it is not compared against SDP-CROWN in the setting where both methods apply. Therefore, it is unclear whether the additional flexibility brings tighter bounds than SDP-CROWN on ReLU networks, e.g., on the ℓ2\ell_2 benchmarks of [1], and at what computational cost. Additionally, the introduction motivates the work with Transformers, recurrent networks and neural controllers, but the evaluation only covers small feedforward networks (MLPs of up to 9 layers or 500 neurons per layer, and ConvSmall) on MNIST and CIFAR-10, as the method does not support general computational graphs. Similarly, Appendix B.3 claims that multivariate operations such as softmax can be handled, but this is not evaluated. Additionally, PRIMA [3], which supports general activations with multi-neuron relaxations, is not included in the comparison.

[1] Chiu et al., SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming, ICML 2025

[2] Shi et al., Neural Network Verification with Branch-and-Bound for General Nonlinearities, TACAS 2025

[3] Müller et al., PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations, POPL 2022

Questions for authors
  • How does the proposed method compare with SDP-CROWN [1] on ReLU networks, e.g., on the ℓ2\ell_2 benchmarks of [1], in terms of verified accuracy and runtime? Showing improvements over SDP-CROWN in this setting would improve my assessment.

  • What is the runtime of the proposed method compared with α-CROWN and GenBaB [2], with and without branch-and-bound? How does it scale with the number of sector and quadratic bounds and the number of ellipsoids?

  • Clarification: Which number of sector and quadratic bounds, anchors and ellipsoids KK are used in the experiments, and which branch-and-bound procedure is used in "Ours"?

  • Can the method be applied to the non-feedforward models in the benchmark of GenBaB [2]? If not, what prevents it?

[1] Chiu et al., SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming, ICML 2025

[2] Shi et al., Neural Network Verification with Branch-and-Bound for General Nonlinearities, TACAS 2025

4 comments
AuthorsOpenReview ↗

Author Rebuttal (Part 1)

We thank the reviewers for their constructive feedback and for recognizing the key contributions of our paper. We address the primary concerns below and will incorporate these clarifications, alongside additional experimental results, into the final version of the manuscript.

How does the proposed method compare with SDP-CROWN [1] on ReLU networks, e.g., on the benchmarks of [1], in terms of verified accuracy and runtime? Showing improvements over SDP-CROWN in this setting would improve my assessment. Additionally, PRIMA [3], which supports general activations with multi-neuron relaxations, is not included in the comparison.

We added experiments against SDP-CROWN [1] on ReLU networks and against PRIMA [3]. We first evaluate our method on the same nine ReLU benchmarks as [1], with a 150 s timeout for all methods. Table 1 reports verified accuracy and runtime in parentheses. Our method improves verified accuracy on all nine benchmarks before branch-and-bound, with an average increase of 3.5 percentage points. This is consistent with the added flexibility of optimizing the slope g of the propagated linear bound.

Table 1: Comparison between ours and SDP-CROWN on Lipschitz regularized networks

ModelεOurs BaBOurs w/o BaBSDP-CROWN
MNIST MLP1.050.0(3.4s)44.0(1.8s)32.5(1.9s)
MNIST ConvSmall0.384.5(7.7s)83.0(7.6s)81.5(5.2s)
MNIST ConvLarge0.382.5(10.5s)80.0(8.2s)79.5(32.7s)
CIFAR CNN-A24/25553.5(15.0s)51.5(8.5s)49.0(4.8s)
CIFAR CNN-B24/25558.0(61.5s)54.0(58.7s)49.5(9.0s)
CIFAR CNN-C24/25545.5(8.6s)45.0(4.0s)42.5(4.8s)
CIFAR ConvSmall24/25551.0(10.8s)48.5(6.6s)43.5(3.9s)
CIFAR ConvDeep24/25549.0(13.0s)47.5(9.9s)45.5(11.2s)
CIFAR ConvLarge8/25570.0(14.3s)65.0(7.8s)63.5(38.5s)
Avg60.457.654.1

The networks in [1] were trained with Lipschitz regularization to keep weight matrices’ norms close to one. When layer norms are larger, forward propagation of a ball using layerwise Lipschitz bounds can yield loose preactivation sets. We therefore evaluate five additional ReLU benchmarks without this regularization, using the same 150 s timeout. Our method improves verified accuracy on all five benchmarks compared to SDP-CROWN, even with one ellipsoid and without BaB. Increasing the number of ellipsoids from one to five improves average verified accuracy from 47.9% to 58.0% without BaB and from 63.6% to 69.0% with BaB.

Table 2: Comparison between ours and SDP-CROWN on Non-Lipschitz regularized networks

ModelεOurs 5 ellipsoidsOurs 1 ellipsoidOurs 5 ellipsoids w/o BaBOurs 1 ellipsoid w/o BaBSDP-CROWN
MNIST NOR0.1593.0(44.8s)85.5(28.2s)76.0(37.7s)60.0(8.8s)42.0(8.4s)
MNIST ADV0.2593.5(43.8s)93.0(16.4s)83.0(37.6s)79.5(8.1s)33.0(7.8s)
CIFAR NOR8/25564.0(81.1s)60.0(40.1s)55.5(69.8s)47.0(10.3s)34.5(7.4s)
CIFAR CNN-A-Adv32/25550.0(101.5s)41.5(63.0s)37.0(89.1s)24.5(11.9s)9.0(8.0s)
CIFAR CNN-A-Adv432/25544.5(110.0s)38.0(50.9s)38.5(102.7s)28.5(11.3s)14.5(7.3s)
Avg69.063.658.047.926.6

Finally, we compare with PRIMA [3] on the six ℓ∞\ell_\infty benchmarks with sigmoid or tanh activations. These benchmarks are only evaluated benchmarks that are supported by PRIMA, which lacks support for ℓ2\ell_2 perturbations and for GELU and sine activations. We use the same 300 s timeout as in our reported experiments. Within this budget, PRIMA certifies no instances on these six benchmarks, while our method achieves 30–55% verified accuracy without BaB and 37–75% with BaB.

Table 3: Comparison with PRIMA

MethodSigmoid 4×100Sigmoid 4×500Sigmoid 6×100Sigmoid 6×200Tanh 4×100Tanh 6×100
PRIMA000000
Ours w/o BaB515353554930
Ours736775696837
AuthorsOpenReview ↗

Author Rebuttal (Part 2)

What is the runtime of the proposed method compared with α-CROWN and GenBaB [2], with and without branch-and-bound? How does it scale with the number of sector and quadratic bounds and the number of ellipsoids?

We now report verified accuracy and mean runtime for the experiments in Tables 1 and 2 of the paper, along with a fixed-iteration study of how runtime changes with the number of sector bounds, quadratic bounds, and ellipsoids.

Runtime compare to α-CROWN and GenBaB We used a 300 s timeout for all methods. Tables 4 and 5 report verified accuracy and mean runtime in seconds over all instances.

Table 4: Verified accuracy and mean runtime for the benchmarks in Table 1 of the paper

ActivationModelρUpper Bound (%)OursOurs w/o BaBα-CROWNGenBaB
MNIST
Sigmoid6×1000.28976(68.5s)68(36.2s)62(14.3s)68(80.7s)
6×2000.29880(88.6s)75(69.8s)64(16.0s)68(98.8s)
9×1000.2258957(133.6s)53(73.3s)41(47.2s)44(159.1s)
ConvSmall0.19857(223.2s)39(168.7s)6(3.0s)12(266.6s)
Tanh6×1000.0759784(51.4s)78(22.4s)77(9.4s)81(54.9s)
6×2000.059958(145.6s)53(103.7s)49(17.6s)56(138.2s)
9×1000.19863(126.1s)58(71.9s)54(32.4s)59(128.5s)
ConvSmall0.059819(279.4s)13(182.6s)0(2.9s)3(292.9s)
CIFAR-10
Sigmoid4×1000.27416(257.3s)3(33.9s)0(5.5s)2(294.7s)
4×5000.1759860(204.3s)43(144.1s)5(3.5s)12(265.8s)
6×1000.1758841(207.6s)27(80.8s)3(11.0s)28(225.1s)
6×2000.1759153(199.9s)45(140.3s)13(10.3s)31(212.9s)
Tanh4×1000.159964(130.6s)50(30.9s)20(4.4s)47(170.7s)
6×1000.110081(81.1s)71(26.0s)48(5.9s)64(119.8s)
Sine4×1000.26856(89.5s)44(36.9s)0(7.4s)16(255.6s)
4×2000.27861(129.0s)54(78.3s)0(7.4s)0(300.6s)
4×5000.28582(183.1s)77(178.5s)0(7.5s)0(300.6s)
GeLU4×1000.36015(242.1s)6(38.9s)3(8.6s)10(256.4s)
4×2000.29546(187.9s)30(70.2s)15(8.4s)30(213.3s)
4×5000.29531(240.6s)23(143.6s)10(5.4s)22(238.1s)

Table 5: Verified accuracy and mean runtime for the benchmarks in Table 2 of the paper

MethodSigmoid 4×100Sigmoid 4×500Sigmoid 6×100Sigmoid 6×200Tanh 4×100Tanh 6×100Sine 4×100Sine 4×200Sine 4×500GeLU 4×100GeLU 4×200GeLU 4×500
α-CROWN28(10.6s)16(3.3s)43(8.0s)39(8.4s)25(4.0s)6(10.3s)4(6.8s)2(7.0s)4(4.6s)49(6.6s)40(7.7s)33(4.3s)
GenBaB61(134.2s)25(230.6s)64(121.3s)50(156.6s)54(152.1s)19(254.3s)59(140.3s)35(201.9s)23(239.0s)81(75.8s)67(114.3s)40(183.6s)
Ours w/o BaB51(36.7s)53(136.6s)53(46.1s)55(88.3s)49(32.6s)30(81.4s)81(42.8s)82(77.1s)85(141.8s)72(22.3s)62(54.5s)42(112.8s)
Ours73(111.6s)67(182.8s)75(114.4s)69(142.7s)68(123.4s)37(218.6s)81(91.7s)84(113.4s)87(162.1s)89(59.6s)76(108.9s)49(182.0s)

Time scaling with number of sector/quadratic bounds/ellipsoids

Each additional sector bound introduces three scalar parameters per neuron, and each additional pair of lower and upper quadratic bounds introduces two nonnegative multipliers per neuron. Each additional ellipsoid introduces one nonnegative multiplier shared across the layer, with one contribution to the curvature constraint for each neuron. The time for one backward bound pass thus grows linearly with the number of sector/quadratic bounds and ellipsoids. To measure the runtime concretely, we varied one component at a time and timed bound computation before BaB using the same number of optimization steps. Table 6 reports the runtime and the resulting lower bound for each setting.

tanh 6×100: time / bound changesigmoid 4×500: time / bound change
sectors 1→818.4→19.7s / −1.11→−0.9919.5→38.5s / −1.84→−1.47
quadratic bounds 0→818.4→21.0s / −1.11→−0.8419.5→40.4s / −1.84→−1.08
ellipsoids 1→1018.4→22.2s / −1.11→−1.0619.5→24.5s / −1.84→−1.72
AuthorsOpenReview ↗

Author Rebuttal (Part 3)

Clarification: Which number of sector and quadratic bounds, anchors and ellipsoids are used in the experiments, and which branch-and-bound procedure is used in "Ours"?

We tuned the number of sector bounds, quadratic bound pairs, and ellipsoids to balance runtime and bound tightness. As the results above show, adding constraints can tighten the bound at the cost of additional computation. For most benchmarks, we used 8 sector bounds and 8 pairs of quadratic bounds per neuron, and 10 ellipsoids per layer. The exceptions were: MNIST Sigmoid 6×200 and Tanh 9×100. We used 4 sector bounds per neuron, which gave a better tradeoff between runtime and tightness. MNIST Tanh 6×200 and the Sigmoid 4×100 benchmark under ℓ∞\ell_\infty perturbations. We used 8 sector bounds and 16 pairs of quadratic bounds per neuron, and 5 ellipsoids per layer. The two ConvSmall networks. To reduce GPU memory usage, we used 1 sector bound and 4 pairs of quadratic bounds per neuron, and 5 ellipsoids per layer.

Ours branch-and-bound follows GenBaB's branch-and-bound procedure (BBPS branching, branching points) and replaces only the bounding of each subproblem by SDP-CROWN. A split enters the SDP as one more constraint with its own multiplier β≥0\beta ≥ 0, as in GenBaB, optimized jointly with the other multipliers and warm-started from the parent. The child also rebuilds the constraints (quadratic and sector bounds) of the split neuron on its narrower interval.

Can the method be applied to the non-feedforward models in the benchmark of GenBaB [2]? If not, what prevents it?

Our proposed method is compatible with general computational graphs as long as all the nonlinearities inside could be supported. The previous lack of support was due to limitations of our current implementation. During the rebuttal period, we implemented the subroutine necessary for our method to support general computational graphs. We provide some results for the LSTM models used in the GenBaB paper. We can see that our methods beat GenBaB already before any branch-and-bound. We will continue to work on supporting general computational graphs and add more results.

ModelUpper Bound (%)OursOurs w/o BaBα-CROWNGenBaB
LSTM-4-3210095(49.7s)90(37.4s)64(33.4s)78(86.4s)
LSTM-4-6410077(103.8s)71(56.5s)48(44.2s)62(147.7s)

Thanks for the additional results, I have increased my score.

Reviewer_FE2oOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper extends the SDP-CROWN method from ReLU to general activations functions by building sector and quadratic envelopes, from which SDP-based bounds are derived and propagated in a CROWN-like fashion. Experiments on GenBaB’s feedforward benchmarks show large gains over α-CROWN and GenBaB under both ℓ2 and ℓ∞ perturbations.

Critical strengths

The proposed approach allows to handle non-convex quadratic outer-bounding inequalities via an SDP relaxation of said quadratic. This opens up an avenue to improve verification of general activation neural networks at scale.

Numerical results show consistent improved performance on a range of test cases, albeit limited to feed-forward networks.

Critical weaknesses

Several claimed methodological contributions intersect with prior work by Fazlyab et al, Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming. Please provide a clearer positioning of the paper and its contribution agains this reference.

While the methodology is sound, it is not clear from the paper how to derive sector and quadratic bounds for general functions (if possible at all), additional details and guidance would be valuable.

Questions for authors
  • Figure 1(f) appears to show two quadratic curves?
  • Under which conditions are sector bounds valid? Given a general function ff, how can one construct sector bounds systematically?
  • Please provide more details regarding the computed sector slopes and quadratic coefficients (Eqs. 14–15, App. B.2) when dealing with over-approximations for non-monotone or non-convex activations functions
3 comments
AuthorsOpenReview ↗

Author Rebuttal (Part 1)

Several claimed methodological contributions intersect with prior work by Fazlyab et al. Please provide a clearer positioning of the paper and its contribution agains this reference.

We thank the reviewer for highlighting this connection. The central contribution of our paper is to utilize SDP relaxation to derive novel linear bounding oracles for sector bounded and quadratic bounded activations. The linear bounding oracles can fit into $\alpha,\beta$-CROWN infrastructure, enabling GPU-accelerated optimization and refinement through branch-and-bound.

Our sector-bound construction also uses a different SDP formulation. For simplicity, consider a sector anchored at the origin with $\sigma(0)=0$. Fazlyab et al. derive the SDP relaxation through the quadratic constraint: $$

σ(z)−A‾z\sigma(z)-\underline Az σ(z)−A‾z\sigma(z)-\overline Az

\leq 0.$$ In Appendix A.1, we propose to derive SDP relaxation on its equivalent absolute-split representation: $$\frac{\overline A+\underline A}{2}z-\frac{\overline A-\underline A}{2}|z| \leq \sigma(z) \leq \frac{\overline A+\underline A}{2}z+\frac{\overline A-\underline A}{2}|z|.$$ The resulting SDP relaxation has a sparse structure that enables us to derive linear bounding oracles compatible with the $\alpha,\beta$-CROWN infrastructure. Thus, one of our technical contributions is exploiting this structure to enable efficient optimization and scalable bound propagation.

On the other hand, Fazlyab et al. proposed a methodology for deriving SDP relaxations for general activation functions. Their formulation does not necessarily have the sparse structure used to derive the linear bounding oracles in our paper. However, their framework can accommodate more general quadratic outer approximations, including the sector and quadratic bounds in our paper. We will clarify these distinctions in the final version.

Figure 1(f) appears to show two quadratic curves?

Yes, Figure 1(f) shows one pair of quadratic bounds: an upper bound that captures the activations curvature near $(z=-1.5)$, and a lower bound chosen to be nearly linear.

AuthorsOpenReview ↗

Author Rebuttal (Part 2)

Under which conditions are sector bounds valid? Given a general function , how can one construct sector bounds systematically? Please provide more details regarding the computed sector slopes and quadratic coefficients (Eqs. 14–15, App. B.2) when dealing with over-approximations for non-monotone or non-convex activations functions

We thank the reviewer for pointing out this ambiguity. We have revised Appendix B in our paper to include more details on the construction of sector and quadratic bounds. We address the reviewer’s question below.

For a general activation $\sigma(z)$, a sector bound with anchor $\tilde z$ is valid within an interval $

z‾,z‾\underline z,\overline z

$ if $$\underline A\leq\frac{\sigma(z)-\sigma(\tilde z)}{z-\tilde z}\leq \overline A\quad\text{for all }z\in

z‾,z‾\underline z,\overline z

\setminus\tilde z.$$ Hence, the best choice of $\underline A$ is given by equation 14: $$\underline A=\inf_{z\in

z‾,z‾\underline z,\overline z

\setminus\tilde z}\phi(z)=\frac{\sigma(z)-\sigma(\tilde z)}{z-\tilde z}.$$ We focus on describing how to compute $\underline A$ systematically; the construction for $\overline A$ is similar. Any minimizer for $\phi(z)$ must satisfy the necessary conditions $$\begin{cases}f(z)=\sigma'(z)(z-\tilde z) - \sigma(z) + \sigma(\tilde z)=0,\\ f'(z)=\sigma''(z)(z-\tilde z)\geq 0.\end{cases}$$ To identify candidate minimizers, we find $z$ such that $f(z)=0$ within intervals on which $f'(z)\geq 0$. On each of those interval, $f(z)$ is monotone, candidate minimizer is the unique root of $f(z)=0$ whenever $f(z)$ crosses zero on the interval. Finally, $\underline A$ is obtained by evaluating $\phi(z)$ at the candidate minimizers and intervals' boundary points and taking the minimum.

Consider an example of constructing a sector bound for $\sigma(z)=z^3-z$ within $[-2,2]$, with anchor $\tilde z=1$. Note that $\sigma(z)$ is non-monotone and non-convex. In this case, $\underline A=\inf_{z\in[-2,2]}\phi(z)=z^2+z$ and candidate minimizers satisfy the following necessary condition $$\begin{cases}f(z)=(z-1)^2(2z+1)=0,\\ f'(z)=6z(z-1)\geq 0.\end{cases}$$ Here, $f'(z)\geq 0$ on two intervals $[-2,0]\cup [1,2]$, and $f(z)=0$ at $z=-0.5$ and $z=1$ for respective interval. The candidate minimizers are $z=\{-0.5,1\}$ and the intervals' boundary points are $z=\{-2,0,1,2\}$. Hence, $$\underline A = \min\{\phi(-2),\phi(-0.5),\phi(0),\phi(1),\phi(2)\}=\phi(-0.5)=-1/4.$$
This construction is efficient for activations with few curvature sign changes, which holds for the activations considered in our paper. For highly irregular functions, this construction may be less efficient, although we expect commonly used activations to have simpler curvature patterns.

The construction of the coefficients for quadratic bounds is similar. For fixed $\underline C$ and $\underline P$, the best choice of $\underline Q$ is given by Equation 15: $$\underline Q = \inf_{z\in

z‾,z‾\underline z,\overline z

}\psi(z)=\sigma(z)-\frac{1}{2}\underline Cz^2-\underline Pz.$$ Any minimizer for $\psi(z)$ must satisfy the necessary conditions $$\begin{cases}g(z)=\sigma'(z) - \underline Cz-\underline P=0,\\ g'(z)=\sigma''(z) - \underline C\geq 0.\end{cases}$$ We identify candidate minimizers by finding roots of $g(z)=0$ within intervals on which $g'(z)\geq0$. Then $\underline Q$ is the minimum of $\psi(z)$ evaluated at these candidates and the interval boundaries.

Reviewer_FE2oOpenReview ↗

Answer acknowledgement

I thank the authors for their response, and I appreciate the additional information regarding the computation of sector & quadratic bounds for general activation functions.

Re-Figure 1: I find the figure a visually heavy (especially 1f - 1h); I would suggest moving/adding detailed graphs to the appendix where visibility can be improved by enlarging the plots.

I maintain my score because this paper's contribution centers on the derivation of quadratic outer-approximations and experiments., while the core methodological contribution (SDP relaxation & bound propagation) is in previous work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.