Relative entropy coding (REC) algorithms encode a random sample following a
target distribution $Q$, using a coding distribution $P$ shared between the
sender and receiver. Sadly, general REC algorithms suffer from prohibitive
encoding times, at least on the order of $2^{D_{\text{KL}}[Q||P]}$, and faster
algorithms are limited to very specific settings. This work addresses this
issue by introducing a REC scheme utilizing space partitioning to reduce
runtime in practical scenarios. We provide theoretical analyses of our method
and demonstrate its effectiveness with both toy examples and practical
applications. Notably, our method successfully handles REC tasks with
$D_{\text{KL}}[Q||P]$ about three times what previous methods can manage and
reduces the compression rate by approximately 5-15\% in VAE-based lossless
compression on MNIST and INR-based lossy compression on CIFAR-10 compared to
previous methods, significantly improving the practicality of REC for neural
compression.

使用空间分割减少运行时间的相对熵编码（REC）算法可成功处理具有三倍于先前方法的 KL 散度，并将压缩率与先前方法相比提高了约 5-15％，显著改善了神经压缩中的 REC 方法的实用性。

加速相对熵编码的空间分割

Accelerating Relative Entropy Coding with Space Partitioning

Creation of a synthetic dataset that faithfully represents the data
distribution and simultaneously preserves privacy is a major research
challenge. Many space partitioning based approaches have emerged in recent
years for answering statistical queries in a differentially private manner.
However, for synthetic data generation problem, recent research has been mainly
focused on deep generative models. In contrast, we exploit space partitioning
techniques together with noise perturbation and thus achieve intuitive and
transparent algorithms. We propose both data independent and data dependent
algorithms for $\epsilon$-differentially private synthetic data generation
whose kernel density resembles that of the real dataset. Additionally, we
provide theoretical results on the utility-privacy trade-offs and show how our
data dependent approach overcomes the curse of dimensionality and leads to a
scalable algorithm. We show empirical utility improvements over the prior work,
and discuss performance of our algorithm on a downstream classification task on
a real dataset.

提出了基于空间划分技术的差分隐私合成数据生成算法，可以保护数据隐私并生成与原始数据类似的数据，具有可解释性、透明性和可扩展性，并且在实验中表现出相比之前方法更优的效果。

使用 KD 树实现差分隐私合成数据

Differentially Private Synthetic Data Using KD-Trees

Existing methods for retrieving k-nearest neighbours suffer from the curse of
dimensionality. We argue this is caused in part by inherent deficiencies of
space partitioning, which is the underlying strategy used by most existing
methods. We devise a new strategy that avoids partitioning the vector space and
present a novel randomized algorithm that runs in time linear in dimensionality
of the space and sub-linear in the intrinsic dimensionality and the size of the
dataset and takes space constant in dimensionality of the space and linear in
the size of the dataset. The proposed algorithm allows fine-grained control
over accuracy and speed on a per-query basis, automatically adapts to
variations in data density, supports dynamic updates to the dataset and is
easy-to-implement. We show appealing theoretical properties and demonstrate
empirically that the proposed algorithm outperforms locality-sensitivity
hashing (LSH) in terms of approximation quality, speed and space efficiency.

提出一种新的无需数据空间分割的随机化算法来避免由于数据维度过高而导致的数据检索问题，并通过理论分析和实验结果来证明这种算法在数据近似性、速度和空间效率等方面优于传统的局部敏感哈希算法（LSH）