{"id":"8a2cf7c8-9621-40c7-ba3f-671d8dd945a8","arxiv_id":"2501.18312","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors propose PPS quantization for distributed optimization and derive accelerated methods with large deviation bounds.","lead":"A new compression scheme, PPS, samples vector coordinates with probability proportional to their size, and the authors build accelerated primal and primal-dual optimization methods around it with large-deviation convergence bounds. The paper claims near-optimal communication and lower second-moment error on simplex-structured gradients, with applications to decentralized Wasserstein barycenter computation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's sub-Gaussian constant is incorrect; the exponential moment can be e^e, so the concentration proofs do not follow as written.","rationale":"The reader's weakest-assumption identification is correct and it is the most load-bearing point in the paper. My independent check confirms that the claimed alpha in Lemma 1 is too small by a factor of e: for the uniform simplex vector the exponential moment equals e^e, not e. The proof step 'Since we strive for E_k[||v-e_k||^2/alpha] <= e' is not sufficient for the desired concentration inequality; Jensen's inequality connects E[X] to exp(E[X]), not to E[exp(X)]. All later theorems use Lemma 1's sigma^2_{r,M}, so the theoretical results are unproven. I did not find a separate flaw that would change the verdict; the counterexample makes the rejection warranted. I note in good faith that the flaw is a constant-factor error rather than a collapse of the method: replacing alpha by (1-1/n) seems to restore a valid sub-Gaussian-type estimate, and the eO rates would survive with variance inflated by a factor e. However, as submitted, the central lemma and the quantitative claims depending on it are false.","tokens_in":18985,"tokens_out":10592,"duration_ms":104812,"concrete_test":"Directly evaluate the claimed one-sample exponential moment in Lemma 1 for v = (1/n, ..., 1/n): X = ||v - e_k||^2 = 1 - 1/n, so with alpha = (1-1/n)/e, E_{k~v}[exp(X/alpha)] = exp(e) ~= 15.15 > e ~= 2.72. This single counterexample invalidates the bound used to define sigma^2_{r,M}. A useful follow-up check is whether alpha' = (1-1/n) satisfies E_{k~v}[exp(||v-e_k||^2/alpha')] <= e for every v in the simplex; if yes, the convergence-rate theorems can likely be restored with all sigma^2_{r,M} multiplied by e.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Lemma 1, after reducing to the one-sample quantization error X=||v-e_k||^2 with k drawn from P_v, the authors require E_k[exp(X/alpha)] <= e. They then compute (1/n) sum_k ||v-e_k||^2 >= 1 - 1/n and conclude that alpha = (1-1/n)/e suffices. This is a Jensen/quantifier error: a bound on E[X] does not imply the stated exponential moment, and the numerical value is wrong. Taking v = (1/n, ..., 1/n), the correct sampled distribution is uniform, X = 1 - 1/n, and the claimed alpha gives E[exp(X/alpha)] = exp(e) = e^e > e. Thus the hypothesis used in Lemma 1 is false. Since Lemma 5 and the subsequent large-deviation estimates (Theorems 1-4, Corollary 1, and the bit-count formulas in Sections 4.3-4.4) all invoke sigma^2_{r,M} from Lemma 1, their proofs do not hold as written. A factor-e larger variance, alpha = (1-1/n), appears to repair the statement, so the algorithmic idea may survive revision, but the paper's stated theoretical guarantees and Table 1's second-moment entry are not supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a 'probability-proportional-to-size' (PPS) quantization scheme for distributed convex optimization: a vector is split into positive and negative parts, mapped to categorical distributions, and sampled M times to produce an unbiased sparse estimator. This estimator is inserted into accelerated primal and primal-dual methods. The central theoretical claim is Lemma 1, which asserts a sub-Gaussian bound for the PPS-estimated gradient with parameter sigma^2_{r,M} = 50(2(1-1/n)B^2/(eM) + sigma^2_r). From Lemma 1 the paper derives large-deviation convergence guarantees (Theorems 1-4, Corollary 1, Corollary 3), including communication-bit complexity bounds, and applies the method to decentralized Wasserstein-barycenter computation with numerical experiments.","tokens_in":19239,"tokens_out":9017,"duration_ms":86500,"significance":"If Lemma 1 were correct, the paper would be a valuable contribution: the PPS estimator would be communication-efficient, unbiased, and would have an attractive second-moment behavior on simplex-structured gradients, and the paper would provide the first accelerated distributed primal-dual method combining quantization, stochasticity, and large-deviation bounds. The manuscript also contains an application and reproducible-looking experiments. However, the proof of Lemma 1 contains a distribution mismatch and an invalid step from a mean bound to an exponential-moment bound, and the lemma is false as stated. Since all convergence and bit-complexity results depend on this lemma, the theoretical claims are not currently supported. The approach may be repairable by correcting the sub-Gaussian constant and supplying a genuine proof, but this is a substantial revision rather than a local fix.","major_comments":[{"comment":"The proof reduces the problem to the condition E_k[exp(||v-e_k||^2/alpha)] <= e for k drawn from P_v(k)=v_k, but then computes E_k[||v-e_k||^2] as the uniform average (1/n) sum_k(...). These two distributions agree only when v is uniform. Under P_v one has E[||v-e_k||^2] = 1 - ||v||_2^2, not ||v||_2^2 - 2/n + 1. More importantly, a bound on the mean of ||v-e_k||^2/alpha does not imply the required bound on its exponential moment; the step 'we have (1-1/n)/alpha <= e, from where alpha=(1-1/n)/e' is a Jensen/quantifier error.","section":"§2, Lemma 1"},{"comment":"Concrete counterexample: take v = (1/n,...,1/n). Then k is drawn uniformly and X = ||v-e_k||^2 = 1 - 1/n with probability one. Under the claimed alpha = (1-1/n)/e, E_k[exp(X/alpha)] = exp(e) = e^e > e, so the hypothesis used inside Lemma 1 fails. In fact alpha = 1 - 1/n would give the value e for this example, indicating the constant is off by a factor e. The tightness remark in the proof concerns only the mean, not the exponential moment, so it does not rescue the lemma.","section":"§2, Lemma 1, proof"},{"comment":"All downstream results inherit sigma^2_{r,M} from Lemma 1: Lemma 5 uses it in every large-deviation estimate, Theorems 1–4 use it in the epsilon(T,delta,...) formulas and in parameter choices such as M_t = 2(1-1/n)B^2/(e sigma^2 r_t), and Corollaries 1 and 3 use it in the communication-bit counts. Since Lemma 1 is not proven and is false with the stated constant, the convergence and complexity bounds as stated do not follow. This error is load-bearing, not a local typo.","section":"§4–§5 and Appendix A"}],"minor_comments":[{"comment":"The definition 'Delta_n = {x >= 0 || sum_i x_i = 1}' should use ':' or '|' instead of the norm symbol '||' in the set-builder notation; as printed, the definition is unreadable.","section":"§1, Notation"},{"comment":"The sentence 'The following theorem is similar to Theorem 2' appears before Theorem 2 is stated; reorder or renumber the sections to avoid a forward reference.","section":"§4.1"},{"comment":"The symbol xi is used both for stochastic oracle noise and for the uniform reference distribution in Eq. (9) and the surrounding text; this collision makes the entropy-regularization term confusing and should be disambiguated.","section":"§6.1"},{"comment":"The axis labels and curve legends in the reproduced figures contain corrupted text (e.g., '1 o2', '10°'), which makes the experimental comparison difficult to read; the figures should be regenerated with clean labels.","section":"§6.2, Figures 1–2"}],"recommendation":"major_revision","confidential_remarks":"For the editor: I am recommending major revision rather than outright rejection because the flaw is a concrete mistake in a key lemma and the estimator may be salvageable with a corrected constant and a genuine proof of the exponential-moment bound. However, this is a substantial revision: all constants in the main theorems and their proofs would need to be re-derived. The references to prior works ([15]–[17], [23], [27]) are used legitimately as building blocks; I see no circularity or novelty-disclosure problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"PPS quantization is a genuinely neat idea: sample coordinates proportionally to their absolute value, send a few indices, and get an unbiased gradient estimate with near-optimal bit cost when the gradient lies in a simplex. The paper also makes a serious attempt at large-deviation bounds for accelerated primal-dual decentralized methods, and the Wasserstein barycenter experiments show the method works in practice. That's real substance.\n\nThe problem is Lemma 1. The proof needs E_k[exp(||v-e_k||^2/alpha)] <= e, but it only lower-bounds E_k[||v-e_k||^2] >= 1 - 1/n and then sets alpha = (1-1/n)/e. That's the wrong direction: Jensen gives exp(E[X]/alpha) <= E[exp(X/alpha)], so a lower bound on E[X] can't upper-bound the exponential moment. For the uniform simplex vector, X = 1 - 1/n deterministically, and with the claimed alpha the exponential moment is exp(e) = e^e, not e. The lemma is false as written, and since Theorems 1-4 and Corollary 1 all feed on sigma^2_{r,M} from Lemma 1, the theoretical results don't hold. The good news is the fix is cheap: taking alpha = 1 - 1/n (a factor e larger variance) restores the inequality for the uniform case and likely for the general case, so the algorithm may survive with slightly worse constants. But the paper as submitted does not prove its advertised guarantees.\n\nSecondary issues: Table 1's second-moment entry carries the same factor-e error; Section 6.3's simplified variance inherits it. The reliance on prior lemmas from the authors' earlier work is not itself a problem, but the novel lemma is the one that fails. The experiments are a plus, but they don't patch the theory.\n\nVerdict: this is a promising idea with a load-bearing proof error. I would send it to peer review—a good referee can catch this and the authors can fix it—but I would not cite the current version's guarantees. The paper is worth a reading group if you want a crisp example of a quantifier/Jensen slip in an otherwise serious optimization paper.","headline":"The PPS quantization idea is genuinely interesting, but Lemma 1's sub-Gaussian bound is wrong by a factor of e, and every subsequent theorem rides on it.","tokens_in":19740,"tokens_out":2948,"would_cite":false,"duration_ms":26627,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes a probability-proportional-to-size (PPS) quantized gradient oracle and accelerated primal-dual methods, deriving large-deviation convergence guarantees for affine-constrained and decentralized stochastic convex…","keywords":["probability-proportional-to-size quantization","distributed convex optimization","accelerated gradient method","quantized gradient oracle","large deviations","primal-dual algorithm","Wasserstein barycenter"],"falsifier":"Set $v=(1/n,\\dots,1/n)$, draw $k$ from the categorical distribution with probabilities $v_k$, and evaluate $E_k[\\exp(\\|e_k-v\\|^2/\\alpha)]$ with $\\alpha=(1-1/n)/e$. For every $k$, $\\|e_k-v\\|^2=1-1/n$, so the expectation equals $\\exp(e)>e$, contradicting the inequality the proof of Lemma 1 relies on. The same calculation with $k$ drawn uniformly, the sampling used in the proof, returns exactly $e$.","tokens_in":18804,"feed_emoji":"📉","tokens_out":12411,"duration_ms":228728,"temperature":0.7,"pith_summary":"The paper attacks the communication bottleneck of distributed optimization with a new way to quantize a vector before it is sent: split a mini-batched stochastic gradient into positive and negative parts, turn each part into a categorical distribution with probabilities proportional to component magnitudes, and sample a sparse zero-one vector from it. The resulting PPS oracle is unbiased, costs only 2 floats plus 2M log n bits per message, and has a second moment that shrinks as 1/M, making it competitive with near-optimal compressors and better than them when gradients live in a simplex. The paper's main claim is that this oracle is sub-Gaussian with a computable variance, and that this concentration property feeds accelerated primal and primal-dual algorithms for affine-constrained problems, giving epsilon,delta guarantees on both objective accuracy and constraint satisfaction. It then converts those results into a decentralized method and reports that the method matches optimal rates up to eO(1) factors while transmitting far fewer bits, with experiments on semi-discrete entropy-regularized Wasserstein barycenters.","feed_headline":"PPS sampler cuts communication in distributed optimization","feed_subtitle":"Sampling gradient entries by size keeps accelerated convergence while sending only M log n bits per round","key_machinery":"The PPS quantized gradient oracle: for a mini-batched stochastic gradient $G$, split it as $G=[G]_+ - [-G]_+$, draw $M$ indices from the categorical distribution with probabilities $P_G(k)=[G_k]_+/\\|[G]_+\\|_1$ and $M$ more from $P_{-G}$, and return $\\frac{\\|[G]_+\\|_1}{M}\\sum_i e_{k_i} - \\frac{\\|[-G]_+\\|_1}{M}\\sum_i e_{l_i}$. This object carries the whole argument because its unbiasedness gives correctness, its message format $2|\\mathrm{float}|+2M\\log_2 n$ gives the communication cost, and Lemma 1's sub-Gaussian bound gives the large-deviation estimates that Theorem 2 and Corollary 1 convert into $\\epsilon,\\delta$ rates. The algorithms additionally couple $r_t$ and $M_t$ iteration by iteration so quantization noise and stochastic noise enter the bounds on equal footing.","core_discovery":"On its own terms, the paper's central discovery is that sampling gradient components with probability proportional to their magnitude yields a quantized estimate that is simultaneously unbiased, cheap to encode, and concentrated enough to drive accelerated primal-dual methods. The formal core is Lemma 1: for the PPS oracle, $E_{\\xi,k,l}[\\exp(\\|\\mathrm{PPS}(x,\\xi,k,l)-\\nabla f(x)\\|^2/\\sigma_{r,M}^2)] \\le e$ with $\\sigma_{r,M}^2=50(2(1-1/n)B^2/(eM)+\\sigma_r^2)$, where $B$ bounds the $\\ell^1$ norm of the oracle. From this sub-Gaussian inequality, Theorem 2 gives high-probability accuracy and constraint-violation bounds for affine-constrained problems; Theorems 3 and 4 show how to set the batch size $r_t$ and the sample count $M_t$ to minimize oracle calls and transmitted bits; and Corollary 1 turns the result into a decentralized algorithm whose communication complexity depends on graph parameters such as diameter and maximum degree. The paper claims these rates are optimal up to $\\tilde O(1)$ factors and are the first to combine stochasticity, quantization, and primal-dual large-deviation guarantees.","pith_inferences":["A corrected sub-Gaussian constant in Lemma 1 would alter only constants inside the $\\tilde O(\\cdot)$ rates, not the qualitative structure of Theorems 1-4, because every later bound depends on $\\sigma_{r,M}$ polynomially.","The same large-deviation technology could be reused for non-Euclidean prox setups if the sub-Gaussian lemma is re-proved with a proper dimension-dependent constant; the paper notes its results are intended to generalize but works out the Euclidean case only.","For objectives whose gradients are simplex-valued, PPS should behave as a drop-in communication compressor for federated logistic regression and Sinkhorn-type optimal transport solvers, since its second moment is constant in dimension there; the paper tests only the Wasserstein barycenter case.","A natural stress test is to run the same primal-dual algorithm with uniform random sampling instead of size-proportional sampling; comparing the two under identical bit budgets would isolate what the PPS design itself contributes beyond cheap encoding."],"forward_implications":["One communicated message under PPS costs $2$ floats plus $2M\\log_2 n$ index bits, so with small $M$ the per-round communication is logarithmic in the dimension rather than linear.","If Lemma 1 stands, the accelerated primal-dual method returns an $\\epsilon$-accurate and $\\epsilon/R$-feasible point with probability at least $1-\\delta$, with an $\\tilde O(\\max\\{\\sqrt{LR^2/\\epsilon},\\sigma^2R^2/\\epsilon^2,\\sigma^2L^2/(\\epsilon^2\\|A\\|_2^2)\\})$ oracle-call count.","The variable-batch schemes of Theorems 3 and 4 let the user balance stochastic noise and quantization noise: more samples per iteration $r_t$ or more component samples $M_t$ reduce the variance terms in the rates, at known bit and arithmetic costs.","In the decentralized setting of Algorithm 3, each node transmits $\\tilde O(B^2 d\\log n\\max\\{...\\})$ bits with dependence on the graph's diameter, maximum degree, and mixing constant, so denser networks and noisier oracles reduce communication.","For the Wasserstein barycenter application, the gradient of the entropy-regularized dual lies in the simplex, so PPS's second moment does not blow up with dimension; the experiments confirm that $M=1$ with modest batch sizes already tracks the unquantized baseline."],"supporting_citations":[{"why":"Supplies the accelerated stochastic first-order method and the coefficient conditions that Algorithm 2 inherits.","marker":"[15]"},{"why":"Supplies the sub-Gaussian concentration lemmas on which Lemma 1 and the large-deviation proofs rest.","marker":"[16]"},{"why":"Provides the affine-constrained formulation and the Wasserstein barycenter dual oracle used in Section 6.","marker":"[17]"},{"why":"Provides the large-deviation machinery and the J(T) factor appearing in the probability bounds of Theorems 1-2.","marker":"[23]"},{"why":"Establishes the decentralized quantization approach for Wasserstein barycenters that this paper extends in Algorithm 3.","marker":"[27]"},{"why":"Gives the nearly-optimal compression operator against which PPS's bit count and second moment are compared.","marker":"[2]"},{"why":"Provides the random-M quantization baseline whose n/M-1 second moment is compared with PPS in Table 1.","marker":"[29]"},{"why":"Supplies the graph Laplacian eigenvalue bounds used in Corollary 1's communication estimate.","marker":"[31]"},{"why":"Supplies the lower bounds for decentralized convex optimization that justify the claimed optimality up to eO(1) factors.","marker":"[36]"}],"fun_headline_variants":["Size-proportional gradient sampling speeds distributed optimization","PPS quantization: less communication, same convergence","Sample gradients by size to cut distributed communication","PPS sampling: smaller bit budgets, same convergence","Gradient entry sampling by magnitude slashes network traffic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 1's claim that the PPS estimator's error has exponentially decaying tails with the stated variance; the proof derives that constant by averaging over indices uniformly even though the method samples them with probability proportional to component size, and for the vector whose components are all equal, the claimed exponential-moment inequality fails.","fun_headline_variants_meta":{"raw":{"variants":["Size-proportional gradient sampling speeds distributed optimization","PPS quantization: less communication, same convergence","Sample gradients by size to cut distributed communication","PPS sampling: smaller bit budgets, same convergence","Gradient entry sampling by magnitude slashes network traffic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000702,"raw_usage":{"total_tokens":3147,"prompt_tokens":901,"completion_tokens":2246,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":2175}},"tokens_in":517,"tokens_out":2246,"duration_ms":16262,"temperature":1.0,"reasoning_tokens":2175,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:56:21.429056+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $v=(1/n,\\dots,1/n)$, draw $k$ from the categorical distribution with probabilities $v_k$, and evaluate $E_k[\\exp(\\|e_k-v\\|^2/\\alpha)]$ with $\\alpha=(1-1/n)/e$. For every $k$, $\\|e_k-v\\|^2=1-1/n$, so the expectation equals $\\exp(e)>e$, contradicting the inequality the proof of Lemma 1 relies on. The same calculation with $k$ drawn uniformly, the sampling used in the proof, returns exactly $e$.","supporting_citations":[{"cited_title":"Eigenvalues, diameter, and mean distance in graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the graph Laplacian eigenvalue bounds used in Corollary 1's communication estimate."},{"cited_title":"Optimal convergence rates for convex distributed optimization in networks","cited_arxiv_id":null,"evidence_quote":"Supplies the lower bounds for decentralized convex optimization that justify the claimed optimality up to eO(1) factors."},{"cited_title":"Decentralized algorithms for wasserstein barycenters","cited_arxiv_id":null,"evidence_quote":"Supplies the sub-Gaussian concentration lemmas on which Lemma 1 and the large-deviation proofs rest."},{"cited_title":"Decentralize and randomize: Faster algorithm for wasserstein barycenters.Advances in Neural Information Processing Systems, 31, 2018","cited_arxiv_id":null,"evidence_quote":"Provides the affine-constrained formulation and the Wasserstein barycenter dual oracle used in Section 6."},{"cited_title":"Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization","cited_arxiv_id":"1911.07363","evidence_quote":"Provides the large-deviation machinery and the J(T) factor appearing in the probability bounds of Theorems 1-2."},{"cited_title":"Distributed Optimization with Quantization for Computing Wasserstein Barycenters","cited_arxiv_id":"2010.14325","evidence_quote":"Establishes the decentralized quantization approach for Wasserstein barycenters that this paper extends in Algorithm 3."}],"review_version":1}