Pith. sign in

REVIEW 3 major objections 4 minor 23 references

RDD Function: A Tradeoff Between Rate and Distortion-in-Distortion

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The RDD function, using Gromov-type distortion, is proved to be the minimum rate for structural source coding and is computable by an alternating mirror descent algorithm.

desk verdict The RDD function is a legitimate new formulation, but the AMD algorithm's curves are unvalidated upper bounds until convergence is addressed. read the letter →

arxiv 2507.09712 v2 pith:HLTENVBI submitted 2025-07-13 cs.IT math.IT

Lingyi Chen , Haoran Tang , Shitong Wu , Jiakun Liu , Huihui Wu , Wenyi Zhang , Hao Wu This is my paper · ORCID
classification cs.ITmath.IT MSC 94A3494A1549Q22
keywords rate-distortiontheoryGromov-WassersteinGromov-typedistortionsourcecodingalternatingmirrordescentmutualinformationstructural
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces the Rate Distortion-in-Distortion (RDD) function, a modification of the classical rate-distortion function in which the expected pointwise distortion is replaced by a Gromov-type distortion that compares the distance structures of two metric spaces. The authors aim to prove that this function gives the minimum rate for a source coding task where the reproduction must preserve the intrinsic geometry of the source, even when the source and reproduction spaces have different dimensions. A coding theorem establishes that rates above the RDD function are both necessary and sufficient for such coding, giving the function operational meaning. Because the Gromov-type distortion is quadratic and hard to handle analytically, the paper develops an alternating mirror descent algorithm that computes the RDD function for discrete sources with per-iteration cost cubic in the alphabet sizes. Numerical experiments on Gaussian, Laplacian, uniform, circle, and sphere grids show decreasing rate-distortion curves, and a combined distortion term interpolates between the classical and structural regimes.

What carries the argument

The central object is the Gromov-type distortion $\mathbb{E}[|d_X^q(X,X') - d_Y^q(Y,Y')|^2]$, which measures how well the distance function of the reproduction space matches the distance function of the source space under the joint distribution induced by the channel $P_{Y|X}$. This distortion is borrowed from the Gromov-Wasserstein distance and lets the rate-distortion problem compare metric spaces of different dimensions without any explicit pointwise correspondence. The algorithmic workhorse is an alternating mirror descent method applied to the Lagrangian of a semi-relaxed discrete problem: it alternates a closed-form mirror-descent update for the conditional probability matrix $W$ and a closed-form update for the reproduction marginal $r$, after decomposing the quartic distortion into a constant term and two quadratic terms. This decomposition is what reduces the per-iteration complexity from quartic to $O(M^2N + MN^2)$.

What would settle it

Compute the exact RDD value for a small discrete source by a dense grid search or by solving the KKT system over the conditional probability simplex, then run the AMD algorithm from many different random initializations; if the algorithm returns different values for the same multiplier or values above the exact optimum, the claimed convergence to the global optimum fails. Convexity of the constraint set could be checked directly on a two-point example to see whether the Gromov-type distortion sublevel set is convex.

Watch

Extended reading notes

Core claim

The central claim is that the RDD function $R_G(D)$, defined as the infimum of mutual information $I(X;Y)$ over conditional distributions $P_{Y|X}$ subject to $\mathbb{E}[|d_X^q(X,X') - d_Y^q(Y,Y')|^2] \le D$, is the true operational rate-distortion function for this structural distortion constraint. Theorem 1 states that $R \ge R_G(D)$ is necessary and sufficient for the existence of a code sequence with asymptotic rate $R$ whose encoded reproductions satisfy the Gromov-type distortion constraint for every block. In addition, the paper claims that a semi-relaxed version of the discrete optimization problem, in which the marginal constraint on the reproduction distribution is dropped, has the same optimal value as the original problem, and that the proposed alternating mirror descent updates compute this optimal value. The contribution is therefore both a new information measure with a coding theorem and a practical algorithm with cubic per-iteration complexity.

Load-bearing premise

The numerical claims rest on the assumption that the alternating mirror descent algorithm, run with a fixed Lagrange multiplier and a fixed maximum of 100 iterations, reaches the global optimum of the nonconvex relaxed problem for every sampled value of the multiplier.

Editorial extensions

If this is right

  • The RDD function provides a lower bound on the bit rate for any source code that must preserve the pairwise distance structure between source symbols, including cases where source and reproduction live in spaces of different dimensions.
  • The AMD algorithm makes this bound numerically computable for discrete sources, with per-iteration cost $O(M^2N + MN^2)$, so the tradeoff can be plotted as a rate-distortion curve.
  • The combined distortion $R(D;\theta)$ shows that adding structural distortion to the classical distortion monotonically increases the required rate, quantified by the weight $\theta$.
  • The semi-relaxed equivalence means that the cheaper relaxed problem solved by the algorithm is exactly the original RDD problem, not an approximation.
  • The two-stream coding formulation in the appendix shows that the RDD function is the classical RD function of a product source under a structural distortion measure, connecting the new function to standard rate-distortion theory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The Gromov-type distortion could serve as a natural training objective for representation learning and generative models, where the goal is to preserve relationships rather than coordinates; the paper notes but does not develop this direction.
  • Because the coding theorem is derived from the rate-distortion-perception coding theorem, coupling the RDD constraint with a perception constraint could yield a three-way rate-distortion-perception-structure tradeoff.
  • A direct way to test the scope of the method is to replace the squared-loss $f$ in the distortion with KL divergence and check whether the AMD update still has a closed form.
  • If the RDD problem turns out to be non-convex, as suggested by the open question in Section V, the global-optimality guarantee would need either a convex relaxation or a proven initialization strategy; until then the numerical curves are best interpreted as upper bounds on the true RDD function.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces the Rate Distortion-in-Distortion (RDD) function, which replaces the expected distortion constraint of the classical rate-distortion problem with a Gromov-type distortion that compares squared powers of the source and reproduction metrics. It states a zero-distortion characterization (Proposition 1), an operational coding theorem (Theorem 1), an equivalent relaxed formulation of the discrete problem (Theorem 2), and an alternating mirror descent (AMD) algorithm with claimed per-iteration complexity O(M^2N + MN^2). Numerical experiments on Gaussian, Laplacian, and uniform sources over grids and spherical surfaces are used to illustrate the rate-distortion tradeoff, and a fused distortion variant R(D;θ) is studied.

Significance. If the main claims are fully established, the RDD function is a conceptually interesting extension of rate-distortion theory that can compare source and reproduction spaces of different dimensions without a pointwise correspondence, and Theorem 1 would give it operational meaning via a coding theorem. The paper also contributes a complexity reduction for evaluating Gromov-type distortion, from quartic to cubic, and a concrete iterative algorithm. The theoretical framework is clearly presented and the relation to the Gromov-Wasserstein distance is apt. However, the numerical claim that the AMD algorithm computes the RDD function is currently conditional on an unproved convergence property, and two proofs in the appendix require tightening before the central claims can be regarded as established.

major comments (3)
  1. [Section IV-B and Section V] The claim that the AMD algorithm 'computes' the RDD function is not supported by a convergence proof. Problem (8) is nonconvex: the objective f(W,r) is convex, but the Gromov-type distortion constraint (8c) is a quadratic and indefinite function of W, and Section V explicitly states that convexity of the RDD function is unclear. Algorithm 1 performs alternating updates for a fixed Lagrange multiplier λ with max_iter = 100, but no theorem guarantees that its fixed points are global optima of (8), and Theorem 2 only equates optimal solutions of (7) and (8), not the stationary points or limit points of the iteration. Without a convergence guarantee, a lower bound, or a validation against a known example, the RDD curves in Figures 1-3 may lie strictly above the true RG(D). This is load-bearing for the numerical contribution and for the phrase 'effectiveness of the developed algorithm' in the abstract.
  2. [Appendix: Proof of Theorem 2] The proof is not rigorous and contains a logical inversion. It begins by assuming an optimal solution (W*,r*) to (8) and invoking KKT conditions without stating or verifying any constraint qualification, which is nontrivial because (8c) is nonconvex. The step 'Substituting these into condition (11), we obtain (W*,r*) satisfying the relaxed condition' is unclear: the desired condition r_j = sum_i w_ij p_i should be derived from stationarity in r, but the proof does not show that the KKT multipliers exist or that the stationarity condition is sufficient. The final claim that an optimal solution to (7), being feasible for (8), is 'also optimal to (8)' is invalid; feasibility in the relaxed problem does not imply optimality. The equality of the optimal values of (7) and (8) needs a direct argument, e.g., showing that every feasible point of (8) can be projected to a feasible point of (7) without increasing the objective.
  3. [Section III, Theorem 1 and its proof] The coding theorem is the central operational claim, but its proof is outsourced to 'Theorem 3 in [17]' and to the Poisson Functional Representation [23] without verifying that the hypotheses of those results are satisfied in the present setting. In particular, the Gromov-type distortion constraint is not a standard per-symbol average distortion; it is a pairwise expectation over two independent copies of the joint distribution, and the paper does not show that the abstract coding theorem in [17] applies verbatim to this constraint. The converse direction is asserted with 'the same steps in the proof of the classical rate-distortion theorem' but not carried out. This gap should be closed either by a self-contained proof or by a precise verification of the conditions of the cited theorems.
minor comments (4)
  1. [Section IV, notation] The symbols D_X and D_Y for the metric matrices conflict with the distortion threshold D used throughout the paper; consider using Δ_X and Δ_Y or similar notation.
  2. [Figure 1] The third subplot displays an x-axis label beginning with '-25 0 100 ...', which appears to be a rendering artifact; the axes of all subplots should be formatted consistently.
  3. [Section V and Algorithm 1] The experimental setup is not fully reproducible: the range of the arithmetic sequence for λ is not specified, and no convergence criterion is reported beyond max_iter = 100. Please state the λ values and the stopping rule, and ideally provide the code.
  4. [Appendix, two-source coding theorem] The informal coding theorem for two independent source streams is stated without a formal definition of probability of error or a precise statement of the achievable region; please formalize it or remove it.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: RDD is defined independently, the coding theorem uses external functional-representation results, and the AMD solver does not fit RG(D); the caveats are an unproved KKT step in Theorem 2 and the lack of a convergence proof for the nonconvex Algorithm 1, which are correctness risks, not circularity.

full rationale

The RDD function in (2) is defined directly as a minimum of mutual information under a Gromov-type distortion constraint, independently of any solver or fitted quantity. Theorem 1's achievability is imported from the external Poisson functional representation (Li–Gamal, ref. [23]) and from the coding theorem of Theis–Wagner (ref. [17]); the converse uses standard rate-distortion marginal arguments. Neither step is equivalent to the definition by construction. The relaxation (8) and Theorem 2 are not circular: for fixed W, f(W,r) is minimized by r_j = sum_i w_ij p_i, so the relaxed optimum satisfies the dropped marginal constraint; the paper's proof instead invokes KKT at an optimum of a nonconvex problem, which is an unjustified assumption, but this is a proof gap, not a self-referential reduction. The Gromov-distortion decomposition ~C1 + ~C2 − 2⟨CW D_Y, W⟩ is an algebraic identity presented in the paper; citations [12], [18], and [20] (some with overlapping authors) supply algorithmic inspiration, but the central coding claim does not rest on them, so these self-citations are not load-bearing. The main weakness is numerical: Section V states 'It is still unclear whether the RDD function is convex with respect to the RDD term,' and Algorithm 1 fixes λ and runs 100 iterations without a global-convergence proof, so Figures 1–3 are not established as exactly RG(D). This is a correctness and validation concern, not circularity, because the plotted quantities are not fitted to RG(D) and the algorithm does not define RG(D).

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claim (operationality of RDD) rests on the applicability of the Poisson Functional Representation and standard measure-theoretic assumptions. The numerical claims rest on the unproven convergence of the AMD algorithm. No free parameters are fitted to data; λ is a swept Lagrange multiplier and the source scale σ is an input.

assumptions (2)
  • domain assumption The source and reproduction spaces are standard Borel spaces so that the Poisson Functional Representation lemma applies.
    Theorem 1's direct part uses the Poisson Functional Representation from [23], which requires standard Borel spaces; the paper only states measurable spaces.
  • ad hoc to paper The alternating mirror descent updates in Algorithm 1 converge to a stationary point (or global optimum) of (8) for each fixed λ.
    No convergence analysis is provided; the numerical curves assume the iterates after 100 steps approximate the true RDD value. Section V notes convexity is unclear.

how reviews work

0 comments
Cite this review

Pith. "Pith review of RDD Function: A Tradeoff Between Rate and Distortion-in-Distortion." pith.science (2026). https://pith.science/paper/HLTENVBI

@misc{pith2026250709712,
  author       = {Pith},
  title        = {Pith review of: RDD Function: A Tradeoff Between Rate and Distortion-in-Distortion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HLTENVBI}},
  note         = {Machine review of arXiv:2507.09712}
}
read the original abstract

In this paper, we propose a novel function named Rate Distortion-in-Distortion (RDD) function as an extension of the classical rate-distortion (RD) function, where the expected distortion constraint is replaced by a Gromov-type distortion. This distortion, integral to the Gromov-Wasserstein (GW) distance, effectively defines the similarity in spaces of possibly different dimensions even without a direct metric between them. While the RDD function qualifies as an informational RD function, encoding theorems substantiate its status as an operational RD function, thereby underscoring its potential applicability in real-world source coding. Due to the high computational complexity associated with Gromov-type distortion, in general, the RDD function cannot be evaluated analytically. Consequently, we develop an alternating mirror descent algorithm that significantly reduces computational complexity by employing decomposition, linearization, and relaxation techniques. Numerical results on classical sources and different grids demonstrate the effectiveness of the developed algorithm. By exploring the relationship between the RDD function and the RD function, we suggest that the RDD function may have potential applications in future scenarios.

Figures

Figures reproduced from arXiv: 2507.09712 by the authors.

Figure 3
Figure 3. The R(D; θ) surface and its corresponding cross-section curves. Left: R(D; θ) surface with θ ∈ [0, 0.1]; Middle: R-D curve; Right: R￾θ curve. The dimensions of metric spaces are dim(X ) = dim(Y) = 1 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 1
Figure 1. The RDD functions of different sources and different metric space dimensions. Left: dim(X ) = dim(Y) = 1; Right: dim(X ) = 2, dim(Y) = 3. The parameter σ denotes the scale parameter for both Gaussian and Laplacian sources, see Appendix for the definition of these sources due to space limitation. Finally, we discuss the relationship between RDD and RD functions by considering the following problem, with the con￾strai… view at source ↗
Figure 2
Figure 2. The RDD function of Gaussian source on spherical surfaces and corresponding spatial configurations. Left: points on circle with dimension dim(X ) = 2; Middle: R-D curve; Right: points on sphere with dimension dim(Y) = 3. The constraint (9b) draws inspiration from the form of Fused GW [22], which combines Wasserstein and Gromov￾Wasserstein distances to jointly account for the features and structures of graphs. The fu… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The conditional probability PY |X for different θ and D. Left: D = 1; Right: D = 3; Upper: θ = 0; Middle: θ = 0.01; Lower: θ = 0.02. the corresponding distribution represents the solution to the classical RD problem. It can be observed that, as θ increases, the conditi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 20 canonical work pages

  1. [17]

    A coding theorem for the rate- distortion- perception function,

    L. Theis and A. B. Wagner, “A coding theorem for the rate- distortion- perception function,” arXiv preprint arXiv:2104.13662 , 2021

    arXiv 2021

  2. [23]

    Strong functional representat ion lemma and applications to coding theorems,

    C. T. Li and A. E. Gamal, “Strong functional representat ion lemma and applications to coding theorems,” IEEE Transactions on Information Theory, vol. 64, no. 11, pp. 6967–6978, Nov 2018. APPENDIX PROOF OF PROPOSITION 1 Proof: Note that I(X; Y ) = 0 if and only if X and Y are independent. Therefore, if there exists a pmf PY such that D≥ ∫ ∫ (X ×Y)2 |dq X ...

    work page 2018

  3. [1]

    T. M. Cover and J. A. Thomas, Elements of Information Theory . Wiley- Interscience, 2006

    work page 2006

  4. [2]

    Berger, Rate Distortion Theory: A Mathematical Basis for Data Compression

    T. Berger, Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice-Hall, 1971

    1971

  5. [3]

    Gromov-Wasserstein distances and the metri c approach to object matching,

    F. Mémoli, “Gromov-Wasserstein distances and the metri c approach to object matching,” F oundations of Computational Mathematics , vol. 11, pp. 417–487, 2011

    work page 2011

  6. [4]

    Entropic metr ic alignment for correspondence problems,

    J. Solomon, G. Peyré, V . G. Kim, and S. Sra, “Entropic metr ic alignment for correspondence problems,” ACM Transactions on Graphics (ToG) , vol. 35, no. 4, pp. 1–13, 2016

    work page 2016

  7. [5]

    The Gromov-Wasserstein dis tance be- tween networks and stable network invariants,

    S. Chowdhury and F. Mémoli, “The Gromov-Wasserstein dis tance be- tween networks and stable network invariants,” Information and Infer- ence: A Journal of the IMA , vol. 8, no. 4, pp. 757–787, 2019

    work page 2019

  8. [6]

    Gromov-Wasserste i n averaging of kernel and distance matrices,

    G. Peyré, M. Cuturi, and J. Solomon, “Gromov-Wasserste i n averaging of kernel and distance matrices,” in Proc. International Conference on Machine Learning (ICML) , New Y ork, NY , USA, Jun. 2016, pp. 2664– 2672

    work page 2016

Show all 23 references
  1. [7]

    Rethinking lossy compression: The rate- distortion-perception tradeoff,

    Y . Blau and T. Michaeli, “Rethinking lossy compression: The rate- distortion-perception tradeoff,” in Proc. International Conference on Machine Learning (ICML) , Long Beach, California, USA, Jun. 2019, pp. 675–685

    2019

  2. [8]

    The information bottleneck method,

    N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” arXiv preprint physics/0004057 , 2000

    2000 arXiv

  3. [9]

    The Monge-Kantorov ich problem: Achievements, connections, and perspectives,

    V . I. Bogachev and A. V . Kolesnikov, “The Monge-Kantorov ich problem: Achievements, connections, and perspectives,” Russian Mathematical Surveys, vol. 67, no. 5, p. 785, Oct. 2012

    2012

  4. [10]

    A communic ation optimal transport approach to the computation of rate-dist ortion func- tions,

    S. Wu, W. Y e, H. Wu, H. Wu, W. Zhang, and B. Bai, “A communic ation optimal transport approach to the computation of rate-dist ortion func- tions,” in Proc. IEEE Information Theory W orkshop (ITW) , Saint-Malo, France, Apr. 2023

    2023

  5. [11]

    Spectral Gromov-Wasserstein distances fo r shape matching,

    F. Mémoli, “Spectral Gromov-Wasserstein distances fo r shape matching,” in Proc. International Conference on Computer Vision W orkshops (IC CV W orkshops), Kyoto, Japan, Sep. 2009, pp. 256–263

    2009

  6. [12]

    Linear-time Gromo v Wasserstein distances using low rank couplings and costs,

    M. Scetbon, G. Peyré, and M. Cuturi, “Linear-time Gromo v Wasserstein distances using low rank couplings and costs,” in Proc. International Conference on Machine Learning (ICML) , Baltimore, Maryland, USA, Jul. 2022, pp. 19 347–19 365

    2022

  7. [13]

    Gromov-Wasserstei n learning for graph matching and node embedding,

    H. Xu, D. Luo, H. Zha, and L. C. Duke, “Gromov-Wasserstei n learning for graph matching and node embedding,” in Proc. International Confer- ence on Machine Learning (ICML) , Long Beach, California, USA, Jun. 2019, pp. 6932–6941

    2019

  8. [14]

    Gromov-Wasserstei n alignment of word embedding spaces,

    D. Alvarez-Melis and T. Jaakkola, “Gromov-Wasserstei n alignment of word embedding spaces,” in Proc. Conference on Empirical Methods in Natural Language Processing , Brussels, Belgium, Oct. 2018, pp. 1881– 1890

    2018

  9. [15]

    Learning a utoencoders with relational regularization,

    H. Xu, D. Luo, R. Henao, S. Shah, and L. Carin, “Learning a utoencoders with relational regularization,” in Proc. International Conference on Machine Learning (ICML) , Virtual Conference, Jul. 2020, pp. 10 576– 10 586

    2020

  10. [16]

    Learning generative models across incomparable spaces,

    C. Bunne, D. Alvarez-Melis, A. Krause, and S. Jegelka, “ Learning generative models across incomparable spaces,” in Proc. International Conference on Machine Learning (ICML) , Long Beach, California, USA, Jun. 2019, pp. 851–861

    2019

  11. [18]

    Fast gradi ent computation for Gromov-Wasserstein distance,

    W. Zhang, Z. Wang, J. Fan, H. Wu, and Y . Zhang, “Fast gradi ent computation for Gromov-Wasserstein distance,” Journal of Machine Learning, vol. 3, no. 3, pp. 282–299, 2024

    2024

  12. [19]

    A mathematical theory of communication ,

    C. E. Shannon, “A mathematical theory of communication ,” The Bell System Technical Journal , vol. 27, no. 3, pp. 379–423, 1948

    1948

  13. [20]

    Efficient and prov- ably convergent computation of information bottleneck: A s emi-relaxed approach,

    L. Chen, S. Wu, J. Y e, H. Wu, W. Zhang, and H. Wu, “Efficient and prov- ably convergent computation of information bottleneck: A s emi-relaxed approach,” in Proc. IEEE International Conference on Communications (ICC), Denver, USA, May 2024, pp. 1637–1642

    2024

  14. [21]

    On the computation of rate-distortion fun ctions,

    I. Csiszár, “On the computation of rate-distortion fun ctions,” IEEE Transactions on Information Theory , vol. 20, no. 1, pp. 122–124, 1974

    1974

  15. [22]

    Fused Gromov-Wasserstein distance for structured objects,

    T. V ayer, L. Chapel, R. Flamary, R. Tavenard, and N. Cour ty, “Fused Gromov-Wasserstein distance for structured objects,” Algorithms, vol. 13, no. 9, p. 212, 2020

    2020

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.