SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming

• URL: http://arxiv.org/abs/2506.06665v1
• Date: Sat, 07 Jun 2025 05:06:07 GMT
• Title: SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming
• Authors: Hong-Ming Chiu, Hao Chen, Huan Zhang, Richard Y. Zhang,
• Abstract summary: We propose SDP-CROWN, a novel hybrid verification framework.<n>SDP-CROWN combines the tightness of SDP relaxations with the scalability of bound-propagation verifiers.<n>We observe markedly improved verification performance on large models with up to 65 thousand neurons and 2.47 million parameters.
• Score: 19.728899459582276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural network verifiers based on linear bound propagation scale impressively to massive models but can be surprisingly loose when neuron coupling is crucial. Conversely, semidefinite programming (SDP) verifiers capture inter-neuron coupling naturally, but their cubic complexity restricts them to only small models. In this paper, we propose SDP-CROWN, a novel hybrid verification framework that combines the tightness of SDP relaxations with the scalability of bound-propagation verifiers. At the core of SDP-CROWN is a new linear bound, derived via SDP principles, that explicitly captures $\ell_{2}$-norm-based inter-neuron coupling while adding only one extra parameter per layer. This bound can be integrated seamlessly into any linear bound-propagation pipeline, preserving the inherent scalability of such methods yet significantly improving tightness. In theory, we prove that our inter-neuron bound can be up to a factor of $\sqrt{n}$ tighter than traditional per-neuron bounds. In practice, when incorporated into the state-of-the-art $\alpha$-CROWN verifier, we observe markedly improved verification performance on large models with up to 65 thousand neurons and 2.47 million parameters, achieving tightness that approaches that of costly SDP-based methods.

Related papers

• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Scalable Neural Network Kernels [22.299704296356836]
  We introduce scalable neural network kernels (SNNKs), capable of approximating regular feedforward layers (FFLs) We also introduce the neural network bundling process that applies SNNKs to compactify deep neural network architectures. Our mechanism provides up to 5x reduction in the number of trainable parameters, while maintaining competitive accuracy.
  arXiv  Detail & Related papers  (2023-10-20T02:12:56Z)
• Quantized Distributed Training of Large Models with Convergence Guarantees [34.054462975511996]
  We present QSDP, a variant of FSDP which supports both quant and weight gradientization with theoretical guarantees. We show that QSDP preserves accuracy, while completely removing the communication of FSDP, providing the speed-to-endups of up to 2.2x.
  arXiv  Detail & Related papers  (2023-02-05T14:20:55Z)
• Direct Parameterization of Lipschitz-Bounded Deep Networks [3.883460584034766]
  This paper introduces a new parameterization of deep neural networks (both fully-connected and convolutional) with guaranteed $ell2$ Lipschitz bounds. The Lipschitz guarantees are equivalent to the tightest-known bounds based on certification via a semidefinite program (SDP) We provide a direct'' parameterization, i.e., a smooth mapping from $mathbb RN$ onto the set of weights satisfying the SDP-based bound.
  arXiv  Detail & Related papers  (2023-01-27T04:06:31Z)
• Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Nets [57.06026574261203]
  We provide theoretical evidence for learning low-dimensional state spaces, which can also model long-term memory. Experiments corroborate our theory, demonstrating extrapolation via learning low-dimensional state spaces with both linear and non-linear RNNs.
  arXiv  Detail & Related papers  (2022-10-25T14:45:15Z)
• Chordal Sparsity for SDP-based Neural Network Verification [1.9556053645976446]
  We focus on improving semidefinite programming (SDP) based techniques for neural network verification. By leveraging chordal sparsity, we can decompose the primary computational bottleneck of DeepSDP into an equivalent collection of smaller LMIs. We show that additional analysis of Chordal-DeepSDP allows us to further rewrite its collection of LMIs in a second level of decomposition.
  arXiv  Detail & Related papers  (2022-06-07T17:57:53Z)
• Generalization Error Bounds for Deep Neural Networks Trained by SGD [3.148524502470734]
  Generalization error bounds for deep trained by gradient descent (SGD) are derived. The bounds explicitly depend on the loss along the training trajectory. Results show that our bounds are non-vacuous and robust with the change of neural networks and network hypers.
  arXiv  Detail & Related papers  (2022-06-07T13:46:10Z)
• Towards Evaluating and Training Verifiably Robust Neural Networks [81.39994285743555]
  We study the relationship between IBP and CROWN, and prove that CROWN is always tighter than IBP when choosing appropriate bounding lines. We propose a relaxed version of CROWN, linear bound propagation (LBP), that can be used to verify large networks to obtain lower verified errors.
  arXiv  Detail & Related papers  (2021-04-01T13:03:48Z)
• Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Verification [151.62491805851107]
  We develop $beta$-CROWN, a bound propagation based verifier that can fully encode per-neuron splits. $beta$-CROWN is close to three orders of magnitude faster than LP-based BaB methods for robustness verification. By terminating BaB early, our method can also be used for incomplete verification.
  arXiv  Detail & Related papers  (2021-03-11T11:56:54Z)
• Adaptive Subcarrier, Parameter, and Power Allocation for Partitioned Edge Learning Over Broadband Channels [69.18343801164741]
  partitioned edge learning (PARTEL) implements parameter-server training, a well known distributed learning method, in wireless network. We consider the case of deep neural network (DNN) models which can be trained using PARTEL by introducing some auxiliary variables.
  arXiv  Detail & Related papers  (2020-10-08T15:27:50Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)
• Deep Latent-Variable Kernel Learning [25.356503463916816]
  We present a complete deep latent-variable kernel learning (DLVKL) model wherein the latent variables perform encoding for regularized representation. Experiments imply that the DLVKL-NSDE performs similarly to the well calibrated GP on small datasets, and outperforms existing deep GPs on large datasets.
  arXiv  Detail & Related papers  (2020-05-18T05:55:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.