Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

We study online maximization of non-monotone Diminishing-Return(DR)-submodular functions over down-closed convex sets, a regime where existing projection-free online methods suffer from suboptimal regret and limited feedback guarantees. Our main contribution is a new structural result showing that this class is $1/e$-Upper-Linearizable under carefully designed exponential reparametrization, scaling parameter, and surrogate potential, enabling a reduction to online linear optimization. As a result, we obtain optimal $O(T^{1/2})$ static regret with a single gradient query per round and unlock adaptive and dynamic regret guarantees, together with improved rates under semi-bandit, bandit, and zeroth-order feedback. Across all feedback models, our bounds strictly improve the state of the art.

(1) Problem: Imagine trying to pack a backpack for a trip where the usefulness of each item changes depending on what else you pack, and some combinations actually make your trip worse. In machine learning, this is called "non-monotone submodular maximization," a complex mathematical problem used for dynamic tasks like budget allocation or recommendation systems. When a computer must make these decisions on the fly (online) with very limited information, existing algorithms are either far too slow or make poor choices. (2) Solution: We discovered a mathematical shortcut that transforms this highly complex puzzle into a much simpler, straightforward path. By applying a specialized "exponential mapping," our framework safely unkinks the complicated reward landscape. We also built an efficient algorithm that takes only a single "glimpse" at the problem per round but still accurately estimates the best direction to proceed. (3) Impact: This breakthrough allows us to plug in standard, off-the-shelf optimization tools to solve the problem much faster and more accurately than before. It sets a new state-of-the-art performance standard for making robust, real-time decisions in unpredictable environments, paving the way for smarter resource management and AI systems.