(ICML20) Streaming Algorithms for M$k$SC under Noise

发表于 2020-11-16 更新于 2020-11-26 分类于学习，算法阅读次数：

本文字数： 20k

这几年次模优化里做 $k$-submodular 的开始多起来了, 不过目前不管是 offline 还是 streaming setting 下, 大多做的都是无约束的最大化算法. 而基数约束问题 Maximize a $k$-submodular function subject to Size Constraint (M$k$SC) 的研究还较少, 且也仅限于单调函数的情况. ICML2020 里出现了一篇研究 streaming 下的 non-monotone M$k$SC 算法的文章, 且文章还假设了对 objective function 的 query 是困难的, 只能间接获得一个 (有 bound 保证的) 真实值的估计 (就是所谓带噪数据). 这篇博文在介绍一下该论文的同时, 也是对 $k$ 次模函数的一个简单调研.

Preliminaries

$k$-submodular function

$k$-submodular 函数是 submodular 函数的自然 extension. 给定 ground set 为 $V$, 定义 $V$ 上的 $k$-tuple 是 $k$ 个两两不交子集作为分量的 $k$ 维向量, 即 \[ (k+1)^{V}:=\{(S_1,\dots,S_k):S_i\subseteq V,S_i\cap S_j=\emptyset,\ \forall i\neq j,\ i,j\in[k]\} \] 称函数 $f:(k+1)^{V}\to\mathbb{R}_{\geq0}$ 是 $k$-submodular 的, 若对 $(k+1)^{V}$ 里的任意两个元素 $S=(S_1,\dots,S_k)$ 和 $T=(T_1,\dots,T_k)$ 都有 \[ f(S)+f(T)\geq f(S\sqcap T)+f(S\sqcup T) \] 其中 \[ \begin{aligned} & S\sqcap T := (S_1\cap T_1,\dots,S_k\cap T_k)\\ & S\sqcup T := \bigg((S_1\cup T_1)\Big\backslash\Big(\bigcup_{i\in[k]\backslash\{1\}}(S_i\cup T_i)\Big),\dots,(S_k\cup T_k)\Big\backslash\Big(\bigcup_{i\in[k]\backslash\{k\}}(S_i\cup T_i)\Big)\bigg) \end{aligned} \]

Notations and properties

对 $\mathbf{x}=(X_1,\dots,X_k)\in(k+1)^V$, 令 $\text{supp}(\mathbf{x})=\cup_{i\in[k]}X_i$, 且记 $\mathbf{x}$ 特征函数为 \[ \mathbf{x}(e)=\begin{cases} i,& \text{if}\ e\in X_i \\ 0,& \text{if}\ e\in V\backslash\text{supp}(\mathbf{x}) \end{cases} \] 为方便起见, 记 $|\mathbf{x}|=|\text{supp}(\mathbf{x})|$. 特别地, 我们记 $\mathbf{x}=\langle e,i\rangle$, 若 $\mathbf{x}(e)=i,\mathbf{x}(e')=0,\forall e'\in V\backslash\{e\}$. 另外, 我们记 $i$ 方向的 marginal gain 为 \[ \Delta_{e,i}f(\mathbf{x})=f(\mathbf{x}\sqcup\langle e,i\rangle)-f(\mathbf{x}) \] 特别地, 若 $\Delta_{e,i}f(\mathbf{x})\geq0$ 对任意 $\mathbf{x}\in(k+1)^V,\mathbf{x}(e)=0$ 成立, 我们就说这个 $k$-submodular 函数是单调的.
对 $(k+1)^V$ 中的元素 $\mathbf{x}=(X_1,\dots,X_k)$ 和 $\mathbf{y}=(Y_1,\dots,Y_k)$, 我们记 $\mathbf{x}\sqsubseteq\mathbf{y}$, 若 $X_i\subseteq Y_i$, $\forall i\in[k]$. 显然, 由次模性我们可以推出 \[ \Delta_{e,i}f(\mathbf{y})\leq \Delta_{e,i}f(\mathbf{x}),\ \forall \mathbf{x}\sqsubseteq\mathbf{y},\mathbf{y}(e)=0 \] 另外由次模性我们可以得到 $k$-submodular 函数所谓 pairwise-monotone 的重要性质: \[ \Delta_{e,i}f(\mathbf{x})+\Delta_{e,j}f(\mathbf{x})\geq0,\ \forall \mathbf{x}\in(k+1)^V,\mathbf{x}(e)=0,i,j\in[k],i\neq j \]
称函数 $F:(k+1)^V\to\mathbb{R}$ 是 $f$ 的 $\epsilon$-estimate, 若 \[ (1-\epsilon)f(\mathbf{x})\leq F(\mathbf{x})\leq (1+\epsilon)f(\mathbf{x}),\ \forall\mathbf{x}\in(k+1)^V \]

Problem definition

给定一个有限集合 $V$, 一个 $k$-submodular 函数 $f$ 的 $\epsilon$-estimate $F$ 和一个正整数 $B$, 我们要解决如下问题 \[ \begin{aligned} \text{Maximize}&\quad f(\mathbf{s}) \\ \text{Subject to}&\quad \mathbf{s}\in(k+1)^V,\ |\mathbf{s}|\leq B \end{aligned} \] 这个问题是 NP 难的 (并且我们仅知道带噪数据 $F$, 且 streaming setting 下只能最多进行一次遍历全体数据 $V$ 的操作), 所以我们只能去寻求效果最好的近似解. 记理论上的一个最优解为 $\mathbf{o}$, 即 $f(\mathbf{o})=\text{max}_{|\mathbf{s}|\leq B}f(\mathbf{s})$. 容易看出 $k=1$ 时就是基数约束下的次模优化问题.

Algorithms

文章首先提出了已知 $f(\mathbf{o})$ 的值的确定性算法.

(Alg. 1) DStream with known $f(\mathbf{o})$

input $V,F,k,B,M$ and $o,\gamma$ s.t. $f(\mathbf{o})\geq o\times B\geq f(\mathbf{o})/(1+\gamma)$
initiate $\mathbf{s}^0=\{\emptyset,\dots,\emptyset\}$, $t=0$
for each $e\in V$:
if $|\mathbf{s}^t|<B$:
find $i=\text{argmax}_{i'\in [k]}F(\mathbf{s}^t\sqcup\langle e,i'\rangle)$
if $\frac{F(\mathbf{s}^t\sqcup\langle e,i\rangle)}{1-\epsilon}\geq(t+1)\frac{o}{M}$:
$\mathbf{s}^{t+1}=\mathbf{s}^t\sqcup\langle e,i\rangle$
$t=t+1$
return $\mathbf{s}^t$ if $f$ is monotone; $\text{argmax}_{\mathbf{s}\in\{\mathbf{s}^j:j\leq t\}}F(\mathbf{s})$ if $f$ is non-monotone.

可以看出这个算法的开始类似梯度下降: 在每一轮对新的元素 $e$ 的处理时, 首先选择一个下降速度最快的方向 $i$. 接着算法使用 $\frac{F}{(1-\epsilon)(t+1)}$ 来近似 (往大了取) 当前平均值 $\frac{f}{t+1}$, 通过判断这个值和预先设定好的 threshold 值 $\frac{o}{M}$ 的大小关系来决定是否将 $e$ 加入到集合中. (即, 排除掉那些对集合贡献不大的元素.)

Proposition 1

If $\mathbf{s}$ is an output of Alg. 1 under monotone case, then it satisfies \[ f(\mathbf{o})\leq\max\Big\{(1+\gamma)(1+\epsilon),\frac{2+4B\epsilon}{M-1}\Big\}\frac{M}{1-\epsilon}f(\mathbf{s}) \]

如下为未知 $f(\mathbf{o})$ 的值时的确定性算法.

(Alg. 2) DStream without known $f(\mathbf{o})$

input $V,F,k,B,M>1,\gamma>0$
initiate $\Delta_u=\Delta_l=\Delta=0$, $t_j=0,\forall j\in\mathbb{Z}^+$
for each $e\in V$:
$\Delta=\max\{\Delta,\max_{j\in[k]}F(\langle e,j\rangle)\}$
$\Delta_u=\Delta\big/(1-\epsilon),\ \ \Delta_l=\Delta\big/((1+\epsilon)(1+\gamma))$
$O=\{(1+\gamma)^j\ |\ \frac{\Delta_l}{BM}\leq(1+\gamma)^j\leq(1+\epsilon)\Delta_u\}$
for each $j$ s.t. $(1+\gamma)^j\in O$:
$o=M(1+\gamma)^j$
if $t_j<B$:
$i=\text{argmax}_{j'\in[k]}F(\mathbf{s}_j^{t_j}\sqcup\langle e,j'\rangle)$
if $\frac{F(\mathbf{s}_j^{t_j}\sqcup\langle e,i\rangle)}{1-\epsilon}\geq(t_j+1)\frac{o}{M}$:
$\mathbf{s}_j^{t_j+1}=\mathbf{s}_j^{t_j}\sqcup\langle e,i\rangle$
$t_j=t_j+1$
return $\text{argmax}_{\mathbf{s}_j^{t_j}:j\in O}F(\mathbf{s}_j^{t_j})$ if $f$ is monotone; $\text{argmax}_{\mathbf{s}_j^{i}:i\leq t_j,j\in O}F(\mathbf{s}_j^{i})$ if $f$ is non-monotone.

这个算法的大致思路仍类似经典的 sieve streaming: 当我们不知道 $f(\mathbf{o})$ 时, 想办法构造一个包含 $[\frac{f(\mathbf{o})}{(1+\gamma)B},\frac{f(\mathbf{o})}{B}]$ 的区间, 并在该区间内散布诸多 sieve 以期望其中有一个 sieve 能达到 Alg. 1 中 $o$ 的效果. 那么此时这个区间该如何估计? 由于 $F$ 的 $\epsilon$-estimate 性质, 必然有 \[ (1-\epsilon)\max_{|\mathbf{x}|=1}f(\mathbf{x})\leq\max_{|\mathbf{x}|=1}F(\mathbf{x})\leq(1+\epsilon)\max_{|\mathbf{x}|=1}f(\mathbf{x}) \] 利用次模性, 所以 $\Delta_u=\max_{|\mathbf{x}|=1}\frac{F(\mathbf{x})}{1-\epsilon}$ 就可作为 $\frac{f(\mathbf{o})}{B}$ 的一个 upper bound, $\Delta_l/B=\max_{|\mathbf{x}|=1}\frac{F(\mathbf{x})}{(1+\epsilon)(1+\gamma)B}$ 可作为 $\frac{f(\mathbf{o})}{(1+\gamma)B}$ 的一个 lower bound. 所以 sieve 集合 $\{(1+\gamma)^j\ |\ j\in\mathbb{Z},\frac{\Delta_l}{BM}\leq(1+\gamma)^j\leq\frac{\Delta_u}{M}\}$ 中就存在 $v$ 使得 $vM$ 是 $o$ 的一个理想值, $v$ 所对应的集合 $S_v$ 就是我们想要的估计值. 有了这个区间和筛子, 我们对每个到来的元素都分别对各个筛子过一遍 Alg. 1 就可以了.

那么现在的问题是, 我们并不能提前知道所有单元素集合中使得 $f$ 最大的那个. 所以算法中对上下界 $\Delta_u,\Delta_l$ 采取了 lazy estimation 的做法: 即取当前所见过的单元素集合的最大值. 事实上, 下界因为变小了, 对算法的正确性并没有什么影响, 而上界可能损失一些性质比较好的集合. 所以我们调整上界到让算法能包含当前能使得 $S_v$ 非空的最大的 $v$. 由于 \[ \frac{F(\mathbf{s})}{1+\epsilon}\leq |\mathbf{s}|\max_{\mathbf{s}(e)\neq0,i\in[k]}\frac{F(\langle e,i \rangle)}{1-\epsilon} \] 故不等式 \[ \frac{F(\mathbf{s})}{1-\epsilon}>\frac{(1+\epsilon)|\mathbf{s}|}{1-\epsilon}\max_{\mathbf{s}(e)\neq0,i\in[k]}\frac{F(\langle e,i \rangle)}{1-\epsilon} \] 必然不成立, 这启发我们取 $\frac{o}{M}=M'(1+\epsilon)\Delta_u$, 这里 $M'$ 是可以任取一个大于 $\frac{1}{1-\epsilon}$ 的常数. 所以算法的 sieve 集合可取为 \[ \Big\{(1+\gamma)^j\ |\ j\in\mathbb{Z},\frac{\Delta_l}{BM}\leq(1+\gamma)^j\leq\frac{M'}{M}(1+\epsilon)\Delta_u\Big\} \] (这里跟原文取的不太一样, 原文中对应这里直接取了 $M'=M$, 有点令人费解. 另外原算法中 $j$ 仅取正整数其实是没有道理的, 因为根据我们的分析 $j$ 完全是可以取到负值的.)

Proposition 2

DStream has query complexity of $O\bigg(\frac{|V|k}{\gamma}\log\Big(\frac{(1+\epsilon)(1+\gamma)}{1-\epsilon}BM\Big)\bigg)$ and takes $O\bigg(\frac{B}{\gamma}\log\Big(\frac{(1+\epsilon)(1+\gamma)}{1-\epsilon}BM\Big)\bigg)$ memory. If $f$ is monotone, the approximation ratio is \[ \frac{1+\epsilon}{(1-\epsilon)^2}\min_{x\in(1,M]}\max\bigg\{(1+\gamma)(1+\epsilon)x,\frac{(2+4B\epsilon)x}{x-1}\bigg\} \] If $f$ is non-monotone, then the ratio is \[ \frac{1+\epsilon}{(1-\epsilon)^2}\min_{x\in(1,M]}\max\bigg\{(1+\gamma)(1+\epsilon)x,\frac{(3+4\epsilon+6\epsilon B+\epsilon^2+2\epsilon^2 B)x}{(1-\epsilon)(x-1)}\bigg\} \]

下面介绍论文提出的一个随机算法.

(Alg. 3) RStream

input $V,F,k,B,M>1,\gamma>0,\eta\geq1$
initiate $\Delta_u=\Delta_l=\Delta=0$, $t_{j,\epsilon'}=0,\forall j\in\mathbb{Z}^+,\epsilon'\in\mathbb{R}^+$
for each $e\in V$:
$\Delta=\max\{\Delta,\max_{j\in[k]}F(\langle e,j\rangle)\}$
$\Delta_u=\frac{(1+\epsilon)^2+4\epsilon B}{(1-\epsilon^2)(1-\epsilon)}\Delta,\ \ \Delta_l=\Delta\big/((1+\epsilon)(1+\gamma))$
$O=\{(1+\gamma)^j\ |\ \frac{\Delta_l}{BM}\leq(1+\gamma)^j\leq\Delta_u\}$
for each $j$ s.t. $(1+\gamma)^j\in O$:
$o=M(1+\gamma)^j$
for each $\epsilon'=\epsilon,\frac{(\eta-2)\epsilon}{\eta-1},\frac{(\eta-3)\epsilon}{\eta-1},\dots,0$:
if $t_{j,\epsilon'}<B$:
for each $i\in[k]$:
$d_i=\frac{F(\mathbf{s}_{j\epsilon'}^{t_{j,\epsilon'}}\sqcup\langle i,e\rangle)}{1-\epsilon'}-\frac{F(\mathbf{s}_{j\epsilon'}^{t_{j,\epsilon'}})}{1+\epsilon'}$
$d_i=0$ if $d_i<\frac{o}{M}$
$T=|\{i\ |\ d_i>0\}|$
$D=\sum_{i\in[k]}d_i^{T-1}$
if $t_{j,\epsilon'}<B$ and $T>0$:
if $T=1$:
$i=$ the only one that $d_i>0$
else:
$i=$ selected with prob. $d_i^{T-1}\big/D$
$\mathbf{s}_{j,\epsilon'}^{t_{j,\epsilon'}+1}=\mathbf{s}_{j,\epsilon'}^{t_{j,\epsilon'}}\sqcup\langle e,i\rangle$
$t_{j,\epsilon'}=t_{j,\epsilon'}+1$
return $\text{argmax}_{\mathbf{s}_{j,\epsilon'}^{t_{j,\epsilon'}}:j\in O}F(\mathbf{s}_{j,\epsilon'}^{t_{j,\epsilon'}})$ if $f$ is monotone; $\text{argmax}_{\mathbf{s}_{j,\epsilon'}^{i}:i<t_{j,\epsilon'},j\in O}F(\mathbf{s}_{j,\epsilon'}^{i})$ if $f$ is non-monotone.

类似之前的想法, 我们仍然需要找出一个合适的 $o$ 使得 $f(\mathbf{o})\geq oB\geq f(\mathbf{o})\big/(1+\gamma)$. 但是我们不会直接使用 $\text{argmax}$ 方向, 而是对所有 marginal gain 超过 threshold 的方向按比例随机选择其一来加入到 $\mathbf{s}$ 中: 首先我们使用 $d_i$ 来"近似"表达 marginal gain, (因子 $1/(1-\epsilon),1/(1+\epsilon)$ 是为了考虑到 $F(\mathbf{s}\sqcup\langle e,i\rangle)<F(\mathbf{s})$ 最坏的情况.) 并且我们将没有超过 threshold 的 $d_i$ 置零. 然后按概率 \[ \mathrm{Pr}[\langle e,i\rangle\ \text{is added to }\mathbf{s}] = d_i^{T-1}\Big/\sum_{j\in[k]}d_j^{T-1} \] 进行选择, $T=|\{i\ |\ d_i>0\}|$.

这样简单的处理有一个问题: $d_i$ 作为我们想要求的 $f(\langle e,i\rangle|\mathbf{s})$ 估计值可能效果很差. 例如若 $F(\mathbf{s})\approx f(\mathbf{s})=f(\mathbf{s}\sqcup\langle e,i\rangle)\approx F(\mathbf{s}\sqcup\langle e,i\rangle)$, 此时 $d_i\approx\frac{2\epsilon}{1-\epsilon^2}f(\mathbf{s})$, 这可能使得选择方向 $i$ 的几率非零, 即使真实的 marginal gain 此时为 0. 为了解决这个问题, 文章在算法中引入了 $\eta$ 来将 $\epsilon$ 拆分成一系列 $\epsilon'(\to0)$ 来实现某种去随机化的效果: 对每个 $\epsilon'$, 将 $F$ 视作 $\epsilon'$-estimate 进行计算, 即对每个 sieve $j$, 都有一串 $\{t_{j,\epsilon'}\}_{\epsilon'}$ 来记录各个 $\epsilon'$ 下集合的大小.

那么这个时候的 $\Delta_u$ 如何选择? 首先 \[ \frac{F(\mathbf{s}\sqcup\langle i,e\rangle)}{1-\epsilon}-\frac{F(\mathbf{s})}{1+\epsilon}=\frac{1}{1-\epsilon^2}\Big(F(\mathbf{s}\sqcup\langle i,e\rangle)-F(\mathbf{s})+\epsilon\big(F(\mathbf{s}\sqcup\langle i,e\rangle)+F(\mathbf{s})\big)\Big) \] 注意到 \[ \begin{aligned} F(\mathbf{s}\sqcup\langle i,e\rangle)-F(\mathbf{s})\leq&(1+\epsilon)f(\mathbf{s}\sqcup\langle i,e\rangle)-(1-\epsilon)f(\mathbf{s})\\ =&f(\mathbf{s}\sqcup\langle i,e\rangle)-f(\mathbf{s})+\epsilon\big(f(\mathbf{s}\sqcup\langle i,e\rangle)+f(\mathbf{s})\big)\\ \leq&\frac{\Delta}{1-\epsilon}+2B\epsilon\Delta \end{aligned} \] 故可取 (和原文仍稍有出入) \[ \frac{1}{1-\epsilon^2}\Big(\frac{\Delta}{1-\epsilon}+2B\epsilon\Delta+2B(1+\epsilon)\epsilon\Delta\Big)\leq\frac{1+4B\epsilon}{(1-\epsilon^2)(1-\epsilon)}\Delta=\Delta_u \]

Proposition 3

RStream has query complexity of $O\bigg(\frac{\eta|V|k}{\gamma}\log\Big(\frac{(1+\gamma)((1+\epsilon)^2+4\epsilon B)}{(1-\epsilon)^2}BM\Big)\bigg)$ and takes $O\bigg(\frac{\eta B}{\gamma}\log\Big(\frac{(1+\gamma)((1+\epsilon)^2+4\epsilon B)}{(1-\epsilon)^2}BM\Big)\bigg)$ memory. If $f$ is monotone, the approximation ratio is \[ \frac{1+\epsilon}{1-\epsilon}\min_{x\in(1,M]}\max\bigg\{\frac{(1+\epsilon+2B\epsilon)(1+\gamma)x}{1-\epsilon},\Big(\frac{(1+\epsilon)^2+4B\epsilon}{1-\epsilon^2}(1-k^{-1})+1\Big)\frac{kx}{kx-k-1}\bigg\} \] If $f$ is non-monotone, then the ratio is \[ \frac{1+\epsilon}{1-\epsilon}\min_{x\in(1,M]}\max\bigg\{\frac{(1+\epsilon+2B\epsilon)(1+\gamma)x}{1-\epsilon},\frac{(3k-2)(1+\epsilon)^2+(8k-8)\epsilon B}{(1-\epsilon)^2}\frac{x}{kx-k-2}\bigg\} \]

Greedy on $F$

现在我们考虑直接使用 greedy 算法的效果.

(Alg. 4) Greedy Algorithm

input $V,F,k,B$
initiate $\mathbf{s}^0=\{\emptyset,\dots,\emptyset\}$
for $t=1$ to $B$:
$e,i=\text{argmax}_{e\in V\backslash\text{supp}(\mathbf{s}),i\in[k]}F(\mathbf{s}^{t-1}\sqcup\langle e,i\rangle)$:
$\mathbf{s}^{t}=\mathbf{s}^{t-1}\sqcup\langle e,i\rangle$
return $\mathbf{s}^B$ if $f$ is monotone; $\text{argmax}_{\mathbf{s}\in\{\mathbf{s}^j:j\leq B\}}F(\mathbf{s})$ if $f$ is non-monotone.

Proposition 4

If $\mathbf{s}$ is an output of Alg. 4 under monotone case, then it satisfies \[ f(\mathbf{o})\leq\frac{2+2\epsilon B}{1-\epsilon}f(\mathbf{s}) \]

Proof of Proposition 4: 设 $e^j,i^j$ 是算法第 $j$ 轮选中的元素和方向, 按如下方式构造 $\{\mathbf{o}^j\}$ 序列:

$\mathbf{o}^0=\mathbf{o}$
当 $j>0$ 时, 记 $S^j=\text{supp}(\mathbf{o}^{j-1})\backslash\text{supp}(\mathbf{s}^{j-1})$. 并令 \[ o^j=\begin{cases} e^j,&\text{if}\ e^j\in S^j\\ \text{an arbitrary element in }S^j,&\text{otherwise} \end{cases} \] 再定义 $\mathbf{o}^{j-1/2},\mathbf{o}^{j},\mathbf{s}^{j-1/2}\in(k+1)^V$ 使得
\[\begin{aligned} &\mathbf{o}^{j-1/2}(e)=\begin{cases} 0,& e=o^j\\ \mathbf{o}^{j-1}(e),& e\in V\backslash\{o^j\} \end{cases},\ \ \mathbf{o}^{j}(e)=\begin{cases} i^j,& e=e^j\\ \mathbf{o}^{j-1/2}(e),& e\in V\backslash\{e^j\} \end{cases},\\ &\mathbf{s}^{j-1/2}(e)=\begin{cases} i^j,& e=o^j\\ \mathbf{s}^{j-1}(e),& e\in V\backslash\{o^j\} \end{cases} \end{aligned}\]
(简单解释就是, 对第 $j$ 轮选出的 $i,e$, 若 $e\in\text{supp}(\mathbf{o}^{j-1})\backslash\text{supp}(\mathbf{s}^{j-1})$, 则构造 $\mathbf{o}^j$ 为从 $\mathbf{o}^{j-1}$ 里删掉元素 $e$ 后再重新把 $e$ 加到 $i$ 位置上; 若 $e\notin\text{supp}(\mathbf{o}^{j-1})\backslash\text{supp}(\mathbf{s}^{j-1})$, 则构造 $\mathbf{o}^j$ 为从 $\text{supp}(\mathbf{o}^{j-1})\backslash\text{supp}(\mathbf{s}^{j-1})$ 任意选一个元素在 $\mathbf{o}^{j-1}$ 中删去后, 再将 $e$ 加到第 $i$ 个位置的集合中去. 而 $\mathbf{o}^{j-1/2}$ 就表示删掉元素后而 $e$ 尚未加入前时的中间量, $\mathbf{s}^{j-1/2}$ 是将被从 $\mathbf{o}^{j-1}$ 删去的元素加到 $\mathbf{s}^{j-1}$ 的第 $i$ 位置上去的辅助量.)

显然, $\mathbf{s}^j\sqsubseteq\mathbf{o}^j,\mathbf{s}^B=\mathbf{o}^B$ (W.L.O.G. 设 $|\mathbf{o}|=|\mathbf{s}|=B$). 结合单调性, greedy, 次模性, 我们有 \[ \begin{aligned} f(\mathbf{o}^{j-1})-f(\mathbf{o}^{j})\leq&f(\mathbf{o}^{j-1})-f(\mathbf{o}^{j-1/2})\leq f(\mathbf{s}^{j-1/2})-f(\mathbf{s}^{j-1})\\ \leq&\frac{1}{1-\epsilon}F(\mathbf{s}^{j-1/2})-f(\mathbf{s}^{j-1})\leq\frac{1}{1-\epsilon}F(\mathbf{s}^{j})-f(\mathbf{s}^{j-1})\\ \leq&\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s}^{j})-f(\mathbf{s}^{j-1}) \end{aligned} \] 因此 \[ \begin{aligned} f(\mathbf{o})-f(\mathbf{s})=&\sum_{j=1}^B\Big(f(\mathbf{o}^{j-1})-f(\mathbf{o}^j)\Big)\leq\sum_{j=1}^B\Big(\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s}^{j})-f(\mathbf{s}^{j-1})\Big)\\ \leq&\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s})+\sum_{j=1}^B\frac{2\epsilon}{1-\epsilon}f(\mathbf{s}^{j})\leq\frac{1+\epsilon+2\epsilon B}{1-\epsilon}f(\mathbf{s}) \end{aligned} \] 得证.

RMK 1

从这个证明我们可以看出单调 $k$-submodular 函数在 cardinality 约束下的近似比只能做到 $1/2$. 回想 $k=1$ 时最佳近似比 $1-1/e$ 的证明过程中用到的关键不等式 \[ f(O)-f(S^{j-1})\leq\sum_{e\in O\backslash S^{j-1}}\Delta_ef(S^{j-1})\leq B(f(S^j)-f(S^{j-1})) \] 在高维情况下是不起作用的, 因为元素的加入在纵向上按时间排列的同时, 在横向上对集合也有区别, 这就造成了 $f(\mathbf{o})-f(\mathbf{s}^{j-1})$ 无法简单展开, 即类似 $f(\mathbf{o}|\mathbf{s})$ 的表达在高维时会出现问题. 当然, 在固定其他 $k-1$ 个集合的情形下, $f$ 对单个位置上还是有次可加性的, 但总体上来看, 我们也许只能得到 \[ f(S_1,\dots,S_k)\leq\bigg|\bigcup_{j\in[k]}S_j\bigg|\sum_{i\in[k]}\Big(\frac{1}{|S_i|}\sum_{e\in S_i}f(\langle e,i\rangle)\Big) \]

Proposition 5

If $\mathbf{s}$ is an output of Alg. 4 under non-monotone case, then it satisfies \[ f(\mathbf{o})\leq\frac{3+\epsilon+4\epsilon B}{1-\epsilon}f(\mathbf{s}) \]

Proof of Proposition 5: 仍然像上面构造 $\mathbf{o}^j,\mathbf{o}^{j-1/2}$. 由 pairwise-monotonicity, 必存在 $i'\in[k]$ 使得 $f(\mathbf{s}^{j-1}\sqcup\langle e^j,i'\rangle)\geq f(\mathbf{s}^{j-1})$. 另外由 greedy 选择: \[ f(\mathbf{s}^{j-1}\sqcup\langle e^j,i'\rangle)\leq\frac{1}{1-\epsilon}F(\mathbf{s}^{j-1}\sqcup\langle e^j,i'\rangle)\leq\frac{1}{1-\epsilon}F(\mathbf{s}^j)\leq\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s}^j) \] 考虑如下三种情况:

$\mathbf{o}^{j-1}(e^j)=i^j$. 此时 $e^j$ 不动, $\mathbf{o}^{j}=\mathbf{o}^{j-1}$, 故 $f(\mathbf{o}^{j-1})-f(\mathbf{o}^j)=0\leq\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s}^j)-f(\mathbf{s}^{j-1})$.
$\mathbf{o}^{j-1}(e^j)=0$. 此时 $e^j$ 与 $\text{supp}(\mathbf{o}^{j-1})\backslash\text{supp}(\mathbf{s}^{j-1})$ 中的某个元素进行交换. 令任一 $i'\in[k]\backslash\{i^j\}$, 有 \[ \begin{aligned} f(\mathbf{o}^{j-1})-f(\mathbf{o}^{j})=&f(\mathbf{o}^{j-1})+f(\mathbf{o}^{j-1/2}\sqcup\langle e^j,i'\rangle)-2f(\mathbf{o}^{j-1/2})-\Big(f(\mathbf{o}^{j-1/2}\sqcup\langle e^j,i'\rangle)+f(\mathbf{o}^{j})-2f(\mathbf{o}^{j-1/2})\Big)\\ \leq&f(\mathbf{o}^{j-1})+f(\mathbf{o}^{j-1/2}\sqcup\langle e^j,i'\rangle)-2f(\mathbf{o}^{j-1/2})\\ \leq &f(\mathbf{s}^{j-1/2})+f(\mathbf{s}^{j-1}\sqcup\langle e^j,i'\rangle)-2f(\mathbf{s}^{j-1})\\ \leq&\frac{1}{1-\epsilon}F(\mathbf{s}^{j-1/2})+\frac{1}{1-\epsilon}F(\mathbf{s}^{j-1}\sqcup\langle e^j,i'\rangle)-2f(\mathbf{s}^{j-1})\\ \leq&\frac{2}{1-\epsilon}F(\mathbf{s}^j)-2f(\mathbf{s}^{j-1})\leq \frac{2(1+\epsilon)}{1-\epsilon}f(\mathbf{s}^j)-2f(\mathbf{s}^{j-1}) \end{aligned} \]
$\mathbf{o}^{j-1}(e^j)\in[k]\backslash\{i^j\}$. 这种情况表明 $e^j$ 从第 $\mathbf{o}^{j-1}(e^j)$ 个位置移动到了第 $i^j$ 位置上去. \[ \begin{aligned} f(\mathbf{o}^{j-1})-f(\mathbf{o}^{j})=&2f(\mathbf{o}^{j-1})-2f(\mathbf{o}^{j-1/2})-\Big(f(\mathbf{o}^{j-1})+f(\mathbf{o}^j)-2f(\mathbf{o}^{j-1/2})\Big)\\ \leq&2f(\mathbf{o}^{j-1})-2f(\mathbf{o}^{j-1/2})\\ \leq &2f(\mathbf{s}^{j-1/2})-2f(\mathbf{s}^{j-1})\\ \leq&\frac{2}{1-\epsilon}F(\mathbf{s}^{j-1/2})-2f(\mathbf{s}^{j-1})\\ \leq&\frac{2}{1-\epsilon}F(\mathbf{s}^j)-2f(\mathbf{s}^{j-1})\leq \frac{2(1+\epsilon)}{1-\epsilon}f(\mathbf{s}^j)-2f(\mathbf{s}^{j-1}) \end{aligned} \]

综上我们有 \[ \begin{aligned} f(\mathbf{o})-f(\mathbf{s})=&\sum_{j=1}^B\Big(f(\mathbf{o}^{j-1})-f(\mathbf{o}^j)\Big)\leq2\sum_{j=1}^B\Big(\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s}^{j})-f(\mathbf{s}^{j-1})\Big)\\ \leq&2\Big(\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s})+\sum_{j=1}^B\frac{2\epsilon}{1-\epsilon}f(\mathbf{s}^{j})\Big)\leq\frac{2+2\epsilon+4\epsilon B}{1-\epsilon}f(\mathbf{s}) \end{aligned} \] 得证.

RMK 2

从这个证明可以看出非单调 $k$-submodular 函数在 cardinality 约束下的近似比可达到 $3$. 另外, 在 $k=1$ 时至少能做到 $e$ 的结果了 (见 SODA2014 的一篇文章).

Omitted Proofs

Proof of Proposition 1

首先, 对 $V$ 做完一趟 pass 之后, $|\mathbf{s}|$ 可能达到也可能没达到满的 budget. 若 $t=B$, 则 \[ f(\mathbf{s})\geq\frac{F(\mathbf{s}^B)}{1+\epsilon}\geq\frac{1-\epsilon}{1+\epsilon}B\frac{o}{M}\geq\frac{1-\epsilon}{1+\epsilon}\frac{f(\mathbf{o})}{(1+\gamma)M} \] 得到近似比之一 $(1+\epsilon)(1+\gamma)\frac{M}{1-\epsilon}$.

下面我们考虑 $t<B$ 时的情况. 定义 $\mathbf{o}^{j}=(\mathbf{o}\sqcup\mathbf{s}^j)\sqcup\mathbf{s}^{j}$.

Claim 1

\[ f(\mathbf{o})-f(\mathbf{o}^t)\leq\frac{1+\epsilon+2B\epsilon}{1-\epsilon}f(\mathbf{s}) \]

Proof of Claim 1: 类似地, 我们记 $\langle e^j,i^j\rangle$ 是 Alg. 1 中第 $j$ 个加入的元素. 定义 $\mathbf{o}^{j-1/2}=(\mathbf{o}\sqcup\mathbf{s}^j)\sqcup\mathbf{s}^{j-1}$. 进一步, 我们定义 \[ \mathbf{s}^{j-1/2}=\begin{cases} \mathbf{s}^{j-1}\sqcup\langle e^j,\mathbf{o}(e^j)\rangle,&\text{if}\ e^j\in\text{supp}(\mathbf{o})\\ \mathbf{s}^{j-1},&\text{otherwise} \end{cases} \] 此时就有 \[ \begin{aligned} f(\mathbf{o}^{j-1})-f(\mathbf{o}^j)\leq& f(\mathbf{o}^{j-1})-f(\mathbf{o}^{j-1/2})\\ \leq&f(\mathbf{s}^{j-1/2})-f(\mathbf{s}^{j-1})\\ \leq&\frac{1}{1-\epsilon}F(\mathbf{s}^{j-1/2})-f(\mathbf{s}^{j-1})\\ \leq&\frac{1}{1-\epsilon}F(\mathbf{s}^j)-f(\mathbf{s}^{j-1})\\ \leq&\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s}^j)-f(\mathbf{s}^{j-1}) \end{aligned} \] 因此 \[ \begin{aligned} f(\mathbf{o})-f(\mathbf{o}^t)=&\sum_{j=1}^t\Big(f(\mathbf{o}^{j-1})-f(\mathbf{o}^j)\Big)\leq\sum_{j=1}^t\Big(\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s}^j)-f(\mathbf{s}^{j-1})\Big)\\ =&\frac{1+\epsilon}{1-\epsilon}f(\mathbf{s})+\sum_{j=1}^{t-1}\frac{2\epsilon}{1-\epsilon}f(\mathbf{s}^j)\leq\frac{1+\epsilon+2B\epsilon}{1-\epsilon}f(\mathbf{s}) \end{aligned} \] Claim 1 得证.

Claim 2

\[ f(\mathbf{o}^t)-f(\mathbf{s})\leq\frac{1}{M}f(\mathbf{o})+\frac{2\epsilon B}{1-\epsilon}f(\mathbf{s}) \]

Proof of Claim 2: 由于 $\mathbf{s}\sqsubseteq\mathbf{o}^t$, 用 $\{\langle u_i,j_i\rangle\}_{j=1}^r$ 表示 $\text{supp}(\mathbf{o}^t)\backslash\text{supp}(\mathbf{s})$ 中的元素及其位置, 然后我们用 $\mathbf{s}_i$ 表示 $\mathbf{s}$ 遇到 $u_i$ 时的值. 我们有 \[ \frac{F(\mathbf{s}_i\sqcup\langle u_i,j_i\rangle)}{1-\epsilon}-\frac{F(\mathbf{s}_i)}{1+\epsilon}\leq\frac{o}{M}+\frac{2\epsilon F(\mathbf{s}_i)}{1-\epsilon^2} \] 令 $\mathbf{u}_i=\mathbf{s}\sqcup\{\langle u_1,j_i\rangle,\dots,\langle u_i,j_i\rangle\}$, 有 \[ \begin{aligned} f(\mathbf{o}^t)-f(\mathbf{s})=&\sum_{i=1}^{B-t}\Big(f(\mathbf{u}_i)-f(\mathbf{u}_{i-1})\Big)\leq\sum_{i=1}^{B-t}\Big(f(\mathbf{s}_i\sqcup\langle u_i,j_i\rangle)-f(\mathbf{s}_{i})\Big)\\ \leq&\sum_{i=1}^{B-t}\Big(\frac{1}{1-\epsilon}F(\mathbf{s}_i\sqcup\langle u_i,j_i\rangle)-\frac{1}{1+\epsilon}F(\mathbf{s}^i)\Big)\leq\sum_{i=1}^{B-t}\Big(\frac{o}{M}+\frac{2\epsilon}{1-\epsilon^2}F(\mathbf{s}_i)\Big)\leq\frac{1}{M}f(\mathbf{o})+\frac{2\epsilon B}{1-\epsilon}f(\mathbf{s}) \end{aligned} \] Claim 2 得证.

结合 Claim 1, Claim 2 就可完成 Proposition 1 的证明.

Proof of Proposition 2

TBC.

Proof of Proposition 3