More Like this

1. Distributed Generalized Cross-Validation for Divide-and-Conquer Kernel Ridge Regression and Its Asymptotic Optimality

   Xu, G.; Shang, Z.; Cheng, G. (May 2019, Journal of computational and graphical statistics)

   Tuning parameter selection is of critical importance for kernel ridge regression. To date, a data-driven tuning method for divide-and-conquer kernel ridge regression (d-KRR) has been lacking in the literature, which limits the applicability of d-KRR for large datasets. In this article, by modifying the generalized cross-validation (GCV) score, we propose a distributed generalized cross-validation (dGCV) as a data-driven tool for selecting the tuning parameters in d-KRR. Not only the proposed dGCV is computationally scalable for massive datasets, it is also shown, under mild conditions, to be asymptotically optimal in the sense that minimizing the dGCV score is equivalent to minimizing the true global conditional empirical loss of the averaged function estimator, extending the existing optimality results of GCV to the divide-and-conquer framework. Supplemental materials for this article are available online. 

   more » « less
2. Optimal Tuning for Divide-and-conquer Kernel Ridge Regression with Massive Data

   Xu, G.; Shang, Z.; Cheng, G. (January 2018, The Thirty-fifth International Conference on Machine Learning)

   Divide-and-conquer is a powerful approach for large and massive data analysis. In the nonparameteric regression setting, although various theoretical frameworks have been established to achieve optimality in estimation or hypothesis testing, how to choose the tuning parameter in a practically effective way is still an open problem. In this paper, we propose a data-driven procedure based on divide-and-conquer for selecting the tuning parameters in kernel ridge regression by modifying the popular Generalized Cross-validation (GCV, Wahba, 1990). While the proposed criterion is computationally scalable for massive data sets, it is also shown under mild conditions to be asymptotically optimal in the sense that minimizing the proposed distributed-GCV (dGCV) criterion is equivalent to minimizing the true global conditional empirical loss of the averaged function estimator, extending the existing optimality results of GCV to the divide-and-conquer framework. 

   more » « less
3. Optimal Tuning for Divide-and-conquer Kernel Ridge Regression with Massive Data

   Xu, G. (January 2018, The Thirty-fifth International Conference on Machine Learning)

   Divide-and-conquer is a powerful approach for large and massive data analysis. In the nonparameteric regression setting, although various theoretical frameworks have been established to achieve optimality in estimation or hypothesis testing, how to choose the tuning parameter in a practically effective way is still an open problem. In this paper, we propose a data-driven procedure based on divide-and-conquer for selecting the tuning parameters in kernel ridge regression by modifying the popular Generalized Cross-validation (GCV, Wahba, 1990). While the proposed criterion is computationally scalable for massive data sets, it is also shown under mild conditions to be asymptotically optimal in the sense that minimizing the proposed distributed-GCV (dGCV) criterion is equivalent to minimizing the true global conditional empirical loss of the averaged function estimator, extending the existing optimality results of GCV to the divide-and-conquer framework. 

   more » « less
4. Overparameterized Random Feature Regression with Nearly Orthogonal Data

   Wang, Zhichao; Zhu, Yizhe (April 2023, Proceedings of Machine Learning Research)

   Ruiz, Francisco; Dy, Jennifer; van_de_Meent, Jan-Willem (Ed.)

   We investigate the properties of random feature ridge regression (RFRR) given by a two-layer neural network with random Gaussian initialization. We study the non-asymptotic behaviors of the RFRR with nearly orthogonal deterministic unit-length input data vectors in the overparameterized regime, where the width of the first layer is much larger than the sample size. Our analysis shows high-probability non-asymptotic concentration results for the training errors, cross-validations, and generalization errors of RFRR centered around their respective values for a kernel ridge regression (KRR). This KRR is derived from an expected kernel generated by a nonlinear random feature map. We then approximate the performance of the KRR by a polynomial kernel matrix obtained from the Hermite polynomial expansion of the activation function, whose degree only depends on the orthogonality among different data points. This polynomial kernel determines the asymptotic behavior of the RFRR and the KRR. Our results hold for a wide variety of activation functions and input data sets that exhibit nearly orthogonal properties. Based on these approximations, we obtain a lower bound for the generalization error of the RFRR for a nonlinear student-teacher model. 

   more » « less
5. Learning with centered reproducing kernels

   https://doi.org/10.1142/S0219530523400018  

   Wang, Chendi; Guo, Xin; Wu, Qiang (April 2024, Analysis and Applications)

   Kernel-based learning algorithms have been extensively studied over the past two decades for their successful applications in scientific research and industrial problem-solving. In classical kernel methods, such as kernel ridge regression and support vector machines, an unregularized offset term naturally appears. While its importance can be defended in some situations, it is arguable in others. However, it is commonly agreed that the offset term introduces essential challenges to the optimization and theoretical analysis of the algorithms. In this paper, we demonstrate that Kernel Ridge Regression (KRR) with an offset is closely connected to regularization schemes involving centered reproducing kernels. With the aid of this connection and the theory of centered reproducing kernels, we will establish generalization error bounds for KRR with an offset. These bounds indicate that the algorithm can achieve minimax optimal rates. 

   more » « less