Landscape analysis for shallow neural networks: complete classification of critical points for affine target functions

In this paper, we analyze the landscape of the true loss of one-hidden-layer networks with ReLU, leaky ReLU, as well as with quadratic activation. In all three cases, we provide a complete classification of the critical points in the case where the target function is affine. In particular, we show that there exist no local maxima and clarify the structure of saddle points. Moreover, we prove that non-global local minima can only be caused by `dead' ReLU neurons. In particular, they do not appear in the case of leaky ReLU or quadratic activation. Our approach is of a combinatorial nature and builds on a careful analysis of the different types of hidden neurons that can occur.