Pith Number

pith:GED5RDU3

pith:2026:GED5RDU3JMFVHE2GVVSH4TDKHE

not attested not anchored not stored refs pending

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

Yuhan Ye

Testing approximate stationarity for continuous piecewise-affine functions is XP-tractable in fixed dimension for some cases but W[1]-hard for others, with ETH lower bounds excluding subexponential dependence on dimension.

arxiv:2605.10219 v2 · 2026-05-11 · math.OC · cs.CC · cs.LG

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{GED5RDU3JMFVHE2GVVSH4TDKHE}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

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) size^{o(d)} for any computable function ρ, where size denotes the total binary encoding length of the stationarity-testing instance.

C2weakest assumption

The assumption that continuous piecewise-affine functions form a canonical model that captures the local polyhedral geometry appearing in ReLU-type training losses, and that the chosen notion of approximate first-order stationarity is the appropriate one for the parameterized analysis.

C3one line summary

The paper fully characterizes the parameterized complexity of approximate first-order stationarity testing for continuous piecewise-affine functions and shallow ReLU CNN losses with respect to the dimension parameter, including XP algorithms, W[1]-hardness, and ETH lower bounds.

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-25T02:01:22.788761Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

3107d88e9b4b0b539346ad647e4c6a391c06840c0529e36b0797d6104ae2056a

Aliases

arxiv: 2605.10219 · arxiv_version: 2605.10219v2 · doi: 10.48550/arxiv.2605.10219 · pith_short_12: GED5RDU3JMFV · pith_short_16: GED5RDU3JMFVHE2G · pith_short_8: GED5RDU3

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/GED5RDU3JMFVHE2GVVSH4TDKHE \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 3107d88e9b4b0b539346ad647e4c6a391c06840c0529e36b0797d6104ae2056a

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "eaeda1156351b7ffa91e17e4a4295db6964e268b1cd3ce9a530bd4af9e327e56",
    "cross_cats_sorted": [
      "cs.CC",
      "cs.LG"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "math.OC",
    "submitted_at": "2026-05-11T08:59:57Z",
    "title_canon_sha256": "632fd37e0d9554c4a1846e13e91fc71c4d49351b5a7fa58a22681c6a163b0546"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.10219",
    "kind": "arxiv",
    "version": 2
  }
}