TOWARDS ROBUST, LOCALLY LINEAR DEEP NET- WORKS
Deep networks realize complex mappings that are often understood by their locally linear behavior at or around points of interest. For example, we use the derivative of the mapping with respect to its inputs for sensitivity analysis, or to explain (obtain coordinate relevance for) a prediction. One key challenge is that such derivatives are themselves inherently unstable. In this paper, we propose a new learning problem to encourage deep networks to have stable derivatives over larger regions. While the problem is challenging in general, we focus on networks with piecewise linear activation functions. Our algorithm consists of an inference step that identifies a region around a point where linear approximation is provably stable, and an optimization step to expand such regions. We propose a novel relaxation to scale the algorithm to realistic models. We illustrate our method with residual and recurrent networks on image and sequence datasets.
########## Updated Review ##########
The author(s) have presented a very good rebuttal, and I am impressed. My concerns have been addressed and my confusions have been clarified. To reflect this, I am raising my points to 8. It is a good paper, job well done. I enthusiastically recommend acceptance. 
################################
A key challenge that presents the deep learning community is that state-of-the-art solutions are oftentimes associated with unstable derivatives, compromising the robustness of the network. In this paper, the author(s) explore the problem of how to train a neural network with stable derivatives by expanding the linear region associated with training samples. 
The author(s) studied deep networks with piecewise linear activations, which allow them to derive lower bounds on the $l_p$ margin with provably stable derivatives. In the special case of $l_2$ metric, this bound is analytic, albeit rigid and non-smooth. To avoid associated computational issues, the author(s) borrowed an idea from transductive/semi-supervised SVM (TSVM) to derive a relaxed formulation. 
In general, I find this paper rather interesting and well written. However, I do have a few concerns and confusions as listed below: 
Major ones:
- I would prefer some elaborations on why the relaxation proposed in Eqn (8) serves to encourage the margin of L2 ball? What's the working mechanism or heuristic behind this relaxation? This is supposedly one of the key techniques used in optimization, yet remains obscure. 
- On empirical gains, the author(s) claimed that "about 30 times larger margins can be achieved by trading off 1% accuracy."  It seems that consistently yields inferior prediction accuracy. In my opinion, the author(s) failed to showcase the practical utility of their solution. A better job should be done to validate the claim `` The problem we tackle has implications to interpretability and transparency of complex models. '' 
- As always, gradient-based penalties suffer from heavy computational overhead. The final objectives derived in this paper (Eqn (7) & Eqn (9)) seem no exception to this, and perhaps even worse since the gradient is taken wrt each neuron. Could the author(s) provide statistics on empirical wallclock performance? How much drain does this extra gradient penalty impose on the training efficiency? 
Minor ones:
- Just to clarify, does the | - | used in Eqn (9) for |I(x,\gamma)|  denote counting measure? 
- I do not see the necessity of introducing Lemma 7 in the text. Please explain. 
- Lemma 8, ``... then any optimal solutions for the problem is also optimal for Eqn (4). '' Do you mean ``the following problem'' (Eqn (5))?