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.

Read and checkBao–Eshraghi–Wang (2026), §1

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

Regression. Given data (z1,y1),…,(zn,yn), find a function f with f(zi)≈yi. A new input z is then predicted as f(z). Whether that prediction is any good is the whole question of machine learning; regression is how the prediction is made.
Parametric regression. Choose a family of functions described by a few numbers, the parameters, and fit those. If the data look quadratic you might take f(z)=az2+bz+c and fit (a,b,c); a neural network is the same idea with millions of parameters (see the Neural Networks page). The usual fit minimizes the squared error ∑i(yi−f(zi))2.
Nonparametric regression. Skip the formula and fit the values directly: choose numbers y^1,…,y^n, one fitted value per data point, to minimize ∑i(yi−y^i)2. No model of the form “az2+bz+c” is assumed.

Why that needs a constraint. With no restriction on the y^i, the minimum is trivial: take y^i=yi and the error is 0. That fits the noise exactly and says nothing about new inputs. What makes nonparametric regression meaningful is a shape constraint: a rule the fitted values must obey. Isotonic regression uses the simplest one, monotonicity: larger inputs never receive smaller fitted values.

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 E[Y∣X=x]=g(⟨w,x⟩) with an unknown increasing link g, the link is fitted by isotonic regression.

Worked example

Data (1,1.0), (2,4.5), (3,8.8), roughly z2.

  1. Fit f(z)=az2 (one parameter) by least squares.

    Minimize ∑i(yi−azi2)2: setting the derivative in a to 0 gives a=∑iyizi2/∑izi4=(1+18+79.2)/(1+16+81)=98.2/98≈1.002. The fitted values are 1.00, 4.01, 9.02, and the model predicts f(2.5)≈6.26.

  2. Now fit the values directly, with no constraint.

    y^=(1.0,4.5,8.8), error 0. The data are already increasing, so the isotonic fit is the same.

  3. The nonparametric fit gives values only at z=1,2,3. How would you predict at z=2.5?

    Any increasing function through the fitted points is consistent with the constraint; a common choice is to interpolate linearly (6.65) 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 ∑i(yi−y^i)2 over y^1,…,y^n with no constraint. The minimum is:

  1. 0, at y^i=yi.
  2. The variance of the yi, at y^i=y¯.That is the best constant fit; here every y^i is free.
Each term can be made 0 separately. The problem only becomes interesting once a constraint ties the y^i together.

Why is isotonic regression called nonparametric?

  1. Because it has no constraints.It has a constraint: monotonicity.
  2. Because it fits the values y^i directly instead of the parameters of a formula.
  3. Because it ignores the inputs zi.The inputs decide the order the fitted values must respect.
The unknowns are the n fitted values themselves; the only assumption is the shape (monotone), not a formula with a fixed number of parameters.
InteractiveBao–Eshraghi–Wang (2026), eq. (IR)

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

Isotonic regression. With the inputs sorted, z1<z2<⋯<zn, solve
miny^1,…,y^n ∑i=1n(yi−y^i)2subject toy^1≤y^2≤⋯≤y^n.
The fitted values have no z in them: the inputs matter only through their order. (Isotonic means nondecreasing; ties are allowed, so the fit may be flat.)

Without sorting. The same constraint can be written for every pair at once:

(zi−zj)(y^i−y^j)≥0for all i,j.
A product of two numbers is ≥0 when they have the same sign, so this says: whenever zi>zj, also y^i≥y^j. This is the form that generalizes to vectors later (module 5).

Pool adjacent violators (PAVA). Start with y^=y. While some neighbour pair is out of order, y^i>y^i+1, merge the two blocks containing them into one block and give every point in it the block's average. When no violations remain, the result is the isotonic fit.

Why the average? If two observations must share one fitted value a, the best a minimizes g(a)=(yi−a)2+(yi+1−a)2. Take the derivative and set it to 0:

g′(a)=−2(yi−a)−2(yi+1−a)=0 ⟹ yi+yi+1−2a=0 ⟹ a=yi+yi+12.

(The minus signs come from the chain rule: dda(y−a)2=−2(y−a).) The same computation for a block of k points gives the block mean. So pooling is least squares inside the order constraint, not an arbitrary smoothing step.

Show why a violating pair must be pooled

Suppose yi>yi+1 (the data are out of order there) and take any feasible fit with a=y^i<b=y^i+1. Replace both by their midpoint m=a+b2. The order is kept, since y^i−1≤a≤m≤b≤y^i+2. The error drops by

D=(yi−a)2+(yi+1−b)2−(yi−m)2−(yi+1−m)2=12(b−a)2+(b−a)(yi−yi+1) > 0.

(Expand: the quadratic terms give a2+b2−2m2=12(a−b)2, and the linear terms give (b−a)(yi−yi+1).) So a fit that separates the pair can always be improved, and the best fit has y^i=y^i+1. Given that, the two points act as one point with the average value and weight 2, and the same argument applies to the merged problem. That is why PAVA's answer is optimal.

Explore

Data
Show
Drag any point up or down. data yi isotonic fit y^i; each flat run is a pooled block, at the mean of its points. In step-by-step mode, the red pair is the next violation PAVA merges.

Worked example

Inputs z=(1,2,3), outputs y=(0.8, 0.2, 0.6).

  1. Which pair violates the order?

    0.8>0.2: the first two. (0.2≤0.6 is fine.)

  2. Pool them. What is the fit, and is it isotonic?

    Both become (0.8+0.2)/2=0.5, giving y^=(0.5,0.5,0.6). Now 0.5≤0.5≤0.6: no violations, so PAVA stops.

  3. Compare its error with another isotonic candidate, (0.2,0.2,0.6).

    Pooled: 0.32+0.32+0=0.18. Candidate: 0.62+0+0=0.36. Pooling splits the disagreement evenly, which costs less than putting all of it on one point: 2⋅0.32<0.62.

  4. Change the data to y=(0.8,0.2,0.4). Run PAVA.

    Pool the first two to 0.5; now 0.5>0.4 is a new violation, so pool all three: y^=(0.46―,0.46―,0.46―), the mean 1.4/3. One merge can create the next one, which is why PAVA loops until nothing is out of order.

Check your understanding

If the data y1≤⋯≤yn are already in order, the isotonic fit is:

  1. The data themselves, with error 0.
  2. A smoothed version of the data.Isotonic regression only changes values that break the order.
y^=y is feasible and has error 0, so nothing can beat it. Isotonic regression is not a smoother; it only intervenes where the data go down.

The data are strictly decreasing, y1>y2>⋯>yn. The isotonic fit is:

  1. The data reversed.The fitted values are attached to the inputs; you can't move them to other inputs.
  2. The constant y¯ at every point.
Every neighbour pair violates the order, so PAVA ends with one block, at the overall mean. The best nondecreasing fit to decreasing data is flat. Try “decreasing” in the figure.

Practice

Weighted poolingThe mean of a block

A block of k points must share one value a. Show that the best a is the block mean. If two blocks with means m1,m2 and sizes k1,k2 merge, what is the new value?

Outline
  1. The best a minimizes ∑i∈B(yi−a)2, whose derivative is −2∑i∈B(yi−a).
    Why?

    Differentiate each term by the chain rule.

  2. Setting it to 0 gives a=1k∑i∈Byi.
    Why?

    ∑iyi−ka=0. The function is a parabola opening upward, so this critical point is the minimum.

  3. Merged blocks get k1m1+k2m2k1+k2.
    Why?

    The mean of the union: the total k1m1+k2m2 divided by the count. So PAVA only needs each block's size and mean, not its points.

Running PAVAFive points

Run PAVA on y=(1,3,2,2,5) and compute the error of the fit.

Outline
  1. The only violation is 3>2; pool to get (1,2.5,2.5,2,5).
    Why?

    1≤3, 3>2, 2≤2, 2≤5.

  2. Now 2.5>2: pool the block with the next point, giving (1,73,73,73,5).
    Why?

    The merged block is {3,2,2}, mean 7/3.

  3. No violations remain; the error is 23.
    Why?

    (3−73)2+2(2−73)2=49+29=23.

InteractiveBao–Eshraghi–Wang (2026), §1

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 p=0.8 for “class 1”, because the other class automatically gets 1−p=0.2. With d classes (CS, math or physics major, say) the classifier reports a whole vector of probabilities,

p=(p1,…,pd)∈Δd−1,Δd−1={p∈Rd: pj≥0, ∑jpj=1},
the probability simplex. For d=3 it is a triangle, with one corner per class. Calibrating such a classifier means fitting a map from score vectors to probability vectors, and we would like that map to be “monotone”.

Aside: why classifiers output probabilities at all

The labels are discrete (0 or 1, or one of d classes), but the functions we fit, neural networks included, are continuous, and a continuous function can't jump cleanly between 0 and 1 wherever the labels do. So the model predicts a probability in between instead, and the predicted class is the most likely one (above 0.5, in the binary case). Logistic regression does this for two classes with p=1/(1+e−s) applied to a score s; with d classes the scores s∈Rd go through the softmax

softmax⁡(s)j=esj∑kesk,
which lands in the simplex. (See the softmax module for where this formula comes from.)

Which vector is bigger? Is p=(0.6,0.3,0.1) bigger or smaller than q=(0.4,0.5,0.1)? One class probability rose and another fell. Some candidate orders:

  • Compare norms |p| and |q|. 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: p≤q when pj≤qj for every j. 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.

The softmax is not coordinatewise monotone. Raising one score s1 raises p1 but lowers every other pj. The natural calibration map is “increasing” in some sense, but not in the coordinatewise sense. The paper replaces the order by a different, genuinely vector-valued condition, cyclic monotonicity, which the softmax does satisfy.

Explore

The three probabilities. The faint bars mark where they were before your last change: raise one score and watch the other two fall.
The same vector as a point in the simplex Δ2, a triangle with one corner per class. The trail shows where it has been.

Check your understanding

Two probability vectors p≠q in Δd−1. Can pj≤qj hold for every j?

  1. Yes, often.Add up the inequalities.
  2. No: summing would give 1≤1 with some strict inequality, which is impossible.
If pj≤qj for all j and p≠q, then ∑jpj<∑jqj, but both sums are 1. On the simplex, distinct vectors are never comparable coordinatewise.

Why would demanding that every output coordinate increase with every input coordinate be inappropriate for calibrating a d-class classifier?

  1. Raising one class's score should raise that class's probability and lower the others; the softmax itself does this.
  2. Because calibration maps are never increasing.They should be increasing in a suitable vector sense.
The probabilities compete for a total of 1. Any sensible map from scores to probabilities, the softmax first of all, fails coordinatewise monotonicity, so that constraint would rule out the very maps we want.
InteractiveRockafellar, Convex Analysis, §23

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.

Convex function. φ:Rd→R∪{+∞} is convex if φ(λx+(1−λ)y)≤λφ(x)+(1−λ)φ(y) for all x,y and λ∈[0,1]: the chord between two points of the graph lies above the graph. It is proper if it is not +∞ everywhere (and never −∞). If φ is differentiable, convexity is equivalent to lying above every tangent: φ(y)≥φ(x)+⟨∇φ(x),y−x⟩.
Subgradient and subdifferential. A vector g∈Rd is a subgradient of φ at x if
(1)φ(y) ≥ φ(x)+⟨g,y−x⟩for all y∈Rd.
The subdifferential ∂φ(x) is the set of all subgradients at x. In pictures, (1) says the line (or plane) through (x,φ(x)) with slope g stays below the graph everywhere.

Check what kind of object it is. The gradient ∇φ(x) is one vector. The subdifferential ∂φ(x) is a set of vectors. It is defined whether or not φ is differentiable at x, which is the point of it:

  • If φ is convex and differentiable at x, then ∂φ(x)={∇φ(x)}: the tangent is the only supporting line.
  • For φ(x)=|x| on R: ∂φ(x)={−1} for x<0, {1} for x>0, and the whole interval [−1,1] at the corner x=0, where every line through the origin with slope between −1 and 1 stays below |x|. Infinitely many subgradients.
  • It can be empty. For φ(x)=−x on [0,∞) (and +∞ for x<0), 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 Rd has a nonempty subdifferential everywhere.
  • ∂φ(x) is always a convex set: if g1,g2 satisfy (1), so does λg1+(1−λ)g2, by adding λ times one inequality to 1−λ times the other.
Subgradient graph. Collect every point together with every one of its subgradients:
graph⁡∂φ={(x,g)∈Rd×Rd: g∈∂φ(x)}.
For |x| this is the horizontal ray at height −1 over x<0, the vertical segment from (0,−1) to (0,1), and the ray at height 1 over x>0: a “staircase” in the plane. It is not a list of pairs of subgradients; each pair is (a point, a subgradient at that point).

Explore

Function φ
Drag the point along the graph. supporting lines at x: one where φ is smooth, a whole fan at a corner.
The subgradient graph: horizontal axis x, vertical axis the slopes g∈∂φ(x). current ∂φ(x). It never goes down as x moves right.

Worked example

φ(t)=max{0,t} on R.

  1. Find ∂φ(t) for t≠0.

    φ is differentiable there, so the subdifferential is the derivative: {0} for t<0 and {1} for t>0.

  2. Find ∂φ(0).

    We need max{0,y}≥gy for all y. For y>0 this says g≤1; for y<0 it says 0≥gy, i.e. g≥0. So ∂φ(0)=[0,1]: every line through the origin with slope between 0 and 1.

  3. Is 12⋅0+12⋅1=12 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

φ is convex and differentiable at x. Then ∂φ(x) is:

  1. {∇φ(x)}, a set with one element.
  2. ∇φ(x), a vector.The subdifferential is always a set; here it has one element.
  3. Empty: subgradients are only for nondifferentiable points.They are defined everywhere; at smooth points they agree with the gradient.
The tangent is the only line that touches the graph at x and stays below it. So the set of subgradients contains exactly the gradient.

Which of these is an element of graph⁡∂φ for φ(x)=|x|?

  1. (0, 0.3)
  2. (2, 0.3)At x=2 the only subgradient is 1.
  3. (−1, 1)At x=−1 the only subgradient is −1.
A pair (x,g) is in the graph when g∈∂φ(x). Only at the corner x=0 is 0.3 allowed, since ∂|⋅|(0)=[−1,1].

Practice

Half a squared normA smooth example in ℝᵈ

For φ(z)=12|z|2 on Rd, find ∂φ(z) and check inequality (1) directly.

Outline
  1. φ is differentiable with ∇φ(z)=z, so ∂φ(z)={z}.
    Why?

    φ(z)=12∑jzj2, so ∂φ/∂zj=zj; and φ is convex.

  2. Inequality (1) reads 12|y|2≥12|z|2+⟨z,y−z⟩.
    Why?

    Substitute g=z.

  3. It holds because the difference is 12|y−z|2≥0.
    Why?

    12|y|2−12|z|2−⟨z,y⟩+|z|2=12(|y|2−2⟨z,y⟩+|z|2).

A maximum of linesSubdifferentials of piecewise-linear functions

Let φ(x)=maxk(akx+bk), a maximum of finitely many lines. Show that ∂φ(x) is the interval between the smallest and largest slopes ak of the lines that attain the maximum at x.

Outline
  1. Every active slope is a subgradient.
    Why?

    If line k attains the max at x, then φ(y)≥aky+bk=φ(x)+ak(y−x) for all y.

  2. So is everything in between.
    Why?

    The subdifferential is convex.

  3. Nothing outside the interval works.
    Why?

    Just to the right of x, φ follows the active line with the largest slope a+, so g>a+ 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.

InteractiveRockafellar, Convex Analysis, §24; Bao–Eshraghi–Wang (2026), §2

From monotone to cyclically monotone

Vectors have no order, but “increasing” can still be defined: replace the product in (x−y)(T(x)−T(y))≥0 by an inner product. That is not quite enough to single out gradients of convex functions. Requiring the inequality around every cycle of points is, and that is the constraint the paper puts on its regression function.

The idea

Monotone, without an order. On R, a function T is nondecreasing exactly when (x−y)(T(x)−T(y))≥0 for all x,y.

Show why the product captures “increasing”

If x>y, then x−y>0, and an increasing T has T(x)≥T(y), so T(x)−T(y)≥0: positive times nonnegative. If x<y, both factors are ≤0: negative times nonpositive. Either way the product is ≥0. Conversely, if the product is ≥0 and x>y, the second factor can't be negative, so T(x)≥T(y). The product says “the output moves in the same direction as the input” without ever saying which number is bigger.

Monotone map on Rd. T:Rd→Rd (it must output a vector of the same dimension, for the inner product to make sense) is monotone if
(2)⟨T(x)−T(y), x−y⟩ ≥ 0for all x,y.
The product of numbers has become an inner product of vectors: the change in output never points against the change in input.
A monotone map that is not a gradient. The 90∘ rotation T(x1,x2)=(−x2,x1) satisfies (2) with equality, ⟨T(x)−T(y),x−y⟩=0, because T moves every vector perpendicular to itself. Yet T is not the gradient of any convex function, since it just spins points around the origin.
Show the computation

T is linear, so T(x)−T(y)=T(x−y). Write v=x−y=(v1,v2). Then T(v)=(−v2,v1) and

⟨T(v),v⟩=(−v2)v1+v1v2=0.

So (2) holds with equality for every pair. It is not a gradient: if T=∇φ, the mixed partials would agree, ∂2T1=∂1T2, but ∂2T1=−1 and ∂1T2=1.

Cyclically monotone relation (Rockafellar 1966). A set Γ⊆Rd×Rd of pairs is cyclically monotone if for every m≥2 and every choice of pairs (z1,u1),…,(zm,um)∈Γ, with um+1=u1,
(3)∑i=1m⟨zi,ui⟩ ≥ ∑i=1m⟨zi,ui+1⟩.
A map is cyclically monotone when its graph {(x,T(x))} is. Γ may be infinite; the condition is checked on every finite list taken from it. In words: matching each zi with its own ui scores at least as high as shifting all the partners one step around the cycle.

For m=2 it is ordinary monotonicity. With two pairs, (3) reads ⟨z1,u1⟩+⟨z2,u2⟩≥⟨z1,u2⟩+⟨z2,u1⟩. Move everything to the left:

⟨z1,u1−u2⟩+⟨z2,u2−u1⟩=⟨z1−z2, u1−u2⟩ ≥ 0.

Taking zi=xi and ui=T(xi) gives exactly (2). Cycles of length 3 and more add conditions that pairs can't see. For the rotation, take the three points z1=(0,0), z2=(0,1), z3=(1,0) with ui=T(zi), that is u1=(0,0), u2=(−1,0), u3=(0,1). The left side of (3) is 0+0+0=0, but the right side is ⟨z1,u2⟩+⟨z2,u3⟩+⟨z3,u1⟩=0+1+0=1. So (3) fails: the rotation is monotone but not cyclically monotone.

Convex functions give cyclically monotone sets (Rockafellar, Thm. 24.8). For every proper convex φ, the subgradient graph graph⁡∂φ is cyclically monotone. Conversely, every cyclically monotone set is contained in the subgradient graph of some proper, lower semicontinuous convex function.
Show why the first part holds

Take pairs (zi,ui) with ui∈∂φ(zi), and zm+1=z1, um+1=u1. The subgradient inequality (1) at the point zi+1, tested at the previous point y=zi, gives

φ(zi) ≥ φ(zi+1)+⟨ui+1, zi−zi+1⟩,i=1,…,m.

Add these m inequalities. The φ terms cancel around the cycle (each φ(zi) appears once on each side), leaving

0 ≥ ∑i=1m⟨zi,ui+1⟩−∑i=1m⟨zi+1,ui+1⟩=∑i=1m⟨zi,ui+1⟩−∑i=1m⟨zi,ui⟩,

which is (3). (The last step only renames i+1 as i, which is allowed because the indices go around a cycle.)

So: cyclically monotone ⇔ (part of) the subgradient of a convex function. For a smooth convex φ this says the gradient map ∇φ is cyclically monotone, which is the precise meaning of the paper's slogan “a cyclically monotone function is the gradient of some convex potential”. The softmax is one: it is the gradient of the convex function log⁡∑kesk, so it is cyclically monotone although it is not coordinatewise monotone (module 3).

Key idea for the paper. Checking (3) directly means checking every cycle of every length, which is hopeless. Instead, build the fitted relation so that it is automatically the subgradient graph of a convex function. The paper's regression problem (CMIR, cyclically monotone isotonic regression) minimizes ∑i|yi−y^i|2 over fitted vectors y^i such that the pairs (zi,y^i) are cyclically monotone. The construction it uses comes from optimal transport, where Kantorovich's optimal couplings are always cyclically monotone and Brenier's theorem writes the optimal map as ∇ψ with ψ convex. That is the next meeting's topic.

Explore

Cycle
The linear map T(z)=Mz with M=(a−bba): stretch by a, plus a twist b (a multiple of the rotation). points zi (drag them in triangle mode) arrows to ui=T(zi), scaled down to fit. The stats compare the two sides of (3) for the cycle in both directions.

Worked example

The map in the figure, T(z)=Mz with M=aI+bJ, where J is the 90∘ rotation.

  1. When is T monotone, in the sense of (2)?

    ⟨Mv,v⟩=a|v|2+b⟨Jv,v⟩=a|v|2, since Jv⟂v. So T is monotone exactly when a≥0; the twist b is invisible to every pair.

  2. For a cycle z1,…,zm, compute the gap ∑i⟨zi,ui⟩−∑i⟨zi,ui+1⟩.

    It splits into a stretch part and a twist part:

    gap=a2∑i=1m|zi−zi+1|2+b∑i=1m(zi×zi+1),

    where x×y=x1y2−x2y1. The second sum is twice the signed area enclosed by the cycle: positive counterclockwise, negative clockwise.

  3. Show that any twist b≠0 breaks cyclic monotonicity, however large a is.

    Run a regular m-gon of radius R in the direction that makes b⋅area negative. Its area tends to πR2, while ∑|zi−zi+1|2=m⋅(2Rsin⁡πm)2≈4π2R2/m→0. So for m large the twist term wins and the gap is negative. Longer cycles catch smaller twists. Only b=0, a≥0 survives: T=aI=∇(a2|z|2), the gradient of a convex function, as the theorem says.

Check your understanding

Inequality (3) with m=2 is:

  1. Ordinary monotonicity, ⟨z1−z2,u1−u2⟩≥0.
  2. Always true, for any relation.Try the pairs ((1,0),(−1,0)) and ((0,0),(0,0)).
Move all four terms to one side and group them: ⟨z1,u1−u2⟩−⟨z2,u1−u2⟩. Cyclic monotonicity contains monotonicity as its m=2 case and adds more conditions for longer cycles.

To guarantee that fitted pairs (zi,y^i) are cyclically monotone, the most practical route is to:

  1. Check inequality (3) for every cycle of the data.There are far too many cycles: every length, every ordering.
  2. Construct them so that each y^i is a subgradient of one convex function at zi.
  3. Make each coordinate of y^ increase in each coordinate of z.That is coordinatewise monotonicity, neither necessary nor sufficient.
Subgradient graphs of convex functions are automatically cyclically monotone, and by Rockafellar's theorem every cyclically monotone set arises this way. The paper gets such a construction from optimal transport.

In the figure, set the twist to b=0.4 with stretch a=1. For an equilateral triangle the gap stays positive in both directions. What does that show?

  1. That T is cyclically monotone.One cycle passing doesn't mean every cycle passes. Try the regular m-gon with more points.
  2. Nothing conclusive: a longer cycle (a regular m-gon with m large enough) will make the gap negative.
The stretch term shrinks like 1/m for a polygon of fixed size while the area term doesn't, so some cycle always exposes the twist. Cyclic monotonicity is a condition on all cycles at once.

Practice

Symmetric matricesWhich linear maps are cyclically monotone?

Show that T(z)=Az with A symmetric positive semidefinite is cyclically monotone. Is every monotone linear map of this form?

Outline
  1. Az=∇φ(z) for φ(z)=12z⊤Az.
    Why?

    ∇(12z⊤Az)=12(A+A⊤)z=Az when A is symmetric.

  2. φ is convex, so T is cyclically monotone.
    Why?

    Its Hessian is A⪰0. Then apply the theorem: the gradient of a convex function has a cyclically monotone graph.

  3. No: T(z)=Mz is monotone iff M+M⊤⪰0, which allows an antisymmetric part.
    Why?

    ⟨Mv,v⟩=12v⊤(M+M⊤)v. The rotation J has J+J⊤=0: 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 R, show that every nondecreasing T is cyclically monotone. (So in one dimension, monotone and cyclically monotone agree, and ordinary isotonic regression is already CMIR.)

Outline
  1. φ(x)=∫0xT(s)ds is convex.
    Why?

    Its slope T never decreases. A function whose difference quotients increase is convex.

  2. T(x)∈∂φ(x) for every x.
    Why?

    φ(y)−φ(x)=∫xyT(s)ds≥T(x)(y−x) in both cases y>x and y<x, because T is nondecreasing.

  3. So the graph of T is cyclically monotone.
    Why?

    It lies in graph⁡∂φ, which is cyclically monotone by the theorem.