Non-differentiable saddle points and sub-optimal local minima exist for deep ReLU networks.

Abstract

Whether sub-optimal local minima and saddle points exist in the highly non-convex loss landscape of deep neural networks has a great impact on the performance of optimization algorithms. Theoretically, we study in this paper the existence of non-differentiable sub-optimal local minima and saddle points for deep ReLU networks with arbitrary depth. We prove that there always exist non-differentiable saddle points in the loss surface of deep ReLU networks with squared loss or cross-entropy loss under reasonable assumptions. We also prove that deep ReLU networks with cross-entropy loss will have non-differentiable sub-optimal local minima if some outermost samples do not belong to a certain class. Experimental results on real and synthetic datasets verify our theoretical findings.