Interior-Point Vanishing Problem in Semidefinite Relaxations for Neural Network Verification

• URL: http://arxiv.org/abs/2506.10269v1
• Date: Thu, 12 Jun 2025 01:25:21 GMT
• Title: Interior-Point Vanishing Problem in Semidefinite Relaxations for Neural Network Verification
• Authors: Ryota Ueda, Takami Sato, Ken Kobayashi, Kazuhide Nakata,
• Abstract summary: Semidefinite programming (SDP) relaxation has emerged as a promising approach for neural network verification.<n>We identify a critical limitation in the SDP relaxation when applied to deep networks: interior-point vanishing.<n>We investigate five solutions to enhance the feasibility conditions of the verification problem.
• Score: 9.063592930122113
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semidefinite programming (SDP) relaxation has emerged as a promising approach for neural network verification, offering tighter bounds than other convex relaxation methods for deep neural networks (DNNs) with ReLU activations. However, we identify a critical limitation in the SDP relaxation when applied to deep networks: interior-point vanishing, which leads to the loss of strict feasibility -- a crucial condition for the numerical stability and optimality of SDP. Through rigorous theoretical and empirical analysis, we demonstrate that as the depth of DNNs increases, the strict feasibility is likely to be lost, creating a fundamental barrier to scaling SDP-based verification. To address the interior-point vanishing, we design and investigate five solutions to enhance the feasibility conditions of the verification problem. Our methods can successfully solve 88% of the problems that could not be solved by existing methods, accounting for 41% of the total. Our analysis also reveals that the valid constraints for the lower and upper bounds for each ReLU unit are traditionally inherited from prior work without solid reasons, but are actually not only unbeneficial but also even harmful to the problem's feasibility. This work provides valuable insights into the fundamental challenges of SDP-based DNN verification and offers practical solutions to improve its applicability to deeper neural networks, contributing to the development of more reliable and secure systems with DNNs.

Related papers

• Enhancing Uncertainty Estimation and Interpretability via Bayesian Non-negative Decision Layer [55.66973223528494]
  We develop a Bayesian Non-negative Decision Layer (BNDL), which reformulates deep neural networks as a conditional Bayesian non-negative factor analysis.<n>BNDL can model complex dependencies and provide robust uncertainty estimation.<n>We also offer theoretical guarantees that BNDL can achieve effective disentangled learning.
  arXiv  Detail & Related papers  (2025-05-28T10:23:34Z)
• Peeking Behind the Curtains of Residual Learning [10.915277646160707]
  "The Plain Neural Net Hypothesis" (PNNH) identifies the internal path across non-linear layers as the most critical part in residual learning. We thoroughly evaluate PNNH-enabled CNN architectures and Transformers on popular vision benchmarks, showing on-par accuracy, up to 0.3% higher training throughput, and 2x better parameter efficiency compared to ResNets and vision Transformers.
  arXiv  Detail & Related papers  (2024-02-13T18:24:10Z)
• Scalable and Efficient Methods for Uncertainty Estimation and Reduction in Deep Learning [0.0]
  This paper explores scalable and efficient methods for uncertainty estimation and reduction in deep learning. We tackle the inherent uncertainties arising from out-of-distribution inputs and hardware non-idealities. Our approach encompasses problem-aware training algorithms, novel NN topologies, and hardware co-design solutions.
  arXiv  Detail & Related papers  (2024-01-13T19:30:34Z)
• Enumerating Safe Regions in Deep Neural Networks with Provable Probabilistic Guarantees [86.1362094580439]
  We introduce the AllDNN-Verification problem: given a safety property and a DNN, enumerate the set of all the regions of the property input domain which are safe. Due to the #P-hardness of the problem, we propose an efficient approximation method called epsilon-ProVe. Our approach exploits a controllable underestimation of the output reachable sets obtained via statistical prediction of tolerance limits.
  arXiv  Detail & Related papers  (2023-08-18T22:30:35Z)
• OccRob: Efficient SMT-Based Occlusion Robustness Verification of Deep Neural Networks [7.797299214812479]
  Occlusion is a prevalent and easily realizable semantic perturbation to deep neural networks (DNNs) It can fool a DNN into misclassifying an input image by occluding some segments, possibly resulting in severe errors. Most existing robustness verification approaches for DNNs are focused on non-semantic perturbations.
  arXiv  Detail & Related papers  (2023-01-27T18:54:00Z)
• The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networks [94.63547069706459]
  #DNN-Verification problem involves counting the number of input configurations of a DNN that result in a violation of a safety property. We propose a novel approach that returns the exact count of violations. We present experimental results on a set of safety-critical benchmarks.
  arXiv  Detail & Related papers  (2023-01-17T18:32:01Z)
• Measurement-Consistent Networks via a Deep Implicit Layer for Solving Inverse Problems [0.0]
  End-to-end deep neural networks (DNNs) have become state-of-the-art (SOTA) for solving inverse problems. These networks are sensitive to minor variations in the training pipeline and often fail to reconstruct small but important details. We propose a framework that transforms any DNN for inverse problems into a measurement-consistent one.
  arXiv  Detail & Related papers  (2022-11-06T17:05:04Z)
• Can pruning improve certified robustness of neural networks? [106.03070538582222]
  We show that neural network pruning can improve empirical robustness of deep neural networks (NNs) Our experiments show that by appropriately pruning an NN, its certified accuracy can be boosted up to 8.2% under standard training. We additionally observe the existence of certified lottery tickets that can match both standard and certified robust accuracies of the original dense models.
  arXiv  Detail & Related papers  (2022-06-15T05:48:51Z)
• 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)
• Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks [64.23331120621118]
  We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs) INNs are a class of implicit learning models that use implicit equations as layers. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs.
  arXiv  Detail & Related papers  (2022-04-01T03:31:27Z)
• A Unified View of SDP-based Neural Network Verification through Completely Positive Programming [27.742278216854714]
  We develop an exact, convex formulation of verification as a completely positive program ( CPP) We provide analysis showing that our formulation is minimal -- the removal of any constraint fundamentally misrepresents the neural network computation.
  arXiv  Detail & Related papers  (2022-03-06T19:23:09Z)
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks [54.27962244835622]
  This paper proposes a new mean-field framework for over- parameterized deep neural networks (DNNs) In this framework, a DNN is represented by probability measures and functions over its features in the continuous limit. We illustrate the framework via the standard DNN and the Residual Network (Res-Net) architectures.
  arXiv  Detail & Related papers  (2020-07-03T01:37:16Z)

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.