입력 볼록 신경망의 $L_p$-립시츠 상수와 조노토프 위 $L_p$-노름 최대화의 매개변수화된 복잡도
Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
한국어 초록
립시츠 상수(Lipschitz constant)는 입력의 작은 섭동에 대한 신경망의 민감도를 정량화하는 표준적인 방법이지만, 얕은 ReLU 네트워크에 대해서조차 이를 계산하는 것은 어렵다. 본 연구에서는 음이 아닌 출력 가중치로 볼록성을 강제하는 제한된 아키텍처인 2층 입력 볼록 신경망(input-convex neural network, ICNN)에 대해 이 문제를 연구한다. 이러한 네트워크의 $L_p$-립시츠 상수를 계산하는 것은 조노토프(zonotope) 위에서 쌍대 노름(dual norm)을 최대화하는 것과 동치이다. 조노토프 위의 $L_1$-노름 및 $L_\infty$-노름 최대화는 각각 고정 매개변수 알고리즘과 다항 시간 알고리즘이 존재하지만, 나머지 $L_p$-노름의 매개변수화된 복잡도는 미해결 문제였다. 본 논문은 모든 고정된 $p\in (1,\infty)\cap \mathbb{Q}$에 대해, $\mathbb{R}^d$의 조노토프 위에서 $L_p$-노름을 최대화하는 문제가 차원 $d$에 대해 W[1]-난해(W[1]-hard)임을 증명한다. 더 나아가, 본 논문의 난해성 결과는 지수 시간 가설(Exponential Time Hypothesis) 하에서 이 문제에 대해 전수 탐색(brute-force enumeration) 알고리즘이 본질적으로 최적임을 함의한다. 쌍대성에 의해, 2층 ReLU ICNN의 $L_p$-립시츠 상수를 계산하는 문제에도 동일한 난해성 결과가 성립한다. 증명은 먼저 $L_2$-노름에 대한 결과를 확립한 뒤, 적절한 테일러 근사(Taylor approximation)를 사용하여 그 구성을 임의의 고정된 $p\in (1,\infty)\cap\mathbb{Q}$로 확장한다. 이러한 결과는 조노토프 노름 최대화 및 2층 ICNN 립시츠 상수의 매개변수화된 복잡도 지위에 관한 해당 문제들을 해결한다. 본 논문은 COLT'25에서 제기된 미해결 문제를 해결한다. 동일한 문제를 해결한 독립적인 동시대 논문이 여러 편 있다. 본 논문은 증명의 기저에 있는 수학과 개념적 직관을 명확하게 설명하는 데 중점을 둔다. 또한 LLM의 활용을 포함한 연구 과정을 명시적으로 기술한다.
원문 초록
Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult even for shallow ReLU networks. We study this problem for two-layer input-convex neural networks (ICNNs), a restricted architecture where nonnegative output weights enforce convexity. Computing the $L_p$-Lipschitz constant for these networks is equivalent to maximizing the dual norm over a zonotope. While $L_1$- and $L_\infty$-norm maximization on zonotopes admit fixed-parameter and polynomial-time algorithms, respectively, the parameterized complexity of the remaining $L_p$-norms was open. We prove that, for every fixed $p\in (1,\infty)\cap \mathbb{Q}$, maximizing the $L_p$-norm over a zonotope in $\mathbb{R}^d$ is W[1]-hard with respect to the dimension $d$. Moreover, our hardness results imply that brute-force enumeration algorithms are essentially optimal for this problem under the Exponential Time Hypothesis. By duality, the same hardness results hold for computing the $L_p$-Lipschitz constant of two-layer ReLU ICNNs. Our proof first establishes the result for the $L_2$-norm and then transfers the construction to arbitrary fixed $p\in (1,\infty)\cap\mathbb{Q}$ using a suitable Taylor approximation. These results resolve the corresponding questions regarding the parameterized complexity status for zonotope norm maximization and two-layer ICNN Lipschitz constants. Our paper resolves an open problem posted at COLT'25. There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying mathematics and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2608.24865v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.