Interactive demo · Nonparametric Statistical Inference · Chapter 10

Isotonic regression and pool-adjacent-violators

If the regression function is known to be nondecreasing, least squares over all nondecreasing functions gives a consistent estimate with no bandwidth to choose. The fit is a step function: the slopes of the greatest convex minorant of the cumulative sums of the responses. Pool-adjacent-violators computes it in one pass: take the points from left to right, and whenever a new block has a smaller mean than the block before it, merge the two and keep merging backwards until the block means increase again.

Points processed by PAV k

Noise sd σ

True function r

Sample size n

Try these

Design xi = (i − 1/2)/n, Yi = r(xi) + σεi with Normal errors. The fit after k points is the isotonic regression of the first k responses, which is exactly the state of the algorithm's stack of blocks at that moment. In the right panel the grey points are Pj = (j, Y1 + ... + Yj) and the red polygon is their greatest convex minorant; the slope of its segment above (j − 1, j) is the fitted value at xj. The reference line in the readout is the rate n−1/3(σ2V)1/3 of (10.30), with V the total variation of r.

In the lecture notes