Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation

Abstract

We consider the problem of nonparametric regression when the covariate is $d$-dimensional, where $d\ge 1$. In this paper we introduce and study two nonparametric least squares estimators (LSEs) in this setting---the entirely monotonic LSE and the constrained Hardy-Krause variation LSE. We show that these two LSEs are natural generalizations of univariate isotonic regression and univariate total variation denoising, respectively, to multiple dimensions. We discuss the characterization and computation of these two LSEs obtained from $n$ data points. We provide a detailed study of their risk properties under the squared error loss and fixed uniform lattice design. We show that the finite sample risk of these LSEs is always bounded from above by $n^{-2/3}$ modulo logarithmic factors depending on $d$; thus these nonparametric LSEs avoid the curse of dimensionality to some extent. We also prove nearly matching minimax lower bounds. Further, we illustrate that these LSEs are particularly useful in fitting rectangular piecewise constant functions. Specifically, we show that the risk of the entirely monotonic LSE is almost parametric (at most $1/n$ up to logarithmic factors) when the true function is well-approximable by a rectangular piecewise constant entirely monotone function with not too many constant pieces. A similar result is also shown to hold for the constrained Hardy-Krause variation LSE for a simple subclass of rectangular piecewise constant functions. We believe that the proposed LSEs yield a novel approach to estimating multivariate functions using convex optimization that avoid the curse of dimensionality to some extent.

References in corpus (16)

• On the Prediction Performance of the Lasso
• Asymptotics for minimisers of convex processes
• On risk bounds in isotonic and other shape restricted regression problems
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• A new perspective on least squares under convex constraint
• Optimal rates for total variation denoising
• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• Adaptive Risk Bounds in Univariate Total Variation Denoising and Trend Filtering
• Synthesis and analysis in total variation regularization
• Isotonic Regression in Multi-Dimensional Spaces and Graphs
• Optimistic lower bounds for convex regularized least-squares
• Uniform Consistency of the Highly Adaptive Lasso Estimator of Infinite Dimensional Parameters
• A note on the approximate admissibility of regularized estimators in the Gaussian sequence model
• Element-wise estimation error of a total variation regularized estimator for change point detection
• Frame-constrained Total Variation Regularization for White Noise Regression
• Finite Sample Inference for Targeted Learning

Cited by in corpus (5)

• Fast rates for empirical risk minimization over càdlàg functions with bounded sectional variation norm
• Confidence intervals for multiple isotonic regression and other monotone models
• Sequential causal inference in a single world of connected units
• Logistic regression with total variation regularization
• Frame-constrained Total Variation Regularization for White Noise Regression