L infinity Isotonic Regression for Linear, Multidimensional, and Tree Orders

2015/07/08 by Quentin F. Stout, Stout, Quentin F.
Computer Science · #Bayesian Modeling and Causal Inference #Computation (stat.CO) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Data Classification

paper · pdf · doi:10.48550/arxiv.1507.02226

openalex publication_date 2015/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Algorithms are given for determining L_∞ isotonic regression of weighted data. For a linear order, grid in multidimensional space, or tree, of n vertices, optimal algorithms are given, taking Θ(n) time. These improve upon previous algorithms by a factor of Ω(log n). For vertices at arbitrary positions in d-dimensional space a Θ(n log^d-1 n) algorithm employs iterative sorting to yield the functionality of a multidimensional structure while using only Θ(n) space. The algorithms utilize a new non-constructive feasibility test on a rendezvous graph, with bounded error envelopes at each vertex.

Related

• L_p Isotonic Regression Algorithms Using an L₀ Approach
• Lipschitz Unimodal and Isotonic Regression on Paths and Trees
• Fast, Provable Algorithms for Isotonic Regression in all ℓ_p-norms
• Optimal Reduced Isotonic Regression
• L₀ Isotonic Regression With Secondary Objectives