揭示神经网络Lipschitz验证的根源困境,指出其本质是不可达状态判定难题。
Demystifying Lipschitz verification: positive matrices, negative results
- 从隐藏状态可达性角度解释验证困难,该问题本质为NP难
- 证明SDP方法无法避免与简单乘积界相同的多项式保守性缺陷
- 提出通过参数正则化和三角层结构可使简单界变紧,适合理论研究者
神经网络的全局Lipschitz常数与鲁棒性和泛化能力相关,但不像经典模型那样能直接从参数读出。这催生了基于增量二次约束的半定规划(SDP)等复杂验证算法,以改进快速但常松散的逐层乘积界(平凡界)。我们追问:为何验证本身是个难题?答案在于结构性障碍——估计Lipschitz常数需知哪些隐藏状态可达,而可达性是NP难的。若P≠NP,则可达性构成多项式时间算法的屏障。通过显式构造,我们表明这种盲点会导致基于SDP的界继承与平凡界相同的定性失败,包括但不限于每层多项式保守性。这些困难并非仅存在于最坏情况的计算归约中,而是真实影响所有验证实例。因此SDP不足以实现可靠验证。我们还论证其非必要性:平凡界的一些失效源于可移除的参数化病态,可通过优化或正则化平凡界本身缓解。我们以‘球形牛’线性模型和数值实验验证此观点。尽管主贡献为理论性负面结果,我们最终提出一种无需偏置的新型三角函数层,结合平凡界正则化,使其在理论上和实践中均可被证明为紧致。
原文摘要 · Abstract (English)
The global Lipschitz constant of a neural network is related to robustness and generalization, yet unlike in many classical models, it is not plainly legible from the parameters. This has motivated sophisticated verification algorithms, especially semidefinite programming (SDP) based on incremental quadratic constraints on the activation functions, to improve on the fast but often loose product of layerwise Lipschitz constants (the trivial bound). We ask why Lipschitz verification is a problem in the first place. Our answer is that the difficulty is structural: estimating a network's Lipschitz constant requires knowing which hidden states are reachable, and reachability is NP-hard. If P!=NP, then reachability is a barrier to any polynomial-time algorithm. Through explicit constructions, we show that this blindness can force SDP-based bounds to inherit the same qualitative failures as the trivial bound, including but not limited to polynomial per-layer conservatism. We show that the difficulties of NP-hard questions are not isolated to worst-case computational reductions, but actually afflict every instance of the verification problem. Thus SDP is not sufficient for Lipschitz verification. We also argue that it is not necessary: several apparent failures of the trivial bound arise from removable parameterization pathologies, and can be mitigated by optimizing or regularizing the trivial bound itself. We demonstrate this claim via a "spherical cow" linear model and numerical proofs of concept. While the main contribution is theoretical and negative, we finally motivate a novel form of trigonometric layers that do not need biases for universal approximation. Combined with trivial bound regularization, they make the trivial bound provably and practically tight.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。