Krause 2008 - Greedy Algorithm and the 1-1 over e Guarantee

Summary

The greedy rule adds the location maximising ${\delta }_y={\sigma }_{y\mid A}^2/{\sigma }_{y\mid \bar{A}}^2$ (Eq. 6, Algorithm 1). Mutual information is submodular (Lemma 3) and, once the grid is fine enough and sensor noise is positive, approximately monotone for sets up to size $2k$ (Lemma 5, Corollary 6). Nemhauser et al.’s argument then gives $MI(A_{\text{greedy}})\ge (1-1/e)(\text{OPT}-k\epsilon )$ (Theorem 7).

Overview

Plain greedy adds the single best next sensor. For a monotone submodular $F$ with $F(\varnothing )=0$ this is within $1-1/e\approx 63\%$ of optimal. MI is not monotone globally ($MI(V)=0$, Fig. 6), so the paper proves approximate monotonicity for $|A|\le 2k$, which is all the proof needs.

Main Content

Greedy marginal gain (Eq. 6)

With $\bar{A}=V\setminus (A\cup \{y\})$,

$$MI(A\cup y)-MI(A)=H(y\mid A)-H(y\mid \bar{A}).$$

By Eq. (5) maximising this is maximising the ratio ${\delta }_y=\frac{{\sigma }_y^2-{\Sigma }_{yA}{\Sigma }_{AA}^{-1}{\Sigma }_{Ay}}{{\sigma }_y^2-{\Sigma }_{y\bar{A}}{\Sigma }_{\bar{A}\bar{A}}^{-1}{\Sigma }_{\bar{A}y}}$. Entropy keeps only the numerator; the denominator forces a “central” $y$ whose variance is small given everything not selected.

Algorithm 1. $A\leftarrow \varnothing$; for $j=\mathrm{1..}k$: for each $y\in S\setminus A$ compute ${\delta }_y$; $y^{\ast }\leftarrow \arg \max {\delta }_y$; $A\leftarrow A\cup y^{\ast }$. Complexity $O(k{n}^4)$ for $n=|V|$ ($O(n^3)$ per conditional-variance computation, recomputed for all $y$, $k$ times).

Submodular set function

$F$ is submodular if $F(A\cup B)+F(A\cap B)\le F(A)+F(B)$; equivalently for $A\subseteq A^{\prime }$ and $y\notin A^{\prime }$, $F(A\cup y)-F(A)\ge F(A^{\prime }\cup y)-F(A^{\prime })$ (diminishing returns).

Lemma 3

$A\mapsto MI(A)$ is submodular.

Proof. “Information never hurts”: $H(y\mid A)\ge H(y\mid A\cup B)$, and similarly the term $H(y\mid \bar{A})$ increases with the conditioning set shrinking, so $MI(A^{\prime }\cup y)-MI(A^{\prime })\le MI(A\cup y)-MI(A)$ whenever $A\subseteq A^{\prime }$, for arbitrary sets (not only those the greedy algorithm visits).

Theorem 4 (Nemhauser, Wolsey, Fisher, 1978)

For monotone submodular $F$ over a finite $V$ with $F(\varnothing )=0$, greedy picks $A_G$ with $|A_G|=k$ and

$$F(A_G)\ge (1-(\frac{k-1}{k}{)}^k)\text{OPT}\ge (1-1/e)\text{OPT}.$$

Lemma 5 (approximate monotonicity)

Let $X$ be a GP on a compact $C\subset {\mathbb{R}}^m$ with positive-definite continuous kernel $K:C\times C\to {\mathbb{R}}_0^{+}$ and sensor noise variance at least ${\sigma }^2$. For any $\epsilon >0$ and any maximum number $k$ of sensors there is a discretisation $V=S\cup U$ of mesh width $\delta$ such that for all $A\subseteq S$, $|A|\le 2k$, and all $y\in V\setminus A$: $MI(A\cup y)\ge MI(A)-\epsilon$.

Proof sketch (App. A). Fix ${\epsilon }_1$ and use uniform continuity of $K$ to choose a mesh with $|K(x,y)-K(x^{\prime },y^{\prime })|\le {\epsilon }_1$ whenever points move by at most ${\delta }_1$. Compare the grid $C_1$ with its translate $C_2$. Because sensor noise gives smallest eigenvalue at least ${\sigma }^2$, $\Vert {\Sigma }_{AA}^{-1}{\Vert }_2\le {\sigma }^{-2}$; bounding $\Vert {\Sigma }_{AA}^{-1}-{\Sigma }_{\tilde{A}\tilde{A}}^{-1}\Vert \le {\sigma }^{-4}{k}^2{\epsilon }_1$ and $\Vert {\Sigma }_{XA}-{\Sigma }_{X\tilde{A}}\Vert \le {\epsilon }_1\sqrt{k}$ yields $|{\sigma }_{X\mid A}^2-{\sigma }_{X\mid \tilde{A}}^2|\le {\epsilon }_1(k{\sigma }^{-2}{M}^2+{\sigma }^{-2}{k}^{2}M)+O({\epsilon }_1^2)$ with $M={\max }_{x}K(x,x)$. Picking $\delta$ so this is at most ${\sigma }^2\epsilon$ bounds the entropy difference $H(X\mid A)-H(X\mid \tilde{A})=\frac{1}{2}\log ({\sigma }_{X\mid A}^2/{\sigma }_{X\mid \tilde{A}}^2)$ by at most $\epsilon$, which is what approximate monotonicity needs.

Corollary 6 (Lipschitz kernels)

If $K$ is Lipschitz with constant $L$, the required mesh width is

$$\delta \le \frac{\epsilon {\sigma }^6}{4kLM({\sigma }^2+2k^{2}M+6k^2{\sigma }^2)},M=\underset{x}{\max }K(x,x),\epsilon <\min (M,1).$$

A polynomial discretisation suffices; the bound is worst-case (sensors arbitrarily close) and loose for spread-out placements.

Theorem 7 (main guarantee)

Under the assumptions of Lemma 5, Algorithm 1 selects $A$ with $|A|=k$ and

$$MI(A)\ge (1-1/e)(\text{OPT}-k\epsilon ).$$

It also gives an upper bound on OPT usable to judge other heuristics.

Proof sketch. Nemhauser’s proof, simplified by Jon Kleinberg: with $A_i$ the first $i$ greedy picks, ${\delta }_i=MI(A_i)-MI(A_{i-1})$ and $A^{\ast }$ optimal, Lemma 5 gives $MI(A_i\cup A^{\ast })\ge MI(A^{\ast })-k\epsilon$, and submodularity gives $MI(A_i\cup A^{\ast })\le MI(A_i)+k{\delta }_{i+1}$; the resulting recursion gives the bound.

Examples

Verified 1-D comparison (60 points, SE kernel length 0.1, noise 0.1, $k=5$):

import numpy as np
n = 60; x = np.linspace(0, 1, n); S = np.arange(n)
K = np.exp(-0.5*((x[:, None] - x[None, :])/0.1)**2); s2 = 0.1
Sig = K + s2*np.eye(n)                      # covariance of noisy observations
def cv(y, A):
    A = list(A)
    return Sig[y, y] if not A else Sig[y, y] - Sig[y, A] @ np.linalg.solve(Sig[np.ix_(A, A)], Sig[A, y])
def greedy(k, mi=True):
    A = []
    for _ in range(k):
        best = max(((cv(y, A)/cv(y, [j for j in S if j not in A and j != y]) if mi else cv(y, A)), y)
                   for y in S if y not in A)
        A.append(best[1])
    return sorted(int(a) for a in A)
print(greedy(5, True), greedy(5, False))

Output: MI [2, 13, 29, 46, 57], entropy [0, 11, 23, 41, 59] (the latter includes both borders, 0 and 59). This illustrates Figure 4. (This implementation treats every grid point as both a candidate and a target, so $S=U=V$; the paper allows distinct $S$ and $U$.)

Connections

• The same diminishing-returns structure is why lazy greedy is exact: Krause 2008 - Lazy Evaluation and Local Kernels.
• A knowledge-gradient or entropy-search acquisition (Acquisition Functions, Bayesian Optimisation) is a one-step cousin; MI placement is non-adaptive because variance does not depend on data.

See Also

• Krause 2008 - Near-Optimal Sensor Placements in Gaussian Processes - Overview