Dimension-free deterministic equivalents and scaling laws for random feature regression

2024/05/24 by Leonardo Defilippis, Defilippis, Leonardo, Bruno Loureiro +3 · 12 citations
Computer Science · Mathematics · #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2405.15699

openalex publication_date 2024/05/24 · openalex created_date 2024/05/28 · openalex updated_date 2026/07/28

Abstract

In this work we investigate the generalization performance of random feature ridge regression (RFRR). Our main contribution is a general deterministic equivalent for the test error of RFRR. Specifically, under a certain concentration property, we show that the test error is well approximated by a closed-form expression that only depends on the feature map eigenvalues. Notably, our approximation guarantee is non-asymptotic, multiplicative, and independent of the feature map dimension -- allowing for infinite-dimensional features. We expect this deterministic equivalent to hold broadly beyond our theoretical analysis, and we empirically validate its predictions on various real and synthetic datasets. As an application, we derive sharp excess error rates under standard power-law assumptions of the spectrum and target decay. In particular, we provide a tight result for the smallest number of features achieving optimal minimax error rate.

Cited by

• Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data
• One-Bit Quantization for Random Features Models
• Kernel ridge regression under power-law data: spectrum and generalization
• Theory of Scaling Laws for In-Context Regression: Depth, Width, Context and Time
• Inductive Bias and Spectral Properties of Single-Head Attention in High Dimensions
• Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime
• A Law of Data Reconstruction for Random Features (and Beyond)
• Physics of Learning: A Lagrangian perspective to different learning paradigms
• Breaking the curse of dimensionality for linear rules: optimal predictors over the ellipsoid
• Neural Scaling Laws for Deep Regression
• On the existence of consistent adversarial attacks in high-dimensional linear classification
• Models of Heavy-Tailed Mechanistic Universality

Related

• Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• On the Universality of the Double Descent Peak in Ridgeless Regression
• High-dimensional ridge regression with random features for non-identically distributed data with a variance profile
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration