A proposed rule for selecting the regularization level in random-feature kernel regression is reported to achieve the oracle convergence rate, up to logarithmic factors, under the paper's stated conditions. The rule is designed to work without prior knowledge of two theory parameters, called source and capacity exponents, that describe the problem's smoothness and complexity. The result is a conditional theoretical guarantee with probability at least 1 minus delta, not an unconditional promise about every dataset or implementation.
The method, called NESR-KRR-RF, is described in an arXiv preprint, version 1, dated 26 Aug 2026. Its central practical idea is to compare nearby candidate fits as it searches for a regularization level.
A neighboring search through candidate fits
NESR places candidate estimators on a grid that is uniform in inverse regularization. It compares adjacent estimators and stops when their discrepancy crosses a threshold. The calculation is carried out in random-feature coordinates, so it does not require the exact kernel Gram matrix.
The theory's comparison bound covers differences between KRR-RF estimators at different regularization levels. It involves the separation between those levels, an empirical measure of the random-feature model's effective dimension, and the smoothness of the target. This bound is part of the justification for the stopping rule.
The stopping quantity can be evaluated from differences in the models' empirical predictions and from their coefficient norms in the random-feature coordinates. That gives the procedure the numerical comparison it uses while moving along the candidate grid.
The reported complexity distinction concerns the comparison stage. LP-RF makes all-pairs comparisons, which gives a quadratic operation order, while NESR compares neighboring candidates, giving a linear operation order for that stage. The order depends on the size of the candidate path and does not by itself establish that every full implementation will run faster.
What the experiments found
An introductory benchmark compared five-fold cross-validation with an oracle path. Averaged over 12 trials, cross-validation required 80 solves, compared with 16 for the oracle path. Its average test RMSE, or root mean squared error, was 0.694 plus or minus 0.013, compared with 0.677 plus or minus 0.005 for the oracle. The supplied analysis does not define what the displayed plus-or-minus values represent, so they cannot be treated as a stated confidence interval.
The broader synthetic study used four parameter configurations. Three satisfied the condition 2r + gamma greater than 1 used by the adaptive-rate theorem. The configuration r = 0.4 and gamma = 0.1 fell below that boundary and was outside the theorem's stated regime, so its results do not serve as a validation of that theorem.
In the configuration r = 0.5 and gamma = 0.45, NESR had the lowest RMSE among the feasible selection methods for most reported sample sizes and remained close to the oracle benchmark. The result is limited to that tested configuration and the sample sizes shown in the supplied analysis.
In runtime simulations with restricted candidate ranges, NESR generally required less running time than LP while maintaining comparable prediction accuracy. Those candidate ranges were informed by oracle solutions, however, so the comparison was not a fully data-driven, end-to-end test of the search path.
The feature-count checks showed prediction errors tending to decrease or level off as more random features were used. In the reported comparisons, NESR generally maintained a slightly lower RMSE than LP. For the synthetic configurations inside the theorem's regime, log-log plots showed an approximately linear decrease in mean squared error, consistent with the theoretical polynomial rate.
Six benchmark datasets added a practical test
The real-data benchmark covered six datasets. KIN8NM, SPCD and PPOPTS were regression tasks, while SUSY, HTRU2 and MGT were binary-classification tasks. Results were averaged over 10 independent trials, and SUSY was randomly subsampled.
Across the reported real-data experiments, NESR generally matched or exceeded LP on prediction performance and had lower recorded runtime in most experiments. This is evidence from six heterogeneous datasets under the reported trial and implementation settings, not a universal result.
The guarantee has a defined boundary
The oracle-rate theorem depends on assumptions about source behavior, model capacity, coverage of the regularization grid, the operating regime and a sufficient random-feature budget. The lower feature-budget requirement itself depends on unknown exponents, and the study does not consider adaptive selection of the random-feature count.
The runtime evidence also has a built-in qualification because the synthetic candidate ranges were chosen with information from oracle solutions. The real-data evidence is limited to six datasets, while several results are qualitative summaries of figures and the meaning of the displayed plus-or-minus values is not specified in the supplied analysis.
Taken together, the study presents NESR as a conditional adaptive option for the tested random-feature kernel-regression setting. It supports a linear-versus-quadratic distinction in the comparison stage and reports favorable results in specified experiments, but it does not establish universal speed or accuracy advantages, adaptive feature-budget selection, or performance beyond the stated conditions.
Paper data and sources
Original title: Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees
Authors: Caixing Wang, Zhibo Chen, Yue Wang
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text