{"id":"arxiv/2608.12134","url":"https://arxiv.org/abs/2608.12134","tags":["cs.LG","cs.AI","cs.CC","math.OC"],"score":0,"title":"Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning","domain":"cs.LG","source":"arxiv","authors":["Vaneet Aggarwal"],"reviews":0,"subject":"cs.LG","summary":"We study nonnegative submodular maximization on $n$ elements subject to a general matroid of rank $k$, 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, given an error bound $ξ\\ge0$, under every controlled oracle $\\widehat f$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}