Pith. sign in

REVIEW 2 major objections 2 minor 56 references

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

T0 review · 2 major / 2 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An algorithm recovers any high-dimensional Gaussian truncated by an unknown halfspace using Õ(d²/ε²) samples to total variation error ε.

desk verdict 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. read the letter →

arxiv 2606.27298 v1 pith:J2GW7G3G submitted 2026-06-25 cs.DS cs.LGmath.STstat.MLstat.TH

Haitong Liu , Deepak Narayanan Sridharan , David Steurer , Manuel Wiedmer This is my paper · ORCID
classification cs.DScs.LGmath.STstat.MLstat.TH
keywords gaussianlearninghalfspacetruncationsamplecomplexitytotalvariationdistancemomentmethodshigh-dimensionalstatisticsparameterrecoveryalgorithmic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

The relative truncation parameter obtained from low-degree moments of the truncated distribution, which uniquely pins down the original Gaussian parameters for direct recovery.

What would settle it

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 ε.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

The low-degree moments of the truncated Gaussian can be rewritten so that one relative truncation parameter uniquely identifies the original mean and covariance.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

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.

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 (2)
  1. [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.
  2. [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.
minor comments (2)
  1. [Abstract] 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.
  2. [Notation section] Notation section: define the relative truncation parameter and its relation to the halfspace before any moment equations are stated, to avoid forward references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: [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.

    Authors: 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: yes

  2. Referee: [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.

    Authors: 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: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper's central contribution is a novel reinterpretation of low-degree moments of the truncated Gaussian via a relative truncation parameter that uniquely determines the untruncated parameters, enabling direct recovery without projected SGD. This is presented as an independent mathematical insight rather than a self-definition, fitted input renamed as prediction, or reduction to prior self-citations. The abstract and description cite external prior work (Lee et al. FOCS'24) for the baseline polynomial-time result and claim optimality matching the untruncated case, with no equations or steps shown to collapse by construction to the inputs. The derivation chain is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the relative truncation parameter appears to be a derived quantity rather than an added free parameter.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity." pith.science (2026). https://pith.science/paper/J2GW7G3G

@misc{pith2026260627298,
  author       = {Pith},
  title        = {Pith review of: Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J2GW7G3G}},
  note         = {Machine review of arXiv:2606.27298}
}
abstract

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 1 canonical work pages

  1. [1]

    and Mehrotra, Anay and Zampetakis, Manolis , TITLE =

    Lee, Jane H. and Mehrotra, Anay and Zampetakis, Manolis , TITLE =. 2024. 2024 , ISBN =

    2024

  2. [2]

    2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Agnostic estimation of mean and covariance , author=. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2016 , organization=

    2016

  3. [3]

    Course notes: http://www.sumofsquares.org/public/index.html , volume=

    Proofs, beliefs, and algorithms through the lens of sum-of-squares , author=. Course notes: http://www.sumofsquares.org/public/index.html , volume=

  4. [4]

    Diakonikolas, Ilias and Kamath, Gautam and Kane, Daniel and Li, Jerry and Moitra, Ankur and Stewart, Alistair , TITLE =. SIAM J. Comput. , FJOURNAL =. 2019 , NUMBER =

    2019

  5. [5]

    and Mehrotra, Anay and Zampetakis, Manolis , title =

    Lee, Jane H. and Mehrotra, Anay and Zampetakis, Manolis , title =. 2026 , isbn =. doi:10.1145/3798129.3800725 , booktitle =

    work page doi:10.1145/3798129.3800725 2026

  6. [6]

    Breakthroughs in statistics: Methodology and distribution , pages=

    Robust estimation of a location parameter , author=. Breakthroughs in statistics: Methodology and distribution , pages=. 1992 , publisher=

    1992

  7. [7]

    Journal of the Royal Statistical Society Series B: Statistical Methodology , volume=

    Estimation of generalized linear latent variable models , author=. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume=. 2004 , publisher=

    2004

  8. [8]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    Detecting low-degree truncation , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

Show all 56 references
  1. [9]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Testing convex truncation , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  2. [10]

    Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , pages =

    Gaussian Mean Testing under Truncation , author =. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , pages =. 2025 , editor =

    2025

  3. [11]

    Private Statistical Estimation via Truncation , volume =

    Zampetakis, Manolis and Zhou, Felix , booktitle =. Private Statistical Estimation via Truncation , volume =

  4. [12]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Clustering mixtures with almost optimal separation in polynomial time , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  5. [13]

    Conference on Learning Theory , pages=

    Blind signal separation in the presence of Gaussian noise , author=. Conference on Learning Theory , pages=. 2013 , organization=

    2013

  6. [14]

    Conference on Learning Theory , pages=

    Uniqueness of tensor decompositions with applications to polynomial identifiability , author=. Conference on Learning Theory , pages=. 2014 , organization=

    2014

  7. [15]

    2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=

    Settling the polynomial learnability of mixtures of gaussians , author=. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=. 2010 , organization=

    2010

  8. [16]

    Philosophical Transactions of the Royal Society of London

    Contributions to the mathematical theory of evolution , author=. Philosophical Transactions of the Royal Society of London. A , volume=. 1894 , publisher=

  9. [17]

    2016 , month = dec, note =

    van Handel, Ramon , title =. 2016 , month = dec, note =

    2016

  10. [18]

    2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=

    Learning geometric concepts via Gaussian surface area , author=. 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=. 2008 , organization=

    2008

  11. [19]

    The Thirty Seventh Annual Conference on Learning Theory , pages=

    Statistical query lower bounds for learning truncated gaussians , author=. The Thirty Seventh Annual Conference on Learning Theory , pages=. 2024 , organization=

    2024

  12. [20]

    Kontonis, Vasilis and Tzamos, Christos and Zampetakis, Manolis , TITLE =. 2019. 2019 , ISBN =

    2019

  13. [21]

    Gasull, Armengol and Utzet, Frederic , TITLE =. J. Math. Anal. Appl. , FJOURNAL =. 2014 , NUMBER =

    2014

  14. [22]

    Kuchibhotla, Arun Kumar and Chakrabortty, Abhishek , TITLE =. Inf. Inference , FJOURNAL =. 2022 , NUMBER =

    2022

  15. [23]

    Sampford, M. R. , TITLE =. Ann. Math. Statistics , FJOURNAL =. 1953 , PAGES =

    1953

  16. [24]

    Birnbaum, Z. W. , TITLE =. Ann. Math. Statistics , FJOURNAL =. 1942 , PAGES =

    1942

  17. [25]

    2018 , publisher=

    High-dimensional probability: An introduction with applications in data science , author=. 2018 , publisher=

    2018

  18. [26]

    Shah, S. M. and Jaiswal, M. C. , TITLE =. Ann. Inst. Statist. Math. , FJOURNAL =. 1966 , PAGES =

    1966

  19. [27]

    Barreto, Mathias and Marchal, Olivier and Arbel, Julyan , TITLE =. Statist. Probab. Lett. , FJOURNAL =. 2026 , PAGES =

    2026

  20. [28]

    Proceedings of the 2024

    Bhardwaj, Abhinav and Vu, Van , TITLE =. Proceedings of the 2024. 2024 , ISBN =

    2024

  21. [29]

    Tony and Zhang, Cun-Hui and Zhou, Harrison H

    Cai, T. Tony and Zhang, Cun-Hui and Zhou, Harrison H. , TITLE =. Ann. Statist. , FJOURNAL =. 2010 , NUMBER =

    2010

  22. [30]

    and Lim, Lek-Heng , TITLE =

    Hillar, Christopher J. and Lim, Lek-Heng , TITLE =. J. ACM , FJOURNAL =. 2013 , NUMBER =

    2013

  23. [31]

    and Steinhardt, Jacob and Steurer, David , TITLE =

    Kothari, Pravesh K. and Steinhardt, Jacob and Steurer, David , TITLE =. S. 2018 , ISBN =

    2018

  24. [32]

    and Pensia, Ankit and Tiegel, Stefan , TITLE =

    Diakonikolas, Ilias and Hopkins, Samuel B. and Pensia, Ankit and Tiegel, Stefan , TITLE =. S. 2025 , ISBN =

    2025

  25. [33]

    Banach, Stefan , journal=

  26. [34]

    Daskalakis, Constantinos and Gouleakis, Themis and Tzamos, Christos and Zampetakis, Manolis , TITLE =. 59th. 2018 , ISBN =

    2018

  27. [35]

    Boyd, A. V. , TITLE =. Rep. Statist. Appl. Res. Un. Japan. Sci. Engrs. , FJOURNAL =. 1959 , PAGES =

    1959

  28. [36]

    Friedland, Shmuel , TITLE =. Front. Math. China , FJOURNAL =. 2013 , NUMBER =

    2013

  29. [37]

    Davis, Chandler and Kahan, W. M. , TITLE =. SIAM J. Numer. Anal. , FJOURNAL =. 1970 , PAGES =

    1970

  30. [38]

    Chen, Bilian and He, Simai and Li, Zhening and Zhang, Shuzhong , TITLE =. SIAM J. Optim. , FJOURNAL =. 2012 , NUMBER =

    2012

  31. [39]

    Histoire de l'Acad., Roy

    Bernoulli, Daniel , TITLE =. Histoire de l'Acad., Roy. Sci. (Paris) avec Mem , YEAR =

  32. [40]

    Proceedings of the Royal Society of London , volume =

    Galton, Francis , title =. Proceedings of the Royal Society of London , volume =. 1898 , month =

  33. [41]

    Biometrika , volume =

    Karl Pearson , title =. Biometrika , volume =. 1902 , publisher =

    1902

  34. [42]

    Biometrika , volume =

    Karl Pearson and Alice Lee , title =. Biometrika , volume =. 1908 , publisher =

    1908

  35. [43]

    Biometrika , volume =

    Alice Lee , title =. Biometrika , volume =. 1914 , publisher =

    1914

  36. [44]

    Introduction to British A.A.S

    Ronald Aylmer Fisher , title =. Introduction to British A.A.S. Math. Tables , volume =

  37. [45]

    Bliss, Chester Ittner and Stevens, W. L. , title =. Annals of Applied Biology , volume =

  38. [46]

    Clifford , TITLE =

    Cohen, A. Clifford , TITLE =. 1991 , PAGES =

    1991

  39. [47]

    Proceedings of the 2025

    Alman, Josh and Duan, Ran and Vassilevska Williams, Virginia and Xu, Yinzhan and Xu, Zixuan and Zhou, Renfei , TITLE =. Proceedings of the 2025. 2025 , ISBN =

    2025

  40. [48]

    The Thirteenth International Conference on Learning Representations , YEAR =

    Oracle efficient truncated statistics , AUTHOR =. The Thirteenth International Conference on Learning Representations , YEAR =

  41. [49]

    2023 , publisher=

    Algorithmic high-dimensional robust statistics , author=. 2023 , publisher=

    2023

  42. [50]

    Wainwright, Martin J. , year=. High-Dimensional Statistics: A Non-Asymptotic Viewpoint , publisher=

  43. [51]

    (Lecture Notes), Cambridge, MA, USA: MIT Open-CourseWare , year=

    18.S997: High dimensional statistics , author=. (Lecture Notes), Cambridge, MA, USA: MIT Open-CourseWare , year=

  44. [52]

    2023 , pages=

    Arbas, Jamil and Ashtiani, Hassan and Liaw, Christopher , title =. 2023 , pages=

    2023

  45. [53]

    1997 , PAGES =

    Bhatia, Rajendra , TITLE =. 1997 , PAGES =

    1997

  46. [54]

    Weyl, Hermann , TITLE =. Math. Ann. , FJOURNAL =. 1912 , NUMBER =

    1912

  47. [55]

    explanatory

    Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multi-modal factor analysis , author=. UCLA working papers in phonetics , volume=. 1970 , publisher=

    1970

  48. [56]

    Leurgans, S. E. and Ross, R. T. and Abel, R. B. , TITLE =. SIAM J. Matrix Anal. Appl. , FJOURNAL =. 1993 , NUMBER =

    1993

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.