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

arXiv: https://arxiv.org/abs/1903.01395 · HTML: https://mlsanity.com/paper/1903.01395/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2019.

## Built on by (most cited first, 12 of 12)

- [Adaptive debiased machine learning using data-driven model selection techniques](https://mlsanity.com/paper/2307.12544/) (2023)
- [MARS via LASSO](https://mlsanity.com/paper/2111.11694/) (2021)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [Lassoed Tree Boosting](https://mlsanity.com/paper/2205.10697/) (2022)
- [Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps](https://mlsanity.com/paper/2402.14985/) (2024)
- [Highly Adaptive Ridge](https://mlsanity.com/paper/2410.02680/) (2024)
- [A Cross Validation Framework for Signal Denoising with Applications to Trend Filtering, Dyadic CART and Beyond](https://mlsanity.com/paper/2201.02654/) (2022)
- [Spatially Adaptive Online Prediction of Piecewise Regular Functions](https://mlsanity.com/paper/2203.16587/) (2022)
- [Highly Adaptive Principal Component Regression](https://mlsanity.com/paper/2602.10613/) (2026)
- [Brenier Isotonic Regression](https://mlsanity.com/paper/2603.10452/) (2026)
- [Adaptive approximation of monotone functions](https://mlsanity.com/paper/2309.07530/) (2023)
- [Learning What Evaluators Value: A Reliable Approach to Modeling Evaluator Preferences](https://mlsanity.com/paper/2605.16615/) (2026)

## Abstract (arXiv)

We consider the problem of nonparametric regression when the covariate is d-dimensional, where d ≥ 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.