Decomposing isotonic regression for efficiently solving large problems

A new algorithm for isotonic regression is presented based on recursively par-titioning the solution space. We develop efficient methods for each partitioning subproblem through an equivalent representation as a network flow problem, and prove that this sequence of partitions converges to the global solution. These net-work flow problems can further be decomposed in order to solve very large prob-lems. Success of isotonic regression in prediction and our algorithm’s favorable computational properties are demonstrated through simulated examples as large as 2 × 105 variables and 107 constraints.