Dimension-free deterministic equivalents and scaling laws for random feature regression
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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSimilar Papers 제목 키워드 기반
High-dimensional analysis of ridge regression for non-identically distributed data with a variance profile
High-dimensional linear regression has been thoroughly studied in the context of independent and identically distributed data. We propose to investigate high-dimensional regression models for independent but non-identica…
regressionCauchy noise loss for stochastic optimization of random matrix models via free deterministic equivalents
For random matrix models, the parameter estimation based on the traditional likelihood functions is not straightforward in particular when we have only one sample matrix. We introduce a new parameter optimization method …
parameter estimationStochastic OptimizationScaling Laws for Galaxy Images
We present the first systematic investigation of supervised scaling laws outside of an ImageNet-like context - on images of galaxies. We use 840k galaxy images and over 100M annotations by Galaxy Zoo volunteers, comparab…
Domain AdaptationScaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law
Recent works have highlighted optimization difficulties faced by gradient descent in training the first and last layers of transformer-based language models, which are overcome by optimizers such as Adam. These works sug…
A non-asymptotic theory of Kernel Ridge Regression: deterministic equivalents, test error, and GCV estimator
We consider learning an unknown target function $f_*$ using kernel ridge regression (KRR) given i.i.d. data $(u_i,y_i)$, $i\leq n$, where $u_i \in U$ is a covariate vector and $y_i = f_* (u_i) +\varepsilon_i \in \mathbb{…