- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper determines the minimax regret of online isotonic regression on every finite poset P, up to absolute constants. For squared loss the rate is R*_T(P) = Θ(min{T, inf_K [H_P(K) + T/K²]}), where H_P(K) is the logarithm of Stanley's order polynomial. The same formula holds for log loss and for bounded exp-concave, smooth, strongly proper losses. Pinball loss gets a separate rate, governed by H_P(1).
Upper bound: exponential weights over isotonic functions on a grid, already known since Kotłowski et al. (2016). Lower bound (the main new content): a noisy search for a hidden order ideal, driven by Linial–Saks central elements. Efficient learner: perturbs a chain encoding of the ideals with low-dimensional Gumbel noise and samples maximizers by one minimum cut each. A new inequality ("Gibbs domination") shows this loses only a constant factor relative to exponential weights. Horizon-free version: aggregates the dyadic resolutions and runs in polynomial time.
The results answer the open problems of Kotłowski–Koolen–Malek (2016, 2017) and Wang (2026).
Critical strengths
Strong, clean result: a tight characterization on every finite poset with absolute constants, identifying the order polynomial as the right complexity measure.
The lower bound is elegant. Combining Linial–Saks central elements, block-wise noisy queries, and strong properness gives a general argument that is not specific to product orders.
Gibbs domination is a genuinely new tool. It makes oracle-efficient, perturbation-based learning match exponential weights up to a constant for exp-concave losses, which may be useful beyond isotonic regression.
The scope is broad: log loss, general proper losses, pinball loss, high-probability horizon-free guarantees, an extension to difference-constraint classes, and a finite-precision complexity analysis.
Proof sketches in the main text are informative. The appendix appears complete.
Critical weaknesses
Constant gap. The constants are absolute but far apart. The lower bound carries λ/2048 ≈ 9·10⁻⁵, and the efficient learner loses a factor of about 11.3. "Up to absolute constants" is correct, but practically loose.
Upper bound is not new. The upper bound for exponential weights is classical. The novelty lies in the lower bound and the efficient learner, and the abstract and introduction could separate these more clearly.
Per-round cost grows with t. At round t the learner runs polylog many minimum cuts on networks with O(nt) vertices and O(n²t) arcs. It is polynomial but heavy. There is no runtime discussion and no experiment, for example on multi-signal calibration, which the paper itself uses as motivation and which matters for an ICLR audience.
Protocol mismatch with the original problem. The lower bounds use repeated queries, while Kotłowski et al. posed the problem in a single-pass, fixed-design protocol. In that protocol the chain still has a log^{2/3} T gap between bounds. The claim to resolve "all of these open problems" should be qualified accordingly.
Dense and COLT-style presentation. The paper is 60 pages, and the main text is very compressed. Venue fit for ICLR is acceptable but not ideal.
Questions for authors
Does the lower bound, and hence Θ(r_P(T)), hold in the single-pass protocol of Kotłowski et al. (2016)?
Is κ = 4 in Gibbs domination an artifact of the analysis, and can it be improved toward 1 for K > 1?
What are the practical wall-clock costs, and is there a cheaper approximate variant, for example sampling with a fixed number of cuts or reusing cuts across rounds?
How the regret looks with the absolute loss l(p,y)=|p-y|.
6 comments
Response to Reviewer LfUi (2/4)
Running time and experiments. The growth of the per-round computation with comes from the horizon-free learner of Theorem 4, which at round uses all the resolutions up to . Algorithm 1 works at one fixed resolution . In every round it predicts at the queried point with the average of sampled predictions, each computed by one minimum cut on a network with vertices, so for fixed and the number and the size of the minimum cuts per round do not grow with . The algorithm has two modes. Pair mode uses a small learning rate, and with it already has a regret bound of order in expectation (Theorem 7). The revised Section 4.2 now says that two minimum cuts per round suffice. Mean mode uses a larger learning rate, and by the new Remark 5 its expected regret under squared loss is at most for every fixed , which for is at most a constant times the bound of exponential weights.
Table 2 in Appendix J gives the wall-clock time of one sampled prediction on the product orders with 64 to 4096 points at resolutions 4 to 32, measured on one core with the maximum-flow routine of Boykov and Kolmogorov. A round takes about times as long, and is between 2 and 25 in our regret experiments. The time of a sampled prediction changes during a run, so the table gives it at the start and after rounds. At the start, before the learner has seen any data, this time lies between 0.08 milliseconds on the smallest instance and 1.5 seconds on the largest. After rounds it is smaller on every instance and at most 34 milliseconds.
As for reusing cuts across rounds, the noise can be kept from one round to the next when the sequence is fixed in advance, and each minimum cut can then be computed by a warm start from the flow of the previous round. With a fixed sequence the scores of the learner are deterministic, because their update does not depend on the predictions. If independent copies of the noise are drawn once and kept, they therefore still give independent sampled predictions with the correct law in every round, and the bounds in expectation of both modes remain valid. If, in addition, the arcs that encode the order are given one fixed large capacity, the networks of consecutive rounds differ only in the weights of the vertices that belong to the queried point, and this makes the warm start possible.
Appendix J also compares the regret of Algorithm 1 with that of follow the leader on chains, ordinal sums of antichains and product orders , on which a calibration map with two signals of values each is defined. Follow the leader is fast and does well on benign data. Its regret depends on the order of arrival, however, and can be linear even on a chain (Kotłowski et al., 2016), whereas the guarantee of Algorithm 1 holds for every sequence. The experiments show how far the two can differ when the order is unfavorable. In our sequences an isotonic function fits the labels without error, but the points arrive in an order in which every value at the queried point is consistent with the earlier labels. Follow the leader then predicts in every round and has regret on points. The guarantee of Algorithm 1 is of the order of , which grows like up to logarithmic factors on a chain and like on , so the ratio of the two regrets should grow with the size of the problem, and Figure 2 shows that it does. In mean mode with , follow the leader has about 4 times the regret of Algorithm 1 on the smallest instances and between 9 and 18 times on the largest, and in pair mode with between 2 and 6 times.
Constants. In Theorem 1 the small constant is that of the lower bound, , which results from the block argument, with from the constant of Linial and Saks. The upper bound of the theorem holds with the constant . For the learner, the factor between its regret bound and that of exponential weights is , the product of two constants, from Gibbs domination and from the bound on the potential before the first round. In the experiments the learner performs considerably better than this guarantee. On the sequences of rounds described above, its regret in mean mode with lies between and times , against a guarantee of .
Response to Reviewer LfUi (3/4)
The constant of Gibbs domination. The value is in part an artifact of the analysis. With a minimum chain partition it can be lowered to at the resolutions and to for . For the learner, the factor accordingly becomes at and for when the learning rate is raised in the same proportion. The constant cannot be lowered below , however, since at every resolution there is a poset with a minimum chain partition for which no constant below makes the inequality of Theorem 3 hold for all scores. At the value is therefore the best possible.
The value can be reached with a different partition. If the cells are partitioned into the columns, one for each point , the inequality holds with at every resolution (Lemma 18). The regret bound of the learner is proportional to , however, where is the potential before the first round. On a chain of points the partition into columns has at least of order , whereas a minimum chain partition keeps , which is of order at a fixed resolution. With the partition into columns the regret bound is therefore of larger order in , and the learner uses a minimum chain partition for this reason.
With a minimum chain partition, the value arises in the proof of Theorem 3 as a product of two factors . The first comes from Lemma 16, because the level at a point is decided by two cells, which may lie in different chains, and the second from the inequality in the proof of Lemma 17. With a different argument both factors can be avoided, and the number of chains that are needed to distinguish the levels at a point takes the place of the constant . Since Theorem 3 remains valid, the inequality holds at a point with
in place of , where is the number of chains of the partition that contain a cell of , and is for and for . To prove this, we condition on the noise of all chains but one. Given this noise, the prefix length of the maximizer in the remaining chain is an exact sample from exponential weights, so for the pairs of ideals that differ in this prefix length the curvature bound of Lemma 17 holds with the factor . Two ideals with different levels at differ in the prefix length of a chain through a cell of , and when these chains are chosen by a binary search over the levels, the comparisons of any one level with the others use at most of them. The complete proof is in the fourth part of this reply.
We show by an example that the constant cannot be smaller than . Let be the chain and . The cells of level form a chain, namely in the order of Definition 2, in which the points appear in reverse, and the cells of level form a second chain. The two chains form a minimum chain partition, because the cells and are incomparable. Let the scores of the levels and at and of the levels and at tend to , so that in the limit only the three functions with and remain, and give the level at the score and every other level the score . The ideal of the function with has prefix length in the first chain if and otherwise, and prefix length in the second chain if and otherwise. With the noise of the prefix of length in the -th chain, the perturbed scores of the three functions are therefore , and , and the maximizer has the level at exactly when and . These two differences are independent logistic variables, so this event has probability with , and . When is raised by , the potential grows by , and the right side of Theorem 3 is . The inequality therefore requires
which tends to as . For the same computation applies when is a chain of points and the partition consists of the sets of cells of equal level, if the scores leave only the functions that are at , at most at and at all later points.
Response to Reviewer LfUi (1/4)
Thank you for your careful and thorough review and for your questions on the scope of the results, the computation and the constants. In response, we have qualified the claim of the abstract and added experiments and a discussion of the running time, with the code in the supplementary material. We have also substantially rewritten the exposition of the main text, in particular Sections 1.1 and 4, to make it clearer and easier to follow. The theorems are unchanged in content, and the changes are marked in red in the revised paper.
You describe the main text as very compressed. When we reread it as a first-time reader would, we found that Section 1.1 used terms whose definitions came only in Section 2, and that Sections 3 and 4 treated several topics in single long paragraphs. Section 1.1 now explains its terms where it uses them, the long paragraphs are divided, the proof sketch of Theorem 3 proceeds in separate steps, and Algorithm 1 appears in the main text (page 9).
Upper bound and new results. The new results are the lower bound and the polynomial-time learner. With the lower bound, rP(T) is the minimax rate on every finite poset, and on the product orders, where Wang (2026) had determined the rate under squared loss up to constants that depend on the dimension, the constants become absolute. The learner attains this rate in polynomial time, and its analysis rests on a new inequality, Gibbs domination. The upper bound of Theorem 1, by contrast, was known. Exponential weights over the grid-valued isotonic functions is the algorithm of Kotłowski et al. (2016), and Wang (2026) bounded its regret on every finite poset. The abstract states that exponential weights attains the upper bounds and introduces our learner as the efficient alternative, and the revised introduction and Section 3 now name Wang (2026) as the source of the regret bound.
Single-pass protocol. You point out that the lower bounds use repeated queries, while Kotłowski et al. (2016) posed the problem in a single-pass protocol, and that the claim of the abstract should be qualified accordingly. The abstract now reads “In the natural protocol, in which points may recur, we resolve all of these open problems on every finite poset P”, and the introduction adds that this is the protocol of Wang (2026), whereas in that of Kotłowski et al. (2016) each point appears once. We call this protocol natural because in most applications there is no guarantee that each point is queried only once. In calibration, for example, the same bin of scores is seen many times.
In the single-pass protocol itself, the upper bounds and the guarantee of the learner remain valid, because they hold for every sequence. The efficient algorithm for partial orders that Kotłowski et al. (2016) asked for is therefore available in their protocol too, with the regret bound of exponential weights up to a constant factor. A matching lower bound, however, is not established there, because in the proof of the lower bound one point is queried throughout a block of 32K2 rounds.
Absolute loss. The absolute loss is twice the pinball loss at τ=1/2, so Theorem 10 in Appendix H applies, and the minimax regret under absolute loss on every finite poset is
Θ(min{T,THP(1)})
with absolute constants, where HP(1) is the logarithm of the number of binary isotonic functions on P. On a chain of n points this is of order min{T,Tlog(n+1)}. A polynomial-time learner attains this rate on every finite poset (Theorem 11). The revised Section 1.1 now names the absolute loss next to the pinball loss.