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

Code

• github.com/sachdevasushant/Isotonic
  OfficialIn papernone★ 0

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 _p-norms with rigorous performance guarantees. Our algorithms are quite practical, and their variants can be implemented to run fast in practice.

Tasks

Reproductions