$γ$-약한 $θ$-상향 볼록성: DR-부분 모듈 함수 및 OSS 함수에 대한 응용을 갖는 선형화 가능한 비선형 최적화

$γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions

단조 비선형 함수 최적화는 머신 러닝 및 조합 최적화 분야에서 근본적인 과제입니다. 본 논문에서는 새로운 1차 조건인 $γ$-약한 $θ$-상향 볼록성을 소개하고 연구합니다. 이 조건은 광범위한 종류의 함수를 특징짓는 강력한 통합 프레임워크를 제공하며, DR-부분 모듈 함수와 One-Sided Smooth (OSS) 함수를 엄격하게 일반화합니다. 본 논문의 핵심 이론적 기여는 $γ$-약한 $θ$-상향 볼록 함수가 상향 선형화 가능하다는 것을 보여주는 것입니다. 즉, 어떤 실행 가능한 점에 대해서도 원래의 비선형 목적 함수를 근사하는 선형 대리 함수를 구성할 수 있으며, 이 근사 오차는 $γ$, $θ$ 및 실행 가능한 집합의 기하학적 구조에만 의존하는 상수 계수를 통해 제한됩니다. 이러한 선형화는 광범위한 문제에 대한 즉각적이고 통합된 근사 보장을 제공합니다. 특히, 표준적인 선형 최적화로의 환원을 통해 오프라인 최적화뿐만 아니라 정적 및 동적 후회 경계를 온라인 설정에서 통일적으로 제공합니다. 또한, 본 프레임워크는 DR-부분 모듈 최대화에 대한 최적의 근사 계수를 복구하고, 특히 매트료이드 제약 조건 하에서 기존의 OSS 최적화에 대한 근사 계수를 크게 개선합니다.

Optimizing monotone non-convex functions is a fundamental challenge across machine learning and combinatorial optimization. We introduce and study $γ$-weakly $θ$-up-concavity, a novel first-order condition that characterizes a broad class of such functions. This condition provides a powerful unifying framework, strictly generalizing both DR-submodular functions and One-Sided Smooth (OSS) functions. Our central theoretical contribution demonstrates that $γ$-weakly $θ$-up-concave functions are upper-linearizable: for any feasible point, we can construct a linear surrogate whose gains provably approximate the original non-linear objective. This approximation holds up to a constant factor, namely the approximation coefficient, dependent solely on $γ$, $θ$, and the geometry of the feasible set. This linearizability yields immediate and unified approximation guarantees for a wide range of problems. Specifically, we obtain unified approximation guarantees for offline optimization as well as static and dynamic regret bounds in online settings via standard reductions to linear optimization. Moreover, our framework recovers the optimal approximation coefficient for DR-submodular maximization and significantly improves existing approximation coefficients for OSS optimization, particularly over matroid constraints.