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?