Reproduce “On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford
Researchers at Stanford University developed an efficient algorithm for Profile Maximum Likelihood (PML) that achieves sample-optimal estimation of symmetric properties for error regimes where ǫ ≫ n⁻¹ᐟ³. This closes a long-standing gap by realizing PML's full statistical potential with a computationally feasible approach, matching theoretical limits for universal estimators.
Key insights
- A `β-approximate PML with respect to a specific discretization set R` is statistically sufficient to achieve `ǫ ≫ n⁻¹ᐟ³` optimality, rather than requiring an exact PML.
- The novel `swapmatrixround` procedure drastically reduces the L1 error in matrix rounding to `O(|R|)`, leading to an `exp(-O(min(k, |R|) log n))` approximation loss.
- This reduced approximation loss, tied to `|R| = O(n^(1/3))` for the target regime, enables efficient algorithms to match the full statistical power of PML.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.