Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?
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:


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).
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.
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.
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)
Algorithms for minimizing submodular functions are also a bit slow, the fastest running in time $O(n^5)$ (see Iwata's survey).