acceptodds
Under review as a conference paper at ICLR 2027

Rate–Distortion Dictionaries for Reconstruction and Generation

Abstract

Deploying a family of -VAE codecs at multiple rate–distortion operating points is straightforward; deciding which of them to keep is not. We study the problem of selecting a small dictionary of frozen codecs from a larger candidate frontier so that every future request is served by its single nearest deployed atom. We show that this constrained -medoids problem is not solvable by the classical one-dimensional clustering dynamic program, because nearest-atom assignment is provably non-monotone once matching is judged against points external to the frontier. We restore tractability by freezing, independently of , which frontier atom each request would use on the full unreduced frontier, which makes the resulting surrogate objective exactly solvable by an dynamic program. We then certify this surrogate: an exact identity for its gap to the true deployed loss, a geometric bound computable before optimization, and a finite-sample guarantee that extends the certificate to the underlying population objective. Experiments across three datasets show the certificate is non-vacuous and that the resulting dictionary matches or exceeds standard selection heuristics.

Primary area:
learning theory
Keywords:
Information Bottleneck, rate–distortion optimization, dictionary/codec selection, dynamic programming, generalization guarantees

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_G3BHOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper considers the problem of choosing a reduced dictionary of kk codes, out of M≫kM\gg k pre-trained encoders set, such that at inference time every service request (given desired performance, that is, variational rate RR and distortion DD) is answered with an adequate working point. The main method proposes first to allocate each request QQ to one of the MM existing options (called an “anchor”), and then use classical dynamic programming to choose a dictionary optimize an upper bound on the loss.

Critical strengths
  1. The main method is not confined to coding problems, and can be used as a method for more general service allocation settings, replacing RR and DD with relevant metrics.
  2. The proposed method is efficient, and has polynomial time complexity.
  3. Error guarantee and sample complexity analysis are given.
Critical weaknesses
  1. The first strength is also the major weakness - the core method is somewhat straightforward, and general. The paper devotes most of its focus to the VAE problem, but there is nothing specific about the VAE problem that makes the routing problem specific.

  2. Error analysis, although not completely trivial, is given in terms of the maximal diversity from optimum along atoms, which might not be tight.

  3. Overall setting is not well-motivated (see Questions 4 and 5 below).

  4. The main text is not clearly written, barely readable and lacks many of the central definitions and the main Algorithm. The Appendix is more carefully edited, but the paper is judged based on the main text.

Questions for authors
  1. What are weights w_{n} and how they are chosen. (l.266)

  2. In (l.273) “a request can end up closer to an interior atom than to either atom flanking it in D-order”. This central claim remains unclear. please clarify this (i.e. give a concrete example).

  3. (l.660) Define h_{n} clearly.

  4. In lossy compression, the classical Rate-Distortion tradeoff [R1,R2] relate the maximal tolerable distortion DD with a minimal rate RR achieving this distortion at reconstruction. That is, by setting the rate RR of a scheme, an optimal distortion DD is automatically set, and vice versa. In your setting, a “request” is defined by the point (R,D)(R,D), which might be non-optimal or non-achievable. Please add motivation for this mode of operation.

  5. When traversing a Pareto at inference time, a common practice is an interpolation between pre-trained models. This can be done for example in pixel space [R3], or in the model (parameters) space [R4]. In your method, is it possible to interpolate between endpoints instead of routing the anchor to one of them? How would it affect the deviation from true loss?

[R1] Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, 2012.

[R2] Toby Berger. Rate-distortion theory. Wiley Encyclopedia of Telecommunications, 2003.

[R3] Xintao Wang, Ke Yu, Shixiang Wu, Jinjin Gu, Yihao Liu, Chao Dong, Yu Qiao, and Chen Change Loy. ESRGAN: Enhanced super-resolution generative adversarial networks. In Proceedings of the European Conference on Computer Vision (ECCV) Workshops, pages 0–0, 2018.

[R4] Xintao Wang, Ke Yu, Chao Dong, Xiaoou Tang, and Chen Change Loy. Deep network interpolation for continuous imagery effect transition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1692–1701, 2019.

Reviewer_xSW1OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper deals with a setting in which β\beta-VAE encoder/decoder pairs are trained to traverse a rate-distortion frontier, and kk are retained as to form "rate-distortion dictionary". A pair from the dictionary is then chosen in order to perform encoding and decoding at a specified rate-distortion operating point. The paper's main contribution is to propose an dynamic programming algorithm to solve a surrogate objective and choose the dictionary, which approximates the constrained kk-medoids solution. A regret certificate which bounds the gap incurred by using the surrogate instead of the true objective is also proven, and shown empirically to be non-vacuous in the settings considered. Empirical validation is carried out on MNIST, CIFAR-10 and Fashion-MNIST, with reported gains over greedy algorithms.

Critical strengths
  1. The dynamic programming solution proposed by the paper is well-motivated as a method to solve an approximation of the dictionary selection problem which is considered throughout the work, and offers a regret bound against the best possible solution which can be computed ahead of time. This is a convenient property of the algorithm, and the regret bound is non-vacuous. The analysis of the algorithm appears to be carefully done and extensive.
Critical weaknesses
  1. The contribution appears limited, as the paper seems only to be offering an approximate algorithm for a particular selection problem from a fixed set of β\beta-VAE codecs. The broader significance of this problem and the proposed surrogate-DP solution for neural compression more widely is unclear to me.
  2. A fairly obvious missing baseline would be to have a single trained β\beta-VAE encoder/decoder pair which is conditioned on the desired rate parameter. For example, Dosovitskiy and Djolonga (ICLR 2020, https://openreview.net/forum?id=HyxY6JHKwr) is one simple example. There are also the referenced works [23;18;24;25;26] in the current manuscript, which are mentioned in the introduction as taking a similar rate-conditional approach. While the conclusion briefly mentions this possibility, the use of a rate-distortion dictionary instead of a conditional codec is not clearly motivated. Especially given that dictionary approach additionally requires keeping several models on hand, potentially increasing the memory footprint and complicating deployment, this raises further questions about how useful the proposed method might be. The analysis of the surrogate-DP solution, no matter how extensive, does not quite answer this question of relevance for me.
Questions for authors
  1. The paper states in places that the standard error or standard deviation is reported (e.g. lines 313 and 1257), but these are not reported in the tables. Given that the proposed method is close in many places to "Greedy Nearest Atom" in Table 1, this makes it hard to judge whether the gains are statistically significant. The same goes for the "frontier-quality report" mentioned on page 314, which I do not see included in the main paper or the appendix. Are these numbers available?
  2. The baselines are chosen as standard selection heuristics, but I do not see any references in the paper showing exactly where these heuristics have been adopted for variable-rate compression. Linking the baseline comparisons to prior work in the area would increase their relevance for evaluation.
  3. There are some presentation issues in the paper, for example: broken references on page 24 in the appendix, the text in the plots in Figures 4-6 is very small and hard to read, the left and right margins appear quite a bit smaller than that required by the ICLR 2027 format, the text in Section 6 references itself on line 323, some strange wording choices such as "we let the comparison decide, not the claim" in the conclusion. As there is no comparison in the paper with the possibility of single conditional codec which this sentence seems to be referencing, it appears potentially misleading.
  4. After the anchor is chosen according to Equation 14, the shortest-path solution with backtracking appears quite standard. Could the authors then clarify where they consider the main novelty to lie, in the step from the exact selection problem to the surrogate anchor-routed loss, the DP solver of Algorithms 1 and 2, the analysis of the proposed algorithm, or elsewhere?
  5. The paper does not perform any entropy coding or quantization, as per Remark 1, the discussion of quantization preceding this and the related Proposition 1 therefore seem irrelevant.
Reviewer_mkT1OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies dictionary selection for frozen β‑VAE codecs on rate‑distortion Pareto frontiers. Bent frontiers break monotonicity and invalidate classic 1‑D k‑medoids DP. It proposes an anchor‑routed surrogate solved by polynomial‑time dynamic programming. Computable a‑priori error certificates, finite‑sample and perturbation‑stability guarantees are derived. Experiments are conducted against multiple baselines across datasets, yet it suffers from surrogate gap, complexity overhead and narrow applicability.

Critical strengths

This work addresses codec dictionary‑selection on rate‑distortion frontiers and identifies why classic 1‑D k‑medoids DP fails. It proposes an anchor‑routed surrogate solved via polynomial‑time dynamic programming. Unlike heuristic baselines with no theoretical guarantees, it provides computable a‑priori error certificates, finite‑sample and perturbation‑stability analysis for both reconstruction and generation tasks.

Critical weaknesses
  1. It optimizes a surrogate instead of true loss. The a‑priori error certificate can be loose for small dictionary sizes, with no strong guarantee of approaching the true optimum.
  2. The DP complexity contains a quadratic term w.r.t candidate count, leading to high computational cost and limited scalability for large candidate pools.
  3. It is highly application‑specific, relies on high‑quality Pareto frontiers and representative request samples, and lacks real‑world online‑deployment validation.
Questions for authors

As in the above weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.