# The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 59 references that are in the map.
- First posted on arXiv 30 Dec 2022.

## Builds on (most cited first, 10 of 10)

- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Continuum limit of total variation on point clouds](https://mlsanity.com/paper/1403.6355/) (2014)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Efficient Implementations of the Generalized Lasso Dual Path Algorithm](https://mlsanity.com/paper/1405.3222/) (2014)
- [Divided Differences, Falling Factorials, and Discrete Splines: Another Look at Trend Filtering and Related Problems](https://mlsanity.com/paper/2003.03886/) (2020)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [Adaptive Non-Parametric Regression With the K-NN Fused Lasso](https://mlsanity.com/paper/1807.11641/) (2018)

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

- [Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes](https://mlsanity.com/paper/2406.06838/) (2024)
- [Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps](https://mlsanity.com/paper/2402.14985/) (2024)
- [Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations](https://mlsanity.com/paper/2407.08494/) (2024)

## Abstract (arXiv)

We consider the problem of estimating a multivariate function f0 of bounded variation (BV), from noisy observations yi = f0(xi) + zi made at random design points xi ∈ ℝd, i=1,ldots,n. We study an estimator that forms the Voronoi diagram of the design points, and then solves an optimization problem that regularizes according to a certain discrete notion of total variation (TV): the sum of weighted absolute differences of parameters θi,θj (which estimate the function values f0(xi),f0(xj)) at all neighboring cells i,j in the Voronoi diagram. This is seen to be equivalent to a variational optimization problem that regularizes according to the usual continuum (measure-theoretic) notion of TV, once we restrict the domain to functions that are piecewise constant over the Voronoi diagram. The regression estimator under consideration hence performs (shrunken) local averaging over adaptively formed unions of Voronoi cells, and we refer to it as the Voronoigram, following the ideas in Koenker (2005), and drawing inspiration from Tukey's regressogram (Tukey, 1961). Our contributions in this paper span both the conceptual and theoretical frontiers: we discuss some of the unique properties of the Voronoigram in comparison to TV-regularized estimators that use other graph-based discretizations; we derive the asymptotic limit of the Voronoi TV functional; and we prove that the Voronoigram is minimax rate optimal (up to log factors) for estimating BV functions that are essentially bounded.