  We consider a class of sparsity-inducing regularization terms based on
submodular functions. While previous work has focused on non-decreasing
functions, we explore symmetric submodular functions and their \lova
extensions. We show that the Lovasz extension may be seen as the convex
envelope of a function that depends on level sets (i.e., the set of indices
whose corresponding components of the underlying predictor are greater than a
given constant): this leads to a class of convex structured regularization
terms that impose prior knowledge on the level sets, and not only on the
supports of the underlying predictors. We provide a unified set of optimization
algorithms, such as proximal operators, and theoretical guarantees (allowed
level sets and recovery conditions). By selecting specific submodular
functions, we give a new interpretation to known norms, such as the total
variation; we also define new norms, in particular ones that are based on order
statistics with application to clustering and outlier detection, and on noisy
cuts in graphs with application to change point detection in the presence of
outliers.
