@inproceedings{
tian2023testing,
title={Testing Approximate Stationarity Concepts for Piecewise Affine Functions and Extensions},
author={Lai Tian and Anthony Man-Cho So},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=5HbXROFu3p}
}
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.
Testing Approximate Stationarity Concepts for Piecewise Affine Functions and Extensions
Lai Tian Anthony Man-Cho So