Research map / Learning theory and algorithms / Sample complexity
Optimal Robust Learning of Discrete Distributions from Batches
Ayush Jain, Alon Orlitsky
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase alphabet size while holding n=1000 and β=0.4, with m=k/(0.4)^2 | Robust Distribution Estimator · Synthetic data, varying alphabet size k | L1 loss | No clear effect |
| Increase batch size while keeping total sample count constant | Robust Distribution Estimator · Synthetic data, varying batch size n | L1 loss | Improved |
| Increase adversarial fraction β | Robust Distribution Estimator · Synthetic data, varying adversarial noise level | L1 loss | Hurt |
| Increase the number of batches | Robust Distribution Estimator · Synthetic data, varying number of batches | L1 loss | Mixed |
| Use the naive empirical estimator over all batches instead of robust batch filtering | Synthetic distribution learning · Synthetic data, varying alphabet size k | L1 loss | Hurt |
| Use adversarial batches drawn from a distribution far from the target | Robust Distribution Estimator · Synthetic data, adversarial distribution distance | L1 loss | Improved |
Closest papers by meaning
- A General Method for Robust Learning from Batches (NeurIPS 2020 · similarity 0.92)
- Robust Density Estimation from Batches: The Best Things in Life are (Nearly) Free (ICML 2021 · similarity 0.90)
- Communication-Efficient Distributed Learning of Discrete Distributions (NeurIPS 2017 · similarity 0.86)
- A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation (ICML 2025 · similarity 0.84)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.83)
- Near-Optimality of Contrastive Divergence Algorithms (NeurIPS 2024 · similarity 0.83)
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.
