Learning Neural Network Classifiers with Low Model Complexity

Deep neural networks have become an extremely popular learning technique, with significant deployment in a wide variety of practical domains such as computer vision [1, 2, 3], biosignal processing [4, 5], image captioning [6] and speech recognition [7]. With the significant increase in dataset scale and subsequent increase in model complexity of multilayered neural network architectures, it has become imperative to learn networks that can offer performance guarantees, yield good generalization, and provide sparse representations. Vapnik's seminal work in computational learning theory [8] highlighted that a small VC dimension and good generalization go hand in hand, however, minimizing the VC dimension as a function of the weights of the class of networks has remained elusive. The representational redundancy in deep neural networks is well recognized. Some works on model complexity have recently appeared in literature [9, 10]. In many cases, the number of parameters exceeds the amount of training data resulting in severe overfitting [11]. Sontag [12] derived that the VC dimension of neural network with |W | weights is O(|W |log(|W |)), where |W | is the cardinality of total number of weights. Hence, it is essential to reduce the redundancy in weights and neurons and enforce sparsity in the structure to bring down the VC dimension [13, 14]. A number of methods have been proposed in the neural network domain to reduce model complexity [15, 16, 17], but these largely focus on pruning trained networks by removing synapses or neurons through heuristics or by applying sparsity inducing norms (e.g., L