2018/10/16 by Yibo Zhang, Chao Qian, Zhang, Yibo +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1810.06833
openalex publication_date 2018/10/16 · openalex created_date 2018/10/26 · openalex updated_date 2026/07/28
In this paper, we study the problem of monotone (weakly) DR-submodular continuous maximization. While previous methods require the gradient information of the objective function, we propose a derivative-free algorithm LDGM for the first time. We define β and α to characterize how close a function is to continuous DR-submodulr and submodular, respectively. Under a convex polytope constraint, we prove that LDGM can achieve a (1-e-β-ε)-approximation guarantee after O(1/ε) iterations, which is the same as the best previous gradient-based algorithm. Moreover, in some special cases, a variant of LDGM can achieve a ((α/2)(1-e-α)-ε)-approximation guarantee for (weakly) submodular functions. We also compare LDGM with the gradient-based algorithm Frank-Wolfe under noise, and show that LDGM can be more robust. Empirical results on budget allocation verify the effectiveness of LDGM.