Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

원문 초록

We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine (PA) functions, a basic task in nonsmooth optimization. PA functions form a canonical model for nonsmooth stationarity testing and capture the local polyhedral geometry that appears in ReLU-type training losses. Recent work of Tian and So (2025) shows that testing approximate stationarity notions for PA functions is computationally intractable in the worst case, and identifies fixed-dimensional tractability as an open direction. We address this direction from the viewpoint of parameterized complexity, with the ambient dimension $d$ as the parameter. In this paper, we give XP algorithms in fixed dimension for the tractable sides, and prove W[1]-hardness for the complementary sides. Moreover, lower bounds under the parameterized $k$-Clique hypothesis rule out deterministic algorithms running in time $\rho(d)s^{o(d)}$ for any computable function $\rho$, where $s$ denotes the total binary encoding length of the instance. As a further consequence, our results yield the corresponding parameterized complexity picture for testing local minimality of continuous PA functions. We also extend our hardness results to a family of shallow ReLU CNN training losses, tested in the trainable weight space. Thus, the same parameterized-complexity picture also appears for simple CNN training losses. Notably, our lower bounds assume that $k$-Clique on $N$-vertex graphs admits no deterministic $\rho(k)N^{o(k)}$-time algorithm for any computable function $\rho$. The recent refutations of the Exponential Time Hypothesis (ETH) (OpenAI, 2026) and the stronger fine-grained $k$-Clique hypothesis (Vassilevska Williams and Zamir, 2026) do not contradict this assumption.