{"id":"45d49213-d3da-4482-a676-1ee25846b946","arxiv_id":"2507.19816","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"AM-CD computes Marton's error exponent and its inverse via a decoupled composite maximization with alternating updates and a one-dimensional line search.","lead":"This paper introduces AM-CD, a faster algorithm for computing Marton's error exponent, a key performance bound in lossy source coding. It replaces a costly two-dimensional grid search with a one-dimensional line search plus convex subproblems and reports order-of-magnitude speedups.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The equality-constrained reformulation in Lemma 1 is not valid: forcing every dual RD constraint to equality can make model (6) infeasible for ζ>0, so the algorithm may not be computing Marton's exponent as claimed.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing flaw: Lemma 1 assumes the dual RD maximum is attained only with all constraints active. My analysis confirms and strengthens this: the equality system can be infeasible for all ζ > 0 when N > M, making model (6) return the wrong value even in a simple binary-source example. This is not a question of convergence rates or numerical precision; the optimization model itself is not equivalent to Marton's exponent. I also note that the algorithm's BA update solves the inequality-constrained dual, so the paper's stated model and its actual computation diverge. The numerical validation, including Ahlswede's counterexample, is genuine evidence that the underlying alternating scheme may be salvageable, but it does not cover the infeasible-equality regime. Since the reader already assigned CONDITIONAL and the required fix is to replace '=' with '≤' in the dual constraints and repair the proofs, I do not move the verdict; the conditionality is correct and should be resolved before acceptance.","tokens_in":10627,"tokens_out":20790,"duration_ms":260541,"concrete_test":"Analytically verify the counterexample in the attack: set M = 2, N = 3, p = q = (0.5, 0.5), Δ = 0.05, R = 0.1, with distortion columns (0,1), (1,0), (0.25,0.75). Show that (2) gives EM = 0 because q satisfies R(Δ,q) ≥ R, while (6) is infeasible for ζ > 0 and gives rate ≤ 0 at ζ = 0, hence its optimum is -∞. If this is confirmed, Lemma 1 is refuted and the paper must replace the equalities in (5b)–(7b) with the original inequalities and re-derive the algorithm and convergence proofs, or restrict the alphabet sizes to N ≤ M and prove that equality can always be enforced at an optimum.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 1 (Section III) rests on the assertion after Eq. (4) that the dual RD maximum is reached only when every inequality constraint sum_i a_i e^{-ζd_ij} ≤ 1 holds with equality. This is false in general. The dual has M variables a_i but N constraints; when N > M, the equality system sum_i a_i e^{-ζd_ij} = 1 for all j is overdetermined and generically infeasible for ζ > 0, while the inequality-constrained dual value is finite. Concretely, take M = 2, N = 3, p = (0.5, 0.5), and distortion columns d(·,y1) = (0,1), d(·,y2) = (1,0), d(·,y3) = (0.25,0.75). For any ζ > 0, the first two equalities force a1 = a2 = 1/(1+e^{-ζ}); the third then requires (e^{-0.25ζ}+e^{-0.75ζ})/(1+e^{-ζ}) = 1, which holds only at ζ = 0. Thus model (6) has no feasible point with ζ > 0, and at ζ = 0 the rate expression is at most 0. If Δ = 0.05 and R = 0.1, the true problem (2) has q = p feasible with EM = 0, but (6) is infeasible. Therefore the equivalence in Lemma 1 fails, and Theorems 1–2 analyze the wrong model. Moreover, Algorithm 1's BA update produces a satisfying the inequality constraints, but when some r_j = 0 the corresponding equality in (6) is not enforced, so the algorithm's output is not even feasible for the model it claims to solve.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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].","tokens_in":11011,"tokens_out":12897,"duration_ms":126269,"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":[{"comment":"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":"Section III, Eq. (4) and Lemma 1"},{"comment":"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.","section":"Section IV-A, Eq. (10), and Appendix B"},{"comment":"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.","section":"Appendix B, proof of Theorem 1"}],"minor_comments":[{"comment":"The verb 'demonstrates' should agree with the plural subject 'experiments', and the comma before 'demonstrates' creates a comma splice; consider rephrasing.","section":"Abstract"},{"comment":"The word 'tighest' should be 'tightest'.","section":"Section I"},{"comment":"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":"Eq. (4)"},{"comment":"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.","section":"Section III, model (5)"},{"comment":"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.","section":"Theorems 1 and 2"},{"comment":"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.","section":"Algorithms 1 and 2"}],"recommendation":"reject","confidential_remarks":"The numerical experiments appear carefully done and the reported speedups are plausible, but the theoretical foundation of the paper is unsound. The equality-constrained reformulation is not equivalent to the original problem, and the algorithm's iterates do not necessarily satisfy the constraints of the model being solved. If the authors were to reformulate the algorithm around the inequality-constrained dual rate-distortion problem and repair the convergence proof, a resubmission could be considered; in its present form, the central claim is not supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know: the AM-CD algorithm is a real step forward in practice—tens of times faster than the grid search in [6], and it reproduces Ahlswede's counterexample. But the reformulation that justifies the algorithm has a load-bearing gap: the equality-constraint claim in Eq. (4) is not generally true, so Lemmas 1–2 and Theorems 1–2 analyze a model that can be infeasible for the true problem.\n\nThe constraint decoupling idea is genuinely new. Replacing the 2D search with a 1D line search plus an alternating update, with the RD subproblem solved by BA, is a sensible engineering contribution. The numerical work is careful: 100 repeats, clear speedup tables, and the Ahlswede curve comes out right. That is real evidence.\n\nThe problem is Section III. The paper states that the maximum in the dual RD representation is reached only when every inequality constraint is active. That is false. Standard complementary slackness says only the constraints corresponding to positive probabilities in the optimal reproduction distribution need be tight. When N > M, forcing all N equalities is generically infeasible for ζ > 0; the stress-test's 2×3 example demonstrates it cleanly. For N = M, the system can be square but the active-set issue remains if the optimal reproduction has zeros. So model (6) is not equivalent to (5) in general, and Algorithm 1's output is not necessarily feasible for the model it claims to solve. This is the central claim of the paper, so it is a serious flaw, not a cosmetic one.\n\nThe convergence proof is also thinner than advertised. Theorem 1 covers only fixed ζ, and the outer loop is a finite grid, so 'global convergence' over ζ is not established. Appendix B is a sketch that leans on the BA subproblem being solved exactly. That is fixable, but it needs real work.\n\nWhere does this leave the paper? The numerics suggest the algorithm often works when N ≤ M and the optimal reproduction has full support. For those cases it is a useful heuristic and likely faster than anything else around. But the general equivalence claims, and the title-level claim of efficiently computing Marton's exponent, are not supported.\n\nThis deserves a serious referee, but not acceptance in present form. I would send it to review with the expectation of major revision: either fix the reformulation using inequality constraints (and prove convergence for that), or restrict the claims to the full-support, N ≤ M regime and say clearly what is heuristic.","headline":"Fast, well-tested algorithm, but the equality-constrained reformulation at the core is not generally valid—overclaims Marton-exponent computation.","tokens_in":11510,"tokens_out":3239,"would_cite":false,"duration_ms":38504,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A34","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Marton's error exponent","rate-distortion function","lossy source coding","constraint decoupling","alternating maximization","Blahut-Arimoto algorithm","Ahlswede's counterexample","information theory"],"falsifier":"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.","tokens_in":10447,"feed_emoji":"⚡","tokens_out":9095,"duration_ms":94653,"temperature":0.7,"pith_summary":"This paper claims that Marton's error exponent, the tight asymptotic bound on how quickly error probability decays with blocklength in lossy source coding, can be computed efficiently despite its non-convex formulation. The authors convert the nested max-min definition into a single composite maximization by using the dual rate-distortion representation and decoupling the constraints into equality constraints. This yields a two-layer algorithm: a one-dimensional line search over the dual parameter $\\zeta$, with a convex two-variable subproblem solved by alternating updates of the source distribution and the dual variables. Reported experiments on Gaussian and Laplacian sources show tens-of-times speedups over the existing two-dimensional grid search, and the method reproduces the discontinuous behavior in Ahlswede's counterexample.","feed_headline":"Constraint decoupling computes Marton's error exponent 30-40x faster","feed_subtitle":"An alternating maximization routine plus a one-dimensional line search replaces the costly two-dimensional grid search.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the Marton error exponent that is the object of computation.","marker":"[5]"},{"why":"Supplies the two-dimensional grid-search baseline and the inverse-function formulation that AM-CD replaces.","marker":"[6]"},{"why":"Provides the alternating rate-distortion solver used as the inner update for the dual variables.","marker":"[7]"},{"why":"Provides Ahlswede's counterexample, used to test the algorithm on a discontinuous exponent.","marker":"[8]"},{"why":"Supplies the dual rate-distortion representation used for the constraint-decoupling reformulation.","marker":"[11]"}],"fun_headline_variants":["Marton's error exponent computed faster via alternating maximization","Constraint decoupling speeds up Marton exponent calculation","Efficient Marton exponent via convex subproblems","Line search plus convex updates accelerates Marton exponent","Decoupling trick makes Marton exponent tractable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Marton's error exponent computed faster via alternating maximization","Constraint decoupling speeds up Marton exponent calculation","Efficient Marton exponent via convex subproblems","Line search plus convex updates accelerates Marton exponent","Decoupling trick makes Marton exponent tractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000346,"raw_usage":{"total_tokens":1875,"prompt_tokens":903,"completion_tokens":972,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":899}},"tokens_in":519,"tokens_out":972,"duration_ms":10189,"temperature":1.0,"reasoning_tokens":899,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:00:12.597567+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Error exponent for source coding with a fideli ty criterion,","cited_arxiv_id":null,"evidence_quote":"Defines the Marton error exponent that is the object of computation."},{"cited_title":"Computation of Marton’s error exponent for discrete memoryless sources,","cited_arxiv_id":null,"evidence_quote":"Supplies the two-dimensional grid-search baseline and the inverse-function formulation that AM-CD replaces."},{"cited_title":"Extremal properties of rate distortion fu nctions,","cited_arxiv_id":null,"evidence_quote":"Provides Ahlswede's counterexample, used to test the algorithm on a discontinuous exponent."}],"review_version":1}