Research map / Learning theory and algorithms / Sample complexity
Robust Density Estimation from Batches: The Best Things in Life are (Nearly) Free
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 |
|---|---|---|---|
| Replace prior filtering with SDP-relaxation-based filtering that uses optimal ~O(k) samples for Ak learning | robust Ak-distance density estimation from batches · theory; simulations on discrete domain l=500 | sample complexity in Ak distance | Improved |
| Scale k from 10 to 50 with good batches set to k/β² | proposed Ak filtering estimator · discrete domain l=500, β=0.4 | Ak-distance | No clear effect |
| Replace Ak-distance learning with TV-distance learning for piecewise polynomials via reduction | Pt,d distributions · theory | sample complexity | Improved |
Closest papers by meaning
- A General Method for Robust Learning from Batches (NeurIPS 2020 · similarity 0.92)
- Optimal Robust Learning of Discrete Distributions from Batches (ICML 2020 · similarity 0.90)
- Robust learning of halfspaces under log-concave marginals (NeurIPS 2025 · similarity 0.86)
- Consistent Adversarially Robust Linear Classification: Non-Parametric Setting (ICML 2024 · similarity 0.85)
- Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness (NeurIPS 2024 · similarity 0.85)
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.85)
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.
