Reproduce “Algorithms for the Communication of Samples” 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
Lucas Theis, Noureldin Yosri
Researchers from Google developed Ordered Random Coding (ORC) and Hybrid Coding, two new reverse channel coding schemes that enhance the efficient communication of samples for applications like neural compression and differential privacy. ORC unifies existing methods to achieve near-optimal coding costs with finite candidates, while Hybrid Coding significantly reduces computational costs for distributions with bounded support, demonstrating exponential speedups over PFR for Gaussian distributions.
Key insights
- Ordered Random Coding (ORC) unifies importance sampling and Poisson Functional Representation, inheriting PFR's near-optimal coding cost bounds (I[X,Z] + log(I[X,Z]+1) + 4) while operating with a finite, manageable number of candidates.
- Hybrid Coding significantly reduces computational costs for distributions with bounded support, outperforming PFR with exponential speedups for Gaussian distributions, making it practical for real-world applications.
- Unlike Minimal Random Coding, ORC's coding cost converges, allowing for improved sample quality by increasing the number of candidates without incurring an unbounded communication overhead.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.