Provable Submodular Minimization using Wolfe's Algorithm

Introduction

However, from a practical stand point, none of the provably polynomial time algorithms exhibit good performance on instances of SFM encountered in practice (see §4). This, along with the widespread applicability of SFM in machine learning, has inspired a large body of work on practically fast procedures (see for a survey). But most of these procedures focus either on special submodular functions such as decomposable functions or on constrained SFM problems .

Fujishige-Wolfe’s Algorithm for SFM: For any submodular function $f$, the base polytope ${\mathcal{B}}_{f}$ of $f$ is defined as follows:

This approach towards SFM was revitalized in 2006 when Fujishige and Isotani announced encouraging computational results regarding the minimum norm point algorithm. In particular, this algorithm significantly out-performed all known provably polynomial time algorithms. Theoretically, however, little is known regarding the convergence of Wolfe’s procedure except for the finite, but exponential, running time Wolfe himself proved. Nor is the situation any better for its application on the base polytope. Given the practical success, we believe this is an important, and intriguing, theoretical challenge.

In this work, we make some progress towards analyzing the Fujishige-Wolfe method for SFM and, in fact, Wolfe’s algorithm in general. In particular, we prove the following two results:

We prove (in Theorem 4) that for any polytope ${\mathcal{B}}$, Wolfe’s algorithm converges to an $\varepsilon$-approximate solution, in $O(1/\varepsilon)$ steps. More precisely, in $O(nQ^{2}/\varepsilon)$ iterations, Wolfe’s algorithm returns a point $\|x\|_{2}^{2}\leq\|x_{*}\|_{2}^{2}+\varepsilon$, where $Q=\max_{p\in{\mathcal{B}}}\|p\|_{2}$.

We prove (in Theorem 5) a robust version of a theorem by Fujishige relating min-norm points on the base polytope to SFM. In particular, we prove that an approximate min-norm point solution provides an approximate solution to SFM as well. More precisely, if $x$ satisfies $\|x\|_{2}^{2}\leq z^{T}x+\varepsilon^{2}$ for all $z\in{\mathcal{B}}_{f}$, then, $f(S_{x})\leq\min_{S}f(S)+2n\varepsilon$, where $S_{x}$ can be constructed efficiently using $x$.

Together, these two results gives us our main result which is a pseudopolynomial bound on the running time of the Fujishige-Wolfe algorithm for submodular function minimization.

Our analysis suggests that the Fujishige-Wolfe’s algorithm is dependent on $F$ and has worse dependence on $n$ than the Iwata-Orlin algorithm. To verify this, we conducted empirical study on several standard SFM problems. However, for the considered benchmark functions, running time of Fujishige-Wolfe’s algorithm seemed to be independent of $F$ and exhibited better dependence on $n$ than the Iwata-Orlin algorithm. This is described in §4.

Preliminaries: Submodular Functions and Wolfe’s Algorithm

The connection between the SFM problem and the base polytope was first established in the following minimax theorem of Edmonds .

Given any submodular function $f$ with $f(\emptyset)=0$, we have

The following theorem of Fujishige shows the connection between finding the minimum norm point in the base polytope $\mathcal{B}_{f}$ of a submodular function $f$ and the problem of SFM on input $f$. This forms the basis of the Fujishige-Wolfe algorithm. In §3.2, we prove a robust version of this theorem.

2 Wolfe’s Algorithm for Minimum Norm Point of a polytope.

When $\varepsilon=0$, the algorithm on termination (if it terminates) returns the minimum norm point in ${\mathcal{B}}$ since $||x||^{2}\leq x^{\top}x_{*}\leq||x||\cdot||x_{*}||$. For completeness, we sketch Wolfe’s argument in of finite termination. Note that $|S|\leq n$ always; otherwise the affine minimizer is which either terminates the program or starts a minor cycle which decrements $|S|$. Thus, the number of minor cycles in a major cycle $\leq n$, and it suffices to bound the number of major cycles. Each major cycle is associated with a set $S$ whose affine minimizer, which is the current $x$, lies in the convex hull of $S$. Wolfe calls such sets corrals. Next, we show that $||x||$ strictly decreases across iterations (major or minor cycle) of the algorithm, which proves that no corral repeats, thus bounding the number of major cycles by the number of corrals. The latter is at most $N\choose n$, where $N$ is the number of vertices of ${\mathcal{B}}$.

Consider iteration $j$ which starts with $x_{j}$ and ends with $x_{j+1}$. Let $S_{j}$ be the set $S$ at the beginning of iteration $j$. If the iteration is a major cycle, then $x_{j+1}$ is the affine minimizer of $S_{j}\cup\{q_{j}\}$ where $q_{j}=\text{LO}(x_{j})$. Since $x_{j}^{\top}q_{j}<||x_{j}||^{2}$ (the algorithm doesn’t terminate in iteration $j$) and $x_{j+1}^{\top}q_{j}=||x_{j+1}||^{2}$ (affine minimizer property), we get $x_{j}\neq x_{j+1}$, and so $||x_{j+1}||<||x_{j}||$ (since the affine minimizer is unique). If the iteration is a minor cycle, then $x_{j+1}=\theta x_{j}+(1-\theta)y_{j}$, where $y_{j}$ is the affine minimizer of $S_{j}$ and $\theta<1$. Since $||y_{j}||<||x_{j}||$ ($y_{j}\neq x_{j}$ since $y_{j}\notin{\tt conv}(S_{j})$), we get $||x_{j+1}||<||x_{j}||$.

Analysis

Our refined analysis of Wolfe’s algorithm is encapsulated in the following theorem.

Let ${\mathcal{B}}$ be an arbitrary polytope such that the maximum Euclidean norm of any vertex of ${\mathcal{B}}$ is at most $Q$. After $O(nQ^{2}/\varepsilon^{2})$ iterations, Wolfe’s algorithm returns a point $x\in{\mathcal{B}}$ which satisfies $||x||^{2}\leq x^{\top}q+\varepsilon^{2}$, for all points $q\in{\mathcal{B}}$. In particular, this implies $||x||^{2}\leq||x_{*}||^{2}+2\varepsilon^{2}$.

The above theorem shows that Wolfe’s algorithm converges to the minimum norm point at an $1/t$-rate. We stress that the above is for any polytope. To apply this to SFM, we prove the following robust version of Fujishige’s theorem connecting the minimum norm point in the base polytope and the set minimizing the submodular function value.

Fix a submodular function $f$ with base polytope $\mathcal{B}_{f}$. Let $x\in{\mathcal{B}}_{f}$ be such that $||x||^{2}\leq x^{\top}q+\varepsilon^{2}$ for all $q\in{\mathcal{B}}_{f}$. Renumber indices such that $x_{1}\leq\cdots\leq x_{n}$. Let $S=\{1,2,\dots,k\},$where $k$ is smallest index satisfying (C1) $x_{k+1}\geq 0$ and (C2) $x_{k+1}-x_{k}\geq\varepsilon/n$. Then, $f(S)\leq f(T)+2n\varepsilon$ for any subset $T\subseteq S$. In particular, if $\varepsilon=\frac{1}{4n}$ and $f$ is integer-valued, then $S$ is a minimizer.

Theorem 4 and Theorem 5 implies our main theorem. See 1

We prove Theorem 4 and Theorem 5 in §3.1 and §3.2, respectively.

The stumbling block in the analysis of Wolfe’s algorithm is the interspersing of major and minor cycles which oscillates the size of $S$ preventing it from being a good measure of progress. Instead, in our analysis, we use the norm of $x$ as the measure of progress. Already we have seen that $||x||$ strictly decreases. It would be nice to quantify how much the decrease is, say, across one major cycle. This, at present, is out of our reach even for major cycles which contain two or more minor cycles in them. However, we can prove significant drop in norm in major cycles which have at most one minor cycle in them. We call such major cycles good. The next easy, but very useful, observation is the following: one cannot have too many bad major cycles without having too many good major cycles.

In any consecutive $3n+1$ iterations, there exists at least one good major cycle.

Consider a run of $r$ iterations where all major cycles are bad, and therefore contain $\geq 2$ minor cycles. Say there are $k$ major cycles and $r-k$ minor cycles, and so $r-k\geq 2k$ implying $r\geq 3k$. Let $S_{I}$ be the set $S$ at the start of these iterations and $S_{F}$ be the set at the end. We have $|S_{F}|\leq|S_{I}|+k-(r-k)\leq|S_{I}|+2k-r\leq n-\frac{r}{3}$. Therefore, $r\leq 3n$, since $|S_{F}|\geq 0$.∎

Before proceeding, we introduce some notation.

Given a point $x\in{\mathcal{B}}$, let us denote ${\tt err}(x):=||x||^{2}-||x_{*}||^{2}$. Given a point $x$ and $q$, let $\Delta(x,q):=||x||^{2}-x^{\top}q$ and let $\Delta(x):=\max_{q\in{\mathcal{B}}}\Delta(x,q)=||x||^{2}-\min_{q\in{\mathcal{B}}}x^{\top}q$. Observe that $\Delta(x)\geq{\tt err}(x)/2$ since $\Delta(x)\geq||x||^{2}-x^{\top}x_{*}\geq(||x||^{2}-||x_{*}||^{2})/2$.

We now use $t$ to index all good major cycles. Let $x_{t}$ be the point $x$ at the beginning of the $t$-th good major cycle. The next theorem shows that the norm significantly drops across good major cycles.

For $t$ iterating over good major cycles, ${\tt err}(x_{t})-{\tt err}(x_{t+1})\geq\Delta^{2}(x_{t})/8Q^{2}$.

We now complete the proof of Theorem 4 using Theorem 6.

Using Theorem 6, we get that ${\tt err}(x_{t})-{\tt err}(x_{t+1})\geq{\tt err}(x_{t})^{2}/32Q^{2}$ since $\Delta(x)\geq{\tt err}(x)/2$ for all $x$. We claim that in $t^{*}\leq 64Q^{2}/\varepsilon^{2}$ good major cycles, we reach $x_{t}$ with ${\tt err}(x_{t^{*}})\leq\varepsilon^{2}$. To see this rewrite as follows:

Now let $e_{0}:={\tt err}(x_{0})$. Define $t_{0},t_{1},\ldots$ such that for all $k\geq 1$ we have ${\tt err}(x_{t})>e_{0}/2^{k}$ for $t\in[t_{k-1},t_{k})$. That is, $t_{k}$ is the first time $t$ at which ${\tt err}(x_{t})\leq e_{0}/2^{k}$. Note that for $t\in[t_{k-1},t_{k})$, we have ${\tt err}(x_{t+1})\leq{\tt err}(x_{t})\left(1-\frac{e_{0}}{32Q^{2}2^{k}}\right)$. This implies in $32Q^{2}2^{k}/e_{0}$ time units after $t_{k-1}$, we will have ${\tt err}(x_{t})\leq{\tt err}(x_{t_{k-1}})/2$; we have used the fact that $(1-\delta)^{1/\delta}<1/2$ when $\delta<1/32$. That is, $t_{k}\leq t_{k-1}+32Q^{2}2^{k}/e_{0}$. We are interested in $t^{*}=t_{K}$ where $2^{K}=e_{0}/\varepsilon^{2}$. We get $t^{*}\leq\frac{32Q^{2}}{e_{0}}\left(1+2+\cdots+2^{K}\right)\leq 64Q^{2}2^{K}/e_{0}=64Q^{2}/\varepsilon^{2}$.

Next, we claim that in $t^{**}<t^{*}+t^{\prime}$ good major cycles, where $t^{\prime}=8Q^{2}/\varepsilon^{2}$, we obtain an $x_{t^{**}}$ with $\Delta(x_{t^{**}})\leq\varepsilon^{2}$. This is because, if not, then, using Theorem 6, in each of the good major cycles $t^{*}+1,t^{*}+2,\ldots t^{*}+t^{\prime}$, ${\tt err}(x)$ falls additively by $>\varepsilon^{4}/8Q^{2}$ and thus ${\tt err}(x_{t^{*}+t^{\prime}})<{\tt err}(x_{t^{*}})-\varepsilon^{2}\leq 0$, which is a contradiction. Therefore, in $O(Q^{2}/\varepsilon^{2})$ good major cycles, the algorithm obtains an $x=x_{t^{**}}$ with $\Delta(x)\leq\varepsilon^{2}$, proving Theorem 4. ∎

The rest of this subsection is dedicated to proving Theorem 6.

We start off with a simple geometric lemma.

where $Q$ is an upper bound on $||x||,||q||$.

Since $y$ is the minimum norm point in ${\tt aff}(S)$, we have $x^{\top}y=q^{\top}y=||y||^{2}$. In particular, $||x-y||^{2}=||x||^{2}-||y||^{2}$. Therefore,

where the first inequality is Cauchy-Schwartz and the second is triangle inequality. Lemma now follows by taking square of the above expression and by observing that $\|y-x\|^{2}=\|x\|^{2}-\|y\|^{2}$. ∎

The above lemma takes case of major cycles with no minor cycles in them.

Let $t$ be the index of a good major cycle with no minor cycles. Then ${\tt err}(x_{t})-{\tt err}(x_{t+1})\geq\Delta^{2}(x_{t})/4Q^{2}$.

Let $S_{t}$ be the set $S$ at start of the $t$th good major cycle, and let $q_{t}$ be the point minimizing $x_{t}^{\top}q$. Let $S=S_{t}\cup q_{t}$ and let $y$ be the minimum norm point in ${\tt aff}(S)$. Since there are no minor cycles, $y\in{\tt conv}(S)$. Abuse notation and let $x_{t+1}=y$ be the iterate at the call of the next major cycle (and not the next good major cycle). Since the norm monotonically decreases, it suffices to prove the lemma statement for this $x_{t+1}$. Now apply Lemma 2 with $x=x_{t}$ and $q=q_{t}$ and $S=S_{t}\cup q_{t}$. We have that ${\tt err}(x_{t})-{\tt err}(x_{t+1})=||x_{t}||^{2}-||y||^{2}\geq\Delta(x_{t},q_{t})^{2}/4Q^{2}=\Delta(x_{t})^{2}/4Q^{2}$. ∎

Now we have to argue about major cycles with exactly one minor cycle. The next observation is a useful structural result.

Consider any (not necessarily good) major cycle. Let $x_{t},S_{t},q_{t}$ be the parameters at the beginning of this cycle, and let $x_{t+1},S_{t+1},q_{t+1}$ be the parameters at the beginning of the next major cycle. Then, $q_{t}\in S_{t+1}$.

Clearly $S_{t+1}\subseteq S_{t}\cup q_{t}$ since $q_{t}$ is added and then maybe minor cycles remove some points from $S$. Suppose $q_{t}\notin S_{t+1}$. Well, then $S_{t+1}\subseteq S_{t}$. But $x_{t+1}$ is the affine minimizer of $S_{t+1}$ and $x_{t}$ is the affine minimizer of $S_{t}$. Since $S_{t}$ is the larger set, we get $||x_{t}||\leq||x_{t+1}||$. This contradicts the strict decrease in the norm. ∎

Suppose the $t$th good major cycle has exactly one minor cycle. Then, ${\tt err}(x_{t})-{\tt err}(x_{t+1})\geq\Delta(x_{t})^{2}/8Q^{2}$.

Let $x_{t},S_{t},q_{t}$ be the parameters at the beginning of the $t$th good major cycle. Let $y$ be the affine minimizer of $S_{t}\cup q_{t}$. Since there is one minor cycle, $y\notin{\tt conv}(S_{t}\cup q_{t})$. Let $z=\theta x_{t}+(1-\theta)y$ be the intermediate $x$, that is, point in the line segment $[x_{t},y]$ which lies in ${\tt conv}(S_{t}\cup q_{t})$. Let $S^{\prime}$ be the set after the single minor cycle is run. Since there is just one minor cycle, we get $x_{t+1}$ (abusing notation once again since the next major cycle maynot be good) is the affine minimizer of $S^{\prime}$.

Let $A\triangleq||x_{t}||^{2}-||y||^{2}$. From Lemma 2, and using $q_{t}$ is the minimizer of $x_{t}^{\top}q$ over all $q$, we have:

Recall, $z=\theta x_{t}+(1-\theta)y$ for some $\theta\in$. Since $y$ is the min-norm point of ${\tt aff}(S_{t}\cup q_{t})$, and $x_{t}\in S_{t}$, we get $||z||^{2}=\theta^{2}||x_{t}||^{2}+(1-\theta^{2})||y||^{2}$. this yields:

Further, recall that $S^{\prime}$ is the set after the only minor cycle in the $t^{th}$ iteration is run and thus, from Lemma 4, $q_{t}\in S^{\prime}$. $z\in{\tt conv}(S^{\prime})$ by definition. And since there is only one minor cycle, $x_{t+1}$ is the affine minimizer of $S^{\prime}$. We can apply Lemma 2 with $z,q_{t}$ and $x_{t+1}$, to get

Now we lower bound $\Delta^{2}(z,q_{t})$. By definition of $z$, we have:

where the last equality follows since $y^{\top}q_{t}=||y||^{2}$ (since $q_{t}\in S_{t}\cup q_{t}$ and $y$ is affine minimizer of $S_{t}\cup q_{t}$). This gives

We need to show that the RHS is at least $\Delta(x_{t})^{2}/8Q^{2}$. Intuitively, if $\theta$ is small (close to ), the first term implies this using (3), and if $\theta$ is large (close to $1$), then the second term implies this. The following paragraph formalizes this intuition for any $\theta$.

Now, if $(1-\theta^{2})A>\Delta(x_{t})^{2}/8Q^{2}$, we are done. Therefore, we assume $(1-\theta^{2})A\leq\Delta(x_{t})^{2}/8Q^{2}$. In this case, using the fact that $\Delta(x_{t})\leq||x_{t}||^{2}+||x_{t}||||q_{t}||\leq 2Q^{2}$, we get that

Substituting in (7), and using (3), we get

Lemma 3 and Lemma 5 complete the proof of Theorem 6.

2 A Robust version of Fujishige’s Theorem

In this section we prove Theorem 5 which we restate below. See 5

Before proving the theorem, note that setting $\varepsilon=0$ gives Fujishige’s theorem Theorem 3.

We claim that the following inequality holds. Below, $[i]:=\{1,\ldots,i\}$.

We prove this shortly. Let $S$ and $k$ be as defined in the theorem statement. Note that $\sum_{i\in S:x_{i}\geq 0}x_{i}\leq n\varepsilon$, since (C2) doesn’t hold for any index $i<k$ with $x_{i}\geq 0$. Furthermore, since $x_{k+1}-x_{k}\geq\varepsilon/n$, we get using (9), $f(S)-x(S)\leq n\varepsilon$. Therefore, $f(S)\leq\sum_{i\in S:x_{i}<0}x_{i}+2n\varepsilon$ which implies the theorem due to Theorem 2.

Now we prove (9). Let $z\in{\mathcal{B}}_{f}$ be the point which minimizes $z^{\top}x$. By the Greedy algorithm described in Section 2.1, we know that $z_{i}=f([i])-f([i-1])$. Next, we write $x$ in a different basis as follows: $x=\sum_{i=1}^{n-1}(x_{i}-x_{i+1}){\mathbf{1}}_{[i]}+x_{n}{\mathbf{1}}_{[n]}$. Here ${\mathbf{1}}_{[i]}$ is used as the shorthand for the vector which has $1$’s in the first $i$ coordinates and s everywhere else. Taking dot product with $(x-z)$, we get

Since $z_{i}=f([i])-f([i-1])$, we get $x^{\top}{\mathbf{1}}_{[i]}-z^{\top}{\mathbf{1}}_{[i]}$ is $x([i])-f([i])$. Therefore the RHS of (10) is the LHS of (9). The LHS of (10), by the assumption of the theorem, is at most $\varepsilon^{2}$ implying (9). ∎

Discussion and Conclusions

Note that our anlaysis of the Fujishige-Wolfe algorithm is weaker than the best known method in terms of time complexity (IO method by ) on two counts: a) dependence on $n$, b) dependence on $F$. In contrast, we found this algorithm significantly outperforming the IO algorithm empirically – we show two plots here. In Figure 1 (a), we run both on Erdos-Renyi graphs with $p=0.8$ and randomly chosen $s,t$ nodes. In Figure 1 (b), we run both on the Iwata group functions with $3$ groups. Perhaps more interestingly, in Figure 1 (c), we ran the Fujishige-Wolfe algorithm on the simple path graph where $s,t$ were the end points, and changed the capacities on the edges of the graph which changed the parameter $F$. As can be seen, the number of iterations of the algorithm remains constant even for exponentially increasing $F$.

References