EFFICIENTLY TESTING LOCAL OPTIMALITY AND ESCAPING SADDLES FOR RELU NETWORKS
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, secondorder 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.
This paper proposes an efficient method to test whether a point is a local minimum in a 1-hidden-layer ReLU network. If the point is not a local minimum, the algorithm also returns a direction for descending the value of the loss function. 
The tests include a first-order stationary point test (FOSP), and a second-order stationary point test (SOSP). As these test can be written as QPs, the core challenge is that if there are M boundary points in the dataset, i.e.,  data points on a non-differentiable region of the ReLU function, then the FOSP test requires 2^M tests of extreme rays -- each boundary partition the whole space into at least two parts. This paper observes that since the feasible sets are pointed polyhedral cones. Therefore checking only these extreme rays suffices. This results in an efficient test with only 2M tests. 
Lastly, the paper performs experiments on synthetic data. It turns out there are surprisingly many boundary points.
Comments:
This paper proposes an interesting method of testing whether a given point is a local minimum or not in a ReLU network. The technique is non-trivial and requires some key observation to make it computationally efficient. However, I have the following concerns:
1) such a test may need very high numeric precision. For instance, you cannot make sure whether a floating point number is strictly greater than 0 or not. The small error may critically affect the property of a point. 
2) boundary points of a ReLU network should have measure 0 (correct me if not). The finding in the experiment shows surprisingly many boundary points. This is counter-intuitive. Is it because of numeric issues? You might misclassify non-boundary points.
3) Usefulness. 
    a. The paper claims that such a test would be very useful in practice. However, they cannot even perform an experiment on real datasets. 
    b. Such a method only works for one-hidden layer network. It is not clear deeper network admit similar structure. 
    c. Practical training of neural-network usually trains the network using SGD, which always obtain a solution with a non-zero gradient. In this sense, there is no need for such a testing. 
    d. It seems like it is much easier to perform a test with different activation function, e.g., sigmoid.
    
If the authors can address these concerns convincingly, I would be happy to change the rating.