- 论文公开站arXiv
输入凸神经网络L_p-Lipschitz常数的参数化复杂度及Zonotopes上L_p-范数最大化
Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
摘要显示，该研究探讨了两层输入凸神经网络（ICNNs）计算L_p-Lipschitz常数的问题，该问题等价于在Zonotope上最大化对偶范数。对于固定的p∈(1,∞)∩Q，在d维Zonotope上最大化L_p-范数是W[1]-难的，且暴力枚举算法在指数时间假设下本质最优。通过二元性，相同难度适用于两层ReLU ICNN的L_p-Lipschitz常数计算。证明先建立L_2情形，再通过泰勒近似推广至任意固定p。该结果解决了COLT'25…
意义：该研究明确了ICNN Lipschitz常数计算的计算复杂性边界，对神经网络的鲁棒性验证和安全性分析有重要指导意义，也为相关算法设计提供了理论依据。