Authors: Simon Kuang, Yuezhu Xu, S. Sivaranjani, Xinfan Lin
Organizations: Department of Mechanical and Aerospace Engineering University of California, Davis · Edwardson School of Industrial Engineering Purdue University
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.
Figures & tables
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
λ
Train Loss
Test Loss
Train Acc.
Test Acc.
0
1.0×10−4
0.4661
1.000
0.933
10−2
0.0542
0.0932
0.983
0.967
Appendix
Table D.1 : Iris experiment: final predictive performance after 20,000 steps.
λ
K (upper)
K/(2κ(W))
L
K/L
0
179.21
25.04
105.74
1.69
10−2
5.84
0.82
5.84
1.00
Appendix
Table D.2 : Iris experiment: 2-norm Lipschitz upper bound K versus lower bounds. Here K/(2κ(W)) is the guaranteed lower bound from Theorem 3.1 , while L is an empirical lower bound from local optimization of the Lipschitz ratio over input pairs.
Figure D.1 : Iris experiment: training curves for λ=0 (left) and λ=10−2 (right). Shaded area indicates the gap between theoretical upper and lower bounds on the Lipschitz constant.
Figure D.2 : Iris experiment: decision boundaries in 2D principal component planes for λ=0 . (Training data)
Figure D.3 : Iris experiment: decision boundaries in 2D principal component planes for λ=10−2 . (Training data)
lower bound L
ECLipsE
trivial
trivial/ L
ECLipsE/ L
no penalty
19.59
6755.76
30060.89
1534.34
344.82
penalty λ=10−6
14.74
130.19
218.58
14.83
8.83
Appendix
Table F.1 : Lipschitz upper and lower bounds on a 3-layer ReLU MNIST network initialized with an adversarial dead neuron.
config
λ
train loss
test loss
train acc.
test acc.
ReLU
0
0.0136
0.0696
0.9953
0.9754
ReLU
10−2
0.0302
0.0596
0.9919
0.9809
Cos/Sin
10−2
0.0180
0.0517
0.9959
0.9826
Appendix
Table G.1 : MNIST three-way comparison: final predictive performance after 20 epochs.
config
λ
K
K time
L
L time
K/L
ReLU
0
605.171
0.03s
48.014
2.88s
12.60
ReLU
10−2
3.314
0.02s
2.614
1.96s
1.27
Cos/Sin
10−2
3.741
0.02s
3.082
8.16s
1.21
Appendix
Table G.2 : MNIST three-way comparison: trivial Lipschitz upper bound K , empirical lower bound L , computation times, and upper-to-lower ratio.