Research map / Learning theory and algorithms / Sample complexity
Learning multivariate Gaussians with imperfect advice
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that given a mean and covariance advice, multivariate Gaussian PAC learning in TV can use fewer samples than the advice-free O~(d^2/eps^2) bound when the advice is accurate, via tolerant testing plus l1-constrained LASSO/SDP estimators, with matching-style lower bounds.
Problem
Learning d-dimensional Gaussians N(mu, Sigma) to total variation eps from samples when imperfect advice (mean and covariance estimates) is available; the sample complexity should decrease as advice quality improves.
Approach
Use sublinear tolerant property testers to certify the advice quality measured in entrywise l1 norm (of the mean, or of the whitened covariance deviation), then solve an l1-constrained least-squares (LASSO) or SDP estimation problem, with partitioning over blocks of coordinates to convert l2/Frobenius tests into l1 estimates.
Key results
- For mean advice with ||mu - mu_tilde||_1 small, TestAndOptimizeMean uses O~(d^{1-eta}/eps^2) samples versus O~(d/eps^2) without advice.
- For covariance advice, TestAndOptimizeCovariance uses O~(d^{2-eta}/eps^2) samples when the whitened deviation l1 norm is below eps d^{1-eta}, versus O~(d^2/eps^2) advice-free.
- Lower bounds show Omega~(min{d, Delta^2/eps^2}/eps^2) for mean and Omega~(min{d^2, Delta^2/eps^2}/eps^2) for covariance, matching the upper bounds up to log factors when Delta is known.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| provide accurate mean advice with \|\bm{\mu} - \widetilde{\bm{\mu}}\|_1 < \varepsilon d^{(1 - 5 \eta)/2} | TestAndOptimizeMean · Isotropic Gaussian mean learning | sample complexity: \widetilde{\mathcal{O}}(\frac{d^{1-\eta}}{\varepsilon^2}) samples | Helped |
| provide accurate covariance advice with \| \mathrm{vec}(\widetilde{\bm{\Sigma}}^{-1/2} \bm{\Sigma} \widetilde{\bm{\Sigma}}^{-1/2} - \mathbf{I}_d) \|_1 < \varepsilon d^{1-\eta} | TestAndOptimizeCovariance · General Gaussian learning | sample complexity: \widetilde{\mathcal{O}}(\frac{d^{2 - \eta}}{\varepsilon^2}) samples | Helped |
| provide low-quality mean advice bounded by \|\bm{\mu} - \widetilde{\bm{\mu}}\|_1 \leq \Delta | Gaussian mean learning · Isotropic Gaussian mean learning | sample complexity: \Omega\left(\frac{\min\{d, \Delta^2/\varepsilon^2\}}{\varepsilon^2 \log (1/\varepsilon)}\right) | Mixed |
| provide low-quality covariance advice bounded by normalized entrywise \ell_1 error \leq \Delta | Gaussian covariance learning · General Gaussian learning | sample complexity: \Omega \left( \frac{\min\{d^2, \Delta^2/\varepsilon^2\}}{\varepsilon^2 \log(1/\varepsilon)} \right) | Mixed |
Limitations
- Improvement only applies when advice error in l1 norm is small (below eps*sqrt(d) for mean, eps*d for covariance).
- Theoretical paper; no experiments reported in the provided text beyond a planned section.
Experimental setup
Metrics: sample complexity total variation distance
Baselines: empirical mean and empirical covariance (advice-free)
Builds on: algorithms with predictions tolerant testing Scheffé tournament
Closest papers by meaning
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.86)
- Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions (NeurIPS 2021 · similarity 0.86)
- Sample-Efficient Private Learning of Mixtures of Gaussians (NeurIPS 2024 · similarity 0.85)
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.84)
- Product Distribution Learning with Imperfect Advice (NeurIPS 2025 · similarity 0.84)
- The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.