# Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization

arXiv: https://arxiv.org/abs/1707.09157 · HTML: https://mlsanity.com/paper/1707.09157/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jul 2017.

## Built on by (most cited first, 1 of 1)

- [Revisiting Matching Pursuit: Beyond Approximate Submodularity](https://mlsanity.com/paper/2305.07782/) (2023)

## Abstract (arXiv)

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.