Estimates KRR risk from training data for various kernels and hyperparameters.
problem Predicting the generalization error of Kernel Ridge Regression.
method Introduces SCT and KARE to approximate KRR risk from training data.
result KARE provides an excellent approximation of KRR risk and helps select good kernels.
RF models implicitly regularize kernel methods as feature count increases.
problem Understanding implicit regularization in RF models.
method Random matrix theory applied to Gaussian RF models and KRR.
result The average RF predictor is close to a KRR predictor with an effective ridge.
Study improves KRR for non-i.i.d. data, with applications in denoising.
problem Kernel regression in structured non-i.i.d. settings.
method Developed a blockwise decomposition method for dependent data, deriving excess risk bounds.
result Established generalization guarantees for KRR in non-i.i.d. settings.
Study on KRR with power-law data, showing better sample complexity.
problem High-dimensional kernel ridge regression with anisotropic power-law covariance.
method Explicit characterization of kernel spectrum and asymptotic analysis of excess risk.
result Sample complexity is governed by effective dimension, not ambient dimension.
Kernel ridge regression (KRR) is a well-known and popular nonparametric regression approach with many desirable properties, including minimax rate-optimality in estimating functions that belong to common reproducing kernel Hilbert spaces (RKHS). The approach, however, is computationally intensive for large data sets, d…
Simplified kernel ridge regression with a conservation law.
problem Understanding the test risk and generalization of kernel ridge regression.
method Identification of a conservation law that limits KRR's learning ability, leading to simplified expressions for test risk.
result Transparency in test risk expressions through the conserved quantity in the kernel eigenbasis.
Optimally tackles covariate shift in RKHS-based nonparametric regression.
problem Covariate shift in nonparametric regression over RKHS.
method Two families of covariate shift problems defined using likelihood ratios. Minimax rate-optimal estimators for KRR and reweighted KRR.
result KRR is minimax rate-optimal and strictly sub-optimal compared to naive estimator under covariate shift.
ASkotch solves large-scale KRR faster and better than existing methods.
problem Challenges in scaling full Kernel Ridge Regression (KRR) to large datasets.
method ASkotch: A scalable, accelerated, iterative method for full KRR.
result ASkotch provides better solutions faster than state-of-the-art solvers for full and inducing points KRR.
The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting …
We analyze kernel matrices in polynomial high-dimensional settings and explain double descent in KRR.
problem Understanding the spectrum of kernel matrices in polynomial high-dimensional settings and its implications for KRR risk.
method Generalized decomposition of kernel matrices into low-rank spike matrix, identity, and Gegenbauer matrix.
result The test error in KRR can exhibit double descent behavior, depending on effective regularization and signal-to-noise ratio.
Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given n samples, the time and space complexity of computing the KRR estimate scale as O(n3) and O(n2) respectively, and so is prohibitive in many cases. We prop…
TKRR improves KRR performance by aligning target functions with kernels.
problem Improving kernel ridge regression performance through target alignment.
method Focuses on truncated kernel ridge regression (TKRR) with an additional spectral truncation parameter.
result TKRR can achieve faster rates than full KRR, reaching parametric rates.
Efficiently approximates statistical leverage scores for faster KRR.
problem Accurately estimating statistical leverage scores for fast KRR.
method Analytic formula for statistical leverage scores, leveraging kernel spectral density.
result Linear time approximation with theoretical guarantees, significantly faster than existing methods.
Noiseless KRR achieves optimal rates and exhibits saturation effects.
problem Understanding optimal rates and saturation phenomena in noiseless kernel ridge regression.
method Comprehensive study of noiseless KRR, establishing minimax optimal rates and uncovering phenomena of extra-smoothness and saturation.
result Noiseless KRR achieves minimax optimal rates and exhibits saturation effects.
Study the cost of overfitting in noisy KRR models.
problem Cost of overfitting in noisy kernel ridge regression.
method An agnostic view of overfitting cost as a function of sample size for any target function, using Gaussian universality ansatz and task eigenstructure.
result Characterization of benign, tempered, and catastrophic overfitting.
Paper proves KRR saturation effect for smooth functions.
problem Kernel ridge regression fails to reach theoretical limits for smooth functions.
method Proof of conjectured saturation lower bound for KRR.
result Proved the conjectured saturation lower bound for KRR.
StreaMRAK improves KRR for streaming data.
problem Streaming data with memory constraints.
method Divides problem into levels of resolution, sub-sampling.
result Efficiently integrates new samples, reduces memory and complexity.
Sharp bounds derived for test error of finite-rank kernel ridge regression.
problem Loose bounds on test error for finite-rank kernels in machine learning.
method Sharp non-asymptotic upper and lower bounds for KRR test error.
result Tighter bounds on finite-rank KRR test error, valid for any regularization parameters.
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.
In this paper, we investigate a divide and conquer approach to Kernel Ridge Regression (KRR). Given n samples, the division step involves separating the points based on some underlying disjoint partition of the input space (possibly via clustering), and then computing a KRR estimate for each partition. The conquering s…
SATL adapts to varying smoothness in hypothesis transfer learning.
problem Fixed kernel regularization fails in varying smoothness settings.
method Proposes SATL, a two-phase KRR algorithm with adaptive Gaussian kernels.
result SATL achieves minimax optimality with matching upper and lower bounds.
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.
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.
Paper proves convergence rates for Gaussian kernel ridge regression.
problem Understanding convergence rates for Gaussian kernel ridge regression.
method Establishes polynomial convergence rates for KRR with fixed hyperparameters.
result First polynomial convergence rates for Gaussian kernel ridge regression.
Tuning parameter selection is of critical importance for kernel ridge regression. To this date, data driven tuning method for divide-and-conquer kernel ridge regression (d-KRR) has been lacking in the literature, which limits the applicability of d-KRR for large data sets. In this paper, by modifying the Generalized Cr…
Random feature mapping (RFM) is a popular method for speeding up kernel methods at the cost of losing a little accuracy. We study kernel ridge regression with random feature mapping (RFM-KRR) and establish novel out-of-sample error upper and lower bounds. While out-of-sample bounds for RFM-KRR have been established by …
New bounds for KRR condition number reveal overfitting phenomena.
problem Characterizing overfitting in KRR with varying kernel spectral decay.
method Derived new bounds for kernel matrices, enhanced test error bounds, and identified feature independence role.
result Identified tempered and catastrophic overfitting phenomena.
Study shows RFRR's effectiveness with nearly orthogonal data in overparameterized settings.
problem Understanding the effectiveness of random feature regression with nearly orthogonal data.
method Investigates RFRR with nearly orthogonal deterministic unit-length input data vectors in the overparameterized regime.
result Shows high-probability non-asymptotic concentration results for RFRR's training, cross-validation, and generalization errors.
k-Rater reliability corrects under-reporting of aggregated data reliability.
problem Under-reporting of data reliability in aggregated ratings.
method k-Rater reliability (kRR) as a multi-rater generalization of IRR.
result kRR provides a more accurate measure of reliability for aggregated datasets.
The paper proves a non-asymptotic test error approximation for KRR.
problem Understanding the test error of Kernel Ridge Regression.
method Established a non-asymptotic deterministic approximation for test error of KRR.
result The test error of KRR can be approximated by a closed-form estimate derived from the spectrum of the kernel operator.
General predictive models do not provide a measure of confidence in predictions without Bayesian assumptions. A way to circumvent potential restrictions is to use conformal methods for constructing non-parametric confidence regions, that offer guarantees regarding validity. In this paper we provide a detailed descripti…
Quantum kernel improves solar irradiance forecasting.
problem Improving short-term solar irradiance forecasting accuracy.
method Quantum Fourier Transform kernel in KRR with feature mixing.
result Consistently improves R2 and nRMSE over classical kernels.
The study analyzes spectral algorithms for kernel methods and derives generalization error.
problem Estimating generalization error of spectral algorithms for kernel methods.
method Considered spectral algorithms including KRR and GD, derived generalization error as a functional of learning profile.
result Showed the loss localizes on certain spectral scales and conjectured universality of the loss for noisy observations.
Study reveals learning curves and benign overfitting in spectral algorithms for large dimensions.
problem Understanding learning curves and benign overfitting in spectral algorithms for large-dimensional data.
method Analysis of learning curves and benign overfitting in spectral algorithms for inner-product kernels on the sphere and general domains.
result Characterization of three distinct regimes: over-regularized, under-regularized, and interpolation regimes, revealing benign overfitting across both under-regularized and interpolation regimes.
Kernel ridge regression inference for nonstandard data.
problem Inferential theory for kernel ridge regression with nonstandard data.
method Constructs valid and sharp confidence sets using anti-symmetric multipliers.
result Develops a test for match effects in school matching mechanisms.
The paper explores how kernel eigenalignments affect generalization in KRR.
problem Achieving robust generalization in kernel methods.
method Direct connection between generalization and matrix eigenvectors/eigenvalues, focusing on finite-sample settings.
result Strong generalization requires increasing eigenvector alignment, eigenvalue magnitude, or gaps between eigenvalues.
SQUEAK reduces space complexity for Nystrom approximations in KRR.
problem Large datasets in KRR require impractical storage space.
method SQUEAK uses unnormalized ridge leverage scores for incremental updates.
result Space complexity improved with constant factor worse than exact RLS.
We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), with mini-batches and multi-passes over the data. We show that optimal generalization error bounds c…
This paper explores saturation effects in spectral algorithms over large dimensions.
problem Saturation effects in spectral algorithms over large dimensions.
method Improved minimax lower bound and gradient flow with early stopping strategy.
result Exact convergence rates of spectral algorithms in large dimensional settings.
AGOP from KRR recovers central subspace in fewer samples than needed for prediction.
problem Recovering low-dimensional structure in multi-index polynomial functions.
method Fit kernel ridge regression and compute AGOP from the fitted predictor.
result AGOP's top r eigenspace recovers the central subspace in n≍dp+δ samples. Optimal CATE estimation with structured contrast functions using KRR.
problem Estimating CATEs with complex response functions in RKHS.
method Unified two-stage kernel ridge regression method for structured contrast functions.
result Minimax rates governed by contrast function complexity, enabling adaptation.
In this paper, we propose a fast surrogate leverage weighted sampling strategy to generate refined random Fourier features for kernel approximation. Compared to the current state-of-the-art method that uses the leverage weighted scheme [Li-ICML2019], our new strategy is simpler and more effective. It uses kernel alignm…
KIP meta-learning compresses datasets significantly.
problem Training data size and quality issues in machine learning.
method Kernel Inducing Points (KIP) for dataset compression.
result Significant reduction in dataset size with similar model performance.
The study examines Kernel Ridge Regression error rates across noiseless and noisy conditions.
problem Characterizing Kernel Ridge Regression error rates in different noise levels.
method Unified analysis of Kernel Ridge Regression under various noise and regularization conditions.
result A crossover from noiseless to noisy error rates is observed as sample complexity increases.
We consider the task of robust non-linear regression in the presence of both inlier noise and outliers. Assuming that the unknown non-linear function belongs to a Reproducing Kernel Hilbert Space (RKHS), our goal is to estimate the set of the associated unknown parameters. Due to the presence of outliers, common techni…
New findings on kernel regression in the quadratic regime, improving understanding of machine learning models.
problem Understanding kernel ridge regression in the quadratic asymptotic regime.
method Extended study of kernel regression to the quadratic regime, establishing approximation bounds and spectral distributions.
result Broad class of inner-product kernels exhibit behavior similar to a quadratic kernel, with precise asymptotic training and test errors characterized.
Method leverages data transfer for estimating CATE with KRR.
problem Leveraging findings from one study to estimate CATE in a different population.
method Overlap-adaptive transfer learning of CATE using kernel ridge regression.
result The method achieves superior efficiency and adaptability in estimating CATE.
Enhances supervised learning speed with KT algorithm.
problem Speed up supervised learning tasks with minimal loss.
method Generalizes kernel thinning to supervised learning, combining NW and KRR with KT.
result KT-based estimators offer superior computational and statistical efficiency.