Quentin F. Stout
Computer Science and Engineering, University of Michigan
Extended Abstract: Significant advances in maximum flow algorithms have changed the relative performance of various approaches to isotonic regression. If the transitive closure is given then the standard approach used for L0 (Hamming distance) isotonic regression (finding anti-chains in the transitive closure of the violator dag), combined with new flow algorithms, gives an L1 isotonic regression algorithm taking Θ̃(n2) time on a graph of n vertices. The previous fastest was Θ(n3). For points in d-dimensional space with coordinate-wise ordering, d ≥2, L1 regression can be found in o(n3/2) time, improving on the previous best of Ω(n2). Similar results are obtained for Lp approximations, 1 < p < ∞, and for exact L2 regression when the values and weights are restricted.
The improvements come from the observation that for binary valued data, L0 and L1 regression are the same. Previously that had been used to suggest that for such data the current L1 algorithms should be used, but the improvements in the flow algorithms have now helped create L0 algorithms that are faster. Using partitioning then gives faster L1 algorithms for arbitrary real-valued data.Keywords: L0 isotonic regression, monotonic, shape constrained nonparametric regression, linear order, multidimensional grid, product order, rendezvous graph, domination, violator graph, flow algorithm
Complete paper. arXiv:2107.00251
Related work: Here is an overview of my work on shape constrained regression (isotonic, unimodal, step). The paper L0 Isotonic Regression with Secondary Objectives is particularly relevant. Here is information about the fastest (in O-notation) isotonic regression algorithms known to date, for a variety of orderings and metrics.
|
Copyright © 2024 Quentin F. Stout. |