Smoothing Splines Approximation Using Hilbert Curve Basis Selection
针对大样本非参数回归中平滑样条计算量大的问题，提出一种自适应于预测变量未知密度函数的基选择算法，在保证收敛速度的同时大幅降低计算成本。
Smoothing splines have been used pervasively in nonparametric regressions. However, the computational burden of smoothing splines is significant when the sample size n is large. When the number of predictors d≥2, the computational cost for smoothing splines is at the order of O(n3) using the standard approach. Many methods have been developed to approximate smoothing spline estimators by using q basis functions instead of n ones, resulting in a computational cost of the order O(nq2). These methods are called the basis selection methods. Despite algorithmic benefits, most of the basis selection methods require the assumption that the sample is uniformly distributed on a hypercube. These methods may have deteriorating performance when such an assumption is not met. To overcome the obstacle, we develop an efficient algorithm that is adaptive to the unknown probability density function of the predictors. Theoretically, we show the proposed estimator has the same convergence rate as the full-basis estimator when q is roughly at the order of O[n2d/{(pr+1)(d+2)}], where p∈[1,2] and r≈4 are some constants depend on the type of the spline. Numerical studies on various synthetic datasets demonstrate the superior performance of the proposed estimator in comparison with mainstream competitors. Supplementary files for this article are available online.