Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

Question

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).

I am particularly interested in algorithms (specially their application to machine learning, and whenever possible, proving theoretical guarantees for them, wether these guarantees are in complexity or learnability).

I'd be interested in knowing if there are any "heuristic" algorithms out there in the area of sub modularity and machine learning, with unknown guarantees. From my current knowledge of the topic, the most common heuristic seems to be the "greedy" heuristic, and it seems to be quite well understood. Hence, I was wondering if there was any open problems in the area of designing new algorithms (or improving current ones) or algorithms that already exists, that don't have any guarantees. Is there anything open questions related with theoretical guarantees that is open in sub modularity?

Or of if there aren't any such open question, are there any open question in the intersection of sub modularity and machine learning?

Answer 1

There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The following are just a sample:

1. Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known approximation ratio is $1/e+0.004$ (BFNS14). When "at most" is replaced by "exactly", the best known approximation ratio is 0.356 (also BFNS14).

2. Given a non-negative monotone submodular function and $k$ matroids, find a set $A$ belonging to all different matroids and maximizing $f(A)$. When $k=1$ the best approximation ratio is $1-1/e$, and this is optimal. For larger $k$, LSV give a $1/k$ approximation, but this is probably not tight.

3. There are two algorithms for maximizing a non-negative monotone submodular function over a matroid that give the optimal approximation ratio $1-1/e$: the continuous greedy algorithm and the non-oblivious local search algorithm. Both are randomized. The best known deterministic algorithm is the greedy algorithm, giving a $1/2$ approximation. Can we separate deterministic and randomized algorithms in this oracle setting? A similar question arises in the non-monotone unconstrained case, in which BFNS12 give an optimal randomized $1/2$ approximation algorithm, but the best known deterministic algorithms (one in BFNS12 and an earlier local search algorithm due to FMV) give only a $1/3$ approximation.

4. Both the continuous greedy algorithm and the non-oblivious local search algorithm are rather slow. Is there a fast, $\tilde{O}(n)$ algorithm for maximizing a monotone submodular function over a matroid? (see BV for the case of a uniform matroid)

5. Algorithms for minimizing submodular functions are also a bit slow, the fastest running in time $O(n^5)$ (see Iwata's survey).