Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets
This addresses online optimization for non-monotone submodular functions, a challenging problem in machine learning and operations research, with strictly improved state-of-the-art bounds.
The paper tackles online maximization of non-monotone DR-submodular functions over down-closed convex sets, where existing methods have suboptimal regret. It shows this class is 1/e-linearizable via exponential reparametrization, enabling reduction to online linear optimization and achieving O(T^{1/2}) static regret with one gradient query per round, with improved rates across feedback models.
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$-linearizable under carefully designed exponential reparametrization, scaling parameter, and surrogate potential, enabling a reduction to online linear optimization. As a result, we obtain $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.