오프라인 $0.401$ 계수와 일치하는 온라인 비단조 DR-준모듈 최대화
Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
한국어 초록
우리는 $d$차원 단위 hypercube의 compact convex down-closed 부분집합 위에서, 음이 아닌(nonnegative) 비단조 DR-준모듈 함수의 온라인 최대화를 연구한다. 대응하는 meta-solvability 가정 하에서 알려진 최고의 구성적(constructive) 오프라인 근사 계수는 $0.401$이며, 비교 가능한 적대적(adversarial) 온라인 보장은 $1/e$에 머물러 있었다. 우리는 이 계수가 온라인에서도 달성 가능함을 보인다. 사후 결정(post-decision) 완전 정보(full-information) 값 오라클(value-oracle) 모델에서, 오라클 피드백이 조건부 비편향(conditionally unbiased)이고 유계(bounded)일 때 우리 알고리즘은 $0.401$ 계수와 함께 sublinear 근사 regret을 달성한다. 온라인 알고리즘은 변하는 목적함수에 대해 오프라인 구성을 그대로 실행하지 않는다. 대신, 오프라인의 목적함수 의존 box step을 필요한 잔차(residual) 항들을 누적으로 제어하는 가중 온라인 learner로 대체한다. 정확한 비대칭 균형(asymmetric balance) 정리가 적대적 변화에도 불구하고 오프라인 계수를 보존한다. 직접 구현은 $O(T^{3/4})$ regret을 갖고 라운드당 $O(dT^{1/4})$번의 오라클 호출을 사용한다. 더 일반적으로, 모든 $\delta\in[0,1/4]$에 대해 배치(batching)는 라운드당 $O(T^\delta)$번의 호출과 $O(T^{4/5-\delta/5})$ regret을 주며, 호출 1회 $O(T^{4/5})$의 극단점을 포함한다. positive-anchor 조건 하에서, randomized blocking은 $O(T^{5/6})$ one-point bandit regret으로 $0.401$ 계수를 유지한다.
원문 초록
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 $δ\in[0,1/4]$, batching gives $O(T^δ)$ calls per round and $O(T^{4/5-δ/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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.02145v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.