The Minimax Rate of Online Isotonic Regression on Product Orders

Online Learning Isotonic Regression Minimax Regret

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$.

Sichen Wang
NeurIPS 2026

Depth over Fidelity in Fixed-Budget Noisy Evolution Strategies

Evolution Strategies Noisy Optimization Black-Box Optimization
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.
Sichen Wang, Zhipeng Lu
ICML 2026

On Completion Times under Memoryless Catastrophe

Stochastic Processes Stochastic Resetting Completion Times
We study the completion time of a task subject to independent reset (catastrophe) at each step. The completion-time PGF depends on the base-process PGF through an affine relation, and we exploit this structure systematically. Our main result shows that, among age-based catastrophe mechanisms, geometric-tail catastrophe is exactly the class that yields uniform affine PGF structure; in continuous time, the characterization sharpens to Poisson resetting. We establish a sharp two-sided Kolmogorov bound of order $p+|\alpha|$ for the exponential approximation $d_K(T/E[T], \mathrm{Exp}(1))$, thereby closing a logarithmic gap. Applications to the coupon collector with reset coupons reveal a discontinuous Gumbel-to-Exponential transition under resetting, while a multi-phase model exhibits a Gaussian-to-exponential transition with exponential convergence rate.
Sichen Wang, Zhipeng Lu
Preprint

Retained-Set Descent for Diagonal Ramsey Numbers

Ramsey Theory Extremal Combinatorics Graph Theory
We study how far a fixed Ramsey upper bound can be improved by descending through blue neighborhoods in one vertex set while keeping a second set fixed. A weighted inequality in the two set sizes determines when the descent can stop. For the source bound specified here, the infimum diagonal exponent over all finite derivations lies in $[1.305,\,1.307]$. A finite derivation gives $R(k,k)\le3.69507^k$ for all sufficiently large $k$; a concave polygon proves the lower bound for every finite depth. We also characterize the infimum as a greatest fixed point and show that every larger exponent has a finite derivation valid uniformly for nearby clique-size ratios.
Zhipeng Lu, Sichen Wang
Preprint

The Minimax Rate of Denoising Flows on Trees

Minimax Estimation Shape-Constrained Inference Tree Flows
Isotonic regression and mean estimation over a simplex are among the most classical denoising problems under geometric constraints. Chatterjee and Lafferty generalized both to the recovery of a flow on a rooted tree from Gaussian noise, with isotonic regression on a path and the simplex on a star. Their results reach only special trees; on a general tree the minimax risk remained unknown for a decade. We settle the question in full. On every tree with $n$ vertices, at every budget $V$ and noise level $\sigma$, the minimax risk is of order $\min\{V^2H_T,\ \sigma^2k_0\}$, with $H_T$ the diameter and $k_0$ the crossing index of a truncated ancestor profile. A deterministic estimator, an exponentially weighted aggregate over integer states, attains it in $O(n^2\log(n+1))$ arithmetic operations. Least squares at a known budget, the natural convex program for the model, is suboptimal in the worst case by a factor of order $(\log n)^{2/5}$. One functional, the truncated ancestor profile, carries the rate, the estimator, and the least squares comparison. It serves as covering radius, as packing entropy in the positive cone, and as the range of the one-dimensional state behind the exact computation. Two classical theories become one on trees, sharp and computable throughout.
Sichen Wang
Preprint

A Bound Below 2.8 for Tuza's Conjecture

Graph Theory Triangle Packing Extremal Combinatorics
Let $\nu(G)$ be the maximum number of edge-disjoint triangles in a graph $G$ and $\tau(G)$ the minimum number of edges meeting every triangle. Tuza conjectured that $\tau(G)\le 2\nu(G)$. We prove that $\tau(G)\le (165/59)\nu(G)$. The constant $165/59\approx 2.797$ improves the bound $66/23\approx 2.870$ that Haxell proved in 1999. The key observation is that, for a suitable red-blue coloring, the families left over in Haxell’s construction contain every triangle with exactly one red edge. Such a family $\mathcal{F}$ admits an exchange that forces certain red edges to lie in a single triangle once the blue edges of a maximum packing are deleted, which gives $\tau(\mathcal{F})\le (8/3)\nu(\mathcal{F})$.
Sichen Wang
Preprint

The Price of Order in the Logarithmic Method

Data Structures Lower Bounds Write-Optimized Indexes

The logarithmic method is a classical static-to-dynamic transformation: it stores one dynamic ordered set as several immutable static components and rebuilds them by merges. The same component-and-merge discipline underlies write-optimized ordered indexes, where cheap insertions must be reconciled with exact ordered queries. In this paper, we study the insertion-only version after $n$ insertions, over abstract keys, in a strongly materialized merge-stack model with sequential component merges and one forward scan of the live components per query. We bound the product between the total amount of data written during the $n$ insertions and the worst-case amount of data read by a single query, known as the write-read product. The optimal bounds are as follows:

  • Membership and local certificates: $\Theta(n\log^2 n)$.
  • Order and range queries with named keys or endpoints: $\Theta(n\log^3 n)$.
  • Select: $\Theta(n^2)$.

Thus, the logarithmic method does not impose a universal dynamic overhead: under materialized one-way access, the optimum depends on what information the query reveals before the scan starts. This pinpoints the access-model obstruction behind the extra logarithm for exact order and range queries, and the quadratic barrier for select.

Sichen Wang, Zhipeng Lu, Jingbang Chen
Preprint