Timezone: »
Poster
Fast, Provable Algorithms for Isotonic Regression in all L_p-norms
Rasmus Kyng · Anup Rao · Sushant Sachdeva
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
-
2022 Poster: Sample Constrained Treatment Effect Estimation »
Raghavendra Addanki · David Arbour · Tung Mai · Cameron Musco · Anup Rao -
2020 Poster: Model Selection in Contextual Stochastic Bandit Problems »
Aldo Pacchiano · My Phan · Yasin Abbasi Yadkori · Anup Rao · Julian Zimmert · Tor Lattimore · Csaba Szepesvari -
2019 Poster: Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression »
Deeksha Adil · Richard Peng · Sushant Sachdeva