Isotonic Regression
Fit the data as closely as you can, subject to one rule: a larger input never gets a smaller output. Drag data points and watch adjacent violators pool, see why probability vectors can't be put in order, collect the supporting lines of a convex function, and find the cycles that catch a map pretending to be monotone.
Built from the notes and meetings of the Rates for CMIR project (cyclically monotone isotonic regression), which studies H. Bao, A. Eshraghi and Y. Wang, “Brenier Isotonic Regression” (AISTATS 2026, PMLR 300, 883–891). Convexity, subgradients and cyclic monotonicity follow R. T. Rockafellar, Convex Analysis (Princeton, 1970), §§23–24. The paper's optimal-transport step comes next; until then, the optimal transport module on the Gradient Flows page covers the background. The questions and examples are written for this page. For how this subject connects to the others, see the roadmap.
Regression: fitting values, not formulas
Machine learning, at its core, is making predictions from data: given input–output pairs, predict the output for an input you haven't seen. Regression is the tool. Fit a function through the data, and the function makes the predictions.
The idea
Why that needs a constraint. With no restriction on the
Where monotonicity is the right rule. The paper's main application is calibration. A classifier outputs a score, and we want to turn the score into an honest probability: “of all the times the model said 0.8, how often was it right?” Whatever the map from scores to probabilities is, a higher score should never mean a lower probability, and the shape is otherwise unknown. Isotonic regression fits exactly that. Other examples: a drug's effect should not fall as the dose rises, and in a single-index model
Worked example
Data
Fit
(one parameter) by least squares.Minimize
: setting the derivative in to 0 gives . The fitted values are , and the model predicts .Now fit the values directly, with no constraint.
, error 0. The data are already increasing, so the isotonic fit is the same.The nonparametric fit gives values only at
. How would you predict at ?Any increasing function through the fitted points is consistent with the constraint; a common choice is to interpolate linearly (
) or to use the step function that stays at the last fitted value. The fit commits to the order, not to a formula.
Check your understanding
Minimize
- 0, at
. - The variance of the
, at .That is the best constant fit; here every is free.
Why is isotonic regression called nonparametric?
- Because it has no constraints.It has a constraint: monotonicity.
- Because it fits the values
directly instead of the parameters of a formula. - Because it ignores the inputs
.The inputs decide the order the fitted values must respect.
Isotonic regression and pooling
Fit the outputs as closely as possible, but never let the fitted curve go down. When two neighbours are out of order, the fix is to merge them into one value, their average, and keep merging until nothing is out of order.
The idea
Without sorting. The same constraint can be written for every pair at once:
Why the average? If two observations must share one fitted value
(The minus signs come from the chain rule:
Show why a violating pair must be pooled
Suppose
(Expand: the quadratic terms give
Explore
Worked example
Inputs
Which pair violates the order?
: the first two. ( is fine.)Pool them. What is the fit, and is it isotonic?
Both become
, giving . Now : no violations, so PAVA stops.Compare its error with another isotonic candidate,
.Pooled:
. Candidate: . Pooling splits the disagreement evenly, which costs less than putting all of it on one point: .Change the data to
. Run PAVA.Pool the first two to
; now is a new violation, so pool all three: , the mean . One merge can create the next one, which is why PAVA loops until nothing is out of order.
Check your understanding
If the data
- The data themselves, with error 0.
- A smoothed version of the data.Isotonic regression only changes values that break the order.
The data are strictly decreasing,
- The data reversed.The fitted values are attached to the inputs; you can't move them to other inputs.
- The constant
at every point.
Practice
Weighted poolingThe mean of a block
A block of
Outline
- The best
minimizes , whose derivative is .Why?
Differentiate each term by the chain rule.
- Setting it to 0 gives
.Why?
. The function is a parabola opening upward, so this critical point is the minimum. - Merged blocks get
.Why?
The mean of the union: the total
divided by the count. So PAVA only needs each block's size and mean, not its points.
Running PAVAFive points
Run PAVA on
Outline
- The only violation is
; pool to get .Why?
, , , . - Now
: pool the block with the next point, giving .Why?
The merged block is
, mean . - No violations remain; the error is
.Why?
.
When the output is a vector
Isotonic regression needs to say which of two outputs is bigger. Numbers can be compared; vectors of class probabilities can't, at least not in any single natural way. That is the problem the paper solves.
The idea
Why outputs become vectors. A binary classifier can report one number, say
Aside: why classifiers output probabilities at all
The labels are discrete (0 or 1, or one of
Which vector is bigger? Is
- Compare norms
and . Many different vectors share a norm, and the norm forgets which class rose. - Lexicographic order: compare first coordinates, then second, and so on, like digits. It favours class 1 for no reason.
- Coordinatewise order:
when for every . On the simplex this almost never holds: the coordinates add to 1, so if one rises, another must fall.
One-vs-rest isotonic regression fits each class separately with ordinary isotonic regression. It ignores the relationships among the classes and needs an extra normalization step afterwards to make the outputs add to 1.
Explore
Check your understanding
Two probability vectors
- Yes, often.Add up the inequalities.
- No: summing would give
with some strict inequality, which is impossible.
Why would demanding that every output coordinate increase with every input coordinate be inappropriate for calibrating a
- Raising one class's score should raise that class's probability and lower the others; the softmax itself does this.
- Because calibration maps are never increasing.They should be increasing in a suitable vector sense.
Convexity and subgradients
A convex function lies above each of its tangent lines. Where there is no tangent, at a corner, there are many lines that stay below the graph, and their slopes together form the subdifferential: a set of vectors, not a single vector.
The idea
Why convexity matters. Gradient descent is the workhorse for minimizing functions; it is how neural networks are trained. For a convex function it provably converges to the minimum (see the convexity module on the Gradient Descent page). For nonconvex functions there is no such guarantee, and minimization is hard in general. So convexity is the standard assumption that makes optimization tractable, and it will also turn out to be the key to the vector-valued order.
Check what kind of object it is. The gradient
- If
is convex and differentiable at , then : the tangent is the only supporting line. - For
on : for , for , and the whole interval at the corner , where every line through the origin with slope between and stays below . Infinitely many subgradients. - It can be empty. For
on (and for ), no line through the origin stays below the graph near 0, because the graph drops vertically. This only happens at the edge of where is finite: a convex function that is finite on all of has a nonempty subdifferential everywhere. is always a convex set: if satisfy (1), so does , by adding times one inequality to times the other.
Explore
Worked example
Find
for . is differentiable there, so the subdifferential is the derivative: for and for .Find
.We need
for all . For this says ; for it says , i.e. . So : every line through the origin with slope between 0 and 1.Is
a subgradient at 0? Why does that matter?Yes; the subdifferential is convex, so averages of subgradients are subgradients. At a corner,
can “split” its slope among many values at once. The notes point out that this is the mechanism behind the paper's Theorem 2: one input can be sent to a whole set of outputs, a fact that will matter for optimal transport, where mass at one point may be split among several destinations.
Check your understanding
, a set with one element. , a vector.The subdifferential is always a set; here it has one element.- Empty: subgradients are only for nondifferentiable points.They are defined everywhere; at smooth points they agree with the gradient.
Which of these is an element of
At the only subgradient is 1. At the only subgradient is .
Practice
Half a squared normA smooth example in ℝᵈ
For
Outline
is differentiable with , so .Why?
, so ; and is convex.- Inequality (1) reads
.Why?
Substitute
. - It holds because the difference is
.Why?
.
A maximum of linesSubdifferentials of piecewise-linear functions
Let
Outline
- Every active slope is a subgradient.
Why?
If line
attains the max at , then for all . - So is everything in between.
Why?
The subdifferential is convex.
- Nothing outside the interval works.
Why?
Just to the right of
, follows the active line with the largest slope , so would put the line above the graph there; likewise a slope below the smallest active one fails just to the left.
Try “three pieces” in the figure: at each corner the fan of supporting lines spans exactly the two slopes that meet there.
From monotone to cyclically monotone
Vectors have no order, but “increasing” can still be defined: replace the product in
The idea
Monotone, without an order. On
Show why the product captures “increasing”
If
Show the computation
So (2) holds with equality for every pair. It is not a gradient: if
For
Taking
Show why the first part holds
Take pairs
Add these
which is (3). (The last step only renames
So: cyclically monotone ⇔ (part of) the subgradient of a convex function. For a smooth convex
Explore
Worked example
The map in the figure,
When is
monotone, in the sense of (2)? , since . So is monotone exactly when ; the twist is invisible to every pair.For a cycle
, compute the gap .It splits into a stretch part and a twist part:
where
. The second sum is twice the signed area enclosed by the cycle: positive counterclockwise, negative clockwise.Show that any twist
breaks cyclic monotonicity, however large is.Run a regular
-gon of radius in the direction that makes negative. Its area tends to , while . So for large the twist term wins and the gap is negative. Longer cycles catch smaller twists. Only , survives: , the gradient of a convex function, as the theorem says.
Check your understanding
Inequality (3) with
- Ordinary monotonicity,
. - Always true, for any relation.Try the pairs
and .
To guarantee that fitted pairs
- Check inequality (3) for every cycle of the data.There are far too many cycles: every length, every ordering.
- Construct them so that each
is a subgradient of one convex function at . - Make each coordinate of
increase in each coordinate of .That is coordinatewise monotonicity, neither necessary nor sufficient.
In the figure, set the twist to
- That
is cyclically monotone.One cycle passing doesn't mean every cycle passes. Try the regular m-gon with more points. - Nothing conclusive: a longer cycle (a regular m-gon with m large enough) will make the gap negative.
Practice
Symmetric matricesWhich linear maps are cyclically monotone?
Show that
Outline
for .Why?
when is symmetric. is convex, so is cyclically monotone.Why?
Its Hessian is
. Then apply the theorem: the gradient of a convex function has a cyclically monotone graph.- No:
is monotone iff , which allows an antisymmetric part.Why?
. The rotation has : monotone, not cyclically monotone.
For linear maps: monotone means the symmetric part is positive semidefinite; cyclically monotone means the map is symmetric and positive semidefinite.
Cyclic on the lineWhy vectors were the hard case
On
Outline
is convex.Why?
Its slope
never decreases. A function whose difference quotients increase is convex. for every .Why?
in both cases and , because is nondecreasing.- So the graph of
is cyclically monotone.Why?
It lies in
, which is cyclically monotone by the theorem.