mlsanityData to 14 Oct 2026

Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models

arXiv 2411.15669 ↗First posted 23 Nov 2024cs.DS cs.LG math.STcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the task of learning latent-variable models. A common algorithmic technique for this task is the method of moments. Unfortunately, moment-based approaches are hampered by the fact that the moment tensors of super-constant degree cannot even be written down in polynomial time. Motivated by such learning applications, we develop a general efficient algorithm for em implicit moment tensor computation. Our framework generalizes the work of~citeLL21-opt which developed an efficient algorithm for the specific moment tensors that arise in clustering mixtures of spherical Gaussians. By leveraging our implicit moment estimation algorithm, we obtain the first poly(d, k)-time learning algorithms for the following models. * bf Mixtures of Linear Regressions We give a poly(d, k, 1/ε)-time algorithm for this task, where ε is the desired error. * bf Mixtures of Spherical Gaussians For density estimation, we give a poly(d, k, 1/ε)-time learning algorithm, where ε is the desired total variation error, under the condition that the means lie in a ball of radius O(√log k). For parameter estimation, we give a poly(d, k, 1/ε)-time algorithm under the em optimal mean separation of Omega(log1/2(k/ε)). * bf Positive Linear Combinations of Non-Linear Activations We give a general algorithm for this task with complexity poly(d, k) g(ε), where ε is the desired error and the function g depends on the Hermite concentration of the target class of functions. Specifically, for positive linear combinations of ReLU activations, our algorithm has complexity poly(d, k) 2poly(1/ε).

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 38 of its 72 references that are in the map. First posted on arXiv 23 Nov 2024.

Builds on

38 of 72 references.

References · 38

  1. 2020Implicit Neural Representations with Periodic Activation Functionscited by 2,238
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  5. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  6. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  7. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  8. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  9. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  10. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  11. 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
  12. 2020Continuous LWEcited by 37
26 more
  1. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  2. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  3. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  4. 2014Tight bounds for learning a mixture of two gaussianscited by 29
  5. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  6. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  7. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  8. 2019EM Converges for a Mixture of Many Linear Regressionscited by 27
  9. 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
  10. 2019Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Momentscited by 26
  11. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  12. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  13. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  14. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  15. 2017On the Complexity of Learning Neural Networkscited by 18
  16. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  17. 2015ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Timecited by 16
  18. 2020Robust Learning of Mixtures of Gaussianscited by 15
  19. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  20. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  21. 2024BiPer: Binary Neural Networks using a Periodic Functioncited by 9
  22. 2020Logic Synthesis Meets Machine Learning: Trading Exactness for Generalizationcited by 8
  23. 2023A faster and simpler algorithm for learning shallow networkscited by 7
  24. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  25. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  26. 2024On the Hardness of Learning One Hidden Layer Neural Networkscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 2.

6 papers.

  1. 2025Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contaminationcited by 6
  2. 2025Batch List-Decodable Linear Regression via Higher Momentscited by 0
  3. 2025On Learning Parallel Pancakes with Mostly Uniform Weightscited by 0
  4. 2025Optimal Bias-variance Tradeoff in Matrix and Tensor Estimationcited by 0
  5. 2026Precise sample covariance spectral norm error -- an RDT viewcited by 0
  6. 2026Is √d Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?cited by 0