Smooth Interactive Submodular Set Cover
Interactive submodular set cover is an interactive variant of submodular set cover over a hypothesis class of submodular functions, where the goal is to satisfy all sufficiently plausible submodular functions to a target threshold using as few (cost-weighted) actions as possible. It models settings where there is uncertainty regarding which submodular function to optimize. In this paper, we propose a new extension, which we call smooth interactive submodular set cover, that allows the target threshold to vary depending on the plausibility of each hypothesis. We present the first algorithm for this more general setting with theoretical guarantees on optimality. We further show how to extend our approach to deal with realvalued functions, which yields new theoretical results for real-valued submodular set cover for both the interactive and non-interactive settings.
*Summary*This paper considers the interactive submodular set cover problem, where one is given a set of submodular functions, and needs to optimize an unknown true function using a minimal amount of actions. The paper considers two extensions of previous work: (1) varying "saturation" conditions (i.e., threshold) for different hypothesis functions in the hypothesis class; and (2) settings when the hypothesis submodular functions are real-valued. The paper provides a unified greedy framework to (approximately) solve both problems. In general the paper is well organized and the theory seems sound, even though some parts could have been made clearer. My major criticism is the empirical part of the paper, namely there is no empirical support why one should use the proposed algorithm. please see my detailed comments below.*Quality*The paper provides worst case cost bound for the smooth interactive set cover problem, by designing a submodular meta-objective objective for various scenarios (of the threshold function). The key result of the paper the approximation guarantee for the multiple threshold version (and the authors show that one can reduce the convex threshold curve version can be approximately reduced to the previous case). The theory and proofs non-trivially generalize the results of Guillory and Bilmes, 2010.The authors gives an example of a real-world applications, but show no empirical results. In the simulation results, there are no competitive approaches (even random selection) as well, thus it's hard to tell the empirical effectiveness of the algorithm.The bound depends on the number of thresholds $N$. When N=1 it reduces to the Noisy ISSC setting. It would be helpful to see empirically how different N's influence the performance of the algorithm. *Clarity*The paper mentions active learning a couple of times in the paper. However, along the line of submodular maximization, active learning is more of "exploring" tests that can mostly reduces size of the version space, and does not favors the actions that are "exploitative". It may cause some confusion to readers.There are a list of typos / points that are unclear, as summarized below.Ln 73, in the cost bound, define $a$. Ln 208-210, if alpha_n > alpha_j, then by Ln 140, it should hold that kapa_n < kapa_j. Hence the kapa_n and kapa_j in equation (2) should be flipped.Ln 230, from the figure, shouldn't the condition only enforces that either of the two threshold must be satisfied, according to (A) (Ln 228-229)?In section 4.5, there seem to be a couple of typos / unclear explanations to the experiment: Ln 327, each cluster was randomly assigned 15 clusters of interest: do you mean 15 hypotheses of interest? Ln 334 states that "at epsilon = 15, the algorithm is allowed to terminate immediate immediately". Why is the cost still non-negative when epsilon >= 15?Ln 429, threshold for to*Originality and Significance*The work builds upon and extends the work of Guillory and Bilmes, 2010. As I mentioned earlier, even though it relies heavily on the previously work, the generalization in the proofs is novel.Since the construction of the algorithm (specifically, the surrogate meta objective) is non-trivial, I would like to see some empirical evidences showing that why one should use the proposed approach.