  We consider the minimization of submodular functions subject to ordering
constraints. We show that this optimization problem can be cast as a convex
optimization problem on a space of uni-dimensional measures, with ordering
constraints corresponding to first-order stochastic dominance. We propose new
discretization schemes that lead to simple and efficient algorithms based on
zero-th, first, or higher order oracles; these algorithms also lead to
improvements without isotonic constraints. Finally, our experiments show that
non-convex loss functions can be much more robust to outliers for isotonic
regression, while still leading to an efficient optimization problem.
