Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization

Abstract

We study online and offline maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets $K\subseteq [0,1{]}^d$ that contain a supplied diagonal point $\zeta 1$. Our online algorithm earns at least $\underline{\alpha }(\zeta )=\frac{1}{2}-\frac{(1-2\zeta {)}_{+}^2}{2(3-2\zeta {)}^2}$ times the reward of the best fixed feasible point, minus $O(\sqrt{T})$, using one possibly stochastic gradient query and one projection per round; $\underline{\alpha }(0)=4/9$. One post-decision noisy value query per round gives $O(T^{3/4})$ regret, and two exact value queries give $O(\sqrt{T})$. Conversely, no offline algorithm with polynomially many exact value-and-gradient queries attains a coefficient above an explicit ${\beta }_{\ast }\approx 0.4704$ at $\zeta =0$, improving the bound $2(e^{-1/2}-e^{-1})\approx 0.478$ of Oveis Gharan and Vondrák (2011); for $\zeta >0$, two families of hard instances give an upper bound that we reduce exactly to finitely many convex problems below $\zeta =1/8$ and give in closed form above it. The bound ${\beta }_{\ast }$ also holds for nonnegative submodular set functions under a cardinality constraint, improving the previous $0.478$. Online-to-offline conversion gives $\underline{\alpha }(\zeta )-\epsilon$ offline, and the upper bound also limits online learners with polynomial query budgets and uniform $O(T^{\kappa })$ regret, $\kappa <1$. Both coefficients equal $1/2$ for $\zeta \ge 1/2$ and fall short of $1/2$ by order $(1/2-\zeta {)}^2$ below. For quadratic objectives we attain $1/2$, and for cubic objectives $\max \{8/17,2\sqrt{3-4r}/(1+\sqrt{3-4r}{)}^2\}$ with $r=\min \{\zeta ,1/2\}$. For submodular set functions, rounding the multilinear extension gives $\underline{\alpha }(\zeta )-\epsilon$ under a matroid whose polytope contains $\zeta 1$ and $4/9-\epsilon$ under a fixed number of knapsack constraints.