Net-Trim: Convex Pruning of Deep Neural Networks with Performance Guarantee
We introduce and analyze a new technique for model reduction for deep neural networks. While large networks are theoretically capable of learning arbitrarily complex models, overfitting and model redundancy negatively affects the prediction accuracy and model variance. Our Net-Trim algorithm prunes (sparsifies) a trained network layer-wise, removing connections at each layer by solving a convex optimization program. This program seeks a sparse set of weights at each layer that keeps the layer inputs and outputs consistent with the originally trained model. The algorithms and associated analysis are applicable to neural networks operating with the rectified linear unit (ReLU) as the nonlinear activation. We present both parallel and cascade versions of the algorithm. While the latter can achieve slightly simpler models with the same generalization performance, the former can be computed in a distributed manner. In both cases, Net-Trim significantly reduces the number of connections in the network, while also providing enough regularization to slightly reduce the generalization error. We also provide a mathematical analysis of the consistency between the initial network and the retrained model. To analyze the model sample complexity, we derive the general sufficient conditions for the recovery of a sparse transform matrix. For a single layer taking independent Gaussian random vectors of length N as inputs, we show that if the network response can be described using a maximum number of s non-zero weights per node, these weights can be learned from O(s log N ) samples.
The paper presents a technique to sparsify a deep ReLU neural network by solving a sequence of convex problems at each layer. The convex problem finds the sparsest set of weights that approximates the mapping from one layer to another. The ReLU nonlinearity is dealt with by treating the activated and deactivated cases as two separate sets of constraints in the optimization problem, thus, bringing convexity.
Two variants are provided, one that considers each layer separately, and another that carries the approximation in the next layer optimization problem to give the chance to the next layer to counterbalance this error. In both cases, the authors provide bounds on the approximation error after sparsification.
The paper is very clear and well-written. A number of theoretical results come in support to the proposed method.
The experiments section shows results for various networks (fully connected, and convolutional) on the MNIST data. The results are compared with a baseline which consists of removing weights with smallest magnitude from the network. The authors observe that their method works robustly while the baseline methods lands in some plateau with very low accuracy.
The baseline proposed here looks particularly weak. Setting a large number of weights to zero slashes the variance of the neuron preactivations, and the negative biases will tend to drive activations zero. Actually, in the HPTD paper, the authors obtain the best results by iteratively pruning the weights.
A pruning ratio of 80% is quite low. Other approaches such as SqueezeNet have achieved 98% parameter reduction on image data without significant drop of performance.