arXiv:2509.22849v3 cs.CC

조노토프 포함 문제 및 신경망 검증의 매개변수화된 난해성

Parameterized Hardness of Zonotope Containment and Neural Network Verification

Vincent Froese, Moritz Grillo, Christoph Hertrich, Moritz Stargalla

제출 2025-09-26

한국어 초록

렐루(ReLU) 활성화 함수를 사용하는 신경망은 머신러닝에서 널리 사용되는 모델입니다. 따라서 이러한 신경망이 계산하는 함수의 특성을 깊이 이해하는 것은 중요합니다. 최근에는 이러한 특성을 판별하는 (매개변수화된) 계산 복잡도에 대한 관심이 높아지고 있습니다. 본 연구에서는 신경망 검증과 관련된 여러 문제의 매개변수화된 복잡도에 대해 몇 가지 공백을 메우고 Froese 등이 제기한 공개 문제[COLT '25]를 해결합니다. 구체적으로, 모든 $\ell\ge 2$에 대해 $\ell$-층 렐루 신경망이 계산하는 함수 $f:\mathbb{R}^d\to\mathbb{R}$의 양수성(positivity, 나아가 전사성(surjectivity))을 판별하는 문제는 입력 차원 $d$로 매개변수화되었을 때 W[$\ell-1$]-난해(W[$\ell-1$]-hard)임을 증명합니다. $\ell=2$인 경우는 조노토프 비포함(zonotope non-containment, 계산기하학, 제어 이론, 로보틱스에서 독자적인 관심을 갖는 문제) 문제가 주변 차원(ambient dimension) $d$에 대해 W[1]-난해임을 의미합니다. 또한, 임의의 곱셈 계수 내에서 최댓값을 근사하는 문제와 $p\in(0,\infty]$에 대한 $L_p$-립시츠 상수(Lipschitz constant)를 계산하는 문제가 $\ell$-층 신경망에서 $d$에 대해 NP-난해이며 W[$\ell-1$]-난해임을 보입니다. $\ell\ge 3$의 경우, $L_p$-립시츠 상수를 근사하는 것은 NP-난해이자 W[$\ell-2$]-난해입니다. 나아가 상수 $d$에 대해 위의 문제들이 $\ell$에 대해 (모든 $t\ge 1$에 대하여) NP-난해이자 W[$t$]-난해임을 보입니다. 특히, 우리의 난해성 결과는 이러한 기본 문제들에 대해 $n^{(\ell-1) d}\cdot\operatorname{poly}(N)$ 시간에 실행되는 단순 열거 기반 방법들이 지수 시간 가설(Exponential Time Hypothesis) 하에서 모두 본질적으로 최적임을 시사합니다.

원문 초록

Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing interest in the (parameterized) computational complexity of determining these properties. In this work, we close several gaps and resolve an open problem posed by Froese et al. [COLT '25] regarding the parameterized complexity of various problems related to network verification. In particular, we prove that, for all $\ell\ge 2$, deciding positivity (and thus surjectivity) of a function $f:\mathbb{R}^d\to\mathbb{R}$ computed by an $\ell$-layer ReLU network is W[$\ell-1$]-hard when parameterized by the input dimension $d$. The case $\ell=2$ implies that zonotope non-containment (a problem that is of independent interest in computational geometry, control theory, and robotics) is W[1]-hard with respect to the ambient dimension $d$. Moreover, we show that approximating the maximum within any multiplicative factor and computing the $L_p$-Lipschitz constant for $p\in(0,\infty]$ in $\ell$-layer networks is NP-hard and W[$\ell-1$]-hard with respect to $d$. For $\ell\ge 3$, approximating the $L_p$-Lipschitz constant is NP- and W[$\ell-2$]-hard. We further show that the above problems are NP- and W[$t$]-hard (for all $t\ge 1$) with respect to $\ell$ for constant $d$. Notably, our hardness results imply that the naive enumeration-based methods for these fundamental problems running in $n^{(\ell-1) d}\cdot\operatorname{poly}(N)$ time are all essentially optimal under the Exponential Time Hypothesis.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2509.22849v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.