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

2015/07/02 by Kyng, Rasmus, Rao, Anup, Sachdeva, Sushant
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1507.00710

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.

Related

• L_p Isotonic Regression Algorithms Using an L₀ Approach
• L infinity Isotonic Regression for Linear, Multidimensional, and Tree Orders
• Optimal solutions to the isotonic regression problem
• Private Isotonic Regression
• Lipschitz Unimodal and Isotonic Regression on Paths and Trees