提出鲁棒贪心算法，可在对抗性噪声下稳定优化复杂约束的收益函数。
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning
- 基于泊松过程设计贪心交换策略，增强对噪声输入的抵抗力。
- 在非单调/单调目标下分别保持1/e和1-1/e的近似比，误差可控。
- 适用于带约束的在线学习场景，适合关注鲁棒优化的研究者。
研究在一般拟阵约束下，非负子模最大化问题在任意受控价值预言机下的离线优化。核心成果是针对挑衅式贪心交换泊松过程（SGS-Poisson）的对抗鲁棒性定理：不改变泊松强度、单元素交换规则或挑衅丢弃步骤，算法仍能保持极限近似比1/e（非单调）和1-1/e（单调）。具体地，对任意满足|f̂(S)−f(S)|≤ξ的受控预言机，算法返回可行集的期望值至少为(1/e−ε)OPT−O(kξ)和(1−1/e−ε)OPT−O(kξ)，仅需~O(nk²ε⁻²)次预言机查询。由此，离线到在线的转化导出全反馈上下文多臂老虎机（CMAB）算法，在一般拟阵约束下实现精确的极限近似-遗憾因子1/e与1−1/e，且总遗憾为~O(n¹ᐟ⁵k⁴ᐟ⁵T⁴ᐟ⁵)。
原文摘要 · Abstract (English)
We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)\OPT-O(kξ)$ and $(1-1/e-\varepsilon)\OPT-O(kξ)$, respectively, using $\widetilde O(nk^2\varepsilon^{-2})$ oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。