From 5550e00c788050053a01cae9d5ab40219ff03a67 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 18 Jul 2016 00:39:35 -0400 Subject: NIPS 2016 reviews (only one good paper) --- nips-2016-220.txt | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 61 insertions(+) create mode 100644 nips-2016-220.txt (limited to 'nips-2016-220.txt') 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? -- cgit v1.2.3-70-g09d2