Isotonic Regression in Multi-Dimensional Spaces and Graphs
share
In this paper we study minimax and adaptation rates in general isotonic regression. For uniform deterministic and random designs in [0,1]^d with d> 2 and N(0,1) noise, the minimax rate for the ℓ_2 risk is known to be bounded from below by n^-1/d when the unknown mean function f is nondecreasing and its range is bounded by a constant, while the least squares estimator (LSE) is known to nearly achieve the minimax rate up to a factor ( n)^γ where n is sample size, γ = 4 in the lattice design and γ = {9/2, (d^2+d+1)/2 } in the random design. Moreover, the LSE is known to achieve the adaptation rate (K/n)^-2/d{1∨(n/K)}^2γ when f is piecewise constant on K hyperrectangles in a partition of [0,1]^d. Due to the minimax theorem, the LSE is identical on every design point to both the max-min and min-max estimators over all upper and lower sets containing the design point. This motivates our consideration of estimators which lie in-between the max-min and min-max estimators over possibly smaller classes of upper and lower sets, including a subclass of block estimators. Under a q-th moment condition on the noise, we develop ℓ_q risk bounds for such general estimators for isotonic regression on graphs. For uniform deterministic and random designs in [0,1]^d with d> 3, our ℓ_2 risk bound for the block estimator matches the minimax rate n^-1/d when the range of f is bounded and achieves the near parametric adaptation rate (K/n){1∨(n/K)}^d when f is K-piecewise constant. Furthermore, the block estimator possesses the following oracle property in variable selection: When f depends on only a subset S of variables, the ℓ_2 risk of the block estimator automatically achieves up to a poly-logarithmic factor the minimax rate based on the oracular knowledge of S.
READ FULL TEXT