mlsanityData to 7 Oct 2026

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

arXiv 2212.14514 ↗First posted 30 Dec 2022stat.ML cs.LG math.STcited by 3

Not on the map. Why?

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.

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

Builds on

10 of 59 references.

References · 10

  1. 2013Adaptive piecewise polynomial estimation via trend filteringcited by 47
  2. 2014Trend Filtering on Graphscited by 45
  3. 2014Continuum limit of total variation on point cloudscited by 24
  4. 2016Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smootherscited by 20
  5. 2021Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphscited by 13
  6. 2014Efficient Implementations of the Generalized Lasso Dual Path Algorithmcited by 11
  7. 2020Divided Differences, Falling Factorials, and Discrete Splines: Another Look at Trend Filtering and Related Problemscited by 6
  8. 2021Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphscited by 5
  9. 2021Multivariate Trend Filtering for Lattice Datacited by 4
  10. 2018Adaptive Non-Parametric Regression With the K-NN Fused Lassocited by 3

Built on by

Cited by year

Citing papers per year: 2024: 3.

3 papers.

  1. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  2. 2024Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmapscited by 2
  3. 2024Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectationscited by 1