nips nips2010 nips2010-58 nips2010-58-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ronny Luss, Saharon Rosset, Moni Shahar
Abstract: A new algorithm for isotonic regression is presented based on recursively partitioning 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 network flow problems can further be decomposed in order to solve very large problems. 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.
[1] R.E. Barlow and H.D. Brunk. The isotonic regression problem and its dual. Journal of the American Statistical Association, 67(337):140–147, 1972.
[2] G. Obozinski, G. Lanckriet, C. Grant, M.I. Jordan, and W.S. Noble. Consistent probabilistic outputs for protein function prediction. Genome Biology, 9:247–254, 2008. Open Access.
[3] M.J. Schell and B. Singh. The reduced monotonic regression method. Journal of the American Statistical Association, 92(437):128–135, 1997.
[4] J.B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1), 1964.
[5] H. Block, S. Qian, and A. Sampson. Structure algorithms for partially ordered isotonic regression. Journal of Computational and Graphical Statistcs, 3(3):285–300, 1994.
[6] O. Burdakov, O. Sysoev, A. Grimvall, and M. Hussian. An o(n2 ) algorithm for isotonic regression. 83:25– 83, 2006. In: G. Di Pillo and M. Roma (Eds) Large-Scale Nonlinear Optimization. Series: Nonconvex Optimization and Its Applications.
[7] C.-I. C. Lee. The min-max algorithm and isotonic regression. The Annals of Statistics, 11(2):467–477, 1983.
[8] J. de Leeuw, K. Hornik, and P. Mair. Isotone optimization in r: Pool-adjacent-violators algorithm (pava) and active set methods. 2009. UC Los Angeles: Department of Statistics, UCLA. Retrieved from: http://cran.r-project.org/web/packages/isotone/vignettes/isotone.pdf.
[9] W.L. Maxwell and J.A. Muckstadt. Establishing consistent and realistic reorder intervals in productiondistribution systems. Operations Research, 33(6):1316–1341, 1985.
[10] R.D.C. Monteiro and I. Adler. Interior path following primal-dual algorithms. part II: Convex quadratic programming. Mathematical Programming, 44:43–66, 1989.
[11] O. Burdakov, O. Sysoev, and A. Grimvall. Generalized PAV algorithm with block refinement for partially ordered monotonic regression. pages 23–37, 2009. In: A. Feelders and R. Potharst (Eds.) Proc. of the Workshop on Learning Monotone Models from Data at the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases.
[12] P.M. Pardalos and G. Xue. Algorithms for a class of isotonic regression problems. Algorithmica, 23:211– 222, 1999.
[13] K.G. Murty. Linear Programming. John Wiley & Sons, Inc., 1983.
[14] R. Chandrasekaran, Y.U. Ryu, V.S. Jacob, and S. Hong. Isotonic separation. INFORMS Journal on Computing, 17(4):462–474, 2005.
[15] MOSEK ApS. The MOSEK optimization tools manual. version 6.0, revision 61. 2010. Software available at http://www.mosek.com.
[16] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., 1993. 9