acceptodds
Under review as a conference paper at ICLR 2027

The Minimax Rate of Online Isotonic Regression

12 views

Abstract

Kotłowski, Koolen and Malek posed as an open problem, at COLT 2016 and again at NeurIPS 2017, the design of efficient algorithms for online isotonic regression on arbitrary partial orders. Wang (NeurIPS 2026) settled the product orders, conjectured the minimax rate for every finite partially ordered set, and posed the general case as an open problem. We resolve all of these open problems on every finite poset , determining the squared-loss minimax regret over rounds up to absolute constants: where is the logarithm of Stanley's order polynomial at , which counts the monotone maps from into . The same formula holds for log loss and, up to loss-dependent constants, for bounded exp-concave smooth losses that are strongly proper, while pinball loss at quantile level has minimax regret , . Exponential weights over the monotone maps attains the upper bounds, but its predictions are #P-hard to compute exactly on a general partial order. Our learner instead perturbs the scores with low-dimensional Gumbel noise and samples their maximizers, one minimum cut per sample, and an inequality that we call Gibbs domination shows that this costs only a constant factor in regret. It runs in polynomial time and attains each of these rates without knowledge of the horizon.

Primary area:
learning theory
Keywords:
online learning, isotonic regression, minimax regret

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_LfUiOpenReview ↗
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
AuthorsOpenReview ↗

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)r_P(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 PP”, 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 32K232K^2 rounds.

Absolute loss. The absolute loss is twice the pinball loss at τ=1/2\tau=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)})\Theta\left(\min\left\lbrace T,\sqrt{T H_P(1)}\right\rbrace\right)

with absolute constants, where HP(1)H_P(1) is the logarithm of the number of binary isotonic functions on PP. On a chain of nn points this is of order min⁡{T,Tlog⁡(n+1)}\min\lbrace T,\sqrt{T\log(n+1)}\rbrace. 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.

AuthorsOpenReview ↗

Response to Reviewer LfUi (2/4)

Running time and experiments. The growth of the per-round computation with tt comes from the horizon-free learner of Theorem 4, which at round tt uses all the resolutions K=1,2,4,…K=1,2,4,\ldots up to tt. Algorithm 1 works at one fixed resolution KK. In every round it predicts at the queried point with the average of SS sampled predictions, each computed by one minimum cut on a network with nK+2nK+2 vertices, so for fixed KK and SS the number and the size of the minimum cuts per round do not grow with tt. The algorithm has two modes. Pair mode uses a small learning rate, and with S=2S=2 it already has a regret bound of order HP(K)+T/K2H_P(K)+T/K^2 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 2κcΦHP(K)+T/(4K2)+T/(4S)2\kappa c_\Phi H_P(K)+T/(4K^2)+T/(4S) for every fixed SS, which for S=K2S=K^2 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 [m]2[m]^2 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 SS times as long, and SS 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 200n200n 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 200n200n 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 SS independent copies of the noise are drawn once and kept, they therefore still give SS 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 KK 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 [m]2[m]^2, on which a calibration map with two signals of mm 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 1/21/2 in every round and has regret n/4n/4 on nn points. The guarantee of Algorithm 1 is of the order of rP(n)r_P(n), which grows like n1/3n^{1/3} up to logarithmic factors on a chain and like n2/3n^{2/3} on [m]2[m]^2, 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 S=K2S=K^2, 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 S=2S=2 between 2 and 6 times.

Constants. In Theorem 1 the small constant is that of the lower bound, λ/2048\lambda/2048, which results from the block argument, with λ≈0.19\lambda\approx0.19 from the constant of Linial and Saks. The upper bound of the theorem holds with the constant 11. For the learner, the factor between its regret bound and that of exponential weights is κcΦ<11.3\kappa c_\Phi\lt11.3, the product of two constants, κ=4\kappa=4 from Gibbs domination and cΦ<2.82c_\Phi\lt2.82 from the bound Φ(0)≤cΦHP(K)\Phi(0)\le c_\Phi H_P(K) on the potential before the first round. In the experiments the learner performs considerably better than this guarantee. On the sequences of nn rounds described above, its regret in mean mode with S=K2S=K^2 lies between 0.170.17 and 0.570.57 times rP(n)r_P(n), against a guarantee of 11.3rP(n)11.3 r_P(n).

AuthorsOpenReview ↗

Response to Reviewer LfUi (3/4)

The constant κ\kappa of Gibbs domination. The value κ=4\kappa=4 is in part an artifact of the analysis. With a minimum chain partition it can be lowered to 22 at the resolutions K=2,3K=2,3 and to 33 for 4≤K≤74\le K\le7. For the learner, the factor 11.311.3 accordingly becomes 5.75.7 at K=2,3K=2,3 and 8.58.5 for 4≤K≤74\le K\le7 when the learning rate is raised in the same proportion. The constant κ\kappa cannot be lowered below 22, however, since at every resolution K≥2K\ge2 there is a poset with a minimum chain partition for which no constant below 22 makes the inequality of Theorem 3 hold for all scores. At K=2,3K=2,3 the value 22 is therefore the best possible.

The value 11 can be reached with a different partition. If the cells (x,j)(x,j) are partitioned into the nn columns, one for each point xx, the inequality holds with κ=1\kappa=1 at every resolution (Lemma 18). The regret bound of the learner is proportional to κΦ(0)\kappa\Phi(0), however, where Φ(0)\Phi(0) is the potential before the first round. On a chain of nn points the partition into columns has Φ(0)\Phi(0) at least of order n\sqrt n, whereas a minimum chain partition keeps Φ(0)≤2.82HP(K)\Phi(0)\le2.82 H_P(K), which is of order log⁡n\log n at a fixed resolution. With the partition into columns the regret bound is therefore of larger order in nn, and the learner uses a minimum chain partition for this reason.

With a minimum chain partition, the value 44 arises in the proof of Theorem 3 as a product of two factors 22. 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 (u−v)2≤2(u2+v2)(u-v)^2\le2(u^2+v^2) 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 44. Since Theorem 3 remains valid, the inequality holds at a point xx with

κx=min⁡{4,sx,⌈log⁡2(K+1)⌉}\kappa_x=\min\lbrace4, s_x, \lceil\log_2(K+1)\rceil\rbrace

in place of κ\kappa, where sxs_x is the number of chains of the partition that contain a cell of xx, and ⌈log⁡2(K+1)⌉\lceil\log_2(K+1)\rceil is 22 for K=2,3K=2,3 and 33 for 4≤K≤74\le K\le7. 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 11. Two ideals with different levels at xx differ in the prefix length of a chain through a cell of xx, 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 ⌈log⁡2(K+1)⌉\lceil\log_2(K+1)\rceil 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 22. Let PP be the chain x1≺x2≺x3x_1\prec x_2\prec x_3 and K=2K=2. The cells of level 11 form a chain, namely (x3,1)<(x2,1)<(x1,1)(x_3,1)\lt(x_2,1)\lt(x_1,1) in the order of Definition 2, in which the points appear in reverse, and the cells of level 22 form a second chain. The two chains form a minimum chain partition, because the cells (x1,1)(x_1,1) and (x2,2)(x_2,2) are incomparable. Let the scores of the levels 11 and 22 at x1x_1 and of the levels 00 and 11 at x3x_3 tend to −∞-\infty, so that in the limit only the three functions with F(x1)=0F(x_1)=0 and F(x3)=2F(x_3)=2 remain, and give the level 11 at x2x_2 the score tt and every other level the score 00. The ideal of the function with F(x2)=jF(x_2)=j has prefix length 22 in the first chain if j≥1j\ge1 and 11 otherwise, and prefix length 22 in the second chain if j=2j=2 and 11 otherwise. With ξi,k\xi_{i,k} the noise of the prefix of length kk in the ii-th chain, the perturbed scores of the three functions are therefore ξ1,1+ξ2,1\xi_{1,1}+\xi_{2,1}, t+ξ1,2+ξ2,1t+\xi_{1,2}+\xi_{2,1} and ξ1,2+ξ2,2\xi_{1,2}+\xi_{2,2}, and the maximizer has the level 11 at x2x_2 exactly when ξ1,2−ξ1,1>−t\xi_{1,2}-\xi_{1,1}\gt-t and ξ2,1−ξ2,2>−t\xi_{2,1}-\xi_{2,2}\gt-t. These two differences are independent logistic variables, so this event has probability p=q2p=q^2 with q=1/(1+e−t)q=1/(1+e^{-t}), and dp/dt=2q2(1−q)dp/dt=2q^2(1-q). When tt is raised by ε\varepsilon, the potential grows by εp+ε2(dp/dt)/2+O(ε3)\varepsilon p+\varepsilon^2(dp/dt)/2+O(\varepsilon^3), and the right side of Theorem 3 is εp+κε2p(1−p)/2+O(ε3)\varepsilon p+\kappa\varepsilon^2p(1-p)/2+O(\varepsilon^3). The inequality therefore requires

κ≥dp/dtp(1−p)=21+q,\kappa\ge\frac{dp/dt}{p(1-p)}=\frac{2}{1+q},

which tends to 22 as t→−∞t\to-\infty. For K≥3K\ge3 the same computation applies when PP is a chain of KK points and the partition consists of the KK sets of cells of equal level, if the scores leave only the functions that are 00 at x1x_1, at most 22 at x2x_2 and 22 at all later points.

Reviewer_LSyTOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies sequential prediction over a known finite set with monotonicity constraints. They characterize the smallest worst-case cumulative prediction regret using the number of monotone functions at different numerical resolutions. They then construct a polynomial-time algorithm that achieves that rate.

Critical strengths

The paper addresses a recognizable problem of performing isotonic regression in the presence of streaming data, i.e., the incorporation of an online learning framework. I appreciate its rigorous treatment of the statistical and computational challenges presented in online isotonic regression estimation and regret bound analysis. The matching upper and lower regret bounds establish that the proposed performance guarantees are optimal up to constant factors, providing a clear account of the unavoidable cost of learning sequentially. Extending these results to arbitrary finite partial orders substantially broadens their scope beyond simpler ordering structures. The guarantees also accommodate arbitrary observation sequences without an iid assumption, which is valuable when the order of incoming data cannot be controlled. In addition, the authors provide a polynomial-time learner that attains these rates through minimum-cut optimization, giving readers a concrete illustration of how the minimax analysis translates into a computationally tractable learning procedure. Its ability to operate without knowing the total number of rounds in advance further strengthens its suitability for streaming settings, where the eventual amount of data is often unknown.

Critical weaknesses

The paper would benefit from a simulation study illustrating how its theoretical guarantees translate into observed performance. For example, tracking cumulative regret and computing time as observations arrive, across several ordering structures and against simpler baseline methods, would help readers understand when the proposed learner offers a meaningful advantage. This is particularly relevant because attaining the optimal regret rate and running in polynomial time leave open questions about performance at realistic sample sizes. Furthermore, Section 2 assumes a finite set of input points and their ordering are known in advance, with each outcome revealed within the same prediction round. Although these assumptions are clearly stated, their practical implications warrant further discussion. For example, applications with continuously valued covariates may involve new input points outside any predefined finite set. It would therefore be useful to discuss whether the analysis could accommodate an unknown or expanding domain, or how discretization could connect such applications to the current framework. Alternatively, concrete real-world examples satisfying the known-domain and feedback assumptions would help readers understand where the proposed regret bounds are directly applicable.

Questions for authors
  1. Could the authors provide concrete real-world examples in which the possible input points and their ordering are known in advance, and outcomes are available within each prediction round?
  2. What challenges would arise when extending the framework to an unknown or expanding input domain, particularly for continuously valued covariates?
  3. Could discretization connect continuous-domain applications to the current framework? If so, how would the resulting approximation error affect the regret guarantees?
  4. How would delayed outcome feedback affect the proposed learner, and which parts of the analysis would require modification?
4 comments
AuthorsOpenReview ↗

Response to Reviewer LSyT (1/4)

Thank you for your careful and thorough review and for your questions on how the results apply in practice. In response, we have added experiments to the paper, with the code in the supplementary material, and the introduction now explains why the points are assumed to be known in advance and says that continuous inputs are binned. We have also revised 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.

Simulation study. The submitted version had no experiments, and we have added them in the new Appendix J to show how the theorems and the algorithm translate into observed performance. They compare our learner with follow the leader, which predicts with the least-squares isotonic fit to the past labels. Follow the leader is fast, and on benign data it already performs well. Its regret depends on the order in which the points arrive, however, and it can be linear in the number of rounds, even on a chain (Kotłowski et al., 2016), whereas the guarantee of our learner holds for every sequence. The two methods can therefore differ widely when the order of arrival is unfavorable. As you note, the order of incoming data cannot always be controlled, so we ran the experiments on sequences that arrive in an unfavorable order.

The sequences in the experiments are simple, with labels that are 00 on a downward closed set and 11 on the remaining points. An isotonic function fits these labels without error, and only the order of arrival is unfavorable. The points labeled 00 arrive from the bottom of the poset upward and those labeled 11 from the top downward, interleaved, so every value at the next point is consistent with the labels seen so far. Follow the leader then predicts 1/21/2 in every round, and on nn points its regret is n/4n/4. For our learner (Algorithm 1) the guarantee is a regret of the order of the rate rP(n)r_P(n) of Theorem 1, and on many posets this rate grows much more slowly than nn. On a chain it is of order n1/3n^{1/3} up to logarithmic factors, and on the product order [m]2[m]^2 it is of order n2/3n^{2/3}. The gap between the two methods therefore widens with the size of the problem, and Figure 2 shows this on chains, on ordinal sums of antichains and on product orders [m]2[m]^2. Algorithm 1 predicts with the average of SS sampled predictions per round, and we ran it in the two modes of the paper, pair mode with S=2S=2 and mean mode with S=K2S=K^2 at resolution KK. In pair mode, follow the leader has between 2 and 6 times the regret of the learner. In mean mode the factor grows from about 4 on the smallest instances to between 9 and 18 on the largest, which have a few thousand points, and the measured regret of the learner stays below rP(n)r_P(n) throughout. For sequences of this kind the advantage is clear already at moderate sizes, and it increases as the problem grows.

For the second guarantee of the paper, the polynomial running time, the relevant quantity is the time of one sampled prediction. Each sampled prediction is computed by one minimum cut, and a round takes SS of them, between 2 and 25 in the experiments above. Table 2 reports this time on product orders [m]2[m]^2 with 64 to 4096 points and resolutions up to 32. It is longer at the start, before the learner has seen any data, where it lies between a fraction of a millisecond and 1.5 seconds depending on the instance. After a long run of the learner it is shorter on every instance and at most 34 milliseconds. The learner is slower than follow the leader, whose regret, however, can be linear, as described above. The other known way to the optimal rate is exponential weights, whose predictions are #P-hard to compute exactly on a general poset. Of the three methods, only our learner has both a regret guarantee of optimal order and a polynomial running time on every finite poset.

AuthorsOpenReview ↗

Response to Reviewer LSyT (2/4)

Real-world examples. In the introduction we name the applications only by area. Here we make explicit how three applications fit the setting of the paper, in particular why the points and their order are known in advance and when the outcome arrives.

The first is a phase I trial of a drug combination (Wages et al., Biometrics, 2011). The dose combinations to be tested are fixed in the design of the trial. The probability of a toxic reaction increases with the dose of each drug when the doses of the others are held fixed, so the combinations are partially ordered, and both the points and their order are known before the first patient is treated. Each patient is one round, in which the learner predicts the probability of a toxic reaction at the combination that the patient receives, and in this design the reaction is observed before the next patient is assigned a dose.

The second is the calibration of click probabilities in online advertising (Dai et al., WWW, 2025). An advertising platform ranks the candidate advertisements by expected revenue, the amount that the advertiser bids for a click times the predicted probability of a click. Since the bids differ, this ranking depends on the values of the predicted probabilities, and a correct order of the advertisements by click probability is not enough. The scores of the prediction model are therefore calibrated before they are used, that is, passed through a map that brings them into agreement with the observed click frequencies. The map takes the score together with a context feature of the display, such as the country or the source of the advertisement, and it is increasing in the score for every value of the feature, so that the ranking by the model is preserved. As in binning-based calibration methods, we divide the scores into bins at quantiles fixed before deployment. The points are then the pairs of a feature value and a score bin, and two pairs are comparable when they have the same feature value. A round is one display, the prediction is the calibrated click probability, and the outcome, a click or none, is known once a fixed time window after the display has passed.

The third is the statistical postprocessing of weather forecasts (Henzi et al., J. R. Stat. Soc. B, 2021). Henzi et al. predict the probability of precipitation in a 24-hour period from three summaries of an ensemble of numerical forecasts, namely the high-resolution forecast, the control forecast and the mean of the perturbed forecasts. In their model this probability is nondecreasing in each of the three summaries. We bin each summary, and the points then form a product order with three coordinates that is fixed in advance. One forecast is issued per day, and its outcome is known only once the forecast horizon has passed, between one and five days in their case study.

In the second and third examples the continuous variables are binned, and the outcome may arrive only after further predictions have been made. These are the situations of your third and fourth questions. The learner of the paper handles both, under the conditions and with the regret bounds that we give below under Discretization and Delayed feedback.

Unknown or expanding domain. Sublinear regret becomes impossible for arbitrary sequences once points can appear whose place in the order is not known beforehand. If the adversary may introduce such points, it can put each new point between the points labeled 00 so far and those labeled 11, and then give it the label farther from the expected prediction of the learner. Every round then costs the learner at least 1/41/4 in expectation, while a threshold function predicts every label correctly, so the regret is linear even on a totally ordered set (Kotłowski et al., 2016). Continuous covariates about which nothing is assumed lead to this situation, because every observation can be a new point. Some additional assumption is therefore necessary, and two such assumptions are known. The first is the assumption of the paper that the possible points form a finite set fixed in advance. The submitted version stated it without this reason, and the revised introduction now gives the reason. Under this assumption the learner has to know which points can occur and how they are ordered, but not which of them will be queried or how often, so the set PP may contain more points than are ever seen, and the queried part of it may grow throughout play. For continuous covariates such a set is obtained by binning, and the part on discretization below shows how the regret bound changes. The second assumption is a restriction on the order of arrival. For a totally ordered set, Kotłowski et al. (2017) show that sublinear regret is possible without knowing the points in advance when they arrive in random order, and the extension of this result to partial orders is a separate question.

AuthorsOpenReview ↗

Response to Reviewer LSyT (3/4)

Discretization. Continuous covariates fit the setting of the paper once they are discretized, and the approximation error then appears as one additional term in the regret bound. Let the covariates lie in [0,1]d[0,1]^d with the coordinatewise order, and divide each coordinate into mm equal intervals. The resulting cells form the product order [m]d[m]^d. Run any learner on [m]d[m]^d and show it in each round the cell of the covariate xtx_t. Then for every sequence and every function gg from [0,1]d[0,1]^d to [0,1][0,1] that is nondecreasing in each coordinate,

∑t≤T(y^t−yt)2−∑t≤T(g(xt)−yt)2≤RT+2dmd−1NT,\sum_{t\le T}(\hat y_t-y_t)^2-\sum_{t\le T}(g(x_t)-y_t)^2\le R_T+2dm^{d-1}N_T,

where RTR_T is the regret of the learner on [m]d[m]^d and NTN_T is the largest number of rounds that fall into one cell.

The size of the additional term depends on how the rounds spread over the cells. Without any condition NTN_T can be as large as TT, and the term is then linear in TT, in agreement with the impossibility result of Kotłowski et al. (2016). If no cell receives more than a constant multiple of its share, that is, NT≤c0T/mdN_T\le c_0T/m^d for a constant c0c_0, the term is at most 2dc0T/m2dc_0T/m. For i.i.d. covariates with a bounded density this holds with high probability when T/mdT/m^d is large compared with log⁡T\log T, by a Chernoff bound and a union bound over the cells. With finer bins the additional term becomes smaller and the rate on [m]d[m]^d larger, so mm is chosen to balance the two. In two dimensions, for example, the rate on [m]2[m]^2 is of order m2/3T1/3m^{2/3}T^{1/3} for m≤T≤m4m\le T\le m^4 (Table 1). Under the condition on NTN_T and with mm of order T2/5T^{2/5}, the rate and the additional term are both at most of order T3/5T^{3/5}, and the learner of Theorem 4 has expected regret at most of order T3/5T^{3/5} against every monotone function on the square. In summary, continuous covariates can be handled by discretization, and the approximation error appears in the regret bound as a single additive term. Under the condition on NTN_T above, this term is of smaller order than TT for a suitable choice of mm.

For the proof of the inequality, let ff be the function on [m]d[m]^d whose value in each cell is the value of gg at the upper corner of the cell. This ff is isotonic, so the cumulative loss of the learner exceeds that of ff by at most RTR_T, and it remains to compare ff with gg. In a round that falls into the cell cc, the value g(xt)g(x_t) lies between the values of gg at the lower and the upper corner of cc, because gg is monotone. The values of ff and gg in this round therefore differ by at most the difference Δc\Delta_c of the two corner values and, since all values lie in [0,1][0,1], their squared losses differ by at most 2Δc2\Delta_c. Each cell is visited at most NTN_T times, so the cumulative losses of ff and gg differ by at most 2NT2N_T times the sum of the Δc\Delta_c over all cells. To bound this sum by dmd−1dm^{d-1}, we group the cells into diagonal chains. Each chain starts at a cell that has a coordinate equal to one, and each step along it raises every coordinate by one. Along a chain the upper corner of a cell is the lower corner of the next, so the differences Δc\Delta_c along it add up to a difference of two values of gg and hence to at most one. There are at most dmd−1dm^{d-1} cells with a coordinate equal to one, hence at most that many chains, and the sum is at most dmd−1dm^{d-1}.

AuthorsOpenReview ↗

Response to Reviewer LSyT (4/4)

Delayed feedback. With a delay of DD rounds, where the label of round tt becomes available only after round t+Dt+D, the term 2HP(K)2H_P(K) of the rate becomes 2(D+1)HP(K)2(D+1)H_P(K), and nothing else in the rate changes. The learner is run in D+1D+1 copies that take the rounds in turn, and no part of the analysis has to be modified, because the bounds follow from Theorems 1 and 4 as they stand. For squared loss and a fixed delay D≥0D\ge0, the minimax regret is of order

min⁡{T,inf⁡K≥1(2(D+1)HP(K)+T4K2)}\min\left\lbrace T, \inf_{K\ge1}\left(2(D+1)H_P(K)+\frac{T}{4K^2}\right)\right\rbrace

with absolute constants, and a polynomial-time learner attains this order. On the product order [m]d[m]^d, for example, the expression is of order (D+1)2/3m2(d−1)/3T1/3(D+1)^{2/3}m^{2(d-1)/3}T^{1/3} for (D+1)md−1≤T≤md+2(D+1)m^{d-1}\le T\le m^{d+2}, that is, (D+1)2/3(D+1)^{2/3} times the rate without delay (Table 1).

For the upper bound, the D+1D+1 copies are independent copies of the learner of Theorem 4, and letting them take the rounds in turn is a standard reduction for delayed feedback (Joulani, György and Szepesvári, ICML 2013). When a copy has to predict, the labels of all its earlier rounds have arrived, so each copy runs without delay on its own rounds, and the regret of the whole run is at most the sum of the regrets of the copies. By Theorem 4, a copy that runs for T′T' rounds has expected regret at most a constant times rP(T′)r_P(T'). By the definition of the rate, rP(T′)r_P(T') is at most T′T' and at most 2HP(K)+T′/(4K2)2H_P(K)+T'/(4K^2) for every KK. Summing these bounds over the D+1D+1 copies, whose numbers of rounds add up to TT, gives a constant times the expression above. The same upper bound holds when the delays vary from round to round but never exceed DD.

For the lower bound, take any sequence of points and labels and repeat each of its rounds D+1D+1 times. Under delay DD, no label of such a block of D+1D+1 rounds reaches the learner before the block is over, so its predictions in the block depend only on the labels of earlier blocks. Now consider a learner without delay on the original sequence. In each round it can compute the D+1D+1 predictions of the delayed learner in the corresponding block before the label of the round is revealed, and it predicts their average. Since the squared loss is convex, the loss of this average is at most the average of the D+1D+1 losses, while every isotonic function has over the block exactly D+1D+1 times its loss in the round. On the repeated sequence the delayed learner thus has at least D+1D+1 times the regret of the learner without delay on the original one.

By Theorem 1 there is, for this learner without delay, a sequence of T′T' rounds on which its expected regret is at least a constant times rP(T′)r_P(T'), where T′T' is the integer part of T/(D+1)T/(D+1). Its repetition has (D+1)T′(D+1)T' rounds. The rounds that remain are spent at one fixed point, with the value there of a best isotonic function for this sequence as the label, and this does not lower the regret. Multiplied by D+1D+1, the rate rP(T′)r_P(T') is the expression above with (D+1)T′(D+1)T' in place of TT. When T≥D+1T\ge D+1, the number (D+1)T′(D+1)T' is at least T/2T/2. Since the expression is nondecreasing in TT and falls by at most half when TT is halved, the product (D+1)rP(T′)(D+1)r_P(T') is then at least half of the expression itself. When T≤DT\le D no label arrives during play. A fair binary label that is repeated at one point then gives every learner expected regret at least T/4T/4, and the expression equals TT because HP(K)≥log⁡2H_P(K)\ge\log2 for every KK.

We hope that these answers address your questions, and we are happy to discuss any of them further.

Reviewer_1T9kOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In summary, this paper studies online isotonic regression with arbitrary partial orders. Concisely, they contribute the minimax bounds for the problem and achieve them in performance with an efficient polynomial time algorithm. The paper is validated through proofs, mostly in appendix.

Critical strengths

The submission seems technically correct in general, more so for Section 3, where the bounds are presented.

The submission appears to present novel findings. Theoretical findings are through the presentation of the minimax rates and algorithmic findings are through the polynomial time algorithm, although the algorithm is not very clearly presented.

Critical weaknesses

The submission is not clear in important aspects. I had trouble digesting especially Section 4 which seems to present the core method.

The submission is not experimentally rigorous and reproducible as the results are purely mathematical.

Questions for authors

In Section 4, too much terminology is convoluted without proper definitions.

Line 58: could you expand and clarify here what special case Wang (2026) achieved and what the general case is.

Line 85: how is Omega and F_K related?

Line 92: this sentence is hard to understand.

Line 118: what do you mean by "resolution"? Please define it.

Line 143: nats?

Figure 1: why are (x,0) cells not included?

Line 238: what does it mean for a central element of a poset to lie in a fraction of its ideals given as a scalar interval?

Line 274: define n.

Line 298: what are residual and induced ideals? Aren't ideals of function F, what does ideals of a poset mean?

Line 325: minimum cut needs to be properly defined for your context.

Line 330: what is the use of these chains?

Line 338: why does the noise accumulate like this, i.e., once per chain?

Line 345: so sum k_i is the total range of x? why are they necessarily the prefix of each chain?

Line 346: Why does the error coordinate count grow beyond the (x,j) grid? Isn't it exactly nK?

Line 349: shouldn't the inequalities here be reversed?

Line 381: why introduce new notations L and alt-sigma? This sketch is very confusing.

Line 414: why every ideal?

5 comments
AuthorsOpenReview ↗

Response to Reviewer 1T9k (1/3)

Thank you for your careful and thorough review and for the detailed questions on individual lines. In response, we have 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.

Section 4. You had trouble digesting Section 4 and found that it used terminology without proper definitions. When we reread the section as a first-time reader would, we found that its opening used the level distribution and the perturbed potential before Section 4.1 defined them, and that Section 4.1 introduced the chains and the noise without saying what they are for. We have rewritten large parts of the section. It now begins by saying what the learner does and how the section proceeds. Section 4.1 then builds the learner's random perturbation step by step from two standard tools, exponential weights and Gumbel sampling, with a reason for each choice. In Section 4.2, the proof sketch of Theorem 3 (Gibbs domination) is divided into its three steps and says why each one holds. Algorithm 1, the pseudocode of the learner at a fixed resolution, now appears in the main text (page 9).

Experiments and reproducibility. The results of the paper are mathematical, and each is proved in full in the appendix. To show how the learner behaves in practice, we have added experiments in the new Appendix J, and the code for the algorithm and the experiments is in the supplementary material. In these experiments we compare the regret of Algorithm 1 with that of the follow-the-leader baseline on sequences that are hard for follow the leader. The regret of Algorithm 1 is smaller on every instance. When the algorithm averages K2K^2 sampled predictions per round at resolution KK, its regret is smaller by a factor that grows with the number of points, from 4.5 to 17.5 on chains, from 3.5 to 9.3 on ordinal sums of antichains and from 3.9 to 10.0 on product orders. We also report the time that the algorithm takes for one sampled prediction.

Line 58. Wang (2026) and the general case. Wang (2026) treats the product orders [m]d[m]^d for every fixed dimension d≥2d\ge2. For these posets that paper determines the minimax regret under squared loss by a formula, up to constants that depend on dd, and gives polynomial-time learners that attain it. The general case is an arbitrary finite poset. Wang (2026) conjectured that the same formula holds there and posed this case as an open problem, to prove the conjecture and to attain the rate in polynomial time. Our Theorem 1 proves the conjecture, and Theorem 4 gives the polynomial-time learner. The constants of Theorem 1 are absolute, so on the product orders it also removes the dependence on dd. The introduction now states the result of Wang (2026) and its conjecture in two separate sentences.

Line 85. The relation between Ω\Omega and FK\mathcal F_K. The class FK\mathcal F_K consists of the isotonic functions from PP into the grid {0,1/K,…,1}\lbrace 0,1/K,\ldots,1\rbrace, and Ω(P,K+1)\Omega(P,K+1) is the number of isotonic functions from PP into {0,…,K}\lbrace 0,\ldots,K\rbrace. Multiplication by KK turns the functions of the first kind into those of the second, one to one, so ∣FK∣=Ω(P,K+1)\lvert\mathcal F_K\rvert=\Omega(P,K+1). In the submitted version this identity came only in Section 2 (line 214), after the introduction had used both symbols. Section 1.1 now states it where the order polynomial is introduced.

Line 92. The sentence on central elements. The sentence is about the lower bound, in which the adversary picks an ideal in secret and the learner has to find out which one. Here an ideal of a poset is a downward closed subset. Linial and Saks (1985) proved that every nonempty finite poset has an element that lies in at least a sixth of its ideals and outside at least a sixth of them, and such an element is called central. Once the learner knows whether a central element lies in the hidden ideal, at least a sixth of the ideals are ruled out, whichever the answer. The ideals that remain correspond to the ideals of a smaller poset, which again has a central element, so the same step can be repeated until one ideal is left. We have rewritten the sentence to say this.

Line 118. The meaning of “resolution”. The resolution of a grid is the number of its levels minus one, so the grid {0,1/K,…,1}\lbrace 0,1/K,\ldots,1\rbrace has resolution KK. For squared loss the rate involves an infimum over KK, and the resolution that attains this infimum depends on the horizon TT. For pinball loss the rate is min⁡{ρT,ρTHP(1)}\min\lbrace\rho T,\sqrt{\rho T H_P(1)}\rbrace up to constants. It contains only HP(1)H_P(1), the value of HPH_P at resolution one, so no resolution has to be chosen, which is what the sentence at line 118 says. In the submitted version the word was defined only in Section 2 (line 209), after line 118. We now introduce it in Section 1.1, where it is first used.

AuthorsOpenReview ↗

Response to Reviewer 1T9k (2/3)

Line 143. “Nats”. A nat is the unit of information when logarithms are natural, as a bit is when they are binary. The hidden ideal is uniform over eHP(K)e^{H_P(K)} ideals, so its entropy is HP(K)H_P(K) nats. The sentence now reads “the entropy HP(K)H_P(K) of the hidden ideal”, and Section 2 states that entropies are in nats.

Figure 1. The cells (x,0)(x,0). By Definition 2, QKQ_K is the set P×{1,…,K}P\times\lbrace 1,\ldots,K\rbrace, so its levels start at 11. The ideal IFI_F contains the cells (x,1),…,(x,F(x))(x,1),\ldots,(x,F(x)) of each point xx, so F(x)=0F(x)=0 means that it contains no cell of xx, as for u′u' in the right panel of Figure 1. A cell (x,0)(x,0) would lie in the ideal of every function, whatever the value F(x)F(x), and would therefore be redundant. The paragraph after Definition 2 now states that QKQ_K needs no level 00.

Line 238. Central elements and the interval [δLS,1−δLS][\delta_{\mathrm{LS}},1-\delta_{\mathrm{LS}}]. The fraction in question is the number of ideals of the poset that contain the element, divided by the number of all its ideals, and the element is central if this fraction lies between δLS≈0.17\delta_{\mathrm{LS}}\approx0.17 and 1−δLS≈0.831-\delta_{\mathrm{LS}}\approx0.83. In Figure 1, the cell (u,1)(u,1) lies in 88 of the 1414 ideals of Q2Q_2, a fraction of 0.570.57, so it is central. The definition is now a sentence of its own.

Line 274. The definition of nn. Here nn is the number of points of PP, as defined at the start of Section 2 (line 174).

Line 298. The residual poset and its ideals. An ideal is always a subset of a poset, a downward closed one (Section 2, line 228). The ideal of a function is defined in Definition 2. An isotonic function FF corresponds to the subset IFI_F of the poset QKQ_K, this subset is an ideal of QKQ_K, and every ideal of QKQ_K arises from exactly one FF. Hiding a function and hiding an ideal of QKQ_K are therefore the same thing. At line 298 the words “residual” and “induced” qualify a poset. In the lower bound the adversary reveals levels of the hidden function. After that, some cells of QKQ_K are known to lie in the hidden ideal, others are known to lie outside it, and the rest are undecided. The residual poset consists of the undecided cells, and “induced” meant that these cells keep the order they have in QKQ_K. The unknown part of the hidden ideal is an ideal of the residual poset (Lemma 6), so the theorem of Linial and Saks can be applied to it again. The revised sentence defines the residual poset directly and no longer uses “induced”.

Line 325. The minimum cut. The learner needs the ideal of QKQ_K with the highest perturbed score. This score is a constant plus the total weight of the cells of the ideal, where every cell has a real weight determined by the scores and the noise. By a result of Picard (1976), an ideal of maximum weight is obtained from a minimum cut of the following network. It has a source, a sink and one vertex per cell. The source is joined to every cell of positive weight, and every cell of negative weight to the sink, with capacity the absolute value of the weight. Every cell is joined to the cells that it covers, those immediately below it, with a capacity above the total absolute weight. A minimum cut then contains no arc between cells, so the cells on its source side form an ideal, and this ideal has maximum weight. The submitted version cited this result in Section 4.1 and described the network only in Appendix D. The revised Section 4.1 describes the network itself.

Lines 330 and 338. The chains and the noise. The chains determine the noise that the learner adds to the scores of the ideals. Two simpler choices of noise do not work. With one independent Gumbel variable for each ideal, the ideal with the highest perturbed score is an exact sample from exponential weights, but there can be exponentially many ideals. With one variable for each cell, and the noise of an ideal equal to the sum over its cells, the maximizer is computed by one minimum cut, but the noise is too large. The regret bound is proportional to the expected maximum of the noise over the ideals. Already on a single point, where QKQ_K is one chain of KK cells, this expected maximum is of order K\sqrt K, whereas exponential weights has HP(K)=log⁡(K+1)H_P(K)=\log(K+1) in its place. The learner therefore divides the cells of QKQ_K into chains. An ideal meets each chain in a prefix, and the learner uses one Gumbel variable for each prefix of each chain. An ideal has exactly one prefix in each chain, so its noise is a sum of one variable per chain, ξ(I)=∑iξi,ki(I)\xi(I)=\sum_i\xi_{i,k_i(I)}, which is the formula at line 338. With this noise the maximizer is still computed by one minimum cut. The expected maximum of the noise is at most 2HP(K)2H_P(K) plus a constant for each chain, which is why the learner uses as few chains as possible. The expected maximum is then at most 2.82HP(K)2.82 H_P(K). Section 4.1 now opens with this explanation.

AuthorsOpenReview ↗

Response to Reviewer 1T9k (3/3)

Line 345. Prefixes and the sum of the kik_i. An ideal is downward closed, and the cells of a chain are totally ordered. If the ideal contains a cell of a chain, it therefore contains every cell of the chain that lies below that cell, so its intersection with the chain is a prefix, a possibly empty initial segment of the chain. Every cell lies in exactly one chain, so the prefix lengths add up to the number of cells of the ideal, which is also the sum of the levels of FIF_I over the points. Thus ∑iki(I)=∣I∣=∑xFI(x)\sum_ik_i(I)=\lvert I\rvert=\sum_xF_I(x), a number between 00 and nKnK. The revised Section 4.1 says that an ideal meets each chain in a prefix because it is downward closed.

Line 346. The number of noise coordinates. The number is nK+wKnK+w_K, where wKw_K is the number of chains. A chain CiC_i has ∣Ci∣+1\lvert C_i\rvert+1 prefixes, the empty one included, and each has its own noise variable, as in the index set Ξ\Xi of Definition 3. An ideal that contains no cell of a chain has the empty prefix there, and the empty prefix has a variable of its own like every other prefix. The chains together contain the nKnK cells of QKQ_K, so there are nK+wKnK+w_K variables. The revised sentence says that the empty prefix is included.

Line 349. The direction of the inequalities. The inequalities are correct as written, because the order of QKQ_K reverses the order of PP. By Definition 2, (x,j)≤(x′,j′)(x,j)\le(x',j') means that x′⪯xx'\preceq x and j≤j′j\le j', so a cell becomes smaller when its point becomes larger. In Figure 1 the point vv lies above uu and u′u', hence (v,1)<(u,1)(v,1)\lt(u,1) and (v,2)<(u′,2)(v,2)\lt(u',2), and (u,1)<(u,2)(u,1)\lt(u,2) compares two levels of the same point. The reason for the reversal is that an isotonic function is larger at larger points. If F(x)≥jF(x)\ge j and x⪯x′x\preceq x', then F(x′)≥jF(x')\ge j as well, so whenever the cell (x,j)(x,j) belongs to IFI_F, the cell (x′,j)(x',j) belongs to it too. In the order of Definition 2 the cell (x′,j)(x',j) lies below (x,j)(x,j), which is why IFI_F is downward closed. In the submitted main text the reversal appeared only inside Definition 2 and without this reason, so it was easy to pass over. A sentence after the definition now gives the reason.

Line 381. The symbols LL and ς\varsigma in the sketch of Theorem 3. The two symbols belong to the first step of the sketch, which is a general fact. Take a set of ideals in which membership depends only on the prefix lengths in LL chains. If the scores of all its members are raised by ς≥0\varsigma\ge0, the probability that the perturbed maximizer lies in the set grows by a factor of at most eLςe^{L\varsigma}. So LL is a number of chains and ς\varsigma is the size of the raise. The second step uses this fact with L=2L=2 for the ideals whose function has level jj at a point xx. Whether an ideal is one of them depends on at most two cells, (x,j)(x,j) and (x,j+1)(x,j+1) where they exist, and hence on at most two chains. The constant κ=4\kappa=4 of the theorem comes from this exponent 22, and we state the first step for a general LL to make this visible. In the submitted version the sketch was a single paragraph and introduced both symbols within one sentence. It is now three paragraphs, one for each step, and the set of ideals is defined before the first step is stated.

Line 414. The inequality for every ideal. The potential Φ(θ)\Phi(\theta) is the expectation of the largest perturbed score. This score is at least the perturbed score θ(I)+ξ(I)\theta(I)+\xi(I) of any fixed ideal II, and the noise ξ(I)\xi(I) has mean zero, so Φ(θ)≥θ(I)\Phi(\theta)\ge\theta(I) for every ideal II. The proof of the regret bound applies this inequality to the ideal of the best grid-valued isotonic function in hindsight. This function is not known in advance, which is why the inequality is stated for every ideal. The submitted version stated the inequality at the start of Section 4.2 (line 363) but did not say why it holds. The revised version gives the reason at the same place.

We hope that these answers resolve your questions. We would be glad to clarify any point that remains unclear, here or in the paper.

Reviewer_jFcuOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper considers the problem of online isotonic regression on a partially ordered poset. The problem of online isotonic regression was considered in the work of Kotłowski et al., where, informally speaking, the goal of a learner is to make predictions that incur low regret compared to the best hypothesis in the class of isotonic functions (the setup in Kotłowski et al. considered isotonic functions over a chain x1≤⋯≤xTx_{1} \le \dots \le x_{T}). Kotłowski proposed an algorithm with the minimax regret Θ~(T1/3)\tilde{\Theta}(T ^ {1 / 3}) for the squared loss (they also considered several other loss functions, e.g., the cross entropy loss).

The current paper resolves the minimax regret for the squared loss in the partially ordered case. In particular, the instances chosen by the adversary belong to a poset PP. This was an open problem left in the work of Kotłowski et al. The major contribution of the paper is Theorem 1, which shows that the minimax regret for the squared loss is Θ(rP(T))\Theta(r_P(T)), where rP(T)=min⁡(T,inf⁡K≥1(2HP(K)+T4K2))r_P(T) = \min\left(T, \inf_{K \ge 1} (2H_P (K) + \frac{T}{4K ^ 2})\right) for any fixed poset PP. Here, HP(K)=log⁡Ω(P,K+1)H_{P}(K) = \log \Omega(P, K + 1) and Ω(P,K+1)\Omega(P, K + 1) counts the number of isotonic functions from PP to a uniform finite grid 0,1K,…,1{0, \frac{1}{K}, \dots, 1} of [0,1][0, 1] with K+1K + 1 points. Several other extensions to other loss functions are also analyzed, e.g., the cross-entropy loss. The major contribution of the paper seems to be in terms of getting a computationlly efficient algorithm achieving the upper bound (the standard approach of running exponential weights over the set of all isotonic functions mapping PP to the uniform grid seems to achieve the upper bound already) and proving a matching lower bound.

Critical strengths

The paper considers an important problem, the complexity of which has been unsettled since the work of Kotłowski et al. The paper fully establishes minimax error rates for the squared and cross-entropy losses for any fixed poset PP (in terms of developing a computationally efficient algorithm and a matching lower bound for the problem), which is quite nice!

Critical weaknesses

The paper is quite dense and hard to follow. The problem formulation and related definitions appear on page 4, and it is quite hard to parse the paper before that. At several places in the paper, a lot of content is clubbed together without intuition (e.g., the algorithm description in page 6). I am not an expert in this topic; however, I believe the paper requires significant rewriting to cater to a general audience (and possibly to the more expert readers too). Therefore, at this point, I am inclined towards rejection of the paper.

Questions for authors

I do not have any substantial questions for the authors. My concerns are mostly related to presentation.

1 comment
AuthorsOpenReview ↗

Response to Reviewer jFcu

Thank you for your careful and thorough review and for your kind words about the result. We agree with your concerns about the presentation. In response, we have 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.

Problem formulation and definitions. The submitted version described the problem on its first page, but only in words and in a few sentences that are easy to pass over, and the formal statement with the regret formula came in Section 2 on page 4. We have rewritten these sentences. The first page now states formally what happens in each round and gives the formula for the regret. You found the pages before Section 2 hard to parse. When we reread them as a first-time reader would, we found that Section 1.1 used several terms whose precise definitions appeared only in Section 2, such as the resolution of a grid and the central elements of a poset. Section 1.1 now explains these terms where it uses them.

Dense passages. The algorithm described on page 6 of the submitted version is exponential weights, which Section 3 uses to prove the upper bound. Looking at that page again, we found one paragraph that had to cover the algorithm, the rounding to the grid and the treatment of log loss, followed by a sketch of the lower bound that was a single long paragraph as well. The description of exponential weights is now three paragraphs, one for each topic. The sketch is now four paragraphs, and two new sentences before it state the idea of the lower bound.

Section 4, which presents our learner, was dense in the same way, and we have rewritten large parts of it. It now begins by saying what the learner does and how the section proceeds. Section 4.1 then builds the learner's random perturbation step by step from two standard tools, exponential weights and Gumbel sampling, with a reason for each choice. In Section 4.2, the proof sketch of Theorem 3 (Gibbs domination) is divided into its three steps and says why each one holds. Algorithm 1, the pseudocode of the learner at a fixed resolution, now appears in the main text (page 9).

Intuition for the lower bound and the learner. The lower bound comes from an adversary who secretly picks one of the isotonic functions with values in a grid of K+1K+1 levels. The learner finds out about this function through noisy labels. Until the labels at a point have revealed the value of the hidden function there, the learner predicts worse than someone who knows this value, and its expected excess loss is at least a constant times the information that the labels reveal. A theorem of Linial and Saks allows the adversary to keep the labels informative. As long as more than one candidate remains, the theorem provides a point where the value is uncertain enough that a block of order K2K^2 rounds at this point reveals at least a constant amount of information. The learner thus keeps paying until it knows the whole function or the TT rounds are over. Knowing the whole function takes an amount HP(K)H_P(K) of information, the logarithm of the number of candidates, and TT rounds contain about T/K2T/K^2 blocks. The regret is therefore at least a constant times the smaller of HP(K)H_P(K) and T/K2T/K^2.

Exponential weights over these functions attains a matching upper bound, but it is not an efficient algorithm on a general poset, because even its first prediction, a weighted average over all the functions, is #P-hard to compute exactly. Maximizing over the functions, by contrast, is easy. Each function has a score, the logarithm of its weight, and one minimum cut finds the function with the highest score. Our learner therefore perturbs the scores at random and predicts the value of the function with the highest perturbed score, averaged over independent draws of the noise. If every score received its own independent Gumbel variable, this function would be an exact sample from exponential weights, but there can be exponentially many functions. The learner uses at most 2nK2nK Gumbel variables per draw on a poset of nn points and shares them among the functions so that one minimum cut still finds the maximizer. Such a maximizer is in general not a draw from exponential weights. The analysis of exponential weights tracks one quantity from round to round, the logarithm of the total weight, and Gibbs domination (Theorem 3) shows that the corresponding quantity for our learner obeys an inequality of the same form. The same analysis therefore applies to the learner, with a regret bound larger by a constant factor. The revised Section 1.1 presents the lower bound and the learner along these lines.

We hope that the paper is now clear and accessible to a general reader, and we would be glad to revise any passage that you still find hard to follow.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revision

We thank the reviewers for their careful reading and their questions. We have uploaded a revised paper, with changes marked in red, together with the code for the algorithm and the experiments as supplementary material. At the request of several reviewers, we have 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 edits to their statements and proofs concern only presentation and wording.

Presentation (Reviewers jFcu, 1T9k and LfUi). The problem is now stated formally on the first page, where the second paragraph of the introduction describes each round and gives the formula for the regret. Section 1.1 now explains the grid, its resolution and the central elements of a poset where it uses them. In Section 3 the long paragraphs have been split, and the sketch of the lower bound is preceded by two sentences that give its idea. The description of the learner in Sections 1.1 and 4.1 has been rewritten to start from exponential weights and Gumbel sampling and to explain why the noise is attached to the prefixes of chains and why one minimum cut then computes a maximizer. The proof sketch of Theorem 3 now gives a reason for each step. Algorithm 1 has moved into the main text (page 9).

Setting and earlier work (Reviewers LfUi, LSyT and 1T9k). In the abstract, the claim now reads “In the natural protocol, in which points may recur, we resolve all of these open problems on every finite poset PP”. The introduction adds that points may also recur in Wang (2026), whereas in Kotłowski et al. (2016) each point appears once. It also explains why the poset is assumed known in advance. Without this assumption every learner has linear regret, even for squared loss on a total order (Kotłowski et al., 2016). The introduction now separates what Wang (2026) proved, a formula for the minimax regret on product orders, from what that paper left as a conjecture, the same formula on every finite poset.

Experiments and running time (Reviewers LSyT, LfUi and 1T9k). The new Appendix J compares the regret of Algorithm 1 with that of the follow-the-leader baseline on three families of posets and reports running times. Section 4.2 now states how many minimum cuts per round suffice for the regret bound in expectation at a fixed resolution, and the new Remark 5 in Appendix E bounds the expected regret in terms of the number of cuts per round.

The remaining changes keep the rest of the paper consistent with these revisions or adjust wording to improve clarity and avoid ambiguity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.