NIPS 2016 reviews (only one good paper)

1 files changed, 61 insertions, 0 deletions

diff --git a/nips-2016-220.txt b/nips-2016-220.txt
new file mode 100644
index 0000000..2c5b67a
--- /dev/null
+++ b/nips-2016-220.txt
@@ -0,0 +1,61 @@
+Summary
+=======
+
+This papers studies submodular functions over a continuous domain: these
+functions are sometimes referred to as "smooth" submodular functions and are
+the direct generalization of discrete submodular functions for continuous
+variables. While prior work has focused on obtaining algorithms and
+optimization guarantees for minimizing smooth submodular functions, this paper
+focuses on obtaining approximation guarantees for maximizing smooth submodular
+functions. Specifically, the authors:
+
+* give and prove a characterization of submodularity (and coordinate-wise
+  concavity) in terms of a diminishing return (DR) property. This is
+  a generalization of a well-known characterization in the discrete case.
+
+* give a (1-1/e) approximation algorithm for smooth submodular functions which
+  are coordinate wise concave and monotone
+
+* give a 1/3 approximation algorithm for arbitrary smooth submodular functions
+
+* give examples of problems which lead to optimizing a smooth submodular
+  function
+
+* validate their algorithms through experiments
+
+Comments
+========
+
+Smooth submodular functions have gathered interest in the recent years and as
+the authors point out, event though results were known for minimization, there
+was a lack of results on the maximization side. 
+
+While it is interesting to see that the results of the discrete case translate
+well to the continuous case, this is also the source of a (relative) weakness
+of the paper: a lack of technical novelty.
+
+Section 4 in particular is a direct adaptation of the continuous algorithm of
+Vondrak 2008. I don't see any fundamental difference in the statement of the
+algorithm and the proof follows a very similar technique. Also, it would have
+been interesting to mention that the multilinear extension of a monotone
+submodular function is DR-submodular to clearly show the connection with
+already existing results.
+
+The algorithm in section 5 is more novel: it draws heavily from the algorithm
+of [Buchbinder 2012] but required an adaptation to the continuous case (and
+a specific analysis).
+
+It is interesting that the authors give examples where maximizing smooth
+submodular functions arise. Some of these examples seem a bit contrived, but
+I don't have enough domain-specific knowledge to judge this confidently.
+
+The paper is well written overall, but suffers from some notations
+inconsitencies locally which can be unsettling for the reader. Two examples:
+
+* the definition of submodularity line 80 is given for arbitrary compact sets,
+but later the authors seem to focs on the specific case of the positive orthant
+of R^n, it is not clear if the results hold in the most general case.
+
+* definition 3.1 is hard to read: is it necessary to introduce a ground set and
+then the characteristic vectors of the ground set elements? why not simply use
+R^n and the standard basis vectors?