# Product distribution learning with imperfect advice

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 32 references that are in the map.
- First posted on arXiv 13 Nov 2025.

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

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [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)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [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)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [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)
- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Learning multivariate Gaussians with imperfect advice](https://mlsanity.com/paper/2411.12700/) (2024)

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

- [Online Allocation with Unknown Shared Supply](https://mlsanity.com/paper/2605.07080/) (2026)

## Abstract (arXiv)

Given i.i.d.~samples from an unknown distribution P, the goal of distribution learning is to recover the parameters of a distribution that is close to P. When P belongs to the class of product distributions on the Boolean hypercube 0,1d, it is known that Omega(d/varepsilon2) samples are necessary to learn P within total variation (TV) distance varepsilon. We revisit this problem when the learner is also given as advice the parameters of a product distribution Q. We show that there is an efficient algorithm to learn P within TV distance varepsilon that has sample complexity tildeO(d1-η/varepsilon2), if |p - q|1 < varepsilon d0.5 - Omega(η). Here, p and q are the mean vectors of P and Q respectively, and no bound on |p - q|1 is known to the algorithm a priori.