- 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 and perturbations. Under a unified time constraint, the complete method achieves higher verified accuracy than α-CROWN and GenBaB across the reported benchmarks.
Critical strengths
-
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.
-
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
-
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.
-
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?
-
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?
-
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
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.
| Model | Upper Bound (%) | Ours | Ours w/o BaB | α-CROWN | GenBaB |
|---|---|---|---|---|---|
| LSTM-4-32 | 100 | 90(64.4s) | 90(45.9s) | 64(33.4s) | 78(86.4s) |
| LSTM-4-64 | 100 | 71(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 , for which sector and quadratic bounds can be constructed.
Our proposed method cannot be extended directly to multivariate activation functions 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 . 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
under the input ball . We compare the linear lower bounds on obtained by CROWN and our method.
Since , the preactivations satisfy
CROWN constructs its local activation relaxation over the preactivation box .
CROWN. CROWN relaxes the ReLU by using the upper chord on each preactivation interval,
Negating and adding these bounds gives the affine lower bound
Our method. We consider a quadratic upper bound per neuron instead. We know
which is valid for all real . Negating and adding the two quadratic bounds gives
We now use the joint constraint to bound the squared terms together. This produces the affine lower bound
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.
Author Rebuttal (Part 1)
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$.
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 is approximately linear on the interval [−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], leaving more room for additional quadratic constraints to improve the bound.