{"id":"arxiv/2602.20578","url":"https://arxiv.org/abs/2602.20578","tags":["cs.LG","math.OC","stat.ML"],"score":0,"title":"Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets","domain":"cs.LG","source":"arxiv","authors":["Yiyang Lu","Haresh Jadav","Mohammad Pedramfar","Ranveer Singh","Vaneet Aggarwal"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-24","reactions":{}}