Beyond Cross-Validation: Adaptive Parameter Selection for Kernel-Based Gradient Descents

Xiaotong Liu; Yunwen Lei; Xiangyu Chang; Shao-Bo Lin

stat.MLMar 3, 2026

Beyond Cross-Validation: Adaptive Parameter Selection for Kernel-Based Gradient Descents

Authors: Xiaotong Liu, Yunwen Lei, Xiangyu Chang, Shao-Bo Lin

Organizations: Center for Intelligent Decision-Making and Machine Learning, School of Management, Xi’an Jiaotong University, Xi’an, China · Department of Mathematics, The University of Hong Kong, Hongkong, China

Abstract

This paper proposes a novel parameter selection strategy for kernel-based gradient descent (KGD) algorithms, integrating bias-variance analysis with the splitting method. We introduce the concept of empirical effective dimension to quantify iteration increments in KGD, deriving an adaptive parameter selection strategy that is implementable. Theoretical verifications are provided within the framework of learning theory. Utilizing the recently developed integral operator approach, we rigorously demonstrate that KGD, equipped with the proposed adaptive parameter selection strategy, achieves the optimal generalization error bound and adapts effectively to different kernels, target functions, and error metrics. Consequently, this strategy showcases significant advantages over existing parameter selection methods for KGD.

Figures & tables

Panel of Figure 1 — Figure 1: Role of the number of iterations in controlling the bias, variance and total error of KGD under the $L_{2}$ norm. The training samples $\{x_{i}\}_{i=1}^{1000}$ are independently drawn according to the uniform distribution on the (hyper-)cube $[0,1]^{d}$ with $d=1,3$ . The corresponding outputs are generated by the model $y_{i}=g_{j}(x_{i})+\varepsilon_{i},j=1,2$ , where $g_{1}$ and $g_{2}$ are defined by ( 64 ) and ( 65 ), respectively, and $\varepsilon_{i}$ is the independent Gaussian noise $\mathcal{N}(0,\sigma^{2})$ with $\sigma=0.6$ . The bias and variance is defined by ( 23 ) below.

Panel of Figure 2 — Figure 2: Step $t_{\tilde{C}}$ determined by different values of the constant $\tilde{C}$ under the BSP. The experimental setting is the same as in Figure 1 .

t\|f_{t+1,\beta,D_{tr,L}}\!-\!f_{t,\beta,D_{tr,L}}\|_{D_{tr,L}}+t^{1/2}\|f_{t+1,\beta,D_{tr,L}}\!-\!f_{t,\beta,D_{tr,L}}\|_{K}\geq\hat{C}_{j}\mathcal{W}_{D_{tr,L},t}.

(10)

Algorithm 1 KGD with HSS

Comparison of parameter selection methods for KGD
Methods		generalization error bound	Ada. to kernel	Ada. to function	Ada. to norm $\\|\cdot\\|_{\rho}$ and $\\|\cdot\\|_{K}$
Information entropy method	AIC ( Demyanov et al., 2012 )	N/A	✓	$\times$	$\times$
Information entropy method	BIC ( Demyanov et al., 2012 )	N/A	✓	$\times$	$\times$
Splitting method	HO ( Caponnetto and Yao, 2010 )	Optimal	✓	✓	$\times$
Splitting method	CV ( Györfi et al., 2002 )	Optimal	✓	✓	$\times$
	LOO ( Zhang, 2003 )	Sub-optimal	✓	✓	$\times$

Table 1: Comparison of different parameter selection methods

Panel of Figure 3 — Figure 3: Relation between the $L_{2}$ norm/ $L_{\infty}$ norm and the constant $\tilde{C}$ .

Panel of Figure 4 — Figure 4: Range of $\hat{C}_{j^{*}}$ under BSP and range of $\hat{t}^{*}$ under BS (results from a single experiment).

Panel of Figure 5 — Figure 5: Generalization performance of BS, HO, and HSS (where $L$ in HSS is fixed at $0.6|D|$ ).

Settings	Details	Settings	Details
Number of alternative parameters	24	Step size	$\beta=1$ for $d=1$ , $\beta=3$ for $d=3$
Parameter selection interval	0.05	Training data size $\|D\|$	1000, 1200
Optimal parameter was selected	Yes	Testing data size $\|D^{\prime}\|$	500
Number of trials	10	Accuracy metric	$L_{2}$ norm, $L_{\infty}$ norm
Maximum number of iterations	$T=\|D\|$	Efficiency metric	Maximum memory usage (MMU), Time (s)

Table 2: Experiment settings for all bias–variance analysis methods in Table 3 and Table 4

Numerical performance of different parameter selection methods
Methods	$d=1$				$d=3$
Methods	$L_{2}$ norm	$L_{\infty}$ norm	Time (s)	MMU (GB)	$L_{2}$ norm	$L_{\infty}$ norm	Time (s)	MMU (GB)
HO	0.0587	0.2630	1.03	0.43	0.1641	0.9370	15.98	0.54
AIC	0.0742	0.2407	7.26	0.66	0.1738	1.0100	110.76	0.80
BIC	0.0750	0.2995	8.85	0.65	0.2356	1.0573	109.75	0.81
BP	0.0643	0.1817	924.71	52.40	0.1680	1.0030	1081.37	53.38

Table 3: Numerical performance of different parameter selection methods when

|D|=1000

Numerical performance of different parameter selection methods
Methods	$d=1$				$d=3$
Methods	$L_{2}$ norm	$L_{\infty}$ norm	Time (s)	MMU (GB)	$L_{2}$ norm	$L_{\infty}$ norm	Time (s)	MMU (GB)
HO	0.0384	0.2046	1.52	0.45	0.1594	1.0457	21.77	0.60
AIC	0.0439	0.1548	11.58	0.68	0.1503	1.0330	158.02	0.87
BIC	0.0485	0.2439	12.50	0.68	0.2169	1.0292	163.58	0.92
BP	0.0423	0.1346	1524.22	91.37	0.1513	1.0835	1788.85	91.48

Table 4: Numerical performance of different parameter selection methods when

|D|=1200

Panel of Figure 6 — Figure 6: Illustration of the numerical performance of methods presented in Tables 3 and 4 .

Panel of Figure 7 — Figure 7: Results under covariate shift.

Panel of Figure 8 — Figure 8: Results under covariate shift.

Panel of Figure 9 — Figure 9: Generalization performance of BS, HO, and HSS for the total intensity data and declination data of magnetic ﬁeld. In HSS, $L$ is set to $0.8|D|$ for the total intensity data and $0.9|D|$ for the declination data.

Panel of Figure 10 — Figure 10: Maps of magnetic total intensity given by IGRF-13 (top panel) and predicted by KGD under HO (middle panel) and KGD under HSS (bottom panel) at the WGS84 ellipsoid surface on August 15th, 2024. The projection used is the Miller cylindrical projection.

Kernel Methods

Kernel methods use similarity functions and reproducing kernel spaces to model nonlinear relationships, quantify uncertainty, and compare data.

See all 227 papers

Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms
Sep 10, 2026Jun-Yi Meng, Zheng-Chu Guo, Yuan MaoKernel Regression Communication-Efficient Distributed Training
School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, P. R. China · College of Informatics, Huazhong Agricultural University, Wuhan 430070, P. R. China
Generalization Guarantees on Data-Driven Tuning of Gradient Descent with Langevin Updates
Apr 13, 2026Saumya Goyal, Rohith Rongali, Ritabrata Ray +1Meta-Learning Gradient Descent
Machine Learning Department, Carnegie Mellon University · Electrical and Computer Engineering Department, Carnegie Mellon University.
Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees
Aug 26, 2026Caixing Wang, Zhibo Chen, Yue WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China

Sep 10, 2026J/K move · Enter open · S save

Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms

Jun-Yi Meng, Zheng-Chu Guo, Yuan Mao

School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, P. R. China · College of Informatics, Huazhong Agricultural University, Wuhan 430070, P. R. China

Kernel Regression Communication-Efficient Distributed Training Robust Loss Functions Distributed Training Statistical Learning Theory

Open paper AskPDF arXiv

In this paper, we investigate the generalization performance of distributed gradient descent algorithms in a reproducing kernel Hilbert space under a robust loss function

l_σ

. By exploiting the spectral characterization of gradient descent together with the intrinsic properties of robust loss functions, we establish optimal learning rates for the distributed kernel-based robust gradient descent (DKRGD) algorithm with an appropriately chosen scale parameter

σ

. The proposed parameter choice of

σ

simultaneously alleviates the saturation phenomenon and guarantees statistical robustness. A key technical contribution is a novel error analysis that provides substantially sharper bounds for products of operators, thereby significantly relaxing existing restrictions on the maximum number of local machines while retaining optimal learning rates. Finally, we develop a communication-efficient strategy that further improves the convergence performance of DKRGD.

Abstract

Kernel Methods

Explore similar work

Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms

Generalization Guarantees on Data-Driven Tuning of Gradient Descent with Langevin Updates

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees