在线非单调DR-子模最大化首破0.401！追平离线最优，遗憾仅O(T^¾)
Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
📖 AI 总结
该研究探讨了在线环境下非单调DR-子模函数的最大化问题，目标域为d维单位立方体的紧致凸向下闭子集。此前，离线场景下已知最优构造性近似因子为0.401，而对抗性在线算法的保证仅能达到1/e。本文首次证明该0.401因子在在线设定中同样可实现。其核心创新在于不直接对变化目标运行离线构造，而是引入加权在线学习器替代依赖目标的箱步，并借助精确非对称平衡定理在对抗性变化下保持离线系数。算法直接实现具备O(T^(3/4))的近似遗憾，每轮调用O(dT^(1/4))次预言机。通过批处理，可实现遗憾与调用次数的灵活权衡，包括单次调用下O(T^(4/5))遗憾的端点情形。此外，在正锚点条件下，随机阻塞策略能以O(T^(5/6))的单点强盗遗憾维持0.401因子。该成果弥合了在线与离线算法在非单调DR-子模最大化问题上的性能差距。
🔑 关键词速览
| DR-submodular | DR-子模性，一种连续子模函数性质，用于离散优化问题的连续松弛。 |
| approximation factor | 近似因子，衡量算法输出与最优解接近程度的比率。 |
| regret | 遗憾，在线学习算法中衡量累积损失与最优固定决策损失之差的指标。 |
| value-oracle model | 值预言机模型，一种查询模型，算法通过查询函数值来获取信息。 |
| bandit regret | 强盗遗憾，在部分反馈（仅观察到所选动作的收益）下的遗憾度量。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅