Fast, Provable Algorithms for Isotonic Regression in all L_p-norms

Rasmus Kyng; Anup Rao; Sushant Sachdeva

NeurIPS 2015poster61 citations

Fast, Provable Algorithms for Isotonic Regression in all L_p-norms

Abstract

Given a directed acyclic graph $G,$ and a set of values $y$ on the vertices, the Isotonic Regression of $y$ is a vector $x$ that respects the partial order described by $G,$ and minimizes $\|x-y\|,$ for a specified norm. This paper gives improved algorithms for computing the Isotonic Regression for all weighted $\ell_{p}$-norms with rigorous performance guarantees. Our algorithms are quite practical, and their variants can be implemented to run fast in practice.

BibTeX

@inproceedings{NIPS2015_be53ee61,
 author = {Kyng, Rasmus and Rao, Anup and Sachdeva, Sushant},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {C. Cortes and N. Lawrence and D. Lee and M. Sugiyama and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Fast, Provable Algorithms for Isotonic Regression in all L\_p-norms},
 url = {https://proceedings.neurips.cc/paper_files/paper/2015/file/be53ee61104935234b174e62a07e53cf-Paper.pdf},
 volume = {28},
 year = {2015}
}