State-of-the-art deep neural networks (DNNs) typically have tens of millions of parameters, which might not fit into the upper levels of the memory hierarchy, thus increasing the inference time and energy consumption significantly, and prohibiting their use on edge devices such as mobile phones. The compression of DNN models has therefore become an active area of research recently, with connection pruning emerging as one of the most successful strategies. A very natural approach is to prune connections of DNNs via 1 regularization, but recent empirical investigations have suggested that this does not work as well in the context of DNN compression. In this work, we revisit this simple strategy and analyze it rigorously, to show that: (a) any stationary point of an 1 -regularized layerwisepruning objective has its number of non-zero elements bounded by the number of penalized prediction logits, regardless of the strength of the regularization; (b) successful pruning highly relies on an accurate optimization solver, and there is a trade-off between compression speed and distortion of prediction accuracy, controlled by the strength of regularization. Our theoretical results thus suggest that 1 pruning could be successful provided we use an accurate optimization solver. We corroborate this in our experiments, where we show that simple 1 regularization with an Adamax-L1(cumulative) solver gives pruning ratio competitive to the state-of-the-art.
This paper discusses the effect of L1 penalization for deep neural network. In particular it shows the stationary point of an l1 regularized layer has bounded non-zero elements. 
The perspective of the proof is interesting: By chain rule, the stationary point satisfies nnz(W^j) linear equations, but the subgradients of the loss function w.r.t. the logits have at most N\times ks variables. If the coefficients of the linear equation are distributed in general positions, then the number of variables should not be larger than the number of equations. 
While I mostly like the paper, I would like to point out some possible issues:
main concerns: 
1. the columns of V may not be independent during the optimization(training) process. In this situation, I am not quite sure if the assumption of “general position” still holds. I understand that in literatures of Lasso and sparse coding it is common to assume “general position”. But in those problems the coefficient matrix is not Jacobian from a learning procedure. 
2. the claim is a little bit counter intuitive: Theorem 1 claims the sparse inequality holds for any \lambda. It is against the empirical observation that when lambda is extremely small, effect of the regularizer tends to be almost zero. Can authors also show this effects empirically, i.e., when the regularization coefficients decrease, the nnz does not vary much? (Maybe there is some optimization details or approximations I missed?)
Some minor notation issues:
1. in theorem 1: dim(W^{(j)})=d should be dim(vec(W^{(j)}))=d
2. in theorem 1: Even though I understand what you are trying to say, I would suggest we describe the jacobian matrix V in details. Especially it is confusing to stack vec(X^J) (vec(W^j)) in the description.
3. the notations of subgradient and gradient are used without claim