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.
Cite
Text
Kyng et al. "Fast, Provable Algorithms for Isotonic Regression in All L_p-Norms." Neural Information Processing Systems, 2015.Markdown
[Kyng et al. "Fast, Provable Algorithms for Isotonic Regression in All L_p-Norms." Neural Information Processing Systems, 2015.](https://mlanthology.org/neurips/2015/kyng2015neurips-fast/)BibTeX
@inproceedings{kyng2015neurips-fast,
title = {{Fast, Provable Algorithms for Isotonic Regression in All L_p-Norms}},
author = {Kyng, Rasmus and Rao, Anup and Sachdeva, Sushant},
booktitle = {Neural Information Processing Systems},
year = {2015},
pages = {2719-2727},
url = {https://mlanthology.org/neurips/2015/kyng2015neurips-fast/}
}