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.
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