# Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms

arXiv: https://arxiv.org/abs/2302.12261 · HTML: https://mlsanity.com/paper/2302.12261/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 23 Feb 2023.

## Builds on (most cited first, 19 of 19)

- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions](https://mlsanity.com/paper/2112.09002/) (2021)
- [Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization](https://mlsanity.com/paper/1808.04685/) (2018)
- [On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias](https://mlsanity.com/paper/2205.09072/) (2022)
- [Understanding Notions of Stationarity in Non-Smooth Optimization](https://mlsanity.com/paper/2006.14901/) (2020)
- [No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzians](https://mlsanity.com/paper/2210.06907/) (2022)
- [Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions](https://mlsanity.com/paper/2002.04130/) (2020)
- [The cost of nonconvexity in deterministic nonsmooth optimization](https://mlsanity.com/paper/2210.00652/) (2022)
- [On the Complexity of Finding Small Subgradients in Nonsmooth Optimization](https://mlsanity.com/paper/2209.10346/) (2022)
- [On the complexity of finding a local minimizer of a quadratic function over a polytope](https://mlsanity.com/paper/2008.05558/) (2020)
- [On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization](https://mlsanity.com/paper/2209.12463/) (2022)
- [Efficiently testing local optimality and escaping saddles for ReLU networks](https://mlsanity.com/paper/1809.10858/) (2018)
- [Perturbed Iterate SGD for Lipschitz Continuous Loss Functions](https://mlsanity.com/paper/2003.07606/) (2020)

## Built on by (most cited first, 2 of 2)

- [On subdifferential chain rule of matrix factorization and beyond](https://mlsanity.com/paper/2410.05022/) (2024)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)

## Abstract (arXiv)

We study the computational problem of the stationarity test for the empirical loss of neural networks with ReLU activation functions. Our contributions are: Hardness: We show that checking a certain first-order approximate stationarity concept for a piecewise linear function is co-NP-hard. This implies that testing a certain stationarity concept for a modern nonsmooth neural network is in general computationally intractable. As a corollary, we prove that testing so-called first-order minimality for functions in abs-normal form is co-NP-complete, which was conjectured by Griewank and Walther (2019, SIAM J. Optim., vol. 29, p284). Regularity: We establish a necessary and sufficient condition for the validity of an equality-type subdifferential chain rule in terms of Clarke, Fr'echet, and limiting subdifferentials of the empirical loss of two-layer ReLU networks. This new condition is simple and efficiently checkable. Robust algorithms: We introduce an algorithmic scheme to test near-approximate stationarity in terms of both Clarke and Fr'echet subdifferentials. Our scheme makes no false positive or false negative error when the tested point is sufficiently close to a stationary one and a certain qualification is satisfied. This is the first practical and robust stationarity test approach for two-layer ReLU networks.