Isotonic Regression (PAVA)

Background

Isotonic regression fits the best monotone non-decreasing function to data. Unlike Platt (a 2-parameter sigmoid), isotonic is non-parametric — more flexible at the cost of needing more data. The Pool-Adjacent-Violators Algorithm (PAVA) computes it in linear time after a single sort.

Problem statement

Implement pava(x, y). Sort observations by x ascending. Walk left-to-right maintaining a stack of (sum, count) blocks; when adjacent blocks violate monotonicity (left block's mean > right block's mean), pool them into a single block with merged sum and count. Expand block averages back to the original input order.

Input

• x — array-like of floats, the predictor.
• y — array-like of floats, the response.

Output

Returns np.ndarray of length $n$, the calibrated $\hat y_i$ at each input position. The values are monotone non-decreasing when sorted by x.

Examples

Example 1 — already-monotone input passes through

Input:  x=[1,2,3], y=[1.0, 2.0, 3.0]
Output: [1.0, 2.0, 3.0]

Example 2 — pool a violator

Input:  x=[1,2,3], y=[1.0, 3.0, 2.0]
Output: [1.0, 2.5, 2.5]

Explanation: the second and third points violate monotonicity; their pooled mean is $2.5$.

Example 3 — random noise → output is monotone non-decreasing

Input:  random y at sorted x
Output: post-isotonic y is monotone (np.diff >= 0)

Constraints

• Input lengths must match.
• Output is in original input order, not sorted order.
• Sort is stable so duplicate x values are handled deterministically.

Notes

• Platt vs Isotonic. Platt fits 2 parameters and needs little data; isotonic fits an arbitrary monotone function and needs at least a few hundred samples to avoid overfitting.
• Convex variant. Convex regression (PAVA's cousin) extends to higher-dimensional shape constraints; out of scope here.