Abstract

 We study a generalization of the classic isotonic regression problem where we allow separable nonconvex objective functions, focusing on the case where the functions are estimators used in robust regression. One can solve this problem to within -accuracy (of the global minimum) in using a simple dynamic program, and the complexity of this approach is independent of the underlying functions. We introduce an algorithm that combines techniques from the convex case with branchand-bound ideas that is able to exploit the shape of the functions. Our algorithm achieves the best known bounds for both the convex case and the general nonconvex case. Experiments show that this algorithm can perform much faster than the dynamic programming approach on robust estimators, especially as the desired accuracy increases.