Penalized polygram regression. (English) Zbl 07643159

Jhong, Jae-Hwan; Bak, Kwan-Young; Koo, Ja-Yong

J. Korean Stat. Soc. 51, No. 4, 1161-1192 (2022).

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.

MSC:

62-XX

Statistics

Keywords:

barycentric coordinates; coordinate descent algorithm; minimaxity; polygonal partitions; triangulation

Software:

polygram; R; ISLR; Triangle

References:

[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)