Overview:

In this work, we propose a novel convex surrogate loss function for submodular losses, the Lovasz hinge based on the definition of Lovász extension [1], which leads to O(p log p) complexity with O(p) oracle accesses to the loss function to compute a gradient or cutting-plane. As a result, we have developed the first tractable convex surrogates in the literature for submodular losses. 

Reference:

[1] Lovasz, László. Submodular functions and convexity. In Mathematical Programming The State of the Art, pp. 235–257. Springer, 1983.

[2] J. Yu and M. B. Blaschko. Learning submodular losses with the Lovasz hinge. In Proceedings of the International Conference on Machine Learning, 2015.