math.OCMay 11, 2026

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

Authors: Yuhan Ye

Organizations: MIT

Abstract

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 by Tian and So (SODA 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 dd 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 Exponential Time Hypothesis rule out algorithms running in time ρ(d)\sizeo(d)ρ(d)\size^{o(d)} for any computable function ρρ, where \size\size denotes the total binary encoding length of the stationarity-testing instance. As a further consequence, our results yield the corresponding parameterized complexity picture for testing local minimality of continuous PA functions. We further extend our hardness results to a family of shallow ReLU CNN training losses, with stationarity tested in the trainable weight space. Thus, the same parameterized-complexity picture also appears for simple CNN training losses.

Explore similar work

CardsList
Sep 26, 2025cs.CC

Parameterized Hardness of Zonotope Containment and Neural Network Verification

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 ℓ≥2\ell\ge 2, deciding positivity (and thus surjectivity) of a function f:Rd→Rf:\mathbb{R}^d\to\mathbb{R} computed by an ℓ\ell-layer ReLU network is W[ℓ−1\ell-1]-hard when parameterized by the input dimension dd. The case ℓ=2\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 dd. Moreover, we show that approximating the maximum within any multiplicative factor and computing the LpL_p-Lipschitz constant for p∈(0,∞]p\in(0,\infty] in ℓ\ell-layer networks is NP-hard and W[ℓ−1\ell-1]-hard with respect to dd. For ℓ≥3\ell\ge 3, approximating the LpL_p-Lipschitz constant is NP- and W[ℓ−2\ell-2]-hard. We further show that the above problems are NP- and W[tt]-hard (for all t≥1t\ge 1) with respect to ℓ\ell for constant dd. Notably, our hardness results imply that the naive enumeration-based methods for these fundamental problems running in n(ℓ−1)d⋅poly⁡(N)n^{(\ell-1) d}\cdot\operatorname{poly}(N) time are all essentially optimal under the Exponential Time Hypothesis.
Vincent Froese, Moritz Grillo, Christoph Hertrich +1
Neural Network VerificationRectified Linear Unit NetworksNp-HardPolytopesLipschitz ConstantSemidefinite Programming+1
AskPDF
May 5, 2026cs.LG

Most ReLU Networks Admit Identifiable Parameters

We study the realization map of deep ReLU networks, focusing on when a function determines its parameters up to scaling and permutation. To analyze hidden redundancies beyond these standard symmetries, we introduce a framework based on weighted polyhedral complexes. Our main result shows that for every architecture whose input and hidden layers have width at least two, there exists an open set of identifiable parameters. This implies that the functional dimension of every such architecture is exactly the number of parameters minus the number of hidden neurons. We further show that minimal functional representations can still have non-trivial parameter redundancies. Finally, we establish a generic depth hierarchy, whereby for an open set of parameters the realized function cannot be represented generically by any shallower network.
Moritz Grillo, Guido Montúfar
Rectified Linear Unit NetworksIntrinsic Dimensionality
AskPDF
Jul 23, 2026cs.LG

New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of 11, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.
Cornelius Brand, Robert Ganian, Mathis Rocton
Rectified Linear Unit NetworksActivation FunctionsOptimalityComputable
AskPDF