Source-linked AI summary
Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees
Caixing Wang, Zhibo Chen, Yue Wang
TL;DR
Large-scale KRR is computationally demanding, and random-feature KRR needs regularization tuning tied to unknown source and capacity parameters. The paper proposes neighboring early stopping in random-feature space and proves oracle-rate attainment up to logarithmic factors under stated conditions.
Problem
Random-feature KRR can achieve optimal rates under source and capacity conditions, but those results typically require careful regularization tuning, while exact KRR is costly at large sample sizes.
Method
The method compares adjacent KRR-RF estimators on a grid uniform in inverse regularization, computing discrepancy and complexity quantities directly from random features.
Results
The selected estimator attains the oracle polynomial learning rate up to logarithmic factors under source, capacity, grid, and random-feature budget conditions.
Takeaways & Limitations
Regularization can be selected without prior knowledge of source and capacity exponents, covering the well-specified regime and part of the misspecified regime.
Takeaways & Limitations
The guarantees require source, capacity, grid-coverage, and random-feature budget conditions, and figure errors may not be directly comparable when candidate ranges differ.
Abstract
from arXiv · showhide
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.
1 Introduction
KRR offers flexible nonlinear modeling but becomes costly at large sample sizes, motivating random-feature approximations and adaptive regularization. The paper proposes a neighboring KRR-RF stopping rule with theoretical oracle-rate guarantees and practical computational savings.
- Motivation: KRR can become infeasible on large datasets because its computational complexity scales quadratically or cubically with sample size.The exact method may require O(|D|^3) computation and O(|D|^2) memory for kernel-matrix inversion.
- Motivation: Random features replace the implicit kernel with an explicit low-dimensional randomized map, enabling scalable KRR approximations with optimal rates under source and capacity conditions.Optimal rates still require careful regularization-parameter tuning.
- Related approaches: Existing adaptive approaches include predictive-risk criteria, discrepancy rules, and Lepskii-type comparisons across regularization levels.Prior work also uses regularization-path structure to reduce repeated cross-scale comparisons.
- Method motivation: Random-feature adaptation must simultaneously control sampling error, regularization bias, and approximation error while remaining computable without the exact kernel matrix.These requirements motivate a stopping rule tailored to the random-feature representation.
- Contribution: The proposed rule compares neighboring estimators on a uniformly subdivided regularization grid, reducing all-pairs comparisons and computing stopping quantities directly from predictions and coefficients.This design is intended to make adaptive KRR-RF regularization more efficient and implementable.
- Theory and evaluation: Under source, capacity, grid, and feature-budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors without prior source or capacity exponents.The result covers the well-specified regime and part of the misspecified regime; experiments compare the method with cross-validation and Lepskii-type selection.
2 Preliminaries
This section introduces KRR and its random-feature approximation, then states the assumptions and oracle-rate benchmark used for adaptive regularization. Random features reduce computational requirements, while optimal tuning depends on unknown source and capacity parameters.
- Kernel ridge regression: KRR minimizes regularized empirical risk, with λ controlling the bias–variance trade-off and a representer-theorem solution based on the kernel matrix.The coefficient vector is α = (K + λ|D|I)^−1y.
- Kernel ridge regression: O(|D|^3) computation and O(|D|^2) memory make exact KRR costly for large datasets.These costs arise from inverting and storing the |D|×|D| kernel matrix.
- Random-feature approximation: Random features replace the implicit kernel with an explicit map sampled from an integral representation, producing KRR-RF estimators in a finite-dimensional feature space.The induced random-feature kernel KM approximates the original kernel K.
- Random-feature approximation: O(|D|M^2 + M^3) computation and O(|D|M + M^2) memory make KRR-RF feasible for large-scale learning.This is a substantial reduction relative to the exact KRR costs stated above.
- Assumptions: The source and capacity assumptions characterize target smoothness and RKHS complexity through r and the effective-dimension growth exponent γ.The analysis also imposes bounded-feature and response-moment conditions, plus a random-feature dimension condition involving α.
- Oracle benchmark: λopt = |D|^−1/(2r+γ) yields the minimax rate |D|^−r/(2r+γ) up to logarithmic factors when M is sufficiently large.The theorem assumes 2r + γ > 1 and covers r ∈ (0,1), including part of the misspecified regime, but λopt depends on unknown r and γ.
3 Method
The method adaptively selects regularization for KRR-RF by comparing neighboring estimators on a uniformly subdivided inverse-regularization grid, with comparisons computed in random-feature coordinates. Its analysis provides high-probability control and oracle-rate guarantees under source, capacity, grid, and feature-budget conditions.
- Neighboring early-stopping rule: NESR-KRR-RF compares only neighboring KRR-RF estimators along a uniformly subdivided regularization grid, replacing standard all-pairs comparisons.The neighboring construction is designed to reduce computational burden while retaining adaptive guarantees.
- Comparison estimate: The comparison bound depends on regularization differences, empirical random feature effective dimension, and target-function smoothness.This bound supports analysis of adaptive procedures based on estimator comparisons.
- Algorithm: The adaptive rule uses λ_k = 1/hk and scans neighboring estimators over a candidate grid, selecting the first threshold-crossing index or λ_1 if none occurs.The procedure constructs Λ_ES, computes estimators and empirical effective dimensions, evaluates neighboring discrepancies, and returns the selected estimator.
- Computable discrepancy: The stopping quantity is computable from empirical prediction differences and coefficient norms without constructing an exact-kernel or random-feature |D| × |D| Gram matrix.The computational representation uses quantities available directly in the random feature space.
- Computational comparison: NESR requires O(KM^2) comparison operations, whereas the all-pairs LP-RF rule requires O(K^2M^2).When M ≪ |D|, adaptive selection in the M-dimensional random feature space can also reduce computational and memory costs relative to exact-KRR selection.
4 Theory
The neighboring early-stopping rule achieves the oracle learning rate up to logarithmic factors under stated assumptions and feature-budget conditions. The theorem also specifies how the result handles unknown exponents and random-feature budgets.
- Main result: The selected KRR-RF estimator achieves the optimal adaptive learning rate up to logarithmic factors.The result is established under the theorem’s assumptions, including source and capacity conditions and suitable grid and random feature budget conditions.
- Main result: Theorem 2 assumes Assumptions 1–5, h ≥1, 2r + γ > 1, KES ≥2, and a candidate path covering the oracle parameter.The theorem also imposes a sufficient lower bound on the number of random features M.
- Main result: With probability at least 1 −δ, the estimator selected with λES = λˆk satisfies the theorem’s stated performance bound.The constants cRF and C3 are independent of |D|, λ, M, and δ.
- Adaptation: The adaptive procedure selects the regularization parameter without prior knowledge of the smoothness and capacity parameters while retaining optimal statistical performance.This conclusion is stated for the neighboring early-stopping rule under the conditions of Theorem 2.
- Scope and conditions: The feature budget M must be sufficiently large for the oracle-rate guarantee, but adaptive selection of M is not considered.The required lower bound depends on the unknown parameters r, α, and γ; M is treated as a prespecified computational budget.
- Proof strategy: The proof compares the selected scale with an oracle grid point and combines neighboring discrepancies, effective-dimension estimates, covariance stability, and fixed-scale bounds.The oracle grid point satisfies λopt ≤ λk∗ ≤ 2λopt; the two cases λES ≤ λk∗ and λES > λk∗ are handled separately.
5 Simulation
The simulations evaluate NESR against LP, CV, and an oracle across smoothness-capacity settings, varying training size and random-feature budget. NESR generally matches benchmark prediction accuracy while reducing runtime under the specified candidate paths.
- Simulation setup: The study uses periodic spline kernels with four (r, γ) configurations, three within the theoretical regime 2r + γ > 1 and one additional setting with 2r + γ < 1.The last configuration, (r, γ) = (0.4, 0.1), is outside Theorem 2’s theoretical regime.
- Simulation setup: NESR, LP, CV, and an oracle selector are compared using controlled regularization parameterizations and candidate grids.The oracle minimizes test error, while the simulation parameterization uses the known data-generating r and γ only for controlled comparison.
- Curve fitting: NESR and LP closely track the true function in most curve-fitting settings, with larger boundary discrepancies for (r, γ) = (0.5, 0.45).The four methods produce broadly similar fitted curves overall.
- Training sample size: RMSE generally decreases with training size; NESR, LP, and CV are broadly comparable in several settings, while NESR and LP outperform CV in the (0.4, 0.1) setting.NESR often has narrower error bars than CV and is slightly better than LP at several sample sizes.
- Computational cost: NESR generally runs faster than LP while retaining comparable RMSE, consistent with replacing all-pairs discrepancy comparisons by neighboring comparisons.The runtime experiment uses restricted candidate ranges centered around regions where oracle solutions are observed.
6 Real Data Analysis
Real-data experiments compare NESR and LP on six regression and classification datasets while varying training size and random-feature count. NESR generally provides comparable or better prediction accuracy with lower recorded runtime in most reported experiments.
- Datasets and protocol: The evaluation covers six datasets: three regression tasks and three binary classification tasks, using prediction or classification error as appropriate.All input variables are continuous, and the bandwidth parameter is selected by five-fold cross-validation.
- Varying training size: When training sample size increases, prediction error generally decreases, while NESR is comparable to or better than LP across the reported datasets.Results are averaged over 10 independent trials, with error bars of similar magnitude.
- Varying training size: NESR’s recorded running time is lower than LP’s in most reported training-size experiments.The same runtime-oriented candidate settings are used for prediction-error and computational-cost reporting.
- Varying random features: As M grows, regression performance largely stabilizes around M = 1000, while classification performance levels off at somewhat smaller feature counts.Across the considered M values, NESR generally achieves prediction performance comparable to or better than LP.
7 Conclusion
The paper presents NESR as an adaptive KRR-RF rule that combines neighboring comparisons with random-feature-space computation. Its theory gives oracle-rate guarantees, and experiments report competitive accuracy with lower computational cost in the tested settings.
- Method: NESR compares adjacent estimators on a grid uniform in inverse regularization, reducing discrepancy comparisons relative to all-pairs Lepskii procedures.The discrepancy and empirical complexity term are computed directly in the random feature space without forming the exact kernel Gram matrix.
- Theory: Under source, capacity, grid-coverage, and random-feature budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors.The guarantee covers well-specified and partially misspecified regimes without prior knowledge of source and capacity exponents.
- Empirical findings: The numerical experiments report prediction performance comparable to benchmark methods while requiring fewer discrepancy comparisons and, in reported implementations, less computation.The conclusion concerns the tested simulation and real-data implementations.