The Minimax Rate of Denoising Flows on Trees
Abstract
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 σ, the minimax risk is of order min{V2HT, σ2k0}, with HT the diameter and k0 the crossing index of a truncated ancestor profile. A deterministic estimator, an exponentially weighted aggregate over integer states, attains it in O(n2log(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.
Related
- A statistical theory for blind denoising: minimax estimation of the noise level from a single sample
- Poisson Image Denoising Using Minimax Concave and Reweighted ℓ1 Penalties: Nonblind and Blind Approaches
- Nonparametric hazard rate estimation with associated kernels and minimax bandwidth choice
- On the minimax-rate optimality of approximate Bayesian computation in nonparametric problems
- Near Minimax Rate for Quantile Distributional Reinforcement Learning
BibTeX
@misc{wang2026minimax,
title = {{The Minimax Rate of Denoising Flows on Trees}},
author = {Sichen Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14091},
eprint = {2609.14091},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14091},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Minimax Rate of Denoising Flows on Trees
AU - Sichen Wang
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.14091
UR - https://arxiv.org/abs/2609.14091
AB - 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 σ, the minimax risk is of order min{V^2H_T, σ^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^2log(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.
ER -