Short proof shows how ridge regression works with random data.
problem Understanding prediction error in ridge regression with random design.
method Combination of exchangeability arguments, matrix perturbation, and operator convexity.
result Elementary proof of prediction error without complex inequalities.
HARFE approximates sparse additive functions using random features and ridge regression.
problem Approximating high-dimensional sparse additive functions.
method Hard-ridge random feature expansion with sparse ridge regression and hard-thresholding pursuit.
result HARFE method converges with a given error bound and achieves lower error than other algorithms.
Paper proposes methods for transfer learning with random coefficient ridge regression.
problem Estimation and prediction in high-dimensional settings with related models.
method Two estimators using weighted sums of ridge estimates from target and source models.
result Explicit expression of estimation and prediction risks derived using random matrix theory.
DRE combines DNN with random feature regression for efficient neural network design.
problem Designing and training deep neural networks (DNN) efficiently and effectively.
method DRE architecture with two-layer neural networks, randomly drawn input and output weights trained with linear ridge regression.
result DRE outperforms state-of-the-art DNN in many data sets with lower computational cost.
Improved kernel ridge regression for large datasets using weighted random binning.
problem Efficiently approximating kernel matrices for large-scale datasets.
method Introduced weighted random binning features for locality sensitive hashing.
result Weighted random binning features generate Gaussian processes of any desired smoothness.
Bayes-optimal learning of deep random networks with Gaussian weights is studied.
problem Learning a target function corresponding to a deep, extensive-width, non-linear neural network with random Gaussian weights.
method Closed-form expressions for Bayes-optimal test error, ridge regression, kernel and random features regression are computed.
result Optimally regularized ridge regression and kernel regression achieve Bayes-optimal performances, while logistic loss yields a near-optimal test error for classification.
Improved ridge regression with Frequent Directions for large-scale tasks.
problem Improving performance of ridge regression for large-scale data.
method Combines Frequent Directions with iterative optimization schemes.
result Achieves high accuracy in estimating bias and variance for sketched ridge regression.
Study predictive performance of linear regression with random functional covariates.
problem Theoretical predictive performance of linear regression with random functional covariates.
method Theoretical analysis of ridge and ridge-less least-squares regression with random functional covariates.
result Probabilistic bounds on predictive excess risk for random functional covariates.
Ridge leverage scores provide a balance between low-rank approximation and regularization, and are ubiquitous in randomized linear algebra and machine learning. Deterministic algorithms are also of interest in the moderately big data regime, because deterministic algorithms provide interpretability to the practitioner …
Study ridge regression for non-identically distributed data with varying variances.
problem Investigate high-dimensional regression with non-identical data variance.
method Propose a random effect model and use tools from random matrix theory.
result Highlight the double descent phenomenon in high-dimensional regression for certain variance profiles.
Meta-learning improves predictions with generalized ridge regression in high-dimensional settings.
problem Improving meta-learning performance in high-dimensional settings.
method Generalized ridge regression applied to high-dimensional multivariate random-effects linear models.
result Optimal predictive risk achieved when using the inverse of the covariance matrix of random coefficients.
The paper analyzes ridge regression with random features for non-identically distributed data.
problem Analyzing ridge regression performance for data with heterogeneous variance profiles.
method Combining linear-plus-chaos approximation and operator-valued free probability.
result Derives asymptotic equivalents for training and test risks under non-identically distributed data.
ParK efficiently solves kernel ridge regression for large datasets.
problem Large-scale kernel ridge regression efficiency and accuracy.
method Partitioning feature space with random projections and iterative optimization.
result Provably maintains statistical accuracy with reduced space and time complexity.
We propose LOCO, an algorithm for large-scale ridge regression which distributes the features across workers on a cluster. Important dependencies between variables are preserved using structured random projections which are cheap to compute and must only be communicated once. We show that LOCO obtains a solution which …
We improve prediction risk estimation for large datasets using sketching and ridge regression.
problem Estimating prediction risks for large datasets efficiently and accurately.
method Random matrix theory, generalized cross validation, sketched ridge regression ensembles, and ensemble trick.
result Consistent risk estimation and prediction intervals for large-scale datasets.
Kernel ridge regression for causal inference with missing data.
problem Estimating treatment effects with missing data in selected samples.
method Kernel ridge regression estimators for nonparametric dose response curves and semiparametric treatment effects.
result Uniform consistency and finite sample rates for continuous treatment, root-n consistency for discrete treatment.
Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier features are still not well understood. In this paper we take steps toward filling this gap. Specifica…
Ridge regression reveals surprising high-dimensional behaviors via random matrix theory.
problem Understanding power-law scalings in high-dimensional regression models.
method Random matrix theory and free probability.
result Analytic formulas for training and generalization errors derived from S-transform. New method detects biomarker-treatment interactions in clinical trials.
problem Detecting interactions between high-dimensional biomarkers and treatments in randomized trials.
method Two-stage penalized regression screening using ridge regression for multivariate screening.
result Ridge regression screening provides greater power than traditional methods in correlated data.
We analyze ridge interpolators in correlated factor regression models using RDT.
problem Performance analysis of ridge interpolators in correlated factor regression models.
method Utilizing Random Duality Theory (RDT), we obtain precise closed form characterizations of optimization problems.
result Ridge interpolators can smooth out the excess prediction risk and exhibit double-descent behavior.
This paper improves computational efficiency in kernel ridge regression under covariate shift.
problem Covariate shift in nonparametric regression.
method Random projections in RKHS to reduce computational demands.
result Significant computational savings can be achieved without compromising learning performance under covariate shift.
Paper analyzes error bounds for learning with vector-valued RF, improving existing analyses.
problem Learning with vector-valued random features in infinite-dimensional settings.
method Direct analysis of risk functional, avoiding random matrix theory.
result Strong consistency and minimax optimal convergence rates established.
Optimal ridge regularization computed iteratively from generative parameters.
problem Finding the optimal ridge regularization strength for linear regression.
method Iterative procedure to compute optimal regularization strength numerically.
result The proposed procedure attains near-optimal generalization across various conditions.
Random features and KRR generalize similarly when N is large enough.
problem Understanding the generalization error of random features and KRR methods.
method Analyzing spectral conditions and hypercontractivity on kernel eigenfunctions.
result The test error of random features is larger than KRR when N is small, but they achieve the same error when N is large.
We propose a new two stage algorithm LING for large scale regression problems. LING has the same risk as the well known Ridge Regression under the fixed design setting and can be computed much faster. Our experiments have shown that LING performs well in terms of both prediction accuracy and computational efficiency co…
We analyzed optimism in linear and kernel regression models.
problem Understanding predictive complexity in regression models.
method Derived closed-form asymptotic optimism for linear and kernel regression models.
result Scaled optimism is a useful measure for model complexity.
Analyzes neural networks using linear models to understand their behavior.
problem Understanding multi-layer neural networks through linear models.
method Recalls and reviews four models: linear regression with concentrated features, kernel ridge regression, random feature model, and neural tangent model.
result Highlights limitations of linear theory and discusses approaches to overcome them.
In this paper, we propose a random projection approach to estimate variance in kernel ridge regression. Our approach leads to a consistent estimator of the true variance, while being computationally more efficient. Our variance estimator is optimal for a large family of kernels, including cubic splines and Gaussian ker…
New insights into ridge regression with correlated data, improving risk prediction.
problem Understanding and predicting risk in ridge regression with correlated samples.
method Random matrix theory and free probability for asymptotic analysis; modified GCV estimator (CorrGCV) for unbiased prediction.
result GCV estimator fails for out-of-sample risk with correlated data; CorrGCV provides an unbiased estimator.
Two methods solve kernel ridge regression problems efficiently.
problem Solving kernel ridge regression problems with large datasets.
method RPCholesky and KRILL preconditioning techniques.
result Efficient solutions to KRR problems with strong guarantees.
New ridge regression bounds for high-dimensional data without proportional growth.
problem Moving beyond proportional asymptotics in high-dimensional statistics.
method Revisits ridge regression on i.i.d. data, allowing high-dimensional or infinite-dimensional feature vectors.
result Establishes non-asymptotic bounds approximating bias and variance of ridge regression.
Gradient descent outperforms ridge regression under certain covariance matrix decay conditions.
problem Comparing the performance of gradient descent and ridge regression in linear models.
method Investigated gradient descent and ridge regression for linear regression with random isotropic ground truth.
result Gradient descent outperforms ridge regression under specific covariance matrix decay conditions.
This work gives a simultaneous analysis of both the ordinary least squares estimator and the ridge regression estimator in the random design setting under mild assumptions on the covariate/response distributions. In particular, the analysis provides sharp results on the ``out-of-sample'' prediction error, as opposed to…
New approach quantifies overfitting in high-dimensional regression.
problem Quantifying and avoiding overfitting in large neural networks.
method Information bottleneck theory to minimize residual information while maximizing relevant bits.
result Characterized the relative information efficiency of randomized regression compared to optimal algorithms.
We introduce single-set spectral sparsification as a deterministic sampling based feature selection technique for regularized least squares classification, which is the classification analogue to ridge regression. The method is unsupervised and gives worst-case guarantees of the generalization power of the classificati…
We analyze generalization in deep learning models using random matrix theory.
problem Understanding the generalization error in deep learning models with random feature representations.
method Applying Random Matrix Theory to derive asymptotic generalization error formulas for various architectures.
result Linear ESNs are equivalent to ridge regression with exponentially time-weighted input covariance, revealing an inductive bias towards recent inputs.
New decentralized KRR algorithm adapts to node-specific data.
problem Consistent node-specific data in decentralized KRR.
method Data-dependent random features for adaptive RF generation.
result Average regression accuracy improved by 25.5% across six datasets.
New method shows supervised learning can mimic unsupervised learning effectively.
problem The fundamental difference between supervised and unsupervised learning.
method A two-stage procedure where unsupervised model selection is followed by adding outputs without changing parameters.
result Asymptotic out-of-sample risk bounds for various models trained without access to labels.
This paper carries out a large dimensional analysis of a variation of kernel ridge regression that we call \emph{centered kernel ridge regression} (CKRR), also known in the literature as kernel ridge regression with offset. This modified technique is obtained by accounting for the bias in the regression problem resulti…
Study characterizes training and test risks for MAP regression with Gaussian priors.
problem Understanding high-dimensional behavior of regularized linear regression with informative priors.
method Maximum a posteriori (MAP) regression with Gaussian priors, using random matrix theory.
result Closed-form risk formulas reveal the bias-variance-prior tradeoff and explain double descent.
Study shows minimizing the norm of the ERM solution stabilizes kernel ridge-less regression.
problem Stability of kernel ridge-less regression.
method Minimizing the norm of the ERM solution to minimize CV stability.
result Interpolating solution with minimum norm minimizes CV stability.
Ridge regression analysis under varying sample size and dimensionality.
problem Prediction error analysis in asymptotic ridge regression.
method Characterization of prediction error based on covariance and parameter structure.
result Interpolation can be optimal even with bounded SNR if true parameter coefficients are larger on high-variance directions.
The paper proposes a gradient-based method for multi-penalty Ridge regression.
problem Optimizing multiple regularization hyperparameters for linear regression.
method Gradient-based optimization through matrix differential calculus.
result The method outperforms traditional regularization techniques like LASSO and Ridge.
We provide a unified analysis of the predictive risk of ridge regression and regularized discriminant analysis in a dense random effects model. We work in a high-dimensional asymptotic regime where p,n→∞ and p/n→γ∈(0,∞), and allow for arbitrary covariance among the features. For both metho…
Study precise estimators for correlated data using RDT.
problem Analyzing estimators in correlated linear regression models.
method Utilized Random Duality Theory to characterize prediction risk.
result Precise closed form characterizations of estimators' risk.
Study shows double descent curve in high-dimensional linear regression with random projections.
problem Understanding the generalization performance in high-dimensional settings with random projections.
method Fixed prediction problem, ridge regression estimator, minimum norm least-squares fit, random matrix theory, asymptotic equivalents.
result Exhibit a double descent curve for high-dimensional linear regression with random projections.
Ridge regression performs optimally in noisy environments with heavy-tailed distributions.
problem Performance of ridge regression in noisy environments with heavy-tailed noise.
method Established excess risk bounds using integral operator framework and Fuk-Nagaev inequality.
result Ridge regression achieves optimal convergence rates under heavy-tailed noise, demonstrating robustness.
We analyze optimal weighted ridge regression in overparameterized linear models.
problem Optimal regularization in overparameterized linear regression models.
method Generalized ridge regression with weighted regularization.
result The optimal regularization parameter can be negative in overparameterized settings.