# Dimensionality Reduction for General KDE Mode Finding

arXiv: https://arxiv.org/abs/2305.18755 · HTML: https://mlsanity.com/paper/2305.18755/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 31 references that are in the map.
- First posted on arXiv 30 May 2023.

## Builds on (most cited first, 4 of 4)

- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Sparse Approximation via Generating Point Sets](https://mlsanity.com/paper/1507.02574/) (2015)
- [Geometric Inference on Kernel Density Estimates](https://mlsanity.com/paper/1307.7760/) (2013)

## Built on by (most cited first, 2 of 2)

- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Entropy-MCMC: Sampling from Flat Basins with Ease](https://mlsanity.com/paper/2310.05401/) (2023)

## Abstract (arXiv)

Finding the mode of a high dimensional probability distribution D is a fundamental algorithmic problem in statistics and data analysis. There has been particular interest in efficient methods for solving the problem when D is represented as a mixture model or kernel density estimate, although few algorithmic results with worst-case approximation and runtime guarantees are known. In this work, we significantly generalize a result of (LeeLiMusco:2021) on mode approximation for Gaussian mixture models. We develop randomized dimensionality reduction methods for mixtures involving a broader class of kernels, including the popular logistic, sigmoid, and generalized Gaussian kernels. As in Lee et al.'s work, our dimensionality reduction results yield quasi-polynomial algorithms for mode finding with multiplicative accuracy (1-ε) for any ε > 0. Moreover, when combined with gradient descent, they yield efficient practical heuristics for the problem. In addition to our positive results, we prove a hardness result for box kernels, showing that there is no polynomial time algorithm for finding the mode of a kernel density estimate, unless mathitP = mathitNP. Obtaining similar hardness results for kernels used in practice (like Gaussian or logistic kernels) is an interesting future direction.