`

Timezone: »

 
Poster
Fast, Provable Algorithms for Isotonic Regression in all L_p-norms
Rasmus Kyng · Anup Rao · Sushant Sachdeva

Tue Dec 08 04:00 PM -- 08:59 PM (PST) @ 210 C #86 #None
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.

Author Information

Rasmus Kyng (Yale University)
Anup Rao (School of Computer Science, Georgia Tech)
Sushant Sachdeva (Yale University)

More from the Same Authors