High-dimensional kernel regression struggles due to rotational invariance.
problem Kernel ridge regression struggles in high dimensions due to rotational invariance.
method Analysis of kernel properties and their impact on high-dimensional data.
result Lower bound on generalization error for high-dimensional kernel regression.
Characterizes kernel interpolation in large dimensions, revealing optimal and sub-optimal regions.
problem Understanding the phase diagram of kernel interpolation in large dimensions.
method Characterization of variance and bias under various source conditions.
result Determined the ( s , γ ) (s,γ) ( s , γ ) -phase diagram of large-dimensional kernel interpolation. Study on kernel tests for high-dimensional data, focusing on MMD and CLT.
problem Asymptotic behavior of kernel two-sample tests in high dimensions and large samples.
method Maximum mean discrepancy (MMD) with isotropic kernels, deriving asymptotic expansions and CLT.
result Interplay between moment discrepancy and dimension-and-sample orders in kernel tests.
Study provides bounds for estimating intrinsic dimension using Gaussian kernels.
problem Estimating intrinsic dimension from data.
method Finite-sample concentration and anti-concentration bounds for Gaussian kernel sums.
result Explicit dependence on sample size, bandwidth, and geometric parameters.
Study shows that ridgeless Gaussian kernel regression overfits even with varying bandwidth or dimensionality.
problem Analyzing overfitting in Gaussian kernel ridgeless regression with varying bandwidth or dimensionality.
method Examined the behavior of minimum norm interpolating solutions for fixed and increasing dimensions under varying bandwidth and sample size.
result Ridgeless solutions are never consistent and can be worse than null predictor with large enough noise, even with varying bandwidth or dimensionality.
The paper identifies a K K K -theoretic obstruction for higher kernel dimensions of Dirac operators.
problem Identifying obstructions for higher kernel dimensions of Dirac operators.
method Using a fibre-wise Dirac operator and topological K K K -theory, the paper constructs a family of Fredholm operators and analyzes their Chern classes. result Chern classes of the K K K -class contain information about the kernel of the operators. Interpolation with Laplace kernel fails in low dimensions but succeeds in high dimensions.
problem Consistency of interpolation with Laplace kernels in low-dimensional settings.
method Minimum-norm interpolation in Reproducing Kernel Hilbert Space (RKHS) with Laplace kernel.
result Consistency of interpolation is a high-dimensional phenomenon.
Proposes an online method for high-dimensional streaming data.
problem Increasing variable dimensions with sample size in online kernel sliced inverse regression.
method Introduces approximate linear dependence condition and dictionary variable sets to address the problem. Transforms into online generalized eigen-decomposition problem and uses stochastic optimization for updates.
result Achieves close performance to batch processing kernel sliced inverse regression.
VC dimensions of group CNNs are infinite for certain kernels and groups.
problem Estimating the generalization capacity of group convolutional neural networks.
method Identifying precise VC dimension estimates for simple sets of group CNNs.
result Two-parameter families of convolutional neural networks have an infinite VC dimension for infinite groups and certain kernels.
Study on kernel regression risk in high dimensions using Pinsker bound.
problem Kernel regression risk in high-dimensional inner product spaces.
method Investigation of Pinsker bound for kernel regression on sphere S d \mathbb{S}^{d} S d with sample size n = α d γ ( 1 + o d ( 1 ) ) n = αd^γ(1+o_{d}(1)) n = α d γ ( 1 + o d ( 1 )) . result Exact minimax risk and Pinsker constant identified for kernel regression.
SKI accelerates GP inference with sparse grids to handle higher dimensions.
problem SKI scales poorly in high dimensions due to dense grid size.
method Sparse grids within SKI framework, novel matrix-vector multiplication algorithm.
result SKI can be scaled to higher dimensions while maintaining accuracy.
New divergences help audit DP in high dimensions.
problem Challenges in auditing DP in high-dimensional data.
method Propose kernel Rényi divergence and its regularized version for auditing.
result Regularized kernel Rényi divergence can be estimated from samples in high dimensions.
Adaptive kernel density estimation improves accuracy in high dimensions.
problem Challenges in high-dimensional density estimation with traditional methods.
method Pre-training a neural network to recommend location-adaptive kernels.
result Effective density estimation in high dimensions with improved accuracy.
Proves heat kernel superconvexity in hyperbolic space.
problem Heat kernel superconvexity in hyperbolic space.
method Proves conjecture by Bernstein in all dimensions.
result Analog of Huisken's monotonicity formula for mean curvature flow.
This paper improves coreset construction for kernel density estimates.
problem Approximating large kernel density estimates with smaller ones.
method Developed a coreset construction algorithm called kernel herding.
result Approximates kernel density estimates with much smaller point sets.
Study spectral properties of radial kernels for high-dimensional mixtures.
problem Understanding spectral properties of radial kernels for high-dimensional mixtures.
method High-dimensional analysis focusing on concentration properties of components in mixtures.
result Kernel PCA can successfully cluster mixtures with common means but different covariances, even in high dimensions.
New method speeds up Bayesian optimization in high dimensions.
problem High-dimensional expensive function optimization struggles.
method Structured automatic differentiation for kernel matrices.
result First-order Bayesian optimization scalable to high dimensions.
Study shows how to effectively predict functions on manifolds using kernel methods.
problem Regression on manifolds with limited data.
method Reproducing kernel Hilbert space methods, Weyl law, effective dimension.
result Kernel regression estimator yields minimax-optimal error bounds controlled by effective dimension.
Invariant kernels reduce rank and improve generalization across dimensions.
problem Symmetry in high-dimensional data impacts kernel matrix rank and learning algorithms.
method Compute invariant polynomial kernel ranks under various groups acting on data.
result Symmetry decreases kernel rank, making it independent of data dimension.
Optimizes differentially private kernel learning with random projection.
problem Privacy-preserving learning algorithms with optimal performance.
method Differentially private kernel ERM algorithm based on random projection in reproducing kernel Hilbert space.
result Achieves minimax-optimal excess risk rates for various loss functions.
New KCC-SDs improve distribution comparison in high dimensions.
problem Challenges in high-dimensional Stein discrepancies.
method Kernelized complete conditional Stein discrepancies (KCC-SDs).
result KCC-SDs outperform baselines in distinguishing distributions.
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.
Sliced kernelized Stein discrepancy improves goodness-of-fit tests and model learning in high dimensions.
problem The curse-of-dimensionality in kernelized Stein discrepancy (KSD).
method Sliced Stein discrepancy and its scalable variants using optimal one-dimensional projections.
result Significantly outperforms KSD and baselines in goodness-of-fit tests and improves model learning.
Eluder dimension and information gain are equivalent for reproducing kernel Hilbert spaces.
problem Complexity measures in bandit and reinforcement learning.
method Equivalence of eluder dimension and information gain for reproducing kernel Hilbert spaces.
result Eluder dimension and information gain are equivalent for reproducing kernel Hilbert spaces.
Kernelized Q-learning achieves good performance with minimal data.
problem Efficient Q-learning in high-dimensional spaces.
method Kernelized Q-learning framework with effective dimensionality.
result Concrete regret bounds for linear and Gaussian RBF kernels.
Proposes a new method to approximate kernel functions for large datasets.
problem Limited applicability of kernel methods for large scale datasets.
method Pseudo Random Fourier Features (PRFF) for reducing feature dimensions and improving performance.
result Improves prediction performance and reduces feature dimensions compared to RFF.
New insights into why neural networks can overfit without interpolating data.
problem Understanding why neural networks can overfit without interpolating data in fixed dimensions.
method Analyzing the smoothness of estimators and their derivatives.
result Benign overfitting is possible with estimators that have large enough derivatives, not just in high dimensions but also in fixed dimensions.
Unified theory for kernel regression generalizes well under realistic assumptions.
problem Analyzing kernel regression under realistic conditions.
method Unified theory providing rigorous bounds for various settings.
result Self-regularization phenomenon in kernel matrices enables good generalization.
This paper consists of two parts. In the first part we show that in odd dimension, as well as in even dimension below the critical weight (i.e. half the dimension), the logarithmic singularities of Schwartz kernels and Green kernels of conformal invariant pseudodifferential operators are linear combinations of Weyl con…
A new kernel-based nonconformity score improves multivariate prediction regions.
problem Tackling the challenge of compressing multivariate residual vectors into scalars while preserving geometric structure.
method Introducing a Multivariate Kernel Score (MKS) that decomposes into an anisotropic MMD, providing finite-sample coverage guarantees and convergence rates.
result The MKS produces prediction regions that explicitly adapt to geometric structure, reducing volume compared to ellipsoidal baselines.
New method for reducing dimensions of distributional data.
problem Nonlinear sufficient dimension reduction for distribution-on-distribution regression.
method Building universal kernels on metric spaces to characterize conditional independence.
result Method outperforms competing methods in synthetic and real data applications.
New framework estimates eigenvalues of kernel matrices without full matrix construction.
problem Estimating eigenvalues of large kernel matrices efficiently.
method Eigenvalue quantile estimation framework for kernel matrices with quick decay.
result Validates framework with empirical evidence and proves interlacing theorem.
We consider fast kernel summations in high dimensions: given a large set of points in d d d dimensions (with d ≫ 3 d \gg 3 d ≫ 3 ) and a pair-potential function (the {\em kernel} function), we compute a weighted sum of all pairwise kernel interactions for each point in the set. Direct summation is equivalent to a (dense) matrix-vec…
This paper proposes a novel kernel approach to linear dimension reduction for supervised learning. The purpose of the dimension reduction is to find directions in the input space to explain the output as effectively as possible. The proposed method uses an estimator for the gradient of regression function, based on the…
Bayesian optimization in one dimension achieves O ( T log T ) O(\sqrt{T\log T}) O ( T log T ) regret.
problem Optimizing a function in one dimension with Gaussian process prior and noise.
method Theoretical analysis of Gaussian process and Gaussian sampling noise.
result Cumulative regret up to time T T T is O ( T log T ) O(\sqrt{T\log T}) O ( T log T ) under mild assumptions. Novel approach to OT using kernel mean embeddings controls overfitting and achieves dimension-free sample complexity.
problem Consistently estimate optimal transport plan from samples.
method Pose OT as learning kernel mean embedding, employ MMD regularization.
result ε-optimal recovery of transport plan and map with dimension-free sample complexity.
Solves kernel dimension reduction while making features interpretable.
problem Making kernel dimension reduction methods interpretable.
method Projects onto a subspace before kernel feature mapping, using ISM for optimization.
result Extends ISM's theoretical guarantees to a family of kernels, enabling broader applicability.
Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given n n n samples, the time and space complexity of computing the KRR estimate scale as O ( n 3 ) \mathcal{O}(n^3) O ( n 3 ) and O ( n 2 ) \mathcal{O}(n^2) O ( n 2 ) respectively, and so is prohibitive in many cases. We prop…
Researchers compute heat kernel coefficients for 2D diffusion operators.
problem Analyzing heat kernel coefficients for 2D hypoelliptic operators.
method Explicit computation of heat kernel coefficients and interpretation in terms of curvature.
result Interpretation of heat kernel asymptotics for non-sub-Riemannian operators.
The paper analyzes high-dimensional kernel regression, showing different risk curves based on data and regularization.
problem Characterizing generalization properties of high-dimensional kernel ridge regression.
method Bias-variance decomposition of the expected excess risk, considering different regularization schemes and data eigen-profiles.
result The risk curve of kernel regression can be double-descent-like, bell-shaped, or monotonic, depending on n, d, and regularization level.
CobBO optimizes expensive functions in high dimensions by using a two-stage kernel approach.
problem Bayesian optimization struggles in high dimensions due to computational inefficiency.
method Coordinate backoff Bayesian Optimization with two-stage kernels.
result CobBO finds solutions comparable to or better than other methods in high dimensions.
Improves probability distribution compression with KT algorithm.
problem Efficiently compressing probability distributions.
method Kernel thinning (KT) algorithm with four improvements.
result KT yields tighter, dimension-free guarantees for any kernel.
Study on optimal rate of kernel regression for large-dimensional data.
problem Characterizing the upper and lower bounds of kernel regression for large-dimensional data.
method Using Mendelson complexity and metric entropy, the study characterizes the upper and lower bounds of kernel regression for large-dimensional data.
result The minimax rate of the excess risk of kernel regression is \( n^{-1/2} \) for \( n \asymp d^γ \) with \( γ=2, 4, 6, 8, \cdots \).
A new GP inference method using simplices for high-dimensional data.
problem Scalable Gaussian Processes in high dimensions.
method Developed a Simplex-GP method using a sparse simplicial grid to accelerate MVMs.
result Significantly faster GP inference in high dimensions compared to SKI.
The study shows inner-product kernels behave similarly to binary kernels in high dimensions.
problem Understanding the behavior of inner-product kernels in high-dimensional data.
method Investigation of eigenspectrum under binary mixture model using random matrix theory.
result The eigenspectrum of inner-product kernels is asymptotically equivalent to binary kernels.
A new, fast kernel test for large data.
problem Efficient kernel two-sample tests for high-dimensional, large-scale data.
method A new kernel-based test that is computationally efficient and robust to high dimensions.
result The new test performs well across various alternatives and dimensions.
Study analyzes learnability of RKHS under L∞ norm for kernel methods.
problem Understand performance of kernel methods and random feature models.
method Relate L∞ learnability to kernel spectrum decay and establish sample complexity bounds.
result Conditions for efficient L∞ learning of RKHS identified.
Kernel balancing weights are generalized as KRRR, providing better confidence intervals for treatment effects.
problem Lack of generalization error, correct feature specification, and limited to average effects.
method Interpreting kernel balancing weights as KRRR, relaxing feature specification, and extending Gaussian approximation.
result KRRR provides strong generalization properties and justifies confidence sets for causal functions.