Weighted L∞ Isotonic Regression

Quentin F. Stout
Computer Science and Engineering, University of Michigan

 

Extended Abstract: This paper gives algorithms for determining weighted L∞ isotonic regressions satisfying order constraints on a partially ordered set specified via a directed acyclic graph (dag). Except for degenerate caes, L∞ isotonic regression is not unique, and some regressions have undesirable properties. Hence we examine properties of the regressions an algorithm produces, in adition to its running time. Note that the L∞ metric is also called the uniform metric, Chebyshev metric, and minimax metric, and isotonic regression is also known as monotonic regression. Isotonic regression is a form of nonparametric shape-constrained regression.

For a dag with n vertices and m edges we give an algorithm taking Θ(m log n) time. Unfortunately it is based on parametric search, which is completely infeasible, so we also give a simple, fast, randomized parametric search algorithm taking Θ(m log n) expected time with high probability. Further, this approach can easily replace parametric search in several other problems, such as approximation by step functions. In practice it should be significantly faster than algorithms with guaranteed worst-case performance.

The properties of the regressions these two algorithms produce are not always desireable. For example, the algorithms are not monotonic, in that there can be functions f and g where pointwise f ≥ g, but the isotonic regression produced for f is not pointwise ≥ the regression produced for g. An approach that is monotonic is to solve the prefix isotonic regression problem, where for every element x in the partial order, you determine the regression error for the isotonic regression on x and all of its predecessors. This regression is called Prefix. An algorithm is given for computing Prefix of linear and tree orders in Θ(n log n) time. It is also used to find a unimodal regression on linear orders in the same time bound. This completes the work in Unimodal Regression via Prefix Isotonic Regression by solving the remaining open case, namely L∞ isotonic regression on weighted data. This is significantly more difficult than the unweighted data case.

Algorithms are also given to determine unimodal regression for an undirected tree, for isotonic regressions where the regression values must come from a specified set, and for isotonic regressions when the number of different weights, or number of different values, is much smaller than the number of vertices. An algorithm is also given for isotonic regression on a rooted tree, where the value of a parent must be the largest value of its children. We call this ``river isotonic regression'' since it is similar to the naming convention for rivers.

The parametric search and randomized algorithms mentioned above can produce Max, the regression which is pointwise the largest of any L∞ isotonic regression, and Min, the pointwise minimum. Other regressions considered are Basic and Strict. Basic is the most commonly studied one, but people have rarely addressed the fact that it is nontrivial to compute for weighted data. Prefix is somewhat easier. Strict is discussed more thoroughly in Strict L∞ isotonic regression. Strict regression is the "best best" L∞ isotonic regression. It is the limit, as p → ∞, of Lp isotonic regression. It has a strong property concerning the number of vertices with large regression errors (see the paper for a precise statement). Prefix and Basic have a somewhat weaker property in that they minimize the set of vertices with maximal error. At the other end of the spectrum, at any vertex, one or both of Max and Min have the worst error among all isotonic regressions.

Complete paper. This appears in J. Computer Sys. and Sci. 91 (2018), pp. 69-81. This version is a major revision of a much longer version from 2008. That version included an approach for multidimensional data which was moved to Isotonic Regression for Multiple Independent Variables where the approach was also applied to L1 and L2 isotonic regressions. That paper was published a few years ago, and now, after a sequence of absurdly long delays, including ones caused by the death of an editor, this version is finally published.

 

Related work: Here is an overview of my work on shape constrained regression (isotonic, unimodal, step). One paper closely related to this one is L∞ Isotonic Regression for Linear, Multidimensional, and Tree Orders. Here is information about the fastest (in O-notation) isotonic regression algorithms known to date, for a variety of orderings and metrics.

Quentin's Home Copyright © 2008-2024 Quentin F. Stout.