拟阵约束下正则化次模最大化的参数化惩罚随机贪心算法

Parameterized Penalty Stochastic GreedyAlgorithm for Regularized SubmodularMaximization under Matroid Constraint

摘要: 在大数据分析、机器学习特征选择与传感器网络优化等应用中，常需要在结构化约束 (如拟阵约束) 下，从大量候选元素中选取一个子集以最大化收益并控制成本。该类问题可表述为正则 化次模最大化：g(S) = f (S) − c(S)，其中 f 为非负次模函数，c 为非负模函数。由于正则化项的引入可能使目标值为负，传统乘性近似比不再适用，因而需要采用双准则近似框架。本文提出一种参数化惩罚随机贪心算法：在每轮迭代中构造一个最大化∑_u∈M(f_u(S)−λc(u))的拟阵基，并从中均匀随机选择元素加入解集，其中 λ ≥ 1 为可调惩罚参数。我们给出严格的概率演化分析与完整推导，证明在假设 c(N ) ≤ 2c(OPT) 下，算法输出S_k 满足标准双准则保证$$\mathbb{E}[f(S_k)-c(S_k)]\ge \alpha f(OPT)-\beta (\lambda )c(OPT),\alpha =\frac{1+e^{-2}}{4},\beta (\lambda )=\lambda (1-e^{-2})$$。刻画了惩罚强度对成本系数的线性影响；通过求解 λ 的最优，我们得到 (0.283, 1) 的近似比保证。

Abstract: In applications such as big data analysis, machine learning feature selection, and sensor network optimization, it is often necessary to select a subset from a large set of candidate elements under structural constraints (e.g., matroid constraints) to maximize the profit while controlling the cost. This kind of problem can be formulated as regularized submodular maximization: g(S) = f(S) − c(S), where f is a nonnegative submodular function and c is a nonnegative modular function. Since the introduction of the regularization term may cause the objective value to be negative, the traditional multiplicative approximation ratio is no longer applicable, thus a bi-criteria approximation framework is required. This paper proposes a parameterized penalty stochastic greedy algorithm: in each round, it constructs a matroid basis that maximizes ∑_u∈M(f_u(S)−λc(u)), and then uniformly selects an element from this basis to add to the solution set, where λ ≥ 1 is an adjustable penalty parameter. We provide a rigorous probabilistic evolution analysis and complete derivation, proving that under the assumption c(N ) ≤ 2c(OPT), the output Sk satisfies the standard bi-criteria guarantee:$$\mathbb{E}[f(S_k)-c(S_k)]\ge \alpha f(OPT)-\beta (\lambda )c(OPT),\alpha =\frac{1+e^{-2}}{4},\beta (\lambda )=\lambda (1-e^{-2})$$. This characterizes the linear influence of the penalty strength on the cost coefficient; by solving for the optimal λ, we obtain an approximation guarantee of (0.283, 1).