The Minimax Rate of Online Isotonic Regression

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 $P$, determining the squared-loss minimax regret over $T$ rounds up to absolute constants: $R_T^{\ast }(P)=\Theta \left(\min \left\{T,{\inf }_{K\ge 1}\left[H_P(K)+\frac{T}{K^2}\right]\right\}\right),$ where $H_P(K)$ is the logarithm of Stanley's order polynomial at $K+1$, which counts the monotone maps from $P$ into $\{0,\dots ,K\}$. 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 $\tau$ has minimax regret $\Theta (\min \{\rho T,\sqrt{\rho T{H}_P(1)}\})$, $\rho =\tau (1-\tau )$. 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.