Isotonic regression in general dimensions

DOI10.1214/18-AOS1753MaRDI QIDQ2328048zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1708.09468, https://projecteuclid.org/euclid.aos/1564797853

zbMATH Keywords

adaptationblock increasing functionsisotonic regressionleast squaressharp oracle inequalitystatistical dimension

Mathematics Subject Classification ID

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

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.

Review text

The article combines empirical processes, convex geometry and combinatorics theory to extend the concept of isotonic regression (a particular form of estimation under shape constrains) to a general number of dimensions. The methodological advances of the paper include quantification of the empirical risk of the least squares isotonic estimator, risk bounds, from both worst case perspective and adaptation point of view, when the dimension is larger than 3, together with a sharp oracle inequality. Both fixed and random designs are included in the study and discussed in contrast to earlier literature results under the same setting. Finally it is revealed that the results established adapt to a strictly (suboptimal) nonparametric rate which similtaneously is optimal when seen from a worst-case perspective.

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

Cites work

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

Cited in

(62)

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

Describes a project that uses

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)