A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice
We consider a generalization of the submodular cover problem based on the concept of diminishing return property on the integer lattice. We are motivated by real scenarios in machine learning that cannot be captured by (traditional) submodular set functions. We show that the generalized submodular cover problem can be applied to various problems and devise a bicriteria approximation algorithm. Our algorithm is guaranteed to output a log-factor approximate solution that satisfies the constraints with the desired accuracy. The running time of our algorithm is roughly O(n log(nr) log r), where n is the size of the ground set and r is the maximum value of a coordinate. The dependency on r is exponentially better than the naive reduction algorithms. Several experiments on real and artificial datasets demonstrate that the solution quality of our algorithm is comparable to naive algorithms, while the running time is several orders of magnitude faster.
PAPER SUMMARYThe paper proposes a generalization of submodular cover to integer lattices. Specifically, the problem is to minimum a sub-additive function c over an integer lattice, under the constraint that the value of a DR-submodular function f is at least \alpha. The paper presents an efficient greedy algorithm, which provides a multiplicative bound on the objective c, and a multiplicative violation of the constraint f. Even in the case where c is DR-submodular, and the problem can be reduced from integer lattices to set functions, the worst-case runtime of the algorithm is better than the one suggested by this reduction. COMMENTS- The generalization of submodular cover is interesting, and nicely justified through some plausible applications.- The paper is clearly written. However, section 1.1 contains several terms that are defined later. This makes it difficult to immediately follow the related work section that compares the guarantees of the proposed method with previous algorithms for special cases. Either all the terms should be specified in section 1.1, or the related work section should be moved to the end of the technical section.- When c is DR-submodular, how does the theoretical guarantee obtained by the naive reduction compare to the proposed method? The paper only mentions that the proposed method is faster. Is it as accurate?- Can multiple submodular constraints be handled using the proposed method?- The functions c and f used in the experiments are hand-tuned, and their validity for the applications is not clear. However, for the setting used, the proposed method seems to perform more accurately than some baselines, and faster than others, thereby providing a desirable trade-off.- Minor: equation (5): explain the notation "x*: optimal solution". By context, I think this means that "x* \in X*" where X* is the set of all optimal solutions. Is that right?