Isotonic regression in general dimensions
Authors
Han, Qiyang
Wang, Tengyao
Chatterjee, Sabyasachi
Samworth, RJ
Publication Date
2019-08-03Journal Title
Annals of Statistics
ISSN
0090-5364
Publisher
Institute of Mathematical Statistics
Volume
47
Issue
5
Pages
2440-2471
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Han, Q., Wang, T., Chatterjee, S., & Samworth, R. (2019). Isotonic regression in general dimensions. Annals of Statistics, 47 (5), 2440-2471. https://doi.org/10.1214/18-AOS1753
Abstract
We study the least squares regression function estimator over the class of real-valued functions on $[0,1]^d$ that are increasing in each coordinate. For uniformly bounded signals and with a fixed, cubic lattice design, we establish that the estimator achieves the minimax rate of order $n^{-\min\{2/(d+2),1/d\}}$ in the empirical $L_2$ loss, up to poly-logarithmic factors. Further, we prove a sharp oracle inequality, which reveals in particular that when the true regression function is piecewise constant on $k$ hyperrectangles, the least squares estimator enjoys a faster, adaptive rate of convergence of $(k/n)^{\min(1,2/d)}$, again up to poly-logarithmic factors. Previous results are confined to the case $d \leq 2$. Finally, we establish corresponding bounds (which are new even in the case $d=2$) in the more challenging random design setting. There are two surprising features of these results: first, they demonstrate that it is possible for a global empirical risk minimisation procedure to be rate optimal up to poly-logarithmic factors even when the corresponding entropy integral for the function class diverges rapidly; second, they indicate that the adaptation rate for shape-constrained estimators can be strictly worse than the parametric rate.
Sponsorship
The research of the first author is supported in part by NSF Grant DMS-1566514. The research of the second and fourth authors is supported by EPSRC fellowship EP/J017213/1 and a grant from the Leverhulme Trust RG81761.
Funder references
Engineering and Physical Sciences Research Council (EP/J017213/1)
Leverhulme Trust (PLP-2014-353)
Engineering and Physical Sciences Research Council (EP/N031938/1)
Engineering and Physical Sciences Research Council (EP/P031447/1)
Embargo Lift Date
2100-01-01
Identifiers
External DOI: https://doi.org/10.1214/18-AOS1753
This record's URL: https://www.repository.cam.ac.uk/handle/1810/287832
Rights
All rights reserved
Licence:
http://www.rioxx.net/licenses/all-rights-reserved
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk