In this paper, we consider the problem of training structured neural networks (NN) with nonsmooth regularization (e.g. 1 -norm) and constraints (e.g. interval constraints). We formulate training as a constrained nonsmooth nonconvex optimization problem, and propose a convergent proximal-type stochastic gradient descent (Prox-SGD) algorithm. We show that under properly selected learning rates, with probability 1, every limit point of the sequence generated by the proposed Prox-SGD algorithm is a stationary point. Finally, to support the theoretical analysis and demonstrate the flexibility of Prox-SGD, we show by extensive numerical tests how Prox-SGD can be used to train either sparse or binary neural networks through an adequate selection of the regularization function and constraint set.
[Summary]
This paper proposes Prox-SGD, a theoretical framework for stochastic optimization algorithms that (1) incorporates momentum and coordinate-wise scaling as in Adam, and (2) can handle constraint and (non-smooth) regularizers through the proximal operator. With proper choices of hyperparameters, the algorithm is shown to converge asymptotically to stationarity, for smooth non-convex loss + convex constraint/regularizer. The algorithm is empirically tested on training binary and sparse neural nets on MNIST and CIFAR-10.
[Pros]
The theoretical framework that incorporates most of the commonly used tweaks in stochastic optimization for deep learning, and a convergence result that establishes broadly the asymptotic convergence to stationarity.
[Cons]
The result of Theorem 1 sounds rather a straightforward application of classical results; important sub-cases such as Adam violates the assumption (Adam has \rho_t = \rho so \sum \rho_t^2 = \infty) and thus are not contained in this case. From this it seems to me Theorem 1 says things mostly about the “easier” sub-cases, and thus is perhaps not very surprising and a bit limited in bringing in new messages. 
The experiments are mostly done on simple problems --- 3 of the 4 figures are on MNIST. The specific tasks (training sparse / binary neural nets with MLP / vanilla CNN architectures) considered in the experiments are all very extensively studied in prior work, and the results in this paper says at most that the proposed Prox-SGD works for these tasks.
Overall, I like the idea in this paper that we can put together a unified framework for stochastic optimization algorithms and incorporate things like momentums and regularizations that were previously treated separately. However, beyond proposing such a framework, it seems that contributions on both the theoretical and empirical side are a bit limited at this point.
***
Thank the authors for the response and the efforts in revising the paper. I am glad to see the additional experiments for training sparse networks on CIFAR-100 (a much harder task than MNIST and also CIFAR-10) in which the proposed method works well. This largely resolved my concerns on the experimental side. 
However, I'd still like to hold my evaluation on the theoretical side, in that approaches for handling constraints / non-smoothness / momentums are fairly well understood in the optimization literature. The present result (Theorem 1) conveys the message that these approaches can be combined to work (give an algorithm that converges to stationary points if it converges), but is not really a result that gives us new understandings / novel proof techniques beyond that.
I have slightly improved my rating to reflect my updated evaluation.