# Uniform Brackets, Containers, and Combinatorial Macbeath Regions

arXiv: https://arxiv.org/abs/2111.10048 · HTML: https://mlsanity.com/paper/2111.10048/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 41 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 9 of 9)

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [On Communication Complexity of Classification Problems](https://mlsanity.com/paper/1711.05893/) (2017)
- [The Communication Complexity of Optimization](https://mlsanity.com/paper/1906.05832/) (2019)
- [Optimal Approximate Polytope Membership](https://mlsanity.com/paper/1612.01696/) (2016)
- [Optimal Bound on the Combinatorial Complexity of Approximating Polytopes](https://mlsanity.com/paper/1910.14459/) (2019)
- [On the Combinatorial Complexity of Approximating Polytopes](https://mlsanity.com/paper/1604.01175/) (2016)
- [Epsilon-approximations and epsilon-nets](https://mlsanity.com/paper/1702.03676/) (2017)

## Abstract (arXiv)

We study the connections between three seemingly different combinatorial structures - "uniform" brackets in statistics and probability theory, "containers" in online and distributed learning theory, and "combinatorial Macbeath regions", or Mnets in discrete and computational geometry. We show that these three concepts are manifestations of a single combinatorial property that can be expressed under a unified framework along the lines of Vapnik-Chervonenkis type theory for uniform convergence. These new connections help us to bring tools from discrete and computational geometry to prove improved bounds for these objects. Our improved bounds help to get an optimal algorithm for distributed learning of halfspaces, an improved algorithm for the distributed convex set disjointness problem, and improved regret bounds for online algorithms against a smoothed adversary for a large class of semi-algebraic threshold functions.