在线优化多个子模函数，提升选择目标的平均收益
Online Two-Stage Submodular Maximization
- 在线逐个揭示子模函数，动态优化候选集以提升平均性能
- 在一般拟阵约束下实现(1-1/e)²的次线性后悔率，均匀拟阵下更优
- 适用于影响力传播、数据摘要等场景，适合在线决策应用
给定一组单调子模函数，两阶段子模最大化（2SSM）的目标是限制基础集，使得从集合中随机选取的任一目标函数在受限集上优化时，其最大值的平均表现尽可能高。本文提出在线两阶段子模最大化（O2SSM）问题，其中子模目标函数以在线方式逐步揭示。针对加权阈值势函数这一重要且广泛的单调子模函数类（包括影响力传播、数据摘要和设施选址等），设计了一种算法，在一般拟阵约束下实现(1 - 1/e)²的次线性后悔率，在秩为k的均匀拟阵情况下达到(1 - 1/e)(1-e^{-k}k^k/k!)的后悔率；后者也构成了离线2SSM问题的最先进界。通过真实数据集实验验证了该在线算法的有效性。
原文摘要 · Abstract (English)
Given a collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) [Balkanski et al., 2016] is to restrict the ground set so an objective selected u.a.r. from the collection attains a high maximal value, on average, when optimized over the restricted ground set. We introduce the Online Two-Stage Submodular Maximization (O2SSM) problem, in which the submodular objectives are revealed in an online fashion. We study this problem for weighted threshold potential functions, a large and important subclass of monotone submodular functions that includes influence maximization, data summarization, and facility location, to name a few. We design an algorithm that achieves sublinear $(1 - 1/e)^2$-regret under general matroid constraints and $(1 - 1/e)(1-e^{-k}k^k/k!)$-regret in the case of uniform matroids of rank $k$; the latter also yields a state-of-the-art bound for the (offline) 2SSM problem. We empirically validate the performance of our online algorithm with experiments on real datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。