Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
This work addresses optimization challenges in machine learning and AI for applications such as sensor management and data summarization, though it is incremental as it extends existing submodular maximization techniques to continuous domains.
The paper tackles the problem of maximizing submodular continuous functions, which are non-convex and have applications like influence maximization, by proposing algorithms with approximation guarantees: a Frank-Wolfe variant achieves (1-1/e) for monotone functions under convex constraints, and a DoubleGreedy algorithm achieves 1/3 for non-monotone functions under box constraints.
Submodular continuous functions are a category of (generally) non-convex/non-concave functions with a wide spectrum of applications. We characterize these functions and demonstrate that they can be maximized efficiently with approximation guarantees. Specifically, i) We introduce the weak DR property that gives a unified characterization of submodularity for all set, integer-lattice and continuous functions; ii) for maximizing monotone DR-submodular continuous functions under general down-closed convex constraints, we propose a Frank-Wolfe variant with $(1-1/e)$ approximation guarantee, and sub-linear convergence rate; iii) for maximizing general non-monotone submodular continuous functions subject to box constraints, we propose a DoubleGreedy algorithm with $1/3$ approximation guarantee. Submodular continuous functions naturally find applications in various real-world settings, including influence and revenue maximization with continuous assignments, sensor energy management, multi-resolution data summarization, facility location, etc. Experimental results show that the proposed algorithms efficiently generate superior solutions compared to baseline algorithms.