提出新方法实现非单调子模函数在线优化，显著提升精度与适应性。
Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets
- 通过指数重参数化将问题转化为线性优化，突破原有方法局限。
- 每轮仅需一次梯度查询，静态后悔率降至$O(T^{1/2})$。
- 适用于多种反馈场景，优于当前最优结果，适合高动态环境应用。
我们研究在向下闭凸集上对非单调的边际递减（DR）-子模函数进行在线最大化，该领域中现有无投影在线方法存在次优后悔率和有限反馈保证。主要贡献是提出一个新结构结果：在精心设计的指数重参数化、缩放参数和代理势能下，此类问题可实现$1/e$-线性化，从而可归约为在线线性优化。由此获得每轮仅需一次梯度查询的$O(T^{1/2})$静态后悔率，并解锁自适应与动态后悔保证，同时在半盲、盲和零阶反馈下实现更优速率。在所有反馈模型中，我们的界严格优于当前最优结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。