REVIEW 3 major objections 6 minor 18 references
Efficient Computation of Marton's Error Exponent via Constraint Decoupling
T0 review · 3 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper introduces AM-CD, an alternating maximization algorithm that computes Marton's error exponent and its inverse in a fraction of the time of existing grid-search methods.
desk verdict Fast, well-tested algorithm, but the equality-constrained reformulation at the core is not generally valid—overclaims Marton-exponent computation. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the dual representation of the rate-distortion function, $R(\Delta,p_X)=\max_{\zeta,a\ge 0}[-\zeta\Delta+\sum_i p_X(x_i)\log(a_i/p_X(x_i))]$ subject to $\sum_i a_i e^{-\zeta d(x_i,y_j)}\le 1$ for all $j$, combined with the constraint-decoupling step that converts the nested Marton problem into one joint maximization. For fixed $\zeta$, the subproblem is convex in $(p,a)$: the $p$-update has closed form $p_i\propto q_i^{\frac{1}{\lambda+1}}a_i^{\frac{\lambda}{\lambda+1}}$ after finding the monotone root of a scalar function, and the $a$-update is obtained by solving the primal rate-distortion problem through alternating conditional updates, then converting back via $a_i=p_i/\sum_j e^{-\zeta d_{ij}}r_j$. The outer layer is a one-dimensional line search over $\zeta$ on a uniform grid.
What would settle it
Take a discrete source and distortion for which the optimal reproduction distribution at the chosen distortion leaves at least one symbol unused, so the dual constraints have slack; run AM-CD and compare with an exhaustive search over a fine grid of $(p,\zeta,a)$. A mismatch between the two values would falsify Lemma 1 and the claimed equivalence.
Extended reading notes
Core claim
The central discovery is that the two optimization models defining Marton's error exponent $E_M(R,\Delta,q)$ and its inverse $R_M(E,\Delta,q)$ can be rewritten as composite maximization problems in which, for a fixed dual variable $\zeta$, the remaining objective is jointly convex in $(p,a)$. Lemma 1 replaces the rate-distortion constraint together with the dual inequality constraints by equality constraints $\sum_i a_i e^{-\zeta d(x_i,y_j)}=1$ for every $j$, so that the two unknown distributions can be updated alternately with closed-form updates and a monotone root-finding step for the multiplier. The paper establishes that the limit point of these alternating iterates satisfies the KKT conditions and is the global optimizer of the fixed-$\zeta$ subproblem, and that the outer line search over $\zeta$ selects the best exponent.
Load-bearing premise
The central reformulation assumes that, at the optimum, every inequality constraint in the dual rate-distortion problem is active, meaning each equality replacement loses nothing; if the optimal reproduction distribution does not use some reconstruction symbols, this equality model may compute a different value.
Editorial extensions
If this is right
- Both $E_M(R,\Delta,q)$ and $R_M(E,\Delta,q)$ become directly computable by the same alternating-maximization routine, eliminating the need to invert one function to get the other.
- For fixed $\zeta$, the alternating iterates converge to the global optimizer of the convex subproblem, so no ad-hoc initialization is needed beyond the one-dimensional grid over $\zeta$.
- Numerical experiments show speedups of roughly 31-to-43 times over the grid search on Gaussian and Laplacian sources, with comparable or better accuracy because Newton's method resolves the multiplier exactly.
- The algorithm reproduces the theoretical discontinuity in Ahlswede's counterexample, including the jump from $E_L=0.1255$ to $E_R=0.9147$ at $R=1.5669$, indicating the method tracks non-smooth features of the exponent.
Reading between the lines
- Because the equality-constraint assumption in Lemma 1 is asserted rather than proved, the method should be tested on sources whose optimal reproduction distribution leaves some reconstruction symbols unused; the current experiments do not include such a case.
- The proof of global convergence covers the inner fixed-$\zeta$ problem; the outer search samples a uniform grid, so the reported global optimum is the best grid point unless an additional certified step over $\zeta$ is added.
- The same constraint-decoupling trick may extend to other error exponents with nested rate-distortion structure, such as strong converse exponents, with a concrete test being to run the same two-layer scheme on Dueck-Körner style exponents.
- An adaptive or bracketing search over $\zeta$ could replace the uniform grid and likely reduce computation further; the paper does not explore this refinement.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an alternating-maximization algorithm (AM-CD) for computing Marton's error exponent EM(R,Delta,q) and its inverse RM(E,Delta,q). Starting from the dual rate-distortion representation, the authors reformulate the nested optimization as a composite maximization in variables (p,zeta,a), then for fixed zeta solve a convex subproblem by alternating updates of p and a, with the a-update computed via the Blahut-Arimoto algorithm. Theorems 1 and 2 claim convergence for fixed zeta, and numerical experiments on discretized Gaussian and Laplacian sources and on Ahlswede's counterexample report order-of-magnitude speedups over the grid-search method of [6].
Significance. If the reformulation were valid, the paper would offer a practically useful and substantially faster method for an important information-theoretic quantity, with the appealing feature of reproducing the discontinuous Ahlswede example. The numerical comparisons are carefully benchmarked, and the reported speedups are consistent with replacing a two-dimensional grid by a one-dimensional line search plus Newton iterations. However, the central equivalence on which the algorithm and the convergence results rest is false, and the algorithm's iterates do not in general satisfy the constraints of the model being solved.
major comments (3)
- [Section III, Eq. (4) and Lemma 1] The statement after Eq. (4) that the dual rate-distortion maximum is reached only when every constraint sum_i a_i exp(-zeta d_ij) <= 1 holds with equality is false. For fixed zeta, the inner maximization over a has inequality constraints, and complementary slackness allows some constraints to be inactive at the optimum. Consequently, replacing the inequalities by equalities in (5b) and (6b) changes the problem. A concrete instance: take M=2, N=3, p=(1/2,1/2), and distortion columns d(.,y1)=(0,1), d(.,y2)=(1,0), d(.,y3)=(1/4,3/4). For any zeta>0, the three equalities sum_i a_i exp(-zeta d_ij)=1 force a1=a2=1/(1+exp(-zeta)) and then require (exp(-zeta/4)+exp(-3zeta/4))/(1+exp(-zeta))=1, which holds only at zeta=0. At zeta=0 the rate expression is -D(p||a)<=0, so model (6) is infeasible for any R>0, while problem (2) is feasible whenever R<=R(Delta,p) by taking p=q. Lemma 1 is therefore invalid, and Theorems 1 and 2 analyze a model that is not the Marton exponent problem. The same defect carries over to Lemma 2 and model (7).
- [Section IV-A, Eq. (10), and Appendix B] The Blahut-Arimoto update for a does not enforce the equality constraints of model (6). At a BA fixed point, sum_i a_i exp(-zeta d_ij)=1 holds only for indices j with r_j>0; for r_j=0 the corresponding equality is not guaranteed. Since the optimal reproduction distribution in the rate-distortion problem can have zero components, Algorithm 1's output is not necessarily feasible for (6). The convergence proofs in Appendix B assume the iterates satisfy the constraints, so they do not apply to the algorithm as stated. Algorithm 2 inherits the same issue.
- [Appendix B, proof of Theorem 1] The descent calculation contains an algebraic error. With u_ij^(n)=w_ij^(n) r_j^(n) and v_ij^(n)=u_ij^(n)/p_i^(n), the asserted identity a_i^(n)=exp(zeta d_ij) v_ij^(n) is false: the right-hand side equals r_j^(n)^2/(B_i p_i^(n)) with B_i=sum_j exp(-zeta d_ij) r_j^(n), whereas a_i^(n)=p_i^(n)/B_i. The subsequent decomposition into KL divergences and the KKT conclusion therefore do not follow. A similar issue affects the proof of Theorem 2.
minor comments (6)
- [Abstract] The verb 'demonstrates' should agree with the plural subject 'experiments', and the comma before 'demonstrates' creates a comma splice; consider rephrasing.
- [Section I] The word 'tighest' should be 'tightest'.
- [Eq. (4)] The maximization is over zeta>=0 in the standard dual rate-distortion formula, but the nonnegativity constraint on zeta is not stated; the later line search over zeta>=0 suggests this was intended.
- [Section III, model (5)] Model (5) is not well-typed: the variables zeta and a appearing in (5b) are not quantified, and (5c) uses an inner max that makes the constraint non-explicit; a correct reformulation should use existential quantifiers over zeta,a and inequality constraints.
- [Theorems 1 and 2] Theorems 1 and 2 only establish convergence for a fixed zeta; the outer grid search over zeta is finite and provides no global optimality certificate, so the abstract's claim of 'global convergence of the algorithm' is stronger than what is proven.
- [Algorithms 1 and 2] The variable a is used in the first lambda-update or xi-update before being initialized; the pseudocode should specify an initial value, for example a_i=1 or the BA output for an initial r.
Circularity Check
No significant circularity: the algorithm is derived from the standard dual rate-distortion formulation and validated against external benchmarks; the flagged Lemma 1 concern is a correctness issue, not a circularity.
full rationale
The derivation chain starts from Marton's error exponent (2), substitutes the dual RD representation (4), and derives composite models (6) and (7) via Lemma 1. None of these steps defines the target in terms of the algorithm's output or fits a parameter to the quantity being predicted. The only load-bearing equivalence, Lemma 1, asserts that the inequality constraints in the dual RD problem can be replaced by equalities; the supplied counterexample suggests this equivalence can fail, but a false equivalence is a mathematical validity defect, not circularity. The algorithm is benchmarked against the external grid-search method [6] and against Ahlswede's counterexample, and no fitted scientific constants or self-citation chain is used to force the results. Accordingly, no circular step can be exhibited under the required standard.
Assumptions & free parameters
free parameters (2)
- zeta grid mesh size delta =
100 points on [0,5]
- stopping tolerance =
10^-5
assumptions (3)
- standard math Dual RD representation (Berger, Thm 2.5.3) with non-negative a_i and inequality constraints
- ad hoc to paper Equality condition in the dual RD max is necessary and sufficient
- domain assumption Blahut-Arimoto algorithm converges to the exact optimum of the fixed-zeta RD subproblem
Cite this review
Pith. "Pith review of Efficient Computation of Marton's Error Exponent via Constraint Decoupling." pith.science (2026). https://pith.science/paper/5CGXBVHZ
@misc{pith2026250719816,
author = {Pith},
title = {Pith review of: Efficient Computation of Marton's Error Exponent via Constraint Decoupling},
year = {2026},
howpublished = {\url{https://pith.science/paper/5CGXBVHZ}},
note = {Machine review of arXiv:2507.19816}
}
read the original abstract
The error exponent in lossy source coding characterizes the asymptotic decay rate of error probability with respect to blocklength. The Marton's error exponent provides the theoretically optimal bound on this rate. However, computation methods of the Marton's error exponent remain underdeveloped due to its formulation as a non-convex optimization problem with limited efficient solvers. While a recent grid search algorithm can compute its inverse function, it incurs prohibitive computational costs from two-dimensional brute-force parameter grid searches. This paper proposes a composite maximization approach that effectively handles both Marton's error exponent and its inverse function. Through a constraint decoupling technique, the resulting problem formulations admit efficient solvers driven by an alternating maximization algorithm. By fixing one parameter via a one-dimensional line search, the remaining subproblem becomes convex and can be efficiently solved by alternating variable updates, thereby significantly reducing search complexity. Therefore, the global convergence of the algorithm can be guaranteed. Numerical experiments for simple sources and the Ahlswede's counterexample, demonstrates the superior efficiency of our algorithm in contrast to existing methods.
Figures
Reference graph
Works this paper leans on
-
[6]
Computation of Marton’s error exponent for discrete memoryless sources,
Y . Jitsumatsu, “Computation of Marton’s error exponent for discrete memoryless sources,” in IEEE International Symposium on Informa- tion Theory (ISIT) . IEEE, 2023, pp. 1372–1377
work page 2023
-
[1]
A simple derivation of the coding theore m and some applications,
R. G. Gallager, “A simple derivation of the coding theore m and some applications,” IEEE Trans. Inform. Theory , vol. 11, pp. 3–18, Jan. 1965
work page 1965
-
[2]
Lower bounds to error probability for coding on discrete memoryless channels,
C. Shannon, R. Gallager, and E. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels,” Inf. Control., vol. 10, pp. 65–103, 1967
work page 1967
-
[3]
F, Probabilistic Information Theory, Discrete and Memoryles s Mod- els
J. F, Probabilistic Information Theory, Discrete and Memoryles s Mod- els. New Y ork: McGraw-Hill, 1968
work page 1968
-
[4]
Hypothesis testing and information theory,
R. Blahut, “Hypothesis testing and information theory, ” IEEE Trans- actions on Information Theory , vol. 20, no. 4, pp. 405–417, 1974
work page 1974
-
[5]
Error exponent for source coding with a fideli ty criterion,
K. Marton, “Error exponent for source coding with a fideli ty criterion,” IEEE Transactions on Information Theory , vol. 20, no. 2, pp. 197–199, 1974
work page 1974
-
[7]
Computation of channel capacity and rate-di stortion func- tions,
R. Blahut, “Computation of channel capacity and rate-di stortion func- tions,” IEEE Transactions on Information Theory , vol. 18, no. 4, pp. 460–473, July 1972
1972
-
[8]
Extremal properties of rate distortion fu nctions,
R. Ahlswede, “Extremal properties of rate distortion fu nctions,” IEEE Transactions on Information Theory, vol. 36, no. 1, pp. 166–171, 1990
work page 1990
Show all 18 references
-
[9]
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, July 1948
1948
-
[10]
T. M. Cover and J. A. Thomas, Elements of Information Theory . Wiley-Interscience, 2006
2006
-
[11]
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
-
[12]
Reliability Function of a Dis crete Memoryless Channel at Rates Above Capacity,
G. Dueck and J. K. Korner, “Reliability Function of a Dis crete Memoryless Channel at Rates Above Capacity,” IEEE Transactions on Information Theory , vol. 25, no. 1, 1979
1979
-
[13]
Csiszár and J
I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems . Cambridge University Press, 2011
2011
-
[14]
Exponential source/channe l duality,
S. Tridenski and R. Zamir, “Exponential source/channe l duality,” in IEEE International Symposium on Information Theory (ISIT) . IEEE, 2017, pp. 3140–3144. APPENDIX A PROPERTIES OF FUNCTIONS FE(λ) AND FR(ξ) In Section IV , we propose the root-finding of monotonic functions FE(λ...
2017
-
[15]
The Root Existence and Monotonicity of FE(λ): We have FE(0) = ∑ i qi log ai qi − ζ∆ − R < −ζ∆ + ∑ i qi log ai qi − R(∆, q) ≤ R(∆, q) − R(∆, q) = 0 . The first inequality holds because R > R (∆, q), otherwise by the definition of Marton’s error exponent (2), q will be a feasible ...
-
[16]
Thus, we can employ New- ton’s method for root-finding in the case of FR(0) > 0
The Monotonicity of FR(ξ): We have F ′ R(ξ) = − 1 (1 + ξ)3 I0I2 − I 2 1 I 2 0 ≤ 0, Ik = ∑ i e log ai +ξ log qi 1+ξ ( log ai qi ) k , k = 0, 1, 2, where the inequality holds from Cauchy-Schwarz’s inequal- ity, hence FR(ξ) is monotonic. Thus, we can employ New- ton’s method for ...
-
[17]
Proof of Theorem 1: We have a(n) i = p(n) i ∑ j e−ζdij r(n) j = p(n) i w(n) ij e−ζdij r(n) j = eζdij v(n) ij , ∀j. So we have fE(p(n+1)) − fE(p(n)) = ∑ i p(n) i (log p(n) i − log qi) − ∑ i p(n+1) i (log p(n+1) i − log qi) = ∑ i p(n) i (log p(n) i − log qi) − ∑ i p(n+1) i (log ...
-
[18]
fR(p(n+1), a(n+1)) − fR(p(n+1), a(n)) = ∑ i p(n+1) i (log a(n+1) i − log a(n) i ) = ∑ i,j p(n+1) i w(n+1) ij log v(n+1) ij v(n) ij = ∑ j r(n+1) j D(v(n+1) j ‖v(n) j )
Proof of Theorem 2: We have fR(p(n+1), a(n)) − fR(p(n), a(n)) = ∑ i p(n+1) i (log a(n) i − log p(n+1) i ) − ∑ i p(n) i (log a(n) i − log p(n) i ) − ξ(n+1)∑ i p(n+1) i (log p(n+1) i − log qi) + ξ(n+1)∑ i p(n) i (log p(n) i − log qi) = − ∑ i p(n+1) i ( (ξ(n+1) + 1) log p(n+1) i ...
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.