{"id":"cb9a1a2a-ff06-4a72-998a-508722eca859","arxiv_id":"2606.21873","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A one-bit quantized variant of Lloyd's algorithm for two-component sub-Gaussian mixtures achieves misclassification rates decaying exponentially with SNR comparable to unquantized data and exact recovery with separation only logarithmically worse than optimal.","lead":"This paper proposes the first one-bit clustering method for two-component sub-Gaussian mixture models using dithered quantization and a variant of Lloyd's algorithm. A smart generalist might read it to see how heavily quantized data can still support accurate clustering with performance close to full-precision methods in high dimensions.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Performance guarantees require non-spikiness on centers; random rotation enforces it only for p ≳ log n log log n (exact recovery)","rationale":"The reader's weakest_assumption directly identifies the same load-bearing premise (non-spikiness and its enforcement). No other internal inconsistency is visible from the abstract; the lower-bound claim of sharp constants is consistent with the upper-bound statement once the condition is granted. Because the full manuscript is referenced but not reproduced here, the same UNVERDICTED stance is retained.","tokens_in":1774,"tokens_out":352,"duration_ms":27544,"concrete_test":"Construct two spiky centers (one coordinate dominates the Euclidean norm) with separation satisfying the paper's explicit threshold, draw n sub-Gaussian samples, apply the dithered one-bit quantizer without rotation, run the Lloyd variant, and measure whether the misclassification rate still decays exponentially in the SNR; if the rate plateaus or decays only polynomially the necessity of non-spikiness is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (exponential misclassification decay comparable to unquantized case, plus exact recovery) is conditioned on a mild non-spikiness assumption on the two cluster centers. The abstract states this condition is needed for both the Lloyd variant analysis and the random-rotation argument. When centers are spiky the claimed rates may fail; rotation is invoked to restore the condition, but only succeeds w.h.p. for p ≳ 1 (partial) or p ≳ log n log log n (exact). This dimension threshold and the necessity of the condition are therefore the least-secured premises in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript proposes the first one-bit clustering method for two-component sub-Gaussian mixture models, using dithered one-bit quantization per entry. Under a mild non-spikiness condition on the cluster centers, a variant of Lloyd's algorithm is shown to achieve a misclassification rate decaying exponentially in the signal-to-noise ratio at a rate comparable to the unquantized setting. This implies exact recovery under an explicit separation condition exceeding the optimal unquantized threshold by only a logarithmic factor. When dimension p is large, a random rotation via a Haar-distributed matrix enforces the non-spikiness condition with high probability (p ≳ 1 for partial recovery; p ≳ log n log log n for exact recovery). A matching minimax lower bound establishes sharpness of the misclassification rate and separation condition, supported by numerical experiments.","tokens_in":1907,"tokens_out":580,"duration_ms":21259,"significance":"If the derivations hold, the work establishes the first rigorous performance guarantees for one-bit quantized clustering in this model class, achieving near-optimal exponential rates and exact recovery thresholds. Notable strengths include the matching lower bound with sharp constants and the explicit random-rotation argument that quantifies the dimension threshold needed to enforce non-spikiness. These elements provide a concrete bridge between quantized sensing and classical mixture-model theory.","major_comments":[{"comment":"The non-spikiness condition is load-bearing for both the Lloyd-variant upper bound and the exact-recovery claim (as stated in the abstract). The random-rotation argument is invoked to restore the condition, but the manuscript must explicitly derive the p ≳ log n log log n threshold for exact recovery and confirm that the failure probability is controlled uniformly over the two centers; without this derivation the conditional nature of the central claim remains incompletely substantiated.","section":"Abstract and rotation argument section"},{"comment":"The separation condition for exact recovery is claimed to exceed the unquantized optimum by only a logarithmic factor. The relevant theorem should contain an explicit side-by-side comparison of the two thresholds (including the precise logarithmic term) so that the “only logarithmic” statement can be verified directly against the lower bound.","section":"Exact recovery theorem"}],"minor_comments":[{"comment":"Notation for the dithered quantizer and the precise definition of the non-spikiness parameter should be introduced once in a dedicated preliminary section rather than scattered across the abstract and main text.","section":"Preliminaries"},{"comment":"The numerical section would benefit from an explicit statement of the parameter regimes (n, p, SNR) used in the simulations relative to the theoretical thresholds.","section":"Numerical results"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive assessment and constructive suggestions. We address the two major comments below and will revise the manuscript accordingly to improve clarity and completeness.","responses":[{"response":"We agree that an explicit derivation of the dimension threshold strengthens the presentation. In the revised version we will expand the random-rotation argument (currently sketched in the relevant section) to include a self-contained proof that the non-spikiness condition holds with high probability for p ≳ log n log log n under exact recovery, with the failure probability controlled uniformly over both centers via a union bound. The updated text will also clarify how this probability is absorbed into the overall success probability of the algorithm.","revision_made":"yes","referee_comment":"[Abstract and rotation argument section] The non-spikiness condition is load-bearing for both the Lloyd-variant upper bound and the exact-recovery claim (as stated in the abstract). The random-rotation argument is invoked to restore the condition, but the manuscript must explicitly derive the p ≳ log n log log n threshold for exact recovery and confirm that the failure probability is controlled uniformly over the two centers; without this derivation the conditional nature of the central claim remains incompletely substantiated."},{"response":"We will revise the exact-recovery theorem statement and its surrounding discussion to include a direct side-by-side display of the one-bit separation threshold and the corresponding unquantized threshold (both taken from the matching lower bound), explicitly isolating the logarithmic factor. This will allow immediate verification of the claimed gap without cross-referencing other results.","revision_made":"yes","referee_comment":"[Exact recovery theorem] The separation condition for exact recovery is claimed to exceed the unquantized optimum by only a logarithmic factor. The relevant theorem should contain an explicit side-by-side comparison of the two thresholds (including the precise logarithmic term) so that the “only logarithmic” statement can be verified directly against the lower bound."}],"tokens_in":1473,"tokens_out":422,"duration_ms":12925,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that the authors deliver the first one-bit clustering guarantees for this model using a dithered quantizer and a Lloyd variant. Under the non-spikiness condition they get exponential error decay comparable to full precision, and exact recovery when separation exceeds the unquantized optimum by only a log factor. When p is large they add a random rotation step that enforces the condition with high probability, needing p ≳ log n log log n for the exact-recovery case.\n\nThe work does a clean job of stating the upper bounds, matching them with a minimax lower bound that shows the constants are sharp in general, and including numerical checks. It extends the existing quantized clustering literature in a direct way without obvious circularity.\n\nThe soft spot is the non-spikiness assumption itself. The abstract is upfront that the rates and exact recovery require it, and the rotation fix only works above the stated dimension thresholds. For moderate p or spiky centers the claims do not apply, which narrows the practical scope. Without the full proofs it is also hard to judge whether the analysis hides large constants or extra log factors.\n\nThis is for readers working on high-dimensional statistics and resource-efficient mixture modeling. Someone in that subfield would get concrete new rates and the rotation idea. It deserves a serious referee because the claims are specific, the setup is standard, and the lower bound gives something to check against.","headline":"This paper gives the first one-bit clustering method for two-component sub-Gaussian mixtures, with misclassification rates decaying exponentially at rates close to the unquantized case under a non-spikiness condition on centers, plus exact recovery above a separation threshold only a log factor worse.","tokens_in":2378,"tokens_out":387,"would_cite":false,"duration_ms":21095,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"A variant of Lloyd's algorithm on one-bit dithered quantized samples clusters two-component sub-Gaussian mixtures with misclassification rates decaying exponentially in signal-to-noise ratio at rates comparable to full data.","keywords":["one-bit clustering","sub-Gaussian mixture models","Lloyd's algorithm","dithered quantization","misclassification rate","exact recovery","minimax lower bound"],"falsifier":"Fix the signal-to-noise ratio and increase the spikiness of the centers while measuring whether the misclassification rate stops decaying exponentially.","tokens_in":2660,"feed_emoji":"","tokens_out":719,"duration_ms":25840,"temperature":0.7,"pith_summary":"The paper establishes that one-bit clustering is possible for two-component sub-Gaussian mixture models by quantizing each sample entry to a single bit using a dithered quantizer. A variant of Lloyd's algorithm then achieves misclassification rates that decay exponentially in the signal-to-noise ratio at rates comparable to those with full-precision data, provided the cluster centers satisfy a mild non-spikiness condition. This guarantee further yields exact cluster recovery whenever the separation between centers exceeds the information-theoretic threshold for unquantized data by only a logarithmic factor. When the dimension is high, a preliminary random rotation renders the non-spikiness condition likely to hold, and matching lower bounds show the constants are sharp.","feed_headline":"One-bit Lloyd variant clusters mixtures at near full-data rates","feed_subtitle":"Exponential misclassification decay holds under non-spikiness, with exact recovery only a log factor above the unquantized threshold.","key_machinery":"Variant of Lloyd's algorithm applied to one-bit dithered quantized samples","core_discovery":"Under a mild non-spikiness condition on the cluster centers, a variant of Lloyd's algorithm applied after one-bit dithered quantization achieves a misclassification rate that decays exponentially with a signal-to-noise ratio comparable to the unquantized setting. This implies exact recovery under an explicit separation condition exceeding the optimal unquantized threshold by only a logarithmic factor. When the dimension p is sufficiently large, the non-spikiness condition can be enforced by a random rotation using a Haar distributed matrix prior to quantization, holding with high probability for p ≳ 1 in partial recovery and p ≳ log n log log n in exact recovery. A minimax lower bound establ","pith_inferences":["Dithering is essential to keep the one-bit observations informative about the cluster means.","The same quantization-plus-Lloyd pipeline may apply to other mixture estimation tasks once the non-spikiness issue is handled.","Storage or communication cost in distributed clustering can drop by roughly the original bit depth per coordinate."],"forward_implications":["Misclassification rate decays exponentially in the signal-to-noise ratio at a rate comparable to the unquantized case.","Exact recovery holds when separation exceeds the unquantized optimum by only a logarithmic factor.","Random rotation before quantization enforces non-spikiness with high probability when p is large enough.","The achieved rates match the minimax lower bound up to constants."],"fun_headline_variants":["One-bit dithered Lloyd achieves near unquantized clustering rates","Lloyd variant delivers exponential decay in one-bit mixture clustering","One-bit clustering under non-spikiness matches unquantized thresholds","Random Haar rotation enforces non-spikiness for high-dim one-bit recovery"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The cluster centers must satisfy a mild non-spikiness condition; if they are spiky the exponential decay and exact recovery may fail.","fun_headline_variants_meta":{"raw":{"variants":["One-bit dithered Lloyd achieves near unquantized clustering rates","Lloyd variant delivers exponential decay in one-bit mixture clustering","One-bit clustering under non-spikiness matches unquantized thresholds","Random Haar rotation enforces non-spikiness for high-dim one-bit recovery"]},"model":"grok-4.3","cost_usd":0.005042,"raw_usage":{"total_tokens":2408,"prompt_tokens":729,"num_sources_used":0,"completion_tokens":71,"cost_in_usd_ticks":50415500,"prompt_tokens_details":{"text_tokens":729,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1608,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":729,"tokens_out":71,"duration_ms":8210,"temperature":1.0,"reasoning_tokens":1608,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T11:49:45.630542+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Fix the signal-to-noise ratio and increase the spikiness of the centers while measuring whether the misclassification rate stops decaying exponentially.","supporting_citations":[],"review_version":1}