{"id":"arxiv/2605.10219","url":"https://arxiv.org/abs/2605.10219","tags":["math.OC","cs.CC","cs.LG"],"score":0,"title":"Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses","domain":"math.OC","source":"arxiv","authors":["Yuhan Ye"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-11","reactions":{}}