We show the existence of variable-rate rate-distortion codes that meet the disortion constraint almost surely and are minimax, i.e., strongly, universal with respect to an unknown source distribution and a distortion measure that is revealed only to the encoder and only at runtime. If we only require minimax universality with respect to the source distribution and not the distortion measure, then we provide an achievable $\tilde{O}(1/\sqrt{n})$ redundancy rate, which we show is optimal. This is in contrast to prior work on universal lossy compression, which provides $O(\log n/n)$ redundancy guarantees for weakly universal codes under various regularity conditions. We show that either eliminating the regularity conditions or upgrading to strong universality while keeping these regularity conditions entails an inevitable increase in the redundancy to $\tilde{O}(1/\sqrt{n})$. Our construction involves random coding with non-i.i.d.\ codewords and a zero-rate uncoded transmission scheme. The proof uses exact asymptotics from large deviations, acceptance-rejection sampling, and the VC dimension of distortion measures.
翻译:如果我们只要求源分配的最小值普遍性而不是扭曲度量,那么我们就会提供一个可以实现的 $\ tilde{O}(1/\\ sqrt{n}) 美元冗余率,这是最佳的。这与以前关于普遍损耗压缩的工作形成对照,前者为各种常规条件下的薄弱通用代码提供$(log n/n)的冗余保证,后者为薄弱的通用代码提供$(log n/n) 的冗余保证。我们表明,要么消除常规性条件,要么升级为强大的普遍性,同时保持这些常规性条件,必然会增加对 $\ tilde{O}(1/\sqrt{n}) 的冗余率。我们的构造涉及与非i.i.d.\ codewords和零率的未编码传输计划随机编码。 证据使用了从大规模偏差、 接受- 取样和 V- jective- rec 转换度的参数。