  Due to the non-convex nature of training Deep Neural Network (DNN) models,
their effectiveness relies on the use of non-convex optimization heuristics.
Traditional methods for training DNNs often require costly empirical methods to
produce successful models and do not have a clear theoretical foundation. In
this study, we examine the use of convex optimization theory and sparse
recovery models to refine the training process of neural networks and provide a
better interpretation of their optimal weights. We focus on training two-layer
neural networks with piecewise linear activations and demonstrate that they can
be formulated as a finite-dimensional convex program. These programs include a
regularization term that promotes sparsity, which constitutes a variant of
group Lasso. We first utilize semi-infinite programming theory to prove strong
duality for finite width neural networks and then we express these
architectures equivalently as high dimensional convex sparse recovery models.
Remarkably, the worst-case complexity to solve the convex program is polynomial
in the number of samples and number of neurons when the rank of the data matrix
is bounded, which is the case in convolutional networks. To extend our method
to training data of arbitrary rank, we develop a novel polynomial-time
approximation scheme based on zonotope subsampling that comes with a guaranteed
approximation ratio. We also show that all the stationary of the nonconvex
training objective can be characterized as the global optimum of a subsampled
convex program. Our convex models can be trained using standard convex solvers
without resorting to heuristics or extensive hyper-parameter tuning unlike
non-convex methods. Through extensive numerical experiments, we show that
convex models can outperform traditional non-convex methods and are not
sensitive to optimizer hyperparameters.
