arXiv:2605.10219 · v3
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 $ρ(d)s^{o(d)}$ for any computable function $ρ$, 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 $ρ(k)N^{o(k)}$-time algorithm for any computable function $ρ$. 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.
作者备注：2:46 Accepted at NeurIPS 2026. 29 pages. This revision states the conditional lower bounds directly under the parameterized k-Clique hypothesis, which is not contradicted by the recent refutations of ETH and the stronger fine-grained k-Clique hypothesis