mlsanityData to 7 Oct 2026

Product distribution learning with imperfect advice

arXiv 2511.10366 ↗First posted 13 Nov 2025cs.LGcited by 1

Not on the map. Why?

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.

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

Builds on

20 of 32 references.

References · 20

  1. 2017The Case for Learned Index Structurescited by 188
  2. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  3. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  4. 2024Improving Online Algorithms via ML Predictionscited by 65
  5. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  6. 2021Faster Matchings via Learned Dualscited by 56
  7. 2019Online Computation with Untrusted Advicecited by 42
  8. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  9. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  10. 2016Testing Bayesian Networkscited by 23
  11. 2022Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Locationcited by 19
  12. 2021A Novel Prediction Setup for Online Speed-Scalingcited by 17
8 more
  1. 2022A Universal Error Measure for Input Predictions Applied to Online Graph Problemscited by 14
  2. 2024Online bipartite matching with imperfect advicecited by 13
  3. 2016Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testingcited by 11
  4. 2023Active causal structure learning with advicecited by 10
  5. 2022Improved Price of Anarchy via Predictionscited by 9
  6. 2022Learning-Augmented Algorithms for Online TSP on the Linecited by 8
  7. 2025Learning-Augmented Online Bipartite Fractional Matchingcited by 8
  8. 2024Learning multivariate Gaussians with imperfect advicecited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Online Allocation with Unknown Shared Supplycited by 0