{"id":"0ea4a0b2-32c5-4561-abff-fa5bed4e05f4","arxiv_id":"2507.18025","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A coded multi-task learning scheme is claimed to achieve optimal communication loads under a mild data-placement condition, but the optimality proof applies a lower bound that is invalid for the general number of data batches.","lead":"This paper proposes a coded communication scheme for distributed multi-task learning that claims to hit the theoretical minimum uplink and downlink traffic under a mild data-placement condition. The paper's optimality claim relies on a lower bound that is only proven for the special case where the number of data batches equals the number of workers, and the scheme can require workers to send a negative number of packets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is false as stated: Condition 1 permits d_k < 0, so the §IV construction cannot run for the valid instance K=4, N=6, Z1={1}, Z2=Z3=Z4={1..6}.","rationale":"The reader's verdict correctly rejects the paper, and the reader did mention the nonnegativity of d_k in the same counterexample. However, the reader's primary stated weakest assumption was that Lemma 1's lower bound is applied to N != K, and the reader also suggested that the claimed uplink load being smaller than the downlink load is itself impossible. That latter comparison is not a valid information-theoretic constraint in this model: the server may broadcast more than it receives. The load-bearing flaw is narrower and stronger: the achievability scheme in Section IV and Algorithm 1 requires each worker to send a nonnegative integer number of packets, d_k, but Condition 1 does not enforce this. The exhibited placement satisfies Condition 1 yet gives d1 = -10, so the construction cannot even be formulated, and Theorem 1 is false as stated. This is an internal inconsistency in the paper's own framework, not a disagreement with an external consensus. Fixing it would require adding d_k >= 0 to Condition 1 (or to the theorem's hypotheses) and then checking whether optimality still holds; additionally, the N != K extension of Lemma 1 would need a separate proof. Because the main claim of optimality for general heterogeneous placements fails on a legal instance, rejection is appropriate.","tokens_in":107,"tokens_out":3869,"duration_ms":53057,"concrete_test":"Run the counterexample through the construction: set K=4, N=6, Z1={1}, Z2=Z3=Z4={1,...,6}; compute d_k from (11), S, and P_k from (12); verify Condition 1 holds. Then attempt to execute Algorithm 1: step 8 yields d1=-10 and step 15 requires solving A1*B1 = 0 with A1 of size -10 x S, which has no matrix-theoretic meaning; equivalently, the Hall matching in Lemma 6 would need to match a negative number of vertices, so the proof of Lemma 4 cannot produce the required disjoint subsets. This directly confirms that Theorem 1 must be restricted to placements with all d_k >= 0, or the theorem is false.","verdict_should_be":"REJECT","load_bearing_attack":"Proposition 1 fixes worker k's number of transmitted packets as d_k = N + (K-1)|Z_k| - sum_{k'} |Z_{k'}|, and Theorem 1 claims a scheme exists whenever Condition 1 holds. But Condition 1 does not imply d_k >= 0. In the instance K=4, N=6, Z1={1}, Z2=Z3=Z4={1,...,6}, equation (11) gives d1 = 6+3-19 = -10, d2=d3=d4 = 6+18-19 = 5, and S=5. The sets P_k from (12) are P1 of size 15 and P2=P3=P4=empty, so Condition 1 reduces to |P1| <= S-d1 (15<=15) and 0 <= S-(d1+d2) etc., all true. Yet the proposed uplink process requires worker 1 to transmit d1=-10 coded packets, which is impossible. Algorithm 1 and Lemma 4 construct A_k as a d_k x S matrix; a negative d_k makes these objects undefined. Thus the theorem's existential claim is internally inconsistent: a system satisfying Condition 1 exists for which the stated scheme cannot be executed, independent of whether the lower-bound Lemma 1 is valid for N != K. The paper's examples all have positive d_k, but the theorem as written covers all placements satisfying Condition 1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers a distributed multi-task learning (DMTL) system with K workers and N data batches, where each worker stores an arbitrary subset Zk. It proposes to model the uplink and downlink encoding as a matrix factorization P = AB, with B an MDS matrix, and claims that under a placement-dependent condition (Condition 1) the scheme achieves the information-theoretically optimal uplink and downlink communication loads for arbitrary heterogeneous placements. The proof is based on a lower bound cited from [12], a Hall-marriage argument for constructing an invertible A, and a decoding step using the MDS property. The paper also reports numerical comparisons with [12] and [33] and claims an extension to distributed linearly separable computation.","tokens_in":23769,"tokens_out":18188,"duration_ms":190014,"significance":"If correct, the result would be a substantial step: previous optimal coded MTL schemes were limited to symmetric placements, and a general optimal scheme for heterogeneous placements has been an open problem. The matrix-decomposition formulation is a useful unifying viewpoint, and the paper contains a fully worked example and numerical comparisons. However, the central optimality claim is not valid as stated. The lower bound used for the uplink is taken from a lemma stated only for N = K and is false for a concrete (K = 4, N = 6) instance; moreover, Condition 1 does not prevent the prescribed number of transmitted packets d_k from being negative, so the proposed algorithm is not even executable for some instances satisfying its hypotheses. A third issue in the proof of Lemma 6 (the Hall step) is demonstrably false for a positive-d_k instance. These are load-bearing, not cosmetic, defects. The conceptual framework may still be salvageable, but the paper in its current form does not establish the advertised optimality.","major_comments":[{"comment":"The lower bound L*_up is imported from Lemma 1, which is explicitly restricted to (K, N = K) systems. Theorem 1 then asserts the same expression for arbitrary N, and Proposition 1 uses it. This extension is not only unproved but false. Consider K = 4, N = 6, Z1 = {1}, Z2 = Z3 = Z4 = {1,...,6}. Here d1 = -10, d2 = d3 = d4 = 5, S = 5; the claimed L*_up is (24 - 19)/3 = 5/3, while the claimed L*_down is 6 - 1 = 5. In any scheme, the server's broadcast X is a deterministic function of the uplink messages, so the downlink normalized load cannot exceed the total uplink normalized load; hence the pair (5/3, 5) cannot be achieved. The claimed formula for L*_up is therefore invalid for N != K, and Theorem 1's optimality statement collapses for the general setting advertised in the paper.","section":"Section III.A, Theorem 1 with Lemma 1"},{"comment":"The construction requires each worker k to transmit d_k coded packets, but Condition 1 does not imply d_k >= 0. In the same (K = 4, N = 6) instance as above, d1 = -10 while Condition 1 holds: |P1| = 15 = S - d1, P2 = P3 = P4 = empty, so all inequalities in Condition 1 reduce to 0 <= S - sum_i d_i, which hold with equality at k = 4. Algorithm 1 line 15 would need a matrix A1 with -10 rows, and Proposition 1 asks worker 1 to send -10 packets. Thus Theorem 1 asserts existence of a scheme for a system in which its own scheme cannot be executed; the theorem is internally inconsistent as stated. The examples in the paper all have positive d_k, but that is not guaranteed by the stated hypotheses.","section":"Section III.A, Eq. (11), Proposition 1, and Algorithm 1"},{"comment":"This inequality is used to ensure |Ai| >= di, but it does not follow from Condition 1 and is false in general. Take K = 3, N = 6, Z1 = {5,6}, Z2 = {1,2,3,4}, Z3 = {3,4,6}. Then d = (1,5,3), S = 9, P1 = {1,2,3,4,7,8,9,10}, P2 = {5,6,11,12}, P3 = {1,2,5,7,8,11}. Condition 1 holds: |P1| = 8 <= 8, |P1 ∩ P2| = 0 <= 3, and the triple intersection is empty. Yet |P2 ∩ P3| = 2 > S - (d2 + d3) = 1. Lemma 6 would require a subset of P3 of size d2 = 5 disjoint from P2, but P3 \\ P2 has only 4 elements, so the claimed matching does not exist. Since Lemma 6 underlies Lemma 5 and hence Lemma 4, the Hall-marriage proof of Theorem 1 is not valid even for instances with all d_k positive.","section":"Appendix C, Lemma 6 and the inequality |Pk ∩ Pi| <= S - (dk + di)"}],"minor_comments":[{"comment":"Algorithm 1 is titled '(K, N=K; ...)' but is applied to general (K,N); the header should be corrected.","section":"Algorithm 1 header"},{"comment":"Lemmas 2 and 3 state that the subsets {Z_k} are subsets of [K]; for the general (K,N) model they should be subsets of [N].","section":"Lemmas 2 and 3"},{"comment":"The Vandermonde example contains corrupted entries such as 'w w 11' and 'w w 14'; these should be cleaned up.","section":"Section III.C example"},{"comment":"The definition of P_{k,j} says 'dk > 0 rows'; since d_k can be zero or negative under the stated assumptions, the definition should either impose d_k >= 0 as an explicit hypothesis or be reformulated.","section":"Section IV.A, matrix P_{k,j} definition"},{"comment":"Remark 3's LSC extension is dimensionally unclear: B' has (K-1)(N - min_k r_k) rows, while the matrix F of the LSC problem has N_c rows; the claimed identification needs a separate argument.","section":"Remark 3, LSC extension"},{"comment":"Reference [34] is cited as 'Hall's marriage theorem, 2025'; a standard textbook or Hall's original paper would be more appropriate.","section":"Reference [34]"}],"recommendation":"reject","confidential_remarks":"The manuscript is very close in formulation and notation to reference [12], which is coauthored by one of the current authors; the provenance of the general-N lower bound should be checked carefully by the editor, since the paper relies on it without proving it. The counterexamples in this report are elementary and can be independently verified. Even if the authors repair the proof, the main theorem's scope will need to be narrowed, for example to N = K or to an additional d_k >= 0 condition combined with a valid lower bound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: the paper's central theorem is false as stated. Lemma 1's lower bound is proved only for N=K, and Theorem 1 applies it to arbitrary N. For K=4, N=6, with Z1={1} and Z2=Z3=Z4={1,...,6}, the claimed L*_up is 5/3 while L*_down is 5; the server would broadcast more than it receives. Worse, the d_k defined in (11) can be negative: the same example gives d1=-10, Condition 1 is satisfied, and the theorem asserts a scheme in which worker 1 sends -10 packets. The §IV construction is undefined for negative d_k.\n\nThe paper is not a waste of time. The matrix decomposition P=AB—storage constraints as zero-patterns in the uplink matrix, demands as MDS properties of the downlink matrix—is a genuinely new reformulation for DMTL. The use of Hall's theorem to prove invertibility is a plausible route, the worked example is thorough, and the extension to linearly separable computation is a nice observation. The comparison to [12] and [33] is fair, and the self-citation to [12] is not an issue.\n\nThe flaws are load-bearing. First, the N=K to N≠K jump is unjustified; the counterexample kills it. Second, d_k≥0 is never established; Condition 1 does not prevent negative d_k. Third, the proof of Lemma 6 uses |P_k∩P_i| ≤ S-(d_k+d_i) for arbitrary pairs, but Condition 1 only bounds initial-segment intersections, so the matching argument looks unproved. These are not minor.\n\nWho should read this? Someone interested in the matrix-decomposition framing might mine the idea for a correct scheme under N=K with d_k≥0. But as written, the main theorem is false and the numerical claims in Fig. 2 lean on it.\n\nRecommendation: desk reject. Tell the authors the reformulation has merit, but the main claim needs to be restricted and the proof of Lemma 6 fixed before resubmission.","headline":"The matrix-decomposition framing is fresh, but the main theorem is false: the lower bound only holds for N=K, and the construction permits negative d_k.","tokens_in":24272,"tokens_out":9080,"would_cite":false,"duration_ms":81386,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94B05","68P30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims a coded scheme that, under a data-placement condition, simultaneously attains the provable minimum uplink and downlink communication loads in distributed multi-task learning, including heterogeneous worker storage.","keywords":["distributed multi-task learning","coded computing","communication load","matrix decomposition","MDS codes","heterogeneous data placement","linearly separable computation","Hall's marriage theorem"],"falsifier":"A concrete disproof would be a placement with $N\\neq K$ that satisfies Condition 1 yet has $d_k = N + (K-1)|Z_k| - \\sum_{k'} |Z_{k'}|$ negative for some worker, or has the claimed $L^*_{\\text{up}}$ smaller than $L^*_{\\text{down}}$; either observation would make the scheme's per-worker packet counts and the server's broadcast impossible. One candidate to check is $K=4,N=6$ with $Z_1=\\{1\\}$ and $Z_2=Z_3=Z_4=\\{1,\\ldots,6\\}$, where the formula gives $L^*_{\\text{up}}=5/3$, $L^*_{\\text{down}}=5$, and $d_1=-10$.","tokens_in":23245,"feed_emoji":"📡","tokens_out":12116,"duration_ms":113853,"temperature":0.7,"pith_summary":"Distributed multi-task learning trains several personalized models at once, with workers sending local updates to a server and receiving a broadcast that lets each worker update its own model; communication, not computation, is usually the bottleneck. This paper tries to show that the communication bottleneck can be removed up to provable limits even when workers store unequal, arbitrary subsets of the data. It models the whole scheme as a matrix factorization and then constructs one code that simultaneously achieves the smallest possible uplink and downlink traffic under a mild data-placement condition. A sympathetic reader should care because earlier optimal coded schemes only worked in symmetric settings; if the construction is right, optimal communication becomes available in general heterogeneous deployments, and the same design transfers to distributed linearly separable computation.","feed_headline":"Distributed multi-task learning hits optimal communication","feed_subtitle":"New proof shows upload and download loads can both hit their lower bounds, even with uneven data placement.","key_machinery":"The load-bearing object is the matrix decomposition $P=AB$, which unifies the two communication directions. The uplink matrix $P$ stacks each worker's coded transmissions; its zero-column pattern reflects exactly which packets worker $k$ cannot compute. The downlink matrix $B$ is an MDS matrix over a finite field with $q > \\max\\{S, N(K-1)\\}$, so all its square submatrices are invertible, and the server broadcasts $B'\\mathbf{v}$. The invertible matrix $A$ is assembled from row blocks $A_k$ that annihilate the columns of $B$ corresponding to packets worker $k$ lacks. Condition 1, $|\\cap_{i\\in[k]} P_i| \\le S - \\sum_{i\\in[k]} d_i$ for every $k\\in[K]$, is the Hall-type combinatorial condition that guarantees such an $A$ exists: for every prefix of workers, the intersection of their missing-packet sets is small enough that the zero blocks can be matched disjointly. Hall's Marriage Theorem turns this inequality into the disjoint subsets needed to prove the row blocks are linearly independent.","core_discovery":"The paper's central claim is Theorem 1: in a $(K,N;\\{Z_k\\})$ DMTL system satisfying Condition 1, there exists a scheme with minimum communication loads $L^*_{\\text{up}} = \\frac{KN}{K-1} - \\sum_{z\\in[K]} \\frac{z|I_z|}{K-1}$ and $L^*_{\\text{down}} = N - \\min_k |Z_k|$, where $I_z$ is the set of data batches stored by exactly $z$ workers. The construction splits every local update into $K-1$ packets and represents transmissions by matrices: the uplink matrix $P$ has zero blocks exactly where a worker lacks data, and the downlink matrix $B$ is chosen with the MDS (Maximum Distance Separable) property, so that any sufficiently small square submatrix is invertible. The proof shows that Condition 1, an intersection bound on the sets of packets absent from each worker, is exactly what is needed for the row blocks $A_1,\\ldots,A_K$ to span the full space, making $A$ invertible in $P=AB$. If correct, this is the first optimal coded MTL scheme that handles heterogeneous data placement, and the uplink half of the same construction is claimed to solve distributed linearly separable computation for arbitrary placement.","pith_inferences":["The matrix-decomposition view suggests a natural research direction: formulating the converse bound itself as a rank constraint on the uplink matrix $P$, which would give a unified proof for all $N$ and all placements.","Condition 1 is checkable directly from the storage sets, so practitioners could add a quick feasibility test before deploying the scheme; a natural next step is an efficient algorithm that verifies it and outputs the matrices $A$ and $B$.","Because $B$ is an MDS matrix, a straggler-tolerant variant suggests itself: if a worker fails to upload its $d_k$ packets, the server may still broadcast as long as the remaining rows of $P$ span enough of the space, and verifying when erased rows preserve invertibility is a direct extension.","The same decomposition may apply to decentralized settings where no central server exists, since the broadcast step only needs a common MDS matrix available to all workers; whether the invertibility condition still holds under gossip-style communication is untested."],"forward_implications":["For any placement satisfying Condition 1, the proposed scheme's loads equal $L^*_{\\text{up}}$ and $L^*_{\\text{down}}$, so no coded scheme can do better for those placements.","The optimality subsumes the symmetric equal-load cases treated by earlier schemes and extends to unequal computation loads and asymmetric data placement.","The downlink broadcast size is $N - \\min_k |Z_k|$ regardless of total storage, so the least-stored worker determines the broadcast cost.","The uplink construction transfers to distributed linearly separable computation, where it handles non-cyclic heterogeneous data placements that prior linearly separable computation schemes could not.","In the paper's $(K=4,N=6)$ numerical comparison, the scheme matches the lower bounds at every tested computation load while the prior schemes leave an uplink gap."],"supporting_citations":[{"why":"Supplies the lower-bound formulas and the prior coded MTL scheme that this paper's optimal scheme extends and is measured against.","marker":"[12]"},{"why":"Gives the hierarchical coded MTL scheme whose communication loads are compared numerically and which is outperformed in heterogeneous cases.","marker":"[33]"},{"why":"Hall's Marriage Theorem is the combinatorial tool used to partition missing-packet sets and prove the invertibility of matrix A.","marker":"[34]"},{"why":"Cited for the existence of MDS matrices over a finite field, which constructs the downlink matrix B.","marker":"[36]"},{"why":"Defines distributed linearly separable computation, the problem to which this paper's uplink construction is extended.","marker":"[26]"},{"why":"Provides the prior LSC scheme limited to cyclic data placement, whose limitation motivates the extension claim.","marker":"[27]"}],"fun_headline_variants":["Coded DMTL scheme hits optimal communication bounds","Distributed multi-task learning reaches lower-bound communication","Optimal communication for heterogeneous DMTL achieved","New coded scheme attains optimal MTL communication cost","Coded DMTL achieves optimal upload and download loads"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the lower-bound formula for the uplink load being true for every $N$, although the cited lemma proves it only for $N=K$; when $N>K$ the formula can come out smaller than the downlink load, which would make the claimed optimum impossible even if Condition 1 holds.","fun_headline_variants_meta":{"raw":{"variants":["Coded DMTL scheme hits optimal communication bounds","Distributed multi-task learning reaches lower-bound communication","Optimal communication for heterogeneous DMTL achieved","New coded scheme attains optimal MTL communication cost","Coded DMTL achieves optimal upload and download loads"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000544,"raw_usage":{"total_tokens":2651,"prompt_tokens":1040,"completion_tokens":1611,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":1546}},"tokens_in":656,"tokens_out":1611,"duration_ms":11753,"temperature":1.0,"reasoning_tokens":1546,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:43:09.167580+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete disproof would be a placement with $N\\neq K$ that satisfies Condition 1 yet has $d_k = N + (K-1)|Z_k| - \\sum_{k'} |Z_{k'}|$ negative for some worker, or has the claimed $L^*_{\\text{up}}$ smaller than $L^*_{\\text{down}}$; either observation would make the scheme's per-worker packet counts and the server's broadcast impossible. One candidate to check is $K=4,N=6$ with $Z_1=\\{1\\}$ and $Z_2=Z_3=Z_4=\\{1,\\ldots,6\\}$, where the formula gives $L^*_{\\text{up}}=5/3$, $L^*_{\\text{down}}=5$, and $d_1=-10$.","supporting_citations":[{"cited_title":"Communication-efficient coded computing for distributed multi-task learning,","cited_arxiv_id":null,"evidence_quote":"Supplies the lower-bound formulas and the prior coded MTL scheme that this paper's optimal scheme extends and is measured against."},{"cited_title":"On exploiting network topology for hierarchical coded multi-task learning,","cited_arxiv_id":null,"evidence_quote":"Gives the hierarchical coded MTL scheme whose communication loads are compared numerically and which is outperformed in heterogeneous cases."},{"cited_title":"Hall’s marriage theorem,","cited_arxiv_id":null,"evidence_quote":"Hall's Marriage Theorem is the combinatorial tool used to partition missing-packet sets and prove the invertibility of matrix A."},{"cited_title":"Xing and S","cited_arxiv_id":null,"evidence_quote":"Cited for the existence of MDS matrices over a finite field, which constructs the downlink matrix B."},{"cited_title":"Distributed linearly separable computation,","cited_arxiv_id":null,"evidence_quote":"Defines distributed linearly separable computation, the problem to which this paper's uplink construction is extended."},{"cited_title":"Fundamental limits of distributed linearly separable computation under cyclic assignment,","cited_arxiv_id":null,"evidence_quote":"Provides the prior LSC scheme limited to cyclic data placement, whose limitation motivates the extension claim."}],"review_version":1}