Generalization Properties of Robust Learning With Random Features

Random features (RFs) provide an efficient approximation to kernel methods, and allow for scalable learning on large datasets by reducing computational complexity while maintaining strong theoretical guarantees. However, real-world data can often be contaminated by outliers or heavy-tailed noise, which significantly degrades the performance of standard RF algorithms. To address this issue, we propose a robust and adaptive regularized least squares method with random features (RRLS-RF) that incorporates response truncation. The truncation level adaptively balances robustness and bias based on the sample size and moment conditions. We establish the generalization properties of RRLS-RF by assuming only a bounded $(1+\delta )$(1+δ)-th moment for any $\delta > 0$δ>0. Specifically, our analysis shows that RRLS-RF achieves learning rates of $\mathcal {O}(|D|^{-\frac{\delta }{2\delta +2}})$O(|D|-δ2δ+2) with only $\mathcal {O}(|D|^{\frac{\delta }{2\delta +2}}\log |D|)$O(|D|δ2δ+2log|D|) random features, where $|D|$|D| denotes the training sample size. These results converge to the optimal learning rates of $\mathcal {O}(|D|^{-\frac{1}{2}})$O(|D|-12) as $\delta \rightarrow \infty$δ→∞, covering the traditional boundedness or sub-Gaussian assumptions in the regularized least squares method with random features (RLS-RF). Furthermore, we refine our analysis and show that RRLS-RF can achieve even faster learning rates under source and capacity conditions, as well as a smaller number of RFs with data-dependent sampling strategies. The derived sharp learning rates can also cover the mis-specified settings where the true function may not precisely align with the assumed kernel space. We further establish the first minimax lower bound under the weak moment condition, which shows that the RRLS-RF estimator is optimal over a wide range of source conditions. Our numerical experiments and real data analysis verify the theoretical results and demonstrate the superior robustness of RRLS-RF against outliers and heavy-tailed noise compared to standard methods.