Dynamic Maintenance of Kernel Density Estimation Data Structure: From
Practice to Theory
- URL: http://arxiv.org/abs/2208.03915v2
- Date: Tue, 13 Feb 2024 19:59:56 GMT
- Title: Dynamic Maintenance of Kernel Density Estimation Data Structure: From
Practice to Theory
- Authors: Jiehao Liang, Zhao Song, Zhaozhuo Xu, Junze Yin, Danyang Zhuo
- Abstract summary: Kernel density estimation (KDE) stands out as a challenging task in machine learning.
Recently, there has been a growing trend of using data structures for efficient KDE.
In this work, we focus on the dynamic maintenance of KDE data structures with robustness to adversarial queries.
- Score: 16.460386321121945
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Kernel density estimation (KDE) stands out as a challenging task in machine
learning. The problem is defined in the following way: given a kernel function
$f(x,y)$ and a set of points $\{x_1, x_2, \cdots, x_n \} \subset \mathbb{R}^d$,
we would like to compute $\frac{1}{n}\sum_{i=1}^{n} f(x_i,y)$ for any query
point $y \in \mathbb{R}^d$. Recently, there has been a growing trend of using
data structures for efficient KDE. However, the proposed KDE data structures
focus on static settings. The robustness of KDE data structures over dynamic
changing data distributions is not addressed. In this work, we focus on the
dynamic maintenance of KDE data structures with robustness to adversarial
queries. Especially, we provide a theoretical framework of KDE data structures.
In our framework, the KDE data structures only require subquadratic spaces.
Moreover, our data structure supports the dynamic update of the dataset in
sublinear time. Furthermore, we can perform adaptive queries with the potential
adversary in sublinear time.
Related papers
- MOKD: Cross-domain Finetuning for Few-shot Classification via Maximizing Optimized Kernel Dependence [97.93517982908007]
In cross-domain few-shot classification, NCC aims to learn representations to construct a metric space where few-shot classification can be performed.
In this paper, we find that there exist high similarities between NCC-learned representations of two samples from different classes.
We propose a bi-level optimization framework, emphmaximizing optimized kernel dependence (MOKD) to learn a set of class-specific representations that match the cluster structures indicated by labeled data.
arXiv Detail & Related papers (2024-05-29T05:59:52Z) - Deep Equilibrium Based Neural Operators for Steady-State PDEs [100.88355782126098]
We study the benefits of weight-tied neural network architectures for steady-state PDEs.
We propose FNO-DEQ, a deep equilibrium variant of the FNO architecture that directly solves for the solution of a steady-state PDE.
arXiv Detail & Related papers (2023-11-30T22:34:57Z) - Fast Private Kernel Density Estimation via Locality Sensitive
Quantization [10.227538355037554]
We study efficient mechanisms for differentially private kernel density estimation (DP-KDE)
We show how the kernel can privately be approximated in time linear in $d$, making it feasible for high-dimensional data.
arXiv Detail & Related papers (2023-07-04T18:48:04Z) - KDEformer: Accelerating Transformers via Kernel Density Estimation [30.860357184928407]
In this paper, we introduce a new approach to exact computation of Dot-product attention mechanism.
We show that our proposed approach outperforms other attention approximations in terms of accuracy, memory, and runtime.
For image classification with T2T-ViT, we show over $18times$ speedup while the accuracy drop is less than $0.5%$.
arXiv Detail & Related papers (2023-02-05T18:23:49Z) - Differentiable and Transportable Structure Learning [73.84540901950616]
We introduce D-Struct, which recovers transportability in the discovered structures through a novel architecture and loss function.
Because D-Struct remains differentiable, our method can be easily adopted in existing differentiable architectures.
arXiv Detail & Related papers (2022-06-13T17:50:53Z) - ISDE : Independence Structure Density Estimation [0.0]
Multidimensional density estimation suffers from the curse of dimensionality.
We propose ISDE (Independence Structure Density Estimation), an algorithm designed to estimate a density and an undirected graphical model.
We show how it performs both quantitatively and qualitatively on real-world datasets.
arXiv Detail & Related papers (2022-03-18T08:01:04Z) - Generative Adversarial Learning via Kernel Density Discrimination [32.91091065436645]
We introduce Kernel Density Discrimination GAN (KDD GAN), a novel method for generative adversarial learning.
We define the Kernel Density Estimates directly in feature space and forgo the requirement of invertibility of the kernel feature mappings.
We show a boost in the quality of generated samples with respect to FID from 10% to 40% compared to the baseline.
arXiv Detail & Related papers (2021-07-13T15:52:10Z) - DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest
Neighbor Search [8.25574589820305]
We present an algorithm called Density Estimation from Approximate Nearest Neighbors (DEANN)
We apply ANN algorithms as a black box subroutine to compute an unbiased Density Estimation (KDE)
We show that our implementation outperforms state of the art implementations in all high dimensional datasets we considered.
arXiv Detail & Related papers (2021-07-06T17:11:28Z) - Deep Parametric Continuous Convolutional Neural Networks [92.87547731907176]
Parametric Continuous Convolution is a new learnable operator that operates over non-grid structured data.
Our experiments show significant improvement over the state-of-the-art in point cloud segmentation of indoor and outdoor scenes.
arXiv Detail & Related papers (2021-01-17T18:28:23Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
We re-interpret node aggregation from the perspective of kernel weighting.
We present a framework to consider feature similarity in an aggregation scheme.
We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
arXiv Detail & Related papers (2020-05-16T04:44:29Z) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees.
Our approach leads to significantly better bounds for datasets with known rates of singular value decay.
We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
arXiv Detail & Related papers (2020-02-21T00:43:06Z)
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.