Timezone: »

An Efficient Pruning Algorithm for Robust Isotonic Regression
Cong Han Lim

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #60

We study a generalization of the classic isotonic regression problem where we allow separable nonconvex objective functions, focusing on the case of estimators used in robust regression. A simple dynamic programming approach allows us to solve this problem to within ε-accuracy (of the global minimum) in time linear in 1/ε and the dimension. We can combine techniques from the convex case with branch-and-bound ideas to form a new algorithm for this problem that naturally exploits the shape of the objective function. Our algorithm achieves the best bounds for both the general nonconvex and convex case (linear in log (1/ε)), while performing much faster in practice than a straightforward dynamic programming approach, especially as the desired accuracy increases.

Author Information

Cong Han Lim (Georgia Tech)

More from the Same Authors