  The NP-hard problem of optimizing a shallow ReLU network can be characterized
as a combinatorial search over each training example's activation pattern
followed by a constrained convex problem given a fixed set of activation
patterns. We explore the implications of this combinatorial aspect of ReLU
optimization in this work. We show that it can be naturally modeled via a
geometric and combinatoric object known as a zonotope with its vertex set
isomorphic to the set of feasible activation patterns. This assists in analysis
and provides a foundation for further research. We demonstrate its usefulness
when we explore the sensitivity of the optimal loss to perturbations of the
training data. Later we discuss methods of zonotope vertex selection and its
relevance to optimization. Overparameterization assists in training by making a
randomly chosen vertex more likely to contain a good solution. We then
introduce a novel polynomial-time vertex selection procedure that provably
picks a vertex containing the global optimum using only double the minimum
number of parameters required to fit the data. We further introduce a local
greedy search heuristic over zonotope vertices and demonstrate that it
outperforms gradient descent on underparameterized problems.
