Search papers, labs, and topics across Lattice.
This paper addresses the online maximization of nonnegative, non-monotone DR-submodular functions, achieving an online approximation factor of $0.401$, which matches the best known offline factor. The authors introduce an innovative algorithm that utilizes a weighted online learner to manage residual terms, circumventing the limitations of traditional offline constructions in dynamic environments. Their approach results in sublinear approximate regret and efficient oracle call usage, significantly improving upon existing adversarial online guarantees.
Achieving a $0.401$ online approximation factor for non-monotone DR-submodular maximization could redefine expectations for online optimization in adversarial settings.
We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at $1/e$. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has $O(T^{3/4})$ regret and uses $O(dT^{1/4})$ oracle calls per round. More generally, for every $\delta\in[0,1/4]$, batching gives $O(T^\delta)$ calls per round and $O(T^{4/5-\delta/5})$ regret, including a one-call $O(T^{4/5})$ endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with $O(T^{5/6})$ one-point bandit regret.
