Abstract
Convex relaxations are a key component of training and certifying provablysafe neural networks. However, despite substantial progress, a wide and poorlyunderstood accuracy gap to standard networks remains, raising the question ofwhether this is due to fundamental limitations of convex relaxations. Initialwork investigating this question focused on the simple and widely used IBPrelaxation. It revealed that some univariate, convex, continuous piecewiselinear (CPWL) functions cannot be encoded by any ReLU network such that itsIBP-analysis is precise. To explore whether this limitation is shared by moreadvanced convex relaxations, we conduct the first in-depth study on theexpressive power of ReLU networks across all commonly used convex relaxations.We show that: (i) more advanced relaxations allow a larger class of univariatefunctions to be expressed as precisely analyzable ReLU networks, (ii) moreprecise relaxations can allow exponentially larger solution spaces of ReLUnetworks encoding the same functions, and (iii) even using the most precisesingle-neuron relaxations, it is impossible to construct precisely analyzableReLU networks that express multivariate, convex, monotone CPWL functions.