Timezone: »

 
Poster
Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization
Francis Bach

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 210 #38
in Wed Poster Session B »

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.

Keywords: Convex Optimization · Submodular Optimization · Non-Convex Optimization
[ Paper]  [ Poster] 

Author Information

Francis Bach (INRIA - Ecole Normale Superieure)

More from the Same Authors