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

Abstract

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 $\epsilon$-graph rather than a $K$-NN graph, and contrast this with the $K$-NN fused lasso.

References in corpus (10)

• Local polynomial regression on unknown manifolds
• Modular proximal optimization for multidimensional total-variation regularization
• Rates of Convergence for Nearest Neighbor Classification
• k-NN Regression Adapts to Local Intrinsic Dimension
• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Hitting and commute times in large graphs are often misleading
• Randomized partition trees for exact nearest neighbor search
• Analysis of k-Nearest Neighbor Distances with Application to Entropy Estimation
• Escaping the curse of dimensionality with a tree-based regressor

Cited by in corpus (1)

• On Structured Filtering-Clustering: Global Error Bound and Optimal First-Order Algorithms