Research map / Learning theory and algorithms / Sample complexity
Product Distribution Learning 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 learning a balanced product distribution on the hypercube with advice mean vector q can use sublinear-in-d samples when ||p-q||_1 is small, via a tolerant mean tester, an l1-distance approximator, and constrained least squares.
Problem
Learning product distributions on {0,1}^d in total variation distance needs Omega(d/eps^2) samples; the question is whether advice mean vector q (with unknown quality) can reduce sample complexity.
Approach
Approximate ||p-q||_1 with a block-wise tolerant identity tester using about sqrt(d)/eps^2 samples, then run a least-squares estimate constrained to an l1 ball around q; the sample cost scales with ||p-q||_1^2, giving sublinear complexity when the advice is accurate and falling back to empirical mean otherwise.
Key results
- Sample complexity O~(d^{1-eta}/eps^2) when ||p-q||_1 < eps d^{0.5-Omega(eta)} for balanced product distributions, without knowing ||p-q||_1 a priori.
- Lower bound: without balancedness, sublinear sample complexity is impossible even with ||p-q||_1 = O(1).
- Lower bound: Omega(min{||p-q||_1^2/eps^4, d/eps^2}) samples needed for balanced distributions with advice.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an advice mean vector close to the true mean | TestAndOptimizeMean for balanced product distributions · Product distributions on {0,1}^d | sample complexity: \tilde{O}(d^{1-\eta}/\varepsilon^2) when advice distance is sufficiently small, versus \Theta(d/\varepsilon^2) without a | Helped |
| Allow mean-vector entries to be O(1/d), without balancedness | Product-distribution learning with advice distance O(ε) · Unbalanced product distributions on {0,1}^d | sample complexity: \widetilde{\Omega}\left(\frac{d}{\varepsilon}\right) | Hurt |
| Use advice with distance at least ε√d from the true mean | Product-distribution learning with advice · 1/4-balanced product distributions on {0,1}^d | sample complexity: \Omega(d/\varepsilon^2) | Hurt |
| Use exact advice and test it against samples | Product-distribution identity testing · Product distributions on {0,1}^d | sample complexity: \Theta(\sqrt{d}/\varepsilon^2) versus \Theta(d/\varepsilon^2) | Helped |
Surprising findings
- Balancedness is necessary: without it, linear samples are needed even when the advice is O(eps)-close in l1.
- Sublinear sample complexity is impossible when ||p-q||_1 >> eps sqrt(d), so advice must be accurate to help.
Limitations
- Requires tau-balanced assumption on the true distribution; the result degrades with balancedness parameter tau.
- Sublinear gains only when ||p-q||_1 is small (below eps*sqrt(d)-scale).
- Extension to Bayesian networks, Ising models, and unstructured discrete domains left open.
Experimental setup
Metrics: sample complexity total variation distance
Baselines: empirical mean estimator
Builds on: Gaussian mean estimation with advice Diakonikolas-Kane tolerant identity tester Scheffe tournament
Closest papers by meaning
- Learning multivariate Gaussians with imperfect advice (ICML 2025 · similarity 0.84)
- Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue (NeurIPS 2026 · similarity 0.84)
- Computational Explorations of Total Variation Distance (ICLR 2025 · similarity 0.82)
- Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.82)
- Iterative Chow Filtering for Learning with Distribution Shift (NeurIPS 2026 · similarity 0.81)
- Distribution Learning with Valid Outputs Beyond the Worst-Case (NeurIPS 2024 · similarity 0.81)
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.