Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions

Introduction

The search for optimal algorithms for submodular optimization has seen substantial progress in recent years, but is still an ongoing endeavor. The first polynomial-time algorithm used the ellipsoid method , and several combinatorial algorithms followed . For a detailed summary, see . Unlike submodular minimization, submodular maximization is NP hard. However, maximization problems admit constant-factor approximations , often even in the constrained case .

While submodularity, like convexity, occurs naturally in a wide variety of problems, recent studies have shown that in the general case, many submodular problems of interest are very hard: the problems of learning a submodular function or of submodular minimization under constraints do not even admit constant or logarithmic approximation factors in polynomial time . These rather pessimistic results however stand in sharp contrast to empirical observations, which suggest that these lower bounds are specific to rather contrived classes of functions, whereas much better results can be achieved in many practically relevant cases. Given the increasing importance of submodular functions in machine learning, these observations beg the question of qualifying and quantifying properties that make sub-classes of submodular functions more amenable to learning and optimization. Indeed, limited prior work has shown improved results for constrained minimization and learning of sub-classes of submodular functions, including symmetric functions , concave functions , label cost or covering functions .

In this paper, we take additional steps towards addressing the above problems and show how the generic notion of the curvature – the deviation from modularity– of a submodular function determines both upper and lower bounds on approximation factors for many learning and constrained optimization problems. In particular, our quantification tightens the generic, function-independent bounds in for many practically relevant functions. Previously, the concept of curvature has been used to tighten bounds for submodular maximization problems . Hence, our results complete a unifying picture of the effect of curvature on submodular problems. By quantifying the influence of curvature on other problems, we improve previous bounds in for many functions used in applications. Curvature, moreover, does not rely on a specific functional form but generically only on the marginal gains. It allows a smooth transition between the ‘easy’ functions and the ‘really hard’ subclasses of submodular functions.

Problem statements, definitions and background

(Approximation ) Given a submodular function $f$ in form of a value oracle, find an approximation $\hat{f}$ (within polynomial time and representable within polynomial space), such that for all $X\subseteq V$, it holds that $\hat{f}(X)\leq f(X)\leq\alpha_{1}(n)\hat{f}(X)$ for a polynomial $\alpha_{1}(n)$.

(PMAC-Learning ) Given i.i.d training samples $\{(X_{i},f(X_{i})\}_{i=1}^{m}$ from a distribution $\mathcal{D}$, learn an approximation $\hat{f}(X)$ that is, with probability $1-\delta$, within a multiplicative factor of $\alpha_{2}(n)$ from $f$. PMAC learning is defined like PAC learning with the added relaxation that the function is, with high probability, approximated within a factor of $\alpha_{2}(n)$.

(Constrained optimization ) Minimize a submodular function $f$ over a family $\mathcal{C}$ of feasible sets, i.e., $\min_{X\in\mathcal{C}}f(X)$.

In its general form, the approximation problem was first studied by Goemans et al. , who approximate any monotone submodular function to within a factor of $O(\sqrt{n}\log n)$, with a lower bound of $\alpha_{1}(n)=\Omega(\sqrt{n}/\log n)$. Building on this result, Balcan and Harvey show how to PMAC-learn a monotone submodular function within a factor of $\alpha_{2}(n)=O(\sqrt{n})$, and prove a lower bound of $\Omega(n^{1/3})$ for the learning problem. Subsequent work extends these results to sub-additive and fractionally sub-additive functions . Better learning results are possible for the subclass of submodular shells and Fourier sparse set functions . Very recently Devanur et al investigated a related problem of approximating one class of submodular functions with another and they show how many non-monotone submodular functions can be approximated with simple directed graph cuts within a factor of $n^{2}/4$ which is tight. They also consider problems of approximating symmetric submodular functions and other subclasses of submodular functions.

Both Problems 1 and 2 have numerous applications in algorithmic game theory and economics as well as machine learning . For example, applications like bundle pricing, predicting prices of objects or growth rates etc. often have diminishing returns and a natural problem is to estimate these functions . Similarly in machine learning, a number of problems involving sensor placement, summarization and others can be modeled through submodular functions. Often in these scenarios we would want to explicitly approximate or learn the true objective. For example in the case of document summarization, we are given the ROUGE scores. Since this function is submodular , a natural application is to learn these functions for summarization tasks.

Constrained submodular minimization arises in applications such as power assignment or transportation problems . In machine learning, it occurs, for instance, in the form of MAP inference in high-order graphical models or in size-constrained corpus extraction . Recent results show that almost all constraints make it hard to solve the minimization even within a constant factor . Here, we will focus on the constraint of imposing a lower bound on the cardinality, and on combinatorial constraints where $\mathcal{C}$ is the set of all $s$-$t$ paths, $s$-$t$ cuts, spanning trees, or perfect matchings in a graph.

A central concept in this work is the total curvature $\kappa_{f}$ of a submodular function $f$ and the curvature $\kappa_{f}(S)$ with respect to a set $S\subseteq V$, defined as

Without loss of generality, assume that $f(j)>0$ for all $j\in V$. This follows since, if there exists an element $j\in V$ such that $f(j)=0$, we can safely remove element $j$ from the ground set, since for every set $X$, $f(j|X)$ = 0 (from submodularity), and including or excluding $j$ does not make any difference to the cost function.

These different forms of curvature are closely related.

For any monotone submodular function and set $S\subseteq V$,

We finally prove that $\hat{\kappa_{f}}(S)\leq\kappa_{f}(S)$. Note that,

Hence, $\hat{\kappa_{f}}(S)\leq\kappa_{f}(S)$. ∎

For submodular minimization, learning, and approximation, however, the role of curvature has not yet been addressed (an exception are the upper bounds in for minimization). In the following sections, we complete the picture of how curvature affects the complexity of submodular maximization and minimization, approximation, and learning.

The above-cited lower bounds for Problems 1–3 were established with functions of maximal curvature ($\kappa_{f}=1$) which, as we will see, is the worst case. By contrast, many practically interesting functions have smaller curvature, and our analysis will provide an explanation for the good empirical results observed with such functions . An example for functions with $\kappa_{f}<1$ is the class of concave over modular functions that have been used in speech processing and computer vision . This class comprises, for instance, functions of the form $f(X)=\sum_{i=1}^{k}(w_{i}(X))^{a}$, for some $a\in$ and a nonnegative weight vectors $w_{i}$. Such functions may be defined over clusters $C_{i}\subseteq V$, in which case the weights $w_{i}(j)$ are nonzero only if $j\in C_{i}$ .

A related quantity distinct from curvature that has been introduced in the machine learning community is the submodularity ratio :

This parameter shows the decay of approximation bounds when an algorithm for submodular maximization is applied to non-submodular functions. The submodularity ratio measures how “close” $f$ is to submodularity, and helps characterize theoretical bounds for functions which are approximately submodular. Curvature, by contrast, measures how close a submodular function to being modular.

2 The Curve-normalized Polymatroid function

To analyze Problems 1 – 3, we introduce the concept of a curve-normalized polymatroidA polymatroid function is a monotone increasing, nonnegative, submodular function satisfying $f(\emptyset)=0$.. Specifically, we define the $\kappa_{f}$-curve-normalized version of $f$ as

If $\kappa_{f}=0$, then we set $f^{\kappa}\equiv 0$. We call $f^{\kappa}$ the curve-normalized version of $f$ because its curvature is $\kappa_{f^{\kappa}}=1$. The function $f^{\kappa}$ allows us to decompose a submodular function $f$ into a “difficult” polymatroid function and an “easy” modular part as $f(X)=f_{\text{difficult}}(X)+m_{\text{easy}}(X)$ where $f_{\text{difficult}}(X)=\kappa_{f}f^{\kappa}(X)$ and $m_{\text{easy}}(X)=(1-\kappa_{f})\sum_{j\in X}f(j)$. Moreover, we may modulate the curvature of given any function $g$ with $\kappa_{g}=1$, by constructing a function $f(X)\triangleq cg(X)+(1-c)|X|$ with curvature $\kappa_{f}=c$ but otherwise the same polymatroidal structure as $g$.

Our curvature-based decomposition is different from decompositions such as that into a totally normalized function and a modular function . Indeed, the curve-normalized function has some specific properties that will be useful later on :

If $f$ is monotone submodular with $\kappa_{f}>0$, then

The inequalities follow from submodularity and monotonicity of $f$. The first part follows from the subadditivity of $f$. The second inequality follows since $f(X)\geq\sum_{j\in X}f(j|V\backslash j)\geq(1-\kappa_{f})\sum_{j\in X}f(j)$, since $\forall j\in X,f(j|V\backslash j)\geq(1-\kappa_{f})f(j)$ by definition of $\kappa_{f}$. ∎

If $f$ is monotone submodular, then $f^{\kappa}(X)$ in Eqn. (6) is a monotone non-negative submodular function. Furthermore, $f^{\kappa}(X)\leq\sum_{j\in X}f(j)$.

Submodularity of $f^{\kappa}$ is evident from the definition. To show the monotonicity, it suffices to show that $f(X)-{(1-\kappa_{f})}\sum_{j\in X}f(j)$ is monotone non-decreasing and non-negative submodular. To show it is non-decreasing, notice that $\forall j\notin X,f(j|V\backslash j)-(1-\kappa_{f})f(j)\geq 0$, since $(1-\kappa_{f})f(j)\leq f(j|V\backslash j)$ by the definition of $\kappa_{f}$. Non-negativity follows from monotonicity and the fact that $f^{\kappa}(\emptyset)=0$. To show the second part, notice that $\frac{f(X)-(1-\kappa_{f})\sum_{j\in X}f(j)}{\kappa_{f}}\leq\frac{\sum_{j\in X}f(j)-(1-\kappa_{f})\sum_{j\in X}f(j)}{\kappa_{f}}=\sum_{j\in X}f(j)$. ∎

3 A framework for curvature-dependent lower bounds.

The function $f^{\kappa}$ will be our tool for analyzing the hardness of submodular problems. Previous information-theoretic lower bounds for Problems 1–3 are independent of curvature and use functions with $\kappa_{f}=1$. These curvature-independent bounds are proven by constructing two essentially indistinguishable matroid rank functions $h$ and $f^{R}$, one of which depends on a random set $R\subseteq V$. One then argues that any algorithm would need to make a super-polynomial number of queries to the functions for being able to distinguish $h$ and $f^{R}$ with high enough probability. The lower bound will be the ratio $\max_{X\in\mathcal{C}}h(X)/f^{R}(X)$. We extend this proof technique to functions with a fixed given curvature. To this end, we define the functions

Both of these functions have curvature $\kappa_{f}$. This construction enables us to explicitly introduce the effect of curvature into information-theoretic bounds for all monotone submodular functions.

Approximating submodular functions everywhere

We first address improved bounds for the problem of approximating a monotone submodular function everywhere. Previous work established $\alpha$-approximations $g$ to a submodular function $f$ satisfying $g(S)\leq f(S)\leq\alpha g(S)$ for all $S\subseteq V$ . We begin with a theorem showing how any algorithm computing such an approximation may be used to obtain a curvature-specific, improved approximation. Note that the curvature of a monotone submodular function can be obtained within $2n+1$ queries to $f$. The key idea of Theorem 3.1 is to only approximate the curved part of $f$, and to retain the modular part exactly.

Given a polymatroid function $f$ with $\kappa_{f}<1$, let $f^{\kappa}$ be its curve-normalized version defined in Equation (6), and let $\hat{f}^{\kappa}$ be a submodular function satisfying $\hat{f}^{\kappa}(X)\leq f^{\kappa}(X)\leq\alpha(n)\hat{f}^{\kappa}(X)$, for some $X\subseteq V$. Then the function $\hat{f}(X)\triangleq\kappa_{f}\hat{f^{\kappa}}(X)+(1-\kappa_{f})\sum_{j\in X}f(j)$ satisfies

The above inequalities hold, even if we use an upper bound $\bar{\kappa_{f}}$ instead of the actual curvature $\kappa_{f}$.

The first inequality follows directly from definitions. To show the second inequality, note that $\hat{f^{\kappa}}(X)\geq\frac{f^{\kappa}(X)}{\alpha(n)}$, and therefore

The last inequality follows since $\kappa_{f}f^{\kappa}(X)+(1-\kappa_{f})\sum_{j\in X}f(j)\leq\sum_{j\in X}f(j)$. The other inequalities in Eqn. (9) follow directly from the definitions.

It is also easy to see that all the above inequalities will hold using an upper bound $\bar{\kappa_{f}}>\kappa_{f}$ instead of $\kappa_{f}$ in the definition of the curve-normalized function. The bound in that case would be,

where, $\hat{f}(X)=\bar{\kappa_{f}}\hat{f^{\bar{\kappa}}}(X)+(1-\bar{\kappa_{f}})\sum_{j\in X}f(j)$, $\hat{f^{\bar{\kappa}}}$ is an approximation of $f^{\bar{\kappa}}$ satisfying $\hat{f^{\bar{\kappa}}}(X)\leq f^{\kappa}(X)\leq\alpha(n)\hat{f^{\kappa}}(X)$ and,

Theorem 3.1 may be directly applied to tighten recent results on approximating submodular functions everywhere. An algorithm by Goemans et al. computes an approximation to a polymatroid function $f$ in polynomial time by approximating the submodular polyhedron via an ellipsoid. This approximation (which we call the ellipsoidal approximation) satisfies $\alpha(n)=O(\sqrt{n}\log{n})$, and has the form $\sqrt{w^{f}(X)}$ for a certain weight vector $w^{f}$.

For any polymatroid rank function $f$, one can compute a weight vector $w^{f}$ and correspondingly an approximation $\sqrt{w^{f}(X)}$ via a polynomial number of oracle queries such that $\sqrt{w^{f}(X)}\leq f(X)\leq O(\sqrt{n}\log{n})\sqrt{w^{f}(X)}$.

The weights $w^{f}$ are computed via an ellipsoidal approximation of the submodular polyhedron . Corollary 3.3 states that a tighter approximation is possible for functions with $\kappa_{f}<1$.

Let $f$ be a polymatroid function with $\kappa_{f}<1$, and let $\sqrt{w^{f^{\kappa}}(X)}$ be the ellipsoidal approximation to the $\kappa$-curve-normalized version $f^{\kappa}(X)$ of $f$. Then the function $f^{ea}(X)=\kappa_{f}\sqrt{w^{f^{\kappa}}(X)}+(1-\kappa_{f})\sum_{j\in X}f(j)$ satisfies

If $\kappa_{f}=0$, then the approximation is exact. This is not surprising since a modular function can be inferred exactly within $O(n)$ oracle calls.

To compute $f^{ea}$, construct the function $f^{\kappa}$ as in Equation (6), and apply the algorithm in to construct the approximation $\sqrt{w^{f^{\kappa}}(X)}$ such that $\sqrt{w^{f^{\kappa}}(X)}\leq f^{\kappa}(X)\leq O(\sqrt{n}\log n)\sqrt{w^{f^{\kappa}}(X)}$. Note that $\sqrt{w^{f^{\kappa}}(X)}$ is an approximation of $f^{\kappa}$ and not $f$. Then define $f^{ea}(X)\triangleq\kappa_{f}(X)f^{ea}(X)+(1-\kappa_{f})\sum_{j\in X}f(j)$ ∎

The following lower bound shows that Corollary 3.3 is tight up to logarithmic factors. It refines the lower bound in to include $\kappa_{f}$.

Given a submodular function $f$ with curvature $\kappa_{f}$, there does not exist a (possibly randomized) polynomial-time algorithm that computes an approximation to $f$ within a factor of $\frac{n^{1/2-\epsilon}}{1+(n^{1/2-\epsilon}-1)(1-\kappa_{f})}$, for any $\epsilon>0$.

The information-theoretic proof uses a construction and argumentation similar to that in , but perturbs the functions to have the desired curvature.

In the following let $\kappa_{f}=\kappa$. Define two monotone submodular functions $h^{\kappa}(X)=\kappa\min\{|X|,\alpha\}+(1-\kappa)|X|$ and $f_{\kappa}^{R}(X)=\kappa\min\{\beta+|X\cap\bar{R}|,|X\cap R|,\alpha\}+(1-\kappa)|X|$, where $R\subseteq V$ is a random set of cardinality $\alpha$. Let $\alpha$ and $\beta$ be an integer such that $\alpha=x\sqrt{n}/5$ and $\beta=x^{2}/5$ for an $x^{2}=\omega(\log n)$. Both $h^{\kappa}$ and $f_{\kappa}^{R}$ have curvature equal to $\kappa_{f}=\kappa$.

Using a Chernoff bound, one can then show that any algorithm that uses a polynomial number of queries can distinguish $h^{\kappa}$ and $f_{\kappa}^{R}$ with probability only $n^{-\omega(1)}$, and therefore cannot reliably distinguish the functions with a polynomial number of queries .

Therefore, any such algorithm will, with high probability, approximate $h^{\kappa}$ and $f_{\kappa}^{R}$ by the same function $\hat{f}$. Since the approximation must hold for both functions, the approximation factor must satisfy $h^{\kappa}(R)\leq\gamma\hat{f}(R)\leq\gamma f_{\kappa}^{R}(R)$, and is therefore lower bounded by $h^{\kappa}(R)/f_{\kappa}^{R}(R)$. Given an arbitrary $\epsilon>0$, set $x^{2}=n^{2\epsilon}=\omega(\log n)$. Then

Assume there was an algorithm that generates an approximation $\hat{f}^{\prime}$ with approximation factor $\gamma^{\prime}<\gamma$. This would imply that $h^{\kappa}(R)/f_{\kappa}^{R}(R)<\gamma^{\prime}$, but this contradicts the above derivation. ∎

The simplest alternative approximation to $f$ one might conceive is the modular function $\hat{f}^{m}(X)\triangleq\sum_{j\in X}f(j)$ which can easily be computed by querying the $n$ values $f(j)$.

Given a monotone submodular function $f$, it holds that

We first show the result for $\hat{\kappa_{f}}(X)$, and since it is a stronger notion of curvature, the bound will hold for $\kappa_{f}(X)$ as well.

We shall use the following facts, which follow from the definitions of submodularity and curvature.

Sum the expressions from Fact 2, $\forall k\in X$, use Fact 1, and we obtain the following series of inequalities,

From the fact that $1-\hat{\kappa_{f}}(X)\geq 1-\kappa_{f}(X)$, it immediately follows that,

The form of Lemma 3.1 is slightly different from Corollary 3.3. However, there is a straightforward correspondence: given $\hat{f}$ such that $\hat{f}(X)\leq f(X)\leq\alpha^{\prime}(n)\hat{f}(X)$, by defining $\hat{f^{\prime}}(X)=\alpha^{\prime}(n)\hat{f}(X)$, we get that $f(X)\leq\hat{f^{\prime}}(X)\leq\alpha^{\prime}(n)f(X)$. Lemma 3.1 for the modular approximation is complementary to Corollary 3.3: First, the modular approximation is better whenever $|X|\leq\sqrt{n}$. Second, the bound in Lemma 3.1 depends on the curvature $\kappa_{f}(X)$ with respect to the set $X$, which is stronger than $\kappa_{f}$. Third, $\hat{f}^{m}$ is extremely simple to compute. For sets of larger cardinality, however, the ellipsoidal approximation of Corollary 3.3 provides a better approximation, in fact, the best possible one (Theorem 3.4). In a similar manner, Lemma 3.1 is tight for any modular approximation to a submodular function:

For any $\kappa>0$, there exists a monotone submodular function $f$ with curvature $\kappa$ such that no modular upper bound on $f$,$\hat{f}(X)=\sum_{j\in X}w(j)\geq f(X),\forall X\subseteq V$, can approximate $f(X)$ to a factor better than $\frac{|X|}{1+(|X|-1)(1-\kappa_{f})}$.

Let $f^{\kappa}(X)=\kappa\min\{|X|,1\}+(1-\kappa)|X|$. Then $f^{\kappa}(X)=\kappa+(1-\kappa)|X|=1+(1-\kappa)(|X|-1)$ for all $\emptyset\subset X\subseteq V$. Since $\hat{f}^{m}$ is an upper bound, it must satisfy $\hat{f}(j)=w(j)\geq 1$ for all $j\in V$. Therefore, $\hat{f}^{m}(X)=|X|,X\neq\emptyset$. ∎

The improved curvature dependent bounds immediately imply better bounds for the class of concave over modular functions used in .

Given weight vectors $w_{1},\cdots,w_{k}\geq 0$, and a submodular function $f(X)=\sum_{i=1}^{k}\lambda_{i}[w_{i}(X)]^{a},\lambda_{i}\geq 0$, for $a\in(0,1)$, it holds that $f(X)\leq\sum_{j\in X}f(j)\leq|X|^{1-a}f(X)$

We first show this result independent of curvature, and then show how the curvature dependent bound also implies this improved bound. First define $f(X)=[w(X)]^{a}$, for $a\in(0,1]$ and $w\geq 0$. since $x^{a}$ is a concave function for $a\in(0,1]$, we have from Jensen’s inequality that, given $x_{1},x_{2},\cdots,x_{n}\geq 0$,

Notice that, when $f(X)=[w(X)]^{a}$, we have that $f(i)=w(i)^{a}$. Hence $\sum_{j\in X}f(i)=\sum_{i\in X}w(i)^{a}$. Hence from the inequality above, it directly holds that,

and hence, $\sum_{j\in X}f(j)\leq|X|^{1-a}f(X)$. This inequality also holds for a sum of concave over modular functions, since for each $w_{i}\geq 0$, we have

Moreover, when $f(X)=\sum_{i=1}^{k}\lambda_{i}[w_{i}(X)]^{a}$, the modular upper bound $\sum_{j\in X}f(j)=\sum_{j\in X}\sum_{i=1}^{k}\lambda_{i}[w_{i}(j)]^{a}$. Summing up eqn. (26) for all $i$, we have that,

We next show that this result can also be seen from the curvature of the function.

Given weight vectors $w_{1},\cdots,w_{k}\geq 0$, and a submodular function $f(X)=\sum_{i=1}^{k}\lambda_{i}[w_{i}(X)]^{a},\lambda_{i}\geq 0$, for $a\in(0,1]$, it holds that,

Again, let $f(X)=[w(X)]^{a}$, for $w\geq 0$ and $a\in(0,1]$. Then,

The last inequality again holds due to concavity of $g(x)=x^{a}$. In particular, for a concave function, $g(y)-g(x)\leq g^{\prime}(x)(y-x)$, where $g^{\prime}$ is the derivative of $g$. Hence $g(x)\geq g(y)+g^{\prime}(x)(x-y)$. Substitute $y=w(X)-w(j),x=w(X)$ and $g(x)=x^{a}$, and we get the above expression.

The last inequality follows from the previous Lemma. ∎

Hence from the curvature dependent bound, we obtain a slightly weaker bound, which still gives a $O(|X|^{1-a})$ bound for the modular upper bound.

In particular, when $a=1/2$, the modular upper bound approximates the sum of square-root over modular functions by a factor of $\sqrt{|X|}$.

Learning Submodular functions

We next address the problem of learning submodular functions in a PMAC setting . The PMAC (Probably Mostly Approximately Correct) framework is an extension of the PAC framework to allow multiplicative errors in the function values from a fixed but unknown distribution $\mathcal{D}$ over $2^{V}$. We are given training samples $\{(X_{i},f(X_{i})\}_{i=1}^{m}$ drawn i.i.d. from $\mathcal{D}$. The algorithm may take time polynomial in $n$, $1/\epsilon$, $1/\delta$ to compute a (polynomially-representable) function $\hat{f}$ that is a good approximation to $f$ with respect to $\mathcal{D}$. Formally, $\hat{f}$ must satisfy that

for some approximation factor $\alpha(n)$. Balcan and Harvey propose an algorithm that PMAC-learns any monotone, nonnegative submodular function within a factor $\alpha(n)=\sqrt{n+1}$ by reducing the problem to that of learning a binary classifier. If we assume that we have an upper bound on the curvature $\kappa_{f}$, or that we can estimate it note that $\kappa_{f}$ can be estimated from a set of $2n+1$ samples $\{(j,f(j))\}_{j\in V}$, $\{(V,f(V))\}$, and $\{(V\backslash j,f(V\backslash j)\}_{j\in V}$ included in the training samples, and have access to the value of the singletons $f(j),j\in V$, then we can obtain better learning results with non-maximal curvature:

Let $f$ be a monotone submodular function for which we know an upper bound on its curvature and the singleton weights $f(j)$ for all $j\in V$. For every $\epsilon,\delta>0$ there is an algorithm that uses a polynomial number of training examples, runs in time polynomial in $(n,1/\epsilon,1/\delta)$ and PMAC-learns $f$ within a factor of $\frac{\sqrt{n+1}}{1+(\sqrt{n+1}-1)(1-\kappa_{f})}$. If $\mathcal{D}$ is a product distribution, then there exists an algorithm that PMAC-learns $f$ within a factor of $O(\frac{\log\frac{1}{\epsilon}}{1+(\log\frac{1}{\epsilon}-1)(1-\kappa_{f})})$.

The algorithm of Lemma 4.1 uses the reduction of Balcan and Harvey to learn the $\kappa_{f}$-curve-normalized version $f^{\kappa}$ of $f$. From the learned function $\hat{f^{\kappa}}(X)$, we construct the final estimate $\hat{f}(X)\triangleq\kappa_{f}\hat{f^{\kappa}}(X)+(1-\kappa_{f})\sum_{j\in X}f(j)$. Theorem 3.1 implies Lemma 4.1 for this $\hat{f}(X)$.

The proof of this theorem directly follows from the results in and those from section 3. The idea is that, we use the PMAC setting and algorithm from . We use the same construction as section 3, and construct the function $f^{\kappa}(X)$ which is the curve-normalized version of $f$. Let $\hat{f^{\kappa}}(X)$ be the function learn from $f^{\kappa}$ using the algorithm from . Then define $\hat{f}(X)=(1-\kappa_{f})\hat{f^{\kappa}}(X)+\kappa_{f}\sum_{j\in X}f(j)$ and an analysis similar to that in section 3 conveys that the function $\hat{f}$ is within a factor of $\frac{\sqrt{n+1}}{1+(\sqrt{n+1}-1)(1-\kappa_{f})}$. Note that moreover, whenever the bound $\hat{f^{\kappa}}(X)\leq f^{\kappa}(X)\leq\sqrt{n+1}\hat{f^{\kappa}}(X)$, the above curvature dependent bound will also hold. Hence the curvature dependent bound holds with high probability on a large measure of sets. The case for product distributions also follows from very similar lines and the results from . ∎

Given a class of submodular functions with curvature $\kappa_{f}$, there does not exist a polynomial-time algorithm (which possibly even has information about $\kappa_{f}$) that is guaranteed to PMAC-learn $f$ for every $\epsilon,\delta>0$ within a factor of $\frac{n^{1/3-\epsilon^{\prime}}}{1+(n^{1/3-\epsilon^{\prime}}-1)(1-\kappa_{f})}$, for any $\epsilon^{\prime}>0$.

We end this section by showing how we can learn with a construction analogous to that in Lemma 3.1.

If $f$ is a monotone submodular function with known curvature (or a known upper bound) $\hat{\kappa_{f}}(X),\forall X\subseteq V$, then for every $\epsilon,\delta>0$ there is an algorithm that uses a polynomial number of training examples, runs in time polynomial in $(n,1/\epsilon,1/\delta)$ and PMAC learns $f(X)$ within a factor of $1+\frac{|X|}{1+(|X|-1)(1-\hat{\kappa_{f}}(X))}$.

Before proving this result, we compare this result to Lemma 4.1. Lemma 4.3 leads to better bounds for small sets, whereas Lemma 4.1 provides a better general bound. Moreover, in contrast to Lemma 4.1, here we only need an upper bound on the curvature and do not need to know the singleton weights $\{f(j),j\in V\}$. Note also that, while $\kappa_{f}$ itself is an upper bound of $\hat{\kappa_{f}}(X)$, often one does have an upper bound on $\hat{\kappa_{f}}(X)$ if one knows the function class of $f$ (for example, say concave over modular). In particular, an immediate corollary is that the class of concave over modular functions $f(X)=\sum_{i=1}^{k}\lambda_{i}[w_{i}(X)]^{a},\lambda_{i}\geq 0$, for $a\in(0,1)$ can be learnt within a factor of $\min\{\sqrt{n+1},1+|X|^{1-a}\}$.

To prove this result, we adapt Algorithm 2 in to curvature and modular approximations. Following their arguments, we reduce the problem of learning a submodular function to that of learning a linear seperator, while separately handling the subset of instances where $f$ is zero. We detail the parts where our proof deviates from .

We divide $2^{V}$ into the support set $\mathcal{S}=\{X\subseteq V\mid f(X)>0\}$ of $f$ and its complement $\mathcal{Z}=\{X\subseteq V\mid f(X)=0\}$. Using samples from $\mathcal{D}^{\prime}$, we generate new, binary labeled samples from a distribution $\mathcal{D}^{\prime}$ on $\{0,1\}^{n}\times\mathcal{R}$ that will be used to learn the linear separator. These samples differ slightly from those in . Let

To sample from $\mathcal{D}^{\prime}$, we repeatedly sample from $\mathcal{D}$ until we obtain a set $X\in\mathcal{S}$. For each such $X$, we flip a fair coin and, with equal probability, generate a sample point from $\mathcal{D}^{\prime}$ as

We observe that the generated positive and negative sample are linearly separable with the separator $u=(w,-1)$, where $w(j)=0$ if $f(j)=0$, and $w(j)=f(j)+\delta$ if $f(j)>0$, with $\delta$ such that $0<\delta<\min_{j\in\mathcal{S}}f(X_{j})/n$:

for all $X\subseteq V$. The second inequality holds since $\sum_{j\in X}f(j)\leq\alpha(X)f(X)$ and $\delta|X|\leq\delta n<f(X)$. (For points in $\mathcal{Z}$, we have that $u^{\top}(1_{X},f(X))=0$.)

The final algorithm generates a sample from $\mathcal{D}^{\prime}$ for each sample $X\in\mathcal{S}$ from $\mathcal{D}$. For each $X\in\mathcal{Z}$, it adds the constraint that $w(j)=0$ for all $j\in X$. We then find a linear separator $u=(w,-z)$ and output the function $\hat{f}(X)\triangleq w(X)/z$. This is possible by the above arguments.

This function satisfies the approximation constraints for the set $\mathcal{Y}$ of all training points $X\in\mathcal{S}$ for which both generated samples are labeled correctly: the correct labelings $w(X)-zf(X)>0$ and $w(X)-z(\alpha(X)+1)f(X)<0$ imply that

Similarly, the constraints on $w$ imply that the same holds for any subset of the union of the training samples in $\mathcal{Z}$.

Constrained submodular minimization

Next, we apply our results to the minimization of submodular functions under constraints. Most algorithms for constrained minimization use one of two strategies: they apply a convex relaxation , or they optimize a surrogate function $\hat{f}$ that should approximate $f$ well . We follow the second strategy and propose a new, widely applicable curvature-dependent choice for surrogate functions. A suitable selection of $\hat{f}$ will ensure theoretically optimal results. Throughout this section, we refer to the optimal solution as $X^{*}\in\operatorname*{argmin}_{X\in\mathcal{C}}f(X)$.

We prove the first part and the second part similarly follows. Given that,

Then, if $\hat{X}$ is the optimal solution for minimizing $\hat{f}$ over $\mathcal{C}$. We then have that,

where $X^{*}$ is the optimal solution of $f$. ∎

For Lemma 5.1 to be practically useful, it is essential that $\hat{f}_{1}$ and $\hat{f}_{2}$ be efficiently optimizable over $\mathcal{C}$. We discuss two general curvature-dependent approximations that work for a large class of combinatorial constraints. In particular, we use Theorem 3.1: we decompose $f$ into $f^{\kappa}$ and a modular part $f^{m}$, and then approximate $f^{\kappa}$ while retaining $f^{m}$, i.e., $\hat{f}=\hat{f}^{\kappa}+f^{m}$. The first approach uses a simple modular upper bound (MUB) and the second relies on the Ellipsoidal approximation (EA) we used in Section 3.

MUB: The simplest approximation to a submodular function is the modular approximation $\hat{f}^{m}(X)\triangleq\sum_{j\in X}f(j)\geq f(X)$. Since here, $\hat{f}^{\kappa}$ happens to be equivalent to $f^{m}$, we obtain the overall approximation $\hat{f}=\hat{f}^{m}$. Lemmas 5.1 and 3.1 directly imply a set-dependent approximation factor for $\hat{f}^{m}$:

Let $\widehat{X}\in\mathcal{C}$ be a $\beta$-approximate solution for minimizing $\sum_{j\in X}f(j)$ over $\mathcal{C}$, i.e. $\sum_{j\in\widehat{X}}f(j)\leq\beta\min_{X\in\mathcal{C}}\sum_{j\in X}f(j)$. Then

Corollary 5.1 has also been shown in . Thanks to Lemma 3.1 and the second part of Lemma 5.1, however, we can provide a much simpler proof. Similar to the algorithms in , MUB can be extended to an iterative algorithm yielding performance gains in practice. In particular, Corollary 5.1 implies improved approximation bounds for practically relevant concave over modular functions, such as those used in . For instance, for $f(X)=\sum_{i=1}^{k}\sqrt{\sum_{j\in X}w_{i}(j)}$, we obtain a worst-case approximation bound of $\sqrt{|X^{*}|}\leq\sqrt{n}$. This is significantly better than the worst case factor of $|X^{*}|$ for general submodular functions.

EA: Instead of employing a modular upper bound, we can approximate $f^{\kappa}$ using the construction by Goemans et al. , as in Corollary 3.3. In that case, $\hat{f}(X)=\kappa_{f}\sqrt{w^{f^{\kappa}}(X)}+(1-\kappa_{f})f^{m}(X)$ has a special form: a weighted sum of a concave function and a modular function. Minimizing such a function over constraints $\mathcal{C}$ is harder than minimizing a merely modular function, but with the algorithm in we obtain an FPTASThe FPTAS will yield a $\beta=(1+\epsilon)$-approximation through an algorithm polynomial in $\frac{1}{\epsilon}$. for minimizing $\hat{f}$ over $\mathcal{C}$ whenever we can minimize a nonnegative linear function over $\mathcal{C}$.

For a submodular function with curvature $\kappa_{f}<1$, algorithm EA will return a solution $\widehat{X}$ that satisfies

We use the important result from where they show that any function of the form $\lambda_{1}\sqrt{m_{1}(X)}+\lambda_{2}m_{2}(X)$ where $\lambda_{1}\geq 0,\lambda_{2}\geq 0$ and $m_{1}$ and $m_{2}$ are positive modular functions, has a FPTAS, provided a modular function can easily be optimized over $\mathcal{C}$. Notice that our function is exactly of that form. Hence $\hat{f}(X)$ can be approximately optimized over $\mathcal{C}$. This bound then translates into the approximation guarantee using Corollary 3.3 and the first part of Lemma 5.1.

Next, we apply the results of this section to specific optimization problems, for which we show (mostly tight) curvature-dependent upper and lower bounds.

Cardinality lower bounds (SLB). A simple constraint is a lower bound on the cardinality of the solution, i.e., $\mathcal{C}=\{X\subseteq V:|X|\geq k\}$. Svitkina and Fleischer prove that for monotone submodular functions of arbitrary curvature, it is impossible to find a polynomial-time algorithm with an approximation factor better than $\sqrt{n/\log{n}}$. They show an algorithm which matches this approximation factor.

For the SLB problem, Algorithm EA and MUB are guaranteed to be no worse than factors of $O(\frac{\sqrt{n}\log n}{1+(\sqrt{n}\log n-1)(1-\kappa_{f})})$ and $\frac{k}{1+(k-1)(1-\kappa_{f})}$ respectively.

The guarantee for MUB follows directly from Corollary 5.1, by observing that $|X^{*}|=k$. We also show a similar asymptotic hardness result, which is quite close to the bounds in observation 5.1. These bounds are improvements over the results of whenever $\kappa_{f}<1$. Here, MUB is preferable to EA whenever $k$ is small. The following theorem shows that the bound for EA is tight up to poly-log factors.

For $\kappa_{f}<1$ and any $\epsilon>0$, there exists submodular functions with curvature $\kappa_{f}$ such that no poly-time algorithm achieves an approx. factor of $\frac{n^{1/2-\epsilon}}{1+(n^{1/2-\epsilon}-1)(1-\kappa_{f})}$ for the SLB problem.

The proof of this theorem is analogous to that of theorem 3.4. Define two monotone submodular functions $h_{\kappa}(X)=\kappa_{f}\min\{|X|,\alpha\}+(1-\kappa_{f})|X|$ and $f^{R}_{\kappa}(X)=\kappa_{f}\min\{\beta+|X|\cap\bar{R}|,|X|,\alpha\}+(1-\kappa_{f})|X|$, where $R\subseteq V$ is a random set of cardinality $\alpha$. Let $\alpha$ and $\beta$ be an integer such that $\alpha=x\sqrt{n}/5$ and $\beta=x^{2}/5$ for an $x^{2}=\omega(\log n)$. Also we assume that $k=\alpha$ in this case. Both $h_{\kappa}$ and $f^{R}_{\kappa}$ have curvature $\kappa_{f}$. Given an arbitrary $\epsilon>0$, set $x^{2}=n^{2\epsilon}=\omega(\log n)$. Then the ratio between $f^{R}_{\kappa}$ and $g^{\kappa_{f}}$ is $\frac{n^{1/2-\epsilon}}{1+(n^{1/2-\epsilon}-1)(1-\kappa_{f})}$. Clearly then if any algorithm can achieve better than this bound, it can distinguish between $f_{R}$ and $g$ which is a contradiction. ∎

Shortest submodular s-t path (SSP). Here, we aim to find an s-t path $X$ of minimum (submodular) length $f(X)$. Goel et al. show a $O(n^{2/3})$-approximation with matching curvature-independent lower bound $\Omega(n^{2/3})$. By Corollary 5.1, the curvature-dependent worst-case bound for MUB is $\frac{n}{1+(n-1)(1-\kappa_{f})}$ since any minimal s-t path has at most $n$ edges. Similarly, the factor for EA is $O(\frac{\sqrt{m}\log m}{1+(\sqrt{m}\log m-1)(1-\kappa_{f})})$. The bound of EA will be tighter for sparse graphs while MUB provides better results for dense ones. We can also show the following curvature-dependent lower bound:

Given a submodular function with a curvature $\kappa_{f}>0$ and any $\epsilon>0$, no polynomial-time algorithm achieves an approximation factor better than $\frac{n^{2/3-\epsilon}}{1+(n^{2/3-\epsilon}-1)(1-\kappa_{f})}$ for the SSP problem.

The proof of this follows in very similar lines to the earlier lower bounds using our construction and the matroid constructions in . The main idea is to use their multilevel graph, but define adjusted versions of their cost functions. In particular, define $h(X)=\kappa_{f}\min\{|X|,\alpha\}+(1-\kappa_{f})|X|$ and $f_{R}(X)=\kappa_{f}\min\{\beta+|X|\cap\bar{R}|,|X|,\alpha\}+(1-\kappa_{f})|X|$. In this context $R$ is a randomly chosen s-t path of length $n^{2/3}$ and $\alpha=n^{2/3}$. Similarly the value of $\beta=n^{\epsilon}$. The Chernoff bounds then show that the two functions above are indistinguishable (with high probability) and hence the ratio of the two functions $h$ and $f_{R}$ then provides the hardness result. ∎

Minimum submodular s-t cut (SSC): This problem, also known as the cooperative cut problem , asks to minimize a monotone submodular function $f$ such that the solution $X\subseteq\mathcal{E}$ is a set of edges whose removal disconnects $s$ from $t$ in $\mathcal{G}$. Using curvature refines the lower bound in :

No polynomial-time algorithm can achieve an approximation factor better than $\frac{n^{1/2-\epsilon}}{1+(n^{1/2-\epsilon}-1)(1-\kappa_{f})}$, for any $\epsilon>0$, for the SSC problem with a submodular function of curvature $\kappa_{f}$.

This proof follows along the lines of the results shown above. It uses the construction from . ∎

Corollary 5.1 implies an approximation factor of $O(\frac{\sqrt{m}\log m}{(\sqrt{m}\log m-1)(1-\kappa_{f})+1})$ for EA and a factor of $\frac{m}{1+(m-1)(1-\kappa_{f})}$ for MUB, where $m=|\mathcal{E}|$ is the number of edges in the graph. By Theorem 5.5, the factor for EA is tight for sparse graphs. Specifically for cut problems, there is yet another useful surrogate function that is exact on local neighborhoods. Jegelka and Bilmes demonstrate how this approximation may be optimized via a generalized maximum flow algorithm that maximizes a polymatroidal network flow . This algorithm still applies to the combination $\hat{f}=\kappa_{f}\hat{f}^{\kappa}+(1-\kappa_{f})f^{m}$, where we only approximate $f^{\kappa}$. We refer to this approximation as Polymatroidal Network Approximation (PNA).

Algorithm PNA achieves a worst-case approximation factor of $\frac{n}{2+(n-2)(1-\kappa_{f})}$ for the cooperative cut problem.

For dense graphs, this factor is theoretically tighter than that of the EA approximation.

We use the polymatroidal network flow construction from , where the approximation $\hat{f}$ is defined via a partition of the ground set, and is separable over groups of edges. This approximation can be solved efficiently via generalized flows in polynomial time . Moreover adding a modular term (for the modulation) does not increase the complexity of the problem.

This approximation satisfies $f^{\kappa}(X)\leq\hat{f^{\kappa}}(X)\leq\frac{n}{2}f^{\kappa}(X)$ for all cuts $X\in\mathcal{C}$.We then convert this expression in the form of Theorem 3.1 as $\frac{2\hat{f^{\kappa}}(X)}{n}\leq f^{\kappa}(X)\leq\hat{f^{\kappa}}(X)$. Then define $\hat{f}(X)\triangleq\kappa_{f}\frac{2\hat{f^{\kappa}(X)}}{n}+(1-\kappa_{f})\sum_{j\in X}f(j)$, and using theorem 3.1, it implies that:

Then let $\hat{X}$ be the minimizer of $\hat{f}(X)$ over $\mathcal{C}$ (using the generalized flows ). It then follows that (let $\alpha=\frac{n}{2+(n-2)(1-\kappa_{f})}$): $f(\hat{X})\leq\alpha\hat{f}(\hat{X})\leq\alpha\hat{f}(X^{*})\leq f(X^{*})$ where $X^{*}$ is the optimal solution of $f$ over $\mathcal{C}$. ∎

Minimum submodular spanning tree (SST). Here, $\mathcal{C}$ is the family of all spanning trees in a given graph $\mathcal{G}$. Such constraints occur for example in power assignment problems . Goel et al. show a curvature-independent optimal approximation factor of $O(n)$ for this problem.

For the minimum submodular spanning tree problem, algorithm MUB achieves an approximation guarantee, which is no worse than $\frac{n-r}{1+(n-r-1)(1-\kappa_{f})}$, where $r$ is the number of connected components of $\mathcal{G}$.

This result follows directly from Corollary 5.1 and the fact that $|X^{*}|=n-r$. ∎

In this case, Algorithm EA in fact provides slightly worse guarantees. Moreover the bound for MUB is optimal:

For the class of submodular functions with curvature $\kappa_{f}<1$, no poly-time algorithm can achieve an approximation factor of $\frac{n^{1-3\epsilon}}{1+(n^{1-3\epsilon}-1)(1-\kappa_{f})+\delta\kappa_{f}}$ for the SST problem for any $\epsilon,\delta>0$.

In this case, we use the construction of , and define $f_{\kappa}^{R}(X)=\kappa_{f}\min\{|X\cap\bar{R}|+min\{|X\cap R|,\beta\},\alpha\}+(1-\kappa_{f})|X|$, and $g^{\kappa_{f}}(X)=\kappa_{f}min\{|X|,\alpha\}+(1-\kappa_{f})|X|$, where $\alpha=n^{1+\epsilon}$, $\beta=n^{3\epsilon}(1+\delta)$ and $|R|=\alpha$. For the formal graph construction, see . Then with high probability $R$ is connected in the graph . Since $f_{R}$ and $g$ are indistinguishable with high probability, so are $f_{\kappa}^{R}$ and $g^{\kappa_{f}}$. Then notice that the minimum value of $f_{\kappa}^{R}$ and $g^{\kappa_{f}}$ are $\kappa_{f}\beta+(1-\kappa_{f})n$ and $n$ respectively, and it is clear that the ratio between them is better than $\frac{n^{1-3\epsilon}}{1+(n^{1-3\epsilon}-1)(1-\kappa_{f})+\delta\kappa_{f}}$. Hence if any algorithm performs better than this, it will be able to distinguish $f_{R}$ and $g$ with high probability, which is a contradiction. ∎

Ana analogous analysis applies to combinatorial constraints like Steiner trees .

Minimum submodular perfect matching (SPM): Here, we aim to find a perfect matching in a graph that minimizes a monotone submodular function. Corollary 5.1 implies that an MUB approximation will achieve an approximation factor of at most $\frac{n}{2+(n-2)(1-\kappa_{f})}$. This bound is also tight:

Given a submodular function with a curvature $\kappa_{f}>0$ and any $\epsilon>0$, no polynomial-time algorithm achieves an approximation factor better than $\frac{n^{1-3\epsilon}}{2+(n^{1-3\epsilon}-2)(1-\kappa_{f})+2\delta\kappa_{f}}$ for the SPM problem.

We use the same submodular functions as the spanning tree case, and it can be shown that with high probability the set $R$ contains a perfect matching and the two functions are indistinguishable. Taking the ratio of $g^{\kappa_{f}}$ and $f_{R}^{\kappa_{f}}$, provides the above result. ∎

The minimum submodular edge cover involves finding an edge cover (subset of edges covering all vertices), with minimum submodular cost. This problem has been investigated in , and they show that this problem is $O(n)$ hard. Algorithm MUB provides an approximation guarantee which is no worse than $\frac{2n}{2+(n-2)(1-\kappa_{f})}$. We can show a almost matching hardness lower bound for this problem.

Given a submodular function, with curvature coefficient $\kappa_{f}$ and any $\epsilon,\delta>0$, there cannot exist a polynomial-time approximation algorithm, which achieves an approximation better than $\frac{n^{1-3\epsilon}}{2+(n^{1-3\epsilon}-2)(1-\kappa_{f})+2\delta\kappa_{f}}$ for the minimum submodular edge cover problem.

We can use the construction of to show this. However a simple observation shows that a perfect matching is also an edge cover, and hence the hardness of edge cover has to be at least as much as the hardness of perfect matchings. ∎

1 Experiments

We end this section by empirically demonstrating the performance of MUB and EA and their precise dependence on curvature. We focus on cardinality lower bound constraints, $\mathcal{C}=\{X\subseteq V:|X|\geq\alpha\}$ and the “worst-case” class of functions that has been used throughout this paper to prove lower bounds,

where $\bar{R}=V\backslash R$ and $R\subseteq V$ is random set such that $|R|=\alpha$. We adjust $\alpha=n^{1/2+\epsilon}$ and $\beta=n^{2\epsilon}$ by a parameter $\epsilon$. The smaller $\epsilon$ is, the harder the problem. The function (40) has curvature $\kappa_{f}=1$. To obtain a function with specific curvature $\kappa$, we define

In all our experiments, we take the average over $20$ random draws of $R$. We first set $\kappa=1$ and vary $\epsilon$. Figure 1(a) shows the empirical approximation factors obtained using EA and MUB, and the theoretical bound. The empirical factors follow the theoretical results very closely. Empirically, we also see that the problem becomes harder as $\epsilon$ decreases. Next we fix $\epsilon=0.1$ and vary the curvature $\kappa$ in $f^{R}_{\kappa}$. Figure 1(b) illustrates that the theoretical and empirical approximation factors improve significantly as $\kappa$ decreases. Hence, much better approximations than the previous theoretical lower bounds are possible if $\kappa$ is not too large. This observation can be very important in practice. Here, too, the empirical upper bounds follow the theoretical bounds very closely.

Figures 1(c) and (d) show results for larger $\alpha$ and $\beta=1$. In Figure 1(c), as $\alpha$ increases, the empirical factors improve. In particular, as predicted by the theoretical bounds, EA outperforms MUB for large $\alpha$ and, for $\alpha\geq n^{2/3}$, EA finds the optimal solution. In addition, Figures 1(b) and (d) illustrate the theoretical and empirical effect of curvature: as $n$ grows, the bounds saturate and approximate a constant $1/(1-\kappa)$ – they do not grow polynomially in $n$. Overall, we see that the empirical results quite closely follow our theoretical results, and that, as the theory suggests, curvature significantly affects the approximation factors.