= Minimax rate for isotonic sequence estimation
For a concrete <isotonic regression> model, observe $Y_i=\theta_i+\varepsilon_i$ with <independent> <Gaussian distribution> errors of <expected value> zero and fixed <variance> $\sigma^2>0$. Let $\Theta_V=\{0\leq\theta_1\leq\cdots\leq\theta_n\leq V\}$ for fixed $V>0$, and use normalized <squared-error loss> $n^{-1}\sum_i(\widehat\theta_i-\theta_i)^2$. The <minimax risk> over $\Theta_V$ has order
$$
\inf_{\widehat\theta}\sup_{\theta\in\Theta_V}\mathbb E_\theta\frac1n\|\widehat\theta-\theta\|_2^2\asymp
\left(\frac{\sigma^2V}{n}\right)^{2/3}
$$
as $n\to\infty$ with $V,\sigma$ fixed. This states the model and loss behind the shorthand rate $n^{-2/3}$.
The <isotonic least squares estimator> satisfies an upper bound of order $(\sigma^2V/n)^{2/3}+\sigma^2\log(en)/n$. Locally increasing sequences supply matching lower bounds for the first term. The primary analysis also shows why a worst-case rate does not describe every signal: when the true sequence has few constant blocks, the risk can be substantially smaller.<Improved Risk Bounds in Isotonic Regression by Sabyasachi Chatterjee and others>[2013 preprint, Introduction, equations (5)–(6), and Section 4.1, Theorem 4.3]{ref}
A heuristic for the exponent is to approximate a changing monotone signal by $k$ blocks: squared approximation error scales as $(V/k)^2$, while estimating $k$ block levels costs approximately $\sigma^2k/n$. Balancing these gives $k\asymp(nV^2/\sigma^2)^{1/3}$ and risk $(\sigma^2V/n)^{2/3}$. This balance motivates the rate; it does not replace the lower-bound argument. Uniformly constant signals or a variation bound shrinking with $n$ require their own regime analysis.
Back to article page
