Penalized polygram regression. (English) Zbl 07643159

Summary: We consider a study on regression function estimation over a bounded domain of arbitrary shapes based on triangulation and penalization techniques. A total variation type penalty is imposed to encourage fusion of adjacent triangles, which leads to a partition of the domain consisting of disjointed polygons. The proposed method provides a piecewise linear, and continuous estimator over a data adaptive polygonal partition of the domain. We adopt a coordinate decent algorithm to handle the non-separable structure of the penalty and investigate its convergence property. Regarding the asymptotic results, we establish an oracle type inequality and convergence rate of the proposed estimator. A numerical study is carried out to illustrate the performance of this method. An R software package polygram is available.


62-XX Statistics
Full Text: DOI


[1] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3, 1, 1-122 (2011) · Zbl 1229.90122
[2] Bregman, LM, A relaxation method of finding a common point of convex sets and its application to problems of optimization’, In Soviet Mathematics Doklady, 7, 1578-1581 (1966) · Zbl 0157.50401
[3] Breiman, L., The ii method for estimating multivariate functions from noisy data, Technometrics, 33, 2, 125-143 (1991)
[4] Breiman, L.; Friedman, JH; Olshen, RA; Stone, CJ, Classification and Regression Trees (1984), Belmont, CA: Wadsworth, Belmont, CA
[5] Bunea, F.; Tsybakov, A.; Wegkamp, M., Sparsity oracle inequalities for the lasso, Electronic Journal of Statistics, 1, 169-194 (2007)
[6] Courant, R. et al. (1943). Variational methods for the solution of problems of equilibrium and vibrations. Verlag nicht ermittelbar. · Zbl 0063.00985
[7] De Boor, C. (1978). A practical guide to splines, Volume 27. Springer. · Zbl 0406.41003
[8] Nychka, D., Furrer, R., Paige, J., & Sain, S. (2017). fields: Tools for spatial data. Boulder, CO, USA: University Corporation for Atmospheric Research. R package version 9.8-1.
[9] Franke, R., A critical comparison of some methods for interpolation of scattered data (1979), Naval Postgraduate School Monterey CA: Technical report, Naval Postgraduate School Monterey CA
[10] Friedman, J.; Hastie, T.; Hofling, H.; Tibshirani, R., Pathwise coordinate optimazation, The Annals of Statistics, 1, 2, 302-332 (2007)
[11] Friedman, JH, Multivariate adaptive regression splines, The Annals of Statistics, 19, 1, 1-67 (1991)
[12] Friedman, JH; Silverman, BW, Flexible parsimonious smoothing and additive modeling, Technometrics, 31, 1, 3-21 (1989) · Zbl 0672.65119
[13] Gaines, BR; Kim, J.; Zhou, H., Algorithms for fitting the constrained lasso, Journal of Computational and Graphical Statistics, 27, 4, 861-871 (2018)
[14] Gu, C.; Bates, D.; Chen, Z.; Wahba, G., The computation of gcv functions through householder tridiagonalization with application to the fitting of interaction spline models, SIAM Journal of Matrix Analysis, 10, 457-480 (1989)
[15] Hansen, M. (1994). Extended linear models, multivariate splines, and anova. Ph.D. dissertation.
[16] Hansen, M.; Kooperberg, C.; Sardy, S., Triogram models, Journal of the American Statistical Association, 93, 441, 101-119 (1998)
[17] He, X.; Shi, P., Bivariate tensor-product b-splines in a partly linear model, Journal of Multivariate Analysis, 58, 2, 162-181 (1996)
[18] Huang, JZ, Projection estimation in multiple regression with application to functional anova models, The Annals of Statistics, 26, 1, 242-272 (1998)
[19] Huang, JZ, Asymptotics for polynomial spline regression under weak conditions, Statistics & Probability Letters, 65, 3, 207-216 (2003)
[20] Huang, JZ, Local asymptotics for polynomial spline regression, The Annals of Statistics, 31, 5, 1600-1635 (2003)
[21] James, G.; Witten, D.; Hastie, T.; Tibshirani, R., ISLR: Data for an Introduction to Statistical Learning with Applications in R, R Package Version, 1, 2 (2017)
[22] James, G.M., Paulson, C., & Rusmevichientong, P. (2013). Penalized and constrained regression. Unpublished manuscript, http://www.bcf.usc.edu/ gareth/research/Research.html
[23] Jhong, JH; Koo, JY; Lee, SW, Penalized B-spline estimator for regression functions using total variation penalty, Journal of Statistical Planning and Inference, 184, 77-93 (2017)
[24] Keller, J. M., Gray, M. R., & Givens. J. A. (1985). A fuzzy k-nearest neighbor algorithm. IEEE Transactions on Systems, Man, and Cybernetics SMC-15(4): 580-585.
[25] Koenker, R.; Mizera, I., Penalized triograms: Total variation regularization for bivariate smoothing, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 66, 1, 145-163 (2004) · Zbl 1064.62038
[26] Kooperberg, C., Stone, C.J., & Truong. Y.K. (1995a). The l2 rate of convergence for hazard regression. Scandinavian Journal of Statistics: 143-157 . · Zbl 0839.62050
[27] Kooperberg, C.; Stone, CJ; Truong, YK, Rate of convergence for logspline spectral density estimation, Journal of Time Series Analysis, 16, 4, 389-401 (1995)
[28] Lai, MJ, Multivariate splines for data fitting and approximation, 210-228 (2007), San Antonio: Approximation Theory XII, San Antonio
[29] Lai, MJ; Schumaker, LL, On the approximation power of bivariate splines, Advances in Computational Mathematics, 9, 3-4, 251-279 (1998)
[30] Lai, M. J., & Schumaker, L. L. (2007). Spline functions on triangulations. Cambridge University Press. · Zbl 1185.41001
[31] Lai, MJ; Wang, L., Bivariate penalized splines for regression, Statistica Sinica, 23, 3, 1399-1417 (2013)
[32] Lange, K.; Hunter, DR; Yang, I., Optimization transfer using surrogate objective functions, Journal of Computational and Graphical Statistics, 9, 1, 1-20 (2000)
[33] Meier, L.; Van De Geer, S.; Bühlmann, P., The group lasso for logistic regression, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70, 1, 53-71 (2008)
[34] Ramsay, T., Spline smoothing over difficult regions, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 64, 2, 307-319 (2002)
[35] Rippa, S., Adaptive approximation by piecewise linear polynomials on triangulations of subsets of scattered data, SIAM Journal on Scientific and Statistical Computing, 13, 5, 1123-1141 (1992) · Zbl 0758.65004
[36] Ruppert, D., Selecting the number of knots for penalized splines, Journal of Computational and Graphical Statistics, 11, 4, 735-757 (2002)
[37] Schwarz, G., Estimating the dimension of a model, The Annals of Statistics, 6, 2, 461-464 (1978)
[38] Shewchuk, J.R. (1996), may. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator, In Applied Computational Geometry: Towards Geometric Engineering, eds. Lin, M.C. and D. Manocha, Volume 1148 of Lecture Notes in Computer Science, 203-222. Springer-Verlag. From the First ACM Workshop on Applied Computational Geometry.
[39] S Stone, C.J. (1982). Optimal global rates of convergence for nonparametric regression. The Annals of Statistics: 1040-1053. · Zbl 0511.62048
[40] Stone, CJ, Additive regression and other nonparametric models, The Annals of Statistics, 13, 2, 689-705 (1985)
[41] Stone, CJ, The dimensionality reduction principle for generalized additive models, The Annals of Statistics, 14, 2, 590-606 (1986)
[42] Stone, CJ, The use of polynomial splines and their tensor products in multivariate function estimation, The Annals of Statistics, 22, 1, 118-171 (1994)
[43] Stone, CJ; Hansen, MH; Kooperberg, C.; Truong, YK, Polynomial splines and their tensor products in extended linear modeling: 1994 wald memorial lecture, The Annals of Statistics, 25, 4, 1371-1470 (1997)
[44] Szeliski, R. (2010). Computer vision: algorithms and applications. Springer. · Zbl 1478.68007
[45] Tibshirani, R., Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society, 58, 1, 267-288 (1996)
[46] Tibshirani, R.; Saunders, M., Sparsity and smoothness via the fused lasso, Journal of the Royal Statistical Society, 67, 1, 91-108 (2005)
[47] Tibshirani, RJ; Taylor, J., The solution path of the generalized lasso, The Annals of Statistics, 39, 3, 1335-1371 (2011)
[48] Tseng, P., Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109, 3, 475-494 (2001)
[49] Xiao, L., Asymptotics of bivariate penalised splines, Journal of Nonparametric Statistics, 31, 2, 289-314 (2019) · Zbl 1420.62180
[50] Xiao, L.; Li, Y.; Ruppert, D., Fast bivariate p-splines: The sandwich smoother, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 75, 3, 577-599 (2013) · Zbl 1411.62109
[51] Ye, GB; Xie, X., Split bregman method for large scale fused lasso, Computational Statistics & Data Analysis, 55, 4, 1552-1569 (2011) · Zbl 1328.65048
[52] Yu, D.; Won, JH; Lee, T.; Lim, J.; Yoon, S., High-dimensional fused lasso regression using majorization-minimization and parallel processing, Journal of Computational and Graphical Statistics, 24, 1, 121-153 (2015)
[53] Zou, H.; Hastie, T., Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society, 67, 2, 301-320 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.