Smoothed Distance Kernels for MMDs and Applications in Wasserstein Gradient Flows

• URL: http://arxiv.org/abs/2504.07820v1
• Date: Thu, 10 Apr 2025 14:57:33 GMT
• Title: Smoothed Distance Kernels for MMDs and Applications in Wasserstein Gradient Flows
• Authors: Nicolaj Rux, Michael Quellmalz, Gabriele Steidl,
• Abstract summary: Negative distance kernels $K(x,y) := - |x-y|$ were used in the definition of maximum mean discrepancies (MMDs) in statistics.<n>We propose a new kernel which keeps the favorable properties of the negative distance kernel as being conditionally positive definite of order one.
• Score: 1.3654846342364308
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Negative distance kernels $K(x,y) := - \|x-y\|$ were used in the definition of maximum mean discrepancies (MMDs) in statistics and lead to favorable numerical results in various applications. In particular, so-called slicing techniques for handling high-dimensional kernel summations profit from the simple parameter-free structure of the distance kernel. However, due to its non-smoothness in $x=y$, most of the classical theoretical results, e.g. on Wasserstein gradient flows of the corresponding MMD functional do not longer hold true. In this paper, we propose a new kernel which keeps the favorable properties of the negative distance kernel as being conditionally positive definite of order one with a nearly linear increase towards infinity and a simple slicing structure, but is Lipschitz differentiable now. Our construction is based on a simple 1D smoothing procedure of the absolute value function followed by a Riemann-Liouville fractional integral transform. Numerical results demonstrate that the new kernel performs similarly well as the negative distance kernel in gradient descent methods, but now with theoretical guarantees.

Related papers

• On the Approximation of Kernel functions [0.0]
  The paper addresses approximations of the kernel itself. For the Hilbert Gauss kernel on the unit cube, the paper establishes an upper bound of the associated eigenfunctions. This improvement confirms low rank approximation methods such as the Nystr"om method.
  arXiv  Detail & Related papers  (2024-03-11T13:50:07Z)
• Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms [0.0]
  Kernel-based methods are heavily used in machine learning. They suffer from $O(N2)$ complexity in the number $N$ of considered data points. We propose an approximation procedure, which reduces this complexity to $O(N)$.
  arXiv  Detail & Related papers  (2024-01-16T10:31:27Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• On The Relative Error of Random Fourier Features for Preserving Kernel Distance [7.383448514243228]
  We show that for a significant range of kernels, including the well-known Laplacian kernels, RFF cannot approximate the kernel distance with small relative error using low dimensions. We make the first step towards data-oblivious dimension-reduction for general shift-invariant kernels, and we obtain a similar $mathrmpoly(epsilon-1 log n)$ dimension bound for Laplacian kernels.
  arXiv  Detail & Related papers  (2022-10-01T10:35:12Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
  We show that in the low-data regime $ND$, the Gram matrix can be decomposed in a manner that reduces the cost of inference to $mathcalO(N2D + (N2)3)$. We demonstrate this potential in a variety of tasks relevant for machine learning, such as optimization and Hamiltonian Monte Carlo with predictive gradients.
  arXiv  Detail & Related papers  (2021-02-15T13:24:41Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)
• RFN: A Random-Feature Based Newton Method for Empirical Risk Minimization in Reproducing Kernel Hilbert Spaces [14.924672048447334]
  Large-scale finite-sum problems can be solved using efficient variants of Newton method, where the Hessian is approximated via sub-samples of data. In this paper, we observe that for this class of problems, one can naturally use kernel approximation to speed up the Newton method. We provide a novel second-order algorithm that enjoys local superlinear convergence and global linear convergence.
  arXiv  Detail & Related papers  (2020-02-12T01:14:44Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)
• Kernel Selection for Modal Linear Regression: Optimal Kernel and IRLS Algorithm [8.571896191090744]
  We show that a Biweight kernel is optimal in the sense of minimizing an mean squared error of a resulting MLR parameter. Secondly, we provide a kernel class for which algorithm iteratively reweighted least-squares algorithm (IRLS) is guaranteed to converge.
  arXiv  Detail & Related papers  (2020-01-30T03:57:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.