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

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\mathbf{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_*\approx 0.4704$ at $\zeta=0$, improving the bound $2(e^{-1/2}-e^{-1})\approx 0.478$ of Oveis Gharan and Vondr\'ak (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_*$ also holds for nonnegative submodular set functions under a cardinality constraint, improving the previous $0.478$. Online-to-offline conversion gives $\underline{\alpha}(\zeta)-\varepsilon$ 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)-\varepsilon$ under a matroid whose polytope contains $\zeta\mathbf{1}$ and $4/9-\varepsilon$ under a fixed number of knapsack constraints.