arXiv:2506.10269cs.LGmath.OC2025-06

发现深度神经网络验证中SDP求解的可行性崩溃问题,提出有效解决方案。

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

  • 提出五种增强SDP可行性条件的方法,解决深层网络验证难题。
  • 新方法使88%原不可解问题可解,覆盖总量41%。
  • 揭示传统上下界约束反噬可行性,为优化提供理论依据。

半定规划(SDP)松弛已成为神经网络验证的有力工具,相较于其他凸松弛方法,对带ReLU激活函数的深度神经网络(DNN)能提供更紧的界。然而,我们发现当应用于深层网络时,该方法存在关键缺陷:内点消失问题,导致严格可行性丧失——这是保证SDP数值稳定性和最优性的必要条件。通过严格的理论与实证分析,我们证明随着网络深度增加,严格可行性极可能被破坏,形成制约基于SDP验证扩展的根本障碍。针对此问题,我们设计并评估了五种改进方案,显著提升可行性条件。所提方法成功解决了88%原有无法求解的问题,占总数的41%。分析还显示,传统上继承自先前工作的每个ReLU单元的上下界约束,并无坚实依据,反而损害问题的可行性。本工作揭示了基于SDP的DNN验证中的根本挑战,提供了切实可行的改进路径,助力构建更可靠、安全的深度神经网络系统。

原文摘要 · Abstract (English)

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.

神经网络验证半定规划ReLU网络可行性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。