{"id":"305c8ec4-f809-4e2b-9090-265f63bca07e","arxiv_id":"2507.09712","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The RDD function extends classical rate-distortion by replacing point-wise distortion with a Gromov-Wasserstein style distance distortion, supported by a coding theorem and a heuristic alternating mirror descent algorithm.","lead":"This paper defines a new rate-distortion function, the RDD function, that measures distortion through differences of distance structures between source and reproduction, rather than point-wise error. It proves the function has operational meaning and gives a numerical algorithm, but the algorithm's convergence and accuracy are not established.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The numerical claim is the soft spot: AMD has no global-convergence proof for the nonconvex problem (8), so the plotted curves may not equal the true RDD function RG(D).","rationale":"The reader's weakest assumption correctly identified the lack of a convergence guarantee for the AMD algorithm on the nonconvex problem (8). My independent reading reaches the same conclusion: Theorem 1 and Theorem 2 are theoretically sound, but the numerical results rely on a heuristic that is not proven to find global optima. The proposed concrete test directly checks this assumption by comparing AMD against a certified global optimum on a small instance. Since the condition is the same as the reader's, the reader's conditional verdict remains appropriate. I do not see a stronger objection that would change the verdict.","tokens_in":686,"tokens_out":808,"duration_ms":315670,"concrete_test":"Take a small discrete instance, e.g., M = N = 3 with a fixed PX, DX, and DY, and compute the true RG(D) by global optimization of (8): use a dense grid over the conditional matrix W followed by local refinement, or a certified global solver, over the same range of λ used in Algorithm 1. Then run the published AMD algorithm (100 iterations, fixed λ) on the same instance and compare the achieved (D, R) points. If the AMD curve exceeds the global RG(D) curve by more than a small tolerance (say 1% in rate at any distortion), the numerical claim is falsified; if it matches, the concern is substantially mitigated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical result (Theorem 1) is plausible: achievability follows from the Poisson functional representation, and the converse from the per-coordinate marginal lower bound. Theorem 2 is also essentially correct, because for any fixed W the optimal r in the relaxed problem is exactly the marginal. The load-bearing gap is in the numerical computation. Problem (8) is nonconvex: the objective is convex in (W, r), but the Gromov-type distortion constraint (8c) is quadratic and indefinite in W, and Section V explicitly leaves convexity of the RDD function open. Algorithm 1 is an alternating fixed-point / mirror-descent heuristic derived from the Lagrangian for a fixed Lagrange multiplier λ; no convergence proof is supplied, and Theorem 2 only equates optimal solutions of (7) and (8), not the stationary points that the iteration can reach. With max_iter = 100 and no validation against a known solution or lower bound, the RDD curves in Figures 1-3 could lie strictly above the true RG(D). Thus the assertion that the AMD algorithm 'computes' the RDD function is not established, and the numerical evidence for the tradeoff is conditional.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12786,"tokens_out":4028,"duration_ms":52195,"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":[{"comment":"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.","section":"Section IV-B and Section V"},{"comment":"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.","section":"Appendix: Proof of Theorem 2"},{"comment":"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.","section":"Section III, Theorem 1 and its proof"}],"minor_comments":[{"comment":"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.","section":"Section IV, notation"},{"comment":"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.","section":"Figure 1"},{"comment":"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.","section":"Section V and Algorithm 1"},{"comment":"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.","section":"Appendix, two-source coding theorem"}],"recommendation":"major_revision","confidential_remarks":"The paper's theoretical definition and the complexity reduction are solid contributions, but the numerical section currently depends on an unverified convergence property of a nonconvex algorithm. If the authors can either prove convergence of AMD (even to a stationary point and then justify global optimality on the tested instances) or supply a comparison against a lower bound on small problems, the paper would be much stronger. The outsourced proof of Theorem 1 is another point that should be addressed before publication in a journal with a rigorous information-theory readership."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe RDD paper is worth a look if you care about rate-distortion beyond a fixed distortion measure. The new thing is the RDD function: replace expected pointwise distortion with a Gromov-type comparison of distance matrices. That's a legitimate way to formulate source coding when the source and reproduction alphabets aren't directly comparable or have different dimensions. The coding theorem is plausible—achievability via Poisson functional representation, converse via standard per-coordinate marginal arguments—and the semi-relaxation exactness claim (Theorem 2) is essentially correct: for any fixed W the optimal r is just the marginal, so relaxing the marginal constraint doesn't change the optimum.\n\nThe soft spot is where the paper makes its empirical claims. Problem (8) is nonconvex; the distortion constraint is quadratic and indefinite in W, and Section V explicitly says convexity of the RDD function is open. Algorithm 1 is an alternating mirror-descent heuristic with no convergence proof, fixed λ, max_iter=100, and no validation against a known solution or lower bound. So the curves in Figures 1–3 should be read as candidates, likely upper bounds on the true R(D), not as computed values of the RDD function. The proof of Theorem 1 is also outsourced to [17] without checking conditions, and the appendix proof of Theorem 2 is muddled, but these are minor given the standard nature of the arguments.\n\nThe theoretical contribution stands. It's a new formulation with a credible operational meaning, and the authors are honest about the open convexity question. The numerical evidence is illustrative, not definitive.\n\nA serious referee should engage with this paper. I'd recommend conditional acceptance: require a stated convergence or heuristic caveat, validation against the classical RD limit at θ=0, and at least one small exact comparison. For a reader working on structural or GW-based coding, the theoretical part is citable and worth discussing.","headline":"The RDD function is a legitimate new formulation, but the AMD algorithm's curves are unvalidated upper bounds until convergence is addressed.","tokens_in":13302,"tokens_out":2545,"would_cite":true,"duration_ms":27032,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A34","94A15","49Q22"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["rate-distortion theory","Gromov-Wasserstein","Gromov-type distortion","source coding","alternating mirror descent","mutual information","structural distortion","information theory"],"falsifier":"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.","tokens_in":12376,"feed_emoji":"📉","tokens_out":9435,"duration_ms":92211,"temperature":0.7,"pith_summary":"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.","feed_headline":"Gromov-type distortion yields a computable rate-distortion function","feed_subtitle":"A new lower bound for coding that preserves distance structure, computed by alternating mirror descent in cubic time.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the classical rate-distortion function and its coding theorem that the paper extends.","marker":"[1]"},{"why":"Introduces the Gromov-Wasserstein distance whose distortion term the RDD constraint adopts.","marker":"[3]"},{"why":"Defines the Gromov-type distortion between measurable spaces used in the RDD constraint.","marker":"[5]"},{"why":"Supplies the rate-distortion-perception coding theorem used to prove Theorem 1.","marker":"[17]"},{"why":"Provides the decomposition of Gromov-type distortion into a constant and quadratic terms that cuts computational complexity.","marker":"[18]"},{"why":"Contributes the semi-relaxed optimization idea that lets the algorithm drop one marginal constraint.","marker":"[20]"},{"why":"Supplies the alternating minimization template for rate-distortion computation that the update rules follow.","marker":"[21]"},{"why":"Provides the functional representation lemma used in the achievability direction of Theorem 1.","marker":"[23]"}],"fun_headline_variants":["RDD function: new rate-distortion tradeoff for structured data","Gromov-type distortion gives operational rate-distortion bound","Cubic-time algorithm for a new rate-distortion function","Coding with Gromov-Wasserstein distortion: RDD function","Rate-distortion meets Gromov: operational coding theorem"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["RDD function: new rate-distortion tradeoff for structured data","Gromov-type distortion gives operational rate-distortion bound","Cubic-time algorithm for a new rate-distortion function","Coding with Gromov-Wasserstein distortion: RDD function","Rate-distortion meets Gromov: operational coding theorem"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000862,"raw_usage":{"total_tokens":3737,"prompt_tokens":937,"completion_tokens":2800,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":2714}},"tokens_in":553,"tokens_out":2800,"duration_ms":22610,"temperature":1.0,"reasoning_tokens":2714,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:50:15.938923+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the classical rate-distortion function and its coding theorem that the paper extends."},{"cited_title":"Gromov-Wasserstein distances and the metri c approach to object matching,","cited_arxiv_id":null,"evidence_quote":"Introduces the Gromov-Wasserstein distance whose distortion term the RDD constraint adopts."},{"cited_title":"The Gromov-Wasserstein dis tance be- tween networks and stable network invariants,","cited_arxiv_id":null,"evidence_quote":"Defines the Gromov-type distortion between measurable spaces used in the RDD constraint."},{"cited_title":"Fast gradi ent computation for Gromov-Wasserstein distance,","cited_arxiv_id":null,"evidence_quote":"Provides the decomposition of Gromov-type distortion into a constant and quadratic terms that cuts computational complexity."},{"cited_title":"Efficient and prov- ably convergent computation of information bottleneck: A s emi-relaxed approach,","cited_arxiv_id":null,"evidence_quote":"Contributes the semi-relaxed optimization idea that lets the algorithm drop one marginal constraint."},{"cited_title":"On the computation of rate-distortion fun ctions,","cited_arxiv_id":null,"evidence_quote":"Supplies the alternating minimization template for rate-distortion computation that the update rules follow."},{"cited_title":"Strong functional representat ion lemma and applications to coding theorems,","cited_arxiv_id":null,"evidence_quote":"Provides the functional representation lemma used in the achievability direction of Theorem 1."}],"review_version":1}