Research map / Learning theory and algorithms / Sample complexity

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

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Neural network approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Parameterized complexity (dimension d as parameter) of approximate Fréchet/Clarke stationarity testing for continuous piecewise-affine functions and shallow ReLU CNN losses: XP algorithms on one side, W[1]-hardness and ETH-tight lower bounds on the complementary sides.

Problem

Testing approximate first-order stationarity (Fréchet and Clarke) at a prescribed point for continuous piecewise-affine functions, and for shallow ReLU/max-pooling CNN training losses, parameterized by ambient dimension or trainable parameter dimension.

Approach

Shows the fixed-dimension picture for PA stationarity testing: one polarity is in XP via vertex enumeration / arrangement cone enumeration, the complementary polarity is W[1]-hard via reductions from k-Clique using convex subdifferential containment (Fréchet) and an extra coordinate (Clarke), and transfers these hardness results to shallow CNN losses.

Key results

• Fréchet-ε-YES and Clarke-ε-NO are decidable in s^{O(d)} time for explicit max-min input and in XP for fixed-depth n-MC DC input.
• d-Fréchet-ε-NO is W[1]-hard for every fixed ε≥0 and d-Clarke-ε-YES is W[1]-hard for ε in [0,1/2), via parameter-preserving reductions from k-Clique, with ETH lower bounds ruling out ρ(d)s^{o(d)} algorithms.
• For shallow ReLU CNN losses parameterized by trainable dimension p, Fréchet-ε-NO and Clarke-ε-YES are W[1]-hard, and all four polarities are decidable in M^{O(p)} time.

Surprising findings

• Single-max DC PA stationarity tests are polynomial-time solvable, while compact n-MC DC representations of the same kind of objects require exponential expansion into the flat form.

Limitations

• Results are worst-case for explicitly represented PA functions and a specific shallow CNN family.
• Lower bounds do not rule out faster algorithms under additional geometric regularity, average-case, or smoothed models.
• Clarke-side hardness is stated only for epsilon in [0,1/2).

Experimental setup

Baselines: direct enumeration s^{O(d)} single-max DC polynomial baseline

Builds on: Tian and So (2025) PA stationarity testing framework Reluplex/Marabou-style verification context k-Clique W[1]-completeness ETH

Closest papers by meaning

• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.86)
• The Multi-Block DC Function Class: Theory, Algorithms, and Applications (NeurIPS 2026 · similarity 0.85)
• First-Order Methods for Linearly Constrained Bilevel Optimization (NeurIPS 2024 · similarity 0.84)
• Transductive Learning is Compact (NeurIPS 2024 · similarity 0.84)
• Loss Landscape Characterization of Neural Networks without Over-Parametrization (NeurIPS 2024 · similarity 0.84)
• Random Function Descent (NeurIPS 2024 · similarity 0.84)