매트로이드 위 포아송-과정 부분모듈러 최대화의 적대적 견고성: 견고한 오프라인 최적화에서 풀 밴딧 학습까지
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning
한국어 초록
일반 매트로이드 제약 하에서 비음(nonnegative) 부분모듈러 최대화를 연구하며, 오프라인 알고리즘이 임의의 제어된 값 오라클(controlled value oracle)을 받는 경우를 다룬다. 주요 결과는 Spiteful Greedy Swap Poisson Process(SGS-Poisson)에 대한 적대적 견고성 정리이다. 포아송 강도, 단일 원소 교환 규칙, spiteful drop 단계를 바꾸지 않아도, 비단조 목적함수에 대해서는 극한 근사비 $1/e$를, 단조 목적함수에 대해서는 $1-1/e$를 그대로 유지한다. 더 정확히, 모든 집합 $S$에 대해 $|\widehat f(S)-f(S)|\le ξ$를 만족하는 제어된 오라클 $\widehat f$마다, 구현은 각각 기대값이 최소 $(1/e-\varepsilon)\OPT-O(kξ)$ 및 $(1-1/e-\varepsilon)\OPT-O(kξ)$인 실행 가능한 집합을 $\widetilde O(nk^2\varepsilon^{-2})$회의 오라클 호출로 반환한다. 이에 따라 오프라인-온라인 환원은 일반 매트로이드 제약 부분모듈러 보상에 대한 풀 밴딧 CMAB 알고리즘을 주며, 극한 근사-후회(approximation-regret) 인수는 정확히 $1/e$와 $1-1/e$이고 후회는 $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$이다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2608.12134v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.