비단조 γ-약한 DR-부분합 가능 최대화 문제에 대한 더 강력한 근사 보장

Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization

머신러닝 및 최적화 분야에서 제약 조건 하에서 부분합 함수를 최대화하는 문제는 기본적인 문제입니다. 본 연구에서는 하위 집합에 대해 닫힌 볼록 집합에서 음수가 아닌, 비단조적인 γ-약한 DR-부분합 함수를 최대화하는 문제를 다룹니다. 주요 결과는 γ 값에 따라 부드럽게 변화하는 근사 보장을 제공하는 근사 알고리즘입니다. 특히, γ=1인 경우 (DR-부분합 함수인 경우) 0.401의 근사 계수를 얻으며, γ<1인 경우에도 기존의 γ-약한 DR-부분합 최대화 문제에 대한 근사 계수를 개선합니다. 본 연구의 접근 방식은 Frank-Wolfe 알고리즘 기반의 연속적인 탐욕적 방법과 γ 값을 고려한 이중 탐욕적 단계를 결합하여, 비단조성을 처리하는 간단하면서도 효과적인 절차를 제공합니다. 이러한 접근 방식을 통해, 하위 집합에 대해 닫힌 볼록 집합에서의 비단조 γ-약한 DR-부분합 최대화 문제에 대한 최첨단 수준의 근사 보장을 달성합니다.

Maximizing submodular objectives under constraints is a fundamental problem in machine learning and optimization. We study the maximization of a nonnegative, non-monotone $γ$-weakly DR-submodular function over a down-closed convex body. Our main result is an approximation algorithm whose guarantee depends smoothly on $γ$; in particular, when $γ=1$ (the DR-submodular case) our bound recovers the $0.401$ approximation factor, while for $γ<1$ the guarantee degrades gracefully and, it improves upon previously reported bounds for $γ$-weakly DR-submodular maximization under the same constraints. Our approach combines a Frank-Wolfe-guided continuous-greedy framework with a $γ$-aware double-greedy step, yielding a simple yet effective procedure for handling non-monotonicity. This results in state-of-the-art guarantees for non-monotone $γ$-weakly DR-submodular maximization over down-closed convex bodies.