Paper-Conference

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 on the product orders $[m]^d = \{1, \ldots, m\}^d$ for every fixed dimension $d \geq 2$, determining the squared-loss minimax regret over $T$ rounds up to constant factors:

$$ R_T^{*}\bigl([m]^d\bigr) \;=\; \Theta_d\!\left(\min\!\left\{T,\; \inf_{K \in \mathbb{N}_+}\!\Bigl[\, 2\, H_{[m]^d}(K) \,+\, \frac{T}{4 K^2} \,\Bigr]\right\}\right), $$

where the order polynomial $\Omega(\mathcal{P}, K{+}1)$ counts the monotone maps from a poset $\mathcal{P}$ to $\{1, \ldots, K{+}1\}$ and $H_{\mathcal{P}}(K) := \log \Omega(\mathcal{P}, K{+}1)$. The formula reveals a three-phase scaling law: $\Theta_d(T)$ for $T \lesssim_d m^{d-1}$, $\Theta_d(m^{2(d-1)/3}\, T^{1/3})$ for $m^{d-1} \lesssim_d T \lesssim_d m^{d+2}$, and $\Theta_d(m^d \log(T/m^{d+2}))$ for $T \gg_d m^{d+2}$. The characterization covers every smooth, exp-concave, strongly proper, bounded loss and the entropic loss, up to loss-dependent constants, while absolute and pinball losses obey a square-root law. We construct polynomial-time algorithms matching the characterization in every regime, for every fixed $d$ and every covered loss, including a horizon-free learner requiring no advance knowledge of $T$.

Noisy evolution strategies under fixed evaluation budgets face a depth-fidelity trade-off: spending evaluations to denoise intra-generation rankings reduces the number of distribution updates the optimizer can execute. We argue for depth over fidelity and propose probabilistic elite membership (PEM), which replaces hard rank-based weights in evolution strategies with conditional expected rank weights that integrate over ranking uncertainty. PEM preserves the conditional mean update while reducing conditional update dispersion, a Rao-Blackwellization of the noisy rank-based step. We instantiate PEM via residual bootstrapping (RB-PEM) with capped per-generation overhead, complemented by an adaptive probe-and-switch mechanism for low-noise regimes. Across the COCO bbob-noisy suite and external tasks including RL policy search and hyperparameter optimization, RB-PEM achieves consistent gains in high-misranking, budget-constrained settings.