# Learning multivariate Gaussians with imperfect advice

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 19 Nov 2024.

## Builds on (most cited first, 24 of 24)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Testable Learning with Distribution Shift](https://mlsanity.com/paper/2311.15142/) (2023)
- [Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location](https://mlsanity.com/paper/2204.01120/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [Improved Price of Anarchy via Predictions](https://mlsanity.com/paper/2205.04252/) (2022)
- [Learning-Augmented Algorithms for Online TSP on the Line](https://mlsanity.com/paper/2206.00655/) (2022)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)

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

- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget](https://mlsanity.com/paper/2509.00135/) (2025)
- [Product distribution learning with imperfect advice](https://mlsanity.com/paper/2511.10366/) (2025)
- [Online Allocation with Unknown Shared Supply](https://mlsanity.com/paper/2605.07080/) (2026)

## Abstract (arXiv)

We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is provided as potentially inaccurate advice on the true, unknown distribution. Our objective is to develop learning algorithms whose sample complexity decreases as the quality of the advice improves, thereby surpassing standard learning lower bounds when the advice is sufficiently accurate. Specifically, we demonstrate that this outcome is achievable for the problem of learning a multivariate Gaussian distribution N(boldsymbolμ, boldsymbolSigma) in the PAC learning setting. Classically, in the advice-free setting, tildeTheta(d2/varepsilon2) samples are sufficient and worst case necessary to learn d-dimensional Gaussians up to TV distance varepsilon with constant probability. When we are additionally given a parameter tildeboldsymbolSigma as advice, we show that tildeO(d2-β/varepsilon2) samples suffices whenever | tildeboldsymbolSigma-1/2 boldsymbolSigma tildeboldsymbolSigma-1/2 - boldsymbolId |1 ≤ varepsilon d1-β (where |·|1 denotes the entrywise ℓ1 norm) for any β > 0, yielding a polynomial improvement over the advice-free setting.