The Minimax Rate of Online Isotonic Regression on Product Orders

Kotłowski et al. (NeurIPS 2017) posed as a central open problem the design of efficient online isotonic regression algorithms beyond totally ordered domains. We resolve this for the product order $[m]\times[m]$, the canonical two-dimensional case, by determining the minimax regret up to constant factors: $$ R_T^* = \Theta\left(\min\left\\{T,\ \inf_{K \in \mathbb{N}_+}\left[\log\Omega([m]^2, K+1) + \frac{T}{K^2}\right]\right\\}\right), $$ where $\Omega(\mathcal{P}, K+1)$ is the order polynomial counting monotone maps from $\mathcal{P}$ to $[K+1]$. This unified formula reveals a three-phase scaling law: $\Theta(T)$ for $T \lesssim m$, $\Theta(m^{2/3} T^{1/3})$ for $m \lesssim T \lesssim m^4$, and $\Theta(m^2 \log(T/m^4))$ for $T \gg m^4$. We further construct polynomial-time algorithms achieving this rate in every regime, including a horizon-free variant requiring no advance knowledge of $T$.