Testing Approximate Stationarity Concepts for Piecewise Smooth Functions

We study various aspects of the fundamental computational problem of the stationarity test for piecewise smooth functions. Our contributions are:* Hardness: We show that checking first-order approximate stationarity concepts in term of different subdifferential constructions for a piecewise linear function is strongly co-NP-hard. As a corollary, we proved that testing FOM for abs-norm form is computational hard, confirming a conjecture by Griewank and Walther [14, SIAM J. Optim., 29 (2019), pp. 284].* Regularity: We establish a necessary and sufficient condition for the validity of an equality-type subdifferential sum rule for the Sum of Difference-of-Max (SDM) functions by using tools from generalized differentiation theory and polytope theory. This SDM class is underlying the analysis of many important nonsmooth piecewise differentiable functions, including the empirical loss of two-layer ReLU networks.In particular, we show that this condition is efficiently checkable when the subdifferential set is of a zonotope type.* Robust algorithms: We introduce the first oracle-polynomial-time algorithm to test near-approximate stationarity for a SDM function. When specialized to the empirical loss of two-layer ReLU networks, our new algorithm is the first practical and robust stationarity test approach, tackling an open issue in the work of Yun et al. [29, ICLR (2019)].