{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T02:08:13Z","timestamp":1785550093185,"version":"3.56.0"},"reference-count":59,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T00:00:00Z","timestamp":1580256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Simons InvestigatorAward in Mathematical Modeling of Living Systems"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,1]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>The fused lasso, also known as total-variation denoising, is a locally adaptive function estimator over a regular grid of design points. In this article, we extend the fused lasso to settings in which the points do not occur on a regular grid, leading to a method for nonparametric regression. This approach, which we call the $K$-nearest-neighbours fused lasso, involves computing the $K$-nearest-neighbours graph of the design points and then performing the fused lasso over this graph. We show that this procedure has a number of theoretical advantages over competing methods: specifically, it inherits local adaptivity from its connection to the fused lasso, and it inherits manifold adaptivity from its connection to the $K$-nearest-neighbours approach. In a simulation study and an application to flu data, we show that excellent results are obtained. For completeness, we also study an estimator that makes use of an $\\epsilon$-graph rather than a $K$-nearest-neighbours graph and contrast it with the $K$-nearest-neighbours fused lasso.<\/jats:p>","DOI":"10.1093\/biomet\/asz071","type":"journal-article","created":{"date-parts":[[2019,11,9]],"date-time":"2019-11-09T20:09:05Z","timestamp":1573330145000},"page":"293-310","source":"Crossref","is-referenced-by-count":20,"title":["Adaptive nonparametric regression with the K-nearest neighbour fused lasso"],"prefix":"10.1093","volume":"107","author":[{"given":"Oscar Hernan","family":"Madrid Padilla","sequence":"first","affiliation":[{"name":"Department of Statistics, University of California, 520 Portola Plaza, Los Angeles, California, U.S.A"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Sharpnack","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of California, One Shields Avenue, Davis, California, U.S.A"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanzhen","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Information Systems, Business Statistics and Operations Management, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniela M","family":"Witten","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Washington, Seattle, Washington, U.S.A"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,1,29]]},"reference":[{"key":"2020071623423803200_B1","first-page":"543","article-title":"Density-preserving quantization with application to graph downsampling","volume":"35","author":"Alamgir,","year":"2014","journal-title":"Proc. Mach. Learn. Res."},{"key":"2020071623423803200_B2","article-title":"Modular proximal optimization for multidimensional total-variation regularization","author":"Barbero,","year":"2017","journal-title":"arXiv: 1411.0589v3"},{"key":"2020071623423803200_B3","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1214\/074921707000000148","volume-title":"Complex Datasets and Inverse Problems","author":"Bickel,","year":"2007"},{"key":"2020071623423803200_B4","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","article-title":"An experimental comparison of min-cut\/max-flow algorithms for energy minimization in vision","volume":"26","author":"Boykov,","year":"2004","journal-title":"IEEE Trans. Pat. Anal. Mach. Intel."},{"key":"2020071623423803200_B5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random forests","volume":"45","author":"Breiman,","year":"2001","journal-title":"Mach. Learn."},{"key":"2020071623423803200_B6","volume-title":"Classification and Regression Trees","author":"Breiman,","year":"1984"},{"key":"2020071623423803200_B7","first-page":"179","article-title":"Faster rates in regression via active learning","volume-title":"Proc. 18th Int. Conf. Neural Information Processing Systems","author":"Castro,","year":"2005"},{"key":"2020071623423803200_B8","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/s11263-009-0238-9","article-title":"On total variation minimization and surface evolution using parametric maximum flows","volume":"84","author":"Chambolle,","year":"2009","journal-title":"Int. J. Comp. Vis."},{"key":"2020071623423803200_B9","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","article-title":"A first-order primal-dual algorithm for convex problems with applications to imaging","volume":"40","author":"Chambolle,","year":"2011","journal-title":"J. Math. Imag. Vis."},{"key":"2020071623423803200_B10","first-page":"3437","article-title":"Rates of convergence for nearest neighbor classification","volume-title":"Proc. 27th Int. Conf. Neural Information Processing Systems (NIPS\u201914)","author":"Chaudhuri,","year":"2014"},{"key":"2020071623423803200_B11","doi-asserted-by":"crossref","first-page":"1421","DOI":"10.1080\/01621459.2013.827984","article-title":"Local linear regression on manifolds and its geometric interpretation","volume":"108","author":"Cheng,","year":"2013","journal-title":"J. Am. Statist. Assoc."},{"key":"2020071623423803200_B12","first-page":"18.1","article-title":"Consistency of nearest neighbor classification under selective sampling","volume":"23","author":"Dasgupta,","year":"2012","journal-title":"Proc. Mach. Learn. Res."},{"key":"2020071623423803200_B13","first-page":"2555","article-title":"Optimal rates for k-NN density and mode estimation","volume-title":"Advances in Neural Information Processing Systems 27 (NIPS\u201914)","author":"Dasgupta,","year":"2014"},{"key":"2020071623423803200_B14","first-page":"317","article-title":"Randomized partition trees for exact nearest neighbor search","volume":"30","author":"Dasgupta,","year":"2013","journal-title":"JMLR Workshop Conf. Proc."},{"key":"2020071623423803200_B15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aos\/996986501","article-title":"Local extremes, runs, strings and multiresolution","volume":"29","author":"Davies,","year":"2001","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B16","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1214\/aos\/1024691081","article-title":"Minimax estimation via wavelet shrinkage","volume":"26","author":"Donoho,","year":"1998","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/BFb0086566","article-title":"Splines minimizing rotation-invariant semi-norms in Sobolev spaces","volume-title":"Constructive Theory of Functions of Several Variables","author":"Duchon,","year":"1977"},{"key":"2020071623423803200_B18","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.1109\/TIP.2008.924284","article-title":"Nonlocal discrete regularization on weighted graphs: A framework for image and manifold processing","volume":"17","author":"Elmoataz,","year":"2008","journal-title":"IEEE Trans. Image Proces."},{"key":"2020071623423803200_B19","doi-asserted-by":"crossref","first-page":"1853","DOI":"10.1137\/130929886","article-title":"Regularized discrete optimal transport","volume":"7","author":"Ferradans,","year":"2014","journal-title":"SIAM J. Imag. Sci."},{"key":"2020071623423803200_B20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aos\/1176347963","article-title":"Multivariate adaptive regression splines","volume":"19","author":"Friedman,","year":"1991","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/355744.355745","article-title":"An algorithm for finding best matches in logarithmic expected time","volume":"3","author":"Friedman,","year":"1977","journal-title":"ACM Trans. Math. Software"},{"key":"2020071623423803200_B22","article-title":"Adaptive risk bounds in univariate total variation and trend filtering","author":"Guntuboyina,","year":"2018","journal-title":"arXiv: 1702.05113v2"},{"key":"2020071623423803200_B23","volume-title":"A Distribution-Free Theory of Nonparametric Regression","author":"Gy\u00f6rfi,","year":"2006"},{"key":"2020071623423803200_B24","volume-title":"Neural Network Design","author":"Hagan,","year":"1996"},{"key":"2020071623423803200_B25","volume-title":"Wavelets, Approximation, and Statistical Applications, vol. 129 of Lecture Notes in Statistics","author":"H\u00e4rdle,","year":"2012"},{"key":"2020071623423803200_B26","doi-asserted-by":"crossref","first-page":"1301","DOI":"10.1016\/j.cageo.2007.05.001","article-title":"About regression-kriging: From equations to case studies","volume":"33","author":"Hengl,","year":"2007","journal-title":"Comp. Geosci."},{"key":"2020071623423803200_B27","doi-asserted-by":"crossref","first-page":"984","DOI":"10.1198\/jcgs.2010.09208","article-title":"A path algorithm for the fused lasso signal approximator","volume":"19","author":"Hoefling,","year":"2010","journal-title":"J. Comp. Graph. Statist."},{"key":"2020071623423803200_B28","first-page":"1115","article-title":"Optimal rates for total variation denoising","volume":"29","author":"Hutter,","year":"2016","journal-title":"Proc. Mach. Learn. Res."},{"key":"2020071623423803200_B29","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1080\/10618600.2012.681238","article-title":"A dynamic programming algorithm for the fused lasso and l0-segmentation","volume":"22","author":"Johnson,","year":"2013","journal-title":"J. Comp. Graph. Statist."},{"key":"2020071623423803200_B30","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1137\/070690274","article-title":"$\\ell_1$ trend filtering","volume":"51","author":"Kim,","year":"2009","journal-title":"SIAM Rev."},{"key":"2020071623423803200_B31","first-page":"856","article-title":"Active nearest-neighbor learning in metric spaces","volume-title":"Proc. 30th Int. Conf. Neural Information Processing Systems (NIPS\u201916)","author":"Kontorovich,","year":"2016"},{"key":"2020071623423803200_B32","article-title":"Escaping the curse of dimensionality with a tree-based regressor","author":"Kpotufe,","year":"2009","journal-title":"arXiv: 0902.3453"},{"key":"2020071623423803200_B33","first-page":"729","article-title":"$k$-NN regression adapts to local intrinsic dimension","volume-title":"Proc. 24th Int. Conf. Neural Information Processing Systems (NIPS\u201911)","author":"Kpotufe,","year":"2011"},{"key":"2020071623423803200_B34","doi-asserted-by":"crossref","first-page":"1496","DOI":"10.1016\/j.jcss.2012.01.002","article-title":"A tree-based regressor that adapts to intrinsic dimension","volume":"78","author":"Kpotufe,","year":"2012","journal-title":"J. Comp. Syst. Sci."},{"key":"2020071623423803200_B35","first-page":"1384","article-title":"Cut pursuit: Fast algorithms to learn piecewise constant functions on general weighted graphs","volume-title":"Proc. 19th International Conference on Artificial Intelligence and Statistics","author":"Landrieu,","year":"2016"},{"key":"2020071623423803200_B36","first-page":"6887","article-title":"A sharp error analysis for the fused lasso, with application to approximate changepoint screening","volume-title":"Proc. 31st Int. Conf. Neural Information Processing Systems (NIPS\u201917)","author":"Lin,","year":"2017"},{"key":"2020071623423803200_B37","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1214\/aos\/1034276635","article-title":"Locally adaptive regression splines","volume":"25","author":"Mammen,","year":"1997","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/256292.256294","article-title":"Separators for sphere-packings and nearest neighbor graphs","volume":"44","author":"Miller,","year":"1997","journal-title":"J. Assoc. Comp. Mach"},{"key":"2020071623423803200_B39","doi-asserted-by":"crossref","first-page":"4517","DOI":"10.1214\/18-EJS1519","article-title":"On the total variation regularized estimator over a class of tree graphs","volume":"12","author":"Ortelli,","year":"2018","journal-title":"Electron. J. Statist."},{"key":"2020071623423803200_B40","first-page":"1","article-title":"The DFS fused lasso: Linear-time denoising over general graphs","volume":"18","author":"Padilla,","year":"2018","journal-title":"J. Comp. Graph. Statist."},{"key":"2020071623423803200_B41","first-page":"3240","article-title":"Convex regression with interpretable sharp partitions","volume":"17","author":"Petersen,","year":"2016","journal-title":"J. Comp. Graph. Statist."},{"key":"2020071623423803200_B42","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1080\/10618600.2015.1073155","article-title":"Fused lasso additive model","volume":"25","author":"Petersen,","year":"2016","journal-title":"J. Comp. Graph. Statist."},{"key":"2020071623423803200_B43","volume-title":"R: A Language and Environment for Statistical Computing","year":"2020"},{"key":"2020071623423803200_B44","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0167-2789(92)90242-F","article-title":"Nonlinear total variation based noise removal algorithms","volume":"60","author":"Rudin,","year":"1992","journal-title":"Physica D"},{"key":"2020071623423803200_B45","article-title":"Additive models with trend filtering","author":"Sadhanala,","year":"2018","journal-title":"arXiv: 1702.05037v4"},{"key":"2020071623423803200_B46","first-page":"5796","article-title":"Higher-order total variation classes on grids: Minimax theory and trend filtering methods","volume-title":"Proc. 31st Int. Conf. Neural Information Processing Systems (NIPS\u201917)","author":"Sadhanala,","year":"2017"},{"key":"2020071623423803200_B47","first-page":"3513","article-title":"Total variation classes beyond 1d: Minimax rates, and the limitations of linear smoothers","volume-title":"Proc. 30th Int. Conf. Neural Information Processing Systems (NIPS\u201916)","author":"Sadhanala,","year":"2016"},{"key":"2020071623423803200_B48","article-title":"Analysis of k-nearest neighbor distances with application to entropy estimation","author":"Singh,","year":"2016","journal-title":"arXiv: 1603.08578v2"},{"key":"2020071623423803200_B49","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1214\/aos\/1176343886","article-title":"Consistent nonparametric regression","volume":"5","author":"Stone,","year":"1977","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B50","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1111\/j.1467-9868.2005.00490.x","article-title":"Sparsity and smoothness via the fused lasso","volume":"67","author":"Tibshirani,","year":"2005","journal-title":"J. R. Statist. Soc"},{"key":"2020071623423803200_B51","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1214\/13-AOS1189","article-title":"Adaptive piecewise polynomial estimation via trend filtering","volume":"42","author":"Tibshirani,","year":"2014","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B52","doi-asserted-by":"crossref","first-page":"1335","DOI":"10.1214\/11-AOS878","article-title":"The solution path of the generalized lasso","volume":"39","author":"Tibshirani,","year":"2011","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B53","first-page":"1751","article-title":"Hitting and commute times in large graphs are often misleading","volume":"15","author":"Von Luxburg,","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"2020071623423803200_B54","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1080\/01621459.2017.1319839","article-title":"Estimation and inference of heterogeneous treatment effects using random forests","volume":"113","author":"Wager,","year":"2018","journal-title":"J. Am. Statist. Assoc."},{"key":"2020071623423803200_B55","first-page":"1","article-title":"Trend filtering on graphs","volume":"17","author":"Wang,","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"2020071623423803200_B56","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1214\/15-AOS1390","article-title":"Bayesian manifold regression","volume":"44","author":"Yang,","year":"2016","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B57","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1214\/14-AOS1289","article-title":"Minimax-optimal nonparametric regression in high dimensions","volume":"43","author":"Yang,","year":"2015","journal-title":"Ann. Statist."},{"key":"2020071623423803200_B58","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/2247596.2247602","article-title":"Efficient parallel kNN joins for large data in MapReduce","volume-title":"Proc. 15th Int. Conf. Extending Database Technology","author":"Zhang,","year":"2012"},{"key":"2020071623423803200_B59","volume-title":"Weakly Differentiable Functions: Sobolev Spaces and Functions of Bounded Variation","author":"Ziemer,","year":"2012"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/biomet\/article-pdf\/107\/2\/293\/33218075\/asz071.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/biomet\/article-pdf\/107\/2\/293\/33218075\/asz071.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T02:00:42Z","timestamp":1611885642000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/107\/2\/293\/5717457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,29]]},"references-count":59,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,1,29]]},"published-print":{"date-parts":[[2020,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asz071","relation":{},"ISSN":["0006-3444","1464-3510"],"issn-type":[{"value":"0006-3444","type":"print"},{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,6]]},"published":{"date-parts":[[2020,1,29]]}}}