Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918353276239872 |
|---|---|
| author | Lu, Yiyang Jadav, Haresh Pedramfar, Mohammad Singh, Ranveer Aggarwal, Vaneet |
| author_facet | Lu, Yiyang Jadav, Haresh Pedramfar, Mohammad Singh, Ranveer Aggarwal, Vaneet |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20578 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets Lu, Yiyang Jadav, Haresh Pedramfar, Mohammad Singh, Ranveer Aggarwal, Vaneet Machine Learning Optimization and Control 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. |
| title | Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2602.20578 |