  We develop an analytical framework to characterize the set of optimal ReLU
neural networks by reformulating the non-convex training problem as a convex
program. We show that the global optima of the convex parameterization are
given by a polyhedral set and then extend this characterization to the optimal
set of the non-convex training objective. Since all stationary points of the
ReLU training problem can be represented as optima of sub-sampled convex
programs, our work provides a general expression for all critical points of the
non-convex objective. We then leverage our results to provide an optimal
pruning algorithm for computing minimal networks, establish conditions for the
regularization path of ReLU networks to be continuous, and develop sensitivity
results for minimal ReLU networks.
