Reproduce “Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models” 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
Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu, Zhewei Wei
Algorithms are presented that achieve near-optimal communication complexities for ℓp heavy hitters and Fp estimation in both static coordinator and dynamic distributed tracking models. The work from Fudan University and Renmin University of China establishes communication bounds matching theoretical lower limits up to logarithmic factors, simplifying prior methods and resolving several open problems.
Key insights
- A novel sampling strategy for ℓ2-heavy hitters (HH) yields an εℓ'2 error guarantee, forming a robust foundation for more general problems.
- The 'thresholding trick' is effective in transforming ℓ2-HH solutions into ℓp-HH solutions for p > 2, avoiding the universe size 'n' dependence.
- Dynamizing sampling algorithms with non-linear probabilities requires a multi-round, piecewise linear approximation technique to maintain optimality in dynamic tracking models.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.