Fast, Provable Algorithms for Isotonic Regression in all $\ell_{p}$-norms
This work provides incremental improvements in algorithms for isotonic regression, benefiting researchers and practitioners in optimization and machine learning.
The paper tackles the problem of computing Isotonic Regression for all weighted ℓp-norms with improved algorithms that offer rigorous performance guarantees, resulting in practical and fast implementations.
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.