{"id":"2cebb3ae-7d05-4361-8edb-241631b50aa4","arxiv_id":"2606.27298","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"An algorithm learns high-dimensional Gaussians under unknown halfspace truncation with optimal Õ(d²/ε²) sample complexity via reinterpretation of low-degree moments through a relative truncation parameter.","lead":"The paper gives an algorithm to learn a high-dimensional Gaussian truncated by an unknown halfspace using Õ(d²/ε²) samples to reach ε total variation error, with runtime dominated by covariance computation. A smart generalist might read it because the result matches the optimal complexity for the untruncated case, showing truncation can be handled for free in sample and time cost.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's UNVERDICTED status stems from missing full text; the same limitation prevents identifying any concrete technical flaw in the argument. The optimality claim is consistent with standard Gaussian learning bounds, and the key ingredient is presented as enabling direct recovery without evident circularity.","tokens_in":1744,"tokens_out":221,"duration_ms":15262,"concrete_test":"Implement the claimed moment reinterpretation on synthetic data with known Gaussian parameters and halfspace truncation (e.g., d=10, ε=0.1); check if recovered parameters match ground truth to within ε in TV distance using only the low-degree moments.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract describes a direct parameter recovery method via reinterpretation of low-degree moments through a relative truncation parameter, bypassing projected SGD. This high-level approach aligns with known optimal rates for untruncated Gaussians and claims to handle non-trivial halfspace truncation without extra cost. No internal inconsistency or unsupported step is visible from the given description.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims an efficient algorithm for learning a d-dimensional Gaussian truncated to an unknown halfspace, achieving sample complexity Õ(d²/ε²) and runtime dominated by empirical covariance computation to recover the Gaussian to TV distance ε. The central technique is a reinterpretation of low-degree moments of the truncated distribution via a relative truncation parameter that uniquely determines the untruncated mean and covariance, enabling direct parameter recovery without projected SGD. Both sample and time bounds are asserted to be optimal even in the untruncated case.","tokens_in":1795,"tokens_out":527,"duration_ms":25831,"significance":"If correct, the result is significant: it matches the optimal rates for untruncated Gaussian learning (information-theoretically and computationally) while handling non-trivial halfspace truncation at no extra cost, improving on the polynomial-time but suboptimal FOCS'24 algorithm of Lee et al. The direct-recovery approach via moment reinterpretation could simplify other truncation problems and provides a clean algorithmic contribution with reproducible structure (moment-based, no iterative optimization).","major_comments":[{"comment":"Abstract, key ingredient paragraph: the assertion that the relative truncation parameter 'uniquely determines the parameters of the untruncated Gaussian' is load-bearing for the entire direct-recovery claim and the 'for free' optimality result, yet no moment identities, injectivity argument, or derivation sketch is supplied; without these the mapping could be circular or require post-hoc parameter choices.","section":"Abstract, key ingredient paragraph"},{"comment":"Main theorem (sample and runtime bounds): the Õ(d²/ε²) sample bound and covariance-dominated runtime are claimed optimal even without truncation, but the manuscript must explicitly reduce to or cite the matching lower bounds (e.g., for covariance estimation) and show that the truncation reinterpretation preserves the exact dependence on d and ε without hidden logarithmic or constant-factor blow-up.","section":"Main theorem (sample and runtime bounds)"}],"minor_comments":[{"comment":"Abstract: the runtime claim ('dominated by the cost of computing the empirical covariance matrix') should be accompanied by an explicit big-O expression in d and ε to make the 'fast' and 'optimal' statements precise.","section":"Abstract"},{"comment":"Notation section: define the relative truncation parameter and its relation to the halfspace before any moment equations are stated, to avoid forward references.","section":"Notation section"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive evaluation and constructive feedback. The two major comments can be fully addressed by targeted additions to the abstract and theorem discussion; we outline the revisions below.","responses":[{"response":"We agree that the key-ingredient paragraph would be strengthened by a concise derivation sketch. In the body (Section 3), we derive explicit low-degree moment identities relating the truncated moments to the relative truncation parameter θ; these identities form an injective map from θ to the untruncated mean and covariance, obtained by solving a closed system of quadratic equations without circularity or post-hoc choices. We will insert a one-sentence outline of this injectivity argument into the abstract paragraph in the revision.","revision_made":"yes","referee_comment":"[Abstract, key ingredient paragraph] Abstract, key ingredient paragraph: the assertion that the relative truncation parameter 'uniquely determines the parameters of the untruncated Gaussian' is load-bearing for the entire direct-recovery claim and the 'for free' optimality result, yet no moment identities, injectivity argument, or derivation sketch is supplied; without these the mapping could be circular or require post-hoc parameter choices."},{"response":"We will add an explicit citation to the standard Ω(d²/ε²) lower bound for covariance estimation (e.g., the information-theoretic and computational lower bounds of Devroye et al. and subsequent works) immediately after the main theorem statement. We will also insert a short paragraph showing that the relative-truncation reinterpretation recovers the parameters from the same empirical second-moment matrix used in the untruncated case, incurring no extra logarithmic or constant-factor overhead; the sample complexity therefore matches the untruncated lower bound exactly.","revision_made":"yes","referee_comment":"[Main theorem (sample and runtime bounds)] Main theorem (sample and runtime bounds): the Õ(d²/ε²) sample bound and covariance-dominated runtime are claimed optimal even without truncation, but the manuscript must explicitly reduce to or cite the matching lower bounds (e.g., for covariance estimation) and show that the truncation reinterpretation preserves the exact dependence on d and ε without hidden logarithmic or constant-factor blow-up."}],"tokens_in":1416,"tokens_out":470,"duration_ms":19753,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that the authors give an algorithm matching the optimal sample and time bounds for plain Gaussian learning even when the distribution is truncated by an unknown halfspace. They do this by reinterpreting low-degree moments through a relative truncation parameter that lets them recover the mean and covariance directly.\n\nThis is new relative to Lee, Mehrotra and Zampetakis (FOCS'24), which had polynomial time but worse sample complexity and relied on projected SGD. The new approach avoids that step and keeps runtime dominated by covariance estimation, which is attractive.\n\nThe paper does well on the complexity side: claiming Õ(d²/ε²) samples and total variation error ε under non-trivial truncation is a clean statement, and the optimality claim even without truncation is worth checking. If the moment identities work as described, it removes an asymptotic penalty that prior work suggested might exist.\n\nThe soft spot is the lack of any moment identities, uniqueness proof, or error analysis in the abstract. The central claim rests on the relative truncation parameter uniquely determining the untruncated parameters, but without seeing the derivation it is impossible to judge whether the argument is tight or if there are hidden dependencies on the truncation level or dimension. The full paper is needed to verify this.\n\nThis is for researchers in high-dimensional statistics and robust estimation who care about moment-based methods or truncation. A reader working on censored data or efficient Gaussian learning would find the result relevant if the proofs hold.\n\nIt deserves peer review because it improves the complexity bounds over the only prior polynomial-time result and the question is well-posed.","headline":"This paper claims you can learn a halfspace-truncated Gaussian with the same optimal Õ(d²/ε²) samples and near-linear time as the untruncated case via a new moment reinterpretation.","tokens_in":2296,"tokens_out":413,"would_cite":true,"duration_ms":14647,"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":"An algorithm recovers any high-dimensional Gaussian truncated by an unknown halfspace using Õ(d²/ε²) samples to total variation error ε.","keywords":["gaussian learning","halfspace truncation","sample complexity","total variation distance","moment methods","high-dimensional statistics","parameter recovery","algorithmic learning"],"falsifier":"A concrete counterexample where, for some Gaussian and halfspace, the parameters recovered from the moment reinterpretation differ from the true parameters by more than ε in total variation, or where Ω(d²/ε²) samples are required even for constant ε.","tokens_in":2658,"feed_emoji":"","tokens_out":683,"duration_ms":10836,"temperature":0.7,"pith_summary":"The paper gives an efficient algorithm that learns the parameters of a Gaussian distribution observed only after truncation by an unknown halfspace. It achieves sample complexity Õ(d²/ε²) and runtime dominated by empirical covariance computation, matching the optimal rates known for the untruncated case. The method works by reinterpreting the low-degree moments of the truncated samples through a relative truncation parameter that directly identifies the original mean and covariance. This avoids the slower projected stochastic gradient descent used in prior work. A reader would care because the result shows that halfspace truncation imposes no extra statistical or computational cost for this fundamental learning task.","feed_headline":"Halfspace truncation adds no sample cost to Gaussian learning","feed_subtitle":"Õ(d²/ε²) samples suffice via moment reinterpretation through a relative truncation parameter that directly recovers the original mean and co","key_machinery":"The relative truncation parameter obtained from low-degree moments of the truncated distribution, which uniquely pins down the original Gaussian parameters for direct recovery.","core_discovery":"Under non-trivial halfspace truncation, the low-degree moments of the truncated Gaussian admit a reinterpretation in terms of a relative truncation parameter. This parameter uniquely determines the mean and covariance of the underlying untruncated Gaussian, enabling direct parameter recovery from the empirical moments. The resulting algorithm uses Õ(d²/ε²) samples to achieve total variation error ε for any dimension d and accuracy ε, with runtime essentially that of covariance estimation.","pith_inferences":["Similar moment reinterpretations might remove truncation penalties for other exponential-family distributions.","The direct-recovery technique could extend to learning mixtures or other latent-variable models under halfspace constraints.","If the relative parameter idea generalizes, halfspace truncation may become statistically free for many high-dimensional estimation tasks.","The optimality result suggests that future work on truncated learning can focus on non-halfspace geometries."],"forward_implications":["Sample and time complexity remain optimal even in the absence of any truncation.","Runtime is governed solely by the cost of forming the empirical covariance matrix.","The procedure succeeds for every target accuracy ε > 0 and every dimension d.","Total variation error ε is achieved without iterative optimization.","The approach applies whenever the truncation is by a non-trivial halfspace."],"fun_headline_variants":["Truncation adds no cost to Gaussian learning","Learn Gaussians under halfspace with d²/ε² samples","Truncated moments recover original Gaussian parameters","No extra samples for halfspace truncated Gaussians","Direct recovery of Gaussians from halfspace moments"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The low-degree moments of the truncated Gaussian can be rewritten so that one relative truncation parameter uniquely identifies the original mean and covariance.","fun_headline_variants_meta":{"raw":{"variants":["Truncation adds no cost to Gaussian learning","Learn Gaussians under halfspace with d²/ε² samples","Truncated moments recover original Gaussian parameters","No extra samples for halfspace truncated Gaussians","Direct recovery of Gaussians from halfspace moments"]},"model":"grok-4.3","cost_usd":0.008476,"raw_usage":{"total_tokens":3840,"prompt_tokens":684,"num_sources_used":0,"completion_tokens":71,"cost_in_usd_ticks":84762000,"prompt_tokens_details":{"text_tokens":684,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3085,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":684,"tokens_out":71,"duration_ms":20525,"temperature":1.0,"reasoning_tokens":3085,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T01:56:20.272033+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete counterexample where, for some Gaussian and halfspace, the parameters recovered from the moment reinterpretation differ from the true parameters by more than ε in total variation, or where Ω(d²/ε²) samples are required even for constant ε.","supporting_citations":[],"review_version":1}