Minimax Rate-Distortion

We show the existence of universal, variable-rate rate-distortion codes that meet the distortion constraint almost surely and approach the rate-distortion function uniformly with respect to an unknown source distribution and a distortion measure that is only revealed to the encoder and only at run-time. If the convergence only needs to be uniform with respect to the source distribution and not the distortion measure, then we provide an achievable $\tilde{O}(1/\sqrt{n})$ minimax rate of convergence. A converse result is also given showing that under minimax guarantees, one can do no better than $\Omega(1/\sqrt{n})$. Our construction combines conventional random coding with a zero-rate uncoded transmission scheme. The proof uses exact asymptotics from large deviations, acceptance-rejection sampling, the VC dimension of distortion measures, and the identification of an explicit, code-independent, finite-blocklength quantity, which converges to the rate-distortion function, that controls the performance of the best codes.