Error Bounds for Learning with Vector-Valued Random Features
This work provides a theoretical foundation for vector-valued random feature methods, addressing a gap in the literature for researchers in machine learning theory, though it is incremental as it builds on existing finite-dimensional analyses.
The paper tackles the problem of error analysis for learning with vector-valued random features, establishing strong consistency under model misspecification and minimax optimal convergence rates in well-specified settings, with parameter and sample complexities comparable to Monte Carlo intuition and free from logarithmic factors.
This paper provides a comprehensive error analysis of learning with vector-valued random features (RF). The theory is developed for RF ridge regression in a fully general infinite-dimensional input-output setting, but nonetheless applies to and improves existing finite-dimensional analyses. In contrast to comparable work in the literature, the approach proposed here relies on a direct analysis of the underlying risk functional and completely avoids the explicit RF ridge regression solution formula in terms of random matrices. This removes the need for concentration results in random matrix theory or their generalizations to random operators. The main results established in this paper include strong consistency of vector-valued RF estimators under model misspecification and minimax optimal convergence rates in the well-specified setting. The parameter complexity (number of random features) and sample complexity (number of labeled data) required to achieve such rates are comparable with Monte Carlo intuition and free from logarithmic factors.