论文标题
局部单酮自适应下调最大化
Partial-Monotone Adaptive Submodular Maximization
论文作者
论文摘要
许多顺序决策问题，包括基于池的主动学习和自适应病毒营销，可以作为适应性的下调最大化问题。关于自适应下调优化的大多数研究都集中在单调病例或非单调酮病例上。具体而言，如果效用函数是单调的，并且自适应下调，则\ cite {golovin2011Adaptive}制定了一种贪婪的策略，该策略实现了$（1-1/e）$的近似值，但受基质约束。如果实用程序函数是非单调性的，并且自适应下调，则\ cite {Tang2021beyond}表明，随机贪婪的策略实现了$ 1/e $ $ $的近似比，但受到基数约束。在这项工作中，我们旨在通过研究部分单键酮自适应下调最大化问题来概括上述结果。为此，我们介绍了[0,1] $中的自适应单调性比$ m \的表示法，以测量功能的单调性程度。我们的主要结果是表明，如果实用程序功能为$ M $ - 适应性单调和自适应子模块，则随机贪婪政策的近似值为$ m（1-1/e）+（1-m）（1-m）（1/e）$。值得注意的是，当$ m = 0 $和$ m = 1 $时，此结果将恢复上述$（1-1/e）$和$ 1/e $ $近似值。我们进一步扩展了结果，以考虑背包约束。我们表明，如果实用程序功能为$ M $ $ - 自适应单调和自适应supsodular，则基于抽样的策略的近似值为$（m+1）/10 $。我们结果的一个重要含义是，即使对于非马可分子实用程序函数，如果此函数与单调函数``clote''，我们仍然可以达到接近$（1-1/e）$的近似值。对于许多机器学习应用程序，其实用程序功能几乎是自适应单调的，这会改善性能界限。
Many sequential decision making problems, including pool-based active learning and adaptive viral marketing, can be formulated as an adaptive submodular maximization problem. Most of existing studies on adaptive submodular optimization focus on either monotone case or non-monotone case. Specifically, if the utility function is monotone and adaptive submodular, \cite{golovin2011adaptive} developed a greedy policy that achieves a $(1-1/e)$ approximation ratio subject to a cardinality constraint. If the utility function is non-monotone and adaptive submodular, \cite{tang2021beyond} showed that a random greedy policy achieves a $1/e$ approximation ratio subject to a cardinality constraint. In this work, we aim to generalize the above mentioned results by studying the partial-monotone adaptive submodular maximization problem. To this end, we introduce the notation of adaptive monotonicity ratio $m\in[0,1]$ to measure the degree of monotonicity of a function. Our main result is to show that a random greedy policy achieves an approximation ratio of $m(1-1/e)+(1-m)(1/e)$ if the utility function is $m$-adaptive monotone and adaptive submodular. Notably this result recovers the aforementioned $(1-1/e)$ and $1/e$ approximation ratios when $m = 0$ and $m = 1$, respectively. We further extend our results to consider a knapsack constraint. We show that a sampling-based policy achieves an approximation ratio of $(m+1)/10$ if the utility function is $m$-adaptive monotone and adaptive submodular. One important implication of our results is that even for a non-monotone utility function, we still can achieve an approximation ratio close to $(1-1/e)$ if this function is ``close'' to a monotone function. This leads to improved performance bounds for many machine learning applications whose utility functions are almost adaptive monotone.
