Isotonic regression in general dimensions

DOI10.1214/18-AOS1753zbMATH Open1437.62124arXiv1708.09468MaRDI QIDQ2328048FDOQ2328048

Authors: Qiyang Han, Tengyao Wang, Sabyasachi Chatterjee, Richard Samworth 

Publication date: 9 October 2019

Published in: The Annals of Statistics (Search for Journal in Brave)

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^{-min2/(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 $dleq2$. 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.

Full work available at URL: https://arxiv.org/abs/1708.09468

Recommendations

• Isotonic regression in multi-dimensional spaces and graphs
• On risk bounds in isotonic and other shape restricted regression problems
• On estimation of isotonic piecewise constant signals
• Sharp oracle inequalities for least squares estimators in shape restricted regression
• Distribution-free properties of isotonic regression

zbMATH Keywords

adaptationleast squaresisotonic regressionsharp oracle inequalitystatistical dimensionblock increasing functions

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Nonparametric regression and quantile regression (62G08) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Generalized additive and index models with shape constraints
• Weak convergence and empirical processes. With applications to statistics
• On the degrees of freedom in shape-restricted regression.
• Title not available (Why is that?)
• Concentration inequalities. A nonasymptotic theory of independence
• New concentration inequalities in product spaces
• Isotonic regression for multiple independent variables
• The Reduced Monotonic Regression Method
• An algorithm for isotonic regression for two or more independent variables
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Maximum Likelihood Estimates of Monotone Parameters
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient regularized isotonic regression with application to gene-gene interaction search
• Nonparametric estimation under shape constraints. Estimators, algorithms and asymptotics
• An Algorithm for Restricted Least Squares Regression
• Entropy estimate for high-dimensional monotonic functions
• Living on the edge: phase transitions in convex programs with random data
• A user's guide to measure theoretic probability
• Rates of convergence for minimum contrast estimators
• Hellinger-consistency of certain nonparametric maximum likelihood estimators
• Global rates of convergence in log-concave density estimation
• Global risk bounds and adaptation in univariate convex regression
• Information-theoretic determination of minimax rates of convergence
• Risk bounds in isotonic regression
• On risk bounds in isotonic and other shape restricted regression problems
• A new perspective on least squares under convex constraint
• Additive isotone regression
• Estimating a regression function
• The surprising mathematics of longest increasing subsequences
• Sharp oracle inequalities for least squares estimators in shape restricted regression
• On the \(\mathbb L_p\)-error of monotonicity constrained estimators
• Empirical entropy, minimax regret and minimax risk
• Monotone nonparametric regression with random design
• Contraction and uniform convergence of isotonic regression
• Adaptive risk bounds in unimodal regression
• Title not available (Why is that?)
• Isotonic regression in general dimensions
• On matrix estimation under monotonicity constraints
• Adaptation in log-concave density estimation

Cited In (51)

• Frame-constrained total variation regularization for white noise regression
• Local continuity of log-concave projection, with applications to estimation under model misspecification
• Coverage of credible intervals in Bayesian multivariate isotonic regression
• Guaranteed Functional Tensor Singular Value Decomposition
• Local convergence rates of the nonparametric least squares estimator with applications to transfer learning
• Uncoupled isotonic regression via minimum Wasserstein deconvolution
• Editorial: Special issue on ``Nonparametric inference under shape constraints
• Limit theory in monotone function estimation
• Nonparametric shape-restricted regression
• Suboptimality of constrained least squares and improvements via non-linear predictors
• Isotonic Distributional Regression
• Limit distribution theory for block estimators in multiple isotonic regression
• Towards optimal estimation of bivariate isotonic matrices with unknown permutations
• Fused Lasso nearly-isotonic signal approximation in general dimensions
• High-dimensional asymptotics of likelihood ratio tests in the Gaussian sequence model under convex constraints
• On least squares estimation under heteroscedastic and heavy-tailed errors
• Adaptation in multivariate log-concave density estimation
• Methods for estimation of convex sets
• Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation
• Algorithm AS 257: Isotonic Regression for Umbrella Orderings
• A new computational framework for log-concave density estimation
• Isotonic regression in multi-dimensional spaces and graphs
• A study on the least squares estimator of multivariate isotonic regression function
• Isotonic regression for multiple independent variables
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Empirical variance minimization with applications in variance reduction and optimal control
• Estimating piecewise monotone signals
• Isotonic regression in general dimensions
• Adaptive confidence sets in shape restricted regression
• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
• Title not available (Why is that?)
• A geometrical approach to iterative isotone regression
• The bias of isotonic regression
• On estimation of isotonic piecewise constant signals
• Partially linear monotone methods with automatic variable selection and monotonicity direction discovery
• Confidence intervals for multiple isotonic regression and other monotone models
• Set structured global empirical risk minimizers are rate optimal in general dimensions
• Sharp asymptotics for isotonic regression
• Title not available (Why is that?)
• Approximation, characterization, and continuity of multivariate monotonic regression functions
• Risk bounds in isotonic regression
• Title not available (Why is that?)
• Posterior contraction and testing for multivariate isotonic regression
• A dynamic programming approach for generalized nearly isotonic optimization
• Characterizing the optimal solutions to the isotonic regression problem for identifiable functionals
• The limiting behavior of isotonic and convex regression estimators when the model is misspecified
• An isotonic regression problem for infinite-dimensional parameters
• Sharp oracle inequalities for least squares estimators in shape restricted regression
• Isotonic regression meets Lasso
• The asymptotic distribution of the isotonic regression estimator over a general countable pre-ordered set
• Characterization of the least squares estimator: mis-specified multivariate isotonic regression model with dependent errors

Uses Software

• scar

This page was built for publication: Isotonic regression in general dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328048)