Deep Submodular Functions: Definitions & Learning
We propose and study a new class of submodular functions called deep submodular functions (DSFs). We define DSFs and situate them within the broader context of classes of submodular functions in relationship both to various matroid ranks and sums of concave composed with modular functions (SCMs). Notably, we find that DSFs constitute a strictly broader class than SCMs, thus motivating their use, but that they do not comprise all submodular functions. Interestingly, some DSFs can be seen as special cases of certain deep neural networks (DNNs), hence the name. Finally, we provide a method to learn DSFs in a max-margin framework, and offer preliminary results applying this both to synthetic and real-world data instances.
The papers introduces deep submodular functions which is a generalization of previous considered sums of concave over modular functions (SCM). SCM's are basically submodular functions obtained by summing over concave functions applied to the output of a sum of modular/linear functions.  Now the deep submodular functionsare sum of concave sum of concave ... on sum of modular functions. This seems like a natural generalization of SCMs.  The paper proves that deep submodular functions is a strictly bigger class than SCMs and a strict subset of submodular functions.   They also argue that these functions are easier to optimize than submodular functions in general. In particular, they consider the problem of learning a deep submodular function. These results are experimental  (and no real proofs).  
The novelty in terms of techniques seems limited and the theory results not too surprising. I would say that the main contribution of the paper is the introduction of deep submodular functions. This is definitely a worthwhile conceptual contribution. But, as the paper contains limited indications of its usefulness, I rate this contribution as insufficient for NIPS.   I would also recommend that the authors are more careful in some of the writing. For example, in the first paragraph you say that submodular function maximization is one of the easiest NP-hard problems and then cite the result of Nemhauser's (1-1/e)-approximation. The best approximation for submodular function maximization is 1/2 and that is tight. Nemhauser result is in the monotone case and then it is trivial to maximize; his result is when you have a cardinality constraint.  Also, I would say that the rank function of the laminar matroid is a fairly simple submodular function.