(ICML20) The FAST Algorithm for Submodular Maximization
经过悠长的摸鱼期终于还是感受到了情况的紧迫, 继否决了一票 idea 之后我将再次冲锋, 打算基于一个全新的想法来完成自己的 paper, 希望这次人没事. 本文将怀着忐忑不安的心情介绍一下 ICML 2020 的一篇 paper, 这篇文章将使用一种快速的并行算法, 在 \(\mathcal{O}(\log(n)\log^2(\log k))\) 的自适应轮数以及 \(\mathcal{O}(n\log\log k)\) 的 query 数内重新给出单调次模函数的 \(k\) 基数约束这一经典问题的 \(1-1/\mathrm e\) 近似解.
Preliminaries
我们使用 adaptivity 来衡量并行时间复杂度, 即有多项式数量的 query 被并行处理的轮数. 例如简单贪心算法的 adaptivity 是 \(\mathcal O(k)\), 最差为 \(\mathcal O(n)\). 最近出现的 adaptive sampling 框架对该问题可在 \(\mathcal O(\log n)\) 轮数下给出常数近似比, 并且也已经有人将该思想从最初的 \(1/3\) 近似比 improve 到 \(1-1/\mathrm e\) 的最佳近似比. 但作者指出目前的算法存在 "the logarithmic parallel runtime of algorithms in this genre carries extremely large constants and polynomial dependencies on precision and confidence parameters that are hidden in their asymptotic analysis" 这样的问题, 例如若想以 \(95\%\) 的置信度取得 \(1-1/\mathrm e-0.1\) 的近似比时每轮需要采样的集合数就达到了 \(10^6\sim10^8\) 量级.
本文所作的贡献就在于保证渐近近似比一定的情况下, 使得算法在非渐近最差情形下 query 复杂度和运行轮数 (实际运行时间) 能维持在一个较低的水平, 为此使用到了 adaptive sequencing 和 multiple optimization 的技术.
Algorithms
我们首先从一个简单版本的算法开始.
这里 \(\text{SEQ}(X,k)\) 是从集合 \(X\) 中等概率随机取样的一个 \(k\) 元素排列. 可以看出有关系 \(X_k\subset X_{k-1}\subset\cdots\subset X_1\), 我们取 \(i^*\) 使得 \(|X_{i^*}|\leq(1-\epsilon)|X|<X_{i^*-1}\), 然后将 \(a_1,\dots,a_{i^*-1}\) 加入到 \(S\) 中并且将 \(X\) 的占至少 \(\epsilon\) 部分的 marginal gain 小于门槛值 \(t\) 的元素删去.
算法 Alg. 1 包括内外两个循环, 对于一个外循环, 由 \(|X|=0\) 为终止条件知内循环次数 \(i\) 满足 \((1-\epsilon)^in\geq1\), 故内循环轮数不超过 \(\epsilon^{-1}\log n\), 总的 adaptivity 复杂度为 \(\mathcal O(\epsilon^{-2}\log n)\). 对每个内循环, 我们至多要计算 \(k|X|\) 次 marginal gain, 故 query 复杂度为 \(\mathcal O\Big(\epsilon^{-1}\sum_{i=1}^{\epsilon^{-1}\log n}k(1-\epsilon)^in\Big)=\mathcal O(\epsilon^{-2}nk)\).
下面分析近似比.
Proof of Lemma 1: 由 \(|S_{i+1}|<k\) 可知在第 \(i\) 轮外循环结束时 \(X=\emptyset\). 这表明对任一 \(e\in N\backslash S_{i+1}\), \(e\) 都在第 \(i\) 轮外循环的某一内循环中因对某时刻 solution 集合 \(S\) 的 marginal gain 小于门槛值而被舍弃, 这里 \(S_i\subset S\subset S_{i+1}\). 故由次模性得 \[ f(O)-f(S_{i+1})\leq\sum_{e\in O\backslash S_{i+1}}f(e\mid S_{i+1})\leq\sum_{e\in O\backslash S_{i+1}}\frac{(1-\epsilon)(f(O)-f(S_i))}{k}\leq(1-\epsilon)(f(O)-f(S_i)) \] 整理后即得 Lemma 1 结论.
Proof of Lemma 2: 由于 \(a_i\) 是从 \(X\) 中等概率选取的元素, 且对 \(i<i^*\) 都有 \(|X_i|\geq(1-\epsilon)|X|\), 故 \[ \mathbb E_{a_i}[f(a_i\mid S\cup\{a_1,\dots,a_{i-1}\})]\geq\mathrm{Pr}_{a_i}[f(a_i\mid S\cup\{a_1,\dots,a_{i-1}\})\geq t]\cdot t\geq(1-\epsilon)^2(f(O)-f(S))/k \]
Proof of Theorem 1: 分情况讨论.
- 若算法不因违反 \(|S|<k\) 结束, 即 \(\epsilon^{-1}\) 次外循环全部完成了. 设 \(S_1,\dots,S_{\epsilon^{-1}}\) 依次为这 \(\epsilon^{-1}\) 次外循环中每次循环下的 solution 集合 \(S\). 由 Lemma 1 知每次循环使得目标函数值增加至少 \(t\), 即 \[ f(S_i)\geq f(S_{i-1})+\epsilon(f(O)-f(S_{i-1})) \] 递推易得 \(f(S_i)\geq\Big(1-(1-\epsilon)^i\Big)f(O)\). 再由 \(1-x\leq\mathrm e^{-x}\) 就得 \(f(S_{\epsilon^{-1}})\geq(1-\mathrm e^{-1})f(O)\).
- 若算法因 \(|S|\geq k\) 退出, 我们设 \(S_i\) 代表 \(S\) 中按序加入的前 \(i\) 个元素所构成的集合, 不妨 \(S_{i}=S_{i-1}\cup\{a_i\}\). 则利用 Lemma 2 中结论 \[ \begin{aligned} \mathbb E_{a_i}[f(a_i\mid S_{i-1})]=&\mathbb E_{a_i}[f(a_i\mid S'\cup\{e_1,\dots,e_{j}\})]\\ \geq&(1-\epsilon)^2\frac{f(O)-f(S')}{k}\\ \Rightarrow \mathbb E[f(S_{i}\mid S_{i-1})]\geq&(1-\epsilon)^2\frac{f(O)-f(S_{i-1})}{k} \end{aligned} \] 这里 \(S'\) 是该轮 \(S\) 的初始值. 故类似地 \[ \begin{aligned} f(S_k)\geq&\bigg(1-\Big(1-\frac{(1-\epsilon)^2}{k}\Big)^k\bigg)f(O)\geq\Big(1-\mathrm e^{-(1-\epsilon)^2}\Big)f(O)\\ \geq&\Big(1-\mathrm e^{-(1-2\epsilon)}\Big)f(O)\geq(1-\mathrm e^{-1}(1-4\epsilon))f(O)\geq\Big(1-\mathrm e^{-1}-\frac32\epsilon\Big)f(O) \end{aligned} \]
现在我们可以考虑完整版的算法了. 该算法将不再假设 \(f(O)\) 已知, 且由于二分搜索和采样方法的引入降低了 query 复杂度.
可以看到主算法 Alg. 2 用了常用的 sieve 手段解决 \(f(O)\) 未知的问题. \(\text{GEOMETRIC}(a,b,q), (a<b,0<q<1)\) 生成一个从 \(a\) 到 \(b\) 的公比为 \(q^{-1}\) 的等比数列 (筛子), 然后我们在这个有序数组中二分查找满足 \(1-e^{-1}\) 近似要求的最大 \(v\) 即可 (\(v\) 即是我们对 \(f(O)\) 的近似).
Alg. 3 稍显复杂, 但原理与 Alg. 1 类似. 首先生成 \(X\) 的一个均匀分布随机排列 \(\text{SEQ}(X,|X|)\), 然后将对 \(S\cup A_{i-1}\) marginal gain 大于门槛值 \(t\) 的 \(a_i\) 加入到 \(S\) 中. 接下来我们确定 \(i^*\) 是使得 \(X\) 中对于 \(S\cup A_{i^*-1}\) 的 marginal gain 大于门槛值的元素足够多 (比例不小于 \(1-2\epsilon\)) 的最大标号. 这里为了效率起见, 我们不再对 \(X\) 中每个元素进行检验, 而是提前取样一个从 \(X\) 中均匀概率选取 \(m\) 个元素构成的集合 \(\text{SAMPLE}(X,m)\).