在线优化非单调子模函数,首次实现与离线最优相同的0.401逼近因子。
Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
- 设计新型在线学习器替代离线构造,通过加权机制控制残差项累积。
- 在条件无偏反馈下,实现0.401逼近因子,后悔值为O(T^{3/4})。
- 适用于对抗性环境,支持低查询次数(如单次调用)场景。
我们研究在d维单位立方体的紧凸下闭子集上对非负、非单调的DR-子模函数进行在线最大化。已知最优离线构造逼近因子为0.401,在相应元可解性假设下,而相应的对抗性在线保证长期停留在1/e。本文证明该因子同样可在在线设置中实现。在后决策全信息价值预言机模型下,算法在预言机反馈条件无偏且有界时,达到0.401逼近因子,且近似后悔值为次线性。在线算法不重复运行离线构造,而是用加权在线学习器替代依赖目标的盒子步长,累计控制所需残差项。精确的非对称平衡定理确保了即使面对对抗性变化,仍保持离线系数。直接实现具有O(T^{3/4})后悔值,每轮使用O(dT^{1/4})次预言机调用。更一般地,对任意δ∈[0,1/4],分批处理可实现每轮O(T^δ)次调用和O(T^{4/5−δ/5})后悔值,包括单次调用的端点情形(即O(T^{4/5}))。在正锚条件下,随机阻塞策略仍保持0.401逼近因子,且带单点惩罚的后悔值为O(T^{5/6})。
原文摘要 · Abstract (English)
We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at $1/e$. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has $O(T^{3/4})$ regret and uses $O(dT^{1/4})$ oracle calls per round. More generally, for every $\delta\in[0,1/4]$, batching gives $O(T^\delta)$ calls per round and $O(T^{4/5-\delta/5})$ regret, including a one-call $O(T^{4/5})$ endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with $O(T^{5/6})$ one-point bandit regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。