Uniform Brackets, Containers, and Combinatorial Macbeath Regions
  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.
