In this paper we propose the Highly Adaptive Ridge (HAR): a regression method that achieves an n−1/3 dimension-free L2 convergence rate (up to log factors) in the class of right-continuous functions with square-integrable sectional derivatives. This is a large nonparametric function class that is particularly appropriate for tabular data. For squared error loss, HAR is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion, and thus scales reasonably well, computationally. We prove close connections between HAR and kernel ridge regression in Sobolev spaces of dominating mixed derivatives, and highlight practical differences. We use simulation and real data to confirm our theory.
Figures & tables
Fig 1: Fits of HAR and other methods on simple one-dimensional data. Each panel shows the fits of one estimator in the 3 repetitions (colored lines) and the true function (black).
Fig 2: The waves f1 and f2 on the square of the first two covariates.
Process
HAR
Mixed Sobolev KRR
HAL
Gradient Boosted Trees
Radial Basis KRR
wave, k=1
0.022
0.021
0.022
0.022
0.033
wave, k=2
0.11
0.090
0.11
0.10
0.054
wave, k=3
0.26
0.20
0.28
0.20
0.053
wave, k=4
0.35
0.28
0.43
0.34
0.053
Table 1: Mean generalization MSE of each estimator on the wave along k covariates, over 200 datasets. The smallest of each row, before rounding, is in bold, and the Monte Carlo standard error of each mean is at most 1.9% of the mean. The estimators that penalize sectional variation beat radial basis KRR when the wave lies along one covariate and lose more and more when the wave spans several.
p
HAR
Mixed Sobolev KRR
Gradient Boosted Trees
Radial Basis KRR
4
0.11
0.089
0.15
0.054
8
0.29
0.23
0.31
0.22
12
0.50
0.40
0.49
0.56
16
0.66
0.56
0.63
0.68
24
0.72
0.68
0.78
0.74
Table 2: Mean generalization MSE of each estimator on the sum of waves along pairs of covariates, over 200 datasets for each number of covariates p . The smallest of each row, before rounding, is in bold, and the Monte Carlo standard error of each mean is at most 1.2% of the mean. Radial basis KRR has the smallest error with few covariates and loses that lead as p grows. HAL excluded due to compute time.
Fig 3: The terms in x1 and x2 of the truth fθ of the steps ( θ=0 ) and of the ramps ( θ=\immediate0.5$$ ), which change at the same places. The terms in x3 and x4 are the same function of (x3,x4) .
Process
HAR
Mixed Sobolev KRR
HAL
Gradient Boosted Trees
Radial Basis KRR
steps
0.066
0.066
0.039
0.055
0.11
ramps
0.020
0.019
0.032
0.046
0.023
Table 3: Mean generalization MSE of each estimator on the steps and ramps processes, over 200 datasets. The smallest of each row, before rounding, is in bold, and the Monte Carlo standard error of each mean is at most 1.9% of the mean. HAL and gradient boosted trees beat HAR and MS-KRR on the steps, and lose to them on the ramps.
Fig 4: The terms in x1 and x2 of the truths of the dense, sparse and flipped processes, with 300 points of one training draw. The terms in x3 and x4 are the same function of (x3,x4) . Colors are scaled per panel.
Process
HAR
Mixed Sobolev KRR
HAL
Gradient Boosted Trees
Radial Basis KRR
dense
0.016
0.038
0.033
0.049
0.066
sparse
0.054
0.034
0.056
0.053
0.024
dense, flipped
0.030
0.038
0.046
0.049
0.066
Table 4: Mean generalization MSE of each estimator on the processes with skewed covariates, over 200 datasets. The smallest of each row, before rounding, is in bold, and the Monte Carlo standard error of each mean is at most 1.9% of the mean. HAR beats MS-KRR when the truth changes where the data are dense and loses to it when the truth changes where they are sparse, and the flip raises the error of HAR and leaves that of MS-KRR as it was.
data
rows
p
HAR
Mixed Sobolev KRR
HAL
Gradient Boosted Trees
Radial Basis KRR
Elastic Net
power
2000
4
1.02
1.05
1.08
1.00
1.13
1.34
yacht
308
6
2.68
1.00
2.57
2.01
2.10
453
concrete
1030
8
1.03
1.00
1.13
1.25
1.93
7.61
energy
768
8
1.22
1.24
1.01
1.00
2.04
79.6
kin8nm
2000
8
2.46
2.16
2.71
2.56
1.00
4.65
protein
2000
9
1.03
1.07
1.00
1.00
1.09
2.14
Table 5: Test MSE of each method across the UCI datasets, averaged over the 5 repetitions, as a multiple of the smallest such average on the same dataset, which is in bold. The column “rows” gives the number of rows used, before the split, and the column p gives the number of covariates. A dash marks a method that we did not run on a dataset.
data
rows
p
HAR
Mixed Sobolev KRR
HAL
Gradient Boosted Trees
Radial Basis KRR
Elastic Net
power
2000
4
48
11
220
24
24
0.099
yacht
308
6
0.29
0.24
2.5
14
0.34
0.13
concrete
1030
8
9.7
3
64
42
3.6
0.12
energy
768
8
4
1.4
18
20
1.8
0.2
kin8nm
2000
8
71
14
842
54
24
0.1
protein
2000
9
52
11
572
15
24
0.25
Table 6: Mean time in seconds over the 5 repetitions to tune and fit each method on the training data and predict the test data, on one core. A dash marks a method that we did not run on a dataset.
Fig 5: Cross-validated error of HAR and mixed Sobolev KRR at each depth D of the depth path, averaged over the 5 repetitions, as a multiple of the smallest such error of either method on the same dataset. The last point of each curve is the full depth D=p , which is plain HAR or plain mixed Sobolev KRR. The depth axis has a log scale, and so does the error axis of a panel whose title says so.
data
rows
p
HAR
Mixed Sobolev KRR
HAL
Gradient Boosted Trees
Radial Basis KRR
MARS
Random Forest
MLP
Elastic Net
power
2000
4
1.02
1.05
1.08
1.00
1.13
1.19
1.04
1.16
1.34
yacht
308
6
2.68
1.00
2.57
2.01
2.10
6.67
6.67
10.7
453
concrete
1030
8
1.03
1.00
1.13
1.25
1.93
2.03
1.68
1.44
7.61
energy
768
8
1.22
1.24
1.01
1.00
2.04
2.30
2.10
4.18
79.6
kin8nm
2000
8
3.06
2.69
3.37
3.18
1.24
3.20
3.82
1.00
5.78
protein
2000
9
1.03
1.07
1.00
1.00
1.09
1.09
1.01
1.12
2.14
Table 7: Test MSE of all the estimators across the UCI datasets, averaged over the 5 repetitions, as a multiple of the smallest such average on the same dataset, which is in bold. The column “rows” gives the number of rows used, before the split, and the column p gives the number of covariates. A dash marks a method that we did not run on a dataset.
data
rows
p
HAR
Mixed Sobolev KRR
HAL
Gradient Boosted Trees
Radial Basis KRR
MARS
Random Forest
MLP
Elastic Net
power
2000
4
48
11
220
24
24
1.4
7.3
261
0.099
yacht
308
6
0.29
0.24
2.5
14
0.34
0.85
1.4
126
0.13
concrete
1030
8
9.7
3
64
42
3.6
44
4.4
205
0.12
energy
768
8
4
1.4
18
20
1.8
3.4
1.8
166
0.2
kin8nm
2000
8
71
14
842
54
24
260
13
301
0.1
protein
2000
9
52
11
572
15
24
8.2
15
194
0.25
Table 8: Mean time in seconds over the 5 repetitions to tune and fit each of the estimators on the training data and predict the test data, on one core. A dash marks a method that we did not run on a dataset.
Random feature methods provide a scalable approximation to kernel ridge regression (KRR), but the regularization parameter that yields the oracle learning rate depends on unknown smoothness and capacity parameters. In this work, we propose a neighboring early-stopping rule for adaptive regularization in KRR with random features (KRR-RF). The method uses a grid that is uniform in inverse regularization and compares only adjacent estimators, reducing the number of discrepancy comparisons relative to standard all-pairs Lepskii-type procedures. Both the neighboring discrepancy and its empirical complexity term can be computed directly in the random feature space, without constructing the exact kernel Gram matrix. We establish a high-probability comparison bound for neighboring KRR-RF estimators and show that, under standard source and capacity conditions together with suitable grid and random feature budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors. The result allows the regularization parameter to be selected without prior knowledge of the source and capacity exponents and covers both well-specified and partially misspecified regimes. Our analysis is based on an empirical random feature effective dimension that connects the observable stopping threshold with the population complexity of the random feature model. Simulation and real-data experiments illustrate the prediction performance and computational behavior of the proposed method in comparison with standard tuning procedures.
Caixing Wang, Zhibo Chen, Yue Wang
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
We study ordinary kernel ridge regression over full Hölder-Zygmund balls, measuring errors in Sobolev norms and in pointwise and uniform losses for mixed derivatives. For targets of smoothness s, every RKHS norm equivalent to Hs+d/2 gives the optimal Hr risk for 0≤r<s; integer choices of r include integrated squared derivative losses. Pointwise and uniform guarantees require additional kernel structure. A localized wavelet kernel attains the sharp derivative rates with the same regularization orders as for function estimation, whereas equivalent changes of the RKHS norm can destroy the population bias rates. For the ordinary Gaussian kernel with a shrinking bandwidth, we prove a uniform derivative risk bound with the optimal polynomial rate and an explicit, unoptimized logarithmic factor. The results allow bounded measurable design densities bounded away from zero and conditionally sub-Gaussian noise.
We develop a comprehensive theory for regularized M-estimation in reproducing kernel Hilbert spaces. Under mild conditions on the loss we establish existence and measurability of the estimator, covering a wide range of convex and non-convex losses, including bounded robust losses. We further prove sharp rates of convergence with an explicit bias-variance decomposition governed by a novel complexity measure. We show that the variance is independent of misspecification, while the bias depends on a source condition parameter known in the learning literature. For tensor product Sobolev spaces we obtain new rates that connect to spaces of functions with dominating mixed smoothness, substantially extending existing results and explaining why these estimators circumvent the curse of dimensionality. Our methodology, combining elements from both functional analysis and empirical process theory, allows for an asymptotic linearisation of the objective function that avoids both closed-form solutions and global Lipschitz assumptions, and may be of independent interest. The estimators are implemented in C++ and theory is supported by numerical experiments.
Ioannis Kalogridis
School of Mathematics and Statistics, University of Glasgow, United Kingdom