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

We propose Rosko -- row skipping outer products -- for deriving sparse matrix
multiplication (SpMM) kernels in reducing computation and memory access
requirements of deep neural networks (DNNs). Rosko allows skipping of entire
row computations during program execution with low sparsity-management
overheads. We analytically derive sparse CPU kernels that adapt to given
hardware characteristics to effectively utilize processor cores and minimize
data movement without the need for auto-tuning or search space exploration.
Rosko can be integrated with other outer product scheduling methods, allowing
them to leverage row skipping by using Rosko's packing format to skip
unnecessary computation.
Rosko kernels outperform existing auto-tuning and search-based solutions as
well as state-of-the-art vendor-optimized libraries on real hardware across a
variety of neural network workloads. For matrices with sparsities ranging from
65% to 99.8% typically found in machine learning, Rosko kernels achieve up to a
6.5x runtime reduction on Intel and ARM CPUs.

Rosko 提出了一种用于减少深度神经网络中计算和内存访问需求的稀疏矩阵乘法（SpMM）核，它允许在程序执行期间跳过整行计算，具有低稀疏管理开销。通过分析，我们有效地利用处理器核心来适应给定硬件特征的稀疏 CPU 核，并在不需要自动调整或搜索空间探索的情况下尽量减少数据移动。与现有的自动调整和基于搜索的解决方案以及最先进的供应商优化库相比，Rosko 核在各种神经网络工作负载下对真实硬件的性能表现更好。对于在机器学习中通常出现的 65％到 99.8％的稀疏性矩阵，Rosko 核在 Intel 和 ARM CPU 上可以实现高达 6.5 倍的运行时减少。

Rosko: 稀疏矩阵乘法核函数的行跳跃外积

Rosko: Row Skipping Outer Products for Sparse Matrix Multiplication  Kernels

It is common to encounter situations where one must solve a sequence of
similar computational problems. Running a standard algorithm with worst-case
runtime guarantees on each instance will fail to take advantage of valuable
structure shared across the problem instances. For example, when a commuter
drives from work to home, there are typically only a handful of routes that
will ever be the shortest path. A naive algorithm that does not exploit this
common structure may spend most of its time checking roads that will never be
in the shortest path. More generally, we can often ignore large swaths of the
search space that will likely never contain an optimal solution.
We present an algorithm that learns to maximally prune the search space on
repeated computations, thereby reducing runtime while provably outputting the
correct solution each period with high probability. Our algorithm employs a
simple explore-exploit technique resembling those used in online algorithms,
though our setting is quite different. We prove that, with respect to our model
of pruning search spaces, our approach is optimal up to constant factors.
Finally, we illustrate the applicability of our model and algorithm to three
classic problems: shortest-path routing, string search, and linear programming.
We present experiments confirming that our simple algorithm is effective at
significantly reducing the runtime of solving repeated computations.

该研究提出了一种能够学习最大程度地修剪搜索空间的算法，从而在解决多次相似的计算问题时，能够大幅减少运行时间并保证准确解决问题。