Extended Abstract: We provide algorithms for isotonic regression on arbitrary dags minimizing L₀ error (Hamming distance). This is also known as monotonic relabeling and is applicable when labels have a linear ordering but not necessarily a metric. There may be exponentially many optimal relabelings, so we look at secondary criteria to determine which are best. For simple ordinal labels the criterion is maximizing the number of labels which are only changed to an adjacent label (and recursively apply this). For real-valued labels we minimize the L_p error. For linearly ordered sets we also give algorithms which minimize the sum of the L_p and weighted L₀ errors, a form of penalized (regularized) regression. We also examine L₀ isotonic regression on multidimensional coordinate-wise orderings.

Basic L₀ algorithms here and elsewhere are based on violator graphs and flow algorithms. Flow algorithms have been undergoing rapid improvement (in O-notation), which leads to faster regression algorithms. For linear orderings we use a different approach which is more direct, not constructing a violator graph. For multidimensional orderings we use the basic approach, but show how to rapidly construct a violator graph of size o(n²), which is in general smaller than the transitive reduction of the violator graph.

Keywords: L0 isotonic regression, monotonic, shape constrained nonparametric regression, linear order, multidimensional grid, product order, rendezvous graph, domination, violator graph

Complete paper. arXiv:2107.00251

Related work: Here is an overview of my work on shape constrained regression (isotonic, unimodal, step). The paper L_p Isotonic Regression using an L₀ Approach 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.