# Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models

arXiv: https://arxiv.org/abs/2012.07774 · HTML: https://mlsanity.com/paper/2012.07774/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

## Built on by (most cited first, 28 of 28)

- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspective](https://mlsanity.com/paper/2405.16418/) (2024)
- [Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixtures](https://mlsanity.com/paper/2504.05300/) (2025)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [What Makes A Good Fisherman? Linear Regression under Self-Selection Bias](https://mlsanity.com/paper/2205.03246/) (2022)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures](https://mlsanity.com/paper/2112.05445/) (2021)
- [A Fourier Approach to Mixture Learning](https://mlsanity.com/paper/2210.02415/) (2022)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures](https://mlsanity.com/paper/2203.15150/) (2022)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation](https://mlsanity.com/paper/2312.11769/) (2023)
- [Most Neural Networks Are Almost Learnable](https://mlsanity.com/paper/2305.16508/) (2023)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [On the robust learning mixtures of linear regressions](https://mlsanity.com/paper/2305.15317/) (2023)
- [Sample-Efficient Linear Regression with Self-Selection Bias](https://mlsanity.com/paper/2402.14229/) (2024)
- [Batch List-Decodable Linear Regression via Higher Moments](https://mlsanity.com/paper/2503.09802/) (2025)

## Abstract (arXiv)

Let V be any vector space of multivariate degree-d homogeneous polynomials with co-dimension at most k, and S be the set of points where all polynomials in V em nearly vanish. We establish a qualitatively optimal upper bound on the size of ε-covers for S, in the ℓ2-norm. Roughly speaking, we show that there exists an ε-cover for S of cardinality M = (k/ε)^Od(k1/d). Our result is constructive yielding an algorithm to compute such an ε-cover that runs in time poly(M). Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models with hidden variables. These include density and parameter estimation for k-mixtures of spherical Gaussians (with known common covariance), PAC learning one-hidden-layer ReLU networks with k hidden units (under the Gaussian distribution), density and parameter estimation for k-mixtures of linear regressions (with Gaussian covariates), and parameter estimation for k-mixtures of hyperplanes. Our algorithms run in time em quasi-polynomial in the parameter k. Previous algorithms for these problems had running times exponential in kOmega(1). At a high-level our algorithms for all these learning problems work as follows: By computing the low-degree moments of the hidden parameters, we are able to find a vector space of polynomials that nearly vanish on the unknown parameters. Our structural result allows us to compute a quasi-polynomial sized cover for the set of hidden parameters, which we exploit in our learning algorithms.