Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

Excerpt

arXiv:2610.00545v1 Announce Type: new Abstract: We study adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. A learner commits each action before observing its objective and competes with the best fixed action in hindsight. We prove a comparator-uniform first-order inequality that gives coefficient $4/9$, improving the online $0.401$ benchmark, with one gradient query and one projection per round and $O(\sqrt T)$ expected app