A general technique for approximating high-dimensional empirical kernel matrices

Chiraag Kaushik, Justin Romberg, Vidya Muthukumar · 2025

Read A general technique for approximating high-dimensional empirical kernel matrices by Chiraag Kaushik, Justin Romberg, Vidya Muthukumar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03892.txt.

Introduction

Chiraag Kaushik, Justin Romberg, and Vidya Muthukumar give a general technique for approximating high-dimensional empirical kernel matrices, a core object in kernel methods. Their bounds target the expected operator norm of a random kernel matrix under broad conditions on the kernel function.

Decoupling results for U-statistics and a non-commutative Khintchine inequality yield upper and lower bounds from scalar kernel statistics and a correlation kernel matrix. Applied to inner-product kernels, the method simplifies older moment-based proofs and gives tighter results, including for anisotropic Gaussian data. A sharper lower bound on the bias of kernel regression with such data follows from the same techniques.

Catalog record

CREATORChiraag Kaushik, Justin Romberg, Vidya Muthukumar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-03892

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A general technique for approximating high-dimensional empirical kernel matrices Chiraag Kaushik, Justin Romberg, Vidya Muthukumar Abstract We present simple, user-friendly bounds for the expected operator norm of a random kernel matrix under general conditions on the kernel function k ⁡ ( ⋅ , ⋅ ) k(\cdot,\cdot) . Our approach uses decoupling results for U-statistics and the non-commutative Khintchine inequality to obtain upper and lower bounds depending only on scalar statistics of the kernel function and a “correlation kernel” matrix corresponding to k ⁡ ( ⋅ , ⋅ ) k(\cdot,\cdot) . We then apply our method to provide new, tighter approximations for inner-product kernel matrices on general high-dimensional data, where the sample size and data dimension are polynomially related. Our method obtains simplified proofs of existing results that rely on the moment method and combinatorial arguments while also providing novel approximation results for the case of anisotropic Gaussian data. Finally, using similar techniques to our approximation result, we show a tighter lower bound on the bias of kernel regression with anisotropic Gaussian data. 1 Introduction Kernel methods are commonly employed to solve a range of problems in engineering, science, statistics, and machine learning [ 49 ] . Traditionally, much of the power of these methods has been derived from the fact that, in classical statistical settings with fixed data dimension, the eigenvalues of the empirical kernel matrix derived from samples behave akin to those of the original kernel integral operator [ 30 ] . Together with the universal approximation properties of several common kernels [ 50 , 39 ] , minimax-optimal rates can be derived for a broad class of target functions for kernel ridge regression and the kernel support-vector-machine [ 39 , 7 ] . This is no longer the case when kernel methods are applied on high-dimensional data. Indeed, a seminal result of El Karoui [ 28 ] showed that in the proportional regime where the number of samples is proportional to the data dimension ( n\asymp d ), a large family of kernel methods equipped with an inner-product kernel (i.e., a kernel of the form k(x,z)=h(\langle x,z\rangle/d) ) are restricted in their behavior to linear models. The crux of this result is a proof that the empirical kernel matrix is well-approximated in operator norm by an affine (constant + linear) kernel matrix plus a multiple of the identity matrix. This can be viewed as a type of curse of dimensionality for kernel methods, where the nonlinear approximation power becomes negligible when the dimension of the data is proportional to the sample size. More recently, equivalences between certain types of wide neural networks and kernel methods [ 26 , 11 ] , the occurrence of phenomena like benign overfitting and double descent in kernel models [ 5 , 24 , 36 , 38 , 37 ] , and the increasing use of iterative kernel machines [ 46 , 57 ] to adapt to hidden low-dimensional structure in modern machine learning tasks have spurred increased interest in sharp analyses of these methods in high-dimensional settings. A flexible but delicate setting that has received substantial recent attention is the polynomial scaling regime n\asymp d^{q} , where the number of samples scales as a polynomial power q\geq 1 of the data dimension. A reasonable conjecture would be that kernel methods now can approximate only polynomial functions of the data up to degree \lfloor q\rfloor . However, showing this is challenging beyond special cases ( q=1 and q=2 ) and/or specialized assumptions on the data (uniform on the sphere/Boolean hypercube) due to the intricate dependencies between entries of the empirical kernel matrix. Indeed, even the proofs of the results in these specialized settings, e.g., [ 23 , 45 ] involve intricate applications of the moment/trace method and combinatorial arguments. The only more general-purpose result shows an approximation barrier of degree- \lfloor 2q\rfloor instead of degree- \lfloor q\rfloor , and the factor of 2 is not expected to be tight [ 16 ] . The central goal of this work is to provide a sharp and general-purpose technique for kernel matrix approximation, applicable in high-dimensional regimes like the above. Specifically, we aim to provide a general technique that can be used to show tight bounds on \E[||\bm{K}-\bar{\bm{K}}||] for any candidate approximator \bar{\bm{K}} — thereby providing conditions under which \bar{\bm{K}} is a faithful approximation of \bm{K} in operator norm. Often, the approximator \bar{\bm{K}} has lower-dimensional structure of some form (e.g., lower-degree, as mentioned above) and is a useful object for studying generalization in kernel ridge regression and its recent iterative extensions [ 57 ] . In fact, approximation results of this form often constitute the first step in precisely characterizing the test error, which reduces to studying the spectrum of the often simpler matrix \bar{\bm{K}} . Contributions: In this paper, we first provide a general-purpose bound on the the expected operator norm of an empirical kernel matrix under minimal distributional assumptions and mild integrability conditions on the kernel function k(\cdot,\cdot) . We then focus especially on applying our result to inner-product kernels that include those derived as the asymptotic limit of random-feature models/wide neural networks when the number of features/width tends to infinity. For such kernels, our technique recovers the specialized kernel matrix approximation results of [ 23 , 45 ] in a simpler manner, either matching or improving the best known approximation rates, and significantly improves the approximation barrier from \lfloor 2q\rfloor to \lfloor 4q/3\rfloor on general anisotropic Gaussian data. We finally use similar techniques to obtain new lower bounds for the bias of kernel ridge regression estimates in these high-dimensional settings. While we apply our bound primarily to these types of approximation problems, we have not seen our general kernel matrix bounds stated in this form in the existing literature, and we believe they may find broader use in the analysis of kernel methods on high-dimensional data. Our contributions are listed in more detail below: (1) Our main result, Theorem 1 , provides upper and lower bounds on the expected operator norm of a random kernel matrix under general measurability conditions on the kernel function k . Our proof relies on a combination of decoupling inequalities for U-statistics and the non-commutative Khintchine inequality and obtains bounds depending on simple scalar statistics of k and a “correlation kernel” matrix. (2) We argue that the “correlation kernel” matrix appearing in our general bound has a simple form in several common scenarios that arise in the study of high-dimensional kernel regression in the regime n\asymp d^{q} , such as Gegenbauer polynomial, hypercubic Gegenbauer polynomial, and Hermite polynomial kernels. For the already studied cases of data that is uniform on the sphere (corresponding to Gegenbauer polynomial approximation) and uniform on the Boolean hypercube (corresponding to hypercubic Gegenbauer approximation), we recover existing approximation-theoretic results with respect to low-degree polynomial kernel matrices of degree up to \lfloor q\rfloor [ 23 , 38 ] as an elementary corollary of Theorem 1 (compared to the involved moment/trace method and combinatorial arguments that appear in the proofs of [ 23 , 38 ] ). (3) We then turn to the case of anisotropic Gaussian data 1 1 1 Like [ 45 ] , we can relax the anisotropic Gaussian assumption to a

Read the complete text