Research map / Learning theory and algorithms / Sample complexity
Convergence Guarantees for the Good-Turing Estimator
Amichai Painsky
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 |
|---|---|---|---|
| use Good-Turing instead of ML, Laplace, smooth GT or PML | occupancy probability estimation · Zipf's law (s=1.01, m=10000), k=0 and k=1 | MSE | Improved |
| use ML or PML instead of Good-Turing for larger k | occupancy probability estimation · Zipf's law (m=10000), k=10 | MSE | Improved |
| use the hybrid GT-ML estimator | occupancy probability estimation · Zipf's law (m=10000), k=10 | MSE: equals ML for n < 317 and GT otherwise | Improved |
| use GT instead of PML | occupancy probability estimation · Uniform distribution (m=10000), k=0 | MSE | Improved |
| use GT (and hybrid GT-ML) instead of alternatives | occupancy probability estimation · Step distribution (m=10000) | MSE | Improved |
| use hybrid GT-ML estimator | occupancy probability estimation · Hamilton corpus (m=3578), k=8 | MSE: equals ML for n < 181 and GT otherwise | Improved |
| use Laplace instead of GT | occupancy probability estimation · Skin biota (m=1221, n<=100), k=1 | MSE | Hurt |
| use hybrid GT-ML estimator | occupancy probability estimation · US Census last names (m=1000), k=8 | MSE: equals GT for n >= 182 | Improved |
| use simultaneous bound instead of marginal bound for GT-ML threshold (ablation) | MSE bound for set of occupancy probabilities · Theoretical bound, K={0..n} | MSE bound: optimal threshold less than 20 for n = 20,000 | Improved |
| restrict alphabet size to bounded m in the GT bound (ablation) | Good-Turing MSE bound · Theoretical bound, varying m/n | MSE bound | Improved |
Closest papers by meaning
- A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.83)
- Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees (NeurIPS 2025 · similarity 0.82)
- Near-Optimality of Contrastive Divergence Algorithms (NeurIPS 2024 · similarity 0.82)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.82)
- Theoretical guarantees on the best-of-n alignment policy (ICML 2025 · similarity 0.82)
- Occupancy-based Quantile Risk Control (NeurIPS 2026 · similarity 0.82)
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.
