We provide a theoretical algorithm for checking local optimality and escaping saddles at nondifferentiable points of empirical risks of two-layer ReLU networks. Our algorithm receives any parameter value and returns: local minimum, second-order stationary point, or a strict descent direction. The presence of M data points on the nondifferentiability of the ReLU divides the parameter space into at most 2^M regions, which makes analysis difficult. By exploiting polyhedral geometry, we reduce the total computation down to one convex quadratic program (QP) for each hidden node, O(M) (in)equality tests, and one (or a few) nonconvex QP. For the last QP, we show that our specific problem can be solved efficiently, in spite of nonconvexity. In the benign case, we solve one equality constrained QP, and we prove that projected gradient descent solves it exponentially fast. In the bad case, we have to solve a few more inequality constrained QPs, but we prove that the time complexity is exponential only in the number of inequality constraints. Our experiments show that either benign case or bad case with very few inequality constraints occurs, implying that our algorithm is efficient in most cases. Empirical success of deep neural networks has sparked great interest in the theory of deep models. From an optimization viewpoint, the biggest mystery is that deep neural networks are successfully trained by gradient-based algorithms despite their nonconvexity. On the other hand, it has been known that training neural networks to global optimality is NP-hard BID2 . It is also known that even checking local optimality of nonconvex problems can be NP-hard (Murty & Kabadi, 1987) . Bridging this gap between theory and practice is a very active area of research, and there have been many attempts to understand why optimization works well for neural networks, by studying the loss surface BID1 Yu & Chen, 1995; Kawaguchi, 2016; Soudry & Carmon, 2016; Nguyen & Hein, 2017; Safran & Shamir, 2018; Laurent & Brecht, 2018; Yun et al., 2019; Zhou & Liang, 2018; Wu et al., 2018; Shamir, 2018) and the role of (stochastic) gradientbased methods (Tian, 2017; BID4 Zhong et al., 2017; Soltanolkotabi, 2017; Li & Yuan, 2017; Zhang et al., 2018; BID5 Wang et al., 2018; Li & Liang, 2018; BID9 BID11 BID7 BID0 Zou et al., 2018; Zhou et al., 2019) .One of the most important beneficial features of convex optimization is the existence of an optimality test (e.g., norm of the gradient is smaller than a certain threshold) for termination, which gives us a certificate of (approximate) optimality. In contrast, many practitioners in deep learning rely on running first-order methods for a fixed number of epochs, without good termination criteria for the optimization problem. This means that the solutions that we obtain at the end of training are not necessarily global or even local minima. Yun et al. (2018; 2019) showed efficient and simple global optimality tests for deep linear neural networks, but such optimality tests cannot be extended to general nonlinear neural networks, mainly due to nonlinearity in activation functions.Besides nonlinearity, in case of ReLU networks significant additional challenges in the analysis arise due to nondifferentiability, and obtaining a precise understanding of the nondifferentiable points is still elusive. ReLU activation function h(t) = max{t, 0} is nondifferentiable at t = 0. This means that, for example, the function f (w, b) := (h(w T x + b) − 1) 2 is nondifferentiable for any (w, b) satisfying w T x+b = 0. See FIG2 for an illustration of how the empirical risk of a ReLU network looks like. Although the plotted function does not exactly match the definition of empirical risk we study in this paper, the figures help us understand that the empirical risk is continuous but piecewise differentiable, with affine hyperplanes on which the function is nondifferentiable.Such nondifferentiable points lie in a set of measure zero, so one may be tempted to overlook them as "non-generic." However, when studying critical points we cannot do so, as they are precisely such "non-generic" points. For example , Laurent & Brecht (2018) study one-hidden-layer ReLU networks with hinge loss and note that except for piecewise constant regions, local minima always occur on nonsmooth boundaries. Probably due to difficulty in analysis, there have not been other works that handle such nonsmooth points of losses and prove results that work for all points. Some theorems (Soudry & Carmon, 2016; Nguyen & Hein, 2018) hold "almost surely"; some assume differentiability or make statements only for differentiable points (Nguyen & Hein, 2017; Yun et al., 2019) ; others analyze population risk, in which case the nondifferentiability disappears after taking expectation (Tian, 2017; BID4 BID10 Safran & Shamir, 2018; Wu et al., 2018 ). We provided a theoretical algorithm that tests second-order stationarity and escapes saddle points, for any points (including nondifferentiable ones) of empirical risk of shallow ReLU-like networks. Despite difficulty raised by boundary data points dividing the parameter space into 2 M regions, we reduced the computation to d h convex QPs, O(M ) equality/inequality tests, and one (or a few more) nonconvex QP. In benign cases, the last QP is equality constrained, which can be efficiently solved with projected gradient descent. In worse cases, the QP has a few (say L) inequality constraints, but it can be solved efficiently when L is small. We also provided empirical evidences that L is usually either zero or very small, suggesting that the test can be done efficiently in most cases. A limitation of this work is that in practice, exact nondifferentiable points are impossible to reach, so the algorithm must be extended to apply the nonsmooth analysis for points that are "close" to nondifferentiable ones. Also, current algorithm only tests for exact SOSP, while it is desirable to check approximate second-order stationarity. These extensions must be done in order to implement a robust numerial version of the algorithm, but they require significant amount of additional work; thus, we leave practical/robust implementation as future work. Also, extending the test to deeper neural networks is an interesting future direction. Algorithm 2 SOSP-CHECK DISPLAYFORM0
A theoretical algorithm for testing local optimality and extracting descent directions at nondifferentiable points of empirical risks of one-hidden-layer ReLU networks. Proposes an algorithm to check whether a given point is a generalized second-order stationary point. A theoretical algorithm, involving solving convex and non-convex quadratic programs, for checking local optimality and escaping saddles when training two-layer ReLU networks. Author proposes a method to check if a point is a stationary point or not and then classify stationary points as either local min or second-order stationary