Continuous DR-submodular Maximization: Structure and Algorithms
DR-submodular continuous functions are important objectives with wide real-world applications spanning MAP inference in determinantal point processes (DPPs), and mean-field inference for probabilistic submodular models, amongst others. DR-submodularity captures a subclass of non-convex functions that enables both exact minimization and approximate maximization in polynomial time. In this work we study the problem of maximizing non-monotone continuous DRsubmodular functions under general down-closed convex constraints. We start by investigating geometric properties that underlie such objectives, e.g., a strong relation between (approximately) stationary points and global optimum is proved. These properties are then used to devise two optimization algorithms with provable guarantees. Concretely, we first devise a "two-phase" algorithm with 1/4 approximation guarantee. This algorithm allows the use of existing methods for finding (approximately) stationary points as a subroutine, thus, harnessing recent progress in non-convex optimization. Then we present a non-monotone FRANK-WOLFE variant with 1/e approximation guarantee and sublinear convergence rate. Finally, we extend our approach to a broader class of generalized DR-submodular continuous functions, which captures a wider spectrum of applications. Our theoretical findings are validated on synthetic and real-world problem instances.
This paper presents a new approach for non-monotone DR sub modular optimisation. The strength of this paper over existing approaches is proposing a solution to a more general problem setting than having an approach subject to constraints such as the box constraints. The proofs are well constructed and presented. However the experimental results are somehow very limited. The parameters used for the simulated data are very limited and not sure if the authors have performed a much more simulations with different parameters to assess more in depth the "performance" of their approach over the existing ones. Also, for the real data set example, it is not very clear if that the proposed two-phase Frank-Wolfe algorithm performs much better than the others. From the figures, it seems performing just slightly better but not very convincing. For real-world problems, it is typically difficult to verify whether the assumptions hold or not, so a comparison with the DoubleGreedy algorithm would have been appropriate to see how much gain we have by considering a more general constraint.