mlsanityData to 14 Oct 2026

Non-Gaussian Component Analysis via Lattice Basis Reduction

arXiv 2112.09104 ↗First posted 16 Dec 2021cs.DS cs.LG math.STcited by 14

Not on the map. Why?

Abstract (arXiv)

Non-Gaussian Component Analysis (NGCA) is the following distribution learning problem: Given i.i.d. samples from a distribution on ℝd that is non-gaussian in a hidden direction v and an independent standard Gaussian in the orthogonal directions, the goal is to approximate the hidden direction v. Prior work citeDKS17-sq provided formal evidence for the existence of an information-computation tradeoff for NGCA under appropriate moment-matching conditions on the univariate non-gaussian distribution A. The latter result does not apply when the distribution A is discrete. A natural question is whether information-computation tradeoffs persist in this setting. In this paper, we answer this question in the negative by obtaining a sample and computationally efficient algorithm for NGCA in the regime that A is discrete or nearly discrete, in a well-defined technical sense. The key tool leveraged in our algorithm is the LLL method citeLLL82 for lattice basis reduction.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 18 of its 34 references that are in the map. First posted on arXiv 16 Dec 2021.

Builds on

18 of 34 references.

References · 18

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  2. 2018Adversarial examples from computational constraintscited by 80
  3. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  4. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  5. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  6. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  7. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 51
  8. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  9. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  10. 2020Continuous LWEcited by 37
  11. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  12. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
6 more
  1. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  2. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  3. 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
  4. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  5. 2017Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methodscited by 9
  6. 2018Non-Gaussian Component Analysis using Entropy Methodscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 3; 2024: 5; 2025: 2; 2026: 1.

14 papers.

Sort:

By area:

  1. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  2. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  3. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  4. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  5. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  6. 2023Precise Error Rates for Computationally Efficient Testingcited by 4
  7. 2024Computational-Statistical Gaps for Improper Learning in Sparse Linear Regressioncited by 4
  8. 2023SQ Lower Bounds for Random Sparse Planted Vector Problemcited by 3
  9. 2024Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testingcited by 3
  10. 2024Cryptographic Hardness of Score Estimationcited by 3
  11. 2023Sparse PCA Beyond Covariance Thresholdingcited by 2
  12. 2026Low-Degree Method Fails to Predict Robust Subspace Recoverycited by 2
2 more
  1. 2025Provably Extracting the Features from a General Superpositioncited by 1
  2. 2025A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomialscited by 0