Skip to yearly menu bar Skip to main content


Poster

Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization

Francis Bach

Room 210 #38

Keywords: [ Convex Optimization ] [ Submodular Optimization ] [ Non-Convex Optimization ]


Abstract:

We consider the minimization of submodular functions subject to ordering constraints. We show that this potentially non-convex 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 being solvable in polynomial time.

Live content is unavailable. Log in and register to view live content