# Adaptive Non-Parametric Regression With the K-NN Fused Lasso

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2018.

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

- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [Rates of Convergence for Regression with the Graph Poly-Laplacian](https://mlsanity.com/paper/2209.02305/) (2022)
- [The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data](https://mlsanity.com/paper/2212.14514/) (2022)

## Abstract (arXiv)

The fused lasso, also known as total-variation denoising, is a locally-adaptive function estimator over a regular grid of design points. In this paper, we extend the fused lasso to settings in which the points do not occur on a regular grid, leading to an approach for non-parametric regression. This approach, which we call the K-nearest neighbors (K-NN) fused lasso, involves (i) computing the K-NN graph of the design points; and (ii) performing the fused lasso over this K-NN graph. We show that this procedure has a number of theoretical advantages over competing approaches: specifically, it inherits local adaptivity from its connection to the fused lasso, and it inherits manifold adaptivity from its connection to the K-NN approach. We show that excellent results are obtained in a simulation study and on an application to flu data. For completeness, we also study an estimator that makes use of an ε-graph rather than a K-NN graph, and contrast this with the K-NN fused lasso.