Dimensionality Reduction for General KDE Mode Finding

Xinyu Luo, Christopher Musco, Cas Widdershoven

    Research output: Contribution to journalConference articlepeer-review

    Abstract

    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 (Lee et al., 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 P = NP. Obtaining similar hardness results for kernels used in practice (like Gaussian or logistic kernels) is an interesting future direction.

    Original languageEnglish (US)
    Pages (from-to)23067-23082
    Number of pages16
    JournalProceedings of Machine Learning Research
    Volume202
    StatePublished - 2023
    Event40th International Conference on Machine Learning, ICML 2023 - Honolulu, United States
    Duration: Jul 23 2023Jul 29 2023

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Control and Systems Engineering
    • Statistics and Probability

    Fingerprint

    Dive into the research topics of 'Dimensionality Reduction for General KDE Mode Finding'. Together they form a unique fingerprint.

    Cite this