Kernel interpolation is inconsistent for norms with smoothness above a constant.
problem Inconsistency of kernel interpolation in reproducing kernel Hilbert spaces.
method Lower bounds for generalization error in Sobolev norms.
result Kernel interpolation is always inconsistent for norms with smoothness above a constant.
We introduce a new structured kernel interpolation (SKI) framework, which generalises and unifies inducing point methods for scalable Gaussian processes (GPs). SKI methods produce kernel approximations for fast computations through kernel interpolation. The SKI framework clarifies how the quality of an inducing point a…
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,γ)-phase diagram of large-dimensional kernel interpolation. SoftKI combines SKI and variational methods for scalable GP regression.
problem Scalable Gaussian Process regression on high-dimensional datasets.
method SoftKI approximates kernel via softmax interpolation from a smaller number of learned points.
result SoftKI is competitive with other approximated GP methods for modest data dimensions.
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 method interpolates high-dimensional scattered data using kernel theory.
problem Scattered data in high-dimensional spaces defy traditional distributional assumptions.
method Kernel interpolation framework based on integral operator theory.
result Spectra of kernel matrices predict performance of interpolation methods.
DSoftKI scales GP regression with full derivative observations.
problem Efficiently fitting and predicting full derivative observations in Gaussian Processes.
method Extends SoftKI by using local temperature vectors for interpolation, enabling encoding of local directional sensitivity.
result DSoftKI achieves accurate predictions and scales to larger datasets with full derivative observations.
We show that minimum-norm interpolation in the Reproducing Kernel Hilbert Space corresponding to the Laplace kernel is not consistent if input dimension is constant. The lower bound holds for any choice of kernel bandwidth, even if selected based on data. The result supports the empirical observation that minimum-norm …
New method interpolates training data and is consistent for various data distributions.
problem Establishing generalization guarantees for ensemble methods in the interpolating regime.
method Developed manifold-Hilbert kernel for Riemannian manifolds and used it in ensemble classification.
result Consistent ensemble classification method for broad data distributions.
Strong inductive biases prevent harmless interpolation in overparameterized models.
problem Understanding the conditions under which overparameterized models can interpolate noise without overfitting.
method Theoretical analysis of high-dimensional kernel regression and deep neural networks, focusing on the role of inductive biases.
result The strength of an estimator's inductive bias determines whether interpolation is harmless or requires fitting noise for good generalization.
Paper shows SVMs can interpolate data in various settings.
problem Understanding SVM performance and generalization.
method Flexible analysis framework for proving SVM interpolation in diverse settings.
result Support vector machines can interpolate data in many cases not previously covered.
In the absence of explicit regularization, Kernel "Ridgeless" Regression with nonlinear kernels has the potential to fit the training data perfectly. It has been observed empirically, however, that such interpolated solutions can still generalize well on test data. We isolate a phenomenon of implicit regularization for…
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.
Kernel interpolation speeds up online Gaussian process updates.
problem Efficiently updating Gaussian process posteriors with new data.
method Structured kernel interpolation for constant-time updates.
result Exact inference maintained with constant-time updates.
We study the risk of minimum-norm interpolants of data in Reproducing Kernel Hilbert Spaces. Our upper bounds on the risk are of a multiple-descent shape for the various scalings of d=nα, α∈(0,1), for the input dimension d and sample size n. Empirical evidence supports our finding that minimum-norm interpo…
A fundamental task in kernel methods is to pick nodes and weights, so as to approximate a given function from an RKHS by the weighted sum of kernel translates located at the nodes. This is the crux of kernel density estimation, kernel quadrature, or interpolation from discrete samples. Furthermore, RKHSs offer a conven…
This paper analyzes error in SKI for Gaussian Processes, providing conditions for linear time inference.
problem Lack of rigorous theoretical error analysis for SKI.
method Proved error bounds for SKI Gram matrix, examined error effects, provided practical guidelines.
result Identified two dimensionality regimes for SKI's scalability-accuracy trade-offs.
Geometric theory connects machine learning classifiers to differential geometry.
problem Classifying data points in machine learning.
method Mapping binary classification to vector bundles and differential geometry.
result Harmonic interpolation solves RKHS interpolation problems.
Study on learning properties of scale-dependent kernels controlling stability and error.
problem Understanding the learning properties of scale-dependent kernels in nonparametric ridge-less least squares.
method Combines probabilistic results with interpolation theory to analyze stability and error.
result Different regimes of learning error depending on sample size and data dimension.
Recent work shows that inference for Gaussian processes can be performed efficiently using iterative methods that rely only on matrix-vector multiplications (MVMs). Structured Kernel Interpolation (SKI) exploits these techniques by deriving approximate kernels with very fast MVMs. Unfortunately, such strategies suffer …
New study finds many neural networks are not benignly overfitting.
problem Understanding the behavior of overfitting in neural networks.
method Exploring kernel ridge regression and deep neural networks to identify overfitting behaviors.
result Many interpolating methods, including neural networks, exhibit tempered overfitting rather than benign or catastrophic.
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.
Improved forecasting for irregularly-sampled time series using kernel flows.
problem Forecasting dynamical systems from irregularly-sampled time series data.
method Directly approximating the vector field using time differences in data-adapted kernels.
result Significant improvement in forecasting accuracy compared to classical methods.
Neural networks can interpolate random data but still generalize well, studied in the NT regime.
problem Understanding how neural networks interpolate random labels and generalize well in the overparametrized regime.
method Characterization of the eigenstructure of the empirical NT kernel and generalization error of NT ridge regression.
result The generalization error is well approximated by polynomial ridge regression with an increased regularization parameter.
The paper examines how kernel approximations affect Gaussian process regression in large data applications.
problem Effect of kernel approximations on Gaussian process regression in large data applications.
method Unified framework to analyze Gaussian process regression under computational and epistemic misspecification.
result Theoretical analysis of Gaussian process regression under various misspecifications.
Continuous-time interpolation of volatility surfaces preserving mixtures and arbitrage-free.
problem Interpolation of volatility surfaces
method Constructing a mixture-preserving, arbitrage-free interpolation
result Lifts Brigo-Mercurio to time-varying weights with additive cost
New method efficiently interpolates nonparametric density estimators.
problem Efficient evaluation of nonparametric density estimators.
method Piecewise multivariate polynomial interpolation scheme.
result New estimator with low space requirements and efficient querying.
Many modern machine learning models are trained to achieve zero or near-zero training error in order to obtain near-optimal (but non-zero) test error. This phenomenon of strong generalization performance for "overfitted" / interpolated classifiers appears to be ubiquitous in high-dimensional data, having been observed …
The paper shows how multi-task learning in neural networks is similar to kernel regression and Hilbert spaces.
problem Understanding the solutions to multi-task shallow ReLU neural network learning problems.
method Analyzing the properties of solutions to multi-task shallow ReLU neural network learning problems, proving uniqueness and equivalence to minimum-norm interpolation problems in Hilbert spaces.
result The solutions to multi-task neural network interpolation problems are almost always unique and coincide with the solution to a minimum-norm interpolation problem in a Sobolev (Reproducing Kernel) Hilbert Space.
The paper analyzes kernel classifiers' performance in Sobolev spaces and proves their optimality.
problem Theoretical analysis of kernel classifiers' performance in Sobolev spaces.
method Deriving upper and lower bounds on classification excess risk using kernel regression theory and estimating interpolation smoothness.
result The proposed kernel classifier is optimal in Sobolev spaces, with theoretical bounds confirmed by real data.
IIC provides a PAC-Bayes bound for interpolating models, revealing factors affecting generalization.
problem Theoretical challenges in understanding overparameterized models and their performance.
method PAC-Bayesian perspective applied to the Interpolating Information Criterion (IIC).
result Test error for overparameterized models achieving zero training error depends on various factors.
Study improves sugarcane plot prediction using data interpolation.
problem Predicting adventive plants in sugarcane plots with limited data.
method Interpolation techniques (Gaussian processes, kriging) for geo-referenced data augmentation.
result GP-COMB outperforms other methods with less additional data.
Estimates individual treatment effects using gradient interpolation and kernel smoothing.
problem Estimating individualized continuous treatment effects in observational data.
method Augment training data with independently sampled treatments and inferred counterfactual outcomes using gradient interpolation and kernel smoothing.
result Our method outperforms state-of-the-art methods on counterfactual estimation error.
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.
Paper calculates eigenvalue decay rates for neural network kernels on general domains.
problem Determining eigenvalue decay rates for neural network kernels on arbitrary domains.
method Proved dynamics of wide neural networks approximates NTK on general domains, used minimax optimality and interpolation spaces.
result Provided strategy to calculate eigenvalue decay rates for neural network kernels.
Learning can be seen as approximating an unknown function by interpolating the training data. Kriging offers a solution to this problem based on the prior specification of a kernel. We explore a numerical approximation approach to kernel selection/construction based on the simple premise that a kernel must be good if t…
The paper explains how certain neural network models can still perform well even when they fit training data perfectly.
problem Understanding how overparametrized models can generalize well despite fitting training data perfectly.
method Develops a framework to upper bound regression and classification risk in a reproducing kernel Hilbert space, providing conditions for harmless interpolation.
result Shows that harmless interpolation can occur in more general settings like bounded orthonormal systems, not just independent features.
The paper improves interpolation in generative models by using specific base distributions.
problem Unexpected side effects in linear interpolations of normalizing flows.
method Enforces a specific manifold using Dirichlet and von Mises-Fisher base distributions.
result Superior performance in terms of bits per dimension, FID, and KID scores for interpolation.
New learning rates derived for Tikhonov-regularized problems without kernel assumptions.
problem Learning rates for Tikhonov-regularized learning problems.
method Minimax adaptive rates derived using Fourier isocapacitary condition and interpolation theory.
result Derivation of minimax adaptive rates without requiring kernel assumptions.
Neural networks trained with PGD achieve sharp regression rates in interpolation spaces.
problem Nonparametric regression using over-parameterized neural networks in interpolation spaces.
method Over-parameterized two-layer neural networks trained with Preconditioned Gradient Descent (PGD) and early stopping.
result Achieves a sharp regression rate of \(\cO(n^{-\frac{2αs'}{2αs'+1}})\) in interpolation spaces \(\bth{\cH_K}^{s'}\).
ResNets promote smoother interpolations than MLPs, enhancing generalization.
problem Understanding the difference in smoothness between ResNets and MLPs.
method Neural Tangent Kernel (NTK) analysis during gradient descent training.
result ResNet's NTK results in smoother interpolations than MLPs.
SKI speeds up Toeplitz Neural Networks by avoiding explicit decay bias and using frequency response.
problem Efficiently compute and update Toeplitz matrices in neural networks.
method Sparse plus low-rank decomposition, asymmetric SKI, frequency response modeling.
result Achieved significant speedup with minimal performance loss.
The expressive power of Gaussian processes depends heavily on the choice of kernel. In this work we propose the novel harmonizable mixture kernel (HMK), a family of expressive, interpretable, non-stationary kernels derived from mixture models on the generalized spectral representation. As a theoretically sound treatmen…
This paper introduces an interpolation-based method, called the reconstruction approach, for nonparametric regression. Based on the fact that interpolation usually has negligible errors compared to statistical estimation, the reconstruction approach uses an interpolator to parameterize the regression function with its …
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.
Paper analyzes mistake and generalization of MNIC classifiers.
problem Understanding the performance of interpolating classifiers.
method Elementary analyses of MNIC's regret and generalization.
result MNIC generalizes with a rate proportional to the norm of the interpolating solution and inversely proportional to the number of data points.
Proposes a novel graph signal model using narrowband kernels.
problem Graph signals with multiple concentrated frequency regions.
method Jointly learns graph signal model parameters and coefficients.
result Joint learning improves signal interpolation accuracy.
Gaussian processes are rich distributions over functions, which provide a Bayesian nonparametric approach to smoothing and interpolation. We introduce simple closed form kernels that can be used with Gaussian processes to discover patterns and enable extrapolation. These kernels are derived by modelling a spectral dens…