{"id":"98c81380-245b-4a56-8077-c6e3b0de8193","arxiv_id":"2508.13486","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The authors derive and test a primal-dual algorithm whose outer iterations converge at rate O(1/n) for discrete RDP functions under KL, Wasserstein, and TV perception measures.","lead":"This paper introduces IAS-II, a primal-dual algorithm for computing rate-distortion-perception (RDP) functions with a claimed O(1/n) convergence rate. It addresses a known gap: existing numerical RDP methods, including the authors' own IAS algorithm, lacked rigorous convergence guarantees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(1/n) convergence claim is proved only for an idealized scheme with exact inner solves; Algorithms 1 and 2 run finite inner loops with no stopping criterion or inner-rate analysis, so the implemented methods are not covered by Theorems 3 and 5.","rationale":"Read in good faith: the paper's core contribution is a convergence-rate theorem for a primal-dual alternating algorithm for RDP computation, and the exact-scheme proof structure (Lemmas 2-8, Theorems 3 and 5) is plausible and largely checkable. The descent inequalities and telescoping are standard once exact inner minimizers and active constraints are granted. However, the central claim is about an algorithm, and the only algorithms supplied are finite inner-loop procedures. No theorem in Section 4 analyzes the finite-inner version; there is no stopping criterion, no inner complexity, and no coupling between inner and outer iterations. This is exactly the weakest assumption the reader identified. The entropy-regularized Wasserstein theorem and the pseudocode inconsistency are further symptoms of the same gap. I would not reject the paper: the underlying exact scheme may well admit an O(1/n) rate, and the gaps are fixable by adding an inner-solve budget analysis or a tolerance schedule. But as written the headline overstates the guarantee, so the conditional verdict is appropriate and unchanged.","tokens_in":15680,"tokens_out":17766,"duration_ms":171746,"concrete_test":"Analyze the rate with approximate inner solves: assume at outer step k the inner routine returns \\tilde w_k with f(\\tilde w_k,r_k) \\le \\min_w f(w,r_k)+\\delta_k, and re-derive the telescoping sum in Theorem 3. Show that the conclusion becomes f(w_n,r_n)-f^* \\le C/n + (1/n)\\sum_{k=1}^n \\delta_k. Then inspect Algorithms 1 and 2 for any choice of iteration counts or tolerances that bounds (1/n)\\sum \\delta_k; if none exists, the O(1/n) claim does not follow for the implemented finite-inner-loop algorithms. A complementary run on the Table 2 binary instance, comparing machine-precision inner solves with a fixed 5-iteration inner loop, would show the practical floor.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 3 and 5 define w_n = \\tilde w(r_n), where \\tilde w(r) is an exact minimizer of the inner problem (6) or (15), and Lemmas 2 and 6 use exact optimality to obtain the representation \\tilde w_{ij} = r_j e^{a_j - \\lambda d_{ij} - b_i/p_i -1} and to lower-bound the per-step decrease. Algorithm 1 (lines 4-9) and Algorithm 2 (lines 4-10), however, only run an inner loop 'while the inner iteration is sufficient', with no convergence rate, no tolerance, and no guarantee that the returned w is close to the exact inner minimizer. Thus the telescope in Theorem 3 (and its Wasserstein analogue) does not control the quantity actually computed by the algorithms. If at outer step k the inner solve is only \\delta_k-suboptimal, the bound in the proof acquires an extra term (1/n)\\sum_{k=1}^n \\delta_k; the paper supplies no mechanism (e.g., \\delta_k \\le 1/k^2) to make this vanish. As a result the advertised O(1/n) is an outer-iteration rate for an exact alternating-minimization scheme, not a convergence guarantee for the algorithm as implemented. Secondary but related: no inner-loop complexity is stated, no code is shipped, the Wasserstein theorem applies to the entropy-regularized problem (13) with unquantified bias, and Algorithm 2's \\hat\\phi update does not visibly enforce \\sum_j \\Pi_{ij}=p_i, so even the regularized inner problem may not be solved.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two primal-dual algorithms, IAS-II for KL-divergence perception and for entropy-regularized Wasserstein perception, to compute the information rate-distortion-perception (RDP) function. The authors reformulate the RDP problem by optimizing over the reconstruction distribution rather than imposing hard perceptual constraints, derive explicit dual updates for the resulting subproblems, and claim an O(1/n) convergence rate to the global optimum in both cases. Numerical comparisons against the authors' earlier IAS algorithm on binary and Gaussian sources report speed-ups and small objective differences. The central theoretical claims, however, are proved only for an idealized alternating-minimization scheme with exact inner solves and, in the Wasserstein case, for the entropy-regularized objective rather than the original RDP problem.","tokens_in":16026,"tokens_out":10479,"duration_ms":107451,"significance":"If the O(1/n) claim were fully established, this would be a notable advance: a rigorous, non-asymptotic convergence guarantee for RDP computation would close a well-recognized gap, and the relaxation idea of optimizing over the reconstruction marginal is a useful structural contribution. The outer-loop telescoping argument is elegant, the monotone decrease lemmas are self-contained, and the experimental comparisons are a practical strength. However, the advertised guarantee is currently not supported for the algorithms as implemented, for the specific reasons detailed in the major comments. The paper therefore provides a promising framework whose central theorem needs substantial additional work before the result can be considered established.","major_comments":[{"comment":"The O(1/n) proofs assume that each outer step uses exact inner minimizers w_n = \\tilde w(r_n) and Pi_n = \\tilde Pi(r_n), as defined by problems (6) and (15). Both algorithms, however, run an inner 'while the inner iteration is sufficient' loop with no tolerance, no stopping rule, and no inner-loop convergence rate. If the inner solve at outer step k is only delta_k-suboptimal, the proof acquires an additional term (1/n) sum_k delta_k; the paper supplies no mechanism, such as delta_k <= O(1/k^2), to make this term vanish. Consequently the telescoping arguments in Theorems 3 and 5 control an idealized quantity that is not what Algorithms 1 and 2 return. The authors must either prove an inner-loop rate with an explicit stopping criterion that makes the accumulated inner error vanish in the outer bound, or explicitly restate the main claim as a rate for an exact-arithmetic alternating-minimization scheme.","section":"Section 4 (Theorems 3 and 5), Algorithms 1 and 2"},{"comment":"The update \\hat phi_i <- 1 / sum_j exp(-beta_j/epsilon - lambda c_ij/epsilon) does not enforce the source marginal. Since Pi_ij = exp(-beta_j/epsilon - lambda c_ij/epsilon) \\hat phi_i, this update normalizes sum_j Pi_ij to 1, whereas constraint (15c) requires sum_j Pi_ij = p_i. The correct update is \\hat phi_i <- p_i / sum_j exp(-beta_j/epsilon - lambda c_ij/epsilon). As written, even a perfectly converged inner loop in Algorithm 2 does not solve the inner problem (15), so Lemma 6 and Theorem 5 cannot be applied to Algorithm 2 without correcting this error.","section":"Section 3.2, Algorithm 2 line 6"},{"comment":"The Wasserstein convergence result is stated for the entropy-regularized problem (13) with a fixed regularization coefficient epsilon, not for the original Wasserstein RDP problem (12)/(2). The paragraph citing [20] asserts only qualitative convergence as epsilon goes to 0; no quantitative bound of the form |g_epsilon^* - g_0^*| <= rho(epsilon) is derived. The experiments fix epsilon = 0.01, yet the paper presents the computed values as the RDP function. Without a quantified bias in epsilon, the numerical results in Tables 1 and 2 are for an unquantified approximation of the quantity that the paper claims to compute.","section":"Section 3.2, Eq. (13), and Theorem 5"},{"comment":"The KL convergence proof assumes that \\tilde w(r) is a global minimizer of subproblem (6) and that it admits the representation (8) in terms of Lagrange multipliers. However, constraint (6d), sum_j p_j log(sum_i p_i w_ij) >= T, is a lower bound on a concave function, so the feasible set of (6) is generally nonconvex. The paper does not establish convexity of (6), nor KKT sufficiency, nor strong duality for this nonconvex problem. Without such an argument, the fundamental inequality in Lemma 2 that drives Theorem 3 is not justified, and Theorem 3 cannot be read as a proof of global convergence to f(w*, r*).","section":"Section 4.1, Lemma 2 and Theorem 3"},{"comment":"The proofs that the inner loops converge are incomplete as stated. The authors assert that the implemented updates coincide with alternating minimization of F1 and F2, but no detailed correspondence is given, and the derivation in Theorem 2 contains an apparent error: the b-update is written with log(-sum_j r_j e^{...}), which has a negative argument and is undefined. In addition, the Newton root-finding steps for a_j, gamma, and lambda are stated without local or global convergence analysis. Since the inner convergence is a premise for Theorems 3 and 5, this is a load-bearing gap: the inner loop as pseudocoded is not yet proven to converge to the exact inner minimizer.","section":"Section 4.1, Theorem 2, and Section 4.2, Theorem 4"}],"minor_comments":[{"comment":"In the first line of the proof, the inequality W(p, r*) <= sum_{i,j} Pi*_{ij} c_{ij} <= D should read <= P, because the perception constraint is (12e), not the distortion constraint. The typo is confusing in a proof that is otherwise about feasibility.","section":"Section 3.2, proof of Theorem 1"},{"comment":"The symbol D is used both for the distortion budget and for the KL divergence D(. || .). These two uses appear in the same equations and should be renamed (for example, use an uppercase script or a different letter for the divergence).","section":"Throughout, in particular Lemmas 2, 3, and Theorem 3"},{"comment":"The notation 'simeq O(1/n)' in Theorem 3 and 'O(1/n)' in Theorem 5 should be replaced by a precise big-O statement with an explicit constant, since the proof actually yields a bound with a finite constant C depending on the initial KL divergence and, in the Wasserstein case, a bound of the form epsilon C/((1+epsilon)^n - 1).","section":"Section 4, Theorems 3 and 5"},{"comment":"The Gaussian discretization parameters S and delta are fixed without a convergence study; the paper does not report how the computed RDP value depends on S and delta or whether the results are in the asymptotic regime of the discretization.","section":"Section 5, Eq. (19)"},{"comment":"The output lines return sum_{i,j} w_ij p_i (log w_ij - log r_j), which is the objective value rather than 'Minimal value'; this wording should be clarified so that the reader knows whether the reported quantity is the objective at the final iterate or a computed lower/upper bound.","section":"Algorithms 1 and 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's novelty depends substantially on the authors' own prior CBA and IAS work (refs. [10] and [7]), and the present manuscript does not clearly separate the new convergence contribution from the previously reported algorithmic structure. The main advertised theorem is not yet established for the implemented algorithms, so the major revision is required. If the authors can supply an inner-loop rate with a stopping criterion, correct the Algorithm 2 marginal update, quantify the entropy-regularization bias, and address the nonconvexity issue in Lemma 2, the paper could become a solid contribution to the RDP computation literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one with the stress-test concern in mind: it is real. The paper has a genuine new idea—relaxing the RDP constraint and proving an outer-loop O(1/n) rate for an exact alternating scheme—but the convergence theorem does not cover the algorithm as implemented. The abstract overstates the guarantee.\n\nWhat is actually new: Theorem 1 gives an equivalent (or entropy-regularized) reformulation that avoids the non-convex perceptual constraint, and Lemmas 2–3 plus Theorem 3 give a clean telescoping argument for the KL case. The Wasserstein analogue in Theorem 5 is a genuine extension, with an epsilon-dependent factor that still yields O(1/n). The proof is self-contained convex analysis; the rate is not fitted, and there is no circularity beyond relying on the authors' prior CBA machinery. The numerical tables show consistent speedups over IAS, though only against their own predecessor and with no code shipped.\n\nSoft spots, in order of severity. First, the load-bearing gap: Theorems 3 and 5 define wtilde(r) as an exact minimizer of the inner problem, while Algorithms 1 and 2 run a finite inner loop with a vaguely specified stopping rule and no rate. The telescoping argument does not control the quantity actually computed. If inner suboptimality contributes (1/n) times the sum of per-step errors, the paper needs either an inner complexity bound or a tolerance schedule. This must be fixed before the O(1/n) claim can be accepted. Second, Algorithm 2's update for what the text calls phi-hat_i should be p_i divided by the sum of exponentials, not one divided by that sum, because the constraint is sum_j Pi_ij = p_i. As written, the beta update does not enforce the source marginal. This looks like a typo, since the derivation in the text has the right form, but the pseudocode will not reproduce the theory. Third, the entropy-regularization bias is not quantified: Theorem 5 is for the regularized problem, and the citation to entropic OT convergence supplies no rate or explicit bound back to the original RDP value. Fourth, smaller issues: the proof of Theorem 1 has a P/D typo, there are repeated 'Kulback' and indexing typos, and no reproducibility details are included.\n\nThe underlying approach is sound and the result is plausibly repairable. I would send this to serious peer review and require major revision. I would not cite the O(1/n) claim as it currently stands.","headline":"The outer-loop O(1/n) result is a real advance for an exact alternating scheme, but the paper overstates it as a guarantee for the implemented algorithms, and the Wasserstein pseudocode has a marginal-constraint bug.","tokens_in":16555,"tokens_out":5097,"would_cite":false,"duration_ms":53335,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","90C25","94A34"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes an $O(1/n)$ convergent primal-dual algorithm for the information rate-distortion-perception function under KL and entropy-regularized Wasserstein perception measures.","keywords":["rate-distortion-perception function","optimal transport","Wasserstein distance","KL divergence","primal-dual algorithm","O(1/n) convergence","entropic regularization","alternating minimization"],"falsifier":"Under the paper's exact-inner-solve assumption, take a Bernoulli source with $p=0.1$, Hamming distortion, and total-variation perception, compute the RDP value by exhaustive enumeration over small alphabets, and run the algorithm with increasingly exact inner solves and a range of outer iterations; the gap $f(w_n,r_n)-f(w^*,r^*)$ should follow a $C/n$ envelope. A plateau above that envelope would contradict the $O(1/n)$ claim; separately, comparing the entropy-regularized Wasserstein output to the unregularized value as $\\varepsilon\\to0$ tests Theorem 5.","tokens_in":15483,"feed_emoji":"📉","tokens_out":14364,"duration_ms":135631,"temperature":0.7,"pith_summary":"The paper targets the information rate-distortion-perception (RDP) function, a three-way trade-off among compression rate, distortion, and perceptual similarity of reconstructions. Its central move is to relax the hard constraint on the reconstruction distribution and instead alternate optimization over the channel and over that distribution directly, a reformulation that preserves the optimal value (Theorem 1). The main claim is that the resulting primal-dual algorithm, named IAS-II, converges in objective value at rate $O(1/n)$ for both KL-divergence perception and entropy-regularized Wasserstein perception. If true, this supplies the first rigorous convergence-rate guarantee for computing RDP functions, turning a problem previously handled by heuristic adversarial training or empirically convergent optimal-transport schemes into one with a worst-case accuracy certificate.","feed_headline":"One algorithm now computes rate-distortion-perception curves with O(1/n) error","feed_subtitle":"Primal-dual proof gives a 1/n convergence rate for KL and Wasserstein perception constraints.","key_machinery":"The load-bearing mechanism is the alternating minimization of a convex dual potential built from the channel, the reconstruction marginal, and (in the Wasserstein case) an auxiliary coupling $\\Pi$. The key object is the exact marginal update $r_j=\\sum_i p_i w_{ij}$, which gives the reconstruction distribution in closed form and turns the perceptual constraint into an optimization variable. For the Wasserstein case, the entropy term $\\varepsilon H(\\Pi)$ makes the inner problem strictly convex, and entropic optimal transport convergence justifies taking $\\varepsilon\\to0$. The convergence proof rests on Lemmas 2 and 6, which show that each outer step decreases the objective by at least a marginal KL divergence, and on monotonicity (Lemmas 4 and 8); a telescoping sum converts those decreases into the $O(1/n)$ bounds of Theorems 3 and 5.","core_discovery":"The paper's central claim is that the discrete information RDP problem (2) can be solved by a relaxed primal-dual algorithm with a provable objective-error rate. The perceptual constraint $d(p,r)\\le P$ is replaced by an optimization over the reconstruction marginal $r$, so the problem alternates between updating the channel $w$ and updating $r$; Theorem 1 states that the optimum is unchanged. Under KL perception, Theorem 3 shows $f(w_n,r_n)-f(w^*,r^*)=O(1/n)$ when each inner subproblem is solved exactly. Under entropy-regularized Wasserstein perception, Theorem 5 gives $g(w_n,\\Pi_n,r_n)-g(w^*,\\Pi^*,r^*)\\le \\varepsilon C/((1+\\varepsilon)^n-1)$, and choosing $\\varepsilon$ optimally for a fixed $n$ keeps the rate $O(1/n)$. The reconstruction marginal $r_n$ is always the output marginal $\\sum_i p_i w_{n,i}$, so it is updated in closed form in both cases.","pith_inferences":["An unstated but natural corollary is that the outer-rate proof would transfer to any perception measure whose reconstruction marginal can be updated in closed form from the channel; the paper does not test that generalization.","The theorems assume exact inner solves, so a practical stopping rule for the inner updates would be needed to turn the $O(1/n)$ bound into a runtime guarantee; the paper leaves that unspecified.","A concrete testable extension would be a schedule $\\varepsilon=\\Theta(1/n)$ in the Wasserstein algorithm; the bound then gives an explicit iteration count for a target tolerance, but the paper does not derive such a schedule or report its empirical cost.","The constants in the bounds inherit the KL divergence $D(r^*\\|r_1)$ and may grow with alphabet size; analyzing that dependence would decide whether the rate guarantee is useful for high-dimensional discretized sources."],"forward_implications":["For KL-divergence perception, the objective gap $f(w_n,r_n)-f(w^*,r^*)$ decays as $O(1/n)$ with exact inner solves, so the number of outer iterations needed for a fixed accuracy grows linearly in the inverse tolerance.","For entropy-regularized Wasserstein perception, the bound $g(w_n,\\Pi_n,r_n)-g(w^*,\\Pi^*,r^*)\\le \\varepsilon C/((1+\\varepsilon)^n-1)$ holds, and choosing $\\varepsilon$ with $n$ gives the same $O(1/n)$ rate while $\\varepsilon\\to0$ recovers the original Wasserstein RDP value.","Because the relaxation preserves the optimal value (Theorem 1), the computed curve is the information RDP function itself rather than an approximation of a nearby problem.","Total-variation perception is a special case of the Wasserstein formulation with cost $c_{ij}=\\mathbf{1}_{i\\neq j}$, so the $O(1/n)$ guarantee also covers TV perception.","In the reported experiments, IAS-II matches the accuracy of the earlier IAS algorithm while running faster, with speed-ups from about 1.2x to 13x in the reported settings."],"supporting_citations":[{"why":"Defines the Wasserstein-barycenter model (WBM-RDP) and the earlier IAS algorithm that IAS-II extends and compares against in the experiments.","marker":"[7]"},{"why":"Supplies the constrained formulation and the dual-variable updates that the KL and Wasserstein inner loops adapt.","marker":"[10]"},{"why":"Provides the entropic optimal transport convergence result used to justify recovering the original Wasserstein perception constraint as the entropy parameter tends to zero.","marker":"[20]"},{"why":"States the representation of total-variation distance as an optimal-transport distance with the cost $c_{ij}=\\mathbf{1}_{i\\neq j}$, which lets the TV case be treated by the same algorithm.","marker":"[26]"}],"fun_headline_variants":["Primal-dual algorithm gives O(1/n) convergence for RDP functions","New proof: rate-distortion-perception computed with 1/n error","First rigorous O(1/n) rate for RDP computation","Convergent primal-dual method solves RDP with O(1/n) guarantee","Algorithm computes RDP curves with provable O(1/n) convergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Every $O(1/n)$ theorem assumes the inner optimization is solved exactly at each outer step, while the implemented algorithms only run a finite inner loop with no stated stopping criterion, so the proof does not directly cover the practical code.","fun_headline_variants_meta":{"raw":{"variants":["Primal-dual algorithm gives O(1/n) convergence for RDP functions","New proof: rate-distortion-perception computed with 1/n error","First rigorous O(1/n) rate for RDP computation","Convergent primal-dual method solves RDP with O(1/n) guarantee","Algorithm computes RDP curves with provable O(1/n) convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000235,"raw_usage":{"total_tokens":1523,"prompt_tokens":990,"completion_tokens":533,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":434}},"tokens_in":606,"tokens_out":533,"duration_ms":5300,"temperature":1.0,"reasoning_tokens":434,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:14:55.405479+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Under the paper's exact-inner-solve assumption, take a Bernoulli source with $p=0.1$, Hamming distortion, and total-variation perception, compute the RDP value by exhaustive enumeration over small alphabets, and run the algorithm with increasingly exact inner solves and a range of outer iterations; the gap $f(w_n,r_n)-f(w^*,r^*)$ should follow a $C/n$ envelope. A plateau above that envelope would contradict the $O(1/n)$ claim; separately, comparing the entropy-regularized Wasserstein output to the unregularized value as $\\varepsilon\\to0$ tests Theorem 5.","supporting_citations":[{"cited_title":"In: IEEE International Sym- posium on Information Theory (ISIT), pp","cited_arxiv_id":null,"evidence_quote":"Defines the Wasserstein-barycenter model (WBM-RDP) and the earlier IAS algorithm that IAS-II extends and compares against in the experiments."},{"cited_title":"CSIAM Trans- actions on Applied Mathematics 6(2), 350–379 (2025)","cited_arxiv_id":null,"evidence_quote":"Supplies the constrained formulation and the dual-variable updates that the KL and Wasserstein inner loops adapt."},{"cited_title":"Probability Theory and Related Fields 184(1), 401–424 (2022)","cited_arxiv_id":null,"evidence_quote":"Provides the entropic optimal transport convergence result used to justify recovering the original Wasserstein perception constraint as the entropy parameter tends to zero."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the representation of total-variation distance as an optimal-transport distance with the cost $c_{ij}=\\mathbf{1}_{i\\neq j}$, which lets the TV case be treated by the same algorithm."}],"review_version":2}