Isotonic regression

Isotonic regression estimates a sequence or function subject to an order constraint such as ${\theta }_1\le \cdots \le {\theta }_n$.

For observations $y_1,\dots ,y_n$ in a known covariate order, the isotonic least squares estimator solvesIt is the orthogonal projection of the observation vector onto a closed convex cone of nondecreasing sequences. Strict convexity of the squared distance gives a unique estimate.

For data $(3,1,2)$, the first pair violates monotonicity. Pooling it gives mean two, producing $(2,2,2)$ with squared error two. The pool adjacent violators algorithm repeatedly merges neighboring blocks whose means are out of order; the fitted value is constant at the block mean on each final block.

Positive observation weights replace squared error by ${\sum }_i{w}_i(y_i-{\theta }_i{)}^2$ and block means by weighted means. The order restriction regularizes the estimate without specifying a fixed polynomial form. The method requires the ordering to be meaningful; it does not discover an unknown covariate order from the response values.

The pool adjacent violators algorithm solves weighted isotonic regression: minimize ${\sum }_i{w}_i(y_i-{\theta }_i{)}^2$ with $w_i>0$ and ${\theta }_1\le \cdots \le {\theta }_n$. Start with singleton blocks. Whenever consecutive fitted block means decrease, merge the two blocks and replace them by their weighted mean; continue until no violation remains. For equal weights and observations $(3,1,2)$, merging the first two gives the solution $(2,2,2)$. A stack implementation revisits each block only when merging it, giving linear time. Pooling is required by the order-constrained optimum: two reversed adjacent blocks cannot remain separate fitted levels.

For a concrete isotonic regression model, observe $Y_i={\theta }_i+{\epsilon }_i$ with independent Gaussian distribution errors of expected value zero and fixed variance ${\sigma }^2>0$. Let ${\Theta }_V=\{0\le {\theta }_1\le \cdots \le {\theta }_n\le V\}$ for fixed $V>0$, and use normalized squared-error loss $n^{-1}{\sum }_i({\hat{\theta }}_i-{\theta }_i{)}^2$. The minimax risk over ${\Theta }_V$ has orderas $n\to \infty$ with $V,\sigma$ fixed. This states the model and loss behind the shorthand rate $n^{-2/3}$.

The isotonic least squares estimator satisfies an upper bound of order $({\sigma }^{2}V/n{)}^{2/3}+{\sigma }^2\log (en)/n$. Locally increasing sequences supply matching lower bounds for the first term. The primary analysis also shows why a worst-case rate does not describe every signal: when the true sequence has few constant blocks, the risk can be substantially smaller.^[ref]

A heuristic for the exponent is to approximate a changing monotone signal by $k$ blocks: squared approximation error scales as $(V/k{)}^2$, while estimating $k$ block levels costs approximately ${\sigma }^{2}k/n$. Balancing these gives $k\asymp (n{V}^2/{\sigma }^2{)}^{1/3}$ and risk $({\sigma }^{2}V/n{)}^{2/3}$. This balance motivates the rate; it does not replace the lower-bound argument. Uniformly constant signals or a variation bound shrinking with $n$ require their own regime analysis.