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

arXiv: https://arxiv.org/abs/1507.00710 · HTML: https://mlsanity.com/paper/1507.00710/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2015.

## Built on by (most cited first, 3 of 3)

- [Size and depth of monotone neural networks: interpolation and approximation](https://mlsanity.com/paper/2207.05275/) (2022)
- [Differentiable Neural Networks with RePU Activation: with Applications to Score Estimation and Isotonic Regression](https://mlsanity.com/paper/2305.00608/) (2023)
- [Geometric Meta-Learning via Coupled Ricci Flow: Unifying Knowledge Representation and Quantum Entanglement](https://mlsanity.com/paper/2503.19867/) (2025)

## Abstract (arXiv)

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.