Maximizing Monotone DR-submodular Continuous Functions by Derivative-free Optimization
This work addresses optimization challenges in machine learning and operations research where gradient information is unavailable or noisy, offering a robust alternative for practitioners.
The paper tackles the problem of maximizing monotone DR-submodular continuous functions without using gradient information, proposing a derivative-free algorithm called LDGM that achieves a (1-e^{-β}-ε)-approximation guarantee, matching the best gradient-based methods, and shows robustness under noise in empirical tests on budget allocation.
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.