Testing Approximate Stationarity Concepts for Piecewise Affine Functions and Extensions

Abstract

We study various aspects of the fundamental computational problem of detecting approximate stationary points for piecewise affine (PA) functions, including computational complexity, regularity conditions, and robustness in implementation. Specifically, for a PA function, we show that testing first-order approximate stationarity concepts in terms of three commonly used subdifferential constructions is computationally intractable unless P=NP. To facilitate computability, we establish the first necessary and sufficient condition for the validity of an equality-type (Clarke) subdifferential sum rule for a certain representation of arbitrary PA functions. Our main tools are nonsmooth analysis and polytope theory. Moreover, to address an important implementation issue, we introduce the first oracle-polynomial-time algorithm to test near-approximate stationarity for PA functions. We complement our results with extensions to other subdifferentials and applications to a series of structured piecewise smooth functions, including $\rho$-margin-loss SVM, piecewise affine regression, and neural networks with nonsmooth activation functions.