An Efficient Pruning Algorithm for Robust Isotonic Regression
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 O(n/ ) 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 (O(n log(1/ ))) 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.
This paper studies fast algorithms for isotonic regression under general loss functions. The author(s) build upon an existing dynamic programming (DP) approach by suggesting two main strategies to prune points -- one based on pruning with lower/upper bounds based on the Lipschitz constants of the loss functions, and another based on "linear underestimators" (which are assumed to be computable in constant time).  Overall this is a well written paper. There are minor language issues and ommisions which can be ironed. A few examples are  line 69 what is S in argmin_{z in [0,1]} \sum_{i \in S} f_i(z) line 181 the tighter "the" underestimator .. line 240 "and run" should be "and ran"  In my opinion the proofs presented in the paper appear a bit heuristic and "hand-wavy", so one suggestion that I have is to strengthen the proofs.   One thing that does not become very clear from the paper is the following: does the DP have complexity O(nk) in the general case, and O(n log k) in the convex case (or only a special variant of it has O(n log k) in the convex case)? If so, then the improvement of this paper is not in improving those orders, but is in improving the constants of the orders?  Another related question is does the DP require the loss functions to be Lipschitz, as required by the pruning algorithm? If not that would be a disadvantage to the pruning algorithm which seems to rely on the Lipschitz assumptions (and is hence not applicable to the Euclidean distance which is the classic isotonic regression).   Finally, I think that including back the omitted plot "running time vs k" would be beneficial since one would see how much real time it takes to run the algorithm.